bpf: Fix register equivalence tracking.
authorAlexei Starovoitov <ast@kernel.org>
Wed, 14 Oct 2020 17:56:08 +0000 (10:56 -0700)
committerDaniel Borkmann <daniel@iogearbox.net>
Thu, 15 Oct 2020 14:05:31 +0000 (16:05 +0200)
commite688c3db7ca69bea1872c5706aec6a7fdf89df17
tree349ebbc1f6d7a6e61e7c56a447ba8c926f811b79
parentccdf7fae3afaeaf0e5dd03311b86ffa56adf85ae
bpf: Fix register equivalence tracking.

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
true or false branch. In the case 'if (reg->id)' check was done on the other
branch the counter part register would have reg->id == 0 when called into
find_equal_scalars(). In such case the helper would incorrectly identify other
registers with id == 0 as equivalent and propagate the state incorrectly.
Fix it by preserving ID across reg_set_min_max().

In other words any kind of comparison operator on the scalar register
should preserve its ID to recognize:

r1 = r2
if (r1 == 20) {
  #1 here both r1 and r2 == 20
} else if (r2 < 20) {
  #2 here both r1 and r2 < 20
}

The patch is addressing #1 case. The #2 was working correctly already.

Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: Andrii Nakryiko <andrii@kernel.org>
Acked-by: John Fastabend <john.fastabend@gmail.com>
Tested-by: Yonghong Song <yhs@fb.com>
Link: https://lore.kernel.org/bpf/20201014175608.1416-1-alexei.starovoitov@gmail.com
kernel/bpf/verifier.c
tools/testing/selftests/bpf/verifier/regalloc.c