root/drivers/net/ethernet/netronome/nfp/bpf/verifier.c

DEFINITIONS

1. nfp_bpf_goto_meta
2. nfp_record_adjust_head
3. nfp_bpf_map_update_value_ok
4. nfp_bpf_stack_arg_ok
5. nfp_bpf_map_call_ok
6. nfp_bpf_check_helper_call
7. nfp_bpf_check_exit
8. nfp_bpf_check_stack_access
9. nfp_bpf_map_use_name
10. nfp_bpf_map_mark_used_one
11. nfp_bpf_map_mark_used
12. nfp_bpf_check_ptr
13. nfp_bpf_check_store
14. nfp_bpf_check_xadd
15. nfp_bpf_check_alu
16. nfp_verify_insn
17. nfp_assign_subprog_idx_and_regs
18. nfp_bpf_get_stack_usage
19. nfp_bpf_insn_flag_zext
20. nfp_bpf_finalize
21. nfp_bpf_opt_replace_insn
22. nfp_bpf_opt_remove_insns

   1 // SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause)
   2 /* Copyright (C) 2016-2018 Netronome Systems, Inc. */
   3 
   4 #include <linux/bpf.h>
   5 #include <linux/bpf_verifier.h>
   6 #include <linux/kernel.h>
   7 #include <linux/netdevice.h>
   8 #include <linux/pkt_cls.h>
   9 
  10 #include "../nfp_app.h"
  11 #include "../nfp_main.h"
  12 #include "../nfp_net.h"
  13 #include "fw.h"
  14 #include "main.h"
  15 
  16 #define pr_vlog(env, fmt, ...)  \
  17         bpf_verifier_log_write(env, "[nfp] " fmt, ##__VA_ARGS__)
  18 
  19 struct nfp_insn_meta *
  20 nfp_bpf_goto_meta(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
  21                   unsigned int insn_idx)
  22 {
  23         unsigned int forward, backward, i;
  24 
  25         backward = meta->n - insn_idx;
  26         forward = insn_idx - meta->n;
  27 
  28         if (min(forward, backward) > nfp_prog->n_insns - insn_idx - 1) {
  29                 backward = nfp_prog->n_insns - insn_idx - 1;
  30                 meta = nfp_prog_last_meta(nfp_prog);
  31         }
  32         if (min(forward, backward) > insn_idx && backward > insn_idx) {
  33                 forward = insn_idx;
  34                 meta = nfp_prog_first_meta(nfp_prog);
  35         }
  36 
  37         if (forward < backward)
  38                 for (i = 0; i < forward; i++)
  39                         meta = nfp_meta_next(meta);
  40         else
  41                 for (i = 0; i < backward; i++)
  42                         meta = nfp_meta_prev(meta);
  43 
  44         return meta;
  45 }
  46 
  47 static void
  48 nfp_record_adjust_head(struct nfp_app_bpf *bpf, struct nfp_prog *nfp_prog,
  49                        struct nfp_insn_meta *meta,
  50                        const struct bpf_reg_state *reg2)
  51 {
  52         unsigned int location = UINT_MAX;
  53         int imm;
  54 
  55         /* Datapath usually can give us guarantees on how much adjust head
  56          * can be done without the need for any checks.  Optimize the simple
  57          * case where there is only one adjust head by a constant.
  58          */
  59         if (reg2->type != SCALAR_VALUE || !tnum_is_const(reg2->var_off))
  60                 goto exit_set_location;
  61         imm = reg2->var_off.value;
  62         /* Translator will skip all checks, we need to guarantee min pkt len */
  63         if (imm > ETH_ZLEN - ETH_HLEN)
  64                 goto exit_set_location;
  65         if (imm > (int)bpf->adjust_head.guaranteed_add ||
  66             imm < -bpf->adjust_head.guaranteed_sub)
  67                 goto exit_set_location;
  68 
  69         if (nfp_prog->adjust_head_location) {
  70                 /* Only one call per program allowed */
  71                 if (nfp_prog->adjust_head_location != meta->n)
  72                         goto exit_set_location;
  73 
  74                 if (meta->arg2.reg.var_off.value != imm)
  75                         goto exit_set_location;
  76         }
  77 
  78         location = meta->n;
  79 exit_set_location:
  80         nfp_prog->adjust_head_location = location;
  81 }
  82 
  83 static bool nfp_bpf_map_update_value_ok(struct bpf_verifier_env *env)
  84 {
  85         const struct bpf_reg_state *reg1 = cur_regs(env) + BPF_REG_1;
  86         const struct bpf_reg_state *reg3 = cur_regs(env) + BPF_REG_3;
  87         struct bpf_offloaded_map *offmap;
  88         struct bpf_func_state *state;
  89         struct nfp_bpf_map *nfp_map;
  90         int off, i;
  91 
  92         state = env->cur_state->frame[reg3->frameno];
  93 
  94         /* We need to record each time update happens with non-zero words,
  95          * in case such word is used in atomic operations.
  96          * Implicitly depend on nfp_bpf_stack_arg_ok(reg3) being run before.
  97          */
  98 
  99         offmap = map_to_offmap(reg1->map_ptr);
 100         nfp_map = offmap->dev_priv;
 101         off = reg3->off + reg3->var_off.value;
 102 
 103         for (i = 0; i < offmap->map.value_size; i++) {
 104                 struct bpf_stack_state *stack_entry;
 105                 unsigned int soff;
 106 
 107                 soff = -(off + i) - 1;
 108                 stack_entry = &state->stack[soff / BPF_REG_SIZE];
 109                 if (stack_entry->slot_type[soff % BPF_REG_SIZE] == STACK_ZERO)
 110                         continue;
 111 
 112                 if (nfp_map->use_map[i / 4].type == NFP_MAP_USE_ATOMIC_CNT) {
 113                         pr_vlog(env, "value at offset %d/%d may be non-zero, bpf_map_update_elem() is required to initialize atomic counters to zero to avoid offload endian issues\n",
 114                                 i, soff);
 115                         return false;
 116                 }
 117                 nfp_map->use_map[i / 4].non_zero_update = 1;
 118         }
 119 
 120         return true;
 121 }
 122 
 123 static int
 124 nfp_bpf_stack_arg_ok(const char *fname, struct bpf_verifier_env *env,
 125                      const struct bpf_reg_state *reg,
 126                      struct nfp_bpf_reg_state *old_arg)
 127 {
 128         s64 off, old_off;
 129 
 130         if (reg->type != PTR_TO_STACK) {
 131                 pr_vlog(env, "%s: unsupported ptr type %d\n",
 132                         fname, reg->type);
 133                 return false;
 134         }
 135         if (!tnum_is_const(reg->var_off)) {
 136                 pr_vlog(env, "%s: variable pointer\n", fname);
 137                 return false;
 138         }
 139 
 140         off = reg->var_off.value + reg->off;
 141         if (-off % 4) {
 142                 pr_vlog(env, "%s: unaligned stack pointer %lld\n", fname, -off);
 143                 return false;
 144         }
 145 
 146         /* Rest of the checks is only if we re-parse the same insn */
 147         if (!old_arg)
 148                 return true;
 149 
 150         old_off = old_arg->reg.var_off.value + old_arg->reg.off;
 151         old_arg->var_off |= off != old_off;
 152 
 153         return true;
 154 }
 155 
 156 static bool
 157 nfp_bpf_map_call_ok(const char *fname, struct bpf_verifier_env *env,
 158                     struct nfp_insn_meta *meta,
 159                     u32 helper_tgt, const struct bpf_reg_state *reg1)
 160 {
 161         if (!helper_tgt) {
 162                 pr_vlog(env, "%s: not supported by FW\n", fname);
 163                 return false;
 164         }
 165 
 166         return true;
 167 }
 168 
 169 static int
 170 nfp_bpf_check_helper_call(struct nfp_prog *nfp_prog,
 171                           struct bpf_verifier_env *env,
 172                           struct nfp_insn_meta *meta)
 173 {
 174         const struct bpf_reg_state *reg1 = cur_regs(env) + BPF_REG_1;
 175         const struct bpf_reg_state *reg2 = cur_regs(env) + BPF_REG_2;
 176         const struct bpf_reg_state *reg3 = cur_regs(env) + BPF_REG_3;
 177         struct nfp_app_bpf *bpf = nfp_prog->bpf;
 178         u32 func_id = meta->insn.imm;
 179 
 180         switch (func_id) {
 181         case BPF_FUNC_xdp_adjust_head:
 182                 if (!bpf->adjust_head.off_max) {
 183                         pr_vlog(env, "adjust_head not supported by FW\n");
 184                         return -EOPNOTSUPP;
 185                 }
 186                 if (!(bpf->adjust_head.flags & NFP_BPF_ADJUST_HEAD_NO_META)) {
 187                         pr_vlog(env, "adjust_head: FW requires shifting metadata, not supported by the driver\n");
 188                         return -EOPNOTSUPP;
 189                 }
 190 
 191                 nfp_record_adjust_head(bpf, nfp_prog, meta, reg2);
 192                 break;
 193 
 194         case BPF_FUNC_xdp_adjust_tail:
 195                 if (!bpf->adjust_tail) {
 196                         pr_vlog(env, "adjust_tail not supported by FW\n");
 197                         return -EOPNOTSUPP;
 198                 }
 199                 break;
 200 
 201         case BPF_FUNC_map_lookup_elem:
 202                 if (!nfp_bpf_map_call_ok("map_lookup", env, meta,
 203                                          bpf->helpers.map_lookup, reg1) ||
 204                     !nfp_bpf_stack_arg_ok("map_lookup", env, reg2,
 205                                           meta->func_id ? &meta->arg2 : NULL))
 206                         return -EOPNOTSUPP;
 207                 break;
 208 
 209         case BPF_FUNC_map_update_elem:
 210                 if (!nfp_bpf_map_call_ok("map_update", env, meta,
 211                                          bpf->helpers.map_update, reg1) ||
 212                     !nfp_bpf_stack_arg_ok("map_update", env, reg2,
 213                                           meta->func_id ? &meta->arg2 : NULL) ||
 214                     !nfp_bpf_stack_arg_ok("map_update", env, reg3, NULL) ||
 215                     !nfp_bpf_map_update_value_ok(env))
 216                         return -EOPNOTSUPP;
 217                 break;
 218 
 219         case BPF_FUNC_map_delete_elem:
 220                 if (!nfp_bpf_map_call_ok("map_delete", env, meta,
 221                                          bpf->helpers.map_delete, reg1) ||
 222                     !nfp_bpf_stack_arg_ok("map_delete", env, reg2,
 223                                           meta->func_id ? &meta->arg2 : NULL))
 224                         return -EOPNOTSUPP;
 225                 break;
 226 
 227         case BPF_FUNC_get_prandom_u32:
 228                 if (bpf->pseudo_random)
 229                         break;
 230                 pr_vlog(env, "bpf_get_prandom_u32(): FW doesn't support random number generation\n");
 231                 return -EOPNOTSUPP;
 232 
 233         case BPF_FUNC_perf_event_output:
 234                 BUILD_BUG_ON(NFP_BPF_SCALAR_VALUE != SCALAR_VALUE ||
 235                              NFP_BPF_MAP_VALUE != PTR_TO_MAP_VALUE ||
 236                              NFP_BPF_STACK != PTR_TO_STACK ||
 237                              NFP_BPF_PACKET_DATA != PTR_TO_PACKET);
 238 
 239                 if (!bpf->helpers.perf_event_output) {
 240                         pr_vlog(env, "event_output: not supported by FW\n");
 241                         return -EOPNOTSUPP;
 242                 }
 243 
 244                 /* Force current CPU to make sure we can report the event
 245                  * wherever we get the control message from FW.
 246                  */
 247                 if (reg3->var_off.mask & BPF_F_INDEX_MASK ||
 248                     (reg3->var_off.value & BPF_F_INDEX_MASK) !=
 249                     BPF_F_CURRENT_CPU) {
 250                         char tn_buf[48];
 251 
 252                         tnum_strn(tn_buf, sizeof(tn_buf), reg3->var_off);
 253                         pr_vlog(env, "event_output: must use BPF_F_CURRENT_CPU, var_off: %s\n",
 254                                 tn_buf);
 255                         return -EOPNOTSUPP;
 256                 }
 257 
 258                 /* Save space in meta, we don't care about arguments other
 259                  * than 4th meta, shove it into arg1.
 260                  */
 261                 reg1 = cur_regs(env) + BPF_REG_4;
 262 
 263                 if (reg1->type != SCALAR_VALUE /* NULL ptr */ &&
 264                     reg1->type != PTR_TO_STACK &&
 265                     reg1->type != PTR_TO_MAP_VALUE &&
 266                     reg1->type != PTR_TO_PACKET) {
 267                         pr_vlog(env, "event_output: unsupported ptr type: %d\n",
 268                                 reg1->type);
 269                         return -EOPNOTSUPP;
 270                 }
 271 
 272                 if (reg1->type == PTR_TO_STACK &&
 273                     !nfp_bpf_stack_arg_ok("event_output", env, reg1, NULL))
 274                         return -EOPNOTSUPP;
 275 
 276                 /* Warn user that on offload NFP may return success even if map
 277                  * is not going to accept the event, since the event output is
 278                  * fully async and device won't know the state of the map.
 279                  * There is also FW limitation on the event length.
 280                  *
 281                  * Lost events will not show up on the perf ring, driver
 282                  * won't see them at all.  Events may also get reordered.
 283                  */
 284                 dev_warn_once(&nfp_prog->bpf->app->pf->pdev->dev,
 285                               "bpf: note: return codes and behavior of bpf_event_output() helper differs for offloaded programs!\n");
 286                 pr_vlog(env, "warning: return codes and behavior of event_output helper differ for offload!\n");
 287 
 288                 if (!meta->func_id)
 289                         break;
 290 
 291                 if (reg1->type != meta->arg1.type) {
 292                         pr_vlog(env, "event_output: ptr type changed: %d %d\n",
 293                                 meta->arg1.type, reg1->type);
 294                         return -EINVAL;
 295                 }
 296                 break;
 297 
 298         default:
 299                 pr_vlog(env, "unsupported function id: %d\n", func_id);
 300                 return -EOPNOTSUPP;
 301         }
 302 
 303         meta->func_id = func_id;
 304         meta->arg1 = *reg1;
 305         meta->arg2.reg = *reg2;
 306 
 307         return 0;
 308 }
 309 
 310 static int
 311 nfp_bpf_check_exit(struct nfp_prog *nfp_prog,
 312                    struct bpf_verifier_env *env)
 313 {
 314         const struct bpf_reg_state *reg0 = cur_regs(env) + BPF_REG_0;
 315         u64 imm;
 316 
 317         if (nfp_prog->type == BPF_PROG_TYPE_XDP)
 318                 return 0;
 319 
 320         if (!(reg0->type == SCALAR_VALUE && tnum_is_const(reg0->var_off))) {
 321                 char tn_buf[48];
 322 
 323                 tnum_strn(tn_buf, sizeof(tn_buf), reg0->var_off);
 324                 pr_vlog(env, "unsupported exit state: %d, var_off: %s\n",
 325                         reg0->type, tn_buf);
 326                 return -EINVAL;
 327         }
 328 
 329         imm = reg0->var_off.value;
 330         if (nfp_prog->type == BPF_PROG_TYPE_SCHED_CLS &&
 331             imm <= TC_ACT_REDIRECT &&
 332             imm != TC_ACT_SHOT && imm != TC_ACT_STOLEN &&
 333             imm != TC_ACT_QUEUED) {
 334                 pr_vlog(env, "unsupported exit state: %d, imm: %llx\n",
 335                         reg0->type, imm);
 336                 return -EINVAL;
 337         }
 338 
 339         return 0;
 340 }
 341 
 342 static int
 343 nfp_bpf_check_stack_access(struct nfp_prog *nfp_prog,
 344                            struct nfp_insn_meta *meta,
 345                            const struct bpf_reg_state *reg,
 346                            struct bpf_verifier_env *env)
 347 {
 348         s32 old_off, new_off;
 349 
 350         if (reg->frameno != env->cur_state->curframe)
 351                 meta->flags |= FLAG_INSN_PTR_CALLER_STACK_FRAME;
 352 
 353         if (!tnum_is_const(reg->var_off)) {
 354                 pr_vlog(env, "variable ptr stack access\n");
 355                 return -EINVAL;
 356         }
 357 
 358         if (meta->ptr.type == NOT_INIT)
 359                 return 0;
 360 
 361         old_off = meta->ptr.off + meta->ptr.var_off.value;
 362         new_off = reg->off + reg->var_off.value;
 363 
 364         meta->ptr_not_const |= old_off != new_off;
 365 
 366         if (!meta->ptr_not_const)
 367                 return 0;
 368 
 369         if (old_off % 4 == new_off % 4)
 370                 return 0;
 371 
 372         pr_vlog(env, "stack access changed location was:%d is:%d\n",
 373                 old_off, new_off);
 374         return -EINVAL;
 375 }
 376 
 377 static const char *nfp_bpf_map_use_name(enum nfp_bpf_map_use use)
 378 {
 379         static const char * const names[] = {
 380                 [NFP_MAP_UNUSED]        = "unused",
 381                 [NFP_MAP_USE_READ]      = "read",
 382                 [NFP_MAP_USE_WRITE]     = "write",
 383                 [NFP_MAP_USE_ATOMIC_CNT] = "atomic",
 384         };
 385 
 386         if (use >= ARRAY_SIZE(names) || !names[use])
 387                 return "unknown";
 388         return names[use];
 389 }
 390 
 391 static int
 392 nfp_bpf_map_mark_used_one(struct bpf_verifier_env *env,
 393                           struct nfp_bpf_map *nfp_map,
 394                           unsigned int off, enum nfp_bpf_map_use use)
 395 {
 396         if (nfp_map->use_map[off / 4].type != NFP_MAP_UNUSED &&
 397             nfp_map->use_map[off / 4].type != use) {
 398                 pr_vlog(env, "map value use type conflict %s vs %s off: %u\n",
 399                         nfp_bpf_map_use_name(nfp_map->use_map[off / 4].type),
 400                         nfp_bpf_map_use_name(use), off);
 401                 return -EOPNOTSUPP;
 402         }
 403 
 404         if (nfp_map->use_map[off / 4].non_zero_update &&
 405             use == NFP_MAP_USE_ATOMIC_CNT) {
 406                 pr_vlog(env, "atomic counter in map value may already be initialized to non-zero value off: %u\n",
 407                         off);
 408                 return -EOPNOTSUPP;
 409         }
 410 
 411         nfp_map->use_map[off / 4].type = use;
 412 
 413         return 0;
 414 }
 415 
 416 static int
 417 nfp_bpf_map_mark_used(struct bpf_verifier_env *env, struct nfp_insn_meta *meta,
 418                       const struct bpf_reg_state *reg,
 419                       enum nfp_bpf_map_use use)
 420 {
 421         struct bpf_offloaded_map *offmap;
 422         struct nfp_bpf_map *nfp_map;
 423         unsigned int size, off;
 424         int i, err;
 425 
 426         if (!tnum_is_const(reg->var_off)) {
 427                 pr_vlog(env, "map value offset is variable\n");
 428                 return -EOPNOTSUPP;
 429         }
 430 
 431         off = reg->var_off.value + meta->insn.off + reg->off;
 432         size = BPF_LDST_BYTES(&meta->insn);
 433         offmap = map_to_offmap(reg->map_ptr);
 434         nfp_map = offmap->dev_priv;
 435 
 436         if (off + size > offmap->map.value_size) {
 437                 pr_vlog(env, "map value access out-of-bounds\n");
 438                 return -EINVAL;
 439         }
 440 
 441         for (i = 0; i < size; i += 4 - (off + i) % 4) {
 442                 err = nfp_bpf_map_mark_used_one(env, nfp_map, off + i, use);
 443                 if (err)
 444                         return err;
 445         }
 446 
 447         return 0;
 448 }
 449 
 450 static int
 451 nfp_bpf_check_ptr(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
 452                   struct bpf_verifier_env *env, u8 reg_no)
 453 {
 454         const struct bpf_reg_state *reg = cur_regs(env) + reg_no;
 455         int err;
 456 
 457         if (reg->type != PTR_TO_CTX &&
 458             reg->type != PTR_TO_STACK &&
 459             reg->type != PTR_TO_MAP_VALUE &&
 460             reg->type != PTR_TO_PACKET) {
 461                 pr_vlog(env, "unsupported ptr type: %d\n", reg->type);
 462                 return -EINVAL;
 463         }
 464 
 465         if (reg->type == PTR_TO_STACK) {
 466                 err = nfp_bpf_check_stack_access(nfp_prog, meta, reg, env);
 467                 if (err)
 468                         return err;
 469         }
 470 
 471         if (reg->type == PTR_TO_MAP_VALUE) {
 472                 if (is_mbpf_load(meta)) {
 473                         err = nfp_bpf_map_mark_used(env, meta, reg,
 474                                                     NFP_MAP_USE_READ);
 475                         if (err)
 476                                 return err;
 477                 }
 478                 if (is_mbpf_store(meta)) {
 479                         pr_vlog(env, "map writes not supported\n");
 480                         return -EOPNOTSUPP;
 481                 }
 482                 if (is_mbpf_xadd(meta)) {
 483                         err = nfp_bpf_map_mark_used(env, meta, reg,
 484                                                     NFP_MAP_USE_ATOMIC_CNT);
 485                         if (err)
 486                                 return err;
 487                 }
 488         }
 489 
 490         if (meta->ptr.type != NOT_INIT && meta->ptr.type != reg->type) {
 491                 pr_vlog(env, "ptr type changed for instruction %d -> %d\n",
 492                         meta->ptr.type, reg->type);
 493                 return -EINVAL;
 494         }
 495 
 496         meta->ptr = *reg;
 497 
 498         return 0;
 499 }
 500 
 501 static int
 502 nfp_bpf_check_store(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
 503                     struct bpf_verifier_env *env)
 504 {
 505         const struct bpf_reg_state *reg = cur_regs(env) + meta->insn.dst_reg;
 506 
 507         if (reg->type == PTR_TO_CTX) {
 508                 if (nfp_prog->type == BPF_PROG_TYPE_XDP) {
 509                         /* XDP ctx accesses must be 4B in size */
 510                         switch (meta->insn.off) {
 511                         case offsetof(struct xdp_md, rx_queue_index):
 512                                 if (nfp_prog->bpf->queue_select)
 513                                         goto exit_check_ptr;
 514                                 pr_vlog(env, "queue selection not supported by FW\n");
 515                                 return -EOPNOTSUPP;
 516                         }
 517                 }
 518                 pr_vlog(env, "unsupported store to context field\n");
 519                 return -EOPNOTSUPP;
 520         }
 521 exit_check_ptr:
 522         return nfp_bpf_check_ptr(nfp_prog, meta, env, meta->insn.dst_reg);
 523 }
 524 
 525 static int
 526 nfp_bpf_check_xadd(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
 527                    struct bpf_verifier_env *env)
 528 {
 529         const struct bpf_reg_state *sreg = cur_regs(env) + meta->insn.src_reg;
 530         const struct bpf_reg_state *dreg = cur_regs(env) + meta->insn.dst_reg;
 531 
 532         if (dreg->type != PTR_TO_MAP_VALUE) {
 533                 pr_vlog(env, "atomic add not to a map value pointer: %d\n",
 534                         dreg->type);
 535                 return -EOPNOTSUPP;
 536         }
 537         if (sreg->type != SCALAR_VALUE) {
 538                 pr_vlog(env, "atomic add not of a scalar: %d\n", sreg->type);
 539                 return -EOPNOTSUPP;
 540         }
 541 
 542         meta->xadd_over_16bit |=
 543                 sreg->var_off.value > 0xffff || sreg->var_off.mask > 0xffff;
 544         meta->xadd_maybe_16bit |=
 545                 (sreg->var_off.value & ~sreg->var_off.mask) <= 0xffff;
 546 
 547         return nfp_bpf_check_ptr(nfp_prog, meta, env, meta->insn.dst_reg);
 548 }
 549 
 550 static int
 551 nfp_bpf_check_alu(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta,
 552                   struct bpf_verifier_env *env)
 553 {
 554         const struct bpf_reg_state *sreg =
 555                 cur_regs(env) + meta->insn.src_reg;
 556         const struct bpf_reg_state *dreg =
 557                 cur_regs(env) + meta->insn.dst_reg;
 558 
 559         meta->umin_src = min(meta->umin_src, sreg->umin_value);
 560         meta->umax_src = max(meta->umax_src, sreg->umax_value);
 561         meta->umin_dst = min(meta->umin_dst, dreg->umin_value);
 562         meta->umax_dst = max(meta->umax_dst, dreg->umax_value);
 563 
 564         /* NFP supports u16 and u32 multiplication.
 565          *
 566          * For ALU64, if either operand is beyond u32's value range, we reject
 567          * it. One thing to note, if the source operand is BPF_K, then we need
 568          * to check "imm" field directly, and we'd reject it if it is negative.
 569          * Because for ALU64, "imm" (with s32 type) is expected to be sign
 570          * extended to s64 which NFP mul doesn't support.
 571          *
 572          * For ALU32, it is fine for "imm" be negative though, because the
 573          * result is 32-bits and there is no difference on the low halve of
 574          * the result for signed/unsigned mul, so we will get correct result.
 575          */
 576         if (is_mbpf_mul(meta)) {
 577                 if (meta->umax_dst > U32_MAX) {
 578                         pr_vlog(env, "multiplier is not within u32 value range\n");
 579                         return -EINVAL;
 580                 }
 581                 if (mbpf_src(meta) == BPF_X && meta->umax_src > U32_MAX) {
 582                         pr_vlog(env, "multiplicand is not within u32 value range\n");
 583                         return -EINVAL;
 584                 }
 585                 if (mbpf_class(meta) == BPF_ALU64 &&
 586                     mbpf_src(meta) == BPF_K && meta->insn.imm < 0) {
 587                         pr_vlog(env, "sign extended multiplicand won't be within u32 value range\n");
 588                         return -EINVAL;
 589                 }
 590         }
 591 
 592         /* NFP doesn't have divide instructions, we support divide by constant
 593          * through reciprocal multiplication. Given NFP support multiplication
 594          * no bigger than u32, we'd require divisor and dividend no bigger than
 595          * that as well.
 596          *
 597          * Also eBPF doesn't support signed divide and has enforced this on C
 598          * language level by failing compilation. However LLVM assembler hasn't
 599          * enforced this, so it is possible for negative constant to leak in as
 600          * a BPF_K operand through assembly code, we reject such cases as well.
 601          */
 602         if (is_mbpf_div(meta)) {
 603                 if (meta->umax_dst > U32_MAX) {
 604                         pr_vlog(env, "dividend is not within u32 value range\n");
 605                         return -EINVAL;
 606                 }
 607                 if (mbpf_src(meta) == BPF_X) {
 608                         if (meta->umin_src != meta->umax_src) {
 609                                 pr_vlog(env, "divisor is not constant\n");
 610                                 return -EINVAL;
 611                         }
 612                         if (meta->umax_src > U32_MAX) {
 613                                 pr_vlog(env, "divisor is not within u32 value range\n");
 614                                 return -EINVAL;
 615                         }
 616                 }
 617                 if (mbpf_src(meta) == BPF_K && meta->insn.imm < 0) {
 618                         pr_vlog(env, "divide by negative constant is not supported\n");
 619                         return -EINVAL;
 620                 }
 621         }
 622 
 623         return 0;
 624 }
 625 
 626 int nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx,
 627                     int prev_insn_idx)
 628 {
 629         struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv;
 630         struct nfp_insn_meta *meta = nfp_prog->verifier_meta;
 631 
 632         meta = nfp_bpf_goto_meta(nfp_prog, meta, insn_idx);
 633         nfp_prog->verifier_meta = meta;
 634 
 635         if (!nfp_bpf_supported_opcode(meta->insn.code)) {
 636                 pr_vlog(env, "instruction %#02x not supported\n",
 637                         meta->insn.code);
 638                 return -EINVAL;
 639         }
 640 
 641         if (meta->insn.src_reg >= MAX_BPF_REG ||
 642             meta->insn.dst_reg >= MAX_BPF_REG) {
 643                 pr_vlog(env, "program uses extended registers - jit hardening?\n");
 644                 return -EINVAL;
 645         }
 646 
 647         if (is_mbpf_helper_call(meta))
 648                 return nfp_bpf_check_helper_call(nfp_prog, env, meta);
 649         if (meta->insn.code == (BPF_JMP | BPF_EXIT))
 650                 return nfp_bpf_check_exit(nfp_prog, env);
 651 
 652         if (is_mbpf_load(meta))
 653                 return nfp_bpf_check_ptr(nfp_prog, meta, env,
 654                                          meta->insn.src_reg);
 655         if (is_mbpf_store(meta))
 656                 return nfp_bpf_check_store(nfp_prog, meta, env);
 657 
 658         if (is_mbpf_xadd(meta))
 659                 return nfp_bpf_check_xadd(nfp_prog, meta, env);
 660 
 661         if (is_mbpf_alu(meta))
 662                 return nfp_bpf_check_alu(nfp_prog, meta, env);
 663 
 664         return 0;
 665 }
 666 
 667 static int
 668 nfp_assign_subprog_idx_and_regs(struct bpf_verifier_env *env,
 669                                 struct nfp_prog *nfp_prog)
 670 {
 671         struct nfp_insn_meta *meta;
 672         int index = 0;
 673 
 674         list_for_each_entry(meta, &nfp_prog->insns, l) {
 675                 if (nfp_is_subprog_start(meta))
 676                         index++;
 677                 meta->subprog_idx = index;
 678 
 679                 if (meta->insn.dst_reg >= BPF_REG_6 &&
 680                     meta->insn.dst_reg <= BPF_REG_9)
 681                         nfp_prog->subprog[index].needs_reg_push = 1;
 682         }
 683 
 684         if (index + 1 != nfp_prog->subprog_cnt) {
 685                 pr_vlog(env, "BUG: number of processed BPF functions is not consistent (processed %d, expected %d)\n",
 686                         index + 1, nfp_prog->subprog_cnt);
 687                 return -EFAULT;
 688         }
 689 
 690         return 0;
 691 }
 692 
 693 static unsigned int nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog)
 694 {
 695         struct nfp_insn_meta *meta = nfp_prog_first_meta(nfp_prog);
 696         unsigned int max_depth = 0, depth = 0, frame = 0;
 697         struct nfp_insn_meta *ret_insn[MAX_CALL_FRAMES];
 698         unsigned short frame_depths[MAX_CALL_FRAMES];
 699         unsigned short ret_prog[MAX_CALL_FRAMES];
 700         unsigned short idx = meta->subprog_idx;
 701 
 702         /* Inspired from check_max_stack_depth() from kernel verifier.
 703          * Starting from main subprogram, walk all instructions and recursively
 704          * walk all callees that given subprogram can call. Since recursion is
 705          * prevented by the kernel verifier, this algorithm only needs a local
 706          * stack of MAX_CALL_FRAMES to remember callsites.
 707          */
 708 process_subprog:
 709         frame_depths[frame] = nfp_prog->subprog[idx].stack_depth;
 710         frame_depths[frame] = round_up(frame_depths[frame], STACK_FRAME_ALIGN);
 711         depth += frame_depths[frame];
 712         max_depth = max(max_depth, depth);
 713 
 714 continue_subprog:
 715         for (; meta != nfp_prog_last_meta(nfp_prog) && meta->subprog_idx == idx;
 716              meta = nfp_meta_next(meta)) {
 717                 if (!is_mbpf_pseudo_call(meta))
 718                         continue;
 719 
 720                 /* We found a call to a subprogram. Remember instruction to
 721                  * return to and subprog id.
 722                  */
 723                 ret_insn[frame] = nfp_meta_next(meta);
 724                 ret_prog[frame] = idx;
 725 
 726                 /* Find the callee and start processing it. */
 727                 meta = nfp_bpf_goto_meta(nfp_prog, meta,
 728                                          meta->n + 1 + meta->insn.imm);
 729                 idx = meta->subprog_idx;
 730                 frame++;
 731                 goto process_subprog;
 732         }
 733         /* End of for() loop means the last instruction of the subprog was
 734          * reached. If we popped all stack frames, return; otherwise, go on
 735          * processing remaining instructions from the caller.
 736          */
 737         if (frame == 0)
 738                 return max_depth;
 739 
 740         depth -= frame_depths[frame];
 741         frame--;
 742         meta = ret_insn[frame];
 743         idx = ret_prog[frame];
 744         goto continue_subprog;
 745 }
 746 
 747 static void nfp_bpf_insn_flag_zext(struct nfp_prog *nfp_prog,
 748                                    struct bpf_insn_aux_data *aux)
 749 {
 750         struct nfp_insn_meta *meta;
 751 
 752         list_for_each_entry(meta, &nfp_prog->insns, l) {
 753                 if (aux[meta->n].zext_dst)
 754                         meta->flags |= FLAG_INSN_DO_ZEXT;
 755         }
 756 }
 757 
 758 int nfp_bpf_finalize(struct bpf_verifier_env *env)
 759 {
 760         struct bpf_subprog_info *info;
 761         struct nfp_prog *nfp_prog;
 762         unsigned int max_stack;
 763         struct nfp_net *nn;
 764         int i;
 765 
 766         nfp_prog = env->prog->aux->offload->dev_priv;
 767         nfp_prog->subprog_cnt = env->subprog_cnt;
 768         nfp_prog->subprog = kcalloc(nfp_prog->subprog_cnt,
 769                                     sizeof(nfp_prog->subprog[0]), GFP_KERNEL);
 770         if (!nfp_prog->subprog)
 771                 return -ENOMEM;
 772 
 773         nfp_assign_subprog_idx_and_regs(env, nfp_prog);
 774 
 775         info = env->subprog_info;
 776         for (i = 0; i < nfp_prog->subprog_cnt; i++) {
 777                 nfp_prog->subprog[i].stack_depth = info[i].stack_depth;
 778 
 779                 if (i == 0)
 780                         continue;
 781 
 782                 /* Account for size of return address. */
 783                 nfp_prog->subprog[i].stack_depth += REG_WIDTH;
 784                 /* Account for size of saved registers, if necessary. */
 785                 if (nfp_prog->subprog[i].needs_reg_push)
 786                         nfp_prog->subprog[i].stack_depth += BPF_REG_SIZE * 4;
 787         }
 788 
 789         nn = netdev_priv(env->prog->aux->offload->netdev);
 790         max_stack = nn_readb(nn, NFP_NET_CFG_BPF_STACK_SZ) * 64;
 791         nfp_prog->stack_size = nfp_bpf_get_stack_usage(nfp_prog);
 792         if (nfp_prog->stack_size > max_stack) {
 793                 pr_vlog(env, "stack too large: program %dB > FW stack %dB\n",
 794                         nfp_prog->stack_size, max_stack);
 795                 return -EOPNOTSUPP;
 796         }
 797 
 798         nfp_bpf_insn_flag_zext(nfp_prog, env->insn_aux_data);
 799         return 0;
 800 }
 801 
 802 int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off,
 803                              struct bpf_insn *insn)
 804 {
 805         struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv;
 806         struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
 807         struct nfp_insn_meta *meta = nfp_prog->verifier_meta;
 808 
 809         meta = nfp_bpf_goto_meta(nfp_prog, meta, aux_data[off].orig_idx);
 810         nfp_prog->verifier_meta = meta;
 811 
 812         /* conditional jump to jump conversion */
 813         if (is_mbpf_cond_jump(meta) &&
 814             insn->code == (BPF_JMP | BPF_JA | BPF_K)) {
 815                 unsigned int tgt_off;
 816 
 817                 tgt_off = off + insn->off + 1;
 818 
 819                 if (!insn->off) {
 820                         meta->jmp_dst = list_next_entry(meta, l);
 821                         meta->jump_neg_op = false;
 822                 } else if (meta->jmp_dst->n != aux_data[tgt_off].orig_idx) {
 823                         pr_vlog(env, "branch hard wire at %d changes target %d -> %d\n",
 824                                 off, meta->jmp_dst->n,
 825                                 aux_data[tgt_off].orig_idx);
 826                         return -EINVAL;
 827                 }
 828                 return 0;
 829         }
 830 
 831         pr_vlog(env, "unsupported instruction replacement %hhx -> %hhx\n",
 832                 meta->insn.code, insn->code);
 833         return -EINVAL;
 834 }
 835 
 836 int nfp_bpf_opt_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
 837 {
 838         struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv;
 839         struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
 840         struct nfp_insn_meta *meta = nfp_prog->verifier_meta;
 841         unsigned int i;
 842 
 843         meta = nfp_bpf_goto_meta(nfp_prog, meta, aux_data[off].orig_idx);
 844 
 845         for (i = 0; i < cnt; i++) {
 846                 if (WARN_ON_ONCE(&meta->l == &nfp_prog->insns))
 847                         return -EINVAL;
 848 
 849                 /* doesn't count if it already has the flag */
 850                 if (meta->flags & FLAG_INSN_SKIP_VERIFIER_OPT)
 851                         i--;
 852 
 853                 meta->flags |= FLAG_INSN_SKIP_VERIFIER_OPT;
 854                 meta = list_next_entry(meta, l);
 855         }
 856 
 857         return 0;
 858 }