ROSE 0.11.145.147
PoolAllocator.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_PoolAllocator_H
9#define Sawyer_PoolAllocator_H
10
11#include <boost/version.hpp>
12#include <boost/foreach.hpp>
13#include <boost/static_assert.hpp>
14#include <boost/cstdint.hpp>
15#include <list>
16#include <Sawyer/Assert.h>
17#include <Sawyer/Interval.h>
18#include <Sawyer/IntervalMap.h>
19#include <Sawyer/Sawyer.h>
20#include <Sawyer/Synchronization.h>
21#include <vector>
22
23namespace Sawyer {
24
59template<size_t smallestCell, size_t sizeDelta, size_t nPools, size_t chunkSize, typename Sync>
61public:
62 enum { SMALLEST_CELL = smallestCell };
63 enum { SIZE_DELTA = sizeDelta };
64 enum { N_POOLS = nPools };
65 enum { CHUNK_SIZE = chunkSize };
66 enum { N_FREE_LISTS = 32 }; // number of free lists per pool
67
68private:
69
70 // Singly-linked list of cells (units of object backing store) that are not being used by the caller.
71 struct FreeCell { FreeCell *next; };
72
74
76 // Basic unit of allocation.
78private:
79 class Chunk {
80 unsigned char data_[chunkSize];
81 public:
82 BOOST_STATIC_ASSERT(chunkSize >= sizeof(FreeCell));
83
84 FreeCell* fill(size_t cellSize) { // create a free list for this chunk
85 ASSERT_require(cellSize >= sizeof(FreeCell));
86 ASSERT_require(cellSize <= chunkSize);
87 FreeCell *retval = NULL;
88 size_t n = chunkSize / cellSize;
89 for (size_t i=n; i>0; --i) { // free list in address order is easier to debug at no extra expense
90 FreeCell *cell = reinterpret_cast<FreeCell*>(data_+(i-1)*cellSize);
91 cell->next = retval;
92 retval = cell;
93 }
94 return retval;
95 }
96
97 ChunkAddressInterval extent() const {
98 return ChunkAddressInterval::hull(reinterpret_cast<boost::uint64_t>(data_),
99 reinterpret_cast<boost::uint64_t>(data_+chunkSize-1));
100 }
101 };
102
104 // Interesting info about a chunk
106private:
107 struct ChunkInfo {
108 const Chunk *chunk;
109 size_t nUsed;
110 ChunkInfo(): chunk(NULL), nUsed(0) {}
111 ChunkInfo(const Chunk *chunk, size_t nUsed): chunk(chunk), nUsed(nUsed) {}
112 bool operator==(const ChunkInfo &other) const {
113 return chunk==other.chunk && nUsed==other.nUsed;
114 }
115 };
116
118
119 class Pool;
120
121 // Aquire all locks for a pool.
122 class LockEverything {
123 SAWYER_THREAD_TRAITS::Mutex *freeListMutexes_, &chunkMutex_;
124 size_t nLocked_;
125 public:
126 LockEverything(SAWYER_THREAD_TRAITS::Mutex *freeListMutexes, SAWYER_THREAD_TRAITS::Mutex &chunkMutex)
127 : freeListMutexes_(freeListMutexes), chunkMutex_(chunkMutex), nLocked_(0) {
128 while (nLocked_ < N_FREE_LISTS) {
129 freeListMutexes_[nLocked_].lock();
130 ++nLocked_;
131 }
132 chunkMutex_.lock();
133 }
134
135 ~LockEverything() {
136 while (nLocked_ > 0) {
137 freeListMutexes_[nLocked_-1].unlock();
138 --nLocked_;
139 }
140 chunkMutex_.unlock();
141 }
142 };
143
145 // Pool of single-sized cells; collection of chunks
147 class Pool {
148 size_t cellSize_; // only modified immediately after construction
149
150 // Multiple free-lists for parallelism reduces the contention on the pool. The aquire and release methods select a
151 // free-list uniformly at random in order to keep the sizes of the free-lists relatively equal. There is no requirement
152 // that an object allocated from one free-list be released back to the same free-list. Each free-list has its own
153 // mutex. When locking multiple free-lists, the locks should be aquired in order of their indexes.
154 SAWYER_THREAD_TRAITS::Mutex freeListMutexes_[N_FREE_LISTS];
155 FreeCell *freeLists_[N_FREE_LISTS];
156
157 // The chunk-list stores the memory allocated for objects. The chunk-list is protected by a mutex. When locking
158 // free-list(s) and the chunk-list, the free-list locks should be aquired first.
159 mutable SAWYER_THREAD_TRAITS::Mutex chunkMutex_;
160 std::list<Chunk*> chunks_;
161
162 private:
163 Pool(const Pool&); // nonsense
164
165 public:
166 Pool(): cellSize_(0) {
167 memset(freeLists_, 0, sizeof freeLists_);
168 }
169
170 void init(size_t cellSize) {
171 assert(cellSize_ == 0);
172 assert(cellSize > 0);
173 cellSize_ = cellSize;
174 }
175
176 public:
177 ~Pool() {
178 for (typename std::list<Chunk*>::iterator ci=chunks_.begin(); ci!=chunks_.end(); ++ci)
179 delete *ci;
180 }
181
182 bool isEmpty() const {
183 SAWYER_THREAD_TRAITS::LockGuard lock(chunkMutex_);
184 return chunks_.empty();
185 }
186
187 // Obtains the cell at the front of the free list, allocating more space if necessary.
188 void* aquire() { // hot
189 const size_t freeListIdx = fastRandomIndex(N_FREE_LISTS);
190 SAWYER_THREAD_TRAITS::LockGuard lock(freeListMutexes_[freeListIdx]);
191 if (!freeLists_[freeListIdx]) {
192 Chunk *chunk = new Chunk;
193 freeLists_[freeListIdx] = chunk->fill(cellSize_);
194 SAWYER_THREAD_TRAITS::LockGuard lock(chunkMutex_);
195 chunks_.push_back(chunk);
196 }
197 ASSERT_not_null(freeLists_[freeListIdx]);
198 FreeCell *cell = freeLists_[freeListIdx];
199 freeLists_[freeListIdx] = freeLists_[freeListIdx]->next;
200 cell->next = NULL; // optional
201 return cell;
202 }
203
204 // Returns an cell to the front of the free list.
205 void release(void *cell) { // hot
206 const size_t freeListIdx = fastRandomIndex(N_FREE_LISTS);
207 SAWYER_THREAD_TRAITS::LockGuard lock(freeListMutexes_[freeListIdx]);
208 ASSERT_not_null(cell);
209 FreeCell *freedCell = reinterpret_cast<FreeCell*>(cell);
210 freedCell->next = freeLists_[freeListIdx];
211 freeLists_[freeListIdx] = freedCell;
212 }
213
214 // Information about each chunk.
215 ChunkInfoMap chunkInfoNS() const {
216 ChunkInfoMap map;
217 BOOST_FOREACH (const Chunk* chunk, chunks_)
218 map.insert(chunk->extent(), ChunkInfo(chunk, chunkSize / cellSize_));
219 for (size_t freeListIdx = 0; freeListIdx < N_FREE_LISTS; ++freeListIdx) {
220 for (FreeCell *cell=freeLists_[freeListIdx]; cell!=NULL; cell=cell->next) {
221 typename ChunkInfoMap::ValueIterator found = map.find(reinterpret_cast<boost::uint64_t>(cell));
222 ASSERT_require2(found!=map.values().end(), "each freelist item must be some chunk cell");
223 ASSERT_require2(found->nUsed > 0, "freelist must be consistent with chunk capacities");
224 --found->nUsed;
225 }
226 }
227 return map;
228 }
229
230 // Reserve objects to satisfy future allocation requests.
231 void reserve(size_t nObjects) {
232 LockEverything guard(freeListMutexes_, chunkMutex_);
233 size_t nFree = 0;
234 for (size_t freeListIdx = 0; freeListIdx < N_FREE_LISTS; ++freeListIdx) {
235 for (FreeCell *cell = freeLists_[freeListIdx]; cell != NULL; cell = cell->next) {
236 ++nFree;
237 if (nFree >= nObjects)
238 return;
239 }
240 }
241
242 size_t freeListIdx = fastRandomIndex(N_FREE_LISTS);
243 size_t nNeeded = nObjects - nFree;
244 const size_t cellsPerChunk = chunkSize / cellSize_;
245 while (1) {
246 // Allocate a new chunk of object cells
247 Chunk *chunk = new Chunk;
248 FreeCell *newCells = chunk->fill(cellSize_);
249 chunks_.push_back(chunk);
250
251 // Insert the new object cells into the free lists in round-robin order
252 while (newCells) {
253 FreeCell *cell = newCells;
254 newCells = cell->next;
255 cell->next = freeLists_[freeListIdx];
256 freeLists_[freeListIdx] = cell;
257 if (++freeListIdx >= N_FREE_LISTS)
258 freeListIdx = 0;
259 }
260
261 if (nNeeded < cellsPerChunk)
262 return;
263 }
264 }
265
266 // Free unused chunks
267 void vacuum() {
268 // We must aquire all the free list-locks plus the chunks-lock before we call chunkInfoNS. Free-list locks must be
269 // aquired before the chunk-list lock.
270 LockEverything guard(freeListMutexes_, chunkMutex_);
271 ChunkInfoMap map = chunkInfoNS();
272
273 // Scan the free lists, creating new free lists in the process. For any cell on an old free list, if the cell
274 // belongs to a chunk that we're keeping, then copy the cell to a new free list. The cells are copied round-robin
275 // to the new free lists so that the lists stay balanced.
276 FreeCell *newFreeLists[N_FREE_LISTS];
277 memset(newFreeLists, 0, sizeof newFreeLists);
278 size_t newFreeListIdx = 0;
279 for (size_t oldFreeListIdx=0; oldFreeListIdx<N_FREE_LISTS; ++oldFreeListIdx) {
280 FreeCell *next = NULL;
281 for (FreeCell *cell = freeLists_[oldFreeListIdx]; cell != NULL; cell = next) {
282 next = cell->next;
283 boost::uint64_t cellAddr = reinterpret_cast<boost::uint64_t>(cell);
284 if (map[cellAddr].nUsed != 0) {
285 // Keep this cell by round-robin inserting it into a new free list.
286 cell->next = newFreeLists[newFreeListIdx];
287 newFreeLists[newFreeListIdx] = cell;
288 if (++newFreeListIdx >= N_FREE_LISTS)
289 newFreeListIdx = 0;
290 }
291 }
292 }
293 memcpy(freeLists_, newFreeLists, sizeof newFreeLists);
294
295 // Delete chunks that have no used cells.
296 typename std::list<Chunk*>::iterator iter = chunks_.begin();
297 while (iter!=chunks_.end()) {
298 Chunk *chunk = *iter;
299 boost::uint64_t cellAddr = chunk->extent().least(); // any cell will do
300 if (map[cellAddr].nUsed == 0) {
301 delete chunk;
302 iter = chunks_.erase(iter);
303 } else {
304 ++iter;
305 }
306 }
307 }
308
309 size_t showInfo(std::ostream &out) const {
310 ChunkInfoMap cim;
311 {
312 LockEverything guard(const_cast<SAWYER_THREAD_TRAITS::Mutex*>(freeListMutexes_), chunkMutex_);
313 cim = chunkInfoNS();
314 }
315
316 const size_t nCells = chunkSize / cellSize_;
317 size_t totalUsed=0;
318 BOOST_FOREACH (const ChunkInfo &info, cim.values()) {
319 out <<" chunk " <<info.chunk <<"\t" <<info.nUsed <<"/" <<nCells <<"\t= " <<100.0*info.nUsed/nCells <<"%\n";
320 totalUsed += info.nUsed;
321 }
322 return totalUsed;
323 }
324
325 std::pair<size_t, size_t> nAllocated() const {
326 ChunkInfoMap cim;
327 {
328 LockEverything guard(const_cast<SAWYER_THREAD_TRAITS::Mutex*>(freeListMutexes_), chunkMutex_);
329 cim = chunkInfoNS();
330 }
331
332 const size_t nCells = chunkSize / cellSize_;
333 size_t nReserved = nCells * cim.nIntervals();
334 size_t nAllocated = 0;
335 BOOST_FOREACH (const ChunkInfo &info, cim.values())
336 nAllocated += info.nUsed;
337 return std::make_pair(nAllocated, nReserved);
338 }
339 };
340
342 // Private data members and methods
344private:
345 Pool *pools_; // modified only in constructors and destructor
346
347 // Called only by constructors
348 void init() {
349 pools_ = new Pool[nPools];
350 for (size_t i=0; i<nPools; ++i)
351 pools_[i].init(cellSize(i));
352 }
353
355 // Construction
357public:
360 init();
361 }
362
368 init();
369 }
370
371private:
372 // Assignment is nonsensical
373 PoolAllocatorBase& operator=(const PoolAllocatorBase&);
374
375public:
381 delete[] pools_;
382 }
383
385 // Public methods
387public:
393 static size_t poolNumber(size_t size) {
394 return size <= smallestCell ? 0 : (size - smallestCell + sizeDelta - 1) / sizeDelta;
395 }
396
400 static size_t cellSize(size_t poolNumber) {
401 return smallestCell + poolNumber * sizeDelta;
402 }
403
407 static size_t nCells(size_t poolNumber) {
408 return chunkSize / cellSize(poolNumber);
409 }
410
422 void *allocate(size_t size) { // hot
423 ASSERT_require(size>0);
424 size_t pn = poolNumber(size);
425 return pn < nPools ? pools_[pn].aquire() : ::operator new(size);
426 }
427
435 void reserve(size_t objectSize, size_t nObjects) {
436 ASSERT_always_require(objectSize > 0); // so objectSize is always used
437 size_t pn = poolNumber(nObjects);
438 if (pn >= nPools)
439 return;
440 pools_[pn].reserve(nObjects);
441 }
442
450 std::pair<size_t, size_t> nAllocated() const {
451 size_t nAllocated = 0, nReserved = 0;
452 for (size_t pn=0; pn<nPools; ++pn) {
453 std::pair<size_t, size_t> pp = pools_[pn].nAllocated();
454 nAllocated += pp.first;
455 nReserved += pp.second;
456 }
457 return std::make_pair(nAllocated, nReserved);
458 }
459
469 void deallocate(void *addr, size_t size) { // hot
470 if (addr) {
471 ASSERT_require(size>0);
472 size_t pn = poolNumber(size);
473 if (pn < nPools) {
474 pools_[pn].release(addr);
475 } else {
476 ::operator delete(addr);
477 }
478 }
479 }
480
488 void vacuum() {
489 for (size_t pn=0; pn<nPools; ++pn)
490 pools_[pn].vacuum();
491 }
492
498 void showInfo(std::ostream &out) const {
499 for (size_t pn=0; pn<nPools; ++pn) {
500 if (!pools_[pn].isEmpty()) {
501 out <<" pool #" <<pn <<"; cellSize = " <<cellSize(pn) <<" bytes:\n";
502 size_t nUsed = pools_[pn].showInfo(out);
503 out <<" total objects in use: " <<nUsed <<"\n";
504 }
505 }
506 }
507};
508
515
522
523} // namespace
524#endif
An associative container whose keys are non-overlapping intervals.
size_t nIntervals() const
Number of nodes in the container.
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
Range of values delimited by endpoints.
Definition Interval.h:31
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition Interval.h:162
Bidirectional iterator over values.
Definition Sawyer/Map.h:271
Small object allocation from memory pools.
static size_t nCells(size_t poolNumber)
Number of cells per chunk.
static size_t poolNumber(size_t size)
Pool number for a request size.
void * allocate(size_t size)
Allocate one object of specified size.
PoolAllocatorBase(const PoolAllocatorBase &)
Copy constructor.
std::pair< size_t, size_t > nAllocated() const
Number of objects allocated and reserved.
void deallocate(void *addr, size_t size)
Deallocate an object of specified size.
void vacuum()
Delete unused chunks.
virtual ~PoolAllocatorBase()
Destructor.
void reserve(size_t objectSize, size_t nObjects)
Reserve a certain number of objects in the pool.
void showInfo(std::ostream &out) const
Print pool allocation information.
PoolAllocatorBase()
Default constructor.
static size_t cellSize(size_t poolNumber)
Size of each cell for a given pool.
Sawyer support library.
size_t fastRandomIndex(size_t n, size_t seed=0)
Thread-safe random number generator.
Tag indicating that an algorithm or API should assume multiple threads.
Tag indicating that an algorithm or API can assume only a single thread.