Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 1 | /* 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 Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 12 | #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 */ |
| 103 | enum 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 */ |
| 112 | struct 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 */ |
| 119 | struct wdrr_bucket { |
| 120 | struct sk_buff *head; |
| 121 | struct sk_buff *tail; |
| 122 | struct list_head bucketchain; |
| 123 | int deficit; |
| 124 | }; |
| 125 | |
| 126 | struct 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 | |
| 173 | static u32 hhf_time_stamp(void) |
| 174 | { |
| 175 | return jiffies; |
| 176 | } |
| 177 | |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 178 | /* Looks up a heavy-hitter flow in a chaining list of table T. */ |
| 179 | static 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 | */ |
| 211 | static 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 | */ |
| 246 | static 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 Herbert | f969777 | 2015-05-01 11:30:14 -0700 | [diff] [blame] | 266 | hash = skb_get_hash_perturb(skb, q->perturbation); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 267 | |
| 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. */ |
| 328 | static 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. */ |
| 338 | static 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 | |
| 348 | static 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 Fastabend | 25331d6 | 2014-09-28 11:53:29 -0700 | [diff] [blame] | 362 | qdisc_qstats_drop(sch); |
| 363 | qdisc_qstats_backlog_dec(sch, skb); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 364 | 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 Cong | 6ac644a | 2015-10-07 16:47:32 -0700 | [diff] [blame] | 371 | static 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 Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 380 | static 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 Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 385 | unsigned int prev_backlog; |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 386 | |
| 387 | idx = hhf_classify(skb, sch); |
| 388 | |
| 389 | bucket = &q->buckets[idx]; |
| 390 | bucket_add(bucket, skb); |
John Fastabend | 25331d6 | 2014-09-28 11:53:29 -0700 | [diff] [blame] | 391 | qdisc_qstats_backlog_inc(sch, skb); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 392 | |
| 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 Yingliang | b2ce49e7 | 2014-05-09 16:49:05 +0800 | [diff] [blame] | 410 | if (++sch->q.qlen <= sch->limit) |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 411 | return NET_XMIT_SUCCESS; |
| 412 | |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 413 | prev_backlog = sch->qstats.backlog; |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 414 | 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 Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 422 | qdisc_tree_reduce_backlog(sch, 1, prev_backlog - sch->qstats.backlog); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 423 | return NET_XMIT_SUCCESS; |
| 424 | } |
| 425 | |
| 426 | static 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 | |
| 433 | begin: |
| 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 Fastabend | 25331d6 | 2014-09-28 11:53:29 -0700 | [diff] [blame] | 454 | qdisc_qstats_backlog_dec(sch, skb); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 455 | } |
| 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 | |
| 471 | static 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 | |
| 479 | static 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 | |
| 489 | static void hhf_free(void *addr) |
| 490 | { |
WANG Cong | 4cb2897 | 2014-06-02 15:55:22 -0700 | [diff] [blame] | 491 | kvfree(addr); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 492 | } |
| 493 | |
| 494 | static 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 | |
| 518 | static 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 | |
| 528 | static 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 Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 532 | unsigned int qlen, prev_backlog; |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 533 | 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 Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 545 | 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 Fastabend | f6a082f | 2014-05-01 09:23:06 -0700 | [diff] [blame] | 554 | |
| 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 Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 560 | 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 Lam | 6c76a07 | 2014-01-09 00:40:00 -0800 | [diff] [blame] | 567 | u32 us = nla_get_u32(tb[TCA_HHF_RESET_TIMEOUT]); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 568 | |
Terry Lam | 6c76a07 | 2014-01-09 00:40:00 -0800 | [diff] [blame] | 569 | q->hhf_reset_timeout = usecs_to_jiffies(us); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 570 | } |
| 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 Lam | 6c76a07 | 2014-01-09 00:40:00 -0800 | [diff] [blame] | 576 | u32 us = nla_get_u32(tb[TCA_HHF_EVICT_TIMEOUT]); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 577 | |
Terry Lam | 6c76a07 | 2014-01-09 00:40:00 -0800 | [diff] [blame] | 578 | q->hhf_evict_timeout = usecs_to_jiffies(us); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 579 | } |
| 580 | |
| 581 | qlen = sch->q.qlen; |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 582 | prev_backlog = sch->qstats.backlog; |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 583 | while (sch->q.qlen > sch->limit) { |
| 584 | struct sk_buff *skb = hhf_dequeue(sch); |
| 585 | |
| 586 | kfree_skb(skb); |
| 587 | } |
WANG Cong | 2ccccf5 | 2016-02-25 14:55:01 -0800 | [diff] [blame] | 588 | qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, |
| 589 | prev_backlog - sch->qstats.backlog); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 590 | |
| 591 | sch_tree_unlock(sch); |
| 592 | return 0; |
| 593 | } |
| 594 | |
| 595 | static 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-Hewapathirane | 63862b5 | 2014-01-11 07:15:59 -0500 | [diff] [blame] | 602 | q->perturbation = prandom_u32(); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 603 | 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 | |
| 666 | static 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 Lam | 6c76a07 | 2014-01-09 00:40:00 -0800 | [diff] [blame] | 679 | jiffies_to_usecs(q->hhf_reset_timeout)) || |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 680 | nla_put_u32(skb, TCA_HHF_ADMIT_BYTES, q->hhf_admit_bytes) || |
| 681 | nla_put_u32(skb, TCA_HHF_EVICT_TIMEOUT, |
Terry Lam | 6c76a07 | 2014-01-09 00:40:00 -0800 | [diff] [blame] | 682 | jiffies_to_usecs(q->hhf_evict_timeout)) || |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 683 | nla_put_u32(skb, TCA_HHF_NON_HH_WEIGHT, q->hhf_non_hh_weight)) |
| 684 | goto nla_put_failure; |
| 685 | |
Yang Yingliang | d59b7d8 | 2014-03-12 10:20:32 +0800 | [diff] [blame] | 686 | return nla_nest_end(skb, opts); |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 687 | |
| 688 | nla_put_failure: |
| 689 | return -1; |
| 690 | } |
| 691 | |
| 692 | static 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 hemminger | c49fa25 | 2013-12-26 10:09:05 -0800 | [diff] [blame] | 705 | static struct Qdisc_ops hhf_qdisc_ops __read_mostly = { |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 706 | .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 Cong | 6ac644a | 2015-10-07 16:47:32 -0700 | [diff] [blame] | 712 | .drop = hhf_qdisc_drop, |
Terry Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 713 | .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 Lam | 10239ed | 2013-12-15 00:30:21 -0800 | [diff] [blame] | 721 | |
| 722 | static int __init hhf_module_init(void) |
| 723 | { |
| 724 | return register_qdisc(&hhf_qdisc_ops); |
| 725 | } |
| 726 | |
| 727 | static void __exit hhf_module_exit(void) |
| 728 | { |
| 729 | unregister_qdisc(&hhf_qdisc_ops); |
| 730 | } |
| 731 | |
| 732 | module_init(hhf_module_init) |
| 733 | module_exit(hhf_module_exit) |
| 734 | MODULE_AUTHOR("Terry Lam"); |
| 735 | MODULE_AUTHOR("Nandita Dukkipati"); |
| 736 | MODULE_LICENSE("GPL"); |