Mercurial > repos > rhope
diff runtime/fixed_alloc.c @ 41:1b86a1ee500a
Added faster allocator for small objects
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Sat, 10 Oct 2009 16:40:50 -0400 |
parents | |
children | a24eb366195c |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/runtime/fixed_alloc.c Sat Oct 10 16:40:50 2009 -0400 @@ -0,0 +1,153 @@ +#include "fixed_alloc.h" +#include <stdlib.h> + +uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE]; + +void fixed_alloc_init() +{ + int i; + for(i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; ++i) + max_free[i] = (BLOCK_SIZE - sizeof(mem_block)+1)*8/((i*STRIDE+MIN_SIZE)*8+1); +} + +mem_manager * new_mem_manager() +{ + int i; + mem_manager * ret = malloc(sizeof(mem_manager)); + memset(ret, 0, sizeof(mem_manager)); + return ret; +} + +void * falloc(size_t size, mem_manager * manager) +{ + uint16_t i,bit; + uint16_t bucket; + mem_block * block,*temp; + if(size > MAX_SIZE) + return malloc(size); + //puts("falloc"); + size = ADJUST_SIZE(size); + bucket = (size-MIN_SIZE)/STRIDE; + block = manager->inuse[bucket]; + if(!block) + { + block = manager->freelist; + if(block) + { + --manager->freecount; + manager->freelist = block->next; + } + else + { + block = block_alloc(BLOCK_SIZE); + } + manager->inuse[bucket] = block; + block->next = NULL; + block->last = NULL; + block->numfree = max_free[bucket]; + block->firstfree = 0; + memset(block->bitmap, 0xFF, max_free[bucket]/8+1); + } + //printf("block: %X,numfree: %d, firstfree: %d, maxfree: %d\n", block, block->numfree, block->firstfree, max_free[bucket]); + /*if(block->numfree > max_free[bucket]) + { + puts("uh oh!"); + exit(1); + }*/ + //find first free + i = block->firstfree; + while(!block->bitmap[i]) + ++i; + //printf("i:%d,bitmap:%X\n", i, block->bitmap[i]); + bit = 0; + while(!((1 << bit) & block->bitmap[i])) + ++bit; + //update free bitmask + block->bitmap[i] ^= 1 << bit; + //If current bitmap has no more free elements, set firstfree to the next bitmap + if(!block->bitmap[i]) + block->firstfree = i+1; + else + block->firstfree = i; + --block->numfree; + if(!block->numfree) + { + //Remove from linked list if there are no more free elements + manager->inuse[bucket] = block->next; + if(block->next) + block->next->last = block->last; + } + i = i*8+bit; + //printf("%X\n", ((char *)block)+BLOCK_SIZE-((i+1)*size)); + return (void *)(((char *)block)+BLOCK_SIZE-((i+1)*size)); +} + +void ffree(void * ptr, size_t size, mem_manager * manager) +{ + mem_block * block,*temp; + uint16_t i,bit,bucket; + if(size > MAX_SIZE) + { + free(ptr); + return; + } + //puts("ffree"); + size = ADJUST_SIZE(size); + block = GET_BLOCK(ptr); + i = (((((char *)block) + BLOCK_SIZE) - ((char *)ptr))/size)-1; + bit = i & 0x7; + i = (i&0xFFFFFFF8) >> 3; + //printf("ptr:%X,block:%X,i:%d,bit:%d\n", ptr,block,bit,i); + block->bitmap[i] |= 1 << bit; + if(i < block->firstfree) + block->firstfree = i; + ++block->numfree; + bucket = (size-MIN_SIZE)/STRIDE; + //printf("numfree:%d,max_free:%d,last:%X,next:%X\n", block->numfree, max_free[bucket], block->last, block->next); + /*if(block->numfree > max_free[bucket]) + { + puts("uh oh!"); + exit(1); + }*/ + if(block->numfree == max_free[bucket]) + { + //Block is now unused, remove it from the inuse list + if(block->last) + block->last->next = block->next; + else + manager->inuse[bucket] = block->next; + if(block->next) + block->next->last = block->last; + if(manager->freecount == MAX_FREE) + block_free(block, BLOCK_SIZE); + else + { + block->next = manager->freelist; + manager->freelist = block; + ++manager->freecount; + } + } else if(block->numfree == 1) { + //Block was previously full, add it to the inuse list + block->next = manager->inuse[bucket]; + block->last = NULL; + manager->inuse[bucket] = block; + if(block->next) + block->next->last = block; + } else if(block->next && block->next->numfree < block->numfree) { + //We want to use more filled blockes before less filled ones + //so we can return empty ones to the OS more often + //so if we now have more free nodes in this block than the + //next one swap them + temp = block->next; + block->next = temp->next; + temp->last = block->last; + block->last = temp; + temp->next = block; + if(block->next) + block->next->last = block; + if(temp->last) + temp->last->next = temp; + else + manager->inuse[bucket] = temp; + } +}