aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2001-10-15 06:57:04 +0000
committerH. Peter Anvin <hpa@zytor.com>2001-10-15 06:57:04 +0000
commitff243205e626e8761c50d0eaa4b3cd66d2f1908f (patch)
tree089fb1a1427df3425be026fa0a06b2f312af1833
parent85a914ba599e2b2db8ed74a59a049107d6f1bd19 (diff)
downloadlpsm-ff243205e626e8761c50d0eaa4b3cd66d2f1908f.tar.gz
lpsm-ff243205e626e8761c50d0eaa4b3cd66d2f1908f.tar.xz
lpsm-ff243205e626e8761c50d0eaa4b3cd66d2f1908f.zip
Implement realloc(). Not tested yet.
-rw-r--r--alloc.c177
1 files changed, 170 insertions, 7 deletions
diff --git a/alloc.c b/alloc.c
index f56486e..cc721a8 100644
--- a/alloc.c
+++ b/alloc.c
@@ -584,14 +584,22 @@ static void objstore_free_chunk(int xbit, int rorder)
set_bit(ah->free_bitmap, xbit);
}
-static void objstore_free_buddy(void *ptr)
+/*
+ * This routine finds the parameters for one particular
+ * buddy allocation from its address; used by free() and
+ * realloc().
+ */
+struct buddy_params {
+ int xbit;
+ int rorder;
+};
+static struct buddy_params objstore_find_alloc_buddy(void *ptr)
{
+ struct buddy_params bp;
uintptr_t offset = (uintptr_t)ptr - (uintptr_t)ah->data_start;
int order, rorder;
int xbit, obit;
- DPRINTF(("buddy: freeing allocation at %p\n", ptr));
-
assert(offset < (1UL << ah->arena_size_lg2)); /* Not inside the arena?? */
for ( rorder = 0, order = ah->arena_size_lg2 ;
@@ -605,15 +613,24 @@ static void objstore_free_buddy(void *ptr)
if ( test_bit(ah->alloc_bitmap, xbit) ) {
/* We're this order... */
- DPRINTF(("buddy: freeing rorder %2d %8d\n", rorder, xbit));
- clr_bit(ah->alloc_bitmap, xbit);
- objstore_free_chunk(xbit, rorder);
- return;
+ bp.xbit = xbit; bp.rorder = rorder;
+ return bp;
}
}
assert(0); /* Freeing bogus memory? */
}
+
+static void objstore_free_buddy(void *ptr)
+{
+ struct buddy_params bp;
+
+ DPRINTF(("buddy: freeing allocation at %p\n", ptr));
+ bp = objstore_find_alloc_buddy(ptr);
+ DPRINTF(("buddy: freeing rorder %2d %8d\n", bp.rorder, bp.xbit));
+ clr_bit(ah->alloc_bitmap, bp.xbit);
+ objstore_free_chunk(bp.xbit, bp.rorder);
+}
static void objstore_free_slab(void *ptr)
{
@@ -679,3 +696,149 @@ void objstore_free(void *ptr)
else
objstore_free_buddy(ptr);
}
+
+static void *objstore_realloc_buddy(void *ptr, size_t new_size)
+{
+ struct buddy_params bp;
+ int order, rorder, dorder;
+ int xbit, nxbit, i;
+
+ bp = objstore_find_alloc_buddy(ptr);
+
+ order = BUDDY_ORDER_MIN;
+ while ( new_size > ((size_t)1 << order) )
+ order++;
+ rorder = ah->arena_size_lg2 - order;
+
+ if ( rorder == bp.rorder ) {
+ return ptr; /* No change at all */
+ } else if ( rorder > bp.rorder ) {
+ /* Allocation shrink. Return the extra space to the arena;
+ no copy. */
+ dorder = rorder - bp.rorder;
+ nxbit = bp.xbit << dorder;
+
+ /* Clear the old allocation size bit. */
+ xbit = bp.xbit;
+ clr_bit(ah->alloc_bitmap, xbit);
+
+ /* Mark new buddies free */
+ for ( i = bp.rorder+1 ; i <= rorder ; i++ ) {
+ xbit <<= 1;
+ set_bit(ah->free_bitmap, xbit^1);
+ }
+
+ /* Finally, mark new allocation size */
+ set_bit(ah->alloc_bitmap, xbit);
+
+ /* Nothing moved */
+ return ptr;
+ } else {
+ /* Allocation enlargement. Try to see if we can claim all the
+ memory areas we need in order to avoid copying, otherwise
+ get new allocation and copy. */
+
+ dorder = bp.rorder - rorder;
+ nxbit = bp.xbit >> dorder;
+
+ xbit = bp.xbit;
+ for ( i = bp.rorder ; i > rorder ; i-- ) {
+ if ( !test_bit(ah->free_bitmap, xbit^1) ) {
+ /* A chunk we need is unavailable. Need to copy, sorry... */
+ void *nptr = objstore_malloc_buddy(new_size);
+ if ( !nptr )
+ return NULL; /* realloc failed */
+
+ memcpy(nptr, ptr, (size_t)1 << (ah->arena_size_lg2-bp.rorder));
+
+ /* Free the old area */
+ clr_bit(ah->alloc_bitmap, bp.xbit);
+ objstore_free_chunk(bp.xbit, bp.rorder);
+ return nptr;
+ }
+ xbit >>= 1;
+ }
+
+ /* Oh cool, we actually have the memory */
+ xbit = bp.xbit;
+
+ /* Remove old allocation bit */
+ clr_bit(ah->alloc_bitmap, xbit);
+
+ /* Claim the memory */
+ for ( i = bp.rorder ; i > rorder ; i-- ) {
+ clr_bit(ah->free_bitmap, xbit^1);
+ xbit >>= 1;
+ }
+
+ /* Add new allocation bit */
+ set_bit(ah->alloc_bitmap, xbit);
+
+ /* We didn't have to move... */
+ return ptr;
+ }
+}
+
+static void *objstore_realloc_slab(void *ptr, size_t new_size)
+{
+ struct slab_header *sh;
+ struct slab_info *si;
+
+ /* Slab header should be at the start of the page */
+ sh = (struct slab_header *)((uintptr_t)ptr & ~(BUDDY_SIZE_MIN-1));
+ assert(sh->magic == SLAB_MAGIC);
+
+ si = &ah->slab[sh->index];
+
+ /* For realloc(), tolerate the size being off by as much as a
+ factor of four... it's not worth copying then */
+ if ( new_size > si->size ) {
+ void *nptr = objstore_malloc_slab(new_size);
+ if ( !nptr )
+ return NULL;
+ memcpy(nptr, ptr, si->size);
+ objstore_free_slab(ptr);
+ return nptr;
+ } else if ( new_size < (si->size >> 2) ) {
+ void *nptr = objstore_malloc_slab(new_size);
+ if ( !nptr )
+ return ptr; /* Old allocation still OK */
+ memcpy(nptr, ptr, new_size);
+ objstore_free_slab(ptr);
+ return nptr;
+ } else {
+ /* Nothing to do... */
+ return ptr;
+ }
+}
+
+void *objstore_realloc(void *ptr, size_t new_size)
+{
+ int is_slab = (uintptr_t)ptr & (BUDDY_SIZE_MIN-1);
+ int slab_max = ah->slab[0].size;
+
+ if ( is_slab && new_size <= slab_max )
+ return objstore_realloc_slab(ptr, new_size);
+ else if ( !is_slab && new_size > slab_max )
+ return objstore_realloc_buddy(ptr, new_size);
+ else if ( is_slab ) {
+ /* Increase in size from slab to buddy */
+ void *nptr = objstore_malloc_buddy(new_size);
+ if ( !nptr )
+ return NULL;
+
+ /* This is overkill. Hopefully it won't matter. */
+ memcpy(nptr, nptr, slab_max);
+ objstore_free_slab(ptr);
+ return nptr;
+ } else {
+ /* Decrease in size from buddy to slab */
+ void *nptr = objstore_malloc_slab(new_size);
+ if ( !nptr )
+ return ptr; /* Old allocation still OK */
+ memcpy(nptr, ptr, new_size);
+ objstore_free_buddy(ptr);
+ return nptr;
+ }
+}
+