kfence: buffer random bools in bitmask
Subsystems (2)
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.
--- mm/kfence/core.c | 32 +++++++++++++++++++++++++++++--- 1 file changed, 29 insertions(+), 3 deletions(-)
mm/kfence/core.c +29 -3
@@ -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
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
Marco Elver
maintainerQuoted 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 ofget_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 alocal_lockinstead. 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_lockin the way this patch does, we now also get this code onPREEMPT_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]>Signed-off-by Jason A. Donenfeld <[email protected]>--- mm/kfence/core.c | 32 +++++++++++++++++++++++++++++--- 1 file changed, 29 insertions(+), 3 deletions(-)mm/kfence/core.c +0
-0@@ -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
-0u32 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
-1if (!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
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
Marco Elver
maintainerQuoted 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 aAhh, 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