Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

memory-manager.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Contributing authors:
00006  *     Guido Tack <tack@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Christian Schulte, 2002
00010  *     Guido Tack, 2004
00011  *
00012  *  Last modified:
00013  *     $Date: 2005-11-18 14:08:53 +0100 (Fri, 18 Nov 2005) $ by $Author: schulte $
00014  *     $Revision: 2605 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
00023  *
00024  */
00025 
00026 namespace Gecode {
00027 
00028   namespace Memory {
00033     namespace Config {
00037       const size_t hcsz_min =  1 * 1024;
00045       const size_t hcsz_max = 64 * 1024;
00052       const int hcsz_inc_ratio = 8;
00062       const int hcsz_dec_ratio = 4;
00063       
00075       const int fl_unit_size = ((sizeof(void*) == 4) ? 2 : 3);
00084       const int fl_size_min  = ((sizeof(void*) == 4) ? 3 : 2);
00093       const int fl_size_max  = ((sizeof(void*) == 4) ? 3 : 2);
00101       const int fl_refill = 8;
00109 #ifndef GECODE_MEMORY_ALIGNMENT
00110 #define GECODE_MEMORY_ALIGNMENT 8
00111 #endif
00112     }
00113   }
00114 
00123   class FreeList {
00124   protected:
00125     FreeList* _next;
00126   public:
00127     FreeList(void);
00128     FreeList(FreeList*);
00129     FreeList* next(void) const;
00130     void next(FreeList*);
00131   };
00132   
00134   class MemoryManager {
00135   private:
00137     class HeapChunk {
00138     public:
00140       HeapChunk* next;
00142       double area[1];
00143     };
00144   private:
00146     void init(void);
00147   public:
00149     MemoryManager(void);
00151     MemoryManager(MemoryManager& mm);
00153     ~MemoryManager(void);
00154 
00155   private:
00156     size_t     cur_hcsz;  
00157     HeapChunk* cur_hc;    
00158     size_t     requested; 
00159 
00160     char*  start; 
00161     size_t lsz;   
00162 
00164     GECODE_KERNEL_EXPORT 
00165     void alloc_refill(size_t s);
00167     void alloc_fill(size_t s);
00168 
00169   public:
00171     void* alloc(size_t s);
00173     size_t allocated(void) const;
00174 
00175   private:
00177     FreeList* fl[Memory::Config::fl_size_max-Memory::Config::fl_size_min+1];
00179     template <size_t> void fl_refill(void);
00181     static size_t sz2i(size_t);
00183     static size_t i2sz(size_t);
00184 
00185   public:
00187     template <size_t s> 
00188     void* fl_alloc(void);
00190     template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
00191 
00192   public:
00194     class ReuseChunk {
00195     public:
00197       size_t      size;
00199       ReuseChunk* next;
00200     };
00201   private:
00203     ReuseChunk* slack;
00204   public:
00206     void reuse(void* p, size_t s);
00208     void reuse(ReuseChunk *rc);
00210     void* reusealloc(size_t s);
00211   };
00212 
00213 
00214   /*
00215    * Freelists
00216    *
00217    */
00218 
00219   forceinline
00220   FreeList::FreeList(void) {}
00221 
00222   forceinline
00223   FreeList::FreeList(FreeList* n)
00224     : _next(n) {}
00225 
00226   forceinline FreeList*
00227   FreeList::next(void) const {
00228     return _next;
00229   }
00230 
00231   forceinline void
00232   FreeList::next(FreeList* n) {
00233     _next = n;
00234   }
00235 
00236   forceinline size_t
00237   MemoryManager::sz2i(size_t s) {
00238     assert((s % (1 << Memory::Config::fl_unit_size)) == 0);
00239     assert(s >= (Memory::Config::fl_size_min << Memory::Config::fl_unit_size));
00240     assert(s <= (Memory::Config::fl_size_max << Memory::Config::fl_unit_size));
00241     return (s >> Memory::Config::fl_unit_size) - Memory::Config::fl_size_min;
00242   }
00243 
00244   forceinline size_t
00245   MemoryManager::i2sz(size_t i) {
00246     return (i + Memory::Config::fl_size_min) << Memory::Config::fl_unit_size;
00247   }
00248 
00249 
00250   /*
00251    * The active memory manager
00252    *
00253    */
00254 
00255   forceinline size_t
00256   MemoryManager::allocated(void) const {
00257     return requested;
00258   }
00259 
00260   forceinline void*
00261   MemoryManager::alloc(size_t sz) {
00262     // Size must be a multiple of four
00263     assert((sz > 0) && ((sz % 4) == 0));
00264 #if GECODE_MEMORY_ALIGNMENT == 8
00265     // Performs alignment to 8 bytes
00266     sz += sz & 4;
00267 #endif
00268     // Check whether sufficient memory left
00269     if (sz > lsz)
00270       alloc_refill(sz);
00271     lsz -= sz;
00272     return start + lsz;
00273   }
00274 
00275   forceinline void
00276   MemoryManager::alloc_fill(size_t sz) {
00277     // Adjust current heap chunk size
00278     if (((requested > Memory::Config::hcsz_inc_ratio*cur_hcsz) || 
00279          (sz > cur_hcsz)) && 
00280         (cur_hcsz < Memory::Config::hcsz_max)) {
00281       cur_hcsz <<= 1;
00282     }
00283 
00284     // Round size to next multiple of current heap chunk size
00285     lsz = ((sz > cur_hcsz) ?
00286            (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
00287 
00288     // Request as close as possible a chunk with lsz sizes free
00289 #if GECODE_MEMORY_ALIGNMENT == 4
00290     requested += lsz;
00291     HeapChunk* hc = reinterpret_cast<HeapChunk*>
00292       (Memory::malloc(sizeof(HeapChunk)+lsz-sizeof(double)));
00293     start = reinterpret_cast<char*>(&(hc->area[0]));
00294 #endif
00295 #if GECODE_MEMORY_ALIGNMENT == 8
00296     // Leave room for adjusting alignment by 4
00297     requested += lsz+sizeof(double);
00298     HeapChunk* hc = reinterpret_cast<HeapChunk*>
00299       (Memory::malloc(sizeof(HeapChunk)+lsz));
00300     start = reinterpret_cast<char*>(&(hc->area[0]));
00301     // This is four if it is only four aligned
00302     size_t size_adj = reinterpret_cast<size_t>(start) & 4;
00303     start += size_adj;
00304     lsz += sizeof(double) - size_adj;
00305 #endif
00306     // Link heap chunk
00307     hc->next = cur_hc; cur_hc = hc;
00308 #ifdef GECODE_MEMORY_CHECK
00309     for (char* c = start; c < (start+lsz); c++)
00310       *c = 0;
00311 #endif
00312   }
00313 
00314   forceinline void
00315   MemoryManager::init(void) {
00316     cur_hc    = NULL;
00317     requested = 0;
00318     alloc_fill(cur_hcsz);
00319     for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00320          i--; )
00321       fl[i] = NULL;
00322   }
00323 
00324   forceinline
00325   MemoryManager::MemoryManager(void)
00326     : cur_hcsz(Memory::Config::hcsz_min), slack(NULL) {
00327     init();
00328   }
00329 
00330   forceinline
00331   MemoryManager::MemoryManager(MemoryManager& mm)
00332     : cur_hcsz(mm.cur_hcsz), slack(NULL) {
00333     if ((mm.requested < Memory::Config::hcsz_dec_ratio*mm.cur_hcsz) && 
00334         (mm.cur_hcsz > Memory::Config::hcsz_min))
00335       cur_hcsz >>= 1;
00336     init();
00337   }
00338 
00339   forceinline
00340   MemoryManager::~MemoryManager(void) {
00341     // Release all allocated heap chunks
00342     HeapChunk* hc = cur_hc;
00343     do {
00344       HeapChunk* t = hc; hc = hc->next;
00345       Memory::free(t);
00346     } while (hc != NULL);
00347   }
00348 
00349 
00350   /*
00351    * Slack memory management
00352    *
00353    */
00354   forceinline void
00355   MemoryManager::reuse(void* p, size_t s) {
00356 #ifdef GECODE_MEMORY_CHECK
00357     {
00358       char* c = reinterpret_cast<char*>(p);
00359       char* e = c + s;
00360       while (c < e) {
00361         *c = 0; c++;
00362       }
00363     }
00364 #endif
00365     if (s >= (Memory::Config::fl_size_max<<Memory::Config::fl_unit_size)) {
00366       ReuseChunk* rc = reinterpret_cast<ReuseChunk*>(p);
00367       rc->next = slack;
00368       rc->size = s;
00369       slack = rc;
00370     }
00371   }
00372 
00373   forceinline void
00374   MemoryManager::reuse(ReuseChunk* rc) {
00375 #ifdef GECODE_MEMORY_CHECK
00376     {
00377       size_t s = rc->size;
00378       char* c = reinterpret_cast<char*>(rc);
00379       char* e = c + s;
00380       while (c < e) {
00381         *c = 0; c++;
00382       }
00383       rc->size = s;
00384     }
00385 #endif
00386     assert(rc->size >= 
00387            (Memory::Config::fl_size_max<<Memory::Config::fl_unit_size));
00388     rc->next = slack;
00389     slack = rc;
00390   }
00391 
00392 
00393   /*
00394    * Freelist management
00395    *
00396    */
00397 
00398   template <size_t s>
00399   forceinline void*
00400   MemoryManager::fl_alloc(void) {
00401     size_t i = sz2i(s);
00402     FreeList* f = fl[i];
00403     if (f == NULL) {
00404       fl_refill<s>(); f = fl[i];
00405     }
00406     FreeList* n = f->next();
00407     fl[i] = n;
00408     return f;
00409   }
00410 
00411   template <size_t s>
00412   forceinline void
00413   MemoryManager::fl_dispose(FreeList* f, FreeList* l) {
00414     size_t i = sz2i(s);
00415     l->next(fl[i]); fl[i] = f;
00416   }
00417 
00418 #define GECODE_PTR2FL(p) (reinterpret_cast<FreeList*>(p))
00419 #define GECODE_PTR2CH(p) (reinterpret_cast<char*>(p))
00420 
00421   template <size_t sz>
00422   void
00423   MemoryManager::fl_refill(void) {
00424     // Try to acquire memory from slack
00425     if (slack != NULL) {
00426       ReuseChunk* m = slack; 
00427       slack = NULL;
00428       do {
00429         char*  block = GECODE_PTR2CH(m);
00430         size_t s     = m->size;
00431         assert(s >= sz);
00432         m = m->next;
00433         fl[sz2i(sz)] = GECODE_PTR2FL(block);
00434         while (s >= 2*sz) {
00435           GECODE_PTR2FL(block)->next(GECODE_PTR2FL(block+sz));
00436           block += sz;
00437           s     -= sz;
00438         }
00439         GECODE_PTR2FL(block)->next(NULL);
00440       } while (m != NULL);
00441     } else {
00442       char* block = GECODE_PTR2CH(alloc(Memory::Config::fl_refill*sz));
00443       fl[sz2i(sz)] = GECODE_PTR2FL(block);
00444       int i = Memory::Config::fl_refill-2;
00445       do {
00446         GECODE_PTR2FL(block+i*sz)->next(GECODE_PTR2FL(block+(i+1)*sz));
00447       } while (--i >= 0);
00448       GECODE_PTR2FL(block+(Memory::Config::fl_refill-1)*sz)->next
00449         (GECODE_PTR2FL(NULL));
00450     }
00451   }
00452 
00453 #undef GECODE_PTR2FL
00454 #undef GECODE_PTR2CH
00455 
00456 }
00457 
00458 // STATISTICS: kernel-core