Branch data Line data Source code
1 : : #ifndef __NET_SCHED_CODEL_H 2 : : #define __NET_SCHED_CODEL_H 3 : : 4 : : /* 5 : : * Codel - The Controlled-Delay Active Queue Management algorithm 6 : : * 7 : : * Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com> 8 : : * Copyright (C) 2011-2012 Van Jacobson <van@pollere.net> 9 : : * Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net> 10 : : * Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com> 11 : : * 12 : : * Redistribution and use in source and binary forms, with or without 13 : : * modification, are permitted provided that the following conditions 14 : : * are met: 15 : : * 1. Redistributions of source code must retain the above copyright 16 : : * notice, this list of conditions, and the following disclaimer, 17 : : * without modification. 18 : : * 2. Redistributions in binary form must reproduce the above copyright 19 : : * notice, this list of conditions and the following disclaimer in the 20 : : * documentation and/or other materials provided with the distribution. 21 : : * 3. The names of the authors may not be used to endorse or promote products 22 : : * derived from this software without specific prior written permission. 23 : : * 24 : : * Alternatively, provided that this notice is retained in full, this 25 : : * software may be distributed under the terms of the GNU General 26 : : * Public License ("GPL") version 2, in which case the provisions of the 27 : : * GPL apply INSTEAD OF those given above. 28 : : * 29 : : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 30 : : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 31 : : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 32 : : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 33 : : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 34 : : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 35 : : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 36 : : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 37 : : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 38 : : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 39 : : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 40 : : * DAMAGE. 41 : : * 42 : : */ 43 : : 44 : : #include <linux/types.h> 45 : : #include <linux/ktime.h> 46 : : #include <linux/skbuff.h> 47 : : #include <net/pkt_sched.h> 48 : : #include <net/inet_ecn.h> 49 : : 50 : : /* Controlling Queue Delay (CoDel) algorithm 51 : : * ========================================= 52 : : * Source : Kathleen Nichols and Van Jacobson 53 : : * http://queue.acm.org/detail.cfm?id=2209336 54 : : * 55 : : * Implemented on linux by Dave Taht and Eric Dumazet 56 : : */ 57 : : 58 : : 59 : : /* CoDel uses a 1024 nsec clock, encoded in u32 60 : : * This gives a range of 2199 seconds, because of signed compares 61 : : */ 62 : : typedef u32 codel_time_t; 63 : : typedef s32 codel_tdiff_t; 64 : : #define CODEL_SHIFT 10 65 : : #define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT) 66 : : 67 : 0 : static inline codel_time_t codel_get_time(void) 68 : : { 69 : 0 : u64 ns = ktime_get_ns(); 70 : : 71 : 0 : return ns >> CODEL_SHIFT; 72 : : } 73 : : 74 : : /* Dealing with timer wrapping, according to RFC 1982, as desc in wikipedia: 75 : : * https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution 76 : : * codel_time_after(a,b) returns true if the time a is after time b. 77 : : */ 78 : : #define codel_time_after(a, b) \ 79 : : (typecheck(codel_time_t, a) && \ 80 : : typecheck(codel_time_t, b) && \ 81 : : ((s32)((a) - (b)) > 0)) 82 : : #define codel_time_before(a, b) codel_time_after(b, a) 83 : : 84 : : #define codel_time_after_eq(a, b) \ 85 : : (typecheck(codel_time_t, a) && \ 86 : : typecheck(codel_time_t, b) && \ 87 : : ((s32)((a) - (b)) >= 0)) 88 : : #define codel_time_before_eq(a, b) codel_time_after_eq(b, a) 89 : : 90 : 0 : static inline u32 codel_time_to_us(codel_time_t val) 91 : : { 92 : 0 : u64 valns = ((u64)val << CODEL_SHIFT); 93 : : 94 : 0 : do_div(valns, NSEC_PER_USEC); 95 : 0 : return (u32)valns; 96 : : } 97 : : 98 : : /** 99 : : * struct codel_params - contains codel parameters 100 : : * @target: target queue size (in time units) 101 : : * @ce_threshold: threshold for marking packets with ECN CE 102 : : * @interval: width of moving time window 103 : : * @mtu: device mtu, or minimal queue backlog in bytes. 104 : : * @ecn: is Explicit Congestion Notification enabled 105 : : */ 106 : : struct codel_params { 107 : : codel_time_t target; 108 : : codel_time_t ce_threshold; 109 : : codel_time_t interval; 110 : : u32 mtu; 111 : : bool ecn; 112 : : }; 113 : : 114 : : /** 115 : : * struct codel_vars - contains codel variables 116 : : * @count: how many drops we've done since the last time we 117 : : * entered dropping state 118 : : * @lastcount: count at entry to dropping state 119 : : * @dropping: set to true if in dropping state 120 : : * @rec_inv_sqrt: reciprocal value of sqrt(count) >> 1 121 : : * @first_above_time: when we went (or will go) continuously above target 122 : : * for interval 123 : : * @drop_next: time to drop next packet, or when we dropped last 124 : : * @ldelay: sojourn time of last dequeued packet 125 : : */ 126 : : struct codel_vars { 127 : : u32 count; 128 : : u32 lastcount; 129 : : bool dropping; 130 : : u16 rec_inv_sqrt; 131 : : codel_time_t first_above_time; 132 : : codel_time_t drop_next; 133 : : codel_time_t ldelay; 134 : : }; 135 : : 136 : : #define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */ 137 : : /* needed shift to get a Q0.32 number from rec_inv_sqrt */ 138 : : #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS) 139 : : 140 : : /** 141 : : * struct codel_stats - contains codel shared variables and stats 142 : : * @maxpacket: largest packet we've seen so far 143 : : * @drop_count: temp count of dropped packets in dequeue() 144 : : * @drop_len: bytes of dropped packets in dequeue() 145 : : * ecn_mark: number of packets we ECN marked instead of dropping 146 : : * ce_mark: number of packets CE marked because sojourn time was above ce_threshold 147 : : */ 148 : : struct codel_stats { 149 : : u32 maxpacket; 150 : : u32 drop_count; 151 : : u32 drop_len; 152 : : u32 ecn_mark; 153 : : u32 ce_mark; 154 : : }; 155 : : 156 : : #define CODEL_DISABLED_THRESHOLD INT_MAX 157 : : 158 : : typedef u32 (*codel_skb_len_t)(const struct sk_buff *skb); 159 : : typedef codel_time_t (*codel_skb_time_t)(const struct sk_buff *skb); 160 : : typedef void (*codel_skb_drop_t)(struct sk_buff *skb, void *ctx); 161 : : typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars, 162 : : void *ctx); 163 : : 164 : : #endif