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.
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!
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.
If the loop used list_for_each_entry() then the initial "if"
statement wouldn't be needed.
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
