linux-kernel - Re: [PATCH v5 07/70] Maple Tree: Add new data structure

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: <1181363.1643973863@warthog.procyon.org.uk>
Date:   Fri, 04 Feb 2022 11:24:23 +0000
From:   David Howells <dhowells@...hat.com>
To:     Mike Rapoport <rppt@...nel.org>,
        Liam Howlett <liam.howlett@...cle.com>
Cc:     dhowells@...hat.com,
        "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [PATCH v5 07/70] Maple Tree: Add new data structure

Mike Rapoport <rppt@...nel.org> wrote:

> > +The Maple Tree maintains a small memory footprint and was designed to use
> > +modern processor cache efficiently.  The most important user of the Maple Tree
> > +is the virtual memory area.
> 
> For me it sounds like VMA *is* the maple tree user. Maybe

I'm having a go at using it for the netfs lib support library to store a list
of dirty regions.  So far it looks like it should work for me.  It might be
more useful if it had a loff_t index, but I can manage with pgoff_t.

Also isn't the intention to move xarray to use this inside eventually?

I would just drop the last sentence from the docs entirely.  If someone wants
to know who is using it, they can probably work it out with grep;-).  And,
anyway, once there's more than one user, which is the most important will be
subjective - and if you do put a list of users here, it's likely to get out of
date.

> > +
> > +The Maple Tree can store between 0 and ``ULONG_MAX``.  The Maple Tree reserves
> 
>                           ^ values

Indices or keys?  Isn't the "value" the thing that is being storing at an
index or index range?

> > +Pre-allocating of nodes is also supported using the advanced API.  This is
> > +useful for users who must guarantee a successful store operation within a given
> > +code segment when allocating cannot be done.  Allocations of nodes are
> > +relatively small at 256 bytes.
> 
> I doubt the size here will get timely updates when the node size will
> change in the code, maybe use "around" or "roughly" to be future proof? :)

I would suggest dropping the number and saying "Nodes are relatively small
allocations".  If there's a symbol that specifies this, you could plonk that
in.

> There are a lots of comments describing the maple tree internals here and
> below. Did yaou consider adding a section "Implementation details" or
> something like that to the maple_tree.rst and linking these comments there
> with DOC: and some glue text?

Could even add a maple_tree_gory_details.rst.  It doesn't necessarily have to
go in the same document as the API description.

David