Re: [PATCH] USB and Driver Core patches for 2.6.10

[Greg KH <greg@kroah.com>]

ChangeSet 1.1938.446.33, 2004/12/17 11:45:25-08:00, david-b@pacbell.net

[PATCH] USB: EHCI periodic schedule tree

This implements an interrupt schedule tree for EHCI; the bug's listed
in bugzilla (http://bugme.osdl.org/show_bug.cgi?id=3374) and affects
the ability to handle certain devices and configurations.

Now multiple interrupt transfers are supported per microframe.  Scheduling
prevents overcommit for reserved bandwidth and, for full/low speed devices,
the relevant transaction translator's buffer.  (TT-per-port hubs are already
initialized into the multi-TT mode.)

The interrupt transfer schedule is arranged in a sparse tree, just like OHCI.
A key difference is that OHCI implements a "best fit" scheduling policy,
while this implements "first fit" for EHCI.  (There's no load balancing;
it's not really needed in most users' configurations.)

There's also logic here to handle "high bandwidth" transfers, guaranteed
streaming of from 8-24 KB of data per millisecond.

Also includes some related cleanups for descheduling interrupt transfers.
Those will probably be split into a separate patch.

Against 2.6.10-rc3-bk5 ... this hasn't recently been tested much, but the
main old bug seems to be gone so it shouldn't make too much trouble.


From: David Brownell <david-b@pacbell.net>
Signed-off-by: Greg Kroah-Hartman <greg@kroah.com>


 drivers/usb/host/ehci-hcd.c   |   19 +-
 drivers/usb/host/ehci-q.c     |   12 -
 drivers/usb/host/ehci-sched.c |  354 ++++++++++++++++++++++++------------------
 3 files changed, 227 insertions(+), 158 deletions(-)


diff -Nru a/drivers/usb/host/ehci-hcd.c b/drivers/usb/host/ehci-hcd.c
--- a/drivers/usb/host/ehci-hcd.c	2005-01-07 15:46:14 -08:00
+++ b/drivers/usb/host/ehci-hcd.c	2005-01-07 15:46:14 -08:00
@@ -97,7 +97,7 @@
  * 2001-June	Works with usb-storage and NEC EHCI on 2.4
  */
 
-#define DRIVER_VERSION "26 Oct 2004"
+#define DRIVER_VERSION "10 Dec 2004"
 #define DRIVER_AUTHOR "David Brownell"
 #define DRIVER_DESC "USB 2.0 'Enhanced' Host Controller (EHCI) Driver"
 
@@ -991,12 +991,18 @@
 		qh = (struct ehci_qh *) urb->hcpriv;
 		if (!qh)
 			break;
-		if (qh->qh_state == QH_STATE_LINKED) {
-			/* messy, can spin or block a microframe ... */
-			intr_deschedule (ehci, qh, 1);
-			/* qh_state == IDLE */
+		switch (qh->qh_state) {
+		case QH_STATE_LINKED:
+			intr_deschedule (ehci, qh);
+			/* FALL THROUGH */
+		case QH_STATE_IDLE:
+			qh_completions (ehci, qh, NULL);
+			break;
+		default:
+			ehci_dbg (ehci, "bogus qh %p state %d\n",
+					qh, qh->qh_state);
+			goto done;
 		}
-		qh_completions (ehci, qh, NULL);
 
 		/* reschedule QH iff another request is queued */
 		if (!list_empty (&qh->qtd_list)
@@ -1023,6 +1029,7 @@
 		// completion irqs can wait up to 1024 msec,
 		break;
 	}
+done:
 	spin_unlock_irqrestore (&ehci->lock, flags);
 	return 0;
 }
diff -Nru a/drivers/usb/host/ehci-q.c b/drivers/usb/host/ehci-q.c
--- a/drivers/usb/host/ehci-q.c	2005-01-07 15:46:14 -08:00
+++ b/drivers/usb/host/ehci-q.c	2005-01-07 15:46:14 -08:00
@@ -268,8 +268,7 @@
 
 static void start_unlink_async (struct ehci_hcd *ehci, struct ehci_qh *qh);
 
