Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.os.linux.advocacy > #355806
| From | owl <owl@rooftop.invalid> |
|---|---|
| Newsgroups | comp.os.linux.advocacy |
| Subject | Re: man, am I sick of md5 |
| Date | 2016-05-18 00:44 +0000 |
| Organization | O.W.L. |
| Message-ID | <ghjao903.a@rooftop.invalid> (permalink) |
| References | (7 earlier) <dp9itfF2mgfU1@mid.individual.net> <fhjdsao03.ji@rooftop.invalid> <dpcpndFmc2fU1@mid.individual.net> <hgjplfu30a.jkgi3@rooftop.invalid> <dq1csrFt903U1@mid.individual.net> |
vallor <vallor@cultnix.org> wrote:
> On Fri, 13 May 2016 03:52:06 +0000, owl wrote:
>
>> vallor <vallor@cultnix.org> wrote:
>>> On Mon, 09 May 2016 22:43:53 +0000, owl wrote:
>>>
>> ...
>>>>>
>>>> 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.
>>>
>>
>> I did some tests with an ascii-only sorted file, with the IP address
>> in hex to fix record length at 42 bytes. Holy shit it took 11 hours to
>> sort the file, after several failures. :) Finally had to set TMPDIR to
>> the target drive just to keep it from crapping out. (Watching it work,
>> it created 30-some 6GB files before recombining).
>>
>> anon@lowtide:/mnt/blue/ips$ ls -lh testy*
>> -r--r--r-- 1 anon anon 168G May 10 13:31 testy
>> -r--r--r-- 1 anon anon 168G May 11 10:20 testysorted
>> anon@lowtide:/mnt/blue/ips$
>>
>>
>> anon@lowtide:/mnt/blue/ips$ wc -l testy
>> 4294967296 testy
>> anon@lowtide:/mnt/blue/ips$ wc -l testysorted
>> 4294967296 testysorted
>> anon@lowtide:/mnt/blue/ips$
>>
>> IP addresses on right in hex, sorted by IP address:
>>
>> anon@lowtide:/mnt/blue/ips$ head testy
>> f1f17934834ae2613699701054ef9684 00000000
>> 357244d0fa7fba3bfba07be39f368a22 00000001
>> 523f8855414afd1ec1be065afe9081e5 00000002
>> ea48a9e83c978f720d08263d5eba8b2f 00000003
>> e9457babae7b1680ad9491ecb7adce13 00000004
>> 4342b336f4a9e26764604c43c93f82d5 00000005
>> f6b32856a199df19aa5a03d38a70ee3e 00000006
>> b6cccc3e597a1dbcce185aad7dad7af3 00000007
>> 37d758a32c00ee5deb17a45a2d4373c8 00000008
>> 038b50f4a68be5cf44d325e67501d6d0 00000009
>> anon@lowtide:/mnt/blue/ips$
>>
>>
>> anon@lowtide:/mnt/blue/ips$ tail testy
>> 9ac8b30cc6fd0b0da6499d3bdb00707b fffffff6
>> f7357860d912f326268ac7032d06a911 fffffff7
>> 99c1b11d1f470d6457498d379d031514 fffffff8
>> 68672e3e466373f493542f394351ecd9 fffffff9
>> 09e35b1b1d02f28d1ad207dfcc32df94 fffffffa
>> 02b8ba3fc026d02cbc7f4d9d7ad292f7 fffffffb
>> 0285a0a4894c6a81af03802668a769eb fffffffc
>> 7a41e3dc6531e303c47d842573b55551 fffffffd
>> 69943e983e64dbebafd67afc051a2772 fffffffe
>> eea88cd0d9a7ba26282fc786713bbbb6 ffffffff
>> anon@lowtide:/mnt/blue/ips$
>>
>>
>> Sorted by hash:
>>
>> anon@lowtide:/mnt/blue/ips$ head testysorted
>> 0000000191fab544b163e31753366fae 9c8380c2
>> 0000000384db5f2b13aae0c719c21aa0 02e6c0b2
>> 0000000426d85f05baf066762c2138d3 10203e2b
>> 00000005e10941cd6f90b4ab82877387 ca240710
>> 000000068d2bea76c03e33bb8ef3fd4c 259dbc19
>> 000000087d47b373894f4d7849d7624a 0a10aeba
>> 0000000aea5f91546205fd55d18272da d3f58273
>> 0000000b9511ad5b8c2d32e82e9b58d4 6058d59a
>> 00000012f2b46fc20fb36e3caa544080 f28ebfbd
>> 00000013a6f920ad53f0e4f9162ff237 a6602b3b
>> anon@lowtide:/mnt/blue/ips$
>>
>>
>> anon@lowtide:/mnt/blue/ips$ tail testysorted
>> fffffff7d731177e2ad428b94c0d8e95 bd3c7370
>> fffffff86abdbe68a461c9718e57a8d6 ed57653d
>> fffffff9a6d336c41665fbb70e246bbf 6d4d4a8a
>> fffffffa6ca08d0269ae456ca18bbec4 5c935465
>> fffffffb10c5e411124caffb93b606b6 946b4370
>> fffffffb579e6172e7bbc9de304dd68e b2f83959
>> fffffffbdcfe150e46f857da7af3adc9 58179eca
>> fffffffc1dc82a62370f439136416e07 5a90511e
>> fffffffc691b530829cfd5740328175e c61fe707
>> fffffffcfef441108d45e6ea4c38b0a7 c3fe66b0
>> anon@lowtide:/mnt/blue/ips$
>>
>>
>> Below test has no compare logic, just dividing to the left only, to test
>> seek times and verify. No memory allocated, just walking the FILE
>> seek pointer and running some fgetc():
>>
>> anon@lowtide:/mnt/blue/ips$ time ./walk
>> (line: 2147483649) left: 0 center: 90194313216 right:
> 180388626432
>> 7fff68b343886c462555d9d6977a0942 59e2550a
>> (line: 1073741825) left: 0 center: 45097156608 right:
> 90194313216
>> 3fff98e41675dcb63132b592e2484e4e 4de14538
>> (line: 536870913) left: 0 center: 22548578304 right:
> 45097156608
>> 1fff982dd8c31c18bc12fec5599b8966 ddb0d995
>> (line: 268435457) left: 0 center: 11274289152 right:
> 22548578304
>> 0fffd2452f347395b5e8e2d267ec4dd5 2ec283a8
>> (line: 134217729) left: 0 center: 5637144576 right:
> 11274289152
>> 07ffdafc98cab3cce884589aa44cff75 586a4499
>> (line: 67108865) left: 0 center: 2818572288 right:
> 5637144576
>> 03ffeb13202823932d05c55dc061a8ed 956f49e2
>> (line: 33554433) left: 0 center: 1409286144 right:
> 2818572288
>> 01fffc76a7f4105195a0c5a2901ae63c 25ec047d
>> (line: 16777217) left: 0 center: 704643072 right:
> 1409286144
>> 010000f7c82e582d08b5989c86178b09 98e4c362
>> (line: 8388609) left: 0 center: 352321536 right: 704643072
>> 007ffb6915a42af4e7b700cab81b9cfe 9a753d2e
>> (line: 4194305) left: 0 center: 176160768 right: 352321536
>> 003fff2106f3f942b6b9c127d0dfd174 7f1061b4
>> (line: 2097153) left: 0 center: 88080384 right: 176160768
>> 001ffecb98526ea76a9bdab85750e3e9 12b74609
>> (line: 1048577) left: 0 center: 44040192 right: 88080384
>> 001000980124d482d81e59e029b85eb9 f5148ef8
>> (line: 524289) left: 0 center: 22020096 right: 44040192
>> 0008003559fd76c1720f17d5f2a3d7a5 1496d8c3
>> (line: 262145) left: 0 center: 11010048 right: 22020096
>> 0004028a5ac8a9afa708da9ec701349b 403badf1
>> (line: 131073) left: 0 center: 5505024 right: 11010048
>> 000202d79b49f5393740e5564d1b4ad3 2ee3c058
>> (line: 65537) left: 0 center: 2752512 right: 5505024
>> 0001013f048e11ea57dcba6fdf04662f ae644240
>> (line: 32769) left: 0 center: 1376256 right: 2752512
>> 00007ffcb2508646a5efea7419930fd6 6b402c3e
>> (line: 16385) left: 0 center: 688128 right: 1376256
>> 00004015d124e66dca7d8955378146fe 0e6d43b2
>> (line: 8193) left: 0 center: 344064 right: 688128
>> 0000203d66aa718b56785d33168e5ee2 2ead3055
>> (line: 4097) left: 0 center: 172032 right: 344064
>> 0000101db01d7c3c90eb087fd14bdf6b 7bd393af
>> (line: 2049) left: 0 center: 86016 right: 172032
>> 0000086ee9f47ab167b4cdd43fbf967f 80d364d7
>> (line: 1025) left: 0 center: 43008 right: 86016
>> 0000044a6040737f5b031b77d6ad00e5 d04651dd
>> (line: 513) left: 0 center: 21504 right: 43008
>> 0000021f3c635acc0c75695915c8c555 82bd776f
>> (line: 257) left: 0 center: 10752 right: 21504
>> 00000122bae47887e0baf0be2eae0f8c aef4532d
>> (line: 129) left: 0 center: 5376 right: 10752
>> 00000096bbe528c0f862e86478c47fa5 36702d90
>> (line: 65) left: 0 center: 2688 right: 5376
>> 0000005374c67d34298f4116e723073e ee08f0fb
>> (line: 33) left: 0 center: 1344 right: 2688
>> 00000030f1a4c23a2d8a2395bbc3820f e4a12ba1
>> (line: 17) left: 0 center: 672 right: 1344
>> 0000001c710e151871b6c0451ff87d23 6e26c3c5
>> (line: 9) left: 0 center: 336 right: 672
>> 00000012f2b46fc20fb36e3caa544080 f28ebfbd
>> (line: 5) left: 0 center: 168 right: 336
>> 000000068d2bea76c03e33bb8ef3fd4c 259dbc19
>> (line: 3) left: 0 center: 84 right: 168
>> 0000000426d85f05baf066762c2138d3 10203e2b
>> (line: 2) left: 0 center: 42 right: 84
>> 0000000384db5f2b13aae0c719c21aa0 02e6c0b2
>> (line: 1) left: 0 center: 0 right: 42
>> 0000000191fab544b163e31753366fae 9c8380c2
>>
>> real 0m0.003s
>> user 0m0.000s
>> sys 0m0.000s
>> anon@lowtide:/mnt/blue/ips$
>
> Lookin good -- surprised you're keeping the data in hexadecimal, though,
> that takes up twice the storage space.
>
Yeah, I need to get back to this one and see how the speed compares
to your binary file walk. I know the ascii file is twice as large,
but it lets me verify things easily. I chose hex for alignment
and for easy recognition of the addresses.
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