On Wed, Jul 13, 2011 at 01:38:26PM -0400, Alan Stern wrote:
> On Thu, 7 Jul 2011, Sarah Sharp wrote:
>
> > In order to update the root port or TT's bandwidth interval table, we will
> > need to keep track of a list of endpoints, per interval. That way we can
> > easily know the new largest max packet size when we have to remove an
> > endpoint.
>
> Okay. I haven't read through these patches in exhaustive detail, but
> at least I now understand how the bandwidth-tracking algorithm works.
> As you say, it is rather pessimistic. For example, it would fail when
> given:
>
> two endpoints of period 2, each requiring 35% of the available
> periodic bandwidth, and
>
> one endpoint of period 4, requiring 70% of the available
> bandwidth,
>
> even though this could be handled easily enough by scheduling the first
> two endpoints in the same uframe.
Yes, that's true.
> However, I'm not sure that describing this as a "worst-case" algorithm
> is really correct. If you want to be pedantic, worst-case scheduling
> means trying to cram every transaction into the same uframe!
Fair enough. :) I guess you could say it's the worst case for the
behavior we expect from this particular xHCI scheduler.
> Regardless, it seems basically okay. I didn't spend much time looking
> for mistakes in the code, but one thing caught my eye:
>
> > +static void xhci_add_ep_to_interval_table(struct xhci_hcd *xhci,
> > + struct xhci_bw_info *ep_bw,
> > + struct xhci_interval_bw_table *bw_table,
> > + struct usb_device *udev,
> > + struct xhci_virt_ep *virt_ep,
> > + struct xhci_tt_bw_info *tt_info)
> > +{
>
> ...
>
> > + /* Insert the endpoint into the list, largest max packet size first. */
> > + if (list_empty(&interval_bw->endpoints))
> > + list_add(&virt_ep->bw_endpoint_list, &interval_bw->endpoints);
> > + else {
> > + struct xhci_virt_ep *smaller_ep;
> > +
> > + list_for_each(ep_list_entry, &interval_bw->endpoints) {
> > + smaller_ep = list_entry(ep_list_entry,
> > + struct xhci_virt_ep, bw_endpoint_list);
> > + if (ep_bw->max_packet_size >=
> > + smaller_ep->bw_info.max_packet_size) {
> > + break;
> > + }
> > + }
> > + /* If we have looped through the list, ep_list_entry will point
> > + * to the head of the list, and list_add_tail will put the new
> > + * entry at the end of the list (before the head entry).
> > + * Otherwise, we'll add this endpoint in the list before the
> > + * endpoint with the smaller max packet size.
> > + */
> > + list_add_tail(&virt_ep->bw_endpoint_list,
> > + &smaller_ep->bw_endpoint_list);
> > + }
>
> Despite the lengthy comment, the logic is wrong. I'll leave it as an
> exercise for you to figure out why. Here are two hints:
>
> The comment talks about ep_list_entry, but the following line
> of code uses smaller_ep instead.
Ah, you're right. If we've wrapped around the list, smaller_ep will
point to the last endpoint in the list, and list_add_tail will add the
new endpoint in the second-to-last position. Nice catch!
> If the loop used list_for_each_entry() then the initial "if"
> statement wouldn't be needed.
Really? I always feel a bit clumsy with the list structures, so I may
be wrong, but it seems like we would potentially be dereferencing memory
we don't own.
If the list is empty, interval_bw->endpoints->next will point to the
struct list_head in struct xhci_interval_bw. But we would pass
containerof the type struct xhci_virt_ep, so we'd have a pointer to an
xhci_virt_ep that would be somewhere far away from the struct
xhci_interval_bw, since the xhci_virt_ep structure is much bigger. Then
the conditional part of the for loop in list_for_each_entry would
calculate &smaller_ep->bw_endpoint_list. Won't the kernel complain when
the bogus address is dereferenced? Or is it just pointer math, so the
bogus smaller_ep address won't actually be dereferenced?
Sarah
--
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
