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,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>
Subject: [PATCH 28/34] maple_tree: Revise limit checks in mas_empty_area{_rev}()
Date:   Tue, 25 Apr 2023 10:09:49 -0400
Message-Id: <20230425140955.3834476-29-Liam.Howlett@oracle.com>
In-Reply-To: <20230425140955.3834476-1-Liam.Howlett@oracle.com>
References: <20230425140955.3834476-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?kYoRzLumolKC51FHmeyiwKkwbMNKQSB6yUYY1Jeweok+GHC+A9h0zRu/O0IB?=
 =?us-ascii?Q?6yTp+bJNlLwMcCEVbCq9jvedmhqBbp0YwZjVW9A6crPr1I2SyurE/hAog21S?=
 =?us-ascii?Q?rFwGJOHvBu0KMBxgK18L3t/S5CZwOU3M1cbpcY5/LQFL76Ahfbl2Q3/L/W6A?=
 =?us-ascii?Q?ZJAEpt/aKOanUflCKvq60nUM2TxSLOzyNqujxZR1RSgMFXv8UE859MxNiYVE?=
 =?us-ascii?Q?8KvcQclVnhKZnR7Z61aJQlkz0YE7yagHHnrgII+OOpvL8bXLkh8x+fvetxvl?=
 =?us-ascii?Q?i7ChHQegiAAkLaTRLfabw3uGZLv3Gye3tKC13EoBvT2IjH8p7DmFhoZxnrIa?=
 =?us-ascii?Q?KruRfbgYoxkq9U27cqyfcDwCqOnAWb/+Hb/lZWCC9Lcsg4wBgH8yMmvs7EmX?=
 =?us-ascii?Q?ns3hD1iHqd14fkuFnddQbEFylkrcyZFLil1KBbeQYPPGqZJlpD4XQA8ZL6Yo?=
 =?us-ascii?Q?58zZyc4embZz6LWFvXg2NmOV/O9hAjwxTaLnE4O2ooz3Em2lrVuc+CXj6Sex?=
 =?us-ascii?Q?+OOIagYRrw/+gkFEzDVupA8RalTJ4pyLqSz2YI0+ahGZ6vc0ktOrCo6g9Hut?=
 =?us-ascii?Q?IKGs0ZCLNUBw/CJIhLJM0Zk7kGts1+HsKlXoW+q9hVsJK3XuDMF9RrUUEkba?=
 =?us-ascii?Q?MOCbmW4u9zAjuorqjhr0Tim7jHtbj9sICd30RRtBshmhAjMVtIlCjg7mkNhZ?=
 =?us-ascii?Q?qD7cw4VmgIc/bNt70jjWkJ5mRK4C1V4w/+cBmPwNBpAbnjjw66vQeM60KvXo?=
 =?us-ascii?Q?uBEiI08jnTSXWJTy0K0tArL5UhSR8BVU+aqss8dCCdKwiaiAPsuiwNyMDKi5?=
 =?us-ascii?Q?3hYJETKkxHU6+9CEtSXTO4zQEYQTU684MkwlzmG5JyQWxmU538C+v7J+3bcj?=
 =?us-ascii?Q?UF1x0DuAwmlCXlMEjExT2Zp2xvpq1HKVH51VY+VREmmf8zgcJcWOINVvNXHH?=
 =?us-ascii?Q?23lmXffdS8EVr87URcKWv2PTurh9TRAv8/8FHsBAgmG3DGHKTGWNliOKtaZb?=
 =?us-ascii?Q?7t69c7tOSudtfGB65kzKHHSBIoNOlfgzldUUS0U93ZteVdxq5oI5epyZ4Iv9?=
 =?us-ascii?Q?HYQc5TfqUhuCnhrginFv8fJG3752qgf3goQgp0CgjMAiEf/SxI70jYlKNzBq?=
 =?us-ascii?Q?9oMIBEiGgDhntIQWgWc3rzsNkw1MIhdOngcIDpcHE9XbGQlnX3ZaqPQw1WDT?=
 =?us-ascii?Q?fYXE169q4hPkb31v4+3zdtsnKr17pBMQAwfo28poGWYY15Z7am+EfMvRD2uO?=
 =?us-ascii?Q?2/gw/0aEHBYPVgMaw6TTFtwS7s5fhgR7adu+hopRcNc/qWwQXiAtrfpXLlhg?=
 =?us-ascii?Q?L6wB5Cdmkp1G35gznnzxf758+j98WzGgotsKptHIeJcmrmyF9/ry6UVn1vVB?=
 =?us-ascii?Q?cSrYmfbWD40DsCyjrPt26K3MhbX2kROFal+E0JNOtsz3TbQa2O5FAGXj4sS/?=
 =?us-ascii?Q?SIFeuQgqXLh9i76HP3c0gcfbtQPXDaNb60xBv3AVGclO1Nc24HKPcNCOd+bL?=
 =?us-ascii?Q?LtEuZhKvx+cCfr0Vf89K0MjzJ4Zb/Fg9z32hLkyRgrxAV4FON7Gf4/jBAO1y?=
 =?us-ascii?Q?c4MsZXgx+dHZFb119UI4+PDznaLtVCiH6MyY37AmK2ONowGDEY5RtrFX6e6j?=
 =?us-ascii?Q?Vw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?6N6d2R+FGZS+Ded0nvSdXEoS8W23cju8DayuWrM/dpG1gKm0oPi2cz5A+Kti?=
 =?us-ascii?Q?8HNc6wn8fKal8lG8tw4IX211U2zdD+TSfY2uvV1jItPjjqelWE6iuVMkwn/O?=
 =?us-ascii?Q?lA5c0fNK2WktiXMa15hUnaN2OLX1pPdgpRWLB7+ab69bTtA9ZMMUQTQpMT3m?=
 =?us-ascii?Q?xLy0SL2Q4wriiCK0gghZXhGTTcQqcbtcFd2vQSBswBfMPgJqbR+U6LlRBQLD?=
 =?us-ascii?Q?QXiaRcHtz4uDjHIo+aJw6VpT4/caFx1VIS9cmw/Q2Jb7S1V+XhcEaIoun899?=
 =?us-ascii?Q?Amv/iIRPN5DldFDd1r7FFuwYmzeBXQCicFYCmz0KcUF4oYw+nnKtsBnrLMzG?=
 =?us-ascii?Q?DkTo8YyX8jVZY3OlF3YBp6rRW1dcwHy65azzEaq4rChZPah845/gbLGj8flH?=
 =?us-ascii?Q?2N8+XAo1Qi/RT3WtBwodYtH3cywv0s2zS0WmjWAJMqlHubBRA0AqPWqDCHCr?=
 =?us-ascii?Q?AfmXCxetXQUsmoL4h4NL5gHKWFA3gMwYvgw8itf3rB+4GoAc4REnezxa2+D0?=
 =?us-ascii?Q?f4jYnnhfcaVZOJOCcSP5Ft5M7ggJR9o4lfOl2tOqtL3XAIs8zDC3P5yzfYIH?=
 =?us-ascii?Q?tm7NrubZqGH7jtSAqFAjw7zUS2YQSmwdi8ATNhjMjUDmIeShp+No21wiLi2q?=
 =?us-ascii?Q?/trrrde4tvfsVv+umIQc2mTNOlcLqNN7cyRCj8dan2fTBd8x4obftfdWDMED?=
 =?us-ascii?Q?PC5BhrUMyld1SwQx5rv8KVYDOmaDXKyXWwGDR1qz49K0f1K2uXUCFUORn8MS?=
 =?us-ascii?Q?aaGx2NK9z4HWCGXDb7olSIVbB/XaneEZdozUxqzqabCpJZTLu9JzMfukOB9a?=
 =?us-ascii?Q?4yHJB1eQfkIrqAQJkRZMcx6Cv5dp4JwayGe7BDfPgTuL6s1p8Z6IkPMG3sqK?=
 =?us-ascii?Q?dR71MRLnJ5ccX8l9D3UjRF7nKPYY5BwzKTkDrR6w8tzOCIQ1lJPk/kkXxiQ/?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: b43eeb0d-62b0-4217-3e7d-08db4596f5c5
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Apr 2023 14:11:27.4855
 (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: USK32S/vwbS5JgYh123LPFQnhNFJp06dCVmgqY2cURbe39Jb3iM8xxQyUqg+0nDogjJln7k4xbS5WqiqX7FV3g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO6PR10MB5572
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-25_06,2023-04-25_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 spamscore=0
 malwarescore=0 mlxscore=0 adultscore=0 suspectscore=0 phishscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2303200000 definitions=main-2304250128
X-Proofpoint-GUID: 28P6BtvjL_-cDmSEjHX2Nd7mihE-pkLp
X-Proofpoint-ORIG-GUID: 28P6BtvjL_-cDmSEjHX2Nd7mihE-pkLp
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

Since the maple tree is inclusive in range, ensure that a range of 1
(min = max) works for searching for a gap in either direction, and make
sure the size is at least 1 but not larger than the delta between min
and max.

This commit also updates the testing.  Unfortunately there isn't a way
to safely update the tests and code without a test failure.

Suggested-by: Peng Zhang <zhangpeng.00@bytedance.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c      | 20 +++++++++++++-------
 lib/test_maple_tree.c | 27 ++++++++++++++++++++-------
 2 files changed, 33 insertions(+), 14 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index fe6c9da6f2bd5..7370d7c12fe3b 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5248,7 +5248,10 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 	unsigned long *pivots;
 	enum maple_type mt;
 
-	if (min >= max)
+	if (min > max)
+		return -EINVAL;
+
+	if (size == 0 || max - min < size - 1)
 		return -EINVAL;
 
 	if (mas_is_start(mas))
@@ -5303,7 +5306,10 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 {
 	struct maple_enode *last = mas->node;
 
-	if (min >= max)
+	if (min > max)
+		return -EINVAL;
+
+	if (size == 0 || max - min < size - 1)
 		return -EINVAL;
 
 	if (mas_is_start(mas)) {
@@ -5339,7 +5345,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 		return -EBUSY;
 
 	/* Trim the upper limit to the max. */
-	if (max <= mas->last)
+	if (max < mas->last)
 		mas->last = max;
 
 	mas->index = mas->last - size + 1;
@@ -6375,7 +6381,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, max - size);
+	MA_STATE(mas, mt, min, min);
 	if (!mt_is_alloc(mt))
 		return -EINVAL;
 
@@ -6395,7 +6401,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 retry:
 	mas.offset = 0;
 	mas.index = min;
-	mas.last = max - size;
+	mas.last = max - size + 1;
 	ret = mas_alloc(&mas, entry, size, startp);
 	if (mas_nomem(&mas, gfp))
 		goto retry;
@@ -6411,14 +6417,14 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, max - size);
+	MA_STATE(mas, mt, min, max - size + 1);
 	if (!mt_is_alloc(mt))
 		return -EINVAL;
 
 	if (WARN_ON_ONCE(mt_is_reserved(entry)))
 		return -EINVAL;
 
-	if (min >= max)
+	if (min > max)
 		return -EINVAL;
 
 	if (max < size - 1)
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 345eef526d8b0..7b2d19ad5934d 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -105,7 +105,7 @@ static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
 	unsigned long result = expected + 1;
 	int ret;
 
-	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end - 1,
+	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
 			GFP_KERNEL);
 	MT_BUG_ON(mt, ret != eret);
 	if (ret)
