aboutsummaryrefslogtreecommitdiffstats
path: root/free.c
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2001-10-20 02:32:11 +0000
committerH. Peter Anvin <hpa@zytor.com>2001-10-20 02:32:11 +0000
commitbe9d8ab8ec452c46777b2eb4ae925843d7361c7b (patch)
treeaad187010f9d0f268698c53273a86dc392207eb1 /free.c
parent50cedb0ff19233273ef33cb5b5e8725025a35024 (diff)
downloadlpsm-be9d8ab8ec452c46777b2eb4ae925843d7361c7b.tar.gz
lpsm-be9d8ab8ec452c46777b2eb4ae925843d7361c7b.tar.xz
lpsm-be9d8ab8ec452c46777b2eb4ae925843d7361c7b.zip
Add calloc(), break alloc.c into free/malloc/mgmt files, add
automatic dependency generation.
Diffstat (limited to 'free.c')
-rw-r--r--free.c155
1 files changed, 155 insertions, 0 deletions
diff --git a/free.c b/free.c
new file mode 100644
index 0000000..627e53f
--- /dev/null
+++ b/free.c
@@ -0,0 +1,155 @@
+#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.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * free.c
+ *
+ * Provides free() for the persistent memory allocator.
+ */
+
+#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_free_chunk(int xbit, int rorder)
+{
+ if ( rorder > 0 ) {
+ int bxbit = xbit^1; /* Buddy xbit */
+ if ( test_bit(AH->free_bitmap, bxbit) ) {
+ /* Buddy is free. */
+ 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);
+}
+
+/*
+ * This routine finds the parameters for one particular
+ * buddy allocation from its address; used by free() and
+ * realloc().
+ */
+struct buddy_params lpsm_find_alloc_buddy(void *ptr)
+{
+ struct buddy_params bp;
+ 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?? */
+
+ for ( rorder = 0, order = AH->arena_size_lg2 ;
+ order >= BUDDY_ORDER_MIN ;
+ rorder++, order-- ) {
+ if ( offset & ((1UL << order)-1) )
+ continue; /* Can't be this order */
+
+ obit = 1 << rorder;
+ xbit = obit + (offset >> order);
+
+ if ( test_bit(AH->alloc_bitmap, xbit) ) {
+ /* We're this order... */
+ bp.xbit = xbit; bp.rorder = rorder;
+ return bp;
+ }
+ }
+
+ abort(); /* Freeing bogus memory? */
+}
+
+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);
+ lpsm_free_chunk(bp.xbit, bp.rorder);
+}
+
+void lpsm_free_slab(void *ptr)
+{
+ struct slab_header *sh;
+ struct slab_info *si;
+ int offset, which, free_count;
+ unsigned char *slab_bitmap;
+
+ /* 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];
+ slab_bitmap = (unsigned char *)sh +
+ ((sizeof(struct slab_header)+MINIMUM_ALIGN-1) & ~MINIMUM_ALIGN_MASK);
+
+ DPRINTF(("slab: Freeing size %d slab at %p, %d/%d allocated\n",
+ si->size, ptr, si->count-sh->free_count, si->count));
+
+ offset = ((uintptr_t)ptr & (BUDDY_SIZE_MIN-1)) - si->data_offset;
+ assert(offset >= 0);
+ which = offset/si->size;
+ assert(offset == which*si->size);
+
+ free_count = sh->free_count;
+ si->alloc_slabs--;
+
+ if ( free_count == si->count-1 ) {
+ /* Deallocated the entire page; give back to buddy system */
+ DPRINTF(("slab: Returning page %p back to the buddy system\n", sh));
+ *(sh->rev) = sh->next; /* Remove from free list */
+ if ( sh->next ) {
+ sh->next->rev = sh->rev;
+ assert(sh->next->index == sh->index);
+ }
+ si->total_pages--;
+#ifndef NDEBUG
+ /* This unfortunately makes the page dirty */
+ memset(sh, 0, BUDDY_SIZE_MIN);
+#endif
+ lpsm_free_buddy(sh);
+ } else {
+ set_bit(slab_bitmap, which);
+ sh->free_count = free_count+1;
+ if ( free_count == 0 ) {
+ /* 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]);
+ sh->rev = &(si->list);
+ sh->next = si->list;
+ if ( sh->next ) {
+ sh->next->rev = &(sh->next);
+ assert(sh->next->index == sh->index);
+ }
+ si->list = sh;
+ }
+ }
+}
+
+void lpsm_free(void *ptr)
+{
+ /* Buddy allocations are ALWAYS page-aligned, SLAB allocations never */
+ if ( (uintptr_t)ptr & (BUDDY_SIZE_MIN-1) )
+ lpsm_free_slab(ptr);
+ else
+ lpsm_free_buddy(ptr);
+}