aboutsummaryrefslogtreecommitdiffstats
path: root/realloc.c
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2001-10-20 02:12:22 +0000
committerH. Peter Anvin <hpa@zytor.com>2001-10-20 02:12:22 +0000
commit50cedb0ff19233273ef33cb5b5e8725025a35024 (patch)
tree25b21afff2ef45d706df0b05f18473516b8911f5 /realloc.c
parentf3d637296f1f839d4a95a849a7dbfbb600f563f1 (diff)
downloadlpsm-50cedb0ff19233273ef33cb5b5e8725025a35024.tar.gz
lpsm-50cedb0ff19233273ef33cb5b5e8725025a35024.tar.xz
lpsm-50cedb0ff19233273ef33cb5b5e8725025a35024.zip
Split apart into modules. Create lpsm_zalloc()/lpsm_calloc().
Diffstat (limited to 'realloc.c')
-rw-r--r--realloc.c216
1 files changed, 216 insertions, 0 deletions
diff --git a/realloc.c b/realloc.c
new file mode 100644
index 0000000..3dce36e
--- /dev/null
+++ b/realloc.c
@@ -0,0 +1,216 @@
+#ident "$Id$"
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2000-2001 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA, version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * realloc.c
+ *
+ * Provice persistent storate version of realloc().
+ *
+ */
+
+#include <assert.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <string.h>
+
+#include "lpsm.h"
+#include "internals.h"
+#include "bitops.h"
+
+static void *lpsm_realloc_buddy(void *ptr, size_t new_size)
+{
+ struct buddy_params bp;
+ int order, rorder;
+ int xbit, obit, i;
+ void *nptr;
+
+ bp = lpsm_find_alloc_buddy(ptr);
+
+ order = BUDDY_ORDER_MIN;
+ while ( new_size > ((size_t)1 << order) )
+ order++;
+
+ if ( order > AH->arena_size_lg2 ) {
+ /* Need to extend the arena immediately... */
+ if ( lpsm_extend_arena(order+1) )
+ return NULL;
+ }
+
+ rorder = AH->arena_size_lg2 - order;
+
+ DPRINTF(("buddy: realloc rorder %d %d -> rorder %d\n",
+ bp.rorder, bp.xbit, rorder));
+
+ 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. */
+
+ /*** FIXME: this could be bad for fragmentation if the
+ *** allocation size delta is large. Consider adding a
+ *** heuristic copy to a less prime spot if delta is large. */
+
+ /* 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);
+ DPRINTF(("buddy: freing rorder %2d %8d\n", i, 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. */
+
+ size_t current_size = (size_t)1 << (AH->arena_size_lg2-bp.rorder);
+
+ 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... */
+ DPRINTF(("buddy: unable to reallocate in place, rorder %2d %8d in use\n", i, xbit^1));
+
+ /* Careful. If lpsm_malloc_buddy resizes the arena we need to
+ adjust the rorder and xbit values afterwards. */
+ nptr = lpsm_malloc_buddy(new_size);
+ if ( !nptr )
+ return NULL; /* realloc failed */
+
+ memcpy(nptr, ptr, current_size);
+
+ /* Free the old area */
+ /* Consider later if we can optimize this given the resizing issue */
+ lpsm_free_buddy(ptr);
+
+ return nptr;
+ }
+ xbit >>= 1;
+ }
+
+ DPRINTF(("buddy: reallocating in place...\n"));
+
+ /* Oh cool, we can expand in place */
+ 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;
+ DPRINTF(("allocated rorder %2d %8d\n", i, xbit^1));
+ }
+
+ /* Add new allocation bit */
+ set_bit(AH->alloc_bitmap, xbit);
+
+ /* Expansion in place is good, but we may still have to copy,
+ since we might have been "high buddy" in one or more of the
+ pairs we just claimed. */
+
+ obit = 1 << rorder;
+ nptr = (void *)((char *)AH->data_start +
+ ((uintptr_t)(xbit-obit) << order));
+
+ if ( nptr != ptr ) {
+ DPRINTF(("buddy: copying base from %p to %p\n", ptr, nptr));
+ memcpy(nptr, ptr, current_size);
+ }
+
+ return nptr;
+ }
+}
+
+static void *lpsm_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];
+
+ DPRINTF(("slab: realloc %p size %d new_size %d\n",
+ ptr, si->size, new_size));
+
+ /* 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 ) {
+ /* This also covers the possibility of new_size > slab_max */
+ void *nptr = lpsm_malloc(new_size);
+ if ( !nptr )
+ return NULL;
+ memcpy(nptr, ptr, si->size);
+ lpsm_free_slab(ptr);
+ return nptr;
+ } else if ( new_size < (si->size >> 2) ) {
+ void *nptr = lpsm_malloc_slab(new_size);
+ if ( !nptr )
+ return ptr; /* Old allocation still OK */
+ memcpy(nptr, ptr, new_size);
+ lpsm_free_slab(ptr);
+ return nptr;
+ } else {
+ /* Nothing to do... */
+ return ptr;
+ }
+}
+
+void *lpsm_realloc(void *ptr, size_t new_size)
+{
+ int is_slab = ((uintptr_t)ptr & (BUDDY_SIZE_MIN-1)) != 0;
+ int slab_max = AH->slab[0].size;
+
+ /* Special cases for "realloc everything" style programming */
+ if ( !ptr )
+ return lpsm_malloc(new_size);
+ else if ( new_size == 0 ) {
+ lpsm_free(ptr);
+ return NULL;
+ }
+
+ DPRINTF(("realloc: ptr = %p, new_size = %d, is_slab = %d\n",
+ ptr, new_size, is_slab));
+
+ if ( is_slab ) {
+ /* lpsm_realloc_slab() also handles the slab->buddy case */
+ return lpsm_realloc_slab(ptr, new_size);
+ } else {
+ /* Currently buddy. */
+ if ( new_size > slab_max ) {
+ return lpsm_realloc_buddy(ptr, new_size);
+ } else {
+ /* Buddy shrunk to slab size */
+ void *nptr = lpsm_malloc_slab(new_size);
+ if ( !nptr )
+ return ptr; /* Old allocation still OK */
+ memcpy(nptr, ptr, new_size);
+ lpsm_free_buddy(ptr);
+ return nptr;
+ }
+ }
+}