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