memory-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 * Copyright: 00010 * Christian Schulte, 2002 00011 * Guido Tack, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00015 * $Revision: 9692 $ 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 00045 class MemoryChunk { 00046 public: 00048 MemoryChunk* next; 00050 size_t size; 00051 }; 00052 00054 class HeapChunk : public MemoryChunk { 00055 public: 00057 double area[1]; 00058 }; 00059 00060 class Region; 00061 00063 class SharedMemory { 00064 friend class Region; 00065 private: 00067 unsigned int use_cnt; 00069 struct { 00071 size_t free; 00073 double area[MemoryConfig::region_area_size / sizeof(double)]; 00074 } region; 00076 struct { 00078 unsigned int n_hc; 00080 HeapChunk* hc; 00081 } heap; 00082 public: 00084 SharedMemory(void); 00086 void flush(void); 00088 ~SharedMemory(void); 00090 //@ 00092 bool region_alloc(size_t s, void*& p); 00094 00095 //@ 00097 HeapChunk* heap_alloc(size_t s, size_t l); 00099 void heap_free(HeapChunk* hc); 00101 00102 SharedMemory* copy(bool share); 00104 bool release(void); 00106 static void* operator new(size_t s); 00108 static void operator delete(void* p); 00109 }; 00110 00111 00120 class FreeList { 00121 protected: 00123 FreeList* _next; 00124 public: 00126 FreeList(void); 00128 FreeList(FreeList* n); 00130 FreeList* next(void) const; 00132 FreeList** nextRef(void); 00134 void next(FreeList* n); 00135 }; 00136 00138 class MemoryManager { 00139 public: 00141 MemoryManager(SharedMemory* sm); 00143 MemoryManager(SharedMemory* sm, MemoryManager& mm, size_t s_sub); 00145 void release(SharedMemory* sm); 00146 00147 private: 00148 size_t cur_hcsz; 00149 HeapChunk* cur_hc; 00150 size_t requested; 00151 00152 char* start; 00153 size_t lsz; 00154 00156 GECODE_KERNEL_EXPORT 00157 void alloc_refill(SharedMemory* sm, size_t s); 00159 void alloc_fill(SharedMemory* sm, size_t s, bool first); 00160 00161 public: 00163 void* alloc(SharedMemory* sm, size_t s); 00165 size_t allocated(void) const; 00167 void* subscriptions(void) const; 00168 00169 private: 00171 FreeList* fl[MemoryConfig::fl_size_max-MemoryConfig::fl_size_min+1]; 00173 template<size_t> void fl_refill(SharedMemory* sm); 00175 static size_t sz2i(size_t); 00177 static size_t i2sz(size_t); 00178 00179 public: 00181 template<size_t s> 00182 void* fl_alloc(SharedMemory* sm); 00184 template<size_t> void fl_dispose(FreeList* f, FreeList* l); 00185 00186 private: 00188 MemoryChunk* slack; 00189 public: 00191 void reuse(void* p, size_t s); 00192 }; 00193 00194 00195 /* 00196 * Shared memory area 00197 * 00198 */ 00199 00200 forceinline void* 00201 SharedMemory::operator new(size_t s) { 00202 return Gecode::heap.ralloc(s); 00203 } 00204 forceinline void 00205 SharedMemory::operator delete(void* p) { 00206 Gecode::heap.rfree(p); 00207 } 00208 forceinline 00209 SharedMemory::SharedMemory(void) 00210 : use_cnt(1) { 00211 region.free = MemoryConfig::region_area_size; 00212 heap.n_hc = 0; 00213 heap.hc = NULL; 00214 } 00215 forceinline void 00216 SharedMemory::flush(void) { 00217 heap.n_hc = 0; 00218 while (heap.hc != NULL) { 00219 HeapChunk* hc = heap.hc; 00220 heap.hc = static_cast<HeapChunk*>(hc->next); 00221 Gecode::heap.rfree(hc); 00222 } 00223 } 00224 forceinline 00225 SharedMemory::~SharedMemory(void) { 00226 flush(); 00227 } 00228 forceinline SharedMemory* 00229 SharedMemory::copy(bool share) { 00230 if (share) { 00231 use_cnt++; 00232 return this; 00233 } else { 00234 return new SharedMemory(); 00235 } 00236 } 00237 forceinline bool 00238 SharedMemory::release(void) { 00239 return --use_cnt == 0; 00240 } 00241 forceinline bool 00242 SharedMemory::region_alloc(size_t s, void*& p) { 00243 MemoryConfig::align(s); 00244 if (s > region.free) 00245 return false; 00246 region.free -= s; 00247 p = Support::ptr_cast<char*>(®ion.area[0]) + region.free; 00248 return true; 00249 } 00250 forceinline HeapChunk* 00251 SharedMemory::heap_alloc(size_t s, size_t l) { 00252 while ((heap.hc != NULL) && (heap.hc->size < l)) { 00253 heap.n_hc--; 00254 HeapChunk* hc = heap.hc; 00255 heap.hc = static_cast<HeapChunk*>(hc->next); 00256 Gecode::heap.rfree(hc); 00257 } 00258 if (heap.hc == NULL) { 00259 assert(heap.n_hc == 0); 00260 HeapChunk* hc = static_cast<HeapChunk*>(Gecode::heap.ralloc(s)); 00261 hc->size = s; 00262 return hc; 00263 } else { 00264 heap.n_hc--; 00265 HeapChunk* hc = heap.hc; 00266 heap.hc = static_cast<HeapChunk*>(hc->next); 00267 return hc; 00268 } 00269 } 00270 forceinline void 00271 SharedMemory::heap_free(HeapChunk* hc) { 00272 if (heap.n_hc == MemoryConfig::n_hc_cache) { 00273 Gecode::heap.rfree(hc); 00274 } else { 00275 heap.n_hc++; 00276 hc->next = heap.hc; heap.hc = hc; 00277 } 00278 } 00279 00280 00281 /* 00282 * Freelists 00283 * 00284 */ 00285 00286 forceinline 00287 FreeList::FreeList(void) {} 00288 00289 forceinline 00290 FreeList::FreeList(FreeList* n) 00291 : _next(n) {} 00292 00293 forceinline FreeList* 00294 FreeList::next(void) const { 00295 return _next; 00296 } 00297 00298 forceinline FreeList** 00299 FreeList::nextRef(void) { 00300 return &_next; 00301 } 00302 00303 forceinline void 00304 FreeList::next(FreeList* n) { 00305 _next = n; 00306 } 00307 00308 forceinline size_t 00309 MemoryManager::sz2i(size_t s) { 00310 assert(s >= (MemoryConfig::fl_size_min << MemoryConfig::fl_unit_size)); 00311 assert(s <= (MemoryConfig::fl_size_max << MemoryConfig::fl_unit_size)); 00312 return (s >> MemoryConfig::fl_unit_size) - MemoryConfig::fl_size_min; 00313 } 00314 00315 forceinline size_t 00316 MemoryManager::i2sz(size_t i) { 00317 return (i + MemoryConfig::fl_size_min) << MemoryConfig::fl_unit_size; 00318 } 00319 00320 00321 /* 00322 * The active memory manager 00323 * 00324 */ 00325 00326 forceinline size_t 00327 MemoryManager::allocated(void) const { 00328 return requested; 00329 } 00330 00331 forceinline void* 00332 MemoryManager::alloc(SharedMemory* sm, size_t sz) { 00333 assert(sz > 0); 00334 // Perform alignment 00335 MemoryConfig::align(sz); 00336 // Check whether sufficient memory left 00337 if (sz > lsz) 00338 alloc_refill(sm,sz); 00339 lsz -= sz; 00340 return start + lsz; 00341 } 00342 00343 forceinline void* 00344 MemoryManager::subscriptions(void) const { 00345 return &cur_hc->area[0]; 00346 } 00347 00348 forceinline void 00349 MemoryManager::alloc_fill(SharedMemory* sm, size_t sz, bool first) { 00350 // Adjust current heap chunk size 00351 if (((requested > MemoryConfig::hcsz_inc_ratio*cur_hcsz) || 00352 (sz > cur_hcsz)) && 00353 (cur_hcsz < MemoryConfig::hcsz_max)) { 00354 cur_hcsz <<= 1; 00355 } 00356 // Increment the size that it caters for the initial overhead 00357 size_t overhead = sizeof(HeapChunk) - sizeof(double); 00358 sz += overhead; 00359 // Round size to next multiple of current heap chunk size 00360 size_t allocate = ((sz > cur_hcsz) ? 00361 (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz); 00362 // Request a chunk of preferably size allocate, but at least size sz 00363 HeapChunk* hc = sm->heap_alloc(allocate,sz); 00364 start = Support::ptr_cast<char*>(&hc->area[0]); 00365 lsz = hc->size - overhead; 00366 // Link heap chunk, where the first heap chunk is kept in place 00367 if (first) { 00368 requested = hc->size; 00369 hc->next = NULL; cur_hc = hc; 00370 } else { 00371 requested += hc->size; 00372 hc->next = cur_hc->next; cur_hc->next = hc; 00373 } 00374 #ifdef GECODE_MEMORY_CHECK 00375 for (char* c = start; c < (start+lsz); c++) 00376 *c = 0; 00377 #endif 00378 } 00379 00380 forceinline 00381 MemoryManager::MemoryManager(SharedMemory* sm) 00382 : cur_hcsz(MemoryConfig::hcsz_min), requested(0), slack(NULL) { 00383 alloc_fill(sm,cur_hcsz,true); 00384 for (size_t i = MemoryConfig::fl_size_max-MemoryConfig::fl_size_min+1; 00385 i--; ) 00386 fl[i] = NULL; 00387 } 00388 00389 forceinline 00390 MemoryManager::MemoryManager(SharedMemory* sm, MemoryManager& mm, 00391 size_t s_sub) 00392 : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) { 00393 MemoryConfig::align(s_sub); 00394 if ((mm.requested < MemoryConfig::hcsz_dec_ratio*mm.cur_hcsz) && 00395 (cur_hcsz > MemoryConfig::hcsz_min) && 00396 (s_sub*2 < cur_hcsz)) 00397 cur_hcsz >>= 1; 00398 alloc_fill(sm,cur_hcsz+s_sub,true); 00399 // Skip the memory area at the beginning for subscriptions 00400 lsz -= s_sub; 00401 start += s_sub; 00402 for (size_t i = MemoryConfig::fl_size_max-MemoryConfig::fl_size_min+1; 00403 i--; ) 00404 fl[i] = NULL; 00405 } 00406 00407 forceinline void 00408 MemoryManager::release(SharedMemory* sm) { 00409 // Release all allocated heap chunks 00410 HeapChunk* hc = cur_hc; 00411 do { 00412 HeapChunk* t = hc; hc = static_cast<HeapChunk*>(hc->next); 00413 sm->heap_free(t); 00414 } while (hc != NULL); 00415 } 00416 00417 00418 00419 /* 00420 * Slack memory management 00421 * 00422 */ 00423 forceinline void 00424 MemoryManager::reuse(void* p, size_t s) { 00425 #ifdef GECODE_MEMORY_CHECK 00426 { 00427 char* c = static_cast<char*>(p); 00428 char* e = c + s; 00429 while (c < e) { 00430 *c = 0; c++; 00431 } 00432 } 00433 #endif 00434 if (s < (MemoryConfig::fl_size_min<<MemoryConfig::fl_unit_size)) 00435 return; 00436 if (s > (MemoryConfig::fl_size_max<<MemoryConfig::fl_unit_size)) { 00437 MemoryChunk* rc = static_cast<MemoryChunk*>(p); 00438 rc->next = slack; 00439 rc->size = s; 00440 slack = rc; 00441 } else { 00442 size_t i = sz2i(s); 00443 FreeList* f = static_cast<FreeList*>(p); 00444 f->next(fl[i]); fl[i]=f; 00445 } 00446 } 00447 00448 00449 /* 00450 * Freelist management 00451 * 00452 */ 00453 00454 template<size_t s> 00455 forceinline void* 00456 MemoryManager::fl_alloc(SharedMemory* sm) { 00457 size_t i = sz2i(s); 00458 FreeList* f = fl[i]; 00459 if (f == NULL) { 00460 fl_refill<s>(sm); f = fl[i]; 00461 } 00462 FreeList* n = f->next(); 00463 fl[i] = n; 00464 return f; 00465 } 00466 00467 template<size_t s> 00468 forceinline void 00469 MemoryManager::fl_dispose(FreeList* f, FreeList* l) { 00470 size_t i = sz2i(s); 00471 l->next(fl[i]); fl[i] = f; 00472 } 00473 00474 template<size_t sz> 00475 void 00476 MemoryManager::fl_refill(SharedMemory* sm) { 00477 // Try to acquire memory from slack 00478 if (slack != NULL) { 00479 MemoryChunk* m = slack; 00480 slack = NULL; 00481 do { 00482 char* block = Support::ptr_cast<char*>(m); 00483 size_t s = m->size; 00484 assert(s >= sz); 00485 m = m->next; 00486 fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block); 00487 while (s >= 2*sz) { 00488 Support::ptr_cast<FreeList*>(block)->next 00489 (Support::ptr_cast<FreeList*>(block+sz)); 00490 block += sz; 00491 s -= sz; 00492 } 00493 Support::ptr_cast<FreeList*>(block)->next(NULL); 00494 } while (m != NULL); 00495 } else { 00496 char* block = static_cast<char*>(alloc(sm,MemoryConfig::fl_refill*sz)); 00497 fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block); 00498 int i = MemoryConfig::fl_refill-2; 00499 do { 00500 Support::ptr_cast<FreeList*>(block+i*sz)->next 00501 (Support::ptr_cast<FreeList*>(block+(i+1)*sz)); 00502 } while (--i >= 0); 00503 Support::ptr_cast<FreeList*>(block+ 00504 (MemoryConfig::fl_refill-1)*sz)->next 00505 (Support::ptr_cast<FreeList*>(NULL)); 00506 } 00507 } 00508 00509 } 00510 00511 // STATISTICS: kernel-core