Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2018 Intel Corporation
3 : : */
4 : :
5 : : #include <stdio.h>
6 : : #include <stdlib.h>
7 : : #include <string.h>
8 : : #include <errno.h>
9 : : #include <stdint.h>
10 : : #include <inttypes.h>
11 : :
12 : : #include <rte_bpf_validate_debug.h>
13 : : #include <rte_common.h>
14 : :
15 : : #include "bpf_impl.h"
16 : : #include "bpf_validate.h"
17 : : #include "bpf_validate_debug.h"
18 : : #include "bpf_value_set.h"
19 : :
20 : : #define BPF_ARG_PTR_STACK RTE_BPF_ARG_RESERVED
21 : :
22 : : /* type containing no values (AKA "bottom", "never" etc) */
23 : : #define BPF_ARG_UNINHABITED ((enum rte_bpf_arg_type)(RTE_BPF_ARG_UNDEF - 1))
24 : :
25 : : struct bpf_reg_val {
26 : : struct rte_bpf_arg v;
27 : : uint64_t mask;
28 : : struct {
29 : : int64_t min;
30 : : int64_t max;
31 : : } s;
32 : : struct {
33 : : uint64_t min;
34 : : uint64_t max;
35 : : } u;
36 : : };
37 : :
38 : : struct bpf_eval_state {
39 : : SLIST_ENTRY(bpf_eval_state) next; /* for @safe list traversal */
40 : : struct bpf_reg_val rv[EBPF_REG_NUM];
41 : : struct bpf_reg_val sv[MAX_BPF_STACK_SIZE / sizeof(uint64_t)];
42 : : /* flag set for branches determined to be dynamically unreachable */
43 : : bool unreachable;
44 : : };
45 : :
46 : : SLIST_HEAD(bpf_evst_head, bpf_eval_state);
47 : :
48 : : /* possible instruction node colour */
49 : : enum {
50 : : WHITE,
51 : : GREY,
52 : : BLACK,
53 : : MAX_NODE_COLOUR
54 : : };
55 : :
56 : : /* possible edge types */
57 : : enum {
58 : : UNKNOWN_EDGE,
59 : : TREE_EDGE,
60 : : BACK_EDGE,
61 : : CROSS_EDGE,
62 : : MAX_EDGE_TYPE
63 : : };
64 : :
65 : : #define MAX_EDGES 2
66 : :
67 : : /* max number of 'safe' evaluated states to track per node */
68 : : #define NODE_EVST_MAX 32
69 : :
70 : : struct inst_node {
71 : : uint8_t colour;
72 : : uint8_t nb_edge:4;
73 : : uint8_t cur_edge:4;
74 : : uint8_t edge_type[MAX_EDGES];
75 : : uint32_t edge_dest[MAX_EDGES];
76 : : struct inst_node *prev_node;
77 : : struct {
78 : : struct bpf_eval_state *cur; /* save/restore for jcc targets */
79 : : struct bpf_eval_state *start;
80 : : struct bpf_evst_head safe; /* safe states for track/prune */
81 : : uint32_t nb_safe;
82 : : } evst;
83 : : };
84 : :
85 : : struct evst_pool {
86 : : uint32_t num;
87 : : uint32_t cur;
88 : : struct bpf_eval_state *ent;
89 : : };
90 : :
91 : : struct bpf_verifier {
92 : : const struct rte_bpf_prm_ex *prm;
93 : : struct inst_node *in;
94 : : uint64_t stack_sz;
95 : : uint32_t nb_nodes;
96 : : uint32_t nb_jcc_nodes;
97 : : uint32_t nb_ldmb_nodes;
98 : : uint32_t node_colour[MAX_NODE_COLOUR];
99 : : uint32_t edge_type[MAX_EDGE_TYPE];
100 : : struct bpf_eval_state *evst;
101 : : struct inst_node *evin;
102 : : struct evst_pool evst_sr_pool; /* for evst save/restore */
103 : : struct evst_pool evst_tp_pool; /* for evst track/prune */
104 : : struct rte_bpf_validate_debug *debug;
105 : : };
106 : :
107 : : struct bpf_ins_check {
108 : : struct {
109 : : uint16_t dreg;
110 : : uint16_t sreg;
111 : : } mask;
112 : : struct {
113 : : uint16_t min;
114 : : uint16_t max;
115 : : } off;
116 : : struct {
117 : : uint32_t min;
118 : : uint32_t max;
119 : : } imm;
120 : : const char * (*check)(const struct ebpf_insn *);
121 : : const char * (*eval)(struct bpf_verifier *, const struct ebpf_insn *);
122 : : };
123 : :
124 : : #define ALL_REGS RTE_LEN2MASK(EBPF_REG_NUM, uint16_t)
125 : : #define WRT_REGS RTE_LEN2MASK(EBPF_REG_10, uint16_t)
126 : : #define ZERO_REG RTE_LEN2MASK(EBPF_REG_1, uint16_t)
127 : :
128 : : /* For LD_IND R6 is an implicit CTX register. */
129 : : #define IND_SRC_REGS (WRT_REGS ^ 1 << EBPF_REG_6)
130 : :
131 : : /*
132 : : * Debugging internal interface and helpers.
133 : : */
134 : :
135 : : static bool
136 : 408199 : reg_val_range_is_valid(const struct bpf_reg_val *rv)
137 : : {
138 [ + + ]: 408199 : if (rv->v.type == RTE_BPF_ARG_UNDEF)
139 : : return true;
140 : :
141 [ + - ]: 41805 : if (rv->s.min > rv->s.max)
142 : : return false;
143 : :
144 [ + - ]: 41805 : if (rv->u.min > rv->u.max)
145 : : return false;
146 : :
147 : : /* If one of the ranges does not change sign, the other should match. */
148 [ + + + + ]: 41805 : if (rv->s.min >= 0 || rv->s.max < 0 ||
149 [ + + + + ]: 5150 : rv->u.min > INT64_MAX || rv->u.max <= INT64_MAX)
150 [ + + ]: 78634 : return rv->u.min == (uint64_t)rv->s.min &&
151 [ + + ]: 34989 : rv->u.max == (uint64_t)rv->s.max;
152 : :
153 : : return true;
154 : : }
155 : :
156 : : int
157 : 10343 : __rte_bpf_validate_state_is_valid(const struct bpf_verifier *verifier)
158 : : {
159 : 10343 : const struct bpf_eval_state *const st = verifier->evst;
160 : :
161 [ + + ]: 79838 : for (int reg = 0; reg != RTE_DIM(st->rv); ++reg)
162 [ + + ]: 74655 : if (!reg_val_range_is_valid(st->rv + reg))
163 : : return false;
164 : :
165 [ + + ]: 336895 : for (int var = 0; var != RTE_DIM(st->sv); ++var)
166 [ + - ]: 331712 : if (!reg_val_range_is_valid(st->sv + var))
167 : : return false;
168 : :
169 : : return true;
170 : : }
171 : :
172 : : int
173 : 96 : __rte_bpf_validate_can_access(const struct bpf_verifier *verifier,
174 : : const struct ebpf_insn *access, uint64_t off64)
175 : : {
176 : 96 : const struct bpf_eval_state *const st = verifier->evst;
177 : : const struct bpf_reg_val *rv;
178 : : /* Set of accessed byte offsets relative to memory area base. */
179 : : struct value_set access_set;
180 : : uint32_t opsz;
181 : :
182 [ + - ]: 96 : if (st->unreachable)
183 : : return -ENOENT;
184 : :
185 [ + - - - ]: 96 : switch (BPF_CLASS(access->code)) {
186 : 96 : case BPF_LDX:
187 : 96 : rv = &st->rv[access->src_reg];
188 [ + - ]: 96 : if (rv->v.type == BPF_ARG_PTR_STACK)
189 : : /* Not supporting stack access queries yet. */
190 : : return -ENOTSUP;
191 : : break;
192 : 0 : case BPF_ST:
193 : 0 : rv = &st->rv[access->dst_reg];
194 : 0 : break;
195 : 0 : case BPF_STX:
196 : 0 : rv = &st->rv[access->dst_reg];
197 [ # # ]: 0 : if (st->rv[access->src_reg].v.type == RTE_BPF_ARG_UNDEF)
198 : : return false;
199 : : break;
200 : : default:
201 : : return -ENOTSUP;
202 : : }
203 : :
204 [ + - + - ]: 96 : if (!RTE_BPF_ARG_PTR_TYPE(rv->v.type) || rv->v.size == 0)
205 : : return false;
206 : :
207 : 96 : access_set = value_set_from_pair(rv->s.min, rv->s.max, rv->u.min, rv->u.max);
208 : 96 : value_set_translate(&access_set, off64);
209 [ - + ]: 96 : opsz = bpf_size(BPF_SIZE(access->code));
210 : 96 : value_set_add_contiguous(&access_set, 0, opsz - 1);
211 : :
212 : 96 : return value_set_is_covered_by_contiguous(&access_set, 0, rv->v.size - 1);
213 : : }
214 : :
215 : : /* Return true if instruction `code` is supported by `may_jump`. */
216 : : static bool
217 : 14608 : may_jump_code_is_supported(uint8_t code)
218 : : {
219 [ + - ]: 14608 : if (BPF_CLASS(code) != BPF_JMP)
220 : : return false;
221 : :
222 [ - + ]: 14608 : switch (BPF_OP(code)) {
223 : : case BPF_JEQ:
224 : : case BPF_JGT:
225 : : case BPF_JGE:
226 : : case EBPF_JNE:
227 : : case EBPF_JSGT:
228 : : case EBPF_JSGE:
229 : : case EBPF_JLT:
230 : : case EBPF_JLE:
231 : : case EBPF_JSLT:
232 : : case EBPF_JSLE:
233 : : return true;
234 : 0 : default:
235 : 0 : return false;
236 : : }
237 : : }
238 : :
239 : : /* Return true if instruction `code` corresponds to a signed comparison. */
240 : : static bool
241 : : may_jump_code_is_signed(uint8_t code)
242 : : {
243 : 14608 : switch (BPF_OP(code)) {
244 : : case EBPF_JSGT:
245 : : case EBPF_JSGE:
246 : : case EBPF_JSLT:
247 : : case EBPF_JSLE:
248 : : return true;
249 : : default:
250 : : return false;
251 : : }
252 : : }
253 : :
254 : : /* Return true the specified jump condition _may_ be true. */
255 : : static bool
256 : 29216 : may_jump(uint8_t code, const struct value_set *origin,
257 : : const struct value_set *dst_set, const struct value_set *src_set)
258 : : {
259 [ + + + + : 29216 : switch (BPF_OP(code)) {
+ + - ]
260 : 7304 : case BPF_JEQ:
261 : 7304 : return value_sets_intersect(dst_set, src_set);
262 : 7304 : case EBPF_JNE:
263 [ + + - + ]: 9276 : return !(value_set_is_singleton(dst_set) &&
264 : 1972 : value_sets_equal(dst_set, src_set));
265 : 3652 : case BPF_JGT:
266 : : case EBPF_JSGT:
267 : 3652 : return !value_sets_based_less_or_equal(origin, dst_set, src_set);
268 : 3652 : case BPF_JGE:
269 : : case EBPF_JSGE:
270 : 3652 : return !value_sets_based_less(origin, dst_set, src_set);
271 : 3652 : case EBPF_JLT:
272 : : case EBPF_JSLT:
273 : 3652 : return !value_sets_based_less_or_equal(origin, src_set, dst_set);
274 : 3652 : case EBPF_JSLE:
275 : : case EBPF_JLE:
276 : 3652 : return !value_sets_based_less(origin, src_set, dst_set);
277 : : }
278 : : /* may_jump_code_is_supported should have caught this */
279 : : RTE_ASSERT(false);
280 : : return false;
281 : : }
282 : :
283 : : /* Return instruction code for jump condition complement (negated result). */
284 : : static uint8_t
285 : 14608 : may_jump_code_complement(uint8_t code)
286 : : {
287 [ + + + + : 14608 : switch (BPF_OP(code)) {
+ - ]
288 : 7304 : case BPF_JEQ:
289 : : case EBPF_JNE:
290 : 7304 : return code ^ BPF_JEQ ^ EBPF_JNE;
291 : 1832 : case BPF_JGT:
292 : : case EBPF_JLE:
293 : 1832 : return code ^ BPF_JGT ^ EBPF_JLE;
294 : 1832 : case BPF_JGE:
295 : : case EBPF_JLT:
296 : 1832 : return code ^ BPF_JGE ^ EBPF_JLT;
297 : 1820 : case EBPF_JSGT:
298 : : case EBPF_JSLE:
299 : 1820 : return code ^ EBPF_JSGT ^ EBPF_JSLE;
300 : 1820 : case EBPF_JSGE:
301 : : case EBPF_JSLT:
302 : 1820 : return code ^ EBPF_JSGE ^ EBPF_JSLT;
303 : : }
304 : : /* may_jump_code_is_supported should have caught this */
305 : : RTE_ASSERT(false);
306 : : return 0;
307 : : }
308 : :
309 : : int
310 : 14608 : __rte_bpf_validate_may_jump(const struct bpf_verifier *verifier,
311 : : const struct ebpf_insn *jump, uint64_t imm64)
312 : : {
313 : 14608 : const struct bpf_eval_state *const st = verifier->evst;
314 : : const struct bpf_reg_val *rd, *rs;
315 : : struct value_set dst_set, src_set, origin;
316 : : int result;
317 : :
318 [ + - ]: 14608 : if (!may_jump_code_is_supported(jump->code))
319 : : return -ENOTSUP;
320 : :
321 [ + - ]: 14608 : if (st->unreachable)
322 : : /* Set no bits since neither false nor true is possible. */
323 : : return 0;
324 : :
325 : 14608 : rd = &st->rv[jump->dst_reg];
326 [ + - ]: 14608 : dst_set = (rd->v.type == RTE_BPF_ARG_UNDEF) ? value_set_full :
327 : 14608 : value_set_from_pair(rd->s.min, rd->s.max, rd->u.min, rd->u.max);
328 : :
329 [ + + ]: 14608 : rs = BPF_SRC(jump->code) == BPF_X ? &st->rv[jump->src_reg] : NULL;
330 : 14560 : src_set = rs == NULL ? value_set_singleton((int64_t)jump->imm) :
331 [ + - ]: 48 : rs->v.type == RTE_BPF_ARG_UNDEF ? value_set_full :
332 : 48 : value_set_from_pair(rs->s.min, rs->s.max, rs->u.min, rs->u.max);
333 : :
334 : 14608 : value_set_translate(&src_set, imm64);
335 : :
336 [ + + + - ]: 14608 : if (RTE_BPF_ARG_PTR_TYPE(rd->v.type) &&
337 [ + - ]: 48 : (rs != NULL && RTE_BPF_ARG_PTR_TYPE(rs->v.type)) &&
338 [ + - ]: 48 : rd->v.size == rs->v.size) {
339 : : /*
340 : : * Both sides are pointers with the same memory area size.
341 : : * Until tracking of memory areas is implemented we will consider them
342 : : * pointing to the same memory area just because of this.
343 : : * In this case our value sets represent offsets from the memory area base,
344 : : * which is some unknown distance from the scalar zero (NULL).
345 : : * We know however that the memory area cannot cross zero address.
346 : : * Thus range of origin relative to memory base starts with 1 byte gap
347 : : * after the memory area and ends just before it.
348 : : */
349 : 48 : origin = value_set_contiguous(rd->v.size + 1, -1);
350 : : } else {
351 : : /* Scalar value of a pointer depends on the memory area base address. */
352 [ - + ]: 14560 : if (RTE_BPF_ARG_PTR_TYPE(rd->v.type))
353 : 0 : value_set_add_contiguous(&dst_set, 1, UINT64_MAX - rd->v.size);
354 [ - + - - ]: 14560 : if (rs != NULL && RTE_BPF_ARG_PTR_TYPE(rs->v.type))
355 : 0 : value_set_add_contiguous(&dst_set, 1, UINT64_MAX - rs->v.size);
356 : 14560 : origin = value_set_singleton(0);
357 : : }
358 : :
359 [ + + ]: 14608 : if (may_jump_code_is_signed(jump->code))
360 : : /* Shift origin to the minimal value for signed comparisons. */
361 : 3640 : value_set_translate(&origin, INT64_MIN);
362 : :
363 : : result = 0;
364 : :
365 [ + + ]: 14608 : if (may_jump(jump->code, &origin, &dst_set, &src_set))
366 : : result |= RTE_BPF_VALIDATE_DEBUG_MAY_BE_TRUE;
367 : :
368 [ + + ]: 14608 : if (may_jump(may_jump_code_complement(jump->code), &origin, &dst_set, &src_set))
369 : 12636 : result |= RTE_BPF_VALIDATE_DEBUG_MAY_BE_FALSE;
370 : :
371 : : return result;
372 : : }
373 : :
374 : : /* Like snprintf, but advances (except for overflow) ptr and reduces szleft. */
375 : : __rte_format_printf(3, 4)
376 : : static int
377 : 680 : buf_printf(char **ptr, ssize_t *szleft, const char *format, ...)
378 : : {
379 : : va_list args;
380 : : int rc;
381 : :
382 : 680 : va_start(args, format);
383 [ + - ]: 680 : rc = vsnprintf(*ptr, RTE_MAX(0, *szleft), format, args);
384 : 680 : va_end(args);
385 : :
386 [ + - ]: 680 : if (rc > 0) {
387 : 680 : *szleft -= rc;
388 [ + - ]: 680 : if (*szleft > 0)
389 : 680 : *ptr += rc;
390 : : }
391 : :
392 : 680 : return rc;
393 : : }
394 : :
395 : : static int
396 : 1832 : format_memory_area(char **ptr, ssize_t *szleft, const struct bpf_reg_val *rv)
397 : : {
398 [ + - - - : 1832 : switch (rv->v.type) {
+ ]
399 : : case RTE_BPF_ARG_RAW:
400 : : return 0;
401 : 12 : case RTE_BPF_ARG_PTR:
402 : 12 : return buf_printf(ptr, szleft, "%%buffer<%zu> + ",
403 : 12 : (size_t)rv->v.size);
404 : 0 : case RTE_BPF_ARG_PTR_MBUF:
405 : 0 : return buf_printf(ptr, szleft, "%%mbuf<%zu, %zu> + ",
406 : 0 : (size_t)rv->v.size, (size_t)rv->v.buf_size);
407 : 0 : case BPF_ARG_PTR_STACK:
408 : 0 : return buf_printf(ptr, szleft, "%%stack + ");
409 : 0 : default:
410 : 0 : return -ENOTSUP;
411 : : }
412 : : }
413 : :
414 : : /* Format min..max interval using validate-debug API and updating ptr and szleft. */
415 : : static int
416 : 2166 : buf_print_interval(char **ptr, ssize_t *szleft, char format, uint64_t min, uint64_t max)
417 : : {
418 : : int rc;
419 : :
420 : 2166 : rc = rte_bpf_validate_debug_format_interval(*ptr, RTE_MAX(0, *szleft),
421 : : format, min, max);
422 : :
423 [ + - ]: 2166 : if (rc > 0) {
424 : 2166 : *szleft -= rc;
425 [ + - ]: 2166 : if (*szleft > 0)
426 : 2166 : *ptr += rc;
427 : : }
428 : :
429 : 2166 : return rc;
430 : : }
431 : :
432 : : /* Format rv roughly as "<signed-range> INTERSECT <unsigned-hex-range>" */
433 : : static int
434 : 1832 : format_register_range(char **ptr, ssize_t *szleft, const struct bpf_reg_val *rv)
435 : : {
436 : : int rc;
437 : : uint64_t expected_unsigned_min, expected_unsigned_max;
438 : 1832 : const bool valid = reg_val_range_is_valid(rv);
439 : :
440 : : /* Print signed unless trivial. */
441 [ + + + + : 1832 : if (!valid || rv->s.min != INT64_MIN || rv->s.max != INT64_MAX) {
+ + ]
442 : 1770 : rc = buf_print_interval(ptr, szleft, 'd', rv->s.min, rv->s.max);
443 [ + - ]: 1770 : if (rc < 0)
444 : : return rc;
445 : :
446 [ + + ]: 1770 : if (valid) {
447 : : /* Skip printing unsigned if it has expected values. */
448 [ + + + + ]: 1436 : if (rv->s.min >= 0 || rv->s.max < 0) {
449 : 1414 : expected_unsigned_min = (uint64_t)rv->s.min;
450 : 1414 : expected_unsigned_max = (uint64_t)rv->s.max;
451 : : } else {
452 : : expected_unsigned_min = 0;
453 : : expected_unsigned_max = UINT64_MAX;
454 : : }
455 : :
456 [ + - ]: 1436 : if (rv->u.min == expected_unsigned_min &&
457 [ - + ]: 1436 : rv->u.max == expected_unsigned_max)
458 : : return 0;
459 : : }
460 : :
461 : 334 : rc = buf_printf(ptr, szleft, " INTERSECT ");
462 [ + - ]: 334 : if (rc < 0)
463 : : return rc;
464 : : }
465 : :
466 : 396 : rc = buf_print_interval(ptr, szleft, 'x', rv->u.min, rv->u.max);
467 [ + - ]: 396 : if (rc < 0)
468 : : return rc;
469 : :
470 [ + + ]: 396 : if (!valid) {
471 : 334 : rc = buf_printf(ptr, szleft, " (!)");
472 : : if (rc < 0)
473 : : return rc;
474 : : }
475 : :
476 : : return 0;
477 : : }
478 : :
479 : : /* Format rv roughly as "<memory-object> + <offsets-range>" */
480 : : static int
481 : 1833 : format_reg_val(char *buffer, size_t bufsz, const struct bpf_reg_val *rv)
482 : : {
483 : 1833 : char *ptr = buffer;
484 : 1833 : ssize_t szleft = bufsz;
485 : : int rc;
486 : :
487 [ + + ]: 1833 : if (rv->v.type == RTE_BPF_ARG_UNDEF)
488 : 1 : return snprintf(buffer, bufsz, "%%undefined");
489 : :
490 : : /* Print data area info, if any. */
491 : 1832 : rc = format_memory_area(&ptr, &szleft, rv);
492 [ + - ]: 1832 : if (rc < 0)
493 : : return rc;
494 : :
495 : 1832 : rc = format_register_range(&ptr, &szleft, rv);
496 [ + - ]: 1832 : if (rc < 0)
497 : : return rc;
498 : :
499 : : /* At least one snprintf was called and added terminating zero. */
500 : : RTE_ASSERT(szleft < (ssize_t)bufsz);
501 : 1832 : --szleft;
502 : :
503 : 1832 : return bufsz - szleft;
504 : : }
505 : :
506 : : int
507 : 1833 : __rte_bpf_validate_format_register_info(const struct bpf_verifier *verifier,
508 : : char *buffer, size_t bufsz, uint8_t reg)
509 : : {
510 [ + - ]: 1833 : if (reg >= EBPF_REG_NUM)
511 : : return -EINVAL;
512 : :
513 : 1833 : return format_reg_val(buffer, bufsz, &verifier->evst->rv[reg]);
514 : : }
515 : :
516 : : int
517 : 0 : __rte_bpf_validate_format_frame_info(const struct bpf_verifier *verifier,
518 : : char *buffer, size_t bufsz, int32_t offset)
519 : : {
520 [ # # ]: 0 : if (offset % sizeof(uint64_t) != 0)
521 : : return -EINVAL;
522 : :
523 [ # # ]: 0 : if (offset >= 0 || offset < -MAX_BPF_STACK_SIZE)
524 : : return -ERANGE;
525 : :
526 : 0 : offset = (MAX_BPF_STACK_SIZE + offset) / sizeof(uint64_t);
527 : :
528 : 0 : return format_reg_val(buffer, bufsz, &verifier->evst->sv[offset]);
529 : : }
530 : :
531 : : int32_t
532 : 0 : __rte_bpf_validate_get_frame_size(const struct bpf_verifier *verifier)
533 : : {
534 [ # # ]: 0 : if (verifier->stack_sz > INT32_MAX)
535 : : return -ERANGE;
536 : :
537 : 0 : return verifier->stack_sz;
538 : : }
539 : :
540 : :
541 : : /*
542 : : * check and evaluate functions for particular instruction types.
543 : : */
544 : :
545 : : static const char *
546 : 8 : check_alu_bele(const struct ebpf_insn *ins)
547 : : {
548 [ + + - + ]: 8 : if (ins->imm != 16 && ins->imm != 32 && ins->imm != 64)
549 : 0 : return "invalid imm field";
550 : : return NULL;
551 : : }
552 : :
553 : : static const char *
554 : 3271 : eval_exit(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
555 : : {
556 : : RTE_SET_USED(ins);
557 [ + + ]: 3271 : if (bvf->evst->rv[EBPF_REG_0].v.type == RTE_BPF_ARG_UNDEF)
558 : 1 : return "undefined return value";
559 : : return NULL;
560 : : }
561 : :
562 : : /* setup max possible with this mask bounds */
563 : : static void
564 : : eval_umax_bound(struct bpf_reg_val *rv, uint64_t mask)
565 : : {
566 : 1434 : rv->u.max = mask;
567 : 1434 : rv->u.min = 0;
568 : 84 : }
569 : :
570 : : static void
571 : : eval_smax_bound(struct bpf_reg_val *rv, uint64_t mask)
572 : : {
573 : 4295 : rv->s.max = mask >> 1;
574 : 4295 : rv->s.min = rv->s.max ^ UINT64_MAX;
575 : 687 : }
576 : :
577 : : static void
578 : : eval_max_bound(struct bpf_reg_val *rv, uint64_t mask)
579 : : {
580 : : eval_umax_bound(rv, mask);
581 : : eval_smax_bound(rv, mask);
582 : 116 : }
583 : :
584 : : static void
585 : : eval_fill_max_bound(struct bpf_reg_val *rv, uint64_t mask)
586 : : {
587 : : eval_max_bound(rv, mask);
588 : 646 : rv->v.type = RTE_BPF_ARG_RAW;
589 : 646 : rv->mask = mask;
590 : 104 : }
591 : :
592 : : static void
593 : : eval_fill_imm64(struct bpf_reg_val *rv, uint64_t mask, uint64_t val)
594 : : {
595 : 5803 : rv->mask = mask;
596 : 5813 : rv->s.min = val;
597 : 5803 : rv->s.max = val;
598 : 5803 : rv->u.min = val;
599 : 5803 : rv->u.max = val;
600 : 1 : }
601 : :
602 : : static void
603 : : eval_fill_imm(struct bpf_reg_val *rv, uint64_t mask, int32_t imm)
604 : : {
605 : : uint64_t v;
606 : :
607 : 5332 : v = (uint64_t)imm & mask;
608 : :
609 : 0 : rv->v.type = RTE_BPF_ARG_RAW;
610 : : eval_fill_imm64(rv, mask, v);
611 : 115 : }
612 : :
613 : : static const char *
614 : 365 : eval_ld_imm64(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
615 : : {
616 : : uint32_t i;
617 : : uint64_t val;
618 : : struct bpf_reg_val *rd;
619 : :
620 : 365 : val = (uint32_t)ins[0].imm | (uint64_t)(uint32_t)ins[1].imm << 32;
621 : :
622 : 365 : rd = bvf->evst->rv + ins->dst_reg;
623 : 365 : rd->v.type = RTE_BPF_ARG_RAW;
624 : : eval_fill_imm64(rd, UINT64_MAX, val);
625 : :
626 [ - + ]: 365 : for (i = 0; i != bvf->prm->nb_xsym; i++) {
627 : :
628 : : /* load of external variable */
629 [ # # ]: 0 : if (bvf->prm->xsym[i].type == RTE_BPF_XTYPE_VAR &&
630 [ # # ]: 0 : (uintptr_t)bvf->prm->xsym[i].var.val == val) {
631 : 0 : rd->v = bvf->prm->xsym[i].var.desc;
632 : : eval_fill_imm64(rd, UINT64_MAX, 0);
633 : : break;
634 : : }
635 : : }
636 : :
637 : 365 : return NULL;
638 : : }
639 : :
640 : : static void
641 : : eval_apply_mask(struct bpf_reg_val *rv, uint64_t mask)
642 : : {
643 : : struct bpf_reg_val rt;
644 : :
645 : 2829 : rt.u.min = rv->u.min & mask;
646 : 2829 : rt.u.max = rv->u.max & mask;
647 [ + + - + : 2828 : if (rt.u.min != rv->u.min || rt.u.max != rv->u.max) {
+ - - + +
+ + - +
+ ]
648 : 13 : rv->u.max = RTE_MAX(rt.u.max, mask);
649 : 76 : rv->u.min = 0;
650 : : }
651 : :
652 : : eval_smax_bound(&rt, mask);
653 : 2829 : rv->s.max = RTE_MIN(rt.s.max, rv->s.max);
654 : 2829 : rv->s.min = RTE_MAX(rt.s.min, rv->s.min);
655 : :
656 : 2750 : rv->mask = mask;
657 : 496 : }
658 : :
659 : : static void
660 : 854 : eval_add(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
661 : : {
662 : : struct bpf_reg_val rs_buf;
663 : : struct bpf_reg_val rv;
664 : :
665 [ + + ]: 854 : if (RTE_BPF_ARG_PTR_TYPE(rs->v.type) != 0) {
666 [ + + ]: 8 : if (RTE_BPF_ARG_PTR_TYPE(rd->v.type) != 0) {
667 : : /* treat sum of pointers as sum of two unknown scalars */
668 : : eval_fill_max_bound(&rs_buf, msk);
669 : 1 : *rd = rs_buf;
670 : : rs = &rs_buf;
671 : : } else
672 : : /* scalar + pointer is a pointer of the same type */
673 : 7 : rd->v = rs->v;
674 : : }
675 : :
676 : 854 : rv.u.min = (rd->u.min + rs->u.min) & msk;
677 : 854 : rv.u.max = (rd->u.max + rs->u.max) & msk;
678 : 854 : rv.s.min = ((uint64_t)rd->s.min + (uint64_t)rs->s.min) & msk;
679 : 854 : rv.s.max = ((uint64_t)rd->s.max + (uint64_t)rs->s.max) & msk;
680 : :
681 : : /*
682 : : * if at least one of the operands is not constant,
683 : : * then check for overflow
684 : : */
685 [ + + + + : 854 : if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
+ - ]
686 [ + + ]: 102 : (rv.u.min < rd->u.min || rv.u.max < rd->u.max))
687 : : eval_umax_bound(&rv, msk);
688 : :
689 [ + + + + : 854 : if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
+ + ]
690 [ + + + + ]: 102 : (((rs->s.min < 0 && rv.s.min > rd->s.min) ||
691 [ - + ]: 71 : rv.s.min < rd->s.min) ||
692 [ - - + + ]: 71 : ((rs->s.max < 0 && rv.s.max > rd->s.max) ||
693 : : rv.s.max < rd->s.max)))
694 : : eval_smax_bound(&rv, msk);
695 : :
696 : 854 : rd->s = rv.s;
697 : 854 : rd->u = rv.u;
698 : 854 : }
699 : :
700 : : static void
701 : 10 : eval_sub(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
702 : : {
703 : : struct bpf_reg_val rv;
704 : :
705 : 10 : rv.u.min = (rd->u.min - rs->u.max) & msk;
706 : 10 : rv.u.max = (rd->u.max - rs->u.min) & msk;
707 : 10 : rv.s.min = ((uint64_t)rd->s.min - (uint64_t)rs->s.max) & msk;
708 : 10 : rv.s.max = ((uint64_t)rd->s.max - (uint64_t)rs->s.min) & msk;
709 : :
710 : : /*
711 : : * if at least one of the operands is not constant,
712 : : * then check for overflow
713 : : */
714 [ + + - + : 10 : if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
- + ]
715 [ # # ]: 0 : (rv.u.min > rd->u.min || rv.u.max > rd->u.max))
716 : : eval_umax_bound(&rv, msk);
717 : :
718 [ + + - + : 10 : if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
- + ]
719 [ - - + + ]: 7 : (((rs->s.max < 0 && rv.s.min < rd->s.min) ||
720 [ + - ]: 1 : rv.s.min > rd->s.min) ||
721 [ - + - - ]: 1 : ((rs->s.min < 0 && rv.s.max < rd->s.max) ||
722 : : rv.s.max > rd->s.max)))
723 : : eval_smax_bound(&rv, msk);
724 : :
725 : 10 : rd->s = rv.s;
726 : 10 : rd->u = rv.u;
727 : 10 : }
728 : :
729 : : static void
730 : 37 : eval_lsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
731 : : uint64_t msk)
732 : : {
733 : : /* check if shift value is less then max result bits */
734 [ + + ]: 37 : if (rs->u.max >= opsz) {
735 : : eval_max_bound(rd, msk);
736 : 2 : return;
737 : : }
738 : :
739 : : /* check for overflow */
740 [ + + ]: 35 : if (rd->u.max > RTE_LEN2MASK(opsz - rs->u.max, uint64_t))
741 : : eval_umax_bound(rd, msk);
742 : : else {
743 : 2 : rd->u.max <<= rs->u.max;
744 : 2 : rd->u.min <<= rs->u.min;
745 : : }
746 : :
747 : : /* check that dreg values are and would remain always positive */
748 [ + + + - ]: 68 : if ((uint64_t)rd->s.min >> (opsz - 1) != 0 || rd->s.max >=
749 [ + + ]: 33 : (rs->u.max == opsz - 1 ? 0 :
750 : 32 : RTE_LEN2MASK(opsz - rs->u.max - 1, int64_t)))
751 : : eval_smax_bound(rd, msk);
752 : : else {
753 : 0 : rd->s.max <<= rs->u.max;
754 : 0 : rd->s.min <<= rs->u.min;
755 : : }
756 : : }
757 : :
758 : : static void
759 : 16 : eval_rsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
760 : : uint64_t msk)
761 : : {
762 : : /* check if shift value is less then max result bits */
763 [ + + ]: 16 : if (rs->u.max >= opsz) {
764 : : eval_max_bound(rd, msk);
765 : 1 : return;
766 : : }
767 : :
768 : 15 : rd->u.max >>= rs->u.min;
769 : 15 : rd->u.min >>= rs->u.max;
770 : :
771 : : /* check that dreg values are always positive */
772 [ + + ]: 15 : if ((uint64_t)rd->s.min >> (opsz - 1) != 0)
773 : : eval_smax_bound(rd, msk);
774 : : else {
775 : 10 : rd->s.max >>= rs->u.min;
776 : 10 : rd->s.min >>= rs->u.max;
777 : : }
778 : : }
779 : :
780 : : static void
781 : 2 : eval_arsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
782 : : uint64_t msk)
783 : : {
784 : : uint32_t shv;
785 : :
786 : : /* check if shift value is less then max result bits */
787 [ + + ]: 2 : if (rs->u.max >= opsz) {
788 : : eval_max_bound(rd, msk);
789 : 1 : return;
790 : : }
791 : :
792 : 1 : rd->u.max = (int64_t)rd->u.max >> rs->u.min;
793 : 1 : rd->u.min = (int64_t)rd->u.min >> rs->u.max;
794 : :
795 : : /* if we have 32-bit values - extend them to 64-bit */
796 [ - + ]: 1 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
797 : 0 : rd->s.min <<= opsz;
798 : 0 : rd->s.max <<= opsz;
799 : : shv = opsz;
800 : : } else
801 : : shv = 0;
802 : :
803 [ + - ]: 1 : if (rd->s.min < 0)
804 : 1 : rd->s.min = (rd->s.min >> (rs->u.min + shv)) & msk;
805 : : else
806 : 0 : rd->s.min = (rd->s.min >> (rs->u.max + shv)) & msk;
807 : :
808 [ - + ]: 1 : if (rd->s.max < 0)
809 : 0 : rd->s.max = (rd->s.max >> (rs->u.max + shv)) & msk;
810 : : else
811 : 1 : rd->s.max = (rd->s.max >> (rs->u.min + shv)) & msk;
812 : : }
813 : :
814 : : static uint64_t
815 : : eval_umax_bits(uint64_t v, size_t opsz)
816 : : {
817 [ + + + - : 198 : if (v == 0)
+ - + - +
- + - ]
818 : : return 0;
819 : :
820 : : v = rte_clz64(v);
821 : 395 : return RTE_LEN2MASK(opsz - v, uint64_t);
822 : : }
823 : :
824 : : /* estimate max possible value for (v1 & v2) */
825 : : static uint64_t
826 : : eval_uand_max(uint64_t v1, uint64_t v2, size_t opsz)
827 : : {
828 : : v1 = eval_umax_bits(v1, opsz);
829 : : v2 = eval_umax_bits(v2, opsz);
830 : 185 : return (v1 & v2);
831 : : }
832 : :
833 : : /* estimate max possible value for (v1 | v2) */
834 : : static uint64_t
835 : : eval_uor_max(uint64_t v1, uint64_t v2, size_t opsz)
836 : : {
837 : : v1 = eval_umax_bits(v1, opsz);
838 : : v2 = eval_umax_bits(v2, opsz);
839 : 13 : return (v1 | v2);
840 : : }
841 : :
842 : : static void
843 : 93 : eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
844 : : uint64_t msk)
845 : : {
846 : : /* both operands are constants */
847 [ - + - - ]: 93 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
848 : 0 : rd->u.min &= rs->u.min;
849 : 0 : rd->u.max &= rs->u.max;
850 : : } else {
851 [ + - ]: 93 : rd->u.max = eval_uand_max(rd->u.max, rs->u.max, opsz);
852 : 93 : rd->u.min = 0;
853 : : }
854 : :
855 : : /* both operands are constants */
856 [ - + - - ]: 93 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
857 : 0 : rd->s.min &= rs->s.min;
858 : 0 : rd->s.max &= rs->s.max;
859 : : /* at least one of operand is non-negative */
860 [ + + + + ]: 93 : } else if (rd->s.min >= 0 || rs->s.min >= 0) {
861 : 184 : rd->s.max = eval_uand_max(rd->s.max & (msk >> 1),
862 [ + - ]: 92 : rs->s.max & (msk >> 1), opsz);
863 : 92 : rd->s.min = 0;
864 : : } else
865 : : eval_smax_bound(rd, msk);
866 : 93 : }
867 : :
868 : : static void
869 : 165 : eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
870 : : uint64_t msk)
871 : : {
872 : : /* both operands are constants */
873 [ + + + - ]: 165 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
874 : 159 : rd->u.min |= rs->u.min;
875 : 159 : rd->u.max |= rs->u.max;
876 : : } else {
877 [ + - ]: 6 : rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
878 : 6 : rd->u.min = RTE_MAX(rd->u.min, rs->u.min);
879 : : }
880 : :
881 : : /* both operands are constants */
882 [ + + + - ]: 165 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
883 : 159 : rd->s.min |= rs->s.min;
884 : 159 : rd->s.max |= rs->s.max;
885 : :
886 : : /* both operands are non-negative */
887 [ + + + + ]: 6 : } else if (rd->s.min >= 0 && rs->s.min >= 0) {
888 [ + - ]: 2 : rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
889 : 2 : rd->s.min = RTE_MAX(rd->s.min, rs->s.min);
890 : : } else
891 : : eval_smax_bound(rd, msk);
892 : 165 : }
893 : :
894 : : static void
895 : 119 : eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
896 : : uint64_t msk)
897 : : {
898 : : /* both operands are constants */
899 [ + + + - ]: 119 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
900 : 115 : rd->u.min ^= rs->u.min;
901 : 115 : rd->u.max ^= rs->u.max;
902 : : } else {
903 [ + - ]: 4 : rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
904 : 4 : rd->u.min = 0;
905 : : }
906 : :
907 : : /* both operands are constants */
908 [ + + + - ]: 119 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
909 : 115 : rd->s.min ^= rs->s.min;
910 : 115 : rd->s.max ^= rs->s.max;
911 : :
912 : : /* both operands are non-negative */
913 [ + + + - ]: 4 : } else if (rd->s.min >= 0 && rs->s.min >= 0) {
914 [ + - ]: 1 : rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
915 : 1 : rd->s.min = 0;
916 : : } else
917 : : eval_smax_bound(rd, msk);
918 : 119 : }
919 : :
920 : : static void
921 : 16 : eval_mul(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
922 : : uint64_t msk)
923 : : {
924 : : /* both operands are constants */
925 [ + + + + ]: 16 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
926 : 1 : rd->u.min = (rd->u.min * rs->u.min) & msk;
927 : 1 : rd->u.max = (rd->u.max * rs->u.max) & msk;
928 : : /* check for overflow */
929 [ + + + + ]: 15 : } else if (rd->u.max <= msk >> opsz / 2 && rs->u.max <= msk >> opsz) {
930 : 2 : rd->u.max *= rs->u.max;
931 : 2 : rd->u.min *= rs->u.min;
932 : : } else
933 : : eval_umax_bound(rd, msk);
934 : :
935 : : /* both operands are constants */
936 [ + + + + ]: 16 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
937 : 1 : rd->s.min = ((uint64_t)rd->s.min * (uint64_t)rs->s.min) & msk;
938 : 1 : rd->s.max = ((uint64_t)rd->s.max * (uint64_t)rs->s.max) & msk;
939 : : /* check that both operands are positive and no overflow */
940 [ + + + + ]: 15 : } else if (rd->s.min >= 0 && rs->s.min >= 0) {
941 : 13 : rd->s.max *= rs->s.max;
942 : 13 : rd->s.min *= rs->s.min;
943 : : } else
944 : : eval_smax_bound(rd, msk);
945 : 16 : }
946 : :
947 : : static const char *
948 : 47 : eval_divmod(uint32_t op, struct bpf_reg_val *rd, struct bpf_reg_val *rs, uint64_t msk)
949 : : {
950 : : /* both operands are constants */
951 [ + + + - ]: 47 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
952 [ + - ]: 24 : if (rs->u.max == 0)
953 : : return "division by 0";
954 [ + + ]: 24 : if (op == BPF_DIV) {
955 : 12 : rd->u.min /= rs->u.min;
956 : 12 : rd->u.max /= rs->u.max;
957 : : } else {
958 : 12 : rd->u.min %= rs->u.min;
959 : 12 : rd->u.max %= rs->u.max;
960 : : }
961 : : } else {
962 [ + + ]: 23 : if (op == BPF_MOD)
963 : 11 : rd->u.max = RTE_MIN(rd->u.max, rs->u.max - 1);
964 : : else
965 : : rd->u.max = rd->u.max;
966 : 23 : rd->u.min = 0;
967 : : }
968 : :
969 [ + + + + ]: 47 : if (rd->u.min >= (uint64_t)INT64_MIN || rd->u.max <= (uint64_t)INT64_MAX) {
970 : : /*
971 : : * All values have the same sign bit, which means range
972 : : * contiguous as unsigned is also contiguous as signed,
973 : : * so we can just reuse it without any changes.
974 : : */
975 : 34 : rd->s.min = rd->u.min;
976 : 34 : rd->s.max = rd->u.max;
977 : : } else
978 : : eval_smax_bound(rd, msk);
979 : :
980 : : return NULL;
981 : : }
982 : :
983 : : static void
984 : 41 : eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t msk)
985 : : {
986 : : uint64_t ux, uy;
987 : : int64_t sx, sy;
988 : : /* additional limits imposed by signed on unsigned and back */
989 : : struct bpf_reg_val cross_limits = {
990 : : .s = { INT64_MIN, INT64_MAX },
991 : : .u = { 0, UINT64_MAX },
992 : : };
993 : :
994 : : /* if we have 32-bit values - extend them to 64-bit */
995 [ + + ]: 41 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
996 : 1 : rd->u.min = (int32_t)rd->u.min;
997 : 1 : rd->u.max = (int32_t)rd->u.max;
998 : : }
999 : :
1000 [ + + ]: 41 : if (rd->u.min == 0) {
1001 : : /* special case: ranges that include 0 and, possibly, 1 */
1002 : :
1003 : : /*
1004 : : * Calculate requirements on the signed range of negation.
1005 : : * It is only possible when negated range does not cross from
1006 : : * INT64_MIN to INT64_MAX, which means our original range does
1007 : : * not reach (uint64_t)-INT64_MAX.
1008 : : */
1009 [ + + ]: 26 : if (rd->u.max < (uint64_t)-INT64_MAX) {
1010 : 9 : cross_limits.s.min = -rd->u.max;
1011 : : cross_limits.s.max = -rd->u.min;
1012 : : }
1013 : :
1014 [ + + ]: 26 : if (rd->u.max != 0)
1015 : 24 : rd->u.max = UINT64_MAX;
1016 : : } else {
1017 : 15 : ux = -rd->u.min & msk;
1018 : 15 : uy = -rd->u.max & msk;
1019 : :
1020 : 15 : rd->u.max = RTE_MAX(ux, uy);
1021 : 15 : rd->u.min = RTE_MIN(ux, uy);
1022 : : }
1023 : :
1024 : : /* if we have 32-bit values - extend them to 64-bit */
1025 [ + + ]: 41 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
1026 : 1 : rd->s.min = (int32_t)rd->s.min;
1027 : 1 : rd->s.max = (int32_t)rd->s.max;
1028 : : }
1029 : :
1030 [ + + ]: 41 : if (rd->s.min == INT64_MIN) {
1031 : : /* special case: negation of INT64_MIN is INT64_MIN */
1032 [ + + ]: 25 : if (rd->s.max <= 0) {
1033 : 8 : cross_limits.u.min = -(uint64_t)rd->s.max;
1034 : : cross_limits.u.max = -(uint64_t)rd->s.min;
1035 : : }
1036 [ + + ]: 25 : if (rd->s.max != INT64_MIN)
1037 : 23 : rd->s.max = INT64_MAX;
1038 : : } else {
1039 : : /* since max >= min, neither can be INT64_MIN here */
1040 : 16 : sx = -rd->s.min & msk;
1041 : 16 : sy = -rd->s.max & msk;
1042 : :
1043 : 16 : rd->s.max = RTE_MAX(sx, sy);
1044 : 16 : rd->s.min = RTE_MIN(sx, sy);
1045 : : }
1046 : :
1047 : 41 : rd->s.min = RTE_MAX(rd->s.min, cross_limits.s.min) & msk;
1048 : 41 : rd->s.max = RTE_MIN(rd->s.max, cross_limits.s.max) & msk;
1049 : 41 : rd->u.min = RTE_MAX(rd->u.min, cross_limits.u.min) & msk;
1050 : 41 : rd->u.max = RTE_MIN(rd->u.max, cross_limits.u.max) & msk;
1051 : 41 : }
1052 : :
1053 : : static const char *
1054 : 536 : eval_ld_mbuf(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1055 : : {
1056 : : uint32_t i, mode;
1057 : : struct bpf_reg_val *rv, ri, rs;
1058 : :
1059 : 536 : mode = BPF_MODE(ins->code);
1060 : :
1061 : : /* R6 is an implicit input that must contain pointer to mbuf */
1062 [ + - ]: 536 : if (bvf->evst->rv[EBPF_REG_6].v.type != RTE_BPF_ARG_PTR_MBUF)
1063 : : return "invalid type for implicit ctx register";
1064 : :
1065 [ + + ]: 536 : if (mode == BPF_IND) {
1066 : 69 : rs = bvf->evst->rv[ins->src_reg];
1067 [ + - ]: 69 : if (rs.v.type != RTE_BPF_ARG_RAW)
1068 : : return "unexpected type for src register";
1069 : :
1070 : 69 : eval_fill_imm(&ri, UINT64_MAX, ins->imm);
1071 : 69 : eval_add(&rs, &ri, UINT64_MAX);
1072 : :
1073 [ + - + - ]: 69 : if (rs.s.max < 0 || rs.u.min > UINT32_MAX)
1074 : : return "mbuf boundary violation";
1075 : : }
1076 : :
1077 : : /* R1-R5 scratch registers */
1078 [ + + ]: 3216 : for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
1079 : 2680 : bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;
1080 : :
1081 : : /* R0 is an implicit output, contains data fetched from the packet */
1082 : : rv = bvf->evst->rv + EBPF_REG_0;
1083 [ + + ]: 536 : rv->v.size = bpf_size(BPF_SIZE(ins->code));
1084 : 536 : eval_fill_max_bound(rv, RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
1085 : :
1086 : 536 : return NULL;
1087 : : }
1088 : :
1089 : : /*
1090 : : * check that destination and source operand are in defined state.
1091 : : */
1092 : : static const char *
1093 : : eval_defined(const struct bpf_reg_val *dst, const struct bpf_reg_val *src)
1094 : : {
1095 [ + - + - ]: 3838 : if (dst != NULL && dst->v.type == RTE_BPF_ARG_UNDEF)
1096 : : return "dest reg value is undefined";
1097 [ - + + - : 5655 : if (src != NULL && src->v.type == RTE_BPF_ARG_UNDEF)
+ + - + ]
1098 : : return "src reg value is undefined";
1099 : : return NULL;
1100 : : }
1101 : :
1102 : : static const char *
1103 : 2333 : eval_alu(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1104 : : {
1105 : : uint64_t msk;
1106 : : uint32_t op;
1107 : : size_t opsz, sz;
1108 : : const char *err;
1109 : : struct bpf_eval_state *st;
1110 : : struct bpf_reg_val *rd, rs;
1111 : :
1112 : 2333 : sz = (BPF_CLASS(ins->code) == BPF_ALU) ?
1113 [ + + ]: 2333 : sizeof(uint32_t) : sizeof(uint64_t);
1114 : 2333 : opsz = sz * CHAR_BIT;
1115 : 2333 : msk = RTE_LEN2MASK(opsz, uint64_t);
1116 : :
1117 : 2333 : st = bvf->evst;
1118 : 2333 : rd = st->rv + ins->dst_reg;
1119 : :
1120 [ + + ]: 2333 : if (BPF_SRC(ins->code) == BPF_X) {
1121 [ + + ]: 414 : rs = st->rv[ins->src_reg];
1122 : : eval_apply_mask(&rs, msk);
1123 : : } else {
1124 : 1919 : rs = (struct bpf_reg_val){.v = {.size = sz,},};
1125 : 1919 : eval_fill_imm(&rs, msk, ins->imm);
1126 : : }
1127 : :
1128 : : eval_apply_mask(rd, msk);
1129 : :
1130 : 2333 : op = BPF_OP(ins->code);
1131 : :
1132 : : /* Allow self-xor as way to zero register */
1133 [ + + + + ]: 2333 : if (op == BPF_XOR && BPF_SRC(ins->code) == BPF_X &&
1134 [ + + ]: 116 : ins->src_reg == ins->dst_reg) {
1135 : : eval_fill_imm(&rs, UINT64_MAX, 0);
1136 : : eval_fill_imm(rd, UINT64_MAX, 0);
1137 : : }
1138 : :
1139 [ + + + + ]: 2374 : err = eval_defined((op != EBPF_MOV) ? rd : NULL,
1140 : : (op != BPF_NEG) ? &rs : NULL);
1141 : : if (err != NULL)
1142 : 0 : return err;
1143 : :
1144 [ + + ]: 2333 : if (op == BPF_ADD)
1145 : 59 : eval_add(rd, &rs, msk);
1146 : : else if (op == BPF_SUB)
1147 : 10 : eval_sub(rd, &rs, msk);
1148 : : else if (op == BPF_LSH)
1149 : 37 : eval_lsh(rd, &rs, opsz, msk);
1150 : : else if (op == BPF_RSH)
1151 : 16 : eval_rsh(rd, &rs, opsz, msk);
1152 : : else if (op == EBPF_ARSH)
1153 : 2 : eval_arsh(rd, &rs, opsz, msk);
1154 : : else if (op == BPF_AND)
1155 : 93 : eval_and(rd, &rs, opsz, msk);
1156 : : else if (op == BPF_OR)
1157 : 165 : eval_or(rd, &rs, opsz, msk);
1158 : : else if (op == BPF_XOR)
1159 : 119 : eval_xor(rd, &rs, opsz, msk);
1160 : : else if (op == BPF_MUL)
1161 : 16 : eval_mul(rd, &rs, opsz, msk);
1162 : : else if (op == BPF_DIV || op == BPF_MOD)
1163 : 47 : err = eval_divmod(op, rd, &rs, msk);
1164 : : else if (op == BPF_NEG)
1165 : 41 : eval_neg(rd, opsz, msk);
1166 : : else if (op == EBPF_MOV)
1167 : 1728 : *rd = rs;
1168 : : else
1169 : : eval_max_bound(rd, msk);
1170 : :
1171 : : return err;
1172 : : }
1173 : :
1174 : : static const char *
1175 : 10 : eval_bele(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1176 : : {
1177 : : uint64_t msk;
1178 : : struct bpf_eval_state *st;
1179 : : struct bpf_reg_val *rd;
1180 : : const char *err;
1181 : :
1182 : 10 : msk = RTE_LEN2MASK(ins->imm, uint64_t);
1183 : :
1184 : 10 : st = bvf->evst;
1185 [ + - ]: 10 : rd = st->rv + ins->dst_reg;
1186 : :
1187 : : err = eval_defined(rd, NULL);
1188 : : if (err != NULL)
1189 : : return err;
1190 : :
1191 : : #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
1192 [ + + ]: 10 : if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_BE))
1193 : : eval_max_bound(rd, msk);
1194 : : else
1195 : : eval_apply_mask(rd, msk);
1196 : : #else
1197 : : if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_LE))
1198 : : eval_max_bound(rd, msk);
1199 : : else
1200 : : eval_apply_mask(rd, msk);
1201 : : #endif
1202 : :
1203 : : return NULL;
1204 : : }
1205 : :
1206 : : static const char *
1207 : 726 : eval_ptr(struct bpf_verifier *bvf, struct bpf_reg_val *rm, uint32_t opsz,
1208 : : uint32_t align, int16_t off)
1209 : : {
1210 : : struct bpf_reg_val rv;
1211 : :
1212 : : /* calculate reg + offset */
1213 : 726 : eval_fill_imm(&rv, rm->mask, off);
1214 : 726 : eval_add(rm, &rv, rm->mask);
1215 : :
1216 [ + + ]: 726 : if (RTE_BPF_ARG_PTR_TYPE(rm->v.type) == 0)
1217 : : return "destination is not a pointer";
1218 : :
1219 [ + - ]: 724 : if (rm->mask != UINT64_MAX)
1220 : : return "pointer truncation";
1221 : :
1222 [ + - ]: 724 : if (rm->u.max + opsz > rm->v.size ||
1223 [ + - ]: 724 : (uint64_t)rm->s.max + opsz > rm->v.size ||
1224 [ + - ]: 724 : rm->s.min < 0)
1225 : : return "memory boundary violation";
1226 : :
1227 [ + - ]: 724 : if (rm->u.max % align != 0)
1228 : : return "unaligned memory access";
1229 : :
1230 [ + + ]: 724 : if (rm->v.type == BPF_ARG_PTR_STACK) {
1231 : :
1232 [ + - + - : 43 : if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
+ - ]
1233 : : rm->u.max != (uint64_t)rm->s.max)
1234 : : return "stack access with variable offset";
1235 : :
1236 : 43 : bvf->stack_sz = RTE_MAX(bvf->stack_sz, rm->v.size - rm->u.max);
1237 : :
1238 : : /* pointer to mbuf */
1239 [ + + ]: 681 : } else if (rm->v.type == RTE_BPF_ARG_PTR_MBUF) {
1240 : :
1241 [ + - + - : 2 : if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
- + ]
1242 : : rm->u.max != (uint64_t)rm->s.max)
1243 : 0 : return "mbuf access with variable offset";
1244 : : }
1245 : :
1246 : : return NULL;
1247 : : }
1248 : :
1249 : : static void
1250 : : eval_max_load(struct bpf_reg_val *rv, uint64_t mask)
1251 : : {
1252 : : eval_umax_bound(rv, mask);
1253 : :
1254 : : /* full 64-bit load */
1255 [ - + + + ]: 609 : if (mask == UINT64_MAX)
1256 : : eval_smax_bound(rv, mask);
1257 : : else {
1258 : : /* zero-extend load */
1259 : 30 : rv->s.min = rv->u.min;
1260 : 30 : rv->s.max = rv->u.max;
1261 : : }
1262 : : }
1263 : :
1264 : :
1265 : : static const char *
1266 : 626 : eval_load(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1267 : : {
1268 : : uint32_t opsz;
1269 : : uint64_t msk;
1270 : : const char *err;
1271 : : struct bpf_eval_state *st;
1272 : : struct bpf_reg_val *rd, rs;
1273 : : const struct bpf_reg_val *sv;
1274 : :
1275 : 626 : st = bvf->evst;
1276 : 626 : rd = st->rv + ins->dst_reg;
1277 : 626 : rs = st->rv[ins->src_reg];
1278 [ + + ]: 626 : opsz = bpf_size(BPF_SIZE(ins->code));
1279 : 626 : msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);
1280 : :
1281 : 626 : err = eval_ptr(bvf, &rs, opsz, 1, ins->off);
1282 [ + - ]: 626 : if (err != NULL)
1283 : : return err;
1284 : :
1285 [ + + ]: 626 : if (rs.v.type == BPF_ARG_PTR_STACK) {
1286 : :
1287 : 17 : sv = st->sv + rs.u.max / sizeof(uint64_t);
1288 [ + - + - ]: 17 : if (sv->v.type == RTE_BPF_ARG_UNDEF || sv->mask < msk)
1289 : : return "undefined value on the stack";
1290 : :
1291 : 17 : *rd = *sv;
1292 : :
1293 : : /* pointer to mbuf */
1294 [ + + ]: 609 : } else if (rs.v.type == RTE_BPF_ARG_PTR_MBUF) {
1295 : :
1296 [ - + ]: 2 : if (rs.u.max == offsetof(struct rte_mbuf, next)) {
1297 : : eval_fill_imm(rd, msk, 0);
1298 : 0 : rd->v = rs.v;
1299 [ - + ]: 2 : } else if (rs.u.max == offsetof(struct rte_mbuf, buf_addr)) {
1300 : : eval_fill_imm(rd, msk, 0);
1301 : 0 : rd->v.type = RTE_BPF_ARG_PTR;
1302 : 0 : rd->v.size = rs.v.buf_size;
1303 [ - + ]: 2 : } else if (rs.u.max == offsetof(struct rte_mbuf, data_off)) {
1304 : : eval_fill_imm(rd, msk, RTE_PKTMBUF_HEADROOM);
1305 : : rd->v.type = RTE_BPF_ARG_RAW;
1306 : : } else {
1307 : : eval_max_load(rd, msk);
1308 : 2 : rd->v.type = RTE_BPF_ARG_RAW;
1309 : : }
1310 : :
1311 : : /* pointer to raw data */
1312 : : } else {
1313 : : eval_max_load(rd, msk);
1314 : 607 : rd->v.type = RTE_BPF_ARG_RAW;
1315 : : }
1316 : :
1317 : : return NULL;
1318 : : }
1319 : :
1320 : : static const char *
1321 : : eval_mbuf_store(const struct bpf_reg_val *rv, uint32_t opsz)
1322 : : {
1323 : : uint32_t i;
1324 : :
1325 : : static const struct {
1326 : : size_t off;
1327 : : size_t sz;
1328 : : } mbuf_ro_fileds[] = {
1329 : : { .off = offsetof(struct rte_mbuf, buf_addr), },
1330 : : { .off = offsetof(struct rte_mbuf, refcnt), },
1331 : : { .off = offsetof(struct rte_mbuf, nb_segs), },
1332 : : { .off = offsetof(struct rte_mbuf, buf_len), },
1333 : : { .off = offsetof(struct rte_mbuf, pool), },
1334 : : { .off = offsetof(struct rte_mbuf, next), },
1335 : : { .off = offsetof(struct rte_mbuf, priv_size), },
1336 : : };
1337 : :
1338 [ # # ]: 0 : for (i = 0; i != RTE_DIM(mbuf_ro_fileds) &&
1339 : 0 : (mbuf_ro_fileds[i].off + mbuf_ro_fileds[i].sz <=
1340 [ # # # # ]: 0 : rv->u.max || rv->u.max + opsz <= mbuf_ro_fileds[i].off);
1341 : 0 : i++)
1342 : : ;
1343 : :
1344 [ # # ]: 0 : if (i != RTE_DIM(mbuf_ro_fileds))
1345 : : return "store to the read-only mbuf field";
1346 : :
1347 : : return NULL;
1348 : :
1349 : : }
1350 : :
1351 : : static const char *
1352 : 313 : eval_store(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1353 : : {
1354 : : uint32_t opsz;
1355 : : uint64_t msk;
1356 : : const char *err;
1357 : : struct bpf_eval_state *st;
1358 : : struct bpf_reg_val rd, rs, *sv;
1359 : :
1360 [ + + ]: 313 : opsz = bpf_size(BPF_SIZE(ins->code));
1361 : 313 : msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);
1362 : :
1363 : 313 : st = bvf->evst;
1364 : 313 : rd = st->rv[ins->dst_reg];
1365 : :
1366 [ + + ]: 313 : if (BPF_CLASS(ins->code) == BPF_STX) {
1367 : 303 : rs = st->rv[ins->src_reg];
1368 [ + + ]: 303 : if (BPF_MODE(ins->code) == EBPF_ATOMIC)
1369 [ + + + ]: 260 : switch (ins->imm) {
1370 : : case BPF_ATOMIC_ADD:
1371 : : break;
1372 : 13 : case BPF_ATOMIC_XCHG:
1373 : : eval_max_bound(&st->rv[ins->src_reg], msk);
1374 : : break;
1375 : : default:
1376 : : return "unsupported atomic operation";
1377 : : }
1378 : : eval_apply_mask(&rs, msk);
1379 : : } else
1380 : 10 : eval_fill_imm(&rs, msk, ins->imm);
1381 : :
1382 : : err = eval_defined(NULL, &rs);
1383 : : if (err != NULL)
1384 : : return err;
1385 : :
1386 : 89 : err = eval_ptr(bvf, &rd, opsz, 1, ins->off);
1387 [ + + ]: 89 : if (err != NULL)
1388 : : return err;
1389 : :
1390 [ + + ]: 87 : if (rd.v.type == BPF_ARG_PTR_STACK) {
1391 : :
1392 : 17 : sv = st->sv + rd.u.max / sizeof(uint64_t);
1393 [ - + ]: 17 : if (BPF_CLASS(ins->code) == BPF_STX &&
1394 : : BPF_MODE(ins->code) == EBPF_ATOMIC)
1395 : : eval_max_bound(sv, msk);
1396 : : else
1397 : 17 : *sv = rs;
1398 : :
1399 : : /* pointer to mbuf */
1400 [ - + ]: 70 : } else if (rd.v.type == RTE_BPF_ARG_PTR_MBUF) {
1401 : : err = eval_mbuf_store(&rd, opsz);
1402 : : if (err != NULL)
1403 : 0 : return err;
1404 : : }
1405 : :
1406 : : return NULL;
1407 : : }
1408 : :
1409 : : static const char *
1410 : 199 : eval_ja(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1411 : : {
1412 : : RTE_SET_USED(bvf);
1413 : : RTE_SET_USED(ins);
1414 : 199 : return NULL;
1415 : : }
1416 : :
1417 : : static const char *
1418 : 116 : eval_func_arg(struct bpf_verifier *bvf, const struct rte_bpf_arg *arg,
1419 : : struct bpf_reg_val *rv)
1420 : : {
1421 : : uint32_t i, n;
1422 : : struct bpf_eval_state *st;
1423 : : const char *err;
1424 : :
1425 : 116 : st = bvf->evst;
1426 : :
1427 [ + - ]: 116 : if (rv->v.type == RTE_BPF_ARG_UNDEF)
1428 : : return "Undefined argument type";
1429 : :
1430 [ + + + - ]: 116 : if (arg->type != rv->v.type &&
1431 [ + - ]: 9 : arg->type != RTE_BPF_ARG_RAW &&
1432 : 9 : (arg->type != RTE_BPF_ARG_PTR ||
1433 [ + - ]: 9 : RTE_BPF_ARG_PTR_TYPE(rv->v.type) == 0))
1434 : : return "Invalid argument type";
1435 : :
1436 : : err = NULL;
1437 : :
1438 : : /* argument is a pointer */
1439 [ + + ]: 116 : if (RTE_BPF_ARG_PTR_TYPE(arg->type) != 0) {
1440 : :
1441 : 11 : err = eval_ptr(bvf, rv, arg->size, 1, 0);
1442 : :
1443 : : /*
1444 : : * pointer to the variable on the stack is passed
1445 : : * as an argument, mark stack space it occupies as initialized.
1446 : : */
1447 [ + - + + ]: 11 : if (err == NULL && rv->v.type == BPF_ARG_PTR_STACK) {
1448 : :
1449 : 9 : i = rv->u.max / sizeof(uint64_t);
1450 : 9 : n = i + arg->size / sizeof(uint64_t);
1451 [ + + ]: 14 : while (i != n) {
1452 : 5 : eval_fill_max_bound(st->sv + i, UINT64_MAX);
1453 : 5 : i++;
1454 : : };
1455 : : }
1456 : : }
1457 : :
1458 : : return err;
1459 : : }
1460 : :
1461 : : static const char *
1462 : 107 : eval_call(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1463 : : {
1464 : : uint32_t i, idx;
1465 : : struct bpf_reg_val *rv;
1466 : : const struct rte_bpf_xsym *xsym;
1467 : : const char *err;
1468 : :
1469 : 107 : idx = ins->imm;
1470 : :
1471 [ + - ]: 107 : if (idx >= bvf->prm->nb_xsym ||
1472 [ + - ]: 107 : bvf->prm->xsym[idx].type != RTE_BPF_XTYPE_FUNC)
1473 : : return "invalid external function index";
1474 : :
1475 : : /* for now don't support function calls on 32 bit platform */
1476 : : if (sizeof(uint64_t) != sizeof(uintptr_t))
1477 : : return "function calls are supported only for 64 bit apps";
1478 : :
1479 : : xsym = bvf->prm->xsym + idx;
1480 : :
1481 : : /* evaluate function arguments */
1482 : : err = NULL;
1483 [ + + + - ]: 223 : for (i = 0; i != xsym->func.nb_args && err == NULL; i++) {
1484 : 116 : err = eval_func_arg(bvf, xsym->func.args + i,
1485 : 116 : bvf->evst->rv + EBPF_REG_1 + i);
1486 : : }
1487 : :
1488 : : /* R1-R5 argument/scratch registers */
1489 [ + + ]: 642 : for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
1490 : 535 : bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;
1491 : :
1492 : : /* update return value */
1493 : :
1494 : 107 : rv = bvf->evst->rv + EBPF_REG_0;
1495 : 107 : rv->v = xsym->func.ret;
1496 [ + + ]: 107 : if (rv->v.type == RTE_BPF_ARG_RAW)
1497 : 104 : eval_fill_max_bound(rv,
1498 : 104 : RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
1499 [ + + ]: 3 : else if (RTE_BPF_ARG_PTR_TYPE(rv->v.type) != 0)
1500 : : eval_fill_imm64(rv, UINTPTR_MAX, 0);
1501 : :
1502 : : return err;
1503 : : }
1504 : :
1505 : : static void
1506 : 555 : eval_jeq_jne(struct bpf_reg_val *trd, struct bpf_reg_val *trs)
1507 : : {
1508 : : /* sreg is constant */
1509 [ + + ]: 555 : if (trs->u.min == trs->u.max) {
1510 : 537 : trd->u = trs->u;
1511 : : /* dreg is constant */
1512 [ + + ]: 18 : } else if (trd->u.min == trd->u.max) {
1513 : 8 : trs->u = trd->u;
1514 : : } else {
1515 : 10 : trd->u.max = RTE_MIN(trd->u.max, trs->u.max);
1516 : 10 : trd->u.min = RTE_MAX(trd->u.min, trs->u.min);
1517 : 10 : trs->u = trd->u;
1518 : : }
1519 : :
1520 : : /* sreg is constant */
1521 [ + + ]: 555 : if (trs->s.min == trs->s.max) {
1522 : 537 : trd->s = trs->s;
1523 : : /* dreg is constant */
1524 [ + + ]: 18 : } else if (trd->s.min == trd->s.max) {
1525 : 8 : trs->s = trd->s;
1526 : : } else {
1527 : 10 : trd->s.max = RTE_MIN(trd->s.max, trs->s.max);
1528 : 10 : trd->s.min = RTE_MAX(trd->s.min, trs->s.min);
1529 : 10 : trs->s = trd->s;
1530 : : }
1531 : 555 : }
1532 : :
1533 : : static void
1534 : : eval_jgt_jle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1535 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1536 : : {
1537 [ + + + + ]: 685 : if (frd->u.min <= frs->u.max) {
1538 : 669 : frd->u.max = RTE_MIN(frd->u.max, frs->u.max);
1539 : 669 : frs->u.min = RTE_MAX(frs->u.min, frd->u.min);
1540 : : } else
1541 : 16 : frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;
1542 : :
1543 [ + + + + ]: 685 : if (trs->u.min < trd->u.max) {
1544 : 645 : trd->u.min = RTE_MAX(trd->u.min, trs->u.min + 1);
1545 : 645 : trs->u.max = RTE_MIN(trs->u.max, trd->u.max - 1);
1546 : : } else
1547 : 40 : trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
1548 : : }
1549 : :
1550 : : static void
1551 : : eval_jlt_jge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1552 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1553 : : {
1554 [ + + + + ]: 612 : if (frs->u.min <= frd->u.max) {
1555 : 596 : frd->u.min = RTE_MAX(frd->u.min, frs->u.min);
1556 : 596 : frs->u.max = RTE_MIN(frs->u.max, frd->u.max);
1557 : : } else
1558 : 16 : frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;
1559 : :
1560 [ + + + + ]: 612 : if (trd->u.min < trs->u.max) {
1561 : 586 : trd->u.max = RTE_MIN(trd->u.max, trs->u.max - 1);
1562 : 586 : trs->u.min = RTE_MAX(trs->u.min, trd->u.min + 1);
1563 : : } else
1564 : 26 : trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
1565 : : }
1566 : :
1567 : : static void
1568 : : eval_jsgt_jsle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1569 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1570 : : {
1571 [ + + + + ]: 648 : if (frd->s.min <= frs->s.max) {
1572 : 632 : frd->s.max = RTE_MIN(frd->s.max, frs->s.max);
1573 : 632 : frs->s.min = RTE_MAX(frs->s.min, frd->s.min);
1574 : : } else
1575 : 16 : frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;
1576 : :
1577 [ + + + + ]: 648 : if (trs->s.min < trd->s.max) {
1578 : 604 : trd->s.min = RTE_MAX(trd->s.min, trs->s.min + 1);
1579 : 604 : trs->s.max = RTE_MIN(trs->s.max, trd->s.max - 1);
1580 : : } else
1581 : 44 : trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
1582 : : }
1583 : :
1584 : : static void
1585 : : eval_jslt_jsge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1586 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1587 : : {
1588 [ + + + + ]: 603 : if (frs->s.min <= frd->s.max) {
1589 : 587 : frd->s.min = RTE_MAX(frd->s.min, frs->s.min);
1590 : 587 : frs->s.max = RTE_MIN(frs->s.max, frd->s.max);
1591 : : } else
1592 : 16 : frd->v.type = frs->v.type = BPF_ARG_UNINHABITED;
1593 : :
1594 [ + + + + ]: 603 : if (trd->s.min < trs->s.max) {
1595 : 579 : trd->s.max = RTE_MIN(trd->s.max, trs->s.max - 1);
1596 : 579 : trs->s.min = RTE_MAX(trs->s.min, trd->s.min + 1);
1597 : : } else
1598 : 24 : trd->v.type = trs->v.type = BPF_ARG_UNINHABITED;
1599 : : }
1600 : :
1601 : : static const char *
1602 : 3233 : eval_jcc(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1603 : : {
1604 : : uint32_t op;
1605 : : const char *err;
1606 : : struct bpf_eval_state *fst, *tst;
1607 : : struct bpf_reg_val *frd, *frs, *trd, *trs;
1608 : : struct bpf_reg_val rvf, rvt;
1609 : :
1610 : 3233 : tst = bvf->evst;
1611 : 3233 : fst = bvf->evin->evst.cur;
1612 : :
1613 : 3233 : frd = fst->rv + ins->dst_reg;
1614 : 3233 : trd = tst->rv + ins->dst_reg;
1615 : :
1616 [ + + ]: 3233 : if (BPF_SRC(ins->code) == BPF_X) {
1617 : 625 : frs = fst->rv + ins->src_reg;
1618 : 625 : trs = tst->rv + ins->src_reg;
1619 : : } else {
1620 : : frs = &rvf;
1621 : : trs = &rvt;
1622 : 2608 : eval_fill_imm(frs, UINT64_MAX, ins->imm);
1623 : : eval_fill_imm(trs, UINT64_MAX, ins->imm);
1624 : : }
1625 : :
1626 : : err = eval_defined(trd, trs);
1627 : : if (err != NULL)
1628 : 0 : return err;
1629 : :
1630 : 3233 : op = BPF_OP(ins->code);
1631 : :
1632 [ + + ]: 3233 : if (op == BPF_JEQ)
1633 : 215 : eval_jeq_jne(trd, trs);
1634 [ + + ]: 3018 : else if (op == EBPF_JNE)
1635 : 340 : eval_jeq_jne(frd, frs);
1636 [ + + ]: 2678 : else if (op == BPF_JGT)
1637 : : eval_jgt_jle(trd, trs, frd, frs);
1638 [ + + ]: 2077 : else if (op == EBPF_JLE)
1639 : : eval_jgt_jle(frd, frs, trd, trs);
1640 [ + + ]: 1993 : else if (op == EBPF_JLT)
1641 : : eval_jlt_jge(trd, trs, frd, frs);
1642 [ + + ]: 1430 : else if (op == BPF_JGE)
1643 : : eval_jlt_jge(frd, frs, trd, trs);
1644 [ + + ]: 1381 : else if (op == EBPF_JSGT)
1645 : : eval_jsgt_jsle(trd, trs, frd, frs);
1646 [ + + ]: 775 : else if (op == EBPF_JSLE)
1647 : : eval_jsgt_jsle(frd, frs, trd, trs);
1648 [ + + ]: 733 : else if (op == EBPF_JSLT)
1649 : : eval_jslt_jsge(trd, trs, frd, frs);
1650 [ + + ]: 170 : else if (op == EBPF_JSGE)
1651 : : eval_jslt_jsge(frd, frs, trd, trs);
1652 : :
1653 [ + + ]: 3233 : if (trd->v.type == BPF_ARG_UNINHABITED ||
1654 [ - + ]: 3132 : trs->v.type == BPF_ARG_UNINHABITED)
1655 : 101 : tst->unreachable = true;
1656 : :
1657 [ + + ]: 3233 : if (frd->v.type == BPF_ARG_UNINHABITED ||
1658 [ - + ]: 3136 : frs->v.type == BPF_ARG_UNINHABITED)
1659 : 97 : fst->unreachable = true;
1660 : :
1661 : : return NULL;
1662 : : }
1663 : :
1664 : : /*
1665 : : * validate parameters for each instruction type.
1666 : : */
1667 : : static const struct bpf_ins_check ins_chk[UINT8_MAX + 1] = {
1668 : : /* ALU IMM 32-bit instructions */
1669 : : [(BPF_ALU | BPF_ADD | BPF_K)] = {
1670 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1671 : : .off = { .min = 0, .max = 0},
1672 : : .imm = { .min = 0, .max = UINT32_MAX,},
1673 : : .eval = eval_alu,
1674 : : },
1675 : : [(BPF_ALU | BPF_SUB | BPF_K)] = {
1676 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1677 : : .off = { .min = 0, .max = 0},
1678 : : .imm = { .min = 0, .max = UINT32_MAX,},
1679 : : .eval = eval_alu,
1680 : : },
1681 : : [(BPF_ALU | BPF_AND | BPF_K)] = {
1682 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1683 : : .off = { .min = 0, .max = 0},
1684 : : .imm = { .min = 0, .max = UINT32_MAX,},
1685 : : .eval = eval_alu,
1686 : : },
1687 : : [(BPF_ALU | BPF_OR | BPF_K)] = {
1688 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1689 : : .off = { .min = 0, .max = 0},
1690 : : .imm = { .min = 0, .max = UINT32_MAX,},
1691 : : .eval = eval_alu,
1692 : : },
1693 : : [(BPF_ALU | BPF_LSH | BPF_K)] = {
1694 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1695 : : .off = { .min = 0, .max = 0},
1696 : : .imm = { .min = 0, .max = UINT32_MAX,},
1697 : : .eval = eval_alu,
1698 : : },
1699 : : [(BPF_ALU | BPF_RSH | BPF_K)] = {
1700 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1701 : : .off = { .min = 0, .max = 0},
1702 : : .imm = { .min = 0, .max = UINT32_MAX,},
1703 : : .eval = eval_alu,
1704 : : },
1705 : : [(BPF_ALU | BPF_XOR | BPF_K)] = {
1706 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1707 : : .off = { .min = 0, .max = 0},
1708 : : .imm = { .min = 0, .max = UINT32_MAX,},
1709 : : .eval = eval_alu,
1710 : : },
1711 : : [(BPF_ALU | BPF_MUL | BPF_K)] = {
1712 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1713 : : .off = { .min = 0, .max = 0},
1714 : : .imm = { .min = 0, .max = UINT32_MAX,},
1715 : : .eval = eval_alu,
1716 : : },
1717 : : [(BPF_ALU | EBPF_MOV | BPF_K)] = {
1718 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1719 : : .off = { .min = 0, .max = 0},
1720 : : .imm = { .min = 0, .max = UINT32_MAX,},
1721 : : .eval = eval_alu,
1722 : : },
1723 : : [(BPF_ALU | BPF_DIV | BPF_K)] = {
1724 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1725 : : .off = { .min = 0, .max = 0},
1726 : : .imm = { .min = 1, .max = UINT32_MAX},
1727 : : .eval = eval_alu,
1728 : : },
1729 : : [(BPF_ALU | BPF_MOD | BPF_K)] = {
1730 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1731 : : .off = { .min = 0, .max = 0},
1732 : : .imm = { .min = 1, .max = UINT32_MAX},
1733 : : .eval = eval_alu,
1734 : : },
1735 : : /* ALU IMM 64-bit instructions */
1736 : : [(EBPF_ALU64 | BPF_ADD | BPF_K)] = {
1737 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1738 : : .off = { .min = 0, .max = 0},
1739 : : .imm = { .min = 0, .max = UINT32_MAX,},
1740 : : .eval = eval_alu,
1741 : : },
1742 : : [(EBPF_ALU64 | BPF_SUB | BPF_K)] = {
1743 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1744 : : .off = { .min = 0, .max = 0},
1745 : : .imm = { .min = 0, .max = UINT32_MAX,},
1746 : : .eval = eval_alu,
1747 : : },
1748 : : [(EBPF_ALU64 | BPF_AND | BPF_K)] = {
1749 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1750 : : .off = { .min = 0, .max = 0},
1751 : : .imm = { .min = 0, .max = UINT32_MAX,},
1752 : : .eval = eval_alu,
1753 : : },
1754 : : [(EBPF_ALU64 | BPF_OR | BPF_K)] = {
1755 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1756 : : .off = { .min = 0, .max = 0},
1757 : : .imm = { .min = 0, .max = UINT32_MAX,},
1758 : : .eval = eval_alu,
1759 : : },
1760 : : [(EBPF_ALU64 | BPF_LSH | BPF_K)] = {
1761 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1762 : : .off = { .min = 0, .max = 0},
1763 : : .imm = { .min = 0, .max = UINT32_MAX,},
1764 : : .eval = eval_alu,
1765 : : },
1766 : : [(EBPF_ALU64 | BPF_RSH | BPF_K)] = {
1767 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1768 : : .off = { .min = 0, .max = 0},
1769 : : .imm = { .min = 0, .max = UINT32_MAX,},
1770 : : .eval = eval_alu,
1771 : : },
1772 : : [(EBPF_ALU64 | EBPF_ARSH | BPF_K)] = {
1773 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1774 : : .off = { .min = 0, .max = 0},
1775 : : .imm = { .min = 0, .max = UINT32_MAX,},
1776 : : .eval = eval_alu,
1777 : : },
1778 : : [(EBPF_ALU64 | BPF_XOR | BPF_K)] = {
1779 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1780 : : .off = { .min = 0, .max = 0},
1781 : : .imm = { .min = 0, .max = UINT32_MAX,},
1782 : : .eval = eval_alu,
1783 : : },
1784 : : [(EBPF_ALU64 | BPF_MUL | BPF_K)] = {
1785 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1786 : : .off = { .min = 0, .max = 0},
1787 : : .imm = { .min = 0, .max = UINT32_MAX,},
1788 : : .eval = eval_alu,
1789 : : },
1790 : : [(EBPF_ALU64 | EBPF_MOV | BPF_K)] = {
1791 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1792 : : .off = { .min = 0, .max = 0},
1793 : : .imm = { .min = 0, .max = UINT32_MAX,},
1794 : : .eval = eval_alu,
1795 : : },
1796 : : [(EBPF_ALU64 | BPF_DIV | BPF_K)] = {
1797 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1798 : : .off = { .min = 0, .max = 0},
1799 : : .imm = { .min = 1, .max = UINT32_MAX},
1800 : : .eval = eval_alu,
1801 : : },
1802 : : [(EBPF_ALU64 | BPF_MOD | BPF_K)] = {
1803 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1804 : : .off = { .min = 0, .max = 0},
1805 : : .imm = { .min = 1, .max = UINT32_MAX},
1806 : : .eval = eval_alu,
1807 : : },
1808 : : /* ALU REG 32-bit instructions */
1809 : : [(BPF_ALU | BPF_ADD | BPF_X)] = {
1810 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1811 : : .off = { .min = 0, .max = 0},
1812 : : .imm = { .min = 0, .max = 0},
1813 : : .eval = eval_alu,
1814 : : },
1815 : : [(BPF_ALU | BPF_SUB | BPF_X)] = {
1816 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1817 : : .off = { .min = 0, .max = 0},
1818 : : .imm = { .min = 0, .max = 0},
1819 : : .eval = eval_alu,
1820 : : },
1821 : : [(BPF_ALU | BPF_AND | BPF_X)] = {
1822 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1823 : : .off = { .min = 0, .max = 0},
1824 : : .imm = { .min = 0, .max = 0},
1825 : : .eval = eval_alu,
1826 : : },
1827 : : [(BPF_ALU | BPF_OR | BPF_X)] = {
1828 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1829 : : .off = { .min = 0, .max = 0},
1830 : : .imm = { .min = 0, .max = 0},
1831 : : .eval = eval_alu,
1832 : : },
1833 : : [(BPF_ALU | BPF_LSH | BPF_X)] = {
1834 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1835 : : .off = { .min = 0, .max = 0},
1836 : : .imm = { .min = 0, .max = 0},
1837 : : .eval = eval_alu,
1838 : : },
1839 : : [(BPF_ALU | BPF_RSH | BPF_X)] = {
1840 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1841 : : .off = { .min = 0, .max = 0},
1842 : : .imm = { .min = 0, .max = 0},
1843 : : .eval = eval_alu,
1844 : : },
1845 : : [(BPF_ALU | BPF_XOR | BPF_X)] = {
1846 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1847 : : .off = { .min = 0, .max = 0},
1848 : : .imm = { .min = 0, .max = 0},
1849 : : .eval = eval_alu,
1850 : : },
1851 : : [(BPF_ALU | BPF_MUL | BPF_X)] = {
1852 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1853 : : .off = { .min = 0, .max = 0},
1854 : : .imm = { .min = 0, .max = 0},
1855 : : .eval = eval_alu,
1856 : : },
1857 : : [(BPF_ALU | BPF_DIV | BPF_X)] = {
1858 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1859 : : .off = { .min = 0, .max = 0},
1860 : : .imm = { .min = 0, .max = 0},
1861 : : .eval = eval_alu,
1862 : : },
1863 : : [(BPF_ALU | BPF_MOD | BPF_X)] = {
1864 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1865 : : .off = { .min = 0, .max = 0},
1866 : : .imm = { .min = 0, .max = 0},
1867 : : .eval = eval_alu,
1868 : : },
1869 : : [(BPF_ALU | EBPF_MOV | BPF_X)] = {
1870 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1871 : : .off = { .min = 0, .max = 0},
1872 : : .imm = { .min = 0, .max = 0},
1873 : : .eval = eval_alu,
1874 : : },
1875 : : [(BPF_ALU | BPF_NEG)] = {
1876 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1877 : : .off = { .min = 0, .max = 0},
1878 : : .imm = { .min = 0, .max = 0},
1879 : : .eval = eval_alu,
1880 : : },
1881 : : [(BPF_ALU | EBPF_END | EBPF_TO_BE)] = {
1882 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1883 : : .off = { .min = 0, .max = 0},
1884 : : .imm = { .min = 16, .max = 64},
1885 : : .check = check_alu_bele,
1886 : : .eval = eval_bele,
1887 : : },
1888 : : [(BPF_ALU | EBPF_END | EBPF_TO_LE)] = {
1889 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1890 : : .off = { .min = 0, .max = 0},
1891 : : .imm = { .min = 16, .max = 64},
1892 : : .check = check_alu_bele,
1893 : : .eval = eval_bele,
1894 : : },
1895 : : /* ALU REG 64-bit instructions */
1896 : : [(EBPF_ALU64 | BPF_ADD | BPF_X)] = {
1897 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1898 : : .off = { .min = 0, .max = 0},
1899 : : .imm = { .min = 0, .max = 0},
1900 : : .eval = eval_alu,
1901 : : },
1902 : : [(EBPF_ALU64 | BPF_SUB | BPF_X)] = {
1903 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1904 : : .off = { .min = 0, .max = 0},
1905 : : .imm = { .min = 0, .max = 0},
1906 : : .eval = eval_alu,
1907 : : },
1908 : : [(EBPF_ALU64 | BPF_AND | BPF_X)] = {
1909 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1910 : : .off = { .min = 0, .max = 0},
1911 : : .imm = { .min = 0, .max = 0},
1912 : : .eval = eval_alu,
1913 : : },
1914 : : [(EBPF_ALU64 | BPF_OR | BPF_X)] = {
1915 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1916 : : .off = { .min = 0, .max = 0},
1917 : : .imm = { .min = 0, .max = 0},
1918 : : .eval = eval_alu,
1919 : : },
1920 : : [(EBPF_ALU64 | BPF_LSH | BPF_X)] = {
1921 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1922 : : .off = { .min = 0, .max = 0},
1923 : : .imm = { .min = 0, .max = 0},
1924 : : .eval = eval_alu,
1925 : : },
1926 : : [(EBPF_ALU64 | BPF_RSH | BPF_X)] = {
1927 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1928 : : .off = { .min = 0, .max = 0},
1929 : : .imm = { .min = 0, .max = 0},
1930 : : .eval = eval_alu,
1931 : : },
1932 : : [(EBPF_ALU64 | EBPF_ARSH | BPF_X)] = {
1933 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1934 : : .off = { .min = 0, .max = 0},
1935 : : .imm = { .min = 0, .max = 0},
1936 : : .eval = eval_alu,
1937 : : },
1938 : : [(EBPF_ALU64 | BPF_XOR | BPF_X)] = {
1939 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1940 : : .off = { .min = 0, .max = 0},
1941 : : .imm = { .min = 0, .max = 0},
1942 : : .eval = eval_alu,
1943 : : },
1944 : : [(EBPF_ALU64 | BPF_MUL | BPF_X)] = {
1945 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1946 : : .off = { .min = 0, .max = 0},
1947 : : .imm = { .min = 0, .max = 0},
1948 : : .eval = eval_alu,
1949 : : },
1950 : : [(EBPF_ALU64 | BPF_DIV | BPF_X)] = {
1951 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1952 : : .off = { .min = 0, .max = 0},
1953 : : .imm = { .min = 0, .max = 0},
1954 : : .eval = eval_alu,
1955 : : },
1956 : : [(EBPF_ALU64 | BPF_MOD | BPF_X)] = {
1957 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1958 : : .off = { .min = 0, .max = 0},
1959 : : .imm = { .min = 0, .max = 0},
1960 : : .eval = eval_alu,
1961 : : },
1962 : : [(EBPF_ALU64 | EBPF_MOV | BPF_X)] = {
1963 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1964 : : .off = { .min = 0, .max = 0},
1965 : : .imm = { .min = 0, .max = 0},
1966 : : .eval = eval_alu,
1967 : : },
1968 : : [(EBPF_ALU64 | BPF_NEG)] = {
1969 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1970 : : .off = { .min = 0, .max = 0},
1971 : : .imm = { .min = 0, .max = 0},
1972 : : .eval = eval_alu,
1973 : : },
1974 : : /* load instructions */
1975 : : [(BPF_LDX | BPF_MEM | BPF_B)] = {
1976 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1977 : : .off = { .min = 0, .max = UINT16_MAX},
1978 : : .imm = { .min = 0, .max = 0},
1979 : : .eval = eval_load,
1980 : : },
1981 : : [(BPF_LDX | BPF_MEM | BPF_H)] = {
1982 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1983 : : .off = { .min = 0, .max = UINT16_MAX},
1984 : : .imm = { .min = 0, .max = 0},
1985 : : .eval = eval_load,
1986 : : },
1987 : : [(BPF_LDX | BPF_MEM | BPF_W)] = {
1988 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1989 : : .off = { .min = 0, .max = UINT16_MAX},
1990 : : .imm = { .min = 0, .max = 0},
1991 : : .eval = eval_load,
1992 : : },
1993 : : [(BPF_LDX | BPF_MEM | EBPF_DW)] = {
1994 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1995 : : .off = { .min = 0, .max = UINT16_MAX},
1996 : : .imm = { .min = 0, .max = 0},
1997 : : .eval = eval_load,
1998 : : },
1999 : : /* load 64 bit immediate value */
2000 : : [(BPF_LD | BPF_IMM | EBPF_DW)] = {
2001 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
2002 : : .off = { .min = 0, .max = 0},
2003 : : .imm = { .min = 0, .max = UINT32_MAX},
2004 : : .eval = eval_ld_imm64,
2005 : : },
2006 : : /* load absolute instructions */
2007 : : [(BPF_LD | BPF_ABS | BPF_B)] = {
2008 : : .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
2009 : : .off = { .min = 0, .max = 0},
2010 : : .imm = { .min = 0, .max = INT32_MAX},
2011 : : .eval = eval_ld_mbuf,
2012 : : },
2013 : : [(BPF_LD | BPF_ABS | BPF_H)] = {
2014 : : .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
2015 : : .off = { .min = 0, .max = 0},
2016 : : .imm = { .min = 0, .max = INT32_MAX},
2017 : : .eval = eval_ld_mbuf,
2018 : : },
2019 : : [(BPF_LD | BPF_ABS | BPF_W)] = {
2020 : : .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
2021 : : .off = { .min = 0, .max = 0},
2022 : : .imm = { .min = 0, .max = INT32_MAX},
2023 : : .eval = eval_ld_mbuf,
2024 : : },
2025 : : /* load indirect instructions */
2026 : : [(BPF_LD | BPF_IND | BPF_B)] = {
2027 : : .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
2028 : : .off = { .min = 0, .max = 0},
2029 : : .imm = { .min = 0, .max = UINT32_MAX},
2030 : : .eval = eval_ld_mbuf,
2031 : : },
2032 : : [(BPF_LD | BPF_IND | BPF_H)] = {
2033 : : .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
2034 : : .off = { .min = 0, .max = 0},
2035 : : .imm = { .min = 0, .max = UINT32_MAX},
2036 : : .eval = eval_ld_mbuf,
2037 : : },
2038 : : [(BPF_LD | BPF_IND | BPF_W)] = {
2039 : : .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
2040 : : .off = { .min = 0, .max = 0},
2041 : : .imm = { .min = 0, .max = UINT32_MAX},
2042 : : .eval = eval_ld_mbuf,
2043 : : },
2044 : : /* store REG instructions */
2045 : : [(BPF_STX | BPF_MEM | BPF_B)] = {
2046 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2047 : : .off = { .min = 0, .max = UINT16_MAX},
2048 : : .imm = { .min = 0, .max = 0},
2049 : : .eval = eval_store,
2050 : : },
2051 : : [(BPF_STX | BPF_MEM | BPF_H)] = {
2052 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2053 : : .off = { .min = 0, .max = UINT16_MAX},
2054 : : .imm = { .min = 0, .max = 0},
2055 : : .eval = eval_store,
2056 : : },
2057 : : [(BPF_STX | BPF_MEM | BPF_W)] = {
2058 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2059 : : .off = { .min = 0, .max = UINT16_MAX},
2060 : : .imm = { .min = 0, .max = 0},
2061 : : .eval = eval_store,
2062 : : },
2063 : : [(BPF_STX | BPF_MEM | EBPF_DW)] = {
2064 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2065 : : .off = { .min = 0, .max = UINT16_MAX},
2066 : : .imm = { .min = 0, .max = 0},
2067 : : .eval = eval_store,
2068 : : },
2069 : : /* atomic instructions */
2070 : : [(BPF_STX | EBPF_ATOMIC | BPF_W)] = {
2071 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2072 : : .off = { .min = 0, .max = UINT16_MAX},
2073 : : .imm = { .min = BPF_ATOMIC_ADD, .max = BPF_ATOMIC_XCHG},
2074 : : .eval = eval_store,
2075 : : },
2076 : : [(BPF_STX | EBPF_ATOMIC | EBPF_DW)] = {
2077 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2078 : : .off = { .min = 0, .max = UINT16_MAX},
2079 : : .imm = { .min = BPF_ATOMIC_ADD, .max = BPF_ATOMIC_XCHG},
2080 : : .eval = eval_store,
2081 : : },
2082 : : /* store IMM instructions */
2083 : : [(BPF_ST | BPF_MEM | BPF_B)] = {
2084 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2085 : : .off = { .min = 0, .max = UINT16_MAX},
2086 : : .imm = { .min = 0, .max = UINT32_MAX},
2087 : : .eval = eval_store,
2088 : : },
2089 : : [(BPF_ST | BPF_MEM | BPF_H)] = {
2090 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2091 : : .off = { .min = 0, .max = UINT16_MAX},
2092 : : .imm = { .min = 0, .max = UINT32_MAX},
2093 : : .eval = eval_store,
2094 : : },
2095 : : [(BPF_ST | BPF_MEM | BPF_W)] = {
2096 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2097 : : .off = { .min = 0, .max = UINT16_MAX},
2098 : : .imm = { .min = 0, .max = UINT32_MAX},
2099 : : .eval = eval_store,
2100 : : },
2101 : : [(BPF_ST | BPF_MEM | EBPF_DW)] = {
2102 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2103 : : .off = { .min = 0, .max = UINT16_MAX},
2104 : : .imm = { .min = 0, .max = UINT32_MAX},
2105 : : .eval = eval_store,
2106 : : },
2107 : : /* jump instruction */
2108 : : [(BPF_JMP | BPF_JA)] = {
2109 : : .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
2110 : : .off = { .min = 0, .max = UINT16_MAX},
2111 : : .imm = { .min = 0, .max = 0},
2112 : : .eval = eval_ja,
2113 : : },
2114 : : /* jcc IMM instructions */
2115 : : [(BPF_JMP | BPF_JEQ | BPF_K)] = {
2116 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2117 : : .off = { .min = 0, .max = UINT16_MAX},
2118 : : .imm = { .min = 0, .max = UINT32_MAX},
2119 : : .eval = eval_jcc,
2120 : : },
2121 : : [(BPF_JMP | EBPF_JNE | BPF_K)] = {
2122 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2123 : : .off = { .min = 0, .max = UINT16_MAX},
2124 : : .imm = { .min = 0, .max = UINT32_MAX},
2125 : : .eval = eval_jcc,
2126 : : },
2127 : : [(BPF_JMP | BPF_JGT | BPF_K)] = {
2128 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2129 : : .off = { .min = 0, .max = UINT16_MAX},
2130 : : .imm = { .min = 0, .max = UINT32_MAX},
2131 : : .eval = eval_jcc,
2132 : : },
2133 : : [(BPF_JMP | EBPF_JLT | BPF_K)] = {
2134 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2135 : : .off = { .min = 0, .max = UINT16_MAX},
2136 : : .imm = { .min = 0, .max = UINT32_MAX},
2137 : : .eval = eval_jcc,
2138 : : },
2139 : : [(BPF_JMP | BPF_JGE | BPF_K)] = {
2140 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2141 : : .off = { .min = 0, .max = UINT16_MAX},
2142 : : .imm = { .min = 0, .max = UINT32_MAX},
2143 : : .eval = eval_jcc,
2144 : : },
2145 : : [(BPF_JMP | EBPF_JLE | BPF_K)] = {
2146 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2147 : : .off = { .min = 0, .max = UINT16_MAX},
2148 : : .imm = { .min = 0, .max = UINT32_MAX},
2149 : : .eval = eval_jcc,
2150 : : },
2151 : : [(BPF_JMP | EBPF_JSGT | BPF_K)] = {
2152 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2153 : : .off = { .min = 0, .max = UINT16_MAX},
2154 : : .imm = { .min = 0, .max = UINT32_MAX},
2155 : : .eval = eval_jcc,
2156 : : },
2157 : : [(BPF_JMP | EBPF_JSLT | BPF_K)] = {
2158 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2159 : : .off = { .min = 0, .max = UINT16_MAX},
2160 : : .imm = { .min = 0, .max = UINT32_MAX},
2161 : : .eval = eval_jcc,
2162 : : },
2163 : : [(BPF_JMP | EBPF_JSGE | BPF_K)] = {
2164 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2165 : : .off = { .min = 0, .max = UINT16_MAX},
2166 : : .imm = { .min = 0, .max = UINT32_MAX},
2167 : : .eval = eval_jcc,
2168 : : },
2169 : : [(BPF_JMP | EBPF_JSLE | BPF_K)] = {
2170 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2171 : : .off = { .min = 0, .max = UINT16_MAX},
2172 : : .imm = { .min = 0, .max = UINT32_MAX},
2173 : : .eval = eval_jcc,
2174 : : },
2175 : : [(BPF_JMP | BPF_JSET | BPF_K)] = {
2176 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
2177 : : .off = { .min = 0, .max = UINT16_MAX},
2178 : : .imm = { .min = 0, .max = UINT32_MAX},
2179 : : .eval = eval_jcc,
2180 : : },
2181 : : /* jcc REG instructions */
2182 : : [(BPF_JMP | BPF_JEQ | BPF_X)] = {
2183 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2184 : : .off = { .min = 0, .max = UINT16_MAX},
2185 : : .imm = { .min = 0, .max = 0},
2186 : : .eval = eval_jcc,
2187 : : },
2188 : : [(BPF_JMP | EBPF_JNE | BPF_X)] = {
2189 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2190 : : .off = { .min = 0, .max = UINT16_MAX},
2191 : : .imm = { .min = 0, .max = 0},
2192 : : .eval = eval_jcc,
2193 : : },
2194 : : [(BPF_JMP | BPF_JGT | BPF_X)] = {
2195 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2196 : : .off = { .min = 0, .max = UINT16_MAX},
2197 : : .imm = { .min = 0, .max = 0},
2198 : : .eval = eval_jcc,
2199 : : },
2200 : : [(BPF_JMP | EBPF_JLT | BPF_X)] = {
2201 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2202 : : .off = { .min = 0, .max = UINT16_MAX},
2203 : : .imm = { .min = 0, .max = 0},
2204 : : .eval = eval_jcc,
2205 : : },
2206 : : [(BPF_JMP | BPF_JGE | BPF_X)] = {
2207 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2208 : : .off = { .min = 0, .max = UINT16_MAX},
2209 : : .imm = { .min = 0, .max = 0},
2210 : : .eval = eval_jcc,
2211 : : },
2212 : : [(BPF_JMP | EBPF_JLE | BPF_X)] = {
2213 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2214 : : .off = { .min = 0, .max = UINT16_MAX},
2215 : : .imm = { .min = 0, .max = 0},
2216 : : .eval = eval_jcc,
2217 : : },
2218 : : [(BPF_JMP | EBPF_JSGT | BPF_X)] = {
2219 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2220 : : .off = { .min = 0, .max = UINT16_MAX},
2221 : : .imm = { .min = 0, .max = 0},
2222 : : .eval = eval_jcc,
2223 : : },
2224 : : [(BPF_JMP | EBPF_JSLT | BPF_X)] = {
2225 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2226 : : .off = { .min = 0, .max = UINT16_MAX},
2227 : : .imm = { .min = 0, .max = 0},
2228 : : .eval = eval_jcc,
2229 : : },
2230 : : [(BPF_JMP | EBPF_JSGE | BPF_X)] = {
2231 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2232 : : .off = { .min = 0, .max = UINT16_MAX},
2233 : : .imm = { .min = 0, .max = 0},
2234 : : .eval = eval_jcc,
2235 : : },
2236 : : [(BPF_JMP | EBPF_JSLE | BPF_X)] = {
2237 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2238 : : .off = { .min = 0, .max = UINT16_MAX},
2239 : : .imm = { .min = 0, .max = 0},
2240 : : .eval = eval_jcc,
2241 : : },
2242 : : [(BPF_JMP | BPF_JSET | BPF_X)] = {
2243 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
2244 : : .off = { .min = 0, .max = UINT16_MAX},
2245 : : .imm = { .min = 0, .max = 0},
2246 : : .eval = eval_jcc,
2247 : : },
2248 : : /* call instruction */
2249 : : [(BPF_JMP | EBPF_CALL)] = {
2250 : : .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
2251 : : .off = { .min = 0, .max = 0},
2252 : : .imm = { .min = 0, .max = UINT32_MAX},
2253 : : .eval = eval_call,
2254 : : },
2255 : : /* ret instruction */
2256 : : [(BPF_JMP | EBPF_EXIT)] = {
2257 : : .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
2258 : : .off = { .min = 0, .max = 0},
2259 : : .imm = { .min = 0, .max = 0},
2260 : : .eval = eval_exit,
2261 : : },
2262 : : };
2263 : :
2264 : : /*
2265 : : * make sure that instruction syntax is valid,
2266 : : * and its fields don't violate particular instruction type restrictions.
2267 : : */
2268 : : static const char *
2269 : 8565 : check_syntax(const struct ebpf_insn *ins)
2270 : : {
2271 : :
2272 : : uint8_t op;
2273 : : uint16_t off;
2274 : : uint32_t imm;
2275 : :
2276 : 8565 : op = ins->code;
2277 : :
2278 [ + - ]: 8565 : if (ins_chk[op].mask.dreg == 0)
2279 : : return "invalid opcode";
2280 : :
2281 [ + - ]: 8565 : if ((ins_chk[op].mask.dreg & 1 << ins->dst_reg) == 0)
2282 : : return "invalid dst-reg field";
2283 : :
2284 [ + - ]: 8565 : if ((ins_chk[op].mask.sreg & 1 << ins->src_reg) == 0)
2285 : : return "invalid src-reg field";
2286 : :
2287 : 8565 : off = ins->off;
2288 [ + - + - ]: 8565 : if (ins_chk[op].off.min > off || ins_chk[op].off.max < off)
2289 : : return "invalid off field";
2290 : :
2291 : 8565 : imm = ins->imm;
2292 [ + - + + ]: 8565 : if (ins_chk[op].imm.min > imm || ins_chk[op].imm.max < imm)
2293 : : return "invalid imm field";
2294 : :
2295 [ + + ]: 8561 : if (ins_chk[op].check != NULL)
2296 : 8 : return ins_chk[op].check(ins);
2297 : :
2298 : : return NULL;
2299 : : }
2300 : :
2301 : : /*
2302 : : * helper function, return instruction index for the given node.
2303 : : */
2304 : : static uint32_t
2305 : : get_node_idx(const struct bpf_verifier *bvf, const struct inst_node *node)
2306 : : {
2307 : 33242 : return node - bvf->in;
2308 : : }
2309 : :
2310 : : /*
2311 : : * helper function, used to walk through constructed CFG.
2312 : : */
2313 : : static struct inst_node *
2314 : : get_next_node(struct bpf_verifier *bvf, struct inst_node *node)
2315 : : {
2316 : : uint32_t ce, ne, dst;
2317 : :
2318 : 40157 : ne = node->nb_edge;
2319 : 40157 : ce = node->cur_edge;
2320 [ + + + + ]: 40157 : if (ce == ne)
2321 : : return NULL;
2322 : :
2323 : 21070 : node->cur_edge++;
2324 : 21070 : dst = node->edge_dest[ce];
2325 : 21070 : return bvf->in + dst;
2326 : : }
2327 : :
2328 : : static void
2329 : : set_node_colour(struct bpf_verifier *bvf, struct inst_node *node,
2330 : : uint32_t new)
2331 : : {
2332 : : uint32_t prev;
2333 : :
2334 : : prev = node->colour;
2335 : 17096 : node->colour = new;
2336 : :
2337 : 17096 : bvf->node_colour[prev]--;
2338 : 17096 : bvf->node_colour[new]++;
2339 : 8548 : }
2340 : :
2341 : : /*
2342 : : * helper function, add new edge between two nodes.
2343 : : */
2344 : : static int
2345 : 10354 : add_edge(struct bpf_verifier *bvf, struct inst_node *node, uint32_t nidx)
2346 : : {
2347 : : uint32_t ne;
2348 : :
2349 [ + + ]: 10354 : if (nidx >= bvf->prm->raw.nb_ins) {
2350 : 1 : RTE_BPF_LOG_FUNC_LINE(ERR,
2351 : : "program boundary violation at pc: %u, next pc: %u",
2352 : : get_node_idx(bvf, node), nidx);
2353 : 1 : return -EINVAL;
2354 : : }
2355 : :
2356 : 10353 : ne = node->nb_edge;
2357 [ - + ]: 10353 : if (ne >= RTE_DIM(node->edge_dest)) {
2358 : 0 : RTE_BPF_LOG_FUNC_LINE(ERR, "internal error at pc: %u",
2359 : : get_node_idx(bvf, node));
2360 : 0 : return -EINVAL;
2361 : : }
2362 : :
2363 : 10353 : node->edge_dest[ne] = nidx;
2364 : 10353 : node->nb_edge = ne + 1;
2365 : 10353 : return 0;
2366 : : }
2367 : :
2368 : : /*
2369 : : * helper function, determine type of edge between two nodes.
2370 : : */
2371 : : static void
2372 : : set_edge_type(struct bpf_verifier *bvf, struct inst_node *node,
2373 : : const struct inst_node *next)
2374 : : {
2375 : : uint32_t ce, clr, type;
2376 : :
2377 : 10341 : ce = node->cur_edge - 1;
2378 : 10341 : clr = next->colour;
2379 : :
2380 : : type = UNKNOWN_EDGE;
2381 : :
2382 [ + + ]: 10341 : if (clr == WHITE)
2383 : : type = TREE_EDGE;
2384 [ + - ]: 2627 : else if (clr == GREY)
2385 : : type = BACK_EDGE;
2386 [ + - ]: 2627 : else if (clr == BLACK)
2387 : : /*
2388 : : * in fact it could be either direct or cross edge,
2389 : : * but for now, we don't need to distinguish between them.
2390 : : */
2391 : : type = CROSS_EDGE;
2392 : :
2393 : 10341 : node->edge_type[ce] = type;
2394 : 10341 : bvf->edge_type[type]++;
2395 : : }
2396 : :
2397 : : /*
2398 : : * Depth-First Search (DFS) through previously constructed
2399 : : * Control Flow Graph (CFG).
2400 : : * Information collected at this path would be used later
2401 : : * to determine is there any loops, and/or statically unreachable instructions.
2402 : : * PREREQUISITE: there is at least one node.
2403 : : */
2404 : : static void
2405 : 834 : dfs(struct bpf_verifier *bvf)
2406 : : {
2407 : : struct inst_node *next, *node;
2408 : :
2409 : : RTE_ASSERT(bvf->nb_nodes != 0);
2410 : : /*
2411 : : * Since there is at least one node, node with index 0 always exists;
2412 : : * it is our program entry point.
2413 : : */
2414 : 834 : node = &bvf->in[0];
2415 : : do {
2416 : :
2417 [ + + ]: 16262 : if (node->colour == WHITE)
2418 : : set_node_colour(bvf, node, GREY);
2419 : :
2420 [ + - ]: 16262 : if (node->colour == GREY) {
2421 : :
2422 : : /* find next unprocessed child node */
2423 : : do {
2424 : : next = get_next_node(bvf, node);
2425 [ + - ]: 10341 : if (next == NULL)
2426 : : break;
2427 : : set_edge_type(bvf, node, next);
2428 [ + + ]: 10341 : } while (next->colour != WHITE);
2429 : :
2430 [ + + ]: 16262 : if (next != NULL) {
2431 : : /* proceed with next child */
2432 : 7714 : next->prev_node = node;
2433 : : node = next;
2434 : : } else {
2435 : : /*
2436 : : * finished with current node and all it's kids,
2437 : : * proceed with parent
2438 : : */
2439 : : set_node_colour(bvf, node, BLACK);
2440 : 8548 : node->cur_edge = 0;
2441 : 8548 : node = node->prev_node;
2442 : : }
2443 : : } else
2444 : : node = NULL;
2445 [ + + ]: 16262 : } while (node != NULL);
2446 : 834 : }
2447 : :
2448 : : /*
2449 : : * report statically unreachable instructions.
2450 : : */
2451 : : static void
2452 : 0 : log_unreachable(const struct bpf_verifier *bvf)
2453 : : {
2454 : : uint32_t i;
2455 : : struct inst_node *node;
2456 : : const struct ebpf_insn *ins;
2457 : :
2458 [ # # ]: 0 : for (i = 0; i != bvf->prm->raw.nb_ins; i++) {
2459 : :
2460 : 0 : node = bvf->in + i;
2461 : 0 : ins = bvf->prm->raw.ins + i;
2462 : :
2463 [ # # ]: 0 : if (node->colour == WHITE &&
2464 [ # # ]: 0 : ins->code != (BPF_LD | BPF_IMM | EBPF_DW))
2465 : 0 : RTE_BPF_LOG_LINE(ERR, "unreachable code at pc: %u;", i);
2466 : : }
2467 : 0 : }
2468 : :
2469 : : /*
2470 : : * report loops detected.
2471 : : */
2472 : : static void
2473 : 0 : log_loop(const struct bpf_verifier *bvf)
2474 : : {
2475 : : uint32_t i, j;
2476 : : struct inst_node *node;
2477 : :
2478 [ # # ]: 0 : for (i = 0; i != bvf->prm->raw.nb_ins; i++) {
2479 : :
2480 : 0 : node = bvf->in + i;
2481 [ # # ]: 0 : if (node->colour != BLACK)
2482 : 0 : continue;
2483 : :
2484 [ # # ]: 0 : for (j = 0; j != node->nb_edge; j++) {
2485 [ # # ]: 0 : if (node->edge_type[j] == BACK_EDGE)
2486 : 0 : RTE_BPF_LOG_LINE(ERR,
2487 : : "loop at pc:%u --> pc:%u;",
2488 : : i, node->edge_dest[j]);
2489 : : }
2490 : : }
2491 : 0 : }
2492 : :
2493 : : /*
2494 : : * First pass goes though all instructions in the set, checks that each
2495 : : * instruction is a valid one (correct syntax, valid field values, etc.)
2496 : : * and constructs control flow graph (CFG).
2497 : : * Then depth-first search is performed over the constructed graph.
2498 : : * Programs with unreachable instructions and/or loops will be rejected.
2499 : : */
2500 : : static int
2501 : 839 : validate(struct bpf_verifier *bvf)
2502 : : {
2503 : : int32_t rc;
2504 : : uint32_t i;
2505 : : struct inst_node *node;
2506 : : const struct ebpf_insn *ins;
2507 : : const char *err;
2508 : :
2509 : : rc = 0;
2510 [ + + ]: 9404 : for (i = 0; i < bvf->prm->raw.nb_ins; i++) {
2511 : :
2512 : 8565 : ins = bvf->prm->raw.ins + i;
2513 : 8565 : node = bvf->in + i;
2514 : :
2515 : 8565 : err = check_syntax(ins);
2516 [ + + ]: 8565 : if (err != 0) {
2517 : 4 : RTE_BPF_LOG_FUNC_LINE(ERR, "%s at pc: %u", err, i);
2518 : 4 : rc |= -EINVAL;
2519 : : }
2520 : :
2521 : : /*
2522 : : * construct CFG, jcc nodes have to outgoing edges,
2523 : : * 'exit' nodes - none, all other nodes have exactly one
2524 : : * outgoing edge.
2525 : : */
2526 [ + + + + : 8565 : switch (ins->code) {
+ + ]
2527 : : case (BPF_JMP | EBPF_EXIT):
2528 : : break;
2529 : 3010 : case (BPF_JMP | BPF_JEQ | BPF_K):
2530 : : case (BPF_JMP | EBPF_JNE | BPF_K):
2531 : : case (BPF_JMP | BPF_JGT | BPF_K):
2532 : : case (BPF_JMP | EBPF_JLT | BPF_K):
2533 : : case (BPF_JMP | BPF_JGE | BPF_K):
2534 : : case (BPF_JMP | EBPF_JLE | BPF_K):
2535 : : case (BPF_JMP | EBPF_JSGT | BPF_K):
2536 : : case (BPF_JMP | EBPF_JSLT | BPF_K):
2537 : : case (BPF_JMP | EBPF_JSGE | BPF_K):
2538 : : case (BPF_JMP | EBPF_JSLE | BPF_K):
2539 : : case (BPF_JMP | BPF_JSET | BPF_K):
2540 : : case (BPF_JMP | BPF_JEQ | BPF_X):
2541 : : case (BPF_JMP | EBPF_JNE | BPF_X):
2542 : : case (BPF_JMP | BPF_JGT | BPF_X):
2543 : : case (BPF_JMP | EBPF_JLT | BPF_X):
2544 : : case (BPF_JMP | BPF_JGE | BPF_X):
2545 : : case (BPF_JMP | EBPF_JLE | BPF_X):
2546 : : case (BPF_JMP | EBPF_JSGT | BPF_X):
2547 : : case (BPF_JMP | EBPF_JSLT | BPF_X):
2548 : : case (BPF_JMP | EBPF_JSGE | BPF_X):
2549 : : case (BPF_JMP | EBPF_JSLE | BPF_X):
2550 : : case (BPF_JMP | BPF_JSET | BPF_X):
2551 : 3010 : rc |= add_edge(bvf, node, i + ins->off + 1);
2552 : 3010 : rc |= add_edge(bvf, node, i + 1);
2553 : 3010 : bvf->nb_jcc_nodes++;
2554 : 3010 : break;
2555 : 48 : case (BPF_JMP | BPF_JA):
2556 : 48 : rc |= add_edge(bvf, node, i + ins->off + 1);
2557 : 48 : break;
2558 : : /* load 64 bit immediate value */
2559 : 369 : case (BPF_LD | BPF_IMM | EBPF_DW):
2560 : 369 : rc |= add_edge(bvf, node, i + 2);
2561 : 369 : i++;
2562 : 369 : break;
2563 : 488 : case (BPF_LD | BPF_ABS | BPF_B):
2564 : : case (BPF_LD | BPF_ABS | BPF_H):
2565 : : case (BPF_LD | BPF_ABS | BPF_W):
2566 : : case (BPF_LD | BPF_IND | BPF_B):
2567 : : case (BPF_LD | BPF_IND | BPF_H):
2568 : : case (BPF_LD | BPF_IND | BPF_W):
2569 : 488 : bvf->nb_ldmb_nodes++;
2570 : : /* fallthrough */
2571 : 3917 : default:
2572 : 3917 : rc |= add_edge(bvf, node, i + 1);
2573 : 3917 : break;
2574 : : }
2575 : :
2576 : 8565 : bvf->nb_nodes++;
2577 : 8565 : bvf->node_colour[WHITE]++;
2578 : : }
2579 : :
2580 [ + + ]: 839 : if (rc != 0)
2581 : : return rc;
2582 : :
2583 [ - + ]: 834 : if (bvf->nb_nodes == 0) {
2584 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) the program is empty",
2585 : : __func__, bvf);
2586 : 0 : return -EINVAL;
2587 : : }
2588 : :
2589 : 834 : dfs(bvf);
2590 : :
2591 : 834 : RTE_LOG(DEBUG, BPF, "%s(%p) stats:\n"
2592 : : "nb_nodes=%u;\n"
2593 : : "nb_jcc_nodes=%u;\n"
2594 : : "node_color={[WHITE]=%u, [GREY]=%u,, [BLACK]=%u};\n"
2595 : : "edge_type={[UNKNOWN]=%u, [TREE]=%u, [BACK]=%u, [CROSS]=%u};\n",
2596 : : __func__, bvf,
2597 : : bvf->nb_nodes,
2598 : : bvf->nb_jcc_nodes,
2599 : : bvf->node_colour[WHITE], bvf->node_colour[GREY],
2600 : : bvf->node_colour[BLACK],
2601 : : bvf->edge_type[UNKNOWN_EDGE], bvf->edge_type[TREE_EDGE],
2602 : : bvf->edge_type[BACK_EDGE], bvf->edge_type[CROSS_EDGE]);
2603 : :
2604 [ - + ]: 834 : if (bvf->node_colour[BLACK] != bvf->nb_nodes) {
2605 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) unreachable instructions;",
2606 : : __func__, bvf);
2607 : 0 : log_unreachable(bvf);
2608 : 0 : return -EINVAL;
2609 : : }
2610 : :
2611 [ + - + - ]: 834 : if (bvf->node_colour[GREY] != 0 || bvf->node_colour[WHITE] != 0 ||
2612 [ - + ]: 834 : bvf->edge_type[UNKNOWN_EDGE] != 0) {
2613 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) DFS internal error;",
2614 : : __func__, bvf);
2615 : 0 : return -EINVAL;
2616 : : }
2617 : :
2618 [ - + ]: 834 : if (bvf->edge_type[BACK_EDGE] != 0) {
2619 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) loops detected;",
2620 : : __func__, bvf);
2621 : 0 : log_loop(bvf);
2622 : 0 : return -EINVAL;
2623 : : }
2624 : :
2625 : : return 0;
2626 : : }
2627 : :
2628 : : /*
2629 : : * helper functions get/free eval states.
2630 : : */
2631 : : static struct bpf_eval_state *
2632 : : pull_eval_state(struct evst_pool *pool)
2633 : : {
2634 : : uint32_t n;
2635 : :
2636 : 9129 : n = pool->cur;
2637 [ + + ]: 5896 : if (n == pool->num)
2638 : : return NULL;
2639 : :
2640 : 9657 : pool->cur = n + 1;
2641 : 5590 : return pool->ent + n;
2642 : : }
2643 : :
2644 : : static void
2645 : : push_eval_state(struct evst_pool *pool)
2646 : : {
2647 : : RTE_ASSERT(pool->cur != 0);
2648 : 3233 : pool->cur--;
2649 : : }
2650 : :
2651 : : static void
2652 : 834 : evst_pool_fini(struct bpf_verifier *bvf)
2653 : : {
2654 : 834 : bvf->evst = NULL;
2655 : 834 : free(bvf->evst_sr_pool.ent);
2656 : 834 : memset(&bvf->evst_sr_pool, 0, sizeof(bvf->evst_sr_pool));
2657 : 834 : memset(&bvf->evst_tp_pool, 0, sizeof(bvf->evst_tp_pool));
2658 : 834 : }
2659 : :
2660 : : static int
2661 : 834 : evst_pool_init(struct bpf_verifier *bvf)
2662 : : {
2663 : : uint32_t k, n;
2664 : :
2665 [ + - ]: 834 : if (bvf->nb_jcc_nodes > UINT32_MAX / 4)
2666 : : /* Calculations that follow may overflow. */
2667 : : return -E2BIG;
2668 : :
2669 : : /*
2670 : : * We need nb_jcc_nodes + 1 for save_cur/restore_cur
2671 : : * remaining ones will be used for state tracking/pruning.
2672 : : */
2673 : 834 : k = bvf->nb_jcc_nodes + 1;
2674 : 834 : n = k * 3;
2675 : :
2676 : 834 : bvf->evst_sr_pool.ent = calloc(n, sizeof(bvf->evst_sr_pool.ent[0]));
2677 [ + - ]: 834 : if (bvf->evst_sr_pool.ent == NULL)
2678 : : return -ENOMEM;
2679 : :
2680 : 834 : bvf->evst_sr_pool.num = k;
2681 : : bvf->evst_sr_pool.cur = 0;
2682 : :
2683 : 834 : bvf->evst_tp_pool.ent = bvf->evst_sr_pool.ent + k;
2684 : 834 : bvf->evst_tp_pool.num = n - k;
2685 : 834 : bvf->evst_tp_pool.cur = 0;
2686 : :
2687 : 834 : bvf->evst = pull_eval_state(&bvf->evst_sr_pool);
2688 : 834 : return 0;
2689 : : }
2690 : :
2691 : : /*
2692 : : * try to allocate and initialise new eval state for given node.
2693 : : * later if no errors will be encountered, this state will be accepted as
2694 : : * one of the possible 'safe' states for that node.
2695 : : */
2696 : : static void
2697 : 5896 : save_start_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2698 : : {
2699 : : RTE_ASSERT(node->evst.start == NULL);
2700 : :
2701 : : /* limit number of states for one node with some reasonable value */
2702 [ + - ]: 5896 : if (node->evst.nb_safe >= NODE_EVST_MAX)
2703 : : return;
2704 : :
2705 : : /* try to get new eval_state */
2706 : 5896 : node->evst.start = pull_eval_state(&bvf->evst_tp_pool);
2707 : :
2708 : : /* make a copy of current state */
2709 [ + + ]: 5896 : if (node->evst.start != NULL) {
2710 : 5590 : memcpy(node->evst.start, bvf->evst, sizeof(*node->evst.start));
2711 : 5590 : SLIST_NEXT(node->evst.start, next) = NULL;
2712 : : }
2713 : : }
2714 : :
2715 : : /*
2716 : : * add @start state to the list of @safe states.
2717 : : */
2718 : : static void
2719 : 10539 : save_safe_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2720 : : {
2721 [ + + ]: 10539 : if (node->evst.start == NULL)
2722 : : return;
2723 : :
2724 : 5588 : SLIST_INSERT_HEAD(&node->evst.safe, node->evst.start, next);
2725 : 5588 : node->evst.nb_safe++;
2726 : :
2727 : 5588 : RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u,state=%p): nb_safe=%u;",
2728 : : __func__, bvf, get_node_idx(bvf, node), node->evst.start,
2729 : : node->evst.nb_safe);
2730 : :
2731 : 5588 : node->evst.start = NULL;
2732 : : }
2733 : :
2734 : : /*
2735 : : * Save current eval state.
2736 : : */
2737 : : static int
2738 [ + - ]: 3233 : save_cur_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2739 : : {
2740 : : struct bpf_eval_state *st;
2741 : :
2742 : : /* get new eval_state for this node */
2743 : : st = pull_eval_state(&bvf->evst_sr_pool);
2744 [ - + ]: 3233 : if (st == NULL) {
2745 : 0 : RTE_BPF_LOG_FUNC_LINE(ERR,
2746 : : "internal error (out of space) at pc: %u",
2747 : : get_node_idx(bvf, node));
2748 : 0 : return -ENOMEM;
2749 : : }
2750 : :
2751 : : /* make a copy of current state */
2752 : 3233 : memcpy(st, bvf->evst, sizeof(*st));
2753 : :
2754 : : /* swap current state with new one */
2755 : : RTE_ASSERT(node->evst.cur == NULL);
2756 : 3233 : node->evst.cur = bvf->evst;
2757 : 3233 : bvf->evst = st;
2758 : :
2759 : 3233 : RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;",
2760 : : __func__, bvf, get_node_idx(bvf, node), node->evst.cur,
2761 : : bvf->evst);
2762 : :
2763 : 3233 : return 0;
2764 : : }
2765 : :
2766 : : /*
2767 : : * Restore previous eval state and mark current eval state as free.
2768 : : */
2769 : : static void
2770 : 3233 : restore_cur_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2771 : : {
2772 : 3233 : RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;",
2773 : : __func__, bvf, get_node_idx(bvf, node), bvf->evst,
2774 : : node->evst.cur);
2775 : :
2776 : 3233 : bvf->evst = node->evst.cur;
2777 : 3233 : node->evst.cur = NULL;
2778 : : push_eval_state(&bvf->evst_sr_pool);
2779 : 3233 : }
2780 : :
2781 : : static void
2782 : 10766 : log_dbg_eval_state(const struct bpf_verifier *bvf, const struct ebpf_insn *ins,
2783 : : uint32_t pc)
2784 : : {
2785 : : const struct bpf_eval_state *st;
2786 : : const struct bpf_reg_val *rv;
2787 : :
2788 : 10766 : RTE_BPF_LOG_LINE(DEBUG, "%s(pc=%u):", __func__, pc);
2789 : :
2790 : 10766 : st = bvf->evst;
2791 : 10766 : rv = st->rv + ins->dst_reg;
2792 : :
2793 : 10766 : RTE_LOG(DEBUG, BPF,
2794 : : "r%u={\n"
2795 : : "\tv={type=%u, size=%zu, buf_size=%zu},\n"
2796 : : "\tmask=0x%" PRIx64 ",\n"
2797 : : "\tu={min=0x%" PRIx64 ", max=0x%" PRIx64 "},\n"
2798 : : "\ts={min=%" PRId64 ", max=%" PRId64 "},\n"
2799 : : "};\n",
2800 : : ins->dst_reg,
2801 : : rv->v.type, rv->v.size, rv->v.buf_size,
2802 : : rv->mask,
2803 : : rv->u.min, rv->u.max,
2804 : : rv->s.min, rv->s.max);
2805 : 10766 : }
2806 : :
2807 : : /*
2808 : : * compare two evaluation states.
2809 : : * returns zero if @lv is more conservative (safer) then @rv.
2810 : : * returns non-zero value otherwise.
2811 : : */
2812 : : static int
2813 : 7186 : cmp_reg_val_within(const struct bpf_reg_val *lv, const struct bpf_reg_val *rv)
2814 : : {
2815 : : /* expect @v and @mask to be identical */
2816 [ + + + + ]: 7186 : if (memcmp(&lv->v, &rv->v, sizeof(lv->v)) != 0 || lv->mask != rv->mask)
2817 : : return -1;
2818 : :
2819 : : /* exact match only for mbuf and stack pointers */
2820 [ + - ]: 6860 : if (lv->v.type == RTE_BPF_ARG_PTR_MBUF ||
2821 : : lv->v.type == BPF_ARG_PTR_STACK)
2822 : : return -1;
2823 : :
2824 [ + + + + ]: 6860 : if (lv->u.min <= rv->u.min && lv->u.max >= rv->u.max &&
2825 [ + + + + ]: 2086 : lv->s.min <= rv->s.min && lv->s.max >= rv->s.max)
2826 : 28 : return 0;
2827 : :
2828 : : return -1;
2829 : : }
2830 : :
2831 : : /*
2832 : : * compare two evaluation states.
2833 : : * returns zero if they are identical.
2834 : : * returns positive value if @lv is more conservative (safer) then @rv.
2835 : : * returns negative value otherwise.
2836 : : */
2837 : : static int
2838 : 7530 : cmp_eval_state(const struct bpf_eval_state *lv, const struct bpf_eval_state *rv)
2839 : : {
2840 : : int32_t rc;
2841 : : uint32_t i, k;
2842 : :
2843 : : /* for stack expect identical values */
2844 : 7530 : rc = memcmp(lv->sv, rv->sv, sizeof(lv->sv));
2845 [ + - ]: 7530 : if (rc != 0)
2846 : : return -(2 * EBPF_REG_NUM);
2847 : :
2848 : : k = 0;
2849 : : /* check register values */
2850 [ + + ]: 25704 : for (i = 0; i != RTE_DIM(lv->rv); i++) {
2851 : 25332 : rc = memcmp(&lv->rv[i], &rv->rv[i], sizeof(lv->rv[i]));
2852 [ + + + + ]: 25332 : if (rc != 0 && cmp_reg_val_within(&lv->rv[i], &rv->rv[i]) != 0)
2853 : 7158 : return -(i + 1);
2854 : 18174 : k += (rc != 0);
2855 : : }
2856 : :
2857 : 372 : return k;
2858 : : }
2859 : :
2860 : : /*
2861 : : * check did we already evaluated that path and can it be pruned that time.
2862 : : */
2863 : : static int
2864 : 6268 : prune_eval_state(struct bpf_verifier *bvf, const struct inst_node *node,
2865 : : struct inst_node *next)
2866 : : {
2867 : : int32_t rc;
2868 : : struct bpf_eval_state *safe;
2869 : :
2870 : : rc = INT32_MIN;
2871 [ + + ]: 13426 : SLIST_FOREACH(safe, &next->evst.safe, next) {
2872 : 7530 : rc = cmp_eval_state(safe, bvf->evst);
2873 [ + + ]: 7530 : if (rc >= 0)
2874 : : break;
2875 : : }
2876 : :
2877 [ + + ]: 6268 : rc = (rc >= 0) ? 0 : -1;
2878 : :
2879 : : /*
2880 : : * current state doesn't match any safe states,
2881 : : * so no prunning is possible right now,
2882 : : * track current state for future references.
2883 : : */
2884 : : if (rc != 0)
2885 : 5896 : save_start_eval_state(bvf, next);
2886 : :
2887 : 6268 : RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u,next=%u) returns %d, "
2888 : : "next->evst.start=%p, next->evst.nb_safe=%u",
2889 : : __func__, bvf, get_node_idx(bvf, node),
2890 : : get_node_idx(bvf, next), rc,
2891 : : next->evst.start, next->evst.nb_safe);
2892 : 6268 : return rc;
2893 : : }
2894 : :
2895 : : /* Do second pass through CFG and try to evaluate instructions
2896 : : * via each possible path. The verifier will try all paths, tracking types of
2897 : : * registers used as input to instructions, and updating resulting type via
2898 : : * register state values. Plus for each register and possible stack value it
2899 : : * tries to estimate possible max/min value.
2900 : : * For conditional jumps, a stack is used to save evaluation state, so one
2901 : : * path is explored while the state for the other path is pushed onto the stack.
2902 : : * Then later, we backtrack to the first pushed instruction and repeat the cycle
2903 : : * until the stack is empty and we're done.
2904 : : * For program with many conditional branches walking through all possible path
2905 : : * could be very excessive. So to minimize number of evaluations we use
2906 : : * heuristic similar to what Linux kernel does - state pruning:
2907 : : * If from given instruction for given program state we explore all possible
2908 : : * paths and for each of them reach _exit() without any complaints and a valid
2909 : : * R0 value, then for that instruction, that program state can be marked as
2910 : : * 'safe'. When we later arrive at the same instruction with a state
2911 : : * equivalent to an earlier instruction's 'safe' state, we can prune the search.
2912 : : * For now, only states for JCC targets are saved/examined.
2913 : : */
2914 : : static int
2915 : 834 : evaluate(struct bpf_verifier *bvf)
2916 : : {
2917 : : uint32_t idx, op;
2918 : : const char *err;
2919 : : const struct ebpf_insn *ins;
2920 : : struct inst_node *next, *node;
2921 : : int prev_nb_edge; /* branching number of the previous instruction */
2922 : : int rc, debug_rc;
2923 : 834 : struct rte_bpf_validate_debug *const debug = bvf->prm->debug;
2924 : :
2925 : : struct {
2926 : : uint32_t nb_eval;
2927 : : uint32_t nb_prune;
2928 : : uint32_t nb_save;
2929 : : uint32_t nb_restore;
2930 : : } stats;
2931 : :
2932 : : /* initial state of frame pointer */
2933 : : static const struct bpf_reg_val rvfp = {
2934 : : .v = {
2935 : : .type = BPF_ARG_PTR_STACK,
2936 : : .size = MAX_BPF_STACK_SIZE,
2937 : : },
2938 : : .mask = UINT64_MAX,
2939 : : .u = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
2940 : : .s = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
2941 : : };
2942 : :
2943 [ + + ]: 1669 : for (uint32_t pai = 0; pai != bvf->prm->nb_prog_arg; ++pai) {
2944 : 835 : struct bpf_reg_val *reg = &bvf->evst->rv[EBPF_REG_1 + pai];
2945 : :
2946 : 835 : reg->v = bvf->prm->prog_arg[pai];
2947 : 835 : reg->mask = UINT64_MAX;
2948 [ + + ]: 835 : if (reg->v.type == RTE_BPF_ARG_RAW)
2949 : : eval_max_bound(reg, UINT64_MAX);
2950 : : }
2951 : :
2952 : 834 : bvf->evst->rv[EBPF_REG_10] = rvfp;
2953 : :
2954 : 834 : ins = bvf->prm->raw.ins;
2955 : 834 : node = bvf->in;
2956 : : next = node;
2957 : : prev_nb_edge = 1;
2958 : :
2959 : : memset(&stats, 0, sizeof(stats));
2960 : :
2961 : 834 : rc = __rte_bpf_validate_debug_evaluate_start(debug, bvf, bvf->prm);
2962 [ + - ]: 834 : if (rc < 0)
2963 : : return rc;
2964 : :
2965 [ + + ]: 22102 : while (node != NULL) {
2966 : : /*
2967 : : * current node evaluation, make sure we evaluate
2968 : : * each node only once.
2969 : : */
2970 [ + + ]: 21495 : if (next != NULL) {
2971 : : /* just started or stepped down the tree, node == next */
2972 : :
2973 : 10993 : bvf->evin = node;
2974 : : idx = get_node_idx(bvf, node);
2975 : 10993 : op = ins[idx].code;
2976 : :
2977 : : /* for jcc node make a copy of evaluation state */
2978 [ + + ]: 10993 : if (node->nb_edge > 1) {
2979 : 3233 : rc = save_cur_eval_state(bvf, node);
2980 [ + - ]: 3233 : if (rc < 0)
2981 : : break;
2982 : 3233 : stats.nb_save++;
2983 : : }
2984 : :
2985 [ - + ]: 10993 : if (ins_chk[op].eval == NULL) {
2986 : 0 : RTE_BPF_LOG_FUNC_LINE(ERR,
2987 : : "Unrecognized instruction at pc: %u", idx);
2988 : : rc = -EINVAL;
2989 : 0 : break;
2990 : : }
2991 : :
2992 [ + + ]: 16090 : rc = __rte_bpf_validate_debug_evaluate_step(debug, idx,
2993 : : prev_nb_edge > 1 ?
2994 : : RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_ENTER :
2995 : : RTE_BPF_VALIDATE_DEBUG_EVENT_STEP);
2996 [ + - ]: 10993 : if (rc < 0)
2997 : : break;
2998 : :
2999 : 10993 : err = ins_chk[op].eval(bvf, ins + idx);
3000 : 10993 : stats.nb_eval++;
3001 [ + + ]: 10993 : if (err != NULL) {
3002 : 227 : RTE_BPF_LOG_FUNC_LINE(ERR,
3003 : : "%s at pc: %u", err, idx);
3004 : : rc = -EINVAL;
3005 : 227 : break;
3006 : : }
3007 : :
3008 : 10766 : log_dbg_eval_state(bvf, ins + idx, idx);
3009 : 10766 : bvf->evin = NULL;
3010 : : }
3011 : :
3012 : : /* proceed through CFG */
3013 : : next = get_next_node(bvf, node);
3014 : :
3015 [ + - ]: 10729 : if (next != NULL) {
3016 : : /*
3017 : : * proceed with next child
3018 : : * next points to an unwalked subtree of node
3019 : : */
3020 [ + + ]: 10729 : if (node->cur_edge == node->nb_edge &&
3021 [ + + ]: 7496 : node->evst.cur != NULL) {
3022 : 3233 : restore_cur_eval_state(bvf, node);
3023 : 3233 : stats.nb_restore++;
3024 : : }
3025 : :
3026 [ + + ]: 10729 : if (bvf->evst->unreachable) {
3027 : 198 : rc = __rte_bpf_validate_debug_evaluate_step(
3028 : : debug, get_node_idx(bvf, next),
3029 : : RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_UNREACHABLE);
3030 [ + - ]: 198 : if (rc < 0)
3031 : : break;
3032 : :
3033 : : next = NULL;
3034 : : /*
3035 : : * for jcc targets: check did we already evaluated
3036 : : * that path and can it's evaluation be skipped that
3037 : : * time.
3038 : : */
3039 [ + + + + ]: 16799 : } else if (node->nb_edge > 1 &&
3040 : 6268 : prune_eval_state(bvf, node, next) == 0) {
3041 : 372 : rc = __rte_bpf_validate_debug_evaluate_step(
3042 : : debug, get_node_idx(bvf, next),
3043 : : RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_PRUNE);
3044 [ + - ]: 372 : if (rc < 0)
3045 : : break;
3046 : :
3047 : : next = NULL;
3048 : 372 : stats.nb_prune++;
3049 : : } else {
3050 : 10159 : next->prev_node = node;
3051 : 10159 : prev_nb_edge = node->nb_edge;
3052 : : node = next;
3053 : : }
3054 : : } else {
3055 : : /*
3056 : : * finished with current node and all it's kids,
3057 : : * mark it's @start state as safe for future references,
3058 : : * and proceed with parent.
3059 : : */
3060 : :
3061 [ + + ]: 10539 : if (prev_nb_edge != 0) {
3062 : 3356 : rc = __rte_bpf_validate_debug_evaluate_step(
3063 : : debug, get_node_idx(bvf, node) + 1,
3064 : : RTE_BPF_VALIDATE_DEBUG_EVENT_BRANCH_RETURN);
3065 [ + - ]: 3356 : if (rc < 0)
3066 : : break;
3067 : : }
3068 : :
3069 : 10539 : node->cur_edge = 0;
3070 : 10539 : save_safe_eval_state(bvf, node);
3071 : : prev_nb_edge = 0;
3072 : 10539 : node = node->prev_node;
3073 : :
3074 : : /* first node will not have prev, signalling finish */
3075 : : }
3076 : :
3077 : : /*
3078 : : * next != NULL: stepped down the tree, node == next;
3079 : : * next == NULL: stepped up after processing or pruning subtree;
3080 : : */
3081 : : }
3082 : :
3083 : 834 : RTE_LOG(DEBUG, BPF, "%s(%p) returns %d, stats:\n"
3084 : : "node evaluations=%u;\n"
3085 : : "state pruned=%u;\n"
3086 : : "state saves=%u;\n"
3087 : : "state restores=%u;\n",
3088 : : __func__, bvf, rc,
3089 : : stats.nb_eval, stats.nb_prune, stats.nb_save, stats.nb_restore);
3090 : :
3091 : 834 : debug_rc = __rte_bpf_validate_debug_evaluate_finish(debug, rc);
3092 [ + - ]: 834 : rc = debug_rc < 0 ? debug_rc : rc;
3093 : :
3094 : : /* Caller does not expect positive values. */
3095 : 834 : return RTE_MIN(0, rc);
3096 : : }
3097 : :
3098 : : static bool
3099 : 840 : prog_arg_is_valid(const struct rte_bpf_arg *prog_arg)
3100 : : {
3101 : : /* check input argument type, don't allow mbuf ptr on 32-bit */
3102 [ + + ]: 840 : if (prog_arg->type != RTE_BPF_ARG_RAW &&
3103 [ - + ]: 59 : prog_arg->type != RTE_BPF_ARG_PTR &&
3104 : : (sizeof(uint64_t) != sizeof(uintptr_t) ||
3105 : : prog_arg->type != RTE_BPF_ARG_PTR_MBUF)) {
3106 : 0 : RTE_BPF_LOG_FUNC_LINE(ERR, "unsupported argument type");
3107 : 0 : return false;
3108 : : }
3109 : :
3110 : : return true;
3111 : : }
3112 : :
3113 : : int
3114 : 839 : __rte_bpf_validate(const struct rte_bpf_prm_ex *prm, uint32_t *stack_sz)
3115 : : {
3116 : : int32_t rc;
3117 : : struct bpf_verifier bvf;
3118 : :
3119 [ - + ]: 839 : if (prm->nb_prog_arg > EBPF_FUNC_MAX_ARGS) {
3120 : 0 : RTE_BPF_LOG_FUNC_LINE(ERR,
3121 : : "support up to %u arguments, found %u",
3122 : : EBPF_FUNC_MAX_ARGS, prm->nb_prog_arg);
3123 : 0 : return -ENOTSUP;
3124 : : }
3125 : :
3126 [ + + ]: 1679 : for (uint32_t pai = 0; pai != prm->nb_prog_arg; ++pai)
3127 [ - + ]: 840 : if (!prog_arg_is_valid(&prm->prog_arg[pai])) {
3128 : 0 : RTE_BPF_LOG_FUNC_LINE(ERR,
3129 : : "unsupported argument %d (r%d) type",
3130 : : pai, EBPF_REG_1 + pai);
3131 : 0 : return -ENOTSUP;
3132 : : }
3133 : :
3134 : : memset(&bvf, 0, sizeof(bvf));
3135 : 839 : bvf.prm = prm;
3136 : 839 : bvf.in = calloc(prm->raw.nb_ins, sizeof(bvf.in[0]));
3137 [ + - ]: 839 : if (bvf.in == NULL)
3138 : : return -ENOMEM;
3139 : :
3140 : 839 : rc = validate(&bvf);
3141 : :
3142 [ + + ]: 839 : if (rc == 0) {
3143 : 834 : rc = evst_pool_init(&bvf);
3144 [ + - ]: 834 : if (rc == 0)
3145 : 834 : rc = evaluate(&bvf);
3146 : 834 : evst_pool_fini(&bvf);
3147 : : }
3148 : :
3149 : 839 : free(bvf.in);
3150 : :
3151 : : /* copy collected info */
3152 [ + + ]: 839 : if (rc == 0) {
3153 : 607 : *stack_sz = bvf.stack_sz;
3154 : :
3155 : : /* for LD_ABS/LD_IND, we'll need extra space on the stack */
3156 [ + + ]: 607 : if (bvf.nb_ldmb_nodes != 0)
3157 : 57 : *stack_sz = RTE_ALIGN_CEIL(*stack_sz +
3158 : : sizeof(uint64_t), sizeof(uint64_t));
3159 : : }
3160 : :
3161 : : return rc;
3162 : : }
|
