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