From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-f68.google.com (mail-ed1-f68.google.com [209.85.208.68]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id E40773B29E for ; Sat, 20 Apr 2019 17:16:00 -0400 (EDT) Received: by mail-ed1-f68.google.com with SMTP id d55so6917262ede.0 for ; Sat, 20 Apr 2019 14:16:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=bFHba6g5LOK2hpMjgYJcXDbjHK43XE3J6EaoLQMq7Sg=; b=kcVqTLpB/mAEhISzsheBHHNsqXn2Q6gRUVj/cvGrWRULWKfUj0qLAK75EuSRxGGzsg eVuGbCrZosium2sHtvNABsKVXgKZSbCq566mRg2S85RRphTbuZ8bkCBQo6ZcQFTTHXmn 9tALezSx4aaYh1xH0KYdLbH3zKJj2GqmxMFBX3O+91yRePtH35dGMzAY76qbTRgeVmlH FgFOLLvBqF1pwRuTPgjOSPu2n/twpdwiCsEPvV9Tnw9wabPw1quYG/GKrjCl/GYxk9El f2u2e/vb73YYYcqAM2rvpSZoszFVDjd0JvG09lItjTv6bJpCxJ9p5xCSMW3t3psR+hc+ uTqw== X-Gm-Message-State: APjAAAV7FXqVV61m9IgYvGAITOB/8RM3sOntVS+lg9Vky39rNTMU8YGj XyoCj6XskYzqsKgZHDKpvfJPuw== X-Google-Smtp-Source: APXvYqw9Up3ilL5pgWilKGFr08FrPWNcybTFrD9EsQciNZZJGBuoCtUGhlZHdjq2dSUZrOozVLgmJA== X-Received: by 2002:a50:9a02:: with SMTP id o2mr6845822edb.182.1555794959968; Sat, 20 Apr 2019 14:15:59 -0700 (PDT) Received: from alrua-x1.borgediget.toke.dk (borgediget.toke.dk. [85.204.121.218]) by smtp.gmail.com with ESMTPSA id b8sm1363381edk.16.2019.04.20.14.15.58 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 20 Apr 2019 14:15:59 -0700 (PDT) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id 3C02E1800E8; Sat, 20 Apr 2019 23:15:55 +0200 (CEST) From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= To: Yibo Zhao Cc: make-wifi-fast@lists.bufferbloat.net, linux-wireless@vger.kernel.org, Felix Fietkau , Rajkumar Manoharan , Kan Yan , linux-wireless-owner@vger.kernel.org In-Reply-To: <76591d2924d7b6fec06d0df07247166a@codeaurora.org> References: <20190215170512.31512-1-toke@redhat.com> <753b328855b85f960ceaf974194a7506@codeaurora.org> <87ftqy41ea.fsf@toke.dk> <877ec2ykrh.fsf@toke.dk> <89d32174b282006c8d4e7614657171be@codeaurora.org> <87a7gyw3cu.fsf@toke.dk> <73077ba7cda566d5eeb2395978b3524c@codeaurora.org> <877ec0u6mu.fsf@toke.dk> <76591d2924d7b6fec06d0df07247166a@codeaurora.org> X-Clacks-Overhead: GNU Terry Pratchett Date: Sat, 20 Apr 2019 22:15:55 +0100 Message-ID: <87bm10ped0.fsf@toke.dk> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Make-wifi-fast] [RFC/RFT] mac80211: Switch to a virtual time-based airtime scheduler X-BeenThere: make-wifi-fast@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 20 Apr 2019 21:16:01 -0000 Yibo Zhao writes: > On 2019-04-11 19:24, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >> Yibo Zhao writes: >>=20 >>> On 2019-04-10 18:40, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >>>> Yibo Zhao writes: >>>>=20 >>>>> On 2019-04-10 04:41, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >>>>>> Yibo Zhao writes: >>>>>>=20 >>>>>>> On 2019-04-04 16:31, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >>>>>>>> Yibo Zhao writes: >>>>>>>>=20 >>>>>>>>> On 2019-02-16 01:05, Toke H=C3=B8iland-J=C3=B8rgensen wrote: >>>>>>>>>> This switches the airtime scheduler in mac80211 to use a=20 >>>>>>>>>> virtual >>>>>>>>>> time-based >>>>>>>>>> scheduler instead of the round-robin scheduler used before.=20 >>>>>>>>>> This >>>>>>>>>> has >>>>>>>>>> a >>>>>>>>>> couple of advantages: >>>>>>>>>>=20 >>>>>>>>>> - No need to sync up the round-robin scheduler in >>>>>>>>>> firmware/hardware >>>>>>>>>> with >>>>>>>>>> the round-robin airtime scheduler. >>>>>>>>>>=20 >>>>>>>>>> - 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. >>>>>>>>>>=20 >>>>>>>>>> - The check of whether a station is eligible for transmission >>>>>>>>>> becomes >>>>>>>>>> simpler (in ieee80211_txq_may_transmit()). >>>>>>>>>>=20 >>>>>>>>>> The drawback is that scheduling becomes slightly more=20 >>>>>>>>>> expensive, >>>>>>>>>> as >>>>>>>>>> we >>>>>>>>>> need >>>>>>>>>> to maintain an rbtree of TXQs sorted by virtual time. This=20 >>>>>>>>>> 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),=20 >>>>>>>>>> so >>>>>>>>>> it >>>>>>>>>> shouldn't be too big of an issue. >>>>>>>>>>=20 >>>>>>>>>> @@ -1831,18 +1830,32 @@ void >>>>>>>>>> ieee80211_sta_register_airtime(struct >>>>>>>>>> ieee80211_sta *pubsta, u8 tid, >>>>>>>>>> { >>>>>>>>>> struct sta_info *sta =3D container_of(pubsta, struct sta_info, >>>>>>>>>> sta); >>>>>>>>>> struct ieee80211_local *local =3D sta->sdata->local; >>>>>>>>>> + struct ieee80211_txq *txq =3D sta->sta.txq[tid]; >>>>>>>>>> u8 ac =3D ieee80211_ac_from_tid(tid); >>>>>>>>>> - u32 airtime =3D 0; >>>>>>>>>> + u64 airtime =3D 0, weight_sum; >>>>>>>>>> + >>>>>>>>>> + if (!txq) >>>>>>>>>> + return; >>>>>>>>>>=20 >>>>>>>>>> if (sta->local->airtime_flags & AIRTIME_USE_TX) >>>>>>>>>> airtime +=3D tx_airtime; >>>>>>>>>> if (sta->local->airtime_flags & AIRTIME_USE_RX) >>>>>>>>>> airtime +=3D rx_airtime; >>>>>>>>>>=20 >>>>>>>>>> + /* Weights scale so the unit weight is 256 */ >>>>>>>>>> + airtime <<=3D 8; >>>>>>>>>> + >>>>>>>>>> spin_lock_bh(&local->active_txq_lock[ac]); >>>>>>>>>> + >>>>>>>>>> sta->airtime[ac].tx_airtime +=3D tx_airtime; >>>>>>>>>> sta->airtime[ac].rx_airtime +=3D rx_airtime; >>>>>>>>>> - sta->airtime[ac].deficit -=3D airtime; >>>>>>>>>> + >>>>>>>>>> + weight_sum =3D local->airtime_weight_sum[ac] ?: >>>>>>>>>> sta->airtime_weight; >>>>>>>>>> + >>>>>>>>>> + local->airtime_v_t[ac] +=3D airtime / weight_sum; > Hi Toke, > > I was porting this version of ATF design to my ath10k platform and found= =20 > my old kernel version not supporting 64bit division. I'm wondering if it= =20 > is necessary to use u64 for airtime and weight_sum here though I can=20 > find a solution for it. I think u32 might be enough. For airtime,=20 > u32_max / 256 =3D 7182219 us(718 ms). As for weight_sum, u32_max / 8092 u= s=20 > =3D 130490, meaning we can support more than 130000 nodes with airtime=20 > 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