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

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

[Manfred Spraul]

Hi,

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?

--

     Manfred

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

[Matthew Wilcox]

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.

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

[Manfred Spraul]

Hello Matthew,

On 3/18/19 7:18 PM, Matthew Wilcox wrote:
> 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).

Any update?

I would have some time, and the (idx--) loop is on my list. With 
IPCMNI_EXTEND_SHIFT, we can loop over 2^24 entries...

- Should I review ipc xarray code and send it to Andrew for merging?

- Should I try to create a "xa_find_last(xa, &index, XA_PRESENT)" function?

The alternative would be a binary search with find next.
> 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.