Skip to contentSkip to conversation

Rebasing the IDR

RFC In review Matthew Wilcox 3 participants 6 messages Nov 30, 2017 – Feb 9, 2018

Subsystems (4)
lore
Share & tools
lore

Matthew Wilcox

author maintainer
#0 lore raw

RFC 1/1 Rebasing the IDR

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

The current implementation of this grieves me. You see, we mark each node of the radix tree according to whether it has any free entries or not, and entry 0 is always free! If we've already allocated 10,000 entries from this IDR, and see this call, we'll walk all the way down the left side of the tree looking for entry 1, get to the bottom, see that entries 1-63 are allocated, then walk up to the next level, see that 64-4095 are allocated, walk up to the next level, see that 8192-12287 has a free entry, and then start walking down again.

It'd be somewhere around two to three times quicker to know not to look down the left hand side of the tree, see that 1-8191 are used and start looking in the range 8192-12287. I considered a function like idr_reserve(idr, N) to reserve the first N entries (we have at least one consumer in the tree that is 2-based, not 1-based), but that struck me as inelegant. We also have the cool optimisation that if there's only one element in the radix tree at offset 0, then we don't even need to allocate a node to store it, we just store it right in the head. And that optimisation was never available to the 1-based users.

I've come up with this solution instead, idr_base. It's free in terms of memory consumption on 64-bit as it fits in the gap at the end of the struct idr. Essentially, we just subtract off idr_base when looking up the ID, and add it back on when reporting the ID. We need to do some saturating arithmetic in idr_get_next(), because starting a walk at 4 billion or negative 8 quintillion doesn't work out terribly well.

It does require the user to call idr_init_base() instead of idr_init(). That should be a relatively small conversion effort. Opinions? Feedback? Better test cases for the test-suite (ahem)?

include/linux/idr.h +15 -5
index 91d27a9bcdf4..a657b1f925f8 100644
@@ -18,6 +18,7 @@
 
 struct idr {
 	struct radix_tree_root	idr_rt;
+	unsigned int		idr_base;
 	unsigned int		idr_next;
 };
 
@@ -30,9 +31,10 @@ struct idr {
 /* Set the IDR flag and the IDR_FREE tag */
 #define IDR_RT_MARKER		((__force gfp_t)(3 << __GFP_BITS_SHIFT))
 
-#define IDR_INIT							\
-{									\
-	.idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER)			\
+#define IDR_INIT {							\
+	.idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER),			\
+	.idr_base = 0,							\
+	.idr_next = 0,							\
 }
 #define DEFINE_IDR(name)	struct idr name = IDR_INIT
 
