[PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/18 01:30PM, Rik van Riel wrote:
> On Thu, 2026-06-18 at 13:27 -0400, Liam R. Howlett wrote:
> > On 26/06/18 12:24PM, Jason Gunthorpe wrote:
> > > 
> > > 
> > > - I like your idea for Rik to try to store NULL to erase, on
> > > failure
> > >   store ZERO_ENTRY, and then set a note on the next alloc to clean
> > > the
> > >   ZERO_ENTRYs?
> > 
> > The ZERO_ENTRY can be found by mas_* functions and will cause issues
> > with the gap searching.  You also have to be careful to handle these
> > entries in mas_for_each() loops - you don't want to treat them as
> > valid
> > entries.
> > 
> Could it make sense for the maple tree to have
> something similar to ZERO_ENTRY that is treated
> like a gap, so the gap search can find it, and
> get rid of those entries when the gap gets re-used?

It might, but it's not as simple as adding a new special entry.  Gaps
are propagated up the tree so that we know which subtree has what size
gap.  If we have a special entry that isn't counted as an entry at all,
then we're in a position where the gap calculation code needs to change.

I'm also not sure how we handle this entry if it's at the edge of a
node.  How do you account for a gap in a subtree if it's not fully in
that subtree?  If one node has a gap of 5 and a value and then the next
node starts with a gap of 5, how do we represent that gap in the parent
node?  What if it's multiple levels up?  How do we find that gap and how
do we return something that makes sense to the caller?  What if the gap
spans an entire node or larger?

It also brings into question how much data is considered within a node -
is one of these entries kept if we rebalance?  Do we have to mark the
tree itself to state that it's in this odd state to avoid other stores
from actually happening before the tree is cleaned?  How do we state
that the tree is in this unusual state?

It might be worth doing, but it's not a simple change.

Thanks,
Liam