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