1 /* 2 * Copyright (c) 1990, 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from the Stanford/CMU enet packet filter, 6 * (net/enet.c) distributed as part of 4.3BSD, and code contributed 7 * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence 8 * Berkeley Laboratory. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 * 38 * @(#)bpf_filter.c 8.1 (Berkeley) 6/10/93 39 * 40 * $FreeBSD: src/sys/net/bpf_filter.c,v 1.17 1999/12/29 04:38:31 peter Exp $ 41 * $DragonFly: src/sys/net/bpf_filter.c,v 1.4 2003/08/26 20:49:47 rob Exp $ 42 */ 43 44 #include <sys/param.h> 45 46 #ifdef sun 47 #include <netinet/in.h> 48 #endif 49 50 #if defined(sparc) || defined(mips) || defined(ibm032) || defined(__alpha__) 51 #define BPF_ALIGN 52 #endif 53 54 #ifndef BPF_ALIGN 55 #define EXTRACT_SHORT(p) ((u_int16_t)ntohs(*(u_int16_t *)p)) 56 #define EXTRACT_LONG(p) (ntohl(*(u_int32_t *)p)) 57 #else 58 #define EXTRACT_SHORT(p)\ 59 ((u_int16_t)\ 60 ((u_int16_t)*((u_char *)p+0)<<8|\ 61 (u_int16_t)*((u_char *)p+1)<<0)) 62 #define EXTRACT_LONG(p)\ 63 ((u_int32_t)*((u_char *)p+0)<<24|\ 64 (u_int32_t)*((u_char *)p+1)<<16|\ 65 (u_int32_t)*((u_char *)p+2)<<8|\ 66 (u_int32_t)*((u_char *)p+3)<<0) 67 #endif 68 69 #ifdef _KERNEL 70 #include <sys/mbuf.h> 71 #endif 72 #include <net/bpf.h> 73 #ifdef _KERNEL 74 #define MINDEX(m, k) \ 75 { \ 76 int len = m->m_len; \ 77 \ 78 while (k >= len) { \ 79 k -= len; \ 80 m = m->m_next; \ 81 if (m == 0) \ 82 return 0; \ 83 len = m->m_len; \ 84 } \ 85 } 86 87 static u_int16_t m_xhalf (struct mbuf *m, bpf_u_int32 k, int *err); 88 static u_int32_t m_xword (struct mbuf *m, bpf_u_int32 k, int *err); 89 90 static u_int32_t 91 m_xword(m, k, err) 92 struct mbuf *m; 93 bpf_u_int32 k; 94 int *err; 95 { 96 size_t len; 97 u_char *cp, *np; 98 struct mbuf *m0; 99 100 len = m->m_len; 101 while (k >= len) { 102 k -= len; 103 m = m->m_next; 104 if (m == 0) 105 goto bad; 106 len = m->m_len; 107 } 108 cp = mtod(m, u_char *) + k; 109 if (len - k >= 4) { 110 *err = 0; 111 return EXTRACT_LONG(cp); 112 } 113 m0 = m->m_next; 114 if (m0 == 0 || m0->m_len + len - k < 4) 115 goto bad; 116 *err = 0; 117 np = mtod(m0, u_char *); 118 switch (len - k) { 119 120 case 1: 121 return 122 ((u_int32_t)cp[0] << 24) | 123 ((u_int32_t)np[0] << 16) | 124 ((u_int32_t)np[1] << 8) | 125 (u_int32_t)np[2]; 126 127 case 2: 128 return 129 ((u_int32_t)cp[0] << 24) | 130 ((u_int32_t)cp[1] << 16) | 131 ((u_int32_t)np[0] << 8) | 132 (u_int32_t)np[1]; 133 134 default: 135 return 136 ((u_int32_t)cp[0] << 24) | 137 ((u_int32_t)cp[1] << 16) | 138 ((u_int32_t)cp[2] << 8) | 139 (u_int32_t)np[0]; 140 } 141 bad: 142 *err = 1; 143 return 0; 144 } 145 146 static u_int16_t 147 m_xhalf(m, k, err) 148 struct mbuf *m; 149 bpf_u_int32 k; 150 int *err; 151 { 152 size_t len; 153 u_char *cp; 154 struct mbuf *m0; 155 156 len = m->m_len; 157 while (k >= len) { 158 k -= len; 159 m = m->m_next; 160 if (m == 0) 161 goto bad; 162 len = m->m_len; 163 } 164 cp = mtod(m, u_char *) + k; 165 if (len - k >= 2) { 166 *err = 0; 167 return EXTRACT_SHORT(cp); 168 } 169 m0 = m->m_next; 170 if (m0 == 0) 171 goto bad; 172 *err = 0; 173 return (cp[0] << 8) | mtod(m0, u_char *)[0]; 174 bad: 175 *err = 1; 176 return 0; 177 } 178 #endif 179 180 /* 181 * Execute the filter program starting at pc on the packet p 182 * wirelen is the length of the original packet 183 * buflen is the amount of data present 184 */ 185 u_int 186 bpf_filter(pc, p, wirelen, buflen) 187 const struct bpf_insn *pc; 188 u_char *p; 189 u_int wirelen; 190 u_int buflen; 191 { 192 u_int32_t A = 0, X = 0; 193 bpf_u_int32 k; 194 int32_t mem[BPF_MEMWORDS]; 195 196 if (pc == 0) 197 /* 198 * No filter means accept all. 199 */ 200 return (u_int)-1; 201 202 --pc; 203 while (1) { 204 ++pc; 205 switch (pc->code) { 206 207 default: 208 #ifdef _KERNEL 209 return 0; 210 #else 211 abort(); 212 #endif 213 case BPF_RET|BPF_K: 214 return (u_int)pc->k; 215 216 case BPF_RET|BPF_A: 217 return (u_int)A; 218 219 case BPF_LD|BPF_W|BPF_ABS: 220 k = pc->k; 221 if (k > buflen || sizeof(int32_t) > buflen - k) { 222 #ifdef _KERNEL 223 int merr; 224 225 if (buflen != 0) 226 return 0; 227 A = m_xword((struct mbuf *)p, k, &merr); 228 if (merr != 0) 229 return 0; 230 continue; 231 #else 232 return 0; 233 #endif 234 } 235 #ifdef BPF_ALIGN 236 if (((intptr_t)(p + k) & 3) != 0) 237 A = EXTRACT_LONG(&p[k]); 238 else 239 #endif 240 A = ntohl(*(int32_t *)(p + k)); 241 continue; 242 243 case BPF_LD|BPF_H|BPF_ABS: 244 k = pc->k; 245 if (k > buflen || sizeof(int16_t) > buflen - k) { 246 #ifdef _KERNEL 247 int merr; 248 249 if (buflen != 0) 250 return 0; 251 A = m_xhalf((struct mbuf *)p, k, &merr); 252 continue; 253 #else 254 return 0; 255 #endif 256 } 257 A = EXTRACT_SHORT(&p[k]); 258 continue; 259 260 case BPF_LD|BPF_B|BPF_ABS: 261 k = pc->k; 262 if (k >= buflen) { 263 #ifdef _KERNEL 264 struct mbuf *m; 265 266 if (buflen != 0) 267 return 0; 268 m = (struct mbuf *)p; 269 MINDEX(m, k); 270 A = mtod(m, u_char *)[k]; 271 continue; 272 #else 273 return 0; 274 #endif 275 } 276 A = p[k]; 277 continue; 278 279 case BPF_LD|BPF_W|BPF_LEN: 280 A = wirelen; 281 continue; 282 283 case BPF_LDX|BPF_W|BPF_LEN: 284 X = wirelen; 285 continue; 286 287 case BPF_LD|BPF_W|BPF_IND: 288 k = X + pc->k; 289 if (pc->k > buflen || X > buflen - pc->k || 290 sizeof(int32_t) > buflen - k) { 291 #ifdef _KERNEL 292 int merr; 293 294 if (buflen != 0) 295 return 0; 296 A = m_xword((struct mbuf *)p, k, &merr); 297 if (merr != 0) 298 return 0; 299 continue; 300 #else 301 return 0; 302 #endif 303 } 304 #ifdef BPF_ALIGN 305 if (((intptr_t)(p + k) & 3) != 0) 306 A = EXTRACT_LONG(&p[k]); 307 else 308 #endif 309 A = ntohl(*(int32_t *)(p + k)); 310 continue; 311 312 case BPF_LD|BPF_H|BPF_IND: 313 k = X + pc->k; 314 if (X > buflen || pc->k > buflen - X || 315 sizeof(int16_t) > buflen - k) { 316 #ifdef _KERNEL 317 int merr; 318 319 if (buflen != 0) 320 return 0; 321 A = m_xhalf((struct mbuf *)p, k, &merr); 322 if (merr != 0) 323 return 0; 324 continue; 325 #else 326 return 0; 327 #endif 328 } 329 A = EXTRACT_SHORT(&p[k]); 330 continue; 331 332 case BPF_LD|BPF_B|BPF_IND: 333 k = X + pc->k; 334 if (pc->k >= buflen || X >= buflen - pc->k) { 335 #ifdef _KERNEL 336 struct mbuf *m; 337 338 if (buflen != 0) 339 return 0; 340 m = (struct mbuf *)p; 341 MINDEX(m, k); 342 A = mtod(m, char *)[k]; 343 continue; 344 #else 345 return 0; 346 #endif 347 } 348 A = p[k]; 349 continue; 350 351 case BPF_LDX|BPF_MSH|BPF_B: 352 k = pc->k; 353 if (k >= buflen) { 354 #ifdef _KERNEL 355 struct mbuf *m; 356 357 if (buflen != 0) 358 return 0; 359 m = (struct mbuf *)p; 360 MINDEX(m, k); 361 X = (mtod(m, char *)[k] & 0xf) << 2; 362 continue; 363 #else 364 return 0; 365 #endif 366 } 367 X = (p[pc->k] & 0xf) << 2; 368 continue; 369 370 case BPF_LD|BPF_IMM: 371 A = pc->k; 372 continue; 373 374 case BPF_LDX|BPF_IMM: 375 X = pc->k; 376 continue; 377 378 case BPF_LD|BPF_MEM: 379 A = mem[pc->k]; 380 continue; 381 382 case BPF_LDX|BPF_MEM: 383 X = mem[pc->k]; 384 continue; 385 386 case BPF_ST: 387 mem[pc->k] = A; 388 continue; 389 390 case BPF_STX: 391 mem[pc->k] = X; 392 continue; 393 394 case BPF_JMP|BPF_JA: 395 pc += pc->k; 396 continue; 397 398 case BPF_JMP|BPF_JGT|BPF_K: 399 pc += (A > pc->k) ? pc->jt : pc->jf; 400 continue; 401 402 case BPF_JMP|BPF_JGE|BPF_K: 403 pc += (A >= pc->k) ? pc->jt : pc->jf; 404 continue; 405 406 case BPF_JMP|BPF_JEQ|BPF_K: 407 pc += (A == pc->k) ? pc->jt : pc->jf; 408 continue; 409 410 case BPF_JMP|BPF_JSET|BPF_K: 411 pc += (A & pc->k) ? pc->jt : pc->jf; 412 continue; 413 414 case BPF_JMP|BPF_JGT|BPF_X: 415 pc += (A > X) ? pc->jt : pc->jf; 416 continue; 417 418 case BPF_JMP|BPF_JGE|BPF_X: 419 pc += (A >= X) ? pc->jt : pc->jf; 420 continue; 421 422 case BPF_JMP|BPF_JEQ|BPF_X: 423 pc += (A == X) ? pc->jt : pc->jf; 424 continue; 425 426 case BPF_JMP|BPF_JSET|BPF_X: 427 pc += (A & X) ? pc->jt : pc->jf; 428 continue; 429 430 case BPF_ALU|BPF_ADD|BPF_X: 431 A += X; 432 continue; 433 434 case BPF_ALU|BPF_SUB|BPF_X: 435 A -= X; 436 continue; 437 438 case BPF_ALU|BPF_MUL|BPF_X: 439 A *= X; 440 continue; 441 442 case BPF_ALU|BPF_DIV|BPF_X: 443 if (X == 0) 444 return 0; 445 A /= X; 446 continue; 447 448 case BPF_ALU|BPF_AND|BPF_X: 449 A &= X; 450 continue; 451 452 case BPF_ALU|BPF_OR|BPF_X: 453 A |= X; 454 continue; 455 456 case BPF_ALU|BPF_LSH|BPF_X: 457 A <<= X; 458 continue; 459 460 case BPF_ALU|BPF_RSH|BPF_X: 461 A >>= X; 462 continue; 463 464 case BPF_ALU|BPF_ADD|BPF_K: 465 A += pc->k; 466 continue; 467 468 case BPF_ALU|BPF_SUB|BPF_K: 469 A -= pc->k; 470 continue; 471 472 case BPF_ALU|BPF_MUL|BPF_K: 473 A *= pc->k; 474 continue; 475 476 case BPF_ALU|BPF_DIV|BPF_K: 477 A /= pc->k; 478 continue; 479 480 case BPF_ALU|BPF_AND|BPF_K: 481 A &= pc->k; 482 continue; 483 484 case BPF_ALU|BPF_OR|BPF_K: 485 A |= pc->k; 486 continue; 487 488 case BPF_ALU|BPF_LSH|BPF_K: 489 A <<= pc->k; 490 continue; 491 492 case BPF_ALU|BPF_RSH|BPF_K: 493 A >>= pc->k; 494 continue; 495 496 case BPF_ALU|BPF_NEG: 497 A = -A; 498 continue; 499 500 case BPF_MISC|BPF_TAX: 501 X = A; 502 continue; 503 504 case BPF_MISC|BPF_TXA: 505 A = X; 506 continue; 507 } 508 } 509 } 510 511 #ifdef _KERNEL 512 /* 513 * Return true if the 'fcode' is a valid filter program. 514 * The constraints are that each jump be forward and to a valid 515 * code. The code must terminate with either an accept or reject. 516 * 517 * The kernel needs to be able to verify an application's filter code. 518 * Otherwise, a bogus program could easily crash the system. 519 */ 520 int 521 bpf_validate(f, len) 522 const struct bpf_insn *f; 523 int len; 524 { 525 int i; 526 const struct bpf_insn *p; 527 528 for (i = 0; i < len; ++i) { 529 /* 530 * Check that that jumps are forward, and within 531 * the code block. 532 */ 533 p = &f[i]; 534 if (BPF_CLASS(p->code) == BPF_JMP) { 535 int from = i + 1; 536 537 if (BPF_OP(p->code) == BPF_JA) { 538 if (from >= len || p->k >= len - from) 539 return 0; 540 } 541 else if (from >= len || p->jt >= len - from || 542 p->jf >= len - from) 543 return 0; 544 } 545 /* 546 * Check that memory operations use valid addresses. 547 */ 548 if ((BPF_CLASS(p->code) == BPF_ST || 549 (BPF_CLASS(p->code) == BPF_LD && 550 (p->code & 0xe0) == BPF_MEM)) && 551 p->k >= BPF_MEMWORDS) 552 return 0; 553 /* 554 * Check for constant division by 0. 555 */ 556 if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0) 557 return 0; 558 } 559 return BPF_CLASS(f[len - 1].code) == BPF_RET; 560 } 561 #endif 562