[BUG] ebtree: fix duplicate strings insertion
(update to ebtree 6.0.4)
Recent fix fd301cc1370cd4977fe175dfa4544c7dc0e7ce6b was not OK because it
was returning one excess byte, causing some duplicates not to be detected.
The reason is that we added 8 bits to count the trailing zero but they
were implied by the pre-incrementation of the pointer.
Fixing this was still not enough, as the problem appeared when
string_equal_bits() was applied on two identical strings, and it returned
a number of bits covering the trailing zero. Subsequent calls were applied
to the first byte after this trailing zero. It was often zero when doing
insertion from raw files, explaining why the issue was not discovered
earlier. But when the data is from a reused area, duplicate strings are not
correctly detected when inserting into the tree.
Several solutions were tested, and the only efficient one consists in making
string_equal_bits() notify the caller that the end of the string was reached.
It now returns zero and the callers just have to ensure that when they get a
zero, they stop using that bit until a dup tree or a leaf is encountered.
This fix brought the unexpected bonus of simplifying the insertion code a bit
and making it slightly faster to process duplicates.
The impact for haproxy was that if many similar string patterns were loaded
from a file, there was a potential risk that their insertion or matching could
have been slower. The bigger impact was with the URL sorting feature of halog,
which is not yet merged and is how this bug was discovered.
(cherry picked from commit 518d59ec9ba43705f930f9ece3749c450fd005df)
diff --git a/ebtree/ebsttree.h b/ebtree/ebsttree.h
index f15af38..5c52d6e 100644
--- a/ebtree/ebsttree.h
+++ b/ebtree/ebsttree.h
@@ -78,10 +78,24 @@
return node;
}
- /* OK, normal data node, let's walk down */
- bit = string_equal_bits(x, node->key, bit);
- if (bit < node_bit)
- return NULL; /* no more common bits */
+ /* OK, normal data node, let's walk down but don't compare data
+ * if we already reached the end of the key.
+ */
+ if (likely(bit >= 0)) {
+ bit = string_equal_bits(x, node->key, bit);
+ if (likely(bit < node_bit)) {
+ if (bit >= 0)
+ return NULL; /* no more common bits */
+
+ /* bit < 0 : we reached the end of the key. If we
+ * are in a tree with unique keys, we can return
+ * this node. Otherwise we have to walk it down
+ * and stop comparing bits.
+ */
+ if (eb_gettag(root->b[EB_RGHT]))
+ return node;
+ }
+ }
troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
(~node_bit & 7)) & 1];
@@ -158,32 +172,41 @@
*
* The last two cases can easily be partially merged.
*/
- bit = string_equal_bits(new->key, old->key, bit);
- diff = cmp_bits(new->key, old->key, bit);
+ if (bit >= 0)
+ bit = string_equal_bits(new->key, old->key, bit);
- if (diff < 0) {
- new->node.leaf_p = new_left;
- old->node.leaf_p = new_rght;
- new->node.branches.b[EB_LEFT] = new_leaf;
- new->node.branches.b[EB_RGHT] = old_leaf;
- } else {
+ if (bit < 0) {
+ /* key was already there */
+
/* we may refuse to duplicate this key if the tree is
* tagged as containing only unique keys.
*/
- if (diff == 0 && eb_gettag(root_right))
+ if (eb_gettag(root_right))
return old;
- /* new->key >= old->key, new goes the right */
+ /* new arbitrarily goes to the right and tops the dup tree */
old->node.leaf_p = new_left;
new->node.leaf_p = new_rght;
new->node.branches.b[EB_LEFT] = old_leaf;
new->node.branches.b[EB_RGHT] = new_leaf;
+ new->node.bit = -1;
+ root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
+ return new;
+ }
- if (diff == 0) {
- new->node.bit = -1;
- root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
- return new;
- }
+ diff = cmp_bits(new->key, old->key, bit);
+ if (diff < 0) {
+ /* new->key < old->key, new takes the left */
+ new->node.leaf_p = new_left;
+ old->node.leaf_p = new_rght;
+ new->node.branches.b[EB_LEFT] = new_leaf;
+ new->node.branches.b[EB_RGHT] = old_leaf;
+ } else {
+ /* new->key > old->key, new takes the right */
+ old->node.leaf_p = new_left;
+ new->node.leaf_p = new_rght;
+ new->node.branches.b[EB_LEFT] = old_leaf;
+ new->node.branches.b[EB_RGHT] = new_leaf;
}
break;
}
@@ -199,23 +222,36 @@
* the current node's because as long as they are identical, we
* know we descend along the correct side.
*/
- if (old_node_bit < 0) {
- /* we're above a duplicate tree, we must compare till the end */
- bit = string_equal_bits(new->key, old->key, bit);
- goto dup_tree;
- }
- else if (bit < old_node_bit) {
+ if (bit >= 0 && (bit < old_node_bit || old_node_bit < 0))
bit = string_equal_bits(new->key, old->key, bit);
- }
- if (bit < old_node_bit) { /* we don't have all bits in common */
- /* The tree did not contain the key, so we insert <new> before the node
- * <old>, and set ->bit to designate the lowest bit position in <new>
- * which applies to ->branches.b[].
+ if (unlikely(bit < 0)) {
+ /* Perfect match, we must only stop on head of dup tree
+ * or walk down to a leaf.
+ */
+ if (old_node_bit < 0) {
+ /* We know here that string_equal_bits matched all
+ * bits and that we're on top of a dup tree, then
+ * we can perform the dup insertion and return.
+ */
+ struct eb_node *ret;
+ ret = eb_insert_dup(&old->node, &new->node);
+ return container_of(ret, struct ebmb_node, node);
+ }
+ /* OK so let's walk down */
+ }
+ else if (bit < old_node_bit || old_node_bit < 0) {
+ /* The tree did not contain the key, or we stopped on top of a dup
+ * tree, possibly containing the key. In the former case, we insert
+ * <new> before the node <old>, and set ->bit to designate the lowest
+ * bit position in <new> which applies to ->branches.b[]. In the later
+ * case, we add the key to the existing dup tree. Note that we cannot
+ * enter here if we match an intermediate node's key that is not the
+ * head of a dup tree.
*/
eb_troot_t *new_left, *new_rght;
eb_troot_t *new_leaf, *old_node;
- dup_tree:
+
new_left = eb_dotag(&new->node.branches, EB_LEFT);
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
@@ -223,6 +259,7 @@
new->node.node_p = old->node.node_p;
+ /* we can never match all bits here */
diff = cmp_bits(new->key, old->key, bit);
if (diff < 0) {
new->node.leaf_p = new_left;
@@ -230,17 +267,12 @@
new->node.branches.b[EB_LEFT] = new_leaf;
new->node.branches.b[EB_RGHT] = old_node;
}
- else if (diff > 0) {
+ else {
old->node.node_p = new_left;
new->node.leaf_p = new_rght;
new->node.branches.b[EB_LEFT] = old_node;
new->node.branches.b[EB_RGHT] = new_leaf;
}
- else {
- struct eb_node *ret;
- ret = eb_insert_dup(&old->node, &new->node);
- return container_of(ret, struct ebmb_node, node);
- }
break;
}
@@ -258,6 +290,7 @@
/* We need the common higher bits between new->key and old->key.
* This number of bits is already in <bit>.
+ * NOTE: we can't get here whit bit < 0 since we found a dup !
*/
new->node.bit = bit;
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);