Me@50: /* Me@50: * Copyright 2009 OpenSourceCodeStewardshipFoundation.org Me@50: * Licensed under GNU General Public License version 2 Me@50: * Me@50: * Author: seanhalle@yahoo.com Me@50: * Me@50: * Created on November 14, 2009, 9:07 PM Me@50: */ Me@50: Me@50: #include msach@76: #include Me@53: #include msach@76: #include msach@101: #include msach@101: #include Me@50: Me@50: #include "VMS.h" Me@68: #include "Histogram/Histogram.h" Me@50: msach@115: #define MAX_UINT64 0xFFFFFFFFFFFFFFFF msach@115: msach@102: //A MallocProlog is a head element if the HigherInMem variable is NULL msach@102: //A Chunk is free if the prevChunkInFreeList variable is NULL msach@102: msach@101: /* msach@101: * This calculates the container which fits the given size. Me@50: */ msach@101: inline msach@101: uint32 getContainer(size_t size) msach@101: { msach@118: return (log2(size)-LOG128)/LOG54; msach@101: } msach@101: msach@101: /* msach@101: * Removes the first chunk of a freeList msach@101: * The chunk is removed but not set as free. There is no check if msach@101: * the free list is empty, so make sure this is not the case. msach@101: */ msach@101: inline msach@116: MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx) msach@101: { msach@116: MallocProlog** container = &freeLists->bigChunks[containerIdx]; msach@116: MallocProlog* removedChunk = *container; msach@116: *container = removedChunk->nextChunkInFreeList; msach@116: msach@116: if(removedChunk->nextChunkInFreeList) msach@116: removedChunk->nextChunkInFreeList->prevChunkInFreeList = msach@116: (MallocProlog*)container; msach@116: msach@116: if(*container == NULL) msach@116: { msach@116: if(containerIdx < 64) msach@116: freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); msach@116: else msach@116: freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); msach@116: } msach@116: msach@116: return removedChunk; msach@116: } msach@116: msach@116: /* msach@116: * Removes the first chunk of a freeList msach@116: * The chunk is removed but not set as free. There is no check if msach@116: * the free list is empty, so make sure this is not the case. msach@116: */ msach@116: inline msach@116: MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx) msach@116: { msach@116: MallocProlog** container = &freeLists->smallChunks[containerIdx]; msach@116: MallocProlog* removedChunk = *container; msach@101: *container = removedChunk->nextChunkInFreeList; msach@101: msach@101: if(removedChunk->nextChunkInFreeList) msach@101: removedChunk->nextChunkInFreeList->prevChunkInFreeList = msach@101: (MallocProlog*)container; msach@101: msach@101: return removedChunk; msach@101: } msach@101: msach@102: inline msach@117: size_t getChunkSize(MallocProlog* chunk) msach@102: { msach@117: return (uintptr_t)chunk->nextHigherInMem - msach@117: (uintptr_t)chunk - sizeof(MallocProlog); msach@102: } msach@102: msach@101: /* msach@101: * Removes a chunk from a free list. msach@101: */ msach@101: inline msach@115: void extractChunk(MallocProlog* chunk, MallocArrays *freeLists) msach@101: { msach@102: chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList; msach@102: if(chunk->nextChunkInFreeList) msach@102: chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList; msach@116: msach@116: //The last element in the list points to the container. If the container points msach@116: //to NULL the container is empty msach@125: if(*((void**)(chunk->prevChunkInFreeList)) == NULL && getChunkSize(chunk) >= BIG_LOWER_BOUND); msach@115: { msach@117: //Find the approppiate container because we do not know it msach@117: uint64 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 3; msach@116: if(containerIdx < (uint32)64) msach@116: freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); msach@116: if(containerIdx < 128 && containerIdx >=64) msach@116: freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); msach@117: msach@115: } msach@101: } msach@101: msach@101: /* msach@101: * Merges two chunks. msach@102: * Chunk A has to be before chunk B in memory. Both have to be removed from msach@102: * a free list msach@101: */ msach@101: inline msach@101: MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB) msach@101: { msach@102: chunkA->nextHigherInMem = chunkB->nextHigherInMem; msach@117: chunkB->nextHigherInMem->nextLowerInMem = chunkA; msach@102: return chunkA; msach@101: } msach@101: /* msach@101: * Inserts a chunk into a free list. msach@101: */ msach@101: inline msach@101: void insertChunk(MallocProlog* chunk, MallocProlog** container) msach@101: { msach@101: chunk->nextChunkInFreeList = *container; msach@101: chunk->prevChunkInFreeList = (MallocProlog*)container; msach@101: if(*container) msach@101: (*container)->prevChunkInFreeList = chunk; msach@101: *container = chunk; msach@101: } msach@101: msach@101: /* msach@101: * Divides the chunk that a new chunk of newSize is created. msach@101: * There is no size check, so make sure the size value is valid. msach@101: */ msach@101: inline msach@101: MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize) msach@101: { msach@101: MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem - msach@101: newSize - sizeof(MallocProlog)); msach@101: msach@101: newChunk->nextLowerInMem = chunk; msach@101: newChunk->nextHigherInMem = chunk->nextHigherInMem; msach@101: msach@117: chunk->nextHigherInMem->nextLowerInMem = newChunk; msach@101: chunk->nextHigherInMem = newChunk; msach@101: msach@101: return newChunk; msach@101: } msach@101: msach@117: /* msach@117: * Search for chunk in the list of big chunks. Split the block if it's too big msach@117: */ msach@101: inline msach@117: MallocProlog *searchChunk(MallocArrays *freeLists, size_t sizeRequested, uint32 containerIdx) msach@101: { msach@117: MallocProlog* foundChunk; msach@117: msach@117: uint64 searchVector = freeLists->bigChunksSearchVector[0]; msach@117: //set small chunk bits to zero msach@117: searchVector &= MAX_UINT64 << containerIdx; msach@117: containerIdx = __builtin_ffsl(searchVector); msach@117: msach@117: if(containerIdx == 0) msach@117: { msach@117: searchVector = freeLists->bigChunksSearchVector[1]; msach@117: containerIdx = __builtin_ffsl(searchVector); msach@117: if(containerIdx == 0) msach@117: { msach@117: printf("VMS malloc failed: low memory"); msach@117: exit(1); msach@117: } msach@117: containerIdx += 64; msach@117: } msach@117: containerIdx--; msach@117: msach@117: msach@117: foundChunk = removeChunk(freeLists, containerIdx); msach@117: size_t chunkSize = getChunkSize(foundChunk); msach@117: msach@117: //If the new chunk is larger than the requested size: split msach@125: if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + BIG_LOWER_BOUND) msach@117: { msach@117: MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested); msach@117: containerIdx = getContainer(getChunkSize(foundChunk)) - 1; msach@117: insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]); msach@117: if(containerIdx < 64) msach@117: freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx); msach@117: else msach@117: freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64)); msach@117: foundChunk = newChunk; msach@117: } msach@117: msach@117: return foundChunk; msach@101: } msach@101: msach@102: msach@102: /* msach@101: * This is sequential code, meant to only be called from the Master, not from msach@101: * any slave VPs. msach@101: */ msach@101: void *VMS__malloc( size_t sizeRequested ) msach@101: { msach@101: //============================= MEASUREMENT STUFF ======================== msach@101: #ifdef MEAS__TIME_MALLOC msach@101: int32 startStamp, endStamp; msach@101: saveLowTimeStampCountInto( startStamp ); msach@101: #endif msach@101: //======================================================================== msach@101: msach@115: MallocArrays* freeLists = _VMSMasterEnv->freeLists; msach@117: MallocProlog* foundChunk; msach@101: msach@101: //Return a small chunk if the requested size is smaller than 128B msach@102: if(sizeRequested <= LOWER_BOUND) msach@102: { msach@117: uint32 freeListIdx = (sizeRequested-1)/SMALL_CHUNK_SIZE; msach@117: if(freeLists->smallChunks[freeListIdx] == NULL) msach@117: foundChunk = searchChunk(freeLists, SMALL_CHUNK_SIZE*(freeListIdx+1), 0); msach@117: else msach@117: foundChunk = removeSmallChunk(freeLists, freeListIdx); msach@102: msach@117: //Mark as allocated msach@117: foundChunk->prevChunkInFreeList = NULL; msach@117: return foundChunk + 1; msach@102: } msach@102: msach@101: //Calculate the expected container. Start one higher to have a Chunk that's msach@101: //always big enough. msach@117: uint32 containerIdx = getContainer(sizeRequested); msach@101: msach@115: if(freeLists->bigChunks[containerIdx] == NULL) msach@117: foundChunk = searchChunk(freeLists, sizeRequested, containerIdx); msach@101: else msach@117: foundChunk = removeChunk(freeLists, containerIdx); msach@101: msach@101: //Mark as allocated msach@101: foundChunk->prevChunkInFreeList = NULL; msach@101: msach@101: //============================= MEASUREMENT STUFF ======================== msach@101: #ifdef MEAS__TIME_MALLOC msach@101: saveLowTimeStampCountInto( endStamp ); msach@101: addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); msach@101: #endif msach@101: //======================================================================== msach@102: msach@101: //skip over the prolog by adding its size to the pointer return msach@102: return foundChunk + 1; Me@50: } Me@50: msach@101: /* msach@101: * This is sequential code, meant to only be called from the Master, not from Me@50: * any slave VPs. Me@50: */ msach@101: void msach@101: VMS__free( void *ptrToFree ) msach@101: { msach@117: Me@65: //============================= MEASUREMENT STUFF ======================== Me@65: #ifdef MEAS__TIME_MALLOC Me@65: int32 startStamp, endStamp; Me@65: saveLowTimeStampCountInto( startStamp ); Me@65: #endif Me@65: //======================================================================== Me@65: msach@102: MallocArrays* freeLists = _VMSMasterEnv->freeLists; msach@101: MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1; msach@102: uint32 containerIdx; msach@101: msach@101: //Check for free neighbors msach@101: if(chunkToFree->nextLowerInMem) msach@101: { msach@101: if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL) msach@101: {//Chunk is not allocated msach@117: extractChunk(chunkToFree->nextLowerInMem, freeLists); msach@117: chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree); Me@50: } msach@101: } msach@102: if(chunkToFree->nextHigherInMem) msach@102: { msach@102: if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL) msach@102: {//Chunk is not allocated msach@117: extractChunk(chunkToFree->nextHigherInMem, freeLists); msach@117: chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem); msach@102: } msach@102: } msach@117: msach@117: size_t chunkSize = getChunkSize(chunkToFree); msach@125: if(chunkSize < BIG_LOWER_BOUND) msach@117: { msach@117: containerIdx = (chunkSize/SMALL_CHUNK_SIZE)-1; msach@125: if(containerIdx > SMALL_CHUNK_COUNT-1) msach@125: containerIdx = SMALL_CHUNK_COUNT-1; msach@117: insertChunk(chunkToFree, &freeLists->smallChunks[containerIdx]); msach@117: } msach@116: else msach@117: { msach@117: containerIdx = getContainer(getChunkSize(chunkToFree)) - 1; msach@117: insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]); msach@117: if(containerIdx < 64) msach@117: freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx; msach@117: else msach@117: freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64); msach@117: } msach@102: Me@65: //============================= MEASUREMENT STUFF ======================== Me@65: #ifdef MEAS__TIME_MALLOC Me@65: saveLowTimeStampCountInto( endStamp ); Me@65: addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->freeTimeHist ); Me@65: #endif Me@65: //======================================================================== Me@50: Me@50: } Me@50: msach@117: /* msach@117: * Designed to be called from the main thread outside of VMS, during init Me@50: */ msach@101: MallocArrays * Me@53: VMS_ext__create_free_list() msach@101: { msach@101: //Initialize containers for small chunks and fill with zeros msach@101: _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) ); msach@101: MallocArrays *freeLists = _VMSMasterEnv->freeLists; msach@101: msach@101: freeLists->smallChunks = msach@101: (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); msach@101: memset((void*)freeLists->smallChunks, msach@101: 0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*)); msach@101: msach@101: //Calculate number of containers for big chunks msach@101: uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1; msach@101: freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*)); msach@101: memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*)); msach@101: freeLists->containerCount = container; msach@101: msach@101: //Create first element in lastContainer msach@101: MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE ); msach@117: if( firstChunk == NULL ) {printf("Can't allocate initial memory\n"); exit(1);} msach@102: freeLists->memSpace = firstChunk; msach@79: msach@126: //Touch memory to avoid page faults msach@126: void *ptr,*endPtr; msach@126: endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE; msach@126: for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE) msach@126: { msach@126: *(char*)ptr = 0; msach@126: } msach@126: msach@101: firstChunk->nextLowerInMem = NULL; msach@101: firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk + msach@101: MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*)); msach@101: firstChunk->nextChunkInFreeList = NULL; msach@101: //previous element in the queue is the container msach@117: firstChunk->prevChunkInFreeList = &freeLists->bigChunks[container-2]; Me@53: msach@117: freeLists->bigChunks[container-2] = firstChunk; msach@115: //Insert into bit search list msach@117: if(container <= 65) msach@117: freeLists->bigChunksSearchVector[0] |= ((uint64)1 << (container-2)); msach@116: else msach@117: freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (container-66)); msach@101: msach@101: //Create dummy chunk to mark the top of stack this is of course msach@101: //never freed msach@101: MallocProlog *dummyChunk = firstChunk->nextHigherInMem; msach@101: dummyChunk->nextHigherInMem = dummyChunk+1; msach@101: dummyChunk->nextLowerInMem = NULL; msach@101: dummyChunk->nextChunkInFreeList = NULL; msach@101: dummyChunk->prevChunkInFreeList = NULL; msach@101: msach@101: return freeLists; Me@50: } Me@50: Me@50: Me@50: /*Designed to be called from the main thread outside of VMS, during cleanup Me@50: */ Me@50: void msach@102: VMS_ext__free_free_list( MallocArrays *freeLists ) Me@50: { msach@102: free(freeLists->memSpace); msach@102: free(freeLists->bigChunks); msach@102: free(freeLists->smallChunks); msach@102: Me@50: } Me@50: