SLAB support for KASAN

depending on which allocator (SLAB or SLUB) is being used

...

lib/test_kasan.c +6 -1

@@ -68,7 +68,22 @@ static noinline void __init kmalloc_node_oob_right(void)
 static noinline void __init kmalloc_large_oob_right(void)
 {
 	char *ptr;
-	size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
+	size_t size;
+
+	if (KMALLOC_MAX_CACHE_SIZE == KMALLOC_MAX_SIZE) {
+		/*
+		 * We're using the SLAB allocator. Allocate a chunk that fits
+		 * into a slab.

Quoted 17 lines · On Wed, 27 Jan 2016 19:25:06 +0100 Alexander Potapenko <[email protected]>…

depending on which allocator (SLAB or SLUB) is being used

...

lib/test_kasan.c +6 -1

@@ -68,7 +68,22 @@ static noinline void __init kmalloc_node_oob_right(void)
 static noinline void __init kmalloc_large_oob_right(void)
 {
 	char *ptr;
-	size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
+	size_t size;
+
+	if (KMALLOC_MAX_CACHE_SIZE == KMALLOC_MAX_SIZE) {
+		/*
+		 * We're using the SLAB allocator. Allocate a chunk that fits
+		 * into a slab.

lib/test_kasan.c static noinline void __init kmalloc_node_oob_right(void) · line 86

Quoted 10 lines

lib/test_kasan.c +10 -0

+		 */
+		size = KMALLOC_MAX_CACHE_SIZE - 256;
+	} else {
+		/*
+		 * KMALLOC_MAX_SIZE > KMALLOC_MAX_CACHE_SIZE.
+		 * We're using the SLUB allocator. Allocate a chunk that does
+		 * not fit into a slab to trigger the page allocator.
+		 */
+		size = KMALLOC_MAX_CACHE_SIZE + 10;
+	}

This seems a weird way of working out whether we're using SLAB or SLUB.

Can't we use, umm, #ifdef CONFIG_SLAB? If not that then let's cook up something standardized rather than a weird just-happens-to-work like this.

Quoted 32 lines · Andrew Morton

Quoted 17 lines · On Wed, 27 Jan 2016 19:25:06 +0100 Alexander Potapenko <[email protected]>…

depending on which allocator (SLAB or SLUB) is being used

...

lib/test_kasan.c +6 -1

@@ -68,7 +68,22 @@ static noinline void __init kmalloc_node_oob_right(void)
 static noinline void __init kmalloc_large_oob_right(void)
 {
     char *ptr;
-    size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
+    size_t size;
+
+    if (KMALLOC_MAX_CACHE_SIZE == KMALLOC_MAX_SIZE) {
+            /*
+             * We're using the SLAB allocator. Allocate a chunk that fits
+             * into a slab.

lib/test_kasan.c static noinline void __init kmalloc_node_oob_right(void) · line 86

Quoted 10 lines

lib/test_kasan.c +10 -0

+             */
+            size = KMALLOC_MAX_CACHE_SIZE - 256;
+    } else {
+            /*
+             * KMALLOC_MAX_SIZE > KMALLOC_MAX_CACHE_SIZE.
+             * We're using the SLUB allocator. Allocate a chunk that does
+             * not fit into a slab to trigger the page allocator.
+             */
+            size = KMALLOC_MAX_CACHE_SIZE + 10;
+    }

This seems a weird way of working out whether we're using SLAB or SLUB.

Quoted 4 lines

Can't we use, umm, #ifdef CONFIG_SLAB? If not that then let's cook up something standardized rather than a weird just-happens-to-work like this.

Actually it would be simpler to not use KMALLOC_MAX_CACHE_SIZE at all. Simply replace it with 2 or 3 PAGE_SIZEs.

The intention was to detect the situation in which a new allocator appears for which we don't know how it behaves if we allocate more than KMALLOC_MAX_CACHE_SIZE.
I agree this makes little sense and we can just stick to CONFIG_SLAB/CONFIG_SLUB cases.

However I think it's better to keep 'size = KMALLOC_MAX_CACHE_SIZE + something' to keep this code working in the case the value of KMALLOC_MAX_CACHE_SIZE changes.

Quoted 35 lines · Andrey Ryabinin

Quoted 32 lines · Andrew Morton

Quoted 17 lines · On Wed, 27 Jan 2016 19:25:06 +0100 Alexander Potapenko <[email protected]>…

depending on which allocator (SLAB or SLUB) is being used

...

lib/test_kasan.c +6 -1

@@ -68,7 +68,22 @@ static noinline void __init kmalloc_node_oob_right(void)
 static noinline void __init kmalloc_large_oob_right(void)
 {
     char *ptr;
-    size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
+    size_t size;
+
+    if (KMALLOC_MAX_CACHE_SIZE == KMALLOC_MAX_SIZE) {
+            /*
+             * We're using the SLAB allocator. Allocate a chunk that fits
+             * into a slab.

lib/test_kasan.c static noinline void __init kmalloc_node_oob_right(void) · line 86

Quoted 10 lines

lib/test_kasan.c +10 -0

+             */
+            size = KMALLOC_MAX_CACHE_SIZE - 256;
+    } else {
+            /*
+             * KMALLOC_MAX_SIZE > KMALLOC_MAX_CACHE_SIZE.
+             * We're using the SLUB allocator. Allocate a chunk that does
+             * not fit into a slab to trigger the page allocator.
+             */
+            size = KMALLOC_MAX_CACHE_SIZE + 10;
+    }

This seems a weird way of working out whether we're using SLAB or SLUB.

Quoted 7 lines

Quoted 4 lines

Can't we use, umm, #ifdef CONFIG_SLAB? If not that then let's cook up something standardized rather than a weird just-happens-to-work like this.

Actually it would be simpler to not use KMALLOC_MAX_CACHE_SIZE at all. Simply replace it with 2 or 3 PAGE_SIZEs.

--
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
Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind, leiten Sie diese bitte nicht weiter, informieren Sie den Absender und löschen Sie die E-Mail und alle Anhänge. Vielen Dank. This e-mail is confidential. If you are not the right addressee please do not forward it, please inform the sender, and please erase this e-mail including any attachments. Thanks.

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

Quoted 8 lines · Alexander Potapenko

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

...

mm/kasan/kasan.c void kasan_poison_object_data(struct kmem_cache *cache, void *object) · line 415

Quoted 13 lines

mm/kasan/kasan.c +13 -0

+#ifdef CONFIG_SLAB
+struct kasan_alloc_meta *get_alloc_info(struct kmem_cache *cache,
+                                     const void *object)
+{
+     return (void *)object + cache->kasan_info.alloc_meta_offset;
+}
+
+struct kasan_free_meta *get_free_info(struct kmem_cache *cache,
+                                   const void *object)
+{
+     return (void *)object + cache->kasan_info.free_meta_offset;
+}
+#endif

I cannot find the place to store stack info for free. get_free_info() isn't used except print_object(). Plese let me know where.

Thanks.

Quoted 13 lines · Joonsoo Kim

Quoted 8 lines · Alexander Potapenko

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

...

Quoted 16 lines

mm/kasan/kasan.c void kasan_poison_object_data(struct kmem_cache *cache, void *object) · line 415

Quoted 13 lines

mm/kasan/kasan.c +13 -0

+#ifdef CONFIG_SLAB
+struct kasan_alloc_meta *get_alloc_info(struct kmem_cache *cache,
+                                     const void *object)
+{
+     return (void *)object + cache->kasan_info.alloc_meta_offset;
+}
+
+struct kasan_free_meta *get_free_info(struct kmem_cache *cache,
+                                   const void *object)
+{
+     return (void *)object + cache->kasan_info.free_meta_offset;
+}
+#endif

I cannot find the place to store stack info for free. get_free_info() isn't used except print_object(). Plese let me know where.

This is covered by other patches in this patchset.

Quoted 1 line

Thanks.

Quoted 32 lines · Alexander Potapenko

Quoted 29 lines · Joonsoo Kim

Quoted 8 lines · Alexander Potapenko

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

...

mm/kasan/kasan.c void kasan_poison_object_data(struct kmem_cache *cache, void *object) · line 415

Quoted 13 lines

mm/kasan/kasan.c +13 -0

+#ifdef CONFIG_SLAB
+struct kasan_alloc_meta *get_alloc_info(struct kmem_cache *cache,
+                                     const void *object)
+{
+     return (void *)object + cache->kasan_info.alloc_meta_offset;
+}
+
+struct kasan_free_meta *get_free_info(struct kmem_cache *cache,
+                                   const void *object)
+{
+     return (void *)object + cache->kasan_info.free_meta_offset;
+}
+#endif

I cannot find the place to store stack info for free. get_free_info() isn't used except print_object(). Plese let me know where.

Quoted 1 line

This is covered by other patches in this patchset.

Quoted 33 lines · Alexander Potapenko

Quoted 32 lines · Alexander Potapenko

Quoted 29 lines · Joonsoo Kim

Quoted 8 lines · Alexander Potapenko

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

...

mm/kasan/kasan.c void kasan_poison_object_data(struct kmem_cache *cache, void *object) · line 415

Quoted 13 lines

mm/kasan/kasan.c +13 -0

+#ifdef CONFIG_SLAB
+struct kasan_alloc_meta *get_alloc_info(struct kmem_cache *cache,
+                                     const void *object)
+{
+     return (void *)object + cache->kasan_info.alloc_meta_offset;
+}
+
+struct kasan_free_meta *get_free_info(struct kmem_cache *cache,
+                                   const void *object)
+{
+     return (void *)object + cache->kasan_info.free_meta_offset;
+}
+#endif

I cannot find the place to store stack info for free. get_free_info() isn't used except print_object(). Plese let me know where.

Quoted 1 line

Quoted 1 line

This is covered by other patches in this patchset.

This should be covered by this patch. Stroing and printing free_info is already done on SLUB and it is meaningful without quarantain.

Thanks.

Quoted 34 lines · Alexander Potapenko

Quoted 33 lines · Alexander Potapenko

Quoted 32 lines · Joonsoo Kim

Quoted 29 lines · Alexander Potapenko

Quoted 8 lines

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

...

mm/kasan/kasan.c void kasan_poison_object_data(struct kmem_cache *cache, void *object) · line 415

Quoted 13 lines

mm/kasan/kasan.c +13 -0

+#ifdef CONFIG_SLAB
+struct kasan_alloc_meta *get_alloc_info(struct kmem_cache *cache,
+                                     const void *object)
+{
+     return (void *)object + cache->kasan_info.alloc_meta_offset;
+}
+
+struct kasan_free_meta *get_free_info(struct kmem_cache *cache,
+                                   const void *object)
+{
+     return (void *)object + cache->kasan_info.free_meta_offset;
+}
+#endif

I cannot find the place to store stack info for free. get_free_info() isn't used except print_object(). Plese let me know where.

Quoted 4 lines

Quoted 1 line

Quoted 1 line

This is covered by other patches in this patchset.

This should be covered by this patch. Stroing and printing free_info is already done on SLUB and it is meaningful without quarantain.

However this info is meaningless without saved stack traces, which are only introduced in the stackdepot patch (see "[PATCH v1 5/8] mm,
kasan: Stackdepot implementation. Enable stackdepot for SLAB")

Quoted 35 lines · Joonsoo Kim

Quoted 34 lines · Alexander Potapenko

Quoted 33 lines · Alexander Potapenko

Quoted 32 lines · Joonsoo Kim

Quoted 29 lines · Alexander Potapenko

Quoted 8 lines

This patch adds KASAN hooks to SLAB allocator.

This patch is based on the "mm: kasan: unified support for SLUB and SLAB allocators" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 Documentation/kasan.txt  |  5 ++-

...

Review

Quoted 13 lines

(quoted diff) +13 -0

+#ifdef CONFIG_SLAB
+struct kasan_alloc_meta *get_alloc_info(struct kmem_cache *cache,
+                                     const void *object)
+{
+     return (void *)object + cache->kasan_info.alloc_meta_offset;
+}
+
+struct kasan_free_meta *get_free_info(struct kmem_cache *cache,
+                                   const void *object)
+{
+     return (void *)object + cache->kasan_info.free_meta_offset;
+}
+#endif

I cannot find the place to store stack info for free. get_free_info() isn't used except print_object(). Plese let me know where.

Quoted 4 lines

Quoted 4 lines

Quoted 1 line

Quoted 1 line

This is covered by other patches in this patchset.

This should be covered by this patch. Stroing and printing free_info is already done on SLUB and it is meaningful without quarantain.

2016-02-18 21:58 GMT+09:00 Alexander Potapenko <[email protected]>:

Quoted 3 lines

However this info is meaningless without saved stack traces, which are only introduced in the stackdepot patch (see "[PATCH v1 5/8] mm,
kasan: Stackdepot implementation. Enable stackdepot for SLAB")

Not meaningless. You already did it for allocation caller without saved stack traces. What makes difference between alloc/free?

Thanks.

include/linux/ftrace.h +13 -0

@@ -762,6 +762,26 @@ struct ftrace_graph_ret {
 typedef void (*trace_func_graph_ret_t)(struct ftrace_graph_ret *); /* return */
 typedef int (*trace_func_graph_ent_t)(struct ftrace_graph_ent *); /* entry */
 
+#if defined(CONFIG_FUNCTION_GRAPH_TRACER) || defined(CONFIG_KASAN)
+/*
+ * We want to know which function is an entrypoint of a hardirq.
+ */
+#define __irq_entry		 __attribute__((__section__(".irqentry.text")))
+#define __softirq_entry  \
+	__attribute__((__section__(".softirqentry.text")))
+
+/* Limits of hardirq entrypoints */
+extern char __irqentry_text_start[];
+extern char __irqentry_text_end[];
+/* Limits of softirq entrypoints */
+extern char __softirqentry_text_start[];

Quoted 19 lines · On Wed, 27 Jan 2016 19:25:09 +0100 Alexander Potapenko <[email protected]>…

include/linux/ftrace.h +13 -0

@@ -762,6 +762,26 @@ struct ftrace_graph_ret {
 typedef void (*trace_func_graph_ret_t)(struct ftrace_graph_ret *); /* return */
 typedef int (*trace_func_graph_ent_t)(struct ftrace_graph_ent *); /* entry */
 
+#if defined(CONFIG_FUNCTION_GRAPH_TRACER) || defined(CONFIG_KASAN)
+/*
+ * We want to know which function is an entrypoint of a hardirq.
+ */
+#define __irq_entry           __attribute__((__section__(".irqentry.text")))
+#define __softirq_entry  \
+     __attribute__((__section__(".softirqentry.text")))
+
+/* Limits of hardirq entrypoints */
+extern char __irqentry_text_start[];
+extern char __irqentry_text_end[];
+/* Limits of softirq entrypoints */
+extern char __softirqentry_text_start[];

include/linux/ftrace.h struct ftrace_graph_ret { · line 787

Quoted 10 lines

include/linux/ftrace.h +7 -0

+extern char __softirqentry_text_end[];
+
+#else
+#define __irq_entry
+#define __softirq_entry
+#endif
+
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 
 /* for init task */

Since this is no longer just used for function tracing, perhaps the code should be moved to include/linux/irq.h or something.

-- Steve

Agreed. Once I receive more comments I will make a new patch set and include this change as well.

Quoted 31 lines · Steven Rostedt

Quoted 28 lines · On Wed, 27 Jan 2016 19:25:09 +0100 Alexander Potapenko <[email protected]>…

include/linux/ftrace.h +20 -0

@@ -762,6 +762,26 @@ struct ftrace_graph_ret {
 typedef void (*trace_func_graph_ret_t)(struct ftrace_graph_ret *); /* return */
 typedef int (*trace_func_graph_ent_t)(struct ftrace_graph_ent *); /* entry */
 
+#if defined(CONFIG_FUNCTION_GRAPH_TRACER) || defined(CONFIG_KASAN)
+/*
+ * We want to know which function is an entrypoint of a hardirq.
+ */
+#define __irq_entry           __attribute__((__section__(".irqentry.text")))
+#define __softirq_entry  \
+     __attribute__((__section__(".softirqentry.text")))
+
+/* Limits of hardirq entrypoints */
+extern char __irqentry_text_start[];
+extern char __irqentry_text_end[];
+/* Limits of softirq entrypoints */
+extern char __softirqentry_text_start[];
+extern char __softirqentry_text_end[];
+
+#else
+#define __irq_entry
+#define __softirq_entry
+#endif
+
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 

Quoted 7 lines

include/linux/ftrace.h struct ftrace_graph_ret { · line 787

Quoted 1 line

include/linux/ftrace.h +0 -0

 /* for init task */

Since this is no longer just used for function tracing, perhaps the code should be moved to include/linux/irq.h or something.

-- Steve

--
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
Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind, leiten Sie diese bitte nicht weiter, informieren Sie den Absender und löschen Sie die E-Mail und alle Anhänge. Vielen Dank. This e-mail is confidential. If you are not the right addressee please do not forward it, please inform the sender, and please erase this e-mail including any attachments. Thanks.

On the other hand, this will require including <linux/irq.h> into various files that currently use __irq_section.
But that header has a comment saying:

/*
* Please do not include this file in generic code. There is currently
* no requirement for any architecture to implement anything held
* within this file.
*
* Thanks. --rmk
*/

Do we really want to put anything into that header?

Quoted 12 lines · On Fri, 29 Jan 2016 12:59:13 +0100 Alexander Potapenko <[email protected]>…

On the other hand, this will require including <linux/irq.h> into various files that currently use __irq_section.
But that header has a comment saying:

/*
* Please do not include this file in generic code. There is currently
* no requirement for any architecture to implement anything held
* within this file.
*
* Thanks. --rmk
*/

Quoted 2 lines

Do we really want to put anything into that header?

What about interrupt.h?

It's just weird to have KSAN needing to pull in ftrace.h for irq work.

-- Steve

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference

and allow to remove. Is it possible?

Thanks.

Quoted 9 lines · Joonsoo Kim

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.
There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).

I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

Quoted 2 lines

Thanks.

Quoted 17 lines · Alexander Potapenko

Quoted 9 lines · Joonsoo Kim

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 7 lines

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.

Quoted 8 lines

There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).
I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

Quoted 18 lines · Alexander Potapenko

Quoted 17 lines · Alexander Potapenko

Quoted 9 lines · Joonsoo Kim

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.

Okay.

Quoted 8 lines

Quoted 8 lines

There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).
I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

I re-think the page owner case and it also may not need refcount. For now, just moving this stuff to /lib would be helpful for other future user.

BTW, is there any performance number? I guess that it could affect the performance.

Thanks.

Quoted 38 lines · Joonsoo Kim

Quoted 18 lines · Alexander Potapenko

Quoted 17 lines · Alexander Potapenko

Quoted 9 lines · Joonsoo Kim

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.

Okay.

Quoted 8 lines

Quoted 8 lines

There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).
I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

Quoted 2 lines

I re-think the page owner case and it also may not need refcount. For now, just moving this stuff to /lib would be helpful for other future user.

I agree this code may need to be moved to /lib someday, but I wouldn't hurry with that.
Right now it is quite KASAN-specific, and it's unclear yet whether anyone else is going to use it.
I suggest we keep it in mm/kasan for now, and factor the common parts into /lib when the need arises.

Quoted 2 lines

BTW, is there any performance number? I guess that it could affect the performance.

I've compared the performance of KASAN with SLAB allocator on a small synthetic benchmark in two modes: with stack depot enabled and with kasan_save_stack() unconditionally returning 0.
In the former case 8% more time was spent in the kernel than in the latter case.

If I am not mistaking, for SLUB allocator the bookkeeping (enabled with the slub_debug=UZ boot options) take only 1.5 time, so the difference is worth looking into (at least before we switch SLUB to stack depot).

Quoted 2 lines

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
Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind, leiten Sie diese bitte nicht weiter, informieren Sie den Absender und löschen Sie die E-Mail und alle Anhänge. Vielen Dank. This e-mail is confidential. If you are not the right addressee please do not forward it, please inform the sender, and please erase this e-mail including any attachments. Thanks.

Quoted 55 lines · Joonsoo Kim

Quoted 38 lines · Alexander Potapenko

Quoted 18 lines · Alexander Potapenko

Quoted 17 lines · Joonsoo Kim

Quoted 9 lines

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.

Okay.

Quoted 8 lines

Quoted 8 lines

There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).
I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

Quoted 2 lines

I re-think the page owner case and it also may not need refcount. For now, just moving this stuff to /lib would be helpful for other future user.

I agree this code may need to be moved to /lib someday, but I wouldn't hurry with that.
Right now it is quite KASAN-specific, and it's unclear yet whether anyone else is going to use it.
I suggest we keep it in mm/kasan for now, and factor the common parts into /lib when the need arises.

Quoted 2 lines

BTW, is there any performance number? I guess that it could affect the performance.

I've compared the performance of KASAN with SLAB allocator on a small synthetic benchmark in two modes: with stack depot enabled and with kasan_save_stack() unconditionally returning 0.
In the former case 8% more time was spent in the kernel than in the latter case.

Quoted 4 lines

If I am not mistaking, for SLUB allocator the bookkeeping (enabled with the slub_debug=UZ boot options) take only 1.5 time, so the difference is worth looking into (at least before we switch SLUB to stack depot).

I've made additional measurements.
Previously I had been using a userspace benchmark that created and destroyed pipes in a loop
(https://github.com/google/sanitizers/blob/master/address-sanitizer/kernel_buildbot/slave/bench_pipes.c).

Now I've made a kernel module that allocated and deallocated memory chunks of different sizes in a loop.
There were two modes of operation:
1) all the allocations were made from the same function, therefore all allocation/deallocation stacks were similar and there always was a hit in the stackdepot hashtable
2) The allocations were made from 2^16 different stacks.

In the first case SLAB+stackdepot turned out to be 13% faster than SLUB+slub_debug, in the second SLAB was 11% faster.

Note that in both cases and for both allocators most of the time (more than 90%) was spent in the x86 stack unwinder, which is common for both approaches.

Yet another observation regarding stackdepot: under a heavy load (running Trinity for a hour, 101M allocations) the depot saturates at around 20K records with the hashtable miss rate of 0.02%. That said, I still cannot justify the results of the userspace benchmark, but the slowdown of the stackdepot approach for SLAB sounds acceptable, especially given the memory gain compared to SLUB bookkeeping (which requires 128 bytes per memory allocation) and the fact we'll be dealing with the fast path most of the time.

It will certainly be nice to compare SLUB+slub_debug to SLUB+stackdepot once we start switching SLUB to stackdepot.

2016-02-18 3:29 GMT+09:00 Alexander Potapenko <[email protected]>:

Quoted 74 lines · Alexander Potapenko

Quoted 55 lines · Joonsoo Kim

Quoted 38 lines · Alexander Potapenko

Quoted 18 lines · Alexander Potapenko

Quoted 17 lines · Joonsoo Kim

Quoted 9 lines

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.

Okay.

Quoted 8 lines

Quoted 8 lines

There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).
I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

Quoted 2 lines

I re-think the page owner case and it also may not need refcount. For now, just moving this stuff to /lib would be helpful for other future user.

I agree this code may need to be moved to /lib someday, but I wouldn't hurry with that.
Right now it is quite KASAN-specific, and it's unclear yet whether anyone else is going to use it.
I suggest we keep it in mm/kasan for now, and factor the common parts into /lib when the need arises.

Quoted 2 lines

BTW, is there any performance number? I guess that it could affect the performance.

I've compared the performance of KASAN with SLAB allocator on a small synthetic benchmark in two modes: with stack depot enabled and with kasan_save_stack() unconditionally returning 0.
In the former case 8% more time was spent in the kernel than in the latter case.

Quoted 4 lines

If I am not mistaking, for SLUB allocator the bookkeeping (enabled with the slub_debug=UZ boot options) take only 1.5 time, so the difference is worth looking into (at least before we switch SLUB to stack depot).

I've made additional measurements.
Previously I had been using a userspace benchmark that created and destroyed pipes in a loop
(https://github.com/google/sanitizers/blob/master/address-sanitizer/kernel_buildbot/slave/bench_pipes.c).

Now I've made a kernel module that allocated and deallocated memory chunks of different sizes in a loop.
There were two modes of operation:
1) all the allocations were made from the same function, therefore all allocation/deallocation stacks were similar and there always was a hit in the stackdepot hashtable
2) The allocations were made from 2^16 different stacks.

Quoted 2 lines

In the first case SLAB+stackdepot turned out to be 13% faster than SLUB+slub_debug, in the second SLAB was 11% faster.

I don't know what version of kernel you tested but, until recently, slub_debug=UZ has a side effect not to using fastpath of SLUB. So, comparison between them isn't appropriate. Today's linux-next branch would have some improvements on this area so use it to compare them.

Quoted 3 lines

Note that in both cases and for both allocators most of the time (more than 90%) was spent in the x86 stack unwinder, which is common for both approaches.

If more than 90% time is spent in stack unwinder which is common for both cases, how something is better than the other by 13%?

Quoted 8 lines

Yet another observation regarding stackdepot: under a heavy load (running Trinity for a hour, 101M allocations) the depot saturates at around 20K records with the hashtable miss rate of 0.02%. That said, I still cannot justify the results of the userspace benchmark, but the slowdown of the stackdepot approach for SLAB sounds acceptable, especially given the memory gain compared to SLUB bookkeeping (which requires 128 bytes per memory allocation) and the fact we'll be dealing with the fast path most of the time.

In fact, I don't have much concern about performance because saving memory has enough merit to be merged. Anyway, it looks acceptable even for performance.

Quoted 2 lines

It will certainly be nice to compare SLUB+slub_debug to SLUB+stackdepot once we start switching SLUB to stackdepot.

Okay.

Thanks.

Quoted 38 lines · Alexander Potapenko

Quoted 18 lines · Alexander Potapenko

Quoted 17 lines · Joonsoo Kim

Quoted 9 lines

Hello,

Quoted 4 lines · Alexander Potapenko

Stack depot will allow KASAN store allocation/deallocation stack traces for memory chunks. The stack traces are stored in a hash table and referenced by handles which reside in the kasan_alloc_meta and kasan_free_meta structures in the allocated memory chunks.

Quoted 4 lines

Looks really nice!

Could it be more generalized to be used by other feature that need to store stack trace such as tracepoint or page owner?

Certainly yes, but see below.

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

If it could be, there is one more requirement.
I understand the fact that entry is never removed from depot makes things very simpler, but, for general usecases, it's better to use reference count
and allow to remove. Is it possible?

For our use case reference counting is not really necessary, and it would introduce unwanted contention.

Okay.

Quoted 8 lines

Quoted 8 lines

There are two possible options, each having its advantages and drawbacks: we can let the clients store the refcounters directly in their stacks (more universal, but harder to use for the clients), or keep the counters in the depot but add an API that does not change them (easier for the clients, but potentially error-prone).
I'd say it's better to actually find at least one more user for the stack depot in order to understand the requirements, and refactor the code after that.

Quoted 2 lines

I re-think the page owner case and it also may not need refcount. For now, just moving this stuff to /lib would be helpful for other future user.

I agree this code may need to be moved to /lib someday, but I wouldn't hurry with that.
Right now it is quite KASAN-specific, and it's unclear yet whether anyone else is going to use it.
I suggest we keep it in mm/kasan for now, and factor the common parts into /lib when the need arises.

Quoted 2 lines

BTW, is there any performance number? I guess that it could affect the performance.

I've compared the performance of KASAN with SLAB allocator on a small synthetic benchmark in two modes: with stack depot enabled and with kasan_save_stack() unconditionally returning 0.
In the former case 8% more time was spent in the kernel than in the latter case.

If I am not mistaking, for SLUB allocator the bookkeeping (enabled with the slub_debug=UZ boot options) take only 1.5 time, so the difference is worth looking into (at least before we switch SLUB to stack depot).

Quarantine isolates freed objects in a separate queue. The objects are returned to the allocator later, which helps to detect use-after-free errors.

Freed objects are first added to per-cpu quarantine queues. When a cache is destroyed or memory shrinking is requested, the objects are moved into the global quarantine queue. Whenever a kmalloc call allows memory reclaiming, the oldest objects are popped out of the global queue until the total size of objects in quarantine is less than 3/4 of the maximum quarantine size (which is a fraction of installed physical memory).

Right now quarantine support is only enabled in SLAB allocator. Unification of KASAN features in SLAB and SLUB will be done later.

This patch is based on the "mm: kasan: quarantine" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 include/linux/kasan.h |  30 ++++--
 lib/test_kasan.c      |  29 ++++++
 mm/kasan/Makefile     |   2 +-
 mm/kasan/kasan.c      |  68 +++++++++++-
 mm/kasan/kasan.h      |  11 +-
 mm/kasan/quarantine.c | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/kasan/report.c     |   3 +-
 mm/mempool.c          |   7 +-
 mm/page_alloc.c       |   2 +-
 mm/slab.c             |  12 ++-
 mm/slab.h             |   4 +
 mm/slab_common.c      |   2 +
 mm/slub.c             |   4 +-
 13 files changed, 435 insertions(+), 23 deletions(-)

mm/kasan/kasan.c +7 -0

+bool kasan_slab_free(struct kmem_cache *cache, void *object)
+{
+#ifdef CONFIG_SLAB
+	/* RCU slabs could be legally used after free within the RCU period */
+	if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
+		return false;
+

mm/kasan/kasan.c +18 -0

+			kasan_poison_slab_free(cache, object);
+			return true;
+		case KASAN_STATE_QUARANTINE:
+		case KASAN_STATE_FREE:
+			pr_err("Double free");
+			dump_stack();
+			break;
+		default:
+			break;
+		}
+	}
+	return false;
+#else
+	kasan_poison_slab_free(cache, object);
+	return false;
+#endif
+}
+

