On Wed, Jul 03, 2002, David Brownell <[EMAIL PROTECTED]> wrote:
> [ re why a separate list of URBs vs checking the schedule ]
>
> > Actually, you *MUST* maintain a list of outstanding URB's. Since the HC
> > doesn't tell the HCD which URB's have completed, we need to check all of
> > them to determine which one's completed.
>
> It does say which TDs have completed though ... and as I pointed
> out, that's quite sufficient for knowing which URBs completed.
If by "says which TDs have completed" you mean that it twiddles some
bits in the TD, you are correct.
But if you mean it actually gives a list to the HCD of the completed
TD's, QH's and/or URB's, you are wrong.
> It may even be less work to check the schedule than the list of
> all URBs. (It's possible to skip chunks of the periodic schedule,
> and the URBs held there.)
If what you mean by "less work" is processor work, that can be debated. I
think there's cases where that will be true and cases where it won't be.
I think it's moot given the likely difference in speed is more than
outweighed by additional complexity in code.
If what you mean by "less work" is code, it definately won't be.
> > The only other solution is to walk the schedule, but that requires
> > complicated code to convert bus addresses into kernel addresses. Not to
> > mention it's effectively a list anyway and it still needs a lock.
>
> Or maintain a "shadow schedule" which is what EHCI does. Much
> simpler and more efficient ... only OHCI needs that annoying
> done-list processing, which requires a bus_to_virt() analogue.
I saw that in the EHCI code. Can you elaborate on what it does?
Since we need to check each URB to see if it's done, I don't see how
using a "shadown schedule" is any better. The current list is the most
efficient way of doing that.
The only possible optimization I can see would be to not check some
periodic URB's, but we can't do that because we don't know definitively
or not if the HC has processed the TD's since the last interrupt.
> > The reason we don't do it that way is because it's dumb. I'm sure if you
> > try to implement what you're proposing you'll see just how complicated
> > it is.
>
> On the contrary (and as I've already said) -- I did implement it,
> which is how I know it's a lot simpler. And why I thought it was
> worth commenting on the relative complexity of _both_ UHCI drivers.
Hmm, I was hoping for an actual patch...
> (Or were you meaning "dumb" in the sense of "good because it's
> so simple/effective"? As in "smart clients, dumb servers"? :)
In this case it would seem like dumb HC, smart HCD.
> > However, when we drop the lock, the other CPU's are free to do pretty
> > much anything to the list.
>
> Like I said ... that's fine, and it needn't cause any confusion unless
> whatever code scans the schedule is being buggy. Heck, it's an exact
> corrollary of the problem of updating the hardware's view of that same
> schedule: if the one problem can be solved, so can the other.
I fail to see the corollary.
The hardware processes the schedule once, and at the next frame it
starts from the beginning again.
The interrupt handler needs to walk the list of URB's once and only
once.
The problem is really with removing entries from the list. There's
special code in the UHCI HCD drivers to unlink the QH and then free the
memory for the QH on the next frame. This way there is no race. Take a
look at the ASYNC_UNLINK processing to see what I'm talking about.
There are no provisions like this in the urb_list case. If we have a
list like this
A - B - C - D - E
and we're processing URB B and C gets removed while we're traversing the
list, thanks can break. That's what we need to protect against.
usb-uhci-hcd and ehci-hcd do it similarly. uhci-hcd does it completely
differently.
> > Plus, you still need a lock to prevent multiple CPU's from modifying the
> > schedule.
>
> Only one lock is needed, no more. Adding more (to get finer lock
> granularity) sometimes helps with performance, but that's not what
> you've argued.
No, you're just misunderstanding.
If you have a list of URB's, you need a lock. Period. End of story. The
HC may provide this functionality (is in OHCI), but in UHCI the HC
doesn't help us.
As a result, you cannot hold the lock for the list of URB's when you
call the completion callback, since the completion callback may call a
function which then needs to obtain that same lock.
However, you knew that already since ehci-hcd protects against that by
dropping the lock before making the completion callback. However, it
adds extra complexity.
> > What I did say is that they have implemented the necessary the logic
> > that you're advocating and it's hacky, kludgy, contains arbitrary
> > processing limits and nothing like it is ever going to see uhci.c.
>
> You must have been reading what someone else wrote. For starters,
> the "usb-uhci" codebase does _not_ implement the approach I sketched.
I know that usb-uhci-hcd has many similarities to what you do in
ehci-hcd, but that are some differences, which may or may not be
relevant to the topic at hand.
I based my comments on trying to interpret what you've said. Since you
were referring to the "schedule" in your previous email, I interpreted
that as the schedule the HC processes. That's where all of my comments
came from.
Thankfully, you've explained that you meant a "shadow schedule" which is
different and thusly isn't as bad as I was led to believe.
> And that approach certainly is neither hacky, nor kludgey, nor even a
> vague bit posessed of arbitrary processing limits.
Actually, it is just as hacky and kludgy...
> > I'm looking at the ehci-hcd driver right now and I'm not sure how you
> > can be sure it's safe. Perhaps it's just you haven't seen any problems
> > because of the lack of USB 2.0 devices? But you have the same locking
> > problems with lists that usb-uhci does, except you don't even try to
> > jump through hoops to workaround it.
>
> Since that driver isn't structured like the "usb-uhci" driver, there
> is no way it could have the same locking problems ... or need the same
> kind of hoop-jumping.
Actually, I was wrong, you do jump through hoops just like usb-uhci.
Take this call chain for instance:
scan_periodic (loops through all of the ehci_shadow union's for that frame)
intr_complete
qh_completions
ehci_urb_complete
urb->complete
usb_unlink_urb (called with the URB which is associated with the next qh
in the shadow list)
hcd_unlink_urb
ehci_urb_dequeue
intr_deschedule which has this tidbit
qh->qh_next.ptr = 0;
Now, you correctly noticed that this call chain can occur and to restart
it, you check to see if next->ptr is set to NULL (to denote the URB was
unlinked) and restart the loop from the beginning since the list has been
changed.
If you look at how usb-uhci-hcd works, you'll see that it does something
very similar, but it uses a flag called unlink_urb_done to restart the
loop from the beginning.
The way uhci-hcd works is by looping through the URB's to determine which
ones are finished and when it has determined one should have it's
completion callback made, it gets moved to another list, complete_list.
Once all of the URB's have been checked, we then loop through all of the
URB's in complete_list, without urb_list being held, and call the
completion routine, safe in knowing that it won't break the list
processing and there won't be a deadlock on urb_list since it's not
holding it. There won't be a deadlock on complete_list because
complete_list is only used by the interrupt handler.
Actually, the kernel guarantees only one instance of the IRQ handler
active at any time, right? If so, I can ditch complete_list_lock. I'll
need to check on this.
Everyone is happy, and the code is simpler and is more efficient since
there's no chance of restarting the list unnecessarily for deleting an
URB.
JE
-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
No, I will not fix your computer.
http://thinkgeek.com/sf
_______________________________________________
[EMAIL PROTECTED]
To unsubscribe, use the last form field at:
https://lists.sourceforge.net/lists/listinfo/linux-usb-devel
