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 #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/malloc.h>
41 #include <sys/mbuf.h>
42 #include <sys/socket.h>
43
44 #include <net/if.h>
45 #else
46 #include <stdlib.h>
47 #include <string.h>
48 #include <sys/mman.h>
49 #include <sys/param.h>
50 #endif
51
52 #include <sys/types.h>
53
54 #include <net/bpf.h>
55 #include <net/bpf_jitter.h>
56
57 #include <amd64/amd64/bpf_jit_machdep.h>
58
59 /*
60 * Emit routine to update the jump table.
61 */
62 static void
emit_length(bpf_bin_stream * stream,__unused u_int value,u_int len)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
emit_code(bpf_bin_stream * stream,u_int value,u_int len)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 *)(void *)(stream->ibuf + stream->cur_ip)) =
86 (u_short)value;
87 stream->cur_ip += 2;
88 break;
89
90 case 4:
91 *((u_int *)(void *)(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
bpf_jit_optimize(struct bpf_insn * prog,u_int nins)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
bpf_jit_compile(struct bpf_insn * prog,u_int nins,size_t * size)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 case BPF_JMP|BPF_JGE|BPF_K:
428 case BPF_JMP|BPF_JEQ|BPF_K:
429 case BPF_JMP|BPF_JSET|BPF_K:
430 case BPF_JMP|BPF_JGT|BPF_X:
431 case BPF_JMP|BPF_JGE|BPF_X:
432 case BPF_JMP|BPF_JEQ|BPF_X:
433 case BPF_JMP|BPF_JSET|BPF_X:
434 if (ins->jt == ins->jf) {
435 JUMP(ins->jt);
436 break;
437 }
438 switch (ins->code) {
439 case BPF_JMP|BPF_JGT|BPF_K:
440 CMPid(ins->k, EAX);
441 JCC(JA, JBE);
442 break;
443
444 case BPF_JMP|BPF_JGE|BPF_K:
445 CMPid(ins->k, EAX);
446 JCC(JAE, JB);
447 break;
448
449 case BPF_JMP|BPF_JEQ|BPF_K:
450 CMPid(ins->k, EAX);
451 JCC(JE, JNE);
452 break;
453
454 case BPF_JMP|BPF_JSET|BPF_K:
455 TESTid(ins->k, EAX);
456 JCC(JNE, JE);
457 break;
458
459 case BPF_JMP|BPF_JGT|BPF_X:
460 CMPrd(EDX, EAX);
461 JCC(JA, JBE);
462 break;
463
464 case BPF_JMP|BPF_JGE|BPF_X:
465 CMPrd(EDX, EAX);
466 JCC(JAE, JB);
467 break;
468
469 case BPF_JMP|BPF_JEQ|BPF_X:
470 CMPrd(EDX, EAX);
471 JCC(JE, JNE);
472 break;
473
474 case BPF_JMP|BPF_JSET|BPF_X:
475 TESTrd(EDX, EAX);
476 JCC(JNE, JE);
477 break;
478 }
479 break;
480
481 case BPF_ALU|BPF_ADD|BPF_X:
482 ADDrd(EDX, EAX);
483 break;
484
485 case BPF_ALU|BPF_SUB|BPF_X:
486 SUBrd(EDX, EAX);
487 break;
488
489 case BPF_ALU|BPF_MUL|BPF_X:
490 MOVrd(EDX, ECX);
491 MULrd(EDX);
492 MOVrd(ECX, EDX);
493 break;
494
495 case BPF_ALU|BPF_DIV|BPF_X:
496 case BPF_ALU|BPF_MOD|BPF_X:
497 TESTrd(EDX, EDX);
498 if (fmem) {
499 JNEb(4);
500 ZEROrd(EAX);
501 LEAVE();
502 } else {
503 JNEb(3);
504 ZEROrd(EAX);
505 }
506 RET();
507 MOVrd(EDX, ECX);
508 ZEROrd(EDX);
509 DIVrd(ECX);
510 if (BPF_OP(ins->code) == BPF_MOD)
511 MOVrd(EDX, EAX);
512 MOVrd(ECX, EDX);
513 break;
514
515 case BPF_ALU|BPF_AND|BPF_X:
516 ANDrd(EDX, EAX);
517 break;
518
519 case BPF_ALU|BPF_OR|BPF_X:
520 ORrd(EDX, EAX);
521 break;
522
523 case BPF_ALU|BPF_XOR|BPF_X:
524 XORrd(EDX, EAX);
525 break;
526
527 case BPF_ALU|BPF_LSH|BPF_X:
528 MOVrd(EDX, ECX);
529 SHL_CLrb(EAX);
530 break;
531
532 case BPF_ALU|BPF_RSH|BPF_X:
533 MOVrd(EDX, ECX);
534 SHR_CLrb(EAX);
535 break;
536
537 case BPF_ALU|BPF_ADD|BPF_K:
538 ADD_EAXi(ins->k);
539 break;
540
541 case BPF_ALU|BPF_SUB|BPF_K:
542 SUB_EAXi(ins->k);
543 break;
544
545 case BPF_ALU|BPF_MUL|BPF_K:
546 MOVrd(EDX, ECX);
547 MOVid(ins->k, EDX);
548 MULrd(EDX);
549 MOVrd(ECX, EDX);
550 break;
551
552 case BPF_ALU|BPF_DIV|BPF_K:
553 case BPF_ALU|BPF_MOD|BPF_K:
554 MOVrd(EDX, ECX);
555 ZEROrd(EDX);
556 MOVid(ins->k, ESI);
557 DIVrd(ESI);
558 if (BPF_OP(ins->code) == BPF_MOD)
559 MOVrd(EDX, EAX);
560 MOVrd(ECX, EDX);
561 break;
562
563 case BPF_ALU|BPF_AND|BPF_K:
564 ANDid(ins->k, EAX);
565 break;
566
567 case BPF_ALU|BPF_OR|BPF_K:
568 ORid(ins->k, EAX);
569 break;
570
571 case BPF_ALU|BPF_XOR|BPF_K:
572 XORid(ins->k, EAX);
573 break;
574
575 case BPF_ALU|BPF_LSH|BPF_K:
576 SHLib((ins->k) & 0xff, EAX);
577 break;
578
579 case BPF_ALU|BPF_RSH|BPF_K:
580 SHRib((ins->k) & 0xff, EAX);
581 break;
582
583 case BPF_ALU|BPF_NEG:
584 NEGd(EAX);
585 break;
586
587 case BPF_MISC|BPF_TAX:
588 MOVrd(EAX, EDX);
589 break;
590
591 case BPF_MISC|BPF_TXA:
592 MOVrd(EDX, EAX);
593 break;
594 }
595 ins++;
596 }
597
598 if (pass > 0)
599 continue;
600
601 *size = stream.cur_ip;
602 #ifdef _KERNEL
603 stream.ibuf = malloc_exec(*size, M_BPFJIT, M_NOWAIT);
604 if (stream.ibuf == NULL)
605 break;
606 #else
607 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
608 MAP_ANON, -1, 0);
609 if (stream.ibuf == MAP_FAILED) {
610 stream.ibuf = NULL;
611 break;
612 }
613 #endif
614
615 /*
616 * Modify the reference table to contain the offsets and
617 * not the lengths of the instructions.
618 */
619 if (fjmp)
620 for (i = 1; i < nins + 1; i++)
621 stream.refs[i] += stream.refs[i - 1];
622
623 /* Reset the counters. */
624 stream.cur_ip = 0;
625 stream.bpf_pc = 0;
626
627 /* The second pass creates the actual code. */
628 emitm = emit_code;
629 }
630
631 /*
632 * The reference table is needed only during compilation,
633 * now we can free it.
634 */
635 if (fjmp)
636 #ifdef _KERNEL
637 free(stream.refs, M_BPFJIT);
638 #else
639 free(stream.refs);
640 #endif
641
642 #ifndef _KERNEL
643 if (stream.ibuf != NULL &&
644 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
645 munmap(stream.ibuf, *size);
646 stream.ibuf = NULL;
647 }
648 #endif
649
650 return ((bpf_filter_func)(void *)stream.ibuf);
651 }
652