Re: [PATCH v2] rbtree: fix the red root

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Sunday, January 13, 2019 11:52 PM, Douglas Gilbert <dgilbert@xxxxxxxxxxxx> wrote:

> On 2019-01-13 10:59 p.m., Esme wrote:
>
> > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > On Sunday, January 13, 2019 10:52 PM, Douglas Gilbert dgilbert@xxxxxxxxxxxx wrote:
> >
> > > On 2019-01-13 10:07 p.m., Esme wrote:
> > >
> > > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > > On Sunday, January 13, 2019 9:33 PM, Qian Cai cai@xxxxxx wrote:
> > > >
> > > > > On 1/13/19 9:20 PM, David Lechner wrote:
> > > > >
> > > > > > On 1/11/19 8:58 PM, Michel Lespinasse wrote:
> > > > > >
> > > > > > > On Fri, Jan 11, 2019 at 3:47 PM David Lechner david@xxxxxxxxxxxxxx wrote:
> > > > > > >
> > > > > > > > On 1/11/19 2:58 PM, Qian Cai wrote:
> > > > > > > >
> > > > > > > > > A GPF was reported,
> > > > > > > > > kasan: CONFIG_KASAN_INLINE enabled
> > > > > > > > > kasan: GPF could be caused by NULL-ptr deref or user memory access
> > > > > > > > > general protection fault: 0000 [#1] SMP KASAN
> > > > > > > > >           kasan_die_handler.cold.22+0x11/0x31
> > > > > > > > >           notifier_call_chain+0x17b/0x390
> > > > > > > > >           atomic_notifier_call_chain+0xa7/0x1b0
> > > > > > > > >           notify_die+0x1be/0x2e0
> > > > > > > > >           do_general_protection+0x13e/0x330
> > > > > > > > >           general_protection+0x1e/0x30
> > > > > > > > >           rb_insert_color+0x189/0x1480
> > > > > > > > >           create_object+0x785/0xca0
> > > > > > > > >           kmemleak_alloc+0x2f/0x50
> > > > > > > > >           kmem_cache_alloc+0x1b9/0x3c0
> > > > > > > > >           getname_flags+0xdb/0x5d0
> > > > > > > > >           getname+0x1e/0x20
> > > > > > > > >           do_sys_open+0x3a1/0x7d0
> > > > > > > > >           __x64_sys_open+0x7e/0xc0
> > > > > > > > >           do_syscall_64+0x1b3/0x820
> > > > > > > > >           entry_SYSCALL_64_after_hwframe+0x49/0xbe
> > > > > > > > > It turned out,
> > > > > > > > > gparent = rb_red_parent(parent);
> > > > > > > > > tmp = gparent->rb_right; <-- GPF was triggered here.
> > > > > > > > > Apparently, "gparent" is NULL which indicates "parent" is rbtree's root
> > > > > > > > > which is red. Otherwise, it will be treated properly a few lines above.
> > > > > > > > > /*
> > > > > > > > >    * If there is a black parent, we are done.
> > > > > > > > >    * Otherwise, take some corrective action as,
> > > > > > > > >    * per 4), we don't want a red root or two
> > > > > > > > >    * consecutive red nodes.
> > > > > > > > >    */
> > > > > > > > > if(rb_is_black(parent))
> > > > > > > > >        break;
> > > > > > > > > Hence, it violates the rule #1 (the root can't be red) and need a fix
> > > > > > > > > up, and also add a regression test for it. This looks like was
> > > > > > > > > introduced by 6d58452dc06 where it no longer always paint the root as
> > > > > > > > > black.
> > > > > > > > > Fixes: 6d58452dc06 (rbtree: adjust root color in rb_insert_color() only
> > > > > > > > > when necessary)
> > > > > > > > > Reported-by: Esme esploit@xxxxxxxxxxxxx
> > > > > > > > > Tested-by: Joey Pabalinas joeypabalinas@xxxxxxxxx
> > > > > > > > > Signed-off-by: Qian Cai cai@xxxxxx
> > > > > > > >
> > > > > > > > Tested-by: David Lechner david@xxxxxxxxxxxxxx
> > > > > > > > FWIW, this fixed the following crash for me:
> > > > > > > > Unable to handle kernel NULL pointer dereference at virtual address 00000004
> > > > > > >
> > > > > > > Just to clarify, do you have a way to reproduce this crash without the fix ?
> > > > > >
> > > > > > I am starting to suspect that my crash was caused by some new code
> > > > > > in the drm-misc-next tree that might be causing a memory corruption.
> > > > > > It threw me off that the stack trace didn't contain anything related
> > > > > > to drm.
> > > > > > See: https://patchwork.freedesktop.org/patch/276719/
> > > > >
> > > > > It may be useful for those who could reproduce this issue to turn on those
> > > > > memory corruption debug options to narrow down a bit.
> > > > > CONFIG_DEBUG_PAGEALLOC=y
> > > > > CONFIG_DEBUG_PAGEALLOC_ENABLE_DEFAULT=y
> > > > > CONFIG_KASAN=y
> > > > > CONFIG_KASAN_GENERIC=y
> > > > > CONFIG_SLUB_DEBUG_ON=y
> > > >
> > > > I have been on SLAB, I configured SLAB DEBUG with a fresh pull from github. Linux syzkaller 5.0.0-rc2 #9 SMP Sun Jan 13 21:57:40 EST 2019 x86_64
> > > > ...
> > > > In an effort to get a different stack into the kernel, I felt that nothing works better than fork bomb? :)
> > > > Let me know if that helps.
> > > > root@syzkaller:~# gcc -o test3 test3.c
> > > > root@syzkaller:~# while : ; do ./test3 & done
> > >
> > > And is test3 the same multi-threaded program that enters the kernel via
> > > /dev/sg0 and then calls SCSI_IOCTL_SEND_COMMAND which goes to the SCSI
> > > mid-level and thence to the block layer?
> > > And please remind me, does it also fail on lk 4.20.2 ?
> > > Doug Gilbert
> >
> > Yes, the same C repro from the earlier thread. It was a 4.20.0 kernel where it was first detected. I can move to 4.20.2 and see if that changes anything.
>
> Hi,
> I don't think there is any need to check lk 4.20.2 (as it would
> be very surprising if it didn't also have this "feature").
>
> More interesting might be: has "test3" been run on lk 4.19 or
> any earlier kernel?
>
> Doug Gilbert

