On Tue, Jun 7, 2016 at 8:03 PM, Kuthonuzo Luruo <kuthonuzo.lu...@hpe.com> wrote: > 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 serializing access to KASAN object metadata. > New functions kasan_meta_lock() and kasan_meta_unlock() are provided to > lock/unlock per-object metadata. Double-free errors are now reported via > kasan_report(). > > Per-object lock concept from suggestion/observations by Dmitry Vyukov. Note I've sent out a patch that enables stackdepot support in SLUB. I'll probably need to wait till you patch lands and add locking to SLUB as well.
> Testing: > - Tested with 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. > - Tested with new double-free tests for 'test_kasan' in accompanying patch. > > Signed-off-by: Kuthonuzo Luruo <kuthonuzo.lu...@hpe.com> > --- > > Changes in v5: > - Removed redundant print of 'alloc_state' for pr_err in kasan_slab_free. > > Changes in v4: > - Takes use of shadow memory in v3 further by storing lock bit in shadow > byte for object header solving the issue of OOB nuking the header lock. > Allocation state is also stored in the shadow header. > - CAS loop using cmpxchg() byte similar to v2 is brought back. > Unfortunately, standard lock primitives cannot be used since there aren't > enough header/redzone shadow bytes for smaller objects. (A generic > bit_spinlock() operating on a byte would have been sweet... :). > - CAS loop with union magic is largely due to suggestions on patch v2 from > Dmitry Vyukov. Thanks. > - preempt enable/disable inside CAS loop to reduce contention is from > review comment on v2 patch from Yury Norov. Thanks. > > Changes in v3: > - simplified kasan_meta_lock()/unlock() to use generic bit spinlock apis; > kasan_alloc_meta structure modified accordingly. > - introduced a 'safety valve' for kasan_meta_lock() to prevent a kfree from > getting stuck when a prior out-of-bounds write clobbers the object > header. > - removed potentially unsafe __builtin_return_address(1) from > kasan_report() call per review comment from Yury Norov; callee now passed > into kasan_slab_free(). > > --- > > include/linux/kasan.h | 7 ++- > mm/kasan/kasan.c | 125 > ++++++++++++++++++++++++++++++++++++++----------- > mm/kasan/kasan.h | 24 +++++++++- > mm/kasan/quarantine.c | 4 +- > mm/kasan/report.c | 24 +++++++++- > mm/slab.c | 3 +- > mm/slub.c | 2 +- > 7 files changed, 153 insertions(+), 36 deletions(-) > > diff --git a/include/linux/kasan.h b/include/linux/kasan.h > index 611927f..3db974b 100644 > --- a/include/linux/kasan.h > +++ b/include/linux/kasan.h > @@ -53,6 +53,7 @@ void kasan_cache_create(struct kmem_cache *cache, size_t > *size, > void kasan_cache_shrink(struct kmem_cache *cache); > void kasan_cache_destroy(struct kmem_cache *cache); > > +void kasan_init_object(struct kmem_cache *cache, void *object); > void kasan_poison_slab(struct page *page); > void kasan_unpoison_object_data(struct kmem_cache *cache, void *object); > void kasan_poison_object_data(struct kmem_cache *cache, void *object); > @@ -65,7 +66,7 @@ void kasan_kmalloc(struct kmem_cache *s, const void > *object, size_t size, > void kasan_krealloc(const void *object, size_t new_size, gfp_t flags); > > void kasan_slab_alloc(struct kmem_cache *s, void *object, gfp_t flags); > -bool kasan_slab_free(struct kmem_cache *s, void *object); > +bool kasan_slab_free(struct kmem_cache *s, void *object, unsigned long > caller); > void kasan_poison_slab_free(struct kmem_cache *s, void *object); > > struct kasan_cache { > @@ -94,6 +95,7 @@ static inline void kasan_cache_create(struct kmem_cache > *cache, > static inline void kasan_cache_shrink(struct kmem_cache *cache) {} > static inline void kasan_cache_destroy(struct kmem_cache *cache) {} > > +static inline void kasan_init_object(struct kmem_cache *s, void *object) {} > static inline void kasan_poison_slab(struct page *page) {} > static inline void kasan_unpoison_object_data(struct kmem_cache *cache, > void *object) {} > @@ -110,7 +112,8 @@ static inline void kasan_krealloc(const void *object, > size_t new_size, > > static inline void kasan_slab_alloc(struct kmem_cache *s, void *object, > gfp_t flags) {} > -static inline bool kasan_slab_free(struct kmem_cache *s, void *object) > +static inline bool kasan_slab_free(struct kmem_cache *s, void *object, > + unsigned long caller) > { > return false; > } > diff --git a/mm/kasan/kasan.c b/mm/kasan/kasan.c > index 28439ac..daec64b 100644 > --- a/mm/kasan/kasan.c > +++ b/mm/kasan/kasan.c > @@ -402,6 +402,23 @@ void kasan_cache_create(struct kmem_cache *cache, size_t > *size, > cache->object_size + > optimal_redzone(cache->object_size))); > } > + > +static inline union kasan_shadow_meta *get_shadow_meta( > + struct kasan_alloc_meta *allocp) > +{ > + return (union kasan_shadow_meta *)kasan_mem_to_shadow((void *)allocp); > +} > + > +void kasan_init_object(struct kmem_cache *cache, void *object) > +{ > + if (cache->flags & SLAB_KASAN) { > + struct kasan_alloc_meta *allocp = get_alloc_info(cache, > object); > + union kasan_shadow_meta *shadow_meta = > get_shadow_meta(allocp); > + > + __memset(allocp, 0, sizeof(*allocp)); I think we need initialize the lock first, then lock it in order to touch *allocp. > + shadow_meta->data = KASAN_KMALLOC_META; Shouldn't this be a release store? > + } > +} > #endif > > void kasan_cache_shrink(struct kmem_cache *cache) > @@ -431,13 +448,6 @@ void kasan_poison_object_data(struct kmem_cache *cache, > void *object) > kasan_poison_shadow(object, > round_up(cache->object_size, KASAN_SHADOW_SCALE_SIZE), > KASAN_KMALLOC_REDZONE); > -#ifdef CONFIG_SLAB > - if (cache->flags & SLAB_KASAN) { > - struct kasan_alloc_meta *alloc_info = > - get_alloc_info(cache, object); > - alloc_info->state = KASAN_STATE_INIT; > - } > -#endif > } > > #ifdef CONFIG_SLAB > @@ -501,6 +511,53 @@ struct kasan_free_meta *get_free_info(struct kmem_cache > *cache, > BUILD_BUG_ON(sizeof(struct kasan_free_meta) > 32); > return (void *)object + cache->kasan_info.free_meta_offset; > } > + > +u8 get_alloc_state(struct kasan_alloc_meta *alloc_info) > +{ > + return get_shadow_meta(alloc_info)->state; > +} > + > +void set_alloc_state(struct kasan_alloc_meta *alloc_info, u8 state) > +{ > + get_shadow_meta(alloc_info)->state = state; > +} > + > +/* > + * Acquire per-object lock before accessing KASAN metadata. Lock bit is > stored > + * in header shadow memory to protect it from being flipped by out-of-bounds > + * accesses on object. Standard lock primitives cannot be used since there > + * aren't enough header shadow bytes. > + */ > +void kasan_meta_lock(struct kasan_alloc_meta *alloc_info) > +{ > + union kasan_shadow_meta *shadow_meta = get_shadow_meta(alloc_info); > + union kasan_shadow_meta old, new; > + > + for (;;) { > + old.data = READ_ONCE(shadow_meta->data); > + if (old.lock) { > + cpu_relax(); > + continue; > + } > + new.data = old.data; > + new.lock = 1; > + preempt_disable(); > + if (cmpxchg(&shadow_meta->data, old.data, new.data) == > old.data) > + break; > + preempt_enable(); > + } > +} > + > +/* Release lock after a kasan_meta_lock(). */ > +void kasan_meta_unlock(struct kasan_alloc_meta *alloc_info) > +{ > + union kasan_shadow_meta *shadow_meta = get_shadow_meta(alloc_info), > new; > + > + new.data = READ_ONCE(shadow_meta->data); > + new.lock = 0; > + smp_store_release(&shadow_meta->data, new.data); > + preempt_enable(); > +} > #endif > > void kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t flags) > @@ -520,35 +577,44 @@ void kasan_poison_slab_free(struct kmem_cache *cache, > void *object) > kasan_poison_shadow(object, rounded_up_size, KASAN_KMALLOC_FREE); > } > > -bool kasan_slab_free(struct kmem_cache *cache, void *object) > +bool kasan_slab_free(struct kmem_cache *cache, void *object, > + unsigned long caller) > { > #ifdef CONFIG_SLAB > + struct kasan_alloc_meta *alloc_info; > + struct kasan_free_meta *free_info; > + u8 alloc_state; > + > /* 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); > + kasan_meta_lock(alloc_info); > + alloc_state = get_alloc_state(alloc_info); > + if (alloc_state == 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); > + set_alloc_state(alloc_info, KASAN_STATE_QUARANTINE); > + kasan_meta_unlock(alloc_info); > + return true; > + } > + switch (alloc_state) { > case KASAN_STATE_QUARANTINE: > case KASAN_STATE_FREE: > - pr_err("Double free"); > - dump_stack(); > - break; > + kasan_report((unsigned long)object, 0, false, caller); > + kasan_meta_unlock(alloc_info); > + return true; > default: > + pr_err("invalid allocation state!\n"); I suggest you also print the object pointer here. > break; > - } > } > + kasan_meta_unlock(alloc_info); > return false; > #else > kasan_poison_slab_free(cache, object); > @@ -580,10 +646,15 @@ void kasan_kmalloc(struct kmem_cache *cache, const void > *object, size_t size, > if (cache->flags & SLAB_KASAN) { > struct kasan_alloc_meta *alloc_info = > get_alloc_info(cache, object); > + unsigned long flags; > > - alloc_info->state = KASAN_STATE_ALLOC; > + local_irq_save(flags); > + kasan_meta_lock(alloc_info); > + set_alloc_state(alloc_info, KASAN_STATE_ALLOC); > alloc_info->alloc_size = size; > set_track(&alloc_info->track, flags); > + kasan_meta_unlock(alloc_info); > + local_irq_restore(flags); > } > #endif > } > @@ -636,7 +707,7 @@ void kasan_kfree(void *ptr) > kasan_poison_shadow(ptr, PAGE_SIZE << compound_order(page), > KASAN_FREE_PAGE); > else > - kasan_slab_free(page->slab_cache, ptr); > + kasan_slab_free(page->slab_cache, ptr, _RET_IP_); > } > > void kasan_kfree_large(const void *ptr) > diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h > index fb87923..76bdadd 100644 > --- a/mm/kasan/kasan.h > +++ b/mm/kasan/kasan.h > @@ -12,6 +12,8 @@ > #define KASAN_KMALLOC_REDZONE 0xFC /* redzone inside slub object */ > #define KASAN_KMALLOC_FREE 0xFB /* object was freed > (kmem_cache_free/kfree) */ > #define KASAN_GLOBAL_REDZONE 0xFA /* redzone for global variable */ > +#define KASAN_KMALLOC_META 0xE0 /* slab object header shadow; see > union kasan_shadow_meta */ > +#define KASAN_KMALLOC_META_MAX 0xEF /* end of header shadow code */ > > /* > * Stack redzone shadow values > @@ -73,10 +75,24 @@ struct kasan_track { > depot_stack_handle_t stack; > }; > > +/* > + * Object header lock bit and allocation state are stored in shadow memory to > + * prevent out-of-bounds accesses on object from overwriting them. > + */ > +union kasan_shadow_meta { > + u8 data; > + struct { > + u8 lock : 1; /* lock bit */ > + u8 state : 2; /* enum kasan_state */ > + u8 unused : 1; > + u8 poison : 4; /* poison constant; do not use */ > + }; > +}; > + > struct kasan_alloc_meta { > + u32 alloc_size : 24; Why reduce the alloc size? > + u32 unused : 8; > struct kasan_track track; > - u32 state : 2; /* enum kasan_state */ > - u32 alloc_size : 30; > }; > > struct qlist_node { > @@ -114,6 +130,10 @@ void kasan_report(unsigned long addr, size_t size, > void quarantine_put(struct kasan_free_meta *info, struct kmem_cache *cache); > void quarantine_reduce(void); > void quarantine_remove_cache(struct kmem_cache *cache); > +void kasan_meta_lock(struct kasan_alloc_meta *alloc_info); > +void kasan_meta_unlock(struct kasan_alloc_meta *alloc_info); > +u8 get_alloc_state(struct kasan_alloc_meta *alloc_info); > +void set_alloc_state(struct kasan_alloc_meta *alloc_info, u8 state); > #else > static inline void quarantine_put(struct kasan_free_meta *info, > struct kmem_cache *cache) { } > diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c > index 4973505..ce9c913 100644 > --- a/mm/kasan/quarantine.c > +++ b/mm/kasan/quarantine.c > @@ -148,7 +148,9 @@ static void qlink_free(struct qlist_node *qlink, struct > kmem_cache *cache) > unsigned long flags; > > local_irq_save(flags); > - alloc_info->state = KASAN_STATE_FREE; > + kasan_meta_lock(alloc_info); > + set_alloc_state(alloc_info, KASAN_STATE_FREE); > + kasan_meta_unlock(alloc_info); > ___cache_free(cache, object, _THIS_IP_); > local_irq_restore(flags); > } > diff --git a/mm/kasan/report.c b/mm/kasan/report.c > index b3c122d..48c9c60 100644 > --- a/mm/kasan/report.c > +++ b/mm/kasan/report.c > @@ -53,6 +53,17 @@ static void print_error_description(struct > kasan_access_info *info) > const char *bug_type = "unknown-crash"; > u8 *shadow_addr; > > +#ifdef CONFIG_SLAB > + if (!info->access_size) { > + bug_type = "double-free"; > + pr_err("BUG: KASAN: %s attempt in %pS on object at addr %p\n", > + bug_type, (void *)info->ip, > info->access_addr); > + pr_err("%s by task %s/%d\n", bug_type, current->comm, > + task_pid_nr(current)); > + info->first_bad_addr = info->access_addr; > + return; > + } > +#endif > info->first_bad_addr = find_first_bad_addr(info->access_addr, > info->access_size); > > @@ -75,6 +86,7 @@ static void print_error_description(struct > kasan_access_info *info) > break; > case KASAN_PAGE_REDZONE: > case KASAN_KMALLOC_REDZONE: > + case KASAN_KMALLOC_META ... KASAN_KMALLOC_META_MAX: > bug_type = "slab-out-of-bounds"; > break; > case KASAN_GLOBAL_REDZONE: > @@ -131,7 +143,7 @@ static void print_track(struct kasan_track *track) > } > > static void object_err(struct kmem_cache *cache, struct page *page, > - void *object, char *unused_reason) > + void *object, struct kasan_access_info *info) > { > struct kasan_alloc_meta *alloc_info = get_alloc_info(cache, object); > struct kasan_free_meta *free_info; > @@ -140,7 +152,9 @@ static void object_err(struct kmem_cache *cache, struct > page *page, > pr_err("Object at %p, in cache %s\n", object, cache->name); > if (!(cache->flags & SLAB_KASAN)) > return; > - switch (alloc_info->state) { > + if (info->access_size) > + kasan_meta_lock(alloc_info); In which case can info->access_size be zero? Guess even in that case we need to lock the metadata. > + switch (get_alloc_state(alloc_info)) { > case KASAN_STATE_INIT: > pr_err("Object not allocated yet\n"); > break; > @@ -161,6 +175,8 @@ static void object_err(struct kmem_cache *cache, struct > page *page, > print_track(&free_info->track); > break; > } > + if (info->access_size) > + kasan_meta_unlock(alloc_info); > } > #endif > > @@ -177,8 +193,12 @@ static void print_address_description(struct > kasan_access_info *info) > struct kmem_cache *cache = page->slab_cache; > object = nearest_obj(cache, page, > (void *)info->access_addr); > +#ifdef CONFIG_SLAB > + object_err(cache, page, object, info); > +#else > object_err(cache, page, object, > "kasan: bad access detected"); > +#endif > return; > } > dump_page(page, "kasan: bad access detected"); > diff --git a/mm/slab.c b/mm/slab.c > index 763096a..b8c51a6 100644 > --- a/mm/slab.c > +++ b/mm/slab.c > @@ -2611,6 +2611,7 @@ static void cache_init_objs(struct kmem_cache *cachep, > cachep->ctor(objp); > kasan_poison_object_data(cachep, objp); > } > + kasan_init_object(cachep, index_to_obj(cachep, page, i)); > > if (!shuffled) > set_free_obj(page, i, i); > @@ -3508,7 +3509,7 @@ static inline void __cache_free(struct kmem_cache > *cachep, void *objp, > unsigned long caller) > { > /* Put the object into the quarantine, don't touch it for now. */ > - if (kasan_slab_free(cachep, objp)) > + if (kasan_slab_free(cachep, objp, _RET_IP_)) > return; > > ___cache_free(cachep, objp, caller); > diff --git a/mm/slub.c b/mm/slub.c > index 5beeeb2..f25c0c2 100644 > --- a/mm/slub.c > +++ b/mm/slub.c > @@ -1344,7 +1344,7 @@ static inline void slab_free_hook(struct kmem_cache *s, > void *x) > if (!(s->flags & SLAB_DEBUG_OBJECTS)) > debug_check_no_obj_freed(x, s->object_size); > > - kasan_slab_free(s, x); > + kasan_slab_free(s, x, _RET_IP_); > } > > static inline void slab_free_freelist_hook(struct kmem_cache *s, > -- > 1.7.1 > -- 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