-static void intr_deschedule (struct ehci_hcd *ehci,
-				struct ehci_qh *qh, int wait);
+static void intr_deschedule (struct ehci_hcd *ehci, struct ehci_qh *qh);
 static int qh_schedule (struct ehci_hcd *ehci, struct ehci_qh *qh);
 
 /*
@@ -428,7 +427,7 @@
 			 * except maybe high bandwidth ...
 			 */
 			if (qh->period) {
-				intr_deschedule (ehci, qh, 1);
+				intr_deschedule (ehci, qh);
 				(void) qh_schedule (ehci, qh);
 			} else
 				start_unlink_async (ehci, qh);
@@ -664,9 +663,12 @@
 			qh->c_usecs = 0;
 			qh->gap_uf = 0;
 
-			/* FIXME handle HS periods of less than 1 frame. */
 			qh->period = urb->interval >> 3;
-			if (qh->period < 1) {
+			if (qh->period == 0 && urb->interval != 1) {
+				/* NOTE interval 2 or 4 uframes could work.
+				 * But interval 1 scheduling is simpler, and
+				 * includes high bandwidth.
+				 */
 				dbg ("intr period %d uframes, NYET!",
 						urb->interval);
 				goto done;
diff -Nru a/drivers/usb/host/ehci-sched.c b/drivers/usb/host/ehci-sched.c
--- a/drivers/usb/host/ehci-sched.c	2005-01-07 15:46:14 -08:00
+++ b/drivers/usb/host/ehci-sched.c	2005-01-07 15:46:14 -08:00
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2001-2003 by David Brownell
+ * Copyright (c) 2001-2004 by David Brownell
  * Copyright (c) 2003 Michal Sojka, for high-speed iso transfers
  * 
  * This program is free software; you can redistribute it and/or modify it
@@ -59,39 +59,28 @@
 	}
 }
 
-/* returns true after successful unlink */
 /* caller must hold ehci->lock */
-static int periodic_unlink (struct ehci_hcd *ehci, unsigned frame, void *ptr)
+static void periodic_unlink (struct ehci_hcd *ehci, unsigned frame, void *ptr)
 {
 	union ehci_shadow	*prev_p = &ehci->pshadow [frame];
 	__le32			*hw_p = &ehci->periodic [frame];
 	union ehci_shadow	here = *prev_p;
-	union ehci_shadow	*next_p;
 
 	/* find predecessor of "ptr"; hw and shadow lists are in sync */
 	while (here.ptr && here.ptr != ptr) {
 		prev_p = periodic_next_shadow (prev_p, Q_NEXT_TYPE (*hw_p));
-		hw_p = &here.qh->hw_next;
+		hw_p = here.hw_next;
 		here = *prev_p;
 	}
 	/* an interrupt entry (at list end) could have been shared */
-	if (!here.ptr) {
-		dbg ("entry %p no longer on frame [%d]", ptr, frame);
-		return 0;
-	}
-	// vdbg ("periodic unlink %p from frame %d", ptr, frame);
+	if (!here.ptr)
+		return;
 
-	/* update hardware list ... HC may still know the old structure, so
-	 * don't change hw_next until it'll have purged its cache
+	/* update shadow and hardware lists ... the old "next" pointers
+	 * from ptr may still be in use, the caller updates them.
 	 */
-	next_p = periodic_next_shadow (&here, Q_NEXT_TYPE (*hw_p));
-	*hw_p = here.qh->hw_next;
-
-	/* unlink from shadow list; HCD won't see old structure again */
-	*prev_p = *next_p;
-	next_p->ptr = NULL;
-
-	return 1;
+	*prev_p = *periodic_next_shadow (&here, Q_NEXT_TYPE (*hw_p));
+	*hw_p = *here.hw_next;
 }
 
 /* how many of the uframe's 125 usecs are allocated? */
@@ -114,7 +103,8 @@
 			hw_p = &q->qh->hw_next;
 			q = &q->qh->qh_next;
 			break;
