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.
