Skip to content

Commit f1174f7

Browse files
ecree-solarflaredavem330
ecree-solarflare
authored and
davem330
committed
bpf/verifier: rework value tracking
Unifies adjusted and unadjusted register value types (e.g. FRAME_POINTER is now just a PTR_TO_STACK with zero offset). Tracks value alignment by means of tracking known & unknown bits. This also replaces the 'reg->imm' (leading zero bits) calculations for (what were) UNKNOWN_VALUEs. If pointer leaks are allowed, and adjust_ptr_min_max_vals returns -EACCES, treat the pointer as an unknown scalar and try again, because we might be able to conclude something about the result (e.g. pointer & 0x40 is either 0 or 0x40). Verifier hooks in the netronome/nfp driver were changed to match the new data structures. Signed-off-by: Edward Cree <ecree@solarflare.com> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent e1cb90f commit f1174f7

File tree

7 files changed

+1265
-852
lines changed

7 files changed

+1265
-852
lines changed

‎drivers/net/ethernet/netronome/nfp/bpf/verifier.c

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -79,28 +79,32 @@ nfp_bpf_check_exit(struct nfp_prog *nfp_prog,
7979
const struct bpf_verifier_env *env)
8080
{
8181
const struct bpf_reg_state *reg0 = &env->cur_state.regs[0];
82+
u64 imm;
8283

8384
if (nfp_prog->act == NN_ACT_XDP)
8485
return 0;
8586

86-
if (reg0->type != CONST_IMM) {
87-
pr_info("unsupported exit state: %d, imm: %llx\n",
88-
reg0->type, reg0->imm);
87+
if (!(reg0->type == SCALAR_VALUE && tnum_is_const(reg0->var_off))) {
88+
char tn_buf[48];
89+
90+
tnum_strn(tn_buf, sizeof(tn_buf), reg0->var_off);
91+
pr_info("unsupported exit state: %d, var_off: %s\n",
92+
reg0->type, tn_buf);
8993
return -EINVAL;
9094
}
9195

92-
if (nfp_prog->act != NN_ACT_DIRECT &&
93-
reg0->imm != 0 && (reg0->imm & ~0U) != ~0U) {
96+
imm = reg0->var_off.value;
97+
if (nfp_prog->act != NN_ACT_DIRECT && imm != 0 && (imm & ~0U) != ~0U) {
9498
pr_info("unsupported exit state: %d, imm: %llx\n",
95-
reg0->type, reg0->imm);
99+
reg0->type, imm);
96100
return -EINVAL;
97101
}
98102

99-
if (nfp_prog->act == NN_ACT_DIRECT && reg0->imm <= TC_ACT_REDIRECT &&
100-
reg0->imm != TC_ACT_SHOT && reg0->imm != TC_ACT_STOLEN &&
101-
reg0->imm != TC_ACT_QUEUED) {
103+
if (nfp_prog->act == NN_ACT_DIRECT && imm <= TC_ACT_REDIRECT &&
104+
imm != TC_ACT_SHOT && imm != TC_ACT_STOLEN &&
105+
imm != TC_ACT_QUEUED) {
102106
pr_info("unsupported exit state: %d, imm: %llx\n",
103-
reg0->type, reg0->imm);
107+
reg0->type, imm);
104108
return -EINVAL;
105109
}
106110

‎include/linux/bpf.h

Lines changed: 12 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -117,35 +117,25 @@ enum bpf_access_type {
117117
};
118118

119119
/* types of values stored in eBPF registers */
120+
/* Pointer types represent:
121+
* pointer
122+
* pointer + imm
123+
* pointer + (u16) var
124+
* pointer + (u16) var + imm
125+
* if (range > 0) then [ptr, ptr + range - off) is safe to access
126+
* if (id > 0) means that some 'var' was added
127+
* if (off > 0) means that 'imm' was added
128+
*/
120129
enum bpf_reg_type {
121130
NOT_INIT = 0, /* nothing was written into register */
122-
UNKNOWN_VALUE, /* reg doesn't contain a valid pointer */
131+
SCALAR_VALUE, /* reg doesn't contain a valid pointer */
123132
PTR_TO_CTX, /* reg points to bpf_context */
124133
CONST_PTR_TO_MAP, /* reg points to struct bpf_map */
125134
PTR_TO_MAP_VALUE, /* reg points to map element value */
126135
PTR_TO_MAP_VALUE_OR_NULL,/* points to map elem value or NULL */
127-
FRAME_PTR, /* reg == frame_pointer */
128-
PTR_TO_STACK, /* reg == frame_pointer + imm */
129-
CONST_IMM, /* constant integer value */
130-
131-
/* PTR_TO_PACKET represents:
132-
* skb->data
133-
* skb->data + imm
134-
* skb->data + (u16) var
135-
* skb->data + (u16) var + imm
136-
* if (range > 0) then [ptr, ptr + range - off) is safe to access
137-
* if (id > 0) means that some 'var' was added
138-
* if (off > 0) menas that 'imm' was added
139-
*/
140-
PTR_TO_PACKET,
136+
PTR_TO_STACK, /* reg == frame_pointer + offset */
137+
PTR_TO_PACKET, /* reg points to skb->data */
141138
PTR_TO_PACKET_END, /* skb->data + headlen */
142-
143-
/* PTR_TO_MAP_VALUE_ADJ is used for doing pointer math inside of a map
144-
* elem value. We only allow this if we can statically verify that
145-
* access from this register are going to fall within the size of the
146-
* map element.
147-
*/
148-
PTR_TO_MAP_VALUE_ADJ,
149139
};
150140

151141
struct bpf_prog;

‎include/linux/bpf_verifier.h

Lines changed: 21 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99

1010
#include <linux/bpf.h> /* for enum bpf_reg_type */
1111
#include <linux/filter.h> /* for MAX_BPF_STACK */
12+
#include <linux/tnum.h>
1213

1314
/* Just some arbitrary values so we can safely do math without overflowing and
1415
* are obviously wrong for any sort of memory access.
@@ -19,30 +20,37 @@
1920
struct bpf_reg_state {
2021
enum bpf_reg_type type;
2122
union {
22-
/* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE */
23-
s64 imm;
24-
25-
/* valid when type == PTR_TO_PACKET* */
26-
struct {
27-
u16 off;
28-
u16 range;
29-
};
23+
/* valid when type == PTR_TO_PACKET */
24+
u16 range;
3025

3126
/* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE |
3227
* PTR_TO_MAP_VALUE_OR_NULL
3328
*/
3429
struct bpf_map *map_ptr;
3530
};
31+
/* Fixed part of pointer offset, pointer types only */
32+
s32 off;
33+
/* For PTR_TO_PACKET, used to find other pointers with the same variable
34+
* offset, so they can share range knowledge.
35+
* For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
36+
* came from, when one is tested for != NULL.
37+
*/
3638
u32 id;
39+
/* These three fields must be last. See states_equal() */
40+
/* For scalar types (SCALAR_VALUE), this represents our knowledge of
41+
* the actual value.
42+
* For pointer types, this represents the variable part of the offset
43+
* from the pointed-to object, and is shared with all bpf_reg_states
44+
* with the same id as us.
45+
*/
46+
struct tnum var_off;
3747
/* Used to determine if any memory access using this register will
38-
* result in a bad access. These two fields must be last.
39-
* See states_equal()
48+
* result in a bad access.
49+
* These refer to the same value as var_off, not necessarily the actual
50+
* contents of the register.
4051
*/
4152
s64 min_value;
4253
u64 max_value;
43-
u32 min_align;
44-
u32 aux_off;
45-
u32 aux_off_align;
4654
bool value_from_signed;
4755
};
4856

