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

[Craig Gallek]

On Thu, Jul 7, 2016 at 4:36 PM, Jiri Kosina <jikos@xxxxxxxxxx> wrote:
> From: Jiri Kosina <jkosina@xxxxxxx>
>
> 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@xxxxxxx>
> ---
>
> 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...