Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
17  * development environment:
18  * http://www.gecode.org
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  *
39  */
40 
41 namespace Gecode { namespace Kernel {
42 
44  class MemoryChunk {
45  public:
49  size_t size;
50  };
51 
53  class HeapChunk : public MemoryChunk {
54  public:
56  double area[1];
57  };
58 
60  class SharedMemory {
61  private:
63  struct {
65  unsigned int n_hc;
68  } heap;
70  GECODE_KERNEL_EXPORT static Support::Mutex& m(void);
71  public:
73  SharedMemory(void);
75  ~SharedMemory(void);
77  //@
79  HeapChunk* alloc(size_t s, size_t l);
81  void free(HeapChunk* hc);
83  };
84 
85 
86 }}
87 
88 namespace Gecode {
89 
98  class FreeList {
99  protected:
102  public:
104  FreeList(void);
106  FreeList(FreeList* n);
108  FreeList* next(void) const;
110  FreeList** nextRef(void);
112  void next(FreeList* n);
113  };
114 
115 }
116 
117 namespace Gecode { namespace Kernel {
118 
121  public:
125  MemoryManager(SharedMemory& sm, MemoryManager& mm, size_t s_sub);
127  void release(SharedMemory& sm);
128 
129  private:
130  size_t cur_hcsz;
131  HeapChunk* cur_hc;
132  size_t requested;
133 
134  char* start;
135  size_t lsz;
136 
139  void alloc_refill(SharedMemory& sm, size_t s);
141  void alloc_fill(SharedMemory& sm, size_t s, bool first);
142 
143  public:
145  void* alloc(SharedMemory& sm, size_t s);
147  void* subscriptions(void) const;
148 
149  private:
153  template<size_t> void fl_refill(SharedMemory& sm);
155  static size_t sz2i(size_t);
157  static size_t i2sz(size_t);
158 
159  public:
161  template<size_t s>
162  void* fl_alloc(SharedMemory& sm);
164  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
165 
166  private:
168  MemoryChunk* slack;
169  public:
171  void reuse(void* p, size_t s);
172  };
173 
174 }}
175 
176 namespace Gecode { namespace Kernel {
177 
178  /*
179  * Shared memory area
180  *
181  */
182 
185  heap.n_hc = 0;
186  heap.hc = NULL;
187  }
190  while (heap.hc != NULL) {
191  HeapChunk* hc = heap.hc;
192  heap.hc = static_cast<HeapChunk*>(hc->next);
194  }
195  }
196 
198  SharedMemory::alloc(size_t s, size_t l) {
199  // To protect from exceptions from heap.ralloc()
200  Support::Lock guard(m());
201  while ((heap.hc != NULL) && (heap.hc->size < l)) {
202  heap.n_hc--;
203  HeapChunk* hc = heap.hc;
204  heap.hc = static_cast<HeapChunk*>(hc->next);
206  }
207  HeapChunk* hc;
208  if (heap.hc == NULL) {
209  assert(heap.n_hc == 0);
210  hc = static_cast<HeapChunk*>(Gecode::heap.ralloc(s));
211  hc->size = s;
212  } else {
213  heap.n_hc--;
214  hc = heap.hc;
215  heap.hc = static_cast<HeapChunk*>(hc->next);
216  }
217  return hc;
218  }
219  forceinline void
221  Support::Lock guard(m());
222  if (heap.n_hc == MemoryConfig::n_hc_cache) {
224  } else {
225  heap.n_hc++;
226  hc->next = heap.hc; heap.hc = hc;
227  }
228  }
229 
230 
231 }}
232 
233 namespace Gecode {
234 
235  /*
236  * Freelists
237  *
238  */
239 
242 
245  : _next(n) {}
246 
248  FreeList::next(void) const {
249  return _next;
250  }
251 
254  return &_next;
255  }
256 
257  forceinline void
259  _next = n;
260  }
261 
262 }
263 
264 namespace Gecode { namespace Kernel {
265 
266  /*
267  * The active memory manager
268  *
269  */
270 
271  forceinline size_t
272  MemoryManager::sz2i(size_t s) {
276  }
277 
278  forceinline size_t
279  MemoryManager::i2sz(size_t i) {
281  }
282 
283 
284  forceinline void*
286  assert(sz > 0);
287  // Perform alignment
289  // Check whether sufficient memory left
290  if (sz > lsz)
291  alloc_refill(sm,sz);
292  lsz -= sz;
293  return start + lsz;
294  }
295 
296  forceinline void*
298  return &cur_hc->area[0];
299  }
300 
301  forceinline void
302  MemoryManager::alloc_fill(SharedMemory& sm, size_t sz, bool first) {
303  // Adjust current heap chunk size
304  if (((requested > MemoryConfig::hcsz_inc_ratio*cur_hcsz) ||
305  (sz > cur_hcsz)) &&
306  (cur_hcsz < MemoryConfig::hcsz_max) &&
307  !first) {
308  cur_hcsz <<= 1;
309  }
310  // Increment the size that it caters for the initial overhead
311  size_t overhead = sizeof(HeapChunk) - sizeof(double);
312  sz += overhead;
313  // Round size to next multiple of current heap chunk size
314  size_t allocate = ((sz > cur_hcsz) ?
315  (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
316  // Request a chunk of preferably size allocate, but at least size sz
317  HeapChunk* hc = sm.alloc(allocate,sz);
318  start = ptr_cast<char*>(&hc->area[0]);
319  lsz = hc->size - overhead;
320  // Link heap chunk, where the first heap chunk is kept in place
321  if (first) {
322  requested = hc->size;
323  hc->next = NULL; cur_hc = hc;
324  } else {
325  requested += hc->size;
326  hc->next = cur_hc->next; cur_hc->next = hc;
327  }
328 #ifdef GECODE_MEMORY_CHECK
329  for (char* c = start; c < (start+lsz); c++)
330  *c = 0;
331 #endif
332  }
333 
336  : cur_hcsz(MemoryConfig::hcsz_min), requested(0), slack(NULL) {
337  alloc_fill(sm,cur_hcsz,true);
339  i++)
340  fl[i] = NULL;
341  }
342 
345  size_t s_sub)
346  : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
347  MemoryConfig::align(s_sub);
348  if ((mm.requested < MemoryConfig::hcsz_dec_ratio*mm.cur_hcsz) &&
349  (cur_hcsz > MemoryConfig::hcsz_min) &&
350  (s_sub*2 < cur_hcsz))
351  cur_hcsz >>= 1;
352  alloc_fill(sm,cur_hcsz+s_sub,true);
353  // Skip the memory area at the beginning for subscriptions
354  lsz -= s_sub;
355  start += s_sub;
357  i++)
358  fl[i] = NULL;
359  }
360 
361  forceinline void
363  // Release all allocated heap chunks
364  HeapChunk* hc = cur_hc;
365  do {
366  HeapChunk* t = hc; hc = static_cast<HeapChunk*>(hc->next);
367  sm.free(t);
368  } while (hc != NULL);
369  }
370 
371 
372 
373  /*
374  * Slack memory management
375  *
376  */
377  forceinline void
378  MemoryManager::reuse(void* p, size_t s) {
379 #ifdef GECODE_MEMORY_CHECK
380  {
381  char* c = static_cast<char*>(p);
382  char* e = c + s;
383  while (c < e) {
384  *c = 0; c++;
385  }
386  }
387 #endif
389  return;
391  MemoryChunk* rc = static_cast<MemoryChunk*>(p);
392  rc->next = slack;
393  rc->size = s;
394  slack = rc;
395  } else {
396  size_t i = sz2i(s);
397  FreeList* f = static_cast<FreeList*>(p);
398  f->next(fl[i]); fl[i]=f;
399  }
400  }
401 
402 
403  /*
404  * Freelist management
405  *
406  */
407 
408  template<size_t s>
409  forceinline void*
411  size_t i = sz2i(s);
412  FreeList* f = fl[i];
413  if (f == NULL) {
414  fl_refill<s>(sm); f = fl[i];
415  }
416  FreeList* n = f->next();
417  fl[i] = n;
418  return f;
419  }
420 
421  template<size_t s>
422  forceinline void
424  size_t i = sz2i(s);
425 #ifdef GECODE_AUDIT
426  FreeList* cur = f;
427  while (cur != l) {
428  assert(cur->next());
429  cur = cur->next();
430  }
431 #endif
432  l->next(fl[i]); fl[i] = f;
433  }
434 
435  template<size_t sz>
436  void
437  MemoryManager::fl_refill(SharedMemory& sm) {
438  // Try to acquire memory from slack
439  if (slack != NULL) {
440  MemoryChunk* m = slack;
441  slack = NULL;
442  do {
443  char* block = ptr_cast<char*>(m);
444  size_t s = m->size;
445  assert(s >= sz);
446  m = m->next;
447  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
448  while (s >= 2*sz) {
449  ptr_cast<FreeList*>(block)->next(ptr_cast<FreeList*>(block+sz));
450  block += sz;
451  s -= sz;
452  }
453  ptr_cast<FreeList*>(block)->next(NULL);
454  } while (m != NULL);
455  } else {
456  char* block = static_cast<char*>(alloc(sm,MemoryConfig::fl_refill*sz));
457  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
458  int i = MemoryConfig::fl_refill-2;
459  do {
460  ptr_cast<FreeList*>(block+i*sz)->next(ptr_cast<FreeList*>(block+(i+1)*sz));
461  } while (--i >= 0);
462  ptr_cast<FreeList*>(block+
463  (MemoryConfig::fl_refill-1)*sz)->next
464  (ptr_cast<FreeList*>(NULL));
465  }
466  }
467 
468 }}
469 
470 // STATISTICS: kernel-memory
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition: manager.hpp:253
FreeList * _next
Pointer to next freelist object.
Definition: manager.hpp:101
HeapChunk * hc
A list of cached heap chunks.
Definition: manager.hpp:67
const int hcsz_dec_ratio
Decrement ratio for chunk size.
Definition: config.hpp:77
MemoryManager(SharedMemory &sm)
Constructor initialization.
Definition: manager.hpp:335
void * alloc(SharedMemory &sm, size_t s)
Allocate memory of size s.
Definition: manager.hpp:285
void * fl_alloc(SharedMemory &sm)
Allocate free list element of size s.
Definition: manager.hpp:410
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition: manager.hpp:297
const int hcsz_inc_ratio
Increment ratio for chunk size.
Definition: config.hpp:67
Manage memory for space.
Definition: manager.hpp:120
NodeType t
Type of node.
Definition: bool-expr.cpp:230
const size_t hcsz_min
Minimal size of a heap chunk requested from the OS.
Definition: config.hpp:52
const int fl_size_min
Minimal size for free list element.
Definition: config.hpp:99
size_t size
Size of chunk.
Definition: manager.hpp:49
A lock as a scoped frontend for a mutex.
Definition: thread.hpp:191
void fl_dispose(FreeList *f, FreeList *l)
Release all free list elements of size s between f and l (inclusive)
Definition: manager.hpp:423
RegSimpleC rc
Gecode toplevel namespace
const unsigned int n_hc_cache
How many heap chunks should be cached at most.
Definition: config.hpp:47
void release(SharedMemory &sm)
Release all allocated heap chunks.
Definition: manager.hpp:362
Shared object for several memory areas.
Definition: manager.hpp:60
Memory chunk with size information.
Definition: manager.hpp:44
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:248
~SharedMemory(void)
Destructor.
Definition: manager.hpp:189
const size_t hcsz_max
Maximal size of a heap chunk requested from the OS.
Definition: config.hpp:60
const int fl_unit_size
Unit size for free lists.
Definition: config.hpp:90
void align(size_t &s, size_t a=GECODE_MEMORY_ALIGNMENT)
Align size s to the required alignment a.
Definition: config.hpp:144
const int fl_size_max
Maximal size for free list element.
Definition: config.hpp:108
void free(HeapChunk *hc)
Free heap chunk (or cache for later)
Definition: manager.hpp:220
double area[1]
Start of memory area inside chunk.
Definition: manager.hpp:56
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
Heap heap
The single global heap.
Definition: heap.cpp:44
Base-class for freelist-managed objects.
Definition: manager.hpp:98
Base * next(void) const
Return next test.
Definition: test.hpp:58
unsigned int n_hc
How many heap chunks are available for caching.
Definition: manager.hpp:65
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
SharedMemory(void)
Initialize.
Definition: manager.hpp:184
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
Definition: manager.hpp:378
FreeList(void)
Use uninitialized.
Definition: manager.hpp:241
MemoryChunk * next
Next chunk.
Definition: manager.hpp:47
#define forceinline
Definition: config.hpp:185
HeapChunk * alloc(size_t s, size_t l)
Return heap chunk, preferable of size s, but at least of size l.
Definition: manager.hpp:198
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
Gecode::IntArgs i({1, 2, 3, 4})
const int fl_refill
Number of free lists elements to allocate.
Definition: config.hpp:116
Memory chunk allocated from heap with proper alignment.
Definition: manager.hpp:53
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232