1.1 --- a/vmalloc.c	Wed Aug 03 13:23:32 2011 +0200
     1.2 +++ b/vmalloc.c	Thu Aug 25 16:32:13 2011 +0200
     1.3 @@ -17,6 +17,8 @@
     1.4  #include "VMS.h"
     1.5  #include "Histogram/Histogram.h"
     1.6  
     1.7 +#define MAX_UINT64 0xFFFFFFFFFFFFFFFF
     1.8 +
     1.9  //A MallocProlog is a head element if the HigherInMem variable is NULL
    1.10  //A Chunk is free if the prevChunkInFreeList variable is NULL
    1.11  
    1.12 @@ -66,11 +68,16 @@
    1.13   * Removes a chunk from a free list.
    1.14   */
    1.15  inline
    1.16 -void extractChunk(MallocProlog* chunk)
    1.17 +void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
    1.18  {
    1.19     chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
    1.20     if(chunk->nextChunkInFreeList)
    1.21         chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
    1.22 +   if(*(chunk->prevChunkInFreeList) == NULL)
    1.23 +   {
    1.24 +       uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*);
    1.25 +       freeLists->bigChunksSearchVector &= ~(1 << containerIdx); 
    1.26 +   }
    1.27  }
    1.28  
    1.29  /*
    1.30 @@ -162,20 +169,20 @@
    1.31     //========================================================================
    1.32     
    1.33     
    1.34 -   MallocArrays* freeList = _VMSMasterEnv->freeLists;
    1.35 +   MallocArrays* freeLists = _VMSMasterEnv->freeLists;
    1.36     
    1.37     //Return a small chunk if the requested size is smaller than 128B
    1.38     if(sizeRequested <= LOWER_BOUND)
    1.39     {
    1.40         uint32 freeListIdx = (sizeRequested-1)/32;
    1.41 -       if(freeList->smallChunkCount[freeListIdx] == 0)
    1.42 +       if(freeLists->smallChunkCount[freeListIdx] == 0)
    1.43         {
    1.44 -           makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]);
    1.45 -           freeList->smallChunkCount[freeListIdx] += 5;
    1.46 +           makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]);
    1.47 +           freeLists->smallChunkCount[freeListIdx] += 5;
    1.48         }
    1.49         
    1.50 -       freeList->smallChunkCount[freeListIdx]--;
    1.51 -       return removeChunk(&freeList->smallChunks[freeListIdx]) + 1;
    1.52 +       freeLists->smallChunkCount[freeListIdx]--;
    1.53 +       return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1;
    1.54     }
    1.55     
    1.56     //Calculate the expected container. Start one higher to have a Chunk that's
    1.57 @@ -184,8 +191,19 @@
    1.58     uint32 containerIdx = targetContainerIdx + 1;
    1.59     
    1.60     MallocProlog* foundChunk;
    1.61 -   if(freeList->bigChunks[containerIdx] == NULL)
    1.62 +   if(freeLists->bigChunks[containerIdx] == NULL)
    1.63     {
    1.64 +       uint64 searchVector = freeLists->bigChunksSearchVector;
    1.65 +       //set small chunk bits to zero
    1.66 +       searchVector &= MAX_UINT64 << containerIdx;
    1.67 +       containerIdx = __builtin_ffsl(searchVector);
    1.68 +       
    1.69 +       if(containerIdx == 0)
    1.70 +       {
    1.71 +           printf("VMS malloc failed: low memory");
    1.72 +           exit(1);
    1.73 +       }
    1.74 +       /*
    1.75         while(freeList->bigChunks[containerIdx] == NULL)
    1.76         {
    1.77             containerIdx++;
    1.78 @@ -194,22 +212,24 @@
    1.79                 printf("VMS malloc failed: low memory");
    1.80                 exit(1);
    1.81             }
    1.82 -       }
    1.83 +       }*/
    1.84         
    1.85 -       foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
    1.86 +       foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
    1.87         size_t chunkSize     = getChunkSize(foundChunk);
    1.88         
    1.89 -       if(chunkSize > sizeRequested + sizeof(MallocProlog))
    1.90 +       //If the new chunk is larger than the requested size: split
    1.91 +       if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)
    1.92         {
    1.93             MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
    1.94 -           containerIdx = getContainer(chunkSize - sizeRequested - sizeof(MallocProlog));
    1.95 -           insertChunk(foundChunk,&freeList->bigChunks[containerIdx]);
    1.96 +           containerIdx = getContainer(getChunkSize(newChunk));
    1.97 +           insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
    1.98 +           freeLists->bigChunksSearchVector |= 1 << containerIdx;
    1.99             foundChunk = newChunk;
   1.100         }        
   1.101     }
   1.102     else
   1.103     {
   1.104 -        foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); 
   1.105 +        foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 
   1.106     }
   1.107     
   1.108     //Mark as allocated
   1.109 @@ -393,6 +413,8 @@
   1.110     firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
   1.111     
   1.112     freeLists->bigChunks[container-1] = firstChunk;
   1.113 +   //Insert into bit search list
   1.114 +   freeLists->bigChunksSearchVector |= (1 << (container-1));
   1.115     
   1.116     //Create dummy chunk to mark the top of stack this is of course
   1.117     //never freed

     2.1 --- a/vmalloc.h	Wed Aug 03 13:23:32 2011 +0200
     2.2 +++ b/vmalloc.h	Thu Aug 25 16:32:13 2011 +0200
     2.3 @@ -42,6 +42,7 @@
     2.4       MallocProlog **smallChunks;
     2.5       uint32       smallChunkCount[SMALL_CHUNK_COUNT];
     2.6       MallocProlog **bigChunks;
     2.7 +     uint64       bigChunksSearchVector;
     2.8       void         *memSpace;
     2.9       uint32       containerCount;
    2.10   };