red.h 10.3 KB
Newer Older
1
/* SPDX-License-Identifier: GPL-2.0 */
Thomas Graf's avatar
Thomas Graf committed
2 3 4 5
#ifndef __NET_SCHED_RED_H
#define __NET_SCHED_RED_H

#include <linux/types.h>
6
#include <linux/bug.h>
Thomas Graf's avatar
Thomas Graf committed
7 8 9
#include <net/pkt_sched.h>
#include <net/inet_ecn.h>
#include <net/dsfield.h>
Eric Dumazet's avatar
Eric Dumazet committed
10
#include <linux/reciprocal_div.h>
Thomas Graf's avatar
Thomas Graf committed
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 91 92

/*	Random Early Detection (RED) algorithm.
	=======================================

	Source: Sally Floyd and Van Jacobson, "Random Early Detection Gateways
	for Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking.

	This file codes a "divisionless" version of RED algorithm
	as written down in Fig.17 of the paper.

	Short description.
	------------------

	When a new packet arrives we calculate the average queue length:

	avg = (1-W)*avg + W*current_queue_len,

	W is the filter time constant (chosen as 2^(-Wlog)), it controls
	the inertia of the algorithm. To allow larger bursts, W should be
	decreased.

	if (avg > th_max) -> packet marked (dropped).
	if (avg < th_min) -> packet passes.
	if (th_min < avg < th_max) we calculate probability:

	Pb = max_P * (avg - th_min)/(th_max-th_min)

	and mark (drop) packet with this probability.
	Pb changes from 0 (at avg==th_min) to max_P (avg==th_max).
	max_P should be small (not 1), usually 0.01..0.02 is good value.

	max_P is chosen as a number, so that max_P/(th_max-th_min)
	is a negative power of two in order arithmetics to contain
	only shifts.


	Parameters, settable by user:
	-----------------------------

	qth_min		- bytes (should be < qth_max/2)
	qth_max		- bytes (should be at least 2*qth_min and less limit)
	Wlog	       	- bits (<32) log(1/W).
	Plog	       	- bits (<32)

	Plog is related to max_P by formula:

	max_P = (qth_max-qth_min)/2^Plog;

	F.e. if qth_max=128K and qth_min=32K, then Plog=22
	corresponds to max_P=0.02

	Scell_log
	Stab

	Lookup table for log((1-W)^(t/t_ave).


	NOTES:

	Upper bound on W.
	-----------------

	If you want to allow bursts of L packets of size S,
	you should choose W:

	L + 1 - th_min/S < (1-(1-W)^L)/W

	th_min/S = 32         th_min/S = 4

	log(W)	L
	-1	33
	-2	35
	-3	39
	-4	46
	-5	57
	-6	75
	-7	101
	-8	135
	-9	190
	etc.
 */

Eric Dumazet's avatar
Eric Dumazet committed
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
/*
 * Adaptative RED : An Algorithm for Increasing the Robustness of RED's AQM
 * (Sally FLoyd, Ramakrishna Gummadi, and Scott Shenker) August 2001
 *
 * Every 500 ms:
 *  if (avg > target and max_p <= 0.5)
 *   increase max_p : max_p += alpha;
 *  else if (avg < target and max_p >= 0.01)
 *   decrease max_p : max_p *= beta;
 *
 * target :[qth_min + 0.4*(qth_min - qth_max),
 *          qth_min + 0.6*(qth_min - qth_max)].
 * alpha : min(0.01, max_p / 4)
 * beta : 0.9
 * max_P is a Q0.32 fixed point number (with 32 bits mantissa)
 * max_P between 0.01 and 0.5 (1% - 50%) [ Its no longer a negative power of two ]
 */
#define RED_ONE_PERCENT ((u32)DIV_ROUND_CLOSEST(1ULL<<32, 100))

