1.1 --- a/VMS.c	Tue Aug 02 15:44:28 2011 +0200
     1.2 +++ b/VMS.c	Wed Aug 03 13:23:32 2011 +0200
     1.3 @@ -678,8 +678,8 @@
     1.4     //SchedSlot     ***allSchedSlots; //ptr to array of ptrs
     1.5  
     1.6        //Before getting rid of everything, print out any measurements made
     1.7 -   forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&printHist );
     1.8 -   forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&saveHistToFile);
     1.9 +   //forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&printHist );
    1.10 +   //forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, (DynArrayFnPtr)&saveHistToFile);
    1.11     //forAllInDynArrayDo( _VMSMasterEnv->measHistsInfo, &freeHistExt );
    1.12     #ifdef MEAS__TIME_PLUGIN
    1.13     printHist( _VMSMasterEnv->reqHdlrLowTimeHist );

     2.1 --- a/vmalloc.c	Tue Aug 02 15:44:28 2011 +0200
     2.2 +++ b/vmalloc.c	Wed Aug 03 13:23:32 2011 +0200
     2.3 @@ -17,13 +17,16 @@
     2.4  #include "VMS.h"
     2.5  #include "Histogram/Histogram.h"
     2.6  
     2.7 +//A MallocProlog is a head element if the HigherInMem variable is NULL
     2.8 +//A Chunk is free if the prevChunkInFreeList variable is NULL
     2.9 +
    2.10  /*
    2.11   * This calculates the container which fits the given size.
    2.12   */
    2.13  inline
    2.14  uint32 getContainer(size_t size)
    2.15  {
    2.16 -    return floor((log10(size)-LOG128)/LOG54);
    2.17 +    return (log10(size)-LOG128)/LOG54;
    2.18  }
    2.19  
    2.20  /*
    2.21 @@ -53,23 +56,33 @@
    2.22      return removedChunk;
    2.23  }
    2.24  
    2.25 +inline
    2.26 +void recycleSmallChunks(MallocProlog** container)
    2.27 +{
    2.28 +    //TODO recycle small chunks
    2.29 +}
    2.30 +
    2.31  /*
    2.32   * Removes a chunk from a free list.
    2.33   */
    2.34  inline
    2.35 -MallocProlog *extractChunk(MallocProlog* chunk)
    2.36 +void extractChunk(MallocProlog* chunk)
    2.37  {
    2.38 -    
    2.39 +   chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
    2.40 +   if(chunk->nextChunkInFreeList)
    2.41 +       chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
    2.42  }
    2.43  
    2.44  /*
    2.45   * Merges two chunks.
    2.46 - * Chunk A has to be before chunk B in memory.
    2.47 + * Chunk A has to be before chunk B in memory. Both have to be removed from
    2.48 + * a free list
    2.49   */
    2.50  inline
    2.51  MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
    2.52  {
    2.53 -    
    2.54 +    chunkA->nextHigherInMem = chunkB->nextHigherInMem;
    2.55 +    return chunkA;
    2.56  }
    2.57  /*
    2.58   * Inserts a chunk into a free list.
    2.59 @@ -110,6 +123,31 @@
    2.60              (uintptr_t)chunk - sizeof(MallocProlog);
    2.61  }
    2.62  
    2.63 +
    2.64 +/*
    2.65 + * This makes 5 Chunks of the requested size.
    2.66 + */
    2.67 +inline
    2.68 +void makeChunks(size_t size, MallocProlog **container)
    2.69 +{
    2.70 +    MallocArrays *freeLists = _VMSMasterEnv->freeLists;
    2.71 +    size_t addedSize = 5*(size + sizeof(MallocProlog));
    2.72 +    
    2.73 +    uint32 containerIdx = getContainer(addedSize)+4;
    2.74 +    while(freeLists->bigChunks[containerIdx] == NULL )
    2.75 +        containerIdx++;
    2.76 +    
    2.77 +    MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
    2.78 +    
    2.79 +    int i;
    2.80 +    for(i=0; i<5; i++)
    2.81 +    {
    2.82 +        insertChunk(divideChunk(foundChunk,size), container);
    2.83 +    }
    2.84 +    containerIdx = getContainer(getChunkSize(foundChunk));
    2.85 +    insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
    2.86 +}
    2.87 +
    2.88  /*
    2.89   * This is sequential code, meant to only be called from the Master, not from
    2.90   * any slave VPs.
    2.91 @@ -123,13 +161,23 @@
    2.92     #endif
    2.93     //========================================================================
    2.94     
    2.95 +   
    2.96     MallocArrays* freeList = _VMSMasterEnv->freeLists;
    2.97     
    2.98     //Return a small chunk if the requested size is smaller than 128B
    2.99 -   //TODO: for now set size to 129B
   2.100 -   if(sizeRequested < 128)
   2.101 -       sizeRequested = 129;
   2.102 -           
   2.103 +   if(sizeRequested <= LOWER_BOUND)
   2.104 +   {
   2.105 +       uint32 freeListIdx = (sizeRequested-1)/32;
   2.106 +       if(freeList->smallChunkCount[freeListIdx] == 0)
   2.107 +       {
   2.108 +           makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]);
   2.109 +           freeList->smallChunkCount[freeListIdx] += 5;
   2.110 +       }
   2.111 +       
   2.112 +       freeList->smallChunkCount[freeListIdx]--;
   2.113 +       return removeChunk(&freeList->smallChunks[freeListIdx]) + 1;
   2.114 +   }
   2.115 +   
   2.116     //Calculate the expected container. Start one higher to have a Chunk that's
   2.117     //always big enough.
   2.118     uint32 targetContainerIdx = getContainer(sizeRequested);
   2.119 @@ -141,7 +189,7 @@
   2.120         while(freeList->bigChunks[containerIdx] == NULL)
   2.121         {
   2.122             containerIdx++;
   2.123 -           if(containerIdx > freeList->containerCount)
   2.124 +           if(containerIdx >= freeList->containerCount)
   2.125             {
   2.126                 printf("VMS malloc failed: low memory");
   2.127                 exit(1);
   2.128 @@ -149,23 +197,15 @@
   2.129         }
   2.130         
   2.131         foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
   2.132 -       //Found bigger Element, so we have to divide until it fits the
   2.133 -       //requested size
   2.134 -       containerIdx--;       
   2.135 -       size_t containerSize = getContainerSize(containerIdx);
   2.136         size_t chunkSize     = getChunkSize(foundChunk);
   2.137         
   2.138 -       while(containerIdx > targetContainerIdx)
   2.139 +       if(chunkSize > sizeRequested + sizeof(MallocProlog))
   2.140         {
   2.141 -           if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog))
   2.142 -           {
   2.143 -               MallocProlog *newChunk = divideChunk(foundChunk,containerSize);
   2.144 -               insertChunk(newChunk,&freeList->bigChunks[containerIdx]);
   2.145 -               chunkSize = getChunkSize(foundChunk);
   2.146 -           }
   2.147 -           containerIdx--;
   2.148 -           containerSize /= CHUNK_INCREASE_RATE;
   2.149 -       }
   2.150 +           MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
   2.151 +           containerIdx = getContainer(chunkSize - sizeRequested - sizeof(MallocProlog));
   2.152 +           insertChunk(foundChunk,&freeList->bigChunks[containerIdx]);
   2.153 +           foundChunk = newChunk;
   2.154 +       }        
   2.155     }
   2.156     else
   2.157     {
   2.158 @@ -181,9 +221,9 @@
   2.159     addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
   2.160     #endif
   2.161     //========================================================================
   2.162 -
   2.163 +   
   2.164     //skip over the prolog by adding its size to the pointer return
   2.165 -   return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog));
   2.166 +   return foundChunk + 1;
   2.167   }
   2.168  
   2.169  /*
   2.170 @@ -201,17 +241,50 @@
   2.171     #endif
   2.172     //========================================================================
   2.173     
   2.174 -   MallocArrays* freeList = _VMSMasterEnv->freeLists;
   2.175 +   MallocArrays* freeLists = _VMSMasterEnv->freeLists;
   2.176     MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
   2.177 +   uint32 containerIdx;
   2.178 +
   2.179 +   size_t chunkSize = getChunkSize(chunkToFree);
   2.180 +   if(chunkSize <= LOWER_BOUND)
   2.181 +   {
   2.182 +       containerIdx = (chunkSize-1)/32;
   2.183 +       insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]);
   2.184 +       freeLists->smallChunkCount[containerIdx]++;
   2.185 +       
   2.186 +       if(freeLists->smallChunkCount[containerIdx] > 20)
   2.187 +           recycleSmallChunks(&freeLists->smallChunks[containerIdx]);
   2.188 +       
   2.189 +       return;
   2.190 +   }
   2.191     
   2.192     //Check for free neighbors
   2.193     if(chunkToFree->nextLowerInMem)
   2.194     {
   2.195         if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
   2.196         {//Chunk is not allocated
   2.197 -           mergeChunks()
   2.198 +           if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
   2.199 +           {
   2.200 +               extractChunk(chunkToFree->nextLowerInMem);
   2.201 +               chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
   2.202 +           }
   2.203         }
   2.204     }
   2.205 +   if(chunkToFree->nextHigherInMem)
   2.206 +   {
   2.207 +       if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
   2.208 +       {//Chunk is not allocated
   2.209 +           if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
   2.210 +           {
   2.211 +               extractChunk(chunkToFree->nextHigherInMem);
   2.212 +               chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
   2.213 +           }
   2.214 +       }
   2.215 +   }
   2.216 +
   2.217 +   containerIdx = getContainer(chunkSize);
   2.218 +   insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
   2.219 +   
   2.220     //============================= MEASUREMENT STUFF ========================
   2.221     #ifdef MEAS__TIME_MALLOC
   2.222     saveLowTimeStampCountInto( endStamp );
   2.223 @@ -298,10 +371,11 @@
   2.224             (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
   2.225     memset((void*)freeLists->smallChunks,
   2.226             0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
   2.227 +   memset((void*)freeLists->smallChunkCount,
   2.228 +           0,SMALL_CHUNK_COUNT*sizeof(uint32));
   2.229     
   2.230     //Calculate number of containers for big chunks
   2.231     uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
   2.232 -   
   2.233     freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
   2.234     memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
   2.235     freeLists->containerCount = container;
   2.236 @@ -309,6 +383,7 @@
   2.237     //Create first element in lastContainer 
   2.238     MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
   2.239     if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
   2.240 +   freeLists->memSpace = firstChunk;
   2.241     
   2.242     firstChunk->nextLowerInMem = NULL;
   2.243     firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
   2.244 @@ -334,13 +409,11 @@
   2.245  /*Designed to be called from the main thread outside of VMS, during cleanup
   2.246   */
   2.247  void
   2.248 -VMS_ext__free_free_list( MallocProlog *freeListHead )
   2.249 +VMS_ext__free_free_list( MallocArrays *freeLists )
   2.250   {    
   2.251 -      //stashed a ptr to the one and only bug chunk malloc'd from OS in the
   2.252 -      // free list head's next lower in mem pointer
   2.253 -   free( freeListHead->nextLowerInMem );
   2.254 -
   2.255 -   //don't free the head -- it'll be in an array eventually -- free whole
   2.256 -   // array when all the free lists linked from it have already been freed
   2.257 +   free(freeLists->memSpace);
   2.258 +   free(freeLists->bigChunks);
   2.259 +   free(freeLists->smallChunks);
   2.260 +   
   2.261   }
   2.262  

     3.1 --- a/vmalloc.h	Tue Aug 02 15:44:28 2011 +0200
     3.2 +++ b/vmalloc.h	Wed Aug 03 13:23:32 2011 +0200
     3.3 @@ -18,6 +18,8 @@
     3.4  #define SMALL_CHUNK_COUNT 4
     3.5  #define LOWER_BOUND 128
     3.6  #define CHUNK_INCREASE_RATE 1.25
     3.7 +#define MAX_SMALL_CHUNKS 20
     3.8 +#define SMALL_CHUNKS_ALLOCATION 5
     3.9  
    3.10  #define LOG54 0.096910013
    3.11  #define LOG128 2.10720997
    3.12 @@ -38,7 +40,9 @@
    3.13   struct MallocArrays
    3.14   {
    3.15       MallocProlog **smallChunks;
    3.16 +     uint32       smallChunkCount[SMALL_CHUNK_COUNT];
    3.17       MallocProlog **bigChunks;
    3.18 +     void         *memSpace;
    3.19       uint32       containerCount;
    3.20   };
    3.21   //MallocArrays
    3.22 @@ -74,6 +78,6 @@
    3.23  VMS_ext__create_free_list();
    3.24  
    3.25  void
    3.26 -VMS_ext__free_free_list( MallocProlog *freeListHead );
    3.27 +VMS_ext__free_free_list(MallocArrays *freeLists );
    3.28  
    3.29  #endif
    3.30 \ No newline at end of file