Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Liam Howlett <liam.howlett@oracle.com>
To:     Qian Cai <quic_qiancai@quicinc.com>
CC:     "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>
Subject: Re: [PATCH v6 00/71] Introducing the Maple Tree
Thread-Topic: [PATCH v6 00/71] Introducing the Maple Tree
Thread-Index: AQHYInmXxzMTjmF25U+e/3QAVwcn6KyjsEsAgAEA+wA=
Date:   Fri, 25 Feb 2022 19:08:54 +0000
Message-ID: <20220225190846.u4fwebimd5ejfdpd@revolver>
References: <20220215143728.3810954-1-Liam.Howlett@oracle.com>
 <YhhRrBpXTFolUAKi@qian>
In-Reply-To: <YhhRrBpXTFolUAKi@qian>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?lvAT9mCVnW1RtUhT7xwVGJbZtP6mzF4VYXYJRVC9laUfvo5M4JnZwETkAMKt?=
 =?us-ascii?Q?OKAuWOdChPQ5CWE0/iwHdjS5wHExcu0TMlurPiX/YrQucAG9y1/JhR7svrwT?=
 =?us-ascii?Q?rwtmS1wuE3Cx+wH4C1NDlQWT5J/i6S5urFTMyQIe0bMNRm0mL4fVPw8yIK12?=
 =?us-ascii?Q?vwfU93bEYAHk+abPIdFiMwZ/SLtZx9FpOornt1zQyx7wJ3SsoDzNkhXfpoUI?=
 =?us-ascii?Q?8OdSUPGpH0922WJEMmZpneneGvDvTdEWySirXHFk/HHS/Z5K2tSGgoVkb5FW?=
 =?us-ascii?Q?pCJmsJifOOgM2T0PbJAOpCmQjPoX8+iNwXn3r08ybESlNaJJBBBMHYG0KAXq?=
 =?us-ascii?Q?xamr7qLMtmGaB0kmc7FSQgFGLBSYBcQaykig+OXItpYLnNY40L2uWbwa71JY?=
 =?us-ascii?Q?TaQX8QHJ3ma8ciEqi5sS18SyMlTkv1va3ENCynIVyLn2O5PsBjv52GXaDrwK?=
 =?us-ascii?Q?NQKD4FJm/IOU02+Gl2Vgym+t+oF3i6qVxlN7t0ytyxgoe2hjDE4cQaMFDKdC?=
 =?us-ascii?Q?fhpFYwrtAiIJlsJleueSugo0FCVLcPhw5QPfqWXK1PWVAiUYnjckPLd9mSrH?=
 =?us-ascii?Q?8rr/SFSluL3jIL45wCZa+Pa1Ux5MHkeli2+3194ZTsHuw/QvSA+drW9X/RP/?=
 =?us-ascii?Q?a0OpYMgopQnFy96GREP5D+5IfQXsI5wOiuNL5T8C4GimA5elSQRSai4aAJvY?=
 =?us-ascii?Q?Vfw1Mz0G7ET6doctLQVhvaHl0LsHAtdy68HU0ggKG2H006kXvhFU2tvEgwwc?=
 =?us-ascii?Q?jKUL3AZjgwKScb4lzcw2psPxlpMvPnr/30kz6BEtN7IlFnJ3e1x5uXqfFaEQ?=
 =?us-ascii?Q?RO/BXtJsiqA1tAvmYubevGWYm+84TIU3W4K2gbYzr7feSHn5LPEDqlrnN0N3?=
 =?us-ascii?Q?KkBgCs8NXZkRc129ptc/DgwAlRioQx7x+F0aC7IdMD4Rl32lDx4NHQqRajYK?=
 =?us-ascii?Q?H9Aumlzui1+6AxU4TsENSb0iQhh60GJYOWotwkHcW93F8Ow3lA2hIqZuLlx3?=
 =?us-ascii?Q?J76s9n9ftSig3VOkfXK60bUVV/fsetBTwD7EX2qbiU6eJUwSgKSXVcnBGBkH?=
 =?us-ascii?Q?VuUx4c/a5sW+z0jTqdu/5OadbcdnGfmKOSKyWHYSGa4X7YlQRkkCJtCPvShi?=
 =?us-ascii?Q?WVgxufbBh1D3aoPd7/3W9jqY5GB2Jy6wlLQ95SbcW21kU3JippzdOw1TZ5Yq?=
 =?us-ascii?Q?XtMjmizsQSFxG5PresFsy4/f6NW2c5PD8we4PApl1nW9yo12Ct1hQofkzdIo?=
 =?us-ascii?Q?iopLT78JFHpwKc5no40n8IqYZsZvQPIM8/NIwZT3O57Is9eKji5hPH1F56AS?=
 =?us-ascii?Q?OtKoFf+b9thzUKOAvj6y1RdAXe9PqN2O1Zy6z74I5ty1ezxOeObQLwCgrq1d?=
 =?us-ascii?Q?oeAyASLkxxDMMGHqQ65pHJqMnHAuPp7vfy98LORcjQzFV0I/hd9Ms/9YYYje?=
 =?us-ascii?Q?YPGpPNVm2I0EaPqCHXntPrlhmD+Cgdhd2buvtHlprt4Yl4CWEIjv53hvLOq3?=
 =?us-ascii?Q?e0Nhw9HbqZQ4C3/pFchWF8iaSVI1zQE3Q/mmR9DZGwP/lwnKePyShpOuMrPa?=
 =?us-ascii?Q?M7DCosIJc3l5WvcBft7LLN2yFqf8Z/B7Xo0JhsAgFnpZC/PDnxgVRB1xkUhs?=
 =?us-ascii?Q?GWBPrYWhaUi3KWBoacwWnnA=3D?=
