On Mon, Apr 13, 2009 at 5:54 PM, Alan Stern <stern@xxxxxxxxxxxxxxxxxxx> wrote: > On Mon, 13 Apr 2009, Dan Streetman wrote: > >> > The comment's explanation isn't clear enough. What does "illegally >> > delay already scheduled transactions" mean? What's wrong with pushing >> > back existing transactions to later in the frame? And why do transfers >> > longer than 125 us need special treatment? Neither the USB 2.0 spec >> > nor the EHCI spec mentions anything about this. >> >> Maybe "illegally" isn't the most appropriate adjective, but ignoring >> the per-uframe scheduling requirements kind of defeats the purpose of >> scheduling. If we don't care about delaying transfers past the uframe >> where their SSPLIT is scheduled, why not just schedule everything to >> SSPLIT in uframe 0? > > Maybe it's the way you express yourself; I get the feeling we are > talking at cross purposes. From my point of view, pushing back a > transaction means rescheduling its SSPLITs and CSPLITs to occur in > later uframes, by definition. So transfers never get delayed past the > uframe where their SSPLIT is scheduled. This would be rebalancing, which as far as I know isn't done for TT schedules in the current driver. Not that rebalancing is bad, it would be great to add rebalancing to the TT scheduler. But that isn't simple. >> The problem isn't on the low/full-speed side, it's perfectly ok on >> that side to delay a transfer within a frame. The problem is on the >> high-speed side, of managing the TT. Scheduling uses the best case >> timing, so all the "fudges" built in are intended to handle errors, >> not make up for improper scheduling. > > The are also intended to handle delays caused by bit-stuffing. Yep. >> The "correct" way to schedule a >> TT, as I understand it, is to ensure that in the best case, for each >> transfer, the transfer will actually happen in the same uframe as the >> SSPLIT is issued (same in H-frame and B-frame uframe number, EHCI spec >> sec 4.5 fig 4.7). Knowingly scheduling a multi-uframe isoc transfer >> that will force the TT to delay issuing another transfer for one or >> more uframes is not correct scheduling. > > I'm not sure what you mean by this. The scheduler must guarantee that > no more than 188 bytes of data are transferred during a uframe; is that > what you mean? The scheduler is supposed to ensure that for all the SSPLTs issued in any uframe, the TT should be able to at least *start* each of the corresponding transfers. It doesn't have to be able to *complete* all those transfers, as it is ok if the last transfer "carrys over" into the next uframe. This is optimal scheduling; to restrict scheduling so each transfer completed in the right uframe, there is a very small chance of actually using 100% of each uframe, since all the transfers in each uframe would have to combine exactly to 125usec, which is unlikely. The transfer time "carried over" into the next uframe must be accounted for in the next uframe's scheduling, which is what the current code does. >> If the requested uframe isn't full, and the transfer is an isoc >> transfer that is larger than 1 uframe (125usec), then the start >> uframe, and each subsequent fully-used uframe must be empty. > > I still disagree about the requirement that the start uframe be empty. I think we agree. The first uframe doesn't have to be empty, but the scheduling is more complicated if it isn't. The current code puts it starting in an empty uframe because that is easier. >> If not, >> then whatever other transfers were scheduled in those uframes would >> not execute in the uframe they were scheduled to execute in, which >> will very likely cause them to fail. After making sure each >> fully-used uframe is empty, the last partially-used uframe can be >> scheduled using the normal carryover scheduling. >> >> If the requested uframe isn't full, and the transfer isn't an isoc >> transfer larger than 1 uframe, then simple carryover scheduling is >> used. The requested uframe bandwidth time is increased by the new >> transfer's tt_usecs time, and carryover_tt_bandwidth is called again. >> As long as the schedule isn't pushed into the reserved time (for >> control/bulk transfers), the transfer is allowed to schedule itself in >> the specified frame/uframe with the specified period. > > Are you forgetting that isoc transfers must occur before all interrupt > transfers, and that OUT interrupt transfers must fit entirely within a > single uframe? Or is this all handled in a part of the code I haven't > come to yet? I believe that within a uframe, isoc does occur before interrupt. Is there anywhere in the spec that says the TT must be scheduled the same way, by rebalancing all interrupts to happen after isoc? I disagree that interrupt OUT transfers have to occur in a single uframe. Where does it say that in the spec? >> > Or take another example. Suppose we already have an isoc transfer of >> > length 154 and an interrupt transfer of length 32 scheduled in uframe >> > 0. Is there enough room to add a new isoc transfer of length 40? Not >> > if the interrupt transfer can't be pushed back to uframe 1 -- but >> > tt_available wouldn't realize this since none of the transfers lasts >> > more than 125 us. >> >> Sure it would. That's done in periodic_tt_usecs via the carryover >> scheduling. It doesn't rebalance the TT's schedule, it just makes >> sure that the SSPLIT will execute in the right uframe. > > But doing that requires moving the interrupt transfer's SSPLIT from > uframe 0 to uframe 1. Obviously periodic_tt_usecs doesn't do this. > In fact, this is exactly what I mean by "rebalancing the schedule". Where in the spec does it say that TTs have to be rebalanced to have interrupt after isoc? >> Can the simple carryover math be improved? Sure. In fact it is >> possible to delay transfers past the uframe where they were supposed >> to execute; for example if uframe 0 is 90% full, and uframe 1 is 90% >> full with multiple transfers; if a new transfer asked to be scheduled >> in uframe 0 with say 100usec, it would be allowed since most of it >> would carry over into uframe 1, and most of uframe 1 would carry over >> into uframe 2. The last of the multiple transfers in uframe 1 could >> very well get pushed out if there is no time in uframe 1 to start it, >> but since there is a 3-uframe "fudge" buffer mandated per USB 2.0 >> spec, this should be ok. > > The only "fudging" I'm aware of applies to CSPLITs, not SSPLITs. So it > would depend on whether these transactions were IN or OUT. Besides, if > you do push back some of the transfers from uframe 1 to uframe 2 then > you should update the siTDs accordingly. It's the transfer that may be "fudged", the CSPLITs simply have to account for that. So even for OUTs there may be a delay, even though there aren't any CSPLITs. And we are still talking about different things when we say "pushing back". I mean that the TT did not have time to execute a transfer, so it had to "push it" to the next uframe from where it was supposed to run. You are talking about rescheduling, which is completely different. >> The large isoc check is supposed to prevent >> anything from being delayed more than 1 uframe, but the current bug >> changes it so it could possibly be delayed up to 2 uframes, leaving >> only 1 left for any not-best-case delays. > > Personally, I wouldn't do that. You wouldn't do what? >> The code could be improved to correctly schedule for all cases, >> probably by re-checking each transfer in the schedule after adding the >> time for the new transfer request, or maybe by keeping track of the >> time of the last SSPLIT in each uframe so it can verify that no SSPLIT >> is pushed into the next uframe. This would also remove the special >> large isoc case. >> >> But, with the -1 bug fixed, there is a max of 1 uframe that any >> transfer can be pushed back from its SSPLIT, and that is in rare cases >> I believe. > > What about interrupt transfers? They can't be pushed around so easily. Semantic difference in "push". I don't mean reschedule or rebalance. I mean the TT itself can "push", i.e. delay, a transfer, including an interrupt transfer, for up to 3 uframes before it drops it. USB spec sec 11.18.7 fig 11-66. -- 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
