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

[Jan Kara]

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

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@xxxxxxxx>
SUSE Labs, CR