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

[Andrey Ryabinin <a.ryabinin@samsung.com>]

On 06/24/14 05:26, Lai Jiangshan wrote:
> 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)) {
> 			...
> 		}
> 	}
> 

This will work only for idr_for_each and idr_get_new, but not for __idr_remove_all, since we have to to free layers
in second loop:

		while (n < fls(id ^ bt_mask)) {
			if (p)
				free_layer(idp, p);
			n += IDR_BITS;
			p = *--paa;
		}



> 
>>
>> 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@samsung.com>
>> ---
>>  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;
> 
>