Mercurial > repos > rhope
view runtime/fixed_alloc.c @ 180:c40e0faa1c92
Add Call to Dict and List
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Sun, 19 Jun 2011 10:43:11 -0700 |
parents | 72c648bca43b |
children |
line wrap: on
line source
#include "fixed_alloc.h" #include "object.h" #include <stdlib.h> #include <string.h> #include <stdio.h> uint16_t max_free[(MAX_SIZE-MIN_SIZE)/STRIDE+1]; void fixed_alloc_init() { int i; for(i = 0; i < ((MAX_SIZE-MIN_SIZE)/STRIDE+1); ++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 print_mem_info(mem_manager * manager) { int i,count,freeobjs; mem_block * cur; //printf("Free blocks: %d\n", manager->freecount); if (manager->fullcount) printf("Full Blocks: %d\n", manager->fullcount); for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++) { count = 0; freeobjs = 0; cur = manager->inuse[i]; while(cur) { count++; freeobjs += ((int)cur->numfree); cur = cur->next; } if (freeobjs) printf("Bucket %d(size: %d) has %d blocks in use with %d free slots out of %d\n", i, i*STRIDE+MIN_SIZE,count, freeobjs, max_free[i]*count); } fflush(stdout); } void find_live_objects_oftype(mem_manager * manager, int32_t type_id, void ** output) { object * obj; mem_block * cur; int32_t i,j,bitslots,bit,outpos=0; for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++) { cur = manager->inuse[i]; while(cur) { bitslots = max_free[i]/8; if(max_free[i]&7) ++bitslots; for(j = 0; j < bitslots; ++j) if(cur->bitmap[j] != 0xFF) { for (bit = 0; bit < 8; ++bit) { if (!(cur->bitmap[j] & (1 << bit))) { obj = (object *)(((char *)cur)+BLOCK_SIZE-(((j*8+bit)+1)*(i*STRIDE+MIN_SIZE))); if(obj->bprint->type_id == type_id) output[outpos++] = obj; } } } cur = cur->next; } } } void get_live_object_counts(mem_manager * manager, int32_t * counts) { object * obj; mem_block * cur; int32_t i,j,bitslots,bit; memset(counts, 0, sizeof(int32_t)*max_registered_type); for (i = 0; i < (MAX_SIZE-MIN_SIZE)/STRIDE; i++) { cur = manager->inuse[i]; while(cur) { bitslots = max_free[i]/8; if(max_free[i]&7) ++bitslots; for(j = 0; j < bitslots; ++j) if(cur->bitmap[j] != 0xFF) { for (bit = 0; bit < 8; ++bit) { if (!(cur->bitmap[j] & (1 << bit))) { obj = (object *)(((char *)cur)+BLOCK_SIZE-(((j*8+bit)+1)*(i*STRIDE+MIN_SIZE))); counts[obj->bprint->type_id]++; } } } cur = cur->next; } } } void print_live_object_types(mem_manager * manager) { int32_t i,*counts = malloc(sizeof(int32_t)*max_registered_type); get_live_object_counts(manager, counts); for (i = 0; i < max_registered_type; ++i) if(counts[i]) printf("%d live objects of type %d\n", counts[i], i); fflush(stdout); } 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; //memset(block, 0xCD, BLOCK_SIZE); } else { block = block_alloc(BLOCK_SIZE); //memset(block, 0xAB, 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; manager->fullcount++; if(block->next) block->next->last = block->last; } i = i*8+bit; 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); //memset(ptr, 0xEF, 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; manager->fullcount--; 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; } }