From mboxrd@z Thu Jan 1 00:00:00 1970 Return-path: Received: from smtp.codeaurora.org ([198.145.29.96]) by bombadil.infradead.org with esmtps (Exim 4.92.2 #3 (Red Hat Linux)) id 1iBEQG-00008i-A1 for ath10k@lists.infradead.org; Fri, 20 Sep 2019 08:37:49 +0000 MIME-Version: 1.0 Date: Fri, 20 Sep 2019 16:37:45 +0800 From: Yibo Zhao Subject: Re: [PATCH 1/4] mac80211: Switch to a virtual time-based airtime scheduler In-Reply-To: <87ftkuip9f.fsf@toke.dk> References: <1568639388-27291-1-git-send-email-yiboz@codeaurora.org> <87ftkuip9f.fsf@toke.dk> Message-ID: <741a71abebf0ceecb2fbe440ae1c2750@codeaurora.org> List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Transfer-Encoding: base64 Content-Type: text/plain; charset="utf-8"; Format="flowed" Sender: "ath10k" Errors-To: ath10k-bounces+kvalo=adurom.com@lists.infradead.org To: =?UTF-8?Q?Toke_H=C3=B8iland-J=C3=B8rgensen?= Cc: linux-wireless@vger.kernel.org, ath10k@lists.infradead.org T24gMjAxOS0wOS0xOCAwNTozMSwgVG9rZSBIw7hpbGFuZC1Kw7hyZ2Vuc2VuIHdyb3RlOgo+IFlp Ym8gWmhhbyA8eWlib3pAY29kZWF1cm9yYS5vcmc+IHdyaXRlczoKPiAKPj4gRnJvbTogVG9rZSBI w7hpbGFuZC1Kw7hyZ2Vuc2VuIDx0b2tlQHJlZGhhdC5jb20+Cj4+IAo+PiBUaGlzIHN3aXRjaGVz IHRoZSBhaXJ0aW1lIHNjaGVkdWxlciBpbiBtYWM4MDIxMSB0byB1c2UgYSB2aXJ0dWFsIAo+PiB0 aW1lLWJhc2VkCj4+IHNjaGVkdWxlciBpbnN0ZWFkIG9mIHRoZSByb3VuZC1yb2JpbiBzY2hlZHVs ZXIgdXNlZCBiZWZvcmUuIFRoaXMgaGFzIGEKPj4gY291cGxlIG9mIGFkdmFudGFnZXM6Cj4+IAo+ PiAtIE5vIG5lZWQgdG8gc3luYyB1cCB0aGUgcm91bmQtcm9iaW4gc2NoZWR1bGVyIGluIGZpcm13 YXJlL2hhcmR3YXJlIAo+PiB3aXRoCj4+ICAgdGhlIHJvdW5kLXJvYmluIGFpcnRpbWUgc2NoZWR1 bGVyLgo+PiAKPj4gLSBJZiBzZXZlcmFsIHN0YXRpb25zIGFyZSBlbGlnaWJsZSBmb3IgdHJhbnNt aXNzaW9uIHdlIGNhbiBzY2hlZHVsZSAKPj4gYm90aCBvZgo+PiAgIHRoZW07IG5vIG5lZWQgdG8g aGFyZC1ibG9jayB0aGUgc2NoZWR1bGluZyByb3RhdGlvbiB1bnRpbCB0aGUgaGVhZCAKPj4gb2Yg dGhlCj4+ICAgcXVldWUgaGFzIHVzZWQgdXAgaXRzIHF1YW50dW0uCj4+IAo+PiAtIFRoZSBjaGVj ayBvZiB3aGV0aGVyIGEgc3RhdGlvbiBpcyBlbGlnaWJsZSBmb3IgdHJhbnNtaXNzaW9uIGJlY29t ZXMKPj4gICBzaW1wbGVyIChpbiBpZWVlODAyMTFfdHhxX21heV90cmFuc21pdCgpKS4KPj4gCj4+ IFRoZSBkcmF3YmFjayBpcyB0aGF0IHNjaGVkdWxpbmcgYmVjb21lcyBzbGlnaHRseSBtb3JlIGV4 cGVuc2l2ZSwgYXMgd2UgCj4+IG5lZWQKPj4gdG8gbWFpbnRhaW4gYW4gcmJ0cmVlIG9mIFRYUXMg c29ydGVkIGJ5IHZpcnR1YWwgdGltZS4gVGhpcyBtZWFucyB0aGF0Cj4+IGllZWU4MDIxMV9yZWdp c3Rlcl9haXJ0aW1lKCkgYmVjb21lcyBPKGxvZ04pIGluIHRoZSBudW1iZXIgb2YgCj4+IGN1cnJl bnRseQo+PiBzY2hlZHVsZWQgVFhRcy4gSG93ZXZlciwgaG9wZWZ1bGx5IHRoaXMgbnVtYmVyIHJh cmVseSBncm93cyB0b28gYmlnIAo+PiAoaXQncwo+PiBvbmx5IFRYUXMgY3VycmVudGx5IGJhY2ts b2dnZWQsIG5vdCBhbGwgYXNzb2NpYXRlZCBzdGF0aW9ucyksIHNvIGl0Cj4+IHNob3VsZG4ndCBi ZSB0b28gYmlnIG9mIGFuIGlzc3VlLgo+PiAKPj4gU2lnbmVkLW9mZi1ieTogVG9rZSBIw7hpbGFu ZC1Kw7hyZ2Vuc2VuIDx0b2tlQHJlZGhhdC5jb20+Cj4gCj4gSSdsbCBub3RlIHRoYXQgdGhpcyBw YXRjaCBzdGlsbCBoYXMgdGhlIHR3byBpc3N1ZXMgdGhhdCBGZWxpeCBwb2ludGVkCj4gb3V0IHdo ZW4gSSBwb3N0ZWQgdGhlIFJGQyB2ZXJzaW9uLiBOYW1lbHk6Cj4gCj4gLSBUaGUgdXNlIG9mIGRp dmlzaW9ucyBpbiB0aGUgZmFzdCBwYXRoLiBJIGd1ZXNzIEkgbmVlZCB0byBnbyB3cml0ZSAKPiBz b21lCj4gICByZWNpcHJvY2FsLWNhbGN1bGF0aW9uIGNvZGUsIHNpbmNlIHRoYXQgaXMgYWxzbyBh biBpc3N1ZSB3aXRoIHRoZSBBUUwKPiAgIHBhdGNoZXMgSSBsaW5rZWQgdG8gYmVmb3JlLgo+IAo+ IC0gVGhlIGZhY3QgdGhhdCB3ZSBkb24ndCBjb3VudCB0aGUgYWlydGltZSB1c2FnZSBvZiBtdWx0 aWNhc3QgdHJhZmZpYywKPiAgIHdoaWNoIHdpdGggdGhpcyBzZXJpZXMgbWVhbnMgdGhhdCB0aGUg dmlmIFRYUSB3aWxsIGdldCBwcmlvcml0eSBvdmVyCj4gICB0aGUgb3RoZXJzLiBJIHRoaW5rIHdl IGFncmVlZCB0byBmaXggdGhpcyBieSBqdXN0IGFkZGluZyBhbiBhaXJ0aW1lCj4gICB2X3QgdG8g dGhlIHZpZiBhcyB3ZWxsIGFuZCB1c2UgdGhhdCBmb3Igc2NoZWR1bGluZyB0aGUgVFhRLiBEb2Vz Cj4gICBhdGgxMGsgcmVwb3J0IGFpcnRpbWUgdXNhZ2UgZm9yIG11bHRpY2FzdCBhcyB3ZWxsLCBv ciBvbmx5IGZvcgo+ICAgc3RhdGlvbnM/Cj4gCj4gCkkgcmVtZW1iZXIgd2UgaGF2ZSBGZWxpeCcg cGF0Y2hlcyByZWR1Y2luZyB0aGUgdGltZSB0aGUgbG9jayBpcyBoZWxkIGluIAptYWM4MDIxMSBm b3IgRFJSLCBkbyB3ZSBuZWVkIHRvIGludGVncmF0ZSBpdCBpbnRvIHRoaXMgdmVyc2lvbu+8nwo+ IC1Ub2tlCgotLSAKWWlibwoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX18KYXRoMTBrIG1haWxpbmcgbGlzdAphdGgxMGtAbGlzdHMuaW5mcmFkZWFkLm9yZwpo dHRwOi8vbGlzdHMuaW5mcmFkZWFkLm9yZy9tYWlsbWFuL2xpc3RpbmZvL2F0aDEwawo= From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.5 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE, SPF_PASS,URIBL_BLOCKED autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 688DEC49ED7 for ; Fri, 20 Sep 2019 08:37:48 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 37E77207E0 for ; Fri, 20 Sep 2019 08:37:48 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="key not found in DNS" (0-bit key) header.d=codeaurora.org header.i=@codeaurora.org header.b="WL/EEfu0"; dkim=fail reason="key not found in DNS" (0-bit key) header.d=codeaurora.org header.i=@codeaurora.org header.b="JCV/p9tA" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2405234AbfITIhr (ORCPT ); Fri, 20 Sep 2019 04:37:47 -0400 Received: from smtp.codeaurora.org ([198.145.29.96]:60526 "EHLO smtp.codeaurora.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2404933AbfITIhr (ORCPT ); Fri, 20 Sep 2019 04:37:47 -0400 Received: by smtp.codeaurora.org (Postfix, from userid 1000) id 09011613A3; Fri, 20 Sep 2019 08:37:46 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=codeaurora.org; s=default; t=1568968666; bh=Z4dsZ3wKgL3qMslROGOTlPWRLuujF5cMmxJyeuRYXLo=; h=Date:From:To:Cc:Subject:In-Reply-To:References:From; b=WL/EEfu0ybiDIonKXjBQtwp7erDFShDQSeFcrdcf/eqyW1kB8m/dPPOa7uEpjZuhZ XaHAVffqhHn7rTU/IofX4mR5XlvDlf6oGu+Pv4ghJLkTN6kKw0l6ElrIx4G9G51AG1 8lz/aJrn1wGHm+pzXfUGIyt68o2rJo0WkNnYfNrc= Received: from mail.codeaurora.org (localhost.localdomain [127.0.0.1]) by smtp.codeaurora.org (Postfix) with ESMTP id 9894460850; Fri, 20 Sep 2019 08:37:45 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=codeaurora.org; s=default; t=1568968665; bh=Z4dsZ3wKgL3qMslROGOTlPWRLuujF5cMmxJyeuRYXLo=; h=Date:From:To:Cc:Subject:In-Reply-To:References:From; b=JCV/p9tANUS4tkc5fW2LbK6Va+e06oPX+vU7gB2UQESqUFaKJG6nJ9uFbf5rJW1ql c8zb4rphleEK+BuJe4Csy95DbaZbfwaTK8NvxHDN2n47M4JgO+EvDGrwRm8q2UJeUF 66/KDydrVmPDqd8UDpHArbYEoETMIKC/YwWLlSCE= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Date: Fri, 20 Sep 2019 16:37:45 +0800 From: Yibo Zhao To: =?UTF-8?Q?Toke_H=C3=B8iland-J=C3=B8rgensen?= Cc: ath10k@lists.infradead.org, linux-wireless@vger.kernel.org Subject: Re: [PATCH 1/4] mac80211: Switch to a virtual time-based airtime scheduler In-Reply-To: <87ftkuip9f.fsf@toke.dk> References: <1568639388-27291-1-git-send-email-yiboz@codeaurora.org> <87ftkuip9f.fsf@toke.dk> Message-ID: <741a71abebf0ceecb2fbe440ae1c2750@codeaurora.org> X-Sender: yiboz@codeaurora.org User-Agent: Roundcube Webmail/1.2.5 Sender: linux-wireless-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-wireless@vger.kernel.org On 2019-09-18 05:31, Toke Høiland-Jørgensen wrote: > Yibo Zhao writes: > >> From: Toke Høiland-Jørgensen >> >> 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. >> >> Signed-off-by: Toke Høiland-Jørgensen > > I'll note that this patch still has the two issues that Felix pointed > out when I posted the RFC version. Namely: > > - The use of divisions in the fast path. I guess I need to go write > some > reciprocal-calculation code, since that is also an issue with the AQL > patches I linked to before. > > - The fact that we don't count the airtime usage of multicast traffic, > which with this series means that the vif TXQ will get priority over > the others. I think we agreed to fix this by just adding an airtime > v_t to the vif as well and use that for scheduling the TXQ. Does > ath10k report airtime usage for multicast as well, or only for > stations? > > I remember we have Felix' patches reducing the time the lock is held in mac80211 for DRR, do we need to integrate it into this version？ > -Toke -- Yibo