Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2025 Huawei Technologies Co., Ltd
3 : : */
4 : :
5 : : #include "test.h"
6 : :
7 : : #include <bpf_def.h>
8 : : #include <rte_bpf.h>
9 : : #include <rte_bpf_validate_debug.h>
10 : : #include <rte_errno.h>
11 : :
12 : : /*
13 : : * Tests of BPF validation.
14 : : */
15 : :
16 : : extern int test_bpf_validate_logtype;
17 : : #define RTE_LOGTYPE_TEST_BPF_VALIDATE test_bpf_validate_logtype
18 : : #define TEST_LOG_LINE(level, ...) \
19 : : RTE_LOG_LINE(level, TEST_BPF_VALIDATE, "" __VA_ARGS__)
20 : :
21 [ - + ]: 303 : RTE_LOG_REGISTER(test_bpf_validate_logtype, test.bpf_validate, NOTICE);
22 : :
23 : : /* Special value indicating that program counter variable is not being used. */
24 : : #define NO_PROGRAM_COUNTER UINT32_MAX
25 : :
26 : : /* Special value indicating that register variable is not being used. */
27 : : #define NO_REGISTER UINT8_MAX
28 : :
29 : : /* Sizes of text buffers used for formatting various debug outputs. */
30 : : #define VALUE_FORMAT_BUFFER_SIZE 32
31 : : #define INTERVAL_FORMAT_BUFFER_SIZE 64
32 : : #define REGISTER_FORMAT_BUFFER_SIZE 256
33 : : #define DISASSEMBLY_FORMAT_BUFFER_SIZE 64
34 : :
35 : : #define COMPARISON_INDEX_IMMEDIATE RTE_BIT32(0)
36 : : #define COMPARISON_INDEX_GREATER RTE_BIT32(1)
37 : : #define COMPARISON_INDEX_INCLUSIVE RTE_BIT32(2)
38 : : #define COMPARISON_INDEX_SIGNED RTE_BIT32(3)
39 : :
40 : : /* List comparison opcodes to make their index bits match constants above. */
41 : : static const uint8_t comparisons_opcode[] = {
42 : : (BPF_JMP | EBPF_JLT | BPF_X),
43 : : (BPF_JMP | EBPF_JLT | BPF_K),
44 : : (BPF_JMP | BPF_JGT | BPF_X),
45 : : (BPF_JMP | BPF_JGT | BPF_K),
46 : : (BPF_JMP | EBPF_JLE | BPF_X),
47 : : (BPF_JMP | EBPF_JLE | BPF_K),
48 : : (BPF_JMP | BPF_JGE | BPF_X),
49 : : (BPF_JMP | BPF_JGE | BPF_K),
50 : : (BPF_JMP | EBPF_JSLT | BPF_X),
51 : : (BPF_JMP | EBPF_JSLT | BPF_K),
52 : : (BPF_JMP | EBPF_JSGT | BPF_X),
53 : : (BPF_JMP | EBPF_JSGT | BPF_K),
54 : : (BPF_JMP | EBPF_JSLE | BPF_X),
55 : : (BPF_JMP | EBPF_JSLE | BPF_K),
56 : : (BPF_JMP | EBPF_JSGE | BPF_X),
57 : : (BPF_JMP | EBPF_JSGE | BPF_K),
58 : : };
59 : :
60 : : /* Interval bounded by two signed values, inclusive; min <= max. */
61 : : struct signed_interval {
62 : : int64_t min;
63 : : int64_t max;
64 : : };
65 : :
66 : : /* Interval bounded by two unsigned values, inclusive; min <= max. */
67 : : struct unsigned_interval {
68 : : uint64_t min;
69 : : uint64_t max;
70 : : };
71 : :
72 : : /*
73 : : * Expected interval of register values.
74 : : *
75 : : * If `is_defined` is not set, domain is considered to be unused in verification
76 : : * parameters (instruction is not accessing corresponding register).
77 : : * It's not the same as `unknown` domain which describes register that is being
78 : : * used but can hold any value.
79 : : *
80 : : * Flag `is_pointer` tells if the interval is relative to some memory area base.
81 : : */
82 : : struct domain {
83 : : bool is_defined;
84 : : bool is_pointer;
85 : : struct signed_interval s;
86 : : struct unsigned_interval u;
87 : : };
88 : :
89 : : /* Expected validation state at certain point. */
90 : : struct state {
91 : : /* Specifies that the branch is dynamically unreachable. */
92 : : bool is_unreachable;
93 : : struct domain dst;
94 : : struct domain src;
95 : : };
96 : :
97 : : /* Instruction verification parameters. */
98 : : struct verify_instruction_param {
99 : : struct ebpf_insn tested_instruction;
100 : : size_t area_size;
101 : : /* States just before the tested instruction, just after, or if jumped. */
102 : : struct state pre;
103 : : struct state post;
104 : : struct state jump;
105 : : };
106 : :
107 : : /* Point (pre/post/jump) specific verification context. */
108 : : struct point_context {
109 : : uint32_t program_counter;
110 : : uint32_t hit_count;
111 : : char formatted_dst[REGISTER_FORMAT_BUFFER_SIZE];
112 : : char formatted_src[REGISTER_FORMAT_BUFFER_SIZE];
113 : : };
114 : :
115 : : /* Verification context. */
116 : : struct verify_instruction_context {
117 : : struct verify_instruction_param prm;
118 : : /* Allocation of registers in the generated program. */
119 : : uint8_t base_reg;
120 : : uint8_t dst_reg;
121 : : uint8_t src_reg;
122 : : uint8_t tmp_reg;
123 : : /* Number of times invalid state callback was called. */
124 : : uint32_t invalid_state_count;
125 : : /* Contexts just before the tested instruction, just after, or if jumped. */
126 : : struct point_context pre;
127 : : struct point_context post;
128 : : struct point_context jump;
129 : : };
130 : :
131 : : /* Domain with both signed and unsigned interval having maximum size. */
132 : : static const struct domain unknown = {
133 : : .is_defined = true,
134 : : .s = { .min = INT64_MIN, .max = INT64_MAX },
135 : : .u = { .min = 0, .max = UINT64_MAX },
136 : : };
137 : :
138 : : /* Unreachable state. */
139 : : static const struct state unreachable = {
140 : : .is_unreachable = true,
141 : : };
142 : :
143 : :
144 : : /* BUILDING DOMAINS */
145 : :
146 : : /* Create domain from singleton interval. */
147 : : static struct domain
148 : : make_singleton_domain(uint64_t value)
149 : : {
150 : 60 : return (struct domain){
151 : : .is_defined = true,
152 : : .s = { .min = value, .max = value },
153 : : .u = { .min = value, .max = value },
154 : : };
155 : : }
156 : :
157 : : /* Create domain from signed interval. */
158 : : static struct domain
159 : 60 : make_signed_domain(int64_t min, int64_t max)
160 : : {
161 [ - + ]: 60 : RTE_VERIFY(min <= max);
162 : 107 : return (struct domain){
163 : : .is_defined = true,
164 : : .s = { .min = min, .max = max },
165 : 60 : .u = (min ^ max) >= 0 ?
166 [ + + ]: 60 : (struct unsigned_interval){ .min = min, .max = max } :
167 : : unknown.u,
168 : : };
169 : : }
170 : :
171 : : /* Create domain from unsigned interval. */
172 : : static struct domain
173 : 39 : make_unsigned_domain(uint64_t min, uint64_t max)
174 : : {
175 [ - + ]: 39 : RTE_VERIFY(min <= max);
176 : 59 : return (struct domain){
177 : : .is_defined = true,
178 : 39 : .s = (int64_t)(min ^ max) >= 0 ?
179 [ + + ]: 39 : (struct signed_interval){ .min = min, .max = max } :
180 : : unknown.s,
181 : : .u = { .min = min, .max = max },
182 : : };
183 : : }
184 : :
185 : : /* Create domain from signed interval. */
186 : : static struct domain
187 : : make_pointer_domain(int64_t min, int64_t max)
188 : : {
189 : 9 : struct domain result = make_signed_domain(min, max);
190 : : result.is_pointer = true;
191 : 4 : return result;
192 : : }
193 : :
194 : : /* Return true if domain is a scalar or pointer singleton. */
195 : : static bool
196 : : domain_is_singleton(const struct domain *domain)
197 : : {
198 : 1583 : return domain->s.min == domain->s.max &&
199 [ + + + - : 629 : (uint64_t)domain->s.max == domain->u.min &&
+ - + - +
- + - +
- ]
200 [ - + - + : 389 : domain->u.min == domain->u.max;
- + - + ]
201 : : }
202 : :
203 : : /* Print error message into buffer if rc signifies error or overflow. */
204 : : static void
205 : 1833 : handle_format_errors(char *buffer, size_t bufsz, int rc)
206 : : {
207 [ - + ]: 1833 : if (rc < 0)
208 : 0 : snprintf(buffer, bufsz, "FORMAT ERROR %d!", -rc);
209 [ - + ]: 1833 : else if ((unsigned int)rc >= bufsz)
210 : : snprintf(buffer, bufsz, "FORMAT OVERFLOW!");
211 : 1833 : }
212 : :
213 : : /* Format register information into provided buffer and return the buffer. */
214 : : static const char *
215 : : format_value(char *buffer, size_t bufsz, char format, uint64_t value)
216 : : {
217 : 0 : handle_format_errors(buffer, bufsz,
218 : : rte_bpf_validate_debug_format_value(buffer, bufsz, format, value));
219 : : return buffer;
220 : : }
221 : :
222 : : /* Format register information into provided buffer and return the buffer. */
223 : : static const char *
224 : : format_interval(char *buffer, size_t bufsz, char format, uint64_t min, uint64_t max)
225 : : {
226 : 0 : handle_format_errors(buffer, bufsz,
227 : : rte_bpf_validate_debug_format_interval(buffer, bufsz, format, min, max));
228 : : return buffer;
229 : : }
230 : :
231 : : /* Format domain information into provided buffer and return the buffer. */
232 : : static const char *
233 : 0 : format_domain(char *buffer, size_t bufsz, const struct domain *domain)
234 : : {
235 : : char signed_buffer[INTERVAL_FORMAT_BUFFER_SIZE];
236 : : char unsigned_buffer[INTERVAL_FORMAT_BUFFER_SIZE];
237 : :
238 : 0 : const int rc = !domain->is_defined ?
239 [ # # ]: 0 : snprintf(buffer, bufsz, "UNDEFINED") :
240 : 0 : snprintf(buffer, bufsz, "%s %s INTERSECT %s",
241 [ # # ]: 0 : domain->is_pointer ? "pointer" : "scalar",
242 : : format_interval(signed_buffer, sizeof(signed_buffer), 'd',
243 : 0 : domain->s.min, domain->s.max),
244 : : format_interval(unsigned_buffer, sizeof(unsigned_buffer), 'x',
245 : 0 : domain->u.min, domain->u.max));
246 : :
247 [ # # ]: 0 : handle_format_errors(buffer, bufsz, rc < 0 ? -errno : rc);
248 : :
249 : 0 : return buffer;
250 : : }
251 : :
252 : : /* Format register information into provided buffer and return the buffer. */
253 : : static const char *
254 : 1833 : format_register(struct rte_bpf_validate_debug *debug, char *buffer, size_t bufsz, uint8_t reg)
255 : : {
256 : 1833 : handle_format_errors(buffer, bufsz,
257 : : rte_bpf_validate_debug_format_register_info(debug, buffer, bufsz, reg));
258 : 1833 : return buffer;
259 : : }
260 : :
261 : :
262 : : /* CHECKING REGISTER ACTUAL DOMAINS */
263 : :
264 : : /* Return true the specified conditional jump _may_ occur at current state. */
265 : : static bool
266 : 14608 : may_jump(const struct rte_bpf_validate_debug *debug,
267 : : const struct ebpf_insn *jump, uint64_t imm64)
268 : : {
269 : 14608 : const int result = rte_bpf_validate_debug_may_jump(debug, jump, imm64);
270 [ - + ]: 14608 : RTE_VERIFY(result >= 0);
271 : 14608 : return (result & RTE_BPF_VALIDATE_DEBUG_MAY_BE_TRUE) != 0;
272 : : }
273 : :
274 : : /* Check interval of the register interpreted as signed scalar. */
275 : : static int
276 : 1820 : check_signed_interval(struct rte_bpf_validate_debug *debug,
277 : : uint8_t reg, struct signed_interval interval)
278 : : {
279 : : char buffer[VALUE_FORMAT_BUFFER_SIZE];
280 : :
281 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
282 : : &(struct ebpf_insn){
283 : : .code = (BPF_JMP | EBPF_JSLT | BPF_K),
284 : : .dst_reg = reg,
285 : : }, interval.min),
286 : : false,
287 : : "r%hhu s< %s is impossible", reg,
288 : : format_value(buffer, sizeof(buffer), 'd', interval.min));
289 : :
290 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
291 : : &(struct ebpf_insn){
292 : : .code = (BPF_JMP | BPF_JEQ | BPF_K),
293 : : .dst_reg = reg,
294 : : }, interval.min),
295 : : true,
296 : : "r%hhu == %s is possible", reg,
297 : : format_value(buffer, sizeof(buffer), 'd', interval.min));
298 : :
299 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
300 : : &(struct ebpf_insn){
301 : : .code = (BPF_JMP | BPF_JEQ | BPF_K),
302 : : .dst_reg = reg,
303 : : }, interval.max),
304 : : true,
305 : : "r%hhu == %s is possible", reg,
306 : : format_value(buffer, sizeof(buffer), 'd', interval.max));
307 : :
308 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
309 : : &(struct ebpf_insn){
310 : : .code = (BPF_JMP | EBPF_JSGT | BPF_K),
311 : : .dst_reg = reg,
312 : : }, interval.max),
313 : : false,
314 : : "r%hhu s> %s is impossible", reg,
315 : : format_value(buffer, sizeof(buffer), 'd', interval.max));
316 : :
317 : 1820 : return TEST_SUCCESS;
318 : : }
319 : :
320 : : /* Check interval of the register interpreted as unsigned scalar. */
321 : : static int
322 : 1820 : check_unsigned_interval(struct rte_bpf_validate_debug *debug,
323 : : uint8_t reg, struct unsigned_interval interval)
324 : : {
325 : : char buffer[VALUE_FORMAT_BUFFER_SIZE];
326 : :
327 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
328 : : &(struct ebpf_insn){
329 : : .code = (BPF_JMP | EBPF_JLT | BPF_K),
330 : : .dst_reg = reg,
331 : : }, interval.min),
332 : : false,
333 : : "r%hhu u< %s is impossible", reg,
334 : : format_value(buffer, sizeof(buffer), 'x', interval.min));
335 : :
336 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
337 : : &(struct ebpf_insn){
338 : : .code = (BPF_JMP | BPF_JEQ | BPF_K),
339 : : .dst_reg = reg,
340 : : }, interval.min),
341 : : true,
342 : : "r%hhu == %s is possible", reg,
343 : : format_value(buffer, sizeof(buffer), 'x', interval.min));
344 : :
345 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
346 : : &(struct ebpf_insn){
347 : : .code = (BPF_JMP | BPF_JEQ | BPF_K),
348 : : .dst_reg = reg,
349 : : }, interval.max),
350 : : true,
351 : : "r%hhu == %s is possible", reg,
352 : : format_value(buffer, sizeof(buffer), 'x', interval.max));
353 : :
354 [ - + ]: 1820 : TEST_ASSERT_EQUAL(may_jump(debug,
355 : : &(struct ebpf_insn){
356 : : .code = (BPF_JMP | BPF_JGT | BPF_K),
357 : : .dst_reg = reg,
358 : : }, interval.max),
359 : : false,
360 : : "r%hhu u> %s is impossible", reg,
361 : : format_value(buffer, sizeof(buffer), 'x', interval.max));
362 : :
363 : 1820 : return TEST_SUCCESS;
364 : : }
365 : :
366 : : /* Check interval of the register relative to the base register. */
367 : : static int
368 : 12 : check_relative_interval(struct rte_bpf_validate_debug *debug,
369 : : uint8_t reg, struct signed_interval interval, uint8_t base_reg)
370 : : {
371 : : char buffer[VALUE_FORMAT_BUFFER_SIZE];
372 : :
373 [ - + ]: 12 : TEST_ASSERT_EQUAL(may_jump(debug,
374 : : &(struct ebpf_insn){
375 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
376 : : .dst_reg = reg,
377 : : .src_reg = base_reg,
378 : : }, interval.min),
379 : : false,
380 : : "r%hhu u< r%hhu + %s is impossible", reg, base_reg,
381 : : format_value(buffer, sizeof(buffer), 'd', interval.min));
382 : :
383 [ - + ]: 12 : TEST_ASSERT_EQUAL(may_jump(debug,
384 : : &(struct ebpf_insn){
385 : : .code = (BPF_JMP | BPF_JEQ | BPF_X),
386 : : .dst_reg = reg,
387 : : .src_reg = base_reg,
388 : : }, interval.min),
389 : : true,
390 : : "r%hhu == r%hhu + %s is possible", reg, base_reg,
391 : : format_value(buffer, sizeof(buffer), 'd', interval.min));
392 : :
393 [ - + ]: 12 : TEST_ASSERT_EQUAL(may_jump(debug,
394 : : &(struct ebpf_insn){
395 : : .code = (BPF_JMP | BPF_JEQ | BPF_X),
396 : : .dst_reg = reg,
397 : : .src_reg = base_reg,
398 : : }, interval.max),
399 : : true,
400 : : "r%hhu == r%hhu + %s is possible", reg, base_reg,
401 : : format_value(buffer, sizeof(buffer), 'd', interval.max));
402 : :
403 [ - + ]: 12 : TEST_ASSERT_EQUAL(may_jump(debug,
404 : : &(struct ebpf_insn){
405 : : .code = (BPF_JMP | BPF_JGT | BPF_X),
406 : : .dst_reg = reg,
407 : : .src_reg = base_reg,
408 : : }, interval.max),
409 : : false,
410 : : "r%hhu u> r%hhu + %s is impossible", reg, base_reg,
411 : : format_value(buffer, sizeof(buffer), 'd', interval.max));
412 : :
413 : 12 : return TEST_SUCCESS;
414 : : }
415 : :
416 : : /*
417 : : * Check access of the register interpreted as pointer.
418 : : *
419 : : * Unlike other similar functions, min > max is not a problem here,
420 : : * so either signed or unsigned pair can be passed without any issues.
421 : : *
422 : : * This is the reason we are not using signed_interval or unsigned_interval here
423 : : * to avoid confusion.
424 : : */
425 : : static int
426 : 24 : check_pointer_access(struct rte_bpf_validate_debug *debug, uint8_t reg,
427 : : uint64_t min, uint64_t max, size_t area_size)
428 : : {
429 : : char buffer[VALUE_FORMAT_BUFFER_SIZE];
430 : :
431 : : /* Start and end of the valid offsets window (unless empty). */
432 : 24 : const uint64_t window_begin = -min;
433 : 24 : const uint64_t window_end = area_size - max;
434 : :
435 : : /* Only have accessible bytes if the interval is smaller than the area. */
436 : 24 : const uint64_t interval_size = max - min;
437 : : const bool window_empty = (interval_size >= area_size);
438 : :
439 [ - + ]: 24 : TEST_ASSERT_EQUAL(rte_bpf_validate_debug_can_access(debug,
440 : : &(struct ebpf_insn){
441 : : .code = (BPF_LDX | BPF_B | BPF_MEM),
442 : : .src_reg = reg
443 : : }, window_begin - 1),
444 : : false,
445 : : "r%hhu + %s (before window begin) dereference is invalid", reg,
446 : : format_value(buffer, sizeof(buffer), 'd', window_begin - 1));
447 : :
448 [ - + - - ]: 24 : TEST_ASSERT_EQUAL(rte_bpf_validate_debug_can_access(debug,
449 : : &(struct ebpf_insn){
450 : : .code = (BPF_LDX | BPF_B | BPF_MEM),
451 : : .src_reg = reg
452 : : }, window_begin),
453 : : !window_empty,
454 : : "r%hhu + %s (after window begin) dereference is %s", reg,
455 : : format_value(buffer, sizeof(buffer), 'd', window_begin),
456 : : window_empty ? "invalid for empty window" : "valid");
457 : :
458 [ - + - - ]: 24 : TEST_ASSERT_EQUAL(rte_bpf_validate_debug_can_access(debug,
459 : : &(struct ebpf_insn){
460 : : .code = (BPF_LDX | BPF_B | BPF_MEM),
461 : : .src_reg = reg
462 : : }, window_end - 1),
463 : : !window_empty,
464 : : "r%hhu + %s (before window end) dereference is %s", reg,
465 : : format_value(buffer, sizeof(buffer), 'd', window_end - 1),
466 : : window_empty ? "invalid for empty window" : "valid");
467 : :
468 [ - + ]: 24 : TEST_ASSERT_EQUAL(rte_bpf_validate_debug_can_access(debug,
469 : : &(struct ebpf_insn){
470 : : .code = (BPF_LDX | BPF_B | BPF_MEM),
471 : : .src_reg = reg
472 : : }, window_end),
473 : : false,
474 : : "r%hhu + %s (after window end) dereference is invalid", reg,
475 : : format_value(buffer, sizeof(buffer), 'd', window_end));
476 : :
477 : 24 : return TEST_SUCCESS;
478 : : }
479 : :
480 : : /* Check domain of the register interpreted as absolute value. */
481 : : static int
482 : 1820 : check_scalar_domain(struct rte_bpf_validate_debug *debug, uint8_t reg,
483 : : const struct domain *domain)
484 : : {
485 [ - + ]: 1820 : TEST_ASSERT_SUCCESS(
486 : : check_signed_interval(debug, reg, domain->s),
487 : : "absolute signed interval check");
488 : :
489 [ - + ]: 1820 : TEST_ASSERT_SUCCESS(
490 : : check_unsigned_interval(debug, reg, domain->u),
491 : : "absolute unsigned interval check");
492 : :
493 : : return TEST_SUCCESS;
494 : : }
495 : :
496 : : /* Check domain of the register interpreted as relative pointer. */
497 : : static int
498 : 12 : check_pointer_domain(struct rte_bpf_validate_debug *debug, uint8_t reg,
499 : : const struct domain *domain, uint8_t base_reg, size_t area_size)
500 : : {
501 [ - + ]: 12 : TEST_ASSERT_SUCCESS(
502 : : check_relative_interval(debug, reg, domain->s, base_reg),
503 : : "relative interval check");
504 : :
505 [ - + ]: 12 : TEST_ASSERT_SUCCESS(
506 : : check_pointer_access(debug, reg, domain->s.min, domain->s.max,
507 : : area_size),
508 : : "pointer signed access check");
509 : :
510 [ - + ]: 12 : TEST_ASSERT_SUCCESS(
511 : : check_pointer_access(debug, reg, domain->u.min, domain->u.max,
512 : : area_size),
513 : : "pointer unsigned access check");
514 : :
515 : : return TEST_SUCCESS;
516 : : }
517 : :
518 : : /* Check domain of the register and format the values in case of an error. */
519 : : static int
520 : 1832 : check_domain(struct rte_bpf_validate_debug *debug, uint8_t reg,
521 : : const struct domain *domain, uint8_t base_reg, size_t area_size)
522 : : {
523 : : char buffer[REGISTER_FORMAT_BUFFER_SIZE];
524 : :
525 : 1832 : const int rc = domain->is_pointer ?
526 [ + + ]: 1832 : check_pointer_domain(debug, reg, domain, base_reg, area_size) :
527 : 1820 : check_scalar_domain(debug, reg, domain);
528 : :
529 [ - + ]: 1832 : if (rc != TEST_SUCCESS) {
530 : 0 : TEST_LOG_LINE(WARNING, "\tExpected: r%hhu = %s", reg,
531 : : format_domain(buffer, sizeof(buffer), domain));
532 : :
533 : 0 : TEST_LOG_LINE(WARNING, "\tFound: r%hhu = %s", reg,
534 : : format_register(debug, buffer, sizeof(buffer), reg));
535 : : }
536 : :
537 : 1832 : return rc;
538 : : }
539 : :
540 : :
541 : : /* GENERATING TEST PROGRAM */
542 : :
543 : : static bool
544 : : fits_in_imm32(int64_t value)
545 : : {
546 : 2406 : return value >= INT32_MIN && value <= INT32_MAX;
547 : : }
548 : :
549 : : /* Load constant into the register. */
550 : : static void
551 : 262 : load_constant(struct ebpf_insn **ins, uint8_t reg, int64_t value)
552 : : {
553 [ + + ]: 262 : if (fits_in_imm32(value)) {
554 : 1296 : *(*ins)++ = (struct ebpf_insn){
555 : : .code = (EBPF_ALU64 | EBPF_MOV | BPF_K),
556 : : .dst_reg = reg,
557 : 144 : .imm = (int32_t)value,
558 : : };
559 : : } else {
560 : : /* Load imm64 into tmp_reg using wide load, lower bits first... */
561 : 118 : *(*ins)++ = (struct ebpf_insn){
562 : : .code = (BPF_LD | BPF_IMM | EBPF_DW),
563 : : .dst_reg = reg,
564 : 118 : .imm = (uint32_t)value,
565 : : };
566 : : /* ... then higher bits. */
567 : 118 : *(*ins)++ = (struct ebpf_insn){
568 : 118 : .imm = (uint32_t)(value >> 32),
569 : : };
570 : : }
571 : 262 : }
572 : :
573 : : /*
574 : : * Compare specified register to value and jump.
575 : : *
576 : : * Jump offset is not filled and should be patched in by the caller.
577 : : */
578 : : static void
579 : 2126 : compare_and_jump(struct ebpf_insn **ins, uint8_t op, uint8_t reg,
580 : : int64_t value, uint8_t tmp_reg)
581 : : {
582 [ + + ]: 2126 : if (fits_in_imm32(value)) {
583 : : /* Jump on specified condition between reg and immediate. */
584 : 2061 : *(*ins)++ = (struct ebpf_insn){
585 : : .code = (BPF_JMP | op | BPF_K),
586 : : .dst_reg = reg,
587 : 2061 : .imm = (int32_t)value,
588 : : };
589 : : } else {
590 : : /* Load value into tmp_reg. */
591 : 65 : load_constant(ins, tmp_reg, value);
592 : :
593 : : /* Jump on specified condition between reg and tmp_reg. */
594 : 65 : *(*ins)++ = (struct ebpf_insn){
595 : : .code = (BPF_JMP | op | BPF_X),
596 : : .dst_reg = reg,
597 : : .src_reg = tmp_reg,
598 : : };
599 : : }
600 : 2126 : }
601 : :
602 : : /*
603 : : * Prepare register to be in the specified scalar domain.
604 : : *
605 : : * Unless singleton, load unknown value into it and clamp it with conditional jumps.
606 : : * (Jump offsets are not filled and should be patched in by the caller.)
607 : : */
608 : : static void
609 [ + + ]: 762 : prepare_scalar_domain(struct ebpf_insn **ins, uint8_t reg,
610 : : const struct domain *domain, uint8_t base_reg, int *service_cell_count,
611 : : uint8_t tmp_reg)
612 : : {
613 [ + + ]: 762 : if (domain_is_singleton(domain)) {
614 : : /* Don't need any uncertainty for a singleton. */
615 : 197 : load_constant(ins, reg, domain->s.min);
616 : : return;
617 : : }
618 : :
619 : : /* Load value from memory area into the register. */
620 : 565 : *(*ins)++ = (struct ebpf_insn){
621 : : .code = (BPF_LDX | EBPF_DW | BPF_MEM),
622 : : .dst_reg = reg,
623 : : .src_reg = base_reg,
624 : 565 : .off = sizeof(uint64_t) * (*service_cell_count)++,
625 : : };
626 : :
627 : : /*
628 : : * Use both signed and unsigned conditions, even if redundant.
629 : : * It makes it more robust if conditional jump verification itself
630 : : * contains bugs like not updating the other type of interval.
631 : : * Jump instructions themselves can be tested separately to catch
632 : : * these bugs, this preparation phase is not a test for them.
633 : : */
634 [ + + ]: 565 : if (domain->u.min > unknown.u.min)
635 : 522 : compare_and_jump(ins, EBPF_JLT, reg, domain->u.min, tmp_reg);
636 [ + + ]: 565 : if (domain->u.max < unknown.u.max)
637 : 548 : compare_and_jump(ins, BPF_JGT, reg, domain->u.max, tmp_reg);
638 [ + + ]: 565 : if (domain->s.min > unknown.s.min)
639 : 522 : compare_and_jump(ins, EBPF_JSLT, reg, domain->s.min, tmp_reg);
640 [ + + ]: 565 : if (domain->s.max < unknown.s.max)
641 : 534 : compare_and_jump(ins, EBPF_JSGT, reg, domain->s.max, tmp_reg);
642 : : }
643 : :
644 : : /*
645 : : * Prepare register to be in the specified scalar or pointer domain, if any.
646 : : *
647 : : * If `domain` is NULL, do nothing. Otherwise prepare scalar domain,
648 : : * and then add base register to it to convert it to a pointer, if needed.
649 : : */
650 : : static void
651 : 762 : prepare_domain(struct ebpf_insn **ins, uint8_t reg,
652 : : const struct domain *domain, uint8_t base_reg, int *service_cell_count,
653 : : uint8_t tmp_reg)
654 : : {
655 : 762 : prepare_scalar_domain(ins, reg, domain, base_reg, service_cell_count, tmp_reg);
656 : :
657 [ + + ]: 762 : if (domain->is_pointer)
658 : : /* Add base_reg to convert resulting scalar into a pointer. */
659 : 6 : *(*ins)++ = (struct ebpf_insn){
660 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_X),
661 : : .dst_reg = reg,
662 : : .src_reg = base_reg,
663 : : };
664 : 762 : }
665 : :
666 : : static void
667 : 454 : fill_verify_instruction_defaults(struct verify_instruction_param *prm)
668 : : {
669 : :
670 [ + + ]: 454 : if (BPF_CLASS(prm->tested_instruction.code) != BPF_JMP)
671 : 90 : prm->jump.is_unreachable = true;
672 : :
673 [ - + ]: 454 : RTE_VERIFY(!prm->pre.is_unreachable);
674 [ + + ]: 454 : if (prm->post.is_unreachable) {
675 [ - + ]: 90 : RTE_VERIFY(!prm->post.dst.is_defined);
676 [ - + ]: 90 : RTE_VERIFY(!prm->post.src.is_defined);
677 : : } else {
678 [ + + ]: 364 : if (!prm->post.dst.is_defined)
679 : 20 : prm->post.dst = prm->pre.dst;
680 [ + + ]: 364 : if (!prm->post.src.is_defined)
681 : 133 : prm->post.src = prm->pre.src;
682 : : }
683 : :
684 [ + + ]: 454 : if (prm->jump.is_unreachable) {
685 [ - + ]: 184 : RTE_VERIFY(!prm->jump.dst.is_defined);
686 [ - + ]: 184 : RTE_VERIFY(!prm->jump.src.is_defined);
687 : : } else {
688 [ + + ]: 270 : if (!prm->jump.dst.is_defined)
689 : 16 : prm->jump.dst = prm->pre.dst;
690 [ + + ]: 270 : if (!prm->jump.src.is_defined)
691 : 39 : prm->jump.src = prm->pre.src;
692 : : }
693 : 454 : }
694 : :
695 : : /* Generate program for the tested instruction and domains from the context.
696 : : *
697 : : * Return number of instructions.
698 : : *
699 : : * Destination and source registers in tested_instruction should not be specified,
700 : : * they are filled in by the function as long as domains for them are specified.
701 : : * Jump offset should not be specified, it is filled in by the function.
702 : : *
703 : : * If `pre.dst` or `pre.src` domain is not defined, corresponding register
704 : : * is not prepared.
705 : : *
706 : : * For non-jump instructions `jump.is_unreachable` is always set automatically.
707 : : *
708 : : * If any of the post or jump domains are not defined, they are copied from src
709 : : * unless corresponding branch is unreachable.
710 : : *
711 : : * Memory area size is automatically expanded to have enough space for loading
712 : : * unknown dst and src register values, thus testing sizes less than 16 bytes is
713 : : * not guaranteed.
714 : : *
715 : : * Limitations:
716 : : * - Support for jump instructions is incomplete (e.g. exit, ja).
717 : : * - Wide instructions are not supported yet.
718 : : */
719 : : static uint32_t
720 : 414 : generate_program(struct verify_instruction_context *ctx, struct ebpf_insn *ins)
721 : : {
722 : 414 : struct ebpf_insn *const ins_buf = ins;
723 : : /* Number of double words used for service purposes. */
724 : 414 : int service_cell_count = 0;
725 : :
726 : : /* Make sure we actually support provided instruction. */
727 [ - + ]: 414 : switch (BPF_CLASS(ctx->prm.tested_instruction.code)) {
728 : 0 : case BPF_LD:
729 : : /* Wide instructions are not supported yet. */
730 [ # # ]: 0 : RTE_VERIFY(!rte_bpf_insn_is_wide(&ctx->prm.tested_instruction));
731 : : break;
732 : : }
733 : :
734 : 414 : fill_verify_instruction_defaults(&ctx->prm);
735 : :
736 : : /* Allocate registers, base_reg is received as program argument. */
737 : 414 : ctx->base_reg = EBPF_REG_1;
738 [ + + - + ]: 414 : ctx->dst_reg = (ctx->prm.pre.dst.is_defined || ctx->prm.post.dst.is_defined ||
739 [ # # ]: 0 : ctx->prm.jump.dst.is_defined) ? EBPF_REG_2 : NO_REGISTER;
740 [ + + + - ]: 414 : ctx->src_reg = (ctx->prm.pre.src.is_defined || ctx->prm.post.src.is_defined ||
741 [ + - ]: 65 : ctx->prm.jump.src.is_defined) ? EBPF_REG_3 : NO_REGISTER;
742 : 414 : ctx->tmp_reg = EBPF_REG_4;
743 : :
744 : : /* Clear r0 to make it eligible as a return value. */
745 : : load_constant(&ins, EBPF_REG_0, 0);
746 : :
747 : : /* Fill dst register in the instruction if defined anywhere, prepare if needed. */
748 [ + - ]: 414 : if (ctx->dst_reg != NO_REGISTER) {
749 [ - + ]: 414 : RTE_VERIFY(ctx->prm.tested_instruction.dst_reg == 0);
750 : 414 : ctx->prm.tested_instruction.dst_reg = ctx->dst_reg;
751 : :
752 [ + + ]: 414 : if (ctx->prm.pre.dst.is_defined)
753 : 413 : prepare_domain(&ins, ctx->dst_reg, &ctx->prm.pre.dst,
754 : 413 : ctx->base_reg, &service_cell_count, ctx->tmp_reg);
755 : : else
756 : 1 : TEST_LOG_LINE(DEBUG, "Not preparing undefined r%hhu", ctx->dst_reg);
757 : : }
758 : :
759 : : /* Fill src register in the instruction if defined anywhere, prepare if needed. */
760 [ + + ]: 414 : if (ctx->src_reg != NO_REGISTER) {
761 [ - + ]: 349 : RTE_VERIFY(ctx->prm.tested_instruction.src_reg == 0);
762 : 349 : ctx->prm.tested_instruction.src_reg = ctx->src_reg;
763 : :
764 [ + - ]: 349 : if (ctx->prm.pre.src.is_defined)
765 : 349 : prepare_domain(&ins, ctx->src_reg, &ctx->prm.pre.src,
766 : 349 : ctx->base_reg, &service_cell_count, ctx->tmp_reg);
767 : : else
768 : 0 : TEST_LOG_LINE(DEBUG, "Not preparing undefined r%hhu", ctx->src_reg);
769 : : }
770 : :
771 : : /* Automatically increase area size if needed. */
772 : 414 : ctx->prm.area_size = RTE_MAX(ctx->prm.area_size, service_cell_count * sizeof(uint64_t));
773 : :
774 : : /* Issue tested instruction. */
775 : 414 : ctx->pre.program_counter = ins - ins_buf;
776 : 414 : *ins++ = ctx->prm.tested_instruction;
777 : :
778 : : /* Issue post instruction (for setting post breakpoint). */
779 : 414 : ctx->post.program_counter = ins - ins_buf;
780 : : load_constant(&ins, EBPF_REG_0, 1);
781 : :
782 : : /* Issue jump branch for the jump instruction, even if dynamically unreachable. */
783 [ + + ]: 414 : if (BPF_CLASS(ctx->prm.tested_instruction.code) != BPF_JMP)
784 : 90 : ctx->jump.program_counter = NO_PROGRAM_COUNTER;
785 : : else {
786 : : /* Finish previous branch by issuing exit. */
787 : 324 : *ins++ = (struct ebpf_insn){ .code = (BPF_JMP | EBPF_EXIT) };
788 : :
789 : : /* Issue jump target instruction (for setting jump breakpoint). */
790 : 324 : ctx->jump.program_counter = ins - ins_buf;
791 : : load_constant(&ins, EBPF_REG_0, 2);
792 : :
793 : : /* Patch jump in tested jump instruction. */
794 [ - + ]: 324 : RTE_VERIFY(ins_buf[ctx->pre.program_counter].off == 0);
795 : 324 : ins_buf[ctx->pre.program_counter].off =
796 : 324 : ctx->jump.program_counter - ctx->post.program_counter;
797 : : }
798 : :
799 : : /* Issue exit instruction. */
800 : 414 : const uint32_t exit_pc = ins - ins_buf;
801 : 414 : *ins++ = (struct ebpf_insn){ .code = (BPF_JMP | EBPF_EXIT) };
802 : :
803 : : /* Patch all jumps to point to exit. */
804 [ + + ]: 3905 : for (uint32_t pc = 0; pc != ctx->pre.program_counter; ++pc)
805 [ + + ]: 3491 : if (BPF_CLASS(ins_buf[pc].code) == BPF_JMP) {
806 : : RTE_ASSERT(ins_buf[pc].off == 0);
807 : 2126 : ins_buf[pc].off = exit_pc - (pc + 1);
808 : : }
809 : :
810 : 414 : const uint32_t nb_ins = ins - ins_buf;
811 : 414 : return nb_ins;
812 : : }
813 : :
814 : :
815 : : /* VERIFICATION OF AN ARBITRARY INSTRUCTION */
816 : :
817 : : /* Invoked when invalid state is detected. */
818 : : static int
819 : 5160 : invalid_state_cb(struct rte_bpf_validate_debug *debug, void *void_ctx)
820 : : {
821 : : struct verify_instruction_context *const ctx = void_ctx;
822 : :
823 : 5160 : ++ctx->invalid_state_count;
824 : :
825 : 5160 : TEST_LOG_LINE(WARNING,
826 : : "Invalid state detected at pc %u",
827 : : rte_bpf_validate_debug_get_pc(debug));
828 : :
829 : : RTE_SET_USED(debug);
830 : :
831 : 5160 : return TEST_SUCCESS;
832 : : }
833 : :
834 : : static int
835 : 990 : point_callback(struct rte_bpf_validate_debug *debug, const struct verify_instruction_context *ctx,
836 : : struct point_context *point_ctx, const struct state *state)
837 : : {
838 [ - + ]: 990 : TEST_ASSERT_EQUAL(point_ctx->hit_count, 0, "not called before");
839 : :
840 : 990 : const uint32_t pc = rte_bpf_validate_debug_get_pc(debug);
841 [ - + ]: 990 : TEST_ASSERT_EQUAL(pc, point_ctx->program_counter,
842 : : "Expected program counter: %" PRIu32 ", found: %" PRIu32,
843 : : point_ctx->program_counter, pc);
844 : :
845 [ + - ]: 990 : if (ctx->dst_reg != NO_REGISTER) {
846 : 990 : format_register(debug, point_ctx->formatted_dst,
847 : : sizeof(point_ctx->formatted_dst), ctx->dst_reg);
848 : :
849 [ + + ]: 990 : if (state->dst.is_defined) {
850 [ - + ]: 989 : TEST_ASSERT_SUCCESS(
851 : : check_domain(debug, ctx->dst_reg, &state->dst,
852 : : ctx->base_reg, ctx->prm.area_size),
853 : : "dst domain check");
854 : 989 : TEST_LOG_LINE(DEBUG, "Successfully checked r%hhu.", ctx->dst_reg);
855 : : } else
856 : 1 : TEST_LOG_LINE(DEBUG, "Not checking undefined r%hhu.", ctx->dst_reg);
857 : : }
858 : :
859 [ + + ]: 990 : if (ctx->src_reg != NO_REGISTER) {
860 : 843 : format_register(debug, point_ctx->formatted_src,
861 : : sizeof(point_ctx->formatted_src), ctx->src_reg);
862 : :
863 [ + - ]: 843 : if (state->src.is_defined) {
864 [ - + ]: 843 : TEST_ASSERT_SUCCESS(
865 : : check_domain(debug, ctx->src_reg, &state->src,
866 : : ctx->base_reg, ctx->prm.area_size),
867 : : "src domain check");
868 : 843 : TEST_LOG_LINE(DEBUG, "Successfully checked r%hhu.", ctx->src_reg);
869 : : } else
870 : 0 : TEST_LOG_LINE(DEBUG, "Not checking undefined r%hhu.", ctx->src_reg);
871 : : }
872 : :
873 : 990 : ++point_ctx->hit_count;
874 : :
875 : 990 : return TEST_SUCCESS;
876 : : }
877 : :
878 : : /*
879 : : * Invoked before the tested instruction and checks pre-conditions.
880 : : *
881 : : * Also formats registers in the pre state for postmortem, if needed.
882 : : */
883 : : static int
884 : 414 : pre_callback(struct rte_bpf_validate_debug *debug, void *void_ctx)
885 : : {
886 : : struct verify_instruction_context *const ctx = void_ctx;
887 : :
888 : 414 : TEST_LOG_LINE(DEBUG, "Pre callback invoked.");
889 : :
890 [ - + ]: 414 : TEST_ASSERT_SUCCESS(
891 : : point_callback(debug, ctx, &ctx->pre, &ctx->prm.pre),
892 : : "pre-state check");
893 : :
894 : : return TEST_SUCCESS;
895 : : }
896 : :
897 : : /* Invoked after the tested instruction and checks post-conditions. */
898 : : static int
899 : 333 : post_callback(struct rte_bpf_validate_debug *debug, void *void_ctx)
900 : : {
901 : : struct verify_instruction_context *const ctx = void_ctx;
902 : :
903 : 333 : TEST_LOG_LINE(DEBUG, "Post callback invoked.");
904 : :
905 [ - + ]: 333 : TEST_ASSERT_SUCCESS(
906 : : point_callback(debug, ctx, &ctx->post, &ctx->prm.post),
907 : : "post-state check");
908 : :
909 : : return TEST_SUCCESS;
910 : : }
911 : :
912 : : /* Invoked after the tested instruction jumped and checks jump post-conditions. */
913 : : static int
914 : 243 : jump_callback(struct rte_bpf_validate_debug *debug, void *void_ctx)
915 : : {
916 : : struct verify_instruction_context *const ctx = void_ctx;
917 : :
918 : 243 : TEST_LOG_LINE(DEBUG, "Jump callback invoked.");
919 : :
920 [ - + ]: 243 : TEST_ASSERT_SUCCESS(
921 : : point_callback(debug, ctx, &ctx->jump, &ctx->prm.jump),
922 : : "jump-state check");
923 : :
924 : : return TEST_SUCCESS;
925 : : }
926 : :
927 : : static int
928 : 414 : debug_validation(struct verify_instruction_context *ctx, const struct ebpf_insn *ins,
929 : : uint32_t nb_ins)
930 : : {
931 : 414 : struct rte_bpf_validate_debug *const debug = rte_bpf_validate_debug_create();
932 [ - + ]: 414 : TEST_ASSERT_NOT_NULL(debug, "validate debug create error %d", rte_errno);
933 : :
934 : 414 : const struct rte_bpf_prm_ex prm = {
935 : : .sz = sizeof(struct rte_bpf_prm_ex),
936 : : .origin = RTE_BPF_ORIGIN_RAW,
937 : : .raw.ins = ins,
938 : : .raw.nb_ins = nb_ins,
939 : : .prog_arg[0] = {
940 : : .type = RTE_BPF_ARG_PTR,
941 : 414 : .size = ctx->prm.area_size,
942 : : },
943 : : .nb_prog_arg = 1,
944 : : .debug = debug,
945 : : };
946 : :
947 : : /* Catch invalid states. */
948 [ - + ]: 414 : TEST_ASSERT_NOT_NULL(rte_bpf_validate_debug_catch(debug,
949 : : RTE_BPF_VALIDATE_DEBUG_EVENT_INVALID_STATE,
950 : : &(struct rte_bpf_validate_debug_callback){
951 : : .fn = invalid_state_cb,
952 : : .ctx = ctx,
953 : : }), "add catchpoint error %d", rte_errno);
954 : :
955 : : /* Break on pre test instruction. */
956 [ - + ]: 414 : TEST_ASSERT_NOT_NULL(rte_bpf_validate_debug_break(debug, ctx->pre.program_counter,
957 : : &(struct rte_bpf_validate_debug_callback){
958 : : .fn = pre_callback,
959 : : .ctx = ctx,
960 : : }), "add pre breakpoint error %d", rte_errno);
961 : :
962 : : /* Break on post test instruction. */
963 [ - + ]: 414 : TEST_ASSERT_NOT_NULL(rte_bpf_validate_debug_break(debug, ctx->post.program_counter,
964 : : &(struct rte_bpf_validate_debug_callback){
965 : : .fn = post_callback,
966 : : .ctx = ctx,
967 : : }), "add post breakpoint error %d", rte_errno);
968 : :
969 [ + + ]: 414 : if (ctx->jump.program_counter != NO_PROGRAM_COUNTER)
970 : : /* Break on jump test instruction. */
971 [ - + ]: 324 : TEST_ASSERT_NOT_NULL(rte_bpf_validate_debug_break(debug, ctx->jump.program_counter,
972 : : &(struct rte_bpf_validate_debug_callback){
973 : : .fn = jump_callback,
974 : : .ctx = ctx,
975 : : }), "add jump breakpoint error %d", rte_errno);
976 : :
977 : 414 : struct rte_bpf *const bpf = rte_bpf_load_ex(&prm);
978 : 414 : const int validation_errno = rte_errno;
979 : :
980 : 414 : rte_bpf_destroy(bpf);
981 : 414 : rte_bpf_validate_debug_destroy(debug);
982 : :
983 [ - + ]: 414 : TEST_ASSERT_NOT_NULL(bpf, "validation error %d", validation_errno);
984 : :
985 [ - + ]: 414 : TEST_ASSERT_EQUAL(ctx->pre.hit_count, !ctx->prm.pre.is_unreachable,
986 : : "pre hit_count = %d", ctx->pre.hit_count);
987 [ - + ]: 414 : TEST_ASSERT_EQUAL(ctx->post.hit_count, !ctx->prm.post.is_unreachable,
988 : : "post hit_count = %d", ctx->post.hit_count);
989 [ - + ]: 414 : TEST_ASSERT_EQUAL(ctx->jump.hit_count, !ctx->prm.jump.is_unreachable,
990 : : "jump hit_count = %d", ctx->jump.hit_count);
991 : :
992 : : return TEST_SUCCESS;
993 : : }
994 : :
995 : : /* Dump whole program to log. */
996 : : static void
997 : 0 : log_program_dump(const struct ebpf_insn *ins, uint32_t nb_ins, uint32_t pre_pc)
998 : : {
999 : : char hexadecimal[DISASSEMBLY_FORMAT_BUFFER_SIZE];
1000 : : char disassembly[DISASSEMBLY_FORMAT_BUFFER_SIZE];
1001 : :
1002 : 0 : TEST_LOG_LINE(NOTICE, "\tTested program:");
1003 [ # # ]: 0 : for (uint32_t pc = 0; pc != nb_ins; ++pc) {
1004 : 0 : rte_bpf_format(hexadecimal, sizeof(hexadecimal), &ins[pc], pc,
1005 : : RTE_BPF_FORMAT_FLAG_HEXADECIMAL |
1006 : : RTE_BPF_FORMAT_FLAG_NEVER_WIDE);
1007 : 0 : rte_bpf_format(disassembly, sizeof(disassembly), &ins[pc], pc,
1008 : : RTE_BPF_FORMAT_FLAG_DISASSEMBLY |
1009 : : RTE_BPF_FORMAT_FLAG_ABSOLUTE_JUMPS);
1010 [ # # ]: 0 : TEST_LOG_LINE(NOTICE, "\t%5u: \t%s \t%s%s",
1011 : : pc, hexadecimal, disassembly,
1012 : : pc != pre_pc ? "" : " ; tested instruction");
1013 : :
1014 [ # # ]: 0 : if (!rte_bpf_insn_is_wide(&ins[pc]))
1015 : 0 : continue;
1016 : :
1017 : 0 : ++pc;
1018 : :
1019 : 0 : rte_bpf_format(hexadecimal, sizeof(hexadecimal), &ins[pc], pc,
1020 : : RTE_BPF_FORMAT_FLAG_HEXADECIMAL |
1021 : : RTE_BPF_FORMAT_FLAG_NEVER_WIDE);
1022 : 0 : TEST_LOG_LINE(NOTICE, "\t%6s \t%s", "", hexadecimal);
1023 : : }
1024 : 0 : }
1025 : :
1026 : : static void
1027 : 0 : log_formatted_registers(const char *heading, const struct verify_instruction_context *ctx,
1028 : : const struct point_context *point_ctx)
1029 : : {
1030 : : char register_name[8];
1031 : :
1032 : 0 : TEST_LOG_LINE(NOTICE, "\t%s", heading);
1033 [ # # ]: 0 : if (ctx->dst_reg != NO_REGISTER) {
1034 : 0 : snprintf(register_name, sizeof(register_name), "r%hhu", ctx->dst_reg);
1035 : 0 : TEST_LOG_LINE(NOTICE, "\t%5s: \t%s", register_name, point_ctx->formatted_dst);
1036 : : }
1037 [ # # ]: 0 : if (ctx->src_reg != NO_REGISTER) {
1038 : 0 : snprintf(register_name, sizeof(register_name), "r%hhu", ctx->src_reg);
1039 : 0 : TEST_LOG_LINE(NOTICE, "\t%5s: \t%s", register_name, point_ctx->formatted_src);
1040 : : }
1041 : 0 : }
1042 : :
1043 : : /*
1044 : : * Verify instruction validation behaviour described by prm.
1045 : : *
1046 : : * Generate the program containing specified instruction on the code path with
1047 : : * specified register pre-domains and verify specified register post-domains.
1048 : : *
1049 : : * See comment to `generate_program` for more requirements and limitations.
1050 : : */
1051 : : static int
1052 : 414 : verify_instruction(struct verify_instruction_param prm)
1053 : : {
1054 : 414 : struct verify_instruction_context ctx = {
1055 : : .prm = prm,
1056 : : };
1057 : : struct ebpf_insn ins_buf[64];
1058 : :
1059 : 414 : const uint32_t nb_ins = generate_program(&ctx, ins_buf);
1060 : : RTE_ASSERT(nb_ins <= RTE_DIM(ins_buf));
1061 : :
1062 : 414 : const int rc = debug_validation(&ctx, ins_buf, nb_ins);
1063 : :
1064 : : /* Log more data at DEBUG level on success, NOTICE on failure. */
1065 [ + - - + ]: 414 : if (rte_log_can_log(RTE_LOGTYPE_TEST_BPF_VALIDATE, RTE_LOG_DEBUG) ||
1066 : : rc != TEST_SUCCESS) {
1067 : 0 : log_program_dump(ins_buf, nb_ins, ctx.pre.program_counter);
1068 : 0 : log_formatted_registers("Pre-state:", &ctx, &ctx.pre);
1069 : 0 : log_formatted_registers("Post-state:", &ctx, &ctx.post);
1070 [ # # ]: 0 : if (ctx.jump.program_counter != NO_PROGRAM_COUNTER)
1071 : 0 : log_formatted_registers("Jump-state:", &ctx, &ctx.jump);
1072 : : }
1073 : :
1074 : 414 : return rc;
1075 : : }
1076 : :
1077 : : static int
1078 : 808 : opcode_comparison_index(uint8_t opcode)
1079 : : {
1080 [ + - ]: 6260 : for (int index = 0; index != RTE_DIM(comparisons_opcode); ++index)
1081 [ + + ]: 6260 : if (comparisons_opcode[index] == opcode)
1082 : 808 : return index;
1083 : 0 : TEST_LOG_LINE(ERR, "Unsupported or not a comparison opcode: %hhx", opcode);
1084 : 0 : RTE_VERIFY(false);
1085 : : }
1086 : :
1087 : : /* Change two-register comparison verification to immediate one. */
1088 : : static bool
1089 : 304 : make_comparison_immediate(struct verify_instruction_param *prm)
1090 : : {
1091 : 304 : int comparison_index = opcode_comparison_index(prm->tested_instruction.code);
1092 : 304 : const int64_t value = prm->pre.src.s.min;
1093 : :
1094 [ - + ]: 304 : if ((comparison_index & COMPARISON_INDEX_IMMEDIATE) != 0) {
1095 : 0 : TEST_LOG_LINE(ERR, "Comparison %hhx is already immediate.",
1096 : : prm->tested_instruction.code);
1097 : 0 : RTE_VERIFY(false);
1098 : : }
1099 : :
1100 [ + + + - : 432 : if (!domain_is_singleton(&prm->pre.src) || !domain_is_singleton(&prm->post.src) ||
- + ]
1101 : : !domain_is_singleton(&prm->jump.src)) {
1102 : 240 : TEST_LOG_LINE(DEBUG, "Cannot make immediate out of a non-singleton domain.");
1103 : 240 : return false;
1104 : : }
1105 [ + - + - : 64 : if (prm->pre.src.is_pointer || prm->post.src.is_pointer || prm->jump.src.is_pointer) {
- + ]
1106 : 0 : TEST_LOG_LINE(DEBUG, "Cannot make immediate out of a pointer.");
1107 : 0 : return false;
1108 : : }
1109 [ + + + + ]: 64 : if (prm->post.src.s.min != value || prm->jump.src.s.min != value) {
1110 : 46 : TEST_LOG_LINE(DEBUG, "Cannot make immediate if the value changes.");
1111 : 46 : return false;
1112 : : }
1113 [ - + ]: 18 : if (!fits_in_imm32(value)) {
1114 : 0 : TEST_LOG_LINE(ERR, "Cannot make immediate unless value fits in int32.");
1115 : 0 : return false;
1116 : : }
1117 : :
1118 : 18 : comparison_index |= COMPARISON_INDEX_IMMEDIATE;
1119 : 18 : prm->tested_instruction.code = comparisons_opcode[comparison_index];
1120 : 18 : prm->tested_instruction.imm = value;
1121 : :
1122 [ - + ]: 18 : RTE_VERIFY(prm->pre.src.is_defined);
1123 : 18 : prm->pre.src.is_defined = false;
1124 : :
1125 [ + + ]: 18 : if (!prm->post.is_unreachable) {
1126 [ - + ]: 17 : RTE_VERIFY(prm->post.src.is_defined);
1127 : 17 : prm->post.src.is_defined = false;
1128 : : }
1129 : :
1130 [ + + ]: 18 : if (!prm->jump.is_unreachable) {
1131 [ - + ]: 17 : RTE_VERIFY(prm->jump.src.is_defined);
1132 : 17 : prm->jump.src.is_defined = false;
1133 : : }
1134 : :
1135 : : return true;
1136 : : }
1137 : :
1138 : : /* Change immediate comparison verification to two-register one. */
1139 : : static void
1140 : 12 : make_comparison_two_register(struct verify_instruction_param *prm)
1141 : : {
1142 : 12 : int comparison_index = opcode_comparison_index(prm->tested_instruction.code);
1143 : 12 : const int64_t value = prm->tested_instruction.imm;
1144 : :
1145 [ - + ]: 12 : if ((comparison_index & COMPARISON_INDEX_IMMEDIATE) == 0) {
1146 : 0 : TEST_LOG_LINE(ERR, "Comparison %hhx is already two-register.",
1147 : : prm->tested_instruction.code);
1148 : 0 : RTE_VERIFY(false);
1149 : : }
1150 : :
1151 : 12 : comparison_index &= ~COMPARISON_INDEX_IMMEDIATE;
1152 : 12 : prm->tested_instruction.code = comparisons_opcode[comparison_index];
1153 : 12 : prm->tested_instruction.imm = 0;
1154 : :
1155 [ - + ]: 12 : RTE_VERIFY(!prm->pre.src.is_defined);
1156 : 12 : prm->pre.src = make_singleton_domain(value);
1157 : :
1158 [ + + ]: 12 : if (!prm->post.is_unreachable) {
1159 [ - + ]: 8 : RTE_VERIFY(!prm->post.src.is_defined);
1160 : 8 : prm->post.src = prm->pre.src;
1161 : : }
1162 : :
1163 [ + + ]: 12 : if (!prm->jump.is_unreachable) {
1164 [ - + ]: 8 : RTE_VERIFY(!prm->jump.src.is_defined);
1165 : 8 : prm->jump.src = prm->pre.src;
1166 : : }
1167 : 12 : }
1168 : :
1169 : : /* Change comparison verification to complement (negated result) one. */
1170 : : static void
1171 : 152 : make_comparison_complement(struct verify_instruction_param *prm)
1172 : : {
1173 : 152 : int comparison_index = opcode_comparison_index(prm->tested_instruction.code);
1174 : 152 : comparison_index ^= COMPARISON_INDEX_GREATER | COMPARISON_INDEX_INCLUSIVE;
1175 : 152 : prm->tested_instruction.code = comparisons_opcode[comparison_index];
1176 : 152 : RTE_SWAP(prm->post, prm->jump);
1177 : 152 : }
1178 : :
1179 : : /* Change comparison verification to converse (swapped operands) one. */
1180 : : static void
1181 : 304 : make_comparison_converse(struct verify_instruction_param *prm)
1182 : : {
1183 : 304 : int comparison_index = opcode_comparison_index(prm->tested_instruction.code);
1184 : 304 : comparison_index ^= COMPARISON_INDEX_GREATER;
1185 : 304 : prm->tested_instruction.code = comparisons_opcode[comparison_index];
1186 : 304 : RTE_SWAP(prm->pre.dst, prm->pre.src);
1187 : 304 : RTE_SWAP(prm->post.dst, prm->post.src);
1188 : 304 : RTE_SWAP(prm->jump.dst, prm->jump.src);
1189 : 304 : }
1190 : :
1191 : : /* Change signed comparison verification to unsigned one. */
1192 : : static void
1193 : 36 : make_comparison_signed(struct verify_instruction_param *prm)
1194 : : {
1195 : 36 : int comparison_index = opcode_comparison_index(prm->tested_instruction.code);
1196 [ - + ]: 36 : if ((comparison_index & COMPARISON_INDEX_SIGNED) != 0) {
1197 : 0 : TEST_LOG_LINE(ERR, "Comparison %hhx is already signed.",
1198 : : prm->tested_instruction.code);
1199 : 0 : RTE_VERIFY(false);
1200 : : }
1201 : 36 : comparison_index |= COMPARISON_INDEX_SIGNED;
1202 : 36 : prm->tested_instruction.code = comparisons_opcode[comparison_index];
1203 : 36 : }
1204 : :
1205 : : /* Verify specified two-register comparison and, if possible, immediate one. */
1206 : : static int
1207 : 304 : verify_comparison_subcase(struct verify_instruction_param prm)
1208 : : {
1209 [ - + ]: 304 : TEST_ASSERT_SUCCESS(verify_instruction(prm), "two-register version check");
1210 : :
1211 [ + + ]: 304 : if (make_comparison_immediate(&prm))
1212 [ - + ]: 18 : TEST_ASSERT_SUCCESS(verify_instruction(prm), "immediate version check");
1213 : :
1214 : : return TEST_SUCCESS;
1215 : : }
1216 : :
1217 : : /*
1218 : : * Verify comparison instruction validation behaviour.
1219 : : *
1220 : : * Call `verify_instruction` for all valid variations of the instruction.
1221 : : *
1222 : : * For instance, `jgt r2, r3` verifies:
1223 : : * * `jgt r2, r3`;
1224 : : * * `jlt r3, r2` src and dst swapped with each other;
1225 : : * * `jle r2, r3` with post and jump domains swapped with each other;
1226 : : * * `jge r3, r2` with all corresponding swaps;
1227 : : * * immediate versions of everything above where possible,
1228 : : * that is, register on the right is an int32 scalar singleton;
1229 : : * * signed versions of everything above if `also_signed` is true;
1230 : : *
1231 : : * Regardless if passed instruction compares with immediate or singleton src
1232 : : * both cases are generated and tested.
1233 : : */
1234 : : static int
1235 : 40 : verify_comparison(struct verify_instruction_param prm, bool also_signed)
1236 : : {
1237 : 40 : fill_verify_instruction_defaults(&prm);
1238 : :
1239 [ + + ]: 40 : if (!prm.pre.src.is_defined)
1240 : : /* Convert from immediate form to simplify further logic. */
1241 : 12 : make_comparison_two_register(&prm);
1242 : :
1243 : : /* All reachable domains must be defined by this point. */
1244 [ - + ]: 40 : RTE_VERIFY(prm.pre.dst.is_defined);
1245 [ - + ]: 40 : RTE_VERIFY(prm.pre.src.is_defined);
1246 [ + + ]: 40 : if (!prm.post.is_unreachable) {
1247 [ - + ]: 31 : RTE_VERIFY(prm.post.dst.is_defined);
1248 [ - + ]: 31 : RTE_VERIFY(prm.post.src.is_defined);
1249 : : }
1250 [ + + ]: 40 : if (!prm.jump.is_unreachable) {
1251 [ - + ]: 27 : RTE_VERIFY(prm.jump.dst.is_defined);
1252 [ + - ]: 27 : RTE_VERIFY(prm.jump.src.is_defined);
1253 : : }
1254 : :
1255 [ + + ]: 116 : for (int make_signed = 0; make_signed <= also_signed; ++make_signed) {
1256 [ + + ]: 76 : if (make_signed)
1257 : 36 : make_comparison_signed(&prm);
1258 : :
1259 [ + + ]: 228 : for (int complement = false; complement <= true; ++complement) {
1260 : :
1261 [ + + ]: 456 : for (int converse = false; converse <= true; ++converse) {
1262 : :
1263 [ - + ]: 304 : TEST_ASSERT_SUCCESS(verify_comparison_subcase(prm),
1264 : : "make_signed=%d, complement=%d, converse=%d",
1265 : : make_signed, complement, converse);
1266 : :
1267 : 304 : make_comparison_converse(&prm);
1268 : : }
1269 : :
1270 : 152 : make_comparison_complement(&prm);
1271 : : }
1272 : : }
1273 : :
1274 : : return TEST_SUCCESS;
1275 : : }
1276 : :
1277 : :
1278 : : /* TESTS FOR SPECIFIC INSTRUCTIONS */
1279 : :
1280 : : /* 64-bit addition of immediate to a range. */
1281 : : static int
1282 : 1 : test_alu64_add_k(void)
1283 : : {
1284 : 1 : return verify_instruction((struct verify_instruction_param){
1285 : : .tested_instruction = {
1286 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_K),
1287 : : .imm = 17,
1288 : : },
1289 : : .pre.dst = make_signed_domain(11, 29),
1290 : : .post.dst = make_signed_domain(11 + 17, 29 + 17),
1291 : : });
1292 : : }
1293 : :
1294 : : /* 64-bit addition of immediate to a pointer range. */
1295 : : static int
1296 : 1 : test_alu64_add_k_pointer(void)
1297 : : {
1298 : 2 : return verify_instruction((struct verify_instruction_param){
1299 : : .tested_instruction = {
1300 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_K),
1301 : : .imm = 17,
1302 : : },
1303 : : .area_size = 256,
1304 : : .pre.dst = make_pointer_domain(11, 29),
1305 : : .post.dst = make_pointer_domain(11 + 17, 29 + 17),
1306 : : });
1307 : : }
1308 : :
1309 : : /* 64-bit addition of pointer to a pointer. */
1310 : : static int
1311 : 1 : test_alu64_add_x_pointer_pointer(void)
1312 : : {
1313 : 2 : return verify_instruction((struct verify_instruction_param){
1314 : : .tested_instruction = {
1315 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_X),
1316 : : },
1317 : : .area_size = 256,
1318 : : .pre.dst = make_pointer_domain(11, 29),
1319 : : .pre.src = make_pointer_domain(17, 23),
1320 : : .post.dst = unknown,
1321 : : });
1322 : : }
1323 : :
1324 : : /* 64-bit addition of scalar to a pointer. */
1325 : : static int
1326 : 1 : test_alu64_add_x_pointer_scalar(void)
1327 : : {
1328 : 2 : return verify_instruction((struct verify_instruction_param){
1329 : : .tested_instruction = {
1330 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_X),
1331 : : },
1332 : : .area_size = 256,
1333 : : .pre.dst = make_pointer_domain(11, 29),
1334 : : .pre.src = make_signed_domain(17, 23),
1335 : : .post.dst = make_pointer_domain(11 + 17, 29 + 23),
1336 : : });
1337 : : }
1338 : :
1339 : : /* 64-bit addition of pointer to a scalar. */
1340 : : static int
1341 : 1 : test_alu64_add_x_scalar_pointer(void)
1342 : : {
1343 : 2 : return verify_instruction((struct verify_instruction_param){
1344 : : .tested_instruction = {
1345 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_X),
1346 : : },
1347 : : .area_size = 256,
1348 : : .pre.dst = make_signed_domain(11, 29),
1349 : : .pre.src = make_pointer_domain(17, 23),
1350 : : .post.dst = make_pointer_domain(11 + 17, 29 + 23),
1351 : : });
1352 : : }
1353 : :
1354 : : /* 64-bit addition of scalar to a scalar. */
1355 : : static int
1356 : 1 : test_alu64_add_x_scalar_scalar(void)
1357 : : {
1358 : 1 : return verify_instruction((struct verify_instruction_param){
1359 : : .tested_instruction = {
1360 : : .code = (EBPF_ALU64 | BPF_ADD | BPF_X),
1361 : : },
1362 : : .area_size = 256,
1363 : : .pre.dst = make_signed_domain(11, 29),
1364 : : .pre.src = make_signed_domain(17, 23),
1365 : : .post.dst = make_signed_domain(11 + 17, 29 + 23),
1366 : : });
1367 : : }
1368 : :
1369 : : /* 64-bit bitwise AND between a scalar range and immediate. */
1370 : : static int
1371 : 1 : test_alu64_and_k(void)
1372 : : {
1373 : 1 : return verify_instruction((struct verify_instruction_param){
1374 : : .tested_instruction = {
1375 : : .code = (EBPF_ALU64 | BPF_AND | BPF_K),
1376 : : .imm = 5,
1377 : : },
1378 : : .pre.dst = make_signed_domain(6, 8),
1379 : : .post.dst = make_signed_domain(0, 7),
1380 : : });
1381 : : }
1382 : :
1383 : : /* 64-bit division and modulo of UINT64_MAX*2/3. */
1384 : : static int
1385 : 1 : test_alu64_div_mod_big_constant(void)
1386 : : {
1387 : : const uint64_t dividend = UINT64_MAX / 3 * 2;
1388 : : static const uint64_t divisors[] = {
1389 : : 1,
1390 : : 2,
1391 : : 3,
1392 : : UINT64_MAX / 3,
1393 : : INT64_MAX,
1394 : : INT64_MIN,
1395 : : UINT64_MAX / 3 * 2,
1396 : : UINT64_MAX / 4 * 3,
1397 : : UINT64_MAX,
1398 : : };
1399 [ + + ]: 10 : for (int index = 0; index != RTE_DIM(divisors); ++index) {
1400 : 9 : const uint64_t divisor = divisors[index];
1401 : :
1402 [ - + ]: 9 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1403 : : .tested_instruction = {
1404 : : .code = (EBPF_ALU64 | BPF_DIV | BPF_X),
1405 : : },
1406 : : .pre.dst = make_singleton_domain(dividend),
1407 : : .pre.src = make_singleton_domain(divisor),
1408 : : .post.dst = make_singleton_domain(dividend / divisor),
1409 : : }), "(EBPF_ALU64 | BPF_DIV | BPF_X) check, index=%d", index);
1410 : :
1411 [ - + ]: 9 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1412 : : .tested_instruction = {
1413 : : .code = (EBPF_ALU64 | BPF_MOD | BPF_X),
1414 : : },
1415 : : .pre.dst = make_singleton_domain(dividend),
1416 : : .pre.src = make_singleton_domain(divisor),
1417 : : .post.dst = make_singleton_domain(dividend % divisor),
1418 : : }), "(EBPF_ALU64 | BPF_MOD | BPF_X) check, index=%d", index);
1419 : : }
1420 : :
1421 : : return TEST_SUCCESS;
1422 : : }
1423 : :
1424 : : /* 64-bit division and modulo of UINT64_MAX/3..UINT64_MAX*2/3 by a constant. */
1425 : : static int
1426 : 1 : test_alu64_div_mod_big_range(void)
1427 : : {
1428 : : const uint64_t dividend_first = UINT64_MAX / 3;
1429 : : const uint64_t dividend_last = UINT64_MAX / 3 * 2;
1430 : : static const uint64_t divisors[] = {
1431 : : 1,
1432 : : 2,
1433 : : 3,
1434 : : UINT64_MAX / 3,
1435 : : INT64_MAX,
1436 : : INT64_MIN,
1437 : : UINT64_MAX / 3 * 2,
1438 : : UINT64_MAX / 4 * 3,
1439 : : UINT64_MAX,
1440 : : };
1441 [ + + ]: 10 : for (int index = 0; index != RTE_DIM(divisors); ++index) {
1442 : 9 : const uint64_t divisor = divisors[index];
1443 : :
1444 [ - + ]: 9 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1445 : : .tested_instruction = {
1446 : : .code = (EBPF_ALU64 | BPF_DIV | BPF_X),
1447 : : },
1448 : : .pre.dst = make_unsigned_domain(dividend_first, dividend_last),
1449 : : .pre.src = make_singleton_domain(divisor),
1450 : : .post.dst = make_unsigned_domain(0, dividend_last),
1451 : : }), "(EBPF_ALU64 | BPF_DIV | BPF_X) check, index=%d", index);
1452 : :
1453 [ - + ]: 9 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1454 : : .tested_instruction = {
1455 : : .code = (EBPF_ALU64 | BPF_MOD | BPF_X),
1456 : : },
1457 : : .pre.dst = make_unsigned_domain(dividend_first, dividend_last),
1458 : : .pre.src = make_singleton_domain(divisor),
1459 : : .post.dst = make_unsigned_domain(0, RTE_MIN(dividend_last, divisor - 1)),
1460 : : }), "(EBPF_ALU64 | BPF_MOD | BPF_X) check, index=%d", index);
1461 : : }
1462 : :
1463 : : return TEST_SUCCESS;
1464 : : }
1465 : :
1466 : : /* 64-bit division and modulo of INT64_MIN by -1. */
1467 : : static int
1468 : 1 : test_alu64_div_mod_overflow(void)
1469 : : {
1470 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1471 : : .tested_instruction = {
1472 : : .code = (EBPF_ALU64 | BPF_DIV | BPF_K),
1473 : : .imm = -1,
1474 : : },
1475 : : .pre.dst = make_singleton_domain(INT64_MIN),
1476 : : .post.dst = make_singleton_domain(0),
1477 : : }), "(EBPF_ALU64 | BPF_DIV | BPF_K) check");
1478 : :
1479 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1480 : : .tested_instruction = {
1481 : : .code = (EBPF_ALU64 | BPF_DIV | BPF_X),
1482 : : },
1483 : : .pre.dst = make_singleton_domain(INT64_MIN),
1484 : : .pre.src = make_singleton_domain(-1),
1485 : : .post.dst = make_singleton_domain(0),
1486 : : }), "(EBPF_ALU64 | BPF_DIV | BPF_X) check");
1487 : :
1488 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1489 : : .tested_instruction = {
1490 : : .code = (EBPF_ALU64 | BPF_MOD | BPF_K),
1491 : : .imm = -1,
1492 : : },
1493 : : .pre.dst = make_singleton_domain(INT64_MIN),
1494 : : .post.dst = make_singleton_domain(INT64_MIN),
1495 : : }), "(EBPF_ALU64 | BPF_MOD | BPF_K) check");
1496 : :
1497 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1498 : : .tested_instruction = {
1499 : : .code = (EBPF_ALU64 | BPF_MOD | BPF_X),
1500 : : },
1501 : : .pre.dst = make_singleton_domain(INT64_MIN),
1502 : : .pre.src = make_singleton_domain(-1),
1503 : : .post.dst = make_singleton_domain(INT64_MIN),
1504 : : }), "(EBPF_ALU64 | BPF_MOD | BPF_X) check");
1505 : :
1506 : 1 : return TEST_SUCCESS;
1507 : : }
1508 : :
1509 : : /* 64-bit left shift by 63. */
1510 : : static int
1511 : 1 : test_alu64_lsh_63(void)
1512 : : {
1513 : 1 : return verify_instruction((struct verify_instruction_param){
1514 : : .tested_instruction = {
1515 : : .code = (EBPF_ALU64 | BPF_LSH | BPF_K),
1516 : : .imm = 63,
1517 : : },
1518 : : .pre.dst = make_signed_domain(3, 5),
1519 : : .post.dst = unknown,
1520 : : });
1521 : : }
1522 : :
1523 : : /* 64-bit multiplication of constant and immediate with overflow. */
1524 : : static int
1525 : 1 : test_alu64_mul_k_overflow(void)
1526 : : {
1527 : 1 : return verify_instruction((struct verify_instruction_param){
1528 : : .tested_instruction = {
1529 : : .code = (EBPF_ALU64 | BPF_MUL | BPF_K),
1530 : : .imm = 0x12345678,
1531 : : },
1532 : : .pre.dst = make_singleton_domain(0x9876543210),
1533 : : .post.dst = make_singleton_domain(0x9876543210u * 0x12345678),
1534 : : });
1535 : : }
1536 : :
1537 : : /* 64-bit mul of small scalar range and immediate. */
1538 : : static int
1539 : 1 : test_alu64_mul_k_range_small(void)
1540 : : {
1541 : 1 : return verify_instruction((struct verify_instruction_param){
1542 : : .tested_instruction = {
1543 : : .code = (EBPF_ALU64 | BPF_MUL | BPF_K),
1544 : : .imm = 11,
1545 : : },
1546 : : .pre.dst = make_unsigned_domain(17, 29),
1547 : : .post.dst = make_unsigned_domain(17 * 11, 29 * 11),
1548 : : });
1549 : : }
1550 : :
1551 : : /* 64-bit negation when interval first element is INT64_MIN. */
1552 : : static int
1553 : 1 : test_alu64_neg_int64min_first(void)
1554 : : {
1555 : : static const int64_t other_values[] = {
1556 : : INT64_MIN,
1557 : : INT64_MIN + 1,
1558 : : INT64_MIN + 13,
1559 : : -17,
1560 : : -1,
1561 : : 0,
1562 : : 1,
1563 : : 19,
1564 : : INT64_MAX - 23,
1565 : : INT64_MAX - 1,
1566 : : INT64_MAX,
1567 : : };
1568 [ + + ]: 12 : for (int other_index = 0; other_index != RTE_DIM(other_values); ++other_index) {
1569 : 11 : const int64_t other_value = other_values[other_index];
1570 [ + + - + ]: 11 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1571 : : .tested_instruction = {
1572 : : .code = (EBPF_ALU64 | BPF_NEG),
1573 : : },
1574 : : .pre.dst = make_signed_domain(INT64_MIN, other_value),
1575 : : .post.dst = other_value > 0 ? unknown :
1576 : : make_unsigned_domain(-(uint64_t)other_value, INT64_MIN),
1577 : : }), "other_index=%d", other_index);
1578 : : }
1579 : : return TEST_SUCCESS;
1580 : : }
1581 : :
1582 : : /* 64-bit negation when interval last element is INT64_MIN. */
1583 : : static int
1584 : 1 : test_alu64_neg_int64min_last(void)
1585 : : {
1586 : : static const uint64_t other_values[] = {
1587 : : 0,
1588 : : 1,
1589 : : 19,
1590 : : INT64_MAX - 23,
1591 : : INT64_MAX - 1,
1592 : : INT64_MAX,
1593 : : INT64_MIN,
1594 : : };
1595 [ + + ]: 8 : for (int other_index = 0; other_index != RTE_DIM(other_values); ++other_index) {
1596 : 7 : const int64_t other_value = other_values[other_index];
1597 [ - + ]: 7 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1598 : : .tested_instruction = {
1599 : : .code = (EBPF_ALU64 | BPF_NEG),
1600 : : },
1601 : : .pre.dst = make_unsigned_domain(other_value, INT64_MIN),
1602 : : .post.dst = make_signed_domain(INT64_MIN, -(uint64_t)other_value),
1603 : : }), "other_index=%d", other_index);
1604 : : }
1605 : : return TEST_SUCCESS;
1606 : : }
1607 : :
1608 : : /* 64-bit negation when interval first element is zero. */
1609 : : static int
1610 : 1 : test_alu64_neg_zero_first(void)
1611 : : {
1612 : : static const uint64_t other_values[] = {
1613 : : 0,
1614 : : 1,
1615 : : 19,
1616 : : INT64_MAX - 23,
1617 : : INT64_MAX - 1,
1618 : : INT64_MAX,
1619 : : INT64_MIN,
1620 : : INT64_MIN + 1,
1621 : : INT64_MIN + 13,
1622 : : -17,
1623 : : -1,
1624 : : };
1625 [ + + ]: 12 : for (int other_index = 0; other_index != RTE_DIM(other_values); ++other_index) {
1626 : 11 : const uint64_t other_value = other_values[other_index];
1627 [ + + - + ]: 11 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1628 : : .tested_instruction = {
1629 : : .code = (EBPF_ALU64 | BPF_NEG),
1630 : : },
1631 : : .pre.dst = make_unsigned_domain(0, other_value),
1632 : : .post.dst = other_value > (uint64_t)INT64_MIN ? unknown :
1633 : : make_signed_domain(-(uint64_t)other_value, 0),
1634 : : }), "other_index=%d", other_index);
1635 : : }
1636 : : return TEST_SUCCESS;
1637 : : }
1638 : :
1639 : : /* 64-bit negation when interval last element is zero. */
1640 : : static int
1641 : 1 : test_alu64_neg_zero_last(void)
1642 : : {
1643 : : static const int64_t other_values[] = {
1644 : : INT64_MIN,
1645 : : INT64_MIN + 1,
1646 : : INT64_MIN + 13,
1647 : : -17,
1648 : : -1,
1649 : : 0,
1650 : : };
1651 [ + + ]: 7 : for (int other_index = 0; other_index != RTE_DIM(other_values); ++other_index) {
1652 : 6 : const int64_t other_value = other_values[other_index];
1653 [ - + ]: 6 : TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
1654 : : .tested_instruction = {
1655 : : .code = (EBPF_ALU64 | BPF_NEG),
1656 : : },
1657 : : .pre.dst = make_signed_domain(other_value, 0),
1658 : : .post.dst = make_unsigned_domain(0, -(uint64_t)other_value),
1659 : : }), "other_index=%d", other_index);
1660 : : }
1661 : :
1662 : : return TEST_SUCCESS;
1663 : : }
1664 : :
1665 : : /* 64-bit bitwise OR between a positive scalar range and negative immediate. */
1666 : : static int
1667 : 1 : test_alu64_or_k_negative(void)
1668 : : {
1669 : 1 : return verify_instruction((struct verify_instruction_param){
1670 : : .tested_instruction = {
1671 : : .code = (EBPF_ALU64 | BPF_OR | BPF_K),
1672 : : .imm = -2,
1673 : : },
1674 : : .pre.dst = make_signed_domain(5, 6),
1675 : : .post.dst = make_signed_domain(-2, -1),
1676 : : });
1677 : : }
1678 : :
1679 : : /* 64-bit bitwise OR between a positive scalar range and positive immediate. */
1680 : : static int
1681 : 1 : test_alu64_or_k_positive(void)
1682 : : {
1683 : 1 : return verify_instruction((struct verify_instruction_param){
1684 : : .tested_instruction = {
1685 : : .code = (EBPF_ALU64 | BPF_OR | BPF_K),
1686 : : .imm = 2,
1687 : : },
1688 : : .pre.dst = make_signed_domain(5, 6),
1689 : : .post.dst = make_signed_domain(5, 7),
1690 : : });
1691 : : }
1692 : :
1693 : : /* 64-bit difference between two negative ranges.. */
1694 : : static int
1695 : 1 : test_alu64_sub_x_src_signed_max_zero(void)
1696 : : {
1697 : 1 : return verify_instruction((struct verify_instruction_param){
1698 : : .tested_instruction = {
1699 : : .code = (EBPF_ALU64 | BPF_SUB | BPF_X),
1700 : : },
1701 : : .pre.dst = make_signed_domain(INT64_MIN, 0),
1702 : : .pre.src = make_signed_domain(INT64_MIN, 0),
1703 : : .post.dst = unknown,
1704 : : });
1705 : : }
1706 : :
1707 : : /* 64-bit bitwise XOR between a negative scalar range and zero immediate. */
1708 : : static int
1709 : 1 : test_alu64_xor_k_negative(void)
1710 : : {
1711 : 1 : return verify_instruction((struct verify_instruction_param){
1712 : : .tested_instruction = {
1713 : : .code = (EBPF_ALU64 | BPF_XOR | BPF_K),
1714 : : .imm = 0,
1715 : : },
1716 : : .pre.dst = make_signed_domain(INT64_MIN, 0),
1717 : : .post.dst = unknown,
1718 : : });
1719 : : }
1720 : :
1721 : : /* Jump if greater than immediate. */
1722 : : static int
1723 : 1 : test_jmp64_jeq_k(void)
1724 : : {
1725 : 1 : return verify_instruction((struct verify_instruction_param){
1726 : : .tested_instruction = {
1727 : : .code = (BPF_JMP | BPF_JGT | BPF_K),
1728 : : .imm = 0,
1729 : : },
1730 : : .pre.dst = make_unsigned_domain(0, 1),
1731 : : .post.dst = make_singleton_domain(0),
1732 : : .jump.dst = make_singleton_domain(1),
1733 : : });
1734 : : }
1735 : :
1736 : : /* Jump if signed less than another register. */
1737 : : static int
1738 : 1 : test_jmp64_jslt_x(void)
1739 : : {
1740 : 1 : return verify_instruction((struct verify_instruction_param){
1741 : : .tested_instruction = {
1742 : : .code = (BPF_JMP | EBPF_JSLT | BPF_X),
1743 : : },
1744 : : .pre.dst = make_signed_domain(-3, 3),
1745 : : .pre.src = make_signed_domain(0, 0),
1746 : : .post.dst = make_signed_domain(0, 3),
1747 : : .jump.dst = make_signed_domain(-3, -1),
1748 : : });
1749 : : }
1750 : :
1751 : : /* Jump on ordering comparisons with potential bound overflow. */
1752 : : static int
1753 : 1 : test_jmp64_ordering_overflow(void)
1754 : : {
1755 : : /* In this test signed and unsigned cases are spelled out explicitly. */
1756 : : const bool also_signed = false;
1757 : :
1758 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1759 : : .tested_instruction = {
1760 : : .code = (BPF_JMP | EBPF_JSLT | BPF_X),
1761 : : },
1762 : : .pre.dst = make_singleton_domain(42),
1763 : : .pre.src = make_singleton_domain(INT64_MIN),
1764 : : .jump = unreachable,
1765 : : }, also_signed), "signed less than INT64_MIN");
1766 : :
1767 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1768 : : .tested_instruction = {
1769 : : .code = (BPF_JMP | EBPF_JSGT | BPF_X),
1770 : : },
1771 : : .pre.dst = make_singleton_domain(42),
1772 : : .pre.src = make_singleton_domain(INT64_MAX),
1773 : : .jump = unreachable,
1774 : : }, also_signed), "signed greater than INT64_MAX");
1775 : :
1776 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1777 : : .tested_instruction = {
1778 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1779 : : },
1780 : : .pre.dst = make_singleton_domain(42),
1781 : : .pre.src = make_singleton_domain(0),
1782 : : .jump = unreachable,
1783 : : }, also_signed), "unsigned less than zero");
1784 : :
1785 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1786 : : .tested_instruction = {
1787 : : .code = (BPF_JMP | BPF_JGT | BPF_X),
1788 : : },
1789 : : .pre.dst = make_singleton_domain(42),
1790 : : .pre.src = make_singleton_domain(UINT64_MAX),
1791 : : .jump = unreachable,
1792 : : }, also_signed), "unsigned greater than UINT64_MAX");
1793 : :
1794 : 1 : return TEST_SUCCESS;
1795 : : }
1796 : :
1797 : : /* Jump on ordering comparisons between two ranges. */
1798 : : static int
1799 : 1 : test_jmp64_ordering_ranges(void)
1800 : : {
1801 : : /* All ranges used are valid for both signed and unsigned comparisons. */
1802 : : const bool also_signed = true;
1803 : :
1804 : : /*
1805 : : * 20 ---- dst ---- 60
1806 : : * 0 - src - 10
1807 : : */
1808 : :
1809 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1810 : : .tested_instruction = {
1811 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1812 : : },
1813 : : .pre.dst = make_signed_domain(20, 60),
1814 : : .pre.src = make_signed_domain(0, 10),
1815 : : .jump = unreachable,
1816 : : }, also_signed), "strict, dst range strongly greater than src range");
1817 : :
1818 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1819 : : .tested_instruction = {
1820 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
1821 : : },
1822 : : .pre.dst = make_signed_domain(20, 60),
1823 : : .pre.src = make_signed_domain(0, 10),
1824 : : .jump = unreachable,
1825 : : }, also_signed), "non-strict, dst range strongly greater than src range");
1826 : :
1827 : : /*
1828 : : * 20 ---- dst ---- 60
1829 : : * 10 -- src -- 40
1830 : : */
1831 : :
1832 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1833 : : .tested_instruction = {
1834 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1835 : : },
1836 : : .pre.dst = make_signed_domain(20, 60),
1837 : : .pre.src = make_signed_domain(10, 40),
1838 : : .jump.dst = make_signed_domain(20, 39),
1839 : : .jump.src = make_signed_domain(21, 40),
1840 : : }, also_signed), "strict, dst range weakly greater than src range");
1841 : :
1842 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1843 : : .tested_instruction = {
1844 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
1845 : : },
1846 : : .pre.dst = make_signed_domain(20, 60),
1847 : : .pre.src = make_signed_domain(10, 40),
1848 : : .jump.dst = make_signed_domain(20, 40),
1849 : : .jump.src = make_signed_domain(20, 40),
1850 : : }, also_signed), "non-strict, dst range weakly greater than src range");
1851 : :
1852 : : /*
1853 : : * 20 ---- dst ---- 60
1854 : : * 10 -------- src -------- 70
1855 : : */
1856 : :
1857 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1858 : : .tested_instruction = {
1859 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1860 : : },
1861 : : .pre.dst = make_signed_domain(20, 60),
1862 : : .pre.src = make_signed_domain(10, 70),
1863 : : .post.src = make_signed_domain(10, 60),
1864 : : .jump.src = make_signed_domain(21, 70),
1865 : : }, also_signed), "strict, dst range included in src range");
1866 : :
1867 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1868 : : .tested_instruction = {
1869 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
1870 : : },
1871 : : .pre.dst = make_signed_domain(20, 60),
1872 : : .pre.src = make_signed_domain(10, 70),
1873 : : .post.src = make_signed_domain(10, 59),
1874 : : .jump.src = make_signed_domain(20, 70),
1875 : : }, also_signed), "non-strict, dst range included in src range");
1876 : :
1877 : : /*
1878 : : * 20 ---- dst ---- 60
1879 : : * 30 - src - 50
1880 : : */
1881 : :
1882 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1883 : : .tested_instruction = {
1884 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1885 : : },
1886 : : .pre.dst = make_signed_domain(20, 60),
1887 : : .pre.src = make_signed_domain(30, 50),
1888 : : .post.dst = make_signed_domain(30, 60),
1889 : : .jump.dst = make_signed_domain(20, 49),
1890 : : }, also_signed), "strict, dst range includes src range");
1891 : :
1892 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1893 : : .tested_instruction = {
1894 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
1895 : : },
1896 : : .pre.dst = make_signed_domain(20, 60),
1897 : : .pre.src = make_signed_domain(30, 50),
1898 : : .post.dst = make_signed_domain(31, 60),
1899 : : .jump.dst = make_signed_domain(20, 50),
1900 : : }, also_signed), "non-strict, dst range includes src range");
1901 : :
1902 : : /*
1903 : : * 20 ---- dst ---- 60
1904 : : * 40 -- src -- 70
1905 : : */
1906 : :
1907 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1908 : : .tested_instruction = {
1909 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1910 : : },
1911 : : .pre.dst = make_signed_domain(20, 60),
1912 : : .pre.src = make_signed_domain(40, 70),
1913 : : .post.dst = make_signed_domain(40, 60),
1914 : : .post.src = make_signed_domain(40, 60),
1915 : : }, also_signed), "strict, dst range weakly less than src range");
1916 : :
1917 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1918 : : .tested_instruction = {
1919 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
1920 : : },
1921 : : .pre.dst = make_signed_domain(20, 60),
1922 : : .pre.src = make_signed_domain(40, 70),
1923 : : .post.dst = make_signed_domain(41, 60),
1924 : : .post.src = make_signed_domain(40, 59),
1925 : : }, also_signed), "non-strict, dst range weakly less than src range");
1926 : :
1927 : : /*
1928 : : * 20 ---- dst ---- 60
1929 : : * 70 - src - 80
1930 : : */
1931 : :
1932 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1933 : : .tested_instruction = {
1934 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
1935 : : },
1936 : : .pre.dst = make_signed_domain(20, 60),
1937 : : .pre.src = make_signed_domain(70, 80),
1938 : : .post = unreachable,
1939 : : }, also_signed), "strict, dst range strongly less than src range");
1940 : :
1941 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1942 : : .tested_instruction = {
1943 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
1944 : : },
1945 : : .pre.dst = make_signed_domain(20, 60),
1946 : : .pre.src = make_signed_domain(70, 80),
1947 : : .post = unreachable,
1948 : : }, also_signed), "non-strict, dst range strongly less than src range");
1949 : :
1950 : 1 : return TEST_SUCCESS;
1951 : : }
1952 : :
1953 : : /* Jump on ordering comparisons with singleton inside the range. */
1954 : : static int
1955 : 1 : test_jmp64_ordering_singleton_inside(void)
1956 : : {
1957 : : /* All ranges used are valid for both signed and unsigned comparisons. */
1958 : : const bool also_signed = true;
1959 : :
1960 : : /*
1961 : : * 20 ---- dst ---- 60
1962 : : * imm
1963 : : */
1964 : :
1965 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1966 : : .tested_instruction = {
1967 : : .code = (BPF_JMP | EBPF_JLT | BPF_K),
1968 : : .imm = 40,
1969 : : },
1970 : : .pre.dst = make_signed_domain(20, 60),
1971 : : .post.dst = make_signed_domain(40, 60),
1972 : : .jump.dst = make_signed_domain(20, 39),
1973 : : }, also_signed), "(BPF_JMP | EBPF_JLT | BPF_K) check");
1974 : :
1975 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1976 : : .tested_instruction = {
1977 : : .code = (BPF_JMP | BPF_JGT | BPF_K),
1978 : : .imm = 40,
1979 : : },
1980 : : .pre.dst = make_signed_domain(20, 60),
1981 : : .post.dst = make_signed_domain(20, 40),
1982 : : .jump.dst = make_signed_domain(41, 60),
1983 : : }, also_signed), "(BPF_JMP | EBPF_JGT | BPF_K) check");
1984 : :
1985 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1986 : : .tested_instruction = {
1987 : : .code = (BPF_JMP | EBPF_JLE | BPF_K),
1988 : : .imm = 40,
1989 : : },
1990 : : .pre.dst = make_signed_domain(20, 60),
1991 : : .post.dst = make_signed_domain(41, 60),
1992 : : .jump.dst = make_signed_domain(20, 40),
1993 : : }, also_signed), "(BPF_JMP | EBPF_JLE | BPF_K) check");
1994 : :
1995 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
1996 : : .tested_instruction = {
1997 : : .code = (BPF_JMP | BPF_JGE | BPF_K),
1998 : : .imm = 40,
1999 : : },
2000 : : .pre.dst = make_signed_domain(20, 60),
2001 : : .post.dst = make_signed_domain(20, 39),
2002 : : .jump.dst = make_signed_domain(40, 60),
2003 : : }, also_signed), "(BPF_JMP | EBPF_JGE | BPF_K) check");
2004 : :
2005 : 1 : return TEST_SUCCESS;
2006 : : }
2007 : :
2008 : : /* Jump on ordering comparisons with singleton outside the range. */
2009 : : static int
2010 : 1 : test_jmp64_ordering_singleton_outside(void)
2011 : : {
2012 : : /* All ranges used are valid for both signed and unsigned comparisons. */
2013 : : const bool also_signed = true;
2014 : :
2015 : : /*
2016 : : * 20 ---- dst ---- 60
2017 : : * imm
2018 : : */
2019 : :
2020 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2021 : : .tested_instruction = {
2022 : : .code = (BPF_JMP | EBPF_JLT | BPF_K),
2023 : : .imm = 10,
2024 : : },
2025 : : .pre.dst = make_signed_domain(20, 60),
2026 : : .jump = unreachable,
2027 : : }, also_signed), "(BPF_JMP | EBPF_JLT | BPF_K) check, range greater than imm");
2028 : :
2029 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2030 : : .tested_instruction = {
2031 : : .code = (BPF_JMP | EBPF_JLE | BPF_K),
2032 : : .imm = 10,
2033 : : },
2034 : : .pre.dst = make_signed_domain(20, 60),
2035 : : .jump = unreachable,
2036 : : }, also_signed), "(BPF_JMP | EBPF_JLE | BPF_K) check, range greater than imm");
2037 : :
2038 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2039 : : .tested_instruction = {
2040 : : .code = (BPF_JMP | BPF_JGT | BPF_K),
2041 : : .imm = 10,
2042 : : },
2043 : : .pre.dst = make_signed_domain(20, 60),
2044 : : .post = unreachable,
2045 : : }, also_signed), "(BPF_JMP | EBPF_JGT | BPF_K) check, range greater than imm");
2046 : :
2047 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2048 : : .tested_instruction = {
2049 : : .code = (BPF_JMP | BPF_JGE | BPF_K),
2050 : : .imm = 10,
2051 : : },
2052 : : .pre.dst = make_signed_domain(20, 60),
2053 : : .post = unreachable,
2054 : : }, also_signed), "(BPF_JMP | EBPF_JGE | BPF_K) check, range greater than imm");
2055 : :
2056 : : /*
2057 : : * 20 ---- dst ---- 60
2058 : : * imm
2059 : : */
2060 : :
2061 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2062 : : .tested_instruction = {
2063 : : .code = (BPF_JMP | EBPF_JLT | BPF_K),
2064 : : .imm = 70,
2065 : : },
2066 : : .pre.dst = make_signed_domain(20, 60),
2067 : : .post = unreachable,
2068 : : }, also_signed), "(BPF_JMP | EBPF_JLT | BPF_K) check, range less than imm");
2069 : :
2070 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2071 : : .tested_instruction = {
2072 : : .code = (BPF_JMP | EBPF_JLE | BPF_K),
2073 : : .imm = 70,
2074 : : },
2075 : : .pre.dst = make_signed_domain(20, 60),
2076 : : .post = unreachable,
2077 : : }, also_signed), "(BPF_JMP | EBPF_JLE | BPF_K) check, range less than imm");
2078 : :
2079 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2080 : : .tested_instruction = {
2081 : : .code = (BPF_JMP | BPF_JGT | BPF_K),
2082 : : .imm = 70,
2083 : : },
2084 : : .pre.dst = make_signed_domain(20, 60),
2085 : : .jump = unreachable,
2086 : : }, also_signed), "(BPF_JMP | EBPF_JGT | BPF_K) check, range less than imm");
2087 : :
2088 [ - + ]: 1 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2089 : : .tested_instruction = {
2090 : : .code = (BPF_JMP | BPF_JGE | BPF_K),
2091 : : .imm = 70,
2092 : : },
2093 : : .pre.dst = make_signed_domain(20, 60),
2094 : : .jump = unreachable,
2095 : : }, also_signed), "(BPF_JMP | EBPF_JGE | BPF_K) check, range less than imm");
2096 : :
2097 : 1 : return TEST_SUCCESS;
2098 : : }
2099 : :
2100 : : /* Jump on ordering comparisons with ranges "touching" each other. */
2101 : : static int
2102 : 1 : test_jmp64_ordering_touching(void)
2103 : : {
2104 : : /* All ranges used are valid for both signed and unsigned comparisons. */
2105 : : const bool also_signed = true;
2106 : :
2107 [ + + ]: 4 : for (int overlap = 0; overlap != 3; ++overlap) {
2108 : :
2109 : : /*
2110 : : * 20 - dst - 30
2111 : : * 10 - src - (19 + overlap)
2112 : : */
2113 : :
2114 [ + + - + ]: 3 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2115 : : .tested_instruction = {
2116 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
2117 : : },
2118 : : .pre.dst = make_signed_domain(20, 30),
2119 : : .pre.src = make_signed_domain(10, 19 + overlap),
2120 : : .jump = overlap <= 1 ? unreachable : (struct state){
2121 : : .dst = make_singleton_domain(20),
2122 : : .src = make_singleton_domain(21),
2123 : : },
2124 : : }, also_signed), "strict, dst left touching src right, overlap=%d", overlap);
2125 : :
2126 [ + + - + ]: 3 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2127 : : .tested_instruction = {
2128 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
2129 : : },
2130 : : .pre.dst = make_signed_domain(20, 30),
2131 : : .pre.src = make_signed_domain(10, 19 + overlap),
2132 : : .jump = overlap < 1 ? unreachable : (struct state){
2133 : : .dst = make_signed_domain(20, 19 + overlap),
2134 : : .src = make_signed_domain(20, 19 + overlap),
2135 : : },
2136 : : }, also_signed), "non-strict, dst left touching src right, overlap=%d", overlap);
2137 : :
2138 : : /*
2139 : : * 10 - dst - (19 + overlap)
2140 : : * 20 - src - 30
2141 : : */
2142 : :
2143 [ + + - + ]: 3 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2144 : : .tested_instruction = {
2145 : : .code = (BPF_JMP | EBPF_JLT | BPF_X),
2146 : : },
2147 : : .pre.dst = make_signed_domain(10, 19 + overlap),
2148 : : .pre.src = make_signed_domain(20, 30),
2149 : : .post = overlap < 1 ? unreachable : (struct state){
2150 : : .dst = make_signed_domain(20, 19 + overlap),
2151 : : .src = make_signed_domain(20, 19 + overlap),
2152 : : },
2153 : : }, also_signed), "strict, dst right touching src left, overlap=%d", overlap);
2154 : :
2155 [ + + - + ]: 3 : TEST_ASSERT_SUCCESS(verify_comparison((struct verify_instruction_param){
2156 : : .tested_instruction = {
2157 : : .code = (BPF_JMP | EBPF_JLE | BPF_X),
2158 : : },
2159 : : .pre.dst = make_signed_domain(10, 19 + overlap),
2160 : : .pre.src = make_signed_domain(20, 30),
2161 : : .post = overlap <= 1 ? unreachable : (struct state){
2162 : : .dst = make_singleton_domain(21),
2163 : : .src = make_singleton_domain(20),
2164 : : },
2165 : : }, also_signed), "non-strict, dst right touching src left, overlap=%d", overlap);
2166 : : }
2167 : :
2168 : : return TEST_SUCCESS;
2169 : : }
2170 : :
2171 : : /* 64-bit load from heap (should be set to unknown). */
2172 : : static int
2173 : 1 : test_mem_ldx_dw_heap(void)
2174 : : {
2175 : 1 : return verify_instruction((struct verify_instruction_param){
2176 : : .tested_instruction = {
2177 : : .code = (BPF_MEM | BPF_LDX | EBPF_DW),
2178 : : .off = 16,
2179 : : },
2180 : : .area_size = 24,
2181 : : .pre.src = make_pointer_domain(0, 0),
2182 : : .post.dst = unknown,
2183 : : });
2184 : : }
2185 : :
2186 : : static struct
2187 : : unit_test_suite test_bpf_validate_suite = {
2188 : : .suite_name = "Test BPF Validate Unit Test Suite",
2189 : : .unit_test_cases = {
2190 : : TEST_CASE(test_alu64_add_k),
2191 : : TEST_CASE(test_alu64_add_k_pointer),
2192 : : TEST_CASE(test_alu64_add_x_pointer_pointer),
2193 : : TEST_CASE(test_alu64_add_x_pointer_scalar),
2194 : : TEST_CASE(test_alu64_add_x_scalar_pointer),
2195 : : TEST_CASE(test_alu64_add_x_scalar_scalar),
2196 : : TEST_CASE(test_alu64_and_k),
2197 : : TEST_CASE(test_alu64_div_mod_big_constant),
2198 : : TEST_CASE(test_alu64_div_mod_big_range),
2199 : : TEST_CASE(test_alu64_div_mod_overflow),
2200 : : TEST_CASE(test_alu64_lsh_63),
2201 : : TEST_CASE(test_alu64_mul_k_overflow),
2202 : : TEST_CASE(test_alu64_mul_k_range_small),
2203 : : TEST_CASE(test_alu64_neg_int64min_first),
2204 : : TEST_CASE(test_alu64_neg_int64min_last),
2205 : : TEST_CASE(test_alu64_neg_zero_first),
2206 : : TEST_CASE(test_alu64_neg_zero_last),
2207 : : TEST_CASE(test_alu64_or_k_negative),
2208 : : TEST_CASE(test_alu64_or_k_positive),
2209 : : TEST_CASE(test_alu64_sub_x_src_signed_max_zero),
2210 : : TEST_CASE(test_alu64_xor_k_negative),
2211 : : TEST_CASE(test_jmp64_jeq_k),
2212 : : TEST_CASE(test_jmp64_jslt_x),
2213 : : TEST_CASE(test_jmp64_ordering_overflow),
2214 : : TEST_CASE(test_jmp64_ordering_ranges),
2215 : : TEST_CASE(test_jmp64_ordering_singleton_inside),
2216 : : TEST_CASE(test_jmp64_ordering_singleton_outside),
2217 : : TEST_CASE(test_jmp64_ordering_touching),
2218 : : TEST_CASE(test_mem_ldx_dw_heap),
2219 : : TEST_CASES_END()
2220 : : }
2221 : : };
2222 : :
2223 : : static int
2224 : 1 : test_bpf_validate(void)
2225 : : {
2226 : 1 : return unit_test_suite_runner(&test_bpf_validate_suite);
2227 : : }
2228 : :
2229 : 303 : REGISTER_FAST_TEST(bpf_validate_autotest, NOHUGE_OK, ASAN_OK, test_bpf_validate);
|
