1.1 --- a/VMS.c	Tue Jul 26 16:14:30 2011 +0200
     1.2 +++ b/VMS.c	Tue Aug 02 15:44:28 2011 +0200
     1.3 @@ -105,7 +105,7 @@
     1.4          //Very first thing put into the master env is the free-list, seeded
     1.5          // with a massive initial chunk of memory.
     1.6          //After this, all other mallocs are VMS__malloc.
     1.7 -   _VMSMasterEnv->freeListHead        = VMS_ext__create_free_list();
     1.8 +   _VMSMasterEnv->freeLists        = VMS_ext__create_free_list();
     1.9  
    1.10  
    1.11     //============================= MEASUREMENT STUFF ========================
    1.12 @@ -751,7 +751,7 @@
    1.13     //========================================================================
    1.14  */
    1.15        //These are the only two that use system free 
    1.16 -   VMS_ext__free_free_list( _VMSMasterEnv->freeListHead );
    1.17 +   VMS_ext__free_free_list( _VMSMasterEnv->freeLists );
    1.18     free( (void *)_VMSMasterEnv );
    1.19   }
    1.20  

     2.1 --- a/VMS.h	Tue Jul 26 16:14:30 2011 +0200
     2.2 +++ b/VMS.h	Tue Aug 02 15:44:28 2011 +0200
     2.3 @@ -224,7 +224,7 @@
     2.4  
     2.5     void            *semanticEnv;
     2.6     void            *OSEventStruc;   //for future, when add I/O to BLIS
     2.7 -   MallocProlog    *freeListHead;
     2.8 +   MallocArrays    *freeLists;
     2.9     int32            amtOfOutstandingMem; //total currently allocated
    2.10  
    2.11     void            *coreLoopReturnPt;//addr to jump to to re-enter coreLoop

     3.1 --- a/vmalloc.c	Tue Jul 26 16:14:30 2011 +0200
     3.2 +++ b/vmalloc.c	Tue Aug 02 15:44:28 2011 +0200
     3.3 @@ -11,46 +11,188 @@
     3.4  #include <inttypes.h>
     3.5  #include <stdlib.h>
     3.6  #include <stdio.h>
     3.7 +#include <string.h>
     3.8 +#include <math.h>
     3.9  
    3.10  #include "VMS.h"
    3.11  #include "Histogram/Histogram.h"
    3.12  
    3.13 -/*Helper function
    3.14 - *Insert a newly generated free chunk into the first spot on the free list.
    3.15 - * The chunk is cast as a MallocProlog, so the various pointers in it are
    3.16 - * accessed with C's help -- and the size of the prolog is easily added to
    3.17 - * the pointer when a chunk is returned to the app -- so C handles changes
    3.18 - * in pointer sizes among machines.
    3.19 - *
    3.20 - *The list head is a normal MallocProlog struct -- identified by its
    3.21 - * prevChunkInFreeList being NULL -- the only one.
    3.22 - *
    3.23 - *The end of the list is identified by next chunk being NULL, as usual.
    3.24 +/*
    3.25 + * This calculates the container which fits the given size.
    3.26   */
    3.27 -void inline
    3.28 -add_chunk_to_free_list( MallocProlog *chunk, MallocProlog *listHead )
    3.29 - { 
    3.30 -   chunk->nextChunkInFreeList     = listHead->nextChunkInFreeList;
    3.31 -   if( chunk->nextChunkInFreeList != NULL ) //if not last in free list
    3.32 -      chunk->nextChunkInFreeList->prevChunkInFreeList = chunk;
    3.33 -   chunk->prevChunkInFreeList     = listHead;
    3.34 -   listHead->nextChunkInFreeList  = chunk;
    3.35 +inline
    3.36 +uint32 getContainer(size_t size)
    3.37 +{
    3.38 +    return floor((log10(size)-LOG128)/LOG54);
    3.39 +}
    3.40 +
    3.41 +/*
    3.42 + * This calculates the size of a given container
    3.43 + */
    3.44 +inline
    3.45 +size_t getContainerSize(uint32 idx)
    3.46 +{
    3.47 +    return pow(CHUNK_INCREASE_RATE,idx)*LOWER_BOUND;
    3.48 +}
    3.49 +
    3.50 +/*
    3.51 + * Removes the first chunk of a freeList
    3.52 + * The chunk is removed but not set as free. There is no check if
    3.53 + * the free list is empty, so make sure this is not the case.
    3.54 + */
    3.55 +inline
    3.56 +MallocProlog *removeChunk(MallocProlog** container)
    3.57 +{
    3.58 +    MallocProlog *removedChunk = *container;
    3.59 +    *container = removedChunk->nextChunkInFreeList;
    3.60 +    
    3.61 +    if(removedChunk->nextChunkInFreeList)
    3.62 +        removedChunk->nextChunkInFreeList->prevChunkInFreeList = 
    3.63 +                (MallocProlog*)container;
    3.64 +    
    3.65 +    return removedChunk;
    3.66 +}
    3.67 +
    3.68 +/*
    3.69 + * Removes a chunk from a free list.
    3.70 + */
    3.71 +inline
    3.72 +MallocProlog *extractChunk(MallocProlog* chunk)
    3.73 +{
    3.74 +    
    3.75 +}
    3.76 +
    3.77 +/*
    3.78 + * Merges two chunks.
    3.79 + * Chunk A has to be before chunk B in memory.
    3.80 + */
    3.81 +inline
    3.82 +MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
    3.83 +{
    3.84 +    
    3.85 +}
    3.86 +/*
    3.87 + * Inserts a chunk into a free list.
    3.88 + */
    3.89 +inline
    3.90 +void insertChunk(MallocProlog* chunk, MallocProlog** container)
    3.91 +{
    3.92 +    chunk->nextChunkInFreeList = *container;
    3.93 +    chunk->prevChunkInFreeList = (MallocProlog*)container;
    3.94 +    if(*container)
    3.95 +        (*container)->prevChunkInFreeList = chunk;
    3.96 +    *container = chunk;
    3.97 +}
    3.98 +
    3.99 +/*
   3.100 + * Divides the chunk that a new chunk of newSize is created.
   3.101 + * There is no size check, so make sure the size value is valid.
   3.102 + */
   3.103 +inline
   3.104 +MallocProlog *divideChunk(MallocProlog* chunk, size_t newSize)
   3.105 +{
   3.106 +    MallocProlog* newChunk = (MallocProlog*)((uintptr_t)chunk->nextHigherInMem -
   3.107 +            newSize - sizeof(MallocProlog));
   3.108 +    
   3.109 +    newChunk->nextLowerInMem  = chunk;
   3.110 +    newChunk->nextHigherInMem = chunk->nextHigherInMem;
   3.111 +    
   3.112 +    chunk->nextHigherInMem = newChunk;
   3.113 +    chunk->nextHigherInMem->nextLowerInMem = newChunk;
   3.114 +    
   3.115 +    return newChunk;
   3.116 +}
   3.117 +
   3.118 +inline
   3.119 +size_t getChunkSize(MallocProlog* chunk)
   3.120 +{
   3.121 +    return (uintptr_t)chunk->nextHigherInMem -
   3.122 +            (uintptr_t)chunk - sizeof(MallocProlog);
   3.123 +}
   3.124 +
   3.125 +/*
   3.126 + * This is sequential code, meant to only be called from the Master, not from
   3.127 + * any slave VPs.
   3.128 + */
   3.129 +void *VMS__malloc( size_t sizeRequested )
   3.130 + {     
   3.131 +   //============================= MEASUREMENT STUFF ========================
   3.132 +   #ifdef MEAS__TIME_MALLOC
   3.133 +   int32 startStamp, endStamp;
   3.134 +   saveLowTimeStampCountInto( startStamp );
   3.135 +   #endif
   3.136 +   //========================================================================
   3.137 +   
   3.138 +   MallocArrays* freeList = _VMSMasterEnv->freeLists;
   3.139 +   
   3.140 +   //Return a small chunk if the requested size is smaller than 128B
   3.141 +   //TODO: for now set size to 129B
   3.142 +   if(sizeRequested < 128)
   3.143 +       sizeRequested = 129;
   3.144 +           
   3.145 +   //Calculate the expected container. Start one higher to have a Chunk that's
   3.146 +   //always big enough.
   3.147 +   uint32 targetContainerIdx = getContainer(sizeRequested);
   3.148 +   uint32 containerIdx = targetContainerIdx + 1;
   3.149 +   
   3.150 +   MallocProlog* foundChunk;
   3.151 +   if(freeList->bigChunks[containerIdx] == NULL)
   3.152 +   {
   3.153 +       while(freeList->bigChunks[containerIdx] == NULL)
   3.154 +       {
   3.155 +           containerIdx++;
   3.156 +           if(containerIdx > freeList->containerCount)
   3.157 +           {
   3.158 +               printf("VMS malloc failed: low memory");
   3.159 +               exit(1);
   3.160 +           }
   3.161 +       }
   3.162 +       
   3.163 +       foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
   3.164 +       //Found bigger Element, so we have to divide until it fits the
   3.165 +       //requested size
   3.166 +       containerIdx--;       
   3.167 +       size_t containerSize = getContainerSize(containerIdx);
   3.168 +       size_t chunkSize     = getChunkSize(foundChunk);
   3.169 +       
   3.170 +       while(containerIdx > targetContainerIdx)
   3.171 +       {
   3.172 +           if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog))
   3.173 +           {
   3.174 +               MallocProlog *newChunk = divideChunk(foundChunk,containerSize);
   3.175 +               insertChunk(newChunk,&freeList->bigChunks[containerIdx]);
   3.176 +               chunkSize = getChunkSize(foundChunk);
   3.177 +           }
   3.178 +           containerIdx--;
   3.179 +           containerSize /= CHUNK_INCREASE_RATE;
   3.180 +       }
   3.181 +   }
   3.182 +   else
   3.183 +   {
   3.184 +        foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); 
   3.185 +   }
   3.186 +   
   3.187 +   //Mark as allocated
   3.188 +   foundChunk->prevChunkInFreeList = NULL;      
   3.189 +   
   3.190 +   //============================= MEASUREMENT STUFF ========================
   3.191 +   #ifdef MEAS__TIME_MALLOC
   3.192 +   saveLowTimeStampCountInto( endStamp );
   3.193 +   addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
   3.194 +   #endif
   3.195 +   //========================================================================
   3.196 +
   3.197 +   //skip over the prolog by adding its size to the pointer return
   3.198 +   return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog));
   3.199   }
   3.200  
   3.201 -
   3.202 -/*This is sequential code, meant to only be called from the Master, not from
   3.203 +/*
   3.204 + * This is sequential code, meant to only be called from the Master, not from
   3.205   * any slave VPs.
   3.206 - *Search down list, checking size by the nextHigherInMem pointer, to find
   3.207 - * first chunk bigger than size needed.
   3.208 - *Shave off the extra and make it into a new free-list element, hook it in
   3.209 - * then return the address of the found element plus size of prolog.
   3.210 - *
   3.211 - *Will find a
   3.212   */
   3.213 -void *VMS__malloc( size_t sizeRequested )
   3.214 - { MallocProlog *foundElem = NULL, *currElem, *newElem;
   3.215 -   ssize_t        amountExtra, sizeConsumed,sizeOfFound;
   3.216 -   uint32        foundElemIsTopOfHeap;
   3.217 +void
   3.218 +VMS__free( void *ptrToFree )
   3.219 + {
   3.220  
   3.221     //============================= MEASUREMENT STUFF ========================
   3.222     #ifdef MEAS__TIME_MALLOC
   3.223 @@ -59,312 +201,17 @@
   3.224     #endif
   3.225     //========================================================================
   3.226     
   3.227 -      //step up the size to be aligned at 16-byte boundary, prob better ways
   3.228 -   sizeRequested = (sizeRequested + 16) & ~15;
   3.229 -   currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
   3.230 -
   3.231 -   while( currElem != NULL )
   3.232 -    {    //check if size of currElem is big enough
   3.233 -      sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
   3.234 -      amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
   3.235 -      if( amountExtra > 0 )
   3.236 -       {    //found it, get out of loop
   3.237 -         foundElem = currElem;
   3.238 -         currElem = NULL;
   3.239 +   MallocArrays* freeList = _VMSMasterEnv->freeLists;
   3.240 +   MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
   3.241 +   
   3.242 +   //Check for free neighbors
   3.243 +   if(chunkToFree->nextLowerInMem)
   3.244 +   {
   3.245 +       if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
   3.246 +       {//Chunk is not allocated
   3.247 +           mergeChunks()
   3.248         }
   3.249 -      else
   3.250 -         currElem = currElem->nextChunkInFreeList;
   3.251 -    }
   3.252 -   
   3.253 -   if( foundElem == NULL )
   3.254 -    { ERROR("\nmalloc failed\n")
   3.255 -      return (void *)NULL;  //indicates malloc failed
   3.256 -    }
   3.257 -      //Using a kludge to identify the element that is the top chunk in the
   3.258 -      // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
   3.259 -      // save addr of start of heap in head's nextLowerInMem
   3.260 -      //Will handle top of Heap specially
   3.261 -   foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
   3.262 -                          _VMSMasterEnv->freeListHead->nextHigherInMem;
   3.263 -   
   3.264 -      //before shave off and try to insert new elem, remove found elem
   3.265 -      //note, foundElem will never be the head, so always has valid prevChunk
   3.266 -   foundElem->prevChunkInFreeList->nextChunkInFreeList =
   3.267 -                                              foundElem->nextChunkInFreeList;
   3.268 -   if( foundElem->nextChunkInFreeList != NULL )
   3.269 -    { foundElem->nextChunkInFreeList->prevChunkInFreeList =
   3.270 -                                              foundElem->prevChunkInFreeList;
   3.271 -    }
   3.272 -   foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
   3.273 -   
   3.274 -      //if enough, turn extra into new elem & insert it
   3.275 -   if( amountExtra > 64 )
   3.276 -    {   //make new elem by adding to addr of curr elem then casting
   3.277 -        sizeConsumed = sizeof(MallocProlog) + sizeRequested; 
   3.278 -        newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
   3.279 -        newElem->nextLowerInMem    = foundElem; //This is evil (but why?) 
   3.280 -        newElem->nextHigherInMem   = foundElem->nextHigherInMem; //This is evil (but why?)
   3.281 -        foundElem->nextHigherInMem = newElem;
   3.282 -        if( ! foundElemIsTopOfHeap )
   3.283 -        {  //there is no next higher for top of heap, so can't write to it
   3.284 -           newElem->nextHigherInMem->nextLowerInMem = newElem;
   3.285 -        }
   3.286 -        add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
   3.287 -    }
   3.288 -   else
   3.289 -    {
   3.290 -      sizeConsumed = sizeOfFound;
   3.291 -    }
   3.292 -  _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
   3.293 -
   3.294 -   //============================= MEASUREMENT STUFF ========================
   3.295 -   #ifdef MEAS__TIME_MALLOC
   3.296 -   saveLowTimeStampCountInto( endStamp );
   3.297 -   addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
   3.298 -   #endif
   3.299 -   //========================================================================
   3.300 -
   3.301 -      //skip over the prolog by adding its size to the pointer return
   3.302 -   return (void*)((uintptr_t)foundElem + sizeof(MallocProlog));
   3.303 - }
   3.304 -
   3.305 -/*This is sequential code, meant to only be called from the Master, not from
   3.306 - * any slave VPs.
   3.307 - *Search down list, checking size by the nextHigherInMem pointer, to find
   3.308 - * first chunk bigger than size needed.
   3.309 - *Shave off the extra and make it into a new free-list element, hook it in
   3.310 - * then return the address of the found element plus size of prolog.
   3.311 - *
   3.312 - * The difference to the regular malloc is, that all the allocated chunks are
   3.313 - * aligned and padded to the size of a CACHE_LINE. Thus creating a new chunk
   3.314 - * before the aligned chunk.
   3.315 - */
   3.316 -void *VMS__malloc_aligned( size_t sizeRequested )
   3.317 - { MallocProlog *foundElem = NULL, *currElem, *newElem;
   3.318 -   ssize_t        amountExtra, sizeConsumed,sizeOfFound,prevAmount;
   3.319 -   uint32        foundElemIsTopOfHeap;
   3.320 -
   3.321 -   //============================= MEASUREMENT STUFF ========================
   3.322 -   #ifdef MEAS__TIME_MALLOC
   3.323 -   uint32 startStamp, endStamp;
   3.324 -   saveLowTimeStampCountInto( startStamp );
   3.325 -   #endif
   3.326 -   //========================================================================
   3.327 -   
   3.328 -      //step up the size to be multiple of the cache line size
   3.329 -   sizeRequested = (sizeRequested + CACHE_LINE) & ~(CACHE_LINE-1);
   3.330 -   currElem = (_VMSMasterEnv->freeListHead)->nextChunkInFreeList;
   3.331 -
   3.332 -   while( currElem != NULL )
   3.333 -    {    //check if size of currElem is big enough
   3.334 -      sizeOfFound=(size_t)((uintptr_t)currElem->nextHigherInMem -(uintptr_t)currElem);
   3.335 -      amountExtra = sizeOfFound - sizeRequested - sizeof(MallocProlog);
   3.336 -      if( amountExtra > 0 )
   3.337 -       {    
   3.338 -         //look if the found element is already aligned
   3.339 -         if((((uintptr_t)currElem+sizeof(MallocProlog)) & (uintptr_t)(CACHE_LINE-1)) == 0){
   3.340 -             //found it, get out of loop
   3.341 -             foundElem = currElem;
   3.342 -             break;
   3.343 -         }else{
   3.344 -             //find first aligned address and check if it's still big enough
   3.345 -             //check also if the space before the aligned address is big enough
   3.346 -             //for a new element
   3.347 -             void *firstAlignedAddr = (void*)(((uintptr_t)currElem + 2*CACHE_LINE) & ~((uintptr_t)(CACHE_LINE-1)));
   3.348 -             prevAmount = (uintptr_t)firstAlignedAddr - (uintptr_t)currElem;
   3.349 -             sizeOfFound=(uintptr_t)currElem->nextHigherInMem -(uintptr_t)firstAlignedAddr + sizeof(MallocProlog);
   3.350 -             amountExtra= sizeOfFound - sizeRequested - sizeof(MallocProlog);
   3.351 -             if(prevAmount > 2*sizeof(MallocProlog) && amountExtra > 0 ){
   3.352 -                 //found suitable element
   3.353 -                 //create new previous element and exit loop
   3.354 -                 MallocProlog *newAlignedElem = (MallocProlog*)firstAlignedAddr - 1;
   3.355 -                 
   3.356 -                 //insert new element into free list
   3.357 -                 if(currElem->nextChunkInFreeList != NULL)
   3.358 -                     currElem->nextChunkInFreeList->prevChunkInFreeList = newAlignedElem;                     
   3.359 -                 newAlignedElem->prevChunkInFreeList = currElem;
   3.360 -                 newAlignedElem->nextChunkInFreeList = currElem->nextChunkInFreeList;
   3.361 -                 currElem->nextChunkInFreeList = newAlignedElem;
   3.362 -                 
   3.363 -                 //set higherInMem and lowerInMem
   3.364 -                 newAlignedElem->nextHigherInMem = currElem->nextHigherInMem;
   3.365 -                 foundElemIsTopOfHeap = currElem->nextHigherInMem ==
   3.366 -                          _VMSMasterEnv->freeListHead->nextHigherInMem;
   3.367 -                 if(!foundElemIsTopOfHeap)
   3.368 -                     currElem->nextHigherInMem->nextLowerInMem = newAlignedElem;
   3.369 -                 currElem->nextHigherInMem = newAlignedElem;
   3.370 -                 newAlignedElem->nextLowerInMem = currElem;
   3.371 -                 
   3.372 -                 //Found new element leaving loop
   3.373 -                 foundElem = newAlignedElem;
   3.374 -                 break;
   3.375 -             }
   3.376 -         }
   3.377 -         
   3.378 -       }
   3.379 -       currElem = currElem->nextChunkInFreeList;
   3.380 -    }
   3.381 -
   3.382 -   if( foundElem == NULL )
   3.383 -    { ERROR("\nmalloc failed\n")
   3.384 -      return (void *)NULL;  //indicates malloc failed
   3.385 -    }
   3.386 -      //Using a kludge to identify the element that is the top chunk in the
   3.387 -      // heap -- saving top-of-heap addr in head's nextHigherInMem -- and
   3.388 -      // save addr of start of heap in head's nextLowerInMem
   3.389 -      //Will handle top of Heap specially
   3.390 -   foundElemIsTopOfHeap = foundElem->nextHigherInMem ==
   3.391 -                          _VMSMasterEnv->freeListHead->nextHigherInMem;
   3.392 -
   3.393 -      //before shave off and try to insert new elem, remove found elem
   3.394 -      //note, foundElem will never be the head, so always has valid prevChunk
   3.395 -   foundElem->prevChunkInFreeList->nextChunkInFreeList =
   3.396 -                                              foundElem->nextChunkInFreeList;
   3.397 -   if( foundElem->nextChunkInFreeList != NULL )
   3.398 -    { foundElem->nextChunkInFreeList->prevChunkInFreeList =
   3.399 -                                              foundElem->prevChunkInFreeList;
   3.400 -    }
   3.401 -   foundElem->prevChunkInFreeList = NULL;//indicates elem currently allocated
   3.402 -   
   3.403 -      //if enough, turn extra into new elem & insert it
   3.404 -   if( amountExtra > 64 )
   3.405 -    {    //make new elem by adding to addr of curr elem then casting
   3.406 -      sizeConsumed = sizeof(MallocProlog) + sizeRequested;
   3.407 -      newElem = (MallocProlog *)( (uintptr_t)foundElem + sizeConsumed );
   3.408 -      newElem->nextHigherInMem   = foundElem->nextHigherInMem;
   3.409 -      newElem->nextLowerInMem    = foundElem;
   3.410 -      foundElem->nextHigherInMem = newElem;
   3.411 -      
   3.412 -      if( ! foundElemIsTopOfHeap )
   3.413 -       {    //there is no next higher for top of heap, so can't write to it
   3.414 -         newElem->nextHigherInMem->nextLowerInMem = newElem;
   3.415 -       }
   3.416 -      add_chunk_to_free_list( newElem, _VMSMasterEnv->freeListHead );
   3.417 -    }
   3.418 -   else
   3.419 -    {
   3.420 -      sizeConsumed = sizeOfFound;
   3.421 -    }
   3.422 -  _VMSMasterEnv->amtOfOutstandingMem += sizeConsumed;
   3.423 -
   3.424 -   //============================= MEASUREMENT STUFF ========================
   3.425 -   #ifdef MEAS__TIME_MALLOC
   3.426 -   saveLowTimeStampCountInto( endStamp );
   3.427 -   addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
   3.428 -   #endif
   3.429 -   //========================================================================
   3.430 -
   3.431 -      //skip over the prolog by adding its size to the pointer return
   3.432 -   return (void*)((uintptr_t)foundElem + sizeof(MallocProlog));
   3.433 - }
   3.434 -
   3.435 -
   3.436 -/*This is sequential code -- only to be called from the Master
   3.437 - * When free, subtract the size of prolog from pointer, then cast it to a
   3.438 - * MallocProlog.  Then check the nextLower and nextHigher chunks to see if
   3.439 - * one or both are also free, and coalesce if so, and if neither free, then
   3.440 - * add this one to free-list.
   3.441 - */
   3.442 -void
   3.443 -VMS__free( void *ptrToFree )
   3.444 - { MallocProlog *elemToFree, *nextLowerElem, *nextHigherElem;
   3.445 -   size_t         sizeOfElem;
   3.446 -   uint32         lowerExistsAndIsFree, higherExistsAndIsFree;
   3.447 -
   3.448 -   //============================= MEASUREMENT STUFF ========================
   3.449 -   #ifdef MEAS__TIME_MALLOC
   3.450 -   int32 startStamp, endStamp;
   3.451 -   saveLowTimeStampCountInto( startStamp );
   3.452 -   #endif
   3.453 -   //========================================================================
   3.454 -
   3.455 -   if( ptrToFree < (void*)_VMSMasterEnv->freeListHead->nextLowerInMem ||
   3.456 -       ptrToFree > (void*)_VMSMasterEnv->freeListHead->nextHigherInMem )
   3.457 -    {    //outside the range of data owned by VMS's malloc, so do nothing
   3.458 -      return;
   3.459 -    }
   3.460 -      //subtract size of prolog to get pointer to prolog, then cast
   3.461 -   elemToFree = (MallocProlog *)((uintptr_t)ptrToFree - sizeof(MallocProlog));
   3.462 -   sizeOfElem =(size_t)((uintptr_t)elemToFree->nextHigherInMem-(uintptr_t)elemToFree);
   3.463 -
   3.464 -   if( elemToFree->prevChunkInFreeList != NULL )
   3.465 -    { printf( "error: freeing same element twice!" ); exit(1);
   3.466 -    }
   3.467 -
   3.468 -   _VMSMasterEnv->amtOfOutstandingMem -= sizeOfElem;
   3.469 -
   3.470 -   nextLowerElem  = elemToFree->nextLowerInMem;
   3.471 -   nextHigherElem = elemToFree->nextHigherInMem;
   3.472 -
   3.473 -   if( nextHigherElem == NULL )
   3.474 -      higherExistsAndIsFree = FALSE;
   3.475 -   else //okay exists, now check if in the free-list by checking back ptr
   3.476 -      higherExistsAndIsFree = (nextHigherElem->prevChunkInFreeList != NULL);
   3.477 -    
   3.478 -   if( nextLowerElem == NULL )
   3.479 -      lowerExistsAndIsFree = FALSE;
   3.480 -   else //okay, it exists, now check if it's free
   3.481 -      lowerExistsAndIsFree = (nextLowerElem->prevChunkInFreeList != NULL);
   3.482 -    
   3.483 -
   3.484 -      //now, know what exists and what's free
   3.485 -   if( lowerExistsAndIsFree )
   3.486 -    { if( higherExistsAndIsFree )
   3.487 -       {    //both exist and are free, so coalesce all three
   3.488 -            //First, remove higher from free-list
   3.489 -         nextHigherElem->prevChunkInFreeList->nextChunkInFreeList =
   3.490 -                                         nextHigherElem->nextChunkInFreeList;
   3.491 -         if( nextHigherElem->nextChunkInFreeList != NULL ) //end-of-list?
   3.492 -            nextHigherElem->nextChunkInFreeList->prevChunkInFreeList =
   3.493 -                                         nextHigherElem->prevChunkInFreeList;
   3.494 -            //Now, fix-up sequence-in-mem list -- by side-effect, this also
   3.495 -            // changes size of the lower elem, which is still in free-list
   3.496 -         nextLowerElem->nextHigherInMem = nextHigherElem->nextHigherInMem;
   3.497 -         if( nextHigherElem->nextHigherInMem !=
   3.498 -             _VMSMasterEnv->freeListHead->nextHigherInMem )
   3.499 -            nextHigherElem->nextHigherInMem->nextLowerInMem = nextLowerElem;
   3.500 -            //notice didn't do anything to elemToFree -- it simply is no
   3.501 -            // longer reachable from any of the lists.  Wonder if could be a
   3.502 -            // security leak because left valid addresses in it,
   3.503 -            // but don't care for now.
   3.504 -       }
   3.505 -      else
   3.506 -       {    //lower is the only of the two that exists and is free,
   3.507 -            //In this case, no adjustment to free-list, just change mem-list.
   3.508 -            // By side-effect, changes size of the lower elem
   3.509 -         nextLowerElem->nextHigherInMem = elemToFree->nextHigherInMem;
   3.510 -         if( elemToFree->nextHigherInMem !=
   3.511 -             _VMSMasterEnv->freeListHead->nextHigherInMem )
   3.512 -            elemToFree->nextHigherInMem->nextLowerInMem = nextLowerElem;
   3.513 -       }
   3.514 -    }
   3.515 -   else
   3.516 -    {    //lower either doesn't exist or isn't free, so check higher
   3.517 -      if( higherExistsAndIsFree )
   3.518 -       {    //higher exists and is the only of the two free
   3.519 -            //First, in free-list, replace higher elem with the one to free
   3.520 -         elemToFree->nextChunkInFreeList=nextHigherElem->nextChunkInFreeList;
   3.521 -         elemToFree->prevChunkInFreeList=nextHigherElem->prevChunkInFreeList;
   3.522 -         elemToFree->prevChunkInFreeList->nextChunkInFreeList = elemToFree;
   3.523 -         if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
   3.524 -            elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
   3.525 -            //Now chg mem-list. By side-effect, changes size of elemToFree
   3.526 -         elemToFree->nextHigherInMem = nextHigherElem->nextHigherInMem;
   3.527 -         if( elemToFree->nextHigherInMem !=
   3.528 -             _VMSMasterEnv->freeListHead->nextHigherInMem )
   3.529 -            elemToFree->nextHigherInMem->nextLowerInMem = elemToFree;
   3.530 -       }
   3.531 -      else
   3.532 -       {    //neither lower nor higher is availabe to coalesce so add to list
   3.533 -            // this makes prev chunk ptr non-null, which indicates it's free
   3.534 -         elemToFree->nextChunkInFreeList =
   3.535 -                            _VMSMasterEnv->freeListHead->nextChunkInFreeList;
   3.536 -         _VMSMasterEnv->freeListHead->nextChunkInFreeList = elemToFree;
   3.537 -         if( elemToFree->nextChunkInFreeList != NULL ) // end-of-list?
   3.538 -            elemToFree->nextChunkInFreeList->prevChunkInFreeList =elemToFree;
   3.539 -         elemToFree->prevChunkInFreeList = _VMSMasterEnv->freeListHead;
   3.540 -       }
   3.541 -    }
   3.542 +   }
   3.543     //============================= MEASUREMENT STUFF ========================
   3.544     #ifdef MEAS__TIME_MALLOC
   3.545     saveLowTimeStampCountInto( endStamp );
   3.546 @@ -440,43 +287,47 @@
   3.547  
   3.548  /*Designed to be called from the main thread outside of VMS, during init
   3.549   */
   3.550 -MallocProlog *
   3.551 +MallocArrays *
   3.552  VMS_ext__create_free_list()
   3.553 - { MallocProlog *freeListHead, *firstChunk;
   3.554 -
   3.555 -      //Note, this is running in the main thread -- all increases in malloc
   3.556 -      // mem and all frees of it must be done in this thread, with the
   3.557 -      // thread's original stack available
   3.558 -   freeListHead = malloc( sizeof(MallocProlog) );
   3.559 -   firstChunk   = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
   3.560 +{     
   3.561 +   //Initialize containers for small chunks and fill with zeros
   3.562 +   _VMSMasterEnv->freeLists = (MallocArrays*)malloc( sizeof(MallocArrays) );
   3.563 +   MallocArrays *freeLists = _VMSMasterEnv->freeLists;
   3.564 +   
   3.565 +   freeLists->smallChunks = 
   3.566 +           (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
   3.567 +   memset((void*)freeLists->smallChunks,
   3.568 +           0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
   3.569 +   
   3.570 +   //Calculate number of containers for big chunks
   3.571 +   uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
   3.572 +   
   3.573 +   freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
   3.574 +   memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
   3.575 +   freeLists->containerCount = container;
   3.576 +   
   3.577 +   //Create first element in lastContainer 
   3.578 +   MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
   3.579     if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
   3.580     
   3.581 -   //Touch memory to avoid page faults
   3.582 -   void *ptr,*endPtr; 
   3.583 -   endPtr = (void*)firstChunk+MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE;
   3.584 -   for(ptr = firstChunk; ptr < endPtr; ptr+=PAGE_SIZE)
   3.585 -   {
   3.586 -       *(char*)ptr = 0;
   3.587 -   }
   3.588 -
   3.589 -   freeListHead->prevChunkInFreeList = NULL;
   3.590 -      //Use this addr to free the heap when cleanup
   3.591 -   freeListHead->nextLowerInMem      = firstChunk;
   3.592 -      //to identify top-of-heap elem, compare this addr to elem's next higher
   3.593 -   freeListHead->nextHigherInMem     = (void*)( (uintptr_t)firstChunk +
   3.594 -                                         MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
   3.595 -   freeListHead->nextChunkInFreeList = firstChunk;
   3.596 -
   3.597 -   firstChunk->nextChunkInFreeList   = NULL;
   3.598 -   firstChunk->prevChunkInFreeList   = freeListHead;
   3.599 -      //next Higher has to be set to top of chunk, so can calc size in malloc
   3.600 -   firstChunk->nextHigherInMem       = (void*)( (uintptr_t)firstChunk +
   3.601 -                                         MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE);
   3.602 -   firstChunk->nextLowerInMem        = NULL; //identifies as bott of heap
   3.603 +   firstChunk->nextLowerInMem = NULL;
   3.604 +   firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
   3.605 +                        MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE - sizeof(MallocProlog*));
   3.606 +   firstChunk->nextChunkInFreeList = NULL;
   3.607 +   //previous element in the queue is the container
   3.608 +   firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
   3.609     
   3.610 -   _VMSMasterEnv->amtOfOutstandingMem = 0; //none allocated yet
   3.611 -
   3.612 -   return freeListHead;
   3.613 +   freeLists->bigChunks[container-1] = firstChunk;
   3.614 +   
   3.615 +   //Create dummy chunk to mark the top of stack this is of course
   3.616 +   //never freed
   3.617 +   MallocProlog *dummyChunk = firstChunk->nextHigherInMem;
   3.618 +   dummyChunk->nextHigherInMem = dummyChunk+1;
   3.619 +   dummyChunk->nextLowerInMem  = NULL;
   3.620 +   dummyChunk->nextChunkInFreeList = NULL;
   3.621 +   dummyChunk->prevChunkInFreeList = NULL;
   3.622 +   
   3.623 +   return freeLists;
   3.624   }
   3.625  
   3.626  

     4.1 --- a/vmalloc.h	Tue Jul 26 16:14:30 2011 +0200
     4.2 +++ b/vmalloc.h	Tue Aug 02 15:44:28 2011 +0200
     4.3 @@ -14,6 +14,14 @@
     4.4  #include <inttypes.h>
     4.5  #include "VMS_primitive_data_types.h"
     4.6  
     4.7 +#define SMALL_CHUNK_SIZE 32
     4.8 +#define SMALL_CHUNK_COUNT 4
     4.9 +#define LOWER_BOUND 128
    4.10 +#define CHUNK_INCREASE_RATE 1.25
    4.11 +
    4.12 +#define LOG54 0.096910013
    4.13 +#define LOG128 2.10720997
    4.14 +
    4.15  typedef struct _MallocProlog MallocProlog;
    4.16  
    4.17  struct _MallocProlog
    4.18 @@ -24,6 +32,16 @@
    4.19     MallocProlog *nextLowerInMem;
    4.20   };
    4.21  //MallocProlog
    4.22 + 
    4.23 + typedef struct MallocArrays MallocArrays;
    4.24 +
    4.25 + struct MallocArrays
    4.26 + {
    4.27 +     MallocProlog **smallChunks;
    4.28 +     MallocProlog **bigChunks;
    4.29 +     uint32       containerCount;
    4.30 + };
    4.31 + //MallocArrays
    4.32  
    4.33  typedef struct
    4.34   {
    4.35 @@ -52,7 +70,7 @@
    4.36  VMS__free_in_ext( void *ptrToFree );
    4.37  
    4.38  
    4.39 -MallocProlog *
    4.40 +MallocArrays *
    4.41  VMS_ext__create_free_list();
    4.42  
    4.43  void