@@ -683,7 +683,7 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
 		0,              /* Return value success. */
 
 		0x0,            /* Min */
-		0x565234AF1 << 12,    /* Max */
+		0x565234AF0 << 12,    /* Max */
 		0x3000,         /* Size */
 		0x565234AEE << 12,  /* max - 3. */
 		0,              /* Return value success. */
@@ -695,14 +695,14 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
 		0,              /* Return value success. */
 
 		0x0,            /* Min */
-		0x7F36D510A << 12,    /* Max */
+		0x7F36D5109 << 12,    /* Max */
 		0x4000,         /* Size */
 		0x7F36D5106 << 12,    /* First rev hole of size 0x4000 */
 		0,              /* Return value success. */
 
 		/* Ascend test. */
 		0x0,
-		34148798629 << 12,
+		34148798628 << 12,
 		19 << 12,
 		34148797418 << 12,
 		0x0,
@@ -714,6 +714,12 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
 		0x0,
 		-EBUSY,
 
+		/* Single space test. */
+		34148798725 << 12,
+		34148798725 << 12,
+		1 << 12,
+		34148798725 << 12,
+		0,
 	};
 
 	int i, range_count = ARRAY_SIZE(range);
@@ -762,9 +768,9 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
 	mas_unlock(&mas);
 	for (i = 0; i < req_range_count; i += 5) {
 #if DEBUG_REV_RANGE
-		pr_debug("\tReverse request between %lu-%lu size %lu, should get %lu\n",
-				req_range[i] >> 12,
-				(req_range[i + 1] >> 12) - 1,
+		pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
+				i, req_range[i] >> 12,
+				(req_range[i + 1] >> 12),
 				req_range[i+2] >> 12,
 				req_range[i+3] >> 12);
 #endif
@@ -883,6 +889,13 @@ static noinline void __init check_alloc_range(struct maple_tree *mt)
 		4503599618982063UL << 12,  /* Size */
 		34359052178 << 12,  /* Expected location */
 		-EBUSY,             /* Return failure. */
+
+		/* Test a single entry */
+		34148798648 << 12,		/* Min */
+		34148798648 << 12,		/* Max */
+		4096,			/* Size of 1 */
+		34148798648 << 12,	/* Location is the same as min/max */
+		0,			/* Success */
 	};
 	int i, range_count = ARRAY_SIZE(range);
 	int req_range_count = ARRAY_SIZE(req_range);
-- 
2.39.2