From: NeilBrown <neilb@suse.com>
To: "J. Bruce Fields" <bfields@fieldses.org>
Cc: Jeff Layton <jlayton@kernel.org>,
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 10/12] fs/locks: create a tree of dependent requests.
Date: Fri, 09 Nov 2018 17:24:04 +1100 [thread overview]
Message-ID: <87bm6ywyyj.fsf@notabene.neil.brown.name> (raw)
In-Reply-To: <20181109030913.GA8831@fieldses.org>
[-- Attachment #1: Type: text/plain, Size: 3959 bytes --]
On Thu, Nov 08 2018, J. Bruce Fields wrote:
> On Fri, Nov 09, 2018 at 11:38:19AM +1100, NeilBrown wrote:
>> On Thu, Nov 08 2018, J. Bruce Fields wrote:
>>
>> > On Mon, Nov 05, 2018 at 12:30:48PM +1100, NeilBrown wrote:
>> >> When we find an existing lock which conflicts with a request,
>> >> and the request wants to wait, we currently add the request
>> >> to a list. When the lock is removed, the whole list is woken.
>> >> This can cause the thundering-herd problem.
>> >> To reduce the problem, we make use of the (new) fact that
>> >> a pending request can itself have a list of blocked requests.
>> >> When we find a conflict, we look through the existing blocked requests.
>> >> If any one of them blocks the new request, the new request is attached
>> >> below that request, otherwise it is added to the list of blocked
>> >> requests, which are now known to be mutually non-conflicting.
>> >>
>> >> This way, when the lock is released, only a set of non-conflicting
>> >> locks will be woken, the rest can stay asleep.
>> >> If the lock request cannot be granted and the request needs to be
>> >> requeued, all the other requests it blocks will then be woken
>> >
>> > So, to make sure I understand: the tree of blocking locks only ever has
>> > three levels (the active lock, the locks blocking on it, and their
>> > children?)
>>
>> Not correct.
>> Blocks is only vertical, never horizontal. Siblings never block each
>> other.
>> So one process hold a lock on a byte, and 27 other process want a lock
>> on that byte, then there will be 28 levels in a narrow tree - it is
>> effectively a queue.
>> Branching (via siblings) only happens when a child conflict with only
>> part of the lock held by the parent.
>> So if one process locks 32K, then two other processes request locks on
>> the 2 16K halves, then 4 processes request locks on the 8K quarters, and
>> so-on, then you could end up with 32767 processes in a binary tree, with
>> half of them all waiting on different individual bytes.
>
> Maybe I should actually read the code carefully instead of just skimming
> the changelog and jumping to conclusions.
>
> I think this is correct, but I wish we had an actual written-out
> argument that it's correct, because intuition isn't a great guide for
> posix file locks.
>
> Maybe:
>
> Waiting and applied locks are all kept in trees whose properties are:
>
> - the root of a tree may be an applied or unapplied lock.
> - every other node in the tree is an unapplied lock that
> conflicts with every ancestor of that node.
>
> Every such tree begins life as an unapplied singleton which obviously
> satisfies the above properties.
>
> The only ways we modify trees preserve these properties:
>
> 1. We may add a new child, but only after first verifying that it
> conflicts with all of its ancestors.
> 2. We may remove the root of a tree, creating a new singleton
> tree from the root and N new trees rooted in the immediate
> children.
> 3. If the root of a tree is not currently an applied lock, we may
> apply it (if possible).
> 4. We may upgrade the root of the tree (either extend its range,
> or upgrade its entire range from read to write).
>
> When an applied lock is modified in a way that reduces or downgrades any
> part of its range, we remove all its children (2 above).
>
> For each of those child trees: if the root of the tree applies, we do so
> (3). If it doesn't, it must conflict with some applied lock. We remove
> all of its children (2), and add it is a new leaf to the tree rooted in
> the applied lock (1). We then repeat the process recursively with those
> children.
>
Thanks pretty thorough - and even looks correct.
I'll re-reading some time when it isn't late, and maybe make it into a
comment in the code.
I agree, this sort of documentation can be quite helpful.
Thanks,
NeilBrown
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]
next prev parent reply other threads:[~2018-11-09 16:03 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-11-05 1:30 [PATCH 00/12] Series short description NeilBrown
2018-11-05 1:30 ` [PATCH 02/12] fs/locks: split out __locks_wake_up_blocks() NeilBrown
2018-11-05 1:30 ` [PATCH 08/12] fs/locks: always delete_block after waiting NeilBrown
2018-11-05 1:30 ` [PATCH 06/12] locks: use properly initialized file_lock when unlocking NeilBrown
2018-11-05 1:30 ` [PATCH 01/12] fs/locks: rename some lists and pointers NeilBrown
2018-11-08 20:26 ` J. Bruce Fields
2018-11-09 0:32 ` NeilBrown
2018-11-09 3:11 ` J. Bruce Fields
2018-11-05 1:30 ` [PATCH 04/12] gfs2: properly initial file_lock used for unlock NeilBrown
2018-11-05 12:18 ` Jeff Layton
2018-11-06 1:48 ` NeilBrown
2018-11-06 13:20 ` Jeff Layton
2018-11-05 1:30 ` [PATCH 05/12] ocfs2: " NeilBrown
2018-11-05 1:30 ` [PATCH 07/12] fs/locks: allow a lock request to block other requests NeilBrown
2018-11-05 1:30 ` [PATCH 09/12] fs/locks: change all *_conflict() functions to return bool NeilBrown
2018-11-05 1:30 ` [PATCH 03/12] NFS: use locks_copy_lock() to copy locks NeilBrown
2018-11-05 1:30 ` [PATCH 11/12] locks: merge posix_unblock_lock() and locks_delete_block() NeilBrown
2018-11-05 1:30 ` [PATCH 10/12] fs/locks: create a tree of dependent requests NeilBrown
2018-11-08 21:30 ` J. Bruce Fields
2018-11-09 0:38 ` NeilBrown
2018-11-09 3:09 ` J. Bruce Fields
2018-11-09 6:24 ` NeilBrown [this message]
2018-11-09 15:08 ` J. Bruce Fields
2018-11-05 1:30 ` [PATCH 12/12] VFS: locks: remove unnecessary white space NeilBrown
2018-11-08 21:35 ` [PATCH 00/12] Series short description J. Bruce Fields
2018-11-12 1:14 [PATCH 00/12 v5] locks: avoid thundering-herd wake-ups NeilBrown
2018-11-12 1:14 ` [PATCH 10/12] fs/locks: create a tree of dependent requests NeilBrown
2018-11-12 15:09 ` J. Bruce Fields
2018-11-29 23:04 [PATCH 00/12 v6] fs/locks: avoid thundering-herd wake-ups NeilBrown
2018-11-29 23:04 ` [PATCH 10/12] fs/locks: create a tree of dependent requests NeilBrown
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=87bm6ywyyj.fsf@notabene.neil.brown.name \
--to=neilb@suse.com \
--cc=bfields@fieldses.org \
--cc=ffilzlnx@mindspring.com \
--cc=jlayton@kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mwilck@suse.de \
--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).