Re: [PATCH] idr: fix a subtle bug in idr_get_next()

[Li Zefan]

On 2013/2/3 7:10, Tejun Heo wrote:
> 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@xxxxxxxxxx>

Don't we need to cc stable?

> Reported-by: David Teigland <teigland@xxxxxxxxxx>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@xxxxxxxxxxxxxx>
> ---
>  lib/idr.c |    9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/idr.c b/lib/idr.c
> index 6482390..ca5aa00 100644
> --- a/lib/idr.c
> +++ b/lib/idr.c
> @@ -625,7 +625,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
>  			return p;
>  		}
>  
> -		id += 1 << n;
> +		/*
> +		 * Proceed to the next layer at the current level.  Unlike
> +		 * idr_for_each(), @id isn't guaranteed to be aligned to
> +		 * layer boundary at this point and adding 1 << n may
> +		 * incorrectly skip IDs.  Make sure we jump to the
> +		 * beginning of the next layer using round_up().
> +		 */
> +		id = round_up(id + 1, 1 << n);
>  		while (n < fls(id)) {
>  			n += IDR_BITS;
>  			p = *--paa;
> --

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/