summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2008-01-15 03:18:03 (GMT)
committerH. Peter Anvin <hpa@zytor.com>2008-01-15 03:18:03 (GMT)
commitf734372b23435748a9e794f3997e53c99fe1a786 (patch)
treecdd2a8c66705b995e8b867475179175f87579d94
parent18284e8f5c54510ee02d5a3513b79aa687f9ed6f (diff)
downloadlpsm-f734372b23435748a9e794f3997e53c99fe1a786.zip
lpsm-f734372b23435748a9e794f3997e53c99fe1a786.tar.gz
lpsm-f734372b23435748a9e794f3997e53c99fe1a786.tar.bz2
lpsm-f734372b23435748a9e794f3997e53c99fe1a786.tar.xz
64-bit fixes (still has errors, however)
Do a number of 64-bit fixes. In particular: * (1 << foo) is not safe if foo >= 32 * size_t is the appropriate type for "as big as we can fit"
-rw-r--r--bitops.c94
-rw-r--r--bitops.h81
-rw-r--r--malloc.c40
-rw-r--r--testalloc.c69
4 files changed, 163 insertions, 121 deletions
diff --git a/bitops.c b/bitops.c
index c6f4886..f969136 100644
--- a/bitops.c
+++ b/bitops.c
@@ -1,11 +1,11 @@
/* ----------------------------------------------------------------------- *
*
- * Copyright 2000-2001 H. Peter Anvin - All Rights Reserved
+ * Copyright 2000-2008 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,
+ * 51 Franklin St, Fifth Floor, Boston MA 02110-1301, USA; version 2.1,
* incorporated herein by reference.
*
* ----------------------------------------------------------------------- */
@@ -22,67 +22,55 @@
/* 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)
+size_t lpsm_find_set_bit(const void *ptr, size_t start, size_t count,
+ size_t err)
{
const bitscan_t *cp, *ecp;
- bitscan_t mask, val;
- int i, end;
+ bitscan_t val, smask, emask;
+ size_t end, base;
- end = start+count-1;
+ assert(count >= 1);
- cp = (bitscan_t *)ptr + (start >> BITSCAN_SHIFT);
+ end = start+count-1; /* Inclusive! */
- if ( ((start^end) & ~BITSCAN_MASK) == 0 ) {
+ cp = (const bitscan_t *)ptr + (start >> BITSCAN_SHIFT);
+ ecp = (const bitscan_t *)ptr + (end >> BITSCAN_SHIFT);
+
+ base = start & ~BITSCAN_MASK;
+
+ smask = ~BITSCAN_0 << (start & BITSCAN_MASK);
+ emask = ~(~BITSCAN_1 << (end & BITSCAN_MASK));
+
+ if (cp == ecp) {
/* 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;
+ val = *cp & smask & emask;
+ if ( !val )
+ return err;
+ else
+ return bitctz(val) + base;
}
- 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;
+ /* First quantum */
+ val = *cp & smask;
+ if (val)
+ return bitctz(val) + base;
+ cp++;
+ base += 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;
+ /* Whole quanta */
+ while (cp < ecp) {
+ val = *cp;
+ if (val)
+ return bitctz(val) + base;
+ cp++;
+ base += 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 */
+ /* Final quantum */
+ val = *cp & emask;
+ if (val)
+ return bitctz(val) + base;
+ else
+ return err; /* Nothing found */
}
diff --git a/bitops.h b/bitops.h
index 8e870b9..bb79979 100644
--- a/bitops.h
+++ b/bitops.h
@@ -1,11 +1,11 @@
/* ----------------------------------------------------------------------- *
*
- * Copyright 2000-2001 H. Peter Anvin - All Rights Reserved
+ * Copyright 2000-2008 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,
+ * 51 Franklin St, Fifth Floor, Boston MA 02110-1301, USA; version 2.1,
* incorporated herein by reference.
*
* ----------------------------------------------------------------------- */
@@ -26,14 +26,16 @@
the "natural" size on the machine; defined in system.h. */
#if MACHINE_SIZE_LG2 == 6
typedef uint64_t bitscan_t;
+# define BITSCAN_C(X) UINT64_C(X)
#else
typedef uint32_t bitscan_t;
+# define BITSCAN_C(X) UINT32_C(X)
#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)
+#define BITSCAN_0 BITSCAN_C(0)
+#define BITSCAN_1 BITSCAN_C(1)
/*
* These should be revamped to be thread-safe at some point. That
@@ -42,12 +44,17 @@
* Important: "bit" can be negative, and that needs to be handled
* correctly!
*/
-static inline int test_bit(const void *ptr, int bit)
+static inline int test_bit(const void *ptr, size_t 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");
+#if defined(__GNUC__) && defined(__x86_64__)
+ char rv;
+ asm("btq %2,%1 ; setc %0"
+ : "=rm" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
+ return rv;
+#elif defined(__GNUC__) && defined(__i386__)
+ char rv;
+ asm("btl %2,%1 ; setc %0"
+ : "=rm" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
return rv;
#else
const bitscan_t *cp;
@@ -57,10 +64,12 @@ static inline int test_bit(const void *ptr, int bit)
#endif
}
-static inline void set_bit(void *ptr, int bit)
+static inline void set_bit(void *ptr, size_t bit)
{
-#if defined(__GNUC__) && defined(__i386__)
- asm volatile("btsl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
+#if defined(__GNUC__) && defined(__x86_64__)
+ asm volatile("btsq %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
+#elif defined(__GNUC__) && defined(__i386__)
+ asm volatile("btsl %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#else
bitscan_t *cp;
@@ -69,10 +78,12 @@ static inline void set_bit(void *ptr, int bit)
#endif
}
-static inline void clr_bit(void *ptr, int bit)
+static inline void clr_bit(void *ptr, size_t bit)
{
-#if defined(__GNUC__) && defined(__i386__)
- asm volatile("btcl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
+#if defined(__GNUC__) && defined(__x86_64__)
+ asm volatile("btcq %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
+#elif defined(__GNUC__) && defined(__i386__)
+ asm volatile("btcl %1,%0" : "+m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#else
bitscan_t *cp;
@@ -81,6 +92,44 @@ static inline void clr_bit(void *ptr, int bit)
#endif
}
-int lpsm_find_set_bit(const void *ptr, int start, int count, int err);
+static inline int bitctz(bitscan_t x)
+{
+#if defined(__GNUC__) && __GNUC__ >= 4
+ return __builtin_ctzl(x);
+#else
+ int r = 0;
+# if MACHINE_SIZE_LG2 >= 6
+ if (!(x & BITSCAN_C(0xffffffff))) {
+ r += 32;
+ x >>= 32;
+ }
+# endif
+ if (!(x & BITSCAN_C(0xffff))) {
+ r += 16;
+ x >>= 16;
+ }
+ if (!(x & BITSCAN_C(0xff))) {
+ r += 8;
+ x >>= 8;
+ }
+ if (!(x & BITSCAN_C(0xf))) {
+ r += 4;
+ x >>= 4;
+ }
+ if (!(x & BITSCAN_C(0x3))) {
+ r += 2;
+ x >>= 2;
+ }
+ if (!(x & BITSCAN_C(0x1))) {
+ r += 1;
+ /* x >>= 1; */
+ }
+ return r;
#endif
+}
+
+size_t lpsm_find_set_bit(const void *ptr, size_t start, size_t count,
+ size_t err);
+
+#endif /* LPSM_BITOPS_H */
diff --git a/malloc.c b/malloc.c
index 5f71da0..f05bd88 100644
--- a/malloc.c
+++ b/malloc.c
@@ -1,11 +1,11 @@
/* ----------------------------------------------------------------------- *
*
- * Copyright 2000-2001 H. Peter Anvin - All Rights Reserved
+ * Copyright 2000-2008 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,
+ * 51 Franklin St, Fifth Floor, Boston MA 02110-1301, USA; version 2.1,
* incorporated herein by reference.
*
* ----------------------------------------------------------------------- */
@@ -36,16 +36,17 @@
* Note that "orders" here refers to orders of bitmap, which is usually
* arena_size_lg2 - BUDDY_ORDER_MIN + 1.
*/
-static void lpsm_expand_bitmap(void *nbitmap, const void *obitmap, int norder, int oorder)
+static void lpsm_expand_bitmap(void *nbitmap, const void *obitmap,
+ int norder, int oorder)
{
- int deltao, o, i, obit, nbit;
- int obyte, nbyte;
+ int deltao, o, i;
+ size_t obit, nbit, obyte, nbyte;
assert(norder > oorder);
deltao = norder - oorder;
/* First, expand the orders which have fractional bytes */
- obit = 1; nbit = 1 << deltao;
+ obit = 1; nbit = (size_t)1 << deltao;
for ( o = 0 ; o < 3 ; o++ ) {
for ( i = 0 ; i < obit ; i++ ) {
if ( test_bit(obitmap, obit+i) )
@@ -55,11 +56,9 @@ static void lpsm_expand_bitmap(void *nbitmap, const void *obitmap, int norder, i
}
/* Then expand the orders which have complete bytes */
- obyte = 1; nbyte = 1 << deltao;
+ obyte = 1; nbyte = (size_t)1 << deltao;
for ( o = 3 ; o < oorder ; o++ ) {
- memcpy((unsigned char *)nbitmap + nbyte,
- (unsigned char *)obitmap + obyte,
- obyte);
+ memcpy((char *)nbitmap + nbyte, (char *)obitmap + obyte, obyte);
obyte <<= 1; nbyte <<= 1;
}
}
@@ -72,15 +71,15 @@ 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 bitmap_size;
+ size_t bitmap_size;
void *newfreemap, *newallocmap;
- int obp;
+ size_t obp;
assert(logsize > ologsize);
DPRINTF(("arena: extending arena to order %d: ", logsize));
- bitmap_size = 1 << (logsize-BUDDY_ORDER_MIN-1);
+ bitmap_size = (size_t)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;
newallocmap = (char *)newfreemap + bitmap_size;
@@ -100,7 +99,7 @@ int lpsm_extend_arena(int logsize)
AH->arena_size_lg2 = logsize;
/* Mark the new allocations available */
- obp = 1 << (logsize-ologsize);
+ obp = (size_t)1 << (logsize-ologsize);
if ( test_bit(newfreemap, obp) ) {
/* The arena is completely unallocated... */
clr_bit(newfreemap, obp);
@@ -126,9 +125,9 @@ int lpsm_extend_arena(int logsize)
*/
static int lpsm_find_free_chunk(int rorder)
{
- int obit, xbit;
+ size_t obit, xbit;
- obit = 1 << rorder;
+ obit = (size_t)1 << rorder;
xbit = lpsm_find_set_bit(AH->free_bitmap, obit, obit, 0);
if ( !xbit ) {
@@ -137,14 +136,15 @@ static int lpsm_find_free_chunk(int rorder)
xbit = lpsm_find_free_chunk(rorder-1);
if ( !xbit )
return 0; /* All out of those, sir */
- DPRINTF(("buddy: splitting rorder %2d %8d -> %d %d\n", rorder-1, xbit, xbit << 1, (xbit << 1)+1));
+ DPRINTF(("buddy: splitting rorder %2d %8zu -> %zu %zu\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 */
/* Return the lower buddy */
} else {
clr_bit(AH->free_bitmap, xbit); /* No longer available */
}
- DPRINTF(("buddy: allocated rorder %2d %8d\n", rorder, xbit));
+ DPRINTF(("buddy: allocated rorder %2d %8zu\n", rorder, xbit));
return xbit;
}
@@ -245,7 +245,7 @@ static struct slab_header *lpsm_make_new_slab(struct slab_info *si, int index)
void *lpsm_malloc_slab(size_t size)
{
int i, index;
- int which;
+ size_t which;
struct slab_info *si;
struct slab_header *sh;
void *slab_bitmap;
@@ -286,7 +286,7 @@ void *lpsm_malloc_slab(size_t size)
slab_bitmap = (unsigned char *)(sh+1);
which = lpsm_find_set_bit(slab_bitmap, 0, si->count, -1);
- assert(which >= 0); /* Otherwise something is bad... */
+ assert(which != (size_t)-1); /* Otherwise something is bad... */
clr_bit(slab_bitmap, which); /* No longer available */
si->alloc_slabs++;
diff --git a/testalloc.c b/testalloc.c
index 3cccd26..79c2dba 100644
--- a/testalloc.c
+++ b/testalloc.c
@@ -23,24 +23,27 @@
#define SLOTS 1024
#define MAXLOG 26
-void *areas[COUNT];
-int sizes[COUNT];
+struct area_info {
+ void *ptr;
+ size_t size;
+ int atseq;
+} areas[COUNT];
void verify_no_overlap(int slot)
{
- char *start = areas[slot];
- char *end = start+sizes[slot];
+ char *start = areas[slot].ptr;
+ char *end = start+areas[slot].size;
char *xs, *xe;
int i;
for ( i = 0 ; i < SLOTS ; i++ ) {
- if ( i != slot && areas[i] ) {
- xs = areas[i];
- xe = xs + sizes[i];
+ if ( i != slot && areas[i].ptr ) {
+ xs = areas[i].ptr;
+ xe = xs + areas[i].size;
if ( xs < end && xe > start ) {
- printf("OVERLAP ALERT: [%p,%p) -> [%p,%p)\n",
- start, end, xs, xe);
+ printf("OVERLAP ALERT: [%p,%p) -> [%p,%p) (from sequence %d)\n",
+ start, end, xs, xe, areas[i].atseq);
abort();
}
}
@@ -62,7 +65,6 @@ int main(int argc, char *argv[])
unlink("arena.log");
memset(areas, 0, sizeof(areas));
- memset(sizes, 0, sizeof(sizes));
if ( !(root_ptr = lpsm_init("arena.dat", "arena.log")) ) {
fprintf(stderr, "%s: lpsm_arena_init() failed\n", argv[0]);
@@ -79,41 +81,44 @@ int main(int argc, char *argv[])
slot = rand() % SLOTS;
- if ( areas[slot] ) {
+ if ( areas[slot].ptr ) {
if ( rand() % 1 ) {
- printf("Free: %d (0x%08x) bytes at %p\n",
- sizes[slot], sizes[slot], areas[slot]);
- lpsm_free(areas[slot]);
- areas[slot] = NULL;
- occupied -= sizes[slot];
+ printf("Free: %zu (0x%zx) bytes at %p\n",
+ areas[slot].size, areas[slot].size, areas[slot].ptr);
+ lpsm_free(areas[slot].ptr);
+ areas[slot].ptr = NULL;
+ occupied -= areas[slot].size;
+ areas[slot].atseq = 0;
} else {
rnd = (double)rand()/RAND_MAX;
newsize = (int)pow(2.0, MAXLOG*pow(rnd,3.0));
- nptr = lpsm_realloc(areas[slot], newsize);
+ nptr = lpsm_realloc(areas[slot].ptr, newsize);
if ( nptr ) {
- printf("Realloc: %d bytes at %p -> %d bytes at %p\n",
- sizes[slot], areas[slot], newsize, nptr);
+ printf("Realloc: %zu bytes at %p -> %d bytes at %p\n",
+ areas[slot].size, areas[slot].ptr, newsize, nptr);
occupied += newsize;
- occupied -= sizes[slot];
- sizes[slot] = newsize;
- areas[slot] = nptr;
+ occupied -= areas[slot].size;
+ areas[slot].size = newsize;
+ areas[slot].ptr = nptr;
+ areas[slot].atseq = sequence;
verify_no_overlap(slot);
} else {
- printf("Realloc: %d bytes at %p -> %d bytes FAILED\n",
- sizes[slot], areas[slot], newsize);
+ printf("Realloc: %zu bytes at %p -> %d bytes FAILED\n",
+ areas[slot].size, areas[slot].ptr, newsize);
}
}
} else {
rnd = (double)rand()/RAND_MAX;
- sizes[slot] = (int)pow(2.0, MAXLOG*pow(rnd,5.0));
- areas[slot] = lpsm_malloc(sizes[slot]);
- if ( areas[slot] ) {
- printf("Alloc: %d (0x%08x) bytes at %p\n",
- sizes[slot], sizes[slot], areas[slot]);
- occupied += sizes[slot];
+ areas[slot].size = (int)pow(2.0, MAXLOG*pow(rnd,5.0));
+ areas[slot].ptr = lpsm_malloc(areas[slot].size);
+ if ( areas[slot].ptr ) {
+ printf("Alloc: %zu (0x%zx) bytes at %p\n",
+ areas[slot].size, areas[slot].size, areas[slot].ptr);
+ occupied += areas[slot].size;
+ areas[slot].atseq = sequence;
} else {
- printf("Alloc: %d (0x%08x) bytes FAILED\n",
- sizes[slot], sizes[slot]);
+ printf("Alloc: %zu (0x%zx) bytes FAILED\n",
+ areas[slot].size, areas[slot].size);
}
verify_no_overlap(slot);
}