netdev - Re: htb parallelism on multi-core platforms

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: <1241010951.6554.355.camel@blade.ines.ro>
Date:	Wed, 29 Apr 2009 16:15:51 +0300
From:	Radu Rendec <radu.rendec@...s.ro>
To:	Jarek Poplawski <jarkao2@...il.com>
Cc:	Jesper Dangaard Brouer <hawk@...u.dk>,
	Denys Fedoryschenko <denys@...p.net.lb>,
	netdev <netdev@...r.kernel.org>,
	Calin Velea <calin.velea@...enii.ro>
Subject: Re: htb parallelism on multi-core platforms

On Wed, 2009-04-29 at 14:23 +0200, Jarek Poplawski wrote:
> According to the author's(?) comment with hysteresis "The speed gain
> is about 1/6", so not very much here considering htb_dequeue time.

Thought so :)

> Radu, since not only your worst case, but also the real case u32
> lookups are very big I think you should mainly have a look at Calin's
> u32 hash generator or at least his method, and only after optimizing
> it try these other tricks. Btw. I hope Calin made this nice program
> known to networking/admins lists too.

I've just had a look at Calin's approach to optimizing u32 lookups. It
does indeed make a very nice use of u32 hash capabilities, resulting in
a maximum of 4 lookups. The algorithm he uses takes advantage of the
fact that only a (small) subset of the whole ipv4 address space is
actually used in an ISP's network.

Unfortunately his approach makes it a bit difficult to dynamically
adjust the configuration, since the controller (program/application)
must remember the exact hash tables, filters etc in order to be able to
add/remove CIDRs without rewriting the entire configuration. Unused hash
tables also need to be "garbage collected" and reused, otherwise the
hash table id space could be exhausted.

Since I only use IP lookups (and u32 is very generic) I'm starting to
ask myself if a different kind of data structures and classifier were
more appropriate.

For instance, I think a binary search tree that is matched against the
bits in the ip address would result in pretty nice performance. It would
take at most 32 iterations (descending through the tree) with less
overhead than the (complex) u32 rule match.

> Btw. #2: I think you wrote you didn't use iptables...
No, I don't use iptables.

Btw, the e1000e driver seems to have no way to disable NAPI. Am I
missing something (like a global kernel config option that disables NAPI
completely)?

Thanks,

Radu

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