From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3F22EC77B61 for ; Fri, 28 Apr 2023 07:06:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9EE8A6B0071; Fri, 28 Apr 2023 03:06:36 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 99F216B0072; Fri, 28 Apr 2023 03:06:36 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8406A6B0074; Fri, 28 Apr 2023 03:06:36 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 717646B0071 for ; Fri, 28 Apr 2023 03:06:36 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 394EC1C6039 for ; Fri, 28 Apr 2023 07:06:36 +0000 (UTC) X-FDA: 80729916792.21.51902A6 Received: from mail-pf1-f193.google.com (mail-pf1-f193.google.com [209.85.210.193]) by imf20.hostedemail.com (Postfix) with ESMTP id 4F3DB1C0017 for ; Fri, 28 Apr 2023 07:06:33 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=iXQevaYP; spf=pass (imf20.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.210.193 as permitted sender) smtp.mailfrom=perlyzhang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1682665593; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=9xQ4i41yadNXZoMMfJR6ndq8RUGvvWSipx17IUzZw44=; b=cLXo9k/PEENpw7hNinqkpVwhm6uB/o1BP7XQTwv+v8gopzbeh6ndlL0MOqeRSnQEn9q4aJ NcvJJofzURCceBvDp7uRAFH6ZmsxJNyImf3OASbc9ZY7Gr3HtD7qXcZGMU60yJhz4kRWcV 4bBOtibeXcFoqmzUBZtTCHwnNatcXNo= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1682665593; a=rsa-sha256; cv=none; b=OvO2Hstsd7MSvTkzlqKIBWMxBBa8R61OfLNsocxab0fYQABWmrgQT4D3r/TUeUNUvw0lx5 eGCdC3r/2Jdj6lX6nAiH4Nv6Mw+LAj/Qw0/WrzIWTSjZ8nMNdbnXEscC5m0GvxTHrieuId 3UMY4rC4f1poeu3eHyAxEYHInlB3uyI= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=iXQevaYP; spf=pass (imf20.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.210.193 as permitted sender) smtp.mailfrom=perlyzhang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-pf1-f193.google.com with SMTP id d2e1a72fcca58-63b64a32fd2so11725909b3a.2 for ; Fri, 28 Apr 2023 00:06:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1682665592; x=1685257592; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=9xQ4i41yadNXZoMMfJR6ndq8RUGvvWSipx17IUzZw44=; b=iXQevaYPY8i3iz3s9iVGQV/tD++3V73SujgAUJxBWB6lgovu7UOaSflc7KM/dv74b8 +7Pshzhao4ftWLuyLS+XNcjQ/BYqwwF6pIHYreX1FYY+a8gQbQZBD3kAJOaQj4zgyrh2 O3P9dvz3jhvw7c8AY16YGSAsDwk1dmmGmi7ldCJf7WNCVyVlTWJvaWIlQBRzQSBBgEy/ lSTc89mVQuP3c9aV4T0k6DUiL+c2LsDwXuyAdUy8EnrdYh6fJRFnxtpHC41JJMIzrLYa 2CB8kmA0IzZjoOHyAPlLDCxn8ajn4IIyWvEDSI0+JmWYVAeX51qi7vp48FK8v8VfQTne dW2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682665592; x=1685257592; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=9xQ4i41yadNXZoMMfJR6ndq8RUGvvWSipx17IUzZw44=; b=LRzfaxD9TtSSS2kutzaG0qiJ1oQ6xh+RA+xdKG7Bt17YF4331YykCy9bbKQdsBRmNH GJ9eidw6DdHLsymGIluvbwnX8fWUfPymBBd7TNGw7JEB2FrhPafCnGtB1wxo12lbms88 k0o8EGnxSeTa53tk5tON03i+75yQGk6bLOpXaLwYp3KKRIl00x7FAXcMSOqGMnpt5Q9s HXv6dqADQCN8I5xYADWCgfEJOYECVwDwoYef9bh4IbGpRO3Q8mK3Fh1O0ACvD3s6ZZEM /R4DBMiLU95FUvntPB6/lnX0gjUxsf0OFQ3Fa1ZRrJ57yMulRAVMC7SLkn54sgbfoAMv 0dJg== X-Gm-Message-State: AC+VfDwbugqtoJm1h3LB+Vqx4ERbB3dVi62LeuDYOFIBpNk76l6iabD1 j3yjBBk4nP99O0IrRkZCE7E= X-Google-Smtp-Source: ACHHUZ43ezaN7TXWkuh7bvquJ5ITlCH6GUi6PqnfVF/+9iHZNU0GWP8pdsKUe5xyq1GgNKPvTi41yw== X-Received: by 2002:a05:6a00:1806:b0:641:d9b:a458 with SMTP id y6-20020a056a00180600b006410d9ba458mr7416151pfa.18.1682665592004; Fri, 28 Apr 2023 00:06:32 -0700 (PDT) Received: from [10.200.10.82] ([139.177.225.232]) by smtp.gmail.com with ESMTPSA id b200-20020a621bd1000000b0063b1bb2e0a7sm14242055pfb.203.2023.04.28.00.06.29 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 28 Apr 2023 00:06:31 -0700 (PDT) Message-ID: Date: Fri, 28 Apr 2023 15:06:27 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.10.1 Subject: Re: [PATCH 28/34] maple_tree: Revise limit checks in mas_empty_area{_rev}() To: "Liam R. Howlett" Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org, Peng Zhang , Andrew Morton References: <20230425140955.3834476-1-Liam.Howlett@oracle.com> <20230425140955.3834476-29-Liam.Howlett@oracle.com> From: Peng Zhang In-Reply-To: <20230425140955.3834476-29-Liam.Howlett@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspam-User: X-Rspamd-Queue-Id: 4F3DB1C0017 X-Rspamd-Server: rspam09 X-Stat-Signature: 1ykrc63p15tcac34t6e84ucnbfdhtrig X-HE-Tag: 1682665593-370967 X-HE-Meta: U2FsdGVkX1+8mBaoMplYsKO4GfCGnL7nnLz8As0Tfhy0GBXHTYOP0ll9DDU7eM3l4WVM1vwhRgWkvIkQUdrbnqww+Gk3m80/WOHDXJlAJE9C7pSnhLjnFNZQP4ISDdO1ZAGCEgQ4bA8Iov+Su6VYwlJJPw+0h5vKUklWt7D4vaSdgXjep65cJWW43odnmu0GlPVpdzQIImVa/Y7YEtYAecARbKPl+dPWREqAbgoFoUWSGLsg7r7jyt1ZIKyyxQ0IRJkkVxR7QC0D+M7baZmDpYk1Shi1ikGst6kDKAYTNt5We+qEW3GROSWuKKUsslDMkSv/6zt+Yxp9L9d2wc1S0JsEA6VDXHRo/zHjJ91wxHjQnUv4JFs7GhiQm5/EK2ILopmNqdajBbhB/QZsACpQsg+yUOmAWOnIOtxsrkpBXW7Gs0fldmISlxi/BkWBK9QVwNQ6F/+SXYxvY8wQS3sSaMPlA075+FPnWm5Xzudn29wRm+kdrKEMqR++zAhw6L3mDzit3LIUITefNLhBmbZ3WjoI8E7UZq3+T129u+sSTe9xdLMmong9pihQykQtAj43g+PNYB2G/7ovOfG9TKGqRxiDZ6BtZ9AVa2KTX2nbQM50XjvUd0VEMDIwArlnvHAOovcLO/DaO1Ug3MCc+eb3hCUfbF2a6/owRph68RcnOzkz2gZTFcyH2trjqCWP9addIog9gYcibJi2a3BJDyOhYRMhyc8LKW3BZl2rnFo66IWcqKKXVa6QFl4Fr5gjXWnHh2pQuHvhbStX2jt4UIpHwQ9+s2Iub62w0keYbwOCYxFNcNHKAjHPrIDUx315uPscT4QJltEWODjCO6l4n3tR57V81sxlUDDfspl5Vk0AizT30t42zB3HAMmLlE9W9k8/DZHi2nysyxxwt9Ht8K/PCoxrvY92AHlj+J6GCHV5ohfWovRriHHoC29LOqs+tBCoaYCGO/W2PvyG6A+Cmb3 77Vgi5bA dfmL2A295DskUvbAwko8t64D2Kcyu3gfTUCLyox5JqaaR55fOTlSYRisW5qyFVXoM68CPfGTg2jOsssnKkaYxgASqm2umrH3CBNVtIx6yt4U7qt/XwPc0tdQG5LsqE+Ru3ts/q/UDbe3VpPF/jW3TE9JKFMq8Zcbk9ZBkv0+NXQYJGv2+V44Q3ScoVGPP/G0t8xeegGT6JRDVGoun0Kl2ec/6Xi3YBpxNyvezBjDVQX1OabWHuqXixEp/DECC4fqynnjeqnnZkxNyDmLzMjNBGcMtg25N9PYcU5pys/mG38R3dRS2E3uP9/LTDf2RIit1sTHnX/kUhw6v9lZAB6IDr7KkwR7huftwJiGlJodECiLCxE3h1ypwbBcgOcwQCDhlQPLN1yXjOnl72zkOG78+2uPTcutxYHawj0HvHbluHk6HP3aA+OgvPLW+Eieq0BbltymnhVnBj9NTcSFeqgjv7RgyPNJwZGLFkJYSQgBRSRcni+/4WwlhWn+nDlD7Lx4/b47zTY7TfzG8AiRgk6Sjf8u1E9081Y4Msqf5VOg54JfUd7MhNindKiW9Ug== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 在 2023/4/25 22:09, Liam R. Howlett 写道: > 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 > Signed-off-by: Liam R. Howlett Reviewed-by: Peng Zhang Except test code. > --- > 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);