[Dnsmasq-discuss] Dnsmasq with Gigantic hosts file

[Preston Crow]

I'm running dnsmasq with a large hosts file, and it's taking about a
minute to start up, which doesn't seem right. Specifically, for the
first minute while it is initializing, it does not respond to DNS
requests. If I attach to it with strace, I see it doing a sequence of
4K reads of the hosts file, and I can see it slowing down as it
progresses. After every 8 reads, there is one brk() syscall.

I assume that the slow part is in processing the hosts that it's reading.

My setup is using only DNS, no DHCP. I have two hosts files, the first
is short, only 1116 bytes, but the second is over 1MB and includes over
50,000 entries.

If you're curious, the second file is a copy of the NIS hosts file, as
I've had performance problems with NIS over VPN, so I grab it
occasionally and serve it locally. It works great once it's
initialized, but this is my laptop, not an always-up server, so the
extra minute is painful. (It's a new high-end laptop with tons of
memory, fast CPU, and an SSD, so it I shouldn't hit any issues there.)

[r***@gmail.com]

I'm running dnsmasq with a large hosts file, and it's taking about a minute
to start up, which doesn't seem right.  Specifically, for the first minute
while it is initializing, it does not respond to DNS requests.  If I attach
to it with strace, I see it doing a sequence of 4K reads of the hosts file,
and I can see it slowing down as it progresses.  After every 8 reads, there
is one brk() syscall.
I assume that the slow part is in processing the hosts that it's reading.

[snip]

Any suggestions for how to fix this?

Small host file and use DBus to feed in all the other entries?

[Jan Seiffert]

I'm running dnsmasq with a large hosts file, and it's taking about a minute
to start up, which doesn't seem right.  Specifically, for the first minute
while it is initializing, it does not respond to DNS requests.  If I attach
to it with strace, I see it doing a sequence of 4K reads of the hosts file,
and I can see it slowing down as it progresses.  After every 8 reads, there
is one brk() syscall.
I assume that the slow part is in processing the hosts that it's reading.
My setup is using only DNS, no DHCP.  I have two hosts files, the first is
short, only 1116 bytes, but the second is over 1MB and includes over 50,000
entries.

I can only offer 450kbyte, 15k entries, but it reads it in, don't know, seconds?
Something must be "different".

If you're curious, the second file is a copy of the NIS hosts file,

NIS ...
hmmm, all hosts of the same domain?

Simon, i already forgot how the cache works, could this be a massive
hash collision?

[snip]

(It's a
new high-end laptop with tons of memory, fast CPU, and an SSD, so it I
shouldn't hit any issues there.)

i have dnsmasq on an Sempron, so it is bigger/faster than one of those
Atom/ARM, but still small compared with your laptop.
Frequency scaling setting it to slowest frequency?

[Simon Kelley]

Post by Jan Seiffert

Post by Preston Crow
If you're curious, the second file is a copy of the NIS hosts file,

NIS ...
hmmm, all hosts of the same domain?
Simon, i already forgot how the cache works, could this be a massive
hash collision?

It's possible, but I have another hypothesis: the performance fixes back
in 2007 are predicated on most entries in massive host files for the
same IP address. That's reasonable because all of the really big
hostsfiles we were seeing were for ad-blocking, and mapped nearly all
the domains to 127.0.0.1 or 0.0.0.0

Part of the read-in process does a reverse lookup on the previously-read
entries. This is needed because only the first occurrence of an IP
address is used for reverse mapping, so


domain1.com 1.2.3.4
domain2.com 1.2.3.4

both domain1.com and domian2.com forward-map to 1.2.3.4, but 1.2.3.4
only backwards maps to domain1.com

To implement this, as each line is read in a host file, the address is
looked up in the cache to determine if it's been seen before. As the
cache is NOT hashed for by-address lookups, this is an O(n) operation,
and reading a hostfile is O(n^2) worst-case.

The 2007 speedup simply checks to see if the address on this line is the
same as the address in the previous line. If so we know it's a duplicate
in O(1) time and avoid the O(n) lookup. Works brilliantly when almost
all addresses are the same, but won't help for a file full of distinct
addresses.

Post by Jan Seiffert
[snip]

Post by Preston Crow
(It's a
new high-end laptop with tons of memory, fast CPU, and an SSD, so it I
shouldn't hit any issues there.)

memory and disk are almost certainly not relevant, and any CPU in the
universe will be overwhelmed eventually by an O(n^2) algorithm.

[Jan Seiffert]

2012/1/11 Simon Kelley <***@thekelleys.org.uk>:
[snip]

Post by Simon Kelley
To implement this, as each line is read in a host file, the address is
looked up in the cache to determine if it's been seen before. As the cache
is NOT hashed for by-address lookups, this is an O(n) operation, and reading
a hostfile is O(n^2) worst-case.

Ouch!

[snip]

Post by Simon Kelley
Try commenting out the code around line 650 in cache.c which starts with a
big comment block explaining the tweak I mention above, starting
/* Ensure there is only one address -> name mapping (first one trumps)
If goes fast then I've guessed right. Assuming I have, there are various
solutions: add hashing for by-adddress cache lookups,

Should i refresh my reverse tree code?
Nice thing was it was so unintrusive, so small device could disable it,

Preston, which version are you running, or can you run the latest version?

Post by Simon Kelley
We can argue about that once we know it's the correct issue.

Sure

Post by Simon Kelley
HTH
Simon.

Greetings
Jan

[Simon Kelley]

Post by r***@gmail.com
[snip]

Post by Simon Kelley
To implement this, as each line is read in a host file, the address is
looked up in the cache to determine if it's been seen before. As the cache
is NOT hashed for by-address lookups, this is an O(n) operation, and reading
a hostfile is O(n^2) worst-case.

Ouch!
[snip]

Post by Simon Kelley
Try commenting out the code around line 650 in cache.c which starts with a
big comment block explaining the tweak I mention above, starting
/* Ensure there is only one address -> name mapping (first one trumps)
If goes fast then I've guessed right. Assuming I have, there are various
solutions: add hashing for by-adddress cache lookups,

Should i refresh my reverse tree code?
Nice thing was it was so unintrusive, so small device could disable it,

Remind me: I remember the regex patch, but not that one.

I've thought about this a bit more, and I think it's pretty easy to hash
the addresses only during the process of reading hostsfiles with
basically no extra resource: There is a pointer field in cache entries
which is unused at that time, and could be used to hold an open-hash
chain. All that's needed is an array of pointers, one per hash bucket,
which can be freed once files are read.

Post by r***@gmail.com
Preston, which version are you running, or can you run the latest version?

and a further question, can you send me a copy of our hosts file? It's
easy to benchmark accurately if we have real data.



Cheers,

Simon.

[Jan Seiffert]

[snip]

Post by Simon Kelley

Post by Jan Seiffert

Post by Simon Kelley
Try commenting out the code around line 650 in cache.c which starts with a
big comment block explaining the tweak I mention above, starting
/* Ensure there is only one address ->  name mapping (first one trumps)
If goes fast then I've guessed right. Assuming I have, there are various
solutions: add hashing for by-adddress cache lookups,

Should i refresh my reverse tree code?
Nice thing was it was so unintrusive, so small device could disable it,

Remind me: I remember the regex patch, but not that one.

The patch in:
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2007q1/001120.html
Or should i attach it again?

Post by Simon Kelley
I've thought about this a bit more, and I think it's pretty easy to hash the
addresses only during the process of reading hostsfiles with basically no
extra resource: There is a pointer field in cache entries which is unused at
that time, and could be used to hold an open-hash chain. All that's needed
is an array of pointers, one per hash bucket, which can be freed once files
are read.

*mumbel, mumbel*
While i envy your genius, and are intrigued by the nifty trick, this
is on the verge of ... insanity?

Ok, ok, a reverse tree is "complicated", but would put the whole
reverse thing to rest, also during runtime.
I mean now Preston seems to be slowed down during read in, but i guess
later reverse lookups will also not be fast due to the sheer number of
unique IP/hosts.

[snip]

Post by Simon Kelley
Cheers,
Simon.

Greetings
Jan

[Simon Kelley]

Post by r***@gmail.com
[snip]

Post by Simon Kelley

Post by Simon Kelley
Try commenting out the code around line 650 in cache.c which
starts with a big comment block explaining the tweak I mention
above, starting
/* Ensure there is only one address -> name mapping (first one trumps)
If goes fast then I've guessed right. Assuming I have, there
are various solutions: add hashing for by-adddress cache
lookups,

Should i refresh my reverse tree code? Nice thing was it was so
unintrusive, so small device could disable it,

Remind me: I remember the regex patch, but not that one.

http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2007q1/001120.html

Or should i attach it again?

Got it, thanks.

Post by r***@gmail.com

Post by Simon Kelley
I've thought about this a bit more, and I think it's pretty easy to
hash the addresses only during the process of reading hostsfiles
with basically no extra resource: There is a pointer field in cache
entries which is unused at that time, and could be used to hold an
open-hash chain. All that's needed is an array of pointers, one per
hash bucket, which can be freed once files are read.

*mumbel, mumbel* While i envy your genius, and are intrigued by the
nifty trick, this is on the verge of ... insanity?

We eat insanity for breakfast round here.

Post by r***@gmail.com
Ok, ok, a reverse tree is "complicated", but would put the whole
reverse thing to rest, also during runtime.

Tree is good, because it works for lookup too. Downside is extra memory
use, and malloc/free during cache operation: dnsmasq at the moment is
written so that it never calls malloc/free during DNS operations - saves
memory fragmentation, especially in MMU-less systems (Do they still exist?)

Post by r***@gmail.com
I mean now Preston seems to be slowed down during read in, but i
guess later reverse lookups will also not be fast due to the sheer
number of unique IP/hosts.

ash-during-read doesn't cost extra memory and doesn't do malloc, but it
won't speed up reverse operations. This isn't normally a problem, even
for gigantic hosts files, since the lookup cost is limited by the number
of _reverse_ entries in the cache. For ad-blocking gigantic hosts files,
almost none of the entries are reverse, so no problem. For Preston's
workload, it maybe moreso, but reverse lookups are much less frequent
than forward ones on most systems, so it may still be OK.

Simon.

[Jan Seiffert]

[snip]

Post by Simon Kelley

Post by r***@gmail.com

Post by Simon Kelley
I've thought about this a bit more, and I think it's pretty easy to
hash the addresses only during the process of reading hostsfiles
with basically no extra resource: There is a pointer field in cache
entries which is unused at that time, and could be used to hold an
open-hash chain. All that's needed is an array of pointers, one per
hash bucket, which can be freed once files are read.

*mumbel, mumbel* While i envy your genius, and are intrigued by the
nifty trick, this is on the verge of ... insanity?

We eat insanity for breakfast round here.

Yummy!
*crunch crunch*
Can you pass me the milk, please?

Post by Simon Kelley

Post by r***@gmail.com
Ok, ok, a reverse tree is "complicated", but would put the whole
reverse thing to rest, also during runtime.

Tree is good, because it works for lookup too. Downside is extra memory
use, and malloc/free during cache operation: dnsmasq at the moment is
written so that it never calls malloc/free during DNS operations - saves
memory fragmentation

It is written so the tree grows and shrinks dynamically, but only to
the needed extend, and after that i prop. would be rather static,
allocating a tree node here, freeing one there. I expect no massiv malloc mania.
If this would fragment your memory, then your allocator is bad...

But thats the beauty, the code is on-off switchable.
So operators on normal systems (installed from distro) would turn it
on, on plastic-box-router turn it off.

Post by Simon Kelley
, especially in MMU-less systems (Do they still exist?)

Sure, they do, but i guess they are fading into so low cost market
segments, that dnsmasq is out of the question.
(i heard those "can't do sh..."-router are not using Linux or *BSD,
because it is to big, saving on 2Mbyte of flash and 4Mbyte RAM)

Post by Simon Kelley

Post by r***@gmail.com
I mean now Preston seems to be slowed down during read in, but i
guess later reverse lookups will also not be fast due to the sheer
number of unique IP/hosts.

ash-during-read doesn't cost extra memory and doesn't do malloc, but it
won't speed up reverse operations. This isn't normally a problem, even
for gigantic hosts files, since the lookup cost is limited by the number
of _reverse_ entries in the cache. For ad-blocking gigantic hosts files,
almost none of the entries are reverse, so no problem.

Yes, that solved the problem last time, so i didn't take the patch
from back then any further...

Post by Simon Kelley
For Preston's
workload, it maybe moreso, but reverse lookups are much less frequent
than forward ones on most systems, so it may still be OK.

... but the underlying problem that reverse lookup are implemented ...
suboptimal, remains.
Even if they are less frequent, Preston is with his use case (cache a
subnet because it is flaky)
nearing the wall we predicted back then.
If i remember right, the main problem back then was that even a single
reverse lookup (say Windows smb or other stuff) in a lot of forward
lookups could slow everything down dramatically because dnsmasq is
synchronous (which is a good thing).

Post by Simon Kelley
Simon.

Greetings
Jan

[Preston Crow]

Post by Jan Seiffert

Post by Jan Seiffert
Should i refresh my reverse tree code?
Nice thing was it was so unintrusive, so small device could disable it,

http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2007q1/001120.html
Or should i attach it again?

I built with that patch (updating to compile with 2.59), and it made no
difference. I've attached it. Perhaps it's something simple.

I also found that if I define CONFIG_NO_REVERSE_TREE, then it doesn't
work at all, but I didn't play with that much.

[Jan Seiffert]

Post by Preston Crow

Post by Jan Seiffert
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2007q1/001120.html

I built with that patch (updating to compile with 2.59),

Thanks

Post by Preston Crow
and it made no difference.  I've attached it.  Perhaps it's something simple.

It can't work, since the slow check, the one you commented out in your
second patch, is an open coded search over the hash chains, it does
not go by any function which would use the tree.

But looking at it again: this needs generally more work.
There has to be some tuning done where to hook in the cache code. And
the cache code is complicated...

Post by Preston Crow
I also found that if I define CONFIG_NO_REVERSE_TREE, then it doesn't work
at all, but I didn't play with that much.

Huh?
With CONFIG_NO_REVERSE_TREE this should be a NOP, the code should be
in "pristine" form then....
I have to look

Greetings
Jan

[Jan Seiffert]

Post by Jan Seiffert

Post by Preston Crow

Post by Jan Seiffert
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2007q1/001120.html

I built with that patch (updating to compile with 2.59),

Thanks

Post by Preston Crow
and it made no difference.  I've attached it.  Perhaps it's something simple.

It can't work, since the slow check, the one you commented out in your
second patch, is an open coded search over the hash chains, it does
not go by any function which would use the tree.
But looking at it again: this needs generally more work.
There has to be some tuning done where to hook in the cache code. And
the cache code is complicated...

Ok, i looked at it, here is a new version.
It should now use the reverse tree on hosts insert and generally fixes
some errors in the code.
Just for fun and reference, only compile tested.
Why it does not work without the reverse tree enables, i can't see it.

Anyway, Simon was faster. Master of the hash tables ;)

Greetings
Jan

[Preston Crow]

That works perfectly for me. Putting a lookup as a command on the same
line following the restart sees the results.
/etc/init.d/dnsmasq restart ; host google.com
No visible delay at all.

Thanks for the help on this!

Post by Jan Seiffert

Post by Jan Seiffert

Post by Preston Crow

Post by Jan Seiffert
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2007q1/001120.html

I built with that patch (updating to compile with 2.59),

Thanks

Post by Preston Crow
and it made no difference. I've attached it. Perhaps it's something simple.

It can't work, since the slow check, the one you commented out in your
second patch, is an open coded search over the hash chains, it does
not go by any function which would use the tree.
But looking at it again: this needs generally more work.
There has to be some tuning done where to hook in the cache code. And
the cache code is complicated...

Ok, i looked at it, here is a new version.
It should now use the reverse tree on hosts insert and generally fixes
some errors in the code.
Just for fun and reference, only compile tested.
Why it does not work without the reverse tree enables, i can't see it.
Anyway, Simon was faster. Master of the hash tables ;)
Greetings
Jan
_______________________________________________
Dnsmasq-discuss mailing list
http://lists.thekelleys.org.uk/mailman/listinfo/dnsmasq-discuss

[Preston Crow]

Post by Simon Kelley
and a further question, can you send me a copy of our hosts file? It's
easy to benchmark accurately if we have real data.

Since it's the internal corporate host names and IP addresses, it's not
something that I can distribute. Just generate 50,000 or so random host
names and IP addresses, and you'll see the same problem.

And I apologize for all the slow replies--I sent the initial email just
before leaving town, which in retrospect was not the wisest timing.

[Simon Kelley]

Post by Preston Crow

Post by Simon Kelley
and a further question, can you send me a copy of our hosts file? It's
easy to benchmark accurately if we have real data.

Since it's the internal corporate host names and IP addresses, it's not
something that I can distribute. Just generate 50,000 or so random host
names and IP addresses, and you'll see the same problem.
And I apologize for all the slow replies--I sent the initial email just
before leaving town, which in retrospect was not the wisest timing.

could you try

<http://www.thekelleys.org.uk/dnsmasq/test-releases/dnsmasq-2.60test10.tar.gz>

That starts with ~18000 names from the hosts file at work in less than a
second on a 3Ghz P4


Cheers,

Simon.

[Preston Crow]

Post by Simon Kelley
Try commenting out the code around line 650 in cache.c which starts with
a big comment block explaining the tweak I mention above, starting
/* Ensure there is only one address -> name mapping (first one trumps)
If goes fast then I've guessed right. Assuming I have, there are various
solutions: add hashing for by-adddress cache lookups, stipulate that big
hostfiles should be sorted by address so that we can rely on the
adjacent-line test without falling back to the slow exhaustive search,
abandon the "first-appearance-of-address is used for reverse lookups"
semantics, declare it a non-problem.
We can argue about that once we know it's the correct issue.

Yup, that causes my hosts file to be read instantly.

I attached the patch that I applied. I left the check verses the
previous entry intact.

In my case, this is perfect, as I clean up the hosts file from NIS a bit
with a script (it's a mess), then sort it. So one approach would be to
remove that code, and add a sort of the hosts file before processing it.

[Dan White]

BTW, !!SIMON!! There is an easy path to dump the previous archives into Mail Archive:
http://www.mail-archive.com/faq.html#import

OK, now to my question:
I have a Cobbler Server that was constructed to simplify/centralize/standardize setting up new machines.

For Cobbler to "do its thing" properly, I need to be able to have a DHCP server configured to allow me to PXE-boot/net-load machines. The DHCP Server is a Microsoft box, under the control of of an extreme Linux-phobe. When I can get him to create a DHCP reservation for me with the appropriate PXE information, my server works great, but getting him to create/edit the DHCP entries is like pulling teeth without drugs.

I have found hints that dnsmasq can:

* Serve DHCP only
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2011q1/004687.html

* Serve DHCP as a proxy thus piecefully co-existing with another DCHP server on the network
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2011q1/004673.html
http://lists.thekelleys.org.uk/pipermail/dnsmasq-discuss/2011q2/004987.html

But I have not found sufficient info to be comfortable enough to try it.

“Sometimes I think the surest sign that intelligent life exists elsewhere in the universe is that none of it has tried to contact us.”
Bill Waterson (Calvin & Hobbes)