2 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
3 * Copyright (C) 2005-2009 Jung-uk Kim <jkim@FreeBSD.org>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the Politecnico di Torino nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD$");
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/kernel.h>
40 #include <sys/socket.h>
41 #include <sys/malloc.h>
47 #include <sys/param.h>
50 #include <sys/types.h>
53 #include <net/bpf_jitter.h>
55 #include <i386/i386/bpf_jit_machdep.h>
57 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *);
60 * Emit routine to update the jump table.
63 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
66 if (stream->refs != NULL)
67 (stream->refs)[stream->bpf_pc] += len;
68 stream->cur_ip += len;
72 * Emit routine to output the actual binary code.
75 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
80 stream->ibuf[stream->cur_ip] = (u_char)value;
85 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
90 *((u_int *)(stream->ibuf + stream->cur_ip)) = value;
99 * Scan the filter program and find possible optimization.
102 bpf_jit_optimize(struct bpf_insn *prog, u_int nins)
107 /* Do we return immediately? */
108 if (BPF_CLASS(prog[0].code) == BPF_RET)
109 return (BPF_JIT_FRET);
111 for (flags = 0, i = 0; i < nins; i++) {
112 switch (prog[i].code) {
113 case BPF_LD|BPF_W|BPF_ABS:
114 case BPF_LD|BPF_H|BPF_ABS:
115 case BPF_LD|BPF_B|BPF_ABS:
116 case BPF_LD|BPF_W|BPF_IND:
117 case BPF_LD|BPF_H|BPF_IND:
118 case BPF_LD|BPF_B|BPF_IND:
119 case BPF_LDX|BPF_MSH|BPF_B:
120 flags |= BPF_JIT_FPKT;
123 case BPF_LDX|BPF_MEM:
126 flags |= BPF_JIT_FMEM;
129 case BPF_JMP|BPF_JGT|BPF_K:
130 case BPF_JMP|BPF_JGE|BPF_K:
131 case BPF_JMP|BPF_JEQ|BPF_K:
132 case BPF_JMP|BPF_JSET|BPF_K:
133 case BPF_JMP|BPF_JGT|BPF_X:
134 case BPF_JMP|BPF_JGE|BPF_X:
135 case BPF_JMP|BPF_JEQ|BPF_X:
136 case BPF_JMP|BPF_JSET|BPF_X:
137 flags |= BPF_JIT_FJMP;
139 case BPF_ALU|BPF_DIV|BPF_K:
140 flags |= BPF_JIT_FADK;
143 if (flags == BPF_JIT_FLAG_ALL)
151 * Function that does the real stuff.
154 bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size)
156 bpf_bin_stream stream;
157 struct bpf_insn *ins;
158 int flags, fret, fpkt, fmem, fjmp, fadk;
163 * NOTE: Do not modify the name of this variable, as it's used by
164 * the macros to emit code.
168 flags = bpf_jit_optimize(prog, nins);
169 fret = (flags & BPF_JIT_FRET) != 0;
170 fpkt = (flags & BPF_JIT_FPKT) != 0;
171 fmem = (flags & BPF_JIT_FMEM) != 0;
172 fjmp = (flags & BPF_JIT_FJMP) != 0;
173 fadk = (flags & BPF_JIT_FADK) != 0;
174 save_esp = (fpkt || fmem || fadk); /* Stack is used. */
179 memset(&stream, 0, sizeof(stream));
181 /* Allocate the reference table for the jumps. */
184 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
187 stream.refs = calloc(nins + 1, sizeof(u_int));
189 if (stream.refs == NULL)
194 * The first pass will emit the lengths of the instructions
195 * to create the reference table.
199 for (pass = 0; pass < 2; pass++) {
202 /* Create the procedure header. */
208 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP);
215 MOVodd(16, EBP, EDI);
218 for (i = 0; i < nins; i++) {
254 case BPF_LD|BPF_W|BPF_ABS:
260 CMPid(sizeof(int32_t), ECX);
268 MOVobd(EBX, ESI, EAX);
272 case BPF_LD|BPF_H|BPF_ABS:
279 CMPid(sizeof(int16_t), ECX);
286 MOVobw(EBX, ESI, AX);
290 case BPF_LD|BPF_B|BPF_ABS:
300 MOVobb(EBX, ESI, AL);
303 case BPF_LD|BPF_W|BPF_LEN:
305 MOVodd(12, EBP, EAX);
308 MOVodd(12, ECX, EAX);
312 case BPF_LDX|BPF_W|BPF_LEN:
314 MOVodd(12, EBP, EDX);
317 MOVodd(12, ECX, EDX);
321 case BPF_LD|BPF_W|BPF_IND:
332 CMPid(sizeof(int32_t), ECX);
340 MOVobd(EBX, ESI, EAX);
344 case BPF_LD|BPF_H|BPF_IND:
356 CMPid(sizeof(int16_t), ECX);
363 MOVobw(EBX, ESI, AX);
367 case BPF_LD|BPF_B|BPF_IND:
382 MOVobb(EBX, ESI, AL);
385 case BPF_LDX|BPF_MSH|BPF_B:
396 MOVobb(EBX, ESI, DL);
405 case BPF_LDX|BPF_IMM:
411 MOVid(((int)ins->k - BPF_MEMWORDS) *
412 sizeof(uint32_t), ESI);
413 MOVobd(ECX, ESI, EAX);
416 case BPF_LDX|BPF_MEM:
418 MOVid(((int)ins->k - BPF_MEMWORDS) *
419 sizeof(uint32_t), ESI);
420 MOVobd(ECX, ESI, EDX);
425 * XXX this command and the following could
426 * be optimized if the previous instruction
427 * was already of this type
430 MOVid(((int)ins->k - BPF_MEMWORDS) *
431 sizeof(uint32_t), ESI);
432 MOVomd(EAX, ECX, ESI);
437 MOVid(((int)ins->k - BPF_MEMWORDS) *
438 sizeof(uint32_t), ESI);
439 MOVomd(EDX, ECX, ESI);
446 case BPF_JMP|BPF_JGT|BPF_K:
447 if (ins->jt == ins->jf) {
455 case BPF_JMP|BPF_JGE|BPF_K:
456 if (ins->jt == ins->jf) {
464 case BPF_JMP|BPF_JEQ|BPF_K:
465 if (ins->jt == ins->jf) {
473 case BPF_JMP|BPF_JSET|BPF_K:
474 if (ins->jt == ins->jf) {
482 case BPF_JMP|BPF_JGT|BPF_X:
483 if (ins->jt == ins->jf) {
491 case BPF_JMP|BPF_JGE|BPF_X:
492 if (ins->jt == ins->jf) {
500 case BPF_JMP|BPF_JEQ|BPF_X:
501 if (ins->jt == ins->jf) {
509 case BPF_JMP|BPF_JSET|BPF_X:
510 if (ins->jt == ins->jf) {
518 case BPF_ALU|BPF_ADD|BPF_X:
522 case BPF_ALU|BPF_SUB|BPF_X:
526 case BPF_ALU|BPF_MUL|BPF_X:
532 case BPF_ALU|BPF_DIV|BPF_X:
557 case BPF_ALU|BPF_AND|BPF_X:
561 case BPF_ALU|BPF_OR|BPF_X:
565 case BPF_ALU|BPF_LSH|BPF_X:
570 case BPF_ALU|BPF_RSH|BPF_X:
575 case BPF_ALU|BPF_ADD|BPF_K:
579 case BPF_ALU|BPF_SUB|BPF_K:
583 case BPF_ALU|BPF_MUL|BPF_K:
590 case BPF_ALU|BPF_DIV|BPF_K:
598 case BPF_ALU|BPF_AND|BPF_K:
602 case BPF_ALU|BPF_OR|BPF_K:
606 case BPF_ALU|BPF_LSH|BPF_K:
607 SHLib((ins->k) & 0xff, EAX);
610 case BPF_ALU|BPF_RSH|BPF_K:
611 SHRib((ins->k) & 0xff, EAX);
614 case BPF_ALU|BPF_NEG:
618 case BPF_MISC|BPF_TAX:
622 case BPF_MISC|BPF_TXA:
632 *size = stream.cur_ip;
634 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT);
635 if (stream.ibuf == NULL)
638 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
640 if (stream.ibuf == MAP_FAILED) {
647 * Modify the reference table to contain the offsets and
648 * not the lengths of the instructions.
651 for (i = 1; i < nins + 1; i++)
652 stream.refs[i] += stream.refs[i - 1];
654 /* Reset the counters. */
658 /* The second pass creates the actual code. */
663 * The reference table is needed only during compilation,
664 * now we can free it.
668 free(stream.refs, M_BPFJIT);
674 if (stream.ibuf != NULL &&
675 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
676 munmap(stream.ibuf, *size);
681 return ((bpf_filter_func)stream.ibuf);