base/z_zone.c

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