Generated on Sat Feb 7 2015 02:01:28 for Gecode by doxygen 1.8.9.1
memory-manager.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Contributing authors:
7  * Guido Tack <tack@gecode.org>
8  *
9  * Bugfixes provided by:
10  * Zandra Norman
11  *
12  * Copyright:
13  * Christian Schulte, 2002
14  * Guido Tack, 2004
15  *
16  * Last modified:
17  * $Date: 2013-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
18  * $Revision: 13840 $
19  *
20  * This file is part of Gecode, the generic constraint
21  * development environment:
22  * http://www.gecode.org
23  *
24  * Permission is hereby granted, free of charge, to any person obtaining
25  * a copy of this software and associated documentation files (the
26  * "Software"), to deal in the Software without restriction, including
27  * without limitation the rights to use, copy, modify, merge, publish,
28  * distribute, sublicense, and/or sell copies of the Software, and to
29  * permit persons to whom the Software is furnished to do so, subject to
30  * the following conditions:
31  *
32  * The above copyright notice and this permission notice shall be
33  * included in all copies or substantial portions of the Software.
34  *
35  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
36  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
37  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
38  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
39  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
40  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
41  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
42  *
43  */
44 
45 namespace Gecode {
46 
48  class MemoryChunk {
49  public:
53  size_t size;
54  };
55 
57  class HeapChunk : public MemoryChunk {
58  public:
60  double area[1];
61  };
62 
63  class Region;
64 
66  class SharedMemory {
67  friend class Region;
68  private:
70  unsigned int use_cnt;
72  struct {
74  size_t free;
76  double area[MemoryConfig::region_area_size / sizeof(double)];
77  } region;
79  struct {
81  unsigned int n_hc;
84  } heap;
85  public:
87  SharedMemory(void);
89  void flush(void);
91  ~SharedMemory(void);
93  //@
95  bool region_alloc(size_t s, void*& p);
97  //@
100  HeapChunk* heap_alloc(size_t s, size_t l);
102  void heap_free(HeapChunk* hc);
104  SharedMemory* copy(bool share);
107  bool release(void);
109  static void* operator new(size_t s);
111  static void operator delete(void* p);
112  };
113 
114 
123  class FreeList {
124  protected:
127  public:
129  FreeList(void);
131  FreeList(FreeList* n);
133  FreeList* next(void) const;
135  FreeList** nextRef(void);
137  void next(FreeList* n);
138  };
139 
142  public:
146  MemoryManager(SharedMemory* sm, MemoryManager& mm, size_t s_sub);
148  void release(SharedMemory* sm);
149 
150  private:
151  size_t cur_hcsz;
152  HeapChunk* cur_hc;
153  size_t requested;
154 
155  char* start;
156  size_t lsz;
157 
160  void alloc_refill(SharedMemory* sm, size_t s);
162  void alloc_fill(SharedMemory* sm, size_t s, bool first);
163 
164  public:
166  void* alloc(SharedMemory* sm, size_t s);
168  void* subscriptions(void) const;
169 
170  private:
174  template<size_t> void fl_refill(SharedMemory* sm);
176  static size_t sz2i(size_t);
178  static size_t i2sz(size_t);
179 
180  public:
182  template<size_t s>
183  void* fl_alloc(SharedMemory* sm);
185  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
186 
187  private:
189  MemoryChunk* slack;
190  public:
192  void reuse(void* p, size_t s);
193  };
194 
195 
196  /*
197  * Shared memory area
198  *
199  */
200 
201  forceinline void*
202  SharedMemory::operator new(size_t s) {
203  return Gecode::heap.ralloc(s);
204  }
205  forceinline void
206  SharedMemory::operator delete(void* p) {
208  }
211  : use_cnt(1) {
212  region.free = MemoryConfig::region_area_size;
213  heap.n_hc = 0;
214  heap.hc = NULL;
215  }
216  forceinline void
218  heap.n_hc = 0;
219  while (heap.hc != NULL) {
220  HeapChunk* hc = heap.hc;
221  heap.hc = static_cast<HeapChunk*>(hc->next);
222  Gecode::heap.rfree(hc);
223  }
224  }
227  flush();
228  }
230  SharedMemory::copy(bool share) {
231  if (share) {
232  use_cnt++;
233  return this;
234  } else {
235  return new SharedMemory();
236  }
237  }
238  forceinline bool
240  return --use_cnt == 0;
241  }
242  forceinline bool
243  SharedMemory::region_alloc(size_t s, void*& p) {
245  if (s > region.free)
246  return false;
247  region.free -= s;
248  p = ptr_cast<char*>(&region.area[0]) + region.free;
249  return true;
250  }
252  SharedMemory::heap_alloc(size_t s, size_t l) {
253  while ((heap.hc != NULL) && (heap.hc->size < l)) {
254  heap.n_hc--;
255  HeapChunk* hc = heap.hc;
256  heap.hc = static_cast<HeapChunk*>(hc->next);
257  Gecode::heap.rfree(hc);
258  }
259  if (heap.hc == NULL) {
260  assert(heap.n_hc == 0);
261  HeapChunk* hc = static_cast<HeapChunk*>(Gecode::heap.ralloc(s));
262  hc->size = s;
263  return hc;
264  } else {
265  heap.n_hc--;
266  HeapChunk* hc = heap.hc;
267  heap.hc = static_cast<HeapChunk*>(hc->next);
268  return hc;
269  }
270  }
271  forceinline void
273  if (heap.n_hc == MemoryConfig::n_hc_cache) {
274  Gecode::heap.rfree(hc);
275  } else {
276  heap.n_hc++;
277  hc->next = heap.hc; heap.hc = hc;
278  }
279  }
280 
281 
282  /*
283  * Freelists
284  *
285  */
286 
289 
292  : _next(n) {}
293 
295  FreeList::next(void) const {
296  return _next;
297  }
298 
301  return &_next;
302  }
303 
304  forceinline void
306  _next = n;
307  }
308 
309  forceinline size_t
310  MemoryManager::sz2i(size_t s) {
314  }
315 
316  forceinline size_t
317  MemoryManager::i2sz(size_t i) {
319  }
320 
321 
322  /*
323  * The active memory manager
324  *
325  */
326 
327  forceinline void*
329  assert(sz > 0);
330  // Perform alignment
332  // Check whether sufficient memory left
333  if (sz > lsz)
334  alloc_refill(sm,sz);
335  lsz -= sz;
336  return start + lsz;
337  }
338 
339  forceinline void*
341  return &cur_hc->area[0];
342  }
343 
344  forceinline void
345  MemoryManager::alloc_fill(SharedMemory* sm, size_t sz, bool first) {
346  // Adjust current heap chunk size
347  if (((requested > MemoryConfig::hcsz_inc_ratio*cur_hcsz) ||
348  (sz > cur_hcsz)) &&
349  (cur_hcsz < MemoryConfig::hcsz_max) &&
350  !first) {
351  cur_hcsz <<= 1;
352  }
353  // Increment the size that it caters for the initial overhead
354  size_t overhead = sizeof(HeapChunk) - sizeof(double);
355  sz += overhead;
356  // Round size to next multiple of current heap chunk size
357  size_t allocate = ((sz > cur_hcsz) ?
358  (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
359  // Request a chunk of preferably size allocate, but at least size sz
360  HeapChunk* hc = sm->heap_alloc(allocate,sz);
361  start = ptr_cast<char*>(&hc->area[0]);
362  lsz = hc->size - overhead;
363  // Link heap chunk, where the first heap chunk is kept in place
364  if (first) {
365  requested = hc->size;
366  hc->next = NULL; cur_hc = hc;
367  } else {
368  requested += hc->size;
369  hc->next = cur_hc->next; cur_hc->next = hc;
370  }
371 #ifdef GECODE_MEMORY_CHECK
372  for (char* c = start; c < (start+lsz); c++)
373  *c = 0;
374 #endif
375  }
376 
379  : cur_hcsz(MemoryConfig::hcsz_min), requested(0), slack(NULL) {
380  alloc_fill(sm,cur_hcsz,true);
382  i--; )
383  fl[i] = NULL;
384  }
385 
388  size_t s_sub)
389  : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
390  MemoryConfig::align(s_sub);
391  if ((mm.requested < MemoryConfig::hcsz_dec_ratio*mm.cur_hcsz) &&
392  (cur_hcsz > MemoryConfig::hcsz_min) &&
393  (s_sub*2 < cur_hcsz))
394  cur_hcsz >>= 1;
395  alloc_fill(sm,cur_hcsz+s_sub,true);
396  // Skip the memory area at the beginning for subscriptions
397  lsz -= s_sub;
398  start += s_sub;
400  i--; )
401  fl[i] = NULL;
402  }
403 
404  forceinline void
406  // Release all allocated heap chunks
407  HeapChunk* hc = cur_hc;
408  do {
409  HeapChunk* t = hc; hc = static_cast<HeapChunk*>(hc->next);
410  sm->heap_free(t);
411  } while (hc != NULL);
412  }
413 
414 
415 
416  /*
417  * Slack memory management
418  *
419  */
420  forceinline void
421  MemoryManager::reuse(void* p, size_t s) {
422 #ifdef GECODE_MEMORY_CHECK
423  {
424  char* c = static_cast<char*>(p);
425  char* e = c + s;
426  while (c < e) {
427  *c = 0; c++;
428  }
429  }
430 #endif
432  return;
434  MemoryChunk* rc = static_cast<MemoryChunk*>(p);
435  rc->next = slack;
436  rc->size = s;
437  slack = rc;
438  } else {
439  size_t i = sz2i(s);
440  FreeList* f = static_cast<FreeList*>(p);
441  f->next(fl[i]); fl[i]=f;
442  }
443  }
444 
445 
446  /*
447  * Freelist management
448  *
449  */
450 
451  template<size_t s>
452  forceinline void*
454  size_t i = sz2i(s);
455  FreeList* f = fl[i];
456  if (f == NULL) {
457  fl_refill<s>(sm); f = fl[i];
458  }
459  FreeList* n = f->next();
460  fl[i] = n;
461  return f;
462  }
463 
464  template<size_t s>
465  forceinline void
467  size_t i = sz2i(s);
468 #ifdef GECODE_AUDIT
469  FreeList* cur = f;
470  while (cur != l) {
471  assert(cur->next());
472  cur = cur->next();
473  }
474 #endif
475  l->next(fl[i]); fl[i] = f;
476  }
477 
478  template<size_t sz>
479  void
480  MemoryManager::fl_refill(SharedMemory* sm) {
481  // Try to acquire memory from slack
482  if (slack != NULL) {
483  MemoryChunk* m = slack;
484  slack = NULL;
485  do {
486  char* block = ptr_cast<char*>(m);
487  size_t s = m->size;
488  assert(s >= sz);
489  m = m->next;
490  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
491  while (s >= 2*sz) {
492  ptr_cast<FreeList*>(block)->next(ptr_cast<FreeList*>(block+sz));
493  block += sz;
494  s -= sz;
495  }
496  ptr_cast<FreeList*>(block)->next(NULL);
497  } while (m != NULL);
498  } else {
499  char* block = static_cast<char*>(alloc(sm,MemoryConfig::fl_refill*sz));
500  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
501  int i = MemoryConfig::fl_refill-2;
502  do {
503  ptr_cast<FreeList*>(block+i*sz)->next(ptr_cast<FreeList*>(block+(i+1)*sz));
504  } while (--i >= 0);
505  ptr_cast<FreeList*>(block+
506  (MemoryConfig::fl_refill-1)*sz)->next
507  (ptr_cast<FreeList*>(NULL));
508  }
509  }
510 
511 }
512 
513 // STATISTICS: kernel-memory
Memory chunk with size information.
void * subscriptions(void) const
Get the memory area for subscriptions.
const int fl_size_max
Maximal size for free list element.
MemoryManager(SharedMemory *sm)
Constructor initialization.
NodeType t
Type of node.
Definition: bool-expr.cpp:234
SharedMemory(void)
Initialize.
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const unsigned int n_hc_cache
How many heap chunks should be cached at most.
const int hcsz_inc_ratio
Increment ratio for chunk size.
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
void fl_dispose(FreeList *f, FreeList *l)
Release all free list elements of size s between f and l (inclusive)
void * fl_alloc(SharedMemory *sm)
Allocate free list element of size s.
Manage memory for space.
const size_t hcsz_min
Minimal size of a heap chunk requested from the OS.
HeapChunk * heap_alloc(size_t s, size_t l)
Return heap chunk, preferable of size s, but at least of size l.
bool region_alloc(size_t s, void *&p)
Return memory chunk if available.
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
FreeList * next(void) const
Return next freelist object.
SharedMemory * copy(bool share)
Return copy during cloning.
const size_t hcsz_max
Maximal size of a heap chunk requested from the OS.
Memory chunk allocated from heap with proper alignment.
Handle to region.
Definition: region.hpp:61
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
const int hcsz_dec_ratio
Decrement ratio for chunk size.
FreeList(void)
Use uninitialized.
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void release(SharedMemory *sm)
Release all allocated heap chunks.
const int fl_refill
Number of free lists elements to allocate.
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
FreeList * _next
Pointer to next freelist object.
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
void * alloc(SharedMemory *sm, size_t s)
Allocate memory of size s.
~SharedMemory(void)
Destructor.
T ptr_cast(void *p)
Cast p into pointer of type T.
Definition: cast.hpp:54
const int fl_size_min
Minimal size for free list element.
double area[1]
Start of memory area inside chunk.
size_t size
Size of chunk.
const size_t region_area_size
Size of region area.
#define forceinline
Definition: config.hpp:132
Base-class for freelist-managed objects.
unsigned int n_hc
How many heap chunks are available for caching.
void heap_free(HeapChunk *hc)
Free heap chunk (or cache for later)
const int fl_unit_size
Unit size for free lists.
HeapChunk * hc
A list of cached heap chunks.
double area[MemoryConfig::region_area_size/sizeof(double)]
The actual memory area (allocated from top to bottom)
Gecode toplevel namespace
size_t free
Amount of free memory.
MemoryChunk * next
Next chunk.
void align(size_t &s)
Align size s to the required alignment.
Shared object for several memory areas.
void flush(void)
Flush all cached memory.
bool release(void)
Release by one space.