Skip to contentSkip to conversation

kfence: buffer random bools in bitmask

PATCH In review Jason A. Donenfeld 2 participants 5 messages Oct 26, 2022 – Oct 27, 2022

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 kfence: buffer random bools in bitmask

Recently kfence got a 4x speed up in calls to the RNG, due to using internally get_random_u8() instead of get_random_u32() for its random boolean values. We can extend that speed up another 8x, to 32x total, by buffering a long at a time, and reading bits from it.

I'd looked into introducing a get_random_bool(), along with the complexities required for that kind of function to work for a general case. But kfence is the only high-speed user of random booleans in a hot path, so we're better off open coding this to take advantage of kfence particularities.

In particular, we take advantage of the fact that kfence_guarded_alloc() already disables interrupts for its raw spinlocks, so that we can keep track of a per-cpu buffered boolean bitmask, without needing to add more interrupt disabling.

This is slightly complicated by PREEMPT_RT, where we actually need to take a local_lock instead. But the resulting code in both cases compiles down to something very compact, and is basically zero cost. Specifically, on !PREEMPT_RT, this amounts to:

    local_irq_save(flags);
    random boolean stuff;
    raw_spin_lock(&other_thing);
    do the existing stuff;
    raw_spin_unlock_irqrestore(&other_thing, flags);

By using a local_lock in the way this patch does, we now also get this code on PREEMPT_RT:

    spin_lock(this_cpu_ptr(&local_lock));
    random boolean stuff;
    spin_unlock(this_cpu_ptr(&local_lock));
    raw_spin_lock_irqsave(&other_thing, flags);
    do the existing stuff;
    raw_spin_unlock_irqrestore(&other_thing, flags);

This is also optimal for RT systems. So all and all, this is pretty good. But there are some compile-time conditionals in order to accomplish this.

Cc Marco Elver <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
---
 mm/kfence/core.c | 32 +++++++++++++++++++++++++++++---
 1 file changed, 29 insertions(+), 3 deletions(-)
