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