@@ -123,12 +125,20 @@ static inline int __must_check idr_alloc_u32(struct idr *idr, void *ptr,
 
 static inline void *idr_remove(struct idr *idr, unsigned long id)
 {
-	return radix_tree_delete_item(&idr->idr_rt, id, NULL);
+	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
 }
 
 static inline void idr_init(struct idr *idr)
 {
 	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
+	idr->idr_base = 0;
+	idr->idr_next = 0;
+}
+
+static inline void idr_init_base(struct idr *idr, int base)
+{
+	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
+	idr->idr_base = base;
 	idr->idr_next = 0;
 }
 
@@ -163,7 +173,7 @@ static inline void idr_preload_end(void)
  */
 static inline void *idr_find(const struct idr *idr, unsigned long id)
 {
-	return radix_tree_lookup(&idr->idr_rt, id);
+	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
 }
 
 /**
lib/idr.c +19 -9
index 1aaeb5a8c426..a1d3531bd62f 100644
@@ -33,21 +33,22 @@ int idr_alloc_ul(struct idr *idr, void *ptr, unsigned long *nextid,
 {
 	struct radix_tree_iter iter;
 	void __rcu **slot;
+	int base = idr->idr_base;
 
 	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
 		return -EINVAL;
 	if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
 		idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
 
-	radix_tree_iter_init(&iter, *nextid);
-	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max);
+	radix_tree_iter_init(&iter, *nextid - base);
+	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
 	if (IS_ERR(slot))
 		return PTR_ERR(slot);
 
 	radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
 	radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
 
-	*nextid = iter.index;
+	*nextid = iter.index + base;
 	return 0;
 }
 EXPORT_SYMBOL_GPL(idr_alloc_ul);
@@ -143,13 +144,14 @@ int idr_for_each(const struct idr *idr,
 {
 	struct radix_tree_iter iter;
 	void __rcu **slot;
+	int base = idr->idr_base;
 
 	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
 		int ret;
 
 		if (WARN_ON_ONCE(iter.index > INT_MAX))
 			break;
-		ret = fn(iter.index, rcu_dereference_raw(*slot), data);
+		ret = fn(iter.index + base, rcu_dereference_raw(*slot), data);
 		if (ret)
 			return ret;
 	}
@@ -172,15 +174,19 @@ void *idr_get_next(struct idr *idr, int *nextid)
 {
 	struct radix_tree_iter iter;
 	void __rcu **slot;
+	int base = idr->idr_base;
+	int id = *nextid;
 
-	slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
+	id = (id < base) ? 0 : id - base;
+	slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
 	if (!slot)
 		return NULL;
+	id = iter.index + base;
 
-	if (WARN_ON_ONCE(iter.index > INT_MAX))
+	if (WARN_ON_ONCE(id > INT_MAX))
 		return NULL;
 
-	*nextid = iter.index;
+	*nextid = id;
 	return rcu_dereference_raw(*slot);
 }
 EXPORT_SYMBOL(idr_get_next);
@@ -199,12 +205,15 @@ void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
 {
 	struct radix_tree_iter iter;
 	void __rcu **slot;
+	unsigned long base = idr->idr_base;
+	unsigned long id = *nextid;
 
-	slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
+	id = (id < base) ? 0 : id - base;
+	slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
 	if (!slot)
 		return NULL;
 
-	*nextid = iter.index;
+	*nextid = iter.index + base;
 	return rcu_dereference_raw(*slot);
 }
 EXPORT_SYMBOL(idr_get_next_ul);
@@ -231,6 +240,7 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 
 	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
 		return ERR_PTR(-EINVAL);
+	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
 	if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
tools/testing/radix-tree/idr-test.c +5 -2
index 36437ade429c..44ef9eba5a7a 100644
@@ -153,11 +153,12 @@ void idr_nowait_test(void)
 	idr_destroy(&idr);
 }
 
-void idr_get_next_test(void)
+void idr_get_next_test(int base)
 {
 	unsigned long i;
 	int nextid;
 	DEFINE_IDR(idr);
+	idr_init_base(&idr, base);
 
 	int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
 
@@ -244,7 +245,9 @@ void idr_checks(void)
 	idr_alloc_test();
 	idr_null_test();
 	idr_nowait_test();
-	idr_get_next_test();
+	idr_get_next_test(0);
+	idr_get_next_test(1);
+	idr_get_next_test(4);
 }
 
 /*
#1 lore raw

Adding dri-devel, I think a pile of those are in drm.

Quoted 34 lines · Matthew Wilcox

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

The current implementation of this grieves me. You see, we mark each node of the radix tree according to whether it has any free entries or not, and entry 0 is always free! If we've already allocated 10,000 entries from this IDR, and see this call, we'll walk all the way down the left side of the tree looking for entry 1, get to the bottom, see that entries 1-63 are allocated, then walk up to the next level, see that 64-4095 are allocated, walk up to the next level, see that 8192-12287 has a free entry, and then start walking down again.

It'd be somewhere around two to three times quicker to know not to look down the left hand side of the tree, see that 1-8191 are used and start looking in the range 8192-12287. I considered a function like idr_reserve(idr, N) to reserve the first N entries (we have at least one consumer in the tree that is 2-based, not 1-based), but that struck me as inelegant. We also have the cool optimisation that if there's only one element in the radix tree at offset 0, then we don't even need to allocate a node to store it, we just store it right in the head. And that optimisation was never available to the 1-based users.

I've come up with this solution instead, idr_base. It's free in terms of memory consumption on 64-bit as it fits in the gap at the end of the struct idr. Essentially, we just subtract off idr_base when looking up the ID, and add it back on when reporting the ID. We need to do some saturating arithmetic in idr_get_next(), because starting a walk at 4 billion or negative 8 quintillion doesn't work out terribly well.

Quoted 3 lines

It does require the user to call idr_init_base() instead of idr_init(). That should be a relatively small conversion effort. Opinions? Feedback? Better test cases for the test-suite (ahem)?

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.

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.

Cheers, Daniel

Quoted 182 lines
include/linux/idr.h +15 -5
index 91d27a9bcdf4..a657b1f925f8 100644
@@ -18,6 +18,7 @@
 
 struct idr {
        struct radix_tree_root  idr_rt;
+       unsigned int            idr_base;
        unsigned int            idr_next;
 };
 
@@ -30,9 +31,10 @@ struct idr {
 /* Set the IDR flag and the IDR_FREE tag */
 #define IDR_RT_MARKER          ((__force gfp_t)(3 << __GFP_BITS_SHIFT))
 
-#define IDR_INIT                                                       \
-{                                                                      \
-       .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER)                        \
+#define IDR_INIT {                                                     \
+       .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER),                       \
+       .idr_base = 0,                                                  \
+       .idr_next = 0,                                                  \
 }
 #define DEFINE_IDR(name)       struct idr name = IDR_INIT
 
