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>

2 files changed, 84 insertions, 1 deletions

diff --git a/core/test/Makefile.check b/core/test/Makefile.check
index 869eafc..3554050 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 0000000..80de917
--- /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;
+}