From patchwork Thu Jun 16 01:17:55 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 12883226 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 76AEBC433EF for ; Thu, 16 Jun 2022 01:18:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4534E6B0072; Wed, 15 Jun 2022 21:18:02 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4022A6B0074; Wed, 15 Jun 2022 21:18:02 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 22F888D0001; Wed, 15 Jun 2022 21:18:02 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id EBD506B0074 for ; Wed, 15 Jun 2022 21:18:01 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id CC599212E3 for ; Thu, 16 Jun 2022 01:18:01 +0000 (UTC) X-FDA: 79582337562.07.0D65D2C Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf19.hostedemail.com (Postfix) with ESMTP id 3C51A1A003E for ; Thu, 16 Jun 2022 01:18:01 +0000 (UTC) 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 25FLpV60029748; Thu, 16 Jun 2022 01:17:58 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=WwbgqN0jBzUCDRGnAFlAXcMr83worM9p824UDNGTRp9FTl1N4uuzO8PITiECiO9/Xcul DJdSEqmGxSxnFTXR/vry5xsBtI5ynC+Oko53ZfD46QhfEZ0vIwvay/o8P89j3lNn2ine l7siedgmFxXo3ILD/ICeykNu6F25AUYvWTzSpUBC+SX3/9P0KvNFw6aNsWfOmfA3hCHP IohsRipHNA40RFG/R8f9vTGKT7jMK+WUFVMNZT+TtMU2QstmHKDLGpjUkdwGECgAy8Xn rzQomfqUCR5LS8Ap81tKyhrBPTpaCjn7qCbe3jam1/raQ22X08FIdBMC+CEvmK4co1UP vQ== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3gmjx9hr0n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jun 2022 01:17:58 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 25G1AY2o025240; Thu, 16 Jun 2022 01:17:56 GMT Received: from nam11-dm6-obe.outbound.protection.outlook.com (mail-dm6nam11lp2174.outbound.protection.outlook.com [104.47.57.174]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3gprbsbqhj-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jun 2022 01:17:56 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=X4YwK2tcX25HRqp1w5AiU5dTlT6oKGR0tLdzP9a3ezN6NiP6F4FTLWcHTeXjGyZay+E/Jcq7FWLgsxDIeLbUlPS6quTdd5HO3EpB8UG+1lAgkYFkM/LrKV4E+JpRZ87jaYjrXZs9sdiH+xgAhpiuxn4Rt1sx/LzV+eLRRSrq/HZ8lqJEsgclDHOydpeY0KcSmDt8DvzRNxS+xBE7fFLgh5pl4pKBtD+y6tO3enE2vgwkU0MJ13M5wwMsM0FTJv2U+G6yBdVYciEoGwMg7SfO41JoD2EyGh7QIFbnjqbZc+RggZMJEObIfrSAE+CBhAh6ovzYODB1Z6XO1OyBeIBfYw== 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=EMoYT0ng021K0ChofsyUVQzTb6EQVyD4BGqTcO3rmcWjrDy4NGkYbDtoAIUMLqUbqHBi8jC/TpY4dd+RtwGEzkPp9SdOndw/zyo8uMC372MqpNxmM7hn0KbdUWR/F5NJotyIagb7U4ana6stxWclUIMzkbAXCloh9NyBB6jZgjjiR5C/OUgMUHKJjK0/ByCL1Oi+ikcivgideup+aHJCUTBFmFgW3XVBO1Bh2N6do//3GnDgETx0ugOEbWSv/IP4t7tqwmULsnjCBjJYtqdmlYQ8eehLCl+r7lkVJ2KW3zopAVftXhXFLRd/NbW7MESpHCpac+X375GvtvzVECYuzw== 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=f5p605Zi2FlIR8/dCUliPwoQoN8FqD2B5SqTBp82nudMpY1wDwPLKyQ4h1AQ6+iUHG3X1PSkT2i1OeiMPbnurC0JVKcf69+qrUiCFyQhPV8zRm1Atyu7NMBiSlkT3USqfc9cjEK2A0sYaWH6ntGdsEum9sHetE0i+xCu8LsDXdo= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by SN6PR10MB3456.namprd10.prod.outlook.com (2603:10b6:805:d0::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5332.17; Thu, 16 Jun 2022 01:17:55 +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; Thu, 16 Jun 2022 01:17:55 +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 v2 Fix 1/3] maple_tree: Fix mt_destroy_walk() on full non-leaf non-alloc nodes Thread-Topic: [PATCH v2 Fix 1/3] maple_tree: Fix mt_destroy_walk() on full non-leaf non-alloc nodes Thread-Index: AQHYgR7oTco3DccjcUe2xGaJZEub+A== Date: Thu, 16 Jun 2022 01:17:55 +0000 Message-ID: <20220616011739.802669-2-Liam.Howlett@oracle.com> References: <20220616011739.802669-1-Liam.Howlett@oracle.com> In-Reply-To: <20220616011739.802669-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: bdb094bd-4b82-45d9-f784-08da4f360aa1 x-ms-traffictypediagnostic: SN6PR10MB3456: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: uFUCRbhoPmwORp2K+tTaRxvGVHRPN5ENehJYSy5Brw9kVWKRkiK7PW6dXvyAqfo6xn1K4voFY40h07en3zOVIcURhOcXcYfSbF+UAdM3BDg/0TV24/3+0vYi2TNMmHP+qNNermSpwBItQ31tcNfYvjAIjOGJ1RGP011DePWxGpx9uiDxCWOSd/4iUdXEeEqGQx4eEUVtWN4sDjrG0vBazfoKuHh0ZQx3sqf4JsiqZ2HQe+1Z90IRTodlrFlHQb54uMYgj3WRWWIn3BDUCqUp2EiocJkh/sV3CEwWgD2ZYS0X3qMIDU45P2T1m3ZOFgGViOU6M32mY9+7g1skzlaFUHdAasqhueF6YBloKrduE5LoFlLfL7G2fqMg6BgaeEIcjQY6sj/WbLYsAmjmM9GocvRIONLK0gED7O5WIX+aMsL8PUE2evLn2yxHgRUOpP2LS2UnYR5HrqKBh0Tfgcvagq4IQSfTk4C8RNyx47CACzPJdaCMjI+nkMjb1iuYIkx9cMuvizVzILElduikkvD13eFmajYePtp3o4kjPlnE0YZtcj03C65zqZ4Vh5Rbo2iWOwkkf+7njTJw5wzJD3TN6boDGRmjALKVJ3GoAn5QrFWeOHFpDUaHClnU0IGf4NOupOM56/bM3oyARxyTeFyx+6Jg3GdJxafok+gQiXn/TdL0WkyIE9XoqKBC8s2X8UvyGFsWx+DgRtvbVYusHVUCgQ== 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)(26005)(186003)(66556008)(6506007)(1076003)(6512007)(2616005)(38100700002)(122000001)(86362001)(38070700005)(83380400001)(76116006)(91956017)(316002)(4326008)(8936002)(508600001)(6486002)(44832011)(36756003)(64756008)(5660300002)(2906002)(66946007)(110136005)(8676002)(71200400001)(66476007)(66446008);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?RjpsR+W9HX85NCReePOCfcq?= =?iso-8859-1?q?gRg5Iz8JU8vOT9j53XeAd18O4imi6aHOX7AxcJ4Cte6fVJFXkuZxrQfpFFfo?= =?iso-8859-1?q?4/xVVmbllBmh0KRAHszIwXrPIO1PhpPs7Ht/CnOsusKzJYyVzWje3/4BcWB7?= =?iso-8859-1?q?qfp/bhhF+RjbIW6O4UAr8eOvd4gUdjoNAkjnrSxNrJ4CI+PjjZSn0IRexCVk?= =?iso-8859-1?q?rbiM5YIgnz9kUZKFYyk6e8voy3bKofDsW8FmNvyV000FjIwjaKsOltFjQcgo?= =?iso-8859-1?q?XqruffhhXhF26hQbepBodjKt/4ighxVy2QCCQ2B9meTnzUfYBPBbRoWtrmUM?= =?iso-8859-1?q?Lt/Mwpl4UxmU9laQy9zsMSXeD793cxrf3JJ/h0bjyefu+xVKzBSj6D7KLZJ8?= =?iso-8859-1?q?J4+rbvi8tWf9II/rBl+hzjdSuOXMH+eJ0CwvAKNtTqueUyv7fgBW4xEglX70?= =?iso-8859-1?q?syfX7dvEVeYy07x5ijDebiKYxgSHQyuqoYDJoJanUy0PAi3w+vwUN/DgFIBs?= =?iso-8859-1?q?TQEQoaqJeMg8V0fE0P5RPGkh0033p0Q9YkXbXRA0c6SWUtKzoGzlALPQNdDS?= =?iso-8859-1?q?R8MF1luYyPtfiBeVnyMfJVVhf5nA97OWWCYFZIEP4ZD4wjeOO5a+jqDdZRbP?= =?iso-8859-1?q?q46hSS9hzzKInI/JKQiAJOQvH/NJF/3b/negWc1VM24q9NuumAr/XdnUZtt+?= =?iso-8859-1?q?jD8G8ffs3JOFtcmATnCmXoMTTjb9pOV9t3VpfuOyYuB7m7ajPKq7ongpqi0C?= =?iso-8859-1?q?dAVlNqCUYPJNspVh8oMh8L2lFYkepOK9c4+E9pH6sVPHDmt0qkR8xVEOih8i?= =?iso-8859-1?q?TiSiD6BQUV0jtYoWVJ+45yrt0k2NqEdRuGfNjoPWnhRs1kIlZccpOAutuesY?= =?iso-8859-1?q?iauMJeOygTeSS8LPKtVOJnoghEhjH/K23a+ShQIDPYUzX7IrtThJCeMUxgce?= =?iso-8859-1?q?8qeojyoSGT4jyKelwWL2mLhULMmpIK02/TgYsXKa6FwjdiBLo9+hC7t/bnFg?= =?iso-8859-1?q?Ax0AIjApqqJc9rRMQ+2rRXugVI47MIiOTMTxNUATmwufZZa5WGWO+YxnVepu?= =?iso-8859-1?q?9GWxI8EscfTyeBh2xLrvPep5QOf9w+p/H4RWbxNQ7v+3BKpJ8Y/5bLeHHqWX?= =?iso-8859-1?q?WECjN/4DF6PJWdG4QhKky8wEb6xIU4x0wuoVFrPZtGmvMnmY337Mv2Qbj8V/?= =?iso-8859-1?q?ZLucBJcZhBN/e/C3ttAH/lGVasWVsK1evKiAWr7IiMy3rG5Vp4zBOSbJyq5z?= =?iso-8859-1?q?2GLHOJd1psz9LdBC6f7P3lMu506pbLon0JSNiek4ba8h9AEzRHQBJ7cEbVIX?= =?iso-8859-1?q?107q/Wqfb/RLRAOGYQ+Qwcuema5HBikLHAB1WEVpAv29XkKwKD8NVz+4rfRu?= =?iso-8859-1?q?U0dHcnP/+ddEauit+P+Bo2Ce4S+f/UYdBBsEWVQ/ICegp97glyytNvDNNjXP?= =?iso-8859-1?q?N8PfRObtFUVGt3gU2OEtqAR6y7oDfp8BuU7+lhjfr27k3EfmVBFudgQQ6lRH?= =?iso-8859-1?q?WAkmOKJhGu+3Idec0dv9S2gYoD4Sul9RsPjJ4BtLm9B6TOdCay9B8tmJ9Y/x?= =?iso-8859-1?q?uht3wowZo1uSHhBDwvtvbbtmm5Swjiy05Xf07LPJGONM355q8YpoLyUDmZtS?= =?iso-8859-1?q?0I1F3Vfx8vIcHN01MqkTV0hmP0uT5Z2BjgWI0q2g3WFPn5LX6L4BIHy6FnN0?= =?iso-8859-1?q?wD/pos4M9zmavlVRGQLNEL4perJqdIWj27gseYvrV03xHOXsebvOZfnowy7v?= =?iso-8859-1?q?o/nsAkhx/wrPNnH4Lu6ueWknLn6NyqLa4Z4STDSXX5v1dlsHRPgKE+AnuBaf?= =?iso-8859-1?q?aGGlWUyg=3D?= 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: bdb094bd-4b82-45d9-f784-08da4f360aa1 X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Jun 2022 01:17:55.0936 (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: VPf7czaI440CaYMENE0TM3rEaTCbPai+YeONdB2+Es96tg2CfayTM9Z7f+LTC+2UAc3ivfPn2yJF2Bx4s5glWg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR10MB3456 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874 definitions=2022-06-15_08:2022-06-15,2022-06-15 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 mlxlogscore=999 spamscore=0 phishscore=0 suspectscore=0 adultscore=0 malwarescore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206160003 X-Proofpoint-ORIG-GUID: NaYCMUcC0OvvXIrkMoqd5xWpfnEaYL0_ X-Proofpoint-GUID: NaYCMUcC0OvvXIrkMoqd5xWpfnEaYL0_ ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1655342281; 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=gTOa4sCsowVfnMdwtik+r2rl6y+WpU7ND9MuGs2cInU=; b=6gTfCXJetl/u2+d6xp3Jk0QXVD8FjbM8WVnRmDw2d22I7CMRz6hR0bXiH1FpU6TTcWTAfl 4wDdpxQgSn0F+xkUxsjG4eqGxww8khYkOWsttTvVD/ClPPDzzm3IcLFTESf1g4SDHT0k10 ciMF8bSnPSIWAN8GFWKTsNspfuX/glk= ARC-Authentication-Results: i=2; imf19.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=WwbgqN0j; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=f5p605Zi; dmarc=pass (policy=none) header.from=oracle.com; spf=none (imf19.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1655342281; a=rsa-sha256; cv=pass; b=zjAaoRM74mdn5aeKAm4/ofdDJYDKKDoXBdC6SosobxynOaywJjOv5vvfpNs1jnVmc79RIs udNfvV1uTubvQcp5ln8UeF6OZ7Fd4o/mpNGl7a85QXaBg0ReP2m010zzjAbNjkq1qoDp1x fSpsyXHJqYjdbzGwhnyPRDQy4yzsHUs= X-Rspamd-Queue-Id: 3C51A1A003E X-Rspam-User: X-Stat-Signature: 8bz7bqrqwroxxp7rqfk7xahoq5fqxkkm Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=WwbgqN0j; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=f5p605Zi; dmarc=pass (policy=none) header.from=oracle.com; spf=none (imf19.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") X-Rspamd-Server: rspam04 X-HE-Tag: 1655342281-278672 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: 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 *enode, unsigned char ma_flags, goto start_slots_free; type = mte_node_type(mas.node); slots = ma_slots(mte_to_node(mas.node), type); - if ((offset < mt_slots[type]) && (slots[offset])) { - struct maple_enode *parent = mas.node; + if ((offset < mt_slots[type])) { + struct maple_enode *next = slots[offset]; - mas.node = mas_slot_locked(&mas, slots, offset); - slots = mas_destroy_descend(&mas, parent, offset); + if (mte_node_type(next) && mte_to_node(next)) { + struct maple_enode *parent = mas.node; + + mas.node = mas_slot_locked(&mas, slots, offset); + slots = mas_destroy_descend(&mas, parent, offset); + } } node = mas_mn(&mas); } while (start != mas.node); From patchwork Thu Jun 16 01:17:55 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 12883228 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 D8EBCCCA473 for ; Thu, 16 Jun 2022 01:18:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 82D4D8D0001; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7B4D88D0005; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 403828D0003; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 1C0168D0001 for ; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id ECB38612F9 for ; Thu, 16 Jun 2022 01:18:02 +0000 (UTC) X-FDA: 79582337604.17.35A6D20 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf30.hostedemail.com (Postfix) with ESMTP id 59A0780052 for ; Thu, 16 Jun 2022 01:18:02 +0000 (UTC) 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 25FLpV62029748; Thu, 16 Jun 2022 01:17:59 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=qCoqAd0xRUtkgvsdwZpRdfZP3PnguNS3NPvBRCHvxl4=; b=EOe1C5P8fPO25PscGBvxzsPTSP5ZjRhtdq+1IolOPPrwbqp4KCj5nsztfIk0Xk0vGNzG Tfh1QbRZHFoKsb+DSEzjHJSrS8npzvjl4YtHfTmaLz6QOuBzFIRgeHcYwayBvZAHEXI+ v3htFZ19CYWalnI6S5Z8kEMhtriFy1u+6ftLrcZ1lNshPMyPQ6hKMRHikX2ouhHvOsj3 /J40CxL5yaZYYx+qb/IOBOp3xK66zlvmteEwkVZEPrDHMWMR5HUr547GV8eGRYfFLDAD rj+GPr9afLI7TaQ4Sl+Y3yJ3N20JGU949/HPYvIbLqq7/NMozhgSkaR7KtHciEnItUtL LA== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3gmjx9hr0r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jun 2022 01:17:58 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 25G1AY2p025240; Thu, 16 Jun 2022 01:17:57 GMT Received: from nam11-dm6-obe.outbound.protection.outlook.com (mail-dm6nam11lp2174.outbound.protection.outlook.com [104.47.57.174]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3gprbsbqhj-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jun 2022 01:17:57 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=eMSczQNKh0d9G5UIEk0mPTp6pleC9ZhTG4OJeWru6bXMjTsM2y78P5R0Ed9yk8irx5JeNWZERL4bWGBsBG+QlCMY7d2OTHVetZM+UOlrtSRoFpyYAxMpc/4HLBpvFDbMniEmZPlCkQzWPGcZYO8/2/BmZ4cQOrhwgiMIS6D+wdZ9ijpd6Rmc9P+wxjL4y9DTupfhy7f0KDY4rBXTXD9AP7DerGJ6Bwc4TPn0XkZQ/IdspCPAp1pf4Y60NEbjRq3If4MXVb6U+w86RqyP/H58yvYUWxBExaE+DoIyaDYOfD4awPb0g/egUEHhDdLQ0z4Zv0my2DXUpZ9U45Ti0vWhnw== 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=qCoqAd0xRUtkgvsdwZpRdfZP3PnguNS3NPvBRCHvxl4=; b=T4NMF1kXUbrBJl3FaYgKMGwMyiTGsROawTC1okxlEt5sWBh+TZyfyjrlFmmB4pX4DinXAPQrWCaCMT7wDZA4sc5xMxtaAMWD0ZVu2rG7FdMVp2kj7Wfp1TrzQ4yKCgPRi1AJ3YxEXqgrdHVOuFq6VobLGEq+AZc45cBT7eaN3R8zI8YUzMFSQXfF67EtrcvdM+zv1wQX/YQbHvfv6gg24VOuBCMmvuC4q1o43LWjPEr+UDg4WL6UboXZ8tWyYKk7M6nUMUj2LRJPIbJuZLWDXq2PE6KMIEwGp+McPflKc8y+gNOWoMctV0U9TsssYiVM2uHjJauVQtZtsTDF8i1SKg== 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=qCoqAd0xRUtkgvsdwZpRdfZP3PnguNS3NPvBRCHvxl4=; b=IIMWmo3q45g5Rh6qNSaTbkiVJwmFVj1MMbuZWhy2RrrjaAiPxXB4aZf7ZsVliLoBDYJZfgZfLdHtWidcg4ODXCBOUpkoKi/kM+Sc56KnzLo4lN4ZOT99p/jcreaxh3IAgAmmSjy4tPyABob8tGXR1eY+u2S74VViY3Kw0p6WRxo= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by SN6PR10MB3456.namprd10.prod.outlook.com (2603:10b6:805:d0::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5332.17; Thu, 16 Jun 2022 01:17:55 +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; Thu, 16 Jun 2022 01:17:55 +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 v2 Fix 2/3] maple_tree: Change spanning store to work on larger trees Thread-Topic: [PATCH v2 Fix 2/3] maple_tree: Change spanning store to work on larger trees Thread-Index: AQHYgR7oSXwS6qQ3XEyxNkDHS/25dg== Date: Thu, 16 Jun 2022 01:17:55 +0000 Message-ID: <20220616011739.802669-3-Liam.Howlett@oracle.com> References: <20220616011739.802669-1-Liam.Howlett@oracle.com> In-Reply-To: <20220616011739.802669-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: 89aa1da0-7efe-480c-1a86-08da4f360ae7 x-ms-traffictypediagnostic: SN6PR10MB3456: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: tAxg+d1l7DxFqWCd3fHsgu4LEK9x5FK2PeKr9pKa9Lj1AKeF+6coXjnOLxO00FZpRB7SEKgAjjRXrB2DC5iUcuDAdfsis3iSaha8JW4/iCl3lDC/kX2UpHVJqU2OIcOSIPFOff+JrGtA1eG1bTGnakCjQzWiJw9akFJpHhkYyNfttxI2Yx0OcGuMnW3U8hOiqrYsg50uVrN/5seWReHuIvm9qtLpDZSnySNP8cjf5X/KDoR9qlcR+29LGr/t2nGB3KoI7LZk1HI+KbKzUdI1Qj/Dnu7gSuuxPovjVyOEqMs1lnRh8WHYVRGZXR0mMx0kq2WZLG11t7kwuzbj5xMZ2HswszLK8++T67dQ5/DBq6FtW0Up6xmTIYXnMujs1Vl9TYHdIZbtz4vD79CA+YSRMNJ2d0FQ9SQkAVaGFv0/J10ouYivbZH0j8UKw3yJgWlsAQSozGycdxxmfuTRzm0v7vnMBE70uuXtKrAwshGygl07jK8ERlY24mR9oIkXJf8hP0ThLm/cXmgdcwHyPCTUkJVugWXwp1AW6qVT79P9ExZWIoJx/5DQq6HbIjUVCs6Mw1HtqMbFmvFyFppM6f4sj1kdwbzHZ9w692BtMr8TG1z4KDMlBDoZgtgnZDcJJOvH+mgymsjzxRVu8ZGId1t32tbvcojoFZ6vmaeb4ihSFjtF+J8OWI8an75SWRSNpsAkc5Ye8O6PXKy5HDp0TEO/sg== 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)(26005)(186003)(66556008)(6506007)(1076003)(6512007)(2616005)(38100700002)(122000001)(86362001)(38070700005)(83380400001)(76116006)(91956017)(316002)(4326008)(8936002)(508600001)(6486002)(44832011)(36756003)(30864003)(64756008)(5660300002)(2906002)(66946007)(110136005)(8676002)(71200400001)(66476007)(66446008);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?2XB+ADGmeWvP3IYouK/QWm2?= =?iso-8859-1?q?Dqy1blBR3OVDMKflZuQcpWmKMMvVXlSEfIcdPKBbS64u3vzRHKgkJtSjrXOI?= =?iso-8859-1?q?3viLaznnKPFnBloZXMg8J1I+QRSnpgChzHp4WAFjSp0wDfwE8X/pRzNR0IOk?= =?iso-8859-1?q?9sTbRC/EIqFkiUYxqYSTVcx6dj9y7AnfXoMOXfKZJtoYJlrzWwjOBDb0KRNu?= =?iso-8859-1?q?ZZ89tdoIUYWPEANjwqtw863UJpbyfC51jUnOFO34rUF5nueL/fqGH+cgcMJ2?= =?iso-8859-1?q?Eg42KuYOH7D2rCB1OExXGWOjSRbxmf/btDUEBSe1+iAXzY6KN+6qQ5jlQHc5?= =?iso-8859-1?q?bsKpfDkjMzSFqsKqqS8gD7qztHheaRV0VDj9D10X66kxJEbgU6VRTAP6FOSy?= =?iso-8859-1?q?8u2PSv/KCfM8LzsB7nWJ64r2dX48eBC82tbHey31DnJU0KMyzKDlRP/uMzyx?= =?iso-8859-1?q?oEtQKLir+19hoRk7PjCjWN/kU9wrKqJXTXuMuScFqzB8uCiCXXy1mk6wrfyY?= =?iso-8859-1?q?84b3myDKDf6awiUAxynM3277NU2bjlwoUaebhHcaMtJPYqlzjkbjAG3mMvXB?= =?iso-8859-1?q?bkE1rwspWvAJmXtWHFI4yx8yUKe2B53MAQcCYwWg2V8qXf1i6GsZ/s/cbPtJ?= =?iso-8859-1?q?R4RwjHVYnOSNkDkFzdE3Wg8MLqZy+Ky19zoY+KXN0iJiZGPdKoSL44591O3E?= =?iso-8859-1?q?1HlIfZAbFLUveMkLrafeejJ4/PrGXcrrsmlRT3aI9yCT6nUPM9fplyxECaoy?= =?iso-8859-1?q?pWXKwLJGHABzqDx42mFIjilvDpQOfYnDVEDFR/7R+y0UwqPtmMAtoI96vR9D?= =?iso-8859-1?q?oQidEtVrVIjfQnul4PnqLjIO0JrH4Gxgd3zz4JVKC0iLYCV+0Q8RZVCbIVki?= =?iso-8859-1?q?WnI7fKpTfHgX+yUtODFyd+FMnaBewzoE9p2m8ajp8Wn/k9kPL3nTzwhznrGf?= =?iso-8859-1?q?WxNi0ofs9hM0tQjNMGtYop6Vgv4h5cUkypEKnAY8YUAwg7en0Iw+ohSTjEnN?= =?iso-8859-1?q?wzlTWKEl7VSZnak0yUsUXT9NA8hY4rd00fDCf/f6nfR715I7FaPP3hcf7NHg?= =?iso-8859-1?q?+91Pe3PxBMWzmSNQuP62mzFZqcj3NwKkDQKyYeD+g1xjyVq29yDPMyICpTlh?= =?iso-8859-1?q?zBIkRPRnP+ZvDQsZCw771zBiAAhRO/JRIozbah7T8ThhFIQsoSG/NkO+Xjfe?= =?iso-8859-1?q?DT52ENBuUwsvUo0r+Cyg7M+3GxeK4dVqHbBg+uOAEyepZLt9xYp73MSYo4vr?= =?iso-8859-1?q?zOcjsIcGJQ3oIVo3kLEIJ5JH6mLIk0QszF7RqqYvPxfzzmLtPPt8LAvO0AO+?= =?iso-8859-1?q?NvmNEwdx4AbuTJHxH0jLle8uL2BnKn0eLIXeZCzqQibN/XHBELn38j4B/QwU?= =?iso-8859-1?q?uxsSut3QUuIADbWpGXYbJjsDanCd8nWkCGOXnNeQM5QRWZR+7sZYMFzN4EQd?= =?iso-8859-1?q?Xqj0saZf9VnkPF13AJDoyWgVmMK95eGWQY1Wxlx1xn70aZW9t9B5/6s5wG4u?= =?iso-8859-1?q?ERe6TqZ7HPl7CjpEeHLjESu9xe5hhjBcBeqUQn6llJc7AfPRgF/niyfCPJvC?= =?iso-8859-1?q?obftXY87dYTzPAKzf3YjMbfQWkI2kM8JB/j7opYsaUxAQNNBXvM5SL+VjWNK?= =?iso-8859-1?q?B1EZdfg8GwDOZuF9cORNAKTI+mfdoMHrputYQRdhBU7aeFiyKCdKnynRfXlD?= =?iso-8859-1?q?i/ypyWLWFjj2WKQDKJQO0fHHtWqpZkyaYcRrJu1yiCtG4/d2E6Mx/24CY0LT?= =?iso-8859-1?q?MOEoSdRPpBMXxEc1APO08nxukDogyVvMI13jMddsn+AU1xjzZgbCI5CTh37o?= =?iso-8859-1?q?NeahQHSE=3D?= 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: 89aa1da0-7efe-480c-1a86-08da4f360ae7 X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Jun 2022 01:17:55.5936 (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: N/jASo+EtUbCN3RI55bMEBoTM9ACcbDCSWjIL9MBDU57Vpy/SkxS4tIAspfIKfJ/wiHYyhkS58KW1yo1+kJh4g== X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR10MB3456 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874 definitions=2022-06-15_08:2022-06-15,2022-06-15 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 mlxlogscore=999 spamscore=0 phishscore=0 suspectscore=0 adultscore=0 malwarescore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206160003 X-Proofpoint-ORIG-GUID: F5WYu6-QOJIss5LJnAxC74WhCiVmkRhG X-Proofpoint-GUID: F5WYu6-QOJIss5LJnAxC74WhCiVmkRhG ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1655342282; a=rsa-sha256; cv=pass; b=iqnixE89Ll/HYr4IxQdERMvgzKgvnSu/ch3x4VAysCuX1RSLybXPgAU3OXef6SaKSYQGMy AHPhvlzpSYE9DzWnpomMgyr/fjxzh+E8UiTWRK5SERPGjrsJNX7dXPn1tvXzkweip1Yffy 8XGtLGAvlWk11Z8xDMZt9twrOttU9Bg= ARC-Authentication-Results: i=2; imf30.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=EOe1C5P8; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=IIMWmo3q; dmarc=pass (policy=none) header.from=oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1"); spf=none (imf30.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1655342282; 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=qCoqAd0xRUtkgvsdwZpRdfZP3PnguNS3NPvBRCHvxl4=; b=ajQ2uTbg2EfcEsXliRyE9rq6ym5xhjtULPUhFSEWEtKSpz8VHwlbnXGxzLNKGSrrqKi9g6 JV8geDJJDZU2hl5FHdfBw7xn5/SVeTkcGNfqutRJtR4Mp+G4LrxpXNit6DUsjao6p/KR+b ePAtt8dz4m2QqpamWiO3HOXYBBhiMYs= X-Rspamd-Server: rspam03 X-Rspamd-Queue-Id: 59A0780052 X-Stat-Signature: dabwszg78pqq581aekuge4wf7g5crmnf Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=EOe1C5P8; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=IIMWmo3q; dmarc=pass (policy=none) header.from=oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1"); spf=none (imf30.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com X-Rspam-User: X-HE-Tag: 1655342282-970128 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: 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 Reported-by: kernel test robot --- lib/maple_tree.c | 309 +++++++++++++++++++++++++++++------------------ 1 file changed, 190 insertions(+), 119 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a1035963ae0d..aba5763bc7a1 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 type * supports data end metadata. @@ -2272,6 +2271,31 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) wr_mas->offset_end = mas->offset = offset; } +/* + * 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 = ma_slots(mas_mn(mas), mte_node_type(mas->node)); + for (offset = start; offset <= end; offset++) { + struct maple_enode *enode = 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; either to * be freed or discarded (destroy walk). @@ -2280,48 +2304,62 @@ static inline void mas_wr_node_walk(struct ma_wr_state *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; wr_mas.type = mte_node_type(mast->orig_l->node); - /* The left node is consumed, so add to the free list. */ - l_index = mast->orig_l->index; mast->orig_l->index = mast->orig_l->last; mas_wr_node_walk(&wr_mas); - mast->orig_l->index = l_index; - l_off = mast->orig_l->offset; - r_off = mast->orig_r->offset; - if (mast->orig_l->node == mast->orig_r->node) { - slots = ma_slots(mte_to_node(mast->orig_l->node), wr_mas.type); - for (offset = l_off + 1; offset < r_off; offset++) - mat_add(mast->destroy, mas_slot_locked(mast->orig_l, - slots, offset)); + l_start = mast->orig_l->offset + 1; + l_end = mas_data_end(mast->orig_l); + r_start = 0; + r_end = mast->orig_r->offset; + + if (r_end) + r_end--; + + l_slots = ma_slots(mas_mn(mast->orig_l), + mte_node_type(mast->orig_l->node)); + + r_slots = ma_slots(mas_mn(mast->orig_r), + mte_node_type(mast->orig_r->node)); + + 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 == mast->orig_r->node)) return; + + /* At the node where left and right sides meet, add the parts between */ + if (mast->orig_l->node == mast->orig_r->node) { + return mas_topiary_range(mast->orig_l, mast->destroy, + l_start, r_end); } /* mast->orig_r is different and consumed. */ if (mte_is_leaf(mast->orig_r->node)) return; - /* Now destroy l_off + 1 -> end and 0 -> r_off - 1 */ - offset = l_off + 1; - slots = ma_slots(mte_to_node(mast->orig_l->node), wr_mas.type); - while (offset < mt_slots[wr_mas.type]) { - child = 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--; - mat_add(mast->destroy, child); - } - slots = ma_slots(mte_to_node(mast->orig_r->node), - mte_node_type(mast->orig_r->node)); - for (offset = 0; offset < r_off; offset++) - mat_add(mast->destroy, - mas_slot_locked(mast->orig_l, slots, offset)); + if (l_start <= 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 <= r_end) + mas_topiary_range(mast->orig_r, mast->destroy, 0, r_end); } /* @@ -2329,19 +2367,13 @@ static inline void mast_topiary(struct maple_subtree_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 = mast->bn->b_end; 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 = mast->orig_r->max; - if (old_r == mast->orig_l->node) - mast->orig_l->node = mast->orig_r->node; } /* @@ -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 = mas_data_end(mast->orig_l) + 1; unsigned char b_end = mast->bn->b_end; 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 == old_l) - mast->orig_r->node = mast->orig_l->node; mast->l->min = mast->orig_l->min; mast->orig_l->index = mast->orig_l->min; mast->bn->b_end = end + b_end; @@ -2367,68 +2395,116 @@ static inline void mast_rebalance_prev(struct maple_subtree_state *mast, } /* - * mast_sibling_rebalance_right() - Rebalance from nodes with the same parents. - * Check the right side, then the left. Data is copied into the @mast->bn. + * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favouring + * the node to the right. Checking the nodes to the right then the left at 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 free) +bool mast_spanning_rebalance(struct maple_subtree_state *mast) { - struct maple_enode *old_r; - struct maple_enode *old_l; + struct ma_state r_tmp = *mast->orig_r; + struct ma_state l_tmp = *mast->orig_l; + struct maple_enode *ancestor = NULL; + unsigned char start, end; + unsigned char depth = 0; - old_r = mast->orig_r->node; - if (mas_next_sibling(mast->orig_r)) { - mast_rebalance_next(mast, old_r, free); - return true; - } + r_tmp = *mast->orig_r; + l_tmp = *mast->orig_l; + do { + mas_ascend(mast->orig_r); + mas_ascend(mast->orig_l); + depth++; + if (!ancestor && + (mast->orig_r->node == mast->orig_l->node)) { + ancestor = mast->orig_r->node; + end = mast->orig_r->offset - 1; + start = mast->orig_l->offset + 1; + } - old_l = mast->orig_l->node; - if (mas_prev_sibling(mast->orig_l)) { - mast->bn->type = 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 = mast->orig_r->node; + start = 0; + } - return false; -} + mast->orig_r->offset++; + do { + mas_descend(mast->orig_r); + mast->orig_r->offset = 0; + depth--; + } while (depth); -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 *node, - unsigned long max); -/* - * mast_cousin_rebalance_right() - Rebalance from nodes with different parents. - * 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 free) -{ - struct maple_enode *old_l = mast->orig_l->node; - struct maple_enode *old_r = mast->orig_r->node; + mast_rebalance_next(mast); + do { + unsigned char l_off = 0; + struct maple_enode *child = r_tmp.node; - MA_STATE(tmp, mast->orig_r->tree, mast->orig_r->index, mast->orig_r->last); + mas_ascend(&r_tmp); + if (ancestor == r_tmp.node) + l_off = start; - tmp = *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--; - *mast->orig_r = *mast->orig_l; - *mast->r = *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 = *mast->orig_r; - *mast->orig_r = tmp; - return false; - } + if (l_off < r_tmp.offset) + mas_topiary_range(&r_tmp, mast->destroy, + l_off, r_tmp.offset); - mast->orig_l->offset = 0; - mast_rebalance_prev(mast, old_l); - return true; + if (l_tmp.node != child) + mat_add(mast->free, child); + + } while (r_tmp.node != ancestor); + + *mast->orig_l = l_tmp; + return true; + + } else if (mast->orig_l->offset != 0) { + if (!ancestor) { + ancestor = mast->orig_l->node; + end = mas_data_end(mast->orig_l); + } + + mast->orig_l->offset--; + do { + mas_descend(mast->orig_l); + mast->orig_l->offset = + mas_data_end(mast->orig_l); + depth--; + } while (depth); + + mast_rebalance_prev(mast); + do { + unsigned char r_off; + struct maple_enode *child = l_tmp.node; + + mas_ascend(&l_tmp); + if (ancestor == l_tmp.node) + r_off = end; + else + r_off = 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 != child) + mat_add(mast->free, child); + + } while (l_tmp.node != ancestor); + + *mast->orig_r = r_tmp; + return true; + } + } while (!mte_is_root(mast->orig_r->node)); + + *mast->orig_r = r_tmp; + *mast->orig_l = l_tmp; + return false; } /* @@ -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 = mas_data_end(mast->orig_r) + 1; - else { - wr_mas.type = mte_node_type(mast->orig_r->node); - mas_wr_node_walk(&wr_mas); - } + wr_mas.type = mte_node_type(mast->orig_r->node); + mas_wr_node_walk(&wr_mas); /* Set up the left side of things */ mast->orig_l->offset = 0; mast->orig_l->index = mast->l->min; wr_mas.mas = mast->orig_l; wr_mas.type = mte_node_type(mast->orig_l->node); mas_wr_node_walk(&wr_mas); + + mast->bn->type = wr_mas.type; } /* @@ -2881,7 +2955,7 @@ static int mas_spanning_rebalance(struct ma_state *mas, struct maple_enode *left = NULL, *middle = NULL, *right = NULL; 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 *mas, mast->destroy = &destroy; l_mas.node = r_mas.node = m_mas.node = MAS_NONE; if (!mas_is_root_limits(mast->orig_l) && - unlikely(mast->bn->b_end <= 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 <= mt_min_slots[mast->bn->type])) + mast_spanning_rebalance(mast); + mast->orig_l->depth = 0; /* @@ -2961,15 +3030,14 @@ static int mas_spanning_rebalance(struct ma_state *mas, if (mas_is_root_limits(mast->orig_l)) break; - /* 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; /* rebalancing from other nodes may require another loop. */ if (!count) count++; } + l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), mte_node_type(mast->orig_l->node)); mast->orig_l->depth++; @@ -3042,6 +3110,7 @@ static inline int mas_rebalance(struct ma_state *mas, mast.orig_l = &l_mas; mast.orig_r = &r_mas; mast.bn = b_node; + mast.bn->type = mte_node_type(mas->node); l_mas = r_mas = *mas; @@ -3855,7 +3924,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 completed + * mas_wr_spanning_store() - Create a subtree with the store operation completed * and new nodes where necessary, then place the sub-tree in the actual tree. * Note that mas is expected to point to the node which caused the store to * span. @@ -5387,6 +5456,9 @@ static inline void __rcu **mas_destroy_descend(struct ma_state *mas, node = mas_mn(mas); slots = ma_slots(node, mte_node_type(mas->node)); next = mas_slot_locked(mas, slots, 0); + if ((mte_dead_node(next))) + next = mas_slot_locked(mas, slots, 1); + mte_set_node_dead(mas->node); node->type = mte_node_type(mas->node); node->piv_parent = prev; @@ -5394,6 +5466,7 @@ static inline void __rcu **mas_destroy_descend(struct ma_state *mas, offset = 0; prev = mas->node; } while (!mte_is_leaf(next)); + return slots; } @@ -5427,17 +5500,15 @@ static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags, mas.node = node->piv_parent; if (mas_mn(&mas) == node) goto start_slots_free; + type = mte_node_type(mas.node); slots = ma_slots(mte_to_node(mas.node), type); - if ((offset < mt_slots[type])) { - struct maple_enode *next = slots[offset]; + if ((offset < mt_slots[type]) && mte_node_type(slots[offset]) && + mte_to_node(slots[offset])) { + struct maple_enode *parent = mas.node; - if (mte_node_type(next) && mte_to_node(next)) { - struct maple_enode *parent = mas.node; - - mas.node = mas_slot_locked(&mas, slots, offset); - slots = mas_destroy_descend(&mas, parent, offset); - } + mas.node = mas_slot_locked(&mas, slots, offset); + slots = mas_destroy_descend(&mas, parent, offset); } node = mas_mn(&mas); } while (start != mas.node); From patchwork Thu Jun 16 01:17:55 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 12883227 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 ED7A1C43334 for ; Thu, 16 Jun 2022 01:18:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5FF2F8D0002; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4EF8C8D0001; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0D0188D0002; Wed, 15 Jun 2022 21:18:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id EC36F8D0001 for ; Wed, 15 Jun 2022 21:18:02 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id BA717203DB for ; Thu, 16 Jun 2022 01:18:02 +0000 (UTC) X-FDA: 79582337604.27.4B5864B Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf05.hostedemail.com (Postfix) with ESMTP id 3BA51100085 for ; Thu, 16 Jun 2022 01:18:02 +0000 (UTC) Received: from pps.filterd (m0246617.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 25FLcXru009908; Thu, 16 Jun 2022 01:17:59 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=VCxlausvk3jlr1ZuwJ4Ak7rA838MtTSLFOcBQ5nBlWYQT1pELnwcfF9lsxpAehUUJP3B 40fRYLm31bn3yT2nTdZyZRDKZkBIthShKv6oTyZ/dT18Uxan6M0t7bfBCm4p06ZWW22r QjdVBXxLA4Y5xch825y7rX+QobNLGM/QdbBzeHANWuWfotGL7k4QbezYk2Z3gRMme4rA rmxszt0mYGYHEv5RfFRG3ZacHwBFvrGGvWT4K5QkEU9m36PTgLk1JdJiwy6PO1tI/Akk LlH764pB7zK1JJzVdrqvNrX8rUp7C9MDIwdYDuZPyu0Ms8RzOTz6PyUvot46S0zGffl1 6g== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3gmkkthxps-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jun 2022 01:17:59 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 25G1AY2q025240; Thu, 16 Jun 2022 01:17:57 GMT Received: from nam11-dm6-obe.outbound.protection.outlook.com (mail-dm6nam11lp2174.outbound.protection.outlook.com [104.47.57.174]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3gprbsbqhj-4 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 16 Jun 2022 01:17:57 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=hWsuGYKX+/spARHYhH9fxNaoKIPuTofhdhwZOZpnw1SJr4nJVFFWvKdchyjx5PyiuJOET8vewsKD8l+H8l+/g8Ao9jOCvbHfQX7UYxTOdyE72cHVzKwQYVV/w3h0mIiAwvrvt3kr20n5viS9xVd82uRZIfcbhItBpUx0xIId2iJ0H7HR+312XZ28A5S+baCVl8h5K/jNbqIXobW6lJlabRNwgvZPEZLzVoYliAnX5ZajmcsStk8aaqQDtT7zxYL7CY6ZvrGTrQdXj3cmu5BT0SmNXZ5J1/+VnDUBtAsbyNEMxDJIvVekBAutJRkf2ItV+3y7I+mESjXoM/RN11dfig== 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=LIEeP3eXBD7GVOdI0IUwlgbxayDJ+ZwMbQLoWTpFu3U03qUU2qRt3RymWF8wsJpU7vJNukyuEO46adojZbLbbiMdjX1WxmarXNbnunmEE9k9dnBEfX8+7dMoXDGKhKkv5u3UACjXDGK7Xaxm/zp+nSPLS2PLO55xwVHkAumWDTVBS/TKF+lqkDn97ZqrrVgEUdNk/P+wnqEhAGpKLqu/9iojuElazJOWma3uDI0MiLRAYbwQLOkAd4wwE4VasDnWueVRf8NOfkTtuNl+JvaUHjmPKJ3rwAo+5EIBA6bT5Y08/Z5ey6ewILQv7N2prPHJkRCMBl7N7/4W1c+5WBuddw== 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=Xk8tLzMQJINJl1r9f61dIfJdpYqfThyPDb/UDpXCU27X4sf0ApDh3xQ264uibVf+DILcVVAXESWvpYKVB+/35tZOxoIdIGTqd6QX/tSHdbZlR+p8w5crq/kqNTLUoEN1L65GjvVIhoAnOYuExnlTVrYF/HnlwZKV/dlkhB9Gz5I= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by SN6PR10MB3456.namprd10.prod.outlook.com (2603:10b6:805:d0::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5332.17; Thu, 16 Jun 2022 01:17:56 +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; Thu, 16 Jun 2022 01:17:55 +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 v2 Fix 3/3] test_maple_tree: Add tests for preallocations and large spanning writes Thread-Topic: [PATCH v2 Fix 3/3] test_maple_tree: Add tests for preallocations and large spanning writes Thread-Index: AQHYgR7olLQoMIs+6Emr+1dYSc2pSg== Date: Thu, 16 Jun 2022 01:17:55 +0000 Message-ID: <20220616011739.802669-4-Liam.Howlett@oracle.com> References: <20220616011739.802669-1-Liam.Howlett@oracle.com> In-Reply-To: <20220616011739.802669-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: fb5ec49c-1b66-4969-c8c6-08da4f360b16 x-ms-traffictypediagnostic: SN6PR10MB3456: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: DqymvjYG+qz4k6S55NoNzXqAltlk85xmfjkFNArOLwvnHSgUiQdoBYeeCDAVnrQ6pEyEIExAVELlbE9JKcbRbmKB4FP/B7yYJsd8hR1q+3nuoG3NItWLgyvYKGBLmLYCFPSvxf6Rms5R9/fPfZsHHTMyCehF150W0vy8FAQYFov5b6OzBRSc4NNRopn9vHZRE3B4hkhfMQJPkfvsH7vltO2hf1nyBuW8KTZ8acvjpN3CfkNGyGfFJL8nUy344sK5BbeIu+kohI1X97mvlG0bmnMXMPKrwEHBgn2HwzMewFAzLJtrdVDx+0Y+uVjOeM+e9tqgovaiaYsCuUIgNcu6RAs5Wz3Yrzg4r7BCuOdtX4bRCkqt2w9tCgvmNAVM3fLYCs1Q7oGRMXckIU3DwvX8E9THBXLTQTbwSVQMauwyYrQSmiCxmKipvcAo6BUEUrkYA4SVvo1ioGIAGZorFe9PPAD7PuklNPkTBllXVjWAok8EDg1UtqliR50ErzgAFbNRdRU2c/SlvcQvvMb4zvgdSiOQiT3fTHkghkyg5UoArbXqk7o+zw5JgwagMPmp6TIqolGgzd+sV7/WB/VgY+1JTrM53Pzl0lqnF3qixj4hEYiT4FuS1JUmyZVZOKSiZWwB2p6VHJyXvN3qtaAQadZ/mxmRObzBhX/lhwuAGWwn9L3k3tQG/ocjoN6uMf1na9hXeQ1WlJQuJ3oochc7DQzckg== 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)(26005)(186003)(66556008)(6506007)(1076003)(6512007)(2616005)(38100700002)(122000001)(86362001)(38070700005)(83380400001)(76116006)(91956017)(316002)(4326008)(8936002)(508600001)(6486002)(44832011)(36756003)(64756008)(5660300002)(2906002)(66946007)(110136005)(8676002)(71200400001)(66476007)(66446008);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?6UVyFWhXt6iGLN6JiW/o8Ti?= =?iso-8859-1?q?XaTiq2pFCAlNaoE2HBkeo/CrFnzZzlXjp6QIyQ8zpPsXmbc63jBwBnp0B4ts?= =?iso-8859-1?q?lWyT3eHDsUYnZrzzJ51OY3U7ZtidiNw2hJIqBXjTwUo6JLswca2jb9Wteh4F?= =?iso-8859-1?q?wG5oBlIQbmZFAmKKiohKJ8VyQSD8+VHvKIPzm3Pu/c/yB7A+zkvzg6OCa/IC?= =?iso-8859-1?q?+i0CHmDHT6QxGXzwsH7DyoWGKUpyBQliUPZfJOQBu/3OcfGyoNScBB3vc4tE?= =?iso-8859-1?q?F1Vm/VfOjnmjLEEE19enmT69/zhJ7P8lE1x6V5Zk2D7MyM2LUAsjYAXa97yl?= =?iso-8859-1?q?hi3Hq5bmEu6SttGIJ4UdOqYoiShccfmYkjBN2Jw0FnVYBWk+4ktC3SXwEak0?= =?iso-8859-1?q?uPoeCcOuVo2I5GyfxiZ9Cj3tDbDXSfBgTK5S5IABpAs7G+EddDZq/abbH5HN?= =?iso-8859-1?q?C5+QErrx+XY7UxOdkKHsgUynWwH9qbBOAvjW9xTB2n/FIMjtpqLT/5d+89fd?= =?iso-8859-1?q?1tUt5+Lv+jMZxtitgEqmpTH0hNVX4pnaGkaHsHrB4PoIvh/0aisGfkHw4TyZ?= =?iso-8859-1?q?kBJGnUALbTOVZm0nw7Sn4wWFhJPg836KYAZeKMRhJq04H4avz8p7jMloFZ3P?= =?iso-8859-1?q?D5EtUhLFZ0oNT4eJkpC8tfXVlXVNFeKsfxxoBrIo7NsKDb7clYgLPWxBSkUj?= =?iso-8859-1?q?hlskGp33mC2Y/86lHUTEgypm/gQk1GP00DvUn9//qsn5jKQ2WOEqA17SdZmy?= =?iso-8859-1?q?7s796CKw8trO1+oDWp6P4FGun2f+jON88HBoydh8a+X4gIInD0CMRF07jKtb?= =?iso-8859-1?q?MVIDrR94bL5qXY8rtkBT4BcOEV1ttUyksiQPTLBjzydV/m0DJti0jsQz5mp+?= =?iso-8859-1?q?M+qSCZ+xMsdS+prM2P0uT2gN5wGW978kKPQ8kY/aTqg+yZgJZ70Bf9UUJQqv?= =?iso-8859-1?q?I6xdgrpH/UDPDujJVUGueYOnQEgGFxsjpGzXbPrXN16kzNi7T+QrEtsDaVRp?= =?iso-8859-1?q?tecoaywCHeg5Hg+2ya/CXp2TOwJlns5IRBFT8wwAn3iqtxDOGFmZ81sNR7E1?= =?iso-8859-1?q?Lht0dFuC9Q3T66ceP79lt1HQmtbnEBU2niq8xRiZykUVPRTzEK20AOf7pchi?= =?iso-8859-1?q?WvNRy0AxMrem8OoN7rj9FWOXp3eM3GdJ7p7AsxoGZb+A3/T1PzKNwxlmTRgA?= =?iso-8859-1?q?e+ped9bsIIgggWgsG0Uq1ZFb+AIlaSaoDAvFMu12AlFRHbsd+kwUx3plHLvU?= =?iso-8859-1?q?vNgltfQXc7ATFxctBUVjdYXzzKYn5gtGPe8TWcU+JZoeyfE4m3HGl3rr1FA3?= =?iso-8859-1?q?DOzQocpo2OHGKL6qhw3WvXxipzPnmM54T00IefLrVNqlywXCbvNtgECrCRIl?= =?iso-8859-1?q?dio+9D6/uZPDHR+Dbbr/8y3wjhEe7hYhLoGGWFPYA+gygzCLt61p0de1kIMu?= =?iso-8859-1?q?ZA+b7q8PEp5fRQtuJJodNtvdZEwNtJdDG0VlSoOkLdIm0De996ba/QXBn+2Y?= =?iso-8859-1?q?jTYsddAMUg8uy9qb3a3WHI+qdi1ORXyFisw5T1MPeFSGcimmM0JD3FDSlYCr?= =?iso-8859-1?q?XnfnEj0S29vOjCUr6Ah4GejB5v4Ywgoxj6fuzduPL5H8MbSanADgHXOBr+bw?= =?iso-8859-1?q?Nrf3G9vg445RRRTs4Ik5lI6P875+99XY/5K1nu3b2ee5R/r9cnZUQKp4oI5V?= =?iso-8859-1?q?wr2QTuJelCZd/I1zvletmm58epLcDJb7k1whd0/0M+JYItCAMexVuumRmQwM?= =?iso-8859-1?q?XW2ud5feOySfa9MxA1OJC+TCnAoKcfBGq+mm1G4hUOcAc7FpG7dqaoinI7+V?= =?iso-8859-1?q?tzfUsrH8=3D?= 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: fb5ec49c-1b66-4969-c8c6-08da4f360b16 X-MS-Exchange-CrossTenant-originalarrivaltime: 16 Jun 2022 01:17:55.9061 (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: pYLRgitQ0/NlnjoO2Fi0Z/a/dLrWe1TbSPq/IYAgO944CP9snPb8R48QlNSr0mu6Nhp3rbSMOsgk0Q/BLGCODg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR10MB3456 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874 definitions=2022-06-15_08:2022-06-15,2022-06-15 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 mlxlogscore=988 spamscore=0 phishscore=0 suspectscore=0 adultscore=0 malwarescore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206160003 X-Proofpoint-GUID: M-hjFE88NyI-UD6oC0F91KCQnpcybmwj X-Proofpoint-ORIG-GUID: M-hjFE88NyI-UD6oC0F91KCQnpcybmwj ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1655342282; a=rsa-sha256; cv=pass; b=AOLyeqYulNaymYHPmmkCsdbniCBTEcBKjDLagloGgqw6AltYctoKLK+lI5RpLbPx4BKoJu KV/yfvxD3uX41eK8k3c6GmVbJJi639/TC9bdOnnV/tQyx8jZUwCGbaZbS8xN/t+gIwK9fL z89xRpaRgz5waWS4kW1AaKit/WpSDac= ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1655342282; 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=lmhWxVhmnXmxvHLPOyPtk7GraaRj0TzIN4wkdhlEmF4=; b=H48IeX/sSq0r6HagjwiW/q6ybHtYF+dHnqX9CoPzLNDvQS2Ty9fFYjslOzCtc6FEcYexq2 YpN1pn0Dq56zwCHqZqQMLHR72oz3XDEsX8vCbFPEg37r1kEnXY1CCn6vqxGO85eTaqC/7I e7OfXfrH1GHOjyBXlAr8yPCineGfvBQ= ARC-Authentication-Results: i=2; imf05.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=VCxlausv; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=Xk8tLzMQ; dmarc=pass (policy=none) header.from=oracle.com; spf=none (imf05.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=VCxlausv; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=Xk8tLzMQ; dmarc=pass (policy=none) header.from=oracle.com; spf=none (imf05.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") X-Rspam-User: X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 3BA51100085 X-Stat-Signature: hmxu4mfwkoi584gs6zs3bgpwdjy7r75m X-HE-Tag: 1655342282-480416 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: 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 maple_tree *mt) mas_unlock(&mas); } +static noinline void check_prealloc(struct maple_tree *mt) +{ + unsigned long i, max = 100; + unsigned long allocated; + unsigned char height; + struct maple_node *mn; + void *ptr= check_prealloc; + MA_STATE(mas, mt, 10, 20); + + mt_set_non_kernel(1000); + for (i = 0; i <= max; i++) + mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mas_destroy(&mas); + allocated = mas_allocated(&mas); + MT_BUG_ON(mt, allocated != 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + mas_destroy(&mas); + allocated = mas_allocated(&mas); + MT_BUG_ON(mt, allocated != 0); + + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mn = mas_pop_node(&mas); + MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); + ma_free_rcu(mn); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + mas_destroy(&mas); + allocated = mas_allocated(&mas); + MT_BUG_ON(mt, allocated != 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mn = mas_pop_node(&mas); + MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + mas_destroy(&mas); + allocated = mas_allocated(&mas); + MT_BUG_ON(mt, allocated != 0); + ma_free_rcu(mn); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mn = mas_pop_node(&mas); + MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); + mas_push_node(&mas, mn); + MT_BUG_ON(mt, mas_allocated(&mas) != allocated); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + mas_destroy(&mas); + allocated = mas_allocated(&mas); + MT_BUG_ON(mt, allocated != 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) != 0); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) != 0); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mas_store_prealloc(&mas, ptr); + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) != 0); + mt_set_non_kernel(1); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated != 0); + mas_destroy(&mas); + + + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated == 0); + MT_BUG_ON(mt, allocated != 1 + height * 3); + mas_store_prealloc(&mas, ptr); + MT_BUG_ON(mt, mas_allocated(&mas) != 0); + mt_set_non_kernel(1); + MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); + allocated = mas_allocated(&mas); + height = mas_mt_height(&mas); + MT_BUG_ON(mt, allocated != 0); +} + +static noinline void check_spanning_write(struct maple_tree *mt) +{ + unsigned long i, max = 5000; + MA_STATE(mas, mt, 1200, 2380); + + for (i = 0; i <= 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) != 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 = 0; i <= 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) != NULL); + mtree_unlock(mt); + mtree_destroy(mt); + + /* Test non-alloc tree spanning store */ + mt_init_flags(mt, 0); + for (i = 0; i <= 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) != 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 = 0; i <= 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) != 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 = 0; i <= 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) != 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 = 0; i <= 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) != 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 = 0; i <= 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) != 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 = 0; i <= 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) != 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 = 0; i <= 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)) != 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 = 0; i <= 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) != NULL); + mtree_unlock(mt); + mtree_destroy(mt); +} + static noinline void check_null_expand(struct maple_tree *mt) { unsigned long i, max = 100; @@ -37678,6 +37947,14 @@ static int maple_tree_seed(void) check_new_node(&tree); mtree_destroy(&tree); + 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);