#define MAX_P_MIN (1 * RED_ONE_PERCENT)
#define MAX_P_MAX (50 * RED_ONE_PERCENT)
#define MAX_P_ALPHA(val) min(MAX_P_MIN, val / 4)

Thomas Graf's avatar
Thomas Graf committed
116 117 118
#define RED_STAB_SIZE	256
#define RED_STAB_MASK	(RED_STAB_SIZE - 1)

Eric Dumazet's avatar
Eric Dumazet committed
119
struct red_stats {
Thomas Graf's avatar
Thomas Graf committed
120 121 122 123 124 125 126 127
	u32		prob_drop;	/* Early probability drops */
	u32		prob_mark;	/* Early probability marks */
	u32		forced_drop;	/* Forced drops, qavg > max_thresh */
	u32		forced_mark;	/* Forced marks, qavg > max_thresh */
	u32		pdrop;          /* Drops due to queue limits */
	u32		other;          /* Drops due to drop() calls */
};

Eric Dumazet's avatar
Eric Dumazet committed
128
struct red_parms {
Thomas Graf's avatar
Thomas Graf committed
129
	/* Parameters */
Eric Dumazet's avatar
Eric Dumazet committed
130 131
	u32		qth_min;	/* Min avg length threshold: Wlog scaled */
	u32		qth_max;	/* Max avg length threshold: Wlog scaled */
Thomas Graf's avatar
Thomas Graf committed
132
	u32		Scell_max;
Eric Dumazet's avatar
Eric Dumazet committed
133
	u32		max_P;		/* probability, [0 .. 1.0] 32 scaled */
134 135
	/* reciprocal_value(max_P / qth_delta) */
	struct reciprocal_value	max_P_reciprocal;
Eric Dumazet's avatar
Eric Dumazet committed
136 137 138
	u32		qth_delta;	/* max_th - min_th */
	u32		target_min;	/* min_th + 0.4*(max_th - min_th) */
	u32		target_max;	/* min_th + 0.6*(max_th - min_th) */
Thomas Graf's avatar
Thomas Graf committed
139 140 141 142
	u8		Scell_log;
	u8		Wlog;		/* log(W)		*/
	u8		Plog;		/* random number bits	*/
	u8		Stab[RED_STAB_SIZE];
143
};
Thomas Graf's avatar
Thomas Graf committed
144

145
struct red_vars {
Thomas Graf's avatar
Thomas Graf committed
146 147 148 149 150
	/* Variables */
	int		qcount;		/* Number of packets since last random
					   number generation */
	u32		qR;		/* Cached random number */

Eric Dumazet's avatar
Eric Dumazet committed
151
	unsigned long	qavg;		/* Average queue length: Wlog scaled */
152
	ktime_t		qidlestart;	/* Start of current idle period */
Thomas Graf's avatar
Thomas Graf committed
153 154
};

Eric Dumazet's avatar
Eric Dumazet committed
155
static inline u32 red_maxp(u8 Plog)
Thomas Graf's avatar
Thomas Graf committed
156
{
Eric Dumazet's avatar
Eric Dumazet committed
157
	return Plog < 32 ? (~0U >> Plog) : ~0U;
Thomas Graf's avatar
Thomas Graf committed
158 159
}

160 161 162 163 164 165 166 167 168 169
static inline void red_set_vars(struct red_vars *v)
{
	/* Reset average queue length, the value is strictly bound
	 * to the parameters below, reseting hurts a bit but leaving
	 * it might result in an unreasonable qavg for a while. --TGR
	 */
	v->qavg		= 0;

	v->qcount	= -1;
}
Eric Dumazet's avatar
Eric Dumazet committed
170

171 172 173 174 175 176 177 178 179 180 181
static inline bool red_check_params(u32 qth_min, u32 qth_max, u8 Wlog)
{
	if (fls(qth_min) + Wlog > 32)
		return false;
	if (fls(qth_max) + Wlog > 32)
		return false;
	if (qth_max < qth_min)
		return false;
	return true;
}

