Two new cvars for blood particles: decal alpha, decal random scaling (min/max)
[divverent/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 #ifdef WIN32
25 #include <windows.h>
26 #else
27 #include <unistd.h>
28 #endif
29
30 #ifdef _MSC_VER
31 #include <vadefs.h>
32 #else
33 #include <stdint.h>
34 #endif
35 #define MEMHEADER_SENTINEL_FOR_ADDRESS(p) ((sentinel_seed ^ (unsigned int) (uintptr_t) (p)) + sentinel_seed)
36 unsigned int sentinel_seed;
37
38 qboolean mem_bigendian = false;
39
40 // LordHavoc: enables our own low-level allocator (instead of malloc)
41 #define MEMCLUMPING 0
42 #define MEMCLUMPING_FREECLUMPS 0
43
44 #if MEMCLUMPING
45 // smallest unit we care about is this many bytes
46 #define MEMUNIT 128
47 // try to do 32MB clumps, but overhead eats into this
48 #define MEMWANTCLUMPSIZE (1<<27)
49 // give malloc padding so we can't waste most of a page at the end
50 #define MEMCLUMPSIZE (MEMWANTCLUMPSIZE - MEMWANTCLUMPSIZE/MEMUNIT/32 - 128)
51 #define MEMBITS (MEMCLUMPSIZE / MEMUNIT)
52 #define MEMBITINTS (MEMBITS / 32)
53
54 typedef struct memclump_s
55 {
56         // contents of the clump
57         unsigned char block[MEMCLUMPSIZE];
58         // should always be MEMCLUMP_SENTINEL
59         unsigned int sentinel1;
60         // if a bit is on, it means that the MEMUNIT bytes it represents are
61         // allocated, otherwise free
62         unsigned int bits[MEMBITINTS];
63         // should always be MEMCLUMP_SENTINEL
64         unsigned int sentinel2;
65         // if this drops to 0, the clump is freed
66         size_t blocksinuse;
67         // largest block of memory available (this is reset to an optimistic
68         // number when anything is freed, and updated when alloc fails the clump)
69         size_t largestavailable;
70         // next clump in the chain
71         struct memclump_s *chain;
72 }
73 memclump_t;
74
75 #if MEMCLUMPING == 2
76 static memclump_t masterclump;
77 #endif
78 static memclump_t *clumpchain = NULL;
79 #endif
80
81
82 cvar_t developer_memory = {0, "developer_memory", "0", "prints debugging information about memory allocations"};
83 cvar_t developer_memorydebug = {0, "developer_memorydebug", "0", "enables memory corruption checks (very slow)"};
84
85 static mempool_t *poolchain = NULL;
86
87 void Mem_PrintStats(void);
88 void Mem_PrintList(size_t minallocationsize);
89
90 #if MEMCLUMPING != 2
91 // some platforms have a malloc that returns NULL but succeeds later
92 // (Windows growing its swapfile for example)
93 static void *attempt_malloc(size_t size)
94 {
95         void *base;
96         // try for half a second or so
97         unsigned int attempts = 500;
98         while (attempts--)
99         {
100                 base = (void *)malloc(size);
101                 if (base)
102                         return base;
103                 Sys_Sleep(1000);
104         }
105         return NULL;
106 }
107 #endif
108
109 #if MEMCLUMPING
110 static memclump_t *Clump_NewClump(void)
111 {
112         memclump_t **clumpchainpointer;
113         memclump_t *clump;
114 #if MEMCLUMPING == 2
115         if (clumpchain)
116                 return NULL;
117         clump = &masterclump;
118 #else
119         clump = (memclump_t*)attempt_malloc(sizeof(memclump_t));
120         if (!clump)
121                 return NULL;
122 #endif
123
124         // initialize clump
125         if (developer_memorydebug.integer)
126                 memset(clump, 0xEF, sizeof(*clump));
127         clump->sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel1);
128         memset(clump->bits, 0, sizeof(clump->bits));
129         clump->sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel2);
130         clump->blocksinuse = 0;
131         clump->largestavailable = 0;
132         clump->chain = NULL;
133
134         // link clump into chain
135         for (clumpchainpointer = &clumpchain;*clumpchainpointer;clumpchainpointer = &(*clumpchainpointer)->chain)
136                 ;
137         *clumpchainpointer = clump;
138
139         return clump;
140 }
141 #endif
142
143 // low level clumping functions, all other memory functions use these
144 static void *Clump_AllocBlock(size_t size)
145 {
146         unsigned char *base;
147 #if MEMCLUMPING
148         if (size <= MEMCLUMPSIZE)
149         {
150                 int index;
151                 unsigned int bit;
152                 unsigned int needbits;
153                 unsigned int startbit;
154                 unsigned int endbit;
155                 unsigned int needints;
156                 int startindex;
157                 int endindex;
158                 unsigned int value;
159                 unsigned int mask;
160                 unsigned int *array;
161                 memclump_t **clumpchainpointer;
162                 memclump_t *clump;
163                 needbits = (size + MEMUNIT - 1) / MEMUNIT;
164                 needints = (needbits+31)>>5;
165                 for (clumpchainpointer = &clumpchain;;clumpchainpointer = &(*clumpchainpointer)->chain)
166                 {
167                         clump = *clumpchainpointer;
168                         if (!clump)
169                         {
170                                 clump = Clump_NewClump();
171                                 if (!clump)
172                                         return NULL;
173                         }
174                         if (clump->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel1))
175                                 Sys_Error("Clump_AllocBlock: trashed sentinel1\n");
176                         if (clump->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel2))
177                                 Sys_Error("Clump_AllocBlock: trashed sentinel2\n");
178                         startbit = 0;
179                         endbit = startbit + needbits;
180                         array = clump->bits;
181                         // do as fast a search as possible, even if it means crude alignment
182                         if (needbits >= 32)
183                         {
184                                 // large allocations are aligned to large boundaries
185                                 // furthermore, they are allocated downward from the top...
186                                 endindex = MEMBITINTS;
187                                 startindex = endindex - needints;
188                                 index = endindex;
189                                 while (--index >= startindex)
190                                 {
191                                         if (array[index])
192                                         {
193                                                 endindex = index;
194                                                 startindex = endindex - needints;
195                                                 if (startindex < 0)
196                                                         goto nofreeblock;
197                                         }
198                                 }
199                                 startbit = startindex*32;
200                                 goto foundblock;
201                         }
202                         else
203                         {
204                                 // search for a multi-bit gap in a single int
205                                 // (not dealing with the cases that cross two ints)
206                                 mask = (1<<needbits)-1;
207                                 endbit = 32-needbits;
208                                 bit = endbit;
209                                 for (index = 0;index < MEMBITINTS;index++)
210                                 {
211                                         value = array[index];
212                                         if (value != 0xFFFFFFFFu)
213                                         {
214                                                 // there may be room in this one...
215                                                 for (bit = 0;bit < endbit;bit++)
216                                                 {
217                                                         if (!(value & (mask<<bit)))
218                                                         {
219                                                                 startbit = index*32+bit;
220                                                                 goto foundblock;
221                                                         }
222                                                 }
223                                         }
224                                 }
225                                 goto nofreeblock;
226                         }
227 foundblock:
228                         endbit = startbit + needbits;
229                         // mark this range as used
230                         // TODO: optimize
231                         for (bit = startbit;bit < endbit;bit++)
232                                 if (clump->bits[bit>>5] & (1<<(bit & 31)))
233                                         Sys_Error("Clump_AllocBlock: internal error (%i needbits)\n", needbits);
234                         for (bit = startbit;bit < endbit;bit++)
235                                 clump->bits[bit>>5] |= (1<<(bit & 31));
236                         clump->blocksinuse += needbits;
237                         base = clump->block + startbit * MEMUNIT;
238                         if (developer_memorydebug.integer)
239                                 memset(base, 0xBF, needbits * MEMUNIT);
240                         return base;
241 nofreeblock:
242                         ;
243                 }
244                 // never reached
245                 return NULL;
246         }
247         // too big, allocate it directly
248 #endif
249 #if MEMCLUMPING == 2
250         return NULL;
251 #else
252         base = (unsigned char *)attempt_malloc(size);
253         if (base && developer_memorydebug.integer)
254                 memset(base, 0xAF, size);
255         return base;
256 #endif
257 }
258 static void Clump_FreeBlock(void *base, size_t size)
259 {
260 #if MEMCLUMPING
261         unsigned int needbits;
262         unsigned int startbit;
263         unsigned int endbit;
264         unsigned int bit;
265         memclump_t **clumpchainpointer;
266         memclump_t *clump;
267         unsigned char *start = (unsigned char *)base;
268         for (clumpchainpointer = &clumpchain;(clump = *clumpchainpointer);clumpchainpointer = &(*clumpchainpointer)->chain)
269         {
270                 if (start >= clump->block && start < clump->block + MEMCLUMPSIZE)
271                 {
272                         if (clump->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel1))
273                                 Sys_Error("Clump_FreeBlock: trashed sentinel1\n");
274                         if (clump->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel2))
275                                 Sys_Error("Clump_FreeBlock: trashed sentinel2\n");
276                         if (start + size > clump->block + MEMCLUMPSIZE)
277                                 Sys_Error("Clump_FreeBlock: block overrun\n");
278                         // the block belongs to this clump, clear the range
279                         needbits = (size + MEMUNIT - 1) / MEMUNIT;
280                         startbit = (start - clump->block) / MEMUNIT;
281                         endbit = startbit + needbits;
282                         // first verify all bits are set, otherwise this may be misaligned or a double free
283                         for (bit = startbit;bit < endbit;bit++)
284                                 if ((clump->bits[bit>>5] & (1<<(bit & 31))) == 0)
285                                         Sys_Error("Clump_FreeBlock: double free\n");
286                         for (bit = startbit;bit < endbit;bit++)
287                                 clump->bits[bit>>5] &= ~(1<<(bit & 31));
288                         clump->blocksinuse -= needbits;
289                         memset(base, 0xFF, needbits * MEMUNIT);
290                         // if all has been freed, free the clump itself
291                         if (clump->blocksinuse == 0)
292                         {
293                                 *clumpchainpointer = clump->chain;
294                                 if (developer_memorydebug.integer)
295                                         memset(clump, 0xFF, sizeof(*clump));
296 #if MEMCLUMPING != 2
297                                 free(clump);
298 #endif
299                         }
300                         return;
301                 }
302         }
303         // does not belong to any known chunk...  assume it was a direct allocation
304 #endif
305 #if MEMCLUMPING != 2
306         memset(base, 0xFF, size);
307         free(base);
308 #endif
309 }
310
311 void *_Mem_Alloc(mempool_t *pool, void *olddata, size_t size, size_t alignment, const char *filename, int fileline)
312 {
313         unsigned int sentinel1;
314         unsigned int sentinel2;
315         size_t realsize;
316         size_t sharedsize;
317         size_t remainsize;
318         memheader_t *mem;
319         memheader_t *oldmem;
320         unsigned char *base;
321
322         if (size <= 0)
323         {
324                 if (olddata)
325                         _Mem_Free(olddata, filename, fileline);
326                 return NULL;
327         }
328         if (pool == NULL)
329                 Sys_Error("Mem_Alloc: pool == NULL (alloc at %s:%i)", filename, fileline);
330         if (developer_memory.integer)
331                 Con_DPrintf("Mem_Alloc: pool %s, file %s:%i, size %i bytes\n", pool->name, filename, fileline, (int)size);
332         //if (developer.integer && developer_memorydebug.integer)
333         //      _Mem_CheckSentinelsGlobal(filename, fileline);
334         pool->totalsize += size;
335         realsize = alignment + sizeof(memheader_t) + size + sizeof(sentinel2);
336         pool->realsize += realsize;
337         base = (unsigned char *)Clump_AllocBlock(realsize);
338         if (base== NULL)
339         {
340                 Mem_PrintList(0);
341                 Mem_PrintStats();
342                 Mem_PrintList(1<<30);
343                 Mem_PrintStats();
344                 Sys_Error("Mem_Alloc: out of memory (alloc at %s:%i)", filename, fileline);
345         }
346         // calculate address that aligns the end of the memheader_t to the specified alignment
347         mem = (memheader_t*)((((size_t)base + sizeof(memheader_t) + (alignment-1)) & ~(alignment-1)) - sizeof(memheader_t));
348         mem->baseaddress = (void*)base;
349         mem->filename = filename;
350         mem->fileline = fileline;
351         mem->size = size;
352         mem->pool = pool;
353
354         // calculate sentinels (detects buffer overruns, in a way that is hard to exploit)
355         sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&mem->sentinel);
356         sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS((unsigned char *) mem + sizeof(memheader_t) + mem->size);
357         mem->sentinel = sentinel1;
358         memcpy((unsigned char *) mem + sizeof(memheader_t) + mem->size, &sentinel2, sizeof(sentinel2));
359
360         // append to head of list
361         mem->next = pool->chain;
362         mem->prev = NULL;
363         pool->chain = mem;
364         if (mem->next)
365                 mem->next->prev = mem;
366
367         // copy the shared portion in the case of a realloc, then memset the rest
368         sharedsize = 0;
369         remainsize = size;
370         if (olddata)
371         {
372                 oldmem = (memheader_t*)olddata - 1;
373                 sharedsize = min(oldmem->size, size);
374                 memcpy((void *)((unsigned char *) mem + sizeof(memheader_t)), olddata, sharedsize);
375                 remainsize -= sharedsize;
376                 _Mem_Free(olddata, filename, fileline);
377         }
378         memset((void *)((unsigned char *) mem + sizeof(memheader_t) + sharedsize), 0, remainsize);
379         return (void *)((unsigned char *) mem + sizeof(memheader_t));
380 }
381
382 // only used by _Mem_Free and _Mem_FreePool
383 static void _Mem_FreeBlock(memheader_t *mem, const char *filename, int fileline)
384 {
385         mempool_t *pool;
386         size_t size;
387         size_t realsize;
388         unsigned int sentinel1;
389         unsigned int sentinel2;
390
391         // check sentinels (detects buffer overruns, in a way that is hard to exploit)
392         sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&mem->sentinel);
393         sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS((unsigned char *) mem + sizeof(memheader_t) + mem->size);
394         if (mem->sentinel != sentinel1)
395                 Sys_Error("Mem_Free: trashed header sentinel 1 (alloc at %s:%i, free at %s:%i)", mem->filename, mem->fileline, filename, fileline);
396         if (memcmp((unsigned char *) mem + sizeof(memheader_t) + mem->size, &sentinel2, sizeof(sentinel2)))
397                 Sys_Error("Mem_Free: trashed header sentinel 2 (alloc at %s:%i, free at %s:%i)", mem->filename, mem->fileline, filename, fileline);
398
399         pool = mem->pool;
400         if (developer_memory.integer)
401                 Con_DPrintf("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));
402         // unlink memheader from doubly linked list
403         if ((mem->prev ? mem->prev->next != mem : pool->chain != mem) || (mem->next && mem->next->prev != mem))
404                 Sys_Error("Mem_Free: not allocated or double freed (free at %s:%i)", filename, fileline);
405         if (mem->prev)
406                 mem->prev->next = mem->next;
407         else
408                 pool->chain = mem->next;
409         if (mem->next)
410                 mem->next->prev = mem->prev;
411         // memheader has been unlinked, do the actual free now
412         size = mem->size;
413         realsize = sizeof(memheader_t) + size + sizeof(sentinel2);
414         pool->totalsize -= size;
415         pool->realsize -= realsize;
416         Clump_FreeBlock(mem->baseaddress, realsize);
417 }
418
419 void _Mem_Free(void *data, const char *filename, int fileline)
420 {
421         if (data == NULL)
422         {
423                 Con_DPrintf("Mem_Free: data == NULL (called at %s:%i)\n", filename, fileline);
424                 return;
425         }
426
427         if (developer_memorydebug.integer)
428         {
429                 //_Mem_CheckSentinelsGlobal(filename, fileline);
430                 if (!Mem_IsAllocated(NULL, data))
431                         Sys_Error("Mem_Free: data is not allocated (called at %s:%i)", filename, fileline);
432         }
433
434         _Mem_FreeBlock((memheader_t *)((unsigned char *) data - sizeof(memheader_t)), filename, fileline);
435 }
436
437 mempool_t *_Mem_AllocPool(const char *name, int flags, mempool_t *parent, const char *filename, int fileline)
438 {
439         mempool_t *pool;
440         if (developer_memorydebug.integer)
441                 _Mem_CheckSentinelsGlobal(filename, fileline);
442         pool = (mempool_t *)Clump_AllocBlock(sizeof(mempool_t));
443         if (pool == NULL)
444         {
445                 Mem_PrintList(0);
446                 Mem_PrintStats();
447                 Mem_PrintList(1<<30);
448                 Mem_PrintStats();
449                 Sys_Error("Mem_AllocPool: out of memory (allocpool at %s:%i)", filename, fileline);
450         }
451         memset(pool, 0, sizeof(mempool_t));
452         pool->sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1);
453         pool->sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2);
454         pool->filename = filename;
455         pool->fileline = fileline;
456         pool->flags = flags;
457         pool->chain = NULL;
458         pool->totalsize = 0;
459         pool->realsize = sizeof(mempool_t);
460         strlcpy (pool->name, name, sizeof (pool->name));
461         pool->parent = parent;
462         pool->next = poolchain;
463         poolchain = pool;
464         return pool;
465 }
466
467 void _Mem_FreePool(mempool_t **poolpointer, const char *filename, int fileline)
468 {
469         mempool_t *pool = *poolpointer;
470         mempool_t **chainaddress, *iter, *temp;
471
472         if (developer_memorydebug.integer)
473                 _Mem_CheckSentinelsGlobal(filename, fileline);
474         if (pool)
475         {
476                 // unlink pool from chain
477                 for (chainaddress = &poolchain;*chainaddress && *chainaddress != pool;chainaddress = &((*chainaddress)->next));
478                 if (*chainaddress != pool)
479                         Sys_Error("Mem_FreePool: pool already free (freepool at %s:%i)", filename, fileline);
480                 if (pool->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1))
481                         Sys_Error("Mem_FreePool: trashed pool sentinel 1 (allocpool at %s:%i, freepool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
482                 if (pool->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2))
483                         Sys_Error("Mem_FreePool: trashed pool sentinel 2 (allocpool at %s:%i, freepool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
484                 *chainaddress = pool->next;
485
486                 // free memory owned by the pool
487                 while (pool->chain)
488                         _Mem_FreeBlock(pool->chain, filename, fileline);
489
490                 // free child pools, too
491                 for(iter = poolchain; iter; temp = iter = iter->next)
492                         if(iter->parent == pool)
493                                 _Mem_FreePool(&temp, filename, fileline);
494
495                 // free the pool itself
496                 Clump_FreeBlock(pool, sizeof(*pool));
497
498                 *poolpointer = NULL;
499         }
500 }
501
502 void _Mem_EmptyPool(mempool_t *pool, const char *filename, int fileline)
503 {
504         mempool_t *chainaddress;
505
506         if (developer_memorydebug.integer)
507         {
508                 //_Mem_CheckSentinelsGlobal(filename, fileline);
509                 // check if this pool is in the poolchain
510                 for (chainaddress = poolchain;chainaddress;chainaddress = chainaddress->next)
511                         if (chainaddress == pool)
512                                 break;
513                 if (!chainaddress)
514                         Sys_Error("Mem_EmptyPool: pool is already free (emptypool at %s:%i)", filename, fileline);
515         }
516         if (pool == NULL)
517                 Sys_Error("Mem_EmptyPool: pool == NULL (emptypool at %s:%i)", filename, fileline);
518         if (pool->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1))
519                 Sys_Error("Mem_EmptyPool: trashed pool sentinel 2 (allocpool at %s:%i, emptypool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
520         if (pool->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2))
521                 Sys_Error("Mem_EmptyPool: trashed pool sentinel 1 (allocpool at %s:%i, emptypool at %s:%i)", pool->filename, pool->fileline, filename, fileline);
522
523         // free memory owned by the pool
524         while (pool->chain)
525                 _Mem_FreeBlock(pool->chain, filename, fileline);
526
527         // empty child pools, too
528         for(chainaddress = poolchain; chainaddress; chainaddress = chainaddress->next)
529                 if(chainaddress->parent == pool)
530                         _Mem_EmptyPool(chainaddress, filename, fileline);
531
532 }
533
534 void _Mem_CheckSentinels(void *data, const char *filename, int fileline)
535 {
536         memheader_t *mem;
537         unsigned int sentinel1;
538         unsigned int sentinel2;
539
540         if (data == NULL)
541                 Sys_Error("Mem_CheckSentinels: data == NULL (sentinel check at %s:%i)", filename, fileline);
542
543         mem = (memheader_t *)((unsigned char *) data - sizeof(memheader_t));
544         sentinel1 = MEMHEADER_SENTINEL_FOR_ADDRESS(&mem->sentinel);
545         sentinel2 = MEMHEADER_SENTINEL_FOR_ADDRESS((unsigned char *) mem + sizeof(memheader_t) + mem->size);
546         if (mem->sentinel != sentinel1)
547                 Sys_Error("Mem_Free: trashed header sentinel 1 (alloc at %s:%i, sentinel check at %s:%i)", mem->filename, mem->fileline, filename, fileline);
548         if (memcmp((unsigned char *) mem + sizeof(memheader_t) + mem->size, &sentinel2, sizeof(sentinel2)))
549                 Sys_Error("Mem_Free: trashed header sentinel 2 (alloc at %s:%i, sentinel check at %s:%i)", mem->filename, mem->fileline, filename, fileline);
550 }
551
552 #if MEMCLUMPING
553 static void _Mem_CheckClumpSentinels(memclump_t *clump, const char *filename, int fileline)
554 {
555         // this isn't really very useful
556         if (clump->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel1))
557                 Sys_Error("Mem_CheckClumpSentinels: trashed sentinel 1 (sentinel check at %s:%i)", filename, fileline);
558         if (clump->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&clump->sentinel2))
559                 Sys_Error("Mem_CheckClumpSentinels: trashed sentinel 2 (sentinel check at %s:%i)", filename, fileline);
560 }
561 #endif
562
563 void _Mem_CheckSentinelsGlobal(const char *filename, int fileline)
564 {
565         memheader_t *mem;
566 #if MEMCLUMPING
567         memclump_t *clump;
568 #endif
569         mempool_t *pool;
570         for (pool = poolchain;pool;pool = pool->next)
571         {
572                 if (pool->sentinel1 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel1))
573                         Sys_Error("Mem_CheckSentinelsGlobal: trashed pool sentinel 1 (allocpool at %s:%i, sentinel check at %s:%i)", pool->filename, pool->fileline, filename, fileline);
574                 if (pool->sentinel2 != MEMHEADER_SENTINEL_FOR_ADDRESS(&pool->sentinel2))
575                         Sys_Error("Mem_CheckSentinelsGlobal: trashed pool sentinel 2 (allocpool at %s:%i, sentinel check at %s:%i)", pool->filename, pool->fileline, filename, fileline);
576         }
577         for (pool = poolchain;pool;pool = pool->next)
578                 for (mem = pool->chain;mem;mem = mem->next)
579                         _Mem_CheckSentinels((void *)((unsigned char *) mem + sizeof(memheader_t)), filename, fileline);
580 #if MEMCLUMPING
581         for (pool = poolchain;pool;pool = pool->next)
582                 for (clump = clumpchain;clump;clump = clump->chain)
583                         _Mem_CheckClumpSentinels(clump, filename, fileline);
584 #endif
585 }
586
587 qboolean Mem_IsAllocated(mempool_t *pool, void *data)
588 {
589         memheader_t *header;
590         memheader_t *target;
591
592         if (pool)
593         {
594                 // search only one pool
595                 target = (memheader_t *)((unsigned char *) data - sizeof(memheader_t));
596                 for( header = pool->chain ; header ; header = header->next )
597                         if( header == target )
598                                 return true;
599         }
600         else
601         {
602                 // search all pools
603                 for (pool = poolchain;pool;pool = pool->next)
604                         if (Mem_IsAllocated(pool, data))
605                                 return true;
606         }
607         return false;
608 }
609
610 void Mem_ExpandableArray_NewArray(memexpandablearray_t *l, mempool_t *mempool, size_t recordsize, int numrecordsperarray)
611 {
612         memset(l, 0, sizeof(*l));
613         l->mempool = mempool;
614         l->recordsize = recordsize;
615         l->numrecordsperarray = numrecordsperarray;
616 }
617
618 void Mem_ExpandableArray_FreeArray(memexpandablearray_t *l)
619 {
620         size_t i;
621         if (l->maxarrays)
622         {
623                 for (i = 0;i != l->numarrays;i++)
624                         Mem_Free(l->arrays[i].data);
625                 Mem_Free(l->arrays);
626         }
627         memset(l, 0, sizeof(*l));
628 }
629
630 void *Mem_ExpandableArray_AllocRecord(memexpandablearray_t *l)
631 {
632         size_t i, j;
633         for (i = 0;;i++)
634         {
635                 if (i == l->numarrays)
636                 {
637                         if (l->numarrays == l->maxarrays)
638                         {
639                                 memexpandablearray_array_t *oldarrays = l->arrays;
640                                 l->maxarrays = max(l->maxarrays * 2, 128);
641                                 l->arrays = (memexpandablearray_array_t*) Mem_Alloc(l->mempool, l->maxarrays * sizeof(*l->arrays));
642                                 if (oldarrays)
643                                 {
644                                         memcpy(l->arrays, oldarrays, l->numarrays * sizeof(*l->arrays));
645                                         Mem_Free(oldarrays);
646                                 }
647                         }
648                         l->arrays[i].numflaggedrecords = 0;
649                         l->arrays[i].data = (unsigned char *) Mem_Alloc(l->mempool, (l->recordsize + 1) * l->numrecordsperarray);
650                         l->arrays[i].allocflags = l->arrays[i].data + l->recordsize * l->numrecordsperarray;
651                         l->numarrays++;
652                 }
653                 if (l->arrays[i].numflaggedrecords < l->numrecordsperarray)
654                 {
655                         for (j = 0;j < l->numrecordsperarray;j++)
656                         {
657                                 if (!l->arrays[i].allocflags[j])
658                                 {
659                                         l->arrays[i].allocflags[j] = true;
660                                         l->arrays[i].numflaggedrecords++;
661                                         memset(l->arrays[i].data + l->recordsize * j, 0, l->recordsize);
662                                         return (void *)(l->arrays[i].data + l->recordsize * j);
663                                 }
664                         }
665                 }
666         }
667 }
668
669 /*****************************************************************************
670  * IF YOU EDIT THIS:
671  * If this function was to change the size of the "expandable" array, you have
672  * to update r_shadow.c
673  * Just do a search for "range =", R_ShadowClearWorldLights would be the first
674  * function to look at. (And also seems like the only one?) You  might have to
675  * move the  call to Mem_ExpandableArray_IndexRange  back into for(...) loop's
676  * condition
677  */
678 void Mem_ExpandableArray_FreeRecord(memexpandablearray_t *l, void *record) // const!
679 {
680         size_t i, j;
681         unsigned char *p = (unsigned char *)record;
682         for (i = 0;i != l->numarrays;i++)
683         {
684                 if (p >= l->arrays[i].data && p < (l->arrays[i].data + l->recordsize * l->numrecordsperarray))
685                 {
686                         j = (p - l->arrays[i].data) / l->recordsize;
687                         if (p != l->arrays[i].data + j * l->recordsize)
688                                 Sys_Error("Mem_ExpandableArray_FreeRecord: no such record %p\n", p);
689                         if (!l->arrays[i].allocflags[j])
690                                 Sys_Error("Mem_ExpandableArray_FreeRecord: record %p is already free!\n", p);
691                         l->arrays[i].allocflags[j] = false;
692                         l->arrays[i].numflaggedrecords--;
693                         return;
694                 }
695         }
696 }
697
698 size_t Mem_ExpandableArray_IndexRange(const memexpandablearray_t *l)
699 {
700         size_t i, j, k, end = 0;
701         for (i = 0;i < l->numarrays;i++)
702         {
703                 for (j = 0, k = 0;k < l->arrays[i].numflaggedrecords;j++)
704                 {
705                         if (l->arrays[i].allocflags[j])
706                         {
707                                 end = l->numrecordsperarray * i + j + 1;
708                                 k++;
709                         }
710                 }
711         }
712         return end;
713 }
714
715 void *Mem_ExpandableArray_RecordAtIndex(const memexpandablearray_t *l, size_t index)
716 {
717         size_t i, j;
718         i = index / l->numrecordsperarray;
719         j = index % l->numrecordsperarray;
720         if (i >= l->numarrays || !l->arrays[i].allocflags[j])
721                 return NULL;
722         return (void *)(l->arrays[i].data + j * l->recordsize);
723 }
724
725
726 // used for temporary memory allocations around the engine, not for longterm
727 // storage, if anything in this pool stays allocated during gameplay, it is
728 // considered a leak
729 mempool_t *tempmempool;
730 // only for zone
731 mempool_t *zonemempool;
732
733 void Mem_PrintStats(void)
734 {
735         size_t count = 0, size = 0, realsize = 0;
736         mempool_t *pool;
737         memheader_t *mem;
738         Mem_CheckSentinelsGlobal();
739         for (pool = poolchain;pool;pool = pool->next)
740         {
741                 count++;
742                 size += pool->totalsize;
743                 realsize += pool->realsize;
744         }
745         Con_Printf("%lu memory pools, totalling %lu bytes (%.3fMB)\n", (unsigned long)count, (unsigned long)size, size / 1048576.0);
746         Con_Printf("total allocated size: %lu bytes (%.3fMB)\n", (unsigned long)realsize, realsize / 1048576.0);
747         for (pool = poolchain;pool;pool = pool->next)
748         {
749                 if ((pool->flags & POOLFLAG_TEMP) && pool->chain)
750                 {
751                         Con_Printf("Memory pool %p has sprung a leak totalling %lu bytes (%.3fMB)!  Listing contents...\n", (void *)pool, (unsigned long)pool->totalsize, pool->totalsize / 1048576.0);
752                         for (mem = pool->chain;mem;mem = mem->next)
753                                 Con_Printf("%10lu bytes allocated at %s:%i\n", (unsigned long)mem->size, mem->filename, mem->fileline);
754                 }
755         }
756 }
757
758 void Mem_PrintList(size_t minallocationsize)
759 {
760         mempool_t *pool;
761         memheader_t *mem;
762         Mem_CheckSentinelsGlobal();
763         Con_Print("memory pool list:\n"
764                    "size    name\n");
765         for (pool = poolchain;pool;pool = pool->next)
766         {
767                 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" : "");
768                 pool->lastchecksize = pool->totalsize;
769                 for (mem = pool->chain;mem;mem = mem->next)
770                         if (mem->size >= minallocationsize)
771                                 Con_Printf("%10lu bytes allocated at %s:%i\n", (unsigned long)mem->size, mem->filename, mem->fileline);
772         }
773 }
774
775 void MemList_f(void)
776 {
777         switch(Cmd_Argc())
778         {
779         case 1:
780                 Mem_PrintList(1<<30);
781                 Mem_PrintStats();
782                 break;
783         case 2:
784                 Mem_PrintList(atoi(Cmd_Argv(1)) * 1024);
785                 Mem_PrintStats();
786                 break;
787         default:
788                 Con_Print("MemList_f: unrecognized options\nusage: memlist [all]\n");
789                 break;
790         }
791 }
792
793 extern void R_TextureStats_Print(qboolean printeach, qboolean printpool, qboolean printtotal);
794 void MemStats_f(void)
795 {
796         Mem_CheckSentinelsGlobal();
797         R_TextureStats_Print(false, false, true);
798         GL_Mesh_ListVBOs(false);
799         Mem_PrintStats();
800 }
801
802
803 char* Mem_strdup (mempool_t *pool, const char* s)
804 {
805         char* p;
806         size_t sz = strlen (s) + 1;
807         if (s == NULL) return NULL;
808         p = (char*)Mem_Alloc (pool, sz);
809         strlcpy (p, s, sz);
810         return p;
811 }
812
813 /*
814 ========================
815 Memory_Init
816 ========================
817 */
818 void Memory_Init (void)
819 {
820         static union {unsigned short s;unsigned char b[2];} u;
821         u.s = 0x100;
822         mem_bigendian = u.b[0];
823
824         sentinel_seed = rand();
825         poolchain = NULL;
826         tempmempool = Mem_AllocPool("Temporary Memory", POOLFLAG_TEMP, NULL);
827         zonemempool = Mem_AllocPool("Zone", 0, NULL);
828 }
829
830 void Memory_Shutdown (void)
831 {
832 //      Mem_FreePool (&zonemempool);
833 //      Mem_FreePool (&tempmempool);
834 }
835
836 void Memory_Init_Commands (void)
837 {
838         Cmd_AddCommand ("memstats", MemStats_f, "prints memory system statistics");
839         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)");
840         Cvar_RegisterVariable (&developer_memory);
841         Cvar_RegisterVariable (&developer_memorydebug);
842 }
843