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 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 142 static u64 dualpi2_sojourn_time(struct sk_buff *skb, u64 reference) 143 { 144 return reference - dualpi2_skb_cb(skb)->ts; 145 } 146 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 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 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 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 175 static bool skb_is_l4s(struct sk_buff *skb) 176 { 177 return dualpi2_skb_cb(skb)->classified == DUALPI2_C_L4S; 178 } 179 180 static bool skb_in_l_queue(struct sk_buff *skb) 181 { 182 return dualpi2_skb_cb(skb)->classified != DUALPI2_C_CLASSIC; 183 } 184 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 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 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 */ 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 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 */ 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 */ 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 */ 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 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 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 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 */ 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 */ 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 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 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 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 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 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 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 656 static s64 __scale_delta(u64 diff) 657 { 658 do_div(diff, 1 << ALPHA_BETA_GRANULARITY); 659 return diff; 660 } 661 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 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 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 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 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 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 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. */ 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 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 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 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 */ 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 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 1141 static struct Qdisc *dualpi2_leaf(struct Qdisc *sch, unsigned long arg) 1142 { 1143 return NULL; 1144 } 1145 1146 static unsigned long dualpi2_find(struct Qdisc *sch, u32 classid) 1147 { 1148 return 0; 1149 } 1150 1151 static unsigned long dualpi2_bind(struct Qdisc *sch, unsigned long parent, 1152 u32 classid) 1153 { 1154 return 0; 1155 } 1156 1157 static void dualpi2_unbind(struct Qdisc *q, unsigned long cl) 1158 { 1159 } 1160 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 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 1219 static int __init dualpi2_module_init(void) 1220 { 1221 return register_qdisc(&dualpi2_qdisc_ops); 1222 } 1223 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