Thomas Graf's avatar
Thomas Graf committed
182 183
static inline void red_set_parms(struct red_parms *p,
				 u32 qth_min, u32 qth_max, u8 Wlog, u8 Plog,
184
				 u8 Scell_log, u8 *stab, u32 max_P)
Thomas Graf's avatar
Thomas Graf committed
185
{
Eric Dumazet's avatar
Eric Dumazet committed
186
	int delta = qth_max - qth_min;
187
	u32 max_p_delta;
Eric Dumazet's avatar
Eric Dumazet committed
188

Thomas Graf's avatar
Thomas Graf committed
189 190 191 192
	p->qth_min	= qth_min << Wlog;
	p->qth_max	= qth_max << Wlog;
	p->Wlog		= Wlog;
	p->Plog		= Plog;
193
	if (delta <= 0)
Eric Dumazet's avatar
Eric Dumazet committed
194 195
		delta = 1;
	p->qth_delta	= delta;
196 197 198 199 200 201 202 203
	if (!max_P) {
		max_P = red_maxp(Plog);
		max_P *= delta; /* max_P = (qth_max - qth_min)/2^Plog */
	}
	p->max_P = max_P;
	max_p_delta = max_P / delta;
	max_p_delta = max(max_p_delta, 1U);
	p->max_P_reciprocal  = reciprocal_value(max_p_delta);
Eric Dumazet's avatar
Eric Dumazet committed
204 205 206 207 208 209 210 211 212

	/* RED Adaptative target :
	 * [min_th + 0.4*(min_th - max_th),
	 *  min_th + 0.6*(min_th - max_th)].
	 */
	delta /= 5;
	p->target_min = qth_min + 2*delta;
	p->target_max = qth_min + 3*delta;

Thomas Graf's avatar
Thomas Graf committed
213 214 215
	p->Scell_log	= Scell_log;
	p->Scell_max	= (255 << Scell_log);

216 217
	if (stab)
		memcpy(p->Stab, stab, sizeof(p->Stab));
Thomas Graf's avatar
Thomas Graf committed
218 219
}

220
static inline int red_is_idling(const struct red_vars *v)
Thomas Graf's avatar
Thomas Graf committed
221
{
222
	return v->qidlestart != 0;
Thomas Graf's avatar
Thomas Graf committed
223 224
}

225
static inline void red_start_of_idle_period(struct red_vars *v)
Thomas Graf's avatar
Thomas Graf committed
226
{
227
	v->qidlestart = ktime_get();
Thomas Graf's avatar
Thomas Graf committed
228 229
}

230
static inline void red_end_of_idle_period(struct red_vars *v)
Thomas Graf's avatar
Thomas Graf committed
231
{
232
	v->qidlestart = 0;
Thomas Graf's avatar
Thomas Graf committed
233 234
}

235
static inline void red_restart(struct red_vars *v)
Thomas Graf's avatar
Thomas Graf committed
236
{
237 238 239
	red_end_of_idle_period(v);
	v->qavg = 0;
	v->qcount = -1;
Thomas Graf's avatar
Thomas Graf committed
240 241
}

242 243
static inline unsigned long red_calc_qavg_from_idle_time(const struct red_parms *p,
							 const struct red_vars *v)
