[PATCH v4 1/2] mm, kasan: improve double-free detection

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

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.luruo@xxxxxxx>
---

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 18b6a2b..76a6634 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));
+		shadow_meta->data = KASAN_KMALLOC_META;
+	}
+}
 #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 (%u)!\n", alloc_state);
 			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;
+	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);
+	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 cc8bbc1..f7addb3 100644
--- a/mm/slab.c
+++ b/mm/slab.c
@@ -2651,6 +2651,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);
@@ -3548,7 +3549,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 825ff45..21c2b78 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