Re: xas_prev() on an idr tree? idr_get_prev()?

[Matthew Wilcox <willy@infradead.org>]

On Mon, Mar 18, 2019 at 06:36:25PM +0100, Manfred Spraul wrote:
> the ipc code needs to find the highest index allocated in an idr tree.
> It is part of the user space API: The return value of semctl(), msgctl() for
> ..._INFO contains that number.
> 
> Right now, the number is updated by calling idr_find(--idx), until this
> succeeds.
> (ipc_rmid() in ipc/util.c).
> 
> Is there a a standard function already?
> 
> Should I create a patch that adds idr_get_prev() to the idr API?

Oof, please don't add to the IDR API.  I've actually got a tree with all
existing users of the IDR and radix tree APIs converted to the XArray.
http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv
(currently rebasing it on -rc1, checking over each patch for bugs before
sending them off to the maintainers).

Unfortunately, I didn't try to make ipc_rmid any smarter than it already is.
That is, it currently looks like:

@@ -433,7 +425,7 @@ void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
 {
        int idx = ipcid_to_idx(ipcp->id);
 
-       idr_remove(&ids->ipcs_idr, idx);
+       xa_erase(&ids->ipcs, idx);
        ipc_kht_remove(ids, ipcp);
        ids->in_use--;
        ipcp->deleted = true;
@@ -443,7 +435,7 @@ void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp)
                        idx--;
                        if (idx == -1)
                                break;
-               } while (!idr_find(&ids->ipcs_idr, idx));
+               } while (!xa_load(&ids->ipcs, idx));
                ids->max_idx = idx;
        }
 }

One of the things we need is an xa_for_each_rev() macro.  I think it
should look like this:

#define xa_for_each_rev(xa, index, entry)				\
	for (entry = xa_find_last(xa, &index, XA_PRESENT);		\
	     entry;							\
	     entry = xa_find_before(xa, &index, XA_PRESENT))

I was going to work on that at some point in the next month or so,
but if you want to take it on, I'd be awfully grateful!

I don't know if we need an xas_find_last() / xas_find_prev() function.
Without any user that I think would benefit from it, I'd be tempted to
just do the xa_ versions.