[PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[js1304]

From: Joonsoo Kim <iamjoonsoo.kim@lge.com>

There are two bugs on qlist_move_cache(). One is that qlist's tail
isn't set properly. curr->next can be NULL since it is singly linked
list and NULL value on tail is invalid if there is one item on qlist.
Another one is that if cache is matched, qlist_put() is called and
it will set curr->next to NULL. It would cause to stop the loop
prematurely.

These problems come from complicated implementation so I'd like to
re-implement it completely. Implementation in this patch is really
simple. Iterate all qlist_nodes and put them to appropriate list.

Unfortunately, I got this bug sometime ago and lose oops message.
But, the bug looks trivial and no need to attach oops.

v3: fix build warning

Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/kasan/quarantine.c | 21 +++++++--------------
 1 file changed, 7 insertions(+), 14 deletions(-)

diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
index 4973505..cf92494 100644
--- a/mm/kasan/quarantine.c
+++ b/mm/kasan/quarantine.c
@@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
 				   struct qlist_head *to,
 				   struct kmem_cache *cache)
 {
-	struct qlist_node *prev = NULL, *curr;
+	struct qlist_node *curr;
 
 	if (unlikely(qlist_empty(from)))
 		return;
 
 	curr = from->head;
+	qlist_init(from);
 	while (curr) {
 		struct qlist_node *qlink = curr;
 		struct kmem_cache *obj_cache = qlink_to_cache(qlink);
 
-		if (obj_cache == cache) {
-			if (unlikely(from->head == qlink)) {
-				from->head = curr->next;
-				prev = curr;
-			} else
-				prev->next = curr->next;
-			if (unlikely(from->tail == qlink))
-				from->tail = curr->next;
-			from->bytes -= cache->size;
-			qlist_put(to, qlink, cache->size);
-		} else {
-			prev = curr;
-		}
 		curr = curr->next;
+
+		if (obj_cache == cache)
+			qlist_put(to, qlink, cache->size);
+		else
+			qlist_put(from, qlink, cache->size);
 	}
 }
 
-- 
1.9.1

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Dmitry Vyukov]

On Fri, Jul 1, 2016 at 4:02 PM,  <js1304@gmail.com> wrote:
> From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>
> There are two bugs on qlist_move_cache(). One is that qlist's tail
> isn't set properly. curr->next can be NULL since it is singly linked
> list and NULL value on tail is invalid if there is one item on qlist.
> Another one is that if cache is matched, qlist_put() is called and
> it will set curr->next to NULL. It would cause to stop the loop
> prematurely.
>
> These problems come from complicated implementation so I'd like to
> re-implement it completely. Implementation in this patch is really
> simple. Iterate all qlist_nodes and put them to appropriate list.
>
> Unfortunately, I got this bug sometime ago and lose oops message.
> But, the bug looks trivial and no need to attach oops.
>
> v3: fix build warning
>
> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> ---
>  mm/kasan/quarantine.c | 21 +++++++--------------
>  1 file changed, 7 insertions(+), 14 deletions(-)
>
> diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
> index 4973505..cf92494 100644
> --- a/mm/kasan/quarantine.c
> +++ b/mm/kasan/quarantine.c
> @@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
>                                    struct qlist_head *to,
>                                    struct kmem_cache *cache)
>  {
> -       struct qlist_node *prev = NULL, *curr;
> +       struct qlist_node *curr;
>
>         if (unlikely(qlist_empty(from)))
>                 return;
>
>         curr = from->head;
> +       qlist_init(from);
>         while (curr) {
>                 struct qlist_node *qlink = curr;
>                 struct kmem_cache *obj_cache = qlink_to_cache(qlink);
>
> -               if (obj_cache == cache) {
> -                       if (unlikely(from->head == qlink)) {
> -                               from->head = curr->next;
> -                               prev = curr;
> -                       } else
> -                               prev->next = curr->next;
> -                       if (unlikely(from->tail == qlink))
> -                               from->tail = curr->next;
> -                       from->bytes -= cache->size;
> -                       qlist_put(to, qlink, cache->size);
> -               } else {
> -                       prev = curr;
> -               }
>                 curr = curr->next;
> +
> +               if (obj_cache == cache)
> +                       qlist_put(to, qlink, cache->size);
> +               else
> +                       qlist_put(from, qlink, cache->size);

This line is wrong. If obj_cache != cache, object size != cache->size.
Quarantine contains objects of different sizes.

>         }
>  }
>
> --
> 1.9.1
>

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Joonsoo Kim]