Thomas Graf's avatar
Thomas Graf committed
244
{
245
	s64 delta = ktime_us_delta(ktime_get(), v->qidlestart);
246
	long us_idle = min_t(s64, delta, p->Scell_max);
Thomas Graf's avatar
Thomas Graf committed
247 248 249 250 251 252 253 254 255 256 257 258 259 260
	int  shift;

	/*
	 * The problem: ideally, average length queue recalcultion should
	 * be done over constant clock intervals. This is too expensive, so
	 * that the calculation is driven by outgoing packets.
	 * When the queue is idle we have to model this clock by hand.
	 *
	 * SF+VJ proposed to "generate":
	 *
	 *	m = idletime / (average_pkt_size / bandwidth)
	 *
	 * dummy packets as a burst after idle time, i.e.
	 *
261
	 * 	v->qavg *= (1-W)^m
Thomas Graf's avatar
Thomas Graf committed
262 263 264 265 266 267 268 269 270 271
	 *
	 * This is an apparently overcomplicated solution (f.e. we have to
	 * precompute a table to make this calculation in reasonable time)
	 * I believe that a simpler model may be used here,
	 * but it is field for experiments.
	 */

	shift = p->Stab[(us_idle >> p->Scell_log) & RED_STAB_MASK];

	if (shift)
272
		return v->qavg >> shift;
Thomas Graf's avatar
Thomas Graf committed
273 274 275 276 277 278 279 280
	else {
		/* Approximate initial part of exponent with linear function:
		 *
		 * 	(1-W)^m ~= 1-mW + ...
		 *
		 * Seems, it is the best solution to
		 * problem of too coarse exponent tabulation.
		 */
281
		us_idle = (v->qavg * (u64)us_idle) >> p->Scell_log;
Thomas Graf's avatar
Thomas Graf committed
282

283 284
		if (us_idle < (v->qavg >> 1))
			return v->qavg - us_idle;
Thomas Graf's avatar
Thomas Graf committed
285
		else
286
			return v->qavg >> 1;
Thomas Graf's avatar
Thomas Graf committed
287 288 289
	}
}

Eric Dumazet's avatar
Eric Dumazet committed
290
static inline unsigned long red_calc_qavg_no_idle_time(const struct red_parms *p,
291
						       const struct red_vars *v,
Thomas Graf's avatar
Thomas Graf committed
292 293 294
						       unsigned int backlog)
{
	/*
295
	 * NOTE: v->qavg is fixed point number with point at Wlog.
Thomas Graf's avatar
Thomas Graf committed
296 297 298 299 300 301 302
	 * The formula below is equvalent to floating point
	 * version:
	 *
	 * 	qavg = qavg*(1-W) + backlog*W;
	 *
	 * --ANK (980924)
	 */
303
	return v->qavg + (backlog - (v->qavg >> p->Wlog));
Thomas Graf's avatar
Thomas Graf committed
304 305
}

Eric Dumazet's avatar
Eric Dumazet committed
306
static inline unsigned long red_calc_qavg(const struct red_parms *p,
307
					  const struct red_vars *v,
Thomas Graf's avatar
Thomas Graf committed
308 309
					  unsigned int backlog)
{
310 311
	if (!red_is_idling(v))
		return red_calc_qavg_no_idle_time(p, v, backlog);
Thomas Graf's avatar
Thomas Graf committed
312
	else
313
		return red_calc_qavg_from_idle_time(p, v);
Thomas Graf's avatar
Thomas Graf committed
314 315
}

Eric Dumazet's avatar
Eric Dumazet committed
316 317

static inline u32 red_random(const struct red_parms *p)
Thomas Graf's avatar
Thomas Graf committed
318
{
319
	return reciprocal_divide(prandom_u32(), p->max_P_reciprocal);
Thomas Graf's avatar
Thomas Graf committed
320 321
}

322 323 324
static inline int red_mark_probability(const struct red_parms *p,
				       const struct red_vars *v,
				       unsigned long qavg)
