2 Copyright (C) 1996-1997 Id Software, Inc.
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.
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.
13 See the GNU General Public License for more details.
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.
24 // LordHavoc: everyone used a -zone 512 anyway, so...
25 #define DYNAMIC_SIZE 0x80000
26 //#define DYNAMIC_SIZE 0xc000
28 #define ZONEID 0x1d4a11
29 #define MINFRAGMENT 64
31 typedef struct memblock_s
33 int size; // including the header and possibly tiny fragments
34 int tag; // a tag of 0 is a free block
35 int id; // should be ZONEID
36 struct memblock_s *next, *prev;
37 int pad; // pad to 64 bit boundary
42 int size; // total bytes malloced, including header
43 memblock_t blocklist; // start / end cap for linked list
47 void Cache_FreeLow (int new_low_hunk);
48 void Cache_FreeHigh (int new_high_hunk);
52 ==============================================================================
54 ZONE MEMORY ALLOCATION
56 There is never any space between memblocks, and there will never be two
57 contiguous free memblocks.
59 The rover can be left pointing at a non-empty block
61 The zone calls are pretty much only used for small strings and structures,
62 all big things are allocated on the hunk.
63 ==============================================================================
68 void Z_ClearZone (memzone_t *zone, int size);
72 ========================
74 ========================
76 void Z_ClearZone (memzone_t *zone, int size)
80 // set the entire zone to one free block
82 zone->blocklist.next = zone->blocklist.prev = block =
83 (memblock_t *)( (byte *)zone + sizeof(memzone_t) );
84 zone->blocklist.tag = 1; // in use block
85 zone->blocklist.id = 0;
86 zone->blocklist.size = 0;
89 block->prev = block->next = &zone->blocklist;
90 block->tag = 0; // free block
92 block->size = size - sizeof(memzone_t);
97 ========================
99 ========================
101 void Z_Free (void *ptr)
103 memblock_t *block, *other;
106 Sys_Error ("Z_Free: NULL pointer");
108 block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t));
109 if (block->id != ZONEID)
110 Sys_Error ("Z_Free: freed a pointer without ZONEID");
112 Sys_Error ("Z_Free: freed a freed pointer");
114 block->tag = 0; // mark as free
118 { // merge with previous free block
119 other->size += block->size;
120 other->next = block->next;
121 other->next->prev = other;
122 if (block == mainzone->rover)
123 mainzone->rover = other;
129 { // merge the next free block onto the end
130 block->size += other->size;
131 block->next = other->next;
132 block->next->prev = block;
133 if (other == mainzone->rover)
134 mainzone->rover = block;
140 ========================
142 ========================
144 void *Z_Malloc (int size)
148 Z_CheckHeap (); // DEBUG
149 buf = Z_TagMalloc (size, 1);
151 Sys_Error ("Z_Malloc: failed on allocation of %i bytes",size);
152 memset (buf, 0, size);
157 void *Z_TagMalloc (int size, int tag)
160 memblock_t *start, *rover, *new, *base;
163 Sys_Error ("Z_TagMalloc: tried to use a 0 tag");
166 // scan through the block list looking for the first free block
167 // of sufficient size
169 size += sizeof(memblock_t); // account for size of block header
170 size += 4; // space for memory trash tester
171 size = (size + 7) & ~7; // align to 8-byte boundary
173 base = rover = mainzone->rover;
178 if (rover == start) // scaned all the way around the list
181 base = rover = rover->next;
184 } while (base->tag || base->size < size);
187 // found a block big enough
189 extra = base->size - size;
190 if (extra > MINFRAGMENT)
191 { // there will be a free fragment after the allocated block
192 new = (memblock_t *) ((byte *)base + size );
194 new->tag = 0; // free block
197 new->next = base->next;
198 new->next->prev = new;
203 base->tag = tag; // no longer a free block
205 mainzone->rover = base->next; // next allocation will start looking here
209 // marker for memory trash testing
210 *(int *)((byte *)base + base->size - 4) = ZONEID;
212 return (void *) ((byte *)base + sizeof(memblock_t));
217 ========================
219 ========================
221 void Z_Print (memzone_t *zone)
225 Con_Printf ("zone size: %i location: %p\n",mainzone->size,mainzone);
227 for (block = zone->blocklist.next ; ; block = block->next)
229 Con_Printf ("block:%p size:%7i tag:%3i\n",
230 block, block->size, block->tag);
232 if (block->next == &zone->blocklist)
233 break; // all blocks have been hit
234 if ( (byte *)block + block->size != (byte *)block->next)
235 Con_Printf ("ERROR: block size does not touch the next block\n");
236 if ( block->next->prev != block)
237 Con_Printf ("ERROR: next block doesn't have proper back link\n");
238 if (!block->tag && !block->next->tag)
239 Con_Printf ("ERROR: two consecutive free blocks\n");
245 ========================
247 ========================
249 void Z_CheckHeap (void)
253 for (block = mainzone->blocklist.next ; ; block = block->next)
255 if (block->next == &mainzone->blocklist)
256 break; // all blocks have been hit
257 if ( (byte *)block + block->size != (byte *)block->next)
258 Sys_Error ("Z_CheckHeap: block size does not touch the next block\n");
259 if ( block->next->prev != block)
260 Sys_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
261 if (!block->tag && !block->next->tag)
262 Sys_Error ("Z_CheckHeap: two consecutive free blocks\n");
266 //============================================================================
268 #define HUNK_SENTINAL 0x1df001ed
273 int size; // including sizeof(hunk_t), -1 = not allocated
283 qboolean hunk_tempactive;
286 void R_FreeTextures (void);
292 Run consistancy and sentinal trahing checks
295 void Hunk_Check (void)
299 for (h = (hunk_t *)hunk_base ; (byte *)h != hunk_base + hunk_low_used ; )
301 if (h->sentinal != HUNK_SENTINAL)
302 Sys_Error ("Hunk_Check: trahsed sentinal");
303 if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size)
304 Sys_Error ("Hunk_Check: bad size");
305 h = (hunk_t *)((byte *)h+h->size);
313 If "all" is specified, every single allocation is printed.
314 Otherwise, allocations with the same name will be totaled up before printing.
317 void Hunk_Print (qboolean all)
319 hunk_t *h, *next, *endlow, *starthigh, *endhigh;
329 h = (hunk_t *)hunk_base;
330 endlow = (hunk_t *)(hunk_base + hunk_low_used);
331 starthigh = (hunk_t *)(hunk_base + hunk_size - hunk_high_used);
332 endhigh = (hunk_t *)(hunk_base + hunk_size);
334 Con_Printf (" :%8i total hunk size\n", hunk_size);
335 Con_Printf ("-------------------------\n");
340 // skip to the high hunk if done with low hunk
344 Con_Printf ("-------------------------\n");
345 Con_Printf (" :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used);
346 Con_Printf ("-------------------------\n");
351 // if totally done, break
357 // run consistancy checks
359 if (h->sentinal != HUNK_SENTINAL)
360 Sys_Error ("Hunk_Check: trashed sentinal");
361 if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size)
362 Sys_Error ("Hunk_Check: bad size");
364 next = (hunk_t *)((byte *)h+h->size);
370 // print the single block
372 memcpy (name, h->name, 8);
374 Con_Printf ("%8p :%8i %8s\n",h, h->size, name);
379 if (next == endlow || next == endhigh ||
380 strncmp (h->name, next->name, 8) )
383 Con_Printf (" :%8i %8s (TOTAL)\n",sum, name);
391 Con_Printf ("-------------------------\n");
392 Con_Printf ("%8i total blocks\n", totalblocks);
401 void *Hunk_AllocName (int size, char *name)
410 Sys_Error ("Hunk_Alloc: bad size: %i", size);
412 size = sizeof(hunk_t) + ((size+15)&~15);
414 if (hunk_size - hunk_low_used - hunk_high_used < size)
415 Sys_Error ("Hunk_Alloc: failed on %i bytes",size);
417 h = (hunk_t *)(hunk_base + hunk_low_used);
418 hunk_low_used += size;
420 Cache_FreeLow (hunk_low_used);
425 h->sentinal = HUNK_SENTINAL;
426 strncpy (h->name, name, 8);
428 return (void *)(h+1);
436 void *Hunk_Alloc (int size)
438 return Hunk_AllocName (size, "unknown");
441 int Hunk_LowMark (void)
443 return hunk_low_used;
446 void Hunk_FreeToLowMark (int mark)
448 if (mark < 0 || mark > hunk_low_used)
449 Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark);
450 memset (hunk_base + mark, 0, hunk_low_used - mark);
451 hunk_low_used = mark;
454 int Hunk_HighMark (void)
458 hunk_tempactive = false;
459 Hunk_FreeToHighMark (hunk_tempmark);
462 return hunk_high_used;
465 void Hunk_FreeToHighMark (int mark)
469 hunk_tempactive = false;
470 Hunk_FreeToHighMark (hunk_tempmark);
472 if (mark < 0 || mark > hunk_high_used)
473 Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark);
474 memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark);
475 hunk_high_used = mark;
484 void *Hunk_HighAllocName (int size, char *name)
489 Sys_Error ("Hunk_HighAllocName: bad size: %i", size);
493 Hunk_FreeToHighMark (hunk_tempmark);
494 hunk_tempactive = false;
501 size = sizeof(hunk_t) + ((size+15)&~15);
503 if (hunk_size - hunk_low_used - hunk_high_used < size)
505 Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n",size);
509 hunk_high_used += size;
510 Cache_FreeHigh (hunk_high_used);
512 h = (hunk_t *)(hunk_base + hunk_size - hunk_high_used);
516 h->sentinal = HUNK_SENTINAL;
517 strncpy (h->name, name, 8);
519 return (void *)(h+1);
527 Return space from the top of the hunk
530 void *Hunk_TempAlloc (int size)
534 size = (size+15)&~15;
538 Hunk_FreeToHighMark (hunk_tempmark);
539 hunk_tempactive = false;
542 hunk_tempmark = Hunk_HighMark ();
544 buf = Hunk_HighAllocName (size, "temp");
546 hunk_tempactive = true;
552 ===============================================================================
556 ===============================================================================
559 typedef struct cache_system_s
561 int size; // including this header
564 struct cache_system_s *prev, *next;
565 struct cache_system_s *lru_prev, *lru_next; // for LRU flushing
568 cache_system_t *Cache_TryAlloc (int size, qboolean nobottom);
570 cache_system_t cache_head;
577 void Cache_Move ( cache_system_t *c)
581 // we are clearing up space at the bottom, so only allocate it late
582 new = Cache_TryAlloc (c->size, true);
585 // Con_Printf ("cache_move ok\n");
587 memcpy ( new+1, c+1, c->size - sizeof(cache_system_t) );
589 memcpy (new->name, c->name, sizeof(new->name));
590 Cache_Free (c->user);
591 new->user->data = (void *)(new+1);
595 // Con_Printf ("cache_move failed\n");
597 Cache_Free (c->user); // tough luck...
605 Throw things out until the hunk can be expanded to the given point
608 void Cache_FreeLow (int new_low_hunk)
615 if (c == &cache_head)
616 return; // nothing in cache at all
617 if ((byte *)c >= hunk_base + new_low_hunk)
618 return; // there is space to grow the hunk
619 Cache_Move ( c ); // reclaim the space
627 Throw things out until the hunk can be expanded to the given point
630 void Cache_FreeHigh (int new_high_hunk)
632 cache_system_t *c, *prev;
638 if (c == &cache_head)
639 return; // nothing in cache at all
640 if ( (byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk)
641 return; // there is space to grow the hunk
643 Cache_Free (c->user); // didn't move out of the way
646 Cache_Move (c); // try to move it
652 void Cache_UnlinkLRU (cache_system_t *cs)
654 if (!cs->lru_next || !cs->lru_prev)
655 Sys_Error ("Cache_UnlinkLRU: NULL link");
657 cs->lru_next->lru_prev = cs->lru_prev;
658 cs->lru_prev->lru_next = cs->lru_next;
660 cs->lru_prev = cs->lru_next = NULL;
663 void Cache_MakeLRU (cache_system_t *cs)
665 if (cs->lru_next || cs->lru_prev)
666 Sys_Error ("Cache_MakeLRU: active link");
668 cache_head.lru_next->lru_prev = cs;
669 cs->lru_next = cache_head.lru_next;
670 cs->lru_prev = &cache_head;
671 cache_head.lru_next = cs;
678 Looks for a free block of memory between the high and low hunk marks
679 Size should already include the header and padding
682 cache_system_t *Cache_TryAlloc (int size, qboolean nobottom)
684 cache_system_t *cs, *new;
686 // is the cache completely empty?
688 if (!nobottom && cache_head.prev == &cache_head)
690 if (hunk_size - hunk_high_used - hunk_low_used < size)
691 Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size);
693 new = (cache_system_t *) (hunk_base + hunk_low_used);
694 memset (new, 0, sizeof(*new));
697 cache_head.prev = cache_head.next = new;
698 new->prev = new->next = &cache_head;
704 // search from the bottom up for space
706 new = (cache_system_t *) (hunk_base + hunk_low_used);
707 cs = cache_head.next;
711 if (!nobottom || cs != cache_head.next)
713 if ( (byte *)cs - (byte *)new >= size)
715 memset (new, 0, sizeof(*new));
719 new->prev = cs->prev;
720 cs->prev->next = new;
730 new = (cache_system_t *)((byte *)cs + cs->size);
733 } while (cs != &cache_head);
735 // try to allocate one at the very end
736 if ( hunk_base + hunk_size - hunk_high_used - (byte *)new >= size)
738 memset (new, 0, sizeof(*new));
741 new->next = &cache_head;
742 new->prev = cache_head.prev;
743 cache_head.prev->next = new;
744 cache_head.prev = new;
751 return NULL; // couldn't allocate
758 Throw everything out, so new data will be demand cached
761 void Cache_Flush (void)
763 while (cache_head.next != &cache_head)
764 Cache_Free ( cache_head.next->user ); // reclaim the space
774 void Cache_Print (void)
778 for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next)
780 Con_Printf ("%8i : %s\n", cd->size, cd->name);
790 void Cache_Report (void)
792 Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024*1024) );
801 void Cache_Compact (void)
811 void Cache_Init (void)
813 cache_head.next = cache_head.prev = &cache_head;
814 cache_head.lru_next = cache_head.lru_prev = &cache_head;
816 Cmd_AddCommand ("flush", Cache_Flush);
823 Frees the memory and removes it from the LRU list
826 void Cache_Free (cache_user_t *c)
831 Sys_Error ("Cache_Free: not allocated");
833 cs = ((cache_system_t *)c->data) - 1;
835 cs->prev->next = cs->next;
836 cs->next->prev = cs->prev;
837 cs->next = cs->prev = NULL;
841 Cache_UnlinkLRU (cs);
851 void *Cache_Check (cache_user_t *c)
858 cs = ((cache_system_t *)c->data) - 1;
860 // move to head of LRU
861 Cache_UnlinkLRU (cs);
873 void *Cache_Alloc (cache_user_t *c, int size, char *name)
878 Sys_Error ("Cache_Alloc: allready allocated");
881 Sys_Error ("Cache_Alloc: size %i", size);
883 size = (size + sizeof(cache_system_t) + 15) & ~15;
885 // find memory for it
888 cs = Cache_TryAlloc (size, false);
891 strncpy (cs->name, name, sizeof(cs->name)-1);
892 c->data = (void *)(cs+1);
897 // free the least recently used cahedat
898 if (cache_head.lru_prev == &cache_head)
899 Sys_Error ("Cache_Alloc: out of memory");
900 // not enough memory at all
901 Cache_Free ( cache_head.lru_prev->user );
904 return Cache_Check (c);
907 //============================================================================
910 void HunkList_f(void)
913 if (strcmp(Cmd_Argv(1), "all"))
914 Con_Printf("usage: hunklist [all]\n");
922 ========================
924 ========================
926 void Memory_Init (void *buf, int size)
929 int zonesize = DYNAMIC_SIZE;
937 p = COM_CheckParm ("-zone");
941 zonesize = atoi (com_argv[p+1]) * 1024;
943 Sys_Error ("Memory_Init: you must specify a size in KB after -zone");
945 mainzone = Hunk_AllocName (zonesize, "zone" );
946 Z_ClearZone (mainzone, zonesize);
947 Cmd_AddCommand ("hunklist", HunkList_f);