1 /* Copyright (C) 2011 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 Pool(size_t maxObjects)51 Pool(size_t maxObjects) 52 : storage(maxObjects*objectSize) 53 { 54 DeallocateAll(); 55 } 56 RemainingObjects()57 size_t RemainingObjects() 58 { 59 return (storage.MaxCapacity() - end) / objectSize; 60 } 61 Allocate()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 Deallocate(T * p)74 void Deallocate(T* p) 75 { 76 ASSERT(Contains((uintptr_t)p)); 77 mem_freelist_AddToFront(freelist, p); 78 } 79 DeallocateAll()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. Contains(uintptr_t address)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 LIB_API 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 LIB_API 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 LIB_API 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 LIB_API 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 LIB_API 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 LIB_API 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 LIB_API 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 LIB_API size_t pool_committed(Pool* p); 219 220 #endif // #ifndef INCLUDED_ALLOCATORS_POOL 221