2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
5 * Copyright (C) 2005-2017 Jung-uk Kim <jkim@FreeBSD.org>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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.
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
39 #include <sys/param.h>
40 #include <sys/systm.h>
41 #include <sys/kernel.h>
42 #include <sys/malloc.h>
44 #include <sys/socket.h>
51 #include <sys/param.h>
54 #include <sys/types.h>
57 #include <net/bpf_jitter.h>
59 #include <i386/i386/bpf_jit_machdep.h>
62 * Emit routine to update the jump table.
65 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
68 if (stream->refs != NULL)
69 (stream->refs)[stream->bpf_pc] += len;
70 stream->cur_ip += len;
74 * Emit routine to output the actual binary code.
77 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
82 stream->ibuf[stream->cur_ip] = (u_char)value;
87 *((u_short *)(void *)(stream->ibuf + stream->cur_ip)) =
93 *((u_int *)(void *)(stream->ibuf + stream->cur_ip)) = value;
102 * Scan the filter program and find possible optimization.
105 bpf_jit_optimize(struct bpf_insn *prog, u_int nins)
110 /* Do we return immediately? */
111 if (BPF_CLASS(prog[0].code) == BPF_RET)
112 return (BPF_JIT_FRET);
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;
126 case BPF_LDX|BPF_MEM:
129 flags |= BPF_JIT_FMEM;
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;
142 case BPF_ALU|BPF_DIV|BPF_K:
143 case BPF_ALU|BPF_MOD|BPF_K:
144 flags |= BPF_JIT_FADK;
147 if (flags == BPF_JIT_FLAG_ALL)
155 * Function that does the real stuff.
158 bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size)
160 bpf_bin_stream stream;
161 struct bpf_insn *ins;
162 int flags, fret, fpkt, fmem, fjmp, fadk;
167 * NOTE: Do not modify the name of this variable, as it's used by
168 * the macros to emit code.
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. */
183 memset(&stream, 0, sizeof(stream));
185 /* Allocate the reference table for the jumps. */
188 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
191 stream.refs = calloc(nins + 1, sizeof(u_int));
193 if (stream.refs == NULL)
198 * The first pass will emit the lengths of the instructions
199 * to create the reference table.
203 for (pass = 0; pass < 2; pass++) {
206 /* Create the procedure header. */
212 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP);
219 MOVodd(16, EBP, EDI);
222 for (i = 0; i < nins; i++) {
258 case BPF_LD|BPF_W|BPF_ABS:
264 CMPid(sizeof(int32_t), ECX);
272 MOVobd(EBX, ESI, EAX);
276 case BPF_LD|BPF_H|BPF_ABS:
283 CMPid(sizeof(int16_t), ECX);
290 MOVobw(EBX, ESI, AX);
294 case BPF_LD|BPF_B|BPF_ABS:
304 MOVobb(EBX, ESI, AL);
307 case BPF_LD|BPF_W|BPF_LEN:
309 MOVodd(12, EBP, EAX);
312 MOVodd(12, ECX, EAX);
316 case BPF_LDX|BPF_W|BPF_LEN:
318 MOVodd(12, EBP, EDX);
321 MOVodd(12, ECX, EDX);
325 case BPF_LD|BPF_W|BPF_IND:
336 CMPid(sizeof(int32_t), ECX);
344 MOVobd(EBX, ESI, EAX);
348 case BPF_LD|BPF_H|BPF_IND:
360 CMPid(sizeof(int16_t), ECX);
367 MOVobw(EBX, ESI, AX);
371 case BPF_LD|BPF_B|BPF_IND:
386 MOVobb(EBX, ESI, AL);
389 case BPF_LDX|BPF_MSH|BPF_B:
400 MOVobb(EBX, ESI, DL);
409 case BPF_LDX|BPF_IMM:
415 MOVid(((int)ins->k - BPF_MEMWORDS) *
416 sizeof(uint32_t), ESI);
417 MOVobd(ECX, ESI, EAX);
420 case BPF_LDX|BPF_MEM:
422 MOVid(((int)ins->k - BPF_MEMWORDS) *
423 sizeof(uint32_t), ESI);
424 MOVobd(ECX, ESI, EDX);
429 * XXX this command and the following could
430 * be optimized if the previous instruction
431 * was already of this type
434 MOVid(((int)ins->k - BPF_MEMWORDS) *
435 sizeof(uint32_t), ESI);
436 MOVomd(EAX, ECX, ESI);
441 MOVid(((int)ins->k - BPF_MEMWORDS) *
442 sizeof(uint32_t), ESI);
443 MOVomd(EDX, ECX, ESI);
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) {
463 case BPF_JMP|BPF_JGT|BPF_K:
468 case BPF_JMP|BPF_JGE|BPF_K:
473 case BPF_JMP|BPF_JEQ|BPF_K:
478 case BPF_JMP|BPF_JSET|BPF_K:
483 case BPF_JMP|BPF_JGT|BPF_X:
488 case BPF_JMP|BPF_JGE|BPF_X:
493 case BPF_JMP|BPF_JEQ|BPF_X:
498 case BPF_JMP|BPF_JSET|BPF_X:
505 case BPF_ALU|BPF_ADD|BPF_X:
509 case BPF_ALU|BPF_SUB|BPF_X:
513 case BPF_ALU|BPF_MUL|BPF_X:
519 case BPF_ALU|BPF_DIV|BPF_X:
520 case BPF_ALU|BPF_MOD|BPF_X:
542 if (BPF_OP(ins->code) == BPF_MOD)
547 case BPF_ALU|BPF_AND|BPF_X:
551 case BPF_ALU|BPF_OR|BPF_X:
555 case BPF_ALU|BPF_XOR|BPF_X:
559 case BPF_ALU|BPF_LSH|BPF_X:
564 case BPF_ALU|BPF_RSH|BPF_X:
569 case BPF_ALU|BPF_ADD|BPF_K:
573 case BPF_ALU|BPF_SUB|BPF_K:
577 case BPF_ALU|BPF_MUL|BPF_K:
584 case BPF_ALU|BPF_DIV|BPF_K:
585 case BPF_ALU|BPF_MOD|BPF_K:
590 if (BPF_OP(ins->code) == BPF_MOD)
595 case BPF_ALU|BPF_AND|BPF_K:
599 case BPF_ALU|BPF_OR|BPF_K:
603 case BPF_ALU|BPF_XOR|BPF_K:
607 case BPF_ALU|BPF_LSH|BPF_K:
608 SHLib((ins->k) & 0xff, EAX);
611 case BPF_ALU|BPF_RSH|BPF_K:
612 SHRib((ins->k) & 0xff, EAX);
615 case BPF_ALU|BPF_NEG:
619 case BPF_MISC|BPF_TAX:
623 case BPF_MISC|BPF_TXA:
633 *size = stream.cur_ip;
635 stream.ibuf = malloc(*size, M_BPFJIT, M_EXEC | M_NOWAIT);
636 if (stream.ibuf == NULL)
639 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
641 if (stream.ibuf == MAP_FAILED) {
648 * Modify the reference table to contain the offsets and
649 * not the lengths of the instructions.
652 for (i = 1; i < nins + 1; i++)
653 stream.refs[i] += stream.refs[i - 1];
655 /* Reset the counters. */
659 /* The second pass creates the actual code. */
664 * The reference table is needed only during compilation,
665 * now we can free it.
669 free(stream.refs, M_BPFJIT);
675 if (stream.ibuf != NULL &&
676 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
677 munmap(stream.ibuf, *size);
682 return ((bpf_filter_func)(void *)stream.ibuf);