On Fri, Jul 01, 2011 at 01:12:47PM -0400, Alan Stern wrote: > On Fri, 1 Jul 2011, Sarah Sharp wrote: > > > > How is their algorithm going to get implemented in software? Is that > > > your job? > > > > Yes, apparently it is my job. I've convinced them to let me release > > their algorithm in the xHCI driver, so I'll be using that. It's > > actually somewhat hardware specific, because while the xHCI host doesn't > > check whether a changed endpoint pushes the worst-case schedule over the > > top, the hardware does the dynamic scheduling itself. So the algorithm > > actually uses a bit of information about the logic that does the dynamic > > scheduling to make sure it is actually creating the worst-case schedule. > > That sounds kind of tricky. The bandwidth requirements affect when a > transfer can be allowed to take place. Something that might be > perfectly okay in one microframe might be bad in another. How do you > tell the hardware's dynamic scheduler about these restrictions? I don't. The algorithm basically computes the worst-case microframe (or one that is no less crowded than the worst case microframe, since it's an NP complete problem to find the minimum worst case). As I said, it's probably easier to look at the code. > > > Oh dear. You get to implement scheduling for LS/FS, HS, TTs, and SS. > > > Considering that, among all the other HCDs in Linux, only the first has > > > been done correctly, you have your work cut out. > > > > The algorithm covers all those, and also accounts for a couple other > > things. I finally understand the LS/FS/HS and TT scheduling algorithm, > > Really? Good for you, then... I struggled to come up with a good > method for scheduling split transactions. Maybe this algorithm you've > got have been simplified and is less than optimal. Yes, it's less than optimal. Basically it reserves about twice the bandwidth of a FS bus for every TT that has an active periodic endpoint (including potentially for every port on a multi-TT hub). It's assumed LS/FS control and bulk transfers are best effort, and will be included in the HS reservation of 20% for async transfers. So it's entirely possible that one setup that worked under the EHCI host won't work under the Intel xHCI host because we're reserving more of the HS bus for active TTs. > > and I've been putting that into code. I'm still not convinced I > > understand their SuperSpeed algorithm, so those patches will come later. > > I'll post what I have later today. > > Shouldn't SS be essentially the same as HS? It's not quite the same, due to some SuperSpeed-specific requirements. > > > We really ought to coordinate fixing up the TT implementation so that > > > it can be used properly by both xhci-hcd and ehci-hcd. We should also > > > talk about the proper algorithm to use for scheduling with TTs. > > > > So which part of the TT implementation are you talking about? I'm not > > familiar with how EHCI uses the usb_tt structure, but it would be nice > > if we can share some information/code. > > For one thing, we need to store along with the TT a record of how much > time has been committed in each frame. If a hub has per-port TTs, we > need this information for each port. I'm not sure xHCI can make use of that information, since it's just blindly reserving the max bandwidth for each TT with active FS/LS periodic endpoints. Sarah Sharp -- 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
