Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
17  * $Date$ by $Author$
18  * $Revision$
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 { namespace Kernel {
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 
64  class SharedMemory {
65  private:
67  struct {
69  unsigned int n_hc;
72  } heap;
74  GECODE_KERNEL_EXPORT static Support::Mutex& m(void);
75  public:
77  SharedMemory(void);
79  ~SharedMemory(void);
81  //@
83  HeapChunk* alloc(size_t s, size_t l);
85  void free(HeapChunk* hc);
87  };
88 
89 
90 }}
91 
92 namespace Gecode {
93 
102  class FreeList {
103  protected:
106  public:
108  FreeList(void);
110  FreeList(FreeList* n);
112  FreeList* next(void) const;
114  FreeList** nextRef(void);
116  void next(FreeList* n);
117  };
118 
119 }
120 
121 namespace Gecode { namespace Kernel {
122 
125  public:
129  MemoryManager(SharedMemory& sm, MemoryManager& mm, size_t s_sub);
131  void release(SharedMemory& sm);
132 
133  private:
134  size_t cur_hcsz;
135  HeapChunk* cur_hc;
136  size_t requested;
137 
138  char* start;
139  size_t lsz;
140 
143  void alloc_refill(SharedMemory& sm, size_t s);
145  void alloc_fill(SharedMemory& sm, size_t s, bool first);
146 
147  public:
149  void* alloc(SharedMemory& sm, size_t s);
151  void* subscriptions(void) const;
152 
153  private:
157  template<size_t> void fl_refill(SharedMemory& sm);
159  static size_t sz2i(size_t);
161  static size_t i2sz(size_t);
162 
163  public:
165  template<size_t s>
166  void* fl_alloc(SharedMemory& sm);
168  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
169 
170  private:
172  MemoryChunk* slack;
173  public:
175  void reuse(void* p, size_t s);
176  };
177 
178 }}
179 
180 namespace Gecode { namespace Kernel {
181 
182  /*
183  * Shared memory area
184  *
185  */
186 
189  heap.n_hc = 0;
190  heap.hc = NULL;
191  }
194  while (heap.hc != NULL) {
195  HeapChunk* hc = heap.hc;
196  heap.hc = static_cast<HeapChunk*>(hc->next);
197  Gecode::heap.rfree(hc);
198  }
199  }
200 
202  SharedMemory::alloc(size_t s, size_t l) {
203  m().acquire();
204  while ((heap.hc != NULL) && (heap.hc->size < l)) {
205  heap.n_hc--;
206  HeapChunk* hc = heap.hc;
207  heap.hc = static_cast<HeapChunk*>(hc->next);
208  Gecode::heap.rfree(hc);
209  }
210  HeapChunk* hc;
211  if (heap.hc == NULL) {
212  assert(heap.n_hc == 0);
213  hc = static_cast<HeapChunk*>(Gecode::heap.ralloc(s));
214  hc->size = s;
215  } else {
216  heap.n_hc--;
217  hc = heap.hc;
218  heap.hc = static_cast<HeapChunk*>(hc->next);
219  }
220  m().release();
221  return hc;
222  }
223  forceinline void
225  m().acquire();
226  if (heap.n_hc == MemoryConfig::n_hc_cache) {
227  Gecode::heap.rfree(hc);
228  } else {
229  heap.n_hc++;
230  hc->next = heap.hc; heap.hc = hc;
231  }
232  m().release();
233  }
234 
235 
236 }}
237 
238 namespace Gecode {
239 
240  /*
241  * Freelists
242  *
243  */
244 
247 
250  : _next(n) {}
251 
253  FreeList::next(void) const {
254  return _next;
255  }
256 
259  return &_next;
260  }
261 
262  forceinline void
264  _next = n;
265  }
266 
267 }
268 
269 namespace Gecode { namespace Kernel {
270 
271  /*
272  * The active memory manager
273  *
274  */
275 
276  forceinline size_t
277  MemoryManager::sz2i(size_t s) {
281  }
282 
283  forceinline size_t
284  MemoryManager::i2sz(size_t i) {
286  }
287 
288 
289  forceinline void*
290  MemoryManager::alloc(SharedMemory& sm, size_t sz) {
291  assert(sz > 0);
292  // Perform alignment
294  // Check whether sufficient memory left
295  if (sz > lsz)
296  alloc_refill(sm,sz);
297  lsz -= sz;
298  return start + lsz;
299  }
300 
301  forceinline void*
302  MemoryManager::subscriptions(void) const {
303  return &cur_hc->area[0];
304  }
305 
306  forceinline void
307  MemoryManager::alloc_fill(SharedMemory& sm, size_t sz, bool first) {
308  // Adjust current heap chunk size
309  if (((requested > MemoryConfig::hcsz_inc_ratio*cur_hcsz) ||
310  (sz > cur_hcsz)) &&
311  (cur_hcsz < MemoryConfig::hcsz_max) &&
312  !first) {
313  cur_hcsz <<= 1;
314  }
315  // Increment the size that it caters for the initial overhead
316  size_t overhead = sizeof(HeapChunk) - sizeof(double);
317  sz += overhead;
318  // Round size to next multiple of current heap chunk size
319  size_t allocate = ((sz > cur_hcsz) ?
320  (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
321  // Request a chunk of preferably size allocate, but at least size sz
322  HeapChunk* hc = sm.alloc(allocate,sz);
323  start = ptr_cast<char*>(&hc->area[0]);
324  lsz = hc->size - overhead;
325  // Link heap chunk, where the first heap chunk is kept in place
326  if (first) {
327  requested = hc->size;
328  hc->next = NULL; cur_hc = hc;
329  } else {
330  requested += hc->size;
331  hc->next = cur_hc->next; cur_hc->next = hc;
332  }
333 #ifdef GECODE_MEMORY_CHECK
334  for (char* c = start; c < (start+lsz); c++)
335  *c = 0;
336 #endif
337  }
338 
340  MemoryManager::MemoryManager(SharedMemory& sm)
341  : cur_hcsz(MemoryConfig::hcsz_min), requested(0), slack(NULL) {
342  alloc_fill(sm,cur_hcsz,true);
344  i--; )
345  fl[i] = NULL;
346  }
347 
350  size_t s_sub)
351  : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
352  MemoryConfig::align(s_sub);
353  if ((mm.requested < MemoryConfig::hcsz_dec_ratio*mm.cur_hcsz) &&
354  (cur_hcsz > MemoryConfig::hcsz_min) &&
355  (s_sub*2 < cur_hcsz))
356  cur_hcsz >>= 1;
357  alloc_fill(sm,cur_hcsz+s_sub,true);
358  // Skip the memory area at the beginning for subscriptions
359  lsz -= s_sub;
360  start += s_sub;
362  i--; )
363  fl[i] = NULL;
364  }
365 
366  forceinline void
368  // Release all allocated heap chunks
369  HeapChunk* hc = cur_hc;
370  do {
371  HeapChunk* t = hc; hc = static_cast<HeapChunk*>(hc->next);
372  sm.free(t);
373  } while (hc != NULL);
374  }
375 
376 
377 
378  /*
379  * Slack memory management
380  *
381  */
382  forceinline void
383  MemoryManager::reuse(void* p, size_t s) {
384 #ifdef GECODE_MEMORY_CHECK
385  {
386  char* c = static_cast<char*>(p);
387  char* e = c + s;
388  while (c < e) {
389  *c = 0; c++;
390  }
391  }
392 #endif
394  return;
396  MemoryChunk* rc = static_cast<MemoryChunk*>(p);
397  rc->next = slack;
398  rc->size = s;
399  slack = rc;
400  } else {
401  size_t i = sz2i(s);
402  FreeList* f = static_cast<FreeList*>(p);
403  f->next(fl[i]); fl[i]=f;
404  }
405  }
406 
407 
408  /*
409  * Freelist management
410  *
411  */
412 
413  template<size_t s>
414  forceinline void*
416  size_t i = sz2i(s);
417  FreeList* f = fl[i];
418  if (f == NULL) {
419  fl_refill<s>(sm); f = fl[i];
420  }
421  FreeList* n = f->next();
422  fl[i] = n;
423  return f;
424  }
425 
426  template<size_t s>
427  forceinline void
429  size_t i = sz2i(s);
430 #ifdef GECODE_AUDIT
431  FreeList* cur = f;
432  while (cur != l) {
433  assert(cur->next());
434  cur = cur->next();
435  }
436 #endif
437  l->next(fl[i]); fl[i] = f;
438  }
439 
440  template<size_t sz>
441  void
442  MemoryManager::fl_refill(SharedMemory& sm) {
443  // Try to acquire memory from slack
444  if (slack != NULL) {
445  MemoryChunk* m = slack;
446  slack = NULL;
447  do {
448  char* block = ptr_cast<char*>(m);
449  size_t s = m->size;
450  assert(s >= sz);
451  m = m->next;
452  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
453  while (s >= 2*sz) {
454  ptr_cast<FreeList*>(block)->next(ptr_cast<FreeList*>(block+sz));
455  block += sz;
456  s -= sz;
457  }
458  ptr_cast<FreeList*>(block)->next(NULL);
459  } while (m != NULL);
460  } else {
461  char* block = static_cast<char*>(alloc(sm,MemoryConfig::fl_refill*sz));
462  fl[sz2i(sz)] = ptr_cast<FreeList*>(block);
463  int i = MemoryConfig::fl_refill-2;
464  do {
465  ptr_cast<FreeList*>(block+i*sz)->next(ptr_cast<FreeList*>(block+(i+1)*sz));
466  } while (--i >= 0);
467  ptr_cast<FreeList*>(block+
469  (ptr_cast<FreeList*>(NULL));
470  }
471  }
472 
473 }}
474 
475 // STATISTICS: kernel-memory
NodeType t
Type of node.
Definition: bool-expr.cpp:234
const size_t hcsz_min
Minimal size of a heap chunk requested from the OS.
Definition: config.hpp:56
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
Definition: manager.hpp:383
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:253
void align(size_t &s)
Align size s to the required alignment.
Definition: config.hpp:148
void * alloc(SharedMemory &sm, size_t s)
Allocate memory of size s.
Definition: manager.hpp:290
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:361
void fl_dispose(FreeList *f, FreeList *l)
Release all free list elements of size s between f and l (inclusive)
Definition: manager.hpp:428
Memory chunk allocated from heap with proper alignment.
Definition: manager.hpp:57
Manage memory for space.
Definition: manager.hpp:124
#define forceinline
Definition: config.hpp:182
FreeList(void)
Use uninitialized.
Definition: manager.hpp:246
void free(HeapChunk *hc)
Free heap chunk (or cache for later)
Definition: manager.hpp:224
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:105
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
const int fl_size_min
Minimal size for free list element.
Definition: config.hpp:103
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition: manager.hpp:258
MemoryChunk * next
Next chunk.
Definition: manager.hpp:51
unsigned int n_hc
How many heap chunks are available for caching.
Definition: manager.hpp:69
HeapChunk * alloc(size_t s, size_t l)
Return heap chunk, preferable of size s, but at least of size l.
Definition: manager.hpp:202
FreeList * _next
Pointer to next freelist object.
Definition: manager.hpp:105
~SharedMemory(void)
Destructor.
Definition: manager.hpp:193
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:74
const int fl_size_max
Maximal size for free list element.
Definition: config.hpp:112
SharedMemory(void)
Initialize.
Definition: manager.hpp:188
T ptr_cast(void *p)
Cast p into pointer of type T.
Definition: cast.hpp:46
double area[1]
Start of memory area inside chunk.
Definition: manager.hpp:60
const int hcsz_dec_ratio
Decrement ratio for chunk size.
Definition: config.hpp:81
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:64
const int fl_unit_size
Unit size for free lists.
Definition: config.hpp:94
Heap heap
The single global heap.
Definition: heap.cpp:48
Memory chunk with size information.
Definition: manager.hpp:48
Base-class for freelist-managed objects.
Definition: manager.hpp:102
void * fl_alloc(SharedMemory &sm)
Allocate free list element of size s.
Definition: manager.hpp:415
const unsigned int n_hc_cache
How many heap chunks should be cached at most.
Definition: config.hpp:51
size_t size
Size of chunk.
Definition: manager.hpp:53
void release(SharedMemory &sm)
Release all allocated heap chunks.
Definition: manager.hpp:367
Gecode toplevel namespace
MemoryManager(SharedMemory &sm)
Constructor initialization.
Definition: manager.hpp:340
HeapChunk * hc
A list of cached heap chunks.
Definition: manager.hpp:71
Shared object for several memory areas.
Definition: manager.hpp:64
const int hcsz_inc_ratio
Increment ratio for chunk size.
Definition: config.hpp:71
const int fl_refill
Number of free lists elements to allocate.
Definition: config.hpp:120