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