Re: Splay tree bug possibly solved

In article <373B1CE7.67A27A20@hem.passagen.se> Henrik wrote:

>The current implementation of SPLAY lists can't handle overlapping
>regions, and will have unpredictable results when such ACL lists are
>seen. Things may first appear to work (or not), and later change as the
>tree reorganises itself.
>
>Today it is assumed that ACL lists are valid and does not contain
>overlapping regions. Adding safeguard checks for this to Squid is

I don't like this assumption :-). My Squid ACL lists are created from a
lot of different sources and are almost guaranteed to contain overlaps.
I've backported the linked list code from Squid 1.1 to 2.2.STABLE2 for
IP and domain acls until I have a real solution.

>nontrivial as how to do the checks depends on the ACL type and order of
>entries, but it is certainly doable.

Indeed. I've implemented a possible solution and am now testing it. I
still need to do a lot of code cleanups and tests before I can publish
it as a patch for 2.2.STABLE2.

The solution has been implemented in a generic way. For each problematic
data type you need to have a function which can determine whether for a
given A and B, A is a 'subset' of B or B is a 'subset' of A. Based on
this a splay tree can be made without overlapping entries.

splay_insert gets two extra parameters (a subset function and a free
function), splay_splay gets one extra parameter (a subset function
only). By using NULL as subset function one gets the original behavior.

The only remaining overlapping entries which can give problems are
things like:

        172.16.1.1-172.16.1.10 and 172.16.1.4-172.16.1.14

It could be that during the building of the splay tree one can change
these records into

        172.16.1.1-172.16.1.10 and 172.16.1.11-172.16.1.14

as soon as the overlap is detected but I'm not sure yet whether this has
side effects later on. And it's quite ugly to do this of course.

Arjan
Received on Sun May 16 1999 - 11:07:08 MDT