Buffer overflow in drivers/usb/host/ehci-sched.c?

Buffer overflow in drivers/usb/host/ehci-sched.c?

[Sergei Shtylyov]

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

Re: Buffer overflow in drivers/usb/host/ehci-sched.c?

[Alan Stern]

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

Re: Buffer overflow in drivers/usb/host/ehci-sched.c?

[Sergei Shtylyov]

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

Re: Buffer overflow in drivers/usb/host/ehci-sched.c?

[Alan Stern]

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