linux-kernel - Re: [PATCH] cgroup: use new hashtable implementation

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Wed, 9 Jan 2013 09:55:12 +0800
From:	Li Zefan <lizefan@...wei.com>
To:	Tejun Heo <tj@...nel.org>
CC:	LKML <linux-kernel@...r.kernel.org>,
	Cgroups <cgroups@...r.kernel.org>
Subject: Re: [PATCH] cgroup: use new hashtable implementation

On 2013/1/9 2:17, Tejun Heo wrote:
> Hello, Li.
> 
> On Tue, Jan 08, 2013 at 03:51:45PM +0800, Li Zefan wrote:
>> -static struct hlist_head *css_set_hash(struct cgroup_subsys_state *css[])
>> +static unsigned long css_set_hash(struct cgroup_subsys_state *css[])
>>  {
>>  	int i;
>> -	int index;
>> -	unsigned long tmp = 0UL;
>> +	unsigned long key = 0UL;
>>  
>>  	for (i = 0; i < CGROUP_SUBSYS_COUNT; i++)
>> -		tmp += (unsigned long)css[i];
>> -	tmp = (tmp >> 16) ^ tmp;
>> +		key += (unsigned long)css[i];
>> +	key = (key >> 16) ^ key;
> 
> @key is gonna go through hash function anyway.  Do we still need the
> above (key >> 16) ^ key?  It's not gonna help anything.
> 

Nothing's changed after this patch, so the key will still be passed to
hash_long().

I tested this hash function long ago, and the original version was
without (key >> 16) ^ key, and it produced worse hash collision.

>> -	index = hash_long(tmp, CSS_SET_HASH_BITS);
>> -
>> -	return &css_set_table[index];
>> +	return key;
>>  }
>>  
>>  /* We don't maintain the lists running through each css_set to its
>> @@ -4503,23 +4498,17 @@ int __init_or_module cgroup_load_subsys(struct cgroup_subsys *ss)
>>  	 * this is all done under the css_set_lock.
>>  	 */
>>  	write_lock(&css_set_lock);
>> -	for (i = 0; i < CSS_SET_TABLE_SIZE; i++) {
>> -		struct css_set *cg;
>> -		struct hlist_node *node, *tmp;
>> -		struct hlist_head *bucket = &css_set_table[i], *new_bucket;
>> -
>> -		hlist_for_each_entry_safe(cg, node, tmp, bucket, hlist) {
>> -			/* skip entries that we already rehashed */
>> -			if (cg->subsys[ss->subsys_id])
>> -				continue;
>> -			/* remove existing entry */
>> -			hlist_del(&cg->hlist);
>> -			/* set new value */
>> -			cg->subsys[ss->subsys_id] = css;
>> -			/* recompute hash and restore entry */
>> -			new_bucket = css_set_hash(cg->subsys);
>> -			hlist_add_head(&cg->hlist, new_bucket);
>> -		}
>> +	hash_for_each_safe(css_set_table, i, node, tmp, cg, hlist) {
>> +		/* skip entries that we already rehashed */
>> +		if (cg->subsys[ss->subsys_id])
>> +			continue;
>> +		/* remove existing entry */
>> +		hlist_del(&cg->hlist);
> 
> 		hash_del()?
> 

will fix.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/