netdev - Re: Ottawa and slow hash-table resize

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]

Date:	Tue, 24 Feb 2015 10:14:44 -0600
From:	Josh Hunt <johunt@...mai.com>
To:	Patrick McHardy <kaber@...sh.net>,
	Daniel Borkmann <daniel@...earbox.net>
CC:	Thomas Graf <tgraf@...g.ch>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	davem@...emloft.net, alexei.starovoitov@...il.com,
	herbert@...dor.apana.org.au, ying.xue@...driver.com,
	netdev@...r.kernel.org, netfilter-devel@...r.kernel.org,
	josh@...htriplett.org
Subject: Re: Ottawa and slow hash-table resize

On 02/24/2015 04:42 AM, Patrick McHardy wrote:
> On 24.02, Daniel Borkmann wrote:
>> On 02/24/2015 09:59 AM, Thomas Graf wrote:
>>> On 02/23/15 at 10:49am, Paul E. McKenney wrote:
>>>> Hello!
>>>>
>>>> Alexei mentioned that there was some excitement a couple of weeks ago in
>>>> Ottawa, something about the resizing taking forever when there were large
>>>> numbers of concurrent additions.  One approach comes to mind:
>>>
>>> @Dave et al,
>>> Just want to make sure we have the same level of understanding of
>>> urgency for this. The only practical problem experienced so far is
>>> loading n*1M entries into an nft_hash set which takes 3s for 4M
>>> entries upon restore. A regular add is actually fine as it provides
>>> a hint and sizes the table accordingly.
>>
>> Btw, there is one remaining bug in nft that Josh Hunt found which
>> should go into 3.20/4.0, it's not in -net tree, so it could have
>> affected testing with nft. We're currently missing max_shift
>> parameter in nft's rhashtable initialization.
>>
>> This means that there will be _no_ expansions as rht_grow_above_75()
>> will end up always returning false. It's not that dramatic when you
>> have a proper hint provided, but when you start out small
>> (NFT_HASH_ELEMENT_HINT = 3) and try to squeeze 1M entries into it,
>> it might take a while.
>>
>> Simplest fix would be, similarly as in other users:
>>
>> diff --git a/net/netfilter/nft_hash.c b/net/netfilter/nft_hash.c
>> index 61e6c40..47abdca 100644
>> --- a/net/netfilter/nft_hash.c
>> +++ b/net/netfilter/nft_hash.c
>> @@ -192,6 +192,7 @@ static int nft_hash_init(const struct nft_set *set,
>>   		.key_offset = offsetof(struct nft_hash_elem, key),
>>   		.key_len = set->klen,
>>   		.hashfn = jhash,
>> +		.max_shift = 20, /* 1M */
>>   		.grow_decision = rht_grow_above_75,
>>   		.shrink_decision = rht_shrink_below_30,
>>   	};
>>
>> But I presume Josh wanted to resend his code ... or wait for nft
>> folks to further review?
>
> We're perfectly fine with that patch, although I'd say lets use a
> slightly larger value (24) to cover what we know people are doing
> using ipset.
>

I just sent a patch similar to Daniel's in the set 'nft hash resize 
fixes' using a max_shift value of 24. I still think this value should be 
tunable, but sent the patch to fix the immediate expansion problem for now.

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