Re: [PATCH v9] mm: kasan: Initial memory quarantine implementation

[Alexey Klimov]

Hi Alexander,

On Wed, May 11, 2016 at 6:18 PM, Alexander Potapenko <glider@xxxxxxxxxx> wrote:
> 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).
>
> As long as an object remains in the quarantine, KASAN is able to report
> accesses to it, so the chance of reporting a use-after-free is increased.
> Once the object leaves quarantine, the allocator may reuse it, in which
> case the object is unpoisoned and KASAN can't detect incorrect accesses
> to it.
>
> 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. A number of improvements have been
> suggested by Andrey Ryabinin.
>
> Signed-off-by: Alexander Potapenko <glider@xxxxxxxxxx>
> ---
> v2: - added copyright comments
>     - per request from Joonsoo Kim made __cache_free() more straightforward
>     - added comments for smp_load_acquire()/smp_store_release()
>
> v3: - incorporate changes introduced by the "mm, kasan: SLAB support" patch
>
> v4: - fix kbuild compile-time error (missing ___cache_free() declaration)
>       and a warning (wrong format specifier)
>
> v6: - extended the patch description
>     - dropped the unused qlist_remove() function
>
> v9: - incorporate the fixes by Andrey Ryabinin:
>       * Fix comment styles,
>       * Get rid of some ifdefs
>       * Revert needless functions renames in quarantine patch
>       * Remove needless local_irq_save()/restore() in
>         per_cpu_remove_cache()
>       * Add new 'struct qlist_node' instead of 'void **' types. This makes
>         code a bit more redable.
>     - remove the non-deterministic quarantine test
>     - dropped smp_load_acquire()/smp_store_release()
> ---
>  include/linux/kasan.h |  13 ++-
>  mm/kasan/Makefile     |   1 +
>  mm/kasan/kasan.c      |  57 ++++++++--
>  mm/kasan/kasan.h      |  21 +++-
>  mm/kasan/quarantine.c | 291 ++++++++++++++++++++++++++++++++++++++++++++++++++
>  mm/kasan/report.c     |   1 +
>  mm/mempool.c          |   2 +-
>  mm/slab.c             |  12 ++-
>  mm/slab.h             |   2 +
>  mm/slab_common.c      |   2 +
>  10 files changed, 387 insertions(+), 15 deletions(-)
>  create mode 100644 mm/kasan/quarantine.c
>
> diff --git a/include/linux/kasan.h b/include/linux/kasan.h
> index 737371b..611927f 100644
> --- a/include/linux/kasan.h
> +++ b/include/linux/kasan.h
> @@ -50,6 +50,8 @@ void kasan_free_pages(struct page *page, unsigned int order);
>

[...]

> diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c
> new file mode 100644
> index 0000000..4973505
> --- /dev/null
> +++ b/mm/kasan/quarantine.c
> @@ -0,0 +1,291 @@
> +/*
> + * KASAN quarantine.
> + *
> + * Author: Alexander Potapenko <glider@xxxxxxxxxx>
> + * 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>
> +
> +#include "../slab.h"
> +#include "kasan.h"
> +
> +/* Data structure and operations for quarantine queues. */
> +
> +/*
> + * Each queue is a signle-linked list, which also stores the total size of
> + * objects inside of it.
> + */
> +struct qlist_head {
> +       struct qlist_node *head;
> +       struct qlist_node *tail;
> +       size_t bytes;
> +};
> +
> +#define QLIST_INIT { NULL, NULL, 0 }
> +
> +static bool qlist_empty(struct qlist_head *q)
> +{
> +       return !q->head;
> +}
> +
> +static void qlist_init(struct qlist_head *q)
> +{
> +       q->head = q->tail = NULL;
> +       q->bytes = 0;
> +}
> +
> +static void qlist_put(struct qlist_head *q, struct qlist_node *qlink,
> +               size_t size)
> +{
> +       if (unlikely(qlist_empty(q)))
> +               q->head = qlink;
> +       else
> +               q->tail->next = qlink;
> +       q->tail = qlink;
> +       qlink->next = NULL;
> +       q->bytes += size;
> +}
> +
> +static void qlist_move_all(struct qlist_head *from, struct qlist_head *to)
> +{
> +       if (unlikely(qlist_empty(from)))
> +               return;
> +
> +       if (qlist_empty(to)) {
> +               *to = *from;
> +               qlist_init(from);
> +               return;
> +       }
> +
> +       to->tail->next = from->head;
> +       to->tail = from->tail;
> +       to->bytes += from->bytes;
> +
> +       qlist_init(from);
> +}
> +
> +static void qlist_move(struct qlist_head *from, struct qlist_node *last,
> +               struct qlist_head *to, size_t size)
> +{
> +       if (unlikely(last == from->tail)) {
> +               qlist_move_all(from, to);
> +               return;
> +       }
> +       if (qlist_empty(to))
> +               to->head = from->head;
> +       else
> +               to->tail->next = from->head;
> +       to->tail = last;
> +       from->head = last->next;
> +       last->next = NULL;
> +       from->bytes -= size;
> +       to->bytes += size;
> +}

I see conversation with Andrew in previous emails about moving this
code above into generic library facility but I don't anything is going
on here. I also feel like this belongs to lib/*.
Do I miss something or did you decide to do it later?

[...]

-- 
Best regards, Klimov Alexey