Felix Fietkau <nbd@xxxxxxxx> writes:
> On 2019-02-15 18: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.
>>
>> Signed-off-by: Toke Høiland-Jørgensen <toke@xxxxxxxxxx>
> The approach looks good to me, but I haven't really reviewed it very
> carefully yet. Just some points that I noticed below:
Cool!
>> diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
>> index 11f058987a54..9d01fdd86e2d 100644
>> --- a/net/mac80211/sta_info.c
>> +++ b/net/mac80211/sta_info.c
>> @@ -389,7 +389,6 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
>> for (i = 0; i < IEEE80211_NUM_ACS; i++) {
>> skb_queue_head_init(&sta->ps_tx_buf[i]);
>> skb_queue_head_init(&sta->tx_filtered[i]);
>> - sta->airtime[i].deficit = sta->airtime_weight;
>> }
>>
>> for (i = 0; i < IEEE80211_NUM_TIDS; i++)
>> @@ -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;
>> + sta->airtime[ac].v_t += airtime / sta->airtime_weight;
>> + ieee80211_resort_txq(&local->hw, txq);
> These divisions could be a bit expensive, any way to change the
> calculation to avoid them?
Yeah, given that the denominators are constant from the PoV of the fast
path, we can pre-compute reciprocals and turn these divides into
multiplications. Will incorporate that...
>> --- a/net/mac80211/tx.c
>> +++ b/net/mac80211/tx.c
>> -void ieee80211_return_txq(struct ieee80211_hw *hw,
>> +static void __ieee80211_insert_txq(struct rb_root_cached *root,
>> + struct txq_info *txqi, u8 ac)
>> +{
>> + struct rb_node **new = &root->rb_root.rb_node;
>> + struct rb_node *parent = NULL;
>> + struct txq_info *__txqi;
>> + bool leftmost = true;
>> +
>> + while (*new) {
>> + parent = *new;
>> + __txqi = rb_entry(parent, struct txq_info, schedule_order);
>> +
>> + if (!txqi->txq.sta) {
>> + /* new txqi has no sta - insert to the left */
>> + new = &parent->rb_left;
>> + } else if (!__txqi->txq.sta) {
>> + /* existing txqi has no sta - insert to the right */
>> + new = &parent->rb_right;
>> + leftmost = false;
>> + } else {
>> + struct sta_info *old_sta = container_of(__txqi->txq.sta,
>> + struct sta_info,
>> + sta);
>> + struct sta_info *new_sta = container_of(txqi->txq.sta,
>> + struct sta_info,
>> + sta);
>> +
>> + if (new_sta->airtime[ac].v_t <= old_sta->airtime[ac].v_t)
>> + new = &parent->rb_left;
>> + else {
>> + new = &parent->rb_right;
>> + leftmost = false;
>> + }
>> +
>> + }
>> + }
>> +
>> + rb_link_node(&txqi->schedule_order, parent, new);
>> + rb_insert_color_cached(&txqi->schedule_order, root, leftmost);
>> +}
> I'm a bit worried about this part. Does that mean that vif txqs always
> have priority over sta txqs?
Yeah, it does. This sort of mirrors what the existing airtime scheduler
does (because VIFs don't have an airtime deficit), but because it's a
round-robin scheduler the effect is less severe as long as there are
stations able to transmit.
I guess the obvious fix is to start accounting airtime usage for the VIF
as well? We may want to do that in any case, as that would also give
users a convenient way to set policy for multicast traffic. Any
objections to this?
-Toke
