On Wed, Jun 3, 2009 at 12:33 PM, Alan Stern<stern@xxxxxxxxxxxxxxxxxxx> wrote: > Dave and Dan: > > Having read through most of ehci-sched.c, I've got some proposals for > improvements. First I'd like to run them by you, to see if you don't > like any of them or have suggestions for better approaches. > > > 1. Periodic bandwidth accounting is wrong. > > The periodic_usecs() and periodic_tt_usecs() routines both work by > counting the allocations for each QH, iTD, and siTD for the frame in > question, thereby arriving at the total number microseconds in use by > periodic transfers during the frame in question. > > But "in use" != "allocated"! An endpoint may have bandwidth allocated > during a frame without having any transfers queued during that frame. > For example, suppose a period-1 Iso endpoint has 10 iTDs queued. Its > bandwidth should still be allocated for _all_ frames, even though the > time is in use for only 10 of them. This seems to be only for iTDs/siTDs right? Since a QH should be scheduled in all frames for its period. > To solve this, I'll create an array of N*8 bytes to store the number of > us allocated for periodic transfers during each uframe for the N frames > in the periodic schedule. This has the advantage of allowing bandwidth > to remain allocated even when an endpoint isn't in use, should we > decide to allow such a thing. Yep, that makes sense. When a QH or iso_stream is scheduled for the first time, add the new allocated bandwidth to the array in all the frames for the QH/iso_stream's period. When the QH/iso_stream is removed, subtract the bandwith...that makes checking the currently reserved bandwidth easy, instead of walking the tree to check each QH or TD scheduled. > To do the same sort of thing for FS/LS periodic transfers, I'll > allocate a data structure for each active TT. It may contain a similar > array to account for allocated bandwidth; it certainly will hold a > list_head for all the QHs and iso_streams going through the TT. Sounds good to me. > > > 2. Fix unlinking of interrupt URBs. > > You've got to admit, intr_deschedule() looks awfully bogus. Unlinking > should be done properly, using the Inactivate bit for FS/LS. I might > also implement unlinking for Iso URBs; that can be done later. > > > 3. Implement siTD back-pointers and FSTNs. > > This is self-explanatory. Strictly speaking, the current code is wrong > to schedule split transfers in uframe 4 or later, because that requires > either a back-pointer or an FSTN. The best way to do FSTNs isn't > obvious; all I can come up with is to allocate a separate Save FSTN for > each frame that needs one. I agree on all counts. > > > 4. Rewrite the FS/LS scheduler. > > In the end, this comes down to a single subroutine to calculate in > which uframes a transfer can be scheduled to start. The computation > isn't hard but it is a little messy. Once it's done, all that remains > is a strategy for choosing which uframe to use. For instance, it might > be better to bias Isoc transfers towards earlier uframes and Interrupt > transfers towards later uframes. Yep...messy. Also, are you planning to differentiate between bandwidth allocation, which should use worst-case timing, and scheduling, which should use best-case timing? I believe the current functions to calculate bandwidth and scheduling, which are taken from the spec section 5.11.3, use worst-case timing (i.e. max bit stuffing). However, as you pointed out before the actual scheduling of transations should use best-case timing. New function(s) would need to be created to calculate the best-case timings. Is there a need for two different arrays for each TT to track both best-case timing, to use in choosing when to schedule transfers, and to track worst-case timing, to use in verifying the various max use rules such as 80% frame use? Also, I think David suggested moving all the TT scheduling code into a common location, so other non-EHCI highspeed Host Controller drivers could use it...are you planning on moving it out into a common area? For that matter, maybe it would be worthwhile to move all the bandwidth code into hcd.c or some other common area? Tracking bandwidth really isn't (or shouldn't be) HCD-specific, right? > > > I don't have any plans to implement rebalancing. Getting this stuff > done is hard enough. > > Alan Stern > > -- > To unsubscribe from this list: send the line "unsubscribe linux-usb" in > the body of a message to majordomo@xxxxxxxxxxxxxxx > More majordomo info at http://vger.kernel.org/majordomo-info.html > -- To unsubscribe from this list: send the line "unsubscribe linux-usb" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
