filter.rst 61 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653
  1. .. SPDX-License-Identifier: GPL-2.0
  2. .. _networking-filter:
  3. =======================================================
  4. Linux Socket Filtering aka Berkeley Packet Filter (BPF)
  5. =======================================================
  6. Introduction
  7. ------------
  8. Linux Socket Filtering (LSF) is derived from the Berkeley Packet Filter.
  9. Though there are some distinct differences between the BSD and Linux
  10. Kernel filtering, but when we speak of BPF or LSF in Linux context, we
  11. mean the very same mechanism of filtering in the Linux kernel.
  12. BPF allows a user-space program to attach a filter onto any socket and
  13. allow or disallow certain types of data to come through the socket. LSF
  14. follows exactly the same filter code structure as BSD's BPF, so referring
  15. to the BSD bpf.4 manpage is very helpful in creating filters.
  16. On Linux, BPF is much simpler than on BSD. One does not have to worry
  17. about devices or anything like that. You simply create your filter code,
  18. send it to the kernel via the SO_ATTACH_FILTER option and if your filter
  19. code passes the kernel check on it, you then immediately begin filtering
  20. data on that socket.
  21. You can also detach filters from your socket via the SO_DETACH_FILTER
  22. option. This will probably not be used much since when you close a socket
  23. that has a filter on it the filter is automagically removed. The other
  24. less common case may be adding a different filter on the same socket where
  25. you had another filter that is still running: the kernel takes care of
  26. removing the old one and placing your new one in its place, assuming your
  27. filter has passed the checks, otherwise if it fails the old filter will
  28. remain on that socket.
  29. SO_LOCK_FILTER option allows to lock the filter attached to a socket. Once
  30. set, a filter cannot be removed or changed. This allows one process to
  31. setup a socket, attach a filter, lock it then drop privileges and be
  32. assured that the filter will be kept until the socket is closed.
  33. The biggest user of this construct might be libpcap. Issuing a high-level
  34. filter command like `tcpdump -i em1 port 22` passes through the libpcap
  35. internal compiler that generates a structure that can eventually be loaded
  36. via SO_ATTACH_FILTER to the kernel. `tcpdump -i em1 port 22 -ddd`
  37. displays what is being placed into this structure.
  38. Although we were only speaking about sockets here, BPF in Linux is used
  39. in many more places. There's xt_bpf for netfilter, cls_bpf in the kernel
  40. qdisc layer, SECCOMP-BPF (SECure COMPuting [1]_), and lots of other places
  41. such as team driver, PTP code, etc where BPF is being used.
  42. .. [1] Documentation/userspace-api/seccomp_filter.rst
  43. Original BPF paper:
  44. Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
  45. architecture for user-level packet capture. In Proceedings of the
  46. USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
  47. Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
  48. CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf]
  49. Structure
  50. ---------
  51. User space applications include <linux/filter.h> which contains the
  52. following relevant structures::
  53. struct sock_filter { /* Filter block */
  54. __u16 code; /* Actual filter code */
  55. __u8 jt; /* Jump true */
  56. __u8 jf; /* Jump false */
  57. __u32 k; /* Generic multiuse field */
  58. };
  59. Such a structure is assembled as an array of 4-tuples, that contains
  60. a code, jt, jf and k value. jt and jf are jump offsets and k a generic
  61. value to be used for a provided code::
  62. struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
  63. unsigned short len; /* Number of filter blocks */
  64. struct sock_filter __user *filter;
  65. };
  66. For socket filtering, a pointer to this structure (as shown in
  67. follow-up example) is being passed to the kernel through setsockopt(2).
  68. Example
  69. -------
  70. ::
  71. #include <sys/socket.h>
  72. #include <sys/types.h>
  73. #include <arpa/inet.h>
  74. #include <linux/if_ether.h>
  75. /* ... */
  76. /* From the example above: tcpdump -i em1 port 22 -dd */
  77. struct sock_filter code[] = {
  78. { 0x28, 0, 0, 0x0000000c },
  79. { 0x15, 0, 8, 0x000086dd },
  80. { 0x30, 0, 0, 0x00000014 },
  81. { 0x15, 2, 0, 0x00000084 },
  82. { 0x15, 1, 0, 0x00000006 },
  83. { 0x15, 0, 17, 0x00000011 },
  84. { 0x28, 0, 0, 0x00000036 },
  85. { 0x15, 14, 0, 0x00000016 },
  86. { 0x28, 0, 0, 0x00000038 },
  87. { 0x15, 12, 13, 0x00000016 },
  88. { 0x15, 0, 12, 0x00000800 },
  89. { 0x30, 0, 0, 0x00000017 },
  90. { 0x15, 2, 0, 0x00000084 },
  91. { 0x15, 1, 0, 0x00000006 },
  92. { 0x15, 0, 8, 0x00000011 },
  93. { 0x28, 0, 0, 0x00000014 },
  94. { 0x45, 6, 0, 0x00001fff },
  95. { 0xb1, 0, 0, 0x0000000e },
  96. { 0x48, 0, 0, 0x0000000e },
  97. { 0x15, 2, 0, 0x00000016 },
  98. { 0x48, 0, 0, 0x00000010 },
  99. { 0x15, 0, 1, 0x00000016 },
  100. { 0x06, 0, 0, 0x0000ffff },
  101. { 0x06, 0, 0, 0x00000000 },
  102. };
  103. struct sock_fprog bpf = {
  104. .len = ARRAY_SIZE(code),
  105. .filter = code,
  106. };
  107. sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
  108. if (sock < 0)
  109. /* ... bail out ... */
  110. ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
  111. if (ret < 0)
  112. /* ... bail out ... */
  113. /* ... */
  114. close(sock);
  115. The above example code attaches a socket filter for a PF_PACKET socket
  116. in order to let all IPv4/IPv6 packets with port 22 pass. The rest will
  117. be dropped for this socket.
  118. The setsockopt(2) call to SO_DETACH_FILTER doesn't need any arguments
  119. and SO_LOCK_FILTER for preventing the filter to be detached, takes an
  120. integer value with 0 or 1.
  121. Note that socket filters are not restricted to PF_PACKET sockets only,
  122. but can also be used on other socket families.
  123. Summary of system calls:
  124. * setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &val, sizeof(val));
  125. * setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &val, sizeof(val));
  126. * setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER, &val, sizeof(val));
  127. Normally, most use cases for socket filtering on packet sockets will be
  128. covered by libpcap in high-level syntax, so as an application developer
  129. you should stick to that. libpcap wraps its own layer around all that.
  130. Unless i) using/linking to libpcap is not an option, ii) the required BPF
  131. filters use Linux extensions that are not supported by libpcap's compiler,
  132. iii) a filter might be more complex and not cleanly implementable with
  133. libpcap's compiler, or iv) particular filter codes should be optimized
  134. differently than libpcap's internal compiler does; then in such cases
  135. writing such a filter "by hand" can be of an alternative. For example,
  136. xt_bpf and cls_bpf users might have requirements that could result in
  137. more complex filter code, or one that cannot be expressed with libpcap
  138. (e.g. different return codes for various code paths). Moreover, BPF JIT
  139. implementors may wish to manually write test cases and thus need low-level
  140. access to BPF code as well.
  141. BPF engine and instruction set
  142. ------------------------------
  143. Under tools/bpf/ there's a small helper tool called bpf_asm which can
  144. be used to write low-level filters for example scenarios mentioned in the
  145. previous section. Asm-like syntax mentioned here has been implemented in
  146. bpf_asm and will be used for further explanations (instead of dealing with
  147. less readable opcodes directly, principles are the same). The syntax is
  148. closely modelled after Steven McCanne's and Van Jacobson's BPF paper.
  149. The BPF architecture consists of the following basic elements:
  150. ======= ====================================================
  151. Element Description
  152. ======= ====================================================
  153. A 32 bit wide accumulator
  154. X 32 bit wide X register
  155. M[] 16 x 32 bit wide misc registers aka "scratch memory
  156. store", addressable from 0 to 15
  157. ======= ====================================================
  158. A program, that is translated by bpf_asm into "opcodes" is an array that
  159. consists of the following elements (as already mentioned)::
  160. op:16, jt:8, jf:8, k:32
  161. The element op is a 16 bit wide opcode that has a particular instruction
  162. encoded. jt and jf are two 8 bit wide jump targets, one for condition
  163. "jump if true", the other one "jump if false". Eventually, element k
  164. contains a miscellaneous argument that can be interpreted in different
  165. ways depending on the given instruction in op.
  166. The instruction set consists of load, store, branch, alu, miscellaneous
  167. and return instructions that are also represented in bpf_asm syntax. This
  168. table lists all bpf_asm instructions available resp. what their underlying
  169. opcodes as defined in linux/filter.h stand for:
  170. =========== =================== =====================
  171. Instruction Addressing mode Description
  172. =========== =================== =====================
  173. ld 1, 2, 3, 4, 12 Load word into A
  174. ldi 4 Load word into A
  175. ldh 1, 2 Load half-word into A
  176. ldb 1, 2 Load byte into A
  177. ldx 3, 4, 5, 12 Load word into X
  178. ldxi 4 Load word into X
  179. ldxb 5 Load byte into X
  180. st 3 Store A into M[]
  181. stx 3 Store X into M[]
  182. jmp 6 Jump to label
  183. ja 6 Jump to label
  184. jeq 7, 8, 9, 10 Jump on A == <x>
  185. jneq 9, 10 Jump on A != <x>
  186. jne 9, 10 Jump on A != <x>
  187. jlt 9, 10 Jump on A < <x>
  188. jle 9, 10 Jump on A <= <x>
  189. jgt 7, 8, 9, 10 Jump on A > <x>
  190. jge 7, 8, 9, 10 Jump on A >= <x>
  191. jset 7, 8, 9, 10 Jump on A & <x>
  192. add 0, 4 A + <x>
  193. sub 0, 4 A - <x>
  194. mul 0, 4 A * <x>
  195. div 0, 4 A / <x>
  196. mod 0, 4 A % <x>
  197. neg !A
  198. and 0, 4 A & <x>
  199. or 0, 4 A | <x>
  200. xor 0, 4 A ^ <x>
  201. lsh 0, 4 A << <x>
  202. rsh 0, 4 A >> <x>
  203. tax Copy A into X
  204. txa Copy X into A
  205. ret 4, 11 Return
  206. =========== =================== =====================
  207. The next table shows addressing formats from the 2nd column:
  208. =============== =================== ===============================================
  209. Addressing mode Syntax Description
  210. =============== =================== ===============================================
  211. 0 x/%x Register X
  212. 1 [k] BHW at byte offset k in the packet
  213. 2 [x + k] BHW at the offset X + k in the packet
  214. 3 M[k] Word at offset k in M[]
  215. 4 #k Literal value stored in k
  216. 5 4*([k]&0xf) Lower nibble * 4 at byte offset k in the packet
  217. 6 L Jump label L
  218. 7 #k,Lt,Lf Jump to Lt if true, otherwise jump to Lf
  219. 8 x/%x,Lt,Lf Jump to Lt if true, otherwise jump to Lf
  220. 9 #k,Lt Jump to Lt if predicate is true
  221. 10 x/%x,Lt Jump to Lt if predicate is true
  222. 11 a/%a Accumulator A
  223. 12 extension BPF extension
  224. =============== =================== ===============================================
  225. The Linux kernel also has a couple of BPF extensions that are used along
  226. with the class of load instructions by "overloading" the k argument with
  227. a negative offset + a particular extension offset. The result of such BPF
  228. extensions are loaded into A.
  229. Possible BPF extensions are shown in the following table:
  230. =================================== =================================================
  231. Extension Description
  232. =================================== =================================================
  233. len skb->len
  234. proto skb->protocol
  235. type skb->pkt_type
  236. poff Payload start offset
  237. ifidx skb->dev->ifindex
  238. nla Netlink attribute of type X with offset A
  239. nlan Nested Netlink attribute of type X with offset A
  240. mark skb->mark
  241. queue skb->queue_mapping
  242. hatype skb->dev->type
  243. rxhash skb->hash
  244. cpu raw_smp_processor_id()
  245. vlan_tci skb_vlan_tag_get(skb)
  246. vlan_avail skb_vlan_tag_present(skb)
  247. vlan_tpid skb->vlan_proto
  248. rand prandom_u32()
  249. =================================== =================================================
  250. These extensions can also be prefixed with '#'.
  251. Examples for low-level BPF:
  252. **ARP packets**::
  253. ldh [12]
  254. jne #0x806, drop
  255. ret #-1
  256. drop: ret #0
  257. **IPv4 TCP packets**::
  258. ldh [12]
  259. jne #0x800, drop
  260. ldb [23]
  261. jneq #6, drop
  262. ret #-1
  263. drop: ret #0
  264. **(Accelerated) VLAN w/ id 10**::
  265. ld vlan_tci
  266. jneq #10, drop
  267. ret #-1
  268. drop: ret #0
  269. **icmp random packet sampling, 1 in 4**:
  270. ldh [12]
  271. jne #0x800, drop
  272. ldb [23]
  273. jneq #1, drop
  274. # get a random uint32 number
  275. ld rand
  276. mod #4
  277. jneq #1, drop
  278. ret #-1
  279. drop: ret #0
  280. **SECCOMP filter example**::
  281. ld [4] /* offsetof(struct seccomp_data, arch) */
  282. jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */
  283. ld [0] /* offsetof(struct seccomp_data, nr) */
  284. jeq #15, good /* __NR_rt_sigreturn */
  285. jeq #231, good /* __NR_exit_group */
  286. jeq #60, good /* __NR_exit */
  287. jeq #0, good /* __NR_read */
  288. jeq #1, good /* __NR_write */
  289. jeq #5, good /* __NR_fstat */
  290. jeq #9, good /* __NR_mmap */
  291. jeq #14, good /* __NR_rt_sigprocmask */
  292. jeq #13, good /* __NR_rt_sigaction */
  293. jeq #35, good /* __NR_nanosleep */
  294. bad: ret #0 /* SECCOMP_RET_KILL_THREAD */
  295. good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */
  296. The above example code can be placed into a file (here called "foo"), and
  297. then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
  298. and cls_bpf understands and can directly be loaded with. Example with above
  299. ARP code::
  300. $ ./bpf_asm foo
  301. 4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
  302. In copy and paste C-like output::
  303. $ ./bpf_asm -c foo
  304. { 0x28, 0, 0, 0x0000000c },
  305. { 0x15, 0, 1, 0x00000806 },
  306. { 0x06, 0, 0, 0xffffffff },
  307. { 0x06, 0, 0, 0000000000 },
  308. In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
  309. filters that might not be obvious at first, it's good to test filters before
  310. attaching to a live system. For that purpose, there's a small tool called
  311. bpf_dbg under tools/bpf/ in the kernel source directory. This debugger allows
  312. for testing BPF filters against given pcap files, single stepping through the
  313. BPF code on the pcap's packets and to do BPF machine register dumps.
  314. Starting bpf_dbg is trivial and just requires issuing::
  315. # ./bpf_dbg
  316. In case input and output do not equal stdin/stdout, bpf_dbg takes an
  317. alternative stdin source as a first argument, and an alternative stdout
  318. sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
  319. Other than that, a particular libreadline configuration can be set via
  320. file "~/.bpf_dbg_init" and the command history is stored in the file
  321. "~/.bpf_dbg_history".
  322. Interaction in bpf_dbg happens through a shell that also has auto-completion
  323. support (follow-up example commands starting with '>' denote bpf_dbg shell).
  324. The usual workflow would be to ...
  325. * load bpf 6,40 0 0 12,21 0 3 2048,48 0 0 23,21 0 1 1,6 0 0 65535,6 0 0 0
  326. Loads a BPF filter from standard output of bpf_asm, or transformed via
  327. e.g. ``tcpdump -iem1 -ddd port 22 | tr '\n' ','``. Note that for JIT
  328. debugging (next section), this command creates a temporary socket and
  329. loads the BPF code into the kernel. Thus, this will also be useful for
  330. JIT developers.
  331. * load pcap foo.pcap
  332. Loads standard tcpdump pcap file.
  333. * run [<n>]
  334. bpf passes:1 fails:9
  335. Runs through all packets from a pcap to account how many passes and fails
  336. the filter will generate. A limit of packets to traverse can be given.
  337. * disassemble::
  338. l0: ldh [12]
  339. l1: jeq #0x800, l2, l5
  340. l2: ldb [23]
  341. l3: jeq #0x1, l4, l5
  342. l4: ret #0xffff
  343. l5: ret #0
  344. Prints out BPF code disassembly.
  345. * dump::
  346. /* { op, jt, jf, k }, */
  347. { 0x28, 0, 0, 0x0000000c },
  348. { 0x15, 0, 3, 0x00000800 },
  349. { 0x30, 0, 0, 0x00000017 },
  350. { 0x15, 0, 1, 0x00000001 },
  351. { 0x06, 0, 0, 0x0000ffff },
  352. { 0x06, 0, 0, 0000000000 },
  353. Prints out C-style BPF code dump.
  354. * breakpoint 0::
  355. breakpoint at: l0: ldh [12]
  356. * breakpoint 1::
  357. breakpoint at: l1: jeq #0x800, l2, l5
  358. ...
  359. Sets breakpoints at particular BPF instructions. Issuing a `run` command
  360. will walk through the pcap file continuing from the current packet and
  361. break when a breakpoint is being hit (another `run` will continue from
  362. the currently active breakpoint executing next instructions):
  363. * run::
  364. -- register dump --
  365. pc: [0] <-- program counter
  366. code: [40] jt[0] jf[0] k[12] <-- plain BPF code of current instruction
  367. curr: l0: ldh [12] <-- disassembly of current instruction
  368. A: [00000000][0] <-- content of A (hex, decimal)
  369. X: [00000000][0] <-- content of X (hex, decimal)
  370. M[0,15]: [00000000][0] <-- folded content of M (hex, decimal)
  371. -- packet dump -- <-- Current packet from pcap (hex)
  372. len: 42
  373. 0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
  374. 16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
  375. 32: 00 00 00 00 00 00 0a 3b 01 01
  376. (breakpoint)
  377. >
  378. * breakpoint::
  379. breakpoints: 0 1
  380. Prints currently set breakpoints.
  381. * step [-<n>, +<n>]
  382. Performs single stepping through the BPF program from the current pc
  383. offset. Thus, on each step invocation, above register dump is issued.
  384. This can go forwards and backwards in time, a plain `step` will break
  385. on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
  386. * select <n>
  387. Selects a given packet from the pcap file to continue from. Thus, on
  388. the next `run` or `step`, the BPF program is being evaluated against
  389. the user pre-selected packet. Numbering starts just as in Wireshark
  390. with index 1.
  391. * quit
  392. Exits bpf_dbg.
  393. JIT compiler
  394. ------------
  395. The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC,
  396. PowerPC, ARM, ARM64, MIPS, RISC-V and s390 and can be enabled through
  397. CONFIG_BPF_JIT. The JIT compiler is transparently invoked for each
  398. attached filter from user space or for internal kernel users if it has
  399. been previously enabled by root::
  400. echo 1 > /proc/sys/net/core/bpf_jit_enable
  401. For JIT developers, doing audits etc, each compile run can output the generated
  402. opcode image into the kernel log via::
  403. echo 2 > /proc/sys/net/core/bpf_jit_enable
  404. Example output from dmesg::
  405. [ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
  406. [ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
  407. [ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
  408. [ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
  409. [ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
  410. [ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
  411. When CONFIG_BPF_JIT_ALWAYS_ON is enabled, bpf_jit_enable is permanently set to 1 and
  412. setting any other value than that will return in failure. This is even the case for
  413. setting bpf_jit_enable to 2, since dumping the final JIT image into the kernel log
  414. is discouraged and introspection through bpftool (under tools/bpf/bpftool/) is the
  415. generally recommended approach instead.
  416. In the kernel source tree under tools/bpf/, there's bpf_jit_disasm for
  417. generating disassembly out of the kernel log's hexdump::
  418. # ./bpf_jit_disasm
  419. 70 bytes emitted from JIT compiler (pass:3, flen:6)
  420. ffffffffa0069c8f + <x>:
  421. 0: push %rbp
  422. 1: mov %rsp,%rbp
  423. 4: sub $0x60,%rsp
  424. 8: mov %rbx,-0x8(%rbp)
  425. c: mov 0x68(%rdi),%r9d
  426. 10: sub 0x6c(%rdi),%r9d
  427. 14: mov 0xd8(%rdi),%r8
  428. 1b: mov $0xc,%esi
  429. 20: callq 0xffffffffe0ff9442
  430. 25: cmp $0x800,%eax
  431. 2a: jne 0x0000000000000042
  432. 2c: mov $0x17,%esi
  433. 31: callq 0xffffffffe0ff945e
  434. 36: cmp $0x1,%eax
  435. 39: jne 0x0000000000000042
  436. 3b: mov $0xffff,%eax
  437. 40: jmp 0x0000000000000044
  438. 42: xor %eax,%eax
  439. 44: leaveq
  440. 45: retq
  441. Issuing option `-o` will "annotate" opcodes to resulting assembler
  442. instructions, which can be very useful for JIT developers:
  443. # ./bpf_jit_disasm -o
  444. 70 bytes emitted from JIT compiler (pass:3, flen:6)
  445. ffffffffa0069c8f + <x>:
  446. 0: push %rbp
  447. 55
  448. 1: mov %rsp,%rbp
  449. 48 89 e5
  450. 4: sub $0x60,%rsp
  451. 48 83 ec 60
  452. 8: mov %rbx,-0x8(%rbp)
  453. 48 89 5d f8
  454. c: mov 0x68(%rdi),%r9d
  455. 44 8b 4f 68
  456. 10: sub 0x6c(%rdi),%r9d
  457. 44 2b 4f 6c
  458. 14: mov 0xd8(%rdi),%r8
  459. 4c 8b 87 d8 00 00 00
  460. 1b: mov $0xc,%esi
  461. be 0c 00 00 00
  462. 20: callq 0xffffffffe0ff9442
  463. e8 1d 94 ff e0
  464. 25: cmp $0x800,%eax
  465. 3d 00 08 00 00
  466. 2a: jne 0x0000000000000042
  467. 75 16
  468. 2c: mov $0x17,%esi
  469. be 17 00 00 00
  470. 31: callq 0xffffffffe0ff945e
  471. e8 28 94 ff e0
  472. 36: cmp $0x1,%eax
  473. 83 f8 01
  474. 39: jne 0x0000000000000042
  475. 75 07
  476. 3b: mov $0xffff,%eax
  477. b8 ff ff 00 00
  478. 40: jmp 0x0000000000000044
  479. eb 02
  480. 42: xor %eax,%eax
  481. 31 c0
  482. 44: leaveq
  483. c9
  484. 45: retq
  485. c3
  486. For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
  487. toolchain for developing and testing the kernel's JIT compiler.
  488. BPF kernel internals
  489. --------------------
  490. Internally, for the kernel interpreter, a different instruction set
  491. format with similar underlying principles from BPF described in previous
  492. paragraphs is being used. However, the instruction set format is modelled
  493. closer to the underlying architecture to mimic native instruction sets, so
  494. that a better performance can be achieved (more details later). This new
  495. ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which
  496. originates from [e]xtended BPF is not the same as BPF extensions! While
  497. eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading'
  498. of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.)
  499. It is designed to be JITed with one to one mapping, which can also open up
  500. the possibility for GCC/LLVM compilers to generate optimized eBPF code through
  501. an eBPF backend that performs almost as fast as natively compiled code.
  502. The new instruction set was originally designed with the possible goal in
  503. mind to write programs in "restricted C" and compile into eBPF with a optional
  504. GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with
  505. minimal performance overhead over two steps, that is, C -> eBPF -> native code.
  506. Currently, the new format is being used for running user BPF programs, which
  507. includes seccomp BPF, classic socket filters, cls_bpf traffic classifier,
  508. team driver's classifier for its load-balancing mode, netfilter's xt_bpf
  509. extension, PTP dissector/classifier, and much more. They are all internally
  510. converted by the kernel into the new instruction set representation and run
  511. in the eBPF interpreter. For in-kernel handlers, this all works transparently
  512. by using bpf_prog_create() for setting up the filter, resp.
  513. bpf_prog_destroy() for destroying it. The macro
  514. BPF_PROG_RUN(filter, ctx) transparently invokes eBPF interpreter or JITed
  515. code to run the filter. 'filter' is a pointer to struct bpf_prog that we
  516. got from bpf_prog_create(), and 'ctx' the given context (e.g.
  517. skb pointer). All constraints and restrictions from bpf_check_classic() apply
  518. before a conversion to the new layout is being done behind the scenes!
  519. Currently, the classic BPF format is being used for JITing on most
  520. 32-bit architectures, whereas x86-64, aarch64, s390x, powerpc64,
  521. sparc64, arm32, riscv64, riscv32 perform JIT compilation from eBPF
  522. instruction set.
  523. Some core changes of the new internal format:
  524. - Number of registers increase from 2 to 10:
  525. The old format had two registers A and X, and a hidden frame pointer. The
  526. new layout extends this to be 10 internal registers and a read-only frame
  527. pointer. Since 64-bit CPUs are passing arguments to functions via registers
  528. the number of args from eBPF program to in-kernel function is restricted
  529. to 5 and one register is used to accept return value from an in-kernel
  530. function. Natively, x86_64 passes first 6 arguments in registers, aarch64/
  531. sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved
  532. registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers.
  533. Therefore, eBPF calling convention is defined as:
  534. * R0 - return value from in-kernel function, and exit value for eBPF program
  535. * R1 - R5 - arguments from eBPF program to in-kernel function
  536. * R6 - R9 - callee saved registers that in-kernel function will preserve
  537. * R10 - read-only frame pointer to access stack
  538. Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64,
  539. etc, and eBPF calling convention maps directly to ABIs used by the kernel on
  540. 64-bit architectures.
  541. On 32-bit architectures JIT may map programs that use only 32-bit arithmetic
  542. and may let more complex programs to be interpreted.
  543. R0 - R5 are scratch registers and eBPF program needs spill/fill them if
  544. necessary across calls. Note that there is only one eBPF program (== one
  545. eBPF main routine) and it cannot call other eBPF functions, it can only
  546. call predefined in-kernel functions, though.
  547. - Register width increases from 32-bit to 64-bit:
  548. Still, the semantics of the original 32-bit ALU operations are preserved
  549. via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower
  550. subregisters that zero-extend into 64-bit if they are being written to.
  551. That behavior maps directly to x86_64 and arm64 subregister definition, but
  552. makes other JITs more difficult.
  553. 32-bit architectures run 64-bit internal BPF programs via interpreter.
  554. Their JITs may convert BPF programs that only use 32-bit subregisters into
  555. native instruction set and let the rest being interpreted.
  556. Operation is 64-bit, because on 64-bit architectures, pointers are also
  557. 64-bit wide, and we want to pass 64-bit values in/out of kernel functions,
  558. so 32-bit eBPF registers would otherwise require to define register-pair
  559. ABI, thus, there won't be able to use a direct eBPF register to HW register
  560. mapping and JIT would need to do combine/split/move operations for every
  561. register in and out of the function, which is complex, bug prone and slow.
  562. Another reason is the use of atomic 64-bit counters.
  563. - Conditional jt/jf targets replaced with jt/fall-through:
  564. While the original design has constructs such as ``if (cond) jump_true;
  565. else jump_false;``, they are being replaced into alternative constructs like
  566. ``if (cond) jump_true; /* else fall-through */``.
  567. - Introduces bpf_call insn and register passing convention for zero overhead
  568. calls from/to other kernel functions:
  569. Before an in-kernel function call, the internal BPF program needs to
  570. place function arguments into R1 to R5 registers to satisfy calling
  571. convention, then the interpreter will take them from registers and pass
  572. to in-kernel function. If R1 - R5 registers are mapped to CPU registers
  573. that are used for argument passing on given architecture, the JIT compiler
  574. doesn't need to emit extra moves. Function arguments will be in the correct
  575. registers and BPF_CALL instruction will be JITed as single 'call' HW
  576. instruction. This calling convention was picked to cover common call
  577. situations without performance penalty.
  578. After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has
  579. a return value of the function. Since R6 - R9 are callee saved, their state
  580. is preserved across the call.
  581. For example, consider three C functions::
  582. u64 f1() { return (*_f2)(1); }
  583. u64 f2(u64 a) { return f3(a + 1, a); }
  584. u64 f3(u64 a, u64 b) { return a - b; }
  585. GCC can compile f1, f3 into x86_64::
  586. f1:
  587. movl $1, %edi
  588. movq _f2(%rip), %rax
  589. jmp *%rax
  590. f3:
  591. movq %rdi, %rax
  592. subq %rsi, %rax
  593. ret
  594. Function f2 in eBPF may look like::
  595. f2:
  596. bpf_mov R2, R1
  597. bpf_add R1, 1
  598. bpf_call f3
  599. bpf_exit
  600. If f2 is JITed and the pointer stored to ``_f2``. The calls f1 -> f2 -> f3 and
  601. returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to
  602. be used to call into f2.
  603. For practical reasons all eBPF programs have only one argument 'ctx' which is
  604. already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs
  605. can call kernel functions with up to 5 arguments. Calls with 6 or more arguments
  606. are currently not supported, but these restrictions can be lifted if necessary
  607. in the future.
  608. On 64-bit architectures all register map to HW registers one to one. For
  609. example, x86_64 JIT compiler can map them as ...
  610. ::
  611. R0 - rax
  612. R1 - rdi
  613. R2 - rsi
  614. R3 - rdx
  615. R4 - rcx
  616. R5 - r8
  617. R6 - rbx
  618. R7 - r13
  619. R8 - r14
  620. R9 - r15
  621. R10 - rbp
  622. ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
  623. and rbx, r12 - r15 are callee saved.
  624. Then the following internal BPF pseudo-program::
  625. bpf_mov R6, R1 /* save ctx */
  626. bpf_mov R2, 2
  627. bpf_mov R3, 3
  628. bpf_mov R4, 4
  629. bpf_mov R5, 5
  630. bpf_call foo
  631. bpf_mov R7, R0 /* save foo() return value */
  632. bpf_mov R1, R6 /* restore ctx for next call */
  633. bpf_mov R2, 6
  634. bpf_mov R3, 7
  635. bpf_mov R4, 8
  636. bpf_mov R5, 9
  637. bpf_call bar
  638. bpf_add R0, R7
  639. bpf_exit
  640. After JIT to x86_64 may look like::
  641. push %rbp
  642. mov %rsp,%rbp
  643. sub $0x228,%rsp
  644. mov %rbx,-0x228(%rbp)
  645. mov %r13,-0x220(%rbp)
  646. mov %rdi,%rbx
  647. mov $0x2,%esi
  648. mov $0x3,%edx
  649. mov $0x4,%ecx
  650. mov $0x5,%r8d
  651. callq foo
  652. mov %rax,%r13
  653. mov %rbx,%rdi
  654. mov $0x6,%esi
  655. mov $0x7,%edx
  656. mov $0x8,%ecx
  657. mov $0x9,%r8d
  658. callq bar
  659. add %r13,%rax
  660. mov -0x228(%rbp),%rbx
  661. mov -0x220(%rbp),%r13
  662. leaveq
  663. retq
  664. Which is in this example equivalent in C to::
  665. u64 bpf_filter(u64 ctx)
  666. {
  667. return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
  668. }
  669. In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64
  670. arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper
  671. registers and place their return value into ``%rax`` which is R0 in eBPF.
  672. Prologue and epilogue are emitted by JIT and are implicit in the
  673. interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve
  674. them across the calls as defined by calling convention.
  675. For example the following program is invalid::
  676. bpf_mov R1, 1
  677. bpf_call foo
  678. bpf_mov R0, R1
  679. bpf_exit
  680. After the call the registers R1-R5 contain junk values and cannot be read.
  681. An in-kernel eBPF verifier is used to validate internal BPF programs.
  682. Also in the new design, eBPF is limited to 4096 insns, which means that any
  683. program will terminate quickly and will only call a fixed number of kernel
  684. functions. Original BPF and the new format are two operand instructions,
  685. which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT.
  686. The input context pointer for invoking the interpreter function is generic,
  687. its content is defined by a specific use case. For seccomp register R1 points
  688. to seccomp_data, for converted BPF filters R1 points to a skb.
  689. A program, that is translated internally consists of the following elements::
  690. op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32
  691. So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field
  692. has room for new instructions. Some of them may use 16/24/32 byte encoding. New
  693. instructions must be multiple of 8 bytes to preserve backward compatibility.
  694. Internal BPF is a general purpose RISC instruction set. Not every register and
  695. every instruction are used during translation from original BPF to new format.
  696. For example, socket filters are not using ``exclusive add`` instruction, but
  697. tracing filters may do to maintain counters of events, for example. Register R9
  698. is not used by socket filters either, but more complex filters may be running
  699. out of registers and would have to resort to spill/fill to stack.
  700. Internal BPF can be used as a generic assembler for last step performance
  701. optimizations, socket filters and seccomp are using it as assembler. Tracing
  702. filters may use it as assembler to generate code from kernel. In kernel usage
  703. may not be bounded by security considerations, since generated internal BPF code
  704. may be optimizing internal code path and not being exposed to the user space.
  705. Safety of internal BPF can come from a verifier (TBD). In such use cases as
  706. described, it may be used as safe instruction set.
  707. Just like the original BPF, the new format runs within a controlled environment,
  708. is deterministic and the kernel can easily prove that. The safety of the program
  709. can be determined in two steps: first step does depth-first-search to disallow
  710. loops and other CFG validation; second step starts from the first insn and
  711. descends all possible paths. It simulates execution of every insn and observes
  712. the state change of registers and stack.
  713. eBPF opcode encoding
  714. --------------------
  715. eBPF is reusing most of the opcode encoding from classic to simplify conversion
  716. of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
  717. field is divided into three parts::
  718. +----------------+--------+--------------------+
  719. | 4 bits | 1 bit | 3 bits |
  720. | operation code | source | instruction class |
  721. +----------------+--------+--------------------+
  722. (MSB) (LSB)
  723. Three LSB bits store instruction class which is one of:
  724. =================== ===============
  725. Classic BPF classes eBPF classes
  726. =================== ===============
  727. BPF_LD 0x00 BPF_LD 0x00
  728. BPF_LDX 0x01 BPF_LDX 0x01
  729. BPF_ST 0x02 BPF_ST 0x02
  730. BPF_STX 0x03 BPF_STX 0x03
  731. BPF_ALU 0x04 BPF_ALU 0x04
  732. BPF_JMP 0x05 BPF_JMP 0x05
  733. BPF_RET 0x06 BPF_JMP32 0x06
  734. BPF_MISC 0x07 BPF_ALU64 0x07
  735. =================== ===============
  736. When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ...
  737. ::
  738. BPF_K 0x00
  739. BPF_X 0x08
  740. * in classic BPF, this means::
  741. BPF_SRC(code) == BPF_X - use register X as source operand
  742. BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
  743. * in eBPF, this means::
  744. BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
  745. BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
  746. ... and four MSB bits store operation code.
  747. If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of::
  748. BPF_ADD 0x00
  749. BPF_SUB 0x10
  750. BPF_MUL 0x20
  751. BPF_DIV 0x30
  752. BPF_OR 0x40
  753. BPF_AND 0x50
  754. BPF_LSH 0x60
  755. BPF_RSH 0x70
  756. BPF_NEG 0x80
  757. BPF_MOD 0x90
  758. BPF_XOR 0xa0
  759. BPF_MOV 0xb0 /* eBPF only: mov reg to reg */
  760. BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */
  761. BPF_END 0xd0 /* eBPF only: endianness conversion */
  762. If BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ], BPF_OP(code) is one of::
  763. BPF_JA 0x00 /* BPF_JMP only */
  764. BPF_JEQ 0x10
  765. BPF_JGT 0x20
  766. BPF_JGE 0x30
  767. BPF_JSET 0x40
  768. BPF_JNE 0x50 /* eBPF only: jump != */
  769. BPF_JSGT 0x60 /* eBPF only: signed '>' */
  770. BPF_JSGE 0x70 /* eBPF only: signed '>=' */
  771. BPF_CALL 0x80 /* eBPF BPF_JMP only: function call */
  772. BPF_EXIT 0x90 /* eBPF BPF_JMP only: function return */
  773. BPF_JLT 0xa0 /* eBPF only: unsigned '<' */
  774. BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */
  775. BPF_JSLT 0xc0 /* eBPF only: signed '<' */
  776. BPF_JSLE 0xd0 /* eBPF only: signed '<=' */
  777. So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF
  778. and eBPF. There are only two registers in classic BPF, so it means A += X.
  779. In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly,
  780. BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous
  781. src_reg = (u32) src_reg ^ (u32) imm32 in eBPF.
  782. Classic BPF is using BPF_MISC class to represent A = X and X = A moves.
  783. eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no
  784. BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean
  785. exactly the same operations as BPF_ALU, but with 64-bit wide operands
  786. instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.:
  787. dst_reg = dst_reg + src_reg
  788. Classic BPF wastes the whole BPF_RET class to represent a single ``ret``
  789. operation. Classic BPF_RET | BPF_K means copy imm32 into return register
  790. and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT
  791. in eBPF means function exit only. The eBPF program needs to store return
  792. value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is used as
  793. BPF_JMP32 to mean exactly the same operations as BPF_JMP, but with 32-bit wide
  794. operands for the comparisons instead.
  795. For load and store instructions the 8-bit 'code' field is divided as::
  796. +--------+--------+-------------------+
  797. | 3 bits | 2 bits | 3 bits |
  798. | mode | size | instruction class |
  799. +--------+--------+-------------------+
  800. (MSB) (LSB)
  801. Size modifier is one of ...
  802. ::
  803. BPF_W 0x00 /* word */
  804. BPF_H 0x08 /* half word */
  805. BPF_B 0x10 /* byte */
  806. BPF_DW 0x18 /* eBPF only, double word */
  807. ... which encodes size of load/store operation::
  808. B - 1 byte
  809. H - 2 byte
  810. W - 4 byte
  811. DW - 8 byte (eBPF only)
  812. Mode modifier is one of::
  813. BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
  814. BPF_ABS 0x20
  815. BPF_IND 0x40
  816. BPF_MEM 0x60
  817. BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */
  818. BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */
  819. BPF_XADD 0xc0 /* eBPF only, exclusive add */
  820. eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and
  821. (BPF_IND | <size> | BPF_LD) which are used to access packet data.
  822. They had to be carried over from classic to have strong performance of
  823. socket filters running in eBPF interpreter. These instructions can only
  824. be used when interpreter context is a pointer to ``struct sk_buff`` and
  825. have seven implicit operands. Register R6 is an implicit input that must
  826. contain pointer to sk_buff. Register R0 is an implicit output which contains
  827. the data fetched from the packet. Registers R1-R5 are scratch registers
  828. and must not be used to store the data across BPF_ABS | BPF_LD or
  829. BPF_IND | BPF_LD instructions.
  830. These instructions have implicit program exit condition as well. When
  831. eBPF program is trying to access the data beyond the packet boundary,
  832. the interpreter will abort the execution of the program. JIT compilers
  833. therefore must preserve this property. src_reg and imm32 fields are
  834. explicit inputs to these instructions.
  835. For example::
  836. BPF_IND | BPF_W | BPF_LD means:
  837. R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))
  838. and R1 - R5 were scratched.
  839. Unlike classic BPF instruction set, eBPF has generic load/store operations::
  840. BPF_MEM | <size> | BPF_STX: *(size *) (dst_reg + off) = src_reg
  841. BPF_MEM | <size> | BPF_ST: *(size *) (dst_reg + off) = imm32
  842. BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *) (src_reg + off)
  843. BPF_XADD | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg
  844. BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
  845. Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and
  846. 2 byte atomic increments are not supported.
  847. eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists
  848. of two consecutive ``struct bpf_insn`` 8-byte blocks and interpreted as single
  849. instruction that loads 64-bit immediate value into a dst_reg.
  850. Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
  851. 32-bit immediate value into a register.
  852. eBPF verifier
  853. -------------
  854. The safety of the eBPF program is determined in two steps.
  855. First step does DAG check to disallow loops and other CFG validation.
  856. In particular it will detect programs that have unreachable instructions.
  857. (though classic BPF checker allows them)
  858. Second step starts from the first insn and descends all possible paths.
  859. It simulates execution of every insn and observes the state change of
  860. registers and stack.
  861. At the start of the program the register R1 contains a pointer to context
  862. and has type PTR_TO_CTX.
  863. If verifier sees an insn that does R2=R1, then R2 has now type
  864. PTR_TO_CTX as well and can be used on the right hand side of expression.
  865. If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
  866. since addition of two valid pointers makes invalid pointer.
  867. (In 'secure' mode verifier will reject any type of pointer arithmetic to make
  868. sure that kernel addresses don't leak to unprivileged users)
  869. If register was never written to, it's not readable::
  870. bpf_mov R0 = R2
  871. bpf_exit
  872. will be rejected, since R2 is unreadable at the start of the program.
  873. After kernel function call, R1-R5 are reset to unreadable and
  874. R0 has a return type of the function.
  875. Since R6-R9 are callee saved, their state is preserved across the call.
  876. ::
  877. bpf_mov R6 = 1
  878. bpf_call foo
  879. bpf_mov R0 = R6
  880. bpf_exit
  881. is a correct program. If there was R1 instead of R6, it would have
  882. been rejected.
  883. load/store instructions are allowed only with registers of valid types, which
  884. are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
  885. For example::
  886. bpf_mov R1 = 1
  887. bpf_mov R2 = 2
  888. bpf_xadd *(u32 *)(R1 + 3) += R2
  889. bpf_exit
  890. will be rejected, since R1 doesn't have a valid pointer type at the time of
  891. execution of instruction bpf_xadd.
  892. At the start R1 type is PTR_TO_CTX (a pointer to generic ``struct bpf_context``)
  893. A callback is used to customize verifier to restrict eBPF program access to only
  894. certain fields within ctx structure with specified size and alignment.
  895. For example, the following insn::
  896. bpf_ld R0 = *(u32 *)(R6 + 8)
  897. intends to load a word from address R6 + 8 and store it into R0
  898. If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
  899. that offset 8 of size 4 bytes can be accessed for reading, otherwise
  900. the verifier will reject the program.
  901. If R6=PTR_TO_STACK, then access should be aligned and be within
  902. stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
  903. so it will fail verification, since it's out of bounds.
  904. The verifier will allow eBPF program to read data from stack only after
  905. it wrote into it.
  906. Classic BPF verifier does similar check with M[0-15] memory slots.
  907. For example::
  908. bpf_ld R0 = *(u32 *)(R10 - 4)
  909. bpf_exit
  910. is invalid program.
  911. Though R10 is correct read-only register and has type PTR_TO_STACK
  912. and R10 - 4 is within stack bounds, there were no stores into that location.
  913. Pointer register spill/fill is tracked as well, since four (R6-R9)
  914. callee saved registers may not be enough for some programs.
  915. Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
  916. The eBPF verifier will check that registers match argument constraints.
  917. After the call register R0 will be set to return type of the function.
  918. Function calls is a main mechanism to extend functionality of eBPF programs.
  919. Socket filters may let programs to call one set of functions, whereas tracing
  920. filters may allow completely different set.
  921. If a function made accessible to eBPF program, it needs to be thought through
  922. from safety point of view. The verifier will guarantee that the function is
  923. called with valid arguments.
  924. seccomp vs socket filters have different security restrictions for classic BPF.
  925. Seccomp solves this by two stage verifier: classic BPF verifier is followed
  926. by seccomp verifier. In case of eBPF one configurable verifier is shared for
  927. all use cases.
  928. See details of eBPF verifier in kernel/bpf/verifier.c
  929. Register value tracking
  930. -----------------------
  931. In order to determine the safety of an eBPF program, the verifier must track
  932. the range of possible values in each register and also in each stack slot.
  933. This is done with ``struct bpf_reg_state``, defined in include/linux/
  934. bpf_verifier.h, which unifies tracking of scalar and pointer values. Each
  935. register state has a type, which is either NOT_INIT (the register has not been
  936. written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
  937. pointer type. The types of pointers describe their base, as follows:
  938. PTR_TO_CTX
  939. Pointer to bpf_context.
  940. CONST_PTR_TO_MAP
  941. Pointer to struct bpf_map. "Const" because arithmetic
  942. on these pointers is forbidden.
  943. PTR_TO_MAP_VALUE
  944. Pointer to the value stored in a map element.
  945. PTR_TO_MAP_VALUE_OR_NULL
  946. Either a pointer to a map value, or NULL; map accesses
  947. (see section 'eBPF maps', below) return this type,
  948. which becomes a PTR_TO_MAP_VALUE when checked != NULL.
  949. Arithmetic on these pointers is forbidden.
  950. PTR_TO_STACK
  951. Frame pointer.
  952. PTR_TO_PACKET
  953. skb->data.
  954. PTR_TO_PACKET_END
  955. skb->data + headlen; arithmetic forbidden.
  956. PTR_TO_SOCKET
  957. Pointer to struct bpf_sock_ops, implicitly refcounted.
  958. PTR_TO_SOCKET_OR_NULL
  959. Either a pointer to a socket, or NULL; socket lookup
  960. returns this type, which becomes a PTR_TO_SOCKET when
  961. checked != NULL. PTR_TO_SOCKET is reference-counted,
  962. so programs must release the reference through the
  963. socket release function before the end of the program.
  964. Arithmetic on these pointers is forbidden.
  965. However, a pointer may be offset from this base (as a result of pointer
  966. arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable
  967. offset'. The former is used when an exactly-known value (e.g. an immediate
  968. operand) is added to a pointer, while the latter is used for values which are
  969. not exactly known. The variable offset is also used in SCALAR_VALUEs, to track
  970. the range of possible values in the register.
  971. The verifier's knowledge about the variable offset consists of:
  972. * minimum and maximum values as unsigned
  973. * minimum and maximum values as signed
  974. * knowledge of the values of individual bits, in the form of a 'tnum': a u64
  975. 'mask' and a u64 'value'. 1s in the mask represent bits whose value is unknown;
  976. 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both
  977. mask and value; no bit should ever be 1 in both. For example, if a byte is read
  978. into a register from memory, the register's top 56 bits are known zero, while
  979. the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we
  980. then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;
  981. 0x1ff), because of potential carries.
  982. Besides arithmetic, the register state can also be updated by conditional
  983. branches. For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch
  984. it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'
  985. branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or
  986. BPF_JSGE) would instead update the signed minimum/maximum values. Information
  987. from the signed and unsigned bounds can be combined; for instance if a value is
  988. first tested < 8 and then tested s> 4, the verifier will conclude that the value
  989. is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.
  990. PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all
  991. pointers sharing that same variable offset. This is important for packet range
  992. checks: after adding a variable to a packet pointer register A, if you then copy
  993. it to another register B and then add a constant 4 to A, both registers will
  994. share the same 'id' but the A will have a fixed offset of +4. Then if A is
  995. bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
  996. now known to have a safe range of at least 4 bytes. See 'Direct packet access',
  997. below, for more on PTR_TO_PACKET ranges.
  998. The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of
  999. the pointer returned from a map lookup. This means that when one copy is
  1000. checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.
  1001. As well as range-checking, the tracked information is also used for enforcing
  1002. alignment of pointer accesses. For instance, on most systems the packet pointer
  1003. is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump
  1004. over the Ethernet header, then reads IHL and addes (IHL * 4), the resulting
  1005. pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
  1006. bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
  1007. that pointer are safe.
  1008. The 'id' field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common
  1009. to all copies of the pointer returned from a socket lookup. This has similar
  1010. behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but
  1011. it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly
  1012. represents a reference to the corresponding ``struct sock``. To ensure that the
  1013. reference is not leaked, it is imperative to NULL-check the reference and in
  1014. the non-NULL case, and pass the valid reference to the socket release function.
  1015. Direct packet access
  1016. --------------------
  1017. In cls_bpf and act_bpf programs the verifier allows direct access to the packet
  1018. data via skb->data and skb->data_end pointers.
  1019. Ex::
  1020. 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */
  1021. 2: r3 = *(u32 *)(r1 +76) /* load skb->data */
  1022. 3: r5 = r3
  1023. 4: r5 += 14
  1024. 5: if r5 > r4 goto pc+16
  1025. R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
  1026. 6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
  1027. this 2byte load from the packet is safe to do, since the program author
  1028. did check ``if (skb->data + 14 > skb->data_end) goto err`` at insn #5 which
  1029. means that in the fall-through case the register R3 (which points to skb->data)
  1030. has at least 14 directly accessible bytes. The verifier marks it
  1031. as R3=pkt(id=0,off=0,r=14).
  1032. id=0 means that no additional variables were added to the register.
  1033. off=0 means that no additional constants were added.
  1034. r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
  1035. Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
  1036. to the packet data, but constant 14 was added to the register, so
  1037. it now points to ``skb->data + 14`` and accessible range is [R5, R5 + 14 - 14)
  1038. which is zero bytes.
  1039. More complex packet access may look like::
  1040. R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
  1041. 6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
  1042. 7: r4 = *(u8 *)(r3 +12)
  1043. 8: r4 *= 14
  1044. 9: r3 = *(u32 *)(r1 +76) /* load skb->data */
  1045. 10: r3 += r4
  1046. 11: r2 = r1
  1047. 12: r2 <<= 48
  1048. 13: r2 >>= 48
  1049. 14: r3 += r2
  1050. 15: r2 = r3
  1051. 16: r2 += 8
  1052. 17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */
  1053. 18: if r2 > r1 goto pc+2
  1054. R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
  1055. 19: r1 = *(u8 *)(r3 +4)
  1056. The state of the register R3 is R3=pkt(id=2,off=0,r=8)
  1057. id=2 means that two ``r3 += rX`` instructions were seen, so r3 points to some
  1058. offset within a packet and since the program author did
  1059. ``if (r3 + 8 > r1) goto err`` at insn #18, the safe range is [R3, R3 + 8).
  1060. The verifier only allows 'add'/'sub' operations on packet registers. Any other
  1061. operation will set the register state to 'SCALAR_VALUE' and it won't be
  1062. available for direct packet access.
  1063. Operation ``r3 += rX`` may overflow and become less than original skb->data,
  1064. therefore the verifier has to prevent that. So when it sees ``r3 += rX``
  1065. instruction and rX is more than 16-bit value, any subsequent bounds-check of r3
  1066. against skb->data_end will not give us 'range' information, so attempts to read
  1067. through the pointer will give "invalid access to packet" error.
  1068. Ex. after insn ``r4 = *(u8 *)(r3 +12)`` (insn #7 above) the state of r4 is
  1069. R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits
  1070. of the register are guaranteed to be zero, and nothing is known about the lower
  1071. 8 bits. After insn ``r4 *= 14`` the state becomes
  1072. R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit
  1073. value by constant 14 will keep upper 52 bits as zero, also the least significant
  1074. bit will be zero as 14 is even. Similarly ``r2 >>= 48`` will make
  1075. R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign
  1076. extending. This logic is implemented in adjust_reg_min_max_vals() function,
  1077. which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice
  1078. versa) and adjust_scalar_min_max_vals() for operations on two scalars.
  1079. The end result is that bpf program author can access packet directly
  1080. using normal C code as::
  1081. void *data = (void *)(long)skb->data;
  1082. void *data_end = (void *)(long)skb->data_end;
  1083. struct eth_hdr *eth = data;
  1084. struct iphdr *iph = data + sizeof(*eth);
  1085. struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
  1086. if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
  1087. return 0;
  1088. if (eth->h_proto != htons(ETH_P_IP))
  1089. return 0;
  1090. if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
  1091. return 0;
  1092. if (udp->dest == 53 || udp->source == 9)
  1093. ...;
  1094. which makes such programs easier to write comparing to LD_ABS insn
  1095. and significantly faster.
  1096. eBPF maps
  1097. ---------
  1098. 'maps' is a generic storage of different types for sharing data between kernel
  1099. and userspace.
  1100. The maps are accessed from user space via BPF syscall, which has commands:
  1101. - create a map with given type and attributes
  1102. ``map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size)``
  1103. using attr->map_type, attr->key_size, attr->value_size, attr->max_entries
  1104. returns process-local file descriptor or negative error
  1105. - lookup key in a given map
  1106. ``err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size)``
  1107. using attr->map_fd, attr->key, attr->value
  1108. returns zero and stores found elem into value or negative error
  1109. - create or update key/value pair in a given map
  1110. ``err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)``
  1111. using attr->map_fd, attr->key, attr->value
  1112. returns zero or negative error
  1113. - find and delete element by key in a given map
  1114. ``err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)``
  1115. using attr->map_fd, attr->key
  1116. - to delete map: close(fd)
  1117. Exiting process will delete maps automatically
  1118. userspace programs use this syscall to create/access maps that eBPF programs
  1119. are concurrently updating.
  1120. maps can have different types: hash, array, bloom filter, radix-tree, etc.
  1121. The map is defined by:
  1122. - type
  1123. - max number of elements
  1124. - key size in bytes
  1125. - value size in bytes
  1126. Pruning
  1127. -------
  1128. The verifier does not actually walk all possible paths through the program. For
  1129. each new branch to analyse, the verifier looks at all the states it's previously
  1130. been in when at this instruction. If any of them contain the current state as a
  1131. subset, the branch is 'pruned' - that is, the fact that the previous state was
  1132. accepted implies the current state would be as well. For instance, if in the
  1133. previous state, r1 held a packet-pointer, and in the current state, r1 holds a
  1134. packet-pointer with a range as long or longer and at least as strict an
  1135. alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can't
  1136. have been used by any path from that point, so any value in r2 (including
  1137. another NOT_INIT) is safe. The implementation is in the function regsafe().
  1138. Pruning considers not only the registers but also the stack (and any spilled
  1139. registers it may hold). They must all be safe for the branch to be pruned.
  1140. This is implemented in states_equal().
  1141. Understanding eBPF verifier messages
  1142. ------------------------------------
  1143. The following are few examples of invalid eBPF programs and verifier error
  1144. messages as seen in the log:
  1145. Program with unreachable instructions::
  1146. static struct bpf_insn prog[] = {
  1147. BPF_EXIT_INSN(),
  1148. BPF_EXIT_INSN(),
  1149. };
  1150. Error:
  1151. unreachable insn 1
  1152. Program that reads uninitialized register::
  1153. BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
  1154. BPF_EXIT_INSN(),
  1155. Error::
  1156. 0: (bf) r0 = r2
  1157. R2 !read_ok
  1158. Program that doesn't initialize R0 before exiting::
  1159. BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
  1160. BPF_EXIT_INSN(),
  1161. Error::
  1162. 0: (bf) r2 = r1
  1163. 1: (95) exit
  1164. R0 !read_ok
  1165. Program that accesses stack out of bounds::
  1166. BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
  1167. BPF_EXIT_INSN(),
  1168. Error::
  1169. 0: (7a) *(u64 *)(r10 +8) = 0
  1170. invalid stack off=8 size=8
  1171. Program that doesn't initialize stack before passing its address into function::
  1172. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1173. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1174. BPF_LD_MAP_FD(BPF_REG_1, 0),
  1175. BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
  1176. BPF_EXIT_INSN(),
  1177. Error::
  1178. 0: (bf) r2 = r10
  1179. 1: (07) r2 += -8
  1180. 2: (b7) r1 = 0x0
  1181. 3: (85) call 1
  1182. invalid indirect read from stack off -8+0 size 8
  1183. Program that uses invalid map_fd=0 while calling to map_lookup_elem() function::
  1184. BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
  1185. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1186. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1187. BPF_LD_MAP_FD(BPF_REG_1, 0),
  1188. BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
  1189. BPF_EXIT_INSN(),
  1190. Error::
  1191. 0: (7a) *(u64 *)(r10 -8) = 0
  1192. 1: (bf) r2 = r10
  1193. 2: (07) r2 += -8
  1194. 3: (b7) r1 = 0x0
  1195. 4: (85) call 1
  1196. fd 0 is not pointing to valid bpf_map
  1197. Program that doesn't check return value of map_lookup_elem() before accessing
  1198. map element::
  1199. BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
  1200. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1201. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1202. BPF_LD_MAP_FD(BPF_REG_1, 0),
  1203. BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
  1204. BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
  1205. BPF_EXIT_INSN(),
  1206. Error::
  1207. 0: (7a) *(u64 *)(r10 -8) = 0
  1208. 1: (bf) r2 = r10
  1209. 2: (07) r2 += -8
  1210. 3: (b7) r1 = 0x0
  1211. 4: (85) call 1
  1212. 5: (7a) *(u64 *)(r0 +0) = 0
  1213. R0 invalid mem access 'map_value_or_null'
  1214. Program that correctly checks map_lookup_elem() returned value for NULL, but
  1215. accesses the memory with incorrect alignment::
  1216. BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
  1217. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1218. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1219. BPF_LD_MAP_FD(BPF_REG_1, 0),
  1220. BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
  1221. BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
  1222. BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
  1223. BPF_EXIT_INSN(),
  1224. Error::
  1225. 0: (7a) *(u64 *)(r10 -8) = 0
  1226. 1: (bf) r2 = r10
  1227. 2: (07) r2 += -8
  1228. 3: (b7) r1 = 1
  1229. 4: (85) call 1
  1230. 5: (15) if r0 == 0x0 goto pc+1
  1231. R0=map_ptr R10=fp
  1232. 6: (7a) *(u64 *)(r0 +4) = 0
  1233. misaligned access off 4 size 8
  1234. Program that correctly checks map_lookup_elem() returned value for NULL and
  1235. accesses memory with correct alignment in one side of 'if' branch, but fails
  1236. to do so in the other side of 'if' branch::
  1237. BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
  1238. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1239. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1240. BPF_LD_MAP_FD(BPF_REG_1, 0),
  1241. BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
  1242. BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
  1243. BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
  1244. BPF_EXIT_INSN(),
  1245. BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
  1246. BPF_EXIT_INSN(),
  1247. Error::
  1248. 0: (7a) *(u64 *)(r10 -8) = 0
  1249. 1: (bf) r2 = r10
  1250. 2: (07) r2 += -8
  1251. 3: (b7) r1 = 1
  1252. 4: (85) call 1
  1253. 5: (15) if r0 == 0x0 goto pc+2
  1254. R0=map_ptr R10=fp
  1255. 6: (7a) *(u64 *)(r0 +0) = 0
  1256. 7: (95) exit
  1257. from 5 to 8: R0=imm0 R10=fp
  1258. 8: (7a) *(u64 *)(r0 +0) = 1
  1259. R0 invalid mem access 'imm'
  1260. Program that performs a socket lookup then sets the pointer to NULL without
  1261. checking it::
  1262. BPF_MOV64_IMM(BPF_REG_2, 0),
  1263. BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
  1264. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1265. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1266. BPF_MOV64_IMM(BPF_REG_3, 4),
  1267. BPF_MOV64_IMM(BPF_REG_4, 0),
  1268. BPF_MOV64_IMM(BPF_REG_5, 0),
  1269. BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
  1270. BPF_MOV64_IMM(BPF_REG_0, 0),
  1271. BPF_EXIT_INSN(),
  1272. Error::
  1273. 0: (b7) r2 = 0
  1274. 1: (63) *(u32 *)(r10 -8) = r2
  1275. 2: (bf) r2 = r10
  1276. 3: (07) r2 += -8
  1277. 4: (b7) r3 = 4
  1278. 5: (b7) r4 = 0
  1279. 6: (b7) r5 = 0
  1280. 7: (85) call bpf_sk_lookup_tcp#65
  1281. 8: (b7) r0 = 0
  1282. 9: (95) exit
  1283. Unreleased reference id=1, alloc_insn=7
  1284. Program that performs a socket lookup but does not NULL-check the returned
  1285. value::
  1286. BPF_MOV64_IMM(BPF_REG_2, 0),
  1287. BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
  1288. BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
  1289. BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
  1290. BPF_MOV64_IMM(BPF_REG_3, 4),
  1291. BPF_MOV64_IMM(BPF_REG_4, 0),
  1292. BPF_MOV64_IMM(BPF_REG_5, 0),
  1293. BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
  1294. BPF_EXIT_INSN(),
  1295. Error::
  1296. 0: (b7) r2 = 0
  1297. 1: (63) *(u32 *)(r10 -8) = r2
  1298. 2: (bf) r2 = r10
  1299. 3: (07) r2 += -8
  1300. 4: (b7) r3 = 4
  1301. 5: (b7) r4 = 0
  1302. 6: (b7) r5 = 0
  1303. 7: (85) call bpf_sk_lookup_tcp#65
  1304. 8: (95) exit
  1305. Unreleased reference id=1, alloc_insn=7
  1306. Testing
  1307. -------
  1308. Next to the BPF toolchain, the kernel also ships a test module that contains
  1309. various test cases for classic and internal BPF that can be executed against
  1310. the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and
  1311. enabled via Kconfig::
  1312. CONFIG_TEST_BPF=m
  1313. After the module has been built and installed, the test suite can be executed
  1314. via insmod or modprobe against 'test_bpf' module. Results of the test cases
  1315. including timings in nsec can be found in the kernel log (dmesg).
  1316. Misc
  1317. ----
  1318. Also trinity, the Linux syscall fuzzer, has built-in support for BPF and
  1319. SECCOMP-BPF kernel fuzzing.
  1320. Written by
  1321. ----------
  1322. The document was written in the hope that it is found useful and in order
  1323. to give potential BPF hackers or security auditors a better overview of
  1324. the underlying architecture.
  1325. - Jay Schulist <jschlst@samba.org>
  1326. - Daniel Borkmann <daniel@iogearbox.net>
  1327. - Alexei Starovoitov <ast@kernel.org>