bpf_jit_machdep.c revision 153995 
154359Sroberto/*-
2182007Sroberto * Copyright (c) 2002 - 2003 NetGroup, Politecnico di Torino (Italy)
354359Sroberto * Copyright (c) 2005 Jung-uk Kim <jkim@FreeBSD.org>
4182007Sroberto * All rights reserved.
5182007Sroberto *
654359Sroberto * Redistribution and use in source and binary forms, with or without
754359Sroberto * modification, are permitted provided that the following conditions
8182007Sroberto * are met:
9182007Sroberto *
10182007Sroberto * 1. Redistributions of source code must retain the above copyright
11182007Sroberto * notice, this list of conditions and the following disclaimer.
12182007Sroberto * 2. Redistributions in binary form must reproduce the above copyright
13182007Sroberto * notice, this list of conditions and the following disclaimer in the
14182007Sroberto * documentation and/or other materials provided with the distribution.
15182007Sroberto * 3. Neither the name of the Politecnico di Torino nor the names of its
16182007Sroberto * contributors may be used to endorse or promote products derived from
17182007Sroberto * this software without specific prior written permission.
18182007Sroberto *
19182007Sroberto * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20182007Sroberto * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21182007Sroberto * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22182007Sroberto * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23182007Sroberto * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24182007Sroberto * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25182007Sroberto * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26182007Sroberto * DATA, OR PROFITS; OR BUSINESS intERRUPTION) HOWEVER CAUSED AND ON ANY
27182007Sroberto * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28182007Sroberto * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29182007Sroberto * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30182007Sroberto */
31182007Sroberto
32182007Sroberto#include <sys/cdefs.h>
33182007Sroberto__FBSDID("$FreeBSD: head/sys/i386/i386/bpf_jit_machdep.c 153995 2006-01-03 20:26:03Z jkim $");
3454359Sroberto
3554359Sroberto#include "opt_bpf.h"
3654359Sroberto
3754359Sroberto#include <sys/param.h>
3854359Sroberto#include <sys/systm.h>
3954359Sroberto#include <sys/kernel.h>
4054359Sroberto#include <sys/types.h>
4154359Sroberto#include <sys/socket.h>
4254359Sroberto#include <sys/malloc.h>
4354359Sroberto
4454359Sroberto#include <net/if.h>
4554359Sroberto#include <net/bpf.h>
4654359Sroberto#include <net/bpf_jitter.h>
4754359Sroberto
4854359Sroberto#include <i386/i386/bpf_jit_machdep.h>
4954359Sroberto
5054359Srobertobpf_filter_func	bpf_jit_compile(struct bpf_insn *, u_int, int *);
5154359Sroberto
5254359Sroberto/*
5354359Sroberto * emit routine to update the jump table
5454359Sroberto */
5554359Srobertostatic void
5654359Srobertoemit_length(bpf_bin_stream *stream, u_int value, u_int len)
5754359Sroberto{
5854359Sroberto
5954359Sroberto	(stream->refs)[stream->bpf_pc] += len;
6054359Sroberto	stream->cur_ip += len;
6154359Sroberto}
6254359Sroberto
6354359Sroberto/*
6454359Sroberto * emit routine to output the actual binary code
6554359Sroberto */
6654359Srobertostatic void
6754359Srobertoemit_code(bpf_bin_stream *stream, u_int value, u_int len)
6854359Sroberto{
6954359Sroberto
7054359Sroberto	switch (len) {
7154359Sroberto	case 1:
7254359Sroberto		stream->ibuf[stream->cur_ip] = (u_char)value;
7354359Sroberto		stream->cur_ip++;
7454359Sroberto		break;
7554359Sroberto
7654359Sroberto	case 2:
7754359Sroberto		*((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
78182007Sroberto		stream->cur_ip += 2;
79182007Sroberto		break;
8054359Sroberto
81182007Sroberto	case 4:
82182007Sroberto		*((u_int *)(stream->ibuf + stream->cur_ip)) = value;
83182007Sroberto		stream->cur_ip += 4;
84182007Sroberto		break;
85182007Sroberto	}
86182007Sroberto
8754359Sroberto	return;
8854359Sroberto}
8954359Sroberto
9054359Sroberto/*
9154359Sroberto * Function that does the real stuff
9254359Sroberto */
9354359Srobertobpf_filter_func
9454359Srobertobpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem)
9554359Sroberto{
9654359Sroberto	struct bpf_insn *ins;
97	u_int i, pass;
98	bpf_bin_stream stream;
99
100	/*
101	 * NOTE: do not modify the name of this variable, as it's used by
102	 * the macros to emit code.
103	 */
104	emit_func emitm;
105
106	/* Do not compile an empty filter. */
107	if (nins == 0)
108		return NULL;
109
110	/* Allocate the reference table for the jumps */
111	stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int),
112	    M_BPFJIT, M_NOWAIT);
113	if (stream.refs == NULL)
114		return NULL;
115
116	/* Reset the reference table */
117	for (i = 0; i < nins + 1; i++)
118		stream.refs[i] = 0;
119
120	stream.cur_ip = 0;
121	stream.bpf_pc = 0;
122
123	/*
124	 * the first pass will emit the lengths of the instructions
125	 * to create the reference table
126	 */
127	emitm = emit_length;
128
129	pass = 0;
130	for (;;) {
131		ins = prog;
132
133		/* create the procedure header */
134		PUSH(EBP);
135		MOVrd(EBP, ESP);
136		PUSH(EDI);
137		PUSH(ESI);
138		PUSH(EBX);
139		MOVodd(EBX, EBP, 8);
140
141		for (i = 0; i < nins; i++) {
142			stream.bpf_pc++;
143
144			switch (ins->code) {
145			default:
146				return NULL;
147
148			case BPF_RET|BPF_K:
149				MOVid(EAX, ins->k);
150				POP(EBX);
151				POP(ESI);
152				POP(EDI);
153				LEAVE_RET();
154				break;
155
156			case BPF_RET|BPF_A:
157				POP(EBX);
158				POP(ESI);
159				POP(EDI);
160				LEAVE_RET();
161				break;
162
163			case BPF_LD|BPF_W|BPF_ABS:
164				MOVid(ECX, ins->k);
165				MOVrd(ESI, ECX);
166				ADDib(ECX, sizeof(int));
167				CMPodd(ECX, EBP, 0x10);
168				JLEb(7);
169				ZERO_EAX();
170				POP(EBX);
171				POP(ESI);
172				POP(EDI);
173				LEAVE_RET();
174				MOVobd(EAX, EBX, ESI);
175				BSWAP(EAX);
176				break;
177
178			case BPF_LD|BPF_H|BPF_ABS:
179				ZERO_EAX();
180				MOVid(ECX, ins->k);
181				MOVrd(ESI, ECX);
182				ADDib(ECX, sizeof(short));
183				CMPodd(ECX, EBP, 0x10);
184				JLEb(5);
185				POP(EBX);
186				POP(ESI);
187				POP(EDI);
188				LEAVE_RET();
189				MOVobw(AX, EBX, ESI);
190				SWAP_AX();
191				break;
192
193			case BPF_LD|BPF_B|BPF_ABS:
194				ZERO_EAX();
195				MOVid(ECX, ins->k);
196				CMPodd(ECX, EBP, 0x10);
197				JLEb(5);
198				POP(EBX);
199				POP(ESI);
200				POP(EDI);
201				LEAVE_RET();
202				MOVobb(AL, EBX, ECX);
203				break;
204
205			case BPF_LD|BPF_W|BPF_LEN:
206				MOVodd(EAX, EBP, 0xc);
207				break;
208
209			case BPF_LDX|BPF_W|BPF_LEN:
210				MOVodd(EDX, EBP, 0xc);
211				break;
212
213			case BPF_LD|BPF_W|BPF_IND:
214				MOVid(ECX, ins->k);
215				ADDrd(ECX, EDX);
216				MOVrd(ESI, ECX);
217				ADDib(ECX, sizeof(int));
218				CMPodd(ECX, EBP, 0x10);
219				JLEb(7);
220				ZERO_EAX();
221				POP(EBX);
222				POP(ESI);
223				POP(EDI);
224				LEAVE_RET();
225				MOVobd(EAX, EBX, ESI);
226				BSWAP(EAX);
227				break;
228
229			case BPF_LD|BPF_H|BPF_IND:
230				ZERO_EAX();
231				MOVid(ECX, ins->k);
232				ADDrd(ECX, EDX);
233				MOVrd(ESI, ECX);
234				ADDib(ECX, sizeof(short));
235				CMPodd(ECX, EBP, 0x10);
236				JLEb(5);
237				POP(EBX);
238				POP(ESI);
239				POP(EDI);
240				LEAVE_RET();
241				MOVobw(AX, EBX, ESI);
242				SWAP_AX();
243				break;
244
245			case BPF_LD|BPF_B|BPF_IND:
246				ZERO_EAX();
247				MOVid(ECX, ins->k);
248				ADDrd(ECX, EDX);
249				CMPodd(ECX, EBP, 0x10);
250				JLEb(5);
251				POP(EBX);
252				POP(ESI);
253				POP(EDI);
254				LEAVE_RET();
255				MOVobb(AL, EBX, ECX);
256				break;
257
258			case BPF_LDX|BPF_MSH|BPF_B:
259				MOVid(ECX, ins->k);
260				CMPodd(ECX, EBP, 0x10);
261				JLEb(7);
262				ZERO_EAX();
263				POP(EBX);
264				POP(ESI);
265				POP(EDI);
266				LEAVE_RET();
267				ZERO_EDX();
268				MOVobb(DL, EBX, ECX);
269				ANDib(DL, 0xf);
270				SHLib(EDX, 2);
271				break;
272
273			case BPF_LD|BPF_IMM:
274				MOVid(EAX, ins->k);
275				break;
276
277			case BPF_LDX|BPF_IMM:
278				MOVid(EDX, ins->k);
279				break;
280
281			case BPF_LD|BPF_MEM:
282				MOVid(ECX, (uintptr_t)mem);
283				MOVid(ESI, ins->k * 4);
284				MOVobd(EAX, ECX, ESI);
285				break;
286
287			case BPF_LDX|BPF_MEM:
288				MOVid(ECX, (uintptr_t)mem);
289				MOVid(ESI, ins->k * 4);
290				MOVobd(EDX, ECX, ESI);
291				break;
292
293			case BPF_ST:
294				/*
295				 * XXX this command and the following could
296				 * be optimized if the previous instruction
297				 * was already of this type
298				 */
299				MOVid(ECX, (uintptr_t)mem);
300				MOVid(ESI, ins->k * 4);
301				MOVomd(ECX, ESI, EAX);
302				break;
303
304			case BPF_STX:
305				MOVid(ECX, (uintptr_t)mem);
306				MOVid(ESI, ins->k * 4);
307				MOVomd(ECX, ESI, EDX);
308				break;
309
310			case BPF_JMP|BPF_JA:
311				JMP(stream.refs[stream.bpf_pc + ins->k] -
312				    stream.refs[stream.bpf_pc]);
313				break;
314
315			case BPF_JMP|BPF_JGT|BPF_K:
316				CMPid(EAX, ins->k);
317				/* 5 is the size of the following JMP */
318				JG(stream.refs[stream.bpf_pc + ins->jt] -
319				    stream.refs[stream.bpf_pc] + 5 );
320				JMP(stream.refs[stream.bpf_pc + ins->jf] -
321				    stream.refs[stream.bpf_pc]);
322				break;
323
324			case BPF_JMP|BPF_JGE|BPF_K:
325				CMPid(EAX, ins->k);
326				JGE(stream.refs[stream.bpf_pc + ins->jt] -
327				    stream.refs[stream.bpf_pc] + 5);
328				JMP(stream.refs[stream.bpf_pc + ins->jf] -
329				    stream.refs[stream.bpf_pc]);
330				break;
331
332			case BPF_JMP|BPF_JEQ|BPF_K:
333				CMPid(EAX, ins->k);
334				JE(stream.refs[stream.bpf_pc + ins->jt] -
335				    stream.refs[stream.bpf_pc] + 5);
336				JMP(stream.refs[stream.bpf_pc + ins->jf] -
337				    stream.refs[stream.bpf_pc]);
338				break;
339
340			case BPF_JMP|BPF_JSET|BPF_K:
341				MOVrd(ECX, EAX);
342				ANDid(ECX, ins->k);
343				JE(stream.refs[stream.bpf_pc + ins->jf] -
344				    stream.refs[stream.bpf_pc] + 5);
345				JMP(stream.refs[stream.bpf_pc + ins->jt] -
346				    stream.refs[stream.bpf_pc]);
347				break;
348
349			case BPF_JMP|BPF_JGT|BPF_X:
350				CMPrd(EAX, EDX);
351				JA(stream.refs[stream.bpf_pc + ins->jt] -
352				    stream.refs[stream.bpf_pc] + 5);
353				JMP(stream.refs[stream.bpf_pc + ins->jf] -
354				    stream.refs[stream.bpf_pc]);
355				break;
356
357			case BPF_JMP|BPF_JGE|BPF_X:
358				CMPrd(EAX, EDX);
359				JAE(stream.refs[stream.bpf_pc + ins->jt] -
360				    stream.refs[stream.bpf_pc] + 5);
361				JMP(stream.refs[stream.bpf_pc + ins->jf] -
362				    stream.refs[stream.bpf_pc]);
363				break;
364
365			case BPF_JMP|BPF_JEQ|BPF_X:
366				CMPrd(EAX, EDX);
367				JE(stream.refs[stream.bpf_pc + ins->jt] -
368				    stream.refs[stream.bpf_pc] + 5);
369				JMP(stream.refs[stream.bpf_pc + ins->jf] -
370				    stream.refs[stream.bpf_pc]);
371				break;
372
373			case BPF_JMP|BPF_JSET|BPF_X:
374				MOVrd(ECX, EAX);
375				ANDrd(ECX, EDX);
376				JE(stream.refs[stream.bpf_pc + ins->jf] -
377				    stream.refs[stream.bpf_pc] + 5);
378				JMP(stream.refs[stream.bpf_pc + ins->jt] -
379				    stream.refs[stream.bpf_pc]);
380				break;
381
382			case BPF_ALU|BPF_ADD|BPF_X:
383				ADDrd(EAX, EDX);
384				break;
385
386			case BPF_ALU|BPF_SUB|BPF_X:
387				SUBrd(EAX, EDX);
388				break;
389
390			case BPF_ALU|BPF_MUL|BPF_X:
391				MOVrd(ECX, EDX);
392				MULrd(EDX);
393				MOVrd(EDX, ECX);
394				break;
395
396			case BPF_ALU|BPF_DIV|BPF_X:
397				CMPid(EDX, 0);
398				JNEb(7);
399				ZERO_EAX();
400				POP(EBX);
401				POP(ESI);
402				POP(EDI);
403				LEAVE_RET();
404				MOVrd(ECX, EDX);
405				ZERO_EDX();
406				DIVrd(ECX);
407				MOVrd(EDX, ECX);
408				break;
409
410			case BPF_ALU|BPF_AND|BPF_X:
411				ANDrd(EAX, EDX);
412				break;
413
414			case BPF_ALU|BPF_OR|BPF_X:
415				ORrd(EAX, EDX);
416				break;
417
418			case BPF_ALU|BPF_LSH|BPF_X:
419				MOVrd(ECX, EDX);
420				SHL_CLrb(EAX);
421				break;
422
423			case BPF_ALU|BPF_RSH|BPF_X:
424				MOVrd(ECX, EDX);
425				SHR_CLrb(EAX);
426				break;
427
428			case BPF_ALU|BPF_ADD|BPF_K:
429				ADD_EAXi(ins->k);
430				break;
431
432			case BPF_ALU|BPF_SUB|BPF_K:
433				SUB_EAXi(ins->k);
434				break;
435
436			case BPF_ALU|BPF_MUL|BPF_K:
437				MOVrd(ECX, EDX);
438				MOVid(EDX, ins->k);
439				MULrd(EDX);
440				MOVrd(EDX, ECX);
441				break;
442
443			case BPF_ALU|BPF_DIV|BPF_K:
444				MOVrd(ECX, EDX);
445				ZERO_EDX();
446				MOVid(ESI, ins->k);
447				DIVrd(ESI);
448				MOVrd(EDX, ECX);
449				break;
450
451			case BPF_ALU|BPF_AND|BPF_K:
452				ANDid(EAX, ins->k);
453				break;
454
455			case BPF_ALU|BPF_OR|BPF_K:
456				ORid(EAX, ins->k);
457				break;
458
459			case BPF_ALU|BPF_LSH|BPF_K:
460				SHLib(EAX, (ins->k) & 255);
461				break;
462
463			case BPF_ALU|BPF_RSH|BPF_K:
464				SHRib(EAX, (ins->k) & 255);
465				break;
466
467			case BPF_ALU|BPF_NEG:
468				NEGd(EAX);
469				break;
470
471			case BPF_MISC|BPF_TAX:
472				MOVrd(EDX, EAX);
473				break;
474
475			case BPF_MISC|BPF_TXA:
476				MOVrd(EAX, EDX);
477				break;
478			}
479			ins++;
480		}
481
482		pass++;
483		if (pass == 2)
484			break;
485
486		stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT);
487		if (stream.ibuf == NULL) {
488			free(stream.refs, M_BPFJIT);
489			return NULL;
490		}
491
492		/*
493		 * modify the reference table to contain the offsets and
494		 * not the lengths of the instructions
495		 */
496		for (i = 1; i < nins + 1; i++)
497			stream.refs[i] += stream.refs[i - 1];
498
499		/* Reset the counters */
500		stream.cur_ip = 0;
501		stream.bpf_pc = 0;
502
503		/* the second pass creates the actual code */
504		emitm = emit_code;
505	}
506
507	/*
508	 * the reference table is needed only during compilation,
509	 * now we can free it
510	 */
511	free(stream.refs, M_BPFJIT);
512
513	return (bpf_filter_func)stream.ibuf;
514}
515