1 /*-
2  * Copyright (C) 1997-2003
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 /*-
28  * Copyright (c) 1990-1994 Regents of the University of California.
56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
100  * ALTQ/RED (Random Early Detection) implementation using 32-bit
101  * fixed-point calculation.
105  * http://www-nrg.ee.lbl.gov/floyd/
108  * to prevent fixed-point overflow/underflow.
109  * if you change the parameters, watch out for overflow/underflow!
114  *	minthresh=5 maxthresh=15 queue-size=60
116  *	dropmech=drop-tail
117  *	bytes=false (can't be handled by 32-bit fixed-point)
127  * for a slow link like dial-up, 500 packets takes more than 1 minute!
146 /* fixed-point uses 12-bit decimal places */
147 #define	FP_SHIFT	12	/* fixed-point shift */
149 /* red parameters for drop probability */
150 #define	INV_P_MAX	10	/* inverse of max drop probability */
158  * our default policy for forced-drop is drop-tail.
159  * (in altq-1.1.2 or earlier, the default was random-drop.
161  * to switch to the random-drop policy, define "RED_RANDOM_DROP".
185 		rp->red_weight = W_WEIGHT;  in red_alloc()
187 		rp->red_weight = weight;  in red_alloc()
190 	rp->red_wtab = wtab_alloc(rp->red_weight);  in red_alloc()
191 	if (rp->red_wtab == NULL) {  in red_alloc()
196 	rp->red_avg = 0;  in red_alloc()
197 	rp->red_idle = 1;  in red_alloc()
200 		rp->red_inv_pmax = default_inv_pmax;  in red_alloc()
202 		rp->red_inv_pmax = inv_pmax;  in red_alloc()
204 		rp->red_thmin = default_th_min;  in red_alloc()
206 		rp->red_thmin = th_min;  in red_alloc()
208 		rp->red_thmax = default_th_max;  in red_alloc()
210 		rp->red_thmax = th_max;  in red_alloc()
212 	rp->red_flags = flags;  in red_alloc()
216 		rp->red_pkttime = 800;  in red_alloc()
218 		rp->red_pkttime = pkttime;  in red_alloc()
222 		npkts_per_sec = 1000000 / rp->red_pkttime;  in red_alloc()
225 			rp->red_weight = W_WEIGHT_2;  in red_alloc()
228 			rp->red_weight = W_WEIGHT_1;  in red_alloc()
233 	w = rp->red_weight;  in red_alloc()
236 	rp->red_wshift = i;  in red_alloc()
237 	w = 1 << rp->red_wshift;  in red_alloc()
238 	if (w != rp->red_weight) {  in red_alloc()
240 		       rp->red_weight, w);  in red_alloc()
241 		rp->red_weight = w;  in red_alloc()
248 	rp->red_thmin_s = rp->red_thmin << (rp->red_wshift + FP_SHIFT);  in red_alloc()
249 	rp->red_thmax_s = rp->red_thmax << (rp->red_wshift + FP_SHIFT);  in red_alloc()
253 	 *  probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point  in red_alloc()
255 	rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin)  in red_alloc()
256 			 * rp->red_inv_pmax) << FP_SHIFT;  in red_alloc()
258 	microtime(&rp->red_last);  in red_alloc()
265 	wtab_destroy(rp->red_wtab);  in red_destroy()
272 	sp->q_avg		= rp->red_avg >> rp->red_wshift;  in red_getstats()
273 	sp->xmit_cnt		= rp->red_stats.xmit_cnt;  in red_getstats()
274 	sp->drop_cnt		= rp->red_stats.drop_cnt;  in red_getstats()
275 	sp->drop_forced		= rp->red_stats.drop_forced;  in red_getstats()
276 	sp->drop_unforced	= rp->red_stats.drop_unforced;  in red_getstats()
277 	sp->marked_packets	= rp->red_stats.marked_packets;  in red_getstats()
287 	avg = rp->red_avg;  in red_addq()
293 	if (rp->red_idle) {  in red_addq()
297 		rp->red_idle = 0;  in red_addq()
299 		t = (now.tv_sec - rp->red_last.tv_sec);  in red_addq()
307 			t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec);  in red_addq()
308 			n = t / rp->red_pkttime - 1;  in red_addq()
310 			/* the following line does (avg = (1 - Wq)^n * avg) */  in red_addq()
313 				    pow_w(rp->red_wtab, n);  in red_addq()
317 	/* run estimator. (note: avg is scaled by WEIGHT in fixed-point) */  in red_addq()
318 	avg += (qlen(q) << FP_SHIFT) - (avg >> rp->red_wshift);  in red_addq()
319 	rp->red_avg = avg;		/* save the new value */  in red_addq()
325 	rp->red_count++;  in red_addq()
327 	/* see if we drop early */  in red_addq()
329 	if (avg >= rp->red_thmin_s && qlen(q) > 1) {  in red_addq()
330 		if (avg >= rp->red_thmax_s) {  in red_addq()
331 			/* avg >= th_max: forced drop */  in red_addq()
333 		} else if (rp->red_old == 0) {  in red_addq()
335 			rp->red_count = 1;  in red_addq()
336 			rp->red_old = 1;  in red_addq()
337 		} else if (drop_early((avg - rp->red_thmin_s) >> rp->red_wshift,  in red_addq()
338 				      rp->red_probd, rp->red_count)) {  in red_addq()
339 			/* mark or drop by red */  in red_addq()
340 			if ((rp->red_flags & REDF_ECN) &&  in red_addq()
341 			    mark_ecn(m, pktattr, rp->red_flags)) {  in red_addq()
342 				/* successfully marked.  do not drop. */  in red_addq()
343 				rp->red_count = 0;  in red_addq()
345 				rp->red_stats.marked_packets++;  in red_addq()
348 				/* unforced drop by red */  in red_addq()
354 		rp->red_old = 0;  in red_addq()
358 	 * if the queue length hits the hard limit, it's a forced drop.  in red_addq()
364 	/* if successful or forced drop, enqueue this packet. */  in red_addq()
374 			/* drop the incoming packet */  in red_addq()
376 			rp->red_stats.drop_unforced++;  in red_addq()
379 			/* forced drop, select a victim packet in the queue. */  in red_addq()
384 			rp->red_stats.drop_forced++;  in red_addq()
388 		PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m));  in red_addq()
390 		rp->red_count = 0;  in red_addq()
392 		return (-1);  in red_addq()
396 	PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m));  in red_addq()
402  * early-drop probability is calculated as follows:
403  *   prob = p_max * (avg - th_min) / (th_max - th_min)
404  *   prob_a = prob / (2 - count*prob)
405  *	    = (avg-th_min) / (2*(th_max-th_min)*inv_p_max - count*(avg-th_min))
413 	int	d;		/* denominator of drop-probability */  in drop_early()
415 	d = fp_probd - count * fp_len;  in drop_early()
417 		/* count exceeds the hard limit: drop or mark */  in drop_early()
421 	 * now the range of d is [1..600] in fixed-point. (when  in drop_early()
422 	 * th_max-th_min=10 and p_max=1/30)  in drop_early()
423 	 * drop probability = (avg - TH_MIN) / d  in drop_early()
427 		/* drop or mark */  in drop_early()
430 	/* no drop/mark */  in drop_early()
447 		hdr = at->hdr;  in mark_ecn()
452 	for (m0 = m; m0 != NULL; m0 = m0->m_next)  in mark_ecn()
453 		if (((caddr_t)hdr >= m0->m_data) &&  in mark_ecn()
454 		    ((caddr_t)hdr < m0->m_data + m0->m_len))  in mark_ecn()
461 	switch (((struct ip *)hdr)->ip_v) {  in mark_ecn()
468 			if (ip->ip_v != 4)  in mark_ecn()
471 			if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_NOTECT)  in mark_ecn()
472 				return (0);	/* not-ECT */  in mark_ecn()
473 			if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_CE)  in mark_ecn()
477 			 * ecn-capable but not marked,  in mark_ecn()
480 			otos = ip->ip_tos;  in mark_ecn()
481 			ip->ip_tos |= IPTOS_ECN_CE;  in mark_ecn()
486 			sum = ~ntohs(ip->ip_sum) & 0xffff;  in mark_ecn()
487 			sum += (~otos & 0xffff) + ip->ip_tos;  in mark_ecn()
490 			ip->ip_sum = htons(~sum & 0xffff);  in mark_ecn()
500 			flowlabel = ntohl(ip6->ip6_flow);  in mark_ecn()
505 				return (0);	/* not-ECT */  in mark_ecn()
510 			 * ecn-capable but not marked,  mark CE  in mark_ecn()
513 			ip6->ip6_flow = htonl(flowlabel);  in mark_ecn()
530 		if (rp->red_idle == 0) {  in red_getq()
531 			rp->red_idle = 1;  in red_getq()
532 			microtime(&rp->red_last);  in red_getq()
537 	rp->red_idle = 0;  in red_getq()
543  * pow_w(wtab, n) returns (1 - Wq)^n in fixed-point
546  * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point.
556 	for (w = wtab_list; w != NULL; w = w->w_next)  in wtab_alloc()
557 		if (w->w_weight == weight) {  in wtab_alloc()
558 			w->w_refcount++;  in wtab_alloc()
565 	w->w_weight = weight;  in wtab_alloc()
566 	w->w_refcount = 1;  in wtab_alloc()
567 	w->w_next = wtab_list;  in wtab_alloc()
571 	w->w_tab[0] = ((weight - 1) << FP_SHIFT) / weight;  in wtab_alloc()
573 		w->w_tab[i] = (w->w_tab[i-1] * w->w_tab[i-1]) >> FP_SHIFT;  in wtab_alloc()
574 		if (w->w_tab[i] == 0 && w->w_param_max == 0)  in wtab_alloc()
575 			w->w_param_max = 1 << i;  in wtab_alloc()
586 	if (--w->w_refcount > 0)  in wtab_destroy()
590 		wtab_list = w->w_next;  in wtab_destroy()
591 	else for (prev = wtab_list; prev->w_next != NULL; prev = prev->w_next)  in wtab_destroy()
592 		if (prev->w_next == w) {  in wtab_destroy()
593 			prev->w_next = w->w_next;  in wtab_destroy()
607 	if (n >= w->w_param_max)  in pow_w()
618 			val = (val * w->w_tab[i]) >> FP_SHIFT;  in pow_w()