// Emacs style mode select -*- C++ -*- //----------------------------------------------------------------------------- // // $Id: z_zone.c 131 2005-09-24 23:45:18Z fraggle $ // // Copyright(C) 1993-1996 Id Software, Inc. // Copyright(C) 2005 Simon Howard // // 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. // // $Log$ // Revision 1.4 2005/09/24 23:45:18 fraggle // Remove leftover debug code // // Revision 1.3 2005/09/22 12:58:46 fraggle // Use a new PU_FREE tag to mark free blocks, rather than the 'user' field // (avoids using magic numbers to mark allocated blocks with no user) // // Revision 1.2 2005/07/23 16:44:57 fraggle // Update copyright to GNU GPL // // Revision 1.1.1.1 2005/07/23 16:19:55 fraggle // Initial import // // // DESCRIPTION: // Zone Memory Allocation. Neat. // //----------------------------------------------------------------------------- static const char rcsid[] = "$Id: z_zone.c 131 2005-09-24 23:45:18Z fraggle $"; #include "z_zone.h" #include "i_system.h" #include "doomdef.h" // // 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. // // It is of no value to free a cachable block, // because it will get overwritten automatically if needed. // #define ZONEID 0x1d4a11 typedef struct { // total bytes malloced, including header int size; // start / end cap for linked list memblock_t blocklist; memblock_t* rover; } memzone_t; memzone_t* mainzone; // // Z_ClearZone // void Z_ClearZone (memzone_t* zone) { 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.user = (void *)zone; zone->blocklist.tag = PU_STATIC; zone->rover = block; block->prev = block->next = &zone->blocklist; // a free block. block->tag = PU_FREE; block->size = zone->size - sizeof(memzone_t); } // // Z_Init // void Z_Init (void) { memblock_t* block; int size; mainzone = (memzone_t *)I_ZoneBase (&size); mainzone->size = size; // set the entire zone to one free block mainzone->blocklist.next = mainzone->blocklist.prev = block = (memblock_t *)( (byte *)mainzone + sizeof(memzone_t) ); mainzone->blocklist.user = (void *)mainzone; mainzone->blocklist.tag = PU_STATIC; mainzone->rover = block; block->prev = block->next = &mainzone->blocklist; // free block block->tag = PU_FREE; block->size = mainzone->size - sizeof(memzone_t); } // // Z_Free // void Z_Free (void* ptr) { memblock_t* block; memblock_t* other; block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t)); if (block->id != ZONEID) I_Error ("Z_Free: freed a pointer without ZONEID"); if (block->tag != PU_FREE && block->user != NULL) { // clear the user's mark *block->user = 0; } // mark as free block->tag = PU_FREE; block->user = NULL; block->id = 0; other = block->prev; if (other->tag == PU_FREE) { // 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 == PU_FREE) { // 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_Malloc // You can pass a NULL user if the tag is < PU_PURGELEVEL. // #define MINFRAGMENT 64 void* Z_Malloc ( int size, int tag, void* user ) { int extra; memblock_t* start; memblock_t* rover; memblock_t* newblock; memblock_t* base; void *result; size = (size + 3) & ~3; // scan through the block list, // looking for the first free block // of sufficient size, // throwing out any purgable blocks along the way. // account for size of block header size += sizeof(memblock_t); // if there is a free block behind the rover, // back up over them base = mainzone->rover; if (base->prev->tag == PU_FREE) base = base->prev; rover = base; start = base->prev; do { if (rover == start) { // scanned all the way around the list I_Error ("Z_Malloc: failed on allocation of %i bytes", size); } if (rover->tag != PU_FREE) { if (rover->tag < PU_PURGELEVEL) { // hit a block that can't be purged, // so move base past it base = rover = rover->next; } else { // free the rover block (adding the size to base) // the rover can be the base block base = base->prev; Z_Free ((byte *)rover+sizeof(memblock_t)); base = base->next; rover = base->next; } } else { rover = rover->next; } } while (base->tag != PU_FREE || 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 newblock = (memblock_t *) ((byte *)base + size ); newblock->size = extra; newblock->tag = PU_FREE; newblock->user = NULL; newblock->prev = base; newblock->next = base->next; newblock->next->prev = newblock; base->next = newblock; base->size = size; } if (user == NULL && tag >= PU_PURGELEVEL) I_Error ("Z_Malloc: an owner is required for purgable blocks"); base->user = user; base->tag = tag; result = (void *) ((byte *)base + sizeof(memblock_t)); if (base->user) { *base->user = result; } // next allocation will start looking here mainzone->rover = base->next; base->id = ZONEID; return result; } // // Z_FreeTags // void Z_FreeTags ( int lowtag, int hightag ) { memblock_t* block; memblock_t* next; for (block = mainzone->blocklist.next ; block != &mainzone->blocklist ; block = next) { // get link before freeing next = block->next; // free block? if (block->tag == PU_FREE) continue; if (block->tag >= lowtag && block->tag <= hightag) Z_Free ( (byte *)block+sizeof(memblock_t)); } } // // Z_DumpHeap // Note: TFileDumpHeap( stdout ) ? // void Z_DumpHeap ( int lowtag, int hightag ) { memblock_t* block; printf ("zone size: %i location: %p\n", mainzone->size,mainzone); printf ("tag range: %i to %i\n", lowtag, hightag); for (block = mainzone->blocklist.next ; ; block = block->next) { if (block->tag >= lowtag && block->tag <= hightag) printf ("block:%p size:%7i user:%p tag:%3i\n", block, block->size, block->user, block->tag); if (block->next == &mainzone->blocklist) { // all blocks have been hit break; } if ( (byte *)block + block->size != (byte *)block->next) printf ("ERROR: block size does not touch the next block\n"); if ( block->next->prev != block) printf ("ERROR: next block doesn't have proper back link\n"); if (block->tag == PU_FREE && block->next->tag == PU_FREE) printf ("ERROR: two consecutive free blocks\n"); } } // // Z_FileDumpHeap // void Z_FileDumpHeap (FILE* f) { memblock_t* block; fprintf (f,"zone size: %i location: %p\n",mainzone->size,mainzone); for (block = mainzone->blocklist.next ; ; block = block->next) { fprintf (f,"block:%p size:%7i user:%p tag:%3i\n", block, block->size, block->user, block->tag); if (block->next == &mainzone->blocklist) { // all blocks have been hit break; } if ( (byte *)block + block->size != (byte *)block->next) fprintf (f,"ERROR: block size does not touch the next block\n"); if ( block->next->prev != block) fprintf (f,"ERROR: next block doesn't have proper back link\n"); if (block->tag == PU_FREE && block->next->tag == PU_FREE) fprintf (f,"ERROR: two consecutive free blocks\n"); } } // // Z_CheckHeap // void Z_CheckHeap (void) { memblock_t* block; for (block = mainzone->blocklist.next ; ; block = block->next) { if (block->next == &mainzone->blocklist) { // all blocks have been hit break; } if ( (byte *)block + block->size != (byte *)block->next) I_Error ("Z_CheckHeap: block size does not touch the next block\n"); if ( block->next->prev != block) I_Error ("Z_CheckHeap: next block doesn't have proper back link\n"); if (block->tag == PU_FREE && block->next->tag == PU_FREE) I_Error ("Z_CheckHeap: two consecutive free blocks\n"); } } // // Z_ChangeTag // void Z_ChangeTag2 ( void* ptr, int tag ) { memblock_t* block; block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t)); if (block->id != ZONEID) I_Error ("Z_ChangeTag: freed a pointer without ZONEID"); if (tag >= PU_PURGELEVEL && block->user == NULL) I_Error ("Z_ChangeTag: an owner is required for purgable blocks"); block->tag = tag; } // // Z_FreeMemory // int Z_FreeMemory (void) { memblock_t* block; int free; free = 0; for (block = mainzone->blocklist.next ; block != &mainzone->blocklist; block = block->next) { if (block->tag == PU_FREE || block->tag >= PU_PURGELEVEL) free += block->size; } return free; }