Re: [PATCH perf] tools: Update rbtree files
From: Arnaldo Carvalho de Melo
Date: Fri Oct 13 2017 - 10:57:01 EST
Em Thu, Oct 12, 2017 at 01:52:11PM -0600, David Ahern escreveu:
> hi Arnaldo:
>
> On 9/29/17 2:26 PM, David Ahern wrote:
> > Update rbtree files to 4.14.
>
> Haven't seen this one in your perf/core branch. You added the existing
> version, so assuming an update goes through you as well.
Ok, I'll get to it and merge your update, thanks!
- Arnaldo
> >
> > Changes made after copy:
> > - update guards in header files
> > - remove rcu references
> >
> > Signed-off-by: David Ahern <dsahern@xxxxxxxxx>
> > ---
> > tools/include/linux/rbtree.h | 59 ++++++++---
> > tools/include/linux/rbtree_augmented.h | 58 +++++++++--
> > tools/lib/rbtree.c | 184 +++++++++++++++++++++++++--------
> > 3 files changed, 233 insertions(+), 68 deletions(-)
> >
> > diff --git a/tools/include/linux/rbtree.h b/tools/include/linux/rbtree.h
> > index 112582253dd0..fe5d79881749 100644
> > --- a/tools/include/linux/rbtree.h
> > +++ b/tools/include/linux/rbtree.h
> > @@ -1,7 +1,7 @@
> > /*
> > Red Black Trees
> > (C) 1999 Andrea Arcangeli <andrea@xxxxxxx>
> > -
> > +
> > 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
> > @@ -43,13 +43,28 @@ struct rb_root {
> > struct rb_node *rb_node;
> > };
> >
> > +/*
> > + * Leftmost-cached rbtrees.
> > + *
> > + * We do not cache the rightmost node based on footprint
> > + * size vs number of potential users that could benefit
> > + * from O(1) rb_last(). Just not worth it, users that want
> > + * this feature can always implement the logic explicitly.
> > + * Furthermore, users that want to cache both pointers may
> > + * find it a bit asymmetric, but that's ok.
> > + */
> > +struct rb_root_cached {
> > + struct rb_root rb_root;
> > + struct rb_node *rb_leftmost;
> > +};
> >
> > #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
> >
> > #define RB_ROOT (struct rb_root) { NULL, }
> > +#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
> > #define rb_entry(ptr, type, member) container_of(ptr, type, member)
> >
> > -#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
> > +#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) \
> > @@ -68,6 +83,12 @@ 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 *);
> >
> > +extern void rb_insert_color_cached(struct rb_node *,
> > + struct rb_root_cached *, bool);
> > +extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
> > +/* Same as rb_first(), but O(1) */
> > +#define rb_first_cached(root) (root)->rb_leftmost
> > +
> > /* 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 *);
> > @@ -90,15 +111,27 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
> > ____ptr ? rb_entry(____ptr, type, member) : NULL; \
> > })
> >
> > -
> > -/*
> > - * Handy for checking that we are not deleting an entry that is
> > - * already in a list, found in block/{blk-throttle,cfq-iosched}.c,
> > - * probably should be moved to lib/rbtree.c...
> > +/**
> > + * 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.
> > */
> > -static inline void rb_erase_init(struct rb_node *n, struct rb_root *root)
> > -{
> > - rb_erase(n, root);
> > - RB_CLEAR_NODE(n);
> > -}
> > -#endif /* __TOOLS_LINUX_PERF_RBTREE_H */
> > +#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 /* __TOOLS_LINUX_PERF_RBTREE_H */
> > diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
> > index 43be941db695..405716528516 100644
> > --- a/tools/include/linux/rbtree_augmented.h
> > +++ b/tools/include/linux/rbtree_augmented.h
> > @@ -44,7 +44,9 @@ struct rb_augment_callbacks {
> > void (*rotate)(struct rb_node *old, struct rb_node *new);
> > };
> >
> > -extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
> > +extern void __rb_insert_augmented(struct rb_node *node,
> > + struct rb_root *root,
> > + bool newleft, struct rb_node **leftmost,
> > void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
> > /*
> > * Fixup the rbtree and update the augmented information when rebalancing.
> > @@ -60,7 +62,16 @@ 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);
> > + __rb_insert_augmented(node, root, false, NULL, augment->rotate);
> > +}
> > +
> > +static inline void
> > +rb_insert_augmented_cached(struct rb_node *node,
> > + struct rb_root_cached *root, bool newleft,
> > + const struct rb_augment_callbacks *augment)
> > +{
> > + __rb_insert_augmented(node, &root->rb_root,
> > + newleft, &root->rb_leftmost, augment->rotate);
> > }
> >
> > #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
> > @@ -93,7 +104,9 @@ rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
> > old->rbaugmented = rbcompute(old); \
> > } \
> > rbstatic const struct rb_augment_callbacks rbname = { \
> > - rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
> > + .propagate = rbname ## _propagate, \
> > + .copy = rbname ## _copy, \
> > + .rotate = rbname ## _rotate \
> > };
> >
> >
> > @@ -126,11 +139,11 @@ __rb_change_child(struct rb_node *old, struct rb_node *new,
> > {
> > if (parent) {
> > if (parent->rb_left == old)
> > - parent->rb_left = new;
> > + WRITE_ONCE(parent->rb_left, new);
> > else
> > - parent->rb_right = new;
> > + WRITE_ONCE(parent->rb_right, new);
> > } else
> > - root->rb_node = new;
> > + WRITE_ONCE(root->rb_node, new);
> > }
> >
> > extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > @@ -138,12 +151,17 @@ extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
> >
> > static __always_inline struct rb_node *
> > __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
> > + struct rb_node **leftmost,
> > const struct rb_augment_callbacks *augment)
> > {
> > - struct rb_node *child = node->rb_right, *tmp = node->rb_left;
> > + struct rb_node *child = node->rb_right;
> > + struct rb_node *tmp = node->rb_left;
> > struct rb_node *parent, *rebalance;
> > unsigned long pc;
> >
> > + if (leftmost && node == *leftmost)
> > + *leftmost = rb_next(node);
> > +
> > if (!tmp) {
> > /*
> > * Case 1: node to erase has no more than 1 child (easy!)
> > @@ -170,6 +188,7 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
> > tmp = parent;
> > } else {
> > struct rb_node *successor = child, *child2;
> > +
> > tmp = child->rb_left;
> > if (!tmp) {
> > /*
> > @@ -183,6 +202,7 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
> > */
> > parent = successor;
> > child2 = successor->rb_right;
> > +
> > augment->copy(node, successor);
> > } else {
> > /*
> > @@ -204,19 +224,23 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
> > successor = tmp;
> > tmp = tmp->rb_left;
> > } while (tmp);
> > - parent->rb_left = child2 = successor->rb_right;
> > - successor->rb_right = child;
> > + 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);
> > }
> >
> > - successor->rb_left = tmp = node->rb_left;
> > + 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);
> > @@ -237,9 +261,21 @@ 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);
> > + struct rb_node *rebalance = __rb_erase_augmented(node, root,
> > + NULL, augment);
> > if (rebalance)
> > __rb_erase_color(rebalance, root, augment->rotate);
> > }
> >
> > +static __always_inline void
> > +rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
> > + const struct rb_augment_callbacks *augment)
> > +{
> > + struct rb_node *rebalance = __rb_erase_augmented(node, &root->rb_root,
> > + &root->rb_leftmost,
> > + augment);
> > + if (rebalance)
> > + __rb_erase_color(rebalance, &root->rb_root, augment->rotate);
> > +}
> > +
> > #endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */
> > diff --git a/tools/lib/rbtree.c b/tools/lib/rbtree.c
> > index 17c2b596f043..a3bf68a3f1d4 100644
> > --- a/tools/lib/rbtree.c
> > +++ b/tools/lib/rbtree.c
> > @@ -22,6 +22,7 @@
> > */
> >
> > #include <linux/rbtree_augmented.h>
> > +#include <linux/export.h>
> >
> > /*
> > * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
> > @@ -43,6 +44,30 @@
> > * parentheses and have some accompanying text comment.
> > */
> >
> > +/*
> > + * 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.
> > + */
> > +
> > static inline void rb_set_black(struct rb_node *rb)
> > {
> > rb->__rb_parent_color |= RB_BLACK;
> > @@ -70,22 +95,35 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
> >
> > static __always_inline void
> > __rb_insert(struct rb_node *node, struct rb_root *root,
> > + bool newleft, struct rb_node **leftmost,
> > void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
> > {
> > struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
> >
> > + if (newleft)
> > + *leftmost = node;
> > +
> > while (true) {
> > /*
> > - * 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.
> > + * Loop invariant: node is red.
> > */
> > - if (!parent) {
> > + if (unlikely(!parent)) {
> > + /*
> > + * The inserted node is root. Either this is the
> > + * first node, or we recursed at Case 1 below and
> > + * are no longer violating 4).
> > + */
> > rb_set_parent_color(node, NULL, RB_BLACK);
> > break;
> > - } else if (rb_is_black(parent))
> > + }
> > +
> > + /*
> > + * If there is a black parent, we are done.
> > + * Otherwise, take some corrective action as,
> > + * per 4), we don't want a red root or two
> > + * consecutive red nodes.
> > + */
> > + if(rb_is_black(parent))
> > break;
> >
> > gparent = rb_red_parent(parent);
> > @@ -94,7 +132,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > if (parent != tmp) { /* parent == gparent->rb_left */
> > if (tmp && rb_is_red(tmp)) {
> > /*
> > - * Case 1 - color flips
> > + * Case 1 - node's uncle is red (color flips).
> > *
> > * G g
> > * / \ / \
> > @@ -117,7 +155,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > tmp = parent->rb_right;
> > if (node == tmp) {
> > /*
> > - * Case 2 - left rotate at parent
> > + * Case 2 - node's uncle is black and node is
> > + * the parent's right child (left rotate at parent).
> > *
> > * G G
> > * / \ / \
> > @@ -128,8 +167,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > * This still leaves us in violation of 4), the
> > * continuation into Case 3 will fix that.
> > */
> > - parent->rb_right = tmp = node->rb_left;
> > - node->rb_left = parent;
> > + 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);
> > @@ -140,7 +180,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > }
> >
> > /*
> > - * Case 3 - right rotate at gparent
> > + * Case 3 - node's uncle is black and node is
> > + * the parent's left child (right rotate at gparent).
> > *
> > * G P
> > * / \ / \
> > @@ -148,8 +189,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > * / \
> > * n U
> > */
> > - gparent->rb_left = tmp; /* == parent->rb_right */
> > - parent->rb_right = gparent;
> > + 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);
> > @@ -170,8 +211,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > tmp = parent->rb_left;
> > if (node == tmp) {
> > /* Case 2 - right rotate at parent */
> > - parent->rb_left = tmp = node->rb_right;
> > - node->rb_right = 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);
> > @@ -182,8 +224,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
> > }
> >
> > /* Case 3 - left rotate at gparent */
> > - gparent->rb_right = tmp; /* == parent->rb_left */
> > - parent->rb_left = 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);
> > @@ -223,8 +265,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > * / \ / \
> > * Sl Sr N Sl
> > */
> > - parent->rb_right = tmp1 = sibling->rb_left;
> > - sibling->rb_left = parent;
> > + 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);
> > @@ -268,15 +311,31 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > *
> > * (p) (p)
> > * / \ / \
> > - * N S --> N Sl
> > + * N S --> N sl
> > * / \ \
> > - * sl Sr s
> > + * 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
> > */
> > - sibling->rb_left = tmp1 = tmp2->rb_right;
> > - tmp2->rb_right = sibling;
> > - parent->rb_right = tmp2;
> > + 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);
> > @@ -296,8 +355,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > * / \ / \
> > * (sl) sr N (sl)
> > */
> > - parent->rb_right = tmp2 = sibling->rb_left;
> > - sibling->rb_left = parent;
> > + 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);
> > @@ -309,8 +369,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > sibling = parent->rb_left;
> > if (rb_is_red(sibling)) {
> > /* Case 1 - right rotate at parent */
> > - parent->rb_left = tmp1 = sibling->rb_right;
> > - sibling->rb_right = 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);
> > @@ -334,10 +395,11 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > }
> > break;
> > }
> > - /* Case 3 - right rotate at sibling */
> > - sibling->rb_right = tmp1 = tmp2->rb_left;
> > - tmp2->rb_left = sibling;
> > - parent->rb_left = tmp2;
> > + /* 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);
> > @@ -345,9 +407,10 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > tmp1 = sibling;
> > sibling = tmp2;
> > }
> > - /* Case 4 - left rotate at parent + color flips */
> > - parent->rb_left = tmp2 = sibling->rb_right;
> > - sibling->rb_right = parent;
> > + /* 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);
> > @@ -365,6 +428,7 @@ void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
> > {
> > ____rb_erase_color(parent, root, augment_rotate);
> > }
> > +EXPORT_SYMBOL(__rb_erase_color);
> >
> > /*
> > * Non-augmented rbtree manipulation functions.
> > @@ -378,21 +442,44 @@ 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 = {
> > - dummy_propagate, dummy_copy, dummy_rotate
> > + .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);
> > + __rb_insert(node, root, false, NULL, dummy_rotate);
> > }
> > +EXPORT_SYMBOL(rb_insert_color);
> >
> > void rb_erase(struct rb_node *node, struct rb_root *root)
> > {
> > struct rb_node *rebalance;
> > - rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
> > + rebalance = __rb_erase_augmented(node, root,
> > + NULL, &dummy_callbacks);
> > if (rebalance)
> > ____rb_erase_color(rebalance, root, dummy_rotate);
> > }
> > +EXPORT_SYMBOL(rb_erase);
> > +
> > +void rb_insert_color_cached(struct rb_node *node,
> > + struct rb_root_cached *root, bool leftmost)
> > +{
> > + __rb_insert(node, &root->rb_root, leftmost,
> > + &root->rb_leftmost, dummy_rotate);
> > +}
> > +EXPORT_SYMBOL(rb_insert_color_cached);
> > +
> > +void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
> > +{
> > + struct rb_node *rebalance;
> > + rebalance = __rb_erase_augmented(node, &root->rb_root,
> > + &root->rb_leftmost, &dummy_callbacks);
> > + if (rebalance)
> > + ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
> > +}
> > +EXPORT_SYMBOL(rb_erase_cached);
> >
> > /*
> > * Augmented rbtree manipulation functions.
> > @@ -402,10 +489,12 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
> > */
> >
> > void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
> > + bool newleft, struct rb_node **leftmost,
> > void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
> > {
> > - __rb_insert(node, root, augment_rotate);
> > + __rb_insert(node, root, newleft, leftmost, augment_rotate);
> > }
> > +EXPORT_SYMBOL(__rb_insert_augmented);
> >
> > /*
> > * This function returns the first node (in sort order) of the tree.
> > @@ -421,6 +510,7 @@ struct rb_node *rb_first(const struct rb_root *root)
> > n = n->rb_left;
> > return n;
> > }
> > +EXPORT_SYMBOL(rb_first);
> >
> > struct rb_node *rb_last(const struct rb_root *root)
> > {
> > @@ -433,6 +523,7 @@ struct rb_node *rb_last(const struct rb_root *root)
> > n = n->rb_right;
> > return n;
> > }
> > +EXPORT_SYMBOL(rb_last);
> >
> > struct rb_node *rb_next(const struct rb_node *node)
> > {
> > @@ -464,6 +555,7 @@ struct rb_node *rb_next(const struct rb_node *node)
> >
> > return parent;
> > }
> > +EXPORT_SYMBOL(rb_next);
> >
> > struct rb_node *rb_prev(const struct rb_node *node)
> > {
> > @@ -492,22 +584,24 @@ struct rb_node *rb_prev(const struct rb_node *node)
> >
> > return parent;
> > }
> > +EXPORT_SYMBOL(rb_prev);
> >
> > void rb_replace_node(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 */
> > - __rb_change_child(victim, new, parent, root);
> > if (victim->rb_left)
> > rb_set_parent(victim->rb_left, new);
> > if (victim->rb_right)
> > rb_set_parent(victim->rb_right, new);
> > -
> > - /* Copy the pointers/colour from the victim to the replacement */
> > - *new = *victim;
> > + __rb_change_child(victim, new, parent, root);
> > }
> > +EXPORT_SYMBOL(rb_replace_node);
> >
> > static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
> > {
> > @@ -538,6 +632,7 @@ struct rb_node *rb_next_postorder(const struct rb_node *node)
> > * should be next */
> > return (struct rb_node *)parent;
> > }
> > +EXPORT_SYMBOL(rb_next_postorder);
> >
> > struct rb_node *rb_first_postorder(const struct rb_root *root)
> > {
> > @@ -546,3 +641,4 @@ struct rb_node *rb_first_postorder(const struct rb_root *root)
> >
> > return rb_left_deepest_node(root->rb_node);
> > }
> > +EXPORT_SYMBOL(rb_first_postorder);
> >