linux-kernel - Re: [PATCH] idr: fix a subtle bug in idr_get

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <510F2D86.5050408@huawei.com>
Date:	Mon, 4 Feb 2013 11:39:50 +0800
From:	Li Zefan <lizefan@...wei.com>
To:	Tejun Heo <tj@...nel.org>
CC:	David Teigland <teigland@...hat.com>, <akpm@...ux-foundation.org>,
	<rusty@...tcorp.com.au>, <linux-kernel@...r.kernel.org>,
	Christine Caulfield <ccaulfie@...hat.com>,
	<cluster-devel@...hat.com>,
	KAMEZAWA Hiroyuki <kamezawa.hiroyu@...fujitsu.com>
Subject: Re: [PATCH] idr: fix a subtle bug in idr_get_next()

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@...nel.org>

Don't we need to cc stable?

> Reported-by: David Teigland <teigland@...hat.com>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@...fujitsu.com>
> ---
>  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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/