Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.os.linux.advocacy > #355779
| From | vallor <vallor@cultnix.org> |
|---|---|
| Newsgroups | comp.os.linux.advocacy |
| Subject | Re: man, am I sick of md5 |
| Date | 2016-05-17 20:22 +0000 |
| Message-ID | <dq1csrFt903U1@mid.individual.net> (permalink) |
| References | (6 earlier) <ghjdi0a3f.ee@rooftop.invalid> <dp9itfF2mgfU1@mid.individual.net> <fhjdsao03.ji@rooftop.invalid> <dpcpndFmc2fU1@mid.individual.net> <hgjplfu30a.jkgi3@rooftop.invalid> |
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.
--
-v
"Desktops, workstations and servers are and Microsoft
is doing very well. AS well as Linux." -"Slimer"
"I do not see desktop Linux as a failure." -"Snit"
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