Generated on Mon May 5 05:54:00 2008 for Gecode by doxygen 1.5.5

memory-manager.icc

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  *  Copyright:
00010  *     Christian Schulte, 2002
00011  *     Guido Tack, 2004
00012  *
00013  *  Last modified:
00014  *     $Date: 2008-01-21 22:41:02 +0100 (Mon, 21 Jan 2008) $ by $Author: schulte $
00015  *     $Revision: 5936 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 namespace Gecode {
00043 
00044   namespace Memory {
00049     namespace Config {
00053       const size_t hcsz_min =  2 * 1024;
00061       const size_t hcsz_max = 64 * 1024;
00068       const int hcsz_inc_ratio = 8;
00078       const int hcsz_dec_ratio = 2;
00079 
00091       const int fl_unit_size = ((sizeof(void*) == 4) ? 2 : 3);
00100       const int fl_size_min  = ((sizeof(void*) == 4) ? 3 : 2);
00109       const int fl_size_max  = ((sizeof(void*) == 4) ? 3 : 3);
00117       const int fl_refill = 8;
00125 #ifndef GECODE_MEMORY_ALIGNMENT
00126 #define GECODE_MEMORY_ALIGNMENT 8
00127 #endif
00128     }
00129   }
00130 
00139   class FreeList {
00140   protected:
00142     FreeList* _next;
00143   public:
00145     FreeList(void);
00147     FreeList(FreeList* n);
00149     FreeList* next(void) const;
00151     void next(FreeList* n);
00152   };
00153 
00155   class MemoryManager {
00156   private:
00158     class HeapChunk {
00159     public:
00161       HeapChunk* next;
00163       double area[1];
00164     };
00165   public:
00167     MemoryManager(void);
00169     MemoryManager(MemoryManager& mm, size_t s_sub);
00171     ~MemoryManager(void);
00172 
00173   private:
00174     size_t     cur_hcsz;  
00175     HeapChunk* cur_hc;    
00176     size_t     requested; 
00177 
00178     char*  start; 
00179     size_t lsz;   
00180 
00182     GECODE_KERNEL_EXPORT
00183     void alloc_refill(size_t s);
00185     void alloc_fill(size_t s, bool first);
00186 
00187   public:
00189     void* alloc(size_t s);
00191     size_t allocated(void) const;
00193     void* subscriptions(void) const;
00194 
00195   private:
00197     FreeList* fl[Memory::Config::fl_size_max-Memory::Config::fl_size_min+1];
00199     template <size_t> void fl_refill(void);
00201     static size_t sz2i(size_t);
00203     static size_t i2sz(size_t);
00204 
00205   public:
00207     template <size_t s>
00208     void* fl_alloc(void);
00210     template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
00211 
00212   private:
00214     class ReuseChunk {
00215     public:
00217       size_t      size;
00219       ReuseChunk* next;
00220     };
00222     ReuseChunk* slack;
00223   public:
00225     void reuse(void* p, size_t s);
00226   };
00227 
00228 
00229   /*
00230    * Freelists
00231    *
00232    */
00233 
00234   forceinline
00235   FreeList::FreeList(void) {}
00236 
00237   forceinline
00238   FreeList::FreeList(FreeList* n)
00239     : _next(n) {}
00240 
00241   forceinline FreeList*
00242   FreeList::next(void) const {
00243     return _next;
00244   }
00245 
00246   forceinline void
00247   FreeList::next(FreeList* n) {
00248     _next = n;
00249   }
00250 
00251   forceinline size_t
00252   MemoryManager::sz2i(size_t s) {
00253     assert(s >= (Memory::Config::fl_size_min << Memory::Config::fl_unit_size));
00254     assert(s <= (Memory::Config::fl_size_max << Memory::Config::fl_unit_size));
00255     return (s >> Memory::Config::fl_unit_size) - Memory::Config::fl_size_min;
00256   }
00257 
00258   forceinline size_t
00259   MemoryManager::i2sz(size_t i) {
00260     return (i + Memory::Config::fl_size_min) << Memory::Config::fl_unit_size;
00261   }
00262 
00263 
00264   /*
00265    * The active memory manager
00266    *
00267    */
00268 
00269   forceinline size_t
00270   MemoryManager::allocated(void) const {
00271     return requested;
00272   }
00273 
00274   forceinline void*
00275   MemoryManager::alloc(size_t sz) {
00276     // Size must be a multiple of four
00277     assert((sz > 0) && ((sz % 4) == 0));
00278 #if GECODE_MEMORY_ALIGNMENT == 8
00279     // Performs alignment to 8 bytes
00280     sz += sz & 4;
00281 #endif
00282     // Check whether sufficient memory left
00283     if (sz > lsz)
00284       alloc_refill(sz);
00285     lsz -= sz;
00286     return start + lsz;
00287   }
00288 
00289   forceinline void*
00290   MemoryManager::subscriptions(void) const {
00291     return &cur_hc->area[0];
00292   }
00293 
00294   forceinline void
00295   MemoryManager::alloc_fill(size_t sz, bool first) {
00296     // Adjust current heap chunk size
00297     if (((requested > Memory::Config::hcsz_inc_ratio*cur_hcsz) ||
00298          (sz > cur_hcsz)) &&
00299         (cur_hcsz < Memory::Config::hcsz_max)) {
00300       cur_hcsz <<= 1;
00301     }
00302     // Increment the size that it caters for the initial overhead
00303     size_t overhead = sizeof(HeapChunk) - sizeof(double);
00304     sz += overhead;
00305     // Round size to next multiple of current heap chunk size
00306     size_t allocate = ((sz > cur_hcsz) ?
00307                        (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
00308     // Request a chunk of size allocate
00309     HeapChunk* hc = static_cast<HeapChunk*>(Memory::malloc(allocate));
00310     start = Support::ptr_cast<char*>(&hc->area[0]);
00311     lsz   = allocate - overhead;
00312     // Link heap chunk, where the first heap chunk is kept in place
00313     if (first) {
00314       requested = allocate;
00315       hc->next = NULL; cur_hc = hc;
00316     } else {
00317       requested += allocate;
00318       hc->next = cur_hc->next; cur_hc->next = hc;
00319     }
00320 #ifdef GECODE_MEMORY_CHECK
00321     for (char* c = start; c < (start+lsz); c++)
00322       *c = 0;
00323 #endif
00324   }
00325 
00326   forceinline
00327   MemoryManager::MemoryManager(void)
00328     : cur_hcsz(Memory::Config::hcsz_min), requested(0), slack(NULL) {
00329     alloc_fill(cur_hcsz,true);
00330     for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00331          i--; )
00332       fl[i] = NULL;
00333   }
00334 
00335   forceinline
00336   MemoryManager::MemoryManager(MemoryManager& mm, size_t s_sub)
00337     : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
00338 #if GECODE_MEMORY_ALIGNMENT == 8
00339     s_sub += s_sub & 4;
00340 #endif
00341     if ((mm.requested < Memory::Config::hcsz_dec_ratio*mm.cur_hcsz) &&
00342         (cur_hcsz > Memory::Config::hcsz_min) &&
00343         (s_sub*2 < cur_hcsz))
00344       cur_hcsz >>= 1;
00345     alloc_fill(cur_hcsz+s_sub,true);
00346     // Skip the memory area at the beginning for subscriptions
00347     lsz   -= s_sub;
00348     start += s_sub;
00349     for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00350          i--; )
00351       fl[i] = NULL;
00352   }
00353 
00354   forceinline
00355   MemoryManager::~MemoryManager(void) {
00356     // Release all allocated heap chunks
00357     HeapChunk* hc = cur_hc;
00358     do {
00359       HeapChunk* t = hc; hc = hc->next;
00360       Memory::free(t);
00361     } while (hc != NULL);
00362   }
00363 
00364 
00365 
00366   /*
00367    * Slack memory management
00368    *
00369    */
00370   forceinline void
00371   MemoryManager::reuse(void* p, size_t s) {
00372 #ifdef GECODE_MEMORY_CHECK
00373     {
00374       char* c = static_cast<char*>(p);
00375       char* e = c + s;
00376       while (c < e) {
00377         *c = 0; c++;
00378       }
00379     }
00380 #endif
00381     if (s < (Memory::Config::fl_size_min<<Memory::Config::fl_unit_size))
00382       return;
00383     if (s > (Memory::Config::fl_size_max<<Memory::Config::fl_unit_size)) {
00384       ReuseChunk* rc = static_cast<ReuseChunk*>(p);
00385       rc->next = slack;
00386       rc->size = s;
00387       slack = rc;
00388     } else {
00389       size_t i = sz2i(s);
00390       FreeList* f = static_cast<FreeList*>(p);
00391       f->next(fl[i]); fl[i]=f;
00392     }
00393   }
00394 
00395 
00396   /*
00397    * Freelist management
00398    *
00399    */
00400 
00401   template <size_t s>
00402   forceinline void*
00403   MemoryManager::fl_alloc(void) {
00404     size_t i = sz2i(s);
00405     FreeList* f = fl[i];
00406     if (f == NULL) {
00407       fl_refill<s>(); f = fl[i];
00408     }
00409     FreeList* n = f->next();
00410     fl[i] = n;
00411     return f;
00412   }
00413 
00414   template <size_t s>
00415   forceinline void
00416   MemoryManager::fl_dispose(FreeList* f, FreeList* l) {
00417     size_t i = sz2i(s);
00418     l->next(fl[i]); fl[i] = f;
00419   }
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 = Support::ptr_cast<char*>(m);
00430         size_t s     = m->size;
00431         assert(s >= sz);
00432         m = m->next;
00433         fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block);
00434         while (s >= 2*sz) {
00435           Support::ptr_cast<FreeList*>(block)->next
00436             (Support::ptr_cast<FreeList*>(block+sz));
00437           block += sz;
00438           s     -= sz;
00439         }
00440         Support::ptr_cast<FreeList*>(block)->next(NULL);
00441       } while (m != NULL);
00442     } else {
00443       char* block = static_cast<char*>(alloc(Memory::Config::fl_refill*sz));
00444       fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block);
00445       int i = Memory::Config::fl_refill-2;
00446       do {
00447         Support::ptr_cast<FreeList*>(block+i*sz)->next
00448           (Support::ptr_cast<FreeList*>(block+(i+1)*sz));
00449       } while (--i >= 0);
00450       Support::ptr_cast<FreeList*>(block+
00451                                    (Memory::Config::fl_refill-1)*sz)->next
00452         (Support::ptr_cast<FreeList*>(NULL));
00453     }
00454   }
00455 
00456 }
00457 
00458 // STATISTICS: kernel-core