From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-23.3 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, USER_IN_DEF_DKIM_WL autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 79B08C433F5 for ; Thu, 23 Sep 2021 11:19:06 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 58C3961211 for ; Thu, 23 Sep 2021 11:19:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240604AbhIWLUg (ORCPT ); Thu, 23 Sep 2021 07:20:36 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58968 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240493AbhIWLUc (ORCPT ); Thu, 23 Sep 2021 07:20:32 -0400 Received: from mail-ot1-x32f.google.com (mail-ot1-x32f.google.com [IPv6:2607:f8b0:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 22EC6C061574 for ; Thu, 23 Sep 2021 04:19:01 -0700 (PDT) Received: by mail-ot1-x32f.google.com with SMTP id 97-20020a9d006a000000b00545420bff9eso7994769ota.8 for ; Thu, 23 Sep 2021 04:19:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=s0cPQoIqCHpexQHN8I9O9O1s6hHQIW6w4g54hPahYMY=; b=qHGxCAn7jinjDDPHFQUDloEwU1harzzS5BJHKqqUmOVpa53v56pEb/snjXFueSJQlE WZMN1u9sh2uvDXUP6GghIdBZiXWYudbzoseo76XTZPLqCpV43T609NVrnbOG2TvqkL3q 2ror1gzZ3nnY+9tYAphSHWn9VISBGsoQ1v4B5cOf8ORGOMVxH6yzV/bG+JSV6aJJYMfu IiFptphYABB0gZfh4ALTeFjB6cqfEMggokaoTVU9JnKh2a1BO7yzqUi/ynFEeLTWs421 9ilYt0reMrZyY2GX9FYNFGB6/gFO4J+Q865FW4+S6qfbywnLuAqXws+KRr+XCocz9sjK s3UQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=s0cPQoIqCHpexQHN8I9O9O1s6hHQIW6w4g54hPahYMY=; b=wdnNPFdsYwMg9hba27InamVY0S9sulZjhG6ntECT57UQcywt808djljSSki64Rcs9N 5HHhsP4g3oWULWIuTCl9bObjPXbIq/bNcMRKGEBZ+PNbRIGdogy3GGANPbC66XHM1HqO dGQGeJgsMy66vp3EqdGanrkQEJ+LC5W2flivAwd/v7OJ+AJL/qw7DtS5wUC+GEY/uhb9 eL55xyfFHLAphGKwiTNmiMckOnKPDkKETBxQMnYc9KZqWg//Ey6kISpsQMpe+j9ILfgx JPQZU3bH1gl90I5p5PIQjtqPU520fSPLsRW5oRUCgOEYvgyzJua2YuH9SL6s4nsZ5p4c OGWw== X-Gm-Message-State: AOAM531NlLaksiNlNSyeDesYLvoaJjQviUUxWLLx9OoKCrcC5bAltDdo PJmgxNAyVBtvGbJ22jLTo7dACeX8Bgfn5xSuv9CKQg== X-Google-Smtp-Source: ABdhPJyV6Gq0lOamTxj0NtSjJE+CiMC+Gbio02ClpLQlVGav8QgwgW3aaEaPL3RpeERBg3iaBCWSk52uC09avgKBb/M= X-Received: by 2002:a9d:7244:: with SMTP id a4mr3878121otk.137.1632395940082; Thu, 23 Sep 2021 04:19:00 -0700 (PDT) MIME-Version: 1.0 References: <20210923104803.2620285-1-elver@google.com> <20210923104803.2620285-4-elver@google.com> In-Reply-To: <20210923104803.2620285-4-elver@google.com> From: Dmitry Vyukov Date: Thu, 23 Sep 2021 13:18:48 +0200 Message-ID: Subject: Re: [PATCH v3 4/5] kfence: limit currently covered allocations when pool nearly full To: Marco Elver Cc: Andrew Morton , Alexander Potapenko , Jann Horn , Aleksandr Nogikh , Taras Madan , linux-kernel@vger.kernel.org, linux-mm@kvack.org, kasan-dev@googlegroups.com Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, 23 Sept 2021 at 12:48, Marco Elver wrote: > > 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)". > > Signed-off-by: Marco Elver Reviewed-by: Dmitry Vyukov > --- > v3: > * Remove unneeded !alloc_stack_hash checks. > * Remove unneeded meta->alloc_stack_hash=0 in kfence_guarded_free(). > > v2: > * Switch to counting bloom filter to guarantee currently covered > allocations being skipped. > * Use a module param for skip_covered threshold. > * Use kfence pool address as hash entropy. > * Use filter_irq_stacks(). > --- > mm/kfence/core.c | 103 ++++++++++++++++++++++++++++++++++++++++++++- > mm/kfence/kfence.h | 2 + > 2 files changed, 103 insertions(+), 2 deletions(-) > > diff --git a/mm/kfence/core.c b/mm/kfence/core.c > index db01814f8ff0..58a0f6f1acc5 100644 > --- a/mm/kfence/core.c > +++ b/mm/kfence/core.c > @@ -11,11 +11,13 @@ > #include > #include > #include > +#include > #include > #include > #include > #include > #include > +#include > #include > #include > #include > @@ -82,6 +84,10 @@ static const struct kernel_param_ops sample_interval_param_ops = { > }; > module_param_cb(sample_interval, &sample_interval_param_ops, &kfence_sample_interval, 0600); > > +/* Pool usage% threshold when currently covered allocations are skipped. */ > +static unsigned long kfence_skip_covered_thresh __read_mostly = 75; > +module_param_named(skip_covered_thresh, kfence_skip_covered_thresh, ulong, 0644); > + > /* The pool of pages used for guard pages and objects. */ > char *__kfence_pool __ro_after_init; > EXPORT_SYMBOL(__kfence_pool); /* Export for test modules. */ > @@ -105,6 +111,25 @@ DEFINE_STATIC_KEY_FALSE(kfence_allocation_key); > /* Gates the allocation, ensuring only one succeeds in a given period. */ > atomic_t kfence_allocation_gate = ATOMIC_INIT(1); > > +/* > + * A Counting Bloom filter of allocation coverage: limits currently covered > + * allocations of the same source filling up the pool. > + * > + * Assuming a range of 15%-85% unique allocations in the pool at any point in > + * time, the below parameters provide a probablity of 0.02-0.33 for false > + * positive hits respectively: > + * > + * P(alloc_traces) = (1 - e^(-HNUM * (alloc_traces / SIZE)) ^ HNUM > + */ > +#define ALLOC_COVERED_HNUM 2 > +#define ALLOC_COVERED_SIZE (1 << (const_ilog2(CONFIG_KFENCE_NUM_OBJECTS) + 2)) > +#define ALLOC_COVERED_HNEXT(h) (1664525 * (h) + 1013904223) > +#define ALLOC_COVERED_MASK (ALLOC_COVERED_SIZE - 1) > +static atomic_t alloc_covered[ALLOC_COVERED_SIZE]; > + > +/* Stack depth used to determine uniqueness of an allocation. */ > +#define UNIQUE_ALLOC_STACK_DEPTH 8UL > + > /* Statistics counters for debugfs. */ > enum kfence_counter_id { > KFENCE_COUNTER_ALLOCATED, > @@ -114,6 +139,7 @@ enum kfence_counter_id { > KFENCE_COUNTER_BUGS, > KFENCE_COUNTER_SKIP_INCOMPAT, > KFENCE_COUNTER_SKIP_CAPACITY, > + KFENCE_COUNTER_SKIP_COVERED, > KFENCE_COUNTER_COUNT, > }; > static atomic_long_t counters[KFENCE_COUNTER_COUNT]; > @@ -125,11 +151,60 @@ static const char *const counter_names[] = { > [KFENCE_COUNTER_BUGS] = "total bugs", > [KFENCE_COUNTER_SKIP_INCOMPAT] = "skipped allocations (incompatible)", > [KFENCE_COUNTER_SKIP_CAPACITY] = "skipped allocations (capacity)", > + [KFENCE_COUNTER_SKIP_COVERED] = "skipped allocations (covered)", > }; > static_assert(ARRAY_SIZE(counter_names) == KFENCE_COUNTER_COUNT); > > /* === Internals ============================================================ */ > > +static inline bool should_skip_covered(void) > +{ > + unsigned long thresh = (CONFIG_KFENCE_NUM_OBJECTS * kfence_skip_covered_thresh) / 100; > + > + return atomic_long_read(&counters[KFENCE_COUNTER_ALLOCATED]) > thresh; > +} > + > +static u32 get_alloc_stack_hash(unsigned long *stack_entries, size_t num_entries) > +{ > + /* Some randomness across reboots / different machines. */ > + u32 seed = (u32)((unsigned long)__kfence_pool >> (BITS_PER_LONG - 32)); > + > + num_entries = min(num_entries, UNIQUE_ALLOC_STACK_DEPTH); > + num_entries = filter_irq_stacks(stack_entries, num_entries); > + return jhash(stack_entries, num_entries * sizeof(stack_entries[0]), seed); > +} > + > +/* > + * Adds (or subtracts) count @val for allocation stack trace hash > + * @alloc_stack_hash from Counting Bloom filter. > + */ > +static void alloc_covered_add(u32 alloc_stack_hash, int val) > +{ > + int i; > + > + for (i = 0; i < ALLOC_COVERED_HNUM; i++) { > + atomic_add(val, &alloc_covered[alloc_stack_hash & ALLOC_COVERED_MASK]); > + alloc_stack_hash = ALLOC_COVERED_HNEXT(alloc_stack_hash); > + } > +} > + > +/* > + * Returns true if the allocation stack trace hash @alloc_stack_hash is > + * currently contained (non-zero count) in Counting Bloom filter. > + */ > +static bool alloc_covered_contains(u32 alloc_stack_hash) > +{ > + int i; > + > + for (i = 0; i < ALLOC_COVERED_HNUM; i++) { > + if (!atomic_read(&alloc_covered[alloc_stack_hash & ALLOC_COVERED_MASK])) > + return false; > + alloc_stack_hash = ALLOC_COVERED_HNEXT(alloc_stack_hash); > + } > + > + return true; > +} > + > static bool kfence_protect(unsigned long addr) > { > return !KFENCE_WARN_ON(!kfence_protect_page(ALIGN_DOWN(addr, PAGE_SIZE), true)); > @@ -269,7 +344,8 @@ static __always_inline void for_each_canary(const struct kfence_metadata *meta, > } > > static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t gfp, > - unsigned long *stack_entries, size_t num_stack_entries) > + unsigned long *stack_entries, size_t num_stack_entries, > + u32 alloc_stack_hash) > { > struct kfence_metadata *meta = NULL; > unsigned long flags; > @@ -332,6 +408,8 @@ static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g > /* Pairs with READ_ONCE() in kfence_shutdown_cache(). */ > WRITE_ONCE(meta->cache, cache); > meta->size = size; > + meta->alloc_stack_hash = alloc_stack_hash; > + > for_each_canary(meta, set_canary_byte); > > /* Set required struct page fields. */ > @@ -344,6 +422,8 @@ static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g > > raw_spin_unlock_irqrestore(&meta->lock, flags); > > + alloc_covered_add(alloc_stack_hash, 1); > + > /* Memory initialization. */ > > /* > @@ -412,6 +492,8 @@ static void kfence_guarded_free(void *addr, struct kfence_metadata *meta, bool z > > raw_spin_unlock_irqrestore(&meta->lock, flags); > > + alloc_covered_add(meta->alloc_stack_hash, -1); > + > /* Protect to detect use-after-frees. */ > kfence_protect((unsigned long)addr); > > @@ -752,6 +834,7 @@ void *__kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags) > { > unsigned long stack_entries[KFENCE_STACK_DEPTH]; > size_t num_stack_entries; > + u32 alloc_stack_hash; > > /* > * Perform size check before switching kfence_allocation_gate, so that > @@ -799,7 +882,23 @@ void *__kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags) > > num_stack_entries = stack_trace_save(stack_entries, KFENCE_STACK_DEPTH, 0); > > - return kfence_guarded_alloc(s, size, flags, stack_entries, num_stack_entries); > + /* > + * Do expensive check for coverage of allocation in slow-path after > + * allocation_gate has already become non-zero, even though it might > + * mean not making any allocation within a given sample interval. > + * > + * This ensures reasonable allocation coverage when the pool is almost > + * full, including avoiding long-lived allocations of the same source > + * filling up the pool (e.g. pagecache allocations). > + */ > + alloc_stack_hash = get_alloc_stack_hash(stack_entries, num_stack_entries); > + if (should_skip_covered() && alloc_covered_contains(alloc_stack_hash)) { > + atomic_long_inc(&counters[KFENCE_COUNTER_SKIP_COVERED]); > + return NULL; > + } > + > + return kfence_guarded_alloc(s, size, flags, stack_entries, num_stack_entries, > + alloc_stack_hash); > } > > size_t kfence_ksize(const void *addr) > diff --git a/mm/kfence/kfence.h b/mm/kfence/kfence.h > index c1f23c61e5f9..2a2d5de9d379 100644 > --- a/mm/kfence/kfence.h > +++ b/mm/kfence/kfence.h > @@ -87,6 +87,8 @@ struct kfence_metadata { > /* Allocation and free stack information. */ > struct kfence_track alloc_track; > struct kfence_track free_track; > + /* For updating alloc_covered on frees. */ > + u32 alloc_stack_hash; > }; > > extern struct kfence_metadata kfence_metadata[CONFIG_KFENCE_NUM_OBJECTS]; > -- > 2.33.0.464.g1972c5931b-goog > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-23.3 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1B50CC433EF for ; Thu, 23 Sep 2021 11:19:03 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 97FE160EC0 for ; Thu, 23 Sep 2021 11:19:02 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org 97FE160EC0 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=google.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=kvack.org Received: by kanga.kvack.org (Postfix) id 202826B006C; Thu, 23 Sep 2021 07:19:02 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 164966B0071; Thu, 23 Sep 2021 07:19:02 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 02D496B0072; Thu, 23 Sep 2021 07:19:01 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0224.hostedemail.com [216.40.44.224]) by kanga.kvack.org (Postfix) with ESMTP id E6F046B006C for ; Thu, 23 Sep 2021 07:19:01 -0400 (EDT) Received: from smtpin39.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id A559E180373E0 for ; Thu, 23 Sep 2021 11:19:01 +0000 (UTC) X-FDA: 78618591282.39.1A2F280 Received: from mail-ot1-f45.google.com (mail-ot1-f45.google.com [209.85.210.45]) by imf03.hostedemail.com (Postfix) with ESMTP id 519C030000B0 for ; Thu, 23 Sep 2021 11:19:01 +0000 (UTC) Received: by mail-ot1-f45.google.com with SMTP id l16-20020a9d6a90000000b0053b71f7dc83so8005910otq.7 for ; Thu, 23 Sep 2021 04:19:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=s0cPQoIqCHpexQHN8I9O9O1s6hHQIW6w4g54hPahYMY=; b=qHGxCAn7jinjDDPHFQUDloEwU1harzzS5BJHKqqUmOVpa53v56pEb/snjXFueSJQlE WZMN1u9sh2uvDXUP6GghIdBZiXWYudbzoseo76XTZPLqCpV43T609NVrnbOG2TvqkL3q 2ror1gzZ3nnY+9tYAphSHWn9VISBGsoQ1v4B5cOf8ORGOMVxH6yzV/bG+JSV6aJJYMfu IiFptphYABB0gZfh4ALTeFjB6cqfEMggokaoTVU9JnKh2a1BO7yzqUi/ynFEeLTWs421 9ilYt0reMrZyY2GX9FYNFGB6/gFO4J+Q865FW4+S6qfbywnLuAqXws+KRr+XCocz9sjK s3UQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=s0cPQoIqCHpexQHN8I9O9O1s6hHQIW6w4g54hPahYMY=; b=d/J43I924zA1FFPg9s6BJx52Nj6Y2MS1KdIgIODvHdQ/4JAH8MhdkMjVEem4UBVqJ/ s2o+3U5F4TYvEL4DTya7amdvfEd+CYBBSNp/I3/jlRvb4RCRNiTmsZsjE3b08+zNpYEg 3im/QVBOoonZUNw3PzSothujIu4NiFzAlOtc8IvAK9duw4jmPXR6s5SPykx+Lwrb5yyR RDEbpCms/ngEEYSq902upOMude2Ga7PfW92S9sTJjwGIKYnGqXm4Jf086ETJXiAdUSQJ BEuhNzrnEfQhT4jIb4ZZxkG2t+rIo0mSDxCkbBiRbrU2H77ZJaEV/loM2YFwrSqfqbrF k2MQ== X-Gm-Message-State: AOAM5330cmK426zpQlVUgXwBc/dg4Mk81n0Et1GZIA2PIqwKHZqr0lBR XYCSO0lw6wb0N5Cj79GuIok4hXjDwQ3l5laEOikZaQ== X-Google-Smtp-Source: ABdhPJyV6Gq0lOamTxj0NtSjJE+CiMC+Gbio02ClpLQlVGav8QgwgW3aaEaPL3RpeERBg3iaBCWSk52uC09avgKBb/M= X-Received: by 2002:a9d:7244:: with SMTP id a4mr3878121otk.137.1632395940082; Thu, 23 Sep 2021 04:19:00 -0700 (PDT) MIME-Version: 1.0 References: <20210923104803.2620285-1-elver@google.com> <20210923104803.2620285-4-elver@google.com> In-Reply-To: <20210923104803.2620285-4-elver@google.com> From: Dmitry Vyukov Date: Thu, 23 Sep 2021 13:18:48 +0200 Message-ID: Subject: Re: [PATCH v3 4/5] kfence: limit currently covered allocations when pool nearly full To: Marco Elver Cc: Andrew Morton , Alexander Potapenko , Jann Horn , Aleksandr Nogikh , Taras Madan , linux-kernel@vger.kernel.org, linux-mm@kvack.org, kasan-dev@googlegroups.com Content-Type: text/plain; charset="UTF-8" X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 519C030000B0 X-Stat-Signature: 8byfx8day91pz7kafjwi9egdydg3ny3n Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=qHGxCAn7; spf=pass (imf03.hostedemail.com: domain of dvyukov@google.com designates 209.85.210.45 as permitted sender) smtp.mailfrom=dvyukov@google.com; dmarc=pass (policy=reject) header.from=google.com X-HE-Tag: 1632395941-330001 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Thu, 23 Sept 2021 at 12:48, Marco Elver wrote: > > 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)". > > Signed-off-by: Marco Elver Reviewed-by: Dmitry Vyukov > --- > v3: > * Remove unneeded !alloc_stack_hash checks. > * Remove unneeded meta->alloc_stack_hash=0 in kfence_guarded_free(). > > v2: > * Switch to counting bloom filter to guarantee currently covered > allocations being skipped. > * Use a module param for skip_covered threshold. > * Use kfence pool address as hash entropy. > * Use filter_irq_stacks(). > --- > mm/kfence/core.c | 103 ++++++++++++++++++++++++++++++++++++++++++++- > mm/kfence/kfence.h | 2 + > 2 files changed, 103 insertions(+), 2 deletions(-) > > diff --git a/mm/kfence/core.c b/mm/kfence/core.c > index db01814f8ff0..58a0f6f1acc5 100644 > --- a/mm/kfence/core.c > +++ b/mm/kfence/core.c > @@ -11,11 +11,13 @@ > #include > #include > #include > +#include > #include > #include > #include > #include > #include > +#include > #include > #include > #include > @@ -82,6 +84,10 @@ static const struct kernel_param_ops sample_interval_param_ops = { > }; > module_param_cb(sample_interval, &sample_interval_param_ops, &kfence_sample_interval, 0600); > > +/* Pool usage% threshold when currently covered allocations are skipped. */ > +static unsigned long kfence_skip_covered_thresh __read_mostly = 75; > +module_param_named(skip_covered_thresh, kfence_skip_covered_thresh, ulong, 0644); > + > /* The pool of pages used for guard pages and objects. */ > char *__kfence_pool __ro_after_init; > EXPORT_SYMBOL(__kfence_pool); /* Export for test modules. */ > @@ -105,6 +111,25 @@ DEFINE_STATIC_KEY_FALSE(kfence_allocation_key); > /* Gates the allocation, ensuring only one succeeds in a given period. */ > atomic_t kfence_allocation_gate = ATOMIC_INIT(1); > > +/* > + * A Counting Bloom filter of allocation coverage: limits currently covered > + * allocations of the same source filling up the pool. > + * > + * Assuming a range of 15%-85% unique allocations in the pool at any point in > + * time, the below parameters provide a probablity of 0.02-0.33 for false > + * positive hits respectively: > + * > + * P(alloc_traces) = (1 - e^(-HNUM * (alloc_traces / SIZE)) ^ HNUM > + */ > +#define ALLOC_COVERED_HNUM 2 > +#define ALLOC_COVERED_SIZE (1 << (const_ilog2(CONFIG_KFENCE_NUM_OBJECTS) + 2)) > +#define ALLOC_COVERED_HNEXT(h) (1664525 * (h) + 1013904223) > +#define ALLOC_COVERED_MASK (ALLOC_COVERED_SIZE - 1) > +static atomic_t alloc_covered[ALLOC_COVERED_SIZE]; > + > +/* Stack depth used to determine uniqueness of an allocation. */ > +#define UNIQUE_ALLOC_STACK_DEPTH 8UL > + > /* Statistics counters for debugfs. */ > enum kfence_counter_id { > KFENCE_COUNTER_ALLOCATED, > @@ -114,6 +139,7 @@ enum kfence_counter_id { > KFENCE_COUNTER_BUGS, > KFENCE_COUNTER_SKIP_INCOMPAT, > KFENCE_COUNTER_SKIP_CAPACITY, > + KFENCE_COUNTER_SKIP_COVERED, > KFENCE_COUNTER_COUNT, > }; > static atomic_long_t counters[KFENCE_COUNTER_COUNT]; > @@ -125,11 +151,60 @@ static const char *const counter_names[] = { > [KFENCE_COUNTER_BUGS] = "total bugs", > [KFENCE_COUNTER_SKIP_INCOMPAT] = "skipped allocations (incompatible)", > [KFENCE_COUNTER_SKIP_CAPACITY] = "skipped allocations (capacity)", > + [KFENCE_COUNTER_SKIP_COVERED] = "skipped allocations (covered)", > }; > static_assert(ARRAY_SIZE(counter_names) == KFENCE_COUNTER_COUNT); > > /* === Internals ============================================================ */ > > +static inline bool should_skip_covered(void) > +{ > + unsigned long thresh = (CONFIG_KFENCE_NUM_OBJECTS * kfence_skip_covered_thresh) / 100; > + > + return atomic_long_read(&counters[KFENCE_COUNTER_ALLOCATED]) > thresh; > +} > + > +static u32 get_alloc_stack_hash(unsigned long *stack_entries, size_t num_entries) > +{ > + /* Some randomness across reboots / different machines. */ > + u32 seed = (u32)((unsigned long)__kfence_pool >> (BITS_PER_LONG - 32)); > + > + num_entries = min(num_entries, UNIQUE_ALLOC_STACK_DEPTH); > + num_entries = filter_irq_stacks(stack_entries, num_entries); > + return jhash(stack_entries, num_entries * sizeof(stack_entries[0]), seed); > +} > + > +/* > + * Adds (or subtracts) count @val for allocation stack trace hash > + * @alloc_stack_hash from Counting Bloom filter. > + */ > +static void alloc_covered_add(u32 alloc_stack_hash, int val) > +{ > + int i; > + > + for (i = 0; i < ALLOC_COVERED_HNUM; i++) { > + atomic_add(val, &alloc_covered[alloc_stack_hash & ALLOC_COVERED_MASK]); > + alloc_stack_hash = ALLOC_COVERED_HNEXT(alloc_stack_hash); > + } > +} > + > +/* > + * Returns true if the allocation stack trace hash @alloc_stack_hash is > + * currently contained (non-zero count) in Counting Bloom filter. > + */ > +static bool alloc_covered_contains(u32 alloc_stack_hash) > +{ > + int i; > + > + for (i = 0; i < ALLOC_COVERED_HNUM; i++) { > + if (!atomic_read(&alloc_covered[alloc_stack_hash & ALLOC_COVERED_MASK])) > + return false; > + alloc_stack_hash = ALLOC_COVERED_HNEXT(alloc_stack_hash); > + } > + > + return true; > +} > + > static bool kfence_protect(unsigned long addr) > { > return !KFENCE_WARN_ON(!kfence_protect_page(ALIGN_DOWN(addr, PAGE_SIZE), true)); > @@ -269,7 +344,8 @@ static __always_inline void for_each_canary(const struct kfence_metadata *meta, > } > > static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t gfp, > - unsigned long *stack_entries, size_t num_stack_entries) > + unsigned long *stack_entries, size_t num_stack_entries, > + u32 alloc_stack_hash) > { > struct kfence_metadata *meta = NULL; > unsigned long flags; > @@ -332,6 +408,8 @@ static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g > /* Pairs with READ_ONCE() in kfence_shutdown_cache(). */ > WRITE_ONCE(meta->cache, cache); > meta->size = size; > + meta->alloc_stack_hash = alloc_stack_hash; > + > for_each_canary(meta, set_canary_byte); > > /* Set required struct page fields. */ > @@ -344,6 +422,8 @@ static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g > > raw_spin_unlock_irqrestore(&meta->lock, flags); > > + alloc_covered_add(alloc_stack_hash, 1); > + > /* Memory initialization. */ > > /* > @@ -412,6 +492,8 @@ static void kfence_guarded_free(void *addr, struct kfence_metadata *meta, bool z > > raw_spin_unlock_irqrestore(&meta->lock, flags); > > + alloc_covered_add(meta->alloc_stack_hash, -1); > + > /* Protect to detect use-after-frees. */ > kfence_protect((unsigned long)addr); > > @@ -752,6 +834,7 @@ void *__kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags) > { > unsigned long stack_entries[KFENCE_STACK_DEPTH]; > size_t num_stack_entries; > + u32 alloc_stack_hash; > > /* > * Perform size check before switching kfence_allocation_gate, so that > @@ -799,7 +882,23 @@ void *__kfence_alloc(struct kmem_cache *s, size_t size, gfp_t flags) > > num_stack_entries = stack_trace_save(stack_entries, KFENCE_STACK_DEPTH, 0); > > - return kfence_guarded_alloc(s, size, flags, stack_entries, num_stack_entries); > + /* > + * Do expensive check for coverage of allocation in slow-path after > + * allocation_gate has already become non-zero, even though it might > + * mean not making any allocation within a given sample interval. > + * > + * This ensures reasonable allocation coverage when the pool is almost > + * full, including avoiding long-lived allocations of the same source > + * filling up the pool (e.g. pagecache allocations). > + */ > + alloc_stack_hash = get_alloc_stack_hash(stack_entries, num_stack_entries); > + if (should_skip_covered() && alloc_covered_contains(alloc_stack_hash)) { > + atomic_long_inc(&counters[KFENCE_COUNTER_SKIP_COVERED]); > + return NULL; > + } > + > + return kfence_guarded_alloc(s, size, flags, stack_entries, num_stack_entries, > + alloc_stack_hash); > } > > size_t kfence_ksize(const void *addr) > diff --git a/mm/kfence/kfence.h b/mm/kfence/kfence.h > index c1f23c61e5f9..2a2d5de9d379 100644 > --- a/mm/kfence/kfence.h > +++ b/mm/kfence/kfence.h > @@ -87,6 +87,8 @@ struct kfence_metadata { > /* Allocation and free stack information. */ > struct kfence_track alloc_track; > struct kfence_track free_track; > + /* For updating alloc_covered on frees. */ > + u32 alloc_stack_hash; > }; > > extern struct kfence_metadata kfence_metadata[CONFIG_KFENCE_NUM_OBJECTS]; > -- > 2.33.0.464.g1972c5931b-goog >