MUCH more paranoid memory checking (use random address dependent sentinels)
[xonotic/darkplaces.git] / 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