1.1 --- a/vmalloc.c	Tue Aug 02 15:44:28 2011 +0200
     1.2 +++ b/vmalloc.c	Wed Aug 03 13:23:32 2011 +0200
     1.3 @@ -17,13 +17,16 @@
     1.4  #include "VMS.h"
     1.5  #include "Histogram/Histogram.h"
     1.6  
     1.7 +//A MallocProlog is a head element if the HigherInMem variable is NULL
     1.8 +//A Chunk is free if the prevChunkInFreeList variable is NULL
     1.9 +
    1.10  /*
    1.11   * This calculates the container which fits the given size.
    1.12   */
    1.13  inline
    1.14  uint32 getContainer(size_t size)
    1.15  {
    1.16 -    return floor((log10(size)-LOG128)/LOG54);
    1.17 +    return (log10(size)-LOG128)/LOG54;
    1.18  }
    1.19  
    1.20  /*
    1.21 @@ -53,23 +56,33 @@
    1.22      return removedChunk;
    1.23  }
    1.24  
    1.25 +inline
    1.26 +void recycleSmallChunks(MallocProlog** container)
    1.27 +{
    1.28 +    //TODO recycle small chunks
    1.29 +}
    1.30 +
    1.31  /*
    1.32   * Removes a chunk from a free list.
    1.33   */
    1.34  inline
    1.35 -MallocProlog *extractChunk(MallocProlog* chunk)
    1.36 +void extractChunk(MallocProlog* chunk)
    1.37  {
    1.38 -    
    1.39 +   chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
    1.40 +   if(chunk->nextChunkInFreeList)
    1.41 +       chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
    1.42  }
    1.43  
    1.44  /*
    1.45   * Merges two chunks.
    1.46 - * Chunk A has to be before chunk B in memory.
    1.47 + * Chunk A has to be before chunk B in memory. Both have to be removed from
    1.48 + * a free list
    1.49   */
    1.50  inline
    1.51  MallocProlog *mergeChunks(MallocProlog* chunkA, MallocProlog* chunkB)
    1.52  {
    1.53 -    
    1.54 +    chunkA->nextHigherInMem = chunkB->nextHigherInMem;
    1.55 +    return chunkA;
    1.56  }
    1.57  /*
    1.58   * Inserts a chunk into a free list.
    1.59 @@ -110,6 +123,31 @@
    1.60              (uintptr_t)chunk - sizeof(MallocProlog);
    1.61  }
    1.62  
    1.63 +
    1.64 +/*
    1.65 + * This makes 5 Chunks of the requested size.
    1.66 + */
    1.67 +inline
    1.68 +void makeChunks(size_t size, MallocProlog **container)
    1.69 +{
    1.70 +    MallocArrays *freeLists = _VMSMasterEnv->freeLists;
    1.71 +    size_t addedSize = 5*(size + sizeof(MallocProlog));
    1.72 +    
    1.73 +    uint32 containerIdx = getContainer(addedSize)+4;
    1.74 +    while(freeLists->bigChunks[containerIdx] == NULL )
    1.75 +        containerIdx++;
    1.76 +    
    1.77 +    MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
    1.78 +    
    1.79 +    int i;
    1.80 +    for(i=0; i<5; i++)
    1.81 +    {
    1.82 +        insertChunk(divideChunk(foundChunk,size), container);
    1.83 +    }
    1.84 +    containerIdx = getContainer(getChunkSize(foundChunk));
    1.85 +    insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
    1.86 +}
    1.87 +
    1.88  /*
    1.89   * This is sequential code, meant to only be called from the Master, not from
    1.90   * any slave VPs.
    1.91 @@ -123,13 +161,23 @@
    1.92     #endif
    1.93     //========================================================================
    1.94     
    1.95 +   
    1.96     MallocArrays* freeList = _VMSMasterEnv->freeLists;
    1.97     
    1.98     //Return a small chunk if the requested size is smaller than 128B
    1.99 -   //TODO: for now set size to 129B
   1.100 -   if(sizeRequested < 128)
   1.101 -       sizeRequested = 129;
   1.102 -           
   1.103 +   if(sizeRequested <= LOWER_BOUND)
   1.104 +   {
   1.105 +       uint32 freeListIdx = (sizeRequested-1)/32;
   1.106 +       if(freeList->smallChunkCount[freeListIdx] == 0)
   1.107 +       {
   1.108 +           makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]);
   1.109 +           freeList->smallChunkCount[freeListIdx] += 5;
   1.110 +       }
   1.111 +       
   1.112 +       freeList->smallChunkCount[freeListIdx]--;
   1.113 +       return removeChunk(&freeList->smallChunks[freeListIdx]) + 1;
   1.114 +   }
   1.115 +   
   1.116     //Calculate the expected container. Start one higher to have a Chunk that's
   1.117     //always big enough.
   1.118     uint32 targetContainerIdx = getContainer(sizeRequested);
   1.119 @@ -141,7 +189,7 @@
   1.120         while(freeList->bigChunks[containerIdx] == NULL)
   1.121         {
   1.122             containerIdx++;
   1.123 -           if(containerIdx > freeList->containerCount)
   1.124 +           if(containerIdx >= freeList->containerCount)
   1.125             {
   1.126                 printf("VMS malloc failed: low memory");
   1.127                 exit(1);
   1.128 @@ -149,23 +197,15 @@
   1.129         }
   1.130         
   1.131         foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
   1.132 -       //Found bigger Element, so we have to divide until it fits the
   1.133 -       //requested size
   1.134 -       containerIdx--;       
   1.135 -       size_t containerSize = getContainerSize(containerIdx);
   1.136         size_t chunkSize     = getChunkSize(foundChunk);
   1.137         
   1.138 -       while(containerIdx > targetContainerIdx)
   1.139 +       if(chunkSize > sizeRequested + sizeof(MallocProlog))
   1.140         {
   1.141 -           if(chunkSize > containerSize + sizeRequested + sizeof(MallocProlog))
   1.142 -           {
   1.143 -               MallocProlog *newChunk = divideChunk(foundChunk,containerSize);
   1.144 -               insertChunk(newChunk,&freeList->bigChunks[containerIdx]);
   1.145 -               chunkSize = getChunkSize(foundChunk);
   1.146 -           }
   1.147 -           containerIdx--;
   1.148 -           containerSize /= CHUNK_INCREASE_RATE;
   1.149 -       }
   1.150 +           MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
   1.151 +           containerIdx = getContainer(chunkSize - sizeRequested - sizeof(MallocProlog));
   1.152 +           insertChunk(foundChunk,&freeList->bigChunks[containerIdx]);
   1.153 +           foundChunk = newChunk;
   1.154 +       }        
   1.155     }
   1.156     else
   1.157     {
   1.158 @@ -181,9 +221,9 @@
   1.159     addIntervalToHist( startStamp, endStamp, _VMSMasterEnv->mallocTimeHist );
   1.160     #endif
   1.161     //========================================================================
   1.162 -
   1.163 +   
   1.164     //skip over the prolog by adding its size to the pointer return
   1.165 -   return (void*)((uintptr_t)foundChunk + sizeof(MallocProlog));
   1.166 +   return foundChunk + 1;
   1.167   }
   1.168  
   1.169  /*
   1.170 @@ -201,17 +241,50 @@
   1.171     #endif
   1.172     //========================================================================
   1.173     
   1.174 -   MallocArrays* freeList = _VMSMasterEnv->freeLists;
   1.175 +   MallocArrays* freeLists = _VMSMasterEnv->freeLists;
   1.176     MallocProlog *chunkToFree = (MallocProlog*)ptrToFree - 1;
   1.177 +   uint32 containerIdx;
   1.178 +
   1.179 +   size_t chunkSize = getChunkSize(chunkToFree);
   1.180 +   if(chunkSize <= LOWER_BOUND)
   1.181 +   {
   1.182 +       containerIdx = (chunkSize-1)/32;
   1.183 +       insertChunk(chunkToFree,&freeLists->smallChunks[containerIdx]);
   1.184 +       freeLists->smallChunkCount[containerIdx]++;
   1.185 +       
   1.186 +       if(freeLists->smallChunkCount[containerIdx] > 20)
   1.187 +           recycleSmallChunks(&freeLists->smallChunks[containerIdx]);
   1.188 +       
   1.189 +       return;
   1.190 +   }
   1.191     
   1.192     //Check for free neighbors
   1.193     if(chunkToFree->nextLowerInMem)
   1.194     {
   1.195         if(chunkToFree->nextLowerInMem->prevChunkInFreeList != NULL)
   1.196         {//Chunk is not allocated
   1.197 -           mergeChunks()
   1.198 +           if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
   1.199 +           {
   1.200 +               extractChunk(chunkToFree->nextLowerInMem);
   1.201 +               chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
   1.202 +           }
   1.203         }
   1.204     }
   1.205 +   if(chunkToFree->nextHigherInMem)
   1.206 +   {
   1.207 +       if(chunkToFree->nextHigherInMem->prevChunkInFreeList != NULL)
   1.208 +       {//Chunk is not allocated
   1.209 +           if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
   1.210 +           {
   1.211 +               extractChunk(chunkToFree->nextHigherInMem);
   1.212 +               chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
   1.213 +           }
   1.214 +       }
   1.215 +   }
   1.216 +
   1.217 +   containerIdx = getContainer(chunkSize);
   1.218 +   insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
   1.219 +   
   1.220     //============================= MEASUREMENT STUFF ========================
   1.221     #ifdef MEAS__TIME_MALLOC
   1.222     saveLowTimeStampCountInto( endStamp );
   1.223 @@ -298,10 +371,11 @@
   1.224             (MallocProlog**)malloc(SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
   1.225     memset((void*)freeLists->smallChunks,
   1.226             0,SMALL_CHUNK_COUNT*sizeof(MallocProlog*));
   1.227 +   memset((void*)freeLists->smallChunkCount,
   1.228 +           0,SMALL_CHUNK_COUNT*sizeof(uint32));
   1.229     
   1.230     //Calculate number of containers for big chunks
   1.231     uint32 container = getContainer(MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE)+1;
   1.232 -   
   1.233     freeLists->bigChunks = (MallocProlog**)malloc(container*sizeof(MallocProlog*));
   1.234     memset((void*)freeLists->bigChunks,0,container*sizeof(MallocProlog*));
   1.235     freeLists->containerCount = container;
   1.236 @@ -309,6 +383,7 @@
   1.237     //Create first element in lastContainer 
   1.238     MallocProlog *firstChunk = malloc( MALLOC_ADDITIONAL_MEM_FROM_OS_SIZE );
   1.239     if( firstChunk == NULL ) {printf("malloc error\n"); exit(1);}
   1.240 +   freeLists->memSpace = firstChunk;
   1.241     
   1.242     firstChunk->nextLowerInMem = NULL;
   1.243     firstChunk->nextHigherInMem = (MallocProlog*)((uintptr_t)firstChunk +
   1.244 @@ -334,13 +409,11 @@
   1.245  /*Designed to be called from the main thread outside of VMS, during cleanup
   1.246   */
   1.247  void
   1.248 -VMS_ext__free_free_list( MallocProlog *freeListHead )
   1.249 +VMS_ext__free_free_list( MallocArrays *freeLists )
   1.250   {    
   1.251 -      //stashed a ptr to the one and only bug chunk malloc'd from OS in the
   1.252 -      // free list head's next lower in mem pointer
   1.253 -   free( freeListHead->nextLowerInMem );
   1.254 -
   1.255 -   //don't free the head -- it'll be in an array eventually -- free whole
   1.256 -   // array when all the free lists linked from it have already been freed
   1.257 +   free(freeLists->memSpace);
   1.258 +   free(freeLists->bigChunks);
   1.259 +   free(freeLists->smallChunks);
   1.260 +   
   1.261   }
   1.262