mm/kasan/quarantine.c new file +28 -0

+void quarantine_reduce(void)
+{
+	size_t new_quarantine_size;
+	unsigned long flags;
+	struct qlist to_free = QLIST_INIT;
+	size_t size_to_free = 0;
+	void **last;
+
+	if (likely(ACCESS_ONCE(global_quarantine.bytes) <=
+		   smp_load_acquire(&quarantine_size)))
+		return;
+
+	spin_lock_irqsave(&quarantine_lock, flags);
+
+	/* Update quarantine size in case of hotplug. Allocate a fraction of
+	 * the installed memory to quarantine minus per-cpu queue limits.
+	 */
+	new_quarantine_size = (ACCESS_ONCE(totalram_pages) << PAGE_SHIFT) /
+		QUARANTINE_FRACTION;
+	new_quarantine_size -= QUARANTINE_PERCPU_SIZE * num_online_cpus();
+	smp_store_release(&quarantine_size, new_quarantine_size);
+
+	last = global_quarantine.head;
+	while (last) {
+		struct kmem_cache *cache = qlink_to_cache(last);
+
+		size_to_free += cache->size;
+		if (!*last || size_to_free >

mm/kasan/quarantine.c new file +37 -0

+
+static inline void qlist_move_cache(struct qlist *from,
+				   struct qlist *to,
+				   struct kmem_cache *cache)
+{
+	void ***prev;
+
+	if (unlikely(empty_qlist(from)))
+		return;
+
+	prev = &from->head;
+	while (*prev) {
+		void **qlink = *prev;
+		struct kmem_cache *obj_cache = qlink_to_cache(qlink);
+
+		if (obj_cache == cache) {
+			if (unlikely(from->tail == qlink))
+				from->tail = (void **) prev;
+			*prev = (void **) *qlink;
+			from->bytes -= cache->size;
+			qlist_put(to, qlink, cache->size);
+		} else
+			prev = (void ***) *prev;
+	}
+}
+
+static void per_cpu_remove_cache(void *arg)
+{
+	struct kmem_cache *cache = arg;
+	struct qlist to_free = QLIST_INIT;
+	struct qlist *q;
+	unsigned long flags;
+
+	local_irq_save(flags);
+	q = this_cpu_ptr(&cpu_quarantine);
+	qlist_move_cache(q, &to_free, cache);
+	local_irq_restore(flags);

mm/kasan/quarantine.c new file +7 -0

+
+	spin_lock_irqsave(&quarantine_lock, flags);
+	qlist_move_cache(&global_quarantine, &to_free, cache);
+	spin_unlock_irqrestore(&quarantine_lock, flags);
+
+	qlist_free_all(&to_free, cache);
+}

mm/kasan/report.c +2 -1

index 6c4afcd..a4dca25 100644
@@ -148,7 +148,8 @@ static void print_object(struct kmem_cache *cache, void *object)
 		print_track(&alloc_info->track);
 		break;
 	case KASAN_STATE_FREE:
-		pr_err("Object freed, allocated with size %u bytes\n",
+	case KASAN_STATE_QUARANTINE:
+		pr_err("Object freed, allocated with size %lu bytes\n",
 		       alloc_info->alloc_size);
 		free_info = get_free_info(cache, object);
 		pr_err("Allocation:\n");

mm/mempool.c +4 -3

index b47c8a7..4beeeef 100644
@@ -105,11 +105,12 @@ static inline void poison_element(mempool_t *pool, void *element)
 static void kasan_poison_element(mempool_t *pool, void *element)
 {
 	if (pool->alloc == mempool_alloc_slab)
-		kasan_slab_free(pool->pool_data, element);
+		kasan_poison_slab_free(pool->pool_data, element);
 	if (pool->alloc == mempool_kmalloc)
-		kasan_kfree(element);
+		kasan_poison_kfree(element);
 	if (pool->alloc == mempool_alloc_pages)
-		kasan_free_pages(element, (unsigned long)pool->pool_data);
+		kasan_poison_free_pages(element,
+					(unsigned long)pool->pool_data);
 }
 
 static void kasan_unpoison_element(mempool_t *pool, void *element, gfp_t flags)

mm/page_alloc.c +1 -1

index 63358d9..4f65587 100644
@@ -980,7 +980,7 @@ static bool free_pages_prepare(struct page *page, unsigned int order)
 
 	trace_mm_page_free(page, order);
 	kmemcheck_free_shadow(page, order);
-	kasan_free_pages(page, order);
+	kasan_poison_free_pages(page, order);
 
 	if (PageAnon(page))
 		page->mapping = NULL;

mm/slab.c +1 -0

index 0ec7aa3..e2fac67 100644
@@ -3374,9 +3374,19 @@ free_done:
 static inline void __cache_free(struct kmem_cache *cachep, void *objp,
 				unsigned long caller)
 {
+#ifdef CONFIG_KASAN

Quoted 11 lines · Alexander Potapenko

Quarantine isolates freed objects in a separate queue. The objects are returned to the allocator later, which helps to detect use-after-free errors.

Freed objects are first added to per-cpu quarantine queues. When a cache is destroyed or memory shrinking is requested, the objects are moved into the global quarantine queue. Whenever a kmalloc call allows memory reclaiming, the oldest objects are popped out of the global queue until the total size of objects in quarantine is less than 3/4 of the maximum quarantine size (which is a fraction of installed physical memory).

Just wondering why not using time based approach rather than size based one. In heavy load condition, how much time do the object stay in quarantine?

Quoted 24 lines

Right now quarantine support is only enabled in SLAB allocator. Unification of KASAN features in SLAB and SLUB will be done later.

This patch is based on the "mm: kasan: quarantine" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 include/linux/kasan.h |  30 ++++--
 lib/test_kasan.c      |  29 ++++++
 mm/kasan/Makefile     |   2 +-
 mm/kasan/kasan.c      |  68 +++++++++++-
 mm/kasan/kasan.h      |  11 +-
 mm/kasan/quarantine.c | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/kasan/report.c     |   3 +-
 mm/mempool.c          |   7 +-
 mm/page_alloc.c       |   2 +-
 mm/slab.c             |  12 ++-
 mm/slab.h             |   4 +
 mm/slab_common.c      |   2 +
 mm/slub.c             |   4 +-
 13 files changed, 435 insertions(+), 23 deletions(-)

...

Quoted 7 lines

mm/kasan/kasan.c +7 -0

+bool kasan_slab_free(struct kmem_cache *cache, void *object)
+{
+#ifdef CONFIG_SLAB
+     /* RCU slabs could be legally used after free within the RCU period */
+     if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
+             return false;
+

mm/kasan/kasan.c void kasan_slab_free(struct kmem_cache *cache, void *object) · line 509

Quoted 10 lines

mm/kasan/kasan.c +10 -0

+     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);

quarantine_put() can be called regardless of SLAB_DESTROY_BY_RCU, although it's not much meaningful without poisoning. But, I have an idea to poison object on SLAB_DESTROY_BY_RCU cache.

quarantine_put() moves per cpu list to global queue when list size reaches QUARANTINE_PERCPU_SIZE. If we call synchronize_rcu() at that time, after then, we can poison objects. With appropriate size setup, it would not be intrusive.

Quoted 1 line

+ set_track(&free_info->track, GFP_NOWAIT);

set_track() can be called regardless of SLAB_DESTROY_BY_RCU.

Quoted 19 lines

mm/kasan/kasan.c +18 -0

+                     kasan_poison_slab_free(cache, object);
+                     return true;
+             case KASAN_STATE_QUARANTINE:
+             case KASAN_STATE_FREE:
+                     pr_err("Double free");
+                     dump_stack();
+                     break;
+             default:
+                     break;
+             }
+     }
+     return false;
+#else
+     kasan_poison_slab_free(cache, object);
+     return false;
+#endif
+}
+

...

Quoted 33 lines

mm/kasan/quarantine.c new file +33 -0

+void quarantine_reduce(void)
+{
+     size_t new_quarantine_size;
+     unsigned long flags;
+     struct qlist to_free = QLIST_INIT;
+     size_t size_to_free = 0;
+     void **last;
+
+     if (likely(ACCESS_ONCE(global_quarantine.bytes) <=
+                smp_load_acquire(&quarantine_size)))
+             return;
+
+     spin_lock_irqsave(&quarantine_lock, flags);
+
+     /* Update quarantine size in case of hotplug. Allocate a fraction of
+      * the installed memory to quarantine minus per-cpu queue limits.
+      */
+     new_quarantine_size = (ACCESS_ONCE(totalram_pages) << PAGE_SHIFT) /
+             QUARANTINE_FRACTION;
+     new_quarantine_size -= QUARANTINE_PERCPU_SIZE * num_online_cpus();
+     smp_store_release(&quarantine_size, new_quarantine_size);
+
+     last = global_quarantine.head;
+     while (last) {
+             struct kmem_cache *cache = qlink_to_cache(last);
+
+             size_to_free += cache->size;
+             if (!*last || size_to_free >
+                 global_quarantine.bytes - QUARANTINE_LOW_SIZE)
+                     break;
+             last = (void **) *last;
+     }
+     qlist_move(&global_quarantine, last, &to_free, size_to_free);

mm/kasan/quarantine.c line 230

Quoted 5 lines

mm/kasan/quarantine.c new file +5 -0

+
+     spin_unlock_irqrestore(&quarantine_lock, flags);
+
+     qlist_free_all(&to_free, NULL);
+}

Isn't it better to call quarantine_reduce() in shrink_slab()? It will help to maximize quarantine time.

Quoted 42 lines

mm/kasan/quarantine.c new file +41 -0

+
+static inline void qlist_move_cache(struct qlist *from,
+                                struct qlist *to,
+                                struct kmem_cache *cache)
+{
+     void ***prev;
+
+     if (unlikely(empty_qlist(from)))
+             return;
+
+     prev = &from->head;
+     while (*prev) {
+             void **qlink = *prev;
+             struct kmem_cache *obj_cache = qlink_to_cache(qlink);
+
+             if (obj_cache == cache) {
+                     if (unlikely(from->tail == qlink))
+                             from->tail = (void **) prev;
+                     *prev = (void **) *qlink;
+                     from->bytes -= cache->size;
+                     qlist_put(to, qlink, cache->size);
+             } else
+                     prev = (void ***) *prev;
+     }
+}
+
+static void per_cpu_remove_cache(void *arg)
+{
+     struct kmem_cache *cache = arg;
+     struct qlist to_free = QLIST_INIT;
+     struct qlist *q;
+     unsigned long flags;
+
+     local_irq_save(flags);
+     q = this_cpu_ptr(&cpu_quarantine);
+     qlist_move_cache(q, &to_free, cache);
+     local_irq_restore(flags);
+
+     qlist_free_all(&to_free, cache);
+}
+

mm/kasan/quarantine.c line 277

Quoted 6 lines

mm/kasan/quarantine.c new file +6 -0

+void quarantine_remove_cache(struct kmem_cache *cache)
+{
+     unsigned long flags;
+     struct qlist to_free = QLIST_INIT;
+
+     on_each_cpu(per_cpu_remove_cache, cache, 0);

Should be called with wait = 1.

Quoted 70 lines

mm/kasan/quarantine.c new file +7 -0

+
+     spin_lock_irqsave(&quarantine_lock, flags);
+     qlist_move_cache(&global_quarantine, &to_free, cache);
+     spin_unlock_irqrestore(&quarantine_lock, flags);
+
+     qlist_free_all(&to_free, cache);
+}

mm/kasan/report.c +2 -1

index 6c4afcd..a4dca25 100644
@@ -148,7 +148,8 @@ static void print_object(struct kmem_cache *cache, void *object)
              print_track(&alloc_info->track);
              break;
      case KASAN_STATE_FREE:
-             pr_err("Object freed, allocated with size %u bytes\n",
+     case KASAN_STATE_QUARANTINE:
+             pr_err("Object freed, allocated with size %lu bytes\n",
                     alloc_info->alloc_size);
              free_info = get_free_info(cache, object);
              pr_err("Allocation:\n");

mm/mempool.c +4 -3

index b47c8a7..4beeeef 100644
@@ -105,11 +105,12 @@ static inline void poison_element(mempool_t *pool, void *element)
 static void kasan_poison_element(mempool_t *pool, void *element)
 {
      if (pool->alloc == mempool_alloc_slab)
-             kasan_slab_free(pool->pool_data, element);
+             kasan_poison_slab_free(pool->pool_data, element);
      if (pool->alloc == mempool_kmalloc)
-             kasan_kfree(element);
+             kasan_poison_kfree(element);
      if (pool->alloc == mempool_alloc_pages)
-             kasan_free_pages(element, (unsigned long)pool->pool_data);
+             kasan_poison_free_pages(element,
+                                     (unsigned long)pool->pool_data);
 }
 
 static void kasan_unpoison_element(mempool_t *pool, void *element, gfp_t flags)

mm/page_alloc.c +1 -1

index 63358d9..4f65587 100644
@@ -980,7 +980,7 @@ static bool free_pages_prepare(struct page *page, unsigned int order)
 
      trace_mm_page_free(page, order);
      kmemcheck_free_shadow(page, order);
-     kasan_free_pages(page, order);
+     kasan_poison_free_pages(page, order);
 
      if (PageAnon(page))
              page->mapping = NULL;

mm/slab.c +8 -0

index 0ec7aa3..e2fac67 100644
@@ -3374,9 +3374,19 @@ free_done:
 static inline void __cache_free(struct kmem_cache *cachep, void *objp,
                              unsigned long caller)
 {
+#ifdef CONFIG_KASAN
+     if (!kasan_slab_free(cachep, objp))
+             /* The object has been put into the quarantine, don't touch it
+              * for now.
+              */
+             nokasan_free(cachep, objp, caller);
+}
+

mm/slab.c free_done: · line 3387

Quoted 3 lines

mm/slab.c +3 -0

+void nokasan_free(struct kmem_cache *cachep, void *objp, unsigned long caller)
+{
+#endif

It looks not good to me.
Converting __cache_free() to ____cache_free() and making __cache_free() call ____cache_free() if (!kasan_slab_free()) looks better to me and less error-prone.

Thanks.

Quoted 66 lines · Alexander Potapenko

Quoted 11 lines

Quarantine isolates freed objects in a separate queue. The objects are returned to the allocator later, which helps to detect use-after-free errors.

Freed objects are first added to per-cpu quarantine queues. When a cache is destroyed or memory shrinking is requested, the objects are moved into the global quarantine queue. Whenever a kmalloc call allows memory reclaiming, the oldest objects are popped out of the global queue until the total size of objects in quarantine is less than 3/4 of the maximum quarantine size (which is a fraction of installed physical memory).

Just wondering why not using time based approach rather than size based one. In heavy load condition, how much time do the object stay in quarantine?

Quoted 24 lines

Right now quarantine support is only enabled in SLAB allocator. Unification of KASAN features in SLAB and SLUB will be done later.

This patch is based on the "mm: kasan: quarantine" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 include/linux/kasan.h |  30 ++++--
 lib/test_kasan.c      |  29 ++++++
 mm/kasan/Makefile     |   2 +-
 mm/kasan/kasan.c      |  68 +++++++++++-
 mm/kasan/kasan.h      |  11 +-
 mm/kasan/quarantine.c | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/kasan/report.c     |   3 +-
 mm/mempool.c          |   7 +-
 mm/page_alloc.c       |   2 +-
 mm/slab.c             |  12 ++-
 mm/slab.h             |   4 +
 mm/slab_common.c      |   2 +
 mm/slub.c             |   4 +-
 13 files changed, 435 insertions(+), 23 deletions(-)

...

Quoted 7 lines

mm/kasan/kasan.c +7 -0

+bool kasan_slab_free(struct kmem_cache *cache, void *object)
+{
+#ifdef CONFIG_SLAB
+     /* RCU slabs could be legally used after free within the RCU period */
+     if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
+             return false;
+

mm/kasan/kasan.c void kasan_slab_free(struct kmem_cache *cache, void *object) · line 509

Quoted 10 lines

mm/kasan/kasan.c +10 -0

+     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);

quarantine_put() can be called regardless of SLAB_DESTROY_BY_RCU, although it's not much meaningful without poisoning. But, I have an idea to poison object on SLAB_DESTROY_BY_RCU cache.

Quoted 5 lines

quarantine_put() moves per cpu list to global queue when list size reaches QUARANTINE_PERCPU_SIZE. If we call synchronize_rcu() at that time, after then, we can poison objects. With appropriate size setup, it would not be intrusive.

Won't this slow the quarantine down unpredictably (e.g. in the case there're no RCU slabs in quarantine we'll still be waiting for synchronize_rcu())?

Yet this is something worth looking into. Do you want RCU to be handled in this patch set?

Quoted 3 lines

Quoted 1 line

+ set_track(&free_info->track, GFP_NOWAIT);

set_track() can be called regardless of SLAB_DESTROY_BY_RCU.

Agreed, I can fix that if we decide to handle RCU in this patch (otherwise it will lead to confusion).

Quoted 55 lines

Quoted 19 lines

mm/kasan/kasan.c +18 -0

+                     kasan_poison_slab_free(cache, object);
+                     return true;
+             case KASAN_STATE_QUARANTINE:
+             case KASAN_STATE_FREE:
+                     pr_err("Double free");
+                     dump_stack();
+                     break;
+             default:
+                     break;
+             }
+     }
+     return false;
+#else
+     kasan_poison_slab_free(cache, object);
+     return false;
+#endif
+}
+

...

Quoted 33 lines

mm/kasan/quarantine.c new file +33 -0

+void quarantine_reduce(void)
+{
+     size_t new_quarantine_size;
+     unsigned long flags;
+     struct qlist to_free = QLIST_INIT;
+     size_t size_to_free = 0;
+     void **last;
+
+     if (likely(ACCESS_ONCE(global_quarantine.bytes) <=
+                smp_load_acquire(&quarantine_size)))
+             return;
+
+     spin_lock_irqsave(&quarantine_lock, flags);
+
+     /* Update quarantine size in case of hotplug. Allocate a fraction of
+      * the installed memory to quarantine minus per-cpu queue limits.
+      */
+     new_quarantine_size = (ACCESS_ONCE(totalram_pages) << PAGE_SHIFT) /
+             QUARANTINE_FRACTION;
+     new_quarantine_size -= QUARANTINE_PERCPU_SIZE * num_online_cpus();
+     smp_store_release(&quarantine_size, new_quarantine_size);
+
+     last = global_quarantine.head;
+     while (last) {
+             struct kmem_cache *cache = qlink_to_cache(last);
+
+             size_to_free += cache->size;
+             if (!*last || size_to_free >
+                 global_quarantine.bytes - QUARANTINE_LOW_SIZE)
+                     break;
+             last = (void **) *last;
+     }
+     qlist_move(&global_quarantine, last, &to_free, size_to_free);

Quoted 8 lines

mm/kasan/quarantine.c line 230

Quoted 5 lines

mm/kasan/quarantine.c new file +5 -0

+
+     spin_unlock_irqrestore(&quarantine_lock, flags);
+
+     qlist_free_all(&to_free, NULL);
+}

Isn't it better to call quarantine_reduce() in shrink_slab()? It will help to maximize quarantine time.

This is true, however if we don't call quarantine_reduce() from kmalloc()/kfree() the size of the quarantine will be unpredictable. There's a tradeoff between efficiency and space here, and at least in some cases we may want to trade efficiency for space.

2016-02-18 23:06 GMT+09:00 Alexander Potapenko <[email protected]>:

Quoted 67 lines · Joonsoo Kim

Quoted 66 lines · Alexander Potapenko

Quoted 11 lines

Quarantine isolates freed objects in a separate queue. The objects are returned to the allocator later, which helps to detect use-after-free errors.

Freed objects are first added to per-cpu quarantine queues. When a cache is destroyed or memory shrinking is requested, the objects are moved into the global quarantine queue. Whenever a kmalloc call allows memory reclaiming, the oldest objects are popped out of the global queue until the total size of objects in quarantine is less than 3/4 of the maximum quarantine size (which is a fraction of installed physical memory).

Just wondering why not using time based approach rather than size based one. In heavy load condition, how much time do the object stay in quarantine?

Quoted 24 lines

Right now quarantine support is only enabled in SLAB allocator. Unification of KASAN features in SLAB and SLUB will be done later.

This patch is based on the "mm: kasan: quarantine" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 include/linux/kasan.h |  30 ++++--
 lib/test_kasan.c      |  29 ++++++
 mm/kasan/Makefile     |   2 +-
 mm/kasan/kasan.c      |  68 +++++++++++-
 mm/kasan/kasan.h      |  11 +-
 mm/kasan/quarantine.c | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/kasan/report.c     |   3 +-
 mm/mempool.c          |   7 +-
 mm/page_alloc.c       |   2 +-
 mm/slab.c             |  12 ++-
 mm/slab.h             |   4 +
 mm/slab_common.c      |   2 +
 mm/slub.c             |   4 +-
 13 files changed, 435 insertions(+), 23 deletions(-)

...

Quoted 7 lines

mm/kasan/kasan.c +7 -0

+bool kasan_slab_free(struct kmem_cache *cache, void *object)
+{
+#ifdef CONFIG_SLAB
+     /* RCU slabs could be legally used after free within the RCU period */
+     if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
+             return false;
+

mm/kasan/kasan.c void kasan_slab_free(struct kmem_cache *cache, void *object) · line 509

Quoted 10 lines

mm/kasan/kasan.c +10 -0

+     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);

quarantine_put() can be called regardless of SLAB_DESTROY_BY_RCU, although it's not much meaningful without poisoning. But, I have an idea to poison object on SLAB_DESTROY_BY_RCU cache.

Quoted 8 lines

Quoted 5 lines

quarantine_put() moves per cpu list to global queue when list size reaches QUARANTINE_PERCPU_SIZE. If we call synchronize_rcu() at that time, after then, we can poison objects. With appropriate size setup, it would not be intrusive.

Won't this slow the quarantine down unpredictably (e.g. in the case there're no RCU slabs in quarantine we'll still be waiting for synchronize_rcu())?

It could be handled by introducing one cpu variable.

Quoted 2 lines

Yet this is something worth looking into. Do you want RCU to be handled in this patch set?

No. It would be future work.

Quoted 69 lines

Quoted 3 lines

Quoted 1 line

+ set_track(&free_info->track, GFP_NOWAIT);

set_track() can be called regardless of SLAB_DESTROY_BY_RCU.

Agreed, I can fix that if we decide to handle RCU in this patch (otherwise it will lead to confusion).

Quoted 55 lines

Quoted 19 lines

mm/kasan/kasan.c +18 -0

+                     kasan_poison_slab_free(cache, object);
+                     return true;
+             case KASAN_STATE_QUARANTINE:
+             case KASAN_STATE_FREE:
+                     pr_err("Double free");
+                     dump_stack();
+                     break;
+             default:
+                     break;
+             }
+     }
+     return false;
+#else
+     kasan_poison_slab_free(cache, object);
+     return false;
+#endif
+}
+

...

Quoted 33 lines

mm/kasan/quarantine.c new file +33 -0

+void quarantine_reduce(void)
+{
+     size_t new_quarantine_size;
+     unsigned long flags;
+     struct qlist to_free = QLIST_INIT;
+     size_t size_to_free = 0;
+     void **last;
+
+     if (likely(ACCESS_ONCE(global_quarantine.bytes) <=
+                smp_load_acquire(&quarantine_size)))
+             return;
+
+     spin_lock_irqsave(&quarantine_lock, flags);
+
+     /* Update quarantine size in case of hotplug. Allocate a fraction of
+      * the installed memory to quarantine minus per-cpu queue limits.
+      */
+     new_quarantine_size = (ACCESS_ONCE(totalram_pages) << PAGE_SHIFT) /
+             QUARANTINE_FRACTION;
+     new_quarantine_size -= QUARANTINE_PERCPU_SIZE * num_online_cpus();
+     smp_store_release(&quarantine_size, new_quarantine_size);
+
+     last = global_quarantine.head;
+     while (last) {
+             struct kmem_cache *cache = qlink_to_cache(last);
+
+             size_to_free += cache->size;
+             if (!*last || size_to_free >
+                 global_quarantine.bytes - QUARANTINE_LOW_SIZE)
+                     break;
+             last = (void **) *last;
+     }
+     qlist_move(&global_quarantine, last, &to_free, size_to_free);

Quoted 8 lines

mm/kasan/quarantine.c line 230

Quoted 5 lines

mm/kasan/quarantine.c new file +5 -0

+
+     spin_unlock_irqrestore(&quarantine_lock, flags);
+
+     qlist_free_all(&to_free, NULL);
+}