mm/kfence/core.c +29 -3
index 6cbd93f2007b..c212ae0cecba 100644
@@ -356,21 +356,47 @@ static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g
 				  unsigned long *stack_entries, size_t num_stack_entries,
 				  u32 alloc_stack_hash)
 {
+	struct random_bools {
+		unsigned long bits;
+		unsigned int len;
+		local_lock_t lock;
+	};
+	static DEFINE_PER_CPU(struct random_bools, pcpu_bools) = {
+		.lock = INIT_LOCAL_LOCK(pcpu_bools.lock)
+	};
+	struct random_bools *bools;
 	struct kfence_metadata *meta = NULL;
 	unsigned long flags;
 	struct slab *slab;
 	void *addr;
-	const bool random_right_allocate = get_random_u32_below(2);
+	bool random_right_allocate;
 	const bool random_fault = CONFIG_KFENCE_STRESS_TEST_FAULTS &&
 				  !get_random_u32_below(CONFIG_KFENCE_STRESS_TEST_FAULTS);
 
+	local_lock_irqsave(&pcpu_bools.lock, flags);
+	bools = raw_cpu_ptr(&pcpu_bools);
+	if (unlikely(!bools->len)) {
+		bools->bits = get_random_long();
+		bools->len = BITS_PER_LONG;
+	}
+	random_right_allocate = bools->bits & 1;
+	bools->bits >>= 1;
+	bools->len--;
+
 	/* Try to obtain a free object. */
-	raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+	if (IS_ENABLED(CONFIG_PREEMPT_RT))
+		raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+	else
+		raw_spin_lock(&kfence_freelist_lock);
 	if (!list_empty(&kfence_freelist)) {
 		meta = list_entry(kfence_freelist.next, struct kfence_metadata, list);
 		list_del_init(&meta->list);
 	}
-	raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+	if (IS_ENABLED(CONFIG_PREEMPT_RT))
+		raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+	else
+		raw_spin_unlock(&kfence_freelist_lock);
+	local_unlock_irqrestore(&pcpu_bools.lock, flags);
 	if (!meta) {
 		atomic_long_inc(&counters[KFENCE_COUNTER_SKIP_CAPACITY]);
 		return NULL;
Signature · 1 line
2.38.1
#1 lore raw

Hi Sebastian,

Quoted 4 lines · Jason A. Donenfeld
mm/kfence/core.c +4 -0
+	if (IS_ENABLED(CONFIG_PREEMPT_RT))
+		raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+	else
+		raw_spin_lock(&kfence_freelist_lock);

[...]

mm/kfence/core.c static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g · line 399

Quoted 5 lines
mm/kfence/core.c +5 -0
+	if (IS_ENABLED(CONFIG_PREEMPT_RT))
+		raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+	else
+		raw_spin_unlock(&kfence_freelist_lock);
+	local_unlock_irqrestore(&pcpu_bools.lock, flags);

I assume those conditionals are really upsetting to you. If you don't want those, can you propose something that has the same good codegen but doesn't need the conditional?

Jason

maintainer
#2 lore raw
In reply to Jason A. Donenfeld
Quoted 11 lines · Jason A. Donenfeld

Recently kfence got a 4x speed up in calls to the RNG, due to using internally get_random_u8() instead of get_random_u32() for its random boolean values. We can extend that speed up another 8x, to 32x total, by buffering a long at a time, and reading bits from it.

I'd looked into introducing a get_random_bool(), along with the complexities required for that kind of function to work for a general case. But kfence is the only high-speed user of random booleans in a hot path, so we're better off open coding this to take advantage of kfence particularities.

kfence_guarded_alloc() is supposed to be a slow-path. And if it were a hot-path, I currently see no evidence that a call into the RNG dominates the time spent there.

Do you have profiles?

What are the real benefits of this change?
Is it to avoid depleting the entropy pool?

Quoted 43 lines

In particular, we take advantage of the fact that kfence_guarded_alloc() already disables interrupts for its raw spinlocks, so that we can keep track of a per-cpu buffered boolean bitmask, without needing to add more interrupt disabling.

This is slightly complicated by PREEMPT_RT, where we actually need to take a local_lock instead. But the resulting code in both cases compiles down to something very compact, and is basically zero cost. Specifically, on !PREEMPT_RT, this amounts to:

    local_irq_save(flags);
    random boolean stuff;
    raw_spin_lock(&other_thing);
    do the existing stuff;
    raw_spin_unlock_irqrestore(&other_thing, flags);

By using a local_lock in the way this patch does, we now also get this code on PREEMPT_RT:

    spin_lock(this_cpu_ptr(&local_lock));
    random boolean stuff;
    spin_unlock(this_cpu_ptr(&local_lock));
    raw_spin_lock_irqsave(&other_thing, flags);
    do the existing stuff;
    raw_spin_unlock_irqrestore(&other_thing, flags);

This is also optimal for RT systems. So all and all, this is pretty good. But there are some compile-time conditionals in order to accomplish this.

Cc Marco Elver <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
---
 mm/kfence/core.c | 32 +++++++++++++++++++++++++++++---
 1 file changed, 29 insertions(+), 3 deletions(-)
mm/kfence/core.c +0 -0
index 6cbd93f2007b..c212ae0cecba 100644
@@ -356,21 +356,47 @@ static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g
                                  unsigned long *stack_entries, size_t num_stack_entries,

mm/kfence/core.c static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g · line 366

Quoted 10 lines
mm/kfence/core.c +8 -0
                                  u32 alloc_stack_hash)
 {
+       struct random_bools {
+               unsigned long bits;
+               unsigned int len;
+               local_lock_t lock;
+       };
+       static DEFINE_PER_CPU(struct random_bools, pcpu_bools) = {
+               .lock = INIT_LOCAL_LOCK(pcpu_bools.lock)
+       };

If I remember right, function-scoped static DEFINE_PER_CPU were disallowed (but I now cannot recall why and where it said that :-/).

Quoted 9 lines
mm/kfence/core.c +2 -1
+       struct random_bools *bools;
        struct kfence_metadata *meta = NULL;
        unsigned long flags;
        struct slab *slab;
        void *addr;
-       const bool random_right_allocate = get_random_u32_below(2);
+       bool random_right_allocate;
        const bool random_fault = CONFIG_KFENCE_STRESS_TEST_FAULTS &&
                                  !get_random_u32_below(CONFIG_KFENCE_STRESS_TEST_FAULTS);

mm/kfence/core.c static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g · line 384

Quoted 10 lines
mm/kfence/core.c +9 -0
 
+       local_lock_irqsave(&pcpu_bools.lock, flags);
+       bools = raw_cpu_ptr(&pcpu_bools);
+       if (unlikely(!bools->len)) {
+               bools->bits = get_random_long();
+               bools->len = BITS_PER_LONG;
+       }
+       random_right_allocate = bools->bits & 1;
+       bools->bits >>= 1;
+       bools->len--;

This should be factored into its own function that returns a result for random_right_allocate.

Quoted 6 lines
mm/kfence/core.c +4 -1
        /* Try to obtain a free object. */
-       raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+       if (IS_ENABLED(CONFIG_PREEMPT_RT))
+               raw_spin_lock_irqsave(&kfence_freelist_lock, flags);
+       else
+               raw_spin_lock(&kfence_freelist_lock);

mm/kfence/core.c static void *kfence_guarded_alloc(struct kmem_cache *cache, size_t size, gfp_t g · line 399

Quoted 10 lines
mm/kfence/core.c +5 -1
        if (!list_empty(&kfence_freelist)) {
                meta = list_entry(kfence_freelist.next, struct kfence_metadata, list);
                list_del_init(&meta->list);
        }
-       raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+       if (IS_ENABLED(CONFIG_PREEMPT_RT))
+               raw_spin_unlock_irqrestore(&kfence_freelist_lock, flags);
+       else
+               raw_spin_unlock(&kfence_freelist_lock);
+       local_unlock_irqrestore(&pcpu_bools.lock, flags);

Overall this introduces complexities that should be hidden behind some new abstractions.

But besides that, I'd first want to understand what the real benefit is given all this is supposed to be a slow-path.

Thanks,
-- Marco

#3 lore raw

Hi Marco,

Quoted 1 line · Marco Elver

Is it to avoid depleting the entropy pool?

The entropy pool never depletes, so no.

Quoted 1 line

kfence_guarded_alloc() is supposed to be a slow-path. And if it were a

Ahh, my huge misunderstanding, then. For some reason, I was under the general assumption that this got called for every allocation. Given that this apparently isn't the case, let's indeed just forget I posted this.

This then means, by the way, that there are in fact no fast-path users of random booleans, which means get_random_bool() is totally unnecessary. Before I thought this was the one case, hence open coding it, but luckily that even isn't necessary.

Anyway, sorry for the noise.

Jason

maintainer
#4 lore raw
Quoted 6 lines · Jason A. Donenfeld

Hi Marco,

Quoted 1 line · Marco Elver

Is it to avoid depleting the entropy pool?

Quoted 7 lines

The entropy pool never depletes, so no.

Quoted 1 line

kfence_guarded_alloc() is supposed to be a slow-path. And if it were a

Ahh, my huge misunderstanding, then. For some reason, I was under the general assumption that this got called for every allocation. Given that this apparently isn't the case, let's indeed just forget I posted this.

No worries. Allocations via sl[au]b are "sampled", i.e. a fixed sample interval decides if an allocation is redirected through KFENCE (the lowest sample interval is 1ms, but that's generally not recommended anyway - default is 100ms - so if the system is busy doing allocations, every 100ms there's a call into kfence_guarded_alloc()).

Quoted 6 lines

This then means, by the way, that there are in fact no fast-path users of random booleans, which means get_random_bool() is totally unnecessary. Before I thought this was the one case, hence open coding it, but luckily that even isn't necessary.

Anyway, sorry for the noise.

Thanks for clarifying - and good we sorted it out. ;-)

Thanks,
-- Marco