FS#8961 - Anti-Aliased Fonts.
[kugel-rb.git] / apps / plugins / doom / z_zone.c
blob1d0ac5b7c8f6c9965c64892f6c385170039c8ea0
1 /* Emacs style mode select -*- C++ -*-
2 *-----------------------------------------------------------------------------
5 * PrBoom a Doom port merged with LxDoom and LSDLDoom
6 * based on BOOM, a modified and improved DOOM engine
7 * Copyright (C) 1999 by
8 * id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
9 * Copyright (C) 1999-2000 by
10 * Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
25 * 02111-1307, USA.
27 * DESCRIPTION:
28 * Zone Memory Allocation. Neat.
30 * Neat enough to be rewritten by Lee Killough...
32 * Must not have been real neat :)
34 * Made faster and more general, and added wrappers for all of Doom's
35 * memory allocation functions, including malloc() and similar functions.
36 * Added line and file numbers, in case of error. Added performance
37 * statistics and tunables.
38 *-----------------------------------------------------------------------------
41 #include "z_zone.h"
42 #include "z_bmalloc.h"
43 #include "doomdef.h"
44 #include "i_system.h"
45 #include "rockmacros.h"
46 #include "m_argv.h"
48 // Tunables
50 // Alignment of zone memory (benefit may be negated by HEADER_SIZE, CHUNK_SIZE)
51 #define CACHE_ALIGN 32
53 // Minimum chunk size at which blocks are allocated
54 #define CHUNK_SIZE 32
56 // Minimum size a block must be to become part of a split
57 #define MIN_BLOCK_SPLIT (1024)
59 // Minimum RAM machine is assumed to have
60 /* cph - Select zone size. 6megs is usable, but with the SDL version
61 * storing sounds in the zone, 8 is more sensible */
62 #define MIN_RAM (8*1024*1024)
64 // Amount to subtract when retrying failed attempts to allocate initial pool
65 #define RETRY_AMOUNT (256*1024)
67 // signature for block header
68 #define ZONEID 0x931d4a11
70 // Number of mallocs & frees kept in history buffer (must be a power of 2)
71 #define ZONE_HISTORY 4
73 // End Tunables
75 typedef struct memblock {
77 #ifdef ZONEIDCHECK
78 unsigned id;
79 #endif
81 struct memblock *next,*prev;
82 size_t size;
83 void **user;
84 unsigned char tag,vm;
86 #ifdef INSTRUMENTED
87 unsigned short extra;
88 const char *file;
89 int line;
90 #endif
92 } memblock_t;
94 /* size of block header
95 * cph - base on sizeof(memblock_t), which can be larger than CHUNK_SIZE on
96 * 64bit architectures */
97 static const size_t HEADER_SIZE IDATA_ATTR= (sizeof(memblock_t)+CHUNK_SIZE-1) & ~(CHUNK_SIZE-1);
99 static memblock_t *rover IBSS_ATTR; // roving pointer to memory blocks
100 static memblock_t *zone IBSS_ATTR; // pointer to first block
101 static memblock_t *zonebase IBSS_ATTR; // pointer to entire zone memory
102 static size_t zonebase_size IBSS_ATTR; // zone memory allocated size
104 #ifdef INSTRUMENTED
106 // statistics for evaluating performance
107 static size_t free_memory;
108 static size_t active_memory;
109 static size_t purgable_memory;
110 static size_t inactive_memory;
111 static size_t virtual_memory;
113 static void Z_PrintStats(void) // Print allocation statistics
115 unsigned long total_memory = free_memory + active_memory +
116 purgable_memory + inactive_memory +
117 virtual_memory;
118 // double s = 100.0 / total_memory;
119 int s = 100/total_memory;
121 doom_printf("%-5u\t%6.01f%%\tstatic\n"
122 "%-5u\t%6.01f%%\tpurgable\n"
123 "%-5u\t%6.01f%%\tfree\n"
124 "%-5u\t%6.01f%%\tfragmentary\n"
125 "%-5u\t%6.01f%%\tvirtual\n"
126 "%-5lu\t\ttotal\n",
127 active_memory,
128 active_memory*s,
129 purgable_memory,
130 purgable_memory*s,
131 free_memory,
132 free_memory*s,
133 inactive_memory,
134 inactive_memory*s,
135 virtual_memory,
136 virtual_memory*s,
137 total_memory
141 #ifdef HEAPDUMP
142 void W_PrintLump(FILE* fp, void* p);
144 void Z_DumpMemory(void)
146 static int dump;
147 memblock_t* block = zone;
148 char buf[80];
149 FILE* fp;
150 size_t total_cache = 0, total_free = 0, total_malloc = 0;
152 sprintf(buf, "memdump.%d", dump++);
153 fp = fopen(buf, "w");
154 do {
155 switch (block->tag) {
156 case PU_FREE:
157 fprintf(fp, "free %d\n", block->size);
158 total_free += block->size;
159 break;
160 case PU_CACHE:
161 fprintf(fp, "cache %s:%d:%d\n", block->file, block->line, block->size);
162 total_cache += block->size;
163 break;
164 case PU_LEVEL:
165 fprintf(fp, "level %s:%d:%d\n", block->file, block->line, block->size);
166 total_malloc += block->size;
167 break;
168 default:
169 fprintf(fp, "malloc %s:%d:%d", block->file, block->line, block->size);
170 total_malloc += block->size;
171 if (!strcmp(block->file,"w_wad.c")) W_PrintLump(fp, (char*)block + HEADER_SIZE);
172 fputc('\n', fp);
173 break;
175 block=block->next;
176 } while (block != zone);
177 fprintf(fp, "malloc %d, cache %d, free %d, total %d\n",
178 total_malloc, total_cache, total_free,
179 total_malloc + total_cache + total_free);
180 fclose(fp);
182 #endif
183 #endif
185 #ifdef INSTRUMENTED
187 // killough 4/26/98: Add history information
189 enum {malloc_history, free_history, NUM_HISTORY_TYPES};
191 static const char *file_history[NUM_HISTORY_TYPES][ZONE_HISTORY];
192 static int line_history[NUM_HISTORY_TYPES][ZONE_HISTORY];
193 static int history_index[NUM_HISTORY_TYPES];
194 static const char *const desc[NUM_HISTORY_TYPES] = {"malloc()'s", "free()'s"};
196 void Z_DumpHistory(char *buf)
198 int i,j;
199 char s[1024];
200 strcat(buf,"\n");
201 for (i=0;i<NUM_HISTORY_TYPES;i++)
203 sprintf(s,"\nLast several %s:\n\n", desc[i]);
204 strcat(buf,s);
205 for (j=0; j<ZONE_HISTORY; j++)
207 int k = (history_index[i]-j-1) & (ZONE_HISTORY-1);
208 if (file_history[i][k])
210 sprintf(s, "File: %s, Line: %d\n", file_history[i][k],
211 line_history[i][k]);
212 strcat(buf,s);
217 #else
219 void Z_DumpHistory(char *buf)
221 (void)buf;
224 #endif
226 void Z_Close(void)
228 // (free)(zonebase);
229 zone = rover = zonebase = NULL;
232 void Z_Init(void)
234 size_t size;
235 #ifdef INSTRUMENTED
236 if (!(HEADER_SIZE >= sizeof(memblock_t) && MIN_RAM > LEAVE_ASIDE))
237 I_Error("Z_Init: Sanity check failed");
238 #endif
240 // atexit(Z_Close); // exit handler
242 // Allocate the memory
244 zonebase=rb->plugin_get_audio_buffer(&size);
245 size-=2*(HEADER_SIZE + CACHE_ALIGN); // Leave space for header and CACHE_ALIGN
246 size = (size+CHUNK_SIZE-1) & ~(CHUNK_SIZE-1); // round to chunk size
247 size += HEADER_SIZE + CACHE_ALIGN;
249 zonebase_size=size;
251 printf("Z_Init: Allocated %dKb zone memory\n", (long unsigned)size >> 10);
253 // Align on cache boundary
255 zone = (memblock_t *) ((unsigned long)zonebase + CACHE_ALIGN -
256 ((unsigned long)zonebase & (CACHE_ALIGN-1)));
258 rover = zone; // Rover points to base of zone mem
259 zone->next = zone->prev = zone; // Single node
260 zone->size = size; // All memory in one block
261 zone->tag = PU_FREE; // A free block
262 zone->vm = 0;
264 #ifdef ZONEIDCHECK
265 zone->id = 0;
266 #endif
268 #ifdef INSTRUMENTED
269 free_memory = size;
270 inactive_memory = zonebase_size - size;
271 active_memory = purgable_memory = virtual_memory = 0;
272 #endif
275 /* Z_Malloc
276 * You can pass a NULL user if the tag is < PU_PURGELEVEL.
278 * cph - the algorithm here was a very simple first-fit round-robin
279 * one - just keep looping around, freeing everything we can until
280 * we get a large enough space
282 * This has been changed now; we still do the round-robin first-fit,
283 * but we only free the blocks we actually end up using; we don't
284 * free all the stuff we just pass on the way.
287 void *(Z_Malloc)(size_t size, int tag, void **user
288 #ifdef INSTRUMENTED
289 , const char *file, int line
290 #endif
293 register memblock_t *block;
294 memblock_t *start, *first_of_free;
295 register size_t contig_free;
297 #ifdef INSTRUMENTED
298 size_t size_orig = size;
299 #ifdef CHECKHEAP
300 Z_CheckHeap();
301 #endif
303 file_history[malloc_history][history_index[malloc_history]] = file;
304 line_history[malloc_history][history_index[malloc_history]++] = line;
305 history_index[malloc_history] &= ZONE_HISTORY-1;
306 #endif
308 #ifdef ZONEIDCHECK
309 if (tag >= PU_PURGELEVEL && !user)
310 I_Error ("Z_Malloc: An owner is required for purgable blocks"
311 #ifdef INSTRUMENTED
312 "Source: %s:%d", file, line
313 #endif
315 #endif
317 if (!size)
318 return user ? *user = NULL : NULL; // malloc(0) returns NULL
320 size = (size+CHUNK_SIZE-1) & ~(CHUNK_SIZE-1); // round to chunk size
322 block = rover;
324 if (block->prev->tag == PU_FREE)
325 block = block->prev;
327 start = block;
328 first_of_free = NULL; contig_free = 0;
330 do {
331 /* If we just wrapped, we're not contiguous with the previous block */
332 if (block == zone) contig_free = 0;
334 if (block->tag < PU_PURGELEVEL && block->tag != PU_FREE) {
335 /* Not free(able), so no free space here */
336 contig_free = 0;
337 } else {
338 /* Add to contiguous chunk of free space */
339 if (!contig_free) first_of_free = block;
340 contig_free += block->size;
342 /* First fit */
343 if (contig_free >= size)
344 break;
347 while ((block = block->next) != start); // detect cycles as failure
349 if (contig_free >= size) {
350 /* We have a block of free(able) memory on the heap which will suffice */
351 block = first_of_free;
353 /* If the previous block is adjacent and free, step back and include it */
354 if (block != zone && block->prev->tag == PU_FREE)
355 block = block->prev;
357 /* Free current block if needed */
358 if (block->tag != PU_FREE) Z_Free((char *) block + HEADER_SIZE);
360 /* Note: guaranteed that block->prev is either
361 * not free or not contiguous
363 * At every step, block->next must be not free, else it would
364 * have been merged with our block
365 * No range check needed because we know it works by the previous loop */
366 while (block->size < size)
367 Z_Free((char *)(block->next) + HEADER_SIZE);
369 /* Now, carve up the block */
371 size_t extra = block->size - size;
372 if (extra >= MIN_BLOCK_SPLIT + HEADER_SIZE) {
373 memblock_t *newb = (memblock_t *)((char *) block +
374 HEADER_SIZE + size);
376 (newb->next = block->next)->prev = newb;
377 (newb->prev = block)->next = newb; // Split up block
378 block->size = size;
379 newb->size = extra - HEADER_SIZE;
380 newb->tag = PU_FREE;
381 newb->vm = 0;
383 #ifdef INSTRUMENTED
384 inactive_memory += HEADER_SIZE;
385 free_memory -= HEADER_SIZE;
386 #endif
389 rover = block->next; // set roving pointer for next search
391 #ifdef INSTRUMENTED
392 inactive_memory += block->extra = block->size - size_orig;
393 if (tag >= PU_PURGELEVEL)
394 purgable_memory += size_orig;
395 else
396 active_memory += size_orig;
397 free_memory -= block->size;
398 #endif
400 } else { // We don't have enough contiguous free blocks
401 I_Error ("Z_Malloc: Failure trying to allocate %d bytes",(unsigned long) size);
402 rb->sleep(300);
405 #ifdef INSTRUMENTED
406 block->file = file;
407 block->line = line;
408 #endif
410 #ifdef ZONEIDCHECK
411 block->id = ZONEID; // signature required in block header
412 #endif
413 block->tag = tag; // tag
414 block->user = user; // user
415 block = (memblock_t *)((char *) block + HEADER_SIZE);
416 if (user) // if there is a user
417 *user = block; // set user to point to new block
419 #ifdef INSTRUMENTED
420 Z_PrintStats(); // print memory allocation stats
421 // scramble memory -- weed out any bugs
422 memset(block, gametic & 0xff, size);
423 #endif
424 return block;
427 void (Z_Free)(void *p
428 #ifdef INSTRUMENTED
429 , const char *file, int line
430 #endif
433 #ifdef INSTRUMENTED
434 #ifdef CHECKHEAP
435 Z_CheckHeap();
436 #endif
437 file_history[free_history][history_index[free_history]] = file;
438 line_history[free_history][history_index[free_history]++] = line;
439 history_index[free_history] &= ZONE_HISTORY-1;
440 #endif
442 if (p)
444 memblock_t *other, *block = (memblock_t *)((char *) p - HEADER_SIZE);
446 #ifdef ZONEIDCHECK
447 if (block->id != ZONEID)
448 I_Error("Z_Free: freed a pointer without ZONEID"
449 #ifdef INSTRUMENTED
450 "\nSource: %s:%d"
451 "\nSource of malloc: %s:%d"
452 , file, line, block->file, block->line
453 #endif
455 block->id = 0; // Nullify id so another free fails
456 #endif
458 #ifdef INSTRUMENTED
459 /* scramble memory -- weed out any bugs */
460 memset(p, gametic & 0xff, block->size);
461 #endif
463 if (block->user) // Nullify user if one exists
464 *block->user = NULL;
468 #ifdef INSTRUMENTED
469 free_memory += block->size;
470 inactive_memory -= block->extra;
471 if (block->tag >= PU_PURGELEVEL)
472 purgable_memory -= block->size - block->extra;
473 else
474 active_memory -= block->size - block->extra;
475 #endif
477 block->tag = PU_FREE; // Mark block freed
479 if (block != zone)
481 other = block->prev; // Possibly merge with previous block
482 if (other->tag == PU_FREE)
484 if (rover == block) // Move back rover if it points at block
485 rover = other;
486 (other->next = block->next)->prev = other;
487 other->size += block->size + HEADER_SIZE;
488 block = other;
490 #ifdef INSTRUMENTED
491 inactive_memory -= HEADER_SIZE;
492 free_memory += HEADER_SIZE;
493 #endif
497 other = block->next; // Possibly merge with next block
498 if (other->tag == PU_FREE && other != zone)
500 if (rover == other) // Move back rover if it points at next block
501 rover = block;
502 (block->next = other->next)->prev = block;
503 block->size += other->size + HEADER_SIZE;
505 #ifdef INSTRUMENTED
506 inactive_memory -= HEADER_SIZE;
507 free_memory += HEADER_SIZE;
508 #endif
512 #ifdef INSTRUMENTED
513 Z_PrintStats(); // print memory allocation stats
514 #endif
518 void (Z_FreeTags)(int lowtag, int hightag
519 #ifdef INSTRUMENTED
520 , const char *file, int line
521 #endif
524 /* cph - move rover to start of zone; we like to encourage static
525 * data to stay in one place, at the start of the heap
527 memblock_t *block = rover = zone;
529 #ifdef HEAPDUMP
530 Z_DumpMemory();
531 #endif
533 if (lowtag <= PU_FREE)
534 lowtag = PU_FREE+1;
536 do // Scan through list, searching for tags in range
537 if (block->tag >= lowtag && block->tag <= hightag)
539 memblock_t *prev = block->prev, *cur = block;
540 #ifdef INSTRUMENTED
541 (Z_Free)((char *) block + HEADER_SIZE, file, line);
542 #else
543 (Z_Free)((char *) block + HEADER_SIZE);
544 #endif
545 /* cph - be more careful here, we were skipping blocks!
546 * If the current block was not merged with the previous,
547 * cur is still a valid pointer, prev->next == cur, and cur is
548 * already free so skip to the next.
549 * If the current block was merged with the previous,
550 * the next block to analyse is prev->next.
551 * Note that the while() below does the actual step forward
553 block = (prev->next == cur) ? cur : prev;
555 while ((block=block->next) != zone);
558 void (Z_ChangeTag)(void *ptr, int tag
559 #ifdef INSTRUMENTED
560 , const char *file, int line
561 #endif
564 memblock_t *block = (memblock_t *)((char *) ptr - HEADER_SIZE);
566 #ifdef INSTRUMENTED
567 #ifdef CHECKHEAP
568 Z_CheckHeap();
569 #endif
570 #endif
572 #ifdef ZONEIDCHECK
573 if (block->id != ZONEID)
574 I_Error ("Z_ChangeTag: freed a pointer without ZONEID"
575 #ifdef INSTRUMENTED
576 "\nSource: %s:%d"
577 "\nSource of malloc: %s:%d"
578 , file, line, block->file, block->line
579 #endif
582 if (tag >= PU_PURGELEVEL && !block->user)
583 I_Error ("Z_ChangeTag: an owner is required for purgable blocks\n"
584 #ifdef INSTRUMENTED
585 "Source: %s:%d"
586 "\nSource of malloc: %s:%d"
587 , file, line, block->file, block->line
588 #endif
591 #endif // ZONEIDCHECK
594 #ifdef INSTRUMENTED
595 if (block->tag < PU_PURGELEVEL && tag >= PU_PURGELEVEL)
597 active_memory -= block->size - block->extra;
598 purgable_memory += block->size - block->extra;
600 else
601 if (block->tag >= PU_PURGELEVEL && tag < PU_PURGELEVEL)
603 active_memory += block->size - block->extra;
604 purgable_memory -= block->size - block->extra;
606 #endif
608 block->tag = tag;
611 void *(Z_Realloc)(void *ptr, size_t n, int tag, void **user
612 #ifdef INSTRUMENTED
613 , const char *file, int line
614 #endif
617 void *p = (Z_Malloc)(n, tag, user DA(file, line));
618 if (ptr)
620 memblock_t *block = (memblock_t *)((char *) ptr - HEADER_SIZE);
621 memcpy(p, ptr, n <= block->size ? n : block->size);
622 (Z_Free)(ptr DA(file, line));
623 if (user) // in case Z_Free nullified same user
624 *user=p;
626 return p;
629 void *(Z_Calloc)(size_t n1, size_t n2, int tag, void **user
630 #ifdef INSTRUMENTED
631 , const char *file, int line
632 #endif
635 return
636 (n1*=n2) ? memset((Z_Malloc)(n1, tag, user DA(file, line)), 0, n1) : NULL;
639 char *(Z_Strdup)(const char *s, int tag, void **user
640 #ifdef INSTRUMENTED
641 , const char *file, int line
642 #endif
645 return strcpy((Z_Malloc)(strlen(s)+1, tag, user DA(file, line)), s);
648 void (Z_CheckHeap)(
649 #ifdef INSTRUMENTED
650 const char *file, int line
651 #endif
654 memblock_t *block = zone; // Start at base of zone mem
655 do // Consistency check (last node treated special)
656 if ((block->next != zone &&
657 (memblock_t *)((char *) block+HEADER_SIZE+block->size) != block->next)
658 || block->next->prev != block || block->prev->next != block)
659 I_Error("Z_ChkHp: B size %d touch %d\n", block+HEADER_SIZE+block->size, block->next
660 #ifdef INSTRUMENTED
661 "Source: %s:%d"
662 "\nSource of offending block: %s:%d"
663 , file, line, block->file, block->line
664 #endif
666 while ((block=block->next) != zone);