Isn't it better to call quarantine_reduce() in shrink_slab()? It will help to maximize quarantine time.

Quoted 4 lines

This is true, however if we don't call quarantine_reduce() from kmalloc()/kfree() the size of the quarantine will be unpredictable. There's a tradeoff between efficiency and space here, and at least in some cases we may want to trade efficiency for space.

size of the quarantine doesn't matter unless there is memory pressure. If memory pressure, shrink_slab() would be called and we can reduce size of quarantine. However, I don't think this is show stopper. We can do it when needed.

No, this does not work. We've tried.
The problem is fragmentation. When all memory is occupied by slab, it's already too late to reclaim memory. Free objects are randomly scattered over memory, so if you have just 1% of live objects, the chances are that you won't be able to reclaim any single page.

Quoted 158 lines · Joonsoo Kim

2016-02-18 23:06 GMT+09:00 Alexander Potapenko <[email protected]>:

Quoted 67 lines · Joonsoo Kim

Quoted 66 lines · Alexander Potapenko

Quoted 11 lines

Quarantine isolates freed objects in a separate queue. The objects are returned to the allocator later, which helps to detect use-after-free errors.

Freed objects are first added to per-cpu quarantine queues. When a cache is destroyed or memory shrinking is requested, the objects are moved into the global quarantine queue. Whenever a kmalloc call allows memory reclaiming, the oldest objects are popped out of the global queue until the total size of objects in quarantine is less than 3/4 of the maximum quarantine size (which is a fraction of installed physical memory).

