LKML Archive on lore.kernel.org
 help / Atom feed
From: Jeff Layton <jlayton@kernel.org>
To: "J. Bruce Fields" <bfields@fieldses.org>, NeilBrown <neilb@suse.com>
Cc: Alexander Viro <viro@zeniv.linux.org.uk>,
	Martin Wilck <mwilck@suse.de>,
	linux-fsdevel@vger.kernel.org,
	Frank Filz <ffilzlnx@mindspring.com>,
	linux-kernel@vger.kernel.org
Subject: Re: [PATCH 0/5 - V2] locks: avoid thundering-herd wake-ups
Date: Sat, 11 Aug 2018 07:56:25 -0400
Message-ID: <0f198c62b057ab7d796746144d458835a6c7433e.camel@kernel.org> (raw)
In-Reply-To: <20180810154742.GE7906@fieldses.org>

On Fri, 2018-08-10 at 11:47 -0400, J. Bruce Fields wrote:
> On Fri, Aug 10, 2018 at 01:17:14PM +1000, NeilBrown wrote:
> > On Thu, Aug 09 2018, J. Bruce Fields wrote:
> > 
> > > On Fri, Aug 10, 2018 at 11:50:58AM +1000, NeilBrown wrote:
> > > > You're good at this game!
> > > 
> > > Everybody's got to have a hobby, mine is pathological posix locking
> > > cases....
> > > 
> > > > So, because a locker with the same "owner" gets a free pass, you can
> > > > *never* say that any lock which conflicts with A also conflicts with B,
> > > > as a lock with the same owner as B will never conflict with B, even
> > > > though it conflicts with A.
> > > > 
> > > > I think there is still value in having the tree, but when a waiter is
> > > > attached under a new blocker, we need to walk the whole tree beneath the
> > > > waiter and detach/wake anything that is not blocked by the new blocker.
> > > 
> > > If you're walking the whole tree every time then it might as well be a
> > > flat list, I think?
> > 
> > The advantage of a tree is that it keeps over-lapping locks closer
> > together.
> > For it to make a difference you would need a load where lots of threads
> > were locking several different small ranges, and other threads were
> > locking large ranges that cover all the small ranges.
> 
> OK, I'm not sure I understand, but I'll give another look at the next
> version....
> 
> > I doubt this is common, but it doesn't seem as strange as other things
> > I've seen in the wild.
> > The other advantage, of course, is that I've already written the code,
> > and I like it.
> > 
> > Maybe I'll do a simple-list version, then a patch to convert that to the
> > clever-tree version, and we can then have something concrete to assess.
> 
> That might help, thanks.
> 

FWIW, I did a bit of testing with lockperf tests that I had written on
an earlier rework of this code:

    https://git.samba.org/jlayton/linux.git/?p=jlayton/lockperf.git;a=summary


The posix01 and flock01 tests in there show about a 10x speedup with
this set in place.

I think something closer to Neil's design will end up being what we want
here. Consider the relatively common case where you have a whole-file
POSIX write lock held with a bunch of different waiters blocked on it
(all whole file write locks with different owners):

With Neil's patches, you will just wake up a single waiter when the
blocked lock is released, as they would all be in a long chain of
waiters.

If you keep all the locks in a single list, you'll either have to:

a) wake up all the waiters on the list when the lock comes free: no lock
is held at that point so none of them will conflict.

...or...

b) keep track of what waiters have already been awoken, and compare any
further candidate for waking against the current set of held locks and
any lock requests by waiters that you just woke.

b seems more expensive as you have to walk over a larger set of locks
on every change.
-- 
Jeff Layton <jlayton@kernel.org>


  reply index

Thread overview: 27+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-08-09  2:04 NeilBrown
2018-08-09  2:04 ` [PATCH 1/5] fs/locks: rename some lists and pointers NeilBrown
2018-08-09  2:04 ` [PATCH 2/5] fs/locks: allow a lock request to block other requests NeilBrown
2018-08-09  2:04 ` [PATCH 3/5] fs/locks: change all *_conflict() functions to return a new enum NeilBrown
2018-08-09 11:09   ` Jeff Layton
2018-08-09 13:09   ` J. Bruce Fields
2018-08-09 23:40     ` NeilBrown
2018-08-10  0:56       ` J. Bruce Fields
2018-08-09  2:04 ` [PATCH 4/5] fs/locks: split out __locks_wake_one() NeilBrown
2018-08-09  2:04 ` [PATCH 5/5] fs/locks: create a tree of dependent requests NeilBrown
2018-08-09 11:17   ` Jeff Layton
2018-08-09 23:25     ` NeilBrown
2018-08-09 14:13   ` J. Bruce Fields
2018-08-09 22:19     ` NeilBrown
2018-08-10  0:36       ` J. Bruce Fields
2018-08-09 17:32 ` [PATCH 0/5 - V2] locks: avoid thundering-herd wake-ups J. Bruce Fields
2018-08-09 22:12   ` NeilBrown
2018-08-10  0:29     ` J. Bruce Fields
2018-08-10  1:50       ` NeilBrown
2018-08-10  2:52         ` J. Bruce Fields
2018-08-10  3:17           ` NeilBrown
2018-08-10 15:47             ` J. Bruce Fields
2018-08-11 11:56               ` Jeff Layton [this message]
2018-08-11 12:35                 ` J. Bruce Fields
2018-08-11 11:51       ` Jeff Layton
2018-08-11 12:21         ` J. Bruce Fields
2018-08-11 13:15           ` Jeff Layton

Reply instructions:

You may reply publically 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=0f198c62b057ab7d796746144d458835a6c7433e.camel@kernel.org \
    --to=jlayton@kernel.org \
    --cc=bfields@fieldses.org \
    --cc=ffilzlnx@mindspring.com \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mwilck@suse.de \
    --cc=neilb@suse.com \
    --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

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org linux-kernel@archiver.kernel.org
	public-inbox-index lkml


Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/ public-inbox