Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Wed, 20 Jan 2021 12:12:42 -0800
From:   Alexei Starovoitov <alexei.starovoitov@gmail.com>
To:     Brendan Jackman <jackmanb@google.com>
Cc:     bpf@vger.kernel.org, Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        Andrii Nakryiko <andrii.nakryiko@gmail.com>,
        KP Singh <kpsingh@chromium.org>,
        Florent Revest <revest@chromium.org>,
        linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org
Subject: Re: [PATCH bpf-next] bpf: Propagate memory bounds to registers in
 atomics w/ BPF_FETCH
Message-ID: <20210120201242.nm35li5yxvo7ir35@ast-mbp.dhcp.thefacebook.com>
References: <20210118160613.541020-1-jackmanb@google.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20210118160613.541020-1-jackmanb@google.com>
Precedence: bulk

On Mon, Jan 18, 2021 at 04:06:13PM +0000, Brendan Jackman wrote:
> When BPF_FETCH is set, atomic instructions load a value from memory
> into a register. The current verifier code first checks via
> check_mem_access whether we can access the memory, and then checks
> via check_reg_arg whether we can write into the register.
> 
> For loads, check_reg_arg has the side-effect of marking the
> register's value as unkonwn, and check_mem_access has the side effect
> of propagating bounds from memory to the register.
> 
> Therefore with the current order, bounds information is thrown away,
> but by simply reversing the order of check_reg_arg
> vs. check_mem_access, we can instead propagate bounds smartly.

I think such improvement makes sense, but please tweak commit log
to mention that check_mem_access() is doing it only for stack pointers.
Since "propagating from memory" is too generic. Most memory
won't have such propagation.

> A simple test is added with an infinite loop that can only be proved
> unreachable if this propagation is present.
> 
> Note that in the test, the memory value has to be written with two
> instructions:
> 
> 		BPF_MOV64_IMM(BPF_REG_0, 0),
> 		BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8),
> 
> instead of one:
> 
> 		BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
> 
> Because BPF_ST_MEM doesn't seem to set the stack slot type to 0 when
> storing an immediate.

This bit is confusing in the commit log. Pls move it into test itself.

> Signed-off-by: Brendan Jackman <jackmanb@google.com>
> ---
>  kernel/bpf/verifier.c                         | 32 +++++++++++--------
>  .../selftests/bpf/verifier/atomic_bounds.c    | 18 +++++++++++
>  2 files changed, 36 insertions(+), 14 deletions(-)
>  create mode 100644 tools/testing/selftests/bpf/verifier/atomic_bounds.c
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0f82d5d46e2c..0512695c70f4 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3663,9 +3663,26 @@ static int check_atomic(struct bpf_verifier_env *env, int insn_idx, struct bpf_i
>  		return -EACCES;
>  	}
>  
> +	if (insn->imm & BPF_FETCH) {
> +		if (insn->imm == BPF_CMPXCHG)
> +			load_reg = BPF_REG_0;
> +		else
> +			load_reg = insn->src_reg;
> +
> +		/* check and record load of old value */
> +		err = check_reg_arg(env, load_reg, DST_OP);
> +		if (err)
> +			return err;
> +	} else {
> +		/* This instruction accesses a memory location but doesn't
> +		 * actually load it into a register.
> +		 */
> +		load_reg = -1;
> +	}
> +
>  	/* check whether we can read the memory */
>  	err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
> -			       BPF_SIZE(insn->code), BPF_READ, -1, true);
> +			       BPF_SIZE(insn->code), BPF_READ, load_reg, true);
>  	if (err)
>  		return err;
>  
> @@ -3675,19 +3692,6 @@ static int check_atomic(struct bpf_verifier_env *env, int insn_idx, struct bpf_i
>  	if (err)
>  		return err;
>  
> -	if (!(insn->imm & BPF_FETCH))
> -		return 0;
> -
> -	if (insn->imm == BPF_CMPXCHG)
> -		load_reg = BPF_REG_0;
> -	else
> -		load_reg = insn->src_reg;
> -
> -	/* check and record load of old value */
> -	err = check_reg_arg(env, load_reg, DST_OP);
> -	if (err)
> -		return err;
> -
>  	return 0;
>  }
>  
> diff --git a/tools/testing/selftests/bpf/verifier/atomic_bounds.c b/tools/testing/selftests/bpf/verifier/atomic_bounds.c
> new file mode 100644
> index 000000000000..45030165ed63
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/verifier/atomic_bounds.c
> @@ -0,0 +1,18 @@
> +{
> +	"BPF_ATOMIC bounds propagation, mem->reg",
> +	.insns = {
> +		/* a = 0; */
> +		BPF_MOV64_IMM(BPF_REG_0, 0),
> +		BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8),
> +		/* b = atomic_fetch_add(&a, 1); */
> +		BPF_MOV64_IMM(BPF_REG_1, 1),
> +		BPF_ATOMIC_OP(BPF_DW, BPF_ADD | BPF_FETCH, BPF_REG_10, BPF_REG_1, -8),
> +		/* Verifier should be able to tell that this infinite loop isn't reachable. */
> +		/* if (b) while (true) continue; */
> +		BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, -1),
> +		BPF_EXIT_INSN(),

I think it's a bit unrealistic to use atomic_add to increment induction variable,
but I don't mind, since the verifier side is simple.
Could you add a C based test as well?