Groups > comp.os.linux.advocacy > #354027 > unrolled thread

Re: man, am I sick of md5

Started by	meat <meat.stretcher@linuxmail.org>
First post	2016-05-07 12:30 +0000
Last post	2016-05-07 13:40 -0700
Articles	19 — 6 participants

Back to article view | Back to comp.os.linux.advocacy

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

  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

#354027 — Re: man, am I sick of md5

From	meat <meat.stretcher@linuxmail.org>
Date	2016-05-07 12:30 +0000
Subject	Re: man, am I sick of md5
Message-ID	<ngkn49$9hk$2@dont-email.me>

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? 


-- 
Meat
Why do they call you Meat? Is it because you are so big?
Yep. You catch em and I'll stretch em.
My college nickname was "The Stretch-Her"

[toc] | [next] | [standalone]

#354049

From	vallor <vallor@cultnix.org>
Date	2016-05-07 18:17 +0000
Message-ID	<dp6pouFfrtrU1@mid.individual.net>
In reply to	#354027

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.

-- 
 -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"

[toc] | [prev] | [next] | [standalone]

#354054

From	owl <owl@rooftop.invalid>
Date	2016-05-07 19:53 +0000
Message-ID	<ghnvmdjf93.akif@rooftop.invalid>
In reply to	#354049

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.

[toc] | [prev] | [next] | [standalone]

#354064

From	owl <owl@rooftop.invalid>
Date	2016-05-07 21:47 +0000
Message-ID	<fhjgie0a2.faeur@rooftop.invalid>
In reply to	#354054

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.

[toc] | [prev] | [next] | [standalone]

#354065

From	owl <owl@rooftop.invalid>
Date	2016-05-07 22:43 +0000
Message-ID	<ghjdi0a3f.ee@rooftop.invalid>
In reply to	#354064

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$

[toc] | [prev] | [next] | [standalone]

#354210

From	vallor <vallor@cultnix.org>
Date	2016-05-08 19:38 +0000
Message-ID	<dp9itfF2mgfU1@mid.individual.net>
In reply to	#354065

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 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. :)

-- 
 -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"

[toc] | [prev] | [next] | [standalone]

#354370

From	owl <owl@rooftop.invalid>
Date	2016-05-09 22:43 +0000
Message-ID	<fhjdsao03.ji@rooftop.invalid>
In reply to	#354210

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?

[toc] | [prev] | [next] | [standalone]

#354372

From	Peter Köhlmann <peter-koehlmann@t-online.de>
Date	2016-05-10 00:58 +0200
Message-ID	<ngr4fo$rni$1@dont-email.me>
In reply to	#354370

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.
>  
 Use a database

[toc] | [prev] | [next] | [standalone]

#354376

From	owl <owl@rooftop.invalid>
Date	2016-05-10 00:02 +0000
Message-ID	<fhjgd02.aadio4e@rooftop.invalid>
In reply to	#354372

Peter Köhlmann <peter-koehlmann@t-online.de> wrote:
> 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.
>>  
>  Use a database

Yes, but I'd rather not do 4+ billion inserts.

[toc] | [prev] | [next] | [standalone]

#354383

From	vallor <vallor@cultnix.org>
Date	2016-05-10 00:53 +0000
Message-ID	<dpcpndFmc2fU1@mid.individual.net>
In reply to	#354370

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

[toc] | [prev] | [next] | [standalone]

#355001

From	owl <owl@rooftop.invalid>
Date	2016-05-13 03:52 +0000
Message-ID	<hgjplfu30a.jkgi3@rooftop.invalid>
In reply to	#354383

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$

[toc] | [prev] | [next] | [standalone]

#355002

From	DFS <nospam@dfs.com>
Date	2016-05-13 00:06 -0400
Message-ID	<nh3jlo$com$1@dont-email.me>
In reply to	#355001

On 5/12/2016 11:52 PM, owl wrote:
> vallor <vallor@cultnix.org> wrote:

>> #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);
>
> IP addresses on right in hex, sorted by IP address:

> Sorted by hash:

> No memory allocated, just walking the FILE
> seek pointer and running some fgetc():


L337 |-|4><0r3r $74L|<3r$ |-|4rD @ \/\/0r|<

http://www.brenz.net/services/l337Maker.asp

[toc] | [prev] | [next] | [standalone]

#355005

From	owl <owl@rooftop.invalid>
Date	2016-05-13 04:27 +0000
Message-ID	<tog3.a0ffe@rooftop.invalid>
In reply to	#355002

DFS <nospam@dfs.com> wrote:
> On 5/12/2016 11:52 PM, owl wrote:
>> vallor <vallor@cultnix.org> wrote:
> 
>>> #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);
>>
>> IP addresses on right in hex, sorted by IP address:
> 
>> Sorted by hash:
> 
>> No memory allocated, just walking the FILE
>> seek pointer and running some fgetc():
> 
> 
> L337 |-|4><0r3r $74L|<3r$ |-|4rD @ \/\/0r|<
> 

Is taht a perl one-liner?


> http://www.brenz.net/services/l337Maker.asp
> 
>

[toc] | [prev] | [next] | [standalone]

#355898

From	vallor <vallor@cultnix.org>
Date	2016-05-18 18:30 +0000
Message-ID	<dq3qmpFct8kU4@mid.individual.net>
In reply to	#355005

On Fri, 13 May 2016 04:27:35 +0000, owl wrote:

