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 3/4] maple_tree: Fix mas_empty_area() search
Date:   Fri, 21 Apr 2023 09:55:58 -0400
Message-Id: <20230421135559.2163923-4-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?Oi/mRNp0E+XVTGEBbmVkZjwzi0in6Mn4tY6QSJ/8W115AhnMmupYWcufiw1/?=
 =?us-ascii?Q?H1eyyUllIKuM7b+vM2xNdnMYMmb9GodXkInEWPZXB47WqUvpyehqpXbMhbMm?=
 =?us-ascii?Q?dyZza63O/u08gjHtIUH6wljndEbL1tjecqPc8LZmNIHh1POr9U7BKjHBM6Re?=
 =?us-ascii?Q?qnBReV3BzXHAmF1wJ+jbJ4D2Gfo2AdeGrUQPn9PqrQz+/CDG6b2qSwyjPs6i?=
 =?us-ascii?Q?zbQAj3qHGe0s2atSd+LOvgTsNxYuztWhcXLC0m9fEguugtyuC6mOyLL8fHwS?=
 =?us-ascii?Q?/jUDyCfmQ8XHGfx2Uxjb9/bnrlELHjx4znMsK/tqt1TKRBlDffse+YiMss4F?=
 =?us-ascii?Q?3bOzR0YXN8UvPoawGqR3Y8I1TzVZyd0HZC1HpXZYBusGR4UqCM2UBsZ1gYTq?=
 =?us-ascii?Q?YWSOei1RV6tUpgdBQv2QDSwY8+9kAXCupJ6iy6exmt3oIQ96fO5KeB7jglTB?=
 =?us-ascii?Q?CxCDPUrRBjMdfItUqMaVhsSLqnqv3opJBZ2kbRydg7ttDn+f7ObxbTdDt2RM?=
 =?us-ascii?Q?B08Dv/fifxTvJVQ1he5njc7VgcII5+7poO3Se7Vbq32PKSqllhbKia7HoEih?=
 =?us-ascii?Q?oyh2wlcM5zTz1hCKEbis6hQNpwhTvnF5xgKMYOx3zkc6Wu6DlupPA5hw+5EZ?=
 =?us-ascii?Q?Ttn3MRTBqqHxtuOpVT2LTxLAEMuxbq7eSOMNe1N22ngxIgIWOD24vtiT3Ky1?=
 =?us-ascii?Q?tzDfjvwu7i38LmqbWyiXb8g4SXF8elmpPyh3Xy5MQuRK/lxAFI/CMwoQsSMe?=
 =?us-ascii?Q?jsfM9UwIloi4Huc5TTrUeSkujSX+06WV5gSSS+xjvymHild0GwYIxxILcRMP?=
 =?us-ascii?Q?rrzCgEhOFCoG2bnGydHwiQOiMDyckvcyAxEqWBs2NFKyB+cOQ/zX8+9WO5NE?=
 =?us-ascii?Q?7/rKANENQgoAAMXgHh/sP5xGcVNAIqZJRfJ1MvBnD1gDxltg98zAAI2f03Gh?=
 =?us-ascii?Q?qoGce8Dv5UAVewgFbFraQ5z5m7CrvtzM0wE1Vy3J+sAA9UDqrFMjDzbiWcp3?=
 =?us-ascii?Q?J6cdMSQwIAbvM/qXJ0F/htlKn+LYvu6LOFaxiOBJCoUJ+VN7MRozDFChFkF/?=
 =?us-ascii?Q?8Ioj92virSzIOqpkerEndTJIVR/9Zk6A2IM2b/LjIXBZCzDKpMNXiF52//+N?=
 =?us-ascii?Q?plqFxQ/S2hQiR2iqVTGZGXb4rRN6nbLokuuxvb+PdyLMgjBtdOmDt991v3VC?=
 =?us-ascii?Q?FGTuHv45SAjVYuRNz+bGB36KtJbHpGdyjvb00lUY5n57ne83rZo3anXG+FdP?=
 =?us-ascii?Q?mpsGd4ydzTiIOreE3A5Z2KhOraqADHhenLGMJQhD9/I+MZF9BJHR9ADibi45?=
 =?us-ascii?Q?y0fmo/8CrHUtWaOGXZSWfyrddWVMBQc8jYJiekkFzwAk09tMOxEicVAmdoRi?=
 =?us-ascii?Q?4ItUYoBbwfGDKsxul2d7fpYvSE0qhb2LSRyVDLwF1taum+kzPK9CHXaR6NUS?=
 =?us-ascii?Q?6gCsGx00XwVjkmhkd4DjWZrwg9xXCErpT/hZb5XXsTy5hgX+QLJSvB3D7ymS?=
 =?us-ascii?Q?gRvdaSBNAI8SS+s9IRJsDN8iY/K+tMbWi9Ylqh9TYC4A42/N+yyOkoQKw7pg?=
 =?us-ascii?Q?GZlELbOI6uH7CzWjX0rWLJi+0Rxe5LUWd8UDZaRfGmO9fJNKLCnYyfMD4Jta?=
 =?us-ascii?Q?qg=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?YmVfvVisaWyf/owDnKvjANhB/A8tjaasayT5+d+ECuwSARqEKVXnZtiIx+v2?=
 =?us-ascii?Q?mdfSIKTgyTthAxlg7WY390Dwd5OXfzSXlOwAbEUTj2+udmCg6G/Uf3i9PcyQ?=
 =?us-ascii?Q?yOWW4jQbsgPY3MERReWx9x5IRwIkTKcLbY7kUCt5ePJBwymN25hPRytXQEFy?=
 =?us-ascii?Q?TIB9Q433YAWbIkX3AOIwjqF2FbPDV8LJUY8Nv+vA+q5aD0o4e7GLfJhD3i9z?=
 =?us-ascii?Q?hBRqthC/FkJvDx+Av6oXyIUvLni0Ao5EbiTzDdScTJpbTIZguhzLDpAMMR0L?=
 =?us-ascii?Q?sfo+KtW6Vz4Zuh/DVOuedguezn5wCIY+b7ULWHzPOVkX0lVWiVZ+rU70UNh/?=
 =?us-ascii?Q?dHXhvDbDNqLYe0dnIscL4oPFkmlFxyWH6LPMqFLIlzpD6jeg+CSWKtgags6o?=
 =?us-ascii?Q?yIh/IIsmzCbd4uXAJVUqrJyDI0Qq95elJOryz5rPTIjbvfg2C0KVPso9OQ1D?=
 =?us-ascii?Q?ETK7XPvAv+a0BvR7ElGZIm1FU/U2lbRv7Q1Ino12GzqQxuGGA9BlUBXXrThG?=
 =?us-ascii?Q?PlqzfcR1GtbYg/GWXL0dyIXMdmbidX2pdkT29lzNUqfrPVOjnF9zYb4/jwlU?=
 =?us-ascii?Q?MezPiW4tFYHhOYWnx7IO8ecomv/LWAoUNAKqJMucybKCSCn1ZfLulDFqQSxW?=
 =?us-ascii?Q?QbUAfFw+OQtRGNRkrqYTlRZ9WtNfAYdNMY0xfyzzNmMZhU98yM+EY9Pnec1L?=
 =?us-ascii?Q?JeVSTdbHgs9uW/LZ7DhHYiM1CxocB/yjzC7gG6pO2b9PVTPap0u2R+pE2tcn?=
 =?us-ascii?Q?m0/D2p5SwhmIl+RLhcEWTvRBszibCL5HZdY+wuBXnO0NEISh3zSO9T5R3HXS?=
 =?us-ascii?Q?T4bZPPy8RKiBHaTn4Z3ru0PQJtxubHytUc6y2iqQCrb2c/A6Us0woj6zgpY0?=
 =?us-ascii?Q?/Q9UTU1bCu9t+pz0rB7uii8tKPjU/Gw/2dOTv8P+LyHRKUYSie4Y7RLBEAI8?=
 =?us-ascii?Q?7FucC/9nR/0PFPIY8I2K/g=3D=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4a7e4c96-1e0d-4026-6c78-08db4270332d
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:26.6427
 (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: Bz9kVsCYohCBgtUmm2HoAieKwz5CaLA6l9ZVFNtOjVvIwI4T+3oM4C1xQ1wWwj265BIGjbNLcnm36/bY1wfuvA==
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 spamscore=0 suspectscore=0 bulkscore=0
 mlxscore=0 mlxlogscore=999 adultscore=0 phishscore=0 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2303200000
 definitions=main-2304210121
X-Proofpoint-GUID: XAcGehv1Thb_F5yBuoLg8inbmZcWdz_i
X-Proofpoint-ORIG-GUID: XAcGehv1Thb_F5yBuoLg8inbmZcWdz_i
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 internal function of mas_awalk() was incorrectly skipping the last
entry in a node, which could potentially be NULL.  This is only a
problem for the left-most node in the tree - otherwise that NULL would
not exist.

Fix mas_awalk() by using the metadata to obtain the end of the node for
the loop and the logical pivot as apposed to the raw pivot value.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index cf4f6cdcaad38..51910c74d4895 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5029,10 +5029,10 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
 {
 	enum maple_type type = mte_node_type(mas->node);
 	unsigned long pivot, min, gap = 0;
-	unsigned char offset;
-	unsigned long *gaps;
-	unsigned long *pivots = ma_pivots(mas_mn(mas), type);
-	void __rcu **slots = ma_slots(mas_mn(mas), type);
+	unsigned char offset, data_end;
+	unsigned long *gaps, *pivots;
+	void __rcu **slots;
+	struct maple_node *node;
 	bool found = false;
 
 	if (ma_is_dense(type)) {
@@ -5040,13 +5040,15 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
 		return true;
 	}
 
-	gaps = ma_gaps(mte_to_node(mas->node), type);
+	node = mas_mn(mas);
+	pivots = ma_pivots(node, type);
+	slots = ma_slots(node, type);
+	gaps = ma_gaps(node, type);
 	offset = mas->offset;
 	min = mas_safe_min(mas, pivots, offset);
-	for (; offset < mt_slots[type]; offset++) {
-		pivot = mas_safe_pivot(mas, pivots, offset, type);
-		if (offset && !pivot)
-			break;
+	data_end = ma_data_end(node, type, pivots, mas->max);
+	for (; offset <= data_end; offset++) {
+		pivot = mas_logical_pivot(mas, pivots, offset, type);
 
 		/* Not within lower bounds */
 		if (mas->index > pivot)
-- 
2.39.2