[PATCH 1/3] ALSA USB MIDI: Fix port starvation

[Andreas Steinmetz]

On Tue, 2020-03-17 at 11:26 +0100, Clemens Ladisch wrote:
> Andreas Steinmetz wrote:
> > On Mon, 2020-03-16 at 13:03 +0100, Clemens Ladisch wrote:
> > > Andreas Steinmetz wrote:
> > > > the snd_usbmidi_transmit_byte helper had to be converted to
> > > > return output notification to allow for the 'repeat' shortcut.
> > > 
> > > Why not simply handle one MIDI byte per port in each
> > > iteration?  It
> > > could be argued that single-byte MIDI commands are likely to be
> > > real-
> > > time messages and deserve to go first.
> > 
> > Actually the patch does exactly this. As soon as the helper signals
> > that a message is complete the next port is processed. The "repeat"
> > loop is just necessary to get a complete class compliant message
> > for
> > transfer as the helper processes one byte at a time.
> 
> Why is it necessary to immedately get a complete class-compliant
> message?
> 

Maybe that's a misunderstanding caused by me using 'message' instead of
'event'. We need a complete MIDI event (or up to 3 sysex bytes) to form
the class compliant 4 byte USB event. That's what the 'repeat' shortcut
is for. And after one such event is collected to the URB the code
switches to the next port.

> > The range optimization is there to prevent O(2) performance cost if
> > possible.
> 
> Do you mean O(n^2)?  For what n?
> 

What I do mean is that in case of only one port being active we would
do 16 full outer iterations over all ports to collect 1 event. And we
need to do this for all events of that port. Even if we use the hint
from port->active as a shortcut its always the full set of iterations.

Memorizing the first and the last port of the previous loop and then
restricting to this set makes a full 16 port run in the first iteration
and then only the active port for all subsequent iterations.

And yes, in the worst case of a 16x16 interface with ports 1 and 16
being active we're back to processing 16 ports for every iteration - I
do, however, see this scenario as being quite theoretical in practice.

> > > My original idea for that FIXME was to use round robin until the
> > > packet
> > > is filled (or all ports are empty), and to store the next port
> > > index
> > > (where to start for the next packet) in the endpoint.  This would
> > > be
> > > able to distribute the balancing over multiple packets.
> > 
> > The problem with "round robin until the packet is filled" is that
> > in
> > case of a large wMaxPacketSize there's then a huge
> > latency.
> 
> This mechanism does not require using the original packet size.
> The point is that we should not restart with the first port in each
> packet.

I was thinking about that but in practice I do not know any class
compliant interface that does have a number of outputs that is not
equal to 2^n, i.e. 1, 2, 4, 8, 16.

Then wMaxPacketSize is also always a 2^m value (16, 64, 512).

With m>=n+2 (I don't believe that there is any class compliant
interface for which this is not true) we can always start at the first
port while doing fair scheduling (when a new URB is filled all ports
get an equal change if they do have events pending).

Implementing a restart based on the last packet scheduled for the very
rare possibility of the above being not true just adds unnecessary
complexity.

> 
> 
> Regards,
> Clemens
Regards
-- 
Andreas Steinmetz