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>
Me@53: #include <stdlib.h>
Me@50: 
Me@50: #include "VMS.h"
Me@50: 
Me@50: /*Helper function
Me@50:  *Insert a newly generated free chunk into the first spot on the free list.
Me@50:  * The chunk is cast as a MallocProlog, so the various pointers in it are
Me@50:  * accessed with C's help -- and the size of the prolog is easily added to
Me@50:  * the pointer when a chunk is returned to the app -- so C handles changes
Me@50:  * in pointer sizes among machines.
Me@50:  *
Me@50:  *The list head is a normal MallocProlog struct -- identified by its
Me@50:  * prevChunkInFreeList being NULL -- the only one.
Me@50:  *
Me@50:  *The end of the list is identified by next chunk being NULL, as usual.
Me@50:  */
Me@50: void inline
Me@50: add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead )
Me@50:  { 
Me@50:    chunk->nextChunkInFreeList     = listHead->nextChunkInFreeList;
Me@50:    if( chunk->nextChunkInFreeList != NULL ) //if not last in free list
Me@50:       chunk->nextChunkInFreeList->prevChunkInFreeList = chunk;
Me@50:    chunk->prevChunkInFreeList     = listHead;
Me@50:    listHead->nextChunkInFreeList  = chunk;
Me@50:  }
Me@50: 
Me@50: 
Me@50: /*This is sequential code, meant to only be called from the Master, not from
Me@50:  * any slave VPs.
Me@50:  *Search down list, checking size by the nextHigherInMem pointer, to find
Me@50:  * first chunk bigger than size needed.
Me@50:  *Shave off the extra and make it into a new free-list element, hook it in
Me@50:  * then return the address of the found element plus size of prolog.
Me@50:  *
Me@50:  *Will find a
Me@50:  */
Me@50: void *
Me@50: VMS__malloc( int32 sizeRequested )
Me@50:  { MallocProlog *foundElem = NULL, *currElem, *newElem;
Me@50:    int32         amountExtra, foundElemIsTopOfHeap, sizeConsumed,sizeOfFound;
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:    
Me@50:       //step up the size to be aligned at 16-byte boundary, prob better ways
Me@50:    sizeRequested = ((sizeRequested + 16) >> 4) << 4;
Me@50:    currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
Me@50: 
Me@50:    while( currElem != NULL )
Me@50:     {    //check if size of currElem is big enough
Me@50:       sizeOfFound=(int32)((char*)currElem->nextHigherInMem -(char*)currElem);
Me@50:       amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
Me@50:       if( amountExtra > 0 )
Me@50:        {    //found it, get out of loop
Me@50:          foundElem = currElem;
Me@50:          currElem = NULL;
Me@50:        }
Me@50:       else
Me@50:          currElem = currElem->nextChunkInFreeList;
Me@50:     }
Me@50: 
Me@50:    if( foundElem == NULL )
Me@55:     { ERROR("\nmalloc failed\n")
Me@60:       return (void *)NULL;  //indicates malloc failed
Me@50:     }
Me@50:       //Using a kludge to identify the element that is the top chunk in the
Me@50:       // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
Me@50:       // save addr of start of heap in head's nextLowerInMem
Me@50:       //Will handle top of Heap specially
Me@50:    foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
Me@50:                           _VMSMasterEnv->freeListHead->nextHigherInMem;
Me@50: 
Me@50:       //before shave off and try to insert new elem, remove found elem
Me@50:       //note, foundElem will never be the head, so always has valid prevChunk
Me@50:    foundElem->prevChunkInFreeList->nextChunkInFreeList =
Me@50:                                               foundElem->nextChunkInFreeList;
Me@50:    if( foundElem->nextChunkInFreeList != NULL )
Me@50:     { foundElem->nextChunkInFreeList->prevChunkInFreeList =
Me@50:                                               foundElem->prevChunkInFreeList;
Me@50:     }
Me@50:    foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
Me@50:    
Me@50:       //if enough, turn extra into new elem & insert it
Me@50:    if( amountExtra > 64 )
Me@50:     {    //make new elem by adding to addr of curr elem then casting
Me@50:       sizeConsumed = sizeof(MallocProlog) + sizeRequested;
Me@50:       newElem = (MallocProlog *)( (char *)foundElem + sizeConsumed );
Me@50:       newElem->nextHigherInMem   = foundElem->nextHigherInMem;
Me@50:       newElem->nextLowerInMem    = foundElem;
Me@50:       foundElem->nextHigherInMem = newElem;
Me@50:       
Me@50:       if( ! foundElemIsTopOfHeap )
Me@50:        {    //there is no next higher for top of heap, so can't write to it
Me@50:          newElem->nextHigherInMem->nextLowerInMem = newElem;
Me@50:        }
Me@50:       add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
Me@50:     }
Me@50:    else
Me@50:     {
Me@50:       sizeConsumed = sizeOfFound;
Me@50:     }
Me@50:   _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
Me@50: 
Me@65:    //============================= MEASUREMENT STUFF ========================
Me@65:    #ifdef MEAS__TIME_MALLOC
Me@65:    saveLowTimeStampCountInto( endStamp );
Me@65:    addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
Me@65:    #endif
Me@65:    //========================================================================
Me@65: 
Me@50:       //skip over the prolog by adding its size to the pointer return
Me@50:    return (void *)((char *)foundElem + sizeof(MallocProlog));
Me@50:  }
Me@50: 
Me@50: 
Me@50: /*This is sequential code -- only to be called from the Master
Me@50:  * When free, subtract the size of prolog from pointer, then cast it to a
Me@50:  * MallocProlog.  Then check the nextLower and nextHigher chunks to see if
Me@50:  * one or both are also free, and coalesce if so, and if neither free, then
Me@50:  * add this one to free-list.
Me@50:  */
Me@50: void
Me@50: VMS__free( void *ptrToFree )
Me@50:  { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem;
Me@50:    int32         lowerExistsAndIsFree, higherExistsAndIsFree, sizeOfElem;
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: 
Me@53:    if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem ||
Me@53:        ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50:     {    //outside the range of data owned by VMS's malloc, so do nothing
Me@50:       return;
Me@50:     }
Me@50:       //subtract size of prolog to get pointer to prolog, then cast
Me@50:    elemToFree = (MallocProlog *)((char *)ptrToFree - sizeof(MallocProlog));
Me@50:    sizeOfElem =(int32)((char*)elemToFree->nextHigherInMem-(char*)elemToFree);
Me@53: 
Me@53:    if( elemToFree->prevChunkInFreeList != NULL )
Me@53:     { printf( "error: freeing same element twice!" ); exit(1);
Me@53:     }
Me@53: 
Me@50:    _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
Me@50: 
Me@50:    nextLowerElem  = elemToFree->nextLowerInMem;
Me@50:    nextHigherElem = elemToFree->nextHigherInMem;
Me@50: 
Me@50:    if( nextHigherElem == NULL )
Me@50:       higherExistsAndIsFree = FALSE;
Me@50:    else //okay exists, now check if in the free-list by checking back ptr
Me@50:       higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
Me@50:     
Me@50:    if( nextLowerElem == NULL )
Me@50:       lowerExistsAndIsFree = FALSE;
Me@50:    else //okay, it exists, now check if it's free
Me@50:       lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
Me@50:     
Me@50: 
Me@50:       //now, know what exists and what's free
Me@50:    if( lowerExistsAndIsFree )
Me@50:     { if( higherExistsAndIsFree )
Me@50:        {    //both exist and are free, so coalesce all three
Me@50:             //First, remove higher from free-list
Me@50:          nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
Me@50:                                          nextHigherElem->nextChunkInFreeList;
Me@50:          if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
Me@50:             nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
Me@50:                                          nextHigherElem->prevChunkInFreeList;
Me@50:             //Now, fix-up sequence-in-mem list -- by side-effect, this also
Me@50:             // changes size of the lower elem, which is still in free-list
Me@50:          nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
Me@50:          if( nextHigherElem->nextHigherInMem !=
Me@50:              _VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50:             nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
Me@50:             //notice didn't do anything to elemToFree -- it simply is no
Me@50:             // longer reachable from any of the lists.  Wonder if could be a
Me@50:             // security leak because left valid addresses in it,
Me@50:             // but don't care for now.
Me@50:        }
Me@50:       else
Me@50:        {    //lower is the only of the two that exists and is free,
Me@50:             //In this case, no adjustment to free-list, just change mem-list.
Me@50:             // By side-effect, changes size of the lower elem
Me@50:          nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem;
Me@50:          if( elemToFree->nextHigherInMem !=
Me@50:              _VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50:             elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
Me@50:        }
Me@50:     }
Me@50:    else
Me@50:     {    //lower either doesn't exist or isn't free, so check higher
Me@50:       if( higherExistsAndIsFree )
Me@50:        {    //higher exists and is the only of the two free
Me@50:             //First, in free-list, replace higher elem with the one to free
Me@50:          elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList;
Me@50:          elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList;
Me@50:          elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree;
Me@50:          if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
Me@50:             elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
Me@50:             //Now chg mem-list. By side-effect, changes size of elemToFree
Me@50:          elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
Me@50:          if( elemToFree->nextHigherInMem !=
Me@50:              _VMSMasterEnv->freeListHead->nextHigherInMem )
Me@50:             elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
Me@50:        }
Me@50:       else
Me@50:        {    //neither lower nor higher is availabe to coalesce so add to list
Me@50:             // this makes prev chunk ptr non-null, which indicates it's free
Me@50:          elemToFree->nextChunkInFreeList =
Me@50:                             _VMSMasterEnv->freeListHead->nextChunkInFreeList;
Me@50:          _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree;
Me@50:          if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
Me@50:             elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
Me@50:          elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead;
Me@50:        }
Me@50:     }
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 *
Me@53: VMS__malloc_in_ext( int32 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:  */
Me@50: MallocProlog *
Me@53: VMS_ext__create_free_list()
Me@50:  { MallocProlog *freeListHead, *firstChunk;
Me@50: 
Me@50:       //Note, this is running in the main thread -- all increases in malloc
Me@50:       // mem and all frees of it must be done in this thread, with the
Me@50:       // thread's original stack available
Me@50:    freeListHead = malloc( sizeof(MallocProlog) );
Me@50:    firstChunk   = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
Me@50:    if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
Me@50: 
Me@50:    freeListHead->prevChunkInFreeList = NULL;
Me@50:       //Use this addr to free the heap when cleanup
Me@50:    freeListHead->nextLowerInMem      = firstChunk;
Me@50:       //to identify top-of-heap elem, compare this addr to elem's next higher
Me@53:    freeListHead->nextHigherInMem     = (void*)( (char*)firstChunk +
Me@53:                                          MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
Me@50:    freeListHead->nextChunkInFreeList = firstChunk;
Me@50: 
Me@50:    firstChunk->nextChunkInFreeList   = NULL;
Me@50:    firstChunk->prevChunkInFreeList   = freeListHead;
Me@50:       //next Higher has to be set to top of chunk, so can calc size in malloc
Me@53:    firstChunk->nextHigherInMem       = (void*)( (char*)firstChunk +
Me@53:                                          MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
Me@50:    firstChunk->nextLowerInMem        = NULL; //identifies as bott of heap
Me@53:    
Me@53:    _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet
Me@50: 
Me@50:    return freeListHead;
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: