netdev - Re: [ANN] Unified dynamic storage for different socket types instead of separate hash tables.

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]

Date:	Thu, 22 Mar 2007 22:30:52 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	David Miller <davem@...emloft.net>
Cc:	shemminger@...ux-foundation.org, netdev@...r.kernel.org
Subject: Re: [ANN] Unified dynamic storage for different socket types instead of separate hash tables.

On Thu, Mar 22, 2007 at 12:21:20PM -0700, David Miller (davem@...emloft.net) wrote:
> From: Evgeniy Polyakov <johnpol@....mipt.ru>
> Date: Thu, 22 Mar 2007 22:14:49 +0300
> 
> > And to be absolutely clear - existing interface does not support it too
> > - we iterate over every single hash entry, and then over every single
> > item in the chain (if it exists). I can create the same for the tree -
> > it is not complex at all, but it is not the most optimal solution, and 
> > since I remove several entries, I think it is not that bad to remove a 
> > bit less and optimize 'iterate over all object' case a bit.
> 
> This results in your trie having two new run-time costs:
> 
> 1) More expensive trie insert/delete compared to hash
>    insert/delete

That's true, it requires additional allocation, which can be combined
with socket allocation though.

> 2) An extra list insert/delete to give list of all sockets

That is too small price.
And as I stated in another mail - we can iterate over whole tree just
like we do with hash tables - even faster, if I will attach a bitmask of
used entires to each level node.

> So connection setup/teardown will be more expensive and
> therefore our connection rates will be lower.

Hmm, I'm not sure - we already allocate several items during connection
setup/teardown time (request socket, usual socket, timewait socket), 
so additional one is not absolutely sure will end up with slower times.

And do not forget about other benefits dynamic structure gives us
compared to static hash table in DoS and traversal speed/locking.

> Evgeniy, your ideas are beautiful in theory, but all the details
> kill all of your non-trivial work and make it useless in the end.

I especially agree with first part of the sentence :))
So far I can not see serious disadvantages in this design.

-- 
	Evgeniy Polyakov
-
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