Implement realloc(). Not tested yet.

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;
+  }
+}
+