Patch "bpf: Detect identical PTR_TO_MAP_VALUE_OR_NULL registers" has been added to the 4.9-stable tree

This is a note to let you know that I've just added the patch titled

bpf: Detect identical PTR_TO_MAP_VALUE_OR_NULL registers

to the 4.9-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
bpf-detect-identical-ptr_to_map_value_or_null-registers.patch
and it can be found in the queue-4.9 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

From: Thomas Graf <[email protected]>
Date: Tue, 18 Oct 2016 19:51:19 +0200
Subject: bpf: Detect identical PTR_TO_MAP_VALUE_OR_NULL registers

From: Thomas Graf <[email protected]>

[ Upstream commit 57a09bf0a416700676e77102c28f9cfcb48267e0 ]

A BPF program is required to check the return register of a map_elem_lookup() call before accessing memory. The verifier keeps track of this by converting the type of the result register from PTR_TO_MAP_VALUE_OR_NULL to PTR_TO_MAP_VALUE after a conditional jump ensures safety. This check is currently exclusively performed for the result register 0.

In the event the compiler reorders instructions, BPF_MOV64_REG instructions may be moved before the conditional jump which causes them to keep their type PTR_TO_MAP_VALUE_OR_NULL to which the verifier objects when the register is accessed:

0: (b7) r1 = 10
1: (7b) *(u64 *)(r10 -8) = r1
2: (bf) r2 = r10
3: (07) r2 += -8
4: (18) r1 = 0x59c00000
6: (85) call 1
7: (bf) r4 = r0
8: (15) if r0 == 0x0 goto pc+1
R0=map_value(ks=8,vs=8) R4=map_value_or_null(ks=8,vs=8) R10=fp
9: (7a) *(u64 *)(r4 +0) = 0
R4 invalid mem access 'map_value_or_null'

This commit extends the verifier to keep track of all identical PTR_TO_MAP_VALUE_OR_NULL registers after a map_elem_lookup() by assigning them an ID and then marking them all when the conditional jump is observed.

---
 include/linux/bpf_verifier.h |    2 -
 kernel/bpf/verifier.c        |   61 +++++++++++++++++++++++++++++++------------
 2 files changed, 46 insertions(+), 17 deletions(-)

@@ -24,13 +24,13 @@ struct bpf_reg_state {
 	 */
 	s64 min_value;
 	u64 max_value;
+	u32 id;
 	union {
 		/* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE */
 		s64 imm;
 
 		/* valid when type == PTR_TO_PACKET* */
 		struct {
-			u32 id;
 			u16 off;
 			u16 range;
 		};

Patches currently in stable-queue which might be from [email protected] are

queue-4.9/bpf-fix-regression-on-verifier-pruning-wrt-map-lookups.patch queue-4.9/bpf-fix-state-equivalence.patch queue-4.9/bpf-detect-identical-ptr_to_map_value_or_null-registers.patch