From 3afb69cb5572b3c8c898c00880803cf1a49852c4 Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Fri, 6 Jun 2014 14:37:10 -0700 Subject: idr: fix overflow bug during maximum ID calculation at maximum height idr_replace() open-codes the logic to calculate the maximum valid ID given the height of the idr tree; unfortunately, the open-coded logic doesn't account for the fact that the top layer may have unused slots and over-shifts the limit to zero when the tree is at its maximum height. The following test code shows it fails to replace the value for id=((1<<27)+42): static void test5(void) { int id; DEFINE_IDR(test_idr); #define TEST5_START ((1<<27)+42) /* use the highest layer */ printk(KERN_INFO "Start test5\n"); id = idr_alloc(&test_idr, (void *)1, TEST5_START, 0, GFP_KERNEL); BUG_ON(id != TEST5_START); TEST_BUG_ON(idr_replace(&test_idr, (void *)2, TEST5_START) != (void *)1); idr_destroy(&test_idr); printk(KERN_INFO "End of test5\n"); } Fix the bug by using idr_max() which correctly takes into account the maximum allowed shift. sub_alloc() shares the same problem and may incorrectly fail with -EAGAIN; however, this bug doesn't affect correct operation because idr_get_empty_slot(), which already uses idr_max(), retries with the increased @id in such cases. [tj@kernel.org: Updated patch description.] Signed-off-by: Lai Jiangshan Acked-by: Tejun Heo Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 2642fa8e424d..4df67928816e 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -249,7 +249,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa, id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; /* if already at the top layer, we need to grow */ - if (id >= 1 << (idp->layers * IDR_BITS)) { + if (id > idr_max(idp->layers)) { *starting_id = id; return -EAGAIN; } @@ -811,12 +811,10 @@ void *idr_replace(struct idr *idp, void *ptr, int id) if (!p) return ERR_PTR(-EINVAL); - n = (p->layer+1) * IDR_BITS; - - if (id >= (1 << n)) + if (id > idr_max(p->layer + 1)) return ERR_PTR(-EINVAL); - n -= IDR_BITS; + n = p->layer * IDR_BITS; while ((n > 0) && p) { p = p->ary[(id >> n) & IDR_MASK]; n -= IDR_BITS; -- cgit v1.2.3 From 8f9f665a707721146f24a892b1a0da1ab4da1d58 Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Fri, 6 Jun 2014 14:37:11 -0700 Subject: idr: fix unexpected ID-removal when idr_remove(unallocated_id) If unallocated_id = (ANY * idr_max(idp->layers) + existing_id) is passed to idr_remove(). The existing_id will be removed unexpectedly. The following test shows this unexpected id-removal: static void test4(void) { int id; DEFINE_IDR(test_idr); printk(KERN_INFO "Start test4\n"); id = idr_alloc(&test_idr, (void *)1, 42, 43, GFP_KERNEL); BUG_ON(id != 42); idr_remove(&test_idr, 42 + IDR_SIZE); TEST_BUG_ON(idr_find(&test_idr, 42) != (void *)1); idr_destroy(&test_idr); printk(KERN_INFO "End of test4\n"); } ida_remove() shares the similar problem. It happens only when the caller tries to free an unallocated ID which is the caller's fault. It is not a bug. But it is better to add the proper check and complain rather than removing an existing_id silently. Signed-off-by: Lai Jiangshan Acked-by: Tejun Heo Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 4df67928816e..c4afd94bdf69 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -562,6 +562,11 @@ void idr_remove(struct idr *idp, int id) if (id < 0) return; + if (id > idr_max(idp->layers)) { + idr_remove_warning(id); + return; + } + sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); if (idp->top && idp->top->count == 1 && (idp->layers > 1) && idp->top->ary[0]) { @@ -1025,6 +1030,9 @@ void ida_remove(struct ida *ida, int id) int n; struct ida_bitmap *bitmap; + if (idr_id > idr_max(ida->idr.layers)) + goto err; + /* clear full bits while looking up the leaf idr_layer */ while ((shift > 0) && p) { n = (idr_id >> shift) & IDR_MASK; -- cgit v1.2.3 From aef0f62e87122c0fb90d5da660fd131acd0a9d67 Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Fri, 6 Jun 2014 14:37:12 -0700 Subject: idr: fix NULL pointer dereference when ida_remove(unallocated_id) If the ida has at least one existing id, and when an unallocated ID which meets a certain condition is passed to the ida_remove(), the system will crash because it hits NULL pointer dereference. The condition is that the unallocated ID shares the same lowest idr layer with the existing ID, but the idr slot would be different if the unallocated ID were to be allocated. In this case the matching idr slot for the unallocated_id is NULL, causing @bitmap to be NULL which the function dereferences without checking crashing the kernel. See the test code: static void test3(void) { int id; DEFINE_IDA(test_ida); printk(KERN_INFO "Start test3\n"); if (ida_pre_get(&test_ida, GFP_KERNEL) < 0) return; if (ida_get_new(&test_ida, &id) < 0) return; ida_remove(&test_ida, 4000); /* bug: null deference here */ printk(KERN_INFO "End of test3\n"); } It happens only when the caller tries to free an unallocated ID which is the caller's fault. It is not a bug. But it is better to add the proper check and complain rather than crashing the kernel. [tj@kernel.org: updated patch description] Signed-off-by: Lai Jiangshan Acked-by: Tejun Heo Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index c4afd94bdf69..36ff732fd2a6 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -1048,7 +1048,7 @@ void ida_remove(struct ida *ida, int id) __clear_bit(n, p->bitmap); bitmap = (void *)p->ary[n]; - if (!test_bit(offset, bitmap->bitmap)) + if (!bitmap || !test_bit(offset, bitmap->bitmap)) goto err; /* update bitmap and remove it if empty */ -- cgit v1.2.3 From b93804b2fcdb35cc45f95ad77cbe23cc620f6593 Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Fri, 6 Jun 2014 14:37:13 -0700 Subject: idr: fix idr_replace()'s returned error code When the smaller id is not found, idr_replace() returns -ENOENT. But when the id is bigger enough, idr_replace() returns -EINVAL, actually there is no difference between these two kinds of ids. These are all unallocated id, the return values of the idr_replace() for these ids should be the same: -ENOENT. Signed-off-by: Lai Jiangshan Acked-by: Tejun Heo Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 36ff732fd2a6..e79e051bddc1 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -814,10 +814,10 @@ void *idr_replace(struct idr *idp, void *ptr, int id) p = idp->top; if (!p) - return ERR_PTR(-EINVAL); + return ERR_PTR(-ENOENT); if (id > idr_max(p->layer + 1)) - return ERR_PTR(-EINVAL); + return ERR_PTR(-ENOENT); n = p->layer * IDR_BITS; while ((n > 0) && p) { -- cgit v1.2.3 From aefb76829742803751725bc75bcdc43fe803ac22 Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Fri, 6 Jun 2014 14:37:13 -0700 Subject: idr: don't need to shink the free list when idr_remove() After idr subsystem is changed to RCU-awared, the free layer will not go to the free list. The free list will not be filled up when idr_remove(). So we don't need to shink it too. Signed-off-by: Lai Jiangshan Acked-by: Tejun Heo Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 16 ---------------- 1 file changed, 16 deletions(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index e79e051bddc1..9ed37a7a031d 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -18,12 +18,6 @@ * pointer or what ever, we treat it as a (void *). You can pass this * id to a user for him to pass back at a later time. You then pass * that id to this code and it returns your pointer. - - * You can release ids at any time. When all ids are released, most of - * the memory is returned (we keep MAX_IDR_FREE) in a local pool so we - * don't need to go to the memory "store" during an id allocate, just - * so you don't need to be too concerned about locking and conflicts - * with the slab allocator. */ #ifndef TEST // to test in user space... @@ -584,16 +578,6 @@ void idr_remove(struct idr *idp, int id) bitmap_clear(to_free->bitmap, 0, IDR_SIZE); free_layer(idp, to_free); } - while (idp->id_free_cnt >= MAX_IDR_FREE) { - p = get_from_free_list(idp); - /* - * Note: we don't call the rcu callback here, since the only - * layers that fall into the freelist are those that have been - * preallocated. - */ - kmem_cache_free(idr_layer_cache, p); - } - return; } EXPORT_SYMBOL(idr_remove); -- cgit v1.2.3 From 15f3ec3f238a44181e1ae85b3cc2c27b9fece01b Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Fri, 6 Jun 2014 14:37:14 -0700 Subject: idr: reduce the unneeded check in free_layer() If "idr->hint == p" is true, it also implies "idr->hint" is true(not NULL). Signed-off-by: Lai Jiangshan Acked-by: Tejun Heo Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/idr.c') diff --git a/lib/idr.c b/lib/idr.c index 9ed37a7a031d..39158abebad1 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -145,7 +145,7 @@ static void idr_layer_rcu_free(struct rcu_head *head) static inline void free_layer(struct idr *idr, struct idr_layer *p) { - if (idr->hint && idr->hint == p) + if (idr->hint == p) RCU_INIT_POINTER(idr->hint, NULL); call_rcu(&p->rcu_head, idr_layer_rcu_free); } -- cgit v1.2.3