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/11.2/sys/i386/i386/bpf_jit_machdep.c 331722 2018-03-29 02:50:57Z eadler $");
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/mbuf.h>
41 #include <sys/socket.h>
42 #include <sys/malloc.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 <i386/i386/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_JMP|BPF_JA:
130 case BPF_JMP|BPF_JGT|BPF_K:
131 case BPF_JMP|BPF_JGE|BPF_K:
132 case BPF_JMP|BPF_JEQ|BPF_K:
133 case BPF_JMP|BPF_JSET|BPF_K:
134 case BPF_JMP|BPF_JGT|BPF_X:
135 case BPF_JMP|BPF_JGE|BPF_X:
136 case BPF_JMP|BPF_JEQ|BPF_X:
137 case BPF_JMP|BPF_JSET|BPF_X:
138 flags |= BPF_JIT_FJMP;
139 break;
140 case BPF_ALU|BPF_DIV|BPF_K:
141 flags |= BPF_JIT_FADK;
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, fadk;
160 int save_esp;
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 fadk = (flags & BPF_JIT_FADK) != 0;
175 save_esp = (fpkt || fmem || fadk); /* Stack is used. */
176
177 if (fret)
178 nins = 1;
179
180 memset(&stream, 0, sizeof(stream));
181
182 /* Allocate the reference table for the jumps. */
183 if (fjmp) {
184 #ifdef _KERNEL
185 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
186 M_NOWAIT | M_ZERO);
187 #else
188 stream.refs = calloc(nins + 1, sizeof(u_int));
189 #endif
190 if (stream.refs == NULL)
191 return (NULL);
192 }
193
194 /*
195 * The first pass will emit the lengths of the instructions
196 * to create the reference table.
197 */
198 emitm = emit_length;
199
200 for (pass = 0; pass < 2; pass++) {
201 ins = prog;
202
203 /* Create the procedure header. */
204 if (save_esp) {
205 PUSH(EBP);
206 MOVrd(ESP, EBP);
207 }
208 if (fmem)
209 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP);
210 if (save_esp)
211 PUSH(ESI);
212 if (fpkt) {
213 PUSH(EDI);
214 PUSH(EBX);
215 MOVodd(8, EBP, EBX);
216 MOVodd(16, EBP, EDI);
217 }
218
219 for (i = 0; i < nins; i++) {
220 stream.bpf_pc++;
221
222 switch (ins->code) {
223 default:
224 #ifdef _KERNEL
225 return (NULL);
226 #else
227 abort();
228 #endif
229
230 case BPF_RET|BPF_K:
231 MOVid(ins->k, EAX);
232 if (save_esp) {
233 if (fpkt) {
234 POP(EBX);
235 POP(EDI);
236 }
237 POP(ESI);
238 LEAVE();
239 }
240 RET();
241 break;
242
243 case BPF_RET|BPF_A:
244 if (save_esp) {
245 if (fpkt) {
246 POP(EBX);
247 POP(EDI);
248 }
249 POP(ESI);
250 LEAVE();
251 }
252 RET();
253 break;
254
255 case BPF_LD|BPF_W|BPF_ABS:
256 MOVid(ins->k, ESI);
257 CMPrd(EDI, ESI);
258 JAb(12);
259 MOVrd(EDI, ECX);
260 SUBrd(ESI, ECX);
261 CMPid(sizeof(int32_t), ECX);
262 JAEb(7);
263 ZEROrd(EAX);
264 POP(EBX);
265 POP(EDI);
266 POP(ESI);
267 LEAVE();
268 RET();
269 MOVobd(EBX, ESI, EAX);
270 BSWAP(EAX);
271 break;
272
273 case BPF_LD|BPF_H|BPF_ABS:
274 ZEROrd(EAX);
275 MOVid(ins->k, ESI);
276 CMPrd(EDI, ESI);
277 JAb(12);
278 MOVrd(EDI, ECX);
279 SUBrd(ESI, ECX);
280 CMPid(sizeof(int16_t), ECX);
281 JAEb(5);
282 POP(EBX);
283 POP(EDI);
284 POP(ESI);
285 LEAVE();
286 RET();
287 MOVobw(EBX, ESI, AX);
288 SWAP_AX();
289 break;
290
291 case BPF_LD|BPF_B|BPF_ABS:
292 ZEROrd(EAX);
293 MOVid(ins->k, ESI);
294 CMPrd(EDI, ESI);
295 JBb(5);
296 POP(EBX);
297 POP(EDI);
298 POP(ESI);
299 LEAVE();
300 RET();
301 MOVobb(EBX, ESI, AL);
302 break;
303
304 case BPF_LD|BPF_W|BPF_LEN:
305 if (save_esp)
306 MOVodd(12, EBP, EAX);
307 else {
308 MOVrd(ESP, ECX);
309 MOVodd(12, ECX, EAX);
310 }
311 break;
312
313 case BPF_LDX|BPF_W|BPF_LEN:
314 if (save_esp)
315 MOVodd(12, EBP, EDX);
316 else {
317 MOVrd(ESP, ECX);
318 MOVodd(12, ECX, EDX);
319 }
320 break;
321
322 case BPF_LD|BPF_W|BPF_IND:
323 CMPrd(EDI, EDX);
324 JAb(27);
325 MOVid(ins->k, ESI);
326 MOVrd(EDI, ECX);
327 SUBrd(EDX, ECX);
328 CMPrd(ESI, ECX);
329 JBb(14);
330 ADDrd(EDX, ESI);
331 MOVrd(EDI, ECX);
332 SUBrd(ESI, ECX);
333 CMPid(sizeof(int32_t), ECX);
334 JAEb(7);
335 ZEROrd(EAX);
336 POP(EBX);
337 POP(EDI);
338 POP(ESI);
339 LEAVE();
340 RET();
341 MOVobd(EBX, ESI, EAX);
342 BSWAP(EAX);
343 break;
344
345 case BPF_LD|BPF_H|BPF_IND:
346 ZEROrd(EAX);
347 CMPrd(EDI, EDX);
348 JAb(27);
349 MOVid(ins->k, ESI);
350 MOVrd(EDI, ECX);
351 SUBrd(EDX, ECX);
352 CMPrd(ESI, ECX);
353 JBb(14);
354 ADDrd(EDX, ESI);
355 MOVrd(EDI, ECX);
356 SUBrd(ESI, ECX);
357 CMPid(sizeof(int16_t), ECX);
358 JAEb(5);
359 POP(EBX);
360 POP(EDI);
361 POP(ESI);
362 LEAVE();
363 RET();
364 MOVobw(EBX, ESI, AX);
365 SWAP_AX();
366 break;
367
368 case BPF_LD|BPF_B|BPF_IND:
369 ZEROrd(EAX);
370 CMPrd(EDI, EDX);
371 JAEb(13);
372 MOVid(ins->k, ESI);
373 MOVrd(EDI, ECX);
374 SUBrd(EDX, ECX);
375 CMPrd(ESI, ECX);
376 JAb(5);
377 POP(EBX);
378 POP(EDI);
379 POP(ESI);
380 LEAVE();
381 RET();
382 ADDrd(EDX, ESI);
383 MOVobb(EBX, ESI, AL);
384 break;
385
386 case BPF_LDX|BPF_MSH|BPF_B:
387 MOVid(ins->k, ESI);
388 CMPrd(EDI, ESI);
389 JBb(7);
390 ZEROrd(EAX);
391 POP(EBX);
392 POP(EDI);
393 POP(ESI);
394 LEAVE();
395 RET();
396 ZEROrd(EDX);
397 MOVobb(EBX, ESI, DL);
398 ANDib(0x0f, DL);
399 SHLib(2, EDX);
400 break;
401
402 case BPF_LD|BPF_IMM:
403 MOVid(ins->k, EAX);
404 break;
405
406 case BPF_LDX|BPF_IMM:
407 MOVid(ins->k, EDX);
408 break;
409
410 case BPF_LD|BPF_MEM:
411 MOVrd(EBP, ECX);
412 MOVid(((int)ins->k - BPF_MEMWORDS) *
413 sizeof(uint32_t), ESI);
414 MOVobd(ECX, ESI, EAX);
415 break;
416
417 case BPF_LDX|BPF_MEM:
418 MOVrd(EBP, ECX);
419 MOVid(((int)ins->k - BPF_MEMWORDS) *
420 sizeof(uint32_t), ESI);
421 MOVobd(ECX, ESI, EDX);
422 break;
423
424 case BPF_ST:
425 /*
426 * XXX this command and the following could
427 * be optimized if the previous instruction
428 * was already of this type
429 */
430 MOVrd(EBP, ECX);
431 MOVid(((int)ins->k - BPF_MEMWORDS) *
432 sizeof(uint32_t), ESI);
433 MOVomd(EAX, ECX, ESI);
434 break;
435
436 case BPF_STX:
437 MOVrd(EBP, ECX);
438 MOVid(((int)ins->k - BPF_MEMWORDS) *
439 sizeof(uint32_t), ESI);
440 MOVomd(EDX, ECX, ESI);
441 break;
442
443 case BPF_JMP|BPF_JA:
444 JUMP(ins->k);
445 break;
446
447 case BPF_JMP|BPF_JGT|BPF_K:
448 if (ins->jt == ins->jf) {
449 JUMP(ins->jt);
450 break;
451 }
452 CMPid(ins->k, EAX);
453 JCC(JA, JBE);
454 break;
455
456 case BPF_JMP|BPF_JGE|BPF_K:
457 if (ins->jt == ins->jf) {
458 JUMP(ins->jt);
459 break;
460 }
461 CMPid(ins->k, EAX);
462 JCC(JAE, JB);
463 break;
464
465 case BPF_JMP|BPF_JEQ|BPF_K:
466 if (ins->jt == ins->jf) {
467 JUMP(ins->jt);
468 break;
469 }
470 CMPid(ins->k, EAX);
471 JCC(JE, JNE);
472 break;
473
474 case BPF_JMP|BPF_JSET|BPF_K:
475 if (ins->jt == ins->jf) {
476 JUMP(ins->jt);
477 break;
478 }
479 TESTid(ins->k, EAX);
480 JCC(JNE, JE);
481 break;
482
483 case BPF_JMP|BPF_JGT|BPF_X:
484 if (ins->jt == ins->jf) {
485 JUMP(ins->jt);
486 break;
487 }
488 CMPrd(EDX, EAX);
489 JCC(JA, JBE);
490 break;
491
492 case BPF_JMP|BPF_JGE|BPF_X:
493 if (ins->jt == ins->jf) {
494 JUMP(ins->jt);
495 break;
496 }
497 CMPrd(EDX, EAX);
498 JCC(JAE, JB);
499 break;
500
501 case BPF_JMP|BPF_JEQ|BPF_X:
502 if (ins->jt == ins->jf) {
503 JUMP(ins->jt);
504 break;
505 }
506 CMPrd(EDX, EAX);
507 JCC(JE, JNE);
508 break;
509
510 case BPF_JMP|BPF_JSET|BPF_X:
511 if (ins->jt == ins->jf) {
512 JUMP(ins->jt);
513 break;
514 }
515 TESTrd(EDX, EAX);
516 JCC(JNE, JE);
517 break;
518
519 case BPF_ALU|BPF_ADD|BPF_X:
520 ADDrd(EDX, EAX);
521 break;
522
523 case BPF_ALU|BPF_SUB|BPF_X:
524 SUBrd(EDX, EAX);
525 break;
526
527 case BPF_ALU|BPF_MUL|BPF_X:
528 MOVrd(EDX, ECX);
529 MULrd(EDX);
530 MOVrd(ECX, EDX);
531 break;
532
533 case BPF_ALU|BPF_DIV|BPF_X:
534 TESTrd(EDX, EDX);
535 if (save_esp) {
536 if (fpkt) {
537 JNEb(7);
538 ZEROrd(EAX);
539 POP(EBX);
540 POP(EDI);
541 } else {
542 JNEb(5);
543 ZEROrd(EAX);
544 }
545 POP(ESI);
546 LEAVE();
547 } else {
548 JNEb(3);
549 ZEROrd(EAX);
550 }
551 RET();
552 MOVrd(EDX, ECX);
553 ZEROrd(EDX);
554 DIVrd(ECX);
555 MOVrd(ECX, EDX);
556 break;
557
558 case BPF_ALU|BPF_AND|BPF_X:
559 ANDrd(EDX, EAX);
560 break;
561
562 case BPF_ALU|BPF_OR|BPF_X:
563 ORrd(EDX, EAX);
564 break;
565
566 case BPF_ALU|BPF_LSH|BPF_X:
567 MOVrd(EDX, ECX);
568 SHL_CLrb(EAX);
569 break;
570
571 case BPF_ALU|BPF_RSH|BPF_X:
572 MOVrd(EDX, ECX);
573 SHR_CLrb(EAX);
574 break;
575
576 case BPF_ALU|BPF_ADD|BPF_K:
577 ADD_EAXi(ins->k);
578 break;
579
580 case BPF_ALU|BPF_SUB|BPF_K:
581 SUB_EAXi(ins->k);
582 break;
583
584 case BPF_ALU|BPF_MUL|BPF_K:
585 MOVrd(EDX, ECX);
586 MOVid(ins->k, EDX);
587 MULrd(EDX);
588 MOVrd(ECX, EDX);
589 break;
590
591 case BPF_ALU|BPF_DIV|BPF_K:
592 MOVrd(EDX, ECX);
593 ZEROrd(EDX);
594 MOVid(ins->k, ESI);
595 DIVrd(ESI);
596 MOVrd(ECX, EDX);
597 break;
598
599 case BPF_ALU|BPF_AND|BPF_K:
600 ANDid(ins->k, EAX);
601 break;
602
603 case BPF_ALU|BPF_OR|BPF_K:
604 ORid(ins->k, EAX);
605 break;
606
607 case BPF_ALU|BPF_LSH|BPF_K:
608 SHLib((ins->k) & 0xff, EAX);
609 break;
610
611 case BPF_ALU|BPF_RSH|BPF_K:
612 SHRib((ins->k) & 0xff, EAX);
613 break;
614
615 case BPF_ALU|BPF_NEG:
616 NEGd(EAX);
617 break;
618
619 case BPF_MISC|BPF_TAX:
620 MOVrd(EAX, EDX);
621 break;
622
623 case BPF_MISC|BPF_TXA:
624 MOVrd(EDX, EAX);
625 break;
626 }
627 ins++;
628 }
629
630 if (pass > 0)
631 continue;
632
633 *size = stream.cur_ip;
634 #ifdef _KERNEL
635 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT);
636 if (stream.ibuf == NULL)
637 break;
638 #else
639 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
640 MAP_ANON, -1, 0);
641 if (stream.ibuf == MAP_FAILED) {
642 stream.ibuf = NULL;
643 break;
644 }
645 #endif
646
647 /*
648 * Modify the reference table to contain the offsets and
649 * not the lengths of the instructions.
650 */
651 if (fjmp)
652 for (i = 1; i < nins + 1; i++)
653 stream.refs[i] += stream.refs[i - 1];
654
655 /* Reset the counters. */
656 stream.cur_ip = 0;
657 stream.bpf_pc = 0;
658
659 /* The second pass creates the actual code. */
660 emitm = emit_code;
661 }
662
663 /*
664 * The reference table is needed only during compilation,
665 * now we can free it.
666 */
667 if (fjmp)
668 #ifdef _KERNEL
669 free(stream.refs, M_BPFJIT);
670 #else
671 free(stream.refs);
672 #endif
673
674 #ifndef _KERNEL
675 if (stream.ibuf != NULL &&
676 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
677 munmap(stream.ibuf, *size);
678 stream.ibuf = NULL;
679 }
680 #endif
681
682 return ((bpf_filter_func)stream.ibuf);
683 }
Cache object: 8054ae14ca0f41911be1327b9cd439d8
|