From:   "Liam R. Howlett" <Liam.Howlett@oracle.com>
To:     maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org,
        Andrew Morton <akpm@linux-foundation.org>,
        Stable@vger.kernel.org, zhangpeng.00@bytedance.com, snild@sony.com
Cc:     "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH v2 1/2] maple_tree: Fix mas_skip_node() end slot detection
Date:   Tue,  7 Mar 2023 13:02:46 -0500
Message-Id: <20230307180247.2220303-2-Liam.Howlett@oracle.com>
In-Reply-To: <20230307180247.2220303-1-Liam.Howlett@oracle.com>
References: <20230307180247.2220303-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?2eUfP/2qwNfbq31r3p/O50Ur+nDiVXuCOzjCnrqpAzipGyDdzAC9h5IThpQR?=
 =?us-ascii?Q?jMvyCS5SKu11j6SfweD2mUgHB4yDQniOw6vslOkuuZAnVgUAiNF29xOs2dn0?=
 =?us-ascii?Q?h87qoo3CcZCurzc1mPOPAkeP3LAySu/gr41tGW53ekIPPbZIuTzoU7sKWqJ3?=
 =?us-ascii?Q?4XQ7VSy0wDpe+Vw1JFnSs9482cpwcepoh9505zphKTlxxSblrx4yW94g8e20?=
 =?us-ascii?Q?Nhq043xNNEY7qsV4TbLwM0MB1cR0SIazcBOhPHyYJbUrigDGsmSKUfCPIpAX?=
 =?us-ascii?Q?Dw8XSiAVGqm3pKbOjQFAPa1zXPchMtVHgh4LYzQSCVsHqy0M+Gydwd26MSyR?=
 =?us-ascii?Q?k4sOjL2gfNt2wKek6Cb5tZR3V7nj4u3znuJTxTUDNk/BFlHf4uzTRhrdjMNT?=
 =?us-ascii?Q?dva4GBTjaAm46W3Kh0jDKSuirykY0dmXqZyS/QpF9qLQh5baOVNvRDJgbWnY?=
 =?us-ascii?Q?ud+EEOLMDVDfcMLPRtQHzNCImCJq9LjnBXMyMO5OcONQmSef7Wx3mQ1+FNe3?=
 =?us-ascii?Q?mNrY2W8ueFKjQNv5eOnlcbAJfmvSTfUDOltcO69e91xSzynNELFZCWxio1qA?=
 =?us-ascii?Q?pID904mmkudIMBp1FBnyQfHdDSgnihl9PrPv9GEFCD9k9JJxhVWBPgWmro88?=
 =?us-ascii?Q?jsU1KR/lE0fagfmfsoTU7fJJeRZI8+2iqaRUxF/72WqxB2LUNMnhlQB8kvvT?=
 =?us-ascii?Q?b5NB+xr4OObP6mXMgT0fTilLodGycD+1QEaIiNec+V52MtI+Qa+CNsjOlAZ+?=
 =?us-ascii?Q?pQuL/ALCuZLyq0YBQ0SauRxfzmJ/6HxJaLO8VwMmPrPHqdjRON9TTAJWAo81?=
 =?us-ascii?Q?sp+fajTvSorsndVfGycHYhd+pYpZNu21MvIfzD0VRdptKwJ6iO4ijy4ssirZ?=
 =?us-ascii?Q?9vh1d/8FegDmqP5cUB8LeZ/3rKC0ysHVgqV2uk1hxwgRlM7s6YJYBw+DFL5o?=
 =?us-ascii?Q?X+gdY6UuBbZqEDJTpoYnNfnU0WoJPj3443fT0AXMemnGyMJSaGb5XRdDilyv?=
 =?us-ascii?Q?W9DhWSvwDETVPvhnN736Yw8kHgBPoX58VTN2xNuZo6Il1B8YJgJ0MZPLnNMi?=
 =?us-ascii?Q?fPrv1vPutAMKJGxuZHQkO1//FNcq709Jflxz0G4bkEzROZAOLmZgu7jO9Uqo?=
 =?us-ascii?Q?GnvtznoCDpnn2vU9nHlyQt44xA0OUOpjWYAWKNrk82mWCoanoDFFEAR2mxPR?=
 =?us-ascii?Q?EQ+rhfYPhrD2Mvw3KWq+WFABGyCiebV89OBy/tKlSYL7wUNzFWHK+qBDa6lY?=
 =?us-ascii?Q?9WfqXHm+fdpNNazcoQMR4o1ogPjSNBBqykjAi67OxEQv2F/4yVYMA04YAvht?=
 =?us-ascii?Q?xAvPQEVQPNL04hTelZZk+WrdynOScZ75Wc0C+E1cox+0HyYRSOwNcE7n0vMz?=
 =?us-ascii?Q?nPJVLsd2SaQyu84+LbG6wP7TJ0yGF+7BhdPXOJUk+OqTIO5u+kNktNfO+sy+?=
 =?us-ascii?Q?VYzo4VWOebggZMuMwkeLDaps3sL7GAeens2lpqbonA6pqZRgtAEdnpw7n0Ie?=
 =?us-ascii?Q?uX5thU2WQW0Tktv+vI4x8gDAAYCtBoxOXGxwltaPGyJsIlTLWY7OcIdgc1BS?=
 =?us-ascii?Q?Wg0ZeQLxyGuhCXh4jG4NFOTvaY8CFPe2jkxJTpUAoevz6JKAizPPhOQnlhv/?=
 =?us-ascii?Q?xw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?XfWAJrdOmQVTcT0n6aW8QM5z8z8A8wmGYF1BOqxQofp4w9PV+HLn0F+3NUyr?=
 =?us-ascii?Q?kNCHer9jqNMfCS1U24xnBFp10MXg7COVF+wWsU4bPiIFLKMiqyZL7snUfWb0?=
 =?us-ascii?Q?qkk25uO6FjGE2405k0xZT0ckhU9FbbHQmNLAN3TztBHlVVMYp6X0CTR3HCRZ?=
 =?us-ascii?Q?aer2wHxw7GNqHziNPhVCtyy+/6T7C+nuMT/lgQCIW94SjRdv4nTDKVRH4gNp?=
 =?us-ascii?Q?dvelA5gY81gSs9UmhAVGnCkzMXb+pRcU4FQ3RsWJ18F+3dZi8bq8/QaYj+CR?=
 =?us-ascii?Q?oVrKHnI9dGfnMZtbrJKG3eCWfVmNFB84ALYDj+JRCvtMzyjywYbHYj/6FnET?=
 =?us-ascii?Q?NwX5XAkgEuWfsU2ndjv2Ryo6+yhn9w069rtsgJp3omkjqs6Yf9g8D74HsR7f?=
 =?us-ascii?Q?uXWE42eSsgF9uqwtoDAbGTaPw9xOSc5pBo0JN/RTt32EahDLJJxSU8sq2q/F?=
 =?us-ascii?Q?2rTmk3MHYuUFM+BmXCc9hAB8NK4mZi61b4dM1/vnqFhIOsnyN0HD9Y2afTCb?=
 =?us-ascii?Q?AB+qxY9TTAmlKeKULN0PY0z439jOhgxw8Z2Dao6JKLZjYGE5I8vYmo0ojv7L?=
 =?us-ascii?Q?0bGv5vxzlRaX8Aes1ZhKapEKrUH5f/617/ERI0pZUA20rjjyedotqPb5M1j+?=
 =?us-ascii?Q?I6Z/KJMQfSjkE2kf7ryv1Kpow8f8YIoufODQ6LNhxolf+JcO56e7imOnblVc?=
 =?us-ascii?Q?o4kFfm0I7SL9rNIaZmyFRbkJgX3QzW64q2vzxo22oG2eWmOhztY5qwp0pnhM?=
 =?us-ascii?Q?lbKXbiwtSkwjZ47dnQBrXr33Y6uCpRsZ2J0RPVQCvnbvau/iCONbEClqU6aB?=
 =?us-ascii?Q?eecj3xFjZafRKfloVSxwJuuxKcLLn74mUXMhOLWJ2xg3NH36bgUqQ9b6ZtBY?=
 =?us-ascii?Q?Hmw7xlmnVWI4fRhmXQUeFzD8DTQNcsv8KtLV3JYWVvyZdl8NsqJFW0hxD5yf?=
 =?us-ascii?Q?1mAshz1hAqt/rco040PC1A=3D=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 896caedb-7582-458d-a5e0-08db1f362bd5
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Mar 2023 18:02:52.8111
 (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: S7vlMuD6Z2clByMwPUHfJz/MbbwsFHdwj0IgsE83sJcTC3y8oYfsMEOl4e+bZ5NQAcJ6sZyShjbZbHdhbpB00Q==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA2PR10MB4650
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.219,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-03-07_13,2023-03-07_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 phishscore=0 bulkscore=0
 adultscore=0 suspectscore=0 spamscore=0 mlxlogscore=999 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2212070000
 definitions=main-2303070160
X-Proofpoint-GUID: YdmZPtyy1XFh38cGod2xytr6FYufmcMc
X-Proofpoint-ORIG-GUID: YdmZPtyy1XFh38cGod2xytr6FYufmcMc
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

mas_skip_node() is used to move the maple state to the node with a
higher limit.  It does this by walking up the tree and increasing the
slot count.  Since slot count may not be able to be increased, it may
need to walk up multiple times to find room to walk right to a higher
limit node.  The limit of slots that was being used was the node limit
and not the last location of data in the node.  This would cause the
maple state to be shifted outside actual data and enter an error state,
thus returning -EBUSY.

The result of the incorrect error state means that mas_awalk() would
return an error instead of finding the allocation space.

The fix is to use mas_data_end() in mas_skip_node() to detect the nodes
data end point and continue walking the tree up until it is safe to move
to a node with a higher limit.

The walk up the tree also sets the maple state limits so remove the
buggy code from mas_skip_node().  Setting the limits had the unfortunate
side effect of triggering another bug if the parent node was full and
the there was no suitable gap in the second last child, but room in the
next child.

mas_skip_node() may also be passed a maple state in an error state from
mas_anode_descend() when no allocations are available.  Return on such
an error state immediately.

Reported-by: Snild Dolkow <snild@sony.com>
Link: https://lore.kernel.org/linux-mm/cb8dc31a-fef2-1d09-f133-e9f7b9f9e77a@sony.com/
Cc: <Stable@vger.kernel.org>
Cc: Peng Zhang <zhangpeng.00@bytedance.com>
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 24 +++++-------------------
 1 file changed, 5 insertions(+), 19 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 2be86368237d..b1db0bd71aed 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5188,35 +5188,21 @@ static inline bool mas_rewind_node(struct ma_state *mas)
  */
 static inline bool mas_skip_node(struct ma_state *mas)
 {
-	unsigned char slot, slot_count;
-	unsigned long *pivots;
-	enum maple_type mt;
+	if (mas_is_err(mas))
+		return false;
 
-	mt = mte_node_type(mas->node);
-	slot_count = mt_slots[mt] - 1;
 	do {
 		if (mte_is_root(mas->node)) {
-			slot = mas->offset;
-			if (slot > slot_count) {
+			if (mas->offset >= mas_data_end(mas)) {
 				mas_set_err(mas, -EBUSY);
 				return false;
 			}
 		} else {
 			mas_ascend(mas);
-			slot = mas->offset;
-			mt = mte_node_type(mas->node);
-			slot_count = mt_slots[mt] - 1;
 		}
-	} while (slot > slot_count);
-
-	mas->offset = ++slot;
-	pivots = ma_pivots(mas_mn(mas), mt);
-	if (slot > 0)
-		mas->min = pivots[slot - 1] + 1;
-
-	if (slot <= slot_count)
-		mas->max = pivots[slot];
+	} while (mas->offset >= mas_data_end(mas));
 
+	mas->offset++;
 	return true;
 }
 
-- 
2.39.2