netdev - Re: net-sched 01/05: add dynamically sized qdisc class hash helpers

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

Message-ID: <486CC328.5070107@trash.net>
Date:	Thu, 03 Jul 2008 14:16:40 +0200
From:	Patrick McHardy <kaber@...sh.net>
To:	Jarek Poplawski <jarkao2@...il.com>
CC:	netdev@...r.kernel.org, devik@....cz
Subject: Re: net-sched 01/05: add dynamically sized qdisc class hash helpers

Jarek Poplawski wrote:
>> +static inline void *qdisc_class_find(struct Qdisc_class_hash *hash, u32 id)
>>     
>
> Why not Qdisc_class_common *?
>   

I originally didn't use container_of but simply required
Qdisc_class_common to be the first element of the
class struct, this is a remnant of that. I'll change it,
thanks.

>> +void qdisc_class_hash_grow(struct Qdisc *sch, struct Qdisc_class_hash *clhash)
>> +{
>> +	struct Qdisc_class_common *cl;
>> +	struct hlist_node *n, *next;
>> +	struct hlist_head *nhash, *ohash;
>> +	unsigned int nsize, nmask, osize;
>> +	unsigned int i, h;
>> +
>> +	/* Rehash when load factor exceeds 0.75 */
>> +	if (clhash->hashelems * 4 <= clhash->hashsize * 3)
>>     
>
> With current init hashsize == 4 this will trigger after adding: 4th,
> 7th, 13th,... class. Maybe we could start with something higher?
>   

We could, but I don't think it makes any difference, for those
small numbers the rehashing is really cheap.

>> +		return;
>> +	nsize = clhash->hashsize * 2;
>> +	nmask = nsize - 1;
>> +	nhash = qdisc_class_hash_alloc(nsize);
>> +	if (nhash == NULL)
>> +		return;
>> +
>> +	ohash = clhash->hash;
>> +	osize = clhash->hashsize;
>> +
>> +	sch_tree_lock(sch);
>> +	for (i = 0; i < osize; i++) {
>> +		hlist_for_each_entry_safe(cl, n, next, &ohash[i], hnode) {
>> +			h = qdisc_class_hash(cl->classid, nmask);
>> +			hlist_add_head(&cl->hnode, &nhash[h]);
>>     
>
> With a large number of classes and changes this could probably give
> noticable delays, so maybe there would be reasonable to add a
> possibility of user defined, ungrowable hashsize as well?

I don't think its really going to be noticable (the numbers are not
*that* large), but I'll try to get some numbers.


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