xarray reserve/release?

xarray reserve/release?

[Jason Gunthorpe]

Hey Matt,

Did you intend that xa_release doesn't work on allocating arrays:

	xa_init_flags(&xa, XA_FLAGS_ALLOC);
	xa_reserve(&xa, 0, GFP_KERNEL);
	WARN_ON(xa_empty(&xa));
	xa_release(&xa, 0);
	WARN_ON(!xa_empty(&xa));

Triggers the second WARN_ON. 

If FLAGS_ALLOC is removed this passes

This creates kind of a confusing / super unexpected situation where 

   xa_for_each (xa, id)
       xa_erase(xa, id);
   WARN_ON(!xa_empty(&xa))

Is not safe with XA_FLAGS_ALLOC??

Seems like at least deserves a documentation note.. Or maybe ALLOC
xa_empty should do something different?

Thanks,
Jason

Re: xarray reserve/release?

[Matthew Wilcox]

On Tue, Feb 19, 2019 at 04:53:49PM -0700, Jason Gunthorpe wrote:
> Hey Matt,
> 
> Did you intend that xa_release doesn't work on allocating arrays:

That surprises me.  I'll take a look in the morning.

(giving me the test case is perfect, btw)

Re: xarray reserve/release?

[Jason Gunthorpe]

On Tue, Feb 19, 2019 at 05:26:09PM -0800, Matthew Wilcox wrote:
> On Tue, Feb 19, 2019 at 04:53:49PM -0700, Jason Gunthorpe wrote:
> > Hey Matt,
> > 
> > Did you intend that xa_release doesn't work on allocating arrays:
> 
> That surprises me.  I'll take a look in the morning.

I think the issue is that this:

