diff options
author | H. Peter Anvin <hpa@zytor.com> | 2001-10-15 06:57:04 +0000 |
---|---|---|
committer | H. Peter Anvin <hpa@zytor.com> | 2001-10-15 06:57:04 +0000 |
commit | ff243205e626e8761c50d0eaa4b3cd66d2f1908f (patch) | |
tree | 089fb1a1427df3425be026fa0a06b2f312af1833 | |
parent | 85a914ba599e2b2db8ed74a59a049107d6f1bd19 (diff) | |
download | lpsm-ff243205e626e8761c50d0eaa4b3cd66d2f1908f.tar.gz lpsm-ff243205e626e8761c50d0eaa4b3cd66d2f1908f.tar.xz lpsm-ff243205e626e8761c50d0eaa4b3cd66d2f1908f.zip |
Implement realloc(). Not tested yet.
-rw-r--r-- | alloc.c | 177 |
1 files changed, 170 insertions, 7 deletions
@@ -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; + } +} + |