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:     linux-mm@kvack.org, linux-kernel@vger.kernel.org,
        Andrew Morton <akpm@linux-foundation.org>,
        maple-tree@lists.infradead.org
Cc:     "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        "Liam R . Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH v4 04/49] test_maple_tree: Test modifications while iterating
Date:   Fri, 20 Jan 2023 11:26:05 -0500
Message-Id: <20230120162650.984577-5-Liam.Howlett@oracle.com>
In-Reply-To: <20230120162650.984577-1-Liam.Howlett@oracle.com>
References: <20230120162650.984577-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?HaIQnwXBcn32wjMviVBEssVPwO2/wYjEVlqRprzWnA6i4YZIUtrAfURRB15H?=
 =?us-ascii?Q?V9TxEvOmuzHqEHK23txZ2dMafridlbT/yGJaJI6yjOCGmDTxOFw8ggPeZIFD?=
 =?us-ascii?Q?2kS42ZufuJdPei1eLlT2Td7JgK8pESQueBhbqc1J8ad5q+jbLFl06g043+fz?=
 =?us-ascii?Q?akmYvvOdIsOJcPRs3jK/6fl8U3YbI4VlwmhEK4/mgDrbcmX8M/MoCxbiV/ed?=
 =?us-ascii?Q?eyR0TIct6aX8+OEd3fJW3MGfbV5vdzMGNIsufx6J9OoNDWVdgFFEXYUClQcq?=
 =?us-ascii?Q?rR/KNZR0O6PE5DsJZ8Yq44I1q5s6+is5BDqMSbY2f9mRbAptkWpf8fH7ep6l?=
 =?us-ascii?Q?AAEnm6FSrO41JuZuicc+T3rmIxI+5MWNVKB+qdcrtlVT+plHIht49Eu07C9S?=
 =?us-ascii?Q?WqlVFtfbxAuIcVd62xo1le71CegPPPS7jaICrqoQvhpUINcrazJC8uOURz2U?=
 =?us-ascii?Q?WxCOJQaVlHprHmBWLWTDS9K0FIDNDGn5mRcMj8GMKKI3IOPQ5umLjfZimtVn?=
 =?us-ascii?Q?JT8mhNQBHFySTAvz5ljjRUXoznBjanIMCJhTpOZnkAJi8o/VKqiCKOBKPagl?=
 =?us-ascii?Q?wfKAsk36cJXusT13Aeq1waJQ5UQhG4K6WcmzZD6l3kQfrUo2ab6fVcPJPbVl?=
 =?us-ascii?Q?c4mDBVna7dxDI119dSlAUJhhMWD/vjfMVhRKjS0ePKQlB1Z1SJLyqo7D46F0?=
 =?us-ascii?Q?ilPOToQTChTI7gDzA9i/FU5MKeKYv8h5uqE9OgGG9OtzkgiY8Ne07ST3BRea?=
 =?us-ascii?Q?/05qSWesSQAYOq/KcSgqG0kYA/ml2KhszyYMJC9l412Ro7WuVmFUsDVjg5eF?=
 =?us-ascii?Q?8GTACfcpRcisMalhHF85/UO85v7Mg/m727VkY6X6/GYaUl5ZsuMzQm0edaKJ?=
 =?us-ascii?Q?oFjR0bCWe+5Vo5iU6uRPZ++ZHLRhDAlEFI590VFhsadFpWH/oUj0MhqISX6B?=
 =?us-ascii?Q?vMXgtHHOGHJogz7MXPIcsJmWgM/xP+M4GAuassQ/w1CAon1ROEhN+VVKuJoq?=
 =?us-ascii?Q?aIXqylmvF28/P8FpMu1vB4TI6d2ia9WL3iQcVlq0Tvdv3kKOXQyzsT6A61kj?=
 =?us-ascii?Q?PR7EA9RTGVxx/bhve1jDz5G4yRMfXzCn5J+mdI5r+/MS9M9RPTRrZaQhx/Dj?=
 =?us-ascii?Q?m0EKj264YxmQpG5FX+u0HqQYD6JxhFpMJkWEBEPg7KkHXFrFuTpdXHT4doJ7?=
 =?us-ascii?Q?CeRj5DnOGFWUGWdTE25+3IiH7MBrgDz9Hv6YGgwg80aX8lY3+yNnB+R2t8nZ?=
 =?us-ascii?Q?gQWuehGmXKn79yWuXhR6aRI1GAW2nAwn6V08Q1BoyE/Cc9+XMn+AvOwEUzvO?=
 =?us-ascii?Q?p7Nls4cs7s6g8Rlcv2EjRwVeXYBzMMW/THUvntmlm6llid/SDENrSbMIgR2X?=
 =?us-ascii?Q?q/8ujRGRsh0OpgsP6S5w3gjdebOUtY2zwNyza8nsEZ8+S6VPClbTvM8yz3Yz?=
 =?us-ascii?Q?0T/MHutUGn284yowRYaz/TmiBAxcrn3VA+hdyO/6y0JM8lkPaRyjJu56P/TG?=
 =?us-ascii?Q?86AQ7qMvkK2IvVG5HEKkLn8urE23ge6jEJtrZhvl2OVXmJzt+7RKzVtwvAez?=
 =?us-ascii?Q?kXNUkzZOEuNrlvt54kkwQeZd3oZIH6obKITTPSzcX7v6nftkGuY2PUZRkeyP?=
 =?us-ascii?Q?Hg=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: H+IDZm11rxetTJc7xbL8vJVjrQ0GroBq+l1QFOqSkWtN8VGRKl+wBnVPeKlFFYDjO+jUeqQBbgRG3/36ask2FMb6MkMbYV45klmAYc+0dP++Q9QckdgkHjj+nP1SnzX9s3TP3PIQd8NDLaTc+5pQZeXK7kknzUqxh8ghVdsiBF4WT9wGy1vAM/EXr3HiXbFlvEr/Q7sbzvCDW2+LE6T5puwncvb3REEDd7B0CR6bqiMHhcOaNDhEylvQMcQwuudSklRXHb0+wZ0bZr9CqGssBU12L4sRMojIzVkQWn50z1y9kb6JENLGkzDKotC4CgZxxbSfMDCEa0Pzfxl3BAUxyoedoVz+cSsG2MMPSSFi53TEF+Feh0cqs1PZugyAc6CWut8hui4rS4zyVhpH0w06D/Y8ycjWhVbzOmCa+zdk9P02y9sNtEXYnL+LFeBZLJ1/NL7SUU58F3VfghmrnTCreB5c6xk403ScOiJxZgSuZFIAO1N8Wlu+aKk/AgrGtWQdK2ooIXOL86HMDhtQS0K3U6iGOR0NvqvPWnqNFi99WS+DRZ0h0MNRA0NR+lRMZQG/KCZ2ce+i44gY6TeJkfFAlQoeZ9AcczALuWm91QiPNfAbvFl6bIucmbjAF4h2MFiyQjx5kPluxZActFZfmALn895K5emyZeJ8fje6BoUSq6krSo9aTUzEGzzSZVyVZG9EpFTdDo8SREY7FDY4OxywvJsetPgxAd98nFBDx34CXtNeX6l23Jt40olMyd6aS3XnZBgy0La3vOyz4y+GmrzhncB/ZosZ92D6APlp7y4tTEMpqtESxFfN1gMS3oJvwVnMjtmbDkXaDNsa4BHaDDmw6Iicb1GmAcdaxCKX1QS6VlYtvemVO29cnJa6+eHF5zOgJVcTpJciJqm8S3abTXmydQ==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: d738d6c0-c0d5-4af4-cdac-08dafb03342e
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 20 Jan 2023 16:27:20.5927
 (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: 8yk0PWXKJ3Xqnw3IgASwUnw4/iy9LjhXOE1qKTceDdc85iqdN+nxvptVsyhNX28wFv2fv7Up2J39sbgItP4DAg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR10MB6026
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.219,Aquarius:18.0.930,Hydra:6.0.562,FMLib:17.11.122.1
 definitions=2023-01-20_09,2023-01-20_01,2022-06-22_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 phishscore=0
 malwarescore=0 spamscore=0 mlxlogscore=999 mlxscore=0 adultscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2212070000 definitions=main-2301200157
X-Proofpoint-ORIG-GUID: 3JfszxDPea2d_D0Qe1bDSsUwlTQiJ6mL
X-Proofpoint-GUID: 3JfszxDPea2d_D0Qe1bDSsUwlTQiJ6mL
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 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

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

Add a testcase to ensure the iterator detects bad states on modifications
and does what the user expects

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/test_maple_tree.c | 72 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index ec847bf4dcb4..3d19b1f78d71 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -1709,6 +1709,74 @@ static noinline void check_forking(struct maple_tree *mt)
 	mtree_destroy(&newmt);
 }
 
