1 /*
2 ** memarena.cpp
3 ** Implements memory arenas.
4 **
5 **---------------------------------------------------------------------------
6 ** Copyright 2010 Randy Heit
7 ** All rights reserved.
8 **
9 ** Redistribution and use in source and binary forms, with or without
10 ** modification, are permitted provided that the following conditions
11 ** are met:
12 **
13 ** 1. Redistributions of source code must retain the above copyright
14 ** notice, this list of conditions and the following disclaimer.
15 ** 2. Redistributions in binary form must reproduce the above copyright
16 ** notice, this list of conditions and the following disclaimer in the
17 ** documentation and/or other materials provided with the distribution.
18 ** 3. The name of the author may not be used to endorse or promote products
19 ** derived from this software without specific prior written permission.
20 **
21 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 ** THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 **---------------------------------------------------------------------------
32 **
33 ** A memory arena is used for efficient allocation of many small objects that
34 ** will all be freed at once. Note that since individual destructors are not
35 ** called, you must not use an arena to allocate any objects that use a
36 ** destructor, either explicitly or implicitly (because they have members
37 ** with destructors).
38 */
39
40 #include "doomtype.h"
41 #include "m_alloc.h"
42 #include "memarena.h"
43 #include "c_dispatch.h"
44 #include "zstring.h"
45
46 #define BLOCK_SIZE (10*1024)
47
48 struct FMemArena::Block
49 {
50 Block *NextBlock;
51 void *Limit; // End of this block
52 void *Avail; // Start of free space in this block
53
54 void Reset();
55 void *Alloc(size_t size);
56 };
57
58 //==========================================================================
59 //
60 // RoundPointer
61 //
62 // Rounds a pointer up to a pointer-sized boundary.
63 //
64 //==========================================================================
65
RoundPointer(void * ptr)66 static inline void *RoundPointer(void *ptr)
67 {
68 return (void *)(((size_t)ptr + sizeof(void*) - 1) & ~(sizeof(void*) - 1));
69 }
70
71 //==========================================================================
72 //
73 // FMemArena Constructor
74 //
75 //==========================================================================
76
FMemArena()77 FMemArena::FMemArena()
78 {
79 TopBlock = NULL;
80 FreeBlocks = NULL;
81 }
82
83 //==========================================================================
84 //
85 // FMemArena Destructor
86 //
87 //==========================================================================
88
~FMemArena()89 FMemArena::~FMemArena()
90 {
91 FreeAllBlocks();
92 }
93
94 //==========================================================================
95 //
96 // FMemArena :: Alloc
97 //
98 //==========================================================================
99
Alloc(size_t size)100 void *FMemArena::Alloc(size_t size)
101 {
102 Block *block;
103
104 for (block = TopBlock; block != NULL; block = block->NextBlock)
105 {
106 void *res = block->Alloc(size);
107 if (res != NULL)
108 {
109 return res;
110 }
111 }
112 block = AddBlock(size);
113 return block->Alloc(size);
114 }
115
116 //==========================================================================
117 //
118 // FMemArena :: FreeAll
119 //
120 // Moves all blocks to the free list. No system-level deallocation occurs.
121 //
122 //==========================================================================
123
FreeAll()124 void FMemArena::FreeAll()
125 {
126 for (Block *next, *block = TopBlock; block != NULL; block = next)
127 {
128 next = block->NextBlock;
129 block->Reset();
130 block->NextBlock = FreeBlocks;
131 FreeBlocks = block;
132 }
133 TopBlock = NULL;
134 }
135
136 //==========================================================================
137 //
138 // FMemArena :: FreeAllBlocks
139 //
140 // Frees all blocks used by this arena.
141 //
142 //==========================================================================
143
FreeAllBlocks()144 void FMemArena::FreeAllBlocks()
145 {
146 FreeBlockChain(TopBlock);
147 FreeBlockChain(FreeBlocks);
148 }
149
150 //==========================================================================
151 //
152 // FMemArena :: FreeBlockChain
153 //
154 // Frees a chain of blocks.
155 //
156 //==========================================================================
157
FreeBlockChain(Block * & top)158 void FMemArena::FreeBlockChain(Block *&top)
159 {
160 for (Block *next, *block = top; block != NULL; block = next)
161 {
162 next = block->NextBlock;
163 M_Free(block);
164 }
165 top = NULL;
166 }
167
168 //==========================================================================
169 //
170 // FMemArena :: AddBlock
171 //
172 // Allocates a block large enough to hold at least <size> bytes and adds it
173 // to the TopBlock chain.
174 //
175 //==========================================================================
176
AddBlock(size_t size)177 FMemArena::Block *FMemArena::AddBlock(size_t size)
178 {
179 Block *mem, **last;
180 size += sizeof(Block); // Account for header size
181
182 // Search for a free block to use
183 for (last = &FreeBlocks, mem = FreeBlocks; mem != NULL; last = &mem->NextBlock, mem = mem->NextBlock)
184 {
185 if ((BYTE *)mem->Limit - (BYTE *)mem >= (ptrdiff_t)size)
186 {
187 *last = mem->NextBlock;
188 break;
189 }
190 }
191 if (mem == NULL)
192 {
193 // Allocate a new block
194 if (size < BLOCK_SIZE)
195 {
196 size = BLOCK_SIZE;
197 }
198 else
199 { // Stick some free space at the end so we can use this block for
200 // other things.
201 size += BLOCK_SIZE/2;
202 }
203 mem = (Block *)M_Malloc(size);
204 mem->Limit = (BYTE *)mem + size;
205 }
206 mem->Reset();
207 mem->NextBlock = TopBlock;
208 TopBlock = mem;
209 return mem;
210 }
211
212 //==========================================================================
213 //
214 // FMemArena :: Block :: Reset
215 //
216 // Resets this block's Avail pointer.
217 //
218 //==========================================================================
219
Reset()220 void FMemArena::Block::Reset()
221 {
222 Avail = RoundPointer(this + sizeof(*this));
223 }
224
225 //==========================================================================
226 //
227 // FMemArena :: Block :: Alloc
228 //
229 // Allocates memory from the block if it has space. Returns NULL if not.
230 //
231 //==========================================================================
232
Alloc(size_t size)233 void *FMemArena::Block::Alloc(size_t size)
234 {
235 if ((char *)Avail + size > Limit)
236 {
237 return NULL;
238 }
239 void *res = Avail;
240 Avail = RoundPointer((char *)Avail + size);
241 return res;
242 }
243
244 //==========================================================================
245 //
246 // FSharedStringArena Constructor
247 //
248 //==========================================================================
249
FSharedStringArena()250 FSharedStringArena::FSharedStringArena()
251 {
252 memset(Buckets, 0, sizeof(Buckets));
253 }
254
255 //==========================================================================
256 //
257 // FSharedStringArena Destructor
258 //
259 //==========================================================================
260
~FSharedStringArena()261 FSharedStringArena::~FSharedStringArena()
262 {
263 FreeAll();
264 // FMemArena destructor will free the blocks.
265 }
266
267 //==========================================================================
268 //
269 // FSharedStringArena :: Alloc
270 //
271 // Allocates a new string and initializes it with the passed string. This
272 // version takes an FString as a parameter, so it won't need to allocate any
273 // memory for the string text if it already exists in the arena.
274 //
275 //==========================================================================
276
Alloc(const FString & source)277 FString *FSharedStringArena::Alloc(const FString &source)
278 {
279 unsigned int hash;
280 Node *strnode;
281
282 strnode = FindString(source, source.Len(), hash);
283 if (strnode == NULL)
284 {
285 strnode = (Node *)FMemArena::Alloc(sizeof(Node));
286 ::new(&strnode->String) FString(source);
287 strnode->Hash = hash;
288 hash %= countof(Buckets);
289 strnode->Next = Buckets[hash];
290 Buckets[hash] = strnode;
291 }
292 return &strnode->String;
293 }
294
295 //==========================================================================
296 //
297 // FSharedStringArena :: Alloc
298 //
299 //==========================================================================
300
Alloc(const char * source)301 FString *FSharedStringArena::Alloc(const char *source)
302 {
303 return Alloc(source, strlen(source));
304 }
305
306 //==========================================================================
307 //
308 // FSharedStringArena :: Alloc
309 //
310 //==========================================================================
311
Alloc(const char * source,size_t strlen)312 FString *FSharedStringArena::Alloc(const char *source, size_t strlen)
313 {
314 unsigned int hash;
315 Node *strnode;
316
317 strnode = FindString(source, strlen, hash);
318 if (strnode == NULL)
319 {
320 strnode = (Node *)FMemArena::Alloc(sizeof(Node));
321 ::new(&strnode->String) FString(source, strlen);
322 strnode->Hash = hash;
323 hash %= countof(Buckets);
324 strnode->Next = Buckets[hash];
325 Buckets[hash] = strnode;
326 }
327 return &strnode->String;
328 }
329
330 //==========================================================================
331 //
332 // FSharedStringArena :: FindString
333 //
334 // Finds the string if it's already in the arena. Returns NULL if not.
335 //
336 //==========================================================================
337
FindString(const char * str,size_t strlen,unsigned int & hash)338 FSharedStringArena::Node *FSharedStringArena::FindString(const char *str, size_t strlen, unsigned int &hash)
339 {
340 hash = SuperFastHash(str, strlen);
341
342 for (Node *node = Buckets[hash % countof(Buckets)]; node != NULL; node = node->Next)
343 {
344 if (node->Hash == hash && node->String.Len() == strlen && memcmp(&node->String[0], str, strlen) == 0)
345 {
346 return node;
347 }
348 }
349 return NULL;
350 }
351
352 //==========================================================================
353 //
354 // FSharedStringArena :: FreeAll
355 //
356 // In addition to moving all used blocks onto the free list, all FStrings
357 // they contain will have their destructors called.
358 //
359 //==========================================================================
360
FreeAll()361 void FSharedStringArena::FreeAll()
362 {
363 for (Block *next, *block = TopBlock; block != NULL; block = next)
364 {
365 next = block->NextBlock;
366 void *limit = block->Avail;
367 block->Reset();
368 for (Node *string = (Node *)block->Avail; string < limit; ++string)
369 {
370 string->~Node();
371 }
372 block->NextBlock = FreeBlocks;
373 FreeBlocks = block;
374 }
375 memset(Buckets, 0, sizeof(Buckets));
376 TopBlock = NULL;
377 }
378