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@102: return (log10(size)-LOG128)/LOG54; msach@101: } msach@101: msach@101: /* msach@101: * This calculates the size of a given container msach@101: */ msach@101: inline msach@101: size_t getContainerSize(uint32 idx) msach@101: { msach@101: return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND; 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@101: MallocProlog *removeChunk(MallocProlog** container) msach@101: { msach@101: 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@102: void recycleSmallChunks(MallocProlog** container) msach@102: { msach@102: //TODO recycle small chunks 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@115: if(*(chunk->prevChunkInFreeList) == NULL) msach@115: { msach@115: uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*); msach@115: freeLists->bigChunksSearchVector &= ~(1 << containerIdx); 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@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@101: chunk->nextHigherInMem = newChunk; msach@101: chunk->nextHigherInMem->nextLowerInMem = newChunk; msach@101: msach@101: return newChunk; msach@101: } msach@101: msach@101: inline msach@101: size_t getChunkSize(MallocProlog* chunk) msach@101: { msach@101: return (uintptr_t)chunk->nextHigherInMem - msach@101: (uintptr_t)chunk - sizeof(MallocProlog); msach@101: } msach@101: msach@102: msach@102: /* msach@102: * This makes 5 Chunks of the requested size. msach@102: */ msach@102: inline msach@102: void makeChunks(size_t size, MallocProlog **container) msach@102: { msach@102: MallocArrays *freeLists = _VMSMasterEnv->freeLists; msach@102: size_t addedSize = 5*(size + sizeof(MallocProlog)); msach@102: msach@102: uint32 containerIdx = getContainer(addedSize)+4; msach@102: while(freeLists->bigChunks[containerIdx] == NULL ) msach@102: containerIdx++; msach@102: msach@102: MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); msach@102: msach@102: int i; msach@102: for(i=0; i<5; i++) msach@102: { msach@102: insertChunk(divideChunk(foundChunk,size), container); msach@102: } msach@102: containerIdx = getContainer(getChunkSize(foundChunk)); msach@102: insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]); msach@102: } msach@102: msach@101: /* 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@102: msach@115: MallocArrays* freeLists = _VMSMasterEnv->freeLists; 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@102: uint32 freeListIdx = (sizeRequested-1)/32; msach@115: if(freeLists->smallChunkCount[freeListIdx] == 0) msach@102: { msach@115: makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]); msach@115: freeLists->smallChunkCount[freeListIdx] += 5; msach@102: } msach@102: msach@115: freeLists->smallChunkCount[freeListIdx]--; msach@115: return removeChunk(&freeLists->smallChunks[freeListIdx]) + 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@101: uint32 targetContainerIdx = getContainer(sizeRequested); msach@101: uint32 containerIdx = targetContainerIdx + 1; msach@101: msach@101: MallocProlog* foundChunk; msach@115: if(freeLists->bigChunks[containerIdx] == NULL) msach@101: { msach@115: uint64 searchVector = freeLists->bigChunksSearchVector; msach@115: //set small chunk bits to zero msach@115: searchVector &= MAX_UINT64 << containerIdx; msach@115: containerIdx = __builtin_ffsl(searchVector); msach@115: msach@115: if(containerIdx == 0) msach@115: { msach@115: printf("VMS malloc failed: low memory"); msach@115: exit(1); msach@115: } msach@115: /* msach@101: while(freeList->bigChunks[containerIdx] == NULL) msach@101: { msach@101: containerIdx++; msach@102: if(containerIdx >= freeList->containerCount) msach@101: { msach@101: printf("VMS malloc failed: low memory"); msach@101: exit(1); msach@101: } msach@115: }*/ msach@101: msach@115: foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); msach@101: size_t chunkSize = getChunkSize(foundChunk); msach@101: msach@115: //If the new chunk is larger than the requested size: split msach@115: if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND) msach@101: { msach@102: MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested); msach@115: containerIdx = getContainer(getChunkSize(newChunk)); msach@115: insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]); msach@115: freeLists->bigChunksSearchVector |= 1 << containerIdx; msach@102: foundChunk = newChunk; msach@102: } msach@101: } msach@101: else msach@101: { msach@115: foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); msach@101: } 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: { Me@50: 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@102: msach@102: size_t chunkSize = getChunkSize(chunkToFree); msach@102: if(chunkSize <= LOWER_BOUND) msach@102: { msach@102: containerIdx = (chunkSize-1)/32; msach@102: insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]); msach@102: freeLists->smallChunkCount[containerIdx]++; msach@102: msach@102: if(freeLists->smallChunkCount[containerIdx] > 20) msach@102: recycleSmallChunks(&freeLists->smallChunks[containerIdx]); msach@102: msach@102: return; msach@102: } 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@102: if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND) msach@102: { msach@102: extractChunk(chunkToFree->nextLowerInMem); msach@102: chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree); msach@102: } 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@102: if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND) msach@102: { msach@102: extractChunk(chunkToFree->nextHigherInMem); msach@102: chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem); msach@102: } msach@102: } msach@102: } msach@102: msach@102: containerIdx = getContainer(chunkSize); msach@102: insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]); 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: Me@50: Me@53: /*Allocates memory from the external system -- higher overhead Me@53: * Me@53: *Because of Linux's malloc throwing bizarre random faults when malloc is Me@53: * used inside a VMS virtual processor, have to pass this as a request and Me@53: * have the core loop do it when it gets around to it -- will look for these Me@53: * chores leftover from the previous animation of masterVP the next time it Me@53: * goes to animate the masterVP -- so it takes two separate masterVP Me@53: * animations, separated by work, to complete an external malloc or Me@53: * external free request. Me@53: * Me@53: *Thinking core loop accepts signals -- just looks if signal-location is Me@53: * empty or not -- Me@53: */ Me@53: void * msach@76: VMS__malloc_in_ext( size_t sizeRequested ) Me@53: { Me@53: /* Me@53: //This is running in the master, so no chance for multiple cores to be Me@53: // competing for the core's flag. Me@53: if( *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 ) Me@53: { //something has already signalled to core loop, so save the signal Me@53: // and look, next time master animated, to see if can send it. Me@53: //Note, the addr to put a signal is in the coreloop's frame, so just Me@53: // checks it each time through -- make it volatile to avoid GCC Me@53: // optimizations -- it's a coreloop local var that only changes Me@53: // after jumping away. The signal includes the addr to send the Me@53: //return to -- even if just empty return completion-signal Me@53: // Me@53: //save the signal in some queue that the master looks at each time Me@53: // it starts up -- one loc says if empty for fast common case -- Me@53: //something like that -- want to hide this inside this call -- but Me@53: // think this has to come as a request -- req handler gives procr Me@53: // back to master loop, which gives it back to req handler at point Me@53: // it sees that core loop has sent return signal. Something like Me@53: // that. Me@53: saveTheSignal Me@53: Me@53: } Me@53: coreSigData->type = malloc; Me@53: coreSigData->sizeToMalloc = sizeRequested; Me@53: coreSigData->locToSignalCompletion = &figureOut; Me@53: _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData; Me@53: */ Me@53: //just risk system-stack faults until get this figured out Me@53: return malloc( sizeRequested ); Me@53: } Me@53: Me@53: Me@53: /*Frees memory that was allocated in the external system -- higher overhead Me@53: * Me@53: *As noted in external malloc comment, this is clunky 'cause the free has Me@53: * to be called in the core loop. Me@53: */ Me@53: void Me@53: VMS__free_in_ext( void *ptrToFree ) Me@53: { Me@53: //just risk system-stack faults until get this figured out Me@53: free( ptrToFree ); Me@53: Me@53: //TODO: fix this -- so Me@53: } Me@53: Me@53: Me@50: /*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@102: memset((void*)freeLists->smallChunkCount, msach@102: 0,SMALL_CHUNK_COUNT*sizeof(uint32)); 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 ); Me@50: if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);} msach@102: freeLists->memSpace = firstChunk; msach@79: 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@101: firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1]; Me@53: msach@101: freeLists->bigChunks[container-1] = firstChunk; msach@115: //Insert into bit search list msach@115: freeLists->bigChunksSearchVector |= (1 << (container-1)); 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: