Split apart into modules. Create lpsm_zalloc()/lpsm_calloc().

10 files changed, 795 insertions, 712 deletions

diff --git a/Makefile b/Makefile
index 5eb17f8..f67108f 100644
--- a/Makefile
+++ b/Makefile
@@ -1,17 +1,18 @@
 TEST     = teststore test_mmap ftrunctest testbuddy testalloc testrecovery
 SONAME   = libpsm.so.0
-VERSION  = 0.1.1
+VERSION  = 0.1.2
 LIBPSM	 = libpsm.so libpsm.a
 
-OSOBJ	 = arena.o alloc.o
+OSOBJ	 = arena.o bitops.o alloc.o realloc.o zalloc.o stats.o
 OSPICOBJ = $(patsubst %.o,%.pic.o,$(OSOBJ))
 
 CC	 = gcc
 # This is a reasonable set of flags for production
-CFLAGS	= -I. -Wall -O3 -fomit-frame-pointer -DNDEBUG -D_FILE_OFFSET_BITS=64
+# Add -NDEBUG if you don't want to retain assert()s
+CFLAGS	= -I. -Wall -O3 -fomit-frame-pointer -D_FILE_OFFSET_BITS=64 # -DNDEBUG
 LDFLAGS	= 
 # This is for debugging
-# CFLAGS	 = -I. -Wall -O -g -D_FILE_OFFSET_BITS=64
+# CFLAGS	 = -I. -Wall -O -g -DPRINT_DEBUG_INFO -D_FILE_OFFSET_BITS=64
 # LDFLAGS  = -g
 LIBS    = libpsm.a -lm
 PICFLAGS = $(CFLAGS) -fPIC
diff --git a/README b/README
index e9839e3..20e3204 100644
--- a/README
+++ b/README
@@ -159,6 +159,17 @@ void *lpsm_realloc(void *ptr, size_t new_size)
 	   lpsm_free(ptr);
 	   return NULL;
 
