MIME-Version: 1.0
References: <20211111161452.86864-1-lmb@cloudflare.com>
In-Reply-To: <20211111161452.86864-1-lmb@cloudflare.com>
From:   Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date:   Fri, 12 Nov 2021 17:27:05 -0800
Message-ID: <CAADnVQKWk5VNT9Z_Cy6COO9NMjkUg1p9gYTsPPzH-fi1qCrDiw@mail.gmail.com>
Subject: Re: [PATCH bpf] selftests: bpf: check map in map pruning
To:     Lorenz Bauer <lmb@cloudflare.com>
Cc:     Shuah Khan <shuah@kernel.org>, Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        Andrii Nakryiko <andrii@kernel.org>,
        kernel-team <kernel-team@cloudflare.com>,
        "open list:KERNEL SELFTEST FRAMEWORK" 
        <linux-kselftest@vger.kernel.org>,
        Network Development <netdev@vger.kernel.org>,
        bpf <bpf@vger.kernel.org>, LKML <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Thu, Nov 11, 2021 at 8:16 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> Ensure that two registers with a map_value loaded from a nested
> map are considered equivalent for the purpose of state pruning
> and don't cause the verifier to revisit a pruning point.
>
> This uses a rather crude match on the number of insns visited by
> the verifier, which might change in the future. I've therefore
> tried to keep the code as "unpruneable" as possible by having
> the code paths only converge on the second to last instruction.
>
> Should you require to adjust the test in the future, reducing the
> number of processed instructions should always be safe. Increasing
> them could cause another regression, so proceed with caution.
>
> Suggested-by: Alexei Starovoitov <ast@kernel.org>
> Signed-off-by: Lorenz Bauer <lmb@cloudflare.com>
> Link: https://lore.kernel.org/bpf/CACAyw99hVEJFoiBH_ZGyy=+oO-jyydoz6v1DeKPKs2HVsUH28w@mail.gmail.com/
> ---
>  .../selftests/bpf/verifier/map_in_map.c       | 33 +++++++++++++++++++
>  1 file changed, 33 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/verifier/map_in_map.c b/tools/testing/selftests/bpf/verifier/map_in_map.c
> index 2798927ee9ff..f46c7121e216 100644
> --- a/tools/testing/selftests/bpf/verifier/map_in_map.c
> +++ b/tools/testing/selftests/bpf/verifier/map_in_map.c
> @@ -18,6 +18,39 @@
>         .fixup_map_in_map = { 3 },
>         .result = ACCEPT,
>  },
> +{
> +       "map in map state pruning",
> +       .insns = {
> +       BPF_ST_MEM(0, BPF_REG_10, -4, 0),
> +       BPF_MOV64_REG(BPF_REG_6, BPF_REG_10),
> +       BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, -4),
> +       BPF_MOV64_REG(BPF_REG_2, BPF_REG_6),
> +       BPF_LD_MAP_FD(BPF_REG_1, 0),
> +       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> +       BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
> +       BPF_EXIT_INSN(),
> +       BPF_MOV64_REG(BPF_REG_2, BPF_REG_6),
> +       BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
> +       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> +       BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 11),
> +       BPF_MOV64_REG(BPF_REG_2, BPF_REG_6),
> +       BPF_LD_MAP_FD(BPF_REG_1, 0),
> +       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> +       BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
> +       BPF_EXIT_INSN(),
> +       BPF_MOV64_REG(BPF_REG_2, BPF_REG_6),
> +       BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
> +       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> +       BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
> +       BPF_EXIT_INSN(),
> +       BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, 0),
> +       BPF_EXIT_INSN(),
> +       },
> +       .fixup_map_in_map = { 4, 14 },
> +       .flags = BPF_F_TEST_STATE_FREQ,
> +       .result = VERBOSE_ACCEPT,
> +       .errstr = "processed 25 insns",
> +},

Not sure how you've tested it, but it doesn't work in unpriv:
$ test_verifier 789
#789/u map in map state pruning FAIL
processed 26 insns (limit 1000000) max_states_per_insn 0 total_states
2 peak_states 2 mark_read 1
#789/p map in map state pruning OK

I've added
.prog_type = BPF_PROG_TYPE_XDP,
and force pushed.