I did not yet verify the previous branches but did tune out kmemleak (CONFIG_DEBUG_MEMLEAK no longer set) as it seemed a bit obtrusive in this matter, this is what I see now (note redzone?).
/Esme

  114.826116] =============================================================================
[  114.828121] BUG kmalloc-64 (Tainted: G        W        ): Padding overwritten. 0x000000006913c65d-0x000000006e410492
[  114.830551] -----------------------------------------------------------------------------
[  114.830551]
[  114.832755] INFO: Slab 0x0000000054f47c55 objects=19 used=19 fp=0x          (null) flags=0x1fffc0000010200
[  114.835063] CPU: 0 PID: 6310 Comm: x Tainted: G    B   W         5.0.0-rc2 #15
[  114.836829] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.11.1-1ubuntu1 04/01/2014
[  114.838847] Call Trace:
[  114.839497]  dump_stack+0x1d8/0x2c6
[  114.840274]  ? dump_stack_print_info.cold.1+0x20/0x20
[  114.841402]  slab_err+0xab/0xcf
[  114.842103]  ? __asan_report_load1_noabort+0x14/0x20
[  114.843244]  ? memchr_inv+0x2c1/0x330
[  114.844059]  slab_pad_check.part.50.cold.87+0x27/0x81
[  114.845123]  ? __request_module+0x434/0xede
[  114.846012]  check_slab+0xb0/0xf0
[  114.846715]  alloc_debug_processing+0x58/0x170
[  114.847648]  ___slab_alloc+0x63e/0x750
[  114.848439]  ? __request_module+0x434/0xede
[  114.849368]  ? trace_hardirqs_on+0x2f0/0x2f0
[  114.850299]  ? check_same_owner+0x340/0x340
[  114.851212]  ? vsnprintf+0x207/0x1b50
[  114.852015]  ? __request_module+0x434/0xede
[  114.852960]  __slab_alloc+0x68/0xc0
[  114.853715]  ? __slab_alloc+0x68/0xc0
[  114.854540]  kmem_cache_alloc_trace+0x2aa/0x330
[  114.855527]  ? __request_module+0x434/0xede
[  114.856416]  __request_module+0x434/0xede
[  114.857271]  ? free_modprobe_argv+0xa0/0xa0
[  114.858159]  ? kasan_check_write+0x14/0x20
[  114.859025]  ? __init_rwsem+0x1cc/0x2a0
[  114.859840]  ? spin_dump.cold.3+0xe7/0xe7
[  114.860690]  ? deactivate_slab.isra.70+0x589/0x5c0
[  114.861699]  ? __sanitizer_cov_trace_cmp4+0x16/0x20
[  114.862801]  ? map_id_range_down+0x1ee/0x430
[  114.863744]  ? __put_user_ns+0x60/0x60
[  114.864571]  ? set_track+0x74/0x120
[  114.865373]  ? init_object+0x79/0x80
[  114.866153]  ? lockdep_init_map+0x105/0x590
[  114.867074]  ? lockdep_init_map+0x105/0x590
[  114.867996]  ? kasan_check_write+0x14/0x20
[  114.868873]  ? inode_init_always+0xae1/0xd80
[  114.869787]  ? lock_acquire+0x1ed/0x510
[  114.870617]  ? new_inode_pseudo+0xcc/0x1a0
[  114.871517]  ? lock_downgrade+0x8f0/0x8f0
[  114.872471]  ? kasan_check_read+0x11/0x20
[  114.873357]  ? do_raw_spin_unlock+0xa7/0x330
[  114.874272]  ? do_raw_spin_trylock+0x270/0x270
[  114.875209]  ? _raw_spin_unlock+0x22/0x30
[  114.876040]  ? prune_icache_sb+0x1c0/0x1c0
[  114.876908]  ? __kasan_slab_free+0x13f/0x170
[  114.877807]  ? __sanitizer_cov_trace_const_cmp4+0x16/0x20
[  114.878995]  ? __sock_create+0x23f/0x930
[  114.879840]  __sock_create+0x6e2/0x930
[  114.880647]  ? kernel_sock_ip_overhead+0x570/0x570
[  114.881675]  ? __kasan_slab_free+0x13f/0x170
[  114.882624]  ? putname+0xf2/0x130
[  114.883347]  ? kasan_slab_free+0xe/0x10
[  114.884198]  ? kmem_cache_free+0x2aa/0x330
[  114.885058]  ? putname+0xf7/0x130
[  114.885763]  __sys_socket+0x106/0x260
[  114.886553]  ? move_addr_to_kernel+0x70/0x70
[  114.887506]  ? entry_SYSCALL_64_after_hwframe+0x49/0xbe
[  114.888633]  ? __bpf_trace_preemptirq_template+0x30/0x30
[  114.889743]  __x64_sys_socket+0x73/0xb0
[  114.890548]  do_syscall_64+0x1b3/0x810
[  114.891357]  ? entry_SYSCALL_64_after_hwframe+0x3e/0xbe
[  114.892487]  ? syscall_return_slowpath+0x5e0/0x5e0
[  114.893531]  ? trace_hardirqs_off_thunk+0x1a/0x1c
[  114.894497]  ? trace_hardirqs_on_caller+0x2e0/0x2e0
[  114.895505]  ? prepare_exit_to_usermode+0x3b0/0x3b0
[  114.896516]  ? prepare_exit_to_usermode+0x291/0x3b0
[  114.897567]  ? trace_hardirqs_off_thunk+0x1a/0x1c
[  114.898564]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
[  114.899670] RIP: 0033:0x7fa123f52229
[  114.900433] Code: 00 f3 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 8b 0d 3f 4c 28
[  114.904409] RSP: 002b:00007ffcd04e76f8 EFLAGS: 00000213 ORIG_RAX: 0000000000000029
[  114.905990] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fa123f52229
[  114.907464] RDX: 0000000000000088 RSI: 0000000000000800 RDI: 000000000000000c
[  114.908913] RBP: 00007ffcd04e7710 R08: 0000000000000000 R09: 000000000000001a
[  114.910348] R10: 000000000000ffff R11: 0000000000000213 R12: 0000560c05dffe30
[  114.911858] R13: 00007ffcd04e7830 R14: 0000000000000000 R15: 0000000000000000
[  114.913404] Padding 000000006913c65d: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.915437] Padding 000000002d53f25c: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.917390] Padding 0000000078f7d621: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.919402] Padding 0000000063547658: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.921414] Padding 000000001a301f4e: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.923364] Padding 0000000046589d24: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.925340] Padding 0000000008fb13da: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.927291] Padding 00000000ae5cc298: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.929239] Padding 00000000d49cc239: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.931177] Padding 00000000d66ad6f5: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.933110] Padding 00000000069ad671: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.934986] Padding 00000000ffaf648c: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.936895] Padding 00000000c96d1b58: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.938848] Padding 00000000768e4920: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.940965] Padding 000000000d06b43c: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.942890] Padding 00000000af5ae9fa: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.944790] Padding 000000006b526f1e: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.946727] Padding 000000009c8dffe3: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.948709] FIX kmalloc-64: Restoring 0x000000006913c65d-0x000000006e410492=0x5a
[  114.948709]
[  114.950620] =============================================================================
[  114.952450] BUG kmalloc-64 (Tainted: G    B   W        ): Redzone overwritten
[  114.953901] -----------------------------------------------------------------------------
[  114.953901]
[  114.955955] INFO: 0x0000000023852d36-0x000000003d7a667f. First byte 0x0 instead of 0xbb
[  114.957662] INFO: Slab 0x0000000054f47c55 objects=19 used=19 fp=0x          (null) flags=0x1fffc0000010200
[  114.959669] INFO: Object 0x00000000a07d3417 @offset=3336 fp=0x          (null)
[  114.959669]
[  114.961491] Redzone 0000000023852d36: 00 00 00 00 00 00 00 00                          ........
[  114.963588] Object 00000000a07d3417: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.965520] Object 000000002b232d06: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.967533] Object 000000000b434529: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.969480] Object 0000000098adb243: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
[  114.971505] Redzone 0000000026bb1e28: 00 00 00 00 00 00 00 00                          ........
[  114.973502] Padding 00000000e8bc385c: 00 00 00 00 00 00 00 00                          ........
[  114.975687] CPU: 0 PID: 6310 Comm: x Tainted: G    B   W         5.0.0-rc2 #15
[  114.977357] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.11.1-1ubuntu1 04/01/2014
[  114.979208] Call Trace:
[  114.979755]  dump_stack+0x1d8/0x2c6
[  114.980541]  ? dump_stack_print_info.cold.1+0x20/0x20
[  114.981691]  ? print_section+0x41/0x50
[  114.982565]  print_trailer+0x172/0x17b
[  114.983380]  check_bytes_and_report.cold.86+0x40/0x70
[  114.984695]  check_object+0x16c/0x290
[  114.985547]  ? __request_module+0x434/0xede
[  114.986511]  alloc_debug_processing+0xda/0x170
[  114.987497]  ___slab_alloc+0x63e/0x750
[  114.988291]  ? __request_module+0x434/0xede
[  114.989177]  ? trace_hardirqs_on+0x2f0/0x2f0
[  114.990069]  ? check_same_owner+0x340/0x340
[  114.991005]  ? vsnprintf+0x207/0x1b50
[  114.991786]  ? __request_module+0x434/0xede
[  114.992710]  __slab_alloc+0x68/0xc0
[  114.993440]  ? __slab_alloc+0x68/0xc0
[  114.994216]  kmem_cache_alloc_trace+0x2aa/0x330
[  114.995278]  ? __request_module+0x434/0xede
[  114.996253]  __request_module+0x434/0xede
[  114.997262]  ? free_modprobe_argv+0xa0/0xa0
[  114.998160]  ? kasan_check_write+0x14/0x20
[  114.999033]  ? __init_rwsem+0x1cc/0x2a0
[  114.999842]  ? spin_dump.cold.3+0xe7/0xe7
[  115.000684]  ? deactivate_slab.isra.70+0x589/0x5c0
[  115.001739]  ? __sanitizer_cov_trace_cmp4+0x16/0x20
[  115.002836]  ? map_id_range_down+0x1ee/0x430
[  115.003804]  ? __put_user_ns+0x60/0x60
[  115.004630]  ? set_track+0x74/0x120
[  115.005395]  ? init_object+0x79/0x80
[  115.006185]  ? lockdep_init_map+0x105/0x590
[  115.007082]  ? lockdep_init_map+0x105/0x590
[  115.007957]  ? kasan_check_write+0x14/0x20
[  115.008916]  ? inode_init_always+0xae1/0xd80
[  115.009820]  ? lock_acquire+0x1ed/0x510
[  115.010645]  ? new_inode_pseudo+0xcc/0x1a0
[  115.011513]  ? lock_downgrade+0x8f0/0x8f0
[  115.012421]  ? kasan_check_read+0x11/0x20
[  115.013294]  ? do_raw_spin_unlock+0xa7/0x330
[  115.014229]  ? do_raw_spin_trylock+0x270/0x270
[  115.015180]  ? _raw_spin_unlock+0x22/0x30
[  115.016034]  ? prune_icache_sb+0x1c0/0x1c0
[  115.016918]  ? __kasan_slab_free+0x13f/0x170
[  115.017831]  ? __sanitizer_cov_trace_const_cmp4+0x16/0x20
[  115.019010]  ? __sock_create+0x23f/0x930
[  115.019871]  __sock_create+0x6e2/0x930
[  115.020673]  ? kernel_sock_ip_overhead+0x570/0x570
[  115.021703]  ? __kasan_slab_free+0x13f/0x170
[  115.022677]  ? putname+0xf2/0x130
[  115.023383]  ? kasan_slab_free+0xe/0x10
[  115.024193]  ? kmem_cache_free+0x2aa/0x330
[  115.025062]  ? putname+0xf7/0x130
[  115.025771]  __sys_socket+0x106/0x260
[  115.026549]  ? move_addr_to_kernel+0x70/0x70
[  115.027462]  ? entry_SYSCALL_64_after_hwframe+0x49/0xbe
[  115.028560]  ? __bpf_trace_preemptirq_template+0x30/0x30
[  115.029707]  __x64_sys_socket+0x73/0xb0
[  115.030523]  do_syscall_64+0x1b3/0x810
[  115.031319]  ? entry_SYSCALL_64_after_hwframe+0x3e/0xbe
[  115.032451]  ? syscall_return_slowpath+0x5e0/0x5e0
[  115.033472]  ? trace_hardirqs_off_thunk+0x1a/0x1c
[  115.034471]  ? trace_hardirqs_on_caller+0x2e0/0x2e0
[  115.035503]  ? prepare_exit_to_usermode+0x3b0/0x3b0
[  115.036613]  ? prepare_exit_to_usermode+0x291/0x3b0
[  115.037647]  ? trace_hardirqs_off_thunk+0x1a/0x1c
[  115.038645]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
[  115.039678] RIP: 0033:0x7fa123f52229
[  115.040423] Code: 00 f3 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 8b 0d 3f 4c 2b
[  115.044451] RSP: 002b:00007ffcd04e76f8 EFLAGS: 00000213 ORIG_RAX: 0000000000000029
[  115.046010] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fa123f52229
[  115.047462] RDX: 0000000000000088 RSI: 0000000000000800 RDI: 000000000000000c
[  115.048938] RBP: 00007ffcd04e7710 R08: 0000000000000000 R09: 000000000000001a
[  115.050379] R10: 000000000000ffff R11: 0000000000000213 R12: 0000560c05dffe30
[  115.051849] R13: 00007ffcd04e7830 R14: 0000000000000000 R15: 0000000000000000
[  115.053422] FIX kmalloc-64: Restoring 0x0000000023852d36-0x000000003d7a667f=0xbb
[  115.053422]
[  115.055233] FIX kmalloc-64: Marking all objects used
[12] 6325
[  115.075174] hrtimer: interrupt took 169862 ns
[13] 6362







[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Bugtraq]     [Linux OMAP]     [Linux MIPS]     [eCos]     [Asterisk Internet PBX]     [Linux API]

  Powered by Linux