BUG/MEDIUM: pattern: only visit equivalent nodes when skipping versions
Miroslav reported in issue #1802 a problem that affects atomic map/acl
updates. During an update, incorrect versions are properly skipped, but
in order to do so, we rely on ebmb_next() instead of ebmb_next_dup().
This means that if a new matching entry is in the process of being
added and is the first one to succeed in the lookup, we'll skip it due
to its version and use the next entry regardless of its value provided
that it has the correct version. For IP addresses and string prefixes
it's particularly visible because a lookup may match a new longer prefix
that's not yet committed (e.g. 11.0.0.1 would match 11/8 when 10/7 was
the only committed one), and skipping it could end up on 12/8 for
example. As soon as a commit for the last version happens, the issue
disappears.
This problem only affects tree-based matches: the "str", "ip", and "beg"
matches.
Here we replace the ebmb_next() values with ebmb_next_dup() for exact
string matches, and with ebmb_lookup_shorter() for longest matches,
which will first visit duplicates, then look for shorter prefixes. This
relies on previous commit:
MINOR: ebtree: add ebmb_lookup_shorter() to pursue lookups
Both need to be backported to 2.4, where the generation ID was added.
Note that nowadays a simpler and more efficient approach might be employed,
by having a single version in the current tree, and a list of trees per
version. Manipulations would look up the tree version and work (and lock)
only in the relevant trees, while normal operations would be performed on
the current tree only. Committing would just be a matter of swapping tree
roots and deleting old trees contents.
(cherry picked from commit 51d38a26fed4eb57015030dfbc57f1c5f394f184)
Signed-off-by: Willy Tarreau <w@1wt.eu>
(cherry picked from commit 63446ead9ce9748bb0a10797a9d45db1d5e2623b)
Signed-off-by: Willy Tarreau <w@1wt.eu>
(cherry picked from commit 6b2f2e66d01bf35dccce23a33e8c32051a6572ed)
Signed-off-by: Willy Tarreau <w@1wt.eu>
diff --git a/src/pattern.c b/src/pattern.c
index 265b05f..417841b 100644
--- a/src/pattern.c
+++ b/src/pattern.c
@@ -476,7 +476,7 @@
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
if (elt->ref->gen_id != expr->ref->curr_gen) {
- node = ebmb_next(node);
+ node = ebmb_next_dup(node);
continue;
}
if (fill) {
@@ -671,7 +671,7 @@
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
if (elt->ref->gen_id != expr->ref->curr_gen) {
- node = ebmb_next(node);
+ node = ebmb_lookup_shorter(node);
continue;
}
if (fill) {
@@ -982,7 +982,7 @@
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
if (elt->ref->gen_id != expr->ref->curr_gen) {
- node = ebmb_next(node);
+ node = ebmb_lookup_shorter(node);
continue;
}
if (fill) {
@@ -1008,7 +1008,7 @@
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
if (elt->ref->gen_id != expr->ref->curr_gen) {
- node = ebmb_next(node);
+ node = ebmb_lookup_shorter(node);
continue;
}
if (fill) {
@@ -1032,7 +1032,7 @@
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
if (elt->ref->gen_id != expr->ref->curr_gen) {
- node = ebmb_next(node);
+ node = ebmb_lookup_shorter(node);
continue;
}
if (fill) {
@@ -1069,7 +1069,7 @@
while (node) {
elt = ebmb_entry(node, struct pattern_tree, node);
if (elt->ref->gen_id != expr->ref->curr_gen) {
- node = ebmb_next(node);
+ node = ebmb_lookup_shorter(node);
continue;
}
if (fill) {