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;
From:   "Liam R. Howlett" <Liam.Howlett@oracle.com>
To:     Andrew Morton <akpm@linux-foundation.org>
Cc:     linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        maple-tree@lists.infradead.org,
        Rick Edgecombe <rick.p.edgecombe@intel.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH v3 4/4] mm/mmap: Regression fix for unmapped_area{_topdown}
Date:   Fri, 21 Apr 2023 09:55:59 -0400
Message-Id: <20230421135559.2163923-5-Liam.Howlett@oracle.com>
In-Reply-To: <20230421135559.2163923-1-Liam.Howlett@oracle.com>
References: <20230421135559.2163923-1-Liam.Howlett@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?9xf2EEHAKkKcyFL6VvhCvXu3LIygxsivqawq/cpR9YL8kXWIDCNh4k3i7TT8?=
 =?us-ascii?Q?oYc8jyneOYlVUkQhWvnr09CjCY34Q5KV2A54Z6/NQ1bT6jt7EU/sXVCegAz9?=
 =?us-ascii?Q?cxNawGb7J85tHOI6yKhnqq0h1CGDllQNa7aWb5SW7WKTxQb24dhQwJZjIK4U?=
 =?us-ascii?Q?ZZWnaxnxTaucJvca9ULFEYt30OVMdLNeQ1iPlF1n+5xzwGwe9Pr5Wpzu8jxP?=
 =?us-ascii?Q?r7n6wqXLuhzCReUwOKWrfvx/y4i4lAP//v+a67ov95DMl6LQR5DQedPsmERN?=
 =?us-ascii?Q?dmMLmNEwKGX/bDTLQU+A+hL9R6vB5Q4mJm3Bgiv4GCLVXDqpakZyYAyeftFJ?=
 =?us-ascii?Q?vaxPt/HtapwsbOPtlIR3Y1XNFO8hSay1MTAUojrjXmulIeTcOYx0qcC2gDk1?=
 =?us-ascii?Q?2tH9H5uRWuURLRHNDzv2CwGG5XVv4v3y6Iebj3J60FJb60FFXH4bO894fJcv?=
 =?us-ascii?Q?gUbAvlnQCSda0b1+mlpL9RNfeq7OUM829y4HYY/E4Dw/nEkM66RpXcQrIsQy?=
 =?us-ascii?Q?5XYfmdHkbdDzz7k8QHpjTNS7aYPlYCnzi48Yijzm4UpCtKnXpEeNeVr61Ud5?=
 =?us-ascii?Q?He3YIS96FCPzis1e6/kE4IhUW8d7IkJryc5fYD6yWL2LByzP7ebthw+aDe5Z?=
 =?us-ascii?Q?8iXtALEAEtIqcborzIckmbM7PAj4281cQJK5NrHpUvj0l6nuqaADT4VZpaNQ?=
 =?us-ascii?Q?H7KpMblmMKdkAZVD8QpYbjQ7TQgMt5vZVJUxe13/b9IXhYcxBz0d1xv+tY8P?=
 =?us-ascii?Q?Pe8DVPoCy3WChTSqY7l+KngZ6GukxoNBPfZEc0rxPPHFGiDKUXL0IJ5WiAAd?=
 =?us-ascii?Q?wc0w/D0QhYCqpLVr4wxOf8da0AXsraNCspyqQmPAUNrFFV/ulPJ5QjaHA0De?=
 =?us-ascii?Q?TYPADLRCQyuJ2DUhzJ73rnGMO9yxYoToJxKNtht2HZ34p7K1DEr46sb4CuIj?=
 =?us-ascii?Q?Avp48cTjn5ocsR1GhYn6QggN4Z2pFwLIhZkXPVUUGMzA9r41Q1ODOf1Q7ayt?=
 =?us-ascii?Q?vknzDzKOoRH3ZrRSvRLr4z05Udv1TIIMgi4j3nKkeLLWDRU/xUQZyDQ1pYeb?=
 =?us-ascii?Q?vib5PR4/0pCaPa2CPO74BjN30aRsdJRdqFBSw3zRXZjwtP+Uck5TguDmF8Cm?=
 =?us-ascii?Q?twh5rGZCFwSKVBTmL6U/0CnzGPA9ByQHLjAh91MliZpbri1X6zLFnrwY1Ji4?=
 =?us-ascii?Q?dRtLwph/izcOz8aLF2INyF1t49p9/aXxOIpyjgBHnErd5wvkatZg8BFA3WYL?=
 =?us-ascii?Q?EjSU0jQaJ/G9N2kLrJg3Dmmo5smQOBnkR15hGghOruGuMdA9/GkbaPf7uYcI?=
 =?us-ascii?Q?aqPJiKrCHWaz4c4+Vva+O/jaVNoFvcVs/nxLITInWC2PBDQfOQ46tSeUTlDD?=
 =?us-ascii?Q?tEGQx1dwFYh46jYjstaDB9581kXTLrj7IJjSzFr+RvJzjW1zvH9D6qbuMuY9?=
 =?us-ascii?Q?FqvcP+m2jr53Y5Ybydh5Clv7RpMWvH+Pu5yIX1/RVGhtpNO7MQ9+zdIsVCIZ?=
 =?us-ascii?Q?QRabMjPK0vBaIEF0WbBB3PEUfj/OT0RZyuU+K0lBT6Bg5TGubBhRhDARG6RF?=
 =?us-ascii?Q?TLwd01N2B3wZyl8+FHTdsxiaaIqYS1HTfabFwQyz97coH22CZz7PCwzYw+KZ?=
 =?us-ascii?Q?4A=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?Zh1FYSJKgItUH5VtdAHgGCRp5eeFpdnkrOCUI55GF7rv8/OBxgJiaF98KKht?=
 =?us-ascii?Q?+4TJ4xW6mhohRFI7Kvnn3lO4g71MOJOud27VOZnsz9fn8y1XgT4MS97gfJ7U?=
 =?us-ascii?Q?Sk8ke0xxWF9YZXd0VVD05ApIEqSCBE4djezsj4wXeeb4OhDi8fhI3olbxjCD?=
 =?us-ascii?Q?P9UeGrP50LVRx2E1QF4a7vcU/WO8/Dlsm61gvUaFsX0beonYpHnnwRLpKiFu?=
 =?us-ascii?Q?ZUNoaYKPmsnNQDi1JBJ72Qh+Wkdf9N4Ui8xz00upfO5DV3EecoQr0mS5QdBu?=
 =?us-ascii?Q?9HRWdPVM5B+cxSQZwjYYAvxZWc22jWqmC9rpv9BWucstU7emtVDIvCksuS02?=
 =?us-ascii?Q?JMr+HiKFnHyT0KsZZbi1C1ao0GxBD0waQAlPYx9c3XoEcp+nMNV7AcDLnZYQ?=
 =?us-ascii?Q?WRvqJXLT0GJ3x9IwUTzAFis92gSO50AGvN3uithWsv4oFoAgs6Kp88Vi+xNU?=
 =?us-ascii?Q?2dmK0gQNcwIPilQL7/h32B20+1qSEzDUsuBw5LgP9941OPsl6IKNxkdjokL2?=
 =?us-ascii?Q?vMh0Dv4lpPfcHuhw/efwX0JvZ/dVswmJbDNfrNSgLvXg1GIKhQObSxUjxqUP?=
 =?us-ascii?Q?0gQ0j8GFw9Q5Js1s+dJ5CN154XhPYTAInt8Bmnat4oKfB+LwVbJHPDBWz1K9?=
 =?us-ascii?Q?KCR2nBftLXSuVLuN75KwFLjO7BVkQW9D0JfIPHKDZMk85W7dh5G5VjU9Mccg?=
 =?us-ascii?Q?XcreNXaVnLgG2gIOBHhmM/sSPDuTIm/87hslduk0Z16oFqY8EerNN8/VAOw0?=
 =?us-ascii?Q?AWiqh3a5pF5dbVAvNfyyTMLuteks+UhQLKQtD5mTwi56XA57N7MRT3qwz+7u?=
 =?us-ascii?Q?BQsoHpcW5A2228ZgUQLhamqCS/fmL8ml5S3UDy+ILaCrMsCbhB1vVZIW7Y8T?=
 =?us-ascii?Q?nYfqoaMqtOQaMh2bnFJFOd/4bpdVjJHH0oWgZlq0Z6B+uGkEvQEpihguc0D0?=
 =?us-ascii?Q?zwUgRDGglIOx2+6cBGRgUQ=3D=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 8d41b251-c89b-4664-8e3f-08db427034bb
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 21 Apr 2023 13:56:29.3576
 (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: ccnuV/UOcaj9DJwG6WZn4YbFHka1OQWFmsU6UgeSXyQH3mjBvxDm0PHxR6WjXzVXDRjSz4akjjEIh8O4+XS5Kg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR10MB7540
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-04-21_06,2023-04-21_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 adultscore=0
 malwarescore=0 mlxlogscore=999 mlxscore=0 bulkscore=0 phishscore=0
 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2303200000 definitions=main-2304210121
X-Proofpoint-ORIG-GUID: IjrZg72Bv0EJyEfyIsajhwMHlzOWjOZj
X-Proofpoint-GUID: IjrZg72Bv0EJyEfyIsajhwMHlzOWjOZj
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

The maple tree limits the gap returned to a window that specifically
fits what was asked.  This may not be optimal in the case of switching
search directions or a gap that does not satisfy the requested space for
other reasons.  Fix the search by retrying the operation and limiting
the search window in the rare occasion that a conflict occurs.

Reported-by: Rick Edgecombe <rick.p.edgecombe@intel.com>
Fixes: 3499a13168da ("mm/mmap: use maple tree for unmapped_area{_topdown}")
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 mm/mmap.c | 48 +++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 43 insertions(+), 5 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index 055fbd5ed762f..6b9116f1c3049 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -1548,7 +1548,8 @@ static inline int accountable_mapping(struct file *file, vm_flags_t vm_flags)
  */
 static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 {
-	unsigned long length, gap;
+	unsigned long length, gap, low_limit;
+	struct vm_area_struct *tmp;
 
 	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 
@@ -1557,12 +1558,29 @@ static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 	if (length < info->length)
 		return -ENOMEM;
 
-	if (mas_empty_area(&mas, info->low_limit, info->high_limit - 1,
-				  length))
+	low_limit = info->low_limit;
+retry:
+	if (mas_empty_area(&mas, low_limit, info->high_limit - 1, length))
 		return -ENOMEM;
 
 	gap = mas.index;
 	gap += (info->align_offset - gap) & info->align_mask;
+	tmp = mas_next(&mas, ULONG_MAX);
+	if (tmp && (tmp->vm_flags & VM_GROWSDOWN)) { /* Avoid prev check if possible */
+		if (vm_start_gap(tmp) < gap + length - 1) {
+			low_limit = tmp->vm_end;
+			mas_reset(&mas);
+			goto retry;
+		}
+	} else {
+		tmp = mas_prev(&mas, 0);
+		if (tmp && vm_end_gap(tmp) > gap) {
+			low_limit = vm_end_gap(tmp);
+			mas_reset(&mas);
+			goto retry;
+		}
+	}
+
 	return gap;
 }
 
@@ -1578,7 +1596,8 @@ static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
  */
 static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 {
-	unsigned long length, gap;
+	unsigned long length, gap, high_limit, gap_end;
+	struct vm_area_struct *tmp;
 
 	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 	/* Adjust search length to account for worst case alignment overhead */
@@ -1586,12 +1605,31 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 	if (length < info->length)
 		return -ENOMEM;
 
-	if (mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1,
+	high_limit = info->high_limit;
+retry:
+	if (mas_empty_area_rev(&mas, info->low_limit, high_limit - 1,
 				length))
 		return -ENOMEM;
 
 	gap = mas.last + 1 - info->length;
 	gap -= (gap - info->align_offset) & info->align_mask;
+	gap_end = mas.last;
+	tmp = mas_next(&mas, ULONG_MAX);
+	if (tmp && (tmp->vm_flags & VM_GROWSDOWN)) { /* Avoid prev check if possible */
+		if (vm_start_gap(tmp) <= gap_end) {
+			high_limit = vm_start_gap(tmp);
+			mas_reset(&mas);
+			goto retry;
+		}
+	} else {
+		tmp = mas_prev(&mas, 0);
+		if (tmp && vm_end_gap(tmp) > gap) {
+			high_limit = tmp->vm_start;
+			mas_reset(&mas);
+			goto retry;
+		}
+	}
+
 	return gap;
 }
 
-- 
2.39.2