xhci: Implement HS/FS/LS bandwidth checking.

xhci: Implement HS/FS/LS bandwidth checking.

Now that we have a bandwidth interval table per root port or TT that
describes the endpoint bandwidth information, we can finally use it to
check whether the bus bandwidth is oversubscribed for a new device
configuration/alternate interface setting.

The complication for this algorithm is that the bit of hardware logic that
creates the bus schedule is only 12-bit logic.  In order to make sure it
can represent the maximum bus bandwidth in 12 bits, it has to convert the
endpoint max packet size and max esit payload into "blocks" (basically a
less-precise representation).  The block size for each speed of device is
different, aside from low speed and full speed.  In order to make sure we
don't allow a setup where the scheduler might fail, we also have to do the
bandwidth checking in blocks.

After checking that the endpoints fit in the schedule, we store the
bandwidth used for this root port or TT.  If this is a FS/LS device under
an external HS hub, we also update the TT bandwidth and the root port
bandwidth (if this is a newly activated or deactivated TT).

I won't go into the details of the algorithm, as it's pretty well
documented in the comments.

Signed-off-by: Sarah Sharp <sarah.a.sharp@linux.intel.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>