buddy: Add a simple generic buddy allocator

It operates on bits representing whatever objects the caller wants
it to represent, it's not per-se a memory allocator (it's meant to
be used among others by XIVE for VP allocations). As such it cannot
keep linked lists of free objects, so don't expect stellar perfs.

Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org>
[stewart@linux.vnet.ibm.com: add (C) header, fix gcc4.8 build error]
Signed-off-by: Stewart Smith <stewart@linux.vnet.ibm.com>

5 files changed, 441 insertions, 2 deletions

diff --git a/core/Makefile.inc b/core/Makefile.inc
index 98bcb11c..21670446 100644
--- a/core/Makefile.inc
+++ b/core/Makefile.inc
@@ -8,7 +8,7 @@ CORE_OBJS += pci-opal.o fast-reboot.o device.o exceptions.o trace.o affinity.o
 CORE_OBJS += vpd.o hostservices.o platform.o nvram.o nvram-format.o hmi.o
 CORE_OBJS += console-log.o ipmi.o time-utils.o pel.o pool.o errorlog.o
 CORE_OBJS += timer.o i2c.o rtc.o flash.o sensor.o ipmi-opal.o
-CORE_OBJS += flash-subpartition.o bitmap.o
+CORE_OBJS += flash-subpartition.o bitmap.o buddy.o
 
 ifeq ($(SKIBOOT_GCOV),1)
 CORE_OBJS += gcov-profiling.o
