110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* net/sched/sch_hhf.c Heavy-Hitter Filter (HHF) 210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Copyright (C) 2013 Terry Lam <vtlam@google.com> 410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Copyright (C) 2013 Nandita Dukkipati <nanditad@google.com> 510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <linux/jhash.h> 810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <linux/jiffies.h> 910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <linux/module.h> 1010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <linux/skbuff.h> 1110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <linux/vmalloc.h> 1210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <net/flow_keys.h> 1310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <net/pkt_sched.h> 1410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#include <net/sock.h> 1510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 1610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Heavy-Hitter Filter (HHF) 1710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 1810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Principles : 1910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Flows are classified into two buckets: non-heavy-hitter and heavy-hitter 2010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * buckets. Initially, a new flow starts as non-heavy-hitter. Once classified 2110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * as heavy-hitter, it is immediately switched to the heavy-hitter bucket. 2210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * The buckets are dequeued by a Weighted Deficit Round Robin (WDRR) scheduler, 2310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * in which the heavy-hitter bucket is served with less weight. 2410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * In other words, non-heavy-hitters (e.g., short bursts of critical traffic) 2510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * are isolated from heavy-hitters (e.g., persistent bulk traffic) and also have 2610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * higher share of bandwidth. 2710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 2810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * To capture heavy-hitters, we use the "multi-stage filter" algorithm in the 2910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * following paper: 3010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * [EV02] C. Estan and G. Varghese, "New Directions in Traffic Measurement and 3110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Accounting", in ACM SIGCOMM, 2002. 3210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 3310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Conceptually, a multi-stage filter comprises k independent hash functions 3410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * and k counter arrays. Packets are indexed into k counter arrays by k hash 3510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * functions, respectively. The counters are then increased by the packet sizes. 3610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Therefore, 3710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - For a heavy-hitter flow: *all* of its k array counters must be large. 3810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - For a non-heavy-hitter flow: some of its k array counters can be large 3910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * due to hash collision with other small flows; however, with high 4010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * probability, not *all* k counters are large. 4110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 4210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * By the design of the multi-stage filter algorithm, the false negative rate 4310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * (heavy-hitters getting away uncaptured) is zero. However, the algorithm is 4410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * susceptible to false positives (non-heavy-hitters mistakenly classified as 4510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * heavy-hitters). 4610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Therefore, we also implement the following optimizations to reduce false 4710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * positives by avoiding unnecessary increment of the counter values: 4810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - Optimization O1: once a heavy-hitter is identified, its bytes are not 4910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * accounted in the array counters. This technique is called "shielding" 5010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * in Section 3.3.1 of [EV02]. 5110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - Optimization O2: conservative update of counters 5210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * (Section 3.3.2 of [EV02]), 5310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * New counter value = max {old counter value, 5410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * smallest counter value + packet bytes} 5510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 5610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Finally, we refresh the counters periodically since otherwise the counter 5710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * values will keep accumulating. 5810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 5910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Once a flow is classified as heavy-hitter, we also save its per-flow state 6010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * in an exact-matching flow table so that its subsequent packets can be 6110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * dispatched to the heavy-hitter bucket accordingly. 6210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 6310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 6410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * At a high level, this qdisc works as follows: 6510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Given a packet p: 6610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - If the flow-id of p (e.g., TCP 5-tuple) is already in the exact-matching 6710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * heavy-hitter flow table, denoted table T, then send p to the heavy-hitter 6810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * bucket. 6910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - Otherwise, forward p to the multi-stage filter, denoted filter F 7010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * + If F decides that p belongs to a non-heavy-hitter flow, then send p 7110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * to the non-heavy-hitter bucket. 7210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * + Otherwise, if F decides that p belongs to a new heavy-hitter flow, 7310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * then set up a new flow entry for the flow-id of p in the table T and 7410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * send p to the heavy-hitter bucket. 7510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 7610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * In this implementation: 7710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - T is a fixed-size hash-table with 1024 entries. Hash collision is 7810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * resolved by linked-list chaining. 7910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - F has four counter arrays, each array containing 1024 32-bit counters. 8010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * That means 4 * 1024 * 32 bits = 16KB of memory. 8110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - Since each array in F contains 1024 counters, 10 bits are sufficient to 8210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * index into each array. 8310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * Hence, instead of having four hash functions, we chop the 32-bit 8410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * skb-hash into three 10-bit chunks, and the remaining 10-bit chunk is 8510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * computed as XOR sum of those three chunks. 8610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - We need to clear the counter arrays periodically; however, directly 8710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * memsetting 16KB of memory can lead to cache eviction and unwanted delay. 8810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * So by representing each counter by a valid bit, we only need to reset 8910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 4K of 1 bit (i.e. 512 bytes) instead of 16KB of memory. 9010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * - The Deficit Round Robin engine is taken from fq_codel implementation 9110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * (net/sched/sch_fq_codel.c). Note that wdrr_bucket corresponds to 9210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * fq_codel_flow in fq_codel implementation. 9310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 9410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 9510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 9610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Non-configurable parameters */ 9710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define HH_FLOWS_CNT 1024 /* number of entries in exact-matching table T */ 9810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define HHF_ARRAYS_CNT 4 /* number of arrays in multi-stage filter F */ 9910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define HHF_ARRAYS_LEN 1024 /* number of counters in each array of F */ 10010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define HHF_BIT_MASK_LEN 10 /* masking 10 bits */ 10110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define HHF_BIT_MASK 0x3FF /* bitmask of 10 bits */ 10210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 10310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define WDRR_BUCKET_CNT 2 /* two buckets for Weighted DRR */ 10410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamenum wdrr_bucket_idx { 10510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam WDRR_BUCKET_FOR_HH = 0, /* bucket id for heavy-hitters */ 10610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam WDRR_BUCKET_FOR_NON_HH = 1 /* bucket id for non-heavy-hitters */ 10710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam}; 10810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 10910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam#define hhf_time_before(a, b) \ 11010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam (typecheck(u32, a) && typecheck(u32, b) && ((s32)((a) - (b)) < 0)) 11110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 11210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Heavy-hitter per-flow state */ 11310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstruct hh_flow_state { 11410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hash_id; /* hash of flow-id (e.g. TCP 5-tuple) */ 11510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hit_timestamp; /* last time heavy-hitter was seen */ 11610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head flowchain; /* chaining under hash collision */ 11710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam}; 11810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 11910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Weighted Deficit Round Robin (WDRR) scheduler */ 12010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstruct wdrr_bucket { 12110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *head; 12210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *tail; 12310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head bucketchain; 12410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int deficit; 12510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam}; 12610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 12710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstruct hhf_sched_data { 12810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct wdrr_bucket buckets[WDRR_BUCKET_CNT]; 12910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 perturbation; /* hash perturbation */ 13010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 quantum; /* psched_mtu(qdisc_dev(sch)); */ 13110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 drop_overlimit; /* number of times max qdisc packet 13210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * limit was hit 13310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 13410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head *hh_flows; /* table T (currently active HHs) */ 13510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hh_flows_limit; /* max active HH allocs */ 13610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hh_flows_overlimit; /* num of disallowed HH allocs */ 13710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hh_flows_total_cnt; /* total admitted HHs */ 13810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hh_flows_current_cnt; /* total current HHs */ 13910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 *hhf_arrays[HHF_ARRAYS_CNT]; /* HH filter F */ 14010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hhf_arrays_reset_timestamp; /* last time hhf_arrays 14110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * was reset 14210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 14310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam unsigned long *hhf_valid_bits[HHF_ARRAYS_CNT]; /* shadow valid bits 14410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * of hhf_arrays 14510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 14610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Similar to the "new_flows" vs. "old_flows" concept in fq_codel DRR */ 14710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head new_buckets; /* list of new buckets */ 14810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head old_buckets; /* list of old buckets */ 14910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 15010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Configurable HHF parameters */ 15110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hhf_reset_timeout; /* interval to reset counter 15210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * arrays in filter F 15310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * (default 40ms) 15410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 15510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hhf_admit_bytes; /* counter thresh to classify as 15610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * HH (default 128KB). 15710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * With these default values, 15810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * 128KB / 40ms = 25 Mbps 15910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * i.e., we expect to capture HHs 16010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * sending > 25 Mbps. 16110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 16210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hhf_evict_timeout; /* aging threshold to evict idle 16310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * HHs out of table T. This should 16410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * be large enough to avoid 16510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * reordering during HH eviction. 16610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * (default 1s) 16710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 16810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 hhf_non_hh_weight; /* WDRR weight for non-HHs 16910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * (default 2, 17010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * i.e., non-HH : HH = 2 : 1) 17110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 17210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam}; 17310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 17410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic u32 hhf_time_stamp(void) 17510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 17610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return jiffies; 17710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 17810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 17910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic unsigned int skb_hash(const struct hhf_sched_data *q, 18010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam const struct sk_buff *skb) 18110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 18210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct flow_keys keys; 18310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam unsigned int hash; 18410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 18510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (skb->sk && skb->sk->sk_hash) 18610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return skb->sk->sk_hash; 18710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 18810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam skb_flow_dissect(skb, &keys); 18910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hash = jhash_3words((__force u32)keys.dst, 19010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam (__force u32)keys.src ^ keys.ip_proto, 19110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam (__force u32)keys.ports, q->perturbation); 19210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return hash; 19310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 19410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 19510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Looks up a heavy-hitter flow in a chaining list of table T. */ 19610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic struct hh_flow_state *seek_list(const u32 hash, 19710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head *head, 19810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q) 19910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 20010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hh_flow_state *flow, *next; 20110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 now = hhf_time_stamp(); 20210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 20310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (list_empty(head)) 20410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NULL; 20510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 20610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_for_each_entry_safe(flow, next, head, flowchain) { 20710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 prev = flow->hit_timestamp + q->hhf_evict_timeout; 20810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 20910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (hhf_time_before(prev, now)) { 21010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Delete expired heavy-hitters, but preserve one entry 21110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * to avoid kzalloc() when next time this slot is hit. 21210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 21310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (list_is_last(&flow->flowchain, head)) 21410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NULL; 21510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_del(&flow->flowchain); 21610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam kfree(flow); 21710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_current_cnt--; 21810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } else if (flow->hash_id == hash) { 21910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return flow; 22010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 22110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 22210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NULL; 22310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 22410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 22510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Returns a flow state entry for a new heavy-hitter. Either reuses an expired 22610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * entry or dynamically alloc a new entry. 22710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 22810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic struct hh_flow_state *alloc_new_hh(struct list_head *head, 22910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q) 23010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 23110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hh_flow_state *flow; 23210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 now = hhf_time_stamp(); 23310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 23410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!list_empty(head)) { 23510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Find an expired heavy-hitter flow entry. */ 23610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_for_each_entry(flow, head, flowchain) { 23710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 prev = flow->hit_timestamp + q->hhf_evict_timeout; 23810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 23910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (hhf_time_before(prev, now)) 24010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return flow; 24110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 24210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 24310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 24410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (q->hh_flows_current_cnt >= q->hh_flows_limit) { 24510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_overlimit++; 24610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NULL; 24710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 24810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Create new entry. */ 24910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow = kzalloc(sizeof(struct hh_flow_state), GFP_ATOMIC); 25010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!flow) 25110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NULL; 25210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 25310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_current_cnt++; 25410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam INIT_LIST_HEAD(&flow->flowchain); 25510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_add_tail(&flow->flowchain, head); 25610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 25710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return flow; 25810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 25910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 26010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Assigns packets to WDRR buckets. Implements a multi-stage filter to 26110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * classify heavy-hitters. 26210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 26310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic enum wdrr_bucket_idx hhf_classify(struct sk_buff *skb, struct Qdisc *sch) 26410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 26510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 26610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 tmp_hash, hash; 26710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 xorsum, filter_pos[HHF_ARRAYS_CNT], flow_pos; 26810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hh_flow_state *flow; 26910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 pkt_len, min_hhf_val; 27010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int i; 27110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 prev; 27210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 now = hhf_time_stamp(); 27310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 27410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Reset the HHF counter arrays if this is the right time. */ 27510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam prev = q->hhf_arrays_reset_timestamp + q->hhf_reset_timeout; 27610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (hhf_time_before(prev, now)) { 27710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT; i++) 27810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bitmap_zero(q->hhf_valid_bits[i], HHF_ARRAYS_LEN); 27910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_arrays_reset_timestamp = now; 28010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 28110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 28210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Get hashed flow-id of the skb. */ 28310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hash = skb_hash(q, skb); 28410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 28510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Check if this packet belongs to an already established HH flow. */ 28610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow_pos = hash & HHF_BIT_MASK; 28710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow = seek_list(hash, &q->hh_flows[flow_pos], q); 28810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (flow) { /* found its HH flow */ 28910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow->hit_timestamp = now; 29010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return WDRR_BUCKET_FOR_HH; 29110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 29210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 29310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Now pass the packet through the multi-stage filter. */ 29410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam tmp_hash = hash; 29510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam xorsum = 0; 29610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT - 1; i++) { 29710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Split the skb_hash into three 10-bit chunks. */ 29810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam filter_pos[i] = tmp_hash & HHF_BIT_MASK; 29910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam xorsum ^= filter_pos[i]; 30010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam tmp_hash >>= HHF_BIT_MASK_LEN; 30110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 30210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* The last chunk is computed as XOR sum of other chunks. */ 30310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam filter_pos[HHF_ARRAYS_CNT - 1] = xorsum ^ tmp_hash; 30410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 30510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam pkt_len = qdisc_pkt_len(skb); 30610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam min_hhf_val = ~0U; 30710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT; i++) { 30810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 val; 30910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 31010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!test_bit(filter_pos[i], q->hhf_valid_bits[i])) { 31110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_arrays[i][filter_pos[i]] = 0; 31210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam __set_bit(filter_pos[i], q->hhf_valid_bits[i]); 31310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 31410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 31510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam val = q->hhf_arrays[i][filter_pos[i]] + pkt_len; 31610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (min_hhf_val > val) 31710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam min_hhf_val = val; 31810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 31910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 32010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Found a new HH iff all counter values > HH admit threshold. */ 32110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (min_hhf_val > q->hhf_admit_bytes) { 32210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Just captured a new heavy-hitter. */ 32310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow = alloc_new_hh(&q->hh_flows[flow_pos], q); 32410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!flow) /* memory alloc problem */ 32510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return WDRR_BUCKET_FOR_NON_HH; 32610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow->hash_id = hash; 32710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam flow->hit_timestamp = now; 32810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_total_cnt++; 32910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 33010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* By returning without updating counters in q->hhf_arrays, 33110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * we implicitly implement "shielding" (see Optimization O1). 33210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 33310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return WDRR_BUCKET_FOR_HH; 33410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 33510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 33610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Conservative update of HHF arrays (see Optimization O2). */ 33710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT; i++) { 33810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (q->hhf_arrays[i][filter_pos[i]] < min_hhf_val) 33910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_arrays[i][filter_pos[i]] = min_hhf_val; 34010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 34110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return WDRR_BUCKET_FOR_NON_HH; 34210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 34310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 34410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Removes one skb from head of bucket. */ 34510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic struct sk_buff *dequeue_head(struct wdrr_bucket *bucket) 34610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 34710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *skb = bucket->head; 34810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 34910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->head = skb->next; 35010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam skb->next = NULL; 35110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return skb; 35210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 35310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 35410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam/* Tail-adds skb to bucket. */ 35510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic void bucket_add(struct wdrr_bucket *bucket, struct sk_buff *skb) 35610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 35710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (bucket->head == NULL) 35810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->head = skb; 35910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam else 36010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->tail->next = skb; 36110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->tail = skb; 36210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam skb->next = NULL; 36310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 36410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 36510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic unsigned int hhf_drop(struct Qdisc *sch) 36610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 36710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 36810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct wdrr_bucket *bucket; 36910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 37010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Always try to drop from heavy-hitters first. */ 37110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket = &q->buckets[WDRR_BUCKET_FOR_HH]; 37210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!bucket->head) 37310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket = &q->buckets[WDRR_BUCKET_FOR_NON_HH]; 37410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 37510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (bucket->head) { 37610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *skb = dequeue_head(bucket); 37710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 37810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam sch->q.qlen--; 37925331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_drop(sch); 38025331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_backlog_dec(sch, skb); 38110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam kfree_skb(skb); 38210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 38310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 38410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Return id of the bucket from which the packet was dropped. */ 38510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return bucket - q->buckets; 38610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 38710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 38810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic int hhf_enqueue(struct sk_buff *skb, struct Qdisc *sch) 38910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 39010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 39110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam enum wdrr_bucket_idx idx; 39210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct wdrr_bucket *bucket; 39310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 39410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam idx = hhf_classify(skb, sch); 39510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 39610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket = &q->buckets[idx]; 39710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket_add(bucket, skb); 39825331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_backlog_inc(sch, skb); 39910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 40010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (list_empty(&bucket->bucketchain)) { 40110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam unsigned int weight; 40210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 40310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* The logic of new_buckets vs. old_buckets is the same as 40410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * new_flows vs. old_flows in the implementation of fq_codel, 40510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * i.e., short bursts of non-HHs should have strict priority. 40610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 40710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (idx == WDRR_BUCKET_FOR_HH) { 40810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Always move heavy-hitters to old bucket. */ 40910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam weight = 1; 41010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_add_tail(&bucket->bucketchain, &q->old_buckets); 41110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } else { 41210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam weight = q->hhf_non_hh_weight; 41310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_add_tail(&bucket->bucketchain, &q->new_buckets); 41410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 41510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->deficit = weight * q->quantum; 41610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 417b2ce49e7375ff5b9b133c474875dfbd97ef00ef7Yang Yingliang if (++sch->q.qlen <= sch->limit) 41810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NET_XMIT_SUCCESS; 41910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 42010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->drop_overlimit++; 42110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Return Congestion Notification only if we dropped a packet from this 42210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam * bucket. 42310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam */ 42410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (hhf_drop(sch) == idx) 42510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NET_XMIT_CN; 42610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 42710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* As we dropped a packet, better let upper stack know this. */ 42810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam qdisc_tree_decrease_qlen(sch, 1); 42910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NET_XMIT_SUCCESS; 43010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 43110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 43210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic struct sk_buff *hhf_dequeue(struct Qdisc *sch) 43310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 43410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 43510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *skb = NULL; 43610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct wdrr_bucket *bucket; 43710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head *head; 43810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 43910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lambegin: 44010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam head = &q->new_buckets; 44110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (list_empty(head)) { 44210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam head = &q->old_buckets; 44310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (list_empty(head)) 44410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return NULL; 44510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 44610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket = list_first_entry(head, struct wdrr_bucket, bucketchain); 44710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 44810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (bucket->deficit <= 0) { 44910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int weight = (bucket - q->buckets == WDRR_BUCKET_FOR_HH) ? 45010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 1 : q->hhf_non_hh_weight; 45110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 45210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->deficit += weight * q->quantum; 45310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_move_tail(&bucket->bucketchain, &q->old_buckets); 45410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam goto begin; 45510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 45610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 45710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (bucket->head) { 45810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam skb = dequeue_head(bucket); 45910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam sch->q.qlen--; 46025331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_backlog_dec(sch, skb); 46110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 46210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 46310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!skb) { 46410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Force a pass through old_buckets to prevent starvation. */ 46510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if ((head == &q->new_buckets) && !list_empty(&q->old_buckets)) 46610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_move_tail(&bucket->bucketchain, &q->old_buckets); 46710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam else 46810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_del_init(&bucket->bucketchain); 46910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam goto begin; 47010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 47110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam qdisc_bstats_update(sch, skb); 47210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam bucket->deficit -= qdisc_pkt_len(skb); 47310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 47410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return skb; 47510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 47610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 47710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic void hhf_reset(struct Qdisc *sch) 47810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 47910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *skb; 48010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 48110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam while ((skb = hhf_dequeue(sch)) != NULL) 48210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam kfree_skb(skb); 48310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 48410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 48510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic void *hhf_zalloc(size_t sz) 48610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 48710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam void *ptr = kzalloc(sz, GFP_KERNEL | __GFP_NOWARN); 48810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 48910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!ptr) 49010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam ptr = vzalloc(sz); 49110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 49210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return ptr; 49310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 49410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 49510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic void hhf_free(void *addr) 49610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 4974cb28970a23ff209199b0a4358d68efe82c8f493WANG Cong kvfree(addr); 49810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 49910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 50010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic void hhf_destroy(struct Qdisc *sch) 50110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 50210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int i; 50310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 50410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 50510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT; i++) { 50610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hhf_free(q->hhf_arrays[i]); 50710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hhf_free(q->hhf_valid_bits[i]); 50810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 50910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 51010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HH_FLOWS_CNT; i++) { 51110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hh_flow_state *flow, *next; 51210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct list_head *head = &q->hh_flows[i]; 51310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 51410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (list_empty(head)) 51510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam continue; 51610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_for_each_entry_safe(flow, next, head, flowchain) { 51710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam list_del(&flow->flowchain); 51810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam kfree(flow); 51910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 52010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 52110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hhf_free(q->hh_flows); 52210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 52310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 52410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic const struct nla_policy hhf_policy[TCA_HHF_MAX + 1] = { 52510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_BACKLOG_LIMIT] = { .type = NLA_U32 }, 52610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_QUANTUM] = { .type = NLA_U32 }, 52710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_HH_FLOWS_LIMIT] = { .type = NLA_U32 }, 52810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_RESET_TIMEOUT] = { .type = NLA_U32 }, 52910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_ADMIT_BYTES] = { .type = NLA_U32 }, 53010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_EVICT_TIMEOUT] = { .type = NLA_U32 }, 53110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam [TCA_HHF_NON_HH_WEIGHT] = { .type = NLA_U32 }, 53210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam}; 53310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 53410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic int hhf_change(struct Qdisc *sch, struct nlattr *opt) 53510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 53610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 53710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct nlattr *tb[TCA_HHF_MAX + 1]; 53810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam unsigned int qlen; 53910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int err; 54010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u64 non_hh_quantum; 54110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 new_quantum = q->quantum; 54210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam u32 new_hhf_non_hh_weight = q->hhf_non_hh_weight; 54310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 54410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!opt) 54510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return -EINVAL; 54610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 54710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam err = nla_parse_nested(tb, TCA_HHF_MAX, opt, hhf_policy); 54810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (err < 0) 54910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return err; 55010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 55110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (tb[TCA_HHF_QUANTUM]) 55210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam new_quantum = nla_get_u32(tb[TCA_HHF_QUANTUM]); 55310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 55410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (tb[TCA_HHF_NON_HH_WEIGHT]) 55510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam new_hhf_non_hh_weight = nla_get_u32(tb[TCA_HHF_NON_HH_WEIGHT]); 55610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 55710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam non_hh_quantum = (u64)new_quantum * new_hhf_non_hh_weight; 55810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (non_hh_quantum > INT_MAX) 55910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return -EINVAL; 560f6a082fed1e6407c2f4437d0d963b1bcbe5f9f58John Fastabend 561f6a082fed1e6407c2f4437d0d963b1bcbe5f9f58John Fastabend sch_tree_lock(sch); 562f6a082fed1e6407c2f4437d0d963b1bcbe5f9f58John Fastabend 563f6a082fed1e6407c2f4437d0d963b1bcbe5f9f58John Fastabend if (tb[TCA_HHF_BACKLOG_LIMIT]) 564f6a082fed1e6407c2f4437d0d963b1bcbe5f9f58John Fastabend sch->limit = nla_get_u32(tb[TCA_HHF_BACKLOG_LIMIT]); 565f6a082fed1e6407c2f4437d0d963b1bcbe5f9f58John Fastabend 56610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->quantum = new_quantum; 56710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_non_hh_weight = new_hhf_non_hh_weight; 56810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 56910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (tb[TCA_HHF_HH_FLOWS_LIMIT]) 57010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_limit = nla_get_u32(tb[TCA_HHF_HH_FLOWS_LIMIT]); 57110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 57210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (tb[TCA_HHF_RESET_TIMEOUT]) { 5736c76a07a711165a31332aa619215f961b115071dTerry Lam u32 us = nla_get_u32(tb[TCA_HHF_RESET_TIMEOUT]); 57410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 5756c76a07a711165a31332aa619215f961b115071dTerry Lam q->hhf_reset_timeout = usecs_to_jiffies(us); 57610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 57710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 57810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (tb[TCA_HHF_ADMIT_BYTES]) 57910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_admit_bytes = nla_get_u32(tb[TCA_HHF_ADMIT_BYTES]); 58010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 58110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (tb[TCA_HHF_EVICT_TIMEOUT]) { 5826c76a07a711165a31332aa619215f961b115071dTerry Lam u32 us = nla_get_u32(tb[TCA_HHF_EVICT_TIMEOUT]); 58310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 5846c76a07a711165a31332aa619215f961b115071dTerry Lam q->hhf_evict_timeout = usecs_to_jiffies(us); 58510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 58610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 58710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam qlen = sch->q.qlen; 58810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam while (sch->q.qlen > sch->limit) { 58910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct sk_buff *skb = hhf_dequeue(sch); 59010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 59110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam kfree_skb(skb); 59210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 59310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen); 59410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 59510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam sch_tree_unlock(sch); 59610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return 0; 59710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 59810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 59910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic int hhf_init(struct Qdisc *sch, struct nlattr *opt) 60010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 60110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 60210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int i; 60310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 60410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam sch->limit = 1000; 60510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->quantum = psched_mtu(qdisc_dev(sch)); 60663862b5bef7349dd1137e4c70702c67d77565785Aruna-Hewapathirane q->perturbation = prandom_u32(); 60710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam INIT_LIST_HEAD(&q->new_buckets); 60810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam INIT_LIST_HEAD(&q->old_buckets); 60910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 61010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Configurable HHF parameters */ 61110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_reset_timeout = HZ / 25; /* 40 ms */ 61210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_admit_bytes = 131072; /* 128 KB */ 61310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_evict_timeout = HZ; /* 1 sec */ 61410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_non_hh_weight = 2; 61510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 61610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (opt) { 61710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam int err = hhf_change(sch, opt); 61810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 61910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (err) 62010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return err; 62110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 62210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 62310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!q->hh_flows) { 62410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Initialize heavy-hitter flow table. */ 62510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows = hhf_zalloc(HH_FLOWS_CNT * 62610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam sizeof(struct list_head)); 62710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!q->hh_flows) 62810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return -ENOMEM; 62910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HH_FLOWS_CNT; i++) 63010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam INIT_LIST_HEAD(&q->hh_flows[i]); 63110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 63210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Cap max active HHs at twice len of hh_flows table. */ 63310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_limit = 2 * HH_FLOWS_CNT; 63410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_overlimit = 0; 63510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_total_cnt = 0; 63610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hh_flows_current_cnt = 0; 63710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 63810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Initialize heavy-hitter filter arrays. */ 63910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT; i++) { 64010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_arrays[i] = hhf_zalloc(HHF_ARRAYS_LEN * 64110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam sizeof(u32)); 64210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!q->hhf_arrays[i]) { 64310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hhf_destroy(sch); 64410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return -ENOMEM; 64510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 64610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 64710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_arrays_reset_timestamp = hhf_time_stamp(); 64810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 64910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Initialize valid bits of heavy-hitter filter arrays. */ 65010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < HHF_ARRAYS_CNT; i++) { 65110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam q->hhf_valid_bits[i] = hhf_zalloc(HHF_ARRAYS_LEN / 65210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam BITS_PER_BYTE); 65310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (!q->hhf_valid_bits[i]) { 65410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam hhf_destroy(sch); 65510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return -ENOMEM; 65610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 65710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 65810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 65910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam /* Initialize Weighted DRR buckets. */ 66010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam for (i = 0; i < WDRR_BUCKET_CNT; i++) { 66110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct wdrr_bucket *bucket = q->buckets + i; 66210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 66310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam INIT_LIST_HEAD(&bucket->bucketchain); 66410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 66510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam } 66610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 66710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return 0; 66810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 66910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 67010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic int hhf_dump(struct Qdisc *sch, struct sk_buff *skb) 67110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 67210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 67310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct nlattr *opts; 67410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 67510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam opts = nla_nest_start(skb, TCA_OPTIONS); 67610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (opts == NULL) 67710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam goto nla_put_failure; 67810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 67910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam if (nla_put_u32(skb, TCA_HHF_BACKLOG_LIMIT, sch->limit) || 68010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam nla_put_u32(skb, TCA_HHF_QUANTUM, q->quantum) || 68110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam nla_put_u32(skb, TCA_HHF_HH_FLOWS_LIMIT, q->hh_flows_limit) || 68210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam nla_put_u32(skb, TCA_HHF_RESET_TIMEOUT, 6836c76a07a711165a31332aa619215f961b115071dTerry Lam jiffies_to_usecs(q->hhf_reset_timeout)) || 68410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam nla_put_u32(skb, TCA_HHF_ADMIT_BYTES, q->hhf_admit_bytes) || 68510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam nla_put_u32(skb, TCA_HHF_EVICT_TIMEOUT, 6866c76a07a711165a31332aa619215f961b115071dTerry Lam jiffies_to_usecs(q->hhf_evict_timeout)) || 68710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam nla_put_u32(skb, TCA_HHF_NON_HH_WEIGHT, q->hhf_non_hh_weight)) 68810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam goto nla_put_failure; 68910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 690d59b7d8059ddc4f9ac1f0904d28ea62a252e8de7Yang Yingliang return nla_nest_end(skb, opts); 69110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 69210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamnla_put_failure: 69310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return -1; 69410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 69510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 69610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic int hhf_dump_stats(struct Qdisc *sch, struct gnet_dump *d) 69710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 69810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct hhf_sched_data *q = qdisc_priv(sch); 69910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam struct tc_hhf_xstats st = { 70010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .drop_overlimit = q->drop_overlimit, 70110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .hh_overlimit = q->hh_flows_overlimit, 70210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .hh_tot_count = q->hh_flows_total_cnt, 70310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .hh_cur_count = q->hh_flows_current_cnt, 70410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam }; 70510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 70610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return gnet_stats_copy_app(d, &st, sizeof(st)); 70710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 70810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 709c49fa257ba260410c76ab6e7f66fa1ec2dab3faastephen hemmingerstatic struct Qdisc_ops hhf_qdisc_ops __read_mostly = { 71010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .id = "hhf", 71110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .priv_size = sizeof(struct hhf_sched_data), 71210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 71310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .enqueue = hhf_enqueue, 71410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .dequeue = hhf_dequeue, 71510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .peek = qdisc_peek_dequeued, 71610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .drop = hhf_drop, 71710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .init = hhf_init, 71810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .reset = hhf_reset, 71910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .destroy = hhf_destroy, 72010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .change = hhf_change, 72110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .dump = hhf_dump, 72210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .dump_stats = hhf_dump_stats, 72310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam .owner = THIS_MODULE, 72410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam}; 72510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 72610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic int __init hhf_module_init(void) 72710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 72810239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam return register_qdisc(&hhf_qdisc_ops); 72910239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 73010239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 73110239edf86f137ce4c39b62ea9575e8053c549a0Terry Lamstatic void __exit hhf_module_exit(void) 73210239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam{ 73310239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam unregister_qdisc(&hhf_qdisc_ops); 73410239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam} 73510239edf86f137ce4c39b62ea9575e8053c549a0Terry Lam 73610239edf86f137ce4c39b62ea9575e8053c549a0Terry Lammodule_init(hhf_module_init) 73710239edf86f137ce4c39b62ea9575e8053c549a0Terry Lammodule_exit(hhf_module_exit) 73810239edf86f137ce4c39b62ea9575e8053c549a0Terry LamMODULE_AUTHOR("Terry Lam"); 73910239edf86f137ce4c39b62ea9575e8053c549a0Terry LamMODULE_AUTHOR("Nandita Dukkipati"); 74010239edf86f137ce4c39b62ea9575e8053c549a0Terry LamMODULE_LICENSE("GPL"); 741