On 25/03/18 12:30PM, David Faust wrote:
>
>
> On 3/18/25 12:24, Anton Protopopov wrote:
> > On 25/03/18 12:00PM, David Faust wrote:
> >>
> >>
> >> On 3/18/25 07:33, Anton Protopopov wrote:
> >>> Add support for a new version of JA instruction, a static branch JA. Such
> >>> instructions may either jump to the specified offset or act as nops. To
> >>> distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
> >>> should be set for the SRC register.
> >>>
> >>> By default on program load such instructions are jitted as a normal JA.
> >>> However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
> >>> then the instruction is jitted to a NOP.
> >>
> >> [adding context from the cover letter:]
> >>> 3) Patch 4 adds support for a new BPF instruction. It looks
> >>> reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
> >>> may_goto. Reasons: a follow up will add support for
> >>> BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
> >>> Then another follow up will add support CALL|BPF_X, for which there's
> >>> no corresponding magic instruction (to be discussed at the following
> >>> LSF/MM/BPF).
> >>
> >> I don't understand the reasoning to extend JA rather than JCOND.
> >>
> >> Couldn't the followup for indirect jumps also use JCOND, with BPF_SRC_X
> >> set to distinguish from the absolute jumps here?
> >>
> >> If the problem is that the indirect version will need both reigster
> >> fields and JCOND is using SRC to encode the operation (0 for may_goto),
> >> aren't you going to have exactly the same problem with BPF_JA|BPF_X and
> >> the BPF_STATIC_BRANCH flag? Or is the plan to stick the flag in another
> >> different field of BPF_JA|BPF_X instruction...?
> >>
> >> It seems like the general problem here that there is a growing class of
> >> statically-decided-post-compiler conditional jumps, but no more free
> >> insn class bits to use. I suggest we try hard to encapsulate them as
> >> much as possible under JCOND rather than (ab)using different fields of
> >> different JMP insns to encode the 'maybe' versions on a case-by-case
> >> basis.
> >>
> >> To put it another way, why not make BPF_JMP|BPF_JCOND its own "class"
> >> of insn and encode all of these conditional pseudo-jumps under it?
> >
> > I agree that the "magic jump" (BPF_STATIC_BRANCH) is, maybe, better to go with
> > BPF_JMP|BPF_JCOND, as it emphasizes that the instruction is a special one.
> >
> > However, for indirect jumps the BPF_JMP|BPF_JA|BPF_X looks more natural.
>
> Ah, maybe I misunderstood the context; will these BPF_JMP|BPF_JA|BPF_X indirect
> jumps exclusively be "real" or was the intent that they also have the "maybe"
> variant (could be jitted to no-op)? I was thinking the latter.
>
> For the always-real version I agree BPF_JA|BPF_X makes total sense.
> If there is a "maybe" variant that could be jitted to no-op then that should
> fall under JCOND.
Yes, those are real, no patching: goto rX (where rX is properly loaded
from an instruction set).
> >
> >> As far as I am aware (I may be out of date), the only JCOND insn
> >> currently is may_goto (src_reg == 0), and may_goto only uses the 16-bit
> >> offset. That seems to leave a lot of room (and bits) to design a whole
> >> sub-class of JMP|JCOND instructions in a backwards compatible way...
> >>
> >>>
> >>> In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
> >>> instructions will be added:
> >>>
> >>> asm volatile goto ("nop_or_gotol %l[label]" :::: label);
> >>>
> >>> will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and
> >>>
> >>> asm volatile goto ("gotol_or_nop %l[label]" :::: label);
> >>>
> >>> will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
> >>> The reason for adding two instructions is that both are required to implement
> >>> static keys functionality for BPF, namely, to distinguish between likely and
> >>> unlikely branches.
> >>>
> >>> The verifier logic is extended to check both possible paths: jump and nop.
> >>>
> >>> Signed-off-by: Anton Protopopov <aspsk@xxxxxxxxxxxxx>
> >>> ---
> >>> arch/x86/net/bpf_jit_comp.c | 19 +++++++++++++--
> >>> include/uapi/linux/bpf.h | 10 ++++++++
> >>> kernel/bpf/verifier.c | 43 +++++++++++++++++++++++++++-------
> >>> tools/include/uapi/linux/bpf.h | 10 ++++++++
> >>> 4 files changed, 71 insertions(+), 11 deletions(-)
> >>>
> >>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> >>> index d3491cc0898b..5856ac1aab80 100644
> >>> --- a/arch/x86/net/bpf_jit_comp.c
> >>> +++ b/arch/x86/net/bpf_jit_comp.c
> >>> @@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
> >>> *pprog = prog;
> >>> }
> >>>
> >>> +static bool is_static_ja_nop(const struct bpf_insn *insn)
> >>> +{
> >>> + u8 code = insn->code;
> >>> +
> >>> + return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
> >>> + (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
> >>> + (insn->src_reg & BPF_STATIC_BRANCH_NOP);
> >>> +}
> >>> +
> >>> #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
> >>>
> >>> #define __LOAD_TCC_PTR(off) \
> >>> @@ -2519,9 +2528,15 @@ st: if (is_imm8(insn->off))
> >>> }
> >>> emit_nops(&prog, INSN_SZ_DIFF - 2);
> >>> }
> >>> - EMIT2(0xEB, jmp_offset);
> >>> + if (is_static_ja_nop(insn))
> >>> + emit_nops(&prog, 2);
> >>> + else
> >>> + EMIT2(0xEB, jmp_offset);
> >>> } else if (is_simm32(jmp_offset)) {
> >>> - EMIT1_off32(0xE9, jmp_offset);
> >>> + if (is_static_ja_nop(insn))
> >>> + emit_nops(&prog, 5);
> >>> + else
> >>> + EMIT1_off32(0xE9, jmp_offset);
> >>> } else {
> >>> pr_err("jmp gen bug %llx\n", jmp_offset);
> >>> return -EFAULT;
> >>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> >>> index b8e588ed6406..57e0fd636a27 100644
> >>> --- a/include/uapi/linux/bpf.h
> >>> +++ b/include/uapi/linux/bpf.h
> >>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
> >>> };
> >>> };
> >>>
> >>> +/* Flags for JA insn, passed in SRC_REG */
> >>> +enum {
> >>> + BPF_STATIC_BRANCH_JA = 1 << 0,
> >>> + BPF_STATIC_BRANCH_NOP = 1 << 1,
> >>> +};
> >>> +
> >>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> >>> + BPF_STATIC_BRANCH_NOP)
> >>> +
> >>> +
> >>> #define BPF_OBJ_NAME_LEN 16U
> >>>
> >>> union bpf_attr {
> >>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >>> index 6554f7aea0d8..0860ef57d5af 100644
> >>> --- a/kernel/bpf/verifier.c
> >>> +++ b/kernel/bpf/verifier.c
> >>> @@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
> >>> else
> >>> off = insn->imm;
> >>>
> >>> - /* unconditional jump with single edge */
> >>> - ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> >>> - if (ret)
> >>> - return ret;
> >>> + if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> >>> + /* static branch - jump with two edges */
> >>> + mark_prune_point(env, t);
> >>>
> >>> - mark_prune_point(env, t + off + 1);
> >>> - mark_jmp_point(env, t + off + 1);
> >>> + ret = push_insn(t, t + 1, FALLTHROUGH, env);
> >>> + if (ret)
> >>> + return ret;
> >>> +
> >>> + ret = push_insn(t, t + off + 1, BRANCH, env);
> >>> + } else {
> >>> + /* unconditional jump with single edge */
> >>> + ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> >>> + if (ret)
> >>> + return ret;
> >>>
> >>> + mark_prune_point(env, t + off + 1);
> >>> + mark_jmp_point(env, t + off + 1);
> >>> + }
> >>> return ret;
> >>>
> >>> default:
> >>> @@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
> >>>
> >>> mark_reg_scratched(env, BPF_REG_0);
> >>> } else if (opcode == BPF_JA) {
> >>> + struct bpf_verifier_state *other_branch;
> >>> + u32 jmp_offset;
> >>> +
> >>> if (BPF_SRC(insn->code) != BPF_K ||
> >>> - insn->src_reg != BPF_REG_0 ||
> >>> + (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
> >>> insn->dst_reg != BPF_REG_0 ||
> >>> (class == BPF_JMP && insn->imm != 0) ||
> >>> (class == BPF_JMP32 && insn->off != 0)) {
> >>> @@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
> >>> }
> >>>
> >>> if (class == BPF_JMP)
> >>> - env->insn_idx += insn->off + 1;
> >>> + jmp_offset = insn->off + 1;
> >>> else
> >>> - env->insn_idx += insn->imm + 1;
> >>> + jmp_offset = insn->imm + 1;
> >>> +
> >>> + /* Staic branch can either jump to +off or +0 */
> >>> + if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> >>> + other_branch = push_stack(env, env->insn_idx + jmp_offset,
> >>> + env->insn_idx, false);
> >>> + if (!other_branch)
> >>> + return -EFAULT;
> >>> +
> >>> + jmp_offset = 1;
> >>> + }
> >>> +
> >>> + env->insn_idx += jmp_offset;
> >>> continue;
> >>>
> >>> } else if (opcode == BPF_EXIT) {
> >>> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
> >>> index b8e588ed6406..57e0fd636a27 100644
> >>> --- a/tools/include/uapi/linux/bpf.h
> >>> +++ b/tools/include/uapi/linux/bpf.h
> >>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
> >>> };
> >>> };
> >>>
> >>> +/* Flags for JA insn, passed in SRC_REG */
> >>> +enum {
> >>> + BPF_STATIC_BRANCH_JA = 1 << 0,
> >>> + BPF_STATIC_BRANCH_NOP = 1 << 1,
> >>> +};
> >>> +
> >>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> >>> + BPF_STATIC_BRANCH_NOP)
> >>> +
> >>> +
> >>> #define BPF_OBJ_NAME_LEN 16U
> >>>
> >>> union bpf_attr {
> >>
>
