2 * Copyright (C) 1997-2003
3 * Sony Computer Science Laboratories Inc. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
26 * $KAME: altq_subr.c,v 1.21 2003/11/06 06:32:53 kjc Exp $
32 #include "opt_inet6.h"
34 #include <sys/param.h>
35 #include <sys/malloc.h>
37 #include <sys/systm.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>
48 #include <net/if_var.h>
49 #include <net/if_dl.h>
50 #include <net/if_types.h>
53 #include <netinet/in.h>
54 #include <netinet/in_systm.h>
55 #include <netinet/ip.h>
57 #include <netinet/ip6.h>
59 #include <netinet/tcp.h>
60 #include <netinet/udp.h>
62 #include <netpfil/pf/pf.h>
63 #include <netpfil/pf/pf_altq.h>
64 #include <net/altq/altq.h>
66 /* machine dependent clock related includes */
69 #include <sys/eventhandler.h>
70 #include <machine/clock.h>
71 #if defined(__amd64__) || defined(__i386__)
72 #include <machine/cpufunc.h> /* for pentium tsc */
73 #include <machine/specialreg.h> /* for CPUID_TSC */
74 #include <machine/md_var.h> /* for cpu_feature */
75 #endif /* __amd64 || __i386__ */
78 * internal function prototypes
80 static void tbr_timeout(void *);
81 int (*altq_input)(struct mbuf *, int) = NULL;
82 static struct mbuf *tbr_dequeue(struct ifaltq *, int);
83 static int tbr_timer = 0; /* token bucket regulator timer */
84 #if !defined(__FreeBSD__) || (__FreeBSD_version < 600000)
85 static struct callout tbr_callout = CALLOUT_INITIALIZER;
87 static struct callout tbr_callout;
90 #ifdef ALTQ3_CLFIER_COMPAT
91 static int extract_ports4(struct mbuf *, struct ip *, struct flowinfo_in *);
93 static int extract_ports6(struct mbuf *, struct ip6_hdr *,
94 struct flowinfo_in6 *);
96 static int apply_filter4(u_int32_t, struct flow_filter *,
97 struct flowinfo_in *);
98 static int apply_ppfilter4(u_int32_t, struct flow_filter *,
99 struct flowinfo_in *);
101 static int apply_filter6(u_int32_t, struct flow_filter6 *,
102 struct flowinfo_in6 *);
104 static int apply_tosfilter4(u_int32_t, struct flow_filter *,
105 struct flowinfo_in *);
106 static u_long get_filt_handle(struct acc_classifier *, int);
107 static struct acc_filter *filth_to_filtp(struct acc_classifier *, u_long);
108 static u_int32_t filt2fibmask(struct flow_filter *);
110 static void ip4f_cache(struct ip *, struct flowinfo_in *);
111 static int ip4f_lookup(struct ip *, struct flowinfo_in *);
112 static int ip4f_init(void);
113 static struct ip4_frag *ip4f_alloc(void);
114 static void ip4f_free(struct ip4_frag *);
115 #endif /* ALTQ3_CLFIER_COMPAT */
118 * alternate queueing support routines
121 /* look up the queue state by the interface name and the queueing type. */
123 altq_lookup(name, type)
129 if ((ifp = ifunit(name)) != NULL) {
130 /* read if_snd unlocked */
131 if (type != ALTQT_NONE && ifp->if_snd.altq_type == type)
132 return (ifp->if_snd.altq_disc);
139 altq_attach(ifq, type, discipline, enqueue, dequeue, request, clfier, classify)
143 int (*enqueue)(struct ifaltq *, struct mbuf *, struct altq_pktattr *);
144 struct mbuf *(*dequeue)(struct ifaltq *, int);
145 int (*request)(struct ifaltq *, int, void *);
147 void *(*classify)(void *, struct mbuf *, int);
150 if (!ALTQ_IS_READY(ifq)) {
155 ifq->altq_type = type;
156 ifq->altq_disc = discipline;
157 ifq->altq_enqueue = enqueue;
158 ifq->altq_dequeue = dequeue;
159 ifq->altq_request = request;
160 ifq->altq_clfier = clfier;
161 ifq->altq_classify = classify;
162 ifq->altq_flags &= (ALTQF_CANTCHANGE|ALTQF_ENABLED);
173 if (!ALTQ_IS_READY(ifq)) {
177 if (ALTQ_IS_ENABLED(ifq)) {
181 if (!ALTQ_IS_ATTACHED(ifq)) {
186 ifq->altq_type = ALTQT_NONE;
187 ifq->altq_disc = NULL;
188 ifq->altq_enqueue = NULL;
189 ifq->altq_dequeue = NULL;
190 ifq->altq_request = NULL;
191 ifq->altq_clfier = NULL;
192 ifq->altq_classify = NULL;
193 ifq->altq_flags &= ALTQF_CANTCHANGE;
207 if (!ALTQ_IS_READY(ifq)) {
211 if (ALTQ_IS_ENABLED(ifq)) {
217 IFQ_PURGE_NOLOCK(ifq);
218 ASSERT(ifq->ifq_len == 0);
219 ifq->ifq_drv_maxlen = 0; /* disable bulk dequeue */
220 ifq->altq_flags |= ALTQF_ENABLED;
221 if (ifq->altq_clfier != NULL)
222 ifq->altq_flags |= ALTQF_CLASSIFY;
236 if (!ALTQ_IS_ENABLED(ifq)) {
242 IFQ_PURGE_NOLOCK(ifq);
243 ASSERT(ifq->ifq_len == 0);
244 ifq->altq_flags &= ~(ALTQF_ENABLED|ALTQF_CLASSIFY);
253 altq_assert(file, line, failedexpr)
254 const char *file, *failedexpr;
257 (void)printf("altq assertion \"%s\" failed: file \"%s\", line %d\n",
258 failedexpr, file, line);
259 panic("altq assertion");
265 * internal representation of token bucket parameters
266 * rate: (byte_per_unittime << TBR_SHIFT) / machclk_freq
267 * (((bits_per_sec) / 8) << TBR_SHIFT) / machclk_freq
268 * depth: byte << TBR_SHIFT
272 #define TBR_SCALE(x) ((int64_t)(x) << TBR_SHIFT)
273 #define TBR_UNSCALE(x) ((x) >> TBR_SHIFT)
280 struct tb_regulator *tbr;
285 IFQ_LOCK_ASSERT(ifq);
287 if (op == ALTDQ_REMOVE && tbr->tbr_lastop == ALTDQ_POLL) {
288 /* if this is a remove after poll, bypass tbr check */
290 /* update token only when it is negative */
291 if (tbr->tbr_token <= 0) {
292 now = read_machclk();
293 interval = now - tbr->tbr_last;
294 if (interval >= tbr->tbr_filluptime)
295 tbr->tbr_token = tbr->tbr_depth;
297 tbr->tbr_token += interval * tbr->tbr_rate;
298 if (tbr->tbr_token > tbr->tbr_depth)
299 tbr->tbr_token = tbr->tbr_depth;
303 /* if token is still negative, don't allow dequeue */
304 if (tbr->tbr_token <= 0)
308 if (ALTQ_IS_ENABLED(ifq))
309 m = (*ifq->altq_dequeue)(ifq, op);
311 if (op == ALTDQ_POLL)
317 if (m != NULL && op == ALTDQ_REMOVE)
318 tbr->tbr_token -= TBR_SCALE(m_pktlen(m));
319 tbr->tbr_lastop = op;
324 * set a token bucket regulator.
325 * if the specified rate is zero, the token bucket regulator is deleted.
328 tbr_set(ifq, profile)
330 struct tb_profile *profile;
332 struct tb_regulator *tbr, *otbr;
334 if (tbr_dequeue_ptr == NULL)
335 tbr_dequeue_ptr = tbr_dequeue;
337 if (machclk_freq == 0)
339 if (machclk_freq == 0) {
340 printf("tbr_set: no cpu clock available!\n");
345 if (profile->rate == 0) {
346 /* delete this tbr */
347 if ((tbr = ifq->altq_tbr) == NULL) {
351 ifq->altq_tbr = NULL;
357 tbr = malloc(sizeof(struct tb_regulator), M_DEVBUF, M_NOWAIT | M_ZERO);
363 tbr->tbr_rate = TBR_SCALE(profile->rate / 8) / machclk_freq;
364 tbr->tbr_depth = TBR_SCALE(profile->depth);
365 if (tbr->tbr_rate > 0)
366 tbr->tbr_filluptime = tbr->tbr_depth / tbr->tbr_rate;
368 tbr->tbr_filluptime = LLONG_MAX;
370 * The longest time between tbr_dequeue() calls will be about 1
371 * system tick, as the callout that drives it is scheduled once per
372 * tick. The refill-time detection logic in tbr_dequeue() can only
373 * properly detect the passage of up to LLONG_MAX machclk ticks.
374 * Therefore, in order for this logic to function properly in the
375 * extreme case, the maximum value of tbr_filluptime should be
376 * LLONG_MAX less one system tick's worth of machclk ticks less
377 * some additional slop factor (here one more system tick's worth
380 if (tbr->tbr_filluptime > (LLONG_MAX - 2 * machclk_per_tick))
381 tbr->tbr_filluptime = LLONG_MAX - 2 * machclk_per_tick;
382 tbr->tbr_token = tbr->tbr_depth;
383 tbr->tbr_last = read_machclk();
384 tbr->tbr_lastop = ALTDQ_REMOVE;
386 otbr = ifq->altq_tbr;
387 ifq->altq_tbr = tbr; /* set the new tbr */
390 free(otbr, M_DEVBUF);
392 if (tbr_timer == 0) {
393 CALLOUT_RESET(&tbr_callout, 1, tbr_timeout, (void *)0);
402 * tbr_timeout goes through the interface list, and kicks the drivers
411 VNET_ITERATOR_DECL(vnet_iter);
413 struct epoch_tracker et;
418 VNET_LIST_RLOCK_NOSLEEP();
419 VNET_FOREACH(vnet_iter) {
420 CURVNET_SET(vnet_iter);
421 for (ifp = CK_STAILQ_FIRST(&V_ifnet); ifp;
422 ifp = CK_STAILQ_NEXT(ifp, if_link)) {
423 /* read from if_snd unlocked */
424 if (!TBR_IS_ENABLED(&ifp->if_snd))
427 if (!IFQ_IS_EMPTY(&ifp->if_snd) &&
428 ifp->if_start != NULL)
429 (*ifp->if_start)(ifp);
433 VNET_LIST_RUNLOCK_NOSLEEP();
436 CALLOUT_RESET(&tbr_callout, 1, tbr_timeout, (void *)0);
438 tbr_timer = 0; /* don't need tbr_timer anymore */
442 * attach a discipline to the interface. if one already exists, it is
444 * Locking is done in the discipline specific attach functions. Basically
445 * they call back to altq_attach which takes care of the attach and locking.
448 altq_pfattach(struct pf_altq *a)
452 switch (a->scheduler) {
457 error = cbq_pfattach(a);
462 error = priq_pfattach(a);
467 error = hfsc_pfattach(a);
472 error = fairq_pfattach(a);
477 error = codel_pfattach(a);
488 * detach a discipline from the interface.
489 * it is possible that the discipline was already overridden by another
493 altq_pfdetach(struct pf_altq *a)
498 if ((ifp = ifunit(a->ifname)) == NULL)
501 /* if this discipline is no longer referenced, just return */
502 /* read unlocked from if_snd */
503 if (a->altq_disc == NULL || a->altq_disc != ifp->if_snd.altq_disc)
507 /* read unlocked from if_snd, _disable and _detach take care */
508 if (ALTQ_IS_ENABLED(&ifp->if_snd))
509 error = altq_disable(&ifp->if_snd);
511 error = altq_detach(&ifp->if_snd);
518 * add a discipline or a queue
519 * Locking is done in the discipline specific functions with regards to
520 * malloc with WAITOK, also it is not yet clear which lock to use.
523 altq_add(struct ifnet *ifp, struct pf_altq *a)
527 if (a->qname[0] != 0)
528 return (altq_add_queue(a));
530 if (machclk_freq == 0)
532 if (machclk_freq == 0)
533 panic("altq_add: no cpu clock");
535 switch (a->scheduler) {
538 error = cbq_add_altq(ifp, a);
543 error = priq_add_altq(ifp, a);
548 error = hfsc_add_altq(ifp, a);
553 error = fairq_add_altq(ifp, a);
558 error = codel_add_altq(ifp, a);
569 * remove a discipline or a queue
570 * It is yet unclear what lock to use to protect this operation, the
571 * discipline specific functions will determine and grab it
574 altq_remove(struct pf_altq *a)
578 if (a->qname[0] != 0)
579 return (altq_remove_queue(a));
581 switch (a->scheduler) {
584 error = cbq_remove_altq(a);
589 error = priq_remove_altq(a);
594 error = hfsc_remove_altq(a);
599 error = fairq_remove_altq(a);
604 error = codel_remove_altq(a);
615 * add a queue to the discipline
616 * It is yet unclear what lock to use to protect this operation, the
617 * discipline specific functions will determine and grab it
620 altq_add_queue(struct pf_altq *a)
624 switch (a->scheduler) {
627 error = cbq_add_queue(a);
632 error = priq_add_queue(a);
637 error = hfsc_add_queue(a);
642 error = fairq_add_queue(a);
653 * remove a queue from the discipline
654 * It is yet unclear what lock to use to protect this operation, the
655 * discipline specific functions will determine and grab it
658 altq_remove_queue(struct pf_altq *a)
662 switch (a->scheduler) {
665 error = cbq_remove_queue(a);
670 error = priq_remove_queue(a);
675 error = hfsc_remove_queue(a);
680 error = fairq_remove_queue(a);
691 * get queue statistics
692 * Locking is done in the discipline specific functions with regards to
693 * copyout operations, also it is not yet clear which lock to use.
696 altq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes, int version)
700 switch (a->scheduler) {
703 error = cbq_getqstats(a, ubuf, nbytes, version);
708 error = priq_getqstats(a, ubuf, nbytes, version);
713 error = hfsc_getqstats(a, ubuf, nbytes, version);
718 error = fairq_getqstats(a, ubuf, nbytes, version);
723 error = codel_getqstats(a, ubuf, nbytes, version);
734 * read and write diffserv field in IPv4 or IPv6 header
737 read_dsfield(m, pktattr)
739 struct altq_pktattr *pktattr;
742 u_int8_t ds_field = 0;
744 if (pktattr == NULL ||
745 (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6))
746 return ((u_int8_t)0);
748 /* verify that pattr_hdr is within the mbuf data */
749 for (m0 = m; m0 != NULL; m0 = m0->m_next)
750 if ((pktattr->pattr_hdr >= m0->m_data) &&
751 (pktattr->pattr_hdr < m0->m_data + m0->m_len))
754 /* ick, pattr_hdr is stale */
755 pktattr->pattr_af = AF_UNSPEC;
757 printf("read_dsfield: can't locate header!\n");
759 return ((u_int8_t)0);
762 if (pktattr->pattr_af == AF_INET) {
763 struct ip *ip = (struct ip *)pktattr->pattr_hdr;
766 return ((u_int8_t)0); /* version mismatch! */
767 ds_field = ip->ip_tos;
770 else if (pktattr->pattr_af == AF_INET6) {
771 struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr;
774 flowlabel = ntohl(ip6->ip6_flow);
775 if ((flowlabel >> 28) != 6)
776 return ((u_int8_t)0); /* version mismatch! */
777 ds_field = (flowlabel >> 20) & 0xff;
784 write_dsfield(struct mbuf *m, struct altq_pktattr *pktattr, u_int8_t dsfield)
788 if (pktattr == NULL ||
789 (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6))
792 /* verify that pattr_hdr is within the mbuf data */
793 for (m0 = m; m0 != NULL; m0 = m0->m_next)
794 if ((pktattr->pattr_hdr >= m0->m_data) &&
795 (pktattr->pattr_hdr < m0->m_data + m0->m_len))
798 /* ick, pattr_hdr is stale */
799 pktattr->pattr_af = AF_UNSPEC;
801 printf("write_dsfield: can't locate header!\n");
806 if (pktattr->pattr_af == AF_INET) {
807 struct ip *ip = (struct ip *)pktattr->pattr_hdr;
812 return; /* version mismatch! */
814 dsfield |= old & 3; /* leave CU bits */
817 ip->ip_tos = dsfield;
819 * update checksum (from RFC1624)
820 * HC' = ~(~HC + ~m + m')
822 sum = ~ntohs(ip->ip_sum) & 0xffff;
823 sum += 0xff00 + (~old & 0xff) + dsfield;
824 sum = (sum >> 16) + (sum & 0xffff);
825 sum += (sum >> 16); /* add carry */
827 ip->ip_sum = htons(~sum & 0xffff);
830 else if (pktattr->pattr_af == AF_INET6) {
831 struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr;
834 flowlabel = ntohl(ip6->ip6_flow);
835 if ((flowlabel >> 28) != 6)
836 return; /* version mismatch! */
837 flowlabel = (flowlabel & 0xf03fffff) | (dsfield << 20);
838 ip6->ip6_flow = htonl(flowlabel);
846 * high resolution clock support taking advantage of a machine dependent
847 * high resolution time counter (e.g., timestamp counter of intel pentium).
849 * - 64-bit-long monotonically-increasing counter
850 * - frequency range is 100M-4GHz (CPU speed)
852 /* if pcc is not available or disabled, emulate 256MHz using microtime() */
853 #define MACHCLK_SHIFT 8
856 u_int32_t machclk_freq;
857 u_int32_t machclk_per_tick;
859 #if defined(__i386__) && defined(__NetBSD__)
860 extern u_int64_t cpu_tsc_freq;
863 #if (__FreeBSD_version >= 700035)
864 /* Update TSC freq with the value indicated by the caller. */
866 tsc_freq_changed(void *arg, const struct cf_level *level, int status)
868 /* If there was an error during the transition, don't do anything. */
872 #if (__FreeBSD_version >= 701102) && (defined(__amd64__) || defined(__i386__))
873 /* If TSC is P-state invariant, don't do anything. */
874 if (tsc_is_invariant)
878 /* Total setting for this level gives the new frequency in MHz. */
881 EVENTHANDLER_DEFINE(cpufreq_post_change, tsc_freq_changed, NULL,
882 EVENTHANDLER_PRI_LAST);
883 #endif /* __FreeBSD_version >= 700035 */
886 init_machclk_setup(void)
888 #if (__FreeBSD_version >= 600000)
889 callout_init(&tbr_callout, 0);
894 #if (!defined(__amd64__) && !defined(__i386__)) || defined(ALTQ_NOPCC)
897 #if defined(__FreeBSD__) && defined(SMP)
900 #if defined(__NetBSD__) && defined(MULTIPROCESSOR)
903 #if defined(__amd64__) || defined(__i386__)
904 /* check if TSC is available */
905 if ((cpu_feature & CPUID_TSC) == 0 ||
906 atomic_load_acq_64(&tsc_freq) == 0)
916 /* Call one-time initialization function. */
918 init_machclk_setup();
922 if (machclk_usepcc == 0) {
923 /* emulate 256MHz using microtime() */
924 machclk_freq = 1000000 << MACHCLK_SHIFT;
925 machclk_per_tick = machclk_freq / hz;
927 printf("altq: emulate %uHz cpu clock\n", machclk_freq);
933 * if the clock frequency (of Pentium TSC or Alpha PCC) is
934 * accessible, just use it.
936 #if defined(__amd64__) || defined(__i386__)
937 machclk_freq = atomic_load_acq_64(&tsc_freq);
941 * if we don't know the clock frequency, measure it.
943 if (machclk_freq == 0) {
945 struct timeval tv_start, tv_end;
946 u_int64_t start, end, diff;
949 microtime(&tv_start);
950 start = read_machclk();
951 timo = hz; /* 1 sec */
952 (void)tsleep(&wait, PWAIT | PCATCH, "init_machclk", timo);
954 end = read_machclk();
955 diff = (u_int64_t)(tv_end.tv_sec - tv_start.tv_sec) * 1000000
956 + tv_end.tv_usec - tv_start.tv_usec;
958 machclk_freq = (u_int)((end - start) * 1000000 / diff);
961 machclk_per_tick = machclk_freq / hz;
964 printf("altq: CPU clock: %uHz\n", machclk_freq);
968 #if defined(__OpenBSD__) && defined(__i386__)
969 static __inline u_int64_t
973 __asm __volatile(".byte 0x0f, 0x31" : "=A" (rv));
976 #endif /* __OpenBSD__ && __i386__ */
983 if (machclk_usepcc) {
984 #if defined(__amd64__) || defined(__i386__)
987 panic("read_machclk");
990 struct timeval tv, boottime;
993 getboottime(&boottime);
994 val = (((u_int64_t)(tv.tv_sec - boottime.tv_sec) * 1000000
995 + tv.tv_usec) << MACHCLK_SHIFT);
1000 #ifdef ALTQ3_CLFIER_COMPAT
1003 #define IPPROTO_ESP 50 /* encapsulating security payload */
1006 #define IPPROTO_AH 51 /* authentication header */
1010 * extract flow information from a given packet.
1011 * filt_mask shows flowinfo fields required.
1012 * we assume the ip header is in one mbuf, and addresses and ports are
1013 * in network byte order.
1016 altq_extractflow(m, af, flow, filt_bmask)
1019 struct flowinfo *flow;
1020 u_int32_t filt_bmask;
1025 struct flowinfo_in *fin;
1028 ip = mtod(m, struct ip *);
1033 fin = (struct flowinfo_in *)flow;
1034 fin->fi_len = sizeof(struct flowinfo_in);
1035 fin->fi_family = AF_INET;
1037 fin->fi_proto = ip->ip_p;
1038 fin->fi_tos = ip->ip_tos;
1040 fin->fi_src.s_addr = ip->ip_src.s_addr;
1041 fin->fi_dst.s_addr = ip->ip_dst.s_addr;
1043 if (filt_bmask & FIMB4_PORTS)
1044 /* if port info is required, extract port numbers */
1045 extract_ports4(m, ip, fin);
1056 struct flowinfo_in6 *fin6;
1057 struct ip6_hdr *ip6;
1059 ip6 = mtod(m, struct ip6_hdr *);
1060 /* should we check the ip version? */
1062 fin6 = (struct flowinfo_in6 *)flow;
1063 fin6->fi6_len = sizeof(struct flowinfo_in6);
1064 fin6->fi6_family = AF_INET6;
1066 fin6->fi6_proto = ip6->ip6_nxt;
1067 fin6->fi6_tclass = (ntohl(ip6->ip6_flow) >> 20) & 0xff;
1069 fin6->fi6_flowlabel = ip6->ip6_flow & htonl(0x000fffff);
1070 fin6->fi6_src = ip6->ip6_src;
1071 fin6->fi6_dst = ip6->ip6_dst;
1073 if ((filt_bmask & FIMB6_PORTS) ||
1074 ((filt_bmask & FIMB6_PROTO)
1075 && ip6->ip6_nxt > IPPROTO_IPV6))
1077 * if port info is required, or proto is required
1078 * but there are option headers, extract port
1079 * and protocol numbers.
1081 extract_ports6(m, ip6, fin6);
1083 fin6->fi6_sport = 0;
1084 fin6->fi6_dport = 0;
1096 flow->fi_len = sizeof(struct flowinfo);
1097 flow->fi_family = AF_UNSPEC;
1102 * helper routine to extract port numbers
1104 /* structure for ipsec and ipv6 option header template */
1106 u_int8_t opt6_nxt; /* next header */
1107 u_int8_t opt6_hlen; /* header extension length */
1109 u_int32_t ah_spi; /* security parameter index
1110 for authentication header */
1114 * extract port numbers from a ipv4 packet.
1117 extract_ports4(m, ip, fin)
1120 struct flowinfo_in *fin;
1131 ip_off = ntohs(ip->ip_off);
1132 /* if it is a fragment, try cached fragment info */
1133 if (ip_off & IP_OFFMASK) {
1134 ip4f_lookup(ip, fin);
1138 /* locate the mbuf containing the protocol header */
1139 for (m0 = m; m0 != NULL; m0 = m0->m_next)
1140 if (((caddr_t)ip >= m0->m_data) &&
1141 ((caddr_t)ip < m0->m_data + m0->m_len))
1145 printf("extract_ports4: can't locate header! ip=%p\n", ip);
1149 off = ((caddr_t)ip - m0->m_data) + (ip->ip_hl << 2);
1155 while (off >= m0->m_len) {
1159 return (0); /* bogus ip_hl! */
1161 if (m0->m_len < off + 4)
1169 udp = (struct udphdr *)(mtod(m0, caddr_t) + off);
1170 fin->fi_sport = udp->uh_sport;
1171 fin->fi_dport = udp->uh_dport;
1172 fin->fi_proto = proto;
1178 if (fin->fi_gpi == 0){
1181 gpi = (u_int32_t *)(mtod(m0, caddr_t) + off);
1184 fin->fi_proto = proto;
1188 /* get next header and header length */
1191 opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1192 proto = opt6->opt6_nxt;
1193 off += 8 + (opt6->opt6_hlen * 4);
1194 if (fin->fi_gpi == 0 && m0->m_len >= off + 8)
1195 fin->fi_gpi = opt6->ah_spi;
1197 /* goto the next header */
1199 #endif /* ALTQ_IPSEC */
1202 fin->fi_proto = proto;
1206 /* if this is a first fragment, cache it. */
1208 ip4f_cache(ip, fin);
1215 extract_ports6(m, ip6, fin6)
1217 struct ip6_hdr *ip6;
1218 struct flowinfo_in6 *fin6;
1225 fin6->fi6_sport = 0;
1226 fin6->fi6_dport = 0;
1228 /* locate the mbuf containing the protocol header */
1229 for (m0 = m; m0 != NULL; m0 = m0->m_next)
1230 if (((caddr_t)ip6 >= m0->m_data) &&
1231 ((caddr_t)ip6 < m0->m_data + m0->m_len))
1235 printf("extract_ports6: can't locate header! ip6=%p\n", ip6);
1239 off = ((caddr_t)ip6 - m0->m_data) + sizeof(struct ip6_hdr);
1241 proto = ip6->ip6_nxt;
1243 while (off >= m0->m_len) {
1249 if (m0->m_len < off + 4)
1257 udp = (struct udphdr *)(mtod(m0, caddr_t) + off);
1258 fin6->fi6_sport = udp->uh_sport;
1259 fin6->fi6_dport = udp->uh_dport;
1260 fin6->fi6_proto = proto;
1265 if (fin6->fi6_gpi == 0) {
1268 gpi = (u_int32_t *)(mtod(m0, caddr_t) + off);
1269 fin6->fi6_gpi = *gpi;
1271 fin6->fi6_proto = proto;
1275 /* get next header and header length */
1278 opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1279 if (fin6->fi6_gpi == 0 && m0->m_len >= off + 8)
1280 fin6->fi6_gpi = opt6->ah_spi;
1281 proto = opt6->opt6_nxt;
1282 off += 8 + (opt6->opt6_hlen * 4);
1283 /* goto the next header */
1287 case IPPROTO_HOPOPTS:
1288 case IPPROTO_ROUTING:
1289 case IPPROTO_DSTOPTS: {
1290 /* get next header and header length */
1293 opt6 = (struct _opt6 *)(mtod(m0, caddr_t) + off);
1294 proto = opt6->opt6_nxt;
1295 off += (opt6->opt6_hlen + 1) * 8;
1296 /* goto the next header */
1300 case IPPROTO_FRAGMENT:
1301 /* ipv6 fragmentations are not supported yet */
1303 fin6->fi6_proto = proto;
1312 * altq common classifier
1315 acc_add_filter(classifier, filter, class, phandle)
1316 struct acc_classifier *classifier;
1317 struct flow_filter *filter;
1321 struct acc_filter *afp, *prev, *tmp;
1325 if (filter->ff_flow.fi_family != AF_INET &&
1326 filter->ff_flow.fi_family != AF_INET6)
1329 if (filter->ff_flow.fi_family != AF_INET)
1333 afp = malloc(sizeof(struct acc_filter),
1334 M_DEVBUF, M_WAITOK);
1337 bzero(afp, sizeof(struct acc_filter));
1339 afp->f_filter = *filter;
1340 afp->f_class = class;
1342 i = ACC_WILDCARD_INDEX;
1343 if (filter->ff_flow.fi_family == AF_INET) {
1344 struct flow_filter *filter4 = &afp->f_filter;
1347 * if address is 0, it's a wildcard. if address mask
1348 * isn't set, use full mask.
1350 if (filter4->ff_flow.fi_dst.s_addr == 0)
1351 filter4->ff_mask.mask_dst.s_addr = 0;
1352 else if (filter4->ff_mask.mask_dst.s_addr == 0)
1353 filter4->ff_mask.mask_dst.s_addr = 0xffffffff;
1354 if (filter4->ff_flow.fi_src.s_addr == 0)
1355 filter4->ff_mask.mask_src.s_addr = 0;
1356 else if (filter4->ff_mask.mask_src.s_addr == 0)
1357 filter4->ff_mask.mask_src.s_addr = 0xffffffff;
1359 /* clear extra bits in addresses */
1360 filter4->ff_flow.fi_dst.s_addr &=
1361 filter4->ff_mask.mask_dst.s_addr;
1362 filter4->ff_flow.fi_src.s_addr &=
1363 filter4->ff_mask.mask_src.s_addr;
1366 * if dst address is a wildcard, use hash-entry
1367 * ACC_WILDCARD_INDEX.
1369 if (filter4->ff_mask.mask_dst.s_addr != 0xffffffff)
1370 i = ACC_WILDCARD_INDEX;
1372 i = ACC_GET_HASH_INDEX(filter4->ff_flow.fi_dst.s_addr);
1375 else if (filter->ff_flow.fi_family == AF_INET6) {
1376 struct flow_filter6 *filter6 =
1377 (struct flow_filter6 *)&afp->f_filter;
1378 #ifndef IN6MASK0 /* taken from kame ipv6 */
1379 #define IN6MASK0 {{{ 0, 0, 0, 0 }}}
1380 #define IN6MASK128 {{{ 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff }}}
1381 const struct in6_addr in6mask0 = IN6MASK0;
1382 const struct in6_addr in6mask128 = IN6MASK128;
1385 if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_flow6.fi6_dst))
1386 filter6->ff_mask6.mask6_dst = in6mask0;
1387 else if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_mask6.mask6_dst))
1388 filter6->ff_mask6.mask6_dst = in6mask128;
1389 if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_flow6.fi6_src))
1390 filter6->ff_mask6.mask6_src = in6mask0;
1391 else if (IN6_IS_ADDR_UNSPECIFIED(&filter6->ff_mask6.mask6_src))
1392 filter6->ff_mask6.mask6_src = in6mask128;
1394 /* clear extra bits in addresses */
1395 for (i = 0; i < 16; i++)
1396 filter6->ff_flow6.fi6_dst.s6_addr[i] &=
1397 filter6->ff_mask6.mask6_dst.s6_addr[i];
1398 for (i = 0; i < 16; i++)
1399 filter6->ff_flow6.fi6_src.s6_addr[i] &=
1400 filter6->ff_mask6.mask6_src.s6_addr[i];
1402 if (filter6->ff_flow6.fi6_flowlabel == 0)
1403 i = ACC_WILDCARD_INDEX;
1405 i = ACC_GET_HASH_INDEX(filter6->ff_flow6.fi6_flowlabel);
1409 afp->f_handle = get_filt_handle(classifier, i);
1411 /* update filter bitmask */
1412 afp->f_fbmask = filt2fibmask(filter);
1413 classifier->acc_fbmask |= afp->f_fbmask;
1416 * add this filter to the filter list.
1417 * filters are ordered from the highest rule number.
1421 LIST_FOREACH(tmp, &classifier->acc_filters[i], f_chain) {
1422 if (tmp->f_filter.ff_ruleno > afp->f_filter.ff_ruleno)
1428 LIST_INSERT_HEAD(&classifier->acc_filters[i], afp, f_chain);
1430 LIST_INSERT_AFTER(prev, afp, f_chain);
1433 *phandle = afp->f_handle;
1438 acc_delete_filter(classifier, handle)
1439 struct acc_classifier *classifier;
1442 struct acc_filter *afp;
1445 if ((afp = filth_to_filtp(classifier, handle)) == NULL)
1449 LIST_REMOVE(afp, f_chain);
1452 free(afp, M_DEVBUF);
1454 /* todo: update filt_bmask */
1460 * delete filters referencing to the specified class.
1461 * if the all flag is not 0, delete all the filters.
1464 acc_discard_filters(classifier, class, all)
1465 struct acc_classifier *classifier;
1469 struct acc_filter *afp;
1473 for (i = 0; i < ACC_FILTER_TABLESIZE; i++) {
1475 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1476 if (all || afp->f_class == class) {
1477 LIST_REMOVE(afp, f_chain);
1478 free(afp, M_DEVBUF);
1479 /* start again from the head */
1482 } while (afp != NULL);
1487 classifier->acc_fbmask = 0;
1493 acc_classify(clfier, m, af)
1498 struct acc_classifier *classifier;
1499 struct flowinfo flow;
1500 struct acc_filter *afp;
1503 classifier = (struct acc_classifier *)clfier;
1504 altq_extractflow(m, af, &flow, classifier->acc_fbmask);
1506 if (flow.fi_family == AF_INET) {
1507 struct flowinfo_in *fp = (struct flowinfo_in *)&flow;
1509 if ((classifier->acc_fbmask & FIMB4_ALL) == FIMB4_TOS) {
1510 /* only tos is used */
1512 &classifier->acc_filters[ACC_WILDCARD_INDEX],
1514 if (apply_tosfilter4(afp->f_fbmask,
1515 &afp->f_filter, fp))
1516 /* filter matched */
1517 return (afp->f_class);
1518 } else if ((classifier->acc_fbmask &
1519 (~(FIMB4_PROTO|FIMB4_SPORT|FIMB4_DPORT) & FIMB4_ALL))
1521 /* only proto and ports are used */
1523 &classifier->acc_filters[ACC_WILDCARD_INDEX],
1525 if (apply_ppfilter4(afp->f_fbmask,
1526 &afp->f_filter, fp))
1527 /* filter matched */
1528 return (afp->f_class);
1530 /* get the filter hash entry from its dest address */
1531 i = ACC_GET_HASH_INDEX(fp->fi_dst.s_addr);
1534 * go through this loop twice. first for dst
1535 * hash, second for wildcards.
1537 LIST_FOREACH(afp, &classifier->acc_filters[i],
1539 if (apply_filter4(afp->f_fbmask,
1540 &afp->f_filter, fp))
1541 /* filter matched */
1542 return (afp->f_class);
1545 * check again for filters with a dst addr
1547 * (daddr == 0 || dmask != 0xffffffff).
1549 if (i != ACC_WILDCARD_INDEX)
1550 i = ACC_WILDCARD_INDEX;
1557 else if (flow.fi_family == AF_INET6) {
1558 struct flowinfo_in6 *fp6 = (struct flowinfo_in6 *)&flow;
1560 /* get the filter hash entry from its flow ID */
1561 if (fp6->fi6_flowlabel != 0)
1562 i = ACC_GET_HASH_INDEX(fp6->fi6_flowlabel);
1564 /* flowlable can be zero */
1565 i = ACC_WILDCARD_INDEX;
1567 /* go through this loop twice. first for flow hash, second
1570 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1571 if (apply_filter6(afp->f_fbmask,
1572 (struct flow_filter6 *)&afp->f_filter,
1574 /* filter matched */
1575 return (afp->f_class);
1578 * check again for filters with a wildcard.
1580 if (i != ACC_WILDCARD_INDEX)
1581 i = ACC_WILDCARD_INDEX;
1588 /* no filter matched */
1593 apply_filter4(fbmask, filt, pkt)
1595 struct flow_filter *filt;
1596 struct flowinfo_in *pkt;
1598 if (filt->ff_flow.fi_family != AF_INET)
1600 if ((fbmask & FIMB4_SPORT) && filt->ff_flow.fi_sport != pkt->fi_sport)
1602 if ((fbmask & FIMB4_DPORT) && filt->ff_flow.fi_dport != pkt->fi_dport)
1604 if ((fbmask & FIMB4_DADDR) &&
1605 filt->ff_flow.fi_dst.s_addr !=
1606 (pkt->fi_dst.s_addr & filt->ff_mask.mask_dst.s_addr))
1608 if ((fbmask & FIMB4_SADDR) &&
1609 filt->ff_flow.fi_src.s_addr !=
1610 (pkt->fi_src.s_addr & filt->ff_mask.mask_src.s_addr))
1612 if ((fbmask & FIMB4_PROTO) && filt->ff_flow.fi_proto != pkt->fi_proto)
1614 if ((fbmask & FIMB4_TOS) && filt->ff_flow.fi_tos !=
1615 (pkt->fi_tos & filt->ff_mask.mask_tos))
1617 if ((fbmask & FIMB4_GPI) && filt->ff_flow.fi_gpi != (pkt->fi_gpi))
1624 * filter matching function optimized for a common case that checks
1625 * only protocol and port numbers
1628 apply_ppfilter4(fbmask, filt, pkt)
1630 struct flow_filter *filt;
1631 struct flowinfo_in *pkt;
1633 if (filt->ff_flow.fi_family != AF_INET)
1635 if ((fbmask & FIMB4_SPORT) && filt->ff_flow.fi_sport != pkt->fi_sport)
1637 if ((fbmask & FIMB4_DPORT) && filt->ff_flow.fi_dport != pkt->fi_dport)
1639 if ((fbmask & FIMB4_PROTO) && filt->ff_flow.fi_proto != pkt->fi_proto)
1646 * filter matching function only for tos field.
1649 apply_tosfilter4(fbmask, filt, pkt)
1651 struct flow_filter *filt;
1652 struct flowinfo_in *pkt;
1654 if (filt->ff_flow.fi_family != AF_INET)
1656 if ((fbmask & FIMB4_TOS) && filt->ff_flow.fi_tos !=
1657 (pkt->fi_tos & filt->ff_mask.mask_tos))
1665 apply_filter6(fbmask, filt, pkt)
1667 struct flow_filter6 *filt;
1668 struct flowinfo_in6 *pkt;
1672 if (filt->ff_flow6.fi6_family != AF_INET6)
1674 if ((fbmask & FIMB6_FLABEL) &&
1675 filt->ff_flow6.fi6_flowlabel != pkt->fi6_flowlabel)
1677 if ((fbmask & FIMB6_PROTO) &&
1678 filt->ff_flow6.fi6_proto != pkt->fi6_proto)
1680 if ((fbmask & FIMB6_SPORT) &&
1681 filt->ff_flow6.fi6_sport != pkt->fi6_sport)
1683 if ((fbmask & FIMB6_DPORT) &&
1684 filt->ff_flow6.fi6_dport != pkt->fi6_dport)
1686 if (fbmask & FIMB6_SADDR) {
1687 for (i = 0; i < 4; i++)
1688 if (filt->ff_flow6.fi6_src.s6_addr32[i] !=
1689 (pkt->fi6_src.s6_addr32[i] &
1690 filt->ff_mask6.mask6_src.s6_addr32[i]))
1693 if (fbmask & FIMB6_DADDR) {
1694 for (i = 0; i < 4; i++)
1695 if (filt->ff_flow6.fi6_dst.s6_addr32[i] !=
1696 (pkt->fi6_dst.s6_addr32[i] &
1697 filt->ff_mask6.mask6_dst.s6_addr32[i]))
1700 if ((fbmask & FIMB6_TCLASS) &&
1701 filt->ff_flow6.fi6_tclass !=
1702 (pkt->fi6_tclass & filt->ff_mask6.mask6_tclass))
1704 if ((fbmask & FIMB6_GPI) &&
1705 filt->ff_flow6.fi6_gpi != pkt->fi6_gpi)
1714 * bit 20-28: index to the filter hash table
1715 * bit 0-19: unique id in the hash bucket.
1718 get_filt_handle(classifier, i)
1719 struct acc_classifier *classifier;
1722 static u_long handle_number = 1;
1724 struct acc_filter *afp;
1727 handle = handle_number++ & 0x000fffff;
1729 if (LIST_EMPTY(&classifier->acc_filters[i]))
1732 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1733 if ((afp->f_handle & 0x000fffff) == handle)
1737 /* this handle is already used, try again */
1740 return ((i << 20) | handle);
1743 /* convert filter handle to filter pointer */
1744 static struct acc_filter *
1745 filth_to_filtp(classifier, handle)
1746 struct acc_classifier *classifier;
1749 struct acc_filter *afp;
1752 i = ACC_GET_HINDEX(handle);
1754 LIST_FOREACH(afp, &classifier->acc_filters[i], f_chain)
1755 if (afp->f_handle == handle)
1761 /* create flowinfo bitmask */
1764 struct flow_filter *filt;
1768 struct flow_filter6 *filt6;
1771 switch (filt->ff_flow.fi_family) {
1773 if (filt->ff_flow.fi_proto != 0)
1774 mask |= FIMB4_PROTO;
1775 if (filt->ff_flow.fi_tos != 0)
1777 if (filt->ff_flow.fi_dst.s_addr != 0)
1778 mask |= FIMB4_DADDR;
1779 if (filt->ff_flow.fi_src.s_addr != 0)
1780 mask |= FIMB4_SADDR;
1781 if (filt->ff_flow.fi_sport != 0)
1782 mask |= FIMB4_SPORT;
1783 if (filt->ff_flow.fi_dport != 0)
1784 mask |= FIMB4_DPORT;
1785 if (filt->ff_flow.fi_gpi != 0)
1790 filt6 = (struct flow_filter6 *)filt;
1792 if (filt6->ff_flow6.fi6_proto != 0)
1793 mask |= FIMB6_PROTO;
1794 if (filt6->ff_flow6.fi6_tclass != 0)
1795 mask |= FIMB6_TCLASS;
1796 if (!IN6_IS_ADDR_UNSPECIFIED(&filt6->ff_flow6.fi6_dst))
1797 mask |= FIMB6_DADDR;
1798 if (!IN6_IS_ADDR_UNSPECIFIED(&filt6->ff_flow6.fi6_src))
1799 mask |= FIMB6_SADDR;
1800 if (filt6->ff_flow6.fi6_sport != 0)
1801 mask |= FIMB6_SPORT;
1802 if (filt6->ff_flow6.fi6_dport != 0)
1803 mask |= FIMB6_DPORT;
1804 if (filt6->ff_flow6.fi6_gpi != 0)
1806 if (filt6->ff_flow6.fi6_flowlabel != 0)
1807 mask |= FIMB6_FLABEL;
1816 * helper functions to handle IPv4 fragments.
1817 * currently only in-sequence fragments are handled.
1818 * - fragment info is cached in a LRU list.
1819 * - when a first fragment is found, cache its flow info.
1820 * - when a non-first fragment is found, lookup the cache.
1824 TAILQ_ENTRY(ip4_frag) ip4f_chain;
1827 struct flowinfo_in ip4f_info;
1830 static TAILQ_HEAD(ip4f_list, ip4_frag) ip4f_list; /* IPv4 fragment cache */
1832 #define IP4F_TABSIZE 16 /* IPv4 fragment cache size */
1838 struct flowinfo_in *fin;
1840 struct ip4_frag *fp;
1842 if (TAILQ_EMPTY(&ip4f_list)) {
1843 /* first time call, allocate fragment cache entries. */
1844 if (ip4f_init() < 0)
1845 /* allocation failed! */
1850 fp->ip4f_id = ip->ip_id;
1851 fp->ip4f_info.fi_proto = ip->ip_p;
1852 fp->ip4f_info.fi_src.s_addr = ip->ip_src.s_addr;
1853 fp->ip4f_info.fi_dst.s_addr = ip->ip_dst.s_addr;
1855 /* save port numbers */
1856 fp->ip4f_info.fi_sport = fin->fi_sport;
1857 fp->ip4f_info.fi_dport = fin->fi_dport;
1858 fp->ip4f_info.fi_gpi = fin->fi_gpi;
1862 ip4f_lookup(ip, fin)
1864 struct flowinfo_in *fin;
1866 struct ip4_frag *fp;
1868 for (fp = TAILQ_FIRST(&ip4f_list); fp != NULL && fp->ip4f_valid;
1869 fp = TAILQ_NEXT(fp, ip4f_chain))
1870 if (ip->ip_id == fp->ip4f_id &&
1871 ip->ip_src.s_addr == fp->ip4f_info.fi_src.s_addr &&
1872 ip->ip_dst.s_addr == fp->ip4f_info.fi_dst.s_addr &&
1873 ip->ip_p == fp->ip4f_info.fi_proto) {
1875 /* found the matching entry */
1876 fin->fi_sport = fp->ip4f_info.fi_sport;
1877 fin->fi_dport = fp->ip4f_info.fi_dport;
1878 fin->fi_gpi = fp->ip4f_info.fi_gpi;
1880 if ((ntohs(ip->ip_off) & IP_MF) == 0)
1881 /* this is the last fragment,
1882 release the entry. */
1888 /* no matching entry found */
1895 struct ip4_frag *fp;
1898 TAILQ_INIT(&ip4f_list);
1899 for (i=0; i<IP4F_TABSIZE; i++) {
1900 fp = malloc(sizeof(struct ip4_frag),
1901 M_DEVBUF, M_NOWAIT);
1903 printf("ip4f_init: can't alloc %dth entry!\n", i);
1909 TAILQ_INSERT_TAIL(&ip4f_list, fp, ip4f_chain);
1914 static struct ip4_frag *
1917 struct ip4_frag *fp;
1919 /* reclaim an entry at the tail, put it at the head */
1920 fp = TAILQ_LAST(&ip4f_list, ip4f_list);
1921 TAILQ_REMOVE(&ip4f_list, fp, ip4f_chain);
1923 TAILQ_INSERT_HEAD(&ip4f_list, fp, ip4f_chain);
1929 struct ip4_frag *fp;
1931 TAILQ_REMOVE(&ip4f_list, fp, ip4f_chain);
1933 TAILQ_INSERT_TAIL(&ip4f_list, fp, ip4f_chain);
1936 #endif /* ALTQ3_CLFIER_COMPAT */