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.ryabi...@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;
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
