source/lib/allocators/pool.h

   1 /* Copyright (C) 2022 Wildfire Games.
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining
   4  * a copy of this software and associated documentation files (the
   5  * "Software"), to deal in the Software without restriction, including
   6  * without limitation the rights to use, copy, modify, merge, publish,
   7  * distribute, sublicense, and/or sell copies of the Software, and to
   8  * permit persons to whom the Software is furnished to do so, subject to
   9  * the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included
  12  * in all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  17  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  18  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  19  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  20  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 /*
  24  * pool allocator (fixed-size blocks, freelist).
  25  */
  26
  27 #ifndef INCLUDED_ALLOCATORS_POOL
  28 #define INCLUDED_ALLOCATORS_POOL
  29
  30 #include "lib/bits.h"   // ROUND_UP
  31 #include "lib/allocators/allocator_policies.h"
  32
  33 namespace Allocators {
  34
  35 /**
  36  * allocator design parameters:
  37  * - O(1) allocation and deallocation;
  38  * - fixed-size objects;
  39  * - support for deallocating all objects;
  40  * - consecutive allocations are back-to-back;
  41  * - objects are aligned to the pointer size.
  42  **/
  43 template<typename T, class Storage = Storage_Fixed<> >
  44 class Pool
  45 {
  46         NONCOPYABLE(Pool);
  47 public:
  48         // (must round up because freelist stores pointers inside objects)
  49         static const size_t objectSize = ROUND_UP(sizeof(T), sizeof(intptr_t));
  50
  51         Pool(size_t maxObjects)
  52                 : storage(maxObjects*objectSize)
  53         {
  54                 DeallocateAll();
  55         }
  56
  57         size_t RemainingObjects()
  58         {
  59                 return (storage.MaxCapacity() - end) / objectSize;
  60         }
  61
  62         T* Allocate()
  63         {
  64                 void* p = mem_freelist_Detach(freelist);
  65                 if(p)
  66                 {
  67                         ASSERT(Contains((uintptr_t)p));
  68                         return (T*)p;
  69                 }
  70
  71                 return (T*)StorageAppend(storage, end, objectSize);
  72         }
  73
  74         void Deallocate(T* p)
  75         {
  76                 ASSERT(Contains((uintptr_t)p));
  77                 mem_freelist_AddToFront(freelist, p);
  78         }
  79
  80         void DeallocateAll()
  81         {
  82                 freelist = mem_freelist_Sentinel();
  83                 end = 0;
  84         }
  85
  86         // @return whether the address lies within the previously allocated range.
  87         bool Contains(uintptr_t address) const
  88         {
  89                 return (address - storage.Address()) < end;
  90         }
  91
  92 private:
  93         Storage storage;
  94         size_t end;
  95         void* freelist;
  96 };
  97
  98 void TestPool();
  99
 100 }       // namespace Allocators
 101
 102
 103 #include "lib/allocators/dynarray.h"
 104
 105 /**
 106  * allocator design parameters:
 107  * - O(1) alloc and free;
 108  * - either fixed- or variable-sized blocks;
 109  * - doesn't preallocate the entire pool;
 110  * - returns sequential addresses.
 111  *
 112  * opaque! do not read/write any fields!
 113  **/
 114 struct Pool
 115 {
 116         DynArray da;
 117
 118         /**
 119          * size of elements. = 0 if pool set up for variable-sized
 120          * elements, otherwise rounded up to pool alignment.
 121          **/
 122         size_t el_size;
 123
 124         /**
 125          * pointer to freelist (opaque); see freelist_*.
 126          * never used (remains 0) if elements are of variable size.
 127          **/
 128         void* freelist;
 129 };
 130
 131 /**
 132  * pass as pool_create's \<el_size\> param to indicate variable-sized allocs
 133  * are required (see below).
 134  **/
 135 const size_t POOL_VARIABLE_ALLOCS = ~(size_t)0u;
 136
 137 /**
 138  * Ready Pool for use.
 139  *
 140  * @param p Pool*
 141  * @param max_size Max size [bytes] of the Pool; this much
 142  * (rounded up to next page multiple) virtual address space is reserved.
 143  * no virtual memory is actually committed until calls to pool_alloc.
 144  * @param el_size Number of bytes that will be returned by each
 145  * pool_alloc (whose size parameter is then ignored). Can be 0 to
 146  * allow variable-sized allocations, but pool_free is then unusable.
 147  * @return Status
 148  **/
 149 Status pool_create(Pool* p, size_t max_size, size_t el_size);
 150
 151 /**
 152  * free all memory (address space + physical) that constitutes the
 153  * given Pool.
 154  *
 155  * future alloc and free calls on this pool will fail.
 156  * continued use of the allocated memory (*) is
 157  * impossible because it is marked not-present via MMU.
 158  * (* no matter if in freelist or unused or "allocated" to user)
 159  *
 160  * @param p Pool*
 161  * @return Status.
 162  **/
 163 Status pool_destroy(Pool* p);
 164
 165 /**
 166  * indicate whether a pointer was allocated from the given pool.
 167  *
 168  * this is useful for callers that use several types of allocators.
 169  *
 170  * @param p Pool*
 171  * @param el
 172  * @return bool.
 173  **/
 174 bool pool_contains(const Pool* p, void* el);
 175
 176 /**
 177  * Dole out memory from the pool.
 178  * exhausts the freelist before returning new entries to improve locality.
 179  *
 180  * @param p Pool*
 181  * @param size bytes to allocate; ignored if pool_create's el_size was not 0.
 182  * @return allocated memory, or 0 if the Pool would have to be expanded and
 183  * there isn't enough memory to do so.
 184  **/
 185 void* pool_alloc(Pool* p, size_t size);
 186
 187 /**
 188  * Make a fixed-size element available for reuse in the given Pool.
 189  *
 190  * this is not allowed if the Pool was created for variable-size elements.
 191  * rationale: avoids having to pass el_size here and compare with size when
 192  * allocating; also prevents fragmentation and leaking memory.
 193  *
 194  * @param p Pool*
 195  * @param el Element returned by pool_alloc.
 196  **/
 197 void pool_free(Pool* p, void* el);
 198
 199 /**
 200  * "free" all user allocations that ensued from the given Pool.
 201  *
 202  * this resets it as if freshly pool_create-d, but doesn't release the
 203  * underlying reserved virtual memory.
 204  *
 205  * @param p Pool*
 206  **/
 207 void pool_free_all(Pool* p);
 208
 209 /**
 210  * Return the number of bytes committed in the pool's backing array.
 211  *
 212  * This is roughly the number of bytes allocated in this pool plus the
 213  * unused freelist entries.
 214  *
 215  * @param p Pool*
 216  * @return number of bytes
 217  **/
 218 size_t pool_committed(Pool* p);
 219
 220 #endif  // #ifndef INCLUDED_ALLOCATORS_POOL