[Skiboot] [PATCH 02/60] buddy: Add a simple generic buddy allocator
Benjamin Herrenschmidt
benh at kernel.crashing.org
Thu Dec 22 14:16:10 AEDT 2016
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 at kernel.crashing.org>
---
core/Makefile.inc | 2 +-
core/buddy.c | 287 +++++++++++++++++++++++++++++++++++++++++++++++
core/test/Makefile.check | 3 +-
core/test/run-buddy.c | 67 +++++++++++
include/buddy.h | 54 +++++++++
5 files changed, 411 insertions(+), 2 deletions(-)
create mode 100644 core/buddy.c
create mode 100644 core/test/run-buddy.c
create mode 100644 include/buddy.h
diff --git a/core/Makefile.inc b/core/Makefile.inc
index 98bcb11..2167044 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 0000000..1b4fe4d
--- /dev/null
+++ b/core/buddy.c
@@ -0,0 +1,287 @@
+#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 d3dd260..abbedfb 100644
--- a/core/test/Makefile.check
+++ b/core/test/Makefile.check
@@ -16,7 +16,8 @@ CORE_TEST := core/test/run-device \
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 0000000..a2f6505
--- /dev/null
+++ b/core/test/run-buddy.c
@@ -0,0 +1,67 @@
+#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 0000000..a52f30b
--- /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_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 */
--
2.9.3
More information about the Skiboot
mailing list