zone.c

   1 /*
   2 Copyright (C) 1996-1997 Id Software, Inc.
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20 // Z_zone.c
  21
  22 #include "quakedef.h"
  23
  24 #if MEMPARANOIA
  25 #include <stdint.h>
  26 #define MEMHEADER_SENTINEL_FOR_ADDRESS(p) ((sentinel_seed ^ (unsigned int) (uintptr_t) (p)) + sentinel_seed)
  27 unsigned int sentinel_seed;
  28 #else
  29 #define MEMHEADER_SENTINEL1 0xDEADF00D
  30 #define MEMHEADER_SENTINEL2 0xDF
  31 #endif
  32
  33 #if MEMCLUMPING
  34 #define MEMCLUMP_SENTINEL 0xABADCAFE
  35 #endif
  36
  37 cvar_t developer_memory = {0, "developer_memory", "0", "prints debugging information about memory allocations"};
  38 cvar_t developer_memorydebug = {0, "developer_memorydebug", "0", "enables memory corruption checks (very slow)"};
  39
  40 mempool_t *poolchain = NULL;
  41
  42 void *_Mem_Alloc(mempool_t *pool, size_t size, const char *filename, int fileline)
  43 {
  44 #if MEMCLUMPING
  45         int i, j, k, needed, endbit, largest;
  46         memclump_t *clump, **clumpchainpointer;
  47 #endif
  48 #if MEMPARANOIA
  49         unsigned int sentinel2;
  50 #endif
  51         memheader_t *mem;
  52         if (size <= 0)
  53                 return NULL;
  54         if (pool == NULL)
  55                 Sys_Error("Mem_Alloc: pool == NULL (alloc at %s:%i)", filename, fileline);
  56         if (developer.integer && developer_memory.integer)
  57                 Con_Printf("Mem_Alloc: pool %s, file %s:%i, size %i bytes\n", pool->name, filename, fileline, (int)size);
  58         if (developer.integer && developer_memorydebug.integer)
  59                 _Mem_CheckSentinelsGlobal(filename, fileline);
  60         pool->totalsize += size;
  61 #if MEMCLUMPING
  62         if (size < 4096)
  63         {
  64                 // clumping
  65 #if MEMPARANOIA
  66                 needed = (sizeof(memheader_t) + size + sizeof(unsigned int) + (MEMUNIT - 1)) / MEMUNIT;
  67 #else
  68                 needed = (sizeof(memheader_t) + size + sizeof(unsigned char) + (MEMUNIT - 1)) / MEMUNIT;
  69 #endif
  70                 endbit = MEMBITS - needed;
  71                 for (clumpchainpointer = &pool->clumpchain;*clumpchainpointer;clumpchainpointer = &(*clumpchainpointer)->chain)
  72                 {
  73                         clump = *clumpchainpointer;
  74                         if (clump->sentinel1 != MEMCLUMP_SENTINEL)
  75                                 Sys_Error("Mem_Alloc: trashed clump sentinel 1 (alloc at %s:%d)", filename, fileline);
  76                         if (clump->sentinel2 != MEMCLUMP_SENTINEL)
  77                                 Sys_Error("Mem_Alloc: trashed clump sentinel 2 (alloc at %s:%d)", filename, fileline);
  78                         if (clump->largestavailable >= needed)
  79                         {
  80                                 largest = 0;
  81                                 for (i = 0;i < endbit;i++)
  82                                 {
  83                                         if (clump->bits[i >> 5] & (1 << (i & 31)))
  84                                                 continue;
  85                                         k = i + needed;
  86                                         for (j = i;i < k;i++)
  87                                                 if (clump->bits[i >> 5] & (1 << (i & 31)))
  88                                                         goto loopcontinue;
  89                                         goto choseclump;
  90         loopcontinue:;
  91                                         if (largest < j - i)
  92                                                 largest = j - i;
  93                                 }
  94                                 // since clump falsely advertised enough space (nothing wrong
  95                                 // with that), update largest count to avoid wasting time in
  96                                 // later allocations
  97                                 clump->largestavailable = largest;
  98                         }
  99                 }
 100                 pool->realsize += sizeof(memclump_t);
 101                 clump = malloc(sizeof(memclump_t));
 102                 if (clump == NULL)
 103                         Sys_Error("Mem_Alloc: out of memory (alloc at %s:%i)", filename, fileline);
 104                 memset(clump, 0, sizeof(memclump_t));
 105                 *clumpchainpointer = clump;
 106                 clump->sentinel1 = MEMCLUMP_SENTINEL;
 107                 clump->sentinel2 = MEMCLUMP_SENTINEL;
 108                 clump->chain = NULL;
 109                 clump->blocksinuse = 0;
 110                 clump->largestavailable = MEMBITS - needed;
 111                 j = 0;
 112 choseclump:
 113                 mem = (memheader_t *)((unsigned char *) clump->block + j * MEMUNIT);
 114                 mem->clump = clump;
 115                 clump->blocksinuse += needed;
 116                 for (i = j + needed;j < i;j++)
 117                         clump->bits[j >> 5] |= (1 << (j & 31));
 118         }
 119         else
 120         {
 121                 // big allocations are not clumped
 122 #endif
 123 #if MEMPARANOIA
 124                 pool->realsize += sizeof(memheader_t) + size + sizeof(sentinel2);
 125                 mem = (memheader_t *)malloc(sizeof(memheader_t) + size + sizeof(sentinel2));
 126 #else
 127                 pool->realsize += sizeof(memheader_t) + size + 1;
 128                 mem = (memheader_t *)malloc(sizeof(memheader_t) + size + 1);
 129 #endif
 130                 if (mem == NULL)
 131                         Sys_Error("Mem_Alloc: out of memory (alloc at %s:%i)", filename, fileline);
 132 #if MEMCLUMPING
 133                 mem->clump = NULL;
 134         }
 135 #endif
 136         mem->filename = filename;
 137         mem->fileline = fileline;
 138         mem->size = size;
 139         mem->pool = pool;
 140 #if MEMPARANOIA
 141         mem->sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&mem->sentinel1);
 142         sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS((unsigned char *) mem + sizeof(memheader_t) + mem->size);
 143         memcpy((unsigned char *) mem + sizeof(memheader_t) + mem->size, &sentinel2, sizeof(sentinel2));
 144 #else
 145         mem->sentinel1 = MEMHEADER_SENTINEL1;
 146         // we have to use only a single byte for this sentinel, because it may not be aligned, and some platforms can't use unaligned accesses
 147         *((unsigned char *) mem + sizeof(memheader_t) + mem->size) = MEMHEADER_SENTINEL2;
 148 #endif
 149         // append to head of list
 150         mem->next = pool->chain;
 151         mem->prev = NULL;
 152         pool->chain = mem;
 153         if (mem->next)
 154                 mem->next->prev = mem;
 155         memset((void *)((unsigned char *) mem + sizeof(memheader_t)), 0, mem->size);
 156         return (void *)((unsigned char *) mem + sizeof(memheader_t));
 157 }
 158
 159 // only used by _Mem_Free and _Mem_FreePool
 160 static void _Mem_FreeBlock(memheader_t *mem, const char *filename, int fileline)
 161 {
 162 #if MEMCLUMPING
 163         int i, firstblock, endblock;
 164         memclump_t *clump, **clumpchainpointer;
 165 #endif
 166         mempool_t *pool;
 167 #if MEMPARANOIA
 168         unsigned int sentinel2;
 169         if (mem->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&mem->sentinel1))
 170                 Sys_Error("Mem_Free: trashed header sentinel 1 (alloc at %s:%i, free at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 171         sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS((unsigned char *) mem + sizeof(memheader_t) + mem->size);
 172         if (memcmp((unsigned char *) mem + sizeof(memheader_t) + mem->size, &sentinel2, sizeof(sentinel2)))
 173                 Sys_Error("Mem_Free: trashed header sentinel 2 (alloc at %s:%i, free at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 174 #else
 175         if (mem->sentinel1 != MEMHEADER_SENTINEL1)
 176                 Sys_Error("Mem_Free: trashed header sentinel 1 (alloc at %s:%i, free at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 177         if (*((unsigned char *) mem + sizeof(memheader_t) + mem->size) != MEMHEADER_SENTINEL2)
 178                 Sys_Error("Mem_Free: trashed header sentinel 2 (alloc at %s:%i, free at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 179 #endif
 180         pool = mem->pool;
 181         if (developer.integer && developer_memory.integer)
 182                 Con_Printf("Mem_Free: pool %s, alloc %s:%i, free %s:%i, size %i bytes\n", pool->name, mem->filename, mem->fileline, filename, fileline, (int)(mem->size));
 183         // unlink memheader from doubly linked list
 184         if ((mem->prev ? mem->prev->next != mem : pool->chain != mem) || (mem->next && mem->next->prev != mem))
 185                 Sys_Error("Mem_Free: not allocated or double freed (free at %s:%i)", filename, fileline);
 186         if (mem->prev)
 187                 mem->prev->next = mem->next;
 188         else
 189                 pool->chain = mem->next;
 190         if (mem->next)
 191                 mem->next->prev = mem->prev;
 192         // memheader has been unlinked, do the actual free now
 193         pool->totalsize -= mem->size;
 194 #if MEMCLUMPING
 195         if ((clump = mem->clump))
 196         {
 197                 if (clump->sentinel1 != MEMCLUMP_SENTINEL)
 198                         Sys_Error("Mem_Free: trashed clump sentinel 1 (free at %s:%i)", filename, fileline);
 199                 if (clump->sentinel2 != MEMCLUMP_SENTINEL)
 200                         Sys_Error("Mem_Free: trashed clump sentinel 2 (free at %s:%i)", filename, fileline);
 201                 firstblock = ((unsigned char *) mem - (unsigned char *) clump->block);
 202                 if (firstblock & (MEMUNIT - 1))
 203                         Sys_Error("Mem_Free: address not valid in clump (free at %s:%i)", filename, fileline);
 204                 firstblock /= MEMUNIT;
 205                 endblock = firstblock + ((sizeof(memheader_t) + mem->size + sizeof(int) + (MEMUNIT - 1)) / MEMUNIT);
 206                 clump->blocksinuse -= endblock - firstblock;
 207                 // could use &, but we know the bit is set
 208                 for (i = firstblock;i < endblock;i++)
 209                         clump->bits[i >> 5] -= (1 << (i & 31));
 210                 if (clump->blocksinuse <= 0)
 211                 {
 212                         // unlink from chain
 213                         for (clumpchainpointer = &pool->clumpchain;*clumpchainpointer;clumpchainpointer = &(*clumpchainpointer)->chain)
 214                         {
 215                                 if (*clumpchainpointer == clump)
 216                                 {
 217                                         *clumpchainpointer = clump->chain;
 218                                         break;
 219                                 }
 220                         }
 221                         pool->realsize -= sizeof(memclump_t);
 222                         memset(clump, 0xBF, sizeof(memclump_t));
 223                         free(clump);
 224                 }
 225                 else
 226                 {
 227                         // clump still has some allocations
 228                         // force re-check of largest available space on next alloc
 229                         clump->largestavailable = MEMBITS - clump->blocksinuse;
 230                 }
 231         }
 232         else
 233         {
 234 #endif
 235                 pool->realsize -= sizeof(memheader_t) + mem->size + sizeof(int);
 236                 if (developer_memorydebug.integer)
 237                         memset(mem, 0xBF, sizeof(memheader_t) + mem->size + sizeof(int));
 238                 free(mem);
 239 #if MEMCLUMPING
 240         }
 241 #endif
 242 }
 243
 244 void _Mem_Free(void *data, const char *filename, int fileline)
 245 {
 246         if (data == NULL)
 247         {
 248                 Con_DPrintf("Mem_Free: data == NULL (called at %s:%i)", filename, fileline);
 249                 return;
 250         }
 251
 252         if (developer.integer && developer_memorydebug.integer)
 253         {
 254                 _Mem_CheckSentinelsGlobal(filename, fileline);
 255                 if (!Mem_IsAllocated(NULL, data))
 256                         Sys_Error("Mem_Free: data is not allocated (called at %s:%i)", filename, fileline);
 257         }
 258
 259         _Mem_FreeBlock((memheader_t *)((unsigned char *) data - sizeof(memheader_t)), filename, fileline);
 260 }
 261
 262 mempool_t *_Mem_AllocPool(const char *name, int flags, mempool_t *parent, const char *filename, int fileline)
 263 {
 264         mempool_t *pool;
 265         if (developer.integer && developer_memorydebug.integer)
 266                 _Mem_CheckSentinelsGlobal(filename, fileline);
 267         pool = (mempool_t *)malloc(sizeof(mempool_t));
 268         if (pool == NULL)
 269                 Sys_Error("Mem_AllocPool: out of memory (allocpool at %s:%i)", filename, fileline);
 270         memset(pool, 0, sizeof(mempool_t));
 271 #if MEMPARANOIA
 272         pool->sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1);
 273         pool->sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2);
 274 #else
 275         pool->sentinel1 = MEMHEADER_SENTINEL1;
 276         pool->sentinel2 = MEMHEADER_SENTINEL1;
 277 #endif
 278         pool->filename = filename;
 279         pool->fileline = fileline;
 280         pool->flags = flags;
 281         pool->chain = NULL;
 282         pool->totalsize = 0;
 283         pool->realsize = sizeof(mempool_t);
 284         strlcpy (pool->name, name, sizeof (pool->name));
 285         pool->parent = parent;
 286         pool->next = poolchain;
 287         poolchain = pool;
 288         return pool;
 289 }
 290
 291 void _Mem_FreePool(mempool_t **poolpointer, const char *filename, int fileline)
 292 {
 293         mempool_t *pool = *poolpointer;
 294         mempool_t **chainaddress, *iter, *temp;
 295
 296         if (developer.integer && developer_memorydebug.integer)
 297                 _Mem_CheckSentinelsGlobal(filename, fileline);
 298         if (pool)
 299         {
 300                 // unlink pool from chain
 301                 for (chainaddress = &poolchain;*chainaddress && *chainaddress != pool;chainaddress = &((*chainaddress)->next));
 302                 if (*chainaddress != pool)
 303                         Sys_Error("Mem_FreePool: pool already free (freepool at %s:%i)", filename, fileline);
 304 #if MEMPARANOIA
 305                 if (pool->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1))
 306                         Sys_Error("Mem_FreePool: trashed pool sentinel 1 (allocpool at %s:%i, freepool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 307                 if (pool->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2))
 308                         Sys_Error("Mem_FreePool: trashed pool sentinel 2 (allocpool at %s:%i, freepool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 309 #else
 310                 if (pool->sentinel1 != MEMHEADER_SENTINEL1)
 311                         Sys_Error("Mem_FreePool: trashed pool sentinel 1 (allocpool at %s:%i, freepool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 312                 if (pool->sentinel2 != MEMHEADER_SENTINEL1)
 313                         Sys_Error("Mem_FreePool: trashed pool sentinel 2 (allocpool at %s:%i, freepool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 314 #endif
 315                 *chainaddress = pool->next;
 316
 317                 // free memory owned by the pool
 318                 while (pool->chain)
 319                         _Mem_FreeBlock(pool->chain, filename, fileline);
 320
 321                 // free child pools, too
 322                 for(iter = poolchain; iter; temp = iter = iter->next)
 323                         if(iter->parent == pool)
 324                                 _Mem_FreePool(&temp, filename, fileline);
 325
 326                 // free the pool itself
 327                 memset(pool, 0xBF, sizeof(mempool_t));
 328                 free(pool);
 329
 330                 *poolpointer = NULL;
 331         }
 332 }
 333
 334 void _Mem_EmptyPool(mempool_t *pool, const char *filename, int fileline)
 335 {
 336         mempool_t *chainaddress;
 337
 338         if (developer.integer && developer_memorydebug.integer)
 339         {
 340                 _Mem_CheckSentinelsGlobal(filename, fileline);
 341                 // check if this pool is in the poolchain
 342                 for (chainaddress = poolchain;chainaddress;chainaddress = chainaddress->next)
 343                         if (chainaddress == pool)
 344                                 break;
 345                 if (!chainaddress)
 346                         Sys_Error("Mem_EmptyPool: pool is already free (emptypool at %s:%i)", filename, fileline);
 347         }
 348         if (pool == NULL)
 349                 Sys_Error("Mem_EmptyPool: pool == NULL (emptypool at %s:%i)", filename, fileline);
 350 #if MEMPARANOIA
 351         if (pool->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1))
 352                 Sys_Error("Mem_EmptyPool: trashed pool sentinel 2 (allocpool at %s:%i, emptypool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 353         if (pool->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2))
 354                 Sys_Error("Mem_EmptyPool: trashed pool sentinel 1 (allocpool at %s:%i, emptypool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 355 #else
 356         if (pool->sentinel1 != MEMHEADER_SENTINEL1)
 357                 Sys_Error("Mem_EmptyPool: trashed pool sentinel 1 (allocpool at %s:%i, emptypool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 358         if (pool->sentinel2 != MEMHEADER_SENTINEL1)
 359                 Sys_Error("Mem_EmptyPool: trashed pool sentinel 2 (allocpool at %s:%i, emptypool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 360 #endif
 361
 362         // free memory owned by the pool
 363         while (pool->chain)
 364                 _Mem_FreeBlock(pool->chain, filename, fileline);
 365
 366         // empty child pools, too
 367         for(chainaddress = poolchain; chainaddress; chainaddress = chainaddress->next)
 368                 if(chainaddress->parent == pool)
 369                         _Mem_EmptyPool(chainaddress, filename, fileline);
 370
 371 }
 372
 373 void _Mem_CheckSentinels(void *data, const char *filename, int fileline)
 374 {
 375         memheader_t *mem;
 376 #if MEMPARANOIA
 377         unsigned int sentinel2;
 378 #endif
 379
 380         if (data == NULL)
 381                 Sys_Error("Mem_CheckSentinels: data == NULL (sentinel check at %s:%i)", filename, fileline);
 382
 383         mem = (memheader_t *)((unsigned char *) data - sizeof(memheader_t));
 384 #if MEMPARANOIA
 385         if (mem->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&mem->sentinel1))
 386                 Sys_Error("Mem_Free: trashed header sentinel 1 (alloc at %s:%i, sentinel check at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 387         sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS((unsigned char *) mem + sizeof(memheader_t) + mem->size);
 388         if (memcmp((unsigned char *) mem + sizeof(memheader_t) + mem->size, &sentinel2, sizeof(sentinel2)))
 389                 Sys_Error("Mem_Free: trashed header sentinel 2 (alloc at %s:%i, sentinel check at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 390 #else
 391         if (mem->sentinel1 != MEMHEADER_SENTINEL1)
 392                 Sys_Error("Mem_CheckSentinels: trashed header sentinel 1 (block allocated at %s:%i, sentinel check at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 393         if (*((unsigned char *) mem + sizeof(memheader_t) + mem->size) != MEMHEADER_SENTINEL2)
 394                 Sys_Error("Mem_CheckSentinels: trashed header sentinel 2 (block allocated at %s:%i, sentinel check at %s:%i)", mem->filename, mem->fileline, filename, fileline);
 395 #endif
 396 }
 397
 398 #if MEMCLUMPING
 399 static void _Mem_CheckClumpSentinels(memclump_t *clump, const char *filename, int fileline)
 400 {
 401         // this isn't really very useful
 402         if (clump->sentinel1 != MEMCLUMP_SENTINEL)
 403                 Sys_Error("Mem_CheckClumpSentinels: trashed sentinel 1 (sentinel check at %s:%i)", filename, fileline);
 404         if (clump->sentinel2 != MEMCLUMP_SENTINEL)
 405                 Sys_Error("Mem_CheckClumpSentinels: trashed sentinel 2 (sentinel check at %s:%i)", filename, fileline);
 406 }
 407 #endif
 408
 409 void _Mem_CheckSentinelsGlobal(const char *filename, int fileline)
 410 {
 411         memheader_t *mem;
 412 #if MEMCLUMPING
 413         memclump_t *clump;
 414 #endif
 415         mempool_t *pool;
 416         for (pool = poolchain;pool;pool = pool->next)
 417         {
 418 #if MEMPARANOIA
 419                 if (pool->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1))
 420                         Sys_Error("Mem_CheckSentinelsGlobal: trashed pool sentinel 1 (allocpool at %s:%i, sentinel check at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 421                 if (pool->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2))
 422                         Sys_Error("Mem_CheckSentinelsGlobal: trashed pool sentinel 2 (allocpool at %s:%i, sentinel check at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 423 #else
 424                 if (pool->sentinel1 != MEMHEADER_SENTINEL1)
 425                         Sys_Error("Mem_CheckSentinelsGlobal: trashed pool sentinel 1 (allocpool at %s:%i, sentinel check at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 426                 if (pool->sentinel2 != MEMHEADER_SENTINEL1)
 427                         Sys_Error("Mem_CheckSentinelsGlobal: trashed pool sentinel 2 (allocpool at %s:%i, sentinel check at %s:%i)", pool->filename, pool->fileline, filename, fileline);
 428 #endif
 429         }
 430         for (pool = poolchain;pool;pool = pool->next)
 431                 for (mem = pool->chain;mem;mem = mem->next)
 432                         _Mem_CheckSentinels((void *)((unsigned char *) mem + sizeof(memheader_t)), filename, fileline);
 433 #if MEMCLUMPING
 434         for (pool = poolchain;pool;pool = pool->next)
 435                 for (clump = pool->clumpchain;clump;clump = clump->chain)
 436                         _Mem_CheckClumpSentinels(clump, filename, fileline);
 437 #endif
 438 }
 439
 440 qboolean Mem_IsAllocated(mempool_t *pool, void *data)
 441 {
 442         memheader_t *header;
 443         memheader_t *target;
 444
 445         if (pool)
 446         {
 447                 // search only one pool
 448                 target = (memheader_t *)((unsigned char *) data - sizeof(memheader_t));
 449                 for( header = pool->chain ; header ; header = header->next )
 450                         if( header == target )
 451                                 return true;
 452         }
 453         else
 454         {
 455                 // search all pools
 456                 for (pool = poolchain;pool;pool = pool->next)
 457                         if (Mem_IsAllocated(pool, data))
 458                                 return true;
 459         }
 460         return false;
 461 }
 462
 463 void Mem_ExpandableArray_NewArray(memexpandablearray_t *l, mempool_t *mempool, size_t recordsize, int numrecordsperarray)
 464 {
 465         memset(l, 0, sizeof(*l));
 466         l->mempool = mempool;
 467         l->recordsize = recordsize;
 468         l->numrecordsperarray = numrecordsperarray;
 469 }
 470
 471 void Mem_ExpandableArray_FreeArray(memexpandablearray_t *l)
 472 {
 473         size_t i;
 474         if (l->maxarrays)
 475         {
 476                 for (i = 0;i != l->numarrays;i++)
 477                         Mem_Free(l->arrays[i].data);
 478                 Mem_Free(l->arrays);
 479         }
 480         memset(l, 0, sizeof(*l));
 481 }
 482
 483 void *Mem_ExpandableArray_AllocRecord(memexpandablearray_t *l)
 484 {
 485         size_t i, j;
 486         for (i = 0;;i++)
 487         {
 488                 if (i == l->numarrays)
 489                 {
 490                         if (l->numarrays == l->maxarrays)
 491                         {
 492                                 memexpandablearray_array_t *oldarrays = l->arrays;
 493                                 l->maxarrays = max(l->maxarrays * 2, 128);
 494                                 l->arrays = (memexpandablearray_array_t*) Mem_Alloc(l->mempool, l->maxarrays * sizeof(*l->arrays));
 495                                 if (oldarrays)
 496                                 {
 497                                         memcpy(l->arrays, oldarrays, l->numarrays * sizeof(*l->arrays));
 498                                         Mem_Free(oldarrays);
 499                                 }
 500                         }
 501                         l->arrays[i].numflaggedrecords = 0;
 502                         l->arrays[i].data = (unsigned char *) Mem_Alloc(l->mempool, (l->recordsize + 1) * l->numrecordsperarray);
 503                         l->arrays[i].allocflags = l->arrays[i].data + l->recordsize * l->numrecordsperarray;
 504                         l->numarrays++;
 505                 }
 506                 if (l->arrays[i].numflaggedrecords < l->numrecordsperarray)
 507                 {
 508                         for (j = 0;j < l->numrecordsperarray;j++)
 509                         {
 510                                 if (!l->arrays[i].allocflags[j])
 511                                 {
 512                                         l->arrays[i].allocflags[j] = true;
 513                                         l->arrays[i].numflaggedrecords++;
 514                                         memset(l->arrays[i].data + l->recordsize * j, 0, l->recordsize);
 515                                         return (void *)(l->arrays[i].data + l->recordsize * j);
 516                                 }
 517                         }
 518                 }
 519         }
 520 }
 521
 522 /*****************************************************************************
 523  * IF YOU EDIT THIS:
 524  * If this function was to change the size of the "expandable" array, you have
 525  * to update r_shadow.c
 526  * Just do a search for "range =", R_ShadowClearWorldLights would be the first
 527  * function to look at. (And also seems like the only one?) You  might have to
 528  * move the  call to Mem_ExpandableArray_IndexRange  back into for(...) loop's
 529  * condition
 530  */
 531 void Mem_ExpandableArray_FreeRecord(memexpandablearray_t *l, void *record) // const!
 532 {
 533         size_t i, j;
 534         unsigned char *p = (unsigned char *)record;
 535         for (i = 0;i != l->numarrays;i++)
 536         {
 537                 if (p >= l->arrays[i].data && p < (l->arrays[i].data + l->recordsize * l->numrecordsperarray))
 538                 {
 539                         j = (p - l->arrays[i].data) / l->recordsize;
 540                         if (p != l->arrays[i].data + j * l->recordsize)
 541                                 Sys_Error("Mem_ExpandableArray_FreeRecord: no such record %p\n", p);
 542                         if (!l->arrays[i].allocflags[j])
 543                                 Sys_Error("Mem_ExpandableArray_FreeRecord: record %p is already free!\n", p);
 544                         l->arrays[i].allocflags[j] = false;
 545                         l->arrays[i].numflaggedrecords--;
 546                         return;
 547                 }
 548         }
 549 }
 550
 551 size_t Mem_ExpandableArray_IndexRange(const memexpandablearray_t *l)
 552 {
 553         size_t i, j, k, end = 0;
 554         for (i = 0;i < l->numarrays;i++)
 555         {
 556                 for (j = 0, k = 0;k < l->arrays[i].numflaggedrecords;j++)
 557                 {
 558                         if (l->arrays[i].allocflags[j])
 559                         {
 560                                 end = l->numrecordsperarray * i + j + 1;
 561                                 k++;
 562                         }
 563                 }
 564         }
 565         return end;
 566 }
 567
 568 void *Mem_ExpandableArray_RecordAtIndex(const memexpandablearray_t *l, size_t index)
 569 {
 570         size_t i, j;
 571         i = index / l->numrecordsperarray;
 572         j = index % l->numrecordsperarray;
 573         if (i >= l->numarrays || !l->arrays[i].allocflags[j])
 574                 return NULL;
 575         return (void *)(l->arrays[i].data + j * l->recordsize);
 576 }
 577
 578
 579 // used for temporary memory allocations around the engine, not for longterm
 580 // storage, if anything in this pool stays allocated during gameplay, it is
 581 // considered a leak
 582 mempool_t *tempmempool;
 583 // only for zone
 584 mempool_t *zonemempool;
 585
 586 void Mem_PrintStats(void)
 587 {
 588         size_t count = 0, size = 0, realsize = 0;
 589         mempool_t *pool;
 590         memheader_t *mem;
 591         Mem_CheckSentinelsGlobal();
 592         for (pool = poolchain;pool;pool = pool->next)
 593         {
 594                 count++;
 595                 size += pool->totalsize;
 596                 realsize += pool->realsize;
 597         }
 598         Con_Printf("%lu memory pools, totalling %lu bytes (%.3fMB)\n", (unsigned long)count, (unsigned long)size, size / 1048576.0);
 599         Con_Printf("total allocated size: %lu bytes (%.3fMB)\n", (unsigned long)realsize, realsize / 1048576.0);
 600         for (pool = poolchain;pool;pool = pool->next)
 601         {
 602                 if ((pool->flags & POOLFLAG_TEMP) && pool->chain)
 603                 {
 604                         Con_Printf("Memory pool %p has sprung a leak totalling %lu bytes (%.3fMB)!  Listing contents...\n", pool, (unsigned long)pool->totalsize, pool->totalsize / 1048576.0);
 605                         for (mem = pool->chain;mem;mem = mem->next)
 606                                 Con_Printf("%10lu bytes allocated at %s:%i\n", (unsigned long)mem->size, mem->filename, mem->fileline);
 607                 }
 608         }
 609 }
 610
 611 void Mem_PrintList(size_t minallocationsize)
 612 {
 613         mempool_t *pool;
 614         memheader_t *mem;
 615         Mem_CheckSentinelsGlobal();
 616         Con_Print("memory pool list:\n"
 617                    "size    name\n");
 618         for (pool = poolchain;pool;pool = pool->next)
 619         {
 620                 Con_Printf("%10luk (%10luk actual) %s (%+li byte change) %s\n", (unsigned long) ((pool->totalsize + 1023) / 1024), (unsigned long)((pool->realsize + 1023) / 1024), pool->name, (long)pool->totalsize - pool->lastchecksize, (pool->flags & POOLFLAG_TEMP) ? "TEMP" : "");
 621                 pool->lastchecksize = pool->totalsize;
 622                 for (mem = pool->chain;mem;mem = mem->next)
 623                         if (mem->size >= minallocationsize)
 624                                 Con_Printf("%10lu bytes allocated at %s:%i\n", (unsigned long)mem->size, mem->filename, mem->fileline);
 625         }
 626 }
 627
 628 void MemList_f(void)
 629 {
 630         switch(Cmd_Argc())
 631         {
 632         case 1:
 633                 Mem_PrintList(1<<30);
 634                 Mem_PrintStats();
 635                 break;
 636         case 2:
 637                 Mem_PrintList(atoi(Cmd_Argv(1)) * 1024);
 638                 Mem_PrintStats();
 639                 break;
 640         default:
 641                 Con_Print("MemList_f: unrecognized options\nusage: memlist [all]\n");
 642                 break;
 643         }
 644 }
 645
 646 extern void R_TextureStats_Print(qboolean printeach, qboolean printpool, qboolean printtotal);
 647 void MemStats_f(void)
 648 {
 649         Mem_CheckSentinelsGlobal();
 650         R_TextureStats_Print(false, false, true);
 651         GL_Mesh_ListVBOs(false);
 652         Mem_PrintStats();
 653 }
 654
 655
 656 char* Mem_strdup (mempool_t *pool, const char* s)
 657 {
 658         char* p;
 659         size_t sz = strlen (s) + 1;
 660         if (s == NULL) return NULL;
 661         p = (char*)Mem_Alloc (pool, sz);
 662         strlcpy (p, s, sz);
 663         return p;
 664 }
 665
 666 /*
 667 ========================
 668 Memory_Init
 669 ========================
 670 */
 671 void Memory_Init (void)
 672 {
 673         sentinel_seed = rand();
 674         poolchain = NULL;
 675         tempmempool = Mem_AllocPool("Temporary Memory", POOLFLAG_TEMP, NULL);
 676         zonemempool = Mem_AllocPool("Zone", 0, NULL);
 677 }
 678
 679 void Memory_Shutdown (void)
 680 {
 681 //      Mem_FreePool (&zonemempool);
 682 //      Mem_FreePool (&tempmempool);
 683 }
 684
 685 void Memory_Init_Commands (void)
 686 {
 687         Cmd_AddCommand ("memstats", MemStats_f, "prints memory system statistics");
 688         Cmd_AddCommand ("memlist", MemList_f, "prints memory pool information (or if used as memlist 5 lists individual allocations of 5K or larger, 0 lists all allocations)");
 689         Cvar_RegisterVariable (&developer_memory);
 690         Cvar_RegisterVariable (&developer_memorydebug);
 691 }
 692