1 // SPDX-License-Identifier: GPL-2.0-only
2 /* net/sched/sch_hhf.c Heavy-Hitter Filter (HHF)
3 *
4 * Copyright (C) 2013 Terry Lam <vtlam@google.com>
5 * Copyright (C) 2013 Nandita Dukkipati <nanditad@google.com>
6 */
7
8 #include <linux/jiffies.h>
9 #include <linux/module.h>
10 #include <linux/skbuff.h>
11 #include <linux/vmalloc.h>
12 #include <linux/siphash.h>
13 #include <net/pkt_sched.h>
14 #include <net/sock.h>
15
16 /* Heavy-Hitter Filter (HHF)
17 *
18 * Principles :
19 * Flows are classified into two buckets: non-heavy-hitter and heavy-hitter
20 * buckets. Initially, a new flow starts as non-heavy-hitter. Once classified
21 * as heavy-hitter, it is immediately switched to the heavy-hitter bucket.
22 * The buckets are dequeued by a Weighted Deficit Round Robin (WDRR) scheduler,
23 * in which the heavy-hitter bucket is served with less weight.
24 * In other words, non-heavy-hitters (e.g., short bursts of critical traffic)
25 * are isolated from heavy-hitters (e.g., persistent bulk traffic) and also have
26 * higher share of bandwidth.
27 *
28 * To capture heavy-hitters, we use the "multi-stage filter" algorithm in the
29 * following paper:
30 * [EV02] C. Estan and G. Varghese, "New Directions in Traffic Measurement and
31 * Accounting", in ACM SIGCOMM, 2002.
32 *
33 * Conceptually, a multi-stage filter comprises k independent hash functions
34 * and k counter arrays. Packets are indexed into k counter arrays by k hash
35 * functions, respectively. The counters are then increased by the packet sizes.
36 * Therefore,
37 * - For a heavy-hitter flow: *all* of its k array counters must be large.
38 * - For a non-heavy-hitter flow: some of its k array counters can be large
39 * due to hash collision with other small flows; however, with high
40 * probability, not *all* k counters are large.
41 *
42 * By the design of the multi-stage filter algorithm, the false negative rate
43 * (heavy-hitters getting away uncaptured) is zero. However, the algorithm is
44 * susceptible to false positives (non-heavy-hitters mistakenly classified as
45 * heavy-hitters).
46 * Therefore, we also implement the following optimizations to reduce false
47 * positives by avoiding unnecessary increment of the counter values:
48 * - Optimization O1: once a heavy-hitter is identified, its bytes are not
49 * accounted in the array counters. This technique is called "shielding"
50 * in Section 3.3.1 of [EV02].
51 * - Optimization O2: conservative update of counters
52 * (Section 3.3.2 of [EV02]),
53 * New counter value = max {old counter value,
54 * smallest counter value + packet bytes}
55 *
56 * Finally, we refresh the counters periodically since otherwise the counter
57 * values will keep accumulating.
58 *
59 * Once a flow is classified as heavy-hitter, we also save its per-flow state
60 * in an exact-matching flow table so that its subsequent packets can be
61 * dispatched to the heavy-hitter bucket accordingly.
62 *
63 *
64 * At a high level, this qdisc works as follows:
65 * Given a packet p:
66 * - If the flow-id of p (e.g., TCP 5-tuple) is already in the exact-matching
67 * heavy-hitter flow table, denoted table T, then send p to the heavy-hitter
68 * bucket.
69 * - Otherwise, forward p to the multi-stage filter, denoted filter F
70 * + If F decides that p belongs to a non-heavy-hitter flow, then send p
71 * to the non-heavy-hitter bucket.
72 * + Otherwise, if F decides that p belongs to a new heavy-hitter flow,
73 * then set up a new flow entry for the flow-id of p in the table T and
74 * send p to the heavy-hitter bucket.
75 *
76 * In this implementation:
77 * - T is a fixed-size hash-table with 1024 entries. Hash collision is
78 * resolved by linked-list chaining.
79 * - F has four counter arrays, each array containing 1024 32-bit counters.
80 * That means 4 * 1024 * 32 bits = 16KB of memory.
81 * - Since each array in F contains 1024 counters, 10 bits are sufficient to
82 * index into each array.
83 * Hence, instead of having four hash functions, we chop the 32-bit
84 * skb-hash into three 10-bit chunks, and the remaining 10-bit chunk is
85 * computed as XOR sum of those three chunks.
86 * - We need to clear the counter arrays periodically; however, directly
87 * memsetting 16KB of memory can lead to cache eviction and unwanted delay.
88 * So by representing each counter by a valid bit, we only need to reset
89 * 4K of 1 bit (i.e. 512 bytes) instead of 16KB of memory.
90 * - The Deficit Round Robin engine is taken from fq_codel implementation
91 * (net/sched/sch_fq_codel.c). Note that wdrr_bucket corresponds to
92 * fq_codel_flow in fq_codel implementation.
93 *
94 */
95
96 /* Non-configurable parameters */
97 #define HH_FLOWS_CNT 1024 /* number of entries in exact-matching table T */
98 #define HHF_ARRAYS_CNT 4 /* number of arrays in multi-stage filter F */
99 #define HHF_ARRAYS_LEN 1024 /* number of counters in each array of F */
100 #define HHF_BIT_MASK_LEN 10 /* masking 10 bits */
101 #define HHF_BIT_MASK 0x3FF /* bitmask of 10 bits */
102
103 #define WDRR_BUCKET_CNT 2 /* two buckets for Weighted DRR */
104 enum wdrr_bucket_idx {
105 WDRR_BUCKET_FOR_HH = 0, /* bucket id for heavy-hitters */
106 WDRR_BUCKET_FOR_NON_HH = 1 /* bucket id for non-heavy-hitters */
107 };
108
109 #define hhf_time_before(a, b) \
110 (typecheck(u32, a) && typecheck(u32, b) && ((s32)((a) - (b)) < 0))
111
112 /* Heavy-hitter per-flow state */
113 struct hh_flow_state {
114 u32 hash_id; /* hash of flow-id (e.g. TCP 5-tuple) */
115 u32 hit_timestamp; /* last time heavy-hitter was seen */
116 struct list_head flowchain; /* chaining under hash collision */
117 };
118
119 /* Weighted Deficit Round Robin (WDRR) scheduler */
120 struct wdrr_bucket {
121 struct sk_buff *head;
122 struct sk_buff *tail;
123 struct list_head bucketchain;
124 int deficit;
125 };
126
127 struct hhf_sched_data {
128 struct wdrr_bucket buckets[WDRR_BUCKET_CNT];
129 siphash_key_t perturbation; /* hash perturbation */
130 u32 quantum; /* psched_mtu(qdisc_dev(sch)); */
131 u32 drop_overlimit; /* number of times max qdisc packet
132 * limit was hit
133 */
134 struct list_head *hh_flows; /* table T (currently active HHs) */
135 u32 hh_flows_limit; /* max active HH allocs */
136 u32 hh_flows_overlimit; /* num of disallowed HH allocs */
137 u32 hh_flows_total_cnt; /* total admitted HHs */
138 u32 hh_flows_current_cnt; /* total current HHs */
139 u32 *hhf_arrays[HHF_ARRAYS_CNT]; /* HH filter F */
140 u32 hhf_arrays_reset_timestamp; /* last time hhf_arrays
141 * was reset
142 */
143 unsigned long *hhf_valid_bits[HHF_ARRAYS_CNT]; /* shadow valid bits
144 * of hhf_arrays
145 */
146 /* Similar to the "new_flows" vs. "old_flows" concept in fq_codel DRR */
147 struct list_head new_buckets; /* list of new buckets */
148 struct list_head old_buckets; /* list of old buckets */
149
150 /* Configurable HHF parameters */
151 u32 hhf_reset_timeout; /* interval to reset counter
152 * arrays in filter F
153 * (default 40ms)
154 */
155 u32 hhf_admit_bytes; /* counter thresh to classify as
156 * HH (default 128KB).
157 * With these default values,
158 * 128KB / 40ms = 25 Mbps
159 * i.e., we expect to capture HHs
160 * sending > 25 Mbps.
161 */
162 u32 hhf_evict_timeout; /* aging threshold to evict idle
163 * HHs out of table T. This should
164 * be large enough to avoid
165 * reordering during HH eviction.
166 * (default 1s)
167 */
168 u32 hhf_non_hh_weight; /* WDRR weight for non-HHs
169 * (default 2,
170 * i.e., non-HH : HH = 2 : 1)
171 */
172 };
173
hhf_time_stamp(void)174 static u32 hhf_time_stamp(void)
175 {
176 return jiffies;
177 }
178
179 /* Looks up a heavy-hitter flow in a chaining list of table T. */
seek_list(const u32 hash,struct list_head * head,struct hhf_sched_data * q)180 static struct hh_flow_state *seek_list(const u32 hash,
181 struct list_head *head,
182 struct hhf_sched_data *q)
183 {
184 struct hh_flow_state *flow, *next;
185 u32 now = hhf_time_stamp();
186
187 if (list_empty(head))
188 return NULL;
189
190 list_for_each_entry_safe(flow, next, head, flowchain) {
191 u32 prev = flow->hit_timestamp + q->hhf_evict_timeout;
192
193 if (hhf_time_before(prev, now)) {
194 /* Delete expired heavy-hitters, but preserve one entry
195 * to avoid kzalloc() when next time this slot is hit.
196 */
197 if (list_is_last(&flow->flowchain, head))
198 return NULL;
199 list_del(&flow->flowchain);
200 kfree(flow);
201 WRITE_ONCE(q->hh_flows_current_cnt,
202 q->hh_flows_current_cnt - 1);
203 } else if (flow->hash_id == hash) {
204 return flow;
205 }
206 }
207 return NULL;
208 }
209
210 /* Returns a flow state entry for a new heavy-hitter. Either reuses an expired
211 * entry or dynamically alloc a new entry.
212 */
alloc_new_hh(struct list_head * head,struct hhf_sched_data * q)213 static struct hh_flow_state *alloc_new_hh(struct list_head *head,
214 struct hhf_sched_data *q)
215 {
216 struct hh_flow_state *flow;
217 u32 now = hhf_time_stamp();
218
219 if (!list_empty(head)) {
220 /* Find an expired heavy-hitter flow entry. */
221 list_for_each_entry(flow, head, flowchain) {
222 u32 prev = flow->hit_timestamp + q->hhf_evict_timeout;
223
224 if (hhf_time_before(prev, now))
225 return flow;
226 }
227 }
228
229 if (q->hh_flows_current_cnt >= q->hh_flows_limit) {
230 WRITE_ONCE(q->hh_flows_overlimit, q->hh_flows_overlimit + 1);
231 return NULL;
232 }
233 /* Create new entry. */
234 flow = kzalloc_obj(struct hh_flow_state, GFP_ATOMIC);
235 if (!flow)
236 return NULL;
237
238 WRITE_ONCE(q->hh_flows_current_cnt, q->hh_flows_current_cnt + 1);
239 INIT_LIST_HEAD(&flow->flowchain);
240 list_add_tail(&flow->flowchain, head);
241
242 return flow;
243 }
244
245 /* Assigns packets to WDRR buckets. Implements a multi-stage filter to
246 * classify heavy-hitters.
247 */
hhf_classify(struct sk_buff * skb,struct Qdisc * sch)248 static enum wdrr_bucket_idx hhf_classify(struct sk_buff *skb, struct Qdisc *sch)
249 {
250 struct hhf_sched_data *q = qdisc_priv(sch);
251 u32 tmp_hash, hash;
252 u32 xorsum, filter_pos[HHF_ARRAYS_CNT], flow_pos;
253 struct hh_flow_state *flow;
254 u32 pkt_len, min_hhf_val;
255 int i;
256 u32 prev;
257 u32 now = hhf_time_stamp();
258
259 /* Reset the HHF counter arrays if this is the right time. */
260 prev = q->hhf_arrays_reset_timestamp + q->hhf_reset_timeout;
261 if (hhf_time_before(prev, now)) {
262 for (i = 0; i < HHF_ARRAYS_CNT; i++)
263 bitmap_zero(q->hhf_valid_bits[i], HHF_ARRAYS_LEN);
264 q->hhf_arrays_reset_timestamp = now;
265 }
266
267 /* Get hashed flow-id of the skb. */
268 hash = skb_get_hash_perturb(skb, &q->perturbation);
269
270 /* Check if this packet belongs to an already established HH flow. */
271 flow_pos = hash & HHF_BIT_MASK;
272 flow = seek_list(hash, &q->hh_flows[flow_pos], q);
273 if (flow) { /* found its HH flow */
274 flow->hit_timestamp = now;
275 return WDRR_BUCKET_FOR_HH;
276 }
277
278 /* Now pass the packet through the multi-stage filter. */
279 tmp_hash = hash;
280 xorsum = 0;
281 for (i = 0; i < HHF_ARRAYS_CNT - 1; i++) {
282 /* Split the skb_hash into three 10-bit chunks. */
283 filter_pos[i] = tmp_hash & HHF_BIT_MASK;
284 xorsum ^= filter_pos[i];
285 tmp_hash >>= HHF_BIT_MASK_LEN;
286 }
287 /* The last chunk is computed as XOR sum of other chunks. */
288 filter_pos[HHF_ARRAYS_CNT - 1] = xorsum ^ tmp_hash;
289
290 pkt_len = qdisc_pkt_len(skb);
291 min_hhf_val = ~0U;
292 for (i = 0; i < HHF_ARRAYS_CNT; i++) {
293 u32 val;
294
295 if (!test_bit(filter_pos[i], q->hhf_valid_bits[i])) {
296 q->hhf_arrays[i][filter_pos[i]] = 0;
297 __set_bit(filter_pos[i], q->hhf_valid_bits[i]);
298 }
299
300 val = q->hhf_arrays[i][filter_pos[i]] + pkt_len;
301 if (min_hhf_val > val)
302 min_hhf_val = val;
303 }
304
305 /* Found a new HH iff all counter values > HH admit threshold. */
306 if (min_hhf_val > q->hhf_admit_bytes) {
307 /* Just captured a new heavy-hitter. */
308 flow = alloc_new_hh(&q->hh_flows[flow_pos], q);
309 if (!flow) /* memory alloc problem */
310 return WDRR_BUCKET_FOR_NON_HH;
311 flow->hash_id = hash;
312 flow->hit_timestamp = now;
313 WRITE_ONCE(q->hh_flows_total_cnt, q->hh_flows_total_cnt + 1);
314
315 /* By returning without updating counters in q->hhf_arrays,
316 * we implicitly implement "shielding" (see Optimization O1).
317 */
318 return WDRR_BUCKET_FOR_HH;
319 }
320
321 /* Conservative update of HHF arrays (see Optimization O2). */
322 for (i = 0; i < HHF_ARRAYS_CNT; i++) {
323 if (q->hhf_arrays[i][filter_pos[i]] < min_hhf_val)
324 q->hhf_arrays[i][filter_pos[i]] = min_hhf_val;
325 }
326 return WDRR_BUCKET_FOR_NON_HH;
327 }
328
329 /* Removes one skb from head of bucket. */
dequeue_head(struct wdrr_bucket * bucket)330 static struct sk_buff *dequeue_head(struct wdrr_bucket *bucket)
331 {
332 struct sk_buff *skb = bucket->head;
333
334 bucket->head = skb->next;
335 skb_mark_not_on_list(skb);
336 return skb;
337 }
338
339 /* Tail-adds skb to bucket. */
bucket_add(struct wdrr_bucket * bucket,struct sk_buff * skb)340 static void bucket_add(struct wdrr_bucket *bucket, struct sk_buff *skb)
341 {
342 if (bucket->head == NULL)
343 bucket->head = skb;
344 else
345 bucket->tail->next = skb;
346 bucket->tail = skb;
347 skb->next = NULL;
348 }
349
hhf_drop(struct Qdisc * sch,struct sk_buff ** to_free)350 static unsigned int hhf_drop(struct Qdisc *sch, struct sk_buff **to_free)
351 {
352 struct hhf_sched_data *q = qdisc_priv(sch);
353 struct wdrr_bucket *bucket;
354
355 /* Always try to drop from heavy-hitters first. */
356 bucket = &q->buckets[WDRR_BUCKET_FOR_HH];
357 if (!bucket->head)
358 bucket = &q->buckets[WDRR_BUCKET_FOR_NON_HH];
359
360 if (bucket->head) {
361 struct sk_buff *skb = dequeue_head(bucket);
362
363 qdisc_qlen_dec(sch);
364 qdisc_qstats_backlog_dec(sch, skb);
365 qdisc_drop(skb, sch, to_free);
366 }
367
368 /* Return id of the bucket from which the packet was dropped. */
369 return bucket - q->buckets;
370 }
371
hhf_enqueue(struct sk_buff * skb,struct Qdisc * sch,struct sk_buff ** to_free)372 static int hhf_enqueue(struct sk_buff *skb, struct Qdisc *sch,
373 struct sk_buff **to_free)
374 {
375 struct hhf_sched_data *q = qdisc_priv(sch);
376 enum wdrr_bucket_idx idx;
377 struct wdrr_bucket *bucket;
378 unsigned int prev_backlog;
379
380 idx = hhf_classify(skb, sch);
381
382 bucket = &q->buckets[idx];
383 bucket_add(bucket, skb);
384 qdisc_qstats_backlog_inc(sch, skb);
385
386 if (list_empty(&bucket->bucketchain)) {
387 unsigned int weight;
388
389 /* The logic of new_buckets vs. old_buckets is the same as
390 * new_flows vs. old_flows in the implementation of fq_codel,
391 * i.e., short bursts of non-HHs should have strict priority.
392 */
393 if (idx == WDRR_BUCKET_FOR_HH) {
394 /* Always move heavy-hitters to old bucket. */
395 weight = 1;
396 list_add_tail(&bucket->bucketchain, &q->old_buckets);
397 } else {
398 weight = q->hhf_non_hh_weight;
399 list_add_tail(&bucket->bucketchain, &q->new_buckets);
400 }
401 bucket->deficit = weight * q->quantum;
402 }
403 qdisc_qlen_inc(sch);
404 if (sch->q.qlen <= sch->limit)
405 return NET_XMIT_SUCCESS;
406
407 prev_backlog = sch->qstats.backlog;
408 WRITE_ONCE(q->drop_overlimit, q->drop_overlimit + 1);
409 /* Return Congestion Notification only if we dropped a packet from this
410 * bucket.
411 */
412 if (hhf_drop(sch, to_free) == idx)
413 return NET_XMIT_CN;
414
415 /* As we dropped a packet, better let upper stack know this. */
416 qdisc_tree_reduce_backlog(sch, 1, prev_backlog - sch->qstats.backlog);
417 return NET_XMIT_SUCCESS;
418 }
419
hhf_dequeue(struct Qdisc * sch)420 static struct sk_buff *hhf_dequeue(struct Qdisc *sch)
421 {
422 struct hhf_sched_data *q = qdisc_priv(sch);
423 struct sk_buff *skb = NULL;
424 struct wdrr_bucket *bucket;
425 struct list_head *head;
426
427 begin:
428 head = &q->new_buckets;
429 if (list_empty(head)) {
430 head = &q->old_buckets;
431 if (list_empty(head))
432 return NULL;
433 }
434 bucket = list_first_entry(head, struct wdrr_bucket, bucketchain);
435
436 if (bucket->deficit <= 0) {
437 int weight = (bucket - q->buckets == WDRR_BUCKET_FOR_HH) ?
438 1 : q->hhf_non_hh_weight;
439
440 bucket->deficit += weight * q->quantum;
441 list_move_tail(&bucket->bucketchain, &q->old_buckets);
442 goto begin;
443 }
444
445 if (bucket->head) {
446 skb = dequeue_head(bucket);
447 qdisc_qlen_dec(sch);
448 qdisc_qstats_backlog_dec(sch, skb);
449 }
450
451 if (!skb) {
452 /* Force a pass through old_buckets to prevent starvation. */
453 if ((head == &q->new_buckets) && !list_empty(&q->old_buckets))
454 list_move_tail(&bucket->bucketchain, &q->old_buckets);
455 else
456 list_del_init(&bucket->bucketchain);
457 goto begin;
458 }
459 qdisc_bstats_update(sch, skb);
460 bucket->deficit -= qdisc_pkt_len(skb);
461
462 return skb;
463 }
464
hhf_reset_classifier(struct hhf_sched_data * q)465 static void hhf_reset_classifier(struct hhf_sched_data *q)
466 {
467 int i;
468
469 if (!q->hh_flows)
470 return;
471
472 for (i = 0; i < HH_FLOWS_CNT; i++) {
473 struct hh_flow_state *flow, *next;
474 struct list_head *head = &q->hh_flows[i];
475
476 list_for_each_entry_safe(flow, next, head, flowchain) {
477 list_del(&flow->flowchain);
478 kfree(flow);
479 }
480 }
481 WRITE_ONCE(q->hh_flows_current_cnt, 0);
482
483 for (i = 0; i < HHF_ARRAYS_CNT; i++) {
484 if (q->hhf_valid_bits[i])
485 bitmap_zero(q->hhf_valid_bits[i], HHF_ARRAYS_LEN);
486 }
487 q->hhf_arrays_reset_timestamp = hhf_time_stamp();
488 }
489
hhf_reset(struct Qdisc * sch)490 static void hhf_reset(struct Qdisc *sch)
491 {
492 struct hhf_sched_data *q = qdisc_priv(sch);
493 struct sk_buff *skb;
494
495 while ((skb = hhf_dequeue(sch)) != NULL)
496 rtnl_kfree_skbs(skb, skb);
497 hhf_reset_classifier(q);
498 }
499
hhf_destroy(struct Qdisc * sch)500 static void hhf_destroy(struct Qdisc *sch)
501 {
502 int i;
503 struct hhf_sched_data *q = qdisc_priv(sch);
504
505 for (i = 0; i < HHF_ARRAYS_CNT; i++) {
506 kvfree(q->hhf_arrays[i]);
507 kvfree(q->hhf_valid_bits[i]);
508 }
509
510 if (!q->hh_flows)
511 return;
512
513 for (i = 0; i < HH_FLOWS_CNT; i++) {
514 struct hh_flow_state *flow, *next;
515 struct list_head *head = &q->hh_flows[i];
516
517 if (list_empty(head))
518 continue;
519 list_for_each_entry_safe(flow, next, head, flowchain) {
520 list_del(&flow->flowchain);
521 kfree(flow);
522 }
523 }
524 kvfree(q->hh_flows);
525 }
526
527 static const struct nla_policy hhf_policy[TCA_HHF_MAX + 1] = {
528 [TCA_HHF_BACKLOG_LIMIT] = { .type = NLA_U32 },
529 [TCA_HHF_QUANTUM] = { .type = NLA_U32 },
530 [TCA_HHF_HH_FLOWS_LIMIT] = { .type = NLA_U32 },
531 [TCA_HHF_RESET_TIMEOUT] = { .type = NLA_U32 },
532 [TCA_HHF_ADMIT_BYTES] = { .type = NLA_U32 },
533 [TCA_HHF_EVICT_TIMEOUT] = { .type = NLA_U32 },
534 [TCA_HHF_NON_HH_WEIGHT] = { .type = NLA_U32 },
535 };
536
hhf_change(struct Qdisc * sch,struct nlattr * opt,struct netlink_ext_ack * extack)537 static int hhf_change(struct Qdisc *sch, struct nlattr *opt,
538 struct netlink_ext_ack *extack)
539 {
540 unsigned int dropped_pkts = 0, dropped_bytes = 0;
541 struct hhf_sched_data *q = qdisc_priv(sch);
542 struct nlattr *tb[TCA_HHF_MAX + 1];
543 int err;
544 u64 non_hh_quantum;
545 u32 new_quantum = q->quantum;
546 u32 new_hhf_non_hh_weight = q->hhf_non_hh_weight;
547
548 err = nla_parse_nested_deprecated(tb, TCA_HHF_MAX, opt, hhf_policy,
549 NULL);
550 if (err < 0)
551 return err;
552
553 if (tb[TCA_HHF_QUANTUM])
554 new_quantum = nla_get_u32(tb[TCA_HHF_QUANTUM]);
555
556 if (tb[TCA_HHF_NON_HH_WEIGHT])
557 new_hhf_non_hh_weight = nla_get_u32(tb[TCA_HHF_NON_HH_WEIGHT]);
558
559 non_hh_quantum = (u64)new_quantum * new_hhf_non_hh_weight;
560 if (non_hh_quantum == 0 || non_hh_quantum > INT_MAX)
561 return -EINVAL;
562
563 sch_tree_lock(sch);
564
565 if (tb[TCA_HHF_BACKLOG_LIMIT])
566 WRITE_ONCE(sch->limit, nla_get_u32(tb[TCA_HHF_BACKLOG_LIMIT]));
567
568 WRITE_ONCE(q->quantum, new_quantum);
569 WRITE_ONCE(q->hhf_non_hh_weight, new_hhf_non_hh_weight);
570
571 if (tb[TCA_HHF_HH_FLOWS_LIMIT])
572 WRITE_ONCE(q->hh_flows_limit,
573 nla_get_u32(tb[TCA_HHF_HH_FLOWS_LIMIT]));
574
575 if (tb[TCA_HHF_RESET_TIMEOUT]) {
576 u32 us = nla_get_u32(tb[TCA_HHF_RESET_TIMEOUT]);
577
578 WRITE_ONCE(q->hhf_reset_timeout,
579 usecs_to_jiffies(us));
580 }
581
582 if (tb[TCA_HHF_ADMIT_BYTES])
583 WRITE_ONCE(q->hhf_admit_bytes,
584 nla_get_u32(tb[TCA_HHF_ADMIT_BYTES]));
585
586 if (tb[TCA_HHF_EVICT_TIMEOUT]) {
587 u32 us = nla_get_u32(tb[TCA_HHF_EVICT_TIMEOUT]);
588
589 WRITE_ONCE(q->hhf_evict_timeout,
590 usecs_to_jiffies(us));
591 }
592
593 while (sch->q.qlen > sch->limit) {
594 struct sk_buff *skb = qdisc_dequeue_internal(sch, false);
595
596 if (!skb)
597 break;
598
599 dropped_pkts++;
600 dropped_bytes += qdisc_pkt_len(skb);
601 rtnl_kfree_skbs(skb, skb);
602 }
603 qdisc_tree_reduce_backlog(sch, dropped_pkts, dropped_bytes);
604
605 sch_tree_unlock(sch);
606 return 0;
607 }
608
hhf_init(struct Qdisc * sch,struct nlattr * opt,struct netlink_ext_ack * extack)609 static int hhf_init(struct Qdisc *sch, struct nlattr *opt,
610 struct netlink_ext_ack *extack)
611 {
612 struct hhf_sched_data *q = qdisc_priv(sch);
613 int i;
614
615 sch->limit = 1000;
616 q->quantum = psched_mtu(qdisc_dev(sch));
617 get_random_bytes(&q->perturbation, sizeof(q->perturbation));
618 INIT_LIST_HEAD(&q->new_buckets);
619 INIT_LIST_HEAD(&q->old_buckets);
620
621 /* Configurable HHF parameters */
622 q->hhf_reset_timeout = HZ / 25; /* 40 ms */
623 q->hhf_admit_bytes = 131072; /* 128 KB */
624 q->hhf_evict_timeout = HZ; /* 1 sec */
625 q->hhf_non_hh_weight = 2;
626
627 if (opt) {
628 int err = hhf_change(sch, opt, extack);
629
630 if (err)
631 return err;
632 }
633
634 if (!q->hh_flows) {
635 /* Initialize heavy-hitter flow table. */
636 q->hh_flows = kvzalloc_objs(struct list_head, HH_FLOWS_CNT);
637 if (!q->hh_flows)
638 return -ENOMEM;
639 for (i = 0; i < HH_FLOWS_CNT; i++)
640 INIT_LIST_HEAD(&q->hh_flows[i]);
641
642 /* Cap max active HHs at twice len of hh_flows table. */
643 q->hh_flows_limit = 2 * HH_FLOWS_CNT;
644 q->hh_flows_overlimit = 0;
645 q->hh_flows_total_cnt = 0;
646 q->hh_flows_current_cnt = 0;
647
648 /* Initialize heavy-hitter filter arrays. */
649 for (i = 0; i < HHF_ARRAYS_CNT; i++) {
650 q->hhf_arrays[i] = kvcalloc(HHF_ARRAYS_LEN,
651 sizeof(u32),
652 GFP_KERNEL);
653 if (!q->hhf_arrays[i]) {
654 /* Note: hhf_destroy() will be called
655 * by our caller.
656 */
657 return -ENOMEM;
658 }
659 }
660 q->hhf_arrays_reset_timestamp = hhf_time_stamp();
661
662 /* Initialize valid bits of heavy-hitter filter arrays. */
663 for (i = 0; i < HHF_ARRAYS_CNT; i++) {
664 q->hhf_valid_bits[i] = kvzalloc(HHF_ARRAYS_LEN /
665 BITS_PER_BYTE, GFP_KERNEL);
666 if (!q->hhf_valid_bits[i]) {
667 /* Note: hhf_destroy() will be called
668 * by our caller.
669 */
670 return -ENOMEM;
671 }
672 }
673
674 /* Initialize Weighted DRR buckets. */
675 for (i = 0; i < WDRR_BUCKET_CNT; i++) {
676 struct wdrr_bucket *bucket = q->buckets + i;
677
678 INIT_LIST_HEAD(&bucket->bucketchain);
679 }
680 }
681
682 return 0;
683 }
684
hhf_dump(struct Qdisc * sch,struct sk_buff * skb)685 static int hhf_dump(struct Qdisc *sch, struct sk_buff *skb)
686 {
687 struct hhf_sched_data *q = qdisc_priv(sch);
688 struct nlattr *opts;
689
690 opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
691 if (opts == NULL)
692 goto nla_put_failure;
693
694 if (nla_put_u32(skb, TCA_HHF_BACKLOG_LIMIT, READ_ONCE(sch->limit)) ||
695 nla_put_u32(skb, TCA_HHF_QUANTUM, READ_ONCE(q->quantum)) ||
696 nla_put_u32(skb, TCA_HHF_HH_FLOWS_LIMIT,
697 READ_ONCE(q->hh_flows_limit)) ||
698 nla_put_u32(skb, TCA_HHF_RESET_TIMEOUT,
699 jiffies_to_usecs(READ_ONCE(q->hhf_reset_timeout))) ||
700 nla_put_u32(skb, TCA_HHF_ADMIT_BYTES,
701 READ_ONCE(q->hhf_admit_bytes)) ||
702 nla_put_u32(skb, TCA_HHF_EVICT_TIMEOUT,
703 jiffies_to_usecs(READ_ONCE(q->hhf_evict_timeout))) ||
704 nla_put_u32(skb, TCA_HHF_NON_HH_WEIGHT,
705 READ_ONCE(q->hhf_non_hh_weight)))
706 goto nla_put_failure;
707
708 return nla_nest_end(skb, opts);
709
710 nla_put_failure:
711 return -1;
712 }
713
hhf_dump_stats(struct Qdisc * sch,struct gnet_dump * d)714 static int hhf_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
715 {
716 struct hhf_sched_data *q = qdisc_priv(sch);
717 struct tc_hhf_xstats st = {
718 .drop_overlimit = READ_ONCE(q->drop_overlimit),
719 .hh_overlimit = READ_ONCE(q->hh_flows_overlimit),
720 .hh_tot_count = READ_ONCE(q->hh_flows_total_cnt),
721 .hh_cur_count = READ_ONCE(q->hh_flows_current_cnt),
722 };
723
724 return gnet_stats_copy_app(d, &st, sizeof(st));
725 }
726
727 static struct Qdisc_ops hhf_qdisc_ops __read_mostly = {
728 .id = "hhf",
729 .priv_size = sizeof(struct hhf_sched_data),
730
731 .enqueue = hhf_enqueue,
732 .dequeue = hhf_dequeue,
733 .peek = qdisc_peek_dequeued,
734 .init = hhf_init,
735 .reset = hhf_reset,
736 .destroy = hhf_destroy,
737 .change = hhf_change,
738 .dump = hhf_dump,
739 .dump_stats = hhf_dump_stats,
740 .owner = THIS_MODULE,
741 };
742 MODULE_ALIAS_NET_SCH("hhf");
743
hhf_module_init(void)744 static int __init hhf_module_init(void)
745 {
746 return register_qdisc(&hhf_qdisc_ops);
747 }
748
hhf_module_exit(void)749 static void __exit hhf_module_exit(void)
750 {
751 unregister_qdisc(&hhf_qdisc_ops);
752 }
753
754 module_init(hhf_module_init)
755 module_exit(hhf_module_exit)
756 MODULE_AUTHOR("Terry Lam");
757 MODULE_AUTHOR("Nandita Dukkipati");
758 MODULE_LICENSE("GPL");
759 MODULE_DESCRIPTION("Heavy-Hitter Filter (HHF)");
760