/* $NetBSD: bpfjit.c,v 1.47 2019/01/20 23:36:57 alnsn Exp $ */ /*- * Copyright (c) 2011-2015 Alexander Nasonov. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include #ifdef _KERNEL __KERNEL_RCSID(0, "$NetBSD: bpfjit.c,v 1.47 2019/01/20 23:36:57 alnsn Exp $"); #else __RCSID("$NetBSD: bpfjit.c,v 1.47 2019/01/20 23:36:57 alnsn Exp $"); #endif #include #include #ifndef _KERNEL #include #define BJ_ASSERT(c) assert(c) #else #define BJ_ASSERT(c) KASSERT(c) #endif #ifndef _KERNEL #include #define BJ_ALLOC(sz) malloc(sz) #define BJ_FREE(p, sz) free(p) #else #include #define BJ_ALLOC(sz) kmem_alloc(sz, KM_SLEEP) #define BJ_FREE(p, sz) kmem_free(p, sz) #endif #ifndef _KERNEL #include #include #include #include #include #else #include #include #endif #define __BPF_PRIVATE #include #include #include #if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE #include /* for stderr */ #endif /* * Number of saved registers to pass to sljit_emit_enter() function. */ #define NSAVEDS 3 /* * Arguments of generated bpfjit_func_t. * The first argument is reassigned upon entry * to a more frequently used buf argument. */ #define BJ_CTX_ARG SLJIT_S0 #define BJ_ARGS SLJIT_S1 /* * Permanent register assignments. */ #define BJ_BUF SLJIT_S0 //#define BJ_ARGS SLJIT_S1 #define BJ_BUFLEN SLJIT_S2 #define BJ_AREG SLJIT_R0 #define BJ_TMP1REG SLJIT_R1 #define BJ_TMP2REG SLJIT_R2 #define BJ_XREG SLJIT_R3 #define BJ_TMP3REG SLJIT_R4 #ifdef _KERNEL #define MAX_MEMWORDS BPF_MAX_MEMWORDS #else #define MAX_MEMWORDS BPF_MEMWORDS #endif #define BJ_INIT_NOBITS ((bpf_memword_init_t)0) #define BJ_INIT_MBIT(k) BPF_MEMWORD_INIT(k) #define BJ_INIT_ABIT BJ_INIT_MBIT(MAX_MEMWORDS) #define BJ_INIT_XBIT BJ_INIT_MBIT(MAX_MEMWORDS + 1) /* * Get a number of memwords and external memwords from a bpf_ctx object. */ #define GET_EXTWORDS(bc) ((bc) ? (bc)->extwords : 0) #define GET_MEMWORDS(bc) (GET_EXTWORDS(bc) ? GET_EXTWORDS(bc) : BPF_MEMWORDS) /* * Optimization hints. */ typedef unsigned int bpfjit_hint_t; #define BJ_HINT_ABS 0x01 /* packet read at absolute offset */ #define BJ_HINT_IND 0x02 /* packet read at variable offset */ #define BJ_HINT_MSH 0x04 /* BPF_MSH instruction */ #define BJ_HINT_COP 0x08 /* BPF_COP or BPF_COPX instruction */ #define BJ_HINT_COPX 0x10 /* BPF_COPX instruction */ #define BJ_HINT_XREG 0x20 /* BJ_XREG is needed */ #define BJ_HINT_LDX 0x40 /* BPF_LDX instruction */ #define BJ_HINT_PKT (BJ_HINT_ABS|BJ_HINT_IND|BJ_HINT_MSH) /* * Datatype for Array Bounds Check Elimination (ABC) pass. */ typedef uint64_t bpfjit_abc_length_t; #define MAX_ABC_LENGTH (UINT32_MAX + UINT64_C(4)) /* max. width is 4 */ struct bpfjit_stack { bpf_ctx_t *ctx; uint32_t *extmem; /* pointer to external memory store */ uint32_t reg; /* saved A or X register */ #ifdef _KERNEL int err; /* 3rd argument for m_xword/m_xhalf/m_xbyte function call */ #endif uint32_t mem[BPF_MEMWORDS]; /* internal memory store */ }; /* * Data for BPF_JMP instruction. * Forward declaration for struct bpfjit_jump. */ struct bpfjit_jump_data; /* * Node of bjumps list. */ struct bpfjit_jump { struct sljit_jump *sjump; SLIST_ENTRY(bpfjit_jump) entries; struct bpfjit_jump_data *jdata; }; /* * Data for BPF_JMP instruction. */ struct bpfjit_jump_data { /* * These entries make up bjumps list: * jtf[0] - when coming from jt path, * jtf[1] - when coming from jf path. */ struct bpfjit_jump jtf[2]; /* * Length calculated by Array Bounds Check Elimination (ABC) pass. */ bpfjit_abc_length_t abc_length; /* * Length checked by the last out-of-bounds check. */ bpfjit_abc_length_t checked_length; }; /* * Data for "read from packet" instructions. * See also read_pkt_insn() function below. */ struct bpfjit_read_pkt_data { /* * Length calculated by Array Bounds Check Elimination (ABC) pass. */ bpfjit_abc_length_t abc_length; /* * If positive, emit "if (buflen < check_length) return 0" * out-of-bounds check. * Values greater than UINT32_MAX generate unconditional "return 0". */ bpfjit_abc_length_t check_length; }; /* * Additional (optimization-related) data for bpf_insn. */ struct bpfjit_insn_data { /* List of jumps to this insn. */ SLIST_HEAD(, bpfjit_jump) bjumps; union { struct bpfjit_jump_data jdata; struct bpfjit_read_pkt_data rdata; } u; bpf_memword_init_t invalid; bool unreachable; }; #ifdef _KERNEL uint32_t m_xword(const struct mbuf *, uint32_t, int *); uint32_t m_xhalf(const struct mbuf *, uint32_t, int *); uint32_t m_xbyte(const struct mbuf *, uint32_t, int *); MODULE(MODULE_CLASS_MISC, bpfjit, "sljit") static int bpfjit_modcmd(modcmd_t cmd, void *arg) { switch (cmd) { case MODULE_CMD_INIT: bpfjit_module_ops.bj_free_code = &bpfjit_free_code; membar_producer(); bpfjit_module_ops.bj_generate_code = &bpfjit_generate_code; membar_producer(); return 0; case MODULE_CMD_FINI: return EOPNOTSUPP; default: return ENOTTY; } } #endif /* * Return a number of scratch registers to pass * to sljit_emit_enter() function. */ static sljit_s32 nscratches(bpfjit_hint_t hints) { sljit_s32 rv = 2; #ifdef _KERNEL if (hints & BJ_HINT_PKT) rv = 3; /* xcall with three arguments */ #endif if (hints & BJ_HINT_IND) rv = 3; /* uses BJ_TMP2REG */ if (hints & BJ_HINT_COP) rv = 3; /* calls copfunc with three arguments */ if (hints & BJ_HINT_XREG) rv = 4; /* uses BJ_XREG */ #ifdef _KERNEL if (hints & BJ_HINT_LDX) rv = 5; /* uses BJ_TMP3REG */ #endif if (hints & BJ_HINT_COPX) rv = 5; /* uses BJ_TMP3REG */ return rv; } static uint32_t read_width(const struct bpf_insn *pc) { switch (BPF_SIZE(pc->code)) { case BPF_W: return 4; case BPF_H: return 2; case BPF_B: return 1; default: return 0; } } /* * Copy buf and buflen members of bpf_args from BJ_ARGS * pointer to BJ_BUF and BJ_BUFLEN registers. */ static int load_buf_buflen(struct sljit_compiler *compiler) { int status; status = sljit_emit_op1(compiler, SLJIT_MOV_P, BJ_BUF, 0, SLJIT_MEM1(BJ_ARGS), offsetof(struct bpf_args, pkt)); if (status != SLJIT_SUCCESS) return status; status = sljit_emit_op1(compiler, SLJIT_MOV, /* size_t source */ BJ_BUFLEN, 0, SLJIT_MEM1(BJ_ARGS), offsetof(struct bpf_args, buflen)); return status; } static bool grow_jumps(struct sljit_jump ***jumps, size_t *size) { struct sljit_jump **newptr; const size_t elemsz = sizeof(struct sljit_jump *); size_t old_size = *size; size_t new_size = 2 * old_size; if (new_size < old_size || new_size > SIZE_MAX / elemsz) return false; newptr = BJ_ALLOC(new_size * elemsz); if (newptr == NULL) return false; memcpy(newptr, *jumps, old_size * elemsz); BJ_FREE(*jumps, old_size * elemsz); *jumps = newptr; *size = new_size; return true; } static bool append_jump(struct sljit_jump *jump, struct sljit_jump ***jumps, size_t *size, size_t *max_size) { if (*size == *max_size && !grow_jumps(jumps, max_size)) return false; (*jumps)[(*size)++] = jump; return true; } /* * Emit code for BPF_LD+BPF_B+BPF_ABS A <- P[k:1]. */ static int emit_read8(struct sljit_compiler *compiler, sljit_s32 src, uint32_t k) { return sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_AREG, 0, SLJIT_MEM1(src), k); } /* * Emit code for BPF_LD+BPF_H+BPF_ABS A <- P[k:2]. */ static int emit_read16(struct sljit_compiler *compiler, sljit_s32 src, uint32_t k) { int status; BJ_ASSERT(k <= UINT32_MAX - 1); /* A = buf[k]; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_AREG, 0, SLJIT_MEM1(src), k); if (status != SLJIT_SUCCESS) return status; /* tmp1 = buf[k+1]; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_TMP1REG, 0, SLJIT_MEM1(src), k+1); if (status != SLJIT_SUCCESS) return status; /* A = A << 8; */ status = sljit_emit_op2(compiler, SLJIT_SHL, BJ_AREG, 0, BJ_AREG, 0, SLJIT_IMM, 8); if (status != SLJIT_SUCCESS) return status; /* A = A + tmp1; */ status = sljit_emit_op2(compiler, SLJIT_ADD, BJ_AREG, 0, BJ_AREG, 0, BJ_TMP1REG, 0); return status; } /* * Emit code for BPF_LD+BPF_W+BPF_ABS A <- P[k:4]. */ static int emit_read32(struct sljit_compiler *compiler, sljit_s32 src, uint32_t k) { int status; BJ_ASSERT(k <= UINT32_MAX - 3); /* A = buf[k]; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_AREG, 0, SLJIT_MEM1(src), k); if (status != SLJIT_SUCCESS) return status; /* tmp1 = buf[k+1]; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_TMP1REG, 0, SLJIT_MEM1(src), k+1); if (status != SLJIT_SUCCESS) return status; /* A = A << 8; */ status = sljit_emit_op2(compiler, SLJIT_SHL, BJ_AREG, 0, BJ_AREG, 0, SLJIT_IMM, 8); if (status != SLJIT_SUCCESS) return status; /* A = A + tmp1; */ status = sljit_emit_op2(compiler, SLJIT_ADD, BJ_AREG, 0, BJ_AREG, 0, BJ_TMP1REG, 0); if (status != SLJIT_SUCCESS) return status; /* tmp1 = buf[k+2]; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_TMP1REG, 0, SLJIT_MEM1(src), k+2); if (status != SLJIT_SUCCESS) return status; /* A = A << 8; */ status = sljit_emit_op2(compiler, SLJIT_SHL, BJ_AREG, 0, BJ_AREG, 0, SLJIT_IMM, 8); if (status != SLJIT_SUCCESS) return status; /* A = A + tmp1; */ status = sljit_emit_op2(compiler, SLJIT_ADD, BJ_AREG, 0, BJ_AREG, 0, BJ_TMP1REG, 0); if (status != SLJIT_SUCCESS) return status; /* tmp1 = buf[k+3]; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_TMP1REG, 0, SLJIT_MEM1(src), k+3); if (status != SLJIT_SUCCESS) return status; /* A = A << 8; */ status = sljit_emit_op2(compiler, SLJIT_SHL, BJ_AREG, 0, BJ_AREG, 0, SLJIT_IMM, 8); if (status != SLJIT_SUCCESS) return status; /* A = A + tmp1; */ status = sljit_emit_op2(compiler, SLJIT_ADD, BJ_AREG, 0, BJ_AREG, 0, BJ_TMP1REG, 0); return status; } #ifdef _KERNEL /* * Emit code for m_xword/m_xhalf/m_xbyte call. * * @pc BPF_LD+BPF_W+BPF_ABS A <- P[k:4] * BPF_LD+BPF_H+BPF_ABS A <- P[k:2] * BPF_LD+BPF_B+BPF_ABS A <- P[k:1] * BPF_LD+BPF_W+BPF_IND A <- P[X+k:4] * BPF_LD+BPF_H+BPF_IND A <- P[X+k:2] * BPF_LD+BPF_B+BPF_IND A <- P[X+k:1] * BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) */ static int emit_xcall(struct sljit_compiler *compiler, bpfjit_hint_t hints, const struct bpf_insn *pc, int dst, struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize, uint32_t (*fn)(const struct mbuf *, uint32_t, int *)) { #if BJ_XREG == SLJIT_RETURN_REG || \ BJ_XREG == SLJIT_R0 || \ BJ_XREG == SLJIT_R1 || \ BJ_XREG == SLJIT_R2 #error "Not supported assignment of registers." #endif struct sljit_jump *jump; sljit_s32 save_reg; int status; save_reg = (BPF_CLASS(pc->code) == BPF_LDX) ? BJ_AREG : BJ_XREG; if (save_reg == BJ_AREG || (hints & BJ_HINT_XREG)) { /* save A or X */ status = sljit_emit_op1(compiler, SLJIT_MOV_U32, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, reg), save_reg, 0); if (status != SLJIT_SUCCESS) return status; } /* * Prepare registers for fn(mbuf, k, &err) call. */ status = sljit_emit_op1(compiler, SLJIT_MOV, SLJIT_R0, 0, BJ_BUF, 0); if (status != SLJIT_SUCCESS) return status; if (BPF_CLASS(pc->code) == BPF_LD && BPF_MODE(pc->code) == BPF_IND) { if (pc->k == 0) { /* k = X; */ status = sljit_emit_op1(compiler, SLJIT_MOV, SLJIT_R1, 0, BJ_XREG, 0); if (status != SLJIT_SUCCESS) return status; } else { /* if (X > UINT32_MAX - pc->k) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_GREATER, BJ_XREG, 0, SLJIT_IMM, UINT32_MAX - pc->k); if (jump == NULL) return SLJIT_ERR_ALLOC_FAILED; if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) return SLJIT_ERR_ALLOC_FAILED; /* k = X + pc->k; */ status = sljit_emit_op2(compiler, SLJIT_ADD, SLJIT_R1, 0, BJ_XREG, 0, SLJIT_IMM, (uint32_t)pc->k); if (status != SLJIT_SUCCESS) return status; } } else { /* k = pc->k */ status = sljit_emit_op1(compiler, SLJIT_MOV, SLJIT_R1, 0, SLJIT_IMM, (uint32_t)pc->k); if (status != SLJIT_SUCCESS) return status; } /* * The third argument of fn is an address on stack. */ status = sljit_get_local_base(compiler, SLJIT_R2, 0, offsetof(struct bpfjit_stack, err)); if (status != SLJIT_SUCCESS) return status; /* fn(buf, k, &err); */ status = sljit_emit_ijump(compiler, SLJIT_CALL3, SLJIT_IMM, SLJIT_FUNC_OFFSET(fn)); if (status != SLJIT_SUCCESS) return status; if (dst != SLJIT_RETURN_REG) { /* move return value to dst */ status = sljit_emit_op1(compiler, SLJIT_MOV, dst, 0, SLJIT_RETURN_REG, 0); if (status != SLJIT_SUCCESS) return status; } /* if (*err != 0) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_NOT_EQUAL|SLJIT_I32_OP, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, err), SLJIT_IMM, 0); if (jump == NULL) return SLJIT_ERR_ALLOC_FAILED; if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) return SLJIT_ERR_ALLOC_FAILED; if (save_reg == BJ_AREG || (hints & BJ_HINT_XREG)) { /* restore A or X */ status = sljit_emit_op1(compiler, SLJIT_MOV_U32, save_reg, 0, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, reg)); if (status != SLJIT_SUCCESS) return status; } return SLJIT_SUCCESS; } #endif /* * Emit code for BPF_COP and BPF_COPX instructions. */ static int emit_cop(struct sljit_compiler *compiler, bpfjit_hint_t hints, const bpf_ctx_t *bc, const struct bpf_insn *pc, struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize) { #if BJ_XREG == SLJIT_RETURN_REG || \ BJ_XREG == SLJIT_R0 || \ BJ_XREG == SLJIT_R1 || \ BJ_XREG == SLJIT_R2 || \ BJ_TMP3REG == SLJIT_R0 || \ BJ_TMP3REG == SLJIT_R1 || \ BJ_TMP3REG == SLJIT_R2 #error "Not supported assignment of registers." #endif struct sljit_jump *jump; sljit_s32 call_reg; sljit_sw call_off; int status; BJ_ASSERT(bc != NULL && bc->copfuncs != NULL); if (hints & BJ_HINT_LDX) { /* save X */ status = sljit_emit_op1(compiler, SLJIT_MOV_U32, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, reg), BJ_XREG, 0); if (status != SLJIT_SUCCESS) return status; } if (BPF_MISCOP(pc->code) == BPF_COP) { call_reg = SLJIT_IMM; call_off = SLJIT_FUNC_OFFSET(bc->copfuncs[pc->k]); } else { /* if (X >= bc->nfuncs) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_GREATER_EQUAL, BJ_XREG, 0, SLJIT_IMM, bc->nfuncs); if (jump == NULL) return SLJIT_ERR_ALLOC_FAILED; if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) return SLJIT_ERR_ALLOC_FAILED; /* tmp1 = ctx; */ status = sljit_emit_op1(compiler, SLJIT_MOV_P, BJ_TMP1REG, 0, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, ctx)); if (status != SLJIT_SUCCESS) return status; /* tmp1 = ctx->copfuncs; */ status = sljit_emit_op1(compiler, SLJIT_MOV_P, BJ_TMP1REG, 0, SLJIT_MEM1(BJ_TMP1REG), offsetof(struct bpf_ctx, copfuncs)); if (status != SLJIT_SUCCESS) return status; /* tmp2 = X; */ status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_TMP2REG, 0, BJ_XREG, 0); if (status != SLJIT_SUCCESS) return status; /* tmp3 = ctx->copfuncs[tmp2]; */ call_reg = BJ_TMP3REG; call_off = 0; status = sljit_emit_op1(compiler, SLJIT_MOV_P, call_reg, call_off, SLJIT_MEM2(BJ_TMP1REG, BJ_TMP2REG), SLJIT_WORD_SHIFT); if (status != SLJIT_SUCCESS) return status; } /* * Copy bpf_copfunc_t arguments to registers. */ #if BJ_AREG != SLJIT_R2 status = sljit_emit_op1(compiler, SLJIT_MOV_U32, SLJIT_R2, 0, BJ_AREG, 0); if (status != SLJIT_SUCCESS) return status; #endif status = sljit_emit_op1(compiler, SLJIT_MOV_P, SLJIT_R0, 0, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, ctx)); if (status != SLJIT_SUCCESS) return status; status = sljit_emit_op1(compiler, SLJIT_MOV_P, SLJIT_R1, 0, BJ_ARGS, 0); if (status != SLJIT_SUCCESS) return status; status = sljit_emit_ijump(compiler, SLJIT_CALL3, call_reg, call_off); if (status != SLJIT_SUCCESS) return status; #if BJ_AREG != SLJIT_RETURN_REG status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, SLJIT_RETURN_REG, 0); if (status != SLJIT_SUCCESS) return status; #endif if (hints & BJ_HINT_LDX) { /* restore X */ status = sljit_emit_op1(compiler, SLJIT_MOV_U32, BJ_XREG, 0, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, reg)); if (status != SLJIT_SUCCESS) return status; } return SLJIT_SUCCESS; } /* * Generate code for * BPF_LD+BPF_W+BPF_ABS A <- P[k:4] * BPF_LD+BPF_H+BPF_ABS A <- P[k:2] * BPF_LD+BPF_B+BPF_ABS A <- P[k:1] * BPF_LD+BPF_W+BPF_IND A <- P[X+k:4] * BPF_LD+BPF_H+BPF_IND A <- P[X+k:2] * BPF_LD+BPF_B+BPF_IND A <- P[X+k:1] */ static int emit_pkt_read(struct sljit_compiler *compiler, bpfjit_hint_t hints, const struct bpf_insn *pc, struct sljit_jump *to_mchain_jump, struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize) { int status = SLJIT_ERR_ALLOC_FAILED; uint32_t width; sljit_s32 ld_reg; struct sljit_jump *jump; #ifdef _KERNEL struct sljit_label *label; struct sljit_jump *over_mchain_jump; const bool check_zero_buflen = (to_mchain_jump != NULL); #endif const uint32_t k = pc->k; #ifdef _KERNEL if (to_mchain_jump == NULL) { to_mchain_jump = sljit_emit_cmp(compiler, SLJIT_EQUAL, BJ_BUFLEN, 0, SLJIT_IMM, 0); if (to_mchain_jump == NULL) return SLJIT_ERR_ALLOC_FAILED; } #endif ld_reg = BJ_BUF; width = read_width(pc); if (width == 0) return SLJIT_ERR_ALLOC_FAILED; if (BPF_MODE(pc->code) == BPF_IND) { /* tmp1 = buflen - (pc->k + width); */ status = sljit_emit_op2(compiler, SLJIT_SUB, BJ_TMP1REG, 0, BJ_BUFLEN, 0, SLJIT_IMM, k + width); if (status != SLJIT_SUCCESS) return status; /* ld_reg = buf + X; */ ld_reg = BJ_TMP2REG; status = sljit_emit_op2(compiler, SLJIT_ADD, ld_reg, 0, BJ_BUF, 0, BJ_XREG, 0); if (status != SLJIT_SUCCESS) return status; /* if (tmp1 < X) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_LESS, BJ_TMP1REG, 0, BJ_XREG, 0); if (jump == NULL) return SLJIT_ERR_ALLOC_FAILED; if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) return SLJIT_ERR_ALLOC_FAILED; } /* * Don't emit wrapped-around reads. They're dead code but * dead code elimination logic isn't smart enough to figure * it out. */ if (k <= UINT32_MAX - width + 1) { switch (width) { case 4: status = emit_read32(compiler, ld_reg, k); break; case 2: status = emit_read16(compiler, ld_reg, k); break; case 1: status = emit_read8(compiler, ld_reg, k); break; } if (status != SLJIT_SUCCESS) return status; } #ifdef _KERNEL over_mchain_jump = sljit_emit_jump(compiler, SLJIT_JUMP); if (over_mchain_jump == NULL) return SLJIT_ERR_ALLOC_FAILED; /* entry point to mchain handler */ label = sljit_emit_label(compiler); if (label == NULL) return SLJIT_ERR_ALLOC_FAILED; sljit_set_label(to_mchain_jump, label); if (check_zero_buflen) { /* if (buflen != 0) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_NOT_EQUAL, BJ_BUFLEN, 0, SLJIT_IMM, 0); if (jump == NULL) return SLJIT_ERR_ALLOC_FAILED; if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) return SLJIT_ERR_ALLOC_FAILED; } switch (width) { case 4: status = emit_xcall(compiler, hints, pc, BJ_AREG, ret0, ret0_size, ret0_maxsize, &m_xword); break; case 2: status = emit_xcall(compiler, hints, pc, BJ_AREG, ret0, ret0_size, ret0_maxsize, &m_xhalf); break; case 1: status = emit_xcall(compiler, hints, pc, BJ_AREG, ret0, ret0_size, ret0_maxsize, &m_xbyte); break; } if (status != SLJIT_SUCCESS) return status; label = sljit_emit_label(compiler); if (label == NULL) return SLJIT_ERR_ALLOC_FAILED; sljit_set_label(over_mchain_jump, label); #endif return SLJIT_SUCCESS; } static int emit_memload(struct sljit_compiler *compiler, sljit_s32 dst, uint32_t k, size_t extwords) { int status; sljit_s32 src; sljit_sw srcw; srcw = k * sizeof(uint32_t); if (extwords == 0) { src = SLJIT_MEM1(SLJIT_SP); srcw += offsetof(struct bpfjit_stack, mem); } else { /* copy extmem pointer to the tmp1 register */ status = sljit_emit_op1(compiler, SLJIT_MOV_P, BJ_TMP1REG, 0, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, extmem)); if (status != SLJIT_SUCCESS) return status; src = SLJIT_MEM1(BJ_TMP1REG); } return sljit_emit_op1(compiler, SLJIT_MOV_U32, dst, 0, src, srcw); } static int emit_memstore(struct sljit_compiler *compiler, sljit_s32 src, uint32_t k, size_t extwords) { int status; sljit_s32 dst; sljit_sw dstw; dstw = k * sizeof(uint32_t); if (extwords == 0) { dst = SLJIT_MEM1(SLJIT_SP); dstw += offsetof(struct bpfjit_stack, mem); } else { /* copy extmem pointer to the tmp1 register */ status = sljit_emit_op1(compiler, SLJIT_MOV_P, BJ_TMP1REG, 0, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, extmem)); if (status != SLJIT_SUCCESS) return status; dst = SLJIT_MEM1(BJ_TMP1REG); } return sljit_emit_op1(compiler, SLJIT_MOV_U32, dst, dstw, src, 0); } /* * Emit code for BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf). */ static int emit_msh(struct sljit_compiler *compiler, bpfjit_hint_t hints, const struct bpf_insn *pc, struct sljit_jump *to_mchain_jump, struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize) { int status; #ifdef _KERNEL struct sljit_label *label; struct sljit_jump *jump, *over_mchain_jump; const bool check_zero_buflen = (to_mchain_jump != NULL); #endif const uint32_t k = pc->k; #ifdef _KERNEL if (to_mchain_jump == NULL) { to_mchain_jump = sljit_emit_cmp(compiler, SLJIT_EQUAL, BJ_BUFLEN, 0, SLJIT_IMM, 0); if (to_mchain_jump == NULL) return SLJIT_ERR_ALLOC_FAILED; } #endif /* tmp1 = buf[k] */ status = sljit_emit_op1(compiler, SLJIT_MOV_U8, BJ_TMP1REG, 0, SLJIT_MEM1(BJ_BUF), k); if (status != SLJIT_SUCCESS) return status; #ifdef _KERNEL over_mchain_jump = sljit_emit_jump(compiler, SLJIT_JUMP); if (over_mchain_jump == NULL) return SLJIT_ERR_ALLOC_FAILED; /* entry point to mchain handler */ label = sljit_emit_label(compiler); if (label == NULL) return SLJIT_ERR_ALLOC_FAILED; sljit_set_label(to_mchain_jump, label); if (check_zero_buflen) { /* if (buflen != 0) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_NOT_EQUAL, BJ_BUFLEN, 0, SLJIT_IMM, 0); if (jump == NULL) return SLJIT_ERR_ALLOC_FAILED; if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) return SLJIT_ERR_ALLOC_FAILED; } status = emit_xcall(compiler, hints, pc, BJ_TMP1REG, ret0, ret0_size, ret0_maxsize, &m_xbyte); if (status != SLJIT_SUCCESS) return status; label = sljit_emit_label(compiler); if (label == NULL) return SLJIT_ERR_ALLOC_FAILED; sljit_set_label(over_mchain_jump, label); #endif /* tmp1 &= 0xf */ status = sljit_emit_op2(compiler, SLJIT_AND, BJ_TMP1REG, 0, BJ_TMP1REG, 0, SLJIT_IMM, 0xf); if (status != SLJIT_SUCCESS) return status; /* X = tmp1 << 2 */ status = sljit_emit_op2(compiler, SLJIT_SHL, BJ_XREG, 0, BJ_TMP1REG, 0, SLJIT_IMM, 2); if (status != SLJIT_SUCCESS) return status; return SLJIT_SUCCESS; } /* * Emit code for A = A / k or A = A % k when k is a power of 2. * @pc BPF_DIV or BPF_MOD instruction. */ static int emit_pow2_moddiv(struct sljit_compiler *compiler, const struct bpf_insn *pc) { uint32_t k = pc->k; int status = SLJIT_SUCCESS; BJ_ASSERT(k != 0 && (k & (k - 1)) == 0); if (BPF_OP(pc->code) == BPF_MOD) { status = sljit_emit_op2(compiler, SLJIT_AND, BJ_AREG, 0, BJ_AREG, 0, SLJIT_IMM, k - 1); } else { int shift = 0; /* * Do shift = __builtin_ctz(k). * The loop is slower, but that's ok. */ while (k > 1) { k >>= 1; shift++; } if (shift != 0) { status = sljit_emit_op2(compiler, SLJIT_LSHR|SLJIT_I32_OP, BJ_AREG, 0, BJ_AREG, 0, SLJIT_IMM, shift); } } return status; } #if !defined(BPFJIT_USE_UDIV) static sljit_uw divide(sljit_uw x, sljit_uw y) { return (uint32_t)x / (uint32_t)y; } static sljit_uw modulus(sljit_uw x, sljit_uw y) { return (uint32_t)x % (uint32_t)y; } #endif /* * Emit code for A = A / div or A = A % div. * @pc BPF_DIV or BPF_MOD instruction. */ static int emit_moddiv(struct sljit_compiler *compiler, const struct bpf_insn *pc) { int status; const bool xdiv = BPF_OP(pc->code) == BPF_DIV; const bool xreg = BPF_SRC(pc->code) == BPF_X; #if BJ_XREG == SLJIT_RETURN_REG || \ BJ_XREG == SLJIT_R0 || \ BJ_XREG == SLJIT_R1 || \ BJ_AREG == SLJIT_R1 #error "Not supported assignment of registers." #endif #if BJ_AREG != SLJIT_R0 status = sljit_emit_op1(compiler, SLJIT_MOV, SLJIT_R0, 0, BJ_AREG, 0); if (status != SLJIT_SUCCESS) return status; #endif status = sljit_emit_op1(compiler, SLJIT_MOV, SLJIT_R1, 0, xreg ? BJ_XREG : SLJIT_IMM, xreg ? 0 : (uint32_t)pc->k); if (status != SLJIT_SUCCESS) return status; #if defined(BPFJIT_USE_UDIV) status = sljit_emit_op0(compiler, SLJIT_UDIV|SLJIT_I32_OP); if (BPF_OP(pc->code) == BPF_DIV) { #if BJ_AREG != SLJIT_R0 status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, SLJIT_R0, 0); #endif } else { #if BJ_AREG != SLJIT_R1 /* Remainder is in SLJIT_R1. */ status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, SLJIT_R1, 0); #endif } if (status != SLJIT_SUCCESS) return status; #else status = sljit_emit_ijump(compiler, SLJIT_CALL2, SLJIT_IMM, xdiv ? SLJIT_FUNC_OFFSET(divide) : SLJIT_FUNC_OFFSET(modulus)); #if BJ_AREG != SLJIT_RETURN_REG status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, SLJIT_RETURN_REG, 0); if (status != SLJIT_SUCCESS) return status; #endif #endif return status; } /* * Return true if pc is a "read from packet" instruction. * If length is not NULL and return value is true, *length will * be set to a safe length required to read a packet. */ static bool read_pkt_insn(const struct bpf_insn *pc, bpfjit_abc_length_t *length) { bool rv; bpfjit_abc_length_t width = 0; /* XXXuninit */ switch (BPF_CLASS(pc->code)) { default: rv = false; break; case BPF_LD: rv = BPF_MODE(pc->code) == BPF_ABS || BPF_MODE(pc->code) == BPF_IND; if (rv) { width = read_width(pc); rv = (width != 0); } break; case BPF_LDX: rv = BPF_MODE(pc->code) == BPF_MSH && BPF_SIZE(pc->code) == BPF_B; width = 1; break; } if (rv && length != NULL) { /* * Values greater than UINT32_MAX will generate * unconditional "return 0". */ *length = (uint32_t)pc->k + width; } return rv; } static void optimize_init(struct bpfjit_insn_data *insn_dat, size_t insn_count) { size_t i; for (i = 0; i < insn_count; i++) { SLIST_INIT(&insn_dat[i].bjumps); insn_dat[i].invalid = BJ_INIT_NOBITS; } } /* * The function divides instructions into blocks. Destination of a jump * instruction starts a new block. BPF_RET and BPF_JMP instructions * terminate a block. Blocks are linear, that is, there are no jumps out * from the middle of a block and there are no jumps in to the middle of * a block. * * The function also sets bits in *initmask for memwords that * need to be initialized to zero. Note that this set should be empty * for any valid kernel filter program. */ static bool optimize_pass1(const bpf_ctx_t *bc, const struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, size_t insn_count, bpf_memword_init_t *initmask, bpfjit_hint_t *hints) { struct bpfjit_jump *jtf; size_t i; uint32_t jt, jf; bpfjit_abc_length_t length; bpf_memword_init_t invalid; /* borrowed from bpf_filter() */ bool unreachable; const size_t memwords = GET_MEMWORDS(bc); *hints = 0; *initmask = BJ_INIT_NOBITS; unreachable = false; invalid = ~BJ_INIT_NOBITS; for (i = 0; i < insn_count; i++) { if (!SLIST_EMPTY(&insn_dat[i].bjumps)) unreachable = false; insn_dat[i].unreachable = unreachable; if (unreachable) continue; invalid |= insn_dat[i].invalid; if (read_pkt_insn(&insns[i], &length) && length > UINT32_MAX) unreachable = true; switch (BPF_CLASS(insns[i].code)) { case BPF_RET: if (BPF_RVAL(insns[i].code) == BPF_A) *initmask |= invalid & BJ_INIT_ABIT; unreachable = true; continue; case BPF_LD: if (BPF_MODE(insns[i].code) == BPF_ABS) *hints |= BJ_HINT_ABS; if (BPF_MODE(insns[i].code) == BPF_IND) { *hints |= BJ_HINT_IND | BJ_HINT_XREG; *initmask |= invalid & BJ_INIT_XBIT; } if (BPF_MODE(insns[i].code) == BPF_MEM && (uint32_t)insns[i].k < memwords) { *initmask |= invalid & BJ_INIT_MBIT(insns[i].k); } invalid &= ~BJ_INIT_ABIT; continue; case BPF_LDX: *hints |= BJ_HINT_XREG | BJ_HINT_LDX; if (BPF_MODE(insns[i].code) == BPF_MEM && (uint32_t)insns[i].k < memwords) { *initmask |= invalid & BJ_INIT_MBIT(insns[i].k); } if (BPF_MODE(insns[i].code) == BPF_MSH && BPF_SIZE(insns[i].code) == BPF_B) { *hints |= BJ_HINT_MSH; } invalid &= ~BJ_INIT_XBIT; continue; case BPF_ST: *initmask |= invalid & BJ_INIT_ABIT; if ((uint32_t)insns[i].k < memwords) invalid &= ~BJ_INIT_MBIT(insns[i].k); continue; case BPF_STX: *hints |= BJ_HINT_XREG; *initmask |= invalid & BJ_INIT_XBIT; if ((uint32_t)insns[i].k < memwords) invalid &= ~BJ_INIT_MBIT(insns[i].k); continue; case BPF_ALU: *initmask |= invalid & BJ_INIT_ABIT; if (insns[i].code != (BPF_ALU|BPF_NEG) && BPF_SRC(insns[i].code) == BPF_X) { *hints |= BJ_HINT_XREG; *initmask |= invalid & BJ_INIT_XBIT; } invalid &= ~BJ_INIT_ABIT; continue; case BPF_MISC: switch (BPF_MISCOP(insns[i].code)) { case BPF_TAX: // X <- A *hints |= BJ_HINT_XREG; *initmask |= invalid & BJ_INIT_ABIT; invalid &= ~BJ_INIT_XBIT; continue; case BPF_TXA: // A <- X *hints |= BJ_HINT_XREG; *initmask |= invalid & BJ_INIT_XBIT; invalid &= ~BJ_INIT_ABIT; continue; case BPF_COPX: *hints |= BJ_HINT_XREG | BJ_HINT_COPX; /* FALLTHROUGH */ case BPF_COP: *hints |= BJ_HINT_COP; *initmask |= invalid & BJ_INIT_ABIT; invalid &= ~BJ_INIT_ABIT; continue; } continue; case BPF_JMP: /* Initialize abc_length for ABC pass. */ insn_dat[i].u.jdata.abc_length = MAX_ABC_LENGTH; *initmask |= invalid & BJ_INIT_ABIT; if (BPF_SRC(insns[i].code) == BPF_X) { *hints |= BJ_HINT_XREG; *initmask |= invalid & BJ_INIT_XBIT; } if (BPF_OP(insns[i].code) == BPF_JA) { jt = jf = insns[i].k; } else { jt = insns[i].jt; jf = insns[i].jf; } if (jt >= insn_count - (i + 1) || jf >= insn_count - (i + 1)) { return false; } if (jt > 0 && jf > 0) unreachable = true; jt += i + 1; jf += i + 1; jtf = insn_dat[i].u.jdata.jtf; jtf[0].jdata = &insn_dat[i].u.jdata; SLIST_INSERT_HEAD(&insn_dat[jt].bjumps, &jtf[0], entries); if (jf != jt) { jtf[1].jdata = &insn_dat[i].u.jdata; SLIST_INSERT_HEAD(&insn_dat[jf].bjumps, &jtf[1], entries); } insn_dat[jf].invalid |= invalid; insn_dat[jt].invalid |= invalid; invalid = 0; continue; } } return true; } /* * Array Bounds Check Elimination (ABC) pass. */ static void optimize_pass2(const bpf_ctx_t *bc, const struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, size_t insn_count) { struct bpfjit_jump *jmp; const struct bpf_insn *pc; struct bpfjit_insn_data *pd; size_t i; bpfjit_abc_length_t length, abc_length = 0; const size_t extwords = GET_EXTWORDS(bc); for (i = insn_count; i != 0; i--) { pc = &insns[i-1]; pd = &insn_dat[i-1]; if (pd->unreachable) continue; switch (BPF_CLASS(pc->code)) { case BPF_RET: /* * It's quite common for bpf programs to * check packet bytes in increasing order * and return zero if bytes don't match * specified critetion. Such programs disable * ABC optimization completely because for * every jump there is a branch with no read * instruction. * With no side effects, BPF_STMT(BPF_RET+BPF_K, 0) * is indistinguishable from out-of-bound load. * Therefore, abc_length can be set to * MAX_ABC_LENGTH and enable ABC for many * bpf programs. * If this optimization encounters any * instruction with a side effect, it will * reset abc_length. */ if (BPF_RVAL(pc->code) == BPF_K && pc->k == 0) abc_length = MAX_ABC_LENGTH; else abc_length = 0; break; case BPF_MISC: if (BPF_MISCOP(pc->code) == BPF_COP || BPF_MISCOP(pc->code) == BPF_COPX) { /* COP instructions can have side effects. */ abc_length = 0; } break; case BPF_ST: case BPF_STX: if (extwords != 0) { /* Write to memory is visible after a call. */ abc_length = 0; } break; case BPF_JMP: abc_length = pd->u.jdata.abc_length; break; default: if (read_pkt_insn(pc, &length)) { if (abc_length < length) abc_length = length; pd->u.rdata.abc_length = abc_length; } break; } SLIST_FOREACH(jmp, &pd->bjumps, entries) { if (jmp->jdata->abc_length > abc_length) jmp->jdata->abc_length = abc_length; } } } static void optimize_pass3(const struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, size_t insn_count) { struct bpfjit_jump *jmp; size_t i; bpfjit_abc_length_t checked_length = 0; for (i = 0; i < insn_count; i++) { if (insn_dat[i].unreachable) continue; SLIST_FOREACH(jmp, &insn_dat[i].bjumps, entries) { if (jmp->jdata->checked_length < checked_length) checked_length = jmp->jdata->checked_length; } if (BPF_CLASS(insns[i].code) == BPF_JMP) { insn_dat[i].u.jdata.checked_length = checked_length; } else if (read_pkt_insn(&insns[i], NULL)) { struct bpfjit_read_pkt_data *rdata = &insn_dat[i].u.rdata; rdata->check_length = 0; if (checked_length < rdata->abc_length) { checked_length = rdata->abc_length; rdata->check_length = checked_length; } } } } static bool optimize(const bpf_ctx_t *bc, const struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, size_t insn_count, bpf_memword_init_t *initmask, bpfjit_hint_t *hints) { optimize_init(insn_dat, insn_count); if (!optimize_pass1(bc, insns, insn_dat, insn_count, initmask, hints)) return false; optimize_pass2(bc, insns, insn_dat, insn_count); optimize_pass3(insns, insn_dat, insn_count); return true; } /* * Convert BPF_ALU operations except BPF_NEG and BPF_DIV to sljit operation. */ static bool alu_to_op(const struct bpf_insn *pc, int *res) { const uint32_t k = pc->k; /* * Note: all supported 64bit arches have 32bit multiply * instruction so SLJIT_I32_OP doesn't have any overhead. */ switch (BPF_OP(pc->code)) { case BPF_ADD: *res = SLJIT_ADD; return true; case BPF_SUB: *res = SLJIT_SUB; return true; case BPF_MUL: *res = SLJIT_MUL|SLJIT_I32_OP; return true; case BPF_OR: *res = SLJIT_OR; return true; case BPF_XOR: *res = SLJIT_XOR; return true; case BPF_AND: *res = SLJIT_AND; return true; case BPF_LSH: *res = SLJIT_SHL; return k < 32; case BPF_RSH: *res = SLJIT_LSHR|SLJIT_I32_OP; return k < 32; default: return false; } } /* * Convert BPF_JMP operations except BPF_JA to sljit condition. */ static bool jmp_to_cond(const struct bpf_insn *pc, bool negate, int *res) { /* * Note: all supported 64bit arches have 32bit comparison * instructions so SLJIT_I32_OP doesn't have any overhead. */ *res = SLJIT_I32_OP; switch (BPF_OP(pc->code)) { case BPF_JGT: *res |= negate ? SLJIT_LESS_EQUAL : SLJIT_GREATER; return true; case BPF_JGE: *res |= negate ? SLJIT_LESS : SLJIT_GREATER_EQUAL; return true; case BPF_JEQ: *res |= negate ? SLJIT_NOT_EQUAL : SLJIT_EQUAL; return true; case BPF_JSET: *res |= negate ? SLJIT_EQUAL : SLJIT_NOT_EQUAL; return true; default: return false; } } /* * Convert BPF_K and BPF_X to sljit register. */ static int kx_to_reg(const struct bpf_insn *pc) { switch (BPF_SRC(pc->code)) { case BPF_K: return SLJIT_IMM; case BPF_X: return BJ_XREG; default: BJ_ASSERT(false); return 0; } } static sljit_sw kx_to_reg_arg(const struct bpf_insn *pc) { switch (BPF_SRC(pc->code)) { case BPF_K: return (uint32_t)pc->k; /* SLJIT_IMM, pc->k, */ case BPF_X: return 0; /* BJ_XREG, 0, */ default: BJ_ASSERT(false); return 0; } } static bool generate_insn_code(struct sljit_compiler *compiler, bpfjit_hint_t hints, const bpf_ctx_t *bc, const struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, size_t insn_count) { /* a list of jumps to out-of-bound return from a generated function */ struct sljit_jump **ret0; size_t ret0_size, ret0_maxsize; struct sljit_jump *jump; struct sljit_label *label; const struct bpf_insn *pc; struct bpfjit_jump *bjump, *jtf; struct sljit_jump *to_mchain_jump; size_t i; unsigned int rval, mode, src, op; int branching, negate; int status, cond, op2; uint32_t jt, jf; bool unconditional_ret; bool rv; const size_t extwords = GET_EXTWORDS(bc); const size_t memwords = GET_MEMWORDS(bc); ret0 = NULL; rv = false; ret0_size = 0; ret0_maxsize = 64; ret0 = BJ_ALLOC(ret0_maxsize * sizeof(ret0[0])); if (ret0 == NULL) goto fail; /* reset sjump members of jdata */ for (i = 0; i < insn_count; i++) { if (insn_dat[i].unreachable || BPF_CLASS(insns[i].code) != BPF_JMP) { continue; } jtf = insn_dat[i].u.jdata.jtf; jtf[0].sjump = jtf[1].sjump = NULL; } /* main loop */ for (i = 0; i < insn_count; i++) { if (insn_dat[i].unreachable) continue; /* * Resolve jumps to the current insn. */ label = NULL; SLIST_FOREACH(bjump, &insn_dat[i].bjumps, entries) { if (bjump->sjump != NULL) { if (label == NULL) label = sljit_emit_label(compiler); if (label == NULL) goto fail; sljit_set_label(bjump->sjump, label); } } to_mchain_jump = NULL; unconditional_ret = false; if (read_pkt_insn(&insns[i], NULL)) { if (insn_dat[i].u.rdata.check_length > UINT32_MAX) { /* Jump to "return 0" unconditionally. */ unconditional_ret = true; jump = sljit_emit_jump(compiler, SLJIT_JUMP); if (jump == NULL) goto fail; if (!append_jump(jump, &ret0, &ret0_size, &ret0_maxsize)) goto fail; } else if (insn_dat[i].u.rdata.check_length > 0) { /* if (buflen < check_length) return 0; */ jump = sljit_emit_cmp(compiler, SLJIT_LESS, BJ_BUFLEN, 0, SLJIT_IMM, insn_dat[i].u.rdata.check_length); if (jump == NULL) goto fail; #ifdef _KERNEL to_mchain_jump = jump; #else if (!append_jump(jump, &ret0, &ret0_size, &ret0_maxsize)) goto fail; #endif } } pc = &insns[i]; switch (BPF_CLASS(pc->code)) { default: goto fail; case BPF_LD: /* BPF_LD+BPF_IMM A <- k */ if (pc->code == (BPF_LD|BPF_IMM)) { status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, SLJIT_IMM, (uint32_t)pc->k); if (status != SLJIT_SUCCESS) goto fail; continue; } /* BPF_LD+BPF_MEM A <- M[k] */ if (pc->code == (BPF_LD|BPF_MEM)) { if ((uint32_t)pc->k >= memwords) goto fail; status = emit_memload(compiler, BJ_AREG, pc->k, extwords); if (status != SLJIT_SUCCESS) goto fail; continue; } /* BPF_LD+BPF_W+BPF_LEN A <- len */ if (pc->code == (BPF_LD|BPF_W|BPF_LEN)) { status = sljit_emit_op1(compiler, SLJIT_MOV, /* size_t source */ BJ_AREG, 0, SLJIT_MEM1(BJ_ARGS), offsetof(struct bpf_args, wirelen)); if (status != SLJIT_SUCCESS) goto fail; continue; } mode = BPF_MODE(pc->code); if (mode != BPF_ABS && mode != BPF_IND) goto fail; if (unconditional_ret) continue; status = emit_pkt_read(compiler, hints, pc, to_mchain_jump, &ret0, &ret0_size, &ret0_maxsize); if (status != SLJIT_SUCCESS) goto fail; continue; case BPF_LDX: mode = BPF_MODE(pc->code); /* BPF_LDX+BPF_W+BPF_IMM X <- k */ if (mode == BPF_IMM) { if (BPF_SIZE(pc->code) != BPF_W) goto fail; status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_XREG, 0, SLJIT_IMM, (uint32_t)pc->k); if (status != SLJIT_SUCCESS) goto fail; continue; } /* BPF_LDX+BPF_W+BPF_LEN X <- len */ if (mode == BPF_LEN) { if (BPF_SIZE(pc->code) != BPF_W) goto fail; status = sljit_emit_op1(compiler, SLJIT_MOV, /* size_t source */ BJ_XREG, 0, SLJIT_MEM1(BJ_ARGS), offsetof(struct bpf_args, wirelen)); if (status != SLJIT_SUCCESS) goto fail; continue; } /* BPF_LDX+BPF_W+BPF_MEM X <- M[k] */ if (mode == BPF_MEM) { if (BPF_SIZE(pc->code) != BPF_W) goto fail; if ((uint32_t)pc->k >= memwords) goto fail; status = emit_memload(compiler, BJ_XREG, pc->k, extwords); if (status != SLJIT_SUCCESS) goto fail; continue; } /* BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) */ if (mode != BPF_MSH || BPF_SIZE(pc->code) != BPF_B) goto fail; if (unconditional_ret) continue; status = emit_msh(compiler, hints, pc, to_mchain_jump, &ret0, &ret0_size, &ret0_maxsize); if (status != SLJIT_SUCCESS) goto fail; continue; case BPF_ST: if (pc->code != BPF_ST || (uint32_t)pc->k >= memwords) { goto fail; } status = emit_memstore(compiler, BJ_AREG, pc->k, extwords); if (status != SLJIT_SUCCESS) goto fail; continue; case BPF_STX: if (pc->code != BPF_STX || (uint32_t)pc->k >= memwords) { goto fail; } status = emit_memstore(compiler, BJ_XREG, pc->k, extwords); if (status != SLJIT_SUCCESS) goto fail; continue; case BPF_ALU: if (pc->code == (BPF_ALU|BPF_NEG)) { status = sljit_emit_op1(compiler, SLJIT_NEG, BJ_AREG, 0, BJ_AREG, 0); if (status != SLJIT_SUCCESS) goto fail; continue; } op = BPF_OP(pc->code); if (op != BPF_DIV && op != BPF_MOD) { if (!alu_to_op(pc, &op2)) goto fail; status = sljit_emit_op2(compiler, op2, BJ_AREG, 0, BJ_AREG, 0, kx_to_reg(pc), kx_to_reg_arg(pc)); if (status != SLJIT_SUCCESS) goto fail; continue; } /* BPF_DIV/BPF_MOD */ src = BPF_SRC(pc->code); if (src != BPF_X && src != BPF_K) goto fail; /* division by zero? */ if (src == BPF_X) { jump = sljit_emit_cmp(compiler, SLJIT_EQUAL|SLJIT_I32_OP, BJ_XREG, 0, SLJIT_IMM, 0); if (jump == NULL) goto fail; if (!append_jump(jump, &ret0, &ret0_size, &ret0_maxsize)) goto fail; } else if (pc->k == 0) { jump = sljit_emit_jump(compiler, SLJIT_JUMP); if (jump == NULL) goto fail; if (!append_jump(jump, &ret0, &ret0_size, &ret0_maxsize)) goto fail; } if (src == BPF_X) { status = emit_moddiv(compiler, pc); if (status != SLJIT_SUCCESS) goto fail; } else if (pc->k != 0) { if (pc->k & (pc->k - 1)) { status = emit_moddiv(compiler, pc); } else { status = emit_pow2_moddiv(compiler, pc); } if (status != SLJIT_SUCCESS) goto fail; } continue; case BPF_JMP: op = BPF_OP(pc->code); if (op == BPF_JA) { jt = jf = pc->k; } else { jt = pc->jt; jf = pc->jf; } negate = (jt == 0) ? 1 : 0; branching = (jt == jf) ? 0 : 1; jtf = insn_dat[i].u.jdata.jtf; if (branching) { if (op != BPF_JSET) { if (!jmp_to_cond(pc, negate, &cond)) goto fail; jump = sljit_emit_cmp(compiler, cond, BJ_AREG, 0, kx_to_reg(pc), kx_to_reg_arg(pc)); } else { status = sljit_emit_op2(compiler, SLJIT_AND, BJ_TMP1REG, 0, BJ_AREG, 0, kx_to_reg(pc), kx_to_reg_arg(pc)); if (status != SLJIT_SUCCESS) goto fail; if (!jmp_to_cond(pc, negate, &cond)) goto fail; jump = sljit_emit_cmp(compiler, cond, BJ_TMP1REG, 0, SLJIT_IMM, 0); } if (jump == NULL) goto fail; BJ_ASSERT(jtf[negate].sjump == NULL); jtf[negate].sjump = jump; } if (!branching || (jt != 0 && jf != 0)) { jump = sljit_emit_jump(compiler, SLJIT_JUMP); if (jump == NULL) goto fail; BJ_ASSERT(jtf[branching].sjump == NULL); jtf[branching].sjump = jump; } continue; case BPF_RET: rval = BPF_RVAL(pc->code); if (rval == BPF_X) goto fail; /* BPF_RET+BPF_K accept k bytes */ if (rval == BPF_K) { status = sljit_emit_return(compiler, SLJIT_MOV_U32, SLJIT_IMM, (uint32_t)pc->k); if (status != SLJIT_SUCCESS) goto fail; } /* BPF_RET+BPF_A accept A bytes */ if (rval == BPF_A) { status = sljit_emit_return(compiler, SLJIT_MOV_U32, BJ_AREG, 0); if (status != SLJIT_SUCCESS) goto fail; } continue; case BPF_MISC: switch (BPF_MISCOP(pc->code)) { case BPF_TAX: status = sljit_emit_op1(compiler, SLJIT_MOV_U32, BJ_XREG, 0, BJ_AREG, 0); if (status != SLJIT_SUCCESS) goto fail; continue; case BPF_TXA: status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, BJ_XREG, 0); if (status != SLJIT_SUCCESS) goto fail; continue; case BPF_COP: case BPF_COPX: if (bc == NULL || bc->copfuncs == NULL) goto fail; if (BPF_MISCOP(pc->code) == BPF_COP && (uint32_t)pc->k >= bc->nfuncs) { goto fail; } status = emit_cop(compiler, hints, bc, pc, &ret0, &ret0_size, &ret0_maxsize); if (status != SLJIT_SUCCESS) goto fail; continue; } goto fail; } /* switch */ } /* main loop */ BJ_ASSERT(ret0_size <= ret0_maxsize); if (ret0_size > 0) { label = sljit_emit_label(compiler); if (label == NULL) goto fail; for (i = 0; i < ret0_size; i++) sljit_set_label(ret0[i], label); } status = sljit_emit_return(compiler, SLJIT_MOV_U32, SLJIT_IMM, 0); if (status != SLJIT_SUCCESS) goto fail; rv = true; fail: if (ret0 != NULL) BJ_FREE(ret0, ret0_maxsize * sizeof(ret0[0])); return rv; } bpfjit_func_t bpfjit_generate_code(const bpf_ctx_t *bc, const struct bpf_insn *insns, size_t insn_count) { void *rv; struct sljit_compiler *compiler; size_t i; int status; /* optimization related */ bpf_memword_init_t initmask; bpfjit_hint_t hints; /* memory store location for initial zero initialization */ sljit_s32 mem_reg; sljit_sw mem_off; struct bpfjit_insn_data *insn_dat; const size_t extwords = GET_EXTWORDS(bc); const size_t memwords = GET_MEMWORDS(bc); const bpf_memword_init_t preinited = extwords ? bc->preinited : 0; rv = NULL; compiler = NULL; insn_dat = NULL; if (memwords > MAX_MEMWORDS) goto fail; if (insn_count == 0 || insn_count > SIZE_MAX / sizeof(insn_dat[0])) goto fail; insn_dat = BJ_ALLOC(insn_count * sizeof(insn_dat[0])); if (insn_dat == NULL) goto fail; if (!optimize(bc, insns, insn_dat, insn_count, &initmask, &hints)) goto fail; compiler = sljit_create_compiler(NULL); if (compiler == NULL) goto fail; #if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE sljit_compiler_verbose(compiler, stderr); #endif status = sljit_emit_enter(compiler, 0, 2, nscratches(hints), NSAVEDS, 0, 0, sizeof(struct bpfjit_stack)); if (status != SLJIT_SUCCESS) goto fail; if (hints & BJ_HINT_COP) { /* save ctx argument */ status = sljit_emit_op1(compiler, SLJIT_MOV_P, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, ctx), BJ_CTX_ARG, 0); if (status != SLJIT_SUCCESS) goto fail; } if (extwords == 0) { mem_reg = SLJIT_MEM1(SLJIT_SP); mem_off = offsetof(struct bpfjit_stack, mem); } else { /* copy "mem" argument from bpf_args to bpfjit_stack */ status = sljit_emit_op1(compiler, SLJIT_MOV_P, BJ_TMP1REG, 0, SLJIT_MEM1(BJ_ARGS), offsetof(struct bpf_args, mem)); if (status != SLJIT_SUCCESS) goto fail; status = sljit_emit_op1(compiler, SLJIT_MOV_P, SLJIT_MEM1(SLJIT_SP), offsetof(struct bpfjit_stack, extmem), BJ_TMP1REG, 0); if (status != SLJIT_SUCCESS) goto fail; mem_reg = SLJIT_MEM1(BJ_TMP1REG); mem_off = 0; } /* * Exclude pre-initialised external memory words but keep * initialization statuses of A and X registers in case * bc->preinited wrongly sets those two bits. */ initmask &= ~preinited | BJ_INIT_ABIT | BJ_INIT_XBIT; #if defined(_KERNEL) /* bpf_filter() checks initialization of memwords. */ BJ_ASSERT((initmask & (BJ_INIT_MBIT(memwords) - 1)) == 0); #endif for (i = 0; i < memwords; i++) { if (initmask & BJ_INIT_MBIT(i)) { /* M[i] = 0; */ status = sljit_emit_op1(compiler, SLJIT_MOV_U32, mem_reg, mem_off + i * sizeof(uint32_t), SLJIT_IMM, 0); if (status != SLJIT_SUCCESS) goto fail; } } if (initmask & BJ_INIT_ABIT) { /* A = 0; */ status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_AREG, 0, SLJIT_IMM, 0); if (status != SLJIT_SUCCESS) goto fail; } if (initmask & BJ_INIT_XBIT) { /* X = 0; */ status = sljit_emit_op1(compiler, SLJIT_MOV, BJ_XREG, 0, SLJIT_IMM, 0); if (status != SLJIT_SUCCESS) goto fail; } status = load_buf_buflen(compiler); if (status != SLJIT_SUCCESS) goto fail; if (!generate_insn_code(compiler, hints, bc, insns, insn_dat, insn_count)) { goto fail; } rv = sljit_generate_code(compiler); fail: if (compiler != NULL) sljit_free_compiler(compiler); if (insn_dat != NULL) BJ_FREE(insn_dat, insn_count * sizeof(insn_dat[0])); return (bpfjit_func_t)rv; } void bpfjit_free_code(bpfjit_func_t code) { sljit_free_code((void *)code); }