aboutsummaryrefslogtreecommitdiffstats
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
parentf3d637296f1f839d4a95a849a7dbfbb600f563f1 (diff)
downloadlpsm-50cedb0ff19233273ef33cb5b5e8725025a35024.tar.gz
lpsm-50cedb0ff19233273ef33cb5b5e8725025a35024.tar.xz
lpsm-50cedb0ff19233273ef33cb5b5e8725025a35024.zip
Split apart into modules. Create lpsm_zalloc()/lpsm_calloc().
-rw-r--r--Makefile9
-rw-r--r--README11
-rw-r--r--alloc.c663
-rw-r--r--arena.c242
-rw-r--r--bitops.c89
-rw-r--r--bitops.h87
-rw-r--r--internals.h108
-rw-r--r--lpsm.h10
-rw-r--r--realloc.c216
-rw-r--r--zalloc.c72
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;
+}
+