memory-manager.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
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
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
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
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
00335 MemoryConfig::align(sz);
00336
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
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
00357 size_t overhead = sizeof(HeapChunk) - sizeof(double);
00358 sz += overhead;
00359
00360 size_t allocate = ((sz > cur_hcsz) ?
00361 (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
00362
00363 HeapChunk* hc = sm->heap_alloc(allocate,sz);
00364 start = Support::ptr_cast<char*>(&hc->area[0]);
00365 lsz = hc->size - overhead;
00366
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
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
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
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
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
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