* xas_prev() on an idr tree? idr_get_prev()?
@ 2019-03-18 17:36 Manfred Spraul
2019-03-18 18:18 ` Matthew Wilcox
0 siblings, 1 reply; 3+ messages in thread
From: Manfred Spraul @ 2019-03-18 17:36 UTC (permalink / raw)
To: Matthew Wilcox, Davidlohr Bueso, Waiman Long, linux-fsdevel; +Cc: 1vier1
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: xas_prev() on an idr tree? idr_get_prev()?
2019-03-18 17:36 xas_prev() on an idr tree? idr_get_prev()? Manfred Spraul
@ 2019-03-18 18:18 ` Matthew Wilcox
2020-03-26 9:20 ` Manfred Spraul
0 siblings, 1 reply; 3+ messages in thread
From: Matthew Wilcox @ 2019-03-18 18:18 UTC (permalink / raw)
To: Manfred Spraul; +Cc: Davidlohr Bueso, Waiman Long, linux-fsdevel, 1vier1
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.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: xas_prev() on an idr tree? idr_get_prev()?
2019-03-18 18:18 ` Matthew Wilcox
@ 2020-03-26 9:20 ` Manfred Spraul
0 siblings, 0 replies; 3+ messages in thread
From: Manfred Spraul @ 2020-03-26 9:20 UTC (permalink / raw)
To: Matthew Wilcox; +Cc: Davidlohr Bueso, Waiman Long, linux-fsdevel, 1vier1
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.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-03-26 9:20 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-03-18 17:36 xas_prev() on an idr tree? idr_get_prev()? Manfred Spraul
2019-03-18 18:18 ` Matthew Wilcox
2020-03-26 9:20 ` Manfred Spraul
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).