+void *lpsm_zalloc(size_t size)
+void *lpsm_calloc(size_t nmemb, size_t size)
+
+	Same as lpsm_malloc(), but returns memory that is initialized
+	to zero.  The implementation attempts to be smart, and for
+	large blocks can be significantly more efficient than
+	lpsm_malloc() followed by memset().
+
+	lpsm_calloc() is implemented as an inline or macro which
+	returns lpsm_zalloc(nmemb*size).
+
 
 struct lpsm_alloc_stats {
   size_t size;
diff --git a/alloc.c b/alloc.c
index 2377e1f..8a80e2e 100644
--- a/alloc.c
+++ b/alloc.c
@@ -14,7 +14,7 @@
 /*
  * alloc.c
  *
- * Provide persistent storage versions of malloc(), realloc() and free().
+ * Provide persistent storage management (basic infrastructure.)
  *
  * This code uses a modified buddy system allocator for large allocations
  * and a SLAB allocator for small allocations.
@@ -30,43 +30,17 @@
 #include <limits.h>
 #include <string.h>
 
-#ifndef NDEBUG
-#include <stdio.h>		/* For debugging printf() */
-#define DPRINTF(X) printf X
-#else
-#define DPRINTF(X)
-#endif
-
 #include "lpsm.h"
 #include "internals.h"
+#include "bitops.h"
+
+struct arena_header *lpsm_arena_header;
 
 static const unsigned char lpsm_arena_magic[16] =
 "\x4f\xd4\x5a\x16\xa0\xaf\xd5\x52\x56\xf1\x1c\x9c\x1c\xed\xcc";
 static const unsigned char lpsm_arena_zero[16] =
 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
 
-#define SLAB_MAGIC		0xec2062ae
-
-struct slab_info {
-  int size;			/* Size of SLAB */
-  int count;			/* SLABs per page */
-  int data_offset;		/* Start of data area */
-  int total_pages;		/* Count of pages allocaed to this size SLAB */
-  int alloc_slabs;		/* Count of SLABs currently in use */
-  struct slab_header *list;
-};
-
-/* This is 16 bytes on 32-bit and 24 bytes on 64-bit architectures */
-/* This header must end aligned to a bitscan_t datum */
-struct slab_header {
-  uint32_t magic;
-  uint16_t free_count;
-  uint16_t index;		/* Index into slab_info array */
-  struct slab_header *next, **rev;
-};
-
-#define SLAB_INFO_COUNT	32
-
 /* Change these if BUDDY_ORDER_MIN or MINIMUM_ALIGN is changed */
 /* These MUST be ordered in order of decreasing size.  0 is end of list. */
 /* This particular set of slab sizes should work well for both a
@@ -76,283 +50,6 @@ static int slabsizes[] =
   2032, 1344, 1016, 800, 576, 448, 256, 192, 128, 96, 64, 48, 32, 16, 8, 4, 2, 1, 0
 };
 
-struct arena_header {
-  unsigned char arena_magic[16];
-  uint32_t arena_byteorder;
-  uint16_t arena_bytesize;
-  uint16_t arena_ptrsize;
-  void *arena_base;		/* Base of allocation */
-  void *free_bitmap;		/* The free bitmap */
-  void *alloc_bitmap;		/* The allocated (buddy) bitmap */
-  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];
-  void *root_data_ptrs[LPSM_ROOT_POINTERS]; /* Root data pointers - for the user */
-};
-
-/* This is the minimal order before going to SLAB allocation. */
-#define BUDDY_ORDER_MIN		12
-#define BUDDY_SIZE_MIN		(1U << BUDDY_ORDER_MIN)
-
-/* Align allocations at least this large (2^n) to this boundary */
-#define MINIMUM_ALIGN_LG2	4
-#define MINIMUM_ALIGN		(1 << MINIMUM_ALIGN_LG2)
-#define MINIMUM_ALIGN_MASK	(MINIMUM_ALIGN-1)
-
-/* This is the size (2^n) allocated for a brand new arena.
-   This allocation will be sparse, so don't freak out too much! */
-#define ARENA_START_SIZE_LG2	17 /* 128K */
-#define ARENA_START_SIZE	(1UL << ARENA_START_SIZE_LG2)
-
-/* The data type to use for bitfield scanning.  Typically should equal
-   the "natural" size on the machine; defined in system.h. */
-#if MACHINE_SIZE_LG2 == 6
-  typedef uint64_t bitscan_t;
-#else
-  typedef uint32_t bitscan_t;
-#endif
-#define BITSCAN_SHIFT		MACHINE_SIZE_LG2
-#define BITSCAN_BITS		(1 << BITSCAN_SHIFT)
-#define BITSCAN_MASK		(BITSCAN_BITS-1)
-#define BITSCAN_0		((bitscan_t)0)
-#define BITSCAN_1		((bitscan_t)1)
-
-/*
- * These should be revamped to be thread-safe at some point.  That
- * may mean doing things that are architecture-specific...
- *
- * Important: "bit" can be negative, and that needs to be handled
- * correctly!
- */
-static inline int test_bit(const void *ptr, int bit)
-{
-#if defined(__GNUC__) && defined(__i386__)
-  int rv;
-  asm("xorl %0,%0 ; btl %2,%1 ; adcl %0,%0"
-      : "=&r" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
-  return rv;
-#else
-  const bitscan_t *cp;
-
-  cp = (const bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
-  return (int)((*cp >> (bit & BITSCAN_MASK)) & BITSCAN_1);
-#endif
-}
-
-static inline void set_bit(void *ptr, int bit)
-{
-#if defined(__GNUC__) && defined(__i386__)
-  asm volatile("btsl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
-#else
-  bitscan_t *cp;
-
-  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
-  *cp |= (BITSCAN_1 << (bit & BITSCAN_MASK));
-#endif
-}
-
-static inline void clr_bit(void *ptr, int bit)
-{
-#if defined(__GNUC__) && defined(__i386__)
-  asm volatile("btcl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
-#else
-  bitscan_t *cp;
-
-  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
-  *cp &= ~(BITSCAN_1 << (bit & BITSCAN_MASK));
-#endif
-}
-
-/* Finds a one bit somewhere between [start, start+count) bit indicies.
-   Returns the index, or "err" if no such bit is found. */
-static int find_set_bit(const void *ptr, int start, int count, int err)
-{
-  const bitscan_t *cp, *ecp;
-  bitscan_t mask, val;
-  int i, end;
-
-  end = start+count-1;
-
-  cp = (bitscan_t *)ptr + (start >> BITSCAN_SHIFT);
-
-  if ( ((start^end) & ~BITSCAN_MASK) == 0 ) {
-    /* All falls within a single bitscan_t quantum */
-    mask = BITSCAN_1 << (start & BITSCAN_MASK);
-    val = *cp;
-    for ( i = start ; i <= end ; i++ ) {
-      if ( val & mask )
-	return i;
-      mask <<= 1;
-    }
-    return err;
-  }
-  
-  mask = ~BITSCAN_0 << (start & BITSCAN_MASK);
-  val = *cp++;
-  if ( val & mask ) {
-    end = start | BITSCAN_MASK;
-    mask = BITSCAN_1 << (start & BITSCAN_MASK);
-    for ( i = start ; i <= end ; i++ ) {
-      if ( val & mask )
-	return i;
-      mask <<= 1;
-    }
-    assert(0);			/* Internal error */
-  }
-
-  ecp = (bitscan_t *)ptr + (end >> BITSCAN_SHIFT);
-  start = (start & ~BITSCAN_MASK) + BITSCAN_BITS;
-
-  while ( cp < ecp ) {
-    val = *cp++;
-    if ( val ) {
-      mask = BITSCAN_1;
-      end = start | BITSCAN_MASK;
-      for ( i = start ; i <= end ; i++ ) {
-	if ( val & mask )
-	  return i;
-	mask <<= 1;
-      }
-      assert(0);		/* Internal error */
-    }
-    start += BITSCAN_BITS;
-  }
-
-  /* Scan final word */
-  val = *cp;
-  mask = BITSCAN_1;
-  for ( i = start ; i <= end ; i++ ) {
-    if ( val & mask )
-      return i;
-    mask <<= 1;
-  }
-  return err;			/* Nothing found */
-}
-
-static struct ObjStore *os;
-static struct arena_header *ah;
-
-#ifndef NDEBUG
-/*
- * Debugging routine to print the number of allocations of each size
- */
-void print_statistics(void)
-{
-  int i, o, obit, ebit, xbit;
-  int fcount, acount, total_slabs;
-  unsigned long bt = 0, bf = 0, ba = 0;
-  struct slab_info *si;
-
-  /* Print buddy system stats */
-
-  for ( i = 0, o = ah->arena_size_lg2 ;
-	o >= BUDDY_ORDER_MIN ;
-	i++, o-- ) {
-    obit = 1 << i;
-    ebit = obit << 1;
-    fcount = acount = 0;
-    for ( xbit = obit ; xbit < ebit ; xbit++ ) {
-      if ( test_bit(ah->free_bitmap, xbit) )
-	fcount++;
-    }
-    for ( xbit = obit ; xbit < ebit ; xbit++ ) {
-      if ( test_bit(ah->alloc_bitmap, xbit) )
-	acount++;
-    }
-
-    DPRINTF(("    rorder %2d order %2d free %8d used %8d\n",
-	     i, ah->arena_size_lg2-i, fcount, acount));
-
-    bt += (fcount+acount) * (1UL << o);
-    bf += fcount * (1UL << o);
-    ba += acount * (1UL << o);
-  }
-  DPRINTF(("    buddy: %lu bytes free, %lu bytes allocated, %lu total\n",
-	   bf, ba, bt));
-
-  bt = bf = ba = 0;
-
-  for ( si = &ah->slab[0], i = 0 ;
-	i < SLAB_INFO_COUNT ;
-	i++, si++ ) {
-    if ( !si->size )
-      break;
-    total_slabs = si->total_pages * si->count;
-    DPRINTF(("    slab size %4d free %8d used %8d\n",
-	     si->size, total_slabs-si->alloc_slabs, si->alloc_slabs));
-    bt += total_slabs * si->size;
-    bf += (total_slabs-si->alloc_slabs) * si->size;
-    ba += si->alloc_slabs * si->size;
-  }
-  DPRINTF(("    slab:  %lu bytes free, %lu bytes allocated, %lu total\n",
-	   bf, ba, bt));
-}
-#else
-#define print_statistics()	((void)0)
-#endif
-
-/*
- * Get allocation statistics.  This returned a malloc()'d list of
- * {block size, free blocks, allocated blocks} followed by an
- * all-zero datum.
- */
-struct lpsm_alloc_stats *lpsm_alloc_stats(void)
-{
-  struct lpsm_alloc_stats *as, *asp;
-  struct slab_info *si;
-  int nb, ns;
-  int i, o;
-  int xbit, obit, ebit;
-  size_t fcount, acount, *last_buddy_alloc;
-
-  /* Compute number of buddy and slab allocation types */
-  nb = ah->arena_size_lg2-BUDDY_ORDER_MIN+1;
-  for ( ns = 0 ; ns < SLAB_INFO_COUNT ; ns++ )
-    if ( !ah->slab[ns].size )
-      break;
-
-  as = malloc((nb+ns+1) * sizeof(struct lpsm_alloc_stats));
-  if ( !as )
-    return NULL;
-
-  for ( asp = as, i = 0, o = ah->arena_size_lg2 ;
-	o >= BUDDY_ORDER_MIN ;
-	asp++, i++, o-- ) {
-    asp->size = (size_t)1 << o;
-    obit = 1 << i;
-    ebit = obit << 1;
-    fcount = acount = 0;
-    for ( xbit = obit ; xbit < ebit ; xbit++ ) {
-      if ( test_bit(ah->free_bitmap, xbit) )
-	fcount++;
-    }
-    asp->free = fcount;
-    for ( xbit = obit ; xbit < ebit ; xbit++ ) {
-      if ( test_bit(ah->alloc_bitmap, xbit) )
-	acount++;
-    }
-    asp->alloc = acount;
-  }
-
-  /* The alloc counter for the last buddy size include all the slab blocks.
-     We want to count them separately. */
-  last_buddy_alloc = &asp[-1].alloc;
-
-  for ( i = 0, si = &ah->slab[0] ;
-	i < SLAB_INFO_COUNT && si->size ;
-	i++, si++, asp++ ) {
-    last_buddy_alloc -= si->total_pages;
-    asp->size  = si->size;
-    asp->alloc = si->alloc_slabs;
-    asp->free  = (si->total_pages * si->count) - si->alloc_slabs;
-  }
-  /* Sentinel block at end */
-  asp->size = asp->alloc = asp->free = 0;
-  return as;
-}
-
 /*
  * Initalize the object store arena allocator.  This returns NULL
  * on failure, or a pointer to the "root data pointer" array if
@@ -365,38 +62,37 @@ void **lpsm_init(const char *main_file, const char *log_file)
   if ( !lpsm_arena_init(main_file, log_file, &arena_len) )
     return NULL;		/* Failed to initialize arena */
 
-  os = lpsm_os_struct;
-  ah = (struct arena_header *)os->arena;
+  AH = (struct arena_header *)PM->arena;
 
-  if ( memcmp(ah->arena_magic, lpsm_arena_magic, 16) != 0 ) {
-    if ( memcmp(ah->arena_magic, lpsm_arena_zero, 16) == 0 ) {
+  if ( memcmp(AH->arena_magic, lpsm_arena_magic, 16) != 0 ) {
+    if ( memcmp(AH->arena_magic, lpsm_arena_zero, 16) == 0 ) {
       size_t total_size, bitmap_size;
       int i, header_pad;
 
-      memset(ah, 0, sizeof(*ah)); /* Just in case */
+      memset(AH, 0, sizeof(*AH)); /* Just in case */
 
       /* Uninitialized arena */
-      memcpy(ah->arena_magic, lpsm_arena_magic, 16);
-      ah->arena_byteorder = 0x12345678;
-      ah->arena_bytesize  = CHAR_BIT;
-      ah->arena_ptrsize   = sizeof(void *);
-      ah->arena_base      = (void *)ah;
-      ah->buddy_order_min = BUDDY_ORDER_MIN;
+      memcpy(AH->arena_magic, lpsm_arena_magic, 16);
+      AH->arena_byteorder = 0x12345678;
+      AH->arena_bytesize  = CHAR_BIT;
+      AH->arena_ptrsize   = sizeof(void *);
+      AH->arena_base      = (void *)AH;
+      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;
+      header_pad = (PM->pagesize > BUDDY_SIZE_MIN)
+	? PM->pagesize : BUDDY_SIZE_MIN;
       assert((header_pad & (header_pad-1)) == 0);
-      ah->header_size = (sizeof(struct arena_header) + header_pad - 1)
+      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;
+      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 = 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;
+      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 ( lpsm_extend(total_size) < 0 )
 	return NULL;		/* Failed to establish initial arena */
@@ -418,26 +114,26 @@ void **lpsm_init(const char *main_file, const char *log_file)
 
 	  count--;
 	}
-	ah->slab[i].size = size;
-	ah->slab[i].count = count;
-	ah->slab[i].data_offset = data_offset;
+	AH->slab[i].size = size;
+	AH->slab[i].count = count;
+	AH->slab[i].data_offset = data_offset;
       }
 
       /* The bitmasks contains zeroes already; set the free bit on the topmost order. */
-      set_bit(ah->free_bitmap, 1);
+      set_bit(AH->free_bitmap, 1);
     }
   }
 
-  if ( memcmp(ah->arena_magic, lpsm_arena_magic, 16) != 0 ||
-       ah->arena_byteorder != 0x12345678 ||
-       ah->arena_bytesize  != CHAR_BIT   ||
-       ah->arena_ptrsize   != sizeof(void *) ||
-       ah->arena_base      != (void *)ah ||
-       ah->buddy_order_min != BUDDY_ORDER_MIN ) {
+  if ( memcmp(AH->arena_magic, lpsm_arena_magic, 16) != 0 ||
+       AH->arena_byteorder != 0x12345678 ||
+       AH->arena_bytesize  != CHAR_BIT   ||
+       AH->arena_ptrsize   != sizeof(void *) ||
+       AH->arena_base      != (void *)AH ||
+       AH->buddy_order_min != BUDDY_ORDER_MIN ) {
     return NULL;		/* Incompatible or corrupt arena */
   }
 
-  return ah->root_data_ptrs;
+  return AH->root_data_ptrs;
 }
 
 /*
@@ -480,11 +176,11 @@ static void lpsm_expand_bitmap(void *nbitmap, const void *obitmap, int norder, i
 /*
  * This function expands the arena to the specified log size.
  */
-static int lpsm_extend_arena(int logsize)
+int lpsm_extend_arena(int logsize)
 {
   size_t new_arena_size = (size_t)1 << logsize;
   size_t total_size;
-  int ologsize = ah->arena_size_lg2;
+  int ologsize = AH->arena_size_lg2;
   int bitmap_size;
   void *newfreemap, *newallocmap;
   int obp;
@@ -494,8 +190,8 @@ static int lpsm_extend_arena(int logsize)
   DPRINTF(("arena: extending arena to order %d: ", logsize));
 
   bitmap_size =  1 << (logsize-BUDDY_ORDER_MIN-1);
-  total_size = ah->header_size + new_arena_size + (bitmap_size << 1);
-  newfreemap  = (char *)ah->data_start + 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 ( lpsm_extend(total_size) < 0 ) {
@@ -504,13 +200,13 @@ static int lpsm_extend_arena(int logsize)
   }
 
   /* Otherwise, we just extended the area; reconstruct the bitmaps */
-  lpsm_expand_bitmap(newfreemap, ah->free_bitmap,
+  lpsm_expand_bitmap(newfreemap, AH->free_bitmap,
 			 logsize-BUDDY_ORDER_MIN+1, ologsize-BUDDY_ORDER_MIN+1);
-  lpsm_expand_bitmap(newallocmap, ah->alloc_bitmap,
+  lpsm_expand_bitmap(newallocmap, AH->alloc_bitmap,
 			 logsize-BUDDY_ORDER_MIN+1, ologsize-BUDDY_ORDER_MIN+1);
-  ah->free_bitmap    = newfreemap;
-  ah->alloc_bitmap   = newallocmap;
-  ah->arena_size_lg2 = logsize;
+  AH->free_bitmap    = newfreemap;
+  AH->alloc_bitmap   = newallocmap;
+  AH->arena_size_lg2 = logsize;
 
   /* Mark the new allocations available */
   obp = 1 << (logsize-ologsize);
@@ -542,7 +238,7 @@ static int lpsm_find_free_chunk(int rorder)
   int obit, xbit;
 
   obit = 1 << rorder;
-  xbit = find_set_bit(ah->free_bitmap, obit, obit, 0);
+  xbit = lpsm_find_set_bit(AH->free_bitmap, obit, obit, 0);
 
   if ( !xbit ) {
     if ( rorder == 0 )
@@ -552,34 +248,28 @@ static int lpsm_find_free_chunk(int rorder)
       return 0;			/* All out of those, sir */
     DPRINTF(("buddy: splitting rorder %2d %8d -> %d %d\n", rorder-1, xbit, xbit << 1, (xbit << 1)+1));
     xbit <<= 1;			/* Convert to address of fragments */
-    set_bit(ah->free_bitmap, xbit+1); /* Upper buddy is available */
+    set_bit(AH->free_bitmap, xbit+1); /* Upper buddy is available */
     /* Return the lower buddy */
   } else {
-    clr_bit(ah->free_bitmap, xbit); /* No longer available */
+    clr_bit(AH->free_bitmap, xbit); /* No longer available */
   }
   DPRINTF(("buddy: allocated rorder %2d %8d\n", rorder, xbit));
   return xbit;
 }
 
-static void *lpsm_malloc_buddy(size_t size)
+int lpsm_malloc_buddy_xbit(int order)
 {
-  int order = BUDDY_ORDER_MIN;
   int rorder;
   int xbit, obit;
-  void *p;
 
-  while ( size > ((size_t)1 << order) )
-    order++;
-
-  /* Now we know the order */
-  if ( order > ah->arena_size_lg2 ) {
+  if ( order > AH->arena_size_lg2 ) {
     if ( lpsm_extend_arena(order+1) )
-      return NULL;		/* Unable to extend arena */
+      return 0;			/* Unable to extend arena */
   }
 
   /* Convert to order relative to the arena size order */
   do {
-    rorder = ah->arena_size_lg2 - order;
+    rorder = AH->arena_size_lg2 - order;
     obit = 1 << rorder;
 
     DPRINTF(("buddy: trying to allocate %d bytes, rorder = %d\n", size, rorder));
@@ -587,16 +277,34 @@ static void *lpsm_malloc_buddy(size_t size)
     xbit = lpsm_find_free_chunk(rorder);
     if ( !xbit ) {
       /* Need to extend */
-      print_statistics();		/* DEBUG */
-      if ( lpsm_extend_arena(ah->arena_size_lg2 + 1) )
-	return NULL;		/* Failed to extend */
+      lpsm_print_statistics();		/* DEBUG */
+      if ( lpsm_extend_arena(AH->arena_size_lg2 + 1) )
+	return 0;		/* Failed to extend */
     }
   } while ( !xbit );
 
   /* Mark this as a proper allocation (used to find the size on free()) */
-  set_bit(ah->alloc_bitmap, xbit);
+  set_bit(AH->alloc_bitmap, xbit);
 
-  p = (void *)((char *)ah->data_start + ((uintptr_t)(xbit-obit) << order));
+  return xbit;
+}
+
+void *lpsm_malloc_buddy(size_t size)
+{
+  int order = BUDDY_ORDER_MIN;
+  int xbit, obit;
+  void *p;
+
+  while ( size > ((size_t)1 << order) )
+    order++;
+
+  xbit = lpsm_malloc_buddy_xbit(order);
+  if ( !xbit )
+    return NULL;
+
+  obit = 1 << (AH->arena_size_lg2 - order);
+
+  p = (void *)((char *)AH->data_start + ((uintptr_t)(xbit-obit) << order));
 
   DPRINTF(("buddy: allocated %u/%u bytes at %p\n", size, 1U << order, p));
   return p;
@@ -615,7 +323,7 @@ static struct slab_header *lpsm_make_new_slab(struct slab_info *si, int index)
     return NULL;
 
   DPRINTF(("slab:  allocating new page for size %d at %p\n", si->size, sh));
-  assert(index == si - &ah->slab[0]);
+  assert(index == si - &AH->slab[0]);
 
   sh->magic       = SLAB_MAGIC;
   sh->free_count  = si->count;
@@ -639,7 +347,7 @@ static struct slab_header *lpsm_make_new_slab(struct slab_info *si, int index)
   return (si->list = sh);
 }
 
-static void *lpsm_malloc_slab(size_t size)
+void *lpsm_malloc_slab(size_t size)
 {
   int i, index;
   int which;
@@ -652,7 +360,7 @@ static void *lpsm_malloc_slab(size_t size)
   if ( size == 0 ) size = 1;
 
   index = 0;
-  si = &ah->slab[0];
+  si = &AH->slab[0];
   for ( i = 1 ; i < SLAB_INFO_COUNT ; i++ ) {
     if ( size <= si[1].size ) {
       si++;
@@ -678,7 +386,7 @@ static void *lpsm_malloc_slab(size_t size)
   
   slab_bitmap = (unsigned char *)(sh+1);
   
-  which = find_set_bit(slab_bitmap, 0, si->count, -1);
+  which = lpsm_find_set_bit(slab_bitmap, 0, si->count, -1);
   assert(which >= 0);		/* Otherwise something is bad... */
 
   clr_bit(slab_bitmap, which);	/* No longer available */
@@ -701,7 +409,7 @@ static void *lpsm_malloc_slab(size_t size)
 
 void *lpsm_malloc(size_t size)
 {
-  if ( size > ah->slab[0].size )
+  if ( size > AH->slab[0].size )
     return lpsm_malloc_buddy(size);
   else
     return lpsm_malloc_slab(size);
@@ -711,16 +419,16 @@ static void lpsm_free_chunk(int xbit, int rorder)
 {
   if ( rorder > 0 ) {
     int bxbit = xbit^1;		/* Buddy xbit */
-    if ( test_bit(ah->free_bitmap, bxbit) ) {
+    if ( test_bit(AH->free_bitmap, bxbit) ) {
       /* Buddy is free. */
-      clr_bit(ah->free_bitmap, bxbit);
+      clr_bit(AH->free_bitmap, bxbit);
       DPRINTF(("buddy: coalescing rorder %2d %d %d -> %2d %d\n",
 	       rorder, xbit, bxbit, rorder-1, (xbit >> 1)));
       lpsm_free_chunk((xbit >> 1), rorder-1);
       return;
     }
   }
-  set_bit(ah->free_bitmap, xbit);
+  set_bit(AH->free_bitmap, xbit);
 }
 
 /*
@@ -728,20 +436,16 @@ static void lpsm_free_chunk(int xbit, int rorder)
  * buddy allocation from its address; used by free() and
  * realloc().
  */
-struct buddy_params {
-  int xbit;
-  int rorder;
-};
-static struct buddy_params lpsm_find_alloc_buddy(void *ptr)
+struct buddy_params lpsm_find_alloc_buddy(void *ptr)
 {
   struct buddy_params bp;
-  uintptr_t offset = (uintptr_t)ptr - (uintptr_t)ah->data_start;
+  uintptr_t offset = (uintptr_t)ptr - (uintptr_t)AH->data_start;
   int order, rorder;
   int xbit, obit;
 
-  assert(offset < (1UL << ah->arena_size_lg2)); /* Not inside the arena?? */
+  assert(offset < (1UL << AH->arena_size_lg2)); /* Not inside the arena?? */
 
-  for ( rorder = 0, order = ah->arena_size_lg2 ;
+  for ( rorder = 0, order = AH->arena_size_lg2 ;
 	order >= BUDDY_ORDER_MIN ;
 	rorder++, order-- ) {
     if ( offset & ((1UL << order)-1) )
@@ -750,7 +454,7 @@ static struct buddy_params lpsm_find_alloc_buddy(void *ptr)
     obit = 1 << rorder;
     xbit = obit + (offset >> order);
     
-    if ( test_bit(ah->alloc_bitmap, xbit) ) {
+    if ( test_bit(AH->alloc_bitmap, xbit) ) {
       /* We're this order... */
       bp.xbit = xbit;  bp.rorder = rorder;
       return bp;
@@ -760,18 +464,18 @@ static struct buddy_params lpsm_find_alloc_buddy(void *ptr)
   abort();			/* Freeing bogus memory? */
 }
   
-static void lpsm_free_buddy(void *ptr)
+void lpsm_free_buddy(void *ptr)
 {
   struct buddy_params bp;
 
   DPRINTF(("buddy: freeing allocation at %p\n", ptr));
   bp = lpsm_find_alloc_buddy(ptr);
   DPRINTF(("buddy: freeing rorder %2d %8d\n", bp.rorder, bp.xbit));
-  clr_bit(ah->alloc_bitmap, bp.xbit);
+  clr_bit(AH->alloc_bitmap, bp.xbit);
   lpsm_free_chunk(bp.xbit, bp.rorder);
 }
 
-static void lpsm_free_slab(void *ptr)
+void lpsm_free_slab(void *ptr)
 {
   struct slab_header *sh;
   struct slab_info   *si;
@@ -781,7 +485,7 @@ static void lpsm_free_slab(void *ptr)
   /* 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];
+  si = &AH->slab[sh->index];
   slab_bitmap = (unsigned char *)sh +
     ((sizeof(struct slab_header)+MINIMUM_ALIGN-1) & ~MINIMUM_ALIGN_MASK);
 
@@ -817,7 +521,7 @@ static void lpsm_free_slab(void *ptr)
       /* Page is no longer full, add to free list */
       DPRINTF(("slab:  Adding page %p back onto free list for slab size %d\n",
 	       sh, si->size));
-      assert(sh->index == si - &ah->slab[0]);
+      assert(sh->index == si - &AH->slab[0]);
       sh->rev  = &(si->list);
       sh->next = si->list;
       if ( sh->next ) {
@@ -837,190 +541,3 @@ void lpsm_free(void *ptr)
   else
     lpsm_free_buddy(ptr);
 }
-
-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;
-    }
-  }
-}
diff --git a/arena.c b/arena.c
index 8026703..f28cb45 100644
--- a/arena.c
+++ b/arena.c
@@ -40,18 +40,12 @@
 #include "lpsm.h"
 #include "internals.h"
 
-/* This might end up being a bitmask eventually */
-enum page_status {
-  page_clean = 0,
-  page_dirty = 1,
-};
-
 /*
- * This is the data structure for the object store.  Note that only
- * one active object store is supported, due to the need to trap
- * SIGSEGV.
+ * This is the data structure for the persistent memory arena.  Note
+ * that only one arena is supported, due to the need to trap SIGSEGV
+ * and address space allocation issues.  
  */
-struct ObjStore *lpsm_os_struct;
+struct lpsm_arena *lpsm_memory_info = NULL;
 
 /* Wrappers for read() and write() which retries if incomplete */
 static ssize_t lpsm_read(int fd, void *buf, size_t count)
@@ -107,7 +101,6 @@ static ssize_t lpsm_write(int fd, void *buf, size_t count)
  */
 static void lpsm_sigsegv(int signal, siginfo_t *siginfo, void *ptr)
 {
-  struct ObjStore *os = lpsm_os_struct;
   void *page;
   uintptr_t npage, offset;
   char *pageinfo;
@@ -131,13 +124,13 @@ static void lpsm_sigsegv(int signal, siginfo_t *siginfo, void *ptr)
 # endif /* __i386__ */
 #endif /* __linux__ */
 
-  page = (void *)((uintptr_t)siginfo->si_addr & ~(os->pagesize-1));
-  offset = (uintptr_t)page - (uintptr_t)os->arena;
-  npage = (offset >> os->pageshift);
-  pageinfo = os->pageinfo + npage;
+  page = (void *)((uintptr_t)siginfo->si_addr & ~(PM->pagesize-1));
+  offset = (uintptr_t)page - (uintptr_t)PM->arena;
+  npage = (offset >> PM->pageshift);
+  pageinfo = PM->pageinfo + npage;
 
   if ( signal != SIGSEGV || siginfo->si_code != SEGV_ACCERR ||
-       offset >= os->arena_len ) {
+       offset >= PM->arena_len ) {
     struct sigaction dfl;
     
     dfl.sa_handler = SIG_DFL;
@@ -157,12 +150,12 @@ static void lpsm_sigsegv(int signal, siginfo_t *siginfo, void *ptr)
     return;			/* Re-take fault */
   }
   
-  mprotect(page, os->pagesize, PROT_READ|PROT_WRITE);
+  mprotect(page, PM->pagesize, PROT_READ|PROT_WRITE);
 
   switch ( (enum page_status) *pageinfo ) {
   case page_clean:
     *pageinfo = page_dirty;	/* Page now dirty */
-    os->dirty_count++;		/* For accounting purposes */
+    PM->dirty_count++;		/* For accounting purposes */
     /* Leave page r/w */
     break;
 
@@ -180,15 +173,14 @@ static void lpsm_sigsegv(int signal, siginfo_t *siginfo, void *ptr)
  */
 static int lpsm_log_writeback(void)
 {
-  struct ObjStore *os = lpsm_os_struct;
-  struct ObjStore_LogRecord record;
+  struct lpsm_logrecord record;
   off_t position, last_commit;
   struct flock lockmain;
   
   last_commit = 0;		/* Last COMMIT record found */
-  position = lseek(os->log_fd, 0, SEEK_SET);
+  position = lseek(PM->log_fd, 0, SEEK_SET);
   
-  while ( lpsm_read(os->log_fd, &record, sizeof(record)) == sizeof(record) ) {
+  while ( lpsm_read(PM->log_fd, &record, sizeof(record)) == sizeof(record) ) {
     if ( record.magic != LOGRECORD_MAGIC )
       break;			/* Bad magic, assume rest of log corrupt */
     if ( record.record_type == osrec_commit ) {
@@ -198,7 +190,7 @@ static int lpsm_log_writeback(void)
       last_commit = position;	/* Found a commit record */
     } else if ( record.record_type == osrec_page ) {
       /* Advance past current page cluster */
-      position = lseek(os->log_fd, record.size, SEEK_CUR);
+      position = lseek(PM->log_fd, record.size, SEEK_CUR);
     } else {
       return -1;		/* Unknown record - unsafe to process */
     }
@@ -207,9 +199,9 @@ static int lpsm_log_writeback(void)
   /* Now we know where the last commit was.  Now we can process
      everything up to that point. */
   
-  position = lseek(os->log_fd, 0, SEEK_SET);
+  position = lseek(PM->log_fd, 0, SEEK_SET);
   
-  while ( lpsm_read(os->log_fd, &record, sizeof(record))
+  while ( lpsm_read(PM->log_fd, &record, sizeof(record))
 	  == sizeof(record) && position < last_commit ) {
     if ( record.magic != LOGRECORD_MAGIC )
       break;			/* Bad magic, assume rest of log corrupt */
@@ -226,18 +218,18 @@ static int lpsm_log_writeback(void)
       lockmain.l_whence = SEEK_SET;
       lockmain.l_start  = record.offset;
       lockmain.l_len    = record.size;
-      while ( fcntl(os->main_fd, F_SETLKW, &lockmain) == -1 && errno == EINTR ); 
+      while ( fcntl(PM->main_fd, F_SETLKW, &lockmain) == -1 && errno == EINTR ); 
       data = mmap(NULL, record.size, PROT_WRITE, MAP_SHARED,
-		  os->main_fd, record.offset);
+		  PM->main_fd, record.offset);
       if ( data == MAP_FAILED )
 	return -1;
-      if ( lpsm_read(os->log_fd, data, record.size) != record.size )
+      if ( lpsm_read(PM->log_fd, data, record.size) != record.size )
 	return -1;		/* Badness */
       if ( munmap(data, record.size) )
 	return -1;
       
       lockmain.l_type = F_UNLCK;
-      while ( fcntl(os->main_fd, F_SETLKW, &lockmain) == -1 && errno == EINTR );
+      while ( fcntl(PM->main_fd, F_SETLKW, &lockmain) == -1 && errno == EINTR );
       position += record.size;
     } else {
       return -1;		/* Unknown record - unsafe to process */
@@ -245,17 +237,17 @@ static int lpsm_log_writeback(void)
   }
   
   /* Log successfully recovered.  Truncate. */
-  fsync(os->main_fd);
-  ftruncate(os->log_fd, 0);
+  fsync(PM->main_fd);
+  ftruncate(PM->log_fd, 0);
   /* Write initial commit record, for sequence number recovery */
   record.magic       = LOGRECORD_MAGIC;
   record.record_type = osrec_commit;
-  record.size        = os->fork_seq;
+  record.size        = PM->fork_seq;
   record.offset      = 0x54494d43; /* For debugging */
-  if ( lpsm_write(os->log_fd, &record, sizeof(record)) < sizeof(record) )
+  if ( lpsm_write(PM->log_fd, &record, sizeof(record)) < sizeof(record) )
     return -1;
 
-  fsync(os->log_fd);		/* Indicate log recovery complete */
+  fsync(PM->log_fd);		/* Indicate log recovery complete */
 
   return 0;
 }
@@ -265,7 +257,6 @@ static int lpsm_log_writeback(void)
  */
 static int lpsm_recover_log(void)
 {
-  struct ObjStore *os = lpsm_os_struct;
   struct flock lock;
   int rv = 0;
 
@@ -274,17 +265,17 @@ static int lpsm_recover_log(void)
   lock.l_whence = SEEK_SET;
   lock.l_start  = 0;
   lock.l_len    = 0;
-  while ( fcntl(os->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  while ( fcntl(PM->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
   /* Do log recovery, and write initial commit record. */
   rv = lpsm_log_writeback();
 
   /* Increase the sequence number, since we just wrote a commit. */
-  os->fork_seq++;
+  PM->fork_seq++;
 
   /* Unlock file and run. */
   lock.l_type = F_UNLCK;
-  while ( fcntl(os->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  while ( fcntl(PM->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
   return rv;
 }
@@ -296,7 +287,6 @@ static int lpsm_recover_log(void)
  */
 void *lpsm_arena_init(const char *main_file, const char *log_file, size_t *arena_len)
 {
-  struct ObjStore *os;
   void *arena_ptr;
   struct sigaction sigact;
   struct flock lock;
@@ -305,30 +295,30 @@ void *lpsm_arena_init(const char *main_file, const char *log_file, size_t *arena
 
   arena_ptr = ARENA_ADDRESS;
 
-  lpsm_os_struct = os = malloc(sizeof(struct ObjStore));
-  if ( !os )
+  PM = malloc(sizeof(struct lpsm_arena));
+  if ( !PM )
     goto errx0;
 
-  os->fork_seq = 0;		/* Initialize sequence counter */
+  PM->fork_seq = 0;		/* Initialize sequence counter */
 
-  os->main_fd = open(main_file, O_RDWR|O_CREAT, 0666);
-  if ( os->main_fd < 0 )
+  PM->main_fd = open(main_file, O_RDWR|O_CREAT, 0666);
+  if ( PM->main_fd < 0 )
     goto errx1;
 
-  os->pagesize = getpagesize();
-  if ( os->pagesize & (os->pagesize - 1) )
+  PM->pagesize = getpagesize();
+  if ( PM->pagesize & (PM->pagesize - 1) )
     goto errx2;			/* WTF -- pagesize not a power of 2? */
 
-  /* Compute log2(os->pagesize) */
-  os->pageshift = 0;
-  while ( (1 << os->pageshift) < os->pagesize )
-    os->pageshift++;
+  /* Compute log2(PM->pagesize) */
+  PM->pageshift = 0;
+  while ( (1 << PM->pageshift) < PM->pagesize )
+    PM->pageshift++;
 
   /*
    * Open log file
    */
-  os->log_fd = open(log_file, O_RDWR|O_APPEND|O_CREAT, 0666);
-  if ( os->log_fd < 0 )
+  PM->log_fd = open(log_file, O_RDWR|O_APPEND|O_CREAT, 0666);
+  if ( PM->log_fd < 0 )
     goto errx3;
 
   /* Now, do log recovery if needed */
@@ -340,55 +330,55 @@ void *lpsm_arena_init(const char *main_file, const char *log_file, size_t *arena
   lock.l_whence = SEEK_SET;
   lock.l_start  = 0;
   lock.l_len    = 0;
-  while ( fcntl(os->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
-  file_len = lseek(os->main_fd, 0, SEEK_END);
+  while ( fcntl(PM->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  file_len = lseek(PM->main_fd, 0, SEEK_END);
   if ( len < file_len ) {
     len = file_len;
   }
-  len = (len + os->pagesize - 1) & ~(os->pagesize - 1);
+  len = (len + PM->pagesize - 1) & ~(PM->pagesize - 1);
   if ( len > file_len ) {
-    ftruncate(os->main_fd, len);	/* Extend file */
+    ftruncate(PM->main_fd, len);	/* Extend file */
   }
   lock.l_type = F_UNLCK;
-  while ( fcntl(os->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  while ( fcntl(PM->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
-  os->arena = mmap(arena_ptr, len, PROT_READ, MAP_PRIVATE|MAP_FIXED, os->main_fd, 0);
-  if ( os->arena == MAP_FAILED )
+  PM->arena = mmap(arena_ptr, len, PROT_READ, MAP_PRIVATE|MAP_FIXED, PM->main_fd, 0);
+  if ( PM->arena == MAP_FAILED )
     goto errx3;
 
-  os->arena_len = len;
+  PM->arena_len = len;
   if ( *arena_len )
     *arena_len = len;
 
-  os->pageinfo = malloc(len >> os->pageshift);
-  if ( !os->pageinfo )
+  PM->pageinfo = malloc(len >> PM->pageshift);
+  if ( !PM->pageinfo )
     goto errx4;
 
-  file_len = (file_len + os->pagesize - 1) & ~(os->pagesize-1);
-  file_pages = file_len >> os->pageshift;
-  len_pages  = len >> os->pageshift;
+  file_len = (file_len + PM->pagesize - 1) & ~(PM->pagesize-1);
+  file_pages = file_len >> PM->pageshift;
+  len_pages  = len >> PM->pageshift;
 
   /* All pages clean at this time */
-  memset(os->pageinfo, page_clean, len_pages);
+  memset(PM->pageinfo, page_clean, len_pages);
 
   sigact.sa_sigaction = lpsm_sigsegv;
   sigemptyset(&sigact.sa_mask);
   sigact.sa_flags = SA_RESTART|SA_SIGINFO;
-  if ( sigaction(SIGSEGV, &sigact, &os->oldact) )
+  if ( sigaction(SIGSEGV, &sigact, &PM->oldact) )
     goto errx5;
 
-  return os->arena;
+  return PM->arena;
 
  errx5:
-  munmap(os->pageinfo, len >> os->pageshift);
+  munmap(PM->pageinfo, len >> PM->pageshift);
  errx4:
   munmap(arena_ptr, len);
  errx3:
-  if ( os->log_fd >= 0 ) close(os->log_fd);
+  if ( PM->log_fd >= 0 ) close(PM->log_fd);
  errx2:
-  close(os->main_fd);
+  close(PM->main_fd);
  errx1:
-  free(os);
+  free(PM);
  errx0:
 
   return NULL;
@@ -416,13 +406,12 @@ void *lpsm_arena_init(const char *main_file, const char *log_file, size_t *arena
 pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
 {
   static pid_t last_sync = 0;
-  struct ObjStore *os = lpsm_os_struct;
   pid_t f, w;
   char *pi, *epi;
   void *page;
   
-  pi  = os->pageinfo;
-  epi = os->pageinfo + (os->arena_len >> os->pageshift);
+  pi  = PM->pageinfo;
+  epi = PM->pageinfo + (PM->arena_len >> PM->pageshift);
 
   if ( last_sync ) {
     int status;
@@ -461,11 +450,11 @@ pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
     /* FIX: We probably want to do something more clever
        than memset() here, and perhaps keep around the old dirty
        array for a while. */
-    mprotect(os->arena, os->arena_len, PROT_READ);
-    memset(os->pageinfo, page_clean, os->arena_len >> os->pageshift);
+    mprotect(PM->arena, PM->arena_len, PROT_READ);
+    memset(PM->pageinfo, page_clean, PM->arena_len >> PM->pageshift);
     
-    os->dirty_count = 0;	/* No pages dirty */
-    os->fork_seq++;		/* Increase next sequence number */
+    PM->dirty_count = 0;	/* No pages dirty */
+    PM->fork_seq++;		/* Increase next sequence number */
 
     if ( wait == PSMSYNC_SYNC ) {
       int status;
@@ -482,7 +471,7 @@ pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
   } else {
     /* Child process -- do the actual work of writing back dirty pages */
 
-    struct ObjStore_LogRecord record, last_rec;
+    struct lpsm_logrecord record, last_rec;
     struct flock lock;
     off_t logsize;
 
@@ -495,43 +484,43 @@ pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
     for (;;) {
       /* First, lock the entire log file */
       lock.l_type   = F_WRLCK;
-      while ( fcntl(os->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+      while ( fcntl(PM->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
       /* Make sure we were indeed next in turn */
-      lseek(os->log_fd, -(off_t)sizeof(last_rec), SEEK_END);
-      if ( lpsm_read(os->log_fd, &last_rec, sizeof(last_rec)) < sizeof(last_rec) ||
+      lseek(PM->log_fd, -(off_t)sizeof(last_rec), SEEK_END);
+      if ( lpsm_read(PM->log_fd, &last_rec, sizeof(last_rec)) < sizeof(last_rec) ||
 	   last_rec.magic != LOGRECORD_MAGIC ) {
 	/* Something bad happened... */
 	  kill(getppid(), SIGABRT); /* Kill main process */
 	  _exit(99);
       }
-      if ( last_rec.size+1 == os->fork_seq )
+      if ( last_rec.size+1 == PM->fork_seq )
 	break;			/* It's for us... */
 
       /* Someone else is ahead of us in line.  Yield to them. */
       lock.l_type = F_UNLCK;
-      while ( fcntl(os->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+      while ( fcntl(PM->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
       
       sched_yield();		/* Snore... */
     }
 
     /* Write dirty pages to log file */
-    for ( pi = os->pageinfo ; pi < epi ; pi++ ) {
+    for ( pi = PM->pageinfo ; pi < epi ; pi++ ) {
       if ( *pi == page_dirty ) {
-	page = (char *)os->arena +
-	  ((uintptr_t)(pi - os->pageinfo) << os->pageshift);
-	record.offset = (char *)page - (char *)os->arena;
+	page = (char *)PM->arena +
+	  ((uintptr_t)(pi - PM->pageinfo) << PM->pageshift);
+	record.offset = (char *)page - (char *)PM->arena;
 
 	/* Aggregate contiguous pages into a single record */
-	record.size   = os->pagesize;
+	record.size   = PM->pagesize;
 	while ( pi+1 < epi && pi[1] == page_dirty ) {
 	  pi++;
-	  record.size += os->pagesize;
+	  record.size += PM->pagesize;
 	}
 
-	if ( lpsm_write(os->log_fd, &record, sizeof(record))
+	if ( lpsm_write(PM->log_fd, &record, sizeof(record))
 	     < sizeof(record) ||
-	     lpsm_write(os->log_fd, page, record.size) < record.size ) {
+	     lpsm_write(PM->log_fd, page, record.size) < record.size ) {
 	  kill(getppid(), SIGABRT); /* Kill main process */
 	  _exit(99);
 	}
@@ -539,21 +528,21 @@ pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
     }
 
     /* This might be more efficiently done with fdatasync() */
-    fsync(os->log_fd);		/* Make sure we have written everything */
+    fsync(PM->log_fd);		/* Make sure we have written everything */
     
     /* Write commit record */
     record.record_type = osrec_commit;
-    record.size        = os->fork_seq;
+    record.size        = PM->fork_seq;
     record.offset      = (off_t)0x54494d43;
-    if ( lpsm_write(os->log_fd, &record, sizeof(record)) < sizeof(record) ) {
+    if ( lpsm_write(PM->log_fd, &record, sizeof(record)) < sizeof(record) ) {
       kill(getppid(), SIGABRT);
       _exit(99);
     }
-    fsync(os->log_fd);
+    fsync(PM->log_fd);
 
     /* Check to see if it's time for garbage collect */
-    logsize = lseek(os->log_fd, 0, SEEK_END);
-    if ( gc_factor < HUGE_VAL && (double)logsize >= gc_factor*os->arena_len ) {
+    logsize = lseek(PM->log_fd, 0, SEEK_END);
+    if ( gc_factor < HUGE_VAL && (double)logsize >= gc_factor*PM->arena_len ) {
       /* Replaying the log isn't the most efficient way to do this.
 	 We could also keep a status bit per page around, and flush
 	 them out of the shadow array.  The biggest problem with that
@@ -567,7 +556,7 @@ pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
 
     /* Drop lock on log file */
     lock.l_type = F_UNLCK;
-    while ( fcntl(os->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+    while ( fcntl(PM->log_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
     _exit(0);			/* Done! */
   }
@@ -582,7 +571,6 @@ pid_t lpsm_checkpoint(double gc_factor, enum psmsync wait)
  */
 int lpsm_extend(size_t new_size)
 {
-  struct ObjStore *os = lpsm_os_struct;
   struct flock lock;
   void *newp, *infop;
   off_t file_size;
@@ -591,12 +579,12 @@ int lpsm_extend(size_t new_size)
   size_t add_pages, old_pages, new_pages, file_pages;
   struct rlimit fsizelimit;
 
-  old_size = os->arena_len;
+  old_size = PM->arena_len;
 
   if ( new_size <= old_size )
     return 0;			/* No action */
 
-  new_size = (new_size + os->pagesize - 1) & ~(os->pagesize - 1);
+  new_size = (new_size + PM->pagesize - 1) & ~(PM->pagesize - 1);
   add_size = new_size - old_size;
 
   /* Make sure we won't run afoul of a set resource limit. */
@@ -609,50 +597,50 @@ int lpsm_extend(size_t new_size)
   lock.l_whence = SEEK_SET;
   lock.l_start  = 0;
   lock.l_len    = 0;
-  while ( fcntl(os->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  while ( fcntl(PM->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
   lock.l_type = F_UNLCK;
-  file_size = lseek(os->main_fd, 0, SEEK_END);
+  file_size = lseek(PM->main_fd, 0, SEEK_END);
   if ( file_size < new_size )
-    ft = ftruncate(os->main_fd, new_size);
+    ft = ftruncate(PM->main_fd, new_size);
   else
     ft = 0;
 
   if ( ft )
     goto reset_size;		/* Failure */
 
-  newp = mmap((char*)os->arena + old_size,
+  newp = mmap((char*)PM->arena + old_size,
 	      add_size, PROT_READ,
-	      MAP_PRIVATE|MAP_FIXED, os->main_fd, old_size);
+	      MAP_PRIVATE|MAP_FIXED, PM->main_fd, old_size);
   
   if ( newp == MAP_FAILED )
     goto reset_size;		/* Failure */
 
   /* Since we specified MAP_FIXED, this should be guaranteed */
-  assert( newp == (char*)os->arena + old_size );
+  assert( newp == (char*)PM->arena + old_size );
 
   /* Convert sizes to pages */
-  file_size  = (file_size + os->pagesize - 1) & ~(os->pagesize-1);
-  new_pages  = new_size  >> os->pageshift;
-  old_pages  = old_size  >> os->pageshift;
-  file_pages = file_size >> os->pageshift;
+  file_size  = (file_size + PM->pagesize - 1) & ~(PM->pagesize-1);
+  new_pages  = new_size  >> PM->pageshift;
+  old_pages  = old_size  >> PM->pageshift;
+  file_pages = file_size >> PM->pageshift;
   add_pages  = new_pages - old_pages;
 
-  infop = realloc(os->pageinfo, new_pages);
+  infop = realloc(PM->pageinfo, new_pages);
   if ( !infop ) {
     munmap(newp, add_size);
     goto reset_size;
   }
   
-  os->arena_len  = new_size;
-  os->pageinfo   = infop;
+  PM->arena_len  = new_size;
+  PM->pageinfo   = infop;
 
   /* No more failure bailouts, unlock */
-  while ( fcntl(os->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  while ( fcntl(PM->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
 
   /* Mark new pages clean */
   assert(new_pages >= file_pages);
-  memset(os->pageinfo + file_pages, page_clean, new_pages-file_pages);
+  memset(PM->pageinfo + file_pages, page_clean, new_pages-file_pages);
 
   return 0;
 
@@ -660,9 +648,9 @@ int lpsm_extend(size_t new_size)
      due to address space limitations. */
  reset_size:
   /* Restore the original file size */
-  ftruncate(os->main_fd, file_size);
+  ftruncate(PM->main_fd, file_size);
   /* Drop lock */
-  while ( fcntl(os->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
+  while ( fcntl(PM->main_fd, F_SETLKW, &lock) == -1 && errno == EINTR );
   return -1;
 }
 
@@ -675,12 +663,10 @@ int lpsm_extend(size_t new_size)
  */
 void lpsm_shutdown(void)
 {
-  struct ObjStore *os = lpsm_os_struct;
-
-  munmap(os->arena, os->arena_len);
-  free(os->pageinfo);
-  sigaction(SIGSEGV, &os->oldact, NULL);
-  close(os->log_fd);
-  close(os->main_fd);
-  free(os);
+  munmap(PM->arena, PM->arena_len);
+  free(PM->pageinfo);
+  sigaction(SIGSEGV, &PM->oldact, NULL);
+  close(PM->log_fd);
+  close(PM->main_fd);
+  free(PM);
 }
diff --git a/bitops.c b/bitops.c
new file mode 100644
index 0000000..59cbdc6
--- /dev/null
+++ b/bitops.c
@@ -0,0 +1,89 @@
+#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.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * bitops.c
+ *
+ * Non-inline bitmap operations.
+ */
+
+#include <string.h>
+#include <assert.h>
+#include "bitops.h"
+
+/* Finds a one bit somewhere between [start, start+count) bit indicies.
+   Returns the index, or "err" if no such bit is found. */
+int lpsm_find_set_bit(const void *ptr, int start, int count, int err)
+{
+  const bitscan_t *cp, *ecp;
+  bitscan_t mask, val;
+  int i, end;
+
+  end = start+count-1;
+
+  cp = (bitscan_t *)ptr + (start >> BITSCAN_SHIFT);
+
+  if ( ((start^end) & ~BITSCAN_MASK) == 0 ) {
+    /* All falls within a single bitscan_t quantum */
+    mask = BITSCAN_1 << (start & BITSCAN_MASK);
+    val = *cp;
+    for ( i = start ; i <= end ; i++ ) {
+      if ( val & mask )
+	return i;
+      mask <<= 1;
+    }
+    return err;
+  }
+  
+  mask = ~BITSCAN_0 << (start & BITSCAN_MASK);
+  val = *cp++;
+  if ( val & mask ) {
+    end = start | BITSCAN_MASK;
+    mask = BITSCAN_1 << (start & BITSCAN_MASK);
+    for ( i = start ; i <= end ; i++ ) {
+      if ( val & mask )
+	return i;
+      mask <<= 1;
+    }
+    assert(0);			/* Internal error */
+  }
+
+  ecp = (bitscan_t *)ptr + (end >> BITSCAN_SHIFT);
+  start = (start & ~BITSCAN_MASK) + BITSCAN_BITS;
+
+  while ( cp < ecp ) {
+    val = *cp++;
+    if ( val ) {
+      mask = BITSCAN_1;
+      end = start | BITSCAN_MASK;
+      for ( i = start ; i <= end ; i++ ) {
+	if ( val & mask )
+	  return i;
+	mask <<= 1;
+      }
+      assert(0);		/* Internal error */
+    }
+    start += BITSCAN_BITS;
+  }
+
+  /* Scan final word */
+  val = *cp;
+  mask = BITSCAN_1;
+  for ( i = start ; i <= end ; i++ ) {
+    if ( val & mask )
+      return i;
+    mask <<= 1;
+  }
+  return err;			/* Nothing found */
+}
+
diff --git a/bitops.h b/bitops.h
new file mode 100644
index 0000000..f20c880
--- /dev/null
+++ b/bitops.h
@@ -0,0 +1,87 @@
+#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.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * bitops.h
+ *
+ * Internals for LPSM: bitmap operations.  Not to be used by applications.
+ */
+
+#ifndef LPSM_BITOPS_H
+#define LPSM_BITOPS_H
+
+#include <inttypes.h>
+#include "system.h"		/* System-specific constants */
+
+/* The data type to use for bitfield scanning.  Typically should equal
+   the "natural" size on the machine; defined in system.h. */
+#if MACHINE_SIZE_LG2 == 6
+  typedef uint64_t bitscan_t;
+#else
+  typedef uint32_t bitscan_t;
+#endif
+#define BITSCAN_SHIFT		MACHINE_SIZE_LG2
+#define BITSCAN_BITS		(1 << BITSCAN_SHIFT)
+#define BITSCAN_MASK		(BITSCAN_BITS-1)
+#define BITSCAN_0		((bitscan_t)0)
+#define BITSCAN_1		((bitscan_t)1)
+
+/*
+ * These should be revamped to be thread-safe at some point.  That
+ * may mean doing things that are architecture-specific...
+ *
+ * Important: "bit" can be negative, and that needs to be handled
+ * correctly!
+ */
+static inline int test_bit(const void *ptr, int bit)
+{
+#if defined(__GNUC__) && defined(__i386__)
+  int rv;
+  asm("xorl %0,%0 ; btl %2,%1 ; adcl %0,%0"
+      : "=&r" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
+  return rv;
+#else
+  const bitscan_t *cp;
+
+  cp = (const bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
+  return (int)((*cp >> (bit & BITSCAN_MASK)) & BITSCAN_1);
+#endif
+}
+
+static inline void set_bit(void *ptr, int bit)
+{
+#if defined(__GNUC__) && defined(__i386__)
+  asm volatile("btsl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
+#else
+  bitscan_t *cp;
+
+  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
+  *cp |= (BITSCAN_1 << (bit & BITSCAN_MASK));
+#endif
+}
+
+static inline void clr_bit(void *ptr, int bit)
+{
+#if defined(__GNUC__) && defined(__i386__)
+  asm volatile("btcl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
+#else
+  bitscan_t *cp;
+
+  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
+  *cp &= ~(BITSCAN_1 << (bit & BITSCAN_MASK));
+#endif
+}
+
+int lpsm_find_set_bit(const void *ptr, int start, int count, int err);
+
+#endif
diff --git a/internals.h b/internals.h
index bf90f1a..81aa518 100644
--- a/internals.h
+++ b/internals.h
@@ -14,16 +14,26 @@
 /*
  * internals.h
  *
- * Internals for object store
+ * Internals for LPSM.  Not to be used by applications.
  */
 
-#ifndef OBJSTORE_INTERNALS_H
-#define OBJSTORE_INTERNALS_H
+#ifndef LPSM_INTERNALS_H
+#define LPSM_INTERNALS_H
 
 #include "lpsm.h"		/* Main include file */
 #include "system.h"		/* System-specific constants */
 
-struct ObjStore {
+/* Debugging print statements */
+#ifdef PRINT_DEBUG_INFO
+#include <stdio.h>
+#define DPRINTF(X) printf X
+#else
+#define DPRINTF(X)
+#endif
+
+/* Arena definitions */
+
+struct lpsm_arena {
   int main_fd;			/* Primary file descriptor */
   int log_fd;			/* Log file descriptor */
   int pagesize;			/* Page size */
@@ -37,20 +47,104 @@ struct ObjStore {
   size_t fork_seq;		/* Sequence number of forked processes */
 };
 
-enum ObjStore_RecordType {
+enum lpsm_recordtype {
   osrec_page,			/* Page data */
   osrec_commit,			/* Commit record */
 };
 
 #define LOGRECORD_MAGIC 0x9247746e
 
-struct ObjStore_LogRecord {
+struct lpsm_logrecord {
   unsigned int  magic;		/* Magic number; for verification */
   unsigned int record_type;	/* Record */
   size_t size;			/* Data byte count (sequence # for commit) */
   off_t offset;			/* Offset of data */
 };
 
-extern struct ObjStore *lpsm_os_struct;
+extern struct lpsm_arena *lpsm_memory_info;
+#define PM lpsm_memory_info	/* Shorthand */
+
+/* This might end up being a bitmask eventually */
+enum page_status {
+  page_clean = 0,
+  page_dirty = 1,
+};
+
+/* Memory management definitions */
+
+#define SLAB_MAGIC		0xec2062ae
+
+struct slab_info {
+  int size;			/* Size of SLAB */
+  int count;			/* SLABs per page */
+  int data_offset;		/* Start of data area */
+  int total_pages;		/* Count of pages allocaed to this size SLAB */
+  int alloc_slabs;		/* Count of SLABs currently in use */
+  struct slab_header *list;
+};
+
+/* This is 16 bytes on 32-bit and 24 bytes on 64-bit architectures */
+/* This header must end aligned to a bitscan_t datum */
+struct slab_header {
+  uint32_t magic;
+  uint16_t free_count;
+  uint16_t index;		/* Index into slab_info array */
+  struct slab_header *next, **rev;
+};
+
+#define SLAB_INFO_COUNT	32
+
+struct arena_header {
+  unsigned char arena_magic[16];
+  uint32_t arena_byteorder;
+  uint16_t arena_bytesize;
+  uint16_t arena_ptrsize;
+  void *arena_base;		/* Base of allocation */
+  void *free_bitmap;		/* The free bitmap */
+  void *alloc_bitmap;		/* The allocated (buddy) bitmap */
+  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];
+  void *root_data_ptrs[LPSM_ROOT_POINTERS]; /* Root data pointers - for the user */
+};
+
+extern struct arena_header *lpsm_arena_header;
+#define AH lpsm_arena_header	/* Shorthand */
+
+/* This is the minimal order before going to SLAB allocation. */
+#define BUDDY_ORDER_MIN		12
+#define BUDDY_SIZE_MIN		(1U << BUDDY_ORDER_MIN)
+
+/* Align allocations at least this large (2^n) to this boundary */
+#define MINIMUM_ALIGN_LG2	4
+#define MINIMUM_ALIGN		(1 << MINIMUM_ALIGN_LG2)
+#define MINIMUM_ALIGN_MASK	(MINIMUM_ALIGN-1)
+
+/* This is the size (2^n) allocated for a brand new arena.
+   This allocation will be sparse, so don't freak out too much! */
+#define ARENA_START_SIZE_LG2	17 /* 128K */
+#define ARENA_START_SIZE	(1UL << ARENA_START_SIZE_LG2)
+
+/* Function definitions used across modules */
+
+struct buddy_params {
+  int xbit;
+  int rorder;
+};
+struct buddy_params lpsm_find_alloc_buddy(void *ptr);
+int lpsm_extend_arena(int logsize);
+int lpsm_malloc_buddy_xbit(int order);
+void *lpsm_malloc_buddy(size_t size);
+void *lpsm_malloc_slab(size_t size);
+void lpsm_free_buddy(void *ptr);
+void lpsm_free_slab(void *ptr);
+
+#ifdef PRINT_DEBUG_INFO
+void lpsm_print_statistics(void);
+#else
+#define lpsm_print_statistics() ((void)0)
+#endif
 
 #endif
diff --git a/lpsm.h b/lpsm.h
index b70475d..b7c5f13 100644
--- a/lpsm.h
+++ b/lpsm.h
@@ -57,6 +57,16 @@ struct lpsm_alloc_stats {
   size_t free;
   size_t alloc;
 };
+void *lpsm_zalloc(size_t);
+#ifdef __GNUC__
+extern inline void *lpsm_calloc(size_t __nmemb, size_t __size)
+{
+  return lpsm_zalloc(__nmemb * __size);
+}
+#else
+#define lpsm_calloc(__nmemb, __size) lpsm_zalloc((size_t)(__nmemb)*(size_t)(__size))
+#endif
+
 struct lpsm_alloc_stats *lpsm_alloc_stats(void);
 
 #endif /* LPSM_H */
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;
+    }
+  }
+}
diff --git a/zalloc.c b/zalloc.c
new file mode 100644
index 0000000..b6e5195
--- /dev/null
+++ b/zalloc.c
@@ -0,0 +1,72 @@
+#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.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * zalloc.c
+ *
+ * Allocate zero-initialized memory.  Try to be efficient if the area is
+ * large.
+ *
+ */
+
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <sys/mman.h>
+#include "lpsm.h"
+#include "internals.h"
+
+void *lpsm_zalloc(size_t size)
+{
+  void *ptr, *mv;
+  int xbit, obit, rorder;
+  int order = BUDDY_ORDER_MIN;
+
+  if ( size > AH->slab[0].size ) {
+    while ( size > ((size_t)1 << order) )
+      order++;
+
+    xbit = lpsm_malloc_buddy_xbit(size);
+    if ( !xbit ) {
+      ptr = NULL;
+    } else {
+      rorder = AH->arena_size_lg2 - order;
+      obit = 1 << rorder;
+      ptr = (void *)((char *)AH->data_start +
+		     ((uintptr_t)(xbit-obit) << order)); 
+      if ( (uintptr_t)ptr & (PM->pagesize-1) ||
+	   order < PM->pageshift ) {
+	memset(ptr, 0, size);	/* Misaligned or too small */
+      } else {
+	size = (size_t)1 << order; /* "Real" size */
+	/* Do an anonymous mmap() over the affected area */
+	mv = mmap(ptr, size, PROT_READ|PROT_WRITE,
+		  MAP_FIXED|MAP_PRIVATE, 0, 0);
+	if ( mv != ptr ) {
+	  memset(ptr, 0, size);
+	} else {
+	  /* Mark dirty */
+	  memset(PM->pageinfo + ((ptr-PM->arena) >> PM->pageshift),
+		 page_dirty, size >> PM->pageshift);
+	}
+      }
+    }
+  } else {
+    ptr = lpsm_malloc_slab(size);
+    if ( ptr )
+      memset(ptr, 0, size);
+  }
+
+  return ptr;
+}
+