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$");
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 <i386/i386/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_JMP|BPF_JA:
132 case BPF_JMP|BPF_JGT|BPF_K:
133 case BPF_JMP|BPF_JGE|BPF_K:
134 case BPF_JMP|BPF_JEQ|BPF_K:
135 case BPF_JMP|BPF_JSET|BPF_K:
136 case BPF_JMP|BPF_JGT|BPF_X:
137 case BPF_JMP|BPF_JGE|BPF_X:
138 case BPF_JMP|BPF_JEQ|BPF_X:
139 case BPF_JMP|BPF_JSET|BPF_X:
140 flags |= BPF_JIT_FJMP;
141 break;
142 case BPF_ALU|BPF_DIV|BPF_K:
143 case BPF_ALU|BPF_MOD|BPF_K:
144 flags |= BPF_JIT_FADK;
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, fadk;
163 int save_esp;
164 u_int i, pass;
165
166 /*
167 * NOTE: Do not modify the name of this variable, as it's used by
168 * the macros to emit code.
169 */
170 emit_func emitm;
171
172 flags = bpf_jit_optimize(prog, nins);
173 fret = (flags & BPF_JIT_FRET) != 0;
174 fpkt = (flags & BPF_JIT_FPKT) != 0;
175 fmem = (flags & BPF_JIT_FMEM) != 0;
176 fjmp = (flags & BPF_JIT_FJMP) != 0;
177 fadk = (flags & BPF_JIT_FADK) != 0;
178 save_esp = (fpkt || fmem || fadk); /* Stack is used. */
179
180 if (fret)
181 nins = 1;
182
183 memset(&stream, 0, sizeof(stream));
184
185 /* Allocate the reference table for the jumps. */
186 if (fjmp) {
187 #ifdef _KERNEL
188 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
189 M_NOWAIT | M_ZERO);
190 #else
191 stream.refs = calloc(nins + 1, sizeof(u_int));
192 #endif
193 if (stream.refs == NULL)
194 return (NULL);
195 }
196
197 /*
198 * The first pass will emit the lengths of the instructions
199 * to create the reference table.
200 */
201 emitm = emit_length;
202
203 for (pass = 0; pass < 2; pass++) {
204 ins = prog;
205
206 /* Create the procedure header. */
207 if (save_esp) {
208 PUSH(EBP);
209 MOVrd(ESP, EBP);
210 }
211 if (fmem)
212 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP);
213 if (save_esp)
214 PUSH(ESI);
215 if (fpkt) {
216 PUSH(EDI);
217 PUSH(EBX);
218 MOVodd(8, EBP, EBX);
219 MOVodd(16, EBP, EDI);
220 }
221
222 for (i = 0; i < nins; i++) {
223 stream.bpf_pc++;
224
225 switch (ins->code) {
226 default:
227 #ifdef _KERNEL
228 return (NULL);
229 #else
230 abort();
231 #endif
232
233 case BPF_RET|BPF_K:
234 MOVid(ins->k, EAX);
235 if (save_esp) {
236 if (fpkt) {
237 POP(EBX);
238 POP(EDI);
239 }
240 POP(ESI);
241 LEAVE();
242 }
243 RET();
244 break;
245
246 case BPF_RET|BPF_A:
247 if (save_esp) {
248 if (fpkt) {
249 POP(EBX);
250 POP(EDI);
251 }
252 POP(ESI);
253 LEAVE();
254 }
255 RET();
256 break;
257
258 case BPF_LD|BPF_W|BPF_ABS:
259 MOVid(ins->k, ESI);
260 CMPrd(EDI, ESI);
261 JAb(12);
262 MOVrd(EDI, ECX);
263 SUBrd(ESI, ECX);
264 CMPid(sizeof(int32_t), ECX);
265 JAEb(7);
266 ZEROrd(EAX);
267 POP(EBX);
268 POP(EDI);
269 POP(ESI);
270 LEAVE();
271 RET();
272 MOVobd(EBX, ESI, EAX);
273 BSWAP(EAX);
274 break;
275
276 case BPF_LD|BPF_H|BPF_ABS:
277 ZEROrd(EAX);
278 MOVid(ins->k, ESI);
279 CMPrd(EDI, ESI);
280 JAb(12);
281 MOVrd(EDI, ECX);
282 SUBrd(ESI, ECX);
283 CMPid(sizeof(int16_t), ECX);
284 JAEb(5);
285 POP(EBX);
286 POP(EDI);
287 POP(ESI);
288 LEAVE();
289 RET();
290 MOVobw(EBX, ESI, AX);
291 SWAP_AX();
292 break;
293
294 case BPF_LD|BPF_B|BPF_ABS:
295 ZEROrd(EAX);
296 MOVid(ins->k, ESI);
297 CMPrd(EDI, ESI);
298 JBb(5);
299 POP(EBX);
300 POP(EDI);
301 POP(ESI);
302 LEAVE();
303 RET();
304 MOVobb(EBX, ESI, AL);
305 break;
306
307 case BPF_LD|BPF_W|BPF_LEN:
308 if (save_esp)
309 MOVodd(12, EBP, EAX);
310 else {
311 MOVrd(ESP, ECX);
312 MOVodd(12, ECX, EAX);
313 }
314 break;
315
316 case BPF_LDX|BPF_W|BPF_LEN:
317 if (save_esp)
318 MOVodd(12, EBP, EDX);
319 else {
320 MOVrd(ESP, ECX);
321 MOVodd(12, ECX, EDX);
322 }
323 break;
324
325 case BPF_LD|BPF_W|BPF_IND:
326 CMPrd(EDI, EDX);
327 JAb(27);
328 MOVid(ins->k, ESI);
329 MOVrd(EDI, ECX);
330 SUBrd(EDX, ECX);
331 CMPrd(ESI, ECX);
332 JBb(14);
333 ADDrd(EDX, ESI);
334 MOVrd(EDI, ECX);
335 SUBrd(ESI, ECX);
336 CMPid(sizeof(int32_t), ECX);
337 JAEb(7);
338 ZEROrd(EAX);
339 POP(EBX);
340 POP(EDI);
341 POP(ESI);
342 LEAVE();
343 RET();
344 MOVobd(EBX, ESI, EAX);
345 BSWAP(EAX);
346 break;
347
348 case BPF_LD|BPF_H|BPF_IND:
349 ZEROrd(EAX);
350 CMPrd(EDI, EDX);
351 JAb(27);
352 MOVid(ins->k, ESI);
353 MOVrd(EDI, ECX);
354 SUBrd(EDX, ECX);
355 CMPrd(ESI, ECX);
356 JBb(14);
357 ADDrd(EDX, ESI);
358 MOVrd(EDI, ECX);
359 SUBrd(ESI, ECX);
360 CMPid(sizeof(int16_t), ECX);
361 JAEb(5);
362 POP(EBX);
363 POP(EDI);
364 POP(ESI);
365 LEAVE();
366 RET();
367 MOVobw(EBX, ESI, AX);
368 SWAP_AX();
369 break;
370
371 case BPF_LD|BPF_B|BPF_IND:
372 ZEROrd(EAX);
373 CMPrd(EDI, EDX);
374 JAEb(13);
375 MOVid(ins->k, ESI);
376 MOVrd(EDI, ECX);
377 SUBrd(EDX, ECX);
378 CMPrd(ESI, ECX);
379 JAb(5);
380 POP(EBX);
381 POP(EDI);
382 POP(ESI);
383 LEAVE();
384 RET();
385 ADDrd(EDX, ESI);
386 MOVobb(EBX, ESI, AL);
387 break;
388
389 case BPF_LDX|BPF_MSH|BPF_B:
390 MOVid(ins->k, ESI);
391 CMPrd(EDI, ESI);
392 JBb(7);
393 ZEROrd(EAX);
394 POP(EBX);
395 POP(EDI);
396 POP(ESI);
397 LEAVE();
398 RET();
399 ZEROrd(EDX);
400 MOVobb(EBX, ESI, DL);
401 ANDib(0x0f, DL);
402 SHLib(2, EDX);
403 break;
404
405 case BPF_LD|BPF_IMM:
406 MOVid(ins->k, EAX);
407 break;
408
409 case BPF_LDX|BPF_IMM:
410 MOVid(ins->k, EDX);
411 break;
412
413 case BPF_LD|BPF_MEM:
414 MOVrd(EBP, ECX);
415 MOVid(((int)ins->k - BPF_MEMWORDS) *
416 sizeof(uint32_t), ESI);
417 MOVobd(ECX, ESI, EAX);
418 break;
419
420 case BPF_LDX|BPF_MEM:
421 MOVrd(EBP, ECX);
422 MOVid(((int)ins->k - BPF_MEMWORDS) *
423 sizeof(uint32_t), ESI);
424 MOVobd(ECX, ESI, EDX);
425 break;
426
427 case BPF_ST:
428 /*
429 * XXX this command and the following could
430 * be optimized if the previous instruction
431 * was already of this type
432 */
433 MOVrd(EBP, ECX);
434 MOVid(((int)ins->k - BPF_MEMWORDS) *
435 sizeof(uint32_t), ESI);
436 MOVomd(EAX, ECX, ESI);
437 break;
438
439 case BPF_STX:
440 MOVrd(EBP, ECX);
441 MOVid(((int)ins->k - BPF_MEMWORDS) *
442 sizeof(uint32_t), ESI);
443 MOVomd(EDX, ECX, ESI);
444 break;
445
446 case BPF_JMP|BPF_JA:
447 JUMP(ins->k);
448 break;
449
450 case BPF_JMP|BPF_JGT|BPF_K:
451 case BPF_JMP|BPF_JGE|BPF_K:
452 case BPF_JMP|BPF_JEQ|BPF_K:
453 case BPF_JMP|BPF_JSET|BPF_K:
454 case BPF_JMP|BPF_JGT|BPF_X:
455 case BPF_JMP|BPF_JGE|BPF_X:
456 case BPF_JMP|BPF_JEQ|BPF_X:
457 case BPF_JMP|BPF_JSET|BPF_X:
458 if (ins->jt == ins->jf) {
459 JUMP(ins->jt);
460 break;
461 }
462 switch (ins->code) {
463 case BPF_JMP|BPF_JGT|BPF_K:
464 CMPid(ins->k, EAX);
465 JCC(JA, JBE);
466 break;
467
468 case BPF_JMP|BPF_JGE|BPF_K:
469 CMPid(ins->k, EAX);
470 JCC(JAE, JB);
471 break;
472
473 case BPF_JMP|BPF_JEQ|BPF_K:
474 CMPid(ins->k, EAX);
475 JCC(JE, JNE);
476 break;
477
478 case BPF_JMP|BPF_JSET|BPF_K:
479 TESTid(ins->k, EAX);
480 JCC(JNE, JE);
481 break;
482
483 case BPF_JMP|BPF_JGT|BPF_X:
484 CMPrd(EDX, EAX);
485 JCC(JA, JBE);
486 break;
487
488 case BPF_JMP|BPF_JGE|BPF_X:
489 CMPrd(EDX, EAX);
490 JCC(JAE, JB);
491 break;
492
493 case BPF_JMP|BPF_JEQ|BPF_X:
494 CMPrd(EDX, EAX);
495 JCC(JE, JNE);
496 break;
497
498 case BPF_JMP|BPF_JSET|BPF_X:
499 TESTrd(EDX, EAX);
500 JCC(JNE, JE);
501 break;
502 }
503 break;
504
505 case BPF_ALU|BPF_ADD|BPF_X:
506 ADDrd(EDX, EAX);
507 break;
508
509 case BPF_ALU|BPF_SUB|BPF_X:
510 SUBrd(EDX, EAX);
511 break;
512
513 case BPF_ALU|BPF_MUL|BPF_X:
514 MOVrd(EDX, ECX);
515 MULrd(EDX);
516 MOVrd(ECX, EDX);
517 break;
518
519 case BPF_ALU|BPF_DIV|BPF_X:
520 case BPF_ALU|BPF_MOD|BPF_X:
521 TESTrd(EDX, EDX);
522 if (save_esp) {
523 if (fpkt) {
524 JNEb(7);
525 ZEROrd(EAX);
526 POP(EBX);
527 POP(EDI);
528 } else {
529 JNEb(5);
530 ZEROrd(EAX);
531 }
532 POP(ESI);
533 LEAVE();
534 } else {
535 JNEb(3);
536 ZEROrd(EAX);
537 }
538 RET();
539 MOVrd(EDX, ECX);
540 ZEROrd(EDX);
541 DIVrd(ECX);
542 if (BPF_OP(ins->code) == BPF_MOD)
543 MOVrd(EDX, EAX);
544 MOVrd(ECX, EDX);
545 break;
546
547 case BPF_ALU|BPF_AND|BPF_X:
548 ANDrd(EDX, EAX);
549 break;
550
551 case BPF_ALU|BPF_OR|BPF_X:
552 ORrd(EDX, EAX);
553 break;
554
555 case BPF_ALU|BPF_XOR|BPF_X:
556 XORrd(EDX, EAX);
557 break;
558
559 case BPF_ALU|BPF_LSH|BPF_X:
560 MOVrd(EDX, ECX);
561 SHL_CLrb(EAX);
562 break;
563
564 case BPF_ALU|BPF_RSH|BPF_X:
565 MOVrd(EDX, ECX);
566 SHR_CLrb(EAX);
567 break;
568
569 case BPF_ALU|BPF_ADD|BPF_K:
570 ADD_EAXi(ins->k);
571 break;
572
573 case BPF_ALU|BPF_SUB|BPF_K:
574 SUB_EAXi(ins->k);
575 break;
576
577 case BPF_ALU|BPF_MUL|BPF_K:
578 MOVrd(EDX, ECX);
579 MOVid(ins->k, EDX);
580 MULrd(EDX);
581 MOVrd(ECX, EDX);
582 break;
583
584 case BPF_ALU|BPF_DIV|BPF_K:
585 case BPF_ALU|BPF_MOD|BPF_K:
586 MOVrd(EDX, ECX);
587 ZEROrd(EDX);
588 MOVid(ins->k, ESI);
589 DIVrd(ESI);
590 if (BPF_OP(ins->code) == BPF_MOD)
591 MOVrd(EDX, EAX);
592 MOVrd(ECX, EDX);
593 break;
594
595 case BPF_ALU|BPF_AND|BPF_K:
596 ANDid(ins->k, EAX);
597 break;
598
599 case BPF_ALU|BPF_OR|BPF_K:
600 ORid(ins->k, EAX);
601 break;
602
603 case BPF_ALU|BPF_XOR|BPF_K:
604 XORid(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_exec(*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)(void *)stream.ibuf);
683 }
Cache object: 194e49c6b7b43cbd17fdf82979fc0365
|