‎include/linux/tnum.h

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
/* tnum: tracked (or tristate) numbers
2+
*
3+
* A tnum tracks knowledge about the bits of a value. Each bit can be either
4+
* known (0 or 1), or unknown (x). Arithmetic operations on tnums will
5+
* propagate the unknown bits such that the tnum result represents all the
6+
* possible results for possible values of the operands.
7+
*/
8+
#include <linux/types.h>
9+
10+
struct tnum {
11+
u64 value;
12+
u64 mask;
13+
};
14+
15+
/* Constructors */
16+
/* Represent a known constant as a tnum. */
17+
struct tnum tnum_const(u64 value);
18+
/* A completely unknown value */
19+
extern const struct tnum tnum_unknown;
20+
21+
/* Arithmetic and logical ops */
22+
/* Shift a tnum left (by a fixed shift) */
23+
struct tnum tnum_lshift(struct tnum a, u8 shift);
24+
/* Shift a tnum right (by a fixed shift) */
25+
struct tnum tnum_rshift(struct tnum a, u8 shift);
26+
/* Add two tnums, return @a + @b */
27+
struct tnum tnum_add(struct tnum a, struct tnum b);
28+
/* Subtract two tnums, return @a - @b */
29+
struct tnum tnum_sub(struct tnum a, struct tnum b);
30+
/* Bitwise-AND, return @a & @b */
31+
struct tnum tnum_and(struct tnum a, struct tnum b);
32+
/* Bitwise-OR, return @a | @b */
33+
struct tnum tnum_or(struct tnum a, struct tnum b);
34+
/* Bitwise-XOR, return @a ^ @b */
35+
struct tnum tnum_xor(struct tnum a, struct tnum b);
36+
/* Multiply two tnums, return @a * @b */
37+
struct tnum tnum_mul(struct tnum a, struct tnum b);
38+
39+
/* Return a tnum representing numbers satisfying both @a and @b */
40+
struct tnum tnum_intersect(struct tnum a, struct tnum b);
41+
42+
/* Return @a with all but the lowest @size bytes cleared */
43+
struct tnum tnum_cast(struct tnum a, u8 size);
44+
45+
/* Returns true if @a is a known constant */
46+
static inline bool tnum_is_const(struct tnum a)
47+
{
48+
return !a.mask;
49+
}
50+
51+
/* Returns true if @a == tnum_const(@b) */
52+
static inline bool tnum_equals_const(struct tnum a, u64 b)
53+
{
54+
return tnum_is_const(a) && a.value == b;
55+
}
56+
57+
/* Returns true if @a is completely unknown */
58+
static inline bool tnum_is_unknown(struct tnum a)
59+
{
60+
return !~a.mask;
61+
}
62+
63+
/* Returns true if @a is known to be a multiple of @size.
64+
* @size must be a power of two.
65+
*/
66+
bool tnum_is_aligned(struct tnum a, u64 size);
67+
68+
/* Returns true if @b represents a subset of @a. */
69+
bool tnum_in(struct tnum a, struct tnum b);
70+
71+
/* Formatting functions. These have snprintf-like semantics: they will write
72+
* up to @size bytes (including the terminating NUL byte), and return the number
73+
* of bytes (excluding the terminating NUL) which would have been written had
74+
* sufficient space been available. (Thus tnum_sbin always returns 64.)
75+
*/
76+
/* Format a tnum as a pair of hex numbers (value; mask) */
77+
int tnum_strn(char *str, size_t size, struct tnum a);
78+
/* Format a tnum as tristate binary expansion */
79+
int tnum_sbin(char *str, size_t size, struct tnum a);

‎kernel/bpf/Makefile

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
obj-y := core.o
22

3-
obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o
3+
obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o
44
obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o
55
ifeq ($(CONFIG_NET),y)
66
obj-$(CONFIG_BPF_SYSCALL) += devmap.o

0 commit comments

Comments
 (0)