On Sat, 7 Aug 2004, David Brownell 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! 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 never
mind; we need to guarantee that _nothing_ (including khubd!) can wake up a
suspended device before suspend() completes.
> > a non-hub, which is why I use this phrasing.) A better name might be
> > "subtree operations"; if you don't mind I'll start using that name in
> > place of the other.
>
> I started out talking about tree/subtree operations, but that seemed
> to invite misunderstandings ... which is why I also started to talk about
> a class of operations that required subtree operations. Namely,
> those which aren't sending differential/data signaling down the wires.
Well, there is a slight difference in meaning. Debouncing, for instance,
could qualify as non-data signalling but not as a subtree operation. At
any rate, the terminology doesn't really matter.
> 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!
>
> We may come up with cases where exceptions are needed,
> but let's look at those cases as they appear. So far you've
> not shown me any cases where they're needed. (Though
> there's still that subsys.rwsem problem, which seems to me
> not unlike a driver model design flaw. Not USB-specific.)
That rwsem problem was a separate issue, nothing to do with this question.
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.
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
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
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.
> > 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. 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.
Let's skip the rest of the serialization discussion; I agree that your
algorithm prevents other tasks from interfering with suspend().
> 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. Or
maybe you really meant something different: (a') locktree() the parent,
(b') visit the parent, (c') unlock the parent, (d') recurse on the
children?
> - postfix (parent after each child) ... pretty common, must hold
Don't you mean "children first, then parent"?
> 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. You might end up visiting (and trying to unlock!)
children you hadn't locked. With the alternate (a') - (d') interpretation
you run the risk of missing a child that was added after you had skipped
over its formerly empty slot.
> Key point: so long as locktree() is used to get the first lock, the
> kind of tree traversal used during the tree operation need not be
> visible to other tasks. Because locktree() established the basic
> task-level serialization.
>
> 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.
> > 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 but which was okay for concurrent
execution on devices _afterwards_..." And it's not fair to say SOP
"really doesn't like concurrent operations"; SOP is fine with concurrent
operations affecting a device after SOP has visited it. SOP only dislikes
concurrent operations on a device before it has been visited.
> Sounds to me like SOP is just an
> academic example then ... normally one wants it to not matter
> whether task T1 completes before T2 starts. Designs usually quite
> work hard to avoid "one lock to rule them all" models ... :)
Let's say that SOP includes an initialization stage during which
concurrent operations are acceptable, but after that no other task should
touch a node before SOP is finished with it. While still hypothetical, I
think this would fall within the parameters of the designs you mention.
> 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. 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.
> I described prefix locking several email messages ago, as the
> way to address the (potential) performance issue that bothered
> you in the khubd context. SOP could do the same; it addresses
> this kind of issue.
SOP can't use prefix locking for the reasons mentioned above, but you're
right that it can use an alternate scheme to get the desired result. If
it did then it wouldn't need to use locktree(). The same is true for
suspend and resume!
> > 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).
> 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. Since suspend() and
resume() are the two most problematic subtree operations, here are some
explicit algorithms to provide a counterexample to your statement:
Suspend(u):
down(&u->serialize)
Call suspend_subr(u)
up(&u->serialize)
Suspend_subr(u):
if u->state is NOTATTACHED or SUSPENDED then return
For each child of u {
down(&child->serialize)
call suspend_subr(child)
}
Send suspend_port message to u->parent
u->state = SUSPENDED
For each child of u:
up(&child->serialize)
Resume(u):
down(&u->serialize)
if u->state is SUSPENDED then:
Send resume_port message to u->parent
u->state = CONFIGURED or ADDRESS
For each child of u, call resume(child)
up(&u->serialize)
The correctness of these algorithms depends on the invariant that if
u->parent->state is SUSPENDED then u->state is either SUSPENDED or
NOTATTACHED. This in turn depends on the fact that it's impossible to
resume, reset, or do pretty much anything apart from disconnect() to a
device whose parent hub is suspended. I don't see reliance on this
invariant as a complication or disadvantage; your routines also rely on it
in the tests made near the beginning of __usb_suspend_device().
Can you show any way in which these algorithms fail to provide proper
serialization? In particular, can you show any way to resume a device
below u after suspend(u) has visited it and before suspend(u) completes?
> 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. As it
turns out, somewhat by coincidence it _is_ safe for resume(). That's
because a newly-added child doesn't need to be resumed. (Note that I
haven't been complaining about resume, though; I've been complaining about
using locktree in khubd and usb_reset_device.)
As for khubd, that's a different story. When processing hub events khubd
doesn't use prefix traversal; it comes closer to infix traversal. This is
because for each port, it has to read the port status before doing
anything to the subtree below the port. Furthermore, I was never
concerned about khubd releasing its lock on the hub when moving from one
port to the next; after all most events involve changes on only one port.
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.
Alan Stern
-------------------------------------------------------
This SF.Net email is sponsored by OSTG. Have you noticed the changes on
Linux.com, ITManagersJournal and NewsForge in the past few weeks? Now,
one more big change to announce. We are now OSTG- Open Source Technology
Group. Come see the changes on the new OSTG site. www.ostg.com
_______________________________________________
[EMAIL PROTECTED]
To unsubscribe, use the last form field at:
https://lists.sourceforge.net/lists/listinfo/linux-usb-devel
