On Sunday 08 August 2004 8:47 am, Alan Stern wrote:
> On Sat, 7 Aug 2004, David Brownell wrote:
> > Alan Stern wrote:
> > > In fact that can't happen; khubd can't wake up suspended devices.
> >
> > Except for its remote wakeup path... :)
>
> Forgot about that one... it didn't exist until quite recently!
Exactly why we need to be closer to feature-complete before trying
to settle some issues ...
> The
> problem you outlined still can't happen, though. khubd won't see the
> remote wakeup status until it can lock the hub sending the status report;
> so long as suspend() is using that hub, khubd won't interfere.
But locktree() is all that would prevent khubd from interfering,
unless you're moving away from the "no-parent-locking" rule.
Your "no parent-locking" rule (or the "lock only the immediate
parent" variant) would certainly let khubd wake up a hub before
its subtree finished suspending.
Consider a task suspending from a root hub:
SUSPEND( root{ a{v,w}, b{x,y}, c } )
When V issues a wakeup after A's been suspended, and
while B is being suspended, the no-locktree behavior is
to wake A up ... whoa, khubd just interfered with the task
that was suspending!! Likewise with other operations.
The hub suspend() method is simple now, but maybe
that needs to change. OHCI doesn't suspend its root hub
until all ports are suspended (or disconnected); maybe
logic like that should be in the main hub driver. I'd
much prefer to defer such issues.
> Well, there is a slight difference in meaning. Debouncing, for instance,
> could qualify as non-data signalling but not as a subtree operation.
Debouncing should be covered by such a lock, certainly; have
you got something against singleton degenerate trees? :)
> > Or I might just say that I want the locking rules to be simple,
> > and not dominated by an armload of easy-to-misunderstand
> > special case exceptions ... in fact I'm very sure I said that!
> > ...
>
> Exceptions aren't _needed_. I'm not claiming that your algorithms are
> incorrect -- merely that they are more complicated and cause more delays
> than necessary.
You've not yet shown me a "... than necessary" case though;
your examples always allow tasks to interfere with each other.
And I don't see complication at all, except when trying to get
potential performance optimizations by switching to fancier
algorithms. How is the "lock parent then child" policy at all
complicated?
> As for simple locking rules... Your rule seems to go like this:
>
> Every subtree operation starts by calling locktree() on its
> topmost node, then uses further locking as appropriate for
> the kind of subtree traversal it will perform. Proper
Missing important adjective: "task" serialization.
> serialization is guaranteed by the fact that _every_ subtree
> operation calls locktree() at the start and locks each device
> before touching it.
>
> The rule I'm proposing goes like this:
>
> Every subtree operation uses locking as appropriate for the kind
> of subtree traversal it will perform. Proper serialization is
Analogous adjective: "device" serialization.
> guaranteed by the fact that _every_ subtree operation locks each
> device before touching it.
>
> Once you accept that my rule is correct, I think you have to agree that
> it's simpler than your rule.
If it's correct, it's for a different problem though; that's why it's
simpler. It allows two tasks to interfere with each other, forcing
the use of non-deterministic and multipass algorithms to clean
up after such interference. (Rather than knowing that it can't
be un-done till later, so a single-pass algorithm will work.)
The way locktree() prevents them is by _consistently_ implementing the
parent-before-child locking hierarchy. If that policy is implemented
consistently, it's equivalent to locktree. Inconsistent locking
policy implementation ... let's not go there!
> > > While all that is going on, suppose task T2 decides to suspend the
> > > entire
> > > tree starting at A. It uses locktree() to lock A. Then it locks B,
> > > then
> > > it locks, suspends, and unlocks C & D. Then it suspends and unlocks B.
> > > And so on... It doesn't block until it tries to lock G, at which point
> > > it has to wait for T1 to finish up.
> >
> > Right. T1 and T2 are fully sequenced; T1 always completes before T2;
> > they can't interfere with each other. They may be partially concurrent.
>
> To me, saying they are fully sequenced would also imply something about
> the order in which one starts relative to when the other completes.
For example, in this case: for every device D, either (a) only T2
will visit and operate on it, or (b) first T1 then T2 will do so.
> The
> tasks aren't sequenced in that respect; T2 could start before or after T1
> completes. It is true, however, that the order in which they visit any
> particular device _is_ fully determined.
It's fully determined because they use the same locking hierarchy;
if they didn't (as in the no-locktree case), it wouldn't be determined
in the general case. (Toss in T3 and T4, for starters.)
Also fully determined are things like devices suspending before
parent, and resuming after parent is resumed.
> Let's skip the rest of the serialization discussion; I agree that your
> algorithm prevents other tasks from interfering with suspend().
OK.
> > Tree locking handles that by dropping the lock as soon as it's no longer
> > needed. Consider the three classic kinds of tree walk, and their
> > different locking requirements:
> >
> > - prefix (parent first then children) ... task can drop parent's lock
> > as soon as it has (a) visited the parent, (b) locked the children
>
> So we can add: (c) unlock the parent, (d) recurse on the children.
Yes. Ideally one just appends to list end, and takes the next item
off its front. That's a classic algorithm, one I suspect the PM core suspend
code might be better off using.
> > - postfix (parent after each child) ... pretty common, must hold
>
> Don't you mean "children first, then parent"?
Yes, parent after "all children". Cut/paste error, sorry!
> > lock until after visiting children. All tree traversals can lock
> > like this, modulo performance tradeoffs.
> >
> > - infix (parent after each child) ... not all that common, must
> > hold lock until after last child (like postfix).
> >
> > I've already described how to make khubd use a prefix walk to get
> > rid of that one performance issue that bothered you ... SOP could
> > use the same policy. Note that suspend() is a good example of a
> > postfix walk, and resume() could be implemented as a prefix walk.
>
> Now here's another problem. The fact is, subtree operations in general
> can't safely use your prefix-traversal locking pattern. You would run
> into problems in step (d), because once the parent is unlocked new
> children can be added.
Which by definition is perfectly OK, otherwise you couldn't have
been safe using the postfix locking pattern ... :)
Remember that what's happening is "apply algorithm to subtree",
the traversal is a part of "algorithm", not part of "apply". For
singleton degenerate subtrees, traversal is trivial: one visit, so calling
it "prefix" or "postfix (or whatever) is pointless. For proper subtrees,
what I said should be clearer: if the algorithm is prefix, then you
can't use postfix locking; and vice versa.
> > And again: using an unlock-early policy with a prefix walk is
> > fundamentally a performance issue, not a correctness one.
>
> No. It is a correctness issue, as shown above.
If a prefix walk is correct, then unlock-early is a performance tweak.
Nothing else.
If unlock-early is incorrect, then prefix traversal would also be
incorrect ... likely it's a postfix algorithm, not a prefix one.
Otherwise there'd be no need to keep those other locks,
or care about things like siblings added after the algorithm
had "finished" with the parent node.
> > > The code used by suspend won't work for SOP. T2 running SOP starting at
> > > A, for example, would need to explicitly lock all the nodes before it
> > > could start doing anything. Otherwise the possibility would exist that
> > > the previously-started T1 could still be doing something below G, which
> > > would be bad.
> >
> > Oh, so there's an _additional_ constraint on SOP: it really doesn't
> > like concurrent operations.
>
> This isn't an _additional_ constraint; it's one I had mentioned
> previously. I said that SOP "had to prevent other tasks from working on
> devices _before_ SOP had touched them
It's not a constraint I can read into those words even now, though
No matter.
> > Is there a real-world use case behind SOP? (It's clearly not
> > "Standard Operating Procedure" despite its TLA.)
>
> (The acronym was meant to be "Subtree OPeration".) No, there isn't. I'm
> merely trying to preserve a kind of temporal symmetry. With locktree,
> once T2 initializes, T1 can't alter the state of any device after T2 has
> touched it.
Depends a lot on what T1 and T2 are doing!! And I'd have said it
differently (more like we both said it above): If both touch the
device, T1 touches first.
> I'm proposing a situation where, once T2 initializes, T1
> isn't allowed to alter the state of any device _before_ T2 has touched it.
> Simple locking can do this with no help from locktree.
But locktree() doesn't hurt either, to get that first lock;
T2 just needs a multi-pass algorithm, and the locking pass
grabs a whole bunch of locks after locktree() returns.
> > > Concurrency is allowed whenever it is _safe_ (which must be
> > > determined according to the nature of the particular operations
> > > acting concurrently). Serialization is achieved simply by
> > > locking device nodes.
> >
> > And if "locking device nodes" uses locktree(), or requires holding
> > the parent node's lock, you're not saying anything different from
> > what I've said.
>
> But "locking device nodes" _doesn't_ use locktree() or reqire holding the
> parent node's lock. It simply means: down(&u->serialize).
I was pointing out a relationship between the two approaches.
You're the one who suggested talking about "locking device
nodes" rather than saying exactly how it was done ... very
specifically to move away from saying it means down(serialize).
Have you changed your mind on that?
> > If there's nothing like locktree() to manage the basic task
> > serialization, I'll have to disagree on basic principles. See
> > the earlier parts of this message ... something like it is needed
> > to prevent two tasks from interfering with each other, just
> > grabbing locks from the middle of the tree can NEVER provide
> > task serialization.
>
> You keep saying that, and I don't understand why.
Again, see the example at the top of this message.
Consider when more than two tasks are active too;
when tasks touch a node, they should always do it in
the same order.
> Since suspend() and
> resume() are the two most problematic subtree operations, here are some
> explicit algorithms to provide a counterexample to your statement:
Ones that don't use the simple down() scheme you've been
talking about, note -- they added a "must own parent lock"
rule. Except (!!) when getting the first lock; ergo, you've got
those "tasks interfere with each other" problems, which comes
from thosee exceptions-to-rule. :)
> > And if you accept that locks after the initial one aren't acquired
> > by locktree, but by the task performing the operation, I don't see
> > any issue either. Some tasks (like khubd and resume) could
> > use a prefix tree traversal, and drop locks earlier than others
> > that need postfix traversal (like suspend).
>
> See above for why prefix tree traversal isn't safe in general.
I never said that only prefix algorithms existed, quite the
contrary. Did you think those words said otherwise?
> I was concerned about the fact that khubd has to keep the hub locked
> during usb_disconnect(), hub_port_init(), and usb_new_device(). Those are
> the time-consuming steps, and they would interfere with another task that
> wanted to use locktree() on some device below a port other than the one
> khubd was using.
So long as there's a device node in hdev->children[], the prefix algorithm
lets that node's lock be used instead of holding the hub's lock. The node
could be stored there earlier than we do now by someone willing to spend
time on a performance patch.
- Dave
-------------------------------------------------------
SF.Net email is sponsored by Shop4tech.com-Lowest price on Blank Media
100pk Sonic DVD-R 4x for only $29 -100pk Sonic DVD+R for only $33
Save 50% off Retail on Ink & Toner - Free Shipping and Free Gift.
http://www.shop4tech.com/z/Inkjet_Cartridges/9_108_r285
_______________________________________________
[EMAIL PROTECTED]
To unsubscribe, use the last form field at:
https://lists.sourceforge.net/lists/listinfo/linux-usb-devel
