netdev - Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

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:	Fri, 01 May 2015 14:04:35 +0300
From:	Sergei Shtylyov <sergei.shtylyov@...entembedded.com>
To:	Thomas Graf <tgraf@...g.ch>, davem@...emloft.net
CC:	netdev@...r.kernel.org, herbert@...dor.apana.org.au,
	kaber@...sh.net
Subject: Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

Hello.

On 5/1/2015 1:46 AM, Thomas Graf wrote:

> Grow the table quicker than 2x in the beginning to avoid long chains
> of rehashes. The effect is observable in the self-test where table
> jumps are reduced to a minimum after a lot of entries have been added
> in a short period of time. The iterator is able to get a consistent
> view most of the time.

> Signed-off-by: Thomas Graf <tgraf@...g.ch>
> ---
>   lib/rhashtable.c | 37 +++++++++++++++++++++++++++++++++++--
>   1 file changed, 35 insertions(+), 2 deletions(-)

> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 4936fc4..23e7f18 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -271,6 +271,38 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
>   	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
>   }
>
> +static int table_growth_log(unsigned int size)
> +{
> +	/*
> +	 * Table growth:
> +	 *     2 ->   64
> +	 *     4 ->  128
> +	 *     8 ->  128
> +	 *    16 ->  256
> +	 *    32 ->  512
> +	 *    64 ->  512
> +	 *   128 -> 1024
> +	 *   256 -> 2048
> +	 *   512 -> 2048
> +	 *  1024 -> 4096
> +	 *  2048 -> 8192
> +	 *  4096 -> 8192
> +	 */
> +	int log = 5 - (ilog2(size) / 3);
> +
> +	return log > 1 ? log : 1;

    max(log, 1)?

[...]

WBR, Sergei

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