bisecting cause commit starting from f48ad69097fe79d1de13c4d8fef556d4c11c5e68 building syzkaller on 098b5d530648147c744a7c2eb8b78c1307f9d3ce testing commit f48ad69097fe79d1de13c4d8fef556d4c11c5e68 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: f699a4e338339b70664df362b8259baebcc6410cfc86aa517c9c3c9031b97ccd all runs: crashed: BUG: unable to handle kernel NULL pointer dereference in bpf testing release v5.14 testing commit 7d2a07b769330c34b4deabeed939325c77a7ec2f compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 836d1ba0693bb05668a15eadc4e121d3411fd2de1d5a1d53ebf89379cea0ad68 all runs: OK # git bisect start f48ad69097fe79d1de13c4d8fef556d4c11c5e68 7d2a07b769330c34b4deabeed939325c77a7ec2f Bisecting: 6218 revisions left to test after this (roughly 13 steps) [477f70cd2a67904e04c2c2b9bd0fa2e95222f2f6] Merge tag 'drm-next-2021-08-31-1' of git://anongit.freedesktop.org/drm/drm testing commit 477f70cd2a67904e04c2c2b9bd0fa2e95222f2f6 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 529d30f87c112a34881139f7d5e4883f81489db7af92568fe10b0bdd968cf6ad all runs: OK # git bisect good 477f70cd2a67904e04c2c2b9bd0fa2e95222f2f6 Bisecting: 3171 revisions left to test after this (roughly 12 steps) [a2b28235335fee2586b4bd16448fb59ed6c80eef] Merge branch 'dmi-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/jdelvare/staging testing commit a2b28235335fee2586b4bd16448fb59ed6c80eef compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 0ae13587f0a773b7e4376c223f4f755ce51dd470982b32e9d0f582312d5c9801 all runs: OK # git bisect good a2b28235335fee2586b4bd16448fb59ed6c80eef Bisecting: 1591 revisions left to test after this (roughly 11 steps) [7f2cd14129f0272a3ae983625a1adf2545bdad52] Merge tag 'arm64-fixes' of git://git.kernel.org/pub/scm/linux/kernel/git/arm64/linux testing commit 7f2cd14129f0272a3ae983625a1adf2545bdad52 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 87b9b49d7d5f7c1c1fc3793f9c08ea209daadf4ee0ab7f2f7b8bed71747769c2 all runs: OK # git bisect good 7f2cd14129f0272a3ae983625a1adf2545bdad52 Bisecting: 904 revisions left to test after this (roughly 10 steps) [4de593fb965fc2bd11a0b767e0c65ff43540a6e4] Merge tag 'net-5.15-rc4' of git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net testing commit 4de593fb965fc2bd11a0b767e0c65ff43540a6e4 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 9b58cef7af256f60be0080241d7dd5d2949d8e9b062eb846be92fcba0d4065d1 all runs: OK # git bisect good 4de593fb965fc2bd11a0b767e0c65ff43540a6e4 Bisecting: 458 revisions left to test after this (roughly 9 steps) [10d48705d5afb854d2edf3e17a3fb222001425d6] fix up for "net: add new socket option SO_RESERVE_MEM" testing commit 10d48705d5afb854d2edf3e17a3fb222001425d6 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: c68f9c1a52237ef5a616ab925cbc97d97633daa43888fd383521835456195d65 all runs: OK # git bisect good 10d48705d5afb854d2edf3e17a3fb222001425d6 Bisecting: 248 revisions left to test after this (roughly 8 steps) [49ed8dde371522b2d330a7383aaa213748ad007e] net: usb: use eth_hw_addr_set() for dev->addr_len cases testing commit 49ed8dde371522b2d330a7383aaa213748ad007e compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 058026dc1301feb80dc20f535467dea202590379e326bf6d8b2f2404d19039aa all runs: OK # git bisect good 49ed8dde371522b2d330a7383aaa213748ad007e Bisecting: 124 revisions left to test after this (roughly 7 steps) [91b2c0afd00cb01d715d6e9503624ab33580d5b6] selftests/bpf: Add parallelism to test_progs testing commit 91b2c0afd00cb01d715d6e9503624ab33580d5b6 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 0d0e2c1f25277944b7e70b72e22bed4475e4e85627f1e2042488ce5b5a4fac0a all runs: OK # git bisect good 91b2c0afd00cb01d715d6e9503624ab33580d5b6 Bisecting: 62 revisions left to test after this (roughly 6 steps) [e89ef634f81c9d90e1824ab183721f3b361472e6] bpftool: Avoid leaking the JSON writer prepared for program metadata testing commit e89ef634f81c9d90e1824ab183721f3b361472e6 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 8d1cdf4f5ce70146846050dd189e46107a3c96b5ecd9d53238b4e4a55b3a7fe8 all runs: OK # git bisect good e89ef634f81c9d90e1824ab183721f3b361472e6 Bisecting: 31 revisions left to test after this (roughly 5 steps) [14e6cac771355dd5eb0b2cd66164ebd34a1621a7] samples: seccomp: Use __BYTE_ORDER__ testing commit 14e6cac771355dd5eb0b2cd66164ebd34a1621a7 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 95d47b287f3e052e352a89aaec626bd0ae47121e5e7339c0d617b169065846a8 all runs: OK # git bisect good 14e6cac771355dd5eb0b2cd66164ebd34a1621a7 Bisecting: 15 revisions left to test after this (roughly 4 steps) [b066abba3ef16a4a085d237e95da0de3f0b87713] bpf, tests: Add module parameter test_suite to test_bpf module testing commit b066abba3ef16a4a085d237e95da0de3f0b87713 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 543ba0a1ebee28ece5036b149a6ff8a18c85fa8e823417cf34eb13c1e489857f all runs: OK # git bisect good b066abba3ef16a4a085d237e95da0de3f0b87713 Bisecting: 7 revisions left to test after this (roughly 3 steps) [c24941cd3766b6de682dbe6809bd6af12271ab5b] libbpf: Add typeless ksym support to gen_loader testing commit c24941cd3766b6de682dbe6809bd6af12271ab5b compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 6ebe09d806aac3450fb86a326928700f72654e35b17011ce79864a69a0ca4a55 all runs: crashed: BUG: unable to handle kernel NULL pointer dereference in bpf # git bisect bad c24941cd3766b6de682dbe6809bd6af12271ab5b Bisecting: 3 revisions left to test after this (roughly 2 steps) [57fd1c63c9a687c5fdc86fa628c490d6733e8d0b] bpf/benchs: Add benchmark tests for bloom filter throughput + false positive testing commit 57fd1c63c9a687c5fdc86fa628c490d6733e8d0b compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 6f92af19169e05b696d387794d530afaad087cc7d42d738ae0a1593927ce5a09 all runs: crashed: BUG: unable to handle kernel NULL pointer dereference in bpf # git bisect bad 57fd1c63c9a687c5fdc86fa628c490d6733e8d0b Bisecting: 1 revision left to test after this (roughly 1 step) [47512102cde2d252d7b984d9675cfd3420b48ad9] libbpf: Add "map_extra" as a per-map-type extra flag testing commit 47512102cde2d252d7b984d9675cfd3420b48ad9 compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: 6f92af19169e05b696d387794d530afaad087cc7d42d738ae0a1593927ce5a09 all runs: crashed: BUG: unable to handle kernel NULL pointer dereference in bpf # git bisect bad 47512102cde2d252d7b984d9675cfd3420b48ad9 Bisecting: 0 revisions left to test after this (roughly 0 steps) [9330986c03006ab1d33d243b7cfe598a7a3c1baa] bpf: Add bloom filter map implementation testing commit 9330986c03006ab1d33d243b7cfe598a7a3c1baa compiler: gcc (GCC) 10.2.1 20210217, GNU ld (GNU Binutils for Debian) 2.35.2 kernel signature: fbf249a37764c01d840afed671e1662c44ec558a9545f996f191dadf81f975e1 all runs: crashed: BUG: unable to handle kernel NULL pointer dereference in bpf # git bisect bad 9330986c03006ab1d33d243b7cfe598a7a3c1baa 9330986c03006ab1d33d243b7cfe598a7a3c1baa is the first bad commit commit 9330986c03006ab1d33d243b7cfe598a7a3c1baa Author: Joanne Koong Date: Wed Oct 27 16:45:00 2021 -0700 bpf: Add bloom filter map implementation This patch adds the kernel-side changes for the implementation of a bpf bloom filter map. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way: BPF_MAP_LOOKUP_ELEM -> peek BPF_MAP_UPDATE_ELEM -> push The bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps: user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use the bpf_map_peek_elem and bpf_map_push_elem APIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with a key_size of 0. For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value, with a NULL key. In the verifier layer, this requires us to modify the argument type of a bloom filter's BPF_FUNC_map_peek_elem call to ARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that in bpf_map_peek_elem, we know which specific value to query. A few things to please take note of: * If there are any concurrent lookups + updates, the user is responsible for synchronizing this to ensure no false negative lookups occur. * The number of hashes to use for the bloom filter is configurable from userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases both the false positive rate and the speed of a lookup. * Deleting an element in the bloom filter map is not supported. * The bloom filter map may be used as an inner map. * The "max_entries" size that is specified at map creation time is used to approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate. Signed-off-by: Joanne Koong Signed-off-by: Alexei Starovoitov Acked-by: Andrii Nakryiko Link: https://lore.kernel.org/bpf/20211027234504.30744-2-joannekoong@fb.com include/linux/bpf.h | 1 + include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 9 ++ kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 195 +++++++++++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 24 ++++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 9 ++ 8 files changed, 253 insertions(+), 7 deletions(-) create mode 100644 kernel/bpf/bloom_filter.c culprit signature: fbf249a37764c01d840afed671e1662c44ec558a9545f996f191dadf81f975e1 parent signature: 543ba0a1ebee28ece5036b149a6ff8a18c85fa8e823417cf34eb13c1e489857f revisions tested: 16, total time: 3h42m20.054563344s (build: 1h45m41.4542365s, test: 1h54m57.429732154s) first bad commit: 9330986c03006ab1d33d243b7cfe598a7a3c1baa bpf: Add bloom filter map implementation recipients (to): ["andrii@kernel.org" "ast@kernel.org" "joannekoong@fb.com"] recipients (cc): [] crash: BUG: unable to handle kernel NULL pointer dereference in bpf BUG: kernel NULL pointer dereference, address: 0000000000000000 #PF: supervisor instruction fetch in kernel mode #PF: error_code(0x0010) - not-present page PGD 6f43d067 P4D 6f43d067 PUD 18ce0067 PMD 0 Oops: 0010 [#1] PREEMPT SMP KASAN CPU: 1 PID: 8715 Comm: syz-executor.3 Not tainted 5.15.0-rc3-syzkaller #0 Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011 RIP: 0010:0x0 Code: Unable to access opcode bytes at RIP 0xffffffffffffffd6. RSP: 0018:ffffc9000bb67cc0 EFLAGS: 00010246 RAX: dffffc0000000000 RBX: 1ffff9200176cf9f RCX: ffffffff81597b74 RDX: 1ffffffff11a57f6 RSI: 0000000000000000 RDI: ffff88807d8fbc00 RBP: ffffc9000bb67f08 R08: 0000000000000000 R09: ffff8880b9f329cb R10: ffffed10173e6539 R11: 0000000000000001 R12: ffff88807296b180 R13: ffff88807d8fbc00 R14: 0000000000000000 R15: ffffffff88d2bf40 FS: 00007f136831c700(0000) GS:ffff8880b9f00000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: ffffffffffffffd6 CR3: 000000001cf64000 CR4: 00000000003506e0 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 Call Trace: map_delete_elem kernel/bpf/syscall.c:1220 [inline] __sys_bpf+0x274d/0x4540 kernel/bpf/syscall.c:4606 __do_sys_bpf kernel/bpf/syscall.c:4719 [inline] __se_sys_bpf kernel/bpf/syscall.c:4717 [inline] __x64_sys_bpf+0x70/0xb0 kernel/bpf/syscall.c:4717 do_syscall_x64 arch/x86/entry/common.c:50 [inline] do_syscall_64+0x35/0xb0 arch/x86/entry/common.c:80 entry_SYSCALL_64_after_hwframe+0x44/0xae RIP: 0033:0x7f1368ba6ae9 Code: ff ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 bc ff ff ff f7 d8 64 89 01 48 RSP: 002b:00007f136831c188 EFLAGS: 00000246 ORIG_RAX: 0000000000000141 RAX: ffffffffffffffda RBX: 00007f1368cb9f60 RCX: 00007f1368ba6ae9 RDX: 0000000000000020 RSI: 00000000200000c0 RDI: 0000000000000003 RBP: 00007f1368c00f25 R08: 0000000000000000 R09: 0000000000000000 R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000 R13: 00007ffe14c9f00f R14: 00007f136831c300 R15: 0000000000022000 Modules linked in: CR2: 0000000000000000 ---[ end trace fbf65d2d59b6e5b5 ]--- RIP: 0010:0x0 Code: Unable to access opcode bytes at RIP 0xffffffffffffffd6. RSP: 0018:ffffc9000bb67cc0 EFLAGS: 00010246 RAX: dffffc0000000000 RBX: 1ffff9200176cf9f RCX: ffffffff81597b74 RDX: 1ffffffff11a57f6 RSI: 0000000000000000 RDI: ffff88807d8fbc00 RBP: ffffc9000bb67f08 R08: 0000000000000000 R09: ffff8880b9f329cb R10: ffffed10173e6539 R11: 0000000000000001 R12: ffff88807296b180 R13: ffff88807d8fbc00 R14: 0000000000000000 R15: ffffffff88d2bf40 FS: 00007f136831c700(0000) GS:ffff8880b9f00000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: ffffffffffffffd6 CR3: 000000001cf64000 CR4: 00000000003506e0 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400