This commit patches the BPF bytecode with special instructions to tell the interpreter to check the oracle. These instructions need to be added whenever we saved information on verifier states, so at each pruning point. At the moment, it relies on a special LD_IMM64 instruction with the address to the array map holding the information from the verifier states. This needs to be changed to not expose a new BPF_PSEUDO_MAP_* constant. One option would be to choose something closer to the existing BPF_ST_NOSPEC instruction, which serves a similar internal-only purpose. This patch defines a zero immediate for our LD_IMM64 instruction. The next patch sets the immediate to our map address. Signed-off-by: Paul Chaignon --- include/linux/bpf_verifier.h | 4 ++++ include/uapi/linux/bpf.h | 10 +++++++++ kernel/bpf/disasm.c | 3 ++- kernel/bpf/oracle.c | 36 +++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 4 +++- kernel/bpf/verifier.c | 16 +++++++++++--- tools/bpf/bpftool/xlated_dumper.c | 3 +++ 7 files changed, 71 insertions(+), 5 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index adaeff35aaa6..e4c8457e02c1 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1107,6 +1107,8 @@ int bpf_jmp_offset(struct bpf_insn *insn); struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx); void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask); bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx); +struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off, + const struct bpf_insn *patch, u32 len); int bpf_stack_liveness_init(struct bpf_verifier_env *env); void bpf_stack_liveness_free(struct bpf_verifier_env *env); @@ -1120,5 +1122,7 @@ bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 spi); void bpf_reset_live_stack_callchain(struct bpf_verifier_env *env); int save_state_in_oracle(struct bpf_verifier_env *env, int insn_idx); +struct bpf_prog *patch_oracle_check_insn(struct bpf_verifier_env *env, struct bpf_insn *insn, + int i, int *cnt); #endif /* _LINUX_BPF_VERIFIER_H */ diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index 84ced3ed2d21..ca4827933d26 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -1345,6 +1345,16 @@ enum { #define BPF_PSEUDO_MAP_VALUE 2 #define BPF_PSEUDO_MAP_IDX_VALUE 6 +/* Internal only. + * insn[0].dst_reg: 0 + * insn[0].src_reg: BPF_PSEUDO_MAP_ORACLE + * insn[0].imm: address of oracle state list + * insn[1].imm: address of oracle state list + * insn[0].off: 0 + * insn[1].off: 0 + */ +#define BPF_PSEUDO_MAP_ORACLE 7 + /* insn[0].src_reg: BPF_PSEUDO_BTF_ID * insn[0].imm: kernel btd id of VAR * insn[1].imm: 0 diff --git a/kernel/bpf/disasm.c b/kernel/bpf/disasm.c index f8a3c7eb451e..a591a0bd0284 100644 --- a/kernel/bpf/disasm.c +++ b/kernel/bpf/disasm.c @@ -323,7 +323,8 @@ void print_bpf_insn(const struct bpf_insn_cbs *cbs, */ u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm; bool is_ptr = insn->src_reg == BPF_PSEUDO_MAP_FD || - insn->src_reg == BPF_PSEUDO_MAP_VALUE; + insn->src_reg == BPF_PSEUDO_MAP_VALUE || + insn->src_reg == BPF_PSEUDO_MAP_ORACLE; char tmp[64]; if (is_ptr && !allow_ptr_leaks) diff --git a/kernel/bpf/oracle.c b/kernel/bpf/oracle.c index adbb153aadee..924a86c90b4e 100644 --- a/kernel/bpf/oracle.c +++ b/kernel/bpf/oracle.c @@ -61,3 +61,39 @@ int save_state_in_oracle(struct bpf_verifier_env *env, int insn_idx) return 0; } + +struct bpf_prog *patch_oracle_check_insn(struct bpf_verifier_env *env, struct bpf_insn *insn, + int i, int *cnt) +{ + struct bpf_insn ld_addrs[2] = { + BPF_LD_IMM64_RAW(0, BPF_PSEUDO_MAP_ORACLE, 0), + }; + struct bpf_insn_aux_data *aux = &env->insn_aux_data[i]; + struct list_head *head = aux->oracle_states; + struct bpf_insn *insn_buf = env->insn_buf; + struct bpf_prog *new_prog = env->prog; + int num_oracle_states; + + if (env->subprog_cnt > 1) + /* Skip the oracle if subprogs are used. */ + goto noop; + + num_oracle_states = list_count_nodes(head); + if (!num_oracle_states) + goto noop; + + insn_buf[0] = ld_addrs[0]; + insn_buf[1] = ld_addrs[1]; + insn_buf[2] = *insn; + *cnt = 3; + + new_prog = bpf_patch_insn_data(env, i, insn_buf, *cnt); + if (!new_prog) + return ERR_PTR(-ENOMEM); + + return new_prog; + +noop: + *cnt = 1; + return new_prog; +} diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index 3080cc48bfc3..211912c91652 100644 --- a/kernel/bpf/syscall.c +++ b/kernel/bpf/syscall.c @@ -4863,7 +4863,8 @@ static const struct bpf_map *bpf_map_from_imm(const struct bpf_prog *prog, for (i = 0, *off = 0; i < prog->aux->used_map_cnt; i++) { map = prog->aux->used_maps[i]; if (map == (void *)addr) { - *type = BPF_PSEUDO_MAP_FD; + if (*type != BPF_PSEUDO_MAP_ORACLE) + *type = BPF_PSEUDO_MAP_FD; goto out; } if (!map->ops->map_direct_value_meta) @@ -4925,6 +4926,7 @@ static struct bpf_insn *bpf_insn_prepare_dump(const struct bpf_prog *prog, if (code != (BPF_LD | BPF_IMM | BPF_DW)) continue; + type = insns[i].src_reg; imm = ((u64)insns[i + 1].imm << 32) | (u32)insns[i].imm; map = bpf_map_from_imm(prog, imm, &off, &type); if (map) { diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 2e48e5c9abae..4ca52c6aaa3b 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -21202,7 +21202,7 @@ static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env) for (i = 0; i < insn_cnt; i++, insn++) { if (insn->code != (BPF_LD | BPF_IMM | BPF_DW)) continue; - if (insn->src_reg == BPF_PSEUDO_FUNC) + if (insn->src_reg == BPF_PSEUDO_FUNC || insn->src_reg == BPF_PSEUDO_MAP_ORACLE) continue; insn->src_reg = 0; } @@ -21296,8 +21296,8 @@ static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len) } } -static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off, - const struct bpf_insn *patch, u32 len) +struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off, + const struct bpf_insn *patch, u32 len) { struct bpf_prog *new_prog; struct bpf_insn_aux_data *new_data = NULL; @@ -22639,6 +22639,16 @@ static int do_misc_fixups(struct bpf_verifier_env *env) } for (i = 0; i < insn_cnt;) { + if (is_prune_point(env, i + delta)) { + new_prog = patch_oracle_check_insn(env, insn, i + delta, &cnt); + if (IS_ERR(new_prog)) + return PTR_ERR(new_prog); + + delta += cnt - 1; + env->prog = prog = new_prog; + insn = new_prog->insnsi + i + delta; + } + if (insn->code == (BPF_ALU64 | BPF_MOV | BPF_X) && insn->imm) { if ((insn->off == BPF_ADDR_SPACE_CAST && insn->imm == 1) || (((struct bpf_map *)env->prog->aux->arena)->map_flags & BPF_F_NO_USER_CONV)) { diff --git a/tools/bpf/bpftool/xlated_dumper.c b/tools/bpf/bpftool/xlated_dumper.c index 5e7cb8b36fef..08bcd0c7d72d 100644 --- a/tools/bpf/bpftool/xlated_dumper.c +++ b/tools/bpf/bpftool/xlated_dumper.c @@ -206,6 +206,9 @@ static const char *print_imm(void *private_data, else if (insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) snprintf(dd->scratch_buff, sizeof(dd->scratch_buff), "map[idx:%d]+%d", insn->imm, (insn + 1)->imm); + else if (insn->src_reg == BPF_PSEUDO_MAP_ORACLE) + snprintf(dd->scratch_buff, sizeof(dd->scratch_buff), + "oracle_map[id:%d]", insn->imm); else if (insn->src_reg == BPF_PSEUDO_FUNC) snprintf(dd->scratch_buff, sizeof(dd->scratch_buff), "subprog[%+d]", insn->imm); -- 2.43.0