xref: /freebsd/sys/net/altq/altq_subr.c (revision a5921bc3653e2e286715e6fe8d473ec0d02da38c)
1 /*-
2  * Copyright (C) 1997-2003
3  *	Sony Computer Science Laboratories Inc.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  * $KAME: altq_subr.c,v 1.21 2003/11/06 06:32:53 kjc Exp $
27  * $FreeBSD$
28  */
29 
30 #include "opt_altq.h"
31 #include "opt_inet.h"
32 #include "opt_inet6.h"
33 
34 #include <sys/param.h>
35 #include <sys/malloc.h>
36 #include <sys/mbuf.h>
37 #include <sys/systm.h>
38 #include <sys/proc.h>
39 #include <sys/socket.h>
40 #include <sys/socketvar.h>
41 #include <sys/kernel.h>
42 #include <sys/errno.h>
43 #include <sys/syslog.h>
44 #include <sys/sysctl.h>
45 #include <sys/queue.h>
46 
47 #include <net/if.h>
48 #include <net/if_var.h>
49 #include <net/if_dl.h>
50 #include <net/if_types.h>
51 #include <net/vnet.h>
52 
53 #include <netinet/in.h>
54 #include <netinet/in_systm.h>
55 #include <netinet/ip.h>
56 #ifdef INET6
57 #include <netinet/ip6.h>
58 #endif
59 #include <netinet/tcp.h>
60 #include <netinet/udp.h>
61 
62 #include <netpfil/pf/pf.h>
63 #include <netpfil/pf/pf_altq.h>
64 #include <net/altq/altq.h>
65 #ifdef ALTQ3_COMPAT
66 #include <net/altq/altq_conf.h>
67 #endif
68 
69 /* machine dependent clock related includes */
70 #include <sys/bus.h>
71 #include <sys/cpu.h>
72 #include <sys/eventhandler.h>
73 #include <machine/clock.h>
74 #if defined(__amd64__) || defined(__i386__)
75 #include <machine/cpufunc.h>		/* for pentium tsc */
76 #include <machine/specialreg.h>		/* for CPUID_TSC */
77 #include <machine/md_var.h>		/* for cpu_feature */
78 #endif /* __amd64 || __i386__ */
79 
80 /*
81  * internal function prototypes
82  */
83 static void	tbr_timeout(void *);
84 int (*altq_input)(struct mbuf *, int) = NULL;
85 static struct mbuf *tbr_dequeue(struct ifaltq *, int);
86 static int tbr_timer = 0;	/* token bucket regulator timer */
87 #if !defined(__FreeBSD__) || (__FreeBSD_version < 600000)
88 static struct callout tbr_callout = CALLOUT_INITIALIZER;
89 #else
90 static struct callout tbr_callout;
91 #endif
92 
93 #ifdef ALTQ3_CLFIER_COMPAT
94 static int 	extract_ports4(struct mbuf *, struct ip *, struct flowinfo_in *);
95 #ifdef INET6
96 static int 	extract_ports6(struct mbuf *, struct ip6_hdr *,
97 			       struct flowinfo_in6 *);
98 #endif
99 static int	apply_filter4(u_int32_t, struct flow_filter *,
100 			      struct flowinfo_in *);
101 static int	apply_ppfilter4(u_int32_t, struct flow_filter *,
102 				struct flowinfo_in *);
103 #ifdef INET6
104 static int	apply_filter6(u_int32_t, struct flow_filter6 *,
105 			      struct flowinfo_in6 *);
106 #endif
107 static int	apply_tosfilter4(u_int32_t, struct flow_filter *,
108 				 struct flowinfo_in *);
109 static u_long	get_filt_handle(struct acc_classifier *, int);
110 static struct acc_filter *filth_to_filtp(struct acc_classifier *, u_long);
111 static u_int32_t filt2fibmask(struct flow_filter *);
112 
113 static void 	ip4f_cache(struct ip *, struct flowinfo_in *);
114 static int 	ip4f_lookup(struct ip *, struct flowinfo_in *);
115 static int 	ip4f_init(void);
116 static struct ip4_frag	*ip4f_alloc(void);
117 static void 	ip4f_free(struct ip4_frag *);
118 #endif /* ALTQ3_CLFIER_COMPAT */
119 
120 /*
121  * alternate queueing support routines
122  */
123 
124 /* look up the queue state by the interface name and the queueing type. */
125 void *
126 altq_lookup(name, type)
127 	char *name;
128 	int type;
129 {
130 	struct ifnet *ifp;
131 
132 	if ((ifp = ifunit(name)) != NULL) {
133 		/* read if_snd unlocked */
134 		if (type != ALTQT_NONE && ifp->if_snd.altq_type == type)
135 			return (ifp->if_snd.altq_disc);
136 	}
137 
138 	return NULL;
139 }
140 
141 int
142 altq_attach(ifq, type, discipline, enqueue, dequeue, request, clfier, classify)
143 	struct ifaltq *ifq;
144 	int type;
145 	void *discipline;
146 	int (*enqueue)(struct ifaltq *, struct mbuf *, struct altq_pktattr *);
147 	struct mbuf *(*dequeue)(struct ifaltq *, int);
148 	int (*request)(struct ifaltq *, int, void *);
149 	void *clfier;
150 	void *(*classify)(void *, struct mbuf *, int);
151 {
152 	IFQ_LOCK(ifq);
153 	if (!ALTQ_IS_READY(ifq)) {
154 		IFQ_UNLOCK(ifq);
155 		return ENXIO;
156 	}
157 
158 #ifdef ALTQ3_COMPAT
159 	/*
160 	 * pfaltq can override the existing discipline, but altq3 cannot.
161 	 * check these if clfier is not NULL (which implies altq3).
162 	 */
163 	if (clfier != NULL) {
164 		if (ALTQ_IS_ENABLED(ifq)) {
165 			IFQ_UNLOCK(ifq);
166 			return EBUSY;
167 		}
168 		if (ALTQ_IS_ATTACHED(ifq)) {
169 			IFQ_UNLOCK(ifq);
170 			return EEXIST;
171 		}
172 	}
173 #endif
174 	ifq->altq_type     = type;
175 	ifq->altq_disc     = discipline;
176 	ifq->altq_enqueue  = enqueue;
177 	ifq->altq_dequeue  = dequeue;
178 	ifq->altq_request  = request;
179 	ifq->altq_clfier   = clfier;
180 	ifq->altq_classify = classify;
181 	ifq->altq_flags &= (ALTQF_CANTCHANGE|ALTQF_ENABLED);
182 #ifdef ALTQ3_COMPAT
183 #ifdef ALTQ_KLD
184 	altq_module_incref(type);
185 #endif
186 #endif
187 	IFQ_UNLOCK(ifq);
188 	return 0;
189 }
190 
191 int
192 altq_detach(ifq)
193 	struct ifaltq *ifq;
194 {
195 	IFQ_LOCK(ifq);
196 
197 	if (!ALTQ_IS_READY(ifq)) {
198 		IFQ_UNLOCK(ifq);
199 		return ENXIO;
200 	}
201 	if (ALTQ_IS_ENABLED(ifq)) {
202 		IFQ_UNLOCK(ifq);
203 		return EBUSY;
204 	}
205 	if (!ALTQ_IS_ATTACHED(ifq)) {
206 		IFQ_UNLOCK(ifq);
207 		return (0);
208 	}
209 #ifdef ALTQ3_COMPAT
210 #ifdef ALTQ_KLD
211 	altq_module_declref(ifq->altq_type);
212 #endif
213 #endif
214 
215 	ifq->altq_type     = ALTQT_NONE;
216 	ifq->altq_disc     = NULL;
217 	ifq->altq_enqueue  = NULL;
218 	ifq->altq_dequeue  = NULL;
219 	ifq->altq_request  = NULL;
220 	ifq->altq_clfier   = NULL;
221 	ifq->altq_classify = NULL;
222 	ifq->altq_flags &= ALTQF_CANTCHANGE;
223 
224 	IFQ_UNLOCK(ifq);
225 	return 0;
226 }
227 
228 int
229 altq_enable(ifq)
230 	struct ifaltq *ifq;
231 {
232 	int s;
233 
234 	IFQ_LOCK(ifq);
235 
236 	if (!ALTQ_IS_READY(ifq)) {
237 		IFQ_UNLOCK(ifq);
238 		return ENXIO;
239 	}
240 	if (ALTQ_IS_ENABLED(ifq)) {
241 		IFQ_UNLOCK(ifq);
242 		return 0;
243 	}
244 
245 	s = splnet();
246 	IFQ_PURGE_NOLOCK(ifq);
247 	ASSERT(ifq->ifq_len == 0);
248 	ifq->ifq_drv_maxlen = 0;		/* disable bulk dequeue */
249 	ifq->altq_flags |= ALTQF_ENABLED;
250 	if (ifq->altq_clfier != NULL)
251 		ifq->altq_flags |= ALTQF_CLASSIFY;
252 	splx(s);
253 
254 	IFQ_UNLOCK(ifq);
255 	return 0;
256 }
257 
258 int
259 altq_disable(ifq)
260 	struct ifaltq *ifq;
261 {
262 	int s;
263 
264 	IFQ_LOCK(ifq);
265 	if (!ALTQ_IS_ENABLED(ifq)) {
266 		IFQ_UNLOCK(ifq);
267 		return 0;
268 	}
269 
270 	s = splnet();
271 	IFQ_PURGE_NOLOCK(ifq);
272 	ASSERT(ifq->ifq_len == 0);
273 	ifq->altq_flags &= ~(ALTQF_ENABLED|ALTQF_CLASSIFY);
274 	splx(s);
275 
276 	IFQ_UNLOCK(ifq);
277 	return 0;
278 }
279 
280 #ifdef ALTQ_DEBUG
281 void
282 altq_assert(file, line, failedexpr)
283 	const char *file, *failedexpr;
284 	int line;
285 {
286 	(void)printf("altq assertion \"%s\" failed: file \"%s\", line %d\n",
287 		     failedexpr, file, line);
288 	panic("altq assertion");
289 	/* NOTREACHED */
290 }
291 #endif
292 
293 /*
294  * internal representation of token bucket parameters
295  *	rate:	byte_per_unittime << 32
296  *		(((bits_per_sec) / 8) << 32) / machclk_freq
297  *	depth:	byte << 32
298  *
299  */
300 #define	TBR_SHIFT	32
301 #define	TBR_SCALE(x)	((int64_t)(x) << TBR_SHIFT)
302 #define	TBR_UNSCALE(x)	((x) >> TBR_SHIFT)
303 
304 static struct mbuf *
305 tbr_dequeue(ifq, op)
306 	struct ifaltq *ifq;
307 	int op;
308 {
309 	struct tb_regulator *tbr;
310 	struct mbuf *m;
311 	int64_t interval;
312 	u_int64_t now;
313 
314 	IFQ_LOCK_ASSERT(ifq);
315 	tbr = ifq->altq_tbr;
316 	if (op == ALTDQ_REMOVE && tbr->tbr_lastop == ALTDQ_POLL) {
317 		/* if this is a remove after poll, bypass tbr check */
318 	} else {
319 		/* update token only when it is negative */
320 		if (tbr->tbr_token <= 0) {
321 			now = read_machclk();
322 			interval = now - tbr->tbr_last;
323 			if (interval >= tbr->tbr_filluptime)
324 				tbr->tbr_token = tbr->tbr_depth;
325 			else {
326 				tbr->tbr_token += interval * tbr->tbr_rate;
327 				if (tbr->tbr_token > tbr->tbr_depth)
328 					tbr->tbr_token = tbr->tbr_depth;
329 			}
330 			tbr->tbr_last = now;
331 		}
332 		/* if token is still negative, don't allow dequeue */
333 		if (tbr->tbr_token <= 0)
334 			return (NULL);
335 	}
336 
337 	if (ALTQ_IS_ENABLED(ifq))
338 		m = (*ifq->altq_dequeue)(ifq, op);
339 	else {
340 		if (op == ALTDQ_POLL)
341 			_IF_POLL(ifq, m);
342 		else
343 			_IF_DEQUEUE(ifq, m);
344 	}
345 
346 	if (m != NULL && op == ALTDQ_REMOVE)
347 		tbr->tbr_token -= TBR_SCALE(m_pktlen(m));
348 	tbr->tbr_lastop = op;
349 	return (m);
350 }
351 
352 /*
353  * set a token bucket regulator.
354  * if the specified rate is zero, the token bucket regulator is deleted.
355  */
356 int
357 tbr_set(ifq, profile)
358 	struct ifaltq *ifq;
359 	struct tb_profile *profile;
360 {
361 	struct tb_regulator *tbr, *otbr;
362 
363 	if (tbr_dequeue_ptr == NULL)
364 		tbr_dequeue_ptr = tbr_dequeue;
365 
366 	if (machclk_freq == 0)
367 		init_machclk();
368 	if (machclk_freq == 0) {
369 		printf("tbr_set: no cpu clock available!\n");
370 		return (ENXIO);
371 	}
372 
373 	IFQ_LOCK(ifq);
374 	if (profile->rate == 0) {
375 		/* delete this tbr */
376 		if ((tbr = ifq->altq_tbr) == NULL) {
377 			IFQ_UNLOCK(ifq);
378 			return (ENOENT);
379 		}
380 		ifq->altq_tbr = NULL;
381 		free(tbr, M_DEVBUF);
382 		IFQ_UNLOCK(ifq);
383 		return (0);
384 	}
385 
386 	tbr = malloc(sizeof(struct tb_regulator), M_DEVBUF, M_NOWAIT | M_ZERO);
387 	if (tbr == NULL) {
388 		IFQ_UNLOCK(ifq);
389 		return (ENOMEM);
390 	}
391 
392 	tbr->tbr_rate = TBR_SCALE(profile->rate / 8) / machclk_freq;
393 	tbr->tbr_depth = TBR_SCALE(profile->depth);
394 	if (tbr->tbr_rate > 0)
395 		tbr->tbr_filluptime = tbr->tbr_depth / tbr->tbr_rate;
396 	else
397 		tbr->tbr_filluptime = 0xffffffffffffffffLL;
398 	tbr->tbr_token = tbr->tbr_depth;
399 	tbr->tbr_last = read_machclk();
400 	tbr->tbr_lastop = ALTDQ_REMOVE;
401 
402 	otbr = ifq->altq_tbr;
403 	ifq->altq_tbr = tbr;	/* set the new tbr */
404 
405 	if (otbr != NULL)
406 		free(otbr, M_DEVBUF);
407 	else {
408 		if (tbr_timer == 0) {
409 			CALLOUT_RESET(&tbr_callout, 1, tbr_timeout, (void *)0);
410 			tbr_timer = 1;
411 		}
412 	}
413 	IFQ_UNLOCK(ifq);
414 	return (0);
415 }
416 
417 /*
418  * tbr_timeout goes through the interface list, and kicks the drivers
419  * if necessary.
420  *
421  * MPSAFE
422  */
423 static void
424 tbr_timeout(arg)
425 	void *arg;
426 {
427 	VNET_ITERATOR_DECL(vnet_iter);
428 	struct ifnet *ifp;
429 	int active, s;
430 
431 	active = 0;
432 	s = splnet();
433 	IFNET_RLOCK_NOSLEEP();
434 	VNET_LIST_RLOCK_NOSLEEP();
435 	VNET_FOREACH(vnet_iter) {
436 		CURVNET_SET(vnet_iter);
437 		for (ifp = TAILQ_FIRST(&V_ifnet); ifp;
438 		    ifp = TAILQ_NEXT(ifp, if_list)) {
439 			/* read from if_snd unlocked */
440 			if (!TBR_IS_ENABLED(&ifp->if_snd))
441 				continue;
442 			active++;
443 			if (!IFQ_IS_EMPTY(&ifp->if_snd) &&
444 			    ifp->if_start != NULL)
445 				(*ifp->if_start)(ifp);
446 		}
447 		CURVNET_RESTORE();
448 	}
449 	VNET_LIST_RUNLOCK_NOSLEEP();
450 	IFNET_RUNLOCK_NOSLEEP();
451 	splx(s);
452 	if (active > 0)
453 		CALLOUT_RESET(&tbr_callout, 1, tbr_timeout, (void *)0);
454 	else
455 		tbr_timer = 0;	/* don't need tbr_timer anymore */
456 }
457 
458 /*
459  * get token bucket regulator profile
460  */
461 int
462 tbr_get(ifq, profile)
463 	struct ifaltq *ifq;
464 	struct tb_profile *profile;
465 {
466 	struct tb_regulator *tbr;
467 
468 	IFQ_LOCK(ifq);
469 	if ((tbr = ifq->altq_tbr) == NULL) {
470 		profile->rate = 0;
471 		profile->depth = 0;
472 	} else {
473 		profile->rate =
474 		    (u_int)TBR_UNSCALE(tbr->tbr_rate * 8 * machclk_freq);
475 		profile->depth = (u_int)TBR_UNSCALE(tbr->tbr_depth);
476 	}
477 	IFQ_UNLOCK(ifq);
478 	return (0);
479 }
480 
481 /*
482  * attach a discipline to the interface.  if one already exists, it is
483  * overridden.
484  * Locking is done in the discipline specific attach functions. Basically
485  * they call back to altq_attach which takes care of the attach and locking.
486  */
487 int
488 altq_pfattach(struct pf_altq *a)
489 {
490 	int error = 0;
491 
492 	switch (a->scheduler) {
493 	case ALTQT_NONE:
494 		break;
495 #ifdef ALTQ_CBQ
496 	case ALTQT_CBQ:
497 		error = cbq_pfattach(a);
498 		break;
499 #endif
500 #ifdef ALTQ_PRIQ
501 	case ALTQT_PRIQ:
502 		error = priq_pfattach(a);
503 		break;
504 #endif
505 #ifdef ALTQ_HFSC
506 	case ALTQT_HFSC:
507 		error = hfsc_pfattach(a);
508 		break;
509 #endif
510 #ifdef ALTQ_FAIRQ
511 	case ALTQT_FAIRQ:
512 		error = fairq_pfattach(a);
513 		break;
514 #endif
515 #ifdef ALTQ_CODEL
516 	case ALTQT_CODEL:
517 		error = codel_pfattach(a);
518 		break;
519 #endif
520 	default:
521 		error = ENXIO;
522 	}
523 
524 	return (error);
525 }
526 
527 /*
528  * detach a discipline from the interface.
529  * it is possible that the discipline was already overridden by another
530  * discipline.
531  */
532 int
533 altq_pfdetach(struct pf_altq *a)
534 {
535 	struct ifnet *ifp;
536 	int s, error = 0;
537 
538 	if ((ifp = ifunit(a->ifname)) == NULL)
539 		return (EINVAL);
540 
541 	/* if this discipline is no longer referenced, just return */
542 	/* read unlocked from if_snd */
543 	if (a->altq_disc == NULL || a->altq_disc != ifp->if_snd.altq_disc)
544 		return (0);
545 
546 	s = splnet();
547 	/* read unlocked from if_snd, _disable and _detach take care */
548 	if (ALTQ_IS_ENABLED(&ifp->if_snd))
549 		error = altq_disable(&ifp->if_snd);
550 	if (error == 0)
551 		error = altq_detach(&ifp->if_snd);
552 	splx(s);
553 
554 	return (error);
555 }
556 
557 /*
558  * add a discipline or a queue
559  * Locking is done in the discipline specific functions with regards to
560  * malloc with WAITOK, also it is not yet clear which lock to use.
561  */
562 int
563 altq_add(struct pf_altq *a)
564 {
565 	int error = 0;
566 
567 	if (a->qname[0] != 0)
568 		return (altq_add_queue(a));
569 
570 	if (machclk_freq == 0)
571 		init_machclk();
572 	if (machclk_freq == 0)
573 		panic("altq_add: no cpu clock");
574 
575 	switch (a->scheduler) {
576 #ifdef ALTQ_CBQ
577 	case ALTQT_CBQ:
578 		error = cbq_add_altq(a);
579 		break;
580 #endif
581 #ifdef ALTQ_PRIQ
582 	case ALTQT_PRIQ:
583 		error = priq_add_altq(a);
584 		break;
585 #endif
586 #ifdef ALTQ_HFSC
587 	case ALTQT_HFSC:
588 		error = hfsc_add_altq(a);
589 		break;
590 #endif
591 #ifdef ALTQ_FAIRQ
592         case ALTQT_FAIRQ:
593                 error = fairq_add_altq(a);
594                 break;
595 #endif
596 #ifdef ALTQ_CODEL
597 	case ALTQT_CODEL:
598 		error = codel_add_altq(a);
599 		break;
600 #endif
601 	default:
602 		error = ENXIO;
603 	}
604 
605 	return (error);
606 }
607 
608 /*
609  * remove a discipline or a queue
610  * It is yet unclear what lock to use to protect this operation, the
611  * discipline specific functions will determine and grab it
612  */
613 int
614 altq_remove(struct pf_altq *a)
615 {
616 	int error = 0;
617 
618 	if (a->qname[0] != 0)
619 		return (altq_remove_queue(a));
620 
621 	switch (a->scheduler) {
622 #ifdef ALTQ_CBQ
623 	case ALTQT_CBQ:
624 		error = cbq_remove_altq(a);
625 		break;
626 #endif
627 #ifdef ALTQ_PRIQ
628 	case ALTQT_PRIQ:
629 		error = priq_remove_altq(a);
630 		break;
631 #endif
632 #ifdef ALTQ_HFSC
633 	case ALTQT_HFSC:
634 		error = hfsc_remove_altq(a);
635 		break;
636 #endif
637 #ifdef ALTQ_FAIRQ
638         case ALTQT_FAIRQ:
639                 error = fairq_remove_altq(a);
640                 break;
641 #endif
642 #ifdef ALTQ_CODEL
643 	case ALTQT_CODEL:
644 		error = codel_remove_altq(a);
645 		break;
646 #endif
647 	default:
648 		error = ENXIO;
649 	}
650 
651 	return (error);
652 }
653 
654 /*
655  * add a queue to the discipline
656  * It is yet unclear what lock to use to protect this operation, the
657  * discipline specific functions will determine and grab it
658  */
659 int
660 altq_add_queue(struct pf_altq *a)
661 {
662 	int error = 0;
663 
664 	switch (a->scheduler) {
665 #ifdef ALTQ_CBQ
666 	case ALTQT_CBQ:
667 		error = cbq_add_queue(a);
668 		break;
669 #endif
670 #ifdef ALTQ_PRIQ
671 	case ALTQT_PRIQ:
672 		error = priq_add_queue(a);
673 		break;
674 #endif
675 #ifdef ALTQ_HFSC
676 	case ALTQT_HFSC:
677 		error = hfsc_add_queue(a);
678 		break;
679 #endif
680 #ifdef ALTQ_FAIRQ
681         case ALTQT_FAIRQ:
682                 error = fairq_add_queue(a);
683                 break;
684 #endif
685 	default:
686 		error = ENXIO;
687 	}
688 
689 	return (error);
690 }
691 
692 /*
693  * remove a queue from the discipline
694  * It is yet unclear what lock to use to protect this operation, the
695  * discipline specific functions will determine and grab it
696  */
697 int
698 altq_remove_queue(struct pf_altq *a)
699 {
700 	int error = 0;
701 
702 	switch (a->scheduler) {
703 #ifdef ALTQ_CBQ
704 	case ALTQT_CBQ:
705 		error = cbq_remove_queue(a);
706 		break;
707 #endif
708 #ifdef ALTQ_PRIQ
709 	case ALTQT_PRIQ:
710 		error = priq_remove_queue(a);
711 		break;
712 #endif
713 #ifdef ALTQ_HFSC
714 	case ALTQT_HFSC:
715 		error = hfsc_remove_queue(a);
716 		break;
717 #endif
718 #ifdef ALTQ_FAIRQ
719         case ALTQT_FAIRQ:
720                 error = fairq_remove_queue(a);
721                 break;
722 #endif
723 	default:
724 		error = ENXIO;
725 	}
726 
727 	return (error);
728 }
729 
730 /*
731  * get queue statistics
732  * Locking is done in the discipline specific functions with regards to
733  * copyout operations, also it is not yet clear which lock to use.
734  */
735 int
736 altq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes)
737 {
738 	int error = 0;
739 
740 	switch (a->scheduler) {
741 #ifdef ALTQ_CBQ
742 	case ALTQT_CBQ:
743 		error = cbq_getqstats(a, ubuf, nbytes);
744 		break;
745 #endif
746 #ifdef ALTQ_PRIQ
747 	case ALTQT_PRIQ:
748 		error = priq_getqstats(a, ubuf, nbytes);
749 		break;
750 #endif
751 #ifdef ALTQ_HFSC
752 	case ALTQT_HFSC:
753 		error = hfsc_getqstats(a, ubuf, nbytes);
754 		break;
755 #endif
756 #ifdef ALTQ_FAIRQ
757         case ALTQT_FAIRQ:
758                 error = fairq_getqstats(a, ubuf, nbytes);
759                 break;
760 #endif
761 #ifdef ALTQ_CODEL
762 	case ALTQT_CODEL:
763 		error = codel_getqstats(a, ubuf, nbytes);
764 		break;
765 #endif
766 	default:
767 		error = ENXIO;
768 	}
769 
770 	return (error);
771 }
772 
773 /*
774  * read and write diffserv field in IPv4 or IPv6 header
775  */
776 u_int8_t
777 read_dsfield(m, pktattr)
778 	struct mbuf *m;
779 	struct altq_pktattr *pktattr;
780 {
781 	struct mbuf *m0;
782 	u_int8_t ds_field = 0;
783 
784 	if (pktattr == NULL ||
785 	    (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6))
786 		return ((u_int8_t)0);
787 
788 	/* verify that pattr_hdr is within the mbuf data */
789 	for (m0 = m; m0 != NULL; m0 = m0->m_next)
790 		if ((pktattr->pattr_hdr >= m0->m_data) &&
791 		    (pktattr->pattr_hdr < m0->m_data + m0->m_len))
792 			break;
793 	if (m0 == NULL) {
794 		/* ick, pattr_hdr is stale */
795 		pktattr->pattr_af = AF_UNSPEC;
796 #ifdef ALTQ_DEBUG
797 		printf("read_dsfield: can't locate header!\n");
798 #endif
799 		return ((u_int8_t)0);
800 	}
801 
802 	if (pktattr->pattr_af == AF_INET) {
803 		struct ip *ip = (struct ip *)pktattr->pattr_hdr;
804 
805 		if (ip->ip_v != 4)
806 			return ((u_int8_t)0);	/* version mismatch! */
807 		ds_field = ip->ip_tos;
808 	}
809 #ifdef INET6
810 	else if (pktattr->pattr_af == AF_INET6) {
811 		struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr;
812 		u_int32_t flowlabel;
813 
814 		flowlabel = ntohl(ip6->ip6_flow);
815 		if ((flowlabel >> 28) != 6)
816 			return ((u_int8_t)0);	/* version mismatch! */
817 		ds_field = (flowlabel >> 20) & 0xff;
818 	}
819 #endif
820 	return (ds_field);
821 }
822 
823 void
824 write_dsfield(struct mbuf *m, struct altq_pktattr *pktattr, u_int8_t dsfield)
825 {
826 	struct mbuf *m0;
827 
828 	if (pktattr == NULL ||
829 	    (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6))
830 		return;
831 
832 	/* verify that pattr_hdr is within the mbuf data */
833 	for (m0 = m; m0 != NULL; m0 = m0->m_next)
834 		if ((pktattr->pattr_hdr >= m0->m_data) &&
835 		    (pktattr->pattr_hdr < m0->m_data + m0->m_len))
836 			break;
837 	if (m0 == NULL) {
838 		/* ick, pattr_hdr is stale */
839 		pktattr->pattr_af = AF_UNSPEC;
840 #ifdef ALTQ_DEBUG
841 		printf("write_dsfield: can't locate header!\n");
842 #endif
843 		return;
844 	}
845 
846 	if (pktattr->pattr_af == AF_INET) {
847 		struct ip *ip = (struct ip *)pktattr->pattr_hdr;
848 		u_int8_t old;
849 		int32_t sum;
850 
851 		if (ip->ip_v != 4)
852 			return;		/* version mismatch! */
853 		old = ip->ip_tos;
854 		dsfield |= old & 3;	/* leave CU bits */
855 		if (old == dsfield)
856 			return;
857 		ip->ip_tos = dsfield;
858 		/*
859 		 * update checksum (from RFC1624)
860 		 *	   HC' = ~(~HC + ~m + m')
861 		 */
862 		sum = ~ntohs(ip->ip_sum) & 0xffff;
863 		sum += 0xff00 + (~old & 0xff) + dsfield;
864 		sum = (sum >> 16) + (sum & 0xffff);
865 		sum += (sum >> 16);  /* add carry */
866 
867 		ip->ip_sum = htons(~sum & 0xffff);
868 	}
869 #ifdef INET6
870 	else if (pktattr->pattr_af == AF_INET6) {
871 		struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr;
872 		u_int32_t flowlabel;
873 
874 		flowlabel = ntohl(ip6->ip6_flow);
875 		if ((flowlabel >> 28) != 6)
876 			return;		/* version mismatch! */
877 		flowlabel = (flowlabel & 0xf03fffff) | (dsfield << 20);
878 		ip6->ip6_flow = htonl(flowlabel);
879 	}
880 #endif
881 	return;
882 }
883 
884 
885 /*
886  * high resolution clock support taking advantage of a machine dependent
887  * high resolution time counter (e.g., timestamp counter of intel pentium).
888  * we assume
889  *  - 64-bit-long monotonically-increasing counter
890  *  - frequency range is 100M-4GHz (CPU speed)
891  */
892 /* if pcc is not available or disabled, emulate 256MHz using microtime() */
893 #define	MACHCLK_SHIFT	8
894 
895 int machclk_usepcc;
896 u_int32_t machclk_freq;
897 u_int32_t machclk_per_tick;
898 
899 #if defined(__i386__) && defined(__NetBSD__)
900 extern u_int64_t cpu_tsc_freq;
901 #endif
902 
903 #if (__FreeBSD_version >= 700035)
904 /* Update TSC freq with the value indicated by the caller. */
905 static void
906 tsc_freq_changed(void *arg, const struct cf_level *level, int status)
907 {
908 	/* If there was an error during the transition, don't do anything. */
909 	if (status != 0)
910 		return;
911 
912 #if (__FreeBSD_version >= 701102) && (defined(__amd64__) || defined(__i386__))
913 	/* If TSC is P-state invariant, don't do anything. */
914 	if (tsc_is_invariant)
915 		return;
916 #endif
917 
918 	/* Total setting for this level gives the new frequency in MHz. */
919 	init_machclk();
920 }
921 EVENTHANDLER_DEFINE(cpufreq_post_change, tsc_freq_changed, NULL,
922     EVENTHANDLER_PRI_LAST);
923 #endif /* __FreeBSD_version >= 700035 */
924 
925 static void
926 init_machclk_setup(void)
927 {
928 #if (__FreeBSD_version >= 600000)
929 	callout_init(&tbr_callout, 0);
930 #endif
931 
932 	machclk_usepcc = 1;
933 
934 #if (!defined(__amd64__) && !defined(__i386__)) || defined(ALTQ_NOPCC)
935 	machclk_usepcc = 0;
936 #endif
937 #if defined(__FreeBSD__) && defined(SMP)
938 	machclk_usepcc = 0;
939 #endif
940 #if defined(__NetBSD__) && defined(MULTIPROCESSOR)
941 	machclk_usepcc = 0;
942 #endif
943 #if defined(__amd64__) || defined(__i386__)
944 	/* check if TSC is available */
945 	if ((cpu_feature & CPUID_TSC) == 0 ||
946 	    atomic_load_acq_64(&tsc_freq) == 0)
947 		machclk_usepcc = 0;
948 #endif
949 }
950 
951 void
952 init_machclk(void)
953 {
954 	static int called;
955 
956 	/* Call one-time initialization function. */
957 	if (!called) {
958 		init_machclk_setup();
959 		called = 1;
960 	}
961 
962 	if (machclk_usepcc == 0) {
963 		/* emulate 256MHz using microtime() */
964 		machclk_freq = 1000000 << MACHCLK_SHIFT;
965 		machclk_per_tick = machclk_freq / hz;
966 #ifdef ALTQ_DEBUG
967 		printf("altq: emulate %uHz cpu clock\n", machclk_freq);
968 #endif
969 		return;
970 	}
971 
972 	/*
973 	 * if the clock frequency (of Pentium TSC or Alpha PCC) is
974 	 * accessible, just use it.
975 	 */
976 #if defined(__amd64__) || defined(__i386__)
977 	machclk_freq = atomic_load_acq_64(&tsc_freq);
978 #endif
979 
980 	/*
981 	 * if we don't know the clock frequency, measure it.
982 	 */
983 	if (machclk_freq == 0) {
984 		static int	wait;
985 		struct timeval	tv_start, tv_end;
986 		u_int64_t	start, end, diff;
987 		int		timo;
988 
989 		microtime(&tv_start);
990 		start = read_machclk();
991 		timo = hz;	/* 1 sec */
992 		(void)tsleep(&wait, PWAIT | PCATCH, "init_machclk", timo);
993 		microtime(&tv_end);
994 		end = read_machclk();
995 		diff = (u_int64_t)(tv_end.tv_sec - tv_start.tv_sec) * 1000000
996 		    + tv_end.tv_usec - tv_start.tv_usec;
997 		if (diff != 0)
998 			machclk_freq = (u_int)((end - start) * 1000000 / diff);
999 	}
1000 
1001 	machclk_per_tick = machclk_freq / hz;
1002 
1003 #ifdef ALTQ_DEBUG
1004 	printf("altq: CPU clock: %uHz\n", machclk_freq);
1005 #endif
1006 }
1007 
1008 #if defined(__OpenBSD__) && defined(__i386__)
1009 static __inline u_int64_t
1010 rdtsc(void)
1011 {
1012 	u_int64_t rv;
1013 	__asm __volatile(".byte 0x0f, 0x31" : "=A" (rv));
1014 	return (rv);
1015 }
1016 #endif /* __OpenBSD__ && __i386__ */
1017 
1018 u_int64_t
1019 read_machclk(void)
1020 {
1021 	u_int64_t val;
1022 
1023 	if (machclk_usepcc) {
1024 #if defined(__amd64__) || defined(__i386__)
1025 		val = rdtsc();
1026 #else
1027 		panic("read_machclk");
1028 #endif
1029 	} else {
1030 		struct timeval tv;
1031 
1032 		microtime(&tv);
1033 		val = (((u_int64_t)(tv.tv_sec - boottime.tv_sec) * 1000000
1034 		    + tv.tv_usec) << MACHCLK_SHIFT);
1035 	}
1036 	return (val);
1037 }
1038 
1039 #ifdef ALTQ3_CLFIER_COMPAT
1040 
1041 #ifndef IPPROTO_ESP
1042 #define	IPPROTO_ESP	50		/* encapsulating security payload */
1043 #endif
1044 #ifndef IPPROTO_AH
1045 #define	IPPROTO_AH	51		/* authentication header */
1046 #endif
1047 
1048 /*
1049  * extract flow information from a given packet.
1050  * filt_mask shows flowinfo fields required.
1051  * we assume the ip header is in one mbuf, and addresses and ports are
1052  * in network byte order.
1053  */
1054 int
1055 altq_extractflow(m, af, flow, filt_bmask)
1056 	struct mbuf *m;
1057 	int af;
1058 	struct flowinfo *flow;
1059 	u_int32_t	filt_bmask;
1060 {
1061 
1062 	switch (af) {
1063 	case PF_INET: {
1064 		struct flowinfo_in *fin;
1065 		struct ip *ip;
1066 
1067 		ip = mtod(m, struct ip *);
1068 
1069 		if (ip->ip_v != 4)
1070 			break;
1071 
1072 		fin = (struct flowinfo_in *)flow;
1073 		fin->fi_len = sizeof(struct flowinfo_in);
1074 		fin->fi_family = AF_INET;
1075 
1076 		fin->fi_proto = ip->ip_p;
1077 		fin->fi_tos = ip->ip_tos;
1078 
1079 		fin->fi_src.s_addr = ip->ip_src.s_addr;
1080 		fin->fi_dst.s_addr = ip->ip_dst.s_addr;
1081 
1082 		if (filt_bmask & FIMB4_PORTS)
1083 			/* if port info is required, extract port numbers */
1084 			extract_ports4(m, ip, fin);
1085 		else {
1086 			fin->fi_sport = 0;
1087 			fin->fi_dport = 0;
1088 			fin->fi_gpi = 0;
1089 		}
1090 		return (1);
1091 	}
1092 
1093 #ifdef INET6
1094 	case PF_INET6: {
1095 		struct flowinfo_in6 *fin6;
1096 		struct ip6_hdr *ip6;
1097 
1098 		ip6 = mtod(m, struct ip6_hdr *);
1099 		/* should we check the ip version? */
1100 
1101 		fin6 = (struct flowinfo_in6 *)flow;
1102 		fin6->fi6_len = sizeof(struct flowinfo_in6);
1103 		fin6->fi6_family = AF_INET6;
1104 
1105 		fin6->fi6_proto = ip6->ip6_nxt;
1106 		fin6->fi6_tclass   = (ntohl(ip6->ip6_flow) >> 20) & 0xff;
1107 
1108 		fin6->fi6_flowlabel = ip6->ip6_flow & htonl(0x000fffff);
1109 		fin6->fi6_src = ip6->ip6_src;
1110 		fin6->fi6_dst = ip6->ip6_dst;
1111 
1112 		if ((filt_bmask & FIMB6_PORTS) ||
1113 		    ((filt_bmask & FIMB6_PROTO)
1114 		     && ip6->ip6_nxt > IPPROTO_IPV6))
1115 			/*
1116 			 * if port info is required, or proto is required
1117 			 * but there are option headers, extract port
1118 			 * and protocol numbers.
1119 			 */
1120 			extract_ports6(m, ip6, fin6);
1121 		else {
1122 			fin6->fi6_sport = 0;
1123 			fin6->fi6_dport = 0;
1124 			fin6->fi6_gpi = 0;
1125 		}
1126 		return (1);
1127 	}
1128 #endif /* INET6 */
1129 
1130 	default:
1131 		break;
1132 	}
1133 
1134 	/* failed */
1135 	flow->fi_len = sizeof(struct flowinfo);
1136 	flow->fi_family = AF_UNSPEC;
1137 	return (0);
1138 }
1139 
1140 /*
1141  * helper routine to extract port numbers
1142  */
1143 /* structure for ipsec and ipv6 option header template */
1144 struct _opt6 {
1145 	u_int8_t	opt6_nxt;	/* next header */
1146 	u_int8_t	opt6_hlen;	/* header extension length */
1147 	u_int16_t	_pad;
1148 	u_int32_t	ah_spi;		/* security parameter index
1149 					   for authentication header */
1150 };
1151 
1152 /*
1153  * extract port numbers from a ipv4 packet.
1154  */
1155 static int
1156 extract_ports4(m, ip, fin)
1157 	struct mbuf *m;
1158 	struct ip *ip;
1159 	struct flowinfo_in *fin;
1160 {
1161 	struct mbuf *m0;
1162 	u_short ip_off;
1163 	u_int8_t proto;
1164 	int 	off;
1165 
1166 	fin->fi_sport = 0;
1167 	fin->fi_dport = 0;
1168 	fin->fi_gpi = 0;
1169 
1170 	ip_off = ntohs(ip->ip_off);
1171 	/* if it is a fragment, try cached fragment info */
1172 	if (ip_off & IP_OFFMASK) {
1173 		ip4f_lookup(ip, fin);
1174 		return (1);
1175 	}
1176 
1177 	/* locate the mbuf containing the protocol header */
1178 	for (m0 = m; m0 != NULL; m0 = m0->m_next)
1179 		if (((caddr_t)ip >= m0->m_data) &&
1180 		    ((caddr_t)ip < m0->m_data + m0->m_len))
1181 			break;
1182 	if (m0 == NULL) {
1183 #ifdef ALTQ_DEBUG
1184 		printf("extract_ports4: can't locate header! ip=%p\n", ip);
1185 #endif
1186 		return (0);
1187 	}
1188 	off = ((caddr_t)ip - m0->m_data) + (ip->ip_hl << 2);
1189 	proto = ip->ip_p;
1190 
1191 #ifdef ALTQ_IPSEC
1192  again:
1193 #endif
1194 	while (off >= m0->m_len) {
1195 		off -= m0->m_len;
1196 		m0 = m0->m_next;
1197 		if (m0 == NULL)
1198 			return (0);  /* bogus ip_hl! */
1199 	}
1200 	if (m0->m_len < off + 4)
1201 		return (0);
1202 
1203 	switch (proto) {
1204 	case IPPROTO_TCP:
1205 	case IPPROTO_UDP: {
1206 		struct udphdr *udp;
1207 
1208 		udp = (struct udphdr *)(mtod(m0, caddr_t) + off);
1209 		fin->fi_sport = udp->uh_sport;
1210 		fin->fi_dport = udp->uh_dport;
1211 		fin->fi_proto = proto;
1212 		}
1213 		break;
1214 
1215 #ifdef ALTQ_IPSEC
1216 	case IPPROTO_ESP:
1217 		if (fin->fi_gpi == 0){
1218 			u_int32_t *gpi;
1219 
1220 			gpi = (u_int32_t *)(mtod(m0, caddr_t) + off);
1221 			fin->fi_gpi   = *gpi;
1222 		}
1223 		fin->fi_proto = proto;
1224 		break;
1225 
1226 	case IPPROTO_AH: {
1227 			/* get next header and header length */
1228 			struct _opt6 *opt6;
1229 
1230 			opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1231 			proto = opt6->opt6_nxt;
1232 			off += 8 + (opt6->opt6_hlen * 4);
1233 			if (fin->fi_gpi == 0 && m0->m_len >= off + 8)
1234 				fin->fi_gpi = opt6->ah_spi;
1235 		}
1236 		/* goto the next header */
1237 		goto again;
1238 #endif  /* ALTQ_IPSEC */
1239 
1240 	default:
1241 		fin->fi_proto = proto;
1242 		return (0);
1243 	}
1244 
1245 	/* if this is a first fragment, cache it. */
1246 	if (ip_off & IP_MF)
1247 		ip4f_cache(ip, fin);
1248 
1249 	return (1);
1250 }
1251 
1252 #ifdef INET6
1253 static int
1254 extract_ports6(m, ip6, fin6)
1255 	struct mbuf *m;
1256 	struct ip6_hdr *ip6;
1257 	struct flowinfo_in6 *fin6;
1258 {
1259 	struct mbuf *m0;
1260 	int	off;
1261 	u_int8_t proto;
1262 
1263 	fin6->fi6_gpi   = 0;
1264 	fin6->fi6_sport = 0;
1265 	fin6->fi6_dport = 0;
1266 
1267 	/* locate the mbuf containing the protocol header */
1268 	for (m0 = m; m0 != NULL; m0 = m0->m_next)
1269 		if (((caddr_t)ip6 >= m0->m_data) &&
1270 		    ((caddr_t)ip6 < m0->m_data + m0->m_len))
1271 			break;
1272 	if (m0 == NULL) {
1273 #ifdef ALTQ_DEBUG
1274 		printf("extract_ports6: can't locate header! ip6=%p\n", ip6);
1275 #endif
1276 		return (0);
1277 	}
1278 	off = ((caddr_t)ip6 - m0->m_data) + sizeof(struct ip6_hdr);
1279 
1280 	proto = ip6->ip6_nxt;
1281 	do {
1282 		while (off >= m0->m_len) {
1283 			off -= m0->m_len;
1284 			m0 = m0->m_next;
1285 			if (m0 == NULL)
1286 				return (0);
1287 		}
1288 		if (m0->m_len < off + 4)
1289 			return (0);
1290 
1291 		switch (proto) {
1292 		case IPPROTO_TCP:
1293 		case IPPROTO_UDP: {
1294 			struct udphdr *udp;
1295 
1296 			udp = (struct udphdr *)(mtod(m0, caddr_t) + off);
1297 			fin6->fi6_sport = udp->uh_sport;
1298 			fin6->fi6_dport = udp->uh_dport;
1299 			fin6->fi6_proto = proto;
1300 			}
1301 			return (1);
1302 
1303 		case IPPROTO_ESP:
1304 			if (fin6->fi6_gpi == 0) {
1305 				u_int32_t *gpi;
1306 
1307 				gpi = (u_int32_t *)(mtod(m0, caddr_t) + off);
1308 				fin6->fi6_gpi   = *gpi;
1309 			}
1310 			fin6->fi6_proto = proto;
1311 			return (1);
1312 
1313 		case IPPROTO_AH: {
1314 			/* get next header and header length */
1315 			struct _opt6 *opt6;
1316 
1317 			opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1318 			if (fin6->fi6_gpi == 0 && m0->m_len >= off + 8)
1319 				fin6->fi6_gpi = opt6->ah_spi;
1320 			proto = opt6->opt6_nxt;
1321 			off += 8 + (opt6->opt6_hlen * 4);
1322 			/* goto the next header */
1323 			break;
1324 			}
1325 
1326 		case IPPROTO_HOPOPTS:
1327 		case IPPROTO_ROUTING:
1328 		case IPPROTO_DSTOPTS: {
1329 			/* get next header and header length */
1330 			struct _opt6 *opt6;
1331 
1332 			opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1333 			proto = opt6->opt6_nxt;
1334 			off += (opt6->opt6_hlen + 1) * 8;
1335 			/* goto the next header */
1336 			break;
1337 			}
1338 
1339 		case IPPROTO_FRAGMENT:
1340 			/* ipv6 fragmentations are not supported yet */
1341 		default:
1342 			fin6->fi6_proto = proto;
1343 			return (0);
1344 		}
1345 	} while (1);
1346 	/*NOTREACHED*/
1347 }
1348 #endif /* INET6 */
1349 
1350 /*
1351  * altq common classifier
1352  */
1353 int
1354 acc_add_filter(classifier, filter, class, phandle)
1355 	struct acc_classifier *classifier;
1356 	struct flow_filter *filter;
1357 	void	*class;
1358 	u_long	*phandle;
1359 {
1360 	struct acc_filter *afp, *prev, *tmp;
1361 	int	i, s;
1362 
1363 #ifdef INET6
1364 	if (filter->ff_flow.fi_family != AF_INET &&
1365 	    filter->ff_flow.fi_family != AF_INET6)
1366 		return (EINVAL);
1367 #else
1368 	if (filter->ff_flow.fi_family != AF_INET)
1369 		return (EINVAL);
1370 #endif
1371 
1372 	afp = malloc(sizeof(struct acc_filter),
1373 	       M_DEVBUF, M_WAITOK);
1374 	if (afp == NULL)
1375 		return (ENOMEM);
1376 	bzero(afp, sizeof(struct acc_filter));
1377 
1378 	afp->f_filter = *filter;
1379 	afp->f_class = class;
1380 
1381 	i = ACC_WILDCARD_INDEX;
1382 	if (filter->ff_flow.fi_family == AF_INET) {
1383 		struct flow_filter *filter4 = &afp->f_filter;
1384 
1385 		/*
1386 		 * if address is 0, it's a wildcard.  if address mask
1387 		 * isn't set, use full mask.
1388 		 */
1389 		if (filter4->ff_flow.fi_dst.s_addr == 0)
1390 			filter4->ff_mask.mask_dst.s_addr = 0;
1391 		else if (filter4->ff_mask.mask_dst.s_addr == 0)
1392 			filter4->ff_mask.mask_dst.s_addr = 0xffffffff;
1393 		if (filter4->ff_flow.fi_src.s_addr == 0)
1394 			filter4->ff_mask.mask_src.s_addr = 0;
1395 		else if (filter4->ff_mask.mask_src.s_addr == 0)
1396 			filter4->ff_mask.mask_src.s_addr = 0xffffffff;
1397 
1398 		/* clear extra bits in addresses  */
1399 		   filter4->ff_flow.fi_dst.s_addr &=
1400 		       filter4->ff_mask.mask_dst.s_addr;
1401 		   filter4->ff_flow.fi_src.s_addr &=
1402 		       filter4->ff_mask.mask_src.s_addr;
1403 
1404 		/*
1405 		 * if dst address is a wildcard, use hash-entry
1406 		 * ACC_WILDCARD_INDEX.
1407 		 */
1408 		if (filter4->ff_mask.mask_dst.s_addr != 0xffffffff)
1409 			i = ACC_WILDCARD_INDEX;
1410 		else
1411 			i = ACC_GET_HASH_INDEX(filter4->ff_flow.fi_dst.s_addr);
1412 	}
1413 #ifdef INET6
1414 	else if (filter->ff_flow.fi_family == AF_INET6) {
1415 		struct flow_filter6 *filter6 =
1416 			(struct flow_filter6 *)&afp->f_filter;
1417 #ifndef IN6MASK0 /* taken from kame ipv6 */
1418 #define	IN6MASK0	{{{ 0, 0, 0, 0 }}}
1419 #define	IN6MASK128	{{{ 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff }}}
1420 		const struct in6_addr in6mask0 = IN6MASK0;
1421 		const struct in6_addr in6mask128 = IN6MASK128;
1422 #endif
1423 
1424 		if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_flow6.fi6_dst))
1425 			filter6->ff_mask6.mask6_dst = in6mask0;
1426 		else if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_mask6.mask6_dst))
1427 			filter6->ff_mask6.mask6_dst = in6mask128;
1428 		if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_flow6.fi6_src))
1429 			filter6->ff_mask6.mask6_src = in6mask0;
1430 		else if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_mask6.mask6_src))
1431 			filter6->ff_mask6.mask6_src = in6mask128;
1432 
1433 		/* clear extra bits in addresses  */
1434 		for (i = 0; i < 16; i++)
1435 			filter6->ff_flow6.fi6_dst.s6_addr[i] &=
1436 			    filter6->ff_mask6.mask6_dst.s6_addr[i];
1437 		for (i = 0; i < 16; i++)
1438 			filter6->ff_flow6.fi6_src.s6_addr[i] &=
1439 			    filter6->ff_mask6.mask6_src.s6_addr[i];
1440 
1441 		if (filter6->ff_flow6.fi6_flowlabel == 0)
1442 			i = ACC_WILDCARD_INDEX;
1443 		else
1444 			i = ACC_GET_HASH_INDEX(filter6->ff_flow6.fi6_flowlabel);
1445 	}
1446 #endif /* INET6 */
1447 
1448 	afp->f_handle = get_filt_handle(classifier, i);
1449 
1450 	/* update filter bitmask */
1451 	afp->f_fbmask = filt2fibmask(filter);
1452 	classifier->acc_fbmask |= afp->f_fbmask;
1453 
1454 	/*
1455 	 * add this filter to the filter list.
1456 	 * filters are ordered from the highest rule number.
1457 	 */
1458 	s = splnet();
1459 	prev = NULL;
1460 	LIST_FOREACH(tmp, &classifier->acc_filters[i], f_chain) {
1461 		if (tmp->f_filter.ff_ruleno > afp->f_filter.ff_ruleno)
1462 			prev = tmp;
1463 		else
1464 			break;
1465 	}
1466 	if (prev == NULL)
1467 		LIST_INSERT_HEAD(&classifier->acc_filters[i], afp, f_chain);
1468 	else
1469 		LIST_INSERT_AFTER(prev, afp, f_chain);
1470 	splx(s);
1471 
1472 	*phandle = afp->f_handle;
1473 	return (0);
1474 }
1475 
1476 int
1477 acc_delete_filter(classifier, handle)
1478 	struct acc_classifier *classifier;
1479 	u_long handle;
1480 {
1481 	struct acc_filter *afp;
1482 	int	s;
1483 
1484 	if ((afp = filth_to_filtp(classifier, handle)) == NULL)
1485 		return (EINVAL);
1486 
1487 	s = splnet();
1488 	LIST_REMOVE(afp, f_chain);
1489 	splx(s);
1490 
1491 	free(afp, M_DEVBUF);
1492 
1493 	/* todo: update filt_bmask */
1494 
1495 	return (0);
1496 }
1497 
1498 /*
1499  * delete filters referencing to the specified class.
1500  * if the all flag is not 0, delete all the filters.
1501  */
1502 int
1503 acc_discard_filters(classifier, class, all)
1504 	struct acc_classifier *classifier;
1505 	void	*class;
1506 	int	all;
1507 {
1508 	struct acc_filter *afp;
1509 	int	i, s;
1510 
1511 	s = splnet();
1512 	for (i = 0; i < ACC_FILTER_TABLESIZE; i++) {
1513 		do {
1514 			LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1515 				if (all || afp->f_class == class) {
1516 					LIST_REMOVE(afp, f_chain);
1517 					free(afp, M_DEVBUF);
1518 					/* start again from the head */
1519 					break;
1520 				}
1521 		} while (afp != NULL);
1522 	}
1523 	splx(s);
1524 
1525 	if (all)
1526 		classifier->acc_fbmask = 0;
1527 
1528 	return (0);
1529 }
1530 
1531 void *
1532 acc_classify(clfier, m, af)
1533 	void *clfier;
1534 	struct mbuf *m;
1535 	int af;
1536 {
1537 	struct acc_classifier *classifier;
1538 	struct flowinfo flow;
1539 	struct acc_filter *afp;
1540 	int	i;
1541 
1542 	classifier = (struct acc_classifier *)clfier;
1543 	altq_extractflow(m, af, &flow, classifier->acc_fbmask);
1544 
1545 	if (flow.fi_family == AF_INET) {
1546 		struct flowinfo_in *fp = (struct flowinfo_in *)&flow;
1547 
1548 		if ((classifier->acc_fbmask & FIMB4_ALL) == FIMB4_TOS) {
1549 			/* only tos is used */
1550 			LIST_FOREACH(afp,
1551 				 &classifier->acc_filters[ACC_WILDCARD_INDEX],
1552 				 f_chain)
1553 				if (apply_tosfilter4(afp->f_fbmask,
1554 						     &afp->f_filter, fp))
1555 					/* filter matched */
1556 					return (afp->f_class);
1557 		} else if ((classifier->acc_fbmask &
1558 			(~(FIMB4_PROTO|FIMB4_SPORT|FIMB4_DPORT) & FIMB4_ALL))
1559 		    == 0) {
1560 			/* only proto and ports are used */
1561 			LIST_FOREACH(afp,
1562 				 &classifier->acc_filters[ACC_WILDCARD_INDEX],
1563 				 f_chain)
1564 				if (apply_ppfilter4(afp->f_fbmask,
1565 						    &afp->f_filter, fp))
1566 					/* filter matched */
1567 					return (afp->f_class);
1568 		} else {
1569 			/* get the filter hash entry from its dest address */
1570 			i = ACC_GET_HASH_INDEX(fp->fi_dst.s_addr);
1571 			do {
1572 				/*
1573 				 * go through this loop twice.  first for dst
1574 				 * hash, second for wildcards.
1575 				 */
1576 				LIST_FOREACH(afp, &classifier->acc_filters[i],
1577 					     f_chain)
1578 					if (apply_filter4(afp->f_fbmask,
1579 							  &afp->f_filter, fp))
1580 						/* filter matched */
1581 						return (afp->f_class);
1582 
1583 				/*
1584 				 * check again for filters with a dst addr
1585 				 * wildcard.
1586 				 * (daddr == 0 || dmask != 0xffffffff).
1587 				 */
1588 				if (i != ACC_WILDCARD_INDEX)
1589 					i = ACC_WILDCARD_INDEX;
1590 				else
1591 					break;
1592 			} while (1);
1593 		}
1594 	}
1595 #ifdef INET6
1596 	else if (flow.fi_family == AF_INET6) {
1597 		struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)&flow;
1598 
1599 		/* get the filter hash entry from its flow ID */
1600 		if (fp6->fi6_flowlabel != 0)
1601 			i = ACC_GET_HASH_INDEX(fp6->fi6_flowlabel);
1602 		else
1603 			/* flowlable can be zero */
1604 			i = ACC_WILDCARD_INDEX;
1605 
1606 		/* go through this loop twice.  first for flow hash, second
1607 		   for wildcards. */
1608 		do {
1609 			LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1610 				if (apply_filter6(afp->f_fbmask,
1611 					(struct flow_filter6 *)&afp->f_filter,
1612 					fp6))
1613 					/* filter matched */
1614 					return (afp->f_class);
1615 
1616 			/*
1617 			 * check again for filters with a wildcard.
1618 			 */
1619 			if (i != ACC_WILDCARD_INDEX)
1620 				i = ACC_WILDCARD_INDEX;
1621 			else
1622 				break;
1623 		} while (1);
1624 	}
1625 #endif /* INET6 */
1626 
1627 	/* no filter matched */
1628 	return (NULL);
1629 }
1630 
1631 static int
1632 apply_filter4(fbmask, filt, pkt)
1633 	u_int32_t	fbmask;
1634 	struct flow_filter *filt;
1635 	struct flowinfo_in *pkt;
1636 {
1637 	if (filt->ff_flow.fi_family != AF_INET)
1638 		return (0);
1639 	if ((fbmask & FIMB4_SPORT) && filt->ff_flow.fi_sport != pkt->fi_sport)
1640 		return (0);
1641 	if ((fbmask & FIMB4_DPORT) && filt->ff_flow.fi_dport != pkt->fi_dport)
1642 		return (0);
1643 	if ((fbmask & FIMB4_DADDR) &&
1644 	    filt->ff_flow.fi_dst.s_addr !=
1645 	    (pkt->fi_dst.s_addr & filt->ff_mask.mask_dst.s_addr))
1646 		return (0);
1647 	if ((fbmask & FIMB4_SADDR) &&
1648 	    filt->ff_flow.fi_src.s_addr !=
1649 	    (pkt->fi_src.s_addr & filt->ff_mask.mask_src.s_addr))
1650 		return (0);
1651 	if ((fbmask & FIMB4_PROTO) && filt->ff_flow.fi_proto != pkt->fi_proto)
1652 		return (0);
1653 	if ((fbmask & FIMB4_TOS) && filt->ff_flow.fi_tos !=
1654 	    (pkt->fi_tos & filt->ff_mask.mask_tos))
1655 		return (0);
1656 	if ((fbmask & FIMB4_GPI) && filt->ff_flow.fi_gpi != (pkt->fi_gpi))
1657 		return (0);
1658 	/* match */
1659 	return (1);
1660 }
1661 
1662 /*
1663  * filter matching function optimized for a common case that checks
1664  * only protocol and port numbers
1665  */
1666 static int
1667 apply_ppfilter4(fbmask, filt, pkt)
1668 	u_int32_t	fbmask;
1669 	struct flow_filter *filt;
1670 	struct flowinfo_in *pkt;
1671 {
1672 	if (filt->ff_flow.fi_family != AF_INET)
1673 		return (0);
1674 	if ((fbmask & FIMB4_SPORT) && filt->ff_flow.fi_sport != pkt->fi_sport)
1675 		return (0);
1676 	if ((fbmask & FIMB4_DPORT) && filt->ff_flow.fi_dport != pkt->fi_dport)
1677 		return (0);
1678 	if ((fbmask & FIMB4_PROTO) && filt->ff_flow.fi_proto != pkt->fi_proto)
1679 		return (0);
1680 	/* match */
1681 	return (1);
1682 }
1683 
1684 /*
1685  * filter matching function only for tos field.
1686  */
1687 static int
1688 apply_tosfilter4(fbmask, filt, pkt)
1689 	u_int32_t	fbmask;
1690 	struct flow_filter *filt;
1691 	struct flowinfo_in *pkt;
1692 {
1693 	if (filt->ff_flow.fi_family != AF_INET)
1694 		return (0);
1695 	if ((fbmask & FIMB4_TOS) && filt->ff_flow.fi_tos !=
1696 	    (pkt->fi_tos & filt->ff_mask.mask_tos))
1697 		return (0);
1698 	/* match */
1699 	return (1);
1700 }
1701 
1702 #ifdef INET6
1703 static int
1704 apply_filter6(fbmask, filt, pkt)
1705 	u_int32_t	fbmask;
1706 	struct flow_filter6 *filt;
1707 	struct flowinfo_in6 *pkt;
1708 {
1709 	int i;
1710 
1711 	if (filt->ff_flow6.fi6_family != AF_INET6)
1712 		return (0);
1713 	if ((fbmask & FIMB6_FLABEL) &&
1714 	    filt->ff_flow6.fi6_flowlabel != pkt->fi6_flowlabel)
1715 		return (0);
1716 	if ((fbmask & FIMB6_PROTO) &&
1717 	    filt->ff_flow6.fi6_proto != pkt->fi6_proto)
1718 		return (0);
1719 	if ((fbmask & FIMB6_SPORT) &&
1720 	    filt->ff_flow6.fi6_sport != pkt->fi6_sport)
1721 		return (0);
1722 	if ((fbmask & FIMB6_DPORT) &&
1723 	    filt->ff_flow6.fi6_dport != pkt->fi6_dport)
1724 		return (0);
1725 	if (fbmask & FIMB6_SADDR) {
1726 		for (i = 0; i < 4; i++)
1727 			if (filt->ff_flow6.fi6_src.s6_addr32[i] !=
1728 			    (pkt->fi6_src.s6_addr32[i] &
1729 			     filt->ff_mask6.mask6_src.s6_addr32[i]))
1730 				return (0);
1731 	}
1732 	if (fbmask & FIMB6_DADDR) {
1733 		for (i = 0; i < 4; i++)
1734 			if (filt->ff_flow6.fi6_dst.s6_addr32[i] !=
1735 			    (pkt->fi6_dst.s6_addr32[i] &
1736 			     filt->ff_mask6.mask6_dst.s6_addr32[i]))
1737 				return (0);
1738 	}
1739 	if ((fbmask & FIMB6_TCLASS) &&
1740 	    filt->ff_flow6.fi6_tclass !=
1741 	    (pkt->fi6_tclass & filt->ff_mask6.mask6_tclass))
1742 		return (0);
1743 	if ((fbmask & FIMB6_GPI) &&
1744 	    filt->ff_flow6.fi6_gpi != pkt->fi6_gpi)
1745 		return (0);
1746 	/* match */
1747 	return (1);
1748 }
1749 #endif /* INET6 */
1750 
1751 /*
1752  *  filter handle:
1753  *	bit 20-28: index to the filter hash table
1754  *	bit  0-19: unique id in the hash bucket.
1755  */
1756 static u_long
1757 get_filt_handle(classifier, i)
1758 	struct acc_classifier *classifier;
1759 	int	i;
1760 {
1761 	static u_long handle_number = 1;
1762 	u_long 	handle;
1763 	struct acc_filter *afp;
1764 
1765 	while (1) {
1766 		handle = handle_number++ & 0x000fffff;
1767 
1768 		if (LIST_EMPTY(&classifier->acc_filters[i]))
1769 			break;
1770 
1771 		LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1772 			if ((afp->f_handle & 0x000fffff) == handle)
1773 				break;
1774 		if (afp == NULL)
1775 			break;
1776 		/* this handle is already used, try again */
1777 	}
1778 
1779 	return ((i << 20) | handle);
1780 }
1781 
1782 /* convert filter handle to filter pointer */
1783 static struct acc_filter *
1784 filth_to_filtp(classifier, handle)
1785 	struct acc_classifier *classifier;
1786 	u_long handle;
1787 {
1788 	struct acc_filter *afp;
1789 	int	i;
1790 
1791 	i = ACC_GET_HINDEX(handle);
1792 
1793 	LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1794 		if (afp->f_handle == handle)
1795 			return (afp);
1796 
1797 	return (NULL);
1798 }
1799 
1800 /* create flowinfo bitmask */
1801 static u_int32_t
1802 filt2fibmask(filt)
1803 	struct flow_filter *filt;
1804 {
1805 	u_int32_t mask = 0;
1806 #ifdef INET6
1807 	struct flow_filter6 *filt6;
1808 #endif
1809 
1810 	switch (filt->ff_flow.fi_family) {
1811 	case AF_INET:
1812 		if (filt->ff_flow.fi_proto != 0)
1813 			mask |= FIMB4_PROTO;
1814 		if (filt->ff_flow.fi_tos != 0)
1815 			mask |= FIMB4_TOS;
1816 		if (filt->ff_flow.fi_dst.s_addr != 0)
1817 			mask |= FIMB4_DADDR;
1818 		if (filt->ff_flow.fi_src.s_addr != 0)
1819 			mask |= FIMB4_SADDR;
1820 		if (filt->ff_flow.fi_sport != 0)
1821 			mask |= FIMB4_SPORT;
1822 		if (filt->ff_flow.fi_dport != 0)
1823 			mask |= FIMB4_DPORT;
1824 		if (filt->ff_flow.fi_gpi != 0)
1825 			mask |= FIMB4_GPI;
1826 		break;
1827 #ifdef INET6
1828 	case AF_INET6:
1829 		filt6 = (struct flow_filter6 *)filt;
1830 
1831 		if (filt6->ff_flow6.fi6_proto != 0)
1832 			mask |= FIMB6_PROTO;
1833 		if (filt6->ff_flow6.fi6_tclass != 0)
1834 			mask |= FIMB6_TCLASS;
1835 		if (!IN6_IS_ADDR_UNSPECIFIED(&filt6->ff_flow6.fi6_dst))
1836 			mask |= FIMB6_DADDR;
1837 		if (!IN6_IS_ADDR_UNSPECIFIED(&filt6->ff_flow6.fi6_src))
1838 			mask |= FIMB6_SADDR;
1839 		if (filt6->ff_flow6.fi6_sport != 0)
1840 			mask |= FIMB6_SPORT;
1841 		if (filt6->ff_flow6.fi6_dport != 0)
1842 			mask |= FIMB6_DPORT;
1843 		if (filt6->ff_flow6.fi6_gpi != 0)
1844 			mask |= FIMB6_GPI;
1845 		if (filt6->ff_flow6.fi6_flowlabel != 0)
1846 			mask |= FIMB6_FLABEL;
1847 		break;
1848 #endif /* INET6 */
1849 	}
1850 	return (mask);
1851 }
1852 
1853 
1854 /*
1855  * helper functions to handle IPv4 fragments.
1856  * currently only in-sequence fragments are handled.
1857  *	- fragment info is cached in a LRU list.
1858  *	- when a first fragment is found, cache its flow info.
1859  *	- when a non-first fragment is found, lookup the cache.
1860  */
1861 
1862 struct ip4_frag {
1863     TAILQ_ENTRY(ip4_frag) ip4f_chain;
1864     char    ip4f_valid;
1865     u_short ip4f_id;
1866     struct flowinfo_in ip4f_info;
1867 };
1868 
1869 static TAILQ_HEAD(ip4f_list, ip4_frag) ip4f_list; /* IPv4 fragment cache */
1870 
1871 #define	IP4F_TABSIZE		16	/* IPv4 fragment cache size */
1872 
1873 
1874 static void
1875 ip4f_cache(ip, fin)
1876 	struct ip *ip;
1877 	struct flowinfo_in *fin;
1878 {
1879 	struct ip4_frag *fp;
1880 
1881 	if (TAILQ_EMPTY(&ip4f_list)) {
1882 		/* first time call, allocate fragment cache entries. */
1883 		if (ip4f_init() < 0)
1884 			/* allocation failed! */
1885 			return;
1886 	}
1887 
1888 	fp = ip4f_alloc();
1889 	fp->ip4f_id = ip->ip_id;
1890 	fp->ip4f_info.fi_proto = ip->ip_p;
1891 	fp->ip4f_info.fi_src.s_addr = ip->ip_src.s_addr;
1892 	fp->ip4f_info.fi_dst.s_addr = ip->ip_dst.s_addr;
1893 
1894 	/* save port numbers */
1895 	fp->ip4f_info.fi_sport = fin->fi_sport;
1896 	fp->ip4f_info.fi_dport = fin->fi_dport;
1897 	fp->ip4f_info.fi_gpi   = fin->fi_gpi;
1898 }
1899 
1900 static int
1901 ip4f_lookup(ip, fin)
1902 	struct ip *ip;
1903 	struct flowinfo_in *fin;
1904 {
1905 	struct ip4_frag *fp;
1906 
1907 	for (fp = TAILQ_FIRST(&ip4f_list); fp != NULL && fp->ip4f_valid;
1908 	     fp = TAILQ_NEXT(fp, ip4f_chain))
1909 		if (ip->ip_id == fp->ip4f_id &&
1910 		    ip->ip_src.s_addr == fp->ip4f_info.fi_src.s_addr &&
1911 		    ip->ip_dst.s_addr == fp->ip4f_info.fi_dst.s_addr &&
1912 		    ip->ip_p == fp->ip4f_info.fi_proto) {
1913 
1914 			/* found the matching entry */
1915 			fin->fi_sport = fp->ip4f_info.fi_sport;
1916 			fin->fi_dport = fp->ip4f_info.fi_dport;
1917 			fin->fi_gpi   = fp->ip4f_info.fi_gpi;
1918 
1919 			if ((ntohs(ip->ip_off) & IP_MF) == 0)
1920 				/* this is the last fragment,
1921 				   release the entry. */
1922 				ip4f_free(fp);
1923 
1924 			return (1);
1925 		}
1926 
1927 	/* no matching entry found */
1928 	return (0);
1929 }
1930 
1931 static int
1932 ip4f_init(void)
1933 {
1934 	struct ip4_frag *fp;
1935 	int i;
1936 
1937 	TAILQ_INIT(&ip4f_list);
1938 	for (i=0; i<IP4F_TABSIZE; i++) {
1939 		fp = malloc(sizeof(struct ip4_frag),
1940 		       M_DEVBUF, M_NOWAIT);
1941 		if (fp == NULL) {
1942 			printf("ip4f_init: can't alloc %dth entry!\n", i);
1943 			if (i == 0)
1944 				return (-1);
1945 			return (0);
1946 		}
1947 		fp->ip4f_valid = 0;
1948 		TAILQ_INSERT_TAIL(&ip4f_list, fp, ip4f_chain);
1949 	}
1950 	return (0);
1951 }
1952 
1953 static struct ip4_frag *
1954 ip4f_alloc(void)
1955 {
1956 	struct ip4_frag *fp;
1957 
1958 	/* reclaim an entry at the tail, put it at the head */
1959 	fp = TAILQ_LAST(&ip4f_list, ip4f_list);
1960 	TAILQ_REMOVE(&ip4f_list, fp, ip4f_chain);
1961 	fp->ip4f_valid = 1;
1962 	TAILQ_INSERT_HEAD(&ip4f_list, fp, ip4f_chain);
1963 	return (fp);
1964 }
1965 
1966 static void
1967 ip4f_free(fp)
1968 	struct ip4_frag *fp;
1969 {
1970 	TAILQ_REMOVE(&ip4f_list, fp, ip4f_chain);
1971 	fp->ip4f_valid = 0;
1972 	TAILQ_INSERT_TAIL(&ip4f_list, fp, ip4f_chain);
1973 }
1974 
1975 #endif /* ALTQ3_CLFIER_COMPAT */
1976