Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
41namespace Gecode { namespace Kernel {
42
45 public:
49 size_t size;
50 };
51
53 class HeapChunk : public MemoryChunk {
54 public:
56 double area[1];
57 };
58
61 private:
63 struct {
65 unsigned int n_hc;
68 } heap;
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
88namespace Gecode {
89
98 class FreeList {
99 protected:
102 public:
104 FreeList(void);
108 FreeList* next(void) const;
110 FreeList** nextRef(void);
112 void next(FreeList* n);
113 };
114
115}
116
117namespace 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
176namespace 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
233namespace 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
264namespace 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);
459 do {
460 ptr_cast<FreeList*>(block+i*sz)->next(ptr_cast<FreeList*>(block+(i+1)*sz));
461 } while (--i >= 0);
463 (MemoryConfig::fl_refill-1)*sz)->next
464 (ptr_cast<FreeList*>(NULL));
465 }
466 }
467
468}}
469
470// STATISTICS: kernel-memory
NNF * l
Left subtree.
NodeType t
Type of node.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for freelist-managed objects.
Definition manager.hpp:98
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition manager.hpp:253
FreeList(void)
Use uninitialized.
Definition manager.hpp:241
FreeList * next(void) const
Return next freelist object.
Definition manager.hpp:248
FreeList * _next
Pointer to next freelist object.
Definition manager.hpp:101
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
Memory chunk allocated from heap with proper alignment.
Definition manager.hpp:53
double area[1]
Start of memory area inside chunk.
Definition manager.hpp:56
Memory chunk with size information.
Definition manager.hpp:44
size_t size
Size of chunk.
Definition manager.hpp:49
MemoryChunk * next
Next chunk.
Definition manager.hpp:47
Manage memory for space.
Definition manager.hpp:120
void * fl_alloc(SharedMemory &sm)
Allocate free list element of size s.
Definition manager.hpp:410
void release(SharedMemory &sm)
Release all allocated heap chunks.
Definition manager.hpp:362
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
Definition manager.hpp:378
void * alloc(SharedMemory &sm, size_t s)
Allocate memory of size s.
Definition manager.hpp:285
MemoryManager(SharedMemory &sm)
Constructor initialization.
Definition manager.hpp:335
void fl_dispose(FreeList *f, FreeList *l)
Release all free list elements of size s between f and l (inclusive)
Definition manager.hpp:423
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition manager.hpp:297
Shared object for several memory areas.
Definition manager.hpp:60
SharedMemory(void)
Initialize.
Definition manager.hpp:184
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
HeapChunk * hc
A list of cached heap chunks.
Definition manager.hpp:67
void free(HeapChunk *hc)
Free heap chunk (or cache for later)
Definition manager.hpp:220
unsigned int n_hc
How many heap chunks are available for caching.
Definition manager.hpp:65
~SharedMemory(void)
Destructor.
Definition manager.hpp:189
A lock as a scoped frontend for a mutex.
Definition thread.hpp:191
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Base * next(void) const
Return next test.
Definition test.hpp:58
Heap heap
The single global heap.
Definition heap.cpp:44
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
const int hcsz_inc_ratio
Increment ratio for chunk size.
Definition config.hpp:67
const size_t hcsz_max
Maximal size of a heap chunk requested from the OS.
Definition config.hpp:60
const int fl_size_max
Maximal size for free list element.
Definition config.hpp:108
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_unit_size
Unit size for free lists.
Definition config.hpp:90
const unsigned int n_hc_cache
How many heap chunks should be cached at most.
Definition config.hpp:47
const size_t hcsz_min
Minimal size of a heap chunk requested from the OS.
Definition config.hpp:52
const int fl_refill
Number of free lists elements to allocate.
Definition config.hpp:116
const int fl_size_min
Minimal size for free list element.
Definition config.hpp:99
const int hcsz_dec_ratio
Decrement ratio for chunk size.
Definition config.hpp:77
Gecode toplevel namespace
T ptr_cast(void *p)
Cast p into pointer of type T.
Definition cast.hpp:42
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition config.hpp:187