From: "Toke Høiland-Jørgensen" <toke@redhat.com>
To: Yibo Zhao <yiboz@codeaurora.org>
Cc: make-wifi-fast@lists.bufferbloat.net,
linux-wireless@vger.kernel.org, Felix Fietkau <nbd@nbd.name>,
Rajkumar Manoharan <rmanohar@codeaurora.org>,
Kan Yan <kyan@google.com>,
linux-wireless-owner@vger.kernel.org
Subject: Re: [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler
Date: Sat, 20 Apr 2019 22:15:55 +0100 [thread overview]
Message-ID: <87bm10ped0.fsf@toke.dk> (raw)
In-Reply-To: <76591d2924d7b6fec06d0df07247166a@codeaurora.org>
Yibo Zhao <yiboz@codeaurora.org> writes:
> On 2019-04-11 19:24, Toke Høiland-Jørgensen wrote:
>> Yibo Zhao <yiboz@codeaurora.org> writes:
>>
>>> On 2019-04-10 18:40, Toke Høiland-Jørgensen wrote:
>>>> Yibo Zhao <yiboz@codeaurora.org> writes:
>>>>
>>>>> On 2019-04-10 04:41, Toke Høiland-Jørgensen wrote:
>>>>>> Yibo Zhao <yiboz@codeaurora.org> writes:
>>>>>>
>>>>>>> On 2019-04-04 16:31, Toke Høiland-Jørgensen wrote:
>>>>>>>> Yibo Zhao <yiboz@codeaurora.org> writes:
>>>>>>>>
>>>>>>>>> On 2019-02-16 01:05, Toke Høiland-Jørgensen wrote:
>>>>>>>>>> This switches the airtime scheduler in mac80211 to use a
>>>>>>>>>> virtual
>>>>>>>>>> time-based
>>>>>>>>>> scheduler instead of the round-robin scheduler used before.
>>>>>>>>>> This
>>>>>>>>>> has
>>>>>>>>>> a
>>>>>>>>>> couple of advantages:
>>>>>>>>>>
>>>>>>>>>> - No need to sync up the round-robin scheduler in
>>>>>>>>>> firmware/hardware
>>>>>>>>>> with
>>>>>>>>>> the round-robin airtime scheduler.
>>>>>>>>>>
>>>>>>>>>> - If several stations are eligible for transmission we can
>>>>>>>>>> schedule
>>>>>>>>>> both of
>>>>>>>>>> them; no need to hard-block the scheduling rotation until the
>>>>>>>>>> head
>>>>>>>>>> of
>>>>>>>>>> the
>>>>>>>>>> queue has used up its quantum.
>>>>>>>>>>
>>>>>>>>>> - The check of whether a station is eligible for transmission
>>>>>>>>>> becomes
>>>>>>>>>> simpler (in ieee80211_txq_may_transmit()).
>>>>>>>>>>
>>>>>>>>>> The drawback is that scheduling becomes slightly more
>>>>>>>>>> expensive,
>>>>>>>>>> as
>>>>>>>>>> we
>>>>>>>>>> need
>>>>>>>>>> to maintain an rbtree of TXQs sorted by virtual time. This
>>>>>>>>>> means
>>>>>>>>>> that
>>>>>>>>>> ieee80211_register_airtime() becomes O(logN) in the number of
>>>>>>>>>> currently
>>>>>>>>>> scheduled TXQs. However, hopefully this number rarely grows too
>>>>>>>>>> big
>>>>>>>>>> (it's
>>>>>>>>>> only TXQs currently backlogged, not all associated stations),
>>>>>>>>>> so
>>>>>>>>>> it
>>>>>>>>>> shouldn't be too big of an issue.
>>>>>>>>>>
>>>>>>>>>> @@ -1831,18 +1830,32 @@ void
>>>>>>>>>> ieee80211_sta_register_airtime(struct
>>>>>>>>>> ieee80211_sta *pubsta, u8 tid,
>>>>>>>>>> {
>>>>>>>>>> struct sta_info *sta = container_of(pubsta, struct sta_info,
>>>>>>>>>> sta);
>>>>>>>>>> struct ieee80211_local *local = sta->sdata->local;
>>>>>>>>>> + struct ieee80211_txq *txq = sta->sta.txq[tid];
>>>>>>>>>> u8 ac = ieee80211_ac_from_tid(tid);
>>>>>>>>>> - u32 airtime = 0;
>>>>>>>>>> + u64 airtime = 0, weight_sum;
>>>>>>>>>> +
>>>>>>>>>> + if (!txq)
>>>>>>>>>> + return;
>>>>>>>>>>
>>>>>>>>>> if (sta->local->airtime_flags & AIRTIME_USE_TX)
>>>>>>>>>> airtime += tx_airtime;
>>>>>>>>>> if (sta->local->airtime_flags & AIRTIME_USE_RX)
>>>>>>>>>> airtime += rx_airtime;
>>>>>>>>>>
>>>>>>>>>> + /* Weights scale so the unit weight is 256 */
>>>>>>>>>> + airtime <<= 8;
>>>>>>>>>> +
>>>>>>>>>> spin_lock_bh(&local->active_txq_lock[ac]);
>>>>>>>>>> +
>>>>>>>>>> sta->airtime[ac].tx_airtime += tx_airtime;
>>>>>>>>>> sta->airtime[ac].rx_airtime += rx_airtime;
>>>>>>>>>> - sta->airtime[ac].deficit -= airtime;
>>>>>>>>>> +
>>>>>>>>>> + weight_sum = local->airtime_weight_sum[ac] ?:
>>>>>>>>>> sta->airtime_weight;
>>>>>>>>>> +
>>>>>>>>>> + local->airtime_v_t[ac] += airtime / weight_sum;
> Hi Toke,
>
> I was porting this version of ATF design to my ath10k platform and found
> my old kernel version not supporting 64bit division. I'm wondering if it
> is necessary to use u64 for airtime and weight_sum here though I can
> find a solution for it. I think u32 might be enough. For airtime,
> u32_max / 256 = 7182219 us(718 ms). As for weight_sum, u32_max / 8092 us
> = 130490, meaning we can support more than 130000 nodes with airtime
> weight 8092 us.
As Felix said, we don't really want divides in the fast path at all. And
since the divisors are constant, we should be able to just pre-compute
reciprocals and turn the whole thing into multiplications...
> Another finding was when I configured two 11ac STAs with different
> airtime weight, such as 256 and 1024 meaning ratio is 1:4, the
> throughput ratio was not roughly matching the ratio. Could you please
> share your results? I am not sure if it is due to platform difference.
Hmm, I tested them with ath9k where things seemed to work equivalently
to the DRR. Are you testing the same hardware with that? Would be a good
baseline.
I am on vacation until the end of the month, but can share my actual
test results once I get back...
-Toke
next prev parent reply other threads:[~2019-04-20 21:32 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-02-15 17:05 [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler Toke Høiland-Jørgensen
2019-02-15 19:44 ` [Make-wifi-fast] " Dave Taht
2019-03-05 15:45 ` Toke Høiland-Jørgensen
2019-03-06 23:09 ` Rajkumar Manoharan
2019-03-07 9:46 ` Toke Høiland-Jørgensen
2019-03-07 14:27 ` Felix Fietkau
2019-03-08 11:05 ` Toke Høiland-Jørgensen
2019-03-08 18:16 ` Felix Fietkau
2019-03-08 19:06 ` Toke Høiland-Jørgensen
2019-04-04 4:41 ` Yibo Zhao
2019-04-04 4:43 ` Yibo Zhao
2019-04-04 5:00 ` Yibo Zhao
2019-04-04 8:31 ` Toke Høiland-Jørgensen
2019-04-04 8:36 ` [Make-wifi-fast] " Dave Taht
2019-04-04 8:50 ` Toke Høiland-Jørgensen
2019-04-09 13:25 ` Yibo Zhao
2019-04-09 20:41 ` Toke Høiland-Jørgensen
2019-04-10 6:35 ` Yibo Zhao
2019-04-10 10:40 ` Toke Høiland-Jørgensen
2019-04-11 3:12 ` Yibo Zhao
2019-04-11 11:24 ` Toke Høiland-Jørgensen
2019-04-12 6:34 ` Yibo Zhao
2019-04-19 15:05 ` Yibo Zhao
2019-04-20 21:15 ` Toke Høiland-Jørgensen [this message]
2019-04-30 9:45 ` Yibo Zhao
2019-04-30 10:39 ` Toke Høiland-Jørgensen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87bm10ped0.fsf@toke.dk \
--to=toke@redhat.com \
--cc=kyan@google.com \
--cc=linux-wireless-owner@vger.kernel.org \
--cc=linux-wireless@vger.kernel.org \
--cc=make-wifi-fast@lists.bufferbloat.net \
--cc=nbd@nbd.name \
--cc=rmanohar@codeaurora.org \
--cc=yiboz@codeaurora.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).