Re: [PATCH v4 net-next 08/15] net/sched: mqprio: allow offloading drivers to request queue count validation

[Vladimir Oltean <vladimir.oltean@nxp.com>]

Hi Claudiu,

On Mon, Jan 30, 2023 at 08:37:02PM +0200, Claudiu Manoil wrote:
> > -----Original Message-----
> > From: Vladimir Oltean <vladimir.oltean@nxp.com>
> > Sent: Monday, January 30, 2023 7:32 PM
> [...]
> > Subject: [PATCH v4 net-next 08/15] net/sched: mqprio: allow offloading drivers
> > to request queue count validation
> >
> 
> [...]
> 
> > +static int mqprio_validate_queue_counts(struct net_device *dev,
> > +					const struct tc_mqprio_qopt *qopt)
> > +{
> > +	int i, j;
> > +
> > +	for (i = 0; i < qopt->num_tc; i++) {
> > +		unsigned int last = qopt->offset[i] + qopt->count[i];
> > +
> > +		/* Verify the queue count is in tx range being equal to the
> > +		 * real_num_tx_queues indicates the last queue is in use.
> > +		 */
> > +		if (qopt->offset[i] >= dev->real_num_tx_queues ||
> > +		    !qopt->count[i] ||
> > +		    last > dev->real_num_tx_queues)
> > +			return -EINVAL;
> > +
> > +		/* Verify that the offset and counts do not overlap */
> > +		for (j = i + 1; j < qopt->num_tc; j++) {
> > +			if (last > qopt->offset[j])
> > +				return -EINVAL;
> > +		}
> > +	}
> > +
> > +	return 0;
> > +}
> > +
> 
> Not related to this series, but the above O(n^2) code snippet....
> If last[i] := offset[i] + count[i] and last[i] <= offset[i+1],
> then offset[i] + count[i] <= offset[i+1] for every i := 0, num_tc - 1.
> 
> In other words, it's enough to check that last[i] <= offset[i+1] to make
> sure there's no interval overlap, and it's O(n).

Hmm, actually you bring a good point, which I didn't notice.

It looks to me like someone had an idea but never went through implementing it.
The complexity is O(n^2) because it's actually only the overlaps that
the code is supposed to check for. It's not necessary for TXQs to be in
ascending order ("last[i] <= offset[i+1]" isn't a given).

I'm pretty sure that TXQs can also be mapped in reverse compared to the TC,
like this:

tc qdisc add dev eno0 root handle 1: mqprio num_tc 8 map 0 1 2 3 4 5 6 7 queues 1@7 1@6 1@5 1@4 1@3 1@2 1@1 1@0 hw 1

Which *should* be allowed (at least in hardware, it is), and which would
indeed justify the higher complexity validation function.

But with "hw 0", the existing code indeed doesn't allow that.

We would need this change first, targeting "net":

diff --git a/net/sched/sch_mqprio.c b/net/sched/sch_mqprio.c
index 4c68abaa289b..4f6fb05a4adc 100644
--- a/net/sched/sch_mqprio.c
+++ b/net/sched/sch_mqprio.c
@@ -101,7 +101,8 @@ static int mqprio_parse_opt(struct net_device *dev, struct tc_mqprio_qopt *qopt)
 
 		/* Verify that the offset and counts do not overlap */
 		for (j = i + 1; j < qopt->num_tc; j++) {
-			if (last > qopt->offset[j])
+			if (last > qopt->offset[j] &&
+			    last <= qopt->offset[j] + qopt->count[j])
 				return -EINVAL;
 		}
 	}

then see you in a week from now, with net-next merged with that patch.
Oh well.. :)