Merge branch 'vendor/LIBPCAP'
[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.44 2003/11/15 23:24:07 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 #include <sys/param.h>
57 #include <sys/types.h>
58 #include <sys/time.h>
59
60 #define SOLARIS (defined(sun) && (defined(__SVR4) || defined(__svr4__)))
61 #if defined(__hpux) || SOLARIS
62 # include <sys/sysmacros.h>
63 # include <sys/stream.h>
64 # define        mbuf    msgb
65 # define        m_next  b_cont
66 # define        MLEN(m) ((m)->b_wptr - (m)->b_rptr)
67 # define        mtod(m,t)       ((t)(m)->b_rptr)
68 #else
69 # define        MLEN(m) ((m)->m_len)
70 #endif
71
72 #endif /* WIN32 */
73
74 #include <net/bpf.h>
75
76 #if !defined(KERNEL) && !defined(_KERNEL)
77 #include <stdlib.h>
78 #endif
79
80 #define int32 bpf_int32
81 #define u_int32 bpf_u_int32
82
83 #ifndef LBL_ALIGN
84 /*
85  * XXX - IA-64?  If not, this probably won't work on Win64 IA-64
86  * systems, unless LBL_ALIGN is defined elsewhere for them.
87  * XXX - SuperH?  If not, this probably won't work on WinCE SuperH
88  * systems, unless LBL_ALIGN is defined elsewhere for them.
89  */
90 #if defined(sparc) || defined(__sparc__) || defined(mips) || \
91     defined(ibm032) || defined(__alpha) || defined(__hpux) || \
92     defined(__arm__)
93 #define LBL_ALIGN
94 #endif
95 #endif
96
97 #ifndef LBL_ALIGN
98 #ifndef WIN32
99 #include <netinet/in.h>
100 #endif
101
102 #define EXTRACT_SHORT(p)        ((u_short)ntohs(*(u_short *)p))
103 #define EXTRACT_LONG(p)         (ntohl(*(u_int32 *)p))
104 #else
105 #define EXTRACT_SHORT(p)\
106         ((u_short)\
107                 ((u_short)*((u_char *)p+0)<<8|\
108                  (u_short)*((u_char *)p+1)<<0))
109 #define EXTRACT_LONG(p)\
110                 ((u_int32)*((u_char *)p+0)<<24|\
111                  (u_int32)*((u_char *)p+1)<<16|\
112                  (u_int32)*((u_char *)p+2)<<8|\
113                  (u_int32)*((u_char *)p+3)<<0)
114 #endif
115
116 #if defined(KERNEL) || defined(_KERNEL)
117 # if !defined(__hpux) && !SOLARIS
118 #include <sys/mbuf.h>
119 # endif
120 #define MINDEX(len, _m, _k) \
121 { \
122         len = MLEN(m); \
123         while ((_k) >= len) { \
124                 (_k) -= len; \
125                 (_m) = (_m)->m_next; \
126                 if ((_m) == 0) \
127                         return 0; \
128                 len = MLEN(m); \
129         } \
130 }
131
132 static int
133 m_xword(m, k, err)
134         register struct mbuf *m;
135         register int k, *err;
136 {
137         register int len;
138         register u_char *cp, *np;
139         register struct mbuf *m0;
140
141         MINDEX(len, m, k);
142         cp = mtod(m, u_char *) + k;
143         if (len - k >= 4) {
144                 *err = 0;
145                 return EXTRACT_LONG(cp);
146         }
147         m0 = m->m_next;
148         if (m0 == 0 || MLEN(m0) + len - k < 4)
149                 goto bad;
150         *err = 0;
151         np = mtod(m0, u_char *);
152         switch (len - k) {
153
154         case 1:
155                 return (cp[0] << 24) | (np[0] << 16) | (np[1] << 8) | np[2];
156
157         case 2:
158                 return (cp[0] << 24) | (cp[1] << 16) | (np[0] << 8) | np[1];
159
160         default:
161                 return (cp[0] << 24) | (cp[1] << 16) | (cp[2] << 8) | np[0];
162         }
163     bad:
164         *err = 1;
165         return 0;
166 }
167
168 static int
169 m_xhalf(m, k, err)
170         register struct mbuf *m;
171         register int k, *err;
172 {
173         register int len;
174         register u_char *cp;
175         register struct mbuf *m0;
176
177         MINDEX(len, m, k);
178         cp = mtod(m, u_char *) + k;
179         if (len - k >= 2) {
180                 *err = 0;
181                 return EXTRACT_SHORT(cp);
182         }
183         m0 = m->m_next;
184         if (m0 == 0)
185                 goto bad;
186         *err = 0;
187         return (cp[0] << 8) | mtod(m0, u_char *)[0];
188  bad:
189         *err = 1;
190         return 0;
191 }
192 #endif
193
194 /*
195  * Execute the filter program starting at pc on the packet p
196  * wirelen is the length of the original packet
197  * buflen is the amount of data present
198  * For the kernel, p is assumed to be a pointer to an mbuf if buflen is 0,
199  * in all other cases, p is a pointer to a buffer and buflen is its size.
200  */
201 u_int
202 bpf_filter(pc, p, wirelen, buflen)
203         register struct bpf_insn *pc;
204         register u_char *p;
205         u_int wirelen;
206         register u_int buflen;
207 {
208         register u_int32 A, X;
209         register int k;
210         int32 mem[BPF_MEMWORDS];
211 #if defined(KERNEL) || defined(_KERNEL)
212         struct mbuf *m, *n;
213         int merr, len;
214
215         if (buflen == 0) {
216                 m = (struct mbuf *)p;
217                 p = mtod(m, u_char *);
218                 buflen = MLEN(m);
219         } else
220                 m = NULL;
221 #endif
222
223         if (pc == 0)
224                 /*
225                  * No filter means accept all.
226                  */
227                 return (u_int)-1;
228         A = 0;
229         X = 0;
230         --pc;
231         while (1) {
232                 ++pc;
233                 switch (pc->code) {
234
235                 default:
236 #if defined(KERNEL) || defined(_KERNEL)
237                         return 0;
238 #else
239                         abort();
240 #endif
241                 case BPF_RET|BPF_K:
242                         return (u_int)pc->k;
243
244                 case BPF_RET|BPF_A:
245                         return (u_int)A;
246
247                 case BPF_LD|BPF_W|BPF_ABS:
248                         k = pc->k;
249                         if (k + sizeof(int32) > buflen) {
250 #if defined(KERNEL) || defined(_KERNEL)
251                                 if (m == NULL)
252                                         return 0;
253                                 A = m_xword(m, k, &merr);
254                                 if (merr != 0)
255                                         return 0;
256                                 continue;
257 #else
258                                 return 0;
259 #endif
260                         }
261                         A = EXTRACT_LONG(&p[k]);
262                         continue;
263
264                 case BPF_LD|BPF_H|BPF_ABS:
265                         k = pc->k;
266                         if (k + sizeof(short) > buflen) {
267 #if defined(KERNEL) || defined(_KERNEL)
268                                 if (m == NULL)
269                                         return 0;
270                                 A = m_xhalf(m, k, &merr);
271                                 if (merr != 0)
272                                         return 0;
273                                 continue;
274 #else
275                                 return 0;
276 #endif
277                         }
278                         A = EXTRACT_SHORT(&p[k]);
279                         continue;
280
281                 case BPF_LD|BPF_B|BPF_ABS:
282                         k = pc->k;
283                         if (k >= buflen) {
284 #if defined(KERNEL) || defined(_KERNEL)
285                                 if (m == NULL)
286                                         return 0;
287                                 n = m;
288                                 MINDEX(len, n, k);
289                                 A = mtod(n, u_char *)[k];
290                                 continue;
291 #else
292                                 return 0;
293 #endif
294                         }
295                         A = p[k];
296                         continue;
297
298                 case BPF_LD|BPF_W|BPF_LEN:
299                         A = wirelen;
300                         continue;
301
302                 case BPF_LDX|BPF_W|BPF_LEN:
303                         X = wirelen;
304                         continue;
305
306                 case BPF_LD|BPF_W|BPF_IND:
307                         k = X + pc->k;
308                         if (k + sizeof(int32) > buflen) {
309 #if defined(KERNEL) || defined(_KERNEL)
310                                 if (m == NULL)
311                                         return 0;
312                                 A = m_xword(m, k, &merr);
313                                 if (merr != 0)
314                                         return 0;
315                                 continue;
316 #else
317                                 return 0;
318 #endif
319                         }
320                         A = EXTRACT_LONG(&p[k]);
321                         continue;
322
323                 case BPF_LD|BPF_H|BPF_IND:
324                         k = X + pc->k;
325                         if (k + sizeof(short) > buflen) {
326 #if defined(KERNEL) || defined(_KERNEL)
327                                 if (m == NULL)
328                                         return 0;
329                                 A = m_xhalf(m, k, &merr);
330                                 if (merr != 0)
331                                         return 0;
332                                 continue;
333 #else
334                                 return 0;
335 #endif
336                         }
337                         A = EXTRACT_SHORT(&p[k]);
338                         continue;
339
340                 case BPF_LD|BPF_B|BPF_IND:
341                         k = X + pc->k;
342                         if (k >= buflen) {
343 #if defined(KERNEL) || defined(_KERNEL)
344                                 if (m == NULL)
345                                         return 0;
346                                 n = m;
347                                 MINDEX(len, n, k);
348                                 A = mtod(n, u_char *)[k];
349                                 continue;
350 #else
351                                 return 0;
352 #endif
353                         }
354                         A = p[k];
355                         continue;
356
357                 case BPF_LDX|BPF_MSH|BPF_B:
358                         k = pc->k;
359                         if (k >= buflen) {
360 #if defined(KERNEL) || defined(_KERNEL)
361                                 if (m == NULL)
362                                         return 0;
363                                 n = m;
364                                 MINDEX(len, n, k);
365                                 X = (mtod(n, char *)[k] & 0xf) << 2;
366                                 continue;
367 #else
368                                 return 0;
369 #endif
370                         }
371                         X = (p[pc->k] & 0xf) << 2;
372                         continue;
373
374                 case BPF_LD|BPF_IMM:
375                         A = pc->k;
376                         continue;
377
378                 case BPF_LDX|BPF_IMM:
379                         X = pc->k;
380                         continue;
381
382                 case BPF_LD|BPF_MEM:
383                         A = mem[pc->k];
384                         continue;
385
386                 case BPF_LDX|BPF_MEM:
387                         X = mem[pc->k];
388                         continue;
389
390                 case BPF_ST:
391                         mem[pc->k] = A;
392                         continue;
393
394                 case BPF_STX:
395                         mem[pc->k] = X;
396                         continue;
397
398                 case BPF_JMP|BPF_JA:
399                         pc += pc->k;
400                         continue;
401
402                 case BPF_JMP|BPF_JGT|BPF_K:
403                         pc += (A > pc->k) ? pc->jt : pc->jf;
404                         continue;
405
406                 case BPF_JMP|BPF_JGE|BPF_K:
407                         pc += (A >= pc->k) ? pc->jt : pc->jf;
408                         continue;
409
410                 case BPF_JMP|BPF_JEQ|BPF_K:
411                         pc += (A == pc->k) ? pc->jt : pc->jf;
412                         continue;
413
414                 case BPF_JMP|BPF_JSET|BPF_K:
415                         pc += (A & pc->k) ? pc->jt : pc->jf;
416                         continue;
417
418                 case BPF_JMP|BPF_JGT|BPF_X:
419                         pc += (A > X) ? pc->jt : pc->jf;
420                         continue;
421
422                 case BPF_JMP|BPF_JGE|BPF_X:
423                         pc += (A >= X) ? pc->jt : pc->jf;
424                         continue;
425
426                 case BPF_JMP|BPF_JEQ|BPF_X:
427                         pc += (A == X) ? pc->jt : pc->jf;
428                         continue;
429
430                 case BPF_JMP|BPF_JSET|BPF_X:
431                         pc += (A & X) ? pc->jt : pc->jf;
432                         continue;
433
434                 case BPF_ALU|BPF_ADD|BPF_X:
435                         A += X;
436                         continue;
437
438                 case BPF_ALU|BPF_SUB|BPF_X:
439                         A -= X;
440                         continue;
441
442                 case BPF_ALU|BPF_MUL|BPF_X:
443                         A *= X;
444                         continue;
445
446                 case BPF_ALU|BPF_DIV|BPF_X:
447                         if (X == 0)
448                                 return 0;
449                         A /= X;
450                         continue;
451
452                 case BPF_ALU|BPF_AND|BPF_X:
453                         A &= X;
454                         continue;
455
456                 case BPF_ALU|BPF_OR|BPF_X:
457                         A |= X;
458                         continue;
459
460                 case BPF_ALU|BPF_LSH|BPF_X:
461                         A <<= X;
462                         continue;
463
464                 case BPF_ALU|BPF_RSH|BPF_X:
465                         A >>= X;
466                         continue;
467
468                 case BPF_ALU|BPF_ADD|BPF_K:
469                         A += pc->k;
470                         continue;
471
472                 case BPF_ALU|BPF_SUB|BPF_K:
473                         A -= pc->k;
474                         continue;
475
476                 case BPF_ALU|BPF_MUL|BPF_K:
477                         A *= pc->k;
478                         continue;
479
480                 case BPF_ALU|BPF_DIV|BPF_K:
481                         A /= pc->k;
482                         continue;
483
484                 case BPF_ALU|BPF_AND|BPF_K:
485                         A &= pc->k;
486                         continue;
487
488                 case BPF_ALU|BPF_OR|BPF_K:
489                         A |= pc->k;
490                         continue;
491
492                 case BPF_ALU|BPF_LSH|BPF_K:
493                         A <<= pc->k;
494                         continue;
495
496                 case BPF_ALU|BPF_RSH|BPF_K:
497                         A >>= pc->k;
498                         continue;
499
500                 case BPF_ALU|BPF_NEG:
501                         A = -A;
502                         continue;
503
504                 case BPF_MISC|BPF_TAX:
505                         X = A;
506                         continue;
507
508                 case BPF_MISC|BPF_TXA:
509                         A = X;
510                         continue;
511                 }
512         }
513 }
514
515
516 /*
517  * Return true if the 'fcode' is a valid filter program.
518  * The constraints are that each jump be forward and to a valid
519  * code.  The code must terminate with either an accept or reject.
520  * 'valid' is an array for use by the routine (it must be at least
521  * 'len' bytes long).
522  *
523  * The kernel needs to be able to verify an application's filter code.
524  * Otherwise, a bogus program could easily crash the system.
525  */
526 int
527 bpf_validate(f, len)
528         struct bpf_insn *f;
529         int len;
530 {
531         register int i;
532         register struct bpf_insn *p;
533
534         for (i = 0; i < len; ++i) {
535                 /*
536                  * Check that that jumps are forward, and within
537                  * the code block.
538                  */
539                 p = &f[i];
540                 if (BPF_CLASS(p->code) == BPF_JMP) {
541                         register int from = i + 1;
542
543                         if (BPF_OP(p->code) == BPF_JA) {
544                                 if (from + p->k >= (unsigned)len)
545                                         return 0;
546                         }
547                         else if (from + p->jt >= len || from + p->jf >= len)
548                                 return 0;
549                 }
550                 /*
551                  * Check that memory operations use valid addresses.
552                  */
553                 if ((BPF_CLASS(p->code) == BPF_ST ||
554                      (BPF_CLASS(p->code) == BPF_LD &&
555                       (p->code & 0xe0) == BPF_MEM)) &&
556                     (p->k >= BPF_MEMWORDS || p->k < 0))
557                         return 0;
558                 /*
559                  * Check for constant division by 0.
560                  */
561                 if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
562                         return 0;
563         }
564         return BPF_CLASS(f[len - 1].code) == BPF_RET;
565 }