include/net/codel.h

0001 #ifndef __NET_SCHED_CODEL_H
0002 #define __NET_SCHED_CODEL_H
0003
0004 /*
0005  * Codel - The Controlled-Delay Active Queue Management algorithm
0006  *
0007  *  Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com>
0008  *  Copyright (C) 2011-2012 Van Jacobson <van@pollere.net>
0009  *  Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net>
0010  *  Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com>
0011  *
0012  * Redistribution and use in source and binary forms, with or without
0013  * modification, are permitted provided that the following conditions
0014  * are met:
0015  * 1. Redistributions of source code must retain the above copyright
0016  *    notice, this list of conditions, and the following disclaimer,
0017  *    without modification.
0018  * 2. Redistributions in binary form must reproduce the above copyright
0019  *    notice, this list of conditions and the following disclaimer in the
0020  *    documentation and/or other materials provided with the distribution.
0021  * 3. The names of the authors may not be used to endorse or promote products
0022  *    derived from this software without specific prior written permission.
0023  *
0024  * Alternatively, provided that this notice is retained in full, this
0025  * software may be distributed under the terms of the GNU General
0026  * Public License ("GPL") version 2, in which case the provisions of the
0027  * GPL apply INSTEAD OF those given above.
0028  *
0029  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0030  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0031  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
0032  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0033  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0034  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0035  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0036  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0037  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0038  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0039  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
0040  * DAMAGE.
0041  *
0042  */
0043
0044 #include <linux/types.h>
0045 #include <linux/ktime.h>
0046 #include <linux/skbuff.h>
0047
0048 /* Controlling Queue Delay (CoDel) algorithm
0049  * =========================================
0050  * Source : Kathleen Nichols and Van Jacobson
0051  * http://queue.acm.org/detail.cfm?id=2209336
0052  *
0053  * Implemented on linux by Dave Taht and Eric Dumazet
0054  */
0055
0056
0057 /* CoDel uses a 1024 nsec clock, encoded in u32
0058  * This gives a range of 2199 seconds, because of signed compares
0059  */
0060 typedef u32 codel_time_t;
0061 typedef s32 codel_tdiff_t;
0062 #define CODEL_SHIFT 10
0063 #define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
0064
0065 static inline codel_time_t codel_get_time(void)
0066 {
0067     u64 ns = ktime_get_ns();
0068
0069     return ns >> CODEL_SHIFT;
0070 }
0071
0072 /* Dealing with timer wrapping, according to RFC 1982, as desc in wikipedia:
0073  *  https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution
0074  * codel_time_after(a,b) returns true if the time a is after time b.
0075  */
0076 #define codel_time_after(a, b)                      \
0077     (typecheck(codel_time_t, a) &&                  \
0078      typecheck(codel_time_t, b) &&                  \
0079      ((s32)((a) - (b)) > 0))
0080 #define codel_time_before(a, b)     codel_time_after(b, a)
0081
0082 #define codel_time_after_eq(a, b)                   \
0083     (typecheck(codel_time_t, a) &&                  \
0084      typecheck(codel_time_t, b) &&                  \
0085      ((s32)((a) - (b)) >= 0))
0086 #define codel_time_before_eq(a, b)  codel_time_after_eq(b, a)
0087
0088 static inline u32 codel_time_to_us(codel_time_t val)
0089 {
0090     u64 valns = ((u64)val << CODEL_SHIFT);
0091
0092     do_div(valns, NSEC_PER_USEC);
0093     return (u32)valns;
0094 }
0095
0096 /**
0097  * struct codel_params - contains codel parameters
0098  * @target: target queue size (in time units)
0099  * @ce_threshold:  threshold for marking packets with ECN CE
0100  * @interval:   width of moving time window
0101  * @mtu:    device mtu, or minimal queue backlog in bytes.
0102  * @ecn:    is Explicit Congestion Notification enabled
0103  * @ce_threshold_selector: apply ce_threshold to packets matching this value
0104  *                         in the diffserv/ECN byte of the IP header
0105  * @ce_threshold_mask: mask to apply to ce_threshold_selector comparison
0106  */
0107 struct codel_params {
0108     codel_time_t    target;
0109     codel_time_t    ce_threshold;
0110     codel_time_t    interval;
0111     u32     mtu;
0112     bool        ecn;
0113     u8      ce_threshold_selector;
0114     u8      ce_threshold_mask;
0115 };
0116
0117 /**
0118  * struct codel_vars - contains codel variables
0119  * @count:      how many drops we've done since the last time we
0120  *          entered dropping state
0121  * @lastcount:      count at entry to dropping state
0122  * @dropping:       set to true if in dropping state
0123  * @rec_inv_sqrt:   reciprocal value of sqrt(count) >> 1
0124  * @first_above_time:   when we went (or will go) continuously above target
0125  *          for interval
0126  * @drop_next:      time to drop next packet, or when we dropped last
0127  * @ldelay:     sojourn time of last dequeued packet
0128  */
0129 struct codel_vars {
0130     u32     count;
0131     u32     lastcount;
0132     bool        dropping;
0133     u16     rec_inv_sqrt;
0134     codel_time_t    first_above_time;
0135     codel_time_t    drop_next;
0136     codel_time_t    ldelay;
0137 };
0138
0139 #define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */
0140 /* needed shift to get a Q0.32 number from rec_inv_sqrt */
0141 #define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
0142
0143 /**
0144  * struct codel_stats - contains codel shared variables and stats
0145  * @maxpacket:  largest packet we've seen so far
0146  * @drop_count: temp count of dropped packets in dequeue()
0147  * @drop_len:   bytes of dropped packets in dequeue()
0148  * ecn_mark:    number of packets we ECN marked instead of dropping
0149  * ce_mark: number of packets CE marked because sojourn time was above ce_threshold
0150  */
0151 struct codel_stats {
0152     u32     maxpacket;
0153     u32     drop_count;
0154     u32     drop_len;
0155     u32     ecn_mark;
0156     u32     ce_mark;
0157 };
0158
0159 #define CODEL_DISABLED_THRESHOLD INT_MAX
0160
0161 typedef u32 (*codel_skb_len_t)(const struct sk_buff *skb);
0162 typedef codel_time_t (*codel_skb_time_t)(const struct sk_buff *skb);
0163 typedef void (*codel_skb_drop_t)(struct sk_buff *skb, void *ctx);
0164 typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars,
0165                         void *ctx);
0166
0167 #endif