BUG: ebtree: ebst_lookup() could return the wrong entry
(from ebtree 6.0.7)
Julien Thomas provided a reproducible test case where a string lookup
could return the wrong node. The issue is caused by the jump to a node
which contains less bit in common than the previous node, making the
string_equal_bits() function return -1. We must not remember more bits
than the number on the node, otherwise we can be tempted to trust them
while they can change while running down.
For a valid test case, enter : "0", "WW", "W", "S", and lookup "W".
Previously, "S" was returned.
Note: string-based ebtrees are used in haproxy in ACL, peers and
stick-tables. ACLs are not affected because all patterns are
interchangeable. stick-tables are not affected because lookups are
performed using ebmb_lookup(). Only peers might be affected though
it is not easy to infirm or confirm the issue.
(cherry picked from commit dd47a54103597458887d3cc8414853a541aee9c1)
diff --git a/ebtree/ebistree.h b/ebtree/ebistree.h
index cfa0de0..a1fbb76 100644
--- a/ebtree/ebistree.h
+++ b/ebtree/ebistree.h
@@ -113,6 +113,14 @@
if (eb_gettag(root->b[EB_RGHT]))
return node;
}
+ /* if the bit is larger than the node's, we must bound it
+ * because we might have compared too many bytes with an
+ * inappropriate leaf. For a test, build a tree from "0",
+ * "WW", "W", "S" inserted in this exact sequence and lookup
+ * "W" => "S" is returned without this assignment.
+ */
+ else
+ bit = node_bit;
}
troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
diff --git a/ebtree/ebsttree.h b/ebtree/ebsttree.h
index 511fb7a..f86101d 100644
--- a/ebtree/ebsttree.h
+++ b/ebtree/ebsttree.h
@@ -110,6 +110,14 @@
if (eb_gettag(root->b[EB_RGHT]))
return node;
}
+ /* if the bit is larger than the node's, we must bound it
+ * because we might have compared too many bytes with an
+ * inappropriate leaf. For a test, build a tree from "0",
+ * "WW", "W", "S" inserted in this exact sequence and lookup
+ * "W" => "S" is returned without this assignment.
+ */
+ else
+ bit = node_bit;
}
troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>