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