@@ -123,12 +125,20 @@ static inline int __must_check idr_alloc_u32(struct idr *idr, void *ptr,
 
 static inline void *idr_remove(struct idr *idr, unsigned long id)
 {
-       return radix_tree_delete_item(&idr->idr_rt, id, NULL);
+       return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
 }
 
 static inline void idr_init(struct idr *idr)
 {
        INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
+       idr->idr_base = 0;
+       idr->idr_next = 0;
+}
+
+static inline void idr_init_base(struct idr *idr, int base)
+{
+       INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
+       idr->idr_base = base;
        idr->idr_next = 0;
 }
 
@@ -163,7 +173,7 @@ static inline void idr_preload_end(void)
  */
 static inline void *idr_find(const struct idr *idr, unsigned long id)
 {
-       return radix_tree_lookup(&idr->idr_rt, id);
+       return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
 }
 
 /**
lib/idr.c +19 -9
index 1aaeb5a8c426..a1d3531bd62f 100644
@@ -33,21 +33,22 @@ int idr_alloc_ul(struct idr *idr, void *ptr, unsigned long *nextid,
 {
        struct radix_tree_iter iter;
        void __rcu **slot;
+       int base = idr->idr_base;
 
        if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
                return -EINVAL;
        if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
                idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
 
-       radix_tree_iter_init(&iter, *nextid);
-       slot = idr_get_free(&idr->idr_rt, &iter, gfp, max);
+       radix_tree_iter_init(&iter, *nextid - base);
+       slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
        if (IS_ERR(slot))
                return PTR_ERR(slot);
 
        radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
        radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
 
-       *nextid = iter.index;
+       *nextid = iter.index + base;
        return 0;
 }
 EXPORT_SYMBOL_GPL(idr_alloc_ul);
@@ -143,13 +144,14 @@ int idr_for_each(const struct idr *idr,
 {
        struct radix_tree_iter iter;
        void __rcu **slot;
+       int base = idr->idr_base;
 
        radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
                int ret;
 
                if (WARN_ON_ONCE(iter.index > INT_MAX))
                        break;
-               ret = fn(iter.index, rcu_dereference_raw(*slot), data);
+               ret = fn(iter.index + base, rcu_dereference_raw(*slot), data);
                if (ret)
                        return ret;
        }
@@ -172,15 +174,19 @@ void *idr_get_next(struct idr *idr, int *nextid)
 {
        struct radix_tree_iter iter;
        void __rcu **slot;
+       int base = idr->idr_base;
+       int id = *nextid;
 
-       slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
+       id = (id < base) ? 0 : id - base;
+       slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
        if (!slot)
                return NULL;
+       id = iter.index + base;
 
-       if (WARN_ON_ONCE(iter.index > INT_MAX))
+       if (WARN_ON_ONCE(id > INT_MAX))
                return NULL;
 
-       *nextid = iter.index;
+       *nextid = id;
        return rcu_dereference_raw(*slot);
 }
 EXPORT_SYMBOL(idr_get_next);
@@ -199,12 +205,15 @@ void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
 {
        struct radix_tree_iter iter;
        void __rcu **slot;
+       unsigned long base = idr->idr_base;
+       unsigned long id = *nextid;
 
-       slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
+       id = (id < base) ? 0 : id - base;
+       slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
        if (!slot)
                return NULL;
 
-       *nextid = iter.index;
+       *nextid = iter.index + base;
        return rcu_dereference_raw(*slot);
 }
 EXPORT_SYMBOL(idr_get_next_ul);
@@ -231,6 +240,7 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 
        if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
                return ERR_PTR(-EINVAL);
+       id -= idr->idr_base;
 
        entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
        if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
tools/testing/radix-tree/idr-test.c +5 -2
index 36437ade429c..44ef9eba5a7a 100644
@@ -153,11 +153,12 @@ void idr_nowait_test(void)
        idr_destroy(&idr);
 }
 
-void idr_get_next_test(void)
+void idr_get_next_test(int base)
 {
        unsigned long i;
        int nextid;
        DEFINE_IDR(idr);
+       idr_init_base(&idr, base);
 
        int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
 
@@ -244,7 +245,9 @@ void idr_checks(void)
        idr_alloc_test();
        idr_null_test();
        idr_nowait_test();
-       idr_get_next_test();
+       idr_get_next_test(0);
+       idr_get_next_test(1);
+       idr_get_next_test(4);
 }
 
 /*
Signature · 7 lines
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
author maintainer
#2 lore raw
Quoted 1 line · Daniel Vetter

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.

Quoted 6 lines · Matthew Wilcox
Quoted 5 lines

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:

Quoted 6 lines
Quoted 3 lines
        /* 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.

Quoted 4 lines

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

#3 lore raw
Quoted 16 lines · Matthew Wilcox
Quoted 1 line · Daniel Vetter

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.

Quoted 9 lines · Matthew Wilcox
Quoted 8 lines

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);
Quoted 5 lines
Quoted 2 lines

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

Quoted 17 lines
Quoted 4 lines

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)

Quoted 8 lines

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

Signature · 7 lines
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch
_______________________________________________
dri-devel mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/dri-devel
#4 lore raw
In reply to Matthew Wilcox

Quoting Matthew Wilcox (2017-11-30 17:36:30)

Quoted 8 lines

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);
Quoted 8 lines

The current implementation of this grieves me. You see, we mark each node of the radix tree according to whether it has any free entries or not, and entry 0 is always free! If we've already allocated 10,000 entries from this IDR, and see this call, we'll walk all the way down the left side of the tree looking for entry 1, get to the bottom, see that entries 1-63 are allocated, then walk up to the next level, see that 64-4095 are allocated, walk up to the next level, see that 8192-12287 has a free entry, and then start walking down again.

Hmm, missing the baseline to apply this patch. But I did the quick hack of allocating index 0 of the idr and that did eradicate the idr_get_free_cmn() from being at the top of the profiles for the many-object stress tests. This improvement will be much appreciated. -Chris

author maintainer
#5 lore raw
Quoted 18 lines · Chris Wilson

Quoting Matthew Wilcox (2017-11-30 17:36:30)

Quoted 8 lines

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);
Quoted 8 lines

The current implementation of this grieves me. You see, we mark each node of the radix tree according to whether it has any free entries or not, and entry 0 is always free! If we've already allocated 10,000 entries from this IDR, and see this call, we'll walk all the way down the left side of the tree looking for entry 1, get to the bottom, see that entries 1-63 are allocated, then walk up to the next level, see that 64-4095 are allocated, walk up to the next level, see that 8192-12287 has a free entry, and then start walking down again.

Quoted 4 lines

Hmm, missing the baseline to apply this patch. But I did the quick hack of allocating index 0 of the idr and that did eradicate the idr_get_free_cmn() from being at the top of the profiles for the many-object stress tests. This improvement will be much appreciated.

Hi Chris,

The new IDR implementation is now in Linus' tree. For any IDR that you want to be 1s based, initialise it using idr_init_base() instead of idr_init() and it will magically be more efficient.

I did a quick example on the first IDR which matched

$ git grep 'idr_alloc.*, 1,' drivers/gpu
drivers/gpu/drm/amd/amdgpu/amdgpu_kms.c +1 -1
index bd6e9a40f421..c35ea6695fee 100644
@@ -844,7 +844,7 @@ int amdgpu_driver_open_kms(struct drm_device *dev, struct drm_file *file_priv)
 	}
 
 	mutex_init(&fpriv->bo_list_lock);
-	idr_init(&fpriv->bo_list_handles);
+	idr_init_base(&fpriv->bo_list_handles, 1);
 
 	amdgpu_ctx_mgr_init(&fpriv->ctx_mgr);
 

Let me know if you run into any problems using it; there are test-cases in the test-suite, but I may have missed something.