From: "Liam R. Howlett" <Liam.Howlett@oracle.com> To: Andrew Morton <akpm@linux-foundation.org>, Kees Cook <keescook@chromium.org> Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Mark Brown <broonie@kernel.org>, Naresh Kamboju <naresh.kamboju@linaro.org>, linux-kselftest@vger.kernel.org, Linux ARM <linux-arm-kernel@lists.infradead.org>, kft-triage@lists.linaro.org, regressions@lists.linux.dev, Will Deacon <will@kernel.org>, Catalin Marinas <catalin.marinas@arm.com>, Dan Carpenter <dan.carpenter@linaro.org>, Eric Biederman <ebiederm@xmission.com>, linux-next@vger.kernel.org, "Liam R. Howlett" <Liam.Howlett@oracle.com> Subject: [PATCH] maple_tree: Fix mas_prev() state separation code Date: Thu, 7 Dec 2023 14:33:19 -0500 [thread overview] Message-ID: <20231207193319.4025462-1-Liam.Howlett@oracle.com> (raw) In-Reply-To: <20231207014104.n6vul2ylgqjnsfia@revolve> mas_prev() was setting the ma_underflow condition when the limit was reached and not when the limit was attempting to go lower. This resulted in the incorrect behaviour on subsequent actions. This commit fixes the status setting to only set ma_underflow when the lower limit is attempted to be decremented, and modifies the testing to ensure that's the case. Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> --- Andrew, This should be clean to squash into 7f79fdb1d94d7 ("maple_tree: separate ma_state node from status.") which is currently in your mm-unstable branch. Thanks, Liam lib/maple_tree.c | 16 ++++++++++++---- lib/test_maple_tree.c | 9 +++++++-- 2 files changed, 19 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 89f8d21602774..47f2a7a973852 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4432,6 +4432,9 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) mas->last = mas->index - 1; mas->index = mas_safe_min(mas, pivots, mas->offset); } else { + if (mas->index <= min) + goto underflow; + if (mas_prev_node(mas, min)) { mas_rewalk(mas, save_point); goto retry; @@ -4452,15 +4455,15 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry; - if (mas->index <= min) - mas->status = ma_underflow; if (likely(entry)) return entry; if (!empty) { - if (mas_is_underflow(mas)) + if (mas->index <= min) { + mas->status = ma_underflow; return NULL; + } goto again; } @@ -4596,7 +4599,7 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry; - if (pivot >= max) { + if (pivot >= max) { /* Was at the limit, next will extend beyond */ mas->status = ma_overflow; return NULL; } @@ -4611,6 +4614,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) else mas->last = mas->max; } else { + if (mas->last >= max) { + mas->status = ma_overflow; + return NULL; + } + if (mas_next_node(mas, node, max)) { mas_rewalk(mas, save_point); goto retry; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 15fbeb788f3ac..29185ac5c727f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3294,8 +3294,8 @@ static noinline void __init check_state_handling(struct maple_tree *mt) MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas)); - /* next:active ->active */ - entry = mas_next(&mas, ULONG_MAX); + /* next:active ->active (spanning limit) */ + entry = mas_next(&mas, 0x2100); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); @@ -3360,6 +3360,11 @@ static noinline void __init check_state_handling(struct maple_tree *mt) MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); + MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */ + entry = mas_prev(&mas, 0x1200); /* underflow */ + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.index != 0x1000); + MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_underflow(&mas)); /* prev:underflow -> underflow (lower limit) spanning end range */ -- 2.40.1
WARNING: multiple messages have this Message-ID (diff)
From: "Liam R. Howlett" <Liam.Howlett@oracle.com> To: Andrew Morton <akpm@linux-foundation.org>, Kees Cook <keescook@chromium.org> Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Mark Brown <broonie@kernel.org>, Naresh Kamboju <naresh.kamboju@linaro.org>, linux-kselftest@vger.kernel.org, Linux ARM <linux-arm-kernel@lists.infradead.org>, kft-triage@lists.linaro.org, regressions@lists.linux.dev, Will Deacon <will@kernel.org>, Catalin Marinas <catalin.marinas@arm.com>, Dan Carpenter <dan.carpenter@linaro.org>, Eric Biederman <ebiederm@xmission.com>, linux-next@vger.kernel.org, "Liam R. Howlett" <Liam.Howlett@oracle.com> Subject: [PATCH] maple_tree: Fix mas_prev() state separation code Date: Thu, 7 Dec 2023 14:33:19 -0500 [thread overview] Message-ID: <20231207193319.4025462-1-Liam.Howlett@oracle.com> (raw) In-Reply-To: <20231207014104.n6vul2ylgqjnsfia@revolve> mas_prev() was setting the ma_underflow condition when the limit was reached and not when the limit was attempting to go lower. This resulted in the incorrect behaviour on subsequent actions. This commit fixes the status setting to only set ma_underflow when the lower limit is attempted to be decremented, and modifies the testing to ensure that's the case. Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> --- Andrew, This should be clean to squash into 7f79fdb1d94d7 ("maple_tree: separate ma_state node from status.") which is currently in your mm-unstable branch. Thanks, Liam lib/maple_tree.c | 16 ++++++++++++---- lib/test_maple_tree.c | 9 +++++++-- 2 files changed, 19 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 89f8d21602774..47f2a7a973852 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4432,6 +4432,9 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) mas->last = mas->index - 1; mas->index = mas_safe_min(mas, pivots, mas->offset); } else { + if (mas->index <= min) + goto underflow; + if (mas_prev_node(mas, min)) { mas_rewalk(mas, save_point); goto retry; @@ -4452,15 +4455,15 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry; - if (mas->index <= min) - mas->status = ma_underflow; if (likely(entry)) return entry; if (!empty) { - if (mas_is_underflow(mas)) + if (mas->index <= min) { + mas->status = ma_underflow; return NULL; + } goto again; } @@ -4596,7 +4599,7 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) goto retry; - if (pivot >= max) { + if (pivot >= max) { /* Was at the limit, next will extend beyond */ mas->status = ma_overflow; return NULL; } @@ -4611,6 +4614,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) else mas->last = mas->max; } else { + if (mas->last >= max) { + mas->status = ma_overflow; + return NULL; + } + if (mas_next_node(mas, node, max)) { mas_rewalk(mas, save_point); goto retry; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 15fbeb788f3ac..29185ac5c727f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3294,8 +3294,8 @@ static noinline void __init check_state_handling(struct maple_tree *mt) MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_active(&mas)); - /* next:active ->active */ - entry = mas_next(&mas, ULONG_MAX); + /* next:active ->active (spanning limit) */ + entry = mas_next(&mas, 0x2100); MT_BUG_ON(mt, entry != ptr2); MT_BUG_ON(mt, mas.index != 0x2000); MT_BUG_ON(mt, mas.last != 0x2500); @@ -3360,6 +3360,11 @@ static noinline void __init check_state_handling(struct maple_tree *mt) MT_BUG_ON(mt, entry != ptr); MT_BUG_ON(mt, mas.index != 0x1000); MT_BUG_ON(mt, mas.last != 0x1500); + MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */ + entry = mas_prev(&mas, 0x1200); /* underflow */ + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.index != 0x1000); + MT_BUG_ON(mt, mas.last != 0x1500); MT_BUG_ON(mt, !mas_is_underflow(&mas)); /* prev:underflow -> underflow (lower limit) spanning end range */ -- 2.40.1 _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
next parent reply other threads:[~2023-12-07 19:33 UTC|newest] Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top [not found] <20231207014104.n6vul2ylgqjnsfia@revolve> 2023-12-07 19:33 ` Liam R. Howlett [this message] 2023-12-07 19:33 ` [PATCH] maple_tree: Fix mas_prev() state separation code Liam R. Howlett 2023-12-07 21:04 ` Kees Cook 2023-12-07 21:04 ` Kees Cook 2023-12-08 17:54 ` Liam R. Howlett 2023-12-08 17:54 ` Liam R. Howlett
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20231207193319.4025462-1-Liam.Howlett@oracle.com \ --to=liam.howlett@oracle.com \ --cc=akpm@linux-foundation.org \ --cc=broonie@kernel.org \ --cc=catalin.marinas@arm.com \ --cc=dan.carpenter@linaro.org \ --cc=ebiederm@xmission.com \ --cc=keescook@chromium.org \ --cc=kft-triage@lists.linaro.org \ --cc=linux-arm-kernel@lists.infradead.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-kselftest@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=linux-next@vger.kernel.org \ --cc=maple-tree@lists.infradead.org \ --cc=naresh.kamboju@linaro.org \ --cc=regressions@lists.linux.dev \ --cc=will@kernel.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.