lkml.org 
[lkml]   [2005]   [Jan]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    SubjectRe: [PATCH] USB and Driver Core patches for 2.6.10
    Date
    From
    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:
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 14:09    [W:0.071 / U:0.016 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site