Re: [Make-wifi-fast] [PATCHv2 1/2] mac80211: implement fair queuing per txq

From: Michal Kazior <michal.kazior@tieto.com>
To: Jonathan Morton <chromatix99@gmail.com>
Cc: Johannes Berg <johannes@sipsolutions.net>,
	make-wifi-fast@lists.bufferbloat.net,
	linux-wireless <linux-wireless@vger.kernel.org>,
	codel@lists.bufferbloat.net
Subject: Re: [Make-wifi-fast] [PATCHv2 1/2] mac80211: implement fair queuing per txq
Date: Wed, 6 Apr 2016 09:16:59 +0200	[thread overview]
Message-ID: <CA+BoTQmTviPfR-xsKB2gNa_epVJJ1JO4Ke=sKt27Xefn=OAQuw@mail.gmail.com> (raw)
In-Reply-To: <2233FCEB-7412-4F22-B262-068AFBB2FDCB@gmail.com>

On 6 April 2016 at 08:03, Jonathan Morton <chromatix99@gmail.com> wrote:
>
>> On 6 Apr, 2016, at 08:35, Michal Kazior <michal.kazior@tieto.com> wrote:
>>
>> Packets can be destined to different stations/txqs. At enqueue time I
>> do a partial hash of a packet to get an "index" which I then use to
>> address a txq_flow from per-radio list (out of 4096 of them). You can
>> end up with a situtation like this:
>> - packet A hashing to X destined to txq P which is VI
>> - packet B hashing to X destined to txq Q which is BK
>>
>> You can't use the same txq_flow for both A and B because you want to
>> maintain packets per txqs more than you want to maintain them per flow
>> (you don't want to queue BK traffic onto VI or vice versa as an
>> artifact, do you? ;). When a txq_flow doesn't have a txqi it is bound.
>> Later, if a collision happens (i.e. resulting txq_flow has non-NULL
>> txqi) the "embedded" per-txq flow is used:
>>
>>  struct txq_info {
>> -     struct sk_buff_head queue;
>> +     struct txq_flow flow; // <--- this
>>
>> When txq_flow becomes empty its txqi is reset.
>>
>> The embedded flow is otherwise treated like any other flow, i.e. it
>> can be linked to old_flows and new_flows.
>
> This smells like a very fragile and complex solution to the collision problem.  You may want to look at how Cake solves it.
>
> I use a separate pool of flows per traffic class (essentially, VO/VI/BE/BK), and there is also a set-associative hash to take care of the birthday problem.  The latter has an order-of-magnitude effect on the general flow collision rate once you get into the tens of flows, for very little CPU cost.

When a driver asks mac80211 to dequeue given txq it implies a
destination station as well. This is important because 802.11
aggregation can be performed only on groups of packets going to a
single station on a single tid.

Cake - as I understand it - doesn't really *guarantee* maintaining
this. Keep in mind you can run with hundreds of stations connected.

You don't really want to burden drivers with sorting this grouping up
themselves (and hence coerce them into introducing another level of
intermediate queues, bis).

Without the per-txq fallback flow (regardless of using fq_codel-like
scheme or cake-like scheme in mac80211) you'll need to modify
codel_dequeue() itself to compensate and re-queue/skip frames not
belonging to requested txq.

I'm not sure it's worth it for initial fair-queuing implementation.

Michał