Received-SPF: pass (google.com: best guess record for domain of linux-wireless-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= <toke@redhat.com>
To:     Lorenzo Bianconi <lorenzo@kernel.org>
Cc:     Johannes Berg <johannes@sipsolutions.net>,
        linux-wireless@vger.kernel.org,
        make-wifi-fast@lists.bufferbloat.net,
        John Crispin <john@phrozen.org>, Felix Fietkau <nbd@nbd.name>
Subject: Re: [PATCH RFC/RFT 4/4] mac80211: Apply Airtime-based Queue Limit (AQL) on packet dequeue
In-Reply-To: <20190920130604.GB6456@localhost.localdomain>
References: <156889576422.191202.5906619710809654631.stgit@alrua-x1> <156889576869.191202.510507546538322707.stgit@alrua-x1> <20190920120639.GA6456@localhost.localdomain> <87k1a39lgt.fsf@toke.dk> <20190920130604.GB6456@localhost.localdomain>
Date:   Fri, 20 Sep 2019 15:32:40 +0200
Message-ID: <87h8579jpj.fsf@toke.dk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Sender: linux-wireless-owner@vger.kernel.org
Precedence: bulk

Lorenzo Bianconi <lorenzo@kernel.org> writes:

>> Lorenzo Bianconi <lorenzo@kernel.org> writes:
>>=20
>> >> From: Toke H=C3=B8iland-J=C3=B8rgensen <toke@redhat.com>
>> >>=20
>> >> Some devices have deep buffers in firmware and/or hardware which prev=
ents
>> >> the FQ structure in mac80211 from effectively limiting bufferbloat on=
 the
>> >> link. For Ethernet devices we have BQL to limit the lower-level queue=
s, but
>> >> this cannot be applied to mac80211 because transmit rates can vary wi=
ldly
>> >> between packets depending on which station we are transmitting it to.
>> >>=20
>> >> To overcome this, we can use airtime-based queue limiting (AQL), wher=
e we
>> >> estimate the transmission time for each packet before dequeueing it, =
and
>> >> use that to limit the amount of data in-flight to the hardware. This =
idea
>> >> was originally implemented as part of the out-of-tree airtime fairnes=
s
>> >> patch to ath10k[0] in chromiumos.
>> >>=20
>> >> This patch ports that idea over to mac80211. The basic idea is simple
>> >> enough: Whenever we dequeue a packet from the TXQs and send it to the
>> >> driver, we estimate its airtime usage, based on the last recorded TX =
rate
>> >> of the station that packet is destined for. We keep a running per-AC =
total
>> >> of airtime queued for the whole device, and when that total climbs ab=
ove 8
>> >> ms' worth of data (corresponding to two maximum-sized aggregates), we
>> >> simply throttle the queues until it drops down again.
>> >>=20
>> >> The estimated airtime for each skb is stored in the tx_info, so we ca=
n
>> >> subtract the same amount from the running total when the skb is freed=
 or
>> >> recycled. The throttling mechanism relies on this accounting to be
>> >> accurate (i.e., that we are not freeing skbs without subtracting any
>> >> airtime they were accounted for), so we put the subtraction into
>> >> ieee80211_report_used_skb().
>> >>=20
>> >> This patch does *not* include any mechanism to wake a throttled TXQ a=
gain,
>> >> on the assumption that this will happen anyway as a side effect of wh=
atever
>> >> freed the skb (most commonly a TX completion).
>> >>=20
>> >> The throttling mechanism only kicks in if the queued airtime total go=
es
>> >> above the limit. Since mac80211 calculates the time based on the repo=
rted
>> >> last_tx_time from the driver, the whole throttling mechanism only kic=
ks in
>> >> for drivers that actually report this value. With the exception of
>> >> multicast, where we always calculate an estimated tx time on the assu=
mption
>> >> that multicast is transmitted at the lowest (6 Mbps) rate.
>> >>=20
>> >> The throttling added in this patch is in addition to any throttling a=
lready
>> >> performed by the airtime fairness mechanism, and in principle the two
>> >> mechanisms are orthogonal (and currently also uses two different sour=
ces of
>> >> airtime). In the future, we could amend this, using the airtime estim=
ates
>> >> calculated by this mechanism as a fallback input to the airtime fairn=
ess
>> >> scheduler, to enable airtime fairness even on drivers that don't have=
 a
>> >> hardware source of airtime usage for each station.
>> >>=20
>> >> [0] https://chromium-review.googlesource.com/c/chromiumos/third_party=
/kernel/+/588190/13/drivers/net/wireless-4.2/ath/ath10k/mac.c#3845
>> >>=20
>> >> Signed-off-by: Toke H=C3=B8iland-J=C3=B8rgensen <toke@redhat.com>
>> >> ---
>> >>  net/mac80211/debugfs.c     |   24 ++++++++++++++++++++++++
>> >>  net/mac80211/ieee80211_i.h |    7 +++++++
>> >>  net/mac80211/status.c      |   22 ++++++++++++++++++++++
>> >>  net/mac80211/tx.c          |   38 ++++++++++++++++++++++++++++++++++=
+++-
>> >>  4 files changed, 90 insertions(+), 1 deletion(-)
>> >
>> > Hi Toke,
>> >
>> > Thx a lot for working on this. Few comments inline.
>> >
>> > Regards,
>> > Lorenzo
>> >
>> >>=20
>> >> diff --git a/net/mac80211/debugfs.c b/net/mac80211/debugfs.c
>> >> index 568b3b276931..c846c6e7f3e3 100644
>> >> --- a/net/mac80211/debugfs.c
>> >> +++ b/net/mac80211/debugfs.c
>> >> @@ -148,6 +148,29 @@ static const struct file_operations aqm_ops =3D =
{
>> >>  =09.llseek =3D default_llseek,
>> >>  };
>> >> =20
>> >
>> > [...]
>> >
>> >> @@ -3581,8 +3591,19 @@ struct sk_buff *ieee80211_tx_dequeue(struct ie=
ee80211_hw *hw,
>> >>  =09tx.skb =3D skb;
>> >>  =09tx.sdata =3D vif_to_sdata(info->control.vif);
>> >> =20
>> >> -=09if (txq->sta)
>> >> +=09pktlen =3D skb->len + 38;
>> >> +=09if (txq->sta) {
>> >>  =09=09tx.sta =3D container_of(txq->sta, struct sta_info, sta);
>> >> +=09=09if (tx.sta->last_tx_bitrate) {
>> >> +=09=09=09airtime =3D (pktlen * 8 * 1000 *
>> >> +=09=09=09=09   tx.sta->last_tx_bitrate_reciprocal) >> IEEE80211_RECI=
PROCAL_SHIFT;
>> >> +=09=09=09airtime +=3D IEEE80211_AIRTIME_OVERHEAD;
>> >
>> > Here we are not taking into account aggregation burst size (it is done
>> > in a rough way in chromeos implementation) and tx retries. I have not
>> > carried out any tests so far but I think IEEE80211_AIRTIME_OVERHEAD
>> > will led to a significant airtime overestimation. Do you think this
>> > can be improved? (..I agree this is not a perfect world, but .. :))
>>=20
>> Hmm, yeah, looking at this again, the way I'm going this now, I should
>> probably have used the low 16-us IFS overhead for every packet.
>>=20
>> I guess we could do something similar to what the chromeos thing is
>> doing. I.e., adding a single "large" overhead value when we think the
>> packet is the first of a burst, and using the smaller value for the
>> rest.
>>=20
>> One approach could be to couple the switch to the "scheduling rounds" we
>> already have. I.e., first packet after a call to
>> ieee8021_txq_schedule_start() will get the 100-us overhead, and every
>> subsequent one will get the low one. Not sure how this will fit with
>> what the driver actually does, though, so I guess some experimentation
>> is in order.
>>=20
>> Ultimately,  I'm not sure it matters that much whether occasionally add
>> 80 us extra to the estimate. But as you say, adding 100 us to every
>> packet is probably a bit much ;)
>
> Would it be possible to use the previous tx airtime reported by the
> driver? (not sure if it is feasible). Some drivers can report airtime
> compute in hw, the issue is it can be no not linked to the given skb
> or aggregation burst, so we should take into account burst size

That's what we do for the fairness scheduler. And yeah, if the HW can
report after-the-fact airtime usage that is bound to be more accurate,
so I think we should keep using that for fairness.

But for this AQL thing, we really need it ahead of time. However, I
don't think it's as important that it is super accurate. As long as we
have a reasonable estimate I think we'll be fine. We can solve any
inaccuracies by fiddling with the limit, I think. Similar to what BQL
does; dynamically adjusting it up and down.

So for a first pass, we can just err on the side of having the limit
higher, and then iterate from there.

>> > Moreover, can this approach be affected by some interrupt coalescing
>> > implemented by the chipset?
>>=20
>> Probably? Ultimately we don't really know what exactly the chipset is
>> doing, so we're guessing here, no?
>
> Here I mean if the hw relies on a 1:n tx interrupt/packet ratio (I
> guess most driver do), it would probably affect throughput, right?
> (e.g TCP)

Yeah, this is what I alluded to above: If we set the limit too low, were
are going to kill TCP throughput. Ideally, we want the limit to be as
low as we can get it without hurting TCP (too much), but no lower. Just
doing the conversion to airtime is a way to achieve this: This will
scale the actual queue length with the achievable throughput as long as
the tx rate estimate is reasonably accurate. If needed, we can add
another layer of dynamic tuning on top using the existing BQL logic; but
I'd like to get the basic case working first...

-Toke