BPF List
 help / color / mirror / Atom feed
* [PATCH bpf-next v2 0/2] propagate nullness information for reg to reg comparisons
@ 2022-11-06 21:49 Eduard Zingerman
  2022-11-06 21:49 ` [PATCH bpf-next v2 1/2] bpf: " Eduard Zingerman
  2022-11-06 21:49 ` [PATCH bpf-next v2 2/2] selftests/bpf: check nullness propagation " Eduard Zingerman
  0 siblings, 2 replies; 3+ messages in thread
From: Eduard Zingerman @ 2022-11-06 21:49 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, kernel-team, yhs, john.fastabend, shung-hsi.yu,
	Eduard Zingerman

This patchset adds ability to propagates nullness information for
branches of register to register equality compare instructions. The
following rules are used:
 - suppose register A maybe null
 - suppose register B is not null
 - for JNE A, B, ... - A is not null in the false branch
 - for JEQ A, B, ... - A is not null in the true branch

E.g. for program like below:

  r6 = skb->sk;
  r7 = sk_fullsock(r6);
  r0 = sk_fullsock(r6);
  if (r0 == 0) return 0;    (a)
  if (r0 != r7) return 0;   (b)
  *r7->type;                (c)
  return 0;

It is safe to dereference r7 at point (c), because of (a) and (b).

The utility of this change came up while working on BPF CLang backend
issue [1]. Specifically, while debugging issue with selftest
`test_sk_lookup.c`. This test has the following structure:

    int access_ctx_sk(struct bpf_sk_lookup *ctx __CTX__)
    {
        struct bpf_sock *sk1 = NULL, *sk2 = NULL;
        ...
        sk1 = bpf_map_lookup_elem(&redir_map, &KEY_SERVER_A);
        if (!sk1)           // (a)
            goto out;
        ...
        if (ctx->sk != sk1) // (b)
            goto out;
        ...
        if (ctx->sk->family != AF_INET ||     // (c)
            ctx->sk->type != SOCK_STREAM ||
            ctx->sk->state != BPF_TCP_LISTEN)
            goto out;
            ...
    }

- at (a) `sk1` is checked to be not null;
- at (b) `ctx->sk` is verified to be equal to `sk1`;
- at (c) `ctx->sk` is accessed w/o nullness check.

Currently Global Value Numbering pass considers expressions `sk1` and
`ctx->sk` to be identical at point (c) and replaces `ctx->sk` with
`sk1` (not expressions themselves but corresponding SSA values).
Since `sk1` is known to be not null after (b) verifier allows
execution of the program.

However, such optimization is not guaranteed to happen. When it does
not happen verifier reports an error.

Changelog:
v1 -> v2:
 - after investigation described in [2] as suggested by John, Daniel
   and Shung-Hsi, function `type_is_pointer` is removed, calls to this
   function are replaced by `__is_pointer_value(false, src_reg)`.
   
RFC -> v1:
 - newly added if block in `check_cond_jmp_op` is moved down to keep
   `make_ptr_not_null_reg` actions together;
 - tests rewritten to have a single `r0 = 0; exit;` block.

[1]   https://reviews.llvm.org/D131633#3722231
[2]   https://lore.kernel.org/bpf/bad8be826d088e0d180232628160bf932006de89.camel@gmail.com/
[v1]  https://lore.kernel.org/bpf/20220826172915.1536914-1-eddyz87@gmail.com/
[RFC] https://lore.kernel.org/bpf/20220822094312.175448-1-eddyz87@gmail.com/

Eduard Zingerman (2):
  bpf: propagate nullness information for reg to reg comparisons
  selftests/bpf: check nullness propagation for reg to reg comparisons

 kernel/bpf/verifier.c                         |  35 +++-
 .../bpf/verifier/jeq_infer_not_null.c         | 166 ++++++++++++++++++
 2 files changed, 199 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/jeq_infer_not_null.c

-- 
2.34.1


^ permalink raw reply	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-11-06 21:50 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2022-11-06 21:49 [PATCH bpf-next v2 0/2] propagate nullness information for reg to reg comparisons Eduard Zingerman
2022-11-06 21:49 ` [PATCH bpf-next v2 1/2] bpf: " Eduard Zingerman
2022-11-06 21:49 ` [PATCH bpf-next v2 2/2] selftests/bpf: check nullness propagation " Eduard Zingerman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox