/* * 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 * under the terms of the GNU General Public License as published by the * Free Software Foundation; either version 2 of the License, or (at your * option) any later version. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License * for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software Foundation, * Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *//* this file is part of ehci-hcd.c *//*-------------------------------------------------------------------------*//* * EHCI scheduled transaction support:  interrupt, iso, split iso * These are called "periodic" transactions in the EHCI spec. * * 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. * * 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);/*-------------------------------------------------------------------------*//* * periodic_next_shadow - return "next" pointer on shadow list * @periodic: host pointer to qh/itd/sitd * @tag: hardware tag for type of this record */static union ehci_shadow *periodic_next_shadow (union ehci_shadow *periodic, __le32 tag){	switch (tag) {	case Q_TYPE_QH:		return &periodic->qh->qh_next;	case Q_TYPE_FSTN:		return &periodic->fstn->fstn_next;	case Q_TYPE_ITD:		return &periodic->itd->itd_next;	// case Q_TYPE_SITD:	default:		return &periodic->sitd->sitd_next;	}}/* caller must hold ehci->lock */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;	/* 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.hw_next;		here = *prev_p;	}	/* an interrupt entry (at list end) could have been shared */	if (!here.ptr)		return;	/* update shadow and hardware lists ... the old "next" pointers	 * from ptr may still be in use, the caller updates them.	 */	*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? */static unsigned shortperiodic_usecs (struct ehci_hcd *ehci, unsigned frame, unsigned uframe){	__le32			*hw_p = &ehci->periodic [frame];	union ehci_shadow	*q = &ehci->pshadow [frame];	unsigned		usecs = 0;	while (q->ptr) {		switch (Q_NEXT_TYPE (*hw_p)) {		case Q_TYPE_QH:			/* is it in the S-mask? */			if (q->qh->hw_info2 & cpu_to_le32 (1 << uframe))				usecs += q->qh->usecs;			/* ... or C-mask? */			if (q->qh->hw_info2 & cpu_to_le32 (1 << (8 + uframe)))				usecs += q->qh->c_usecs;			hw_p = &q->qh->hw_next;			q = &q->qh->qh_next;			break;		// case Q_TYPE_FSTN:		default:			/* for "save place" FSTNs, count the relevant INTR			 * bandwidth from the previous frame			 */			if (q->fstn->hw_prev != EHCI_LIST_END) {				ehci_dbg (ehci, "ignoring FSTN cost ...\n");			}			hw_p = &q->fstn->hw_next;			q = &q->fstn->fstn_next;			break;		case Q_TYPE_ITD:			usecs += q->itd->usecs [uframe];			hw_p = &q->itd->hw_next;			q = &q->itd->itd_next;			break;		case Q_TYPE_SITD:			/* is it in the S-mask?  (count SPLIT, DATA) */			if (q->sitd->hw_uframe & cpu_to_le32 (1 << uframe)) {				if (q->sitd->hw_fullspeed_ep &						__constant_cpu_to_le32 (1<<31))					usecs += q->sitd->stream->usecs;				else	/* worst case for OUT start-split */					usecs += HS_USECS_ISO (188);			}			/* ... C-mask?  (count CSPLIT, DATA) */			if (q->sitd->hw_uframe &					cpu_to_le32 (1 << (8 + uframe))) {				/* worst case for IN complete-split */				usecs += q->sitd->stream->c_usecs;			}			hw_p = &q->sitd->hw_next;			q = &q->sitd->sitd_next;			break;		}	}#ifdef	DEBUG	if (usecs > 100)		ehci_err (ehci, "uframe %d sched overrun: %d usecs\n",			frame * 8 + uframe, usecs);#endif	return usecs;}/*-------------------------------------------------------------------------*/static int same_tt (struct usb_device *dev1, struct usb_device *dev2){	if (!dev1->tt || !dev2->tt)		return 0;	if (dev1->tt != dev2->tt)		return 0;	if (dev1->tt->multi)		return dev1->ttport == dev2->ttport;	else		return 1;}#ifdef CONFIG_USB_EHCI_TT_NEWSCHED/* Which uframe does the low/fullspeed transfer start in? * * The parameter is the mask of ssplits in "H-frame" terms * and this returns the transfer start uframe in "B-frame" terms, * which allows both to match, e.g. a ssplit in "H-frame" uframe 0 * will cause a transfer in "B-frame" uframe 0.  "B-frames" lag * "H-frames" by 1 uframe.  See the EHCI spec sec 4.5 and figure 4.7. */static inline unsigned char tt_start_uframe(struct ehci_hcd *ehci, __le32 mask){	unsigned char smask = QH_SMASK & le32_to_cpu(mask);	if (!smask) {		ehci_err(ehci, "invalid empty smask!\n");		/* uframe 7 can't have bw so this will indicate failure */		return 7;	}	return ffs(smask) - 1;}static const unsigned charmax_tt_usecs[] = { 125, 125, 125, 125, 125, 125, 30, 0 };/* carryover low/fullspeed bandwidth that crosses uframe boundries */static inline void carryover_tt_bandwidth(unsigned short tt_usecs[8]){	int i;	for (i=0; i<7; i++) {		if (max_tt_usecs[i] < tt_usecs[i]) {			tt_usecs[i+1] += tt_usecs[i] - max_tt_usecs[i];			tt_usecs[i] = max_tt_usecs[i];		}	}}/* How many of the tt's periodic downstream 1000 usecs are allocated? * * While this measures the bandwidth in terms of usecs/uframe, * the low/fullspeed bus has no notion of uframes, so any particular * low/fullspeed transfer can "carry over" from one uframe to the next, * since the TT just performs downstream transfers in sequence. * * For example two seperate 100 usec transfers can start in the same uframe, * and the second one would "carry over" 75 usecs into the next uframe. */static voidperiodic_tt_usecs (	struct ehci_hcd *ehci,	struct usb_device *dev,	unsigned frame,	unsigned short tt_usecs[8]){	__le32			*hw_p = &ehci->periodic [frame];	union ehci_shadow	*q = &ehci->pshadow [frame];	unsigned char		uf;	memset(tt_usecs, 0, 16);	while (q->ptr) {		switch (Q_NEXT_TYPE(*hw_p)) {		case Q_TYPE_ITD:			hw_p = &q->itd->hw_next;			q = &q->itd->itd_next;			continue;		case Q_TYPE_QH:			if (same_tt(dev, q->qh->dev)) {				uf = tt_start_uframe(ehci, q->qh->hw_info2);				tt_usecs[uf] += q->qh->tt_usecs;			}			hw_p = &q->qh->hw_next;			q = &q->qh->qh_next;			continue;		case Q_TYPE_SITD:			if (same_tt(dev, q->sitd->urb->dev)) {				uf = tt_start_uframe(ehci, q->sitd->hw_uframe);				tt_usecs[uf] += q->sitd->stream->tt_usecs;			}			hw_p = &q->sitd->hw_next;			q = &q->sitd->sitd_next;			continue;		// case Q_TYPE_FSTN:		default:			ehci_dbg(ehci,				  "ignoring periodic frame %d FSTN\n", frame);			hw_p = &q->fstn->hw_next;			q = &q->fstn->fstn_next;		}	}	carryover_tt_bandwidth(tt_usecs);	if (max_tt_usecs[7] < tt_usecs[7])		ehci_err(ehci, "frame %d tt sched overrun: %d usecs\n",			frame, tt_usecs[7] - max_tt_usecs[7]);}/* * Return true if the device's tt's downstream bus is available for a * periodic transfer of the specified length (usecs), starting at the * specified frame/uframe.  Note that (as summarized in section 11.19 * of the usb 2.0 spec) TTs can buffer multiple transactions for each * uframe. * * The uframe parameter is when the fullspeed/lowspeed transfer * should be executed in "B-frame" terms, which is the same as the * highspeed ssplit's uframe (which is in "H-frame" terms).  For example * a ssplit in "H-frame" 0 causes a transfer in "B-frame" 0. * See the EHCI spec sec 4.5 and fig 4.7. * * This checks if the full/lowspeed bus, at the specified starting uframe, * has the specified bandwidth available, according to rules listed * in USB 2.0 spec section 11.18.1 fig 11-60. * * This does not check if the transfer would exceed the max ssplit * limit of 16, specified in USB 2.0 spec section 11.18.4 requirement #4, * since proper scheduling limits ssplits to less than 16 per uframe. */static int tt_available (	struct ehci_hcd		*ehci,	unsigned		period,	struct usb_device	*dev,	unsigned		frame,	unsigned		uframe,	u16			usecs){	if ((period == 0) || (uframe >= 7))	/* error */		return 0;	for (; frame < ehci->periodic_size; frame += period) {		unsigned short tt_usecs[8];		periodic_tt_usecs (ehci, dev, frame, tt_usecs);		ehci_vdbg(ehci, "tt frame %d check %d usecs start uframe %d in"			" schedule %d/%d/%d/%d/%d/%d/%d/%d\n",			frame, usecs, uframe,			tt_usecs[0], tt_usecs[1], tt_usecs[2], tt_usecs[3],			tt_usecs[4], tt_usecs[5], tt_usecs[6], tt_usecs[7]);		if (max_tt_usecs[uframe] <= tt_usecs[uframe]) {			ehci_vdbg(ehci, "frame %d uframe %d fully scheduled\n",				frame, uframe);			return 0;		}		/* special case for isoc transfers larger than 125us:		 * the first and each subsequent fully used uframe		 * must be empty, so as to not illegally delay		 * already scheduled transactions		 */		if (125 < usecs) {			int ufs = (usecs / 125) - 1;			int i;			for (i = uframe; i < (uframe + ufs) && i < 8; i++)				if (0 < tt_usecs[i]) {					ehci_vdbg(ehci,						"multi-uframe xfer can't fit "						"in frame %d uframe %d\n",						frame, i);					return 0;				}		}		tt_usecs[uframe] += usecs;		carryover_tt_bandwidth(tt_usecs);		/* fail if the carryover pushed bw past the last uframe's limit */		if (max_tt_usecs[7] < tt_usecs[7]) {			ehci_vdbg(ehci,				"tt unavailable usecs %d frame %d uframe %d\n",				usecs, frame, uframe);			return 0;		}	}	return 1;}#else/* return true iff the device's transaction translator is available * for a periodic transfer starting at the specified frame, using * all the uframes in the mask. */static int tt_no_collision (	struct ehci_hcd		*ehci,	unsigned		period,	struct usb_device	*dev,	unsigned		frame,	u32			uf_mask){	if (period == 0)	/* error */		return 0;	/* note bandwidth wastage:  split never follows csplit	 * (different dev or endpoint) until the next uframe.	 * calling convention doesn't make that distinction.	 */	for (; frame < ehci->periodic_size; frame += period) {		union ehci_shadow	here;		__le32			type;		here = ehci->pshadow [frame];		type = Q_NEXT_TYPE (ehci->periodic [frame]);		while (here.ptr) {			switch (type) {			case Q_TYPE_ITD:				type = Q_NEXT_TYPE (here.itd->hw_next);				here = here.itd->itd_next;				continue;			case Q_TYPE_QH:				if (same_tt (dev, here.qh->dev)) {					u32		mask;					mask = le32_to_cpu (here.qh->hw_info2);					/* "knows" no gap is needed */					mask |= mask >> 8;					if (mask & uf_mask)						break;				}				type = Q_NEXT_TYPE (here.qh->hw_next);				here = here.qh->qh_next;				continue;			case Q_TYPE_SITD:				if (same_tt (dev, here.sitd->urb->dev)) {					u16		mask;					mask = le32_to_cpu (here.sitd								->hw_uframe);					/* FIXME assumes no gap for IN! */					mask |= mask >> 8;					if (mask & uf_mask)						break;				}				type = Q_NEXT_TYPE (here.sitd->hw_next);				here = here.sitd->sitd_next;				continue;			// case Q_TYPE_FSTN:			default:				ehci_dbg (ehci,					"periodic frame %d bogus type %d\n",					frame, type);			}			/* collision or error */			return 0;		}	}	/* no collision */	return 1;}#endif /* CONFIG_USB_EHCI_TT_NEWSCHED *//*-------------------------------------------------------------------------*/static int enable_periodic (struct ehci_hcd *ehci){	u32	cmd;	int	status;	/* did clearing PSE did take effect yet?	 * takes effect only at frame boundaries...	 */	status = handshake(ehci, &ehci->regs->status, STS_PSS, 0, 9 * 125);	if (status != 0) {		ehci_to_hcd(ehci)->state = HC_STATE_HALT;		return status;	}	cmd = ehci_readl(ehci, &ehci->regs->command) | CMD_PSE;	ehci_writel(ehci, cmd, &ehci->regs->command);	/* posted write ... PSS happens later */	ehci_to_hcd(ehci)->state = HC_STATE_RUNNING;	/* make sure ehci_work scans these */	ehci->next_uframe = ehci_readl(ehci, &ehci->regs->frame_index)		% (ehci->periodic_size << 3);	return 0;}static int disable_periodic (struct ehci_hcd *ehci){	u32	cmd;	int	status;	/* did setting PSE not take effect yet?	 * takes effect only at frame boundaries...	 */	status = handshake(ehci, &ehci->regs->status, STS_PSS, STS_PSS, 9 * 125);	if (status != 0) {		ehci_to_hcd(ehci)->state = HC_STATE_HALT;		return status;	}	cmd = ehci_readl(ehci, &ehci->regs->command) & ~CMD_PSE;	ehci_writel(ehci, cmd, &ehci->regs->command);	/* posted write ... */	ehci->next_uframe = -1;	return 0;}/*-------------------------------------------------------------------------*//* 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;	dev_dbg (&qh->dev->dev,		"link qh%d-%04x/%p start %d [%d/%d us]\n",		period, le32_to_cpup (&qh->hw_info2) & (QH_CMASK | QH_SMASK),		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];		__le32			*hw_p = &ehci->periodic [i];		union ehci_shadow	here = *prev;		__le32			type = 0;		/* 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 */	ehci_to_hcd(ehci)->self.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