Emilio G. Cota <c...@braap.org> writes:
> This will be used by atomic instruction emulation code.
If we are adding utility functions into the code base like this (which I
can see being useful) we should at least add some documentation with
example calling conventions to docs/
Have you any performance numbers comparing the efficiency of the radix
approach to a "dumb" implementation?
>
> Signed-off-by: Emilio G. Cota <c...@braap.org>
> ---
> 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 <stddef.h>
> +
> +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 <glib.h>
> +
> +#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));
> +}
--
Alex Bennée
