# HG changeset patch
# User Merten Sach <msach@mailbox.tu-berlin.de>
# Date 1314282733 -7200
# Node ID 62c59f2ac9f16cb56fa0df2c181f0f0d1423a613
# Parent  def70e32cf2c2716639db9371f19992982d57bde
first changes malloc

diff -r def70e32cf2c -r 62c59f2ac9f1 vmalloc.c
--- a/vmalloc.c	Wed Aug 03 13:23:32 2011 +0200
+++ b/vmalloc.c	Thu Aug 25 16:32:13 2011 +0200
@@ -17,6 +17,8 @@
 #include "VMS.h"
 #include "Histogram/Histogram.h"
 
+#define MAX_UINT64 0xFFFFFFFFFFFFFFFF
+
 //A MallocProlog is a head element if the HigherInMem variable is NULL
 //A Chunk is free if the prevChunkInFreeList variable is NULL
 
@@ -66,11 +68,16 @@
  * Removes a chunk from a free list.
  */
 inline
-void extractChunk(MallocProlog* chunk)
+void extractChunk(MallocProlog* chunk, MallocArrays *freeLists)
 {
    chunk->prevChunkInFreeList->nextChunkInFreeList = chunk->nextChunkInFreeList;
    if(chunk->nextChunkInFreeList)
        chunk->nextChunkInFreeList->prevChunkInFreeList = chunk->prevChunkInFreeList;
+   if(*(chunk->prevChunkInFreeList) == NULL)
+   {
+       uint32 containerIdx = (uintptr_t)(chunk->prevChunkInFreeList - freeLists->bigChunks) / sizeof(MallocProlog*);
+       freeLists->bigChunksSearchVector &= ~(1 << containerIdx); 
+   }
 }
 
 /*
@@ -162,20 +169,20 @@
    //========================================================================
    
    
-   MallocArrays* freeList = _VMSMasterEnv->freeLists;
+   MallocArrays* freeLists = _VMSMasterEnv->freeLists;
    
    //Return a small chunk if the requested size is smaller than 128B
    if(sizeRequested <= LOWER_BOUND)
    {
        uint32 freeListIdx = (sizeRequested-1)/32;
-       if(freeList->smallChunkCount[freeListIdx] == 0)
+       if(freeLists->smallChunkCount[freeListIdx] == 0)
        {
-           makeChunks((freeListIdx+1)*32, &freeList->smallChunks[freeListIdx]);
-           freeList->smallChunkCount[freeListIdx] += 5;
+           makeChunks((freeListIdx+1)*32, &freeLists->smallChunks[freeListIdx]);
+           freeLists->smallChunkCount[freeListIdx] += 5;
        }
        
-       freeList->smallChunkCount[freeListIdx]--;
-       return removeChunk(&freeList->smallChunks[freeListIdx]) + 1;
+       freeLists->smallChunkCount[freeListIdx]--;
+       return removeChunk(&freeLists->smallChunks[freeListIdx]) + 1;
    }
    
    //Calculate the expected container. Start one higher to have a Chunk that's
@@ -184,8 +191,19 @@
    uint32 containerIdx = targetContainerIdx + 1;
    
    MallocProlog* foundChunk;
-   if(freeList->bigChunks[containerIdx] == NULL)
+   if(freeLists->bigChunks[containerIdx] == NULL)
    {
+       uint64 searchVector = freeLists->bigChunksSearchVector;
+       //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++;
@@ -194,22 +212,24 @@
                printf("VMS malloc failed: low memory");
                exit(1);
            }
-       }
+       }*/
        
-       foundChunk = removeChunk(&freeList->bigChunks[containerIdx]);
+       foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]);
        size_t chunkSize     = getChunkSize(foundChunk);
        
-       if(chunkSize > sizeRequested + sizeof(MallocProlog))
+       //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(chunkSize - sizeRequested - sizeof(MallocProlog));
-           insertChunk(foundChunk,&freeList->bigChunks[containerIdx]);
+           containerIdx = getContainer(getChunkSize(newChunk));
+           insertChunk(foundChunk,&freeLists->bigChunks[containerIdx]);
+           freeLists->bigChunksSearchVector |= 1 << containerIdx;
            foundChunk = newChunk;
        }        
    }
    else
    {
-        foundChunk = removeChunk(&freeList->bigChunks[containerIdx]); 
+        foundChunk = removeChunk(&freeLists->bigChunks[containerIdx]); 
    }
    
    //Mark as allocated
@@ -393,6 +413,8 @@
    firstChunk->prevChunkInFreeList = freeLists->bigChunks[container-1];
    
    freeLists->bigChunks[container-1] = firstChunk;
+   //Insert into bit search list
+   freeLists->bigChunksSearchVector |= (1 << (container-1));
    
    //Create dummy chunk to mark the top of stack this is of course
    //never freed
diff -r def70e32cf2c -r 62c59f2ac9f1 vmalloc.h
--- a/vmalloc.h	Wed Aug 03 13:23:32 2011 +0200
+++ b/vmalloc.h	Thu Aug 25 16:32:13 2011 +0200
@@ -42,6 +42,7 @@
      MallocProlog **smallChunks;
      uint32       smallChunkCount[SMALL_CHUNK_COUNT];
      MallocProlog **bigChunks;
+     uint64       bigChunksSearchVector;
      void         *memSpace;
      uint32       containerCount;
  };