+static noinline void check_iteration(struct maple_tree *mt)
+{
+	int i, nr_entries = 125;
+	void *val;
+	MA_STATE(mas, mt, 0, 0);
+
+	for (i = 0; i <= nr_entries; i++)
+		mtree_store_range(mt, i * 10, i * 10 + 9,
+				  xa_mk_value(i), GFP_KERNEL);
+
+	mt_set_non_kernel(99999);
+
+	i = 0;
+	mas_lock(&mas);
+	mas_for_each(&mas, val, 925) {
+		MT_BUG_ON(mt, mas.index != i * 10);
+		MT_BUG_ON(mt, mas.last != i * 10 + 9);
+		/* Overwrite end of entry 92 */
+		if (i == 92) {
+			mas.index = 925;
+			mas.last = 929;
+			mas_store(&mas, val);
+		}
+		i++;
+	}
+	/* Ensure mas_find() gets the next value */
+	val = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, val != xa_mk_value(i));
+
+	mas_set(&mas, 0);
+	i = 0;
+	mas_for_each(&mas, val, 785) {
+		MT_BUG_ON(mt, mas.index != i * 10);
+		MT_BUG_ON(mt, mas.last != i * 10 + 9);
+		/* Overwrite start of entry 78 */
+		if (i == 78) {
+			mas.index = 780;
+			mas.last = 785;
+			mas_store(&mas, val);
+		} else {
+			i++;
+		}
+	}
+	val = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, val != xa_mk_value(i));
+
+	mas_set(&mas, 0);
+	i = 0;
+	mas_for_each(&mas, val, 765) {
+		MT_BUG_ON(mt, mas.index != i * 10);
+		MT_BUG_ON(mt, mas.last != i * 10 + 9);
+		/* Overwrite end of entry 76 and advance to the end */
+		if (i == 76) {
+			mas.index = 760;
+			mas.last = 765;
+			mas_store(&mas, val);
+			mas_next(&mas, ULONG_MAX);
+		}
+		i++;
+	}
+	/* Make sure the next find returns the one after 765, 766-769 */
+	val = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, val != xa_mk_value(76));
+	mas_unlock(&mas);
+	mas_destroy(&mas);
+	mt_set_non_kernel(0);
+}
+
 static noinline void check_mas_store_gfp(struct maple_tree *mt)
 {
 
@@ -2659,6 +2727,10 @@ static int maple_tree_seed(void)
 	goto skip;
 #endif
 
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	check_iteration(&tree);
+	mtree_destroy(&tree);
+
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_forking(&tree);
 	mtree_destroy(&tree);
-- 
2.35.1