From patchwork Sun Oct 6 14:31:07 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lorenzo Stoakes X-Patchwork-Id: 13823769 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5FA50CFB424 for ; Sun, 6 Oct 2024 14:31:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DB75B6B0249; Sun, 6 Oct 2024 10:31:36 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D15446B024A; Sun, 6 Oct 2024 10:31:36 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A2D5D6B024B; Sun, 6 Oct 2024 10:31:36 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 766C36B0249 for ; Sun, 6 Oct 2024 10:31:36 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 2FE27121326 for ; Sun, 6 Oct 2024 14:31:36 +0000 (UTC) X-FDA: 82643415792.24.B9D4B73 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf13.hostedemail.com (Postfix) with ESMTP id BF02820013 for ; Sun, 6 Oct 2024 14:31:32 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=VYsZQh7+; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=b736EQUb; spf=pass (imf13.hostedemail.com: domain of lorenzo.stoakes@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=lorenzo.stoakes@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com; arc=pass ("microsoft.com:s=arcselector10001:i=1") ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1728225025; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=7kVSLPU3S+DvH+QejgupjPx/n3kvGzT6vMAa/M7tGu4=; b=GjA3On0topshIoZ/zFcuYybGfg9QoVQV9RGvje4aZx0lT5nxV02P90zF4ClPgsvzBHR6JJ J0cHHYcxdKerF66QJNP6aGmz+gJEQK+AAEKdYc8ZtAM+B6KjxgI7xdIJNVtJJDeIBe1m7y O4z/ljbe3SAD9h0DGL7F52Mp7JVKv6I= ARC-Authentication-Results: i=2; imf13.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=VYsZQh7+; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=b736EQUb; spf=pass (imf13.hostedemail.com: domain of lorenzo.stoakes@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=lorenzo.stoakes@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com; arc=pass ("microsoft.com:s=arcselector10001:i=1") ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1728225025; a=rsa-sha256; cv=pass; b=K1EhHmA07xwms1ZF9vaOfyNPqxD1i1VED0mLUTUTIWlD0r/3FmmpTCNJ78WxHIdoAIQRCb ffKok9Z7VQlASAM2hj03T9/EMzQVmY7Uzufr7Yn8sEofx7+Pqiz5wWd+tdKbygda4pysEv q9BUBSkr3l+e4qGX3FyBhpnamYaWPis= Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 496EC68n018991; Sun, 6 Oct 2024 14:31:24 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to; s= corp-2023-11-20; bh=7kVSLPU3S+DvH+QejgupjPx/n3kvGzT6vMAa/M7tGu4=; b= VYsZQh7+OcoWmRSewPaNYSy/40AI9lRxXhD3y2M8N0SZ4o/P+hE7ypebthQXj0xx YIHERoDjCynqtubQYs+TCnqGq4jBQSQi3LMLFxMnFG03+A8c5KSgG1b8Jf8e7yt8 M2T+Bm1XSr23MtfePDH9e0FblZpiVlmk4/s56RWsxTGOjamvbaHo3PwziKIqiljz 058L4o2pH57Edl62Msb35w3c8PlMofnC1UycjI+O47Qf0jz6ivO+oLbnV7jNPnkq AeEF2XwcV/b1yPwryaP9qRN6aScSOl1W8nlm53eWWnBjZxagKYAKEwqZpkr8dJ7C 4jvvwMHipfGexqQhhqfeFQ== Received: from phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta02.appoci.oracle.com [147.154.114.232]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42302p9966-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 06 Oct 2024 14:31:23 +0000 (GMT) Received: from pps.filterd (phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 496969MP001235; Sun, 6 Oct 2024 14:31:23 GMT Received: from nam11-dm6-obe.outbound.protection.outlook.com (mail-dm6nam11lp2171.outbound.protection.outlook.com [104.47.57.171]) by phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 422uw4xfwk-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 06 Oct 2024 14:31:23 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=ot4Jsa5CTJ/u+FarVnas1Gwe21a8CdwAUV/qQN4/vesKNHtUSkeLsz8hEj5ksMRzk2NsuNlrnIRnETVb2+0rvvjQUwTSJbyqd8Q94YWOOYFBdhExc0D8Y7qfvfCWwN+b6hRbVeQ4jkMP2HNZ9BQKmyvf3Bk+7GeIQFJO64XmanvtDfjtK9otysm49aSiiEy5Hx1/GIXX4CnZTekmrfOEHxCIJrLnlc8v9dVKTuUgFjyYX/9qwk2heboW07U3m6qkAJmk4yBg2OuivK3qbiNCLK8xz6yT7H+zJpr5NzRobyaVoaTwdgTtVouFEs1Q92zP/KW2QyOT3QI+CaoEL/RVBA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=7kVSLPU3S+DvH+QejgupjPx/n3kvGzT6vMAa/M7tGu4=; b=BZcTs5Qhucy7UT0F1RsXlIHcOX3bQFS+265bz72tXsm+sGStzbG7b4x/lEHWv6Y/51G9gP3Z80qLpHX5/WsxWZE8DljEVv9WsJOLsfh7Yod6uyo0VFcPqS3WKhGpoP8eyK63CUantZ1OzOOsiio+VYWQ81myEc5eEwvsLmQBlp0bx9jfF6/M/D2Y1BV9L56ehDsBQlsZ5lI9ng91lPy4vb/rr0qLfzafDZ+YrGfHzxAfYYCd7MHmj/Zt2B/eDP7XS2iZDlbhfi5NdkAjIF4PbQBApa8sY23yd9F2cmQtdCgv8WM51I/zIpwpOT51T3JWRWzSs4qVsx5fCnQjvsYZTg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=7kVSLPU3S+DvH+QejgupjPx/n3kvGzT6vMAa/M7tGu4=; b=b736EQUb05dY9AUNGxsgDM1VGVo/CJgA2HfpzCvqYP7/4ZW6bTIO1+LhgQ/A5HiytEeGLa+VDnLWuoIAYr8byoPGn02giNGwdoQT7lc/8+Cc4ZI9+gmdERVR4r+yfMxVA4uXxIxBJ3w9qBG/Z4agZRxbFJo99/jWePWxklFqC5A= Received: from SJ0PR10MB5613.namprd10.prod.outlook.com (2603:10b6:a03:3d0::5) by PH8PR10MB6503.namprd10.prod.outlook.com (2603:10b6:510:229::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8026.21; Sun, 6 Oct 2024 14:31:20 +0000 Received: from SJ0PR10MB5613.namprd10.prod.outlook.com ([fe80::4239:cf6f:9caa:940e]) by SJ0PR10MB5613.namprd10.prod.outlook.com ([fe80::4239:cf6f:9caa:940e%5]) with mapi id 15.20.8026.019; Sun, 6 Oct 2024 14:31:20 +0000 From: Lorenzo Stoakes To: Andrew Morton , "Liam R . Howlett" Cc: Matthew Wilcox , Vlastimil Babka , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Sidhartha Kumar , Bert Karwatzki , Mikhail Gavrilov , maple-tree@lists.infradead.org Subject: [PATCH v2 hotfix 6.12 1/2] maple_tree: correct tree corruption on spanning store Date: Sun, 6 Oct 2024 15:31:07 +0100 Message-ID: <964860c315780cf3a5b8929a34b68d8208333c16.1728223996.git.lorenzo.stoakes@oracle.com> X-Mailer: git-send-email 2.46.2 In-Reply-To: References: X-ClientProxiedBy: LO2P265CA0146.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:9::14) To SJ0PR10MB5613.namprd10.prod.outlook.com (2603:10b6:a03:3d0::5) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SJ0PR10MB5613:EE_|PH8PR10MB6503:EE_ X-MS-Office365-Filtering-Correlation-Id: 1388fe6d-c0d4-4d0a-3448-08dce6138bb1 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|376014|1800799024|366016; X-Microsoft-Antispam-Message-Info: U2PrAMTGBweTijD0Xytp+lOcX8TEMeFZXmorL9YXbeM9gIzR1NFSnE6t1SHz2y4a88T/0dYSwhKTmsF3gO166uHytodA0hg44bLoOkHVoJFHqTI2T7Zyxmzz/nBmtncD/n1RwRt+4aQqJ+rExG7YtUPaE4Xv5pDI+RBXS2y0+AXzl4iNRN3+9TUM5oGTlf6B/0eGS67yu+5EscvTmf9p8+7zNcWcV3uWqPlHL5B0X5WGtsQEODYjqA97LrxHZIyHvke2TLYDld/rNntQ4Ic7hyQL5Vek+4NKedraCl6p5rQAes4CF835SUCoAGH95Hr7PqUVQ6kNXNaO1HIhpHJgUvxtgGU1eSlb2d7BYpXmN+HD4I8YKNCHhM3cZQRbJn+0X2VtEIewcIncQUcr/vqlxt0DNEKaRu/euAbVm13YO9g84ITOku0cXeMH6ygqEPXdlS0Gjn+yxOYO40OG+lnNA+/Gb8C/H6J1zSQ336ZLI65eUAAzMkhMU81yV43gyI221QiPrN9m2EU68mOir7tqrGiCK8w+qxXEpyRKZqCuPkBGC0v52uHT9ScrSmcsjWFqk/efnkPCohtJUpf2fV8fwti+BIZYUZTNrXltmeKWLWUfgfuaxkERwcajSCIEo53WUupUTcAhMo20V8Ts7Ua7sl2Jqeh6SdUr02F80d5VJi1PEazuEMeec1p2bvIDV0YQ0KimJAPamDpU6FUJbg6Dsrkm2vLYId6y1H+CiNGwWIyfKo8tSxlDdhyGvEfP0CzAcncTLqQel440fGx6NWyZGjPIkXaUyJIvVJfy8CDZElBro9zYEvyHPLV7JIpH/KkW2kfsOdGZjOfBPwMMjoa1Ta6BGg82W29BmrXxhglWqbc+ES2kCyuQkmlKJ9tS6sQxHZn7Ko2aKPGxxSfHBpoX0xYneQ0ejNQ/3DCTPyFXU6iD5dpvB8kqA+oayeGUlQQAkOFft28INM81nxZvrGKf5Y180mwrNNW9/N5V+TUnwf5c7b/95D8jElhf1vu0H+DexxcWLrGlos33N6T8P+xeO7kiIacLNkWFjireaFa3p3vG1tIRIOqRSvF4AyJ0RCEHbr9zd0y3NAL/JOvr4NQr2JxtPubY8h+uLLE+lSrHRkhEoP40zdQdWGOPrAyFh1Q/4/JPNVz9V+nXstAj6BkDG+GUQdsjxPMEm0LN95MsNmfvpumSAv4sWEECxsvjmrhYJEa3R/BJdE6MG9sQEQjTDX66Nw0Elc/vgJoOFcmTmrI= X-Forefront-Antispam-Report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SJ0PR10MB5613.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230040)(376014)(1800799024)(366016);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: LxDhpKjd8nIoNQrnMr49BqoAEWLvHfQlRb9quHUro866xQHaOIwnCcBWDPYwvftfOx74neZyh2ZjZagjVp+wGO13F3Z/isgrLBxglyiiQjik/PJGT1YgQ+xfFyOqt6fS/WAT6gB+wMI6rgO3o4iFGyo22gNgk0vEfMq467+83KiHsoJuxHvqz3GaTao1LhJYaaGyU/mKokI7UH/jKK+8mIMRxiO8vzesGPL3TFO1YxcuqEW+fp2oEr8cU9BjSjOXATFOgp0bH0l6XsaZMDqdZWtstMlZiGuWijxTJ0dx9nUdzMZt3k83zHIvyPfOGqFOE3hmG50Id/IvPvYi3DeOlkCdQj9r/8yex/RYJ6MKRbx07hcDEOVcSOLqUIymWueDFLlDVzgeziHs+f+YzCRqZ1wOE4c7VACqlQB2tXL/NNPoc6liEdhKANqCma0Es85q7kCj4NqgIk67drCGEq5X8ixqCp3gmBtZoAIfXT1dmpEC85Npt3KeQf4sBFwCSTflcxcxid8K/C8oA+dnJeM+o7lG0NhcJdzpJUgeXHPp01QM4qw5vGuvkFftRHHd68wYKPUaH7c0Xj+eq1lBjpz+LOa/eGkKuUaYLmC8TiDDFJkOzzMMoJ4441A5BUtPD//b9WNLhMcYvu9C29S5VVywzkMFUqd9Tb7Jh5oUX1DvBRZUPKRJczfH6FcYrFA1gG74idXY/qDzbgq1JuQ8oAbHXX+VVK+Q5x7UDnrkyySqM4u8i9eTx3q2NJHyDlxsBr5SeytdG0XJMMtarVlTIT85Zl2TZjNAHeOpoiGGYZoOjJ38V3/ygOEbwbv0fIpjYkO7PdaiOqYCIgA/gSEK3godIj29uK+gHEd9veA/84sJMagOI1X7D7693mURP6qxRrvcQhHayn4GLt8HnIuS2bSN0GXbZROk/0t+a0cW4XxMwdM2qEo0XkHhUhf2K2szE46zIlAwe8j5ctSNYx4WW32ELEoucxb4hpl2dNIGHTreoxq0bI7OcV3YS8lYXaAXXXzF6u4HV/iFbiX/i6G5XmS2lX/5uOR5Wb03bywL+xWlXyrQNZ70mMuyYc3K9FT7BnUBo4906JLJwPkp7GjL9jxD1GAFCTCoUv4GkvJeRVgq7thpowSxvvTuFUxMWDVg5fwpmAjoMv7Jo7dEEwP7Xy+fTgG63Jvw+clvSJ1kgLuCdLLg6G29D1xUxmZc0IXxBte26+TPoTQMTaveTrHTGOOiaLm3ewAN6AIvKlpwEY3Zsuu8PKks6nfmneUxOsB9NILYrOrU2WY8xlLTlUS8z5FO0LgteFD2kvcIWyE59TyrDTCt438aIYcE5vRpm8WDYR9RxGHu4lKqBbdFBtroU3JTm1v96IjQtBljVILoSQ13HJuVvfuk02erFQSmh2DIEKpaTJHjHlT61AfaB3zqsORpdVK7CszR1qzrEwcOZMkj9dIzzQx8j15fkvoha0a6MYCwz3xhm/oULkEuk/wUg95qCFpwClH+GZxZ9dNZ/EQPo+H/pePMwtS7wOYPCRJPMlNvugJxP1pnxLhvs7JA7JC7cRq1i6Bkc5RwZ7ZQHCiPmANcEhnn6sy2f4WWnLTpENeNQxt+NpYetvkw3jsHPuJhDA== X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: BzQs9ogl+NSNiGU+aprM/IQ1IMxkLqRsn8dYOPwkdwHJCdrJ47toEuxKFNNY0zmLqvyAEf8SfQ7NEOHno2/QMXqDG5B/mWqlfn0LWWRRwrkGAvJhlzIMqjUfCDqeW322+Es9amDVjFvi2uGbxjR0clvcs+57eV9LLBseNet9IymwIJ1qv2dZJv/Wn/wkbv7ZeCOw+A0aCAbTJh5FkdbUf600fi2BJkp9m6CxDZcIVDcXLcmNgZkE9j2FWzl43GfECfkjW5BEOVZ5ZUMQQx2yfF8sr11pggeFhALzHnp86c6XNaItuQNPu9b9/Fkb5VkoAOWupwHBAMIVwRgMPWfShAaGOq/kODnYtYQH6Yc1CGucZSM2t6+ly3nw1hnwyQMj2xjcB4cYlLdGpj9U5H/YDrKWDH5NJHPdDUUFKkRc21MUWvYF9zKqy+vWqfNk+EkmvRUN+FzQ80CfaBlLVS4RVDSgA0QxsN1aQ3xfNSytpItPhiaB292/PyqMY1c3EyajbzCPvONZIaQYf+EnVMaqB+ijoiNBVL9pv693cFOgX9pf2frMi0WNCbB71rYemVyv9np+A+gm3URCriLFbTLu+6uj8uE8hRigByOTqxKoehY= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: 1388fe6d-c0d4-4d0a-3448-08dce6138bb1 X-MS-Exchange-CrossTenant-AuthSource: SJ0PR10MB5613.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Oct 2024 14:31:20.3439 (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: DOPTd/3YBkdaJ7AZCgzKF+S6VAoudrNTv/9wN7DXBjKA/mAzMYxjO99busoZdgxV2k5vI2gpyGVTnm2FMJWkJtCRFDGP1dcMQhqsTWqkCEI= X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH8PR10MB6503 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1051,Hydra:6.0.680,FMLib:17.12.62.30 definitions=2024-10-06_11,2024-10-04_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 malwarescore=0 mlxlogscore=999 mlxscore=0 suspectscore=0 adultscore=0 phishscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2410060105 X-Proofpoint-ORIG-GUID: -5Ui-MUO9r24yUa2Z12x08gL2BhBZztk X-Proofpoint-GUID: -5Ui-MUO9r24yUa2Z12x08gL2BhBZztk X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: BF02820013 X-Stat-Signature: iaw8wf941of34tocuu9n7byesc4psx48 X-HE-Tag: 1728225092-110400 X-HE-Meta: U2FsdGVkX19VtCvJvsp+Wt1EAm1zfFO5W+zaNFfVUJW3cY+pOWHdd/glDJeN+JusLcbP2H1HpPxfgUufi0l6zebRfCxdSbXPkbpNTWlSbM66VcHDmJl38tssB8vSqIYCPNQcGiLoFjiyTC1/w4ew6UBqF5TGyGVs73/hGtzcg4hyLlEHDwfx+LAPun45p1AULMIzQznHCCQnEYbCgeGVGfUDjWUIJB0atqkFNy1tbHZSPWZ05+tdPVkmggPjVKTcxptpuGJGNRzDpclXax8bNmX7O9l5R9gj2qNgJ/qQUWec1UqXgr/nS0TiSFSNy+O6cOTkDZmAa26NR5ISo1+nGY2ca+HYChCsSosXa13LtXf6ZYYa6i6Z0V03jspT+zR5CoZAGqUmn+s4awvdhQF/Cz5HhDzJboXRnLid6cT1jQ67P4lnWTUM/XBJPXy8Wflx1LWlDeuTypxljSTQZbUTsVp3VNOYPvD6it0fu8n7PmaJ+RXsQqIKkl5Zhzqtm3VRfASwbVjesx88e1rRWc+nsvnTPhGuee6TDiHstyVeov5WwpmIYAL0b78v8vNbcbw4xCWEOeF0QJ8T14gPlBJJSE2qz2Ft5AEu0y0ujkF4vTWXdM15hdugsvMSuGrDFSm0nrFTgb2K1PvBVSlD87+xYTlaXWOYnXhF/5bqTSCaOID+x/JB4Cmr4pkt7VX3AC6B0LSMyT5/fCTXFFD9w9dv0jIRfDeveEYMJw5ASBoBV0xvK5Ci9+348yJhhfmoePJFX+MDBNcg3dxrnzRUsH3DO7ysDD0nqyCQcMEmW2/92+WvJ2Gcvm4H8SqzOpa6WFHsYk7Zgs2Ky3qTJ1ic+OvOJD6bvXqnJGCzPE9gLswr62st71kVg8pCUgjnsstB3uqS06fOp9OBYo6V2hlc1FQ9NIpyVe2g2nHmj7qP3W/p485z9+y9SF0qeIq6/qlSlUIxobOMZa4WCabfqoydgSm r64MoQMM HklNisFyZKnZcWrukDMAgGlTyznhVhz8HrutV6OnDS8/3SistNCXFH9dWJXSWXQSNaeDJzc523oc+7kbyh3UGNB4wMq9HQPCzyOYxeQsf0w1Gq4LfW14THKzQdj0pur/Jy9rTSGPqcj0HKY12f8TR1ja2TRgNrwNXL4Xp5JCpDNLG8hmdrmHLpipMhKl4bNiskFn2floExORPcOMQlO/H2EpesX7JEg2mx05l+FMd0J/PgKYXpfXZp8dy7yuBuirsY1GdgAyzTrxObJzzyD7JPtDswf6xgw2NqKgHHkoOOGND2qz41DLbCnz+dO9qdZDSAS9ah4dZZNDA4MfAMAdXGYshnzCPfRcDETjKu4JapAaCxxZ+lRhRHqPxa8jg2a7ZpV6PNOs6Qdm9qIAjsStBrDIlLfsfyj5lwkCr9/Rgqy/LAwf0I0UvxNOwBAxurrcDVgJY3EsEpSTnBSPMtIXoJCDLIWq42qym9pKwbcofQbdqSMFMnnHTNezBHdV7fFWVKGPIbIea1d9MROgxOGwBV/8i+aY0QASM433S9yXHlnwf4SfSr5Za3c+g/c4VJLnU43B/Rlq4pWCFvclsFOhzTv4YuFW2aaFH/hI2nwBQCvH9I1Ek9My7ZnI3o3ectvx7g74WF7C5RusEafz4LjwSoQv5IZ5fwCRCfVUcWIJE6oOQMWU= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: There has been a subtle bug present in the maple tree implementation from its inception. This arises from how stores are performed - when a store occurs, it will overwrite overlapping ranges and adjust the tree as necessary to accommodate this. A range may always ultimately span two leaf nodes. In this instance we walk the two leaf nodes, determine which elements are not overwritten to the left and to the right of the start and end of the ranges respectively and then rebalance the tree to contain these entries and the newly inserted one. This kind of store is dubbed a 'spanning store' and is implemented by mas_wr_spanning_store(). In order to reach this stage, mas_store_gfp() invokes mas_wr_preallocate(), mas_wr_store_type() and mas_wr_walk() in turn to walk the tree and update the object (mas) to traverse to the location where the write should be performed, determining its store type. When a spanning store is required, this function returns false stopping at the parent node which contains the target range, and mas_wr_store_type() marks the mas->store_type as wr_spanning_store to denote this fact. When we go to perform the store in mas_wr_spanning_store(), we first determine the elements AFTER the END of the range we wish to store (that is, to the right of the entry to be inserted) - we do this by walking to the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we have just determined contains the range over which we intend to write. We then turn our attention to the entries to the left of the entry we are inserting, whose state is represented by l_mas, and copy these into a 'big node', which is a special node which contains enough slots to contain two leaf node's worth of data. We then copy the entry we wish to store immediately after this - the copy and the insertion of the new entry is performed by mas_store_b_node(). After this we copy the elements to the right of the end of the range which we are inserting, if we have not exceeded the length of the node (i.e. r_mas.offset <= r_mas.end). Herein lies the bug - under very specific circumstances, this logic can break and corrupt the maple tree. Consider the following tree: Height 0 Root Node / \ pivot = 0xffff / \ pivot = ULONG_MAX / \ 1 A [-----] ... / \ pivot = 0x4fff / \ pivot = 0xffff / \ 2 (LEAVES) B [-----] [-----] C ^--- Last pivot 0xffff. Now imagine we wish to store an entry in the range [0x4000, 0xffff] (note that all ranges expressed in maple tree code are inclusive): 1. mas_store_gfp() descends the tree, finds node A at <=0xffff, then determines that this is a spanning store across nodes B and C. The mas state is set such that the current node from which we traverse further is node A. 2. In mas_wr_spanning_store() we try to find elements to the right of pivot 0xffff by searching for an index of 0x10000: - mas_wr_walk_index() invokes mas_wr_walk_descend() and mas_wr_node_walk() in turn. - mas_wr_node_walk() loops over entries in node A until EITHER it finds an entry whose pivot equals or exceeds 0x10000 OR it reaches the final entry. - Since no entry has a pivot equal to or exceeding 0x10000, pivot 0xffff is selected, leading to node C. - mas_wr_walk_traverse() resets the mas state to traverse node C. We loop around and invoke mas_wr_walk_descend() and mas_wr_node_walk() in turn once again. - Again, we reach the last entry in node C, which has a pivot of 0xffff. 3. We then copy the elements to the left of 0x4000 in node B to the big node via mas_store_b_node(), and insert the new [0x4000, 0xffff] entry too. 4. We determine whether we have any entries to copy from the right of the end of the range via - and with r_mas set up at the entry at pivot 0xffff, r_mas.offset <= r_mas.end, and then we DUPLICATE the entry at pivot 0xffff. 5. BUG! The maple tree is corrupted with a duplicate entry. This requires a very specific set of circumstances - we must be spanning the last element in a leaf node, which is the last element in the parent node. spanning store across two leaf nodes with a range that ends at that shared pivot. A potential solution to this problem would simply be to reset the walk each time we traverse r_mas, however given the rarity of this situation it seems that would be rather inefficient. Instead, this patch detects if the right hand node is populated, i.e. has anything we need to copy. We can do this easily in mas_wr_walk_index() by detecting if the pivot is either 0 (shorthand for the end of the range) or the required index is less than or equal to the last encountered pivot. This change is made in mas_wr_walk_index() which is only used by the spanning store so it has minimal impact. The work performed in commit f8d112a4e657 ("mm/mmap: avoid zeroing vma tree in mmap_region()") seems to have made the probability of this event much more likely, which is the point at which reports started to be submitted concerning this bug. The motivation for this change arose from Bert Karwatzki's report of encountering mm instability after the release of kernel v6.12-rc1 which, after the use of CONFIG_DEBUG_VM_MAPLE_TREE and similar configuration options, was identified as maple tree corruption. After Bert very generously provided his time and ability to reproduce this event consistently, I was able to finally identify that the issue discussed in this commit message was occurring for him. Reported-and-tested-by: Bert Karwatzki Closes: https://lore.kernel.org/all/20241001023402.3374-1-spasswolf@web.de/ Reported-by: Mikhail Gavrilov Closes: https://lore.kernel.org/all/CABXGCsOPwuoNOqSMmAvWO2Fz4TEmPnjFj-b7iF+XFRu1h7-+Dg@mail.gmail.com/ Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Lorenzo Stoakes Acked-by: Vlastimil Babka --- lib/maple_tree.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-) -- 2.46.2 diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 20990ecba2dd..f72e1a5a4dfa 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2196,6 +2196,8 @@ static inline void mas_node_or_none(struct ma_state *mas, /* * mas_wr_node_walk() - Find the correct offset for the index in the @mas. + * If @mas->index cannot be found within the containing + * node, we traverse to the last entry in the node. * @wr_mas: The maple write state * * Uses mas_slot_locked() and does not need to worry about dead nodes. @@ -3532,6 +3534,12 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) return true; } +/* + * Traverse the maple tree until the offset of mas->index is reached. + * + * Return: Is this node actually populated with entries possessing pivots equal + * to or greater than mas->index? + */ static bool mas_wr_walk_index(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; @@ -3540,8 +3548,11 @@ static bool mas_wr_walk_index(struct ma_wr_state *wr_mas) mas_wr_walk_descend(wr_mas); wr_mas->content = mas_slot_locked(mas, wr_mas->slots, mas->offset); - if (ma_is_leaf(wr_mas->type)) - return true; + if (ma_is_leaf(wr_mas->type)) { + unsigned long pivot = wr_mas->pivots[mas->offset]; + + return pivot == 0 || mas->index <= pivot; + } mas_wr_walk_traverse(wr_mas); } @@ -3701,6 +3712,7 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas) struct maple_big_node b_node; struct ma_state *mas; unsigned char height; + bool r_populated; /* Left and Right side of spanning store */ MA_STATE(l_mas, NULL, 0, 0); @@ -3742,7 +3754,7 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas) r_mas.last++; r_mas.index = r_mas.last; - mas_wr_walk_index(&r_wr_mas); + r_populated = mas_wr_walk_index(&r_wr_mas); r_mas.last = r_mas.index = mas->last; /* Set up left side. */ @@ -3766,7 +3778,7 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas) /* Copy l_mas and store the value in b_node. */ mas_store_b_node(&l_wr_mas, &b_node, l_mas.end); /* Copy r_mas into b_node. */ - if (r_mas.offset <= r_mas.end) + if (r_populated && r_mas.offset <= r_mas.end) mas_mab_cp(&r_mas, r_mas.offset, r_mas.end, &b_node, b_node.b_end + 1); else From patchwork Sun Oct 6 14:31:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lorenzo Stoakes X-Patchwork-Id: 13823768 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6B274CFB424 for ; Sun, 6 Oct 2024 14:31:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3ECE06B0276; Sun, 6 Oct 2024 10:31:35 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3763E6B0278; Sun, 6 Oct 2024 10:31:35 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EC1316B0276; Sun, 6 Oct 2024 10:31:34 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id C16646B0278 for ; Sun, 6 Oct 2024 10:31:34 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 6376A80589 for ; Sun, 6 Oct 2024 14:31:34 +0000 (UTC) X-FDA: 82643415708.23.D36D529 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf20.hostedemail.com (Postfix) with ESMTP id C817C1C0015 for ; Sun, 6 Oct 2024 14:31:30 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=fmLUYvAj; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=iVJ6OCAP; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf20.hostedemail.com: domain of lorenzo.stoakes@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=lorenzo.stoakes@oracle.com; arc=pass ("microsoft.com:s=arcselector10001:i=1") ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1728225049; a=rsa-sha256; cv=pass; b=K7SZ2BIKioMi5XZJ2SxVzM+HPWtqIZfUlIDt8+4tuumLTPf0LJXIlrBXxjdmr3DjB35CLJ w7dRl7jgP1V4ps+m8krheXzKOc4TZUCng2HWtJKnZLL24YiUQuIbAVQFkwyDL+4JpATn6Y V57kPfMkDzIs7DXvAWJNKik06/ZiXsg= ARC-Authentication-Results: i=2; imf20.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=fmLUYvAj; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=iVJ6OCAP; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf20.hostedemail.com: domain of lorenzo.stoakes@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=lorenzo.stoakes@oracle.com; arc=pass ("microsoft.com:s=arcselector10001:i=1") ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1728225049; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=sk/AdneOvcPd+6OW0+cMIAMxl2oHVeqmx8xLwcLve40=; b=3zfIXMPElDernioIRrxsYtCyVq+Htfpd1B4iD9qNt1ZJi+32mVbPnShn5+Z0MV2WG9ReXv DpB4sV9Mw10wxpQfxsHnwGwhtRlJ23ylSWLSffAtIf9XnMNLAOQ7rdARveN8H6fhjRTcqx c93OBTCztJhz9f7jR1Gx5nftHrym8C0= Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 4966XX8B004608; Sun, 6 Oct 2024 14:31:26 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to; s= corp-2023-11-20; bh=sk/AdneOvcPd+6OW0+cMIAMxl2oHVeqmx8xLwcLve40=; b= fmLUYvAjxOxLBKzW7tbBiOMQhmcT4UcRbJht2ocYRmewREAAYL0iiianOcohYqhj LcSqSVQU7UtgYb4PW6EhTl6fMsx8U1A9AHNZevPdJHM5q2nmbBx8M0+4JoOGd9+S /lYVYJsPohOC0XV0i4JNGrV2wxnvi2cBTrYeT4JKCZXTWeV0SxCHbzKt1fVdY28h Wp4MmhGDmEkSZ2oL+BSJsYp8dwT17IyWKrbj2a/VrOL3uu/ntKPENHbF3hxlLDT5 mw2L2mcmvHOBiKrClBbvW0CzzJqAHHLeP/AFeXyOBaakVJRPX7YgW5JIQb9Sifml Rkrl7reyEF/xzZhVnWK0EA== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42302p9968-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 06 Oct 2024 14:31:26 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4969Z03Y012028; Sun, 6 Oct 2024 14:31:25 GMT Received: from nam11-co1-obe.outbound.protection.outlook.com (mail-co1nam11lp2173.outbound.protection.outlook.com [104.47.56.173]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 422uw4x515-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 06 Oct 2024 14:31:25 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=fJoe0pQR2HZ9+DNUi1/cqekY6yDicIGXWXGazfKuT+HiBw2TEqpd7OjYyFo2BkebaCJ09LlQirBHCp4QpwqBAExJz8WQSETJsKCzC+o61Qis9Q4guifTF9qkRKsfC4/IA4pL9fCyGOflmH4qlHMVALZ4QjGQD54vXtaV6Uz8J0r3Ubhi83oXN8JD14hQhMDTLV+C54SiWYHuUhIZ3WIsLyzvN3nIft9yGEF30trWwcwh8OXR7rZ+gf5loACYkfm2mD9rFGZWnaRJu6y9BQuCIU5ZBYWTSArm0lfS6v8dH1O27piNht5y7XlP4EvLIpcspbiE3l1ZDZzdX4EU0TVAxA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=sk/AdneOvcPd+6OW0+cMIAMxl2oHVeqmx8xLwcLve40=; b=N1O7OwbsZ0y0Byf7lERSJrB9QKxMaPqF2zKQe6RkrgFJaK9lo8dDjUsvlyAGQtI+B22rzk2fxLfCG8knoGYH4Sd5YPDfsbIAO41sNMmaHlkXasGD19nlY/5cRiUvFNQpQHq7SHlyPbfIXeVydKLJXGSyU/bCEXgXLhV85MpCOk9A8+wuoUPXhgv5QN1mUbfpovp/yPChYkIPRd08SdwY4kmJNhamUo4KVshTMoV/2a6PqSy+Dcys6fl7IbkDIwEGZPmUZpV/uG2uaScrBcOZovxnn7D2/IEKClALiN4fITCC+ks9tKG2LmjlMaRmHwUETPRNKFRxEp/7k60o8m2EZQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=sk/AdneOvcPd+6OW0+cMIAMxl2oHVeqmx8xLwcLve40=; b=iVJ6OCAPsG1vlP4mIv96XDwBo15tCQNFqv+AVp8OF0L2kmCcz3Z9/lDKT87h16sa5eVOO/F80E9voro2h3Vf3fjuHs7NXcSFfazhFa59ddt49+93GCNkO4ulKTfoB/UA3OAzbWmxcowBeprZcCl1B92y0iZjx+jWFuoCdkg785Q= Received: from SJ0PR10MB5613.namprd10.prod.outlook.com (2603:10b6:a03:3d0::5) by PH8PR10MB6503.namprd10.prod.outlook.com (2603:10b6:510:229::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8026.21; Sun, 6 Oct 2024 14:31:23 +0000 Received: from SJ0PR10MB5613.namprd10.prod.outlook.com ([fe80::4239:cf6f:9caa:940e]) by SJ0PR10MB5613.namprd10.prod.outlook.com ([fe80::4239:cf6f:9caa:940e%5]) with mapi id 15.20.8026.019; Sun, 6 Oct 2024 14:31:23 +0000 From: Lorenzo Stoakes To: Andrew Morton , "Liam R . Howlett" Cc: Matthew Wilcox , Vlastimil Babka , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Sidhartha Kumar , Bert Karwatzki , Mikhail Gavrilov , maple-tree@lists.infradead.org Subject: [PATCH v2 hotfix 6.12 2/2] maple_tree: add regression test for spanning store bug Date: Sun, 6 Oct 2024 15:31:08 +0100 Message-ID: <12af588c6b3338bf6a73cd2d95943a83a44c3b42.1728223996.git.lorenzo.stoakes@oracle.com> X-Mailer: git-send-email 2.46.2 In-Reply-To: References: X-ClientProxiedBy: LO2P265CA0147.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:9::15) To SJ0PR10MB5613.namprd10.prod.outlook.com (2603:10b6:a03:3d0::5) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SJ0PR10MB5613:EE_|PH8PR10MB6503:EE_ X-MS-Office365-Filtering-Correlation-Id: 802234f9-2ebd-4e3b-86f9-08dce6138d6a X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|376014|1800799024|366016; X-Microsoft-Antispam-Message-Info: +9e4TBeP+wIfZbn40pWa5YTy3YHHZjnbo1BbpiuRIlMciG22kLrPcEXpxhMQY4gaucfwCoy+J1rKi1z2N7D74LaF+kHk9dhdyF3EuhHz4PFKzGtmFidw/S/1zDnFgg6qHSeUZ1iSF4I71FRW9EHU1+IQwZ/QH++As2gQ3EDf2degy81U5RhGZM4fOn0TCLHnJIPNvR35Lqb1C64XmR1GBjawDUCQGBvwsLd59jkvJTHwgiERLEeJOmar+Klj1lN70HUEwNlUtymfOwHghkqP7EifW+oqlna80CDCwnldc21xP1ui4w+wwNO7G74mrM/Ghk0P3bScenIW+UgmAAJEIMcXZXpKwpfvY/tvrhgzEJBCyqRrRPq+GPbriG4QGd7MEbwNTWg6Fsvv6Qtph/ZRbGACx42hLlib3lGLnJv+0Kutrc+SsyPAo42gAIRk/tIo/rH6wtdFGOqeO5xhKxCYvaL8AxcByoNzof6qbv92nprZEn0msFZ3U7wJJnk8hTwhr10pxBB76UczBUupA4yhE06/Khj20qRLRrZVBZdlKyGkmWvM4ork22Q/8K5u1vfFBq2wPBwuhEPkbhNWCG1U6ov31AhtN0PkpnL8Ec3CzOeT+C43y0Mari5IkGKjtiRZf2DsTSr1zo3Bqq4nvoyGN2f7q/eed8DV1wDjZEFicuZEXpEN0y/Ouda0b+neGkbkKW5K2F9ghWZesybSjfsMeIqOLBsXlM+CF4ipmZEh1fKPwgZnOX6Fl7BwOK0rg5NFIj0XI89iWMztmnuMeYOxRDSn3/lU+4colSPHL3nneqdATiyAr5qkGwwjH5wnB5RmJRk70PyUrk5ucjYTcwSB8r7W1qm0SSpIMXg5VDMXuLuu6NRF2cLf1dqgV1rp9q+X+amUQ+2yOnXLJzRTQkWf3LFD1BpSro/roiBHsqNJfJe88nAh51Zurl01vlZPvj7lzJZiP2XNHczcamL8PBqe52MyqCn47ICclAwUcaHi+tyXOIlq8On1ugo2520b4LlGMklzOJDt+41UwGkgLCWjsHBAxw5x6aIJWRk5/XiKhHeBjIrAE8mj44w2glSoXFTbgM+GG2pC0JVLxOLaSAA2fIgWgrqDg27kA/Ie01AEVY2X/8q4KVDn6eN3+8ngl6n3n3s+ugDqlJt9K/S9xyyEpv9JChv8FvyxLanuTbg5OX7q0gHhN53Zxe0JV5waSeDuB/byKzi3eQhIpawz9PFsmRwB+2hhVIm2xk9rmR+8U0IzCOu+kJ8b3X1FhXEkUPj7iRa/I/swJY+Q2m8nncf8ug== X-Forefront-Antispam-Report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SJ0PR10MB5613.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230040)(376014)(1800799024)(366016);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: zB2PlB7VQdNvflBf3Osty2ladEZQEgR+sW5xV6gIAf/wc1w5i+p5qz/TSjPoZlZUcYBZ+N6+9i5bWVv8xtnBoVIshZtlLu0NlSfKBOwK4wIvjcg5M1LZ7Sb87Mqpi9jGhVEWAHlXlxslVmGUui+SBUz1xBxuODhco0l3Dps10QLhaM2CG2HW+e1Ev0eVyVOuJ7jXo7/t8fjMixh+7NF89ZyQUaGNCrJE8c9IHfn5mr8k/ncn983uWDPk+1ybfbE3H9ZJbLUjFwvLEt+qz1xNPBkugrRLqnkP+vjq83b3JDs3L+fEZNupRTuLWrBB0bbHoC+Tk3KSQUYIml8NQBpW9TFvRvaZAEllNVtyQv9eR2t9r72Ze39V/yUthb4aQtvOCPTtwftP0W8kJRcwMhf+ll7kSim9LxIAnkc+R8j2TGnMBE2CYxCuasZix2zoT8NP6XunNM4Mxo+Mwg4JTBhdIWDxPeG3FEwFOtEBTNWkJ9K5OayU6+WBnQK7/Cks4NDHSlFkGD58GzRUJ64KnNMvuW/hInLUDaXksv6s3iopiVzQtpBohQzRq2BwbH0cOEAQnWCAlL3jXSiPiK02AWHMEoNjG9F4KAZMVIlEwPetP+z37YMHlj5crwC7JjuOAzgYA1anbgfxGOaaZitFMRfpiZYM1ZR5OMDr1J7fwmDG3DvgIBoEjihY7Ejf+qMnJOql+yl2NbfrYqxLcZ0cFsCWJcLEDs44ArRf4ZkRwYc6vKarekgO9iUsyxEAA7UFRxqgLCMckr30swbnYHgpV0nbFW9Jfuwhvgi/G4lZxJujlCMldAkWzyYkvKx8RZibgN0wn8n9EM1ibgclacvXURkMyhc76vPHgx11spAWj3jrl0legb7QUI2rSxC0uVlS4uXSm5qwdBg9orAk+Zz6QMSY8et+IqWWWqmMssklYgVJEro1yLKqPyHG6U6yxH8sj+ra6qa/1BraLDiUjpm1pXrDWhp0opj6M1Qcdvmm+iRk+hsARL8q5EuI533FWK4r3yrnH0SX40mZedQkAkfd1/RHoK967ZrQETgT7Z1rRDbb4Ah7WPZaJYhiBjA+AuLXMlb2JZQEitFDF5h3JFbQAtSodAofCH89f7pttOW8eJHsI0tzjp40Z7OBvfT3X2zwWg+rEtwZqyt+7b2EhBOK25brkzKpg+xajYCa4nxDBDAONUBnUTkSJHRL5uJu1K2lDzTYWbWMiwcMtcQ2cprVH12HQNvWITIh9gaaTBgRycTnomWeIB1vjYNGH+NSget1ltk4GSMEkV+6vxwuB8QDHhzQzM5rX/r43gsZ5dKssGU9VZEaGaHY/b6Y+DOhK/umUKtW5ir5khnOrDL5yHvUcm9Yiygreq2BHRyISzF3mi5Rf202y0BDIZ/wIJQhyivJUVtT7rSFGQiH8XkiIQN0eHRKtCN1aXwMzfxnjdcd+BPy6cp6nYZH/Jj6ijcSadfosrQjBSy1JIPjPAAWJE2IgScEY8NoaksRtziIGVNPU1acBBDDqTIq+/S+YYnwQFk2hA6i45a+uOG/kAgQM4yRBrJtepRj5msnfDHQ0gijR+2JRQvGzxXKq3JADVQPV10L+VhlwIzy4Qu8/HCxvXAVcroiJQ== X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: zEXyT5uOn1aA/R5Zh/+8pshUGaOoKZ+ljbPGd4GAuamlp0EckttCXM31apXi+z1dPMgF1x7fiyE+bAjKSg2LXIo/qR/LQVnVitbc3d3V08rd/s8N6RMaRhECpxTyA3OrWN5vZSV5htdU00YVzdoD36RDHyTLfjH03JJk4MN0uymJhPAE7P04U5/JgVHAKI7UKDF52437KFE6SPIh9atbge7j/ixUTTlaSs5fa/WCcL9iZ/3Rdw1UT8qv6tPabYkBpMl/3TmGHB202YJRwzSvrNUnlprpmaq27U4aeZK35yDy+kKmamG8spzxIV7Zpd/HbDarcQG1FZQEHDP6EkKnZCH/TQX65jtbi4R5aUQYpsbRbA2yskMOXEVjdwLUNNMc7TUNrkZOnkbya0hjXY5nwtpnjRa1mXIyePKel3G5ZVbw9ZRNxuZy7jM7h2I1nQBO08+2vhGmYzIsWaAAnXQqhg7UMihw7LJ3EIOJ0ryy6eG+u4hwpfveT/2YlmBapYClNl/Yzeaa+liw/Hfc2o6rooGsh9kwvnIm5n1Q5ggDdNt/s04niVexc01+yHBa/Ign5Mwco/rtSBWvDNqkkMkWyBdZVYWQFfkYrljk1Dw842k= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: 802234f9-2ebd-4e3b-86f9-08dce6138d6a X-MS-Exchange-CrossTenant-AuthSource: SJ0PR10MB5613.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Oct 2024 14:31:23.1874 (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: lCLYufe0L4EGC3CkQ99Nsnq7CPgXul/LY9X+4nC1iLcXaoQmC9CUvgQdPBnntPrT9MNG96xvjr0QBMEwpo9074Sz+5b0rUl9XudoMfsbqcs= X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH8PR10MB6503 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1051,Hydra:6.0.680,FMLib:17.12.62.30 definitions=2024-10-06_11,2024-10-04_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 adultscore=0 phishscore=0 mlxscore=0 suspectscore=0 bulkscore=0 spamscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2410060105 X-Proofpoint-ORIG-GUID: 7fgNrj8yXV3IuNJGH-JI5wt2RG6ECY1n X-Proofpoint-GUID: 7fgNrj8yXV3IuNJGH-JI5wt2RG6ECY1n X-Rspam-User: X-Rspamd-Queue-Id: C817C1C0015 X-Rspamd-Server: rspam01 X-Stat-Signature: mwwf6dho4px6p4sdpt9aj1p6ucmcum9f X-HE-Tag: 1728225090-75586 X-HE-Meta: U2FsdGVkX18f/kVEZV3e0EeJ1dl3gCWNksdAMsWZ8t3gP7Qhl47d84TToRx36ybIiqTay1JQ/fz5RXyipiS5iVcmONvweN/qMjwAT31Q5LuMErRySGDh6DmcmxkSzcE/TtXhXhEqmd9wkf1yx9iMlWN2cH44UERTTqv7Igkn6XdYG53MDSBxJ1I3R5IOCCsw6C7U4SmHqdm/g0L3+Bo9LTbemRe9Wsmidw9ELYuQb8aPZdm65UZpYW//r+/qgoXGypq6+PGYIPCi1ojbaS0m7Z4IrljfDt1EwtL8q5eJrGVdmdqw+6cZ5PFDEQp0pBIAhhP2ocLfjItWn3LTrjJ4/zeBroiALUwSe+OBxDQ30yb1E11TcDxpv3+0oOn8N0+DgNOZFQdWoGdbc0Ayl46zwqer3nkoghJumGBnGTW9PelzT0LlonhEHi+gD4qDnf93F90opNvyjZ9G87Stm5DK09nNb5EeXd7d0Um/utYkvcc9OtFe0iBO7KENTIK8Ky0et6zrbsXYRD0/5uexz6EvEwa5aBy4ROzvktmmRtDdwsnyltoGJf+g3KtUCVJWzv0uDTvyv9hCO8lSpD4njn8dAM08ETQwg5a4gilQWUvTZFCGc9ue62Tszi8Z1339gREtt/VOju8SyDDCwK56hbAEBnRd9LnoTTMVMf1t2LZLBgbTRkkh6qRNRKf++tvlrKX//qzhToPs5SN4JjCm4/vyEhquuqWAr6coDXw66B79bAibNERoFJS6mk26F7biXbjJ5FkKvXOWvUL7hIKI8Jccbrl1ngYBqYVM2n8ZHX7kbuT2ivXSgRx8sqVL4gGNCUAuhAQ7ahQJ+BoB0t/DIJ67Z/IHEXKF6d1hkLUWBfLkzFhFe5ZtfpiTMmWWXIUs0MlhWNVvouUY65hKV+ezzRPMqk13XntUA2vGFNKg3brHYtF0dd8L9KwOasanlTu1wjthoOnJxWn8VweOITNXlsh 0O7juPpY wnmNFAASQH3xE/Yl5W/FocNxxnxrEXUjYf0gjUndVgv1AxdcdRPNKCzSB9zQyXsObaauhCLgyRqc4LXLKdCFwgI7X4Hh7G8wvWXhEAJaEdvSX5svrqt2SrGPqYVMoU12tKGfryWxCMw7dgzyPQx7lNRQ5kqjNGrw22OhaStXhwa14Vr/V81xd+7rqnEPZQxOQmgx0HFY6pqQlklexaiufJvkR4IlMVsgroBMgO/uk6B8gVzf7Y+gjJXPDZYjCM4fUS+5kr0FHrzyaZJ+dKaJRjMSQrF3ZjqnFSXHh49mA4HXhklTqjEy8vClppn7Js4Fb9EdUdjFXowyEBQzeoirEGr/fQ4rNktO1rogJvXrafQGAd8Tj7C4YIoU5KIntavbjh3CRFzmeJSUK3G+4TnI9JxJqbBOmzftyjdbUux+BknYGBGp5AWp/q+BBt+gsgtk+2bAUMK4Z7Xz66kyGPaYJz+2UD/LTy/0/9U9enRyirzjhszezwqlcP99pVQEtNSEq9swTgXkRllZLChFhF5RaUH89ils3T2i0RJJ5L4rHjKuBL1uLdZaC16x3HpSiuNew05AIFB5I64ZtmtJAfs3dWSYZtpvPxp/mX86uPeUUVyFW7EOcLFqkpKOodpxI71DZjglM X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Add a regression test to assert that, when performing a spanning store which consumes the entirety of the rightmost right leaf node does not result in maple tree corruption when doing so. This achieves this by building a test tree of 3 levels and establishing a store which ultimately results in a spanned store of this nature. Signed-off-by: Lorenzo Stoakes Acked-by: Vlastimil Babka --- tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++ 1 file changed, 84 insertions(+) -- 2.46.2 diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 1873ddbe16cc..5fde09999be4 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36406,9 +36406,93 @@ void farmer_tests(void) check_nomem(&tree); } +static unsigned long get_last_index(struct ma_state *mas) +{ + struct maple_node *node = mas_mn(mas); + enum maple_type mt = mte_node_type(mas->node); + unsigned long *pivots = ma_pivots(node, mt); + unsigned long last_index = mas_data_end(mas); + + BUG_ON(last_index == 0); + + return pivots[last_index - 1] + 1; +} + +/* + * Assert that we handle spanning stores that consume the entirety of the right + * leaf node correctly. + */ +static void test_spanning_store_regression(void) +{ + unsigned long from = 0, to = 0; + DEFINE_MTREE(tree); + MA_STATE(mas, &tree, 0, 0); + + /* + * Build a 3-level tree. We require a parent node below the root node + * and 2 leaf nodes under it, so we can span the entirety of the right + * hand node. + */ + build_full_tree(&tree, 0, 3); + + /* Descend into position at depth 2. */ + mas_reset(&mas); + mas_start(&mas); + mas_descend(&mas); + mas_descend(&mas); + + /* + * We need to establish a tree like the below. + * + * Then we can try a store in [from, to] which results in a spanned + * store across nodes B and C, with the maple state at the time of the + * write being such that only the subtree at A and below is considered. + * + * Height + * 0 Root Node + * / \ + * pivot = to / \ pivot = ULONG_MAX + * / \ + * 1 A [-----] ... + * / \ + * pivot = from / \ pivot = to + * / \ + * 2 (LEAVES) B [-----] [-----] C + * ^--- Last pivot to. + */ + while (true) { + unsigned long tmp = get_last_index(&mas); + + if (mas_next_sibling(&mas)) { + from = tmp; + to = mas.max; + } else { + break; + } + } + + BUG_ON(from == 0 && to == 0); + + /* Perform the store. */ + mas_set_range(&mas, from, to); + mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL); + + /* If the regression occurs, the validation will fail. */ + mt_validate(&tree); + + /* Cleanup. */ + __mt_destroy(&tree); +} + +static void regression_tests(void) +{ + test_spanning_store_regression(); +} + void maple_tree_tests(void) { #if !defined(BENCH) + regression_tests(); farmer_tests(); #endif maple_tree_seed();