Update radix-tree.[ch] from upstream Linux to gain RCU awareness.

We still leave behind features we don't need such as tagged nodes.

Other changes:
 - Allow callers to define their own node alloc routines.
 - Only allocate per-node rcu_head when using the default RCU-safe
   alloc routines.
 - Keep our own radix_tree_destroy().

In future it may also be worth getting rid of the complex and
pointless special-casing of radix-tree height==0, in which a single
data item can be stored directly in radix_tree_root. It introduces a
whole lot of special cases and complicates RCU handling. If we get rid
of it we can reclaim the 'indirect pointer' tag in bit 0 of every slot
entry.

Signed-off-by: Keir Fraser <keir@xen.org>

1 files changed, 2 insertions, 1 deletions

diff --git a/xen/include/xen/lib.h b/xen/include/xen/lib.h
index 65e4fb8bdc..0102b8ab70 100644
--- a/xen/include/xen/lib.h
+++ b/xen/include/xen/lib.h
@@ -48,7 +48,8 @@ do {                                                            \
 #define SWAP(_a, _b) \
    do { typeof(_a) _t = (_a); (_a) = (_b); (_b) = _t; } while ( 0 )
 
-#define DIV_ROUND(x, y) (((x) + (y) / 2) / (y))
+#define DIV_ROUND(n, d) (((n) + (d) / 2) / (d))
+#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
 
 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]) + __must_be_array(x))