Re: [PATCH v2 14/16] maple_tree: Refine mas_preallocate() node calculations

[Matthew Wilcox <willy@infradead.org>]

On Mon, Jun 26, 2023 at 02:38:06AM +0200, Danilo Krummrich wrote:
> On the other hand, unless I miss something (and if so, please let me know),
> something is bogus with the API then.
> 
> While the documentation of the Advanced API of the maple tree explicitly
> claims that the user of the API is responsible for locking, this should be
> limited to the bounds set by the maple tree implementation. Which means, the
> user must decide for either the internal (spin-) lock or an external lock
> (which possibly goes away in the future) and acquire and release it
> according to the rules maple tree enforces through lockdep checks.
> 
> Let's say one picks the internal lock. How is one supposed to ensure the
> tree isn't modified using the internal lock with mas_preallocate()?
> 
> Besides that, I think the documentation should definitely mention this
> limitation and give some guidance for the locking.
> 
> Currently, from an API perspective, I can't see how anyone not familiar with
> the implementation details would be able to recognize this limitation.
> 
> In terms of the GPUVA manager, unfortunately, it seems like I need to drop
> the maple tree and go back to using a rb-tree, since it seems there is no
> sane way doing a worst-case pre-allocation that does not suffer from this
> limitation.

I haven't been paying much attention here (too many other things going
on), but something's wrong.

First, you shouldn't need to preallocate.  Preallocation is only there
for really gnarly cases.  The way this is *supposed* to work is that
the store walks down to the leaf, attempts to insert into that leaf
and tries to allocate new nodes with __GFP_NOWAIT.  If that fails,
it drops the spinlock, allocates with the gfp flags you've specified,
then rewalks the tree to retry the store, this time with allocated
nodes in its back pocket so that the store will succeed.