# HG changeset patch
# User Merten Sach <msach@mailbox.tu-berlin.de>
# Date 1314630540 -7200
# Node ID 35547e66b971f82b72b431bdb929b8f53960900d
# Parent  62c59f2ac9f16cb56fa0df2c181f0f0d1423a613
malloc: multiple small chunk allocation

diff -r 62c59f2ac9f1 -r 35547e66b971 vmalloc.c
--- a/vmalloc.c	Thu Aug 25 16:32:13 2011 +0200
+++ b/vmalloc.c	Mon Aug 29 17:09:00 2011 +0200
@@ -46,9 +46,37 @@
  * the free list is empty, so make sure this is not the case.
  */
 inline
-MallocProlog *removeChunk(MallocProlog** container)
+MallocProlog *removeChunk(MallocArrays* freeLists, uint32 containerIdx)
 {
-    MallocProlog *removedChunk = *container;
+    MallocProlog** container = &freeLists->bigChunks[containerIdx];
+    MallocProlog*  removedChunk = *container;
+    *container = removedChunk->nextChunkInFreeList;
+    
+    if(removedChunk->nextChunkInFreeList)
+        removedChunk->nextChunkInFreeList->prevChunkInFreeList = 
+                (MallocProlog*)container;
+    
+    if(*container == NULL)
+    {
+       if(containerIdx < 64)
+           freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); 
+       else
+           freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64));
+    }
+    
+    return removedChunk;
+}
+
+/*
+ * Removes the first chunk of a freeList
+ * The chunk is removed but not set as free. There is no check if
+ * the free list is empty, so make sure this is not the case.
+ */
+inline
+MallocProlog *removeSmallChunk(MallocArrays* freeLists, uint32 containerIdx)
+{
+    MallocProlog** container = &freeLists->smallChunks[containerIdx];
+    MallocProlog*  removedChunk = *container;
     *container = removedChunk->nextChunkInFreeList;
     
     if(removedChunk->nextChunkInFreeList)
@@ -73,10 +101,16 @@
    chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
    if(chunk->nextChunkInFreeList)
        chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
-   if(*(chunk->prevChunkInFreeList) == NULL)
+   
+   //The last element in the list points to the container. If the container points
+   //to NULL the container is empty
+   if(*((void**)(chunk->prevChunkInFreeList)) == NULL)
    {
-       uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*);
-       freeLists->bigChunksSearchVector &= ~(1 << containerIdx); 
+       uint32 containerIdx = ((uintptr_t)chunk->prevChunkInFreeList - (uintptr_t)freeLists->bigChunks) >> 6;
+       if(containerIdx < (uint32)64)
+           freeLists->bigChunksSearchVector[0] &= ~((uint64)1 << containerIdx); 
+       if(containerIdx < 128 && containerIdx >=64)
+           freeLists->bigChunksSearchVector[1] &= ~((uint64)1 << (containerIdx-64)); 
    }
 }
 
@@ -144,7 +178,7 @@
     while(freeLists->bigChunks[containerIdx] == NULL )
         containerIdx++;
     
-    MallocProlog *foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
+    MallocProlog *foundChunk = removeChunk(freeLists, containerIdx);
     
     int i;
     for(i=0; i<5; i++)
@@ -153,6 +187,10 @@
     }
     containerIdx = getContainer(getChunkSize(foundChunk));
     insertChunk(foundChunk, &freeLists->bigChunks[containerIdx]);
+    if(containerIdx < 64)
+        freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
+    else
+        freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
 }
 
 /*
@@ -168,7 +206,6 @@
    #endif
    //========================================================================
    
-   
    MallocArrays* freeLists = _VMSMasterEnv->freeLists;
    
    //Return a small chunk if the requested size is smaller than 128B
@@ -182,54 +219,54 @@
        }
        
        freeLists->smallChunkCount[freeListIdx]--;
-       return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1;
+       return removeSmallChunk(freeLists, freeListIdx) + 1;
    }
    
    //Calculate the expected container. Start one higher to have a Chunk that's
    //always big enough.
-   uint32 targetContainerIdx = getContainer(sizeRequested);
-   uint32 containerIdx = targetContainerIdx + 1;
+   uint32 containerIdx = getContainer(sizeRequested) + 1;
    
    MallocProlog* foundChunk;
    if(freeLists->bigChunks[containerIdx] == NULL)
    {
-       uint64 searchVector = freeLists->bigChunksSearchVector;
+       uint64 searchVector = freeLists->bigChunksSearchVector[0];
        //set small chunk bits to zero
        searchVector &= MAX_UINT64 << containerIdx;
        containerIdx = __builtin_ffsl(searchVector);
        
        if(containerIdx == 0)
        {
-           printf("VMS malloc failed: low memory");
-           exit(1);
-       }
-       /*
-       while(freeList->bigChunks[containerIdx] == NULL)
-       {
-           containerIdx++;
-           if(containerIdx >= freeList->containerCount)
+           searchVector = freeLists->bigChunksSearchVector[1];
+           containerIdx = __builtin_ffsl(searchVector);
+           if(containerIdx == 0)
            {
                printf("VMS malloc failed: low memory");
-               exit(1);
+               exit(1);   
            }
-       }*/
+           containerIdx += 64;
+       }
+       containerIdx--;
        
