BUG: ebtree: ebst_lookup() could return the wrong entry
authorWilly Tarreau <w@1wt.eu>
Mon, 14 Nov 2011 13:09:27 +0000 (14:09 +0100)
committerWilly Tarreau <w@1wt.eu>
Fri, 2 Dec 2011 16:09:50 +0000 (17:09 +0100)
commit007257ebab378d260c8a0d6b53d1916f9d4fc174
treefc27415b2fef2455a86a4247fea225705f3718ab
parent6258f7b883ba3b9dd15a71d17cb8323301283a47
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)
ebtree/ebistree.h
ebtree/ebsttree.h