Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pool.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/mem/pool.hpp
3  *
4  * A simple memory allocation manager and object allocator. The main reason for
5  * this allocation Pool is to keep memory for allocation of I/O data structures
6  * once the main malloc() memory pool runs out. The allocator itself may not be
7  * as faster as possible.
8  *
9  * Part of Project Thrill - http://project-thrill.org
10  *
11  * Copyright (C) 2016-2017 Timo Bingmann <[email protected]>
12  *
13  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
14  ******************************************************************************/
15 
16 #pragma once
17 #ifndef THRILL_MEM_POOL_HEADER
18 #define THRILL_MEM_POOL_HEADER
19 
20 #include <thrill/common/config.hpp>
22 
23 #include <algorithm>
24 #include <cstddef>
25 #include <cstdint>
26 #include <memory>
27 #include <mutex>
28 #include <string>
29 #include <type_traits>
30 #include <utility>
31 #include <vector>
32 
33 namespace thrill {
34 namespace mem {
35 
36 /******************************************************************************/
37 // Pool - a simple memory allocation manager
38 
39 /*!
40  * A simple memory allocation manager. The Pool gets chunks of memory of size
41  * ArenaSize from new/delete and delivers smaller byte areas to PoolAllocator.
42  *
43  * The main reason for this allocation Pool is to keep memory for allocation of
44  * I/O data structures once the main malloc() memory pool runs out. The
45  * allocator itself may not be as faster as possible.
46  *
47  * An Arena is organized as a singly-linked list of continuous free areas, where
48  * the free information is stored inside the free memory as a Slot. A Slot is
49  * exactly 8 bytes (containing only two uint32_t). All allocations are rounded
50  * up to a multiple of 8.
51  *
52  * +--+-----------+------+---------------+-----------+-------------------------+
53  * |XX| head_slot | used | free slot ... | used .... | free slot ....... |
54  * +--+-----------+------+---------------+-----------+-------------------------+
55  * | ^ | ^
56  * +------------------+ +------------------------+ (next indexes)
57  *
58  * - XX = additional Header information
59  *
60  * - head_slot = sentinel Slot containing .size as the free slots, and .next to
61  * the first free slot.
62  *
63  * - each free Slot contains .size and .next. Size is the amount of free slots
64  * in a free area. Next is the integer offset of the following free slot
65  * (information) or the end of the Arena.
66  *
67  * During allocation the next fitting free slot is searched for. During
68  * deallocation multiple free areas may be consolidated.
69  *
70  * For faster allocation, Arenas are categorized into many bins. Bin k always
71  * contains all Arenas with log_2(k) to log_2(k+1)-1 free space in them. On
72  * allocation and deallocation, the Arenas are moved between bins.
73  */
74 class Pool
75 {
76  static constexpr bool debug = false;
77  static constexpr bool debug_verify = false;
78  //! debug flag to check pairing of allocate()/deallocate() client calls
79  static constexpr bool debug_check_pairing = false;
80  static constexpr size_t check_limit = 4 * 1024 * 1024;
81 
82 public:
83  //! construct with base allocator
84  explicit Pool(size_t default_arena_size = 16384) noexcept;
85 
86  //! non-copyable: delete copy-constructor
87  Pool(const Pool&) = delete;
88  //! non-copyable: delete assignment operator
89  Pool& operator = (const Pool&) = delete;
90 
91  //! dtor
92  ~Pool() noexcept;
93 
94  //! allocate a continuous segment of n bytes in the arenas
95  void * allocate(size_t bytes);
96 
97  //! Deallocate a continuous segment of n bytes in the arenas, the size n
98  //! *MUST* match the allocation.
99  void deallocate(void* ptr, size_t bytes);
100 
101  //! Allocate and construct a single item of given Type using memory from the
102  //! Pool.
103  template <typename Type, typename... Args>
104  Type * make(Args&& ... args) {
105  Type* t = reinterpret_cast<Type*>(allocate(sizeof(Type)));
106  ::new (t)Type(std::forward<Args>(args) ...);
107  return t;
108  }
109 
110  //! Destroy and deallocate a single item of given Type.
111  template <typename Type>
112  void destroy(Type* t) {
113  t->~Type();
114  deallocate(t, sizeof(Type));
115  }
116 
117  //! Print out structure of the arenas.
118  void print(bool debug = true);
119 
120  //! Print out structure of the arenas.
121  void self_verify();
122 
123  //! maximum size possible to allocate
124  size_t max_size() const noexcept;
125 
126  //! deallocate all Arenas
127  void DeallocateAll();
128 
129 private:
130  //! struct in a Slot, which contains free information
131  struct Slot;
132 
133  //! header of an Arena, used to calculate number of slots
134  struct Arena;
135 
136  //! header of an ObjectArena containing equally sized items
137  struct ObjectArena;
138 
139  //! pool of equally sized items
140  class ObjectPool;
141 
142  //! mutex to protect data structures (remove this if you use it in another
143  //! context than Thrill).
144  std::mutex mutex_;
145 
146  //! number of bins
147  static const size_t num_bins
148  = /* log_2(16384) = */ 14 - /* log_2(sizeof(Slot)) */ 3 + 1;
149 
150  //! pointer to first arena in each bin, arenas are in allocation order, the
151  //! last bin is for overflow allocations.
152  Arena* arena_bin_[num_bins + 1];
153 
154  //! number of free slots in all arenas
155  size_t free_ = 0;
156  //! overall number of used slots
157  size_t size_ = 0;
158 
159  //! size of default Arena allocation
161 
162  //! minimum amount of spare memory to keep in the Pool.
163  size_t min_free_ = 1024 * 1024 / 8;
164 
165  //! object areas for small fixed size items
166  ObjectPool* object_32_;
167  ObjectPool* object_64_;
168  ObjectPool* object_128_;
169  ObjectPool* object_256_;
170 
171  //! array of allocations for checking
172  std::vector<std::pair<void*, size_t> > allocs_;
173 
174  //! calculate maximum bytes fitting into an Arena with given size.
175  size_t bytes_per_arena(size_t arena_size);
176 
177  //! allocate a new Arena blob
178  Arena * AllocateFreeArena(size_t arena_size, bool die_on_failure = true);
179 
180  //! find free area inside an Arena
181  void * ArenaFindFree(Arena* curr_arena, size_t bin, size_t n, size_t bytes);
182 
183  //! deallocate all Arenas
184  void IntDeallocateAll();
185 };
186 
187 //! singleton instance of global pool for I/O data structures
188 Pool& GPool();
189 
190 /******************************************************************************/
191 // PoolAllocator - an allocator to draw objects from a Pool.
192 
193 template <typename Type>
194 class PoolAllocator : public tlx::AllocatorBase<Type>
195 {
196 public:
197  using value_type = Type;
198  using pointer = Type *;
199  using const_pointer = const Type *;
200  using reference = Type &;
201  using const_reference = const Type &;
202  using size_type = std::size_t;
203  using difference_type = std::ptrdiff_t;
204 
205  //! C++11 type flag
206  using is_always_equal = std::false_type;
207 
208  //! Return allocator for different type.
209  template <typename U>
210  struct rebind { using other = PoolAllocator<U>; };
211 
212  //! construct PoolAllocator with Pool object
213  explicit PoolAllocator(Pool& pool) noexcept
214  : pool_(&pool) { }
215 
216  //! copy-constructor
217  PoolAllocator(const PoolAllocator&) noexcept = default;
218 
219  //! copy-constructor from a rebound allocator
220  template <typename OtherType>
221  PoolAllocator(const PoolAllocator<OtherType>& other) noexcept
222  : pool_(other.pool_) { }
223 
224  //! copy-assignment operator
225  PoolAllocator& operator = (const PoolAllocator&) noexcept = default;
226 
227  //! maximum size possible to allocate
228  size_type max_size() const noexcept {
229  return pool_->max_size();
230  }
231 
232  //! attempts to allocate a block of storage with a size large enough to
233  //! contain n elements of member type value_type, and returns a pointer to
234  //! the first element.
235  pointer allocate(size_type n, const void* /* hint */ = nullptr) {
236  return static_cast<Type*>(pool_->allocate(n * sizeof(Type)));
237  }
238 
239  //! releases a block of storage previously allocated with member allocate
240  //! and not yet released.
241  void deallocate(pointer p, size_type n) const noexcept {
242  pool_->deallocate(p, n * sizeof(Type));
243  }
244 
245  //! pointer to common Pool object. if we use a reference here, then the
246  //! allocator cannot be default move/assigned anymore.
248 
249  //! compare to another allocator of same type
250  template <typename Other>
251  bool operator == (const PoolAllocator<Other>& other) const noexcept {
252  return (pool_ == other.pool_);
253  }
254 
255  //! compare to another allocator of same type
256  template <typename Other>
257  bool operator != (const PoolAllocator<Other>& other) const noexcept {
258  return (pool_ != other.pool_);
259  }
260 };
261 
262 /******************************************************************************/
263 // FixedPoolAllocator - an allocator to draw objects from a fixed Pool.
264 
265 template <typename Type, Pool& (* pool_)()>
267 {
268 public:
269  using value_type = Type;
270  using pointer = Type *;
271  using const_pointer = const Type *;
272  using reference = Type &;
273  using const_reference = const Type &;
274  using size_type = std::size_t;
275  using difference_type = std::ptrdiff_t;
276 
277  //! C++11 type flag
278  using is_always_equal = std::true_type;
279 
280  //! Return allocator for different type.
281  template <typename U>
283 
284  //! construct FixedPoolAllocator with Pool object
285  FixedPoolAllocator() noexcept = default;
286 
287  //! copy-constructor
288  FixedPoolAllocator(const FixedPoolAllocator&) noexcept = default;
289 
290  //! copy-constructor from a rebound allocator
291  template <typename OtherType>
292  FixedPoolAllocator(const FixedPoolAllocator<OtherType, pool_>&) noexcept { }
293 
294  //! copy-assignment operator
295  FixedPoolAllocator& operator = (const FixedPoolAllocator&) noexcept = default;
296 
297  //! maximum size possible to allocate
298  size_type max_size() const noexcept {
299  return pool_().max_size();
300  }
301 
302  //! attempts to allocate a block of storage with a size large enough to
303  //! contain n elements of member type value_type, and returns a pointer to
304  //! the first element.
305  pointer allocate(size_type n, const void* /* hint */ = nullptr) {
306  return static_cast<Type*>(pool_().allocate(n * sizeof(Type)));
307  }
308 
309  //! releases a block of storage previously allocated with member allocate
310  //! and not yet released.
311  void deallocate(pointer p, size_type n) const noexcept {
312  pool_().deallocate(p, n * sizeof(Type));
313  }
314 
315  //! compare to another allocator of same type
316  template <typename Other>
317  bool operator == (const FixedPoolAllocator<Other, pool_>&) const noexcept {
318  return true;
319  }
320 
321  //! compare to another allocator of same type
322  template <typename Other>
323  bool operator != (const FixedPoolAllocator<Other, pool_>&) const noexcept {
324  return true;
325  }
326 };
327 
328 //! template alias for allocating from mem::g_pool.
329 template <typename Type>
331 
332 //! deleter for unique_ptr with memory from mem::g_pool.
333 template <typename T>
335 {
336 public:
337  //! free the pointer
338  void operator () (T* ptr) const noexcept {
339  GPool().destroy(ptr);
340  }
341 };
342 
343 //! unique_ptr with memory from mem::g_pool.
344 template <typename T>
345 using safe_unique_ptr = std::unique_ptr<T, GPoolDeleter<T> >;
346 
347 //! make_unique with Manager tracking
348 template <typename T, typename... Args>
350  return safe_unique_ptr<T>(
351  GPool().make<T>(std::forward<Args>(args) ...));
352 }
353 
354 //! alias for std::string except that its memory is allocated in the safer
355 //! g_pool.
356 using safe_string = std::basic_string<
357  char, std::char_traits<char>, mem::GPoolAllocator<char> >;
358 
359 //! alias for std::ostringstream except that it uses the safer g_pool as
360 //! allocator for the internal string buffer
361 using safe_ostringstream = std::basic_ostringstream<
362  char, std::char_traits<char>, mem::GPoolAllocator<char> >;
363 
364 } // namespace mem
365 } // namespace thrill
366 
367 #endif // !THRILL_MEM_POOL_HEADER
368 
369 /******************************************************************************/
size_t max_size() const noexcept
maximum size possible to allocate
Definition: pool.cpp:616
std::ptrdiff_t difference_type
Definition: pool.hpp:275
std::size_t size_type
Definition: pool.hpp:202
Type * make(Args &&...args)
Definition: pool.hpp:104
double T
Return allocator for different type.
Definition: pool.hpp:210
std::false_type is_always_equal
C++11 type flag.
Definition: pool.hpp:206
ObjectPool * object_32_
object areas for small fixed size items
Definition: pool.hpp:166
Type
VFS object type.
Definition: file_io.hpp:52
pointer allocate(size_type n, const void *=nullptr)
Definition: pool.hpp:305
std::vector< std::pair< void *, size_t > > allocs_
array of allocations for checking
Definition: pool.hpp:172
std::unique_ptr< T, GPoolDeleter< T > > safe_unique_ptr
unique_ptr with memory from mem::g_pool.
Definition: pool.hpp:345
safe_unique_ptr< T > safe_make_unique(Args &&...args)
make_unique with Manager tracking
Definition: pool.hpp:349
size_t bytes_per_arena(size_t arena_size)
calculate maximum bytes fitting into an Arena with given size.
Definition: pool.cpp:620
void self_verify()
Print out structure of the arenas.
Definition: pool.cpp:931
static constexpr bool debug_check_pairing
debug flag to check pairing of allocate()/deallocate() client calls
Definition: pool.hpp:79
void deallocate(pointer p, size_type n) const noexcept
Definition: pool.hpp:241
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.hpp:181
void destroy(Type *t)
Destroy and deallocate a single item of given Type.
Definition: pool.hpp:112
const Type & const_reference
Definition: pool.hpp:201
const Type & const_reference
Definition: pool.hpp:273
A simple memory allocation manager.
Definition: pool.hpp:74
void * ArenaFindFree(Arena *curr_arena, size_t bin, size_t n, size_t bytes)
find free area inside an Arena
Definition: pool.cpp:449
Arena * AllocateFreeArena(size_t arena_size, bool die_on_failure=true)
allocate a new Arena blob
Definition: pool.cpp:537
size_t min_free_
minimum amount of spare memory to keep in the Pool.
Definition: pool.hpp:163
void * allocate(size_t bytes)
allocate a continuous segment of n bytes in the arenas
Definition: pool.cpp:624
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.hpp:175
std::basic_ostringstream< char, std::char_traits< char >, mem::GPoolAllocator< char > > safe_ostringstream
Definition: pool.hpp:362
Return allocator for different type.
Definition: pool.hpp:282
Pool & GPool()
singleton instance of global pool for I/O data structures
Definition: pool.cpp:26
std::true_type is_always_equal
C++11 type flag.
Definition: pool.hpp:278
deleter for unique_ptr with memory from mem::g_pool.
Definition: pool.hpp:334
void print(bool debug=true)
Print out structure of the arenas.
Definition: pool.cpp:867
ObjectPool * object_256_
Definition: pool.hpp:169
Pool(size_t default_arena_size=16384) noexcept
construct with base allocator
Definition: pool.cpp:408
std::vector< T, Allocator< T > > vector
vector with Manager tracking
Definition: allocator.hpp:228
std::basic_string< char, std::char_traits< char >, mem::GPoolAllocator< char > > safe_string
Definition: pool.hpp:357
void IntDeallocateAll()
deallocate all Arenas
Definition: pool.cpp:604
static const size_t bytes
number of bytes in uint_pair
Definition: uint_types.hpp:75
std::mutex mutex_
Definition: pool.hpp:140
pointer allocate(size_type n, const void *=nullptr)
Definition: pool.hpp:235
const Type * const_pointer
Definition: pool.hpp:199
PoolAllocator(Pool &pool) noexcept
construct PoolAllocator with Pool object
Definition: pool.hpp:213
std::ptrdiff_t difference_type
Definition: pool.hpp:203
size_t free_
number of free slots in all arenas
Definition: pool.hpp:155
void DeallocateAll()
deallocate all Arenas
Definition: pool.cpp:599
Pool & operator=(const Pool &)=delete
non-copyable: delete assignment operator
void deallocate(pointer p, size_type n) const noexcept
Definition: pool.hpp:311
static constexpr bool debug
Definition: pool.hpp:76
size_t size_
overall number of used slots
Definition: pool.hpp:157
Arena * arena_bin_[num_bins+1]
Definition: pool.hpp:152
ObjectPool * object_128_
Definition: pool.hpp:168
static constexpr size_t check_limit
Definition: pool.hpp:80
ObjectPool * object_64_
Definition: pool.hpp:167
size_t default_arena_size_
size of default Arena allocation
Definition: pool.hpp:160
void deallocate(void *ptr, size_t bytes)
Definition: pool.cpp:700
static const size_t num_bins
number of bins
Definition: pool.hpp:148
static constexpr bool debug_verify
Definition: pool.hpp:77