Initial commit.

13 files changed, 1907 insertions, 0 deletions

diff --git a/test/test_avltree.c b/test/test_avltree.c
new file mode 100644
index 0000000..f8fcec8
--- /dev/null
+++ b/test/test_avltree.c
@@ -0,0 +1,132 @@
+/*
+ * Copyright (c) 2010, 2011 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "../hash.h"
+#include "../macros.h"
+#include "../avltree.h"
+
+#define SIZE 28
+
+struct obj {
+    struct avltree_node node;
+    int id;
+};
+
+static inline int obj_cmp_lookup(int id, struct avltree_node *node)
+{
+    struct obj *obj;
+
+    obj = avltree_entry(node, struct obj, node);
+    return id - obj->id;
+}
+
+static void print_subtree(struct avltree_node *node, int level)
+{
+    struct obj *obj;
+    char balance;
+    int i;
+
+    if (node == NULL)
+        return;
+
+    print_subtree(node->children[AVLTREE_RIGHT], level + 1);
+
+    for (i = level; i > 0; i--)
+        putchar(' ');
+
+    obj = avltree_entry(node, struct obj, node);
+
+    switch(node->parent & AVLTREE_BALANCE_MASK) {
+    case 0:
+        balance = '-';
+        break;
+    case 1:
+        balance = '0';
+        break;
+    case 2:
+        balance = '+';
+        break;
+    default:
+        printf("invalid balance for node %d\n", obj->id);
+        return;
+    }
+
+    printf("%d:%c\n", obj->id, balance);
+
+    print_subtree(node->children[AVLTREE_LEFT], level + 1);
+}
+
+static void print_tree(struct avltree *tree)
+{
+    print_subtree(tree->root, 0);
+}
+
+static int get_id(int i)
+{
+    return hash_int32(i, 6);
+}
+
+int main(int argc, char *argv[])
+{
+    struct avltree tree;
+    struct avltree_node *node, *tmp;
+    struct obj *obj;
+    unsigned long slot;
+    int i, id;
+
+    (void)argc;
+    (void)argv;
+
+    avltree_init(&tree);
+
+    for (i = 0; i < SIZE; i++) {
+        id = get_id(i);
+        node = avltree_lookup_slot(&tree, id, obj_cmp_lookup, slot);
+
+        if (node != NULL)
+            continue;
+
+        obj = malloc(sizeof(*obj));
+        obj->id = id;
+        printf("%d ", obj->id);
+        avltree_insert_slot(&tree, slot, &obj->node);
+    }
+
+    printf("\n");
+    print_tree(&tree);
+
+    avltree_for_each_remove(&tree, node, tmp) {
+        obj = avltree_entry(node, struct obj, node);
+        printf("freeing obj %d\n", obj->id);
+        free(obj);
+    }
+
+    return 0;
+}
diff --git a/test/test_mem.c b/test/test_mem.c
new file mode 100644
index 0000000..f0aac95
--- /dev/null
+++ b/test/test_mem.c
@@ -0,0 +1,56 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <string.h>
+
+#include "../mem.h"
+#include "../macros.h"
+
+#define STRING      "This is a test string."
+#define STRING_SIZE (STRLEN(STRING) + 1)
+
+int main(int argc, char *argv[])
+{
+    char *s;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    s = mem_alloc(STRING_SIZE);
+
+    if (s == NULL) {
+        fprintf(stderr, "unable to allocate memory\n");
+        return 1;
+    }
+
+    strcpy(s, STRING);
+    printf("string: '%s'\n", s);
+    mem_free(s, STRING_SIZE);
+
+    return 0;
+}
diff --git a/test/test_mem_cache.c b/test/test_mem_cache.c
new file mode 100644
index 0000000..9ca53f4
--- /dev/null
+++ b/test/test_mem_cache.c
@@ -0,0 +1,142 @@
+/*
+ * Copyright (c) 2010, 2011 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <assert.h>
+#include <stddef.h>
+#include <pthread.h>
+
+#include <stdio.h>
+
+#include "../cpu.h"
+#include "../mem.c"
+#include "../error.c"
+#include "../avltree.c"
+
+#ifdef CONFIG_MEM_USE_PHYS
+#include "../phys.c"
+#endif /* CONFIG_MEM_USE_PHYS */
+
+#define NTHREADS    4
+#define TEST_TIME   60
+#define OBJSPERLOOP 100
+
+struct result {
+    unsigned long allocs;
+    unsigned long frees;
+} __aligned(CPU_L1_SIZE);
+
+struct obj {
+    unsigned long nr_refs;
+    char name[16];
+};
+
+static void obj_ctor(void *ptr)
+{
+    struct obj *obj;
+
+    obj = ptr;
+    obj->nr_refs = 0;
+}
+
+static struct mem_cache *obj_cache;
+static volatile int work;
+static struct result results[NTHREADS];
+
+static void * run(void *arg)
+{
+    struct obj *objs[OBJSPERLOOP];
+    struct result *result;
+    int i, id;
+
+    result = arg;
+    id = result - results;
+
+    mem_print("started");
+
+    while (work) {
+        for (i = 0; i < OBJSPERLOOP; i++) {
+            objs[i] = mem_cache_alloc(obj_cache);
+            result->allocs++;
+        }
+
+        for (i = 0; i < OBJSPERLOOP; i++) {
+            mem_cache_free(obj_cache, objs[i]);
+            result->frees++;
+        }
+    }
+
+    return NULL;
+}
+
+int main(int argc, char *argv[])
+{
+    pthread_t threads[NTHREADS];
+    unsigned long ops;
+    int i;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    mem_info();
+
+    mem_print("Selected cache line size: %u", CPU_L1_SIZE);
+    mem_print("sizeof(pthread_mutex_t): %zu", sizeof(pthread_mutex_t));
+    mem_print("sizeof(struct mem_cpu_pool): %zu", sizeof(struct mem_cpu_pool));
+    mem_print("sizeof(union mem_bufctl): %zu", sizeof(union mem_bufctl));
+    mem_print("sizeof(struct mem_buftag): %zu", sizeof(struct mem_buftag));
+    mem_print("sizeof(struct mem_slab): %zu", sizeof(struct mem_slab));
+    mem_print("sizeof(struct mem_cache): %zu", sizeof(struct mem_cache));
+    mem_print("sizeof(struct obj): %zu", sizeof(struct obj));
+
+    obj_cache = mem_cache_create("obj", sizeof(struct obj), 0,
+                                 obj_ctor, NULL, 0);
+
+    memset(results, 0, sizeof(results));
+    work = 1;
+
+    for (i = 0; i < NTHREADS; i++)
+        pthread_create(&threads[i], NULL, run, &results[i]);
+
+    sleep(TEST_TIME);
+    work = 0;
+
+    for (i = 0; i < NTHREADS; i++)
+        pthread_join(threads[i], NULL);
+
+    ops = 0;
+
+    for (i = 0; i < NTHREADS; i++)
+        ops += results[i].allocs + results[i].frees;
+
+    mem_info();
+    mem_cache_info(obj_cache);
+    mem_print("total: %lu ops in %d secs", ops, TEST_TIME);
+
+    mem_cache_destroy(obj_cache);
+
+    return 0;
+}
diff --git a/test/test_mem_cache_double_free.c b/test/test_mem_cache_double_free.c
new file mode 100644
index 0000000..472c422
--- /dev/null
+++ b/test/test_mem_cache_double_free.c
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+
+#include "../mem.h"
+#include "../macros.h"
+
+struct obj {
+    unsigned long nr_refs;
+    char name[16];
+};
+
+static void obj_ctor(void *ptr)
+{
+    struct obj *obj;
+
+    obj = ptr;
+    obj->nr_refs = 0;
+}
+
+int main(int argc, char *argv[])
+{
+    struct mem_cache *obj_cache;
+    struct obj *obj;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    obj_cache = mem_cache_create("obj", sizeof(struct obj), 0,
+                                 obj_ctor, NULL, MEM_CACHE_VERIFY);
+
+    printf("trying normal alloc+free:\n");
+    obj = mem_cache_alloc(obj_cache);
+    mem_cache_free(obj_cache, obj);
+
+    mem_cache_info(obj_cache);
+
+    printf("trying alloc+double free:\n");
+    obj = mem_cache_alloc(obj_cache);
+    mem_cache_free(obj_cache, obj);
+    mem_cache_free(obj_cache, obj);
+
+    printf("done\n");
+
+    return 0;
+}
diff --git a/test/test_mem_cache_invalid_free.c b/test/test_mem_cache_invalid_free.c
new file mode 100644
index 0000000..85f660a
--- /dev/null
+++ b/test/test_mem_cache_invalid_free.c
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+
+#include "../mem.h"
+#include "../macros.h"
+
+struct obj {
+    unsigned long nr_refs;
+    char name[16];
+};
+
+static void obj_ctor(void *ptr)
+{
+    struct obj *obj;
+
+    obj = ptr;
+    obj->nr_refs = 0;
+}
+
+int main(int argc, char *argv[])
+{
+    struct mem_cache *obj_cache;
+    struct obj *obj;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    obj_cache = mem_cache_create("obj", sizeof(struct obj), 0,
+                                 obj_ctor, NULL, MEM_CACHE_VERIFY);
+
+    printf("trying normal alloc+free:\n");
+    obj = mem_cache_alloc(obj_cache);
+    mem_cache_free(obj_cache, obj);
+
+    mem_cache_info(obj_cache);
+
+    printf("trying alloc+invalid free:\n");
+    obj = mem_cache_alloc(obj_cache);
+    mem_cache_free(obj_cache, (char *)obj + 1);
+
+    printf("done\n");
+
+    return 0;
+}
diff --git a/test/test_mem_cache_write_beyond.c b/test/test_mem_cache_write_beyond.c
new file mode 100644
index 0000000..1519d43
--- /dev/null
+++ b/test/test_mem_cache_write_beyond.c
@@ -0,0 +1,87 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+
+#include "../mem.h"
+#include "../macros.h"
+
+struct obj {
+    unsigned long nr_refs;
+    char name[16];
+};
+
+static void obj_ctor(void *ptr)
+{
+    struct obj *obj;
+
+    obj = ptr;
+    obj->nr_refs = 0;
+}
+
+static void obj_print(struct obj *obj, size_t size)
+{
+    unsigned char *ptr, *end;
+
+    printf("buffer content: ");
+
+    for (ptr = (unsigned char *)obj, end = ptr + size; ptr < end; ptr++)
+        printf("%02x", *ptr);
+
+    printf("\n");
+}
+
+int main(int argc, char *argv[])
+{
+    struct mem_cache *obj_cache;
+    struct obj *obj;
+    size_t buf_size;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    obj_cache = mem_cache_create("obj", sizeof(struct obj), 0,
+                                 obj_ctor, NULL, MEM_CACHE_VERIFY);
+    mem_cache_info(obj_cache);
+
+    printf("doing normal alloc:\n");
+    obj = mem_cache_alloc(obj_cache);
+
+    printf("writing beyond object boundary:\n");
+    strcpy(obj->name, "invalid write 000000");
+    buf_size = P2ROUND(sizeof(*obj), 8);
+    obj_print(obj, buf_size + (sizeof(unsigned long) * 2));
+
+    printf("doing normal free:\n");
+    mem_cache_free(obj_cache, obj);
+
+    printf("done\n");
+
+    return 0;
+}
diff --git a/test/test_mem_cache_write_buftag.c b/test/test_mem_cache_write_buftag.c
new file mode 100644
index 0000000..88ba716
--- /dev/null
+++ b/test/test_mem_cache_write_buftag.c
@@ -0,0 +1,89 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+
+#include "../mem.h"
+#include "../macros.h"
+
+struct obj {
+    unsigned long nr_refs;
+    char name[16];
+};
+
+static void obj_ctor(void *ptr)
+{
+    struct obj *obj;
+
+    obj = ptr;
+    obj->nr_refs = 0;
+}
+
+static void obj_print(struct obj *obj, size_t size)
+{
+    unsigned char *ptr, *end;
+
+    printf("buffer content: ");
+
+    for (ptr = (unsigned char *)obj, end = ptr + size; ptr < end; ptr++)
+        printf("%02x", *ptr);
+
+    printf("\n");
+}
+
+int main(int argc, char *argv[])
+{
+    struct mem_cache *obj_cache;
+    struct obj *obj;
+    unsigned long *ptr;
+    size_t buf_size;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    obj_cache = mem_cache_create("obj", sizeof(struct obj), 0,
+                                 obj_ctor, NULL, MEM_CACHE_VERIFY);
+    mem_cache_info(obj_cache);
+
+    printf("doing normal alloc:\n");
+    obj = mem_cache_alloc(obj_cache);
+
+    printf("writing garbage in buftag:\n");
+    buf_size = P2ROUND(sizeof(*obj), 8);
+    ptr = (void *)obj + buf_size + sizeof(unsigned long);
+    *ptr = 0xed0000a1;
+    obj_print(obj, buf_size + (sizeof(unsigned long) * 2));
+
+    printf("doing normal free:\n");
+    mem_cache_free(obj_cache, obj);
+
+    printf("done\n");
+
+    return 0;
+}
diff --git a/test/test_mem_cache_write_free.c b/test/test_mem_cache_write_free.c
new file mode 100644
index 0000000..0850faf
--- /dev/null
+++ b/test/test_mem_cache_write_free.c
@@ -0,0 +1,103 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#define _GNU_SOURCE
+#include <sched.h>
+
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+
+#include "../mem.h"
+#include "../macros.h"
+
+struct obj {
+    unsigned long nr_refs;
+    char name[16];
+};
+
+static void obj_ctor(void *ptr)
+{
+    struct obj *obj;
+
+    obj = ptr;
+    obj->nr_refs = 0;
+}
+
+static void obj_print(struct obj *obj)
+{
+    unsigned char *ptr, *end;
+
+    printf("buffer content: ");
+
+    for (ptr = (unsigned char *)obj, end = ptr + sizeof(*obj);
+         ptr < end;
+         ptr++)
+        printf("%02x", *ptr);
+
+    printf("\n");
+}
+
+int main(int argc, char *argv[])
+{
+    struct mem_cache *obj_cache;
+    struct obj *obj;
+    cpu_set_t cpu_set;
+
+    (void)argc;
+    (void)argv;
+
+    printf("binding to CPU 0\n");
+    CPU_ZERO(&cpu_set);
+    CPU_SET(0, &cpu_set);
+    sched_setaffinity(0, sizeof(cpu_set), &cpu_set);
+
+    mem_init();
+
+    obj_cache = mem_cache_create("obj", sizeof(struct obj), 0,
+                                 obj_ctor, NULL, MEM_CACHE_VERIFY);
+
+    printf("doing normal alloc+free:\n");
+    obj = mem_cache_alloc(obj_cache);
+    mem_cache_free(obj_cache, obj);
+
+    mem_cache_info(obj_cache);
+
+    obj_print(obj);
+
+    printf("doing write on free object:\n");
+    memset((void *)obj + 3, 0x89, 5);
+
+    obj_print(obj);
+
+    printf("trying normal alloc+free on same CPU (should fail):\n");
+
+    obj = mem_cache_alloc(obj_cache);
+    mem_cache_free(obj_cache, obj);
+
+    printf("done\n");
+
+    return 0;
+}
diff --git a/test/test_mem_offbyone.c b/test/test_mem_offbyone.c
new file mode 100644
index 0000000..084bdb5
--- /dev/null
+++ b/test/test_mem_offbyone.c
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <string.h>
+
+#include "../mem.h"
+
+#define BUFSIZE 200
+
+int main(int argc, char *argv[])
+{
+    char *s;
+
+    (void)argc;
+    (void)argv;
+
+    mem_init();
+
+    printf("allocating memory:\n");
+    s = mem_alloc(BUFSIZE);
+
+    if (s == NULL) {
+        fprintf(stderr, "unable to allocate memory\n");
+        return 1;
+    }
+
+    printf("writing beyond end of buffer:\n");
+    memset(s, 'a', BUFSIZE + 1);
+
+    printf("releasing buffer, should fail if CONFIG_MEM_VERIFY defined\n");
+    mem_free(s, BUFSIZE);
+
+    return 0;
+}
diff --git a/test/test_phys.c b/test/test_phys.c
new file mode 100644
index 0000000..fe94b43
--- /dev/null
+++ b/test/test_phys.c
@@ -0,0 +1,63 @@
+/*
+ * Copyright (c) 2011 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stddef.h>
+#include <string.h>
+
+#include "../phys.c"
+
+int main(int argc, char *argv[])
+{
+    struct phys_page *page;
+
+    (void)argc;
+    (void)argv;
+
+    phys_init();
+
+    phys_info();
+    printf("sizeof(struct phys_cpu_pool) = %zu\n",
+           sizeof(struct phys_cpu_pool));
+    printf("sizeof(struct phys_free_list) = %zu\n",
+           sizeof(struct phys_free_list));
+    printf("sizeof(struct phys_page): %zu\n", sizeof(struct phys_page));
+    printf("sizeof(struct phys_seg): %zu\n", sizeof(struct phys_seg));
+    printf("allocating one page\n");
+    page = phys_alloc_pages(1);
+
+    if (page == NULL) {
+        fprintf(stderr, "unable to allocate memory\n");
+        return 1;
+    }
+
+    phys_info();
+
+    printf("freeing the allocated page\n");
+    phys_free_pages(page, 1);
+    phys_info();
+
+    return 0;
+}
diff --git a/test/test_rbtree.c b/test/test_rbtree.c
new file mode 100644
index 0000000..e379fb8
--- /dev/null
+++ b/test/test_rbtree.c
@@ -0,0 +1,117 @@
+/*
+ * Copyright (c) 2010, 2011 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "../hash.h"
+#include "../macros.h"
+#include "../rbtree.h"
+
+#define SIZE 28
+
+struct obj {
+    struct rbtree_node node;
+    int id;
+};
+
+static inline int obj_cmp_lookup(int id, struct rbtree_node *node)
+{
+    struct obj *obj;
+
+    obj = rbtree_entry(node, struct obj, node);
+    return id - obj->id;
+}
+
+static void print_subtree(struct rbtree_node *node, int level)
+{
+    struct obj *obj;
+    char color;
+    int i;
+
+    if (node == NULL)
+        return;
+
+    print_subtree(node->children[RBTREE_RIGHT], level + 1);
+
+    for (i = level; i > 0; i--)
+        putchar(' ');
+
+    obj = rbtree_entry(node, struct obj, node);
+    color = (node->parent & RBTREE_COLOR_MASK) ? 'b' : 'r';
+    printf("%d:%c\n", obj->id, color);
+
+    print_subtree(node->children[RBTREE_LEFT], level + 1);
+}
+
+static void print_tree(struct rbtree *tree)
+{
+    print_subtree(tree->root, 0);
+}
+
+static int get_id(int i)
+{
+    return hash_int32(i, 6);
+}
+
+int main(int argc, char *argv[])
+{
+    struct rbtree tree;
+    struct rbtree_node *node, *tmp;
+    struct obj *obj;
+    unsigned long slot;
+    int i, id;
+
+    (void)argc;
+    (void)argv;
+
+    rbtree_init(&tree);
+
+    for (i = 0; i < SIZE; i++) {
+        id = get_id(i);
+        node = rbtree_lookup_slot(&tree, id, obj_cmp_lookup, slot);
+
+        if (node != NULL)
+            continue;
+
+        obj = malloc(sizeof(*obj));
+        obj->id = id;
+        printf("%d ", obj->id);
+        rbtree_insert_slot(&tree, slot, &obj->node);
+    }
+
+    printf("\n");
+    print_tree(&tree);
+
+    rbtree_for_each_remove(&tree, node, tmp) {
+        obj = rbtree_entry(node, struct obj, node);
+        printf("freeing obj %d\n", obj->id);
+        free(obj);
+    }
+
+    return 0;
+}
diff --git a/test/test_rdatree.c b/test/test_rdatree.c
new file mode 100644
index 0000000..4ecd64d
--- /dev/null
+++ b/test/test_rdatree.c
@@ -0,0 +1,619 @@
+/*
+ * Copyright (c) 2011 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <stdarg.h>
+
+#include "../macros.h"
+#include "../rdatree.c"
+
+#define TITLE(str) printf("%s: %s\n", __func__, str)
+
+#if RDATREE_RADIX < 6
+#define BM_FORMAT "%lx"
+#elif RDATREE_RADIX == 6 /* RDATREE_RADIX < 6 */
+#ifdef __LP64__
+#define BM_FORMAT "%lx"
+#else /* __LP64__ */
+#define BM_FORMAT "%llx"
+#endif /* __LP64__ */
+#endif /* RDATREE_RADIX < 6 */
+
+struct obj {
+    unsigned long id;
+};
+
+static struct obj * obj_create(unsigned long id)
+{
+    struct obj *obj;
+
+    obj = malloc(sizeof(*obj));
+    assert(obj != NULL);
+    obj->id = id;
+    return obj;
+}
+
+static void obj_destroy(struct obj *obj)
+{
+    free(obj);
+}
+
+static void print_subtree(struct rdatree_node *node, int height, size_t index,
+                          size_t level);
+
+static void print_value(void *ptr, size_t index, size_t level)
+{
+    struct obj *obj;
+    int i;
+
+    if (ptr == NULL)
+        return;
+
+    obj = ptr;
+
+    for (i = level; i > 0; i--)
+        putchar(' ');
+
+    printf("%zu:%lu\n", index, obj->id);
+}
+
+static void print_values(struct rdatree_node *node, size_t index, size_t level)
+{
+    size_t i;
+
+    for (i = level; i > 0; i--)
+        putchar(' ');
+
+    printf("%zu:n (bm: " BM_FORMAT ")\n", index, node->alloc_bm);
+
+    for (i = 0; i < ARRAY_SIZE(node->slots); i++)
+        print_value(node->slots[i], i, level + 1);
+}
+
+static void print_node(struct rdatree_node *node, int height, size_t index,
+                       size_t level)
+{
+    size_t i;
+
+    for (i = level; i > 0; i--)
+        putchar(' ');
+
+    printf("%zu:n (bm: " BM_FORMAT ")\n", index, node->alloc_bm);
+
+    for (i = 0; i < ARRAY_SIZE(node->slots); i++)
+        print_subtree(node->slots[i], height - 1, i, level + 1);
+}
+
+static void print_subtree(struct rdatree_node *node, int height, size_t index,
+                          size_t level)
+{
+    if (node == NULL)
+        return;
+
+    if (height == 1)
+        print_values(node, index, level);
+    else
+        print_node(node, height, index, level);
+}
+
+static void print_tree(struct rdatree *tree)
+{
+    if (tree->height == 0)
+        print_value(tree->root, 0, 0);
+    else
+        print_subtree(tree->root, tree->height, 0, 0);
+}
+
+static void destroy_tree(struct rdatree *tree)
+{
+    struct rdatree_iter iter;
+    struct obj *obj;
+
+    rdatree_for_each(tree, &iter, obj)
+        obj_destroy(obj);
+
+    rdatree_remove_all(tree);
+}
+
+static void test_1(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    int error;
+
+    TITLE("insert 0");
+
+    rdatree_init(&tree);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    print_tree(&tree);
+    destroy_tree(&tree);
+}
+
+static void test_2(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    int error;
+
+    TITLE("insert 1");
+
+    rdatree_init(&tree);
+    obj = obj_create(1);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    print_tree(&tree);
+    destroy_tree(&tree);
+}
+
+static void test_3(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    int error;
+
+    TITLE("insert 0 and 1");
+
+    rdatree_init(&tree);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    obj = obj_create(1);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    print_tree(&tree);
+    destroy_tree(&tree);
+}
+
+static void test_4(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    int error;
+
+    TITLE("insert 1 and 0");
+
+    rdatree_init(&tree);
+    obj = obj_create(1);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    print_tree(&tree);
+    destroy_tree(&tree);
+}
+
+static void test_5(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    int error;
+
+    TITLE("insert 0 and 4096");
+
+    rdatree_init(&tree);
+    obj = obj_create(4096);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    print_tree(&tree);
+    destroy_tree(&tree);
+}
+
+static void test_6(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    int error;
+
+    TITLE("insert 4096 and 0");
+
+    rdatree_init(&tree);
+    obj = obj_create(4096);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    print_tree(&tree);
+    destroy_tree(&tree);
+}
+
+static void test_7(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    void *ptr;
+    int error;
+
+    TITLE("insert and remove 0");
+
+    rdatree_init(&tree);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    ptr = rdatree_remove(&tree, obj->id);
+    assert(ptr == obj);
+    obj_destroy(obj);
+    print_tree(&tree);
+}
+
+static void test_8(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    void *ptr;
+    int error;
+
+    TITLE("insert and remove 4096");
+
+    rdatree_init(&tree);
+    obj = obj_create(4096);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    ptr = rdatree_remove(&tree, obj->id);
+    assert(ptr == obj);
+    obj_destroy(obj);
+    print_tree(&tree);
+}
+
+static void test_9(void)
+{
+    struct rdatree tree;
+    struct obj *obj1, *obj2;
+    void *ptr;
+    int error;
+
+    TITLE("insert 0 and 4096 and remove in reverse order");
+
+    rdatree_init(&tree);
+    obj1 = obj_create(0);
+    error = rdatree_insert(&tree, obj1->id, obj1);
+    assert(!error);
+    obj2 = obj_create(4096);
+    error = rdatree_insert(&tree, obj2->id, obj2);
+    assert(!error);
+    ptr = rdatree_remove(&tree, obj2->id);
+    assert(ptr == obj2);
+    obj_destroy(obj2);
+    ptr = rdatree_remove(&tree, obj1->id);
+    assert(ptr == obj1);
+    obj_destroy(obj1);
+    print_tree(&tree);
+}
+
+static void test_10(void)
+{
+    struct rdatree tree;
+    struct obj *obj1, *obj2;
+    void *ptr;
+    int error;
+
+    TITLE("insert 0 and 4096 and remove in same order");
+
+    rdatree_init(&tree);
+    obj1 = obj_create(0);
+    error = rdatree_insert(&tree, obj1->id, obj1);
+    assert(!error);
+    obj2 = obj_create(4096);
+    error = rdatree_insert(&tree, obj2->id, obj2);
+    assert(!error);
+    ptr = rdatree_remove(&tree, obj1->id);
+    assert(ptr == obj1);
+    obj_destroy(obj1);
+    ptr = rdatree_remove(&tree, obj2->id);
+    assert(ptr == obj2);
+    obj_destroy(obj2);
+    print_tree(&tree);
+}
+
+static void test_11(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert [0..4096] and remove in reverse order");
+
+    rdatree_init(&tree);
+
+    for (i = 0; i <= 4096; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    for (i = 4096; i <= 4096; i--) {
+        obj = rdatree_remove(&tree, i);
+        obj_destroy(obj);
+    }
+
+    print_tree(&tree);
+}
+
+static void test_12(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert [0..4096] and remove in same order");
+
+    rdatree_init(&tree);
+
+    for (i = 0; i <= 4096; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    for (i = 0; i <= 4096; i++) {
+        obj = rdatree_remove(&tree, i);
+        obj_destroy(obj);
+    }
+
+    print_tree(&tree);
+}
+
+static void test_13(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("allocate");
+
+    rdatree_init(&tree);
+    obj = obj_create(0);
+    error = rdatree_insert_alloc(&tree, obj, &obj->id);
+    assert(!error);
+    assert(obj->id == 0);
+    print_tree(&tree);
+    i = obj->id;
+    obj = rdatree_lookup(&tree, i);
+    assert(obj->id == i);
+    destroy_tree(&tree);
+}
+
+static void test_14(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert 0, allocate");
+
+    rdatree_init(&tree);
+    obj = obj_create(0);
+    error = rdatree_insert(&tree, obj->id, obj);
+    assert(!error);
+    obj = obj_create(0);
+    error = rdatree_insert_alloc(&tree, obj, &obj->id);
+    assert(!error);
+    assert(obj->id == 1);
+    print_tree(&tree);
+    i = obj->id;
+    obj = rdatree_lookup(&tree, i);
+    assert(obj->id == i);
+    destroy_tree(&tree);
+}
+
+static void test_15(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert [0..4095], remove 0, allocate");
+
+    rdatree_init(&tree);
+
+    for (i = 0; i < 4096; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    obj = rdatree_remove(&tree, 0);
+    assert(obj->id == 0);
+    error = rdatree_insert_alloc(&tree, obj, &obj->id);
+    assert(!error);
+    assert(obj->id == 0);
+    destroy_tree(&tree);
+}
+
+static void test_16(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert [0..4095], remove 1, allocate");
+
+    rdatree_init(&tree);
+
+    for (i = 0; i < 4096; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    obj = rdatree_remove(&tree, 1);
+    assert(obj->id == 1);
+    error = rdatree_insert_alloc(&tree, obj, &obj->id);
+    assert(!error);
+    assert(obj->id == 1);
+    destroy_tree(&tree);
+}
+
+static void test_17(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert [0..63] and [128..191], allocate x65");
+
+    rdatree_init(&tree);
+
+    for (i = 0; i < 64; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    for (i = 128; i < 192; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    for (i = 64; i < 128; i++) {
+        obj = obj_create(0);
+        error = rdatree_insert_alloc(&tree, obj, &obj->id);
+        assert(!error);
+        assert(obj->id == i);
+    }
+
+    obj = obj_create(0);
+    error = rdatree_insert_alloc(&tree, obj, &obj->id);
+    assert(!error);
+    assert(obj->id == 192);
+    destroy_tree(&tree);
+}
+
+static void test_18(void)
+{
+    struct rdatree tree;
+    struct obj *obj;
+    unsigned long i;
+    int error;
+
+    TITLE("insert [0..4095], allocate");
+
+    rdatree_init(&tree);
+
+    for (i = 0; i < 4096; i++) {
+        obj = obj_create(i);
+        error = rdatree_insert(&tree, i, obj);
+        assert(!error);
+    }
+
+    obj = obj_create(0);
+    error = rdatree_insert_alloc(&tree, obj, &obj->id);
+    assert(!error);
+    assert(obj->id == 4096);
+    destroy_tree(&tree);
+}
+
+static void test_19(void)
+{
+    struct rdatree tree;
+    struct obj *obj1, *obj2, *tmp;
+    void **slot;
+    int error;
+
+    TITLE("insert 0, replace");
+
+    rdatree_init(&tree);
+    obj1 = obj_create(0);
+    error = rdatree_insert(&tree, 0, obj1);
+    assert(!error);
+    slot = rdatree_lookup_slot(&tree, 0);
+    assert(slot != NULL);
+    obj2 = obj_create(0);
+    tmp = rdatree_replace_slot(slot, obj2);
+    assert(obj1 == tmp);
+    obj_destroy(obj1);
+    print_tree(&tree);
+    tmp = rdatree_lookup(&tree, 0);
+    assert(obj2 == tmp);
+    destroy_tree(&tree);
+}
+
+static void test_20(void)
+{
+    struct rdatree tree;
+    struct obj *obj1, *obj2, *tmp;
+    void **slot;
+    int error;
+
+    TITLE("insert 4096, replace");
+
+    rdatree_init(&tree);
+    obj1 = obj_create(4096);
+    error = rdatree_insert(&tree, 4096, obj1);
+    assert(!error);
+    slot = rdatree_lookup_slot(&tree, 4096);
+    assert(slot != NULL);
+    obj2 = obj_create(4096);
+    tmp = rdatree_replace_slot(slot, obj2);
+    assert(obj1 == tmp);
+    obj_destroy(obj1);
+    print_tree(&tree);
+    tmp = rdatree_lookup(&tree, 4096);
+    assert(obj2 == tmp);
+    destroy_tree(&tree);
+}
+
+int main(int argc, char *argv[])
+{
+    (void)argc;
+    (void)argv;
+
+    test_1();
+    test_2();
+    test_3();
+    test_4();
+    test_5();
+    test_6();
+    test_7();
+    test_8();
+    test_9();
+    test_10();
+    test_11();
+    test_12();
+    test_13();
+    test_14();
+    test_15();
+    test_16();
+    test_17();
+    test_18();
+    test_19();
+    test_20();
+    return 0;
+}
diff --git a/test/test_xprintf.c b/test/test_xprintf.c
new file mode 100644
index 0000000..84a4176
--- /dev/null
+++ b/test/test_xprintf.c
@@ -0,0 +1,297 @@
+/*
+ * Copyright (c) 2010 Richard Braun.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <assert.h>
+#include <stdarg.h>
+#include <string.h>
+
+#include "../macros.h"
+#include "../xprintf.h"
+
+#define TEST_PRINTF(format, ...)                        \
+MACRO_BEGIN                                             \
+    char stra[256], strb[256];                          \
+    int la, lb;                                         \
+    la = snprintf(stra, 256, format, ## __VA_ARGS__);   \
+    printf(" printf: %s", stra);                        \
+    lb = xsnprintf(strb, 256, format, ## __VA_ARGS__);  \
+    xprintf("xprintf: %s", stra);                       \
+    assert(la == lb);                                   \
+    assert(strcmp(stra, strb) == 0);                    \
+MACRO_END
+
+int main(int argc, char *argv[])
+{
+    (void)argc;
+    (void)argv;
+
+#define FORMAT "%c"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 'a');
+#undef FORMAT
+
+#define FORMAT "%8c"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 'a');
+#undef FORMAT
+
+#define FORMAT "%-8c"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 'a');
+#undef FORMAT
+
+#define FORMAT "%.s"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "12345");
+#undef FORMAT
+
+#define FORMAT "%.3s"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "12345");
+#undef FORMAT
+
+#define FORMAT "%4.3s"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "12345");
+#undef FORMAT
+
+#define FORMAT "%-4.3s"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "12345");
+#undef FORMAT
+
+#define FORMAT "%3.4s"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "12345");
+#undef FORMAT
+
+#define FORMAT "%-3.4s"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "12345");
+#undef FORMAT
+
+#define FORMAT "%#o"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%#x"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%#X"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%08d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%-8d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%-08d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%0-8d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "% d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%+d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%+ d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%12d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%*d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 12, 123);
+#undef FORMAT
+
+#define FORMAT "%.12d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%.012d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%.*d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 12, 123);
+#undef FORMAT
+
+#define FORMAT "%.d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%.*d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -12, 123);
+#undef FORMAT
+
+#define FORMAT "%.4d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%5.4d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%4.5d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0);
+#undef FORMAT
+
+#define FORMAT "%.0d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0);
+#undef FORMAT
+
+#define FORMAT "%.0o"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0);
+#undef FORMAT
+
+#define FORMAT "%.0x"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0);
+#undef FORMAT
+
+#define FORMAT "%1.0d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0);
+#undef FORMAT
+
+#define FORMAT "%08.0d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%08d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%08d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%8d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%8d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%.8d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%.80d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%-80d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%80d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%80.40d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%-+80.40d"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%+x"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, -123);
+#undef FORMAT
+
+#define FORMAT "%#x"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%#o"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 123);
+#undef FORMAT
+
+#define FORMAT "%p"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, "123");
+#undef FORMAT
+
+#define FORMAT "%#lx"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0xdeadbeefL);
+#undef FORMAT
+
+#define FORMAT "%zd"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, (size_t)-123);
+#undef FORMAT
+
+#define FORMAT "%#llx"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0xdeadbeefbadcafeLL);
+#undef FORMAT
+
+#define FORMAT "%llo"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT, 0xffffffffffffffffLL);
+#undef FORMAT
+
+#define FORMAT "%%"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT);
+#undef FORMAT
+
+#define FORMAT "%y"
+    TEST_PRINTF("%s: '" FORMAT "'\n", FORMAT);
+#undef FORMAT
+
+    char stra[10], strb[10];
+    int la, lb;
+    la = snprintf(stra, sizeof(stra), "%s", "123456789a");
+    printf(" printf: %s\n", stra);
+    lb = xsnprintf(strb, sizeof(strb), "%s", "123456789a");
+    xprintf("xprintf: %s\n", stra);
+    assert(la == lb);
+    assert(strncmp(stra, strb, 10) == 0);
+
+#define FORMAT "12%n3%#08x4%n5"
+    int lc, ld;
+    sprintf(stra, FORMAT, &la, 123, &lb);
+    printf(" printf: la: %d, lb: %d\n", la, lb);
+    xsprintf(strb, FORMAT, &lc, 123, &ld);
+    xprintf("xprintf: lc: %d, ld: %d\n", lc, ld);
+    assert(la == lc);
+    assert(lb == ld);
+#undef FORMAT
+
+    la = snprintf(NULL, 0, "%s", "123");
+    printf(" printf: %d\n", la);
+    lb = xsnprintf(NULL, 0, "%s", "123");
+    xprintf("xprintf: %d\n", lb);
+    assert(la == lb);
+
+    return 0;
+}