These patches are against kernels 2.6.18 through at least 2.6.18-git7.
patch 10: Drops in complete implementation of the shadow budget
abstraction, but does not yet call this code in any way. The shadow
budget is a means of indefinitely reserving bandwidth requested by a
periodic endpoint as well as logic for making scheduling decisions
based on previously budgeted allocations.
Signed-off-by: Christopher "Monty" Montgomery <[EMAIL PROTECTED]>
---
diff -X b/Documentation/dontdiff -upr a/drivers/usb/host/ehci.h
b/drivers/usb/host/ehci.h
--- a/drivers/usb/host/ehci.h 2006-09-26 22:29:36.000000000 -0400
+++ b/drivers/usb/host/ehci.h 2006-09-26 22:29:47.000000000 -0400
@@ -72,6 +72,10 @@ struct ehci_hcd { /* one per controlle
int next_uframe; /* scan periodic, start here */
unsigned periodic_sched; /* periodic activity count */
+ kmem_cache_t *budget_pool; /* Pool for shadow budget */
+ struct ehci_shadow_budget **budget; /* pointer to the
shadow budget
+ of bandwidth placeholders */
+
/* per root hub port */
unsigned long reset_done [EHCI_MAX_ROOT_PORTS];
@@ -155,8 +159,8 @@ timer_action (struct ehci_hcd *ehci, enu
// to go OFF neither can matter, and afterwards the IO
// watchdog stops unless there's still periodic traffic.
if (action != TIMER_IAA_WATCHDOG
- && t > ehci->watchdog.expires
- && timer_pending (&ehci->watchdog))
+ && t > ehci->watchdog.expires
+ && timer_pending (&ehci->watchdog))
return;
mod_timer (&ehci->watchdog, t);
}
@@ -377,6 +381,56 @@ union ehci_shadow {
/*-------------------------------------------------------------------------*/
+/* the shadow budget is a means of reserving bandwidth throughout the
+ periodic schedule (the hardware schedule is currently used as a
+ sliding window by the current transaction code). The shadow budget
+ follows the same list-then-tree structure as the hardware schedule. */
+
+/* must be equal to or smaller than PERIODIC_QH_MAX_PERIOD */
+#define BUDGET_SLOTS 32
+#define BUDGET_SLOT_MASK (BUDGET_SLOTS-1)
+
+/* Because EHCI cannot issue ssplits in uframe 7 and USB 2.0 does not
+ allow ssplits in uframe 6, EHCI can only generate an efficient FS
+ frame by scheduling according to best-case (not worst-case) bit
+ stuffing. Thus we purposely 'overcommit' the FS frame budget
+ within the buffering ability of the TT to buffer, and within the
+ limits of the 90/10 rule. The TT will catch up in the microframes
+ where we cannot issue start splits.
+*/
+
+#define BUDGET_WRAP_P(b) ((b)->cmask & (~0xff))
+
+struct ehci_shadow_budget {
+ struct ehci_shadow_budget *next;
+
+ u16 s_usecs; /* highspeed usecs */
+ u16 c_usecs; /* highspeed completion usecs (FS/LS)*/
+ u16 tt_bytes; /* bytes to budget at TT (FS/LS)*/
+ u16 cmask; /* 16 bits: a 'too big' mask indicates the need for a
+ frame wrap (FSTN or dummy SITD) */
+ u8 smask;
+
+#define BUDGET_TYPE_ITD 1 /* ITD or SITD; budgets early */
+#define BUDGET_TYPE_QH 2 /* QH; budgets late */
+ u8 type;
+
+ /* QHs and FSTNs are persistent in the periodic schedule, so they
+ own their own budget placeholders. [s]ITD placeholders are owned
+ by an ehci_iso_stream. */
+ union {
+ struct ehci_qh *qh; /* needed to extract
+ period and specific
+ TT */
+ struct ehci_iso_stream *iso; /* needed to extract
+ period and specific
+ TT */
+ void *ptr; /* used as an ID */
+ } owner;
+};
+
+/*-------------------------------------------------------------------------*/
+
/*
* EHCI Specification 0.95 Section 3.6
* QH: describes control/bulk/interrupt endpoints
@@ -388,7 +442,9 @@ union ehci_shadow {
/* as per ehci spec guidelines, replicate QH tree linkage of a maximum
size that is less than the full periodic schedule size. This is
also necessary to limit memory usage of FSTN support. */
-#define PERIODIC_QH_MAX_PERIOD 256 // 32 frames * 8 uFrames/Frame
+/* must be equal to or larger than BUDGET_SLOTS*8, otherwise the budget
+ will overcommit */
+#define PERIODIC_QH_MAX_PERIOD (BUDGET_SLOTS*8)
struct ehci_qh {
/* first part defined by EHCI spec */
@@ -433,10 +489,12 @@ struct ehci_qh {
u8 gap_uf; /* uframes split/csplit gap */
u8 c_usecs; /* ... split completion bw */
u16 tt_usecs; /* tt downstream bandwidth */
+ u16 tt_bytes; /* tt downstream bandwidth */
unsigned short period; /* polling interval */
unsigned short start; /* where polling starts */
#define NO_FRAME ((unsigned short)~0) /* pick new start */
struct usb_device *dev; /* access to TT */
+ struct ehci_shadow_budget *budget; /* pointer to budget
placeholder */
} __attribute__ ((aligned (32)));
/*-------------------------------------------------------------------------*/
@@ -493,6 +551,7 @@ struct ehci_iso_stream {
u16 interval;
u8 usecs, c_usecs;
u16 tt_usecs;
+ u16 tt_bytes;
u16 raw_mask;
unsigned bandwidth;
@@ -542,6 +601,7 @@ struct ehci_itd {
unsigned pg;
unsigned index[8]; /* in urb->iso_frame_desc */
u8 usecs[8];
+ struct ehci_shadow_budget *budget; /* pointer to budget
placeholder */
} __attribute__ ((aligned (32)));
/*-------------------------------------------------------------------------*/
@@ -585,6 +645,7 @@ struct ehci_sitd {
struct list_head sitd_list; /* list of stream's sitds */
unsigned frame;
unsigned index;
+ struct ehci_shadow_budget *budget; /* pointer to budget
placeholder */
} __attribute__ ((aligned (32)));
/*-------------------------------------------------------------------------*/
diff -X b/Documentation/dontdiff -upr a/drivers/usb/host/ehci-mem.c
b/drivers/usb/host/ehci-mem.c
--- a/drivers/usb/host/ehci-mem.c 2006-08-07 00:18:54.000000000 -0400
+++ b/drivers/usb/host/ehci-mem.c 2006-09-26 22:29:47.000000000 -0400
@@ -154,6 +154,13 @@ static void ehci_mem_cleanup (struct ehc
ehci->periodic, ehci->periodic_dma);
ehci->periodic = NULL;
+ if(ehci->budget)
+ kfree(ehci->budget);
+ ehci->budget = NULL;
+ if(ehci->budget_pool)
+ kmem_cache_destroy(ehci->budget_pool);
+ ehci->budget_pool = NULL;
+
/* shadow periodic table */
kfree(ehci->pshadow);
ehci->pshadow = NULL;
@@ -219,6 +226,19 @@ static int ehci_mem_init (struct ehci_hc
for (i = 0; i < ehci->periodic_size; i++)
ehci->periodic [i] = EHCI_LIST_END;
+ /* budgeting placeholders */
+ ehci->budget = kcalloc(BUDGET_SLOTS, sizeof(*ehci->budget), flags);
+ if (ehci->budget == NULL){
+ goto fail;
+ }
+ ehci->budget_pool =
+ kmem_cache_create ("ehci_budget",
+ sizeof(struct ehci_shadow_budget),
+ 0,0,NULL,NULL);
+ if (!ehci->budget_pool) {
+ goto fail;
+ }
+
/* software shadow of hardware table */
ehci->pshadow = kcalloc(ehci->periodic_size, sizeof(void *), flags);
if (ehci->pshadow != NULL)
diff -X b/Documentation/dontdiff -upr a/drivers/usb/host/ehci-sched.c
b/drivers/usb/host/ehci-sched.c
--- a/drivers/usb/host/ehci-sched.c 2006-09-26 22:29:36.000000000 -0400
+++ b/drivers/usb/host/ehci-sched.c 2006-09-26 22:29:47.000000000 -0400
@@ -1,6 +1,7 @@
/*
* Copyright (c) 2001-2004 by David Brownell
* Copyright (c) 2003 Michal Sojka, for high-speed iso transfers
+ * Copyright (c) 2006 Monty (budgeting code)
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
@@ -22,19 +23,85 @@
/*-------------------------------------------------------------------------*/
/*
- * EHCI scheduled transaction support: interrupt, iso, split iso
- * These are called "periodic" transactions in the EHCI spec.
+ * EHCI scheduled transaction support: interrupt, iso, split
+ * iso. These are called "periodic" transactions in the EHCI spec. It
+ * should be noted that the Linux USB subsystem has no high-level
+ * notion of periodically serviced transfers; bandwidth is reserved
+ * periodically [the shadow budget], but transfers are still entirely
+ * single-request/single-response. To avoid over/underruns, periodic
+ * streaming relies on upper layers to make a new request before the
+ * next schedule slot passes. Any such xruns are reported as
+ * -EL2NSYNC if they occur.
+ *
+ * The shadow budget consists of placeholders for reserving bandwidth
+ * throughout the periodic schedule for any given active endpoint.
+ * This avoids both underallocation errors (spurious ENOSPC during a
+ * transfer that began successfully) and overallocation errors (lost
+ * frames or HC/hub/irq errors and resets during transfers) due to
+ * basing bandwidth allocation on the always-incomplete hardware
+ * schedule. Although it would be conceptually simpler to place
+ * inactive [s]ITDs and QHs into the actual hardware budget (to be
+ * activated when a transfer makes use of that segment of the periodic
+ * schedule), the additional memory overhead of populating the
+ * complete 1024 frame periodic schedule is not insignificant.
+ * Therefore, a relatively small shadow budget (BUDGET_SLOTS) is
+ * projected ('translated') onto the full (1024 slot) hardware
+ * schedule. Budgeting is fully computed upon the first transfer
+ * attempt with an endpoint and remains in the shadow budget until the
+ * endpoint is closed [disabled]. Transfer descriptors are linked
+ * into the hardware schedule on demand using the precomputed
+ * information in the shadow budget.
+ *
+ * Interrupt transfers share the QH/QTD manipulation with the
+ * "asynchronous" transaction support (control/bulk transfers) in
+ * ehci-q.c, although all toplevel interrupt control originates here.
+ * The only real difference is in how interrupt transfers are
+ * scheduled.
+ *
+ * For isochronous, an "iso_stream" head serves the same role as a QH.
+ * It keeps track of every ITD (or SITD) that's scheduled.
+ *
+ *
+ * The transfer ordering in the shadow schedule looks like:
+ *
+ * . | Level N | N/2 | ... | Level 1
+ * . | | | |
+ * . | | | |
+ * Frame 2: [iso]
+ * \_ [save FSTN]; [QHs] | | |
+ * / \_ [QHs] | |
+ * Frame 1: [iso] ... _/ \_ ... _ |
+ * ... _/ \_ [restore FSTN]; [QHs]
+ * ... _/
+ * Frame 0: [iso]...
+ *
+ * Each [iso] block is ordered [dummy sITDs]; [sITDs/ITDs]
*
- * Note that for interrupt transfers, the QH/QTD manipulation is shared
- * with the "asynchronous" transaction support (control/bulk transfers).
- * The only real difference is in how interrupt transfers are scheduled.
+ * The shadow budget is structured like the shadow schedule, however
+ * it is both smaller (to save memory) and simpler, containing only
+ * QHs and normal [s]ITDs. dummy sITDs and FSTNs are intuited in
+ * budgeting calculations and do not appear explicitly in the shadow
+ * budget:
+ *
+ * . |Level N| N/2 | ... |Level 1
+ * . | | | |
+ * . append | | | |
+ * ---------> |prepend| | |
+ * Frame 2: [sITDs/ITDs] | <---- |prepend| |
+ * \_ [QHs] | <---- | |
+ * / \_ [QHs] | |prepend
+ * Frame 1: [sITDs/ITDs] ... _/ \_ ... _ | <----
+ * ... _/ \_ [QHs]
+ * ... _/
+ * Frame 0: [sITDs/ITDs]...
+ *
+ *
+ * Transaction ordering is determined by the budgeting code and set in
+ * the budget. Transactions are linked into the actual hardware
+ * schedule in the order specified by the budget.
*
- * For ISO, we make an "iso_stream" head to serve the same role as a QH.
- * It keeps track of every ITD (or SITD) that's linked, and holds enough
- * pre-calculated schedule data to make appending to the queue be quick.
*/
-static int ehci_get_frame (struct usb_hcd *hcd);
/* enable/disable shedule-specific debugging output */
static unsigned sched_verbose = 0;
@@ -44,10 +111,44 @@ MODULE_PARM_DESC (sched_verbose,
"debugging information to syslog. Incurs large latencies in"
" near-realtime code; default is 0 (off)");
+/* set limit on periodic load per TT uframe */
+static unsigned fs_bytes_per_uframe = 188;
+module_param (fs_bytes_per_uframe, uint, S_IRUGO);
+MODULE_PARM_DESC (fs_bytes_per_uframe,
+ "full-speed bytes per high-speed uframe: set the "
+ "maximum number of periodic full-speed bytes to schedule "
+ "per TT per microframe; default [spec] is 188");
+
+/* set limit on periodic load per TT frame */
+static unsigned fs_bytes_per_fullframe = 1157;
+module_param (fs_bytes_per_fullframe, uint, S_IRUGO);
+MODULE_PARM_DESC (fs_bytes_per_uframe,
+ "full-speed bytes per full-speed frame: set the "
+ "maximum number of periodic full-speed bytes to schedule "
+ "per frame; default [spec] is 1157");
+
+/* set limit on periodic load per high-speed uframe */
+static unsigned hs_usec_per_uframe = 100;
+module_param (hs_usec_per_uframe, uint, S_IRUGO);
+MODULE_PARM_DESC (hs_usec_per_uframe,
+ "high-speed usec per uframe: set the maximum "
+ "number of usec to use for periodic high-speed transfers; "
+ "default [spec] is 100");
+
+/* set limit on unique endpoints per uframe */
+static unsigned endpoints_per_uframe = 16;
+module_param (endpoints_per_uframe, uint, S_IRUGO);
+MODULE_PARM_DESC (endpoints_per_uframe,
+ "endpoints per uframe: maximum number of unique "
+ "transfers to attemps during a microframe; default "
+ "[spec] is 16");
+
/*-------------------------------------------------------------------------*/
+/* shadow schedule positioning, as this is needed throughout */
/*
* periodic_next_shadow - return "next" pointer on shadow list
+ *
* @periodic: host pointer to qh/itd/sitd
* @tag: hardware tag for type of this record
*/
@@ -67,6 +168,68 @@ periodic_next_shadow (union ehci_shadow
}
}
+/* the following are merely frame-structure dumpers to aid in
+ debugging. Be careful of their use; they will introduce extreme
+ latencies in what is [essentially] realtime code. */
+static void print_budget_frame (struct ehci_hcd *ehci, int frame,
+ struct ehci_shadow_budget *insert,
+ void *owner)
+{
+ struct ehci_shadow_budget *here =
+ ehci->budget [frame & BUDGET_SLOT_MASK];
+ printk(KERN_INFO " slot %d: ",frame & BUDGET_SLOT_MASK);
+
+ while(here){
+ if(here == insert || here->owner.ptr == owner)
+ printk(">>");
+
+ switch(here->type){
+ case BUDGET_TYPE_ITD:
+ if(here->tt_bytes)
+ printk("[SITD %p 0x%x 0x%x]",
+ here,
+ (unsigned)here->cmask,
+ (unsigned)here->smask);
+ else
+ printk("[ITD %p 0x%x 0x%x]",
+ here,
+ (unsigned)here->cmask,
+ (unsigned)here->smask);
+ break;
+ case BUDGET_TYPE_QH:
+ printk("[QH (%s) %p %d 0x%x 0x%x]",
+ (here->tt_bytes?"FS/LS":"HS"),
+ here,
+ here->owner.qh->period,
+ (unsigned)here->cmask,
+ (unsigned)here->smask);
+ break;
+ }
+
+ if(here == insert || here->owner.ptr == owner)
+ printk("<<");
+
+ if(here == here->next){
+ printk("\nERROR: schedule entry linked "
+ "to itself!\n");
+ return;
+ }
+
+ here=here->next;
+
+ }
+ printk("\n");
+}
+
+static void print_budget (struct ehci_hcd *ehci,
+ struct ehci_shadow_budget *insert,
+ void *owner)
+{
+ int i;
+ for(i=0; i<BUDGET_SLOTS; i++)
+ print_budget_frame(ehci,i,insert,owner);
+}
+
/* find position of a specific entry in the periodic schedule (ie,
* returns pointers such that we can update the predecessor's
* linkage); here->ptr == NULL indicates the find failed.
@@ -78,14 +241,15 @@ periodic_next_shadow (union ehci_shadow
*/
static union ehci_shadow *
periodic_find_entry(struct ehci_hcd *ehci,
- unsigned frame,
- void *ptr,
- __le32 **hw_p)
+ unsigned frame,
+ void *ptr,
+ __le32 **hw_p)
{
- union ehci_shadow *here = &ehci->pshadow [frame % ehci->periodic_size];
+ union ehci_shadow *here =
+ &ehci->pshadow [frame & (ehci->periodic_size-1)];
__le32 type;
- *hw_p = &ehci->periodic [frame % ehci->periodic_size];
+ *hw_p = &ehci->periodic [frame & (ehci->periodic_size-1)];
type = Q_NEXT_TYPE (**hw_p);
while (here->ptr && here->ptr != ptr) {
@@ -96,6 +260,9 @@ periodic_find_entry(struct ehci_hcd *ehc
return here;
}
+/*-------------------------------------------------------------------------*/
+/* shadow budget implementation: low-level manipulation machinery */
+
/* covert a QH's period [expressed in uFrames] to tree level.
*
* @period: period (uFrames) of a QH
@@ -109,6 +276,943 @@ static int _period_to_level(int period)
return period>>3;
}
+/* budget_position_new_itd - determine and return proper insertion position
+ * in the shadow budget for a new itd or sitd (both position into the
+ * same segment of the frame)
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame number in the shadow/hardware schedule into which new
+ * transaction is to be inserted.
+ */
+static struct ehci_shadow_budget **
+budget_position_new_itd(struct ehci_hcd *ehci, int frame)
+{
+ struct ehci_shadow_budget **here =
+ &ehci->budget [(frame & BUDGET_SLOT_MASK)];
+
+ /* skip to the end of any dummies or [s]ITDs at list head */
+ while ( (*here) &&
+ (*here)->type == BUDGET_TYPE_ITD ){
+ here = &(*here)->next;
+ }
+
+ return here;
+}
+
+/* budget_position_new_qh - determine and return proper insertion position
+ * in the shadow budget for a newly queued qh
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame number in the shadow/hardware schedule into which new
+ * transaction is to be inserted.
+ * @period: the endpoint period (in uFrames)
+ */
+static struct ehci_shadow_budget **
+budget_position_new_qh(struct ehci_hcd *ehci, int frame, int period)
+{
+ struct ehci_shadow_budget **here =
+ budget_position_new_itd(ehci, frame);
+
+ while (*here){
+
+ /* skip past higher (but not same) period QH entries */
+ /* > 8 to left of restore FSTN, <= 8 to right */
+ if ( (*here)->type == BUDGET_TYPE_QH &&
+ period >= (*here)->owner.qh->period) break;
+
+ here = &(*here)->next;
+ }
+ return here;
+}
+
+/* budget_position_new - determine and return proper insertion position
+ * in the shadow budget for a new budget entry
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame number in the shadow/hardware schedule into which new
+ * transaction is to be inserted.
+ * @new: new,populated budget entry to insert
+ */
+static struct ehci_shadow_budget **
+budget_position_new(struct ehci_hcd *ehci,
+ int frame,
+ struct ehci_shadow_budget *new)
+{
+ switch(new->type){
+ case BUDGET_TYPE_QH:
+ return budget_position_new_qh(ehci,frame,
+ new->owner.qh->period);
+
+ case BUDGET_TYPE_ITD:
+ return budget_position_new_itd(ehci,frame);
+
+ default:
+ return NULL;
+
+ }
+}
+
+/* budget_find_entry_by_owner - find position of a specific entry in
+ * the shadow budget by looking for the single entry in the frame
+ * belonging to the passed in owner. return == NULL indicates the
+ * entry was not found.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame number in the shadow budget to search; masked to
+ * prevent overflow of the shadow budget
+ * @owner: the owner of the placeholder (qh or ehci_iso_stream)
+ */
+static struct ehci_shadow_budget *
+budget_find_entry_by_owner(struct ehci_hcd *ehci,
+ unsigned frame,
+ void *owner)
+{
+ struct ehci_shadow_budget *here =
+ ehci->budget [(frame & BUDGET_SLOT_MASK)];
+
+ /* invariant: any one budget frame will contain at most a single entry
+ for a given owner; the budget does not explicitly contain spanning
+ elements, it only declares them in the transaction's cmask. Thus
+ searching by owner is unique. */
+ while (here){
+ if(here->owner.ptr == owner) break;
+ here = here->next;
+ }
+ return here;
+}
+
+static void *periodic_shadow_owner(struct ehci_hcd *ehci,
+ union ehci_shadow *ptr,
+ __le32 type){
+ switch(type){
+ case Q_TYPE_FSTN:
+ return NULL;
+ case Q_TYPE_QH:
+ return ptr;
+ case Q_TYPE_ITD:
+ return ((struct ehci_itd *)ptr)->stream;
+ case Q_TYPE_SITD:
+ return ((struct ehci_sitd *)ptr)->stream;
+ default:
+ return NULL;
+ }
+}
+
+/* periodic_translate_budget - Finds the position in the
+ * hardware/shadow schedule to insert a new hardware schedule entry
+ * based on the position in the shadow budget of the passed in budget
+ * entry. This handles positioning non-dummy sITD, ITD and QH
+ * entries; FSTN position has nothing to do with the budget and is
+ * handled by code specific to FSTNs.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame number in the hardware schedule to search; masked to
+ * prevent overflow
+ * @translate: budget entry to translate to hardware schedule
+ * @hw_p: return a pointer to the predecessor's hw_next field
+ */
+static union ehci_shadow *
+periodic_translate_budget (struct ehci_hcd *ehci,
+ unsigned frame,
+ struct ehci_shadow_budget *translate,
+ __le32 **hw_p)
+{
+ struct ehci_shadow_budget *budget_curr =
+ ehci->budget [(frame & BUDGET_SLOT_MASK)];
+ union ehci_shadow *shadow =
+ &ehci->pshadow [frame & (ehci->periodic_size-1)];
+ __le32 type;
+
+ /* Complete/Inactive entries that have not yet been processed
+ by scan_periodic may yet be present, that will not affect
+ this algorithm (they will have entries present in the
+ budget, even waiting for final urb completion). */
+
+ *hw_p = &ehci->periodic [frame & (ehci->periodic_size-1)];
+ type = Q_NEXT_TYPE (**hw_p);
+
+ /* Everything in the shadow schedule will be there in the budget
+ [except for FSTNs] */
+ while (shadow->ptr){
+
+ if(type != Q_TYPE_FSTN){
+
+ /* advance past all dummy sITDs before doing anything
else. */
+ if(type == Q_TYPE_SITD &&
+ shadow->sitd->hw_backpointer != EHCI_LIST_END)
+ goto advance;
+
+ while(budget_curr &&
+ budget_curr != translate &&
+ budget_curr->owner.ptr !=
+ periodic_shadow_owner(ehci,shadow->ptr,type)){
+ budget_curr = budget_curr->next;
+ }
+ if(budget_curr == translate){
+ return shadow; /* a match! */
+ }
+
+ /* falling off the end of the budget indicates
+ * an internal logic error */
+ if(budget_curr == NULL){
+ ehci_err(ehci,
+ "schedule contains "
+ "unbudgeted transaction\n");
+ return NULL;
+ }
+ }else{
+ struct ehci_fstn *fstn = shadow->fstn;
+ /* restore fstn:
+ ITD/sITD must go before
+ QH of period > 8 must go before
+ QH of period <=8 must go after
+ */
+ /* save fstn:
+ all ITD/sITD must go before
+ all QH must go after
+ */
+
+ if(translate->type == BUDGET_TYPE_ITD){
+ return shadow;
+ }
+
+ if(fstn->hw_prev == EHCI_LIST_END)
+ if(translate->owner.qh->period > 8)
+ return shadow;
+
+ }
+
+ advance:
+ /* advance shadow and hardware schedule by one, then
+ loop to test this position */
+ *hw_p = shadow->hw_next;
+ shadow = periodic_next_shadow (shadow, type);
+ type = Q_NEXT_TYPE (**hw_p);
+
+ }
+
+ /* nothing queued or fell off the end looking for stopping point.
+ Append to end. */
+ return shadow;
+
+}
+
+/* budget_unlink_entries_by_owner - scan the complete shadow budget
+ * and unlink/free all entries owned by passed in owner ptr.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @owner: pointer to owner
+ */
+static void budget_unlink_entries_by_owner(struct ehci_hcd *ehci,void *owner)
+{
+ struct ehci_shadow_budget *qh = NULL;
+ int frame;
+
+ if(sched_verbose){
+ ehci_info(ehci, "Releasing bandwidth for owner %p\n",
+ owner);
+ ehci_info(ehci, " Budget before: \n");
+ print_budget(ehci,NULL,owner);
+ }
+
+ for(frame=0; frame<BUDGET_SLOTS; frame++){
+ struct ehci_shadow_budget **budget = &ehci->budget[frame];
+
+ while(*budget){
+ if((*budget)->owner.ptr == owner){
+ struct ehci_shadow_budget *next =
+ ((*budget)->next);
+
+ switch((*budget)->type){
+ default:
+ case BUDGET_TYPE_ITD:
+
+ kmem_cache_free(ehci->budget_pool,
+ *budget);
+ *budget = next;
+
+ break;
+ case BUDGET_TYPE_QH:
+ if(!qh || (*budget)==qh){
+ qh = *budget;
+ *budget = next;
+ break;
+ }
+
+ /* another qh with the same
+ owner is an internal error;
+ not fatal, but shouldn't
+ happen. We will leak the
+ memory rather than risk a
+ double-free. */
+ ehci_err(ehci,
+ "multiple unique QH budget "
+ "entries with same endpoint "
+ "owner.\n");
+
+ break;
+ }
+ /* do not advance; need to process the
+ replacement which is now *budget */
+ }else
+ budget = &((*budget)->next);
+
+ }
+ }
+
+ if(qh)kmem_cache_free(ehci->budget_pool,qh);
+
+ if(sched_verbose){
+ ehci_info(ehci, " Budget after: \n");
+ print_budget(ehci,NULL,owner);
+ }
+
+}
+
+/*-------------------------------------------------------------------------*/
+/* Shadow budget constraint/metric calculation routines */
+
+/* determine the TT relevant to this shadow budget entry
+ *
+ * @b: pointer to shadow budget entry
+ */
+static int
+budget_same_tt (struct ehci_shadow_budget *b1,struct ehci_shadow_budget *b2)
+{
+ struct usb_device *dev1;
+ struct usb_device *dev2;
+
+ switch (b1->type) {
+ case BUDGET_TYPE_QH:
+ dev1 = b1->owner.qh->dev;
+ break;
+ case BUDGET_TYPE_ITD:
+ dev1 = b1->owner.iso->udev;
+ break;
+ default:
+ return 0;
+ }
+
+ switch (b2->type) {
+ case BUDGET_TYPE_QH:
+ dev2 = b2->owner.qh->dev;
+ break;
+ case BUDGET_TYPE_ITD:
+ dev2 = b2->owner.iso->udev;
+ break;
+ default:
+ return 0;
+ }
+
+ if(dev1->tt != dev2->tt)
+ return 0;
+ if (dev1->tt->multi)
+ return dev1->ttport == dev2->ttport;
+ else
+ return 1;
+
+}
+
+/* _calc_hs_uframe - count usecs used in the HS schedule of the
+ * specified frame/uFrame. *new is a new proposed shadow budget entry
+ * to be treated as if it is already linked into the shadow budget at
+ * position **insert. Returns abolute usec count, not metric or
+ * remaining available usecs.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame position in the shadow budget (masked to shadow budget size)
+ * @uFrame: uFrame position within full frame; may be 8 or 9 to access
+ * spanning c_mask
+ * @insert: position of *new [NULL if new is NULL]
+ * @new: a proposed shadow entry to be treated as appearing at position
+ * *insert; may be NULL
+ */
+static int _calc_hs_uframe(struct ehci_hcd *ehci,
+ int frame,
+ int uFrame,
+ struct ehci_shadow_budget **insert,
+ struct ehci_shadow_budget *new)
+{
+ struct ehci_shadow_budget **budget =
+ &ehci->budget [(frame & BUDGET_SLOT_MASK)];
+ int usec = 0;
+ if(budget == insert) budget = &new;
+
+ while(*budget){
+ struct ehci_shadow_budget *budgetp = *budget;
+
+ /* is it in the S-mask? */
+ if (budgetp->smask & (1 << uFrame))
+ usec += budgetp->s_usecs;
+
+ /* ... or C-mask? */
+ if (budgetp->cmask & (1 << uFrame))
+ usec += budgetp->c_usecs;
+
+ /* advance */
+ if(budget == &new)
+ budget = insert;
+ else{
+ budget = &(budgetp->next);
+ if(budget == insert) budget = &new;
+ }
+ }
+
+ return usec;
+}
+
+/* budget_calc_hs_frame - returns the budget 'load' metric for a given
+ * high speed frame, range -1 (invalid schedule), 0 (lowest good
+ * score) to 100 (best possible score). HS scheduling uses this to
+ * choose between possbile slots. FS/LS scheduling uses it as a check
+ * to make sure the FS budgeting choice is valid in the context of the
+ * HS schedule. *new is a new proposed shadow budget entry
+ * to be treated as if it is already linked into the shadow budget at
+ * position **insert.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame position in the shadow budget (masked to shadow budget size)
+ * @insert: position to use for *new; in other functions that take an
+ * insertion point as a marker, *insert=NULL indicates insert at end
+ * of list. budget_calc_hs_frame checks more than one frame (because
+ * of transactions that can span frames), so a simple NULL would be
+ * ambiguous. Thus the pointer to the insertion point, which would
+ * uniquely point to only one frame's list, even in the case of
+ * insertion.
+ * @new: a proposed shadow entry to be treated as appearing at position
+ * *insert;
+ * may be NULL
+ */
+
+static int budget_calc_hs_frame(struct ehci_hcd *ehci,
+ int frame,
+ struct ehci_shadow_budget **insert,
+ struct ehci_shadow_budget *new)
+{
+ int max=0, uFrame;
+ for(uFrame=0; uFrame<8; uFrame++){
+
+ /* first verify we've not overcommitted any uFrames */
+ /* If uFrame < 2, count the cmask contribution of
+ * spanning from prior frame */
+ int val = _calc_hs_uframe(ehci,frame,uFrame,insert,new);
+ if(uFrame<2)
+ val += _calc_hs_uframe(ehci,frame-1,
+ uFrame+8,insert,new);
+
+ if(val>max)max=val;
+ if(max>hs_usec_per_uframe){
+ return -1;
+ }
+ }
+ return 100-(max*100/hs_usec_per_uframe);
+}
+
+/* periodic_budget_fs_frame - test a proposed new addition to the
+ * periodic schedule of a given frame. Returns <0 if the frame is
+ * unsuitable, else a positive value indicating the relative space
+ * remaining in that frame after the new transaction would be
+ * scheduled; 0 is lowest score, 100 is best possible score. This
+ * return value is a metric used for breadth-first allocation of
+ * bandwidth. As a side efect, determine and set appropriate s_mask
+ * and c_mask for the passed in *new entry.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @frame: frame position in the shadow budget (masked to shadow
+ * budget size)
+ * @earliest_uFrame: prevent *new from scheduling into any uframe
+ * earlier than this
+ * @insert: position of *new
+ * @new: a proposed shadow entry to be treated as appearing at
+ * position *insert
+ */
+static int budget_calc_fs_frame(struct ehci_hcd *ehci,
+ int frame,
+ unsigned earliest_uFrame,
+ struct ehci_shadow_budget *insert,
+ struct ehci_shadow_budget *new)
+{
+ struct ehci_shadow_budget *budget =
+ ehci->budget [(frame & BUDGET_SLOT_MASK)];
+
+ /* Scheduling through a TT is done by byte counting, not usec
+ counting. Because we cannot issue a FS/LS start split in
+ uFrame 6 or 7, the only way to get anywhere near a full 90%
+ of a FS frame for periodic transactions is to 'overcommit'
+ the FS scheduling of each microframe [when considered by
+ usecs needed for the transfer]. This is not actually
+ overcommitting as the TT will buffer the 'excess' from any
+ uFrame and schedule it to transmit in a later uFrame. USB
+ 2.0 11.18.4: "Scheduling of split transactions is done by
+ the host (typically in software) based on a best-case
+ estimate of how the full-/low-speed transacitons can be run
+ on the downstream facing bus." */
+
+ /* per uFrame best-case byte budget; USB 2.0 11.18.1 */
+ int remaining_tt_bytes = fs_bytes_per_uframe;
+
+ /* max full-frame bytes for enforcing worst-case 90/10 */
+ int remaining_frame_bytes = fs_bytes_per_fullframe;
+
+ /* track max ssplits per uframe per TT */
+ int remaining_tt_transactions = endpoints_per_uframe;
+
+ /* track the amount of frame spanned (likely > used) by ISO */
+ int load_frame_bytes = 0;
+
+ int uFrame=0;
+ int load = remaining_frame_bytes;
+ int spanned_gap = 0;
+
+ if(budget == insert) budget = new;
+ earliest_uFrame &= 0x7;
+
+ while(budget){
+ int start_frame = uFrame;
+ u8 smask=0;
+ u16 cmask=0;
+
+ /* exclude other TTs as well as HS transfers, which
+ have no bearing on FS sched. */
+ if(!budget_same_tt(new,budget))
+ goto advance;
+
+ if(budget != new){
+
+ /* For a variety of reasons, the preexisting
+ FS budget may contain holes where something
+ could be scheduled but nothing is. In this
+ case, the current budget placeholder's
+ smask will exist entirely in the future.
+ Test for this case and advance the counters
+ if true. */
+ if( ((budget->smask >> (uFrame+1)) << (uFrame+1)) ==
+ budget->smask){
+ remaining_tt_bytes =
+ fs_bytes_per_uframe;
+ remaining_tt_transactions =
+ endpoints_per_uframe;
+ uFrame++;
+ continue;
+ }
+
+ /* For now, the scheduler holds invariant that
+ transactions appear in a frame in smask
+ order; that is, that FS transactions appear
+ in the frame budget in the same order that
+ they are run by the host controller.
+
+ Thus, the current transaction must not have
+ already been scheduled into the hardware
+ schedule to start before now. */
+
+ if( ((budget->smask >> uFrame) << uFrame) !=
+ budget->smask)
+ return -1;
+
+
+ }else{
+ if(uFrame < earliest_uFrame){
+ remaining_tt_bytes =
+ fs_bytes_per_uframe;
+ remaining_tt_transactions =
+ endpoints_per_uframe;
+ uFrame++;
+ continue;
+ }
+ }
+
+ if(!spanned_gap && budget->type == BUDGET_TYPE_QH){
+ load = fs_bytes_per_uframe * (uFrame+1) -
+ load_frame_bytes;
+
+ if(load<1)load=1;
+ spanned_gap=1;
+ }
+
+ remaining_frame_bytes -= budget->tt_bytes;
+ remaining_tt_bytes -= budget->tt_bytes;
+ remaining_tt_transactions--;
+
+ if(remaining_tt_transactions<0 || remaining_frame_bytes<0)
+ return -1;
+
+ while(remaining_tt_bytes <= 0){
+ remaining_tt_bytes += fs_bytes_per_uframe;
+ remaining_tt_transactions = endpoints_per_uframe;
+ uFrame++;
+ }
+
+ if(!spanned_gap){
+ load_frame_bytes =
+ fs_bytes_per_uframe * (uFrame+1) -
+ remaining_tt_bytes;
+ load = fs_bytes_per_fullframe -
+ load_frame_bytes;
+ }
+
+ if(budget != new) goto advance;
+
+ /* Generate smask/cmask for new entry */
+
+ if(budget->type == BUDGET_TYPE_QH){
+ smask = (0x01 << start_frame);
+ /* cmask purposely overflows the frame by some
+ amount if FSTN is needed for frame
+ spanning */
+ /* USB 2.0 11.18.4.3.b */
+ cmask = (0x1c << start_frame);
+
+ /* don't allow spanning yet */
+ if(cmask&(~0xff))
+ return -1;
+
+ }else{
+ /* sitd */
+ if(budget->owner.iso->bEndpointAddress & USB_DIR_IN){
+ /* cmask purposely overflows the frame
+ by some amount if dummy SITD is
+ needed for frame spanning */
+ smask = (0x01 << start_frame);
+ cmask = ((1<<(uFrame-start_frame+3)) - 1) <<
+ (2 + start_frame);
+ }else{
+ /* ISO OUT */
+ smask = ((1 << (uFrame-start_frame+1)) - 1) <<
+ start_frame;
+ cmask = 0;
+ }
+
+ /* don't allow spanning yet */
+ if(cmask&(~0xff))
+ return -1;
+
+ }
+
+ /* FS/LS ssplit in uFrame 6 or 7 is illegal */
+ if(smask & 0xffc0)
+ return -1;
+
+ new->smask=smask;
+ new->cmask=cmask;
+
+ advance:
+
+ if(budget == new)
+ budget = insert;
+ else{
+ budget = budget->next;
+ if(budget == insert) budget = new;
+ }
+ }
+
+ return (load * 100 / fs_bytes_per_fullframe);
+}
+
+/* _make_hs_smask - convenience function for generating a HS smask
+ *
+ * @period: trnsaction interval (in uFrames)
+ * @uFrame: intraframe offset
+ */
+static unsigned _make_hs_smask(int period, int uFrame)
+{
+ switch(period){
+ case 1:
+ return 0xff;
+ case 2:
+ return 0x55 << (uFrame & 0x1);
+ case 4:
+ return 0x11 << (uFrame & 0x3);
+ default:
+ return 0x01 << (uFrame & 0x7);
+ }
+}
+
+/*-------------------------------------------------------------------------*/
+/* Top-level shadow budget query and controlling logic */
+
+/* budget_add_endpoint - create a new shadow budget entry for a
+ * transaction of passed in type, owner and interval, and add it to
+ * the shadow budget (or return nonzero if the request is
+ * impossible,eg, no room in the bandwidth budget).
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @owner: pointer to transaction owner (ehci_qh or ehci_iso_stream)
+ * @type: BUDGET_TYPE_QH (intr) or BUDGET_TYPE_ITD (itd or sitd)
+ * @interval: endpoint interval (always in uFrames)
+ */
+static int budget_add_endpoint (struct ehci_hcd *ehci,
+ void *owner,
+ u8 type,
+ int interval)
+{
+ int status = 0;
+ int frame,uFrame;
+ int best_choice = -1;
+ int best_metric = -1;
+ int period = (interval ?
+ (interval > BUDGET_SLOTS*8 ? BUDGET_SLOTS*8 : interval) :
+ 1);
+ int period_8 = ( (period>>3) ? (period>>3) : 1); // always <=
+ // _period_to_level
+ struct ehci_shadow_budget new, *new_p = NULL;
+ memset(&new,0,sizeof(new));
+ new.owner.ptr = owner;
+ new.type = type;
+
+ switch (type){
+ case BUDGET_TYPE_ITD:
+ {
+ struct ehci_iso_stream *stream =
+ (struct ehci_iso_stream *)owner;
+ new.s_usecs = stream->usecs;
+ new.c_usecs = stream->c_usecs;
+ new.tt_bytes = stream->tt_bytes;
+ if(sched_verbose){
+ ehci_info(ehci, "Budgeting new [s]ITD: owner %p, "
+ "timing %u,%u,%u, interval %d\n",
+ owner,new.s_usecs,new.c_usecs,new.tt_bytes,
+ interval);
+ }
+ }
+ break;
+ case BUDGET_TYPE_QH:
+ {
+ struct ehci_qh *qh = (struct ehci_qh *)owner;
+ new.s_usecs = qh->usecs;
+ new.c_usecs = qh->c_usecs;
+ new.tt_bytes = qh->tt_bytes;
+ if(sched_verbose){
+ ehci_info(ehci, "Budgeting new QH: owner %p, "
+ "timing %u,%u,%u, interval %d\n",
+ owner,new.s_usecs,new.c_usecs,new.tt_bytes,
+ interval);
+ }
+ }
+ break;
+ default:
+ status = -ENOSYS;
+ goto out;
+ }
+
+ if(sched_verbose){
+ if(new.tt_bytes)
+ printk(KERN_INFO " FS/LS strategy, Metrics:\n");
+ else
+ printk(KERN_INFO " HS strategy, Metrics:\n");
+ }
+
+ /* determine best 'slot' */
+ for(uFrame = 0; uFrame < period; uFrame++){
+ int frame = (uFrame >> 3);
+ int min_metric = 100; /* percent */
+
+ if(sched_verbose)
+ printk(KERN_INFO " uFrame slot %d : ",uFrame);
+
+ /* scan entirety of slot */
+ for(; frame<BUDGET_SLOTS; frame+=period_8){
+ struct ehci_shadow_budget **insert =
+ budget_position_new(ehci,frame,&new);
+ int hs_metric=0, fs_metric=0;
+
+ if(new.tt_bytes){
+ /* FS/LS endpoint; budget against FS
+ * frame as the primary constraint */
+ /* periodic_budget_fs_frame side
+ * effect: fills in prospective
+ * masks */
+ fs_metric = budget_calc_fs_frame(
+ ehci, frame, uFrame, *insert, &new);
+ hs_metric = budget_calc_hs_frame(
+ ehci, frame, insert, &new);
+
+ if(fs_metric < min_metric)
+ min_metric = fs_metric;
+ if(hs_metric < 0)
+ min_metric = -1;
+
+ }else{
+ new.smask = _make_hs_smask(period,uFrame);
+ hs_metric = budget_calc_hs_frame(
+ ehci, frame, insert, &new);
+ if(hs_metric < min_metric)
+ min_metric = hs_metric;
+ }
+
+ if(sched_verbose){
+ printk(" %d:%d|%d",
+ frame, fs_metric,hs_metric);
+ }
+
+
+ /* If the c_mask 'overflowed', this indicates
+ a frame wrap either FSTN or dummy sITD.
+ Verify it will fit into the next frame's HS
+ budget. */
+ if(BUDGET_WRAP_P(&new)){
+ int span_metric = budget_calc_hs_frame(
+ ehci, frame+1, insert, &new);
+ if(span_metric < 0) min_metric = -1;
+ if(sched_verbose)
+ printk("|%d",span_metric);
+
+ }
+
+ if(min_metric <= best_metric)
+ break; // already no better than
+ // previous best; no reason to
+ // keep looking
+
+ }
+ if(sched_verbose)
+ printk("\n");
+
+ if(min_metric>best_metric){
+ best_metric = min_metric;
+ best_choice = uFrame;
+ }
+
+ if(best_metric == 100)
+ break; // best possible result; no reason to
+ // keep looking
+ }
+
+ if(sched_verbose)
+ ehci_info(ehci," Budgeting slot choice: %d\n",best_choice);
+
+ if(best_choice < 0){
+ status = -ENOSPC;
+ goto out;
+ }
+
+ /* All checks pass. Add necessary budget placeholder[s] to
+ shadow budget */
+ uFrame = best_choice;
+ frame = (uFrame >> 3);
+ for(; frame<BUDGET_SLOTS; frame += period_8){
+ struct ehci_shadow_budget **insert = NULL;
+
+ /* QH uses only one entry that's connected into the
+ tree part of the budget. ISO streams use one entry
+ per slot, just like in the hardware budget. */
+ if(new_p == NULL || type != BUDGET_TYPE_QH)
+ new_p = kmem_cache_zalloc(ehci->budget_pool,
+ GFP_ATOMIC);
+ if(new_p == NULL){
+ /* clean up; remove partially complete
+ * budgeting and error out*/
+ budget_unlink_entries_by_owner(ehci,owner);
+ status = -ENOMEM;
+ goto out;
+ }
+ memcpy(new_p,&new,sizeof(new));
+
+ /* reconstruct best budget masks and positioning
+ (saves on storage not to save all the possibilities
+ from above) */
+ insert = budget_position_new(ehci,frame,new_p);
+ if(*insert != new_p){
+ if(new.tt_bytes){
+ /* FS/LS */
+ budget_calc_fs_frame(ehci, frame, uFrame,
+ *insert, new_p);
+ }else{
+ /* HS */
+ new_p->smask = _make_hs_smask(period,uFrame);
+ }
+
+ if(type == BUDGET_TYPE_QH)
+ ((struct ehci_qh *)owner)->budget = new_p;
+
+ /* link new entry */
+ new_p->next = *insert;
+ *insert = new_p;
+
+ }else
+ ehci_err(ehci,"Should not have seen same QH "
+ "while linking in budget tree\n");
+ }
+out:
+ if(sched_verbose){
+ ehci_info(ehci, " Budgeting status: %d\n",
+ status);
+ ehci_info(ehci, " Budget after: \n");
+ print_budget(ehci,NULL,owner);
+ }
+
+ return status;
+}
+
+/* budget_schedule_next - Return the proper frame number and position
+ * in the shadow schedule of the next transaction belonging to owner
+ * in the shadow budget. If the transaction is already in the
+ * shadow/hard schedule, here->ptr will point to it.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @startframe: frame number in the shadow schedule at which to begin search
+ * @owner: pointer to transaction owner (ehci_qh or ehci_iso_stream)
+ * @b: returns pointer to matching shadow budget entry (NULL if none)
+ * @here: returns pointer to insertion position in shadow schedule
+ * @hw_p: returns pointer to insertion position in hardware schedule
+ */
+static int budget_schedule_next (struct ehci_hcd *ehci,
+ int startframe,
+ void *owner,
+ struct ehci_shadow_budget **b,
+ union ehci_shadow **here,
+ __le32 **hw_p)
+{
+ int i;
+ for(i=startframe; i < startframe+BUDGET_SLOTS; i++){
+ int pframe = i & (ehci->periodic_size-1);
+
+ /* search for it in this frame's budget; we're only
+ searching for sITD, ITD and QH. Finding a spanning
+ element reuses the discovered *b elsewhere */
+ *b = budget_find_entry_by_owner(ehci, i, owner);
+ if(*b){
+ *here = periodic_translate_budget(ehci,pframe,*b,hw_p);
+ if(*here){
+ return i;
+ }
+ }
+ }
+
+ *here = NULL;
+ *b = NULL;
+ ehci_err(ehci,"tried to schedule an endpoint that doesn't "
+ "appear in the budget\n");
+ return -1;
+}
+
+/* budget_schedule_next - Return the number of the next frame for
+ * which there's a budgeted transaction for owner.
+ *
+ * @ehci: pointer to ehci host controller device structure.
+ * @startframe: frame number in the shadow schedule at which to begin search
+ * @owner: pointer to transaction owner (ehci_qh or ehci_iso_stream)
+ */
+static int budget_schedule_next_frame (struct ehci_hcd *ehci,
+ int startframe,
+ void *owner)
+{
+ int i;
+ for(i=startframe; i < startframe+BUDGET_SLOTS; i++){
+ struct ehci_shadow_budget *b;
+ int bframe = i & BUDGET_SLOT_MASK;
+ b = budget_find_entry_by_owner(ehci, bframe, owner);
+ if(b){
+ return i;
+ }
+ }
+ return -1;
+}
+
+/* end of shadow budget implementation */
+
+/*-------------------------------------------------------------------------*/
+
/* how many of the uframe's 125 usecs are allocated? */
static unsigned short
periodic_usecs (struct ehci_hcd *ehci, unsigned frame, unsigned uframe)
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys -- and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
[email protected]
To unsubscribe, use the last form field at:
https://lists.sourceforge.net/lists/listinfo/linux-usb-devel
