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:     Johannes Berg <johannes@sipsolutions.net>,
        linux-wireless@vger.kernel.org
Cc:     Felix Fietkau <nbd@nbd.name>,
        Rajkumar Manoharan <rmanohar@codeaurora.org>,
        Kan Yan <kyan@google.com>,
        make-wifi-fast@lists.bufferbloat.net,
        Yibo Zhao <yiboz@codeaurora.org>
Subject: Re: [PATCH v5] mac80211: Switch to a virtual time-based airtime scheduler
In-Reply-To: <5bab549a72d526f4fd0f708f14b49a7af6e2c0b9.camel@sipsolutions.net>
References: <20191222172423.131033-1-toke@redhat.com> <5bab549a72d526f4fd0f708f14b49a7af6e2c0b9.camel@sipsolutions.net>
Date:   Mon, 06 Jan 2020 16:20:02 +0100
Message-ID: <87r20ck3x9.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

Johannes Berg <johannes@sipsolutions.net> writes:

> On Sun, 2019-12-22 at 18:24 +0100, Toke H=C3=B8iland-J=C3=B8rgensen wrote:
>>  Didn't have a chance to
>> do anything other than compile-test it yet, but wanted to get it out
>> before the holidays (which I almost managed, since technically my
>> holiday started two days ago)...
>
> Didn't help you much, I at least was already on vacation by then too
> :P

Yeah, well, I did say "almost". But at least it gave *me* peace of mind
over the holidays :)

>> @@ -1948,6 +1978,7 @@ void ieee80211_sta_update_pending_airtime(struct i=
eee80211_local *local,
>>  			       tx_pending, 0);
>>  }
>>=20=20
>> +
>
> nit, what's that doing here? :)

Pining for the fjords?

>> +#define IEEE80211_RECIPROCAL_DIVISOR 0x100000000ULL
>> +#define IEEE80211_RECIPROCAL_SHIFT 32
>
> Could we live with less precision and use 32-bit arithmetic only? That
> might help 32-bit systems?
>
> This is basically a 32.32 (31.32 for signed) fixed point number, right?
> So I guess I'm asking if we could live with 16.16 (or 15.16), or
> similar.

Hmm, not sure. For the per-station weights, probably; I expect that in
most cases individual station weights won't be big enough to cause
rounding. However, the weight sum is a different matter. We go above a
10% rounding error once that goes above 2^13, which is certainly not
unrealistic. The worst-case error is 50% if the weight sum happens to
land at 2^15+1.

The impact of a rounding error ends up being that a station's next
transmission is delayed longer than it should be. As long as the
rounding error is constant (i.e., the same set of stations keeps being
active), this should cancel out, I guess; but since stations tend to
cycle between being active and not, I fear it could end up impacting
fairness to a measurable degree.

So IDK; we could say we'll live with this in the interest of
performance? Or we could decide the performance hit is worth keeping
precision? Or do a middle ground thing where we use 32-bit arithmetic
for the per-station weights, but go to 64-bit for the weight sum? I
don't really have a good grip on how much of a performance impact we're
talking about here, so I'm not sure which I prefer...

> I think overall this looks good. I guess you should subject it to some
> testing since I can't.

Heh, yeah, testing is definitely needed :)

I'm hoping Yibo will take it for a spin. If not, I'll try to see if I
can get my old testbed to work; but I seem to recall there being a
hardware issue with it, and I don't have physical access anymore, so it
may be beyond rescue...

-Toke