Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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);
193  Gecode::heap.rfree(hc);
194  }
195  }
196 
198  SharedMemory::alloc(size_t s, size_t l) {
199  m().acquire();
200  while ((heap.hc != NULL) && (heap.hc->size < l)) {
201  heap.n_hc--;
202  HeapChunk* hc = heap.hc;
203  heap.hc = static_cast<HeapChunk*>(hc->next);
204  Gecode::heap.rfree(hc);
205  }
206  HeapChunk* hc;
207  if (heap.hc == NULL) {
208  assert(heap.n_hc == 0);
209  hc = static_cast<HeapChunk*>(Gecode::heap.ralloc(s));
210  hc->size = s;
211  } else {
212  heap.n_hc--;
213  hc = heap.hc;
214  heap.hc = static_cast<HeapChunk*>(hc->next);
215  }
216  m().release();
217  return hc;
218  }
219  forceinline void
221  m().acquire();
222  if (heap.n_hc == MemoryConfig::n_hc_cache) {
223  Gecode::heap.rfree(hc);
224  } else {
225  heap.n_hc++;
226  hc->next = heap.hc; heap.hc = hc;
227  }
228  m().release();
229  }
230 
231 
232 }}
233 
234 namespace Gecode {
235 
236  /*
237  * Freelists
238  *
239  */
240 
243 
246  : _next(n) {}
247 
249  FreeList::next(void) const {
250  return _next;
251  }
252 
255  return &_next;
256  }
257 
258  forceinline void
260  _next = n;
261  }
262 
263 }
264 
265 namespace Gecode { namespace Kernel {
266 
267  /*
268  * The active memory manager
269  *
270  */
271 
272  forceinline size_t
273  MemoryManager::sz2i(size_t s) {
277  }
278 
279  forceinline size_t
280  MemoryManager::i2sz(size_t i) {
282  }
283 
284 
285  forceinline void*
286  MemoryManager::alloc(SharedMemory& sm, size_t sz) {
287  assert(sz > 0);
288  // Perform alignment
290  // Check whether sufficient memory left
291  if (sz > lsz)
292  alloc_refill(sm,sz);
293  lsz -= sz;
294  return start + lsz;
295  }
296 
297  forceinline void*
298  MemoryManager::subscriptions(void) const {
299  return &cur_hc->area[0];
300  }
301 
302  forceinline void
303  MemoryManager::alloc_fill(SharedMemory& sm, size_t sz, bool first) {
304  // Adjust current heap chunk size
305  if (((requested > MemoryConfig::hcsz_inc_ratio*cur_hcsz) ||
306  (sz > cur_hcsz)) &&
307  (cur_hcsz < MemoryConfig::hcsz_max) &&
308  !first) {
309  cur_hcsz <<= 1;
310  }
311  // Increment the size that it caters for the initial overhead
312  size_t overhead = sizeof(HeapChunk) - sizeof(double);
313  sz += overhead;
314  // Round size to next multiple of current heap chunk size
315  size_t allocate = ((sz > cur_hcsz) ?
316  (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
317  // Request a chunk of preferably size allocate, but at least size sz
318  HeapChunk* hc = sm.alloc(allocate,sz);
319  start = ptr_cast<char*>(&hc->area[0]);
320  lsz = hc->size - overhead;
321  // Link heap chunk, where the first heap chunk is kept in place
322  if (first) {
323  requested = hc->size;
324  hc->next = NULL; cur_hc = hc;
325  } else {
326  requested += hc->size;
327  hc->next = cur_hc->next; cur_hc->next = hc;
328  }
329 #ifdef GECODE_MEMORY_CHECK
330  for (char* c = start; c < (start+lsz); c++)
331  *c = 0;
332 #endif
333  }
334 
336  MemoryManager::MemoryManager(SharedMemory& sm)
337  : cur_hcsz(MemoryConfig::hcsz_min), requested(0), slack(NULL) {
338  alloc_fill(sm,cur_hcsz,true);
340  i++)
341  fl[i] = NULL;
342  }
343 
346  size_t s_sub)
347  : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
348  MemoryConfig::align(s_sub);
349  if ((mm.requested < MemoryConfig::hcsz_dec_ratio*mm.cur_hcsz) &&
350  (cur_hcsz > MemoryConfig::hcsz_min) &&
351  (s_sub*2 < cur_hcsz))
352  cur_hcsz >>= 1;
353  alloc_fill(sm,cur_hcsz+s_sub,true);
354  // Skip the memory area at the beginning for subscriptions
355  lsz -= s_sub;
356  start += s_sub;
358  i++)
359  fl[i] = NULL;
360  }
361 
362  forceinline void
364  // Release all allocated heap chunks
365  HeapChunk* hc = cur_hc;
366  do {
367  HeapChunk* t = hc; hc = static_cast<HeapChunk*>(hc->next);
368  sm.free(t);
369  } while (hc != NULL);
370  }
371 
372 
373 
374  /*
375  * Slack memory management
376  *
377  */
378  forceinline void
379  MemoryManager::reuse(void* p, size_t s) {
380 #ifdef GECODE_MEMORY_CHECK
381  {
382  char* c = static_cast<char*>(p);
383  char* e = c + s;
384  while (c < e) {
385  *c = 0; c++;
386  }
387  }
388 #endif
390  return;
392  MemoryChunk* rc = static_cast<MemoryChunk*>(p);
393  rc->next = slack;
394  rc->size = s;
395  slack = rc;
396  } else {
397  size_t i = sz2i(s);
398  FreeList* f = static_cast<FreeList*>(p);
399  f->next(fl[i]); fl[i]=f;
400  }
401  }
402 
403 
404  /*
405  * Freelist management
406  *
407  */
408 
409  template<size_t s>
410  forceinline void*
412  size_t i = sz2i(s);
413  FreeList* f = fl[i];
414  if (f == NULL) {
415  fl_refill<s>(sm); f = fl[i];
416  }
417  FreeList* n = f->next();
418  fl[i] = n;
419  return f;
420  }
421 
422  template<size_t s>
423  forceinline void
425  size_t i = sz2i(s);
426 #ifdef GECODE_AUDIT
427  FreeList* cur = f;
428  while (cur != l) {
429  assert(cur->next());
430  cur = cur->next();
431  }
432 #endif
433  l->next(fl[i]); fl[i] = f;
434  }
435 
436  template<size_t sz>
437  void
438  MemoryManager::fl_refill(SharedMemory& sm) {
439  // Try to acquire memory from slack
440  if (slack != NULL) {
441  MemoryChunk* m = slack;
442  slack = NULL;
443  do {
444  char* block = ptr_cast<char*>(m);
445  size_t s = m->size;
446  assert(s >= sz);
447  m = m->next;
448  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
449  while (s >= 2*sz) {
450  ptr_cast<FreeList*>(block)->next(ptr_cast<FreeList*>(block+sz));
451  block += sz;
452  s -= sz;
453  }
454  ptr_cast<FreeList*>(block)->next(NULL);
455  } while (m != NULL);
456  } else {
457  char* block = static_cast<char*>(alloc(sm,MemoryConfig::fl_refill*sz));
458  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
459  int i = MemoryConfig::fl_refill-2;
460  do {
461  ptr_cast<FreeList*>(block+i*sz)->next(ptr_cast<FreeList*>(block+(i+1)*sz));
462  } while (--i >= 0);
463  ptr_cast<FreeList*>(block+
465  (ptr_cast<FreeList*>(NULL));
466  }
467  }
468 
469 }}
470 
471 // STATISTICS: kernel-memory
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
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
Definition: manager.hpp:379
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:249
void * alloc(SharedMemory &sm, size_t s)
Allocate memory of size s.
Definition: manager.hpp:286
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:357
void fl_dispose(FreeList *f, FreeList *l)
Release all free list elements of size s between f and l (inclusive)
Definition: manager.hpp:424
Memory chunk allocated from heap with proper alignment.
Definition: manager.hpp:53
Manage memory for space.
Definition: manager.hpp:120
#define forceinline
Definition: config.hpp:185
FreeList(void)
Use uninitialized.
Definition: manager.hpp:242
void free(HeapChunk *hc)
Free heap chunk (or cache for later)
Definition: manager.hpp:220
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
const int fl_size_min
Minimal size for free list element.
Definition: config.hpp:99
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition: manager.hpp:254
MemoryChunk * next
Next chunk.
Definition: manager.hpp:47
unsigned int n_hc
How many heap chunks are available for caching.
Definition: manager.hpp:65
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
FreeList * _next
Pointer to next freelist object.
Definition: manager.hpp:101
~SharedMemory(void)
Destructor.
Definition: manager.hpp:189
void align(size_t &s, size_t a=GECODE_MEMORY_ALIGNMENT)
Align size s to the required alignment a.
Definition: config.hpp:144
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
const int fl_size_max
Maximal size for free list element.
Definition: config.hpp:108
SharedMemory(void)
Initialize.
Definition: manager.hpp:184
T ptr_cast(void *p)
Cast p into pointer of type T.
Definition: cast.hpp:42
double area[1]
Start of memory area inside chunk.
Definition: manager.hpp:56
const int hcsz_dec_ratio
Decrement ratio for chunk size.
Definition: config.hpp:77
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
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
Heap heap
The single global heap.
Definition: heap.cpp:44
Memory chunk with size information.
Definition: manager.hpp:44
Base-class for freelist-managed objects.
Definition: manager.hpp:98
void * fl_alloc(SharedMemory &sm)
Allocate free list element of size s.
Definition: manager.hpp:411
const unsigned int n_hc_cache
How many heap chunks should be cached at most.
Definition: config.hpp:47
size_t size
Size of chunk.
Definition: manager.hpp:49
void release(SharedMemory &sm)
Release all allocated heap chunks.
Definition: manager.hpp:363
Gecode toplevel namespace
MemoryManager(SharedMemory &sm)
Constructor initialization.
Definition: manager.hpp:336
HeapChunk * hc
A list of cached heap chunks.
Definition: manager.hpp:67
Shared object for several memory areas.
Definition: manager.hpp:60
const int hcsz_inc_ratio
Increment ratio for chunk size.
Definition: config.hpp:67
const int fl_refill
Number of free lists elements to allocate.
Definition: config.hpp:116