From patchwork Tue Sep 6 19:48:47 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: 12968057 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 2F0B6ECAAA1 for ; Tue, 6 Sep 2022 19:48:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B88B06B0078; Tue, 6 Sep 2022 15:48:58 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B130D6B007B; Tue, 6 Sep 2022 15:48:58 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8358F8D0001; Tue, 6 Sep 2022 15:48:58 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 7051A6B0078 for ; Tue, 6 Sep 2022 15:48:58 -0400 (EDT) Received: from smtpin11.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 4C2048084F for ; Tue, 6 Sep 2022 19:48:58 +0000 (UTC) X-FDA: 79882698756.11.BE444AE Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf08.hostedemail.com (Postfix) with ESMTP id B0EF416007E for ; Tue, 6 Sep 2022 19:48:57 +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 286Id90a024660; Tue, 6 Sep 2022 19:48:56 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-2022-7-12; bh=1kNb/4PZSO1OENQH4kGsfc+HhKZTvRmam3cOhRQymGI=; b=JW0Y46thckma2oK/Mkt58X4oaxsmeDmOxfRjoQHIwwJbKHzrVK4rqdT5kBVDQzi4+I7c E1FVWAOMCqcM426gjLqTm3kGQH1HkotyFCbaP6UEHMbEGTQpt/BjvV+rJnrpoSnCWt/Q OG4XuOA/JBR3veMxnD11fCm3YGIM9cp0OR4aCUBWy/ZnBSaHyVFPj2uO9G5ueMjINYQI 6HAekXFWTiAvQ7CLGg6J7RYDOn+HvSTzfDzf6LtugFHVrgpMj/nRuxP9XtSbotMIwWon M83dF6ykUCmXwxUM7qTIuu7aVhQazVMg0/KaIQDMdPn7vHnhU5YUVsFAu32IJY84K3ub Zw== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3jbxtaet5e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 06 Sep 2022 19:48:56 +0000 Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.5/8.17.1.5) with ESMTP id 286H8KXO023727; Tue, 6 Sep 2022 19:48:54 GMT Received: from nam12-dm6-obe.outbound.protection.outlook.com (mail-dm6nam12lp2174.outbound.protection.outlook.com [104.47.59.174]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3jbwc9kr9w-6 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 06 Sep 2022 19:48:54 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=P09A1TF1jdzf8iQA9xRmC/3cCTmun+zTgP39a2XVDLjjMQmcDFqJi075R3lY3t390+IOQXsJOz1zGvV+boFm9uxE6AAJi4Lgx1177Ldtr56knd3bgLFGcVNJSF6b+Om5kIQcIlAqsfQSIOHghIIUnhF0v8s9GM+VdSZEU8HPqT+0IgS8cAkqGpjcHL+AgwT1gmeiI0ZQ+GIG7yZBWTjFyPPDHgBWzVDei5jZjeXvLcr8409dqt3AMM2r5afEOJa7kovvBia0L9N6YyuHg/a/OBv8gQnvqnQem2c97uPjtewK+qH8wooekFQ0WEN8fJato0KVtdP12jL1O592xswjvQ== 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=1kNb/4PZSO1OENQH4kGsfc+HhKZTvRmam3cOhRQymGI=; b=QGfA82rUqqYqwKflM1i5bgzeAbiOPHSLFIoRxy5E+Gzvn4aeftjSTaB71TBDZOxZZE67pA77Oi8cRQI/OlXLBU6K2CKSK/XZjH5FNFW0DuGi8a/ggJPUg7yGO4KNTIVuzWsLWewCe0h59jVN9gv8xgVyrGdddic52goRGSWk7fSzpO17m3sYtqtW5nbDWQNWSIXSl15e5zajFuzjny95JJI5IL1/MkkTxgi63nGoOTEJbLLWMmQqQEju42KO2K2YtjyFwPogyMN4IYx7Hi2WYQxXzsV9wc+rZ7sXBo27vZvwoZm/HDflUZNAQQt4nOPCZSE8b+80a/NR8/f3PcEtYA== 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=1kNb/4PZSO1OENQH4kGsfc+HhKZTvRmam3cOhRQymGI=; b=VKvqhCumxj0kNzZfKmm9jyYoJnZK6DxKiORWwYZY6nPMBnltiB4SX+16RzWAzhzX5qFCa1B2Vf3keEr6ONTpkT0RR4VJ/CukTdemZk4ptVmIPn4Nc7Nun8PzbfpztyBLzzDxuaWGjTcurjMWUbTxloLDG62CQazpWCF6rWaWCLc= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by DM4PR10MB6183.namprd10.prod.outlook.com (2603:10b6:8:8b::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5588.10; Tue, 6 Sep 2022 19:48:53 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::a420:3107:436d:d223]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::a420:3107:436d:d223%5]) with mapi id 15.20.5588.018; Tue, 6 Sep 2022 19:48:53 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton CC: Liam Howlett Subject: [PATCH v14 13/70] mm/mmap: use maple tree for unmapped_area{_topdown} Thread-Topic: [PATCH v14 13/70] mm/mmap: use maple tree for unmapped_area{_topdown} Thread-Index: AQHYwimtLbyER+H6PEKtTt7v4ylJSg== Date: Tue, 6 Sep 2022 19:48:47 +0000 Message-ID: <20220906194824.2110408-14-Liam.Howlett@oracle.com> References: <20220906194824.2110408-1-Liam.Howlett@oracle.com> In-Reply-To: <20220906194824.2110408-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: 2420fa9e-3717-4fa6-6491-08da9040d3d4 x-ms-traffictypediagnostic: DM4PR10MB6183:EE_ x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: T+eJnihIb9a/hlL660LAqsP9z9gExhTz+lnWhNg81GOTgGKQZ9a7NDpxoh2Wt2HqMWZzXI8VicHSwrXZNsU0xXyzC7PJOeTNb+nkD6xeTDrZqEioKGgjb3ovANr8nGwWBKC3FXnwL66Mf8t/b6NNLcD4KrYfkJT7AFeBPAfsVe+HqEOqRVmzBzXbaSusuHYrhV7pnSiMZN/+ZUA3BywBYALQtcybRbQYyz/aq5Z+tcjs7Tae6X72wfnYI1EvBYoO+vhqoKutZ8A/FWxMHJESO0plgVMUHm7DyxYxbbDH4onBp0l8cyMFew9GTl97tKQHcIc0Drv+rklR4oJmzRoIjPln6CBWrnlqwmxrpqWkiPp+G03iuxpgegLugenRE4U3y48XeMbYbXkp29iPTAq7uX5KcveSh4oJCwY8hFD6Q4QTFFN1O44VKWzWWeiBiTLMAhat2vjEXafmuPYFb3x0phMVRJV9dlkZhN+mEkwgXiFjS+4H7gNld9YmXkfrLvK5aoN/ymT7fcu/kpvKz/x89m4fvNk9wKiebNn6+AV6m60Gtq2ZxyhiZoBDaJp8ilYW634zw2IC7z9ydXjaVmRF2zXElTlvgioUkoXIJHrPqf3oy0JzeiGijsH3uGiG3VXkRuSukgjt/cNBTqyTacoz+2bbueD/Mp/Rao+sUTWmfPzMUdVZn16MB5Lrgzx9m6Xzga5GNVZFKRCPCMQ0lZRNFN/HazhxaXI0rewfw6rhyAl8uY42D1ZXzj4OK5sDsPe3FwLEkXboVAxwyZlxm1vePw== 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)(39860400002)(366004)(376002)(396003)(346002)(136003)(66556008)(38100700002)(122000001)(8936002)(5660300002)(76116006)(66946007)(66446008)(66476007)(2906002)(83380400001)(8676002)(91956017)(36756003)(2616005)(186003)(107886003)(86362001)(1076003)(110136005)(44832011)(71200400001)(6666004)(38070700005)(26005)(64756008)(41300700001)(6506007)(6512007)(6486002)(316002)(478600001)(4326008);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?mUhIGx8VLSXbqCCeMBc8z+q?= =?iso-8859-1?q?FcGQeTaAUGDrLBgvXzrlJtYwjCxcaF/IAkUtJGoJQMBp19ptnkT3dttVevpR?= =?iso-8859-1?q?XlBL8yUXHMF8EshEUxLZPteWLXBOIKTdDg1vmuM8xK7V41LsdD7tGlIPsFYm?= =?iso-8859-1?q?76tQdKpH4pz8BLg8jRniUMGFsWcqaGOLB5gheO+6a4fKvis3KdYhB8oetwlz?= =?iso-8859-1?q?q8xndCooCx+Ym6uJDQYTSSB+mcSASy4J0hIAg9HbckqDiRfBRDmSWp2p4Vnv?= =?iso-8859-1?q?aEL2fcL2WxkxFvOE+1D2tSM+KSI8TELH7tH8TRG16lE5tEwabP0QUXmnn/KT?= =?iso-8859-1?q?4VLgTjJANCLhW94nlclM0AMrqe4qK9db+OEKM27K0xrNeTjEMqe1jyH4bqkd?= =?iso-8859-1?q?1h4E7wfDryjPT7OgXp5mCdklVB/JGqeYMAZn0gqgWnZF+QFHI/lofCsUjKcg?= =?iso-8859-1?q?DNKhs/P2aWysNFt1e1qXQt20E9AWhl5AwODV5Su4cwBybkRTq1brKTYHUJaQ?= =?iso-8859-1?q?mAAkhctDkNvCliWUuEzH8hiC0xv0Su93pkHZTRtTulwisP0x7i7mvk/ZD7lW?= =?iso-8859-1?q?QiDzZbvsQO+4R5w1uGpX3CBAPiCTqlSTbg8iSm/71Ag2Hq5zGViOle+5ouS7?= =?iso-8859-1?q?7jb1Y4tKu9eP65NqkPrc3SakiJf6nmKFXZ3yp2e6H9MdlOSz9lBh6BsmyyOn?= =?iso-8859-1?q?M1icHH0tAwB0cnJstjJF1GkLOMytMzCKqI4l8pImP+/MuL9FTVmtYjqRbxUn?= =?iso-8859-1?q?/q9NIq8C8vvFaMqnI5ZxxNSiMXgVhNQPXjjWdJO+SvPia4QKf5Fi4O+WJ9VC?= =?iso-8859-1?q?Pp8VEwjugRIHBvZDac1pNklRA3xUwGTGB/NAqyeAPtTLft+pFWSsVASwChPJ?= =?iso-8859-1?q?16JpPL4IclX1pN5e8nVDVoCcEjYceot76Wna+O8ECnaT6FVpknepPecEnjV/?= =?iso-8859-1?q?qxGy8Brf/U5nQ2DyRjZdaEX+WxnqociP8WxVXjcKF7lA3IDobcxRQOBTENRu?= =?iso-8859-1?q?CD3C5xhRsSpX4e7ZA2MMImfRIX03OS/rPiGOP6gJOZvCfLoiXoQQTySeYuog?= =?iso-8859-1?q?OMhiNAdkATq1xyShrsWHhWJSAV09KsZSoXqZbUmgcIinpHanqgoXhAuKrY+b?= =?iso-8859-1?q?CbwczdvmWWEEysi4+0MVL+VLTjHth2Xy7pmUxtqOoc0rPXaWbnYJruQt/vYZ?= =?iso-8859-1?q?HDikX3u/DxUPSzuRjasvrObuoL8invNXINPW8yH5qPpD+3o0pvU1x8bjeQ5u?= =?iso-8859-1?q?Ac7cS6M+A/ABi0LqracqBJ1edA5PyozVdSW5AHBuV2i+yW4N9zCJE2QCAKXX?= =?iso-8859-1?q?fnK4wxPiyhJvPvqk1MPgC1POB/qnHo9d1xk7TJ7wAUiGyITKrWgn1Bk5fKv3?= =?iso-8859-1?q?/AbQxltwpK00wNtNbtRoKPInWZpGiCjCQNkqRULjntXPiDVH2ICiMrt8i14b?= =?iso-8859-1?q?hgOEKexmOXiu6RF49+iTPf+N1kEd5+ZXm0lstgFqdS/xYn2KhRHslmYjYbeI?= =?iso-8859-1?q?akaLKueLCvi5sstQxieVceCqTgz8w3boPLRGJpYrTYrKDGHx1bUZPBS0jcNX?= =?iso-8859-1?q?hsxU4NrwATlyU1AtIkY06DrQpEODM+zhXvsgqnOIUaDE6XrrRLu+DIHbysCm?= =?iso-8859-1?q?H9mPetw2IxNTcB+pC9SPmE8+qv2jV0BVGbon1ow=3D=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: 2420fa9e-3717-4fa6-6491-08da9040d3d4 X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Sep 2022 19:48:47.5694 (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: 3pKLCE08GwEPd9l7c2mSzUnCTLWQRXkymuBW75WCrpbcM05hKObDzLXItzxy1hwzY/gCum22BFtH48D1d5HG+A== X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM4PR10MB6183 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.895,Hydra:6.0.528,FMLib:17.11.122.1 definitions=2022-09-06_09,2022-09-06_02,2022-06-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 mlxscore=0 adultscore=0 malwarescore=0 mlxlogscore=999 bulkscore=0 suspectscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2207270000 definitions=main-2209060091 X-Proofpoint-ORIG-GUID: RpUFAyS5ejvRINjh3sv-00JbwTSFaO-3 X-Proofpoint-GUID: RpUFAyS5ejvRINjh3sv-00JbwTSFaO-3 ARC-Authentication-Results: i=2; imf08.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2022-7-12 header.b=JW0Y46th; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=VKvqhCum; spf=pass (imf08.hostedemail.com: domain of liam.howlett@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1"); dmarc=pass (policy=none) header.from=oracle.com ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1662493737; a=rsa-sha256; cv=pass; b=fCld73zDlLIHmcf8Nun+EC/wIhls80SzlPvVZz5nfYOgGefKIKRKo7bxQLNPAx9yTeQGPt fydvY8yQaBts0nx88Y3FDFgN6ugwo4vHUmbkdj0toiLfrDx5RwKQcDbSU0ja+83h57SQN1 +QaTl2zsq+sfcFVe2/Ek6t4DDVgLwBc= ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1662493737; 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=1kNb/4PZSO1OENQH4kGsfc+HhKZTvRmam3cOhRQymGI=; b=N5CJwhCT0AYEbdaVhdzwueKxFQ9fffeOnhhlfLg3FdKX1xTC7ccp/3UI8jfcg3SJbrmYjA yBZCaxjmHkDGx88zfMllbsR9aNRcWsaqGFHKZ/0FDRjeWiZamSZpABFgnK61g0wK3s9Y1d Z5iLFP81HCd4qx+5j4BkDRXB4xZlAI4= X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: B0EF416007E X-Rspam-User: Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2022-7-12 header.b=JW0Y46th; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=VKvqhCum; spf=pass (imf08.hostedemail.com: domain of liam.howlett@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1"); dmarc=pass (policy=none) header.from=oracle.com X-Stat-Signature: qobx14t5fw7xw31fqomib9ffttpampgi X-HE-Tag: 1662493737-137898 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: From: "Liam R. Howlett" The maple tree code was added to find the unmapped area in a previous commit and was checked against what the rbtree returned, but the actual result was never used. Start using the maple tree implementation and remove the rbtree code. Add kernel documentation comment for these functions. Signed-off-by: Liam R. Howlett --- mm/mmap.c | 255 ++++++++---------------------------------------------- 1 file changed, 34 insertions(+), 221 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index 948264cd39cd..68ee2958c0be 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2013,250 +2013,63 @@ unsigned long mmap_region(struct file *file, unsigned long addr, return error; } +/** + * unmapped_area() - Find an area between the low_limit and the high_limit with + * the correct alignment and offset, all from @info. Note: current->mm is used + * for the search. + * + * @info: The unmapped area information including the range (low_limit - + * hight_limit), the alignment offset and mask. + * + * Return: A memory address or -ENOMEM. + */ static unsigned long unmapped_area(struct vm_unmapped_area_info *info) { - /* - * We implement the search by looking for an rbtree node that - * immediately follows a suitable gap. That is, - * - gap_start = vma->vm_prev->vm_end <= info->high_limit - length; - * - gap_end = vma->vm_start >= info->low_limit + length; - * - gap_end - gap_start >= length - */ + unsigned long length, gap; - struct mm_struct *mm = current->mm; - struct vm_area_struct *vma; - unsigned long length, low_limit, high_limit, gap_start, gap_end; - unsigned long gap; - MA_STATE(mas, &mm->mm_mt, 0, 0); + MA_STATE(mas, ¤t->mm->mm_mt, 0, 0); /* Adjust search length to account for worst case alignment overhead */ length = info->length + info->align_mask; if (length < info->length) return -ENOMEM; - mas_empty_area(&mas, info->low_limit, info->high_limit - 1, - length); - gap = mas.index; - gap += (info->align_offset - gap) & info->align_mask; - - /* Adjust search limits by the desired length */ - if (info->high_limit < length) + if (mas_empty_area(&mas, info->low_limit, info->high_limit - 1, + length)) return -ENOMEM; - high_limit = info->high_limit - length; - if (info->low_limit > high_limit) - return -ENOMEM; - low_limit = info->low_limit + length; - - /* Check if rbtree root looks promising */ - if (RB_EMPTY_ROOT(&mm->mm_rb)) - goto check_highest; - vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb); - if (vma->rb_subtree_gap < length) - goto check_highest; - - while (true) { - /* Visit left subtree if it looks promising */ - gap_end = vm_start_gap(vma); - if (gap_end >= low_limit && vma->vm_rb.rb_left) { - struct vm_area_struct *left = - rb_entry(vma->vm_rb.rb_left, - struct vm_area_struct, vm_rb); - if (left->rb_subtree_gap >= length) { - vma = left; - continue; - } - } - - gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0; -check_current: - /* Check if current node has a suitable gap */ - if (gap_start > high_limit) - return -ENOMEM; - if (gap_end >= low_limit && - gap_end > gap_start && gap_end - gap_start >= length) - goto found; - - /* Visit right subtree if it looks promising */ - if (vma->vm_rb.rb_right) { - struct vm_area_struct *right = - rb_entry(vma->vm_rb.rb_right, - struct vm_area_struct, vm_rb); - if (right->rb_subtree_gap >= length) { - vma = right; - continue; - } - } - - /* Go back up the rbtree to find next candidate node */ - while (true) { - struct rb_node *prev = &vma->vm_rb; - if (!rb_parent(prev)) - goto check_highest; - vma = rb_entry(rb_parent(prev), - struct vm_area_struct, vm_rb); - if (prev == vma->vm_rb.rb_left) { - gap_start = vm_end_gap(vma->vm_prev); - gap_end = vm_start_gap(vma); - goto check_current; - } - } - } - -check_highest: - /* Check highest gap, which does not precede any rbtree node */ - gap_start = mm->highest_vm_end; - gap_end = ULONG_MAX; /* Only for VM_BUG_ON below */ - if (gap_start > high_limit) - return -ENOMEM; - -found: - /* We found a suitable gap. Clip it with the original low_limit. */ - if (gap_start < info->low_limit) - gap_start = info->low_limit; - - /* Adjust gap address to the desired alignment */ - gap_start += (info->align_offset - gap_start) & info->align_mask; - - VM_BUG_ON(gap_start + info->length > info->high_limit); - VM_BUG_ON(gap_start + info->length > gap_end); - - VM_BUG_ON(gap != gap_start); - return gap_start; + gap = mas.index; + gap += (info->align_offset - gap) & info->align_mask; + return gap; } +/** + * unmapped_area_topdown() - Find an area between the low_limit and the + * high_limit with * the correct alignment and offset at the highest available + * address, all from @info. Note: current->mm is used for the search. + * + * @info: The unmapped area information including the range (low_limit - + * hight_limit), the alignment offset and mask. + * + * Return: A memory address or -ENOMEM. + */ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info) { - struct mm_struct *mm = current->mm; - struct vm_area_struct *vma = NULL; - unsigned long length, low_limit, high_limit, gap_start, gap_end; - unsigned long gap; - - MA_STATE(mas, &mm->mm_mt, 0, 0); - validate_mm_mt(mm); + unsigned long length, gap; + MA_STATE(mas, ¤t->mm->mm_mt, 0, 0); /* Adjust search length to account for worst case alignment overhead */ length = info->length + info->align_mask; if (length < info->length) return -ENOMEM; - mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1, - length); - gap = mas.last + 1 - info->length; - gap -= (gap - info->align_offset) & info->align_mask; - - /* - * Adjust search limits by the desired length. - * See implementation comment at top of unmapped_area(). - */ - gap_end = info->high_limit; - if (gap_end < length) - return -ENOMEM; - high_limit = gap_end - length; - - if (info->low_limit > high_limit) + if (mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1, + length)) return -ENOMEM; - low_limit = info->low_limit + length; - /* Check highest gap, which does not precede any rbtree node */ - gap_start = mm->highest_vm_end; - if (gap_start <= high_limit) - goto found_highest; - - /* Check if rbtree root looks promising */ - if (RB_EMPTY_ROOT(&mm->mm_rb)) - return -ENOMEM; - vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb); - if (vma->rb_subtree_gap < length) - return -ENOMEM; - - while (true) { - /* Visit right subtree if it looks promising */ - gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0; - if (gap_start <= high_limit && vma->vm_rb.rb_right) { - struct vm_area_struct *right = - rb_entry(vma->vm_rb.rb_right, - struct vm_area_struct, vm_rb); - if (right->rb_subtree_gap >= length) { - vma = right; - continue; - } - } - -check_current: - /* Check if current node has a suitable gap */ - gap_end = vm_start_gap(vma); - if (gap_end < low_limit) - return -ENOMEM; - if (gap_start <= high_limit && - gap_end > gap_start && gap_end - gap_start >= length) - goto found; - - /* Visit left subtree if it looks promising */ - if (vma->vm_rb.rb_left) { - struct vm_area_struct *left = - rb_entry(vma->vm_rb.rb_left, - struct vm_area_struct, vm_rb); - if (left->rb_subtree_gap >= length) { - vma = left; - continue; - } - } - - /* Go back up the rbtree to find next candidate node */ - while (true) { - struct rb_node *prev = &vma->vm_rb; - if (!rb_parent(prev)) - return -ENOMEM; - vma = rb_entry(rb_parent(prev), - struct vm_area_struct, vm_rb); - if (prev == vma->vm_rb.rb_right) { - gap_start = vma->vm_prev ? - vm_end_gap(vma->vm_prev) : 0; - goto check_current; - } - } - } - -found: - /* We found a suitable gap. Clip it with the original high_limit. */ - if (gap_end > info->high_limit) - gap_end = info->high_limit; - -found_highest: - /* Compute highest gap address at the desired alignment */ - gap_end -= info->length; - gap_end -= (gap_end - info->align_offset) & info->align_mask; - - VM_BUG_ON(gap_end < info->low_limit); - VM_BUG_ON(gap_end < gap_start); - - if (gap != gap_end) { - pr_err("%s: %p Gap was found: mt %lu gap_end %lu\n", __func__, - mm, gap, gap_end); - pr_err("window was %lu - %lu size %lu\n", info->high_limit, - info->low_limit, length); - pr_err("mas.min %lu max %lu mas.last %lu\n", mas.min, mas.max, - mas.last); - pr_err("mas.index %lu align mask %lu offset %lu\n", mas.index, - info->align_mask, info->align_offset); - pr_err("rb_find_vma find on %lu => %p (%p)\n", mas.index, - find_vma(mm, mas.index), vma); -#if defined(CONFIG_DEBUG_VM_MAPLE_TREE) - mt_dump(&mm->mm_mt); -#endif - { - struct vm_area_struct *dv = mm->mmap; - - while (dv) { - pr_err("vma %p %lu-%lu\n", dv, dv->vm_start, dv->vm_end); - dv = dv->vm_next; - } - } - VM_BUG_ON(gap != gap_end); - } - - return gap_end; + gap = mas.last + 1 - info->length; + gap -= (gap - info->align_offset) & info->align_mask; + return gap; } /*