bpf_jit_machdep.c revision 179967 
1226031Sstas/*-
2226031Sstas * Copyright (c) 2002 - 2003 NetGroup, Politecnico di Torino (Italy)
3226031Sstas * Copyright (c) 2005 Jung-uk Kim <jkim@FreeBSD.org>
4226031Sstas * All rights reserved.
5226031Sstas *
6226031Sstas * Redistribution and use in source and binary forms, with or without
7226031Sstas * modification, are permitted provided that the following conditions
8226031Sstas * are met:
9226031Sstas *
10226031Sstas * 1. Redistributions of source code must retain the above copyright
11226031Sstas * notice, this list of conditions and the following disclaimer.
12226031Sstas * 2. Redistributions in binary form must reproduce the above copyright
13226031Sstas * notice, this list of conditions and the following disclaimer in the
14226031Sstas * documentation and/or other materials provided with the distribution.
15226031Sstas * 3. Neither the name of the Politecnico di Torino nor the names of its
16226031Sstas * contributors may be used to endorse or promote products derived from
17226031Sstas * this software without specific prior written permission.
18226031Sstas *
19226031Sstas * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20226031Sstas * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21226031Sstas * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22226031Sstas * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23226031Sstas * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24226031Sstas * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25226031Sstas * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26226031Sstas * DATA, OR PROFITS; OR BUSINESS intERRUPTION) HOWEVER CAUSED AND ON ANY
27226031Sstas * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28226031Sstas * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29226031Sstas * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30226031Sstas */
31226031Sstas
32226031Sstas#include <sys/cdefs.h>
33226031Sstas__FBSDID("$FreeBSD: head/sys/amd64/amd64/bpf_jit_machdep.c 179967 2008-06-23 23:09:52Z jkim $");
34226031Sstas
35226031Sstas#include "opt_bpf.h"
36226031Sstas
37226031Sstas#include <sys/param.h>
38226031Sstas#include <sys/systm.h>
39226031Sstas#include <sys/kernel.h>
40226031Sstas#include <sys/types.h>
41226031Sstas#include <sys/socket.h>
42226031Sstas#include <sys/malloc.h>
43226031Sstas
44226031Sstas#include <net/if.h>
45226031Sstas#include <net/bpf.h>
46226031Sstas#include <net/bpf_jitter.h>
47226031Sstas
48226031Sstas#include <amd64/amd64/bpf_jit_machdep.h>
49226031Sstas
50226031Sstasbpf_filter_func	bpf_jit_compile(struct bpf_insn *, u_int, int *);
51226031Sstas
52226031Sstas/*
53226031Sstas * emit routine to update the jump table
54226031Sstas */
55226031Sstasstatic void
56226031Sstasemit_length(bpf_bin_stream *stream, u_int value, u_int len)
57226031Sstas{
58226031Sstas
59226031Sstas	(stream->refs)[stream->bpf_pc] += len;
60226031Sstas	stream->cur_ip += len;
61226031Sstas}
62226031Sstas
63226031Sstas/*
64226031Sstas * emit routine to output the actual binary code
65226031Sstas */
66226031Sstasstatic void
67226031Sstasemit_code(bpf_bin_stream *stream, u_int value, u_int len)
68226031Sstas{
69226031Sstas
70226031Sstas	switch (len) {
71226031Sstas	case 1:
72226031Sstas		stream->ibuf[stream->cur_ip] = (u_char)value;
73226031Sstas		stream->cur_ip++;
74226031Sstas		break;
75226031Sstas
76226031Sstas	case 2:
77226031Sstas		*((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
78226031Sstas		stream->cur_ip += 2;
79226031Sstas		break;
80226031Sstas
81226031Sstas	case 4:
82226031Sstas		*((u_int *)(stream->ibuf + stream->cur_ip)) = value;
83226031Sstas		stream->cur_ip += 4;
84226031Sstas		break;
85226031Sstas	}
86226031Sstas
87226031Sstas	return;
88226031Sstas}
89226031Sstas
90226031Sstas/*
91226031Sstas * Function that does the real stuff
92226031Sstas */
93226031Sstasbpf_filter_func
94226031Sstasbpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem)
95226031Sstas{
96226031Sstas	struct bpf_insn *ins;
97226031Sstas	u_int i, pass;
98226031Sstas	bpf_bin_stream stream;
99226031Sstas
100226031Sstas	/*
101226031Sstas	 * NOTE: do not modify the name of this variable, as it's used by
102226031Sstas	 * the macros to emit code.
103226031Sstas	 */
104226031Sstas	emit_func emitm;
105226031Sstas
106226031Sstas	/* Do not compile an empty filter. */
107226031Sstas	if (nins == 0)
108226031Sstas		return NULL;
109226031Sstas
110226031Sstas	/* Allocate the reference table for the jumps */
111226031Sstas	stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int),
112226031Sstas	    M_BPFJIT, M_NOWAIT);
113226031Sstas	if (stream.refs == NULL)
114226031Sstas		return NULL;
115226031Sstas
116226031Sstas	/* Reset the reference table */
117226031Sstas	for (i = 0; i < nins + 1; i++)
118226031Sstas		stream.refs[i] = 0;
119226031Sstas
120226031Sstas	stream.cur_ip = 0;
121226031Sstas	stream.bpf_pc = 0;
122226031Sstas
123226031Sstas	/*
124226031Sstas	 * the first pass will emit the lengths of the instructions
125226031Sstas	 * to create the reference table
126226031Sstas	 */
127226031Sstas	emitm = emit_length;
128226031Sstas
129226031Sstas	pass = 0;
130226031Sstas	for (;;) {
131226031Sstas		ins = prog;
132226031Sstas
133226031Sstas		/* create the procedure header */
134226031Sstas		PUSH(RBP);
135226031Sstas		MOVrq(RSP, RBP);
136226031Sstas		MOVdoq(ESI, -8, RBP);
137226031Sstas		MOVdoq(EDX, -12, RBP);
138226031Sstas		PUSH(RBX);
139226031Sstas		MOVrq(RDI, RBX);
140226031Sstas
141226031Sstas		for (i = 0; i < nins; i++) {
142226031Sstas			stream.bpf_pc++;
143226031Sstas
144226031Sstas			switch (ins->code) {
145226031Sstas			default:
146226031Sstas				return NULL;
147226031Sstas
148226031Sstas			case BPF_RET|BPF_K:
149226031Sstas				MOVid(ins->k, EAX);
150226031Sstas				POP(RBX);
151226031Sstas				LEAVE_RET();
152226031Sstas				break;
153226031Sstas
154226031Sstas			case BPF_RET|BPF_A:
155226031Sstas				POP(RBX);
156226031Sstas				LEAVE_RET();
157226031Sstas				break;
158226031Sstas
159226031Sstas			case BPF_LD|BPF_W|BPF_ABS:
160226031Sstas				MOVid(ins->k, ECX);
161226031Sstas				MOVrd(ECX, ESI);
162226031Sstas				ADDib(sizeof(int), ECX);
163226031Sstas				CMPoqd(-12, RBP, ECX);
164226031Sstas				JLEb(5);
165226031Sstas				ZERO_EAX();
166226031Sstas				POP(RBX);
167226031Sstas				LEAVE_RET();
168226031Sstas				MOVobd(RBX, RSI, EAX);
169226031Sstas				BSWAP(EAX);
170226031Sstas				break;
171226031Sstas
172226031Sstas			case BPF_LD|BPF_H|BPF_ABS:
173226031Sstas				ZERO_EAX();
174226031Sstas				MOVid(ins->k, ECX);
175226031Sstas				MOVrd(ECX, ESI);
176226031Sstas				ADDib(sizeof(short), ECX);
177				CMPoqd(-12, RBP, ECX);
178				JLEb(3);
179				POP(RBX);
180				LEAVE_RET();
181				MOVobw(RBX, RSI, AX);
182				SWAP_AX();
183				break;
184
185			case BPF_LD|BPF_B|BPF_ABS:
186				ZERO_EAX();
187				MOVid(ins->k, ECX);
188				CMPoqd(-12, RBP, ECX);
189				JLEb(3);
190				POP(RBX);
191				LEAVE_RET();
192				MOVobb(RBX, RCX, AL);
193				break;
194
195			case BPF_LD|BPF_W|BPF_LEN:
196				MOVoqd(-8, RBP, EAX);
197				break;
198
199			case BPF_LDX|BPF_W|BPF_LEN:
200				MOVoqd(-8, RBP, EDX);
201				break;
202
203			case BPF_LD|BPF_W|BPF_IND:
204				MOVid(ins->k, ECX);
205				ADDrd(EDX, ECX);
206				MOVrd(ECX, ESI);
207				ADDib(sizeof(int), ECX);
208				CMPoqd(-12, RBP, ECX);
209				JLEb(5);
210				ZERO_EAX();
211				POP(RBX);
212				LEAVE_RET();
213				MOVobd(RBX, RSI, EAX);
214				BSWAP(EAX);
215				break;
216
217			case BPF_LD|BPF_H|BPF_IND:
218				ZERO_EAX();
219				MOVid(ins->k, ECX);
220				ADDrd(EDX, ECX);
221				MOVrd(ECX, ESI);
222				ADDib(sizeof(short), ECX);
223				CMPoqd(-12, RBP, ECX);
224				JLEb(3);
225				POP(RBX);
226				LEAVE_RET();
227				MOVobw(RBX, RSI, AX);
228				SWAP_AX();
229				break;
230
231			case BPF_LD|BPF_B|BPF_IND:
232				ZERO_EAX();
233				MOVid(ins->k, ECX);
234				ADDrd(EDX, ECX);
235				CMPoqd(-12, RBP, ECX);
236				JLEb(3);
237				POP(RBX);
238				LEAVE_RET();
239				MOVobb(RBX, RCX, AL);
240				break;
241
242			case BPF_LDX|BPF_MSH|BPF_B:
243				MOVid(ins->k, ECX);
244				CMPoqd(-12, RBP, ECX);
245				JLEb(5);
246				ZERO_EAX();
247				POP(RBX);
248				LEAVE_RET();
249				ZERO_EDX();
250				MOVobb(RBX, RCX, DL);
251				ANDib(0xf, DL);
252				SHLib(2, EDX);
253				break;
254
255			case BPF_LD|BPF_IMM:
256				MOVid(ins->k, EAX);
257				break;
258
259			case BPF_LDX|BPF_IMM:
260				MOVid(ins->k, EDX);
261				break;
262
263			case BPF_LD|BPF_MEM:
264				MOViq((uintptr_t)mem, RCX);
265				MOVid(ins->k * 4, ESI);
266				MOVobd(RCX, RSI, EAX);
267				break;
268
269			case BPF_LDX|BPF_MEM:
270				MOViq((uintptr_t)mem, RCX);
271				MOVid(ins->k * 4, ESI);
272				MOVobd(RCX, RSI, EDX);
273				break;
274
275			case BPF_ST:
276				/*
277				 * XXX this command and the following could
278				 * be optimized if the previous instruction
279				 * was already of this type
280				 */
281				MOViq((uintptr_t)mem, RCX);
282				MOVid(ins->k * 4, ESI);
283				MOVomd(EAX, RCX, RSI);
284				break;
285
286			case BPF_STX:
287				MOViq((uintptr_t)mem, RCX);
288				MOVid(ins->k * 4, ESI);
289				MOVomd(EDX, RCX, RSI);
290				break;
291
292			case BPF_JMP|BPF_JA:
293				JMP(stream.refs[stream.bpf_pc + ins->k] -
294				    stream.refs[stream.bpf_pc]);
295				break;
296
297			case BPF_JMP|BPF_JGT|BPF_K:
298				CMPid(ins->k, EAX);
299				/* 5 is the size of the following JMP */
300				JG(stream.refs[stream.bpf_pc + ins->jt] -
301				    stream.refs[stream.bpf_pc] + 5 );
302				JMP(stream.refs[stream.bpf_pc + ins->jf] -
303				    stream.refs[stream.bpf_pc]);
304				break;
305
306			case BPF_JMP|BPF_JGE|BPF_K:
307				CMPid(ins->k, EAX);
308				JGE(stream.refs[stream.bpf_pc + ins->jt] -
309				    stream.refs[stream.bpf_pc] + 5);
310				JMP(stream.refs[stream.bpf_pc + ins->jf] -
311				    stream.refs[stream.bpf_pc]);
312				break;
313
314			case BPF_JMP|BPF_JEQ|BPF_K:
315				CMPid(ins->k, EAX);
316				JE(stream.refs[stream.bpf_pc + ins->jt] -
317				    stream.refs[stream.bpf_pc] + 5);
318				JMP(stream.refs[stream.bpf_pc + ins->jf] -
319				    stream.refs[stream.bpf_pc]);
320				break;
321
322			case BPF_JMP|BPF_JSET|BPF_K:
323				MOVrd(EAX, ECX);
324				ANDid(ins->k, ECX);
325				JE(stream.refs[stream.bpf_pc + ins->jf] -
326				    stream.refs[stream.bpf_pc] + 5);
327				JMP(stream.refs[stream.bpf_pc + ins->jt] -
328				    stream.refs[stream.bpf_pc]);
329				break;
330
331			case BPF_JMP|BPF_JGT|BPF_X:
332				CMPrd(EDX, EAX);
333				JA(stream.refs[stream.bpf_pc + ins->jt] -
334				    stream.refs[stream.bpf_pc] + 5);
335				JMP(stream.refs[stream.bpf_pc + ins->jf] -
336				    stream.refs[stream.bpf_pc]);
337				break;
338
339			case BPF_JMP|BPF_JGE|BPF_X:
340				CMPrd(EDX, EAX);
341				JAE(stream.refs[stream.bpf_pc + ins->jt] -
342				    stream.refs[stream.bpf_pc] + 5);
343				JMP(stream.refs[stream.bpf_pc + ins->jf] -
344				    stream.refs[stream.bpf_pc]);
345				break;
346
347			case BPF_JMP|BPF_JEQ|BPF_X:
348				CMPrd(EDX, EAX);
349				JE(stream.refs[stream.bpf_pc + ins->jt] -
350				    stream.refs[stream.bpf_pc] + 5);
351				JMP(stream.refs[stream.bpf_pc + ins->jf] -
352				    stream.refs[stream.bpf_pc]);
353				break;
354
355			case BPF_JMP|BPF_JSET|BPF_X:
356				MOVrd(EAX, ECX);
357				ANDrd(EDX, ECX);
358				JE(stream.refs[stream.bpf_pc + ins->jf] -
359				    stream.refs[stream.bpf_pc] + 5);
360				JMP(stream.refs[stream.bpf_pc + ins->jt] -
361				    stream.refs[stream.bpf_pc]);
362				break;
363
364			case BPF_ALU|BPF_ADD|BPF_X:
365				ADDrd(EDX, EAX);
366				break;
367
368			case BPF_ALU|BPF_SUB|BPF_X:
369				SUBrd(EDX, EAX);
370				break;
371
372			case BPF_ALU|BPF_MUL|BPF_X:
373				MOVrd(EDX, ECX);
374				MULrd(EDX);
375				MOVrd(ECX, EDX);
376				break;
377
378			case BPF_ALU|BPF_DIV|BPF_X:
379				CMPid(0, EDX);
380				JNEb(5);
381				ZERO_EAX();
382				POP(RBX);
383				LEAVE_RET();
384				MOVrd(EDX, ECX);
385				ZERO_EDX();
386				DIVrd(ECX);
387				MOVrd(ECX, EDX);
388				break;
389
390			case BPF_ALU|BPF_AND|BPF_X:
391				ANDrd(EDX, EAX);
392				break;
393
394			case BPF_ALU|BPF_OR|BPF_X:
395				ORrd(EDX, EAX);
396				break;
397
398			case BPF_ALU|BPF_LSH|BPF_X:
399				MOVrd(EDX, ECX);
400				SHL_CLrb(EAX);
401				break;
402
403			case BPF_ALU|BPF_RSH|BPF_X:
404				MOVrd(EDX, ECX);
405				SHR_CLrb(EAX);
406				break;
407
408			case BPF_ALU|BPF_ADD|BPF_K:
409				ADD_EAXi(ins->k);
410				break;
411
412			case BPF_ALU|BPF_SUB|BPF_K:
413				SUB_EAXi(ins->k);
414				break;
415
416			case BPF_ALU|BPF_MUL|BPF_K:
417				MOVrd(EDX, ECX);
418				MOVid(ins->k, EDX);
419				MULrd(EDX);
420				MOVrd(ECX, EDX);
421				break;
422
423			case BPF_ALU|BPF_DIV|BPF_K:
424				MOVrd(EDX, ECX);
425				ZERO_EDX();
426				MOVid(ins->k, ESI);
427				DIVrd(ESI);
428				MOVrd(ECX, EDX);
429				break;
430
431			case BPF_ALU|BPF_AND|BPF_K:
432				ANDid(ins->k, EAX);
433				break;
434
435			case BPF_ALU|BPF_OR|BPF_K:
436				ORid(ins->k, EAX);
437				break;
438
439			case BPF_ALU|BPF_LSH|BPF_K:
440				SHLib((ins->k) & 0xff, EAX);
441				break;
442
443			case BPF_ALU|BPF_RSH|BPF_K:
444				SHRib((ins->k) & 0xff, EAX);
445				break;
446
447			case BPF_ALU|BPF_NEG:
448				NEGd(EAX);
449				break;
450
451			case BPF_MISC|BPF_TAX:
452				MOVrd(EAX, EDX);
453				break;
454
455			case BPF_MISC|BPF_TXA:
456				MOVrd(EDX, EAX);
457				break;
458			}
459			ins++;
460		}
461
462		pass++;
463		if (pass == 2)
464			break;
465
466		stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT);
467		if (stream.ibuf == NULL) {
468			free(stream.refs, M_BPFJIT);
469			return NULL;
470		}
471
472		/*
473		 * modify the reference table to contain the offsets and
474		 * not the lengths of the instructions
475		 */
476		for (i = 1; i < nins + 1; i++)
477			stream.refs[i] += stream.refs[i - 1];
478
479		/* Reset the counters */
480		stream.cur_ip = 0;
481		stream.bpf_pc = 0;
482
483		/* the second pass creates the actual code */
484		emitm = emit_code;
485	}
486
487	/*
488	 * the reference table is needed only during compilation,
489	 * now we can free it
490	 */
491	free(stream.refs, M_BPFJIT);
492
493	return (bpf_filter_func)stream.ibuf;
494}
495