Generated on Sun Feb 17 15:24:26 2019 for Gecode by doxygen 1.6.3

manager.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Guido Tack <tack@gecode.org>
00008  *
00009  *  Bugfixes provided by:
00010  *     Zandra Norman
00011  *
00012  *  Copyright:
00013  *     Christian Schulte, 2002
00014  *     Guido Tack, 2004
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  Permission is hereby granted, free of charge, to any person obtaining
00021  *  a copy of this software and associated documentation files (the
00022  *  "Software"), to deal in the Software without restriction, including
00023  *  without limitation the rights to use, copy, modify, merge, publish,
00024  *  distribute, sublicense, and/or sell copies of the Software, and to
00025  *  permit persons to whom the Software is furnished to do so, subject to
00026  *  the following conditions:
00027  *
00028  *  The above copyright notice and this permission notice shall be
00029  *  included in all copies or substantial portions of the Software.
00030  *
00031  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00032  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00033  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00034  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00035  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00036  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00037  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00038  *
00039  */
00040 
00041 namespace Gecode { namespace Kernel {
00042 
00044   class MemoryChunk {
00045   public:
00047     MemoryChunk* next;
00049     size_t size;
00050   };
00051 
00053   class HeapChunk : public MemoryChunk {
00054   public:
00056     double area[1];
00057   };
00058 
00060   class SharedMemory {
00061   private:
00063     struct {
00065       unsigned int n_hc;
00067       HeapChunk* hc;
00068     } heap;
00070     GECODE_KERNEL_EXPORT static Support::Mutex& m(void);
00071   public:
00073     SharedMemory(void);
00075     ~SharedMemory(void);
00077     //@
00079     HeapChunk* alloc(size_t s, size_t l);
00081     void free(HeapChunk* hc);
00083   };
00084 
00085 
00086 }}
00087 
00088 namespace Gecode {
00089 
00098   class FreeList {
00099   protected:
00101     FreeList* _next;
00102   public:
00104     FreeList(void);
00106     FreeList(FreeList* n);
00108     FreeList* next(void) const;
00110     FreeList** nextRef(void);
00112     void next(FreeList* n);
00113   };
00114 
00115 }
00116 
00117 namespace Gecode { namespace Kernel {
00118 
00120   class MemoryManager {
00121   public:
00123     MemoryManager(SharedMemory& sm);
00125     MemoryManager(SharedMemory& sm, MemoryManager& mm, size_t s_sub);
00127     void release(SharedMemory& sm);
00128 
00129   private:
00130     size_t     cur_hcsz;  
00131     HeapChunk* cur_hc;    
00132     size_t     requested; 
00133 
00134     char*  start; 
00135     size_t lsz;   
00136 
00138     GECODE_KERNEL_EXPORT
00139     void alloc_refill(SharedMemory& sm, size_t s);
00141     void alloc_fill(SharedMemory& sm, size_t s, bool first);
00142 
00143   public:
00145     void* alloc(SharedMemory& sm, size_t s);
00147     void* subscriptions(void) const;
00148 
00149   private:
00151     FreeList* fl[MemoryConfig::fl_size_max-MemoryConfig::fl_size_min+1];
00153     template<size_t> void fl_refill(SharedMemory& sm);
00155     static size_t sz2i(size_t);
00157     static size_t i2sz(size_t);
00158 
00159   public:
00161     template<size_t s>
00162     void* fl_alloc(SharedMemory& sm);
00164     template<size_t> void  fl_dispose(FreeList* f, FreeList* l);
00165 
00166   private:
00168     MemoryChunk* slack;
00169   public:
00171     void reuse(void* p, size_t s);
00172   };
00173 
00174 }}
00175 
00176 namespace Gecode { namespace Kernel {
00177 
00178   /*
00179    * Shared memory area
00180    *
00181    */
00182 
00183   forceinline
00184   SharedMemory::SharedMemory(void) {
00185     heap.n_hc = 0;
00186     heap.hc = NULL;
00187   }
00188   forceinline
00189   SharedMemory::~SharedMemory(void) {
00190     while (heap.hc != NULL) {
00191       HeapChunk* hc = heap.hc;
00192       heap.hc = static_cast<HeapChunk*>(hc->next);
00193       Gecode::heap.rfree(hc);
00194     }
00195   }
00196 
00197   forceinline HeapChunk*
00198   SharedMemory::alloc(size_t s, size_t l) {
00199     // To protect from exceptions from heap.ralloc()
00200     Support::Lock guard(m());
00201     while ((heap.hc != NULL) && (heap.hc->size < l)) {
00202       heap.n_hc--;
00203       HeapChunk* hc = heap.hc;
00204       heap.hc = static_cast<HeapChunk*>(hc->next);
00205       Gecode::heap.rfree(hc);
00206     }
00207     HeapChunk* hc;
00208     if (heap.hc == NULL) {
00209       assert(heap.n_hc == 0);
00210       hc = static_cast<HeapChunk*>(Gecode::heap.ralloc(s));
00211       hc->size = s;
00212     } else {
00213       heap.n_hc--;
00214       hc = heap.hc;
00215       heap.hc = static_cast<HeapChunk*>(hc->next);
00216     }
00217     return hc;
00218   }
00219   forceinline void
00220   SharedMemory::free(HeapChunk* hc) {
00221     Support::Lock guard(m());
00222     if (heap.n_hc == MemoryConfig::n_hc_cache) {
00223       Gecode::heap.rfree(hc);
00224     } else {
00225       heap.n_hc++;
00226       hc->next = heap.hc; heap.hc = hc;
00227     }
00228   }
00229 
00230 
00231 }}
00232 
00233 namespace Gecode {
00234 
00235   /*
00236    * Freelists
00237    *
00238    */
00239 
00240   forceinline
00241   FreeList::FreeList(void) {}
00242 
00243   forceinline
00244   FreeList::FreeList(FreeList* n)
00245     : _next(n) {}
00246 
00247   forceinline FreeList*
00248   FreeList::next(void) const {
00249     return _next;
00250   }
00251 
00252   forceinline FreeList**
00253   FreeList::nextRef(void) {
00254     return &_next;
00255   }
00256 
00257   forceinline void
00258   FreeList::next(FreeList* n) {
00259     _next = n;
00260   }
00261 
00262 }
00263 
00264 namespace Gecode { namespace Kernel {
00265 
00266   /*
00267    * The active memory manager
00268    *
00269    */
00270 
00271   forceinline size_t
00272   MemoryManager::sz2i(size_t s) {
00273     assert(s >= (MemoryConfig::fl_size_min << MemoryConfig::fl_unit_size));
00274     assert(s <= (MemoryConfig::fl_size_max << MemoryConfig::fl_unit_size));
00275     return (s >> MemoryConfig::fl_unit_size) - MemoryConfig::fl_size_min;
00276   }
00277 
00278   forceinline size_t
00279   MemoryManager::i2sz(size_t i) {
00280     return (i + MemoryConfig::fl_size_min) << MemoryConfig::fl_unit_size;
00281   }
00282 
00283 
00284   forceinline void*
00285   MemoryManager::alloc(SharedMemory& sm, size_t sz) {
00286     assert(sz > 0);
00287     // Perform alignment
00288     MemoryConfig::align(sz);
00289     // Check whether sufficient memory left
00290     if (sz > lsz)
00291       alloc_refill(sm,sz);
00292     lsz -= sz;
00293     return start + lsz;
00294   }
00295 
00296   forceinline void*
00297   MemoryManager::subscriptions(void) const {
00298     return &cur_hc->area[0];
00299   }
00300 
00301   forceinline void
00302   MemoryManager::alloc_fill(SharedMemory& sm, size_t sz, bool first) {
00303     // Adjust current heap chunk size
00304     if (((requested > MemoryConfig::hcsz_inc_ratio*cur_hcsz) ||
00305          (sz > cur_hcsz)) &&
00306         (cur_hcsz < MemoryConfig::hcsz_max) &&
00307         !first) {
00308       cur_hcsz <<= 1;
00309     }
00310     // Increment the size that it caters for the initial overhead
00311     size_t overhead = sizeof(HeapChunk) - sizeof(double);
00312     sz += overhead;
00313     // Round size to next multiple of current heap chunk size
00314     size_t allocate = ((sz > cur_hcsz) ?
00315                        (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
00316     // Request a chunk of preferably size allocate, but at least size sz
00317     HeapChunk* hc = sm.alloc(allocate,sz);
00318     start = ptr_cast<char*>(&hc->area[0]);
00319     lsz   = hc->size - overhead;
00320     // Link heap chunk, where the first heap chunk is kept in place
00321     if (first) {
00322       requested = hc->size;
00323       hc->next = NULL; cur_hc = hc;
00324     } else {
00325       requested += hc->size;
00326       hc->next = cur_hc->next; cur_hc->next = hc;
00327     }
00328 #ifdef GECODE_MEMORY_CHECK
00329     for (char* c = start; c < (start+lsz); c++)
00330       *c = 0;
00331 #endif
00332   }
00333 
00334   forceinline
00335   MemoryManager::MemoryManager(SharedMemory& sm)
00336     : cur_hcsz(MemoryConfig::hcsz_min), requested(0), slack(NULL) {
00337     alloc_fill(sm,cur_hcsz,true);
00338     for (size_t i = 0; i<MemoryConfig::fl_size_max-MemoryConfig::fl_size_min+1;
00339          i++)
00340       fl[i] = NULL;
00341   }
00342 
00343   forceinline
00344   MemoryManager::MemoryManager(SharedMemory& sm, MemoryManager& mm,
00345                                size_t s_sub)
00346     : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
00347     MemoryConfig::align(s_sub);
00348     if ((mm.requested < MemoryConfig::hcsz_dec_ratio*mm.cur_hcsz) &&
00349         (cur_hcsz > MemoryConfig::hcsz_min) &&
00350         (s_sub*2 < cur_hcsz))
00351       cur_hcsz >>= 1;
00352     alloc_fill(sm,cur_hcsz+s_sub,true);
00353     // Skip the memory area at the beginning for subscriptions
00354     lsz   -= s_sub;
00355     start += s_sub;
00356     for (size_t i = 0; i<MemoryConfig::fl_size_max-MemoryConfig::fl_size_min+1;
00357          i++)
00358       fl[i] = NULL;
00359   }
00360 
00361   forceinline void
00362   MemoryManager::release(SharedMemory& sm) {
00363     // Release all allocated heap chunks
00364     HeapChunk* hc = cur_hc;
00365     do {
00366       HeapChunk* t = hc; hc = static_cast<HeapChunk*>(hc->next);
00367       sm.free(t);
00368     } while (hc != NULL);
00369   }
00370 
00371 
00372 
00373   /*
00374    * Slack memory management
00375    *
00376    */
00377   forceinline void
00378   MemoryManager::reuse(void* p, size_t s) {
00379 #ifdef GECODE_MEMORY_CHECK
00380     {
00381       char* c = static_cast<char*>(p);
00382       char* e = c + s;
00383       while (c < e) {
00384         *c = 0; c++;
00385       }
00386     }
00387 #endif
00388     if (s < (MemoryConfig::fl_size_min<<MemoryConfig::fl_unit_size))
00389       return;
00390     if (s > (MemoryConfig::fl_size_max<<MemoryConfig::fl_unit_size)) {
00391       MemoryChunk* rc = static_cast<MemoryChunk*>(p);
00392       rc->next = slack;
00393       rc->size = s;
00394       slack = rc;
00395     } else {
00396       size_t i = sz2i(s);
00397       FreeList* f = static_cast<FreeList*>(p);
00398       f->next(fl[i]); fl[i]=f;
00399     }
00400   }
00401 
00402 
00403   /*
00404    * Freelist management
00405    *
00406    */
00407 
00408   template<size_t s>
00409   forceinline void*
00410   MemoryManager::fl_alloc(SharedMemory& sm) {
00411     size_t i = sz2i(s);
00412     FreeList* f = fl[i];
00413     if (f == NULL) {
00414       fl_refill<s>(sm); f = fl[i];
00415     }
00416     FreeList* n = f->next();
00417     fl[i] = n;
00418     return f;
00419   }
00420 
00421   template<size_t s>
00422   forceinline void
00423   MemoryManager::fl_dispose(FreeList* f, FreeList* l) {
00424     size_t i = sz2i(s);
00425 #ifdef GECODE_AUDIT
00426     FreeList* cur = f;
00427     while (cur != l) {
00428       assert(cur->next());
00429       cur = cur->next();
00430     }
00431 #endif
00432     l->next(fl[i]); fl[i] = f;
00433   }
00434 
00435   template<size_t sz>
00436   void
00437   MemoryManager::fl_refill(SharedMemory& sm) {
00438     // Try to acquire memory from slack
00439     if (slack != NULL) {
00440       MemoryChunk* m = slack;
00441       slack = NULL;
00442       do {
00443         char*  block = ptr_cast<char*>(m);
00444         size_t s     = m->size;
00445         assert(s >= sz);
00446         m = m->next;
00447         fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
00448         while (s >= 2*sz) {
00449           ptr_cast<FreeList*>(block)->next(ptr_cast<FreeList*>(block+sz));
00450           block += sz;
00451           s     -= sz;
00452         }
00453         ptr_cast<FreeList*>(block)->next(NULL);
00454       } while (m != NULL);
00455     } else {
00456       char* block = static_cast<char*>(alloc(sm,MemoryConfig::fl_refill*sz));
00457       fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
00458       int i = MemoryConfig::fl_refill-2;
00459       do {
00460         ptr_cast<FreeList*>(block+i*sz)->next(ptr_cast<FreeList*>(block+(i+1)*sz));
00461       } while (--i >= 0);
00462       ptr_cast<FreeList*>(block+
00463                           (MemoryConfig::fl_refill-1)*sz)->next
00464         (ptr_cast<FreeList*>(NULL));
00465     }
00466   }
00467 
00468 }}
00469 
00470 // STATISTICS: kernel-memory