Just wondering why not using time based approach rather than size based one. In heavy load condition, how much time do the object stay in quarantine?

Quoted 24 lines

Right now quarantine support is only enabled in SLAB allocator. Unification of KASAN features in SLAB and SLUB will be done later.

This patch is based on the "mm: kasan: quarantine" patch originally prepared by Dmitry Chernenkov.

Signed-off-by Alexander Potapenko <[email protected]>

---
 include/linux/kasan.h |  30 ++++--
 lib/test_kasan.c      |  29 ++++++
 mm/kasan/Makefile     |   2 +-
 mm/kasan/kasan.c      |  68 +++++++++++-
 mm/kasan/kasan.h      |  11 +-
 mm/kasan/quarantine.c | 284 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/kasan/report.c     |   3 +-
 mm/mempool.c          |   7 +-
 mm/page_alloc.c       |   2 +-
 mm/slab.c             |  12 ++-
 mm/slab.h             |   4 +
 mm/slab_common.c      |   2 +
 mm/slub.c             |   4 +-
 13 files changed, 435 insertions(+), 23 deletions(-)

...

Quoted 7 lines

mm/kasan/kasan.c +7 -0

+bool kasan_slab_free(struct kmem_cache *cache, void *object)
+{
+#ifdef CONFIG_SLAB
+     /* RCU slabs could be legally used after free within the RCU period */
+     if (unlikely(cache->flags & SLAB_DESTROY_BY_RCU))
+             return false;
+

mm/kasan/kasan.c void kasan_slab_free(struct kmem_cache *cache, void *object) · line 509

Quoted 10 lines

mm/kasan/kasan.c +10 -0

+     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);

