From nobody Mon Apr 27 07:48:13 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id AF30EC433EF for ; Wed, 15 Jun 2022 14:20:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1348392AbiFOOUT (ORCPT ); Wed, 15 Jun 2022 10:20:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35368 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1346483AbiFOOT5 (ORCPT ); Wed, 15 Jun 2022 10:19:57 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ECCAC49937 for ; Wed, 15 Jun 2022 07:19:51 -0700 (PDT) Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 25FDvQ1S015201; Wed, 15 Jun 2022 14:19:41 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2021-07-09; bh=gTOa4sCsowVfnMdwtik+r2rl6y+WpU7ND9MuGs2cInU=; b=OwO8JApKapKC6acGaXwDqLR3fnGED+ZobDeMzGxQvqx+jrrUITCKT3qqwkiSkEMAxI7q wOYkxsYzOJ0W/r6nnjJnmzaA8exGsYtJj1E9mxh50uWuOXY+1n+qV4tOFOaAECMWVPZ2 0pPjZ4IfAn59gpP3b216nNdGw6HX0QhFOqqXF4pbtitusRG+if0cyNgYSTG5e3L/zDXG UafYUK6ZACp0HlieOBNGP3Q1IJVGxip7Mu8g5C/B9sA16pVJNqR8M39jc0vu3EaZYr2o Q6BR9jCAo52I3rc0NOXcImJbc4aFUP4cirCnFV4mNurkVY/9ywvjacA7VpJvLaGYsH02 Ew== Received: from phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta02.appoci.oracle.com [147.154.114.232]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3gmhn0gsfw-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jun 2022 14:19:41 +0000 Received: from pps.filterd (phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 25FDtnhf031252; Wed, 15 Jun 2022 14:19:40 GMT Received: from nam02-sn1-obe.outbound.protection.outlook.com (mail-sn1anam02lp2049.outbound.protection.outlook.com [104.47.57.49]) by phxpaimrmta02.imrmtpd1.prodappphxaev1.oraclevcn.com with ESMTP id 3gpr7p2nrp-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jun 2022 14:19:40 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=iAVcxmU5UoP1HFpE8xSFAVXMI4+q4SxUyMjGYGk/SyqIKgWoM5S7Oopq6vrggGsjwsZ4wDxKLIR6xYK8x64zaOz/lVXStZLClgyi4z4UIm/SyQWJJtUTDREaT6mmHQrDxNN4DLMfNkFIQCVbQirGXLTzKIkCu+sEQIYreONvuWYx/ktbAkiEANHTQNTTL72E/qsBMWWlbWaqBHQfM40JsuvD4hCghH1X9xI4qD1udqm3hlS8dDtETEY7bPUW9ISLoIV9YSg4C47BOA27m8u+cJ+OPMCWuiqjqexELPiDXoIZvfynEBxB4vCkTNw7QwJLRpQYOJj3VIuW2TbdqyIy3w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=gTOa4sCsowVfnMdwtik+r2rl6y+WpU7ND9MuGs2cInU=; b=fG100qUb8FKI68ANOFuz7K9igKYwriJ2BJlU0Z/jWuGNxF0l/sSSquIq1jHIGPx36uV5Rcs7EUqKXiUl364fNvdQJ99RCMszw3onrdTQlK9jOKhvK4ttdhOa7mP32NrAgLTmWq8iIHJdWVm5cRUDWG1PtRSmDKxhACzdWSty177mW6lmH4xEFHUcYPbr9bupaaqX7C1Vz77lDU/rTDiMU8q53Xgd5SW5M4xcmXoVUF/uCqxgiDWwuuVwZK0G39l0gNmagInYNa1JHKQeimqTaZpPT+NvrQ0TrPBcPUZPo9VVVNl7jNsFBTygcVA+/ZDKxEDlF+fuivXMQzIvosAKtw== 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=gTOa4sCsowVfnMdwtik+r2rl6y+WpU7ND9MuGs2cInU=; b=cI93iyTsIzV21JBNqVqRMBgjoZKAdUgmZXw9aVAwmCt5/H4+x30S7ZpRbalR+JLYhMb8P23i9kyy54tZvjPZKZbV7RQhW5Dz+oSYfNlxbXJf9w5f5zbW6Uvm3ccUcaIMUyVysQaLLEHyiIuuS0gm9MWG4i5WncWRIlWxe5tGyLU= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by MN2PR10MB3342.namprd10.prod.outlook.com (2603:10b6:208:12b::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5332.15; Wed, 15 Jun 2022 14:19:39 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::e1df:2e42:6674:313e]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::e1df:2e42:6674:313e%7]) with mapi id 15.20.5332.013; Wed, 15 Jun 2022 14:19:39 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , Qian Cai CC: Yu Zhao Subject: [PATCH Fix 1/3] maple_tree: Fix mt_destroy_walk() on full non-leaf non-alloc nodes Thread-Topic: [PATCH Fix 1/3] maple_tree: Fix mt_destroy_walk() on full non-leaf non-alloc nodes Thread-Index: AQHYgMLys5sMlAg0rkKdMdWAEuRIZQ== Date: Wed, 15 Jun 2022 14:19:38 +0000 Message-ID: <20220615141921.417598-2-Liam.Howlett@oracle.com> References: <20220615141921.417598-1-Liam.Howlett@oracle.com> In-Reply-To: <20220615141921.417598-1-Liam.Howlett@oracle.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-mailer: git-send-email 2.35.1 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: dc122f79-b9bf-447e-c071-08da4eda1519 x-ms-traffictypediagnostic: MN2PR10MB3342:EE_ x-microsoft-antispam-prvs: x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: O8yBqy+6DT0/AMzL3EhZF7BS8UaWKcooNaO4E5NrVnFhODI23pHzP3AHN6zllK5sAu6yxuctiEhBfdgq652mzjDtcKwWBUdxBuVKNEu5B/24I5erfCEZADc5CFs+63b6/uFFEOBcVbb80+H1udMsTVx20J9D/RTLD5khKrlWvxE7bzZVK9ayEmdetFLjT+ql0uVdVDsEfv3/LnUa1QtKat+rkn5vTZ2xt6m0/VAurF9XSelFgC5fK7cV+OxnkwAAWSoN1U5e7MQB0b9anq/HZoll5SQEKPTn6F5ihInVbQlDWxy6iRFeRToy56E4zEd4Ag/SONhHqST6z1WhHMYG5zRGGBUCQUJVOzveMuMGnRckneTajhxMbnrpt0GPKDhV2tZhnALgfYURMDnRRhgwg8zv2PTFA2QYKe3ZEScEsHUrBdAJGlS0AdUud9lij3ieLa73LxJNUgy35MUzZ3q30rjAO6DYtiR/p4EymQeG7xg3nZPkFMMcwCiX+h8+xdbrO4aFyh64ZAlxXqXl+/ujRXAAoOUg0KudBR3GJ2dQSy07wry/9wZIA981b4ntv28S93y6DgzPsw88SwtU+48By8paFMUK7tXU/NhfdA8w5mOXJclWWtqtfAT7RX1d9iGO9IhsKMgqI0flFiRl+baDbn+pgUwJvSdfsu/p3dqGrQNM6Zc/EXw2BlrnbuBqEYsAi7iG3SGRPy7U6cAz6zhuqw== x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SN6PR10MB3022.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230016)(366004)(86362001)(316002)(122000001)(110136005)(38100700002)(186003)(5660300002)(4326008)(8936002)(2906002)(71200400001)(38070700005)(66556008)(64756008)(66476007)(8676002)(66446008)(6506007)(76116006)(91956017)(26005)(6512007)(508600001)(83380400001)(6486002)(1076003)(36756003)(44832011)(2616005)(66946007);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?mT24yWl/IIVZDL3daLivHHf70f1REhRlk4R8dYnCG9NKTN9gbBUbUomNjY?= =?iso-8859-1?Q?raHKuDw5fFJ2dHEra6mTcrPGqU8dEN4qD6rQm9OBM9kAsqQD/AvMa/Qm8u?= =?iso-8859-1?Q?VKMz2XpV5fCuo3jnNFqztLIiLZ7l9r6jODAHhXtTDhcOvFWllNUKJsvWl1?= =?iso-8859-1?Q?URD1jPIVbsq1HBMdQD4dE0KXz9icXkHnnSVCkCjrzjOFVO4OyyZlcia4n3?= =?iso-8859-1?Q?m7fpo2E2hoT2nxYZnrCV6VLDzTzporaXFyiUQaFX7SUvTE9c/EkkwLVvcB?= =?iso-8859-1?Q?RlfRQW7t1uNi2md9jUB2SZ7a3TLxKDKfVBh1aDxP3QWMe83Q6uXgU/LtUA?= =?iso-8859-1?Q?DjW5SeZ6usb/g6VSBjfTRtD2MFv7DKJujLIvHFKKtC1VSWzUsBVBlnsz+7?= =?iso-8859-1?Q?918ZJZVN+lAV9qsxoY6y5qFoQBY+VZFrzimY1wZnYBz38tOkdNrFvFcMgx?= =?iso-8859-1?Q?6nyjiKvWlJaTa5BNvSV/By2Y4/qdjyN50WEYVCovHanxZiSyvydoH3r3qn?= =?iso-8859-1?Q?joAJsCHlpLd3bYOqgSovrFPQDZaDTOoh2kHP50Nbi9d5y5z0OCPD+5QLp+?= =?iso-8859-1?Q?deK4+3qn0F7BulCF9d9M4AaivBQKjvspza3zHvzYwgMeHYJ7yBwMAvpkah?= =?iso-8859-1?Q?rMWI84kocuZmWVT+JBODcB2aHTGW5PtMOnVe1v8s+7gXSBZzE0hYYj/LiL?= =?iso-8859-1?Q?cyDnbG0sCIpD6YmsiM3aApZCn02DY3U95aGlm10XnHVDMqh7erZAOd+XRC?= =?iso-8859-1?Q?4/IgAilwGrI3I9Ic2BhUvPFhlL+9wuhrF/1gP1irIvYZGQv44aXA5UkpmL?= =?iso-8859-1?Q?rRQOFPotp3HIIE5gVKXUp9MVgTABxIHFTJkjJtz4Odk1IQbhxphmXaz2mm?= =?iso-8859-1?Q?vPqRodwdbtWQxNOc0iP2fJEhvvQKhqLXloSc7Qhn8LStvrdh02beG3u+OR?= =?iso-8859-1?Q?Tx2sfhqKq0Yb21Lg0G1Sh/50yRhFKlPXq8yEhk9MNfqFYHhQtc+KYQHOov?= =?iso-8859-1?Q?zFPIkITu5pWqjxSEUDx72kXlpp+Nhp2Vk9jLXg4rGOGKKeZ+WRnwbVQoJC?= =?iso-8859-1?Q?h9ALluWIOUw3L+Tgt+OXfSCHPy+zTuNccASpILzsu7M7+mckFY9IBYrxv5?= =?iso-8859-1?Q?mdjaCS5c/a6+2tkdst1lzBypjG0HH0fS280f1G4jwzKqe8rYvBPsV1H96o?= =?iso-8859-1?Q?f+I6jLfV6aDeiadeTs2tHAXGJsR2oTZ7viHDU879l84lpkugzK5yJ5vdGu?= =?iso-8859-1?Q?NlQNxGc9xX8Zb+S2L6DcR3sVNqT5YZn/jV28hIJsij3GLQjpIkmaC2YLZe?= =?iso-8859-1?Q?XnhRWprwTctaVtYl501AKlC4gQSPa8PdTa6V+oouxd1GlMjllRGY/ghJqO?= =?iso-8859-1?Q?ity+HZkvhu/oFYxi14IgSxuV5j3FlIjM0Rihhdh4qLQqR4mlNi+Ubmuq1d?= =?iso-8859-1?Q?4a58mRZbBxT+dnSEpCw+bQ3eVzNd7VgpdUaovROJUNlulVuOYvY9JYrSwb?= =?iso-8859-1?Q?K75PRa8FilirTVr85pXDIAG4rIy7Ng9F98+jJ15/VxUGQzVIR1uMCra/KC?= =?iso-8859-1?Q?13yvoZyz7JtNO6CqN5IHZZP9skbLyuhFLKvLwm0n1MZLZOtzKUF0nhzIiy?= =?iso-8859-1?Q?pgiRNFMQ5FuttUlJoPP45Znkd2dLRG2YhVpY13+im42nByel3dEvSSbDvz?= =?iso-8859-1?Q?cYXt0jnI5v/cqBbm248ZXzhZcrExVRcYr+p7UAEcbYcpU2/rCHyFLA+RtM?= =?iso-8859-1?Q?lLQ5Pe+fFys70EoXxs/5uK4+VvfSsKQOLzXUClZIn9kr3H2Dn3L+oALE4J?= =?iso-8859-1?Q?Nf9HOLMRVkZSKMHK2C9TTU8PGM0xpuk=3D?= 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: dc122f79-b9bf-447e-c071-08da4eda1519 X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Jun 2022 14:19:38.9411 (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: xxb+cYl0QcKFXL3sxe4ZaCZeeMn2+EUxoGCODm4K/NL211AtU0O3ksUIJ3UFU61Ur59Iy+MPOanUYn1Qz9YC7w== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB3342 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874 definitions=2022-06-15_04:2022-06-15,2022-06-15 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 malwarescore=0 mlxscore=0 adultscore=0 suspectscore=0 mlxlogscore=999 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206150056 X-Proofpoint-GUID: Kn3t0HQrhaVeNK94DqR1lg96wv-dcNP9 X-Proofpoint-ORIG-GUID: Kn3t0HQrhaVeNK94DqR1lg96wv-dcNP9 Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" It is possible to iterate over the metadata of full non-leaf nodes when operating in non-alloc mode. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 80622741c6b8..a1035963ae0d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5429,11 +5429,15 @@ static void mt_destroy_walk(struct maple_enode *eno= de, unsigned char ma_flags, goto start_slots_free; type =3D mte_node_type(mas.node); slots =3D ma_slots(mte_to_node(mas.node), type); - if ((offset < mt_slots[type]) && (slots[offset])) { - struct maple_enode *parent =3D mas.node; + if ((offset < mt_slots[type])) { + struct maple_enode *next =3D slots[offset]; =20 - mas.node =3D mas_slot_locked(&mas, slots, offset); - slots =3D mas_destroy_descend(&mas, parent, offset); + if (mte_node_type(next) && mte_to_node(next)) { + struct maple_enode *parent =3D mas.node; + + mas.node =3D mas_slot_locked(&mas, slots, offset); + slots =3D mas_destroy_descend(&mas, parent, offset); + } } node =3D mas_mn(&mas); } while (start !=3D mas.node); --=20 2.35.1 From nobody Mon Apr 27 07:48:13 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EBE94C43334 for ; Wed, 15 Jun 2022 14:20:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239404AbiFOOUj (ORCPT ); Wed, 15 Jun 2022 10:20:39 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35072 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1347340AbiFOOT6 (ORCPT ); Wed, 15 Jun 2022 10:19:58 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AA5E84A3EE for ; Wed, 15 Jun 2022 07:19:55 -0700 (PDT) Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 25FE3BvQ000856; Wed, 15 Jun 2022 14:19:43 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2021-07-09; bh=Lpeynluy62OchTcRR8nKZ47lIvc8NwMiD57bg/MEgmw=; b=vnMNxIfu5ikN9V6qoSeJ1TkSPDBuDoDkWIrccXijmhuDngEsavPvrUPUjRxLz7fS+9og mCy4vmCQfk0bG0hUb4qgKImbS3T8KO6O19XCEOKkHS2yiwY3E9ZscsmzFFgxL5s5Ci55 USpHIshjM/zAsGDLTK5Jii2uiZHTzeEemq1ZCJkIVBqcDoKJTeMC5twUkoMe/q0J8MZg 5OKxfPBSb1gT0yStgWIFe+6ukjrpM9+hmBSoq8OcIx1LJaPMoejGp1sDQVscCUd8DmAq hdvHwBuuAiVuQK7iXcl7EUC0ILnmnpQ6hTq47TM6uliuHG0UYTJXk7BCMUSnD3zeUUk6 Yw== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3gmjx9gjhq-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jun 2022 14:19:43 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 25FDtwuT008028; Wed, 15 Jun 2022 14:19:42 GMT Received: from nam02-sn1-obe.outbound.protection.outlook.com (mail-sn1anam02lp2044.outbound.protection.outlook.com [104.47.57.44]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com with ESMTP id 3gpr25uq1t-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jun 2022 14:19:42 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=D3oplxIuEHCcXthCcvtbnvkkYNkzzqggSU9SD83SgenMVaKFQyn5nd+EfdN9uciNrKENm9FqGXtur2JR3VisKjXXrnyCjdwT9zrO6T6fEaS0kDnHvEH4bFPEepacLA2i2qSO1QWBfTD3yCWPmfW4cl/1AzOcSy4FaX6yhiPnPOjCzkTUTcOcwG9KGCANlTtj7VgLsf6kijaivDtOm6CRL9JKUizIgd1/CmvDaAuJ4gFGMHF+1JZL+plC+9R3fIqBX2AMXuuQYG/zLxCN0I1Yqfyf584Ou8ZIaElINk82fepOlPMZsvZCAFnvsf2QINZoJsZzJl39SDlFkpmzn7MpxA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=Lpeynluy62OchTcRR8nKZ47lIvc8NwMiD57bg/MEgmw=; b=V3lzZe9NsYc2BgLB+Y60b91aCzRK9RPRbSqNBca4JRxEMoyFoLx4HJvD7tgqAi8AO5QKotlZ8ct5IHdukaSKvko5vBA4wbnlyY1op4t4cKDiMk/qV3Dx0MbcKrbjdfKNEAfwVT/xI3Xh1uHoarvlSTYoiJC3JpZx3ZRfvsswukZMdCwVXAOSAcfIVFGwNUOgsQU9yx7p/CueIJg1EMqQmqvTHux4mFTMpBCdNDpg43UUWvGEWrq2n/aa1yD1KpQvYenjtK+xG3maXxo60RVvKpFWaIYv4QZ1/S6dPAncovrwQvOSQdKuhz2jvtZbzRi9C9Iui62XmzoMWnd72fwM4Q== 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=Lpeynluy62OchTcRR8nKZ47lIvc8NwMiD57bg/MEgmw=; b=wDW5G0Ublj/Emy+kDXiSrdiAdF8gU3F5nQt/mOpWgONVzEZQRkl2FBiEIvGBHgycfzI3ibzi1uf5siyuEmpxGPK7cf41baybbf3224bntfXtju5UG9HwDJeGuMBnkZmpyt0rPMql7WLXQhF2ZlZMgx/PeOAC3Y0m5nWpLA1kDZ0= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by MN2PR10MB3342.namprd10.prod.outlook.com (2603:10b6:208:12b::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5332.15; Wed, 15 Jun 2022 14:19:39 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::e1df:2e42:6674:313e]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::e1df:2e42:6674:313e%7]) with mapi id 15.20.5332.013; Wed, 15 Jun 2022 14:19:39 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , Qian Cai CC: Yu Zhao Subject: [PATCH Fix 2/3] maple_tree: Change spanning store to work on larger trees Thread-Topic: [PATCH Fix 2/3] maple_tree: Change spanning store to work on larger trees Thread-Index: AQHYgMLyLu7LYBVCJECcWBJ+FZIYSQ== Date: Wed, 15 Jun 2022 14:19:39 +0000 Message-ID: <20220615141921.417598-3-Liam.Howlett@oracle.com> References: <20220615141921.417598-1-Liam.Howlett@oracle.com> In-Reply-To: <20220615141921.417598-1-Liam.Howlett@oracle.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-mailer: git-send-email 2.35.1 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 4ca0a7aa-f9c7-44cb-cf07-08da4eda156a x-ms-traffictypediagnostic: MN2PR10MB3342:EE_ x-microsoft-antispam-prvs: x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: lyDtuSjJcML8Z4a39O61l4wKa9n7YFwpo3hZ5u8IOHqd/jy/3qVNFR11LSmkYHkEZuHb5XUHOihZKiq3bqDSyR6/HsYdGATflmNQF55nWMheILsSTjLlWZdqpNRtdHozLjq2JjqaHmwvFvXGvhT/KpbrtCGdLl0KFDPdIXQgwdb3l79muVr5D0P7lY8/NsfYOudWER9IBFtwVx+YBiPT2QkJssw1vt2ppqxFZy6ZsIT8aDihr9RSNtv/s1EFzB16t1/kZeHiM0qlNTJD1lKgxKeTer1gDlgNWHyR9XwT1rqrMYWc6/kN4C5yhlBhhwnb4rHlHmJNHk+HJYlunN6MRzjxNwSoAhUgOnamEs1ezGtrIlJstpjgYnm0SHHdK77P0QpUto9qetoJNOFlE/4E0XTXUtFCVru5tOZRn71MJDEuGw+hK79PBzW0tngxPjEd1Jl7aVDR1MOtN0gFifguab1hKdfUBQGkWsdtLVCDd4RYRmXTqQCn27+6MZY6EpopuQasfwN3GL21YDp3q1j/lIPHZ6FkuOqsrfWbJa3wlWsAa0oHTtJmOJnkBqASshDq+ZRm/hdPckORDNyx+qLnU24jkLDoklMr3XLhBUqCVmFlLQcP2uDLkMWdAEbO0kW6I+tMuPEXD3Iqbk3wFmm/iOIDNLIeh+MkkuUiGN7EDnIWMYOqalxJsbFtJIrV3s1SO+LXqAo/xlui65ZeLA3RvSpIxeAWv0CUt2M9xWC75mU= x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SN6PR10MB3022.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230016)(366004)(30864003)(86362001)(316002)(122000001)(110136005)(38100700002)(186003)(5660300002)(4326008)(8936002)(2906002)(71200400001)(38070700005)(66556008)(64756008)(66476007)(8676002)(66446008)(6506007)(76116006)(91956017)(26005)(6512007)(508600001)(83380400001)(6486002)(1076003)(36756003)(44832011)(2616005)(66946007)(239114007)(579004);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?2mmM10LCmX7kaWDEGQGkBeSc4Hu0xJSgFXg7ALVI/OYlNK4ZASo3UqfThO?= =?iso-8859-1?Q?H0KblJ+1k0vacCZoapl72WUjMLYHuXaP/B8nP2eBRbY+1yPG/Kd8doV1P/?= =?iso-8859-1?Q?j9ap+c090BdFk/Q+edMF1S+tzV2/39EaGvDnsM9tKItjTH8jA0r4hg1BDh?= =?iso-8859-1?Q?v42Wwp8Fu5vDbPlzZVQK4Qg69K/BwN/iNwPNU+hssCA27lnj7Wg/+UQy1X?= =?iso-8859-1?Q?Jsbz57iux27IenI4AvDuMn3R5hDRrMdVoZ7De4Gf+z7FnC+66qXjJsiLyA?= =?iso-8859-1?Q?uOfG0NpYyqVmB1h3GfeheF+cRGwndcoIN6HMmI4WTEORRDNkQSG42rs47V?= =?iso-8859-1?Q?zL6GPOCS+MVx3xS68zQQV+QLzkj3rGj8wVxym7Byt371Sw7Sh9pg3jnZj+?= =?iso-8859-1?Q?XrJaSoTr2xpUfYX+hC1Frz4qMtohmmxbU5HSlpUKHNt86qrkeJGiGOqKt6?= =?iso-8859-1?Q?NLZqslU7YNBq7NeejXj3WiIK1B8dThWQPoOUdQcQycY2WDIpXgRRB/ZWx0?= =?iso-8859-1?Q?oEveZQ0C3thhxIzncFfoc6PbmTEXHpL0pW7vxDlIjpN+3GKre9sVqZuffr?= =?iso-8859-1?Q?7U7x+hBI/Hkvrrw/760IqU5BOxQ0ETq1I9Zq+gpb4ehFiF1vwWWhQ9yJNY?= =?iso-8859-1?Q?G06uv7NBuEys4QMn3qTQreFnA6J1pargpX5CuGPWQKb3HMzURXp/blMERb?= =?iso-8859-1?Q?0tDeh+28ZqmHmt8HIGnxnJ+pzQymwY/HPd3KY9ogrjo/0NanMQKDmYWQaT?= =?iso-8859-1?Q?DWRTv+pgkXMVBUv8ENxUbjOJIf0FfaaqhRlnEitxOV1K6CBrWnQkm8C8HW?= =?iso-8859-1?Q?ouzwfS0WVo7OOhh2aXgobYl+Qb4V/CRlKpL7HsTPEbQoelMU+XLLzYQfsr?= =?iso-8859-1?Q?DZ5qe4wpsmAb3eGmpkH7+wwmzxxH82OdGXfN6++mf+NIiZWTm5TRKWkcu2?= =?iso-8859-1?Q?q5igT2DqkTt0rXgiNutgDqL9gcxdqM487qX17jrwUq30lDY0OwFAFhvoJn?= =?iso-8859-1?Q?QXNvTh/R7J/ScmEKyQSlD+/rgf+f3HC8lmBPjYzVzXF7yKdFjkJ6+UfTdR?= =?iso-8859-1?Q?kom4/pe0tTCReEAokdzlANwDipFD4IshBojLgnQ5JShnEBQtw5KB2YmbBp?= =?iso-8859-1?Q?2UwMAhnNCC3gwgTwrXsUrH/SeDzzDRk1hsLr8sZ1Nuf2XUTJiLVVLgcZEH?= =?iso-8859-1?Q?FdmhhUwmfb8eejLOS7ig+XR03R1UWfYdQ4+Ell00AmViQuVOlqoI6UVufA?= =?iso-8859-1?Q?BtHCqeWHcAlRvMY8H6an1M/t+oOSBh8dlDuZxyD3XkR+NCWR+P5FNTwlC0?= =?iso-8859-1?Q?edgAeCus0vBBckZDbtjKptAnH+UhhWXiGmM9AR6vF5DLt1YfpLxnnmCaZo?= =?iso-8859-1?Q?+j6XfLcJ0DsLfmkLB4hXKzERJCV2aHDHg/XiZUxVHwxBvMs98isfJMVmoM?= =?iso-8859-1?Q?ptgkfcTq3w3dbNLujD38BxIp2Fx9Uj/L6/UzLta7Su/obkTvR9PQrm59Ld?= =?iso-8859-1?Q?Ai+cLRTxEAWcbaQwQzcDAEGERwx5HJ3inG6AtXZKd4VMCKNVXYLYvEhTwR?= =?iso-8859-1?Q?ALOZf54XEgGdYrdsMdYJYrjZa+UIPKi/TEZniTdXH9ICwBDn78myLJoDiG?= =?iso-8859-1?Q?CX7DVOzp5FskZU0SVnqdJtLEuRVXlhn8W4IfiIIq3cTGQoSyv1iF1ndybE?= =?iso-8859-1?Q?LKWJDAeKso0qMHTzR5/8EYJEUw3kfy2FIEqTIzV6Nu0lpKgYew4E0WeYPI?= =?iso-8859-1?Q?E+hAJTZtbwQivSHRh+oF6AhZRUvVD797lGccG/4ENj89J9v1+Q76vTSHZ2?= =?iso-8859-1?Q?JdmIObtIumfRFvNUnR0Ttuo+N5hUERM=3D?= 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: 4ca0a7aa-f9c7-44cb-cf07-08da4eda156a X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Jun 2022 14:19:39.5036 (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: /oV/sFbOQAb9mgUAH9JcLfftQe7earuxHlRVQgLLetjOtIr9se9RVKdrm84WAfFpX9gm7aNcbTZFwbTFZjPFnA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB3342 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874 definitions=2022-06-15_04:2022-06-15,2022-06-15 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 malwarescore=0 suspectscore=0 spamscore=0 mlxscore=0 phishscore=0 bulkscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206150056 X-Proofpoint-ORIG-GUID: gY37B8czSuKhRK3YqwfeHbpYHznM4pCo X-Proofpoint-GUID: gY37B8czSuKhRK3YqwfeHbpYHznM4pCo Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Spanning store had an issue which could lead to double free during a large tree modification. Fix this by being more careful about how nodes are added to the to-be-freed and to-be-destroyed list on this operation. Reported-by: Qian Cai Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 325 ++++++++++++++++++++++++++++++----------------- 1 file changed, 206 insertions(+), 119 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a1035963ae0d..f413b6f0da2b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1388,7 +1388,6 @@ static inline unsigned char ma_data_end(struct maple_= node *node, /* * mas_data_end() - Find the end of the data (slot). * @mas: the maple state - * @type: the type of maple node * * This method is optimized to check the metadata of a node if the node ty= pe * supports data end metadata. @@ -2272,6 +2271,31 @@ static inline void mas_wr_node_walk(struct ma_wr_sta= te *wr_mas) wr_mas->offset_end =3D mas->offset =3D offset; } =20 +/* + * mas_topiary_range() - Add a range of slots to the topiary. + * @mas: The maple state + * @destroy: The topiary to add the slots (usually destroy) + * @start: The starting slot inclusively + * @end: The end slot inclusively + */ +static inline void mas_topiary_range(struct ma_state *mas, + struct ma_topiary *destroy, unsigned char start, unsigned char end) +{ + void __rcu **slots; + unsigned offset; + + MT_BUG_ON(mas->tree, mte_is_leaf(mas->node)); + slots =3D ma_slots(mas_mn(mas), mte_node_type(mas->node)); + for (offset =3D start; offset <=3D end; offset++) { + struct maple_enode *enode =3D mas_slot_locked(mas, slots, offset); + + if (mte_dead_node(enode)) + continue; + + mat_add(destroy, enode); + } +} + /* * mast_topiary() - Add the portions of the tree to the removal list; eith= er to * be freed or discarded (destroy walk). @@ -2280,48 +2304,62 @@ static inline void mas_wr_node_walk(struct ma_wr_st= ate *wr_mas) static inline void mast_topiary(struct maple_subtree_state *mast) { MA_WR_STATE(wr_mas, mast->orig_l, NULL); - unsigned char l_off, r_off, offset; - unsigned long l_index; - struct maple_enode *child; - void __rcu **slots; + unsigned char r_start, r_end; + unsigned char l_start, l_end; + void **l_slots, **r_slots; =20 wr_mas.type =3D mte_node_type(mast->orig_l->node); - /* The left node is consumed, so add to the free list. */ - l_index =3D mast->orig_l->index; mast->orig_l->index =3D mast->orig_l->last; mas_wr_node_walk(&wr_mas); - mast->orig_l->index =3D l_index; - l_off =3D mast->orig_l->offset; - r_off =3D mast->orig_r->offset; - if (mast->orig_l->node =3D=3D mast->orig_r->node) { - slots =3D ma_slots(mte_to_node(mast->orig_l->node), wr_mas.type); - for (offset =3D l_off + 1; offset < r_off; offset++) - mat_add(mast->destroy, mas_slot_locked(mast->orig_l, - slots, offset)); + l_start =3D mast->orig_l->offset + 1; + l_end =3D mas_data_end(mast->orig_l); + r_start =3D 0; + r_end =3D mast->orig_r->offset; + + if (r_end) + r_end--; + + l_slots =3D ma_slots(mas_mn(mast->orig_l), + mte_node_type(mast->orig_l->node)); + + r_slots =3D ma_slots(mas_mn(mast->orig_r), + mte_node_type(mast->orig_r->node)); =20 + if ((l_start < l_end) && + mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_start))) { + l_start++; + } + + if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_end))) { + if (r_end) + r_end--; + } + + if ((l_start > r_end) && (mast->orig_l->node =3D=3D mast->orig_r->node)) return; + + /* At the node where left and right sides meet, add the parts between */ + if (mast->orig_l->node =3D=3D mast->orig_r->node) { + return mas_topiary_range(mast->orig_l, mast->destroy, + l_start, r_end); } =20 /* mast->orig_r is different and consumed. */ if (mte_is_leaf(mast->orig_r->node)) return; =20 - /* Now destroy l_off + 1 -> end and 0 -> r_off - 1 */ - offset =3D l_off + 1; - slots =3D ma_slots(mte_to_node(mast->orig_l->node), wr_mas.type); - while (offset < mt_slots[wr_mas.type]) { - child =3D mas_slot_locked(mast->orig_l, slots, offset++); - if (!child) - break; + if (mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_end))) + l_end--; =20 - mat_add(mast->destroy, child); - } =20 - slots =3D ma_slots(mte_to_node(mast->orig_r->node), - mte_node_type(mast->orig_r->node)); - for (offset =3D 0; offset < r_off; offset++) - mat_add(mast->destroy, - mas_slot_locked(mast->orig_l, slots, offset)); + if (l_start <=3D l_end) + mas_topiary_range(mast->orig_l, mast->destroy, l_start, l_end); + + if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_start))) + r_start++; + + if (r_start <=3D r_end) + mas_topiary_range(mast->orig_r, mast->destroy, 0, r_end); } =20 /* @@ -2329,19 +2367,13 @@ static inline void mast_topiary(struct maple_subtre= e_state *mast) * @mast: The maple subtree state * @old_r: The encoded maple node to the right (next node). */ -static inline void mast_rebalance_next(struct maple_subtree_state *mast, - struct maple_enode *old_r, bool free) +static inline void mast_rebalance_next(struct maple_subtree_state *mast) { unsigned char b_end =3D mast->bn->b_end; =20 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), mast->bn, b_end); - if (free) - mat_add(mast->free, old_r); - mast->orig_r->last =3D mast->orig_r->max; - if (old_r =3D=3D mast->orig_l->node) - mast->orig_l->node =3D mast->orig_r->node; } =20 /* @@ -2349,17 +2381,13 @@ static inline void mast_rebalance_next(struct maple= _subtree_state *mast, * @mast: The maple subtree state * @old_l: The encoded maple node to the left (previous node) */ -static inline void mast_rebalance_prev(struct maple_subtree_state *mast, - struct maple_enode *old_l) +static inline void mast_rebalance_prev(struct maple_subtree_state *mast) { unsigned char end =3D mas_data_end(mast->orig_l) + 1; unsigned char b_end =3D mast->bn->b_end; =20 mab_shift_right(mast->bn, end); mas_mab_cp(mast->orig_l, 0, end - 1, mast->bn, 0); - mat_add(mast->free, old_l); - if (mast->orig_r->node =3D=3D old_l) - mast->orig_r->node =3D mast->orig_l->node; mast->l->min =3D mast->orig_l->min; mast->orig_l->index =3D mast->orig_l->min; mast->bn->b_end =3D end + b_end; @@ -2367,68 +2395,116 @@ static inline void mast_rebalance_prev(struct mapl= e_subtree_state *mast, } =20 /* - * mast_sibling_rebalance_right() - Rebalance from nodes with the same par= ents. - * Check the right side, then the left. Data is copied into the @mast->bn. + * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favo= uring + * the node to the right. Checking the nodes to the right then the left a= t each + * level upwards until root is reached. Free and destroy as needed. + * Data is copied into the @mast->bn. * @mast: The maple_subtree_state. */ static inline -bool mast_sibling_rebalance_right(struct maple_subtree_state *mast, bool f= ree) +bool mast_spanning_rebalance(struct maple_subtree_state *mast) { - struct maple_enode *old_r; - struct maple_enode *old_l; + struct ma_state r_tmp =3D *mast->orig_r; + struct ma_state l_tmp =3D *mast->orig_l; + struct maple_enode *ancestor =3D NULL; + unsigned char start, end; + unsigned char depth =3D 0; =20 - old_r =3D mast->orig_r->node; - if (mas_next_sibling(mast->orig_r)) { - mast_rebalance_next(mast, old_r, free); - return true; - } + r_tmp =3D *mast->orig_r; + l_tmp =3D *mast->orig_l; + do { + mas_ascend(mast->orig_r); + mas_ascend(mast->orig_l); + depth++; + if (!ancestor && + (mast->orig_r->node =3D=3D mast->orig_l->node)) { + ancestor =3D mast->orig_r->node; + end =3D mast->orig_r->offset - 1; + start =3D mast->orig_l->offset + 1; + } =20 - old_l =3D mast->orig_l->node; - if (mas_prev_sibling(mast->orig_l)) { - mast->bn->type =3D mte_node_type(mast->orig_l->node); - mast_rebalance_prev(mast, old_l); - return true; - } + if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { + if (!ancestor) { + ancestor =3D mast->orig_r->node; + start =3D 0; + } =20 - return false; -} + mast->orig_r->offset++; + do { + mas_descend(mast->orig_r); + mast->orig_r->offset =3D 0; + depth--; + } while (depth); =20 -static inline int mas_prev_node(struct ma_state *mas, unsigned long min); -static inline int mas_next_node(struct ma_state *mas, struct maple_node *n= ode, - unsigned long max); -/* - * mast_cousin_rebalance_right() - Rebalance from nodes with different par= ents. - * Check the right side, then the left. Data is copied into the @mast->bn. - * @mast: The maple_subtree_state. - */ -static inline -bool mast_cousin_rebalance_right(struct maple_subtree_state *mast, bool fr= ee) -{ - struct maple_enode *old_l =3D mast->orig_l->node; - struct maple_enode *old_r =3D mast->orig_r->node; + mast_rebalance_next(mast); + do { + unsigned char l_off =3D 0; + struct maple_enode *child =3D r_tmp.node; =20 - MA_STATE(tmp, mast->orig_r->tree, mast->orig_r->index, mast->orig_r->last= ); + mas_ascend(&r_tmp); + if (ancestor =3D=3D r_tmp.node) + l_off =3D start; =20 - tmp =3D *mast->orig_r; - mas_next_node(mast->orig_r, mas_mn(mast->orig_r), ULONG_MAX); - if (!mas_is_none(mast->orig_r)) { - mast_rebalance_next(mast, old_r, free); - return true; - } + if (r_tmp.offset) + r_tmp.offset--; =20 - *mast->orig_r =3D *mast->orig_l; - *mast->r =3D *mast->l; - mas_prev_node(mast->orig_l, 0); - if (mas_is_none(mast->orig_l)) { - /* Making a new root with the contents of mast->bn */ - *mast->orig_l =3D *mast->orig_r; - *mast->orig_r =3D tmp; - return false; - } + if (l_off < r_tmp.offset) + mas_topiary_range(&r_tmp, mast->destroy, + l_off, r_tmp.offset); =20 - mast->orig_l->offset =3D 0; - mast_rebalance_prev(mast, old_l); - return true; + if (l_tmp.node !=3D child) + mat_add(mast->free, child); + + } while (r_tmp.node !=3D ancestor); + + *mast->orig_l =3D l_tmp; + return true; + + } else if (mast->orig_l->offset !=3D 0) { + if (!ancestor) { + ancestor =3D mast->orig_l->node; + end =3D mas_data_end(mast->orig_l); + } + + mast->orig_l->offset--; + do { + mas_descend(mast->orig_l); + mast->orig_l->offset =3D + mas_data_end(mast->orig_l); + depth--; + } while (depth); + + mast_rebalance_prev(mast); + do { + unsigned char r_off; + struct maple_enode *child =3D l_tmp.node; + + mas_ascend(&l_tmp); + if (ancestor =3D=3D l_tmp.node) + r_off =3D end; + else + r_off =3D mas_data_end(&l_tmp); + + if (l_tmp.offset < r_off) + l_tmp.offset++; + + if (l_tmp.offset < r_off) + mas_topiary_range(&l_tmp, mast->destroy, + l_tmp.offset, r_off); + + if (r_tmp.node !=3D child) + mat_add(mast->free, child); + + } while (l_tmp.node !=3D ancestor); + + *mast->orig_r =3D r_tmp; + return true; + } + } while (!mte_is_root(mast->orig_r->node)); + + *mast->orig_r =3D r_tmp; + *mast->orig_l =3D l_tmp; + return false; } =20 /* @@ -2462,18 +2538,16 @@ mast_ascend_free(struct maple_subtree_state *mast) * The node may not contain the value so set slot to ensure all * of the nodes contents are freed or destroyed. */ - if (mast->orig_r->max < mast->orig_r->last) - mast->orig_r->offset =3D mas_data_end(mast->orig_r) + 1; - else { - wr_mas.type =3D mte_node_type(mast->orig_r->node); - mas_wr_node_walk(&wr_mas); - } + wr_mas.type =3D mte_node_type(mast->orig_r->node); + mas_wr_node_walk(&wr_mas); /* Set up the left side of things */ mast->orig_l->offset =3D 0; mast->orig_l->index =3D mast->l->min; wr_mas.mas =3D mast->orig_l; wr_mas.type =3D mte_node_type(mast->orig_l->node); mas_wr_node_walk(&wr_mas); + + mast->bn->type =3D wr_mas.type; } =20 /* @@ -2881,7 +2955,7 @@ static int mas_spanning_rebalance(struct ma_state *ma= s, struct maple_enode *left =3D NULL, *middle =3D NULL, *right =3D NULL; =20 MA_STATE(l_mas, mas->tree, mas->index, mas->index); - MA_STATE(r_mas, mas->tree, mas->index, mas->index); + MA_STATE(r_mas, mas->tree, mas->index, mas->last); MA_STATE(m_mas, mas->tree, mas->index, mas->index); MA_TOPIARY(free, mas->tree); MA_TOPIARY(destroy, mas->tree); @@ -2897,14 +2971,9 @@ static int mas_spanning_rebalance(struct ma_state *m= as, mast->destroy =3D &destroy; l_mas.node =3D r_mas.node =3D m_mas.node =3D MAS_NONE; if (!mas_is_root_limits(mast->orig_l) && - unlikely(mast->bn->b_end <=3D mt_min_slots[mast->bn->type])) { - /* - * Do not free the current node as it may be freed in a bulk - * free. - */ - if (!mast_sibling_rebalance_right(mast, false)) - mast_cousin_rebalance_right(mast, false); - } + unlikely(mast->bn->b_end <=3D mt_min_slots[mast->bn->type])) + mast_spanning_rebalance(mast); + mast->orig_l->depth =3D 0; =20 /* @@ -2948,6 +3017,15 @@ static int mas_spanning_rebalance(struct ma_state *m= as, =20 /* Copy anything necessary out of the right node. */ mast_combine_cp_right(mast); + if (mte_dead_node(mast->orig_l->node) || + mte_dead_node(mast->orig_r->node)) { + printk("FUCKED. l %p is %s and r %p is %s\n", + mas_mn(mast->orig_l), + mte_dead_node(mast->orig_l->node) ? "dead" : "alive", + mas_mn(mast->orig_r), + mte_dead_node(mast->orig_r->node) ? "dead" : "alive"); + printk("Writing %lu-%lu\n", mas->index, mas->last); + } mast_topiary(mast); mast->orig_l->last =3D mast->orig_l->max; =20 @@ -2961,15 +3039,14 @@ static int mas_spanning_rebalance(struct ma_state *= mas, if (mas_is_root_limits(mast->orig_l)) break; =20 - /* Try to get enough data for the next iteration. */ - if (!mast_sibling_rebalance_right(mast, true)) - if (!mast_cousin_rebalance_right(mast, true)) - break; + if (!mast_spanning_rebalance(mast)) + break; =20 /* rebalancing from other nodes may require another loop. */ if (!count) count++; } + l_mas.node =3D mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), mte_node_type(mast->orig_l->node)); mast->orig_l->depth++; @@ -3042,6 +3119,7 @@ static inline int mas_rebalance(struct ma_state *mas, mast.orig_l =3D &l_mas; mast.orig_r =3D &r_mas; mast.bn =3D b_node; + mast.bn->type =3D mte_node_type(mas->node); =20 l_mas =3D r_mas =3D *mas; =20 @@ -3855,7 +3933,7 @@ static inline int mas_new_root(struct ma_state *mas, = void *entry) return 1; } /* - * mas_spanning_store() - Create a subtree with the store operation comple= ted + * mas_wr_spanning_store() - Create a subtree with the store operation com= pleted * and new nodes where necessary, then place the sub-tree in the actual tr= ee. * Note that mas is expected to point to the node which caused the store to * span. @@ -3941,6 +4019,13 @@ static inline int mas_wr_spanning_store(struct ma_wr= _state *wr_mas) mast.bn =3D &b_node; mast.orig_l =3D &l_mas; mast.orig_r =3D &r_mas; + if (mte_dead_node(mast.orig_l->node) || + mte_dead_node(mast.orig_r->node)) { + printk("FUCKED. l is %s and r is %s\n", + mte_dead_node(mast.orig_l->node) ? "dead" : "alive", + mte_dead_node(mast.orig_r->node) ? "dead" : "alive"); + printk("Writing %lu-%lu\n", mas->index, mas->last); + } /* Combine l_mas and r_mas and split them up evenly again. */ return mas_spanning_rebalance(mas, &mast, height + 1); } @@ -5387,6 +5472,9 @@ static inline void __rcu **mas_destroy_descend(struct= ma_state *mas, node =3D mas_mn(mas); slots =3D ma_slots(node, mte_node_type(mas->node)); next =3D mas_slot_locked(mas, slots, 0); + if ((mte_dead_node(next))) + next =3D mas_slot_locked(mas, slots, 1); + mte_set_node_dead(mas->node); node->type =3D mte_node_type(mas->node); node->piv_parent =3D prev; @@ -5394,6 +5482,7 @@ static inline void __rcu **mas_destroy_descend(struct= ma_state *mas, offset =3D 0; prev =3D mas->node; } while (!mte_is_leaf(next)); + return slots; } =20 @@ -5427,17 +5516,15 @@ static void mt_destroy_walk(struct maple_enode *eno= de, unsigned char ma_flags, mas.node =3D node->piv_parent; if (mas_mn(&mas) =3D=3D node) goto start_slots_free; + type =3D mte_node_type(mas.node); slots =3D ma_slots(mte_to_node(mas.node), type); - if ((offset < mt_slots[type])) { - struct maple_enode *next =3D slots[offset]; + if ((offset < mt_slots[type]) && mte_node_type(slots[offset]) && + mte_to_node(slots[offset])) { + struct maple_enode *parent =3D mas.node; =20 - if (mte_node_type(next) && mte_to_node(next)) { - struct maple_enode *parent =3D mas.node; - - mas.node =3D mas_slot_locked(&mas, slots, offset); - slots =3D mas_destroy_descend(&mas, parent, offset); - } + mas.node =3D mas_slot_locked(&mas, slots, offset); + slots =3D mas_destroy_descend(&mas, parent, offset); } node =3D mas_mn(&mas); } while (start !=3D mas.node); --=20 2.35.1 From nobody Mon Apr 27 07:48:13 2026 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C85D2C433EF for ; Wed, 15 Jun 2022 14:20:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1347099AbiFOOUc (ORCPT ); Wed, 15 Jun 2022 10:20:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35370 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1347248AbiFOOT6 (ORCPT ); Wed, 15 Jun 2022 10:19:58 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 333264A3E0 for ; Wed, 15 Jun 2022 07:19:55 -0700 (PDT) Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 25FDbEJq015196; Wed, 15 Jun 2022 14:19:44 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2021-07-09; bh=lmhWxVhmnXmxvHLPOyPtk7GraaRj0TzIN4wkdhlEmF4=; b=nOFY7FrqqGDAGM7pL8n/PSVLFVbKsyidQ2EjwaQcqBczBtMzBJJL52KXs4beKDq3fp10 fA41YH61Of757GuMgSIZFgw8uDS5n4TutKQUw6xB21weC2NrtvR01vU5+a8A44wGA1Tg RUjrOWEpRHpgttgheetYHjRCMKSTy70/Oha0BsL7+ky7MgtibYm1pDVKTQF1B0TLG6Yb UX5z0FHYsuZ5Cmf1yAP6rJ3O53D6JL25z8BhHKV8Mrwt873GtR13+6hze96BB7+GqIwU HU7bcms7B+d9KGcBp8QAqvvDGjP4GFxZMRPQ6B3QI5nQW9bcKqNHIiRJYYtS1N5071m4 hw== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3gmhn0gsfy-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jun 2022 14:19:44 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 25FDtwuU008028; Wed, 15 Jun 2022 14:19:43 GMT Received: from nam02-sn1-obe.outbound.protection.outlook.com (mail-sn1anam02lp2044.outbound.protection.outlook.com [104.47.57.44]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com with ESMTP id 3gpr25uq1t-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 15 Jun 2022 14:19:43 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=CTe92FeI9StVJRQ9YIPwzTc1ZmBSoAX+KvvAjbKE7kwobrk+8ZOdbzLMa75Wb/jQ6Du5LVvmfgu2uPk/wPLC+2iSLQHe3Xc/tcns41+kfUi+nkbGOWgpc7We3rRjWT3UQ7CU3wrRB2/mxWimdhfaZXHkpmAGv1RQxOo/ZuJOre7VppnYYCyfx3vWNvBLGL8DM1ebPAufNcp5XYcXeYcRaT/wiPLVNY3B74g2UsATQgowXpsHI/Ai49fteLHUd6kJQRotWWKDNlDZR3YCk5TJzJrY+2Z+Paeam/NLN7t1TE0IW6i9OqZG/V2GmGC+PpLeUwV4yp0tJbk2Sf46n3etig== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=lmhWxVhmnXmxvHLPOyPtk7GraaRj0TzIN4wkdhlEmF4=; b=ejy8XHmZ6uLTZIWHT6TTMfERAmG3IEad97PFh9rvMocXLQEt6dLAAJ4fQCgPmzO61bMU/f1BG7NRFpWPbM3hnsz7L1miGcLk6Apjf+dqXMxgFyMuCWZRFtqZqiPKBg4BElMR7MHY6plrVfPOggOF0z4ekssCPbJ4UNdBBx+ESgIKh+RgZWusczBx3DNnjSP46mYuyNS4fmcKI8Ewal64XzM72TIv2M+LszdxvcBCBKo/sqEvw4uQ8elufd4TMuykhLocrcxbQBEpauuE2PvmCEnPzz1RcLxGBzqL0PlOSy7i45DQAdrrkVpf5uvQlsIJQk4sj0KgSku9gd2babIyHQ== 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=lmhWxVhmnXmxvHLPOyPtk7GraaRj0TzIN4wkdhlEmF4=; b=wRkGeQxpAWCcE7XgEfhecJf+YIxwbToxtu6Tq+79J2Lv+vpkWryCARrtlzp0LTy6aEMPFZ/7pDEaLpbANy1R6Ww09OfAidN64xUb+A901CLqQCp+BOFh5hm+nsSVzGlBPwRxn2jbAdzgjxX/PF3adQC6+ggc1R503cTXcOTTVk8= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by MN2PR10MB3342.namprd10.prod.outlook.com (2603:10b6:208:12b::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5332.15; Wed, 15 Jun 2022 14:19:40 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::e1df:2e42:6674:313e]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::e1df:2e42:6674:313e%7]) with mapi id 15.20.5332.013; Wed, 15 Jun 2022 14:19:40 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , Qian Cai CC: Yu Zhao Subject: [PATCH Fix 3/3] test_maple_tree: Add tests for preallocations and large spanning writes Thread-Topic: [PATCH Fix 3/3] test_maple_tree: Add tests for preallocations and large spanning writes Thread-Index: AQHYgMLzPlBKBPzE6UyrbBOdTKnb3Q== Date: Wed, 15 Jun 2022 14:19:40 +0000 Message-ID: <20220615141921.417598-4-Liam.Howlett@oracle.com> References: <20220615141921.417598-1-Liam.Howlett@oracle.com> In-Reply-To: <20220615141921.417598-1-Liam.Howlett@oracle.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-mailer: git-send-email 2.35.1 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 65dc88f1-e0ca-4383-277f-08da4eda1608 x-ms-traffictypediagnostic: MN2PR10MB3342:EE_ x-microsoft-antispam-prvs: x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: N5VK+SuB2O1vz92R4cJUKJz/Eht3W6JRH07f8FDzHePAz/KLaUn7hvAokKpwaGeibHFtmH5TGNDXCNfaRACu5MZ+Prgqdo2BoguBORe7Lt6WScrzGTo6ADBqhgOvKNuWs8ua7BUjl8VPtKRRY4huGFnp6qTlTamgoQrXiP3jpDAwYxpANPo/TcThpxjME8LqXEhHZxj0qrEovXrFrQ2lQh8uC2p11E7s/smyprhYa2MpFMkV7oowTHzk4aTq+ufyE1arLYc7Xxe/DZ9/7xp5Yk+leK8SH2mZ6euvjrfUSzbMEdHtBvXpqD/ehH7MSdne6qgr9s+d4tSFSYAx7Iu/+8TX8gpHycXCEXi8fWkNFdqE/hGRTPLhFtzD34TvF8aSVxgGpEBPQegRVVBMrbqPqH4aJkB1ZekCz0CiiJFxeldfk/pouLNDVDnucmnuqDseGHf+HoIB/zf4QCWf4EFKj4XoH9ey+uTS1uOtc0852gbktbV2Vpd4VV4dXdVGqw+B2lAtoRrbjRsJlVFUgeAdOh+Un/1tenaJN8V4iMfN3K34erKAFzRQUu3NLo+P402/3toi950LXxW4+1ELEJ91CVRglxt/VuvjgUXbc+P1PCoymtksLBtcWoUn+lAELAGOVwaocwnR1enNacvt+tl8XMw9Jzexe8sRO1sas7TqwMVmgm1LiZ9k7gkDlvlsQBiWlszPBq1/MnLM4mBtX/zArQ== x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SN6PR10MB3022.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230016)(366004)(86362001)(316002)(122000001)(110136005)(38100700002)(186003)(5660300002)(4326008)(8936002)(2906002)(71200400001)(38070700005)(66556008)(64756008)(66476007)(8676002)(66446008)(6506007)(76116006)(91956017)(26005)(6512007)(508600001)(83380400001)(6486002)(1076003)(36756003)(44832011)(2616005)(66946007);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?hcidxkiWufkod5PZJorYTBYQoQvX6dflMKTRauwxGSYaeL6D4o87MGPOqA?= =?iso-8859-1?Q?EorjqXogLSFC+XpfsBd1mYWoH8wjyuLbUK+YpkCS3Q8J5SHmGi17781SgJ?= =?iso-8859-1?Q?TY0WfRTW7Ai21IsfMqgWS6f1rrG3gqaz+AgUQaPGZsovfrUQGigTRs+Uca?= =?iso-8859-1?Q?UPAAIcU2bwuKBILtBJxr+j+PTjOwmtTJEEhtt5NvvrN1ygKRpyKp5NWdqJ?= =?iso-8859-1?Q?cQDs8xLxtp5eaNBOnXLCfzCjhh9XATajaheD9USyRj9BW/9x3jX7Lj2ppf?= =?iso-8859-1?Q?ZLVIQd7KnAUVFCSJZzDG+18ixv63cusxzdGTVPCJaYRzNI/wBKl/xg3b/p?= =?iso-8859-1?Q?kXjy0pBPxSA+7BeCD9KnafLNNAiEX6vG4/2Suq1vAEqkML70gSdGRR4yhg?= =?iso-8859-1?Q?mhgfw9fa3KhP6zeZ3cRIM9IpoKBoh+q7WVjQNKVV3EbpjobkzhQn3jqphn?= =?iso-8859-1?Q?axHJul5zZQjTj20tI/MqR63jDCg/fOVv0MxS/eZwWtyKuC1uhAZvJOT35L?= =?iso-8859-1?Q?3w6mOEAkyarHVFALUGjG/BVk2hh2wzQpgyKAQhwHy5PzD9uwHQZ4mT3PXq?= =?iso-8859-1?Q?teaN08pwmvIZpDJBiHssv30ysJGp9m2Jw5CqAFiHZP2U1V1MND/koHTIPp?= =?iso-8859-1?Q?DHa8vLy2iiYTiQ7TMwBuLwCQN9sNWNkTmVaVx3DacNXclwrl9iZzruqLeZ?= =?iso-8859-1?Q?KYPEibi8xEVzI5V4x0m03haN4yex9qNr1djDdZh49zItHuN4Y4I/eNbCLi?= =?iso-8859-1?Q?7VseZF5k0GATxcfzYtkoboc8VHuVMAAmNrArJBiodC8wQMH9mPxYZi+fU8?= =?iso-8859-1?Q?XJ5xVY4g9SqRFieguTEWv9LUslP9zo/kF/eKfc5IRVeSwwptEJylekk6yX?= =?iso-8859-1?Q?mTH9gzFhKdKQKvObmC6eQV5MSiTH6glF6/pVECWblE3a4Q7RT/ENTU7wGQ?= =?iso-8859-1?Q?hRP++Cif8BDMPJKugnZbF+eZXwbzQTb3MT+1cmSo1+Zpga6UPwYtRdJdG9?= =?iso-8859-1?Q?2NE1yPXfzOtgk/CJAdLZt9ZA2tlWpHYQ36b4NEq35drxC775QknWot/EQM?= =?iso-8859-1?Q?8WU6fGYa5KGhCtcCF35nl58B5m86FqvzIoKrjqyfJyH3kDy+8OqZeXPWoV?= =?iso-8859-1?Q?D/ID6NskdecmVQqsXw9kvJFxx3hO9qarrLTYBKU22fyIKiY2JbK+S8I02C?= =?iso-8859-1?Q?9RyAaywES731DmVRykHTMynCb7Rkq4SKHACY+f3sDlg3JtGKO2XfTwl31H?= =?iso-8859-1?Q?llNFml9+C+VpqjsiAIc5Zeol35slQw+j/QBmOKOCPYx4846RIQTsSv5VzQ?= =?iso-8859-1?Q?BbzvyOUA0738XyxHBXJABzTxbtwGlkwOgiWsmFE0SWXko6lRlBrBtsUU1M?= =?iso-8859-1?Q?2KLtfIuKzvA6+ZSMWVD40NTc+Hcf76fJoBKAyqEkLun/lweSh1CNieTGxl?= =?iso-8859-1?Q?k4iTCCUhwP7VtL1+f6y4Od+zBVH+pjuEZynaUmjZs0bnwGnvAhOOluJEne?= =?iso-8859-1?Q?fBrDtLFvJw2OaWCBcWmoyUiqbkbCuDnr6rFe2VfXC9eqL/Zw7hnIUS4oPo?= =?iso-8859-1?Q?J8bhHbNCqSh8rQLpSL1C1Vy0zkX231aU9vFU2l7CJwm2RbzsnNm0Ap1Q0h?= =?iso-8859-1?Q?7kOkmjx2ZTvxTCjc46RR2UMaAIgK7DBi5MSfBy/f/KoVgTMwVFoYyrypwE?= =?iso-8859-1?Q?EXK+ZNm7waiZgj9fHbfxQx5eznNycd9SPN6mIZ8V0cJjgJ0YY16cti2iqq?= =?iso-8859-1?Q?KL9vtnHPvXNauNBITyaAea2JFJuHFIsknAcC9+Qz2TKmXbJDaP6zhvUQge?= =?iso-8859-1?Q?kXKDa+2L5pNqmCnfyXUNvckBUvhwUJ0=3D?= 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: 65dc88f1-e0ca-4383-277f-08da4eda1608 X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Jun 2022 14:19:40.2066 (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: yCWr5YEwKqJy3V5rroj8Mz42h3ZMMK+VGdZ3P6WVpYlNJlwwuhUaJF6ezravBGRNhbsft0k5w3l++kxKFmLsKw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB3342 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874 definitions=2022-06-15_04:2022-06-15,2022-06-15 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 malwarescore=0 suspectscore=0 spamscore=0 mlxscore=0 phishscore=0 bulkscore=0 mlxlogscore=988 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206150056 X-Proofpoint-GUID: Ftfg1-lK1bshmzOmxZX8RIUQ1tpDuS6S X-Proofpoint-ORIG-GUID: Ftfg1-lK1bshmzOmxZX8RIUQ1tpDuS6S Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Add test cases to ensure preallocaion works. Add more tests for spanning writes which alter tress with many levels and covers more corner cases. Signed-off-by: Liam R. Howlett --- lib/test_maple_tree.c | 277 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 277 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 8277464e182c..9fc0618f4ae7 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -35537,6 +35537,275 @@ static noinline void check_root_expand(struct map= le_tree *mt) mas_unlock(&mas); } =20 +static noinline void check_prealloc(struct maple_tree *mt) +{ + unsigned long i, max =3D 100; + unsigned long allocated; + unsigned char height; + struct maple_node *mn; + void *ptr=3D check_prealloc; + MA_STATE(mas, mt, 10, 20); + + mt_set_non_kernel(1000); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mas_destroy(&mas); + allocated =3D mas_allocated(&mas); + MT_BUG_ON(mt, allocated !=3D 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + mas_destroy(&mas); + allocated =3D mas_allocated(&mas); + MT_BUG_ON(mt, allocated !=3D 0); + + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mn =3D mas_pop_node(&mas); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); + ma_free_rcu(mn); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + mas_destroy(&mas); + allocated =3D mas_allocated(&mas); + MT_BUG_ON(mt, allocated !=3D 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mn =3D mas_pop_node(&mas); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + mas_destroy(&mas); + allocated =3D mas_allocated(&mas); + MT_BUG_ON(mt, allocated !=3D 0); + ma_free_rcu(mn); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mn =3D mas_pop_node(&mas); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); + mas_push_node(&mas, mn); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + mas_destroy(&mas); + allocated =3D mas_allocated(&mas); + MT_BUG_ON(mt, allocated !=3D 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mas_store_prealloc(&mas, ptr); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); + mt_set_non_kernel(1); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) =3D=3D = 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated !=3D 0); + mas_destroy(&mas); + + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated =3D=3D 0); + MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); + mt_set_non_kernel(1); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) =3D=3D = 0); + allocated =3D mas_allocated(&mas); + height =3D mas_mt_height(&mas); + MT_BUG_ON(mt, allocated !=3D 0); +} + +static noinline void check_spanning_write(struct maple_tree *mt) +{ + unsigned long i, max =3D 5000; + MA_STATE(mas, mt, 1200, 2380); + + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 1205); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test spanning store that requires a right cousin rebalance */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mas_set_range(&mas, 0, 12900); /* Spans more than 2 levels */ + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 1205); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test non-alloc tree spanning store */ + mt_init_flags(mt, 0); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mas_set_range(&mas, 0, 300); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 15); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test spanning store that requires a right sibling rebalance */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mas_set_range(&mas, 0, 12865); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 15); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test spanning store that requires a left sibling rebalance */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mas_set_range(&mas, 90, 13665); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 95); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test spanning store that requires a left cousin rebalance */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mas_set_range(&mas, 46805, 49995); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 46815); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* + * Test spanning store that requires a left cousin rebalance all the way + * to root + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + mas_set_range(&mas, 32395, 49995); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 46815); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* + * Test spanning store that requires a right cousin rebalance all the + * way to root + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + mas_set_range(&mas, 38875, 43190); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 38900); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test spanning store ending at full node (depth 2)*/ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + mtree_lock(mt); + mas_set(&mas, 47606); + mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); + mas_set(&mas, 47607); + mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); + mas_set(&mas, 47608); + mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); + mas_set(&mas, 47609); + mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); + /* Ensure the parent node is full */ + mas_ascend(&mas); + MT_BUG_ON(mt, (mas_data_end(&mas)) !=3D mt_slot_count(mas.node) - 1); + mas_set_range(&mas, 11516,48940); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test spanning write with many many levels of no siblings */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i <=3D max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + mas_set_range(&mas, 43200, 49999); + mtree_lock(mt); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + mas_set(&mas, 43200); + MT_BUG_ON(mt, mas_walk(&mas) !=3D NULL); + mtree_unlock(mt); + mtree_destroy(mt); +} + static noinline void check_null_expand(struct maple_tree *mt) { unsigned long i, max =3D 100; @@ -37678,6 +37947,14 @@ static int maple_tree_seed(void) check_new_node(&tree); mtree_destroy(&tree); =20 + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_prealloc(&tree); + mtree_destroy(&tree); + + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_spanning_write(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree); --=20 2.35.1