1 // SPDX-License-Identifier: GPL-2.0
2 #include <test_progs.h>
3 
4 #define MAX_INSNS	512
5 #define MAX_MATCHES	16
6 
7 struct bpf_reg_match {
8 	unsigned int line;
9 	const char *match;
10 };
11 
12 struct bpf_align_test {
13 	const char *descr;
14 	struct bpf_insn	insns[MAX_INSNS];
15 	enum {
16 		UNDEF,
17 		ACCEPT,
18 		REJECT
19 	} result;
20 	enum bpf_prog_type prog_type;
21 	/* Matches must be in order of increasing line */
22 	struct bpf_reg_match matches[MAX_MATCHES];
23 };
24 
25 static struct bpf_align_test tests[] = {
26 	/* Four tests of known constants.  These aren't staggeringly
27 	 * interesting since we track exact values now.
28 	 */
29 	{
30 		.descr = "mov",
31 		.insns = {
32 			BPF_MOV64_IMM(BPF_REG_3, 2),
33 			BPF_MOV64_IMM(BPF_REG_3, 4),
34 			BPF_MOV64_IMM(BPF_REG_3, 8),
35 			BPF_MOV64_IMM(BPF_REG_3, 16),
36 			BPF_MOV64_IMM(BPF_REG_3, 32),
37 			BPF_MOV64_IMM(BPF_REG_0, 0),
38 			BPF_EXIT_INSN(),
39 		},
40 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
41 		.matches = {
42 			{1, "R1=ctx(id=0,off=0,imm=0)"},
43 			{1, "R10=fp0"},
44 			{1, "R3_w=inv2"},
45 			{2, "R3_w=inv4"},
46 			{3, "R3_w=inv8"},
47 			{4, "R3_w=inv16"},
48 			{5, "R3_w=inv32"},
49 		},
50 	},
51 	{
52 		.descr = "shift",
53 		.insns = {
54 			BPF_MOV64_IMM(BPF_REG_3, 1),
55 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
56 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
57 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
58 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
59 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_3, 4),
60 			BPF_MOV64_IMM(BPF_REG_4, 32),
61 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
62 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
63 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
64 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
65 			BPF_MOV64_IMM(BPF_REG_0, 0),
66 			BPF_EXIT_INSN(),
67 		},
68 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
69 		.matches = {
70 			{1, "R1=ctx(id=0,off=0,imm=0)"},
71 			{1, "R10=fp0"},
72 			{1, "R3_w=inv1"},
73 			{2, "R3_w=inv2"},
74 			{3, "R3_w=inv4"},
75 			{4, "R3_w=inv8"},
76 			{5, "R3_w=inv16"},
77 			{6, "R3_w=inv1"},
78 			{7, "R4_w=inv32"},
79 			{8, "R4_w=inv16"},
80 			{9, "R4_w=inv8"},
81 			{10, "R4_w=inv4"},
82 			{11, "R4_w=inv2"},
83 		},
84 	},
85 	{
86 		.descr = "addsub",
87 		.insns = {
88 			BPF_MOV64_IMM(BPF_REG_3, 4),
89 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 4),
90 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 2),
91 			BPF_MOV64_IMM(BPF_REG_4, 8),
92 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
93 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 2),
94 			BPF_MOV64_IMM(BPF_REG_0, 0),
95 			BPF_EXIT_INSN(),
96 		},
97 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
98 		.matches = {
99 			{1, "R1=ctx(id=0,off=0,imm=0)"},
100 			{1, "R10=fp0"},
101 			{1, "R3_w=inv4"},
102 			{2, "R3_w=inv8"},
103 			{3, "R3_w=inv10"},
104 			{4, "R4_w=inv8"},
105 			{5, "R4_w=inv12"},
106 			{6, "R4_w=inv14"},
107 		},
108 	},
109 	{
110 		.descr = "mul",
111 		.insns = {
112 			BPF_MOV64_IMM(BPF_REG_3, 7),
113 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 1),
114 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 2),
115 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 4),
116 			BPF_MOV64_IMM(BPF_REG_0, 0),
117 			BPF_EXIT_INSN(),
118 		},
119 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
120 		.matches = {
121 			{1, "R1=ctx(id=0,off=0,imm=0)"},
122 			{1, "R10=fp0"},
123 			{1, "R3_w=inv7"},
124 			{2, "R3_w=inv7"},
125 			{3, "R3_w=inv14"},
126 			{4, "R3_w=inv56"},
127 		},
128 	},
129 
130 	/* Tests using unknown values */
131 #define PREP_PKT_POINTERS \
132 	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, \
133 		    offsetof(struct __sk_buff, data)), \
134 	BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, \
135 		    offsetof(struct __sk_buff, data_end))
136 
137 #define LOAD_UNKNOWN(DST_REG) \
138 	PREP_PKT_POINTERS, \
139 	BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), \
140 	BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 8), \
141 	BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_0, 1), \
142 	BPF_EXIT_INSN(), \
143 	BPF_LDX_MEM(BPF_B, DST_REG, BPF_REG_2, 0)
144 
145 	{
146 		.descr = "unknown shift",
147 		.insns = {
148 			LOAD_UNKNOWN(BPF_REG_3),
149 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
150 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
151 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
152 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
153 			LOAD_UNKNOWN(BPF_REG_4),
154 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_4, 5),
155 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
156 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
157 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
158 			BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
159 			BPF_MOV64_IMM(BPF_REG_0, 0),
160 			BPF_EXIT_INSN(),
161 		},
162 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
163 		.matches = {
164 			{7, "R0_w=pkt(id=0,off=8,r=8,imm=0)"},
165 			{7, "R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
166 			{8, "R3_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
167 			{9, "R3_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
168 			{10, "R3_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
169 			{11, "R3_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
170 			{18, "R3=pkt_end(id=0,off=0,imm=0)"},
171 			{18, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
172 			{19, "R4_w=inv(id=0,umax_value=8160,var_off=(0x0; 0x1fe0))"},
173 			{20, "R4_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
174 			{21, "R4_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
175 			{22, "R4_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
176 			{23, "R4_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
177 		},
178 	},
179 	{
180 		.descr = "unknown mul",
181 		.insns = {
182 			LOAD_UNKNOWN(BPF_REG_3),
183 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
184 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 1),
185 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
186 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 2),
187 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
188 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 4),
189 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
190 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 8),
191 			BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 2),
192 			BPF_MOV64_IMM(BPF_REG_0, 0),
193 			BPF_EXIT_INSN(),
194 		},
195 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
196 		.matches = {
197 			{7, "R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
198 			{8, "R4_w=inv(id=1,umax_value=255,var_off=(0x0; 0xff))"},
199 			{9, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
200 			{10, "R4_w=inv(id=1,umax_value=255,var_off=(0x0; 0xff))"},
201 			{11, "R4_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
202 			{12, "R4_w=inv(id=1,umax_value=255,var_off=(0x0; 0xff))"},
203 			{13, "R4_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
204 			{14, "R4_w=inv(id=1,umax_value=255,var_off=(0x0; 0xff))"},
205 			{15, "R4_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
206 			{16, "R4_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
207 		},
208 	},
209 	{
210 		.descr = "packet const offset",
211 		.insns = {
212 			PREP_PKT_POINTERS,
213 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
214 
215 			BPF_MOV64_IMM(BPF_REG_0, 0),
216 
217 			/* Skip over ethernet header.  */
218 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
219 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
220 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
221 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
222 			BPF_EXIT_INSN(),
223 
224 			BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 0),
225 			BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 1),
226 			BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 2),
227 			BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 3),
228 			BPF_LDX_MEM(BPF_H, BPF_REG_4, BPF_REG_5, 0),
229 			BPF_LDX_MEM(BPF_H, BPF_REG_4, BPF_REG_5, 2),
230 			BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
231 
232 			BPF_MOV64_IMM(BPF_REG_0, 0),
233 			BPF_EXIT_INSN(),
234 		},
235 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
236 		.matches = {
237 			{4, "R5_w=pkt(id=0,off=0,r=0,imm=0)"},
238 			{5, "R5_w=pkt(id=0,off=14,r=0,imm=0)"},
239 			{6, "R4_w=pkt(id=0,off=14,r=0,imm=0)"},
240 			{10, "R2=pkt(id=0,off=0,r=18,imm=0)"},
241 			{10, "R5=pkt(id=0,off=14,r=18,imm=0)"},
242 			{10, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
243 			{14, "R4_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
244 			{15, "R4_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
245 		},
246 	},
247 	{
248 		.descr = "packet variable offset",
249 		.insns = {
250 			LOAD_UNKNOWN(BPF_REG_6),
251 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
252 
253 			/* First, add a constant to the R5 packet pointer,
254 			 * then a variable with a known alignment.
255 			 */
256 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
257 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
258 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
259 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
260 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
261 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
262 			BPF_EXIT_INSN(),
263 			BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
264 
265 			/* Now, test in the other direction.  Adding first
266 			 * the variable offset to R5, then the constant.
267 			 */
268 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
269 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
270 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
271 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
272 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
273 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
274 			BPF_EXIT_INSN(),
275 			BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
276 
277 			/* Test multiple accumulations of unknown values
278 			 * into a packet pointer.
279 			 */
280 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
281 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
282 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
283 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 4),
284 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
285 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
286 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
287 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
288 			BPF_EXIT_INSN(),
289 			BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
290 
291 			BPF_MOV64_IMM(BPF_REG_0, 0),
292 			BPF_EXIT_INSN(),
293 		},
294 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
295 		.matches = {
296 			/* Calculated offset in R6 has unknown value, but known
297 			 * alignment of 4.
298 			 */
299 			{8, "R2_w=pkt(id=0,off=0,r=8,imm=0)"},
300 			{8, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
301 			/* Offset is added to packet pointer R5, resulting in
302 			 * known fixed offset, and variable offset from R6.
303 			 */
304 			{11, "R5_w=pkt(id=1,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
305 			/* At the time the word size load is performed from R5,
306 			 * it's total offset is NET_IP_ALIGN + reg->off (0) +
307 			 * reg->aux_off (14) which is 16.  Then the variable
308 			 * offset is considered using reg->aux_off_align which
309 			 * is 4 and meets the load's requirements.
310 			 */
311 			{15, "R4=pkt(id=1,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
312 			{15, "R5=pkt(id=1,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
313 			/* Variable offset is added to R5 packet pointer,
314 			 * resulting in auxiliary alignment of 4.
315 			 */
316 			{18, "R5_w=pkt(id=2,off=0,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
317 			/* Constant offset is added to R5, resulting in
318 			 * reg->off of 14.
319 			 */
320 			{19, "R5_w=pkt(id=2,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
321 			/* At the time the word size load is performed from R5,
322 			 * its total fixed offset is NET_IP_ALIGN + reg->off
323 			 * (14) which is 16.  Then the variable offset is 4-byte
324 			 * aligned, so the total offset is 4-byte aligned and
325 			 * meets the load's requirements.
326 			 */
327 			{23, "R4=pkt(id=2,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
328 			{23, "R5=pkt(id=2,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
329 			/* Constant offset is added to R5 packet pointer,
330 			 * resulting in reg->off value of 14.
331 			 */
332 			{26, "R5_w=pkt(id=0,off=14,r=8"},
333 			/* Variable offset is added to R5, resulting in a
334 			 * variable offset of (4n).
335 			 */
336 			{27, "R5_w=pkt(id=3,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
337 			/* Constant is added to R5 again, setting reg->off to 18. */
338 			{28, "R5_w=pkt(id=3,off=18,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
339 			/* And once more we add a variable; resulting var_off
340 			 * is still (4n), fixed offset is not changed.
341 			 * Also, we create a new reg->id.
342 			 */
343 			{29, "R5_w=pkt(id=4,off=18,r=0,umax_value=2040,var_off=(0x0; 0x7fc)"},
344 			/* At the time the word size load is performed from R5,
345 			 * its total fixed offset is NET_IP_ALIGN + reg->off (18)
346 			 * which is 20.  Then the variable offset is (4n), so
347 			 * the total offset is 4-byte aligned and meets the
348 			 * load's requirements.
349 			 */
350 			{33, "R4=pkt(id=4,off=22,r=22,umax_value=2040,var_off=(0x0; 0x7fc)"},
351 			{33, "R5=pkt(id=4,off=18,r=22,umax_value=2040,var_off=(0x0; 0x7fc)"},
352 		},
353 	},
354 	{
355 		.descr = "packet variable offset 2",
356 		.insns = {
357 			/* Create an unknown offset, (4n+2)-aligned */
358 			LOAD_UNKNOWN(BPF_REG_6),
359 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
360 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
361 			/* Add it to the packet pointer */
362 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
363 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
364 			/* Check bounds and perform a read */
365 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
366 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
367 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
368 			BPF_EXIT_INSN(),
369 			BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
370 			/* Make a (4n) offset from the value we just read */
371 			BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xff),
372 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
373 			/* Add it to the packet pointer */
374 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
375 			/* Check bounds and perform a read */
376 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
377 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
378 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
379 			BPF_EXIT_INSN(),
380 			BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
381 			BPF_MOV64_IMM(BPF_REG_0, 0),
382 			BPF_EXIT_INSN(),
383 		},
384 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
385 		.matches = {
386 			/* Calculated offset in R6 has unknown value, but known
387 			 * alignment of 4.
388 			 */
389 			{8, "R2_w=pkt(id=0,off=0,r=8,imm=0)"},
390 			{8, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
391 			/* Adding 14 makes R6 be (4n+2) */
392 			{9, "R6_w=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
393 			/* Packet pointer has (4n+2) offset */
394 			{11, "R5_w=pkt(id=1,off=0,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc)"},
395 			{13, "R4=pkt(id=1,off=4,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc)"},
396 			/* At the time the word size load is performed from R5,
397 			 * its total fixed offset is NET_IP_ALIGN + reg->off (0)
398 			 * which is 2.  Then the variable offset is (4n+2), so
399 			 * the total offset is 4-byte aligned and meets the
400 			 * load's requirements.
401 			 */
402 			{15, "R5=pkt(id=1,off=0,r=4,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc)"},
403 			/* Newly read value in R6 was shifted left by 2, so has
404 			 * known alignment of 4.
405 			 */
406 			{18, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
407 			/* Added (4n) to packet pointer's (4n+2) var_off, giving
408 			 * another (4n+2).
409 			 */
410 			{19, "R5_w=pkt(id=2,off=0,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc)"},
411 			{21, "R4=pkt(id=2,off=4,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc)"},
412 			/* At the time the word size load is performed from R5,
413 			 * its total fixed offset is NET_IP_ALIGN + reg->off (0)
414 			 * which is 2.  Then the variable offset is (4n+2), so
415 			 * the total offset is 4-byte aligned and meets the
416 			 * load's requirements.
417 			 */
418 			{23, "R5=pkt(id=2,off=0,r=4,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc)"},
419 		},
420 	},
421 	{
422 		.descr = "dubious pointer arithmetic",
423 		.insns = {
424 			PREP_PKT_POINTERS,
425 			BPF_MOV64_IMM(BPF_REG_0, 0),
426 			/* (ptr - ptr) << 2 */
427 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_3),
428 			BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_2),
429 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_5, 2),
430 			/* We have a (4n) value.  Let's make a packet offset
431 			 * out of it.  First add 14, to make it a (4n+2)
432 			 */
433 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
434 			/* Then make sure it's nonnegative */
435 			BPF_JMP_IMM(BPF_JSGE, BPF_REG_5, 0, 1),
436 			BPF_EXIT_INSN(),
437 			/* Add it to packet pointer */
438 			BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
439 			BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
440 			/* Check bounds and perform a read */
441 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_6),
442 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
443 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
444 			BPF_EXIT_INSN(),
445 			BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_6, 0),
446 			BPF_EXIT_INSN(),
447 		},
448 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
449 		.result = REJECT,
450 		.matches = {
451 			{4, "R5_w=pkt_end(id=0,off=0,imm=0)"},
452 			/* (ptr - ptr) << 2 == unknown, (4n) */
453 			{6, "R5_w=inv(id=0,smax_value=9223372036854775804,umax_value=18446744073709551612,var_off=(0x0; 0xfffffffffffffffc)"},
454 			/* (4n) + 14 == (4n+2).  We blow our bounds, because
455 			 * the add could overflow.
456 			 */
457 			{7, "R5_w=inv(id=0,smin_value=-9223372036854775806,smax_value=9223372036854775806,umin_value=2,umax_value=18446744073709551614,var_off=(0x2; 0xfffffffffffffffc)"},
458 			/* Checked s>=0 */
459 			{9, "R5=inv(id=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc)"},
460 			/* packet pointer + nonnegative (4n+2) */
461 			{11, "R6_w=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc)"},
462 			{13, "R4_w=pkt(id=1,off=4,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc)"},
463 			/* NET_IP_ALIGN + (4n+2) == (4n), alignment is fine.
464 			 * We checked the bounds, but it might have been able
465 			 * to overflow if the packet pointer started in the
466 			 * upper half of the address space.
467 			 * So we did not get a 'range' on R6, and the access
468 			 * attempt will fail.
469 			 */
470 			{15, "R6_w=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc)"},
471 		}
472 	},
473 	{
474 		.descr = "variable subtraction",
475 		.insns = {
476 			/* Create an unknown offset, (4n+2)-aligned */
477 			LOAD_UNKNOWN(BPF_REG_6),
478 			BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
479 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
480 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
481 			/* Create another unknown, (4n)-aligned, and subtract
482 			 * it from the first one
483 			 */
484 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
485 			BPF_ALU64_REG(BPF_SUB, BPF_REG_6, BPF_REG_7),
486 			/* Bounds-check the result */
487 			BPF_JMP_IMM(BPF_JSGE, BPF_REG_6, 0, 1),
488 			BPF_EXIT_INSN(),
489 			/* Add it to the packet pointer */
490 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
491 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
492 			/* Check bounds and perform a read */
493 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
494 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
495 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
496 			BPF_EXIT_INSN(),
497 			BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
498 			BPF_EXIT_INSN(),
499 		},
500 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
501 		.matches = {
502 			/* Calculated offset in R6 has unknown value, but known
503 			 * alignment of 4.
504 			 */
505 			{7, "R2_w=pkt(id=0,off=0,r=8,imm=0)"},
506 			{9, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
507 			/* Adding 14 makes R6 be (4n+2) */
508 			{10, "R6_w=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
509 			/* New unknown value in R7 is (4n) */
510 			{11, "R7_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
511 			/* Subtracting it from R6 blows our unsigned bounds */
512 			{12, "R6=inv(id=0,smin_value=-1006,smax_value=1034,umin_value=2,umax_value=18446744073709551614,var_off=(0x2; 0xfffffffffffffffc)"},
513 			/* Checked s>= 0 */
514 			{14, "R6=inv(id=0,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc))"},
515 			/* At the time the word size load is performed from R5,
516 			 * its total fixed offset is NET_IP_ALIGN + reg->off (0)
517 			 * which is 2.  Then the variable offset is (4n+2), so
518 			 * the total offset is 4-byte aligned and meets the
519 			 * load's requirements.
520 			 */
521 			{20, "R5=pkt(id=2,off=0,r=4,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc)"},
522 
523 		},
524 	},
525 	{
526 		.descr = "pointer variable subtraction",
527 		.insns = {
528 			/* Create an unknown offset, (4n+2)-aligned and bounded
529 			 * to [14,74]
530 			 */
531 			LOAD_UNKNOWN(BPF_REG_6),
532 			BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
533 			BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xf),
534 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
535 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
536 			/* Subtract it from the packet pointer */
537 			BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
538 			BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_6),
539 			/* Create another unknown, (4n)-aligned and >= 74.
540 			 * That in fact means >= 76, since 74 % 4 == 2
541 			 */
542 			BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
543 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_7, 76),
544 			/* Add it to the packet pointer */
545 			BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_7),
546 			/* Check bounds and perform a read */
547 			BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
548 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
549 			BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
550 			BPF_EXIT_INSN(),
551 			BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
552 			BPF_EXIT_INSN(),
553 		},
554 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
555 		.matches = {
556 			/* Calculated offset in R6 has unknown value, but known
557 			 * alignment of 4.
558 			 */
559 			{7, "R2_w=pkt(id=0,off=0,r=8,imm=0)"},
560 			{10, "R6_w=inv(id=0,umax_value=60,var_off=(0x0; 0x3c))"},
561 			/* Adding 14 makes R6 be (4n+2) */
562 			{11, "R6_w=inv(id=0,umin_value=14,umax_value=74,var_off=(0x2; 0x7c))"},
563 			/* Subtracting from packet pointer overflows ubounds */
564 			{13, "R5_w=pkt(id=2,off=0,r=8,umin_value=18446744073709551542,umax_value=18446744073709551602,var_off=(0xffffffffffffff82; 0x7c)"},
565 			/* New unknown value in R7 is (4n), >= 76 */
566 			{15, "R7_w=inv(id=0,umin_value=76,umax_value=1096,var_off=(0x0; 0x7fc))"},
567 			/* Adding it to packet pointer gives nice bounds again */
568 			{16, "R5_w=pkt(id=3,off=0,r=0,umin_value=2,umax_value=1082,var_off=(0x2; 0xfffffffc)"},
569 			/* At the time the word size load is performed from R5,
570 			 * its total fixed offset is NET_IP_ALIGN + reg->off (0)
571 			 * which is 2.  Then the variable offset is (4n+2), so
572 			 * the total offset is 4-byte aligned and meets the
573 			 * load's requirements.
574 			 */
575 			{20, "R5=pkt(id=3,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0xfffffffc)"},
576 		},
577 	},
578 };
579 
580 static int probe_filter_length(const struct bpf_insn *fp)
581 {
582 	int len;
583 
584 	for (len = MAX_INSNS - 1; len > 0; --len)
585 		if (fp[len].code != 0 || fp[len].imm != 0)
586 			break;
587 	return len + 1;
588 }
589 
590 static char bpf_vlog[32768];
591 
592 static int do_test_single(struct bpf_align_test *test)
593 {
594 	struct bpf_insn *prog = test->insns;
595 	int prog_type = test->prog_type;
596 	char bpf_vlog_copy[32768];
597 	const char *line_ptr;
598 	int cur_line = -1;
599 	int prog_len, i;
600 	int fd_prog;
601 	int ret;
602 
603 	prog_len = probe_filter_length(prog);
604 	fd_prog = bpf_verify_program(prog_type ? : BPF_PROG_TYPE_SOCKET_FILTER,
605 				     prog, prog_len, BPF_F_STRICT_ALIGNMENT,
606 				     "GPL", 0, bpf_vlog, sizeof(bpf_vlog), 2);
607 	if (fd_prog < 0 && test->result != REJECT) {
608 		printf("Failed to load program.\n");
609 		printf("%s", bpf_vlog);
610 		ret = 1;
611 	} else if (fd_prog >= 0 && test->result == REJECT) {
612 		printf("Unexpected success to load!\n");
613 		printf("%s", bpf_vlog);
614 		ret = 1;
615 		close(fd_prog);
616 	} else {
617 		ret = 0;
618 		/* We make a local copy so that we can strtok() it */
619 		strncpy(bpf_vlog_copy, bpf_vlog, sizeof(bpf_vlog_copy));
620 		line_ptr = strtok(bpf_vlog_copy, "\n");
621 		for (i = 0; i < MAX_MATCHES; i++) {
622 			struct bpf_reg_match m = test->matches[i];
623 
624 			if (!m.match)
625 				break;
626 			while (line_ptr) {
627 				cur_line = -1;
628 				sscanf(line_ptr, "%u: ", &cur_line);
629 				if (cur_line == m.line)
630 					break;
631 				line_ptr = strtok(NULL, "\n");
632 			}
633 			if (!line_ptr) {
634 				printf("Failed to find line %u for match: %s\n",
635 				       m.line, m.match);
636 				ret = 1;
637 				printf("%s", bpf_vlog);
638 				break;
639 			}
640 			if (!strstr(line_ptr, m.match)) {
641 				printf("Failed to find match %u: %s\n",
642 				       m.line, m.match);
643 				ret = 1;
644 				printf("%s", bpf_vlog);
645 				break;
646 			}
647 		}
648 		if (fd_prog >= 0)
649 			close(fd_prog);
650 	}
651 	return ret;
652 }
653 
654 void test_align(void)
655 {
656 	unsigned int i;
657 
658 	for (i = 0; i < ARRAY_SIZE(tests); i++) {
659 		struct bpf_align_test *test = &tests[i];
660 
661 		if (!test__start_subtest(test->descr))
662 			continue;
663 
664 		CHECK_FAIL(do_test_single(test));
665 	}
666 }
667