[PATCH] kasan: improve double-free detection

[PATCH] kasan: improve double-free detection

[Kuthonuzo Luruo]

Hi Alexander/Andrey/Dmitry,

For your consideration/review. Thanks!

Kuthonuzo Luruo 

Currently, KASAN may fail to detect concurrent deallocations of the same
object due to a race in kasan_slab_free(). This patch makes double-free
detection more reliable by atomically setting allocation state for object
to KASAN_STATE_QUARANTINE iff current state is KASAN_STATE_ALLOC.

Tested using a modified version of the 'slab_test' microbenchmark where
allocs occur on CPU 0; then all other CPUs concurrently attempt to free the
same object.

Signed-off-by: Kuthonuzo Luruo <kuthonuzo.luruo@hpe.com>
---
 mm/kasan/kasan.c |   32 ++++++++++++++++++--------------
 mm/kasan/kasan.h |    5 ++---
 2 files changed, 20 insertions(+), 17 deletions(-)

diff --git a/mm/kasan/kasan.c b/mm/kasan/kasan.c
index ef2e87b..4fc4e76 100644
--- a/mm/kasan/kasan.c
+++ b/mm/kasan/kasan.c
@@ -511,23 +511,28 @@ void kasan_poison_slab_free(struct kmem_cache *cache, void *object)
 bool kasan_slab_free(struct kmem_cache *cache, void *object)
 {
 #ifdef CONFIG_SLAB
+	struct kasan_alloc_meta *alloc_info;
+	struct kasan_free_meta *free_info;
+
 	/* RCU slabs could be legally used after free within the RCU period */
 	if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
 		return false;
 
-	if (likely(cache->flags & SLAB_KASAN)) {
-		struct kasan_alloc_meta *alloc_info =
-			get_alloc_info(cache, object);
-		struct kasan_free_meta *free_info =
-			get_free_info(cache, object);
-
-		switch (alloc_info->state) {
-		case KASAN_STATE_ALLOC:
-			alloc_info->state = KASAN_STATE_QUARANTINE;
-			quarantine_put(free_info, cache);
-			set_track(&free_info->track, GFP_NOWAIT);
-			kasan_poison_slab_free(cache, object);
-			return true;
+	if (unlikely(!(cache->flags & SLAB_KASAN)))
+		return false;
+
+	alloc_info = get_alloc_info(cache, object);
+
+	if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
+				KASAN_STATE_QUARANTINE) == KASAN_STATE_ALLOC) {
+		free_info = get_free_info(cache, object);
+		quarantine_put(free_info, cache);
+		set_track(&free_info->track, GFP_NOWAIT);
+		kasan_poison_slab_free(cache, object);
+		return true;
+	}
+
+	switch (alloc_info->state) {
 		case KASAN_STATE_QUARANTINE:
 		case KASAN_STATE_FREE:
 			pr_err("Double free");
@@ -535,7 +540,6 @@ bool kasan_slab_free(struct kmem_cache *cache, void *object)
 			break;
 		default:
 			break;
-		}
 	}
 	return false;
 #else
diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h
index 7da78a6..8c22a96 100644
--- a/mm/kasan/kasan.h
+++ b/mm/kasan/kasan.h
@@ -75,9 +75,8 @@ struct kasan_track {
 
 struct kasan_alloc_meta {
 	struct kasan_track track;
-	u32 state : 2;	/* enum kasan_state */
-	u32 alloc_size : 30;
-	u32 reserved;
+	u32 state;	/* enum kasan_state */
+	u32 alloc_size;
 };
 
 struct kasan_free_meta {
-- 
1.7.1

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Mon, May 2, 2016 at 11:49 AM, Kuthonuzo Luruo
<kuthonuzo.luruo@hpe.com> wrote:
> Hi Alexander/Andrey/Dmitry,
>
> For your consideration/review. Thanks!
>
> Kuthonuzo Luruo
>
> Currently, KASAN may fail to detect concurrent deallocations of the same
> object due to a race in kasan_slab_free(). This patch makes double-free
> detection more reliable by atomically setting allocation state for object
> to KASAN_STATE_QUARANTINE iff current state is KASAN_STATE_ALLOC.
>
> Tested using a modified version of the 'slab_test' microbenchmark where
> allocs occur on CPU 0; then all other CPUs concurrently attempt to free the
> same object.
>
> Signed-off-by: Kuthonuzo Luruo <kuthonuzo.luruo@hpe.com>
> ---
>  mm/kasan/kasan.c |   32 ++++++++++++++++++--------------
>  mm/kasan/kasan.h |    5 ++---
>  2 files changed, 20 insertions(+), 17 deletions(-)
>
> diff --git a/mm/kasan/kasan.c b/mm/kasan/kasan.c
> index ef2e87b..4fc4e76 100644
> --- a/mm/kasan/kasan.c
> +++ b/mm/kasan/kasan.c
> @@ -511,23 +511,28 @@ void kasan_poison_slab_free(struct kmem_cache *cache, void *object)
>  bool kasan_slab_free(struct kmem_cache *cache, void *object)
>  {
>  #ifdef CONFIG_SLAB
> +       struct kasan_alloc_meta *alloc_info;
> +       struct kasan_free_meta *free_info;
> +
>         /* RCU slabs could be legally used after free within the RCU period */
>         if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
>                 return false;
>
> -       if (likely(cache->flags & SLAB_KASAN)) {
> -               struct kasan_alloc_meta *alloc_info =
> -                       get_alloc_info(cache, object);
> -               struct kasan_free_meta *free_info =
> -                       get_free_info(cache, object);
> -
> -               switch (alloc_info->state) {
> -               case KASAN_STATE_ALLOC:
> -                       alloc_info->state = KASAN_STATE_QUARANTINE;
> -                       quarantine_put(free_info, cache);
> -                       set_track(&free_info->track, GFP_NOWAIT);
> -                       kasan_poison_slab_free(cache, object);
> -                       return true;
> +       if (unlikely(!(cache->flags & SLAB_KASAN)))
> +               return false;
> +
> +       alloc_info = get_alloc_info(cache, object);
> +
> +       if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
> +                               KASAN_STATE_QUARANTINE) == KASAN_STATE_ALLOC) {
> +               free_info = get_free_info(cache, object);
> +               quarantine_put(free_info, cache);
> +               set_track(&free_info->track, GFP_NOWAIT);
> +               kasan_poison_slab_free(cache, object);
> +               return true;
> +       }
> +
> +       switch (alloc_info->state) {
>                 case KASAN_STATE_QUARANTINE:
>                 case KASAN_STATE_FREE:
>                         pr_err("Double free");
> @@ -535,7 +540,6 @@ bool kasan_slab_free(struct kmem_cache *cache, void *object)
>                         break;
>                 default:
>                         break;
> -               }
>         }
>         return false;
>  #else
> diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h
> index 7da78a6..8c22a96 100644
> --- a/mm/kasan/kasan.h
> +++ b/mm/kasan/kasan.h
> @@ -75,9 +75,8 @@ struct kasan_track {
>
>  struct kasan_alloc_meta {
>         struct kasan_track track;
> -       u32 state : 2;  /* enum kasan_state */
> -       u32 alloc_size : 30;
> -       u32 reserved;
> +       u32 state;      /* enum kasan_state */
> +       u32 alloc_size;
>  };
>
>  struct kasan_free_meta {


Hi Kuthonuzo,

I agree that it's something we need to fix (user-space ASAN does
something along these lines). My only concern is increase of
kasan_alloc_meta size. It's unnecessary large already and we have a
plan to reduce both alloc and free into to 16 bytes. However, it can
make sense to land this and then reduce size of headers in a separate
patch using a CAS-loop on state. Alexander, what's the state of your
patches that reduce header size?

I think there is another race. If we have racing frees, one thread
sets state to KASAN_STATE_QUARANTINE but does not fill
free_info->track yet, at this point another thread does free and
reports double-free, but the track is wrong so we will print a bogus
stack. The same is true for all other state transitions (e.g.
use-after-free racing with the object being pushed out of the
quarantine).  We could introduce 2 helper functions like:

/* Sets status to KASAN_STATE_LOCKED if the current status is equal to
old_state, returns current state. Waits while current state equals
KASAN_STATE_LOCKED. */
u32 kasan_lock_if_state_equals(struct kasan_alloc_meta *meta, u32 old_state);

/* Changes state from KASAN_STATE_LOCKED to new_state */
void kasan_unlock_and_set_status(struct kasan_alloc_meta *meta, u32 new_state);

Then free can be expressed as:

if (kasan_lock_if_state_equals(meta, KASAN_STATE_ALLOC) == KASAN_STATE_ALLOC) {
               free_info = get_free_info(cache, object);
               quarantine_put(free_info, cache);
               set_track(&free_info->track, GFP_NOWAIT);
               kasan_poison_slab_free(cache, object);
               kasan_unlock_and_set_status(meta, KASAN_STATE_QUARANTINE);
               return true;
}

And on the reporting path we would need to lock the header, read all
state, unlock the header.

Does it make sense?

Please add the test as well. We need to start collecting tests for all
these tricky corner cases.

Thanks!

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

Hi Dmitry,

Thanks very much for your response/review.

> I agree that it's something we need to fix (user-space ASAN does
> something along these lines). My only concern is increase of
> kasan_alloc_meta size. It's unnecessary large already and we have a
> plan to reduce both alloc and free into to 16 bytes. However, it can
> make sense to land this and then reduce size of headers in a separate
> patch using a CAS-loop on state.

ok.

>  Alexander, what's the state of your
> patches that reduce header size?
> 
> I think there is another race. If we have racing frees, one thread
> sets state to KASAN_STATE_QUARANTINE but does not fill
> free_info->track yet, at this point another thread does free and
> reports double-free, but the track is wrong so we will print a bogus
> stack. The same is true for all other state transitions (e.g.
> use-after-free racing with the object being pushed out of the
> quarantine).

Yes, I've noticed this too. For the double-free, in my local tests, the error
reports from the bad frees get printed only after the successful "good"
free set the new track info. But then, I was using kasan_report() on the
error path to get sane reports from the multiple concurrent frees so that
may have "slowed" down the error paths enough until the good free was
done. Agreed, the window still exists for a stale (or missing) deallocation
stack in error report.

>  We could introduce 2 helper functions like:
> 
> /* Sets status to KASAN_STATE_LOCKED if the current status is equal to
> old_state, returns current state. Waits while current state equals
> KASAN_STATE_LOCKED. */
> u32 kasan_lock_if_state_equals(struct kasan_alloc_meta *meta, u32 old_state);
> 
> /* Changes state from KASAN_STATE_LOCKED to new_state */
> void kasan_unlock_and_set_status(struct kasan_alloc_meta *meta, u32
> new_state);
> 
> Then free can be expressed as:
> 
> if (kasan_lock_if_state_equals(meta, KASAN_STATE_ALLOC) ==
> KASAN_STATE_ALLOC) {
>                free_info = get_free_info(cache, object);
>                quarantine_put(free_info, cache);
>                set_track(&free_info->track, GFP_NOWAIT);
>                kasan_poison_slab_free(cache, object);
>                kasan_unlock_and_set_status(meta, KASAN_STATE_QUARANTINE);
>                return true;
> }
> 
> And on the reporting path we would need to lock the header, read all
> state, unlock the header.
> 
> Does it make sense?

It does, thanks! I'll try to hack up something, though right now, it's not entirely
clear to me how to achieve this without resorting to a global lock (which would
be unacceptable).

> 
> Please add the test as well. We need to start collecting tests for all
> these tricky corner cases.

Sure, a new test can be added for test_kasan.ko. Unlike the other tests, a
double-free would likely panic the system due to slab corruption. Would it still
be "KASANic" for kasan_slab_free() to return true after reporting double-free
attempt error so thread will not call into __cache_free()? How does ASAN
handle this?

Thanks,

Kuthonuzo

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Mon, May 2, 2016 at 1:30 PM, Luruo, Kuthonuzo
<kuthonuzo.luruo@hpe.com> wrote:
> Hi Dmitry,
>
> Thanks very much for your response/review.
>
>> I agree that it's something we need to fix (user-space ASAN does
>> something along these lines). My only concern is increase of
>> kasan_alloc_meta size. It's unnecessary large already and we have a
>> plan to reduce both alloc and free into to 16 bytes. However, it can
>> make sense to land this and then reduce size of headers in a separate
>> patch using a CAS-loop on state.
>
> ok.
>
>>  Alexander, what's the state of your
>> patches that reduce header size?
>>
>> I think there is another race. If we have racing frees, one thread
>> sets state to KASAN_STATE_QUARANTINE but does not fill
>> free_info->track yet, at this point another thread does free and
>> reports double-free, but the track is wrong so we will print a bogus
>> stack. The same is true for all other state transitions (e.g.
>> use-after-free racing with the object being pushed out of the
>> quarantine).
>
> Yes, I've noticed this too. For the double-free, in my local tests, the error
> reports from the bad frees get printed only after the successful "good"
> free set the new track info. But then, I was using kasan_report() on the
> error path to get sane reports from the multiple concurrent frees so that
> may have "slowed" down the error paths enough until the good free was
> done. Agreed, the window still exists for a stale (or missing) deallocation
> stack in error report.
>
>>  We could introduce 2 helper functions like:
>>
>> /* Sets status to KASAN_STATE_LOCKED if the current status is equal to
>> old_state, returns current state. Waits while current state equals
>> KASAN_STATE_LOCKED. */
>> u32 kasan_lock_if_state_equals(struct kasan_alloc_meta *meta, u32 old_state);
>>
>> /* Changes state from KASAN_STATE_LOCKED to new_state */
>> void kasan_unlock_and_set_status(struct kasan_alloc_meta *meta, u32
>> new_state);
>>
>> Then free can be expressed as:
>>
>> if (kasan_lock_if_state_equals(meta, KASAN_STATE_ALLOC) ==
>> KASAN_STATE_ALLOC) {
>>                free_info = get_free_info(cache, object);
>>                quarantine_put(free_info, cache);
>>                set_track(&free_info->track, GFP_NOWAIT);
>>                kasan_poison_slab_free(cache, object);
>>                kasan_unlock_and_set_status(meta, KASAN_STATE_QUARANTINE);
>>                return true;
>> }
>>
>> And on the reporting path we would need to lock the header, read all
>> state, unlock the header.
>>
>> Does it make sense?
>
> It does, thanks! I'll try to hack up something, though right now, it's not entirely
> clear to me how to achieve this without resorting to a global lock (which would
> be unacceptable).


We can use per-header lock by setting status to KASAN_STATE_LOCKED.  A
thread can CAS any status to KASAN_STATE_LOCKED which means that it
locked the header. If any thread tried to modify/read the status and
the status is KASAN_STATE_LOCKED, then the thread waits.


>> Please add the test as well. We need to start collecting tests for all
>> these tricky corner cases.
>
> Sure, a new test can be added for test_kasan.ko. Unlike the other tests, a
> double-free would likely panic the system due to slab corruption. Would it still
> be "KASANic" for kasan_slab_free() to return true after reporting double-free
> attempt error so thread will not call into __cache_free()? How does ASAN
> handle this?

Yes, sure, it is OK to return true from kasan_slab_free() in such case.
Use-space ASAN terminates the process after the first report. We've
decided that in kernel we better continue in best-effort manner. But
after the first report all bets are mostly off (leaking an object is
definitely OK).

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Mon, May 2, 2016 at 12:09 PM, Dmitry Vyukov <dvyukov@google.com> wrote:
> On Mon, May 2, 2016 at 11:49 AM, Kuthonuzo Luruo
> <kuthonuzo.luruo@hpe.com> wrote:
>> Hi Alexander/Andrey/Dmitry,
>>
>> For your consideration/review. Thanks!
>>
>> Kuthonuzo Luruo
>>
>> Currently, KASAN may fail to detect concurrent deallocations of the same
>> object due to a race in kasan_slab_free(). This patch makes double-free
>> detection more reliable by atomically setting allocation state for object
>> to KASAN_STATE_QUARANTINE iff current state is KASAN_STATE_ALLOC.
>>
>> Tested using a modified version of the 'slab_test' microbenchmark where
>> allocs occur on CPU 0; then all other CPUs concurrently attempt to free the
>> same object.
>>
>> Signed-off-by: Kuthonuzo Luruo <kuthonuzo.luruo@hpe.com>
>> ---
>>  mm/kasan/kasan.c |   32 ++++++++++++++++++--------------
>>  mm/kasan/kasan.h |    5 ++---
>>  2 files changed, 20 insertions(+), 17 deletions(-)
>>
>> diff --git a/mm/kasan/kasan.c b/mm/kasan/kasan.c
>> index ef2e87b..4fc4e76 100644
>> --- a/mm/kasan/kasan.c
>> +++ b/mm/kasan/kasan.c
>> @@ -511,23 +511,28 @@ void kasan_poison_slab_free(struct kmem_cache *cache, void *object)
>>  bool kasan_slab_free(struct kmem_cache *cache, void *object)
>>  {
>>  #ifdef CONFIG_SLAB
>> +       struct kasan_alloc_meta *alloc_info;
>> +       struct kasan_free_meta *free_info;
>> +
>>         /* RCU slabs could be legally used after free within the RCU period */
>>         if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
>>                 return false;
>>
>> -       if (likely(cache->flags & SLAB_KASAN)) {
>> -               struct kasan_alloc_meta *alloc_info =
>> -                       get_alloc_info(cache, object);
>> -               struct kasan_free_meta *free_info =
>> -                       get_free_info(cache, object);
>> -
>> -               switch (alloc_info->state) {
>> -               case KASAN_STATE_ALLOC:
>> -                       alloc_info->state = KASAN_STATE_QUARANTINE;
>> -                       quarantine_put(free_info, cache);
>> -                       set_track(&free_info->track, GFP_NOWAIT);
>> -                       kasan_poison_slab_free(cache, object);
>> -                       return true;
>> +       if (unlikely(!(cache->flags & SLAB_KASAN)))
>> +               return false;
>> +
>> +       alloc_info = get_alloc_info(cache, object);
>> +
>> +       if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
>> +                               KASAN_STATE_QUARANTINE) == KASAN_STATE_ALLOC) {
>> +               free_info = get_free_info(cache, object);
>> +               quarantine_put(free_info, cache);
>> +               set_track(&free_info->track, GFP_NOWAIT);
>> +               kasan_poison_slab_free(cache, object);
>> +               return true;
>> +       }
>> +
>> +       switch (alloc_info->state) {
>>                 case KASAN_STATE_QUARANTINE:
>>                 case KASAN_STATE_FREE:
>>                         pr_err("Double free");
>> @@ -535,7 +540,6 @@ bool kasan_slab_free(struct kmem_cache *cache, void *object)
>>                         break;
>>                 default:
>>                         break;
>> -               }
>>         }
>>         return false;
>>  #else
>> diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h
>> index 7da78a6..8c22a96 100644
>> --- a/mm/kasan/kasan.h
>> +++ b/mm/kasan/kasan.h
>> @@ -75,9 +75,8 @@ struct kasan_track {
>>
>>  struct kasan_alloc_meta {
>>         struct kasan_track track;
>> -       u32 state : 2;  /* enum kasan_state */
>> -       u32 alloc_size : 30;
>> -       u32 reserved;
>> +       u32 state;      /* enum kasan_state */
>> +       u32 alloc_size;
>>  };
>>
>>  struct kasan_free_meta {
>
>
> Hi Kuthonuzo,
>
> I agree that it's something we need to fix (user-space ASAN does
> something along these lines). My only concern is increase of
> kasan_alloc_meta size. It's unnecessary large already and we have a
> plan to reduce both alloc and free into to 16 bytes. However, it can
> make sense to land this and then reduce size of headers in a separate
> patch using a CAS-loop on state. Alexander, what's the state of your
> patches that reduce header size?


I missed that Alexander already landed patches that reduce header size
to 16 bytes.
It is not OK to increase them again. Please leave state as bitfield
and update it with CAS (if we introduce helper functions for state
manipulation, they will hide the CAS loop, which is nice).


> I think there is another race. If we have racing frees, one thread
> sets state to KASAN_STATE_QUARANTINE but does not fill
> free_info->track yet, at this point another thread does free and
> reports double-free, but the track is wrong so we will print a bogus
> stack. The same is true for all other state transitions (e.g.
> use-after-free racing with the object being pushed out of the
> quarantine).  We could introduce 2 helper functions like:
>
> /* Sets status to KASAN_STATE_LOCKED if the current status is equal to
> old_state, returns current state. Waits while current state equals
> KASAN_STATE_LOCKED. */
> u32 kasan_lock_if_state_equals(struct kasan_alloc_meta *meta, u32 old_state);
>
> /* Changes state from KASAN_STATE_LOCKED to new_state */
> void kasan_unlock_and_set_status(struct kasan_alloc_meta *meta, u32 new_state);
>
> Then free can be expressed as:
>
> if (kasan_lock_if_state_equals(meta, KASAN_STATE_ALLOC) == KASAN_STATE_ALLOC) {
>                free_info = get_free_info(cache, object);
>                quarantine_put(free_info, cache);
>                set_track(&free_info->track, GFP_NOWAIT);
>                kasan_poison_slab_free(cache, object);
>                kasan_unlock_and_set_status(meta, KASAN_STATE_QUARANTINE);
>                return true;
> }
>
> And on the reporting path we would need to lock the header, read all
> state, unlock the header.
>
> Does it make sense?
>
> Please add the test as well. We need to start collecting tests for all
> these tricky corner cases.
>
> Thanks!

Re: [PATCH] kasan: improve double-free detection

[Alexander Potapenko]

On Mon, May 2, 2016 at 1:41 PM, Dmitry Vyukov <dvyukov@google.com> wrote:
> On Mon, May 2, 2016 at 12:09 PM, Dmitry Vyukov <dvyukov@google.com> wrote:
>> On Mon, May 2, 2016 at 11:49 AM, Kuthonuzo Luruo
>> <kuthonuzo.luruo@hpe.com> wrote:
>>> Hi Alexander/Andrey/Dmitry,
>>>
>>> For your consideration/review. Thanks!
>>>
>>> Kuthonuzo Luruo
>>>
>>> Currently, KASAN may fail to detect concurrent deallocations of the same
>>> object due to a race in kasan_slab_free(). This patch makes double-free
>>> detection more reliable by atomically setting allocation state for object
>>> to KASAN_STATE_QUARANTINE iff current state is KASAN_STATE_ALLOC.
>>>
>>> Tested using a modified version of the 'slab_test' microbenchmark where
>>> allocs occur on CPU 0; then all other CPUs concurrently attempt to free the
>>> same object.
>>>
>>> Signed-off-by: Kuthonuzo Luruo <kuthonuzo.luruo@hpe.com>
>>> ---
>>>  mm/kasan/kasan.c |   32 ++++++++++++++++++--------------
>>>  mm/kasan/kasan.h |    5 ++---
>>>  2 files changed, 20 insertions(+), 17 deletions(-)
>>>
>>> diff --git a/mm/kasan/kasan.c b/mm/kasan/kasan.c
>>> index ef2e87b..4fc4e76 100644
>>> --- a/mm/kasan/kasan.c
>>> +++ b/mm/kasan/kasan.c
>>> @@ -511,23 +511,28 @@ void kasan_poison_slab_free(struct kmem_cache *cache, void *object)
>>>  bool kasan_slab_free(struct kmem_cache *cache, void *object)
>>>  {
>>>  #ifdef CONFIG_SLAB
>>> +       struct kasan_alloc_meta *alloc_info;
>>> +       struct kasan_free_meta *free_info;
>>> +
>>>         /* RCU slabs could be legally used after free within the RCU period */
>>>         if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
>>>                 return false;
>>>
>>> -       if (likely(cache->flags & SLAB_KASAN)) {
>>> -               struct kasan_alloc_meta *alloc_info =
>>> -                       get_alloc_info(cache, object);
>>> -               struct kasan_free_meta *free_info =
>>> -                       get_free_info(cache, object);
>>> -
>>> -               switch (alloc_info->state) {
>>> -               case KASAN_STATE_ALLOC:
>>> -                       alloc_info->state = KASAN_STATE_QUARANTINE;
>>> -                       quarantine_put(free_info, cache);
>>> -                       set_track(&free_info->track, GFP_NOWAIT);
>>> -                       kasan_poison_slab_free(cache, object);
>>> -                       return true;
>>> +       if (unlikely(!(cache->flags & SLAB_KASAN)))
>>> +               return false;
>>> +
>>> +       alloc_info = get_alloc_info(cache, object);
>>> +
>>> +       if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
>>> +                               KASAN_STATE_QUARANTINE) == KASAN_STATE_ALLOC) {
>>> +               free_info = get_free_info(cache, object);
>>> +               quarantine_put(free_info, cache);
>>> +               set_track(&free_info->track, GFP_NOWAIT);
>>> +               kasan_poison_slab_free(cache, object);
>>> +               return true;
>>> +       }
>>> +
>>> +       switch (alloc_info->state) {
>>>                 case KASAN_STATE_QUARANTINE:
>>>                 case KASAN_STATE_FREE:
>>>                         pr_err("Double free");
>>> @@ -535,7 +540,6 @@ bool kasan_slab_free(struct kmem_cache *cache, void *object)
>>>                         break;
>>>                 default:
>>>                         break;
>>> -               }
>>>         }
>>>         return false;
>>>  #else
>>> diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h
>>> index 7da78a6..8c22a96 100644
>>> --- a/mm/kasan/kasan.h
>>> +++ b/mm/kasan/kasan.h
>>> @@ -75,9 +75,8 @@ struct kasan_track {
>>>
>>>  struct kasan_alloc_meta {
>>>         struct kasan_track track;
>>> -       u32 state : 2;  /* enum kasan_state */
>>> -       u32 alloc_size : 30;
>>> -       u32 reserved;
>>> +       u32 state;      /* enum kasan_state */
>>> +       u32 alloc_size;
>>>  };
>>>
>>>  struct kasan_free_meta {
>>
>>
>> Hi Kuthonuzo,
>>
>> I agree that it's something we need to fix (user-space ASAN does
>> something along these lines). My only concern is increase of
>> kasan_alloc_meta size. It's unnecessary large already and we have a
>> plan to reduce both alloc and free into to 16 bytes. However, it can
>> make sense to land this and then reduce size of headers in a separate
>> patch using a CAS-loop on state. Alexander, what's the state of your
>> patches that reduce header size?
>
>
> I missed that Alexander already landed patches that reduce header size
> to 16 bytes.
> It is not OK to increase them again. Please leave state as bitfield
> and update it with CAS (if we introduce helper functions for state
> manipulation, they will hide the CAS loop, which is nice).
Note that in this case you'll probably need to update alloc_size with
CAS loop as well.

>
>> I think there is another race. If we have racing frees, one thread
>> sets state to KASAN_STATE_QUARANTINE but does not fill
>> free_info->track yet, at this point another thread does free and
>> reports double-free, but the track is wrong so we will print a bogus
>> stack. The same is true for all other state transitions (e.g.
>> use-after-free racing with the object being pushed out of the
>> quarantine).  We could introduce 2 helper functions like:
>>
>> /* Sets status to KASAN_STATE_LOCKED if the current status is equal to
>> old_state, returns current state. Waits while current state equals
>> KASAN_STATE_LOCKED. */
>> u32 kasan_lock_if_state_equals(struct kasan_alloc_meta *meta, u32 old_state);
>>
>> /* Changes state from KASAN_STATE_LOCKED to new_state */
>> void kasan_unlock_and_set_status(struct kasan_alloc_meta *meta, u32 new_state);
>>
>> Then free can be expressed as:
>>
>> if (kasan_lock_if_state_equals(meta, KASAN_STATE_ALLOC) == KASAN_STATE_ALLOC) {
>>                free_info = get_free_info(cache, object);
>>                quarantine_put(free_info, cache);
>>                set_track(&free_info->track, GFP_NOWAIT);
>>                kasan_poison_slab_free(cache, object);
>>                kasan_unlock_and_set_status(meta, KASAN_STATE_QUARANTINE);
>>                return true;
>> }
>>
>> And on the reporting path we would need to lock the header, read all
>> state, unlock the header.
>>
>> Does it make sense?
>>
>> Please add the test as well. We need to start collecting tests for all
>> these tricky corner cases.
>>
>> Thanks!



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

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> I missed that Alexander already landed patches that reduce header size
> to 16 bytes.
> It is not OK to increase them again. Please leave state as bitfield
> and update it with CAS (if we introduce helper functions for state
> manipulation, they will hide the CAS loop, which is nice).
> 

Available CAS primitives/compiler do not support CAS with bitfield. I propose
to change kasan_alloc_meta to:

struct kasan_alloc_meta {
        struct kasan_track track;
        u16 size_delta;         /* object_size - alloc size */
        u8 state;                    /* enum kasan_state */
        u8 reserved1;
        u32 reserved2;
}

This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1 does
not increase overall alloc meta object size). "Alloc size", where needed, is
easily calculated as a delta from cache->object_size.

Kuthonuzo

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> >
> > I missed that Alexander already landed patches that reduce header size
> > to 16 bytes.
> > It is not OK to increase them again. Please leave state as bitfield
> > and update it with CAS (if we introduce helper functions for state
> > manipulation, they will hide the CAS loop, which is nice).
> Note that in this case you'll probably need to update alloc_size with
> CAS loop as well.

Not sure I understood this; Anyway, revised kasan_alloc_meta in upcoming patch
should make this unnecessary.

Thanks,

Kuthonuzo

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> 
> We can use per-header lock by setting status to KASAN_STATE_LOCKED.  A
> thread can CAS any status to KASAN_STATE_LOCKED which means that it
> locked the header. If any thread tried to modify/read the status and
> the status is KASAN_STATE_LOCKED, then the thread waits.

Thanks, Dmitry. I've successfully tested with the concurrent free slab_test test
(alloc on cpu 0; then concurrent frees on all other cpus on a 12-vcpu KVM) using:

static inline bool kasan_alloc_state_lock(struct kasan_alloc_meta *alloc_info)
{
        if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
                                KASAN_STATE_LOCKED) == KASAN_STATE_ALLOC)
                return true;
        return false;
}

static inline void kasan_alloc_state_unlock_wait(struct kasan_alloc_meta
                *alloc_info)
{
        while (alloc_info->state == KASAN_STATE_LOCKED)
                cpu_relax();
}

Race "winner" sets state to quarantine as the last step:

        if (kasan_alloc_state_lock(alloc_info)) {
                free_info = get_free_info(cache, object);
                quarantine_put(free_info, cache);
                set_track(&free_info->track, GFP_NOWAIT);
                kasan_poison_slab_free(cache, object);
                alloc_info->state = KASAN_STATE_QUARANTINE;
                return true;
        } else
                kasan_alloc_state_unlock_wait(alloc_info);

Now, I'm not sure whether on current KASAN-supported archs, state byte load in
the busy-wait loop is atomic wrt the KASAN_STATE_QUARANTINE byte store.
Would you advise using CAS primitives for load/store here too?

> >
> > Sure, a new test can be added for test_kasan.ko. Unlike the other tests, a
> > double-free would likely panic the system due to slab corruption. Would it still
> > be "KASANic" for kasan_slab_free() to return true after reporting double-free
> > attempt error so thread will not call into __cache_free()? How does ASAN
> > handle this?
> 
> Yes, sure, it is OK to return true from kasan_slab_free() in such case.
> Use-space ASAN terminates the process after the first report. We've
> decided that in kernel we better continue in best-effort manner. But
> after the first report all bets are mostly off (leaking an object is
> definitely OK).

sounds good; I'm also "promoting" double-free pr_err() to kasan_report().

Kuthonuzo

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Tue, May 3, 2016 at 9:53 AM, Luruo, Kuthonuzo
<kuthonuzo.luruo@hpe.com> wrote:
>> I missed that Alexander already landed patches that reduce header size
>> to 16 bytes.
>> It is not OK to increase them again. Please leave state as bitfield
>> and update it with CAS (if we introduce helper functions for state
>> manipulation, they will hide the CAS loop, which is nice).
>>
>
> Available CAS primitives/compiler do not support CAS with bitfield. I propose
> to change kasan_alloc_meta to:
>
> struct kasan_alloc_meta {
>         struct kasan_track track;
>         u16 size_delta;         /* object_size - alloc size */
>         u8 state;                    /* enum kasan_state */
>         u8 reserved1;
>         u32 reserved2;
> }
>
> This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1 does
> not increase overall alloc meta object size). "Alloc size", where needed, is
> easily calculated as a delta from cache->object_size.


What is the maximum size that slab can allocate?
I remember seeing slabs as large as 4MB some time ago (or did I
confuse it with something else?). If there are such large objects,
that 2 bytes won't be able to hold even delta.
However, now on my desktop I don't see slabs larger than 16KB in /proc/slabinfo.

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Tue, May 3, 2016 at 11:24 AM, Luruo, Kuthonuzo
<kuthonuzo.luruo@hpe.com> wrote:
>>
>> We can use per-header lock by setting status to KASAN_STATE_LOCKED.  A
>> thread can CAS any status to KASAN_STATE_LOCKED which means that it
>> locked the header. If any thread tried to modify/read the status and
>> the status is KASAN_STATE_LOCKED, then the thread waits.
>
> Thanks, Dmitry. I've successfully tested with the concurrent free slab_test test
> (alloc on cpu 0; then concurrent frees on all other cpus on a 12-vcpu KVM) using:
>
> static inline bool kasan_alloc_state_lock(struct kasan_alloc_meta *alloc_info)
> {
>         if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
>                                 KASAN_STATE_LOCKED) == KASAN_STATE_ALLOC)
>                 return true;
>         return false;
> }
>
> static inline void kasan_alloc_state_unlock_wait(struct kasan_alloc_meta
>                 *alloc_info)
> {
>         while (alloc_info->state == KASAN_STATE_LOCKED)
>                 cpu_relax();
> }
>
> Race "winner" sets state to quarantine as the last step:
>
>         if (kasan_alloc_state_lock(alloc_info)) {
>                 free_info = get_free_info(cache, object);
>                 quarantine_put(free_info, cache);
>                 set_track(&free_info->track, GFP_NOWAIT);
>                 kasan_poison_slab_free(cache, object);
>                 alloc_info->state = KASAN_STATE_QUARANTINE;
>                 return true;
>         } else
>                 kasan_alloc_state_unlock_wait(alloc_info);
>
> Now, I'm not sure whether on current KASAN-supported archs, state byte load in
> the busy-wait loop is atomic wrt the KASAN_STATE_QUARANTINE byte store.
> Would you advise using CAS primitives for load/store here too?

Store to state needs to use smp_store_release function, otherwise
stores to free_info->track can sink below the store to state.
Similarly, loads of state in kasan_alloc_state_unlock_wait need to use
smp_store_acquire.

A function similar to kasan_alloc_state_lock will also be needed for
KASAN_STATE_QUARANTINE -> KASAN_STATE_ALLOC state transition (when we
reuse the object). If a thread tried to report use-after-free when
another thread pushes the object out of quarantine and overwrites
alloc_info->track, the thread will print a bogus stack.

kasan_alloc_state_unlock_wait is not enough to prevent the races.
Consider that a thread executes kasan_alloc_state_unlock_wait and
proceeds to reporting, at this point another thread pushes the object
to quarantine or out of the quarantine and overwrites tracks. The
first thread will read inconsistent data from the header. Any thread
that reads/writes header needs to (1) wait while status is
KASAN_STATE_LOCKED, (2) CAS status to KASAN_STATE_LOCKED, (3)
read/write header, (4) restore/update status and effectively unlock
the header.
Alternatively, we can introduce LOCKED bit to header. Then it will be
simpler for readers to set/unset the bit.

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> >> I missed that Alexander already landed patches that reduce header size
> >> to 16 bytes.
> >> It is not OK to increase them again. Please leave state as bitfield
> >> and update it with CAS (if we introduce helper functions for state
> >> manipulation, they will hide the CAS loop, which is nice).
> >>
> >
> > Available CAS primitives/compiler do not support CAS with bitfield. I propose
> > to change kasan_alloc_meta to:
> >
> > struct kasan_alloc_meta {
> >         struct kasan_track track;
> >         u16 size_delta;         /* object_size - alloc size */
> >         u8 state;                    /* enum kasan_state */
> >         u8 reserved1;
> >         u32 reserved2;
> > }
> >
> > This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1 does
> > not increase overall alloc meta object size). "Alloc size", where needed, is
> > easily calculated as a delta from cache->object_size.
> 
> 
> What is the maximum size that slab can allocate?
> I remember seeing slabs as large as 4MB some time ago (or did I
> confuse it with something else?). If there are such large objects,
> that 2 bytes won't be able to hold even delta.
> However, now on my desktop I don't see slabs larger than 16KB in
> /proc/slabinfo.

max size for SLAB's slab is 32MB; default is 4MB. I must have gotten confused by
SLUB's 8KB limit. Anyway, new kasan_alloc_meta in patch V2:

struct kasan_alloc_meta {
        struct kasan_track track;
        union {
                u8 lock;
                struct {
                        u32 dummy : 8;
                        u32 size_delta : 24;    /* object_size - alloc size */
                };
        };
        u32 state : 2;                          /* enum kasan_alloc_state */
        u32 unused : 30;
};

This uses 2 more bits than current, but given the constraints I think this is
close to optimal.

Kuthonuzo

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Wed, May 4, 2016 at 10:13 PM, Luruo, Kuthonuzo
<kuthonuzo.luruo@hpe.com> wrote:
>> >> I missed that Alexander already landed patches that reduce header size
>> >> to 16 bytes.
>> >> It is not OK to increase them again. Please leave state as bitfield
>> >> and update it with CAS (if we introduce helper functions for state
>> >> manipulation, they will hide the CAS loop, which is nice).
>> >>
>> >
>> > Available CAS primitives/compiler do not support CAS with bitfield. I propose
>> > to change kasan_alloc_meta to:
>> >
>> > struct kasan_alloc_meta {
>> >         struct kasan_track track;
>> >         u16 size_delta;         /* object_size - alloc size */
>> >         u8 state;                    /* enum kasan_state */
>> >         u8 reserved1;
>> >         u32 reserved2;
>> > }
>> >
>> > This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1 does
>> > not increase overall alloc meta object size). "Alloc size", where needed, is
>> > easily calculated as a delta from cache->object_size.
>>
>>
>> What is the maximum size that slab can allocate?
>> I remember seeing slabs as large as 4MB some time ago (or did I
>> confuse it with something else?). If there are such large objects,
>> that 2 bytes won't be able to hold even delta.
>> However, now on my desktop I don't see slabs larger than 16KB in
>> /proc/slabinfo.
>
> max size for SLAB's slab is 32MB; default is 4MB. I must have gotten confused by
> SLUB's 8KB limit. Anyway, new kasan_alloc_meta in patch V2:
>
> struct kasan_alloc_meta {
>         struct kasan_track track;
>         union {
>                 u8 lock;
>                 struct {
>                         u32 dummy : 8;
>                         u32 size_delta : 24;    /* object_size - alloc size */
>                 };
>         };
>         u32 state : 2;                          /* enum kasan_alloc_state */
>         u32 unused : 30;
> };
>
> This uses 2 more bits than current, but given the constraints I think this is
> close to optimal.


We plan to use the unused part for another depot_stack_handle_t (u32)
to memorize stack of the last call_rcu on the object (this will
greatly simplify debugging of use-after-free for objects freed by
rcu). So we need that unused part.

I would would simply put all these fields into a single u32:

struct kasan_alloc_meta {
        struct kasan_track track;
        u32 status;  // contains lock, state and size
        u32 unused;  // reserved for call_rcu stack handle
};

And then separately a helper type to pack/unpack status:

union kasan_alloc_status {
        u32 raw;
        struct {
                   u32 lock : 1;
                   u32 state : 2;
                   u32 unused : 5;
                   u32 size : 24;
        };
};


Then, when we need to read/update the header we do something like:

kasan_alloc_status status, new_status;

for (;;) {
    status.raw = READ_ONCE(header->status);
    // read status, form new_status, for example:
    if (status.lock)
          continue;
    new_status.raw = status.raw;
    new_status.lock = 1;
    if (cas(&header->status, status.raw, new_status.raw))
             break;
}


This will probably make state manipulation functions few lines longer,
but since there are like 3 such functions I don't afraid that. And we
still can use bitfield magic to extract fields and leave whole 5 bits
unused bits for future.

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> >> >> I missed that Alexander already landed patches that reduce header size
> >> >> to 16 bytes.
> >> >> It is not OK to increase them again. Please leave state as bitfield
> >> >> and update it with CAS (if we introduce helper functions for state
> >> >> manipulation, they will hide the CAS loop, which is nice).
> >> >>
> >> >
> >> > Available CAS primitives/compiler do not support CAS with bitfield. I
> propose
> >> > to change kasan_alloc_meta to:
> >> >
> >> > struct kasan_alloc_meta {
> >> >         struct kasan_track track;
> >> >         u16 size_delta;         /* object_size - alloc size */
> >> >         u8 state;                    /* enum kasan_state */
> >> >         u8 reserved1;
> >> >         u32 reserved2;
> >> > }
> >> >
> >> > This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1
> does
> >> > not increase overall alloc meta object size). "Alloc size", where needed, is
> >> > easily calculated as a delta from cache->object_size.
> >>
> >>
> >> What is the maximum size that slab can allocate?
> >> I remember seeing slabs as large as 4MB some time ago (or did I
> >> confuse it with something else?). If there are such large objects,
> >> that 2 bytes won't be able to hold even delta.
> >> However, now on my desktop I don't see slabs larger than 16KB in
> >> /proc/slabinfo.
> >
> > max size for SLAB's slab is 32MB; default is 4MB. I must have gotten confused
> by
> > SLUB's 8KB limit. Anyway, new kasan_alloc_meta in patch V2:
> >
> > struct kasan_alloc_meta {
> >         struct kasan_track track;
> >         union {
> >                 u8 lock;
> >                 struct {
> >                         u32 dummy : 8;
> >                         u32 size_delta : 24;    /* object_size - alloc size */
> >                 };
> >         };
> >         u32 state : 2;                          /* enum kasan_alloc_state */
> >         u32 unused : 30;
> > };
> >
> > This uses 2 more bits than current, but given the constraints I think this is
> > close to optimal.
> 
> 
> We plan to use the unused part for another depot_stack_handle_t (u32)
> to memorize stack of the last call_rcu on the object (this will
> greatly simplify debugging of use-after-free for objects freed by
> rcu). So we need that unused part.
> 
> I would would simply put all these fields into a single u32:
> 
> struct kasan_alloc_meta {
>         struct kasan_track track;
>         u32 status;  // contains lock, state and size
>         u32 unused;  // reserved for call_rcu stack handle
> };
> 
> And then separately a helper type to pack/unpack status:
> 
> union kasan_alloc_status {
>         u32 raw;
>         struct {
>                    u32 lock : 1;
>                    u32 state : 2;
>                    u32 unused : 5;
>                    u32 size : 24;
>         };
> };
> 
> 
> Then, when we need to read/update the header we do something like:
> 
> kasan_alloc_status status, new_status;
> 
> for (;;) {
>     status.raw = READ_ONCE(header->status);
>     // read status, form new_status, for example:
>     if (status.lock)
>           continue;
>     new_status.raw = status.raw;
>     new_status.lock = 1;
>     if (cas(&header->status, status.raw, new_status.raw))
>              break;
> }
> 
> 
> This will probably make state manipulation functions few lines longer,
> but since there are like 3 such functions I don't afraid that. And we
> still can use bitfield magic to extract fields and leave whole 5 bits
> unused bits for future.

The difficulty is that the lock managed by CAS needs 1 byte, mininum; TAS bit
is even 'worse': address must be that of an unsigned long.

Might it be possible for you to employ the 'kasan_free_meta' header for your
RCU stack handle instead since KASAN does not currently store state for RCU
slabs on free?

Kuthonuzo

Re: [PATCH] kasan: improve double-free detection

[Dmitry Vyukov]

On Thu, May 5, 2016 at 8:23 AM, Luruo, Kuthonuzo
<kuthonuzo.luruo@hpe.com> wrote:
>> >> >> I missed that Alexander already landed patches that reduce header size
>> >> >> to 16 bytes.
>> >> >> It is not OK to increase them again. Please leave state as bitfield
>> >> >> and update it with CAS (if we introduce helper functions for state
>> >> >> manipulation, they will hide the CAS loop, which is nice).
>> >> >>
>> >> >
>> >> > Available CAS primitives/compiler do not support CAS with bitfield. I
>> propose
>> >> > to change kasan_alloc_meta to:
>> >> >
>> >> > struct kasan_alloc_meta {
>> >> >         struct kasan_track track;
>> >> >         u16 size_delta;         /* object_size - alloc size */
>> >> >         u8 state;                    /* enum kasan_state */
>> >> >         u8 reserved1;
>> >> >         u32 reserved2;
>> >> > }
>> >> >
>> >> > This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1
>> does
>> >> > not increase overall alloc meta object size). "Alloc size", where needed, is
>> >> > easily calculated as a delta from cache->object_size.
>> >>
>> >>
>> >> What is the maximum size that slab can allocate?
>> >> I remember seeing slabs as large as 4MB some time ago (or did I
>> >> confuse it with something else?). If there are such large objects,
>> >> that 2 bytes won't be able to hold even delta.
>> >> However, now on my desktop I don't see slabs larger than 16KB in
>> >> /proc/slabinfo.
>> >
>> > max size for SLAB's slab is 32MB; default is 4MB. I must have gotten confused
>> by
>> > SLUB's 8KB limit. Anyway, new kasan_alloc_meta in patch V2:
>> >
>> > struct kasan_alloc_meta {
>> >         struct kasan_track track;
>> >         union {
>> >                 u8 lock;
>> >                 struct {
>> >                         u32 dummy : 8;
>> >                         u32 size_delta : 24;    /* object_size - alloc size */
>> >                 };
>> >         };
>> >         u32 state : 2;                          /* enum kasan_alloc_state */
>> >         u32 unused : 30;
>> > };
>> >
>> > This uses 2 more bits than current, but given the constraints I think this is
>> > close to optimal.
>>
>>
>> We plan to use the unused part for another depot_stack_handle_t (u32)
>> to memorize stack of the last call_rcu on the object (this will
>> greatly simplify debugging of use-after-free for objects freed by
>> rcu). So we need that unused part.
>>
>> I would would simply put all these fields into a single u32:
>>
>> struct kasan_alloc_meta {
>>         struct kasan_track track;
>>         u32 status;  // contains lock, state and size
>>         u32 unused;  // reserved for call_rcu stack handle
>> };
>>
>> And then separately a helper type to pack/unpack status:
>>
>> union kasan_alloc_status {
>>         u32 raw;
>>         struct {
>>                    u32 lock : 1;
>>                    u32 state : 2;
>>                    u32 unused : 5;
>>                    u32 size : 24;
>>         };
>> };
>>
>>
>> Then, when we need to read/update the header we do something like:
>>
>> kasan_alloc_status status, new_status;
>>
>> for (;;) {
>>     status.raw = READ_ONCE(header->status);
>>     // read status, form new_status, for example:
>>     if (status.lock)
>>           continue;
>>     new_status.raw = status.raw;
>>     new_status.lock = 1;
>>     if (cas(&header->status, status.raw, new_status.raw))
>>              break;
>> }
>>
>>
>> This will probably make state manipulation functions few lines longer,
>> but since there are like 3 such functions I don't afraid that. And we
>> still can use bitfield magic to extract fields and leave whole 5 bits
>> unused bits for future.
>
> The difficulty is that the lock managed by CAS needs 1 byte, mininum; TAS bit
> is even 'worse': address must be that of an unsigned long.

cmpxchg function can operate on bytes, words, double words and quad words:
http://lxr.free-electrons.com/source/arch/x86/include/asm/cmpxchg.h#L146


> Might it be possible for you to employ the 'kasan_free_meta' header for your
> RCU stack handle instead since KASAN does not currently store state for RCU
> slabs on free?

Free meta is overlapped with user object. The object is not freed yet
when call_rcu is invoked, so free meta cannot be used yet (user still
holds own data there). Free meta can only be used after kfree is
invoked on the object.

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> >> >> >> I missed that Alexander already landed patches that reduce header size
> >> >> >> to 16 bytes.
> >> >> >> It is not OK to increase them again. Please leave state as bitfield
> >> >> >> and update it with CAS (if we introduce helper functions for state
> >> >> >> manipulation, they will hide the CAS loop, which is nice).
> >> >> >>
> >> >> >
> >> >> > Available CAS primitives/compiler do not support CAS with bitfield. I
> >> propose
> >> >> > to change kasan_alloc_meta to:
> >> >> >
> >> >> > struct kasan_alloc_meta {
> >> >> >         struct kasan_track track;
> >> >> >         u16 size_delta;         /* object_size - alloc size */
> >> >> >         u8 state;                    /* enum kasan_state */
> >> >> >         u8 reserved1;
> >> >> >         u32 reserved2;
> >> >> > }
> >> >> >
> >> >> > This shrinks _used_ meta object by 1 byte wrt the original. (btw, patch v1
> >> does
> >> >> > not increase overall alloc meta object size). "Alloc size", where needed,
> is
> >> >> > easily calculated as a delta from cache->object_size.
> >> >>
> >> >>
> >> >> What is the maximum size that slab can allocate?
> >> >> I remember seeing slabs as large as 4MB some time ago (or did I
> >> >> confuse it with something else?). If there are such large objects,
> >> >> that 2 bytes won't be able to hold even delta.
> >> >> However, now on my desktop I don't see slabs larger than 16KB in
> >> >> /proc/slabinfo.
> >> >
> >> > max size for SLAB's slab is 32MB; default is 4MB. I must have gotten
> confused
> >> by
> >> > SLUB's 8KB limit. Anyway, new kasan_alloc_meta in patch V2:
> >> >
> >> > struct kasan_alloc_meta {
> >> >         struct kasan_track track;
> >> >         union {
> >> >                 u8 lock;
> >> >                 struct {
> >> >                         u32 dummy : 8;
> >> >                         u32 size_delta : 24;    /* object_size - alloc size */
> >> >                 };
> >> >         };
> >> >         u32 state : 2;                          /* enum kasan_alloc_state */
> >> >         u32 unused : 30;
> >> > };
> >> >
> >> > This uses 2 more bits than current, but given the constraints I think this is
> >> > close to optimal.
> >>
> >>
> >> We plan to use the unused part for another depot_stack_handle_t (u32)
> >> to memorize stack of the last call_rcu on the object (this will
> >> greatly simplify debugging of use-after-free for objects freed by
> >> rcu). So we need that unused part.
> >>
> >> I would would simply put all these fields into a single u32:
> >>
> >> struct kasan_alloc_meta {
> >>         struct kasan_track track;
> >>         u32 status;  // contains lock, state and size
> >>         u32 unused;  // reserved for call_rcu stack handle
> >> };
> >>
> >> And then separately a helper type to pack/unpack status:
> >>
> >> union kasan_alloc_status {
> >>         u32 raw;
> >>         struct {
> >>                    u32 lock : 1;
> >>                    u32 state : 2;
> >>                    u32 unused : 5;
> >>                    u32 size : 24;
> >>         };
> >> };
> >>
> >>
> >> Then, when we need to read/update the header we do something like:
> >>
> >> kasan_alloc_status status, new_status;
> >>
> >> for (;;) {
> >>     status.raw = READ_ONCE(header->status);
> >>     // read status, form new_status, for example:
> >>     if (status.lock)
> >>           continue;
> >>     new_status.raw = status.raw;
> >>     new_status.lock = 1;
> >>     if (cas(&header->status, status.raw, new_status.raw))
> >>              break;
> >> }
> >>
> >>
> >> This will probably make state manipulation functions few lines longer,
> >> but since there are like 3 such functions I don't afraid that. And we
> >> still can use bitfield magic to extract fields and leave whole 5 bits
> >> unused bits for future.

v2 has been implemented with your suggested bitfield magic + cas loop. Thanks.

> >
> > The difficulty is that the lock managed by CAS needs 1 byte, mininum; TAS bit
> > is even 'worse': address must be that of an unsigned long.
> 
> cmpxchg function can operate on bytes, words, double words and quad words:
> http://lxr.free-electrons.com/source/arch/x86/include/asm/cmpxchg.h#L146
> 
> 
> > Might it be possible for you to employ the 'kasan_free_meta' header for your
> > RCU stack handle instead since KASAN does not currently store state for RCU
> > slabs on free?
> 
> Free meta is overlapped with user object. The object is not freed yet
> when call_rcu is invoked, so free meta cannot be used yet (user still
> holds own data there). Free meta can only be used after kfree is
> invoked on the object.

Yeah; Iwrongly assumed that kasan_cache_create() special treatment for
SLAB_DESTROY_BY_RCU slabs to store free meta at end of object covers all
uses of RCU. Anyway, "u32 reserved" in alloc meta is now available again...

Kuthonuzo

RE: [PATCH] kasan: improve double-free detection

[Luruo, Kuthonuzo]

> >> We can use per-header lock by setting status to KASAN_STATE_LOCKED.  A
> >> thread can CAS any status to KASAN_STATE_LOCKED which means that it
> >> locked the header. If any thread tried to modify/read the status and
> >> the status is KASAN_STATE_LOCKED, then the thread waits.
> >
> > Thanks, Dmitry. I've successfully tested with the concurrent free slab_test test
> > (alloc on cpu 0; then concurrent frees on all other cpus on a 12-vcpu KVM)
> using:
> >
> > static inline bool kasan_alloc_state_lock(struct kasan_alloc_meta *alloc_info)
> > {
> >         if (cmpxchg(&alloc_info->state, KASAN_STATE_ALLOC,
> >                                 KASAN_STATE_LOCKED) == KASAN_STATE_ALLOC)
> >                 return true;
> >         return false;
> > }
> >
> > static inline void kasan_alloc_state_unlock_wait(struct kasan_alloc_meta
> >                 *alloc_info)
> > {
> >         while (alloc_info->state == KASAN_STATE_LOCKED)
> >                 cpu_relax();
> > }
> >
> > Race "winner" sets state to quarantine as the last step:
> >
> >         if (kasan_alloc_state_lock(alloc_info)) {
> >                 free_info = get_free_info(cache, object);
> >                 quarantine_put(free_info, cache);
> >                 set_track(&free_info->track, GFP_NOWAIT);
> >                 kasan_poison_slab_free(cache, object);
> >                 alloc_info->state = KASAN_STATE_QUARANTINE;
> >                 return true;
> >         } else
> >                 kasan_alloc_state_unlock_wait(alloc_info);
> >
> > Now, I'm not sure whether on current KASAN-supported archs, state byte load
> in
> > the busy-wait loop is atomic wrt the KASAN_STATE_QUARANTINE byte store.
> > Would you advise using CAS primitives for load/store here too?
> 
> Store to state needs to use smp_store_release function, otherwise
> stores to free_info->track can sink below the store to state.
> Similarly, loads of state in kasan_alloc_state_unlock_wait need to use
> smp_store_acquire.
> 
> A function similar to kasan_alloc_state_lock will also be needed for
> KASAN_STATE_QUARANTINE -> KASAN_STATE_ALLOC state transition (when we
> reuse the object). If a thread tried to report use-after-free when
> another thread pushes the object out of quarantine and overwrites
> alloc_info->track, the thread will print a bogus stack.
> 
> kasan_alloc_state_unlock_wait is not enough to prevent the races.
> Consider that a thread executes kasan_alloc_state_unlock_wait and
> proceeds to reporting, at this point another thread pushes the object
> to quarantine or out of the quarantine and overwrites tracks. The
> first thread will read inconsistent data from the header. Any thread
> that reads/writes header needs to (1) wait while status is
> KASAN_STATE_LOCKED, (2) CAS status to KASAN_STATE_LOCKED, (3)
> read/write header, (4) restore/update status and effectively unlock
> the header.
> Alternatively, we can introduce LOCKED bit to header. Then it will be
> simpler for readers to set/unset the bit.

Thanks. As implemented in v2, all accesses to object alloc metadata (alloc,
dealloc, bug report and quarantine release) are now performed under
protection of a lock bit. Your suggested cmpxchg() loop for the lock is
paired with an xchg() on unlock which should address the memory ordering
issue.

In your race scenario between UAF and object reuse from new alloc, if
kmalloc wins, "UAF" report  would be bad (probably bug type
"unknown-crash" with thread stack + alloc stack). To close this window,
object meta lock would need to acquired much closer to point of bad
access detection. Patch does not address this race. How does ASAN
address this?

Kuthonuzo