netdev - Re: [v2 PATCH 7/10] rhashtable: Disable automatic shrinking

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

Date:	Sun, 22 Mar 2015 12:17:55 +0000
From:	Thomas Graf <tgraf@...g.ch>
To:	Herbert Xu <herbert@...dor.apana.org.au>
Cc:	"David S. Miller" <davem@...emloft.net>,
	Eric Dumazet <eric.dumazet@...il.com>,
	Patrick McHardy <kaber@...sh.net>,
	Josh Triplett <josh@...htriplett.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	netdev@...r.kernel.org
Subject: Re: [v2 PATCH 7/10] rhashtable: Disable automatic shrinking

On 03/22/15 at 07:04pm, Herbert Xu wrote:
> Automatic shrinking is dangerous because it provides an easy
> way for an adversary to cause us to do unnecessary work.  Thus
> making the resizable hashtable a poor data structure.
> 
> This patch disables automatic shrinking but retains a manual
> shrink function for those cases where insertions and removals
> are overseen by a trusted entity, e.g., nft_hash.

This is misleading. I agree that unconditional shrinking is dangerous.
Shrinking was an optional feature disabled by default before. The
inlining enabled it by default for all users. What is the benefit of
requiring this logic outside of rhashtable over just adding a flag to
enable shrinking at 30% utilization?

> The shrink function will now also shrink to fit rather than halve
> the size of the table.

I like this part a lot

>  int rhashtable_shrink(struct rhashtable *ht)
>  {
> -	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
> +	unsigned size = roundup_pow_of_two(atomic_read(&ht->nelems) * 4 / 3);

If rhashtable_shrink() is called near the 75% border it will cause an
immediate expansion again. Maybe make this * 3 / 2 so we shrink near
30% utilization as before?

> +	struct bucket_table *new_tbl;
> +	struct bucket_table *tbl;
> +	int err;
>  
> -	ASSERT_RHT_MUTEX(ht);
> +	if (size < ht->p.min_size)
> +		size = ht->p.min_size;

We should only shrink if size < old_tbl->size

> -	new_tbl = bucket_table_alloc(ht, old_tbl->size / 2);
> +	new_tbl = bucket_table_alloc(ht, size);
>  	if (new_tbl == NULL)
>  		return -ENOMEM;
--
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