| blob | 90bf46787603a9c30c3dad3a4aa578af2b475c77 |
1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
2 * Copyright (c) 2016 Facebook
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 */
13 #include <linux/kernel.h>
14 #include <linux/types.h>
15 #include <linux/slab.h>
16 #include <linux/bpf.h>
17 #include <linux/bpf_verifier.h>
18 #include <linux/filter.h>
19 #include <net/netlink.h>
20 #include <linux/file.h>
21 #include <linux/vmalloc.h>
22 #include <linux/stringify.h>
24 /* bpf_check() is a static code analyzer that walks eBPF program
25 * instruction by instruction and updates register/stack state.
26 * All paths of conditional branches are analyzed until 'bpf_exit' insn.
27 *
28 * The first pass is depth-first-search to check that the program is a DAG.
29 * It rejects the following programs:
30 * - larger than BPF_MAXINSNS insns
31 * - if loop is present (detected via back-edge)
32 * - unreachable insns exist (shouldn't be a forest. program = one function)
33 * - out of bounds or malformed jumps
34 * The second pass is all possible path descent from the 1st insn.
35 * Since it's analyzing all pathes through the program, the length of the
36 * analysis is limited to 64k insn, which may be hit even if total number of
37 * insn is less then 4K, but there are too many branches that change stack/regs.
38 * Number of 'branches to be analyzed' is limited to 1k
39 *
40 * On entry to each instruction, each register has a type, and the instruction
41 * changes the types of the registers depending on instruction semantics.
42 * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is
43 * copied to R1.
44 *
45 * All registers are 64-bit.
46 * R0 - return register
47 * R1-R5 argument passing registers
48 * R6-R9 callee saved registers
49 * R10 - frame pointer read-only
50 *
51 * At the start of BPF program the register R1 contains a pointer to bpf_context
52 * and has type PTR_TO_CTX.
53 *
54 * Verifier tracks arithmetic operations on pointers in case:
55 * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
56 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20),
57 * 1st insn copies R10 (which has FRAME_PTR) type into R1
58 * and 2nd arithmetic instruction is pattern matched to recognize
59 * that it wants to construct a pointer to some element within stack.
60 * So after 2nd insn, the register R1 has type PTR_TO_STACK
61 * (and -20 constant is saved for further stack bounds checking).
62 * Meaning that this reg is a pointer to stack plus known immediate constant.
63 *
64 * Most of the time the registers have UNKNOWN_VALUE type, which
65 * means the register has some value, but it's not a valid pointer.
66 * (like pointer plus pointer becomes UNKNOWN_VALUE type)
67 *
68 * When verifier sees load or store instructions the type of base register
69 * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, FRAME_PTR. These are three pointer
70 * types recognized by check_mem_access() function.
71 *
72 * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value'
73 * and the range of [ptr, ptr + map's value_size) is accessible.
74 *
75 * registers used to pass values to function calls are checked against
76 * function argument constraints.
77 *
78 * ARG_PTR_TO_MAP_KEY is one of such argument constraints.
79 * It means that the register type passed to this function must be
80 * PTR_TO_STACK and it will be used inside the function as
81 * 'pointer to map element key'
82 *
83 * For example the argument constraints for bpf_map_lookup_elem():
84 * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
85 * .arg1_type = ARG_CONST_MAP_PTR,
86 * .arg2_type = ARG_PTR_TO_MAP_KEY,
87 *
88 * ret_type says that this function returns 'pointer to map elem value or null'
89 * function expects 1st argument to be a const pointer to 'struct bpf_map' and
90 * 2nd argument should be a pointer to stack, which will be used inside
91 * the helper function as a pointer to map element key.
92 *
93 * On the kernel side the helper function looks like:
94 * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
95 * {
96 * struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
97 * void *key = (void *) (unsigned long) r2;
98 * void *value;
99 *
100 * here kernel can access 'key' and 'map' pointers safely, knowing that
101 * [key, key + map->key_size) bytes are valid and were initialized on
102 * the stack of eBPF program.
103 * }
104 *
105 * Corresponding eBPF program may look like:
106 * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR
107 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK
108 * BPF_LD_MAP_FD(BPF_REG_1, map_fd), // after this insn R1 type is CONST_PTR_TO_MAP
109 * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
110 * here verifier looks at prototype of map_lookup_elem() and sees:
111 * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok,
112 * Now verifier knows that this map has key of R1->map_ptr->key_size bytes
113 *
114 * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far,
115 * Now verifier checks that [R2, R2 + map's key_size) are within stack limits
116 * and were initialized prior to this call.
117 * If it's ok, then verifier allows this BPF_CALL insn and looks at
118 * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets
119 * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function
120 * returns ether pointer to map value or NULL.
121 *
122 * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off'
123 * insn, the register holding that pointer in the true branch changes state to
124 * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false
125 * branch. See check_cond_jmp_op().
126 *
127 * After the call R0 is set to return type of the function and registers R1-R5
128 * are set to NOT_INIT to indicate that they are no longer readable.
129 */
131 /* verifier_state + insn_idx are pushed to stack when branch is encountered */
133 /* verifer state is 'st'
134 * before processing instruction 'insn_idx'
135 * and after processing instruction 'prev_insn_idx'
136 */
141 };
143 #define BPF_COMPLEXITY_LIMIT_INSNS 65536
144 #define BPF_COMPLEXITY_LIMIT_STACK 1024
152 };
154 /* verbose verifier prints what it's seeing
155 * bpf_check() is called under lock, so no race to access these global vars
156 */
162 /* log_level controls verbosity level of eBPF verifier.
163 * verbose() is used to dump the verification trace to the log, so the user
164 * can figure out what's wrong with the program
165 */
167 {
176 }
178 /* string representation of 'enum bpf_reg_type' */
192 };
194 #define __BPF_FUNC_STR_FN(x) [BPF_FUNC_ ## x] = __stringify(bpf_ ## x)
197 };
198 #undef __BPF_FUNC_STR_FN
201 {
206 else
208 }
211 {
242 }
247 }
249 }
260 };
277 };
284 };
297 };
300 {
311 else
331 else
337 }
347 }
369 }
391 }
394 }
395 }
398 {
414 }
418 {
434 }
436 err:
437 /* pop all elements and return */
440 }
442 #define CALLER_SAVED_REGS 6
445 };
448 {
456 }
458 /* frame pointer */
461 /* 1st arg to a function */
463 }
466 {
470 }
473 {
476 }
479 {
482 }
485 u32 regno)
486 {
489 }
494 DST_OP_NO_MARK /* same as above, check only, don't mark */
495 };
499 {
503 }
506 /* check whether register used as source operand can be read */
510 }
512 /* check whether register used as dest operand can be written to */
516 }
519 }
521 }
524 {
533 else
535 }
538 {
552 }
553 }
555 /* check_stack_read/write functions track spill/fill of registers,
556 * stack boundary and alignment are checked in check_mem_access()
557 */
560 {
562 /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
563 * so it's aligned access and [off, off + size) are within stack limits
564 */
569 /* register containing pointer is being spilled into stack */
573 }
575 /* save register state */
582 /* regular write of data into stack */
588 }
590 }
594 {
604 }
609 }
610 }
613 /* restore register state from stack */
623 }
624 }
626 /* have read misc data from the stack */
628 value_regno);
630 }
631 }
633 /* check read/write into map element returned by bpf_map_lookup_elem() */
636 {
643 }
645 }
647 /* check read/write into an adjusted map element */
650 {
655 /* We adjusted the register to this map value, so we
656 * need to change off and size to min_value and max_value
657 * respectively to make sure our theoretical access will be
658 * safe.
659 */
663 /* The minimum value is only important with signed
664 * comparisons where we can't assume the floor of a
665 * value is 0. If we are using signed variables for our
666 * index'es we need to make sure that whatever we use
667 * will have a set floor within our range.
668 */
671 regno);
673 }
677 regno);
679 }
681 /* If we haven't set a max value then we need to bail
682 * since we can't be sure we won't do bad things.
683 */
686 regno);
688 }
690 }
692 #define MAX_PACKET_OFF 0xffff
697 {
701 /* dst_input() and dst_output() can't write for now */
704 /* fallthrough */
716 }
717 }
721 {
730 }
732 }
734 /* check access to 'struct bpf_context' fields */
737 {
738 /* for analyzer ctx accesses are already validated and converted */
744 /* remember the offset of last byte accessed in ctx */
748 }
752 }
755 {
765 }
766 }
770 {
778 }
779 }
782 /* misaligned access to packet is ok on x86,arm,arm64 */
788 }
790 /* skb->data is NET_IP_ALIGN-ed */
796 }
798 }
800 /* check whether memory at (regno + off) is accessible for t = (read | write)
801 * if t==write, value_regno is a register which value is stored into memory
802 * if t==read, value_regno is a register which will receive the value from memory
803 * if t==write && value_regno==-1, some unknown value is stored into memory
804 * if t==read && value_regno==-1, don't care what we read from memory
805 */
809 {
831 }
835 else
839 value_regno);
848 }
852 value_regno);
853 /* note that reg.[id|off|range] == 0 */
855 }
861 }
868 }
872 }
877 }
882 }
886 value_regno);
891 }
895 /* 1 or 2 byte load zero-extends, determine the number of
896 * zero upper bits. Not doing it fo 4 byte load, since
897 * such values cannot be added to ptr_to_packet anyway.
898 */
900 }
902 }
905 {
913 }
915 /* check src1 operand */
920 /* check src2 operand */
925 /* check whether atomic_add can read the memory */
931 /* check whether atomic_add can write into the same memory */
934 }
936 /* when register 'regno' is passed into function that will read 'access_size'
937 * bytes from that pointer, make sure that it's within stack boundary
938 * and all elements of stack are initialized
939 */
943 {
958 }
966 }
972 }
979 }
980 }
982 }
987 {
1000 }
1001 }
1006 {
1017 }
1023 }
1025 }
1031 }
1041 /* One exception. Allow UNKNOWN_VALUE registers when the
1042 * boundaries are known and don't cause unsafe memory accesses
1043 */
1057 /* One exception here. In case function allows for NULL to be
1058 * passed in as argument, it's a CONST_IMM type. Final test
1059 * happens during stack boundary checking.
1060 */
1070 }
1073 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
1076 /* bpf_map_xxx(..., map_ptr, ..., key) call:
1077 * check that [key, key + map->key_size) are within
1078 * stack limits and initialized
1079 */
1081 /* in function declaration map_ptr must come before
1082 * map_key, so that it's verified and known before
1083 * we have to check map_key here. Otherwise it means
1084 * that kernel subsystem misconfigured verifier
1085 */
1088 }
1092 else
1097 /* bpf_map_xxx(..., map_ptr, ..., value) call:
1098 * check [value, value + map->value_size) validity
1099 */
1101 /* kernel subsystem misconfigured verifier */
1104 }
1108 else
1116 /* bpf_xxx(..., buf, len) call will access 'len' bytes
1117 * from stack pointer 'buf'. Check it
1118 * note: regno == len, regno - 1 == buf
1119 */
1121 /* kernel subsystem misconfigured verifier */
1124 }
1126 /* If the register is UNKNOWN_VALUE, the access check happens
1127 * using its boundaries. Otherwise, just use its imm
1128 */
1130 /* For unprivileged variable accesses, disable raw
1131 * mode so that the program is required to
1132 * initialize all the memory that the helper could
1133 * just partially fill up.
1134 */
1139 regno);
1141 }
1145 zero_size_allowed,
1146 meta);
1149 }
1153 regno);
1155 }
1162 /* register is CONST_IMM */
1165 }
1166 }
1169 err_type:
1173 }
1176 {
1180 /* We need a two way check, first is from map perspective ... */
1202 }
1204 /* ... and second from the function itself. */
1226 }
1229 error:
1233 }
1236 {
1240 count++;
1242 count++;
1244 count++;
1246 count++;
1248 count++;
1251 }
1254 {
1273 }
1274 }
1277 {
1286 /* find function prototype */
1290 }
1298 }
1300 /* eBPF programs must be GPL compatible to use GPL-ed functions */
1304 }
1311 /* We only support one arg being in raw mode at the moment, which
1312 * is sufficient for the helper functions we have right now.
1313 */
1319 }
1321 /* check args */
1338 /* Mark slots with STACK_MISC in case of raw mode, stack offset
1339 * is inferred from register state.
1340 */
1345 }
1347 /* reset caller saved regs */
1352 }
1354 /* update return register */
1362 /* remember map_ptr, so that check_map_access()
1363 * can check 'value_size' boundary of memory access
1364 * to map element returned from bpf_map_lookup_elem()
1365 */
1369 }
1377 }
1386 }
1390 {
1395 s32 imm;
1398 /* pkt_ptr += imm */
1401 add_imm:
1405 }
1409 imm);
1411 }
1412 /* a constant was added to pkt_ptr.
1413 * Remember it while keeping the same 'id'
1414 */
1418 /* R6=pkt(id=0,off=0,r=62) R7=imm22; r7 += r6 */
1422 /* if the checks below reject it, the copy won't matter,
1423 * since we're rejecting the whole program. If all ok,
1424 * then imm22 state will be added to r7
1425 * and r7 will be pkt(id=0,off=22,r=62) while
1426 * r6 will stay as pkt(id=0,off=0,r=62)
1427 */
1428 }
1431 /* pkt_ptr += reg where reg is known constant */
1434 }
1435 /* disallow pkt_ptr += reg
1436 * if reg is not uknown_value with guaranteed zero upper bits
1437 * otherwise pkt_ptr may overflow and addition will become
1438 * subtraction which is not allowed
1439 */
1444 }
1449 }
1450 /* dst_reg stays as pkt_ptr type and since some positive
1451 * integer value was added to the pointer, increment its 'id'
1452 */
1455 /* something was added to pkt_ptr, set range and off to zero */
1458 }
1460 }
1463 {
1467 s64 imm_log2;
1469 /* for type == UNKNOWN_VALUE:
1470 * imm > 0 -> number of zero upper bits
1471 * imm == 0 -> don't track which is the same as all bits can be non-zero
1472 */
1479 /* dreg += sreg
1480 * where both have zero upper bits. Adding them
1481 * can only result making one more bit non-zero
1482 * in the larger value.
1483 * Ex. 0xffff (imm=48) + 1 (imm=63) = 0x10000 (imm=47)
1484 * 0xffff (imm=48) + 0xffff = 0x1fffe (imm=47)
1485 */
1489 }
1492 /* dreg += sreg
1493 * where dreg has zero upper bits and sreg is const.
1494 * Adding them can only result making one more bit
1495 * non-zero in the larger value.
1496 */
1501 }
1502 /* all other cases non supported yet, just mark dst_reg */
1505 }
1507 /* sign extend 32-bit imm into 64-bit to make sure that
1508 * negative values occupy bit 63. Note ilog2() would have
1509 * been incorrect, since sizeof(insn->imm) == 4
1510 */
1514 /* reg <<= imm
1515 * if reg was a result of 2 byte load, then its imm == 48
1516 * which means that upper 48 bits are zero and shifting this reg
1517 * left by 4 would mean that upper 44 bits are still zero
1518 */
1521 /* reg *= imm
1522 * if multiplying by 14 subtract 4
1523 * This is conservative calculation of upper zero bits.
1524 * It's not trying to special case insn->imm == 1 or 0 cases
1525 */
1528 /* reg &= imm */
1531 /* reg += imm */
1535 /* reg >>= imm
1536 * which means that after right shift, upper bits will be zero
1537 * note that verifier already checked that
1538 * 0 <= imm < 64 for shift insn
1539 */
1542 /* some dumb code did:
1543 * r2 = *(u32 *)mem;
1544 * r2 >>= 32;
1545 * and all bits are zero now */
1548 /* all other alu ops, means that we don't know what will
1549 * happen to the value, mark it with unknown number of zero bits
1550 */
1552 }
1555 /* all 64 bits of the register can contain non-zero bits
1556 * and such value cannot be added to ptr_to_packet, since it
1557 * may overflow, mark it as unknown to avoid further eval
1558 */
1560 }
1562 }
1566 {
1573 /* dst_reg->type == CONST_IMM here. Simulate execution of insns
1574 * containing ALU ops. Don't care about overflow or negative
1575 * values, just add/sub/... them; registers are in u64.
1576 */
1615 }
1618 out:
1620 }
1623 {
1629 }
1633 {
1645 /* If the source register is a random pointer then the
1646 * min_value/max_value values represent the range of the known
1647 * accesses into that value, not the actual min/max value of the
1648 * register itself. In this case we have to reset the reg range
1649 * values so we know it is not safe to look at.
1650 */
1655 }
1659 }
1661 /* We don't know anything about what was done to this register, mark it
1662 * as unknown.
1663 */
1668 }
1670 /* If one of our values was at the end of our ranges then we can't just
1671 * do our normal operations to the register, we need to set the values
1672 * to the min/max since they are undefined.
1673 */
1699 /* Disallow AND'ing of negative numbers, ain't nobody got time
1700 * for that. Otherwise the minimum is 0 and the max is the max
1701 * value we could AND against.
1702 */
1705 else
1710 /* Gotta have special overflow logic here, if we're shifting
1711 * more than MAX_RANGE then just assume we have an invalid
1712 * range.
1713 */
1725 /* RSH by a negative number is undefined, and the BPF_RSH is an
1726 * unsigned shift, so make the appropriate casts.
1727 */
1730 else
1739 }
1742 }
1744 /* check validity of 32-bit and 64-bit arithmetic operations */
1746 {
1758 }
1764 }
1765 }
1767 /* check src operand */
1776 }
1778 /* check dest operand */
1789 }
1791 /* check src operand */
1799 }
1800 }
1802 /* check dest operand */
1807 /* we are setting our register to something new, we need to
1808 * reset its range values.
1809 */
1814 /* case: R1 = R2
1815 * copy register state to dest reg
1816 */
1823 }
1825 }
1827 /* case: R = imm
1828 * remember the value we stored into this reg
1829 */
1834 }
1846 }
1847 /* check src1 operand */
1855 }
1856 }
1858 /* check src2 operand */
1867 }
1876 }
1877 }
1879 /* check dest operand */
1886 /* first we want to adjust our ranges. */
1889 /* pattern match 'bpf_add Rx, imm' instruction */
1900 /* ptr_to_packet += K|X */
1905 /* unknown += K|X */
1910 /* reg_imm += K|X */
1921 }
1923 /* If we did pointer math on a map value then just set it to our
1924 * PTR_TO_MAP_VALUE_ADJ type so we can deal with any stores or
1925 * loads to this register appropriately, otherwise just mark the
1926 * register as unknown.
1927 */
1932 else
1934 }
1937 }
1941 {
1945 /* LLVM can generate two kind of checks:
1946 *
1947 * Type 1:
1948 *
1949 * r2 = r3;
1950 * r2 += 8;
1951 * if (r2 > pkt_end) goto <handle exception>
1952 * <access okay>
1953 *
1954 * Where:
1955 * r2 == dst_reg, pkt_end == src_reg
1956 * r2=pkt(id=n,off=8,r=0)
1957 * r3=pkt(id=n,off=0,r=0)
1958 *
1959 * Type 2:
1960 *
1961 * r2 = r3;
1962 * r2 += 8;
1963 * if (pkt_end >= r2) goto <access okay>
1964 * <handle exception>
1965 *
1966 * Where:
1967 * pkt_end == dst_reg, r2 == src_reg
1968 * r2=pkt(id=n,off=8,r=0)
1969 * r3=pkt(id=n,off=0,r=0)
1970 *
1971 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8)
1972 * so that range of bytes [r3, r3 + 8) is safe to access.
1973 */
1985 }
1986 }
1988 /* Adjusts the register min/max values in the case that the dst_reg is the
1989 * variable register that we are working on, and src_reg is a constant or we're
1990 * simply doing a BPF_K check.
1991 */
1994 u8 opcode)
1995 {
1998 /* If this is false then we know nothing Jon Snow, but if it is
1999 * true then we know for sure.
2000 */
2004 /* If this is true we know nothing Jon Snow, but if it is false
2005 * we know the value for sure;
2006 */
2010 /* Unsigned comparison, the minimum value is 0. */
2012 /* fallthrough */
2014 /* If this is false then we know the maximum val is val,
2015 * otherwise we know the min val is val+1.
2016 */
2021 /* Unsigned comparison, the minimum value is 0. */
2023 /* fallthrough */
2025 /* If this is false then we know the maximum value is val - 1,
2026 * otherwise we know the mimimum value is val.
2027 */
2033 }
2037 }
2039 /* Same as above, but for the case that dst_reg is a CONST_IMM reg and src_reg
2040 * is the variable reg.
2041 */
2044 u8 opcode)
2045 {
2048 /* If this is false then we know nothing Jon Snow, but if it is
2049 * true then we know for sure.
2050 */
2054 /* If this is true we know nothing Jon Snow, but if it is false
2055 * we know the value for sure;
2056 */
2060 /* Unsigned comparison, the minimum value is 0. */
2062 /* fallthrough */
2064 /*
2065 * If this is false, then the val is <= the register, if it is
2066 * true the register <= to the val.
2067 */
2072 /* Unsigned comparison, the minimum value is 0. */
2074 /* fallthrough */
2076 /* If this is false then constant < register, if it is true then
2077 * the register < constant.
2078 */
2084 }
2088 }
2092 {
2097 /* We don't need id from this point onwards anymore, thus we
2098 * should better reset it, so that state pruning has chances
2099 * to take effect.
2100 */
2104 }
2105 }
2107 /* The logic is similar to find_good_pkt_pointers(), both could eventually
2108 * be folded together at some point.
2109 */
2112 {
2124 }
2125 }
2129 {
2138 }
2144 }
2146 /* check src1 operand */
2155 }
2160 }
2161 }
2163 /* check src2 operand */
2170 /* detect if R == 0 where R was initialized to zero earlier */
2175 /* if (imm == imm) goto pc+off;
2176 * only follow the goto, ignore fall-through
2177 */
2181 /* if (imm != imm) goto pc+off;
2182 * only follow fall-through branch, since
2183 * that's where the program will go
2184 */
2186 }
2187 }
2193 /* detect if we are comparing against a constant value so we can adjust
2194 * our min/max values for our dst register.
2195 */
2200 opcode);
2204 opcode);
2208 }
2210 /* detect if R == 0 where R is returned from bpf_map_lookup_elem() */
2214 /* Mark all identical map registers in each branch as either
2215 * safe or unknown depending R == 0 or R != 0 conditional.
2216 */
2232 }
2236 }
2238 /* return the map pointer stored inside BPF_LD_IMM64 instruction */
2240 {
2244 }
2246 /* verify BPF_LD_IMM64 instruction */
2248 {
2255 }
2259 }
2271 }
2273 /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */
2279 }
2282 {
2290 }
2291 }
2293 /* verify safety of LD_ABS|LD_IND instructions:
2294 * - they can only appear in the programs where ctx == skb
2295 * - since they are wrappers of function calls, they scratch R1-R5 registers,
2296 * preserve R6-R9, and store return value into R0
2297 *
2298 * Implicit input:
2299 * ctx == skb == R6 == CTX
2300 *
2301 * Explicit input:
2302 * SRC == any register
2303 * IMM == 32-bit immediate
2304 *
2305 * Output:
2306 * R0 - 8/16/32-bit skb data converted to cpu endianness
2307 */
2309 {
2318 }
2325 }
2327 /* check whether implicit source operand (register R6) is readable */
2335 }
2338 /* check explicit source operand */
2342 }
2344 /* reset caller saved regs to unreadable */
2349 }
2351 /* mark destination R0 register as readable, since it contains
2352 * the value fetched from the packet
2353 */
2356 }
2358 /* non-recursive DFS pseudo code
2359 * 1 procedure DFS-iterative(G,v):
2360 * 2 label v as discovered
2361 * 3 let S be a stack
2362 * 4 S.push(v)
2363 * 5 while S is not empty
2364 * 6 t <- S.pop()
2365 * 7 if t is what we're looking for:
2366 * 8 return t
2367 * 9 for all edges e in G.adjacentEdges(t) do
2368 * 10 if edge e is already labelled
2369 * 11 continue with the next edge
2370 * 12 w <- G.adjacentVertex(t,e)
2371 * 13 if vertex w is not discovered and not explored
2372 * 14 label e as tree-edge
2373 * 15 label w as discovered
2374 * 16 S.push(w)
2375 * 17 continue at 5
2376 * 18 else if vertex w is discovered
2377 * 19 label e as back-edge
2378 * 20 else
2379 * 21 // vertex w is explored
2380 * 22 label e as forward- or cross-edge
2381 * 23 label t as explored
2382 * 24 S.pop()
2383 *
2384 * convention:
2385 * 0x10 - discovered
2386 * 0x11 - discovered and fall-through edge labelled
2387 * 0x12 - discovered and fall-through and branch edges labelled
2388 * 0x20 - explored
2389 */
2396 };
2398 #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
2404 /* t, w, e - match pseudo-code above:
2405 * t - index of current instruction
2406 * w - next instruction
2407 * e - edge
2408 */
2410 {
2420 }
2423 /* mark branch target for state pruning */
2427 /* tree-edge */
2438 /* forward- or cross-edge */
2443 }
2445 }
2447 /* non-recursive depth-first-search to detect loops in BPF program
2448 * loop == back-edge in directed graph
2449 */
2451 {
2465 }
2471 peek_stack:
2493 }
2494 /* unconditional jump with single edge */
2501 /* tell verifier to check for equivalent states
2502 * after every call and jump
2503 */
2507 /* conditional jump with two edges */
2519 }
2521 /* all other non-branch instructions with single
2522 * fall-through edge
2523 */
2529 }
2531 mark_explored:
2537 }
2540 check_state:
2546 }
2547 }
2550 err_free:
2554 }
2556 /* the following conditions reduce the number of explored insns
2557 * from ~140k to ~80k for ultra large programs that use a lot of ptr_to_packet
2558 */
2561 {
2565 /* old ptr_to_packet is more conservative, since it allows smaller
2566 * range. Ex:
2567 * old(off=0,r=10) is equal to cur(off=0,r=20), because
2568 * old(off=0,r=10) means that with range=10 the verifier proceeded
2569 * further and found no issues with the program. Now we're in the same
2570 * spot with cur(off=0,r=20), so we're safe too, since anything further
2571 * will only be looking at most 10 bytes after this pointer.
2572 */
2576 /* old(off=20,r=10) is equal to cur(off=22,re=22 or 5 or 0)
2577 * since both cannot be used for packet access and safe(old)
2578 * pointer has smaller off that could be used for further
2579 * 'if (ptr > data_end)' check
2580 * Ex:
2581 * old(off=20,r=10) and cur(off=22,r=22) and cur(off=22,r=0) mean
2582 * that we cannot access the packet.
2583 * The safe range is:
2584 * [ptr, ptr + range - off)
2585 * so whenever off >=range, it means no safe bytes from this pointer.
2586 * When comparing old->off <= cur->off, it means that older code
2587 * went with smaller offset and that offset was later
2588 * used to figure out the safe range after 'if (ptr > data_end)' check
2589 * Say, 'old' state was explored like:
2590 * ... R3(off=0, r=0)
2591 * R4 = R3 + 20
2592 * ... now R4(off=20,r=0) <-- here
2593 * if (R4 > data_end)
2594 * ... R4(off=20,r=20), R3(off=0,r=20) and R3 can be used to access.
2595 * ... the code further went all the way to bpf_exit.
2596 * Now the 'cur' state at the mark 'here' has R4(off=30,r=0).
2597 * old_R4(off=20,r=0) equal to cur_R4(off=30,r=0), since if the verifier
2598 * goes further, such cur_R4 will give larger safe packet range after
2599 * 'if (R4 > data_end)' and all further insn were already good with r=20,
2600 * so they will be good with r=30 and we can prune the search.
2601 */
2607 }
2609 /* compare two verifier states
2610 *
2611 * all states stored in state_list are known to be valid, since
2612 * verifier reached 'bpf_exit' instruction through them
2613 *
2614 * this function is called when verifier exploring different branches of
2615 * execution popped from the state stack. If it sees an old state that has
2616 * more strict register state and more strict stack state then this execution
2617 * branch doesn't need to be explored further, since verifier already
2618 * concluded that more strict state leads to valid finish.
2619 *
2620 * Therefore two states are equivalent if register state is more conservative
2621 * and explored stack state is more conservative than the current one.
2622 * Example:
2623 * explored current
2624 * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
2625 * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
2626 *
2627 * In other words if current stack state (one being explored) has more
2628 * valid slots than old one that already passed validation, it means
2629 * the verifier can stop exploring and conclude that current state is valid too
2630 *
2631 * Similarly with registers. If explored state has register type as invalid
2632 * whereas register type in current state is meaningful, it means that
2633 * the current state will reach 'bpf_exit' instruction safely
2634 */
2638 {
2650 /* If the ranges were not the same, but everything else was and
2651 * we didn't do a variable access into a map then we are a-ok.
2652 */
2657 /* If we didn't map access then again we don't care about the
2658 * mismatched range values and it's ok if our old type was
2659 * UNKNOWN and we didn't go to a NOT_INIT'ed reg.
2660 */
2671 }
2677 /* Ex: old explored (safe) state has STACK_SPILL in
2678 * this stack slot, but current has has STACK_MISC ->
2679 * this verifier states are not equivalent,
2680 * return false to continue verification of this path
2681 */
2688 /* when explored and current stack slot types are
2689 * the same, check that stored pointers types
2690 * are the same as well.
2691 * Ex: explored safe path could have stored
2692 * (bpf_reg_state) {.type = PTR_TO_STACK, .imm = -8}
2693 * but current path has stored:
2694 * (bpf_reg_state) {.type = PTR_TO_STACK, .imm = -16}
2695 * such verifier states are not equivalent.
2696 * return false to continue verification of this path
2697 */
2699 else
2701 }
2703 }
2706 {
2712 /* this 'insn_idx' instruction wasn't marked, so we will not
2713 * be doing state search here
2714 */
2719 /* reached equivalent register/stack state,
2720 * prune the search
2721 */
2724 }
2726 /* there were no equivalent states, remember current one.
2727 * technically the current state is not proven to be safe yet,
2728 * but it will either reach bpf_exit (which means it's safe) or
2729 * it will be rejected. Since there are no loops, we won't be
2730 * seeing this 'insn_idx' instruction again on the way to bpf_exit
2731 */
2736 /* add new state to the head of linked list */
2741 }
2745 {
2750 }
2753 {
2774 }
2781 insn_processed);
2783 }
2789 /* found equivalent state, can prune the search */
2794 else
2796 }
2798 }
2804 }
2809 }
2823 /* check for reserved fields is already done */
2825 /* check src operand */
2836 /* check that memory (src_reg + off) is readable,
2837 * the state of dst_reg will be updated by this func
2838 */
2847 insn_idx++;
2849 }
2854 /* saw a valid insn
2855 * dst_reg = *(u32 *)(src_reg + off)
2856 * save type to validate intersecting paths
2857 */
2863 /* ABuser program is trying to use the same insn
2864 * dst_reg = *(u32*) (src_reg + off)
2865 * with different pointer types:
2866 * src_reg == ctx in one branch and
2867 * src_reg == stack|map in some other branch.
2868 * Reject it.
2869 */
2872 }
2881 insn_idx++;
2883 }
2885 /* check src1 operand */
2889 /* check src2 operand */
2896 /* check that memory (dst_reg + off) is writeable */
2912 }
2919 }
2920 /* check src operand */
2925 /* check that memory (dst_reg + off) is writeable */
2942 }
2955 }
2967 }
2969 /* eBPF calling convetion is such that R0 is used
2970 * to return the value from eBPF program.
2971 * Make sure that it's readable at this time
2972 * of bpf_exit, which means that program wrote
2973 * something into it earlier
2974 */
2982 }
2984 process_bpf_exit:
2991 }
2996 }
3010 insn_idx++;
3014 }
3019 }
3021 insn_idx++;
3022 }
3026 }
3031 {
3038 }
3040 }
3042 /* look for pseudo eBPF instructions that access map FDs and
3043 * replace them with actual map pointers
3044 */
3046 {
3060 }
3067 }
3078 }
3081 /* valid generic load 64-bit imm */
3087 }
3095 }
3101 }
3103 /* store map pointer inside BPF_LD_IMM64 instruction */
3107 /* check whether we recorded this map already */
3112 }
3117 }
3119 /* hold the map. If the program is rejected by verifier,
3120 * the map will be released by release_maps() or it
3121 * will be used by the valid program until it's unloaded
3122 * and all maps are released in free_bpf_prog_info()
3123 */
3128 }
3132 next_insn:
3133 insn++;
3134 i++;
3135 }
3136 }
3138 /* now all pseudo BPF_LD_IMM64 instructions load valid
3139 * 'struct bpf_map *' into a register instead of user map_fd.
3140 * These pointers will be used later by verifier to validate map access.
3141 */
3143 }
3145 /* drop refcnt of maps used by the rejected program */
3147 {
3152 }
3154 /* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */
3156 {
3164 }
3166 /* single env->prog->insni[off] instruction was replaced with the range
3167 * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying
3168 * [0, off) and [off, end) to new locations, so the patched range stays zero
3169 */
3172 {
3186 }
3190 {
3199 }
3201 /* convert load instructions that access fields of 'struct __sk_buff'
3202 * into sequence of instructions that access fields of 'struct sk_buff'
3203 */
3205 {
3226 }
3227 }
3245 else
3255 }
3263 /* keep walking new program and skip insns we just inserted */
3266 }
3269 }
3271 /* fixup insn->imm field of bpf_call instructions
3272 * and inline eligible helpers as explicit sequence of BPF instructions
3273 *
3274 * this function is called after eBPF program passed verification
3275 */
3277 {
3298 /* mark bpf_tail_call as different opcode to avoid
3299 * conditional branch in the interpeter for every normal
3300 * call and to prevent accidental JITing by JIT compiler
3301 * that doesn't support bpf_tail_call yet
3302 */
3306 }
3317 }
3320 cnt);
3326 /* keep walking new program and skip insns we just inserted */
3330 }
3332 patch_call_imm:
3334 /* all functions that have prototype and verifier allowed
3335 * programs to call them, must be real in-kernel functions
3336 */
3341 }
3343 }
3346 }
3349 {
3364 }
3365 }
3368 }
3371 {
3376 /* 'struct bpf_verifier_env' can be global, but since it's not small,
3377 * allocate/free it every time bpf_check() is called
3378 */
3390 /* grab the mutex to protect few globals used by verifier */
3394 /* user requested verbose verifier output
3395 * and supplied buffer to store the verification trace
3396 */
3403 /* log_* values have to be sane */
3414 }
3422 GFP_USER);
3435 skip_full_check:
3440 /* program is valid, convert *(u32*)(ctx + off) accesses */
3448 /* verifier log exceeded user supplied buffer */
3450 /* fall through to return what was recorded */
3451 }
3453 /* copy verifier log back to user space including trailing zero */
3457 }
3460 /* if program passed verifier, update used_maps in bpf_prog_info */
3463 GFP_KERNEL);
3468 }
3474 /* program is valid. Convert pseudo bpf_ld_imm64 into generic
3475 * bpf_ld_imm64 instructions
3476 */
3478 }
3480 free_log_buf:
3484 /* if we didn't copy map pointers into bpf_prog_info, release
3485 * them now. Otherwise free_bpf_prog_info() will release them.
3486 */
3489 err_unlock:
3492 err_free_env:
3495 }
3499 {
3516 /* grab the mutex to protect few globals used by verifier */
3523 GFP_KERNEL);
3536 skip_full_check:
3542 err_free_env:
3545 }