bpf_jit_machdep.c revision 182173 
1115013Smarcel/*-
2160157Smarcel * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
3121642Smarcel * Copyright (C) 2005-2008 Jung-uk Kim <jkim@FreeBSD.org>
4121642Smarcel * All rights reserved.
5121642Smarcel *
6121642Smarcel * Redistribution and use in source and binary forms, with or without
7121642Smarcel * modification, are permitted provided that the following conditions
8121642Smarcel * are met:
9121642Smarcel *
10121642Smarcel * 1. Redistributions of source code must retain the above copyright
11115013Smarcel * notice, this list of conditions and the following disclaimer.
12121642Smarcel * 2. Redistributions in binary form must reproduce the above copyright
13121642Smarcel * notice, this list of conditions and the following disclaimer in the
14121642Smarcel * documentation and/or other materials provided with the distribution.
15121642Smarcel * 3. Neither the name of the Politecnico di Torino nor the names of its
16121642Smarcel * contributors may be used to endorse or promote products derived from
17121642Smarcel * this software without specific prior written permission.
18121642Smarcel *
19121642Smarcel * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20121642Smarcel * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21121642Smarcel * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22121642Smarcel * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23121642Smarcel * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24121642Smarcel * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25160163Smarcel * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26115013Smarcel * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27160163Smarcel * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28115013Smarcel * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29115013Smarcel * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30115013Smarcel */
31115013Smarcel
32115013Smarcel#include <sys/cdefs.h>
33160163Smarcel__FBSDID("$FreeBSD: head/sys/i386/i386/bpf_jit_machdep.c 182173 2008-08-25 20:43:13Z jkim $");
34160163Smarcel
35160163Smarcel#ifdef _KERNEL
36115013Smarcel#include "opt_bpf.h"
37160163Smarcel#include <sys/param.h>
38160163Smarcel#include <sys/systm.h>
39160163Smarcel#include <sys/kernel.h>
40160163Smarcel#include <sys/socket.h>
41160163Smarcel#include <sys/malloc.h>
42160163Smarcel#include <net/if.h>
43160163Smarcel#else
44160163Smarcel#include <stdlib.h>
45160163Smarcel#endif
46160163Smarcel
47160163Smarcel#include <sys/types.h>
48160163Smarcel
49160163Smarcel#include <net/bpf.h>
50160163Smarcel#include <net/bpf_jitter.h>
51160163Smarcel
52160163Smarcel#include <i386/i386/bpf_jit_machdep.h>
53160163Smarcel
54160163Smarcelbpf_filter_func	bpf_jit_compile(struct bpf_insn *, u_int, int *);
55160163Smarcel
56160163Smarcel/*
57160163Smarcel * emit routine to update the jump table
58160163Smarcel */
59160163Smarcelstatic void
60160163Smarcelemit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
61160157Smarcel{
62129059Smarcel
63160157Smarcel	(stream->refs)[stream->bpf_pc] += len;
64160157Smarcel	stream->cur_ip += len;
65160157Smarcel}
66160157Smarcel
67160157Smarcel/*
68129059Smarcel * emit routine to output the actual binary code
69129059Smarcel */
70115013Smarcelstatic void
71115013Smarcelemit_code(bpf_bin_stream *stream, u_int value, u_int len)
72115013Smarcel{
73115013Smarcel
74115013Smarcel	switch (len) {
75115013Smarcel	case 1:
76115013Smarcel		stream->ibuf[stream->cur_ip] = (u_char)value;
77115013Smarcel		stream->cur_ip++;
78115013Smarcel		break;
79115013Smarcel
80115013Smarcel	case 2:
81115013Smarcel		*((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
82115013Smarcel		stream->cur_ip += 2;
83115013Smarcel		break;
84115013Smarcel
85115013Smarcel	case 4:
86115013Smarcel		*((u_int *)(stream->ibuf + stream->cur_ip)) = value;
87115013Smarcel		stream->cur_ip += 4;
88115013Smarcel		break;
89115013Smarcel	}
90115013Smarcel
91160157Smarcel	return;
92115013Smarcel}
93115013Smarcel
94115013Smarcel/*
95115013Smarcel * Function that does the real stuff
96115013Smarcel */
97115013Smarcelbpf_filter_func
98115013Smarcelbpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem)
99115013Smarcel{
100115013Smarcel	struct bpf_insn *ins;
101115013Smarcel	u_int i, pass;
102120925Smarcel	bpf_bin_stream stream;
103120925Smarcel
104115013Smarcel	/*
105115013Smarcel	 * NOTE: do not modify the name of this variable, as it's used by
106115013Smarcel	 * the macros to emit code.
107115013Smarcel	 */
108160163Smarcel	emit_func emitm;
109115013Smarcel
110115013Smarcel	/* Do not compile an empty filter. */
111115013Smarcel	if (nins == 0)
112115013Smarcel		return (NULL);
113115013Smarcel
114115013Smarcel	/* Allocate the reference table for the jumps */
115115013Smarcel#ifdef _KERNEL
116115013Smarcel	stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int),
117115013Smarcel	    M_BPFJIT, M_NOWAIT);
118115013Smarcel#else
119115013Smarcel	stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int));
120115013Smarcel#endif
121115013Smarcel	if (stream.refs == NULL)
122115013Smarcel		return (NULL);
123115013Smarcel
124115013Smarcel	/* Reset the reference table */
125115013Smarcel	for (i = 0; i < nins + 1; i++)
126115013Smarcel		stream.refs[i] = 0;
127115013Smarcel
128115013Smarcel	stream.cur_ip = 0;
129115013Smarcel	stream.bpf_pc = 0;
130115013Smarcel
131115013Smarcel	/*
132115013Smarcel	 * the first pass will emit the lengths of the instructions
133115013Smarcel	 * to create the reference table
134115013Smarcel	 */
135115013Smarcel	emitm = emit_length;
136115013Smarcel
137115013Smarcel	pass = 0;
138115013Smarcel	for (;;) {
139115013Smarcel		ins = prog;
140115013Smarcel
141115013Smarcel		/* create the procedure header */
142115013Smarcel		PUSH(EBP);
143115013Smarcel		MOVrd(ESP, EBP);
144115013Smarcel		PUSH(EDI);
145115013Smarcel		PUSH(ESI);
146115013Smarcel		PUSH(EBX);
147115013Smarcel		MOVodd(8, EBP, EBX);
148115013Smarcel		MOVodd(16, EBP, EDI);
149115013Smarcel
150115013Smarcel		for (i = 0; i < nins; i++) {
151115013Smarcel			stream.bpf_pc++;
152115013Smarcel
153115013Smarcel			switch (ins->code) {
154115013Smarcel			default:
155115013Smarcel#ifdef _KERNEL
156115013Smarcel				return (NULL);
157115013Smarcel#else
158115013Smarcel				abort();
159115013Smarcel#endif
160115013Smarcel
161115013Smarcel			case BPF_RET|BPF_K:
162115013Smarcel				MOVid(ins->k, EAX);
163115013Smarcel				POP(EBX);
164115013Smarcel				POP(ESI);
165115013Smarcel				POP(EDI);
166115013Smarcel				LEAVE_RET();
167115013Smarcel				break;
168115013Smarcel
169115013Smarcel			case BPF_RET|BPF_A:
170115013Smarcel				POP(EBX);
171115013Smarcel				POP(ESI);
172115013Smarcel				POP(EDI);
173115013Smarcel				LEAVE_RET();
174115013Smarcel				break;
175115013Smarcel
176115013Smarcel			case BPF_LD|BPF_W|BPF_ABS:
177115013Smarcel				MOVid(ins->k, ESI);
178115013Smarcel				CMPrd(EDI, ESI);
179115013Smarcel				JAb(12);
180115013Smarcel				MOVrd(EDI, ECX);
181115013Smarcel				SUBrd(ESI, ECX);
182115013Smarcel				CMPid(sizeof(int32_t), ECX);
183160163Smarcel				JAEb(7);
184115013Smarcel				ZEROrd(EAX);
185115013Smarcel				POP(EBX);
186115013Smarcel				POP(ESI);
187115013Smarcel				POP(EDI);
188115013Smarcel				LEAVE_RET();
189115013Smarcel				MOVobd(EBX, ESI, EAX);
190115013Smarcel				BSWAP(EAX);
191115013Smarcel				break;
192115013Smarcel
193115013Smarcel			case BPF_LD|BPF_H|BPF_ABS:
194115013Smarcel				ZEROrd(EAX);
195115013Smarcel				MOVid(ins->k, ESI);
196115013Smarcel				CMPrd(EDI, ESI);
197115013Smarcel				JAb(12);
198115013Smarcel				MOVrd(EDI, ECX);
199115013Smarcel				SUBrd(ESI, ECX);
200115013Smarcel				CMPid(sizeof(int16_t), ECX);
201115013Smarcel				JAEb(5);
202115013Smarcel				POP(EBX);
203115013Smarcel				POP(ESI);
204115013Smarcel				POP(EDI);
205115013Smarcel				LEAVE_RET();
206115013Smarcel				MOVobw(EBX, ESI, AX);
207115013Smarcel				SWAP_AX();
208115013Smarcel				break;
209115013Smarcel
210115013Smarcel			case BPF_LD|BPF_B|BPF_ABS:
211115013Smarcel				ZEROrd(EAX);
212115013Smarcel				MOVid(ins->k, ESI);
213115013Smarcel				CMPrd(EDI, ESI);
214115013Smarcel				JBb(5);
215115013Smarcel				POP(EBX);
216115013Smarcel				POP(ESI);
217115013Smarcel				POP(EDI);
218115013Smarcel				LEAVE_RET();
219115013Smarcel				MOVobb(EBX, ESI, AL);
220115013Smarcel				break;
221115013Smarcel
222115013Smarcel			case BPF_LD|BPF_W|BPF_LEN:
223115013Smarcel				MOVodd(12, EBP, EAX);
224115013Smarcel				break;
225115013Smarcel
226115013Smarcel			case BPF_LDX|BPF_W|BPF_LEN:
227115013Smarcel				MOVodd(12, EBP, EDX);
228115013Smarcel				break;
229115013Smarcel
230115013Smarcel			case BPF_LD|BPF_W|BPF_IND:
231115013Smarcel				CMPrd(EDI, EDX);
232115013Smarcel				JAb(27);
233115013Smarcel				MOVid(ins->k, ESI);
234115013Smarcel				MOVrd(EDI, ECX);
235115013Smarcel				SUBrd(EDX, ECX);
236115013Smarcel				CMPrd(ESI, ECX);
237115013Smarcel				JBb(14);
238115013Smarcel				ADDrd(EDX, ESI);
239115013Smarcel				MOVrd(EDI, ECX);
240115013Smarcel				SUBrd(ESI, ECX);
241115013Smarcel				CMPid(sizeof(int32_t), ECX);
242115013Smarcel				JAEb(7);
243115013Smarcel				ZEROrd(EAX);
244115013Smarcel				POP(EBX);
245115013Smarcel				POP(ESI);
246115013Smarcel				POP(EDI);
247115013Smarcel				LEAVE_RET();
248115013Smarcel				MOVobd(EBX, ESI, EAX);
249115013Smarcel				BSWAP(EAX);
250115013Smarcel				break;
251115013Smarcel
252115013Smarcel			case BPF_LD|BPF_H|BPF_IND:
253115013Smarcel				ZEROrd(EAX);
254115013Smarcel				CMPrd(EDI, EDX);
255115013Smarcel				JAb(27);
256115013Smarcel				MOVid(ins->k, ESI);
257115013Smarcel				MOVrd(EDI, ECX);
258115013Smarcel				SUBrd(EDX, ECX);
259115013Smarcel				CMPrd(ESI, ECX);
260115013Smarcel				JBb(14);
261115013Smarcel				ADDrd(EDX, ESI);
262115013Smarcel				MOVrd(EDI, ECX);
263115013Smarcel				SUBrd(ESI, ECX);
264115013Smarcel				CMPid(sizeof(int16_t), ECX);
265115013Smarcel				JAEb(5);
266115013Smarcel				POP(EBX);
267160163Smarcel				POP(ESI);
268115013Smarcel				POP(EDI);
269115013Smarcel				LEAVE_RET();
270115013Smarcel				MOVobw(EBX, ESI, AX);
271115013Smarcel				SWAP_AX();
272115013Smarcel				break;
273115013Smarcel
274115013Smarcel			case BPF_LD|BPF_B|BPF_IND:
275115013Smarcel				ZEROrd(EAX);
276115013Smarcel				CMPrd(EDI, EDX);
277115013Smarcel				JAEb(13);
278115013Smarcel				MOVid(ins->k, ESI);
279115013Smarcel				MOVrd(EDI, ECX);
280115013Smarcel				SUBrd(EDX, ECX);
281115013Smarcel				CMPrd(ESI, ECX);
282115013Smarcel				JAb(5);
283115013Smarcel				POP(EBX);
284115013Smarcel				POP(ESI);
285115013Smarcel				POP(EDI);
286115013Smarcel				LEAVE_RET();
287115013Smarcel				ADDrd(EDX, ESI);
288115013Smarcel				MOVobb(EBX, ESI, AL);
289115013Smarcel				break;
290115013Smarcel
291115013Smarcel			case BPF_LDX|BPF_MSH|BPF_B:
292115013Smarcel				MOVid(ins->k, ESI);
293115013Smarcel				CMPrd(EDI, ESI);
294115013Smarcel				JBb(7);
295115013Smarcel				ZEROrd(EAX);
296115013Smarcel				POP(EBX);
297115013Smarcel				POP(ESI);
298115013Smarcel				POP(EDI);
299115013Smarcel				LEAVE_RET();
300115013Smarcel				ZEROrd(EDX);
301115013Smarcel				MOVobb(EBX, ESI, DL);
302115013Smarcel				ANDib(0x0f, DL);
303115013Smarcel				SHLib(2, EDX);
304160157Smarcel				break;
305160157Smarcel
306160157Smarcel			case BPF_LD|BPF_IMM:
307160157Smarcel				MOVid(ins->k, EAX);
308160157Smarcel				break;
309160157Smarcel
310115013Smarcel			case BPF_LDX|BPF_IMM:
311115013Smarcel				MOVid(ins->k, EDX);
312115013Smarcel				break;
313115013Smarcel
314115013Smarcel			case BPF_LD|BPF_MEM:
315115013Smarcel				MOVid((uintptr_t)mem, ECX);
316				MOVid(ins->k * 4, ESI);
317				MOVobd(ECX, ESI, EAX);
318				break;
319
320			case BPF_LDX|BPF_MEM:
321				MOVid((uintptr_t)mem, ECX);
322				MOVid(ins->k * 4, ESI);
323				MOVobd(ECX, ESI, EDX);
324				break;
325
326			case BPF_ST:
327				/*
328				 * XXX this command and the following could
329				 * be optimized if the previous instruction
330				 * was already of this type
331				 */
332				MOVid((uintptr_t)mem, ECX);
333				MOVid(ins->k * 4, ESI);
334				MOVomd(EAX, ECX, ESI);
335				break;
336
337			case BPF_STX:
338				MOVid((uintptr_t)mem, ECX);
339				MOVid(ins->k * 4, ESI);
340				MOVomd(EDX, ECX, ESI);
341				break;
342
343			case BPF_JMP|BPF_JA:
344				JMP(stream.refs[stream.bpf_pc + ins->k] -
345				    stream.refs[stream.bpf_pc]);
346				break;
347
348			case BPF_JMP|BPF_JGT|BPF_K:
349				if (ins->jt == 0 && ins->jf == 0)
350					break;
351				CMPid(ins->k, EAX);
352				JCC(JA, JBE);
353				break;
354
355			case BPF_JMP|BPF_JGE|BPF_K:
356				if (ins->jt == 0 && ins->jf == 0)
357					break;
358				CMPid(ins->k, EAX);
359				JCC(JAE, JB);
360				break;
361
362			case BPF_JMP|BPF_JEQ|BPF_K:
363				if (ins->jt == 0 && ins->jf == 0)
364					break;
365				CMPid(ins->k, EAX);
366				JCC(JE, JNE);
367				break;
368
369			case BPF_JMP|BPF_JSET|BPF_K:
370				if (ins->jt == 0 && ins->jf == 0)
371					break;
372				TESTid(ins->k, EAX);
373				JCC(JNE, JE);
374				break;
375
376			case BPF_JMP|BPF_JGT|BPF_X:
377				if (ins->jt == 0 && ins->jf == 0)
378					break;
379				CMPrd(EDX, EAX);
380				JCC(JA, JBE);
381				break;
382
383			case BPF_JMP|BPF_JGE|BPF_X:
384				if (ins->jt == 0 && ins->jf == 0)
385					break;
386				CMPrd(EDX, EAX);
387				JCC(JAE, JB);
388				break;
389
390			case BPF_JMP|BPF_JEQ|BPF_X:
391				if (ins->jt == 0 && ins->jf == 0)
392					break;
393				CMPrd(EDX, EAX);
394				JCC(JE, JNE);
395				break;
396
397			case BPF_JMP|BPF_JSET|BPF_X:
398				if (ins->jt == 0 && ins->jf == 0)
399					break;
400				TESTrd(EDX, EAX);
401				JCC(JNE, JE);
402				break;
403
404			case BPF_ALU|BPF_ADD|BPF_X:
405				ADDrd(EDX, EAX);
406				break;
407
408			case BPF_ALU|BPF_SUB|BPF_X:
409				SUBrd(EDX, EAX);
410				break;
411
412			case BPF_ALU|BPF_MUL|BPF_X:
413				MOVrd(EDX, ECX);
414				MULrd(EDX);
415				MOVrd(ECX, EDX);
416				break;
417
418			case BPF_ALU|BPF_DIV|BPF_X:
419				TESTrd(EDX, EDX);
420				JNEb(7);
421				ZEROrd(EAX);
422				POP(EBX);
423				POP(ESI);
424				POP(EDI);
425				LEAVE_RET();
426				MOVrd(EDX, ECX);
427				ZEROrd(EDX);
428				DIVrd(ECX);
429				MOVrd(ECX, EDX);
430				break;
431
432			case BPF_ALU|BPF_AND|BPF_X:
433				ANDrd(EDX, EAX);
434				break;
435
436			case BPF_ALU|BPF_OR|BPF_X:
437				ORrd(EDX, EAX);
438				break;
439
440			case BPF_ALU|BPF_LSH|BPF_X:
441				MOVrd(EDX, ECX);
442				SHL_CLrb(EAX);
443				break;
444
445			case BPF_ALU|BPF_RSH|BPF_X:
446				MOVrd(EDX, ECX);
447				SHR_CLrb(EAX);
448				break;
449
450			case BPF_ALU|BPF_ADD|BPF_K:
451				ADD_EAXi(ins->k);
452				break;
453
454			case BPF_ALU|BPF_SUB|BPF_K:
455				SUB_EAXi(ins->k);
456				break;
457
458			case BPF_ALU|BPF_MUL|BPF_K:
459				MOVrd(EDX, ECX);
460				MOVid(ins->k, EDX);
461				MULrd(EDX);
462				MOVrd(ECX, EDX);
463				break;
464
465			case BPF_ALU|BPF_DIV|BPF_K:
466				MOVrd(EDX, ECX);
467				ZEROrd(EDX);
468				MOVid(ins->k, ESI);
469				DIVrd(ESI);
470				MOVrd(ECX, EDX);
471				break;
472
473			case BPF_ALU|BPF_AND|BPF_K:
474				ANDid(ins->k, EAX);
475				break;
476
477			case BPF_ALU|BPF_OR|BPF_K:
478				ORid(ins->k, EAX);
479				break;
480
481			case BPF_ALU|BPF_LSH|BPF_K:
482				SHLib((ins->k) & 0xff, EAX);
483				break;
484
485			case BPF_ALU|BPF_RSH|BPF_K:
486				SHRib((ins->k) & 0xff, EAX);
487				break;
488
489			case BPF_ALU|BPF_NEG:
490				NEGd(EAX);
491				break;
492
493			case BPF_MISC|BPF_TAX:
494				MOVrd(EAX, EDX);
495				break;
496
497			case BPF_MISC|BPF_TXA:
498				MOVrd(EDX, EAX);
499				break;
500			}
501			ins++;
502		}
503
504		pass++;
505		if (pass == 2)
506			break;
507
508#ifdef _KERNEL
509		stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT);
510		if (stream.ibuf == NULL) {
511			free(stream.refs, M_BPFJIT);
512			return (NULL);
513		}
514#else
515		stream.ibuf = (char *)malloc(stream.cur_ip);
516		if (stream.ibuf == NULL) {
517			free(stream.refs);
518			return (NULL);
519		}
520#endif
521
522		/*
523		 * modify the reference table to contain the offsets and
524		 * not the lengths of the instructions
525		 */
526		for (i = 1; i < nins + 1; i++)
527			stream.refs[i] += stream.refs[i - 1];
528
529		/* Reset the counters */
530		stream.cur_ip = 0;
531		stream.bpf_pc = 0;
532
533		/* the second pass creates the actual code */
534		emitm = emit_code;
535	}
536
537	/*
538	 * the reference table is needed only during compilation,
539	 * now we can free it
540	 */
541#ifdef _KERNEL
542	free(stream.refs, M_BPFJIT);
543#else
544	free(stream.refs);
545#endif
546
547	return ((bpf_filter_func)stream.ibuf);
548}
549