Date:	Thu, 10 Mar 2016 14:50:56 +0100
From:	Alexander Potapenko <glider@...gle.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Andrey Konovalov <adech.fo@...il.com>,
	Christoph Lameter <cl@...ux.com>,
	Dmitriy Vyukov <dvyukov@...gle.com>,
	Andrey Ryabinin <ryabinin.a.a@...il.com>,
	Steven Rostedt <rostedt@...dmis.org>,
	Joonsoo Kim <iamjoonsoo.kim@....com>,
	JoonSoo Kim <js1304@...il.com>,
	Kostya Serebryany <kcc@...gle.com>,
	kasan-dev <kasan-dev@...glegroups.com>,
	LKML <linux-kernel@...r.kernel.org>,
	Linux Memory Management List <linux-mm@...ck.org>
Subject: Re: [PATCH v5 7/7] mm: kasan: Initial memory quarantine implementation

On Wed, Mar 9, 2016 at 9:21 PM, Andrew Morton <akpm@...ux-foundation.org> wrote:
> On Wed,  9 Mar 2016 12:05:48 +0100 Alexander Potapenko <glider@...gle.com> 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.
>
> 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.

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

>
>>
>> ...
>>
>> +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.
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.
>>
>> ...
>>
>> @@ -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;
>>
>> +#ifdef CONFIG_SLAB
>> +     if (flags & __GFP_RECLAIM)
>> +             quarantine_reduce();
>> +#endif
>
> Here also.
Ack.
>
>>       if (unlikely(object == NULL))
>>               return;
>>
>> --- /dev/null
>> +++ b/mm/kasan/quarantine.c
>> @@ -0,0 +1,306 @@
>> +/*
>> + * KASAN quarantine.
>> + *
>> + * Author: Alexander Potapenko <glider@...gle.com>
>> + * 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 signled-linked list, which also stores the total size of
>
> tpyo
Ack.
>
>> + * objects inside of it.
>> + */
>> +struct qlist {
>> +     void **head;
>> +     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.
>
>> +static inline void init_qlist(struct qlist *q)
>> +{
>> +     q->head = q->tail = NULL;
>> +     q->bytes = 0;
>> +}
>
> "qlist_init()"
Ack.
>
>> +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;
>> +     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.
> All the inlining looks excessive, and the compiler will defeat it
> anyway if it thinks that is best.
Ack.
>>
>> ...
>>
>
>



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

Powered by blists - more mailing lists