Merge git://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf
[muen/linux.git] / kernel / bpf / verifier.c
1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
2  * Copyright (c) 2016 Facebook
3  * Copyright (c) 2018 Covalent IO, Inc. http://covalent.io
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of version 2 of the GNU General Public
7  * License as published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * General Public License for more details.
13  */
14 #include <uapi/linux/btf.h>
15 #include <linux/kernel.h>
16 #include <linux/types.h>
17 #include <linux/slab.h>
18 #include <linux/bpf.h>
19 #include <linux/btf.h>
20 #include <linux/bpf_verifier.h>
21 #include <linux/filter.h>
22 #include <net/netlink.h>
23 #include <linux/file.h>
24 #include <linux/vmalloc.h>
25 #include <linux/stringify.h>
26 #include <linux/bsearch.h>
27 #include <linux/sort.h>
28 #include <linux/perf_event.h>
29 #include <linux/ctype.h>
30
31 #include "disasm.h"
32
33 static const struct bpf_verifier_ops * const bpf_verifier_ops[] = {
34 #define BPF_PROG_TYPE(_id, _name) \
35         [_id] = & _name ## _verifier_ops,
36 #define BPF_MAP_TYPE(_id, _ops)
37 #include <linux/bpf_types.h>
38 #undef BPF_PROG_TYPE
39 #undef BPF_MAP_TYPE
40 };
41
42 /* bpf_check() is a static code analyzer that walks eBPF program
43  * instruction by instruction and updates register/stack state.
44  * All paths of conditional branches are analyzed until 'bpf_exit' insn.
45  *
46  * The first pass is depth-first-search to check that the program is a DAG.
47  * It rejects the following programs:
48  * - larger than BPF_MAXINSNS insns
49  * - if loop is present (detected via back-edge)
50  * - unreachable insns exist (shouldn't be a forest. program = one function)
51  * - out of bounds or malformed jumps
52  * The second pass is all possible path descent from the 1st insn.
53  * Since it's analyzing all pathes through the program, the length of the
54  * analysis is limited to 64k insn, which may be hit even if total number of
55  * insn is less then 4K, but there are too many branches that change stack/regs.
56  * Number of 'branches to be analyzed' is limited to 1k
57  *
58  * On entry to each instruction, each register has a type, and the instruction
59  * changes the types of the registers depending on instruction semantics.
60  * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is
61  * copied to R1.
62  *
63  * All registers are 64-bit.
64  * R0 - return register
65  * R1-R5 argument passing registers
66  * R6-R9 callee saved registers
67  * R10 - frame pointer read-only
68  *
69  * At the start of BPF program the register R1 contains a pointer to bpf_context
70  * and has type PTR_TO_CTX.
71  *
72  * Verifier tracks arithmetic operations on pointers in case:
73  *    BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
74  *    BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20),
75  * 1st insn copies R10 (which has FRAME_PTR) type into R1
76  * and 2nd arithmetic instruction is pattern matched to recognize
77  * that it wants to construct a pointer to some element within stack.
78  * So after 2nd insn, the register R1 has type PTR_TO_STACK
79  * (and -20 constant is saved for further stack bounds checking).
80  * Meaning that this reg is a pointer to stack plus known immediate constant.
81  *
82  * Most of the time the registers have SCALAR_VALUE type, which
83  * means the register has some value, but it's not a valid pointer.
84  * (like pointer plus pointer becomes SCALAR_VALUE type)
85  *
86  * When verifier sees load or store instructions the type of base register
87  * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, PTR_TO_STACK, PTR_TO_SOCKET. These are
88  * four pointer types recognized by check_mem_access() function.
89  *
90  * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value'
91  * and the range of [ptr, ptr + map's value_size) is accessible.
92  *
93  * registers used to pass values to function calls are checked against
94  * function argument constraints.
95  *
96  * ARG_PTR_TO_MAP_KEY is one of such argument constraints.
97  * It means that the register type passed to this function must be
98  * PTR_TO_STACK and it will be used inside the function as
99  * 'pointer to map element key'
100  *
101  * For example the argument constraints for bpf_map_lookup_elem():
102  *   .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
103  *   .arg1_type = ARG_CONST_MAP_PTR,
104  *   .arg2_type = ARG_PTR_TO_MAP_KEY,
105  *
106  * ret_type says that this function returns 'pointer to map elem value or null'
107  * function expects 1st argument to be a const pointer to 'struct bpf_map' and
108  * 2nd argument should be a pointer to stack, which will be used inside
109  * the helper function as a pointer to map element key.
110  *
111  * On the kernel side the helper function looks like:
112  * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
113  * {
114  *    struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
115  *    void *key = (void *) (unsigned long) r2;
116  *    void *value;
117  *
118  *    here kernel can access 'key' and 'map' pointers safely, knowing that
119  *    [key, key + map->key_size) bytes are valid and were initialized on
120  *    the stack of eBPF program.
121  * }
122  *
123  * Corresponding eBPF program may look like:
124  *    BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),  // after this insn R2 type is FRAME_PTR
125  *    BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK
126  *    BPF_LD_MAP_FD(BPF_REG_1, map_fd),      // after this insn R1 type is CONST_PTR_TO_MAP
127  *    BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
128  * here verifier looks at prototype of map_lookup_elem() and sees:
129  * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok,
130  * Now verifier knows that this map has key of R1->map_ptr->key_size bytes
131  *
132  * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far,
133  * Now verifier checks that [R2, R2 + map's key_size) are within stack limits
134  * and were initialized prior to this call.
135  * If it's ok, then verifier allows this BPF_CALL insn and looks at
136  * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets
137  * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function
138  * returns ether pointer to map value or NULL.
139  *
140  * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off'
141  * insn, the register holding that pointer in the true branch changes state to
142  * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false
143  * branch. See check_cond_jmp_op().
144  *
145  * After the call R0 is set to return type of the function and registers R1-R5
146  * are set to NOT_INIT to indicate that they are no longer readable.
147  *
148  * The following reference types represent a potential reference to a kernel
149  * resource which, after first being allocated, must be checked and freed by
150  * the BPF program:
151  * - PTR_TO_SOCKET_OR_NULL, PTR_TO_SOCKET
152  *
153  * When the verifier sees a helper call return a reference type, it allocates a
154  * pointer id for the reference and stores it in the current function state.
155  * Similar to the way that PTR_TO_MAP_VALUE_OR_NULL is converted into
156  * PTR_TO_MAP_VALUE, PTR_TO_SOCKET_OR_NULL becomes PTR_TO_SOCKET when the type
157  * passes through a NULL-check conditional. For the branch wherein the state is
158  * changed to CONST_IMM, the verifier releases the reference.
159  *
160  * For each helper function that allocates a reference, such as
161  * bpf_sk_lookup_tcp(), there is a corresponding release function, such as
162  * bpf_sk_release(). When a reference type passes into the release function,
163  * the verifier also releases the reference. If any unchecked or unreleased
164  * reference remains at the end of the program, the verifier rejects it.
165  */
166
167 /* verifier_state + insn_idx are pushed to stack when branch is encountered */
168 struct bpf_verifier_stack_elem {
169         /* verifer state is 'st'
170          * before processing instruction 'insn_idx'
171          * and after processing instruction 'prev_insn_idx'
172          */
173         struct bpf_verifier_state st;
174         int insn_idx;
175         int prev_insn_idx;
176         struct bpf_verifier_stack_elem *next;
177 };
178
179 #define BPF_COMPLEXITY_LIMIT_INSNS      131072
180 #define BPF_COMPLEXITY_LIMIT_STACK      1024
181 #define BPF_COMPLEXITY_LIMIT_STATES     64
182
183 #define BPF_MAP_PTR_UNPRIV      1UL
184 #define BPF_MAP_PTR_POISON      ((void *)((0xeB9FUL << 1) +     \
185                                           POISON_POINTER_DELTA))
186 #define BPF_MAP_PTR(X)          ((struct bpf_map *)((X) & ~BPF_MAP_PTR_UNPRIV))
187
188 static bool bpf_map_ptr_poisoned(const struct bpf_insn_aux_data *aux)
189 {
190         return BPF_MAP_PTR(aux->map_state) == BPF_MAP_PTR_POISON;
191 }
192
193 static bool bpf_map_ptr_unpriv(const struct bpf_insn_aux_data *aux)
194 {
195         return aux->map_state & BPF_MAP_PTR_UNPRIV;
196 }
197
198 static void bpf_map_ptr_store(struct bpf_insn_aux_data *aux,
199                               const struct bpf_map *map, bool unpriv)
200 {
201         BUILD_BUG_ON((unsigned long)BPF_MAP_PTR_POISON & BPF_MAP_PTR_UNPRIV);
202         unpriv |= bpf_map_ptr_unpriv(aux);
203         aux->map_state = (unsigned long)map |
204                          (unpriv ? BPF_MAP_PTR_UNPRIV : 0UL);
205 }
206
207 struct bpf_call_arg_meta {
208         struct bpf_map *map_ptr;
209         bool raw_mode;
210         bool pkt_access;
211         int regno;
212         int access_size;
213         s64 msize_smax_value;
214         u64 msize_umax_value;
215         int ref_obj_id;
216         int func_id;
217 };
218
219 static DEFINE_MUTEX(bpf_verifier_lock);
220
221 static const struct bpf_line_info *
222 find_linfo(const struct bpf_verifier_env *env, u32 insn_off)
223 {
224         const struct bpf_line_info *linfo;
225         const struct bpf_prog *prog;
226         u32 i, nr_linfo;
227
228         prog = env->prog;
229         nr_linfo = prog->aux->nr_linfo;
230
231         if (!nr_linfo || insn_off >= prog->len)
232                 return NULL;
233
234         linfo = prog->aux->linfo;
235         for (i = 1; i < nr_linfo; i++)
236                 if (insn_off < linfo[i].insn_off)
237                         break;
238
239         return &linfo[i - 1];
240 }
241
242 void bpf_verifier_vlog(struct bpf_verifier_log *log, const char *fmt,
243                        va_list args)
244 {
245         unsigned int n;
246
247         n = vscnprintf(log->kbuf, BPF_VERIFIER_TMP_LOG_SIZE, fmt, args);
248
249         WARN_ONCE(n >= BPF_VERIFIER_TMP_LOG_SIZE - 1,
250                   "verifier log line truncated - local buffer too short\n");
251
252         n = min(log->len_total - log->len_used - 1, n);
253         log->kbuf[n] = '\0';
254
255         if (!copy_to_user(log->ubuf + log->len_used, log->kbuf, n + 1))
256                 log->len_used += n;
257         else
258                 log->ubuf = NULL;
259 }
260
261 /* log_level controls verbosity level of eBPF verifier.
262  * bpf_verifier_log_write() is used to dump the verification trace to the log,
263  * so the user can figure out what's wrong with the program
264  */
265 __printf(2, 3) void bpf_verifier_log_write(struct bpf_verifier_env *env,
266                                            const char *fmt, ...)
267 {
268         va_list args;
269
270         if (!bpf_verifier_log_needed(&env->log))
271                 return;
272
273         va_start(args, fmt);
274         bpf_verifier_vlog(&env->log, fmt, args);
275         va_end(args);
276 }
277 EXPORT_SYMBOL_GPL(bpf_verifier_log_write);
278
279 __printf(2, 3) static void verbose(void *private_data, const char *fmt, ...)
280 {
281         struct bpf_verifier_env *env = private_data;
282         va_list args;
283
284         if (!bpf_verifier_log_needed(&env->log))
285                 return;
286
287         va_start(args, fmt);
288         bpf_verifier_vlog(&env->log, fmt, args);
289         va_end(args);
290 }
291
292 static const char *ltrim(const char *s)
293 {
294         while (isspace(*s))
295                 s++;
296
297         return s;
298 }
299
300 __printf(3, 4) static void verbose_linfo(struct bpf_verifier_env *env,
301                                          u32 insn_off,
302                                          const char *prefix_fmt, ...)
303 {
304         const struct bpf_line_info *linfo;
305
306         if (!bpf_verifier_log_needed(&env->log))
307                 return;
308
309         linfo = find_linfo(env, insn_off);
310         if (!linfo || linfo == env->prev_linfo)
311                 return;
312
313         if (prefix_fmt) {
314                 va_list args;
315
316                 va_start(args, prefix_fmt);
317                 bpf_verifier_vlog(&env->log, prefix_fmt, args);
318                 va_end(args);
319         }
320
321         verbose(env, "%s\n",
322                 ltrim(btf_name_by_offset(env->prog->aux->btf,
323                                          linfo->line_off)));
324
325         env->prev_linfo = linfo;
326 }
327
328 static bool type_is_pkt_pointer(enum bpf_reg_type type)
329 {
330         return type == PTR_TO_PACKET ||
331                type == PTR_TO_PACKET_META;
332 }
333
334 static bool type_is_sk_pointer(enum bpf_reg_type type)
335 {
336         return type == PTR_TO_SOCKET ||
337                 type == PTR_TO_SOCK_COMMON ||
338                 type == PTR_TO_TCP_SOCK;
339 }
340
341 static bool reg_type_may_be_null(enum bpf_reg_type type)
342 {
343         return type == PTR_TO_MAP_VALUE_OR_NULL ||
344                type == PTR_TO_SOCKET_OR_NULL ||
345                type == PTR_TO_SOCK_COMMON_OR_NULL ||
346                type == PTR_TO_TCP_SOCK_OR_NULL;
347 }
348
349 static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg)
350 {
351         return reg->type == PTR_TO_MAP_VALUE &&
352                 map_value_has_spin_lock(reg->map_ptr);
353 }
354
355 static bool reg_type_may_be_refcounted_or_null(enum bpf_reg_type type)
356 {
357         return type == PTR_TO_SOCKET ||
358                 type == PTR_TO_SOCKET_OR_NULL ||
359                 type == PTR_TO_TCP_SOCK ||
360                 type == PTR_TO_TCP_SOCK_OR_NULL;
361 }
362
363 static bool arg_type_may_be_refcounted(enum bpf_arg_type type)
364 {
365         return type == ARG_PTR_TO_SOCK_COMMON;
366 }
367
368 /* Determine whether the function releases some resources allocated by another
369  * function call. The first reference type argument will be assumed to be
370  * released by release_reference().
371  */
372 static bool is_release_function(enum bpf_func_id func_id)
373 {
374         return func_id == BPF_FUNC_sk_release;
375 }
376
377 static bool is_acquire_function(enum bpf_func_id func_id)
378 {
379         return func_id == BPF_FUNC_sk_lookup_tcp ||
380                 func_id == BPF_FUNC_sk_lookup_udp;
381 }
382
383 static bool is_ptr_cast_function(enum bpf_func_id func_id)
384 {
385         return func_id == BPF_FUNC_tcp_sock ||
386                 func_id == BPF_FUNC_sk_fullsock;
387 }
388
389 /* string representation of 'enum bpf_reg_type' */
390 static const char * const reg_type_str[] = {
391         [NOT_INIT]              = "?",
392         [SCALAR_VALUE]          = "inv",
393         [PTR_TO_CTX]            = "ctx",
394         [CONST_PTR_TO_MAP]      = "map_ptr",
395         [PTR_TO_MAP_VALUE]      = "map_value",
396         [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null",
397         [PTR_TO_STACK]          = "fp",
398         [PTR_TO_PACKET]         = "pkt",
399         [PTR_TO_PACKET_META]    = "pkt_meta",
400         [PTR_TO_PACKET_END]     = "pkt_end",
401         [PTR_TO_FLOW_KEYS]      = "flow_keys",
402         [PTR_TO_SOCKET]         = "sock",
403         [PTR_TO_SOCKET_OR_NULL] = "sock_or_null",
404         [PTR_TO_SOCK_COMMON]    = "sock_common",
405         [PTR_TO_SOCK_COMMON_OR_NULL] = "sock_common_or_null",
406         [PTR_TO_TCP_SOCK]       = "tcp_sock",
407         [PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
408 };
409
410 static char slot_type_char[] = {
411         [STACK_INVALID] = '?',
412         [STACK_SPILL]   = 'r',
413         [STACK_MISC]    = 'm',
414         [STACK_ZERO]    = '0',
415 };
416
417 static void print_liveness(struct bpf_verifier_env *env,
418                            enum bpf_reg_liveness live)
419 {
420         if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN | REG_LIVE_DONE))
421             verbose(env, "_");
422         if (live & REG_LIVE_READ)
423                 verbose(env, "r");
424         if (live & REG_LIVE_WRITTEN)
425                 verbose(env, "w");
426         if (live & REG_LIVE_DONE)
427                 verbose(env, "D");
428 }
429
430 static struct bpf_func_state *func(struct bpf_verifier_env *env,
431                                    const struct bpf_reg_state *reg)
432 {
433         struct bpf_verifier_state *cur = env->cur_state;
434
435         return cur->frame[reg->frameno];
436 }
437
438 static void print_verifier_state(struct bpf_verifier_env *env,
439                                  const struct bpf_func_state *state)
440 {
441         const struct bpf_reg_state *reg;
442         enum bpf_reg_type t;
443         int i;
444
445         if (state->frameno)
446                 verbose(env, " frame%d:", state->frameno);
447         for (i = 0; i < MAX_BPF_REG; i++) {
448                 reg = &state->regs[i];
449                 t = reg->type;
450                 if (t == NOT_INIT)
451                         continue;
452                 verbose(env, " R%d", i);
453                 print_liveness(env, reg->live);
454                 verbose(env, "=%s", reg_type_str[t]);
455                 if ((t == SCALAR_VALUE || t == PTR_TO_STACK) &&
456                     tnum_is_const(reg->var_off)) {
457                         /* reg->off should be 0 for SCALAR_VALUE */
458                         verbose(env, "%lld", reg->var_off.value + reg->off);
459                         if (t == PTR_TO_STACK)
460                                 verbose(env, ",call_%d", func(env, reg)->callsite);
461                 } else {
462                         verbose(env, "(id=%d", reg->id);
463                         if (reg_type_may_be_refcounted_or_null(t))
464                                 verbose(env, ",ref_obj_id=%d", reg->ref_obj_id);
465                         if (t != SCALAR_VALUE)
466                                 verbose(env, ",off=%d", reg->off);
467                         if (type_is_pkt_pointer(t))
468                                 verbose(env, ",r=%d", reg->range);
469                         else if (t == CONST_PTR_TO_MAP ||
470                                  t == PTR_TO_MAP_VALUE ||
471                                  t == PTR_TO_MAP_VALUE_OR_NULL)
472                                 verbose(env, ",ks=%d,vs=%d",
473                                         reg->map_ptr->key_size,
474                                         reg->map_ptr->value_size);
475                         if (tnum_is_const(reg->var_off)) {
476                                 /* Typically an immediate SCALAR_VALUE, but
477                                  * could be a pointer whose offset is too big
478                                  * for reg->off
479                                  */
480                                 verbose(env, ",imm=%llx", reg->var_off.value);
481                         } else {
482                                 if (reg->smin_value != reg->umin_value &&
483                                     reg->smin_value != S64_MIN)
484                                         verbose(env, ",smin_value=%lld",
485                                                 (long long)reg->smin_value);
486                                 if (reg->smax_value != reg->umax_value &&
487                                     reg->smax_value != S64_MAX)
488                                         verbose(env, ",smax_value=%lld",
489                                                 (long long)reg->smax_value);
490                                 if (reg->umin_value != 0)
491                                         verbose(env, ",umin_value=%llu",
492                                                 (unsigned long long)reg->umin_value);
493                                 if (reg->umax_value != U64_MAX)
494                                         verbose(env, ",umax_value=%llu",
495                                                 (unsigned long long)reg->umax_value);
496                                 if (!tnum_is_unknown(reg->var_off)) {
497                                         char tn_buf[48];
498
499                                         tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
500                                         verbose(env, ",var_off=%s", tn_buf);
501                                 }
502                         }
503                         verbose(env, ")");
504                 }
505         }
506         for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
507                 char types_buf[BPF_REG_SIZE + 1];
508                 bool valid = false;
509                 int j;
510
511                 for (j = 0; j < BPF_REG_SIZE; j++) {
512                         if (state->stack[i].slot_type[j] != STACK_INVALID)
513                                 valid = true;
514                         types_buf[j] = slot_type_char[
515                                         state->stack[i].slot_type[j]];
516                 }
517                 types_buf[BPF_REG_SIZE] = 0;
518                 if (!valid)
519                         continue;
520                 verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE);
521                 print_liveness(env, state->stack[i].spilled_ptr.live);
522                 if (state->stack[i].slot_type[0] == STACK_SPILL)
523                         verbose(env, "=%s",
524                                 reg_type_str[state->stack[i].spilled_ptr.type]);
525                 else
526                         verbose(env, "=%s", types_buf);
527         }
528         if (state->acquired_refs && state->refs[0].id) {
529                 verbose(env, " refs=%d", state->refs[0].id);
530                 for (i = 1; i < state->acquired_refs; i++)
531                         if (state->refs[i].id)
532                                 verbose(env, ",%d", state->refs[i].id);
533         }
534         verbose(env, "\n");
535 }
536
537 #define COPY_STATE_FN(NAME, COUNT, FIELD, SIZE)                         \
538 static int copy_##NAME##_state(struct bpf_func_state *dst,              \
539                                const struct bpf_func_state *src)        \
540 {                                                                       \
541         if (!src->FIELD)                                                \
542                 return 0;                                               \
543         if (WARN_ON_ONCE(dst->COUNT < src->COUNT)) {                    \
544                 /* internal bug, make state invalid to reject the program */ \
545                 memset(dst, 0, sizeof(*dst));                           \
546                 return -EFAULT;                                         \
547         }                                                               \
548         memcpy(dst->FIELD, src->FIELD,                                  \
549                sizeof(*src->FIELD) * (src->COUNT / SIZE));              \
550         return 0;                                                       \
551 }
552 /* copy_reference_state() */
553 COPY_STATE_FN(reference, acquired_refs, refs, 1)
554 /* copy_stack_state() */
555 COPY_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE)
556 #undef COPY_STATE_FN
557
558 #define REALLOC_STATE_FN(NAME, COUNT, FIELD, SIZE)                      \
559 static int realloc_##NAME##_state(struct bpf_func_state *state, int size, \
560                                   bool copy_old)                        \
561 {                                                                       \
562         u32 old_size = state->COUNT;                                    \
563         struct bpf_##NAME##_state *new_##FIELD;                         \
564         int slot = size / SIZE;                                         \
565                                                                         \
566         if (size <= old_size || !size) {                                \
567                 if (copy_old)                                           \
568                         return 0;                                       \
569                 state->COUNT = slot * SIZE;                             \
570                 if (!size && old_size) {                                \
571                         kfree(state->FIELD);                            \
572                         state->FIELD = NULL;                            \
573                 }                                                       \
574                 return 0;                                               \
575         }                                                               \
576         new_##FIELD = kmalloc_array(slot, sizeof(struct bpf_##NAME##_state), \
577                                     GFP_KERNEL);                        \
578         if (!new_##FIELD)                                               \
579                 return -ENOMEM;                                         \
580         if (copy_old) {                                                 \
581                 if (state->FIELD)                                       \
582                         memcpy(new_##FIELD, state->FIELD,               \
583                                sizeof(*new_##FIELD) * (old_size / SIZE)); \
584                 memset(new_##FIELD + old_size / SIZE, 0,                \
585                        sizeof(*new_##FIELD) * (size - old_size) / SIZE); \
586         }                                                               \
587         state->COUNT = slot * SIZE;                                     \
588         kfree(state->FIELD);                                            \
589         state->FIELD = new_##FIELD;                                     \
590         return 0;                                                       \
591 }
592 /* realloc_reference_state() */
593 REALLOC_STATE_FN(reference, acquired_refs, refs, 1)
594 /* realloc_stack_state() */
595 REALLOC_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE)
596 #undef REALLOC_STATE_FN
597
598 /* do_check() starts with zero-sized stack in struct bpf_verifier_state to
599  * make it consume minimal amount of memory. check_stack_write() access from
600  * the program calls into realloc_func_state() to grow the stack size.
601  * Note there is a non-zero 'parent' pointer inside bpf_verifier_state
602  * which realloc_stack_state() copies over. It points to previous
603  * bpf_verifier_state which is never reallocated.
604  */
605 static int realloc_func_state(struct bpf_func_state *state, int stack_size,
606                               int refs_size, bool copy_old)
607 {
608         int err = realloc_reference_state(state, refs_size, copy_old);
609         if (err)
610                 return err;
611         return realloc_stack_state(state, stack_size, copy_old);
612 }
613
614 /* Acquire a pointer id from the env and update the state->refs to include
615  * this new pointer reference.
616  * On success, returns a valid pointer id to associate with the register
617  * On failure, returns a negative errno.
618  */
619 static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx)
620 {
621         struct bpf_func_state *state = cur_func(env);
622         int new_ofs = state->acquired_refs;
623         int id, err;
624
625         err = realloc_reference_state(state, state->acquired_refs + 1, true);
626         if (err)
627                 return err;
628         id = ++env->id_gen;
629         state->refs[new_ofs].id = id;
630         state->refs[new_ofs].insn_idx = insn_idx;
631
632         return id;
633 }
634
635 /* release function corresponding to acquire_reference_state(). Idempotent. */
636 static int release_reference_state(struct bpf_func_state *state, int ptr_id)
637 {
638         int i, last_idx;
639
640         last_idx = state->acquired_refs - 1;
641         for (i = 0; i < state->acquired_refs; i++) {
642                 if (state->refs[i].id == ptr_id) {
643                         if (last_idx && i != last_idx)
644                                 memcpy(&state->refs[i], &state->refs[last_idx],
645                                        sizeof(*state->refs));
646                         memset(&state->refs[last_idx], 0, sizeof(*state->refs));
647                         state->acquired_refs--;
648                         return 0;
649                 }
650         }
651         return -EINVAL;
652 }
653
654 static int transfer_reference_state(struct bpf_func_state *dst,
655                                     struct bpf_func_state *src)
656 {
657         int err = realloc_reference_state(dst, src->acquired_refs, false);
658         if (err)
659                 return err;
660         err = copy_reference_state(dst, src);
661         if (err)
662                 return err;
663         return 0;
664 }
665
666 static void free_func_state(struct bpf_func_state *state)
667 {
668         if (!state)
669                 return;
670         kfree(state->refs);
671         kfree(state->stack);
672         kfree(state);
673 }
674
675 static void free_verifier_state(struct bpf_verifier_state *state,
676                                 bool free_self)
677 {
678         int i;
679
680         for (i = 0; i <= state->curframe; i++) {
681                 free_func_state(state->frame[i]);
682                 state->frame[i] = NULL;
683         }
684         if (free_self)
685                 kfree(state);
686 }
687
688 /* copy verifier state from src to dst growing dst stack space
689  * when necessary to accommodate larger src stack
690  */
691 static int copy_func_state(struct bpf_func_state *dst,
692                            const struct bpf_func_state *src)
693 {
694         int err;
695
696         err = realloc_func_state(dst, src->allocated_stack, src->acquired_refs,
697                                  false);
698         if (err)
699                 return err;
700         memcpy(dst, src, offsetof(struct bpf_func_state, acquired_refs));
701         err = copy_reference_state(dst, src);
702         if (err)
703                 return err;
704         return copy_stack_state(dst, src);
705 }
706
707 static int copy_verifier_state(struct bpf_verifier_state *dst_state,
708                                const struct bpf_verifier_state *src)
709 {
710         struct bpf_func_state *dst;
711         int i, err;
712
713         /* if dst has more stack frames then src frame, free them */
714         for (i = src->curframe + 1; i <= dst_state->curframe; i++) {
715                 free_func_state(dst_state->frame[i]);
716                 dst_state->frame[i] = NULL;
717         }
718         dst_state->speculative = src->speculative;
719         dst_state->curframe = src->curframe;
720         dst_state->active_spin_lock = src->active_spin_lock;
721         for (i = 0; i <= src->curframe; i++) {
722                 dst = dst_state->frame[i];
723                 if (!dst) {
724                         dst = kzalloc(sizeof(*dst), GFP_KERNEL);
725                         if (!dst)
726                                 return -ENOMEM;
727                         dst_state->frame[i] = dst;
728                 }
729                 err = copy_func_state(dst, src->frame[i]);
730                 if (err)
731                         return err;
732         }
733         return 0;
734 }
735
736 static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx,
737                      int *insn_idx)
738 {
739         struct bpf_verifier_state *cur = env->cur_state;
740         struct bpf_verifier_stack_elem *elem, *head = env->head;
741         int err;
742
743         if (env->head == NULL)
744                 return -ENOENT;
745
746         if (cur) {
747                 err = copy_verifier_state(cur, &head->st);
748                 if (err)
749                         return err;
750         }
751         if (insn_idx)
752                 *insn_idx = head->insn_idx;
753         if (prev_insn_idx)
754                 *prev_insn_idx = head->prev_insn_idx;
755         elem = head->next;
756         free_verifier_state(&head->st, false);
757         kfree(head);
758         env->head = elem;
759         env->stack_size--;
760         return 0;
761 }
762
763 static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env,
764                                              int insn_idx, int prev_insn_idx,
765                                              bool speculative)
766 {
767         struct bpf_verifier_state *cur = env->cur_state;
768         struct bpf_verifier_stack_elem *elem;
769         int err;
770
771         elem = kzalloc(sizeof(struct bpf_verifier_stack_elem), GFP_KERNEL);
772         if (!elem)
773                 goto err;
774
775         elem->insn_idx = insn_idx;
776         elem->prev_insn_idx = prev_insn_idx;
777         elem->next = env->head;
778         env->head = elem;
779         env->stack_size++;
780         err = copy_verifier_state(&elem->st, cur);
781         if (err)
782                 goto err;
783         elem->st.speculative |= speculative;
784         if (env->stack_size > BPF_COMPLEXITY_LIMIT_STACK) {
785                 verbose(env, "BPF program is too complex\n");
786                 goto err;
787         }
788         return &elem->st;
789 err:
790         free_verifier_state(env->cur_state, true);
791         env->cur_state = NULL;
792         /* pop all elements and return */
793         while (!pop_stack(env, NULL, NULL));
794         return NULL;
795 }
796
797 #define CALLER_SAVED_REGS 6
798 static const int caller_saved[CALLER_SAVED_REGS] = {
799         BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
800 };
801
802 static void __mark_reg_not_init(struct bpf_reg_state *reg);
803
804 /* Mark the unknown part of a register (variable offset or scalar value) as
805  * known to have the value @imm.
806  */
807 static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
808 {
809         /* Clear id, off, and union(map_ptr, range) */
810         memset(((u8 *)reg) + sizeof(reg->type), 0,
811                offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
812         reg->var_off = tnum_const(imm);
813         reg->smin_value = (s64)imm;
814         reg->smax_value = (s64)imm;
815         reg->umin_value = imm;
816         reg->umax_value = imm;
817 }
818
819 /* Mark the 'variable offset' part of a register as zero.  This should be
820  * used only on registers holding a pointer type.
821  */
822 static void __mark_reg_known_zero(struct bpf_reg_state *reg)
823 {
824         __mark_reg_known(reg, 0);
825 }
826
827 static void __mark_reg_const_zero(struct bpf_reg_state *reg)
828 {
829         __mark_reg_known(reg, 0);
830         reg->type = SCALAR_VALUE;
831 }
832
833 static void mark_reg_known_zero(struct bpf_verifier_env *env,
834                                 struct bpf_reg_state *regs, u32 regno)
835 {
836         if (WARN_ON(regno >= MAX_BPF_REG)) {
837                 verbose(env, "mark_reg_known_zero(regs, %u)\n", regno);
838                 /* Something bad happened, let's kill all regs */
839                 for (regno = 0; regno < MAX_BPF_REG; regno++)
840                         __mark_reg_not_init(regs + regno);
841                 return;
842         }
843         __mark_reg_known_zero(regs + regno);
844 }
845
846 static bool reg_is_pkt_pointer(const struct bpf_reg_state *reg)
847 {
848         return type_is_pkt_pointer(reg->type);
849 }
850
851 static bool reg_is_pkt_pointer_any(const struct bpf_reg_state *reg)
852 {
853         return reg_is_pkt_pointer(reg) ||
854                reg->type == PTR_TO_PACKET_END;
855 }
856
857 /* Unmodified PTR_TO_PACKET[_META,_END] register from ctx access. */
858 static bool reg_is_init_pkt_pointer(const struct bpf_reg_state *reg,
859                                     enum bpf_reg_type which)
860 {
861         /* The register can already have a range from prior markings.
862          * This is fine as long as it hasn't been advanced from its
863          * origin.
864          */
865         return reg->type == which &&
866                reg->id == 0 &&
867                reg->off == 0 &&
868                tnum_equals_const(reg->var_off, 0);
869 }
870
871 /* Attempts to improve min/max values based on var_off information */
872 static void __update_reg_bounds(struct bpf_reg_state *reg)
873 {
874         /* min signed is max(sign bit) | min(other bits) */
875         reg->smin_value = max_t(s64, reg->smin_value,
876                                 reg->var_off.value | (reg->var_off.mask & S64_MIN));
877         /* max signed is min(sign bit) | max(other bits) */
878         reg->smax_value = min_t(s64, reg->smax_value,
879                                 reg->var_off.value | (reg->var_off.mask & S64_MAX));
880         reg->umin_value = max(reg->umin_value, reg->var_off.value);
881         reg->umax_value = min(reg->umax_value,
882                               reg->var_off.value | reg->var_off.mask);
883 }
884
885 /* Uses signed min/max values to inform unsigned, and vice-versa */
886 static void __reg_deduce_bounds(struct bpf_reg_state *reg)
887 {
888         /* Learn sign from signed bounds.
889          * If we cannot cross the sign boundary, then signed and unsigned bounds
890          * are the same, so combine.  This works even in the negative case, e.g.
891          * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff.
892          */
893         if (reg->smin_value >= 0 || reg->smax_value < 0) {
894                 reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value,
895                                                           reg->umin_value);
896                 reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value,
897                                                           reg->umax_value);
898                 return;
899         }
900         /* Learn sign from unsigned bounds.  Signed bounds cross the sign
901          * boundary, so we must be careful.
902          */
903         if ((s64)reg->umax_value >= 0) {
904                 /* Positive.  We can't learn anything from the smin, but smax
905                  * is positive, hence safe.
906                  */
907                 reg->smin_value = reg->umin_value;
908                 reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value,
909                                                           reg->umax_value);
910         } else if ((s64)reg->umin_value < 0) {
911                 /* Negative.  We can't learn anything from the smax, but smin
912                  * is negative, hence safe.
913                  */
914                 reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value,
915                                                           reg->umin_value);
916                 reg->smax_value = reg->umax_value;
917         }
918 }
919
920 /* Attempts to improve var_off based on unsigned min/max information */
921 static void __reg_bound_offset(struct bpf_reg_state *reg)
922 {
923         reg->var_off = tnum_intersect(reg->var_off,
924                                       tnum_range(reg->umin_value,
925                                                  reg->umax_value));
926 }
927
928 /* Reset the min/max bounds of a register */
929 static void __mark_reg_unbounded(struct bpf_reg_state *reg)
930 {
931         reg->smin_value = S64_MIN;
932         reg->smax_value = S64_MAX;
933         reg->umin_value = 0;
934         reg->umax_value = U64_MAX;
935 }
936
937 /* Mark a register as having a completely unknown (scalar) value. */
938 static void __mark_reg_unknown(struct bpf_reg_state *reg)
939 {
940         /*
941          * Clear type, id, off, and union(map_ptr, range) and
942          * padding between 'type' and union
943          */
944         memset(reg, 0, offsetof(struct bpf_reg_state, var_off));
945         reg->type = SCALAR_VALUE;
946         reg->var_off = tnum_unknown;
947         reg->frameno = 0;
948         __mark_reg_unbounded(reg);
949 }
950
951 static void mark_reg_unknown(struct bpf_verifier_env *env,
952                              struct bpf_reg_state *regs, u32 regno)
953 {
954         if (WARN_ON(regno >= MAX_BPF_REG)) {
955                 verbose(env, "mark_reg_unknown(regs, %u)\n", regno);
956                 /* Something bad happened, let's kill all regs except FP */
957                 for (regno = 0; regno < BPF_REG_FP; regno++)
958                         __mark_reg_not_init(regs + regno);
959                 return;
960         }
961         __mark_reg_unknown(regs + regno);
962 }
963
964 static void __mark_reg_not_init(struct bpf_reg_state *reg)
965 {
966         __mark_reg_unknown(reg);
967         reg->type = NOT_INIT;
968 }
969
970 static void mark_reg_not_init(struct bpf_verifier_env *env,
971                               struct bpf_reg_state *regs, u32 regno)
972 {
973         if (WARN_ON(regno >= MAX_BPF_REG)) {
974                 verbose(env, "mark_reg_not_init(regs, %u)\n", regno);
975                 /* Something bad happened, let's kill all regs except FP */
976                 for (regno = 0; regno < BPF_REG_FP; regno++)
977                         __mark_reg_not_init(regs + regno);
978                 return;
979         }
980         __mark_reg_not_init(regs + regno);
981 }
982
983 static void init_reg_state(struct bpf_verifier_env *env,
984                            struct bpf_func_state *state)
985 {
986         struct bpf_reg_state *regs = state->regs;
987         int i;
988
989         for (i = 0; i < MAX_BPF_REG; i++) {
990                 mark_reg_not_init(env, regs, i);
991                 regs[i].live = REG_LIVE_NONE;
992                 regs[i].parent = NULL;
993         }
994
995         /* frame pointer */
996         regs[BPF_REG_FP].type = PTR_TO_STACK;
997         mark_reg_known_zero(env, regs, BPF_REG_FP);
998         regs[BPF_REG_FP].frameno = state->frameno;
999
1000         /* 1st arg to a function */
1001         regs[BPF_REG_1].type = PTR_TO_CTX;
1002         mark_reg_known_zero(env, regs, BPF_REG_1);
1003 }
1004
1005 #define BPF_MAIN_FUNC (-1)
1006 static void init_func_state(struct bpf_verifier_env *env,
1007                             struct bpf_func_state *state,
1008                             int callsite, int frameno, int subprogno)
1009 {
1010         state->callsite = callsite;
1011         state->frameno = frameno;
1012         state->subprogno = subprogno;
1013         init_reg_state(env, state);
1014 }
1015
1016 enum reg_arg_type {
1017         SRC_OP,         /* register is used as source operand */
1018         DST_OP,         /* register is used as destination operand */
1019         DST_OP_NO_MARK  /* same as above, check only, don't mark */
1020 };
1021
1022 static int cmp_subprogs(const void *a, const void *b)
1023 {
1024         return ((struct bpf_subprog_info *)a)->start -
1025                ((struct bpf_subprog_info *)b)->start;
1026 }
1027
1028 static int find_subprog(struct bpf_verifier_env *env, int off)
1029 {
1030         struct bpf_subprog_info *p;
1031
1032         p = bsearch(&off, env->subprog_info, env->subprog_cnt,
1033                     sizeof(env->subprog_info[0]), cmp_subprogs);
1034         if (!p)
1035                 return -ENOENT;
1036         return p - env->subprog_info;
1037
1038 }
1039
1040 static int add_subprog(struct bpf_verifier_env *env, int off)
1041 {
1042         int insn_cnt = env->prog->len;
1043         int ret;
1044
1045         if (off >= insn_cnt || off < 0) {
1046                 verbose(env, "call to invalid destination\n");
1047                 return -EINVAL;
1048         }
1049         ret = find_subprog(env, off);
1050         if (ret >= 0)
1051                 return 0;
1052         if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
1053                 verbose(env, "too many subprograms\n");
1054                 return -E2BIG;
1055         }
1056         env->subprog_info[env->subprog_cnt++].start = off;
1057         sort(env->subprog_info, env->subprog_cnt,
1058              sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
1059         return 0;
1060 }
1061
1062 static int check_subprogs(struct bpf_verifier_env *env)
1063 {
1064         int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
1065         struct bpf_subprog_info *subprog = env->subprog_info;
1066         struct bpf_insn *insn = env->prog->insnsi;
1067         int insn_cnt = env->prog->len;
1068
1069         /* Add entry function. */
1070         ret = add_subprog(env, 0);
1071         if (ret < 0)
1072                 return ret;
1073
1074         /* determine subprog starts. The end is one before the next starts */
1075         for (i = 0; i < insn_cnt; i++) {
1076                 if (insn[i].code != (BPF_JMP | BPF_CALL))
1077                         continue;
1078                 if (insn[i].src_reg != BPF_PSEUDO_CALL)
1079                         continue;
1080                 if (!env->allow_ptr_leaks) {
1081                         verbose(env, "function calls to other bpf functions are allowed for root only\n");
1082                         return -EPERM;
1083                 }
1084                 ret = add_subprog(env, i + insn[i].imm + 1);
1085                 if (ret < 0)
1086                         return ret;
1087         }
1088
1089         /* Add a fake 'exit' subprog which could simplify subprog iteration
1090          * logic. 'subprog_cnt' should not be increased.
1091          */
1092         subprog[env->subprog_cnt].start = insn_cnt;
1093
1094         if (env->log.level > 1)
1095                 for (i = 0; i < env->subprog_cnt; i++)
1096                         verbose(env, "func#%d @%d\n", i, subprog[i].start);
1097
1098         /* now check that all jumps are within the same subprog */
1099         subprog_start = subprog[cur_subprog].start;
1100         subprog_end = subprog[cur_subprog + 1].start;
1101         for (i = 0; i < insn_cnt; i++) {
1102                 u8 code = insn[i].code;
1103
1104                 if (BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32)
1105                         goto next;
1106                 if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
1107                         goto next;
1108                 off = i + insn[i].off + 1;
1109                 if (off < subprog_start || off >= subprog_end) {
1110                         verbose(env, "jump out of range from insn %d to %d\n", i, off);
1111                         return -EINVAL;
1112                 }
1113 next:
1114                 if (i == subprog_end - 1) {
1115                         /* to avoid fall-through from one subprog into another
1116                          * the last insn of the subprog should be either exit
1117                          * or unconditional jump back
1118                          */
1119                         if (code != (BPF_JMP | BPF_EXIT) &&
1120                             code != (BPF_JMP | BPF_JA)) {
1121                                 verbose(env, "last insn is not an exit or jmp\n");
1122                                 return -EINVAL;
1123                         }
1124                         subprog_start = subprog_end;
1125                         cur_subprog++;
1126                         if (cur_subprog < env->subprog_cnt)
1127                                 subprog_end = subprog[cur_subprog + 1].start;
1128                 }
1129         }
1130         return 0;
1131 }
1132
1133 /* Parentage chain of this register (or stack slot) should take care of all
1134  * issues like callee-saved registers, stack slot allocation time, etc.
1135  */
1136 static int mark_reg_read(struct bpf_verifier_env *env,
1137                          const struct bpf_reg_state *state,
1138                          struct bpf_reg_state *parent)
1139 {
1140         bool writes = parent == state->parent; /* Observe write marks */
1141
1142         while (parent) {
1143                 /* if read wasn't screened by an earlier write ... */
1144                 if (writes && state->live & REG_LIVE_WRITTEN)
1145                         break;
1146                 if (parent->live & REG_LIVE_DONE) {
1147                         verbose(env, "verifier BUG type %s var_off %lld off %d\n",
1148                                 reg_type_str[parent->type],
1149                                 parent->var_off.value, parent->off);
1150                         return -EFAULT;
1151                 }
1152                 /* ... then we depend on parent's value */
1153                 parent->live |= REG_LIVE_READ;
1154                 state = parent;
1155                 parent = state->parent;
1156                 writes = true;
1157         }
1158         return 0;
1159 }
1160
1161 static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
1162                          enum reg_arg_type t)
1163 {
1164         struct bpf_verifier_state *vstate = env->cur_state;
1165         struct bpf_func_state *state = vstate->frame[vstate->curframe];
1166         struct bpf_reg_state *regs = state->regs;
1167
1168         if (regno >= MAX_BPF_REG) {
1169                 verbose(env, "R%d is invalid\n", regno);
1170                 return -EINVAL;
1171         }
1172
1173         if (t == SRC_OP) {
1174                 /* check whether register used as source operand can be read */
1175                 if (regs[regno].type == NOT_INIT) {
1176                         verbose(env, "R%d !read_ok\n", regno);
1177                         return -EACCES;
1178                 }
1179                 /* We don't need to worry about FP liveness because it's read-only */
1180                 if (regno != BPF_REG_FP)
1181                         return mark_reg_read(env, &regs[regno],
1182                                              regs[regno].parent);
1183         } else {
1184                 /* check whether register used as dest operand can be written to */
1185                 if (regno == BPF_REG_FP) {
1186                         verbose(env, "frame pointer is read only\n");
1187                         return -EACCES;
1188                 }
1189                 regs[regno].live |= REG_LIVE_WRITTEN;
1190                 if (t == DST_OP)
1191                         mark_reg_unknown(env, regs, regno);
1192         }
1193         return 0;
1194 }
1195
1196 static bool is_spillable_regtype(enum bpf_reg_type type)
1197 {
1198         switch (type) {
1199         case PTR_TO_MAP_VALUE:
1200         case PTR_TO_MAP_VALUE_OR_NULL:
1201         case PTR_TO_STACK:
1202         case PTR_TO_CTX:
1203         case PTR_TO_PACKET:
1204         case PTR_TO_PACKET_META:
1205         case PTR_TO_PACKET_END:
1206         case PTR_TO_FLOW_KEYS:
1207         case CONST_PTR_TO_MAP:
1208         case PTR_TO_SOCKET:
1209         case PTR_TO_SOCKET_OR_NULL:
1210         case PTR_TO_SOCK_COMMON:
1211         case PTR_TO_SOCK_COMMON_OR_NULL:
1212         case PTR_TO_TCP_SOCK:
1213         case PTR_TO_TCP_SOCK_OR_NULL:
1214                 return true;
1215         default:
1216                 return false;
1217         }
1218 }
1219
1220 /* Does this register contain a constant zero? */
1221 static bool register_is_null(struct bpf_reg_state *reg)
1222 {
1223         return reg->type == SCALAR_VALUE && tnum_equals_const(reg->var_off, 0);
1224 }
1225
1226 /* check_stack_read/write functions track spill/fill of registers,
1227  * stack boundary and alignment are checked in check_mem_access()
1228  */
1229 static int check_stack_write(struct bpf_verifier_env *env,
1230                              struct bpf_func_state *state, /* func where register points to */
1231                              int off, int size, int value_regno, int insn_idx)
1232 {
1233         struct bpf_func_state *cur; /* state of the current function */
1234         int i, slot = -off - 1, spi = slot / BPF_REG_SIZE, err;
1235         enum bpf_reg_type type;
1236
1237         err = realloc_func_state(state, round_up(slot + 1, BPF_REG_SIZE),
1238                                  state->acquired_refs, true);
1239         if (err)
1240                 return err;
1241         /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
1242          * so it's aligned access and [off, off + size) are within stack limits
1243          */
1244         if (!env->allow_ptr_leaks &&
1245             state->stack[spi].slot_type[0] == STACK_SPILL &&
1246             size != BPF_REG_SIZE) {
1247                 verbose(env, "attempt to corrupt spilled pointer on stack\n");
1248                 return -EACCES;
1249         }
1250
1251         cur = env->cur_state->frame[env->cur_state->curframe];
1252         if (value_regno >= 0 &&
1253             is_spillable_regtype((type = cur->regs[value_regno].type))) {
1254
1255                 /* register containing pointer is being spilled into stack */
1256                 if (size != BPF_REG_SIZE) {
1257                         verbose(env, "invalid size of register spill\n");
1258                         return -EACCES;
1259                 }
1260
1261                 if (state != cur && type == PTR_TO_STACK) {
1262                         verbose(env, "cannot spill pointers to stack into stack frame of the caller\n");
1263                         return -EINVAL;
1264                 }
1265
1266                 /* save register state */
1267                 state->stack[spi].spilled_ptr = cur->regs[value_regno];
1268                 state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
1269
1270                 for (i = 0; i < BPF_REG_SIZE; i++) {
1271                         if (state->stack[spi].slot_type[i] == STACK_MISC &&
1272                             !env->allow_ptr_leaks) {
1273                                 int *poff = &env->insn_aux_data[insn_idx].sanitize_stack_off;
1274                                 int soff = (-spi - 1) * BPF_REG_SIZE;
1275
1276                                 /* detected reuse of integer stack slot with a pointer
1277                                  * which means either llvm is reusing stack slot or
1278                                  * an attacker is trying to exploit CVE-2018-3639
1279                                  * (speculative store bypass)
1280                                  * Have to sanitize that slot with preemptive
1281                                  * store of zero.
1282                                  */
1283                                 if (*poff && *poff != soff) {
1284                                         /* disallow programs where single insn stores
1285                                          * into two different stack slots, since verifier
1286                                          * cannot sanitize them
1287                                          */
1288                                         verbose(env,
1289                                                 "insn %d cannot access two stack slots fp%d and fp%d",
1290                                                 insn_idx, *poff, soff);
1291                                         return -EINVAL;
1292                                 }
1293                                 *poff = soff;
1294                         }
1295                         state->stack[spi].slot_type[i] = STACK_SPILL;
1296                 }
1297         } else {
1298                 u8 type = STACK_MISC;
1299
1300                 /* regular write of data into stack destroys any spilled ptr */
1301                 state->stack[spi].spilled_ptr.type = NOT_INIT;
1302                 /* Mark slots as STACK_MISC if they belonged to spilled ptr. */
1303                 if (state->stack[spi].slot_type[0] == STACK_SPILL)
1304                         for (i = 0; i < BPF_REG_SIZE; i++)
1305                                 state->stack[spi].slot_type[i] = STACK_MISC;
1306
1307                 /* only mark the slot as written if all 8 bytes were written
1308                  * otherwise read propagation may incorrectly stop too soon
1309                  * when stack slots are partially written.
1310                  * This heuristic means that read propagation will be
1311                  * conservative, since it will add reg_live_read marks
1312                  * to stack slots all the way to first state when programs
1313                  * writes+reads less than 8 bytes
1314                  */
1315                 if (size == BPF_REG_SIZE)
1316                         state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
1317
1318                 /* when we zero initialize stack slots mark them as such */
1319                 if (value_regno >= 0 &&
1320                     register_is_null(&cur->regs[value_regno]))
1321                         type = STACK_ZERO;
1322
1323                 /* Mark slots affected by this stack write. */
1324                 for (i = 0; i < size; i++)
1325                         state->stack[spi].slot_type[(slot - i) % BPF_REG_SIZE] =
1326                                 type;
1327         }
1328         return 0;
1329 }
1330
1331 static int check_stack_read(struct bpf_verifier_env *env,
1332                             struct bpf_func_state *reg_state /* func where register points to */,
1333                             int off, int size, int value_regno)
1334 {
1335         struct bpf_verifier_state *vstate = env->cur_state;
1336         struct bpf_func_state *state = vstate->frame[vstate->curframe];
1337         int i, slot = -off - 1, spi = slot / BPF_REG_SIZE;
1338         u8 *stype;
1339
1340         if (reg_state->allocated_stack <= slot) {
1341                 verbose(env, "invalid read from stack off %d+0 size %d\n",
1342                         off, size);
1343                 return -EACCES;
1344         }
1345         stype = reg_state->stack[spi].slot_type;
1346
1347         if (stype[0] == STACK_SPILL) {
1348                 if (size != BPF_REG_SIZE) {
1349                         verbose(env, "invalid size of register spill\n");
1350                         return -EACCES;
1351                 }
1352                 for (i = 1; i < BPF_REG_SIZE; i++) {
1353                         if (stype[(slot - i) % BPF_REG_SIZE] != STACK_SPILL) {
1354                                 verbose(env, "corrupted spill memory\n");
1355                                 return -EACCES;
1356                         }
1357                 }
1358
1359                 if (value_regno >= 0) {
1360                         /* restore register state from stack */
1361                         state->regs[value_regno] = reg_state->stack[spi].spilled_ptr;
1362                         /* mark reg as written since spilled pointer state likely
1363                          * has its liveness marks cleared by is_state_visited()
1364                          * which resets stack/reg liveness for state transitions
1365                          */
1366                         state->regs[value_regno].live |= REG_LIVE_WRITTEN;
1367                 }
1368                 mark_reg_read(env, &reg_state->stack[spi].spilled_ptr,
1369                               reg_state->stack[spi].spilled_ptr.parent);
1370                 return 0;
1371         } else {
1372                 int zeros = 0;
1373
1374                 for (i = 0; i < size; i++) {
1375                         if (stype[(slot - i) % BPF_REG_SIZE] == STACK_MISC)
1376                                 continue;
1377                         if (stype[(slot - i) % BPF_REG_SIZE] == STACK_ZERO) {
1378                                 zeros++;
1379                                 continue;
1380                         }
1381                         verbose(env, "invalid read from stack off %d+%d size %d\n",
1382                                 off, i, size);
1383                         return -EACCES;
1384                 }
1385                 mark_reg_read(env, &reg_state->stack[spi].spilled_ptr,
1386                               reg_state->stack[spi].spilled_ptr.parent);
1387                 if (value_regno >= 0) {
1388                         if (zeros == size) {
1389                                 /* any size read into register is zero extended,
1390                                  * so the whole register == const_zero
1391                                  */
1392                                 __mark_reg_const_zero(&state->regs[value_regno]);
1393                         } else {
1394                                 /* have read misc data from the stack */
1395                                 mark_reg_unknown(env, state->regs, value_regno);
1396                         }
1397                         state->regs[value_regno].live |= REG_LIVE_WRITTEN;
1398                 }
1399                 return 0;
1400         }
1401 }
1402
1403 static int check_stack_access(struct bpf_verifier_env *env,
1404                               const struct bpf_reg_state *reg,
1405                               int off, int size)
1406 {
1407         /* Stack accesses must be at a fixed offset, so that we
1408          * can determine what type of data were returned. See
1409          * check_stack_read().
1410          */
1411         if (!tnum_is_const(reg->var_off)) {
1412                 char tn_buf[48];
1413
1414                 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1415                 verbose(env, "variable stack access var_off=%s off=%d size=%d",
1416                         tn_buf, off, size);
1417                 return -EACCES;
1418         }
1419
1420         if (off >= 0 || off < -MAX_BPF_STACK) {
1421                 verbose(env, "invalid stack off=%d size=%d\n", off, size);
1422                 return -EACCES;
1423         }
1424
1425         return 0;
1426 }
1427
1428 /* check read/write into map element returned by bpf_map_lookup_elem() */
1429 static int __check_map_access(struct bpf_verifier_env *env, u32 regno, int off,
1430                               int size, bool zero_size_allowed)
1431 {
1432         struct bpf_reg_state *regs = cur_regs(env);
1433         struct bpf_map *map = regs[regno].map_ptr;
1434
1435         if (off < 0 || size < 0 || (size == 0 && !zero_size_allowed) ||
1436             off + size > map->value_size) {
1437                 verbose(env, "invalid access to map value, value_size=%d off=%d size=%d\n",
1438                         map->value_size, off, size);
1439                 return -EACCES;
1440         }
1441         return 0;
1442 }
1443
1444 /* check read/write into a map element with possible variable offset */
1445 static int check_map_access(struct bpf_verifier_env *env, u32 regno,
1446                             int off, int size, bool zero_size_allowed)
1447 {
1448         struct bpf_verifier_state *vstate = env->cur_state;
1449         struct bpf_func_state *state = vstate->frame[vstate->curframe];
1450         struct bpf_reg_state *reg = &state->regs[regno];
1451         int err;
1452
1453         /* We may have adjusted the register to this map value, so we
1454          * need to try adding each of min_value and max_value to off
1455          * to make sure our theoretical access will be safe.
1456          */
1457         if (env->log.level)
1458                 print_verifier_state(env, state);
1459
1460         /* The minimum value is only important with signed
1461          * comparisons where we can't assume the floor of a
1462          * value is 0.  If we are using signed variables for our
1463          * index'es we need to make sure that whatever we use
1464          * will have a set floor within our range.
1465          */
1466         if (reg->smin_value < 0 &&
1467             (reg->smin_value == S64_MIN ||
1468              (off + reg->smin_value != (s64)(s32)(off + reg->smin_value)) ||
1469               reg->smin_value + off < 0)) {
1470                 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
1471                         regno);
1472                 return -EACCES;
1473         }
1474         err = __check_map_access(env, regno, reg->smin_value + off, size,
1475                                  zero_size_allowed);
1476         if (err) {
1477                 verbose(env, "R%d min value is outside of the array range\n",
1478                         regno);
1479                 return err;
1480         }
1481
1482         /* If we haven't set a max value then we need to bail since we can't be
1483          * sure we won't do bad things.
1484          * If reg->umax_value + off could overflow, treat that as unbounded too.
1485          */
1486         if (reg->umax_value >= BPF_MAX_VAR_OFF) {
1487                 verbose(env, "R%d unbounded memory access, make sure to bounds check any array access into a map\n",
1488                         regno);
1489                 return -EACCES;
1490         }
1491         err = __check_map_access(env, regno, reg->umax_value + off, size,
1492                                  zero_size_allowed);
1493         if (err)
1494                 verbose(env, "R%d max value is outside of the array range\n",
1495                         regno);
1496
1497         if (map_value_has_spin_lock(reg->map_ptr)) {
1498                 u32 lock = reg->map_ptr->spin_lock_off;
1499
1500                 /* if any part of struct bpf_spin_lock can be touched by
1501                  * load/store reject this program.
1502                  * To check that [x1, x2) overlaps with [y1, y2)
1503                  * it is sufficient to check x1 < y2 && y1 < x2.
1504                  */
1505                 if (reg->smin_value + off < lock + sizeof(struct bpf_spin_lock) &&
1506                      lock < reg->umax_value + off + size) {
1507                         verbose(env, "bpf_spin_lock cannot be accessed directly by load/store\n");
1508                         return -EACCES;
1509                 }
1510         }
1511         return err;
1512 }
1513
1514 #define MAX_PACKET_OFF 0xffff
1515
1516 static bool may_access_direct_pkt_data(struct bpf_verifier_env *env,
1517                                        const struct bpf_call_arg_meta *meta,
1518                                        enum bpf_access_type t)
1519 {
1520         switch (env->prog->type) {
1521         /* Program types only with direct read access go here! */
1522         case BPF_PROG_TYPE_LWT_IN:
1523         case BPF_PROG_TYPE_LWT_OUT:
1524         case BPF_PROG_TYPE_LWT_SEG6LOCAL:
1525         case BPF_PROG_TYPE_SK_REUSEPORT:
1526         case BPF_PROG_TYPE_FLOW_DISSECTOR:
1527         case BPF_PROG_TYPE_CGROUP_SKB:
1528                 if (t == BPF_WRITE)
1529                         return false;
1530                 /* fallthrough */
1531
1532         /* Program types with direct read + write access go here! */
1533         case BPF_PROG_TYPE_SCHED_CLS:
1534         case BPF_PROG_TYPE_SCHED_ACT:
1535         case BPF_PROG_TYPE_XDP:
1536         case BPF_PROG_TYPE_LWT_XMIT:
1537         case BPF_PROG_TYPE_SK_SKB:
1538         case BPF_PROG_TYPE_SK_MSG:
1539                 if (meta)
1540                         return meta->pkt_access;
1541
1542                 env->seen_direct_write = true;
1543                 return true;
1544         default:
1545                 return false;
1546         }
1547 }
1548
1549 static int __check_packet_access(struct bpf_verifier_env *env, u32 regno,
1550                                  int off, int size, bool zero_size_allowed)
1551 {
1552         struct bpf_reg_state *regs = cur_regs(env);
1553         struct bpf_reg_state *reg = &regs[regno];
1554
1555         if (off < 0 || size < 0 || (size == 0 && !zero_size_allowed) ||
1556             (u64)off + size > reg->range) {
1557                 verbose(env, "invalid access to packet, off=%d size=%d, R%d(id=%d,off=%d,r=%d)\n",
1558                         off, size, regno, reg->id, reg->off, reg->range);
1559                 return -EACCES;
1560         }
1561         return 0;
1562 }
1563
1564 static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off,
1565                                int size, bool zero_size_allowed)
1566 {
1567         struct bpf_reg_state *regs = cur_regs(env);
1568         struct bpf_reg_state *reg = &regs[regno];
1569         int err;
1570
1571         /* We may have added a variable offset to the packet pointer; but any
1572          * reg->range we have comes after that.  We are only checking the fixed
1573          * offset.
1574          */
1575
1576         /* We don't allow negative numbers, because we aren't tracking enough
1577          * detail to prove they're safe.
1578          */
1579         if (reg->smin_value < 0) {
1580                 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
1581                         regno);
1582                 return -EACCES;
1583         }
1584         err = __check_packet_access(env, regno, off, size, zero_size_allowed);
1585         if (err) {
1586                 verbose(env, "R%d offset is outside of the packet\n", regno);
1587                 return err;
1588         }
1589
1590         /* __check_packet_access has made sure "off + size - 1" is within u16.
1591          * reg->umax_value can't be bigger than MAX_PACKET_OFF which is 0xffff,
1592          * otherwise find_good_pkt_pointers would have refused to set range info
1593          * that __check_packet_access would have rejected this pkt access.
1594          * Therefore, "off + reg->umax_value + size - 1" won't overflow u32.
1595          */
1596         env->prog->aux->max_pkt_offset =
1597                 max_t(u32, env->prog->aux->max_pkt_offset,
1598                       off + reg->umax_value + size - 1);
1599
1600         return err;
1601 }
1602
1603 /* check access to 'struct bpf_context' fields.  Supports fixed offsets only */
1604 static int check_ctx_access(struct bpf_verifier_env *env, int insn_idx, int off, int size,
1605                             enum bpf_access_type t, enum bpf_reg_type *reg_type)
1606 {
1607         struct bpf_insn_access_aux info = {
1608                 .reg_type = *reg_type,
1609         };
1610
1611         if (env->ops->is_valid_access &&
1612             env->ops->is_valid_access(off, size, t, env->prog, &info)) {
1613                 /* A non zero info.ctx_field_size indicates that this field is a
1614                  * candidate for later verifier transformation to load the whole
1615                  * field and then apply a mask when accessed with a narrower
1616                  * access than actual ctx access size. A zero info.ctx_field_size
1617                  * will only allow for whole field access and rejects any other
1618                  * type of narrower access.
1619                  */
1620                 *reg_type = info.reg_type;
1621
1622                 env->insn_aux_data[insn_idx].ctx_field_size = info.ctx_field_size;
1623                 /* remember the offset of last byte accessed in ctx */
1624                 if (env->prog->aux->max_ctx_offset < off + size)
1625                         env->prog->aux->max_ctx_offset = off + size;
1626                 return 0;
1627         }
1628
1629         verbose(env, "invalid bpf_context access off=%d size=%d\n", off, size);
1630         return -EACCES;
1631 }
1632
1633 static int check_flow_keys_access(struct bpf_verifier_env *env, int off,
1634                                   int size)
1635 {
1636         if (size < 0 || off < 0 ||
1637             (u64)off + size > sizeof(struct bpf_flow_keys)) {
1638                 verbose(env, "invalid access to flow keys off=%d size=%d\n",
1639                         off, size);
1640                 return -EACCES;
1641         }
1642         return 0;
1643 }
1644
1645 static int check_sock_access(struct bpf_verifier_env *env, int insn_idx,
1646                              u32 regno, int off, int size,
1647                              enum bpf_access_type t)
1648 {
1649         struct bpf_reg_state *regs = cur_regs(env);
1650         struct bpf_reg_state *reg = &regs[regno];
1651         struct bpf_insn_access_aux info = {};
1652         bool valid;
1653
1654         if (reg->smin_value < 0) {
1655                 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
1656                         regno);
1657                 return -EACCES;
1658         }
1659
1660         switch (reg->type) {
1661         case PTR_TO_SOCK_COMMON:
1662                 valid = bpf_sock_common_is_valid_access(off, size, t, &info);
1663                 break;
1664         case PTR_TO_SOCKET:
1665                 valid = bpf_sock_is_valid_access(off, size, t, &info);
1666                 break;
1667         case PTR_TO_TCP_SOCK:
1668                 valid = bpf_tcp_sock_is_valid_access(off, size, t, &info);
1669                 break;
1670         default:
1671                 valid = false;
1672         }
1673
1674
1675         if (valid) {
1676                 env->insn_aux_data[insn_idx].ctx_field_size =
1677                         info.ctx_field_size;
1678                 return 0;
1679         }
1680
1681         verbose(env, "R%d invalid %s access off=%d size=%d\n",
1682                 regno, reg_type_str[reg->type], off, size);
1683
1684         return -EACCES;
1685 }
1686
1687 static bool __is_pointer_value(bool allow_ptr_leaks,
1688                                const struct bpf_reg_state *reg)
1689 {
1690         if (allow_ptr_leaks)
1691                 return false;
1692
1693         return reg->type != SCALAR_VALUE;
1694 }
1695
1696 static struct bpf_reg_state *reg_state(struct bpf_verifier_env *env, int regno)
1697 {
1698         return cur_regs(env) + regno;
1699 }
1700
1701 static bool is_pointer_value(struct bpf_verifier_env *env, int regno)
1702 {
1703         return __is_pointer_value(env->allow_ptr_leaks, reg_state(env, regno));
1704 }
1705
1706 static bool is_ctx_reg(struct bpf_verifier_env *env, int regno)
1707 {
1708         const struct bpf_reg_state *reg = reg_state(env, regno);
1709
1710         return reg->type == PTR_TO_CTX;
1711 }
1712
1713 static bool is_sk_reg(struct bpf_verifier_env *env, int regno)
1714 {
1715         const struct bpf_reg_state *reg = reg_state(env, regno);
1716
1717         return type_is_sk_pointer(reg->type);
1718 }
1719
1720 static bool is_pkt_reg(struct bpf_verifier_env *env, int regno)
1721 {
1722         const struct bpf_reg_state *reg = reg_state(env, regno);
1723
1724         return type_is_pkt_pointer(reg->type);
1725 }
1726
1727 static bool is_flow_key_reg(struct bpf_verifier_env *env, int regno)
1728 {
1729         const struct bpf_reg_state *reg = reg_state(env, regno);
1730
1731         /* Separate to is_ctx_reg() since we still want to allow BPF_ST here. */
1732         return reg->type == PTR_TO_FLOW_KEYS;
1733 }
1734
1735 static int check_pkt_ptr_alignment(struct bpf_verifier_env *env,
1736                                    const struct bpf_reg_state *reg,
1737                                    int off, int size, bool strict)
1738 {
1739         struct tnum reg_off;
1740         int ip_align;
1741
1742         /* Byte size accesses are always allowed. */
1743         if (!strict || size == 1)
1744                 return 0;
1745
1746         /* For platforms that do not have a Kconfig enabling
1747          * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS the value of
1748          * NET_IP_ALIGN is universally set to '2'.  And on platforms
1749          * that do set CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS, we get
1750          * to this code only in strict mode where we want to emulate
1751          * the NET_IP_ALIGN==2 checking.  Therefore use an
1752          * unconditional IP align value of '2'.
1753          */
1754         ip_align = 2;
1755
1756         reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
1757         if (!tnum_is_aligned(reg_off, size)) {
1758                 char tn_buf[48];
1759
1760                 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1761                 verbose(env,
1762                         "misaligned packet access off %d+%s+%d+%d size %d\n",
1763                         ip_align, tn_buf, reg->off, off, size);
1764                 return -EACCES;
1765         }
1766
1767         return 0;
1768 }
1769
1770 static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
1771                                        const struct bpf_reg_state *reg,
1772                                        const char *pointer_desc,
1773                                        int off, int size, bool strict)
1774 {
1775         struct tnum reg_off;
1776
1777         /* Byte size accesses are always allowed. */
1778         if (!strict || size == 1)
1779                 return 0;
1780
1781         reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
1782         if (!tnum_is_aligned(reg_off, size)) {
1783                 char tn_buf[48];
1784
1785                 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1786                 verbose(env, "misaligned %saccess off %s+%d+%d size %d\n",
1787                         pointer_desc, tn_buf, reg->off, off, size);
1788                 return -EACCES;
1789         }
1790
1791         return 0;
1792 }
1793
1794 static int check_ptr_alignment(struct bpf_verifier_env *env,
1795                                const struct bpf_reg_state *reg, int off,
1796                                int size, bool strict_alignment_once)
1797 {
1798         bool strict = env->strict_alignment || strict_alignment_once;
1799         const char *pointer_desc = "";
1800
1801         switch (reg->type) {
1802         case PTR_TO_PACKET:
1803         case PTR_TO_PACKET_META:
1804                 /* Special case, because of NET_IP_ALIGN. Given metadata sits
1805                  * right in front, treat it the very same way.
1806                  */
1807                 return check_pkt_ptr_alignment(env, reg, off, size, strict);
1808         case PTR_TO_FLOW_KEYS:
1809                 pointer_desc = "flow keys ";
1810                 break;
1811         case PTR_TO_MAP_VALUE:
1812                 pointer_desc = "value ";
1813                 break;
1814         case PTR_TO_CTX:
1815                 pointer_desc = "context ";
1816                 break;
1817         case PTR_TO_STACK:
1818                 pointer_desc = "stack ";
1819                 /* The stack spill tracking logic in check_stack_write()
1820                  * and check_stack_read() relies on stack accesses being
1821                  * aligned.
1822                  */
1823                 strict = true;
1824                 break;
1825         case PTR_TO_SOCKET:
1826                 pointer_desc = "sock ";
1827                 break;
1828         case PTR_TO_SOCK_COMMON:
1829                 pointer_desc = "sock_common ";
1830                 break;
1831         case PTR_TO_TCP_SOCK:
1832                 pointer_desc = "tcp_sock ";
1833                 break;
1834         default:
1835                 break;
1836         }
1837         return check_generic_ptr_alignment(env, reg, pointer_desc, off, size,
1838                                            strict);
1839 }
1840
1841 static int update_stack_depth(struct bpf_verifier_env *env,
1842                               const struct bpf_func_state *func,
1843                               int off)
1844 {
1845         u16 stack = env->subprog_info[func->subprogno].stack_depth;
1846
1847         if (stack >= -off)
1848                 return 0;
1849
1850         /* update known max for given subprogram */
1851         env->subprog_info[func->subprogno].stack_depth = -off;
1852         return 0;
1853 }
1854
1855 /* starting from main bpf function walk all instructions of the function
1856  * and recursively walk all callees that given function can call.
1857  * Ignore jump and exit insns.
1858  * Since recursion is prevented by check_cfg() this algorithm
1859  * only needs a local stack of MAX_CALL_FRAMES to remember callsites
1860  */
1861 static int check_max_stack_depth(struct bpf_verifier_env *env)
1862 {
1863         int depth = 0, frame = 0, idx = 0, i = 0, subprog_end;
1864         struct bpf_subprog_info *subprog = env->subprog_info;
1865         struct bpf_insn *insn = env->prog->insnsi;
1866         int ret_insn[MAX_CALL_FRAMES];
1867         int ret_prog[MAX_CALL_FRAMES];
1868
1869 process_func:
1870         /* round up to 32-bytes, since this is granularity
1871          * of interpreter stack size
1872          */
1873         depth += round_up(max_t(u32, subprog[idx].stack_depth, 1), 32);
1874         if (depth > MAX_BPF_STACK) {
1875                 verbose(env, "combined stack size of %d calls is %d. Too large\n",
1876                         frame + 1, depth);
1877                 return -EACCES;
1878         }
1879 continue_func:
1880         subprog_end = subprog[idx + 1].start;
1881         for (; i < subprog_end; i++) {
1882                 if (insn[i].code != (BPF_JMP | BPF_CALL))
1883                         continue;
1884                 if (insn[i].src_reg != BPF_PSEUDO_CALL)
1885                         continue;
1886                 /* remember insn and function to return to */
1887                 ret_insn[frame] = i + 1;
1888                 ret_prog[frame] = idx;
1889
1890                 /* find the callee */
1891                 i = i + insn[i].imm + 1;
1892                 idx = find_subprog(env, i);
1893                 if (idx < 0) {
1894                         WARN_ONCE(1, "verifier bug. No program starts at insn %d\n",
1895                                   i);
1896                         return -EFAULT;
1897                 }
1898                 frame++;
1899                 if (frame >= MAX_CALL_FRAMES) {
1900                         verbose(env, "the call stack of %d frames is too deep !\n",
1901                                 frame);
1902                         return -E2BIG;
1903                 }
1904                 goto process_func;
1905         }
1906         /* end of for() loop means the last insn of the 'subprog'
1907          * was reached. Doesn't matter whether it was JA or EXIT
1908          */
1909         if (frame == 0)
1910                 return 0;
1911         depth -= round_up(max_t(u32, subprog[idx].stack_depth, 1), 32);
1912         frame--;
1913         i = ret_insn[frame];
1914         idx = ret_prog[frame];
1915         goto continue_func;
1916 }
1917
1918 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
1919 static int get_callee_stack_depth(struct bpf_verifier_env *env,
1920                                   const struct bpf_insn *insn, int idx)
1921 {
1922         int start = idx + insn->imm + 1, subprog;
1923
1924         subprog = find_subprog(env, start);
1925         if (subprog < 0) {
1926                 WARN_ONCE(1, "verifier bug. No program starts at insn %d\n",
1927                           start);
1928                 return -EFAULT;
1929         }
1930         return env->subprog_info[subprog].stack_depth;
1931 }
1932 #endif
1933
1934 static int check_ctx_reg(struct bpf_verifier_env *env,
1935                          const struct bpf_reg_state *reg, int regno)
1936 {
1937         /* Access to ctx or passing it to a helper is only allowed in
1938          * its original, unmodified form.
1939          */
1940
1941         if (reg->off) {
1942                 verbose(env, "dereference of modified ctx ptr R%d off=%d disallowed\n",
1943                         regno, reg->off);
1944                 return -EACCES;
1945         }
1946
1947         if (!tnum_is_const(reg->var_off) || reg->var_off.value) {
1948                 char tn_buf[48];
1949
1950                 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1951                 verbose(env, "variable ctx access var_off=%s disallowed\n", tn_buf);
1952                 return -EACCES;
1953         }
1954
1955         return 0;
1956 }
1957
1958 /* truncate register to smaller size (in bytes)
1959  * must be called with size < BPF_REG_SIZE
1960  */
1961 static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
1962 {
1963         u64 mask;
1964
1965         /* clear high bits in bit representation */
1966         reg->var_off = tnum_cast(reg->var_off, size);
1967
1968         /* fix arithmetic bounds */
1969         mask = ((u64)1 << (size * 8)) - 1;
1970         if ((reg->umin_value & ~mask) == (reg->umax_value & ~mask)) {
1971                 reg->umin_value &= mask;
1972                 reg->umax_value &= mask;
1973         } else {
1974                 reg->umin_value = 0;
1975                 reg->umax_value = mask;
1976         }
1977         reg->smin_value = reg->umin_value;
1978         reg->smax_value = reg->umax_value;
1979 }
1980
1981 /* check whether memory at (regno + off) is accessible for t = (read | write)
1982  * if t==write, value_regno is a register which value is stored into memory
1983  * if t==read, value_regno is a register which will receive the value from memory
1984  * if t==write && value_regno==-1, some unknown value is stored into memory
1985  * if t==read && value_regno==-1, don't care what we read from memory
1986  */
1987 static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno,
1988                             int off, int bpf_size, enum bpf_access_type t,
1989                             int value_regno, bool strict_alignment_once)
1990 {
1991         struct bpf_reg_state *regs = cur_regs(env);
1992         struct bpf_reg_state *reg = regs + regno;
1993         struct bpf_func_state *state;
1994         int size, err = 0;
1995
1996         size = bpf_size_to_bytes(bpf_size);
1997         if (size < 0)
1998                 return size;
1999
2000         /* alignment checks will add in reg->off themselves */
2001         err = check_ptr_alignment(env, reg, off, size, strict_alignment_once);
2002         if (err)
2003                 return err;
2004
2005         /* for access checks, reg->off is just part of off */
2006         off += reg->off;
2007
2008         if (reg->type == PTR_TO_MAP_VALUE) {
2009                 if (t == BPF_WRITE && value_regno >= 0 &&
2010                     is_pointer_value(env, value_regno)) {
2011                         verbose(env, "R%d leaks addr into map\n", value_regno);
2012                         return -EACCES;
2013                 }
2014
2015                 err = check_map_access(env, regno, off, size, false);
2016                 if (!err && t == BPF_READ && value_regno >= 0)
2017                         mark_reg_unknown(env, regs, value_regno);
2018
2019         } else if (reg->type == PTR_TO_CTX) {
2020                 enum bpf_reg_type reg_type = SCALAR_VALUE;
2021
2022                 if (t == BPF_WRITE && value_regno >= 0 &&
2023                     is_pointer_value(env, value_regno)) {
2024                         verbose(env, "R%d leaks addr into ctx\n", value_regno);
2025                         return -EACCES;
2026                 }
2027
2028                 err = check_ctx_reg(env, reg, regno);
2029                 if (err < 0)
2030                         return err;
2031
2032                 err = check_ctx_access(env, insn_idx, off, size, t, &reg_type);
2033                 if (!err && t == BPF_READ && value_regno >= 0) {
2034                         /* ctx access returns either a scalar, or a
2035                          * PTR_TO_PACKET[_META,_END]. In the latter
2036                          * case, we know the offset is zero.
2037                          */
2038                         if (reg_type == SCALAR_VALUE) {
2039                                 mark_reg_unknown(env, regs, value_regno);
2040                         } else {
2041                                 mark_reg_known_zero(env, regs,
2042                                                     value_regno);
2043                                 if (reg_type_may_be_null(reg_type))
2044                                         regs[value_regno].id = ++env->id_gen;
2045                         }
2046                         regs[value_regno].type = reg_type;
2047                 }
2048
2049         } else if (reg->type == PTR_TO_STACK) {
2050                 off += reg->var_off.value;
2051                 err = check_stack_access(env, reg, off, size);
2052                 if (err)
2053                         return err;
2054
2055                 state = func(env, reg);
2056                 err = update_stack_depth(env, state, off);
2057                 if (err)
2058                         return err;
2059
2060                 if (t == BPF_WRITE)
2061                         err = check_stack_write(env, state, off, size,
2062                                                 value_regno, insn_idx);
2063                 else
2064                         err = check_stack_read(env, state, off, size,
2065                                                value_regno);
2066         } else if (reg_is_pkt_pointer(reg)) {
2067                 if (t == BPF_WRITE && !may_access_direct_pkt_data(env, NULL, t)) {
2068                         verbose(env, "cannot write into packet\n");
2069                         return -EACCES;
2070                 }
2071                 if (t == BPF_WRITE && value_regno >= 0 &&
2072                     is_pointer_value(env, value_regno)) {
2073                         verbose(env, "R%d leaks addr into packet\n",
2074                                 value_regno);
2075                         return -EACCES;
2076                 }
2077                 err = check_packet_access(env, regno, off, size, false);
2078                 if (!err && t == BPF_READ && value_regno >= 0)
2079                         mark_reg_unknown(env, regs, value_regno);
2080         } else if (reg->type == PTR_TO_FLOW_KEYS) {
2081                 if (t == BPF_WRITE && value_regno >= 0 &&
2082                     is_pointer_value(env, value_regno)) {
2083                         verbose(env, "R%d leaks addr into flow keys\n",
2084                                 value_regno);
2085                         return -EACCES;
2086                 }
2087
2088                 err = check_flow_keys_access(env, off, size);
2089                 if (!err && t == BPF_READ && value_regno >= 0)
2090                         mark_reg_unknown(env, regs, value_regno);
2091         } else if (type_is_sk_pointer(reg->type)) {
2092                 if (t == BPF_WRITE) {
2093                         verbose(env, "R%d cannot write into %s\n",
2094                                 regno, reg_type_str[reg->type]);
2095                         return -EACCES;
2096                 }
2097                 err = check_sock_access(env, insn_idx, regno, off, size, t);
2098                 if (!err && value_regno >= 0)
2099                         mark_reg_unknown(env, regs, value_regno);
2100         } else {
2101                 verbose(env, "R%d invalid mem access '%s'\n", regno,
2102                         reg_type_str[reg->type]);
2103                 return -EACCES;
2104         }
2105
2106         if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
2107             regs[value_regno].type == SCALAR_VALUE) {
2108                 /* b/h/w load zero-extends, mark upper bits as known 0 */
2109                 coerce_reg_to_size(&regs[value_regno], size);
2110         }
2111         return err;
2112 }
2113
2114 static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn)
2115 {
2116         int err;
2117
2118         if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
2119             insn->imm != 0) {
2120                 verbose(env, "BPF_XADD uses reserved fields\n");
2121                 return -EINVAL;
2122         }
2123
2124         /* check src1 operand */
2125         err = check_reg_arg(env, insn->src_reg, SRC_OP);
2126         if (err)
2127                 return err;
2128
2129         /* check src2 operand */
2130         err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2131         if (err)
2132                 return err;
2133
2134         if (is_pointer_value(env, insn->src_reg)) {
2135                 verbose(env, "R%d leaks addr into mem\n", insn->src_reg);
2136                 return -EACCES;
2137         }
2138
2139         if (is_ctx_reg(env, insn->dst_reg) ||
2140             is_pkt_reg(env, insn->dst_reg) ||
2141             is_flow_key_reg(env, insn->dst_reg) ||
2142             is_sk_reg(env, insn->dst_reg)) {
2143                 verbose(env, "BPF_XADD stores into R%d %s is not allowed\n",
2144                         insn->dst_reg,
2145                         reg_type_str[reg_state(env, insn->dst_reg)->type]);
2146                 return -EACCES;
2147         }
2148
2149         /* check whether atomic_add can read the memory */
2150         err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
2151                                BPF_SIZE(insn->code), BPF_READ, -1, true);
2152         if (err)
2153                 return err;
2154
2155         /* check whether atomic_add can write into the same memory */
2156         return check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
2157                                 BPF_SIZE(insn->code), BPF_WRITE, -1, true);
2158 }
2159
2160 /* when register 'regno' is passed into function that will read 'access_size'
2161  * bytes from that pointer, make sure that it's within stack boundary
2162  * and all elements of stack are initialized.
2163  * Unlike most pointer bounds-checking functions, this one doesn't take an
2164  * 'off' argument, so it has to add in reg->off itself.
2165  */
2166 static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
2167                                 int access_size, bool zero_size_allowed,
2168                                 struct bpf_call_arg_meta *meta)
2169 {
2170         struct bpf_reg_state *reg = reg_state(env, regno);
2171         struct bpf_func_state *state = func(env, reg);
2172         int off, i, slot, spi;
2173
2174         if (reg->type != PTR_TO_STACK) {
2175                 /* Allow zero-byte read from NULL, regardless of pointer type */
2176                 if (zero_size_allowed && access_size == 0 &&
2177                     register_is_null(reg))
2178                         return 0;
2179
2180                 verbose(env, "R%d type=%s expected=%s\n", regno,
2181                         reg_type_str[reg->type],
2182                         reg_type_str[PTR_TO_STACK]);
2183                 return -EACCES;
2184         }
2185
2186         /* Only allow fixed-offset stack reads */
2187         if (!tnum_is_const(reg->var_off)) {
2188                 char tn_buf[48];
2189
2190                 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
2191                 verbose(env, "invalid variable stack read R%d var_off=%s\n",
2192                         regno, tn_buf);
2193                 return -EACCES;
2194         }
2195         off = reg->off + reg->var_off.value;
2196         if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
2197             access_size < 0 || (access_size == 0 && !zero_size_allowed)) {
2198                 verbose(env, "invalid stack type R%d off=%d access_size=%d\n",
2199                         regno, off, access_size);
2200                 return -EACCES;
2201         }
2202
2203         if (meta && meta->raw_mode) {
2204                 meta->access_size = access_size;
2205                 meta->regno = regno;
2206                 return 0;
2207         }
2208
2209         for (i = 0; i < access_size; i++) {
2210                 u8 *stype;
2211
2212                 slot = -(off + i) - 1;
2213                 spi = slot / BPF_REG_SIZE;
2214                 if (state->allocated_stack <= slot)
2215                         goto err;
2216                 stype = &state->stack[spi].slot_type[slot % BPF_REG_SIZE];
2217                 if (*stype == STACK_MISC)
2218                         goto mark;
2219                 if (*stype == STACK_ZERO) {
2220                         /* helper can write anything into the stack */
2221                         *stype = STACK_MISC;
2222                         goto mark;
2223                 }
2224 err:
2225                 verbose(env, "invalid indirect read from stack off %d+%d size %d\n",
2226                         off, i, access_size);
2227                 return -EACCES;
2228 mark:
2229                 /* reading any byte out of 8-byte 'spill_slot' will cause
2230                  * the whole slot to be marked as 'read'
2231                  */
2232                 mark_reg_read(env, &state->stack[spi].spilled_ptr,
2233                               state->stack[spi].spilled_ptr.parent);
2234         }
2235         return update_stack_depth(env, state, off);
2236 }
2237
2238 static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
2239                                    int access_size, bool zero_size_allowed,
2240                                    struct bpf_call_arg_meta *meta)
2241 {
2242         struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
2243
2244         switch (reg->type) {
2245         case PTR_TO_PACKET:
2246         case PTR_TO_PACKET_META:
2247                 return check_packet_access(env, regno, reg->off, access_size,
2248                                            zero_size_allowed);
2249         case PTR_TO_MAP_VALUE:
2250                 return check_map_access(env, regno, reg->off, access_size,
2251                                         zero_size_allowed);
2252         default: /* scalar_value|ptr_to_stack or invalid ptr */
2253                 return check_stack_boundary(env, regno, access_size,
2254                                             zero_size_allowed, meta);
2255         }
2256 }
2257
2258 /* Implementation details:
2259  * bpf_map_lookup returns PTR_TO_MAP_VALUE_OR_NULL
2260  * Two bpf_map_lookups (even with the same key) will have different reg->id.
2261  * For traditional PTR_TO_MAP_VALUE the verifier clears reg->id after
2262  * value_or_null->value transition, since the verifier only cares about
2263  * the range of access to valid map value pointer and doesn't care about actual
2264  * address of the map element.
2265  * For maps with 'struct bpf_spin_lock' inside map value the verifier keeps
2266  * reg->id > 0 after value_or_null->value transition. By doing so
2267  * two bpf_map_lookups will be considered two different pointers that
2268  * point to different bpf_spin_locks.
2269  * The verifier allows taking only one bpf_spin_lock at a time to avoid
2270  * dead-locks.
2271  * Since only one bpf_spin_lock is allowed the checks are simpler than
2272  * reg_is_refcounted() logic. The verifier needs to remember only
2273  * one spin_lock instead of array of acquired_refs.
2274  * cur_state->active_spin_lock remembers which map value element got locked
2275  * and clears it after bpf_spin_unlock.
2276  */
2277 static int process_spin_lock(struct bpf_verifier_env *env, int regno,
2278                              bool is_lock)
2279 {
2280         struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
2281         struct bpf_verifier_state *cur = env->cur_state;
2282         bool is_const = tnum_is_const(reg->var_off);
2283         struct bpf_map *map = reg->map_ptr;
2284         u64 val = reg->var_off.value;
2285
2286         if (reg->type != PTR_TO_MAP_VALUE) {
2287                 verbose(env, "R%d is not a pointer to map_value\n", regno);
2288                 return -EINVAL;
2289         }
2290         if (!is_const) {
2291                 verbose(env,
2292                         "R%d doesn't have constant offset. bpf_spin_lock has to be at the constant offset\n",
2293                         regno);
2294                 return -EINVAL;
2295         }
2296         if (!map->btf) {
2297                 verbose(env,
2298                         "map '%s' has to have BTF in order to use bpf_spin_lock\n",
2299                         map->name);
2300                 return -EINVAL;
2301         }
2302         if (!map_value_has_spin_lock(map)) {
2303                 if (map->spin_lock_off == -E2BIG)
2304                         verbose(env,
2305                                 "map '%s' has more than one 'struct bpf_spin_lock'\n",
2306                                 map->name);
2307                 else if (map->spin_lock_off == -ENOENT)
2308                         verbose(env,
2309                                 "map '%s' doesn't have 'struct bpf_spin_lock'\n",
2310                                 map->name);
2311                 else
2312                         verbose(env,
2313                                 "map '%s' is not a struct type or bpf_spin_lock is mangled\n",
2314                                 map->name);
2315                 return -EINVAL;
2316         }
2317         if (map->spin_lock_off != val + reg->off) {
2318                 verbose(env, "off %lld doesn't point to 'struct bpf_spin_lock'\n",
2319                         val + reg->off);
2320                 return -EINVAL;
2321         }
2322         if (is_lock) {
2323                 if (cur->active_spin_lock) {
2324                         verbose(env,
2325                                 "Locking two bpf_spin_locks are not allowed\n");
2326                         return -EINVAL;
2327                 }
2328                 cur->active_spin_lock = reg->id;
2329         } else {
2330                 if (!cur->active_spin_lock) {
2331                         verbose(env, "bpf_spin_unlock without taking a lock\n");
2332                         return -EINVAL;
2333                 }
2334                 if (cur->active_spin_lock != reg->id) {
2335                         verbose(env, "bpf_spin_unlock of different lock\n");
2336                         return -EINVAL;
2337                 }
2338                 cur->active_spin_lock = 0;
2339         }
2340         return 0;
2341 }
2342
2343 static bool arg_type_is_mem_ptr(enum bpf_arg_type type)
2344 {
2345         return type == ARG_PTR_TO_MEM ||
2346                type == ARG_PTR_TO_MEM_OR_NULL ||
2347                type == ARG_PTR_TO_UNINIT_MEM;
2348 }
2349
2350 static bool arg_type_is_mem_size(enum bpf_arg_type type)
2351 {
2352         return type == ARG_CONST_SIZE ||
2353                type == ARG_CONST_SIZE_OR_ZERO;
2354 }
2355
2356 static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
2357                           enum bpf_arg_type arg_type,
2358                           struct bpf_call_arg_meta *meta)
2359 {
2360         struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
2361         enum bpf_reg_type expected_type, type = reg->type;
2362         int err = 0;
2363
2364         if (arg_type == ARG_DONTCARE)
2365                 return 0;
2366
2367         err = check_reg_arg(env, regno, SRC_OP);
2368         if (err)
2369                 return err;
2370
2371         if (arg_type == ARG_ANYTHING) {
2372                 if (is_pointer_value(env, regno)) {
2373                         verbose(env, "R%d leaks addr into helper function\n",
2374                                 regno);
2375                         return -EACCES;
2376                 }
2377                 return 0;
2378         }
2379
2380         if (type_is_pkt_pointer(type) &&
2381             !may_access_direct_pkt_data(env, meta, BPF_READ)) {
2382                 verbose(env, "helper access to the packet is not allowed\n");
2383                 return -EACCES;
2384         }
2385
2386         if (arg_type == ARG_PTR_TO_MAP_KEY ||
2387             arg_type == ARG_PTR_TO_MAP_VALUE ||
2388             arg_type == ARG_PTR_TO_UNINIT_MAP_VALUE) {
2389                 expected_type = PTR_TO_STACK;
2390                 if (!type_is_pkt_pointer(type) && type != PTR_TO_MAP_VALUE &&
2391                     type != expected_type)
2392                         goto err_type;
2393         } else if (arg_type == ARG_CONST_SIZE ||
2394                    arg_type == ARG_CONST_SIZE_OR_ZERO) {
2395                 expected_type = SCALAR_VALUE;
2396                 if (type != expected_type)
2397                         goto err_type;
2398         } else if (arg_type == ARG_CONST_MAP_PTR) {
2399                 expected_type = CONST_PTR_TO_MAP;
2400                 if (type != expected_type)
2401                         goto err_type;
2402         } else if (arg_type == ARG_PTR_TO_CTX) {
2403                 expected_type = PTR_TO_CTX;
2404                 if (type != expected_type)
2405                         goto err_type;
2406                 err = check_ctx_reg(env, reg, regno);
2407                 if (err < 0)
2408                         return err;
2409         } else if (arg_type == ARG_PTR_TO_SOCK_COMMON) {
2410                 expected_type = PTR_TO_SOCK_COMMON;
2411                 /* Any sk pointer can be ARG_PTR_TO_SOCK_COMMON */
2412                 if (!type_is_sk_pointer(type))
2413                         goto err_type;
2414                 if (reg->ref_obj_id) {
2415                         if (meta->ref_obj_id) {
2416                                 verbose(env, "verifier internal error: more than one arg with ref_obj_id R%d %u %u\n",
2417                                         regno, reg->ref_obj_id,
2418                                         meta->ref_obj_id);
2419                                 return -EFAULT;
2420                         }
2421                         meta->ref_obj_id = reg->ref_obj_id;
2422                 }
2423         } else if (arg_type == ARG_PTR_TO_SPIN_LOCK) {
2424                 if (meta->func_id == BPF_FUNC_spin_lock) {
2425                         if (process_spin_lock(env, regno, true))
2426                                 return -EACCES;
2427                 } else if (meta->func_id == BPF_FUNC_spin_unlock) {
2428                         if (process_spin_lock(env, regno, false))
2429                                 return -EACCES;
2430                 } else {
2431                         verbose(env, "verifier internal error\n");
2432                         return -EFAULT;
2433                 }
2434         } else if (arg_type_is_mem_ptr(arg_type)) {
2435                 expected_type = PTR_TO_STACK;
2436                 /* One exception here. In case function allows for NULL to be
2437                  * passed in as argument, it's a SCALAR_VALUE type. Final test
2438                  * happens during stack boundary checking.
2439                  */
2440                 if (register_is_null(reg) &&
2441                     arg_type == ARG_PTR_TO_MEM_OR_NULL)
2442                         /* final test in check_stack_boundary() */;
2443                 else if (!type_is_pkt_pointer(type) &&
2444                          type != PTR_TO_MAP_VALUE &&
2445                          type != expected_type)
2446                         goto err_type;
2447                 meta->raw_mode = arg_type == ARG_PTR_TO_UNINIT_MEM;
2448         } else {
2449                 verbose(env, "unsupported arg_type %d\n", arg_type);
2450                 return -EFAULT;
2451         }
2452
2453         if (arg_type == ARG_CONST_MAP_PTR) {
2454                 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
2455                 meta->map_ptr = reg->map_ptr;
2456         } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
2457                 /* bpf_map_xxx(..., map_ptr, ..., key) call:
2458                  * check that [key, key + map->key_size) are within
2459                  * stack limits and initialized
2460                  */
2461                 if (!meta->map_ptr) {
2462                         /* in function declaration map_ptr must come before
2463                          * map_key, so that it's verified and known before
2464                          * we have to check map_key here. Otherwise it means
2465                          * that kernel subsystem misconfigured verifier
2466                          */
2467                         verbose(env, "invalid map_ptr to access map->key\n");
2468                         return -EACCES;
2469                 }
2470                 err = check_helper_mem_access(env, regno,
2471                                               meta->map_ptr->key_size, false,
2472                                               NULL);
2473         } else if (arg_type == ARG_PTR_TO_MAP_VALUE ||
2474                    arg_type == ARG_PTR_TO_UNINIT_MAP_VALUE) {
2475                 /* bpf_map_xxx(..., map_ptr, ..., value) call:
2476                  * check [value, value + map->value_size) validity
2477                  */
2478                 if (!meta->map_ptr) {
2479                         /* kernel subsystem misconfigured verifier */
2480                         verbose(env, "invalid map_ptr to access map->value\n");
2481                         return -EACCES;
2482                 }
2483                 meta->raw_mode = (arg_type == ARG_PTR_TO_UNINIT_MAP_VALUE);
2484                 err = check_helper_mem_access(env, regno,
2485                                               meta->map_ptr->value_size, false,
2486                                               meta);
2487         } else if (arg_type_is_mem_size(arg_type)) {
2488                 bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO);
2489
2490                 /* remember the mem_size which may be used later
2491                  * to refine return values.
2492                  */
2493                 meta->msize_smax_value = reg->smax_value;
2494                 meta->msize_umax_value = reg->umax_value;
2495
2496                 /* The register is SCALAR_VALUE; the access check
2497                  * happens using its boundaries.
2498                  */
2499                 if (!tnum_is_const(reg->var_off))
2500                         /* For unprivileged variable accesses, disable raw
2501                          * mode so that the program is required to
2502                          * initialize all the memory that the helper could
2503                          * just partially fill up.
2504                          */
2505                         meta = NULL;
2506
2507                 if (reg->smin_value < 0) {
2508                         verbose(env, "R%d min value is negative, either use unsigned or 'var &= const'\n",
2509                                 regno);
2510                         return -EACCES;
2511                 }
2512
2513                 if (reg->umin_value == 0) {
2514                         err = check_helper_mem_access(env, regno - 1, 0,
2515                                                       zero_size_allowed,
2516                                                       meta);
2517                         if (err)
2518                                 return err;
2519                 }
2520
2521                 if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
2522                         verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
2523                                 regno);
2524                         return -EACCES;
2525                 }
2526                 err = check_helper_mem_access(env, regno - 1,
2527                                               reg->umax_value,
2528                                               zero_size_allowed, meta);
2529         }
2530
2531         return err;
2532 err_type:
2533         verbose(env, "R%d type=%s expected=%s\n", regno,
2534                 reg_type_str[type], reg_type_str[expected_type]);
2535         return -EACCES;
2536 }
2537
2538 static int check_map_func_compatibility(struct bpf_verifier_env *env,
2539                                         struct bpf_map *map, int func_id)
2540 {
2541         if (!map)
2542                 return 0;
2543
2544         /* We need a two way check, first is from map perspective ... */
2545         switch (map->map_type) {
2546         case BPF_MAP_TYPE_PROG_ARRAY:
2547                 if (func_id != BPF_FUNC_tail_call)
2548                         goto error;
2549                 break;
2550         case BPF_MAP_TYPE_PERF_EVENT_ARRAY:
2551                 if (func_id != BPF_FUNC_perf_event_read &&
2552                     func_id != BPF_FUNC_perf_event_output &&
2553                     func_id != BPF_FUNC_perf_event_read_value)
2554                         goto error;
2555                 break;
2556         case BPF_MAP_TYPE_STACK_TRACE:
2557                 if (func_id != BPF_FUNC_get_stackid)
2558                         goto error;
2559                 break;
2560         case BPF_MAP_TYPE_CGROUP_ARRAY:
2561                 if (func_id != BPF_FUNC_skb_under_cgroup &&
2562                     func_id != BPF_FUNC_current_task_under_cgroup)
2563                         goto error;
2564                 break;
2565         case BPF_MAP_TYPE_CGROUP_STORAGE:
2566         case BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE:
2567                 if (func_id != BPF_FUNC_get_local_storage)
2568                         goto error;
2569                 break;
2570         /* devmap returns a pointer to a live net_device ifindex that we cannot
2571          * allow to be modified from bpf side. So do not allow lookup elements
2572          * for now.
2573          */
2574         case BPF_MAP_TYPE_DEVMAP:
2575                 if (func_id != BPF_FUNC_redirect_map)
2576                         goto error;
2577                 break;
2578         /* Restrict bpf side of cpumap and xskmap, open when use-cases
2579          * appear.
2580          */
2581         case BPF_MAP_TYPE_CPUMAP:
2582         case BPF_MAP_TYPE_XSKMAP:
2583                 if (func_id != BPF_FUNC_redirect_map)
2584                         goto error;
2585                 break;
2586         case BPF_MAP_TYPE_ARRAY_OF_MAPS:
2587         case BPF_MAP_TYPE_HASH_OF_MAPS:
2588                 if (func_id != BPF_FUNC_map_lookup_elem)
2589                         goto error;
2590                 break;
2591         case BPF_MAP_TYPE_SOCKMAP:
2592                 if (func_id != BPF_FUNC_sk_redirect_map &&
2593                     func_id != BPF_FUNC_sock_map_update &&
2594                     func_id != BPF_FUNC_map_delete_elem &&
2595                     func_id != BPF_FUNC_msg_redirect_map)
2596                         goto error;
2597                 break;
2598         case BPF_MAP_TYPE_SOCKHASH:
2599                 if (func_id != BPF_FUNC_sk_redirect_hash &&
2600                     func_id != BPF_FUNC_sock_hash_update &&
2601                     func_id != BPF_FUNC_map_delete_elem &&
2602                     func_id != BPF_FUNC_msg_redirect_hash)
2603                         goto error;
2604                 break;
2605         case BPF_MAP_TYPE_REUSEPORT_SOCKARRAY:
2606                 if (func_id != BPF_FUNC_sk_select_reuseport)
2607                         goto error;
2608                 break;
2609         case BPF_MAP_TYPE_QUEUE:
2610         case BPF_MAP_TYPE_STACK:
2611                 if (func_id != BPF_FUNC_map_peek_elem &&
2612                     func_id != BPF_FUNC_map_pop_elem &&
2613                     func_id != BPF_FUNC_map_push_elem)
2614                         goto error;
2615                 break;
2616         default:
2617                 break;
2618         }
2619
2620         /* ... and second from the function itself. */
2621         switch (func_id) {
2622         case BPF_FUNC_tail_call:
2623                 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
2624                         goto error;
2625                 if (env->subprog_cnt > 1) {
2626                         verbose(env, "tail_calls are not allowed in programs with bpf-to-bpf calls\n");
2627                         return -EINVAL;
2628                 }
2629                 break;
2630         case BPF_FUNC_perf_event_read:
2631         case BPF_FUNC_perf_event_output:
2632         case BPF_FUNC_perf_event_read_value:
2633                 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY)
2634                         goto error;
2635                 break;
2636         case BPF_FUNC_get_stackid:
2637                 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE)
2638                         goto error;
2639                 break;
2640         case BPF_FUNC_current_task_under_cgroup:
2641         case BPF_FUNC_skb_under_cgroup:
2642                 if (map->map_type != BPF_MAP_TYPE_CGROUP_ARRAY)
2643                         goto error;
2644                 break;
2645         case BPF_FUNC_redirect_map:
2646                 if (map->map_type != BPF_MAP_TYPE_DEVMAP &&
2647                     map->map_type != BPF_MAP_TYPE_CPUMAP &&
2648                     map->map_type != BPF_MAP_TYPE_XSKMAP)
2649                         goto error;
2650                 break;
2651         case BPF_FUNC_sk_redirect_map:
2652         case BPF_FUNC_msg_redirect_map:
2653         case BPF_FUNC_sock_map_update:
2654                 if (map->map_type != BPF_MAP_TYPE_SOCKMAP)
2655                         goto error;
2656                 break;
2657         case BPF_FUNC_sk_redirect_hash:
2658         case BPF_FUNC_msg_redirect_hash:
2659         case BPF_FUNC_sock_hash_update:
2660                 if (map->map_type != BPF_MAP_TYPE_SOCKHASH)
2661                         goto error;
2662                 break;
2663         case BPF_FUNC_get_local_storage:
2664                 if (map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE &&
2665                     map->map_type != BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE)
2666                         goto error;
2667                 break;
2668         case BPF_FUNC_sk_select_reuseport:
2669                 if (map->map_type != BPF_MAP_TYPE_REUSEPORT_SOCKARRAY)
2670                         goto error;
2671                 break;
2672         case BPF_FUNC_map_peek_elem:
2673         case BPF_FUNC_map_pop_elem:
2674         case BPF_FUNC_map_push_elem:
2675                 if (map->map_type != BPF_MAP_TYPE_QUEUE &&
2676                     map->map_type != BPF_MAP_TYPE_STACK)
2677                         goto error;
2678                 break;
2679         default:
2680                 break;
2681         }
2682
2683         return 0;
2684 error:
2685         verbose(env, "cannot pass map_type %d into func %s#%d\n",
2686                 map->map_type, func_id_name(func_id), func_id);
2687         return -EINVAL;
2688 }
2689
2690 static bool check_raw_mode_ok(const struct bpf_func_proto *fn)
2691 {
2692         int count = 0;
2693
2694         if (fn->arg1_type == ARG_PTR_TO_UNINIT_MEM)
2695                 count++;
2696         if (fn->arg2_type == ARG_PTR_TO_UNINIT_MEM)
2697                 count++;
2698         if (fn->arg3_type == ARG_PTR_TO_UNINIT_MEM)
2699                 count++;
2700         if (fn->arg4_type == ARG_PTR_TO_UNINIT_MEM)
2701                 count++;
2702         if (fn->arg5_type == ARG_PTR_TO_UNINIT_MEM)
2703                 count++;
2704
2705         /* We only support one arg being in raw mode at the moment,
2706          * which is sufficient for the helper functions we have
2707          * right now.
2708          */
2709         return count <= 1;
2710 }
2711
2712 static bool check_args_pair_invalid(enum bpf_arg_type arg_curr,
2713                                     enum bpf_arg_type arg_next)
2714 {
2715         return (arg_type_is_mem_ptr(arg_curr) &&
2716                 !arg_type_is_mem_size(arg_next)) ||
2717                (!arg_type_is_mem_ptr(arg_curr) &&
2718                 arg_type_is_mem_size(arg_next));
2719 }
2720
2721 static bool check_arg_pair_ok(const struct bpf_func_proto *fn)
2722 {
2723         /* bpf_xxx(..., buf, len) call will access 'len'
2724          * bytes from memory 'buf'. Both arg types need
2725          * to be paired, so make sure there's no buggy
2726          * helper function specification.
2727          */
2728         if (arg_type_is_mem_size(fn->arg1_type) ||
2729             arg_type_is_mem_ptr(fn->arg5_type)  ||
2730             check_args_pair_invalid(fn->arg1_type, fn->arg2_type) ||
2731             check_args_pair_invalid(fn->arg2_type, fn->arg3_type) ||
2732             check_args_pair_invalid(fn->arg3_type, fn->arg4_type) ||
2733             check_args_pair_invalid(fn->arg4_type, fn->arg5_type))
2734                 return false;
2735
2736         return true;
2737 }
2738
2739 static bool check_refcount_ok(const struct bpf_func_proto *fn, int func_id)
2740 {
2741         int count = 0;
2742
2743         if (arg_type_may_be_refcounted(fn->arg1_type))
2744                 count++;
2745         if (arg_type_may_be_refcounted(fn->arg2_type))
2746                 count++;
2747         if (arg_type_may_be_refcounted(fn->arg3_type))
2748                 count++;
2749         if (arg_type_may_be_refcounted(fn->arg4_type))
2750                 count++;
2751         if (arg_type_may_be_refcounted(fn->arg5_type))
2752                 count++;
2753
2754         /* A reference acquiring function cannot acquire
2755          * another refcounted ptr.
2756          */
2757         if (is_acquire_function(func_id) && count)
2758                 return false;
2759
2760         /* We only support one arg being unreferenced at the moment,
2761          * which is sufficient for the helper functions we have right now.
2762          */
2763         return count <= 1;
2764 }
2765
2766 static int check_func_proto(const struct bpf_func_proto *fn, int func_id)
2767 {
2768         return check_raw_mode_ok(fn) &&
2769                check_arg_pair_ok(fn) &&
2770                check_refcount_ok(fn, func_id) ? 0 : -EINVAL;
2771 }
2772
2773 /* Packet data might have moved, any old PTR_TO_PACKET[_META,_END]
2774  * are now invalid, so turn them into unknown SCALAR_VALUE.
2775  */
2776 static void __clear_all_pkt_pointers(struct bpf_verifier_env *env,
2777                                      struct bpf_func_state *state)
2778 {
2779         struct bpf_reg_state *regs = state->regs, *reg;
2780         int i;
2781
2782         for (i = 0; i < MAX_BPF_REG; i++)
2783                 if (reg_is_pkt_pointer_any(&regs[i]))
2784                         mark_reg_unknown(env, regs, i);
2785
2786         bpf_for_each_spilled_reg(i, state, reg) {
2787                 if (!reg)
2788                         continue;
2789                 if (reg_is_pkt_pointer_any(reg))
2790                         __mark_reg_unknown(reg);
2791         }
2792 }
2793
2794 static void clear_all_pkt_pointers(struct bpf_verifier_env *env)
2795 {
2796         struct bpf_verifier_state *vstate = env->cur_state;
2797         int i;
2798
2799         for (i = 0; i <= vstate->curframe; i++)
2800                 __clear_all_pkt_pointers(env, vstate->frame[i]);
2801 }
2802
2803 static void release_reg_references(struct bpf_verifier_env *env,
2804                                    struct bpf_func_state *state,
2805                                    int ref_obj_id)
2806 {
2807         struct bpf_reg_state *regs = state->regs, *reg;
2808         int i;
2809
2810         for (i = 0; i < MAX_BPF_REG; i++)
2811                 if (regs[i].ref_obj_id == ref_obj_id)
2812                         mark_reg_unknown(env, regs, i);
2813
2814         bpf_for_each_spilled_reg(i, state, reg) {
2815                 if (!reg)
2816                         continue;
2817                 if (reg->ref_obj_id == ref_obj_id)
2818                         __mark_reg_unknown(reg);
2819         }
2820 }
2821
2822 /* The pointer with the specified id has released its reference to kernel
2823  * resources. Identify all copies of the same pointer and clear the reference.
2824  */
2825 static int release_reference(struct bpf_verifier_env *env,
2826                              int ref_obj_id)
2827 {
2828         struct bpf_verifier_state *vstate = env->cur_state;
2829         int err;
2830         int i;
2831
2832         err = release_reference_state(cur_func(env), ref_obj_id);
2833         if (err)
2834                 return err;
2835
2836         for (i = 0; i <= vstate->curframe; i++)
2837                 release_reg_references(env, vstate->frame[i], ref_obj_id);
2838
2839         return 0;
2840 }
2841
2842 static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
2843                            int *insn_idx)
2844 {
2845         struct bpf_verifier_state *state = env->cur_state;
2846         struct bpf_func_state *caller, *callee;
2847         int i, err, subprog, target_insn;
2848
2849         if (state->curframe + 1 >= MAX_CALL_FRAMES) {
2850                 verbose(env, "the call stack of %d frames is too deep\n",
2851                         state->curframe + 2);
2852                 return -E2BIG;
2853         }
2854
2855         target_insn = *insn_idx + insn->imm;
2856         subprog = find_subprog(env, target_insn + 1);
2857         if (subprog < 0) {
2858                 verbose(env, "verifier bug. No program starts at insn %d\n",
2859                         target_insn + 1);
2860                 return -EFAULT;
2861         }
2862
2863         caller = state->frame[state->curframe];
2864         if (state->frame[state->curframe + 1]) {
2865                 verbose(env, "verifier bug. Frame %d already allocated\n",
2866                         state->curframe + 1);
2867                 return -EFAULT;
2868         }
2869
2870         callee = kzalloc(sizeof(*callee), GFP_KERNEL);
2871         if (!callee)
2872                 return -ENOMEM;
2873         state->frame[state->curframe + 1] = callee;
2874
2875         /* callee cannot access r0, r6 - r9 for reading and has to write
2876          * into its own stack before reading from it.
2877          * callee can read/write into caller's stack
2878          */
2879         init_func_state(env, callee,
2880                         /* remember the callsite, it will be used by bpf_exit */
2881                         *insn_idx /* callsite */,
2882                         state->curframe + 1 /* frameno within this callchain */,
2883                         subprog /* subprog number within this prog */);
2884
2885         /* Transfer references to the callee */
2886         err = transfer_reference_state(callee, caller);
2887         if (err)
2888                 return err;
2889
2890         /* copy r1 - r5 args that callee can access.  The copy includes parent
2891          * pointers, which connects us up to the liveness chain
2892          */
2893         for (i = BPF_REG_1; i <= BPF_REG_5; i++)
2894                 callee->regs[i] = caller->regs[i];
2895
2896         /* after the call registers r0 - r5 were scratched */
2897         for (i = 0; i < CALLER_SAVED_REGS; i++) {
2898                 mark_reg_not_init(env, caller->regs, caller_saved[i]);
2899                 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
2900         }
2901
2902         /* only increment it after check_reg_arg() finished */
2903         state->curframe++;
2904
2905         /* and go analyze first insn of the callee */
2906         *insn_idx = target_insn;
2907
2908         if (env->log.level) {
2909                 verbose(env, "caller:\n");
2910                 print_verifier_state(env, caller);
2911                 verbose(env, "callee:\n");
2912                 print_verifier_state(env, callee);
2913         }
2914         return 0;
2915 }
2916
2917 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
2918 {
2919         struct bpf_verifier_state *state = env->cur_state;
2920         struct bpf_func_state *caller, *callee;
2921         struct bpf_reg_state *r0;
2922         int err;
2923
2924         callee = state->frame[state->curframe];
2925         r0 = &callee->regs[BPF_REG_0];
2926         if (r0->type == PTR_TO_STACK) {
2927                 /* technically it's ok to return caller's stack pointer
2928                  * (or caller's caller's pointer) back to the caller,
2929                  * since these pointers are valid. Only current stack
2930                  * pointer will be invalid as soon as function exits,
2931                  * but let's be conservative
2932                  */
2933                 verbose(env, "cannot return stack pointer to the caller\n");
2934                 return -EINVAL;
2935         }
2936
2937         state->curframe--;
2938         caller = state->frame[state->curframe];
2939         /* return to the caller whatever r0 had in the callee */
2940         caller->regs[BPF_REG_0] = *r0;
2941
2942         /* Transfer references to the caller */
2943         err = transfer_reference_state(caller, callee);
2944         if (err)
2945                 return err;
2946
2947         *insn_idx = callee->callsite + 1;
2948         if (env->log.level) {
2949                 verbose(env, "returning from callee:\n");
2950                 print_verifier_state(env, callee);
2951                 verbose(env, "to caller at %d:\n", *insn_idx);
2952                 print_verifier_state(env, caller);
2953         }
2954         /* clear everything in the callee */
2955         free_func_state(callee);
2956         state->frame[state->curframe + 1] = NULL;
2957         return 0;
2958 }
2959
2960 static void do_refine_retval_range(struct bpf_reg_state *regs, int ret_type,
2961                                    int func_id,
2962                                    struct bpf_call_arg_meta *meta)
2963 {
2964         struct bpf_reg_state *ret_reg = &regs[BPF_REG_0];
2965
2966         if (ret_type != RET_INTEGER ||
2967             (func_id != BPF_FUNC_get_stack &&
2968              func_id != BPF_FUNC_probe_read_str))
2969                 return;
2970
2971         ret_reg->smax_value = meta->msize_smax_value;
2972         ret_reg->umax_value = meta->msize_umax_value;
2973         __reg_deduce_bounds(ret_reg);
2974         __reg_bound_offset(ret_reg);
2975 }
2976
2977 static int
2978 record_func_map(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,
2979                 int func_id, int insn_idx)
2980 {
2981         struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
2982
2983         if (func_id != BPF_FUNC_tail_call &&
2984             func_id != BPF_FUNC_map_lookup_elem &&
2985             func_id != BPF_FUNC_map_update_elem &&
2986             func_id != BPF_FUNC_map_delete_elem &&
2987             func_id != BPF_FUNC_map_push_elem &&
2988             func_id != BPF_FUNC_map_pop_elem &&
2989             func_id != BPF_FUNC_map_peek_elem)
2990                 return 0;
2991
2992         if (meta->map_ptr == NULL) {
2993                 verbose(env, "kernel subsystem misconfigured verifier\n");
2994                 return -EINVAL;
2995         }
2996
2997         if (!BPF_MAP_PTR(aux->map_state))
2998                 bpf_map_ptr_store(aux, meta->map_ptr,
2999                                   meta->map_ptr->unpriv_array);
3000         else if (BPF_MAP_PTR(aux->map_state) != meta->map_ptr)
3001                 bpf_map_ptr_store(aux, BPF_MAP_PTR_POISON,
3002                                   meta->map_ptr->unpriv_array);
3003         return 0;
3004 }
3005
3006 static int check_reference_leak(struct bpf_verifier_env *env)
3007 {
3008         struct bpf_func_state *state = cur_func(env);
3009         int i;
3010
3011         for (i = 0; i < state->acquired_refs; i++) {
3012                 verbose(env, "Unreleased reference id=%d alloc_insn=%d\n",
3013                         state->refs[i].id, state->refs[i].insn_idx);
3014         }
3015         return state->acquired_refs ? -EINVAL : 0;
3016 }
3017
3018 static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
3019 {
3020         const struct bpf_func_proto *fn = NULL;
3021         struct bpf_reg_state *regs;
3022         struct bpf_call_arg_meta meta;
3023         bool changes_data;
3024         int i, err;
3025
3026         /* find function prototype */
3027         if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
3028                 verbose(env, "invalid func %s#%d\n", func_id_name(func_id),
3029                         func_id);
3030                 return -EINVAL;
3031         }
3032
3033         if (env->ops->get_func_proto)
3034                 fn = env->ops->get_func_proto(func_id, env->prog);
3035         if (!fn) {
3036                 verbose(env, "unknown func %s#%d\n", func_id_name(func_id),
3037                         func_id);
3038                 return -EINVAL;
3039         }
3040
3041         /* eBPF programs must be GPL compatible to use GPL-ed functions */
3042         if (!env->prog->gpl_compatible && fn->gpl_only) {
3043                 verbose(env, "cannot call GPL-restricted function from non-GPL compatible program\n");
3044                 return -EINVAL;
3045         }
3046
3047         /* With LD_ABS/IND some JITs save/restore skb from r1. */
3048         changes_data = bpf_helper_changes_pkt_data(fn->func);
3049         if (changes_data && fn->arg1_type != ARG_PTR_TO_CTX) {
3050                 verbose(env, "kernel subsystem misconfigured func %s#%d: r1 != ctx\n",
3051                         func_id_name(func_id), func_id);
3052                 return -EINVAL;
3053         }
3054
3055         memset(&meta, 0, sizeof(meta));
3056         meta.pkt_access = fn->pkt_access;
3057
3058         err = check_func_proto(fn, func_id);
3059         if (err) {
3060                 verbose(env, "kernel subsystem misconfigured func %s#%d\n",
3061                         func_id_name(func_id), func_id);
3062                 return err;
3063         }
3064
3065         meta.func_id = func_id;
3066         /* check args */
3067         err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta);
3068         if (err)
3069                 return err;
3070         err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &meta);
3071         if (err)
3072                 return err;
3073         err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &meta);
3074         if (err)
3075                 return err;
3076         err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &meta);
3077         if (err)
3078                 return err;
3079         err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &meta);
3080         if (err)
3081                 return err;
3082
3083         err = record_func_map(env, &meta, func_id, insn_idx);
3084         if (err)
3085                 return err;
3086
3087         /* Mark slots with STACK_MISC in case of raw mode, stack offset
3088          * is inferred from register state.
3089          */
3090         for (i = 0; i < meta.access_size; i++) {
3091                 err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B,
3092                                        BPF_WRITE, -1, false);
3093                 if (err)
3094                         return err;
3095         }
3096
3097         if (func_id == BPF_FUNC_tail_call) {
3098                 err = check_reference_leak(env);
3099                 if (err) {
3100                         verbose(env, "tail_call would lead to reference leak\n");
3101                         return err;
3102                 }
3103         } else if (is_release_function(func_id)) {
3104                 err = release_reference(env, meta.ref_obj_id);
3105                 if (err) {
3106                         verbose(env, "func %s#%d reference has not been acquired before\n",
3107                                 func_id_name(func_id), func_id);
3108                         return err;
3109                 }
3110         }
3111
3112         regs = cur_regs(env);
3113
3114         /* check that flags argument in get_local_storage(map, flags) is 0,
3115          * this is required because get_local_storage() can't return an error.
3116          */
3117         if (func_id == BPF_FUNC_get_local_storage &&
3118             !register_is_null(&regs[BPF_REG_2])) {
3119                 verbose(env, "get_local_storage() doesn't support non-zero flags\n");
3120                 return -EINVAL;
3121         }
3122
3123         /* reset caller saved regs */
3124         for (i = 0; i < CALLER_SAVED_REGS; i++) {
3125                 mark_reg_not_init(env, regs, caller_saved[i]);
3126                 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
3127         }
3128
3129         /* update return register (already marked as written above) */
3130         if (fn->ret_type == RET_INTEGER) {
3131                 /* sets type to SCALAR_VALUE */
3132                 mark_reg_unknown(env, regs, BPF_REG_0);
3133         } else if (fn->ret_type == RET_VOID) {
3134                 regs[BPF_REG_0].type = NOT_INIT;
3135         } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL ||
3136                    fn->ret_type == RET_PTR_TO_MAP_VALUE) {
3137                 /* There is no offset yet applied, variable or fixed */
3138                 mark_reg_known_zero(env, regs, BPF_REG_0);
3139                 /* remember map_ptr, so that check_map_access()
3140                  * can check 'value_size' boundary of memory access
3141                  * to map element returned from bpf_map_lookup_elem()
3142                  */
3143                 if (meta.map_ptr == NULL) {
3144                         verbose(env,
3145                                 "kernel subsystem misconfigured verifier\n");
3146                         return -EINVAL;
3147                 }
3148                 regs[BPF_REG_0].map_ptr = meta.map_ptr;
3149                 if (fn->ret_type == RET_PTR_TO_MAP_VALUE) {
3150                         regs[BPF_REG_0].type = PTR_TO_MAP_VALUE;
3151                         if (map_value_has_spin_lock(meta.map_ptr))
3152                                 regs[BPF_REG_0].id = ++env->id_gen;
3153                 } else {
3154                         regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
3155                         regs[BPF_REG_0].id = ++env->id_gen;
3156                 }
3157         } else if (fn->ret_type == RET_PTR_TO_SOCKET_OR_NULL) {
3158                 mark_reg_known_zero(env, regs, BPF_REG_0);
3159                 regs[BPF_REG_0].type = PTR_TO_SOCKET_OR_NULL;
3160                 if (is_acquire_function(func_id)) {
3161                         int id = acquire_reference_state(env, insn_idx);
3162
3163                         if (id < 0)
3164                                 return id;
3165                         /* For mark_ptr_or_null_reg() */
3166                         regs[BPF_REG_0].id = id;
3167                         /* For release_reference() */
3168                         regs[BPF_REG_0].ref_obj_id = id;
3169                 } else {
3170                         /* For mark_ptr_or_null_reg() */
3171                         regs[BPF_REG_0].id = ++env->id_gen;
3172                 }
3173         } else if (fn->ret_type == RET_PTR_TO_TCP_SOCK_OR_NULL) {
3174                 mark_reg_known_zero(env, regs, BPF_REG_0);
3175                 regs[BPF_REG_0].type = PTR_TO_TCP_SOCK_OR_NULL;
3176                 regs[BPF_REG_0].id = ++env->id_gen;
3177         } else {
3178                 verbose(env, "unknown return type %d of func %s#%d\n",
3179                         fn->ret_type, func_id_name(func_id), func_id);
3180                 return -EINVAL;
3181         }
3182
3183         if (is_ptr_cast_function(func_id))
3184                 /* For release_reference() */
3185                 regs[BPF_REG_0].ref_obj_id = meta.ref_obj_id;
3186
3187         do_refine_retval_range(regs, fn->ret_type, func_id, &meta);
3188
3189         err = check_map_func_compatibility(env, meta.map_ptr, func_id);
3190         if (err)
3191                 return err;
3192
3193         if (func_id == BPF_FUNC_get_stack && !env->prog->has_callchain_buf) {
3194                 const char *err_str;
3195
3196 #ifdef CONFIG_PERF_EVENTS
3197                 err = get_callchain_buffers(sysctl_perf_event_max_stack);
3198                 err_str = "cannot get callchain buffer for func %s#%d\n";
3199 #else
3200                 err = -ENOTSUPP;
3201                 err_str = "func %s#%d not supported without CONFIG_PERF_EVENTS\n";
3202 #endif
3203                 if (err) {
3204                         verbose(env, err_str, func_id_name(func_id), func_id);
3205                         return err;
3206                 }
3207
3208                 env->prog->has_callchain_buf = true;
3209         }
3210
3211         if (changes_data)
3212                 clear_all_pkt_pointers(env);
3213         return 0;
3214 }
3215
3216 static bool signed_add_overflows(s64 a, s64 b)
3217 {
3218         /* Do the add in u64, where overflow is well-defined */
3219         s64 res = (s64)((u64)a + (u64)b);
3220
3221         if (b < 0)
3222                 return res > a;
3223         return res < a;
3224 }
3225
3226 static bool signed_sub_overflows(s64 a, s64 b)
3227 {
3228         /* Do the sub in u64, where overflow is well-defined */
3229         s64 res = (s64)((u64)a - (u64)b);
3230
3231         if (b < 0)
3232                 return res < a;
3233         return res > a;
3234 }
3235
3236 static bool check_reg_sane_offset(struct bpf_verifier_env *env,
3237                                   const str