Thomas Graf's avatar
Thomas Graf committed
325 326 327
{
	/* The formula used below causes questions.

Eric Dumazet's avatar
Eric Dumazet committed
328 329
	   OK. qR is random number in the interval
		(0..1/max_P)*(qth_max-qth_min)
Thomas Graf's avatar
Thomas Graf committed
330 331 332 333 334
	   i.e. 0..(2^Plog). If we used floating point
	   arithmetics, it would be: (2^Plog)*rnd_num,
	   where rnd_num is less 1.

	   Taking into account, that qavg have fixed
Eric Dumazet's avatar
Eric Dumazet committed
335
	   point at Wlog, two lines
Thomas Graf's avatar
Thomas Graf committed
336 337 338 339 340 341
	   below have the following floating point equivalent:

	   max_P*(qavg - qth_min)/(qth_max-qth_min) < rnd/qcount

	   Any questions? --ANK (980924)
	 */
342
	return !(((qavg - p->qth_min) >> p->Wlog) * v->qcount < v->qR);
Thomas Graf's avatar
Thomas Graf committed
343 344 345 346 347 348 349 350
}

enum {
	RED_BELOW_MIN_THRESH,
	RED_BETWEEN_TRESH,
	RED_ABOVE_MAX_TRESH,
};

351
static inline int red_cmp_thresh(const struct red_parms *p, unsigned long qavg)
Thomas Graf's avatar
Thomas Graf committed
352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
{
	if (qavg < p->qth_min)
		return RED_BELOW_MIN_THRESH;
	else if (qavg >= p->qth_max)
		return RED_ABOVE_MAX_TRESH;
	else
		return RED_BETWEEN_TRESH;
}

enum {
	RED_DONT_MARK,
	RED_PROB_MARK,
	RED_HARD_MARK,
};

367 368 369
static inline int red_action(const struct red_parms *p,
			     struct red_vars *v,
			     unsigned long qavg)
Thomas Graf's avatar
Thomas Graf committed
370 371 372
{
	switch (red_cmp_thresh(p, qavg)) {
		case RED_BELOW_MIN_THRESH:
373
			v->qcount = -1;
Thomas Graf's avatar
Thomas Graf committed
374 375 376
			return RED_DONT_MARK;

		case RED_BETWEEN_TRESH:
377 378 379 380
			if (++v->qcount) {
				if (red_mark_probability(p, v, qavg)) {
					v->qcount = 0;
					v->qR = red_random(p);
Thomas Graf's avatar
Thomas Graf committed
381 382 383
					return RED_PROB_MARK;
				}
			} else
384
				v->qR = red_random(p);
Thomas Graf's avatar
Thomas Graf committed
385 386 387 388

			return RED_DONT_MARK;

		case RED_ABOVE_MAX_TRESH:
389
			v->qcount = -1;
Thomas Graf's avatar
Thomas Graf committed
390 391 392 393 394 395 396
			return RED_HARD_MARK;
	}

	BUG();
	return RED_DONT_MARK;
}

397
static inline void red_adaptative_algo(struct red_parms *p, struct red_vars *v)
Eric Dumazet's avatar
Eric Dumazet committed
398 399 400 401
{
	unsigned long qavg;
	u32 max_p_delta;

402 403 404
	qavg = v->qavg;
	if (red_is_idling(v))
		qavg = red_calc_qavg_from_idle_time(p, v);
Eric Dumazet's avatar
Eric Dumazet committed
405

406
	/* v->qavg is fixed point number with point at Wlog */
Eric Dumazet's avatar
Eric Dumazet committed
407 408 409 410 411 412 413 414
	qavg >>= p->Wlog;

	if (qavg > p->target_max && p->max_P <= MAX_P_MAX)
		p->max_P += MAX_P_ALPHA(p->max_P); /* maxp = maxp + alpha */
	else if (qavg < p->target_min && p->max_P >= MAX_P_MIN)
		p->max_P = (p->max_P/10)*9; /* maxp = maxp * Beta */

	max_p_delta = DIV_ROUND_CLOSEST(p->max_P, p->qth_delta);
415
	max_p_delta = max(max_p_delta, 1U);
Eric Dumazet's avatar
Eric Dumazet committed
416 417
	p->max_P_reciprocal = reciprocal_value(max_p_delta);
}
Thomas Graf's avatar
Thomas Graf committed
418
#endif