base/z_zone.c

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