]> git.ipfire.org Git - thirdparty/bind9.git/commit
yet another fix_iterator() bug
authorEvan Hunt <each@isc.org>
Wed, 10 Apr 2024 20:13:48 +0000 (16:13 -0400)
committerEvan Hunt <each@isc.org>
Thu, 25 Apr 2024 17:29:07 +0000 (10:29 -0700)
commit2dff9266248928729a44bd0e7b525941a4187407
tree88e89e7e3f6e79abea5f92fd0d8296944cb296f0
parentb1184d916d2410ba4dd5ae928e5bb0e51a752e4c
yet another fix_iterator() bug

under some circumstances it was possible for the iterator to
be set to the first leaf in a set of twigs, when it should have
been set to the last.

a unit test has been added to test this scenario. if there is a
a tree containing the following values: {".", "abb.", "abc."}, and
we query for "acb.", previously the iterator would be positioned at
"abb." instead of "abc.".

the tree structure is:
    branch (offset 1, ".")
      branch (offset 3, ".ab")
        leaf (".abb")
        leaf (".abc")

we find the branch with offset 3 (indicating that its twigs differ
from each other in the third position of the label, "abB" vs "abC").
but the search key differs from the found keys at position 2
("aC" vs "aB").  we look up the bit value in position 3 of the
search key ("B"), and incorrectly follow it onto the wrong twig
("abB").

to correct for this, we need to check for the case where the search
key is greater than the found key in a position earlier than the
branch offset. if it is, then we need to pop from the current leaf
to its parent, and get the greatest leaf from there.

a further change is needed to ensure that we don't do this twice;
when we've moved to a new leaf and the point of difference between
it and the search key even earlier than before, then we're definitely
at a predecessor node and there's no need to continue the loop.
lib/dns/qp.c
tests/dns/qp_test.c