Update files for libpcap-1.2.1 import.
[dragonfly.git] / contrib / libpcap / bpf / net / bpf_filter.c
1 /*-
2  * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997
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.c       7.5 (Berkeley) 7/15/91
39  */
40
41 #if !(defined(lint) || defined(KERNEL) || defined(_KERNEL))
42 static const char rcsid[] _U_ =
43     "@(#) $Header: /tcpdump/master/libpcap/bpf/net/bpf_filter.c,v 1.46 2008-01-02 04:16:46 guy Exp $ (LBL)";
44 #endif
45
46 #ifdef HAVE_CONFIG_H
47 #include "config.h"
48 #endif
49
50 #ifdef WIN32
51
52 #include <pcap-stdinc.h>
53
54 #else /* WIN32 */
55
56 #if HAVE_INTTYPES_H
57 #include <inttypes.h>
58 #elif HAVE_STDINT_H
59 #include <stdint.h>
60 #endif
61 #ifdef HAVE_SYS_BITYPES_H
62 #include <sys/bitypes.h>
63 #endif
64
65 #include <sys/param.h>
66 #include <sys/types.h>
67 #include <sys/time.h>
68
69 #define SOLARIS (defined(sun) && (defined(__SVR4) || defined(__svr4__)))
70 #if defined(__hpux) || SOLARIS
71 # include <sys/sysmacros.h>
72 # include <sys/stream.h>
73 # define        mbuf    msgb
74 # define        m_next  b_cont
75 # define        MLEN(m) ((m)->b_wptr - (m)->b_rptr)
76 # define        mtod(m,t)       ((t)(m)->b_rptr)
77 #else /* defined(__hpux) || SOLARIS */
78 # define        MLEN(m) ((m)->m_len)
79 #endif /* defined(__hpux) || SOLARIS */
80
81 #endif /* WIN32 */
82
83 #include <pcap/bpf.h>
84
85 #if !defined(KERNEL) && !defined(_KERNEL)
86 #include <stdlib.h>
87 #endif
88
89 #define int32 bpf_int32
90 #define u_int32 bpf_u_int32
91
92 #ifndef LBL_ALIGN
93 /*
94  * XXX - IA-64?  If not, this probably won't work on Win64 IA-64
95  * systems, unless LBL_ALIGN is defined elsewhere for them.
96  * XXX - SuperH?  If not, this probably won't work on WinCE SuperH
97  * systems, unless LBL_ALIGN is defined elsewhere for them.
98  */
99 #if defined(sparc) || defined(__sparc__) || defined(mips) || \
100     defined(ibm032) || defined(__alpha) || defined(__hpux) || \
101     defined(__arm__)
102 #define LBL_ALIGN
103 #endif
104 #endif
105
106 #ifndef LBL_ALIGN
107 #ifndef WIN32
108 #include <netinet/in.h>
109 #endif
110
111 #define EXTRACT_SHORT(p)        ((u_short)ntohs(*(u_short *)p))
112 #define EXTRACT_LONG(p)         (ntohl(*(u_int32 *)p))
113 #else
114 #define EXTRACT_SHORT(p)\
115         ((u_short)\
116                 ((u_short)*((u_char *)p+0)<<8|\
117                  (u_short)*((u_char *)p+1)<<0))
118 #define EXTRACT_LONG(p)\
119                 ((u_int32)*((u_char *)p+0)<<24|\
120                  (u_int32)*((u_char *)p+1)<<16|\
121                  (u_int32)*((u_char *)p+2)<<8|\
122                  (u_int32)*((u_char *)p+3)<<0)
123 #endif
124
125 #if defined(KERNEL) || defined(_KERNEL)
126 # if !defined(__hpux) && !SOLARIS
127 #include <sys/mbuf.h>
128 # endif
129 #define MINDEX(len, _m, _k) \
130 { \
131         len = MLEN(m); \
132         while ((_k) >= len) { \
133                 (_k) -= len; \
134                 (_m) = (_m)->m_next; \
135                 if ((_m) == 0) \
136                         return 0; \
137                 len = MLEN(m); \
138         } \
139 }
140
141 static int
142 m_xword(m, k, err)
143         register struct mbuf *m;
144         register int k, *err;
145 {
146         register int len;
147         register u_char *cp, *np;
148         register struct mbuf *m0;
149
150         MINDEX(len, m, k);
151         cp = mtod(m, u_char *) + k;
152         if (len - k >= 4) {
153                 *err = 0;
154                 return EXTRACT_LONG(cp);
155         }
156         m0 = m->m_next;
157         if (m0 == 0 || MLEN(m0) + len - k < 4)
158                 goto bad;
159         *err = 0;
160         np = mtod(m0, u_char *);
161         switch (len - k) {
162
163         case 1:
164                 return (cp[0] << 24) | (np[0] << 16) | (np[1] << 8) | np[2];
165
166         case 2:
167                 return (cp[0] << 24) | (cp[1] << 16) | (np[0] << 8) | np[1];
168
169         default:
170                 return (cp[0] << 24) | (cp[1] << 16) | (cp[2] << 8) | np[0];
171         }
172     bad:
173         *err = 1;
174         return 0;
175 }
176
177 static int
178 m_xhalf(m, k, err)
179         register struct mbuf *m;
180         register int k, *err;
181 {
182         register int len;
183         register u_char *cp;
184         register struct mbuf *m0;
185
186         MINDEX(len, m, k);
187         cp = mtod(m, u_char *) + k;
188         if (len - k >= 2) {
189                 *err = 0;
190                 return EXTRACT_SHORT(cp);
191         }
192         m0 = m->m_next;
193         if (m0 == 0)
194                 goto bad;
195         *err = 0;
196         return (cp[0] << 8) | mtod(m0, u_char *)[0];
197  bad:
198         *err = 1;
199         return 0;
200 }
201 #endif
202
203 /*
204  * Execute the filter program starting at pc on the packet p
205  * wirelen is the length of the original packet
206  * buflen is the amount of data present
207  * For the kernel, p is assumed to be a pointer to an mbuf if buflen is 0,
208  * in all other cases, p is a pointer to a buffer and buflen is its size.
209  */
210 u_int
211 bpf_filter(pc, p, wirelen, buflen)
212         register const struct bpf_insn *pc;
213         register const u_char *p;
214         u_int wirelen;
215         register u_int buflen;
216 {
217         register u_int32 A, X;
218         register int k;
219         int32 mem[BPF_MEMWORDS];
220 #if defined(KERNEL) || defined(_KERNEL)
221         struct mbuf *m, *n;
222         int merr, len;
223
224         if (buflen == 0) {
225                 m = (struct mbuf *)p;
226                 p = mtod(m, u_char *);
227                 buflen = MLEN(m);
228         } else
229                 m = NULL;
230 #endif
231
232         if (pc == 0)
233                 /*
234                  * No filter means accept all.
235                  */
236                 return (u_int)-1;
237         A = 0;
238         X = 0;
239         --pc;
240         while (1) {
241                 ++pc;
242                 switch (pc->code) {
243
244                 default:
245 #if defined(KERNEL) || defined(_KERNEL)
246                         return 0;
247 #else
248                         abort();
249 #endif
250                 case BPF_RET|BPF_K:
251                         return (u_int)pc->k;
252
253                 case BPF_RET|BPF_A:
254                         return (u_int)A;
255
256                 case BPF_LD|BPF_W|BPF_ABS:
257                         k = pc->k;
258                         if (k + sizeof(int32) > buflen) {
259 #if defined(KERNEL) || defined(_KERNEL)
260                                 if (m == NULL)
261                                         return 0;
262                                 A = m_xword(m, 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_ABS:
274                         k = pc->k;
275                         if (k + sizeof(short) > buflen) {
276 #if defined(KERNEL) || defined(_KERNEL)
277                                 if (m == NULL)
278                                         return 0;
279                                 A = m_xhalf(m, k, &merr);
280                                 if (merr != 0)
281                                         return 0;
282                                 continue;
283 #else
284                                 return 0;
285 #endif
286                         }
287                         A = EXTRACT_SHORT(&p[k]);
288                         continue;
289
290                 case BPF_LD|BPF_B|BPF_ABS:
291                         k = pc->k;
292                         if (k >= buflen) {
293 #if defined(KERNEL) || defined(_KERNEL)
294                                 if (m == NULL)
295                                         return 0;
296                                 n = m;
297                                 MINDEX(len, n, k);
298                                 A = mtod(n, u_char *)[k];
299                                 continue;
300 #else
301                                 return 0;
302 #endif
303                         }
304                         A = p[k];
305                         continue;
306
307                 case BPF_LD|BPF_W|BPF_LEN:
308                         A = wirelen;
309                         continue;
310
311                 case BPF_LDX|BPF_W|BPF_LEN:
312                         X = wirelen;
313                         continue;
314
315                 case BPF_LD|BPF_W|BPF_IND:
316                         k = X + pc->k;
317                         if (k + sizeof(int32) > buflen) {
318 #if defined(KERNEL) || defined(_KERNEL)
319                                 if (m == NULL)
320                                         return 0;
321                                 A = m_xword(m, k, &merr);
322                                 if (merr != 0)
323                                         return 0;
324                                 continue;
325 #else
326                                 return 0;
327 #endif
328                         }
329                         A = EXTRACT_LONG(&p[k]);
330                         continue;
331
332                 case BPF_LD|BPF_H|BPF_IND:
333                         k = X + pc->k;
334                         if (k + sizeof(short) > buflen) {
335 #if defined(KERNEL) || defined(_KERNEL)
336                                 if (m == NULL)
337                                         return 0;
338                                 A = m_xhalf(m, k, &merr);
339                                 if (merr != 0)
340                                         return 0;
341                                 continue;
342 #else
343                                 return 0;
344 #endif
345                         }
346                         A = EXTRACT_SHORT(&p[k]);
347                         continue;
348
349                 case BPF_LD|BPF_B|BPF_IND:
350                         k = X + pc->k;
351                         if (k >= buflen) {
352 #if defined(KERNEL) || defined(_KERNEL)
353                                 if (m == NULL)
354                                         return 0;
355                                 n = m;
356                                 MINDEX(len, n, k);
357                                 A = mtod(n, u_char *)[k];
358                                 continue;
359 #else
360                                 return 0;
361 #endif
362                         }
363                         A = p[k];
364                         continue;
365
366                 case BPF_LDX|BPF_MSH|BPF_B:
367                         k = pc->k;
368                         if (k >= buflen) {
369 #if defined(KERNEL) || defined(_KERNEL)
370                                 if (m == NULL)
371                                         return 0;
372                                 n = m;
373                                 MINDEX(len, n, k);
374                                 X = (mtod(n, char *)[k] & 0xf) << 2;
375                                 continue;
376 #else
377                                 return 0;
378 #endif
379                         }
380                         X = (p[pc->k] & 0xf) << 2;
381                         continue;
382
383                 case BPF_LD|BPF_IMM:
384                         A = pc->k;
385                         continue;
386
387                 case BPF_LDX|BPF_IMM:
388                         X = pc->k;
389                         continue;
390
391                 case BPF_LD|BPF_MEM:
392                         A = mem[pc->k];
393                         continue;
394
395                 case BPF_LDX|BPF_MEM:
396                         X = mem[pc->k];
397                         continue;
398
399                 case BPF_ST:
400                         mem[pc->k] = A;
401                         continue;
402
403                 case BPF_STX:
404                         mem[pc->k] = X;
405                         continue;
406
407                 case BPF_JMP|BPF_JA:
408 #if defined(KERNEL) || defined(_KERNEL)
409                         /*
410                          * No backward jumps allowed.
411                          */
412                         pc += pc->k;
413 #else
414                         /*
415                          * XXX - we currently implement "ip6 protochain"
416                          * with backward jumps, so sign-extend pc->k.
417                          */
418                         pc += (bpf_int32)pc->k;
419 #endif
420                         continue;
421
422                 case BPF_JMP|BPF_JGT|BPF_K:
423                         pc += (A > pc->k) ? pc->jt : pc->jf;
424                         continue;
425
426                 case BPF_JMP|BPF_JGE|BPF_K:
427                         pc += (A >= pc->k) ? pc->jt : pc->jf;
428                         continue;
429
430                 case BPF_JMP|BPF_JEQ|BPF_K:
431                         pc += (A == pc->k) ? pc->jt : pc->jf;
432                         continue;
433
434                 case BPF_JMP|BPF_JSET|BPF_K:
435                         pc += (A & pc->k) ? pc->jt : pc->jf;
436                         continue;
437
438                 case BPF_JMP|BPF_JGT|BPF_X:
439                         pc += (A > X) ? pc->jt : pc->jf;
440                         continue;
441
442                 case BPF_JMP|BPF_JGE|BPF_X:
443                         pc += (A >= X) ? pc->jt : pc->jf;
444                         continue;
445
446                 case BPF_JMP|BPF_JEQ|BPF_X:
447                         pc += (A == X) ? pc->jt : pc->jf;
448                         continue;
449
450                 case BPF_JMP|BPF_JSET|BPF_X:
451                         pc += (A & X) ? pc->jt : pc->jf;
452                         continue;
453
454                 case BPF_ALU|BPF_ADD|BPF_X:
455                         A += X;
456                         continue;
457
458                 case BPF_ALU|BPF_SUB|BPF_X:
459                         A -= X;
460                         continue;
461
462                 case BPF_ALU|BPF_MUL|BPF_X:
463                         A *= X;
464                         continue;
465
466                 case BPF_ALU|BPF_DIV|BPF_X:
467                         if (X == 0)
468                                 return 0;
469                         A /= X;
470                         continue;
471
472                 case BPF_ALU|BPF_AND|BPF_X:
473                         A &= X;
474                         continue;
475
476                 case BPF_ALU|BPF_OR|BPF_X:
477                         A |= X;
478                         continue;
479
480                 case BPF_ALU|BPF_LSH|BPF_X:
481                         A <<= X;
482                         continue;
483
484                 case BPF_ALU|BPF_RSH|BPF_X:
485                         A >>= X;
486                         continue;
487
488                 case BPF_ALU|BPF_ADD|BPF_K:
489                         A += pc->k;
490                         continue;
491
492                 case BPF_ALU|BPF_SUB|BPF_K:
493                         A -= pc->k;
494                         continue;
495
496                 case BPF_ALU|BPF_MUL|BPF_K:
497                         A *= pc->k;
498                         continue;
499
500                 case BPF_ALU|BPF_DIV|BPF_K:
501                         A /= pc->k;
502                         continue;
503
504                 case BPF_ALU|BPF_AND|BPF_K:
505                         A &= pc->k;
506                         continue;
507
508                 case BPF_ALU|BPF_OR|BPF_K:
509                         A |= pc->k;
510                         continue;
511
512                 case BPF_ALU|BPF_LSH|BPF_K:
513                         A <<= pc->k;
514                         continue;
515
516                 case BPF_ALU|BPF_RSH|BPF_K:
517                         A >>= pc->k;
518                         continue;
519
520                 case BPF_ALU|BPF_NEG:
521                         A = -A;
522                         continue;
523
524                 case BPF_MISC|BPF_TAX:
525                         X = A;
526                         continue;
527
528                 case BPF_MISC|BPF_TXA:
529                         A = X;
530                         continue;
531                 }
532         }
533 }
534
535 /*
536  * Return true if the 'fcode' is a valid filter program.
537  * The constraints are that each jump be forward and to a valid
538  * code, that memory accesses are within valid ranges (to the
539  * extent that this can be checked statically; loads of packet
540  * data have to be, and are, also checked at run time), and that
541  * the code terminates with either an accept or reject.
542  *
543  * The kernel needs to be able to verify an application's filter code.
544  * Otherwise, a bogus program could easily crash the system.
545  */
546 int
547 bpf_validate(f, len)
548         const struct bpf_insn *f;
549         int len;
550 {
551         u_int i, from;
552         const struct bpf_insn *p;
553
554         if (len < 1)
555                 return 0;
556         /*
557          * There's no maximum program length in userland.
558          */
559 #if defined(KERNEL) || defined(_KERNEL)
560         if (len > BPF_MAXINSNS)
561                 return 0;
562 #endif
563
564         for (i = 0; i < len; ++i) {
565                 p = &f[i];
566                 switch (BPF_CLASS(p->code)) {
567                 /*
568                  * Check that memory operations use valid addresses.
569                  */
570                 case BPF_LD:
571                 case BPF_LDX:
572                         switch (BPF_MODE(p->code)) {
573                         case BPF_IMM:
574                                 break;
575                         case BPF_ABS:
576                         case BPF_IND:
577                         case BPF_MSH:
578                                 /*
579                                  * There's no maximum packet data size
580                                  * in userland.  The runtime packet length
581                                  * check suffices.
582                                  */
583 #if defined(KERNEL) || defined(_KERNEL)
584                                 /*
585                                  * More strict check with actual packet length
586                                  * is done runtime.
587                                  */
588                                 if (p->k >= bpf_maxbufsize)
589                                         return 0;
590 #endif
591                                 break;
592                         case BPF_MEM:
593                                 if (p->k >= BPF_MEMWORDS)
594                                         return 0;
595                                 break;
596                         case BPF_LEN:
597                                 break;
598                         default:
599                                 return 0;
600                         }
601                         break;
602                 case BPF_ST:
603                 case BPF_STX:
604                         if (p->k >= BPF_MEMWORDS)
605                                 return 0;
606                         break;
607                 case BPF_ALU:
608                         switch (BPF_OP(p->code)) {
609                         case BPF_ADD:
610                         case BPF_SUB:
611                         case BPF_MUL:
612                         case BPF_OR:
613                         case BPF_AND:
614                         case BPF_LSH:
615                         case BPF_RSH:
616                         case BPF_NEG:
617                                 break;
618                         case BPF_DIV:
619                                 /*
620                                  * Check for constant division by 0.
621                                  */
622                                 if (BPF_SRC(p->code) == BPF_K && p->k == 0)
623                                         return 0;
624                                 break;
625                         default:
626                                 return 0;
627                         }
628                         break;
629                 case BPF_JMP:
630                         /*
631                          * Check that jumps are within the code block,
632                          * and that unconditional branches don't go
633                          * backwards as a result of an overflow.
634                          * Unconditional branches have a 32-bit offset,
635                          * so they could overflow; we check to make
636                          * sure they don't.  Conditional branches have
637                          * an 8-bit offset, and the from address is <=
638                          * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
639                          * is sufficiently small that adding 255 to it
640                          * won't overflow.
641                          *
642                          * We know that len is <= BPF_MAXINSNS, and we
643                          * assume that BPF_MAXINSNS is < the maximum size
644                          * of a u_int, so that i + 1 doesn't overflow.
645                          *
646                          * For userland, we don't know that the from
647                          * or len are <= BPF_MAXINSNS, but we know that
648                          * from <= len, and, except on a 64-bit system,
649                          * it's unlikely that len, if it truly reflects
650                          * the size of the program we've been handed,
651                          * will be anywhere near the maximum size of
652                          * a u_int.  We also don't check for backward
653                          * branches, as we currently support them in
654                          * userland for the protochain operation.
655                          */
656                         from = i + 1;
657                         switch (BPF_OP(p->code)) {
658                         case BPF_JA:
659 #if defined(KERNEL) || defined(_KERNEL)
660                                 if (from + p->k < from || from + p->k >= len)
661 #else
662                                 if (from + p->k >= len)
663 #endif
664                                         return 0;
665                                 break;
666                         case BPF_JEQ:
667                         case BPF_JGT:
668                         case BPF_JGE:
669                         case BPF_JSET:
670                                 if (from + p->jt >= len || from + p->jf >= len)
671                                         return 0;
672                                 break;
673                         default:
674                                 return 0;
675                         }
676                         break;
677                 case BPF_RET:
678                         break;
679                 case BPF_MISC:
680                         break;
681                 default:
682                         return 0;
683                 }
684         }
685         return BPF_CLASS(f[len - 1].code) == BPF_RET;
686 }