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 // This is an implementation of the zone memory API which
19 // uses native calls to malloc() and free().
20 //
21
22
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "z_zone.h"
27 #include "i_system.h"
28 #include "doomtype.h"
29
30 #define ZONEID 0x1d4a11
31
32 typedef struct memblock_s memblock_t;
33
34 struct memblock_s
35 {
36 int id; // = ZONEID
37 int tag;
38 int size;
39 void **user;
40 memblock_t *prev;
41 memblock_t *next;
42 };
43
44 // Linked list of allocated blocks for each tag type
45
46 static memblock_t *allocated_blocks[PU_NUM_TAGS];
47
48 #ifdef TESTING
49
50 static int test_malloced = 0;
51
test_malloc(size_t size)52 void *test_malloc(size_t size)
53 {
54 int *result;
55
56 if (test_malloced + size > 2 * 1024 * 1024)
57 {
58 return NULL;
59 }
60
61 test_malloced += size;
62
63 result = malloc(size + sizeof(int));
64
65 *result = size;
66
67 return result + 1;
68 }
69
test_free(void * data)70 void test_free(void *data)
71 {
72 int *i;
73
74 i = ((int *) data) - 1;
75
76 test_malloced -= *i;
77
78 free(i);
79 }
80
81 #define malloc test_malloc
82 #define free test_free
83
84 #endif /* #ifdef TESTING */
85
86
87 // Add a block into the linked list for its type.
88
Z_InsertBlock(memblock_t * block)89 static void Z_InsertBlock(memblock_t *block)
90 {
91 block->prev = NULL;
92 block->next = allocated_blocks[block->tag];
93 allocated_blocks[block->tag] = block;
94
95 if (block->next != NULL)
96 {
97 block->next->prev = block;
98 }
99 }
100
101 // Remove a block from its linked list.
102
Z_RemoveBlock(memblock_t * block)103 static void Z_RemoveBlock(memblock_t *block)
104 {
105 // Unlink from list
106
107 if (block->prev == NULL)
108 {
109 // Start of list
110
111 allocated_blocks[block->tag] = block->next;
112 }
113 else
114 {
115 block->prev->next = block->next;
116 }
117
118 if (block->next != NULL)
119 {
120 block->next->prev = block->prev;
121 }
122 }
123
124 //
125 // Z_Init
126 //
Z_Init(void)127 void Z_Init (void)
128 {
129 memset(allocated_blocks, 0, sizeof(allocated_blocks));
130 printf("zone memory: Using native C allocator.\n");
131 }
132
133
134 //
135 // Z_Free
136 //
Z_Free(void * ptr)137 void Z_Free (void* ptr)
138 {
139 memblock_t* block;
140
141 block = (memblock_t *) ((byte *)ptr - sizeof(memblock_t));
142
143 if (block->id != ZONEID)
144 {
145 I_Error ("Z_Free: freed a pointer without ZONEID");
146 }
147
148 if (block->tag != PU_FREE && block->user != NULL)
149 {
150 // clear the user's mark
151
152 *block->user = NULL;
153 }
154
155 Z_RemoveBlock(block);
156
157 // Free back to system
158
159 free(block);
160 }
161
162 // Empty data from the cache list to allocate enough data of the size
163 // required.
164 //
165 // Returns true if any blocks were freed.
166
ClearCache(int size)167 static boolean ClearCache(int size)
168 {
169 memblock_t *block;
170 memblock_t *next_block;
171 int remaining;
172
173 block = allocated_blocks[PU_CACHE];
174
175 if (block == NULL)
176 {
177 // Cache is already empty.
178
179 return false;
180 }
181
182 // Search to the end of the PU_CACHE list. The blocks at the end
183 // of the list are the ones that have been free for longer and
184 // are more likely to be unneeded now.
185
186 while (block->next != NULL)
187 {
188 block = block->next;
189 }
190
191 //printf("out of memory; cleaning out the cache: %i\n", test_malloced);
192
193 // Search backwards through the list freeing blocks until we have
194 // freed the amount of memory required.
195
196 remaining = size;
197
198 while (remaining > 0)
199 {
200 if (block == NULL)
201 {
202 // No blocks left to free; we've done our best.
203
204 break;
205 }
206
207 next_block = block->prev;
208
209 Z_RemoveBlock(block);
210
211 remaining -= block->size;
212
213 if (block->user)
214 {
215 *block->user = NULL;
216 }
217
218 free(block);
219
220 block = next_block;
221 }
222
223 return true;
224 }
225
226 //
227 // Z_Malloc
228 // You can pass a NULL user if the tag is < PU_PURGELEVEL.
229 //
230
Z_Malloc(int size,int tag,void * user)231 void *Z_Malloc(int size, int tag, void *user)
232 {
233 memblock_t *newblock;
234 unsigned char *data;
235 void *result;
236
237 if (tag < 0 || tag >= PU_NUM_TAGS || tag == PU_FREE)
238 {
239 I_Error("Z_Malloc: attempted to allocate a block with an invalid "
240 "tag: %i", tag);
241 }
242
243 if (user == NULL && tag >= PU_PURGELEVEL)
244 {
245 I_Error ("Z_Malloc: an owner is required for purgable blocks");
246 }
247
248 // Malloc a block of the required size
249
250 newblock = NULL;
251
252 while (newblock == NULL)
253 {
254 newblock = (memblock_t *) malloc(sizeof(memblock_t) + size);
255
256 if (newblock == NULL)
257 {
258 if (!ClearCache(sizeof(memblock_t) + size))
259 {
260 I_Error("Z_Malloc: failed on allocation of %i bytes", size);
261 }
262 }
263 }
264
265 newblock->tag = tag;
266
267 // Hook into the linked list for this tag type
268
269 newblock->id = ZONEID;
270 newblock->user = user;
271 newblock->size = size;
272
273 Z_InsertBlock(newblock);
274
275 data = (unsigned char *) newblock;
276 result = data + sizeof(memblock_t);
277
278 if (user != NULL)
279 {
280 *newblock->user = result;
281 }
282
283 return result;
284 }
285
286
287
288 //
289 // Z_FreeTags
290 //
291
Z_FreeTags(int lowtag,int hightag)292 void Z_FreeTags(int lowtag, int hightag)
293 {
294 int i;
295
296 for (i=lowtag; i<= hightag; ++i)
297 {
298 memblock_t *block;
299 memblock_t *next;
300
301 // Free all in this chain
302
303 for (block=allocated_blocks[i]; block != NULL; )
304 {
305 next = block->next;
306
307 // Free this block
308
309 if (block->user != NULL)
310 {
311 *block->user = NULL;
312 }
313
314 free(block);
315
316 // Jump to the next in the chain
317
318 block = next;
319 }
320
321 // This chain is empty now
322
323 allocated_blocks[i] = NULL;
324 }
325 }
326
327
328
329 //
330 // Z_DumpHeap
331 //
Z_DumpHeap(int lowtag,int hightag)332 void Z_DumpHeap(int lowtag, int hightag)
333 {
334 // broken
335
336 #if 0
337 memblock_t* block;
338
339 printf ("zone size: %i location: %p\n",
340 mainzone->size,mainzone);
341
342 printf ("tag range: %i to %i\n",
343 lowtag, hightag);
344
345 for (block = mainzone->blocklist.next ; ; block = block->next)
346 {
347 if (block->tag >= lowtag && block->tag <= hightag)
348 printf ("block:%p size:%7i user:%p tag:%3i\n",
349 block, block->size, block->user, block->tag);
350
351 if (block->next == &mainzone->blocklist)
352 {
353 // all blocks have been hit
354 break;
355 }
356
357 if ( (byte *)block + block->size != (byte *)block->next)
358 printf ("ERROR: block size does not touch the next block\n");
359
360 if ( block->next->prev != block)
361 printf ("ERROR: next block doesn't have proper back link\n");
362
363 if (block->tag == PU_FREE && block->next->tag == PU_FREE)
364 printf ("ERROR: two consecutive free blocks\n");
365 }
366 #endif
367 }
368
369
370 //
371 // Z_FileDumpHeap
372 //
Z_FileDumpHeap(FILE * f)373 void Z_FileDumpHeap(FILE *f)
374 {
375 // broken
376 #if 0
377 memblock_t* block;
378
379 fprintf (f,"zone size: %i location: %p\n",mainzone->size,mainzone);
380
381 for (block = mainzone->blocklist.next ; ; block = block->next)
382 {
383 fprintf (f,"block:%p size:%7i user:%p tag:%3i\n",
384 block, block->size, block->user, block->tag);
385
386 if (block->next == &mainzone->blocklist)
387 {
388 // all blocks have been hit
389 break;
390 }
391
392 if ( (byte *)block + block->size != (byte *)block->next)
393 fprintf (f,"ERROR: block size does not touch the next block\n");
394
395 if ( block->next->prev != block)
396 fprintf (f,"ERROR: next block doesn't have proper back link\n");
397
398 if (block->tag == PU_FREE && block->next->tag == PU_FREE)
399 fprintf (f,"ERROR: two consecutive free blocks\n");
400 }
401 #endif
402 }
403
404
405
406 //
407 // Z_CheckHeap
408 //
Z_CheckHeap(void)409 void Z_CheckHeap (void)
410 {
411 memblock_t *block;
412 memblock_t *prev;
413 int i;
414
415 // Check all chains
416
417 for (i=0; i<PU_NUM_TAGS; ++i)
418 {
419 prev = NULL;
420
421 for (block=allocated_blocks[i]; block != NULL; block = block->next)
422 {
423 if (block->id != ZONEID)
424 {
425 I_Error("Z_CheckHeap: Block without a ZONEID!");
426 }
427
428 if (block->prev != prev)
429 {
430 I_Error("Z_CheckHeap: Doubly-linked list corrupted!");
431 }
432
433 prev = block;
434 }
435 }
436 }
437
438
439
440
441 //
442 // Z_ChangeTag
443 //
444
Z_ChangeTag2(void * ptr,int tag,const char * file,int line)445 void Z_ChangeTag2(void *ptr, int tag, const char *file, int line)
446 {
447 memblock_t* block;
448
449 block = (memblock_t *) ((byte *)ptr - sizeof(memblock_t));
450
451 if (block->id != ZONEID)
452 I_Error("%s:%i: Z_ChangeTag: block without a ZONEID!",
453 file, line);
454
455 if (tag >= PU_PURGELEVEL && block->user == NULL)
456 I_Error("%s:%i: Z_ChangeTag: an owner is required "
457 "for purgable blocks", file, line);
458
459 // Remove the block from its current list, and rehook it into
460 // its new list.
461
462 Z_RemoveBlock(block);
463 block->tag = tag;
464 Z_InsertBlock(block);
465 }
466
Z_ChangeUser(void * ptr,void ** user)467 void Z_ChangeUser(void *ptr, void **user)
468 {
469 memblock_t* block;
470
471 block = (memblock_t *) ((byte *)ptr - sizeof(memblock_t));
472
473 if (block->id != ZONEID)
474 {
475 I_Error("Z_ChangeUser: Tried to change user for invalid block!");
476 }
477
478 block->user = user;
479 *user = ptr;
480 }
481
482
483 //
484 // Z_FreeMemory
485 //
486
Z_FreeMemory(void)487 int Z_FreeMemory(void)
488 {
489 // Limited by the system??
490
491 return -1;
492 }
493
Z_ZoneSize(void)494 unsigned int Z_ZoneSize(void)
495 {
496 return 0;
497 }
498
499