sys/src/games/doom/z_zone.c

   1 // Emacs style mode select   -*- C++ -*-
   2 //-----------------------------------------------------------------------------
   3 //
   4 // $Id:$
   5 //
   6 // Copyright (C) 1993-1996 by id Software, Inc.
   7 //
   8 // This source is available for distribution and/or modification
   9 // only under the terms of the DOOM Source Code License as
  10 // published by id Software. All rights reserved.
  11 //
  12 // The source is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
  15 // for more details.
  16 //
  17 // $Log:$
  18 //
  19 // DESCRIPTION:
  20 //      Zone Memory Allocation. Neat.
  21 //
  22 //-----------------------------------------------------------------------------
  23
  24 static const char
  25 rcsid[] = "$Id: z_zone.c,v 1.4 1997/02/03 16:47:58 b1 Exp $";
  26
  27 #include "z_zone.h"
  28 #include "i_system.h"
  29 #include "doomdef.h"
  30
  31
  32 //
  33 // ZONE MEMORY ALLOCATION
  34 //
  35 // There is never any space between memblocks,
  36 //  and there will never be two contiguous free memblocks.
  37 // The rover can be left pointing at a non-empty block.
  38 //
  39 // It is of no value to free a cachable block,
  40 //  because it will get overwritten automatically if needed.
  41 //
  42
  43 #define ZONEID  0x1d4a11
  44
  45
  46 typedef struct
  47 {
  48     // total bytes malloced, including header
  49     int         size;
  50
  51     // start / end cap for linked list
  52     memblock_t  blocklist;
  53
  54     memblock_t* rover;
  55
  56 } memzone_t;
  57
  58
  59
  60 memzone_t*      mainzone;
  61
  62
  63
  64 //
  65 // Z_ClearZone
  66 //
  67 void Z_ClearZone (memzone_t* zone)
  68 {
  69     memblock_t*         block;
  70
  71     // set the entire zone to one free block
  72     zone->blocklist.next =
  73         zone->blocklist.prev =
  74         block = (memblock_t *)( (byte *)zone + sizeof(memzone_t) );
  75
  76     zone->blocklist.user = (void *)zone;
  77     zone->blocklist.tag = PU_STATIC;
  78     zone->rover = block;
  79
  80     block->prev = block->next = &zone->blocklist;
  81
  82     // NULL indicates a free block.
  83     block->user = NULL;
  84
  85     block->size = zone->size - sizeof(memzone_t);
  86 }
  87
  88
  89
  90 //
  91 // Z_Init
  92 //
  93 void Z_Init (void)
  94 {
  95     memblock_t* block;
  96     int         size;
  97
  98     mainzone = (memzone_t *)I_ZoneBase (&size);
  99     mainzone->size = size;
 100
 101     // set the entire zone to one free block
 102     mainzone->blocklist.next =
 103         mainzone->blocklist.prev =
 104         block = (memblock_t *)( (byte *)mainzone + sizeof(memzone_t) );
 105
 106     mainzone->blocklist.user = (void *)mainzone;
 107     mainzone->blocklist.tag = PU_STATIC;
 108     mainzone->rover = block;
 109
 110     block->prev = block->next = &mainzone->blocklist;
 111
 112     // NULL indicates a free block.
 113     block->user = NULL;
 114
 115     block->size = mainzone->size - sizeof(memzone_t);
 116 }
 117
 118
 119 //
 120 // Z_Free
 121 //
 122 void Z_Free (void* ptr)
 123 {
 124     memblock_t*         block;
 125     memblock_t*         other;
 126
 127     block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
 128
 129     if (block->id != ZONEID)
 130         I_Error ("Z_Free: freed a pointer without ZONEID");
 131
 132     if (block->user > (void **)0x100)
 133     {
 134         // smaller values are not pointers
 135         // Note: OS-dependend?
 136
 137         // clear the user's mark
 138         *block->user = 0;
 139     }
 140
 141     // mark as free
 142     block->user = NULL;
 143     block->tag = 0;
 144     block->id = 0;
 145
 146     other = block->prev;
 147
 148     if (!other->user)
 149     {
 150         // merge with previous free block
 151         other->size += block->size;
 152         other->next = block->next;
 153         other->next->prev = other;
 154
 155         if (block == mainzone->rover)
 156             mainzone->rover = other;
 157
 158         block = other;
 159     }
 160
 161     other = block->next;
 162     if (!other->user)
 163     {
 164         // merge the next free block onto the end
 165         block->size += other->size;
 166         block->next = other->next;
 167         block->next->prev = block;
 168
 169         if (other == mainzone->rover)
 170             mainzone->rover = block;
 171     }
 172 }
 173
 174
 175
 176 //
 177 // Z_Malloc
 178 // You can pass a NULL user if the tag is < PU_PURGELEVEL.
 179 //
 180 #define MINFRAGMENT             64
 181
 182 void*
 183 Z_Malloc
 184 ( int           size,
 185   int           tag,
 186   void*         user )
 187 {
 188     int         extra;
 189     memblock_t* start;
 190     memblock_t* rover;
 191     memblock_t* newblock;
 192     memblock_t* base;
 193
 194     size = (size + 7) & ~7;
 195
 196     // scan through the block list,
 197     // looking for the first free block
 198     // of sufficient size,
 199     // throwing out any purgable blocks along the way.
 200
 201     // account for size of block header
 202     size += sizeof(memblock_t);
 203
 204     // if there is a free block behind the rover,
 205     //  back up over them
 206     base = mainzone->rover;
 207
 208     if (!base->prev->user)
 209         base = base->prev;
 210
 211     rover = base;
 212     start = base->prev;
 213
 214     do
 215     {
 216         if (rover == start)
 217         {
 218             // scanned all the way around the list
 219             I_Error ("Z_Malloc: failed on allocation of %i bytes", size);
 220         }
 221
 222         if (rover->user)
 223         {
 224             if (rover->tag < PU_PURGELEVEL)
 225             {
 226                 // hit a block that can't be purged,
 227                 //  so move base past it
 228                 base = rover = rover->next;
 229             }
 230             else
 231             {
 232                 // free the rover block (adding the size to base)
 233
 234                 // the rover can be the base block
 235                 base = base->prev;
 236                 Z_Free ((byte *)rover+sizeof(memblock_t));
 237                 base = base->next;
 238                 rover = base->next;
 239             }
 240         }
 241         else
 242             rover = rover->next;
 243     } while (base->user || base->size < size);
 244
 245
 246     // found a block big enough
 247     extra = base->size - size;
 248
 249     if (extra >  MINFRAGMENT)
 250     {
 251         // there will be a free fragment after the allocated block
 252         newblock = (memblock_t *) ((byte *)base + size );
 253         newblock->size = extra;
 254
 255         // NULL indicates free block.
 256         newblock->user = NULL;
 257         newblock->tag = 0;
 258         newblock->prev = base;
 259         newblock->next = base->next;
 260         newblock->next->prev = newblock;
 261
 262         base->next = newblock;
 263         base->size = size;
 264     }
 265
 266     if (user)
 267     {
 268         // mark as an in use block
 269         base->user = user;
 270         *(void **)user = (void *) ((byte *)base + sizeof(memblock_t));
 271     }
 272     else
 273     {
 274         if (tag >= PU_PURGELEVEL)
 275             I_Error ("Z_Malloc: an owner is required for purgable blocks");
 276
 277         // mark as in use, but unowned
 278         base->user = (void *)2;
 279     }
 280     base->tag = tag;
 281
 282     // next allocation will start looking here
 283     mainzone->rover = base->next;
 284
 285     base->id = ZONEID;
 286
 287     return (void *) ((byte *)base + sizeof(memblock_t));
 288 }
 289
 290
 291
 292 //
 293 // Z_FreeTags
 294 //
 295 void
 296 Z_FreeTags
 297 ( int           lowtag,
 298   int           hightag )
 299 {
 300     memblock_t* block;
 301     memblock_t* next;
 302
 303     for (block = mainzone->blocklist.next ;
 304          block != &mainzone->blocklist ;
 305          block = next)
 306     {
 307         // get link before freeing
 308         next = block->next;
 309
 310         // free block?
 311         if (!block->user)
 312             continue;
 313
 314         if (block->tag >= lowtag && block->tag <= hightag)
 315             Z_Free ( (byte *)block+sizeof(memblock_t));
 316     }
 317 }
 318
 319
 320
 321 //
 322 // Z_DumpHeap
 323 // Note: TFileDumpHeap( stdout ) ?
 324 //
 325 void
 326 Z_DumpHeap
 327 ( int           lowtag,
 328   int           hightag )
 329 {
 330     memblock_t* block;
 331
 332     printf ("zone size: %i  location: %p\n",
 333             mainzone->size,mainzone);
 334
 335     printf ("tag range: %i to %i\n",
 336             lowtag, hightag);
 337
 338     for (block = mainzone->blocklist.next ; ; block = block->next)
 339     {
 340         if (block->tag >= lowtag && block->tag <= hightag)
 341             printf ("block:%p    size:%7i    user:%p    tag:%3i\n",
 342                     block, block->size, block->user, block->tag);
 343
 344         if (block->next == &mainzone->blocklist)
 345         {
 346             // all blocks have been hit
 347             break;
 348         }
 349
 350         if ( (byte *)block + block->size != (byte *)block->next)
 351             printf ("ERROR: block size does not touch the next block\n");
 352
 353         if ( block->next->prev != block)
 354             printf ("ERROR: next block doesn't have proper back link\n");
 355
 356         if (!block->user && !block->next->user)
 357             printf ("ERROR: two consecutive free blocks\n");
 358     }
 359 }
 360
 361
 362 //
 363 // Z_FileDumpHeap
 364 //
 365 void Z_FileDumpHeap (FILE* f)
 366 {
 367     memblock_t* block;
 368
 369     fprintf (f,"zone size: %i  location: %p\n",mainzone->size,mainzone);
 370
 371     for (block = mainzone->blocklist.next ; ; block = block->next)
 372     {
 373         fprintf (f,"block:%p    size:%7i    user:%p    tag:%3i\n",
 374                  block, block->size, block->user, block->tag);
 375
 376         if (block->next == &mainzone->blocklist)
 377         {
 378             // all blocks have been hit
 379             break;
 380         }
 381
 382         if ( (byte *)block + block->size != (byte *)block->next)
 383             fprintf (f,"ERROR: block size does not touch the next block\n");
 384
 385         if ( block->next->prev != block)
 386             fprintf (f,"ERROR: next block doesn't have proper back link\n");
 387
 388         if (!block->user && !block->next->user)
 389             fprintf (f,"ERROR: two consecutive free blocks\n");
 390     }
 391 }
 392
 393
 394
 395 //
 396 // Z_CheckHeap
 397 //
 398 void Z_CheckHeap (void)
 399 {
 400     memblock_t* block;
 401
 402     for (block = mainzone->blocklist.next ; ; block = block->next)
 403     {
 404         if (block->next == &mainzone->blocklist)
 405         {
 406             // all blocks have been hit
 407             break;
 408         }
 409
 410         if ( (byte *)block + block->size != (byte *)block->next)
 411             I_Error ("Z_CheckHeap: block size does not touch the next block\n");
 412
 413         if ( block->next->prev != block)
 414             I_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
 415
 416         if (!block->user && !block->next->user)
 417             I_Error ("Z_CheckHeap: two consecutive free blocks\n");
 418     }
 419 }
 420
 421
 422
 423
 424 //
 425 // Z_ChangeTag
 426 //
 427 void
 428 Z_ChangeTag2
 429 ( void*         ptr,
 430   int           tag )
 431 {
 432     memblock_t* block;
 433
 434     block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
 435
 436     if (block->id != ZONEID)
 437         I_Error ("Z_ChangeTag: freed a pointer without ZONEID");
 438
 439     if (tag >= PU_PURGELEVEL && (uintptr)block->user < 0x100)
 440         I_Error ("Z_ChangeTag: an owner is required for purgable blocks");
 441
 442     block->tag = tag;
 443 }
 444
 445
 446
 447 //
 448 // Z_FreeMemory
 449 //
 450 int Z_FreeMemory (void)
 451 {
 452     memblock_t*         block;
 453     int                 free;
 454
 455     free = 0;
 456
 457     for (block = mainzone->blocklist.next ;
 458          block != &mainzone->blocklist;
 459          block = block->next)
 460     {
 461         if (!block->user || block->tag >= PU_PURGELEVEL)
 462             free += block->size;
 463     }
 464     return free;
 465 }
 466