1.1 --- a/vmalloc.c	Thu Aug 25 16:32:13 2011 +0200
     1.2 +++ b/vmalloc.c	Mon Aug 29 17:09:00 2011 +0200
     1.3 @@ -46,9 +46,37 @@
     1.4   * the free list is empty, so make sure this is not the case.
     1.5   */
     1.6  inline
     1.7 -MallocProlog *removeChunk(MallocProlog** container)
     1.8 +MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
     1.9  {
    1.10 -    MallocProlog *removedChunk = *container;
    1.11 +    MallocProlog** container = &freeLists->bigChunks[containerIdx];
    1.12 +    MallocProlog*  removedChunk = *container;
    1.13 +    *container = removedChunk->nextChunkInFreeList;
    1.14 +    
    1.15 +    if(removedChunk->nextChunkInFreeList)
    1.16 +        removedChunk->nextChunkInFreeList->prevChunkInFreeList = 
    1.17 +                (MallocProlog*)container;
    1.18 +    
    1.19 +    if(*container == NULL)
    1.20 +    {
    1.21 +       if(containerIdx < 64)
    1.22 +           freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); 
    1.23 +       else
    1.24 +           freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
    1.25 +    }
    1.26 +    
    1.27 +    return removedChunk;
    1.28 +}
    1.29 +
    1.30 +/*
    1.31 + * Removes the first chunk of a freeList
    1.32 + * The chunk is removed but not set as free. There is no check if
    1.33 + * the free list is empty, so make sure this is not the case.
    1.34 + */
    1.35 +inline
    1.36 +MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
    1.37 +{
    1.38 +    MallocProlog** container = &freeLists->smallChunks[containerIdx];
    1.39 +    MallocProlog*  removedChunk = *container;
    1.40      *container = removedChunk->nextChunkInFreeList;
    1.41      
    1.42      if(removedChunk->nextChunkInFreeList)
    1.43 @@ -73,10 +101,16 @@
    1.44     chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
    1.45     if(chunk->nextChunkInFreeList)
    1.46         chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
    1.47 -   if(*(chunk->prevChunkInFreeList) == NULL)
    1.48 +   
    1.49 +   //The last element in the list points to the container. If the container points
    1.50 +   //to NULL the container is empty
    1.51 +   if(*((void**)(chunk->prevChunkInFreeList)) == NULL)
    1.52     {
    1.53 -       uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*);
    1.54 -       freeLists->bigChunksSearchVector &= ~(1 << containerIdx); 
    1.55 +       uint32 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 6;
    1.56 +       if(containerIdx < (uint32)64)
    1.57 +           freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); 
    1.58 +       if(containerIdx < 128 && containerIdx >=64)
    1.59 +           freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); 
    1.60     }
    1.61  }
    1.62  
    1.63 @@ -144,7 +178,7 @@
    1.64      while(freeLists->bigChunks[containerIdx] == NULL )
    1.65          containerIdx++;
    1.66      
    1.67 -    MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
    1.68 +    MallocProlog *foundChunk = removeChunk(freeLists, containerIdx);
    1.69      
    1.70      int i;
    1.71      for(i=0; i<5; i++)
    1.72 @@ -153,6 +187,10 @@
    1.73      }
    1.74      containerIdx = getContainer(getChunkSize(foundChunk));
    1.75      insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
    1.76 +    if(containerIdx < 64)
    1.77 +        freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
    1.78 +    else
    1.79 +        freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
    1.80  }
    1.81  
    1.82  /*
    1.83 @@ -168,7 +206,6 @@
    1.84     #endif
    1.85     //========================================================================
    1.86     
    1.87 -   
    1.88     MallocArrays* freeLists = _VMSMasterEnv->freeLists;
    1.89     
    1.90     //Return a small chunk if the requested size is smaller than 128B
    1.91 @@ -182,54 +219,54 @@
    1.92         }
    1.93         
    1.94         freeLists->smallChunkCount[freeListIdx]--;
    1.95 -       return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1;
    1.96 +       return removeSmallChunk(freeLists, freeListIdx) + 1;
    1.97     }
    1.98     
    1.99     //Calculate the expected container. Start one higher to have a Chunk that's
   1.100     //always big enough.
   1.101 -   uint32 targetContainerIdx = getContainer(sizeRequested);
   1.102 -   uint32 containerIdx = targetContainerIdx + 1;
   1.103 +   uint32 containerIdx = getContainer(sizeRequested) + 1;
   1.104     
   1.105     MallocProlog* foundChunk;
   1.106     if(freeLists->bigChunks[containerIdx] == NULL)
   1.107     {
   1.108 -       uint64 searchVector = freeLists->bigChunksSearchVector;
   1.109 +       uint64 searchVector = freeLists->bigChunksSearchVector[0];
   1.110         //set small chunk bits to zero
   1.111         searchVector &= MAX_UINT64 << containerIdx;
   1.112         containerIdx = __builtin_ffsl(searchVector);
   1.113         
   1.114         if(containerIdx == 0)
   1.115         {
   1.116 -           printf("VMS malloc failed: low memory");
   1.117 -           exit(1);
   1.118 -       }
   1.119 -       /*
   1.120 -       while(freeList->bigChunks[containerIdx] == NULL)
   1.121 -       {
   1.122 -           containerIdx++;
   1.123 -           if(containerIdx >= freeList->containerCount)
   1.124 +           searchVector = freeLists->bigChunksSearchVector[1];
   1.125 +           containerIdx = __builtin_ffsl(searchVector);
   1.126 +           if(containerIdx == 0)
   1.127             {
   1.128                 printf("VMS malloc failed: low memory");
   1.129 -               exit(1);
   1.130 +               exit(1);   
   1.131             }
   1.132 -       }*/
   1.133 +           containerIdx += 64;
   1.134 +       }
   1.135 +       containerIdx--;
   1.136         
   1.137 -       foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
   1.138 +       
   1.139 +       foundChunk = removeChunk(freeLists, containerIdx);
   1.140         size_t chunkSize     = getChunkSize(foundChunk);
   1.141         
   1.142         //If the new chunk is larger than the requested size: split
   1.143         if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)
   1.144         {
   1.145             MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
   1.146 -           containerIdx = getContainer(getChunkSize(newChunk));
   1.147 +           containerIdx = getContainer(getChunkSize(foundChunk));
   1.148             insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
   1.149 -           freeLists->bigChunksSearchVector |= 1 << containerIdx;
   1.150 +           if(containerIdx < 64)
   1.151 +               freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
   1.152 +           else
   1.153 +               freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
   1.154             foundChunk = newChunk;
   1.155         }        
   1.156     }
   1.157     else
   1.158     {
   1.159 -        foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 
   1.160 +        foundChunk = removeChunk(freeLists, containerIdx); 
   1.161     }
   1.162     
   1.163     //Mark as allocated
   1.164 @@ -285,7 +322,7 @@
   1.165         {//Chunk is not allocated
   1.166             if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
   1.167             {
   1.168 -               extractChunk(chunkToFree->nextLowerInMem);
   1.169 +               extractChunk(chunkToFree->nextLowerInMem, freeLists);
   1.170                 chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
   1.171             }
   1.172         }
   1.173 @@ -296,14 +333,18 @@
   1.174         {//Chunk is not allocated
   1.175             if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
   1.176             {
   1.177 -               extractChunk(chunkToFree->nextHigherInMem);
   1.178 +               extractChunk(chunkToFree->nextHigherInMem, freeLists);
   1.179                 chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
   1.180             }
   1.181         }
   1.182     }
   1.183  
   1.184 -   containerIdx = getContainer(chunkSize);
   1.185 +   containerIdx = getContainer(getChunkSize(chunkToFree));
   1.186     insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
   1.187 +   if(containerIdx < 64)
   1.188 +       freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
   1.189 +   else
   1.190 +       freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
   1.191     
   1.192     //============================= MEASUREMENT STUFF ========================
   1.193     #ifdef MEAS__TIME_MALLOC
   1.194 @@ -414,7 +455,10 @@
   1.195     
   1.196     freeLists->bigChunks[container-1] = firstChunk;
   1.197     //Insert into bit search list
   1.198 -   freeLists->bigChunksSearchVector |= (1 << (container-1));
   1.199 +   if(container <= 64)
   1.200 +       freeLists->bigChunksSearchVector[0] |= ((uint64)1 << (container-1));
   1.201 +   else
   1.202 +       freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (container-65));
   1.203     
   1.204     //Create dummy chunk to mark the top of stack this is of course
   1.205     //never freed