-		case Q_TYPE_FSTN:
+		// case Q_TYPE_FSTN:
+		default:
 			/* for "save place" FSTNs, count the relevant INTR
 			 * bandwidth from the previous frame
 			 */
@@ -149,13 +139,11 @@
 			hw_p = &q->sitd->hw_next;
 			q = &q->sitd->sitd_next;
 			break;
-		default:
-			BUG ();
 		}
 	}
 #ifdef	DEBUG
 	if (usecs > 100)
-		err ("overallocated uframe %d, periodic is %d usecs",
+		ehci_err (ehci, "uframe %d sched overrun: %d usecs\n",
 			frame * 8 + uframe, usecs);
 #endif
 	return usecs;
@@ -300,64 +288,143 @@
 
 /*-------------------------------------------------------------------------*/
 
-// FIXME microframe periods not yet handled
+/* periodic schedule slots have iso tds (normal or split) first, then a
+ * sparse tree for active interrupt transfers.
+ *
+ * this just links in a qh; caller guarantees uframe masks are set right.
+ * no FSTN support (yet; ehci 0.96+)
+ */
+static int qh_link_periodic (struct ehci_hcd *ehci, struct ehci_qh *qh)
+{
+	unsigned	i;
+	unsigned	period = qh->period;
 
-static void intr_deschedule (
-	struct ehci_hcd	*ehci,
-	struct ehci_qh	*qh,
-	int		wait
-) {
-	int		status;
-	unsigned	frame = qh->start;
+	dev_dbg (&qh->dev->dev,
+		"link qh%d-%04x/%p start %d [%d/%d us]\n",
+		period, le32_to_cpup (&qh->hw_info2) & 0xffff,
+		qh, qh->start, qh->usecs, qh->c_usecs);
+
+	/* high bandwidth, or otherwise every microframe */
+	if (period == 0)
+		period = 1;
+
+	for (i = qh->start; i < ehci->periodic_size; i += period) {
+		union ehci_shadow	*prev = &ehci->pshadow [i];
+		u32			*hw_p = &ehci->periodic [i];
+		union ehci_shadow	here = *prev;
+		u32			type = 0;
 
-	do {
-		periodic_unlink (ehci, frame, qh);
-		qh_put (qh);
-		frame += qh->period;
-	} while (frame < ehci->periodic_size);
+		/* skip the iso nodes at list head */
+		while (here.ptr) {
+			type = Q_NEXT_TYPE (*hw_p);
+			if (type == Q_TYPE_QH)
+				break;
+			prev = periodic_next_shadow (prev, type);
+			hw_p = &here.qh->hw_next;
+			here = *prev;
+		}
+
+		/* sorting each branch by period (slow-->fast)
+		 * enables sharing interior tree nodes
+		 */
+		while (here.ptr && qh != here.qh) {
+			if (qh->period > here.qh->period)
+				break;
+			prev = &here.qh->qh_next;
+			hw_p = &here.qh->hw_next;
+			here = *prev;
+		}
+		/* link in this qh, unless some earlier pass did that */
+		if (qh != here.qh) {
+			qh->qh_next = here;
+			if (here.qh)
+				qh->hw_next = *hw_p;
+			wmb ();
+			prev->qh = qh;
+			*hw_p = QH_NEXT (qh->qh_dma);
+		}
+	}
+	qh->qh_state = QH_STATE_LINKED;
+	qh_get (qh);
+
+	/* update per-qh bandwidth for usbfs */
+	hcd_to_bus (&ehci->hcd)->bandwidth_allocated += qh->period
+		? ((qh->usecs + qh->c_usecs) / qh->period)
+		: (qh->usecs * 8);
 
+	/* maybe enable periodic schedule processing */
+	if (!ehci->periodic_sched++)
+		return enable_periodic (ehci);
+
+	return 0;
+}
+
+static void qh_unlink_periodic (struct ehci_hcd *ehci, struct ehci_qh *qh)
+{
+	unsigned	i;
+	unsigned	period;
+
+	// FIXME:
+	// IF this isn't high speed
+	//   and this qh is active in the current uframe
+	//   (and overlay token SplitXstate is false?)
+	// THEN
+	//   qh->hw_info1 |= __constant_cpu_to_le32 (1 << 7 /* "ignore" */);
+
+	/* high bandwidth, or otherwise part of every microframe */
+	if ((period = qh->period) == 0)
+		period = 1;
+
+	for (i = qh->start; i < ehci->periodic_size; i += period)
+		periodic_unlink (ehci, i, qh);
+
+	/* update per-qh bandwidth for usbfs */
+	hcd_to_bus (&ehci->hcd)->bandwidth_allocated -= qh->period
+		? ((qh->usecs + qh->c_usecs) / qh->period)
+		: (qh->usecs * 8);
+
+	dev_dbg (&qh->dev->dev,
+		"unlink qh%d-%04x/%p start %d [%d/%d us]\n",
+		qh->period, le32_to_cpup (&qh->hw_info2) & 0xffff,
+		qh, qh->start, qh->usecs, qh->c_usecs);
+
+	/* qh->qh_next still "live" to HC */
 	qh->qh_state = QH_STATE_UNLINK;
 	qh->qh_next.ptr = NULL;
-	ehci->periodic_sched--;
+	qh_put (qh);
 
 	/* maybe turn off periodic schedule */
+	ehci->periodic_sched--;
 	if (!ehci->periodic_sched)
-		status = disable_periodic (ehci);
-	else {
-		status = 0;
-		ehci_vdbg (ehci, "periodic schedule still enabled\n");
-	}
+		(void) disable_periodic (ehci);
+}
 
-	/*
-	 * If the hc may be looking at this qh, then delay a uframe
-	 * (yeech!) to be sure it's done.
-	 * No other threads may be mucking with this qh.
+static void intr_deschedule (struct ehci_hcd *ehci, struct ehci_qh *qh)
+{
+	unsigned	wait;
+
+	qh_unlink_periodic (ehci, qh);
+
+	/* simple/paranoid:  always delay, expecting the HC needs to read
+	 * qh->hw_next or finish a writeback after SPLIT/CSPLIT ... and
+	 * expect khubd to clean up after any CSPLITs we won't issue.
+	 * active high speed queues may need bigger delays...
 	 */
-	if (((ehci_get_frame (&ehci->hcd) - frame) % qh->period) == 0) {
-		if (wait) {
-			udelay (125);
-			qh->hw_next = EHCI_LIST_END;
-		} else {
-			/* we may not be IDLE yet, but if the qh is empty
-			 * the race is very short.  then if qh also isn't
-			 * rescheduled soon, it won't matter.  otherwise...
-			 */
-			ehci_vdbg (ehci, "intr_deschedule...\n");
-		}
-	} else
-		qh->hw_next = EHCI_LIST_END;
+	if (list_empty (&qh->qtd_list)
+			|| (__constant_cpu_to_le32 (0x0ff << 8)
+					& qh->hw_info2) != 0)
+		wait = 2;
+	else
+		wait = 55;	/* worst case: 3 * 1024 */
 
+	udelay (wait);
 	qh->qh_state = QH_STATE_IDLE;
-
-	/* update per-qh bandwidth utilization (for usbfs) */
-	hcd_to_bus (&ehci->hcd)->bandwidth_allocated -= 
-		(qh->usecs + qh->c_usecs) / qh->period;
-
-	ehci_dbg (ehci, "descheduled qh%d/%p frame=%d count=%d, urbs=%d\n",
-		qh->period, qh, frame,
-		atomic_read (&qh->kref.refcount), ehci->periodic_sched);
+	qh->hw_next = EHCI_LIST_END;
+	wmb ();
 }
 
+/*-------------------------------------------------------------------------*/
+
 static int check_period (
 	struct ehci_hcd *ehci, 
 	unsigned	frame,
@@ -365,6 +432,8 @@
 	unsigned	period,
 	unsigned	usecs
 ) {
+	int		claimed;
+
 	/* complete split running into next frame?
 	 * given FSTN support, we could sometimes check...
 	 */
@@ -377,22 +446,26 @@
 	 */
 	usecs = 100 - usecs;
 
-	do {
-		int	claimed;
-
-// FIXME delete when intr_submit handles non-empty queues
-// this gives us a one intr/frame limit (vs N/uframe)
-// ... and also lets us avoid tracking split transactions
-// that might collide at a given TT/hub.
-		if (ehci->pshadow [frame].ptr)
-			return 0;
-
-		claimed = periodic_usecs (ehci, frame, uframe);
-		if (claimed > usecs)
-			return 0;
+	/* we "know" 2 and 4 uframe intervals were rejected; so
+	 * for period 0, check _every_ microframe in the schedule.
+	 */
+	if (unlikely (period == 0)) {
+		do {
+			for (uframe = 0; uframe < 7; uframe++) {
+				claimed = periodic_usecs (ehci, frame, uframe);
+				if (claimed > usecs)
+					return 0;
+			}
+		} while ((frame += 1) < ehci->periodic_size);
 
-// FIXME update to handle sub-frame periods
-	} while ((frame += period) < ehci->periodic_size);
+	/* just check the specified uframe, at that period */
+	} else {
+		do {
+			claimed = periodic_usecs (ehci, frame, uframe);
+			if (claimed > usecs)
+				return 0;
+		} while ((frame += period) < ehci->periodic_size);
+	}
 
 	// success!
 	return 1;
@@ -407,6 +480,10 @@
 )
 {
     	int		retval = -ENOSPC;
+	u8		mask;
+
+	if (qh->c_usecs && uframe >= 6)		/* FSTN territory? */
+		goto done;
 
 	if (!check_period (ehci, frame, uframe, qh->period, qh->usecs))
 		goto done;
@@ -416,33 +493,33 @@
 		goto done;
 	}
 
-	/* This is a split transaction; check the bandwidth available for
-	 * the completion too.  Check both worst and best case gaps: worst
-	 * case is SPLIT near uframe end, and CSPLIT near start ... best is
-	 * vice versa.  Difference can be almost two uframe times, but we
-	 * reserve unnecessary bandwidth (waste it) this way.  (Actually
-	 * even better cases exist, like immediate device NAK.)
-	 *
-	 * FIXME don't even bother unless we know this TT is idle in that
-	 * range of uframes ... for now, check_period() allows only one
-	 * interrupt transfer per frame, so needn't check "TT busy" status
-	 * when scheduling a split (QH, SITD, or FSTN).
-	 *
-	 * FIXME ehci 0.96 and above can use FSTNs
+	/* Make sure this tt's buffer is also available for CSPLITs.
+	 * We pessimize a bit; probably the typical full speed case
+	 * doesn't need the second CSPLIT.
+	 * 
+	 * NOTE:  both SPLIT and CSPLIT could be checked in just
+	 * one smart pass...
 	 */
-	if (!check_period (ehci, frame, uframe + qh->gap_uf + 1,
-				qh->period, qh->c_usecs))
-		goto done;
-	if (!check_period (ehci, frame, uframe + qh->gap_uf,
-				qh->period, qh->c_usecs))
-		goto done;
+	mask = 0x03 << (uframe + qh->gap_uf);
+	*c_maskp = cpu_to_le32 (mask << 8);
 
-	*c_maskp = cpu_to_le32 (0x03 << (8 + uframe + qh->gap_uf));
-	retval = 0;
+	mask |= 1 << uframe;
+	if (tt_no_collision (ehci, qh->period, qh->dev, frame, mask)) {
+		if (!check_period (ehci, frame, uframe + qh->gap_uf + 1,
+					qh->period, qh->c_usecs))
+			goto done;
+		if (!check_period (ehci, frame, uframe + qh->gap_uf,
+					qh->period, qh->c_usecs))
+			goto done;
+		retval = 0;
+	}
 done:
 	return retval;
 }
 
