# HG changeset patch # User Merten Sach # Date 1312292668 -7200 # Node ID ca154ebe2b6c685c820ecccf335ddba4ea1c6d75 # Parent 5ce4b9beeadbe26297fc0f405c0893f0bb1eaa42 Basic malloc without small chunks diff -r 5ce4b9beeadb -r ca154ebe2b6c VMS.c --- a/VMS.c Tue Jul 26 16:14:30 2011 +0200 +++ b/VMS.c Tue Aug 02 15:44:28 2011 +0200 @@ -105,7 +105,7 @@ //Very first thing put into the master env is the free-list, seeded // with a massive initial chunk of memory. //After this, all other mallocs are VMS__malloc. - _VMSMasterEnv->freeListHead = VMS_ext__create_free_list(); + _VMSMasterEnv->freeLists = VMS_ext__create_free_list(); //============================= MEASUREMENT STUFF ======================== @@ -751,7 +751,7 @@ //======================================================================== */ //These are the only two that use system free - VMS_ext__free_free_list( _VMSMasterEnv->freeListHead ); + VMS_ext__free_free_list( _VMSMasterEnv->freeLists ); free( (void *)_VMSMasterEnv ); } diff -r 5ce4b9beeadb -r ca154ebe2b6c VMS.h --- a/VMS.h Tue Jul 26 16:14:30 2011 +0200 +++ b/VMS.h Tue Aug 02 15:44:28 2011 +0200 @@ -224,7 +224,7 @@ void *semanticEnv; void *OSEventStruc; //for future, when add I/O to BLIS - MallocProlog *freeListHead; + MallocArrays *freeLists; int32 amtOfOutstandingMem; //total currently allocated void *coreLoopReturnPt;//addr to jump to to re-enter coreLoop diff -r 5ce4b9beeadb -r ca154ebe2b6c vmalloc.c --- a/vmalloc.c Tue Jul 26 16:14:30 2011 +0200 +++ b/vmalloc.c Tue Aug 02 15:44:28 2011 +0200 @@ -11,46 +11,188 @@ #include #include #include +#include +#include #include "VMS.h" #include "Histogram/Histogram.h" -/*Helper function - *Insert a newly generated free chunk into the first spot on the free list. - * The chunk is cast as a MallocProlog, so the various pointers in it are - * accessed with C's help -- and the size of the prolog is easily added to - * the pointer when a chunk is returned to the app -- so C handles changes - * in pointer sizes among machines. - * - *The list head is a normal MallocProlog struct -- identified by its - * prevChunkInFreeList being NULL -- the only one. - * - *The end of the list is identified by next chunk being NULL, as usual. +/* + * This calculates the container which fits the given size. */ -void inline -add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead ) - { - chunk->nextChunkInFreeList = listHead->nextChunkInFreeList; - if( chunk->nextChunkInFreeList != NULL ) //if not last in free list - chunk->nextChunkInFreeList->prevChunkInFreeList = chunk; - chunk->prevChunkInFreeList = listHead; - listHead->nextChunkInFreeList = chunk; +inline +uint32 getContainer(size_t size) +{ + return floor((log10(size)-LOG128)/LOG54); +} + +/* + * This calculates the size of a given container + */ +inline +size_t getContainerSize(uint32 idx) +{ + return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND; +} + +/* + * Removes the first chunk of a freeList + * The chunk is removed but not set as free. There is no check if + * the free list is empty, so make sure this is not the case. + */ +inline +MallocProlog *removeChunk(MallocProlog** container) +{ + MallocProlog *removedChunk = *container; + *container = removedChunk->nextChunkInFreeList; + + if(removedChunk->nextChunkInFreeList) + removedChunk->nextChunkInFreeList->prevChunkInFreeList = + (MallocProlog*)container; + + return removedChunk; +} + +/* + * Removes a chunk from a free list. + */ +inline +MallocProlog *extractChunk(MallocProlog* chunk) +{ + +} + +/* + * Merges two chunks. + * Chunk A has to be before chunk B in memory. + */ +inline +MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB) +{ + +} +/* + * Inserts a chunk into a free list. + */ +inline +void insertChunk(MallocProlog* chunk, MallocProlog** container) +{ + chunk->nextChunkInFreeList = *container; + chunk->prevChunkInFreeList = (MallocProlog*)container; + if(*container) + (*container)->prevChunkInFreeList = chunk; + *container = chunk; +} + +/* + * Divides the chunk that a new chunk of newSize is created. + * There is no size check, so make sure the size value is valid. + */ +inline +MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize) +{ + MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem - + newSize - sizeof(MallocProlog)); + + newChunk->nextLowerInMem = chunk; + newChunk->nextHigherInMem = chunk->nextHigherInMem; + + chunk->nextHigherInMem = newChunk; + chunk->nextHigherInMem->nextLowerInMem = newChunk; + + return newChunk; +} + +inline +size_t getChunkSize(MallocProlog* chunk) +{ + return (uintptr_t)chunk->nextHigherInMem - + (uintptr_t)chunk - sizeof(MallocProlog); +} + +/* + * This is sequential code, meant to only be called from the Master, not from + * any slave VPs. + */ +void *VMS__malloc( size_t sizeRequested ) + { + //============================= MEASUREMENT STUFF ======================== + #ifdef MEAS__TIME_MALLOC + int32 startStamp, endStamp; + saveLowTimeStampCountInto( startStamp ); + #endif + //======================================================================== + + MallocArrays* freeList = _VMSMasterEnv->freeLists; + + //Return a small chunk if the requested size is smaller than 128B + //TODO: for now set size to 129B + if(sizeRequested < 128) + sizeRequested = 129; + + //Calculate the expected container. Start one higher to have a Chunk that's + //always big enough. + uint32 targetContainerIdx = getContainer(sizeRequested); + uint32 containerIdx = targetContainerIdx + 1; + + MallocProlog* foundChunk; + if(freeList->bigChunks[containerIdx] == NULL) + { + while(freeList->bigChunks[containerIdx] == NULL) + { + containerIdx++; + if(containerIdx > freeList->containerCount) + { + printf("VMS malloc failed: low memory"); + exit(1); + } + } + + foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); + //Found bigger Element, so we have to divide until it fits the + //requested size + containerIdx--; + size_t containerSize = getContainerSize(containerIdx); + size_t chunkSize = getChunkSize(foundChunk); + + while(containerIdx > targetContainerIdx) + { + if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog)) + { + MallocProlog *newChunk = divideChunk(foundChunk,containerSize); + insertChunk(newChunk,&freeList->bigChunks[containerIdx]); + chunkSize = getChunkSize(foundChunk); + } + containerIdx--; + containerSize /= CHUNK_INCREASE_RATE; + } + } + else + { + foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); + } + + //Mark as allocated + foundChunk->prevChunkInFreeList = NULL; + + //============================= MEASUREMENT STUFF ======================== + #ifdef MEAS__TIME_MALLOC + saveLowTimeStampCountInto( endStamp ); + addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); + #endif + //======================================================================== + + //skip over the prolog by adding its size to the pointer return + return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog)); } - -/*This is sequential code, meant to only be called from the Master, not from +/* + * This is sequential code, meant to only be called from the Master, not from * any slave VPs. - *Search down list, checking size by the nextHigherInMem pointer, to find - * first chunk bigger than size needed. - *Shave off the extra and make it into a new free-list element, hook it in - * then return the address of the found element plus size of prolog. - * - *Will find a */ -void *VMS__malloc( size_t sizeRequested ) - { MallocProlog *foundElem = NULL, *currElem, *newElem; - ssize_t amountExtra, sizeConsumed,sizeOfFound; - uint32 foundElemIsTopOfHeap; +void +VMS__free( void *ptrToFree ) + { //============================= MEASUREMENT STUFF ======================== #ifdef MEAS__TIME_MALLOC @@ -59,312 +201,17 @@ #endif //======================================================================== - //step up the size to be aligned at 16-byte boundary, prob better ways - sizeRequested = (sizeRequested + 16) & ~15; - currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList; - - while( currElem != NULL ) - { //check if size of currElem is big enough - sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem); - amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog); - if( amountExtra > 0 ) - { //found it, get out of loop - foundElem = currElem; - currElem = NULL; + MallocArrays* freeList = _VMSMasterEnv->freeLists; + MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1; + + //Check for free neighbors + if(chunkToFree->nextLowerInMem) + { + if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL) + {//Chunk is not allocated + mergeChunks() } - else - currElem = currElem->nextChunkInFreeList; - } - - if( foundElem == NULL ) - { ERROR("\nmalloc failed\n") - return (void *)NULL; //indicates malloc failed - } - //Using a kludge to identify the element that is the top chunk in the - // heap -- saving top-of-heap addr in head's nextHigherInMem -- and - // save addr of start of heap in head's nextLowerInMem - //Will handle top of Heap specially - foundElemIsTopOfHeap = foundElem->nextHigherInMem == - _VMSMasterEnv->freeListHead->nextHigherInMem; - - //before shave off and try to insert new elem, remove found elem - //note, foundElem will never be the head, so always has valid prevChunk - foundElem->prevChunkInFreeList->nextChunkInFreeList = - foundElem->nextChunkInFreeList; - if( foundElem->nextChunkInFreeList != NULL ) - { foundElem->nextChunkInFreeList->prevChunkInFreeList = - foundElem->prevChunkInFreeList; - } - foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated - - //if enough, turn extra into new elem & insert it - if( amountExtra > 64 ) - { //make new elem by adding to addr of curr elem then casting - sizeConsumed = sizeof(MallocProlog) + sizeRequested; - newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed ); - newElem->nextLowerInMem = foundElem; //This is evil (but why?) - newElem->nextHigherInMem = foundElem->nextHigherInMem; //This is evil (but why?) - foundElem->nextHigherInMem = newElem; - if( ! foundElemIsTopOfHeap ) - { //there is no next higher for top of heap, so can't write to it - newElem->nextHigherInMem->nextLowerInMem = newElem; - } - add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead ); - } - else - { - sizeConsumed = sizeOfFound; - } - _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed; - - //============================= MEASUREMENT STUFF ======================== - #ifdef MEAS__TIME_MALLOC - saveLowTimeStampCountInto( endStamp ); - addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); - #endif - //======================================================================== - - //skip over the prolog by adding its size to the pointer return - return (void*)((uintptr_t)foundElem + sizeof(MallocProlog)); - } - -/*This is sequential code, meant to only be called from the Master, not from - * any slave VPs. - *Search down list, checking size by the nextHigherInMem pointer, to find - * first chunk bigger than size needed. - *Shave off the extra and make it into a new free-list element, hook it in - * then return the address of the found element plus size of prolog. - * - * The difference to the regular malloc is, that all the allocated chunks are - * aligned and padded to the size of a CACHE_LINE. Thus creating a new chunk - * before the aligned chunk. - */ -void *VMS__malloc_aligned( size_t sizeRequested ) - { MallocProlog *foundElem = NULL, *currElem, *newElem; - ssize_t amountExtra, sizeConsumed,sizeOfFound,prevAmount; - uint32 foundElemIsTopOfHeap; - - //============================= MEASUREMENT STUFF ======================== - #ifdef MEAS__TIME_MALLOC - uint32 startStamp, endStamp; - saveLowTimeStampCountInto( startStamp ); - #endif - //======================================================================== - - //step up the size to be multiple of the cache line size - sizeRequested = (sizeRequested + CACHE_LINE) & ~(CACHE_LINE-1); - currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList; - - while( currElem != NULL ) - { //check if size of currElem is big enough - sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem); - amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog); - if( amountExtra > 0 ) - { - //look if the found element is already aligned - if((((uintptr_t)currElem+sizeof(MallocProlog)) & (uintptr_t)(CACHE_LINE-1)) == 0){ - //found it, get out of loop - foundElem = currElem; - break; - }else{ - //find first aligned address and check if it's still big enough - //check also if the space before the aligned address is big enough - //for a new element - void *firstAlignedAddr = (void*)(((uintptr_t)currElem + 2*CACHE_LINE) & ~((uintptr_t)(CACHE_LINE-1))); - prevAmount = (uintptr_t)firstAlignedAddr - (uintptr_t)currElem; - sizeOfFound=(uintptr_t)currElem->nextHigherInMem -(uintptr_t)firstAlignedAddr + sizeof(MallocProlog); - amountExtra= sizeOfFound - sizeRequested - sizeof(MallocProlog); - if(prevAmount > 2*sizeof(MallocProlog) && amountExtra > 0 ){ - //found suitable element - //create new previous element and exit loop - MallocProlog *newAlignedElem = (MallocProlog*)firstAlignedAddr - 1; - - //insert new element into free list - if(currElem->nextChunkInFreeList != NULL) - currElem->nextChunkInFreeList->prevChunkInFreeList = newAlignedElem; - newAlignedElem->prevChunkInFreeList = currElem; - newAlignedElem->nextChunkInFreeList = currElem->nextChunkInFreeList; - currElem->nextChunkInFreeList = newAlignedElem; - - //set higherInMem and lowerInMem - newAlignedElem->nextHigherInMem = currElem->nextHigherInMem; - foundElemIsTopOfHeap = currElem->nextHigherInMem == - _VMSMasterEnv->freeListHead->nextHigherInMem; - if(!foundElemIsTopOfHeap) - currElem->nextHigherInMem->nextLowerInMem = newAlignedElem; - currElem->nextHigherInMem = newAlignedElem; - newAlignedElem->nextLowerInMem = currElem; - - //Found new element leaving loop - foundElem = newAlignedElem; - break; - } - } - - } - currElem = currElem->nextChunkInFreeList; - } - - if( foundElem == NULL ) - { ERROR("\nmalloc failed\n") - return (void *)NULL; //indicates malloc failed - } - //Using a kludge to identify the element that is the top chunk in the - // heap -- saving top-of-heap addr in head's nextHigherInMem -- and - // save addr of start of heap in head's nextLowerInMem - //Will handle top of Heap specially - foundElemIsTopOfHeap = foundElem->nextHigherInMem == - _VMSMasterEnv->freeListHead->nextHigherInMem; - - //before shave off and try to insert new elem, remove found elem - //note, foundElem will never be the head, so always has valid prevChunk - foundElem->prevChunkInFreeList->nextChunkInFreeList = - foundElem->nextChunkInFreeList; - if( foundElem->nextChunkInFreeList != NULL ) - { foundElem->nextChunkInFreeList->prevChunkInFreeList = - foundElem->prevChunkInFreeList; - } - foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated - - //if enough, turn extra into new elem & insert it - if( amountExtra > 64 ) - { //make new elem by adding to addr of curr elem then casting - sizeConsumed = sizeof(MallocProlog) + sizeRequested; - newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed ); - newElem->nextHigherInMem = foundElem->nextHigherInMem; - newElem->nextLowerInMem = foundElem; - foundElem->nextHigherInMem = newElem; - - if( ! foundElemIsTopOfHeap ) - { //there is no next higher for top of heap, so can't write to it - newElem->nextHigherInMem->nextLowerInMem = newElem; - } - add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead ); - } - else - { - sizeConsumed = sizeOfFound; - } - _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed; - - //============================= MEASUREMENT STUFF ======================== - #ifdef MEAS__TIME_MALLOC - saveLowTimeStampCountInto( endStamp ); - addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); - #endif - //======================================================================== - - //skip over the prolog by adding its size to the pointer return - return (void*)((uintptr_t)foundElem + sizeof(MallocProlog)); - } - - -/*This is sequential code -- only to be called from the Master - * When free, subtract the size of prolog from pointer, then cast it to a - * MallocProlog. Then check the nextLower and nextHigher chunks to see if - * one or both are also free, and coalesce if so, and if neither free, then - * add this one to free-list. - */ -void -VMS__free( void *ptrToFree ) - { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem; - size_t sizeOfElem; - uint32 lowerExistsAndIsFree, higherExistsAndIsFree; - - //============================= MEASUREMENT STUFF ======================== - #ifdef MEAS__TIME_MALLOC - int32 startStamp, endStamp; - saveLowTimeStampCountInto( startStamp ); - #endif - //======================================================================== - - if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem || - ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem ) - { //outside the range of data owned by VMS's malloc, so do nothing - return; - } - //subtract size of prolog to get pointer to prolog, then cast - elemToFree = (MallocProlog *)((uintptr_t)ptrToFree - sizeof(MallocProlog)); - sizeOfElem =(size_t)((uintptr_t)elemToFree->nextHigherInMem-(uintptr_t)elemToFree); - - if( elemToFree->prevChunkInFreeList != NULL ) - { printf( "error: freeing same element twice!" ); exit(1); - } - - _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem; - - nextLowerElem = elemToFree->nextLowerInMem; - nextHigherElem = elemToFree->nextHigherInMem; - - if( nextHigherElem == NULL ) - higherExistsAndIsFree = FALSE; - else //okay exists, now check if in the free-list by checking back ptr - higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL); - - if( nextLowerElem == NULL ) - lowerExistsAndIsFree = FALSE; - else //okay, it exists, now check if it's free - lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL); - - - //now, know what exists and what's free - if( lowerExistsAndIsFree ) - { if( higherExistsAndIsFree ) - { //both exist and are free, so coalesce all three - //First, remove higher from free-list - nextHigherElem->prevChunkInFreeList->nextChunkInFreeList = - nextHigherElem->nextChunkInFreeList; - if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list? - nextHigherElem->nextChunkInFreeList->prevChunkInFreeList = - nextHigherElem->prevChunkInFreeList; - //Now, fix-up sequence-in-mem list -- by side-effect, this also - // changes size of the lower elem, which is still in free-list - nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem; - if( nextHigherElem->nextHigherInMem != - _VMSMasterEnv->freeListHead->nextHigherInMem ) - nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem; - //notice didn't do anything to elemToFree -- it simply is no - // longer reachable from any of the lists. Wonder if could be a - // security leak because left valid addresses in it, - // but don't care for now. - } - else - { //lower is the only of the two that exists and is free, - //In this case, no adjustment to free-list, just change mem-list. - // By side-effect, changes size of the lower elem - nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem; - if( elemToFree->nextHigherInMem != - _VMSMasterEnv->freeListHead->nextHigherInMem ) - elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem; - } - } - else - { //lower either doesn't exist or isn't free, so check higher - if( higherExistsAndIsFree ) - { //higher exists and is the only of the two free - //First, in free-list, replace higher elem with the one to free - elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList; - elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList; - elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree; - if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list? - elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree; - //Now chg mem-list. By side-effect, changes size of elemToFree - elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem; - if( elemToFree->nextHigherInMem != - _VMSMasterEnv->freeListHead->nextHigherInMem ) - elemToFree->nextHigherInMem->nextLowerInMem = elemToFree; - } - else - { //neither lower nor higher is availabe to coalesce so add to list - // this makes prev chunk ptr non-null, which indicates it's free - elemToFree->nextChunkInFreeList = - _VMSMasterEnv->freeListHead->nextChunkInFreeList; - _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree; - if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list? - elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree; - elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead; - } - } + } //============================= MEASUREMENT STUFF ======================== #ifdef MEAS__TIME_MALLOC saveLowTimeStampCountInto( endStamp ); @@ -440,43 +287,47 @@ /*Designed to be called from the main thread outside of VMS, during init */ -MallocProlog * +MallocArrays * VMS_ext__create_free_list() - { MallocProlog *freeListHead, *firstChunk; - - //Note, this is running in the main thread -- all increases in malloc - // mem and all frees of it must be done in this thread, with the - // thread's original stack available - freeListHead = malloc( sizeof(MallocProlog) ); - firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE ); +{ + //Initialize containers for small chunks and fill with zeros + _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) ); + MallocArrays *freeLists = _VMSMasterEnv->freeLists; + + freeLists->smallChunks = + (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); + memset((void*)freeLists->smallChunks, + 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); + + //Calculate number of containers for big chunks + uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1; + + freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*)); + memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*)); + freeLists->containerCount = container; + + //Create first element in lastContainer + MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE ); if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);} - //Touch memory to avoid page faults - void *ptr,*endPtr; - endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE; - for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE) - { - *(char*)ptr = 0; - } - - freeListHead->prevChunkInFreeList = NULL; - //Use this addr to free the heap when cleanup - freeListHead->nextLowerInMem = firstChunk; - //to identify top-of-heap elem, compare this addr to elem's next higher - freeListHead->nextHigherInMem = (void*)( (uintptr_t)firstChunk + - MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE); - freeListHead->nextChunkInFreeList = firstChunk; - - firstChunk->nextChunkInFreeList = NULL; - firstChunk->prevChunkInFreeList = freeListHead; - //next Higher has to be set to top of chunk, so can calc size in malloc - firstChunk->nextHigherInMem = (void*)( (uintptr_t)firstChunk + - MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE); - firstChunk->nextLowerInMem = NULL; //identifies as bott of heap + firstChunk->nextLowerInMem = NULL; + firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk + + MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*)); + firstChunk->nextChunkInFreeList = NULL; + //previous element in the queue is the container + firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1]; - _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet - - return freeListHead; + freeLists->bigChunks[container-1] = firstChunk; + + //Create dummy chunk to mark the top of stack this is of course + //never freed + MallocProlog *dummyChunk = firstChunk->nextHigherInMem; + dummyChunk->nextHigherInMem = dummyChunk+1; + dummyChunk->nextLowerInMem = NULL; + dummyChunk->nextChunkInFreeList = NULL; + dummyChunk->prevChunkInFreeList = NULL; + + return freeLists; } diff -r 5ce4b9beeadb -r ca154ebe2b6c vmalloc.h --- a/vmalloc.h Tue Jul 26 16:14:30 2011 +0200 +++ b/vmalloc.h Tue Aug 02 15:44:28 2011 +0200 @@ -14,6 +14,14 @@ #include #include "VMS_primitive_data_types.h" +#define SMALL_CHUNK_SIZE 32 +#define SMALL_CHUNK_COUNT 4 +#define LOWER_BOUND 128 +#define CHUNK_INCREASE_RATE 1.25 + +#define LOG54 0.096910013 +#define LOG128 2.10720997 + typedef struct _MallocProlog MallocProlog; struct _MallocProlog @@ -24,6 +32,16 @@ MallocProlog *nextLowerInMem; }; //MallocProlog + + typedef struct MallocArrays MallocArrays; + + struct MallocArrays + { + MallocProlog **smallChunks; + MallocProlog **bigChunks; + uint32 containerCount; + }; + //MallocArrays typedef struct { @@ -52,7 +70,7 @@ VMS__free_in_ext( void *ptrToFree ); -MallocProlog * +MallocArrays * VMS_ext__create_free_list(); void