bpf_filter.c revision 1.66
1 /* $NetBSD: bpf_filter.c,v 1.66 2014/07/05 22:06:11 alnsn Exp $ */ 2 3 /*- 4 * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997 5 * The Regents of the University of California. All rights reserved. 6 * 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. 11 * 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. 23 * 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. 35 * 36 * @(#)bpf_filter.c 8.1 (Berkeley) 6/10/93 37 */ 38 39 #include <sys/cdefs.h> 40 __KERNEL_RCSID(0, "$NetBSD: bpf_filter.c,v 1.66 2014/07/05 22:06:11 alnsn Exp $"); 41 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 48 49 #include <sys/param.h> 50 #include <sys/time.h> 51 #include <sys/kmem.h> 52 #include <sys/endian.h> 53 54 #define __BPF_PRIVATE 55 #include <net/bpf.h> 56 57 #ifdef _KERNEL 58 59 bpf_ctx_t * 60 bpf_create(void) 61 { 62 return kmem_zalloc(sizeof(bpf_ctx_t), KM_SLEEP); 63 } 64 65 void 66 bpf_destroy(bpf_ctx_t *bc) 67 { 68 kmem_free(bc, sizeof(bpf_ctx_t)); 69 } 70 71 int 72 bpf_set_cop(bpf_ctx_t *bc, const bpf_copfunc_t *funcs, size_t n) 73 { 74 bc->copfuncs = funcs; 75 bc->nfuncs = n; 76 return 0; 77 } 78 79 int 80 bpf_set_extmem(bpf_ctx_t *bc, size_t nwords, bpf_memword_init_t preinited) 81 { 82 if (nwords > BPF_MAX_MEMWORDS || (preinited >> nwords) != 0) { 83 return EINVAL; 84 } 85 bc->extwords = nwords; 86 bc->preinited = preinited; 87 return 0; 88 } 89 90 #endif 91 92 #define EXTRACT_SHORT(p) be16dec(p) 93 #define EXTRACT_LONG(p) be32dec(p) 94 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; \ 106 } \ 107 } 108 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 *); 112 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)) 116 117 uint32_t 118 m_xword(const struct mbuf *m, uint32_t k, int *err) 119 { 120 int len; 121 u_char *cp, *np; 122 struct mbuf *m0; 123 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); 130 } 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 *); 136 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]; 144 } 145 } 146 147 uint32_t 148 m_xhalf(const struct mbuf *m, uint32_t k, int *err) 149 { 150 int len; 151 u_char *cp; 152 struct mbuf *m0; 153 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); 160 } 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]; 166 } 167 168 uint32_t 169 m_xbyte(const struct mbuf *m, uint32_t k, int *err) 170 { 171 int len; 172 173 *err = 1; 174 MINDEX(len, m, k); 175 *err = 0; 176 return mtod(m, u_char *)[k]; 177 } 178 #else /* _KERNEL */ 179 #include <stdlib.h> 180 #endif /* !_KERNEL */ 181 182 #include <net/bpf.h> 183 184 /* 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 188 */ 189 #ifdef _KERNEL 190 191 u_int 192 bpf_filter(const struct bpf_insn *pc, const u_char *p, u_int wirelen, 193 u_int buflen) 194 { 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 202 }; 203 204 return bpf_filter_ext(NULL, pc, &args); 205 } 206 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 214 { 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 224 }; 225 bpf_args_t * const args = &args_store; 226 #else 227 const uint8_t * const p = args->pkt; 228 #endif 229 if (pc == 0) { 230 /* 231 * No filter means accept all. 232 */ 233 return (u_int)-1; 234 } 235 236 /* 237 * Note: safe to leave memwords uninitialised, as the validation 238 * step ensures that it will not be read, if it was not written. 239 */ 240 A = 0; 241 X = 0; 242 --pc; 243 244 for (;;) { 245 ++pc; 246 switch (pc->code) { 247 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; 257 258 case BPF_RET|BPF_A: 259 return (u_int)A; 260 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; 267 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 277 } 278 A = EXTRACT_LONG(&p[k]); 279 continue; 280 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; 287 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 297 } 298 A = EXTRACT_SHORT(&p[k]); 299 continue; 300 301 case BPF_LD|BPF_B|BPF_ABS: 302 k = pc->k; 303 if (k >= args->buflen) { 304 #ifdef _KERNEL 305 int merr; 306 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 316 } 317 A = p[k]; 318 continue; 319 320 case BPF_LD|BPF_W|BPF_LEN: 321 A = args->wirelen; 322 continue; 323 324 case BPF_LDX|BPF_W|BPF_LEN: 325 X = args->wirelen; 326 continue; 327 328 case BPF_LD|BPF_W|BPF_IND: 329 k = X + pc->k; 330 if (pc->k > args->buflen || 331 X > args->buflen - pc->k || 332 sizeof(int32_t) > args->buflen - k) { 333 #ifdef _KERNEL 334 int merr; 335 336 if (args->buflen != 0) 337 return 0; 338 A = xword(args->pkt, k, &merr); 339 if (merr != 0) 340 return 0; 341 continue; 342 #else 343 return 0; 344 #endif 345 } 346 A = EXTRACT_LONG(&p[k]); 347 continue; 348 349 case BPF_LD|BPF_H|BPF_IND: 350 k = X + pc->k; 351 if (pc->k > args->buflen || 352 X > args->buflen - pc->k || 353 sizeof(int16_t) > args->buflen - k) { 354 #ifdef _KERNEL 355 int merr; 356 357 if (args->buflen != 0) 358 return 0; 359 A = xhalf(args->pkt, k, &merr); 360 if (merr != 0) 361 return 0; 362 continue; 363 #else 364 return 0; 365 #endif 366 } 367 A = EXTRACT_SHORT(&p[k]); 368 continue; 369 370 case BPF_LD|BPF_B|BPF_IND: 371 k = X + pc->k; 372 if (pc->k >= args->buflen || 373 X >= args->buflen - pc->k) { 374 #ifdef _KERNEL 375 int merr; 376 377 if (args->buflen != 0) 378 return 0; 379 A = xbyte(args->pkt, k, &merr); 380 if (merr != 0) 381 return 0; 382 continue; 383 #else 384 return 0; 385 #endif 386 } 387 A = p[k]; 388 continue; 389 390 case BPF_LDX|BPF_MSH|BPF_B: 391 k = pc->k; 392 if (k >= args->buflen) { 393 #ifdef _KERNEL 394 int merr; 395 396 if (args->buflen != 0) 397 return 0; 398 X = (xbyte(args->pkt, k, &merr) & 0xf) << 2; 399 if (merr != 0) 400 return 0; 401 continue; 402 #else 403 return 0; 404 #endif 405 } 406 X = (p[pc->k] & 0xf) << 2; 407 continue; 408 409 case BPF_LD|BPF_IMM: 410 A = pc->k; 411 continue; 412 413 case BPF_LDX|BPF_IMM: 414 X = pc->k; 415 continue; 416 417 case BPF_LD|BPF_MEM: 418 A = args->mem[pc->k]; 419 continue; 420 421 case BPF_LDX|BPF_MEM: 422 X = args->mem[pc->k]; 423 continue; 424 425 case BPF_ST: 426 args->mem[pc->k] = A; 427 continue; 428 429 case BPF_STX: 430 args->mem[pc->k] = X; 431 continue; 432 433 case BPF_JMP|BPF_JA: 434 pc += pc->k; 435 continue; 436 437 case BPF_JMP|BPF_JGT|BPF_K: 438 pc += (A > pc->k) ? pc->jt : pc->jf; 439 continue; 440 441 case BPF_JMP|BPF_JGE|BPF_K: 442 pc += (A >= pc->k) ? pc->jt : pc->jf; 443 continue; 444 445 case BPF_JMP|BPF_JEQ|BPF_K: 446 pc += (A == pc->k) ? pc->jt : pc->jf; 447 continue; 448 449 case BPF_JMP|BPF_JSET|BPF_K: 450 pc += (A & pc->k) ? pc->jt : pc->jf; 451 continue; 452 453 case BPF_JMP|BPF_JGT|BPF_X: 454 pc += (A > X) ? pc->jt : pc->jf; 455 continue; 456 457 case BPF_JMP|BPF_JGE|BPF_X: 458 pc += (A >= X) ? pc->jt : pc->jf; 459 continue; 460 461 case BPF_JMP|BPF_JEQ|BPF_X: 462 pc += (A == X) ? pc->jt : pc->jf; 463 continue; 464 465 case BPF_JMP|BPF_JSET|BPF_X: 466 pc += (A & X) ? pc->jt : pc->jf; 467 continue; 468 469 case BPF_ALU|BPF_ADD|BPF_X: 470 A += X; 471 continue; 472 473 case BPF_ALU|BPF_SUB|BPF_X: 474 A -= X; 475 continue; 476 477 case BPF_ALU|BPF_MUL|BPF_X: 478 A *= X; 479 continue; 480 481 case BPF_ALU|BPF_DIV|BPF_X: 482 if (X == 0) 483 return 0; 484 A /= X; 485 continue; 486 487 case BPF_ALU|BPF_AND|BPF_X: 488 A &= X; 489 continue; 490 491 case BPF_ALU|BPF_OR|BPF_X: 492 A |= X; 493 continue; 494 495 case BPF_ALU|BPF_LSH|BPF_X: 496 A <<= X; 497 continue; 498 499 case BPF_ALU|BPF_RSH|BPF_X: 500 A >>= X; 501 continue; 502 503 case BPF_ALU|BPF_ADD|BPF_K: 504 A += pc->k; 505 continue; 506 507 case BPF_ALU|BPF_SUB|BPF_K: 508 A -= pc->k; 509 continue; 510 511 case BPF_ALU|BPF_MUL|BPF_K: 512 A *= pc->k; 513 continue; 514 515 case BPF_ALU|BPF_DIV|BPF_K: 516 A /= pc->k; 517 continue; 518 519 case BPF_ALU|BPF_AND|BPF_K: 520 A &= pc->k; 521 continue; 522 523 case BPF_ALU|BPF_OR|BPF_K: 524 A |= pc->k; 525 continue; 526 527 case BPF_ALU|BPF_LSH|BPF_K: 528 A <<= pc->k; 529 continue; 530 531 case BPF_ALU|BPF_RSH|BPF_K: 532 A >>= pc->k; 533 continue; 534 535 case BPF_ALU|BPF_NEG: 536 A = -A; 537 continue; 538 539 case BPF_MISC|BPF_TAX: 540 X = A; 541 continue; 542 543 case BPF_MISC|BPF_TXA: 544 A = X; 545 continue; 546 547 case BPF_MISC|BPF_COP: 548 #ifdef _KERNEL 549 if (pc->k < bc->nfuncs) { 550 const bpf_copfunc_t fn = bc->copfuncs[pc->k]; 551 A = fn(bc, args, A); 552 continue; 553 } 554 #endif 555 return 0; 556 557 case BPF_MISC|BPF_COPX: 558 #ifdef _KERNEL 559 if (X < bc->nfuncs) { 560 const bpf_copfunc_t fn = bc->copfuncs[X]; 561 A = fn(bc, args, A); 562 continue; 563 } 564 #endif 565 return 0; 566 } 567 } 568 } 569 570 /* 571 * Return true if the 'fcode' is a valid filter program. 572 * The constraints are that each jump be forward and to a valid 573 * code, that memory accesses are within valid ranges (to the 574 * extent that this can be checked statically; loads of packet 575 * data have to be, and are, also checked at run time), and that 576 * the code terminates with either an accept or reject. 577 * 578 * The kernel needs to be able to verify an application's filter code. 579 * Otherwise, a bogus program could easily crash the system. 580 */ 581 582 #if defined(KERNEL) || defined(_KERNEL) 583 584 int 585 bpf_validate(const struct bpf_insn *f, int signed_len) 586 { 587 return bpf_validate_ext(NULL, f, signed_len); 588 } 589 590 int 591 bpf_validate_ext(const bpf_ctx_t *bc, const struct bpf_insn *f, int signed_len) 592 #else 593 int 594 bpf_validate(const struct bpf_insn *f, int signed_len) 595 #endif 596 { 597 u_int i, from, len, ok = 0; 598 const struct bpf_insn *p; 599 #if defined(KERNEL) || defined(_KERNEL) 600 bpf_memword_init_t *mem, invalid; 601 size_t size; 602 const size_t extwords = bc ? bc->extwords : 0; 603 const size_t memwords = extwords ? extwords : BPF_MEMWORDS; 604 const bpf_memword_init_t preinited = extwords ? bc->preinited : 0; 605 #else 606 const size_t memwords = BPF_MEMWORDS; 607 #endif 608 609 len = (u_int)signed_len; 610 if (len < 1) 611 return 0; 612 #if defined(KERNEL) || defined(_KERNEL) 613 if (len > BPF_MAXINSNS) 614 return 0; 615 #endif 616 if (BPF_CLASS(f[len - 1].code) != BPF_RET) 617 return 0; 618 619 #if defined(KERNEL) || defined(_KERNEL) 620 /* Note: only the pre-initialised is valid on startup */ 621 mem = kmem_zalloc(size = sizeof(*mem) * len, KM_SLEEP); 622 invalid = ~preinited; 623 #endif 624 625 for (i = 0; i < len; ++i) { 626 #if defined(KERNEL) || defined(_KERNEL) 627 /* blend in any invalid bits for current pc */ 628 invalid |= mem[i]; 629 #endif 630 p = &f[i]; 631 switch (BPF_CLASS(p->code)) { 632 /* 633 * Check that memory operations use valid addresses. 634 */ 635 case BPF_LD: 636 case BPF_LDX: 637 switch (BPF_MODE(p->code)) { 638 case BPF_MEM: 639 /* 640 * There's no maximum packet data size 641 * in userland. The runtime packet length 642 * check suffices. 643 */ 644 #if defined(KERNEL) || defined(_KERNEL) 645 /* 646 * More strict check with actual packet length 647 * is done runtime. 648 */ 649 if (p->k >= memwords) 650 goto out; 651 /* check for current memory invalid */ 652 if (invalid & BPF_MEMWORD_INIT(p->k)) 653 goto out; 654 #endif 655 break; 656 case BPF_ABS: 657 case BPF_IND: 658 case BPF_MSH: 659 case BPF_IMM: 660 case BPF_LEN: 661 break; 662 default: 663 goto out; 664 } 665 break; 666 case BPF_ST: 667 case BPF_STX: 668 if (p->k >= memwords) 669 goto out; 670 #if defined(KERNEL) || defined(_KERNEL) 671 /* validate the memory word */ 672 invalid &= ~BPF_MEMWORD_INIT(p->k); 673 #endif 674 break; 675 case BPF_ALU: 676 switch (BPF_OP(p->code)) { 677 case BPF_ADD: 678 case BPF_SUB: 679 case BPF_MUL: 680 case BPF_OR: 681 case BPF_AND: 682 case BPF_LSH: 683 case BPF_RSH: 684 case BPF_NEG: 685 break; 686 case BPF_DIV: 687 /* 688 * Check for constant division by 0. 689 */ 690 if (BPF_SRC(p->code) == BPF_K && p->k == 0) 691 goto out; 692 break; 693 default: 694 goto out; 695 } 696 break; 697 case BPF_JMP: 698 /* 699 * Check that jumps are within the code block, 700 * and that unconditional branches don't go 701 * backwards as a result of an overflow. 702 * Unconditional branches have a 32-bit offset, 703 * so they could overflow; we check to make 704 * sure they don't. Conditional branches have 705 * an 8-bit offset, and the from address is <= 706 * BPF_MAXINSNS, and we assume that BPF_MAXINSNS 707 * is sufficiently small that adding 255 to it 708 * won't overflow. 709 * 710 * We know that len is <= BPF_MAXINSNS, and we 711 * assume that BPF_MAXINSNS is < the maximum size 712 * of a u_int, so that i + 1 doesn't overflow. 713 * 714 * For userland, we don't know that the from 715 * or len are <= BPF_MAXINSNS, but we know that 716 * from <= len, and, except on a 64-bit system, 717 * it's unlikely that len, if it truly reflects 718 * the size of the program we've been handed, 719 * will be anywhere near the maximum size of 720 * a u_int. We also don't check for backward 721 * branches, as we currently support them in 722 * userland for the protochain operation. 723 */ 724 from = i + 1; 725 switch (BPF_OP(p->code)) { 726 case BPF_JA: 727 if (from + p->k >= len) 728 goto out; 729 #if defined(KERNEL) || defined(_KERNEL) 730 if (from + p->k < from) 731 goto out; 732 /* 733 * mark the currently invalid bits for the 734 * destination 735 */ 736 mem[from + p->k] |= invalid; 737 invalid = 0; 738 #endif 739 break; 740 case BPF_JEQ: 741 case BPF_JGT: 742 case BPF_JGE: 743 case BPF_JSET: 744 if (from + p->jt >= len || from + p->jf >= len) 745 goto out; 746 #if defined(KERNEL) || defined(_KERNEL) 747 /* 748 * mark the currently invalid bits for both 749 * possible jump destinations 750 */ 751 mem[from + p->jt] |= invalid; 752 mem[from + p->jf] |= invalid; 753 invalid = 0; 754 #endif 755 break; 756 default: 757 goto out; 758 } 759 break; 760 case BPF_RET: 761 break; 762 case BPF_MISC: 763 switch (BPF_MISCOP(p->code)) { 764 case BPF_COP: 765 case BPF_COPX: 766 /* In-kernel COP use only. */ 767 #if defined(KERNEL) || defined(_KERNEL) 768 if (bc == NULL || bc->copfuncs == NULL) 769 goto out; 770 if (BPF_MISCOP(p->code) == BPF_COP && 771 p->k >= bc->nfuncs) { 772 goto out; 773 } 774 break; 775 #else 776 goto out; 777 #endif 778 default: 779 break; 780 } 781 break; 782 default: 783 goto out; 784 } 785 } 786 ok = 1; 787 out: 788 #if defined(KERNEL) || defined(_KERNEL) 789 kmem_free(mem, size); 790 #endif 791 return ok; 792 } 793
Indexes created Tue Sep 30 06:09:59 GMT 2025