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

[Andreas Steinmetz]

In case of a multiport USB MIDI interface the lower numbered ports starve
higher numbered ports when more than one port is busy transmitting data.
The starvation as of the current code is complete and can be for an
arbitrarily long time. Control from userspace is not possible without
at least halving the theoretically possible device throughput.
This is especially bad as there are now 16x16 interface products available.

An unpredicable and arbitrarily long latency is not acceptable. The
loss of half of the throughput is not acceptable, either. Fair
scheduling of all busy ports is required.

The patch below balances the actual USB output between all busy ports.
It is done in such a way that the single port use performance before
applying the patch is identical to the one after applying the patch.
To get there, the snd_usbmidi_transmit_byte helper had to be converted to
return output notification to allow for the 'repeat' shortcut.

The patch tries to avoid O(2) load increase by scaling the balancing
loop to the ports that are actually busy as far as this is possible.

For the patch to properly work the wMaxPacketSize of the device must be
large enough to allow for at least one MIDI event per port in a URB.
If this constraint is not met, which is quite improbable, starvation
will occur again. Though this could be fixed the likelyhood of such
a device is so low that the additional overhead introduced for all
other devices is not worth it. Current multi port MIDI interfaces do
typically have 2^n output ports and 2^x as wMaxPacketSize where x>n.

For a four port USB MIDI interface with a wMaxPacketSize of 64 the
maximum latency for any port is changed by the patch from indefinite
to 107.52ms.

The patch affects the output of all class compliant USB MIDI interfaces.
Users will typically experience either no change or increased response,
depending on their use case.

Signed-off-by: Andreas Steinmetz <ast at domdv.de>

--- a/sound/usb/midi.c	2020-03-12 22:45:06.611877152 +0100
+++ b/sound/usb/midi.c	2020-03-13 02:33:21.392847930 +0100
@@ -554,7 +554,7 @@ static void snd_usbmidi_output_midiman_p
 /*
  * Converts MIDI commands to USB MIDI packets.
  */
-static void snd_usbmidi_transmit_byte(struct usbmidi_out_port *port,
+static int snd_usbmidi_transmit_byte(struct usbmidi_out_port *port,
 				      uint8_t b, struct urb *urb)
 {
 	uint8_t p0 = port->cable;
@@ -563,6 +563,7 @@ static void snd_usbmidi_transmit_byte(st
 
 	if (b >= 0xf8) {
 		output_packet(urb, p0 | 0x0f, b, 0, 0);
+		return 1;
 	} else if (b >= 0xf0) {
 		switch (b) {
 		case 0xf0:
@@ -585,20 +586,20 @@ static void snd_usbmidi_transmit_byte(st
 		case 0xf6:
 			output_packet(urb, p0 | 0x05, 0xf6, 0, 0);
 			port->state = STATE_UNKNOWN;
-			break;
+			return 1;
 		case 0xf7:
 			switch (port->state) {
 			case STATE_SYSEX_0:
 				output_packet(urb, p0 | 0x05, 0xf7, 0, 0);
-				break;
+				return 1;
 			case STATE_SYSEX_1:
 				output_packet(urb, p0 | 0x06, port->data[0],
 					      0xf7, 0);
-				break;
+				return 1;
 			case STATE_SYSEX_2:
 				output_packet(urb, p0 | 0x07, port->data[0],
 					      port->data[1], 0xf7);
-				break;
+				return 1;
 			}
 			port->state = STATE_UNKNOWN;
 			break;
@@ -619,7 +620,7 @@ static void snd_usbmidi_transmit_byte(st
 				port->state = STATE_UNKNOWN;
 			}
 			output_packet(urb, p0, port->data[0], b, 0);
-			break;
+			return 1;
 		case STATE_2PARAM_1:
 			port->data[1] = b;
 			port->state = STATE_2PARAM_2;
@@ -633,7 +634,7 @@ static void snd_usbmidi_transmit_byte(st
 				port->state = STATE_UNKNOWN;
 			}
 			output_packet(urb, p0, port->data[0], port->data[1], b);
-			break;
+			return 1;
 		case STATE_SYSEX_0:
 			port->data[0] = b;
 			port->state = STATE_SYSEX_1;
@@ -646,29 +647,49 @@ static void snd_usbmidi_transmit_byte(st
 			output_packet(urb, p0 | 0x04, port->data[0],
 				      port->data[1], b);
 			port->state = STATE_SYSEX_0;
-			break;
+			return 1;
 		}
 	}
+	return 0;
 }
 
 static void snd_usbmidi_standard_output(struct snd_usb_midi_out_endpoint *ep,
 					struct urb *urb)
 {
 	int p;
+	int start = 0;
+	int total = 0x10;
+	int max = ep->max_transfer - 4;
+
+	if (max < 0)
+		return;
+
+	while (1) {
+		int first = -1;
+		int final = -1;
 
-	/* FIXME: lower-numbered ports can starve higher-numbered ports */
-	for (p = 0; p < 0x10; ++p) {
-		struct usbmidi_out_port *port = &ep->ports[p];
-		if (!port->active)
-			continue;
-		while (urb->transfer_buffer_length + 3 < ep->max_transfer) {
+		for (p = start; p < total; ++p) {
+			struct usbmidi_out_port *port = &ep->ports[p];
 			uint8_t b;
+			if (!port->active)
+				continue;
+repeat:
 			if (snd_rawmidi_transmit(port->substream, &b, 1) != 1) {
 				port->active = 0;
-				break;
+				continue;
 			}
-			snd_usbmidi_transmit_byte(port, b, urb);
+			if (!snd_usbmidi_transmit_byte(port, b, urb))
+				goto repeat;
+			if (urb->transfer_buffer_length > max)
+				return;
+			if (first == -1)
+				first = p;
+			final = p;
 		}
+		if (final == -1)
+			return;
+		start = first;
+		total = final + 1;
 	}
 }