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
