BUG/MAJOR: ebtree/scope: fix lookup of next node in scope-aware trees
The eb32sc_walk_down_left() function needs to be able to go up when
it doesn't find a matching entry because this situation may always
happen, especially when fixing two constraints (scope + value). It
also happens after certain removal situations where some bits remain
on some intermediary nodes in the tree.
In addition, the algorithm for deciding to take the right branch is
wrong as it would take it if the current node shows a scope that
doesn't matchthe required one.
The current code is flakey in that it returns NULL when the bottom
has been reached and it's up to the caller to visit other nodes above.
In addition to being complex it's not reliable, and it was noticed a
few times that some tasks could remain lying in the tree after heavy
insertion/removals under multi-threaded workloads.
Now instead we make eb32sc_walk_down_left() visit the leftmost branch
that matches the scope, and automatically go up to visit the closest
matching right branch. This effectively does the same operations as a
next() operation but in reverse order (down then up instead of up then
down).
The eb32sc_next() function now becomes very simple again and matches
the original one, and the initial issues cannot be met anymore.
No backport is needed, this is purely 1.8-specific.
diff --git a/ebtree/eb32sctree.h b/ebtree/eb32sctree.h
index d0dc31b..8a8dcf1 100644
--- a/ebtree/eb32sctree.h
+++ b/ebtree/eb32sctree.h
@@ -68,52 +68,62 @@
{
struct eb_root *root;
struct eb_node *node;
+ struct eb32sc_node *eb32;
if (unlikely(!start))
return NULL;
- while (eb_gettag(start) == EB_NODE) {
- root = eb_untag(start, EB_NODE);
- node = eb_root_to_node(root);
-
- start = node->branches.b[EB_LEFT];
- if (!(container_of(node, struct eb32sc_node, node)->node_s & scope))
- start = node->branches.b[EB_RGHT];
- }
+ while (1) {
+ if (eb_gettag(start) == EB_NODE) {
+ root = eb_untag(start, EB_NODE);
+ node = eb_root_to_node(root);
+ eb32 = container_of(node, struct eb32sc_node, node);
+ if (eb32->node_s & scope) {
+ start = node->branches.b[EB_LEFT];
+ continue;
+ }
+ start = node->node_p;
+ }
+ else {
+ root = eb_untag(start, EB_LEAF);
+ node = eb_root_to_node(root);
+ eb32 = container_of(node, struct eb32sc_node, node);
+ if (eb32->leaf_s & scope)
+ return eb32;
+ start = node->leaf_p;
+ }
- /* now we have a leaf */
- node = eb_root_to_node(eb_untag(start, EB_LEAF));
- if (!(eb32sc_entry(node, struct eb32sc_node, node)->leaf_s & scope))
- return NULL;
+ /* here we're on a node that doesn't match the scope. We have
+ * to walk to the closest right location.
+ */
+ while (eb_gettag(start) != EB_LEFT)
+ /* Walking up from right branch, so we cannot be below root */
+ start = (eb_root_to_node(eb_untag(start, EB_RGHT)))->node_p;
- return eb32sc_entry(node, struct eb32sc_node, node);
+ /* Note that <start> cannot be NULL at this stage */
+ root = eb_untag(start, EB_LEFT);
+ start = root->b[EB_RGHT];
+ if (eb_clrtag(start) == NULL)
+ return NULL;
+ }
}
/* Return next node in the tree, or NULL if none */
static inline struct eb32sc_node *eb32sc_next(struct eb32sc_node *eb32, unsigned long scope)
{
- struct eb_root *root;
struct eb_node *node = &eb32->node;
eb_troot_t *t = node->leaf_p;
- while (1) {
- while (eb_gettag(t) != EB_LEFT)
- /* Walking up from right branch, so we cannot be below root */
- t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
+ while (eb_gettag(t) != EB_LEFT)
+ /* Walking up from right branch, so we cannot be below root */
+ t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
- /* Note that <t> cannot be NULL at this stage */
- root = eb_untag(t, EB_LEFT);
- t = root->b[EB_RGHT];
- if (eb_clrtag(t) == NULL)
- return NULL;
+ /* Note that <t> cannot be NULL at this stage */
+ t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
+ if (eb_clrtag(t) == NULL)
+ return NULL;
- /* we can't be below the root here */
- eb32 = eb32sc_walk_down_left(t, scope);
- if (eb32)
- return eb32;
- /* not found below, this means we have to go up */
- t = eb_root_to_node(root)->node_p;
- }
+ return eb32sc_walk_down_left(t, scope);
}
/* Return leftmost node in the tree, or NULL if none */