1#ifndef __NET_SCHED_RED_H
2#define __NET_SCHED_RED_H
3
4#include <linux/types.h>
5#include <net/pkt_sched.h>
6#include <net/inet_ecn.h>
7#include <net/dsfield.h>
8
9
10
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#define RED_STAB_SIZE 256
91#define RED_STAB_MASK (RED_STAB_SIZE - 1)
92
93struct red_stats {
94 u32 prob_drop;
95 u32 prob_mark;
96 u32 forced_drop;
97 u32 forced_mark;
98 u32 pdrop;
99 u32 other;
100};
101
102struct red_parms {
103
104 u32 qth_min;
105 u32 qth_max;
106 u32 Scell_max;
107 u32 Rmask;
108 u8 Scell_log;
109 u8 Wlog;
110 u8 Plog;
111 u8 Stab[RED_STAB_SIZE];
112
113
114 int qcount;
115
116 u32 qR;
117
118 unsigned long qavg;
119 psched_time_t qidlestart;
120};
121
122static inline u32 red_rmask(u8 Plog)
123{
124 return Plog < 32 ? ((1 << Plog) - 1) : ~0UL;
125}
126
127static inline void red_set_parms(struct red_parms *p,
128 u32 qth_min, u32 qth_max, u8 Wlog, u8 Plog,
129 u8 Scell_log, u8 *stab)
130{
131
132
133
134
135 p->qavg = 0;
136
137 p->qcount = -1;
138 p->qth_min = qth_min << Wlog;
139 p->qth_max = qth_max << Wlog;
140 p->Wlog = Wlog;
141 p->Plog = Plog;
142 p->Rmask = red_rmask(Plog);
143 p->Scell_log = Scell_log;
144 p->Scell_max = (255 << Scell_log);
145
146 memcpy(p->Stab, stab, sizeof(p->Stab));
147}
148
149static inline int red_is_idling(struct red_parms *p)
150{
151 return p->qidlestart != PSCHED_PASTPERFECT;
152}
153
154static inline void red_start_of_idle_period(struct red_parms *p)
155{
156 p->qidlestart = psched_get_time();
157}
158
159static inline void red_end_of_idle_period(struct red_parms *p)
160{
161 p->qidlestart = PSCHED_PASTPERFECT;
162}
163
164static inline void red_restart(struct red_parms *p)
165{
166 red_end_of_idle_period(p);
167 p->qavg = 0;
168 p->qcount = -1;
169}
170
171static inline unsigned long red_calc_qavg_from_idle_time(struct red_parms *p)
172{
173 psched_time_t now;
174 long us_idle;
175 int shift;
176
177 now = psched_get_time();
178 us_idle = psched_tdiff_bounded(now, p->qidlestart, p->Scell_max);
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200 shift = p->Stab[(us_idle >> p->Scell_log) & RED_STAB_MASK];
201
202 if (shift)
203 return p->qavg >> shift;
204 else {
205
206
207
208
209
210
211
212 us_idle = (p->qavg * (u64)us_idle) >> p->Scell_log;
213
214 if (us_idle < (p->qavg >> 1))
215 return p->qavg - us_idle;
216 else
217 return p->qavg >> 1;
218 }
219}
220
221static inline unsigned long red_calc_qavg_no_idle_time(struct red_parms *p,
222 unsigned int backlog)
223{
224
225
226
227
228
229
230
231
232
233 return p->qavg + (backlog - (p->qavg >> p->Wlog));
234}
235
236static inline unsigned long red_calc_qavg(struct red_parms *p,
237 unsigned int backlog)
238{
239 if (!red_is_idling(p))
240 return red_calc_qavg_no_idle_time(p, backlog);
241 else
242 return red_calc_qavg_from_idle_time(p);
243}
244
245static inline u32 red_random(struct red_parms *p)
246{
247 return net_random() & p->Rmask;
248}
249
250static inline int red_mark_probability(struct red_parms *p, unsigned long qavg)
251{
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268 return !(((qavg - p->qth_min) >> p->Wlog) * p->qcount < p->qR);
269}
270
271enum {
272 RED_BELOW_MIN_THRESH,
273 RED_BETWEEN_TRESH,
274 RED_ABOVE_MAX_TRESH,
275};
276
277static inline int red_cmp_thresh(struct red_parms *p, unsigned long qavg)
278{
279 if (qavg < p->qth_min)
280 return RED_BELOW_MIN_THRESH;
281 else if (qavg >= p->qth_max)
282 return RED_ABOVE_MAX_TRESH;
283 else
284 return RED_BETWEEN_TRESH;
285}
286
287enum {
288 RED_DONT_MARK,
289 RED_PROB_MARK,
290 RED_HARD_MARK,
291};
292
293static inline int red_action(struct red_parms *p, unsigned long qavg)
294{
295 switch (red_cmp_thresh(p, qavg)) {
296 case RED_BELOW_MIN_THRESH:
297 p->qcount = -1;
298 return RED_DONT_MARK;
299
300 case RED_BETWEEN_TRESH:
301 if (++p->qcount) {
302 if (red_mark_probability(p, qavg)) {
303 p->qcount = 0;
304 p->qR = red_random(p);
305 return RED_PROB_MARK;
306 }
307 } else
308 p->qR = red_random(p);
309
310 return RED_DONT_MARK;
311
312 case RED_ABOVE_MAX_TRESH:
313 p->qcount = -1;
314 return RED_HARD_MARK;
315 }
316
317 BUG();
318 return RED_DONT_MARK;
319}
320
321#endif
322