Nmap Development mailing list archives
Re: [PATCH] Add the ability to generate quality random IPs without any duplicates
From: Brandon Enright <bmenrigh () ucsd edu>
Date: Wed, 9 Sep 2009 00:41:30 +0000
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tue, 8 Sep 2009 17:09:38 -0700 Fyodor <fyodor () insecure org> wrote:
On Wed, Sep 02, 2009 at 02:30:21AM +0000, Brandon Enright wrote:This change was committed in r15396. I included better documentation and links than in my original patch.Thanks, it is working well (no duplicates) in my testing.
Excellent. I spent a lot of time thinking about how to do it so I'm glad it works ;-)
I was going to boast that this generator is slightly faster than RC4 and while that's true, ip_is_reserved() is so slow the majority of the time isn't being spent in the generator. I've been thinking of ways to optimize ip_is_reserved() to make it much faster and still maintainable. If I come up with something good I'll send a patch.On my system, "nmap -sL -n -iR 1000000" generates and prints more than 75,000 IPs per second. So IP generation (even with ip_is_reserved) is already so fast as to be essentially immaterial for any scans. We need to optimize the slow parts of Nmap. But if improving ip_is_reserved makes is cleaner and easier to maintain, and improves speed as a side effect, I'm all for it. This technique might be useful for improving the port randomization code, though I'm also not sure if that time is ever material to performance. It would take the longest with a -p- scan. Cheers, -F
I take my slander of ip_is_reserved() back. I thought that the slowness was due to that routine. Turns out, most of the slowness has to do with the internal processing of a target and printing the results. 75k IPs is pretty fast taking that into account. Here's the benchmarks: With Nmap as it is right now I get 151k IP/s: $ time ./nmap -iR 10000000 -sL -n -oN - > /dev/null real 1m6.336s user 1m1.382s sys 0m2.096s If I take out is_ip_reserved() I get 161k IP/s. This isn't actually a measurable speedup because the generator needs to be called 25% less without the reserved check: $ time ./nmap -iR 10000000 -sL -n -oN - > /dev/null real 1m2.688s user 1m0.780s sys 0m1.892s But, if I make Nmap cycle the generator for each IP it returns (4.2B IPs) then I get 186M IP/s: $ time ./nmap -iR 1 -sL -n -oN - > /dev/null real 0m23.948s user 0m23.639s sys 0m0.036s I feel bad because Patrick privately sent me a new implementation of ip_is_reserved() that uses a lookup table. In thinking about it, the long case statement we have in the routine will be turned into a jmp lookup table by GCC which is mostly the same thing as Patrick's patch. So long story short, we don't (and shouldn't!) change anything. It's fast right now. Hopefully Patrick isn't too miffed... Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.11 (GNU/Linux) iEYEARECAAYFAkqm+cYACgkQqaGPzAsl94KaSgCgg4Qvxxcq3/cWvm6pA9/ntlm+ 48UAoKZ8wdhaO6kXGuuvMzEZr8dq1dwS =I7tm -----END PGP SIGNATURE----- _______________________________________________ Sent through the nmap-dev mailing list http://cgi.insecure.org/mailman/listinfo/nmap-dev Archived at http://SecLists.Org
Current thread:
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates, (continued)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates David Fifield (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Fyodor (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 23)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 28)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Fyodor (Aug 28)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates David Fifield (Aug 28)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Sep 01)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Fyodor (Sep 08)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Sep 08)
- Re: [PATCH] Add the ability to generate quality random IPs without any duplicates Brandon Enright (Aug 23)