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:     Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
        stable@vger.kernel.org
Cc:     maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org,
        "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        "Liam R . Howlett" <Liam.Howlett@oracle.com>,
        Snild Dolkow <snild@sony.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>,
        Andrew Morton <akpm@linux-foundation.org>
Subject: [PATCH 6.1 06/14] maple_tree: fix mas_skip_node() end slot detection
Date:   Tue, 11 Apr 2023 11:10:47 -0400
Message-Id: <20230411151055.2910579-7-Liam.Howlett@oracle.com>
In-Reply-To: <20230411151055.2910579-1-Liam.Howlett@oracle.com>
References: <20230411151055.2910579-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?5CsOkmSeTUMaxblAmBse1ZH2PFBRGG7IqUSZpxBltK4xebb4bdgqJ/lkqM8f?=
 =?us-ascii?Q?Pjx52j8KR5TQxSc9gXCZyWiZHDruYppSBLuDLlJxvWFbS/AAX6O/vlhLT2sZ?=
 =?us-ascii?Q?x4lL0E53dooqzJKMA5rFO4I2qFRrP9D05KaHD842HO0z1eywoMQyVIdopA+6?=
 =?us-ascii?Q?HsZKQ2kGfdeaa7QLizrTI/OiZvzDU1y0RrTxMPf+wlSFVZjrD2JmZfUaRoMU?=
 =?us-ascii?Q?eMY/DVNOmcRuVGPzB5XZfo4DF7gI9KHLYj5ljaCOpqkkAUdZp4mIEt7Srz97?=
 =?us-ascii?Q?54DUF6nbpQKpDmNXbHlgZ88eU5O0nr9SjR171BFapI54HZGh5njgXVMhhSz5?=
 =?us-ascii?Q?6vn4c/exue7eQpn64Me3im5hEBt9VJzdIN0VeP9DUp/7u6do0hWfvbVj/LLh?=
 =?us-ascii?Q?Puaf9/RpYE//hmwr/vdC7a8WpGBYqZ9N1ZZfO67MvE81O93o3awYCW/SwW8z?=
 =?us-ascii?Q?4g5p7KCkYxZ151CFvikoe6qQTnIZk/yO3o7ll2eAK//UQ1xYVQ2lNirxhK4c?=
 =?us-ascii?Q?LmBxYODhXmT0iy6+X5YXPdsQPRfHKFyZcfG6VrrYGZkXXt5J3eOsWRmkuFqz?=
 =?us-ascii?Q?syEDmEgPekiGKZSqQeCb4xjtbiL0ZtVSRUJyQPHqO+XCeHtYN8JjXVMbFDLq?=
 =?us-ascii?Q?IWu2q4ePnNoWGQt8cK4kjA7wIL1SzbLq/F61hE5Ha+5q5h2xnc+DV3AclIrS?=
 =?us-ascii?Q?eLf4bdn/szmYRckkdyndiR4WYgMasyoH6ISUDhun79pA1DN2hAP9g9Qo4exc?=
 =?us-ascii?Q?AWoIquVq1xTvcXwDjG8TpLhIsnLhbwGHp05s/eKbDaiZaii3JMvTG83eeoLO?=
 =?us-ascii?Q?FoUHmYmHKlYkujDdzDM499VxKI1DCHAmlpMD6nzxbLJ6Wu1tu3g/4plR/S5p?=
 =?us-ascii?Q?VwsX6DiJ49FcjkP0CvT8NVQpvgsuREsOsoVy/aTRp+Y1gRS9UO/OwmD0gpiV?=
 =?us-ascii?Q?BoqntM99H2uL/jSbX3rlY+7Ok+DT43/BkNqX8hkKhUNA5STg9zTp9WqRwjoG?=
 =?us-ascii?Q?L5swdrrK66tYnkYtqMXZ8KAGsowxTsiMtNMa6lMVg4jR7bb+ioSYP7kFe0QZ?=
 =?us-ascii?Q?C9niUf3riKdwvffZtnQ66E69YZDmcfGBzSZkn0qkAOO6+gYSfdJOOAcpEEmR?=
 =?us-ascii?Q?HZB0sS74kw6OINIR+xSe9RJXk24FbbxjxK57AKoMchUhmWH0wg6E5KWah5SC?=
 =?us-ascii?Q?9fMFd75+tUFSGdOEsxC84gcamcW58ZLJQNQP4Nbv4XJITPmQBzf1F0RDepTC?=
 =?us-ascii?Q?kP7iY4neYzCsLgCiMC7UkMNlZ8utzfkKEBcbFiqikEacNfqCM42RFf3qUOZ7?=
 =?us-ascii?Q?mYWp9fAKOrqJCXSvzN/PNSN9O9tTAdZeYhWeuw9yxSsQymDiMPv+52JRoZRq?=
 =?us-ascii?Q?QePO3D4p554z8r15I/+uatP4ZF6cAU36q8850qwZX9hbhI91zSH3uRsTbrBF?=
 =?us-ascii?Q?gT9msoNUO1J74LxoIU/vz2zblUxKbxBxZ70gju8/WuflHf7ERdi3Ry2dugHR?=
 =?us-ascii?Q?Lll0OAgwauqif4mAClPuOfRow5VSgwZWwY2QPboXKVPalbBdvFLVUid7CrIo?=
 =?us-ascii?Q?dY3nZOmu+dK63h0/EftqI6XE5tMzbnfK77TiokHz9sWa7YtT/C6fQe3BtGPk?=
 =?us-ascii?Q?ZQ=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?XYGwJEsCKs5Rn4hLw2H30eEqq83L+7EM7llFK8iVznOf1UimNsAPpHNZrYfB?=
 =?us-ascii?Q?oSVoJ73UvdYfgsX7azc/KG1CnQEdyhJXlmLRIrR057o1Tyg4pSWMhIa9Ir3r?=
 =?us-ascii?Q?W4UGC2L4+HjCgVGOP/Bd+JVeDzWOYmfoTEFk52VEBnCyp+rBk/p7fxE+cF89?=
 =?us-ascii?Q?MIjMIenaaK3dbVgpvn3t/uclVkphzQMXqwGlRpJK+JjV+NOck1jsh9tmA0UT?=
 =?us-ascii?Q?k+L0qVU04dUkiSdb1DRL7yaO1iEky3pSgaqcuMuViaIjlN+hvdAzc8NcLUaM?=
 =?us-ascii?Q?fQ1N/c9ZDnhFdd34qtpxWP+cqn+VewIhf+ydjjWHuxU8zq5LhFyakfmCvK7Y?=
 =?us-ascii?Q?w/em29uiZtUTaR+6prM6/QkWHhMnREYjLGlkcU3SBBZWEj7TTs+xrveVM9HD?=
 =?us-ascii?Q?w7AxqzRPB3NekzAaIU2gVtP9Xy1i31wiQfThVnRrA28Wq5BS0bA2Zdgt4noZ?=
 =?us-ascii?Q?PyppU/9WL2b3VNsmMOO/hjddduWm5xF+kovp26BPvfbCWSkC2EtF18DPjfnu?=
 =?us-ascii?Q?I3aDeBdvrXUsDvzyqcwDm8HUpU9uyv2UMFnx0oio8IMeX0/p7jbLvyqFiWvX?=
 =?us-ascii?Q?XZOyDNuftw/V9/28v7jzCysAXUJg6uLucFyA3X77emS0H0UYE89DIQVozIAJ?=
 =?us-ascii?Q?s8Qgbzy2pKDngQrpcdC2oTUHx6dhj54f1szMZTiyWRoWqf0yElTQ/0rFnD8l?=
 =?us-ascii?Q?LueoFYbfJlTrMv9zk5jz2wl+VNnwukdIDQ7hwV4+sWhIsWzNeAxQfK3/Ui0X?=
 =?us-ascii?Q?FwA3rpegiAQsVttkFEh65ZLsaLTrqNJyIouL+0f2we0F3suK5SYvk7/LWPxH?=
 =?us-ascii?Q?oyZjEpfgg1Upv/wH/1mDh0n0N9a3C7eiDrtJjZBXeE+Y8j/Mg72/soz1skoc?=
 =?us-ascii?Q?s1Z0z1wePF9LM/URSWZ6wcXP9Uhf+yUnNTL2ZlXk5NqGLek3niI2swrodX65?=
 =?us-ascii?Q?EK6jw2flPWpKiRMq+P6gNlvodOiRnEbHUkwkeHlC8a1q2teWkWbW3uAH/UtV?=
 =?us-ascii?Q?1/Eb?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: eba02011-8ace-434e-cc6a-08db3a9f0aa0
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 11 Apr 2023 15:11:35.6995
 (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: dcG9uJQZzqQve0AAYGMKRhBF/CcdZQjb2/eAsVIjaIwZSJVqaCyUcSETejBCyL37n9HmL0k4zEUAlzOjYx7zfg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR10MB4718
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-11_10,2023-04-11_02,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 mlxscore=0
 mlxlogscore=999 spamscore=0 suspectscore=0 bulkscore=0 adultscore=0
 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2303200000 definitions=main-2304110138
X-Proofpoint-GUID: Yml7GVUvBqtyMrgnU1N7r1iLqE8eFbJI
X-Proofpoint-ORIG-GUID: Yml7GVUvBqtyMrgnU1N7r1iLqE8eFbJI
X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
        DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,RCVD_IN_MSPIKE_H2,
        SPF_HELO_NONE,SPF_NONE autolearn=unavailable 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

From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>

commit 0fa99fdfe1b38da396d0b2d1496a823bcd0ebea0 upstream.

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.

Link: https://lkml.kernel.org/r/20230307180247.2220303-1-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20230307180247.2220303-2-Liam.Howlett@oracle.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reported-by: Snild Dolkow <snild@sony.com>
  Link: https://lore.kernel.org/linux-mm/cb8dc31a-fef2-1d09-f133-e9f7b9f9e77a@sony.com/
Tested-by: Snild Dolkow <snild@sony.com>
Cc: Peng Zhang <zhangpeng.00@bytedance.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
 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 fc3e22cff642..c50646fcb8ca 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5097,35 +5097,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