Re: rhashtable - Cap total number of entries to 2^31

[Florian Westphal <fw@strlen.de>]

Herbert Xu <herbert@gondor.apana.org.au> wrote:
> On Tue, Apr 25, 2017 at 10:48:22AM -0400, David Miller wrote:
> > From: Florian Westphal <fw@strlen.de>
> > Date: Tue, 25 Apr 2017 16:17:49 +0200
> > 
> > > I'd have less of an issue with this if we'd be talking about
> > > something computationally expensive, but this is about storing
> > > an extra value inside a struct just to avoid one "shr" in insert path...
> > 
> > Agreed, this shift is probably filling an available cpu cycle :-)
> 
> OK, but we need to have an extra field for another reason anyway.
> The problem is that we're not capping the total number of elements
> in the hashtable when max_size is not set, this means that nelems
> can overflow which will cause havoc with the automatic shrinking
> when it tries to fit 2^32 entries into a minimum-sized table.

Right, good catch.

I guess eventually we should get rid of min_size and max_size
completely as parameters and keep actual sizing/bucket count internal to
rhashtable.

In fact I would not be surprised if some existing users did set
max_size under assumption it is a 'max element count'.

> ---8<---
> When max_size is not set or if it set to a sufficiently large
> value, the nelems counter can overflow.  This would cause havoc
> with the automatic shrinking as it would then attempt to fit a
> huge number of entries into a tiny hash table.
> 
> This patch fixes this by adding max_elems to struct rhashtable
> to cap the number of elements.  This is set to 2^31 as nelems is
> not a precise count.  This is sufficiently smaller than UINT_MAX
> that it should be safe.
> 
> When max_size is set max_elems will be lowered to at most twice
> max_size as is the status quo.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

[..]

> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
> @@ -165,6 +166,7 @@ struct rhashtable {
>  	atomic_t			nelems;
>  	unsigned int			key_len;
>  	struct rhashtable_params	p;
> +	unsigned int			max_elems;
>  	bool				rhlist;
>  	struct work_struct		run_work;
>  	struct mutex                    mutex;
> @@ -327,8 +329,7 @@ static inline bool rht_grow_above_100(const struct rhashtable *ht,
>  static inline bool rht_grow_above_max(const struct rhashtable *ht,
>  				      const struct bucket_table *tbl)
>  {
> -	return ht->p.max_size &&
> -	       (atomic_read(&ht->nelems) / 2u) >= ht->p.max_size;
> +	return atomic_read(&ht->nelems) >= ht->max_elems;
>  }
>  
>  /* The bucket lock is selected based on the hash and protects mutations
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index f3b82e0..751630b 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -961,6 +961,11 @@ int rhashtable_init(struct rhashtable *ht,
>  	if (params->max_size)
>  		ht->p.max_size = rounddown_pow_of_two(params->max_size);
>  
> +	/* Cap total entries at 2^31 to avoid nelems overflow. */
> +	ht->max_elems = 1u << 31;
> +	if (ht->p.max_size < ht->max_elems / 2)
> +		ht->max_elems = ht->p.max_size * 2;
> +

Looks like instead of adding this max_elems you could instead have fixed this via

if (!ht->p.max_size)
	ht->p.max_size = INT_MAX / 2;

if (ht->p.max_size > INT_MAX / 2)
	return -EINVAL;