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