Received: by 2002:a05:6a10:1a4d:0:0:0:0 with SMTP id nk13csp4985420pxb; Sun, 6 Feb 2022 09:40:12 -0800 (PST) X-Google-Smtp-Source: ABdhPJwPHpXWu34PvVZYMdYcJN+ffyCx4V2S7FPmrMhGfaa/G4m8abKq37tStemJiDn8Z3dL9V5g X-Received: by 2002:a17:90a:c20a:: with SMTP id e10mr13942086pjt.165.1644169212591; Sun, 06 Feb 2022 09:40:12 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1644169212; cv=pass; d=google.com; s=arc-20160816; b=v3Yi7/PX+hFToArxek0LNZYuCG38E0nlSegnHvpxSYsLleTbiPGO56jBffLVnVuv2+ 5LpR1PBU70EqrgYcl2lrllxh+thnKAN8Xd8ps4uX0ZB8IvWajC0dnOolrWQREy62Ywy1 kHv2ZaPCqv+HZJmoa59eig09uF2mQrBiHO8AR3z7DgPFlTI00Wj310JNHx5gstNGWQwo Sy7nZXFSRagZ6GmPXgz13V9SZLoDe5dmoFhwzNB/eE5qdLLUWwyNs03c1ylyJPvsRSJF YDdiONNaR75drolXLZtvXgdnIGpzbxKZoW/jBYUr0nKyfyonh3gqfXZ3OVfCgwERhFjd 67Ag== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:mime-version:content-transfer-encoding :content-language:accept-language:in-reply-to:references:message-id :date:thread-index:thread-topic:subject:to:from:dkim-signature :dkim-signature; bh=TI7A/tj8xvFEQTxUiXLUSvlYTMt3vlMEqMOgLT/rlyk=; b=EU3mYl17jvcVeLMzUeEuhYliPiZiJK1ztAfL9i/udtYaXtpM/uzIFcjnPBIycNYyvV okXFXy19NppyX2TMrbh3OvBeSAUK5A+KxViHmxQ1HG+/bmPWrKJE2TWFb/g7gf1IGDkO rxXX84W9SreZ3u9DMyNGO4crldF6hi6kH8wpJhPwHYPlWEUgESG/mebAQoEODJZlphaK YEm0bv2StlTrKmtqiSBDtIfgJmf9Eo3yXczvmLuKKqug49TLKjbTS7d13NxvULdPzs1U UIk7wUe7zR8y06Z+oeAkNQAkLhxnWToDOgreavOqXzXxhPeHqZczpri0skC+tTfresc+ ZW8A== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@oracle.com header.s=corp-2021-07-09 header.b=yRrSEuOa; dkim=pass header.i=@oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=EV0hTb1d; arc=pass (i=1); spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=oracle.com Return-Path: Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id n9si1636552plc.434.2022.02.06.09.40.00; Sun, 06 Feb 2022 09:40:12 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@oracle.com header.s=corp-2021-07-09 header.b=yRrSEuOa; dkim=pass header.i=@oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=EV0hTb1d; arc=pass (i=1); spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=oracle.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S243993AbiBBCnZ (ORCPT + 99 others); Tue, 1 Feb 2022 21:43:25 -0500 Received: from mx0a-00069f02.pphosted.com ([205.220.165.32]:49574 "EHLO mx0a-00069f02.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S243970AbiBBCmX (ORCPT ); Tue, 1 Feb 2022 21:42:23 -0500 Received: from pps.filterd (m0246617.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 21207SdS022133; Wed, 2 Feb 2022 02:42:12 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2021-07-09; bh=TI7A/tj8xvFEQTxUiXLUSvlYTMt3vlMEqMOgLT/rlyk=; b=yRrSEuOa9OMArESu6m82wm80GF7ly7flVmkvbH/3aba2Z2SNqK8/x6uqwPJob0wgkTQU 4C7i44b7ZFBWkMG24wUbYbb/kdlCnaGv5v3NhvbG/Eqi9TIUx5U8dKRm4xxOVYA/BCF7 RsCR0+JG774yBE+WpcKOP90kqQX735zO8gy0hjc7zjz3PBumUUpEzo9hkPDDRWj7pGLI sOGuDO6O3wvBExFKu0Si2owIMApX4j/zeJW2Te/5MwPZKCRRcxKCe8m4iaBVAimCt7Ci 8fZUzbnxIn48japzVZ75klfaTK0em7fWzUBl/lkBTnCt1At9FE2ayU9bRRFdLypmaLqy Fw== Received: from aserp3030.oracle.com (aserp3030.oracle.com [141.146.126.71]) by mx0b-00069f02.pphosted.com with ESMTP id 3dxnk2m7pv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 02 Feb 2022 02:42:11 +0000 Received: from pps.filterd (aserp3030.oracle.com [127.0.0.1]) by aserp3030.oracle.com (8.16.1.2/8.16.1.2) with SMTP id 2122ZvkR015152; Wed, 2 Feb 2022 02:42:10 GMT Received: from nam04-bn8-obe.outbound.protection.outlook.com (mail-bn8nam08lp2047.outbound.protection.outlook.com [104.47.74.47]) by aserp3030.oracle.com with ESMTP id 3dvumggtjf-11 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 02 Feb 2022 02:42:10 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=FBn4AHMYWYOVAIrEVcF3FWpRLbZw0Skc0s8iVlc25cQsEKPu6epf21oOaLXBH6GmxMwHpEDMyJJygAZHiNMpnjL5U414WCJTEHwcJm6zQOc0P1FeiHnyDFK+lHOyi2nVZjxe1ajR8JI+wIBPxUaq5P1yLDG+z8xgxsPK0yo/jVnuZjVrYwZYXyr+3EKApm2nkzmY0PJ9loCbgiRe9BZQs+GVUB8ztJR/5e0KRpnvIkI1BjuqllAoF4vdwfaOCuGbtV6pUy31dghRfY9FE4CsCyV9e05IaLV1Xyf/IxUFeGDQ+liHvC9pqxef/SdaD/fmW0tRPDkSODvSD5g+MHTeVA== 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=TI7A/tj8xvFEQTxUiXLUSvlYTMt3vlMEqMOgLT/rlyk=; b=jhh2gzKToD6NtXnnQCYRVIW1XC7Nt7Cz6sOS3rz+KhX3hCpUMpW7FnNH3bTTav4XJu0h+nhJ8FruW1Fs/moIiCYsPJJHPay9d2LnRQLHO3sj2+TWBbhAiHS8U1/oNy0JLk1XMjZuTcr9dUxpJxtSHMf1xkzRPZEB8xwmQxA6zE/Uedsn4mTKoreFanpX+PEsrAjrankhR+tQHJiVlZ6XnJOxroVyP70pJ11qpbGUseBLN62ZfD69tVI5H11VDexBuLBydc7BCAR2vcMiZ2ZmTRnA934FIfNrvnuoYqA6ebpSaBtopzZJFAXk5yfstdQyrKY2hUgmY8GlZxdeSR1XKw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; 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=TI7A/tj8xvFEQTxUiXLUSvlYTMt3vlMEqMOgLT/rlyk=; b=EV0hTb1dyw2nN2hx4B5LM5RkLcF3BNOafrbPuXEoLe/vlBMMz0/xRU2gUmQxSfXO+QzbNX23q7RTJHDcIwGybTjNsr5Yh9UXQel+KdZx8bfZt8reWnI4T5/IKzNDOc/S3PbfOkQs7nsxTZLY9n1G1Q7iqJnNST8VIHu5pZtmbgI= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by BY5PR10MB3970.namprd10.prod.outlook.com (2603:10b6:a03:1ff::31) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4951.12; Wed, 2 Feb 2022 02:42:07 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::3857:3a25:3444:fdd3]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::3857:3a25:3444:fdd3%5]) with mapi id 15.20.4930.022; Wed, 2 Feb 2022 02:42:07 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton Subject: [PATCH v5 18/70] mm: Remove rb tree. Thread-Topic: [PATCH v5 18/70] mm: Remove rb tree. Thread-Index: AQHYF952w8q29rW2nkSJPvAJprmJng== Date: Wed, 2 Feb 2022 02:42:04 +0000 Message-ID: <20220202024137.2516438-19-Liam.Howlett@oracle.com> References: <20220202024137.2516438-1-Liam.Howlett@oracle.com> In-Reply-To: <20220202024137.2516438-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.34.1 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 14fd69db-5289-456c-4982-08d9e5f59ae8 x-ms-traffictypediagnostic: BY5PR10MB3970:EE_ x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:525; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: htgVKCUlJt/xuj5JNnVLH6L6Cmj6aVd//8hXZ6x0jnLlPIxlUrj/3udOQgrgBL6KqBENFgge53bOpyk3G8VWtbbtvBVeymiwFRQBBJwiCCERntf12rUui2xZA08daWGWODmRoHjvc8iDy2wLJO1e/xjfMiKCPbkWlCqdDaY8umzV2SAUnaK8yz43mx6FIFVPZNtiIMireyrWeALN+mtsBCefxWF+txf787HlzUwTsY9f68p8BlyAAtOC6iV+BuwOpkobCe9zFwu13ja40yGl+Cb7HfC6okfZJdZguAzuo10A3ZjEVyMyPgQlfdei6RMbcX+TYvWKmU/qoH9LxVXlqqE6HHId5kOyyQpBEElhCUhakAShN/sVLhI4Bb1Dy6gIVJScp7uvcP/Gd/Ap+FPU3lTmAxgkuO/32jyvm/5N4KiMIz03LncZsy+OzdbaxLzQbhGNf/+dmwBKqgxWr+O9TKKhyJyitGiFHad7LynzUWMl4veZWwlFqUC7oH+f6wH1RmxBUQA/FFle6v/ppm9A3tttRFTQgkvCCleuql+tN6xJVtNT7mI1Q/MnDo95nWSQSwoAslcAmRxxYXDRFFN1as++W5vUmEpbG96TB1yZ5t7tIq4p6HAunoNIbbhFHjsVkmkz4UVu1SV+6qIZZUQ5M4V35WQM47vVUbrUfgX3uIcP8RZON1idxhbg8p8WM9dPkwi4j5xO4zfDJFR0HcaAWw== 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:(13230001)(366004)(8936002)(316002)(110136005)(44832011)(2906002)(186003)(30864003)(66446008)(8676002)(91956017)(66476007)(71200400001)(508600001)(76116006)(6486002)(26005)(66946007)(66556008)(6512007)(5660300002)(6666004)(6506007)(64756008)(83380400001)(86362001)(1076003)(38070700005)(2616005)(38100700002)(122000001)(36756003)(579004)(559001);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?nsnTKK4O2iBDZfTFc+dFDtlOhRQYGmTl2ZUsiwxJ+9jooMDY2wpSG+f0lN?= =?iso-8859-1?Q?kpb8+6EbfzO5+8eXu8w1ECuIFV3TGrgwj6sgLAxaVgLSZyhT4jJXDV5IJC?= =?iso-8859-1?Q?S3TRzS+KS8EVGsWZQPIRHEI+orZv3md68vPv6DvuQcrvNY06A5Y7RpD2u3?= =?iso-8859-1?Q?Z/dY5aZ6H7+LcjvFid1bZSN868BaQaXq9Pbd/GhJnL9o0wbNho7sETgjQz?= =?iso-8859-1?Q?IKYucEuY+swkvrZWRA57UKKjIwt2UKzPzxUlAI5/4UPgjqSeO0A0O4VoC7?= =?iso-8859-1?Q?R6ufa074NskSkAHWpcr9u9cxkBuuTKIq3JIuOxMLd2k5kwvMMtcYCWxQEN?= =?iso-8859-1?Q?UGecYDlR2i2KMDAKJm3O0ah/xhj9eNuQkBpqgnbakrEjUDb76hAHwacUkW?= =?iso-8859-1?Q?tb7qN18ZrGozrardRENsKy2zLaeWMCvV/r5sSwgtuVL0xWtsXI9woUpmAp?= =?iso-8859-1?Q?SjD+O6J/W9/Mgk0b3blvm61D11T6wFIl36J0EM4YvYtmAE/tz9hnr5sR0z?= =?iso-8859-1?Q?2Q79x2pdh1AaDlXNXWhkAFkkrKxVauKVpbPkDzYvlZbxbFsmDto3ijLzb/?= =?iso-8859-1?Q?q7q/OVA2RgKzu8v6thtRZh3Ih3k+Qey4a3uBEgrowpF8lUY0nI4vnB4lEq?= =?iso-8859-1?Q?cWb55Gk8zimZrz2sE6/CsGzVeBMxdM1VfpJ2hA8B1hRnwd3Fl6m5ImX7nS?= =?iso-8859-1?Q?JUyXgEtHm81bkPQhheRGI53KAuCXjUjYRpRSJyhgxBb6pH8GebF9AO2YN/?= =?iso-8859-1?Q?ecG1wJ20r5EDalgkxEhsNCBDvf3byb5eYrMKfNwKRLgRvor4Qhd5iqMSh5?= =?iso-8859-1?Q?gftc1TnUlObQ8RnWNDz5+NG4DzkNkMOVIZPBBDJyJQbZUcAYX1cR/RtAle?= =?iso-8859-1?Q?PVdhqZR5GBfXy8oOHPH5oJumAduhf/yRmlkX0xfjq/yrkpqhIfJOX1Gx4I?= =?iso-8859-1?Q?od4xiL5HuRvjOKLujVQyyqCI0mP5vPXO4gMGe28Jn5yjXRJWtUVvvawXoO?= =?iso-8859-1?Q?pFcjevv2THKQ+I57FZjjgD7WOB5t5Pd0tOoOiy68X5tOF7zX0ac2CMrioZ?= =?iso-8859-1?Q?QHtquhDRyUW0EV/vubC9PpA57KSaOkH4EWpyBNuGHNg86G3YqPily9cj0p?= =?iso-8859-1?Q?oUBoErC73//fcAvQQLTc/tfs6LLTDo9TqxFu4bjlR7DLZaYjDKdteQDTZo?= =?iso-8859-1?Q?iyp5fTPDL3yLsv9VUCgYZK0/evu0xZ6nPFoF6vfrCP05C0O0MoBcRZpZxg?= =?iso-8859-1?Q?1FIs7uDxQs4s4uT3ok69guetoyOo4FrPiz+yHn4peApgzlow5S2nthkVIw?= =?iso-8859-1?Q?5bPv68vUS7NWde5FKD+eqmHMx/oKsA0WvyY4MxnCnEi2f8T/6Ze9cqgpL1?= =?iso-8859-1?Q?NEDk2KEl2VTGRwkKWpFCkvWcJ+uDRiUYJN/LVGtvx+RM9klucNywk1AqZr?= =?iso-8859-1?Q?43vPUSXLdQpl/8RbIgAZvcevrD6ZkLen2OpNaidbK/PIl6mAcrU5+Zx/KK?= =?iso-8859-1?Q?sij+YMFcpO/rW4VM/ryxt/d5iav7ArXbzmXGKSo9xr1SHFkwtKse4MOds7?= =?iso-8859-1?Q?cnIfaRlg2M0AFv0r3F/2sW5sMoU9fFetecK0aXq54jb+rzR8fhLO5zEBV5?= =?iso-8859-1?Q?lXK1s5LGUDP2CoSp4aKnC2JC4MTPf1ULZdeoNr/Vze49aD3WD8W1Y475FO?= =?iso-8859-1?Q?CvhfRw8KEezmtWU+K1I=3D?= Content-Type: text/plain; charset="iso-8859-1" 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: 14fd69db-5289-456c-4982-08d9e5f59ae8 X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Feb 2022 02:42:04.7206 (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: P4k1khIbWeGU3UAxt2fHvriMhWUKoYDD3skLjmreD2zRlKkqqSeRA3hddjCG0W0bGXaJi9NFQEN3hBQGkzsSxw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY5PR10MB3970 X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10245 signatures=673430 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 malwarescore=0 phishscore=0 mlxscore=0 adultscore=0 suspectscore=0 mlxlogscore=999 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2201110000 definitions=main-2202020010 X-Proofpoint-GUID: nzA0_4JpemT7d2mjoKbrfTHQYw7EUvgI X-Proofpoint-ORIG-GUID: nzA0_4JpemT7d2mjoKbrfTHQYw7EUvgI Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: "Liam R. Howlett" Remove the RB tree and start using the maple tree for vm_area_struct tracking. Drop validate_mm() calls in expand_upwards() and expand_downwards() as the lock is not held. Signed-off-by: Liam R. Howlett --- arch/x86/kernel/tboot.c | 1 - drivers/firmware/efi/efi.c | 1 - include/linux/mm.h | 2 - include/linux/mm_types.h | 14 -- kernel/fork.c | 8 - mm/init-mm.c | 2 - mm/mmap.c | 495 ++++++++----------------------------- mm/nommu.c | 87 ++----- mm/util.c | 10 +- 9 files changed, 136 insertions(+), 484 deletions(-) diff --git a/arch/x86/kernel/tboot.c b/arch/x86/kernel/tboot.c index 859e8d2ea070..a8e3130890ea 100644 --- a/arch/x86/kernel/tboot.c +++ b/arch/x86/kernel/tboot.c @@ -97,7 +97,6 @@ void __init tboot_probe(void) =20 static pgd_t *tboot_pg_dir; static struct mm_struct tboot_mm =3D { - .mm_rb =3D RB_ROOT, .mm_mt =3D MTREE_INIT_EXT(mm_mt, MM_MT_FLAGS, tboot_mm.mmap_lock= ), .pgd =3D swapper_pg_dir, .mm_users =3D ATOMIC_INIT(2), diff --git a/drivers/firmware/efi/efi.c b/drivers/firmware/efi/efi.c index c41efbff237c..6ddef91698e8 100644 --- a/drivers/firmware/efi/efi.c +++ b/drivers/firmware/efi/efi.c @@ -54,7 +54,6 @@ static unsigned long __initdata mem_reserve =3D EFI_INVAL= ID_TABLE_ADDR; static unsigned long __initdata rt_prop =3D EFI_INVALID_TABLE_ADDR; =20 struct mm_struct efi_mm =3D { - .mm_rb =3D RB_ROOT, .mm_mt =3D MTREE_INIT_EXT(mm_mt, MM_MT_FLAGS, efi_mm.mmap_lock), .mm_users =3D ATOMIC_INIT(2), .mm_count =3D ATOMIC_INIT(1), diff --git a/include/linux/mm.h b/include/linux/mm.h index cc6f72c86f3d..4c2341bcaf03 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -2664,8 +2664,6 @@ extern int __split_vma(struct mm_struct *, struct vm_= area_struct *, extern int split_vma(struct mm_struct *, struct vm_area_struct *, unsigned long addr, int new_below); extern int insert_vm_struct(struct mm_struct *, struct vm_area_struct *); -extern void __vma_link_rb(struct mm_struct *, struct vm_area_struct *, - struct rb_node **, struct rb_node *); extern void unlink_file_vma(struct vm_area_struct *); extern struct vm_area_struct *copy_vma(struct vm_area_struct **, unsigned long addr, unsigned long len, pgoff_t pgoff, diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h index 3cd5f8d8e3e2..bc5e55be5029 100644 --- a/include/linux/mm_types.h +++ b/include/linux/mm_types.h @@ -382,19 +382,6 @@ struct vm_area_struct { =20 /* linked list of VM areas per task, sorted by address */ struct vm_area_struct *vm_next, *vm_prev; - - struct rb_node vm_rb; - - /* - * Largest free memory gap in bytes to the left of this VMA. - * Either between this VMA and vma->vm_prev, or between one of the - * VMAs below us in the VMA rbtree and its ->vm_prev. This helps - * get_unmapped_area find a free area of the right size. - */ - unsigned long rb_subtree_gap; - - /* Second cache line starts here. */ - struct mm_struct *vm_mm; /* The address space we belong to. */ =20 /* @@ -457,7 +444,6 @@ struct mm_struct { struct { struct vm_area_struct *mmap; /* list of VMAs */ struct maple_tree mm_mt; - struct rb_root mm_rb; u64 vmacache_seqnum; /* per-thread vmacache */ #ifdef CONFIG_MMU unsigned long (*get_unmapped_area) (struct file *filp, diff --git a/kernel/fork.c b/kernel/fork.c index 8ea683fcefcd..9858ce389afd 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -502,7 +502,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *= mm, struct mm_struct *oldmm) { struct vm_area_struct *mpnt, *tmp, *prev, **pprev; - struct rb_node **rb_link, *rb_parent; int retval; unsigned long charge =3D 0; MA_STATE(old_mas, &oldmm->mm_mt, 0, 0); @@ -529,8 +528,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *= mm, mm->exec_vm =3D oldmm->exec_vm; mm->stack_vm =3D oldmm->stack_vm; =20 - rb_link =3D &mm->mm_rb.rb_node; - rb_parent =3D NULL; pprev =3D &mm->mmap; retval =3D ksm_fork(mm, oldmm); if (retval) @@ -620,10 +617,6 @@ static __latent_entropy int dup_mmap(struct mm_struct = *mm, tmp->vm_prev =3D prev; prev =3D tmp; =20 - __vma_link_rb(mm, tmp, rb_link, rb_parent); - rb_link =3D &tmp->vm_rb.rb_right; - rb_parent =3D &tmp->vm_rb; - /* Link the vma into the MT */ mas.index =3D tmp->vm_start; mas.last =3D tmp->vm_end - 1; @@ -1062,7 +1055,6 @@ static struct mm_struct *mm_init(struct mm_struct *mm= , struct task_struct *p, struct user_namespace *user_ns) { mm->mmap =3D NULL; - mm->mm_rb =3D RB_ROOT; mt_init_flags(&mm->mm_mt, MM_MT_FLAGS); mt_set_external_lock(&mm->mm_mt, &mm->mmap_lock); mm->vmacache_seqnum =3D 0; diff --git a/mm/init-mm.c b/mm/init-mm.c index 7622ca24eeb7..faf70cda302f 100644 --- a/mm/init-mm.c +++ b/mm/init-mm.c @@ -1,6 +1,5 @@ // SPDX-License-Identifier: GPL-2.0 #include -#include #include #include #include @@ -28,7 +27,6 @@ * and size this cpu_bitmask to NR_CPUS. */ struct mm_struct init_mm =3D { - .mm_rb =3D RB_ROOT, .mm_mt =3D MTREE_INIT_EXT(mm_mt, MM_MT_FLAGS, init_mm.mmap_lock), .pgd =3D swapper_pg_dir, .mm_users =3D ATOMIC_INIT(2), diff --git a/mm/mmap.c b/mm/mmap.c index 02b12d7dd362..2158a14d0e0b 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -39,7 +39,6 @@ #include #include #include -#include #include #include #include @@ -289,93 +288,6 @@ SYSCALL_DEFINE1(brk, unsigned long, brk) return origbrk; } =20 -static inline unsigned long vma_compute_gap(struct vm_area_struct *vma) -{ - unsigned long gap, prev_end; - - /* - * Note: in the rare case of a VM_GROWSDOWN above a VM_GROWSUP, we - * allow two stack_guard_gaps between them here, and when choosing - * an unmapped area; whereas when expanding we only require one. - * That's a little inconsistent, but keeps the code here simpler. - */ - gap =3D vm_start_gap(vma); - if (vma->vm_prev) { - prev_end =3D vm_end_gap(vma->vm_prev); - if (gap > prev_end) - gap -=3D prev_end; - else - gap =3D 0; - } - return gap; -} - -#ifdef CONFIG_DEBUG_VM_RB -static unsigned long vma_compute_subtree_gap(struct vm_area_struct *vma) -{ - unsigned long max =3D vma_compute_gap(vma), subtree_gap; - if (vma->vm_rb.rb_left) { - subtree_gap =3D rb_entry(vma->vm_rb.rb_left, - struct vm_area_struct, vm_rb)->rb_subtree_gap; - if (subtree_gap > max) - max =3D subtree_gap; - } - if (vma->vm_rb.rb_right) { - subtree_gap =3D rb_entry(vma->vm_rb.rb_right, - struct vm_area_struct, vm_rb)->rb_subtree_gap; - if (subtree_gap > max) - max =3D subtree_gap; - } - return max; -} - -static int browse_rb(struct mm_struct *mm) -{ - struct rb_root *root =3D &mm->mm_rb; - int i =3D 0, j, bug =3D 0; - struct rb_node *nd, *pn =3D NULL; - unsigned long prev =3D 0, pend =3D 0; - - for (nd =3D rb_first(root); nd; nd =3D rb_next(nd)) { - struct vm_area_struct *vma; - vma =3D rb_entry(nd, struct vm_area_struct, vm_rb); - if (vma->vm_start < prev) { - pr_emerg("vm_start %lx < prev %lx\n", - vma->vm_start, prev); - bug =3D 1; - } - if (vma->vm_start < pend) { - pr_emerg("vm_start %lx < pend %lx\n", - vma->vm_start, pend); - bug =3D 1; - } - if (vma->vm_start > vma->vm_end) { - pr_emerg("vm_start %lx > vm_end %lx\n", - vma->vm_start, vma->vm_end); - bug =3D 1; - } - spin_lock(&mm->page_table_lock); - if (vma->rb_subtree_gap !=3D vma_compute_subtree_gap(vma)) { - pr_emerg("free gap %lx, correct %lx\n", - vma->rb_subtree_gap, - vma_compute_subtree_gap(vma)); - bug =3D 1; - } - spin_unlock(&mm->page_table_lock); - i++; - pn =3D nd; - prev =3D vma->vm_start; - pend =3D vma->vm_end; - } - j =3D 0; - for (nd =3D pn; nd; nd =3D rb_prev(nd)) - j++; - if (i !=3D j) { - pr_emerg("backwards %d, forwards %d\n", j, i); - bug =3D 1; - } - return bug ? -1 : i; -} #if defined(CONFIG_DEBUG_MAPLE_TREE) extern void mt_validate(struct maple_tree *mt); extern void mt_dump(const struct maple_tree *mt); @@ -403,17 +315,25 @@ static void validate_mm_mt(struct mm_struct *mm) dump_stack(); #ifdef CONFIG_DEBUG_VM dump_vma(vma_mt); - pr_emerg("and next in rb\n"); + pr_emerg("and vm_next\n"); dump_vma(vma->vm_next); #endif pr_emerg("mt piv: %px %lu - %lu\n", vma_mt, mas.index, mas.last); pr_emerg("mt vma: %px %lu - %lu\n", vma_mt, vma_mt->vm_start, vma_mt->vm_end); - pr_emerg("rb vma: %px %lu - %lu\n", vma, + if (vma->vm_prev) { + pr_emerg("ll prev: %px %lu - %lu\n", + vma->vm_prev, vma->vm_prev->vm_start, + vma->vm_prev->vm_end); + } + pr_emerg("ll vma: %px %lu - %lu\n", vma, vma->vm_start, vma->vm_end); - pr_emerg("rb->next =3D %px %lu - %lu\n", vma->vm_next, - vma->vm_next->vm_start, vma->vm_next->vm_end); + if (vma->vm_next) { + pr_emerg("ll next: %px %lu - %lu\n", + vma->vm_next, vma->vm_next->vm_start, + vma->vm_next->vm_end); + } =20 mt_dump(mas.tree); if (vma_mt->vm_end !=3D mas.last + 1) { @@ -437,21 +357,6 @@ static void validate_mm_mt(struct mm_struct *mm) VM_BUG_ON(vma); mt_validate(&mm->mm_mt); } -#else -#define validate_mm_mt(root) do { } while (0) -#endif -static void validate_mm_rb(struct rb_root *root, struct vm_area_struct *ig= nore) -{ - struct rb_node *nd; - - for (nd =3D rb_first(root); nd; nd =3D rb_next(nd)) { - struct vm_area_struct *vma; - vma =3D rb_entry(nd, struct vm_area_struct, vm_rb); - VM_BUG_ON_VMA(vma !=3D ignore && - vma->rb_subtree_gap !=3D vma_compute_subtree_gap(vma), - vma); - } -} =20 static void validate_mm(struct mm_struct *mm) { @@ -460,7 +365,10 @@ static void validate_mm(struct mm_struct *mm) unsigned long highest_address =3D 0; struct vm_area_struct *vma =3D mm->mmap; =20 + validate_mm_mt(mm); + while (vma) { +#ifdef CONFIG_DEBUG_VM_RB struct anon_vma *anon_vma =3D vma->anon_vma; struct anon_vma_chain *avc; =20 @@ -470,6 +378,7 @@ static void validate_mm(struct mm_struct *mm) anon_vma_interval_tree_verify(avc); anon_vma_unlock_read(anon_vma); } +#endif =20 highest_address =3D vm_end_gap(vma); vma =3D vma->vm_next; @@ -484,80 +393,13 @@ static void validate_mm(struct mm_struct *mm) mm->highest_vm_end, highest_address); bug =3D 1; } - i =3D browse_rb(mm); - if (i !=3D mm->map_count) { - if (i !=3D -1) - pr_emerg("map_count %d rb %d\n", mm->map_count, i); - bug =3D 1; - } VM_BUG_ON_MM(bug, mm); } -#else -#define validate_mm_rb(root, ignore) do { } while (0) + +#else /* !CONFIG_DEBUG_MAPLE_TREE */ #define validate_mm_mt(root) do { } while (0) #define validate_mm(mm) do { } while (0) -#endif - -RB_DECLARE_CALLBACKS_MAX(static, vma_gap_callbacks, - struct vm_area_struct, vm_rb, - unsigned long, rb_subtree_gap, vma_compute_gap) - -/* - * Update augmented rbtree rb_subtree_gap values after vma->vm_start or - * vma->vm_prev->vm_end values changed, without modifying the vma's positi= on - * in the rbtree. - */ -static void vma_gap_update(struct vm_area_struct *vma) -{ - /* - * As it turns out, RB_DECLARE_CALLBACKS_MAX() already created - * a callback function that does exactly what we want. - */ - vma_gap_callbacks_propagate(&vma->vm_rb, NULL); -} - -static inline void vma_rb_insert(struct vm_area_struct *vma, - struct rb_root *root) -{ - /* All rb_subtree_gap values must be consistent prior to insertion */ - validate_mm_rb(root, NULL); - - rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); -} - -static void __vma_rb_erase(struct vm_area_struct *vma, struct rb_root *roo= t) -{ - /* - * Note rb_erase_augmented is a fairly large inline function, - * so make sure we instantiate it only once with our desired - * augmented rbtree callbacks. - */ - rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks); -} - -static __always_inline void vma_rb_erase_ignore(struct vm_area_struct *vma= , - struct rb_root *root, - struct vm_area_struct *ignore) -{ - /* - * All rb_subtree_gap values must be consistent prior to erase, - * with the possible exception of - * - * a. the "next" vma being erased if next->vm_start was reduced in - * __vma_adjust() -> __vma_unlink() - * b. the vma being erased in detach_vmas_to_be_unmapped() -> - * vma_rb_erase() - */ - validate_mm_rb(root, ignore); - - __vma_rb_erase(vma, root); -} - -static __always_inline void vma_rb_erase(struct vm_area_struct *vma, - struct rb_root *root) -{ - vma_rb_erase_ignore(vma, root, vma); -} +#endif /* CONFIG_DEBUG_MAPLE_TREE */ =20 /* * vma has some anon_vma assigned, and is already inserted on that @@ -591,39 +433,26 @@ anon_vma_interval_tree_post_update_vma(struct vm_area= _struct *vma) anon_vma_interval_tree_insert(avc, &avc->anon_vma->rb_root); } =20 -static int find_vma_links(struct mm_struct *mm, unsigned long addr, - unsigned long end, struct vm_area_struct **pprev, - struct rb_node ***rb_link, struct rb_node **rb_parent) +/* + * range_has_overlap() - Check the @start - @end range for overlapping VMA= s and + * sets up a pointer to the previous VMA + * @mm: the mm struct + * @start: the start address of the range + * @end: the end address of the range + * @pprev: the pointer to the pointer of the previous VMA + * + * Returns: True if there is an overlapping VMA, false otherwise + */ +static inline +bool range_has_overlap(struct mm_struct *mm, unsigned long start, + unsigned long end, struct vm_area_struct **pprev) { - struct rb_node **__rb_link, *__rb_parent, *rb_prev; + struct vm_area_struct *existing; =20 - mmap_assert_locked(mm); - __rb_link =3D &mm->mm_rb.rb_node; - rb_prev =3D __rb_parent =3D NULL; - - while (*__rb_link) { - struct vm_area_struct *vma_tmp; - - __rb_parent =3D *__rb_link; - vma_tmp =3D rb_entry(__rb_parent, struct vm_area_struct, vm_rb); - - if (vma_tmp->vm_end > addr) { - /* Fail if an existing vma overlaps the area */ - if (vma_tmp->vm_start < end) - return -ENOMEM; - __rb_link =3D &__rb_parent->rb_left; - } else { - rb_prev =3D __rb_parent; - __rb_link =3D &__rb_parent->rb_right; - } - } - - *pprev =3D NULL; - if (rb_prev) - *pprev =3D rb_entry(rb_prev, struct vm_area_struct, vm_rb); - *rb_link =3D __rb_link; - *rb_parent =3D __rb_parent; - return 0; + MA_STATE(mas, &mm->mm_mt, start, start); + existing =3D mas_find(&mas, end - 1); + *pprev =3D mas_prev(&mas, 0); + return existing ? true : false; } =20 /* @@ -650,8 +479,6 @@ static inline struct vm_area_struct *__vma_next(struct = mm_struct *mm, * @start: The start of the range. * @len: The length of the range. * @pprev: pointer to the pointer that will be set to previous vm_area_str= uct - * @rb_link: the rb_node - * @rb_parent: the parent rb_node * * Find all the vm_area_struct that overlap from @start to * @end and munmap them. Set @pprev to the previous vm_area_struct. @@ -660,14 +487,11 @@ static inline struct vm_area_struct *__vma_next(struc= t mm_struct *mm, */ static inline int munmap_vma_range(struct mm_struct *mm, unsigned long start, unsigned long = len, - struct vm_area_struct **pprev, struct rb_node ***link, - struct rb_node **parent, struct list_head *uf) + struct vm_area_struct **pprev, struct list_head *uf) { - - while (find_vma_links(mm, start, start + len, pprev, link, parent)) + while (range_has_overlap(mm, start, start + len, pprev)) if (do_munmap(mm, start, len, uf)) return -ENOMEM; - return 0; } =20 @@ -688,30 +512,6 @@ static unsigned long count_vma_pages_range(struct mm_s= truct *mm, return nr_pages; } =20 -void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma, - struct rb_node **rb_link, struct rb_node *rb_parent) -{ - /* Update tracking information for the gap following the new vma. */ - if (vma->vm_next) - vma_gap_update(vma->vm_next); - else - mm->highest_vm_end =3D vm_end_gap(vma); - - /* - * vma->vm_prev wasn't known when we followed the rbtree to find the - * correct insertion point for that vma. As a result, we could not - * update the vma vm_rb parents rb_subtree_gap values on the way down. - * So, we first insert the vma with a zero rb_subtree_gap value - * (to be consistent with what we did on the way down), and then - * immediately update the gap to the correct value. Finally we - * rebalance the rbtree after all augmented values have been set. - */ - rb_link_node(&vma->vm_rb, rb_parent, rb_link); - vma->rb_subtree_gap =3D 0; - vma_gap_update(vma); - vma_rb_insert(vma, &mm->mm_rb); -} - static void __vma_link_file(struct vm_area_struct *vma) { struct file *file; @@ -759,19 +559,8 @@ void vma_store(struct mm_struct *mm, struct vm_area_st= ruct *vma) vma_mas_store(vma, &mas); } =20 -static void -__vma_link(struct mm_struct *mm, struct vm_area_struct *vma, - struct vm_area_struct *prev, struct rb_node **rb_link, - struct rb_node *rb_parent) -{ - vma_store(mm, vma); - __vma_link_list(mm, vma, prev); - __vma_link_rb(mm, vma, rb_link, rb_parent); -} - static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma, - struct vm_area_struct *prev, struct rb_node **rb_link, - struct rb_node *rb_parent) + struct vm_area_struct *prev) { struct address_space *mapping =3D NULL; =20 @@ -780,7 +569,8 @@ static void vma_link(struct mm_struct *mm, struct vm_ar= ea_struct *vma, i_mmap_lock_write(mapping); } =20 - __vma_link(mm, vma, prev, rb_link, rb_parent); + vma_store(mm, vma); + __vma_link_list(mm, vma, prev); __vma_link_file(vma); =20 if (mapping) @@ -792,30 +582,19 @@ static void vma_link(struct mm_struct *mm, struct vm_= area_struct *vma, =20 /* * Helper for vma_adjust() in the split_vma insert case: insert a vma into= the - * mm's list and rbtree. It has already been inserted into the interval t= ree. + * mm's list and the mm tree. It has already been inserted into the inter= val tree. */ static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct= *vma) { struct vm_area_struct *prev; - struct rb_node **rb_link, *rb_parent; + MA_STATE(mas, &mm->mm_mt, vma->vm_start, vma->vm_start); =20 - if (find_vma_links(mm, vma->vm_start, vma->vm_end, - &prev, &rb_link, &rb_parent)) - BUG(); - __vma_link(mm, vma, prev, rb_link, rb_parent); + prev =3D mas_prev(&mas, 0); + vma_store(mm, vma); + __vma_link_list(mm, vma, prev); mm->map_count++; } =20 -static __always_inline void __vma_unlink(struct mm_struct *mm, - struct vm_area_struct *vma, - struct vm_area_struct *ignore) -{ - vma_rb_erase_ignore(vma, &mm->mm_rb, ignore); - __vma_unlink_list(mm, vma); - /* Kill the cache */ - vmacache_invalidate(mm); -} - /* * We cannot adjust vm_start, vm_end, vm_pgoff fields of a vma that * is already present in an i_mmap tree without adjusting the tree. @@ -833,13 +612,10 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned= long start, struct rb_root_cached *root =3D NULL; struct anon_vma *anon_vma =3D NULL; struct file *file =3D vma->vm_file; - bool start_changed =3D false, end_changed =3D false; + bool vma_changed =3D false; long adjust_next =3D 0; int remove_next =3D 0; =20 - validate_mm(mm); - validate_mm_mt(mm); - if (next && !insert) { struct vm_area_struct *exporter =3D NULL, *importer =3D NULL; =20 @@ -965,21 +741,23 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned= long start, } =20 if (start !=3D vma->vm_start) { - unsigned long old_start =3D vma->vm_start; + if (vma->vm_start < start) + vma_mt_szero(mm, vma->vm_start, start); + else + vma_changed =3D true; vma->vm_start =3D start; - if (old_start < start) - vma_mt_szero(mm, old_start, start); - start_changed =3D true; } if (end !=3D vma->vm_end) { - unsigned long old_end =3D vma->vm_end; + if (vma->vm_end > end) + vma_mt_szero(mm, end, vma->vm_end); + else + vma_changed =3D true; vma->vm_end =3D end; - if (old_end > end) - vma_mt_szero(mm, end, old_end); - end_changed =3D true; + if (!next) + mm->highest_vm_end =3D vm_end_gap(vma); } =20 - if (end_changed || start_changed) + if (vma_changed) vma_store(mm, vma); =20 vma->vm_pgoff =3D pgoff; @@ -997,25 +775,9 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned = long start, } =20 if (remove_next) { - /* - * vma_merge has merged next into vma, and needs - * us to remove next before dropping the locks. - * Since we have expanded over this vma, the maple tree will - * have overwritten by storing the value - */ - if (remove_next !=3D 3) - __vma_unlink(mm, next, next); - else - /* - * vma is not before next if they've been - * swapped. - * - * pre-swap() next->vm_start was reduced so - * tell validate_mm_rb to ignore pre-swap() - * "next" (which is stored in post-swap() - * "vma"). - */ - __vma_unlink(mm, next, vma); + __vma_unlink_list(mm, next); + /* Kill the cache */ + vmacache_invalidate(mm); if (file) __remove_shared_vm_struct(next, file, mapping); } else if (insert) { @@ -1025,15 +787,6 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned= long start, * (it may either follow vma or precede it). */ __insert_vm_struct(mm, insert); - } else { - if (start_changed) - vma_gap_update(vma); - if (end_changed) { - if (!next) - mm->highest_vm_end =3D vm_end_gap(vma); - else if (!adjust_next) - vma_gap_update(next); - } } =20 if (anon_vma) { @@ -1091,10 +844,7 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned= long start, remove_next =3D 1; end =3D next->vm_end; goto again; - } - else if (next) - vma_gap_update(next); - else { + } else if (!next) { /* * If remove_next =3D=3D 2 we obviously can't * reach this path. @@ -1121,8 +871,6 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned = long start, uprobe_mmap(insert); =20 validate_mm(mm); - validate_mm_mt(mm); - return 0; } =20 @@ -1275,7 +1023,6 @@ struct vm_area_struct *vma_merge(struct mm_struct *mm= , struct vm_area_struct *area, *next; int err; =20 - validate_mm_mt(mm); /* * We later require that vma->vm_flags =3D=3D vm_flags, * so this tests vma->vm_flags & VM_SPECIAL, too. @@ -1351,7 +1098,6 @@ struct vm_area_struct *vma_merge(struct mm_struct *mm= , khugepaged_enter_vma_merge(area, vm_flags); return area; } - validate_mm_mt(mm); =20 return NULL; } @@ -1521,6 +1267,7 @@ unsigned long do_mmap(struct file *file, unsigned lon= g addr, vm_flags_t vm_flags; int pkey =3D 0; =20 + validate_mm(mm); *populate =3D 0; =20 if (!len) @@ -1830,10 +1577,8 @@ unsigned long mmap_region(struct file *file, unsigne= d long addr, struct mm_struct *mm =3D current->mm; struct vm_area_struct *vma, *prev, *merge; int error; - struct rb_node **rb_link, *rb_parent; unsigned long charged =3D 0; =20 - validate_mm_mt(mm); /* Check against address space limit. */ if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) { unsigned long nr_pages; @@ -1849,8 +1594,8 @@ unsigned long mmap_region(struct file *file, unsigned= long addr, return -ENOMEM; } =20 - /* Clear old maps, set up prev, rb_link, rb_parent, and uf */ - if (munmap_vma_range(mm, addr, len, &prev, &rb_link, &rb_parent, uf)) + /* Clear old maps, set up prev and uf */ + if (munmap_vma_range(mm, addr, len, &prev, uf)) return -ENOMEM; /* * Private writable mapping: check memory availability @@ -1948,7 +1693,7 @@ unsigned long mmap_region(struct file *file, unsigned= long addr, goto free_vma; } =20 - vma_link(mm, vma, prev, rb_link, rb_parent); + vma_link(mm, vma, prev); /* Once vma denies write, undo our temporary denial count */ unmap_writable: if (file && vm_flags & VM_SHARED) @@ -1981,7 +1726,6 @@ unsigned long mmap_region(struct file *file, unsigned= long addr, =20 vma_set_page_prot(vma); =20 - validate_mm_mt(mm); return addr; =20 unmap_and_free_vma: @@ -1998,7 +1742,6 @@ unsigned long mmap_region(struct file *file, unsigned= long addr, unacct_error: if (charged) vm_unacct_memory(charged); - validate_mm_mt(mm); return error; } =20 @@ -2348,7 +2091,6 @@ int expand_upwards(struct vm_area_struct *vma, unsign= ed long address) unsigned long gap_addr; int error =3D 0; =20 - validate_mm_mt(mm); if (!(vma->vm_flags & VM_GROWSUP)) return -EFAULT; =20 @@ -2395,15 +2137,13 @@ int expand_upwards(struct vm_area_struct *vma, unsi= gned long address) error =3D acct_stack_growth(vma, size, grow); if (!error) { /* - * vma_gap_update() doesn't support concurrent - * updates, but we only hold a shared mmap_lock - * lock here, so we need to protect against - * concurrent vma expansions. - * anon_vma_lock_write() doesn't help here, as - * we don't guarantee that all growable vmas - * in a mm share the same root anon vma. - * So, we reuse mm->page_table_lock to guard - * against concurrent vma expansions. + * We only hold a shared mmap_lock lock here, so + * we need to protect against concurrent vma + * expansions. anon_vma_lock_write() doesn't + * help here, as we don't guarantee that all + * growable vmas in a mm share the same root + * anon vma. So, we reuse mm->page_table_lock + * to guard against concurrent vma expansions. */ spin_lock(&mm->page_table_lock); if (vma->vm_flags & VM_LOCKED) @@ -2411,10 +2151,9 @@ int expand_upwards(struct vm_area_struct *vma, unsig= ned long address) vm_stat_account(mm, vma->vm_flags, grow); anon_vma_interval_tree_pre_update_vma(vma); vma->vm_end =3D address; + vma_store(mm, vma); anon_vma_interval_tree_post_update_vma(vma); - if (vma->vm_next) - vma_gap_update(vma->vm_next); - else + if (!vma->vm_next) mm->highest_vm_end =3D vm_end_gap(vma); spin_unlock(&mm->page_table_lock); =20 @@ -2424,8 +2163,6 @@ int expand_upwards(struct vm_area_struct *vma, unsign= ed long address) } anon_vma_unlock_write(vma->anon_vma); khugepaged_enter_vma_merge(vma, vma->vm_flags); - validate_mm(mm); - validate_mm_mt(mm); return error; } #endif /* CONFIG_STACK_GROWSUP || CONFIG_IA64 */ @@ -2433,14 +2170,12 @@ int expand_upwards(struct vm_area_struct *vma, unsi= gned long address) /* * vma is the first one with address < vma->vm_start. Have to extend vma. */ -int expand_downwards(struct vm_area_struct *vma, - unsigned long address) +int expand_downwards(struct vm_area_struct *vma, unsigned long address) { struct mm_struct *mm =3D vma->vm_mm; struct vm_area_struct *prev; int error =3D 0; =20 - validate_mm(mm); address &=3D PAGE_MASK; if (address < mmap_min_addr) return -EPERM; @@ -2477,15 +2212,13 @@ int expand_downwards(struct vm_area_struct *vma, error =3D acct_stack_growth(vma, size, grow); if (!error) { /* - * vma_gap_update() doesn't support concurrent - * updates, but we only hold a shared mmap_lock - * lock here, so we need to protect against - * concurrent vma expansions. - * anon_vma_lock_write() doesn't help here, as - * we don't guarantee that all growable vmas - * in a mm share the same root anon vma. - * So, we reuse mm->page_table_lock to guard - * against concurrent vma expansions. + * We only hold a shared mmap_lock lock here, so + * we need to protect against concurrent vma + * expansions. anon_vma_lock_write() doesn't + * help here, as we don't guarantee that all + * growable vmas in a mm share the same root + * anon vma. So, we reuse mm->page_table_lock + * to guard against concurrent vma expansions. */ spin_lock(&mm->page_table_lock); if (vma->vm_flags & VM_LOCKED) @@ -2497,7 +2230,6 @@ int expand_downwards(struct vm_area_struct *vma, /* Overwrite old entry in mtree. */ vma_store(mm, vma); anon_vma_interval_tree_post_update_vma(vma); - vma_gap_update(vma); spin_unlock(&mm->page_table_lock); =20 perf_event_mmap(vma); @@ -2506,7 +2238,6 @@ int expand_downwards(struct vm_area_struct *vma, } anon_vma_unlock_write(vma->anon_vma); khugepaged_enter_vma_merge(vma, vma->vm_flags); - validate_mm(mm); return error; } =20 @@ -2639,16 +2370,14 @@ detach_vmas_to_be_unmapped(struct mm_struct *mm, st= ruct vm_area_struct *vma, vma->vm_prev =3D NULL; vma_mt_szero(mm, vma->vm_start, end); do { - vma_rb_erase(vma, &mm->mm_rb); mm->map_count--; tail_vma =3D vma; vma =3D vma->vm_next; } while (vma && vma->vm_start < end); *insertion_point =3D vma; - if (vma) { + if (vma) vma->vm_prev =3D prev; - vma_gap_update(vma); - } else + else mm->highest_vm_end =3D prev ? vm_end_gap(prev) : 0; tail_vma->vm_next =3D NULL; =20 @@ -2781,11 +2510,7 @@ int __do_munmap(struct mm_struct *mm, unsigned long = start, size_t len, if (len =3D=3D 0) return -EINVAL; =20 - /* - * arch_unmap() might do unmaps itself. It must be called - * and finish any rbtree manipulation before this code - * runs and also starts to manipulate the rbtree. - */ + /* arch_unmap() might do unmaps itself. */ arch_unmap(mm, start, end); =20 /* Find the first overlapping VMA where start < vma->vm_end */ @@ -2793,6 +2518,11 @@ int __do_munmap(struct mm_struct *mm, unsigned long = start, size_t len, if (!vma) return 0; prev =3D vma->vm_prev; + /* we have start < vma->vm_end */ + + /* if it doesn't overlap, we have nothing.. */ + if (vma->vm_start >=3D end) + return 0; =20 /* * If we need to split any vma, do it now to save pain later. @@ -2848,7 +2578,7 @@ int __do_munmap(struct mm_struct *mm, unsigned long s= tart, size_t len, if (mm->locked_vm) unlock_range(vma, end); =20 - /* Detach vmas from rbtree */ + /* Detach vmas from the MM linked list and remove from the mm tree*/ if (!detach_vmas_to_be_unmapped(mm, vma, prev, end)) downgrade =3D false; =20 @@ -2992,11 +2722,11 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, st= art, unsigned long, size, * anonymous maps. eventually we may be able to do some * brk-specific accounting here. */ -static int do_brk_flags(unsigned long addr, unsigned long len, unsigned lo= ng flags, struct list_head *uf) +static int do_brk_flags(unsigned long addr, unsigned long len, + unsigned long flags, struct list_head *uf) { struct mm_struct *mm =3D current->mm; struct vm_area_struct *vma, *prev; - struct rb_node **rb_link, *rb_parent; pgoff_t pgoff =3D addr >> PAGE_SHIFT; int error; unsigned long mapped_addr; @@ -3015,8 +2745,8 @@ static int do_brk_flags(unsigned long addr, unsigned = long len, unsigned long fla if (error) return error; =20 - /* Clear old maps, set up prev, rb_link, rb_parent, and uf */ - if (munmap_vma_range(mm, addr, len, &prev, &rb_link, &rb_parent, uf)) + /* Clear old maps, set up prev and uf */ + if (munmap_vma_range(mm, addr, len, &prev, uf)) return -ENOMEM; =20 /* Check against address space limits *after* clearing old maps... */ @@ -3050,7 +2780,7 @@ static int do_brk_flags(unsigned long addr, unsigned = long len, unsigned long fla vma->vm_pgoff =3D pgoff; vma->vm_flags =3D flags; vma->vm_page_prot =3D vm_get_page_prot(flags); - vma_link(mm, vma, prev, rb_link, rb_parent); + vma_link(mm, vma, prev); out: perf_event_mmap(vma); mm->total_vm +=3D len >> PAGE_SHIFT; @@ -3177,26 +2907,10 @@ void exit_mmap(struct mm_struct *mm) int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma) { struct vm_area_struct *prev; - struct rb_node **rb_link, *rb_parent; - unsigned long start =3D vma->vm_start; - struct vm_area_struct *overlap =3D NULL; =20 - if (find_vma_links(mm, vma->vm_start, vma->vm_end, - &prev, &rb_link, &rb_parent)) + if (range_has_overlap(mm, vma->vm_start, vma->vm_end, &prev)) return -ENOMEM; =20 - overlap =3D mt_find(&mm->mm_mt, &start, vma->vm_end - 1); - if (overlap) { - - pr_err("Found vma ending at %lu\n", start - 1); - pr_err("vma : %lu =3D> %lu-%lu\n", (unsigned long)overlap, - overlap->vm_start, overlap->vm_end - 1); -#if defined(CONFIG_DEBUG_MAPLE_TREE) - mt_dump(&mm->mm_mt); -#endif - BUG(); - } - if ((vma->vm_flags & VM_ACCOUNT) && security_vm_enough_memory_mm(mm, vma_pages(vma))) return -ENOMEM; @@ -3218,7 +2932,7 @@ int insert_vm_struct(struct mm_struct *mm, struct vm_= area_struct *vma) vma->vm_pgoff =3D vma->vm_start >> PAGE_SHIFT; } =20 - vma_link(mm, vma, prev, rb_link, rb_parent); + vma_link(mm, vma, prev); return 0; } =20 @@ -3234,9 +2948,7 @@ struct vm_area_struct *copy_vma(struct vm_area_struct= **vmap, unsigned long vma_start =3D vma->vm_start; struct mm_struct *mm =3D vma->vm_mm; struct vm_area_struct *new_vma, *prev; - struct rb_node **rb_link, *rb_parent; bool faulted_in_anon_vma =3D true; - unsigned long index =3D addr; =20 validate_mm_mt(mm); /* @@ -3248,10 +2960,9 @@ struct vm_area_struct *copy_vma(struct vm_area_struc= t **vmap, faulted_in_anon_vma =3D false; } =20 - if (find_vma_links(mm, addr, addr + len, &prev, &rb_link, &rb_parent)) + if (range_has_overlap(mm, addr, addr + len, &prev)) return NULL; /* should never get here */ - if (mt_find(&mm->mm_mt, &index, addr+len - 1)) - BUG(); + new_vma =3D vma_merge(mm, prev, addr, addr + len, vma->vm_flags, vma->anon_vma, vma->vm_file, pgoff, vma_policy(vma), vma->vm_userfaultfd_ctx, vma_anon_name(vma)); @@ -3292,7 +3003,7 @@ struct vm_area_struct *copy_vma(struct vm_area_struct= **vmap, get_file(new_vma->vm_file); if (new_vma->vm_ops && new_vma->vm_ops->open) new_vma->vm_ops->open(new_vma); - vma_link(mm, new_vma, prev, rb_link, rb_parent); + vma_link(mm, new_vma, prev); *need_rmap_locks =3D false; } validate_mm_mt(mm); diff --git a/mm/nommu.c b/mm/nommu.c index 55a9e48a7a02..9b8c033ef997 100644 --- a/mm/nommu.c +++ b/mm/nommu.c @@ -551,9 +551,9 @@ static void put_nommu_region(struct vm_region *region) */ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma= ) { - struct vm_area_struct *pvma, *prev; struct address_space *mapping; - struct rb_node **p, *parent, *rb_prev; + struct vm_area_struct *prev; + MA_STATE(mas, &mm->mm_mt, vma->vm_start, vma->vm_end); =20 BUG_ON(!vma->vm_region); =20 @@ -571,42 +571,10 @@ static void add_vma_to_mm(struct mm_struct *mm, struc= t vm_area_struct *vma) i_mmap_unlock_write(mapping); } =20 + prev =3D mas_prev(&mas, 0); + mas_reset(&mas); /* add the VMA to the tree */ - parent =3D rb_prev =3D NULL; - p =3D &mm->mm_rb.rb_node; - while (*p) { - parent =3D *p; - pvma =3D rb_entry(parent, struct vm_area_struct, vm_rb); - - /* sort by: start addr, end addr, VMA struct addr in that order - * (the latter is necessary as we may get identical VMAs) */ - if (vma->vm_start < pvma->vm_start) - p =3D &(*p)->rb_left; - else if (vma->vm_start > pvma->vm_start) { - rb_prev =3D parent; - p =3D &(*p)->rb_right; - } else if (vma->vm_end < pvma->vm_end) - p =3D &(*p)->rb_left; - else if (vma->vm_end > pvma->vm_end) { - rb_prev =3D parent; - p =3D &(*p)->rb_right; - } else if (vma < pvma) - p =3D &(*p)->rb_left; - else if (vma > pvma) { - rb_prev =3D parent; - p =3D &(*p)->rb_right; - } else - BUG(); - } - - rb_link_node(&vma->vm_rb, parent, p); - rb_insert_color(&vma->vm_rb, &mm->mm_rb); - - /* add VMA to the VMA list also */ - prev =3D NULL; - if (rb_prev) - prev =3D rb_entry(rb_prev, struct vm_area_struct, vm_rb); - + vma_mas_store(vma, &mas); __vma_link_list(mm, vma, prev); } =20 @@ -619,6 +587,7 @@ static void delete_vma_from_mm(struct vm_area_struct *v= ma) struct address_space *mapping; struct mm_struct *mm =3D vma->vm_mm; struct task_struct *curr =3D current; + MA_STATE(mas, &vma->vm_mm->mm_mt, 0, 0); =20 mm->map_count--; for (i =3D 0; i < VMACACHE_SIZE; i++) { @@ -641,8 +610,7 @@ static void delete_vma_from_mm(struct vm_area_struct *v= ma) } =20 /* remove from the MM's tree and list */ - rb_erase(&vma->vm_rb, &mm->mm_rb); - + vma_mas_remove(vma, &mas); __vma_unlink_list(mm, vma); } =20 @@ -666,24 +634,19 @@ static void delete_vma(struct mm_struct *mm, struct v= m_area_struct *vma) struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) { struct vm_area_struct *vma; + MA_STATE(mas, &mm->mm_mt, addr, addr); =20 /* check the cache first */ vma =3D vmacache_find(mm, addr); if (likely(vma)) return vma; =20 - /* trawl the list (there may be multiple mappings in which addr - * resides) */ - for (vma =3D mm->mmap; vma; vma =3D vma->vm_next) { - if (vma->vm_start > addr) - return NULL; - if (vma->vm_end > addr) { - vmacache_update(addr, vma); - return vma; - } - } + vma =3D mas_walk(&mas); =20 - return NULL; + if (vma) + vmacache_update(addr, vma); + + return vma; } EXPORT_SYMBOL(find_vma); =20 @@ -715,26 +678,23 @@ static struct vm_area_struct *find_vma_exact(struct m= m_struct *mm, { struct vm_area_struct *vma; unsigned long end =3D addr + len; + MA_STATE(mas, &mm->mm_mt, addr, addr); =20 /* check the cache first */ vma =3D vmacache_find_exact(mm, addr, end); if (vma) return vma; =20 - /* trawl the list (there may be multiple mappings in which addr - * resides) */ - for (vma =3D mm->mmap; vma; vma =3D vma->vm_next) { - if (vma->vm_start < addr) - continue; - if (vma->vm_start > addr) - return NULL; - if (vma->vm_end =3D=3D end) { - vmacache_update(addr, vma); - return vma; - } - } + vma =3D mas_walk(&mas); + if (!vma) + return NULL; + if (vma->vm_start !=3D addr) + return NULL; + if (vma->vm_end !=3D end) + return NULL; =20 - return NULL; + vmacache_update(addr, vma); + return vma; } =20 /* @@ -1531,6 +1491,7 @@ void exit_mmap(struct mm_struct *mm) delete_vma(mm, vma); cond_resched(); } + __mt_destroy(&mm->mm_mt); } =20 int vm_brk(unsigned long addr, unsigned long len) diff --git a/mm/util.c b/mm/util.c index 7e43369064c8..fcad6c87f9a0 100644 --- a/mm/util.c +++ b/mm/util.c @@ -287,6 +287,8 @@ void __vma_link_list(struct mm_struct *mm, struct vm_ar= ea_struct *vma, vma->vm_next =3D next; if (next) next->vm_prev =3D vma; + else + mm->highest_vm_end =3D vm_end_gap(vma); } =20 void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma) @@ -299,8 +301,14 @@ void __vma_unlink_list(struct mm_struct *mm, struct vm= _area_struct *vma) prev->vm_next =3D next; else mm->mmap =3D next; - if (next) + if (next) { next->vm_prev =3D prev; + } else { + if (prev) + mm->highest_vm_end =3D vm_end_gap(prev); + else + mm->highest_vm_end =3D 0; + } } =20 /* Check if the vma is being used as a stack by this task */ --=20 2.34.1