lkml.org 
[lkml]   [2017]   [Nov]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [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@redhat.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@suse.com>
    SUSE Labs, CR

    \
     
     \ /
      Last update: 2017-11-01 09:41    [W:3.074 / U:0.064 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site