From: Waiman Long <longman@redhat.com>
To: Davidlohr Bueso <dave@stgolabs.net>
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>
Subject: Re: [PATCH v8 1/6] lib/dlock-list: Distributed and lock-protected lists
Date: Thu, 2 Nov 2017 13:30:53 -0400 [thread overview]
Message-ID: <81bb3365-63f3-fea8-d238-e3880a4c8033@redhat.com> (raw)
In-Reply-To: <20171102170431.oq3i5mxtjcg53uot@linux-n805>
On 11/02/2017 01:04 PM, Davidlohr Bueso wrote:
> On Tue, 31 Oct 2017, Waiman Long wrote:
>
>> +/**
>> + * dlock_lists_empty - Check if all the dlock lists are empty
>> + * @dlist: Pointer to the dlock_list_heads structure
>> + * Return: true if list is empty, false otherwise.
>> + * + * This can be a pretty expensive function call. If
>> this function is required
>> + * in a performance critical path, we may have to maintain a global
>> count
>> + * of the list entries in the global dlock_list_heads structure
>> instead.
>> + */
>
> I vote for doing this in the original version. How about the following?
>
>> +bool dlock_lists_empty(struct dlock_list_heads *dlist)
>> +{
>> + int idx;
>> +
>> + for (idx = 0; idx < nr_cpu_ids; idx++)
>> + if (!list_empty(&dlist->heads[idx].list))
>> + return false;
>> + return true;
>> +}
>> +EXPORT_SYMBOL(dlock_lists_empty);
>
> ----------8<-----------------------------------------------
> From: Davidlohr Bueso <dave@stgolabs.net>
> Subject: [PATCH] lib/dlock-list: Scale dlock_lists_empty()
>
> Instead of the current O(N) implementation; at the cost
> of adding an atomic counter. We also need to add a heads
> pointer to the node structure such that we can unaccount
> a thread doing list_del().
>
The counter will then become the single contention point for all
concurrent updates to the dlock-list. So it will have a big impact on
performance. On the other hand, instead of being a counter of # of
items, we can make that a counter of # of non-empty lists. So its value
will only be changed when a list go from empty to non-empty and vice
versa. That will greatly reduce the number of updates to that counter.
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
> ---
> include/linux/dlock-list.h | 2 ++
> lib/dlock-list.c | 40 ++++++++++++++++++++++++++++------------
> 2 files changed, 30 insertions(+), 12 deletions(-)
>
> diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h
> index c00c7f92ada4..dd73d5787885 100644
> --- a/include/linux/dlock-list.h
> +++ b/include/linux/dlock-list.h
> @@ -36,6 +36,7 @@ struct dlock_list_head {
>
> struct dlock_list_heads {
> struct dlock_list_head *heads;
> + atomic_t waiters;
> };
>
> /*
> @@ -44,6 +45,7 @@ struct dlock_list_heads {
> struct dlock_list_node {
> struct list_head list;
> struct dlock_list_head *head;
> + struct dlock_list_heads *heads;
> };
>
I don't want to add a new data item into dlock_list_node as there can be
thousands or even of them in the system. Instead, I prefer increasing the
size of dlock_list_head which only have a limited number of them and
they have unused space because they are cacheline aligned.
Cheers,
Longman
next prev parent reply other threads:[~2017-11-02 17:30 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 [this message]
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
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=81bb3365-63f3-fea8-d238-e3880a4c8033@redhat.com \
--to=longman@redhat.com \
--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=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).