aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2001-10-13 20:50:08 +0000
committerH. Peter Anvin <hpa@zytor.com>2001-10-13 20:50:08 +0000
commitd8eff73f38cec27e9090f040a457d51adf9e959b (patch)
tree0c8cfed549a9cc3f5f3d54945d9a69066cb81a24
parentfd2cb9815b27ca8a45d820c3e45f2c39ca58b8ea (diff)
downloadlpsm-d8eff73f38cec27e9090f040a457d51adf9e959b.tar.gz
lpsm-d8eff73f38cec27e9090f040a457d51adf9e959b.tar.xz
lpsm-d8eff73f38cec27e9090f040a457d51adf9e959b.zip
Modify the bitmap definition so that we use positive offsets, which make
life *so* much easier to deal with. Fix a couple of bogus (c) notices.
-rw-r--r--alloc.c68
-rw-r--r--testbuddy.c11
-rw-r--r--teststore.c11
3 files changed, 48 insertions, 42 deletions
diff --git a/alloc.c b/alloc.c
index 773a093..81d0250 100644
--- a/alloc.c
+++ b/alloc.c
@@ -20,6 +20,7 @@
* and a SLAB allocator for small allocations.
*
* This generally assumes 8-bit bytes and 2's-complement arithmetric.
+ * These days, that's oh-such-a-strech...
*/
#include <assert.h>
@@ -72,8 +73,8 @@ struct arena_header {
uint16_t arena_ptrsize;
void *arena_base; /* Base of allocation */
void *root_data_ptr; /* Root data pointer - for the user */
- void *free_bitmap_end; /* End of the free bitmap */
- void *alloc_bitmap_end; /* End of the allocated (buddy) bitmap */
+ 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 */
@@ -97,9 +98,17 @@ struct arena_header {
#define HEADER_SIZE BUDDY_SIZE_MIN /* Default size of the header */
/* The data type to use for bitfield scanning. Typically should equal
- the "natural" size on the machine... use autoconf for this? */
-typedef uint32_t bitscan_t;
-#define BITSCAN_SHIFT 5
+ the "natural" size on the machine, which used to always be "int".
+ Unfortunately, that's no longer true... and getting all of these,
+ including the value "bitscan_shift" doesn't seem to be feasible
+ without external help. */
+#ifdef BITSCAN_USE_UINT64
+ typedef uint64_t bitscan_t;
+# define BITSCAN_SHIFT 6
+#else
+ typedef uint32_t bitscan_t;
+# define BITSCAN_SHIFT 5
+#endif
#define BITSCAN_BITS (1 << BITSCAN_SHIFT)
#define BITSCAN_MASK (BITSCAN_BITS-1)
#define BITSCAN_0 ((bitscan_t)0)
@@ -245,8 +254,8 @@ void *objstore_arena_init(void)
ah->arena_size_lg2 = ARENA_START_SIZE_LG2;
bitmap_size = 1UL << (ARENA_START_SIZE_LG2-BUDDY_ORDER_MIN-2);
total_size = HEADER_SIZE + ARENA_START_SIZE + (bitmap_size << 1);
- ah->free_bitmap_end = (char *)ah + total_size;
- ah->alloc_bitmap_end = (char *)ah->free_bitmap_end - bitmap_size;
+ ah->free_bitmap = (char *)ah + HEADER_SIZE + ARENA_START_SIZE;
+ ah->alloc_bitmap = (char *)ah->free_bitmap + bitmap_size;
if ( objstore_extend(total_size) < 0 )
return NULL; /* Failed to establish initial arena */
@@ -268,14 +277,13 @@ void *objstore_arena_init(void)
count--;
}
-
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_end, -1);
+ set_bit(ah->free_bitmap, 1);
}
}
@@ -293,12 +301,10 @@ void *objstore_arena_init(void)
static int objstore_find_free_chunk(int rorder)
{
- int rs, obit, xbit;
+ int obit, xbit;
- rs = 1 << rorder;
- obit = 1-(rs+rs);
-
- xbit = find_set_bit(ah->free_bitmap_end, obit, rs, 0);
+ obit = 1 << rorder;
+ xbit = find_set_bit(ah->free_bitmap, obit, obit, 0);
if ( !xbit ) {
if ( rorder == 0 )
@@ -306,12 +312,12 @@ static int objstore_find_free_chunk(int rorder)
xbit = objstore_find_free_chunk(rorder-1);
if ( !xbit )
return 0; /* All out of those, sir */
- printf("buddy: splitting rorder %2d %8d -> %d %d\n", rorder-1, xbit, (xbit << 1)-1, (xbit << 1));
+ printf("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_end, xbit); /* Upper buddy is available */
- xbit--; /* Return the lower buddy */
+ set_bit(ah->free_bitmap, xbit+1); /* Upper buddy is available */
+ /* Return the lower buddy */
} else {
- clr_bit(ah->free_bitmap_end, xbit); /* No longer available */
+ clr_bit(ah->free_bitmap, xbit); /* No longer available */
}
printf("buddy: allocated rorder %2d %8d\n", rorder, xbit);
return xbit;
@@ -335,7 +341,7 @@ static void *objstore_malloc_buddy(size_t size)
/* Convert to order relative to the arena size order */
rorder = ah->arena_size_lg2 - order;
- obit = 1-(2 << rorder);
+ obit = 1 << rorder;
printf("buddy: trying to allocate %d bytes, rorder = %d\n", size, rorder);
@@ -346,10 +352,9 @@ static void *objstore_malloc_buddy(size_t size)
}
/* Mark this as a proper allocation (used to find the size on free()) */
- set_bit(ah->alloc_bitmap_end, xbit);
+ set_bit(ah->alloc_bitmap, xbit);
- p = (void *)((char *)ah->data_start +
- ((uintptr_t)(xbit-obit) << order));
+ p = (void *)((char *)ah->data_start + ((uintptr_t)(xbit-obit) << order));
printf("buddy: allocated %u/%u bytes at %p\n", size, 1U << order, p);
return p;
@@ -451,19 +456,18 @@ void *objstore_malloc(size_t size)
static void objstore_free_chunk(int xbit, int rorder)
{
- int bxbit = -(-xbit^1); /* Buddy xbit */
-
if ( rorder > 0 ) {
- if ( test_bit(ah->free_bitmap_end, bxbit) ) {
+ int bxbit = xbit^1; /* Buddy xbit */
+ if ( test_bit(ah->free_bitmap, bxbit) ) {
/* Buddy is free. */
- clr_bit(ah->free_bitmap_end, bxbit);
+ clr_bit(ah->free_bitmap, bxbit);
printf("buddy: coalescing rorder %2d %d %d -> %2d %d\n",
- rorder, xbit, bxbit, rorder-1, -(-xbit >> 1));
- objstore_free_chunk(-(-xbit >> 1), rorder-1);
+ rorder, xbit, bxbit, rorder-1, (xbit >> 1));
+ objstore_free_chunk((xbit >> 1), rorder-1);
return;
}
}
- set_bit(ah->free_bitmap_end, xbit);
+ set_bit(ah->free_bitmap, xbit);
}
static void objstore_free_buddy(void *ptr)
@@ -482,13 +486,13 @@ static void objstore_free_buddy(void *ptr)
if ( offset & ((1UL << order)-1) )
continue; /* Can't be this order */
- obit = 1-(2 << rorder);
+ obit = 1 << rorder;
xbit = obit + (offset >> order);
- if ( test_bit(ah->alloc_bitmap_end, xbit) ) {
+ if ( test_bit(ah->alloc_bitmap, xbit) ) {
/* We're this order... */
printf("buddy: freeing rorder %2d %8d\n", rorder, xbit);
- clr_bit(ah->alloc_bitmap_end, xbit);
+ clr_bit(ah->alloc_bitmap, xbit);
objstore_free_chunk(xbit, rorder);
return;
}
diff --git a/testbuddy.c b/testbuddy.c
index 00375b6..5bde336 100644
--- a/testbuddy.c
+++ b/testbuddy.c
@@ -1,12 +1,13 @@
#ident "$Id$"
/* ----------------------------------------------------------------------- *
*
- * Copyright 2000 Transmeta Corporation - All Rights Reserved
+ * Copyright 2001 H. Peter Anvin - All Rights Reserved
*
- * This source module contains confidential and proprietary information
- * of Transmeta Corporation. It is not to be disclosed or used except
- * in accordance with applicable agreements. This copyright notice does
- * not evidence any actual or intended publication of such source code.
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, Inc., 675 Mass Ave, Cambridge MA 02139,
+ * USA; either version 2 of the License, or (at your option) any later
+ * version; incorporated herein by reference.
*
* ----------------------------------------------------------------------- */
diff --git a/teststore.c b/teststore.c
index 14c40fc..ba85141 100644
--- a/teststore.c
+++ b/teststore.c
@@ -1,12 +1,13 @@
#ident "$Id$"
/* ----------------------------------------------------------------------- *
*
- * Copyright 2000 Transmeta Corporation - All Rights Reserved
+ * Copyright 2000-2001 H. Peter Anvin - All Rights Reserved
*
- * This source module contains confidential and proprietary information
- * of Transmeta Corporation. It is not to be disclosed or used except
- * in accordance with applicable agreements. This copyright notice does
- * not evidence any actual or intended publication of such source code.
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, Inc., 675 Mass Ave, Cambridge MA 02139,
+ * USA; either version 2 of the License, or (at your option) any later
+ * version; incorporated herein by reference.
*
* ----------------------------------------------------------------------- */