Content-Type: text/plain; charset="us-ascii"
Content-ID: <9A2FA54979E55442B9345472585E5571@namprd10.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 48dee574-d959-457c-b0fb-08d9f8924468
X-MS-Exchange-CrossTenant-originalarrivaltime: 25 Feb 2022 19:08:54.5636
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: OM6yJKTeYFgTAeJNgGw7qqPPYSP4o2ROC74kpN8hHteTaAm8XjwS73sPxbzRHnuHgCxXsQC1xViDQ83Pk9krXg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB4111
X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10268 signatures=684655
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 suspectscore=0 adultscore=0
 malwarescore=0 phishscore=0 mlxlogscore=999 mlxscore=0 bulkscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2201110000
 definitions=main-2202250109
X-Proofpoint-GUID: cSyhj4cH-eLxT6d2W-YmspV2pOFh--X5
X-Proofpoint-ORIG-GUID: cSyhj4cH-eLxT6d2W-YmspV2pOFh--X5
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,
        T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

* Qian Cai <quic_qiancai@quicinc.com> [220224 22:49]:
> On Tue, Feb 15, 2022 at 02:37:44PM +0000, Liam Howlett wrote:
> > The maple tree is an RCU-safe range based B-tree designed to use modern
> > processor cache efficiently.  There are a number of places in the kerne=
l
> > that a non-overlapping range-based tree would be beneficial, especially
> > one with a simple interface.  The first user that is covered in this
> > patch set is the vm_area_struct, where three data structures are
> > replaced by the maple tree: the augmented rbtree, the vma cache, and th=
e
> > linked list of VMAs in the mm_struct.  The long term goal is to reduce
> > or remove the mmap_sem contention.
> >=20
> > The tree has a branching factor of 10 for non-leaf nodes and 16 for lea=
f
> > nodes.  With the increased branching factor, it is significantly shorte=
r than
> > the rbtree so it has fewer cache misses.  The removal of the linked lis=
t
> > between subsequent entries also reduces the cache misses and the need t=
o pull
> > in the previous and next VMA during many tree alterations.
> >=20
> > This patch is based on v5.17-rc4
> >=20
> > git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220214
>=20
> Just a heads-up. I noticed an use-after-free in today's linux-next below.=
 I
