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. > 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. > 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? > After the uframe where a > SSPLIT is scheduled, there are only 3 uframes where the TT will buffer > the transfer until it's dropped; there are no CSPLITs scheduled after > that anyway so there is no point in the TT keeping it. > > The tt_available function should (with the -1 removed) only schedule a > multi-uframe isoc transfer starting in an empty uframe, Why? What's wrong with scheduling a multi-uframe isoc transfer to begin in a partially-occupied uframe? For example, suppose we have two transfers: A is for 150 bytes and B is for 50 bytes. What's wrong with scheduling both A and B to start in uframe 0? Sure, B will spill over into uframe 1; as long as the scheduler is aware of this it won't be a problem. Now suppose B is 200 bytes. Together A and B will still fit into uframes 0 and 1. Why should this case be any different from the other? > with each > following fully used uframe also empty. The last uframe, that is not > fully used (assuming the transfer isn't an exact multiple of 125us), > is handled normally by the scheduling calculations in > periodic_tt_usecs, as are all transfers less than 125usec (1 uframe). > > Note that as TT scheduling only has to be done for periodic transfers, > not control/bulk transfers, we are only talking about isoc or > interrupt here. The max packet size restrictions of low/full-speed > interrupt limit it to less than 1 uframe so a multi-uframe interrupt > transfer is impossible (with "multi-uframe" meaning it takes more than > 125usecs). > > To break down tt_available and its helper functions: > > For each frame where the transfer is executed (start at the specified > frame and also check each frame + period*N), it does: > > Call periodic_tt_usecs. This fills the tt_usecs array with the > current bandwidth usage of each uframe. It checks the current > schedule, adding up each transfer scheduled on the same TT for that > frame. It's a simple calculation, just adding the transfer's tt_usecs > time to the uframe where it is scheduled to run. At the end, > carryover_tt_bandwidth is called, which "carries over" any excess > bandwidth for any uframe. So if uframe 1 has 200usec of transfers > scheduled to start in that uframe, 75usec of that is "carried over" > into uframe 2, and so on. So, the maximum amount of time scheduled > for any single uframe is as defined by max_tt_usecs (i.e., 125usec for > the most uframes, except 6 and 7 as those must be reserved for > control/bulk). > > Once the array is filled with the current schedule times, the uframe > where the new transfer is asking to be scheduled is checked. If it is > already 100% scheduled, simply return failure. > > 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. > 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? > > 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". > 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. > 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. > 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. 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
