Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
  s=dk12062016; d=mindspring.com;
  b=EYJtjs433sVE5yezZoIa5k/hZc+C62dlKcq7MFrgL28cYGBnFlVx9eqxJI2FrEmYV+G6CZrMosrRujaS4dSSE+nP6BqfO3MuEoLnjzHo+WklJxmt17Fpl53GqRgn0U63dXp6Q/+VJfWlm0qoi8G+yhc20JduKgwtDJUXQnvi2MmmjotfWnMKHfAaWNQ15EqQJoBtVReAhD3PdLDiMjENY4La8p52V5/0FRsQiSJrOepFIWp+syvLq1d8uo/9s1HQ/YyPBmaEWlt1VisWxecoxLe0ACMqiWbT0ROfoyKMX66bfnL0YcqxhsqFotsZfZibU/Hxv1dyQ8vA4gAox9FaMg==;
  h=Received:From:To:Cc:References:In-Reply-To:Subject:Date:Message-ID:MIME-Version:Content-Type:Content-Transfer-Encoding:X-Mailer:Content-Language:Thread-Index:X-ELNK-Trace:X-Originating-IP;
From:   "Frank Filz" <ffilzlnx@mindspring.com>
To:     "'J. Bruce Fields'" <bfields@fieldses.org>,
        "'NeilBrown'" <neilb@suse.com>
Cc:     "'Jeff Layton'" <jlayton@kernel.org>,
        "'Alexander Viro'" <viro@zeniv.linux.org.uk>,
        <linux-fsdevel@vger.kernel.org>, <linux-kernel@vger.kernel.org>,
        "'Martin Wilck'" <mwilck@suse.de>
References: <153369219467.12605.13472423449508444601.stgit@noble> <20180808195445.GD23873@fieldses.org> <20180808200912.GE23873@fieldses.org>
In-Reply-To: <20180808200912.GE23873@fieldses.org>
Subject: RE: [PATCH 0/4] locks: avoid thundering-herd wake-ups
Date:   Wed, 8 Aug 2018 14:15:24 -0700
Message-ID: <01b001d42f5c$ed082e20$c7188a60$@mindspring.com>
MIME-Version: 1.0
Content-Type: text/plain;
        charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Language: en-us
Thread-Index: AQGA9keEcMCkmDAsuHSuCoEfEmhAOAG1/rx6AXpKEjmlQ0n5QA==
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

> On Wed, Aug 08, 2018 at 03:54:45PM -0400, J. Bruce Fields wrote:
> > On Wed, Aug 08, 2018 at 11:51:07AM +1000, NeilBrown wrote:
> > > If you have a many-core machine, and have many threads all wanting
> > > to briefly lock a give file (udev is known to do this), you can get
> > > quite poor performance.
> > >
> > > When one thread releases a lock, it wakes up all other threads that
> > > are waiting (classic thundering-herd) - one will get the lock and
> > > the others go to sleep.
> > > When you have few cores, this is not very noticeable: by the time
> > > the 4th or 5th thread gets enough CPU time to try to claim the lock,
> > > the earlier threads have claimed it, done what was needed, and
released.
> > > With 50+ cores, the contention can easily be measured.
> > >
> > > This patchset creates a tree of pending lock request in which
> > > siblings don't conflict and each lock request does conflict with its
parent.
> > > When a lock is released, only requests which don't conflict with
> > > each other a woken.
> >
> > Are you sure you aren't depending on the (incorrect) assumption that
> > "X blocks Y" is a transitive relation?
> >
> > OK I should be able to answer that question myself, my patience for
> > code-reading is at a real low this afternoon....
> 
> In other words, is there the possibility of a tree of, say, exclusive
locks with
> (offset, length) like:
> 
> 	(0, 2) waiting on (1, 2) waiting on (2, 2) waiting on (0, 4)
> 
> and when waking (0, 4) you could wake up (2, 2) but not (0, 2), leaving a
process
> waiting without there being an actual conflict.

That implies that the order the locks were received in was:

(0,4)
(2,2)
(1,2)
(0,2)

But couldn't (0,2) have been made only dependent on (0,4)? Of course then
(1,2) is dependent on BOTH (2,2) and (0,2). Does this tree logic handle that
case?

On the other hand, there might be a fairness reason to make (0,2) wait for
(1,2) even though it could have been granted concurrently with (2,2) since
this dependency tree also preserves some of the order of lock requests.

Frank