-       foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
+       
+       foundChunk = removeChunk(freeLists, containerIdx);
        size_t chunkSize     = getChunkSize(foundChunk);
        
        //If the new chunk is larger than the requested size: split
        if(chunkSize > sizeRequested + 2 * sizeof(MallocProlog) + LOWER_BOUND)
        {
            MallocProlog *newChunk = divideChunk(foundChunk,sizeRequested);
-           containerIdx = getContainer(getChunkSize(newChunk));
+           containerIdx = getContainer(getChunkSize(foundChunk));
            insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
-           freeLists->bigChunksSearchVector |= 1 << containerIdx;
+           if(containerIdx < 64)
+               freeLists->bigChunksSearchVector[0] |= ((uint64)1 << containerIdx);
+           else
+               freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (containerIdx-64));
            foundChunk = newChunk;
        }        
    }
    else
    {
-        foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 
+        foundChunk = removeChunk(freeLists, containerIdx); 
    }
    
    //Mark as allocated
@@ -285,7 +322,7 @@
        {//Chunk is not allocated
            if(getChunkSize(chunkToFree->nextLowerInMem) > LOWER_BOUND)
            {
-               extractChunk(chunkToFree->nextLowerInMem);
+               extractChunk(chunkToFree->nextLowerInMem, freeLists);
                chunkToFree = mergeChunks(chunkToFree->nextLowerInMem, chunkToFree);
            }
        }
@@ -296,14 +333,18 @@
        {//Chunk is not allocated
            if(getChunkSize(chunkToFree->nextHigherInMem) > LOWER_BOUND)
            {
-               extractChunk(chunkToFree->nextHigherInMem);
+               extractChunk(chunkToFree->nextHigherInMem, freeLists);
                chunkToFree = mergeChunks(chunkToFree, chunkToFree->nextHigherInMem);
            }
        }
    }
 
-   containerIdx = getContainer(chunkSize);
+   containerIdx = getContainer(getChunkSize(chunkToFree));
    insertChunk(chunkToFree, &freeLists->bigChunks[containerIdx]);
+   if(containerIdx < 64)
+       freeLists->bigChunksSearchVector[0] |= (uint64)1 << containerIdx;
+   else
+       freeLists->bigChunksSearchVector[1] |= (uint64)1 << (containerIdx-64);
    
    //============================= MEASUREMENT STUFF ========================
    #ifdef MEAS__TIME_MALLOC
@@ -414,7 +455,10 @@
    
    freeLists->bigChunks[container-1] = firstChunk;
    //Insert into bit search list
-   freeLists->bigChunksSearchVector |= (1 << (container-1));
+   if(container <= 64)
+       freeLists->bigChunksSearchVector[0] |= ((uint64)1 << (container-1));
+   else
+       freeLists->bigChunksSearchVector[1] |= ((uint64)1 << (container-65));
    
    //Create dummy chunk to mark the top of stack this is of course
    //never freed
diff -r 62c59f2ac9f1 -r 35547e66b971 vmalloc.h
--- a/vmalloc.h	Thu Aug 25 16:32:13 2011 +0200
+++ b/vmalloc.h	Mon Aug 29 17:09:00 2011 +0200
@@ -42,7 +42,7 @@
      MallocProlog **smallChunks;
      uint32       smallChunkCount[SMALL_CHUNK_COUNT];
      MallocProlog **bigChunks;
-     uint64       bigChunksSearchVector;
+     uint64       bigChunksSearchVector[2];
      void         *memSpace;
      uint32       containerCount;
  };