Re: [RFC PATCH] usb: dwc2: host: Rewrite the microframe scheduler

[Doug Anderson]

Hi,

On Fri, Nov 6, 2015 at 5:50 PM, Douglas Anderson  wrote:
> The old microframe scheduler was terribly hard to follow and (it seemed
> to me) that it had some bugs in it.
>
> Let's re-write it in a simpler, easier-to-read way.  Hopefully this will
> work better.
>
> Note: no known problems are fixed by this patch, and in fact I can see
> very little impact of the microframe scheduler overall.
>
> Signed-off-by: Douglas Anderson 
> ---
>  drivers/usb/dwc2/hcd_queue.c | 72 
> 
>  1 file changed, 32 insertions(+), 40 deletions(-)

Self-NAKing this change.

I wrote up some test code to help visualize how things were scheduled.
That proved that the old function is pretty broken, but the new
function not only has a typo (using "i" instead of "j" in a few
places) but also suffers from some of the same problems as the old
function.

It might be easy to use the bitmap functions to implement this easily
/ properly.  I'll see if I can do that.

-Doug
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC PATCH] usb: dwc2: host: Rewrite the microframe scheduler

[Doug Anderson]

Hi,

On Fri, Nov 6, 2015 at 5:50 PM, Douglas Anderson  wrote:
> The old microframe scheduler was terribly hard to follow and (it seemed
> to me) that it had some bugs in it.
>
> Let's re-write it in a simpler, easier-to-read way.  Hopefully this will
> work better.
>
> Note: no known problems are fixed by this patch, and in fact I can see
> very little impact of the microframe scheduler overall.
>
> Signed-off-by: Douglas Anderson 
> ---
>  drivers/usb/dwc2/hcd_queue.c | 72 
> 
>  1 file changed, 32 insertions(+), 40 deletions(-)

Self-NAKing this change.

I wrote up some test code to help visualize how things were scheduled.
That proved that the old function is pretty broken, but the new
function not only has a typo (using "i" instead of "j" in a few
places) but also suffers from some of the same problems as the old
function.

It might be easy to use the bitmap functions to implement this easily
/ properly.  I'll see if I can do that.

-Doug
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[RFC PATCH] usb: dwc2: host: Rewrite the microframe scheduler

[Douglas Anderson]

The old microframe scheduler was terribly hard to follow and (it seemed
to me) that it had some bugs in it.

Let's re-write it in a simpler, easier-to-read way.  Hopefully this will
work better.

Note: no known problems are fixed by this patch, and in fact I can see
very little impact of the microframe scheduler overall.

Signed-off-by: Douglas Anderson 
---
 drivers/usb/dwc2/hcd_queue.c | 72 
 1 file changed, 32 insertions(+), 40 deletions(-)

