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: msach@141: #define NDEBUG msach@141: #include msach@141: msach@134: #include "VMS.h" msach@140: #include "vmalloc.h" Me@68: #include "Histogram/Histogram.h" Me@50: msach@115: #define MAX_UINT64 0xFFFFFFFFFFFFFFFF msach@115: msach@141: msach@141: msach@135: inline void msach@135: sendFreeReqst_lib(int receiverID, void *ptrToFree, VirtProcr *animPr); msach@135: msach@135: inline void msach@135: sendFreeReqst_master(int receiverID, void *ptrToFree); msach@135: msach@141: void VMS__check_free_list(MallocArrays *freeLists); msach@141: 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@141: assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0); msach@141: msach@116: if(*container == NULL) msach@116: { msach@116: if(containerIdx < 64) msach@141: { msach@141: assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0); msach@116: freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); msach@141: } msach@116: else msach@141: { msach@141: assert((freeLists->bigChunksSearchVector[1] & ((uint64)1 << (containerIdx-64))) != 0); msach@116: freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); msach@141: } 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@141: if(((*((void**)(chunk->prevChunkInFreeList))) == NULL) && (getChunkSize(chunk) >= BIG_LOWER_BOUND)) msach@115: { msach@141: assert((*((void**)(chunk->prevChunkInFreeList))) == NULL); 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@140: if(containerIdx < (uint64)64) msach@141: { msach@141: assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0); msach@116: freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); msach@141: } msach@116: if(containerIdx < 128 && containerIdx >=64) msach@141: { msach@141: assert((freeLists->bigChunksSearchVector[1] & ((uint64)1 << (containerIdx-64))) != 0); msach@116: freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); msach@141: } 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@141: containerIdx--; // ffsl index starts at 1 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@141: assert(freeLists->bigChunks[containerIdx] == foundChunk); msach@141: assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << containerIdx)) != 0); msach@117: foundChunk = newChunk; msach@117: } msach@117: msach@117: return foundChunk; msach@101: } Me@50: msach@132: /* msach@132: * This function is called by code which is part of the master loop. msach@132: * This reads the animating coreID from the MasterEnv and calls the normal malloc msach@132: * in VMS__malloc_on_core msach@132: */ msach@132: void * msach@132: VMS__malloc( size_t sizeRequested) msach@132: { msach@132: return VMS__malloc_on_core(sizeRequested, _VMSMasterEnv->currentMasterProcrID); msach@132: } Me@50: msach@132: /* msach@132: * This is called by the plugin. This call to VMS_malloc_on_core is run on the msach@132: * slave VPs stack so there is no switch to the VMS runtime. msach@132: */ msach@132: void * msach@132: VMS__malloc_in_lib(size_t sizeRequested, VirtProcr *VProcr) msach@132: { msach@132: return VMS__malloc_on_core(sizeRequested, VProcr->coreAnimatedBy); msach@132: } msach@132: msach@132: /* msach@101: * This is sequential code, meant to only be called from the Master, not from msach@101: * any slave VPs. Me@50: */ msach@139: void *VMS__malloc_on_core( size_t sizeRequested, int procrID ) msach@101: { 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@139: MallocArrays* freeLists = _VMSMasterEnv->freeLists[procrID]; msach@117: MallocProlog* foundChunk; msach@139: MallocPrologAllocated* returnChunk; msach@78: 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@140: _VMSMasterEnv->amtOfOutstandingMem -= getChunkSize(foundChunk) + sizeof(MallocProlog); msach@139: returnChunk = (MallocPrologAllocated*)foundChunk; msach@139: returnChunk->prevChunkInFreeList = NULL;//indicates elem currently allocated msach@140: returnChunk->procrID = procrID; msach@139: return returnChunk + 1; msach@102: } msach@78: 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@78: msach@115: if(freeLists->bigChunks[containerIdx] == NULL) msach@117: foundChunk = searchChunk(freeLists, sizeRequested, containerIdx); msach@78: else msach@117: foundChunk = removeChunk(freeLists, containerIdx); msach@101: msach@101: //Mark as allocated msach@140: _VMSMasterEnv->amtOfOutstandingMem -= getChunkSize(foundChunk) + sizeof(MallocProlog); msach@139: returnChunk = (MallocPrologAllocated*)foundChunk; msach@139: returnChunk->prevChunkInFreeList = NULL;//indicates elem currently allocated msach@139: returnChunk->procrID = procrID; msach@101: msach@78: //============================= MEASUREMENT STUFF ======================== msach@78: #ifdef MEAS__TIME_MALLOC msach@78: saveLowTimeStampCountInto( endStamp ); msach@78: addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist ); msach@78: #endif msach@78: //======================================================================== msach@141: assert(getChunkSize((MallocProlog*)returnChunk)>=sizeRequested); msach@102: msach@101: //skip over the prolog by adding its size to the pointer return msach@139: return returnChunk + 1; msach@78: } msach@139: msach@139: /* msach@132: * This free is called for a master loop. It decides whether the allocation of msach@132: * chunk was done on the same core. If it was it calls VMS__free_on_core msach@132: * otherwise it sends a message to the responsible core. msach@78: */ msach@132: void msach@132: VMS__free(void *ptrToFree) msach@132: { msach@134: MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1; msach@132: if(chunk->procrID == _VMSMasterEnv->currentMasterProcrID) msach@132: { msach@132: VMS__free_on_core(ptrToFree, _VMSMasterEnv->currentMasterProcrID); msach@132: } msach@132: else msach@132: { msach@135: sendFreeReqst_master(chunk->procrID, ptrToFree); msach@135: msach@132: } msach@132: } msach@78: msach@132: /* msach@132: * This free is called for the plugins. It decides whether the allocation of msach@132: * chunk was done on the same core. If it was it calls VMS__free_on_core msach@132: * otherwise it sends a message to the responsible core. msach@132: */ msach@132: void msach@132: VMS__free_in_lib(void *ptrToFree, VirtProcr *VProc) msach@132: { msach@134: MallocPrologAllocated *chunk = (MallocPrologAllocated*)ptrToFree - 1; msach@132: if(chunk->procrID == VProc->coreAnimatedBy) msach@132: { msach@132: VMS__free_on_core(ptrToFree, VProc->coreAnimatedBy); msach@78: } msach@132: else msach@132: { msach@135: sendFreeReqst_lib(chunk->procrID, ptrToFree, VProc); Me@50: } msach@132: } Me@50: msach@135: /* msach@135: * This is called form a masterVP and request an free from a different masterVP. msach@135: * The free of the request structure is done after the request is handled. msach@135: */ msach@135: inline void msach@135: sendFreeReqst_master(int receiverID, void *ptrToFree) msach@135: { msach@135: InterVMSCoreReqst *freeReqst = VMS__malloc(sizeof(InterVMSCoreReqst)); msach@135: freeReqst->freePtr = ptrToFree; msach@135: freeReqst->secondReqType = transfer_free_ptr; msach@141: msach@141: VMS__sendInterMasterReqst(receiverID, (InterMasterReqst*)freeReqst); msach@135: } msach@135: msach@135: /* msach@135: * This is called if the free is called from the plugin. This requests an inter msach@135: * master request from his master. msach@135: */ msach@135: inline void msach@135: sendFreeReqst_lib(int receiverID, void *ptrToFree, VirtProcr *animPr ) msach@135: { msach@135: VMSSemReq reqData; msach@135: InterVMSCoreReqst *freeReqst = VMS__malloc(sizeof(InterVMSCoreReqst)); msach@135: freeReqst->freePtr = ptrToFree; msach@135: freeReqst->secondReqType = transfer_free_ptr; msach@135: msach@135: reqData.reqType = interMasterReqst; msach@135: reqData.receiverID = receiverID; msach@135: reqData.data = (void*)freeReqst; msach@135: msach@135: VMS__send_VMSSem_request( (void*)&reqData, animPr ); msach@135: } msach@135: msach@141: void VMS__check_free_list(MallocArrays *freeLists) msach@141: { msach@141: int idx; msach@141: for(idx=0; idx< freeLists->containerCount; idx++) msach@141: { msach@141: if(freeLists->bigChunks[idx]) msach@141: assert((freeLists->bigChunksSearchVector[0] & ((uint64)1 << idx)) != 0); msach@141: if((freeLists->bigChunksSearchVector[0] & ((uint64)1 << idx))) msach@141: assert(freeLists->bigChunks[idx] != NULL); msach@141: } msach@141: } msach@141: msach@101: /* msach@101: * This is sequential code, meant to only be called from the Master, not from msach@82: * any slave VPs. Me@50: */ Me@50: void msach@139: VMS__free_on_core( void *ptrToFree, int procrID ) 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: //======================================================================== msach@134: msach@139: MallocArrays* freeLists = _VMSMasterEnv->freeLists[procrID]; msach@101: MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1; msach@102: uint32 containerIdx; msach@140: _VMSMasterEnv->amtOfOutstandingMem += getChunkSize(chunkToFree) + sizeof(MallocProlog); 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); Me@50: } 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: } Me@50: 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@141: assert((freeLists->bigChunksSearchVector[0] & (uint64)1 << containerIdx) != 0); msach@141: } 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@53: */ msach@101: MallocArrays * Me@53: VMS_ext__create_free_list() msach@101: { msach@101: //Initialize containers for small chunks and fill with zeros msach@139: MallocArrays *freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) ); 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@82: //Touch memory to avoid page faults msach@81: void *ptr,*endPtr; msach@81: endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE; msach@81: for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE) msach@81: { msach@81: *(char*)ptr = 0; msach@81: } Me@53: msach@101: firstChunk->nextLowerInMem = NULL; msach@101: firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk + msach@141: MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog)); msach@101: firstChunk->nextChunkInFreeList = NULL; msach@101: //previous element in the queue is the container msach@139: firstChunk->prevChunkInFreeList = (MallocProlog*)&freeLists->bigChunks[container-2]; msach@82: msach@117: freeLists->bigChunks[container-2] = firstChunk; msach@115: //Insert into bit search list msach@117: if(container <= 65) msach@141: { msach@139: freeLists->bigChunksSearchVector[0] = ((uint64)1 << (container-2)); msach@141: freeLists->bigChunksSearchVector[1] = 0; msach@141: } msach@116: else msach@141: { msach@141: freeLists->bigChunksSearchVector[0] = 0; msach@139: freeLists->bigChunksSearchVector[1] = ((uint64)1 << (container-66)); msach@141: } 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@139: free(freeLists); Me@50: } Me@50: