1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/vmalloc.c	Thu Nov 11 06:19:51 2010 -0800
     1.3 @@ -0,0 +1,327 @@
     1.4 +/*
     1.5 + *  Copyright 2009 OpenSourceCodeStewardshipFoundation.org
     1.6 + *  Licensed under GNU General Public License version 2
     1.7 + *
     1.8 + * Author: seanhalle@yahoo.com
     1.9 + *
    1.10 + * Created on November 14, 2009, 9:07 PM
    1.11 + */
    1.12 +
    1.13 +#include <malloc.h>
    1.14 +#include <stdlib.h>
    1.15 +
    1.16 +#include "VMS.h"
    1.17 +
    1.18 +/*Helper function
    1.19 + *Insert a newly generated free chunk into the first spot on the free list.
    1.20 + * The chunk is cast as a MallocProlog, so the various pointers in it are
    1.21 + * accessed with C's help -- and the size of the prolog is easily added to
    1.22 + * the pointer when a chunk is returned to the app -- so C handles changes
    1.23 + * in pointer sizes among machines.
    1.24 + *
    1.25 + *The list head is a normal MallocProlog struct -- identified by its
    1.26 + * prevChunkInFreeList being NULL -- the only one.
    1.27 + *
    1.28 + *The end of the list is identified by next chunk being NULL, as usual.
    1.29 + */
    1.30 +void inline
    1.31 +add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead )
    1.32 + { 
    1.33 +   chunk->nextChunkInFreeList     = listHead->nextChunkInFreeList;
    1.34 +   if( chunk->nextChunkInFreeList != NULL ) //if not last in free list
    1.35 +      chunk->nextChunkInFreeList->prevChunkInFreeList = chunk;
    1.36 +   chunk->prevChunkInFreeList     = listHead;
    1.37 +   listHead->nextChunkInFreeList  = chunk;
    1.38 + }
    1.39 +
    1.40 +
    1.41 +/*This is sequential code, meant to only be called from the Master, not from
    1.42 + * any slave VPs.
    1.43 + *Search down list, checking size by the nextHigherInMem pointer, to find
    1.44 + * first chunk bigger than size needed.
    1.45 + *Shave off the extra and make it into a new free-list element, hook it in
    1.46 + * then return the address of the found element plus size of prolog.
    1.47 + *
    1.48 + *Will find a
    1.49 + */
    1.50 +void *
    1.51 +VMS__malloc( int32 sizeRequested )
    1.52 + { MallocProlog *foundElem = NULL, *currElem, *newElem;
    1.53 +   int32         amountExtra, foundElemIsTopOfHeap, sizeConsumed,sizeOfFound;
    1.54 +
    1.55 +      //step up the size to be aligned at 16-byte boundary, prob better ways
    1.56 +   sizeRequested = ((sizeRequested + 16) >> 4) << 4;
    1.57 +   currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
    1.58 +
    1.59 +   while( currElem != NULL )
    1.60 +    {    //check if size of currElem is big enough
    1.61 +      sizeOfFound=(int32)((char*)currElem->nextHigherInMem -(char*)currElem);
    1.62 +      amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
    1.63 +      if( amountExtra > 0 )
    1.64 +       {    //found it, get out of loop
    1.65 +         foundElem = currElem;
    1.66 +         currElem = NULL;
    1.67 +       }
    1.68 +      else
    1.69 +         currElem = currElem->nextChunkInFreeList;
    1.70 +    }
    1.71 +
    1.72 +   if( foundElem == NULL )
    1.73 +    { ERROR("\nmalloc failed\n")
    1.74 +      return (void *)NULL;  //indicates malloc failed
    1.75 +    }
    1.76 +      //Using a kludge to identify the element that is the top chunk in the
    1.77 +      // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
    1.78 +      // save addr of start of heap in head's nextLowerInMem
    1.79 +      //Will handle top of Heap specially
    1.80 +   foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
    1.81 +                          _VMSMasterEnv->freeListHead->nextHigherInMem;
    1.82 +
    1.83 +      //before shave off and try to insert new elem, remove found elem
    1.84 +      //note, foundElem will never be the head, so always has valid prevChunk
    1.85 +   foundElem->prevChunkInFreeList->nextChunkInFreeList =
    1.86 +                                              foundElem->nextChunkInFreeList;
    1.87 +   if( foundElem->nextChunkInFreeList != NULL )
    1.88 +    { foundElem->nextChunkInFreeList->prevChunkInFreeList =
    1.89 +                                              foundElem->prevChunkInFreeList;
    1.90 +    }
    1.91 +   foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
    1.92 +   
    1.93 +      //if enough, turn extra into new elem & insert it
    1.94 +   if( amountExtra > 64 )
    1.95 +    {    //make new elem by adding to addr of curr elem then casting
    1.96 +      sizeConsumed = sizeof(MallocProlog) + sizeRequested;
    1.97 +      newElem = (MallocProlog *)( (char *)foundElem + sizeConsumed );
    1.98 +      newElem->nextHigherInMem   = foundElem->nextHigherInMem;
    1.99 +      newElem->nextLowerInMem    = foundElem;
   1.100 +      foundElem->nextHigherInMem = newElem;
   1.101 +      
   1.102 +      if( ! foundElemIsTopOfHeap )
   1.103 +       {    //there is no next higher for top of heap, so can't write to it
   1.104 +         newElem->nextHigherInMem->nextLowerInMem = newElem;
   1.105 +       }
   1.106 +      add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
   1.107 +    }
   1.108 +   else
   1.109 +    {
   1.110 +      sizeConsumed = sizeOfFound;
   1.111 +    }
   1.112 +  _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
   1.113 +
   1.114 +      //skip over the prolog by adding its size to the pointer return
   1.115 +   return (void *)((char *)foundElem + sizeof(MallocProlog));
   1.116 + }
   1.117 +
   1.118 +
   1.119 +/*This is sequential code -- only to be called from the Master
   1.120 + * When free, subtract the size of prolog from pointer, then cast it to a
   1.121 + * MallocProlog.  Then check the nextLower and nextHigher chunks to see if
   1.122 + * one or both are also free, and coalesce if so, and if neither free, then
   1.123 + * add this one to free-list.
   1.124 + */
   1.125 +void
   1.126 +VMS__free( void *ptrToFree )
   1.127 + { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem;
   1.128 +   int32         lowerExistsAndIsFree, higherExistsAndIsFree, sizeOfElem;
   1.129 +
   1.130 +   if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem ||
   1.131 +       ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem )
   1.132 +    {    //outside the range of data owned by VMS's malloc, so do nothing
   1.133 +      return;
   1.134 +    }
   1.135 +      //subtract size of prolog to get pointer to prolog, then cast
   1.136 +   elemToFree = (MallocProlog *)((char *)ptrToFree - sizeof(MallocProlog));
   1.137 +   sizeOfElem =(int32)((char*)elemToFree->nextHigherInMem-(char*)elemToFree);
   1.138 +
   1.139 +   if( elemToFree->prevChunkInFreeList != NULL )
   1.140 +    { printf( "error: freeing same element twice!" ); exit(1);
   1.141 +    }
   1.142 +
   1.143 +   _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
   1.144 +
   1.145 +   nextLowerElem  = elemToFree->nextLowerInMem;
   1.146 +   nextHigherElem = elemToFree->nextHigherInMem;
   1.147 +
   1.148 +   if( nextHigherElem == NULL )
   1.149 +      higherExistsAndIsFree = FALSE;
   1.150 +   else //okay exists, now check if in the free-list by checking back ptr
   1.151 +      higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
   1.152 +    
   1.153 +   if( nextLowerElem == NULL )
   1.154 +      lowerExistsAndIsFree = FALSE;
   1.155 +   else //okay, it exists, now check if it's free
   1.156 +      lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
   1.157 +    
   1.158 +
   1.159 +      //now, know what exists and what's free
   1.160 +   if( lowerExistsAndIsFree )
   1.161 +    { if( higherExistsAndIsFree )
   1.162 +       {    //both exist and are free, so coalesce all three
   1.163 +            //First, remove higher from free-list
   1.164 +         nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
   1.165 +                                         nextHigherElem->nextChunkInFreeList;
   1.166 +         if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
   1.167 +            nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
   1.168 +                                         nextHigherElem->prevChunkInFreeList;
   1.169 +            //Now, fix-up sequence-in-mem list -- by side-effect, this also
   1.170 +            // changes size of the lower elem, which is still in free-list
   1.171 +         nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
   1.172 +         if( nextHigherElem->nextHigherInMem !=
   1.173 +             _VMSMasterEnv->freeListHead->nextHigherInMem )
   1.174 +            nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
   1.175 +            //notice didn't do anything to elemToFree -- it simply is no
   1.176 +            // longer reachable from any of the lists.  Wonder if could be a
   1.177 +            // security leak because left valid addresses in it,
   1.178 +            // but don't care for now.
   1.179 +       }
   1.180 +      else
   1.181 +       {    //lower is the only of the two that exists and is free,
   1.182 +            //In this case, no adjustment to free-list, just change mem-list.
   1.183 +            // By side-effect, changes size of the lower elem
   1.184 +         nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem;
   1.185 +         if( elemToFree->nextHigherInMem !=
   1.186 +             _VMSMasterEnv->freeListHead->nextHigherInMem )
   1.187 +            elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
   1.188 +       }
   1.189 +    }
   1.190 +   else
   1.191 +    {    //lower either doesn't exist or isn't free, so check higher
   1.192 +      if( higherExistsAndIsFree )
   1.193 +       {    //higher exists and is the only of the two free
   1.194 +            //First, in free-list, replace higher elem with the one to free
   1.195 +         elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList;
   1.196 +         elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList;
   1.197 +         elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree;
   1.198 +         if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
   1.199 +            elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
   1.200 +            //Now chg mem-list. By side-effect, changes size of elemToFree
   1.201 +         elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
   1.202 +         if( elemToFree->nextHigherInMem !=
   1.203 +             _VMSMasterEnv->freeListHead->nextHigherInMem )
   1.204 +            elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
   1.205 +       }
   1.206 +      else
   1.207 +       {    //neither lower nor higher is availabe to coalesce so add to list
   1.208 +            // this makes prev chunk ptr non-null, which indicates it's free
   1.209 +         elemToFree->nextChunkInFreeList =
   1.210 +                            _VMSMasterEnv->freeListHead->nextChunkInFreeList;
   1.211 +         _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree;
   1.212 +         if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
   1.213 +            elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
   1.214 +         elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead;
   1.215 +       }
   1.216 +    }
   1.217 +
   1.218 + }
   1.219 +
   1.220 +
   1.221 +/*Allocates memory from the external system -- higher overhead
   1.222 + *
   1.223 + *Because of Linux's malloc throwing bizarre random faults when malloc is
   1.224 + * used inside a VMS virtual processor, have to pass this as a request and
   1.225 + * have the core loop do it when it gets around to it -- will look for these
   1.226 + * chores leftover from the previous animation of masterVP the next time it
   1.227 + * goes to animate the masterVP -- so it takes two separate masterVP
   1.228 + * animations, separated by work, to complete an external malloc or
   1.229 + * external free request.
   1.230 + *
   1.231 + *Thinking core loop accepts signals -- just looks if signal-location is
   1.232 + * empty or not --
   1.233 + */
   1.234 +void *
   1.235 +VMS__malloc_in_ext( int32 sizeRequested )
   1.236 + {
   1.237 + /*
   1.238 +      //This is running in the master, so no chance for multiple cores to be
   1.239 +      // competing for the core's flag.
   1.240 +   if(  *(_VMSMasterEnv->coreLoopSignalAddr[ 0 ]) != 0 )
   1.241 +    {    //something has already signalled to core loop, so save the signal
   1.242 +         // and look, next time master animated, to see if can send it.
   1.243 +         //Note, the addr to put a signal is in the coreloop's frame, so just
   1.244 +         // checks it each time through -- make it volatile to avoid GCC
   1.245 +         // optimizations -- it's a coreloop local var that only changes
   1.246 +         // after jumping away.  The signal includes the addr to send the
   1.247 +         //return to -- even if just empty return completion-signal
   1.248 +         //
   1.249 +         //save the signal in some queue that the master looks at each time
   1.250 +         // it starts up -- one loc says if empty for fast common case --
   1.251 +         //something like that -- want to hide this inside this call -- but
   1.252 +         // think this has to come as a request -- req handler gives procr
   1.253 +         // back to master loop, which gives it back to req handler at point
   1.254 +         // it sees that core loop has sent return signal.  Something like
   1.255 +         // that.
   1.256 +      saveTheSignal
   1.257 +
   1.258 +    }
   1.259 +  coreSigData->type = malloc;
   1.260 +  coreSigData->sizeToMalloc = sizeRequested;
   1.261 +  coreSigData->locToSignalCompletion = &figureOut;
   1.262 +   _VMSMasterEnv->coreLoopSignals[ 0 ] = coreSigData;
   1.263 +  */
   1.264 +      //just risk system-stack faults until get this figured out
   1.265 +   return malloc( sizeRequested );
   1.266 + }
   1.267 +
   1.268 +
   1.269 +/*Frees memory that was allocated in the external system -- higher overhead
   1.270 + *
   1.271 + *As noted in external malloc comment, this is clunky 'cause the free has
   1.272 + * to be called in the core loop.
   1.273 + */
   1.274 +void
   1.275 +VMS__free_in_ext( void *ptrToFree )
   1.276 + {
   1.277 +      //just risk system-stack faults until get this figured out
   1.278 +   free( ptrToFree );
   1.279 +
   1.280 +      //TODO: fix this -- so 
   1.281 + }
   1.282 +
   1.283 +
   1.284 +/*Designed to be called from the main thread outside of VMS, during init
   1.285 + */
   1.286 +MallocProlog *
   1.287 +VMS_ext__create_free_list()
   1.288 + { MallocProlog *freeListHead, *firstChunk;
   1.289 +
   1.290 +      //Note, this is running in the main thread -- all increases in malloc
   1.291 +      // mem and all frees of it must be done in this thread, with the
   1.292 +      // thread's original stack available
   1.293 +   freeListHead = malloc( sizeof(MallocProlog) );
   1.294 +   firstChunk   = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
   1.295 +   if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
   1.296 +
   1.297 +   freeListHead->prevChunkInFreeList = NULL;
   1.298 +      //Use this addr to free the heap when cleanup
   1.299 +   freeListHead->nextLowerInMem      = firstChunk;
   1.300 +      //to identify top-of-heap elem, compare this addr to elem's next higher
   1.301 +   freeListHead->nextHigherInMem     = (void*)( (char*)firstChunk +
   1.302 +                                         MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
   1.303 +   freeListHead->nextChunkInFreeList = firstChunk;
   1.304 +
   1.305 +   firstChunk->nextChunkInFreeList   = NULL;
   1.306 +   firstChunk->prevChunkInFreeList   = freeListHead;
   1.307 +      //next Higher has to be set to top of chunk, so can calc size in malloc
   1.308 +   firstChunk->nextHigherInMem       = (void*)( (char*)firstChunk +
   1.309 +                                         MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
   1.310 +   firstChunk->nextLowerInMem        = NULL; //identifies as bott of heap
   1.311 +   
   1.312 +   _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet
   1.313 +
   1.314 +   return freeListHead;
   1.315 + }
   1.316 +
   1.317 +
   1.318 +/*Designed to be called from the main thread outside of VMS, during cleanup
   1.319 + */
   1.320 +void
   1.321 +VMS_ext__free_free_list( MallocProlog *freeListHead )
   1.322 + {    
   1.323 +      //stashed a ptr to the one and only bug chunk malloc'd from OS in the
   1.324 +      // free list head's next lower in mem pointer
   1.325 +   free( freeListHead->nextLowerInMem );
   1.326 +
   1.327 +   //don't free the head -- it'll be in an array eventually -- free whole
   1.328 +   // array when all the free lists linked from it have already been freed
   1.329 + }
   1.330 +