Re: [RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[Anton Protopopov <aspsk@isovalent.com>]

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@isovalent.com>
> > ---
> >  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 {
>