SLAB support for KASAN

2016-03-09 14:05 GMT+03:00 Alexander Potapenko <[email protected]>:

mm/kasan/kasan.h struct kasan_global { · line 68

Quoted 2 lines

mm/kasan/kasan.h +2 -0

+struct kasan_track {
+       u64 cpu : 6;                    /* for NR_CPUS = 64 */

What about NR_CPUS > 64 ?

Quoted 4 lines

mm/kasan/kasan.h +4 -0

+       u64 pid : 16;                   /* 65536 processes */
+       u64 when : 42;                  /* ~140 years */
+};
+

Quoted 5 lines · Andrey Ryabinin

2016-03-09 14:05 GMT+03:00 Alexander Potapenko <[email protected]>:

Quoted 2 lines

mm/kasan/kasan.h +2 -0

+struct kasan_track {
+       u64 cpu : 6;                    /* for NR_CPUS = 64 */

Quoted 1 line

What about NR_CPUS > 64 ?

After a discussion with Dmitry we've decided to drop |cpu| and |when| at all, as they do not actually help debugging.
This way we'll make kasan_track only 8 bytes (4 bytes for PID, 4 bytes for stack handle).
Then the meta structures will be smaller and have nice alignment:

struct kasan_track {
        u32 pid;
        depot_stack_handle_t stack;
};

struct kasan_alloc_meta {
        struct kasan_track track;
        u32 state : 2;  /* enum kasan_state */
        u32 alloc_size : 30;
        u32 reserved;  /* we can use it to store an additional stack

handle, e.g. for debugging RCU */
};

struct kasan_free_meta {
        /* This field is used while the object is in the quarantine.
         * Otherwise it might be used for the allocator freelist.
         */
        void **quarantine_link;
        struct kasan_track track;
};

Quoted 4 lines

mm/kasan/kasan.h struct kasan_global { · line 72

Quoted 4 lines

mm/kasan/kasan.h +4 -0

+       u64 pid : 16;                   /* 65536 processes */
+       u64 when : 42;                  /* ~140 years */
+};
+

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

Implement the stack depot and provide CONFIG_STACKDEPOT. 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.

IRQ stack traces are cut below the IRQ entry point to avoid unnecessary duplication.

Right now stackdepot support is only enabled in SLAB allocator. Once KASAN features in SLAB are on par with those in SLUB we can switch SLUB to stackdepot as well, thus removing the dependency on SLUB stack bookkeeping, which wastes a lot of memory.

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

include/linux/stackdepot.h new file +14 -0

@@ -0,0 +1,32 @@
+/*
+ * A generic stack depot implementation
+ *
+ * Author: Alexander Potapenko <[email protected]>
+ * Copyright (C) 2016 Google, Inc.
+ *
+ * Based on code by Dmitry Chernenkov.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,

include/linux/stackdepot.h new file +7 -0

+struct stack_trace;
+
+depot_stack_handle depot_save_stack(struct stack_trace *trace, gfp_t flags);
+
+void depot_fetch_stack(depot_stack_handle handle, struct stack_trace *trace);
+
+#endif

lib/Kconfig +3 -0

index ee38a3f..8a60a53 100644
@@ -543,4 +543,7 @@ config ARCH_HAS_PMEM_API
 config ARCH_HAS_MMIO_FLUSH
 	bool
 
+config STACKDEPOT
+  bool
+
 endmenu

lib/Kconfig.kasan +0 -0

index 0e4d2b3..468316d 100644

Quoted 14 lines · On Wed, 9 Mar 2016 12:05:46 +0100 Alexander Potapenko <[email protected]>…

Implement the stack depot and provide CONFIG_STACKDEPOT. 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.

IRQ stack traces are cut below the IRQ entry point to avoid unnecessary duplication.

Right now stackdepot support is only enabled in SLAB allocator. Once KASAN features in SLAB are on par with those in SLUB we can switch SLUB to stackdepot as well, thus removing the dependency on SLUB stack bookkeeping, which wastes a lot of memory.

Quoted 3 lines

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

Have you identified other potential clients for the stackdepot code?

Quoted 22 lines

include/linux/stackdepot.h new file +19 -0

@@ -0,0 +1,32 @@
+/*
+ * A generic stack depot implementation
+ *
+ * Author: Alexander Potapenko <[email protected]>
+ * Copyright (C) 2016 Google, Inc.
+ *
+ * Based on code by Dmitry Chernenkov.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ */

include/linux/stackdepot.h line 24

Quoted 5 lines

include/linux/stackdepot.h new file +5 -0

+
+#ifndef _LINUX_STACKDEPOT_H
+#define _LINUX_STACKDEPOT_H
+
+typedef u32 depot_stack_handle;

I'll rename this to depot_stack_handle_t, which is a pretty strong kernel convention.

Quoted 25 lines

include/linux/stackdepot.h new file +7 -0

+struct stack_trace;
+
+depot_stack_handle depot_save_stack(struct stack_trace *trace, gfp_t flags);
+
+void depot_fetch_stack(depot_stack_handle handle, struct stack_trace *trace);
+
+#endif

lib/Kconfig +3 -0

index ee38a3f..8a60a53 100644
@@ -543,4 +543,7 @@ config ARCH_HAS_PMEM_API
 config ARCH_HAS_MMIO_FLUSH
      bool
 
+config STACKDEPOT
+  bool
+
 endmenu

lib/Kconfig.kasan +0 -0

index 0e4d2b3..468316d 100644
@@ -7,6 +7,7 @@ config KASAN
      bool "KASan: runtime memory debugger"

lib/Kconfig.kasan config KASAN · line 13

Quoted 6 lines

lib/Kconfig.kasan +1 -0

      depends on SLUB_DEBUG || (SLAB && !DEBUG_SLAB)
      select CONSTRUCTORS
+  select STACKDEPOT if SLAB
      help
        Enables kernel address sanitizer - runtime memory debugger,
        designed to find out-of-bounds accesses and use-after-free bugs.

Something weird happened to the Kconfig whitespace. I'll fix that.

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.

...

mm/kasan/kasan.c +3 -0

+void kasan_cache_shrink(struct kmem_cache *cache)
+{
+#ifdef CONFIG_SLAB

mm/kasan/kasan.c +0 -0

 	if (unlikely(object == NULL))
 		return;
 

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

@@ -0,0 +1,306 @@
+/*
+ * KASAN quarantine.
+ *
+ * Author: Alexander Potapenko <[email protected]>
+ * Copyright (C) 2016 Google, Inc.
+ *
+ * Based on code by Dmitry Chernenkov.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ */
+
+#include <linux/gfp.h>
+#include <linux/hash.h>
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <linux/percpu.h>
+#include <linux/printk.h>
+#include <linux/shrinker.h>

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

+ * objects inside of it.
+ */
+struct qlist {
+	void **head;

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

+static inline void qlist_put(struct qlist *q, void **qlink, size_t size)
+{
+	if (unlikely(empty_qlist(q)))
+		q->head = qlink;
+	else
+		*q->tail = qlink;
+	q->tail = qlink;
+	*qlink = NULL;
+	q->bytes += size;
+}
+
+static inline void **qlist_remove(struct qlist *q, void ***prev,
+				 size_t size)
+{
+	void **qlink = *prev;
+
+	*prev = *qlink;
+	if (q->tail == qlink) {
+		if (q->head == qlink)
+			q->tail = NULL;
+		else
+			q->tail = (void **)prev;
+	}
+	q->bytes -= size;
+
+	return qlink;
+}
+
+static inline void qlist_move_all(struct qlist *from, struct qlist *to)
+{
+	if (unlikely(empty_qlist(from)))
+		return;
+
+	if (empty_qlist(to)) {
+		*to = *from;
+		init_qlist(from);
+		return;
+	}
+
+	*to->tail = from->head;
+	to->tail = from->tail;
+	to->bytes += from->bytes;
+
+	init_qlist(from);
+}
+
+static inline void qlist_move(struct qlist *from, void **last, struct qlist *to,
+			  size_t size)
+{
+	if (unlikely(last == from->tail)) {
+		qlist_move_all(from, to);
+		return;
+	}

...

Quoted 3 lines · On Wed, 9 Mar 2016 12:05:48 +0100 Alexander Potapenko <[email protected]>…

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

I'd like to see some more details on precisely *how* the parking of objects in the qlists helps "detect use-after-free"?

Quoted 11 lines

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.

Quoted 3 lines

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

qlists look awfully like list_heads. Some explanation of why a new container mechanism was needed would be good to see - wht are existing ones unsuitable?

Quoted 4 lines

...

mm/kasan/kasan.c void kasan_cache_create(struct kmem_cache *cache, size_t *size, · line 383

Quoted 13 lines

mm/kasan/kasan.c +13 -0

+void kasan_cache_shrink(struct kmem_cache *cache)
+{
+#ifdef CONFIG_SLAB
+     quarantine_remove_cache(cache);
+#endif
+}
+
+void kasan_cache_destroy(struct kmem_cache *cache)
+{
+#ifdef CONFIG_SLAB
+     quarantine_remove_cache(cache);
+#endif
+}

We could avoid th4ese ifdefs in the usual way: an empty version of quarantine_remove_cache() if CONFIG_SLAB=n.

Quoted 7 lines

...

mm/kasan/kasan.c +0 -0

@@ -493,6 +532,11 @@ void kasan_kmalloc(struct kmem_cache *cache, const void *object, size_t size,
      unsigned long redzone_start;
      unsigned long redzone_end;
 

mm/kasan/kasan.c void kasan_kmalloc(struct kmem_cache *cache, const void *object, size_t size, · line 538

Quoted 4 lines

mm/kasan/kasan.c +4 -0

+#ifdef CONFIG_SLAB
+     if (flags & __GFP_RECLAIM)
+             quarantine_reduce();
+#endif

Here also.

Quoted 37 lines

mm/kasan/kasan.c +0 -0

      if (unlikely(object == NULL))
              return;
 

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

@@ -0,0 +1,306 @@
+/*
+ * KASAN quarantine.
+ *
+ * Author: Alexander Potapenko <[email protected]>
+ * Copyright (C) 2016 Google, Inc.
+ *
+ * Based on code by Dmitry Chernenkov.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ */
+
+#include <linux/gfp.h>
+#include <linux/hash.h>
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <linux/percpu.h>
+#include <linux/printk.h>
+#include <linux/shrinker.h>
+#include <linux/slab.h>
+#include <linux/string.h>
+#include <linux/types.h>
+

mm/kasan/quarantine.c line 36

Quoted 6 lines

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

+#include "../slab.h"
+#include "kasan.h"
+
+/* Data structure and operations for quarantine queues. */
+
+/* Each queue is a signled-linked list, which also stores the total size of

tpyo

Quoted 5 lines

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

+ * objects inside of it.
+ */
+struct qlist {
+     void **head;

mm/kasan/quarantine.c line 50

Quoted 10 lines

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

+     void **tail;
+     size_t bytes;
+};
+
+#define QLIST_INIT { NULL, NULL, 0 }
+
+static inline bool empty_qlist(struct qlist *q)
+{
+     return !q->head;
+}

Should be "qlist_empty()".

mm/kasan/quarantine.c line 56

Quoted 6 lines

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

+static inline void init_qlist(struct qlist *q)
+{
+     q->head = q->tail = NULL;
+     q->bytes = 0;
+}

"qlist_init()"

Quoted 59 lines

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

+static inline void qlist_put(struct qlist *q, void **qlink, size_t size)
+{
+     if (unlikely(empty_qlist(q)))
+             q->head = qlink;
+     else
+             *q->tail = qlink;
+     q->tail = qlink;
+     *qlink = NULL;
+     q->bytes += size;
+}
+
+static inline void **qlist_remove(struct qlist *q, void ***prev,
+                              size_t size)
+{
+     void **qlink = *prev;
+
+     *prev = *qlink;
+     if (q->tail == qlink) {
+             if (q->head == qlink)
+                     q->tail = NULL;
+             else
+                     q->tail = (void **)prev;
+     }
+     q->bytes -= size;
+
+     return qlink;
+}
+
+static inline void qlist_move_all(struct qlist *from, struct qlist *to)
+{
+     if (unlikely(empty_qlist(from)))
+             return;
+
+     if (empty_qlist(to)) {
+             *to = *from;
+             init_qlist(from);
+             return;
+     }
+
+     *to->tail = from->head;
+     to->tail = from->tail;
+     to->bytes += from->bytes;
+
+     init_qlist(from);
+}
+
+static inline void qlist_move(struct qlist *from, void **last, struct qlist *to,
+                       size_t size)
+{
+     if (unlikely(last == from->tail)) {
+             qlist_move_all(from, to);
+             return;
+     }
+     if (empty_qlist(to))
+             to->head = from->head;
+     else
+             *to->tail = from->head;
+     to->tail = last;

mm/kasan/quarantine.c line 120

Quoted 5 lines

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

+     from->head = *last;
+     *last = NULL;
+     from->bytes -= size;
+     to->bytes += size;
+}

The above code is a candidate for hoisting out into a generic library facility, so let's impement it that way (ie: get the naming right).

All the inlining looks excessive, and the compiler will defeat it anyway if it thinks that is best.

Quoted 3 lines

...

Quoted 8 lines · Andrew Morton

Quoted 3 lines · On Wed, 9 Mar 2016 12:05:48 +0100 Alexander Potapenko <[email protected]>…

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

I'd like to see some more details on precisely *how* the parking of objects in the qlists helps "detect use-after-free"?

When the object is freed, its state changes from KASAN_STATE_ALLOC to KASAN_STATE_QUARANTINE. The object is poisoned and put into quarantine instead of being returned to the allocator, therefore every subsequent access to that object triggers a KASAN error, and the error handler is able to say where the object has been allocated and deallocated. When it's time for the object to leave quarantine, its state becomes KASAN_STATE_FREE and it's returned to the allocator. From now on the allocator may reuse it for another allocation.
Before that happens, it's still possible to detect a use-after free on that object (it retains the allocation/deallocation stacks). When the allocator reuses this object, the shadow is unpoisoned and old allocation/deallocation stacks are wiped. Therefore a use of this object, even an incorrect one, won't trigger ASan warning. Without the quarantine, it's not guaranteed that the objects aren't reused immediately, that's why the probability of catching a use-after-free is lower than with quarantine in place.

Quoted 4 lines

Quoted 1 line

+}

We could avoid th4ese ifdefs in the usual way: an empty version of quarantine_remove_cache() if CONFIG_SLAB=n.

Yes, agreed.
I am sorry, I don't fully understand the review process now, when you've pulled the patches into mm-tree.
Shall I send the new patch series version, as before, or is anything else needs to be done?
Do I need to rebase against mm- or linux-next? Thanks in advance.

Quoted 9 lines · On Thu, 10 Mar 2016 14:50:56 +0100 Alexander Potapenko <[email protected]>…

Quoted 8 lines · Andrew Morton

Quoted 3 lines · On Wed, 9 Mar 2016 12:05:48 +0100 Alexander Potapenko <[email protected]>…

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

I'd like to see some more details on precisely *how* the parking of objects in the qlists helps "detect use-after-free"?

Quoted 16 lines

When the object is freed, its state changes from KASAN_STATE_ALLOC to KASAN_STATE_QUARANTINE. The object is poisoned and put into quarantine instead of being returned to the allocator, therefore every subsequent access to that object triggers a KASAN error, and the error handler is able to say where the object has been allocated and deallocated. When it's time for the object to leave quarantine, its state becomes KASAN_STATE_FREE and it's returned to the allocator. From now on the allocator may reuse it for another allocation.
Before that happens, it's still possible to detect a use-after free on that object (it retains the allocation/deallocation stacks). When the allocator reuses this object, the shadow is unpoisoned and old allocation/deallocation stacks are wiped. Therefore a use of this object, even an incorrect one, won't trigger ASan warning. Without the quarantine, it's not guaranteed that the objects aren't reused immediately, that's why the probability of catching a use-after-free is lower than with quarantine in place.

I see, thanks. I'll slurp that into the changelog for posterity.

Quoted 10 lines

Quoted 4 lines

Quoted 1 line

+}

We could avoid th4ese ifdefs in the usual way: an empty version of quarantine_remove_cache() if CONFIG_SLAB=n.

Yes, agreed.
I am sorry, I don't fully understand the review process now, when you've pulled the patches into mm-tree.
Shall I send the new patch series version, as before, or is anything else needs to be done?
Do I need to rebase against mm- or linux-next? Thanks in advance.

I like to queue a delta patch so I and others can see what changed and also to keep track of who fixed what and why. It's a bit harsh on the reviewers to send them a slightly altered version of a 500 line patch which they've already read through.

Before sending the patch up to Linus I'll clump everything into a single patch and a lot of that history is somewhat lost.

Sending a replacement patch is often more convenient for the originator so that's fine - I'll turn the replacement into a delta locally and will review then queue that delta. Also a new revision of a patch has an altered changelog so I'll manually move that into the older original patch's changelog immediately.

IOW: either a new patch or a delta is fine.

Your patch is in linux-next now so a diff against -next will work OK.

Probably the easiest thing for you to do is to just alter the patch you have in-place and send out the new one. A "[v2" in the Subject: helps people keep track of things.

Quoted 8 lines · Andrew Morton

Quoted 3 lines · On Wed, 9 Mar 2016 12:05:48 +0100 Alexander Potapenko <[email protected]>…

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

I'd like to see some more details on precisely *how* the parking of objects in the qlists helps "detect use-after-free"?

When the object is freed, its state changes from KASAN_STATE_ALLOC to KASAN_STATE_QUARANTINE. The object is poisoned and put into quarantine instead of being returned to the allocator, therefore every subsequent access to that object triggers a KASAN error, and the error handler is able to say where the object has been allocated and deallocated. When it's time for the object to leave quarantine, its state becomes KASAN_STATE_FREE and it's returned to the allocator. From now on the allocator may reuse it for another allocation.
Before that happens, it's still possible to detect a use-after free on that object (it retains the allocation/deallocation stacks). When the allocator reuses this object, the shadow is unpoisoned and old allocation/deallocation stacks are wiped. Therefore a use of this object, even an incorrect one, won't trigger ASan warning. Without the quarantine, it's not guaranteed that the objects aren't reused immediately, that's why the probability of catching a use-after-free is lower than with quarantine in place.

Quoted 11 lines

Quoted 11 lines

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.

Quoted 7 lines

Quoted 3 lines

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

qlists look awfully like list_heads. Some explanation of why a new container mechanism was needed would be good to see - wht are existing ones unsuitable?

Most of the code in quarantine.c is actually the code that moves the queues around (merges them, frees a given portion of the quarantine, filters the elements belonging to a specific cache) and calculates the sizes. I don't think there're off-the-shelf solutions for this. qlist is a FIFO queue that keeps pointers to the head and the tail of a linked list. That's semantically different from list_head. There's include/linux/kfifo.h, but that also appears to be completely different.

Quoted 20 lines

Quoted 7 lines

...

mm/kasan/kasan.c +3 -0

+void kasan_cache_shrink(struct kmem_cache *cache)
+{
+#ifdef CONFIG_SLAB

mm/kasan/kasan.c void kasan_cache_create(struct kmem_cache *cache, size_t *size, · line 383

Quoted 10 lines

mm/kasan/kasan.c +10 -0

+     quarantine_remove_cache(cache);
+#endif
+}
+
+void kasan_cache_destroy(struct kmem_cache *cache)
+{
+#ifdef CONFIG_SLAB
+     quarantine_remove_cache(cache);
+#endif
+}

We could avoid th4ese ifdefs in the usual way: an empty version of quarantine_remove_cache() if CONFIG_SLAB=n.

Yes, agreed.
I am sorry, I don't fully understand the review process now, when you've pulled the patches into mm-tree.
Shall I send the new patch series version, as before, or is anything else needs to be done?
Do I need to rebase against mm- or linux-next? Thanks in advance.

Quoted 7 lines

Quoted 7 lines

...

mm/kasan/kasan.c +0 -0

@@ -493,6 +532,11 @@ void kasan_kmalloc(struct kmem_cache *cache, const void *object, size_t size,
      unsigned long redzone_start;
      unsigned long redzone_end;
 

Quoted 6 lines

mm/kasan/kasan.c void kasan_kmalloc(struct kmem_cache *cache, const void *object, size_t size, · line 538

Quoted 4 lines

mm/kasan/kasan.c +4 -0

+#ifdef CONFIG_SLAB
+     if (flags & __GFP_RECLAIM)
+             quarantine_reduce();
+#endif

Here also.

Ack.

Quoted 37 lines

Quoted 37 lines

mm/kasan/kasan.c +0 -0

      if (unlikely(object == NULL))
              return;
 

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

@@ -0,0 +1,306 @@
+/*
+ * KASAN quarantine.
+ *
+ * Author: Alexander Potapenko <[email protected]>
+ * Copyright (C) 2016 Google, Inc.
+ *
+ * Based on code by Dmitry Chernenkov.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ */
+
+#include <linux/gfp.h>
+#include <linux/hash.h>
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <linux/percpu.h>
+#include <linux/printk.h>
+#include <linux/shrinker.h>
+#include <linux/slab.h>
+#include <linux/string.h>
+#include <linux/types.h>
+

Quoted 8 lines

mm/kasan/quarantine.c line 36

Quoted 6 lines

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

+#include "../slab.h"
+#include "kasan.h"
+
+/* Data structure and operations for quarantine queues. */
+
+/* Each queue is a signled-linked list, which also stores the total size of

tpyo

Ack.

Quoted 17 lines

Quoted 5 lines

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

+ * objects inside of it.
+ */
+struct qlist {
+     void **head;

mm/kasan/quarantine.c line 50

Quoted 10 lines

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

+     void **tail;
+     size_t bytes;
+};
+
+#define QLIST_INIT { NULL, NULL, 0 }
+
+static inline bool empty_qlist(struct qlist *q)
+{
+     return !q->head;
+}

Should be "qlist_empty()".

Ack.

Quoted 8 lines

mm/kasan/quarantine.c line 56

Quoted 6 lines

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

+static inline void init_qlist(struct qlist *q)
+{
+     q->head = q->tail = NULL;
+     q->bytes = 0;
+}

"qlist_init()"

Ack.

Quoted 59 lines

Quoted 59 lines

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

+static inline void qlist_put(struct qlist *q, void **qlink, size_t size)
+{
+     if (unlikely(empty_qlist(q)))
+             q->head = qlink;
+     else
+             *q->tail = qlink;
+     q->tail = qlink;
+     *qlink = NULL;
+     q->bytes += size;
+}
+
+static inline void **qlist_remove(struct qlist *q, void ***prev,
+                              size_t size)
+{
+     void **qlink = *prev;
+
+     *prev = *qlink;
+     if (q->tail == qlink) {
+             if (q->head == qlink)
+                     q->tail = NULL;
+             else
+                     q->tail = (void **)prev;
+     }
+     q->bytes -= size;
+
+     return qlink;
+}
+
+static inline void qlist_move_all(struct qlist *from, struct qlist *to)
+{
+     if (unlikely(empty_qlist(from)))
+             return;
+
+     if (empty_qlist(to)) {
+             *to = *from;
+             init_qlist(from);
+             return;
+     }
+
+     *to->tail = from->head;
+     to->tail = from->tail;
+     to->bytes += from->bytes;
+
+     init_qlist(from);
+}
+
+static inline void qlist_move(struct qlist *from, void **last, struct qlist *to,
+                       size_t size)
+{
+     if (unlikely(last == from->tail)) {
+             qlist_move_all(from, to);
+             return;
+     }
+     if (empty_qlist(to))
+             to->head = from->head;
+     else
+             *to->tail = from->head;
+     to->tail = last;

Quoted 8 lines

mm/kasan/quarantine.c line 120

Quoted 5 lines

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

+     from->head = *last;
+     *last = NULL;
+     from->bytes -= size;
+     to->bytes += size;
+}

The above code is a candidate for hoisting out into a generic library facility, so let's impement it that way (ie: get the naming right).

Ack.

Quoted 2 lines

All the inlining looks excessive, and the compiler will defeat it anyway if it thinks that is best.

Ack.

Quoted 5 lines

Quoted 3 lines

...

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

This patch set implements SLAB support for KASAN

Unlike SLUB, SLAB doesn't store allocation/deallocation stacks for heap objects, therefore we reimplement this feature in mm/kasan/stackdepot.c. The intention is to ultimately switch SLUB to use this implementation as well, which will save a lot of memory (right now SLUB bloats each object by 256 bytes to store the allocation/deallocation stacks).

Also neither SLUB nor SLAB delay the reuse of freed memory chunks, which is necessary for better detection of use-after-free errors. We introduce memory quarantine (mm/kasan/quarantine.c), which allows delayed reuse of deallocated memory.

Alexander Potapenko (7):
kasan: Modify kmalloc_large_oob_right(), add
kmalloc_pagealloc_oob_right()
mm, kasan: SLAB support
mm, kasan: Added GFP flags to KASAN API
arch, ftrace: For KASAN put hard/soft IRQ entries into separate
sections
mm, kasan: Stackdepot implementation. Enable stackdepot for SLAB
kasan: Test fix: Warn if the UAF could not be detected in kmalloc_uaf2
mm: kasan: Initial memory quarantine implementation
---
v2: - merged two patches that touched kmalloc_large_oob_right
- moved stackdepot implementation to lib/
- moved IRQ definitions to include/linux/interrupt.h

v3: - minor description changes
- store deallocation info in the "mm, kasan: SLAB support" patch

v4: - fix kbuild error reports

v5: - SLAB allocator, stackdepot: adopted suggestions by Andrey Ryabinin
- IRQ: fixed kbuild warnings
---

 Documentation/kasan.txt              |   5 +-
 arch/arm/include/asm/exception.h     |   2 +-
 arch/arm/kernel/vmlinux.lds.S        |   1 +
 arch/arm64/include/asm/exception.h   |   2 +-
 arch/arm64/kernel/vmlinux.lds.S      |   1 +
 arch/blackfin/kernel/vmlinux.lds.S   |   1 +
 arch/c6x/kernel/vmlinux.lds.S        |   1 +
 arch/metag/kernel/vmlinux.lds.S      |   1 +
 arch/microblaze/kernel/vmlinux.lds.S |   1 +
 arch/mips/kernel/vmlinux.lds.S       |   1 +
 arch/nios2/kernel/vmlinux.lds.S      |   1 +
 arch/openrisc/kernel/vmlinux.lds.S   |   1 +
 arch/parisc/kernel/vmlinux.lds.S     |   1 +
 arch/powerpc/kernel/vmlinux.lds.S    |   1 +
 arch/s390/kernel/vmlinux.lds.S       |   1 +
 arch/sh/kernel/vmlinux.lds.S         |   1 +
 arch/sparc/kernel/vmlinux.lds.S      |   1 +
 arch/tile/kernel/vmlinux.lds.S       |   1 +
 arch/x86/kernel/Makefile             |   1 +
 arch/x86/kernel/vmlinux.lds.S        |   1 +
 include/asm-generic/vmlinux.lds.h    |  12 +-
 include/linux/ftrace.h               |  11 --
 include/linux/interrupt.h            |  20 +++
 include/linux/kasan.h                |  63 ++++++--
 include/linux/slab.h                 |  10 +-
 include/linux/slab_def.h             |  14 ++
 include/linux/slub_def.h             |  11 ++
 include/linux/stackdepot.h           |  32 ++++
 kernel/softirq.c                     |   2 +-
 kernel/trace/trace_functions_graph.c |   1 +
 lib/Kconfig                          |   3 +
 lib/Kconfig.kasan                    |   5 +-
 lib/Makefile                         |   3 +
 lib/stackdepot.c                     | 275 +++++++++++++++++++++++++++++++
 lib/test_kasan.c                     |  59 ++++++-
 mm/Makefile                          |   1 +
 mm/kasan/Makefile                    |   4 +
 mm/kasan/kasan.c                     | 221 +++++++++++++++++++++++--
 mm/kasan/kasan.h                     |  45 ++++++
 mm/kasan/quarantine.c                | 306 +++++++++++++++++++++++++++++++++++
 mm/kasan/report.c                    |  64 ++++++--
 mm/mempool.c                         |  23 +--
 mm/page_alloc.c                      |   2 +-
 mm/slab.c                            |  53 +++++-
 mm/slab.h                            |   4 +-
 mm/slab_common.c                     |   8 +-
 mm/slub.c                            |  19 +--
 47 files changed, 1205 insertions(+), 92 deletions(-)
 create mode 100644 include/linux/stackdepot.h
 create mode 100644 lib/stackdepot.c
 create mode 100644 mm/kasan/quarantine.c

--
2.7.0.rc3.207.g0ac5344

This patch set implements SLAB support for KASAN

Quoted 2 lines

This patch set implements SLAB support for KASAN

I'll queue all this up for some testing. I'm undecided about feeding it into 4.5 - it is very late. I'll be interested in advice from others on this...