Change implementation so that variable sized slabs are used to allow arbitrary sized array allocations

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7663 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 196 insertions, 70 deletions

diff --git a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c b/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c
index ca94656f25..b3a715fe9b 100644
--- a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c
+++ b/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c
@@ -1,11 +1,17 @@
 #include <assert.h>
+#include <stdio.h>
 #include <stdlib.h>
 
 #undef assert
 #define assert(X)
 
 
-#define NODES_PER_SLAB 65536
+/* In the current implementation, each slab in the pool has NODES_PER_SLAB
+ * nodes unless the isSingleArray flag is set in which case it contains a
+ * single array of size ArraySize. Small arrays (size <= NODES_PER_SLAB) are
+ * still allocated in the slabs of size NODES_PER_SLAB
+ */
+#define NODES_PER_SLAB 512 
 
 typedef struct PoolTy {
   void    *Data;
@@ -24,6 +30,11 @@ typedef struct PoolSlab {
   struct PoolSlab *Next;
   unsigned char AllocatedBitVector[NODES_PER_SLAB/8];
   unsigned char StartOfAllocation[NODES_PER_SLAB/8];
+
+  unsigned isSingleArray;   /* If this slab is used for exactly one array */
+  /* The array is allocated from the start to the end of the slab */
+  unsigned ArraySize;       /* The size of the array allocated */ 
+
   char Data[1];   /* Buffer to hold data in this slab... variable sized */
 
 } PoolSlab;
@@ -45,7 +56,10 @@ typedef struct PoolSlab {
 /* poolinit - Initialize a pool descriptor to empty
  */
 void poolinit(PoolTy *Pool, unsigned NodeSize) {
-  assert(Pool && "Null pool pointer passed into poolinit!");
+  if (!Pool) {
+    printf("Null pool pointer passed into poolinit!\n");
+    exit(1);
+  }
 
   Pool->NodeSize = NodeSize;
   Pool->Data = 0;
@@ -55,7 +69,11 @@ void poolinit(PoolTy *Pool, unsigned NodeSize) {
 }
 
 void poolmakeunfreeable(PoolTy *Pool) {
-  assert(Pool && "Null pool pointer passed in to poolmakeunfreeable!");
+  if (!Pool) {
+    printf("Null pool pointer passed in to poolmakeunfreeable!\n");
+    exit(1);
+  }
+
   Pool->FreeablePool = 0;
 }
 
@@ -63,7 +81,11 @@ void poolmakeunfreeable(PoolTy *Pool) {
  */
 void pooldestroy(PoolTy *Pool) {
   PoolSlab *PS;
-  assert(Pool && "Null pool pointer passed in to pooldestroy!");
+  if (!Pool) {
+    printf("Null pool pointer passed in to pooldestroy!\n");
+    exit(1);
+  }
+
   PS = (PoolSlab*)Pool->Data;
   while (PS) {
     PoolSlab *Next = PS->Next;
@@ -75,6 +97,12 @@ void pooldestroy(PoolTy *Pool) {
 static void *FindSlabEntry(PoolSlab *PS, unsigned NodeSize) {
   /* Loop through all of the slabs looking for one with an opening */
   for (; PS; PS = PS->Next) {
+
+    /* If the slab is a single array, go on to the next slab */
+    /* Don't allocate single nodes in a SingleArray slab */
+    if (PS->isSingleArray) 
+      continue;
+
     /* Check to see if there are empty entries at the end of the slab... */
     if (PS->LastUsed < NODES_PER_SLAB-1) {
       /* Mark the returned entry used */
@@ -118,8 +146,16 @@ char *poolalloc(PoolTy *Pool) {
   PoolSlab *PS;
   void *Result;
 
-  assert(Pool && "Null pool pointer passed in to poolalloc!");
+  if (!Pool) {
+    printf("Null pool pointer passed in to poolalloc!\n");
+    exit(1);
+  }
+  
   NodeSize = Pool->NodeSize;
+  // Return if this pool has size 0
+  if (NodeSize == 0)
+    return 0;
+
   PS = (PoolSlab*)Pool->Data;
 
   if ((Result = FindSlabEntry(PS, NodeSize)))
@@ -128,11 +164,17 @@ char *poolalloc(PoolTy *Pool) {
   /* Otherwise we must allocate a new slab and add it to the list */
   PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1);
 
-  assert (PS && "Could not allocate memory!");
+  if (!PS) {
+    printf("poolalloc: Could not allocate memory!");
+    exit(1);
+  }
 
   /* Initialize the slab to indicate that the first element is allocated */
   PS->FirstUnused = 1;
   PS->LastUsed = 0;
+  /* This is not a single array */
+  PS->isSingleArray = 0;
+  PS->ArraySize = 0;
   
   MARK_NODE_ALLOCATED(PS, 0);
   SET_START_BIT(PS, 0);
@@ -149,56 +191,97 @@ void poolfree(PoolTy *Pool, char *Node) {
   PoolSlab **PPS;
   unsigned idxiter;
 
-  assert(Pool && "Null pool pointer passed in to poolfree!");
+  if (!Pool) {
+    printf("Null pool pointer passed in to poolfree!\n");
+    exit(1);
+  }
+
   NodeSize = Pool->NodeSize;
+
+  // Return if this pool has size 0
+  if (NodeSize == 0)
+    return;
+
   PS = (PoolSlab*)Pool->Data;
   PPS = (PoolSlab**)&Pool->Data;
 
-  /* Seach for the slab that contains this node... */
-  while (&PS->Data[0] > Node || &PS->Data[NodeSize*NODES_PER_SLAB] < Node) {
-    assert(PS && "free'd node not found in allocation pool specified!");
+  /* Search for the slab that contains this node... */
+  while (&PS->Data[0] > Node || &PS->Data[NodeSize*NODES_PER_SLAB-1] < Node) {
+    if (!PS) { 
+      printf("poolfree: node being free'd not found in allocation pool specified!\n");
+      exit(1);
+    }
+
     PPS = &PS->Next;
     PS = PS->Next;
   }
 
+  /* PS now points to the slab where Node is */
+
   Idx = (Node-&PS->Data[0])/NodeSize;
   assert(Idx < NODES_PER_SLAB && "Pool slab searching loop broken!");
 
-  assert(ALLOCATION_BEGINS(PS, Idx) && 
-	 "Attempt to free middle of allocated array");
+  if (PS->isSingleArray) {
 
-  /* Free the first node */
-  CLEAR_START_BIT(PS, Idx);
-  MARK_NODE_FREE(PS, Idx);
+    /* If this slab is a SingleArray */
 
-  // Free all nodes 
-  idxiter = Idx + 1;
-  while (idxiter < NODES_PER_SLAB && (!ALLOCATION_BEGINS(PS,idxiter)) && 
-	 (NODE_ALLOCATED(PS, idxiter))) {
-    MARK_NODE_FREE(PS, idxiter);
-  }
+    if (Idx != 0) {
+      printf("poolfree: Attempt to free middle of allocated array\n");
+      exit(1);
+    }
+    if (!NODE_ALLOCATED(PS,0)) {
+      printf("poolfree: Attempt to free node that is already freed\n");
+      exit(1);
+    }
+    /* Mark this SingleArray slab as being free by just marking the first
+       entry as free*/
+    MARK_NODE_FREE(PS, 0);
+  } else {
+    
+    /* If this slab is not a SingleArray */
+    
+    if (!ALLOCATION_BEGINS(PS, Idx)) { 
+      printf("poolfree: Attempt to free middle of allocated array\n");
+    }
 
-  /* Update the first free field if this node is below the free node line */
-  if (Idx < PS->FirstUnused) PS->FirstUnused = Idx;
-  
-  /* If we are not freeing the last element in a slab... */
-  if (idxiter - 1 != PS->LastUsed) {
-    return;
-  }
+    /* Free the first node */
+    if (!NODE_ALLOCATED(PS, Idx)) {
+      printf("poolfree: Attempt to free node that is already freed\n");
+      exit(1); 
+    }
+    CLEAR_START_BIT(PS, Idx);
+    MARK_NODE_FREE(PS, Idx);
+    
+    // Free all nodes 
+    idxiter = Idx + 1;
+    while (idxiter < NODES_PER_SLAB && (!ALLOCATION_BEGINS(PS,idxiter)) && 
+	   (NODE_ALLOCATED(PS, idxiter))) {
+      MARK_NODE_FREE(PS, idxiter);
+      ++idxiter;
+    }
 
-  /* Otherwise we are freeing the last element in a slab... shrink the
-   * LastUsed marker down to last used node.
-   */
-  PS->LastUsed = Idx;
-  do {
-    --PS->LastUsed;
-    /* Fixme, this should scan the allocated array an entire byte at a time for
-     * performance!
+    /* Update the first free field if this node is below the free node line */
+    if (Idx < PS->FirstUnused) PS->FirstUnused = Idx;
+    
+    /* If we are not freeing the last element in a slab... */
+    if (idxiter - 1 != PS->LastUsed) {
+      return;
+    }
+
+    /* Otherwise we are freeing the last element in a slab... shrink the
+     * LastUsed marker down to last used node.
      */
-  } while (PS->LastUsed >= 0 && (!NODE_ALLOCATED(PS, PS->LastUsed)));
-  
-  assert(PS->FirstUnused <= PS->LastUsed+1 &&
-         "FirstUnused field was out of date!");
+    PS->LastUsed = Idx;
+    do {
+      --PS->LastUsed;
+      /* Fixme, this should scan the allocated array an entire byte at a time 
+       * for performance!
+       */
+    } while (PS->LastUsed >= 0 && (!NODE_ALLOCATED(PS, PS->LastUsed)));
+    
+    assert(PS->FirstUnused <= PS->LastUsed+1 &&
+	   "FirstUnused field was out of date!");
+  }
     
   /* Ok, if this slab is empty, we unlink it from the of slabs and either move
    * it to the head of the list, or free it, depending on whether or not there
@@ -206,33 +289,38 @@ void poolfree(PoolTy *Pool, char *Node) {
    */
   /* Do this only if the pool is freeable */
   if (Pool->FreeablePool) {
-    if (PS->LastUsed == -1) {   /* Empty slab? */
+    if (PS->isSingleArray) {
+      /* If it is a SingleArray, just free it */
+      *PPS = PS->Next;
+      free(PS);
+    } else if (PS->LastUsed == -1) {   /* Empty slab? */
       PoolSlab *HeadSlab;
       *PPS = PS->Next;   /* Unlink from the list of slabs... */
       
       HeadSlab = (PoolSlab*)Pool->Data;
-      if (HeadSlab && HeadSlab->LastUsed == -1){/* List already has empty slab? */
-	free(PS);                               /* Free memory for slab */
+      if (HeadSlab && HeadSlab->LastUsed == -1){/*List already has empty slab?*/
+	free(PS);                               /*Free memory for slab */
       } else {
-	PS->Next = HeadSlab;                    /* No empty slab yet, add this */
-	Pool->Data = PS;                        /* one to the head of the list */
+	PS->Next = HeadSlab;                    /*No empty slab yet, add this*/
+	Pool->Data = PS;                        /*one to the head of the list */
       }
     }
   } else {
     /* Pool is not freeable for safety reasons */
     /* Leave it in the list of PoolSlabs as an empty PoolSlab */
-    if (PS->LastUsed == -1) {
-      PS->FirstUnused = 0;
-      
-      /* Do not free the pool, but move it to the head of the list if there is no
-	 empty slab there already */
-      PoolSlab *HeadSlab;
-      HeadSlab = (PoolSlab*)Pool->Data;
-      if (HeadSlab && HeadSlab->LastUsed != -1) {
-	PS->Next = HeadSlab;
-	Pool->Data = PS;
+    if (!PS->isSingleArray)
+      if (PS->LastUsed == -1) {
+	PS->FirstUnused = 0;
+	
+	/* Do not free the pool, but move it to the head of the list if there is
+	   no empty slab there already */
+	PoolSlab *HeadSlab;
+	HeadSlab = (PoolSlab*)Pool->Data;
+	if (HeadSlab && HeadSlab->LastUsed != -1) {
+	  PS->Next = HeadSlab;
+	  Pool->Data = PS;
+	}
       }
-    }
   }
 }
 
@@ -243,6 +331,21 @@ static void *FindSlabEntryArray(PoolSlab *PS, unsigned NodeSize,
 
   /* Loop through all of the slabs looking for one with an opening */
   for (; PS; PS = PS->Next) {
+    
+    /* For large array allocation */
+    if (Size > NODES_PER_SLAB) {
+      /* If this slab is a SingleArray that is free with size > Size, use it */
+      if (PS->isSingleArray && !NODE_ALLOCATED(PS,0) && PS->ArraySize >= Size) {
+	/* Allocate the array in this slab */
+	MARK_NODE_ALLOCATED(PS,0); /* In a single array, only the first node
+				      needs to be marked */
+	return &PS->Data[0];
+      } else
+	continue;
+    } else if (PS->isSingleArray)
+      continue; /* Do not allocate small arrays in SingleArray slabs */
+
+    /* For small array allocation */
     /* Check to see if there are empty entries at the end of the slab... */
     if (PS->LastUsed < NODES_PER_SLAB-Size) {
       /* Mark the returned entry used and set the start bit*/
@@ -277,7 +380,7 @@ static void *FindSlabEntryArray(PoolSlab *PS, unsigned NodeSize,
 	  foundArray = 0;
 
       if (foundArray) {
-	/* Successfully allocate out the first unused node */
+	/* Successfully allocate starting from the first unused node */
 	SET_START_BIT(PS, Idx);
 	for (i = Idx; i < Idx + Size; ++i)
 	  MARK_NODE_ALLOCATED(PS, i);
@@ -303,28 +406,51 @@ char* poolallocarray(PoolTy* Pool, unsigned Size) {
   void *Result;
   unsigned i;
 
-  assert(Pool && "Null pool pointer passed in to poolallocarray!");
+  if (!Pool) {
+    printf("Null pool pointer passed to poolallocarray!\n");
+    exit(1);
+  }
+
   NodeSize = Pool->NodeSize;
-  PS = (PoolSlab*)Pool->Data;
 
-  assert(Size <= NODES_PER_SLAB && 
-	 "Exceeded the maximum size of an individual malloc");
+  // Return if this pool has size 0
+  if (NodeSize == 0)
+    return 0;
+
+  PS = (PoolSlab*)Pool->Data;
 
   if ((Result = FindSlabEntryArray(PS, NodeSize,Size)))
     return Result;
 
   /* Otherwise we must allocate a new slab and add it to the list */
-  PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1);
-
-  assert (PS && "Could not allocate memory!");
+  if (Size > NODES_PER_SLAB) {
+    /* Allocate a new slab of size Size */
+    PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*Size-1);
+    if (!PS) {
+      printf("poolallocarray: Could not allocate memory!\n");
+      exit(1);
+    }
+    PS->isSingleArray = 1;
+    PS->ArraySize = Size;
+    MARK_NODE_ALLOCATED(PS, 0);
+  } else {
+    PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1);
+    if (!PS) {
+      printf("poolallocarray: Could not allocate memory!\n");
+      exit(1);
+    }
 
-  /* Initialize the slab to indicate that the first element is allocated */
-  PS->FirstUnused = Size;
-  PS->LastUsed = Size - 1;
+    /* Initialize the slab to indicate that the first element is allocated */
+    PS->FirstUnused = Size;
+    PS->LastUsed = Size - 1;
+    
+    PS->isSingleArray = 0;
+    PS->ArraySize = 0;
 
-  SET_START_BIT(PS, 0);
-  for (i = 0; i < Size; ++i) {
-    MARK_NODE_ALLOCATED(PS, i);
+    SET_START_BIT(PS, 0);
+    for (i = 0; i < Size; ++i) {
+      MARK_NODE_ALLOCATED(PS, i);
+    }
   }
 
   /* Add the slab to the list... */