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