[RFC] Rebasing the IDR

[Matthew Wilcox]

On Thu, Nov 30, 2017 at 08:56:43PM +0100, Daniel Vetter wrote:
> Adding dri-devel, I think a pile of those are in drm.

Yeah, quite a lot!  This is a good thing; means you didn't invent your
own custom ID allocator.

> On Thu, Nov 30, 2017 at 6:36 PM, Matthew Wilcox <willy at infradead.org> wrote:
> > About 40 of the approximately 180 users of the IDR in the kernel are
> > "1-based" instead of "0-based".  That is, they never want to have ID 0
> > allocated; they want to see IDs allocated between 1 and N.  Usually, that's
> > expressed like this:
> >
> >         /* Get the user-visible handle using idr. */
> >         ret = idr_alloc(&file_priv->object_idr, obj, 1, 0, GFP_KERNEL);
> >

> Just quick context on why we do this: We need to marshal/demarshal
> NULL in a ton of our ioctls, mapping that to 0 is natural.

Yep.  You could actually store NULL at IDR index 0; the IDR distinguishes
between an allocated NULL and an unallocated entry.

> And yes I very much like this, and totally fine with trading an
> idr_init_base when we can nuke the explicit index ranges at every
> alloc side instead. So if you give me an idr_alloc function that
> doesn't take a range as icing, that would be great.

I think the API is definitely bad at making the easy things easy ... I'd
call the current idr_alloc() idr_alloc_range().  But I don't want to change
200+ call sites, so I'll settle for a new name.

	ret = idr_get(&file_priv->object_idr, obj, GFP_KERNEL);

I have another new API in the works for after the xarray lands and we can
simplify the locking --

int __must_check idr_alloc_u32(struct idr *idr, void *ptr,
			unsigned int *nextid, unsigned int max, gfp_t gfp)

The trick is that we store to nextid before inserting the ptr into the
xarray, so this will enable more users to dispense with their own locking
(or avoid awful i-looked-up-this-object-but-it's-not-initialised-so-
pretend-i-didn't-see-it dances).

(There's also an idr_alloc_ul for completeness, but I think this is
actually a bad idea; the radix tree gets pretty unwieldy at large sparse
indices and I don't want to encourage people to go outside unsigned int).