Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.os.linux.advocacy > #354383
| From | vallor <vallor@cultnix.org> |
|---|---|
| Newsgroups | comp.os.linux.advocacy |
| Subject | Re: man, am I sick of md5 |
| Date | 2016-05-10 00:53 +0000 |
| Message-ID | <dpcpndFmc2fU1@mid.individual.net> (permalink) |
| References | (4 earlier) <ghnvmdjf93.akif@rooftop.invalid> <fhjgie0a2.faeur@rooftop.invalid> <ghjdi0a3f.ee@rooftop.invalid> <dp9itfF2mgfU1@mid.individual.net> <fhjdsao03.ji@rooftop.invalid> |
On Mon, 09 May 2016 22:43:53 +0000, owl wrote:
> vallor <vallor@cultnix.org> wrote:
>> On Sat, 07 May 2016 22:43:55 +0000, owl wrote:
>>
>>> owl <owl@rooftop.invalid> wrote:
>>>> owl <owl@rooftop.invalid> wrote:
>>>>> vallor <vallor@cultnix.org> wrote:
>>>>>> On Sat, 07 May 2016 12:30:01 +0000, meat wrote:
>>>>>>
>>>>>>> On Sat, 07 May 2016 02:59:11 +0000, vallor wrote:
>>>>>>>
>>>>>>>> On Sat, 07 May 2016 02:40:04 +0000, vallor wrote:
>>>>>>>>> But look at that bootiful sorted data:
>>>>>>>>>
>>>>>>>>> $ head -10 md5_ipv4_rainbow.hex
>>>>>>>>> 0000000191fab544b163e31753366fae9c8380c2
>>>>>>>>> 0000000384db5f2b13aae0c719c21aa002e6c0b2
>>>>>>>>
>>>>>>>>> fffffffcfef441108d45e6ea4c38b0a7c3fe66b0
>>>>>>>>
>>>>>>>> I just showed this to someone looking over my shoulder, and they
>>>>>>>> said, "You mean to tell me you have a file with all the Internet
>>>>>>>> addresses in the world? Like, even foreign countries?"
>>>>>>>
>>>>>>> That's what I was thinking!
>>>>>>> I suspect it's human nature to assume something like that would
>>>>>>> require the NSA and a super computer to churn out. Kind of like
>>>>>>> calculating pi to the 1000000 trillionth digit or something.
>>>>>>>
>>>>>>> It kind of puts a new face on government spying doesn't it?
>>>>>>
>>>>>> BTW, if you've done the math on my file size, you'll discover that
>>>>>> there are 16 records missing. They are for the following IP
>>>>>> addresses:
>>>>>>
>>>>>> 0.0.0.0, 28.0.0.0, 42.0.0.0, 56.0.0.0,
>>>>>> 70.0.0.0, 84.0.0.0, 98.0.0.0, 112.0.0.0,
>>>>>> 126.0.0.0, 140.0.0.0, 154.0.0.0, 168.0.0.0,
>>>>>> 182.0.0.0, 196.0.0.0, 210.0.0.0, 224.0.0.0
>>>>>>
>>>>>> It was an off-by-one error in the shell script that I used to run
>>>>>> the C program to generate each block. (I used 16 processors on my
>>>>>> video superserver.)
>>>>>>
>>>>>> I'm probably going to just hard-code these hashes into the search
>>>>>> program, because I don't want to re-generate the files, convert
>>>>>> them,
>>>>>> sort them, merge them, then convert them back to binary...it takes
>>>>>> a while, as you can imagine.
>>>>>>
>>>>>>
>>>>> I'm decided to try a different approach today. I set up a btrfs
>>>>> partition. btrfs does not suffer the inode limit that you get with
>>>>> ext4,
>>>>> so billions of directories should be doable. It takes a bit of time
>>>>> to generate the tree -- I'm guessing about 1.7 hours per /8 -- but
>>>>> seek times seem to be very fast with testing so far. I pulled a
>>>>> recursive mkdir()
>>>>> function from the web and merged it to my existing code. The ip
>>>>> address for a given hash will end up as a node directory.
>>>>>
>>>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
>> ipdir$
>>>>> echo -n 0.3.100.198 | md5sum ffff32641ebadad6de6b77dc19699e82 -
>>>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
>> ipdir$
>>>>> time ls
>>>>> f/f/f/f/3/2/6/4/1/e/b/a/d/a/d/6/d/e/6/b/7/7/d/c/1/9/6/9/9/e/8/2
>>>>> 0.3.100.198
>>>>>
>>>>> real 0m0.003s user 0m0.000s sys 0m0.000s
>>>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
>> ipdir$
>>>>>
>>>>> This was not with the whole tree built yet. I'm still waiting on
>>>>> the first /8 to complete to get a better idea of the total build
>>>>> time.
>>>>>
>>>>>
>>>> Damn. It's been running for quite a while now creating tree for
>>>> 0.0.0.0-0.255.255.255. Just now hit 0.9.0.0 level, but speeds are
>>>> still holding pretty good.
>>>>
>>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
ipdir
>> $
>>>> echo -n 0.9.0.0 | md5sum 14637e918fe0e9edd63634b57cfe809b -
>>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
ipdir
>> $
>>>> time ./doit.sh 14637e918fe0e9edd63634b57cfe809b 0.9.0.0
>>>>
>>>> real 0m0.005s user 0m0.000s sys 0m0.000s
>>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
ipdir
>> $
>>>>
>>>> This is doit.sh:
>>>>
>>>> #!/bin/bash
>>>>
>>>> if [ ${#} -ne 1 ];then
>>>> echo "need a hash"
>>>> exit
>>>> fi
>>>>
>>>> ls $(./haship2dir ${1})
>>>>
>>>> --------
>>>> haship2dir just creates the directory from the provided hash.
>>>> At this rate, I think we're back to the multiple weeks for tree
>>>> generation, but "decode" speeds are near instantaneous, at least so
>>>> far. And all this assumes btrfs doesn't crap out before it's done.
>>>>
>>>>
>>> Clarification: haship2dir creates the directory *name* from the
>>> provided hash. The directory would have been created already.
>>> This is just to eliminate having to re-type the hash with slashes when
>>> you want to search.
>>>
>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
ipdir$
>>> time ./doit.sh c0f68c9df008b6ba890bf03f84d4c251 0.10.0.0
>>>
>>> real 0m0.009s user 0m0.000s sys 0m0.004s
>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
ipdir$
>>> time ./doit.sh c0f68c9df008b6ba890bf03f84d4c25f ls: cannot access
>>> c/0/f/6/8/c/9/d/f/0/0/8/b/6/b/a/8/9/0/b/f/0/3/f/8/4/d/4/c/2/5/f/: No
>>> such file or directory
>>>
>>> real 0m0.009s user 0m0.008s sys 0m0.000s
>>> anon@lowtide:/media/anon/f617b3c2-e000-437f-9c75-04474c001d92/ips/
ipdir$
>>
>> Interesting way to do it, I'm curious how it turns out.
>>
>>
> I've so far tried the following three directory layouts:
>
> 0/d/f/9/4/e/5/f/0/0/6/3/b/0/3/9/a/a/1/c/3/d/b/0/a/2/6/a/6/d/1/
f/216.58.194.206
> ...
>
> 0/d/f/9/4/e/5/f/0063b039aa1c3db0a26a6d1f/216.58.194.206 ...
>
> 0df94e5f0063b039aa1c3db0a26a6d1f/216.58.194.206 ...
>
> Seek times are fast with each type, but creation of the tree bogs down
> to unacceptable levels, and these are tests on just a single a /8.
> Even in parallel, it gets to about the half-way point and then is down
> to about 300/sec directory creation.
>
> $ echo -n 0.20.0.0 |md5sum 9c5bd27b206e8415dd8f32573b1b51a0 -
> $ time ls work/9c5bd27b206e8415dd8f32573b1b51a0 0.20.0.0
>
> real 0m0.004s user 0m0.000s sys 0m0.000s $ echo -n 0.240.0.0 |
md5sum
> 02c208f40f2b163a7f4a6ddda8814a86 -
> $ time ls work/02c208f40f2b163a7f4a6ddda8814a86 0.240.0.0
>
> real 0m0.004s user 0m0.000s sys 0m0.000s $
>
> Seek times are good, but it took 6 hours to create the directories
> running 8 parallel jobs on a single /8 and only got 2/3 way through
> before I killed it.
>
> $ ls work |wc -l 12012373 $
>
> lol that's about 24 million directories -- about 50 times the number of
> inodes I have in use on /dev/sda.
>
>
>> I finished up my search program, and the output looks like this:
>>
>> $ time ./md5_file_search /var/scott/md5_ipv4_rainbow.b
>> 0df94e5f0063b039aa1c3db0a26a6d1f { * }
>> (span) direction 0 1879048184 3758096368 (3758096368)
>> -114 0 939524092 1879048184 (1879048184) -50 0
>> 469762046 939524092 (939524092) -18 0 234881023
>> 469762046 (469762046) -2 0 117440511 234881023
>> (234881023) 6 117440511 176160767 234881023 (117440512)
>> 2 176160767 205520895 234881023 (58720256) -1536
>> 176160767 190840831 205520895 (29360128) 1 190840831
>> 198180863 205520895 (14680064) 31232 198180863
>> 201850879 205520895 (7340032) 14848 201850879 203685887
>> 205520895 (3670016) 6656 203685887 204603391
>> 205520895 (1835008) 2560 204603391 205062143 205520895
>> (917504) 512 205062143 205291519 205520895 (458752)
>> -512 205062143 205176831 205291519 (229376) -72
>> 205062143 205119487 205176831 (114688) 256 205119487
>> 205148159 205176831 (57344) 57 205148159
>> 205162495 205176831 (28672) -8 205148159 205155327
>> 205162495 (14336) 24 205155327 205158911 205162495
>> (7168) 8 205158911 205160703 205162495 (3584)
>> -16128 205158911 205159807 205160703 (1792) 4
>> 205159807 205160255 205160703 (896) 2 205160255
>> 205160479 205160703 (448) 1 205160479 205160591
>> 205160703 (224) 20992 205160591 205160647 205160703 (112)
>> -768 205160591 205160619 205160647 (56) 7936 205160619
>> 205160633 205160647 (28) 3584
>> 0df94e5f0063b039aa1c3db0a26a6d1f:216.58.194.206
>>
>> real 0m0.002s user 0m0.000s sys 0m0.002s
>>
>> Which is even faster than I suspected.
>>
>> I'm going to clean up the code for the search program,
>> and then put it on my github. But first, it's time for Sunday brunch.
>> :)
>>
>>
> Your approach is definitely the way to go. You're using one huge sorted
> file, right?
Yes, and to respond to Peter's comment, it _is_ a database.
It's just not a relational database. It's a binary file of 20-byte
records which looks like this:
[ 16 bytes of md5 hash][ 4 bytes of IPv4 address ]
No record separators.
The file is sorted, so that one can do a binary search by md5 hash.
As far as I can figure out, this is the most compact format to use, while
still retaining enough structure to make retrieval extremely fast.
The search program is further simplified by mmap'ping the file, so that
the records appear as an array of struct rainrec:
struct rainrec {
u_int8_t digest[MD5_DIGEST_LENGTH];
in_addr_t s_addr;
};
So with lb, rb, and gb being "left bracket, right bracket, gripping
bracket" (respectively), search is done like this:
#define SPANMIN 20
for( span=rb-lb ; span>SPANMIN ; span=rb-lb )
{
gb = (rb+lb)/2;
direction = memcmp(theirdigest,rainbow[gb].digest,MD5_DIGEST_LENGTH);
in that statement, accessing rainbow[gb] will cause a page fault, mapping
the page that contains the array's address into physical RAM. (The
mmap'ed file is similar to a swap file, except it isn't.)
I did have to hit the books a little bit to make sure you could mmap a
file larger than physical RAM without killing the system, but it works
exactly as you'd expect: only the pages you access are mapped to RAM.
(And get paged out of RAM once they haven't been used for a while, using
whatever least-recently-used algorithm the Linux memory manager uses.)
tl;dr:
"Use a database." Yes, that's what I've done -- a specially-constructed
74GB database. Lookup takes .002 seconds.
And I note that Fibian has gone missing, lul.
--
-v
Back to comp.os.linux.advocacy | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: man, am I sick of md5 meat <meat.stretcher@linuxmail.org> - 2016-05-07 12:30 +0000
Re: man, am I sick of md5 vallor <vallor@cultnix.org> - 2016-05-07 18:17 +0000
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-07 19:53 +0000
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-07 21:47 +0000
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-07 22:43 +0000
Re: man, am I sick of md5 vallor <vallor@cultnix.org> - 2016-05-08 19:38 +0000
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-09 22:43 +0000
Re: man, am I sick of md5 Peter Köhlmann <peter-koehlmann@t-online.de> - 2016-05-10 00:58 +0200
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-10 00:02 +0000
Re: man, am I sick of md5 vallor <vallor@cultnix.org> - 2016-05-10 00:53 +0000
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-13 03:52 +0000
Re: man, am I sick of md5 DFS <nospam@dfs.com> - 2016-05-13 00:06 -0400
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-13 04:27 +0000
Re: man, am I sick of md5 vallor <vallor@cultnix.org> - 2016-05-18 18:30 +0000
Re: man, am I sick of md5 DFS <nospam@dfs.com> - 2016-05-18 16:55 -0400
Re: man, am I sick of md5 vallor <vallor@cultnix.org> - 2016-05-17 20:22 +0000
Re: man, am I sick of md5 owl <owl@rooftop.invalid> - 2016-05-18 00:44 +0000
Re: man, am I sick of md5 vallor <vallor@cultnix.org> - 2016-05-07 20:02 +0000
Re: man, am I sick of md5 Snit <usenet@gallopinginsanity.com> - 2016-05-07 13:40 -0700
csiph-web