2 /* $KAME: altq_subr.c,v 1.21 2003/11/06 06:32:53 kjc Exp $ */
5 * Copyright (C) 1997-2003
6 * Sony Computer Science Laboratories Inc. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 #if defined(__FreeBSD__) || defined(__NetBSD__)
34 #include "opt_inet6.h"
36 #endif /* __FreeBSD__ || __NetBSD__ */
38 #include <sys/param.h>
39 #include <sys/malloc.h>
41 #include <sys/systm.h>
43 #include <sys/socket.h>
44 #include <sys/socketvar.h>
45 #include <sys/kernel.h>
46 #include <sys/errno.h>
47 #include <sys/syslog.h>
48 #include <sys/sysctl.h>
49 #include <sys/queue.h>
52 #include <net/if_dl.h>
53 #include <net/if_types.h>
58 #include <netinet/in.h>
59 #include <netinet/in_systm.h>
60 #include <netinet/ip.h>
62 #include <netinet/ip6.h>
64 #include <netinet/tcp.h>
65 #include <netinet/udp.h>
67 #include <net/pfvar.h>
68 #include <altq/altq.h>
70 #include <altq/altq_conf.h>
73 /* machine dependent clock related includes */
77 #include <sys/eventhandler.h>
78 #include <machine/clock.h>
80 #if defined(__amd64__) || defined(__i386__)
81 #include <machine/cpufunc.h> /* for pentium tsc */
82 #include <machine/specialreg.h> /* for CPUID_TSC */
84 #include <machine/md_var.h> /* for cpu_feature */
85 #elif defined(__NetBSD__) || defined(__OpenBSD__)
86 #include <machine/cpu.h> /* for cpu_feature */
88 #endif /* __amd64 || __i386__ */
91 * internal function prototypes
93 static void tbr_timeout(void *);
94 int (*altq_input)(struct mbuf *, int) = NULL;
95 static struct mbuf *tbr_dequeue(struct ifaltq *, int);
96 static int tbr_timer = 0; /* token bucket regulator timer */
97 #if !defined(__FreeBSD__) || (__FreeBSD_version < 600000)
98 static struct callout tbr_callout = CALLOUT_INITIALIZER;
100 static struct callout tbr_callout;
103 #ifdef ALTQ3_CLFIER_COMPAT
104 static int extract_ports4(struct mbuf *, struct ip *, struct flowinfo_in *);
106 static int extract_ports6(struct mbuf *, struct ip6_hdr *,
107 struct flowinfo_in6 *);
109 static int apply_filter4(u_int32_t, struct flow_filter *,
110 struct flowinfo_in *);
111 static int apply_ppfilter4(u_int32_t, struct flow_filter *,
112 struct flowinfo_in *);
114 static int apply_filter6(u_int32_t, struct flow_filter6 *,
115 struct flowinfo_in6 *);
117 static int apply_tosfilter4(u_int32_t, struct flow_filter *,
118 struct flowinfo_in *);
119 static u_long get_filt_handle(struct acc_classifier *, int);
120 static struct acc_filter *filth_to_filtp(struct acc_classifier *, u_long);
121 static u_int32_t filt2fibmask(struct flow_filter *);
123 static void ip4f_cache(struct ip *, struct flowinfo_in *);
124 static int ip4f_lookup(struct ip *, struct flowinfo_in *);
125 static int ip4f_init(void);
126 static struct ip4_frag *ip4f_alloc(void);
127 static void ip4f_free(struct ip4_frag *);
128 #endif /* ALTQ3_CLFIER_COMPAT */
131 * alternate queueing support routines
134 /* look up the queue state by the interface name and the queueing type. */
136 altq_lookup(name, type)
142 if ((ifp = ifunit(name)) != NULL) {
143 /* read if_snd unlocked */
144 if (type != ALTQT_NONE && ifp->if_snd.altq_type == type)
145 return (ifp->if_snd.altq_disc);
152 altq_attach(ifq, type, discipline, enqueue, dequeue, request, clfier, classify)
156 int (*enqueue)(struct ifaltq *, struct mbuf *, struct altq_pktattr *);
157 struct mbuf *(*dequeue)(struct ifaltq *, int);
158 int (*request)(struct ifaltq *, int, void *);
160 void *(*classify)(void *, struct mbuf *, int);
163 if (!ALTQ_IS_READY(ifq)) {
170 * pfaltq can override the existing discipline, but altq3 cannot.
171 * check these if clfier is not NULL (which implies altq3).
173 if (clfier != NULL) {
174 if (ALTQ_IS_ENABLED(ifq)) {
178 if (ALTQ_IS_ATTACHED(ifq)) {
184 ifq->altq_type = type;
185 ifq->altq_disc = discipline;
186 ifq->altq_enqueue = enqueue;
187 ifq->altq_dequeue = dequeue;
188 ifq->altq_request = request;
189 ifq->altq_clfier = clfier;
190 ifq->altq_classify = classify;
191 ifq->altq_flags &= (ALTQF_CANTCHANGE|ALTQF_ENABLED);
194 altq_module_incref(type);
207 if (!ALTQ_IS_READY(ifq)) {
211 if (ALTQ_IS_ENABLED(ifq)) {
215 if (!ALTQ_IS_ATTACHED(ifq)) {
221 altq_module_declref(ifq->altq_type);
225 ifq->altq_type = ALTQT_NONE;
226 ifq->altq_disc = NULL;
227 ifq->altq_enqueue = NULL;
228 ifq->altq_dequeue = NULL;
229 ifq->altq_request = NULL;
230 ifq->altq_clfier = NULL;
231 ifq->altq_classify = NULL;
232 ifq->altq_flags &= ALTQF_CANTCHANGE;
246 if (!ALTQ_IS_READY(ifq)) {
250 if (ALTQ_IS_ENABLED(ifq)) {
260 IFQ_PURGE_NOLOCK(ifq);
261 ASSERT(ifq->ifq_len == 0);
262 ifq->ifq_drv_maxlen = 0; /* disable bulk dequeue */
263 ifq->altq_flags |= ALTQF_ENABLED;
264 if (ifq->altq_clfier != NULL)
265 ifq->altq_flags |= ALTQF_CLASSIFY;
279 if (!ALTQ_IS_ENABLED(ifq)) {
289 IFQ_PURGE_NOLOCK(ifq);
290 ASSERT(ifq->ifq_len == 0);
291 ifq->altq_flags &= ~(ALTQF_ENABLED|ALTQF_CLASSIFY);
300 altq_assert(file, line, failedexpr)
301 const char *file, *failedexpr;
304 (void)printf("altq assertion \"%s\" failed: file \"%s\", line %d\n",
305 failedexpr, file, line);
306 panic("altq assertion");
312 * internal representation of token bucket parameters
313 * rate: byte_per_unittime << 32
314 * (((bits_per_sec) / 8) << 32) / machclk_freq
319 #define TBR_SCALE(x) ((int64_t)(x) << TBR_SHIFT)
320 #define TBR_UNSCALE(x) ((x) >> TBR_SHIFT)
327 struct tb_regulator *tbr;
332 IFQ_LOCK_ASSERT(ifq);
334 if (op == ALTDQ_REMOVE && tbr->tbr_lastop == ALTDQ_POLL) {
335 /* if this is a remove after poll, bypass tbr check */
337 /* update token only when it is negative */
338 if (tbr->tbr_token <= 0) {
339 now = read_machclk();
340 interval = now - tbr->tbr_last;
341 if (interval >= tbr->tbr_filluptime)
342 tbr->tbr_token = tbr->tbr_depth;
344 tbr->tbr_token += interval * tbr->tbr_rate;
345 if (tbr->tbr_token > tbr->tbr_depth)
346 tbr->tbr_token = tbr->tbr_depth;
350 /* if token is still negative, don't allow dequeue */
351 if (tbr->tbr_token <= 0)
355 if (ALTQ_IS_ENABLED(ifq))
356 m = (*ifq->altq_dequeue)(ifq, op);
358 if (op == ALTDQ_POLL)
364 if (m != NULL && op == ALTDQ_REMOVE)
365 tbr->tbr_token -= TBR_SCALE(m_pktlen(m));
366 tbr->tbr_lastop = op;
371 * set a token bucket regulator.
372 * if the specified rate is zero, the token bucket regulator is deleted.
375 tbr_set(ifq, profile)
377 struct tb_profile *profile;
379 struct tb_regulator *tbr, *otbr;
381 if (tbr_dequeue_ptr == NULL)
382 tbr_dequeue_ptr = tbr_dequeue;
384 if (machclk_freq == 0)
386 if (machclk_freq == 0) {
387 printf("tbr_set: no cpu clock available!\n");
392 if (profile->rate == 0) {
393 /* delete this tbr */
394 if ((tbr = ifq->altq_tbr) == NULL) {
398 ifq->altq_tbr = NULL;
404 tbr = malloc(sizeof(struct tb_regulator), M_DEVBUF, M_NOWAIT | M_ZERO);
410 tbr->tbr_rate = TBR_SCALE(profile->rate / 8) / machclk_freq;
411 tbr->tbr_depth = TBR_SCALE(profile->depth);
412 if (tbr->tbr_rate > 0)
413 tbr->tbr_filluptime = tbr->tbr_depth / tbr->tbr_rate;
415 tbr->tbr_filluptime = 0xffffffffffffffffLL;
416 tbr->tbr_token = tbr->tbr_depth;
417 tbr->tbr_last = read_machclk();
418 tbr->tbr_lastop = ALTDQ_REMOVE;
420 otbr = ifq->altq_tbr;
421 ifq->altq_tbr = tbr; /* set the new tbr */
424 free(otbr, M_DEVBUF);
426 if (tbr_timer == 0) {
427 CALLOUT_RESET(&tbr_callout, 1, tbr_timeout, (void *)0);
436 * tbr_timeout goes through the interface list, and kicks the drivers
446 VNET_ITERATOR_DECL(vnet_iter);
458 IFNET_RLOCK_NOSLEEP();
459 VNET_LIST_RLOCK_NOSLEEP();
460 VNET_FOREACH(vnet_iter) {
461 CURVNET_SET(vnet_iter);
463 for (ifp = TAILQ_FIRST(&V_ifnet); ifp;
464 ifp = TAILQ_NEXT(ifp, if_list)) {
465 /* read from if_snd unlocked */
466 if (!TBR_IS_ENABLED(&ifp->if_snd))
469 if (!IFQ_IS_EMPTY(&ifp->if_snd) &&
470 ifp->if_start != NULL)
471 (*ifp->if_start)(ifp);
476 VNET_LIST_RUNLOCK_NOSLEEP();
477 IFNET_RUNLOCK_NOSLEEP();
481 CALLOUT_RESET(&tbr_callout, 1, tbr_timeout, (void *)0);
483 tbr_timer = 0; /* don't need tbr_timer anymore */
487 * get token bucket regulator profile
490 tbr_get(ifq, profile)
492 struct tb_profile *profile;
494 struct tb_regulator *tbr;
497 if ((tbr = ifq->altq_tbr) == NULL) {
502 (u_int)TBR_UNSCALE(tbr->tbr_rate * 8 * machclk_freq);
503 profile->depth = (u_int)TBR_UNSCALE(tbr->tbr_depth);
510 * attach a discipline to the interface. if one already exists, it is
512 * Locking is done in the discipline specific attach functions. Basically
513 * they call back to altq_attach which takes care of the attach and locking.
516 altq_pfattach(struct pf_altq *a)
520 switch (a->scheduler) {
525 error = cbq_pfattach(a);
530 error = priq_pfattach(a);
535 error = hfsc_pfattach(a);
546 * detach a discipline from the interface.
547 * it is possible that the discipline was already overridden by another
551 altq_pfdetach(struct pf_altq *a)
556 if ((ifp = ifunit(a->ifname)) == NULL)
559 /* if this discipline is no longer referenced, just return */
560 /* read unlocked from if_snd */
561 if (a->altq_disc == NULL || a->altq_disc != ifp->if_snd.altq_disc)
569 /* read unlocked from if_snd, _disable and _detach take care */
570 if (ALTQ_IS_ENABLED(&ifp->if_snd))
571 error = altq_disable(&ifp->if_snd);
573 error = altq_detach(&ifp->if_snd);
580 * add a discipline or a queue
581 * Locking is done in the discipline specific functions with regards to
582 * malloc with WAITOK, also it is not yet clear which lock to use.
585 altq_add(struct pf_altq *a)
589 if (a->qname[0] != 0)
590 return (altq_add_queue(a));
592 if (machclk_freq == 0)
594 if (machclk_freq == 0)
595 panic("altq_add: no cpu clock");
597 switch (a->scheduler) {
600 error = cbq_add_altq(a);
605 error = priq_add_altq(a);
610 error = hfsc_add_altq(a);
621 * remove a discipline or a queue
622 * It is yet unclear what lock to use to protect this operation, the
623 * discipline specific functions will determine and grab it
626 altq_remove(struct pf_altq *a)
630 if (a->qname[0] != 0)
631 return (altq_remove_queue(a));
633 switch (a->scheduler) {
636 error = cbq_remove_altq(a);
641 error = priq_remove_altq(a);
646 error = hfsc_remove_altq(a);
657 * add a queue to the discipline
658 * It is yet unclear what lock to use to protect this operation, the
659 * discipline specific functions will determine and grab it
662 altq_add_queue(struct pf_altq *a)
666 switch (a->scheduler) {
669 error = cbq_add_queue(a);
674 error = priq_add_queue(a);
679 error = hfsc_add_queue(a);
690 * remove a queue from the discipline
691 * It is yet unclear what lock to use to protect this operation, the
692 * discipline specific functions will determine and grab it
695 altq_remove_queue(struct pf_altq *a)
699 switch (a->scheduler) {
702 error = cbq_remove_queue(a);
707 error = priq_remove_queue(a);
712 error = hfsc_remove_queue(a);
723 * get queue statistics
724 * Locking is done in the discipline specific functions with regards to
725 * copyout operations, also it is not yet clear which lock to use.
728 altq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes)
732 switch (a->scheduler) {
735 error = cbq_getqstats(a, ubuf, nbytes);
740 error = priq_getqstats(a, ubuf, nbytes);
745 error = hfsc_getqstats(a, ubuf, nbytes);
756 * read and write diffserv field in IPv4 or IPv6 header
759 read_dsfield(m, pktattr)
761 struct altq_pktattr *pktattr;
764 u_int8_t ds_field = 0;
766 if (pktattr == NULL ||
767 (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6))
768 return ((u_int8_t)0);
770 /* verify that pattr_hdr is within the mbuf data */
771 for (m0 = m; m0 != NULL; m0 = m0->m_next)
772 if ((pktattr->pattr_hdr >= m0->m_data) &&
773 (pktattr->pattr_hdr < m0->m_data + m0->m_len))
776 /* ick, pattr_hdr is stale */
777 pktattr->pattr_af = AF_UNSPEC;
779 printf("read_dsfield: can't locate header!\n");
781 return ((u_int8_t)0);
784 if (pktattr->pattr_af == AF_INET) {
785 struct ip *ip = (struct ip *)pktattr->pattr_hdr;
788 return ((u_int8_t)0); /* version mismatch! */
789 ds_field = ip->ip_tos;
792 else if (pktattr->pattr_af == AF_INET6) {
793 struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr;
796 flowlabel = ntohl(ip6->ip6_flow);
797 if ((flowlabel >> 28) != 6)
798 return ((u_int8_t)0); /* version mismatch! */
799 ds_field = (flowlabel >> 20) & 0xff;
806 write_dsfield(struct mbuf *m, struct altq_pktattr *pktattr, u_int8_t dsfield)
810 if (pktattr == NULL ||
811 (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6))
814 /* verify that pattr_hdr is within the mbuf data */
815 for (m0 = m; m0 != NULL; m0 = m0->m_next)
816 if ((pktattr->pattr_hdr >= m0->m_data) &&
817 (pktattr->pattr_hdr < m0->m_data + m0->m_len))
820 /* ick, pattr_hdr is stale */
821 pktattr->pattr_af = AF_UNSPEC;
823 printf("write_dsfield: can't locate header!\n");
828 if (pktattr->pattr_af == AF_INET) {
829 struct ip *ip = (struct ip *)pktattr->pattr_hdr;
834 return; /* version mismatch! */
836 dsfield |= old & 3; /* leave CU bits */
839 ip->ip_tos = dsfield;
841 * update checksum (from RFC1624)
842 * HC' = ~(~HC + ~m + m')
844 sum = ~ntohs(ip->ip_sum) & 0xffff;
845 sum += 0xff00 + (~old & 0xff) + dsfield;
846 sum = (sum >> 16) + (sum & 0xffff);
847 sum += (sum >> 16); /* add carry */
849 ip->ip_sum = htons(~sum & 0xffff);
852 else if (pktattr->pattr_af == AF_INET6) {
853 struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr;
856 flowlabel = ntohl(ip6->ip6_flow);
857 if ((flowlabel >> 28) != 6)
858 return; /* version mismatch! */
859 flowlabel = (flowlabel & 0xf03fffff) | (dsfield << 20);
860 ip6->ip6_flow = htonl(flowlabel);
868 * high resolution clock support taking advantage of a machine dependent
869 * high resolution time counter (e.g., timestamp counter of intel pentium).
871 * - 64-bit-long monotonically-increasing counter
872 * - frequency range is 100M-4GHz (CPU speed)
874 /* if pcc is not available or disabled, emulate 256MHz using microtime() */
875 #define MACHCLK_SHIFT 8
878 u_int32_t machclk_freq;
879 u_int32_t machclk_per_tick;
881 #if defined(__i386__) && defined(__NetBSD__)
882 extern u_int64_t cpu_tsc_freq;
885 #if (__FreeBSD_version >= 700035)
886 /* Update TSC freq with the value indicated by the caller. */
888 tsc_freq_changed(void *arg, const struct cf_level *level, int status)
890 /* If there was an error during the transition, don't do anything. */
894 #if (__FreeBSD_version >= 701102) && (defined(__amd64__) || defined(__i386__))
895 /* If TSC is P-state invariant, don't do anything. */
896 if (tsc_is_invariant)
900 /* Total setting for this level gives the new frequency in MHz. */
903 EVENTHANDLER_DEFINE(cpufreq_post_change, tsc_freq_changed, NULL,
904 EVENTHANDLER_PRI_LAST);
905 #endif /* __FreeBSD_version >= 700035 */
908 init_machclk_setup(void)
910 #if (__FreeBSD_version >= 600000)
911 callout_init(&tbr_callout, 0);
916 #if (!defined(__amd64__) && !defined(__i386__)) || defined(ALTQ_NOPCC)
919 #if defined(__FreeBSD__) && defined(SMP)
922 #if defined(__NetBSD__) && defined(MULTIPROCESSOR)
925 #if defined(__amd64__) || defined(__i386__)
926 /* check if TSC is available */
928 if ((cpu_feature & CPUID_TSC) == 0 ||
929 atomic_load_acq_64(&tsc_freq) == 0)
931 if ((cpu_feature & CPUID_TSC) == 0)
942 /* Call one-time initialization function. */
944 init_machclk_setup();
948 if (machclk_usepcc == 0) {
949 /* emulate 256MHz using microtime() */
950 machclk_freq = 1000000 << MACHCLK_SHIFT;
951 machclk_per_tick = machclk_freq / hz;
953 printf("altq: emulate %uHz cpu clock\n", machclk_freq);
959 * if the clock frequency (of Pentium TSC or Alpha PCC) is
960 * accessible, just use it.
962 #if defined(__amd64__) || defined(__i386__)
964 machclk_freq = atomic_load_acq_64(&tsc_freq);
965 #elif defined(__NetBSD__)
966 machclk_freq = (u_int32_t)cpu_tsc_freq;
967 #elif defined(__OpenBSD__) && (defined(I586_CPU) || defined(I686_CPU))
968 machclk_freq = pentium_mhz * 1000000;
973 * if we don't know the clock frequency, measure it.
975 if (machclk_freq == 0) {
977 struct timeval tv_start, tv_end;
978 u_int64_t start, end, diff;
981 microtime(&tv_start);
982 start = read_machclk();
983 timo = hz; /* 1 sec */
984 (void)tsleep(&wait, PWAIT | PCATCH, "init_machclk", timo);
986 end = read_machclk();
987 diff = (u_int64_t)(tv_end.tv_sec - tv_start.tv_sec) * 1000000
988 + tv_end.tv_usec - tv_start.tv_usec;
990 machclk_freq = (u_int)((end - start) * 1000000 / diff);
993 machclk_per_tick = machclk_freq / hz;
996 printf("altq: CPU clock: %uHz\n", machclk_freq);
1000 #if defined(__OpenBSD__) && defined(__i386__)
1001 static __inline u_int64_t
1005 __asm __volatile(".byte 0x0f, 0x31" : "=A" (rv));
1008 #endif /* __OpenBSD__ && __i386__ */
1015 if (machclk_usepcc) {
1016 #if defined(__amd64__) || defined(__i386__)
1019 panic("read_machclk");
1025 val = (((u_int64_t)(tv.tv_sec - boottime.tv_sec) * 1000000
1026 + tv.tv_usec) << MACHCLK_SHIFT);
1031 #ifdef ALTQ3_CLFIER_COMPAT
1034 #define IPPROTO_ESP 50 /* encapsulating security payload */
1037 #define IPPROTO_AH 51 /* authentication header */
1041 * extract flow information from a given packet.
1042 * filt_mask shows flowinfo fields required.
1043 * we assume the ip header is in one mbuf, and addresses and ports are
1044 * in network byte order.
1047 altq_extractflow(m, af, flow, filt_bmask)
1050 struct flowinfo *flow;
1051 u_int32_t filt_bmask;
1056 struct flowinfo_in *fin;
1059 ip = mtod(m, struct ip *);
1064 fin = (struct flowinfo_in *)flow;
1065 fin->fi_len = sizeof(struct flowinfo_in);
1066 fin->fi_family = AF_INET;
1068 fin->fi_proto = ip->ip_p;
1069 fin->fi_tos = ip->ip_tos;
1071 fin->fi_src.s_addr = ip->ip_src.s_addr;
1072 fin->fi_dst.s_addr = ip->ip_dst.s_addr;
1074 if (filt_bmask & FIMB4_PORTS)
1075 /* if port info is required, extract port numbers */
1076 extract_ports4(m, ip, fin);
1087 struct flowinfo_in6 *fin6;
1088 struct ip6_hdr *ip6;
1090 ip6 = mtod(m, struct ip6_hdr *);
1091 /* should we check the ip version? */
1093 fin6 = (struct flowinfo_in6 *)flow;
1094 fin6->fi6_len = sizeof(struct flowinfo_in6);
1095 fin6->fi6_family = AF_INET6;
1097 fin6->fi6_proto = ip6->ip6_nxt;
1098 fin6->fi6_tclass = (ntohl(ip6->ip6_flow) >> 20) & 0xff;
1100 fin6->fi6_flowlabel = ip6->ip6_flow & htonl(0x000fffff);
1101 fin6->fi6_src = ip6->ip6_src;
1102 fin6->fi6_dst = ip6->ip6_dst;
1104 if ((filt_bmask & FIMB6_PORTS) ||
1105 ((filt_bmask & FIMB6_PROTO)
1106 && ip6->ip6_nxt > IPPROTO_IPV6))
1108 * if port info is required, or proto is required
1109 * but there are option headers, extract port
1110 * and protocol numbers.
1112 extract_ports6(m, ip6, fin6);
1114 fin6->fi6_sport = 0;
1115 fin6->fi6_dport = 0;
1127 flow->fi_len = sizeof(struct flowinfo);
1128 flow->fi_family = AF_UNSPEC;
1133 * helper routine to extract port numbers
1135 /* structure for ipsec and ipv6 option header template */
1137 u_int8_t opt6_nxt; /* next header */
1138 u_int8_t opt6_hlen; /* header extension length */
1140 u_int32_t ah_spi; /* security parameter index
1141 for authentication header */
1145 * extract port numbers from a ipv4 packet.
1148 extract_ports4(m, ip, fin)
1151 struct flowinfo_in *fin;
1162 ip_off = ntohs(ip->ip_off);
1163 /* if it is a fragment, try cached fragment info */
1164 if (ip_off & IP_OFFMASK) {
1165 ip4f_lookup(ip, fin);
1169 /* locate the mbuf containing the protocol header */
1170 for (m0 = m; m0 != NULL; m0 = m0->m_next)
1171 if (((caddr_t)ip >= m0->m_data) &&
1172 ((caddr_t)ip < m0->m_data + m0->m_len))
1176 printf("extract_ports4: can't locate header! ip=%p\n", ip);
1180 off = ((caddr_t)ip - m0->m_data) + (ip->ip_hl << 2);
1186 while (off >= m0->m_len) {
1190 return (0); /* bogus ip_hl! */
1192 if (m0->m_len < off + 4)
1200 udp = (struct udphdr *)(mtod(m0, caddr_t) + off);
1201 fin->fi_sport = udp->uh_sport;
1202 fin->fi_dport = udp->uh_dport;
1203 fin->fi_proto = proto;
1209 if (fin->fi_gpi == 0){
1212 gpi = (u_int32_t *)(mtod(m0, caddr_t) + off);
1215 fin->fi_proto = proto;
1219 /* get next header and header length */
1222 opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1223 proto = opt6->opt6_nxt;
1224 off += 8 + (opt6->opt6_hlen * 4);
1225 if (fin->fi_gpi == 0 && m0->m_len >= off + 8)
1226 fin->fi_gpi = opt6->ah_spi;
1228 /* goto the next header */
1230 #endif /* ALTQ_IPSEC */
1233 fin->fi_proto = proto;
1237 /* if this is a first fragment, cache it. */
1239 ip4f_cache(ip, fin);
1246 extract_ports6(m, ip6, fin6)
1248 struct ip6_hdr *ip6;
1249 struct flowinfo_in6 *fin6;
1256 fin6->fi6_sport = 0;
1257 fin6->fi6_dport = 0;
1259 /* locate the mbuf containing the protocol header */
1260 for (m0 = m; m0 != NULL; m0 = m0->m_next)
1261 if (((caddr_t)ip6 >= m0->m_data) &&
1262 ((caddr_t)ip6 < m0->m_data + m0->m_len))
1266 printf("extract_ports6: can't locate header! ip6=%p\n", ip6);
1270 off = ((caddr_t)ip6 - m0->m_data) + sizeof(struct ip6_hdr);
1272 proto = ip6->ip6_nxt;
1274 while (off >= m0->m_len) {
1280 if (m0->m_len < off + 4)
1288 udp = (struct udphdr *)(mtod(m0, caddr_t) + off);
1289 fin6->fi6_sport = udp->uh_sport;
1290 fin6->fi6_dport = udp->uh_dport;
1291 fin6->fi6_proto = proto;
1296 if (fin6->fi6_gpi == 0) {
1299 gpi = (u_int32_t *)(mtod(m0, caddr_t) + off);
1300 fin6->fi6_gpi = *gpi;
1302 fin6->fi6_proto = proto;
1306 /* get next header and header length */
1309 opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1310 if (fin6->fi6_gpi == 0 && m0->m_len >= off + 8)
1311 fin6->fi6_gpi = opt6->ah_spi;
1312 proto = opt6->opt6_nxt;
1313 off += 8 + (opt6->opt6_hlen * 4);
1314 /* goto the next header */
1318 case IPPROTO_HOPOPTS:
1319 case IPPROTO_ROUTING:
1320 case IPPROTO_DSTOPTS: {
1321 /* get next header and header length */
1324 opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1325 proto = opt6->opt6_nxt;
1326 off += (opt6->opt6_hlen + 1) * 8;
1327 /* goto the next header */
1331 case IPPROTO_FRAGMENT:
1332 /* ipv6 fragmentations are not supported yet */
1334 fin6->fi6_proto = proto;
1343 * altq common classifier
1346 acc_add_filter(classifier, filter, class, phandle)
1347 struct acc_classifier *classifier;
1348 struct flow_filter *filter;
1352 struct acc_filter *afp, *prev, *tmp;
1356 if (filter->ff_flow.fi_family != AF_INET &&
1357 filter->ff_flow.fi_family != AF_INET6)
1360 if (filter->ff_flow.fi_family != AF_INET)
1364 afp = malloc(sizeof(struct acc_filter),
1365 M_DEVBUF, M_WAITOK);
1368 bzero(afp, sizeof(struct acc_filter));
1370 afp->f_filter = *filter;
1371 afp->f_class = class;
1373 i = ACC_WILDCARD_INDEX;
1374 if (filter->ff_flow.fi_family == AF_INET) {
1375 struct flow_filter *filter4 = &afp->f_filter;
1378 * if address is 0, it's a wildcard. if address mask
1379 * isn't set, use full mask.
1381 if (filter4->ff_flow.fi_dst.s_addr == 0)
1382 filter4->ff_mask.mask_dst.s_addr = 0;
1383 else if (filter4->ff_mask.mask_dst.s_addr == 0)
1384 filter4->ff_mask.mask_dst.s_addr = 0xffffffff;
1385 if (filter4->ff_flow.fi_src.s_addr == 0)
1386 filter4->ff_mask.mask_src.s_addr = 0;
1387 else if (filter4->ff_mask.mask_src.s_addr == 0)
1388 filter4->ff_mask.mask_src.s_addr = 0xffffffff;
1390 /* clear extra bits in addresses */
1391 filter4->ff_flow.fi_dst.s_addr &=
1392 filter4->ff_mask.mask_dst.s_addr;
1393 filter4->ff_flow.fi_src.s_addr &=
1394 filter4->ff_mask.mask_src.s_addr;
1397 * if dst address is a wildcard, use hash-entry
1398 * ACC_WILDCARD_INDEX.
1400 if (filter4->ff_mask.mask_dst.s_addr != 0xffffffff)
1401 i = ACC_WILDCARD_INDEX;
1403 i = ACC_GET_HASH_INDEX(filter4->ff_flow.fi_dst.s_addr);
1406 else if (filter->ff_flow.fi_family == AF_INET6) {
1407 struct flow_filter6 *filter6 =
1408 (struct flow_filter6 *)&afp->f_filter;
1409 #ifndef IN6MASK0 /* taken from kame ipv6 */
1410 #define IN6MASK0 {{{ 0, 0, 0, 0 }}}
1411 #define IN6MASK128 {{{ 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff }}}
1412 const struct in6_addr in6mask0 = IN6MASK0;
1413 const struct in6_addr in6mask128 = IN6MASK128;
1416 if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_flow6.fi6_dst))
1417 filter6->ff_mask6.mask6_dst = in6mask0;
1418 else if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_mask6.mask6_dst))
1419 filter6->ff_mask6.mask6_dst = in6mask128;
1420 if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_flow6.fi6_src))
1421 filter6->ff_mask6.mask6_src = in6mask0;
1422 else if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_mask6.mask6_src))
1423 filter6->ff_mask6.mask6_src = in6mask128;
1425 /* clear extra bits in addresses */
1426 for (i = 0; i < 16; i++)
1427 filter6->ff_flow6.fi6_dst.s6_addr[i] &=
1428 filter6->ff_mask6.mask6_dst.s6_addr[i];
1429 for (i = 0; i < 16; i++)
1430 filter6->ff_flow6.fi6_src.s6_addr[i] &=
1431 filter6->ff_mask6.mask6_src.s6_addr[i];
1433 if (filter6->ff_flow6.fi6_flowlabel == 0)
1434 i = ACC_WILDCARD_INDEX;
1436 i = ACC_GET_HASH_INDEX(filter6->ff_flow6.fi6_flowlabel);
1440 afp->f_handle = get_filt_handle(classifier, i);
1442 /* update filter bitmask */
1443 afp->f_fbmask = filt2fibmask(filter);
1444 classifier->acc_fbmask |= afp->f_fbmask;
1447 * add this filter to the filter list.
1448 * filters are ordered from the highest rule number.
1456 LIST_FOREACH(tmp, &classifier->acc_filters[i], f_chain) {
1457 if (tmp->f_filter.ff_ruleno > afp->f_filter.ff_ruleno)
1463 LIST_INSERT_HEAD(&classifier->acc_filters[i], afp, f_chain);
1465 LIST_INSERT_AFTER(prev, afp, f_chain);
1468 *phandle = afp->f_handle;
1473 acc_delete_filter(classifier, handle)
1474 struct acc_classifier *classifier;
1477 struct acc_filter *afp;
1480 if ((afp = filth_to_filtp(classifier, handle)) == NULL)
1488 LIST_REMOVE(afp, f_chain);
1491 free(afp, M_DEVBUF);
1493 /* todo: update filt_bmask */
1499 * delete filters referencing to the specified class.
1500 * if the all flag is not 0, delete all the filters.
1503 acc_discard_filters(classifier, class, all)
1504 struct acc_classifier *classifier;
1508 struct acc_filter *afp;
1516 for (i = 0; i < ACC_FILTER_TABLESIZE; i++) {
1518 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1519 if (all || afp->f_class == class) {
1520 LIST_REMOVE(afp, f_chain);
1521 free(afp, M_DEVBUF);
1522 /* start again from the head */
1525 } while (afp != NULL);
1530 classifier->acc_fbmask = 0;
1536 acc_classify(clfier, m, af)
1541 struct acc_classifier *classifier;
1542 struct flowinfo flow;
1543 struct acc_filter *afp;
1546 classifier = (struct acc_classifier *)clfier;
1547 altq_extractflow(m, af, &flow, classifier->acc_fbmask);
1549 if (flow.fi_family == AF_INET) {
1550 struct flowinfo_in *fp = (struct flowinfo_in *)&flow;
1552 if ((classifier->acc_fbmask & FIMB4_ALL) == FIMB4_TOS) {
1553 /* only tos is used */
1555 &classifier->acc_filters[ACC_WILDCARD_INDEX],
1557 if (apply_tosfilter4(afp->f_fbmask,
1558 &afp->f_filter, fp))
1559 /* filter matched */
1560 return (afp->f_class);
1561 } else if ((classifier->acc_fbmask &
1562 (~(FIMB4_PROTO|FIMB4_SPORT|FIMB4_DPORT) & FIMB4_ALL))
1564 /* only proto and ports are used */
1566 &classifier->acc_filters[ACC_WILDCARD_INDEX],
1568 if (apply_ppfilter4(afp->f_fbmask,
1569 &afp->f_filter, fp))
1570 /* filter matched */
1571 return (afp->f_class);
1573 /* get the filter hash entry from its dest address */
1574 i = ACC_GET_HASH_INDEX(fp->fi_dst.s_addr);
1577 * go through this loop twice. first for dst
1578 * hash, second for wildcards.
1580 LIST_FOREACH(afp, &classifier->acc_filters[i],
1582 if (apply_filter4(afp->f_fbmask,
1583 &afp->f_filter, fp))
1584 /* filter matched */
1585 return (afp->f_class);
1588 * check again for filters with a dst addr
1590 * (daddr == 0 || dmask != 0xffffffff).
1592 if (i != ACC_WILDCARD_INDEX)
1593 i = ACC_WILDCARD_INDEX;
1600 else if (flow.fi_family == AF_INET6) {
1601 struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)&flow;
1603 /* get the filter hash entry from its flow ID */
1604 if (fp6->fi6_flowlabel != 0)
1605 i = ACC_GET_HASH_INDEX(fp6->fi6_flowlabel);
1607 /* flowlable can be zero */
1608 i = ACC_WILDCARD_INDEX;
1610 /* go through this loop twice. first for flow hash, second
1613 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1614 if (apply_filter6(afp->f_fbmask,
1615 (struct flow_filter6 *)&afp->f_filter,
1617 /* filter matched */
1618 return (afp->f_class);
1621 * check again for filters with a wildcard.
1623 if (i != ACC_WILDCARD_INDEX)
1624 i = ACC_WILDCARD_INDEX;
1631 /* no filter matched */
1636 apply_filter4(fbmask, filt, pkt)
1638 struct flow_filter *filt;
1639 struct flowinfo_in *pkt;
1641 if (filt->ff_flow.fi_family != AF_INET)
1643 if ((fbmask & FIMB4_SPORT) && filt->ff_flow.fi_sport != pkt->fi_sport)
1645 if ((fbmask & FIMB4_DPORT) && filt->ff_flow.fi_dport != pkt->fi_dport)
1647 if ((fbmask & FIMB4_DADDR) &&
1648 filt->ff_flow.fi_dst.s_addr !=
1649 (pkt->fi_dst.s_addr & filt->ff_mask.mask_dst.s_addr))
1651 if ((fbmask & FIMB4_SADDR) &&
1652 filt->ff_flow.fi_src.s_addr !=
1653 (pkt->fi_src.s_addr & filt->ff_mask.mask_src.s_addr))
1655 if ((fbmask & FIMB4_PROTO) && filt->ff_flow.fi_proto != pkt->fi_proto)
1657 if ((fbmask & FIMB4_TOS) && filt->ff_flow.fi_tos !=
1658 (pkt->fi_tos & filt->ff_mask.mask_tos))
1660 if ((fbmask & FIMB4_GPI) && filt->ff_flow.fi_gpi != (pkt->fi_gpi))
1667 * filter matching function optimized for a common case that checks
1668 * only protocol and port numbers
1671 apply_ppfilter4(fbmask, filt, pkt)
1673 struct flow_filter *filt;
1674 struct flowinfo_in *pkt;
1676 if (filt->ff_flow.fi_family != AF_INET)
1678 if ((fbmask & FIMB4_SPORT) && filt->ff_flow.fi_sport != pkt->fi_sport)
1680 if ((fbmask & FIMB4_DPORT) && filt->ff_flow.fi_dport != pkt->fi_dport)
1682 if ((fbmask & FIMB4_PROTO) && filt->ff_flow.fi_proto != pkt->fi_proto)
1689 * filter matching function only for tos field.
1692 apply_tosfilter4(fbmask, filt, pkt)
1694 struct flow_filter *filt;
1695 struct flowinfo_in *pkt;
1697 if (filt->ff_flow.fi_family != AF_INET)
1699 if ((fbmask & FIMB4_TOS) && filt->ff_flow.fi_tos !=
1700 (pkt->fi_tos & filt->ff_mask.mask_tos))
1708 apply_filter6(fbmask, filt, pkt)
1710 struct flow_filter6 *filt;
1711 struct flowinfo_in6 *pkt;
1715 if (filt->ff_flow6.fi6_family != AF_INET6)
1717 if ((fbmask & FIMB6_FLABEL) &&
1718 filt->ff_flow6.fi6_flowlabel != pkt->fi6_flowlabel)
1720 if ((fbmask & FIMB6_PROTO) &&
1721 filt->ff_flow6.fi6_proto != pkt->fi6_proto)
1723 if ((fbmask & FIMB6_SPORT) &&
1724 filt->ff_flow6.fi6_sport != pkt->fi6_sport)
1726 if ((fbmask & FIMB6_DPORT) &&
1727 filt->ff_flow6.fi6_dport != pkt->fi6_dport)
1729 if (fbmask & FIMB6_SADDR) {
1730 for (i = 0; i < 4; i++)
1731 if (filt->ff_flow6.fi6_src.s6_addr32[i] !=
1732 (pkt->fi6_src.s6_addr32[i] &
1733 filt->ff_mask6.mask6_src.s6_addr32[i]))
1736 if (fbmask & FIMB6_DADDR) {
1737 for (i = 0; i < 4; i++)
1738 if (filt->ff_flow6.fi6_dst.s6_addr32[i] !=
1739 (pkt->fi6_dst.s6_addr32[i] &
1740 filt->ff_mask6.mask6_dst.s6_addr32[i]))
1743 if ((fbmask & FIMB6_TCLASS) &&
1744 filt->ff_flow6.fi6_tclass !=
1745 (pkt->fi6_tclass & filt->ff_mask6.mask6_tclass))
1747 if ((fbmask & FIMB6_GPI) &&
1748 filt->ff_flow6.fi6_gpi != pkt->fi6_gpi)
1757 * bit 20-28: index to the filter hash table
1758 * bit 0-19: unique id in the hash bucket.
1761 get_filt_handle(classifier, i)
1762 struct acc_classifier *classifier;
1765 static u_long handle_number = 1;
1767 struct acc_filter *afp;
1770 handle = handle_number++ & 0x000fffff;
1772 if (LIST_EMPTY(&classifier->acc_filters[i]))
1775 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1776 if ((afp->f_handle & 0x000fffff) == handle)
1780 /* this handle is already used, try again */
1783 return ((i << 20) | handle);
1786 /* convert filter handle to filter pointer */
1787 static struct acc_filter *
1788 filth_to_filtp(classifier, handle)
1789 struct acc_classifier *classifier;
1792 struct acc_filter *afp;
1795 i = ACC_GET_HINDEX(handle);
1797 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1798 if (afp->f_handle == handle)
1804 /* create flowinfo bitmask */
1807 struct flow_filter *filt;
1811 struct flow_filter6 *filt6;
1814 switch (filt->ff_flow.fi_family) {
1816 if (filt->ff_flow.fi_proto != 0)
1817 mask |= FIMB4_PROTO;
1818 if (filt->ff_flow.fi_tos != 0)
1820 if (filt->ff_flow.fi_dst.s_addr != 0)
1821 mask |= FIMB4_DADDR;
1822 if (filt->ff_flow.fi_src.s_addr != 0)
1823 mask |= FIMB4_SADDR;
1824 if (filt->ff_flow.fi_sport != 0)
1825 mask |= FIMB4_SPORT;
1826 if (filt->ff_flow.fi_dport != 0)
1827 mask |= FIMB4_DPORT;
1828 if (filt->ff_flow.fi_gpi != 0)
1833 filt6 = (struct flow_filter6 *)filt;
1835 if (filt6->ff_flow6.fi6_proto != 0)
1836 mask |= FIMB6_PROTO;
1837 if (filt6->ff_flow6.fi6_tclass != 0)
1838 mask |= FIMB6_TCLASS;
1839 if (!IN6_IS_ADDR_UNSPECIFIED(&filt6->ff_flow6.fi6_dst))
1840 mask |= FIMB6_DADDR;
1841 if (!IN6_IS_ADDR_UNSPECIFIED(&filt6->ff_flow6.fi6_src))
1842 mask |= FIMB6_SADDR;
1843 if (filt6->ff_flow6.fi6_sport != 0)
1844 mask |= FIMB6_SPORT;
1845 if (filt6->ff_flow6.fi6_dport != 0)
1846 mask |= FIMB6_DPORT;
1847 if (filt6->ff_flow6.fi6_gpi != 0)
1849 if (filt6->ff_flow6.fi6_flowlabel != 0)
1850 mask |= FIMB6_FLABEL;
1859 * helper functions to handle IPv4 fragments.
1860 * currently only in-sequence fragments are handled.
1861 * - fragment info is cached in a LRU list.
1862 * - when a first fragment is found, cache its flow info.
1863 * - when a non-first fragment is found, lookup the cache.
1867 TAILQ_ENTRY(ip4_frag) ip4f_chain;
1870 struct flowinfo_in ip4f_info;
1873 static TAILQ_HEAD(ip4f_list, ip4_frag) ip4f_list; /* IPv4 fragment cache */
1875 #define IP4F_TABSIZE 16 /* IPv4 fragment cache size */
1881 struct flowinfo_in *fin;
1883 struct ip4_frag *fp;
1885 if (TAILQ_EMPTY(&ip4f_list)) {
1886 /* first time call, allocate fragment cache entries. */
1887 if (ip4f_init() < 0)
1888 /* allocation failed! */
1893 fp->ip4f_id = ip->ip_id;
1894 fp->ip4f_info.fi_proto = ip->ip_p;
1895 fp->ip4f_info.fi_src.s_addr = ip->ip_src.s_addr;
1896 fp->ip4f_info.fi_dst.s_addr = ip->ip_dst.s_addr;
1898 /* save port numbers */
1899 fp->ip4f_info.fi_sport = fin->fi_sport;
1900 fp->ip4f_info.fi_dport = fin->fi_dport;
1901 fp->ip4f_info.fi_gpi = fin->fi_gpi;
1905 ip4f_lookup(ip, fin)
1907 struct flowinfo_in *fin;
1909 struct ip4_frag *fp;
1911 for (fp = TAILQ_FIRST(&ip4f_list); fp != NULL && fp->ip4f_valid;
1912 fp = TAILQ_NEXT(fp, ip4f_chain))
1913 if (ip->ip_id == fp->ip4f_id &&
1914 ip->ip_src.s_addr == fp->ip4f_info.fi_src.s_addr &&
1915 ip->ip_dst.s_addr == fp->ip4f_info.fi_dst.s_addr &&
1916 ip->ip_p == fp->ip4f_info.fi_proto) {
1918 /* found the matching entry */
1919 fin->fi_sport = fp->ip4f_info.fi_sport;
1920 fin->fi_dport = fp->ip4f_info.fi_dport;
1921 fin->fi_gpi = fp->ip4f_info.fi_gpi;
1923 if ((ntohs(ip->ip_off) & IP_MF) == 0)
1924 /* this is the last fragment,
1925 release the entry. */
1931 /* no matching entry found */
1938 struct ip4_frag *fp;
1941 TAILQ_INIT(&ip4f_list);
1942 for (i=0; i<IP4F_TABSIZE; i++) {
1943 fp = malloc(sizeof(struct ip4_frag),
1944 M_DEVBUF, M_NOWAIT);
1946 printf("ip4f_init: can't alloc %dth entry!\n", i);
1952 TAILQ_INSERT_TAIL(&ip4f_list, fp, ip4f_chain);
1957 static struct ip4_frag *
1960 struct ip4_frag *fp;
1962 /* reclaim an entry at the tail, put it at the head */
1963 fp = TAILQ_LAST(&ip4f_list, ip4f_list);
1964 TAILQ_REMOVE(&ip4f_list, fp, ip4f_chain);
1966 TAILQ_INSERT_HEAD(&ip4f_list, fp, ip4f_chain);
1972 struct ip4_frag *fp;
1974 TAILQ_REMOVE(&ip4f_list, fp, ip4f_chain);
1976 TAILQ_INSERT_TAIL(&ip4f_list, fp, ip4f_chain);
1979 #endif /* ALTQ3_CLFIER_COMPAT */