linux-kernel - Re: [RFC PATCH 2/2] rust: add maple tree abstractions

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <mjn2lz35u6joosddwrbgshgqitwx66fvpie5y4tledbcb2i5p2@gbp2sjva6iop>
Date: Mon, 7 Apr 2025 21:36:35 -0400
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
To: Andrew Ballance <andrewjballance@...il.com>
Cc: a.hindborg@...nel.org, akpm@...ux-foundation.org, alex.gaynor@...il.com,
        aliceryhl@...gle.com, benno.lossin@...ton.me, bjorn3_gh@...tonmail.com,
        boqun.feng@...il.com, brauner@...nel.org, dakr@...nel.org,
        dingxiangfei2009@...il.com, gary@...yguo.net,
        gregkh@...uxfoundation.org, linux-kernel@...r.kernel.org,
        linux-mm@...ck.org, maple-tree@...ts.infradead.org, ojeda@...nel.org,
        rust-for-linux@...r.kernel.org, tmgross@...ch.edu, wedsonaf@...il.com
Subject: Re: [RFC PATCH 2/2] rust: add maple tree abstractions

* Andrew Ballance <andrewjballance@...il.com> [250407 16:03]:
> On Mon, Apr 07, 2025 at 09:59:21AM -0400, Liam R. Howlett wrote:
> > * Andrew Ballance <andrewjballance@...il.com> [250405 02:03]:
> > > maple trees are sparse array like data structure that maps
> > > non-overlapping ranges to pointers.
> > 
> > Why do you think the maple tree is a spare array like data structure?
> > 
> 
> I called the maple tree "sparse array like" because indexes that have
> no entry map to null and there can be gaps between ranges. I did not
> mean to imply that a maple tree was literally a sparse array. 

Yes, I understood what you said to mean it was "like a sparse array", I
just don't see how it is like a sparse array.

My understanding is that a sparse array is sparse because not every
value is represented in the underlying storage, where as the maple tree
defines every range to an entry (including single entries, and NULL
entries).  It does combine multiple NULL entries into a single range.

There is a non-node store of a single entry of range [0,0] when [1,
ULONG_MAX] is NULL, or the entire empty set - but that's an
optimisation.

I haven't implemented a sparse array, so perhaps I'm missing how they
are alike.

> 
> Would you like me to reword this?
> 

No, I don't think it is worth having a rust implementation right now as
there are no users and I could cause issues on the rust side without
knowing.

I was wondering if you read that it was like a sparse array somewhere
and the reason behind it.  There is a plan for a sparse node type, but
there are a number of things that need to happen before I get there.

I've always said it was a b-tree variant (probably b+) for storing
ranges with a branching factor of 10 or 16 (for now, anyways).

Thanks,
Liam