static inline void xa_release(struct xarray *xa, unsigned long index)
{
	xa_cmpxchg(xa, index, NULL, NULL, 0);

relies on the NULL actually being xas_store(NULL), but cmpxchg
transforms it into xas_store(XA_ZERO_ENTRY) when allocating..

So xa_reserve(), xa_release() and xa_cmpxchg() all do the same thing
for allocating arrays.

Perhaps this:

void __xa_release(struct xarray *xa, unsigned long index)
{
	XA_STATE(xas, xa, index);
	void *curr;

	curr = xas_load(&xas);
	if (curr == XA_ZERO_ENTRY)
		xas_store(&xas, NULL);
}

?

Also, I wonder if xa_reserve() is better written as as

       xa_cmpxchg(xa, index, NULL, XA_ZERO_ENTRY)

Bit clearer what is going on..

Jason

Re: xarray reserve/release?

[Matthew Wilcox]

On Tue, Feb 19, 2019 at 08:46:27PM -0700, Jason Gunthorpe wrote:
> On Tue, Feb 19, 2019 at 05:26:09PM -0800, Matthew Wilcox wrote:
> > On Tue, Feb 19, 2019 at 04:53:49PM -0700, Jason Gunthorpe wrote:
> > > Hey Matt,
> > > 
> > > Did you intend that xa_release doesn't work on allocating arrays:
> > 
> > That surprises me.  I'll take a look in the morning.
> 
> I think the issue is that this:
> 
> static inline void xa_release(struct xarray *xa, unsigned long index)
> {
> 	xa_cmpxchg(xa, index, NULL, NULL, 0);
> 
> relies on the NULL actually being xas_store(NULL), but cmpxchg
> transforms it into xas_store(XA_ZERO_ENTRY) when allocating..

Yes, you're right.

> So xa_reserve(), xa_release() and xa_cmpxchg() all do the same thing
> for allocating arrays.
> 
> Perhaps this:
> 
> void __xa_release(struct xarray *xa, unsigned long index)
> {
> 	XA_STATE(xas, xa, index);
> 	void *curr;
> 
> 	curr = xas_load(&xas);
> 	if (curr == XA_ZERO_ENTRY)
> 		xas_store(&xas, NULL);
> }
> 
> ?

I decided to instead remove the magic from xa_cmpxchg().  I used
to prohibit any internal entry being passed to the regular API, but
I recently changed that with 76b4e5299565 ("XArray: Permit storing
2-byte-aligned pointers").  Now that we can pass XA_ZERO_ENTRY, I
think this all makes much more sense.

> Also, I wonder if xa_reserve() is better written as as
> 
>        xa_cmpxchg(xa, index, NULL, XA_ZERO_ENTRY)
> 
> Bit clearer what is going on..

Yes, I agree.  I've pushed a couple of new commits to
http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray

which should fix your problem, and implement this optimisation.
Thanks for the report!

Re: xarray reserve/release?

[Jason Gunthorpe]

On Wed, Feb 20, 2019 at 09:14:14AM -0800, Matthew Wilcox wrote:

> > void __xa_release(struct xarray *xa, unsigned long index)
> > {
> > 	XA_STATE(xas, xa, index);
> > 	void *curr;
> > 
> > 	curr = xas_load(&xas);
> > 	if (curr == XA_ZERO_ENTRY)
> > 		xas_store(&xas, NULL);
> > }
> > 
> > ?
> 
> I decided to instead remove the magic from xa_cmpxchg().  I used
> to prohibit any internal entry being passed to the regular API, but
> I recently changed that with 76b4e5299565 ("XArray: Permit storing
> 2-byte-aligned pointers").  Now that we can pass XA_ZERO_ENTRY, I
> think this all makes much more sense.

Except that for allocating arrays xa_cmpxchg and xa_store now do
different things with NULL. Not necessarily bad, but if you have this
ABI variation it should be mentioned in the kdoc comment.

This is a bit worrysome though:

                curr = xas_load(&xas);
-               if (curr == XA_ZERO_ENTRY)
-                       curr = NULL;
                if (curr == old) {

It means any cmpxchg user has to care explicitly about the possibility
for true-NULL vs reserved. Seems like a difficult API.

What about writing it like this:

   if ((curr == XA_ZERO_ENTRY && old == NULL) || curr == old)

? I can't think of a use case to cmpxchg against real-null only.

And here:
                        xas_store(&xas, entry);
-                       if (xa_track_free(xa))
+                       if (xa_track_free(xa) && !old)
                                xas_clear_mark(&xas, XA_FREE_MARK);

Should this be

    if (xa_track_free(xa) && entry && !old)

? Ie we don't want to clear the XA_FREE_MARK if we just wrote NULL

Also I would think !curr is clearer? I assume the point is to not pay
the price of xas_clear_mark if we already know the index stored is
marked?

> > Also, I wonder if xa_reserve() is better written as as
> > 
> >        xa_cmpxchg(xa, index, NULL, XA_ZERO_ENTRY)
> > 
> > Bit clearer what is going on..
> 
> Yes, I agree.  I've pushed a couple of new commits to
> http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray

That looks really readable now that reserve and release are tidy
paired operations.

Thanks,
Jason

Re: xarray reserve/release?

[Matthew Wilcox]

On Wed, Feb 20, 2019 at 10:43:33AM -0700, Jason Gunthorpe wrote:
> On Wed, Feb 20, 2019 at 09:14:14AM -0800, Matthew Wilcox wrote:
> > > void __xa_release(struct xarray *xa, unsigned long index)
> > > {
> > > 	XA_STATE(xas, xa, index);
> > > 	void *curr;
> > > 
> > > 	curr = xas_load(&xas);
> > > 	if (curr == XA_ZERO_ENTRY)
> > > 		xas_store(&xas, NULL);
> > > }
> > > 
> > > ?
> > 
> > I decided to instead remove the magic from xa_cmpxchg().  I used
> > to prohibit any internal entry being passed to the regular API, but
> > I recently changed that with 76b4e5299565 ("XArray: Permit storing
> > 2-byte-aligned pointers").  Now that we can pass XA_ZERO_ENTRY, I
> > think this all makes much more sense.
> 
> Except that for allocating arrays xa_cmpxchg and xa_store now do
> different things with NULL. Not necessarily bad, but if you have this
> ABI variation it should be mentioned in the kdoc comment.

I'm worrying about the whole xa_store(... NULL, gfp) situation.  Before
I realised I needed to unify the XArray and the IDR (I'd originally
intended to have the IDR be a client of the XArray the same way that
it was a client of the radix tree), everything was nice and simple.
xa_erase() was a synonym for xa_store(... NULL, gfp).  Then the IDR
users showed up with their understanding of what storing NULL meant,
and now xa_store(NULL) means something different depending what kind of
array you have.  This sucks.  I'm tempted to have xa_store(NULL) always
transform the NULL into XA_ZERO_ENTRY, but I worry I might break some
users without noticing.

> This is a bit worrysome though:
> 
>                 curr = xas_load(&xas);
> -               if (curr == XA_ZERO_ENTRY)
> -                       curr = NULL;
>                 if (curr == old) {
> 
> It means any cmpxchg user has to care explicitly about the possibility
> for true-NULL vs reserved. Seems like a difficult API.

I think the users know, though.  I went through the current users of
xa_cmpxchg() and they're not the same users which are using xa_reserve()
or xa_alloc().

> What about writing it like this:
> 
>    if ((curr == XA_ZERO_ENTRY && old == NULL) || curr == old)
> 
> ? I can't think of a use case to cmpxchg against real-null only.
> 
> And here:
>                         xas_store(&xas, entry);
> -                       if (xa_track_free(xa))
> +                       if (xa_track_free(xa) && !old)
>                                 xas_clear_mark(&xas, XA_FREE_MARK);
> 
> Should this be
> 
>     if (xa_track_free(xa) && entry && !old)
> 
> ? Ie we don't want to clear the XA_FREE_MARK if we just wrote NULL

There are four cases to consider: old is NULL/present, entry is NULL/present.
xas_store() will set XA_FREE_MARK (by calling xas_init_marks()) if entry
is NULL.  Otherwise it leaves the marks alone.

old	entry	FREE before	FREE after xas_store	should be FREE
NULL	NULL	true		true			true
NULL	present	true		true			false
present	NULL	false		true			true
present	present	false		false			false

So the only case we need to clear the bit is if old is NULL and entry is
present.  I didn't consider the NULL->NULL transition, so you're right.

> Also I would think !curr is clearer? I assume the point is to not pay
> the price of xas_clear_mark if we already know the index stored is
> marked?

If you find it clearer, I'll use 'curr'.  They're equal at this point anyway.

> That looks really readable now that reserve and release are tidy
> paired operations.

Great!

Re: xarray reserve/release?

[Jason Gunthorpe]

On Wed, Feb 20, 2019 at 12:47:26PM -0800, Matthew Wilcox wrote:
> On Wed, Feb 20, 2019 at 10:43:33AM -0700, Jason Gunthorpe wrote:
> > On Wed, Feb 20, 2019 at 09:14:14AM -0800, Matthew Wilcox wrote:
> > > > void __xa_release(struct xarray *xa, unsigned long index)
> > > > {
> > > > 	XA_STATE(xas, xa, index);
> > > > 	void *curr;
> > > > 
> > > > 	curr = xas_load(&xas);
> > > > 	if (curr == XA_ZERO_ENTRY)
> > > > 		xas_store(&xas, NULL);
> > > > }
> > > > 
> > > > ?
> > > 
> > > I decided to instead remove the magic from xa_cmpxchg().  I used
> > > to prohibit any internal entry being passed to the regular API, but
> > > I recently changed that with 76b4e5299565 ("XArray: Permit storing
> > > 2-byte-aligned pointers").  Now that we can pass XA_ZERO_ENTRY, I
> > > think this all makes much more sense.
> > 
> > Except that for allocating arrays xa_cmpxchg and xa_store now do
> > different things with NULL. Not necessarily bad, but if you have this
> > ABI variation it should be mentioned in the kdoc comment.
> 
> I'm worrying about the whole xa_store(... NULL, gfp) situation.  Before
> I realised I needed to unify the XArray and the IDR (I'd originally
> intended to have the IDR be a client of the XArray the same way that
> it was a client of the radix tree), everything was nice and simple.
> xa_erase() was a synonym for xa_store(... NULL, gfp).  Then the IDR
> users showed up with their understanding of what storing NULL meant,
> and now xa_store(NULL) means something different depending what kind of
> array you have.  This sucks.  I'm tempted to have xa_store(NULL) always
> transform the NULL into XA_ZERO_ENTRY, but I worry I might break some
> users without noticing.

So you will end up with xa_store, xa_insert, xa_alloc doing the
conversion on store, and xa_cmpxchg not doing it.

I'd excuse xa_alloc/xa_insert, as anyone calling them surely means to
reserve the entry. The comment for xa_insert even says it does
this. Great.

xa_store(NULL) == xa_erase(), sometimes, is weird, IMHO. Two APIs
would be clearer: xa_store() which always does the XA_ZERO_ENTRY and
xa_store_erase() which always does xa_erase() if the argument is
NULL.

This makes the itent of the call site super clear without having to
find the xa_init and check the mode.

If this was done then xa_track_free() would only cause the mark to be
updated, or not, and has no other behavior change.

For completeness xa_cmpxchg() should probably get a similar comment as
xa_insert():

  If the predicate matches then a NULL entry will do xa_erase() on the
  index. Otherwise the value is stored.

  When matching the predicate the value NULL only matches unreserved
  entries. [this more or less matches xa_insert anyhow]

> > This is a bit worrysome though:
> > 
> >                 curr = xas_load(&xas);
> > -               if (curr == XA_ZERO_ENTRY)
> > -                       curr = NULL;
> >                 if (curr == old) {
> > 
> > It means any cmpxchg user has to care explicitly about the possibility
> > for true-NULL vs reserved. Seems like a difficult API.
> 
> I think the users know, though.  I went through the current users of
> xa_cmpxchg() and they're not the same users which are using xa_reserve()
> or xa_alloc().

Reflecting on this more, the use case I was looking at was basically

   // First thread here wins ownership of 'id' and does reserve
   ret = xa_cmpxchg(xa, id NULL, XA_ZERO_ENTRY)
   if (ret != NULL)
       return;

   ...

   // Can't fail
   xa_store(xa, id, something);

So that actually works better the way you have it.

Can always have another cmpxchg varient if a use comes up.

> > Also I would think !curr is clearer? I assume the point is to not pay
> > the price of xas_clear_mark if we already know the index stored is
> > marked?
> 
> If you find it clearer, I'll use 'curr'.  They're equal at this point anyway.

Yeah, it brings to mind your table more directly then having to also
work out that old == curr == xa_load ==> optimizing away unneeded clear

BTW, will you send conversion patches for drivers/infiniband sometime
soonish? Feel like I know enough about xarray to review them these
days

Thanks,
Jason