linux-kernel - Re: [PATCH v8 5/6] lib/dlock-list: Enable faster lookup with hashing

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]

Message-ID: <20171101084021.GL26128@quack2.suse.cz>
Date:   Wed, 1 Nov 2017 09:40:21 +0100
From:   Jan Kara <jack@...e.cz>
To:     Waiman Long <longman@...hat.com>
Cc:     Alexander Viro <viro@...iv.linux.org.uk>, Jan Kara <jack@...e.com>,
        Jeff Layton <jlayton@...chiereds.net>,
        "J. Bruce Fields" <bfields@...ldses.org>,
        Tejun Heo <tj@...nel.org>,
        Christoph Lameter <cl@...ux-foundation.org>,
        linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org,
        Ingo Molnar <mingo@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Andi Kleen <andi@...stfloor.org>,
        Dave Chinner <dchinner@...hat.com>,
        Boqun Feng <boqun.feng@...il.com>,
        Davidlohr Bueso <dave@...olabs.net>
Subject: Re: [PATCH v8 5/6] lib/dlock-list: Enable faster lookup with hashing

On Tue 31-10-17 14:50:59, Waiman Long wrote:
> Insertion and deletion is relatively cheap and mostly contention
> free for dlock-list. Lookup, on the other hand, can be rather costly
> because all the lists in a dlock-list will have to be iterated.
> 
> Currently dlock-list insertion is based on the cpu that the task is
> running on. So a given object can be inserted into any one of the
> lists depending on what the current cpu is.
> 
> This patch provides an alternative way of list selection. The caller
> can provide a object context which will be hashed to one of the list
> in a dlock-list. The object can then be added into that particular
> list. Lookup can be done by iterating elements in the provided list
> only instead of all the lists in a dlock-list.
> 
> The new APIs are:
> 
> struct dlock_list_head *dlock_list_hash(struct dlock_list_heads *, void *);
> void dlock_list_add(struct dlock_list_node *, struct dlock_list_head *);
> 
> Signed-off-by: Waiman Long <longman@...hat.com>

Hum, do we have any users for this API? And wouldn't they also need to
control how many lists are allocated then?

								Honza

> ---
>  include/linux/dlock-list.h |  9 ++++++++
>  lib/dlock-list.c           | 51 +++++++++++++++++++++++++++++++++++++++-------
>  2 files changed, 53 insertions(+), 7 deletions(-)
> 
> diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h
> index c00c7f9..b374101 100644
> --- a/include/linux/dlock-list.h
> +++ b/include/linux/dlock-list.h
> @@ -133,6 +133,15 @@ extern void dlock_lists_add(struct dlock_list_node *node,
>  extern void dlock_lists_del(struct dlock_list_node *node);
>  
>  /*
> + * Instead of individual list mapping by CPU number, it can be based on
> + * a given context to speed up loockup performance.
> + */
> +extern struct dlock_list_head *dlock_list_hash(struct dlock_list_heads *dlist,
> +					       void *context);
> +extern void dlock_list_add(struct dlock_list_node *node,
> +			   struct dlock_list_head *head);
> +
> +/*
>   * Find the first entry of the next available list.
>   */
>  extern struct dlock_list_node *
> diff --git a/lib/dlock-list.c b/lib/dlock-list.c
> index a4ddecc..f3667aa 100644
> --- a/lib/dlock-list.c
> +++ b/lib/dlock-list.c
> @@ -20,6 +20,7 @@
>  #include <linux/lockdep.h>
>  #include <linux/slab.h>
>  #include <linux/cpumask.h>
> +#include <linux/jhash.h>
>  
>  /*
>   * The distributed and locked list is a distributed set of lists each of
> @@ -166,6 +167,48 @@ bool dlock_lists_empty(struct dlock_list_heads *dlist)
>  EXPORT_SYMBOL(dlock_lists_empty);
>  
>  /**
> + * dlock_list_hash - Hash the given context to a particular list
> + * @dlist: The dlock list
> + * @ctx  : The context for hashing
> + */
> +struct dlock_list_head *dlock_list_hash(struct dlock_list_heads *dlist,
> +					void *ctx)
> +{
> +	unsigned long val = (unsigned long)ctx;
> +	u32 hash;
> +
> +	if (unlikely(!nr_dlock_lists)) {
> +		WARN_ON_ONCE(1);
> +		return &dlist->heads[0];
> +	}
> +	if (val < nr_dlock_lists)
> +		hash = val;
> +	else
> +		hash = jhash2((u32 *)&ctx, sizeof(ctx)/sizeof(u32), 0)
> +				% nr_dlock_lists;
> +	return &dlist->heads[hash];
> +}
> +EXPORT_SYMBOL(dlock_list_hash);
> +
> +/**
> + * dlock_list_add - Add a node to a particular head of dlock list
> + * @node: The node to be added
> + * @head: The dlock list head where the node is to be added
> + */
> +void dlock_list_add(struct dlock_list_node *node,
> +		    struct dlock_list_head *head)
> +{
> +	/*
> +	 * There is no need to disable preemption
> +	 */
> +	spin_lock(&head->lock);
> +	node->head = head;
> +	list_add(&node->list, &head->list);
> +	spin_unlock(&head->lock);
> +}
> +EXPORT_SYMBOL(dlock_list_add);
> +
> +/**
>   * dlock_lists_add - Adds a node to the given dlock list
>   * @node : The node to be added
>   * @dlist: The dlock list where the node is to be added
> @@ -178,13 +221,7 @@ void dlock_lists_add(struct dlock_list_node *node,
>  {
>  	struct dlock_list_head *head = &dlist->heads[this_cpu_read(cpu2idx)];
>  
> -	/*
> -	 * There is no need to disable preemption
> -	 */
> -	spin_lock(&head->lock);
> -	node->head = head;
> -	list_add(&node->list, &head->list);
> -	spin_unlock(&head->lock);
> +	dlock_list_add(node, head);
>  }
>  EXPORT_SYMBOL(dlock_lists_add);
>  
> -- 
> 1.8.3.1
> 
> 
-- 
Jan Kara <jack@...e.com>
SUSE Labs, CR