# HG changeset patch # User Merten Sach # Date 1312370612 -7200 # Node ID def70e32cf2c2716639db9371f19992982d57bde # Parent ca154ebe2b6c685c820ecccf335ddba4ea1c6d75 Malloc with easy shave off diff -r ca154ebe2b6c -r def70e32cf2c VMS.c --- a/VMS.c Tue Aug 02 15:44:28 2011 +0200 +++ b/VMS.c Wed Aug 03 13:23:32 2011 +0200 @@ -678,8 +678,8 @@ //SchedSlot ***allSchedSlots; //ptr to array of ptrs //Before getting rid of everything, print out any measurements made - forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&printHist ); - forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&saveHistToFile); + //forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&printHist ); + //forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&saveHistToFile); //forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, &freeHistExt ); #ifdef MEAS__TIME_PLUGIN printHist( _VMSMasterEnv->reqHdlrLowTimeHist ); diff -r ca154ebe2b6c -r def70e32cf2c vmalloc.c --- a/vmalloc.c Tue Aug 02 15:44:28 2011 +0200 +++ b/vmalloc.c Wed Aug 03 13:23:32 2011 +0200 @@ -17,13 +17,16 @@ #include "VMS.h" #include "Histogram/Histogram.h" +//A MallocProlog is a head element if the HigherInMem variable is NULL +//A Chunk is free if the prevChunkInFreeList variable is NULL + /* * This calculates the container which fits the given size. */ inline uint32 getContainer(size_t size) { - return floor((log10(size)-LOG128)/LOG54); + return (log10(size)-LOG128)/LOG54; } /* @@ -53,23 +56,33 @@ return removedChunk; } +inline +void recycleSmallChunks(MallocProlog** container) +{ + //TODO recycle small chunks +} + /* * Removes a chunk from a free list. */ inline -MallocProlog *extractChunk(MallocProlog* chunk) +void extractChunk(MallocProlog* chunk) { - + chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList; + if(chunk->nextChunkInFreeList) + chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList; } /* * Merges two chunks. - * Chunk A has to be before chunk B in memory. + * Chunk A has to be before chunk B in memory. Both have to be removed from + * a free list */ inline MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB) { - + chunkA->nextHigherInMem = chunkB->nextHigherInMem; + return chunkA; } /* * Inserts a chunk into a free list. @@ -110,6 +123,31 @@ (uintptr_t)chunk - sizeof(MallocProlog); } + +/* + * This makes 5 Chunks of the requested size. + */ +inline +void makeChunks(size_t size, MallocProlog **container) +{ + MallocArrays *freeLists = _VMSMasterEnv->freeLists; + size_t addedSize = 5*(size + sizeof(MallocProlog)); + + uint32 containerIdx = getContainer(addedSize)+4; + while(freeLists->bigChunks[containerIdx] == NULL ) + containerIdx++; + + MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); + + int i; + for(i=0; i<5; i++) + { + insertChunk(divideChunk(foundChunk,size), container); + } + containerIdx = getContainer(getChunkSize(foundChunk)); + insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]); +} + /* * This is sequential code, meant to only be called from the Master, not from * any slave VPs. @@ -123,13 +161,23 @@ #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; - + if(sizeRequested <= LOWER_BOUND) + { + uint32 freeListIdx = (sizeRequested-1)/32; + if(freeList->smallChunkCount[freeListIdx] == 0) + { + makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]); + freeList->smallChunkCount[freeListIdx] += 5; + } + + freeList->smallChunkCount[freeListIdx]--; + return removeChunk(&freeList->smallChunks[freeListIdx]) + 1; + } + //Calculate the expected container. Start one higher to have a Chunk that's //always big enough. uint32 targetContainerIdx = getContainer(sizeRequested); @@ -141,7 +189,7 @@ while(freeList->bigChunks[containerIdx] == NULL) { containerIdx++; - if(containerIdx > freeList->containerCount) + if(containerIdx >= freeList->containerCount) { printf("VMS malloc failed: low memory"); exit(1); @@ -149,23 +197,15 @@ } 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 > sizeRequested + sizeof(MallocProlog)) { - if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog)) - { - MallocProlog *newChunk = divideChunk(foundChunk,containerSize); - insertChunk(newChunk,&freeList->bigChunks[containerIdx]); - chunkSize = getChunkSize(foundChunk); - } - containerIdx--; - containerSize /= CHUNK_INCREASE_RATE; - } + MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested); + containerIdx = getContainer(chunkSize - sizeRequested - sizeof(MallocProlog)); + insertChunk(foundChunk,&freeList->bigChunks[containerIdx]); + foundChunk = newChunk; + } } else { @@ -181,9 +221,9 @@ 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)); + return foundChunk + 1; } /* @@ -201,17 +241,50 @@ #endif //======================================================================== - MallocArrays* freeList = _VMSMasterEnv->freeLists; + MallocArrays* freeLists = _VMSMasterEnv->freeLists; MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1; + uint32 containerIdx; + + size_t chunkSize = getChunkSize(chunkToFree); + if(chunkSize <= LOWER_BOUND) + { + containerIdx = (chunkSize-1)/32; + insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]); + freeLists->smallChunkCount[containerIdx]++; + + if(freeLists->smallChunkCount[containerIdx] > 20) + recycleSmallChunks(&freeLists->smallChunks[containerIdx]); + + return; + } //Check for free neighbors if(chunkToFree->nextLowerInMem) { if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL) {//Chunk is not allocated - mergeChunks() + if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND) + { + extractChunk(chunkToFree->nextLowerInMem); + chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree); + } } } + if(chunkToFree->nextHigherInMem) + { + if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL) + {//Chunk is not allocated + if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND) + { + extractChunk(chunkToFree->nextHigherInMem); + chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem); + } + } + } + + containerIdx = getContainer(chunkSize); + insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]); + //============================= MEASUREMENT STUFF ======================== #ifdef MEAS__TIME_MALLOC saveLowTimeStampCountInto( endStamp ); @@ -298,10 +371,11 @@ (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); memset((void*)freeLists->smallChunks, 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); + memset((void*)freeLists->smallChunkCount, + 0,SMALL_CHUNK_COUNT*sizeof(uint32)); //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; @@ -309,6 +383,7 @@ //Create first element in lastContainer MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE ); if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);} + freeLists->memSpace = firstChunk; firstChunk->nextLowerInMem = NULL; firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk + @@ -334,13 +409,11 @@ /*Designed to be called from the main thread outside of VMS, during cleanup */ void -VMS_ext__free_free_list( MallocProlog *freeListHead ) +VMS_ext__free_free_list( MallocArrays *freeLists ) { - //stashed a ptr to the one and only bug chunk malloc'd from OS in the - // free list head's next lower in mem pointer - free( freeListHead->nextLowerInMem ); - - //don't free the head -- it'll be in an array eventually -- free whole - // array when all the free lists linked from it have already been freed + free(freeLists->memSpace); + free(freeLists->bigChunks); + free(freeLists->smallChunks); + } diff -r ca154ebe2b6c -r def70e32cf2c vmalloc.h --- a/vmalloc.h Tue Aug 02 15:44:28 2011 +0200 +++ b/vmalloc.h Wed Aug 03 13:23:32 2011 +0200 @@ -18,6 +18,8 @@ #define SMALL_CHUNK_COUNT 4 #define LOWER_BOUND 128 #define CHUNK_INCREASE_RATE 1.25 +#define MAX_SMALL_CHUNKS 20 +#define SMALL_CHUNKS_ALLOCATION 5 #define LOG54 0.096910013 #define LOG128 2.10720997 @@ -38,7 +40,9 @@ struct MallocArrays { MallocProlog **smallChunks; + uint32 smallChunkCount[SMALL_CHUNK_COUNT]; MallocProlog **bigChunks; + void *memSpace; uint32 containerCount; }; //MallocArrays @@ -74,6 +78,6 @@ VMS_ext__create_free_list(); void -VMS_ext__free_free_list( MallocProlog *freeListHead ); +VMS_ext__free_free_list(MallocArrays *freeLists ); #endif \ No newline at end of file