> am running out of time to fully triage this, but I noticed this is the on=
ly
> series (not sure which revision) heavily touched mm/mmap.c recently there=
.
>=20
>  BUG: KASAN: use-after-free in move_vma.isra.0
>  Read of size 8 at addr ffff0009ce752ac8 by task systemd-logind/1280
>=20
>  CPU: 21 PID: 1280 Comm: systemd-logind Not tainted 5.17.0-rc5-next-20220=
223-dirty #242
>  Hardware name: MiTAC RAPTOR EV-883832-X3-0001/RAPTOR, BIOS 1.6 06/28/202=
0
>  Call trace:
>   dump_backtrace
>   show_stack
>   dump_stack_lvl
>   print_address_description.constprop.0
>   kasan_report
>   __asan_report_load8_noabort
>   move_vma.isra.0
>   move_vma at /usr/src/linux-next/mm/mremap.c:714
>   __do_sys_mremap
>   __arm64_sys_mremap
>   invoke_syscall
>   el0_svc_common.constprop.0
>   do_el0_svc
>   el0_svc
>   el0t_64_sync_handler
>   el0t_64_sync
>=20
>  Allocated by task 1280:
>   kasan_save_stack
>   __kasan_slab_alloc
>   slab_post_alloc_hook
>   kmem_cache_alloc
>   vm_area_alloc
>   vm_area_alloc at /usr/src/linux-next/kernel/fork.c:455
>   mmap_region
>   mmap_region at /usr/src/linux-next/mm/mmap.c:2585
>   do_mmap
>   vm_mmap_pgoff
>   ksys_mmap_pgoff
>   __arm64_sys_mmap
>   invoke_syscall
>   el0_svc_common.constprop.0
>   do_el0_svc
>   el0_svc
>   el0t_64_sync_handler
>   el0t_64_sync
>=20
>  Freed by task 1280:
>   kasan_save_stack
>   kasan_set_track
>   kasan_set_free_info
>   __kasan_slab_free
>   kmem_cache_free
>   vm_area_free
>   remove_vma
>   remove_vma at /usr/src/linux-next/mm/mmap.c:187
>   do_mas_align_munmap.isra.0
>   remove_mt at /usr/src/linux-next/mm/mmap.c:2176
>   (inlined by) do_mas_align_munmap at /usr/src/linux-next/mm/mmap.c:2437
>   do_mas_munmap
>   do_mas_munmap at /usr/src/linux-next/mm/mmap.c:2483
>   do_munmap
>   move_vma.isra.0
>   __do_sys_mremap
>   __arm64_sys_mremap
>   invoke_syscall
>   el0_svc_common.constprop.0
>   do_el0_svc
>   el0_svc
>   el0t_64_sync_handler
>   el0t_64_sync
>=20
>  The buggy address belongs to the object at ffff0009ce752aa8
>   which belongs to the cache vm_area_struct of size 144
>  The buggy address is located 32 bytes inside of
>   144-byte region [ffff0009ce752aa8, ffff0009ce752b38)
>  The buggy address belongs to the page:
>  page:fffffc002739d400 refcount:1 mapcount:0 mapping:0000000000000000 ind=
ex:0x0 pfn:0xa4e750
>  head:fffffc002739d400 order:2 compound_mapcount:0 compound_pincount:0
>  memcg:ffff0009ce456e01
>  flags: 0xbfffc0000010200(slab|head|node=3D0|zone=3D2|lastcpupid=3D0xffff=
)
>  raw: 0bfffc0000010200 fffffc002739f108 fffffc00273a3b08 ffff000800f53380
>  raw: 0000000000000000 0000000000210021 00000001ffffffff ffff0009ce456e01
>  page dumped because: kasan: bad access detected
>=20
>  Memory state around the buggy address:
>   ffff0009ce752980: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>   ffff0009ce752a00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>  >ffff0009ce752a80: fc fc fc fc fc fa fb fb fb fb fb fb fb fb fb fb
>                                                ^
>   ffff0009ce752b00: fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc fc
>   ffff0009ce752b80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc

Thank you for the report.  I will try to reproduce it with a kvm here.

Cheers,
Liam