[Dnsmasq-discuss] Many immortals slow down dnsmasq. Bug or expected ?

[reiner otto]

Followin scenario:
dnsmasq runs on embedded system; many (250,000) entries like "address=/abcd/0.0.0.0/" in dnsmasq.conf
Caches in dnsmasq and browser empty.
Now, when browsing to a page with many links to other sites, page load takes more than 10sec.
Clearing browser cache, and reloading the same page, is much faster.

Using dig on the system, running dnsmasq, I see, that first name resolution takes about 400ms.
Second try takes 0ms.

Cache-size set to default or 10,000 makes no difference. cache-size=0 makes dnsmasq unbearable slow, looks like looping somewhere.

Dropping the 250,000 "address=xxx" from dnsmasq.conf, shows fast name resolution (about 25ms) for first try.

In principal, I see same effects on my faster x86-based system.


My conclusions:
Time for cache lookup is not influenced by number of IMMORTALs.
But creating a new entry in cache is badly effected by IMMORTALs.

As creating a new entry assumes checking first, whether same entry exists as IMMORTAL already, which is very like a (fast) cache-lookup, this *should* not have a noticable negative effect.
Which points to a "very slow" insertion of a new entry into hash table.

So, are my observations because of a bug or to be expected ?

[Simon Kelley]

address=/abcd/0.0.0.0/ does NOT use the cache code. There's an implied
wildcard in the domain name, it matches *.abcd. The matching for this
is a relatively slow, linear, search. It is certainly not suitable for
250000 names!

If you don't need the wildcard matching, then using

host-record=abcd,0.0.0.0

instead will make real cache entries, which are efficently searched.
That will be much, much faster.

Cheers,

Simon.

Followin scenario: dnsmasq runs on embedded system; many (250,000)
entries like "address=/abcd/0.0.0.0/" in dnsmasq.conf Caches in
dnsmasq and browser empty. Now, when browsing to a page with many
links to other sites, page load takes more than 10sec. Clearing
browser cache, and reloading the same page, is much faster.
Using dig on the system, running dnsmasq, I see, that first name
resolution takes about 400ms. Second try takes 0ms.
Cache-size set to default or 10,000 makes no difference.
cache-size=0 makes dnsmasq unbearable slow, looks like looping
somewhere.
Dropping the 250,000 "address=xxx" from dnsmasq.conf, shows fast
name resolution (about 25ms) for first try.
In principal, I see same effects on my faster x86-based system.
My conclusions: Time for cache lookup is not influenced by number
of IMMORTALs. But creating a new entry in cache is badly effected
by IMMORTALs.
As creating a new entry assumes checking first, whether same entry
exists as IMMORTAL already, which is very like a (fast)
cache-lookup, this *should* not have a noticable negative effect.
Which points to a "very slow" insertion of a new entry into hash table.
So, are my observations because of a bug or to be expected ?
_______________________________________________ Dnsmasq-discuss
http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss

[w***@gmail.com]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256
address=/abcd/0.0.0.0/ does NOT use the cache code. There's an implied
wildcard in the domain name, it matches *.abcd. The matching for this
is a relatively slow, linear, search. It is certainly not suitable for
250000 names!
If you don't need the wildcard matching, then using
host-record=abcd,0.0.0.0
instead will make real cache entries, which are efficently searched.
That will be much, much faster.

what does one do if they do need wildcard matching?

[Simon Kelley]

Post by w***@gmail.com

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256
address=/abcd/0.0.0.0/ does NOT use the cache code. There's an implied
wildcard in the domain name, it matches *.abcd. The matching for this
is a relatively slow, linear, search. It is certainly not suitable for
250000 names!
If you don't need the wildcard matching, then using
host-record=abcd,0.0.0.0
instead will make real cache entries, which are efficently searched.
That will be much, much faster.

what does one do if they do need wildcard matching?

Making the wildcard matching more efficient is on the TODO list. There
was a series of patches to do it posted here some time ago. They weren't
applied because I wanted to take the opportunity to do a larger tidy of
some very old, knarly code. I plan to do that over the coming Northern
Hemisphere winter.

Cheers,

Simon.

[r***@gmail.com]

There are some awesome data structures for simultaneously matching against
huge numbers of patterns (as opposed to literal fixed strings). dnsmasq
would get a lot more complicated if it tried to implement them, and
complication in an internet-facing daemon is a "BAD thing" because it
increases the chance that there's an exploitable bug. Since the feature
you're using is designed for something completely different from request
blocking, perhaps there should be a pluggable interface just for filtering
requests (e.g. open a pipe to an external process, just like it does for
lease script, and writes nul-separated hostnames getting back a boolean
response whether to allow or block each request). Then the external
process could be compiled for speed using antlr or bison or any other
parser generator that knows how to build the fancy state machine tables.
And buffer overflows or anything else that went seriously wrong in the
request filter couldn't impact dnsmasq -- it would just cause a broken
pipe. Because the request filter wouldn't need root access like the
leasefile script, it could respawn on SIGUSR.

Just my two cents, I'm not volunteering to write the code.

Ben

Post by w***@gmail.com

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256
address=/abcd/0.0.0.0/ does NOT use the cache code. There's an implied
wildcard in the domain name, it matches *.abcd. The matching for this
is a relatively slow, linear, search. It is certainly not suitable for
250000 names!
If you don't need the wildcard matching, then using
host-record=abcd,0.0.0.0
instead will make real cache entries, which are efficently searched.
That will be much, much faster.

what does one do if they do need wildcard matching?
--
NOTE: No off-list assistance is given without prior approval.
*Please keep mailing list traffic on the list* unless
private contact is specifically requested and granted.
_______________________________________________
Dnsmasq-discuss mailing list
http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss