From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:32905) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZTfZ4-0006vP-Bk for qemu-devel@nongnu.org; Sun, 23 Aug 2015 20:24:45 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZTfZ1-0000h4-SQ for qemu-devel@nongnu.org; Sun, 23 Aug 2015 20:24:42 -0400 Received: from out4-smtp.messagingengine.com ([66.111.4.28]:49904) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZTfZ1-0000gs-Or for qemu-devel@nongnu.org; Sun, 23 Aug 2015 20:24:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id A0F9E206C9 for ; Sun, 23 Aug 2015 20:24:39 -0400 (EDT) From: "Emilio G. Cota" Date: Sun, 23 Aug 2015 20:23:44 -0400 Message-Id: <1440375847-17603-16-git-send-email-cota@braap.org> In-Reply-To: <1440375847-17603-1-git-send-email-cota@braap.org> References: <1440375847-17603-1-git-send-email-cota@braap.org> Subject: [Qemu-devel] [RFC 15/38] radix-tree: add generic lockless radix tree module List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org, mttcg@listserver.greensocs.com Cc: mark.burton@greensocs.com, a.rigo@virtualopensystems.com, guillaume.delbergue@greensocs.com, pbonzini@redhat.com, alex.bennee@linaro.org, Frederic Konrad This will be used by atomic instruction emulation code. Signed-off-by: Emilio G. Cota --- include/qemu/radix-tree.h | 29 ++++++++++++++++++ util/Makefile.objs | 2 +- util/radix-tree.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 105 insertions(+), 1 deletion(-) create mode 100644 include/qemu/radix-tree.h create mode 100644 util/radix-tree.c diff --git a/include/qemu/radix-tree.h b/include/qemu/radix-tree.h new file mode 100644 index 0000000..a4e1f97 --- /dev/null +++ b/include/qemu/radix-tree.h @@ -0,0 +1,29 @@ +#ifndef RADIX_TREE_H +#define RADIX_TREE_H + +#include + +typedef struct QemuRadixNode QemuRadixNode; +typedef struct QemuRadixTree QemuRadixTree; + +struct QemuRadixNode { + void *slots[0]; +}; + +struct QemuRadixTree { + QemuRadixNode *root; + int radix; + int max_height; +}; + +void qemu_radix_tree_init(QemuRadixTree *tree, int bits, int radix); +void *qemu_radix_tree_find_alloc(QemuRadixTree *tree, unsigned long index, + void *(*create)(unsigned long), + void (*delete)(void *)); + +static inline void *qemu_radix_tree_find(QemuRadixTree *t, unsigned long index) +{ + return qemu_radix_tree_find_alloc(t, index, NULL, NULL); +} + +#endif /* RADIX_TREE_H */ diff --git a/util/Makefile.objs b/util/Makefile.objs index 114d657..6b18d3d 100644 --- a/util/Makefile.objs +++ b/util/Makefile.objs @@ -1,4 +1,4 @@ -util-obj-y = osdep.o cutils.o unicode.o qemu-timer-common.o +util-obj-y = osdep.o cutils.o unicode.o qemu-timer-common.o radix-tree.o util-obj-$(CONFIG_WIN32) += oslib-win32.o qemu-thread-win32.o event_notifier-win32.o util-obj-$(CONFIG_POSIX) += oslib-posix.o qemu-thread-posix.o event_notifier-posix.o qemu-openpty.o util-obj-y += envlist.o path.o module.o diff --git a/util/radix-tree.c b/util/radix-tree.c new file mode 100644 index 0000000..69eff29 --- /dev/null +++ b/util/radix-tree.c @@ -0,0 +1,75 @@ +/* + * radix-tree.c + * Non-blocking radix tree. + * + * Features: + * - Concurrent lookups and inserts. + * - No support for deletions. + * + * Conventions: + * - Height is counted starting from 0 at the bottom. + * - The index is used from left to right, i.e. MSBs are used first. This way + * nearby addresses land in nearby slots, minimising cache/TLB misses. + */ +#include + +#include "qemu/radix-tree.h" +#include "qemu/atomic.h" +#include "qemu/bitops.h" +#include "qemu/osdep.h" + +typedef struct QemuRadixNode QemuRadixNode; + +void *qemu_radix_tree_find_alloc(QemuRadixTree *tree, unsigned long index, + void *(*create)(unsigned long), + void (*delete)(void *)) +{ + QemuRadixNode *parent; + QemuRadixNode *node = tree->root; + void **slot; + int n_slots = BIT(tree->radix); + int level = tree->max_height - 1; + int shift = (level - 1) * tree->radix; + + do { + parent = node; + slot = parent->slots + ((index >> shift) & (n_slots - 1)); + node = atomic_read(slot); + smp_read_barrier_depends(); + if (node == NULL) { + void *old; + void *new; + + if (!create) { + return NULL; + } + + if (level == 1) { + node = create(index); + } else { + node = g_malloc0(sizeof(*node) + sizeof(void *) * n_slots); + } + new = node; + /* atomic_cmpxchg is type-safe so we cannot use 'node' here */ + old = atomic_cmpxchg(slot, NULL, new); + if (old) { + if (level == 1) { + delete(node); + } else { + g_free(node); + } + node = old; + } + } + shift -= tree->radix; + level--; + } while (level > 0); + return node; +} + +void qemu_radix_tree_init(QemuRadixTree *tree, int bits, int radix) +{ + tree->radix = radix; + tree->max_height = 1 + DIV_ROUND_UP(bits, radix); + tree->root = g_malloc0(sizeof(*tree->root) + sizeof(void *) * BIT(radix)); +} -- 1.9.1