Remove building with NOCRYPTO option
[minix.git] / sys / net / bpf_filter.c
blob926a372b99124f454df381bf0bb5721d8d604614
1 /* $NetBSD: bpf_filter.c,v 1.70 2015/02/11 12:53:15 alnsn Exp $ */
3 /*-
4 * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from the Stanford/CMU enet packet filter,
8 * (net/enet.c) distributed as part of 4.3BSD, and code contributed
9 * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence
10 * Berkeley Laboratory.
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
36 * @(#)bpf_filter.c 8.1 (Berkeley) 6/10/93
39 #include <sys/cdefs.h>
40 __KERNEL_RCSID(0, "$NetBSD: bpf_filter.c,v 1.70 2015/02/11 12:53:15 alnsn Exp $");
42 #if 0
43 #if !(defined(lint) || defined(KERNEL))
44 static const char rcsid[] =
45 "@(#) Header: bpf_filter.c,v 1.33 97/04/26 13:37:18 leres Exp (LBL)";
46 #endif
47 #endif
49 #include <sys/param.h>
50 #include <sys/time.h>
51 #include <sys/kmem.h>
52 #include <sys/endian.h>
54 #define __BPF_PRIVATE
55 #include <net/bpf.h>
57 #ifdef _KERNEL
59 bpf_ctx_t *
60 bpf_create(void)
62 return kmem_zalloc(sizeof(bpf_ctx_t), KM_SLEEP);
65 void
66 bpf_destroy(bpf_ctx_t *bc)
68 kmem_free(bc, sizeof(bpf_ctx_t));
71 int
72 bpf_set_cop(bpf_ctx_t *bc, const bpf_copfunc_t *funcs, size_t n)
74 bc->copfuncs = funcs;
75 bc->nfuncs = n;
76 return 0;
79 int
80 bpf_set_extmem(bpf_ctx_t *bc, size_t nwords, bpf_memword_init_t preinited)
82 if (nwords > BPF_MAX_MEMWORDS || (preinited >> nwords) != 0) {
83 return EINVAL;
85 bc->extwords = nwords;
86 bc->preinited = preinited;
87 return 0;
90 #endif
92 #define EXTRACT_SHORT(p) be16dec(p)
93 #define EXTRACT_LONG(p) be32dec(p)
95 #ifdef _KERNEL
96 #include <sys/mbuf.h>
97 #define MINDEX(len, m, k) \
98 { \
99 len = m->m_len; \
100 while (k >= len) { \
101 k -= len; \
102 m = m->m_next; \
103 if (m == 0) \
104 return 0; \
105 len = m->m_len; \
109 uint32_t m_xword(const struct mbuf *, uint32_t, int *);
110 uint32_t m_xhalf(const struct mbuf *, uint32_t, int *);
111 uint32_t m_xbyte(const struct mbuf *, uint32_t, int *);
113 #define xword(p, k, err) m_xword((const struct mbuf *)(p), (k), (err))
114 #define xhalf(p, k, err) m_xhalf((const struct mbuf *)(p), (k), (err))
115 #define xbyte(p, k, err) m_xbyte((const struct mbuf *)(p), (k), (err))
117 uint32_t
118 m_xword(const struct mbuf *m, uint32_t k, int *err)
120 int len;
121 u_char *cp, *np;
122 struct mbuf *m0;
124 *err = 1;
125 MINDEX(len, m, k);
126 cp = mtod(m, u_char *) + k;
127 if (len - k >= 4) {
128 *err = 0;
129 return EXTRACT_LONG(cp);
131 m0 = m->m_next;
132 if (m0 == 0 || (len - k) + m0->m_len < 4)
133 return 0;
134 *err = 0;
135 np = mtod(m0, u_char *);
137 switch (len - k) {
138 case 1:
139 return (cp[0] << 24) | (np[0] << 16) | (np[1] << 8) | np[2];
140 case 2:
141 return (cp[0] << 24) | (cp[1] << 16) | (np[0] << 8) | np[1];
142 default:
143 return (cp[0] << 24) | (cp[1] << 16) | (cp[2] << 8) | np[0];
147 uint32_t
148 m_xhalf(const struct mbuf *m, uint32_t k, int *err)
150 int len;
151 u_char *cp;
152 struct mbuf *m0;
154 *err = 1;
155 MINDEX(len, m, k);
156 cp = mtod(m, u_char *) + k;
157 if (len - k >= 2) {
158 *err = 0;
159 return EXTRACT_SHORT(cp);
161 m0 = m->m_next;
162 if (m0 == 0)
163 return 0;
164 *err = 0;
165 return (cp[0] << 8) | mtod(m0, u_char *)[0];
168 uint32_t
169 m_xbyte(const struct mbuf *m, uint32_t k, int *err)
171 int len;
173 *err = 1;
174 MINDEX(len, m, k);
175 *err = 0;
176 return mtod(m, u_char *)[k];
178 #else /* _KERNEL */
179 #include <stdlib.h>
180 #endif /* !_KERNEL */
182 #include <net/bpf.h>
185 * Execute the filter program starting at pc on the packet p
186 * wirelen is the length of the original packet
187 * buflen is the amount of data present
189 #ifdef _KERNEL
191 u_int
192 bpf_filter(const struct bpf_insn *pc, const u_char *p, u_int wirelen,
193 u_int buflen)
195 uint32_t mem[BPF_MEMWORDS];
196 bpf_args_t args = {
197 .pkt = p,
198 .wirelen = wirelen,
199 .buflen = buflen,
200 .mem = mem,
201 .arg = NULL
204 return bpf_filter_ext(NULL, pc, &args);
207 u_int
208 bpf_filter_ext(const bpf_ctx_t *bc, const struct bpf_insn *pc, bpf_args_t *args)
209 #else
210 u_int
211 bpf_filter(const struct bpf_insn *pc, const u_char *p, u_int wirelen,
212 u_int buflen)
213 #endif
215 uint32_t A, X, k;
216 #ifndef _KERNEL
217 uint32_t mem[BPF_MEMWORDS];
218 bpf_args_t args_store = {
219 .pkt = p,
220 .wirelen = wirelen,
221 .buflen = buflen,
222 .mem = mem,
223 .arg = NULL
225 bpf_args_t * const args = &args_store;
226 #else
227 const uint8_t * const p = args->pkt;
228 #endif
229 if (pc == 0) {
231 * No filter means accept all.
233 return (u_int)-1;
237 * Note: safe to leave memwords uninitialised, as the validation
238 * step ensures that it will not be read, if it was not written.
240 A = 0;
241 X = 0;
242 --pc;
244 for (;;) {
245 ++pc;
246 switch (pc->code) {
248 default:
249 #ifdef _KERNEL
250 return 0;
251 #else
252 abort();
253 /*NOTREACHED*/
254 #endif
255 case BPF_RET|BPF_K:
256 return (u_int)pc->k;
258 case BPF_RET|BPF_A:
259 return (u_int)A;
261 case BPF_LD|BPF_W|BPF_ABS:
262 k = pc->k;
263 if (k > args->buflen ||
264 sizeof(int32_t) > args->buflen - k) {
265 #ifdef _KERNEL
266 int merr;
268 if (args->buflen != 0)
269 return 0;
270 A = xword(args->pkt, k, &merr);
271 if (merr != 0)
272 return 0;
273 continue;
274 #else
275 return 0;
276 #endif
278 A = EXTRACT_LONG(&p[k]);
279 continue;
281 case BPF_LD|BPF_H|BPF_ABS:
282 k = pc->k;
283 if (k > args->buflen ||
284 sizeof(int16_t) > args->buflen - k) {
285 #ifdef _KERNEL
286 int merr;
288 if (args->buflen != 0)
289 return 0;
290 A = xhalf(args->pkt, k, &merr);
291 if (merr != 0)
292 return 0;
293 continue;
294 #else
295 return 0;
296 #endif
298 A = EXTRACT_SHORT(&p[k]);
299 continue;
301 case BPF_LD|BPF_B|BPF_ABS:
302 k = pc->k;
303 if (k >= args->buflen) {
304 #ifdef _KERNEL
305 int merr;
307 if (args->buflen != 0)
308 return 0;
309 A = xbyte(args->pkt, k, &merr);
310 if (merr != 0)
311 return 0;
312 continue;
313 #else
314 return 0;
315 #endif
317 A = p[k];
318 continue;
320 case BPF_LD|BPF_W|BPF_LEN:
321 A = args->wirelen;
322 continue;
324 case BPF_LDX|BPF_W|BPF_LEN:
325 X = args->wirelen;
326 continue;
328 case BPF_LD|BPF_W|BPF_IND:
329 k = X + pc->k;
330 if (k < X || k >= args->buflen ||
331 sizeof(int32_t) > args->buflen - k) {
332 #ifdef _KERNEL
333 int merr;
335 if (k < X || args->buflen != 0)
336 return 0;
337 A = xword(args->pkt, k, &merr);
338 if (merr != 0)
339 return 0;
340 continue;
341 #else
342 return 0;
343 #endif
345 A = EXTRACT_LONG(&p[k]);
346 continue;
348 case BPF_LD|BPF_H|BPF_IND:
349 k = X + pc->k;
350 if (k < X || k >= args->buflen ||
351 sizeof(int16_t) > args->buflen - k) {
352 #ifdef _KERNEL
353 int merr;
355 if (k < X || args->buflen != 0)
356 return 0;
357 A = xhalf(args->pkt, k, &merr);
358 if (merr != 0)
359 return 0;
360 continue;
361 #else
362 return 0;
363 #endif
365 A = EXTRACT_SHORT(&p[k]);
366 continue;
368 case BPF_LD|BPF_B|BPF_IND:
369 k = X + pc->k;
370 if (k < X || k >= args->buflen) {
371 #ifdef _KERNEL
372 int merr;
374 if (k < X || args->buflen != 0)
375 return 0;
376 A = xbyte(args->pkt, k, &merr);
377 if (merr != 0)
378 return 0;
379 continue;
380 #else
381 return 0;
382 #endif
384 A = p[k];
385 continue;
387 case BPF_LDX|BPF_MSH|BPF_B:
388 k = pc->k;
389 if (k >= args->buflen) {
390 #ifdef _KERNEL
391 int merr;
393 if (args->buflen != 0)
394 return 0;
395 X = (xbyte(args->pkt, k, &merr) & 0xf) << 2;
396 if (merr != 0)
397 return 0;
398 continue;
399 #else
400 return 0;
401 #endif
403 X = (p[pc->k] & 0xf) << 2;
404 continue;
406 case BPF_LD|BPF_IMM:
407 A = pc->k;
408 continue;
410 case BPF_LDX|BPF_IMM:
411 X = pc->k;
412 continue;
414 case BPF_LD|BPF_MEM:
415 A = args->mem[pc->k];
416 continue;
418 case BPF_LDX|BPF_MEM:
419 X = args->mem[pc->k];
420 continue;
422 case BPF_ST:
423 args->mem[pc->k] = A;
424 continue;
426 case BPF_STX:
427 args->mem[pc->k] = X;
428 continue;
430 case BPF_JMP|BPF_JA:
431 pc += pc->k;
432 continue;
434 case BPF_JMP|BPF_JGT|BPF_K:
435 pc += (A > pc->k) ? pc->jt : pc->jf;
436 continue;
438 case BPF_JMP|BPF_JGE|BPF_K:
439 pc += (A >= pc->k) ? pc->jt : pc->jf;
440 continue;
442 case BPF_JMP|BPF_JEQ|BPF_K:
443 pc += (A == pc->k) ? pc->jt : pc->jf;
444 continue;
446 case BPF_JMP|BPF_JSET|BPF_K:
447 pc += (A & pc->k) ? pc->jt : pc->jf;
448 continue;
450 case BPF_JMP|BPF_JGT|BPF_X:
451 pc += (A > X) ? pc->jt : pc->jf;
452 continue;
454 case BPF_JMP|BPF_JGE|BPF_X:
455 pc += (A >= X) ? pc->jt : pc->jf;
456 continue;
458 case BPF_JMP|BPF_JEQ|BPF_X:
459 pc += (A == X) ? pc->jt : pc->jf;
460 continue;
462 case BPF_JMP|BPF_JSET|BPF_X:
463 pc += (A & X) ? pc->jt : pc->jf;
464 continue;
466 case BPF_ALU|BPF_ADD|BPF_X:
467 A += X;
468 continue;
470 case BPF_ALU|BPF_SUB|BPF_X:
471 A -= X;
472 continue;
474 case BPF_ALU|BPF_MUL|BPF_X:
475 A *= X;
476 continue;
478 case BPF_ALU|BPF_DIV|BPF_X:
479 if (X == 0)
480 return 0;
481 A /= X;
482 continue;
484 case BPF_ALU|BPF_MOD|BPF_X:
485 if (X == 0)
486 return 0;
487 A %= X;
488 continue;
490 case BPF_ALU|BPF_AND|BPF_X:
491 A &= X;
492 continue;
494 case BPF_ALU|BPF_OR|BPF_X:
495 A |= X;
496 continue;
498 case BPF_ALU|BPF_XOR|BPF_X:
499 A ^= X;
500 continue;
502 case BPF_ALU|BPF_LSH|BPF_X:
503 A <<= X;
504 continue;
506 case BPF_ALU|BPF_RSH|BPF_X:
507 A >>= X;
508 continue;
510 case BPF_ALU|BPF_ADD|BPF_K:
511 A += pc->k;
512 continue;
514 case BPF_ALU|BPF_SUB|BPF_K:
515 A -= pc->k;
516 continue;
518 case BPF_ALU|BPF_MUL|BPF_K:
519 A *= pc->k;
520 continue;
522 case BPF_ALU|BPF_DIV|BPF_K:
523 A /= pc->k;
524 continue;
526 case BPF_ALU|BPF_MOD|BPF_K:
527 A %= pc->k;
528 continue;
530 case BPF_ALU|BPF_AND|BPF_K:
531 A &= pc->k;
532 continue;
534 case BPF_ALU|BPF_OR|BPF_K:
535 A |= pc->k;
536 continue;
538 case BPF_ALU|BPF_XOR|BPF_K:
539 A ^= pc->k;
540 continue;
542 case BPF_ALU|BPF_LSH|BPF_K:
543 A <<= pc->k;
544 continue;
546 case BPF_ALU|BPF_RSH|BPF_K:
547 A >>= pc->k;
548 continue;
550 case BPF_ALU|BPF_NEG:
551 A = -A;
552 continue;
554 case BPF_MISC|BPF_TAX:
555 X = A;
556 continue;
558 case BPF_MISC|BPF_TXA:
559 A = X;
560 continue;
562 case BPF_MISC|BPF_COP:
563 #ifdef _KERNEL
564 if (pc->k < bc->nfuncs) {
565 const bpf_copfunc_t fn = bc->copfuncs[pc->k];
566 A = fn(bc, args, A);
567 continue;
569 #endif
570 return 0;
572 case BPF_MISC|BPF_COPX:
573 #ifdef _KERNEL
574 if (X < bc->nfuncs) {
575 const bpf_copfunc_t fn = bc->copfuncs[X];
576 A = fn(bc, args, A);
577 continue;
579 #endif
580 return 0;
586 * Return true if the 'fcode' is a valid filter program.
587 * The constraints are that each jump be forward and to a valid
588 * code, that memory accesses are within valid ranges (to the
589 * extent that this can be checked statically; loads of packet
590 * data have to be, and are, also checked at run time), and that
591 * the code terminates with either an accept or reject.
593 * The kernel needs to be able to verify an application's filter code.
594 * Otherwise, a bogus program could easily crash the system.
597 #if defined(KERNEL) || defined(_KERNEL)
600 bpf_validate(const struct bpf_insn *f, int signed_len)
602 return bpf_validate_ext(NULL, f, signed_len);
606 bpf_validate_ext(const bpf_ctx_t *bc, const struct bpf_insn *f, int signed_len)
607 #else
609 bpf_validate(const struct bpf_insn *f, int signed_len)
610 #endif
612 u_int i, from, len, ok = 0;
613 const struct bpf_insn *p;
614 #if defined(KERNEL) || defined(_KERNEL)
615 bpf_memword_init_t *mem, invalid;
616 size_t size;
617 const size_t extwords = bc ? bc->extwords : 0;
618 const size_t memwords = extwords ? extwords : BPF_MEMWORDS;
619 const bpf_memword_init_t preinited = extwords ? bc->preinited : 0;
620 #else
621 const size_t memwords = BPF_MEMWORDS;
622 #endif
624 len = (u_int)signed_len;
625 if (len < 1)
626 return 0;
627 #if defined(KERNEL) || defined(_KERNEL)
628 if (len > BPF_MAXINSNS)
629 return 0;
630 #endif
631 if (f[len - 1].code != (BPF_RET|BPF_K) &&
632 f[len - 1].code != (BPF_RET|BPF_A)) {
633 return 0;
636 #if defined(KERNEL) || defined(_KERNEL)
637 /* Note: only the pre-initialised is valid on startup */
638 mem = kmem_zalloc(size = sizeof(*mem) * len, KM_SLEEP);
639 invalid = ~preinited;
640 #endif
642 for (i = 0; i < len; ++i) {
643 #if defined(KERNEL) || defined(_KERNEL)
644 /* blend in any invalid bits for current pc */
645 invalid |= mem[i];
646 #endif
647 p = &f[i];
648 switch (BPF_CLASS(p->code)) {
650 * Check that memory operations use valid addresses.
652 case BPF_LD:
653 case BPF_LDX:
654 switch (BPF_MODE(p->code)) {
655 case BPF_MEM:
657 * There's no maximum packet data size
658 * in userland. The runtime packet length
659 * check suffices.
661 #if defined(KERNEL) || defined(_KERNEL)
663 * More strict check with actual packet length
664 * is done runtime.
666 if (p->k >= memwords)
667 goto out;
668 /* check for current memory invalid */
669 if (invalid & BPF_MEMWORD_INIT(p->k))
670 goto out;
671 #endif
672 break;
673 case BPF_ABS:
674 case BPF_IND:
675 case BPF_MSH:
676 case BPF_IMM:
677 case BPF_LEN:
678 break;
679 default:
680 goto out;
682 break;
683 case BPF_ST:
684 case BPF_STX:
685 if (p->k >= memwords)
686 goto out;
687 #if defined(KERNEL) || defined(_KERNEL)
688 /* validate the memory word */
689 invalid &= ~BPF_MEMWORD_INIT(p->k);
690 #endif
691 break;
692 case BPF_ALU:
693 switch (BPF_OP(p->code)) {
694 case BPF_ADD:
695 case BPF_SUB:
696 case BPF_MUL:
697 case BPF_OR:
698 case BPF_XOR:
699 case BPF_AND:
700 case BPF_LSH:
701 case BPF_RSH:
702 case BPF_NEG:
703 break;
704 case BPF_DIV:
705 case BPF_MOD:
707 * Check for constant division by 0.
709 if (BPF_SRC(p->code) == BPF_K && p->k == 0)
710 goto out;
711 break;
712 default:
713 goto out;
715 break;
716 case BPF_JMP:
718 * Check that jumps are within the code block,
719 * and that unconditional branches don't go
720 * backwards as a result of an overflow.
721 * Unconditional branches have a 32-bit offset,
722 * so they could overflow; we check to make
723 * sure they don't. Conditional branches have
724 * an 8-bit offset, and the from address is <=
725 * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
726 * is sufficiently small that adding 255 to it
727 * won't overflow.
729 * We know that len is <= BPF_MAXINSNS, and we
730 * assume that BPF_MAXINSNS is < the maximum size
731 * of a u_int, so that i + 1 doesn't overflow.
733 * For userland, we don't know that the from
734 * or len are <= BPF_MAXINSNS, but we know that
735 * from <= len, and, except on a 64-bit system,
736 * it's unlikely that len, if it truly reflects
737 * the size of the program we've been handed,
738 * will be anywhere near the maximum size of
739 * a u_int. We also don't check for backward
740 * branches, as we currently support them in
741 * userland for the protochain operation.
743 from = i + 1;
744 switch (BPF_OP(p->code)) {
745 case BPF_JA:
746 if (from + p->k >= len)
747 goto out;
748 #if defined(KERNEL) || defined(_KERNEL)
749 if (from + p->k < from)
750 goto out;
752 * mark the currently invalid bits for the
753 * destination
755 mem[from + p->k] |= invalid;
756 invalid = 0;
757 #endif
758 break;
759 case BPF_JEQ:
760 case BPF_JGT:
761 case BPF_JGE:
762 case BPF_JSET:
763 if (from + p->jt >= len || from + p->jf >= len)
764 goto out;
765 #if defined(KERNEL) || defined(_KERNEL)
767 * mark the currently invalid bits for both
768 * possible jump destinations
770 mem[from + p->jt] |= invalid;
771 mem[from + p->jf] |= invalid;
772 invalid = 0;
773 #endif
774 break;
775 default:
776 goto out;
778 break;
779 case BPF_RET:
780 break;
781 case BPF_MISC:
782 switch (BPF_MISCOP(p->code)) {
783 case BPF_COP:
784 case BPF_COPX:
785 /* In-kernel COP use only. */
786 #if defined(KERNEL) || defined(_KERNEL)
787 if (bc == NULL || bc->copfuncs == NULL)
788 goto out;
789 if (BPF_MISCOP(p->code) == BPF_COP &&
790 p->k >= bc->nfuncs) {
791 goto out;
793 break;
794 #else
795 goto out;
796 #endif
797 default:
798 break;
800 break;
801 default:
802 goto out;
805 ok = 1;
806 out:
807 #if defined(KERNEL) || defined(_KERNEL)
808 kmem_free(mem, size);
809 #endif
810 return ok;