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 | static inline codel_time_t codel_get_time(void) |

68 | { |

69 | u64 ns = ktime_get_ns(); |

70 | |

71 | 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 | static inline u32 codel_time_to_us(codel_time_t val) |

91 | { |

92 | u64 valns = ((u64)val << CODEL_SHIFT); |

93 | |

94 | do_div(valns, NSEC_PER_USEC); |

95 | 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 |

165 |