BUG/MEDIUM: ebtree: ebmb_insert() must not call cmp_bits on full-length matches
Otherwise we end up comparing the byte past the end, resulting
in duplicate values still being inserted into the tree even if
undesired.
This generally has low impact, though it can sometimes cause one new entry
to be added next to an existing one for stick tables, preventing the results
from being merged.
(cherry picked from commit 12e54ac493a91bb02064568f410592c2700d3933)
diff --git a/ebtree/ebimtree.h b/ebtree/ebimtree.h
index b40e490..1fe9fa0 100644
--- a/ebtree/ebimtree.h
+++ b/ebtree/ebimtree.h
@@ -198,7 +198,14 @@
* The last two cases can easily be partially merged.
*/
bit = equal_bits(new->key, old->key, bit, len);
- diff = cmp_bits(new->key, old->key, bit);
+
+ /* Note: we can compare more bits than the current node's because as
+ * long as they are identical, we know we descend along the correct
+ * side. However we don't want to start to compare past the end.
+ */
+ diff = 0;
+ if (((unsigned)bit >> 3) < len)
+ diff = cmp_bits(new->key, old->key, bit);
if (diff < 0) {
new->node.leaf_p = new_left;
@@ -263,7 +270,14 @@
new->node.node_p = old->node.node_p;
- diff = cmp_bits(new->key, old->key, bit);
+ /* Note: we can compare more bits than the current node's because as
+ * long as they are identical, we know we descend along the correct
+ * side. However we don't want to start to compare past the end.
+ */
+ diff = 0;
+ if (((unsigned)bit >> 3) < len)
+ diff = cmp_bits(new->key, old->key, bit);
+
if (diff < 0) {
new->node.leaf_p = new_left;
old->node.node_p = new_rght;
diff --git a/ebtree/ebmbtree.h b/ebtree/ebmbtree.h
index 121c59f..fa25ac5 100644
--- a/ebtree/ebmbtree.h
+++ b/ebtree/ebmbtree.h
@@ -306,12 +306,16 @@
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
- /* Note: we can compare more bits than
- * the current node's because as long as they are identical, we
- * know we descend along the correct side.
- */
new->node.bit = bit;
- diff = cmp_bits(new->key, old->key, bit);
+
+ /* Note: we can compare more bits than the current node's because as
+ * long as they are identical, we know we descend along the correct
+ * side. However we don't want to start to compare past the end.
+ */
+ diff = 0;
+ if (((unsigned)bit >> 3) < len)
+ diff = cmp_bits(new->key, old->key, bit);
+
if (diff == 0) {
new->node.bit = -1; /* mark as new dup tree, just in case */