2016-07-01 23:03 GMT+09:00 Dmitry Vyukov <dvyukov@google.com>:
> On Fri, Jul 1, 2016 at 4:02 PM,  <js1304@gmail.com> wrote:
>> From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>>
>> There are two bugs on qlist_move_cache(). One is that qlist's tail
>> isn't set properly. curr->next can be NULL since it is singly linked
>> list and NULL value on tail is invalid if there is one item on qlist.
>> Another one is that if cache is matched, qlist_put() is called and
>> it will set curr->next to NULL. It would cause to stop the loop
>> prematurely.
>>
>> These problems come from complicated implementation so I'd like to
>> re-implement it completely. Implementation in this patch is really
>> simple. Iterate all qlist_nodes and put them to appropriate list.
>>
>> Unfortunately, I got this bug sometime ago and lose oops message.
>> But, the bug looks trivial and no need to attach oops.
>>
>> v3: fix build warning
>>
>> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>> ---
>>  mm/kasan/quarantine.c | 21 +++++++--------------
>>  1 file changed, 7 insertions(+), 14 deletions(-)
>>
>> diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
>> index 4973505..cf92494 100644
>> --- a/mm/kasan/quarantine.c
>> +++ b/mm/kasan/quarantine.c
>> @@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
>>                                    struct qlist_head *to,
>>                                    struct kmem_cache *cache)
>>  {
>> -       struct qlist_node *prev = NULL, *curr;
>> +       struct qlist_node *curr;
>>
>>         if (unlikely(qlist_empty(from)))
>>                 return;
>>
>>         curr = from->head;
>> +       qlist_init(from);
>>         while (curr) {
>>                 struct qlist_node *qlink = curr;
>>                 struct kmem_cache *obj_cache = qlink_to_cache(qlink);
>>
>> -               if (obj_cache == cache) {
>> -                       if (unlikely(from->head == qlink)) {
>> -                               from->head = curr->next;
>> -                               prev = curr;
>> -                       } else
>> -                               prev->next = curr->next;
>> -                       if (unlikely(from->tail == qlink))
>> -                               from->tail = curr->next;
>> -                       from->bytes -= cache->size;
>> -                       qlist_put(to, qlink, cache->size);
>> -               } else {
>> -                       prev = curr;
>> -               }
>>                 curr = curr->next;
>> +
>> +               if (obj_cache == cache)
>> +                       qlist_put(to, qlink, cache->size);
>> +               else
>> +                       qlist_put(from, qlink, cache->size);
>
> This line is wrong. If obj_cache != cache, object size != cache->size.
> Quarantine contains objects of different sizes.

You're right. 11 pm is not good time to work. :/
If it is fixed, the patch looks correct to you?
I will fix it and send v4 on next week.

Thanks.

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Dmitry Vyukov]

On Fri, Jul 1, 2016 at 4:09 PM, Joonsoo Kim <js1304@gmail.com> wrote:
> 2016-07-01 23:03 GMT+09:00 Dmitry Vyukov <dvyukov@google.com>:
>> On Fri, Jul 1, 2016 at 4:02 PM,  <js1304@gmail.com> wrote:
>>> From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>>>
>>> There are two bugs on qlist_move_cache(). One is that qlist's tail
>>> isn't set properly. curr->next can be NULL since it is singly linked
>>> list and NULL value on tail is invalid if there is one item on qlist.
>>> Another one is that if cache is matched, qlist_put() is called and
>>> it will set curr->next to NULL. It would cause to stop the loop
>>> prematurely.
>>>
>>> These problems come from complicated implementation so I'd like to
>>> re-implement it completely. Implementation in this patch is really
>>> simple. Iterate all qlist_nodes and put them to appropriate list.
>>>
>>> Unfortunately, I got this bug sometime ago and lose oops message.
>>> But, the bug looks trivial and no need to attach oops.
>>>
>>> v3: fix build warning
>>>
>>> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>>> ---
>>>  mm/kasan/quarantine.c | 21 +++++++--------------
>>>  1 file changed, 7 insertions(+), 14 deletions(-)
>>>
>>> diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
>>> index 4973505..cf92494 100644
>>> --- a/mm/kasan/quarantine.c
>>> +++ b/mm/kasan/quarantine.c
>>> @@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
>>>                                    struct qlist_head *to,
>>>                                    struct kmem_cache *cache)
>>>  {
>>> -       struct qlist_node *prev = NULL, *curr;
>>> +       struct qlist_node *curr;
>>>
>>>         if (unlikely(qlist_empty(from)))
>>>                 return;
>>>
>>>         curr = from->head;
>>> +       qlist_init(from);
>>>         while (curr) {
>>>                 struct qlist_node *qlink = curr;
>>>                 struct kmem_cache *obj_cache = qlink_to_cache(qlink);
>>>
>>> -               if (obj_cache == cache) {
>>> -                       if (unlikely(from->head == qlink)) {
>>> -                               from->head = curr->next;
>>> -                               prev = curr;
>>> -                       } else
>>> -                               prev->next = curr->next;
>>> -                       if (unlikely(from->tail == qlink))
>>> -                               from->tail = curr->next;
>>> -                       from->bytes -= cache->size;
>>> -                       qlist_put(to, qlink, cache->size);
>>> -               } else {
>>> -                       prev = curr;
>>> -               }
>>>                 curr = curr->next;
>>> +
>>> +               if (obj_cache == cache)
>>> +                       qlist_put(to, qlink, cache->size);
>>> +               else
>>> +                       qlist_put(from, qlink, cache->size);
>>
>> This line is wrong. If obj_cache != cache, object size != cache->size.
>> Quarantine contains objects of different sizes.
>
> You're right. 11 pm is not good time to work. :/
> If it is fixed, the patch looks correct to you?
> I will fix it and send v4 on next week.


I don't see anything else wrong. But I need to see how you fix the size issue.
Performance of this operation is not particularly critical, so the
simpler the better.

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Andrey Ryabinin]

On 07/01/2016 05:02 PM, js1304@gmail.com wrote:
> From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> 
> There are two bugs on qlist_move_cache(). One is that qlist's tail
> isn't set properly. curr->next can be NULL since it is singly linked
> list and NULL value on tail is invalid if there is one item on qlist.
> Another one is that if cache is matched, qlist_put() is called and
> it will set curr->next to NULL. It would cause to stop the loop
> prematurely.
> 
> These problems come from complicated implementation so I'd like to
> re-implement it completely. Implementation in this patch is really
> simple. Iterate all qlist_nodes and put them to appropriate list.
> 
> Unfortunately, I got this bug sometime ago and lose oops message.
> But, the bug looks trivial and no need to attach oops.
> 
> v3: fix build warning
> 
> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> ---
>  mm/kasan/quarantine.c | 21 +++++++--------------
>  1 file changed, 7 insertions(+), 14 deletions(-)
> 
> diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
> index 4973505..cf92494 100644
> --- a/mm/kasan/quarantine.c
> +++ b/mm/kasan/quarantine.c
> @@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
>  				   struct qlist_head *to,
>  				   struct kmem_cache *cache)
>  {
> -	struct qlist_node *prev = NULL, *curr;
> +	struct qlist_node *curr;
>  
>  	if (unlikely(qlist_empty(from)))
>  		return;
>  
>  	curr = from->head;
> +	qlist_init(from);
>  	while (curr) {
>  		struct qlist_node *qlink = curr;

Can you please also get rid of either qlink or curr.
Those are essentially the same pointers.

>  		struct kmem_cache *obj_cache = qlink_to_cache(qlink);
>  
> -		if (obj_cache == cache) {
> -			if (unlikely(from->head == qlink)) {
> -				from->head = curr->next;
> -				prev = curr;
> -			} else
> -				prev->next = curr->next;
> -			if (unlikely(from->tail == qlink))
> -				from->tail = curr->next;
> -			from->bytes -= cache->size;
> -			qlist_put(to, qlink, cache->size);
> -		} else {
> -			prev = curr;
> -		}
>  		curr = curr->next;
> +
> +		if (obj_cache == cache)
> +			qlist_put(to, qlink, cache->size);
> +		else
> +			qlist_put(from, qlink, cache->size);
>  	}
>  }
>  
> 

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Andrey Ryabinin]

On 07/01/2016 05:15 PM, Dmitry Vyukov wrote:
> On Fri, Jul 1, 2016 at 4:09 PM, Joonsoo Kim <js1304@gmail.com> wrote:
>> 2016-07-01 23:03 GMT+09:00 Dmitry Vyukov <dvyukov@google.com>:

>>>> +
>>>> +               if (obj_cache == cache)
>>>> +                       qlist_put(to, qlink, cache->size);
>>>> +               else
>>>> +                       qlist_put(from, qlink, cache->size);
>>>
>>> This line is wrong. If obj_cache != cache, object size != cache->size.
>>> Quarantine contains objects of different sizes.
>>
>> You're right. 11 pm is not good time to work. :/
>> If it is fixed, the patch looks correct to you?
>> I will fix it and send v4 on next week.
> 
> 
> I don't see anything else wrong. But I need to see how you fix the size issue.
> Performance of this operation is not particularly critical, so the
> simpler the better.

Is there any other way besides obvious: s/cache->size/obj_cache->size ?

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Dmitry Vyukov]

On Fri, Jul 1, 2016 at 4:18 PM, Andrey Ryabinin <aryabinin@virtuozzo.com> wrote:
>
>
> On 07/01/2016 05:15 PM, Dmitry Vyukov wrote:
>> On Fri, Jul 1, 2016 at 4:09 PM, Joonsoo Kim <js1304@gmail.com> wrote:
>>> 2016-07-01 23:03 GMT+09:00 Dmitry Vyukov <dvyukov@google.com>:
>
>>>>> +
>>>>> +               if (obj_cache == cache)
>>>>> +                       qlist_put(to, qlink, cache->size);
>>>>> +               else
>>>>> +                       qlist_put(from, qlink, cache->size);
>>>>
>>>> This line is wrong. If obj_cache != cache, object size != cache->size.
>>>> Quarantine contains objects of different sizes.
>>>
>>> You're right. 11 pm is not good time to work. :/
>>> If it is fixed, the patch looks correct to you?
>>> I will fix it and send v4 on next week.
>>
>>
>> I don't see anything else wrong. But I need to see how you fix the size issue.
>> Performance of this operation is not particularly critical, so the
>> simpler the better.
>
> Is there any other way besides obvious: s/cache->size/obj_cache->size ?

We can remember the original bytes, then subtract
num_objects_moved*cache->size from it and assign to from->bytes.

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Joonsoo Kim]

2016-07-01 23:20 GMT+09:00 Dmitry Vyukov <dvyukov@google.com>:
> On Fri, Jul 1, 2016 at 4:18 PM, Andrey Ryabinin <aryabinin@virtuozzo.com> wrote:
>>
>>
>> On 07/01/2016 05:15 PM, Dmitry Vyukov wrote:
>>> On Fri, Jul 1, 2016 at 4:09 PM, Joonsoo Kim <js1304@gmail.com> wrote:
>>>> 2016-07-01 23:03 GMT+09:00 Dmitry Vyukov <dvyukov@google.com>:
>>
>>>>>> +
>>>>>> +               if (obj_cache == cache)
>>>>>> +                       qlist_put(to, qlink, cache->size);
>>>>>> +               else
>>>>>> +                       qlist_put(from, qlink, cache->size);
>>>>>
>>>>> This line is wrong. If obj_cache != cache, object size != cache->size.
>>>>> Quarantine contains objects of different sizes.
>>>>
>>>> You're right. 11 pm is not good time to work. :/
>>>> If it is fixed, the patch looks correct to you?
>>>> I will fix it and send v4 on next week.
>>>
>>>
>>> I don't see anything else wrong. But I need to see how you fix the size issue.
>>> Performance of this operation is not particularly critical, so the
>>> simpler the better.
>>
>> Is there any other way besides obvious: s/cache->size/obj_cache->size ?
>
> We can remember the original bytes, then subtract
> num_objects_moved*cache->size from it and assign to from->bytes.

I'd prefer s/cache->size/obj_cache->size. It looks simpler.
If there is no objection, I will use it on v4.

Thanks.

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Joonsoo Kim]

