Loading...
Note: File does not exist in v5.4.
1// SPDX-License-Identifier: GPL-2.0
2#include <test_progs.h>
3
4#define MAX_INSNS 512
5#define MAX_MATCHES 16
6
7struct bpf_reg_match {
8 unsigned int line;
9 const char *match;
10};
11
12struct 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
25static 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=0,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=0,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=0,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=0,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=9223372034707292158,var_off=(0x2; 0x7fffffff7ffffffc)"},
460 /* packet pointer + nonnegative (4n+2) */
461 {11, "R6_w=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372034707292158,var_off=(0x2; 0x7fffffff7ffffffc)"},
462 {13, "R4_w=pkt(id=1,off=4,r=0,umin_value=2,umax_value=9223372034707292158,var_off=(0x2; 0x7fffffff7ffffffc)"},
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=9223372034707292158,var_off=(0x2; 0x7fffffff7ffffffc)"},
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=1,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=1,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=2,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=2,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0xfffffffc)"},
576 },
577 },
578};
579
580static 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
590static char bpf_vlog[32768];
591
592static 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
654void 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}