quarantine_put() can be called regardless of SLAB_DESTROY_BY_RCU, although it's not much meaningful without poisoning. But, I have an idea to poison object on SLAB_DESTROY_BY_RCU cache.

Quoted 8 lines

Quoted 5 lines

quarantine_put() moves per cpu list to global queue when list size reaches QUARANTINE_PERCPU_SIZE. If we call synchronize_rcu() at that time, after then, we can poison objects. With appropriate size setup, it would not be intrusive.

Won't this slow the quarantine down unpredictably (e.g. in the case there're no RCU slabs in quarantine we'll still be waiting for synchronize_rcu())?

It could be handled by introducing one cpu variable.

Quoted 2 lines

Yet this is something worth looking into. Do you want RCU to be handled in this patch set?

No. It would be future work.

Quoted 69 lines

Quoted 3 lines

Quoted 1 line

+ set_track(&free_info->track, GFP_NOWAIT);

set_track() can be called regardless of SLAB_DESTROY_BY_RCU.

Agreed, I can fix that if we decide to handle RCU in this patch (otherwise it will lead to confusion).

Quoted 55 lines

Quoted 19 lines

mm/kasan/kasan.c +18 -0

+                     kasan_poison_slab_free(cache, object);
+                     return true;
+             case KASAN_STATE_QUARANTINE:
+             case KASAN_STATE_FREE:
+                     pr_err("Double free");
+                     dump_stack();
+                     break;
+             default:
+                     break;
+             }
+     }
+     return false;
+#else
+     kasan_poison_slab_free(cache, object);
+     return false;
+#endif
+}
+

