61 /* If we get a NAK, wait this long before retrying */
150  * @num_bits:        The number of bits we need per period we want to reserve
152  * @interval:        How often we need to be scheduled for the reservation this
156  *                   the interval or we return failure right away.
157  * @only_one_period: Normally we'll allow picking a start anywhere within the
158  *                   first interval, since we can still make all repetition
160  *                   here then we'll return failure if we can't fit within
163  * The idea here is that we want to schedule time for repeating events that all
168  * To keep things "simple", we'll represent our schedule with a bitmap that
170  * but does mean that we need to handle things specially (and non-ideally) if
172  * intervals that we're trying to schedule.
174  * Here's an explanation of the scheme we'll implement, assuming 8 periods.
175  * - If interval is 1, we need to take up space in each of the 8
176  *   periods we're scheduling.  Easy.
177  * - If interval is 2, we need to take up space in half of the
179  * - If interval is 3, we actually need to fall back to interval 1.
180  *   Why?  Because we might need time in any period.  AKA for the
181  *   first 8 periods, we'll be in slot 0, 3, 6.  Then we'll be
182  *   in slot 1, 4, 7.  Then we'll be in 2, 5.  Then we'll be back to
183  *   0, 3, and 6.  Since we could be in any frame we need to reserve
185  *   if we were instead scheduling 8 * 3 = 24 we'd do much better, but
186  *   then we need more memory and time to do scheduling.
188  * - If interval is 5, we again need interval 1.  The schedule will be
190  * - If interval is 6, we need interval 2.  0, 6, 4, 2.
191  * - If interval is 7, we need interval 1.
192  * - If interval is 8, we need interval 8.
194  * If you do the math, you'll see that we need to pretend that interval is
250 	/* If start has gotten us past interval then we can't schedule */  in pmap_schedule()
262 	 * We'll try to pick the first repetition, then see if that time  in pmap_schedule()
264 	 * we'll adjust the start time for the next search of the first  in pmap_schedule()
278 		 * We should get start >= end if we fail.  We might be  in pmap_schedule()
287 		/* At this point we have a valid point for first one */  in pmap_schedule()
298 			/* We got the right place, continue checking */  in pmap_schedule()
313 		/* If didn't exit the for loop with a break, we have success */  in pmap_schedule()
367  * We'll always get the periodic map out of our TT.  Note that even if we're
369  * a TT is allocated for us, so we'll use it.  If that ever changes we can
523 	 * If we don't have tracing turned on, don't run unless the special  in dwc2_qh_schedule_print()
574  * @search_slice: We'll start trying to schedule at the passed slice.
580  * Normally we schedule low speed devices on the map associated with the TT.
596 	 * parameters.  Note that we use the "device_interval" here since  in dwc2_ls_pmap_schedule()
597 	 * we want the low speed interval and the only way we'd be in this  in dwc2_ls_pmap_schedule()
600 	 * If we happen to be doing low speed and high speed scheduling for the  in dwc2_ls_pmap_schedule()
601 	 * same transaction (AKA we have a split) we always do low speed first.  in dwc2_ls_pmap_schedule()
602 	 * That means we can always pass "false" for only_one_period (that  in dwc2_ls_pmap_schedule()
603 	 * parameters is only useful when we're trying to get one schedule to  in dwc2_ls_pmap_schedule()
604 	 * match what we already planned in the other schedule).  in dwc2_ls_pmap_schedule()
643  * We'll start looking in qh->hs_transfers[index].start_schedule_us.  We'll
644  * update this with the result upon success.  We also use the duration from
649  * @only_one_period: If true we will limit ourselves to just looking at
650  *                   one period (aka one 100us chunk).  This is used if we have
653  * @index:           The index into qh->hs_transfers that we're working with.
698  * This is the most complicated thing in USB.  We have to find matching time
724 	 * We always try to find space in the low speed schedule first, then  in dwc2_uframe_schedule_split()
725 	 * try to find high speed time that matches.  If we don't, we'll bump  in dwc2_uframe_schedule_split()
726 	 * up the place we start searching in the low speed schedule and try  in dwc2_uframe_schedule_split()
727 	 * again.  To start we'll look right at the beginning of the low speed  in dwc2_uframe_schedule_split()
731 	 * We may eventually want to try to avoid this by either considering  in dwc2_uframe_schedule_split()
752 			 * If we got an error here there's no other magic we  in dwc2_uframe_schedule_split()
754 			 * helpful to redo things if we got a low speed slot  in dwc2_uframe_schedule_split()
775 		 * If we were going to start in uframe 7 then we would need to  in dwc2_uframe_schedule_split()
803 		 * For ISOC out we might need to do:  in dwc2_uframe_schedule_split()
809 		 * For INTERRUPT in we might need to do:  in dwc2_uframe_schedule_split()
815 		 * For INTERRUPT out we might need to do:  in dwc2_uframe_schedule_split()
852 		 * the above cases.  Until it's fixed we just won't be able  in dwc2_uframe_schedule_split()
961 		/* If we scheduled all w/out breaking out then we're all good */  in dwc2_uframe_schedule_split()
997 	/* We'll have one transfer; init start to 0 before calling scheduler */  in dwc2_uframe_schedule_hs()
1074  * Takes a qh that has already been scheduled (which means we know we have the
1079  * running.  It just picks the next frame that we can fit into without any
1101 	 * We wouldn't want to start any earlier than the next frame just in  in dwc2_pick_first_frame()
1102 	 * case the frame number ticks as we're doing this calculation.  in dwc2_pick_first_frame()
1104 	 * NOTE: if we could quantify how long till we actually get scheduled  in dwc2_pick_first_frame()
1105 	 * we might be able to avoid the "+ 1" by looking at the upper part of  in dwc2_pick_first_frame()
1106 	 * HFNUM (the FRREM field).  For now we'll just use the + 1 though.  in dwc2_pick_first_frame()
1121 		 * We're either at high speed or we're doing a split (which  in dwc2_pick_first_frame()
1122 		 * means we're talking high speed to a hub).  In any case  in dwc2_pick_first_frame()
1151 	 * We know interval must divide (HFNUM_MAX_FRNUM + 1) now that we've  in dwc2_pick_first_frame()
1155 	 * After this we might be before earliest_frame, but don't worry,  in dwc2_pick_first_frame()
1156 	 * we'll fix it...  in dwc2_pick_first_frame()
1161 	 * Actually choose to start at the frame number we've been  in dwc2_pick_first_frame()
1168 	 * We actually need 1 frame before since the next_active_frame is  in dwc2_pick_first_frame()
1169 	 * the frame number we'll be put on the ready list and we won't be on  in dwc2_pick_first_frame()
1175 	 * By now we might actually be before the earliest_frame.  Let's move  in dwc2_pick_first_frame()
1176 	 * up intervals until we're not.  in dwc2_pick_first_frame()
1253 	/* No more unreserve pending--we're doing it */  in dwc2_do_unreserve()
1274  * "Reserved Bandwidth Transfers"), we need to keep a reservation active as
1275  * long as a device driver keeps submitting.  Since we're using HCD_BH to give
1276  * back the URB we need to give the driver a little bit of time before we
1289 	 * Wait for the lock, or for us to be scheduled again.  We  in dwc2_unreserve_timer_fn()
1291 	 * - We started executing but didn't get the lock yet.  in dwc2_unreserve_timer_fn()
1293 	 *   because we already started executing.  in dwc2_unreserve_timer_fn()
1304 	 * - We started executing but didn't get the lock yet.  in dwc2_unreserve_timer_fn()
1306 	 *   because we already started executing.  in dwc2_unreserve_timer_fn()
1308 	 * We can't put this in the loop above because unreserve_pending needs  in dwc2_unreserve_timer_fn()
1309 	 * to be accessed under lock, so we can only check it once we got the  in dwc2_unreserve_timer_fn()
1377 	 * valid.  Unreserve might still be pending even if we didn't cancel if  in dwc2_schedule_periodic()
1388 		 * is still good.  Note: we could also try to use the similar  in dwc2_schedule_periodic()
1390 		 * tightly and we might need to hurry and queue things up.  in dwc2_schedule_periodic()
1431 	 * We should never already be scheduled since dwc2_schedule_periodic()  in dwc2_deschedule_periodic()
1435 	 * We add + 1 to the timer to guarantee that at least 1 jiffy has  in dwc2_deschedule_periodic()
1436 	 * passed (otherwise if the jiffy counter might tick right after we  in dwc2_deschedule_periodic()
1437 	 * read it and we'll get no delay).  in dwc2_deschedule_periodic()
1454  * That means that when we encounter a NAK we're supposed to retry.
1456  * ...but if we retry right away (from the interrupt handler that saw the NAK)
1457  * then we can end up with an interrupt storm (if the other side keeps NAKing
1462  * ...so instead of retrying right away in the case of a NAK we'll set a timer
1479 	 * We'll set wait_timer_cancel to true if we want to cancel this  in dwc2_wait_timer_fn()
1565 		 * Schedule low speed if we're running the host in low or  in dwc2_qh_init()
1566 		 * full speed OR if we've got a "TT" to deal with to access this  in dwc2_qh_init()
1573 			/* We won't know num transfers until we schedule */  in dwc2_qh_init()
1581 		/* We'll schedule later when we have something to do */  in dwc2_qh_init()
1693 	 * We don't have the lock so we can safely wait until the wait timer  in dwc2_hcd_qh_free()
1694 	 * finishes.  Of course, at this point in time we'd better have set  in dwc2_hcd_qh_free()
1696 	 * won't do anything anyway, but we want it to finish before we free  in dwc2_hcd_qh_free()
1810  * Periodic splits are single low/full speed transfers that we end up splitting
1812  * frame but might be split over several microframes (125 us each).  We to put
1821  * Return: number missed by (or 0 if we didn't miss).
1848 	 * be 1 frame _before_ when we want to be scheduled.  If we're 1 frame  in dwc2_next_for_periodic_split()
1851 	 * It's _not_ OK, however, if we're more than one frame past.  in dwc2_next_for_periodic_split()
1855 		 * OOPS, we missed.  That's actually pretty bad since  in dwc2_next_for_periodic_split()
1873  * Since we _always_ keep start_active_frame as the start of the previous
1874  * transfer this is normally pretty easy: we just add our interval to
1875  * start_active_frame and we've got our answer.
1877  * The tricks come into play if we miss.  In that case we'll look for the next
1878  * slot we can fit into.
1884  * Return: number missed by (or 0 if we didn't miss).
1898 	 * with if we just incremented by a really large intervals since the  in dwc2_next_periodic_start()
1899 	 * frame counter only goes to 0x3fff.  It's terribly unlikely that we  in dwc2_next_periodic_start()
1900 	 * will have missed in this case anyway.  Just go to exit.  If we want  in dwc2_next_periodic_start()
1901 	 * to try to do better we'll need to keep track of a bigger counter  in dwc2_next_periodic_start()
1911 	 * - We compare against prev_frame_number since start_active_frame  in dwc2_next_periodic_start()
1912 	 *   and next_active_frame are always 1 frame before we want things  in dwc2_next_periodic_start()
1913 	 *   to be active and we assume we can still get scheduled in the  in dwc2_next_periodic_start()
1916 	 *   next_active_frame if we got an EO MISS (even_odd miss) which  in dwc2_next_periodic_start()
1917 	 *   basically means that we detected there wasn't enough time for  in dwc2_next_periodic_start()
1919 	 *   at the last second.  We want to make sure we don't schedule  in dwc2_next_periodic_start()
1922 	 *   we do two transfers in the same frame.  in dwc2_next_periodic_start()
1929 	 *   time.  We can help with the dwc2 parts of this, but it's hard to  in dwc2_next_periodic_start()
1931 	 *   we have to be robust to some misses.  in dwc2_next_periodic_start()
1998 	 * means we don't actually know if we've already handled the SOF  in dwc2_hcd_qh_deactivate()
2024 	 * Note: we purposely use the frame_number from the "hsotg" structure  in dwc2_hcd_qh_deactivate()
2025 	 * since we know SOF interrupt will handle future frames.  in dwc2_hcd_qh_deactivate()