Re: [PATCH] lib: idr: fix out-of-bounds pointer dereference

[Lai Jiangshan]

On 06/23/2014 09:37 PM, Andrey Ryabinin wrote:
> I'm working on address sanitizer project for kernel. Recently we started
> experiments with stack instrumentation, to detect out-of-bounds
> read/write bugs on stack.
> 
> Just after booting I've hit out-of-bounds read on stack in idr_for_each
> (and in __idr_remove_all as well):
> 
> 	struct idr_layer **paa = &pa[0];
> 
> 	while (id >= 0 && id <= max) {
> 		...
> 		while (n < fls(id)) {
> 			n += IDR_BITS;
> 			p = *--paa; <--- here we are reading pa[-1] value.
> 		}
> 	}

I prefer to moving the loop-exit-condition-checking code down:

	if (id < 0 || id > max)		/* only idr_get_next() needs this branch */
		return ...

	for (;;) {			/* move out from here */
		...
		increase the @id;
		if (id < 0 || id > max)	/* move to here */
			break;
		while (n < fls(id)) {
			...
		}
	}


> 
> Despite the fact that after this dereference we are exiting out of loop and
> never use p, such behaviour is undefined and should be avoided.
> 
> Fix this by moving pointer derference to the beggining of the loop, right
> before we will use it.
> 
> Signed-off-by: Andrey Ryabinin <a.ryabinin@xxxxxxxxxxx>
> ---
>  lib/idr.c | 25 ++++++++++++++-----------
>  1 file changed, 14 insertions(+), 11 deletions(-)
> 
> diff --git a/lib/idr.c b/lib/idr.c
> index 39158ab..50be3fa 100644
> --- a/lib/idr.c
> +++ b/lib/idr.c
> @@ -590,26 +590,27 @@ static void __idr_remove_all(struct idr *idp)
>  	struct idr_layer **paa = &pa[0];
>  
>  	n = idp->layers * IDR_BITS;
> -	p = idp->top;
> +	*paa = idp->top;
>  	RCU_INIT_POINTER(idp->top, NULL);
>  	max = idr_max(idp->layers);
>  
>  	id = 0;
>  	while (id >= 0 && id <= max) {
> +		p = *paa;
>  		while (n > IDR_BITS && p) {
>  			n -= IDR_BITS;
> -			*paa++ = p;
>  			p = p->ary[(id >> n) & IDR_MASK];
> +			*++paa = p;
>  		}
>  
>  		bt_mask = id;
>  		id += 1 << n;
>  		/* Get the highest bit that the above add changed from 0->1. */
>  		while (n < fls(id ^ bt_mask)) {
> -			if (p)
> -				free_layer(idp, p);
> +			if (*paa)
> +				free_layer(idp, *paa);
>  			n += IDR_BITS;
> -			p = *--paa;
> +			--paa;
>  		}
>  	}
>  	idp->layers = 0;
> @@ -692,15 +693,16 @@ int idr_for_each(struct idr *idp,
>  	struct idr_layer **paa = &pa[0];
>  
>  	n = idp->layers * IDR_BITS;
> -	p = rcu_dereference_raw(idp->top);
> +	*paa = rcu_dereference_raw(idp->top);
>  	max = idr_max(idp->layers);
>  
>  	id = 0;
>  	while (id >= 0 && id <= max) {
> +		p = *paa;
>  		while (n > 0 && p) {
>  			n -= IDR_BITS;
> -			*paa++ = p;
>  			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
> +			*++paa = p;
>  		}
>  
>  		if (p) {
> @@ -712,7 +714,7 @@ int idr_for_each(struct idr *idp,
>  		id += 1 << n;
>  		while (n < fls(id)) {
>  			n += IDR_BITS;
> -			p = *--paa;
> +			--paa;
>  		}
>  	}
>  
> @@ -740,17 +742,18 @@ void *idr_get_next(struct idr *idp, int *nextidp)
>  	int n, max;
>  
>  	/* find first ent */
> -	p = rcu_dereference_raw(idp->top);
> +	p = *paa = rcu_dereference_raw(idp->top);
>  	if (!p)
>  		return NULL;
>  	n = (p->layer + 1) * IDR_BITS;
>  	max = idr_max(p->layer + 1);
>  
>  	while (id >= 0 && id <= max) {
> +		p = *paa;
>  		while (n > 0 && p) {
>  			n -= IDR_BITS;
> -			*paa++ = p;
>  			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
> +			*++paa = p;
>  		}
>  
>  		if (p) {
> @@ -768,7 +771,7 @@ void *idr_get_next(struct idr *idp, int *nextidp)
>  		id = round_up(id + 1, 1 << n);
>  		while (n < fls(id)) {
>  			n += IDR_BITS;
> -			p = *--paa;
> +			--paa;
>  		}
>  	}
>  	return NULL;

--
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/