1 // SPDX-License-Identifier: GPL-2.0-only OR BSD-2-Clause
2 /* Copyright (C) 2024 Nokia
3 *
4 * Author: Koen De Schepper <koen.de_schepper@nokia-bell-labs.com>
5 * Author: Olga Albisser <olga@albisser.org>
6 * Author: Henrik Steen <henrist@henrist.net>
7 * Author: Olivier Tilmans <olivier.tilmans@nokia.com>
8 * Author: Chia-Yu Chang <chia-yu.chang@nokia-bell-labs.com>
9 *
10 * DualPI Improved with a Square (dualpi2):
11 * - Supports congestion controls that comply with the Prague requirements
12 * in RFC9331 (e.g. TCP-Prague)
13 * - Supports coupled dual-queue with PI2 as defined in RFC9332
14 * - Supports ECN L4S-identifier (IP.ECN==0b*1)
15 *
16 * note: Although DCTCP and BBRv3 can use shallow-threshold ECN marks,
17 * they do not meet the 'Prague L4S Requirements' listed in RFC 9331
18 * Section 4, so they can only be used with DualPI2 in a datacenter
19 * context.
20 *
21 * References:
22 * - RFC9332: https://datatracker.ietf.org/doc/html/rfc9332
23 * - De Schepper, Koen, et al. "PI 2: A linearized AQM for both classic and
24 * scalable TCP." in proc. ACM CoNEXT'16, 2016.
25 */
26
27 #include <linux/errno.h>
28 #include <linux/hrtimer.h>
29 #include <linux/if_vlan.h>
30 #include <linux/kernel.h>
31 #include <linux/limits.h>
32 #include <linux/module.h>
33 #include <linux/skbuff.h>
34 #include <linux/types.h>
35
36 #include <net/gso.h>
37 #include <net/inet_ecn.h>
38 #include <net/pkt_cls.h>
39 #include <net/pkt_sched.h>
40
41 /* 32b enable to support flows with windows up to ~8.6 * 1e9 packets
42 * i.e., twice the maximal snd_cwnd.
43 * MAX_PROB must be consistent with the RNG in dualpi2_roll().
44 */
45 #define MAX_PROB U32_MAX
46
47 /* alpha/beta values exchanged over netlink are in units of 256ns */
48 #define ALPHA_BETA_SHIFT 8
49
50 /* Scaled values of alpha/beta must fit in 32b to avoid overflow in later
51 * computations. Consequently (see and dualpi2_scale_alpha_beta()), their
52 * netlink-provided values can use at most 31b, i.e. be at most (2^23)-1
53 * (~4MHz) as those are given in 1/256th. This enable to tune alpha/beta to
54 * control flows whose maximal RTTs can be in usec up to few secs.
55 */
56 #define ALPHA_BETA_MAX ((1U << 31) - 1)
57
58 /* Internal alpha/beta are in units of 64ns.
59 * This enables to use all alpha/beta values in the allowed range without loss
60 * of precision due to rounding when scaling them internally, e.g.,
61 * scale_alpha_beta(1) will not round down to 0.
62 */
63 #define ALPHA_BETA_GRANULARITY 6
64
65 #define ALPHA_BETA_SCALING (ALPHA_BETA_SHIFT - ALPHA_BETA_GRANULARITY)
66
67 /* We express the weights (wc, wl) in %, i.e., wc + wl = 100 */
68 #define MAX_WC 100
69
70 struct dualpi2_sched_data {
71 struct Qdisc *l_queue; /* The L4S Low latency queue (L-queue) */
72 struct Qdisc *sch; /* The Classic queue (C-queue) */
73
74 /* Registered tc filters */
75 struct tcf_proto __rcu *tcf_filters;
76 struct tcf_block *tcf_block;
77
78 /* PI2 parameters */
79 u64 pi2_target; /* Target delay in nanoseconds */
80 u32 pi2_tupdate; /* Timer frequency in nanoseconds */
81 u32 pi2_prob; /* Base PI probability */
82 u32 pi2_alpha; /* Gain factor for the integral rate response */
83 u32 pi2_beta; /* Gain factor for the proportional response */
84 struct hrtimer pi2_timer; /* prob update timer */
85
86 /* Step AQM (L-queue only) parameters */
87 u32 step_thresh; /* Step threshold */
88 bool step_in_packets; /* Step thresh in packets (1) or time (0) */
89
90 /* C-queue starvation protection */
91 s32 c_protection_credit; /* Credit (sign indicates which queue) */
92 s32 c_protection_init; /* Reset value of the credit */
93 u8 c_protection_wc; /* C-queue weight (between 0 and MAX_WC) */
94 u8 c_protection_wl; /* L-queue weight (MAX_WC - wc) */
95
96 /* General dualQ parameters */
97 u32 memory_limit; /* Memory limit of both queues */
98 u8 coupling_factor;/* Coupling factor (k) between both queues */
99 u8 ecn_mask; /* Mask to match packets into L-queue */
100 u32 min_qlen_step; /* Minimum queue length to apply step thresh */
101 bool drop_early; /* Drop at enqueue (1) instead of dequeue (0) */
102 bool drop_overload; /* Drop (1) on overload, or overflow (0) */
103 bool split_gso; /* Split aggregated skb (1) or leave as is (0) */
104
105 /* Statistics */
106 u64 c_head_ts; /* Enqueue timestamp of the C-queue head */
107 u64 l_head_ts; /* Enqueue timestamp of the L-queue head */
108 u64 last_qdelay; /* Q delay val at the last probability update */
109 u32 packets_in_c; /* Enqueue packet counter of the C-queue */
110 u32 packets_in_l; /* Enqueue packet counter of the L-queue */
111 u32 maxq; /* Maximum queue size of the C-queue */
112 u32 ecn_mark; /* ECN mark pkt counter due to PI probability */
113 u32 step_marks; /* ECN mark pkt counter due to step AQM */
114 u32 memory_used; /* Memory used of both queues */
115 u32 max_memory_used;/* Maximum used memory */
116
117 /* Deferred drop statistics */
118 u32 deferred_drops_cnt; /* Packets dropped */
119 u32 deferred_drops_len; /* Bytes dropped */
120 };
121
122 struct dualpi2_skb_cb {
123 u64 ts; /* Timestamp at enqueue */
124 u8 apply_step:1, /* Can we apply the step threshold */
125 classified:2, /* Packet classification results */
126 ect:2; /* Packet ECT codepoint */
127 };
128
129 enum dualpi2_classification_results {
130 DUALPI2_C_CLASSIC = 0, /* C-queue */
131 DUALPI2_C_L4S = 1, /* L-queue (scale mark/classic drop) */
132 DUALPI2_C_LLLL = 2, /* L-queue (no drops/marks) */
133 __DUALPI2_C_MAX /* Keep last*/
134 };
135
dualpi2_skb_cb(struct sk_buff * skb)136 static struct dualpi2_skb_cb *dualpi2_skb_cb(struct sk_buff *skb)
137 {
138 qdisc_cb_private_validate(skb, sizeof(struct dualpi2_skb_cb));
139 return (struct dualpi2_skb_cb *)qdisc_skb_cb(skb)->data;
140 }
141
dualpi2_sojourn_time(struct sk_buff * skb,u64 reference)142 static u64 dualpi2_sojourn_time(struct sk_buff *skb, u64 reference)
143 {
144 return reference - dualpi2_skb_cb(skb)->ts;
145 }
146
head_enqueue_time(struct Qdisc * q)147 static u64 head_enqueue_time(struct Qdisc *q)
148 {
149 struct sk_buff *skb = qdisc_peek_head(q);
150
151 return skb ? dualpi2_skb_cb(skb)->ts : 0;
152 }
153
dualpi2_scale_alpha_beta(u32 param)154 static u32 dualpi2_scale_alpha_beta(u32 param)
155 {
156 u64 tmp = ((u64)param * MAX_PROB >> ALPHA_BETA_SCALING);
157
158 do_div(tmp, NSEC_PER_SEC);
159 return tmp;
160 }
161
dualpi2_unscale_alpha_beta(u32 param)162 static u32 dualpi2_unscale_alpha_beta(u32 param)
163 {
164 u64 tmp = ((u64)param * NSEC_PER_SEC << ALPHA_BETA_SCALING);
165
166 do_div(tmp, MAX_PROB);
167 return tmp;
168 }
169
next_pi2_timeout(struct dualpi2_sched_data * q)170 static ktime_t next_pi2_timeout(struct dualpi2_sched_data *q)
171 {
172 return ktime_add_ns(ktime_get_ns(), q->pi2_tupdate);
173 }
174
skb_is_l4s(struct sk_buff * skb)175 static bool skb_is_l4s(struct sk_buff *skb)
176 {
177 return dualpi2_skb_cb(skb)->classified == DUALPI2_C_L4S;
178 }
179
skb_in_l_queue(struct sk_buff * skb)180 static bool skb_in_l_queue(struct sk_buff *skb)
181 {
182 return dualpi2_skb_cb(skb)->classified != DUALPI2_C_CLASSIC;
183 }
184
skb_apply_step(struct sk_buff * skb,struct dualpi2_sched_data * q)185 static bool skb_apply_step(struct sk_buff *skb, struct dualpi2_sched_data *q)
186 {
187 return skb_is_l4s(skb) && qdisc_qlen(q->l_queue) >= q->min_qlen_step;
188 }
189
dualpi2_mark(struct dualpi2_sched_data * q,struct sk_buff * skb)190 static bool dualpi2_mark(struct dualpi2_sched_data *q, struct sk_buff *skb)
191 {
192 if (INET_ECN_set_ce(skb)) {
193 WRITE_ONCE(q->ecn_mark, q->ecn_mark + 1);
194 return true;
195 }
196 return false;
197 }
198
dualpi2_reset_c_protection(struct dualpi2_sched_data * q)199 static void dualpi2_reset_c_protection(struct dualpi2_sched_data *q)
200 {
201 WRITE_ONCE(q->c_protection_credit, q->c_protection_init);
202 }
203
204 /* This computes the initial credit value and WRR weight for the L queue (wl)
205 * from the weight of the C queue (wc).
206 * If wl > wc, the scheduler will start with the L queue when reset.
207 */
dualpi2_calculate_c_protection(struct Qdisc * sch,struct dualpi2_sched_data * q,u32 wc)208 static void dualpi2_calculate_c_protection(struct Qdisc *sch,
209 struct dualpi2_sched_data *q, u32 wc)
210 {
211 u32 mtu = clamp_t(u32, psched_mtu(qdisc_dev(sch)), 1, 1 << 20);
212
213 q->c_protection_wc = wc;
214 q->c_protection_wl = MAX_WC - wc;
215 q->c_protection_init = (s32)mtu *
216 ((int)q->c_protection_wc - (int)q->c_protection_wl);
217 dualpi2_reset_c_protection(q);
218 }
219
dualpi2_roll(u32 prob)220 static bool dualpi2_roll(u32 prob)
221 {
222 return get_random_u32() <= prob;
223 }
224
225 /* Packets in the C-queue are subject to a marking probability pC, which is the
226 * square of the internal PI probability (i.e., have an overall lower mark/drop
227 * probability). If the qdisc is overloaded, ignore ECT values and only drop.
228 *
229 * Note that this marking scheme is also applied to L4S packets during overload.
230 * Return true if packet dropping is required in C queue
231 */
dualpi2_classic_marking(struct dualpi2_sched_data * q,struct sk_buff * skb,u32 prob,bool overload)232 static bool dualpi2_classic_marking(struct dualpi2_sched_data *q,
233 struct sk_buff *skb, u32 prob,
234 bool overload)
235 {
236 if (dualpi2_roll(prob) && dualpi2_roll(prob)) {
237 if (overload || dualpi2_skb_cb(skb)->ect == INET_ECN_NOT_ECT)
238 return true;
239 dualpi2_mark(q, skb);
240 }
241 return false;
242 }
243
244 /* Packets in the L-queue are subject to a marking probability pL given by the
245 * internal PI probability scaled by the coupling factor.
246 *
247 * On overload (i.e., @local_l_prob is >= 100%):
248 * - if the qdisc is configured to trade losses to preserve latency (i.e.,
249 * @q->drop_overload), apply classic drops first before marking.
250 * - otherwise, preserve the "no loss" property of ECN at the cost of queueing
251 * delay, eventually resulting in taildrop behavior once sch->limit is
252 * reached.
253 * Return true if packet dropping is required in L queue
254 */
dualpi2_scalable_marking(struct dualpi2_sched_data * q,struct sk_buff * skb,u64 local_l_prob,u32 prob,bool overload)255 static bool dualpi2_scalable_marking(struct dualpi2_sched_data *q,
256 struct sk_buff *skb,
257 u64 local_l_prob, u32 prob,
258 bool overload)
259 {
260 if (overload) {
261 /* Apply classic drop */
262 if (!q->drop_overload ||
263 !(dualpi2_roll(prob) && dualpi2_roll(prob)))
264 goto mark;
265 return true;
266 }
267
268 /* We can safely cut the upper 32b as overload==false */
269 if (dualpi2_roll(local_l_prob)) {
270 /* Non-ECT packets could have classified as L4S by filters. */
271 if (dualpi2_skb_cb(skb)->ect == INET_ECN_NOT_ECT)
272 return true;
273 mark:
274 dualpi2_mark(q, skb);
275 }
276 return false;
277 }
278
279 /* Decide whether a given packet must be dropped (or marked if ECT), according
280 * to the PI2 probability.
281 *
282 * Never mark/drop if we have a standing queue of less than 2 MTUs.
283 */
must_drop(struct Qdisc * sch,struct dualpi2_sched_data * q,struct sk_buff * skb)284 static bool must_drop(struct Qdisc *sch, struct dualpi2_sched_data *q,
285 struct sk_buff *skb)
286 {
287 u64 local_l_prob;
288 bool overload;
289 u32 prob;
290 u32 mtu = clamp_t(u32, psched_mtu(qdisc_dev(sch)), 1, 1 << 20);
291
292 if (sch->qstats.backlog < 2 * mtu)
293 return false;
294
295 prob = READ_ONCE(q->pi2_prob);
296 local_l_prob = (u64)prob * q->coupling_factor;
297 overload = local_l_prob > MAX_PROB;
298
299 switch (dualpi2_skb_cb(skb)->classified) {
300 case DUALPI2_C_CLASSIC:
301 return dualpi2_classic_marking(q, skb, prob, overload);
302 case DUALPI2_C_L4S:
303 return dualpi2_scalable_marking(q, skb, local_l_prob, prob,
304 overload);
305 default: /* DUALPI2_C_LLLL */
306 return false;
307 }
308 }
309
dualpi2_read_ect(struct sk_buff * skb)310 static void dualpi2_read_ect(struct sk_buff *skb)
311 {
312 struct dualpi2_skb_cb *cb = dualpi2_skb_cb(skb);
313 int wlen = skb_network_offset(skb);
314
315 switch (skb_protocol(skb, true)) {
316 case htons(ETH_P_IP):
317 wlen += sizeof(struct iphdr);
318 if (!pskb_may_pull(skb, wlen) ||
319 skb_try_make_writable(skb, wlen))
320 goto not_ecn;
321
322 cb->ect = ipv4_get_dsfield(ip_hdr(skb)) & INET_ECN_MASK;
323 break;
324 case htons(ETH_P_IPV6):
325 wlen += sizeof(struct ipv6hdr);
326 if (!pskb_may_pull(skb, wlen) ||
327 skb_try_make_writable(skb, wlen))
328 goto not_ecn;
329
330 cb->ect = ipv6_get_dsfield(ipv6_hdr(skb)) & INET_ECN_MASK;
331 break;
332 default:
333 goto not_ecn;
334 }
335 return;
336
337 not_ecn:
338 /* Non pullable/writable packets can only be dropped hence are
339 * classified as not ECT.
340 */
341 cb->ect = INET_ECN_NOT_ECT;
342 }
343
dualpi2_skb_classify(struct dualpi2_sched_data * q,struct sk_buff * skb)344 static int dualpi2_skb_classify(struct dualpi2_sched_data *q,
345 struct sk_buff *skb)
346 {
347 struct dualpi2_skb_cb *cb = dualpi2_skb_cb(skb);
348 struct tcf_result res;
349 struct tcf_proto *fl;
350 int result;
351
352 cb->classified = DUALPI2_C_CLASSIC;
353
354 dualpi2_read_ect(skb);
355 if (cb->ect & q->ecn_mask) {
356 cb->classified = DUALPI2_C_L4S;
357 return NET_XMIT_SUCCESS;
358 }
359
360 if (TC_H_MAJ(skb->priority) == q->sch->handle &&
361 TC_H_MIN(skb->priority) < __DUALPI2_C_MAX) {
362 cb->classified = TC_H_MIN(skb->priority);
363 return NET_XMIT_SUCCESS;
364 }
365
366 fl = rcu_dereference_bh(q->tcf_filters);
367 if (!fl)
368 return NET_XMIT_SUCCESS;
369
370 result = tcf_classify_qdisc(skb, fl, &res, false);
371 if (result >= 0) {
372 #ifdef CONFIG_NET_CLS_ACT
373 switch (result) {
374 case TC_ACT_STOLEN:
375 case TC_ACT_QUEUED:
376 case TC_ACT_TRAP:
377 return NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
378 case TC_ACT_SHOT:
379 return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
380 }
381 #endif
382 cb->classified = TC_H_MIN(res.classid) < __DUALPI2_C_MAX ?
383 TC_H_MIN(res.classid) : DUALPI2_C_CLASSIC;
384 }
385 return NET_XMIT_SUCCESS;
386 }
387
dualpi2_enqueue_skb(struct sk_buff * skb,struct Qdisc * sch,struct sk_buff ** to_free)388 static int dualpi2_enqueue_skb(struct sk_buff *skb, struct Qdisc *sch,
389 struct sk_buff **to_free)
390 {
391 struct dualpi2_sched_data *q = qdisc_priv(sch);
392 struct dualpi2_skb_cb *cb;
393
394 if (unlikely(qdisc_qlen(sch) >= sch->limit) ||
395 unlikely((u64)q->memory_used + skb->truesize > q->memory_limit)) {
396 qdisc_qstats_overlimit(sch);
397 if (skb_in_l_queue(skb))
398 qdisc_qstats_overlimit(q->l_queue);
399 return qdisc_drop_reason(skb, sch, to_free, QDISC_DROP_OVERLIMIT);
400 }
401
402 if (q->drop_early && must_drop(sch, q, skb)) {
403 qdisc_drop_reason(skb, sch, to_free, QDISC_DROP_CONGESTED);
404 return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
405 }
406
407 cb = dualpi2_skb_cb(skb);
408 cb->ts = ktime_get_ns();
409 WRITE_ONCE(q->memory_used, q->memory_used + skb->truesize);
410 if (q->memory_used > q->max_memory_used)
411 WRITE_ONCE(q->max_memory_used, q->memory_used);
412
413 if (qdisc_qlen(sch) > q->maxq)
414 WRITE_ONCE(q->maxq, qdisc_qlen(sch));
415
416 if (skb_in_l_queue(skb)) {
417 /* Apply step thresh if skb is L4S && L-queue len >= min_qlen */
418 dualpi2_skb_cb(skb)->apply_step = skb_apply_step(skb, q);
419
420 /* Keep the overall qdisc stats consistent */
421 qdisc_qlen_inc(sch);
422 qdisc_qstats_backlog_inc(sch, skb);
423 WRITE_ONCE(q->packets_in_l, q->packets_in_l + 1);
424 if (!q->l_head_ts)
425 WRITE_ONCE(q->l_head_ts, cb->ts);
426 return qdisc_enqueue_tail(skb, q->l_queue);
427 }
428 WRITE_ONCE(q->packets_in_c, q->packets_in_c + 1);
429 if (!q->c_head_ts)
430 WRITE_ONCE(q->c_head_ts, cb->ts);
431 return qdisc_enqueue_tail(skb, sch);
432 }
433
434 /* By default, dualpi2 will split GSO skbs into independent skbs and enqueue
435 * each of those individually. This yields the following benefits, at the
436 * expense of CPU usage:
437 * - Finer-grained AQM actions as the sub-packets of a burst no longer share the
438 * same fate (e.g., the random mark/drop probability is applied individually)
439 * - Improved precision of the starvation protection/WRR scheduler at dequeue,
440 * as the size of the dequeued packets will be smaller.
441 */
dualpi2_qdisc_enqueue(struct sk_buff * skb,struct Qdisc * sch,struct sk_buff ** to_free)442 static int dualpi2_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
443 struct sk_buff **to_free)
444 {
445 struct dualpi2_sched_data *q = qdisc_priv(sch);
446 int err;
447
448 err = dualpi2_skb_classify(q, skb);
449 if (err != NET_XMIT_SUCCESS) {
450 if (err & __NET_XMIT_BYPASS)
451 qdisc_qstats_drop(sch);
452 __qdisc_drop(skb, to_free);
453 return err;
454 }
455
456 if (q->split_gso && skb_is_gso(skb)) {
457 netdev_features_t features;
458 struct sk_buff *nskb, *next;
459 int cnt, byte_len, orig_len;
460 int err;
461
462 features = netif_skb_features(skb);
463 nskb = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
464 if (IS_ERR_OR_NULL(nskb))
465 return qdisc_drop(skb, sch, to_free);
466
467 cnt = 0;
468 byte_len = 0;
469 orig_len = qdisc_pkt_len(skb);
470 skb_list_walk_safe(nskb, nskb, next) {
471 skb_mark_not_on_list(nskb);
472
473 /* Iterate through GSO fragments of an skb:
474 * (1) Set pkt_len from the single GSO fragments
475 * (2) Copy classified and ect values of an skb
476 * (3) Enqueue fragment & set ts in dualpi2_enqueue_skb
477 */
478 qdisc_skb_cb(nskb)->pkt_len = nskb->len;
479 qdisc_skb_cb(nskb)->pkt_segs = 1;
480 dualpi2_skb_cb(nskb)->classified =
481 dualpi2_skb_cb(skb)->classified;
482 dualpi2_skb_cb(nskb)->ect = dualpi2_skb_cb(skb)->ect;
483 err = dualpi2_enqueue_skb(nskb, sch, to_free);
484
485 if (err == NET_XMIT_SUCCESS) {
486 /* Compute the backlog adjustment that needs
487 * to be propagated in the qdisc tree to reflect
488 * all new skbs successfully enqueued.
489 */
490 ++cnt;
491 byte_len += nskb->len;
492 }
493 }
494 if (cnt > 0) {
495 /* The caller will add the original skb stats to its
496 * backlog, compensate this if any nskb is enqueued.
497 */
498 qdisc_tree_reduce_backlog(sch, 1 - cnt,
499 orig_len - byte_len);
500 }
501 consume_skb(skb);
502 return cnt > 0 ? NET_XMIT_SUCCESS : err;
503 }
504 return dualpi2_enqueue_skb(skb, sch, to_free);
505 }
506
507 /* Select the queue from which the next packet can be dequeued, ensuring that
508 * neither queue can starve the other with a WRR scheduler.
509 *
510 * The sign of the WRR credit determines the next queue, while the size of
511 * the dequeued packet determines the magnitude of the WRR credit change. If
512 * either queue is empty, the WRR credit is kept unchanged.
513 *
514 * As the dequeued packet can be dropped later, the caller has to perform the
515 * qdisc_bstats_update() calls.
516 */
dequeue_packet(struct Qdisc * sch,struct dualpi2_sched_data * q,int * credit_change,u64 now)517 static struct sk_buff *dequeue_packet(struct Qdisc *sch,
518 struct dualpi2_sched_data *q,
519 int *credit_change,
520 u64 now)
521 {
522 struct sk_buff *skb = NULL;
523 int c_len;
524
525 *credit_change = 0;
526 c_len = qdisc_qlen(sch) - qdisc_qlen(q->l_queue);
527 if (qdisc_qlen(q->l_queue) && (!c_len || q->c_protection_credit <= 0)) {
528 skb = __qdisc_dequeue_head(&q->l_queue->q);
529 WRITE_ONCE(q->l_head_ts, head_enqueue_time(q->l_queue));
530 if (c_len)
531 *credit_change = q->c_protection_wc;
532 qdisc_qstats_backlog_dec(q->l_queue, skb);
533
534 /* Keep the global queue size consistent */
535 qdisc_qlen_dec(sch);
536 } else if (c_len) {
537 skb = __qdisc_dequeue_head(&sch->q);
538 WRITE_ONCE(q->c_head_ts, head_enqueue_time(sch));
539 if (qdisc_qlen(q->l_queue))
540 *credit_change = ~((s32)q->c_protection_wl) + 1;
541 } else {
542 dualpi2_reset_c_protection(q);
543 return NULL;
544 }
545 WRITE_ONCE(q->memory_used, q->memory_used - skb->truesize);
546 *credit_change *= qdisc_pkt_len(skb);
547 qdisc_qstats_backlog_dec(sch, skb);
548 return skb;
549 }
550
do_step_aqm(struct dualpi2_sched_data * q,struct sk_buff * skb,u64 now)551 static int do_step_aqm(struct dualpi2_sched_data *q, struct sk_buff *skb,
552 u64 now)
553 {
554 u64 qdelay = 0;
555
556 if (q->step_in_packets)
557 qdelay = qdisc_qlen(q->l_queue);
558 else
559 qdelay = dualpi2_sojourn_time(skb, now);
560
561 if (dualpi2_skb_cb(skb)->apply_step && qdelay > q->step_thresh) {
562 if (!dualpi2_skb_cb(skb)->ect) {
563 /* Drop this non-ECT packet */
564 return 1;
565 }
566
567 if (dualpi2_mark(q, skb))
568 WRITE_ONCE(q->step_marks, q->step_marks + 1);
569 }
570 qdisc_bstats_update(q->l_queue, skb);
571 return 0;
572 }
573
drop_and_retry(struct dualpi2_sched_data * q,struct sk_buff * skb,struct Qdisc * sch,enum qdisc_drop_reason reason)574 static void drop_and_retry(struct dualpi2_sched_data *q, struct sk_buff *skb,
575 struct Qdisc *sch, enum qdisc_drop_reason reason)
576 {
577 ++q->deferred_drops_cnt;
578 q->deferred_drops_len += qdisc_pkt_len(skb);
579 qdisc_dequeue_drop(sch, skb, reason);
580 qdisc_qstats_drop(sch);
581 }
582
__dualpi2_qdisc_dequeue(struct Qdisc * sch)583 static struct sk_buff *__dualpi2_qdisc_dequeue(struct Qdisc *sch)
584 {
585 struct dualpi2_sched_data *q = qdisc_priv(sch);
586 struct sk_buff *skb;
587 int credit_change;
588 u64 now;
589
590 now = ktime_get_ns();
591
592 while ((skb = dequeue_packet(sch, q, &credit_change, now))) {
593 if (!q->drop_early && must_drop(sch, q, skb)) {
594 drop_and_retry(q, skb, sch, QDISC_DROP_CONGESTED);
595 continue;
596 }
597
598 if (skb_in_l_queue(skb) && do_step_aqm(q, skb, now)) {
599 qdisc_qstats_drop(q->l_queue);
600 drop_and_retry(q, skb, sch, QDISC_DROP_L4S_STEP_NON_ECN);
601 continue;
602 }
603
604 WRITE_ONCE(q->c_protection_credit,
605 q->c_protection_credit + credit_change);
606 qdisc_bstats_update(sch, skb);
607 break;
608 }
609
610 return skb;
611 }
612
dualpi2_dequeue_drop(struct Qdisc * sch)613 static void dualpi2_dequeue_drop(struct Qdisc *sch)
614 {
615 struct dualpi2_sched_data *q = qdisc_priv(sch);
616
617 if (q->deferred_drops_cnt) {
618 qdisc_tree_reduce_backlog(sch, q->deferred_drops_cnt,
619 q->deferred_drops_len);
620 q->deferred_drops_cnt = 0;
621 q->deferred_drops_len = 0;
622 }
623 }
624
dualpi2_qdisc_dequeue(struct Qdisc * sch)625 static struct sk_buff *dualpi2_qdisc_dequeue(struct Qdisc *sch)
626 {
627 struct sk_buff *skb;
628
629 skb = __dualpi2_qdisc_dequeue(sch);
630
631 dualpi2_dequeue_drop(sch);
632
633 return skb;
634 }
635
dualpi2_peek(struct Qdisc * sch)636 static struct sk_buff *dualpi2_peek(struct Qdisc *sch)
637 {
638 struct sk_buff *skb = skb_peek(&sch->gso_skb);
639
640 if (!skb) {
641 skb = __dualpi2_qdisc_dequeue(sch);
642
643 if (skb) {
644 __skb_queue_head(&sch->gso_skb, skb);
645 /* it's still part of the queue */
646 qdisc_qstats_backlog_inc(sch, skb);
647 sch->q.qlen++;
648 }
649
650 dualpi2_dequeue_drop(sch);
651 }
652
653 return skb;
654 }
655
__scale_delta(u64 diff)656 static s64 __scale_delta(u64 diff)
657 {
658 do_div(diff, 1 << ALPHA_BETA_GRANULARITY);
659 return diff;
660 }
661
get_queue_delays(struct dualpi2_sched_data * q,u64 * qdelay_c,u64 * qdelay_l)662 static void get_queue_delays(struct dualpi2_sched_data *q, u64 *qdelay_c,
663 u64 *qdelay_l)
664 {
665 u64 now, qc, ql;
666
667 now = ktime_get_ns();
668 qc = READ_ONCE(q->c_head_ts);
669 ql = READ_ONCE(q->l_head_ts);
670
671 *qdelay_c = qc ? now - qc : 0;
672 *qdelay_l = ql ? now - ql : 0;
673 }
674
calculate_probability(struct Qdisc * sch)675 static u32 calculate_probability(struct Qdisc *sch)
676 {
677 struct dualpi2_sched_data *q = qdisc_priv(sch);
678 u32 new_prob;
679 u64 qdelay_c;
680 u64 qdelay_l;
681 u64 qdelay;
682 s64 delta;
683
684 get_queue_delays(q, &qdelay_c, &qdelay_l);
685 qdelay = max(qdelay_l, qdelay_c);
686
687 /* Alpha and beta take at most 32b, i.e, the delay difference would
688 * overflow for queuing delay differences > ~4.2sec.
689 */
690 delta = ((s64)qdelay - (s64)q->pi2_target) * q->pi2_alpha;
691 delta += ((s64)qdelay - (s64)q->last_qdelay) * q->pi2_beta;
692 q->last_qdelay = qdelay;
693
694 /* Bound new_prob between 0 and MAX_PROB */
695 if (delta > 0) {
696 new_prob = __scale_delta(delta) + q->pi2_prob;
697 if (new_prob < q->pi2_prob)
698 new_prob = MAX_PROB;
699 } else {
700 new_prob = q->pi2_prob - __scale_delta(~delta + 1);
701 if (new_prob > q->pi2_prob)
702 new_prob = 0;
703 }
704
705 /* If we do not drop on overload, ensure we cap the L4S probability to
706 * 100% to keep window fairness when overflowing.
707 */
708 if (!q->drop_overload)
709 return min_t(u32, new_prob, MAX_PROB / q->coupling_factor);
710 return new_prob;
711 }
712
get_memory_limit(struct Qdisc * sch,u32 limit)713 static u32 get_memory_limit(struct Qdisc *sch, u32 limit)
714 {
715 /* Apply rule of thumb, i.e., doubling the packet length,
716 * to further include per packet overhead in memory_limit.
717 */
718 u64 memlim = mul_u32_u32(limit, 2 * clamp_t(u32, psched_mtu(qdisc_dev(sch)),
719 1, 1 << 20));
720
721 if (upper_32_bits(memlim))
722 return U32_MAX;
723 else
724 return lower_32_bits(memlim);
725 }
726
convert_us_to_nsec(u32 us)727 static u32 convert_us_to_nsec(u32 us)
728 {
729 u64 ns = mul_u32_u32(us, NSEC_PER_USEC);
730
731 if (upper_32_bits(ns))
732 return U32_MAX;
733
734 return lower_32_bits(ns);
735 }
736
convert_ns_to_usec(u64 ns)737 static u32 convert_ns_to_usec(u64 ns)
738 {
739 do_div(ns, NSEC_PER_USEC);
740 if (upper_32_bits(ns))
741 return U32_MAX;
742
743 return lower_32_bits(ns);
744 }
745
dualpi2_timer(struct hrtimer * timer)746 static enum hrtimer_restart dualpi2_timer(struct hrtimer *timer)
747 {
748 struct dualpi2_sched_data *q = timer_container_of(q, timer, pi2_timer);
749 struct Qdisc *sch = q->sch;
750 spinlock_t *root_lock; /* to lock qdisc for probability calculations */
751
752 rcu_read_lock();
753 root_lock = qdisc_lock(qdisc_root_sleeping(sch));
754 spin_lock(root_lock);
755
756 WRITE_ONCE(q->pi2_prob, calculate_probability(sch));
757 hrtimer_set_expires(&q->pi2_timer, next_pi2_timeout(q));
758
759 spin_unlock(root_lock);
760 rcu_read_unlock();
761 return HRTIMER_RESTART;
762 }
763
764 static struct netlink_range_validation dualpi2_alpha_beta_range = {
765 .min = 1,
766 .max = ALPHA_BETA_MAX,
767 };
768
769 static const struct nla_policy dualpi2_policy[TCA_DUALPI2_MAX + 1] = {
770 [TCA_DUALPI2_LIMIT] = NLA_POLICY_MIN(NLA_U32, 1),
771 [TCA_DUALPI2_MEMORY_LIMIT] = NLA_POLICY_MIN(NLA_U32, 1),
772 [TCA_DUALPI2_TARGET] = { .type = NLA_U32 },
773 [TCA_DUALPI2_TUPDATE] = NLA_POLICY_MIN(NLA_U32, 1),
774 [TCA_DUALPI2_ALPHA] =
775 NLA_POLICY_FULL_RANGE(NLA_U32, &dualpi2_alpha_beta_range),
776 [TCA_DUALPI2_BETA] =
777 NLA_POLICY_FULL_RANGE(NLA_U32, &dualpi2_alpha_beta_range),
778 [TCA_DUALPI2_STEP_THRESH_PKTS] = { .type = NLA_U32 },
779 [TCA_DUALPI2_STEP_THRESH_US] = { .type = NLA_U32 },
780 [TCA_DUALPI2_MIN_QLEN_STEP] = { .type = NLA_U32 },
781 [TCA_DUALPI2_COUPLING] = NLA_POLICY_MIN(NLA_U8, 1),
782 [TCA_DUALPI2_DROP_OVERLOAD] =
783 NLA_POLICY_MAX(NLA_U8, TCA_DUALPI2_DROP_OVERLOAD_MAX),
784 [TCA_DUALPI2_DROP_EARLY] =
785 NLA_POLICY_MAX(NLA_U8, TCA_DUALPI2_DROP_EARLY_MAX),
786 [TCA_DUALPI2_C_PROTECTION] =
787 NLA_POLICY_RANGE(NLA_U8, 0, MAX_WC),
788 [TCA_DUALPI2_ECN_MASK] =
789 NLA_POLICY_RANGE(NLA_U8, TC_DUALPI2_ECN_MASK_L4S_ECT,
790 TCA_DUALPI2_ECN_MASK_MAX),
791 [TCA_DUALPI2_SPLIT_GSO] =
792 NLA_POLICY_MAX(NLA_U8, TCA_DUALPI2_SPLIT_GSO_MAX),
793 };
794
dualpi2_change(struct Qdisc * sch,struct nlattr * opt,struct netlink_ext_ack * extack)795 static int dualpi2_change(struct Qdisc *sch, struct nlattr *opt,
796 struct netlink_ext_ack *extack)
797 {
798 struct nlattr *tb[TCA_DUALPI2_MAX + 1];
799 struct dualpi2_sched_data *q;
800 int old_backlog;
801 int old_qlen;
802 int err;
803
804 if (!opt || !nla_len(opt)) {
805 NL_SET_ERR_MSG_MOD(extack, "Dualpi2 options are required");
806 return -EINVAL;
807 }
808 err = nla_parse_nested(tb, TCA_DUALPI2_MAX, opt, dualpi2_policy,
809 extack);
810 if (err < 0)
811 return err;
812 if (tb[TCA_DUALPI2_STEP_THRESH_PKTS] && tb[TCA_DUALPI2_STEP_THRESH_US]) {
813 NL_SET_ERR_MSG_MOD(extack, "multiple step thresh attributes");
814 return -EINVAL;
815 }
816
817 q = qdisc_priv(sch);
818 sch_tree_lock(sch);
819
820 if (tb[TCA_DUALPI2_LIMIT]) {
821 u32 limit = nla_get_u32(tb[TCA_DUALPI2_LIMIT]);
822
823 WRITE_ONCE(sch->limit, limit);
824 WRITE_ONCE(q->memory_limit, get_memory_limit(sch, limit));
825 }
826
827 if (tb[TCA_DUALPI2_MEMORY_LIMIT])
828 WRITE_ONCE(q->memory_limit,
829 nla_get_u32(tb[TCA_DUALPI2_MEMORY_LIMIT]));
830
831 if (tb[TCA_DUALPI2_TARGET]) {
832 u64 target = nla_get_u32(tb[TCA_DUALPI2_TARGET]);
833
834 WRITE_ONCE(q->pi2_target, target * NSEC_PER_USEC);
835 }
836
837 if (tb[TCA_DUALPI2_TUPDATE]) {
838 u64 tupdate = nla_get_u32(tb[TCA_DUALPI2_TUPDATE]);
839
840 WRITE_ONCE(q->pi2_tupdate, convert_us_to_nsec(tupdate));
841 }
842
843 if (tb[TCA_DUALPI2_ALPHA]) {
844 u32 alpha = nla_get_u32(tb[TCA_DUALPI2_ALPHA]);
845
846 WRITE_ONCE(q->pi2_alpha, dualpi2_scale_alpha_beta(alpha));
847 }
848
849 if (tb[TCA_DUALPI2_BETA]) {
850 u32 beta = nla_get_u32(tb[TCA_DUALPI2_BETA]);
851
852 WRITE_ONCE(q->pi2_beta, dualpi2_scale_alpha_beta(beta));
853 }
854
855 if (tb[TCA_DUALPI2_STEP_THRESH_PKTS]) {
856 u32 step_th = nla_get_u32(tb[TCA_DUALPI2_STEP_THRESH_PKTS]);
857
858 WRITE_ONCE(q->step_in_packets, true);
859 WRITE_ONCE(q->step_thresh, step_th);
860 } else if (tb[TCA_DUALPI2_STEP_THRESH_US]) {
861 u32 step_th = nla_get_u32(tb[TCA_DUALPI2_STEP_THRESH_US]);
862
863 WRITE_ONCE(q->step_in_packets, false);
864 WRITE_ONCE(q->step_thresh, convert_us_to_nsec(step_th));
865 }
866
867 if (tb[TCA_DUALPI2_MIN_QLEN_STEP])
868 WRITE_ONCE(q->min_qlen_step,
869 nla_get_u32(tb[TCA_DUALPI2_MIN_QLEN_STEP]));
870
871 if (tb[TCA_DUALPI2_COUPLING]) {
872 u8 coupling = nla_get_u8(tb[TCA_DUALPI2_COUPLING]);
873
874 WRITE_ONCE(q->coupling_factor, coupling);
875 }
876
877 if (tb[TCA_DUALPI2_DROP_OVERLOAD]) {
878 u8 drop_overload = nla_get_u8(tb[TCA_DUALPI2_DROP_OVERLOAD]);
879
880 WRITE_ONCE(q->drop_overload, (bool)drop_overload);
881 }
882
883 if (tb[TCA_DUALPI2_DROP_EARLY]) {
884 u8 drop_early = nla_get_u8(tb[TCA_DUALPI2_DROP_EARLY]);
885
886 WRITE_ONCE(q->drop_early, (bool)drop_early);
887 }
888
889 if (tb[TCA_DUALPI2_C_PROTECTION]) {
890 u8 wc = nla_get_u8(tb[TCA_DUALPI2_C_PROTECTION]);
891
892 dualpi2_calculate_c_protection(sch, q, wc);
893 }
894
895 if (tb[TCA_DUALPI2_ECN_MASK]) {
896 u8 ecn_mask = nla_get_u8(tb[TCA_DUALPI2_ECN_MASK]);
897
898 WRITE_ONCE(q->ecn_mask, ecn_mask);
899 }
900
901 if (tb[TCA_DUALPI2_SPLIT_GSO]) {
902 u8 split_gso = nla_get_u8(tb[TCA_DUALPI2_SPLIT_GSO]);
903
904 WRITE_ONCE(q->split_gso, (bool)split_gso);
905 }
906
907 old_qlen = qdisc_qlen(sch);
908 old_backlog = sch->qstats.backlog;
909 while (qdisc_qlen(sch) > sch->limit ||
910 q->memory_used > q->memory_limit) {
911 struct sk_buff *skb = NULL;
912
913 if (qdisc_qlen(sch) > qdisc_qlen(q->l_queue)) {
914 skb = qdisc_dequeue_internal(sch, true);
915 if (unlikely(!skb)) {
916 WARN_ON_ONCE(1);
917 break;
918 }
919 WRITE_ONCE(q->memory_used, q->memory_used - skb->truesize);
920 rtnl_qdisc_drop(skb, sch);
921 } else if (qdisc_qlen(q->l_queue)) {
922 skb = qdisc_dequeue_internal(q->l_queue, true);
923 if (unlikely(!skb)) {
924 WARN_ON_ONCE(1);
925 break;
926 }
927 /* L-queue packets are counted in both sch and
928 * l_queue on enqueue; qdisc_dequeue_internal()
929 * handled l_queue, so we further account for sch.
930 */
931 qdisc_qlen_dec(sch);
932 qdisc_qstats_backlog_dec(sch, skb);
933 WRITE_ONCE(q->memory_used, q->memory_used - skb->truesize);
934 rtnl_qdisc_drop(skb, q->l_queue);
935 qdisc_qstats_drop(sch);
936 } else {
937 WARN_ON_ONCE(1);
938 break;
939 }
940 }
941 qdisc_tree_reduce_backlog(sch, old_qlen - qdisc_qlen(sch),
942 old_backlog - sch->qstats.backlog);
943
944 sch_tree_unlock(sch);
945 return 0;
946 }
947
948 /* Default alpha/beta values give a 10dB stability margin with max_rtt=100ms. */
dualpi2_reset_default(struct Qdisc * sch)949 static void dualpi2_reset_default(struct Qdisc *sch)
950 {
951 struct dualpi2_sched_data *q = qdisc_priv(sch);
952
953 q->sch->limit = 10000; /* Max 125ms at 1Gbps */
954 q->memory_limit = get_memory_limit(sch, q->sch->limit);
955
956 q->pi2_target = 15 * NSEC_PER_MSEC;
957 q->pi2_tupdate = 16 * NSEC_PER_MSEC;
958 q->pi2_alpha = dualpi2_scale_alpha_beta(41); /* ~0.16 Hz * 256 */
959 q->pi2_beta = dualpi2_scale_alpha_beta(819); /* ~3.20 Hz * 256 */
960
961 q->step_thresh = 1 * NSEC_PER_MSEC;
962 q->step_in_packets = false;
963
964 dualpi2_calculate_c_protection(q->sch, q, 10); /* wc=10%, wl=90% */
965
966 q->ecn_mask = TC_DUALPI2_ECN_MASK_L4S_ECT; /* INET_ECN_ECT_1 */
967 q->min_qlen_step = 0; /* Always apply step mark in L-queue */
968 q->coupling_factor = 2; /* window fairness for equal RTTs */
969 q->drop_overload = TC_DUALPI2_DROP_OVERLOAD_DROP; /* Drop overload */
970 q->drop_early = TC_DUALPI2_DROP_EARLY_DROP_DEQUEUE; /* Drop dequeue */
971 q->split_gso = TC_DUALPI2_SPLIT_GSO_SPLIT_GSO; /* Split GSO */
972 }
973
dualpi2_init(struct Qdisc * sch,struct nlattr * opt,struct netlink_ext_ack * extack)974 static int dualpi2_init(struct Qdisc *sch, struct nlattr *opt,
975 struct netlink_ext_ack *extack)
976 {
977 struct dualpi2_sched_data *q = qdisc_priv(sch);
978 int err;
979
980 sch->flags |= TCQ_F_DEQUEUE_DROPS;
981 hrtimer_setup(&q->pi2_timer, dualpi2_timer, CLOCK_MONOTONIC,
982 HRTIMER_MODE_ABS_PINNED_SOFT);
983
984 q->l_queue = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
985 TC_H_MAKE(sch->handle, 1), extack);
986 if (!q->l_queue)
987 return -ENOMEM;
988
989 err = tcf_block_get(&q->tcf_block, &q->tcf_filters, sch, extack);
990 if (err)
991 return err;
992
993 q->sch = sch;
994 dualpi2_reset_default(sch);
995
996 if (opt && nla_len(opt)) {
997 err = dualpi2_change(sch, opt, extack);
998
999 if (err)
1000 return err;
1001 }
1002
1003 hrtimer_start(&q->pi2_timer, next_pi2_timeout(q),
1004 HRTIMER_MODE_ABS_PINNED_SOFT);
1005 return 0;
1006 }
1007
dualpi2_dump(struct Qdisc * sch,struct sk_buff * skb)1008 static int dualpi2_dump(struct Qdisc *sch, struct sk_buff *skb)
1009 {
1010 struct dualpi2_sched_data *q = qdisc_priv(sch);
1011 struct nlattr *opts;
1012 bool step_in_pkts;
1013 u32 step_th;
1014
1015 step_in_pkts = READ_ONCE(q->step_in_packets);
1016 step_th = READ_ONCE(q->step_thresh);
1017
1018 opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
1019 if (!opts)
1020 goto nla_put_failure;
1021
1022 if (step_in_pkts &&
1023 (nla_put_u32(skb, TCA_DUALPI2_LIMIT, READ_ONCE(sch->limit)) ||
1024 nla_put_u32(skb, TCA_DUALPI2_MEMORY_LIMIT,
1025 READ_ONCE(q->memory_limit)) ||
1026 nla_put_u32(skb, TCA_DUALPI2_TARGET,
1027 convert_ns_to_usec(READ_ONCE(q->pi2_target))) ||
1028 nla_put_u32(skb, TCA_DUALPI2_TUPDATE,
1029 convert_ns_to_usec(READ_ONCE(q->pi2_tupdate))) ||
1030 nla_put_u32(skb, TCA_DUALPI2_ALPHA,
1031 dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_alpha))) ||
1032 nla_put_u32(skb, TCA_DUALPI2_BETA,
1033 dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_beta))) ||
1034 nla_put_u32(skb, TCA_DUALPI2_STEP_THRESH_PKTS, step_th) ||
1035 nla_put_u32(skb, TCA_DUALPI2_MIN_QLEN_STEP,
1036 READ_ONCE(q->min_qlen_step)) ||
1037 nla_put_u8(skb, TCA_DUALPI2_COUPLING,
1038 READ_ONCE(q->coupling_factor)) ||
1039 nla_put_u8(skb, TCA_DUALPI2_DROP_OVERLOAD,
1040 READ_ONCE(q->drop_overload)) ||
1041 nla_put_u8(skb, TCA_DUALPI2_DROP_EARLY,
1042 READ_ONCE(q->drop_early)) ||
1043 nla_put_u8(skb, TCA_DUALPI2_C_PROTECTION,
1044 READ_ONCE(q->c_protection_wc)) ||
1045 nla_put_u8(skb, TCA_DUALPI2_ECN_MASK, READ_ONCE(q->ecn_mask)) ||
1046 nla_put_u8(skb, TCA_DUALPI2_SPLIT_GSO, READ_ONCE(q->split_gso))))
1047 goto nla_put_failure;
1048
1049 if (!step_in_pkts &&
1050 (nla_put_u32(skb, TCA_DUALPI2_LIMIT, READ_ONCE(sch->limit)) ||
1051 nla_put_u32(skb, TCA_DUALPI2_MEMORY_LIMIT,
1052 READ_ONCE(q->memory_limit)) ||
1053 nla_put_u32(skb, TCA_DUALPI2_TARGET,
1054 convert_ns_to_usec(READ_ONCE(q->pi2_target))) ||
1055 nla_put_u32(skb, TCA_DUALPI2_TUPDATE,
1056 convert_ns_to_usec(READ_ONCE(q->pi2_tupdate))) ||
1057 nla_put_u32(skb, TCA_DUALPI2_ALPHA,
1058 dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_alpha))) ||
1059 nla_put_u32(skb, TCA_DUALPI2_BETA,
1060 dualpi2_unscale_alpha_beta(READ_ONCE(q->pi2_beta))) ||
1061 nla_put_u32(skb, TCA_DUALPI2_STEP_THRESH_US,
1062 convert_ns_to_usec(step_th)) ||
1063 nla_put_u32(skb, TCA_DUALPI2_MIN_QLEN_STEP,
1064 READ_ONCE(q->min_qlen_step)) ||
1065 nla_put_u8(skb, TCA_DUALPI2_COUPLING,
1066 READ_ONCE(q->coupling_factor)) ||
1067 nla_put_u8(skb, TCA_DUALPI2_DROP_OVERLOAD,
1068 READ_ONCE(q->drop_overload)) ||
1069 nla_put_u8(skb, TCA_DUALPI2_DROP_EARLY,
1070 READ_ONCE(q->drop_early)) ||
1071 nla_put_u8(skb, TCA_DUALPI2_C_PROTECTION,
1072 READ_ONCE(q->c_protection_wc)) ||
1073 nla_put_u8(skb, TCA_DUALPI2_ECN_MASK, READ_ONCE(q->ecn_mask)) ||
1074 nla_put_u8(skb, TCA_DUALPI2_SPLIT_GSO, READ_ONCE(q->split_gso))))
1075 goto nla_put_failure;
1076
1077 return nla_nest_end(skb, opts);
1078
1079 nla_put_failure:
1080 nla_nest_cancel(skb, opts);
1081 return -1;
1082 }
1083
dualpi2_dump_stats(struct Qdisc * sch,struct gnet_dump * d)1084 static int dualpi2_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1085 {
1086 struct dualpi2_sched_data *q = qdisc_priv(sch);
1087 struct tc_dualpi2_xstats st = {
1088 .prob = READ_ONCE(q->pi2_prob),
1089 .packets_in_c = READ_ONCE(q->packets_in_c),
1090 .packets_in_l = READ_ONCE(q->packets_in_l),
1091 .maxq = READ_ONCE(q->maxq),
1092 .ecn_mark = READ_ONCE(q->ecn_mark),
1093 .credit = READ_ONCE(q->c_protection_credit),
1094 .step_marks = READ_ONCE(q->step_marks),
1095 .memory_used = READ_ONCE(q->memory_used),
1096 .max_memory_used = READ_ONCE(q->max_memory_used),
1097 .memory_limit = READ_ONCE(q->memory_limit),
1098 };
1099 u64 qc, ql;
1100
1101 get_queue_delays(q, &qc, &ql);
1102 st.delay_l = convert_ns_to_usec(ql);
1103 st.delay_c = convert_ns_to_usec(qc);
1104 return gnet_stats_copy_app(d, &st, sizeof(st));
1105 }
1106
1107 /* Reset both L-queue and C-queue, internal packet counters, PI probability,
1108 * C-queue protection credit, and timestamps, while preserving current
1109 * configuration of DUALPI2.
1110 */
dualpi2_reset(struct Qdisc * sch)1111 static void dualpi2_reset(struct Qdisc *sch)
1112 {
1113 struct dualpi2_sched_data *q = qdisc_priv(sch);
1114
1115 qdisc_reset_queue(sch);
1116 qdisc_reset_queue(q->l_queue);
1117 WRITE_ONCE(q->c_head_ts, 0);
1118 WRITE_ONCE(q->l_head_ts, 0);
1119 WRITE_ONCE(q->pi2_prob, 0);
1120 WRITE_ONCE(q->packets_in_c, 0);
1121 WRITE_ONCE(q->packets_in_l, 0);
1122 WRITE_ONCE(q->maxq, 0);
1123 WRITE_ONCE(q->ecn_mark, 0);
1124 WRITE_ONCE(q->step_marks, 0);
1125 WRITE_ONCE(q->memory_used, 0);
1126 WRITE_ONCE(q->max_memory_used, 0);
1127 dualpi2_reset_c_protection(q);
1128 }
1129
dualpi2_destroy(struct Qdisc * sch)1130 static void dualpi2_destroy(struct Qdisc *sch)
1131 {
1132 struct dualpi2_sched_data *q = qdisc_priv(sch);
1133
1134 q->pi2_tupdate = 0;
1135 hrtimer_cancel(&q->pi2_timer);
1136 if (q->l_queue)
1137 qdisc_put(q->l_queue);
1138 tcf_block_put(q->tcf_block);
1139 }
1140
dualpi2_leaf(struct Qdisc * sch,unsigned long arg)1141 static struct Qdisc *dualpi2_leaf(struct Qdisc *sch, unsigned long arg)
1142 {
1143 return NULL;
1144 }
1145
dualpi2_find(struct Qdisc * sch,u32 classid)1146 static unsigned long dualpi2_find(struct Qdisc *sch, u32 classid)
1147 {
1148 return 0;
1149 }
1150
dualpi2_bind(struct Qdisc * sch,unsigned long parent,u32 classid)1151 static unsigned long dualpi2_bind(struct Qdisc *sch, unsigned long parent,
1152 u32 classid)
1153 {
1154 return 0;
1155 }
1156
dualpi2_unbind(struct Qdisc * q,unsigned long cl)1157 static void dualpi2_unbind(struct Qdisc *q, unsigned long cl)
1158 {
1159 }
1160
dualpi2_tcf_block(struct Qdisc * sch,unsigned long cl,struct netlink_ext_ack * extack)1161 static struct tcf_block *dualpi2_tcf_block(struct Qdisc *sch, unsigned long cl,
1162 struct netlink_ext_ack *extack)
1163 {
1164 struct dualpi2_sched_data *q = qdisc_priv(sch);
1165
1166 if (cl)
1167 return NULL;
1168 return q->tcf_block;
1169 }
1170
dualpi2_walk(struct Qdisc * sch,struct qdisc_walker * arg)1171 static void dualpi2_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1172 {
1173 unsigned int i;
1174
1175 if (arg->stop)
1176 return;
1177
1178 /* We statically define only 2 queues */
1179 for (i = 0; i < 2; i++) {
1180 if (arg->count < arg->skip) {
1181 arg->count++;
1182 continue;
1183 }
1184 if (arg->fn(sch, i + 1, arg) < 0) {
1185 arg->stop = 1;
1186 break;
1187 }
1188 arg->count++;
1189 }
1190 }
1191
1192 /* Minimal class support to handle tc filters */
1193 static const struct Qdisc_class_ops dualpi2_class_ops = {
1194 .leaf = dualpi2_leaf,
1195 .find = dualpi2_find,
1196 .tcf_block = dualpi2_tcf_block,
1197 .bind_tcf = dualpi2_bind,
1198 .unbind_tcf = dualpi2_unbind,
1199 .walk = dualpi2_walk,
1200 };
1201
1202 static struct Qdisc_ops dualpi2_qdisc_ops __read_mostly = {
1203 .id = "dualpi2",
1204 .cl_ops = &dualpi2_class_ops,
1205 .priv_size = sizeof(struct dualpi2_sched_data),
1206 .enqueue = dualpi2_qdisc_enqueue,
1207 .dequeue = dualpi2_qdisc_dequeue,
1208 .peek = dualpi2_peek,
1209 .init = dualpi2_init,
1210 .destroy = dualpi2_destroy,
1211 .reset = dualpi2_reset,
1212 .change = dualpi2_change,
1213 .dump = dualpi2_dump,
1214 .dump_stats = dualpi2_dump_stats,
1215 .owner = THIS_MODULE,
1216 };
1217 MODULE_ALIAS_NET_SCH("dualpi2");
1218
dualpi2_module_init(void)1219 static int __init dualpi2_module_init(void)
1220 {
1221 return register_qdisc(&dualpi2_qdisc_ops);
1222 }
1223
dualpi2_module_exit(void)1224 static void __exit dualpi2_module_exit(void)
1225 {
1226 unregister_qdisc(&dualpi2_qdisc_ops);
1227 }
1228
1229 module_init(dualpi2_module_init);
1230 module_exit(dualpi2_module_exit);
1231
1232 MODULE_DESCRIPTION("Dual Queue with Proportional Integral controller Improved with a Square (dualpi2) scheduler");
1233 MODULE_AUTHOR("Koen De Schepper <koen.de_schepper@nokia-bell-labs.com>");
1234 MODULE_AUTHOR("Chia-Yu Chang <chia-yu.chang@nokia-bell-labs.com>");
1235 MODULE_AUTHOR("Olga Albisser <olga@albisser.org>");
1236 MODULE_AUTHOR("Henrik Steen <henrist@henrist.net>");
1237 MODULE_AUTHOR("Olivier Tilmans <olivier.tilmans@nokia.com>");
1238
1239 MODULE_LICENSE("Dual BSD/GPL");
1240 MODULE_VERSION("1.0");
1241