aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2001-10-15 18:32:39 +0000
committerH. Peter Anvin <hpa@zytor.com>2001-10-15 18:32:39 +0000
commit2c0186aa66ef9d7beb30b033fa49b7f5c05e306f (patch)
tree1f8e6ff00843b00756a3b5b73829a256bbb0f1c8
parent17f1f38e6120119bdbcc4c2b2100671a2826939b (diff)
downloadlpsm-2c0186aa66ef9d7beb30b033fa49b7f5c05e306f.tar.gz
lpsm-2c0186aa66ef9d7beb30b033fa49b7f5c05e306f.tar.xz
lpsm-2c0186aa66ef9d7beb30b033fa49b7f5c05e306f.zip
Now realloc() mostly works... checkpoint the work here.
-rw-r--r--Makefile2
-rw-r--r--alloc.c128
-rw-r--r--testalloc.c45
3 files changed, 122 insertions, 53 deletions
diff --git a/Makefile b/Makefile
index 35dcc87..00a798d 100644
--- a/Makefile
+++ b/Makefile
@@ -7,7 +7,7 @@ OSOBJ = objstore.o alloc.o
OSPICOBJ = $(patsubst %.o,%.pic.o,$(OSOBJ))
CC = gcc
-CFLAGS = -Wall -O2 -g
+CFLAGS = -Wall -O2 -g -D_FILE_OFFSET_BITS=64
PICFLAGS = $(CFLAGS) -fPIC
SOFLAGS = -shared
diff --git a/alloc.c b/alloc.c
index cc721a8..db08c43 100644
--- a/alloc.c
+++ b/alloc.c
@@ -84,6 +84,7 @@ struct arena_header {
void *data_start; /* Beginning of data area */
int buddy_order_min; /* Minimum size of buddy allocation */
int arena_size_lg2; /* Current arena allocation size */
+ int header_size; /* Size of this header+padding */
struct slab_info slab[SLAB_INFO_COUNT];
};
@@ -101,8 +102,6 @@ struct arena_header {
#define ARENA_START_SIZE_LG2 17 /* 128K */
#define ARENA_START_SIZE (1UL << ARENA_START_SIZE_LG2)
-#define HEADER_SIZE BUDDY_SIZE_MIN /* Default size of the header */
-
/* The data type to use for bitfield scanning. Typically should equal
the "natural" size on the machine, which used to always be "int".
Unfortunately, that's no longer true... and getting all of these,
@@ -246,7 +245,7 @@ void *objstore_arena_init(void)
if ( memcmp(ah->arena_magic, objstore_arena_magic, 16) != 0 ) {
if ( memcmp(ah->arena_magic, objstore_arena_zero, 16) == 0 ) {
size_t total_size, bitmap_size;
- int i;
+ int i, header_pad;
/* Uninitialized arena */
memcpy(ah->arena_magic, objstore_arena_magic, 16);
@@ -254,13 +253,21 @@ void *objstore_arena_init(void)
ah->arena_bytesize = CHAR_BIT;
ah->arena_ptrsize = sizeof(void *);
ah->arena_base = (void *)ah;
- ah->data_start = (char *)ah + HEADER_SIZE;
ah->buddy_order_min = BUDDY_ORDER_MIN;
+ /* Header size must be padded to a multiple of BUDDY_SIZE_MIN
+ as well as the hardware page size; this better be a power of 2! */
+ header_pad = (os->pagesize > BUDDY_SIZE_MIN)
+ ? os->pagesize : BUDDY_SIZE_MIN;
+ assert((header_pad & (header_pad-1)) == 0);
+ ah->header_size = (sizeof(struct arena_header) + header_pad - 1)
+ & ~(header_pad-1);
+
+ ah->data_start = (char *)ah + ah->header_size;
ah->arena_size_lg2 = ARENA_START_SIZE_LG2;
bitmap_size = 1UL << (ARENA_START_SIZE_LG2-BUDDY_ORDER_MIN-1);
- total_size = HEADER_SIZE + ARENA_START_SIZE + (bitmap_size << 1);
- ah->free_bitmap = (char *)ah + HEADER_SIZE + ARENA_START_SIZE;
+ total_size = ah->header_size + ARENA_START_SIZE + (bitmap_size << 1);
+ ah->free_bitmap = (char *)ah->data_start + ARENA_START_SIZE;
ah->alloc_bitmap = (char *)ah->free_bitmap + bitmap_size;
if ( objstore_extend(total_size) < 0 )
@@ -359,8 +366,8 @@ static int objstore_extend_arena(int logsize)
DPRINTF(("arena: extending arena to order %d: ", logsize));
bitmap_size = 1 << (logsize-BUDDY_ORDER_MIN-1);
- total_size = HEADER_SIZE + new_arena_size + (bitmap_size << 1);
- newfreemap = (char *)ah + HEADER_SIZE + new_arena_size;
+ total_size = ah->header_size + new_arena_size + (bitmap_size << 1);
+ newfreemap = (char *)ah->data_start + new_arena_size;
newallocmap = (char *)newfreemap + bitmap_size;
if ( objstore_extend(total_size) < 0 ) {
@@ -700,23 +707,32 @@ void objstore_free(void *ptr)
static void *objstore_realloc_buddy(void *ptr, size_t new_size)
{
struct buddy_params bp;
- int order, rorder, dorder;
- int xbit, nxbit, i;
-
+ int order, rorder;
+ int xbit, obit, i;
+ void *nptr;
+
bp = objstore_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... */
+ if ( objstore_extend_arena(order+1) )
+ return NULL;
+ }
+
rorder = ah->arena_size_lg2 - order;
+ DPRINTF(("buddy: realloc rorder %d -> rorder %d\n",
+ bp.rorder, 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. */
- dorder = rorder - bp.rorder;
- nxbit = bp.xbit << dorder;
/* Clear the old allocation size bit. */
xbit = bp.xbit;
@@ -726,6 +742,7 @@ static void *objstore_realloc_buddy(void *ptr, size_t new_size)
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 */
@@ -738,28 +755,32 @@ static void *objstore_realloc_buddy(void *ptr, size_t new_size)
memory areas we need in order to avoid copying, otherwise
get new allocation and copy. */
- dorder = bp.rorder - rorder;
- nxbit = bp.xbit >> dorder;
+ size_t current_size = (size_t)1 << 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... */
- void *nptr = objstore_malloc_buddy(new_size);
+ DPRINTF(("buddy: unable to reallocate in place, rorder %2d %8d in use\n", i, xbit^1));
+ nptr = objstore_malloc_buddy(new_size);
if ( !nptr )
return NULL; /* realloc failed */
- memcpy(nptr, ptr, (size_t)1 << (ah->arena_size_lg2-bp.rorder));
+ memcpy(nptr, ptr, current_size);
/* Free the old area */
+ 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);
+
return nptr;
}
xbit >>= 1;
}
- /* Oh cool, we actually have the memory */
+ DPRINTF(("buddy: reallocating in place...\n"));
+
+ /* Oh cool, we can expand in place */
xbit = bp.xbit;
/* Remove old allocation bit */
@@ -769,13 +790,26 @@ static void *objstore_realloc_buddy(void *ptr, size_t new_size)
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);
- /* We didn't have to move... */
- return ptr;
+ /* 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;
}
}
@@ -790,10 +824,14 @@ static void *objstore_realloc_slab(void *ptr, size_t new_size)
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 ) {
- void *nptr = objstore_malloc_slab(new_size);
+ /* This also covers the possibility of new_size > slab_max */
+ void *nptr = objstore_malloc(new_size);
if ( !nptr )
return NULL;
memcpy(nptr, ptr, si->size);
@@ -814,31 +852,35 @@ static void *objstore_realloc_slab(void *ptr, size_t new_size)
void *objstore_realloc(void *ptr, size_t new_size)
{
- int is_slab = (uintptr_t)ptr & (BUDDY_SIZE_MIN-1);
+ int is_slab = ((uintptr_t)ptr & (BUDDY_SIZE_MIN-1)) != 0;
int slab_max = ah->slab[0].size;
- if ( is_slab && new_size <= slab_max )
+ /* Special cases for "realloc everything" style programming */
+ if ( new_size == 0 ) {
+ objstore_free(ptr);
+ return NULL;
+ } else if ( !ptr ) {
+ return objstore_malloc(new_size);
+ }
+
+ DPRINTF(("realloc: ptr = %p, new_size = %d, is_slab = %d\n",
+ ptr, new_size, is_slab));
+
+ if ( is_slab ) {
+ /* objstore_realloc_slab() also handles the slab->buddy case */
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;
+ /* Currently buddy. */
+ if ( new_size > slab_max ) {
+ return objstore_realloc_buddy(ptr, new_size);
+ } else {
+ /* Buddy shrunk to slab size */
+ 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;
+ }
}
}
-
diff --git a/testalloc.c b/testalloc.c
index 1fcd29d..05e2956 100644
--- a/testalloc.c
+++ b/testalloc.c
@@ -19,8 +19,8 @@
#include <limits.h>
#include "objstore.h"
-#define COUNT 8192
-#define SLOTS 256
+#define COUNT 32768
+#define SLOTS 1024
#define MAXLOG 26
int main(int argc, char *argv[])
@@ -28,9 +28,11 @@ int main(int argc, char *argv[])
void *areas[COUNT];
int sizes[COUNT];
void *buf;
- int arena_len = 16384;
- int i, slot;
+ int i, slot, newsize;
double rnd;
+ void *nptr;
+ size_t arena_len = 4096;
+ unsigned long occupied = 0;
unlink("arena.dat");
unlink("arena.log");
@@ -50,17 +52,42 @@ int main(int argc, char *argv[])
slot = rand() % SLOTS;
if ( areas[slot] ) {
- printf("Free: %8d (0x%08x) bytes at %p\n",
- sizes[slot], sizes[slot], areas[slot]);
- objstore_free(areas[slot]);
- areas[slot] = NULL;
+ if ( rand() % 1 ) {
+ printf("Free: %d (0x%08x) bytes at %p\n",
+ sizes[slot], sizes[slot], areas[slot]);
+ objstore_free(areas[slot]);
+ areas[slot] = NULL;
+ occupied -= sizes[slot];
+ } else {
+ rnd = (double)rand()/RAND_MAX;
+ newsize = (int)pow(2.0, MAXLOG*pow(rnd,3.0));
+ nptr = objstore_realloc(areas[slot], newsize);
+ if ( nptr ) {
+ printf("Realloc: %d bytes at %p -> %d bytes at %p\n",
+ sizes[slot], areas[slot], newsize, nptr);
+ occupied += newsize;
+ occupied -= sizes[slot];
+ sizes[slot] = newsize;
+ areas[slot] = nptr;
+ } else {
+ printf("Realloc: %d bytes at %p -> %d bytes FAILED\n",
+ sizes[slot], areas[slot], newsize);
+ }
+ }
} else {
rnd = (double)rand()/RAND_MAX;
sizes[slot] = (int)pow(2.0, MAXLOG*pow(rnd,5.0));
areas[slot] = objstore_malloc(sizes[slot]);
- printf("Alloc: %8d (0x%08x) bytes at %p\n",
+ printf("Alloc: %d (0x%08x) bytes at %p\n",
sizes[slot], sizes[slot], areas[slot]);
+ occupied += sizes[slot];
+ }
+
+ if ( (i & 255) == 0 ) {
+ printf("Arena: checkpointing...\n");
+ objstore_checkpoint(0.1);
}
+ printf("Arena: %ld bytes officially occupied\n", occupied);
}
objstore_checkpoint(0.0);