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