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? > > 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. > 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? > > 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. > > Without giving it much deep though, I eould expect that you don't > > actually need to traverse the USB device tree. > > I think I just need to post the code with the algorithm and let you see > what it's doing. I do need information about all the devices on the > port, and I could keep that information in the xHCI driver and only > update the worst-case schedule with the changed endpoints. However, as > I said I started to reproduce the USB core tree structure when I tried > to figure out how to store this information. It seemed better to > implement the algorithm the dumb, simple way, get it correct, and then > optimize it. Okay, I'll wait to see it. 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
