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.
> 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 {
>
