On Mon, May 2, 2016 at 1:41 PM, Dmitry Vyukov <dvyukov@xxxxxxxxxx> wrote:
> On Mon, May 2, 2016 at 12:09 PM, Dmitry Vyukov <dvyukov@xxxxxxxxxx> wrote:
>> On Mon, May 2, 2016 at 11:49 AM, Kuthonuzo Luruo
>> <kuthonuzo.luruo@xxxxxxx> 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@xxxxxxx>
>>> ---
>>> 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
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href