netdev - Re: Extensible hashing and RCU

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <17899.60079.450134.412648@robur.slu.se>
Date:	Mon, 5 Mar 2007 11:02:23 +0100
From:	Robert Olsson <Robert.Olsson@...a.slu.se>
To:	"Michael K. Edwards" <medwards.linux@...il.com>
Cc:	"David Miller" <davem@...emloft.net>, johnpol@....mipt.ru,
	dada1@...mosbay.com, akepner@....com, linux@...izon.com,
	netdev@...r.kernel.org
Subject: Re: Extensible hashing and RCU

Michael K. Edwards writes:

 > This, incidentally, seems very similar to the process that Robert
 > Olsson and Stefan Nilsson have gone through with their trie/hash
 > project.  Although I haven't tried it out yet and don't have any basis
 > for an independent opinion, the data and analysis provided in their
 > paper are quite convincing. 

 I've info about this "process" :) Moved fib_trie.c to userland to extend 
 it longer an variable keylengths. Testprogram was doing insert/lookup/remove 
 with random data with blistering performance (very flat trees).

 So quite happy I moved this trie back to the kernel and started testing with
 "real data" - ip addresses and rDoS.  Result was disastrous.... very deep 
 trees and awful network performance. Random data is very different from 
 real data was the lesson learned again. Gave up. 

 A couple days later an idea came up. I'll remembered the poof from the
 LC-trie paper that length of key does not impact tree depth. So went 
 to Stefan, Can't we just fix up the data rather than fiddling with an 
 new improved algorithm? The result was this "hash" header to boost tree 
 compression.

 Cheers
					--ro

-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html