From patchwork Wed Apr 28 15:36:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 12229463 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,PDS_BAD_THREAD_QP_64,SPF_HELO_NONE,SPF_PASS, USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7F4B5C43460 for ; Wed, 28 Apr 2021 15:37:36 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id D946E61434 for ; Wed, 28 Apr 2021 15:37:35 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org D946E61434 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=oracle.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 85B0A8D0010; Wed, 28 Apr 2021 11:36:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 47BAC8D000A; Wed, 28 Apr 2021 11:36:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 692218D000B; Wed, 28 Apr 2021 11:36:54 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0199.hostedemail.com [216.40.44.199]) by kanga.kvack.org (Postfix) with ESMTP id 4236F8D000D for ; Wed, 28 Apr 2021 11:36:52 -0400 (EDT) Received: from smtpin38.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id 06FEF180AD820 for ; Wed, 28 Apr 2021 15:36:52 +0000 (UTC) X-FDA: 78082178664.38.D9AFF0C Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf22.hostedemail.com (Postfix) with ESMTP id 97CDBC0007E3 for ; Wed, 28 Apr 2021 15:36:44 +0000 (UTC) Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.16.0.43/8.16.0.43) with SMTP id 13SFTUtq018934; Wed, 28 Apr 2021 15:36:41 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2020-01-29; bh=SLQbfsh7p4k3x/7576TIMIZJdEEFhIDda5OpSOSGfjw=; b=Rp/ED/l8xcBVfLiL+N6AxSSrDDVJWSC1bKACoXiKFXbBHXney/eyZWUbzJg0/+tcgx/h LqXEOR4eihQpgb5AAGeuzNJYWstDslnDemyYYVqsQiyrEF4RxYWFEeMbgSyTdqcpdmbN xBwqX0Th/153VZ1xddfM+AuXqZLn+oLM6EzxoSnOXOKsYaMoII1A5GpOd3NRnsmZrI+/ NtvzOrX0kkomJmNyAHtqcoxkzK8o7kXrzG8truXbnQOFCfPvbaFDMWzmDTFksoUamXkc hkE0GX+c61pfsvdNR4HOnN1l7AI6KX7Sux71QIXAD8xcerxcHPUiYyj2ArIYoTEYKXAI iQ== Received: from oracle.com (userp3020.oracle.com [156.151.31.79]) by mx0b-00069f02.pphosted.com with ESMTP id 3878pk84sv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 28 Apr 2021 15:36:40 +0000 Received: from userp3020.oracle.com (userp3020.oracle.com [127.0.0.1]) by pps.podrdrct (8.16.0.36/8.16.0.36) with SMTP id 13SFY4iY022800; Wed, 28 Apr 2021 15:36:39 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2101.outbound.protection.outlook.com [104.47.70.101]) by userp3020.oracle.com with ESMTP id 384w3uuaea-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 28 Apr 2021 15:36:39 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=UWplZGHwBDaPghZP+2GXhIb81UNtCpUBAPi94ILjBLOrVyB50fxLSgs/yXPJOqp14SuJ0fxDW7Wevm/j6NFtdDX027hNkrUlXEV2smdt70LdnOI8wQ9nei0k4p6A6Ux5WRsN0S/Ot1dQs0NsfP/llQLmc9ZL2rYxt1ltWpb4eEX4AACkB4TGypDUUISpoC/G/PdPLLVMskW5vWKN7OuabXMEzXCM33GcWCbBihSZVfrrltf5SB6DibsMPp9BNaWsQMuz0QHp3LbWtSncKwMrCQpbu8pRl/Slc6m0Wmcc3dgPkT2+AMYaXiDZIENFjos+cE+ZSYVI7sMuh4Pq1M9BEQ== 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-SenderADCheck; bh=SLQbfsh7p4k3x/7576TIMIZJdEEFhIDda5OpSOSGfjw=; b=LFq4J8H6gFyvN9ysM8dZGdH1RASqj+nqSRLBlhcP2yp9/IMFh8kVnP1Zsijj1Wq/5iANnpWh/a+NpVP0N1QxUlR/jVDqU8zWGxbQyCoDlvafCWMHAR86SYjm9/Baj1I2+aF2nbXKuKfQoUXhWLFkggZ++WJlMeEGcB9cse8izTBAV+rGWm7Wb2zPTf7hDt7bHJiACtP8H+5hoIltYpT2C9wjUbAcOdXAaUUnX+9Bo0/BJ32wHg2pzPMz+Jyo+UVLbj+8lwu2Fz9eTg7A+JjXrwTN10FdecZCjDm2SkXDjSDrk3w1SyDRvCTwngqBw8DuXawfvgp9JJwl9aG7+sOmIA== 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=SLQbfsh7p4k3x/7576TIMIZJdEEFhIDda5OpSOSGfjw=; b=PhZJ/D8vY6bZyvtYdwY/lHDszQdRheuLKHVADlwxcTtESZnIbjDkZJ5i8YnDSHpiawyARbzH5OCbAX8gKSPWWGrVnq/YxzmLfofSisZGNHDdjEbranUeeT5EIItb4ztxGAkwucZp7bMoUlWcdnnsDc5JCNRn3B9gsBcsLfJbypo= Received: from MWHPR10MB1582.namprd10.prod.outlook.com (2603:10b6:300:22::8) by MWHPR10MB1982.namprd10.prod.outlook.com (2603:10b6:300:10a::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4065.20; Wed, 28 Apr 2021 15:36:35 +0000 Received: from MWHPR10MB1582.namprd10.prod.outlook.com ([fe80::353a:1802:6e91:1811]) by MWHPR10MB1582.namprd10.prod.outlook.com ([fe80::353a:1802:6e91:1811%8]) with mapi id 15.20.4065.027; Wed, 28 Apr 2021 15:36:35 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton CC: Song Liu , Davidlohr Bueso , "Paul E . McKenney" , Matthew Wilcox , Laurent Dufour , David Rientjes , Axel Rasmussen , Suren Baghdasaryan , Vlastimil Babka , Rik van Riel , Peter Zijlstra , Michel Lespinasse , Liam Howlett Subject: [PATCH 31/94] mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple tree Thread-Topic: [PATCH 31/94] mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple tree Thread-Index: AQHXPEQzbz+bn/uVg0qIrJjj7IL8gQ== Date: Wed, 28 Apr 2021 15:36:05 +0000 Message-ID: <20210428153542.2814175-32-Liam.Howlett@Oracle.com> References: <20210428153542.2814175-1-Liam.Howlett@Oracle.com> In-Reply-To: <20210428153542.2814175-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.30.2 authentication-results: lists.infradead.org; dkim=none (message not signed) header.d=none;lists.infradead.org; dmarc=none action=none header.from=oracle.com; x-originating-ip: [23.233.25.87] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 671bedb9-2b6f-4047-5ac9-08d90a5b6857 x-ms-traffictypediagnostic: MWHPR10MB1982: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:3826; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: dpfR5InMTD/va6F2fsYliukXuwlQ/I9n8HRaBvN1+7FFHlzM+urs6IlfJSV3Pv9eJsuJ2MJbiYD5zrZV0hiQMDWSSnGe5x4fFSl4XvwR7ZCJPc0DwHzFET0p7EfRmIwbGMCeUENfBZlURUfupsSm1edNsAXmK+yNNChH/WDfaomA858CcsLBsFEJ7a63cbXb4BrO0Wx9XlQut0cM2NRg+r+f+riivKfPZKC7nX44AmuZNc6HRO6wFNiZ578nR28BRecyBQOLNqnLB3RfHo8STquebyo+NBBHlKrfY2v1UGaupYJdZKDGRATPblvtpDPcImbARBtViNq7wk9loEA5twsi2AUc1CLVxZhuoDA2Squ3CZX8Uz5C8n2ECUCu1Of4G5EkVvkFGHBxEE9F8UCSNKZ7naE+Rs/NixMW78a6iwQqg6bVAf8cyPNWsD69xyRtuIu7STIr83VVqWQ7ip2db0T50hRC8Es5PW84ygPZ2cWKOubwBHyPsF8rl5ZYIt28OuwkDFZFigdzPLqnSZnpnmQC2xlyMjWPhjjpf/M/7bD8YosFct1B4audsjVj4Cc/PQDDxxWEBxtisEHoxZgRd2LWzCDrkvnGLYgYF6VNl8c= x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:MWHPR10MB1582.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(136003)(366004)(396003)(376002)(346002)(39860400002)(2906002)(8936002)(6512007)(1076003)(66556008)(76116006)(83380400001)(66946007)(6666004)(2616005)(7416002)(186003)(26005)(4326008)(110136005)(107886003)(66446008)(54906003)(6486002)(71200400001)(316002)(5660300002)(38100700002)(91956017)(478600001)(64756008)(6506007)(86362001)(44832011)(8676002)(66476007)(122000001)(36756003);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata: =?iso-8859-1?q?SoRozVZvJbJvUbI+ifrZlQKtT?= =?iso-8859-1?q?t1Lz8W44MYBMMZNpypP/f13cMoGvghTU4QCSUM7EPWy1efnBvuFo+k6NtLA4?= =?iso-8859-1?q?0z21FqbWk2VV67SJXblGd1g4kNwzvKBJ3JY66g+YBPd4Yay/zkd6PVmvRoh8?= =?iso-8859-1?q?+T61VHWih6jwCuux+hNhyrG9r/3tPfL/pDOGQxYFbvzVELO23EB/ZuQslO3V?= =?iso-8859-1?q?Ym3Mdmr42jvUHKdSWnwW5xO7IC3nV++sZHSb+1GJAmXoki6dVCkGePNhq302?= =?iso-8859-1?q?AuCvvZQozpL8yDdMwxbZSqn7tQ2EAAG7i04qUqe4/dd9brph/GD/dVREiPTk?= =?iso-8859-1?q?8et3Yjii9cCj10B2yTtqPhnWp9ggPGPjkLLIloUWQcZFO32oADL+V4sJFbWA?= =?iso-8859-1?q?pka9vfqnnZoBdVS9LYKIM9c8HyOrUEQILkwkgYhtpfGR6p8mrd9RTyOfcYch?= =?iso-8859-1?q?0fgOcZDL5zXnFVteSObJbFkRu71Hz7VUbQSQkN+zbY0fv3+HF+zhZgvLPl3G?= =?iso-8859-1?q?4E7/I32FKhxTW8wC8S6k/veKbW/DyfodxbjiBjvICZZH+vLXnnjG+hcWD1Zb?= =?iso-8859-1?q?Gf3DQn7VUZLX8VqcUbHdhV/JPQUtG47mKlhR6m49ouaFKAYA2PhTTPSKNQlm?= =?iso-8859-1?q?irSitp5zEMCAZUWwuvBX8JDOzlLngm1PT6hLSNkhfzQzYoJhs/ebYhTAKADH?= =?iso-8859-1?q?NWSmJoqwUsb1yZ6S7dFciJUlKLf5Of/uya1pvFu48zOBEjIiD06HmcOtAvhw?= =?iso-8859-1?q?t2z6krSJbN3i1wNKCcBup1WWnNj0TWWqXPSecoEU65fBH7wh021d0AOYELx4?= =?iso-8859-1?q?SAvnjai0pGnqdv1ccAOwZCEDBbsg/1DaVvmNjfokOCf8Ol7DY7BJ/7W1AVvh?= =?iso-8859-1?q?7Mmd/zg5sScTt9onmBBhdks0ZxbZYE7vOa71ZL5Zo2Vqzt4nsZ/8f1PmDkJl?= =?iso-8859-1?q?OhJgBPthiUjQ+P+nBa4dq9dTYAcZ7tSeRe83p2v9d9Or3dy8g4pe8o4obEdf?= =?iso-8859-1?q?Cn+lFrN3JydtN/GwVwKNWAT47Ro9qbmw3lCv3M0LBCGUI2olQgtEBjQ9D+Bj?= =?iso-8859-1?q?x66MHj/FpHsjOC33eI+2CphzVDY/cey9oPiSEoFNbyNmjHvW3J7K2q8O23/f?= =?iso-8859-1?q?0GAc1pw6JaK6gprSIxaxy0WyMOJ4Y8qUW6J/PMDqh8iITXmAoMpFhFQtnqQk?= =?iso-8859-1?q?UkC3Fjg6edResUGfIviIjcBnqW61cbWPMZAgCWlklKe+pQbdPHy1R6xKgry/?= =?iso-8859-1?q?8hxNLq63/f+KKFNoklsYOpepoeiaNkbJSzrAOMKr5B29j5byeH2e4gikVxGJ?= =?iso-8859-1?q?8MVFTCUQaLTGiAfjdOHMw9+nzXReFr+6DhRLsOalcRQZ6O76Zw17HBGlfNb?= MIME-Version: 1.0 X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: MWHPR10MB1582.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 671bedb9-2b6f-4047-5ac9-08d90a5b6857 X-MS-Exchange-CrossTenant-originalarrivaltime: 28 Apr 2021 15:36:05.0489 (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: YRI6cS7GE7kP31h7nGtIHJFgoYthr2gcj9uDudF6sREyCVjYkkkIPiODS24nhv4THHO7MFB6Zri+cwFSV7yQzw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR10MB1982 X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=9968 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 malwarescore=0 mlxscore=0 mlxlogscore=999 bulkscore=0 phishscore=0 spamscore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104060000 definitions=main-2104280101 X-Proofpoint-ORIG-GUID: 8ZUynKabGEMHRUdG4q641MmYs4YyVuGV X-Proofpoint-GUID: 8ZUynKabGEMHRUdG4q641MmYs4YyVuGV X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 97CDBC0007E3 X-Stat-Signature: 874ixi1n7buk3bn46jqdyr45344oxynm Received-SPF: none (oracle.com>: No applicable sender policy available) receiver=imf22; identity=mailfrom; envelope-from=""; helo=mx0a-00069f02.pphosted.com; client-ip=205.220.165.32 X-HE-DKIM-Result: pass/pass X-HE-Tag: 1619624204-185822 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: Use the new maple tree data structure to find an unmapped area. Signed-off-by: Liam R. Howlett --- mm/mmap.c | 263 +++++++----------------------------------------------- 1 file changed, 32 insertions(+), 231 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index 0fc81b02935f..929c2f9eb3f5 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2049,260 +2049,61 @@ 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; - rcu_read_lock(); - mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1, - length); - rcu_read_unlock(); - gap = mas.index; - gap += (info->align_offset - gap) & info->align_mask; - - /* Adjust search limits by the desired length */ - if (info->high_limit < length) - return -ENOMEM; - high_limit = info->high_limit - length; - - if (info->low_limit > high_limit) + if (mas_empty_area(&mas, info->low_limit, info->high_limit - 1, + length)) { 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; -} - -static inline unsigned long top_area_aligned(struct vm_unmapped_area_info *info, - unsigned long end) -{ - return (end - info->length - info->align_offset) & (~info->align_mask); + 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; - rcu_read_lock(); - mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1, - length); - rcu_read_unlock(); - gap = (mas.index + info->align_mask) & ~info->align_mask; - 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) + if (mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1, + length)) { return -ENOMEM; - high_limit = gap_end - length; - - if (info->low_limit > high_limit) - 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: %px 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 => %px (%px)\n", mas.index, - find_vma(mm, mas.index), vma); -#if defined(CONFIG_DEBUG_MAPLE_TREE) - mt_dump(&mm->mm_mt); -#endif - { - struct vm_area_struct *dv = mm->mmap; - - while (dv) { - printk("vma %px %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.index + info->align_mask) & ~info->align_mask; + gap -= info->align_offset & info->align_mask; + return gap; } /*