Line data Source code
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 0 : 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 0 : Pool(size_t maxObjects)
52 0 : : storage(maxObjects*objectSize)
53 : {
54 0 : DeallocateAll();
55 0 : }
56 :
57 0 : size_t RemainingObjects()
58 : {
59 0 : return (storage.MaxCapacity() - end) / objectSize;
60 : }
61 :
62 0 : T* Allocate()
63 : {
64 0 : void* p = mem_freelist_Detach(freelist);
65 0 : if(p)
66 : {
67 0 : ASSERT(Contains((uintptr_t)p));
68 0 : return (T*)p;
69 : }
70 :
71 0 : 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 0 : void DeallocateAll()
81 : {
82 0 : freelist = mem_freelist_Sentinel();
83 0 : end = 0;
84 0 : }
85 :
86 : // @return whether the address lies within the previously allocated range.
87 0 : bool Contains(uintptr_t address) const
88 : {
89 0 : 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
|