+/* "first fit" scheduling policy used the first time through,
+ * or when the previous schedule slot can't be re-used.
+ */
 static int qh_schedule (struct ehci_hcd *ehci, struct ehci_qh *qh)
 {
 	int 		status;
@@ -469,56 +546,39 @@
 	 * uframes have enough periodic bandwidth available.
 	 */
 	if (status) {
-		frame = qh->period - 1;
-		do {
-			for (uframe = 0; uframe < 8; uframe++) {
-				status = check_intr_schedule (ehci,
-						frame, uframe, qh,
-						&c_mask);
-				if (status == 0)
-					break;
-			}
-		} while (status && frame--);
+		/* "normal" case, uframing flexible except with splits */
+		if (qh->period) {
+			frame = qh->period - 1;
+			do {
+				for (uframe = 0; uframe < 8; uframe++) {
+					status = check_intr_schedule (ehci,
+							frame, uframe, qh,
+							&c_mask);
+					if (status == 0)
+						break;
+				}
+			} while (status && frame--);
+
+		/* qh->period == 0 means every uframe */
+		} else {
+			frame = 0;
+			status = check_intr_schedule (ehci, 0, 0, qh, &c_mask);
+		}
 		if (status)
 			goto done;
 		qh->start = frame;
 
 		/* reset S-frame and (maybe) C-frame masks */
-		qh->hw_info2 &= ~__constant_cpu_to_le32(0xffff);
-		qh->hw_info2 |= cpu_to_le32 (1 << uframe) | c_mask;
+		qh->hw_info2 &= __constant_cpu_to_le32 (~0xffff);
+		qh->hw_info2 |= qh->period
+			? cpu_to_le32 (1 << uframe)
+			: __constant_cpu_to_le32 (0xff);
+		qh->hw_info2 |= c_mask;
 	} else
 		ehci_dbg (ehci, "reused qh %p schedule\n", qh);
 
 	/* stuff into the periodic schedule */
-	qh->qh_state = QH_STATE_LINKED;
-	ehci_dbg(ehci,
-		"scheduled qh%d/%p usecs %d/%d starting %d.%d (gap %d)\n",
-		qh->period, qh, qh->usecs, qh->c_usecs,
-		frame, uframe, qh->gap_uf);
-	do {
-		if (unlikely (ehci->pshadow [frame].ptr != 0)) {
-
-// FIXME -- just link toward the end, before any qh with a shorter period,
-// AND accommodate it already having been linked here (after some other qh)
-// AS WELL AS updating the schedule checking logic
-
-			BUG ();
-		} else {
-			ehci->pshadow [frame].qh = qh_get (qh);
-			ehci->periodic [frame] =
-				QH_NEXT (qh->qh_dma);
-		}
-		wmb ();
-		frame += qh->period;
-	} while (frame < ehci->periodic_size);
-
-	/* update per-qh bandwidth for usbfs */
-	hcd_to_bus (&ehci->hcd)->bandwidth_allocated += 
-		(qh->usecs + qh->c_usecs) / qh->period;
-
-	/* maybe enable periodic schedule processing */
-	if (!ehci->periodic_sched++)
-		status = enable_periodic (ehci);
+ 	status = qh_link_periodic (ehci, qh);
 done:
 	return status;
 }
@@ -780,7 +840,7 @@
 
 /*-------------------------------------------------------------------------*/
 
-/* ehci_iso_sched ops can be shared, ITD-only, or SITD-only */
+/* ehci_iso_sched ops can be ITD-only or SITD-only */
 
 static struct ehci_iso_sched *
 iso_sched_alloc (unsigned packets, int mem_flags)
@@ -1843,7 +1903,7 @@
 				q = q.qh->qh_next;
 				modified = qh_completions (ehci, temp.qh, regs);
 				if (unlikely (list_empty (&temp.qh->qtd_list)))
-					intr_deschedule (ehci, temp.qh, 0);
+					intr_deschedule (ehci, temp.qh);
 				qh_put (temp.qh);
 				break;
 			case Q_TYPE_FSTN: