apps/plugins/doom/z_zone.c

   1 /* Emacs style mode select   -*- C++ -*-
   2  *-----------------------------------------------------------------------------
   3  *
   4  *
   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
  11  *
  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.
  16  *
  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.
  21  *
  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.
  26  *
  27  * DESCRIPTION:
  28  *      Zone Memory Allocation. Neat.
  29  *
  30  * Neat enough to be rewritten by Lee Killough...
  31  *
  32  * Must not have been real neat :)
  33  *
  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  *-----------------------------------------------------------------------------
  39  */
  40
  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"
  47
  48 // Tunables
  49
  50 // Alignment of zone memory (benefit may be negated by HEADER_SIZE, CHUNK_SIZE)
  51 #define CACHE_ALIGN 32
  52
  53 // Minimum chunk size at which blocks are allocated
  54 #define CHUNK_SIZE 32
  55
  56 // Minimum size a block must be to become part of a split
  57 #define MIN_BLOCK_SPLIT (1024)
  58
  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)
  63
  64 // Amount to subtract when retrying failed attempts to allocate initial pool
  65 #define RETRY_AMOUNT (256*1024)
  66
  67 // signature for block header
  68 #define ZONEID  0x931d4a11
  69
  70 // Number of mallocs & frees kept in history buffer (must be a power of 2)
  71 #define ZONE_HISTORY 4
  72
  73 // End Tunables
  74
  75 typedef struct memblock {
  76
  77 #ifdef ZONEIDCHECK
  78    unsigned id;
  79 #endif
  80
  81    struct memblock *next,*prev;
  82    size_t size;
  83    void **user;
  84    unsigned char tag,vm;
  85
  86 #ifdef INSTRUMENTED
  87    unsigned short extra;
  88    const char *file;
  89    int line;
  90 #endif
  91
  92 } memblock_t;
  93
  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);
  98
  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
 103
 104 #ifdef INSTRUMENTED
 105
 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;
 112
 113 static void Z_PrintStats(void)            // Print allocation statistics
 114 {
 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;
 120
 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
 138               );
 139 }
 140
 141 #ifdef HEAPDUMP
 142 void W_PrintLump(FILE* fp, void* p);
 143
 144 void Z_DumpMemory(void)
 145 {
 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;
 151
 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;
 174       }
 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);
 181 }
 182 #endif
 183 #endif
 184
 185 #ifdef INSTRUMENTED
 186
 187 // killough 4/26/98: Add history information
 188
 189 enum {malloc_history, free_history, NUM_HISTORY_TYPES};
 190
 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"};
 195
 196 void Z_DumpHistory(char *buf)
 197 {
 198    int i,j;
 199    char s[1024];
 200    strcat(buf,"\n");
 201    for (i=0;i<NUM_HISTORY_TYPES;i++)
 202    {
 203       sprintf(s,"\nLast several %s:\n\n", desc[i]);
 204       strcat(buf,s);
 205       for (j=0; j<ZONE_HISTORY; j++)
 206       {
 207          int k = (history_index[i]-j-1) & (ZONE_HISTORY-1);
 208          if (file_history[i][k])
 209          {
 210             sprintf(s, "File: %s, Line: %d\n", file_history[i][k],
 211                     line_history[i][k]);
 212             strcat(buf,s);
 213          }
 214       }
 215    }
 216 }
 217 #else
 218
 219 void Z_DumpHistory(char *buf)
 220 {
 221    (void)buf;
 222 }
 223
 224 #endif
 225
 226 void Z_Close(void)
 227 {
 228 //   (free)(zonebase);
 229    zone = rover = zonebase = NULL;
 230 }
 231
 232 void Z_Init(void)
 233 {
 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
 239
 240 //   atexit(Z_Close);            // exit handler
 241
 242    // Allocate the memory
 243
 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;
 248
 249    zonebase_size=size;
 250
 251    printf("Z_Init: Allocated %dKb zone memory\n", (long unsigned)size >> 10);
 252
 253    // Align on cache boundary
 254
 255    zone = (memblock_t *) ((unsigned long)zonebase + CACHE_ALIGN -
 256                          ((unsigned long)zonebase & (CACHE_ALIGN-1)));
 257
 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;
 263
 264 #ifdef ZONEIDCHECK
 265    zone->id  = 0;
 266 #endif
 267
 268 #ifdef INSTRUMENTED
 269    free_memory = size;
 270    inactive_memory = zonebase_size - size;
 271    active_memory = purgable_memory = virtual_memory = 0;
 272 #endif
 273 }
 274
 275 /* Z_Malloc
 276  * You can pass a NULL user if the tag is < PU_PURGELEVEL.
 277  *
 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
 281  *
 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.
 285  */
 286
 287 void *(Z_Malloc)(size_t size, int tag, void **user
 288 #ifdef INSTRUMENTED
 289                  , const char *file, int line
 290 #endif
 291                 )
 292 {
 293    register memblock_t *block;
 294    memblock_t *start, *first_of_free;
 295    register size_t contig_free;
 296
 297 #ifdef INSTRUMENTED
 298    size_t size_orig = size;
 299 #ifdef CHECKHEAP
 300    Z_CheckHeap();
 301 #endif
 302
 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
 307
 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
 314               );
 315 #endif
 316
 317    if (!size)
 318       return user ? *user = NULL : NULL;           // malloc(0) returns NULL
 319
 320    size = (size+CHUNK_SIZE-1) & ~(CHUNK_SIZE-1);  // round to chunk size
 321
 322    block = rover;
 323
 324    if (block->prev->tag == PU_FREE)
 325       block = block->prev;
 326
 327    start = block;
 328    first_of_free = NULL; contig_free = 0;
 329
 330    do {
 331       /* If we just wrapped, we're not contiguous with the previous block */
 332       if (block == zone) contig_free = 0;
 333
 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;
 341
 342          /* First fit */
 343          if (contig_free >= size)
 344             break;
 345       }
 346    }
 347    while ((block = block->next) != start);   // detect cycles as failure
 348
 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;
 352
 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;
 356
 357       /* Free current block if needed */
 358       if (block->tag != PU_FREE) Z_Free((char *) block + HEADER_SIZE);
 359
 360       /* Note: guaranteed that block->prev is either
 361        * not free or not contiguous
 362        *
 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);
 368
 369       /* Now, carve up the block */
 370       {
 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);
 375
 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;
 382
 383 #ifdef INSTRUMENTED
 384             inactive_memory += HEADER_SIZE;
 385             free_memory -= HEADER_SIZE;
 386 #endif
 387          }
 388
 389          rover = block->next;           // set roving pointer for next search
 390
 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
 399       }
 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);
 403    }
 404
 405 #ifdef INSTRUMENTED
 406    block->file = file;
 407    block->line = line;
 408 #endif
 409
 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
 418
 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;
 425 }
 426
 427 void (Z_Free)(void *p
 428 #ifdef INSTRUMENTED
 429               , const char *file, int line
 430 #endif
 431              )
 432 {
 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
 441
 442    if (p)
 443    {
 444       memblock_t *other, *block = (memblock_t *)((char *) p - HEADER_SIZE);
 445
 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
 454                 );
 455       block->id = 0;              // Nullify id so another free fails
 456 #endif
 457
 458 #ifdef INSTRUMENTED
 459       /* scramble memory -- weed out any bugs */
 460       memset(p, gametic & 0xff, block->size);
 461 #endif
 462
 463       if (block->user)            // Nullify user if one exists
 464          *block->user = NULL;
 465
 466       {
 467
 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
 476
 477          block->tag = PU_FREE;       // Mark block freed
 478
 479          if (block != zone)
 480          {
 481             other = block->prev;        // Possibly merge with previous block
 482             if (other->tag == PU_FREE)
 483             {
 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;
 489
 490 #ifdef INSTRUMENTED
 491                inactive_memory -= HEADER_SIZE;
 492                free_memory += HEADER_SIZE;
 493 #endif
 494             }
 495          }
 496
 497          other = block->next;        // Possibly merge with next block
 498          if (other->tag == PU_FREE && other != zone)
 499          {
 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;
 504
 505 #ifdef INSTRUMENTED
 506             inactive_memory -= HEADER_SIZE;
 507             free_memory += HEADER_SIZE;
 508 #endif
 509          }
 510       }
 511
 512 #ifdef INSTRUMENTED
 513       Z_PrintStats();           // print memory allocation stats
 514 #endif
 515    }
 516 }
 517
 518 void (Z_FreeTags)(int lowtag, int hightag
 519 #ifdef INSTRUMENTED
 520                   , const char *file, int line
 521 #endif
 522                  )
 523 {
 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
 526     */
 527    memblock_t *block = rover = zone;
 528
 529 #ifdef HEAPDUMP
 530    Z_DumpMemory();
 531 #endif
 532
 533    if (lowtag <= PU_FREE)
 534       lowtag = PU_FREE+1;
 535
 536    do               // Scan through list, searching for tags in range
 537       if (block->tag >= lowtag && block->tag <= hightag)
 538       {
 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
 552           */
 553          block = (prev->next == cur) ? cur : prev;
 554       }
 555    while ((block=block->next) != zone);
 556 }
 557
 558 void (Z_ChangeTag)(void *ptr, int tag
 559 #ifdef INSTRUMENTED
 560                    , const char *file, int line
 561 #endif
 562                   )
 563 {
 564    memblock_t *block = (memblock_t *)((char *) ptr - HEADER_SIZE);
 565
 566 #ifdef INSTRUMENTED
 567 #ifdef CHECKHEAP
 568    Z_CheckHeap();
 569 #endif
 570 #endif
 571
 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
 580               );
 581
 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
 589               );
 590
 591 #endif // ZONEIDCHECK
 592
 593    {
 594 #ifdef INSTRUMENTED
 595       if (block->tag < PU_PURGELEVEL && tag >= PU_PURGELEVEL)
 596       {
 597          active_memory -= block->size - block->extra;
 598          purgable_memory += block->size - block->extra;
 599       }
 600       else
 601          if (block->tag >= PU_PURGELEVEL && tag < PU_PURGELEVEL)
 602          {
 603             active_memory += block->size - block->extra;
 604             purgable_memory -= block->size - block->extra;
 605          }
 606 #endif
 607    }
 608    block->tag = tag;
 609 }
 610
 611 void *(Z_Realloc)(void *ptr, size_t n, int tag, void **user
 612 #ifdef INSTRUMENTED
 613                   , const char *file, int line
 614 #endif
 615                  )
 616 {
 617    void *p = (Z_Malloc)(n, tag, user DA(file, line));
 618    if (ptr)
 619    {
 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;
 625    }
 626    return p;
 627 }
 628
 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
 633                 )
 634 {
 635    return
 636       (n1*=n2) ? memset((Z_Malloc)(n1, tag, user DA(file, line)), 0, n1) : NULL;
 637 }
 638
 639 char *(Z_Strdup)(const char *s, int tag, void **user
 640 #ifdef INSTRUMENTED
 641                  , const char *file, int line
 642 #endif
 643                 )
 644 {
 645    return strcpy((Z_Malloc)(strlen(s)+1, tag, user DA(file, line)), s);
 646 }
 647
 648 void (Z_CheckHeap)(
 649 #ifdef INSTRUMENTED
 650    const char *file, int line
 651 #endif
 652 )
 653 {
 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
 665                 );
 666    while ((block=block->next) != zone);
 667 }