Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.os.linux.advocacy > #354370
| From | owl <owl@rooftop.invalid> |
|---|---|
| Newsgroups | comp.os.linux.advocacy |
| Subject | Re: man, am I sick of md5 |
| Date | 2016-05-09 22:43 +0000 |
| Organization | O.W.L. |
| Message-ID | <fhjdsao03.ji@rooftop.invalid> (permalink) |
| References | (3 earlier) <dp6pouFfrtrU1@mid.individual.net> <ghnvmdjf93.akif@rooftop.invalid> <fhjgie0a2.faeur@rooftop.invalid> <ghjdi0a3f.ee@rooftop.invalid> <dp9itfF2mgfU1@mid.individual.net> |
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?
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