FreeBSD/Linux Kernel Cross Reference
sys/net/bpf_filter.c
1 /* $NetBSD: bpf_filter.c,v 1.35.4.2 2011/03/20 21:28:08 bouyer 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.35.4.2 2011/03/20 21:28:08 bouyer 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 EXTRACT_SHORT(p) be16dec(p)
55 #define EXTRACT_LONG(p) be32dec(p)
56
57 #ifdef _KERNEL
58 #include <sys/mbuf.h>
59 #define MINDEX(len, m, k) \
60 { \
61 len = m->m_len; \
62 while (k >= len) { \
63 k -= len; \
64 m = m->m_next; \
65 if (m == 0) \
66 return 0; \
67 len = m->m_len; \
68 } \
69 }
70
71 static int m_xword (struct mbuf *, uint32_t, int *);
72 static int m_xhalf (struct mbuf *, uint32_t, int *);
73
74 static int
75 m_xword(struct mbuf *m, uint32_t k, int *err)
76 {
77 int len;
78 u_char *cp, *np;
79 struct mbuf *m0;
80
81 *err = 1;
82 MINDEX(len, m, k);
83 cp = mtod(m, u_char *) + k;
84 if (len >= k + 4) {
85 *err = 0;
86 return EXTRACT_LONG(cp);
87 }
88 m0 = m->m_next;
89 if (m0 == 0 || m0->m_len + len - k < 4)
90 return 0;
91 *err = 0;
92 np = mtod(m0, u_char *);
93 switch (len - k) {
94
95 case 1:
96 return (cp[0] << 24) | (np[0] << 16) | (np[1] << 8) | np[2];
97
98 case 2:
99 return (cp[0] << 24) | (cp[1] << 16) | (np[0] << 8) | np[1];
100
101 default:
102 return (cp[0] << 24) | (cp[1] << 16) | (cp[2] << 8) | np[0];
103 }
104 }
105
106 static int
107 m_xhalf(struct mbuf *m, uint32_t k, int *err)
108 {
109 int len;
110 u_char *cp;
111 struct mbuf *m0;
112
113 *err = 1;
114 MINDEX(len, m, k);
115 cp = mtod(m, u_char *) + k;
116 if (len >= k + 2) {
117 *err = 0;
118 return EXTRACT_SHORT(cp);
119 }
120 m0 = m->m_next;
121 if (m0 == 0)
122 return 0;
123 *err = 0;
124 return (cp[0] << 8) | mtod(m0, u_char *)[0];
125 }
126 #else /* _KERNEL */
127 #include <stdlib.h>
128 #endif /* !_KERNEL */
129
130 #include <net/bpf.h>
131
132 /*
133 * Execute the filter program starting at pc on the packet p
134 * wirelen is the length of the original packet
135 * buflen is the amount of data present
136 */
137 u_int
138 bpf_filter(struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
139 {
140 uint32_t A, X, k;
141 uint32_t mem[BPF_MEMWORDS];
142
143 if (pc == 0)
144 /*
145 * No filter means accept all.
146 */
147 return (u_int)-1;
148 A = 0;
149 X = 0;
150 --pc;
151 for (;;) {
152 ++pc;
153 switch (pc->code) {
154
155 default:
156 #ifdef _KERNEL
157 return 0;
158 #else
159 abort();
160 /*NOTREACHED*/
161 #endif
162 case BPF_RET|BPF_K:
163 return (u_int)pc->k;
164
165 case BPF_RET|BPF_A:
166 return (u_int)A;
167
168 case BPF_LD|BPF_W|BPF_ABS:
169 k = pc->k;
170 if (k + sizeof(int32_t) > buflen) {
171 #ifdef _KERNEL
172 int merr = 0; /* XXX: GCC */
173
174 if (buflen != 0)
175 return 0;
176 A = m_xword((struct mbuf *)p, k, &merr);
177 if (merr != 0)
178 return 0;
179 continue;
180 #else
181 return 0;
182 #endif
183 }
184 A = EXTRACT_LONG(&p[k]);
185 continue;
186
187 case BPF_LD|BPF_H|BPF_ABS:
188 k = pc->k;
189 if (k + sizeof(int16_t) > buflen) {
190 #ifdef _KERNEL
191 int merr;
192
193 if (buflen != 0)
194 return 0;
195 A = m_xhalf((struct mbuf *)p, k, &merr);
196 if (merr != 0)
197 return 0;
198 continue;
199 #else
200 return 0;
201 #endif
202 }
203 A = EXTRACT_SHORT(&p[k]);
204 continue;
205
206 case BPF_LD|BPF_B|BPF_ABS:
207 k = pc->k;
208 if (k >= buflen) {
209 #ifdef _KERNEL
210 struct mbuf *m;
211 int len;
212
213 if (buflen != 0)
214 return 0;
215 m = (struct mbuf *)p;
216 MINDEX(len, m, k);
217 A = mtod(m, u_char *)[k];
218 continue;
219 #else
220 return 0;
221 #endif
222 }
223 A = p[k];
224 continue;
225
226 case BPF_LD|BPF_W|BPF_LEN:
227 A = wirelen;
228 continue;
229
230 case BPF_LDX|BPF_W|BPF_LEN:
231 X = wirelen;
232 continue;
233
234 case BPF_LD|BPF_W|BPF_IND:
235 k = X + pc->k;
236 if (k + sizeof(int32_t) > buflen) {
237 #ifdef _KERNEL
238 int merr = 0; /* XXX: GCC */
239
240 if (buflen != 0)
241 return 0;
242 A = m_xword((struct mbuf *)p, k, &merr);
243 if (merr != 0)
244 return 0;
245 continue;
246 #else
247 return 0;
248 #endif
249 }
250 A = EXTRACT_LONG(&p[k]);
251 continue;
252
253 case BPF_LD|BPF_H|BPF_IND:
254 k = X + pc->k;
255 if (k + sizeof(int16_t) > buflen) {
256 #ifdef _KERNEL
257 int merr = 0; /* XXX: GCC */
258
259 if (buflen != 0)
260 return 0;
261 A = m_xhalf((struct mbuf *)p, k, &merr);
262 if (merr != 0)
263 return 0;
264 continue;
265 #else
266 return 0;
267 #endif
268 }
269 A = EXTRACT_SHORT(&p[k]);
270 continue;
271
272 case BPF_LD|BPF_B|BPF_IND:
273 k = X + pc->k;
274 if (k >= buflen) {
275 #ifdef _KERNEL
276 struct mbuf *m;
277 int len;
278
279 if (buflen != 0)
280 return 0;
281 m = (struct mbuf *)p;
282 MINDEX(len, m, k);
283 A = mtod(m, u_char *)[k];
284 continue;
285 #else
286 return 0;
287 #endif
288 }
289 A = p[k];
290 continue;
291
292 case BPF_LDX|BPF_MSH|BPF_B:
293 k = pc->k;
294 if (k >= buflen) {
295 #ifdef _KERNEL
296 struct mbuf *m;
297 int len;
298
299 if (buflen != 0)
300 return 0;
301 m = (struct mbuf *)p;
302 MINDEX(len, m, k);
303 X = (mtod(m, char *)[k] & 0xf) << 2;
304 continue;
305 #else
306 return 0;
307 #endif
308 }
309 X = (p[pc->k] & 0xf) << 2;
310 continue;
311
312 case BPF_LD|BPF_IMM:
313 A = pc->k;
314 continue;
315
316 case BPF_LDX|BPF_IMM:
317 X = pc->k;
318 continue;
319
320 case BPF_LD|BPF_MEM:
321 A = mem[pc->k];
322 continue;
323
324 case BPF_LDX|BPF_MEM:
325 X = mem[pc->k];
326 continue;
327
328 case BPF_ST:
329 mem[pc->k] = A;
330 continue;
331
332 case BPF_STX:
333 mem[pc->k] = X;
334 continue;
335
336 case BPF_JMP|BPF_JA:
337 pc += pc->k;
338 continue;
339
340 case BPF_JMP|BPF_JGT|BPF_K:
341 pc += (A > pc->k) ? pc->jt : pc->jf;
342 continue;
343
344 case BPF_JMP|BPF_JGE|BPF_K:
345 pc += (A >= pc->k) ? pc->jt : pc->jf;
346 continue;
347
348 case BPF_JMP|BPF_JEQ|BPF_K:
349 pc += (A == pc->k) ? pc->jt : pc->jf;
350 continue;
351
352 case BPF_JMP|BPF_JSET|BPF_K:
353 pc += (A & pc->k) ? pc->jt : pc->jf;
354 continue;
355
356 case BPF_JMP|BPF_JGT|BPF_X:
357 pc += (A > X) ? pc->jt : pc->jf;
358 continue;
359
360 case BPF_JMP|BPF_JGE|BPF_X:
361 pc += (A >= X) ? pc->jt : pc->jf;
362 continue;
363
364 case BPF_JMP|BPF_JEQ|BPF_X:
365 pc += (A == X) ? pc->jt : pc->jf;
366 continue;
367
368 case BPF_JMP|BPF_JSET|BPF_X:
369 pc += (A & X) ? pc->jt : pc->jf;
370 continue;
371
372 case BPF_ALU|BPF_ADD|BPF_X:
373 A += X;
374 continue;
375
376 case BPF_ALU|BPF_SUB|BPF_X:
377 A -= X;
378 continue;
379
380 case BPF_ALU|BPF_MUL|BPF_X:
381 A *= X;
382 continue;
383
384 case BPF_ALU|BPF_DIV|BPF_X:
385 if (X == 0)
386 return 0;
387 A /= X;
388 continue;
389
390 case BPF_ALU|BPF_AND|BPF_X:
391 A &= X;
392 continue;
393
394 case BPF_ALU|BPF_OR|BPF_X:
395 A |= X;
396 continue;
397
398 case BPF_ALU|BPF_LSH|BPF_X:
399 A <<= X;
400 continue;
401
402 case BPF_ALU|BPF_RSH|BPF_X:
403 A >>= X;
404 continue;
405
406 case BPF_ALU|BPF_ADD|BPF_K:
407 A += pc->k;
408 continue;
409
410 case BPF_ALU|BPF_SUB|BPF_K:
411 A -= pc->k;
412 continue;
413
414 case BPF_ALU|BPF_MUL|BPF_K:
415 A *= pc->k;
416 continue;
417
418 case BPF_ALU|BPF_DIV|BPF_K:
419 A /= pc->k;
420 continue;
421
422 case BPF_ALU|BPF_AND|BPF_K:
423 A &= pc->k;
424 continue;
425
426 case BPF_ALU|BPF_OR|BPF_K:
427 A |= pc->k;
428 continue;
429
430 case BPF_ALU|BPF_LSH|BPF_K:
431 A <<= pc->k;
432 continue;
433
434 case BPF_ALU|BPF_RSH|BPF_K:
435 A >>= pc->k;
436 continue;
437
438 case BPF_ALU|BPF_NEG:
439 A = -A;
440 continue;
441
442 case BPF_MISC|BPF_TAX:
443 X = A;
444 continue;
445
446 case BPF_MISC|BPF_TXA:
447 A = X;
448 continue;
449 }
450 }
451 }
452
453 #ifdef _KERNEL
454 /*
455 * Return true if the 'fcode' is a valid filter program.
456 * The constraints are that each jump be forward and to a valid
457 * code, that memory accesses are within valid ranges (to the
458 * extent that this can be checked statically; loads of packet
459 * data have to be, and are, also checked at run time), and that
460 * the code terminates with either an accept or reject.
461 *
462 * The kernel needs to be able to verify an application's filter code.
463 * Otherwise, a bogus program could easily crash the system.
464 */
465 CTASSERT(BPF_MEMWORDS == sizeof(uint16_t) * NBBY);
466
467 int
468 bpf_validate(struct bpf_insn *f, int signed_len)
469 {
470 u_int i, from, len, ok = 0;
471 const struct bpf_insn *p;
472 #if defined(KERNEL) || defined(_KERNEL)
473 uint16_t *mem, invalid;
474 size_t size;
475 #endif
476
477 len = (u_int)signed_len;
478 if (len < 1)
479 return 0;
480 #if defined(KERNEL) || defined(_KERNEL)
481 if (len > BPF_MAXINSNS)
482 return 0;
483 #endif
484 if (BPF_CLASS(f[len - 1].code) != BPF_RET)
485 return 0;
486
487 #if defined(KERNEL) || defined(_KERNEL)
488 mem = kmem_zalloc(size = sizeof(*mem) * len, KM_SLEEP);
489 invalid = ~0; /* All is invalid on startup */
490 #endif
491
492 for (i = 0; i < len; ++i) {
493 #if defined(KERNEL) || defined(_KERNEL)
494 /* blend in any invalid bits for current pc */
495 invalid |= mem[i];
496 #endif
497 p = &f[i];
498 switch (BPF_CLASS(p->code)) {
499 /*
500 * Check that memory operations use valid addresses.
501 */
502 case BPF_LD:
503 case BPF_LDX:
504 switch (BPF_MODE(p->code)) {
505 case BPF_MEM:
506 /*
507 * There's no maximum packet data size
508 * in userland. The runtime packet length
509 * check suffices.
510 */
511 #if defined(KERNEL) || defined(_KERNEL)
512 /*
513 * More strict check with actual packet length
514 * is done runtime.
515 */
516 if (p->k >= BPF_MEMWORDS)
517 goto out;
518 /* check for current memory invalid */
519 if (invalid & (1 << p->k))
520 goto out;
521 #endif
522 break;
523 case BPF_ABS:
524 case BPF_IND:
525 case BPF_MSH:
526 case BPF_IMM:
527 case BPF_LEN:
528 break;
529 default:
530 goto out;
531 }
532 break;
533 case BPF_ST:
534 case BPF_STX:
535 if (p->k >= BPF_MEMWORDS)
536 goto out;
537 #if defined(KERNEL) || defined(_KERNEL)
538 /* validate the memory word */
539 invalid &= ~(1 << p->k);
540 #endif
541 break;
542 case BPF_ALU:
543 switch (BPF_OP(p->code)) {
544 case BPF_ADD:
545 case BPF_SUB:
546 case BPF_MUL:
547 case BPF_OR:
548 case BPF_AND:
549 case BPF_LSH:
550 case BPF_RSH:
551 case BPF_NEG:
552 break;
553 case BPF_DIV:
554 /*
555 * Check for constant division by 0.
556 */
557 if (BPF_SRC(p->code) == BPF_K && p->k == 0)
558 goto out;
559 break;
560 default:
561 goto out;
562 }
563 break;
564 case BPF_JMP:
565 /*
566 * Check that jumps are within the code block,
567 * and that unconditional branches don't go
568 * backwards as a result of an overflow.
569 * Unconditional branches have a 32-bit offset,
570 * so they could overflow; we check to make
571 * sure they don't. Conditional branches have
572 * an 8-bit offset, and the from address is <=
573 * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
574 * is sufficiently small that adding 255 to it
575 * won't overflow.
576 *
577 * We know that len is <= BPF_MAXINSNS, and we
578 * assume that BPF_MAXINSNS is < the maximum size
579 * of a u_int, so that i + 1 doesn't overflow.
580 */
581 from = i + 1;
582 switch (BPF_OP(p->code)) {
583 case BPF_JA:
584 if (from + p->k >= len)
585 goto out;
586 #if defined(KERNEL) || defined(_KERNEL)
587 if (from + p->k < from)
588 goto out;
589 /*
590 * mark the currently invalid bits for the
591 * destination
592 */
593 mem[from + p->k] |= invalid;
594 invalid = 0;
595 #endif
596 break;
597 case BPF_JEQ:
598 case BPF_JGT:
599 case BPF_JGE:
600 case BPF_JSET:
601 if (from + p->jt >= len || from + p->jf >= len)
602 goto out;
603 #if defined(KERNEL) || defined(_KERNEL)
604 /*
605 * mark the currently invalid bits for both
606 * possible jump destinations
607 */
608 mem[from + p->jt] |= invalid;
609 mem[from + p->jf] |= invalid;
610 invalid = 0;
611 #endif
612 break;
613 default:
614 goto out;
615 }
616 break;
617 case BPF_RET:
618 break;
619 case BPF_MISC:
620 break;
621 default:
622 goto out;
623 }
624 }
625 ok = 1;
626 out:
627 #if defined(KERNEL) || defined(_KERNEL)
628 kmem_free(mem, size);
629 #endif
630 return ok;
631 }
632 #endif
Cache object: 90b62b4623daa8bbc5948f5dbc134e5f
|