Merge branch 'subreg-bounds'
authorAlexei Starovoitov <ast@kernel.org>
Mon, 30 Mar 2020 21:44:16 +0000 (14:44 -0700)
committerAlexei Starovoitov <ast@kernel.org>
Mon, 30 Mar 2020 22:11:40 +0000 (15:11 -0700)
commite5ffcc9191ca72ddf1c999a80ae9165705ac4790
tree891b4fa11cdd0212fe9f094af6d6a1e70cc679f9
parent4edf16b72c57bb0faad5da143f812384df0c43f6
parent41f70fe0649dddf02046315dc566e06da5a2dc91
Merge branch 'subreg-bounds'

John Fastabend says:

====================
This series adds ALU32 signed and unsigned min/max bounds.

The origins of this work is to fix do_refine_retval_range() which before
this series clamps the return value bounds to [0, max]. However, this
is not correct because its possible these functions may return negative
errors so the correct bound is [*MIN, max]. Where *MIN is the signed
and unsigned min values U64_MIN and S64_MIN. And 'max' here is the max
positive value returned by this routine.

Patch 1 changes the do_refine_retval_range() to return the correct bounds
but this breaks existing programs that were depending on the old incorrect
bound. To repair these old programs we add ALU32 bounds to properly track
the return values from these helpers. The ALU32 bounds are needed because
clang realizes these helepers return 'int' type and will use jmp32 ops
with the return value.  With current state of things this does little to
help 64bit bounds and with patch 1 applied will cause many programs to
fail verifier pass. See patch 5 for trace details on how this happens.

Patch 2 does the ALU32 addition it adds the new bounds and populates them
through the verifier. Design note, initially a var32 was added but as
pointed out by Alexei and Edward it is not strictly needed so it was
removed here. This worked out nicely.

Patch 3 notes that the refine return value can now also bound the 32-bit
subregister allowing better bouinds tracking in these cases.

Patches 4 adds a C test case to test_progs which will cause the verifier
to fail if new 32bit and do_refine_retval_range() is incorrect.

Patches 5 and 6 fix test cases that broke after refining the return
values from helpers. I attempted to be explicit about each failure and
why we need the change. See patches for details.

Patch 7 adds some bounds check tests to ensure bounds checking when
mixing alu32, alu64 and jmp32 ops together.

Thanks to Alexei, Edward, and Daniel for initial feedback it helped clean
this up a lot.

v2:
  - rebased to bpf-next
  - fixed tnum equals optimization for combining 32->64bits
  - updated patch to fix verifier test correctly
  - updated refine_retval_range to set both s32_*_value and s*_value we
    need both to get better bounds tracking
====================

Signed-off-by: Alexei Starovoitov <ast@kernel.org>