this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2008
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <cstddef>
35
36namespace Gecode {
37
38 /**
39 * \defgroup FuncMemRegion Region memory management
40 *
41 * A region provides a handle to temporary memory owned by
42 * a space. The memory will be managed in a stack fashion, that is,
43 * the memory allocated through a region will be released
44 * only after the region is deleted and all other regions
45 * created later also have been deleted.
46 *
47 * In case a memory request cannot be fulfilled from a space's region,
48 * heap memory is allocated and returned to the operating system
49 * as soon as the region is deleted.
50 *
51 * \ingroup FuncMem
52 */
53 //@{
54 /// Handle to region
55 class Region {
56 private:
57 /// Heap chunks used for regions
58 class Chunk : public HeapAllocated {
59 public:
60 /// Amount of free memory
61 size_t free;
62 /// The actual memory area (allocated from top to bottom)
63 alignas((alignof(std::max_align_t) > GECODE_MEMORY_ALIGNMENT) ?
64 alignof(std::max_align_t) : GECODE_MEMORY_ALIGNMENT)
65 double area[Kernel::MemoryConfig::region_area_size / sizeof(double)];
66 /// A pointer to another chunk
67 Chunk* next;
68 /// Return memory if available
69 bool alloc(size_t s, void*& p);
70 /// Free allocated memory (reset chunk)
71 void reset(void);
72 };
73 /// The heap chunk in use
74 Chunk* chunk;
75 /// A pool of heap chunks to be used for regions
76 class GECODE_KERNEL_EXPORT Pool {
77 protected:
78 /// The current chunk
79 Chunk* c;
80 /// Number of cached chunks
81 unsigned int n_c;
82 /// Mutex to synchronize globally shared access
83 Support::Mutex m;
84 public:
85 /// Initialize pool
86 Pool(void);
87 /// Get a new chunk
88 Chunk* chunk(void);
89 /// Return chunk and possible free unused chunk \a u
90 void chunk(Chunk* u);
91 /// Delete pool
92 ~Pool(void);
93 };
94 /// Just use a single static pool for heap chunks
95 GECODE_KERNEL_EXPORT static Pool& pool();
96 /// Heap information data structure
97 class HeapInfo {
98 public:
99 /// Number of allocated heap blocks
100 unsigned int n;
101 /// Limit of allocated heap blocks
102 unsigned int size;
103 /// Pointers to allocated heap blocks (more entries)
104 void* blocks[1];
105 };
106 /**
107 * \brief Heap allocation information
108 *
109 * If nullptr, no heap memory has been allocated. If the pointer
110 * is marked, it points to a single heap allocated block. Otherwise,
111 * it points to a HeapInfo data structure.
112 */
113 void* hi;
114 /// Allocate memory from heap
115 GECODE_KERNEL_EXPORT void* heap_alloc(size_t s);
116 /// Free memory previously allocated from heap
117 GECODE_KERNEL_EXPORT void heap_free(void);
118 public:
119 /// Initialize region
120 Region(void);
121 /**
122 * \brief Free allocate memory
123 *
124 * Note that in fact not all memory is freed, memory that has been
125 * allocated for large allocation requests will not be freed.
126 */
127 void free(void);
128 /// \name Typed allocation routines
129 //@{
130 /**
131 * \brief Allocate block of \a n objects of type \a T from region
132 *
133 * Note that this function implements C++ semantics: the default
134 * constructor of \a T is run for all \a n objects.
135 */
136 template<class T>
137 T* alloc(long unsigned int n);
138 /**
139 * \brief Allocate block of \a n objects of type \a T from region
140 *
141 * Note that this function implements C++ semantics: the default
142 * constructor of \a T is run for all \a n objects.
143 */
144 template<class T>
145 T* alloc(long int n);
146 /**
147 * \brief Allocate block of \a n objects of type \a T from region
148 *
149 * Note that this function implements C++ semantics: the default
150 * constructor of \a T is run for all \a n objects.
151 */
152 template<class T>
153 T* alloc(unsigned int n);
154 /**
155 * \brief Allocate block of \a n objects of type \a T from region
156 *
157 * Note that this function implements C++ semantics: the default
158 * constructor of \a T is run for all \a n objects.
159 */
160 template<class T>
161 T* alloc(int n);
162 /**
163 * \brief Delete \a n objects allocated from the region starting at \a b
164 *
165 * Note that this function implements C++ semantics: the destructor
166 * of \a T is run for all \a n objects.
167 *
168 * Note that the memory is not freed, the only effect is running the
169 * destructors.
170 */
171 template<class T>
172 void free(T* b, long unsigned int n);
173 /**
174 * \brief Delete \a n objects allocated from the region starting at \a b
175 *
176 * Note that this function implements C++ semantics: the destructor
177 * of \a T is run for all \a n objects.
178 *
179 * Note that the memory is not freed, the only effect is running the
180 * destructors.
181 */
182 template<class T>
183 void free(T* b, long int n);
184 /**
185 * \brief Delete \a n objects allocated from the region starting at \a b
186 *
187 * Note that this function implements C++ semantics: the destructor
188 * of \a T is run for all \a n objects.
189 *
190 * Note that the memory is not freed, the only effect is running the
191 * destructors.
192 */
193 template<class T>
194 void free(T* b, unsigned int n);
195 /**
196 * \brief Delete \a n objects allocated from the region starting at \a b
197 *
198 * Note that this function implements C++ semantics: the destructor
199 * of \a T is run for all \a n objects.
200 *
201 * Note that the memory is not freed, the only effect is running the
202 * destructors.
203 */
204 template<class T>
205 void free(T* b, int n);
206 /**
207 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the region
208 *
209 * Note that this function implements C++ semantics: the copy constructor
210 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
211 * constructor of \a T is run for all remaining
212 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
213 * run for all \a n objects in \a b.
214 *
215 * Returns the address of the new block.
216 */
217 template<class T>
218 T* realloc(T* b, long unsigned int n, long unsigned int m);
219 /**
220 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the region
221 *
222 * Note that this function implements C++ semantics: the copy constructor
223 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
224 * constructor of \a T is run for all remaining
225 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
226 * run for all \a n objects in \a b.
227 *
228 * Returns the address of the new block.
229 */
230 template<class T>
231 T* realloc(T* b, long int n, long int m);
232 /**
233 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the region
234 *
235 * Note that this function implements C++ semantics: the copy constructor
236 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
237 * constructor of \a T is run for all remaining
238 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
239 * run for all \a n objects in \a b.
240 *
241 * Returns the address of the new block.
242 */
243 template<class T>
244 T* realloc(T* b, unsigned int n, unsigned int m);
245 /**
246 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the region
247 *
248 * Note that this function implements C++ semantics: the copy constructor
249 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
250 * constructor of \a T is run for all remaining
251 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
252 * run for all \a n objects in \a b.
253 *
254 * Returns the address of the new block.
255 */
256 template<class T>
257 T* realloc(T* b, int n, int m);
258 //@}
259 /// \name Raw allocation routines
260 //@{
261 /// Allocate memory from region
262 void* ralloc(size_t s);
263 /**
264 * \brief Free memory previously allocated
265 *
266 * Note that the memory is only guaranteed to be freed after the
267 * region object itself gets deleted.
268 */
269 void rfree(void* p, size_t s);
270 //@}
271 /// \name Construction routines
272 //@{
273 /**
274 * \brief Constructs a single object of type \a T from region using the default constructor.
275 */
276 template<class T>
277 T& construct(void);
278 /**
279 * \brief Constructs a single object of type \a T from region using a unary constructor.
280 *
281 * The parameter is passed as a const reference.
282 */
283 template<class T, typename A1>
284 T& construct(A1 const& a1);
285 /**
286 * \brief Constructs a single object of type \a T from region using a binary constructor.
287 *
288 * The parameters are passed as const references.
289 */
290 template<class T, typename A1, typename A2>
291 T& construct(A1 const& a1, A2 const& a2);
292 /**
293 * \brief Constructs a single object of type \a T from region using a ternary constructor.
294 *
295 * The parameters are passed as const references.
296 */
297 template<class T, typename A1, typename A2, typename A3>
298 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
299 /**
300 * \brief Constructs a single object of type \a T from region using a quaternary constructor.
301 *
302 * The parameters are passed as const references.
303 */
304 template<class T, typename A1, typename A2, typename A3, typename A4>
305 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
306 /**
307 * \brief Constructs a single object of type \a T from region using a quinary constructor.
308 *
309 * The parameters are passed as const references.
310 */
311 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
312 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
313 //@}
314 /// Return memory
315 ~Region(void);
316
317 /// Allocate memory from heap (disabled)
318 static void* operator new(size_t s) = delete;
319 /// Free memory allocated from heap (disabled)
320 static void operator delete(void* p) = delete;
321 /// Copy constructor (disabled)
322 Region(const Region&) = delete;
323 /// Assignment operator (disabled)
324 const Region& operator =(const Region&) = delete;
325 };
326 //@}
327
328
329 /*
330 * Implementation
331 *
332 */
333 forceinline bool
334 Region::Chunk::alloc(size_t s, void*& p) {
335 Kernel::MemoryConfig::align
336 (s,((alignof(std::max_align_t) > GECODE_MEMORY_ALIGNMENT) ?
337 alignof(std::max_align_t) : GECODE_MEMORY_ALIGNMENT));
338 if (s > free)
339 return false;
340 free -= s;
341 p = ptr_cast<char*>(&area[0]) + free;
342 return true;
343 }
344
345 forceinline void
346 Region::Chunk::reset(void) {
347 free = Kernel::MemoryConfig::region_area_size;
348 }
349
350
351 forceinline
352 Region::Region(void)
353 : chunk(pool().chunk()), hi(nullptr) {}
354
355 forceinline void
356 Region::free(void) {
357 chunk->reset();
358 }
359
360 forceinline void*
361 Region::ralloc(size_t s) {
362 void* p;
363 if (chunk->alloc(s,p))
364 return p;
365 else
366 return heap_alloc(s);
367 }
368
369 forceinline void
370 Region::rfree(void*, size_t) {}
371
372 forceinline
373 Region::~Region(void) {
374 pool().chunk(chunk);
375 if (hi != nullptr)
376 heap_free();
377 }
378
379
380 /*
381 * Typed allocation routines
382 *
383 */
384 template<class T>
385 forceinline T*
386 Region::alloc(long unsigned int n) {
387 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
388 for (long unsigned int i=0U; i<n; i++)
389 (void) new (p+i) T();
390 return p;
391 }
392 template<class T>
393 forceinline T*
394 Region::alloc(long int n) {
395 assert(n >= 0);
396 return alloc<T>(static_cast<long unsigned int>(n));
397 }
398 template<class T>
399 forceinline T*
400 Region::alloc(unsigned int n) {
401 return alloc<T>(static_cast<long unsigned int>(n));
402 }
403 template<class T>
404 forceinline T*
405 Region::alloc(int n) {
406 assert(n >= 0);
407 return alloc<T>(static_cast<long unsigned int>(n));
408 }
409
410 template<class T>
411 forceinline void
412 Region::free(T* b, long unsigned int n) {
413 for (long unsigned int i=0U; i<n; i++)
414 b[i].~T();
415 rfree(b,n*sizeof(T));
416 }
417 template<class T>
418 forceinline void
419 Region::free(T* b, long int n) {
420 assert(n >= 0);
421 free<T>(b,static_cast<long unsigned int>(n));
422 }
423 template<class T>
424 forceinline void
425 Region::free(T* b, unsigned int n) {
426 free<T>(b,static_cast<long unsigned int>(n));
427 }
428 template<class T>
429 forceinline void
430 Region::free(T* b, int n) {
431 assert(n >= 0);
432 free<T>(b,static_cast<long unsigned int>(n));
433 }
434
435 template<class T>
436 forceinline T*
437 Region::realloc(T* b, long unsigned int n, long unsigned int m) {
438 if (n < m) {
439 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
440 for (long unsigned int i=0U; i<n; i++)
441 (void) new (p+i) T(b[i]);
442 for (long unsigned int i=n; i<m; i++)
443 (void) new (p+i) T();
444 free<T>(b,n);
445 return p;
446 } else {
447 free<T>(b+m,m-n);
448 return b;
449 }
450 }
451 template<class T>
452 forceinline T*
453 Region::realloc(T* b, long int n, long int m) {
454 assert((n >= 0) && (m >= 0));
455 return realloc<T>(b,static_cast<long unsigned int>(n),
456 static_cast<long unsigned int>(m));
457 }
458 template<class T>
459 forceinline T*
460 Region::realloc(T* b, unsigned int n, unsigned int m) {
461 return realloc<T>(b,static_cast<long unsigned int>(n),
462 static_cast<long unsigned int>(m));
463 }
464 template<class T>
465 forceinline T*
466 Region::realloc(T* b, int n, int m) {
467 assert((n >= 0) && (m >= 0));
468 return realloc<T>(b,static_cast<long unsigned int>(n),
469 static_cast<long unsigned int>(m));
470 }
471
472 /*
473 * Region construction support
474 *
475 */
476 template<class T>
477 forceinline T&
478 Region::construct(void) {
479 return alloc<T>(1);
480 }
481 template<class T, typename A1>
482 forceinline T&
483 Region::construct(A1 const& a1) {
484 T& t = *static_cast<T*>(ralloc(sizeof(T)));
485 new (&t) T(a1);
486 return t;
487 }
488 template<class T, typename A1, typename A2>
489 forceinline T&
490 Region::construct(A1 const& a1, A2 const& a2) {
491 T& t = *static_cast<T*>(ralloc(sizeof(T)));
492 new (&t) T(a1,a2);
493 return t;
494 }
495 template<class T, typename A1, typename A2, typename A3>
496 forceinline T&
497 Region::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
498 T& t = *static_cast<T*>(ralloc(sizeof(T)));
499 new (&t) T(a1,a2,a3);
500 return t;
501 }
502 template<class T, typename A1, typename A2, typename A3, typename A4>
503 forceinline T&
504 Region::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
505 T& t = *static_cast<T*>(ralloc(sizeof(T)));
506 new (&t) T(a1,a2,a3,a4);
507 return t;
508 }
509 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
510 forceinline T&
511 Region::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
512 T& t = *static_cast<T*>(ralloc(sizeof(T)));
513 new (&t) T(a1,a2,a3,a4,a5);
514 return t;
515 }
516
517}
518
519// STATISTICS: kernel-memory