Re: [PATCH v1 8/8] mm: kasan: Initial memory quarantine implementation

[Joonsoo Kim]

On Fri, Feb 19, 2016 at 10:19:48AM +0100, Dmitry Vyukov wrote:
> On Fri, Feb 19, 2016 at 3:11 AM, Joonsoo Kim <js1304@xxxxxxxxx> wrote:
> > 2016-02-18 23:06 GMT+09:00 Alexander Potapenko <glider@xxxxxxxxxx>:
> >> On Mon, Feb 1, 2016 at 3:47 AM, Joonsoo Kim <iamjoonsoo.kim@xxxxxxx> wrote:
> >>> On Wed, Jan 27, 2016 at 07:25:13PM +0100, Alexander Potapenko 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).
> >>>
> >>> 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?
> >>>
> >>>>
> >>>> 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 <glider@xxxxxxxxxx>
> >>>> ---
> >>>>  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(-)
> >>>>
> >>>
> >>> ...
> >>>
> >>>> +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;
> >>>> +
> >>>> +     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.
> >>>
> >> 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.
> >
> >> Yet this is something worth looking into. Do you want RCU to be
> >> handled in this patch set?
> >
> > No. It would be future work.
> >
> >>>> +                     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).
> >>
> >>>
> >>>> +                     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
> >>>> +}
> >>>> +
> >>>
> >>> ...
> >>>
> >>>> +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);
> >>>> +
> >>>> +     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.
> >
> > 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.

Okay. Now, I got it.

Thanks.