diff --git a/core/buddy.c b/core/buddy.c
new file mode 100644
index 00000000..59cd2cb0
--- /dev/null
+++ b/core/buddy.c
@@ -0,0 +1,302 @@
+/* Copyright 2016 IBM Corp.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * 	http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "buddy.h"
+
+#define BUDDY_DEBUG
+#undef  BUDDY_VERBOSE
+
+#ifdef BUDDY_VERBOSE
+#define BUDDY_NOISE(fmt...)	printf(fmt)
+#else
+#define BUDDY_NOISE(fmt...)	do { } while(0)
+#endif
+
+static inline unsigned int buddy_map_size(struct buddy *b)
+{
+	return 1u << (b->max_order + 1);
+}
+
+static inline unsigned int buddy_order_start(struct buddy *b,
+					     unsigned int order)
+{
+	unsigned int level = b->max_order - order;
+
+	/* Starting bit of index for order */
+	return 1u << level;
+}
+
+static inline unsigned int buddy_index_to_node(struct buddy *b,
+					       unsigned int index,
+					       unsigned int order)
+{
+	/* Ensure the index is a multiple of the order */
+	assert((index & ((1u << order) - 1)) == 0);
+
+	return buddy_order_start(b, order) + (index >> order);
+}
+
+static inline unsigned int buddy_node_to_index(struct buddy *b,
+					       unsigned int node,
+					       unsigned int order)
+{
+	unsigned int start = buddy_order_start(b, order);
+
+	return (node - start) << order;
+}
+
+#ifdef BUDDY_DEBUG
+static void buddy_check_alloc(struct buddy *b, unsigned int node)
+{
+	assert(bitmap_tst_bit(b->map, node));
+}
+
+static void buddy_check_alloc_down(struct buddy *b, unsigned int node)
+{
+	unsigned int i, count = 1;
+
+	while (node < buddy_map_size(b)) {
+		for (i = 0; i < count; i++)
+			buddy_check_alloc(b, node + i);
+
+		/* Down one level */
+		node <<= 1;
+		count <<= 1;
+	}
+}
+#else
+static inline void buddy_check_alloc(struct buddy *b, unsigned int node) {}
+static inline void buddy_check_alloc_down(struct buddy *b, unsigned int node) {}
+#endif
+
+int buddy_alloc(struct buddy *b, unsigned int order)
+{
+	unsigned int o;
+	int node, index;
+
+	BUDDY_NOISE("buddy_alloc(%d)\n", order);
+	/*
+	 * Find the first order up the tree from our requested order that
+	 * has at least one free node.
+	 */
+	for (o = order; o <= b->max_order; o++) {
+		if (b->freecounts[o] > 0)
+			break;
+	}
+
+	/* Nothing found ? fail */
+	if (o > b->max_order) {
+		BUDDY_NOISE("  no free nodes !\n");
+		return -1;
+	}
+
+	BUDDY_NOISE("  %d free node(s) at order %d, bits %d(%d)\n",
+		    b->freecounts[o], o,
+		    buddy_order_start(b, o),
+		    1u << (b->max_order - o));
+
+	/* Now find a free node */
+	node = bitmap_find_zero_bit(b->map, buddy_order_start(b, o),
+				    1u << (b->max_order - o));
+
+	/* There should always be one */
+	assert(node >= 0);
+
+	/* Mark it allocated and decrease free count */
+	bitmap_set_bit(b->map, node);
+	b->freecounts[o]--;
+
+	/* We know that node was free which means all its children must have
+	 * been marked "allocated". Double check.
+	 */
+	buddy_check_alloc_down(b, node);
+
+	/* We have a node, we've marked it allocated, now we need to go down
+	 * the tree until we reach "order" which is the order we need. For
+	 * each level along the way, we mark the buddy free and leave the
+	 * first child allocated.
+	 */
+	while (o > order) {
+		/* Next level down */
+		o--;
+		node <<= 1;
+
+		BUDDY_NOISE("  order %d, using %d marking %d free\n",
+			    o, node, node ^ 1);
+		bitmap_clr_bit(b->map, node ^ 1);
+		b->freecounts[o]++;
+		assert(bitmap_tst_bit(b->map, node));
+	}
+
+	index = buddy_node_to_index(b, node, order);
+
+	BUDDY_NOISE("  result is index %d (node %d)\n", index, node);
+
+	/* We have a node, convert it to an element number */
+	return index;
+}
+
+bool buddy_reserve(struct buddy *b, unsigned int index, unsigned int order)
+{
+	unsigned int node, freenode, o;
+
+	assert(index < (1u << b->max_order));
+
+	BUDDY_NOISE("buddy_reserve(%d,%d)\n", index, order);
+
+	/* Get bit number for node */
+	node = buddy_index_to_node(b, index, order);
+
+	BUDDY_NOISE("  node=%d\n", node);
+
+	/* Find something free */
+	for (freenode = node, o = order; freenode > 0; freenode >>= 1, o++)
+		if (!bitmap_tst_bit(b->map, freenode))
+			break;
+
+	BUDDY_NOISE("  freenode=%d order %d\n", freenode, o);
+
+	/* Nothing free, error out */
+	if (!freenode)
+		return false;
+
+	/* We sit on a free node, mark it busy */
+	bitmap_set_bit(b->map, freenode);
+	assert(b->freecounts[o]);
+	b->freecounts[o]--;
+
+	/* We know that node was free which means all its children must have
+	 * been marked "allocated". Double check.
+	 */
+	buddy_check_alloc_down(b, freenode);
+
+	/* Reverse-walk the path and break down nodes */
+	while (o > order) {
+		/* Next level down */
+		o--;
+		freenode <<= 1;
+
+		/* Find the right one on the path to node */
+		if (node & (1u << (o - order)))
+		    freenode++;
+
+		BUDDY_NOISE("  order %d, using %d marking %d free\n",
+			    o, freenode, freenode ^ 1);
+		bitmap_clr_bit(b->map, freenode ^ 1);
+		b->freecounts[o]++;
+		assert(bitmap_tst_bit(b->map, node));
+	}
+	assert(node == freenode);
+
+	return true;
+}
+
+void buddy_free(struct buddy *b, unsigned int index, unsigned int order)
+{
+	unsigned int node;
+
+	assert(index < (1u << b->max_order));
+
+	BUDDY_NOISE("buddy_free(%d,%d)\n", index, order);
+
+	/* Get bit number for node */
+	node = buddy_index_to_node(b, index, order);
+
+	BUDDY_NOISE("  node=%d\n", node);
+
+	/* We assume that anything freed was fully allocated, ie,
+	 * there is no child node of that allocation index/order
+	 * that is already free.
+	 *
+	 * BUDDY_DEBUG will verify it at the cost of performances
+	 */
+	buddy_check_alloc_down(b, node);
+
+	/* Propagate if buddy is free */
+	while (order < b->max_order && !bitmap_tst_bit(b->map, node ^ 1)) {
+		BUDDY_NOISE("  order %d node %d buddy %d free, propagating\n",
+			    order, node, node ^ 1);
+
+		/* Mark buddy busy (we are already marked busy) */
+		bitmap_set_bit(b->map, node ^ 1);
+
+		/* Reduce free count */
+		assert(b->freecounts[order] > 0);
+		b->freecounts[order]--;
+
+		/* Get parent */
+		node >>= 1;
+		order++;
+
+		/* It must be busy already ! */
+		buddy_check_alloc(b, node);
+
+		BUDDY_NOISE("  testing order %d node %d\n", order, node ^ 1);
+	}
+
+	/* No more coalescing, mark it free */
+	bitmap_clr_bit(b->map, node);
+
+	/* Increase the freelist count for that level */
+	b->freecounts[order]++;
+
+	BUDDY_NOISE("  free count at order %d is %d\n",
+		    order, b->freecounts[order]);
+}
+
+void buddy_reset(struct buddy *b)
+{
+	unsigned int bsize = BITMAP_BYTES(1u << (b->max_order + 1));
+
+	BUDDY_NOISE("buddy_reset()\n");
+	/* We fill the bitmap with 1's to make it completely "busy" */
+	memset(b->map, 0xff, bsize);
+	memset(b->freecounts, 0, sizeof(b->freecounts));
+
+	/* We mark the root of the tree free, this is entry 1 as entry 0
+	 * is unused.
+	 */
+	buddy_free(b, 0, b->max_order);
+}
+
+struct buddy *buddy_create(unsigned int max_order)
+{
+	struct buddy *b;
+	unsigned int bsize;
+
+	assert(max_order <= BUDDY_MAX_ORDER);
+
+	bsize = BITMAP_BYTES(1u << (max_order + 1));
+
+	b = zalloc(sizeof(struct buddy) + bsize);
+	b->max_order = max_order;
+
+	BUDDY_NOISE("Map @%p, size: %d bytes\n", b->map, bsize);
+
+	buddy_reset(b);
+
+	return b;
+}
+
+void buddy_destroy(struct buddy *b)
+{
+	free(b);
+}
+
diff --git a/core/test/Makefile.check b/core/test/Makefile.check
index 869eafc0..35540504 100644
--- a/core/test/Makefile.check
+++ b/core/test/Makefile.check
@@ -18,7 +18,8 @@ CORE_TEST := \
 	core/test/run-pool \
 	core/test/run-time-utils \
 	core/test/run-timebase \
