From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-f66.google.com (mail-ed1-f66.google.com [209.85.208.66]) (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 E61173CB36 for ; Thu, 4 Apr 2019 04:50:19 -0400 (EDT) Received: by mail-ed1-f66.google.com with SMTP id d1so1391521edd.13 for ; Thu, 04 Apr 2019 01:50:19 -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=B55VQCA4to53n+4iHqquiLi1lhb4fW5gtQM9dNM2UB0=; b=mJsCaOCCx6MtpMaQMJGWrIrm28YS/mEM0im4ebS+cD0ILYpxi0I2vUzmSRv6/x+q5p PwcihMX83Wa2MiI3SmQmohP7ITSlbVJFa5sFIujf+2BUY7kIurjzatJGedoH6dAnV5e1 v/BQZz5K9Qa76dO2/Rfg2cCqbWwI2ZRJKBZOK8P5xwqxY7igNhm2GSW+cNmEyiiuOfFU G6djdXMGBMpsowrutjYRPScg6kp5Z2Avky7tHx0jAb54sEnvWG4zII2Ox/qhbrCb52L2 1gxU8VcPOxco/l6niuAj8rCPHyQlEddAU6gAAJZ9wF+jzRqQC7rN+tixnxmK9piqHVWf D4ww== X-Gm-Message-State: APjAAAXAeNMYhPzI5wBBbd/4+cDeeX42kKWsVXPwmvguLfssgc7B+V6E oii9uKHM1CyxOpvkwZi7tuyH2A== X-Google-Smtp-Source: APXvYqyAS1BerVW5gnF3DUCAW5TrA0CwuLmtZvs87tSEOKpK1YP4xYKZygIPH4NZZlerHIuHD4yluw== X-Received: by 2002:aa7:d784:: with SMTP id s4mr2984648edq.177.1554367819046; Thu, 04 Apr 2019 01:50:19 -0700 (PDT) Received: from alrua-x1.borgediget.toke.dk (alrua-x1.vpn.toke.dk. [2a00:7660:6da:10::2]) by smtp.gmail.com with ESMTPSA id b26sm3463814ejv.21.2019.04.04.01.50.18 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Thu, 04 Apr 2019 01:50:18 -0700 (PDT) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id EDEB21804A5; Thu, 4 Apr 2019 10:50:17 +0200 (CEST) From: Toke =?utf-8?Q?H=C3=B8iland-J=C3=B8rgensen?= To: Dave Taht Cc: Yibo Zhao , Kan Yan , Rajkumar Manoharan , linux-wireless-owner@vger.kernel.org, Make-Wifi-fast , linux-wireless , Felix Fietkau In-Reply-To: References: <20190215170512.31512-1-toke@redhat.com> <753b328855b85f960ceaf974194a7506@codeaurora.org> <87ftqy41ea.fsf@toke.dk> X-Clacks-Overhead: GNU Terry Pratchett Date: Thu, 04 Apr 2019 10:50:17 +0200 Message-ID: <87a7h640ja.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: Thu, 04 Apr 2019 08:50:20 -0000 Dave Taht writes: > On Thu, Apr 4, 2019 at 10:31 AM Toke H=C3=B8iland-J=C3=B8rgensen wrote: >> >> Yibo Zhao writes: >> >> > On 2019-02-16 01:05, Toke H=C3=B8iland-J=C3=B8rgensen 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 current= ly >> >> 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 =3D container_of(pubsta, struct sta_info, s= ta); >> >> 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; >> >> >> >> if (sta->local->airtime_flags & AIRTIME_USE_TX) >> >> airtime +=3D tx_airtime; >> >> if (sta->local->airtime_flags & AIRTIME_USE_RX) >> >> airtime +=3D rx_airtime; >> >> >> >> + /* 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_wei= ght; >> >> + >> >> + local->airtime_v_t[ac] +=3D airtime / weight_sum; >> > Hi Toke, >> > >> > Please ignore the previous two broken emails regarding this new propos= al >> > from me. >> > >> > It looks like local->airtime_v_t acts like a Tx criteria. Only the >> > stations with less airtime than that are valid for Tx. That means there >> > are situations, like 50 clients, that some of the stations can be used >> > to Tx when putting next_txq in the loop. Am I right? >> >> I'm not sure what you mean here. Are you referring to the case where new >> stations appear with a very low (zero) airtime_v_t? That is handled when >> the station is enqueued. >> >> >> + sta->airtime[ac].v_t +=3D airtime / sta->airtime_weight; >> > Another question. Any plan for taking v_t overflow situation into >> > consideration? u64 might be enough for low throughput products but not >> > sure for high end products. Something like below for reference: >> >> The unit for the variable is time, not bytes, so it is unaffected by >> throughput. 2**64 microseconds is 584554 *years* according to my >> 'units' binary, so don't think we have to worry too much about this >> overflowing ;) > > I tend to think more in terms in ns than us. Is this metric in us > currently? Yeah, WiFi stuff generally thinks in coarser time scales than you, then; everything tends to be microseconds here (the actual time unit in the standard is 1.024 us IIRC). > I figure having stuff that at least works correctly within the solar > system is a good start, and getting coverage to 250 light years > is sufficiently forward looking: http://www.atlasoftheuniverse.com/250lys= .html Heh, yeah, not sure the WiFi MAC is appropriate for those distances ;) -Toke