From: Jan Kara <jack@suse.cz>
To: Waiman Long <longman@redhat.com>
Cc: Alexander Viro <viro@zeniv.linux.org.uk>,
Jan Kara <jack@suse.com>, Jeff Layton <jlayton@poochiereds.net>,
"J. Bruce Fields" <bfields@fieldses.org>,
Tejun Heo <tj@kernel.org>,
Christoph Lameter <cl@linux-foundation.org>,
linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
Ingo Molnar <mingo@redhat.com>,
Peter Zijlstra <peterz@infradead.org>,
Andi Kleen <andi@firstfloor.org>,
Dave Chinner <dchinner@redhat.com>,
Boqun Feng <boqun.feng@gmail.com>,
Davidlohr Bueso <dave@stgolabs.net>
Subject: Re: [PATCH v8 5/6] lib/dlock-list: Enable faster lookup with hashing
Date: Wed, 1 Nov 2017 09:40:21 +0100 [thread overview]
Message-ID: <20171101084021.GL26128@quack2.suse.cz> (raw)
In-Reply-To: <1509475860-16139-6-git-send-email-longman@redhat.com>
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
next prev parent reply other threads:[~2017-11-01 8:40 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-10-31 18:50 [PATCH v8 0/6] vfs: Use dlock list for SB's s_inodes list Waiman Long
2017-10-31 18:50 ` [PATCH v8 1/6] lib/dlock-list: Distributed and lock-protected lists Waiman Long
2017-10-31 21:37 ` Davidlohr Bueso
2017-11-01 18:44 ` Waiman Long
2017-11-02 17:04 ` Davidlohr Bueso
2017-11-02 17:30 ` Waiman Long
2017-11-03 13:34 ` Davidlohr Bueso
2017-11-03 14:22 ` [PATCH v3] lib/dlock-list: Scale dlock_lists_empty() Davidlohr Bueso
2017-11-03 16:33 ` Waiman Long
2017-11-06 18:47 ` [PATCH v4] " Davidlohr Bueso
2017-11-06 19:06 ` Waiman Long
2017-11-07 11:59 ` Jan Kara
2017-11-07 17:59 ` Andreas Dilger
2017-11-07 18:57 ` Waiman Long
2017-11-07 19:36 ` James Bottomley
2017-11-08 2:08 ` Boqun Feng
2017-11-09 17:24 ` Davidlohr Bueso
2017-11-09 17:30 ` Peter Zijlstra
2017-11-29 15:29 ` [PATCH v8 1/6] lib/dlock-list: Distributed and lock-protected lists Davidlohr Bueso
2017-10-31 18:50 ` [PATCH v8 2/6] vfs: Remove unnecessary list_for_each_entry_safe() variants Waiman Long
2017-10-31 18:50 ` [PATCH v8 3/6] vfs: Use dlock list for superblock's inode list Waiman Long
2017-10-31 18:50 ` [PATCH v8 4/6] lib/dlock-list: Make sibling CPUs share the same linked list Waiman Long
2017-11-01 8:38 ` Jan Kara
2017-10-31 18:50 ` [PATCH v8 5/6] lib/dlock-list: Enable faster lookup with hashing Waiman Long
2017-11-01 8:40 ` Jan Kara [this message]
2017-11-01 13:16 ` Waiman Long
2017-10-31 18:51 ` [PATCH v8 6/6] lib/dlock-list: Add an IRQ-safe mode to be used in interrupt handler Waiman Long
2017-10-31 21:29 ` Davidlohr Bueso
2017-11-29 15:26 ` [PATCH v8 0/6] vfs: Use dlock list for SB's s_inodes list Davidlohr Bueso
2017-11-29 15:31 ` Waiman Long
2018-02-26 2:47 ` Dave Chinner
2018-02-26 4:05 ` Waiman Long
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171101084021.GL26128@quack2.suse.cz \
--to=jack@suse.cz \
--cc=andi@firstfloor.org \
--cc=bfields@fieldses.org \
--cc=boqun.feng@gmail.com \
--cc=cl@linux-foundation.org \
--cc=dave@stgolabs.net \
--cc=dchinner@redhat.com \
--cc=jack@suse.com \
--cc=jlayton@poochiereds.net \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=longman@redhat.com \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=tj@kernel.org \
--cc=viro@zeniv.linux.org.uk \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).