linux-kernel - Re: [RFC PATCH v2] net: sched: convert qdisc linked list to hashtable

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-next>] [day] [month] [year] [list]

Date:	Thu, 7 Jul 2016 18:57:33 -0400
From:	Craig Gallek <kraigatgoog@...il.com>
To:	Jiri Kosina <jikos@...nel.org>
Cc:	Eric Dumazet <eric.dumazet@...il.com>,
	Jamal Hadi Salim <jhs@...atatu.com>,
	Phil Sutter <phil@....cc>, netdev <netdev@...r.kernel.org>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [RFC PATCH v2] net: sched: convert qdisc linked list to hashtable

On Thu, Jul 7, 2016 at 4:36 PM, Jiri Kosina <jikos@...nel.org> wrote:
> From: Jiri Kosina <jkosina@...e.cz>
>
> Convert the per-device linked list into a hashtable. The primary
> motivation for this change is that currently, we're not tracking all the
> qdiscs in hierarchy (e.g. excluding default qdiscs), as the lookup
> performed over the linked list by qdisc_match_from_root() is rather
> expensive.
>
> The ultimate goal is to get rid of hidden qdiscs completely, which will
> bring much more determinism in user experience.
>
> As we're adding hashtable.h include into generic netdevice.h, we have to make
> sure HASH_SIZE macro is now non-conflicting with local definitions.
>
> Signed-off-by: Jiri Kosina <jkosina@...e.cz>
> ---
>
> v1 -> v2:       fix up RCU hastable usage wrt. rtnl
>                 fix compilation of .c files which define their own
>                  HASH_SIZE that now oncflicts with the one from
>                  hashtable.h (newly included via netdevice.h)
This sort of seems like it's just side-stepping the problem.  Given
that the size of this hash table is fixed, the lookup time of this
operation is still going to approach linear as the number of qdiscs
increases.  I took a quick pass at trying to use rhashtable for this
purpose a few weeks ago but dropped it when I realized many of the
table operations (which can trigger resize events) need to happen
while holding the rtnl lock.  I still think it would be possible to
use a dynamically sizable datastructure for this purpose, but it will
be a fair amount of work to change the current locking semantics to
make it work...