linux-kernel - Re: [PATCH] maple_tree: update mas_next[

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <qc63muaz2hq5pcew3xecs36zsxeui6qs7govowmmraj2jdbdxs@cra4qe552lfj>
Date: Mon, 9 Feb 2026 18:01:29 +0000
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Alice Ryhl <aliceryhl@...gle.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>,
        Andrew Ballance <andrewjballance@...il.com>,
        maple-tree@...ts.infradead.org, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH] maple_tree: update mas_next[_range] docs

* Alice Ryhl <aliceryhl@...gle.com> [260209 08:23]:
> On Sat, Feb 07, 2026 at 08:16:56AM +0000, Liam R. Howlett wrote:
> > * Alice Ryhl <aliceryhl@...gle.com> [260204 15:29]:
> > > On Mon, Jan 26, 2026 at 03:20:17PM -0500, Liam R. Howlett wrote:
> > > > * Alice Ryhl <aliceryhl@...gle.com> [260121 04:56]:
> > > > > On Tue, Jan 20, 2026 at 12:54:47PM -0500, Liam R. Howlett wrote:
> > > > > > * Alice Ryhl <aliceryhl@...gle.com> [260118 06:00]:
> > > > > > > If you read the docs, it sounds like the difference between these
> > > > > > > functions is whether mas->index and mas->last are updated. However, if
> > > > > > > you read the implementation, you will instead find that the difference
> > > > > > > is whether NULL entries are skipped.
> > > > > > 
> > > > > > This is not the intent.
> > > > > > 
> > > > > > mas_ should return special values including the XA_ZERO_ENTRY.
> > > > > > 
> > > > > > mas_next() should get the next non-NULL value.
> > > > > > 
> > > > > > mas_next_range() should advance the maple state to the next range,
> > > > > > regardless of what is in the range (NULL, special, or a regular entry).
> > > > > > 
> > > > > > Both should update the mas->index and mas->last values, if it moves
> > > > > > (ie, no error state is encountered).
> > > > > 
> > > > > I guess I'm a bit confused about the difference between XA_ZERO_ENTRY
> > > > > and returning NULL. Isn't the case where we return NULL when a slot has
> > > > > been reserved but not inserted yet?
> > > > 
> > > > mas_ will return the special entries.
> > > > 
> > > > mtree_ will return NULL on special entries.  I think this is just
> > > > mtree_load().
> > > > 
> > > > If you want to use your own locking and use mas_, then you can filter
> > > > out the special entries yourself.
> > > > 
> > > > If you want to use the normal api, then the special entries are filtered
> > > > for you.
> > > > 
> > > > This way you can mix/match the apis but the noral api still remains
> > > > simple to use - even if there are advanced users that mixed in.
> > > > 
> > > > The idea is that if you're using the advanced interface and storing
> > > > special entries, then you probably want to do something different on
> > > > those entries - at least sometimes.
> > > > 
> > > > > 
> > > > > Like the docs, you use "get" vs "advance" wording here, but I don't
> > > > > think there's any difference behavior-wise? Is one intended?
> > > > 
> > > > On return type, no, there isn't a difference.  The difference is where
> > > > the mas points in the end (mas->offset, mas->index, mas->last).
> > > > 
> > > > If a NULL is encountered bu mas_next(), then we proceed to the next slot
> > > > (which must have a value, if there is a next slot).  So, mas_next() will
> > > > always return the next entry until there is not a next entry - then it
> > > > returns NULL.  Note that mas_next() takes an 'end' value where we'll
> > > > stop advancing slots regardless if there are values.
> > > > 
> > > > If a NULL is encountered by mas_next_range(), then we return the NULL.
> > > > So, in this way, we can move to the next range even if it's NULL.
> > > > 
> > > > I hope this makes the difference more clear?
> > > 
> > > Yes.
> > > 
> > > But I guess the docs should still need to be updated? Right now, both of
> > > them say "Can return the zero entry.", but one of them can't because it
> > > skips them.
> > 
> > Neither of the ones you are updating should skip the zero entry as they
> > are both the advanced interface.
> 
> What do you call the entries that mas_next() skips? You know, the ones
> where it would otherwise return NULL.

mas_next() only skips real NULLs.  If there are special entries, then
they are returned.

mas_next() moves to the next non-null slot.  Special entries are not
considered null by the advanced mas_ interface.

mas_next_range() moves to the next range, regardless of what is there.