Skip to contentSkip to conversation

idr: Prevent unintended underflow for the idr index

PATCH In review Jordan Crouse 2 participants 3 messages Sep 17, 2019 – Sep 18, 2019

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 idr: Prevent unintended underflow for the idr index

It is possible for unaware callers of several idr functions to accidentally underflow the index by specifying a id that is less than the idr base.

---

 lib/idr.c | 9 +++++++++
 1 file changed, 9 insertions(+)
lib/idr.c +9 -0
index 66a3748..d9e180c 100644
@@ -151,6 +151,9 @@ EXPORT_SYMBOL(idr_alloc_cyclic);
  */
 void *idr_remove(struct idr *idr, unsigned long id)
 {
+	if (id < idr->idr_base)
+		return NULL;
+
 	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
 }
 EXPORT_SYMBOL_GPL(idr_remove);
@@ -171,6 +174,9 @@ EXPORT_SYMBOL_GPL(idr_remove);
  */
 void *idr_find(const struct idr *idr, unsigned long id)
 {
+	if (id < idr->idr_base)
+		return NULL;
+
 	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
 }
 EXPORT_SYMBOL_GPL(idr_find);
@@ -302,6 +308,9 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 	void __rcu **slot = NULL;
 	void *entry;
 
+	if (id < idr->idr_base)
+		return ERR_PTR(-ENOENT);
+
 	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
Signature · 1 line
2.7.4
maintainer
#1 lore raw
Quoted 2 lines · Jordan Crouse

It is possible for unaware callers of several idr functions to accidentally underflow the index by specifying a id that is less than the idr base.

Hi Jordan. Thanks for the patch, but this seems like a distinction without a difference.

lib/idr.c EXPORT_SYMBOL(idr_alloc_cyclic); · line 157

Quoted 6 lines

void *idr_remove(struct idr *idr, unsigned long id) {

lib/idr.c +3 -0
+	if (id < idr->idr_base)
+		return NULL;
+
 	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);

If this underflows, we'll try to delete an index which doesn't exist, which will return NULL.

lib/idr.c EXPORT_SYMBOL_GPL(idr_remove); · line 180

Quoted 6 lines

void *idr_find(const struct idr *idr, unsigned long id) {

lib/idr.c +3 -0
+	if (id < idr->idr_base)
+		return NULL;
+
 	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);

If this underflows, we'll look up an entry which doesn't exist, which will return NULL.

lib/idr.c void *idr_replace(struct idr *idr, void *ptr, unsigned long id) · line 316

Quoted 10 lines
lib/idr.c +3 -0
@@ -302,6 +308,9 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 	void __rcu **slot = NULL;
 	void *entry;
 
+	if (id < idr->idr_base)
+		return ERR_PTR(-ENOENT);
+
 	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);

... just outside the context is this line:

        if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
                return ERR_PTR(-ENOENT);

Looking up an index which doesn't exist gets you a NULL slot, so you get -ENOENT anyway.

I did think about these possibilities when I was writing the code and convinced myself I didn't need them. If you have an example of a case where I got thast wrong, I'd love to see it.

More generally, the IDR is deprecated; I'm trying to convert users to the XArray. If you're adding a new user, can you use the XArray API instead?

#2 lore raw
Quoted 45 lines · Matthew Wilcox
Quoted 2 lines · Jordan Crouse

It is possible for unaware callers of several idr functions to accidentally underflow the index by specifying a id that is less than the idr base.

Hi Jordan. Thanks for the patch, but this seems like a distinction without a difference.

lib/idr.c EXPORT_SYMBOL(idr_alloc_cyclic); · line 157

Quoted 6 lines

void *idr_remove(struct idr *idr, unsigned long id) {

lib/idr.c +3 -0
+	if (id < idr->idr_base)
+		return NULL;
+
 	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);

If this underflows, we'll try to delete an index which doesn't exist, which will return NULL.

lib/idr.c EXPORT_SYMBOL_GPL(idr_remove); · line 180

Quoted 6 lines

void *idr_find(const struct idr *idr, unsigned long id) {

lib/idr.c +3 -0
+	if (id < idr->idr_base)
+		return NULL;
+
 	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);

If this underflows, we'll look up an entry which doesn't exist, which will return NULL.

lib/idr.c void *idr_replace(struct idr *idr, void *ptr, unsigned long id) · line 316

Quoted 10 lines
lib/idr.c +3 -0
@@ -302,6 +308,9 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 	void __rcu **slot = NULL;
 	void *entry;
 
+	if (id < idr->idr_base)
+		return ERR_PTR(-ENOENT);
+
 	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);

... just outside the context is this line:

        if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
                return ERR_PTR(-ENOENT);

Looking up an index which doesn't exist gets you a NULL slot, so you get -ENOENT anyway.

Quoted 7 lines

I did think about these possibilities when I was writing the code and convinced myself I didn't need them. If you have an example of a case where I got thast wrong, I'd love to see it.

More generally, the IDR is deprecated; I'm trying to convert users to the XArray. If you're adding a new user, can you use the XArray API instead?

Thanks for the explanation. I happened to walk by while code inspecting an existing out-of-tree user and thought there might be a small hole to fill but I agree it is unlikely that the underflow is likely to be a valid id.

Jordan

Signature · 2 lines
The Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a Linux Foundation Collaborative Project