1 /*-
2 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
3 * Copyright (C) 2005-2009 Jung-uk Kim <jkim@FreeBSD.org>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the Politecnico di Torino nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD: releng/9.0/sys/amd64/amd64/bpf_jit_machdep.c 207081 2010-04-22 23:47:19Z jkim $");
34
35 #ifdef _KERNEL
36 #include "opt_bpf.h"
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/kernel.h>
40 #include <sys/socket.h>
41 #include <sys/malloc.h>
42 #include <net/if.h>
43 #else
44 #include <stdlib.h>
45 #include <string.h>
46 #include <sys/mman.h>
47 #include <sys/param.h>
48 #endif
49
50 #include <sys/types.h>
51
52 #include <net/bpf.h>
53 #include <net/bpf_jitter.h>
54
55 #include <amd64/amd64/bpf_jit_machdep.h>
56
57 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *);
58
59 /*
60 * Emit routine to update the jump table.
61 */
62 static void
63 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
64 {
65
66 if (stream->refs != NULL)
67 (stream->refs)[stream->bpf_pc] += len;
68 stream->cur_ip += len;
69 }
70
71 /*
72 * Emit routine to output the actual binary code.
73 */
74 static void
75 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
76 {
77
78 switch (len) {
79 case 1:
80 stream->ibuf[stream->cur_ip] = (u_char)value;
81 stream->cur_ip++;
82 break;
83
84 case 2:
85 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
86 stream->cur_ip += 2;
87 break;
88
89 case 4:
90 *((u_int *)(stream->ibuf + stream->cur_ip)) = value;
91 stream->cur_ip += 4;
92 break;
93 }
94
95 return;
96 }
97
98 /*
99 * Scan the filter program and find possible optimization.
100 */
101 static int
102 bpf_jit_optimize(struct bpf_insn *prog, u_int nins)
103 {
104 int flags;
105 u_int i;
106
107 /* Do we return immediately? */
108 if (BPF_CLASS(prog[0].code) == BPF_RET)
109 return (BPF_JIT_FRET);
110
111 for (flags = 0, i = 0; i < nins; i++) {
112 switch (prog[i].code) {
113 case BPF_LD|BPF_W|BPF_ABS:
114 case BPF_LD|BPF_H|BPF_ABS:
115 case BPF_LD|BPF_B|BPF_ABS:
116 case BPF_LD|BPF_W|BPF_IND:
117 case BPF_LD|BPF_H|BPF_IND:
118 case BPF_LD|BPF_B|BPF_IND:
119 case BPF_LDX|BPF_MSH|BPF_B:
120 flags |= BPF_JIT_FPKT;
121 break;
122 case BPF_LD|BPF_MEM:
123 case BPF_LDX|BPF_MEM:
124 case BPF_ST:
125 case BPF_STX:
126 flags |= BPF_JIT_FMEM;
127 break;
128 case BPF_LD|BPF_W|BPF_LEN:
129 case BPF_LDX|BPF_W|BPF_LEN:
130 flags |= BPF_JIT_FLEN;
131 break;
132 case BPF_JMP|BPF_JA:
133 case BPF_JMP|BPF_JGT|BPF_K:
134 case BPF_JMP|BPF_JGE|BPF_K:
135 case BPF_JMP|BPF_JEQ|BPF_K:
136 case BPF_JMP|BPF_JSET|BPF_K:
137 case BPF_JMP|BPF_JGT|BPF_X:
138 case BPF_JMP|BPF_JGE|BPF_X:
139 case BPF_JMP|BPF_JEQ|BPF_X:
140 case BPF_JMP|BPF_JSET|BPF_X:
141 flags |= BPF_JIT_FJMP;
142 break;
143 }
144 if (flags == BPF_JIT_FLAG_ALL)
145 break;
146 }
147
148 return (flags);
149 }
150
151 /*
152 * Function that does the real stuff.
153 */
154 bpf_filter_func
155 bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size)
156 {
157 bpf_bin_stream stream;
158 struct bpf_insn *ins;
159 int flags, fret, fpkt, fmem, fjmp, flen;
160 u_int i, pass;
161
162 /*
163 * NOTE: Do not modify the name of this variable, as it's used by
164 * the macros to emit code.
165 */
166 emit_func emitm;
167
168 flags = bpf_jit_optimize(prog, nins);
169 fret = (flags & BPF_JIT_FRET) != 0;
170 fpkt = (flags & BPF_JIT_FPKT) != 0;
171 fmem = (flags & BPF_JIT_FMEM) != 0;
172 fjmp = (flags & BPF_JIT_FJMP) != 0;
173 flen = (flags & BPF_JIT_FLEN) != 0;
174
175 if (fret)
176 nins = 1;
177
178 memset(&stream, 0, sizeof(stream));
179
180 /* Allocate the reference table for the jumps. */
181 if (fjmp) {
182 #ifdef _KERNEL
183 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
184 M_NOWAIT | M_ZERO);
185 #else
186 stream.refs = calloc(nins + 1, sizeof(u_int));
187 #endif
188 if (stream.refs == NULL)
189 return (NULL);
190 }
191
192 /*
193 * The first pass will emit the lengths of the instructions
194 * to create the reference table.
195 */
196 emitm = emit_length;
197
198 for (pass = 0; pass < 2; pass++) {
199 ins = prog;
200
201 /* Create the procedure header. */
202 if (fmem) {
203 PUSH(RBP);
204 MOVrq(RSP, RBP);
205 SUBib(BPF_MEMWORDS * sizeof(uint32_t), RSP);
206 }
207 if (flen)
208 MOVrd2(ESI, R9D);
209 if (fpkt) {
210 MOVrq2(RDI, R8);
211 MOVrd(EDX, EDI);
212 }
213
214 for (i = 0; i < nins; i++) {
215 stream.bpf_pc++;
216
217 switch (ins->code) {
218 default:
219 #ifdef _KERNEL
220 return (NULL);
221 #else
222 abort();
223 #endif
224
225 case BPF_RET|BPF_K:
226 MOVid(ins->k, EAX);
227 if (fmem)
228 LEAVE();
229 RET();
230 break;
231
232 case BPF_RET|BPF_A:
233 if (fmem)
234 LEAVE();
235 RET();
236 break;
237
238 case BPF_LD|BPF_W|BPF_ABS:
239 MOVid(ins->k, ESI);
240 CMPrd(EDI, ESI);
241 JAb(12);
242 MOVrd(EDI, ECX);
243 SUBrd(ESI, ECX);
244 CMPid(sizeof(int32_t), ECX);
245 if (fmem) {
246 JAEb(4);
247 ZEROrd(EAX);
248 LEAVE();
249 } else {
250 JAEb(3);
251 ZEROrd(EAX);
252 }
253 RET();
254 MOVrq3(R8, RCX);
255 MOVobd(RCX, RSI, EAX);
256 BSWAP(EAX);
257 break;
258
259 case BPF_LD|BPF_H|BPF_ABS:
260 ZEROrd(EAX);
261 MOVid(ins->k, ESI);
262 CMPrd(EDI, ESI);
263 JAb(12);
264 MOVrd(EDI, ECX);
265 SUBrd(ESI, ECX);
266 CMPid(sizeof(int16_t), ECX);
267 if (fmem) {
268 JAEb(2);
269 LEAVE();
270 } else
271 JAEb(1);
272 RET();
273 MOVrq3(R8, RCX);
274 MOVobw(RCX, RSI, AX);
275 SWAP_AX();
276 break;
277
278 case BPF_LD|BPF_B|BPF_ABS:
279 ZEROrd(EAX);
280 MOVid(ins->k, ESI);
281 CMPrd(EDI, ESI);
282 if (fmem) {
283 JBb(2);
284 LEAVE();
285 } else
286 JBb(1);
287 RET();
288 MOVrq3(R8, RCX);
289 MOVobb(RCX, RSI, AL);
290 break;
291
292 case BPF_LD|BPF_W|BPF_LEN:
293 MOVrd3(R9D, EAX);
294 break;
295
296 case BPF_LDX|BPF_W|BPF_LEN:
297 MOVrd3(R9D, EDX);
298 break;
299
300 case BPF_LD|BPF_W|BPF_IND:
301 CMPrd(EDI, EDX);
302 JAb(27);
303 MOVid(ins->k, ESI);
304 MOVrd(EDI, ECX);
305 SUBrd(EDX, ECX);
306 CMPrd(ESI, ECX);
307 JBb(14);
308 ADDrd(EDX, ESI);
309 MOVrd(EDI, ECX);
310 SUBrd(ESI, ECX);
311 CMPid(sizeof(int32_t), ECX);
312 if (fmem) {
313 JAEb(4);
314 ZEROrd(EAX);
315 LEAVE();
316 } else {
317 JAEb(3);
318 ZEROrd(EAX);
319 }
320 RET();
321 MOVrq3(R8, RCX);
322 MOVobd(RCX, RSI, EAX);
323 BSWAP(EAX);
324 break;
325
326 case BPF_LD|BPF_H|BPF_IND:
327 ZEROrd(EAX);
328 CMPrd(EDI, EDX);
329 JAb(27);
330 MOVid(ins->k, ESI);
331 MOVrd(EDI, ECX);
332 SUBrd(EDX, ECX);
333 CMPrd(ESI, ECX);
334 JBb(14);
335 ADDrd(EDX, ESI);
336 MOVrd(EDI, ECX);
337 SUBrd(ESI, ECX);
338 CMPid(sizeof(int16_t), ECX);
339 if (fmem) {
340 JAEb(2);
341 LEAVE();
342 } else
343 JAEb(1);
344 RET();
345 MOVrq3(R8, RCX);
346 MOVobw(RCX, RSI, AX);
347 SWAP_AX();
348 break;
349
350 case BPF_LD|BPF_B|BPF_IND:
351 ZEROrd(EAX);
352 CMPrd(EDI, EDX);
353 JAEb(13);
354 MOVid(ins->k, ESI);
355 MOVrd(EDI, ECX);
356 SUBrd(EDX, ECX);
357 CMPrd(ESI, ECX);
358 if (fmem) {
359 JAb(2);
360 LEAVE();
361 } else
362 JAb(1);
363 RET();
364 MOVrq3(R8, RCX);
365 ADDrd(EDX, ESI);
366 MOVobb(RCX, RSI, AL);
367 break;
368
369 case BPF_LDX|BPF_MSH|BPF_B:
370 MOVid(ins->k, ESI);
371 CMPrd(EDI, ESI);
372 if (fmem) {
373 JBb(4);
374 ZEROrd(EAX);
375 LEAVE();
376 } else {
377 JBb(3);
378 ZEROrd(EAX);
379 }
380 RET();
381 ZEROrd(EDX);
382 MOVrq3(R8, RCX);
383 MOVobb(RCX, RSI, DL);
384 ANDib(0x0f, DL);
385 SHLib(2, EDX);
386 break;
387
388 case BPF_LD|BPF_IMM:
389 MOVid(ins->k, EAX);
390 break;
391
392 case BPF_LDX|BPF_IMM:
393 MOVid(ins->k, EDX);
394 break;
395
396 case BPF_LD|BPF_MEM:
397 MOVid(ins->k * sizeof(uint32_t), ESI);
398 MOVobd(RSP, RSI, EAX);
399 break;
400
401 case BPF_LDX|BPF_MEM:
402 MOVid(ins->k * sizeof(uint32_t), ESI);
403 MOVobd(RSP, RSI, EDX);
404 break;
405
406 case BPF_ST:
407 /*
408 * XXX this command and the following could
409 * be optimized if the previous instruction
410 * was already of this type
411 */
412 MOVid(ins->k * sizeof(uint32_t), ESI);
413 MOVomd(EAX, RSP, RSI);
414 break;
415
416 case BPF_STX:
417 MOVid(ins->k * sizeof(uint32_t), ESI);
418 MOVomd(EDX, RSP, RSI);
419 break;
420
421 case BPF_JMP|BPF_JA:
422 JUMP(ins->k);
423 break;
424
425 case BPF_JMP|BPF_JGT|BPF_K:
426 if (ins->jt == ins->jf) {
427 JUMP(ins->jt);
428 break;
429 }
430 CMPid(ins->k, EAX);
431 JCC(JA, JBE);
432 break;
433
434 case BPF_JMP|BPF_JGE|BPF_K:
435 if (ins->jt == ins->jf) {
436 JUMP(ins->jt);
437 break;
438 }
439 CMPid(ins->k, EAX);
440 JCC(JAE, JB);
441 break;
442
443 case BPF_JMP|BPF_JEQ|BPF_K:
444 if (ins->jt == ins->jf) {
445 JUMP(ins->jt);
446 break;
447 }
448 CMPid(ins->k, EAX);
449 JCC(JE, JNE);
450 break;
451
452 case BPF_JMP|BPF_JSET|BPF_K:
453 if (ins->jt == ins->jf) {
454 JUMP(ins->jt);
455 break;
456 }
457 TESTid(ins->k, EAX);
458 JCC(JNE, JE);
459 break;
460
461 case BPF_JMP|BPF_JGT|BPF_X:
462 if (ins->jt == ins->jf) {
463 JUMP(ins->jt);
464 break;
465 }
466 CMPrd(EDX, EAX);
467 JCC(JA, JBE);
468 break;
469
470 case BPF_JMP|BPF_JGE|BPF_X:
471 if (ins->jt == ins->jf) {
472 JUMP(ins->jt);
473 break;
474 }
475 CMPrd(EDX, EAX);
476 JCC(JAE, JB);
477 break;
478
479 case BPF_JMP|BPF_JEQ|BPF_X:
480 if (ins->jt == ins->jf) {
481 JUMP(ins->jt);
482 break;
483 }
484 CMPrd(EDX, EAX);
485 JCC(JE, JNE);
486 break;
487
488 case BPF_JMP|BPF_JSET|BPF_X:
489 if (ins->jt == ins->jf) {
490 JUMP(ins->jt);
491 break;
492 }
493 TESTrd(EDX, EAX);
494 JCC(JNE, JE);
495 break;
496
497 case BPF_ALU|BPF_ADD|BPF_X:
498 ADDrd(EDX, EAX);
499 break;
500
501 case BPF_ALU|BPF_SUB|BPF_X:
502 SUBrd(EDX, EAX);
503 break;
504
505 case BPF_ALU|BPF_MUL|BPF_X:
506 MOVrd(EDX, ECX);
507 MULrd(EDX);
508 MOVrd(ECX, EDX);
509 break;
510
511 case BPF_ALU|BPF_DIV|BPF_X:
512 TESTrd(EDX, EDX);
513 if (fmem) {
514 JNEb(4);
515 ZEROrd(EAX);
516 LEAVE();
517 } else {
518 JNEb(3);
519 ZEROrd(EAX);
520 }
521 RET();
522 MOVrd(EDX, ECX);
523 ZEROrd(EDX);
524 DIVrd(ECX);
525 MOVrd(ECX, EDX);
526 break;
527
528 case BPF_ALU|BPF_AND|BPF_X:
529 ANDrd(EDX, EAX);
530 break;
531
532 case BPF_ALU|BPF_OR|BPF_X:
533 ORrd(EDX, EAX);
534 break;
535
536 case BPF_ALU|BPF_LSH|BPF_X:
537 MOVrd(EDX, ECX);
538 SHL_CLrb(EAX);
539 break;
540
541 case BPF_ALU|BPF_RSH|BPF_X:
542 MOVrd(EDX, ECX);
543 SHR_CLrb(EAX);
544 break;
545
546 case BPF_ALU|BPF_ADD|BPF_K:
547 ADD_EAXi(ins->k);
548 break;
549
550 case BPF_ALU|BPF_SUB|BPF_K:
551 SUB_EAXi(ins->k);
552 break;
553
554 case BPF_ALU|BPF_MUL|BPF_K:
555 MOVrd(EDX, ECX);
556 MOVid(ins->k, EDX);
557 MULrd(EDX);
558 MOVrd(ECX, EDX);
559 break;
560
561 case BPF_ALU|BPF_DIV|BPF_K:
562 MOVrd(EDX, ECX);
563 ZEROrd(EDX);
564 MOVid(ins->k, ESI);
565 DIVrd(ESI);
566 MOVrd(ECX, EDX);
567 break;
568
569 case BPF_ALU|BPF_AND|BPF_K:
570 ANDid(ins->k, EAX);
571 break;
572
573 case BPF_ALU|BPF_OR|BPF_K:
574 ORid(ins->k, EAX);
575 break;
576
577 case BPF_ALU|BPF_LSH|BPF_K:
578 SHLib((ins->k) & 0xff, EAX);
579 break;
580
581 case BPF_ALU|BPF_RSH|BPF_K:
582 SHRib((ins->k) & 0xff, EAX);
583 break;
584
585 case BPF_ALU|BPF_NEG:
586 NEGd(EAX);
587 break;
588
589 case BPF_MISC|BPF_TAX:
590 MOVrd(EAX, EDX);
591 break;
592
593 case BPF_MISC|BPF_TXA:
594 MOVrd(EDX, EAX);
595 break;
596 }
597 ins++;
598 }
599
600 if (pass > 0)
601 continue;
602
603 *size = stream.cur_ip;
604 #ifdef _KERNEL
605 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT);
606 if (stream.ibuf == NULL)
607 break;
608 #else
609 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
610 MAP_ANON, -1, 0);
611 if (stream.ibuf == MAP_FAILED) {
612 stream.ibuf = NULL;
613 break;
614 }
615 #endif
616
617 /*
618 * Modify the reference table to contain the offsets and
619 * not the lengths of the instructions.
620 */
621 if (fjmp)
622 for (i = 1; i < nins + 1; i++)
623 stream.refs[i] += stream.refs[i - 1];
624
625 /* Reset the counters. */
626 stream.cur_ip = 0;
627 stream.bpf_pc = 0;
628
629 /* The second pass creates the actual code. */
630 emitm = emit_code;
631 }
632
633 /*
634 * The reference table is needed only during compilation,
635 * now we can free it.
636 */
637 if (fjmp)
638 #ifdef _KERNEL
639 free(stream.refs, M_BPFJIT);
640 #else
641 free(stream.refs);
642 #endif
643
644 #ifndef _KERNEL
645 if (stream.ibuf != NULL &&
646 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
647 munmap(stream.ibuf, *size);
648 stream.ibuf = NULL;
649 }
650 #endif
651
652 return ((bpf_filter_func)stream.ibuf);
653 }
Cache object: 5abfd0a18dfc94b7ba7af18a67e16d8b
|