diff options
authorTejun Heo2013-02-27 19:03:34 -0600
committerGreg Kroah-Hartman2013-03-03 16:09:04 -0600
commit4ec348232dc21cf79b62f32e0bdb099c9d817941 (patch)
parent975398374dac831d5d5c2825615c489aee24ea3a (diff)
idr: fix a subtle bug in idr_get_next()
commit 6cdae7416a1c45c2ce105a78187d9b7e8feb9e24 upstream. The iteration logic of idr_get_next() is borrowed mostly verbatim from idr_for_each(). It walks down the tree looking for the slot matching the current ID. If the matching slot is not found, the ID is incremented by the distance of single slot at the given level and repeats. The implementation assumes that during the whole iteration id is aligned to the layer boundaries of the level closest to the leaf, which is true for all iterations starting from zero or an existing element and thus is fine for idr_for_each(). However, idr_get_next() may be given any point and if the starting id hits in the middle of a non-existent layer, increment to the next layer will end up skipping the same offset into it. For example, an IDR with IDs filled between [64, 127] would look like the following. [ 0 64 ... ] /----/ | | | NULL [ 64 ... 127 ] If idr_get_next() is called with 63 as the starting point, it will try to follow down the pointer from 0. As it is NULL, it will then try to proceed to the next slot in the same level by adding the slot distance at that level which is 64 - making the next try 127. It goes around the loop and finds and returns 127 skipping [64, 126]. Note that this bug also triggers in idr_for_each_entry() loop which deletes during iteration as deletions can make layers go away leaving the iteration with unaligned ID into missing layers. Fix it by ensuring proceeding to the next slot doesn't carry over the unaligned offset - ie. use round_up(id + 1, slot_distance) instead of id += slot_distance. Signed-off-by: Tejun Heo <tj@kernel.org> Reported-by: David Teigland <teigland@redhat.com> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
1 files changed, 8 insertions, 1 deletions
diff --git a/lib/idr.c b/lib/idr.c
index e15502e8b21..b0540c6a0ec 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -621,7 +621,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
621 return p; 621 return p;
622 } 622 }
623 623
624 id += 1 << n; 624 /*
625 * Proceed to the next layer at the current level. Unlike
626 * idr_for_each(), @id isn't guaranteed to be aligned to
627 * layer boundary at this point and adding 1 << n may
628 * incorrectly skip IDs. Make sure we jump to the
629 * beginning of the next layer using round_up().
630 */
631 id = round_up(id + 1, 1 << n);
625 while (n < fls(id)) { 632 while (n < fls(id)) {
626 n += IDR_BITS; 633 n += IDR_BITS;
627 p = *--paa; 634 p = *--paa;