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.
