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