On Sun, Apr 03, 2022 at 08:22:44PM +0300, Sergei Shtylyov wrote:
> On 4/3/22 6:17 PM, Alan Stern wrote:
>
> >> The following function in the EHCI scheduling code causes the SVACE static analyzer to
> >> report possible buffer overflow (see the last assignment below), e.g.:
> >>
> >> Buffer 'ehci->bandwidth' of size 64 accessed at ehci-sched.c:240 can overflow, since its
> >> index 'i + j' can have value 66 that is out of range, as indicated by preceding conditional
> >> expression at ehci-sched.c:240.
> >
> > Not sure what you mean.
>
> What SVACE means, in this case. :-)
>
> > In my copy of the file, line 240 is the assignment.
>
> For SVACE as well. This is not a full report -- some details did follow but I failed
> to copy/paste them...
>
> > There is a conditional in line 239 and in line 238 (the "for" condition),
> > but I don't see how either one indicates that i+j could be as large as 66.
>
> SVACE doesn't know what qh->ps.bw_uperiod could be...
>
> >> I tried hard to analyze this code but couldn't quite figure out whether an overflow could
> >> actually happen... Maybe Alan (or Greg?) could please help me out?
> >
> > All right. Hold on to your hat...
> >
>
> :-)
>
> >> static void reserve_release_intr_bandwidth(struct ehci_hcd *ehci,
> >> struct ehci_qh *qh, int sign)
> >> {
> >> unsigned start_uf;
> >> unsigned i, j, m;
> >> int usecs = qh->ps.usecs;
> >> int c_usecs = qh->ps.c_usecs;
> >> int tt_usecs = qh->ps.tt_usecs;
> >> struct ehci_tt *tt;
> >>
> >> if (qh->ps.phase == NO_FRAME) /* Bandwidth wasn't reserved */
> >> return;
> >> start_uf = qh->ps.bw_phase << 3;
> >
> > This guarantees that start_uf is a multiple of 8.
>
> I figured. :-)
>
> >> bandwidth_dbg(ehci, sign, "intr", &qh->ps);
> >>
> >> if (sign < 0) { /* Release bandwidth */
> >> usecs = -usecs;
> >> c_usecs = -c_usecs;
> >> tt_usecs = -tt_usecs;
> >> }
> >>
> >> /* Entire transaction (high speed) or start-split (full/low speed) */
> >> for (i = start_uf + qh->ps.phase_uf; i < EHCI_BANDWIDTH_SIZE;
> >> i += qh->ps.bw_uperiod)
> >> ehci->bandwidth[i] += usecs;
> >>
> >> /* Complete-split (full/low speed) */
> >> if (qh->ps.c_usecs) {
> >
> > The fact that c_usecs is nonzero guarantees that we are dealing with a
> > full/low-speed endpoint.
>
> Ah! That's what I missed...
>
> > High-speed transfers don't use split
> > transactions, so they don't reserve any bandwidth for complete-splits.
>
> Aha! I still lack the detailed enough knowledge of the USB 2.0 spec...
>
> >> /* NOTE: adjustments needed for FSTN */
> >> for (i = start_uf; i < EHCI_BANDWIDTH_SIZE;
> >> i += qh->ps.bw_uperiod) {
> >
> > It takes a little checking to make sure, but in fact bw_uperiod is always a
> > multiple of 8 for full/low-speed endpoints. (Such endpoints don't make use
> > of microframes; everything is in multiples of frames, i.e., multiples of 8
> > microframes.)
> >
> > Therefore i is always a multiple of 8 between 0 and 56 (inclusive), since
> > EHCI_BANDWIDTH_SIZE is 64.
>
> Aha!
>
> >> for ((j = 2, m = 1 << (j+8)); j < 8; (++j, m <<= 1)) {
> >
> > We always have 2 <= j < 8.
>
> BTW, why don't we start with 0?
That's another detail from the USB 2.0 spec. Here's how full/low-speed
split interrupt transactions work, in brief:
The host controller sends a Start Split packet in uframe n on the
HS bus.
The intervening hub carries out the interrupt transaction on the
FS/LS bus at some time in uframe n+1 or shortly thereafter. The
transaction completes at some point during uframe n+1, n+2, or n+3,
depending on how much data was transferred and how much other stuff
is happening on the FS/LS bus.
The hub doesn't make the data it received from the device available
until the uframe after the FS/LS transfer completes. So it won't
send data back to the host until uframe n+2, n+3, or n+4.
Since n >= 0, there's no point scheduling a Complete Split packet
until uframe 2 at the earliest because the data won't be ready yet.
This ignores one significant complication: If n is large enough, the hub
might want to send the interrupt data back to the host in uframe 0 or 1 of
the _next_ frame. The design of the EHCI controller makes handling these
cases unreasonably difficult -- they require special FSTN (Frame Span
Traversal Node) data structures -- and therefore ehci-hcd doesn't implement
them.
As a result, ehci-hcd is unable to schedule some loads on full- or low-speed
buses that in theory could be handled: those involving relatively high
bandwidth. This tends to show up more with full-speed isochronous rather
than interrupt transfers, however; things like video applications.
Alan Stern
> >> if (qh->ps.cs_mask & m)
> >> ehci->bandwidth[i+j] += c_usecs;
> >
> > Therefore 2 <= i+j < 56+8 = 64.
> >
> >> }
> >> }
> >> }
> >> [...]
> >>
> >> There shouldn't be a buffer overflow iff qh->ps.bw_uperiod is a
> >> multiple of 8, right?
> >
> > Correct; see above. To probe that qh->ps.bw_uperiod is always a multiple of
> > 8, search the driver for assignments to qh->ps.bw_uperiod. (The only such
> > assignments occur in ehci-q.c:qh_make() --
>
> Yes, seeing them (again)...
>
> > the assignments in ehci-sched.c
> > are all to stream->ps.bw_uperiod, and a stream is different from a qh.) The
> > first assigment is for high-speed endpoints and the second is for
> > full/low-speed endpoints. That second assignment does:
> >
> > qh->ps.bw_uperiod = qh->ps.bw_period << 3;
> >
> > which is always a multiple of 8.
>
> Yes.
>
> Thank you for the prompt reply! :-)
>
> > Alan Stern
>
> MBR, Sergey