...

Quoted 33 lines

mm/kasan/quarantine.c new file +33 -0

+void quarantine_reduce(void)
+{
+     size_t new_quarantine_size;
+     unsigned long flags;
+     struct qlist to_free = QLIST_INIT;
+     size_t size_to_free = 0;
+     void **last;
+
+     if (likely(ACCESS_ONCE(global_quarantine.bytes) <=
+                smp_load_acquire(&quarantine_size)))
+             return;
+
+     spin_lock_irqsave(&quarantine_lock, flags);
+
+     /* Update quarantine size in case of hotplug. Allocate a fraction of
+      * the installed memory to quarantine minus per-cpu queue limits.
+      */
+     new_quarantine_size = (ACCESS_ONCE(totalram_pages) << PAGE_SHIFT) /
+             QUARANTINE_FRACTION;
+     new_quarantine_size -= QUARANTINE_PERCPU_SIZE * num_online_cpus();
+     smp_store_release(&quarantine_size, new_quarantine_size);
+
+     last = global_quarantine.head;
+     while (last) {
+             struct kmem_cache *cache = qlink_to_cache(last);
+
+             size_to_free += cache->size;
+             if (!*last || size_to_free >
+                 global_quarantine.bytes - QUARANTINE_LOW_SIZE)
+                     break;
+             last = (void **) *last;
+     }
+     qlist_move(&global_quarantine, last, &to_free, size_to_free);

Quoted 8 lines

mm/kasan/quarantine.c line 230

Quoted 5 lines

mm/kasan/quarantine.c new file +5 -0

+
+     spin_unlock_irqrestore(&quarantine_lock, flags);
+
+     qlist_free_all(&to_free, NULL);
+}

Isn't it better to call quarantine_reduce() in shrink_slab()? It will help to maximize quarantine time.

Quoted 4 lines

This is true, however if we don't call quarantine_reduce() from kmalloc()/kfree() the size of the quarantine will be unpredictable. There's a tradeoff between efficiency and space here, and at least in some cases we may want to trade efficiency for space.

Quoted 4 lines

size of the quarantine doesn't matter unless there is memory pressure. If memory pressure, shrink_slab() would be called and we can reduce size of quarantine. However, I don't think this is show stopper. We can do it when needed.