[RFC] Rebasing the IDR

[Daniel Vetter]

On Thu, Nov 30, 2017 at 10:09 PM, Matthew Wilcox <willy at infradead.org> wrote:
> 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.

We're storing NULL in a few interim cases already, to solve issues
around init/teardown of objects (where we need to keep the index
reserved, but not pointing to anything). So if I could pick, I'd
prefer to distinguish that from the always-NULL case for 0. Since
doing that would mean in our driver unload code we'd then have to
check for that NULL pointer in the usual cleanup loops (where we know
all the interim NULL values are definitely gone).

>> 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).

+1 on idr_get. A bit confusing since get/put is usually used for
refcounting in the kernel (we're switching the drm subsystem from
ref/unref to get/put for more consistency), but oh well, flag days are
not pretty either.
-Daniel
-- 
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch