[PATCH] kasan/quarantine: fix NULL pointer dereference bug

[js1...@gmail.com]

From: Joonsoo Kim <iamjoon...@lge.com>

If we move an item on qlist's tail, we need to update qlist's tail
properly. curr->next can be NULL since it is singly linked list
so it is invalid for tail. curr is scheduled to be moved so
using prev would be correct.

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

Signed-off-by: Joonsoo Kim <iamjoon...@lge.com>
---
mm/kasan/quarantine.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
index 4973505..9a132fd 100644
--- a/mm/kasan/quarantine.c
+++ b/mm/kasan/quarantine.c
@@ -255,7 +255,7 @@ static void qlist_move_cache(struct qlist_head *from,
} else
prev->next = curr->next;
if (unlikely(from->tail == qlink))
- from->tail = curr->next;
+ from->tail = prev;
from->bytes -= cache->size;
qlist_put(to, qlink, cache->size);
} else {
--
1.9.1

[Andrey Ryabinin]

On 07/01/2016 10:53 AM, js1...@gmail.com wrote:
> From: Joonsoo Kim <iamjoon...@lge.com>
>
> If we move an item on qlist's tail, we need to update qlist's tail
> properly. curr->next can be NULL since it is singly linked list
> so it is invalid for tail. curr is scheduled to be moved so
> using prev would be correct.

Hmm.. prev may be the element that moved in 'to' list. We need to assign the last element
from which is in ther 'from' list.

[Kuthonuzo Luruo]

On Fri, Jul 1, 2016 at 1:41 PM, Andrey Ryabinin <arya...@virtuozzo.com> wrote:
>
>
> On 07/01/2016 10:53 AM, js1...@gmail.com wrote:
>> From: Joonsoo Kim <iamjoon...@lge.com>
>>
>> If we move an item on qlist's tail, we need to update qlist's tail
>> properly. curr->next can be NULL since it is singly linked list
>> so it is invalid for tail. curr is scheduled to be moved so
>> using prev would be correct.
>
> Hmm.. prev may be the element that moved in 'to' list. We need to assign the last element
> from which is in ther 'from' list.

something like this should handle qlink == head == tail:

--- a/mm/kasan/quarantine.c
+++ b/mm/kasan/quarantine.c
@@ -251,11 +251,11 @@ static void qlist_move_cache(struct qlist_head *from,
if (obj_cache == cache) {
if (unlikely(from->head == qlink)) {
from->head = curr->next;
- prev = curr;
+ prev = from->head;

> --
> You received this message because you are subscribed to the Google Groups "kasan-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kasan-dev+...@googlegroups.com.
> To post to this group, send email to kasa...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kasan-dev/577625CC.8080907%40virtuozzo.com.
> For more options, visit https://groups.google.com/d/optout.

[Andrey Ryabinin]

On 07/01/2016 01:55 PM, Kuthonuzo Luruo wrote:
> On Fri, Jul 1, 2016 at 1:41 PM, Andrey Ryabinin <arya...@virtuozzo.com> wrote:
>>
>>
>> On 07/01/2016 10:53 AM, js1...@gmail.com wrote:
>>> From: Joonsoo Kim <iamjoon...@lge.com>
>>>
>>> If we move an item on qlist's tail, we need to update qlist's tail
>>> properly. curr->next can be NULL since it is singly linked list
>>> so it is invalid for tail. curr is scheduled to be moved so
>>> using prev would be correct.
>>
>> Hmm.. prev may be the element that moved in 'to' list. We need to assign the last element
>> from which is in ther 'from' list.
>
> something like this should handle qlink == head == tail:
>
> --- a/mm/kasan/quarantine.c
> +++ b/mm/kasan/quarantine.c
> @@ -251,11 +251,11 @@ static void qlist_move_cache(struct qlist_head *from,
> if (obj_cache == cache) {
> if (unlikely(from->head == qlink)) {
> from->head = curr->next;
> - prev = curr;
> + prev = from->head;

This will break 'to' list.

[js1...@gmail.com]

From: Joonsoo Kim <iamjoon...@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.

Signed-off-by: Joonsoo Kim <iamjoon...@lge.com>
---

mm/kasan/quarantine.c | 22 ++++++++--------------
1 file changed, 8 insertions(+), 14 deletions(-)

diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
index 4973505..061d39b 100644
--- a/mm/kasan/quarantine.c
+++ b/mm/kasan/quarantine.c
@@ -238,30 +238,24 @@ 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;
+ struct qlist_node *head = NULL, *tail = NULL;

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

[Joonsoo Kim]

2016-07-01 17:11 GMT+09:00 Andrey Ryabinin <arya...@virtuozzo.com>:
>
>
> On 07/01/2016 10:53 AM, js1...@gmail.com wrote:
>> From: Joonsoo Kim <iamjoon...@lge.com>
>>
>> If we move an item on qlist's tail, we need to update qlist's tail
>> properly. curr->next can be NULL since it is singly linked list
>> so it is invalid for tail. curr is scheduled to be moved so
>> using prev would be correct.
>
> Hmm.. prev may be the element that moved in 'to' list. We need to assign the last element
> from which is in ther 'from' list.

You're right. Also, I find another bug on this function.
I manage them on v2 and sent.

Thanks.

[js1...@gmail.com]

From: Joonsoo Kim <iamjoon...@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 <iamjoon...@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;

[Joonsoo Kim]

2016-07-01 22:55 GMT+09:00 <js1...@gmail.com>:
> From: Joonsoo Kim <iamjoon...@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.
>
> Signed-off-by: Joonsoo Kim <iamjoon...@lge.com>

Please ignore this. It causes build warning. Please see v3.
Sorry for noise.

Thanks.

[Dmitry Vyukov]

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

> }
> }
>
> --
> 1.9.1
>

[Joonsoo Kim]

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.

[Dmitry Vyukov]

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.

[Andrey Ryabinin]

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

[Andrey Ryabinin]

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

[Dmitry Vyukov]

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

[Joonsoo Kim]

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

Thanks.

[kbuild test robot]

Hi,

[auto build test WARNING on v4.7-rc5]
[also build test WARNING on next-20160701]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url: https://github.com/0day-ci/linux/commits/js1304-gmail-com/kasan-quarantine-fix-bugs-on-qlist_move_cache/20160702-102811
config: x86_64-randconfig-r0-07021543 (attached as .config)
compiler: gcc-6 (Debian 6.1.1-1) 6.1.1 20160430
reproduce:
# save the attached .config to linux build tree
make ARCH=x86_64

All warnings (new ones prefixed by >>):

mm/kasan/quarantine.c: In function 'qlist_move_cache':
>> mm/kasan/quarantine.c:242:35: warning: unused variable 'tail' [-Wunused-variable]

struct qlist_node *head = NULL, *tail = NULL;

^~~~
>> mm/kasan/quarantine.c:242:21: warning: unused variable 'head' [-Wunused-variable]

struct qlist_node *head = NULL, *tail = NULL;

^~~~

vim +/tail +242 mm/kasan/quarantine.c

226 global_quarantine.bytes - QUARANTINE_LOW_SIZE)
227 break;
228 last = last->next;
229 }
230 qlist_move(&global_quarantine, last, &to_free, size_to_free);
231
232 spin_unlock_irqrestore(&quarantine_lock, flags);
233
234 qlist_free_all(&to_free, NULL);
235 }
236
237 static void qlist_move_cache(struct qlist_head *from,
238 struct qlist_head *to,
239 struct kmem_cache *cache)
240 {
241 struct qlist_node *curr;
> 242 struct qlist_node *head = NULL, *tail = NULL;
243
244 if (unlikely(qlist_empty(from)))
245 return;
246
247 curr = from->head;
248 qlist_init(from);
249 while (curr) {
250 struct qlist_node *qlink = curr;

---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation

[js1...@gmail.com]

From: Joonsoo Kim <iamjoon...@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.

v4: fix cache size bug s/cache->size/obj_cache->size/

v3: fix build warning

Signed-off-by: Joonsoo Kim <iamjoon...@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..b2e1827 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, obj_cache->size);
+ else
+ qlist_put(from, qlink, obj_cache->size);
}
}

--
1.9.1

[Joonsoo Kim]

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.

[Andrey Ryabinin]

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

> Thanks.
>

[Andrey Ryabinin]

Nit: Wouldn't be more appropriate to swap 'curr' and 'qlink' variable names?
Because now qlink is acts as a "current" pointer.

[Dmitry Vyukov]

Reviewed-by: Dmitry Vyukov <dvy...@google.com>

Thanks for fixing this!

[js1...@gmail.com]

From: Joonsoo Kim <iamjoon...@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.

v5: rename some variable for better readability

v4: fix cache size bug s/cache->size/obj_cache->size/
v3: fix build warning

Reviewed-by: Dmitry Vyukov <dvy...@google.com>

Signed-off-by: Joonsoo Kim <iamjoon...@lge.com>
---

mm/kasan/quarantine.c | 29 +++++++++++------------------
1 file changed, 11 insertions(+), 18 deletions(-)

diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
index 4973505..65793f1 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;

+ struct qlist_node *next = curr->next;
+ struct kmem_cache *obj_cache = qlink_to_cache(curr);

+
+ if (obj_cache == cache)

+ qlist_put(to, curr, obj_cache->size);
+ else
+ qlist_put(from, curr, obj_cache->size);
+
+ curr = next;
}
}

--
1.9.1

[Joonsoo Kim]

Okay. I sent fixed version.

Thanks.

[Andrey Ryabinin]

On 07/06/2016 03:52 AM, js1...@gmail.com wrote:
> From: Joonsoo Kim <iamjoon...@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.
>
> v5: rename some variable for better readability
> v4: fix cache size bug s/cache->size/obj_cache->size/
> v3: fix build warning
>
> Reviewed-by: Dmitry Vyukov <dvy...@google.com>
> Signed-off-by: Joonsoo Kim <iamjoon...@lge.com>

Fixes: 55834c59098d ("mm: kasan: initial memory quarantine implementation")
Acked-by: Andrey Ryabinin <arya...@virtuozzo.com>

[Alexander Potapenko]

On Wed, Jul 6, 2016 at 9:40 AM, Andrey Ryabinin <arya...@virtuozzo.com> wrote:
>
>
> On 07/06/2016 03:52 AM, js1...@gmail.com wrote:
>> From: Joonsoo Kim <iamjoon...@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.

Neat trick :)

>> Unfortunately, I got this bug sometime ago and lose oops message.
>> But, the bug looks trivial and no need to attach oops.
>>
>> v5: rename some variable for better readability
>> v4: fix cache size bug s/cache->size/obj_cache->size/
>> v3: fix build warning
>>
>> Reviewed-by: Dmitry Vyukov <dvy...@google.com>
>> Signed-off-by: Joonsoo Kim <iamjoon...@lge.com>
>
> Fixes: 55834c59098d ("mm: kasan: initial memory quarantine implementation")
> Acked-by: Andrey Ryabinin <arya...@virtuozzo.com>
>

Acked-by: Alexander Potapenko <gli...@google.com>


--
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Matthew Scott Sucherman, Paul Terence Manicle
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg