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: 2006-08-07 20:47:02 +0200 (Mon, 07 Aug 2006) $ by $Author: schulte $ 00014 * $Revision: 3525 $ 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 = 2 * 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* reusealloc(size_t s); 00209 }; 00210 00211 00212 /* 00213 * Freelists 00214 * 00215 */ 00216 00217 forceinline 00218 FreeList::FreeList(void) {} 00219 00220 forceinline 00221 FreeList::FreeList(FreeList* n) 00222 : _next(n) {} 00223 00224 forceinline FreeList* 00225 FreeList::next(void) const { 00226 return _next; 00227 } 00228 00229 forceinline void 00230 FreeList::next(FreeList* n) { 00231 _next = n; 00232 } 00233 00234 forceinline size_t 00235 MemoryManager::sz2i(size_t s) { 00236 assert((s % (1 << Memory::Config::fl_unit_size)) == 0); 00237 assert(s >= (Memory::Config::fl_size_min << Memory::Config::fl_unit_size)); 00238 assert(s <= (Memory::Config::fl_size_max << Memory::Config::fl_unit_size)); 00239 return (s >> Memory::Config::fl_unit_size) - Memory::Config::fl_size_min; 00240 } 00241 00242 forceinline size_t 00243 MemoryManager::i2sz(size_t i) { 00244 return (i + Memory::Config::fl_size_min) << Memory::Config::fl_unit_size; 00245 } 00246 00247 00248 /* 00249 * The active memory manager 00250 * 00251 */ 00252 00253 forceinline size_t 00254 MemoryManager::allocated(void) const { 00255 return requested; 00256 } 00257 00258 forceinline void* 00259 MemoryManager::alloc(size_t sz) { 00260 // Size must be a multiple of four 00261 assert((sz > 0) && ((sz % 4) == 0)); 00262 #if GECODE_MEMORY_ALIGNMENT == 8 00263 // Performs alignment to 8 bytes 00264 sz += sz & 4; 00265 #endif 00266 // Check whether sufficient memory left 00267 if (sz > lsz) 00268 alloc_refill(sz); 00269 lsz -= sz; 00270 return start + lsz; 00271 } 00272 00273 forceinline void 00274 MemoryManager::alloc_fill(size_t sz) { 00275 // Adjust current heap chunk size 00276 if (((requested > Memory::Config::hcsz_inc_ratio*cur_hcsz) || 00277 (sz > cur_hcsz)) && 00278 (cur_hcsz < Memory::Config::hcsz_max)) { 00279 cur_hcsz <<= 1; 00280 } 00281 00282 // Round size to next multiple of current heap chunk size 00283 lsz = ((sz > cur_hcsz) ? 00284 (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz); 00285 00286 // Request as close as possible a chunk with lsz sizes free 00287 #if GECODE_MEMORY_ALIGNMENT == 4 00288 requested += lsz; 00289 HeapChunk* hc = reinterpret_cast<HeapChunk*> 00290 (Memory::malloc(sizeof(HeapChunk)+lsz-sizeof(double))); 00291 start = reinterpret_cast<char*>(&(hc->area[0])); 00292 #endif 00293 #if GECODE_MEMORY_ALIGNMENT == 8 00294 // Leave room for adjusting alignment by 4 00295 requested += lsz+sizeof(double); 00296 HeapChunk* hc = reinterpret_cast<HeapChunk*> 00297 (Memory::malloc(sizeof(HeapChunk)+lsz)); 00298 start = reinterpret_cast<char*>(&(hc->area[0])); 00299 // This is four if it is only four aligned 00300 size_t size_adj = reinterpret_cast<size_t>(start) & 4; 00301 start += size_adj; 00302 lsz += sizeof(double) - size_adj; 00303 #endif 00304 // Link heap chunk 00305 hc->next = cur_hc; cur_hc = hc; 00306 #ifdef GECODE_MEMORY_CHECK 00307 for (char* c = start; c < (start+lsz); c++) 00308 *c = 0; 00309 #endif 00310 } 00311 00312 forceinline void 00313 MemoryManager::init(void) { 00314 cur_hc = NULL; 00315 requested = 0; 00316 alloc_fill(cur_hcsz); 00317 for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1; 00318 i--; ) 00319 fl[i] = NULL; 00320 } 00321 00322 forceinline 00323 MemoryManager::MemoryManager(void) 00324 : cur_hcsz(Memory::Config::hcsz_min), slack(NULL) { 00325 init(); 00326 } 00327 00328 forceinline 00329 MemoryManager::MemoryManager(MemoryManager& mm) 00330 : cur_hcsz(mm.cur_hcsz), slack(NULL) { 00331 if ((mm.requested < Memory::Config::hcsz_dec_ratio*mm.cur_hcsz) && 00332 (mm.cur_hcsz > Memory::Config::hcsz_min)) 00333 cur_hcsz >>= 1; 00334 init(); 00335 } 00336 00337 forceinline 00338 MemoryManager::~MemoryManager(void) { 00339 // Release all allocated heap chunks 00340 HeapChunk* hc = cur_hc; 00341 do { 00342 HeapChunk* t = hc; hc = hc->next; 00343 Memory::free(t); 00344 } while (hc != NULL); 00345 } 00346 00347 00348 /* 00349 * Slack memory management 00350 * 00351 */ 00352 forceinline void 00353 MemoryManager::reuse(void* p, size_t s) { 00354 #ifdef GECODE_MEMORY_CHECK 00355 { 00356 char* c = reinterpret_cast<char*>(p); 00357 char* e = c + s; 00358 while (c < e) { 00359 *c = 0; c++; 00360 } 00361 } 00362 #endif 00363 if (s >= (Memory::Config::fl_size_max<<Memory::Config::fl_unit_size)) { 00364 ReuseChunk* rc = reinterpret_cast<ReuseChunk*>(p); 00365 rc->next = slack; 00366 rc->size = s; 00367 slack = rc; 00368 } 00369 } 00370 00371 00372 /* 00373 * Freelist management 00374 * 00375 */ 00376 00377 template <size_t s> 00378 forceinline void* 00379 MemoryManager::fl_alloc(void) { 00380 size_t i = sz2i(s); 00381 FreeList* f = fl[i]; 00382 if (f == NULL) { 00383 fl_refill<s>(); f = fl[i]; 00384 } 00385 FreeList* n = f->next(); 00386 fl[i] = n; 00387 return f; 00388 } 00389 00390 template <size_t s> 00391 forceinline void 00392 MemoryManager::fl_dispose(FreeList* f, FreeList* l) { 00393 size_t i = sz2i(s); 00394 l->next(fl[i]); fl[i] = f; 00395 } 00396 00397 #define GECODE_KERNEL_PTR2FL(p) (reinterpret_cast<FreeList*>(p)) 00398 #define GECODE_KERNEL_PTR2CH(p) (reinterpret_cast<char*>(p)) 00399 00400 template <size_t sz> 00401 void 00402 MemoryManager::fl_refill(void) { 00403 // Try to acquire memory from slack 00404 if (slack != NULL) { 00405 ReuseChunk* m = slack; 00406 slack = NULL; 00407 do { 00408 char* block = GECODE_KERNEL_PTR2CH(m); 00409 size_t s = m->size; 00410 assert(s >= sz); 00411 m = m->next; 00412 fl[sz2i(sz)] = GECODE_KERNEL_PTR2FL(block); 00413 while (s >= 2*sz) { 00414 GECODE_KERNEL_PTR2FL(block)->next(GECODE_KERNEL_PTR2FL(block+sz)); 00415 block += sz; 00416 s -= sz; 00417 } 00418 GECODE_KERNEL_PTR2FL(block)->next(NULL); 00419 } while (m != NULL); 00420 } else { 00421 char* block = GECODE_KERNEL_PTR2CH(alloc(Memory::Config::fl_refill*sz)); 00422 fl[sz2i(sz)] = GECODE_KERNEL_PTR2FL(block); 00423 int i = Memory::Config::fl_refill-2; 00424 do { 00425 GECODE_KERNEL_PTR2FL(block+i*sz)->next 00426 (GECODE_KERNEL_PTR2FL(block+(i+1)*sz)); 00427 } while (--i >= 0); 00428 GECODE_KERNEL_PTR2FL(block+(Memory::Config::fl_refill-1)*sz)->next 00429 (GECODE_KERNEL_PTR2FL(NULL)); 00430 } 00431 } 00432 00433 #undef GECODE_KERNEL_PTR2FL 00434 #undef GECODE_KERNEL_PTR2CH 00435 00436 } 00437 00438 // STATISTICS: kernel-core