memory-manager.icc
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
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
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
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
00277 assert((sz > 0) && ((sz % 4) == 0));
00278
00279 sz += sz & ((GECODE_MEMORY_ALIGNMENT >> 1) & 4);
00280
00281 if (sz > lsz)
00282 alloc_refill(sz);
00283 lsz -= sz;
00284 return start + lsz;
00285 }
00286
00287 forceinline void*
00288 MemoryManager::subscriptions(void) const {
00289 return &cur_hc->area[0];
00290 }
00291
00292 forceinline void
00293 MemoryManager::alloc_fill(size_t sz, bool first) {
00294
00295 if (((requested > Memory::Config::hcsz_inc_ratio*cur_hcsz) ||
00296 (sz > cur_hcsz)) &&
00297 (cur_hcsz < Memory::Config::hcsz_max)) {
00298 cur_hcsz <<= 1;
00299 }
00300
00301 size_t overhead = sizeof(HeapChunk) - sizeof(double);
00302 sz += overhead;
00303
00304 size_t allocate = ((sz > cur_hcsz) ?
00305 (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
00306
00307 HeapChunk* hc = static_cast<HeapChunk*>(Memory::malloc(allocate));
00308 start = Support::ptr_cast<char*>(&hc->area[0]);
00309 lsz = allocate - overhead;
00310
00311 if (first) {
00312 requested = allocate;
00313 hc->next = NULL; cur_hc = hc;
00314 } else {
00315 requested += allocate;
00316 hc->next = cur_hc->next; cur_hc->next = hc;
00317 }
00318 #ifdef GECODE_MEMORY_CHECK
00319 for (char* c = start; c < (start+lsz); c++)
00320 *c = 0;
00321 #endif
00322 }
00323
00324 forceinline
00325 MemoryManager::MemoryManager(void)
00326 : cur_hcsz(Memory::Config::hcsz_min), requested(0), slack(NULL) {
00327 alloc_fill(cur_hcsz,true);
00328 for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00329 i--; )
00330 fl[i] = NULL;
00331 }
00332
00333 forceinline
00334 MemoryManager::MemoryManager(MemoryManager& mm, size_t s_sub)
00335 : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
00336 s_sub += s_sub & ((GECODE_MEMORY_ALIGNMENT >> 1) & 4);
00337 if ((mm.requested < Memory::Config::hcsz_dec_ratio*mm.cur_hcsz) &&
00338 (cur_hcsz > Memory::Config::hcsz_min) &&
00339 (s_sub*2 < cur_hcsz))
00340 cur_hcsz >>= 1;
00341 alloc_fill(cur_hcsz+s_sub,true);
00342
00343 lsz -= s_sub;
00344 start += s_sub;
00345 for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00346 i--; )
00347 fl[i] = NULL;
00348 }
00349
00350 forceinline
00351 MemoryManager::~MemoryManager(void) {
00352
00353 HeapChunk* hc = cur_hc;
00354 do {
00355 HeapChunk* t = hc; hc = hc->next;
00356 Memory::free(t);
00357 } while (hc != NULL);
00358 }
00359
00360
00361
00362
00363
00364
00365
00366 forceinline void
00367 MemoryManager::reuse(void* p, size_t s) {
00368 #ifdef GECODE_MEMORY_CHECK
00369 {
00370 char* c = static_cast<char*>(p);
00371 char* e = c + s;
00372 while (c < e) {
00373 *c = 0; c++;
00374 }
00375 }
00376 #endif
00377 if (s < (Memory::Config::fl_size_min<<Memory::Config::fl_unit_size))
00378 return;
00379 if (s > (Memory::Config::fl_size_max<<Memory::Config::fl_unit_size)) {
00380 ReuseChunk* rc = static_cast<ReuseChunk*>(p);
00381 rc->next = slack;
00382 rc->size = s;
00383 slack = rc;
00384 } else {
00385 size_t i = sz2i(s);
00386 FreeList* f = static_cast<FreeList*>(p);
00387 f->next(fl[i]); fl[i]=f;
00388 }
00389 }
00390
00391
00392
00393
00394
00395
00396
00397 template <size_t s>
00398 forceinline void*
00399 MemoryManager::fl_alloc(void) {
00400 size_t i = sz2i(s);
00401 FreeList* f = fl[i];
00402 if (f == NULL) {
00403 fl_refill<s>(); f = fl[i];
00404 }
00405 FreeList* n = f->next();
00406 fl[i] = n;
00407 return f;
00408 }
00409
00410 template <size_t s>
00411 forceinline void
00412 MemoryManager::fl_dispose(FreeList* f, FreeList* l) {
00413 size_t i = sz2i(s);
00414 l->next(fl[i]); fl[i] = f;
00415 }
00416
00417 template <size_t sz>
00418 void
00419 MemoryManager::fl_refill(void) {
00420
00421 if (slack != NULL) {
00422 ReuseChunk* m = slack;
00423 slack = NULL;
00424 do {
00425 char* block = Support::ptr_cast<char*>(m);
00426 size_t s = m->size;
00427 assert(s >= sz);
00428 m = m->next;
00429 fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block);
00430 while (s >= 2*sz) {
00431 Support::ptr_cast<FreeList*>(block)->next
00432 (Support::ptr_cast<FreeList*>(block+sz));
00433 block += sz;
00434 s -= sz;
00435 }
00436 Support::ptr_cast<FreeList*>(block)->next(NULL);
00437 } while (m != NULL);
00438 } else {
00439 char* block = static_cast<char*>(alloc(Memory::Config::fl_refill*sz));
00440 fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block);
00441 int i = Memory::Config::fl_refill-2;
00442 do {
00443 Support::ptr_cast<FreeList*>(block+i*sz)->next
00444 (Support::ptr_cast<FreeList*>(block+(i+1)*sz));
00445 } while (--i >= 0);
00446 Support::ptr_cast<FreeList*>(block+
00447 (Memory::Config::fl_refill-1)*sz)->next
00448 (Support::ptr_cast<FreeList*>(NULL));
00449 }
00450 }
00451
00452 }
00453
00454