* Buffer overflow in drivers/usb/host/ehci-sched.c?
@ 2022-04-02 21:12 Sergei Shtylyov
2022-04-03 15:17 ` Alan Stern
0 siblings, 1 reply; 4+ messages in thread
From: Sergei Shtylyov @ 2022-04-02 21:12 UTC (permalink / raw)
To: Alan Stern; +Cc: Greg Kroah-Hartman, linux-usb
Hello!
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.
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?
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;
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) {
/* NOTE: adjustments needed for FSTN */
for (i = start_uf; i < EHCI_BANDWIDTH_SIZE;
i += qh->ps.bw_uperiod) {
for ((j = 2, m = 1 << (j+8)); j < 8; (++j, m <<= 1)) {
if (qh->ps.cs_mask & m)
ehci->bandwidth[i+j] += c_usecs;
}
}
}
[...]
There shouldn't be a buffer overflow iff qh->ps.bw_uperiod is a multiple of 8, right?
MBR, Sergey
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Buffer overflow in drivers/usb/host/ehci-sched.c?
2022-04-02 21:12 Buffer overflow in drivers/usb/host/ehci-sched.c? Sergei Shtylyov
@ 2022-04-03 15:17 ` Alan Stern
2022-04-03 17:22 ` Sergei Shtylyov
0 siblings, 1 reply; 4+ messages in thread
From: Alan Stern @ 2022-04-03 15:17 UTC (permalink / raw)
To: Sergei Shtylyov; +Cc: Greg Kroah-Hartman, linux-usb
On Sun, Apr 03, 2022 at 12:12:48AM +0300, Sergei Shtylyov wrote:
> Hello!
>
> 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. In my copy of the file, line 240 is the assignment.
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.
> 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.
> 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. High-speed transfers don't use split
transactions, so they don't reserve any bandwidth for complete-splits.
> /* 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.
> for ((j = 2, m = 1 << (j+8)); j < 8; (++j, m <<= 1)) {
We always have 2 <= j < 8.
> 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() -- 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.
Alan Stern
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Buffer overflow in drivers/usb/host/ehci-sched.c?
2022-04-03 15:17 ` Alan Stern
@ 2022-04-03 17:22 ` Sergei Shtylyov
2022-04-03 17:57 ` Alan Stern
0 siblings, 1 reply; 4+ messages in thread
From: Sergei Shtylyov @ 2022-04-03 17:22 UTC (permalink / raw)
To: Alan Stern; +Cc: Greg Kroah-Hartman, linux-usb
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?
>
>> 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Buffer overflow in drivers/usb/host/ehci-sched.c?
2022-04-03 17:22 ` Sergei Shtylyov
@ 2022-04-03 17:57 ` Alan Stern
0 siblings, 0 replies; 4+ messages in thread
From: Alan Stern @ 2022-04-03 17:57 UTC (permalink / raw)
To: Sergei Shtylyov; +Cc: Greg Kroah-Hartman, linux-usb
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2022-04-03 17:57 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-04-02 21:12 Buffer overflow in drivers/usb/host/ehci-sched.c? Sergei Shtylyov
2022-04-03 15:17 ` Alan Stern
2022-04-03 17:22 ` Sergei Shtylyov
2022-04-03 17:57 ` Alan Stern
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.