> DFS <nospam@dfs.com> wrote:
>> On 5/12/2016 11:52 PM, owl wrote:
>>> vallor <vallor@cultnix.org> wrote:
>> 
>>>> #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);
>>>
>>> IP addresses on right in hex, sorted by IP address:
>> 
>>> Sorted by hash:
>> 
>>> No memory allocated, just walking the FILE seek pointer and running
>>> some fgetc():
>> 
>> 
>> L337 |-|4><0r3r $74L|<3r$ |-|4rD @ \/\/0r|<
>> 
>> 
> Is taht a perl one-liner?
> 
> 
>> http://www.brenz.net/services/l337Maker.asp
>> 
>>

Funny how VB master thinks basic data structures and algorithms 
constitutes "L337 |-|4><".

-- 
 -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"

[toc] | [prev] | [next] | [standalone]

#355931

From	DFS <nospam@dfs.com>
Date	2016-05-18 16:55 -0400
Message-ID	<nhikl7$7ai$1@dont-email.me>
In reply to	#355898

On 5/18/2016 2:30 PM, vallor wrote:
> On Fri, 13 May 2016 04:27:35 +0000, owl wrote:
>
>> DFS <nospam@dfs.com> wrote:
>>> On 5/12/2016 11:52 PM, owl wrote:
>>>> vallor <vallor@cultnix.org> wrote:
>>>
>>>>> #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);
>>>>
>>>> IP addresses on right in hex, sorted by IP address:
>>>
>>>> Sorted by hash:
>>>
>>>> No memory allocated, just walking the FILE seek pointer and running
>>>> some fgetc():
>>>
>>>
>>> L337 |-|4><0r3r $74L|<3r$ |-|4rD @ \/\/0r|<
>>>
>>>
>> Is taht a perl one-liner?
>>
>>
>>> http://www.brenz.net/services/l337Maker.asp
>>>
>>>
>
> Funny how VB master thinks basic data structures and algorithms
> constitutes "L337 |-|4><".


Funny how donut master thinks his heart won't stop any day now.

[toc] | [prev] | [next] | [standalone]

#355779

From	vallor <vallor@cultnix.org>
Date	2016-05-17 20:22 +0000
Message-ID	<dq1csrFt903U1@mid.individual.net>
In reply to	#355001

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"

[toc] | [prev] | [next] | [standalone]

#355806

From	owl <owl@rooftop.invalid>
Date	2016-05-18 00:44 +0000
Message-ID	<ghjao903.a@rooftop.invalid>
In reply to	#355779

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.

[toc] | [prev] | [next] | [standalone]

#354058

From	vallor <vallor@cultnix.org>
Date	2016-05-07 20:02 +0000
Message-ID	<dp6vueFfrtrU3@mid.individual.net>
In reply to	#354049

On Sat, 07 May 2016 18:17:02 +0000, vallor 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.)

Turns out, I'm off by one _again_.  Sheesh. :P

The number of records in the file should be (224*2^24)-1, which *20 is 
75161927660 bytes.

Filesize is actually 75161927360 bites, leaving 300 bytes unaccounted 
for.  300/20 = 15 records.

So it is just as I said in my previous post, _except_ 224.0.0.0 wasn't in 
the original set -- I just go up to 223.255.255.255.

(224.0.0.0- are multicast addresses.)

Anyway, I know exactly where the error was.  The only reason I would 
mention something so trivial is that I want Fibian to see what computer 
science really looks like.

-- 
 -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"

[toc] | [prev] | [next] | [standalone]

#354060

From	Snit <usenet@gallopinginsanity.com>
Date	2016-05-07 13:40 -0700
Message-ID	<D353A0D2.72359%usenet@gallopinginsanity.com>
In reply to	#354058

On 5/7/16, 1:02 PM, in article dp6vueFfrtrU3@mid.individual.net, "vallor"
<vallor@cultnix.org> wrote:

> "I do not see desktop Linux as a failure." -"Snit"

While I find the obsession COLA has with me and my views (and even more than
that, my life), I have to say your expression of your obsession is for a
change actually a rare case of it being a (mostly) good thing.

It is absolutely correct of you to say I do not see desktop Linux as a
failure. Sure, it does not compete with OS X and Windows for the general
market, but it is world-changing for those who cannot afford such systems /
licenses and is often the best choice for people who work largely with the
command line.

So often the obsession with me that so many in COLA has leads them to post
absurd and silly attacks, and to twist words and to otherwise troll. We have
seen a LOT of that toward me in the last few days. But you are rising above
that... even if holding on to the weird COLA obsession with me.




-- 
* OS X / Linux: What is a file?     <http://youtu.be/_dMbXGLW9PI>
* Mint MATE Trash, Panel, Menu:     <http://youtu.be/C0y74FIf7uE>
* Mint KDE working with folders:    <http://youtu.be/7C9nvniOoE0>
* Mint KDE creating files:          <http://youtu.be/N7-fZJaJUv8>
* Mint KDE help:                    <http://youtu.be/3ikizUd3sa8>
* Mint KDE general navigation:      <http://youtu.be/t9y14yZtQuI>
* Mint KDE bugs or Easter eggs?     <http://youtu.be/CU-whJQvtfA>
* Easy on OS X / Hard on Linux:     <http://youtu.be/D3BPWANQoIk>
* OS / Word Processor Comparison:   <http://youtu.be/w6Qcl-w7s5c>

[toc] | [prev] | [standalone]

csiph-web

Re: man, am I sick of md5

Contents

#354027 — Re: man, am I sick of md5

#354049

#354054

#354064

#354065

#354210

#354370

#354372

#354376

#354383

#355001

#355002

#355005

#355898

#355931

#355779

#355806

#354058

#354060