Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.os.linux.advocacy > #355001

Re: man, am I sick of md5

From owl <owl@rooftop.invalid>
Newsgroups comp.os.linux.advocacy
Subject Re: man, am I sick of md5
Date 2016-05-13 03:52 +0000
Organization O.W.L.
Message-ID <hgjplfu30a.jkgi3@rooftop.invalid> (permalink)
References (5 earlier) <fhjgie0a2.faeur@rooftop.invalid> <ghjdi0a3f.ee@rooftop.invalid> <dp9itfF2mgfU1@mid.individual.net> <fhjdsao03.ji@rooftop.invalid> <dpcpndFmc2fU1@mid.individual.net>

Show all headers | View raw

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$

Back to comp.os.linux.advocacy | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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