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