From: "Robert White" <rwhite@casabyte.com>
To: "William Lee Irwin III" <wli@holomorphy.com>,
"Nikita Danilov" <Nikita@Namesys.COM>
Cc: "Nick Piggin" <piggin@cyberone.com.au>, <elladan@eskimo.com>,
"Rik van Riel" <riel@imladris.surriel.com>,
"David Woodhouse" <dwmw2@infradead.org>, <ptb@it.uc3m.es>,
"Martin J. Bligh" <mbligh@aracnet.com>,
<linux-kernel@vger.kernel.org>, <root@chaos.analogic.com>
Subject: RE: recursive spinlocks. Shoot.
Date: Fri, 23 May 2003 19:39:08 -0700 [thread overview]
Message-ID: <PEEPIDHAKMCGHDBJLHKGMEMJCMAA.rwhite@casabyte.com> (raw)
In-Reply-To: <20030523121838.GY8978@holomorphy.com>
William's comment below, and its direct ancestor from Nikita, seem to
support the recursive locking approach to the locking (of some) resources.
I didn't go into number 4 myself because I was (rightly) sure that the terms
"shortest amount of time reasonably possible" and "correct result" would be
points of contention.
If Nikita's case 1 is indeed "better" on an SMP system (I take no official
position, even though one could be easily deduced from the sum of my
previous arguments... 8-)
> spin_lock(&lock);
> list_for_each_entry(item, ...) {
> do something with item;
> }
> spin_unlock(&lock);
and case 2 is "worse"
> list_for_each_entry(item, ...) {
> spin_lock(&lock);
> do something with item;
> spin_unlock(&lock);
> }
and since each workqueue primitive op is essentially:
workqueue_op() {
lock_workqueue()
perform_actual_primitive_op()
unlock_workqueue()
}
Then the existing solution of calling several workqueue operations as they
exist today (provable by induction) always decompose to case 2.
Calling just one workqueue_op is nominally case 1 (and indistinguishable
from case 2 when the list-length is 1).
So the existing model, for successive (aggregate) workqueue ops greater than
one nets the SMP unfriendly and non-optimal result described in case 2.
(ignoring, for now, the ratio of locked to unlocked instructions in each
particular primitive)
IF, however, an aggregator knows he is going to do several ops in succession
(and wants the aggregation to be atomic) and takes the recursive lock in an
outer context manually, then the event stream:
lock_wokrqueue()
list_for_each_entry(item...) {
some_workque_op(current_item)
}
unlock_workqueue()
by induction actually becomes:
lock_wokrqueue()
list_for_each_entry(item...) {
lock_workqueue(); // Factoring point
perform_actual_primitive_op();
unlock_workqueue(); // Factoring point
}
unlock_workqueue();
At the marked "factoring points" the code is effectively reduced from taking
a lock to something like "if owner == me then increment/decrement
lock_depth" because the ownership is tautological at all factoring points.
(As is the presence of the lock data in the cache etc(?). But even if
everything is inline the compiler probably still can't get rid of the test
because the parts of the lock are almost certainly declared volatile.)
This leads to a couple of questions (not rhetorical, I genuinely don't
know): (and answers probably very by platform)
1) Does the barrier() and test_and_set() operators (e.g. xchgb on an x86),
when executed on the non-lock-owner CPU(s) invalidate the relevant cache
element(s) of the CPU that owns the lock?
If not
2) Do we care that (in a recursive lock) the alterations of the "depth"
value will invalidate the cache elements of the non-owner CPU(s) that are
waiting for the lock to free up (given that the final unlock will commit at
least one such invalidate anyway)?
If the answer (to #1) is that the owning CPUs cache is not invalidated by a
competitors active competition, then recursive locking is extremely cheap
even if the compiler can't get rid of the conditional.
regardless (and this one is a little rhetorical 8-)
3) Does the always-evaluated conditional (owner == me) and its associated
low-level jump/branch impose sufficient unacceptable cost compared to the
complexity of the actual protected operations on the proposed public
interface(s) to justify always forcing the case-2 model? (e.g. most
manhandle_workqueue operations in the example are way more complex than the
cost of the ever-evaluated conditional.)
and of course, for any considered public interface:
4) Do the primitive operations of each/any considered interface perform most
of their task (over the domain of time) with the lock held or released?
5) For a particular interface, does the flexibility of a recursive lock
outweigh the probability of someone coding each/any stupid error and/or the
costs of adding the code to prevent same?
That is, for any public interface that is selected for recursive locking
there will always be some set of primitive operations which can't *ever*
make sense when aggregated (invoked with the lock held in the aggregating
context). In the case of the workqueue example, if you take the lock and
then call the wait-for-workqueue-to-empty-itself call, you will wait forever
because no CPU can take a task off of the queue 'cause it's locked... And
as obvious as that may be to most people, there are going to be people out
there making those kinds of mistakes. The follow-on decision to add
check-primitives to various attractive nuisances is non free.
Rob.
-----Original Message-----
From: William Lee Irwin III [mailto:wli@holomorphy.com]
Sent: Friday, May 23, 2003 5:19 AM
To: Nikita Danilov
Cc: Robert White; Nick Piggin; elladan@eskimo.com; Rik van Riel; David
Woodhouse; ptb@it.uc3m.es; Martin J. Bligh;
linux-kernel@vger.kernel.org; root@chaos.analogic.com
Subject: Re: recursive spinlocks. Shoot.
On Fri, May 23, 2003 at 11:22:11AM +0400, Nikita Danilov wrote:
> and suppose they both are equally correct. Now, in (2) total amount of
> time &lock is held is smaller than in (1), but (2) will usually perform
> worse on SMP, because:
> . spin_lock() is an optimization barrier
> . taking even un-contended spin lock is an expensive operation, because
> of the cache coherency issues.
All good. Also, the arrival rate (i.e. frequency of lock acquisition)
is more important to lock contention than hold time, so they're actually
not being as friendly to big SMP as the comment from Robert White would
suggest. The arrival rate tends to be O(cpus) since whatever codepath
pounds on a lock on one cpu can be executed on all simultaneously.
-- wli
next prev parent reply other threads:[~2003-05-24 2:31 UTC|newest]
Thread overview: 58+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-05-18 9:21 Peter T. Breuer
2003-05-18 16:30 ` Martin J. Bligh
2003-05-18 16:35 ` William Lee Irwin III
2003-05-18 16:49 ` Arjan van de Ven
2003-05-18 16:54 ` William Lee Irwin III
2003-05-18 17:14 ` Martin J. Bligh
2003-05-18 17:24 ` Peter T. Breuer
2003-05-18 22:34 ` David Woodhouse
2003-05-19 13:37 ` Peter T. Breuer
2003-05-19 13:45 ` Jens Axboe
2003-05-19 13:47 ` Arjan van de Ven
[not found] ` <mailman.1053352200.24653.linux-kernel2news@redhat.com>
2003-05-19 23:54 ` Pete Zaitcev
2003-05-20 0:03 ` viro
2003-05-20 0:03 ` Johannes Erdfelt
2003-05-20 3:12 ` Robert White
2003-05-20 11:59 ` Helge Hafting
2003-05-20 12:23 ` Richard B. Johnson
2003-05-20 21:05 ` Robert White
2003-05-20 21:42 ` Richard B. Johnson
2003-05-20 23:06 ` Robert White
2003-05-21 14:01 ` Richard B. Johnson
2003-05-21 21:56 ` Robert White
2003-05-22 0:13 ` viro
2003-05-22 0:32 ` Robert White
2003-05-22 0:46 ` Carl-Daniel Hailfinger
2003-05-21 5:48 ` Nikita Danilov
2003-05-22 1:00 ` Rik van Riel
2003-05-22 3:11 ` Robert White
2003-05-22 4:04 ` Nick Piggin
2003-05-22 4:42 ` Peter T. Breuer
2003-05-22 5:09 ` Nick Piggin
2003-05-23 0:19 ` Robert White
2003-05-23 7:22 ` Nikita Danilov
2003-05-23 9:07 ` Helge Hafting
2003-05-23 12:18 ` William Lee Irwin III
2003-05-24 2:39 ` Robert White [this message]
2003-05-28 16:50 ` Timothy Miller
2003-05-19 2:05 ` Kevin O'Connor
2003-05-19 6:19 ` Jan Hudec
2003-05-19 10:29 ` Helge Hafting
2003-05-19 11:37 ` Nikita Danilov
2003-05-22 1:21 ` Daniel Phillips
2003-05-19 14:28 ` Martin J. Bligh
2003-05-18 18:13 ` Davide Libenzi
[not found] <20030518182010$0541@gated-at.bofh.it>
2003-05-18 19:09 ` Peter T. Breuer
2003-05-18 19:31 ` Davide Libenzi
2003-05-18 19:49 ` Peter T. Breuer
2003-05-18 20:13 ` Davide Libenzi
2003-05-19 20:47 ` Jan Hudec
[not found] <20030518202013$5297@gated-at.bofh.it>
2003-05-18 23:15 ` Peter T. Breuer
2003-05-18 23:26 ` Davide Libenzi
2003-05-19 12:48 ` Peter T. Breuer
2003-05-19 17:15 ` Davide Libenzi
2003-05-19 17:27 ` Peter T. Breuer
2003-05-19 17:57 ` Alan Cox
2003-05-19 19:51 ` Peter T. Breuer
2003-05-19 20:22 ` Robert White
[not found] <20030520231013$3d77@gated-at.bofh.it>
2003-05-21 14:16 ` Peter T. Breuer
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=PEEPIDHAKMCGHDBJLHKGMEMJCMAA.rwhite@casabyte.com \
--to=rwhite@casabyte.com \
--cc=Nikita@Namesys.COM \
--cc=dwmw2@infradead.org \
--cc=elladan@eskimo.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mbligh@aracnet.com \
--cc=piggin@cyberone.com.au \
--cc=ptb@it.uc3m.es \
--cc=riel@imladris.surriel.com \
--cc=root@chaos.analogic.com \
--cc=wli@holomorphy.com \
/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
all inboxes | Powered by JetHome®