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_common.h>
13 : :
14 : : #include "bpf_impl.h"
15 : :
16 : : #define BPF_ARG_PTR_STACK RTE_BPF_ARG_RESERVED
17 : :
18 : : struct bpf_reg_val {
19 : : struct rte_bpf_arg v;
20 : : uint64_t mask;
21 : : struct {
22 : : int64_t min;
23 : : int64_t max;
24 : : } s;
25 : : struct {
26 : : uint64_t min;
27 : : uint64_t max;
28 : : } u;
29 : : };
30 : :
31 : : struct bpf_eval_state {
32 : : struct bpf_reg_val rv[EBPF_REG_NUM];
33 : : struct bpf_reg_val sv[MAX_BPF_STACK_SIZE / sizeof(uint64_t)];
34 : : };
35 : :
36 : : /* possible instruction node colour */
37 : : enum {
38 : : WHITE,
39 : : GREY,
40 : : BLACK,
41 : : MAX_NODE_COLOUR
42 : : };
43 : :
44 : : /* possible edge types */
45 : : enum {
46 : : UNKNOWN_EDGE,
47 : : TREE_EDGE,
48 : : BACK_EDGE,
49 : : CROSS_EDGE,
50 : : MAX_EDGE_TYPE
51 : : };
52 : :
53 : : #define MAX_EDGES 2
54 : :
55 : : struct inst_node {
56 : : uint8_t colour;
57 : : uint8_t nb_edge:4;
58 : : uint8_t cur_edge:4;
59 : : uint8_t edge_type[MAX_EDGES];
60 : : uint32_t edge_dest[MAX_EDGES];
61 : : uint32_t prev_node;
62 : : struct bpf_eval_state *evst;
63 : : };
64 : :
65 : : struct bpf_verifier {
66 : : const struct rte_bpf_prm *prm;
67 : : struct inst_node *in;
68 : : uint64_t stack_sz;
69 : : uint32_t nb_nodes;
70 : : uint32_t nb_jcc_nodes;
71 : : uint32_t nb_ldmb_nodes;
72 : : uint32_t node_colour[MAX_NODE_COLOUR];
73 : : uint32_t edge_type[MAX_EDGE_TYPE];
74 : : struct bpf_eval_state *evst;
75 : : struct inst_node *evin;
76 : : struct {
77 : : uint32_t num;
78 : : uint32_t cur;
79 : : struct bpf_eval_state *ent;
80 : : } evst_pool;
81 : : };
82 : :
83 : : struct bpf_ins_check {
84 : : struct {
85 : : uint16_t dreg;
86 : : uint16_t sreg;
87 : : } mask;
88 : : struct {
89 : : uint16_t min;
90 : : uint16_t max;
91 : : } off;
92 : : struct {
93 : : uint32_t min;
94 : : uint32_t max;
95 : : } imm;
96 : : const char * (*check)(const struct ebpf_insn *);
97 : : const char * (*eval)(struct bpf_verifier *, const struct ebpf_insn *);
98 : : };
99 : :
100 : : #define ALL_REGS RTE_LEN2MASK(EBPF_REG_NUM, uint16_t)
101 : : #define WRT_REGS RTE_LEN2MASK(EBPF_REG_10, uint16_t)
102 : : #define ZERO_REG RTE_LEN2MASK(EBPF_REG_1, uint16_t)
103 : :
104 : : /* For LD_IND R6 is an implicit CTX register. */
105 : : #define IND_SRC_REGS (WRT_REGS ^ 1 << EBPF_REG_6)
106 : :
107 : : /*
108 : : * check and evaluate functions for particular instruction types.
109 : : */
110 : :
111 : : static const char *
112 : 8 : check_alu_bele(const struct ebpf_insn *ins)
113 : : {
114 [ + + - + ]: 8 : if (ins->imm != 16 && ins->imm != 32 && ins->imm != 64)
115 : 0 : return "invalid imm field";
116 : : return NULL;
117 : : }
118 : :
119 : : static const char *
120 : 627 : eval_exit(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
121 : : {
122 : : RTE_SET_USED(ins);
123 [ - + ]: 627 : if (bvf->evst->rv[EBPF_REG_0].v.type == RTE_BPF_ARG_UNDEF)
124 : 0 : return "undefined return value";
125 : : return NULL;
126 : : }
127 : :
128 : : /* setup max possible with this mask bounds */
129 : : static void
130 : : eval_umax_bound(struct bpf_reg_val *rv, uint64_t mask)
131 : : {
132 : 363 : rv->u.max = mask;
133 : 363 : rv->u.min = 0;
134 : 59 : }
135 : :
136 : : static void
137 : : eval_smax_bound(struct bpf_reg_val *rv, uint64_t mask)
138 : : {
139 : 1676 : rv->s.max = mask >> 1;
140 : 1676 : rv->s.min = rv->s.max ^ UINT64_MAX;
141 : 65 : }
142 : :
143 : : static void
144 : : eval_max_bound(struct bpf_reg_val *rv, uint64_t mask)
145 : : {
146 : : eval_umax_bound(rv, mask);
147 : : eval_smax_bound(rv, mask);
148 : 7 : }
149 : :
150 : : static void
151 : : eval_fill_max_bound(struct bpf_reg_val *rv, uint64_t mask)
152 : : {
153 : : eval_max_bound(rv, mask);
154 : 275 : rv->v.type = RTE_BPF_ARG_RAW;
155 : 275 : rv->mask = mask;
156 : 4 : }
157 : :
158 : : static void
159 : : eval_fill_imm64(struct bpf_reg_val *rv, uint64_t mask, uint64_t val)
160 : : {
161 : 1220 : rv->mask = mask;
162 : 1359 : rv->s.min = val;
163 : 1351 : rv->s.max = val;
164 : 1351 : rv->u.min = val;
165 : 1351 : rv->u.max = val;
166 : 1 : }
167 : :
168 : : static void
169 : : eval_fill_imm(struct bpf_reg_val *rv, uint64_t mask, int32_t imm)
170 : : {
171 : : uint64_t v;
172 : :
173 : 1298 : v = (uint64_t)imm & mask;
174 : :
175 : 0 : rv->v.type = RTE_BPF_ARG_RAW;
176 : : eval_fill_imm64(rv, mask, v);
177 : 55 : }
178 : :
179 : : static const char *
180 : 5 : eval_ld_imm64(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
181 : : {
182 : : uint32_t i;
183 : : uint64_t val;
184 : : struct bpf_reg_val *rd;
185 : :
186 : 5 : val = (uint32_t)ins[0].imm | (uint64_t)(uint32_t)ins[1].imm << 32;
187 : :
188 : 5 : rd = bvf->evst->rv + ins->dst_reg;
189 : 5 : rd->v.type = RTE_BPF_ARG_RAW;
190 : : eval_fill_imm64(rd, UINT64_MAX, val);
191 : :
192 [ - + ]: 5 : for (i = 0; i != bvf->prm->nb_xsym; i++) {
193 : :
194 : : /* load of external variable */
195 [ # # ]: 0 : if (bvf->prm->xsym[i].type == RTE_BPF_XTYPE_VAR &&
196 [ # # ]: 0 : (uintptr_t)bvf->prm->xsym[i].var.val == val) {
197 : 0 : rd->v = bvf->prm->xsym[i].var.desc;
198 : : eval_fill_imm64(rd, UINT64_MAX, 0);
199 : : break;
200 : : }
201 : : }
202 : :
203 : 5 : return NULL;
204 : : }
205 : :
206 : : static void
207 : : eval_apply_mask(struct bpf_reg_val *rv, uint64_t mask)
208 : : {
209 : : struct bpf_reg_val rt;
210 : :
211 : 1325 : rt.u.min = rv->u.min & mask;
212 : 1325 : rt.u.max = rv->u.max & mask;
213 [ - + + - : 1317 : if (rt.u.min != rv->u.min || rt.u.max != rv->u.max) {
- + + + +
- + + ]
214 : 7 : rv->u.max = RTE_MAX(rt.u.max, mask);
215 : 61 : rv->u.min = 0;
216 : : }
217 : :
218 : : eval_smax_bound(&rt, mask);
219 : 1325 : rv->s.max = RTE_MIN(rt.s.max, rv->s.max);
220 : 1325 : rv->s.min = RTE_MAX(rt.s.min, rv->s.min);
221 : :
222 : 1270 : rv->mask = mask;
223 : 292 : }
224 : :
225 : : static void
226 : 229 : eval_add(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
227 : : {
228 : : struct bpf_reg_val rv;
229 : :
230 : 229 : rv.u.min = (rd->u.min + rs->u.min) & msk;
231 : 229 : rv.u.max = (rd->u.max + rs->u.max) & msk;
232 : 229 : rv.s.min = (rd->s.min + rs->s.min) & msk;
233 : 229 : rv.s.max = (rd->s.max + rs->s.max) & msk;
234 : :
235 : : /*
236 : : * if at least one of the operands is not constant,
237 : : * then check for overflow
238 : : */
239 [ + + - + : 229 : if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
+ - ]
240 [ + + ]: 78 : (rv.u.min < rd->u.min || rv.u.max < rd->u.max))
241 : : eval_umax_bound(&rv, msk);
242 : :
243 [ + + - + : 229 : if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
+ + ]
244 [ + + + + ]: 78 : (((rs->s.min < 0 && rv.s.min > rd->s.min) ||
245 [ - + ]: 57 : rv.s.min < rd->s.min) ||
246 [ - - + + ]: 57 : ((rs->s.max < 0 && rv.s.max > rd->s.max) ||
247 : : rv.s.max < rd->s.max)))
248 : : eval_smax_bound(&rv, msk);
249 : :
250 : 229 : rd->s = rv.s;
251 : 229 : rd->u = rv.u;
252 : 229 : }
253 : :
254 : : static void
255 : 6 : eval_sub(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
256 : : {
257 : : struct bpf_reg_val rv;
258 : :
259 : 6 : rv.u.min = (rd->u.min - rs->u.max) & msk;
260 : 6 : rv.u.max = (rd->u.max - rs->u.min) & msk;
261 : 6 : rv.s.min = (rd->s.min - rs->s.max) & msk;
262 : 6 : rv.s.max = (rd->s.max - rs->s.min) & msk;
263 : :
264 : : /*
265 : : * if at least one of the operands is not constant,
266 : : * then check for overflow
267 : : */
268 [ + + - + : 6 : if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
- + ]
269 [ # # ]: 0 : (rv.u.min > rd->u.min || rv.u.max > rd->u.max))
270 : : eval_umax_bound(&rv, msk);
271 : :
272 [ + + - + : 6 : if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
+ + ]
273 [ + - - + ]: 3 : (((rs->s.min < 0 && rv.s.min < rd->s.min) ||
274 [ # # ]: 0 : rv.s.min > rd->s.min) ||
275 [ # # # # ]: 0 : ((rs->s.max < 0 && rv.s.max < rd->s.max) ||
276 : : rv.s.max > rd->s.max)))
277 : : eval_smax_bound(&rv, msk);
278 : :
279 : 6 : rd->s = rv.s;
280 : 6 : rd->u = rv.u;
281 : 6 : }
282 : :
283 : : static void
284 : 31 : eval_lsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
285 : : uint64_t msk)
286 : : {
287 : : /* check if shift value is less then max result bits */
288 [ + + ]: 31 : if (rs->u.max >= opsz) {
289 : : eval_max_bound(rd, msk);
290 : 2 : return;
291 : : }
292 : :
293 : : /* check for overflow */
294 [ + + ]: 29 : if (rd->u.max > RTE_LEN2MASK(opsz - rs->u.max, uint64_t))
295 : : eval_umax_bound(rd, msk);
296 : : else {
297 : 2 : rd->u.max <<= rs->u.max;
298 : 2 : rd->u.min <<= rs->u.min;
299 : : }
300 : :
301 : : /* check that dreg values are and would remain always positive */
302 [ + + ]: 29 : if ((uint64_t)rd->s.min >> (opsz - 1) != 0 || rd->s.max >=
303 [ + - ]: 27 : RTE_LEN2MASK(opsz - rs->u.max - 1, int64_t))
304 : : eval_smax_bound(rd, msk);
305 : : else {
306 : 0 : rd->s.max <<= rs->u.max;
307 : 0 : rd->s.min <<= rs->u.min;
308 : : }
309 : : }
310 : :
311 : : static void
312 : 12 : eval_rsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
313 : : uint64_t msk)
314 : : {
315 : : /* check if shift value is less then max result bits */
316 [ + + ]: 12 : if (rs->u.max >= opsz) {
317 : : eval_max_bound(rd, msk);
318 : 1 : return;
319 : : }
320 : :
321 : 11 : rd->u.max >>= rs->u.min;
322 : 11 : rd->u.min >>= rs->u.max;
323 : :
324 : : /* check that dreg values are always positive */
325 [ + + ]: 11 : if ((uint64_t)rd->s.min >> (opsz - 1) != 0)
326 : : eval_smax_bound(rd, msk);
327 : : else {
328 : 6 : rd->s.max >>= rs->u.min;
329 : 6 : rd->s.min >>= rs->u.max;
330 : : }
331 : : }
332 : :
333 : : static void
334 : 2 : eval_arsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
335 : : uint64_t msk)
336 : : {
337 : : uint32_t shv;
338 : :
339 : : /* check if shift value is less then max result bits */
340 [ + + ]: 2 : if (rs->u.max >= opsz) {
341 : : eval_max_bound(rd, msk);
342 : 1 : return;
343 : : }
344 : :
345 : 1 : rd->u.max = (int64_t)rd->u.max >> rs->u.min;
346 : 1 : rd->u.min = (int64_t)rd->u.min >> rs->u.max;
347 : :
348 : : /* if we have 32-bit values - extend them to 64-bit */
349 [ - + ]: 1 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
350 : 0 : rd->s.min <<= opsz;
351 : 0 : rd->s.max <<= opsz;
352 : : shv = opsz;
353 : : } else
354 : : shv = 0;
355 : :
356 [ - + ]: 1 : if (rd->s.min < 0)
357 : 0 : rd->s.min = (rd->s.min >> (rs->u.min + shv)) & msk;
358 : : else
359 : 1 : rd->s.min = (rd->s.min >> (rs->u.max + shv)) & msk;
360 : :
361 [ + - ]: 1 : if (rd->s.max < 0)
362 : 1 : rd->s.max = (rd->s.max >> (rs->u.max + shv)) & msk;
363 : : else
364 : 0 : rd->s.max = (rd->s.max >> (rs->u.min + shv)) & msk;
365 : : }
366 : :
367 : : static uint64_t
368 : : eval_umax_bits(uint64_t v, size_t opsz)
369 : : {
370 [ + - + - : 147 : if (v == 0)
+ - + - +
- + - ]
371 : : return 0;
372 : :
373 : : v = rte_clz64(v);
374 : 294 : return RTE_LEN2MASK(opsz - v, uint64_t);
375 : : }
376 : :
377 : : /* estimate max possible value for (v1 & v2) */
378 : : static uint64_t
379 : : eval_uand_max(uint64_t v1, uint64_t v2, size_t opsz)
380 : : {
381 : : v1 = eval_umax_bits(v1, opsz);
382 : : v2 = eval_umax_bits(v2, opsz);
383 : 133 : return (v1 & v2);
384 : : }
385 : :
386 : : /* estimate max possible value for (v1 | v2) */
387 : : static uint64_t
388 : : eval_uor_max(uint64_t v1, uint64_t v2, size_t opsz)
389 : : {
390 : : v1 = eval_umax_bits(v1, opsz);
391 : : v2 = eval_umax_bits(v2, opsz);
392 : 14 : return (v1 | v2);
393 : : }
394 : :
395 : : static void
396 : 67 : eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
397 : : uint64_t msk)
398 : : {
399 : : /* both operands are constants */
400 [ - + - - ]: 67 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
401 : 0 : rd->u.min &= rs->u.min;
402 : 0 : rd->u.max &= rs->u.max;
403 : : } else {
404 [ + - ]: 67 : rd->u.max = eval_uand_max(rd->u.max, rs->u.max, opsz);
405 : 67 : rd->u.min &= rs->u.min;
406 : : }
407 : :
408 : : /* both operands are constants */
409 [ - + - - ]: 67 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
410 : 0 : rd->s.min &= rs->s.min;
411 : 0 : rd->s.max &= rs->s.max;
412 : : /* at least one of operand is non-negative */
413 [ + + + + ]: 67 : } else if (rd->s.min >= 0 || rs->s.min >= 0) {
414 : 132 : rd->s.max = eval_uand_max(rd->s.max & (msk >> 1),
415 [ + - ]: 66 : rs->s.max & (msk >> 1), opsz);
416 : 66 : rd->s.min &= rs->s.min;
417 : : } else
418 : : eval_smax_bound(rd, msk);
419 : 67 : }
420 : :
421 : : static void
422 : 259 : eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
423 : : uint64_t msk)
424 : : {
425 : : /* both operands are constants */
426 [ + + + - ]: 259 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
427 : 255 : rd->u.min |= rs->u.min;
428 : 255 : rd->u.max |= rs->u.max;
429 : : } else {
430 [ + - ]: 4 : rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
431 : 4 : rd->u.min |= rs->u.min;
432 : : }
433 : :
434 : : /* both operands are constants */
435 [ + + + - ]: 259 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
436 : 255 : rd->s.min |= rs->s.min;
437 : 255 : rd->s.max |= rs->s.max;
438 : :
439 : : /* both operands are non-negative */
440 [ - + - - ]: 4 : } else if (rd->s.min >= 0 || rs->s.min >= 0) {
441 [ + - ]: 4 : rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
442 : 4 : rd->s.min |= rs->s.min;
443 : : } else
444 : : eval_smax_bound(rd, msk);
445 : 259 : }
446 : :
447 : : static void
448 : 58 : eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
449 : : uint64_t msk)
450 : : {
451 : : /* both operands are constants */
452 [ + + + - ]: 58 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
453 : 55 : rd->u.min ^= rs->u.min;
454 : 55 : rd->u.max ^= rs->u.max;
455 : : } else {
456 [ + - ]: 3 : rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
457 : 3 : rd->u.min = 0;
458 : : }
459 : :
460 : : /* both operands are constants */
461 [ + + + - ]: 58 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
462 : 55 : rd->s.min ^= rs->s.min;
463 : 55 : rd->s.max ^= rs->s.max;
464 : :
465 : : /* both operands are non-negative */
466 [ + + + - ]: 3 : } else if (rd->s.min >= 0 || rs->s.min >= 0) {
467 [ + - ]: 3 : rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
468 : 3 : rd->s.min = 0;
469 : : } else
470 : : eval_smax_bound(rd, msk);
471 : 58 : }
472 : :
473 : : static void
474 : 9 : eval_mul(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
475 : : uint64_t msk)
476 : : {
477 : : /* both operands are constants */
478 [ + + - + ]: 9 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
479 : 0 : rd->u.min = (rd->u.min * rs->u.min) & msk;
480 : 0 : rd->u.max = (rd->u.max * rs->u.max) & msk;
481 : : /* check for overflow */
482 [ + + + + ]: 9 : } else if (rd->u.max <= msk >> opsz / 2 && rs->u.max <= msk >> opsz) {
483 : 1 : rd->u.max *= rs->u.max;
484 : 1 : rd->u.min *= rd->u.min;
485 : : } else
486 : : eval_umax_bound(rd, msk);
487 : :
488 : : /* both operands are constants */
489 [ + + - + ]: 9 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
490 : 0 : rd->s.min = (rd->s.min * rs->s.min) & msk;
491 : 0 : rd->s.max = (rd->s.max * rs->s.max) & msk;
492 : : /* check that both operands are positive and no overflow */
493 [ + - + + ]: 9 : } else if (rd->s.min >= 0 && rs->s.min >= 0) {
494 : 7 : rd->s.max *= rs->s.max;
495 : 7 : rd->s.min *= rd->s.min;
496 : : } else
497 : : eval_smax_bound(rd, msk);
498 : 9 : }
499 : :
500 : : static const char *
501 : 5 : eval_divmod(uint32_t op, struct bpf_reg_val *rd, struct bpf_reg_val *rs,
502 : : size_t opsz, uint64_t msk)
503 : : {
504 : : /* both operands are constants */
505 [ - + - - ]: 5 : if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
506 [ # # ]: 0 : if (rs->u.max == 0)
507 : : return "division by 0";
508 [ # # ]: 0 : if (op == BPF_DIV) {
509 : 0 : rd->u.min /= rs->u.min;
510 : 0 : rd->u.max /= rs->u.max;
511 : : } else {
512 : 0 : rd->u.min %= rs->u.min;
513 : 0 : rd->u.max %= rs->u.max;
514 : : }
515 : : } else {
516 [ + + ]: 5 : if (op == BPF_MOD)
517 : 2 : rd->u.max = RTE_MIN(rd->u.max, rs->u.max - 1);
518 : : else
519 : : rd->u.max = rd->u.max;
520 : 5 : rd->u.min = 0;
521 : : }
522 : :
523 : : /* if we have 32-bit values - extend them to 64-bit */
524 [ + + ]: 5 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
525 : 3 : rd->s.min = (int32_t)rd->s.min;
526 : 3 : rd->s.max = (int32_t)rd->s.max;
527 : 3 : rs->s.min = (int32_t)rs->s.min;
528 : 3 : rs->s.max = (int32_t)rs->s.max;
529 : : }
530 : :
531 : : /* both operands are constants */
532 [ - + - - ]: 5 : if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
533 [ # # ]: 0 : if (rs->s.max == 0)
534 : : return "division by 0";
535 [ # # ]: 0 : if (op == BPF_DIV) {
536 : 0 : rd->s.min /= rs->s.min;
537 : 0 : rd->s.max /= rs->s.max;
538 : : } else {
539 : 0 : rd->s.min %= rs->s.min;
540 : 0 : rd->s.max %= rs->s.max;
541 : : }
542 [ + + ]: 5 : } else if (op == BPF_MOD) {
543 : : rd->s.min = RTE_MAX(rd->s.max, 0);
544 : 2 : rd->s.min = RTE_MIN(rd->s.min, 0);
545 : : } else
546 : : eval_smax_bound(rd, msk);
547 : :
548 : 5 : rd->s.max &= msk;
549 : 5 : rd->s.min &= msk;
550 : :
551 : 5 : return NULL;
552 : : }
553 : :
554 : : static void
555 : 2 : eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t msk)
556 : : {
557 : : uint64_t ux, uy;
558 : : int64_t sx, sy;
559 : :
560 : : /* if we have 32-bit values - extend them to 64-bit */
561 [ + + ]: 2 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
562 : 1 : rd->u.min = (int32_t)rd->u.min;
563 : 1 : rd->u.max = (int32_t)rd->u.max;
564 : : }
565 : :
566 : 2 : ux = -(int64_t)rd->u.min & msk;
567 : 2 : uy = -(int64_t)rd->u.max & msk;
568 : :
569 : 2 : rd->u.max = RTE_MAX(ux, uy);
570 : 2 : rd->u.min = RTE_MIN(ux, uy);
571 : :
572 : : /* if we have 32-bit values - extend them to 64-bit */
573 [ + + ]: 2 : if (opsz == sizeof(uint32_t) * CHAR_BIT) {
574 : 1 : rd->s.min = (int32_t)rd->s.min;
575 : 1 : rd->s.max = (int32_t)rd->s.max;
576 : : }
577 : :
578 : 2 : sx = -rd->s.min & msk;
579 : 2 : sy = -rd->s.max & msk;
580 : :
581 : 2 : rd->s.max = RTE_MAX(sx, sy);
582 : 2 : rd->s.min = RTE_MIN(sx, sy);
583 : 2 : }
584 : :
585 : : static const char *
586 : 266 : eval_ld_mbuf(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
587 : : {
588 : : uint32_t i, mode;
589 : : struct bpf_reg_val *rv, ri, rs;
590 : :
591 : 266 : mode = BPF_MODE(ins->code);
592 : :
593 : : /* R6 is an implicit input that must contain pointer to mbuf */
594 [ + - ]: 266 : if (bvf->evst->rv[EBPF_REG_6].v.type != RTE_BPF_ARG_PTR_MBUF)
595 : : return "invalid type for implicit ctx register";
596 : :
597 [ + + ]: 266 : if (mode == BPF_IND) {
598 : 59 : rs = bvf->evst->rv[ins->src_reg];
599 [ + - ]: 59 : if (rs.v.type != RTE_BPF_ARG_RAW)
600 : : return "unexpected type for src register";
601 : :
602 : 59 : eval_fill_imm(&ri, UINT64_MAX, ins->imm);
603 : 59 : eval_add(&rs, &ri, UINT64_MAX);
604 : :
605 [ + - + - ]: 59 : if (rs.s.max < 0 || rs.u.min > UINT32_MAX)
606 : : return "mbuf boundary violation";
607 : : }
608 : :
609 : : /* R1-R5 scratch registers */
610 [ + + ]: 1596 : for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
611 : 1330 : bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;
612 : :
613 : : /* R0 is an implicit output, contains data fetched from the packet */
614 : : rv = bvf->evst->rv + EBPF_REG_0;
615 [ + + ]: 266 : rv->v.size = bpf_size(BPF_SIZE(ins->code));
616 : 266 : eval_fill_max_bound(rv, RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
617 : :
618 : 266 : return NULL;
619 : : }
620 : :
621 : : /*
622 : : * check that destination and source operand are in defined state.
623 : : */
624 : : static const char *
625 : : eval_defined(const struct bpf_reg_val *dst, const struct bpf_reg_val *src)
626 : : {
627 [ + - + - : 1081 : if (dst != NULL && dst->v.type == RTE_BPF_ARG_UNDEF)
+ - + - ]
628 : : return "dest reg value is undefined";
629 [ + - - + : 1677 : if (src != NULL && src->v.type == RTE_BPF_ARG_UNDEF)
+ - + + -
+ ]
630 : : return "src reg value is undefined";
631 : : return NULL;
632 : : }
633 : :
634 : : static const char *
635 : 1033 : eval_alu(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
636 : : {
637 : : uint64_t msk;
638 : : uint32_t op;
639 : : size_t opsz;
640 : : const char *err;
641 : : struct bpf_eval_state *st;
642 : : struct bpf_reg_val *rd, rs;
643 : :
644 : 1033 : opsz = (BPF_CLASS(ins->code) == BPF_ALU) ?
645 [ + + ]: 1033 : sizeof(uint32_t) : sizeof(uint64_t);
646 : 1033 : opsz = opsz * CHAR_BIT;
647 : 1033 : msk = RTE_LEN2MASK(opsz, uint64_t);
648 : :
649 : 1033 : st = bvf->evst;
650 : 1033 : rd = st->rv + ins->dst_reg;
651 : :
652 [ + + ]: 1033 : if (BPF_SRC(ins->code) == BPF_X) {
653 [ + + ]: 234 : rs = st->rv[ins->src_reg];
654 : : eval_apply_mask(&rs, msk);
655 : : } else
656 : 799 : eval_fill_imm(&rs, msk, ins->imm);
657 : :
658 : : eval_apply_mask(rd, msk);
659 : :
660 : 1033 : op = BPF_OP(ins->code);
661 : :
662 : : /* Allow self-xor as way to zero register */
663 [ + + + + ]: 1033 : if (op == BPF_XOR && BPF_SRC(ins->code) == BPF_X &&
664 [ + + ]: 56 : ins->src_reg == ins->dst_reg) {
665 : : eval_fill_imm(&rs, UINT64_MAX, 0);
666 : : eval_fill_imm(rd, UINT64_MAX, 0);
667 : : }
668 : :
669 [ + + + + ]: 1035 : err = eval_defined((op != EBPF_MOV) ? rd : NULL,
670 : : (op != BPF_NEG) ? &rs : NULL);
671 : : if (err != NULL)
672 : 0 : return err;
673 : :
674 [ + + ]: 1033 : if (op == BPF_ADD)
675 : 39 : eval_add(rd, &rs, msk);
676 : : else if (op == BPF_SUB)
677 : 6 : eval_sub(rd, &rs, msk);
678 : : else if (op == BPF_LSH)
679 : 31 : eval_lsh(rd, &rs, opsz, msk);
680 : : else if (op == BPF_RSH)
681 : 12 : eval_rsh(rd, &rs, opsz, msk);
682 : : else if (op == EBPF_ARSH)
683 : 2 : eval_arsh(rd, &rs, opsz, msk);
684 : : else if (op == BPF_AND)
685 : 67 : eval_and(rd, &rs, opsz, msk);
686 : : else if (op == BPF_OR)
687 : 259 : eval_or(rd, &rs, opsz, msk);
688 : : else if (op == BPF_XOR)
689 : 58 : eval_xor(rd, &rs, opsz, msk);
690 : : else if (op == BPF_MUL)
691 : 9 : eval_mul(rd, &rs, opsz, msk);
692 : : else if (op == BPF_DIV || op == BPF_MOD)
693 : 5 : err = eval_divmod(op, rd, &rs, opsz, msk);
694 : : else if (op == BPF_NEG)
695 : 2 : eval_neg(rd, opsz, msk);
696 : : else if (op == EBPF_MOV)
697 : 543 : *rd = rs;
698 : : else
699 : : eval_max_bound(rd, msk);
700 : :
701 : : return err;
702 : : }
703 : :
704 : : static const char *
705 : 10 : eval_bele(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
706 : : {
707 : : uint64_t msk;
708 : : struct bpf_eval_state *st;
709 : : struct bpf_reg_val *rd;
710 : : const char *err;
711 : :
712 : 10 : msk = RTE_LEN2MASK(ins->imm, uint64_t);
713 : :
714 : 10 : st = bvf->evst;
715 [ + - ]: 10 : rd = st->rv + ins->dst_reg;
716 : :
717 : : err = eval_defined(rd, NULL);
718 : : if (err != NULL)
719 : : return err;
720 : :
721 : : #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
722 [ + + ]: 10 : if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_BE))
723 : : eval_max_bound(rd, msk);
724 : : else
725 : : eval_apply_mask(rd, msk);
726 : : #else
727 : : if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_LE))
728 : : eval_max_bound(rd, msk);
729 : : else
730 : : eval_apply_mask(rd, msk);
731 : : #endif
732 : :
733 : : return NULL;
734 : : }
735 : :
736 : : static const char *
737 : 131 : eval_ptr(struct bpf_verifier *bvf, struct bpf_reg_val *rm, uint32_t opsz,
738 : : uint32_t align, int16_t off)
739 : : {
740 : : struct bpf_reg_val rv;
741 : :
742 : : /* calculate reg + offset */
743 : 131 : eval_fill_imm(&rv, rm->mask, off);
744 : 131 : eval_add(rm, &rv, rm->mask);
745 : :
746 [ + - ]: 131 : if (RTE_BPF_ARG_PTR_TYPE(rm->v.type) == 0)
747 : : return "destination is not a pointer";
748 : :
749 [ + - ]: 131 : if (rm->mask != UINT64_MAX)
750 : : return "pointer truncation";
751 : :
752 [ + - ]: 131 : if (rm->u.max + opsz > rm->v.size ||
753 [ + - ]: 131 : (uint64_t)rm->s.max + opsz > rm->v.size ||
754 [ + - ]: 131 : rm->s.min < 0)
755 : : return "memory boundary violation";
756 : :
757 [ + - ]: 131 : if (rm->u.max % align != 0)
758 : : return "unaligned memory access";
759 : :
760 [ + + ]: 131 : if (rm->v.type == BPF_ARG_PTR_STACK) {
761 : :
762 [ + - + - : 39 : if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
+ - ]
763 : : rm->u.max != (uint64_t)rm->s.max)
764 : : return "stack access with variable offset";
765 : :
766 : 39 : bvf->stack_sz = RTE_MAX(bvf->stack_sz, rm->v.size - rm->u.max);
767 : :
768 : : /* pointer to mbuf */
769 [ + + ]: 92 : } else if (rm->v.type == RTE_BPF_ARG_PTR_MBUF) {
770 : :
771 [ + - + - : 1 : if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
- + ]
772 : : rm->u.max != (uint64_t)rm->s.max)
773 : 0 : return "mbuf access with variable offset";
774 : : }
775 : :
776 : : return NULL;
777 : : }
778 : :
779 : : static void
780 : : eval_max_load(struct bpf_reg_val *rv, uint64_t mask)
781 : : {
782 : : eval_umax_bound(rv, mask);
783 : :
784 : : /* full 64-bit load */
785 : : if (mask == UINT64_MAX)
786 : : eval_smax_bound(rv, mask);
787 : :
788 : : /* zero-extend load */
789 : 42 : rv->s.min = rv->u.min;
790 : 42 : rv->s.max = rv->u.max;
791 : : }
792 : :
793 : :
794 : : static const char *
795 : 57 : eval_load(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
796 : : {
797 : : uint32_t opsz;
798 : : uint64_t msk;
799 : : const char *err;
800 : : struct bpf_eval_state *st;
801 : : struct bpf_reg_val *rd, rs;
802 : : const struct bpf_reg_val *sv;
803 : :
804 : 57 : st = bvf->evst;
805 : 57 : rd = st->rv + ins->dst_reg;
806 : 57 : rs = st->rv[ins->src_reg];
807 [ + + ]: 57 : opsz = bpf_size(BPF_SIZE(ins->code));
808 : 57 : msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);
809 : :
810 : 57 : err = eval_ptr(bvf, &rs, opsz, 1, ins->off);
811 [ + - ]: 57 : if (err != NULL)
812 : : return err;
813 : :
814 [ + + ]: 57 : if (rs.v.type == BPF_ARG_PTR_STACK) {
815 : :
816 : 15 : sv = st->sv + rs.u.max / sizeof(uint64_t);
817 [ + - + - ]: 15 : if (sv->v.type == RTE_BPF_ARG_UNDEF || sv->mask < msk)
818 : : return "undefined value on the stack";
819 : :
820 : 15 : *rd = *sv;
821 : :
822 : : /* pointer to mbuf */
823 [ + + ]: 42 : } else if (rs.v.type == RTE_BPF_ARG_PTR_MBUF) {
824 : :
825 [ - + ]: 1 : if (rs.u.max == offsetof(struct rte_mbuf, next)) {
826 : : eval_fill_imm(rd, msk, 0);
827 : 0 : rd->v = rs.v;
828 [ - + ]: 1 : } else if (rs.u.max == offsetof(struct rte_mbuf, buf_addr)) {
829 : : eval_fill_imm(rd, msk, 0);
830 : 0 : rd->v.type = RTE_BPF_ARG_PTR;
831 : 0 : rd->v.size = rs.v.buf_size;
832 [ - + ]: 1 : } else if (rs.u.max == offsetof(struct rte_mbuf, data_off)) {
833 : : eval_fill_imm(rd, msk, RTE_PKTMBUF_HEADROOM);
834 : : rd->v.type = RTE_BPF_ARG_RAW;
835 : : } else {
836 : : eval_max_load(rd, msk);
837 : 1 : rd->v.type = RTE_BPF_ARG_RAW;
838 : : }
839 : :
840 : : /* pointer to raw data */
841 : : } else {
842 : : eval_max_load(rd, msk);
843 : 41 : rd->v.type = RTE_BPF_ARG_RAW;
844 : : }
845 : :
846 : : return NULL;
847 : : }
848 : :
849 : : static const char *
850 : : eval_mbuf_store(const struct bpf_reg_val *rv, uint32_t opsz)
851 : : {
852 : : uint32_t i;
853 : :
854 : : static const struct {
855 : : size_t off;
856 : : size_t sz;
857 : : } mbuf_ro_fileds[] = {
858 : : { .off = offsetof(struct rte_mbuf, buf_addr), },
859 : : { .off = offsetof(struct rte_mbuf, refcnt), },
860 : : { .off = offsetof(struct rte_mbuf, nb_segs), },
861 : : { .off = offsetof(struct rte_mbuf, buf_len), },
862 : : { .off = offsetof(struct rte_mbuf, pool), },
863 : : { .off = offsetof(struct rte_mbuf, next), },
864 : : { .off = offsetof(struct rte_mbuf, priv_size), },
865 : : };
866 : :
867 [ # # ]: 0 : for (i = 0; i != RTE_DIM(mbuf_ro_fileds) &&
868 : 0 : (mbuf_ro_fileds[i].off + mbuf_ro_fileds[i].sz <=
869 [ # # # # ]: 0 : rv->u.max || rv->u.max + opsz <= mbuf_ro_fileds[i].off);
870 : 0 : i++)
871 : : ;
872 : :
873 [ # # ]: 0 : if (i != RTE_DIM(mbuf_ro_fileds))
874 : : return "store to the read-only mbuf field";
875 : :
876 : : return NULL;
877 : :
878 : : }
879 : :
880 : : static const char *
881 : 63 : eval_store(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
882 : : {
883 : : uint32_t opsz;
884 : : uint64_t msk;
885 : : const char *err;
886 : : struct bpf_eval_state *st;
887 : : struct bpf_reg_val rd, rs, *sv;
888 : :
889 [ + + ]: 63 : opsz = bpf_size(BPF_SIZE(ins->code));
890 : 63 : msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);
891 : :
892 : 63 : st = bvf->evst;
893 : 63 : rd = st->rv[ins->dst_reg];
894 : :
895 [ + + ]: 63 : if (BPF_CLASS(ins->code) == BPF_STX) {
896 [ + + ]: 55 : rs = st->rv[ins->src_reg];
897 : : eval_apply_mask(&rs, msk);
898 : : } else
899 : 8 : eval_fill_imm(&rs, msk, ins->imm);
900 : :
901 : : err = eval_defined(NULL, &rs);
902 : : if (err != NULL)
903 : : return err;
904 : :
905 : 63 : err = eval_ptr(bvf, &rd, opsz, 1, ins->off);
906 [ + - ]: 63 : if (err != NULL)
907 : : return err;
908 : :
909 [ + + ]: 63 : if (rd.v.type == BPF_ARG_PTR_STACK) {
910 : :
911 : 15 : sv = st->sv + rd.u.max / sizeof(uint64_t);
912 [ - + ]: 15 : if (BPF_CLASS(ins->code) == BPF_STX &&
913 : : BPF_MODE(ins->code) == EBPF_XADD)
914 : : eval_max_bound(sv, msk);
915 : : else
916 : 15 : *sv = rs;
917 : :
918 : : /* pointer to mbuf */
919 [ - + ]: 48 : } else if (rd.v.type == RTE_BPF_ARG_PTR_MBUF) {
920 : : err = eval_mbuf_store(&rd, opsz);
921 : : if (err != NULL)
922 : 0 : return err;
923 : : }
924 : :
925 : : return NULL;
926 : : }
927 : :
928 : : static const char *
929 : 16 : eval_func_arg(struct bpf_verifier *bvf, const struct rte_bpf_arg *arg,
930 : : struct bpf_reg_val *rv)
931 : : {
932 : : uint32_t i, n;
933 : : struct bpf_eval_state *st;
934 : : const char *err;
935 : :
936 : 16 : st = bvf->evst;
937 : :
938 [ + - ]: 16 : if (rv->v.type == RTE_BPF_ARG_UNDEF)
939 : : return "Undefined argument type";
940 : :
941 [ + + + - ]: 16 : if (arg->type != rv->v.type &&
942 [ + - ]: 9 : arg->type != RTE_BPF_ARG_RAW &&
943 : 9 : (arg->type != RTE_BPF_ARG_PTR ||
944 [ + - ]: 9 : RTE_BPF_ARG_PTR_TYPE(rv->v.type) == 0))
945 : : return "Invalid argument type";
946 : :
947 : : err = NULL;
948 : :
949 : : /* argument is a pointer */
950 [ + + ]: 16 : if (RTE_BPF_ARG_PTR_TYPE(arg->type) != 0) {
951 : :
952 : 11 : err = eval_ptr(bvf, rv, arg->size, 1, 0);
953 : :
954 : : /*
955 : : * pointer to the variable on the stack is passed
956 : : * as an argument, mark stack space it occupies as initialized.
957 : : */
958 [ + - + + ]: 11 : if (err == NULL && rv->v.type == BPF_ARG_PTR_STACK) {
959 : :
960 : 9 : i = rv->u.max / sizeof(uint64_t);
961 : 9 : n = i + arg->size / sizeof(uint64_t);
962 [ + + ]: 14 : while (i != n) {
963 : 5 : eval_fill_max_bound(st->sv + i, UINT64_MAX);
964 : 5 : i++;
965 : : };
966 : : }
967 : : }
968 : :
969 : : return err;
970 : : }
971 : :
972 : : static const char *
973 : 7 : eval_call(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
974 : : {
975 : : uint32_t i, idx;
976 : : struct bpf_reg_val *rv;
977 : : const struct rte_bpf_xsym *xsym;
978 : : const char *err;
979 : :
980 : 7 : idx = ins->imm;
981 : :
982 [ + - ]: 7 : if (idx >= bvf->prm->nb_xsym ||
983 [ + - ]: 7 : bvf->prm->xsym[idx].type != RTE_BPF_XTYPE_FUNC)
984 : : return "invalid external function index";
985 : :
986 : : /* for now don't support function calls on 32 bit platform */
987 : : if (sizeof(uint64_t) != sizeof(uintptr_t))
988 : : return "function calls are supported only for 64 bit apps";
989 : :
990 : : xsym = bvf->prm->xsym + idx;
991 : :
992 : : /* evaluate function arguments */
993 : : err = NULL;
994 [ + + + - ]: 23 : for (i = 0; i != xsym->func.nb_args && err == NULL; i++) {
995 : 16 : err = eval_func_arg(bvf, xsym->func.args + i,
996 : 16 : bvf->evst->rv + EBPF_REG_1 + i);
997 : : }
998 : :
999 : : /* R1-R5 argument/scratch registers */
1000 [ + + ]: 42 : for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
1001 : 35 : bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;
1002 : :
1003 : : /* update return value */
1004 : :
1005 : 7 : rv = bvf->evst->rv + EBPF_REG_0;
1006 : 7 : rv->v = xsym->func.ret;
1007 [ + + ]: 7 : if (rv->v.type == RTE_BPF_ARG_RAW)
1008 : 4 : eval_fill_max_bound(rv,
1009 : 4 : RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
1010 [ + + ]: 3 : else if (RTE_BPF_ARG_PTR_TYPE(rv->v.type) != 0)
1011 : : eval_fill_imm64(rv, UINTPTR_MAX, 0);
1012 : :
1013 : : return err;
1014 : : }
1015 : :
1016 : : static void
1017 : 304 : eval_jeq_jne(struct bpf_reg_val *trd, struct bpf_reg_val *trs)
1018 : : {
1019 : : /* sreg is constant */
1020 [ + + ]: 304 : if (trs->u.min == trs->u.max) {
1021 : 286 : trd->u = trs->u;
1022 : : /* dreg is constant */
1023 [ + + ]: 18 : } else if (trd->u.min == trd->u.max) {
1024 : 8 : trs->u = trd->u;
1025 : : } else {
1026 : 10 : trd->u.max = RTE_MIN(trd->u.max, trs->u.max);
1027 : 10 : trd->u.min = RTE_MAX(trd->u.min, trs->u.min);
1028 : 10 : trs->u = trd->u;
1029 : : }
1030 : :
1031 : : /* sreg is constant */
1032 [ + + ]: 304 : if (trs->s.min == trs->s.max) {
1033 : 286 : trd->s = trs->s;
1034 : : /* dreg is constant */
1035 [ + + ]: 18 : } else if (trd->s.min == trd->s.max) {
1036 : 8 : trs->s = trd->s;
1037 : : } else {
1038 : 10 : trd->s.max = RTE_MIN(trd->s.max, trs->s.max);
1039 : 10 : trd->s.min = RTE_MAX(trd->s.min, trs->s.min);
1040 : 10 : trs->s = trd->s;
1041 : : }
1042 : 304 : }
1043 : :
1044 : : static void
1045 : : eval_jgt_jle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1046 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1047 : : {
1048 : 72 : frd->u.max = RTE_MIN(frd->u.max, frs->u.min);
1049 : 72 : trd->u.min = RTE_MAX(trd->u.min, trs->u.min + 1);
1050 : 72 : }
1051 : :
1052 : : static void
1053 : : eval_jlt_jge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1054 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1055 : : {
1056 : 5 : frd->u.min = RTE_MAX(frd->u.min, frs->u.min);
1057 : 5 : trd->u.max = RTE_MIN(trd->u.max, trs->u.max - 1);
1058 : 5 : }
1059 : :
1060 : : static void
1061 : : eval_jsgt_jsle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1062 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1063 : : {
1064 : 34 : frd->s.max = RTE_MIN(frd->s.max, frs->s.min);
1065 : 34 : trd->s.min = RTE_MAX(trd->s.min, trs->s.min + 1);
1066 : 34 : }
1067 : :
1068 : : static void
1069 : : eval_jslt_jsge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1070 : : struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1071 : : {
1072 : 0 : frd->s.min = RTE_MAX(frd->s.min, frs->s.min);
1073 : 0 : trd->s.max = RTE_MIN(trd->s.max, trs->s.max - 1);
1074 : 0 : }
1075 : :
1076 : : static const char *
1077 : 581 : eval_jcc(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1078 : : {
1079 : : uint32_t op;
1080 : : const char *err;
1081 : : struct bpf_eval_state *fst, *tst;
1082 : : struct bpf_reg_val *frd, *frs, *trd, *trs;
1083 : : struct bpf_reg_val rvf, rvt;
1084 : :
1085 : 581 : tst = bvf->evst;
1086 : 581 : fst = bvf->evin->evst;
1087 : :
1088 : 581 : frd = fst->rv + ins->dst_reg;
1089 : 581 : trd = tst->rv + ins->dst_reg;
1090 : :
1091 [ + + ]: 581 : if (BPF_SRC(ins->code) == BPF_X) {
1092 : 280 : frs = fst->rv + ins->src_reg;
1093 : 280 : trs = tst->rv + ins->src_reg;
1094 : : } else {
1095 : : frs = &rvf;
1096 : : trs = &rvt;
1097 : 301 : eval_fill_imm(frs, UINT64_MAX, ins->imm);
1098 : : eval_fill_imm(trs, UINT64_MAX, ins->imm);
1099 : : }
1100 : :
1101 : : err = eval_defined(trd, trs);
1102 : : if (err != NULL)
1103 : 0 : return err;
1104 : :
1105 : 581 : op = BPF_OP(ins->code);
1106 : :
1107 [ + + ]: 581 : if (op == BPF_JEQ)
1108 : 171 : eval_jeq_jne(trd, trs);
1109 [ + + ]: 410 : else if (op == EBPF_JNE)
1110 : 133 : eval_jeq_jne(frd, frs);
1111 [ + + ]: 277 : else if (op == BPF_JGT)
1112 : : eval_jgt_jle(trd, trs, frd, frs);
1113 [ + + ]: 269 : else if (op == EBPF_JLE)
1114 : : eval_jgt_jle(frd, frs, trd, trs);
1115 [ - + ]: 205 : else if (op == EBPF_JLT)
1116 : : eval_jlt_jge(trd, trs, frd, frs);
1117 [ + + ]: 205 : else if (op == BPF_JGE)
1118 : : eval_jlt_jge(frd, frs, trd, trs);
1119 [ + + ]: 200 : else if (op == EBPF_JSGT)
1120 : : eval_jsgt_jsle(trd, trs, frd, frs);
1121 [ + + ]: 168 : else if (op == EBPF_JSLE)
1122 : : eval_jsgt_jsle(frd, frs, trd, trs);
1123 [ - + ]: 166 : else if (op == EBPF_JSLT)
1124 : : eval_jslt_jsge(trd, trs, frd, frs);
1125 [ - + ]: 166 : else if (op == EBPF_JSGE)
1126 : : eval_jslt_jsge(frd, frs, trd, trs);
1127 : :
1128 : : return NULL;
1129 : : }
1130 : :
1131 : : /*
1132 : : * validate parameters for each instruction type.
1133 : : */
1134 : : static const struct bpf_ins_check ins_chk[UINT8_MAX + 1] = {
1135 : : /* ALU IMM 32-bit instructions */
1136 : : [(BPF_ALU | BPF_ADD | BPF_K)] = {
1137 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1138 : : .off = { .min = 0, .max = 0},
1139 : : .imm = { .min = 0, .max = UINT32_MAX,},
1140 : : .eval = eval_alu,
1141 : : },
1142 : : [(BPF_ALU | BPF_SUB | BPF_K)] = {
1143 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1144 : : .off = { .min = 0, .max = 0},
1145 : : .imm = { .min = 0, .max = UINT32_MAX,},
1146 : : .eval = eval_alu,
1147 : : },
1148 : : [(BPF_ALU | BPF_AND | BPF_K)] = {
1149 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1150 : : .off = { .min = 0, .max = 0},
1151 : : .imm = { .min = 0, .max = UINT32_MAX,},
1152 : : .eval = eval_alu,
1153 : : },
1154 : : [(BPF_ALU | BPF_OR | BPF_K)] = {
1155 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1156 : : .off = { .min = 0, .max = 0},
1157 : : .imm = { .min = 0, .max = UINT32_MAX,},
1158 : : .eval = eval_alu,
1159 : : },
1160 : : [(BPF_ALU | BPF_LSH | BPF_K)] = {
1161 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1162 : : .off = { .min = 0, .max = 0},
1163 : : .imm = { .min = 0, .max = UINT32_MAX,},
1164 : : .eval = eval_alu,
1165 : : },
1166 : : [(BPF_ALU | BPF_RSH | BPF_K)] = {
1167 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1168 : : .off = { .min = 0, .max = 0},
1169 : : .imm = { .min = 0, .max = UINT32_MAX,},
1170 : : .eval = eval_alu,
1171 : : },
1172 : : [(BPF_ALU | BPF_XOR | BPF_K)] = {
1173 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1174 : : .off = { .min = 0, .max = 0},
1175 : : .imm = { .min = 0, .max = UINT32_MAX,},
1176 : : .eval = eval_alu,
1177 : : },
1178 : : [(BPF_ALU | BPF_MUL | BPF_K)] = {
1179 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1180 : : .off = { .min = 0, .max = 0},
1181 : : .imm = { .min = 0, .max = UINT32_MAX,},
1182 : : .eval = eval_alu,
1183 : : },
1184 : : [(BPF_ALU | EBPF_MOV | BPF_K)] = {
1185 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1186 : : .off = { .min = 0, .max = 0},
1187 : : .imm = { .min = 0, .max = UINT32_MAX,},
1188 : : .eval = eval_alu,
1189 : : },
1190 : : [(BPF_ALU | BPF_DIV | BPF_K)] = {
1191 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1192 : : .off = { .min = 0, .max = 0},
1193 : : .imm = { .min = 1, .max = UINT32_MAX},
1194 : : .eval = eval_alu,
1195 : : },
1196 : : [(BPF_ALU | BPF_MOD | BPF_K)] = {
1197 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1198 : : .off = { .min = 0, .max = 0},
1199 : : .imm = { .min = 1, .max = UINT32_MAX},
1200 : : .eval = eval_alu,
1201 : : },
1202 : : /* ALU IMM 64-bit instructions */
1203 : : [(EBPF_ALU64 | BPF_ADD | BPF_K)] = {
1204 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1205 : : .off = { .min = 0, .max = 0},
1206 : : .imm = { .min = 0, .max = UINT32_MAX,},
1207 : : .eval = eval_alu,
1208 : : },
1209 : : [(EBPF_ALU64 | BPF_SUB | BPF_K)] = {
1210 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1211 : : .off = { .min = 0, .max = 0},
1212 : : .imm = { .min = 0, .max = UINT32_MAX,},
1213 : : .eval = eval_alu,
1214 : : },
1215 : : [(EBPF_ALU64 | BPF_AND | BPF_K)] = {
1216 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1217 : : .off = { .min = 0, .max = 0},
1218 : : .imm = { .min = 0, .max = UINT32_MAX,},
1219 : : .eval = eval_alu,
1220 : : },
1221 : : [(EBPF_ALU64 | BPF_OR | BPF_K)] = {
1222 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1223 : : .off = { .min = 0, .max = 0},
1224 : : .imm = { .min = 0, .max = UINT32_MAX,},
1225 : : .eval = eval_alu,
1226 : : },
1227 : : [(EBPF_ALU64 | BPF_LSH | BPF_K)] = {
1228 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1229 : : .off = { .min = 0, .max = 0},
1230 : : .imm = { .min = 0, .max = UINT32_MAX,},
1231 : : .eval = eval_alu,
1232 : : },
1233 : : [(EBPF_ALU64 | BPF_RSH | BPF_K)] = {
1234 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1235 : : .off = { .min = 0, .max = 0},
1236 : : .imm = { .min = 0, .max = UINT32_MAX,},
1237 : : .eval = eval_alu,
1238 : : },
1239 : : [(EBPF_ALU64 | EBPF_ARSH | BPF_K)] = {
1240 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1241 : : .off = { .min = 0, .max = 0},
1242 : : .imm = { .min = 0, .max = UINT32_MAX,},
1243 : : .eval = eval_alu,
1244 : : },
1245 : : [(EBPF_ALU64 | BPF_XOR | BPF_K)] = {
1246 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1247 : : .off = { .min = 0, .max = 0},
1248 : : .imm = { .min = 0, .max = UINT32_MAX,},
1249 : : .eval = eval_alu,
1250 : : },
1251 : : [(EBPF_ALU64 | BPF_MUL | BPF_K)] = {
1252 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1253 : : .off = { .min = 0, .max = 0},
1254 : : .imm = { .min = 0, .max = UINT32_MAX,},
1255 : : .eval = eval_alu,
1256 : : },
1257 : : [(EBPF_ALU64 | EBPF_MOV | BPF_K)] = {
1258 : : .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1259 : : .off = { .min = 0, .max = 0},
1260 : : .imm = { .min = 0, .max = UINT32_MAX,},
1261 : : .eval = eval_alu,
1262 : : },
1263 : : [(EBPF_ALU64 | BPF_DIV | BPF_K)] = {
1264 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1265 : : .off = { .min = 0, .max = 0},
1266 : : .imm = { .min = 1, .max = UINT32_MAX},
1267 : : .eval = eval_alu,
1268 : : },
1269 : : [(EBPF_ALU64 | BPF_MOD | BPF_K)] = {
1270 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1271 : : .off = { .min = 0, .max = 0},
1272 : : .imm = { .min = 1, .max = UINT32_MAX},
1273 : : .eval = eval_alu,
1274 : : },
1275 : : /* ALU REG 32-bit instructions */
1276 : : [(BPF_ALU | BPF_ADD | BPF_X)] = {
1277 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1278 : : .off = { .min = 0, .max = 0},
1279 : : .imm = { .min = 0, .max = 0},
1280 : : .eval = eval_alu,
1281 : : },
1282 : : [(BPF_ALU | BPF_SUB | BPF_X)] = {
1283 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1284 : : .off = { .min = 0, .max = 0},
1285 : : .imm = { .min = 0, .max = 0},
1286 : : .eval = eval_alu,
1287 : : },
1288 : : [(BPF_ALU | BPF_AND | BPF_X)] = {
1289 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1290 : : .off = { .min = 0, .max = 0},
1291 : : .imm = { .min = 0, .max = 0},
1292 : : .eval = eval_alu,
1293 : : },
1294 : : [(BPF_ALU | BPF_OR | BPF_X)] = {
1295 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1296 : : .off = { .min = 0, .max = 0},
1297 : : .imm = { .min = 0, .max = 0},
1298 : : .eval = eval_alu,
1299 : : },
1300 : : [(BPF_ALU | BPF_LSH | BPF_X)] = {
1301 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1302 : : .off = { .min = 0, .max = 0},
1303 : : .imm = { .min = 0, .max = 0},
1304 : : .eval = eval_alu,
1305 : : },
1306 : : [(BPF_ALU | BPF_RSH | BPF_X)] = {
1307 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1308 : : .off = { .min = 0, .max = 0},
1309 : : .imm = { .min = 0, .max = 0},
1310 : : .eval = eval_alu,
1311 : : },
1312 : : [(BPF_ALU | BPF_XOR | BPF_X)] = {
1313 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1314 : : .off = { .min = 0, .max = 0},
1315 : : .imm = { .min = 0, .max = 0},
1316 : : .eval = eval_alu,
1317 : : },
1318 : : [(BPF_ALU | BPF_MUL | BPF_X)] = {
1319 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1320 : : .off = { .min = 0, .max = 0},
1321 : : .imm = { .min = 0, .max = 0},
1322 : : .eval = eval_alu,
1323 : : },
1324 : : [(BPF_ALU | BPF_DIV | BPF_X)] = {
1325 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1326 : : .off = { .min = 0, .max = 0},
1327 : : .imm = { .min = 0, .max = 0},
1328 : : .eval = eval_alu,
1329 : : },
1330 : : [(BPF_ALU | BPF_MOD | BPF_X)] = {
1331 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1332 : : .off = { .min = 0, .max = 0},
1333 : : .imm = { .min = 0, .max = 0},
1334 : : .eval = eval_alu,
1335 : : },
1336 : : [(BPF_ALU | EBPF_MOV | BPF_X)] = {
1337 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1338 : : .off = { .min = 0, .max = 0},
1339 : : .imm = { .min = 0, .max = 0},
1340 : : .eval = eval_alu,
1341 : : },
1342 : : [(BPF_ALU | BPF_NEG)] = {
1343 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1344 : : .off = { .min = 0, .max = 0},
1345 : : .imm = { .min = 0, .max = 0},
1346 : : .eval = eval_alu,
1347 : : },
1348 : : [(BPF_ALU | EBPF_END | EBPF_TO_BE)] = {
1349 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1350 : : .off = { .min = 0, .max = 0},
1351 : : .imm = { .min = 16, .max = 64},
1352 : : .check = check_alu_bele,
1353 : : .eval = eval_bele,
1354 : : },
1355 : : [(BPF_ALU | EBPF_END | EBPF_TO_LE)] = {
1356 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1357 : : .off = { .min = 0, .max = 0},
1358 : : .imm = { .min = 16, .max = 64},
1359 : : .check = check_alu_bele,
1360 : : .eval = eval_bele,
1361 : : },
1362 : : /* ALU REG 64-bit instructions */
1363 : : [(EBPF_ALU64 | BPF_ADD | BPF_X)] = {
1364 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1365 : : .off = { .min = 0, .max = 0},
1366 : : .imm = { .min = 0, .max = 0},
1367 : : .eval = eval_alu,
1368 : : },
1369 : : [(EBPF_ALU64 | BPF_SUB | BPF_X)] = {
1370 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1371 : : .off = { .min = 0, .max = 0},
1372 : : .imm = { .min = 0, .max = 0},
1373 : : .eval = eval_alu,
1374 : : },
1375 : : [(EBPF_ALU64 | BPF_AND | BPF_X)] = {
1376 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1377 : : .off = { .min = 0, .max = 0},
1378 : : .imm = { .min = 0, .max = 0},
1379 : : .eval = eval_alu,
1380 : : },
1381 : : [(EBPF_ALU64 | BPF_OR | BPF_X)] = {
1382 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1383 : : .off = { .min = 0, .max = 0},
1384 : : .imm = { .min = 0, .max = 0},
1385 : : .eval = eval_alu,
1386 : : },
1387 : : [(EBPF_ALU64 | BPF_LSH | BPF_X)] = {
1388 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1389 : : .off = { .min = 0, .max = 0},
1390 : : .imm = { .min = 0, .max = 0},
1391 : : .eval = eval_alu,
1392 : : },
1393 : : [(EBPF_ALU64 | BPF_RSH | BPF_X)] = {
1394 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1395 : : .off = { .min = 0, .max = 0},
1396 : : .imm = { .min = 0, .max = 0},
1397 : : .eval = eval_alu,
1398 : : },
1399 : : [(EBPF_ALU64 | EBPF_ARSH | BPF_X)] = {
1400 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1401 : : .off = { .min = 0, .max = 0},
1402 : : .imm = { .min = 0, .max = 0},
1403 : : .eval = eval_alu,
1404 : : },
1405 : : [(EBPF_ALU64 | BPF_XOR | BPF_X)] = {
1406 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1407 : : .off = { .min = 0, .max = 0},
1408 : : .imm = { .min = 0, .max = 0},
1409 : : .eval = eval_alu,
1410 : : },
1411 : : [(EBPF_ALU64 | BPF_MUL | BPF_X)] = {
1412 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1413 : : .off = { .min = 0, .max = 0},
1414 : : .imm = { .min = 0, .max = 0},
1415 : : .eval = eval_alu,
1416 : : },
1417 : : [(EBPF_ALU64 | BPF_DIV | BPF_X)] = {
1418 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1419 : : .off = { .min = 0, .max = 0},
1420 : : .imm = { .min = 0, .max = 0},
1421 : : .eval = eval_alu,
1422 : : },
1423 : : [(EBPF_ALU64 | BPF_MOD | BPF_X)] = {
1424 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1425 : : .off = { .min = 0, .max = 0},
1426 : : .imm = { .min = 0, .max = 0},
1427 : : .eval = eval_alu,
1428 : : },
1429 : : [(EBPF_ALU64 | EBPF_MOV | BPF_X)] = {
1430 : : .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1431 : : .off = { .min = 0, .max = 0},
1432 : : .imm = { .min = 0, .max = 0},
1433 : : .eval = eval_alu,
1434 : : },
1435 : : [(EBPF_ALU64 | BPF_NEG)] = {
1436 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1437 : : .off = { .min = 0, .max = 0},
1438 : : .imm = { .min = 0, .max = 0},
1439 : : .eval = eval_alu,
1440 : : },
1441 : : /* load instructions */
1442 : : [(BPF_LDX | BPF_MEM | BPF_B)] = {
1443 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1444 : : .off = { .min = 0, .max = UINT16_MAX},
1445 : : .imm = { .min = 0, .max = 0},
1446 : : .eval = eval_load,
1447 : : },
1448 : : [(BPF_LDX | BPF_MEM | BPF_H)] = {
1449 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1450 : : .off = { .min = 0, .max = UINT16_MAX},
1451 : : .imm = { .min = 0, .max = 0},
1452 : : .eval = eval_load,
1453 : : },
1454 : : [(BPF_LDX | BPF_MEM | BPF_W)] = {
1455 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1456 : : .off = { .min = 0, .max = UINT16_MAX},
1457 : : .imm = { .min = 0, .max = 0},
1458 : : .eval = eval_load,
1459 : : },
1460 : : [(BPF_LDX | BPF_MEM | EBPF_DW)] = {
1461 : : .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1462 : : .off = { .min = 0, .max = UINT16_MAX},
1463 : : .imm = { .min = 0, .max = 0},
1464 : : .eval = eval_load,
1465 : : },
1466 : : /* load 64 bit immediate value */
1467 : : [(BPF_LD | BPF_IMM | EBPF_DW)] = {
1468 : : .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1469 : : .off = { .min = 0, .max = 0},
1470 : : .imm = { .min = 0, .max = UINT32_MAX},
1471 : : .eval = eval_ld_imm64,
1472 : : },
1473 : : /* load absolute instructions */
1474 : : [(BPF_LD | BPF_ABS | BPF_B)] = {
1475 : : .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
1476 : : .off = { .min = 0, .max = 0},
1477 : : .imm = { .min = 0, .max = INT32_MAX},
1478 : : .eval = eval_ld_mbuf,
1479 : : },
1480 : : [(BPF_LD | BPF_ABS | BPF_H)] = {
1481 : : .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
1482 : : .off = { .min = 0, .max = 0},
1483 : : .imm = { .min = 0, .max = INT32_MAX},
1484 : : .eval = eval_ld_mbuf,
1485 : : },
1486 : : [(BPF_LD | BPF_ABS | BPF_W)] = {
1487 : : .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
1488 : : .off = { .min = 0, .max = 0},
1489 : : .imm = { .min = 0, .max = INT32_MAX},
1490 : : .eval = eval_ld_mbuf,
1491 : : },
1492 : : /* load indirect instructions */
1493 : : [(BPF_LD | BPF_IND | BPF_B)] = {
1494 : : .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
1495 : : .off = { .min = 0, .max = 0},
1496 : : .imm = { .min = 0, .max = UINT32_MAX},
1497 : : .eval = eval_ld_mbuf,
1498 : : },
1499 : : [(BPF_LD | BPF_IND | BPF_H)] = {
1500 : : .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
1501 : : .off = { .min = 0, .max = 0},
1502 : : .imm = { .min = 0, .max = UINT32_MAX},
1503 : : .eval = eval_ld_mbuf,
1504 : : },
1505 : : [(BPF_LD | BPF_IND | BPF_W)] = {
1506 : : .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
1507 : : .off = { .min = 0, .max = 0},
1508 : : .imm = { .min = 0, .max = UINT32_MAX},
1509 : : .eval = eval_ld_mbuf,
1510 : : },
1511 : : /* store REG instructions */
1512 : : [(BPF_STX | BPF_MEM | BPF_B)] = {
1513 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1514 : : .off = { .min = 0, .max = UINT16_MAX},
1515 : : .imm = { .min = 0, .max = 0},
1516 : : .eval = eval_store,
1517 : : },
1518 : : [(BPF_STX | BPF_MEM | BPF_H)] = {
1519 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1520 : : .off = { .min = 0, .max = UINT16_MAX},
1521 : : .imm = { .min = 0, .max = 0},
1522 : : .eval = eval_store,
1523 : : },
1524 : : [(BPF_STX | BPF_MEM | BPF_W)] = {
1525 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1526 : : .off = { .min = 0, .max = UINT16_MAX},
1527 : : .imm = { .min = 0, .max = 0},
1528 : : .eval = eval_store,
1529 : : },
1530 : : [(BPF_STX | BPF_MEM | EBPF_DW)] = {
1531 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1532 : : .off = { .min = 0, .max = UINT16_MAX},
1533 : : .imm = { .min = 0, .max = 0},
1534 : : .eval = eval_store,
1535 : : },
1536 : : /* atomic add instructions */
1537 : : [(BPF_STX | EBPF_XADD | BPF_W)] = {
1538 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1539 : : .off = { .min = 0, .max = UINT16_MAX},
1540 : : .imm = { .min = 0, .max = 0},
1541 : : .eval = eval_store,
1542 : : },
1543 : : [(BPF_STX | EBPF_XADD | EBPF_DW)] = {
1544 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1545 : : .off = { .min = 0, .max = UINT16_MAX},
1546 : : .imm = { .min = 0, .max = 0},
1547 : : .eval = eval_store,
1548 : : },
1549 : : /* store IMM instructions */
1550 : : [(BPF_ST | BPF_MEM | BPF_B)] = {
1551 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1552 : : .off = { .min = 0, .max = UINT16_MAX},
1553 : : .imm = { .min = 0, .max = UINT32_MAX},
1554 : : .eval = eval_store,
1555 : : },
1556 : : [(BPF_ST | BPF_MEM | BPF_H)] = {
1557 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1558 : : .off = { .min = 0, .max = UINT16_MAX},
1559 : : .imm = { .min = 0, .max = UINT32_MAX},
1560 : : .eval = eval_store,
1561 : : },
1562 : : [(BPF_ST | BPF_MEM | BPF_W)] = {
1563 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1564 : : .off = { .min = 0, .max = UINT16_MAX},
1565 : : .imm = { .min = 0, .max = UINT32_MAX},
1566 : : .eval = eval_store,
1567 : : },
1568 : : [(BPF_ST | BPF_MEM | EBPF_DW)] = {
1569 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1570 : : .off = { .min = 0, .max = UINT16_MAX},
1571 : : .imm = { .min = 0, .max = UINT32_MAX},
1572 : : .eval = eval_store,
1573 : : },
1574 : : /* jump instruction */
1575 : : [(BPF_JMP | BPF_JA)] = {
1576 : : .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
1577 : : .off = { .min = 0, .max = UINT16_MAX},
1578 : : .imm = { .min = 0, .max = 0},
1579 : : },
1580 : : /* jcc IMM instructions */
1581 : : [(BPF_JMP | BPF_JEQ | BPF_K)] = {
1582 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1583 : : .off = { .min = 0, .max = UINT16_MAX},
1584 : : .imm = { .min = 0, .max = UINT32_MAX},
1585 : : .eval = eval_jcc,
1586 : : },
1587 : : [(BPF_JMP | EBPF_JNE | BPF_K)] = {
1588 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1589 : : .off = { .min = 0, .max = UINT16_MAX},
1590 : : .imm = { .min = 0, .max = UINT32_MAX},
1591 : : .eval = eval_jcc,
1592 : : },
1593 : : [(BPF_JMP | BPF_JGT | BPF_K)] = {
1594 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1595 : : .off = { .min = 0, .max = UINT16_MAX},
1596 : : .imm = { .min = 0, .max = UINT32_MAX},
1597 : : .eval = eval_jcc,
1598 : : },
1599 : : [(BPF_JMP | EBPF_JLT | BPF_K)] = {
1600 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1601 : : .off = { .min = 0, .max = UINT16_MAX},
1602 : : .imm = { .min = 0, .max = UINT32_MAX},
1603 : : .eval = eval_jcc,
1604 : : },
1605 : : [(BPF_JMP | BPF_JGE | BPF_K)] = {
1606 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1607 : : .off = { .min = 0, .max = UINT16_MAX},
1608 : : .imm = { .min = 0, .max = UINT32_MAX},
1609 : : .eval = eval_jcc,
1610 : : },
1611 : : [(BPF_JMP | EBPF_JLE | BPF_K)] = {
1612 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1613 : : .off = { .min = 0, .max = UINT16_MAX},
1614 : : .imm = { .min = 0, .max = UINT32_MAX},
1615 : : .eval = eval_jcc,
1616 : : },
1617 : : [(BPF_JMP | EBPF_JSGT | BPF_K)] = {
1618 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1619 : : .off = { .min = 0, .max = UINT16_MAX},
1620 : : .imm = { .min = 0, .max = UINT32_MAX},
1621 : : .eval = eval_jcc,
1622 : : },
1623 : : [(BPF_JMP | EBPF_JSLT | BPF_K)] = {
1624 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1625 : : .off = { .min = 0, .max = UINT16_MAX},
1626 : : .imm = { .min = 0, .max = UINT32_MAX},
1627 : : .eval = eval_jcc,
1628 : : },
1629 : : [(BPF_JMP | EBPF_JSGE | BPF_K)] = {
1630 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1631 : : .off = { .min = 0, .max = UINT16_MAX},
1632 : : .imm = { .min = 0, .max = UINT32_MAX},
1633 : : .eval = eval_jcc,
1634 : : },
1635 : : [(BPF_JMP | EBPF_JSLE | BPF_K)] = {
1636 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1637 : : .off = { .min = 0, .max = UINT16_MAX},
1638 : : .imm = { .min = 0, .max = UINT32_MAX},
1639 : : .eval = eval_jcc,
1640 : : },
1641 : : [(BPF_JMP | BPF_JSET | BPF_K)] = {
1642 : : .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1643 : : .off = { .min = 0, .max = UINT16_MAX},
1644 : : .imm = { .min = 0, .max = UINT32_MAX},
1645 : : .eval = eval_jcc,
1646 : : },
1647 : : /* jcc REG instructions */
1648 : : [(BPF_JMP | BPF_JEQ | BPF_X)] = {
1649 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1650 : : .off = { .min = 0, .max = UINT16_MAX},
1651 : : .imm = { .min = 0, .max = 0},
1652 : : .eval = eval_jcc,
1653 : : },
1654 : : [(BPF_JMP | EBPF_JNE | BPF_X)] = {
1655 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1656 : : .off = { .min = 0, .max = UINT16_MAX},
1657 : : .imm = { .min = 0, .max = 0},
1658 : : .eval = eval_jcc,
1659 : : },
1660 : : [(BPF_JMP | BPF_JGT | BPF_X)] = {
1661 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1662 : : .off = { .min = 0, .max = UINT16_MAX},
1663 : : .imm = { .min = 0, .max = 0},
1664 : : .eval = eval_jcc,
1665 : : },
1666 : : [(BPF_JMP | EBPF_JLT | BPF_X)] = {
1667 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1668 : : .off = { .min = 0, .max = UINT16_MAX},
1669 : : .imm = { .min = 0, .max = 0},
1670 : : .eval = eval_jcc,
1671 : : },
1672 : : [(BPF_JMP | BPF_JGE | BPF_X)] = {
1673 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1674 : : .off = { .min = 0, .max = UINT16_MAX},
1675 : : .imm = { .min = 0, .max = 0},
1676 : : .eval = eval_jcc,
1677 : : },
1678 : : [(BPF_JMP | EBPF_JLE | BPF_X)] = {
1679 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1680 : : .off = { .min = 0, .max = UINT16_MAX},
1681 : : .imm = { .min = 0, .max = 0},
1682 : : .eval = eval_jcc,
1683 : : },
1684 : : [(BPF_JMP | EBPF_JSGT | BPF_X)] = {
1685 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1686 : : .off = { .min = 0, .max = UINT16_MAX},
1687 : : .imm = { .min = 0, .max = 0},
1688 : : .eval = eval_jcc,
1689 : : },
1690 : : [(BPF_JMP | EBPF_JSLT | BPF_X)] = {
1691 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1692 : : .off = { .min = 0, .max = UINT16_MAX},
1693 : : .imm = { .min = 0, .max = 0},
1694 : : },
1695 : : [(BPF_JMP | EBPF_JSGE | BPF_X)] = {
1696 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1697 : : .off = { .min = 0, .max = UINT16_MAX},
1698 : : .imm = { .min = 0, .max = 0},
1699 : : .eval = eval_jcc,
1700 : : },
1701 : : [(BPF_JMP | EBPF_JSLE | BPF_X)] = {
1702 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1703 : : .off = { .min = 0, .max = UINT16_MAX},
1704 : : .imm = { .min = 0, .max = 0},
1705 : : .eval = eval_jcc,
1706 : : },
1707 : : [(BPF_JMP | BPF_JSET | BPF_X)] = {
1708 : : .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1709 : : .off = { .min = 0, .max = UINT16_MAX},
1710 : : .imm = { .min = 0, .max = 0},
1711 : : .eval = eval_jcc,
1712 : : },
1713 : : /* call instruction */
1714 : : [(BPF_JMP | EBPF_CALL)] = {
1715 : : .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
1716 : : .off = { .min = 0, .max = 0},
1717 : : .imm = { .min = 0, .max = UINT32_MAX},
1718 : : .eval = eval_call,
1719 : : },
1720 : : /* ret instruction */
1721 : : [(BPF_JMP | EBPF_EXIT)] = {
1722 : : .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
1723 : : .off = { .min = 0, .max = 0},
1724 : : .imm = { .min = 0, .max = 0},
1725 : : .eval = eval_exit,
1726 : : },
1727 : : };
1728 : :
1729 : : /*
1730 : : * make sure that instruction syntax is valid,
1731 : : * and its fields don't violate particular instruction type restrictions.
1732 : : */
1733 : : static const char *
1734 : 1001 : check_syntax(const struct ebpf_insn *ins)
1735 : : {
1736 : :
1737 : : uint8_t op;
1738 : : uint16_t off;
1739 : : uint32_t imm;
1740 : :
1741 : 1001 : op = ins->code;
1742 : :
1743 [ + - ]: 1001 : if (ins_chk[op].mask.dreg == 0)
1744 : : return "invalid opcode";
1745 : :
1746 [ + - ]: 1001 : if ((ins_chk[op].mask.dreg & 1 << ins->dst_reg) == 0)
1747 : : return "invalid dst-reg field";
1748 : :
1749 [ + - ]: 1001 : if ((ins_chk[op].mask.sreg & 1 << ins->src_reg) == 0)
1750 : : return "invalid src-reg field";
1751 : :
1752 : 1001 : off = ins->off;
1753 [ + - + - ]: 1001 : if (ins_chk[op].off.min > off || ins_chk[op].off.max < off)
1754 : : return "invalid off field";
1755 : :
1756 : 1001 : imm = ins->imm;
1757 [ + - + - ]: 1001 : if (ins_chk[op].imm.min > imm || ins_chk[op].imm.max < imm)
1758 : : return "invalid imm field";
1759 : :
1760 [ + + ]: 1001 : if (ins_chk[op].check != NULL)
1761 : 8 : return ins_chk[op].check(ins);
1762 : :
1763 : : return NULL;
1764 : : }
1765 : :
1766 : : /*
1767 : : * helper function, return instruction index for the given node.
1768 : : */
1769 : : static uint32_t
1770 : : get_node_idx(const struct bpf_verifier *bvf, const struct inst_node *node)
1771 : : {
1772 : 7945 : return node - bvf->in;
1773 : : }
1774 : :
1775 : : /*
1776 : : * helper function, used to walk through constructed CFG.
1777 : : */
1778 : : static struct inst_node *
1779 : : get_next_node(struct bpf_verifier *bvf, struct inst_node *node)
1780 : : {
1781 : : uint32_t ce, ne, dst;
1782 : :
1783 : 7893 : ne = node->nb_edge;
1784 : 7893 : ce = node->cur_edge;
1785 [ + + + + ]: 7893 : if (ce == ne)
1786 : : return NULL;
1787 : :
1788 : 4001 : node->cur_edge++;
1789 : 4001 : dst = node->edge_dest[ce];
1790 : 4001 : return bvf->in + dst;
1791 : : }
1792 : :
1793 : : static void
1794 : : set_node_colour(struct bpf_verifier *bvf, struct inst_node *node,
1795 : : uint32_t new)
1796 : : {
1797 : : uint32_t prev;
1798 : :
1799 : : prev = node->colour;
1800 : 2002 : node->colour = new;
1801 : :
1802 : 2002 : bvf->node_colour[prev]--;
1803 : 2002 : bvf->node_colour[new]++;
1804 : 1001 : }
1805 : :
1806 : : /*
1807 : : * helper function, add new edge between two nodes.
1808 : : */
1809 : : static int
1810 : 1110 : add_edge(struct bpf_verifier *bvf, struct inst_node *node, uint32_t nidx)
1811 : : {
1812 : : uint32_t ne;
1813 : :
1814 [ - + ]: 1110 : if (nidx > bvf->prm->nb_ins) {
1815 : 0 : RTE_BPF_LOG_LINE(ERR, "%s: program boundary violation at pc: %u, "
1816 : : "next pc: %u",
1817 : : __func__, get_node_idx(bvf, node), nidx);
1818 : 0 : return -EINVAL;
1819 : : }
1820 : :
1821 : 1110 : ne = node->nb_edge;
1822 [ - + ]: 1110 : if (ne >= RTE_DIM(node->edge_dest)) {
1823 : 0 : RTE_BPF_LOG_LINE(ERR, "%s: internal error at pc: %u",
1824 : : __func__, get_node_idx(bvf, node));
1825 : 0 : return -EINVAL;
1826 : : }
1827 : :
1828 : 1110 : node->edge_dest[ne] = nidx;
1829 : 1110 : node->nb_edge = ne + 1;
1830 : 1110 : return 0;
1831 : : }
1832 : :
1833 : : /*
1834 : : * helper function, determine type of edge between two nodes.
1835 : : */
1836 : : static void
1837 : : set_edge_type(struct bpf_verifier *bvf, struct inst_node *node,
1838 : : const struct inst_node *next)
1839 : : {
1840 : : uint32_t ce, clr, type;
1841 : :
1842 : 1110 : ce = node->cur_edge - 1;
1843 : 1110 : clr = next->colour;
1844 : :
1845 : : type = UNKNOWN_EDGE;
1846 : :
1847 [ + + ]: 1110 : if (clr == WHITE)
1848 : : type = TREE_EDGE;
1849 [ + - ]: 155 : else if (clr == GREY)
1850 : : type = BACK_EDGE;
1851 [ + - ]: 155 : else if (clr == BLACK)
1852 : : /*
1853 : : * in fact it could be either direct or cross edge,
1854 : : * but for now, we don't need to distinguish between them.
1855 : : */
1856 : : type = CROSS_EDGE;
1857 : :
1858 : 1110 : node->edge_type[ce] = type;
1859 : 1110 : bvf->edge_type[type]++;
1860 : : }
1861 : :
1862 : : static struct inst_node *
1863 : : get_prev_node(struct bpf_verifier *bvf, struct inst_node *node)
1864 : : {
1865 : 3892 : return bvf->in + node->prev_node;
1866 : : }
1867 : :
1868 : : /*
1869 : : * Depth-First Search (DFS) through previously constructed
1870 : : * Control Flow Graph (CFG).
1871 : : * Information collected at this path would be used later
1872 : : * to determine is there any loops, and/or unreachable instructions.
1873 : : */
1874 : : static void
1875 : 46 : dfs(struct bpf_verifier *bvf)
1876 : : {
1877 : : struct inst_node *next, *node;
1878 : :
1879 : 46 : node = bvf->in;
1880 [ + - ]: 2002 : while (node != NULL) {
1881 : :
1882 [ + + ]: 2002 : if (node->colour == WHITE)
1883 : : set_node_colour(bvf, node, GREY);
1884 : :
1885 [ + + ]: 2002 : if (node->colour == GREY) {
1886 : :
1887 : : /* find next unprocessed child node */
1888 : : do {
1889 : : next = get_next_node(bvf, node);
1890 [ + - ]: 1110 : if (next == NULL)
1891 : : break;
1892 : : set_edge_type(bvf, node, next);
1893 [ + + ]: 1110 : } while (next->colour != WHITE);
1894 : :
1895 [ + + ]: 1956 : if (next != NULL) {
1896 : : /* proceed with next child */
1897 : 955 : next->prev_node = get_node_idx(bvf, node);
1898 : : node = next;
1899 : : } else {
1900 : : /*
1901 : : * finished with current node and all it's kids,
1902 : : * proceed with parent
1903 : : */
1904 : : set_node_colour(bvf, node, BLACK);
1905 : 1001 : node->cur_edge = 0;
1906 : : node = get_prev_node(bvf, node);
1907 : : }
1908 : : } else
1909 : : node = NULL;
1910 : : }
1911 : 46 : }
1912 : :
1913 : : /*
1914 : : * report unreachable instructions.
1915 : : */
1916 : : static void
1917 : 0 : log_unreachable(const struct bpf_verifier *bvf)
1918 : : {
1919 : : uint32_t i;
1920 : : struct inst_node *node;
1921 : : const struct ebpf_insn *ins;
1922 : :
1923 [ # # ]: 0 : for (i = 0; i != bvf->prm->nb_ins; i++) {
1924 : :
1925 : 0 : node = bvf->in + i;
1926 : 0 : ins = bvf->prm->ins + i;
1927 : :
1928 [ # # ]: 0 : if (node->colour == WHITE &&
1929 [ # # ]: 0 : ins->code != (BPF_LD | BPF_IMM | EBPF_DW))
1930 : 0 : RTE_BPF_LOG_LINE(ERR, "unreachable code at pc: %u;", i);
1931 : : }
1932 : 0 : }
1933 : :
1934 : : /*
1935 : : * report loops detected.
1936 : : */
1937 : : static void
1938 : 0 : log_loop(const struct bpf_verifier *bvf)
1939 : : {
1940 : : uint32_t i, j;
1941 : : struct inst_node *node;
1942 : :
1943 [ # # ]: 0 : for (i = 0; i != bvf->prm->nb_ins; i++) {
1944 : :
1945 : 0 : node = bvf->in + i;
1946 [ # # ]: 0 : if (node->colour != BLACK)
1947 : 0 : continue;
1948 : :
1949 [ # # ]: 0 : for (j = 0; j != node->nb_edge; j++) {
1950 [ # # ]: 0 : if (node->edge_type[j] == BACK_EDGE)
1951 : 0 : RTE_BPF_LOG_LINE(ERR,
1952 : : "loop at pc:%u --> pc:%u;",
1953 : : i, node->edge_dest[j]);
1954 : : }
1955 : : }
1956 : 0 : }
1957 : :
1958 : : /*
1959 : : * First pass goes though all instructions in the set, checks that each
1960 : : * instruction is a valid one (correct syntax, valid field values, etc.)
1961 : : * and constructs control flow graph (CFG).
1962 : : * Then depth-first search is performed over the constructed graph.
1963 : : * Programs with unreachable instructions and/or loops will be rejected.
1964 : : */
1965 : : static int
1966 : 46 : validate(struct bpf_verifier *bvf)
1967 : : {
1968 : : int32_t rc;
1969 : : uint32_t i;
1970 : : struct inst_node *node;
1971 : : const struct ebpf_insn *ins;
1972 : : const char *err;
1973 : :
1974 : : rc = 0;
1975 [ + + ]: 1047 : for (i = 0; i < bvf->prm->nb_ins; i++) {
1976 : :
1977 : 1001 : ins = bvf->prm->ins + i;
1978 : 1001 : node = bvf->in + i;
1979 : :
1980 : 1001 : err = check_syntax(ins);
1981 [ - + ]: 1001 : if (err != 0) {
1982 : 0 : RTE_BPF_LOG_LINE(ERR, "%s: %s at pc: %u",
1983 : : __func__, err, i);
1984 : 0 : rc |= -EINVAL;
1985 : : }
1986 : :
1987 : : /*
1988 : : * construct CFG, jcc nodes have to outgoing edges,
1989 : : * 'exit' nodes - none, all other nodes have exactly one
1990 : : * outgoing edge.
1991 : : */
1992 [ + + + + : 1001 : switch (ins->code) {
+ + ]
1993 : : case (BPF_JMP | EBPF_EXIT):
1994 : : break;
1995 : 184 : case (BPF_JMP | BPF_JEQ | BPF_K):
1996 : : case (BPF_JMP | EBPF_JNE | BPF_K):
1997 : : case (BPF_JMP | BPF_JGT | BPF_K):
1998 : : case (BPF_JMP | EBPF_JLT | BPF_K):
1999 : : case (BPF_JMP | BPF_JGE | BPF_K):
2000 : : case (BPF_JMP | EBPF_JLE | BPF_K):
2001 : : case (BPF_JMP | EBPF_JSGT | BPF_K):
2002 : : case (BPF_JMP | EBPF_JSLT | BPF_K):
2003 : : case (BPF_JMP | EBPF_JSGE | BPF_K):
2004 : : case (BPF_JMP | EBPF_JSLE | BPF_K):
2005 : : case (BPF_JMP | BPF_JSET | BPF_K):
2006 : : case (BPF_JMP | BPF_JEQ | BPF_X):
2007 : : case (BPF_JMP | EBPF_JNE | BPF_X):
2008 : : case (BPF_JMP | BPF_JGT | BPF_X):
2009 : : case (BPF_JMP | EBPF_JLT | BPF_X):
2010 : : case (BPF_JMP | BPF_JGE | BPF_X):
2011 : : case (BPF_JMP | EBPF_JLE | BPF_X):
2012 : : case (BPF_JMP | EBPF_JSGT | BPF_X):
2013 : : case (BPF_JMP | EBPF_JSLT | BPF_X):
2014 : : case (BPF_JMP | EBPF_JSGE | BPF_X):
2015 : : case (BPF_JMP | EBPF_JSLE | BPF_X):
2016 : : case (BPF_JMP | BPF_JSET | BPF_X):
2017 : 184 : rc |= add_edge(bvf, node, i + ins->off + 1);
2018 : 184 : rc |= add_edge(bvf, node, i + 1);
2019 : 184 : bvf->nb_jcc_nodes++;
2020 : 184 : break;
2021 : 26 : case (BPF_JMP | BPF_JA):
2022 : 26 : rc |= add_edge(bvf, node, i + ins->off + 1);
2023 : 26 : break;
2024 : : /* load 64 bit immediate value */
2025 : 5 : case (BPF_LD | BPF_IMM | EBPF_DW):
2026 : 5 : rc |= add_edge(bvf, node, i + 2);
2027 : 5 : i++;
2028 : 5 : break;
2029 : 159 : case (BPF_LD | BPF_ABS | BPF_B):
2030 : : case (BPF_LD | BPF_ABS | BPF_H):
2031 : : case (BPF_LD | BPF_ABS | BPF_W):
2032 : : case (BPF_LD | BPF_IND | BPF_B):
2033 : : case (BPF_LD | BPF_IND | BPF_H):
2034 : : case (BPF_LD | BPF_IND | BPF_W):
2035 : 159 : bvf->nb_ldmb_nodes++;
2036 : : /* fallthrough */
2037 : 711 : default:
2038 : 711 : rc |= add_edge(bvf, node, i + 1);
2039 : 711 : break;
2040 : : }
2041 : :
2042 : 1001 : bvf->nb_nodes++;
2043 : 1001 : bvf->node_colour[WHITE]++;
2044 : : }
2045 : :
2046 [ + - ]: 46 : if (rc != 0)
2047 : : return rc;
2048 : :
2049 : 46 : dfs(bvf);
2050 : :
2051 : 46 : RTE_LOG(DEBUG, BPF, "%s(%p) stats:\n"
2052 : : "nb_nodes=%u;\n"
2053 : : "nb_jcc_nodes=%u;\n"
2054 : : "node_color={[WHITE]=%u, [GREY]=%u,, [BLACK]=%u};\n"
2055 : : "edge_type={[UNKNOWN]=%u, [TREE]=%u, [BACK]=%u, [CROSS]=%u};\n",
2056 : : __func__, bvf,
2057 : : bvf->nb_nodes,
2058 : : bvf->nb_jcc_nodes,
2059 : : bvf->node_colour[WHITE], bvf->node_colour[GREY],
2060 : : bvf->node_colour[BLACK],
2061 : : bvf->edge_type[UNKNOWN_EDGE], bvf->edge_type[TREE_EDGE],
2062 : : bvf->edge_type[BACK_EDGE], bvf->edge_type[CROSS_EDGE]);
2063 : :
2064 [ - + ]: 46 : if (bvf->node_colour[BLACK] != bvf->nb_nodes) {
2065 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) unreachable instructions;",
2066 : : __func__, bvf);
2067 : 0 : log_unreachable(bvf);
2068 : 0 : return -EINVAL;
2069 : : }
2070 : :
2071 [ + - + - ]: 46 : if (bvf->node_colour[GREY] != 0 || bvf->node_colour[WHITE] != 0 ||
2072 [ - + ]: 46 : bvf->edge_type[UNKNOWN_EDGE] != 0) {
2073 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) DFS internal error;",
2074 : : __func__, bvf);
2075 : 0 : return -EINVAL;
2076 : : }
2077 : :
2078 [ - + ]: 46 : if (bvf->edge_type[BACK_EDGE] != 0) {
2079 : 0 : RTE_BPF_LOG_LINE(ERR, "%s(%p) loops detected;",
2080 : : __func__, bvf);
2081 : 0 : log_loop(bvf);
2082 : 0 : return -EINVAL;
2083 : : }
2084 : :
2085 : : return 0;
2086 : : }
2087 : :
2088 : : /*
2089 : : * helper functions get/free eval states.
2090 : : */
2091 : : static struct bpf_eval_state *
2092 : : pull_eval_state(struct bpf_verifier *bvf)
2093 : : {
2094 : : uint32_t n;
2095 : :
2096 : 581 : n = bvf->evst_pool.cur;
2097 : 627 : if (n == bvf->evst_pool.num)
2098 : : return NULL;
2099 : :
2100 : 627 : bvf->evst_pool.cur = n + 1;
2101 : 46 : return bvf->evst_pool.ent + n;
2102 : : }
2103 : :
2104 : : static void
2105 : : push_eval_state(struct bpf_verifier *bvf)
2106 : : {
2107 : 581 : bvf->evst_pool.cur--;
2108 : : }
2109 : :
2110 : : static void
2111 : 46 : evst_pool_fini(struct bpf_verifier *bvf)
2112 : : {
2113 : 46 : bvf->evst = NULL;
2114 : 46 : free(bvf->evst_pool.ent);
2115 : 46 : memset(&bvf->evst_pool, 0, sizeof(bvf->evst_pool));
2116 : 46 : }
2117 : :
2118 : : static int
2119 : 46 : evst_pool_init(struct bpf_verifier *bvf)
2120 : : {
2121 : : uint32_t n;
2122 : :
2123 : 46 : n = bvf->nb_jcc_nodes + 1;
2124 : :
2125 : 46 : bvf->evst_pool.ent = calloc(n, sizeof(bvf->evst_pool.ent[0]));
2126 [ + - ]: 46 : if (bvf->evst_pool.ent == NULL)
2127 : : return -ENOMEM;
2128 : :
2129 : 46 : bvf->evst_pool.num = n;
2130 [ + - ]: 46 : bvf->evst_pool.cur = 0;
2131 : :
2132 : 46 : bvf->evst = pull_eval_state(bvf);
2133 : 46 : return 0;
2134 : : }
2135 : :
2136 : : /*
2137 : : * Save current eval state.
2138 : : */
2139 : : static int
2140 [ + - ]: 581 : save_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2141 : : {
2142 : : struct bpf_eval_state *st;
2143 : :
2144 : : /* get new eval_state for this node */
2145 : : st = pull_eval_state(bvf);
2146 [ - + ]: 581 : if (st == NULL) {
2147 : 0 : RTE_BPF_LOG_LINE(ERR,
2148 : : "%s: internal error (out of space) at pc: %u",
2149 : : __func__, get_node_idx(bvf, node));
2150 : 0 : return -ENOMEM;
2151 : : }
2152 : :
2153 : : /* make a copy of current state */
2154 : 581 : memcpy(st, bvf->evst, sizeof(*st));
2155 : :
2156 : : /* swap current state with new one */
2157 : 581 : node->evst = bvf->evst;
2158 : 581 : bvf->evst = st;
2159 : :
2160 : 581 : RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;",
2161 : : __func__, bvf, get_node_idx(bvf, node), node->evst, bvf->evst);
2162 : :
2163 : 581 : return 0;
2164 : : }
2165 : :
2166 : : /*
2167 : : * Restore previous eval state and mark current eval state as free.
2168 : : */
2169 : : static void
2170 : 581 : restore_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2171 : : {
2172 : 581 : RTE_BPF_LOG_LINE(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;",
2173 : : __func__, bvf, get_node_idx(bvf, node), bvf->evst, node->evst);
2174 : :
2175 : 581 : bvf->evst = node->evst;
2176 : 581 : node->evst = NULL;
2177 : : push_eval_state(bvf);
2178 : 581 : }
2179 : :
2180 : : static void
2181 : 2937 : log_dbg_eval_state(const struct bpf_verifier *bvf, const struct ebpf_insn *ins,
2182 : : uint32_t pc)
2183 : : {
2184 : : const struct bpf_eval_state *st;
2185 : : const struct bpf_reg_val *rv;
2186 : :
2187 : 2937 : RTE_BPF_LOG_LINE(DEBUG, "%s(pc=%u):", __func__, pc);
2188 : :
2189 : 2937 : st = bvf->evst;
2190 : 2937 : rv = st->rv + ins->dst_reg;
2191 : :
2192 : 2937 : RTE_LOG(DEBUG, BPF,
2193 : : "r%u={\n"
2194 : : "\tv={type=%u, size=%zu},\n"
2195 : : "\tmask=0x%" PRIx64 ",\n"
2196 : : "\tu={min=0x%" PRIx64 ", max=0x%" PRIx64 "},\n"
2197 : : "\ts={min=%" PRId64 ", max=%" PRId64 "},\n"
2198 : : "};\n",
2199 : : ins->dst_reg,
2200 : : rv->v.type, rv->v.size,
2201 : : rv->mask,
2202 : : rv->u.min, rv->u.max,
2203 : : rv->s.min, rv->s.max);
2204 : 2937 : }
2205 : :
2206 : : /*
2207 : : * Do second pass through CFG and try to evaluate instructions
2208 : : * via each possible path.
2209 : : * Right now evaluation functionality is quite limited.
2210 : : * Still need to add extra checks for:
2211 : : * - use/return uninitialized registers.
2212 : : * - use uninitialized data from the stack.
2213 : : * - memory boundaries violation.
2214 : : */
2215 : : static int
2216 : 46 : evaluate(struct bpf_verifier *bvf)
2217 : : {
2218 : : int32_t rc;
2219 : : uint32_t idx, op;
2220 : : const char *err;
2221 : : const struct ebpf_insn *ins;
2222 : : struct inst_node *next, *node;
2223 : :
2224 : : /* initial state of frame pointer */
2225 : : static const struct bpf_reg_val rvfp = {
2226 : : .v = {
2227 : : .type = BPF_ARG_PTR_STACK,
2228 : : .size = MAX_BPF_STACK_SIZE,
2229 : : },
2230 : : .mask = UINT64_MAX,
2231 : : .u = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
2232 : : .s = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
2233 : : };
2234 : :
2235 : 46 : bvf->evst->rv[EBPF_REG_1].v = bvf->prm->prog_arg;
2236 : 46 : bvf->evst->rv[EBPF_REG_1].mask = UINT64_MAX;
2237 [ - + ]: 46 : if (bvf->prm->prog_arg.type == RTE_BPF_ARG_RAW)
2238 : : eval_max_bound(bvf->evst->rv + EBPF_REG_1, UINT64_MAX);
2239 : :
2240 : 46 : bvf->evst->rv[EBPF_REG_10] = rvfp;
2241 : :
2242 : 46 : ins = bvf->prm->ins;
2243 : 46 : node = bvf->in;
2244 : : next = node;
2245 : : rc = 0;
2246 : :
2247 [ + + ]: 5828 : while (node != NULL && rc == 0) {
2248 : :
2249 : : /*
2250 : : * current node evaluation, make sure we evaluate
2251 : : * each node only once.
2252 : : */
2253 [ + + ]: 5782 : if (next != NULL) {
2254 : :
2255 : 2937 : bvf->evin = node;
2256 : : idx = get_node_idx(bvf, node);
2257 : 2937 : op = ins[idx].code;
2258 : :
2259 : : /* for jcc node make a copy of evaluation state */
2260 [ + + ]: 2937 : if (node->nb_edge > 1)
2261 : 581 : rc |= save_eval_state(bvf, node);
2262 : :
2263 [ + + + - ]: 2937 : if (ins_chk[op].eval != NULL && rc == 0) {
2264 : 2649 : err = ins_chk[op].eval(bvf, ins + idx);
2265 [ - + ]: 2649 : if (err != NULL) {
2266 : 0 : RTE_BPF_LOG_LINE(ERR, "%s: %s at pc: %u",
2267 : : __func__, err, idx);
2268 : : rc = -EINVAL;
2269 : : }
2270 : : }
2271 : :
2272 : 2937 : log_dbg_eval_state(bvf, ins + idx, idx);
2273 : 2937 : bvf->evin = NULL;
2274 : : }
2275 : :
2276 : : /* proceed through CFG */
2277 : : next = get_next_node(bvf, node);
2278 [ + - ]: 2891 : if (next != NULL) {
2279 : :
2280 : : /* proceed with next child */
2281 [ + + ]: 2891 : if (node->cur_edge == node->nb_edge &&
2282 [ + + ]: 2310 : node->evst != NULL)
2283 : 581 : restore_eval_state(bvf, node);
2284 : :
2285 : 2891 : next->prev_node = get_node_idx(bvf, node);
2286 : : node = next;
2287 : : } else {
2288 : : /*
2289 : : * finished with current node and all it's kids,
2290 : : * proceed with parent
2291 : : */
2292 : 2891 : node->cur_edge = 0;
2293 : : node = get_prev_node(bvf, node);
2294 : :
2295 : : /* finished */
2296 [ + + ]: 2891 : if (node == bvf->in)
2297 : : node = NULL;
2298 : : }
2299 : : }
2300 : :
2301 : 46 : return rc;
2302 : : }
2303 : :
2304 : : int
2305 : 46 : __rte_bpf_validate(struct rte_bpf *bpf)
2306 : : {
2307 : : int32_t rc;
2308 : : struct bpf_verifier bvf;
2309 : :
2310 : : /* check input argument type, don't allow mbuf ptr on 32-bit */
2311 [ + + ]: 46 : if (bpf->prm.prog_arg.type != RTE_BPF_ARG_RAW &&
2312 [ - + ]: 29 : bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR &&
2313 : : (sizeof(uint64_t) != sizeof(uintptr_t) ||
2314 : : bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR_MBUF)) {
2315 : 0 : RTE_BPF_LOG_LINE(ERR, "%s: unsupported argument type", __func__);
2316 : 0 : return -ENOTSUP;
2317 : : }
2318 : :
2319 : : memset(&bvf, 0, sizeof(bvf));
2320 : 46 : bvf.prm = &bpf->prm;
2321 : 46 : bvf.in = calloc(bpf->prm.nb_ins, sizeof(bvf.in[0]));
2322 [ + - ]: 46 : if (bvf.in == NULL)
2323 : : return -ENOMEM;
2324 : :
2325 : 46 : rc = validate(&bvf);
2326 : :
2327 [ + - ]: 46 : if (rc == 0) {
2328 : 46 : rc = evst_pool_init(&bvf);
2329 [ + - ]: 46 : if (rc == 0)
2330 : 46 : rc = evaluate(&bvf);
2331 : 46 : evst_pool_fini(&bvf);
2332 : : }
2333 : :
2334 : 46 : free(bvf.in);
2335 : :
2336 : : /* copy collected info */
2337 [ + - ]: 46 : if (rc == 0) {
2338 : 46 : bpf->stack_sz = bvf.stack_sz;
2339 : :
2340 : : /* for LD_ABS/LD_IND, we'll need extra space on the stack */
2341 [ + + ]: 46 : if (bvf.nb_ldmb_nodes != 0)
2342 : 28 : bpf->stack_sz = RTE_ALIGN_CEIL(bpf->stack_sz +
2343 : : sizeof(uint64_t), sizeof(uint64_t));
2344 : : }
2345 : :
2346 : : return rc;
2347 : : }
|