diff --git a/drivers/usb/dwc2/hcd_queue.c b/drivers/usb/dwc2/hcd_queue.c
index 7d8d06cfe3c1..d6c24decee08 100644
--- a/drivers/usb/dwc2/hcd_queue.c
+++ b/drivers/usb/dwc2/hcd_queue.c
@@ -359,57 +359,49 @@ static int dwc2_find_single_uframe(struct dwc2_hsotg 
*hsotg, struct dwc2_qh *qh)
  */
 static int dwc2_find_multi_uframe(struct dwc2_hsotg *hsotg, struct dwc2_qh *qh)
 {
-   unsigned short utime = qh->usecs;
-   unsigned short xtime;
-   int t_left;
+   int utime;
int i;
int j;
-   int k;
 
for (i = 0; i < 8; i++) {
if (hsotg->frame_usecs[i] <= 0)
continue;
 
-   /*
-* we need n consecutive slots so use j as a start slot
-* j plus j+1 must be enough time (for now)
-*/
-   xtime = hsotg->frame_usecs[i];
-   for (j = i + 1; j < 8; j++) {
+   for (utime = qh->usecs, j = i; utime > 0 && j < 8; j++) {
+   /* Give the available time from this uframe */
+   utime -= hsotg->frame_usecs[j];
+
/*
-* if we add this frame remaining time to xtime we may
-* be OK, if not we need to test j for a complete frame
+* Except for first frame, we can't continue past this
+* frame if it wasn't full, so bail now.  We might still
+* be successful the above subtract made utime <= 0.
 */
-   if (xtime + hsotg->frame_usecs[j] < utime) {
-   if (hsotg->frame_usecs[j] <
-   max_uframe_usecs[j])
-   continue;
-   }
-   if (xtime >= utime) {
-   t_left = utime;
-   for (k = i; k < 8; k++) {
-   t_left -= hsotg->frame_usecs[k];
-   if (t_left <= 0) {
-   qh->frame_usecs[k] +=
-   hsotg->frame_usecs[k]
-   + t_left;
-   hsotg->frame_usecs[k] = -t_left;
-   return i;
-   } else {
-   qh->frame_usecs[k] +=
-   hsotg->frame_usecs[k];
-   hsotg->frame_usecs[k] = 0;
-   }
-   }
-   }
-   /* add the frame time to x time */
-   xtime += hsotg->frame_usecs[j];
-   /* we must have a fully available next frame or break */
-   if (xtime < utime &&
-  hsotg->frame_usecs[j] == max_uframe_usecs[j])
-   continue;
+   if ((i != j) &&
+   (hsotg->frame_usecs[j] < max_uframe_usecs[j]))
+   break;
+   }
+
+   /* If utime > 0 after above loop, try a different start (i) */
+   if (utime > 0)
+   continue;
+
+   dev_dbg(hsotg->dev, "Assigned %d us starting at i=%d + %d us\n",
+   qh->usecs, i,
+   max_uframe_usecs[i] - hsotg->frame_usecs[i]);
+
+   /* We've got success, so allocate */
+   for (utime = qh->usecs, j = i; utime > 0 && j < 8; j++) {
+   qh->frame_usecs[i] = min_t(u16, utime,
+  hsotg->frame_usecs[j]);
+   utime -= qh->frame_usecs[i];
+   hsotg->frame_usecs[j] -= qh->frame_usecs[i];
}
+
+   return i;
}
+
+   dev_dbg(hsotg->dev, "Failed to assign %d us\n", qh->usecs);
+
return -ENOSPC;
 }
 
-- 
2.6.0.rc2.230.g3dd15c0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  

[RFC PATCH] usb: dwc2: host: Rewrite the microframe scheduler

[Douglas Anderson]

The old microframe scheduler was terribly hard to follow and (it seemed
to me) that it had some bugs in it.

Let's re-write it in a simpler, easier-to-read way.  Hopefully this will
work better.

Note: no known problems are fixed by this patch, and in fact I can see
very little impact of the microframe scheduler overall.

Signed-off-by: Douglas Anderson 
---
 drivers/usb/dwc2/hcd_queue.c | 72 
 1 file changed, 32 insertions(+), 40 deletions(-)

diff --git a/drivers/usb/dwc2/hcd_queue.c b/drivers/usb/dwc2/hcd_queue.c
index 7d8d06cfe3c1..d6c24decee08 100644
--- a/drivers/usb/dwc2/hcd_queue.c
+++ b/drivers/usb/dwc2/hcd_queue.c
@@ -359,57 +359,49 @@ static int dwc2_find_single_uframe(struct dwc2_hsotg 
*hsotg, struct dwc2_qh *qh)
  */
 static int dwc2_find_multi_uframe(struct dwc2_hsotg *hsotg, struct dwc2_qh *qh)
 {
-   unsigned short utime = qh->usecs;
-   unsigned short xtime;
-   int t_left;
+   int utime;
int i;
int j;
-   int k;
 
for (i = 0; i < 8; i++) {
if (hsotg->frame_usecs[i] <= 0)
continue;
 
-   /*
-* we need n consecutive slots so use j as a start slot
-* j plus j+1 must be enough time (for now)
-*/
-   xtime = hsotg->frame_usecs[i];
-   for (j = i + 1; j < 8; j++) {
+   for (utime = qh->usecs, j = i; utime > 0 && j < 8; j++) {
+   /* Give the available time from this uframe */
+   utime -= hsotg->frame_usecs[j];
+
/*
-* if we add this frame remaining time to xtime we may
-* be OK, if not we need to test j for a complete frame
+* Except for first frame, we can't continue past this
+* frame if it wasn't full, so bail now.  We might still
+* be successful the above subtract made utime <= 0.
 */
-   if (xtime + hsotg->frame_usecs[j] < utime) {
-   if (hsotg->frame_usecs[j] <
-   max_uframe_usecs[j])
-   continue;
-   }
-   if (xtime >= utime) {
-   t_left = utime;
-   for (k = i; k < 8; k++) {
-   t_left -= hsotg->frame_usecs[k];
-   if (t_left <= 0) {
-   qh->frame_usecs[k] +=
-   hsotg->frame_usecs[k]
-   + t_left;
-   hsotg->frame_usecs[k] = -t_left;
-   return i;
-   } else {
-   qh->frame_usecs[k] +=
-   hsotg->frame_usecs[k];
-   hsotg->frame_usecs[k] = 0;
-   }
-   }
-   }
-   /* add the frame time to x time */
-   xtime += hsotg->frame_usecs[j];
-   /* we must have a fully available next frame or break */
-   if (xtime < utime &&
-  hsotg->frame_usecs[j] == max_uframe_usecs[j])
-   continue;
+   if ((i != j) &&
+   (hsotg->frame_usecs[j] < max_uframe_usecs[j]))
+   break;
+   }
+
+   /* If utime > 0 after above loop, try a different start (i) */
+   if (utime > 0)
+   continue;
+
+   dev_dbg(hsotg->dev, "Assigned %d us starting at i=%d + %d us\n",
+   qh->usecs, i,
+   max_uframe_usecs[i] - hsotg->frame_usecs[i]);
+
+   /* We've got success, so allocate */
+   for (utime = qh->usecs, j = i; utime > 0 && j < 8; j++) {
+   qh->frame_usecs[i] = min_t(u16, utime,
+  hsotg->frame_usecs[j]);
+   utime -= qh->frame_usecs[i];
+   hsotg->frame_usecs[j] -= qh->frame_usecs[i];
}
+
+   return i;
}
+
+   dev_dbg(hsotg->dev, "Failed to assign %d us\n", qh->usecs);
+
return -ENOSPC;
 }
 
-- 
2.6.0.rc2.230.g3dd15c0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at