* [resend PATCH] xen: common: rbtree: ported updates from linux tree
@ 2017-05-11 17:21 Praveen Kumar
2017-05-18 13:59 ` Jan Beulich
0 siblings, 1 reply; 5+ messages in thread
From: Praveen Kumar @ 2017-05-11 17:21 UTC (permalink / raw)
To: xen-devel
Cc: sstabellini, wei.liu2, George.Dunlap, andrew.cooper3, ian.jackson,
tim, Praveen Kumar, jbeulich
The patch contains the updated version of rbtree implementation from linux
kernel tree containing the fixes so far handled.
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
xen/common/rbtree.c | 748 +++++++++++++++++++++++++------------
xen/include/xen/compiler.h | 60 +++
xen/include/xen/rbtree.h | 120 ++++--
xen/include/xen/rbtree_augmented.h | 283 ++++++++++++++
4 files changed, 931 insertions(+), 280 deletions(-)
create mode 100644 xen/include/xen/rbtree_augmented.h
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 3328960d56..ae152c5bf2 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -2,7 +2,8 @@
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
-
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
@@ -14,286 +15,479 @@
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; If not, see <http://www.gnu.org/licenses/>.
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/lib/rbtree.c
*/
+#include <xen/rbtree_augmented.h>
#include <xen/types.h>
-#include <xen/rbtree.h>
-
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *right = node->rb_right;
- struct rb_node *parent = rb_parent(node);
- if ((node->rb_right = right->rb_left))
- rb_set_parent(right->rb_left, node);
- right->rb_left = node;
+/*
+ * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
+ *
+ * 1) A node is either red or black
+ * 2) The root is black
+ * 3) All leaves (NULL) are black
+ * 4) Both children of every red node are black
+ * 5) Every simple path from root to leaves contains the same number
+ * of black nodes.
+ *
+ * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ * consecutive red nodes in a path and every red node is therefore followed by
+ * a black. So if B is the number of black nodes on every simple path (as per
+ * 5), then the longest possible path due to 4 is 2B.
+ *
+ * We shall indicate color with case, where black nodes are uppercase and red
+ * nodes will be lowercase. Unknown color nodes shall be drawn as red within
+ * parentheses and have some accompanying text comment.
+ */
- rb_set_parent(right, parent);
+/*
+ * Notes on lockless lookups:
+ *
+ * All stores to the tree structure (rb_left and rb_right) must be done using
+ * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
+ * tree structure as seen in program order.
+ *
+ * These two requirements will allow lockless iteration of the tree -- not
+ * correct iteration mind you, tree rotations are not atomic so a lookup might
+ * miss entire subtrees.
+ *
+ * But they do guarantee that any such traversal will only see valid elements
+ * and that it will indeed complete -- does not get stuck in a loop.
+ *
+ * It also guarantees that if the lookup returns an element it is the 'correct'
+ * one. But not returning an element does _NOT_ mean it's not present.
+ *
+ * NOTE:
+ *
+ * Stores to __rb_parent_color are not important for simple lookups so those
+ * are left undone as of now. Nor did I check for loops involving parent
+ * pointers.
+ */
- if (parent)
- {
- if (node == parent->rb_left)
- parent->rb_left = right;
- else
- parent->rb_right = right;
- }
- else
- root->rb_node = right;
- rb_set_parent(node, right);
+static inline void rb_set_black(struct rb_node *rb)
+{
+ rb->__rb_parent_color |= RB_BLACK;
}
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
- struct rb_node *left = node->rb_left;
- struct rb_node *parent = rb_parent(node);
-
- if ((node->rb_left = left->rb_right))
- rb_set_parent(left->rb_right, node);
- left->rb_right = node;
-
- rb_set_parent(left, parent);
+ return (struct rb_node *)red->__rb_parent_color;
+}
- if (parent)
- {
- if (node == parent->rb_right)
- parent->rb_right = left;
- else
- parent->rb_left = left;
- }
- else
- root->rb_node = left;
- rb_set_parent(node, left);
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+ struct rb_root *root, int color)
+{
+ struct rb_node *parent = rb_parent(old);
+ new->__rb_parent_color = old->__rb_parent_color;
+ rb_set_parent_color(old, new, color);
+ __rb_change_child(old, new, parent, root);
}
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+static __always_inline void
+__rb_insert(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- struct rb_node *parent, *gparent;
+ struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
- while ((parent = rb_parent(node)) && rb_is_red(parent))
+ while (true)
{
- gparent = rb_parent(parent);
-
- if (parent == gparent->rb_left)
+ /*
+ * Loop invariant: node is red
+ *
+ * If there is a black parent, we are done.
+ * Otherwise, take some corrective action as we don't
+ * want a red root or two consecutive red nodes.
+ */
+ if (!parent)
{
+ rb_set_parent_color(node, NULL, RB_BLACK);
+ break;
+ } else if (rb_is_black(parent))
+ break;
+
+ gparent = rb_red_parent(parent);
+
+ tmp = gparent->rb_right;
+ if (parent != tmp)
+ { /* parent == gparent->rb_left */
+ if (tmp && rb_is_red(tmp))
{
- register struct rb_node *uncle = gparent->rb_right;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
+ /*
+ * Case 1 - color flips
+ *
+ * G g
+ * / \ / \
+ * p u --> P U
+ * / /
+ * n n
+ *
+ * However, since g's parent might be red, and
+ * 4) does not allow this, we need to recurse
+ * at g.
+ */
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ rb_set_parent_color(parent, gparent, RB_BLACK);
+ node = gparent;
+ parent = rb_parent(node);
+ rb_set_parent_color(node, parent, RB_RED);
+ continue;
}
- if (parent->rb_right == node)
+ tmp = parent->rb_right;
+ if (node == tmp)
{
- register struct rb_node *tmp;
- __rb_rotate_left(parent, root);
- tmp = parent;
+ /*
+ * Case 2 - left rotate at parent
+ *
+ * G G
+ * / \ / \
+ * p U --> n U
+ * \ /
+ * n p
+ *
+ * This still leaves us in violation of 4), the
+ * continuation into Case 3 will fix that.
+ */
+ tmp = node->rb_left;
+ WRITE_ONCE(parent->rb_right, tmp);
+ WRITE_ONCE(node->rb_left, parent);
+ if (tmp)
+ rb_set_parent_color(tmp, parent,
+ RB_BLACK);
+ rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
parent = node;
- node = tmp;
+ tmp = node->rb_right;
}
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_right(gparent, root);
- } else {
+ /*
+ * Case 3 - right rotate at gparent
+ *
+ * G P
+ * / \ / \
+ * p U --> n g
+ * / \
+ * n U
+ */
+ WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
+ WRITE_ONCE(parent->rb_right, gparent);
+ if (tmp)
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
+ break;
+ }
+ else
+ {
+ tmp = gparent->rb_left;
+ if (tmp && rb_is_red(tmp))
{
- register struct rb_node *uncle = gparent->rb_left;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
+ /* Case 1 - color flips */
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ rb_set_parent_color(parent, gparent, RB_BLACK);
+ node = gparent;
+ parent = rb_parent(node);
+ rb_set_parent_color(node, parent, RB_RED);
+ continue;
}
- if (parent->rb_left == node)
+ tmp = parent->rb_left;
+ if (node == tmp)
{
- register struct rb_node *tmp;
- __rb_rotate_right(parent, root);
- tmp = parent;
+ /* Case 2 - right rotate at parent */
+ tmp = node->rb_right;
+ WRITE_ONCE(parent->rb_left, tmp);
+ WRITE_ONCE(node->rb_right, parent);
+ if (tmp)
+ rb_set_parent_color(tmp, parent,
+ RB_BLACK);
+ rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
parent = node;
- node = tmp;
+ tmp = node->rb_left;
}
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_left(gparent, root);
+ /* Case 3 - left rotate at gparent */
+ WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
+ WRITE_ONCE(parent->rb_left, gparent);
+ if (tmp)
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
+ break;
}
}
-
- rb_set_black(root->rb_node);
}
-EXPORT_SYMBOL(rb_insert_color);
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
- struct rb_root *root)
+/*
+ * Inline version for rb_erase() use - we want to be able to inline
+ * and eliminate the dummy_rotate callback there
+ */
+static __always_inline void
+____rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- struct rb_node *other;
+ struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
- while ((!node || rb_is_black(node)) && node != root->rb_node)
+ while (true)
{
- if (parent->rb_left == node)
- {
- other = parent->rb_right;
- if (rb_is_red(other))
+ /*
+ * Loop invariants:
+ * - node is black (or NULL on first iteration)
+ * - node is not the root (parent is not NULL)
+ * - All leaf paths going through parent and node have a
+ * black node count that is 1 lower than other leaf paths.
+ */
+ sibling = parent->rb_right;
+ if (node != sibling)
+ { /* node == parent->rb_left */
+ if (rb_is_red(sibling))
{
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_left(parent, root);
- other = parent->rb_right;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
+ /*
+ * Case 1 - left rotate at parent
+ *
+ * P S
+ * / \ / \
+ * N s --> p Sr
+ * / \ / \
+ * Sl Sr N Sl
+ */
+ tmp1 = sibling->rb_left;
+ WRITE_ONCE(parent->rb_right, tmp1);
+ WRITE_ONCE(sibling->rb_left, parent);
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_RED);
+ augment_rotate(parent, sibling);
+ sibling = tmp1;
}
- else
+ tmp1 = sibling->rb_right;
+ if (!tmp1 || rb_is_black(tmp1))
{
- if (!other->rb_right || rb_is_black(other->rb_right))
+ tmp2 = sibling->rb_left;
+ if (!tmp2 || rb_is_black(tmp2))
{
- struct rb_node *o_left;
- if ((o_left = other->rb_left))
- rb_set_black(o_left);
- rb_set_red(other);
- __rb_rotate_right(other, root);
- other = parent->rb_right;
+ /*
+ * Case 2 - sibling color flip
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5) which
+ * can be fixed by flipping p to black
+ * if it was red, or by recursing at p.
+ * p is red when coming from Case 1.
+ */
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else
+ {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
}
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_right)
- rb_set_black(other->rb_right);
- __rb_rotate_left(parent, root);
- node = root->rb_node;
- break;
+ /*
+ * Case 3 - right rotate at sibling
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N sl
+ * / \ \
+ * sl Sr S
+ * \
+ * Sr
+ *
+ * Note: p might be red, and then both
+ * p and sl are red after rotation(which
+ * breaks property 4). This is fixed in
+ * Case 4 (in __rb_rotate_set_parents()
+ * which set sl the color of p
+ * and set p RB_BLACK)
+ *
+ * (p) (sl)
+ * / \ / \
+ * N sl --> P S
+ * \ / \
+ * S N Sr
+ * \
+ * Sr
+ */
+ tmp1 = tmp2->rb_right;
+ WRITE_ONCE(sibling->rb_left, tmp1);
+ WRITE_ONCE(tmp2->rb_right, sibling);
+ WRITE_ONCE(parent->rb_right, tmp2);
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling,
+ RB_BLACK);
+ augment_rotate(sibling, tmp2);
+ tmp1 = sibling;
+ sibling = tmp2;
}
+ /*
+ * Case 4 - left rotate at parent + color flips
+ * (p and sl could be either color here.
+ * After rotation, p becomes black, s acquires
+ * p's color, and sl keeps its color)
+ *
+ * (p) (s)
+ * / \ / \
+ * N S --> P Sr
+ * / \ / \
+ * (sl) sr N (sl)
+ */
+ tmp2 = sibling->rb_left;
+ WRITE_ONCE(parent->rb_right, tmp2);
+ WRITE_ONCE(sibling->rb_left, parent);
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_BLACK);
+ augment_rotate(parent, sibling);
+ break;
}
else
{
- other = parent->rb_left;
- if (rb_is_red(other))
+ sibling = parent->rb_left;
+ if (rb_is_red(sibling))
{
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_right(parent, root);
- other = parent->rb_left;
+ /* Case 1 - right rotate at parent */
+ tmp1 = sibling->rb_right;
+ WRITE_ONCE(parent->rb_left, tmp1);
+ WRITE_ONCE(sibling->rb_right, parent);
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_RED);
+ augment_rotate(parent, sibling);
+ sibling = tmp1;
}
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
+ tmp1 = sibling->rb_left;
+ if (!tmp1 || rb_is_black(tmp1))
{
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
- }
- else
- {
- if (!other->rb_left || rb_is_black(other->rb_left))
+ tmp2 = sibling->rb_right;
+ if (!tmp2 || rb_is_black(tmp2))
{
- register struct rb_node *o_right;
- if ((o_right = other->rb_right))
- rb_set_black(o_right);
- rb_set_red(other);
- __rb_rotate_left(other, root);
- other = parent->rb_left;
+ /* Case 2 - sibling color flip */
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else
+ {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
}
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_left)
- rb_set_black(other->rb_left);
- __rb_rotate_right(parent, root);
- node = root->rb_node;
- break;
+ /* Case 3 - left rotate at sibling */
+ tmp1 = tmp2->rb_left;
+ WRITE_ONCE(sibling->rb_right, tmp1);
+ WRITE_ONCE(tmp2->rb_left, sibling);
+ WRITE_ONCE(parent->rb_left, tmp2);
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling,
+ RB_BLACK);
+ augment_rotate(sibling, tmp2);
+ tmp1 = sibling;
+ sibling = tmp2;
}
+ /* Case 4 - right rotate at parent + color flips */
+ tmp2 = sibling->rb_right;
+ WRITE_ONCE(parent->rb_left, tmp2);
+ WRITE_ONCE(sibling->rb_right, parent);
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_BLACK);
+ augment_rotate(parent, sibling);
+ break;
}
}
- if (node)
- rb_set_black(node);
}
-void rb_erase(struct rb_node *node, struct rb_root *root)
+/* Non-inline version for rb_erase_augmented() use */
+void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- struct rb_node *child, *parent;
- int color;
-
- if (!node->rb_left)
- child = node->rb_right;
- else if (!node->rb_right)
- child = node->rb_left;
- else
- {
- struct rb_node *old = node, *left;
-
- node = node->rb_right;
- while ((left = node->rb_left) != NULL)
- node = left;
- child = node->rb_right;
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent == old) {
- parent->rb_right = child;
- parent = node;
- } else
- parent->rb_left = child;
-
- node->rb_parent_color = old->rb_parent_color;
- node->rb_right = old->rb_right;
- node->rb_left = old->rb_left;
-
- if (rb_parent(old))
- {
- if (rb_parent(old)->rb_left == old)
- rb_parent(old)->rb_left = node;
- else
- rb_parent(old)->rb_right = node;
- } else
- root->rb_node = node;
-
- rb_set_parent(old->rb_left, node);
- if (old->rb_right)
- rb_set_parent(old->rb_right, node);
- goto color;
- }
+ ____rb_erase_color(parent, root, augment_rotate);
+}
+EXPORT_SYMBOL(__rb_erase_color);
- parent = rb_parent(node);
- color = rb_color(node);
+/*
+ * Non-augmented rbtree manipulation functions.
+ *
+ * We use dummy augmented callbacks here, and have the compiler optimize them
+ * out of the rb_insert_color() and rb_erase() function definitions.
+ */
- if (child)
- rb_set_parent(child, parent);
- if (parent)
- {
- if (parent->rb_left == node)
- parent->rb_left = child;
- else
- parent->rb_right = child;
- }
- else
- root->rb_node = child;
+static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
+static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
+static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
+
+static const struct rb_augment_callbacks dummy_callbacks = {
+ .propagate = dummy_propagate,
+ .copy = dummy_copy,
+ .rotate = dummy_rotate
+};
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ __rb_insert(node, root, dummy_rotate);
+}
+EXPORT_SYMBOL(rb_insert_color);
- color:
- if (color == RB_BLACK)
- __rb_erase_color(child, parent, root);
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *rebalance;
+ rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
+ if (rebalance)
+ ____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);
/*
+ * Augmented rbtree manipulation functions.
+ *
+ * This instantiates the same __always_inline functions as in the non-augmented
+ * case, but this time with user-defined callbacks.
+ */
+
+void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ __rb_insert(node, root, augment_rotate);
+}
+EXPORT_SYMBOL(__rb_insert_augmented);
+
+/*
* This function returns the first node (in sort order) of the tree.
*/
-struct rb_node *rb_first(struct rb_root *root)
+struct rb_node *rb_first(const struct rb_root *root)
{
- struct rb_node *n;
+ struct rb_node *n;
n = root->rb_node;
if (!n)
@@ -304,9 +498,9 @@ struct rb_node *rb_first(struct rb_root *root)
}
EXPORT_SYMBOL(rb_first);
-struct rb_node *rb_last(struct rb_root *root)
+struct rb_node *rb_last(const struct rb_root *root)
{
- struct rb_node *n;
+ struct rb_node *n;
n = root->rb_node;
if (!n)
@@ -317,28 +511,32 @@ struct rb_node *rb_last(struct rb_root *root)
}
EXPORT_SYMBOL(rb_last);
-struct rb_node *rb_next(struct rb_node *node)
+struct rb_node *rb_next(const struct rb_node *node)
{
struct rb_node *parent;
- if (rb_parent(node) == node)
+ if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a right-hand child, go down and then left as far
- as we can. */
- if (node->rb_right) {
+ /*
+ * If we have a right-hand child, go down and then left as far
+ * as we can.
+ */
+ if (node->rb_right)
+ {
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
- return node;
+ return (struct rb_node *)node;
}
- /* No right-hand children. Everything down and left is
- smaller than us, so any 'next' node must be in the general
- direction of our parent. Go up the tree; any time the
- ancestor is a right-hand child of its parent, keep going
- up. First time it's a left-hand child of its parent, said
- parent is our 'next' node. */
+ /*
+ * No right-hand children. Everything down and left is smaller than us,
+ * so any 'next' node must be in the general direction of our parent.
+ * Go up the tree; any time the ancestor is a right-hand child of its
+ * parent, keep going up. First time it's a left-hand child of its
+ * parent, said parent is our 'next' node.
+ */
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
@@ -346,24 +544,29 @@ struct rb_node *rb_next(struct rb_node *node)
}
EXPORT_SYMBOL(rb_next);
-struct rb_node *rb_prev(struct rb_node *node)
+struct rb_node *rb_prev(const struct rb_node *node)
{
struct rb_node *parent;
- if (rb_parent(node) == node)
+ if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a left-hand child, go down and then right as far
- as we can. */
- if (node->rb_left) {
+ /*
+ * If we have a left-hand child, go down and then right as far
+ * as we can.
+ */
+ if (node->rb_left)
+ {
node = node->rb_left;
while (node->rb_right)
node=node->rb_right;
- return node;
+ return (struct rb_node *)node;
}
- /* No left-hand children. Go up till we find an ancestor which
- is a right-hand child of its parent */
+ /*
+ * No left-hand children. Go up till we find an ancestor which
+ * is a right-hand child of its parent.
+ */
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
@@ -372,25 +575,82 @@ struct rb_node *rb_prev(struct rb_node *node)
EXPORT_SYMBOL(rb_prev);
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *root)
+ struct rb_root *root)
{
struct rb_node *parent = rb_parent(victim);
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+
/* Set the surrounding nodes to point to the replacement */
- if (parent) {
- if (victim == parent->rb_left)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else {
- root->rb_node = new;
- }
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
rb_set_parent(victim->rb_right, new);
+ __rb_change_child(victim, new, parent, root);
+}
+EXPORT_SYMBOL(rb_replace_node);
+
+void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = rb_parent(victim);
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (victim->rb_left)
+ rb_set_parent(victim->rb_left, new);
+ if (victim->rb_right)
+ rb_set_parent(victim->rb_right, new);
+
+ /* Set the parent's pointer to the new node last after an RCU barrier
+ * so that the pointers onwards are seen to be set correctly when doing
+ * an RCU walk over the tree.
+ */
+ __rb_change_child_rcu(victim, new, parent, root);
}
-EXPORT_SYMBOL(rb_replace_node);
+EXPORT_SYMBOL(rb_replace_node_rcu);
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+ for (;;)
+ {
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+ else
+ return (struct rb_node *)node;
+ }
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+ const struct rb_node *parent;
+ if (!node)
+ return NULL;
+ parent = rb_parent(node);
+
+ /* If we're sitting on node, we've already seen our children */
+ if (parent && node == parent->rb_left && parent->rb_right)
+ {
+ /* If we are the parent's left node, go to the parent's right
+ * node then all the way down to the left */
+ return rb_left_deepest_node(parent->rb_right);
+ } else
+ /* Otherwise we are the parent's right node, and the parent
+ * should be next */
+ return (struct rb_node *)parent;
+}
+EXPORT_SYMBOL(rb_next_postorder);
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+ if (!root->rb_node)
+ return NULL;
+
+ return rb_left_deepest_node(root->rb_node);
+}
+EXPORT_SYMBOL(rb_first_postorder);
diff --git a/xen/include/xen/compiler.h b/xen/include/xen/compiler.h
index 533a8ea0f3..8cea29a26b 100644
--- a/xen/include/xen/compiler.h
+++ b/xen/include/xen/compiler.h
@@ -127,4 +127,64 @@
# define CLANG_DISABLE_WARN_GCC_COMPAT_END
#endif
+#include <xen/types.h>
+
+#ifndef __always_inline
+#define __always_inline inline
+#endif
+
+#define __READ_ONCE_SIZE \
+({ \
+ switch(size) { \
+ case 1: *(__u8 *)res = *(volatile __u8 *)p; break; \
+ case 2: *(__u16 *)res = *(volatile __u16 *)p; break; \
+ case 4: *(__u32 *)res = *(volatile __u32 *)p; break; \
+ case 8: *(__u64 *)res = *(volatile __u64 *)p; break; \
+ default: \
+ barrier(); \
+ __builtin_memcpy((void *)res, (const void *)p, size); \
+ barrier(); \
+ } \
+})
+
+static __always_inline
+void __read_once_size(const volatile void *p, void *res, int size)
+{
+ __READ_ONCE_SIZE;
+}
+
+static __always_inline
+void __write_once_size(volatile void *p, void *res, int size)
+{
+ switch (size) {
+ case 1: *(volatile __u8 *)p = *(__u8 *)res; break;
+ case 2: *(volatile __u16 *)p = *(__u16 *)res; break;
+ case 4: *(volatile __u32 *)p = *(__u32 *)res; break;
+ case 8: *(volatile __u64 *)p = *(__u64 *)res; break;
+ default:
+ barrier();
+ __builtin_memcpy((void *)p, (const void *)res, size);
+ barrier();
+ }
+}
+
+#define __READ_ONCE(x, check) \
+({ \
+ union { typeof(x) __val; char __c[1]; } __u; \
+ __read_once_size(&(x), __u.__c, sizeof(x)); \
+})
+
+#define READ_ONCE(x) __READ_ONCE(x, 1)
+
+#define WRITE_ONCE(x, val) \
+({ \
+ union { typeof(x) __val; char __c[1]; } __u = \
+ { .__val = (__force typeof(x)) (val) }; \
+ __write_once_size(&(x), __u.__c, sizeof(x)); \
+ __u.__val; \
+})
+
+
+
+
#endif /* __LINUX_COMPILER_H */
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h
index f93c4d5823..6c51d0c918 100644
--- a/xen/include/xen/rbtree.h
+++ b/xen/include/xen/rbtree.h
@@ -13,69 +13,117 @@
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; If not, see <http://www.gnu.org/licenses/>.
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ See Documentation/rbtree.txt for documentation and samples.
*/
-#ifndef __RBTREE_H__
-#define __RBTREE_H__
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+#include <xen/kernel.h>
+#include <xen/rcupdate.h>
struct rb_node
{
- unsigned long rb_parent_color;
-#define RB_RED 0
-#define RB_BLACK 1
+ unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
-};
+} __attribute__((aligned(sizeof(long))));
+ /* The alignment might seem pointless, but allegedly CRIS needs it */
struct rb_root
{
struct rb_node *rb_node;
};
-#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
-#define rb_color(r) ((r)->rb_parent_color & 1)
-#define rb_is_red(r) (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
- rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
- rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
+#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
-#define RB_ROOT (struct rb_root) { NULL, }
-#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
+#define RB_EMPTY_NODE(node) \
+ ((node)->__rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node) \
+ ((node)->__rb_parent_color = (unsigned long)(node))
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
-#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
+
/* Find logical next and previous nodes in a tree */
-extern struct rb_node *rb_next(struct rb_node *);
-extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
-extern struct rb_node *rb_last(struct rb_root *);
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
+
+/* Postorder iteration - always visit the parent after its children */
+extern struct rb_node *rb_first_postorder(const struct rb_root *);
+extern struct rb_node *rb_next_postorder(const struct rb_node *);
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *root);
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
+extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
-static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
- struct rb_node ** rb_link)
+static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
+ struct rb_node **rb_link)
{
- node->rb_parent_color = (unsigned long )parent;
+ node->__rb_parent_color = (unsigned long)parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
-#endif /* __RBTREE_H__ */
+static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
+ struct rb_node **rb_link)
+{
+ node->__rb_parent_color = (unsigned long)parent;
+ node->rb_left = node->rb_right = NULL;
+
+ rcu_assign_pointer(*rb_link, node);
+}
+
+#define rb_entry_safe(ptr, type, member) \
+ ({ typeof(ptr) ____ptr = (ptr); \
+ ____ptr ? rb_entry(____ptr, type, member) : NULL; \
+ })
+
+/**
+ * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
+ * given type allowing the backing memory of @pos to be invalidated
+ *
+ * @pos: the 'type *' to use as a loop cursor.
+ * @n: another 'type *' to use as temporary storage
+ * @root: 'rb_root *' of the rbtree.
+ * @field: the name of the rb_node field within 'type'.
+ *
+ * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
+ * list_for_each_entry_safe() and allows the iteration to continue independent
+ * of changes to @pos by the body of the loop.
+ *
+ * Note, however, that it cannot handle other modifications that re-order the
+ * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
+ * rb_erase() may rebalance the tree, causing us to miss some nodes.
+ */
+#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
+ for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
+ pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
+ typeof(*pos), field); 1; }); \
+ pos = n)
+
+#endif /* _LINUX_RBTREE_H */
diff --git a/xen/include/xen/rbtree_augmented.h b/xen/include/xen/rbtree_augmented.h
new file mode 100644
index 0000000000..2d355501dc
--- /dev/null
+++ b/xen/include/xen/rbtree_augmented.h
@@ -0,0 +1,283 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree_augmented.h
+*/
+
+#ifndef _LINUX_RBTREE_AUGMENTED_H
+#define _LINUX_RBTREE_AUGMENTED_H
+
+#include <xen/compiler.h>
+#include <xen/rbtree.h>
+
+/*
+ * Please note - only struct rb_augment_callbacks and the prototypes for
+ * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
+ * The rest are implementation details you are not expected to depend on.
+ *
+ * See Documentation/rbtree.txt for documentation and samples.
+ */
+
+struct rb_augment_callbacks
+{
+ void (*propagate)(struct rb_node *node, struct rb_node *stop);
+ void (*copy)(struct rb_node *old, struct rb_node *new);
+ void (*rotate)(struct rb_node *old, struct rb_node *new);
+};
+
+extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+/*
+ * Fixup the rbtree and update the augmented information when rebalancing.
+ *
+ * On insertion, the user must update the augmented information on the path
+ * leading to the inserted node, then call rb_link_node() as usual and
+ * rb_augment_inserted() instead of the usual rb_insert_color() call.
+ * If rb_augment_inserted() rebalances the rbtree, it will callback into
+ * a user provided function to update the augmented information on the
+ * affected subtrees.
+ */
+static inline void
+rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ __rb_insert_augmented(node, root, augment->rotate);
+}
+
+#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
+ rbtype, rbaugmented, rbcompute) \
+static inline void \
+rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
+{ \
+ while (rb != stop) \
+ { \
+ rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
+ rbtype augmented = rbcompute(node); \
+ if (node->rbaugmented == augmented) \
+ break; \
+ node->rbaugmented = augmented; \
+ rb = rb_parent(&node->rbfield); \
+ } \
+} \
+static inline void \
+rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+} \
+static void \
+rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+ old->rbaugmented = rbcompute(old); \
+} \
+rbstatic const struct rb_augment_callbacks rbname = { \
+ .propagate = rbname ## _propagate, \
+ .copy = rbname ## _copy, \
+ .rotate = rbname ## _rotate \
+};
+
+
+#define RB_RED 0
+#define RB_BLACK 1
+
+#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc) ((pc) & 1)
+#define __rb_is_black(pc) __rb_color(pc)
+#define __rb_is_red(pc) (!__rb_color(pc))
+#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
+}
+
+static inline void rb_set_parent_color(struct rb_node *rb,
+ struct rb_node *p, int color)
+{
+ rb->__rb_parent_color = (unsigned long)p | color;
+}
+
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+ struct rb_node *parent, struct rb_root *root)
+{
+ if (parent)
+ {
+ if (parent->rb_left == old)
+ WRITE_ONCE(parent->rb_left, new);
+ else
+ WRITE_ONCE(parent->rb_right, new);
+ } else
+ WRITE_ONCE(root->rb_node, new);
+}
+
+static inline void
+__rb_change_child_rcu(struct rb_node *old, struct rb_node *new,
+ struct rb_node *parent, struct rb_root *root)
+{
+ if (parent)
+ {
+ if (parent->rb_left == old)
+ rcu_assign_pointer(parent->rb_left, new);
+ else
+ rcu_assign_pointer(parent->rb_right, new);
+ }
+ else
+ rcu_assign_pointer(root->rb_node, new);
+}
+
+extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+
+static __always_inline struct rb_node *
+__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *child = node->rb_right;
+ struct rb_node *tmp = node->rb_left;
+ struct rb_node *parent, *rebalance;
+ unsigned long pc;
+
+ if (!tmp)
+ {
+ /*
+ * Case 1: node to erase has no more than 1 child (easy!)
+ *
+ * Note that if there is one child it must be red due to 5)
+ * and node must be black due to 4). We adjust colors locally
+ * so as to bypass __rb_erase_color() later on.
+ */
+ pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, child, parent, root);
+ if (child)
+ {
+ child->__rb_parent_color = pc;
+ rebalance = NULL;
+ }
+ else
+ rebalance = __rb_is_black(pc) ? parent : NULL;
+ tmp = parent;
+ }
+ else if (!child)
+ {
+ /* Still case 1, but this time the child is node->rb_left */
+ tmp->__rb_parent_color = pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, tmp, parent, root);
+ rebalance = NULL;
+ tmp = parent;
+ }
+ else
+ {
+ struct rb_node *successor = child, *child2;
+
+ tmp = child->rb_left;
+ if (!tmp)
+ {
+ /*
+ * Case 2: node's successor is its right child
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (s) -> (x) (c)
+ * \
+ * (c)
+ */
+ parent = successor;
+ child2 = successor->rb_right;
+
+ augment->copy(node, successor);
+ }
+ else
+ {
+ /*
+ * Case 3: node's successor is leftmost under
+ * node's right child subtree
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (y) -> (x) (y)
+ * / /
+ * (p) (p)
+ * / /
+ * (s) (c)
+ * \
+ * (c)
+ */
+ do
+ {
+ parent = successor;
+ successor = tmp;
+ tmp = tmp->rb_left;
+ } while (tmp);
+ child2 = successor->rb_right;
+ WRITE_ONCE(parent->rb_left, child2);
+ WRITE_ONCE(successor->rb_right, child);
+ rb_set_parent(child, successor);
+
+ augment->copy(node, successor);
+ augment->propagate(parent, successor);
+ }
+
+ tmp = node->rb_left;
+ WRITE_ONCE(successor->rb_left, tmp);
+ rb_set_parent(tmp, successor);
+
+ pc = node->__rb_parent_color;
+ tmp = __rb_parent(pc);
+ __rb_change_child(node, successor, tmp, root);
+
+ if (child2)
+ {
+ successor->__rb_parent_color = pc;
+ rb_set_parent_color(child2, parent, RB_BLACK);
+ rebalance = NULL;
+ }
+ else
+ {
+ unsigned long pc2 = successor->__rb_parent_color;
+ successor->__rb_parent_color = pc;
+ rebalance = __rb_is_black(pc2) ? parent : NULL;
+ }
+ tmp = successor;
+ }
+
+ augment->propagate(tmp, NULL);
+ return rebalance;
+}
+
+static __always_inline void
+rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
+ if (rebalance)
+ __rb_erase_color(rebalance, root, augment->rotate);
+}
+
+#endif /* _LINUX_RBTREE_AUGMENTED_H */
--
2.12.0
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [resend PATCH] xen: common: rbtree: ported updates from linux tree
2017-05-11 17:21 [resend PATCH] xen: common: rbtree: ported updates from linux tree Praveen Kumar
@ 2017-05-18 13:59 ` Jan Beulich
2017-05-18 14:47 ` Dario Faggioli
0 siblings, 1 reply; 5+ messages in thread
From: Jan Beulich @ 2017-05-18 13:59 UTC (permalink / raw)
To: Praveen Kumar
Cc: tim, sstabellini, wei.liu2, George.Dunlap, andrew.cooper3,
ian.jackson, xen-devel
>>> On 11.05.17 at 19:21, <kpraveen.lkml@gmail.com> wrote:
> The patch contains the updated version of rbtree implementation from linux
> kernel tree containing the fixes so far handled.
I suppose this isn't just fixes, but also enhancements. Furthermore
I'd appreciate if you recorded the Linux version this was taken from,
so that anyone wanting to do another upgrade would know what
the baseline is. In any event, as long as this is just a general
overhaul and upgrade, I'd like to either see individual bugs pointed
out which get fixed _and_ which affect us, or I'd expect this to be
part of a series which actually requires some of the new functionality.
Otherwise it is e.g. hard to understand why ...
> Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
> ---
> xen/common/rbtree.c | 748 +++++++++++++++++++++++++------------
> xen/include/xen/compiler.h | 60 +++
> xen/include/xen/rbtree.h | 120 ++++--
> xen/include/xen/rbtree_augmented.h | 283 ++++++++++++++
... namely this last (new) header (and what it provides) is needed
at all.
I don't think there's much point in reviewing these changes if
indeed they've been taken from Linux literally (I'm sure you
would have pointed out meaningful changes in the commit
message).
> --- a/xen/include/xen/compiler.h
> +++ b/xen/include/xen/compiler.h
> @@ -127,4 +127,64 @@
> # define CLANG_DISABLE_WARN_GCC_COMPAT_END
> #endif
>
> +#include <xen/types.h>
Anything requiring this header very unlikely belongs into compiler.h.
> +#ifndef __always_inline
> +#define __always_inline inline
> +#endif
Please use always_inline instead, which we already have.
> +#define __READ_ONCE_SIZE \
> +({ \
> + switch(size) { \
> + case 1: *(__u8 *)res = *(volatile __u8 *)p; break; \
> + case 2: *(__u16 *)res = *(volatile __u16 *)p; break; \
> + case 4: *(__u32 *)res = *(volatile __u32 *)p; break; \
> + case 8: *(__u64 *)res = *(volatile __u64 *)p; break; \
No new uses of __u<n> or u<n> or their signed counterparts
please. We have {,u}int<n>_t for that purpose. Iirc even Linux
maintainers nowadays object to these double underscore prefixed
names outside of user visible header files.
> + default: \
> + barrier(); \
> + __builtin_memcpy((void *)res, (const void *)p, size); \
> + barrier(); \
Compiler barriers aren't equivalents of uses of "volatile" on all
architectures, so the correctness here would need to be
explained.
> + } \
> +})
> +
> +static __always_inline
> +void __read_once_size(const volatile void *p, void *res, int size)
> +{
> + __READ_ONCE_SIZE;
> +}
> +
> +static __always_inline
> +void __write_once_size(volatile void *p, void *res, int size)
> +{
> + switch (size) {
> + case 1: *(volatile __u8 *)p = *(__u8 *)res; break;
> + case 2: *(volatile __u16 *)p = *(__u16 *)res; break;
> + case 4: *(volatile __u32 *)p = *(__u32 *)res; break;
> + case 8: *(volatile __u64 *)p = *(__u64 *)res; break;
> + default:
> + barrier();
> + __builtin_memcpy((void *)p, (const void *)res, size);
> + barrier();
> + }
> +}
> +
> +#define __READ_ONCE(x, check) \
> +({ \
> + union { typeof(x) __val; char __c[1]; } __u; \
> + __read_once_size(&(x), __u.__c, sizeof(x)); \
> +})
The "check" parameter is unused, so ...
> +#define READ_ONCE(x) __READ_ONCE(x, 1)
... this wrapper can be dropped.
> +#define WRITE_ONCE(x, val) \
> +({ \
> + union { typeof(x) __val; char __c[1]; } __u = \
> + { .__val = (__force typeof(x)) (val) }; \
> + __write_once_size(&(x), __u.__c, sizeof(x)); \
> + __u.__val; \
> +})
> +
> +
> +
> +
> #endif /* __LINUX_COMPILER_H */
No way you get to add four blank lines in a row to any file.
In any event it is not clear to me whether we really need all of this:
Are there properties at the use sites which neither
{read,write}_atomic() nor ACCESS_ONCE() can fulfill? And if indeed
we need yet another flavor, you'd need to do away with all these
underscore prefixed names.
Jan
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [resend PATCH] xen: common: rbtree: ported updates from linux tree
2017-05-18 13:59 ` Jan Beulich
@ 2017-05-18 14:47 ` Dario Faggioli
2017-05-23 9:12 ` Praveen Kumar
0 siblings, 1 reply; 5+ messages in thread
From: Dario Faggioli @ 2017-05-18 14:47 UTC (permalink / raw)
To: Jan Beulich, Praveen Kumar
Cc: sstabellini, wei.liu2, George.Dunlap, ian.jackson, tim, xen-devel,
andrew.cooper3
[-- Attachment #1.1: Type: text/plain, Size: 2540 bytes --]
On Thu, 2017-05-18 at 07:59 -0600, Jan Beulich wrote:
> > > > On 11.05.17 at 19:21, <kpraveen.lkml@gmail.com> wrote:
> >
> > The patch contains the updated version of rbtree implementation
> > from linux
> > kernel tree containing the fixes so far handled.
>
> I suppose this isn't just fixes, but also enhancements. Furthermore
> I'd appreciate if you recorded the Linux version this was taken from,
> so that anyone wanting to do another upgrade would know what
> the baseline is. In any event, as long as this is just a general
> overhaul and upgrade, I'd like to either see individual bugs pointed
> out which get fixed _and_ which affect us, or I'd expect this to be
> part of a series which actually requires some of the new
> functionality.
>
I fully agree.
And in fact, this is actually quite a big patch, and does (although it
touches only a few files) a bunch of different things (new
functionalities, improved comments, etc).
So, Jan, would it be ok for this thing that Praveen is trying to do, to
be a series, with one patch for each original Linux commit? I think, if
it were me doing this, that would be how I'd do it.
Otherwise it is e.g. hard to understand why ...
>
> > Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
> > ---
> > xen/common/rbtree.c | 748
> > +++++++++++++++++++++++++------------
> > xen/include/xen/compiler.h | 60 +++
> > xen/include/xen/rbtree.h | 120 ++++--
> > xen/include/xen/rbtree_augmented.h | 283 ++++++++++++++
>
> ... namely this last (new) header (and what it provides) is needed
> at all.
>
Indeed. And in fact, for our original purpose (which is to use rb-trees
instead of linked lists for Credit2's runqueues), I don't think we
actually need the augmented variant.
Praveen, as we agreed on IRC, it is ok to send this patch (which I
think should have been a patch series) first, but stating why you are
actually doing this (i.e., a few words on the original purpose I'm
mentioning above), is really useful, to set the context, and should be
there (in the cover letter or a follow up email).
Also, do Cc me please (in addition to what get_maintainers.pl
says). :-)
Regards,
Dario
--
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)
[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
[-- Attachment #2: Type: text/plain, Size: 127 bytes --]
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [resend PATCH] xen: common: rbtree: ported updates from linux tree
2017-05-18 14:47 ` Dario Faggioli
@ 2017-05-23 9:12 ` Praveen Kumar
2017-05-23 10:22 ` Jan Beulich
0 siblings, 1 reply; 5+ messages in thread
From: Praveen Kumar @ 2017-05-23 9:12 UTC (permalink / raw)
To: Dario Faggioli, Jan Beulich
Cc: sstabellini, wei.liu2, George.Dunlap, ian.jackson, tim, xen-devel,
andrew.cooper3
Thanks Jan and Dario for your inputs. Will incorporate your suggested
inputs and share the updated patch.
On Thu, 2017-05-18 at 16:47 +0200, Dario Faggioli wrote:
> On Thu, 2017-05-18 at 07:59 -0600, Jan Beulich wrote:
> >
> > >
> > > >
> > > > >
> > > > > On 11.05.17 at 19:21, <kpraveen.lkml@gmail.com> wrote:
> > >
> > > The patch contains the updated version of rbtree implementation
> > > from linux
> > > kernel tree containing the fixes so far handled.
> >
> > I suppose this isn't just fixes, but also enhancements. Furthermore
> > I'd appreciate if you recorded the Linux version this was taken
> > from,
> > so that anyone wanting to do another upgrade would know what
> > the baseline is. In any event, as long as this is just a general
> > overhaul and upgrade, I'd like to either see individual bugs
> > pointed
> > out which get fixed _and_ which affect us, or I'd expect this to be
> > part of a series which actually requires some of the new
> > functionality.
> >
> I fully agree.
Sure, will put the the commit text ? Else, is it fine to put in as a
code comment ?
>
> And in fact, this is actually quite a big patch, and does (although
> it
> touches only a few files) a bunch of different things (new
> functionalities, improved comments, etc).
>
> So, Jan, would it be ok for this thing that Praveen is trying to do,
> to
> be a series, with one patch for each original Linux commit? I think,
> if
> it were me doing this, that would be how I'd do it.
>
> Otherwise it is e.g. hard to understand why ...
> >
> >
> > >
> > > Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
> > > ---
> > > xen/common/rbtree.c | 748
> > > +++++++++++++++++++++++++------------
> > > xen/include/xen/compiler.h | 60 +++
> > > xen/include/xen/rbtree.h | 120 ++++--
> > > xen/include/xen/rbtree_augmented.h | 283 ++++++++++++++
> >
> > ... namely this last (new) header (and what it provides) is needed
> > at all.
> >
> Indeed. And in fact, for our original purpose (which is to use rb-
> trees
> instead of linked lists for Credit2's runqueues), I don't think we
> actually need the augmented variant.
Ok. I will go through what all changes are incorporated with augmented
variant and not include them ( Need to check with the versions. )
>
> Praveen, as we agreed on IRC, it is ok to send this patch (which I
> think should have been a patch series) first, but stating why you are
> actually doing this (i.e., a few words on the original purpose I'm
> mentioning above), is really useful, to set the context, and should
> be
> there (in the cover letter or a follow up email).
>
Dario, I sent in initial patch as a follow up email, but my bad didn't
send the same while resending the patch. Will take care of the same in
future patches.
> Also, do Cc me please (in addition to what get_maintainers.pl
> says). :-)
>
Sure will add you in Cc. Thanks.
> Regards,
> Dario
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [resend PATCH] xen: common: rbtree: ported updates from linux tree
2017-05-23 9:12 ` Praveen Kumar
@ 2017-05-23 10:22 ` Jan Beulich
0 siblings, 0 replies; 5+ messages in thread
From: Jan Beulich @ 2017-05-23 10:22 UTC (permalink / raw)
To: Praveen Kumar
Cc: tim, sstabellini, wei.liu2, George.Dunlap, andrew.cooper3,
Dario Faggioli, ian.jackson, xen-devel
>>> On 23.05.17 at 11:12, <kpraveen.lkml@gmail.com> wrote:
> On Thu, 2017-05-18 at 16:47 +0200, Dario Faggioli wrote:
>> On Thu, 2017-05-18 at 07:59 -0600, Jan Beulich wrote:
>> >
>> > >
>> > > >
>> > > > >
>> > > > > On 11.05.17 at 19:21, <kpraveen.lkml@gmail.com> wrote:
>> > >
>> > > The patch contains the updated version of rbtree implementation
>> > > from linux
>> > > kernel tree containing the fixes so far handled.
>> >
>> > I suppose this isn't just fixes, but also enhancements. Furthermore
>> > I'd appreciate if you recorded the Linux version this was taken
>> > from,
>> > so that anyone wanting to do another upgrade would know what
>> > the baseline is. In any event, as long as this is just a general
>> > overhaul and upgrade, I'd like to either see individual bugs
>> > pointed
>> > out which get fixed _and_ which affect us, or I'd expect this to be
>> > part of a series which actually requires some of the new
>> > functionality.
>> >
>> I fully agree.
>
> Sure, will put the the commit text ? Else, is it fine to put in as a
> code comment ?
Code comment? The intention has to be to take the Linux code
with as little changes as possible. That includes not adding
comments which don't exist in the original. So unless you follow
Dario's suggestion to possibly use individual Linux commits
instead of this giant one, it'll be the commit message where all
this information should go.
Jan
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-05-23 10:22 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-05-11 17:21 [resend PATCH] xen: common: rbtree: ported updates from linux tree Praveen Kumar
2017-05-18 13:59 ` Jan Beulich
2017-05-18 14:47 ` Dario Faggioli
2017-05-23 9:12 ` Praveen Kumar
2017-05-23 10:22 ` Jan Beulich
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).