On Fri, Jul 01, 2016 at 05:17:10PM +0300, Andrey Ryabinin wrote:
> 
> 
> On 07/01/2016 05:02 PM, js1304@gmail.com wrote:
> > From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> > 
> > There are two bugs on qlist_move_cache(). One is that qlist's tail
> > isn't set properly. curr->next can be NULL since it is singly linked
> > list and NULL value on tail is invalid if there is one item on qlist.
> > Another one is that if cache is matched, qlist_put() is called and
> > it will set curr->next to NULL. It would cause to stop the loop
> > prematurely.
> > 
> > These problems come from complicated implementation so I'd like to
> > re-implement it completely. Implementation in this patch is really
> > simple. Iterate all qlist_nodes and put them to appropriate list.
> > 
> > Unfortunately, I got this bug sometime ago and lose oops message.
> > But, the bug looks trivial and no need to attach oops.
> > 
> > v3: fix build warning
> > 
> > Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> > ---
> >  mm/kasan/quarantine.c | 21 +++++++--------------
> >  1 file changed, 7 insertions(+), 14 deletions(-)
> > 
> > diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
> > index 4973505..cf92494 100644
> > --- a/mm/kasan/quarantine.c
> > +++ b/mm/kasan/quarantine.c
> > @@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
> >  				   struct qlist_head *to,
> >  				   struct kmem_cache *cache)
> >  {
> > -	struct qlist_node *prev = NULL, *curr;
> > +	struct qlist_node *curr;
> >  
> >  	if (unlikely(qlist_empty(from)))
> >  		return;
> >  
> >  	curr = from->head;
> > +	qlist_init(from);
> >  	while (curr) {
> >  		struct qlist_node *qlink = curr;
> 
> Can you please also get rid of either qlink or curr.
> Those are essentially the same pointers.

Hello,

Before putting the qlist_node to the list, we need to calculate
curr->next and remember it to iterate the list. I use curr
for this purpose so qlink and curr are not the same pointer.

Thanks.

Re: [PATCH v3] kasan/quarantine: fix bugs on qlist_move_cache()

[Andrey Ryabinin]

On 07/04/2016 07:36 AM, Joonsoo Kim wrote:
> On Fri, Jul 01, 2016 at 05:17:10PM +0300, Andrey Ryabinin wrote:
>>
>>
>> On 07/01/2016 05:02 PM, js1304@gmail.com wrote:
>>> From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>>>
>>> There are two bugs on qlist_move_cache(). One is that qlist's tail
>>> isn't set properly. curr->next can be NULL since it is singly linked
>>> list and NULL value on tail is invalid if there is one item on qlist.
>>> Another one is that if cache is matched, qlist_put() is called and
>>> it will set curr->next to NULL. It would cause to stop the loop
>>> prematurely.
>>>
>>> These problems come from complicated implementation so I'd like to
>>> re-implement it completely. Implementation in this patch is really
>>> simple. Iterate all qlist_nodes and put them to appropriate list.
>>>
>>> Unfortunately, I got this bug sometime ago and lose oops message.
>>> But, the bug looks trivial and no need to attach oops.
>>>
>>> v3: fix build warning
>>>
>>> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>>> ---
>>>  mm/kasan/quarantine.c | 21 +++++++--------------
>>>  1 file changed, 7 insertions(+), 14 deletions(-)
>>>
>>> diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
>>> index 4973505..cf92494 100644
>>> --- a/mm/kasan/quarantine.c
>>> +++ b/mm/kasan/quarantine.c
>>> @@ -238,30 +238,23 @@ static void qlist_move_cache(struct qlist_head *from,
>>>  				   struct qlist_head *to,
>>>  				   struct kmem_cache *cache)
>>>  {
>>> -	struct qlist_node *prev = NULL, *curr;
>>> +	struct qlist_node *curr;
>>>  
>>>  	if (unlikely(qlist_empty(from)))
>>>  		return;
>>>  
>>>  	curr = from->head;
>>> +	qlist_init(from);
>>>  	while (curr) {
>>>  		struct qlist_node *qlink = curr;
>>
>> Can you please also get rid of either qlink or curr.
>> Those are essentially the same pointers.
> 
> Hello,
> 
> Before putting the qlist_node to the list, we need to calculate
> curr->next and remember it to iterate the list. I use curr
> for this purpose so qlink and curr are not the same pointer.
> 

Right, I missed the fact that qlist_put() changes ->next pointer, thus we  can't fetch ->next after qlist_put().

> Thanks.
>