ROSE  0.11.96.11
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://github.com/matzke1/sawyer.
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 
23 namespace Sawyer {
24 
59 template<size_t smallestCell, size_t sizeDelta, size_t nPools, size_t chunkSize, typename Sync>
61 public:
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 
68 private:
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.
78 private:
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
106 private:
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
344 private:
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
357 public:
360  init();
361  }
362 
368  init();
369  }
370 
371 private:
372  // Assignment is nonsensical
373  PoolAllocatorBase& operator=(const PoolAllocatorBase&);
374 
375 public:
380  virtual ~PoolAllocatorBase() {
381  delete[] pools_;
382  }
383 
385  // Public methods
387 public:
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 
521 typedef PoolAllocatorBase<sizeof(void*), 4, 32, 40960, MultiThreadedTag> SynchronizedPoolAllocator;
522 
523 } // namespace
524 #endif
Sawyer::Container::Map::ValueIterator
Bidirectional iterator over values.
Definition: Sawyer/Map.h:241
Sawyer::PoolAllocatorBase::vacuum
void vacuum()
Delete unused chunks.
Definition: PoolAllocator.h:488
Sawyer::PoolAllocatorBase::nAllocated
std::pair< size_t, size_t > nAllocated() const
Number of objects allocated and reserved.
Definition: PoolAllocator.h:450
Sawyer::PoolAllocatorBase::PoolAllocatorBase
PoolAllocatorBase()
Default constructor.
Definition: PoolAllocator.h:359
Sawyer::SingleThreadedTag
Tag indicating that an algorithm or API can assume only a single thread.
Definition: Synchronization.h:47
Sawyer::Container::IntervalMap::values
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
Definition: IntervalMap.h:299
Sawyer::Container::IntervalMap::find
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
Definition: IntervalMap.h:367
Sawyer::PoolAllocatorBase::nCells
static size_t nCells(size_t poolNumber)
Number of cells per chunk.
Definition: PoolAllocator.h:407
Sawyer::PoolAllocatorBase::PoolAllocatorBase
PoolAllocatorBase(const PoolAllocatorBase &)
Copy constructor.
Definition: PoolAllocator.h:367
Sawyer::PoolAllocatorBase::reserve
void reserve(size_t objectSize, size_t nObjects)
Reserve a certain number of objects in the pool.
Definition: PoolAllocator.h:435
Sawyer::PoolAllocatorBase::~PoolAllocatorBase
virtual ~PoolAllocatorBase()
Destructor.
Definition: PoolAllocator.h:380
Sawyer::PoolAllocatorBase::cellSize
static size_t cellSize(size_t poolNumber)
Size of each cell for a given pool.
Definition: PoolAllocator.h:400
Sawyer::PoolAllocatorBase::deallocate
void deallocate(void *addr, size_t size)
Deallocate an object of specified size.
Definition: PoolAllocator.h:469
Sawyer::MultiThreadedTag
Tag indicating that an algorithm or API should assume multiple threads.
Definition: Synchronization.h:41
Sawyer::fastRandomIndex
size_t fastRandomIndex(size_t n, size_t seed=0)
Thread-safe random number generator.
Sawyer::PoolAllocatorBase::poolNumber
static size_t poolNumber(size_t size)
Pool number for a request size.
Definition: PoolAllocator.h:393
Sawyer::PoolAllocatorBase::showInfo
void showInfo(std::ostream &out) const
Print pool allocation information.
Definition: PoolAllocator.h:498
Sawyer
Name space for the entire library.
Definition: Access.h:13
Sawyer::Container::IntervalMap::insert
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
Definition: IntervalMap.h:838
Sawyer::Container::Interval::hull
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:151
Sawyer::PoolAllocatorBase::allocate
void * allocate(size_t size)
Allocate one object of specified size.
Definition: PoolAllocator.h:422
Sawyer::Container::Interval
Range of values delimited by endpoints.
Definition: Interval.h:33
Sawyer::Container::IntervalMap::nIntervals
size_t nIntervals() const
Number of nodes in the container.
Definition: IntervalMap.h:673
Sawyer::Container::IntervalMap
An associative container whose keys are non-overlapping intervals.
Definition: IntervalMap.h:171
Sawyer::PoolAllocatorBase
Small object allocation from memory pools.
Definition: PoolAllocator.h:60