X-Git-Url: http://v3vee.org/palacios/gitweb/gitweb.cgi?a=blobdiff_plain;f=kitten%2Fmm%2Fbuddy.c;fp=kitten%2Fmm%2Fbuddy.c;h=ad132cb91cf764acddba9d29c5780316d08b6921;hb=66a1a4c7a9edcd7d8bc207aca093d694a6e6b5b2;hp=0000000000000000000000000000000000000000;hpb=f7cf9c19ecb0a589dd45ae0d2c91814bd3c2acc2;p=palacios.git

diff --git a/kitten/mm/buddy.c b/kitten/mm/buddy.c
new file mode 100644
index 0000000..ad132cb
--- /dev/null
+++ b/kitten/mm/buddy.c
@@ -0,0 +1,274 @@
+/* Copyright (c) 2007, Sandia National Laboratories */
+
+#include <lwk/kernel.h>
+#include <lwk/log2.h>
+#include <lwk/buddy.h>
+#include <lwk/bootmem.h>
+
+
+/**
+ * Each free block has one of these structures at its head. The link member
+ * provides linkage for the mp->avail[order] free list, where order is the
+ * size of the free block.
+ */
+struct block {
+	struct list_head link;
+	unsigned long    order;
+};
+
+
+/**
+ * Converts a block address to its block index in the specified buddy allocator.
+ * A block's index is used to find the block's tag bit, mp->tag_bits[block_id].
+ */
+static unsigned long
+block_to_id(struct buddy_mempool *mp, struct block *block)
+{
+	unsigned long block_id =
+		((unsigned long)block - mp->base_addr) >> mp->min_order;
+	BUG_ON(block_id >= mp->num_blocks);
+	return block_id;
+}
+
+
+/**
+ * Marks a block as free by setting its tag bit to one.
+ */
+static void
+mark_available(struct buddy_mempool *mp, struct block *block)
+{
+	__set_bit(block_to_id(mp, block), mp->tag_bits);
+}
+
+
+/**
+ * Marks a block as allocated by setting its tag bit to zero.
+ */
+static void
+mark_allocated(struct buddy_mempool *mp, struct block *block)
+{
+	__clear_bit(block_to_id(mp, block), mp->tag_bits);
+}
+
+
+/**
+ * Returns true if block is free, false if it is allocated.
+ */
+static int
+is_available(struct buddy_mempool *mp, struct block *block)
+{
+	return test_bit(block_to_id(mp, block), mp->tag_bits);
+}
+
+
+/**
+ * Returns the address of the block's buddy block.
+ */
+static void *
+find_buddy(struct buddy_mempool *mp, struct block *block, unsigned long order)
+{
+	unsigned long _block;
+	unsigned long _buddy;
+
+	BUG_ON((unsigned long)block < mp->base_addr);
+
+	/* Fixup block address to be zero-relative */
+	_block = (unsigned long)block - mp->base_addr;
+
+	/* Calculate buddy in zero-relative space */
+	_buddy = _block ^ (1UL << order);
+
+	/* Return the buddy's address */
+	return (void *)(_buddy + mp->base_addr);
+}
+
+
+/**
+ * Initializes a buddy system memory allocator object.
+ *
+ * Arguments:
+ *       [IN] base_addr:  Base address of the memory pool.
+ *       [IN] pool_order: Size of the memory pool (2^pool_order bytes).
+ *       [IN] min_order:  Minimum allocatable block size (2^min_order bytes).
+ *
+ * Returns:
+ *       Success: Pointer to an initialized buddy system memory allocator.
+ *       Failure: NULL
+ *
+ * NOTE: The min_order argument is provided as an optimization. Since one tag
+ *       bit is required for each minimum-sized block, large memory pools that
+ *       allow order 0 allocations will use large amounts of memory. Specifying
+ *       a min_order of 5 (32 bytes), for example, reduces the number of tag
+ *       bits by 32x.
+ */
+struct buddy_mempool *
+buddy_init(
+	unsigned long base_addr,
+	unsigned long pool_order,
+	unsigned long min_order
+)
+{
+	struct buddy_mempool *mp;
+	unsigned long i;
+
+	/* Smallest block size must be big enough to hold a block structure */
+	if ((1UL << min_order) < sizeof(struct block))
+		min_order = ilog2( roundup_pow_of_two(sizeof(struct block)) );
+
+	/* The minimum block order must be smaller than the pool order */
+	if (min_order > pool_order)
+		return NULL;
+
+	mp = alloc_bootmem(sizeof(struct buddy_mempool));
+	
+	mp->base_addr  = base_addr;
+	mp->pool_order = pool_order;
+	mp->min_order  = min_order;
+
+	/* Allocate a list for every order up to the maximum allowed order */
+	mp->avail = alloc_bootmem((pool_order + 1) * sizeof(struct list_head));
+
+	/* Initially all lists are empty */
+	for (i = 0; i <= pool_order; i++)
+		INIT_LIST_HEAD(&mp->avail[i]);
+
+	/* Allocate a bitmap with 1 bit per minimum-sized block */
+	mp->num_blocks = (1UL << pool_order) / (1UL << min_order);
+	mp->tag_bits   = alloc_bootmem(
+	                     BITS_TO_LONGS(mp->num_blocks) * sizeof(long)
+	                 );
+
+	/* Initially mark all minimum-sized blocks as allocated */
+	bitmap_zero(mp->tag_bits, mp->num_blocks);
+
+	return mp;
+}
+
+
+/**
+ * Allocates a block of memory of the requested size (2^order bytes).
+ *
+ * Arguments:
+ *       [IN] mp:    Buddy system memory allocator object.
+ *       [IN] order: Block size to allocate (2^order bytes).
+ *
+ * Returns:
+ *       Success: Pointer to the start of the allocated memory block.
+ *       Failure: NULL
+ */
+void *
+buddy_alloc(struct buddy_mempool *mp, unsigned long order)
+{
+	unsigned long j;
+	struct list_head *list;
+	struct block *block;
+	struct block *buddy_block;
+
+	BUG_ON(mp == NULL);
+	BUG_ON(order > mp->pool_order);
+
+	/* Fixup requested order to be at least the minimum supported */
+	if (order < mp->min_order)
+		order = mp->min_order;
+
+	for (j = order; j <= mp->pool_order; j++) {
+
+		/* Try to allocate the first block in the order j list */
+		list = &mp->avail[j];
+		if (list_empty(list))
+			continue;
+		block = list_entry(list->next, struct block, link);
+		list_del(&block->link);
+		mark_allocated(mp, block);
+
+		/* Trim if a higher order block than necessary was allocated */
+		while (j > order) {
+			--j;
+			buddy_block = (struct block *)((unsigned long)block + (1UL << j));
+			buddy_block->order = j;
+			mark_available(mp, buddy_block);
+			list_add(&buddy_block->link, &mp->avail[j]);
+		}
+
+		return block;
+	}
+
+	return NULL;
+}
+
+
+/**
+ * Returns a block of memory to the buddy system memory allocator.
+ *
+ * Arguments:
+ *       [IN] mp:    Buddy system memory allocator object.
+ *       [IN] addr:  Address of memory block to free.
+ *       [IN] order: Size of the memory block (2^order bytes).
+ */
+void
+buddy_free(struct buddy_mempool *mp, void *addr, unsigned long order)
+{
+	struct block *block;
+	struct block *buddy;
+
+	BUG_ON(mp == NULL);
+	BUG_ON(order > mp->pool_order);
+
+	/* Fixup requested order to be at least the minimum supported */
+	if (order < mp->min_order)
+		order = mp->min_order;
+
+	/* Overlay block structure on the memory block being freed */
+	block = addr;
+	BUG_ON(is_available(mp, block));
+
+	/* Coalesce as much as possible with adjacent free buddy blocks */
+	while (order < mp->pool_order) {
+		/* Determine our buddy block's address */
+		buddy = find_buddy(mp, block, order);
+
+		/* Make sure buddy is available and has the same size as us */
+		if (!is_available(mp, buddy))
+			break;
+		if (is_available(mp, buddy) && (buddy->order != order))
+			break;
+
+		/* OK, we're good to go... buddy merge! */
+		list_del(&buddy->link);
+		if (buddy < block)
+			block = buddy;
+		++order;
+		block->order = order;
+	}
+
+	/* Add the (possibly coalesced) block to the appropriate free list */
+	block->order = order;
+	mark_available(mp, block);
+	list_add(&block->link, &mp->avail[order]);
+}
+
+
+/**
+ * Dumps the state of a buddy system memory allocator object to the console.
+ */
+void
+buddy_dump_mempool(struct buddy_mempool *mp)
+{
+	unsigned long i;
+	unsigned long num_blocks;
+	struct list_head *entry;
+
+	printk(KERN_DEBUG "DUMP OF BUDDY MEMORY POOL:\n");
+
+	for (i = mp->min_order; i <= mp->pool_order; i++) {
+
+		/* Count the number of memory blocks in the list */
+		num_blocks = 0;
+		list_for_each(entry, &mp->avail[i])
+			++num_blocks;
+
+		printk(KERN_DEBUG "  order %2lu: %lu free blocks\n", i, num_blocks);
+	}
+}
+
+