• Marco Elver's avatar
    kfence: limit currently covered allocations when pool nearly full · 08f6b106
    Marco Elver authored
    One of KFENCE's main design principles is that with increasing uptime,
    allocation coverage increases sufficiently to detect previously
    undetected bugs.
    
    We have observed that frequent long-lived allocations of the same source
    (e.g.  pagecache) tend to permanently fill up the KFENCE pool with
    increasing system uptime, thus breaking the above requirement.  The
    workaround thus far had been increasing the sample interval and/or
    increasing the KFENCE pool size, but is no reliable solution.
    
    To ensure diverse coverage of allocations, limit currently covered
    allocations of the same source once pool utilization reaches 75%
    (configurable via `kfence.skip_covered_thresh`) or above.  The effect is
    retaining reasonable allocation coverage when the pool is close to full.
    
    A side-effect is that this also limits frequent long-lived allocations
    of the same source filling up the pool permanently.
    
    Uniqueness of an allocation for coverage purposes is based on its
    (partial) allocation stack trace (the source).  A Counting Bloom filter
    is used to check if an allocation is covered; if the allocation is
    currently covered, the allocation is skipped by KFENCE.
    
    Testing was done using:
    
    	(a) a synthetic workload that performs frequent long-lived
    	    allocations (default config values; sample_interval=1;
    	    num_objects=63), and
    
    	(b) normal desktop workloads on an otherwise idle machine where
    	    the problem was first reported after a few days of uptime
    	    (default config values).
    
    In both test cases the sampled allocation rate no longer drops to zero
    at any point.  In the case of (b) we observe (after 2 days uptime) 15%
    unique allocations in the pool, 77% pool utilization, with 20% "skipped
    allocations (covered)".
    
    [elver@google.com: simplify and just use hash_32(), use more random stack_hash_seed]
      Link: https://lkml.kernel.org/r/YU3MRGaCaJiYht5g@elver.google.com
    [elver@google.com: fix 32 bit]
    
    Link: https://lkml.kernel.org/r/20210923104803.2620285-4-elver@google.comSigned-off-by: default avatarMarco Elver <elver@google.com>
    Reviewed-by: default avatarDmitry Vyukov <dvyukov@google.com>
    Acked-by: default avatarAlexander Potapenko <glider@google.com>
    Cc: Aleksandr Nogikh <nogikh@google.com>
    Cc: Jann Horn <jannh@google.com>
    Cc: Taras Madan <tarasmadan@google.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    08f6b106
core.c 31 KB