From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.8 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_PASS, URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2ED7BC43387 for ; Fri, 11 Jan 2019 23:47:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D1EC921841 for ; Fri, 11 Jan 2019 23:47:11 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=lechnology.com header.i=@lechnology.com header.b="MxneUu/E" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726399AbfAKXrK (ORCPT ); Fri, 11 Jan 2019 18:47:10 -0500 Received: from vern.gendns.com ([98.142.107.122]:45290 "EHLO vern.gendns.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725915AbfAKXrK (ORCPT ); Fri, 11 Jan 2019 18:47:10 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lechnology.com; s=default; h=Content-Transfer-Encoding:Content-Type: In-Reply-To:MIME-Version:Date:Message-ID:From:References:Cc:To:Subject:Sender :Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help: List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=X35e+hYFb9x7HJ2LK34dmNG58JhOx/gJ6f+kdmWI+ek=; b=MxneUu/Efoq0rde48mo+Uu9W+w ICdqCcn7g3bYT/08+npi1jmX7FFhyM3y1rRcOAvGxJ9Gy82AY1lA6xwNkW7BlnNAzGYPBrDt7SGVb OwA/Mgz9S0MI6SDOOZOGJqQ9od868F71tQy1fkijIHzjLtvPpXWszAX+oWtm2jt/6EzC0NQdfxih4 NQc4gI9tp6jLcVgDTl86cYjCxkEGQv35zo3/bc5Efn8anpcNPA+jV8h8oYr4X7iKGpAH8WTkCqoV1 X/pRbrB8X5lGvYTG6LvQLGru50hHW9RGYGQD26UrHifP+xj7LPlg/eX3C2l/DKoEU/SlfzDC/Rgqg Rlmdj3mA==; Received: from 108-198-5-147.lightspeed.okcbok.sbcglobal.net ([108.198.5.147]:33658 helo=[192.168.0.134]) by vern.gendns.com with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.91) (envelope-from ) id 1gi6TU-0000GF-5t; Fri, 11 Jan 2019 18:44:28 -0500 Subject: Re: [PATCH v2] rbtree: fix the red root To: Qian Cai , akpm@linux-foundation.org Cc: esploit@protonmail.ch, jejb@linux.ibm.com, dgilbert@interlog.com, martin.petersen@oracle.com, joeypabalinas@gmail.com, walken@google.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org References: <20190111181600.GJ6310@bombadil.infradead.org> <20190111205843.25761-1-cai@lca.pw> From: David Lechner Message-ID: Date: Fri, 11 Jan 2019 17:47:05 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 In-Reply-To: <20190111205843.25761-1-cai@lca.pw> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - vern.gendns.com X-AntiAbuse: Original Domain - vger.kernel.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - lechnology.com X-Get-Message-Sender-Via: vern.gendns.com: authenticated_id: davidmain+lechnology.com/only user confirmed/virtual account not confirmed X-Authenticated-Sender: vern.gendns.com: davidmain@lechnology.com X-Source: X-Source-Args: X-Source-Dir: Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 > Tested-by: Joey Pabalinas > Signed-off-by: Qian Cai > --- Tested-by: David Lechner FWIW, this fixed the following crash for me: Unable to handle kernel NULL pointer dereference at virtual address 00000004 pgd = (ptrval) [00000004] *pgd=00000000 Internal error: Oops: 5 [#1] PREEMPT ARM Modules linked in: CPU: 0 PID: 1 Comm: swapper Not tainted 5.0.0-rc1-00126-g27b09b277853 #1360 Hardware name: Generic DA850/OMAP-L138/AM18x PC is at rb_insert_color+0x1c/0x1a4 LR is at kernfs_link_sibling+0x94/0xcc pc : [] lr : [] psr: 60000013 sp : c2831b38 ip : 00000000 fp : c06b762c r10: 00000000 r9 : c06b835c r8 : 00000000 r7 : c2963f00 r6 : c066b028 r5 : c2016cc0 r4 : 00000000 r3 : 00000000 r2 : c2983010 r1 : c2963f2c r0 : c2016cd0 Flags: nZCv IRQs on FIQs on Mode SVC_32 ISA ARM Segment none Control: 0005317f Table: c0004000 DAC: 00000053 Process swapper (pid: 1, stack limit = 0x(ptrval)) Stack: (0xc2831b38 to 0xc2832000) 1b20: 00000000 c2016cc0 1b40: c066b028 c014bfdc c2016cc0 c2963f00 c066b028 c014c768 c2963f00 c014c448 1b60: 00000000 c2016cc0 c2963f00 c066b028 c2963f00 c014c860 00000000 00000001 1b80: c0589938 c2b4b408 00000000 c014ec70 00000000 c2b4b408 00000000 c04c4cb0 1ba0: 0000070f 00000000 00000000 9fd04dd9 00000000 c2b4b408 c066b028 00000000 1bc0: c293ac98 c04b58f8 c059081c 00000000 c2b4b408 c066b028 00000000 00000000 1be0: 00000000 c04b5d64 c2831c08 9fd04dd9 c2b4b3c0 c293ac80 c2bd16c0 c2b4b408 1c00: c00d650c c059081c c2bd16c0 c28e3a80 c2b4b3c0 00000000 c2b4b3c0 00000000 1c20: c06b7634 00020000 c06b835c c00d72f8 00000000 c00b0c24 00000000 00000074 1c40: c0590728 00000000 c0590728 c2b4b3c0 00000074 c0590728 00020000 00000000 1c60: c06b762c c00b0958 00000000 00380bc6 00000000 c06bbf1c c2bd9c00 c2bfe000 1c80: c06bbf14 0000000c 00000000 00000000 c2831e0c c00b0a90 00000000 00000000 1ca0: 00000000 00000000 003b2580 c017d6e4 00000000 00000000 00000000 c2bfe000 1cc0: c2bd9c00 00000000 003b2580 00000000 00000000 c01971a0 00001103 00000000 1ce0: c2bd8400 00000400 00000400 9fd04dd9 00000000 0000000a 00000002 00000000 1d00: ffffffff 00000000 ffffffff 00000000 00000000 00000001 00000a04 00000032 1d20: 00000000 0000000c 00000004 c00af550 c2bd9ecc 9fd04dd9 c2404480 c2bd9eb4 1d40: c2bd8400 c2404480 00000002 00000001 00000000 00000000 00000001 00000000 1d60: 00000000 00000000 00000000 00000000 00000000 00000000 00000001 00000000 1d80: 00380bc6 00000000 003b257f 00000000 00000077 0000ffff 00000200 00000002 1da0: 00000001 0000ffff 00000000 00000401 c2bfe22c 00000000 00000000 00000000 1dc0: 00000000 00000000 c2012400 c24be100 00001000 00000000 c2404480 00000000 1de0: 00004003 9fd04dd9 00000000 c2bd9c00 c2404480 00000083 c24044fc 00008000 1e00: 00000000 00000020 00008000 c00e4d88 c2404480 00000000 00000000 c0190afc 1e20: c2bd0be0 c0692898 c0692898 00000000 00000020 c0190b10 c0194f48 c2bd0be0 1e40: c066b370 c00e568c c29f5000 c01002d4 c29f5000 c2bd0be0 00008000 c0100488 1e60: c0692898 00000000 c066b028 c2bd0be0 c2bd0bc0 c01033ec 00000000 ffffff00 1e80: ffff0a00 c0575ff4 c2bd0be0 c281a010 c2417098 c2bd0be0 0000000a 00000000 1ea0: 0000000a 9fd04dd9 0000000a c2bd0be0 c2bd0bc0 00000000 c0575ff8 00008000 1ec0: c066b028 00008000 c0575ff4 c0104178 00000000 00000000 c2014000 c2014005 1ee0: c0575ff8 c3fb1280 c0652868 c062b1ec 00000000 c01013d8 c24c3558 00000000 1f00: 00000000 00006180 c24c3558 c00f17c4 e10c76ac 0b300002 c2858015 c281a010 1f20: c2415da8 9fd04dd9 00000000 00000002 c06ad310 c066b028 c066da68 00000000 1f40: 00000000 00000000 00000000 c062b478 00000000 c0037200 00306b6c 9fd00000 1f60: c0576098 9fd04dd9 00000002 c06ad310 c0652878 00000000 00000000 00000000 1f80: 00000000 00000000 00000000 c062b5e4 00000000 00000000 00000000 00000000 1fa0: c04c7860 c04c7868 00000000 c00090e0 00000000 00000000 00000000 00000000 1fc0: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 1fe0: 00000000 00000000 00000000 00000000 00000013 00000000 00000000 00000000 [] (rb_insert_color) from [] (kernfs_link_sibling+0x94/0xcc) [] (kernfs_link_sibling) from [] (kernfs_add_one+0x90/0x140) [] (kernfs_add_one) from [] (kernfs_create_dir_ns+0x48/0x74) [] (kernfs_create_dir_ns) from [] (sysfs_create_dir_ns+0x68/0xd0) [] (sysfs_create_dir_ns) from [] (kobject_add_internal+0x9c/0x2c4) [] (kobject_add_internal) from [] (kobject_init_and_add+0x54/0x94) [] (kobject_init_and_add) from [] (sysfs_slab_add+0x10c/0x220) [] (sysfs_slab_add) from [] (__kmem_cache_create+0x1d8/0x338) [] (__kmem_cache_create) from [] (kmem_cache_create_usercopy+0x180/0x298) [] (kmem_cache_create_usercopy) from [] (kmem_cache_create+0x20/0x28) [] (kmem_cache_create) from [] (ext4_mb_init+0x374/0x44c) [] (ext4_mb_init) from [] (ext4_fill_super+0x2258/0x2ef0) [] (ext4_fill_super) from [] (mount_bdev+0x154/0x18c) [] (mount_bdev) from [] (ext4_mount+0x14/0x20) [] (ext4_mount) from [] (mount_fs+0x14/0xa8) [] (mount_fs) from [] (vfs_kern_mount+0x48/0xf0) [] (vfs_kern_mount) from [] (do_mount+0x180/0xb9c) [] (do_mount) from [] (ksys_mount+0x8c/0xb4) [] (ksys_mount) from [] (mount_block_root+0x128/0x2a4) [] (mount_block_root) from [] (mount_root+0x110/0x154) [] (mount_root) from [] (prepare_namespace+0x128/0x188) [] (prepare_namespace) from [] (kernel_init+0x8/0xf4) [] (kernel_init) from [] (ret_from_fork+0x14/0x34) Exception stack(0xc2831fb0 to 0xc2831ff8) 1fa0: 00000000 00000000 00000000 00000000 1fc0: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 1fe0: 00000000 00000000 00000000 00000000 00000013 00000000 Code: e5923000 e3130001 1a000054 e92d4070 (e593c004) ---[ end trace 1c5a7737a0eab0f2 ]--- Kernel panic - not syncing: Attempted to kill init! exitcode=0x0000000b ---[ end Kernel panic - not syncing: Attempted to kill init! exitcode=0x0000000b ]---