-	core/test/run-timer
+	core/test/run-timer \
+	core/test/run-buddy
 
 HOSTCFLAGS+=-I . -I include
 
diff --git a/core/test/run-buddy.c b/core/test/run-buddy.c
new file mode 100644
index 00000000..80de917a
--- /dev/null
+++ b/core/test/run-buddy.c
@@ -0,0 +1,82 @@
+/* Copyright 2016 IBM Corp.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * 	http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <buddy.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+static void *zalloc(size_t size)
+{
+        return calloc(size, 1);
+}
+
+#include "../buddy.c"
+#include "../bitmap.c"
+
+#define BUDDY_ORDER	8
+
+int main(void)
+{
+	struct buddy *b;
+	int i, a[10];
+
+	b = buddy_create(BUDDY_ORDER);
+	assert(b);
+
+	buddy_reserve(b, 127, 0);
+	buddy_reserve(b, 0, 4);
+
+	a[0] = buddy_alloc(b, 0);
+	assert(a[0] >= 0);
+	a[1] = buddy_alloc(b, 0);
+	assert(a[1] >= 0);
+	a[2] = buddy_alloc(b, 3);
+	assert(a[2] >= 0);
+	a[3] = buddy_alloc(b, 4);
+	assert(a[3] >= 0);
+	a[4] = buddy_alloc(b, 5);
+	assert(a[4] >= 0);
+	a[5] = buddy_alloc(b, 4);
+	assert(a[5] >= 0);
+	a[6] = buddy_alloc(b, 3);
+	assert(a[6] >= 0);
+	a[7] = buddy_alloc(b, 2);
+	assert(a[7] >= 0);
+	a[8] = buddy_alloc(b, 1);
+	assert(a[8] >= 0);
+	a[9] = buddy_alloc(b, 8);
+	assert(a[9] < 0);
+
+	buddy_free(b, a[0], 0);
+	buddy_free(b, a[8], 1);
+	buddy_free(b, a[1], 0);
+	buddy_free(b, a[7], 2);
+	buddy_free(b, a[2], 3);
+	buddy_free(b, a[6], 3);
+	buddy_free(b, a[3], 4);
+	buddy_free(b, a[5], 4);
+	buddy_free(b, a[4], 5);
+
+	buddy_free(b, 127, 0);
+	buddy_free(b, 0, 4);
+
+	for (i = 2; i < buddy_map_size(b); i++)
+		assert(bitmap_tst_bit(b->map, i));
+	assert(!bitmap_tst_bit(b->map, 1));
+
+	buddy_destroy(b);
+	return 0;
+}
diff --git a/include/buddy.h b/include/buddy.h
new file mode 100644
index 00000000..fa97eb0a
--- /dev/null
+++ b/include/buddy.h
@@ -0,0 +1,54 @@
+/* Copyright 2016 IBM Corp.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * 	http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * Simple power-of-two buddy allocation mechanism.
+ *
+ */
+#ifndef __BUDDY_H
+#define __BUDDY_H
+
+#include "bitmap.h"
+
+#define BUDDY_MAX_ORDER	30
+
+struct buddy {
+	/* max_order is both the height of the tree - 1 and the ^2 of the
+	 * size of the lowest level.
+	 *
+	 * So if we have 512k elements, max_order is 19, which gives us
+	 * a 20 levels tree.
+	 *
+	 * The max supported order is 30 for now. We can increase that
+	 * later if really needed but the performance is going to be
+	 * already pretty bad if we go near that limit.
+	 */
+	unsigned int max_order;
+
+	/* For each order, we keep track of how many free modes we
+	 * have there to speed up searches.
+	 */
+	unsigned int freecounts[BUDDY_MAX_ORDER + 1];
+	bitmap_elem_t     map[];
+};
+
+extern struct buddy *buddy_create(unsigned int max_order);
+extern void buddy_destroy(struct buddy *b);
+
+extern int buddy_alloc(struct buddy *b, unsigned int order);
+extern bool buddy_reserve(struct buddy *b, unsigned int index, unsigned int order);
+extern void buddy_free(struct buddy *b, unsigned int index, unsigned int order);
+extern void buddy_reset(struct buddy *b);
+
+#endif /* __BUDDY_H */