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