From d105a8707a8c9609f1c44c32be4274ff0ab38ddf Mon Sep 17 00:00:00 2001 From: Sumant Kowshik Date: Thu, 7 Aug 2003 05:31:04 +0000 Subject: [PATCH] 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 --- .../libpoolalloc/PoolAllocatorChained.c | 266 +++++++++++++----- 1 file changed, 196 insertions(+), 70 deletions(-) diff --git a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c b/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c index ca94656f25f..b3a715fe9b6 100644 --- a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c +++ b/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c @@ -1,11 +1,17 @@ #include +#include #include #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... */ -- 2.34.1