/* Copyright (C) 1996-1997 Id Software, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "cmd.h" #include "common.h" #include "console.h" #include "mathlib.h" #include "quakedef.h" #include "sys.h" #include "zone.h" #define DYNAMIC_SIZE 0x40000 /* 256k */ #define ZONEID 0x1d4a11 #define MINFRAGMENT 64 typedef struct memblock_s { int size; /* including the header and possibly tiny fragments */ int tag; /* a tag of 0 is a free block */ int id; /* should be ZONEID */ struct memblock_s *next, *prev; int pad; /* pad to 64 bit boundary */ } memblock_t; typedef struct { int size; /* total bytes malloced, including header */ memblock_t blocklist; /* start/end cap for linked list */ memblock_t *rover; } memzone_t; static void Cache_FreeLow(int new_low_hunk); static void Cache_FreeHigh(int new_high_hunk); /* * ============================================================================ * * ZONE MEMORY ALLOCATION * * There is never any space between memblocks, and there will never be two * contiguous free memblocks. * * The rover can be left pointing at a non-empty block * * The zone calls are pretty much only used for small strings and structures, * all big things are allocated on the hunk. * ============================================================================ */ static memzone_t *mainzone; static void Z_ClearZone(memzone_t *zone, int size); /* * ======================== * Z_ClearZone * ======================== */ static void Z_ClearZone(memzone_t *zone, int size) { memblock_t *block; /* * set the entire zone to one free block */ zone->blocklist.next = zone->blocklist.prev = block = (memblock_t *)((byte *)zone + sizeof(memzone_t)); zone->blocklist.tag = 1; /* in use block */ zone->blocklist.id = 0; zone->blocklist.size = 0; zone->rover = block; block->prev = block->next = &zone->blocklist; block->tag = 0; /* free block */ block->id = ZONEID; block->size = size - sizeof(memzone_t); } /* * ======================== * Z_Free * ======================== */ void Z_Free(void *ptr) { memblock_t *block, *other; if (!ptr) Sys_Error("%s: NULL pointer", __func__); block = (memblock_t *) ((byte *)ptr - sizeof(memblock_t)); if (block->id != ZONEID) Sys_Error("%s: freed a pointer without ZONEID", __func__); if (block->tag == 0) Sys_Error("%s: freed a freed pointer", __func__); block->tag = 0; /* mark as free */ other = block->prev; if (!other->tag) { /* merge with previous free block */ other->size += block->size; other->next = block->next; other->next->prev = other; if (block == mainzone->rover) mainzone->rover = other; block = other; } other = block->next; if (!other->tag) { /* merge the next free block onto the end */ block->size += other->size; block->next = other->next; block->next->prev = block; if (other == mainzone->rover) mainzone->rover = block; } } /* * ======================== * Z_CheckHeap * ======================== */ static void Z_CheckHeap(void) { memblock_t *block; for (block = mainzone->blocklist.next;; block = block->next) { if (block->next == &mainzone->blocklist) break; /* all blocks have been hit */ if ((byte *)block + block->size != (byte *)block->next) Sys_Error("%s: block size does not touch the next block", __func__); if (block->next->prev != block) Sys_Error("%s: next block doesn't have proper back link", __func__); if (!block->tag && !block->next->tag) Sys_Error("%s: two consecutive free blocks", __func__); } } static void * Z_TagMalloc(int size, int tag) { int extra; memblock_t *start, *rover, *new, *base; if (!tag) Sys_Error("%s: tried to use a 0 tag", __func__); /* * Scan through the block list looking for the first free block of * sufficient size */ size += sizeof(memblock_t); /* account for size of block header */ size += 4; /* space for memory trash tester */ size = (size + 7) & ~7; /* align to 8-byte boundary */ base = rover = mainzone->rover; start = base->prev; do { if (rover == start) /* scaned all the way around the list */ return NULL; if (rover->tag) base = rover = rover->next; else rover = rover->next; } while (base->tag || base->size < size); /* * found a block big enough */ extra = base->size - size; if (extra > MINFRAGMENT) { /* there will be a free fragment after the allocated block */ new = (memblock_t *) ((byte *)base + size); new->size = extra; new->tag = 0; /* free block */ new->prev = base; new->id = ZONEID; new->next = base->next; new->next->prev = new; base->next = new; base->size = size; } base->tag = tag; /* no longer a free block */ mainzone->rover = base->next; /* next allocation starts looking here */ base->id = ZONEID; /* marker for memory trash testing */ *(int *)((byte *)base + base->size - 4) = ZONEID; return (void *)((byte *)base + sizeof(memblock_t)); } /* * ======================== * Z_Malloc * ======================== */ void * Z_Malloc(int size) { void *buf; Z_CheckHeap(); /* DEBUG */ buf = Z_TagMalloc(size, 1); if (!buf) Sys_Error("%s: failed on allocation of %i bytes", __func__, size); memset(buf, 0, size); return buf; } /* * ======================== * Z_Realloc * ======================== */ void * Z_Realloc(void *ptr, int size) { memblock_t *block; int orig_size; void *ret; if (!ptr) return Z_Malloc(size); block = (memblock_t *)((byte *)ptr - sizeof(memblock_t)); if (block->id != ZONEID) Sys_Error("%s: realloced a pointer without ZONEID", __func__); if (!block->tag) Sys_Error("%s: realloced a freed pointer", __func__); orig_size = block->size; orig_size -= sizeof(memblock_t); orig_size -= 4; Z_Free(ptr); ret = Z_TagMalloc(size, 1); if (!ret) Sys_Error("%s: failed on allocation of %i bytes", __func__, size); if (ret != ptr) memmove(ret, ptr, qmin(orig_size, size)); return ret; } /* FIXME - unused; Make a console command? */ #if 0 /* * ======================== * Z_Print * ======================== */ static void Z_Print(memzone_t * zone) { memblock_t *block; Con_Printf("zone size: %i location: %p\n", mainzone->size, mainzone); for (block = zone->blocklist.next;; block = block->next) { Con_Printf("block:%p size:%7i tag:%3i\n", block, block->size, block->tag); if (block->next == &zone->blocklist) break; /* all blocks have been hit */ if ((byte *)block + block->size != (byte *)block->next) Con_Printf("ERROR: block size does not touch the next block\n"); if (block->next->prev != block) Con_Printf("ERROR: next block doesn't have proper back link\n"); if (!block->tag && !block->next->tag) Con_Printf("ERROR: two consecutive free blocks\n"); } } #endif /* ======================================================================= */ #define HUNK_SENTINAL 0x1df001ed typedef struct { int sentinal; int size; /* including sizeof(hunk_t), -1 = not allocated */ char name[8]; } hunk_t; static byte *hunk_base; static int hunk_size; static int hunk_low_used; static int hunk_high_used; static qboolean hunk_tempactive; static int hunk_tempmark; /* * ============== * Hunk_Check * * Run consistancy and sentinal trashing checks * ============== */ void Hunk_Check(void) { hunk_t *h; for (h = (hunk_t *) hunk_base; (byte *)h != hunk_base + hunk_low_used;) { if (h->sentinal != HUNK_SENTINAL) Sys_Error("%s: trashed sentinal", __func__); if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size) Sys_Error("%s: bad size", __func__); h = (hunk_t *) ((byte *)h + h->size); } } /* FIXME - unused; Make a console command? */ #if 0 /* * ============== * Hunk_Print * * If "all" is specified, every single allocation is printed. * Otherwise, allocations with the same name will be totaled up before * printing. * ============== */ static void Hunk_Print(qboolean all) { hunk_t *h, *next, *endlow, *starthigh, *endhigh; int count, sum; int totalblocks; char name[9]; name[8] = 0; count = 0; sum = 0; totalblocks = 0; h = (hunk_t *) hunk_base; endlow = (hunk_t *) (hunk_base + hunk_low_used); starthigh = (hunk_t *) (hunk_base + hunk_size - hunk_high_used); endhigh = (hunk_t *) (hunk_base + hunk_size); Con_Printf(" :%8i total hunk size\n", hunk_size); Con_Printf("-------------------------\n"); while (1) { /* * skip to the high hunk if done with low hunk */ if (h == endlow) { Con_Printf("-------------------------\n"); Con_Printf(" :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used); Con_Printf("-------------------------\n"); h = starthigh; } /* * if totally done, break */ if (h == endhigh) break; /* * run consistancy checks */ if (h->sentinal != HUNK_SENTINAL) Sys_Error("%s: trahsed sentinal", __func__); if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size) Sys_Error("%s: bad size", __func__); next = (hunk_t *) ((byte *)h + h->size); count++; totalblocks++; sum += h->size; /* * print the single block */ memcpy(name, h->name, 8); if (all) Con_Printf("%8p :%8i %8s\n", h, h->size, name); /* * print the total */ if (next == endlow || next == endhigh || strncmp(h->name, next->name, 8)) { if (!all) Con_Printf(" :%8i %8s (TOTAL)\n", sum, name); count = 0; sum = 0; } h = next; } Con_Printf("-------------------------\n"); Con_Printf("%8i total blocks\n", totalblocks); } #endif /* * =================== * Hunk_AllocName * =================== */ void * Hunk_AllocName(int size, char *name) { hunk_t *h; #ifdef PARANOID Hunk_Check(); #endif if (size < 0) Sys_Error("%s: bad size: %i", __func__, size); size = sizeof(hunk_t) + ((size + 15) & ~15); if (hunk_size - hunk_low_used - hunk_high_used < size) { /* Sys_Error ("%s: failed on %i bytes", __func__, size); */ #ifdef _WIN32 Sys_Error("Not enough RAM allocated. Try starting using " "\"-heapsize 16000\" on the command line."); #else Sys_Error("Not enough RAM allocated. Try starting using " "\"-mem 16\" on the command line."); #endif } h = (hunk_t *) (hunk_base + hunk_low_used); hunk_low_used += size; Cache_FreeLow(hunk_low_used); memset(h, 0, size); h->size = size; h->sentinal = HUNK_SENTINAL; strncpy(h->name, name, 8); return (void *)(h + 1); } /* * =================== * Hunk_Alloc * =================== */ void * Hunk_Alloc(int size) { return Hunk_AllocName(size, "unknown"); } int Hunk_LowMark(void) { return hunk_low_used; } void Hunk_FreeToLowMark(int mark) { if (mark < 0 || mark > hunk_low_used) Sys_Error("%s: bad mark %i", __func__, mark); memset(hunk_base + mark, 0, hunk_low_used - mark); hunk_low_used = mark; } int Hunk_HighMark(void) { if (hunk_tempactive) { hunk_tempactive = false; Hunk_FreeToHighMark(hunk_tempmark); } return hunk_high_used; } void Hunk_FreeToHighMark(int mark) { if (hunk_tempactive) { hunk_tempactive = false; Hunk_FreeToHighMark(hunk_tempmark); } if (mark < 0 || mark > hunk_high_used) Sys_Error("%s: bad mark %i", __func__, mark); memset(hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark); hunk_high_used = mark; } /* * =================== * Hunk_HighAllocName * =================== */ void * Hunk_HighAllocName(int size, char *name) { hunk_t *h; if (size < 0) Sys_Error("%s: bad size: %i", __func__, size); if (hunk_tempactive) { Hunk_FreeToHighMark(hunk_tempmark); hunk_tempactive = false; } #ifdef PARANOID Hunk_Check(); #endif size = sizeof(hunk_t) + ((size + 15) & ~15); if (hunk_size - hunk_low_used - hunk_high_used < size) { Con_Printf("Hunk_HighAlloc: failed on %i bytes\n", size); return NULL; } hunk_high_used += size; Cache_FreeHigh(hunk_high_used); h = (hunk_t *) (hunk_base + hunk_size - hunk_high_used); memset(h, 0, size); h->size = size; h->sentinal = HUNK_SENTINAL; strncpy(h->name, name, 8); return (void *)(h + 1); } /* * ================= * Hunk_TempAlloc * * Return space from the top of the hunk * ================= */ void * Hunk_TempAlloc(int size) { void *buf; size = (size + 15) & ~15; if (hunk_tempactive) { Hunk_FreeToHighMark(hunk_tempmark); hunk_tempactive = false; } hunk_tempmark = Hunk_HighMark(); buf = Hunk_HighAllocName(size, "temp"); hunk_tempactive = true; return buf; } /* * ===================== * Hunk_TempAllocExtend * * Extend the existing temp hunk allocation. * Size is the number of extra bytes required * ===================== */ void * Hunk_TempAllocExtend(int size) { hunk_t *old, *new; if (!hunk_tempactive) Sys_Error("%s: temp hunk not active"); old = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); if (old->sentinal != HUNK_SENTINAL) Sys_Error("%s: old sentinal trashed\n", __func__); if (strncmp(old->name, "temp", 8)) Sys_Error("%s: old hunk name trashed\n", __func__); size = (size + 15) & ~15; if (hunk_size - hunk_low_used - hunk_high_used < size) { Con_Printf("%s: failed on %i bytes\n", __func__, size); return NULL; } hunk_high_used += size; Cache_FreeHigh(hunk_high_used); new = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); memmove(new, old, sizeof(hunk_t)); new->size += size; return (void *)(new + 1); } /* * =========================================================================== * * CACHE MEMORY * * =========================================================================== */ typedef struct cache_system_s { int size; /* including this header */ cache_user_t *user; char name[16]; struct cache_system_s *prev, *next; struct cache_system_s *lru_prev, *lru_next; /* for LRU flushing */ } cache_system_t; static cache_system_t cache_head; static cache_system_t *Cache_TryAlloc(int size, qboolean nobottom); /* * =========== * Cache_Move * =========== */ static void Cache_Move(cache_system_t *c) { cache_system_t *new; /* we are clearing up space at the bottom, so only allocate it late */ new = Cache_TryAlloc(c->size, true); if (new) { memcpy(new + 1, c + 1, c->size - sizeof(cache_system_t)); new->user = c->user; memcpy(new->name, c->name, sizeof(new->name)); Cache_Free(c->user); new->user->data = (void *)(new + 1); } else { /* tough luck... */ Cache_Free(c->user); } } /* * ============ * Cache_FreeLow * * Throw things out until the hunk can be expanded to the given point * ============ */ static void Cache_FreeLow(int new_low_hunk) { cache_system_t *c; while (1) { c = cache_head.next; if (c == &cache_head) return; /* nothing in cache at all */ if ((byte *)c >= hunk_base + new_low_hunk) return; /* there is space to grow the hunk */ Cache_Move(c); /* reclaim the space */ } } /* * ============ * Cache_FreeHigh * * Throw things out until the hunk can be expanded to the given point * ============ */ static void Cache_FreeHigh(int new_high_hunk) { cache_system_t *c, *prev; prev = NULL; while (1) { c = cache_head.prev; if (c == &cache_head) return; /* nothing in cache at all */ if ((byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk) return; /* there is space to grow the hunk */ if (c == prev) Cache_Free(c->user); /* didn't move out of the way */ else { Cache_Move(c); /* try to move it */ prev = c; } } } static void Cache_UnlinkLRU(cache_system_t *cs) { if (!cs->lru_next || !cs->lru_prev) Sys_Error("%s: NULL link", __func__); cs->lru_next->lru_prev = cs->lru_prev; cs->lru_prev->lru_next = cs->lru_next; cs->lru_prev = cs->lru_next = NULL; } static void Cache_MakeLRU(cache_system_t *cs) { if (cs->lru_next || cs->lru_prev) Sys_Error("%s: active link", __func__); cache_head.lru_next->lru_prev = cs; cs->lru_next = cache_head.lru_next; cs->lru_prev = &cache_head; cache_head.lru_next = cs; } /* * ============ * Cache_TryAlloc * * Looks for a free block of memory between the high and low hunk marks * Size should already include the header and padding * ============ */ static cache_system_t * Cache_TryAlloc(int size, qboolean nobottom) { cache_system_t *cs, *new; /* is the cache completely empty? */ if (!nobottom && cache_head.prev == &cache_head) { if (hunk_size - hunk_high_used - hunk_low_used < size) Sys_Error("%s: %i is greater then free hunk", __func__, size); new = (cache_system_t *) (hunk_base + hunk_low_used); memset(new, 0, sizeof(*new)); new->size = size; cache_head.prev = cache_head.next = new; new->prev = new->next = &cache_head; Cache_MakeLRU(new); return new; } /* search from the bottom up for space */ new = (cache_system_t *) (hunk_base + hunk_low_used); cs = cache_head.next; do { if (!nobottom || cs != cache_head.next) { if ((byte *)cs - (byte *)new >= size) { /* found space */ memset(new, 0, sizeof(*new)); new->size = size; new->next = cs; new->prev = cs->prev; cs->prev->next = new; cs->prev = new; Cache_MakeLRU(new); return new; } } /* continue looking */ new = (cache_system_t *) ((byte *)cs + cs->size); cs = cs->next; } while (cs != &cache_head); /* try to allocate one at the very end */ if (hunk_base + hunk_size - hunk_high_used - (byte *)new >= size) { memset(new, 0, sizeof(*new)); new->size = size; new->next = &cache_head; new->prev = cache_head.prev; cache_head.prev->next = new; cache_head.prev = new; Cache_MakeLRU(new); return new; } return NULL; /* couldn't allocate */ } /* * ============ * Cache_Flush * * Throw everything out, so new data will be demand cached * ============ */ void Cache_Flush(void) { while (cache_head.next != &cache_head) Cache_Free(cache_head.next->user); /* reclaim the space */ } /* FIXME - Unused? */ #if 0 /* * ============ * Cache_Print * ============ */ static void Cache_Print(void) { cache_system_t *cd; for (cd = cache_head.next; cd != &cache_head; cd = cd->next) { Con_Printf("%8i : %s\n", cd->size, cd->name); } } #endif /* * ============ * Cache_Report * ============ */ void Cache_Report(void) { Con_DPrintf("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024 * 1024)); } /* FIXME - Unused? */ #if 0 /* * ============ * Cache_Compact * ============ */ static void Cache_Compact(void) { } #endif /* * ============ * Cache_Init * ============ */ static void Cache_Init(void) { cache_head.next = cache_head.prev = &cache_head; cache_head.lru_next = cache_head.lru_prev = &cache_head; } /* * ============== * Cache_Free * * Frees the memory and removes it from the LRU list * ============== */ void Cache_Free(cache_user_t *c) { cache_system_t *cs; if (!c->data) Sys_Error("%s: not allocated", __func__); cs = ((cache_system_t *) c->data) - 1; cs->prev->next = cs->next; cs->next->prev = cs->prev; cs->next = cs->prev = NULL; c->data = NULL; Cache_UnlinkLRU(cs); } /* * ============== * Cache_Check * ============== */ void * Cache_Check(cache_user_t *c) { cache_system_t *cs; if (!c->data) return NULL; cs = ((cache_system_t *) c->data) - 1; /* move to head of LRU */ Cache_UnlinkLRU(cs); Cache_MakeLRU(cs); return c->data; } /* * ============== * Cache_Alloc * ============== */ void * Cache_Alloc(cache_user_t *c, int size, char *name) { cache_system_t *cs; if (c->data) Sys_Error("%s: allready allocated", __func__); if (size <= 0) Sys_Error("%s: size %i", __func__, size); size = (size + sizeof(cache_system_t) + 15) & ~15; /* find memory for it */ while (1) { cs = Cache_TryAlloc(size, false); if (cs) { strncpy(cs->name, name, sizeof(cs->name) - 1); c->data = (void *)(cs + 1); cs->user = c; break; } /* free the least recently used cahedat */ if (cache_head.lru_prev == &cache_head) Sys_Error("%s: out of memory", __func__); /* not enough memory at all */ Cache_Free(cache_head.lru_prev->user); } return Cache_Check(c); } /* ========================================================================= */ /* * ======================== * Memory_Init * ======================== */ void Memory_Init(void *buf, int size) { int p; int zonesize = DYNAMIC_SIZE; hunk_base = buf; hunk_size = size; hunk_low_used = 0; hunk_high_used = 0; Cache_Init(); p = COM_CheckParm("-zone"); if (p) { if (p < com_argc - 1) zonesize = Q_atoi(com_argv[p + 1]) * 1024; else Sys_Error("%s: you must specify a size in KB after -zone", __func__); } mainzone = Hunk_AllocName(zonesize, "zone"); Z_ClearZone(mainzone, zonesize); /* Needs to be added after the zone init... */ Cmd_AddCommand("flush", Cache_Flush); }