1 //
2 // Copyright(C) 1993-1996 Id Software, Inc.
3 // Copyright(C) 2005-2014 Simon Howard
4 //
5 // This program is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU General Public License
7 // as published by the Free Software Foundation; either version 2
8 // of the License, or (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // DESCRIPTION:
16 // Zone Memory Allocation. Neat.
17 //
18
19 #include <string.h>
20
21 #include "doomtype.h"
22 #include "i_system.h"
23 #include "m_argv.h"
24
25 #include "z_zone.h"
26
27
28 //
29 // ZONE MEMORY ALLOCATION
30 //
31 // There is never any space between memblocks,
32 // and there will never be two contiguous free memblocks.
33 // The rover can be left pointing at a non-empty block.
34 //
35 // It is of no value to free a cachable block,
36 // because it will get overwritten automatically if needed.
37 //
38
39 #define MEM_ALIGN sizeof(void *)
40 #define ZONEID 0x1d4a11
41
42 typedef struct memblock_s
43 {
44 int size; // including the header and possibly tiny fragments
45 void** user;
46 int tag; // PU_FREE if this is free
47 int id; // should be ZONEID
48 struct memblock_s* next;
49 struct memblock_s* prev;
50 } memblock_t;
51
52
53 typedef struct
54 {
55 // total bytes malloced, including header
56 int size;
57
58 // start / end cap for linked list
59 memblock_t blocklist;
60
61 memblock_t* rover;
62
63 } memzone_t;
64
65
66
67 static memzone_t *mainzone;
68 static boolean zero_on_free;
69 static boolean scan_on_free;
70
71
72 //
73 // Z_ClearZone
74 //
Z_ClearZone(memzone_t * zone)75 void Z_ClearZone (memzone_t* zone)
76 {
77 memblock_t* block;
78
79 // set the entire zone to one free block
80 zone->blocklist.next =
81 zone->blocklist.prev =
82 block = (memblock_t *)( (byte *)zone + sizeof(memzone_t) );
83
84 zone->blocklist.user = (void *)zone;
85 zone->blocklist.tag = PU_STATIC;
86 zone->rover = block;
87
88 block->prev = block->next = &zone->blocklist;
89
90 // a free block.
91 block->tag = PU_FREE;
92
93 block->size = zone->size - sizeof(memzone_t);
94 }
95
96
97
98 //
99 // Z_Init
100 //
Z_Init(void)101 void Z_Init (void)
102 {
103 memblock_t* block;
104 int size;
105
106 mainzone = (memzone_t *)I_ZoneBase (&size);
107 mainzone->size = size;
108
109 // set the entire zone to one free block
110 mainzone->blocklist.next =
111 mainzone->blocklist.prev =
112 block = (memblock_t *)( (byte *)mainzone + sizeof(memzone_t) );
113
114 mainzone->blocklist.user = (void *)mainzone;
115 mainzone->blocklist.tag = PU_STATIC;
116 mainzone->rover = block;
117
118 block->prev = block->next = &mainzone->blocklist;
119
120 // free block
121 block->tag = PU_FREE;
122
123 block->size = mainzone->size - sizeof(memzone_t);
124
125 // [Deliberately undocumented]
126 // Zone memory debugging flag. If set, memory is zeroed after it is freed
127 // to deliberately break any code that attempts to use it after free.
128 //
129 zero_on_free = M_ParmExists("-zonezero");
130
131 // [Deliberately undocumented]
132 // Zone memory debugging flag. If set, each time memory is freed, the zone
133 // heap is scanned to look for remaining pointers to the freed block.
134 //
135 scan_on_free = M_ParmExists("-zonescan");
136 }
137
138 // Scan the zone heap for pointers within the specified range, and warn about
139 // any remaining pointers.
ScanForBlock(void * start,void * end)140 static void ScanForBlock(void *start, void *end)
141 {
142 memblock_t *block;
143 void **mem;
144 int i, len, tag;
145
146 block = mainzone->blocklist.next;
147
148 while (block->next != &mainzone->blocklist)
149 {
150 tag = block->tag;
151
152 if (tag == PU_STATIC || tag == PU_LEVEL || tag == PU_LEVSPEC)
153 {
154 // Scan for pointers on the assumption that pointers are aligned
155 // on word boundaries (word size depending on pointer size):
156 mem = (void **) ((byte *) block + sizeof(memblock_t));
157 len = (block->size - sizeof(memblock_t)) / sizeof(void *);
158
159 for (i = 0; i < len; ++i)
160 {
161 if (start <= mem[i] && mem[i] <= end)
162 {
163 fprintf(stderr,
164 "%p has dangling pointer into freed block "
165 "%p (%p -> %p)\n",
166 mem, start, &mem[i], mem[i]);
167 }
168 }
169 }
170
171 block = block->next;
172 }
173 }
174
175 //
176 // Z_Free
177 //
Z_Free(void * ptr)178 void Z_Free (void* ptr)
179 {
180 memblock_t* block;
181 memblock_t* other;
182
183 block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
184
185 if (block->id != ZONEID)
186 I_Error ("Z_Free: freed a pointer without ZONEID");
187
188 if (block->tag != PU_FREE && block->user != NULL)
189 {
190 // clear the user's mark
191 *block->user = 0;
192 }
193
194 // mark as free
195 block->tag = PU_FREE;
196 block->user = NULL;
197 block->id = 0;
198
199 // If the -zonezero flag is provided, we zero out the block on free
200 // to break code that depends on reading freed memory.
201 if (zero_on_free)
202 {
203 memset(ptr, 0, block->size - sizeof(memblock_t));
204 }
205 if (scan_on_free)
206 {
207 ScanForBlock(ptr,
208 (byte *) ptr + block->size - sizeof(memblock_t));
209 }
210
211 other = block->prev;
212
213 if (other->tag == PU_FREE)
214 {
215 // merge with previous free block
216 other->size += block->size;
217 other->next = block->next;
218 other->next->prev = other;
219
220 if (block == mainzone->rover)
221 mainzone->rover = other;
222
223 block = other;
224 }
225
226 other = block->next;
227 if (other->tag == PU_FREE)
228 {
229 // merge the next free block onto the end
230 block->size += other->size;
231 block->next = other->next;
232 block->next->prev = block;
233
234 if (other == mainzone->rover)
235 mainzone->rover = block;
236 }
237 }
238
239
240
241 //
242 // Z_Malloc
243 // You can pass a NULL user if the tag is < PU_PURGELEVEL.
244 //
245 #define MINFRAGMENT 64
246
247
248 void*
Z_Malloc(int size,int tag,void * user)249 Z_Malloc
250 ( int size,
251 int tag,
252 void* user )
253 {
254 int extra;
255 memblock_t* start;
256 memblock_t* rover;
257 memblock_t* newblock;
258 memblock_t* base;
259 void *result;
260
261 size = (size + MEM_ALIGN - 1) & ~(MEM_ALIGN - 1);
262
263 // scan through the block list,
264 // looking for the first free block
265 // of sufficient size,
266 // throwing out any purgable blocks along the way.
267
268 // account for size of block header
269 size += sizeof(memblock_t);
270
271 // if there is a free block behind the rover,
272 // back up over them
273 base = mainzone->rover;
274
275 if (base->prev->tag == PU_FREE)
276 base = base->prev;
277
278 rover = base;
279 start = base->prev;
280
281 do
282 {
283 if (rover == start)
284 {
285 // scanned all the way around the list
286 I_Error ("Z_Malloc: failed on allocation of %i bytes", size);
287 }
288
289 if (rover->tag != PU_FREE)
290 {
291 if (rover->tag < PU_PURGELEVEL)
292 {
293 // hit a block that can't be purged,
294 // so move base past it
295 base = rover = rover->next;
296 }
297 else
298 {
299 // free the rover block (adding the size to base)
300
301 // the rover can be the base block
302 base = base->prev;
303 Z_Free ((byte *)rover+sizeof(memblock_t));
304 base = base->next;
305 rover = base->next;
306 }
307 }
308 else
309 {
310 rover = rover->next;
311 }
312
313 } while (base->tag != PU_FREE || base->size < size);
314
315
316 // found a block big enough
317 extra = base->size - size;
318
319 if (extra > MINFRAGMENT)
320 {
321 // there will be a free fragment after the allocated block
322 newblock = (memblock_t *) ((byte *)base + size );
323 newblock->size = extra;
324
325 newblock->tag = PU_FREE;
326 newblock->user = NULL;
327 newblock->prev = base;
328 newblock->next = base->next;
329 newblock->next->prev = newblock;
330
331 base->next = newblock;
332 base->size = size;
333 }
334
335 if (user == NULL && tag >= PU_PURGELEVEL)
336 I_Error ("Z_Malloc: an owner is required for purgable blocks");
337
338 base->user = user;
339 base->tag = tag;
340
341 result = (void *) ((byte *)base + sizeof(memblock_t));
342
343 if (base->user)
344 {
345 *base->user = result;
346 }
347
348 // next allocation will start looking here
349 mainzone->rover = base->next;
350
351 base->id = ZONEID;
352
353 return result;
354 }
355
356
357
358 //
359 // Z_FreeTags
360 //
361 void
Z_FreeTags(int lowtag,int hightag)362 Z_FreeTags
363 ( int lowtag,
364 int hightag )
365 {
366 memblock_t* block;
367 memblock_t* next;
368
369 for (block = mainzone->blocklist.next ;
370 block != &mainzone->blocklist ;
371 block = next)
372 {
373 // get link before freeing
374 next = block->next;
375
376 // free block?
377 if (block->tag == PU_FREE)
378 continue;
379
380 if (block->tag >= lowtag && block->tag <= hightag)
381 Z_Free ( (byte *)block+sizeof(memblock_t));
382 }
383 }
384
385
386
387 //
388 // Z_DumpHeap
389 // Note: TFileDumpHeap( stdout ) ?
390 //
391 void
Z_DumpHeap(int lowtag,int hightag)392 Z_DumpHeap
393 ( int lowtag,
394 int hightag )
395 {
396 memblock_t* block;
397
398 printf ("zone size: %i location: %p\n",
399 mainzone->size,mainzone);
400
401 printf ("tag range: %i to %i\n",
402 lowtag, hightag);
403
404 for (block = mainzone->blocklist.next ; ; block = block->next)
405 {
406 if (block->tag >= lowtag && block->tag <= hightag)
407 printf ("block:%p size:%7i user:%p tag:%3i\n",
408 block, block->size, block->user, block->tag);
409
410 if (block->next == &mainzone->blocklist)
411 {
412 // all blocks have been hit
413 break;
414 }
415
416 if ( (byte *)block + block->size != (byte *)block->next)
417 printf ("ERROR: block size does not touch the next block\n");
418
419 if ( block->next->prev != block)
420 printf ("ERROR: next block doesn't have proper back link\n");
421
422 if (block->tag == PU_FREE && block->next->tag == PU_FREE)
423 printf ("ERROR: two consecutive free blocks\n");
424 }
425 }
426
427
428 //
429 // Z_FileDumpHeap
430 //
Z_FileDumpHeap(FILE * f)431 void Z_FileDumpHeap (FILE* f)
432 {
433 memblock_t* block;
434
435 fprintf (f,"zone size: %i location: %p\n",mainzone->size,mainzone);
436
437 for (block = mainzone->blocklist.next ; ; block = block->next)
438 {
439 fprintf (f,"block:%p size:%7i user:%p tag:%3i\n",
440 block, block->size, block->user, block->tag);
441
442 if (block->next == &mainzone->blocklist)
443 {
444 // all blocks have been hit
445 break;
446 }
447
448 if ( (byte *)block + block->size != (byte *)block->next)
449 fprintf (f,"ERROR: block size does not touch the next block\n");
450
451 if ( block->next->prev != block)
452 fprintf (f,"ERROR: next block doesn't have proper back link\n");
453
454 if (block->tag == PU_FREE && block->next->tag == PU_FREE)
455 fprintf (f,"ERROR: two consecutive free blocks\n");
456 }
457 }
458
459
460
461 //
462 // Z_CheckHeap
463 //
Z_CheckHeap(void)464 void Z_CheckHeap (void)
465 {
466 memblock_t* block;
467
468 for (block = mainzone->blocklist.next ; ; block = block->next)
469 {
470 if (block->next == &mainzone->blocklist)
471 {
472 // all blocks have been hit
473 break;
474 }
475
476 if ( (byte *)block + block->size != (byte *)block->next)
477 I_Error ("Z_CheckHeap: block size does not touch the next block\n");
478
479 if ( block->next->prev != block)
480 I_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
481
482 if (block->tag == PU_FREE && block->next->tag == PU_FREE)
483 I_Error ("Z_CheckHeap: two consecutive free blocks\n");
484 }
485 }
486
487
488
489
490 //
491 // Z_ChangeTag
492 //
Z_ChangeTag2(void * ptr,int tag,char * file,int line)493 void Z_ChangeTag2(void *ptr, int tag, char *file, int line)
494 {
495 memblock_t* block;
496
497 block = (memblock_t *) ((byte *)ptr - sizeof(memblock_t));
498
499 if (block->id != ZONEID)
500 I_Error("%s:%i: Z_ChangeTag: block without a ZONEID!",
501 file, line);
502
503 if (tag >= PU_PURGELEVEL && block->user == NULL)
504 I_Error("%s:%i: Z_ChangeTag: an owner is required "
505 "for purgable blocks", file, line);
506
507 block->tag = tag;
508 }
509
Z_ChangeUser(void * ptr,void ** user)510 void Z_ChangeUser(void *ptr, void **user)
511 {
512 memblock_t* block;
513
514 block = (memblock_t *) ((byte *)ptr - sizeof(memblock_t));
515
516 if (block->id != ZONEID)
517 {
518 I_Error("Z_ChangeUser: Tried to change user for invalid block!");
519 }
520
521 block->user = user;
522 *user = ptr;
523 }
524
525
526
527 //
528 // Z_FreeMemory
529 //
Z_FreeMemory(void)530 int Z_FreeMemory (void)
531 {
532 memblock_t* block;
533 int free;
534
535 free = 0;
536
537 for (block = mainzone->blocklist.next ;
538 block != &mainzone->blocklist;
539 block = block->next)
540 {
541 if (block->tag == PU_FREE || block->tag >= PU_PURGELEVEL)
542 free += block->size;
543 }
544
545 return free;
546 }
547
Z_ZoneSize(void)548 unsigned int Z_ZoneSize(void)
549 {
550 return mainzone->size;
551 }
552
553