projects / openwrt / staging / blocktrron.git / blob
? search:


c900b255398d5c7067155dffc53ee4c3a38da8d4
[openwrt/staging/blocktrron.git] /
1 From: Felix Fietkau <nbd@nbd.name>
2 Date: Sat, 28 May 2022 16:51:51 +0200
3 Subject: [PATCH] mac80211: rework the airtime fairness implementation
4
5 The current ATF implementation has a number of issues which have shown up
6 during testing. Since it does not take into account the AQL budget of
7 pending packets, the implementation might queue up large amounts of packets
8 for a single txq until airtime gets reported after tx completion.
9 The same then happens to the next txq afterwards. While the end result could
10 still be considered fair, the bursty behavior introduces a large amount of
11 latency.
12 The current code also tries to avoid frequent re-sorting of txq entries in
13 order to avoid having to re-balance the rbtree often.
14
15 In order to fix these issues, introduce skip lists as a data structure, which
16 offer similar lookup/insert/delete times as rbtree, but avoids the need for
17 rebalacing by being probabilistic.
18 Use this to keep tx entries sorted by virtual time + pending AQL budget and
19 re-sort after each ieee80211_return_txq call.
20
21 Since multiple txqs share a single air_time struct with a virtual time value,
22 switch the active_txqs list to queue up air_time structs instead of queues.
23 This helps avoid imbalance between shared txqs by servicing them round robin.
24
25 ieee80211_next_txq now only dequeues the first element of active_txqs. To
26 make that work for non-AQL or non-ATF drivers as well, add estimated tx
27 airtime directly to air_info virtual time if either AQL or ATF is not
28 supported.
29
30 Signed-off-by: Felix Fietkau <nbd@nbd.name>
31 ---
32 create mode 100644 include/linux/skiplist.h
33
34 --- /dev/null
35 +++ b/include/linux/skiplist.h
36 @@ -0,0 +1,250 @@
37 +/* SPDX-License-Identifier: GPL-2.0-or-later */
38 +/*
39 + * A skip list is a probabilistic alternative to balanced trees. Unlike the
40 + * red-black tree, it does not require rebalancing.
41 + *
42 + * This implementation uses only unidirectional next pointers and is optimized
43 + * for use in a priority queue where elements are mostly deleted from the front
44 + * of the queue.
45 + *
46 + * When storing up to 2^n elements in a n-level skiplist. lookup and deletion
47 + * for the first element happens in O(1) time, other than that, insertion and
48 + * deletion takes O(log n) time, assuming that the number of elements for an
49 + * n-level list does not exceed 2^n.
50 + *
51 + * Usage:
52 + * DECLARE_SKIPLIST_TYPE(foo, 5) will define the data types for a 5-level list:
53 + * struct foo_list: the list data type
54 + * struct foo_node: the node data for an element in the list
55 + *
56 + * DECLARE_SKIPLIST_IMPL(foo, foo_cmp_fn)
57 + *
58 + * Adds the skip list implementation. It depends on a provided function:
59 + * int foo_cmp_fn(struct foo_list *list, struct foo_node *n1, struct foo_node *n2)
60 + * This compares two elements given by their node pointers, returning values <0
61 + * if n1 is less than n2, =0 and >0 for equal or bigger than respectively.
62 + *
63 + * This macro implements the following functions:
64 + *
65 + * void foo_list_init(struct foo_list *list)
66 + * initializes the skip list
67 + *
68 + * void foo_node_init(struct foo_node *node)
69 + * initializes a node. must be called before adding the node to the list
70 + *
71 + * struct foo_node *foo_node_next(struct foo_node *node)
72 + * gets the node directly after the provided node, or NULL if it was the last
73 + * element in the list.
74 + *
75 + * bool foo_is_queued(struct foo_node *node)
76 + * returns true if the node is on a list
77 + *
78 + * struct foo_node *foo_dequeue(struct foo_list *list)
79 + * deletes and returns the first element of the list (or returns NULL if empty)
80 + *
81 + * struct foo_node *foo_peek(struct foo_list *list)
82 + * returns the first element of the list
83 + *
84 + * void foo_insert(struct foo_list *list, struct foo_node *node)
85 + * inserts the node into the list. the node must be initialized and not on a
86 + * list already.
87 + *
88 + * void foo_delete(struct foo_list *list, struct foo_node *node)
89 + * deletes the node from the list, or does nothing if it's not on the list
90 + */
91 +#ifndef __SKIPLIST_H
92 +#define __SKIPLIST_H
93 +
94 +#include <linux/bits.h>
95 +#include <linux/minmax.h>
96 +#include <linux/bug.h>
97 +#include <linux/prandom.h>
98 +
99 +#define SKIPLIST_POISON ((void *)1)
100 +
101 +#define DECLARE_SKIPLIST_TYPE(name, levels) \
102 +struct name##_node { \
103 + struct name##_node *next[levels]; \
104 +}; \
105 +struct name##_list { \
106 + struct name##_node head; \
107 + unsigned int max_level; \
108 + unsigned int count; \
109 +};
110 +
111 +#define DECLARE_SKIPLIST_IMPL(name, cmp_fn) \
112 +static inline void \
113 +name##_list_init(struct name##_list *list) \
114 +{ \
115 + memset(list, 0, sizeof(*list)); \
116 +} \
117 +static inline void \
118 +name##_node_init(struct name##_node *node) \
119 +{ \
120 + node->next[0] = SKIPLIST_POISON; \
121 +} \
122 +static inline struct name##_node * \
123 +name##_node_next(struct name##_node *node) \
124 +{ \
125 + return node->next[0]; \
126 +} \
127 +static inline bool \
128 +name##_is_queued(struct name##_node *node) \
129 +{ \
130 + return node->next[0] != SKIPLIST_POISON; \
131 +} \
132 +static inline int \
133 +__skiplist_##name##_cmp_impl(void *head, void *n1, void *n2) \
134 +{ \
135 + return cmp_fn(head, n1, n2); \
136 +} \
137 +static inline void \
138 +__##name##_delete(struct name##_list *list) \
139 +{ \
140 + list->count--; \
141 + while (list->max_level && \
142 + !list->head.next[list->max_level]) \
143 + list->max_level--; \
144 +} \
145 +static inline struct name##_node * \
146 +name##_dequeue(struct name##_list *list) \
147 +{ \
148 + struct name##_node *ret; \
149 + unsigned int max_level = ARRAY_SIZE(list->head.next) - 1; \
150 + ret = (void *)__skiplist_dequeue((void **)&list->head, \
151 + max_level); \
152 + if (!ret) \
153 + return NULL; \
154 + __##name##_delete(list); \
155 + return ret; \
156 +} \
157 +static inline struct name##_node * \
158 +name##_peek(struct name##_list *list) \
159 +{ \
160 + return list->head.next[0]; \
161 +} \
162 +static inline void \
163 +name##_insert(struct name##_list *list, struct name##_node *node) \
164 +{ \
165 + int level = __skiplist_level(ARRAY_SIZE(list->head.next) - 1, \
166 + list->count, prandom_u32()); \
167 + level = min_t(int, level, list->max_level + 1); \
168 + __skiplist_insert((void *)&list->head, (void *)node, level, \
169 + __skiplist_##name##_cmp_impl); \
170 + if (level > list->max_level) \
171 + list->max_level = level; \
172 + list->count++; \
173 +} \
174 +static inline void \
175 +name##_delete(struct name##_list *list, struct name##_node *node) \
176 +{ \
177 + if (node->next[0] == SKIPLIST_POISON) \
178 + return; \
179 + __skiplist_delete((void *)&list->head, (void *)node, \
180 + ARRAY_SIZE(list->head.next) - 1, \
181 + __skiplist_##name##_cmp_impl); \
182 + __##name##_delete(list); \
183 +}
184 +
185 +
186 +typedef int (*__skiplist_cmp_t)(void *head, void *n1, void *n2);
187 +
188 +#define __skiplist_cmp(cmp, head, cur, node) \
189 + ({ \
190 + int cmp_val = cmp(head, cur, node); \
191 + if (!cmp_val) \
192 + cmp_val = (unsigned long)(cur) - \
193 + (unsigned long)(node); \
194 + cmp_val; \
195 + })
196 +
197 +static inline void *
198 +__skiplist_dequeue(void **list, int max_level)
199 +{
200 + void **node = list[0];
201 + unsigned int i;
202 +
203 + if (!node)
204 + return NULL;
205 +
206 + list[0] = node[0];
207 + for (i = 1; i <= max_level; i++) {
208 + if (list[i] != node)
209 + break;
210 +
211 + list[i] = node[i];
212 + }
213 + node[0] = SKIPLIST_POISON;
214 +
215 + return node;
216 +}
217 +
218 +static inline void
219 +__skiplist_insert(void **list, void **node, int level, __skiplist_cmp_t cmp)
220 +{
221 + void **head = list;
222 +
223 + if (WARN(node[0] != SKIPLIST_POISON, "Insert on already inserted or uninitialized node"))
224 + return;
225 + for (; level >= 0; level--) {
226 + while (list[level] &&
227 + __skiplist_cmp(cmp, head, list[level], node) < 0)
228 + list = list[level];
229 +
230 + node[level] = list[level];
231 + list[level] = node;
232 + }
233 +}
234 +
235 +
236 +static inline void
237 +__skiplist_delete(void **list, void **node, int max_level, __skiplist_cmp_t cmp)
238 +{
239 + void *head = list;
240 + int i;
241 +
242 + for (i = max_level; i >= 0; i--) {
243 + while (list[i] && list[i] != node &&
244 + __skiplist_cmp(cmp, head, list[i], node) <= 0)
245 + list = list[i];
246 +
247 + if (list[i] != node)
248 + continue;
249 +
250 + list[i] = node[i];
251 + }
252 + node[0] = SKIPLIST_POISON;
253 +}
254 +
255 +static inline unsigned int
256 +__skiplist_level(unsigned int max_level, unsigned int count, unsigned int seed)
257 +{
258 + unsigned int level = 0;
259 +
260 + if (max_level >= 16 && !(seed & GENMASK(15, 0))) {
261 + level += 16;
262 + seed >>= 16;
263 + }
264 +
265 + if (max_level >= 8 && !(seed & GENMASK(7, 0))) {
266 + level += 8;
267 + seed >>= 8;
268 + }
269 +
270 + if (max_level >= 4 && !(seed & GENMASK(3, 0))) {
271 + level += 4;
272 + seed >>= 4;
273 + }
274 +
275 + if (!(seed & GENMASK(1, 0))) {
276 + level += 2;
277 + seed >>= 2;
278 + }
279 +
280 + if (!(seed & BIT(0)))
281 + level++;
282 +
283 + return min(level, max_level);
284 +}
285 +
286 +#endif
287 --- a/net/mac80211/cfg.c
288 +++ b/net/mac80211/cfg.c
289 @@ -1563,7 +1563,6 @@ static void sta_apply_airtime_params(str
290 for (ac = 0; ac < IEEE80211_NUM_ACS; ac++) {
291 struct airtime_sched_info *air_sched = &local->airtime[ac];
292 struct airtime_info *air_info = &sta->airtime[ac];
293 - struct txq_info *txqi;
294 u8 tid;
295
296 spin_lock_bh(&air_sched->lock);
297 @@ -1575,10 +1574,6 @@ static void sta_apply_airtime_params(str
298
299 airtime_weight_set(air_info, params->airtime_weight);
300
301 - txqi = to_txq_info(sta->sta.txq[tid]);
302 - if (RB_EMPTY_NODE(&txqi->schedule_order))
303 - continue;
304 -
305 ieee80211_update_airtime_weight(local, air_sched,
306 0, true);
307 }
308 --- a/net/mac80211/ieee80211_i.h
309 +++ b/net/mac80211/ieee80211_i.h
310 @@ -25,7 +25,8 @@
311 #include <linux/leds.h>
312 #include <linux/idr.h>
313 #include <linux/rhashtable.h>
314 -#include <linux/rbtree.h>
315 +#include <linux/prandom.h>
316 +#include <linux/skiplist.h>
317 #include <net/ieee80211_radiotap.h>
318 #include <net/cfg80211.h>
319 #include <net/mac80211.h>
320 @@ -854,6 +855,7 @@ enum txq_info_flags {
321 IEEE80211_TXQ_AMPDU,
322 IEEE80211_TXQ_NO_AMSDU,
323 IEEE80211_TXQ_STOP_NETIF_TX,
324 + IEEE80211_TXQ_FORCE_ACTIVE,
325 };
326
327 /**
328 @@ -870,7 +872,6 @@ struct txq_info {
329 struct fq_tin tin;
330 struct codel_vars def_cvars;
331 struct codel_stats cstats;
332 - struct rb_node schedule_order;
333
334 struct sk_buff_head frags;
335 unsigned long flags;
336 @@ -1185,8 +1186,7 @@ enum mac80211_scan_state {
337 *
338 * @lock: spinlock that protects all the fields in this struct
339 * @active_txqs: rbtree of currently backlogged queues, sorted by virtual time
340 - * @schedule_pos: the current position maintained while a driver walks the tree
341 - * with ieee80211_next_txq()
342 + * @schedule_pos: last used airtime_info node while a driver walks the tree
343 * @active_list: list of struct airtime_info structs that were active within
344 * the last AIRTIME_ACTIVE_DURATION (100 ms), used to compute
345 * weight_sum
346 @@ -1207,8 +1207,8 @@ enum mac80211_scan_state {
347 */
348 struct airtime_sched_info {
349 spinlock_t lock;
350 - struct rb_root_cached active_txqs;
351 - struct rb_node *schedule_pos;
352 + struct airtime_sched_list active_txqs;
353 + struct airtime_sched_node *schedule_pos;
354 struct list_head active_list;
355 u64 last_weight_update;
356 u64 last_schedule_activity;
357 @@ -1663,6 +1663,20 @@ static inline struct airtime_info *to_ai
358 return &sdata->airtime[txq->ac];
359 }
360
361 +static inline int
362 +airtime_sched_cmp(struct airtime_sched_list *list,
363 + struct airtime_sched_node *n1, struct airtime_sched_node *n2)
364 +{
365 + struct airtime_info *a1, *a2;
366 +
367 + a1 = container_of(n1, struct airtime_info, schedule_order);
368 + a2 = container_of(n2, struct airtime_info, schedule_order);
369 +
370 + return a1->v_t_cur - a2->v_t_cur;
371 +}
372 +
373 +DECLARE_SKIPLIST_IMPL(airtime_sched, airtime_sched_cmp);
374 +
375 /* To avoid divisions in the fast path, we keep pre-computed reciprocals for
376 * airtime weight calculations. There are two different weights to keep track
377 * of: The per-station weight and the sum of weights per phy.
378 @@ -1749,6 +1763,7 @@ static inline void init_airtime_info(str
379 air_info->aql_limit_high = air_sched->aql_txq_limit_high;
380 airtime_weight_set(air_info, IEEE80211_DEFAULT_AIRTIME_WEIGHT);
381 INIT_LIST_HEAD(&air_info->list);
382 + airtime_sched_node_init(&air_info->schedule_order);
383 }
384
385 static inline int ieee80211_bssid_match(const u8 *raddr, const u8 *addr)
386 --- a/net/mac80211/main.c
387 +++ b/net/mac80211/main.c
388 @@ -709,7 +709,7 @@ struct ieee80211_hw *ieee80211_alloc_hw_
389 for (i = 0; i < IEEE80211_NUM_ACS; i++) {
390 struct airtime_sched_info *air_sched = &local->airtime[i];
391
392 - air_sched->active_txqs = RB_ROOT_CACHED;
393 + airtime_sched_list_init(&air_sched->active_txqs);
394 INIT_LIST_HEAD(&air_sched->active_list);
395 spin_lock_init(&air_sched->lock);
396 air_sched->aql_txq_limit_low = IEEE80211_DEFAULT_AQL_TXQ_LIMIT_L;
397 --- a/net/mac80211/sta_info.c
398 +++ b/net/mac80211/sta_info.c
399 @@ -1902,8 +1902,7 @@ void ieee80211_register_airtime(struct i
400 air_sched = &local->airtime[txq->ac];
401 air_info = to_airtime_info(txq);
402
403 - if (local->airtime_flags & AIRTIME_USE_TX)
404 - airtime += tx_airtime;
405 + airtime += tx_airtime;
406 if (local->airtime_flags & AIRTIME_USE_RX)
407 airtime += rx_airtime;
408
409 --- a/net/mac80211/sta_info.h
410 +++ b/net/mac80211/sta_info.h
411 @@ -135,11 +135,14 @@ enum ieee80211_agg_stop_reason {
412 #define AIRTIME_USE_TX BIT(0)
413 #define AIRTIME_USE_RX BIT(1)
414
415 +DECLARE_SKIPLIST_TYPE(airtime_sched, 5);
416
417 struct airtime_info {
418 + struct airtime_sched_node schedule_order;
419 + struct ieee80211_txq *txq[3];
420 u64 rx_airtime;
421 u64 tx_airtime;
422 - u64 v_t;
423 + u64 v_t, v_t_cur;
424 u64 last_scheduled;
425 struct list_head list;
426 atomic_t aql_tx_pending; /* Estimated airtime for frames pending */
427 @@ -147,6 +150,7 @@ struct airtime_info {
428 u32 aql_limit_high;
429 u32 weight_reciprocal;
430 u16 weight;
431 + u8 txq_idx;
432 };
433
434 void ieee80211_sta_update_pending_airtime(struct ieee80211_local *local,
435 --- a/net/mac80211/tx.c
436 +++ b/net/mac80211/tx.c
437 @@ -19,6 +19,7 @@
438 #include <linux/rcupdate.h>
439 #include <linux/export.h>
440 #include <linux/timekeeping.h>
441 +#include <linux/prandom.h>
442 #include <net/net_namespace.h>
443 #include <net/ieee80211_radiotap.h>
444 #include <net/cfg80211.h>
445 @@ -1476,11 +1477,12 @@ void ieee80211_txq_init(struct ieee80211
446 struct sta_info *sta,
447 struct txq_info *txqi, int tid)
448 {
449 + struct airtime_info *air_info;
450 +
451 fq_tin_init(&txqi->tin);
452 codel_vars_init(&txqi->def_cvars);
453 codel_stats_init(&txqi->cstats);
454 __skb_queue_head_init(&txqi->frags);
455 - RB_CLEAR_NODE(&txqi->schedule_order);
456
457 txqi->txq.vif = &sdata->vif;
458
459 @@ -1489,7 +1491,7 @@ void ieee80211_txq_init(struct ieee80211
460 txqi->txq.tid = 0;
461 txqi->txq.ac = IEEE80211_AC_BE;
462
463 - return;
464 + goto out;
465 }
466
467 if (tid == IEEE80211_NUM_TIDS) {
468 @@ -1511,6 +1513,12 @@ void ieee80211_txq_init(struct ieee80211
469 txqi->txq.sta = &sta->sta;
470 txqi->txq.tid = tid;
471 sta->sta.txq[tid] = &txqi->txq;
472 +
473 +out:
474 + air_info = to_airtime_info(&txqi->txq);
475 + air_info->txq[air_info->txq_idx++] = &txqi->txq;
476 + if (air_info->txq_idx == ARRAY_SIZE(air_info->txq))
477 + air_info->txq_idx--;
478 }
479
480 void ieee80211_txq_purge(struct ieee80211_local *local,
481 @@ -3633,6 +3641,8 @@ struct sk_buff *ieee80211_tx_dequeue(str
482 struct ieee80211_tx_data tx;
483 ieee80211_tx_result r;
484 struct ieee80211_vif *vif = txq->vif;
485 + u32 airtime;
486 + bool ampdu;
487
488 WARN_ON_ONCE(softirq_count() == 0);
489
490 @@ -3791,20 +3801,35 @@ begin:
491 encap_out:
492 IEEE80211_SKB_CB(skb)->control.vif = vif;
493
494 - if (vif &&
495 - wiphy_ext_feature_isset(local->hw.wiphy, NL80211_EXT_FEATURE_AQL)) {
496 - bool ampdu = txq->ac != IEEE80211_AC_VO;
497 - u32 airtime;
498 -
499 - airtime = ieee80211_calc_expected_tx_airtime(hw, vif, txq->sta,
500 - skb->len, ampdu);
501 - if (!airtime)
502 - airtime = IEEE80211_TX_TIME_EST_UNIT;
503 -
504 - airtime = ieee80211_info_set_tx_time_est(info, airtime);
505 - ieee80211_sta_update_pending_airtime(local, tx.sta, txq->ac,
506 - airtime, false);
507 - }
508 + if (!vif)
509 + return skb;
510 +
511 + ampdu = txq->ac != IEEE80211_AC_VO;
512 + airtime = ieee80211_calc_expected_tx_airtime(hw, vif, txq->sta,
513 + skb->len, ampdu);
514 + if (!airtime)
515 + airtime = IEEE80211_TX_TIME_EST_UNIT;
516 +
517 + /*
518 + * Tx queue scheduling always happens in airtime order and queues are
519 + * sorted by virtual time + pending AQL budget.
520 + * If AQL is not supported, pending AQL budget is always zero.
521 + * If airtime fairness is not supported, virtual time won't be directly
522 + * increased by driver tx completion.
523 + * Because of that, we register estimated tx time as airtime if either
524 + * AQL or ATF support is missing.
525 + */
526 + if (!wiphy_ext_feature_isset(local->hw.wiphy, NL80211_EXT_FEATURE_AQL) ||
527 + !wiphy_ext_feature_isset(local->hw.wiphy,
528 + NL80211_EXT_FEATURE_AIRTIME_FAIRNESS))
529 + ieee80211_register_airtime(txq, airtime, 0);
530 +
531 + if (!wiphy_ext_feature_isset(local->hw.wiphy, NL80211_EXT_FEATURE_AQL))
532 + return skb;
533 +
534 + airtime = ieee80211_info_set_tx_time_est(info, airtime);
535 + ieee80211_sta_update_pending_airtime(local, tx.sta, txq->ac,
536 + airtime, false);
537
538 return skb;
539
540 @@ -3815,85 +3840,92 @@ out:
541 }
542 EXPORT_SYMBOL(ieee80211_tx_dequeue);
543
544 +static struct ieee80211_txq *
545 +airtime_info_next_txq_idx(struct airtime_info *air_info)
546 +{
547 + air_info->txq_idx++;
548 + if (air_info->txq_idx >= ARRAY_SIZE(air_info->txq) ||
549 + !air_info->txq[air_info->txq_idx])
550 + air_info->txq_idx = 0;
551 + return air_info->txq[air_info->txq_idx];
552 +}
553 +
554 struct ieee80211_txq *ieee80211_next_txq(struct ieee80211_hw *hw, u8 ac)
555 {
556 struct ieee80211_local *local = hw_to_local(hw);
557 struct airtime_sched_info *air_sched;
558 u64 now = ktime_get_coarse_boottime_ns();
559 - struct ieee80211_txq *ret = NULL;
560 + struct airtime_sched_node *node = NULL;
561 + struct ieee80211_txq *txq;
562 struct airtime_info *air_info;
563 struct txq_info *txqi = NULL;
564 - struct rb_node *node;
565 - bool first = false;
566 + u8 txq_idx;
567
568 air_sched = &local->airtime[ac];
569 spin_lock_bh(&air_sched->lock);
570
571 - node = air_sched->schedule_pos;
572 -
573 begin:
574 - if (!node) {
575 - node = rb_first_cached(&air_sched->active_txqs);
576 - first = true;
577 - } else {
578 - node = rb_next(node);
579 - }
580 + txq = NULL;
581 + if (airtime_sched_peek(&air_sched->active_txqs) ==
582 + air_sched->schedule_pos)
583 + goto out;
584
585 + node = airtime_sched_dequeue(&air_sched->active_txqs);
586 if (!node)
587 goto out;
588
589 - txqi = container_of(node, struct txq_info, schedule_order);
590 - air_info = to_airtime_info(&txqi->txq);
591 + air_info = container_of(node, struct airtime_info, schedule_order);
592
593 - if (air_info->v_t > air_sched->v_t &&
594 - (!first || !airtime_catchup_v_t(air_sched, air_info->v_t, now)))
595 - goto out;
596 -
597 - if (!ieee80211_txq_airtime_check(hw, &txqi->txq)) {
598 - first = false;
599 + txq = airtime_info_next_txq_idx(air_info);
600 + txq_idx = air_info->txq_idx;
601 + if (!ieee80211_txq_airtime_check(hw, txq))
602 goto begin;
603 +
604 + while (1) {
605 + txqi = to_txq_info(txq);
606 + if (test_and_clear_bit(IEEE80211_TXQ_FORCE_ACTIVE, &txqi->flags))
607 + break;
608 +
609 + if (txq_has_queue(txq))
610 + break;
611 +
612 + txq = airtime_info_next_txq_idx(air_info);
613 + if (txq_idx == air_info->txq_idx)
614 + goto begin;
615 }
616
617 + if (air_info->v_t_cur > air_sched->v_t)
618 + airtime_catchup_v_t(air_sched, air_info->v_t_cur, now);
619 +
620 air_sched->schedule_pos = node;
621 air_sched->last_schedule_activity = now;
622 - ret = &txqi->txq;
623 out:
624 spin_unlock_bh(&air_sched->lock);
625 - return ret;
626 + return txq;
627 }
628 EXPORT_SYMBOL(ieee80211_next_txq);
629
630 -static void __ieee80211_insert_txq(struct rb_root_cached *root,
631 +static void __ieee80211_insert_txq(struct ieee80211_local *local,
632 + struct airtime_sched_info *air_sched,
633 struct txq_info *txqi)
634 {
635 - struct rb_node **new = &root->rb_root.rb_node;
636 - struct airtime_info *old_air, *new_air;
637 - struct rb_node *parent = NULL;
638 - struct txq_info *__txqi;
639 - bool leftmost = true;
640 -
641 - while (*new) {
642 - parent = *new;
643 - __txqi = rb_entry(parent, struct txq_info, schedule_order);
644 - old_air = to_airtime_info(&__txqi->txq);
645 - new_air = to_airtime_info(&txqi->txq);
646 + struct airtime_info *air_info = to_airtime_info(&txqi->txq);
647 + u32 aql_time = 0;
648
649 - if (new_air->v_t <= old_air->v_t) {
650 - new = &parent->rb_left;
651 - } else {
652 - new = &parent->rb_right;
653 - leftmost = false;
654 - }
655 + if (wiphy_ext_feature_isset(local->hw.wiphy, NL80211_EXT_FEATURE_AQL)) {
656 + aql_time = atomic_read(&air_info->aql_tx_pending);
657 + aql_time *= air_info->weight_reciprocal;
658 + aql_time >>= IEEE80211_RECIPROCAL_SHIFT_STA - IEEE80211_WEIGHT_SHIFT;
659 }
660
661 - rb_link_node(&txqi->schedule_order, parent, new);
662 - rb_insert_color_cached(&txqi->schedule_order, root, leftmost);
663 + airtime_sched_delete(&air_sched->active_txqs, &air_info->schedule_order);
664 + air_info->v_t_cur = air_info->v_t + aql_time;
665 + airtime_sched_insert(&air_sched->active_txqs, &air_info->schedule_order);
666 }
667
668 void ieee80211_resort_txq(struct ieee80211_hw *hw,
669 struct ieee80211_txq *txq)
670 {
671 - struct airtime_info *air_info = to_airtime_info(txq);
672 struct ieee80211_local *local = hw_to_local(hw);
673 struct txq_info *txqi = to_txq_info(txq);
674 struct airtime_sched_info *air_sched;
675 @@ -3901,41 +3933,7 @@ void ieee80211_resort_txq(struct ieee802
676 air_sched = &local->airtime[txq->ac];
677
678 lockdep_assert_held(&air_sched->lock);
679 -
680 - if (!RB_EMPTY_NODE(&txqi->schedule_order)) {
681 - struct airtime_info *a_prev = NULL, *a_next = NULL;
682 - struct txq_info *t_prev, *t_next;
683 - struct rb_node *n_prev, *n_next;
684 -
685 - /* Erasing a node can cause an expensive rebalancing operation,
686 - * so we check the previous and next nodes first and only remove
687 - * and re-insert if the current node is not already in the
688 - * correct position.
689 - */
690 - if ((n_prev = rb_prev(&txqi->schedule_order)) != NULL) {
691 - t_prev = container_of(n_prev, struct txq_info,
692 - schedule_order);
693 - a_prev = to_airtime_info(&t_prev->txq);
694 - }
695 -
696 - if ((n_next = rb_next(&txqi->schedule_order)) != NULL) {
697 - t_next = container_of(n_next, struct txq_info,
698 - schedule_order);
699 - a_next = to_airtime_info(&t_next->txq);
700 - }
701 -
702 - if ((!a_prev || a_prev->v_t <= air_info->v_t) &&
703 - (!a_next || a_next->v_t > air_info->v_t))
704 - return;
705 -
706 - if (air_sched->schedule_pos == &txqi->schedule_order)
707 - air_sched->schedule_pos = n_prev;
708 -
709 - rb_erase_cached(&txqi->schedule_order,
710 - &air_sched->active_txqs);
711 - RB_CLEAR_NODE(&txqi->schedule_order);
712 - __ieee80211_insert_txq(&air_sched->active_txqs, txqi);
713 - }
714 + __ieee80211_insert_txq(local, air_sched, txqi);
715 }
716
717 void ieee80211_update_airtime_weight(struct ieee80211_local *local,
718 @@ -3984,7 +3982,7 @@ void ieee80211_schedule_txq(struct ieee8
719 was_active = airtime_is_active(air_info, now);
720 airtime_set_active(air_sched, air_info, now);
721
722 - if (!RB_EMPTY_NODE(&txqi->schedule_order))
723 + if (airtime_sched_is_queued(&air_info->schedule_order))
724 goto out;
725
726 /* If the station has been inactive for a while, catch up its v_t so it
727 @@ -3996,7 +3994,7 @@ void ieee80211_schedule_txq(struct ieee8
728 air_info->v_t = air_sched->v_t;
729
730 ieee80211_update_airtime_weight(local, air_sched, now, !was_active);
731 - __ieee80211_insert_txq(&air_sched->active_txqs, txqi);
732 + __ieee80211_insert_txq(local, air_sched, txqi);
733
734 out:
735 spin_unlock_bh(&air_sched->lock);
736 @@ -4017,24 +4015,14 @@ static void __ieee80211_unschedule_txq(s
737
738 lockdep_assert_held(&air_sched->lock);
739
740 + airtime_sched_delete(&air_sched->active_txqs, &air_info->schedule_order);
741 if (purge) {
742 list_del_init(&air_info->list);
743 ieee80211_update_airtime_weight(local, air_sched, 0, true);
744 - }
745 -
746 - if (RB_EMPTY_NODE(&txqi->schedule_order))
747 - return;
748 -
749 - if (air_sched->schedule_pos == &txqi->schedule_order)
750 - air_sched->schedule_pos = rb_prev(&txqi->schedule_order);
751 -
752 - if (!purge)
753 + } else {
754 airtime_set_active(air_sched, air_info,
755 ktime_get_coarse_boottime_ns());
756 -
757 - rb_erase_cached(&txqi->schedule_order,
758 - &air_sched->active_txqs);
759 - RB_CLEAR_NODE(&txqi->schedule_order);
760 + }
761 }
762
763 void ieee80211_unschedule_txq(struct ieee80211_hw *hw,
764 @@ -4054,14 +4042,22 @@ void ieee80211_return_txq(struct ieee802
765 {
766 struct ieee80211_local *local = hw_to_local(hw);
767 struct txq_info *txqi = to_txq_info(txq);
768 + struct airtime_sched_info *air_sched;
769 + struct airtime_info *air_info;
770
771 - spin_lock_bh(&local->airtime[txq->ac].lock);
772 + air_sched = &local->airtime[txq->ac];
773 + air_info = to_airtime_info(&txqi->txq);
774
775 - if (!RB_EMPTY_NODE(&txqi->schedule_order) && !force &&
776 - !txq_has_queue(txq))
777 - __ieee80211_unschedule_txq(hw, txq, false);
778 + if (force)
779 + set_bit(IEEE80211_TXQ_FORCE_ACTIVE, &txqi->flags);
780
781 - spin_unlock_bh(&local->airtime[txq->ac].lock);
782 + spin_lock_bh(&air_sched->lock);
783 + if (force || (txq_has_queue(txq) &&
784 + ieee80211_txq_airtime_check(hw, &txqi->txq)))
785 + __ieee80211_insert_txq(local, air_sched, txqi);
786 + else
787 + __ieee80211_unschedule_txq(hw, txq, false);
788 + spin_unlock_bh(&air_sched->lock);
789 }
790 EXPORT_SYMBOL(ieee80211_return_txq);
791
792 @@ -4113,9 +4109,6 @@ bool ieee80211_txq_may_transmit(struct i
793 air_sched = &local->airtime[txq->ac];
794 spin_lock_bh(&air_sched->lock);
795
796 - if (RB_EMPTY_NODE(&txqi->schedule_order))
797 - goto out;
798 -
799 now = ktime_get_coarse_boottime_ns();
800
801 air_info = to_airtime_info(&txqi->txq);
802 @@ -4124,7 +4117,6 @@ bool ieee80211_txq_may_transmit(struct i
803 ret = true;
804 }
805
806 -out:
807 spin_unlock_bh(&air_sched->lock);
808 return ret;
809 }
810 @@ -4135,9 +4127,7 @@ void ieee80211_txq_schedule_start(struct
811 struct ieee80211_local *local = hw_to_local(hw);
812 struct airtime_sched_info *air_sched = &local->airtime[ac];
813
814 - spin_lock_bh(&air_sched->lock);
815 air_sched->schedule_pos = NULL;
816 - spin_unlock_bh(&air_sched->lock);
817 }
818 EXPORT_SYMBOL(ieee80211_txq_schedule_start);
819
Staging tree of David Bauer