kernel/bpf/verifier.c

   1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
   2  *
   3  * This program is free software; you can redistribute it and/or
   4  * modify it under the terms of version 2 of the GNU General Public
   5  * License as published by the Free Software Foundation.
   6  *
   7  * This program is distributed in the hope that it will be useful, but
   8  * WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  10  * General Public License for more details.
  11  */
  12 #include <linux/kernel.h>
  13 #include <linux/types.h>
  14 #include <linux/slab.h>
  15 #include <linux/bpf.h>
  16 #include <linux/filter.h>
  17 #include <net/netlink.h>
  18 #include <linux/file.h>
  19 #include <linux/vmalloc.h>
  20
  21 /* bpf_check() is a static code analyzer that walks eBPF program
  22  * instruction by instruction and updates register/stack state.
  23  * All paths of conditional branches are analyzed until 'bpf_exit' insn.
  24  *
  25  * The first pass is depth-first-search to check that the program is a DAG.
  26  * It rejects the following programs:
  27  * - larger than BPF_MAXINSNS insns
  28  * - if loop is present (detected via back-edge)
  29  * - unreachable insns exist (shouldn't be a forest. program = one function)
  30  * - out of bounds or malformed jumps
  31  * The second pass is all possible path descent from the 1st insn.
  32  * Since it's analyzing all pathes through the program, the length of the
  33  * analysis is limited to 32k insn, which may be hit even if total number of
  34  * insn is less then 4K, but there are too many branches that change stack/regs.
  35  * Number of 'branches to be analyzed' is limited to 1k
  36  *
  37  * On entry to each instruction, each register has a type, and the instruction
  38  * changes the types of the registers depending on instruction semantics.
  39  * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is
  40  * copied to R1.
  41  *
  42  * All registers are 64-bit.
  43  * R0 - return register
  44  * R1-R5 argument passing registers
  45  * R6-R9 callee saved registers
  46  * R10 - frame pointer read-only
  47  *
  48  * At the start of BPF program the register R1 contains a pointer to bpf_context
  49  * and has type PTR_TO_CTX.
  50  *
  51  * Verifier tracks arithmetic operations on pointers in case:
  52  *    BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
  53  *    BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20),
  54  * 1st insn copies R10 (which has FRAME_PTR) type into R1
  55  * and 2nd arithmetic instruction is pattern matched to recognize
  56  * that it wants to construct a pointer to some element within stack.
  57  * So after 2nd insn, the register R1 has type PTR_TO_STACK
  58  * (and -20 constant is saved for further stack bounds checking).
  59  * Meaning that this reg is a pointer to stack plus known immediate constant.
  60  *
  61  * Most of the time the registers have UNKNOWN_VALUE type, which
  62  * means the register has some value, but it's not a valid pointer.
  63  * (like pointer plus pointer becomes UNKNOWN_VALUE type)
  64  *
  65  * When verifier sees load or store instructions the type of base register
  66  * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, FRAME_PTR. These are three pointer
  67  * types recognized by check_mem_access() function.
  68  *
  69  * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value'
  70  * and the range of [ptr, ptr + map's value_size) is accessible.
  71  *
  72  * registers used to pass values to function calls are checked against
  73  * function argument constraints.
  74  *
  75  * ARG_PTR_TO_MAP_KEY is one of such argument constraints.
  76  * It means that the register type passed to this function must be
  77  * PTR_TO_STACK and it will be used inside the function as
  78  * 'pointer to map element key'
  79  *
  80  * For example the argument constraints for bpf_map_lookup_elem():
  81  *   .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
  82  *   .arg1_type = ARG_CONST_MAP_PTR,
  83  *   .arg2_type = ARG_PTR_TO_MAP_KEY,
  84  *
  85  * ret_type says that this function returns 'pointer to map elem value or null'
  86  * function expects 1st argument to be a const pointer to 'struct bpf_map' and
  87  * 2nd argument should be a pointer to stack, which will be used inside
  88  * the helper function as a pointer to map element key.
  89  *
  90  * On the kernel side the helper function looks like:
  91  * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
  92  * {
  93  *    struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
  94  *    void *key = (void *) (unsigned long) r2;
  95  *    void *value;
  96  *
  97  *    here kernel can access 'key' and 'map' pointers safely, knowing that
  98  *    [key, key + map->key_size) bytes are valid and were initialized on
  99  *    the stack of eBPF program.
 100  * }
 101  *
 102  * Corresponding eBPF program may look like:
 103  *    BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),  // after this insn R2 type is FRAME_PTR
 104  *    BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK
 105  *    BPF_LD_MAP_FD(BPF_REG_1, map_fd),      // after this insn R1 type is CONST_PTR_TO_MAP
 106  *    BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
 107  * here verifier looks at prototype of map_lookup_elem() and sees:
 108  * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok,
 109  * Now verifier knows that this map has key of R1->map_ptr->key_size bytes
 110  *
 111  * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far,
 112  * Now verifier checks that [R2, R2 + map's key_size) are within stack limits
 113  * and were initialized prior to this call.
 114  * If it's ok, then verifier allows this BPF_CALL insn and looks at
 115  * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets
 116  * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function
 117  * returns ether pointer to map value or NULL.
 118  *
 119  * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off'
 120  * insn, the register holding that pointer in the true branch changes state to
 121  * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false
 122  * branch. See check_cond_jmp_op().
 123  *
 124  * After the call R0 is set to return type of the function and registers R1-R5
 125  * are set to NOT_INIT to indicate that they are no longer readable.
 126  */
 127
 128 /* types of values stored in eBPF registers */
 129 enum bpf_reg_type {
 130         NOT_INIT = 0,            /* nothing was written into register */
 131         UNKNOWN_VALUE,           /* reg doesn't contain a valid pointer */
 132         PTR_TO_CTX,              /* reg points to bpf_context */
 133         CONST_PTR_TO_MAP,        /* reg points to struct bpf_map */
 134         PTR_TO_MAP_VALUE,        /* reg points to map element value */
 135         PTR_TO_MAP_VALUE_OR_NULL,/* points to map elem value or NULL */
 136         FRAME_PTR,               /* reg == frame_pointer */
 137         PTR_TO_STACK,            /* reg == frame_pointer + imm */
 138         CONST_IMM,               /* constant integer value */
 139 };
 140
 141 struct reg_state {
 142         enum bpf_reg_type type;
 143         union {
 144                 /* valid when type == CONST_IMM | PTR_TO_STACK */
 145                 int imm;
 146
 147                 /* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE |
 148                  *   PTR_TO_MAP_VALUE_OR_NULL
 149                  */
 150                 struct bpf_map *map_ptr;
 151         };
 152 };
 153
 154 enum bpf_stack_slot_type {
 155         STACK_INVALID,    /* nothing was stored in this stack slot */
 156         STACK_SPILL,      /* 1st byte of register spilled into stack */
 157         STACK_SPILL_PART, /* other 7 bytes of register spill */
 158         STACK_MISC        /* BPF program wrote some data into this slot */
 159 };
 160
 161 struct bpf_stack_slot {
 162         enum bpf_stack_slot_type stype;
 163         struct reg_state reg_st;
 164 };
 165
 166 /* state of the program:
 167  * type of all registers and stack info
 168  */
 169 struct verifier_state {
 170         struct reg_state regs[MAX_BPF_REG];
 171         struct bpf_stack_slot stack[MAX_BPF_STACK];
 172 };
 173
 174 /* linked list of verifier states used to prune search */
 175 struct verifier_state_list {
 176         struct verifier_state state;
 177         struct verifier_state_list *next;
 178 };
 179
 180 /* verifier_state + insn_idx are pushed to stack when branch is encountered */
 181 struct verifier_stack_elem {
 182         /* verifer state is 'st'
 183          * before processing instruction 'insn_idx'
 184          * and after processing instruction 'prev_insn_idx'
 185          */
 186         struct verifier_state st;
 187         int insn_idx;
 188         int prev_insn_idx;
 189         struct verifier_stack_elem *next;
 190 };
 191
 192 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
 193
 194 /* single container for all structs
 195  * one verifier_env per bpf_check() call
 196  */
 197 struct verifier_env {
 198         struct bpf_prog *prog;          /* eBPF program being verified */
 199         struct verifier_stack_elem *head; /* stack of verifier states to be processed */
 200         int stack_size;                 /* number of states to be processed */
 201         struct verifier_state cur_state; /* current verifier state */
 202         struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
 203         u32 used_map_cnt;               /* number of used maps */
 204 };
 205
 206 /* verbose verifier prints what it's seeing
 207  * bpf_check() is called under lock, so no race to access these global vars
 208  */
 209 static u32 log_level, log_size, log_len;
 210 static char *log_buf;
 211
 212 static DEFINE_MUTEX(bpf_verifier_lock);
 213
 214 /* log_level controls verbosity level of eBPF verifier.
 215  * verbose() is used to dump the verification trace to the log, so the user
 216  * can figure out what's wrong with the program
 217  */
 218 static void verbose(const char *fmt, ...)
 219 {
 220         va_list args;
 221
 222         if (log_level == 0 || log_len >= log_size - 1)
 223                 return;
 224
 225         va_start(args, fmt);
 226         log_len += vscnprintf(log_buf + log_len, log_size - log_len, fmt, args);
 227         va_end(args);
 228 }
 229
 230 /* string representation of 'enum bpf_reg_type' */
 231 static const char * const reg_type_str[] = {
 232         [NOT_INIT]              = "?",
 233         [UNKNOWN_VALUE]         = "inv",
 234         [PTR_TO_CTX]            = "ctx",
 235         [CONST_PTR_TO_MAP]      = "map_ptr",
 236         [PTR_TO_MAP_VALUE]      = "map_value",
 237         [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null",
 238         [FRAME_PTR]             = "fp",
 239         [PTR_TO_STACK]          = "fp",
 240         [CONST_IMM]             = "imm",
 241 };
 242
 243 static void print_verifier_state(struct verifier_env *env)
 244 {
 245         enum bpf_reg_type t;
 246         int i;
 247
 248         for (i = 0; i < MAX_BPF_REG; i++) {
 249                 t = env->cur_state.regs[i].type;
 250                 if (t == NOT_INIT)
 251                         continue;
 252                 verbose(" R%d=%s", i, reg_type_str[t]);
 253                 if (t == CONST_IMM || t == PTR_TO_STACK)
 254                         verbose("%d", env->cur_state.regs[i].imm);
 255                 else if (t == CONST_PTR_TO_MAP || t == PTR_TO_MAP_VALUE ||
 256                          t == PTR_TO_MAP_VALUE_OR_NULL)
 257                         verbose("(ks=%d,vs=%d)",
 258                                 env->cur_state.regs[i].map_ptr->key_size,
 259                                 env->cur_state.regs[i].map_ptr->value_size);
 260         }
 261         for (i = 0; i < MAX_BPF_STACK; i++) {
 262                 if (env->cur_state.stack[i].stype == STACK_SPILL)
 263                         verbose(" fp%d=%s", -MAX_BPF_STACK + i,
 264                                 reg_type_str[env->cur_state.stack[i].reg_st.type]);
 265         }
 266         verbose("\n");
 267 }
 268
 269 static const char *const bpf_class_string[] = {
 270         [BPF_LD]    = "ld",
 271         [BPF_LDX]   = "ldx",
 272         [BPF_ST]    = "st",
 273         [BPF_STX]   = "stx",
 274         [BPF_ALU]   = "alu",
 275         [BPF_JMP]   = "jmp",
 276         [BPF_RET]   = "BUG",
 277         [BPF_ALU64] = "alu64",
 278 };
 279
 280 static const char *const bpf_alu_string[] = {
 281         [BPF_ADD >> 4]  = "+=",
 282         [BPF_SUB >> 4]  = "-=",
 283         [BPF_MUL >> 4]  = "*=",
 284         [BPF_DIV >> 4]  = "/=",
 285         [BPF_OR  >> 4]  = "|=",
 286         [BPF_AND >> 4]  = "&=",
 287         [BPF_LSH >> 4]  = "<<=",
 288         [BPF_RSH >> 4]  = ">>=",
 289         [BPF_NEG >> 4]  = "neg",
 290         [BPF_MOD >> 4]  = "%=",
 291         [BPF_XOR >> 4]  = "^=",
 292         [BPF_MOV >> 4]  = "=",
 293         [BPF_ARSH >> 4] = "s>>=",
 294         [BPF_END >> 4]  = "endian",
 295 };
 296
 297 static const char *const bpf_ldst_string[] = {
 298         [BPF_W >> 3]  = "u32",
 299         [BPF_H >> 3]  = "u16",
 300         [BPF_B >> 3]  = "u8",
 301         [BPF_DW >> 3] = "u64",
 302 };
 303
 304 static const char *const bpf_jmp_string[] = {
 305         [BPF_JA >> 4]   = "jmp",
 306         [BPF_JEQ >> 4]  = "==",
 307         [BPF_JGT >> 4]  = ">",
 308         [BPF_JGE >> 4]  = ">=",
 309         [BPF_JSET >> 4] = "&",
 310         [BPF_JNE >> 4]  = "!=",
 311         [BPF_JSGT >> 4] = "s>",
 312         [BPF_JSGE >> 4] = "s>=",
 313         [BPF_CALL >> 4] = "call",
 314         [BPF_EXIT >> 4] = "exit",
 315 };
 316
 317 static void print_bpf_insn(struct bpf_insn *insn)
 318 {
 319         u8 class = BPF_CLASS(insn->code);
 320
 321         if (class == BPF_ALU || class == BPF_ALU64) {
 322                 if (BPF_SRC(insn->code) == BPF_X)
 323                         verbose("(%02x) %sr%d %s %sr%d\n",
 324                                 insn->code, class == BPF_ALU ? "(u32) " : "",
 325                                 insn->dst_reg,
 326                                 bpf_alu_string[BPF_OP(insn->code) >> 4],
 327                                 class == BPF_ALU ? "(u32) " : "",
 328                                 insn->src_reg);
 329                 else
 330                         verbose("(%02x) %sr%d %s %s%d\n",
 331                                 insn->code, class == BPF_ALU ? "(u32) " : "",
 332                                 insn->dst_reg,
 333                                 bpf_alu_string[BPF_OP(insn->code) >> 4],
 334                                 class == BPF_ALU ? "(u32) " : "",
 335                                 insn->imm);
 336         } else if (class == BPF_STX) {
 337                 if (BPF_MODE(insn->code) == BPF_MEM)
 338                         verbose("(%02x) *(%s *)(r%d %+d) = r%d\n",
 339                                 insn->code,
 340                                 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
 341                                 insn->dst_reg,
 342                                 insn->off, insn->src_reg);
 343                 else if (BPF_MODE(insn->code) == BPF_XADD)
 344                         verbose("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
 345                                 insn->code,
 346                                 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
 347                                 insn->dst_reg, insn->off,
 348                                 insn->src_reg);
 349                 else
 350                         verbose("BUG_%02x\n", insn->code);
 351         } else if (class == BPF_ST) {
 352                 if (BPF_MODE(insn->code) != BPF_MEM) {
 353                         verbose("BUG_st_%02x\n", insn->code);
 354                         return;
 355                 }
 356                 verbose("(%02x) *(%s *)(r%d %+d) = %d\n",
 357                         insn->code,
 358                         bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
 359                         insn->dst_reg,
 360                         insn->off, insn->imm);
 361         } else if (class == BPF_LDX) {
 362                 if (BPF_MODE(insn->code) != BPF_MEM) {
 363                         verbose("BUG_ldx_%02x\n", insn->code);
 364                         return;
 365                 }
 366                 verbose("(%02x) r%d = *(%s *)(r%d %+d)\n",
 367                         insn->code, insn->dst_reg,
 368                         bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
 369                         insn->src_reg, insn->off);
 370         } else if (class == BPF_LD) {
 371                 if (BPF_MODE(insn->code) == BPF_ABS) {
 372                         verbose("(%02x) r0 = *(%s *)skb[%d]\n",
 373                                 insn->code,
 374                                 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
 375                                 insn->imm);
 376                 } else if (BPF_MODE(insn->code) == BPF_IND) {
 377                         verbose("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
 378                                 insn->code,
 379                                 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
 380                                 insn->src_reg, insn->imm);
 381                 } else if (BPF_MODE(insn->code) == BPF_IMM) {
 382                         verbose("(%02x) r%d = 0x%x\n",
 383                                 insn->code, insn->dst_reg, insn->imm);
 384                 } else {
 385                         verbose("BUG_ld_%02x\n", insn->code);
 386                         return;
 387                 }
 388         } else if (class == BPF_JMP) {
 389                 u8 opcode = BPF_OP(insn->code);
 390
 391                 if (opcode == BPF_CALL) {
 392                         verbose("(%02x) call %d\n", insn->code, insn->imm);
 393                 } else if (insn->code == (BPF_JMP | BPF_JA)) {
 394                         verbose("(%02x) goto pc%+d\n",
 395                                 insn->code, insn->off);
 396                 } else if (insn->code == (BPF_JMP | BPF_EXIT)) {
 397                         verbose("(%02x) exit\n", insn->code);
 398                 } else if (BPF_SRC(insn->code) == BPF_X) {
 399                         verbose("(%02x) if r%d %s r%d goto pc%+d\n",
 400                                 insn->code, insn->dst_reg,
 401                                 bpf_jmp_string[BPF_OP(insn->code) >> 4],
 402                                 insn->src_reg, insn->off);
 403                 } else {
 404                         verbose("(%02x) if r%d %s 0x%x goto pc%+d\n",
 405                                 insn->code, insn->dst_reg,
 406                                 bpf_jmp_string[BPF_OP(insn->code) >> 4],
 407                                 insn->imm, insn->off);
 408                 }
 409         } else {
 410                 verbose("(%02x) %s\n", insn->code, bpf_class_string[class]);
 411         }
 412 }
 413
 414 static int pop_stack(struct verifier_env *env, int *prev_insn_idx)
 415 {
 416         struct verifier_stack_elem *elem;
 417         int insn_idx;
 418
 419         if (env->head == NULL)
 420                 return -1;
 421
 422         memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
 423         insn_idx = env->head->insn_idx;
 424         if (prev_insn_idx)
 425                 *prev_insn_idx = env->head->prev_insn_idx;
 426         elem = env->head->next;
 427         kfree(env->head);
 428         env->head = elem;
 429         env->stack_size--;
 430         return insn_idx;
 431 }
 432
 433 static struct verifier_state *push_stack(struct verifier_env *env, int insn_idx,
 434                                          int prev_insn_idx)
 435 {
 436         struct verifier_stack_elem *elem;
 437
 438         elem = kmalloc(sizeof(struct verifier_stack_elem), GFP_KERNEL);
 439         if (!elem)
 440                 goto err;
 441
 442         memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));
 443         elem->insn_idx = insn_idx;
 444         elem->prev_insn_idx = prev_insn_idx;
 445         elem->next = env->head;
 446         env->head = elem;
 447         env->stack_size++;
 448         if (env->stack_size > 1024) {
 449                 verbose("BPF program is too complex\n");
 450                 goto err;
 451         }
 452         return &elem->st;
 453 err:
 454         /* pop all elements and return */
 455         while (pop_stack(env, NULL) >= 0);
 456         return NULL;
 457 }
 458
 459 #define CALLER_SAVED_REGS 6
 460 static const int caller_saved[CALLER_SAVED_REGS] = {
 461         BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
 462 };
 463
 464 static void init_reg_state(struct reg_state *regs)
 465 {
 466         int i;
 467
 468         for (i = 0; i < MAX_BPF_REG; i++) {
 469                 regs[i].type = NOT_INIT;
 470                 regs[i].imm = 0;
 471                 regs[i].map_ptr = NULL;
 472         }
 473
 474         /* frame pointer */
 475         regs[BPF_REG_FP].type = FRAME_PTR;
 476
 477         /* 1st arg to a function */
 478         regs[BPF_REG_1].type = PTR_TO_CTX;
 479 }
 480
 481 static void mark_reg_unknown_value(struct reg_state *regs, u32 regno)
 482 {
 483         BUG_ON(regno >= MAX_BPF_REG);
 484         regs[regno].type = UNKNOWN_VALUE;
 485         regs[regno].imm = 0;
 486         regs[regno].map_ptr = NULL;
 487 }
 488
 489 enum reg_arg_type {
 490         SRC_OP,         /* register is used as source operand */
 491         DST_OP,         /* register is used as destination operand */
 492         DST_OP_NO_MARK  /* same as above, check only, don't mark */
 493 };
 494
 495 static int check_reg_arg(struct reg_state *regs, u32 regno,
 496                          enum reg_arg_type t)
 497 {
 498         if (regno >= MAX_BPF_REG) {
 499                 verbose("R%d is invalid\n", regno);
 500                 return -EINVAL;
 501         }
 502
 503         if (t == SRC_OP) {
 504                 /* check whether register used as source operand can be read */
 505                 if (regs[regno].type == NOT_INIT) {
 506                         verbose("R%d !read_ok\n", regno);
 507                         return -EACCES;
 508                 }
 509         } else {
 510                 /* check whether register used as dest operand can be written to */
 511                 if (regno == BPF_REG_FP) {
 512                         verbose("frame pointer is read only\n");
 513                         return -EACCES;
 514                 }
 515                 if (t == DST_OP)
 516                         mark_reg_unknown_value(regs, regno);
 517         }
 518         return 0;
 519 }
 520
 521 static int bpf_size_to_bytes(int bpf_size)
 522 {
 523         if (bpf_size == BPF_W)
 524                 return 4;
 525         else if (bpf_size == BPF_H)
 526                 return 2;
 527         else if (bpf_size == BPF_B)
 528                 return 1;
 529         else if (bpf_size == BPF_DW)
 530                 return 8;
 531         else
 532                 return -EINVAL;
 533 }
 534
 535 /* check_stack_read/write functions track spill/fill of registers,
 536  * stack boundary and alignment are checked in check_mem_access()
 537  */
 538 static int check_stack_write(struct verifier_state *state, int off, int size,
 539                              int value_regno)
 540 {
 541         struct bpf_stack_slot *slot;
 542         int i;
 543
 544         if (value_regno >= 0 &&
 545             (state->regs[value_regno].type == PTR_TO_MAP_VALUE ||
 546              state->regs[value_regno].type == PTR_TO_STACK ||
 547              state->regs[value_regno].type == PTR_TO_CTX)) {
 548
 549                 /* register containing pointer is being spilled into stack */
 550                 if (size != 8) {
 551                         verbose("invalid size of register spill\n");
 552                         return -EACCES;
 553                 }
 554
 555                 slot = &state->stack[MAX_BPF_STACK + off];
 556                 slot->stype = STACK_SPILL;
 557                 /* save register state */
 558                 slot->reg_st = state->regs[value_regno];
 559                 for (i = 1; i < 8; i++) {
 560                         slot = &state->stack[MAX_BPF_STACK + off + i];
 561                         slot->stype = STACK_SPILL_PART;
 562                         slot->reg_st.type = UNKNOWN_VALUE;
 563                         slot->reg_st.map_ptr = NULL;
 564                 }
 565         } else {
 566
 567                 /* regular write of data into stack */
 568                 for (i = 0; i < size; i++) {
 569                         slot = &state->stack[MAX_BPF_STACK + off + i];
 570                         slot->stype = STACK_MISC;
 571                         slot->reg_st.type = UNKNOWN_VALUE;
 572                         slot->reg_st.map_ptr = NULL;
 573                 }
 574         }
 575         return 0;
 576 }
 577
 578 static int check_stack_read(struct verifier_state *state, int off, int size,
 579                             int value_regno)
 580 {
 581         int i;
 582         struct bpf_stack_slot *slot;
 583
 584         slot = &state->stack[MAX_BPF_STACK + off];
 585
 586         if (slot->stype == STACK_SPILL) {
 587                 if (size != 8) {
 588                         verbose("invalid size of register spill\n");
 589                         return -EACCES;
 590                 }
 591                 for (i = 1; i < 8; i++) {
 592                         if (state->stack[MAX_BPF_STACK + off + i].stype !=
 593                             STACK_SPILL_PART) {
 594                                 verbose("corrupted spill memory\n");
 595                                 return -EACCES;
 596                         }
 597                 }
 598
 599                 if (value_regno >= 0)
 600                         /* restore register state from stack */
 601                         state->regs[value_regno] = slot->reg_st;
 602                 return 0;
 603         } else {
 604                 for (i = 0; i < size; i++) {
 605                         if (state->stack[MAX_BPF_STACK + off + i].stype !=
 606                             STACK_MISC) {
 607                                 verbose("invalid read from stack off %d+%d size %d\n",
 608                                         off, i, size);
 609                                 return -EACCES;
 610                         }
 611                 }
 612                 if (value_regno >= 0)
 613                         /* have read misc data from the stack */
 614                         mark_reg_unknown_value(state->regs, value_regno);
 615                 return 0;
 616         }
 617 }
 618
 619 /* check read/write into map element returned by bpf_map_lookup_elem() */
 620 static int check_map_access(struct verifier_env *env, u32 regno, int off,
 621                             int size)
 622 {
 623         struct bpf_map *map = env->cur_state.regs[regno].map_ptr;
 624
 625         if (off < 0 || off + size > map->value_size) {
 626                 verbose("invalid access to map value, value_size=%d off=%d size=%d\n",
 627                         map->value_size, off, size);
 628                 return -EACCES;
 629         }
 630         return 0;
 631 }
 632
 633 /* check access to 'struct bpf_context' fields */
 634 static int check_ctx_access(struct verifier_env *env, int off, int size,
 635                             enum bpf_access_type t)
 636 {
 637         if (env->prog->aux->ops->is_valid_access &&
 638             env->prog->aux->ops->is_valid_access(off, size, t))
 639                 return 0;
 640
 641         verbose("invalid bpf_context access off=%d size=%d\n", off, size);
 642         return -EACCES;
 643 }
 644
 645 /* check whether memory at (regno + off) is accessible for t = (read | write)
 646  * if t==write, value_regno is a register which value is stored into memory
 647  * if t==read, value_regno is a register which will receive the value from memory
 648  * if t==write && value_regno==-1, some unknown value is stored into memory
 649  * if t==read && value_regno==-1, don't care what we read from memory
 650  */
 651 static int check_mem_access(struct verifier_env *env, u32 regno, int off,
 652                             int bpf_size, enum bpf_access_type t,
 653                             int value_regno)
 654 {
 655         struct verifier_state *state = &env->cur_state;
 656         int size, err = 0;
 657
 658         size = bpf_size_to_bytes(bpf_size);
 659         if (size < 0)
 660                 return size;
 661
 662         if (off % size != 0) {
 663                 verbose("misaligned access off %d size %d\n", off, size);
 664                 return -EACCES;
 665         }
 666
 667         if (state->regs[regno].type == PTR_TO_MAP_VALUE) {
 668                 err = check_map_access(env, regno, off, size);
 669                 if (!err && t == BPF_READ && value_regno >= 0)
 670                         mark_reg_unknown_value(state->regs, value_regno);
 671
 672         } else if (state->regs[regno].type == PTR_TO_CTX) {
 673                 err = check_ctx_access(env, off, size, t);
 674                 if (!err && t == BPF_READ && value_regno >= 0)
 675                         mark_reg_unknown_value(state->regs, value_regno);
 676
 677         } else if (state->regs[regno].type == FRAME_PTR) {
 678                 if (off >= 0 || off < -MAX_BPF_STACK) {
 679                         verbose("invalid stack off=%d size=%d\n", off, size);
 680                         return -EACCES;
 681                 }
 682                 if (t == BPF_WRITE)
 683                         err = check_stack_write(state, off, size, value_regno);
 684                 else
 685                         err = check_stack_read(state, off, size, value_regno);
 686         } else {
 687                 verbose("R%d invalid mem access '%s'\n",
 688                         regno, reg_type_str[state->regs[regno].type]);
 689                 return -EACCES;
 690         }
 691         return err;
 692 }
 693
 694 static int check_xadd(struct verifier_env *env, struct bpf_insn *insn)
 695 {
 696         struct reg_state *regs = env->cur_state.regs;
 697         int err;
 698
 699         if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
 700             insn->imm != 0) {
 701                 verbose("BPF_XADD uses reserved fields\n");
 702                 return -EINVAL;
 703         }
 704
 705         /* check src1 operand */
 706         err = check_reg_arg(regs, insn->src_reg, SRC_OP);
 707         if (err)
 708                 return err;
 709
 710         /* check src2 operand */
 711         err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
 712         if (err)
 713                 return err;
 714
 715         /* check whether atomic_add can read the memory */
 716         err = check_mem_access(env, insn->dst_reg, insn->off,
 717                                BPF_SIZE(insn->code), BPF_READ, -1);
 718         if (err)
 719                 return err;
 720
 721         /* check whether atomic_add can write into the same memory */
 722         return check_mem_access(env, insn->dst_reg, insn->off,
 723                                 BPF_SIZE(insn->code), BPF_WRITE, -1);
 724 }
 725
 726 /* when register 'regno' is passed into function that will read 'access_size'
 727  * bytes from that pointer, make sure that it's within stack boundary
 728  * and all elements of stack are initialized
 729  */
 730 static int check_stack_boundary(struct verifier_env *env,
 731                                 int regno, int access_size)
 732 {
 733         struct verifier_state *state = &env->cur_state;
 734         struct reg_state *regs = state->regs;
 735         int off, i;
 736
 737         if (regs[regno].type != PTR_TO_STACK)
 738                 return -EACCES;
 739
 740         off = regs[regno].imm;
 741         if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
 742             access_size <= 0) {
 743                 verbose("invalid stack type R%d off=%d access_size=%d\n",
 744                         regno, off, access_size);
 745                 return -EACCES;
 746         }
 747
 748         for (i = 0; i < access_size; i++) {
 749                 if (state->stack[MAX_BPF_STACK + off + i].stype != STACK_MISC) {
 750                         verbose("invalid indirect read from stack off %d+%d size %d\n",
 751                                 off, i, access_size);
 752                         return -EACCES;
 753                 }
 754         }
 755         return 0;
 756 }
 757
 758 static int check_func_arg(struct verifier_env *env, u32 regno,
 759                           enum bpf_arg_type arg_type, struct bpf_map **mapp)
 760 {
 761         struct reg_state *reg = env->cur_state.regs + regno;
 762         enum bpf_reg_type expected_type;
 763         int err = 0;
 764
 765         if (arg_type == ARG_ANYTHING)
 766                 return 0;
 767
 768         if (reg->type == NOT_INIT) {
 769                 verbose("R%d !read_ok\n", regno);
 770                 return -EACCES;
 771         }
 772
 773         if (arg_type == ARG_PTR_TO_STACK || arg_type == ARG_PTR_TO_MAP_KEY ||
 774             arg_type == ARG_PTR_TO_MAP_VALUE) {
 775                 expected_type = PTR_TO_STACK;
 776         } else if (arg_type == ARG_CONST_STACK_SIZE) {
 777                 expected_type = CONST_IMM;
 778         } else if (arg_type == ARG_CONST_MAP_PTR) {
 779                 expected_type = CONST_PTR_TO_MAP;
 780         } else {
 781                 verbose("unsupported arg_type %d\n", arg_type);
 782                 return -EFAULT;
 783         }
 784
 785         if (reg->type != expected_type) {
 786                 verbose("R%d type=%s expected=%s\n", regno,
 787                         reg_type_str[reg->type], reg_type_str[expected_type]);
 788                 return -EACCES;
 789         }
 790
 791         if (arg_type == ARG_CONST_MAP_PTR) {
 792                 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
 793                 *mapp = reg->map_ptr;
 794
 795         } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
 796                 /* bpf_map_xxx(..., map_ptr, ..., key) call:
 797                  * check that [key, key + map->key_size) are within
 798                  * stack limits and initialized
 799                  */
 800                 if (!*mapp) {
 801                         /* in function declaration map_ptr must come before
 802                          * map_key, so that it's verified and known before
 803                          * we have to check map_key here. Otherwise it means
 804                          * that kernel subsystem misconfigured verifier
 805                          */
 806                         verbose("invalid map_ptr to access map->key\n");
 807                         return -EACCES;
 808                 }
 809                 err = check_stack_boundary(env, regno, (*mapp)->key_size);
 810
 811         } else if (arg_type == ARG_PTR_TO_MAP_VALUE) {
 812                 /* bpf_map_xxx(..., map_ptr, ..., value) call:
 813                  * check [value, value + map->value_size) validity
 814                  */
 815                 if (!*mapp) {
 816                         /* kernel subsystem misconfigured verifier */
 817                         verbose("invalid map_ptr to access map->value\n");
 818                         return -EACCES;
 819                 }
 820                 err = check_stack_boundary(env, regno, (*mapp)->value_size);
 821
 822         } else if (arg_type == ARG_CONST_STACK_SIZE) {
 823                 /* bpf_xxx(..., buf, len) call will access 'len' bytes
 824                  * from stack pointer 'buf'. Check it
 825                  * note: regno == len, regno - 1 == buf
 826                  */
 827                 if (regno == 0) {
 828                         /* kernel subsystem misconfigured verifier */
 829                         verbose("ARG_CONST_STACK_SIZE cannot be first argument\n");
 830                         return -EACCES;
 831                 }
 832                 err = check_stack_boundary(env, regno - 1, reg->imm);
 833         }
 834
 835         return err;
 836 }
 837
 838 static int check_call(struct verifier_env *env, int func_id)
 839 {
 840         struct verifier_state *state = &env->cur_state;
 841         const struct bpf_func_proto *fn = NULL;
 842         struct reg_state *regs = state->regs;
 843         struct bpf_map *map = NULL;
 844         struct reg_state *reg;
 845         int i, err;
 846
 847         /* find function prototype */
 848         if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
 849                 verbose("invalid func %d\n", func_id);
 850                 return -EINVAL;
 851         }
 852
 853         if (env->prog->aux->ops->get_func_proto)
 854                 fn = env->prog->aux->ops->get_func_proto(func_id);
 855
 856         if (!fn) {
 857                 verbose("unknown func %d\n", func_id);
 858                 return -EINVAL;
 859         }
 860
 861         /* eBPF programs must be GPL compatible to use GPL-ed functions */
 862         if (!env->prog->aux->is_gpl_compatible && fn->gpl_only) {
 863                 verbose("cannot call GPL only function from proprietary program\n");
 864                 return -EINVAL;
 865         }
 866
 867         /* check args */
 868         err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &map);
 869         if (err)
 870                 return err;
 871         err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &map);
 872         if (err)
 873                 return err;
 874         err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &map);
 875         if (err)
 876                 return err;
 877         err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &map);
 878         if (err)
 879                 return err;
 880         err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &map);
 881         if (err)
 882                 return err;
 883
 884         /* reset caller saved regs */
 885         for (i = 0; i < CALLER_SAVED_REGS; i++) {
 886                 reg = regs + caller_saved[i];
 887                 reg->type = NOT_INIT;
 888                 reg->imm = 0;
 889         }
 890
 891         /* update return register */
 892         if (fn->ret_type == RET_INTEGER) {
 893                 regs[BPF_REG_0].type = UNKNOWN_VALUE;
 894         } else if (fn->ret_type == RET_VOID) {
 895                 regs[BPF_REG_0].type = NOT_INIT;
 896         } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) {
 897                 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
 898                 /* remember map_ptr, so that check_map_access()
 899                  * can check 'value_size' boundary of memory access
 900                  * to map element returned from bpf_map_lookup_elem()
 901                  */
 902                 if (map == NULL) {
 903                         verbose("kernel subsystem misconfigured verifier\n");
 904                         return -EINVAL;
 905                 }
 906                 regs[BPF_REG_0].map_ptr = map;
 907         } else {
 908                 verbose("unknown return type %d of func %d\n",
 909                         fn->ret_type, func_id);
 910                 return -EINVAL;
 911         }
 912         return 0;
 913 }
 914
 915 /* check validity of 32-bit and 64-bit arithmetic operations */
 916 static int check_alu_op(struct reg_state *regs, struct bpf_insn *insn)
 917 {
 918         u8 opcode = BPF_OP(insn->code);
 919         int err;
 920
 921         if (opcode == BPF_END || opcode == BPF_NEG) {
 922                 if (opcode == BPF_NEG) {
 923                         if (BPF_SRC(insn->code) != 0 ||
 924                             insn->src_reg != BPF_REG_0 ||
 925                             insn->off != 0 || insn->imm != 0) {
 926                                 verbose("BPF_NEG uses reserved fields\n");
 927                                 return -EINVAL;
 928                         }
 929                 } else {
 930                         if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
 931                             (insn->imm != 16 && insn->imm != 32 && insn->imm != 64)) {
 932                                 verbose("BPF_END uses reserved fields\n");
 933                                 return -EINVAL;
 934                         }
 935                 }
 936
 937                 /* check src operand */
 938                 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
 939                 if (err)
 940                         return err;
 941
 942                 /* check dest operand */
 943                 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
 944                 if (err)
 945                         return err;
 946
 947         } else if (opcode == BPF_MOV) {
 948
 949                 if (BPF_SRC(insn->code) == BPF_X) {
 950                         if (insn->imm != 0 || insn->off != 0) {
 951                                 verbose("BPF_MOV uses reserved fields\n");
 952                                 return -EINVAL;
 953                         }
 954
 955                         /* check src operand */
 956                         err = check_reg_arg(regs, insn->src_reg, SRC_OP);
 957                         if (err)
 958                                 return err;
 959                 } else {
 960                         if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
 961                                 verbose("BPF_MOV uses reserved fields\n");
 962                                 return -EINVAL;
 963                         }
 964                 }
 965
 966                 /* check dest operand */
 967                 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
 968                 if (err)
 969                         return err;
 970
 971                 if (BPF_SRC(insn->code) == BPF_X) {
 972                         if (BPF_CLASS(insn->code) == BPF_ALU64) {
 973                                 /* case: R1 = R2
 974                                  * copy register state to dest reg
 975                                  */
 976                                 regs[insn->dst_reg] = regs[insn->src_reg];
 977                         } else {
 978                                 regs[insn->dst_reg].type = UNKNOWN_VALUE;
 979                                 regs[insn->dst_reg].map_ptr = NULL;
 980                         }
 981                 } else {
 982                         /* case: R = imm
 983                          * remember the value we stored into this reg
 984                          */
 985                         regs[insn->dst_reg].type = CONST_IMM;
 986                         regs[insn->dst_reg].imm = insn->imm;
 987                 }
 988
 989         } else if (opcode > BPF_END) {
 990                 verbose("invalid BPF_ALU opcode %x\n", opcode);
 991                 return -EINVAL;
 992
 993         } else {        /* all other ALU ops: and, sub, xor, add, ... */
 994
 995                 bool stack_relative = false;
 996
 997                 if (BPF_SRC(insn->code) == BPF_X) {
 998                         if (insn->imm != 0 || insn->off != 0) {
 999                                 verbose("BPF_ALU uses reserved fields\n");
1000                                 return -EINVAL;
1001                         }
1002                         /* check src1 operand */
1003                         err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1004                         if (err)
1005                                 return err;
1006                 } else {
1007                         if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
1008                                 verbose("BPF_ALU uses reserved fields\n");
1009                                 return -EINVAL;
1010                         }
1011                 }
1012
1013                 /* check src2 operand */
1014                 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1015                 if (err)
1016                         return err;
1017
1018                 if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
1019                     BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
1020                         verbose("div by zero\n");
1021                         return -EINVAL;
1022                 }
1023
1024                 /* pattern match 'bpf_add Rx, imm' instruction */
1025                 if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
1026                     regs[insn->dst_reg].type == FRAME_PTR &&
1027                     BPF_SRC(insn->code) == BPF_K)
1028                         stack_relative = true;
1029
1030                 /* check dest operand */
1031                 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1032                 if (err)
1033                         return err;
1034
1035                 if (stack_relative) {
1036                         regs[insn->dst_reg].type = PTR_TO_STACK;
1037                         regs[insn->dst_reg].imm = insn->imm;
1038                 }
1039         }
1040
1041         return 0;
1042 }
1043
1044 static int check_cond_jmp_op(struct verifier_env *env,
1045                              struct bpf_insn *insn, int *insn_idx)
1046 {
1047         struct reg_state *regs = env->cur_state.regs;
1048         struct verifier_state *other_branch;
1049         u8 opcode = BPF_OP(insn->code);
1050         int err;
1051
1052         if (opcode > BPF_EXIT) {
1053                 verbose("invalid BPF_JMP opcode %x\n", opcode);
1054                 return -EINVAL;
1055         }
1056
1057         if (BPF_SRC(insn->code) == BPF_X) {
1058                 if (insn->imm != 0) {
1059                         verbose("BPF_JMP uses reserved fields\n");
1060                         return -EINVAL;
1061                 }
1062
1063                 /* check src1 operand */
1064                 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1065                 if (err)
1066                         return err;
1067         } else {
1068                 if (insn->src_reg != BPF_REG_0) {
1069                         verbose("BPF_JMP uses reserved fields\n");
1070                         return -EINVAL;
1071                 }
1072         }
1073
1074         /* check src2 operand */
1075         err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1076         if (err)
1077                 return err;
1078
1079         /* detect if R == 0 where R was initialized to zero earlier */
1080         if (BPF_SRC(insn->code) == BPF_K &&
1081             (opcode == BPF_JEQ || opcode == BPF_JNE) &&
1082             regs[insn->dst_reg].type == CONST_IMM &&
1083             regs[insn->dst_reg].imm == insn->imm) {
1084                 if (opcode == BPF_JEQ) {
1085                         /* if (imm == imm) goto pc+off;
1086                          * only follow the goto, ignore fall-through
1087                          */
1088                         *insn_idx += insn->off;
1089                         return 0;
1090                 } else {
1091                         /* if (imm != imm) goto pc+off;
1092                          * only follow fall-through branch, since
1093                          * that's where the program will go
1094                          */
1095                         return 0;
1096                 }
1097         }
1098
1099         other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx);
1100         if (!other_branch)
1101                 return -EFAULT;
1102
1103         /* detect if R == 0 where R is returned value from bpf_map_lookup_elem() */
1104         if (BPF_SRC(insn->code) == BPF_K &&
1105             insn->imm == 0 && (opcode == BPF_JEQ ||
1106                                opcode == BPF_JNE) &&
1107             regs[insn->dst_reg].type == PTR_TO_MAP_VALUE_OR_NULL) {
1108                 if (opcode == BPF_JEQ) {
1109                         /* next fallthrough insn can access memory via
1110                          * this register
1111                          */
1112                         regs[insn->dst_reg].type = PTR_TO_MAP_VALUE;
1113                         /* branch targer cannot access it, since reg == 0 */
1114                         other_branch->regs[insn->dst_reg].type = CONST_IMM;
1115                         other_branch->regs[insn->dst_reg].imm = 0;
1116                 } else {
1117                         other_branch->regs[insn->dst_reg].type = PTR_TO_MAP_VALUE;
1118                         regs[insn->dst_reg].type = CONST_IMM;
1119                         regs[insn->dst_reg].imm = 0;
1120                 }
1121         } else if (BPF_SRC(insn->code) == BPF_K &&
1122                    (opcode == BPF_JEQ || opcode == BPF_JNE)) {
1123
1124                 if (opcode == BPF_JEQ) {
1125                         /* detect if (R == imm) goto
1126                          * and in the target state recognize that R = imm
1127                          */
1128                         other_branch->regs[insn->dst_reg].type = CONST_IMM;
1129                         other_branch->regs[insn->dst_reg].imm = insn->imm;
1130                 } else {
1131                         /* detect if (R != imm) goto
1132                          * and in the fall-through state recognize that R = imm
1133                          */
1134                         regs[insn->dst_reg].type = CONST_IMM;
1135                         regs[insn->dst_reg].imm = insn->imm;
1136                 }
1137         }
1138         if (log_level)
1139                 print_verifier_state(env);
1140         return 0;
1141 }
1142
1143 /* return the map pointer stored inside BPF_LD_IMM64 instruction */
1144 static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
1145 {
1146         u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
1147
1148         return (struct bpf_map *) (unsigned long) imm64;
1149 }
1150
1151 /* verify BPF_LD_IMM64 instruction */
1152 static int check_ld_imm(struct verifier_env *env, struct bpf_insn *insn)
1153 {
1154         struct reg_state *regs = env->cur_state.regs;
1155         int err;
1156
1157         if (BPF_SIZE(insn->code) != BPF_DW) {
1158                 verbose("invalid BPF_LD_IMM insn\n");
1159                 return -EINVAL;
1160         }
1161         if (insn->off != 0) {
1162                 verbose("BPF_LD_IMM64 uses reserved fields\n");
1163                 return -EINVAL;
1164         }
1165
1166         err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1167         if (err)
1168                 return err;
1169
1170         if (insn->src_reg == 0)
1171                 /* generic move 64-bit immediate into a register */
1172                 return 0;
1173
1174         /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */
1175         BUG_ON(insn->src_reg != BPF_PSEUDO_MAP_FD);
1176
1177         regs[insn->dst_reg].type = CONST_PTR_TO_MAP;
1178         regs[insn->dst_reg].map_ptr = ld_imm64_to_map_ptr(insn);
1179         return 0;
1180 }
1181
1182 /* non-recursive DFS pseudo code
1183  * 1  procedure DFS-iterative(G,v):
1184  * 2      label v as discovered
1185  * 3      let S be a stack
1186  * 4      S.push(v)
1187  * 5      while S is not empty
1188  * 6            t <- S.pop()
1189  * 7            if t is what we're looking for:
1190  * 8                return t
1191  * 9            for all edges e in G.adjacentEdges(t) do
1192  * 10               if edge e is already labelled
1193  * 11                   continue with the next edge
1194  * 12               w <- G.adjacentVertex(t,e)
1195  * 13               if vertex w is not discovered and not explored
1196  * 14                   label e as tree-edge
1197  * 15                   label w as discovered
1198  * 16                   S.push(w)
1199  * 17                   continue at 5
1200  * 18               else if vertex w is discovered
1201  * 19                   label e as back-edge
1202  * 20               else
1203  * 21                   // vertex w is explored
1204  * 22                   label e as forward- or cross-edge
1205  * 23           label t as explored
1206  * 24           S.pop()
1207  *
1208  * convention:
1209  * 0x10 - discovered
1210  * 0x11 - discovered and fall-through edge labelled
1211  * 0x12 - discovered and fall-through and branch edges labelled
1212  * 0x20 - explored
1213  */
1214
1215 enum {
1216         DISCOVERED = 0x10,
1217         EXPLORED = 0x20,
1218         FALLTHROUGH = 1,
1219         BRANCH = 2,
1220 };
1221
1222 static int *insn_stack; /* stack of insns to process */
1223 static int cur_stack;   /* current stack index */
1224 static int *insn_state;
1225
1226 /* t, w, e - match pseudo-code above:
1227  * t - index of current instruction
1228  * w - next instruction
1229  * e - edge
1230  */
1231 static int push_insn(int t, int w, int e, struct verifier_env *env)
1232 {
1233         if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
1234                 return 0;
1235
1236         if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
1237                 return 0;
1238
1239         if (w < 0 || w >= env->prog->len) {
1240                 verbose("jump out of range from insn %d to %d\n", t, w);
1241                 return -EINVAL;
1242         }
1243
1244         if (insn_state[w] == 0) {
1245                 /* tree-edge */
1246                 insn_state[t] = DISCOVERED | e;
1247                 insn_state[w] = DISCOVERED;
1248                 if (cur_stack >= env->prog->len)
1249                         return -E2BIG;
1250                 insn_stack[cur_stack++] = w;
1251                 return 1;
1252         } else if ((insn_state[w] & 0xF0) == DISCOVERED) {
1253                 verbose("back-edge from insn %d to %d\n", t, w);
1254                 return -EINVAL;
1255         } else if (insn_state[w] == EXPLORED) {
1256                 /* forward- or cross-edge */
1257                 insn_state[t] = DISCOVERED | e;
1258         } else {
1259                 verbose("insn state internal bug\n");
1260                 return -EFAULT;
1261         }
1262         return 0;
1263 }
1264
1265 /* non-recursive depth-first-search to detect loops in BPF program
1266  * loop == back-edge in directed graph
1267  */
1268 static int check_cfg(struct verifier_env *env)
1269 {
1270         struct bpf_insn *insns = env->prog->insnsi;
1271         int insn_cnt = env->prog->len;
1272         int ret = 0;
1273         int i, t;
1274
1275         insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
1276         if (!insn_state)
1277                 return -ENOMEM;
1278
1279         insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
1280         if (!insn_stack) {
1281                 kfree(insn_state);
1282                 return -ENOMEM;
1283         }
1284
1285         insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */
1286         insn_stack[0] = 0; /* 0 is the first instruction */
1287         cur_stack = 1;
1288
1289 peek_stack:
1290         if (cur_stack == 0)
1291                 goto check_state;
1292         t = insn_stack[cur_stack - 1];
1293
1294         if (BPF_CLASS(insns[t].code) == BPF_JMP) {
1295                 u8 opcode = BPF_OP(insns[t].code);
1296
1297                 if (opcode == BPF_EXIT) {
1298                         goto mark_explored;
1299                 } else if (opcode == BPF_CALL) {
1300                         ret = push_insn(t, t + 1, FALLTHROUGH, env);
1301                         if (ret == 1)
1302                                 goto peek_stack;
1303                         else if (ret < 0)
1304                                 goto err_free;
1305                 } else if (opcode == BPF_JA) {
1306                         if (BPF_SRC(insns[t].code) != BPF_K) {
1307                                 ret = -EINVAL;
1308                                 goto err_free;
1309                         }
1310                         /* unconditional jump with single edge */
1311                         ret = push_insn(t, t + insns[t].off + 1,
1312                                         FALLTHROUGH, env);
1313                         if (ret == 1)
1314                                 goto peek_stack;
1315                         else if (ret < 0)
1316                                 goto err_free;
1317                 } else {
1318                         /* conditional jump with two edges */
1319                         ret = push_insn(t, t + 1, FALLTHROUGH, env);
1320                         if (ret == 1)
1321                                 goto peek_stack;
1322                         else if (ret < 0)
1323                                 goto err_free;
1324
1325                         ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
1326                         if (ret == 1)
1327                                 goto peek_stack;
1328                         else if (ret < 0)
1329                                 goto err_free;
1330                 }
1331         } else {
1332                 /* all other non-branch instructions with single
1333                  * fall-through edge
1334                  */
1335                 ret = push_insn(t, t + 1, FALLTHROUGH, env);
1336                 if (ret == 1)
1337                         goto peek_stack;
1338                 else if (ret < 0)
1339                         goto err_free;
1340         }
1341
1342 mark_explored:
1343         insn_state[t] = EXPLORED;
1344         if (cur_stack-- <= 0) {
1345                 verbose("pop stack internal bug\n");
1346                 ret = -EFAULT;
1347                 goto err_free;
1348         }
1349         goto peek_stack;
1350
1351 check_state:
1352         for (i = 0; i < insn_cnt; i++) {
1353                 if (insn_state[i] != EXPLORED) {
1354                         verbose("unreachable insn %d\n", i);
1355                         ret = -EINVAL;
1356                         goto err_free;
1357                 }
1358         }
1359         ret = 0; /* cfg looks good */
1360
1361 err_free:
1362         kfree(insn_state);
1363         kfree(insn_stack);
1364         return ret;
1365 }
1366
1367 static int do_check(struct verifier_env *env)
1368 {
1369         struct verifier_state *state = &env->cur_state;
1370         struct bpf_insn *insns = env->prog->insnsi;
1371         struct reg_state *regs = state->regs;
1372         int insn_cnt = env->prog->len;
1373         int insn_idx, prev_insn_idx = 0;
1374         int insn_processed = 0;
1375         bool do_print_state = false;
1376
1377         init_reg_state(regs);
1378         insn_idx = 0;
1379         for (;;) {
1380                 struct bpf_insn *insn;
1381                 u8 class;
1382                 int err;
1383
1384                 if (insn_idx >= insn_cnt) {
1385                         verbose("invalid insn idx %d insn_cnt %d\n",
1386                                 insn_idx, insn_cnt);
1387                         return -EFAULT;
1388                 }
1389
1390                 insn = &insns[insn_idx];
1391                 class = BPF_CLASS(insn->code);
1392
1393                 if (++insn_processed > 32768) {
1394                         verbose("BPF program is too large. Proccessed %d insn\n",
1395                                 insn_processed);
1396                         return -E2BIG;
1397                 }
1398
1399                 if (log_level && do_print_state) {
1400                         verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
1401                         print_verifier_state(env);
1402                         do_print_state = false;
1403                 }
1404
1405                 if (log_level) {
1406                         verbose("%d: ", insn_idx);
1407                         print_bpf_insn(insn);
1408                 }
1409
1410                 if (class == BPF_ALU || class == BPF_ALU64) {
1411                         err = check_alu_op(regs, insn);
1412                         if (err)
1413                                 return err;
1414
1415                 } else if (class == BPF_LDX) {
1416                         if (BPF_MODE(insn->code) != BPF_MEM ||
1417                             insn->imm != 0) {
1418                                 verbose("BPF_LDX uses reserved fields\n");
1419                                 return -EINVAL;
1420                         }
1421                         /* check src operand */
1422                         err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1423                         if (err)
1424                                 return err;
1425
1426                         err = check_reg_arg(regs, insn->dst_reg, DST_OP_NO_MARK);
1427                         if (err)
1428                                 return err;
1429
1430                         /* check that memory (src_reg + off) is readable,
1431                          * the state of dst_reg will be updated by this func
1432                          */
1433                         err = check_mem_access(env, insn->src_reg, insn->off,
1434                                                BPF_SIZE(insn->code), BPF_READ,
1435                                                insn->dst_reg);
1436                         if (err)
1437                                 return err;
1438
1439                 } else if (class == BPF_STX) {
1440                         if (BPF_MODE(insn->code) == BPF_XADD) {
1441                                 err = check_xadd(env, insn);
1442                                 if (err)
1443                                         return err;
1444                                 insn_idx++;
1445                                 continue;
1446                         }
1447
1448                         if (BPF_MODE(insn->code) != BPF_MEM ||
1449                             insn->imm != 0) {
1450                                 verbose("BPF_STX uses reserved fields\n");
1451                                 return -EINVAL;
1452                         }
1453                         /* check src1 operand */
1454                         err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1455                         if (err)
1456                                 return err;
1457                         /* check src2 operand */
1458                         err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1459                         if (err)
1460                                 return err;
1461
1462                         /* check that memory (dst_reg + off) is writeable */
1463                         err = check_mem_access(env, insn->dst_reg, insn->off,
1464                                                BPF_SIZE(insn->code), BPF_WRITE,
1465                                                insn->src_reg);
1466                         if (err)
1467                                 return err;
1468
1469                 } else if (class == BPF_ST) {
1470                         if (BPF_MODE(insn->code) != BPF_MEM ||
1471                             insn->src_reg != BPF_REG_0) {
1472                                 verbose("BPF_ST uses reserved fields\n");
1473                                 return -EINVAL;
1474                         }
1475                         /* check src operand */
1476                         err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1477                         if (err)
1478                                 return err;
1479
1480                         /* check that memory (dst_reg + off) is writeable */
1481                         err = check_mem_access(env, insn->dst_reg, insn->off,
1482                                                BPF_SIZE(insn->code), BPF_WRITE,
1483                                                -1);
1484                         if (err)
1485                                 return err;
1486
1487                 } else if (class == BPF_JMP) {
1488                         u8 opcode = BPF_OP(insn->code);
1489
1490                         if (opcode == BPF_CALL) {
1491                                 if (BPF_SRC(insn->code) != BPF_K ||
1492                                     insn->off != 0 ||
1493                                     insn->src_reg != BPF_REG_0 ||
1494                                     insn->dst_reg != BPF_REG_0) {
1495                                         verbose("BPF_CALL uses reserved fields\n");
1496                                         return -EINVAL;
1497                                 }
1498
1499                                 err = check_call(env, insn->imm);
1500                                 if (err)
1501                                         return err;
1502
1503                         } else if (opcode == BPF_JA) {
1504                                 if (BPF_SRC(insn->code) != BPF_K ||
1505                                     insn->imm != 0 ||
1506                                     insn->src_reg != BPF_REG_0 ||
1507                                     insn->dst_reg != BPF_REG_0) {
1508                                         verbose("BPF_JA uses reserved fields\n");
1509                                         return -EINVAL;
1510                                 }
1511
1512                                 insn_idx += insn->off + 1;
1513                                 continue;
1514
1515                         } else if (opcode == BPF_EXIT) {
1516                                 if (BPF_SRC(insn->code) != BPF_K ||
1517                                     insn->imm != 0 ||
1518                                     insn->src_reg != BPF_REG_0 ||
1519                                     insn->dst_reg != BPF_REG_0) {
1520                                         verbose("BPF_EXIT uses reserved fields\n");
1521                                         return -EINVAL;
1522                                 }
1523
1524                                 /* eBPF calling convetion is such that R0 is used
1525                                  * to return the value from eBPF program.
1526                                  * Make sure that it's readable at this time
1527                                  * of bpf_exit, which means that program wrote
1528                                  * something into it earlier
1529                                  */
1530                                 err = check_reg_arg(regs, BPF_REG_0, SRC_OP);
1531                                 if (err)
1532                                         return err;
1533
1534                                 insn_idx = pop_stack(env, &prev_insn_idx);
1535                                 if (insn_idx < 0) {
1536                                         break;
1537                                 } else {
1538                                         do_print_state = true;
1539                                         continue;
1540                                 }
1541                         } else {
1542                                 err = check_cond_jmp_op(env, insn, &insn_idx);
1543                                 if (err)
1544                                         return err;
1545                         }
1546                 } else if (class == BPF_LD) {
1547                         u8 mode = BPF_MODE(insn->code);
1548
1549                         if (mode == BPF_ABS || mode == BPF_IND) {
1550                                 verbose("LD_ABS is not supported yet\n");
1551                                 return -EINVAL;
1552                         } else if (mode == BPF_IMM) {
1553                                 err = check_ld_imm(env, insn);
1554                                 if (err)
1555                                         return err;
1556
1557                                 insn_idx++;
1558                         } else {
1559                                 verbose("invalid BPF_LD mode\n");
1560                                 return -EINVAL;
1561                         }
1562                 } else {
1563                         verbose("unknown insn class %d\n", class);
1564                         return -EINVAL;
1565                 }
1566
1567                 insn_idx++;
1568         }
1569
1570         return 0;
1571 }
1572
1573 /* look for pseudo eBPF instructions that access map FDs and
1574  * replace them with actual map pointers
1575  */
1576 static int replace_map_fd_with_map_ptr(struct verifier_env *env)
1577 {
1578         struct bpf_insn *insn = env->prog->insnsi;
1579         int insn_cnt = env->prog->len;
1580         int i, j;
1581
1582         for (i = 0; i < insn_cnt; i++, insn++) {
1583                 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
1584                         struct bpf_map *map;
1585                         struct fd f;
1586
1587                         if (i == insn_cnt - 1 || insn[1].code != 0 ||
1588                             insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
1589                             insn[1].off != 0) {
1590                                 verbose("invalid bpf_ld_imm64 insn\n");
1591                                 return -EINVAL;
1592                         }
1593
1594                         if (insn->src_reg == 0)
1595                                 /* valid generic load 64-bit imm */
1596                                 goto next_insn;
1597
1598                         if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
1599                                 verbose("unrecognized bpf_ld_imm64 insn\n");
1600                                 return -EINVAL;
1601                         }
1602
1603                         f = fdget(insn->imm);
1604
1605                         map = bpf_map_get(f);
1606                         if (IS_ERR(map)) {
1607                                 verbose("fd %d is not pointing to valid bpf_map\n",
1608                                         insn->imm);
1609                                 fdput(f);
1610                                 return PTR_ERR(map);
1611                         }
1612
1613                         /* store map pointer inside BPF_LD_IMM64 instruction */
1614                         insn[0].imm = (u32) (unsigned long) map;
1615                         insn[1].imm = ((u64) (unsigned long) map) >> 32;
1616
1617                         /* check whether we recorded this map already */
1618                         for (j = 0; j < env->used_map_cnt; j++)
1619                                 if (env->used_maps[j] == map) {
1620                                         fdput(f);
1621                                         goto next_insn;
1622                                 }
1623
1624                         if (env->used_map_cnt >= MAX_USED_MAPS) {
1625                                 fdput(f);
1626                                 return -E2BIG;
1627                         }
1628
1629                         /* remember this map */
1630                         env->used_maps[env->used_map_cnt++] = map;
1631
1632                         /* hold the map. If the program is rejected by verifier,
1633                          * the map will be released by release_maps() or it
1634                          * will be used by the valid program until it's unloaded
1635                          * and all maps are released in free_bpf_prog_info()
1636                          */
1637                         atomic_inc(&map->refcnt);
1638
1639                         fdput(f);
1640 next_insn:
1641                         insn++;
1642                         i++;
1643                 }
1644         }
1645
1646         /* now all pseudo BPF_LD_IMM64 instructions load valid
1647          * 'struct bpf_map *' into a register instead of user map_fd.
1648          * These pointers will be used later by verifier to validate map access.
1649          */
1650         return 0;
1651 }
1652
1653 /* drop refcnt of maps used by the rejected program */
1654 static void release_maps(struct verifier_env *env)
1655 {
1656         int i;
1657
1658         for (i = 0; i < env->used_map_cnt; i++)
1659                 bpf_map_put(env->used_maps[i]);
1660 }
1661
1662 /* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */
1663 static void convert_pseudo_ld_imm64(struct verifier_env *env)
1664 {
1665         struct bpf_insn *insn = env->prog->insnsi;
1666         int insn_cnt = env->prog->len;
1667         int i;
1668
1669         for (i = 0; i < insn_cnt; i++, insn++)
1670                 if (insn->code == (BPF_LD | BPF_IMM | BPF_DW))
1671                         insn->src_reg = 0;
1672 }
1673
1674 int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)
1675 {
1676         char __user *log_ubuf = NULL;
1677         struct verifier_env *env;
1678         int ret = -EINVAL;
1679
1680         if (prog->len <= 0 || prog->len > BPF_MAXINSNS)
1681                 return -E2BIG;
1682
1683         /* 'struct verifier_env' can be global, but since it's not small,
1684          * allocate/free it every time bpf_check() is called
1685          */
1686         env = kzalloc(sizeof(struct verifier_env), GFP_KERNEL);
1687         if (!env)
1688                 return -ENOMEM;
1689
1690         env->prog = prog;
1691
1692         /* grab the mutex to protect few globals used by verifier */
1693         mutex_lock(&bpf_verifier_lock);
1694
1695         if (attr->log_level || attr->log_buf || attr->log_size) {
1696                 /* user requested verbose verifier output
1697                  * and supplied buffer to store the verification trace
1698                  */
1699                 log_level = attr->log_level;
1700                 log_ubuf = (char __user *) (unsigned long) attr->log_buf;
1701                 log_size = attr->log_size;
1702                 log_len = 0;
1703
1704                 ret = -EINVAL;
1705                 /* log_* values have to be sane */
1706                 if (log_size < 128 || log_size > UINT_MAX >> 8 ||
1707                     log_level == 0 || log_ubuf == NULL)
1708                         goto free_env;
1709
1710                 ret = -ENOMEM;
1711                 log_buf = vmalloc(log_size);
1712                 if (!log_buf)
1713                         goto free_env;
1714         } else {
1715                 log_level = 0;
1716         }
1717
1718         ret = replace_map_fd_with_map_ptr(env);
1719         if (ret < 0)
1720                 goto skip_full_check;
1721
1722         ret = check_cfg(env);
1723         if (ret < 0)
1724                 goto skip_full_check;
1725
1726         ret = do_check(env);
1727
1728 skip_full_check:
1729         while (pop_stack(env, NULL) >= 0);
1730
1731         if (log_level && log_len >= log_size - 1) {
1732                 BUG_ON(log_len >= log_size);
1733                 /* verifier log exceeded user supplied buffer */
1734                 ret = -ENOSPC;
1735                 /* fall through to return what was recorded */
1736         }
1737
1738         /* copy verifier log back to user space including trailing zero */
1739         if (log_level && copy_to_user(log_ubuf, log_buf, log_len + 1) != 0) {
1740                 ret = -EFAULT;
1741                 goto free_log_buf;
1742         }
1743
1744         if (ret == 0 && env->used_map_cnt) {
1745                 /* if program passed verifier, update used_maps in bpf_prog_info */
1746                 prog->aux->used_maps = kmalloc_array(env->used_map_cnt,
1747                                                      sizeof(env->used_maps[0]),
1748                                                      GFP_KERNEL);
1749
1750                 if (!prog->aux->used_maps) {
1751                         ret = -ENOMEM;
1752                         goto free_log_buf;
1753                 }
1754
1755                 memcpy(prog->aux->used_maps, env->used_maps,
1756                        sizeof(env->used_maps[0]) * env->used_map_cnt);
1757                 prog->aux->used_map_cnt = env->used_map_cnt;
1758
1759                 /* program is valid. Convert pseudo bpf_ld_imm64 into generic
1760                  * bpf_ld_imm64 instructions
1761                  */
1762                 convert_pseudo_ld_imm64(env);
1763         }
1764
1765 free_log_buf:
1766         if (log_level)
1767                 vfree(log_buf);
1768 free_env:
1769         if (!prog->aux->used_maps)
1770                 /* if we didn't copy map pointers into bpf_prog_info, release
1771                  * them now. Otherwise free_bpf_prog_info() will release them.
1772                  */
1773                 release_maps(env);
1774         kfree(env);
1775         mutex_unlock(&bpf_verifier_lock);
1776         return ret;
1777 }