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 <malloc.h>
msach@76: #include <inttypes.h>
Me@53: #include <stdlib.h>
msach@76: #include <stdio.h>
msach@101: #include <string.h>
msach@101: #include <math.h>
Me@50: 
Me@50: #include "VMS.h"
Me@68: #include "Histogram/Histogram.h"
Me@50: 
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@101:     return floor((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@101: /*
msach@101:  * Removes a chunk from a free list.
msach@101:  */
msach@101: inline
msach@101: MallocProlog *extractChunk(MallocProlog* chunk)
msach@101: {
msach@101:     
msach@101: }
msach@101: 
msach@101: /*
msach@101:  * Merges two chunks.
msach@101:  * Chunk A has to be before chunk B in memory.
msach@101:  */
msach@101: inline
msach@101: MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
msach@101: {
msach@101:     
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@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@101:    MallocArrays* freeList = _VMSMasterEnv->freeLists;
msach@101:    
msach@101:    //Return a small chunk if the requested size is smaller than 128B
msach@101:    //TODO: for now set size to 129B
msach@101:    if(sizeRequested < 128)
msach@101:        sizeRequested = 129;
msach@101:            
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@101:    if(freeList->bigChunks[containerIdx] == NULL)
msach@101:    {
msach@101:        while(freeList->bigChunks[containerIdx] == NULL)
msach@101:        {
msach@101:            containerIdx++;
msach@101:            if(containerIdx > freeList->containerCount)
msach@101:            {
msach@101:                printf("VMS malloc failed: low memory");
msach@101:                exit(1);
msach@101:            }
msach@101:        }
msach@101:        
msach@101:        foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
msach@101:        //Found bigger Element, so we have to divide until it fits the
msach@101:        //requested size
msach@101:        containerIdx--;       
msach@101:        size_t containerSize = getContainerSize(containerIdx);
msach@101:        size_t chunkSize     = getChunkSize(foundChunk);
msach@101:        
msach@101:        while(containerIdx > targetContainerIdx)
msach@101:        {
msach@101:            if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog))
msach@101:            {
msach@101:                MallocProlog *newChunk = divideChunk(foundChunk,containerSize);
msach@101:                insertChunk(newChunk,&freeList->bigChunks[containerIdx]);
msach@101:                chunkSize = getChunkSize(foundChunk);
msach@101:            }
msach@101:            containerIdx--;
msach@101:            containerSize /= CHUNK_INCREASE_RATE;
msach@101:        }
msach@101:    }
msach@101:    else
msach@101:    {
msach@101:         foundChunk = removeChunk(&freeList->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@101: 
msach@101:    //skip over the prolog by adding its size to the pointer return
msach@101:    return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog));
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@101:    MallocArrays* freeList = _VMSMasterEnv->freeLists;
msach@101:    MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
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@101:            mergeChunks()
Me@50:        }
msach@101:    }
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@101:    
msach@101:    //Calculate number of containers for big chunks
msach@101:    uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
msach@101:    
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@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@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
Me@50: VMS_ext__free_free_list( MallocProlog *freeListHead )
Me@50:  {    
Me@50:       //stashed a ptr to the one and only bug chunk malloc'd from OS in the
Me@50:       // free list head's next lower in mem pointer
Me@50:    free( freeListHead->nextLowerInMem );
Me@50: 
Me@50:    //don't free the head -- it'll be in an array eventually -- free whole
Me@50:    // array when all the free lists linked from it have already been freed
Me@50:  }
Me@50: