stackdepot: allow evicting stack traces
Subsystems (3)
cover stackdepot: allow evicting stack traces
From: Andrey Konovalov <[email protected]>
Currently, the stack depot grows indefinitely until it reaches its capacity. Once that happens, the stack depot stops saving new stack traces.
This creates a problem for using the stack depot for in-field testing and in production.
For such uses, an ideal stack trace storage should:
1. Allow saving fresh stack traces on systems with a large uptime while limiting the amount of memory used to store the traces;
2. Have a low performance impact.
Implementing #1 in the stack depot is impossible with the current keep-forever approach. This series targets to address that. Issue #2 is left to be addressed in a future series.
This series changes the stack depot implementation to allow evicting unneeded stack traces from the stack depot. The users of the stack depot can do that via a new stack_depot_evict API.
Internal changes to the stack depot code include:
1. Storing stack traces in 32-frame-sized slots (vs precisely-sized slots in the current implementation);
2. Keeping available slots in a freelist (vs keeping an offset to the next free slot);
3. Using a read/write lock for synchronization (vs a lock-free approach combined with a spinlock).
This series also integrates the eviction functionality in the tag-based KASAN modes. (I will investigate integrating it into the Generic mode as well in the following iterations of this series.)
Despite wasting some space on rounding up the size of each stack record to 32 frames, with this change, the tag-based KASAN modes end up consuming ~5% less memory in stack depot during boot (with the default stack ring size of 32k entries). The reason for this is the eviction of irrelevant stack traces from the stack depot, which frees up space for other stack traces.
For other tools that heavily rely on the stack depot, like Generic KASAN and KMSAN, this change leads to the stack depot capacity being reached sooner than before. However, as these tools are mainly used in fuzzing scenarios where the kernel is frequently rebooted, this outcome should be acceptable.
There is no measurable boot time performace impact of these changes for KASAN on x86-64. I haven't done any tests for arm64 modes (the stack depot without performance optimizations is not suitable for intended use of those anyway), but I expect a similar result. Obtaining and copying stack trace frames when saving them into stack depot is what takes the most time.
This series does not yet provide a way to configure the maximum size of the stack depot externally (e.g. via a command-line parameter). This will either be added in the following iterations of this series (if the used approach gets approval) or will be added together with the performance improvement changes.
Andrey Konovalov (15):
stackdepot: check disabled flag when fetching
stackdepot: simplify __stack_depot_save
stackdepot: drop valid bit from handles
stackdepot: add depot_fetch_stack helper
stackdepot: use fixed-sized slots for stack records
stackdepot: fix and clean-up atomic annotations
stackdepot: rework helpers for depot_alloc_stack
stackdepot: rename next_pool_required to new_pool_required
stackdepot: store next pool pointer in new_pool
stackdepot: store free stack records in a freelist
stackdepot: use read/write lock
stackdepot: add refcount for records
stackdepot: add backwards links to hash table buckets
stackdepot: allow users to evict stack traces
kasan: use stack_depot_evict for tag-based modes
include/linux/stackdepot.h | 11 ++ lib/stackdepot.c | 361 ++++++++++++++++++++++++------------- mm/kasan/tags.c | 7 +- 3 files changed, 249 insertions(+), 130 deletions(-)
Signature · 1 line
2.25.1
PATCH 1/15 stackdepot: check disabled flag when fetching
From: Andrey Konovalov <[email protected]>
Do not try fetching a stack trace from the stack depot if the stack_depot_disabled flag is enabled.
--- lib/stackdepot.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/stackdepot.c +1 -1
@@ -477,7 +477,7 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle,*/ kmsan_unpoison_memory (entries,sizeof (*entries)); -if (!handle) +if (!handle || stack_depot_disabled)return 0 ;if (parts.pool_index > pool_index_cached) {
Signature · 1 line
2.25.1
PATCH 2/15 stackdepot: simplify __stack_depot_save
In reply to [email protected]From: Andrey Konovalov <[email protected]>
The retval local variable in __stack_depot_save has the union type handle_parts, but the function never uses anything but the union's handle field.
Define retval simply as depot_stack_handle_t to simplify the code.
--- lib/stackdepot.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-)
lib/stackdepot.c +4 -5
@@ -360,7 +360,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, gfp_t alloc_flags, bool can_alloc) {struct stack_record *found =NULL , **bucket; -union handle_parts retval = { .handle =0 }; +depot_stack_handle_t handle =0 ;struct page *page =NULL ;void *prealloc =NULL ;unsigned long flags;
@@ -377,7 +377,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, nr_entries =filter_irq_stacks (entries, nr_entries);if (unlikely (nr_entries ==0 ) || stack_depot_disabled) - goto fast_exit; +return 0 ; hash =hash_stack (entries, nr_entries); bucket = &stack_table[hash & stack_hash_mask];
@@ -443,9 +443,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,free_pages ((unsigned long )prealloc,DEPOT_POOL_ORDER ); }if (found) - retval.handle = found->handle.handle; -fast_exit: -return retval.handle; + handle = found->handle.handle; +return handle; }EXPORT_SYMBOL_GPL (__stack_depot_save);
Signature · 1 line
2.25.1
PATCH 3/15 stackdepot: drop valid bit from handles
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Stack depot doesn't use the valid bit in handles in any way, so drop it.
--- lib/stackdepot.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-)
lib/stackdepot.c +2 -5
@@ -32,13 +32,12 @@#define DEPOT_HANDLE_BITS (sizeof(depot_stack_handle_t) * 8) -#define DEPOT_VALID_BITS 1#define DEPOT_POOL_ORDER 2/* Pool size order, 4 pages */ #define DEPOT_POOL_SIZE (1LL << (PAGE_SHIFT + DEPOT_POOL_ORDER))#define DEPOT_STACK_ALIGN 4#define DEPOT_OFFSET_BITS (DEPOT_POOL_ORDER + PAGE_SHIFT - DEPOT_STACK_ALIGN) -#define DEPOT_POOL_INDEX_BITS (DEPOT_HANDLE_BITS - DEPOT_VALID_BITS - \ - DEPOT_OFFSET_BITS - STACK_DEPOT_EXTRA_BITS) +#define DEPOT_POOL_INDEX_BITS (DEPOT_HANDLE_BITS - DEPOT_OFFSET_BITS - \ + STACK_DEPOT_EXTRA_BITS)#define DEPOT_POOLS_CAP 8192#define DEPOT_MAX_POOLS \ (((1LL << (DEPOT_POOL_INDEX_BITS)) < DEPOT_POOLS_CAP) ? \
@@ -50,7 +49,6 @@ union handle_parts {struct {u32 pool_index :DEPOT_POOL_INDEX_BITS ;u32 offset :DEPOT_OFFSET_BITS ; -u32 valid :DEPOT_VALID_BITS ;u32 extra :STACK_DEPOT_EXTRA_BITS ; }; };
@@ -303,7 +301,6 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) stack->size = size; stack->handle.pool_index = pool_index; stack->handle.offset = pool_offset >>DEPOT_STACK_ALIGN ; - stack->handle.valid =1 ; stack->handle.extra =0 ;memcpy (stack->entries, entries,flex_array_size (stack, entries, size)); pool_offset += required_size;
Signature · 1 line
2.25.1
PATCH 5/15 stackdepot: use fixed-sized slots for stack records
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Instead of storing stack records in stack depot pools one right after another, use 32-frame-sized slots.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
--- lib/stackdepot.c | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-)
lib/stackdepot.c +10 -4
@@ -42,6 +42,7 @@#define DEPOT_MAX_POOLS \ (((1LL << (DEPOT_POOL_INDEX_BITS)) < DEPOT_POOLS_CAP) ? \ (1LL << (DEPOT_POOL_INDEX_BITS)) : DEPOT_POOLS_CAP) +#define DEPOT_STACK_MAX_FRAMES 32/* Compact structure that stores a reference to a stack. */ union handle_parts {
@@ -58,9 +59,12 @@ struct stack_record {u32 hash;/* Hash in the hash table */ u32 size;/* Number of stored frames */ union handle_parts handle; -unsigned long entries[];/* Variable-sized array of frames */ +unsigned long entries[DEPOT_STACK_MAX_FRAMES ];/* Frames */ }; +#define DEPOT_STACK_RECORD_SIZE \ + ALIGN(sizeof(struct stack_record), 1 << DEPOT_STACK_ALIGN) +static bool stack_depot_disabled;static bool __stack_depot_early_init_requested__initdata =IS_ENABLED (CONFIG_STACKDEPOT_ALWAYS_INIT );static bool __stack_depot_early_init_passed__initdata ;
@@ -258,9 +262,7 @@ static struct stack_record * depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) { struct stack_record *stack; -size_t required_size =struct_size (stack, entries, size); - - required_size =ALIGN (required_size,1 <<DEPOT_STACK_ALIGN ); +size_t required_size =DEPOT_STACK_RECORD_SIZE ;/* Check if there is not enough space in the current pool. */ if (unlikely (pool_offset + required_size >DEPOT_POOL_SIZE )) {
@@ -295,6 +297,10 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)if (stack_pools[pool_index] ==NULL )return NULL ; +/* Limit number of saved frames to DEPOT_STACK_MAX_FRAMES. */ +if (size >DEPOT_STACK_MAX_FRAMES ) + size =DEPOT_STACK_MAX_FRAMES ; +/* Save the stack trace. */ stack = stack_pools[pool_index] + pool_offset; stack->hash = hash;
Signature · 1 line
2.25.1
PATCH 4/15 stackdepot: add depot_fetch_stack helper
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Add a helper depot_fetch_stack function that fetches the pointer to a stack record.
With this change, all static depot_* functions now operate on stack pools and the exported stack_depot_* functions operate on the hash table.
--- lib/stackdepot.c | 45 ++++++++++++++++++++++++++++----------------- 1 file changed, 28 insertions(+), 17 deletions(-)
lib/stackdepot.c +28 -17
@@ -304,6 +304,7 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) stack->handle.extra =0 ;memcpy (stack->entries, entries,flex_array_size (stack, entries, size)); pool_offset += required_size; +/* * Let KMSAN know the stored stack record is initialized. This shall * prevent false positive reports if instrumented code accesses it.
@@ -313,6 +314,32 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)return stack; } +static struct stack_record *depot_fetch_stack (depot_stack_handle_t handle) +{ +union handle_parts parts = { .handle = handle }; +/* +* READ_ONCE pairs with potential concurrent write in +* depot_alloc_stack. +*/ +int pool_index_cached =READ_ONCE (pool_index); +void *pool; +size_t offset = parts.offset <<DEPOT_STACK_ALIGN ; +struct stack_record *stack; + +if (parts.pool_index > pool_index_cached) { +WARN (1 ,"pool index %d out of bounds (%d) for stack id %08x\n" , + parts.pool_index, pool_index_cached, handle); +return NULL ; + } + + pool = stack_pools[parts.pool_index]; +if (!pool) +return NULL ; + + stack = pool + offset; +return stack; +} +/* Calculates the hash for a stack. */ static inline u32 hash_stack (unsigned long *entries,unsigned int size) {
@@ -456,14 +483,6 @@ EXPORT_SYMBOL_GPL(stack_depot_save);unsigned int stack_depot_fetch (depot_stack_handle_t handle,unsigned long **entries) { -union handle_parts parts = { .handle = handle }; -/* -* READ_ONCE pairs with potential concurrent write in -* depot_alloc_stack. -*/ -int pool_index_cached =READ_ONCE (pool_index); -void *pool; -size_t offset = parts.offset <<DEPOT_STACK_ALIGN ;struct stack_record *stack; *entries =NULL ;
@@ -476,15 +495,7 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle,if (!handle || stack_depot_disabled)return 0 ; -if (parts.pool_index > pool_index_cached) { -WARN (1 ,"pool index %d out of bounds (%d) for stack id %08x\n" , - parts.pool_index, pool_index_cached, handle); -return 0 ; - } - pool = stack_pools[parts.pool_index]; -if (!pool) -return 0 ; - stack = pool + offset; + stack =depot_fetch_stack (handle); *entries = stack->entries;return stack->size;
Signature · 1 line
2.25.1
PATCH 6/15 stackdepot: fix and clean-up atomic annotations
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Simplify comments accompanying the use of atomic accesses in the stack depot code.
Also turn smp_load_acquire from next_pool_required in depot_init_pool into READ_ONCE, as both depot_init_pool and the all smp_store_release's to this variable are executed under the stack depot lock.
---
This patch is not strictly required, as the atomic accesses are fully removed in one of the latter patches. However, I decided to keep the patch just in case we end up needing these atomics in the following iterations of this series.
--- lib/stackdepot.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-)
lib/stackdepot.c +13 -14
@@ -226,10 +226,10 @@ static void depot_init_pool(void **prealloc)/* * If the next pool is already initialized or the maximum number of * pools is reached, do not use the preallocated memory. -* smp_load_acquire() here pairs with smp_store_release() below and -* in depot_alloc_stack(). +* READ_ONCE is only used to mark the variable as atomic, +* there are no concurrent writes. */ -if (!smp_load_acquire (&next_pool_required)) +if (!READ_ONCE (next_pool_required))return ;/* Check if the current pool is not yet allocated. */
@@ -250,8 +250,8 @@ static void depot_init_pool(void **prealloc)* At this point, either the next pool is initialized or the * maximum number of pools is reached. In either case, take * note that initializing another pool is not required. -* This smp_store_release pairs with smp_load_acquire() above -* and in stack_depot_save(). +* smp_store_release pairs with smp_load_acquire in +* stack_depot_save. */ smp_store_release (&next_pool_required,0 ); }
@@ -275,15 +275,15 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)/* * Move on to the next pool. * WRITE_ONCE pairs with potential concurrent read in -* stack_depot_fetch(). +* stack_depot_fetch. */ WRITE_ONCE (pool_index, pool_index +1 ); pool_offset =0 ;/* * If the maximum number of pools is not reached, take note * that the next pool needs to initialized. -* smp_store_release() here pairs with smp_load_acquire() in -* stack_depot_save() and depot_init_pool(). +* smp_store_release pairs with smp_load_acquire in +* stack_depot_save. */ if (pool_index +1 <DEPOT_MAX_POOLS )smp_store_release (&next_pool_required,1 );
@@ -414,8 +414,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,/* * Fast path: look the stack trace up without locking. -* The smp_load_acquire() here pairs with smp_store_release() to -* |bucket| below. +* smp_load_acquire pairs with smp_store_release to |bucket| below. */ found =find_stack (smp_load_acquire (bucket), entries, nr_entries, hash);if (found)
@@ -425,8 +424,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,* Check if another stack pool needs to be initialized. If so, allocate * the memory now - we won't be able to do that under the lock. * -* The smp_load_acquire() here pairs with smp_store_release() to -* |next_pool_inited| in depot_alloc_stack() and depot_init_pool(). +* smp_load_acquire pairs with smp_store_release +* in depot_alloc_stack and depot_init_pool. */ if (unlikely (can_alloc &&smp_load_acquire (&next_pool_required))) {/*
@@ -452,8 +451,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,if (new) { new->next = *bucket;/* -* This smp_store_release() pairs with -* smp_load_acquire() from |bucket| above. +* smp_store_release pairs with smp_load_acquire +* from |bucket| above. */ smp_store_release (bucket, new); found = new;
Signature · 1 line
2.25.1
PATCH 7/15 stackdepot: rework helpers for depot_alloc_stack
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Split code in depot_alloc_stack and depot_init_pool into 3 functions:
1. depot_keep_next_pool that keeps preallocated memory for the next pool if required.
2. depot_update_pools that moves on to the next pool if there's no space left in the current pool, uses preallocated memory for the new current pool if required, and calls depot_keep_next_pool otherwise.
3. depot_alloc_stack that calls depot_update_pools and then allocates a stack record as before.
This makes it somewhat easier to follow the logic of depot_alloc_stack and also serves as a preparation for implementing the eviction of stack records from the stack depot.
--- lib/stackdepot.c | 85 +++++++++++++++++++++++++++--------------------- 1 file changed, 48 insertions(+), 37 deletions(-)
lib/stackdepot.c +48 -37
@@ -220,11 +220,11 @@ int stack_depot_init(void) }EXPORT_SYMBOL_GPL (stack_depot_init); -/* Uses preallocated memory to initialize a new stack depot pool. */ -static void depot_init_pool (void **prealloc) +/* Keeps the preallocated memory to be used for the next stack depot pool. */ +static void depot_keep_next_pool (void **prealloc) {/* -* If the next pool is already initialized or the maximum number of +* If the next pool is already saved or the maximum number of * pools is reached, do not use the preallocated memory. * READ_ONCE is only used to mark the variable as atomic, * there are no concurrent writes.
@@ -232,44 +232,33 @@ static void depot_init_pool(void **prealloc)if (!READ_ONCE (next_pool_required))return ; -/* Check if the current pool is not yet allocated. */ -if (stack_pools[pool_index] ==NULL ) { -/* Use the preallocated memory for the current pool. */ - stack_pools[pool_index] = *prealloc; +/* +* Use the preallocated memory for the next pool +* as long as we do not exceed the maximum number of pools. +*/ +if (pool_index +1 <DEPOT_MAX_POOLS ) { + stack_pools[pool_index +1 ] = *prealloc; *prealloc =NULL ; - }else { -/* -* Otherwise, use the preallocated memory for the next pool -* as long as we do not exceed the maximum number of pools. -*/ -if (pool_index +1 <DEPOT_MAX_POOLS ) { - stack_pools[pool_index +1 ] = *prealloc; - *prealloc =NULL ; - } -/* -* At this point, either the next pool is initialized or the -* maximum number of pools is reached. In either case, take -* note that initializing another pool is not required. -* smp_store_release pairs with smp_load_acquire in -* stack_depot_save. -*/ -smp_store_release (&next_pool_required,0 ); } + +/* +* At this point, either the next pool is kept or the maximum +* number of pools is reached. In either case, take note that +* keeping another pool is not required. +* smp_store_release pairs with smp_load_acquire in stack_depot_save. +*/ +smp_store_release (&next_pool_required,0 ); } -/* Allocates a new stack in a stack depot pool. */ -static struct stack_record * -depot_alloc_stack (unsigned long *entries,int size,u32 hash,void **prealloc) +/* Updates refences to the current and the next stack depot pools. */ +static bool depot_update_pools (size_t required_size,void **prealloc) { -struct stack_record *stack; -size_t required_size =DEPOT_STACK_RECORD_SIZE ; -/* Check if there is not enough space in the current pool. */ if (unlikely (pool_offset + required_size >DEPOT_POOL_SIZE )) {/* Bail out if we reached the pool limit. */ if (unlikely (pool_index +1 >=DEPOT_MAX_POOLS )) {WARN_ONCE (1 ,"Stack depot reached limit capacity" ); -return NULL ; +return false; }/*
@@ -279,9 +268,10 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)*/ WRITE_ONCE (pool_index, pool_index +1 ); pool_offset =0 ; +/* * If the maximum number of pools is not reached, take note -* that the next pool needs to initialized. +* that the next pool needs to be initialized. * smp_store_release pairs with smp_load_acquire in * stack_depot_save. */
@@ -289,9 +279,30 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)smp_store_release (&next_pool_required,1 ); } -/* Assign the preallocated memory to a pool if required. */ +/* Check if the current pool is not yet allocated. */ +if (*prealloc && stack_pools[pool_index] ==NULL ) { +/* Use the preallocated memory for the current pool. */ + stack_pools[pool_index] = *prealloc; + *prealloc =NULL ; +return true; + } + +/* Otherwise, try using the preallocated memory for the next pool. */ if (*prealloc) -depot_init_pool (prealloc); +depot_keep_next_pool (prealloc); +return true; +} + +/* Allocates a new stack in a stack depot pool. */ +static struct stack_record * +depot_alloc_stack (unsigned long *entries,int size,u32 hash,void **prealloc) +{ +struct stack_record *stack; +size_t required_size =DEPOT_STACK_RECORD_SIZE ; + +/* Update current and next pools if required and possible. */ +if (!depot_update_pools (required_size, prealloc)) +return NULL ;/* Check if we have a pool to save the stack trace. */ if (stack_pools[pool_index] ==NULL )
@@ -325,7 +336,7 @@ static struct stack_record *depot_fetch_stack(depot_stack_handle_t handle)union handle_parts parts = { .handle = handle };/* * READ_ONCE pairs with potential concurrent write in -* depot_alloc_stack. +* depot_update_pools. */ int pool_index_cached =READ_ONCE (pool_index);void *pool;
@@ -425,7 +436,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,* the memory now - we won't be able to do that under the lock. * * smp_load_acquire pairs with smp_store_release -* in depot_alloc_stack and depot_init_pool. +* in depot_update_pools and depot_keep_next_pool. */ if (unlikely (can_alloc &&smp_load_acquire (&next_pool_required))) {/*
@@ -462,7 +473,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,* Stack depot already contains this stack trace, but let's * keep the preallocated memory for the future. */ -depot_init_pool (&prealloc); +depot_keep_next_pool (&prealloc); }raw_spin_unlock_irqrestore (&pool_lock, flags);
Signature · 1 line
2.25.1
PATCH 8/15 stackdepot: rename next_pool_required to new_pool_required
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Rename next_pool_required to new_pool_required.
This a purely code readability change: the following patch will change stack depot to store the pointer to the new pool in a separate variable, and "new" seems like a more logical name.
--- lib/stackdepot.c | 47 +++++++++++++++++++++++------------------------ 1 file changed, 23 insertions(+), 24 deletions(-)
lib/stackdepot.c +23 -24
@@ -94,12 +94,11 @@ static size_t pool_offset;static DEFINE_RAW_SPINLOCK (pool_lock);/* * Stack depot tries to keep an extra pool allocated even before it runs out -* of space in the currently used pool. -* This flag marks that this next extra pool needs to be allocated and -* initialized. It has the value 0 when either the next pool is not yet -* initialized or the limit on the number of pools is reached. +* of space in the currently used pool. This flag marks whether this extra pool +* needs to be allocated. It has the value 0 when either an extra pool is not +* yet allocated or if the limit on the number of pools is reached. */ -static int next_pool_required =1 ; +static int new_pool_required =1 ;static int __init disable_stack_depot (char *str) {
@@ -220,20 +219,20 @@ int stack_depot_init(void) }EXPORT_SYMBOL_GPL (stack_depot_init); -/* Keeps the preallocated memory to be used for the next stack depot pool. */ -static void depot_keep_next_pool (void **prealloc) +/* Keeps the preallocated memory to be used for a new stack depot pool. */ +static void depot_keep_new_pool (void **prealloc) {/* -* If the next pool is already saved or the maximum number of +* If a new pool is already saved or the maximum number of * pools is reached, do not use the preallocated memory. * READ_ONCE is only used to mark the variable as atomic, * there are no concurrent writes. */ -if (!READ_ONCE (next_pool_required)) +if (!READ_ONCE (new_pool_required))return ;/* -* Use the preallocated memory for the next pool +* Use the preallocated memory for the new pool * as long as we do not exceed the maximum number of pools. */ if (pool_index +1 <DEPOT_MAX_POOLS ) {
@@ -242,12 +241,12 @@ static void depot_keep_next_pool(void **prealloc) }/* -* At this point, either the next pool is kept or the maximum +* At this point, either a new pool is kept or the maximum * number of pools is reached. In either case, take note that * keeping another pool is not required. * smp_store_release pairs with smp_load_acquire in stack_depot_save. */ -smp_store_release (&next_pool_required,0 ); +smp_store_release (&new_pool_required,0 ); }/* Updates refences to the current and the next stack depot pools. */
@@ -262,7 +261,7 @@ static bool depot_update_pools(size_t required_size, void **prealloc) }/* -* Move on to the next pool. +* Move on to the new pool. * WRITE_ONCE pairs with potential concurrent read in * stack_depot_fetch. */
@@ -271,12 +270,12 @@ static bool depot_update_pools(size_t required_size, void **prealloc)/* * If the maximum number of pools is not reached, take note -* that the next pool needs to be initialized. +* that yet another new pool needs to be allocated. * smp_store_release pairs with smp_load_acquire in * stack_depot_save. */ if (pool_index +1 <DEPOT_MAX_POOLS ) -smp_store_release (&next_pool_required,1 ); +smp_store_release (&new_pool_required,1 ); }/* Check if the current pool is not yet allocated. */
@@ -287,9 +286,9 @@ static bool depot_update_pools(size_t required_size, void **prealloc)return true; } -/* Otherwise, try using the preallocated memory for the next pool. */ +/* Otherwise, try using the preallocated memory for a new pool. */ if (*prealloc) -depot_keep_next_pool (prealloc); +depot_keep_new_pool (prealloc);return true; }
@@ -300,7 +299,7 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)struct stack_record *stack;size_t required_size =DEPOT_STACK_RECORD_SIZE ; -/* Update current and next pools if required and possible. */ +/* Update current and new pools if required and possible. */ if (!depot_update_pools (required_size, prealloc))return NULL ;
@@ -432,13 +431,13 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, goto exit;/* -* Check if another stack pool needs to be initialized. If so, allocate -* the memory now - we won't be able to do that under the lock. +* Check if another stack pool needs to be allocated. If so, allocate +* the memory now: we won't be able to do that under the lock. * * smp_load_acquire pairs with smp_store_release -* in depot_update_pools and depot_keep_next_pool. +* in depot_update_pools and depot_keep_new_pool. */ -if (unlikely (can_alloc &&smp_load_acquire (&next_pool_required))) { +if (unlikely (can_alloc &&smp_load_acquire (&new_pool_required))) {/* * Zero out zone modifiers, as we don't have specific zone * requirements. Keep the flags related to allocation in atomic
@@ -471,9 +470,9 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, }else if (prealloc) {/* * Stack depot already contains this stack trace, but let's -* keep the preallocated memory for the future. +* keep the preallocated memory for future. */ -depot_keep_next_pool (&prealloc); +depot_keep_new_pool (&prealloc); }raw_spin_unlock_irqrestore (&pool_lock, flags);
Signature · 1 line
2.25.1
PATCH 9/15 stackdepot: store next pool pointer in new_pool
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Instead of using the last pointer in stack_pools for storing the pointer to a new pool (which does not yet store any stack records), use a new new_pool variable.
This a purely code readability change: it seems more logical to store the pointer to a pool with a special meaning in a dedicated variable.
--- lib/stackdepot.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
lib/stackdepot.c +5 -1
@@ -86,6 +86,8 @@ static unsigned int stack_hash_mask;/* Array of memory regions that store stack traces. */ static void *stack_pools[DEPOT_MAX_POOLS ]; +/* Newly allocated pool that is not yet added to stack_pools. */ +static void *new_pool;/* Currently used pool in stack_pools. */ static int pool_index;/* Offset to the unused space in the currently used pool. */
@@ -236,7 +238,7 @@ static void depot_keep_new_pool(void **prealloc)* as long as we do not exceed the maximum number of pools. */ if (pool_index +1 <DEPOT_MAX_POOLS ) { - stack_pools[pool_index +1 ] = *prealloc; + new_pool = *prealloc; *prealloc =NULL ; }
@@ -266,6 +268,8 @@ static bool depot_update_pools(size_t required_size, void **prealloc)* stack_depot_fetch. */ WRITE_ONCE (pool_index, pool_index +1 ); + stack_pools[pool_index] = new_pool; + new_pool =NULL ; pool_offset =0 ;/*
Signature · 1 line
2.25.1
PATCH 10/15 stackdepot: store free stack records in a freelist
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Instead of using the global pool_offset variable to find a free slot when storing a new stack record, mainlain a freelist of free slots within the allocated stack pools.
A global next_stack variable is used as the head of the freelist, and the next field in the stack_record struct is reused as freelist link (when the record is not in the freelist, this field is used as a link in the hash table).
This is preparatory patch for implementing the eviction of stack records from the stack depot.
--- lib/stackdepot.c | 130 +++++++++++++++++++++++++++++------------------ 1 file changed, 81 insertions(+), 49 deletions(-)
lib/stackdepot.c +81 -49
@@ -55,8 +55,8 @@ union handle_parts { };struct stack_record { -struct stack_record *next;/* Link in the hash table */ -u32 hash;/* Hash in the hash table */ +struct stack_record *next;/* Link in hash table or freelist */ +u32 hash;/* Hash in hash table */ u32 size;/* Number of stored frames */ union handle_parts handle;unsigned long entries[DEPOT_STACK_MAX_FRAMES ];/* Frames */
@@ -88,10 +88,10 @@ static unsigned int stack_hash_mask;static void *stack_pools[DEPOT_MAX_POOLS ];/* Newly allocated pool that is not yet added to stack_pools. */ static void *new_pool; -/* Currently used pool in stack_pools. */ -static int pool_index; -/* Offset to the unused space in the currently used pool. */ -static size_t pool_offset; +/* Number of pools in stack_pools. */ +static int pools_num; +/* Next stack in the freelist of stack records within stack_pools. */ +static struct stack_record *next_stack;/* Lock that protects the variables above. */ static DEFINE_RAW_SPINLOCK (pool_lock);/*
@@ -221,6 +221,41 @@ int stack_depot_init(void) }EXPORT_SYMBOL_GPL (stack_depot_init); +/* Initializes a stack depol pool. */ +static void depot_init_pool (void *pool) +{ +const int records_in_pool =DEPOT_POOL_SIZE /DEPOT_STACK_RECORD_SIZE ; +int i, offset; + +/* Initialize handles and link stack records to each other. */ +for (i =0 , offset =0 ; offset <DEPOT_POOL_SIZE ; + i++, offset +=DEPOT_STACK_RECORD_SIZE ) { +struct stack_record *stack = pool + offset; + + stack->handle.pool_index = pools_num; + stack->handle.offset = offset >>DEPOT_STACK_ALIGN ; + stack->handle.extra =0 ; + +if (i < records_in_pool -1 ) + stack->next = (void *)stack +DEPOT_STACK_RECORD_SIZE ; +else + stack->next =NULL ; + } + +/* Link stack records into the freelist. */ +WARN_ON (next_stack); + next_stack = pool; + +/* Save reference to the pool to be used by depot_fetch_stack. */ + stack_pools[pools_num] = pool; + +/* +* WRITE_ONCE pairs with potential concurrent read in +* depot_fetch_stack. +*/ +WRITE_ONCE (pools_num, pools_num +1 ); +} +/* Keeps the preallocated memory to be used for a new stack depot pool. */ static void depot_keep_new_pool (void **prealloc) {
@@ -237,7 +272,7 @@ static void depot_keep_new_pool(void **prealloc)* Use the preallocated memory for the new pool * as long as we do not exceed the maximum number of pools. */ -if (pool_index +1 <DEPOT_MAX_POOLS ) { +if (pools_num <DEPOT_MAX_POOLS ) { new_pool = *prealloc; *prealloc =NULL ; }
@@ -252,45 +287,42 @@ static void depot_keep_new_pool(void **prealloc) }/* Updates refences to the current and the next stack depot pools. */ -static bool depot_update_pools (size_t required_size,void **prealloc) +static bool depot_update_pools (void **prealloc) { -/* Check if there is not enough space in the current pool. */ -if (unlikely (pool_offset + required_size >DEPOT_POOL_SIZE )) { -/* Bail out if we reached the pool limit. */ -if (unlikely (pool_index +1 >=DEPOT_MAX_POOLS )) { -WARN_ONCE (1 ,"Stack depot reached limit capacity" ); -return false; - } +/* Check if we still have objects in the freelist. */ +if (next_stack) + goto out_keep_prealloc; -/* -* Move on to the new pool. -* WRITE_ONCE pairs with potential concurrent read in -* stack_depot_fetch. -*/ -WRITE_ONCE (pool_index, pool_index +1 ); - stack_pools[pool_index] = new_pool; +/* Check if we have a new pool saved and use it. */ +if (new_pool) { +depot_init_pool (new_pool); new_pool =NULL ; - pool_offset =0 ; -/* -* If the maximum number of pools is not reached, take note -* that yet another new pool needs to be allocated. -* smp_store_release pairs with smp_load_acquire in -* stack_depot_save. -*/ -if (pool_index +1 <DEPOT_MAX_POOLS ) +/* Take note that we might need a new new_pool. */ +if (pools_num <DEPOT_MAX_POOLS )smp_store_release (&new_pool_required,1 ); + +/* Try keeping the preallocated memory for new_pool. */ + goto out_keep_prealloc; + } + +/* Bail out if we reached the pool limit. */ +if (unlikely (pools_num >=DEPOT_MAX_POOLS )) { +WARN_ONCE (1 ,"Stack depot reached limit capacity" ); +return false; } -/* Check if the current pool is not yet allocated. */ -if (*prealloc && stack_pools[pool_index] ==NULL ) { -/* Use the preallocated memory for the current pool. */ - stack_pools[pool_index] = *prealloc; +/* Check if we have preallocated memory and use it. */ +if (*prealloc) { +depot_init_pool (*prealloc); *prealloc =NULL ;return true; } -/* Otherwise, try using the preallocated memory for a new pool. */ +return false; + +out_keep_prealloc: +/* Keep the preallocated memory for a new pool if required. */ if (*prealloc)depot_keep_new_pool (prealloc);return true;
@@ -301,35 +333,35 @@ static struct stack_record * depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) { struct stack_record *stack; -size_t required_size =DEPOT_STACK_RECORD_SIZE ;/* Update current and new pools if required and possible. */ -if (!depot_update_pools (required_size, prealloc)) +if (!depot_update_pools (prealloc))return NULL ; -/* Check if we have a pool to save the stack trace. */ -if (stack_pools[pool_index] ==NULL ) +/* Check if we have a stack record to save the stack trace. */ + stack = next_stack; +if (!stack)return NULL ; +/* Advance the freelist. */ + next_stack = stack->next; +/* Limit number of saved frames to DEPOT_STACK_MAX_FRAMES. */ if (size >DEPOT_STACK_MAX_FRAMES ) size =DEPOT_STACK_MAX_FRAMES ;/* Save the stack trace. */ - stack = stack_pools[pool_index] + pool_offset; + stack->next =NULL ; stack->hash = hash; stack->size = size; - stack->handle.pool_index = pool_index; - stack->handle.offset = pool_offset >>DEPOT_STACK_ALIGN ; - stack->handle.extra =0 ; +/* stack->handle is already filled in by depot_init_pool. */ memcpy (stack->entries, entries,flex_array_size (stack, entries, size)); - pool_offset += required_size;/* * Let KMSAN know the stored stack record is initialized. This shall * prevent false positive reports if instrumented code accesses it. */ -kmsan_unpoison_memory (stack, required_size); +kmsan_unpoison_memory (stack,DEPOT_STACK_RECORD_SIZE );return stack; }
@@ -339,16 +371,16 @@ static struct stack_record *depot_fetch_stack(depot_stack_handle_t handle)union handle_parts parts = { .handle = handle };/* * READ_ONCE pairs with potential concurrent write in -* depot_update_pools. +* depot_init_pool. */ -int pool_index_cached =READ_ONCE (pool_index); +int pools_num_cached =READ_ONCE (pools_num);void *pool;size_t offset = parts.offset <<DEPOT_STACK_ALIGN ;struct stack_record *stack; -if (parts.pool_index > pool_index_cached) { +if (parts.pool_index > pools_num_cached) {WARN (1 ,"pool index %d out of bounds (%d) for stack id %08x\n" , - parts.pool_index, pool_index_cached, handle); + parts.pool_index, pools_num_cached, handle);return NULL ; }
Signature · 1 line
2.25.1
PATCH 11/15 stackdepot: use read/write lock
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Currently, stack depot uses the following locking scheme:
1. Lock-free accesses when looking up a stack record, which allows to have multiple users to look up records in parallel;
2. Spinlock for protecting the stack depot pools and the hash table when adding a new record.
For implementing the eviction of stack traces from stack depot, the lock-free approach is not going to work anymore, as we will need to be able to also remove records from the hash table.
Convert the spinlock into a read/write lock, and drop the atomic accesses, as they are no longer required.
Looking up stack traces is now protected by the read lock and adding new records - by the write lock. One of the following patches will add a new function for evicting stack records, which will be protected by the write lock as well.
With this change, multiple users can still look up records in parallel.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
--- lib/stackdepot.c | 76 ++++++++++++++++++++++-------------------------- 1 file changed, 35 insertions(+), 41 deletions(-)
lib/stackdepot.c +35 -41
@@ -23,6 +23,7 @@#include <linux/percpu.h> #include <linux/printk.h> #include <linux/slab.h> +#include <linux/spinlock.h> #include <linux/stacktrace.h> #include <linux/stackdepot.h> #include <linux/string.h>
@@ -92,15 +93,15 @@ static void *new_pool;static int pools_num;/* Next stack in the freelist of stack records within stack_pools. */ static struct stack_record *next_stack; -/* Lock that protects the variables above. */ -static DEFINE_RAW_SPINLOCK (pool_lock);/* * Stack depot tries to keep an extra pool allocated even before it runs out * of space in the currently used pool. This flag marks whether this extra pool * needs to be allocated. It has the value 0 when either an extra pool is not * yet allocated or if the limit on the number of pools is reached. */ -static int new_pool_required =1 ; +static bool new_pool_required = true; +/* Lock that protects the variables above. */ +static DEFINE_RWLOCK (pool_rwlock);static int __init disable_stack_depot (char *str) {
@@ -248,12 +249,7 @@ static void depot_init_pool(void *pool)/* Save reference to the pool to be used by depot_fetch_stack. */ stack_pools[pools_num] = pool; - -/* -* WRITE_ONCE pairs with potential concurrent read in -* depot_fetch_stack. -*/ -WRITE_ONCE (pools_num, pools_num +1 ); + pools_num++; }/* Keeps the preallocated memory to be used for a new stack depot pool. */
@@ -262,10 +258,8 @@ static void depot_keep_new_pool(void **prealloc)/* * If a new pool is already saved or the maximum number of * pools is reached, do not use the preallocated memory. -* READ_ONCE is only used to mark the variable as atomic, -* there are no concurrent writes. */ -if (!READ_ONCE (new_pool_required)) +if (!new_pool_required)return ;/*
@@ -281,9 +275,8 @@ static void depot_keep_new_pool(void **prealloc)* At this point, either a new pool is kept or the maximum * number of pools is reached. In either case, take note that * keeping another pool is not required. -* smp_store_release pairs with smp_load_acquire in stack_depot_save. */ -smp_store_release (&new_pool_required,0 ); + new_pool_required = false; }/* Updates refences to the current and the next stack depot pools. */
@@ -300,7 +293,7 @@ static bool depot_update_pools(void **prealloc)/* Take note that we might need a new new_pool. */ if (pools_num <DEPOT_MAX_POOLS ) -smp_store_release (&new_pool_required,1 ); + new_pool_required = true;/* Try keeping the preallocated memory for new_pool. */ goto out_keep_prealloc;
@@ -369,18 +362,13 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)static struct stack_record *depot_fetch_stack (depot_stack_handle_t handle) {union handle_parts parts = { .handle = handle }; -/* -* READ_ONCE pairs with potential concurrent write in -* depot_init_pool. -*/ -int pools_num_cached =READ_ONCE (pools_num);void *pool;size_t offset = parts.offset <<DEPOT_STACK_ALIGN ;struct stack_record *stack; -if (parts.pool_index > pools_num_cached) { +if (parts.pool_index > pools_num) {WARN (1 ,"pool index %d out of bounds (%d) for stack id %08x\n" , - parts.pool_index, pools_num_cached, handle); + parts.pool_index, pools_num, handle);return NULL ; }
@@ -439,6 +427,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,depot_stack_handle_t handle =0 ;struct page *page =NULL ;void *prealloc =NULL ; +bool need_alloc = false;unsigned long flags;u32 hash;
@@ -458,22 +447,26 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, hash =hash_stack (entries, nr_entries); bucket = &stack_table[hash & stack_hash_mask]; -/* -* Fast path: look the stack trace up without locking. -* smp_load_acquire pairs with smp_store_release to |bucket| below. -*/ - found =find_stack (smp_load_acquire (bucket), entries, nr_entries, hash); -if (found) +read_lock_irqsave (&pool_rwlock, flags); + +/* Fast path: look the stack trace up without full locking. */ + found =find_stack (*bucket, entries, nr_entries, hash); +if (found) { +read_unlock_irqrestore (&pool_rwlock, flags); goto exit; + } + +/* Take note if another stack pool needs to be allocated. */ +if (new_pool_required) + need_alloc = true; + +read_unlock_irqrestore (&pool_rwlock, flags);/* -* Check if another stack pool needs to be allocated. If so, allocate -* the memory now: we won't be able to do that under the lock. -* -* smp_load_acquire pairs with smp_store_release -* in depot_update_pools and depot_keep_new_pool. +* Allocate memory for a new pool if required now: +* we won't be able to do that under the lock. */ -if (unlikely (can_alloc &&smp_load_acquire (&new_pool_required))) { +if (unlikely (can_alloc && need_alloc)) {/* * Zero out zone modifiers, as we don't have specific zone * requirements. Keep the flags related to allocation in atomic
@@ -487,7 +480,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, prealloc =page_address (page); } -raw_spin_lock_irqsave (&pool_lock, flags); +write_lock_irqsave (&pool_rwlock, flags); found =find_stack (*bucket, entries, nr_entries, hash);if (!found) {
@@ -496,11 +489,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,if (new) { new->next = *bucket; -/* -* smp_store_release pairs with smp_load_acquire -* from |bucket| above. -*/ -smp_store_release (bucket, new); + *bucket = new; found = new; } }else if (prealloc) {
@@ -511,7 +500,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,depot_keep_new_pool (&prealloc); } -raw_spin_unlock_irqrestore (&pool_lock, flags); +write_unlock_irqrestore (&pool_rwlock, flags); exit:if (prealloc) {/* Stack depot didn't use this memory, free it. */
@@ -535,6 +524,7 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle, unsigned long **entries) {struct stack_record *stack; +unsigned long flags; *entries =NULL ;/*
@@ -546,8 +536,12 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle,if (!handle || stack_depot_disabled)return 0 ; +read_lock_irqsave (&pool_rwlock, flags); + stack =depot_fetch_stack (handle); +read_unlock_irqrestore (&pool_rwlock, flags); + *entries = stack->entries;return stack->size; }
Signature · 1 line
2.25.1
PATCH 12/15 stackdepot: add refcount for records
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Add a reference counter for how many times a stack records has been added to stack depot.
Do no yet decrement the refcount, this is implemented in one of the following patches.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
--- lib/stackdepot.c | 4 ++++ 1 file changed, 4 insertions(+)
lib/stackdepot.c +4 -0
@@ -22,6 +22,7 @@#include <linux/mutex.h> #include <linux/percpu.h> #include <linux/printk.h> +#include <linux/refcount.h> #include <linux/slab.h> #include <linux/spinlock.h> #include <linux/stacktrace.h>
@@ -60,6 +61,7 @@ struct stack_record {u32 hash;/* Hash in hash table */ u32 size;/* Number of stored frames */ union handle_parts handle; +refcount_t count;unsigned long entries[DEPOT_STACK_MAX_FRAMES ];/* Frames */ };
@@ -348,6 +350,7 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) stack->hash = hash; stack->size = size;/* stack->handle is already filled in by depot_init_pool. */ +refcount_set (&stack->count,1 );memcpy (stack->entries, entries,flex_array_size (stack, entries, size));/*
@@ -452,6 +455,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,/* Fast path: look the stack trace up without full locking. */ found =find_stack (*bucket, entries, nr_entries, hash);if (found) { +refcount_inc (&found->count);read_unlock_irqrestore (&pool_rwlock, flags); goto exit; }
Signature · 1 line
2.25.1
PATCH 13/15 stackdepot: add backwards links to hash table buckets
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Maintain links in the stack records to previous entries within the hash table buckets.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
--- lib/stackdepot.c | 4 ++++ 1 file changed, 4 insertions(+)
lib/stackdepot.c +4 -0
@@ -58,6 +58,7 @@ union handle_parts {struct stack_record {struct stack_record *next;/* Link in hash table or freelist */ +struct stack_record *prev;/* Link in hash table */ u32 hash;/* Hash in hash table */ u32 size;/* Number of stored frames */ union handle_parts handle;
@@ -493,6 +494,9 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,if (new) { new->next = *bucket; + new->prev =NULL ; +if (*bucket) + (*bucket)->prev = new; *bucket = new; found = new; }
Signature · 1 line
2.25.1
PATCH 14/15 stackdepot: allow users to evict stack traces
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Add stack_depot_evict, a function that decrements a reference counter on a stack record and removes it from the stack depot once the counter reaches 0.
Internally, when removing a stack record, the function unlinks it from the hash table bucket and returns to the freelist.
With this change, the users of stack depot can call stack_depot_evict when keeping a stack trace in the stack depot is not needed anymore. This allows avoiding polluting the stack depot with irrelevant stack traces and thus have more space to store the relevant ones before the stack depot reaches its capacity.
--- include/linux/stackdepot.h | 11 ++++++++++ lib/stackdepot.c | 43 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+)
include/linux/stackdepot.h +11 -0
@@ -121,6 +121,17 @@ depot_stack_handle_t stack_depot_save(unsigned long *entries,unsigned int stack_depot_fetch (depot_stack_handle_t handle,unsigned long **entries); +/** +* stack_depot_evict - Drop a reference to a stack trace from stack depot +* +* @handle: Stack depot handle returned from stack_depot_save() +* +* The stack trace gets fully removed from stack depot once all references +* to it has been dropped (once the number of stack_depot_evict calls matches +* the number of stack_depot_save calls for this stack trace). +*/ +void stack_depot_evict (depot_stack_handle_t handle); +/** * stack_depot_print - Print a stack trace from stack depot *
lib/stackdepot.c +43 -0
55 lines not on this page · raw message
Signature · 1 line
2.25.1
PATCH 15/15 kasan: use stack_depot_evict for tag-based modes
In reply to [email protected]From: Andrey Konovalov <[email protected]>
Evict stack traces from the stack depot for the tag-based KASAN modes once they are evicted from the stack ring.
--- mm/kasan/tags.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
mm/kasan/tags.c +6 -1
@@ -96,7 +96,7 @@ static void save_stack_info(struct kmem_cache *cache, void *object, gfp_t gfp_flags, bool is_free) {unsigned long flags; -depot_stack_handle_t stack; +depot_stack_handle_t stack, old_stack;u64 pos;struct kasan_stack_ring_entry *entry;void *old_ptr;
@@ -120,6 +120,8 @@ static void save_stack_info(struct kmem_cache *cache, void *object,if (!try_cmpxchg (&entry->ptr, &old_ptr,STACK_RING_BUSY_PTR )) goto next;/* Busy slot. */ + old_stack =READ_ONCE (entry->stack); +WRITE_ONCE (entry->size, cache->object_size);WRITE_ONCE (entry->pid, current->pid);WRITE_ONCE (entry->stack, stack);
@@ -131,6 +133,9 @@ static void save_stack_info(struct kmem_cache *cache, void *object,smp_store_release (&entry->ptr, (s64 )object);read_unlock_irqrestore (&stack_ring.lock, flags); + +if (old_stack) +stack_depot_evict (old_stack); }void kasan_save_alloc_info (struct kmem_cache *cache,void *object,gfp_t flags)
Signature · 1 line
2.25.1
Re: [PATCH 01/15] stackdepot: check disabled flag when fetching
In reply to [email protected]Quoted 7 lines · On Tue, Aug 29, 2023 at 7:11 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
Do not try fetching a stack trace from the stack depot if the
stack_depot_disabledflag is enabled.Signed-off-by Andrey Konovalov <[email protected]>
Re: [PATCH 02/15] stackdepot: simplify __stack_depot_save
In reply to [email protected]Quoted 10 lines · On Tue, Aug 29, 2023 at 7:11 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
The retval local variable in
__stack_depot_savehas the union typehandle_parts, but the function never uses anything but the union's handle field.Define retval simply as
depot_stack_handle_tto simplify the code.Signed-off-by Andrey Konovalov <[email protected]>
Re: [PATCH 03/15] stackdepot: drop valid bit from handles
In reply to [email protected]Quoted 4 lines · On Tue, Aug 29, 2023 at 7:11 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
Stack depot doesn't use the valid bit in handles in any way, so drop it.
Good catch!
Quoted 1 line
Signed-off-by Andrey Konovalov <[email protected]>
Quoted 6 lines · On 8/29/23 19:11, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Currently, the stack depot grows indefinitely until it reaches its capacity. Once that happens, the stack depot stops saving new stack traces.
Quoted 8 lines
This creates a problem for using the stack depot for in-field testing and in production.
For such uses, an ideal stack trace storage should:
1. Allow saving fresh stack traces on systems with a large uptime while limiting the amount of memory used to store the traces;
2. Have a low performance impact.
I wonder if there's also another thing to consider for the future:
3. With the number of stackdepot users increasing, each having their distinct set of stacks from others, would it make sense to create separate "storage instance" for each user instead of putting everything in a single shared one?
In any case, evicting support is a good development, thanks!
Quoted 69 lines
Implementing #1 in the stack depot is impossible with the current keep-forever approach. This series targets to address that. Issue #2 is left to be addressed in a future series.
This series changes the stack depot implementation to allow evicting unneeded stack traces from the stack depot. The users of the stack depot can do that via a new
stack_depot_evictAPI.Internal changes to the stack depot code include:
1. Storing stack traces in 32-frame-sized slots (vs precisely-sized slots in the current implementation);
2. Keeping available slots in a freelist (vs keeping an offset to the next free slot);
3. Using a read/write lock for synchronization (vs a lock-free approach combined with a spinlock).This series also integrates the eviction functionality in the tag-based KASAN modes. (I will investigate integrating it into the Generic mode as well in the following iterations of this series.)
Despite wasting some space on rounding up the size of each stack record to 32 frames, with this change, the tag-based KASAN modes end up consuming ~5% less memory in stack depot during boot (with the default stack ring size of 32k entries). The reason for this is the eviction of irrelevant stack traces from the stack depot, which frees up space for other stack traces.
For other tools that heavily rely on the stack depot, like Generic KASAN and KMSAN, this change leads to the stack depot capacity being reached sooner than before. However, as these tools are mainly used in fuzzing scenarios where the kernel is frequently rebooted, this outcome should be acceptable.
There is no measurable boot time performace impact of these changes for KASAN on x86-64. I haven't done any tests for arm64 modes (the stack depot without performance optimizations is not suitable for intended use of those anyway), but I expect a similar result. Obtaining and copying stack trace frames when saving them into stack depot is what takes the most time.
This series does not yet provide a way to configure the maximum size of the stack depot externally (e.g. via a command-line parameter). This will either be added in the following iterations of this series (if the used approach gets approval) or will be added together with the performance improvement changes.
Andrey Konovalov (15):
stackdepot: check disabled flag when fetching
stackdepot: simplify__stack_depot_save
stackdepot: drop valid bit from handles
stackdepot: adddepot_fetch_stackhelper
stackdepot: use fixed-sized slots for stack records
stackdepot: fix and clean-up atomic annotations
stackdepot: rework helpers fordepot_alloc_stack
stackdepot: renamenext_pool_requiredtonew_pool_required
stackdepot: store next pool pointer innew_pool
stackdepot: store free stack records in a freelist
stackdepot: use read/write lock
stackdepot: add refcount for records
stackdepot: add backwards links to hash table buckets
stackdepot: allow users to evict stack traces
kasan: usestack_depot_evictfor tag-based modesinclude/linux/stackdepot.h | 11 ++ lib/stackdepot.c | 361 ++++++++++++++++++++++++------------- mm/kasan/tags.c | 7 +- 3 files changed, 249 insertions(+), 130 deletions(-)
Re: [PATCH 04/15] stackdepot: add depot_fetch_stack helper
In reply to [email protected]Quoted 10 lines · On Tue, Aug 29, 2023 at 7:11 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
Add a helper
depot_fetch_stackfunction that fetches the pointer to a stack record.With this change, all static depot_* functions now operate on stack pools and the exported stack_depot_* functions operate on the hash table.
Signed-off-by Andrey Konovalov <[email protected]>
(one nit below)
lib/stackdepot.c depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) · line 322
Quoted 6 lines
lib/stackdepot.c +6
-0+static struct stack_record *depot_fetch_stack (depot_stack_handle_t handle) +{ +union handle_parts parts = { .handle = handle }; +/* +* READ_ONCE pairs with potential concurrent write in +* depot_alloc_stack.
Nit: please change to "depot_alloc_stack()" for consistency with the rest of the comments.
Alexander Potapenko
reviewerRe: [PATCH 05/15] stackdepot: use fixed-sized slots for stack records
In reply to [email protected]Quoted 5 lines · On Tue, Aug 29, 2023 at 7:11 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
Instead of storing stack records in stack depot pools one right after another, use 32-frame-sized slots.
I am slightly concerned about the KMSAN use case here, which defines KMSAN_STACK_DEPTH to 64.
I don't have a comprehensive stack depth breakdown, but a quick poking around syzkaller.appspot.com shows several cases where the stacks are actually longer than 32 frames.
Can you add a config parameter for the stack depth instead of mandating 32 frames everywhere?
As a side note, kmsan_internal_chain_origin()
(https://elixir.bootlin.com/linux/latest/source/mm/kmsan/core.c#L214)
creates small 3-frame records in the stack depot to link two stacks together, which will add unnecessary stackdepot pressure. But this can be fixed by storing both the new stack trace and the link to the old stack trace in the same record.
Re: [PATCH 08/15] stackdepot: rename next_pool_required to new_pool_required
In reply to [email protected]Quoted 10 lines · On Tue, Aug 29, 2023 at 7:12 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
Rename
next_pool_requiredtonew_pool_required.This a purely code readability change: the following patch will change stack depot to store the pointer to the new pool in a separate variable, and "new" seems like a more logical name.
Signed-off-by Andrey Konovalov <[email protected]>
Re: [PATCH 06/15] stackdepot: fix and clean-up atomic annotations
In reply to [email protected]Quoted 26 lines · On Tue, Aug 29, 2023 at 07:11PM +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Simplify comments accompanying the use of atomic accesses in the stack depot code.
Also turn
smp_load_acquirefromnext_pool_requiredindepot_init_poolintoREAD_ONCE, as bothdepot_init_pooland the all smp_store_release's to this variable are executed under the stack depot lock.Signed-off-by Andrey Konovalov <[email protected]>---
This patch is not strictly required, as the atomic accesses are fully removed in one of the latter patches. However, I decided to keep the patch just in case we end up needing these atomics in the following iterations of this series.
--- lib/stackdepot.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-)lib/stackdepot.c +0
-0
lib/stackdepot.c static void depot_init_pool(void **prealloc) · line 230
Quoted 7 lines
lib/stackdepot.c +2
-2@@ -226,10 +226,10 @@ static void depot_init_pool(void **prealloc)/* * If the next pool is already initialized or the maximum number of * pools is reached, do not use the preallocated memory. -* smp_load_acquire() here pairs with smp_store_release() below and -* in depot_alloc_stack(). +* READ_ONCE is only used to mark the variable as atomic, +* there are no concurrent writes.
This doesn't make sense. If there are no concurrent writes, we should drop the marking, so that if there are concurrent writes, tools like KCSAN can tell us about it if our assumption was wrong.
Quoted 47 lines
lib/stackdepot.c +7
-8*/ -if (!smp_load_acquire (&next_pool_required)) +if (!READ_ONCE (next_pool_required))return ;/* Check if the current pool is not yet allocated. */ @@ -250,8 +250,8 @@ static void depot_init_pool(void **prealloc)* At this point, either the next pool is initialized or the * maximum number of pools is reached. In either case, take * note that initializing another pool is not required. -* This smp_store_release pairs with smp_load_acquire() above -* and in stack_depot_save(). +* smp_store_release pairs with smp_load_acquire in +* stack_depot_save. */ smp_store_release (&next_pool_required,0 ); }@@ -275,15 +275,15 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)/* * Move on to the next pool. * WRITE_ONCE pairs with potential concurrent read in -* stack_depot_fetch(). +* stack_depot_fetch. */ WRITE_ONCE (pool_index, pool_index +1 ); pool_offset =0 ;/* * If the maximum number of pools is not reached, take note * that the next pool needs to initialized. -* smp_store_release() here pairs with smp_load_acquire() in -* stack_depot_save() and depot_init_pool(). +* smp_store_release pairs with smp_load_acquire in +* stack_depot_save. */ if (pool_index +1 <DEPOT_MAX_POOLS )smp_store_release (&next_pool_required,1 );@@ -414,8 +414,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,/* * Fast path: look the stack trace up without locking. -* The smp_load_acquire() here pairs with smp_store_release() to -* |bucket| below. +* smp_load_acquire pairs with smp_store_release to |bucket| below. */ found =find_stack (smp_load_acquire (bucket), entries, nr_entries, hash);if (found)
lib/stackdepot.c depot_stack_handle_t __stack_depot_save(unsigned long *entries, · line 428
Quoted 7 lines
lib/stackdepot.c +2
-2@@ -425,8 +424,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,* Check if another stack pool needs to be initialized. If so, allocate * the memory now - we won't be able to do that under the lock. * -* The smp_load_acquire() here pairs with smp_store_release() to -* |next_pool_inited| in depot_alloc_stack() and depot_init_pool(). +* smp_load_acquire pairs with smp_store_release +* in depot_alloc_stack and depot_init_pool.
Reflow comment to match 80 cols used by comments elsewhere.
Quoted 17 lines
lib/stackdepot.c +2
-2*/ if (unlikely (can_alloc &&smp_load_acquire (&next_pool_required))) {/* @@ -452,8 +451,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,if (new) { new->next = *bucket;/* -* This smp_store_release() pairs with -* smp_load_acquire() from |bucket| above. +* smp_store_release pairs with smp_load_acquire +* from |bucket| above. */ smp_store_release (bucket, new); found = new;Signature · 1 line
2.25.1
Re: [PATCH 11/15] stackdepot: use read/write lock
In reply to [email protected]Quoted 49 lines · On Tue, Aug 29, 2023 at 07:11PM +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Currently, stack depot uses the following locking scheme:
1. Lock-free accesses when looking up a stack record, which allows to have multiple users to look up records in parallel;
2. Spinlock for protecting the stack depot pools and the hash table when adding a new record.For implementing the eviction of stack traces from stack depot, the lock-free approach is not going to work anymore, as we will need to be able to also remove records from the hash table.
Convert the spinlock into a read/write lock, and drop the atomic accesses, as they are no longer required.
Looking up stack traces is now protected by the read lock and adding new records - by the write lock. One of the following patches will add a new function for evicting stack records, which will be protected by the write lock as well.
With this change, multiple users can still look up records in parallel.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
Signed-off-by Andrey Konovalov <[email protected]>--- lib/stackdepot.c | 76 ++++++++++++++++++++++-------------------------- 1 file changed, 35 insertions(+), 41 deletions(-)lib/stackdepot.c +1
-2@@ -23,6 +23,7 @@#include <linux/percpu.h> #include <linux/printk.h> #include <linux/slab.h> +#include <linux/spinlock.h> #include <linux/stacktrace.h> #include <linux/stackdepot.h> #include <linux/string.h> @@ -92,15 +93,15 @@ static void *new_pool;static int pools_num;/* Next stack in the freelist of stack records within stack_pools. */ static struct stack_record *next_stack; -/* Lock that protects the variables above. */ -static DEFINE_RAW_SPINLOCK (pool_lock);
lib/stackdepot.c static void *new_pool; · line 104
Quoted 10 lines
lib/stackdepot.c +3
-1/* * Stack depot tries to keep an extra pool allocated even before it runs out * of space in the currently used pool. This flag marks whether this extra pool * needs to be allocated. It has the value 0 when either an extra pool is not * yet allocated or if the limit on the number of pools is reached. */ -static int new_pool_required =1 ; +static bool new_pool_required = true; +/* Lock that protects the variables above. */ +static DEFINE_RWLOCK (pool_rwlock);
Despite this being a rwlock, it'll introduce tons of (cache) contention for the common case (stack depot entry exists).
If creating new stack depot entries is only common during "warm-up" and then becomes exceedingly rare, I think a percpu-rwsem (read-lock is a CPU-local access, but write-locking is expensive) may be preferable.
Quoted 17 lines
lib/stackdepot.c +1
-6static int __init disable_stack_depot (char *str) {@@ -248,12 +249,7 @@ static void depot_init_pool(void *pool)/* Save reference to the pool to be used by depot_fetch_stack. */ stack_pools[pools_num] = pool; - -/* -* WRITE_ONCE pairs with potential concurrent read in -* depot_fetch_stack. -*/ -WRITE_ONCE (pools_num, pools_num +1 ); + pools_num++; }/* Keeps the preallocated memory to be used for a new stack depot pool. */
lib/stackdepot.c static void depot_keep_new_pool(void **prealloc) · line 262
Quoted 8 lines
lib/stackdepot.c +1
-3@@ -262,10 +258,8 @@ static void depot_keep_new_pool(void **prealloc)/* * If a new pool is already saved or the maximum number of * pools is reached, do not use the preallocated memory. -* READ_ONCE is only used to mark the variable as atomic, -* there are no concurrent writes. */ -if (!READ_ONCE (new_pool_required)) +if (!new_pool_required)
In my comment for the other patch I already suggested this change. Maybe move it there.
Quoted 25 lines
lib/stackdepot.c +2
-3return ;/* @@ -281,9 +275,8 @@ static void depot_keep_new_pool(void **prealloc)* At this point, either a new pool is kept or the maximum * number of pools is reached. In either case, take note that * keeping another pool is not required. -* smp_store_release pairs with smp_load_acquire in stack_depot_save. */ -smp_store_release (&new_pool_required,0 ); + new_pool_required = false; }/* Updates refences to the current and the next stack depot pools. */ @@ -300,7 +293,7 @@ static bool depot_update_pools(void **prealloc)/* Take note that we might need a new new_pool. */ if (pools_num <DEPOT_MAX_POOLS ) -smp_store_release (&new_pool_required,1 ); + new_pool_required = true;/* Try keeping the preallocated memory for new_pool. */ goto out_keep_prealloc;@@ -369,18 +362,13 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)static struct stack_record *depot_fetch_stack (depot_stack_handle_t handle)
lib/stackdepot.c depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) · line 367
Quoted 10 lines
lib/stackdepot.c +0
-5{union handle_parts parts = { .handle = handle }; -/* -* READ_ONCE pairs with potential concurrent write in -* depot_init_pool. -*/ -int pools_num_cached =READ_ONCE (pools_num);void *pool;size_t offset = parts.offset <<DEPOT_STACK_ALIGN ;struct stack_record *stack;
I'd add lockdep assertions to check that the lock is held appropriately when entering various helper functions that don't actually take the lock. Similarly for places that should not have the lock held you could assert the lock is not held.
Quoted 110 lines
lib/stackdepot.c +27
-21-if (parts.pool_index > pools_num_cached) { +if (parts.pool_index > pools_num) {WARN (1 ,"pool index %d out of bounds (%d) for stack id %08x\n" , - parts.pool_index, pools_num_cached, handle); + parts.pool_index, pools_num, handle);return NULL ; }@@ -439,6 +427,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,depot_stack_handle_t handle =0 ;struct page *page =NULL ;void *prealloc =NULL ; +bool need_alloc = false;unsigned long flags;u32 hash;@@ -458,22 +447,26 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, hash =hash_stack (entries, nr_entries); bucket = &stack_table[hash & stack_hash_mask]; -/* -* Fast path: look the stack trace up without locking. -* smp_load_acquire pairs with smp_store_release to |bucket| below. -*/ - found =find_stack (smp_load_acquire (bucket), entries, nr_entries, hash); -if (found) +read_lock_irqsave (&pool_rwlock, flags); + +/* Fast path: look the stack trace up without full locking. */ + found =find_stack (*bucket, entries, nr_entries, hash); +if (found) { +read_unlock_irqrestore (&pool_rwlock, flags); goto exit; + } + +/* Take note if another stack pool needs to be allocated. */ +if (new_pool_required) + need_alloc = true; + +read_unlock_irqrestore (&pool_rwlock, flags);/* -* Check if another stack pool needs to be allocated. If so, allocate -* the memory now: we won't be able to do that under the lock. -* -* smp_load_acquire pairs with smp_store_release -* in depot_update_pools and depot_keep_new_pool. +* Allocate memory for a new pool if required now: +* we won't be able to do that under the lock. */ -if (unlikely (can_alloc &&smp_load_acquire (&new_pool_required))) { +if (unlikely (can_alloc && need_alloc)) {/* * Zero out zone modifiers, as we don't have specific zone * requirements. Keep the flags related to allocation in atomic @@ -487,7 +480,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, prealloc =page_address (page); } -raw_spin_lock_irqsave (&pool_lock, flags); +write_lock_irqsave (&pool_rwlock, flags); found =find_stack (*bucket, entries, nr_entries, hash);if (!found) {@@ -496,11 +489,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,if (new) { new->next = *bucket; -/* -* smp_store_release pairs with smp_load_acquire -* from |bucket| above. -*/ -smp_store_release (bucket, new); + *bucket = new; found = new; } }else if (prealloc) {@@ -511,7 +500,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,depot_keep_new_pool (&prealloc); } -raw_spin_unlock_irqrestore (&pool_lock, flags); +write_unlock_irqrestore (&pool_rwlock, flags); exit:if (prealloc) {/* Stack depot didn't use this memory, free it. */ @@ -535,6 +524,7 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle, unsigned long **entries) {struct stack_record *stack; +unsigned long flags; *entries =NULL ;/* @@ -546,8 +536,12 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle,if (!handle || stack_depot_disabled)return 0 ; +read_lock_irqsave (&pool_rwlock, flags); + stack =depot_fetch_stack (handle); +read_unlock_irqrestore (&pool_rwlock, flags); + *entries = stack->entries;return stack->size; }Signature · 1 line
2.25.1
Re: [PATCH 14/15] stackdepot: allow users to evict stack traces
In reply to [email protected]Quoted 26 lines · On Tue, Aug 29, 2023 at 07:11PM +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Add
stack_depot_evict, a function that decrements a reference counter on a stack record and removes it from the stack depot once the counter reaches 0.Internally, when removing a stack record, the function unlinks it from the hash table bucket and returns to the freelist.
With this change, the users of stack depot can call
stack_depot_evictwhen keeping a stack trace in the stack depot is not needed anymore. This allows avoiding polluting the stack depot with irrelevant stack traces and thus have more space to store the relevant ones before the stack depot reaches its capacity.Signed-off-by Andrey Konovalov <[email protected]>--- include/linux/stackdepot.h | 11 ++++++++++ lib/stackdepot.c | 43 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+)include/linux/stackdepot.h +0
-0
include/linux/stackdepot.h depot_stack_handle_t stack_depot_save(unsigned long *entries, · line 129
Quoted 9 lines
include/linux/stackdepot.h +6
-0@@ -121,6 +121,17 @@ depot_stack_handle_t stack_depot_save(unsigned long *entries,unsigned int stack_depot_fetch (depot_stack_handle_t handle,unsigned long **entries); +/** +* stack_depot_evict - Drop a reference to a stack trace from stack depot +* +* @handle: Stack depot handle returned from stack_depot_save() +* +* The stack trace gets fully removed from stack depot once all references
"gets fully removed" -> "is evicted" ?
include/linux/stackdepot.h depot_stack_handle_t stack_depot_save(unsigned long *entries, · line 130
Quoted 1 line
include/linux/stackdepot.h +1
-0+* to it has been dropped (once the number of stack_depot_evict calls matches
"has been" -> "have been"
Quoted 71 lines
include/linux/stackdepot.h +4
-0+* the number of stack_depot_save calls for this stack trace). +*/ +void stack_depot_evict (depot_stack_handle_t handle); +/** * stack_depot_print - Print a stack trace from stack depot * lib/stackdepot.c +43
-0@@ -384,6 +384,13 @@ static struct stack_record *depot_fetch_stack(depot_stack_handle_t handle)return stack; } +/* Frees stack into the freelist. */ +static void depot_free_stack (struct stack_record *stack) +{ + stack->next = next_stack; + next_stack = stack; +} +/* Calculates the hash for a stack. */ static inline u32 hash_stack (unsigned long *entries,unsigned int size) {@@ -555,6 +562,42 @@ unsigned int stack_depot_fetch(depot_stack_handle_t handle, }EXPORT_SYMBOL_GPL (stack_depot_fetch); +void stack_depot_evict (depot_stack_handle_t handle) +{ +struct stack_record *stack, **bucket; +unsigned long flags; + +if (!handle || stack_depot_disabled) +return ; + +write_lock_irqsave (&pool_rwlock, flags); + + stack =depot_fetch_stack (handle); +if (WARN_ON (!stack)) + goto out; + +if (refcount_dec_and_test (&stack->count)) { +/* Drop stack from the hash table. */ +if (stack->next) + stack->next->prev = stack->prev; +if (stack->prev) + stack->prev->next = stack->next; +else { + bucket = &stack_table[stack->hash & stack_hash_mask]; + *bucket = stack->next; + } + stack->next =NULL ; + stack->prev =NULL ; + +/* Free stack. */ +depot_free_stack (stack); + } + +out: +write_unlock_irqrestore (&pool_rwlock, flags); +} +EXPORT_SYMBOL_GPL (stack_depot_evict); +void stack_depot_print (depot_stack_handle_t stack) {unsigned long *entries;Signature · 1 line
2.25.1
Re: [PATCH 13/15] stackdepot: add backwards links to hash table buckets
In reply to [email protected]Quoted 18 lines · On Tue, Aug 29, 2023 at 07:11PM +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Maintain links in the stack records to previous entries within the hash table buckets.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
Signed-off-by Andrey Konovalov <[email protected]>--- lib/stackdepot.c | 4 ++++ 1 file changed, 4 insertions(+)lib/stackdepot.c +0
-0
lib/stackdepot.c union handle_parts { · line 61
Quoted 4 lines
lib/stackdepot.c +1
-0@@ -58,6 +58,7 @@ union handle_parts {struct stack_record {struct stack_record *next;/* Link in hash table or freelist */ +struct stack_record *prev;/* Link in hash table */
At this point this could be a normal list_head? Then you don't have to roll your own doubly-linked list manipulation (and benefit from things like CONFIG_LIST_DEBUG).
Quoted 16 lines
lib/stackdepot.c +3
-0u32 hash;/* Hash in hash table */ u32 size;/* Number of stored frames */ union handle_parts handle;@@ -493,6 +494,9 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,if (new) { new->next = *bucket; + new->prev =NULL ; +if (*bucket) + (*bucket)->prev = new; *bucket = new; found = new; }Signature · 1 line
2.25.1
Re: [PATCH 12/15] stackdepot: add refcount for records
In reply to [email protected]Quoted 45 lines · On Tue, Aug 29, 2023 at 07:11PM +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Add a reference counter for how many times a stack records has been added to stack depot.
Do no yet decrement the refcount, this is implemented in one of the following patches.
This is preparatory patch for implementing the eviction of stack records from the stack depot.
Signed-off-by Andrey Konovalov <[email protected]>--- lib/stackdepot.c | 4 ++++ 1 file changed, 4 insertions(+)lib/stackdepot.c +3
-0@@ -22,6 +22,7 @@#include <linux/mutex.h> #include <linux/percpu.h> #include <linux/printk.h> +#include <linux/refcount.h> #include <linux/slab.h> #include <linux/spinlock.h> #include <linux/stacktrace.h> @@ -60,6 +61,7 @@ struct stack_record {u32 hash;/* Hash in hash table */ u32 size;/* Number of stored frames */ union handle_parts handle; +refcount_t count;unsigned long entries[DEPOT_STACK_MAX_FRAMES ];/* Frames */ };@@ -348,6 +350,7 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) stack->hash = hash; stack->size = size;/* stack->handle is already filled in by depot_init_pool. */ +refcount_set (&stack->count,1 );memcpy (stack->entries, entries,flex_array_size (stack, entries, size));/*
lib/stackdepot.c depot_stack_handle_t __stack_depot_save(unsigned long *entries, · line 458
Quoted 4 lines
lib/stackdepot.c +1
-0@@ -452,6 +455,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,/* Fast path: look the stack trace up without full locking. */ found =find_stack (*bucket, entries, nr_entries, hash);if (found) { +refcount_inc (&found->count);
If someone doesn't use stack_depot_evict(), and the refcount eventually overflows, it'll do a WARN (per refcount_warn_saturate()).
I think the interface needs to be different:
stack_depot_get(): increments refcount (could be inline if just wrapper around refcount_inc())
stack_depot_put(): what stack_depot_evict() currently does
Then it's clear that if someone uses either stack_depot_get() or _put() that these need to be balanced. Not using either will result in the old behaviour of never evicting an entry.
Quoted 6 lines
lib/stackdepot.c +0
-0read_unlock_irqrestore (&pool_rwlock, flags); goto exit; }Signature · 1 line
2.25.1
Re: [PATCH 15/15] kasan: use stack_depot_evict for tag-based modes
In reply to [email protected]Quoted 24 lines · On Tue, Aug 29, 2023 at 07:11PM +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Evict stack traces from the stack depot for the tag-based KASAN modes once they are evicted from the stack ring.
Signed-off-by Andrey Konovalov <[email protected]>--- mm/kasan/tags.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)mm/kasan/tags.c +1
-1@@ -96,7 +96,7 @@ static void save_stack_info(struct kmem_cache *cache, void *object, gfp_t gfp_flags, bool is_free) {unsigned long flags; -depot_stack_handle_t stack; +depot_stack_handle_t stack, old_stack;u64 pos;struct kasan_stack_ring_entry *entry;void *old_ptr;
mm/kasan/tags.c static void save_stack_info(struct kmem_cache *cache, void *object, · line 123
Quoted 4 lines
mm/kasan/tags.c +1
-0@@ -120,6 +120,8 @@ static void save_stack_info(struct kmem_cache *cache, void *object,if (!try_cmpxchg (&entry->ptr, &old_ptr,STACK_RING_BUSY_PTR )) goto next;/* Busy slot. */ + old_stack =READ_ONCE (entry->stack);
Why READ_ONCE? Is it possible that there is a concurrent writer once the slot has been "locked" with STACK_RING_BUSY_PTR?
If there is no concurrency, it would be clearer to leave it unmarked and add a comment to that effect. (I also think a comment would be good to say what the WRITE_ONCE below pair with, because at this point I've forgotten.)
Quoted 16 lines
mm/kasan/tags.c +3
-0WRITE_ONCE (entry->size, cache->object_size);WRITE_ONCE (entry->pid, current->pid);WRITE_ONCE (entry->stack, stack);@@ -131,6 +133,9 @@ static void save_stack_info(struct kmem_cache *cache, void *object,smp_store_release (&entry->ptr, (s64 )object);read_unlock_irqrestore (&stack_ring.lock, flags); + +if (old_stack) +stack_depot_evict (old_stack); }void kasan_save_alloc_info (struct kmem_cache *cache,void *object,gfp_t flags)Signature · 1 line
2.25.1
Re: [PATCH 12/15] stackdepot: add refcount for records
In reply to [email protected]Quoted 56 lines · On Tue, 2023-08-29 at 19:11 +0200, [email protected] wrote:
From: Andrey Konovalov <[email protected]>
Add a reference counter for how many times a stack records has been added
to stack depot.Do no yet decrement the refcount, this is implemented in one of the following patches.
This is preparatory patch for implementing the eviction of stack records
from the stack depot.Signed-off-by Andrey Konovalov <[email protected]>--- lib/stackdepot.c | 4 ++++ 1 file changed, 4 insertions(+)lib/stackdepot.c +3
-0@@ -22,6 +22,7 @@#include <linux/mutex.h> #include <linux/percpu.h> #include <linux/printk.h> +#include <linux/refcount.h> #include <linux/slab.h> #include <linux/spinlock.h> #include <linux/stacktrace.h> @@ -60,6 +61,7 @@ struct stack_record {u32 hash;/* Hash in hash table */ u32 size;/* Number of stored frames */ union handle_parts handle; +refcount_t count;unsigned long entries[DEPOT_STACK_MAX_FRAMES ];/* Frames */ };@@ -348,6 +350,7 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) stack->hash = hash; stack->size = size;/* stack->handle is already filled in by depot_init_pool. */ +refcount_set (&stack->count,1 );memcpy (stack->entries, entries,flex_array_size (stack, entries, size));lib/stackdepot.c +1
-0/* @@ -452,6 +455,7 @@ depot_stack_handle_t __stack_depot_save(unsignedlong *entries,/* Fast path: look the stack trace up without full locking. */ found =find_stack (*bucket, entries, nr_entries, hash);if (found) { +refcount_inc (&found->count);read_unlock_irqrestore (&pool_rwlock, flags); goto exit;
Quoted 1 line
}
Hi Andrey,
There are two find_stack() function calls in __stack_depot_save().
Maybe we need to add refcount_inc() for both two find_stack()?
Thanks,
Kuan-Ying Lee
Andrey Konovalov
reviewerQuoted 7 lines · Vlastimil Babka
I wonder if there's also another thing to consider for the future:
3. With the number of stackdepot users increasing, each having their distinct set of stacks from others, would it make sense to create separate "storage instance" for each user instead of putting everything in a single shared one?
This shouldn't be hard to implement. However, do you see any particular use cases for this?
One thing that comes to mind is that the users will then be able to create/destroy stack depot instances when required. But I don't know if any of the users need this: so far they all seem to require stack depot throughout the whole lifetime of the system.
Quoted 1 line
In any case, evicting support is a good development, thanks!
Thank you!
Andrey Konovalov
reviewerRe: [PATCH 06/15] stackdepot: fix and clean-up atomic annotations
In reply to Marco ElverQuoted 17 lines · Marco Elver
lib/stackdepot.c static void depot_init_pool(void **prealloc) · line 230
Quoted 13 lines
lib/stackdepot.c +2
-2@@ -226,10 +226,10 @@ static void depot_init_pool(void **prealloc)/* * If the next pool is already initialized or the maximum number of * pools is reached, do not use the preallocated memory. -* smp_load_acquire() here pairs with smp_store_release() below and -* in depot_alloc_stack(). +* READ_ONCE is only used to mark the variable as atomic, +* there are no concurrent writes. This doesn't make sense. If there are no concurrent writes, we should drop the marking, so that if there are concurrent writes, tools like KCSAN can tell us about it if our assumption was wrong.
Makes sense, will do in v2.
Quoted 10 lines
lib/stackdepot.c depot_stack_handle_t __stack_depot_save(unsigned long *entries, · line 428
Quoted 8 lines
lib/stackdepot.c +2
-2@@ -425,8 +424,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries,* Check if another stack pool needs to be initialized. If so, allocate * the memory now - we won't be able to do that under the lock. * -* The smp_load_acquire() here pairs with smp_store_release() to -* |next_pool_inited| in depot_alloc_stack() and depot_init_pool(). +* smp_load_acquire pairs with smp_store_release +* in depot_alloc_stack and depot_init_pool. Reflow comment to match 80 cols used by comments elsewhere.
Will do in v2.
Thanks!
Andrey Konovalov
reviewerRe: [PATCH 11/15] stackdepot: use read/write lock
In reply to Marco ElverQuoted 9 lines · Marco Elver
lib/stackdepot.c static void *new_pool; · line 104
Quoted 5 lines
lib/stackdepot.c +3
-1-static int new_pool_required =1 ; +static bool new_pool_required = true; +/* Lock that protects the variables above. */ +static DEFINE_RWLOCK (pool_rwlock);Despite this being a rwlock, it'll introduce tons of (cache) contention for the common case (stack depot entry exists).
Quoted 3 lines
If creating new stack depot entries is only common during "warm-up" and then becomes exceedingly rare, I think a percpu-rwsem (read-lock is a CPU-local access, but write-locking is expensive) may be preferable.
Good suggestion. I propose that we keep the rwlock for now, and I'll check whether the performance is better with percpu-rwsem once I get to implementing and testing the performance changes. I'll also check whether percpu-rwsem makes sense for stack ring in tag-based KASAN modes.
Quoted 4 lines
Quoted 4 lines
lib/stackdepot.c +0
-0@@ -262,10 +258,8 @@ static void depot_keep_new_pool(void **prealloc)/* * If a new pool is already saved or the maximum number of * pools is reached, do not use the preallocated memory.
Quoted 8 lines
lib/stackdepot.c static void depot_keep_new_pool(void **prealloc) · line 262
Quoted 5 lines
lib/stackdepot.c +1
-3-* READ_ONCE is only used to mark the variable as atomic, -* there are no concurrent writes. */ -if (!READ_ONCE (new_pool_required)) +if (!new_pool_required)In my comment for the other patch I already suggested this change. Maybe move it there.
Will do in v2.
Quoted 33 lines
Quoted 33 lines
lib/stackdepot.c +2
-8return ;/* @@ -281,9 +275,8 @@ static void depot_keep_new_pool(void **prealloc)* At this point, either a new pool is kept or the maximum * number of pools is reached. In either case, take note that * keeping another pool is not required. -* smp_store_release pairs with smp_load_acquire in stack_depot_save. */ -smp_store_release (&new_pool_required,0 ); + new_pool_required = false; }/* Updates refences to the current and the next stack depot pools. */ @@ -300,7 +293,7 @@ static bool depot_update_pools(void **prealloc)/* Take note that we might need a new new_pool. */ if (pools_num <DEPOT_MAX_POOLS ) -smp_store_release (&new_pool_required,1 ); + new_pool_required = true;/* Try keeping the preallocated memory for new_pool. */ goto out_keep_prealloc;@@ -369,18 +362,13 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc)static struct stack_record *depot_fetch_stack (depot_stack_handle_t handle) {union handle_parts parts = { .handle = handle }; -/* -* READ_ONCE pairs with potential concurrent write in -* depot_init_pool. -*/ -int pools_num_cached =READ_ONCE (pools_num);
Quoted 8 lines
lib/stackdepot.c depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) · line 367
Quoted 3 lines
lib/stackdepot.c +0
-0void *pool;size_t offset = parts.offset <<DEPOT_STACK_ALIGN ;struct stack_record *stack;I'd add lockdep assertions to check that the lock is held appropriately when entering various helper functions that don't actually take the lock. Similarly for places that should not have the lock held you could assert the lock is not held.
Will do in v2.
Thanks!
Andrey Konovalov
reviewerRe: [PATCH 12/15] stackdepot: add refcount for records
In reply to Marco ElverQuoted 6 lines · Marco Elver
If someone doesn't use
stack_depot_evict(), and the refcount eventually overflows, it'll do a WARN (perrefcount_warn_saturate()).I think the interface needs to be different:
Quoted 8 lines
stack_depot_get(): increments refcount (could be inline if just wrapper aroundrefcount_inc())
stack_depot_put(): whatstack_depot_evict()currently doesThen it's clear that if someone uses either
stack_depot_get()or_put()that these need to be balanced. Not using either will result in the old behaviour of never evicting an entry.
So you mean the exported interface needs to be different? And the users will need to call both stack_depot_save+stack_depot_get for saving? Hm, this seems odd.
WDYT about adding a new flavor of stack_depot_save called stack_depot_save_get that would increment the refcount? And renaming stack_depot_evict to stack_depot_put.
I'm not sure though if the overflow is actually an issue. Hitting that would require calling stack_depot_save INT_MAX times.
Andrey Konovalov
reviewerRe: [PATCH 12/15] stackdepot: add refcount for records
In reply to Kuan-Ying Lee (李冠穎)Quoted 13 lines · Kuan-Ying Lee (李冠穎)' via kasan-dev
Quoted 10 lines
lib/stackdepot.c +1
-0@@ -452,6 +455,7 @@ depot_stack_handle_t __stack_depot_save(unsignedlong *entries,/* Fast path: look the stack trace up without full locking. */ found =find_stack (*bucket, entries, nr_entries, hash);if (found) { +refcount_inc (&found->count);read_unlock_irqrestore (&pool_rwlock, flags); goto exit;}Hi Andrey,
Quoted 3 lines
There are two
find_stack()function calls in__stack_depot_save().Maybe we need to add
refcount_inc()for both twofind_stack()?
Indeed, good catch! Will fix in v2.
Thanks!
Andrey Konovalov
reviewerRe: [PATCH 14/15] stackdepot: allow users to evict stack traces
In reply to Marco ElverQuoted 8 lines · Marco Elver
Quoted 7 lines
+/**
+ *stack_depot_evict- Drop a reference to a stack trace from stack depot
+ *
+ * @handle: Stack depot handle returned fromstack_depot_save()
+ *
+ * The stack trace gets fully removed from stack depot once all references
Quoted 5 lines
"gets fully removed" -> "is evicted" ?
Quoted 1 line
+ * to it has been dropped (once the number of
stack_depot_evictcalls matches"has been" -> "have been"
Will fix both in v2. Thanks!
Andrey Konovalov
reviewerRe: [PATCH 15/15] kasan: use stack_depot_evict for tag-based modes
In reply to Marco ElverQuoted 21 lines · Marco Elver
Quoted 13 lines
mm/kasan/tags.c +1
-1@@ -96,7 +96,7 @@ static void save_stack_info(struct kmem_cache *cache, void *object, gfp_t gfp_flags, bool is_free) {unsigned long flags; -depot_stack_handle_t stack; +depot_stack_handle_t stack, old_stack;u64 pos;struct kasan_stack_ring_entry *entry;void *old_ptr;mm/kasan/tags.c static void save_stack_info(struct kmem_cache *cache, void *object, · line 123
Quoted 4 lines
mm/kasan/tags.c +1
-0@@ -120,6 +120,8 @@ static void save_stack_info(struct kmem_cache *cache, void *object,if (!try_cmpxchg (&entry->ptr, &old_ptr,STACK_RING_BUSY_PTR )) goto next;/* Busy slot. */ + old_stack =READ_ONCE (entry->stack);Why
READ_ONCE? Is it possible that there is a concurrent writer once the slot has been "locked" withSTACK_RING_BUSY_PTR?
Quoted 4 lines
If there is no concurrency, it would be clearer to leave it unmarked and add a comment to that effect. (I also think a comment would be good to say what the
WRITE_ONCEbelow pair with, because at this point I've forgotten.)
Hm, I actually suspect we don't need these READ/WRITE_ONCE to entry fields at all. This seems to be a leftover from the initial series when I didn't yet have the rwlock. The rwlock prevents the entries from being read (in kasan_complete_mode_report_info) while being written and the try_cmpxchg prevents the same entry from being rewritten (in the unlikely case of wrapping during writing).
Marco, do you think we can drop these READ/WRITE_ONCE?
Thanks!
Re: [PATCH 12/15] stackdepot: add refcount for records
In reply to Andrey KonovalovQuoted 17 lines · Andrey Konovalov
Quoted 6 lines · Marco Elver
If someone doesn't use
stack_depot_evict(), and the refcount eventually overflows, it'll do a WARN (perrefcount_warn_saturate()).I think the interface needs to be different:
Quoted 8 lines
stack_depot_get(): increments refcount (could be inline if just wrapper aroundrefcount_inc())
stack_depot_put(): whatstack_depot_evict()currently doesThen it's clear that if someone uses either
stack_depot_get()or_put()that these need to be balanced. Not using either will result in the old behaviour of never evicting an entry.
Quoted 7 lines
So you mean the exported interface needs to be different? And the users will need to call both stack_depot_save+stack_depot_get for saving? Hm, this seems odd.
WDYT about adding a new flavor of
stack_depot_savecalledstack_depot_save_getthat would increment the refcount? And renamingstack_depot_evicttostack_depot_put.
If there are no other uses of stack_depot_get(), which seems likely, just stack_depot_save_get() seems ok.
Quoted 2 lines
I'm not sure though if the overflow is actually an issue. Hitting that would require calling
stack_depot_saveINT_MAXtimes.
With a long-running kernel it's possible.
Re: [PATCH 15/15] kasan: use stack_depot_evict for tag-based modes
In reply to Andrey KonovalovQuoted 28 lines · Andrey Konovalov
Quoted 21 lines · Marco Elver
Quoted 13 lines
mm/kasan/tags.c +1
-1@@ -96,7 +96,7 @@ static void save_stack_info(struct kmem_cache *cache, void *object, gfp_t gfp_flags, bool is_free) {unsigned long flags; -depot_stack_handle_t stack; +depot_stack_handle_t stack, old_stack;u64 pos;struct kasan_stack_ring_entry *entry;void *old_ptr;mm/kasan/tags.c static void save_stack_info(struct kmem_cache *cache, void *object, · line 123
Quoted 4 lines
mm/kasan/tags.c +1
-0@@ -120,6 +120,8 @@ static void save_stack_info(struct kmem_cache *cache, void *object,if (!try_cmpxchg (&entry->ptr, &old_ptr,STACK_RING_BUSY_PTR )) goto next;/* Busy slot. */ + old_stack =READ_ONCE (entry->stack);Why
READ_ONCE? Is it possible that there is a concurrent writer once the slot has been "locked" withSTACK_RING_BUSY_PTR?Quoted 4 lines
If there is no concurrency, it would be clearer to leave it unmarked and add a comment to that effect. (I also think a comment would be good to say what the
WRITE_ONCEbelow pair with, because at this point I've forgotten.)
Quoted 8 lines
Hm, I actually suspect we don't need these READ/WRITE_ONCE to entry fields at all. This seems to be a leftover from the initial series when I didn't yet have the rwlock. The rwlock prevents the entries from being read (in
kasan_complete_mode_report_info) while being written and thetry_cmpxchgprevents the same entry from being rewritten (in the unlikely case of wrapping during writing).Marco, do you think we can drop these READ/WRITE_ONCE?
Yes, I think they can be dropped.
Quoted 13 lines · Andrey Konovalov
Quoted 10 lines · Vlastimil Babka
I wonder if there's also another thing to consider for the future:
3. With the number of stackdepot users increasing, each having their
distinct set of stacks from others, would it make sense to create separate
"storage instance" for each user instead of putting everything in a single
shared one?
Quoted 8 lines
This shouldn't be hard to implement. However, do you see any particular use cases for this?
One thing that comes to mind is that the users will then be able to create/destroy stack depot instances when required. But I don't know if any of the users need this: so far they all seem to require stack depot throughout the whole lifetime of the system.
Maybe we can use evition in page_owner and slub_debug (SLAB_STORE_USER).
After we update page_owner->handle, we could evict the previous handle?
Quoted 4 lines
Quoted 1 line
In any case, evicting support is a good development, thanks!
Thank you!
Re: [PATCH 11/15] stackdepot: use read/write lock
In reply to Andrey KonovalovQuoted 15 lines · Andrey Konovalov
Quoted 9 lines · Marco Elver
lib/stackdepot.c static void *new_pool; · line 104
Quoted 5 lines
lib/stackdepot.c +3
-1-static int new_pool_required =1 ; +static bool new_pool_required = true; +/* Lock that protects the variables above. */ +static DEFINE_RWLOCK (pool_rwlock);Despite this being a rwlock, it'll introduce tons of (cache) contention for the common case (stack depot entry exists).
Quoted 3 lines
If creating new stack depot entries is only common during "warm-up" and then becomes exceedingly rare, I think a percpu-rwsem (read-lock is a CPU-local access, but write-locking is expensive) may be preferable.
Quoted 5 lines
Good suggestion. I propose that we keep the rwlock for now, and I'll check whether the performance is better with percpu-rwsem once I get to implementing and testing the performance changes. I'll also check whether percpu-rwsem makes sense for stack ring in tag-based KASAN modes.
I think it's quite obvious that the percpu-rwsem is better. A simple experiment is to measure the ratio of stackdepot hits vs misses. If the ratio is obviously skewed towards hits, then I'd just go with the percpu-rwsem.
The performance benefit may not be measurable if you use a small system.
Andrey Konovalov
reviewerRe: [PATCH 05/15] stackdepot: use fixed-sized slots for stack records
In reply to Alexander PotapenkoQuoted 10 lines · Alexander Potapenko
Quoted 5 lines · On Tue, Aug 29, 2023 at 7:11 PM <[email protected]> wrote:
From: Andrey Konovalov <[email protected]>
Instead of storing stack records in stack depot pools one right after another, use 32-frame-sized slots.
I am slightly concerned about the KMSAN use case here, which defines
KMSAN_STACK_DEPTHto 64.
Hm, indeed. KASAN also defines the depth to 64 actually.
I think it's reasonable to change the default value to 64 to cover all the existing users. And whoever wants to save up on memory can change the Kconfig parameter (I'll add one as you suggested).
Quoted 3 lines
I don't have a comprehensive stack depth breakdown, but a quick poking around syzkaller.appspot.com shows several cases where the stacks are actually longer than 32 frames.
Whichever value we choose, some of stack traces will not fit unfortunately. But yeah, 64 seems to be a more reasonable value.
Quoted 2 lines
Can you add a config parameter for the stack depth instead of mandating 32 frames everywhere?
Sure, will do in v2.
Quoted 6 lines
As a side note,
kmsan_internal_chain_origin()
(https://elixir.bootlin.com/linux/latest/source/mm/kmsan/core.c#L214)
creates small 3-frame records in the stack depot to link two stacks together, which will add unnecessary stackdepot pressure. But this can be fixed by storing both the new stack trace and the link to the old stack trace in the same record.
Do you mean this can be fixed in KMSAN? Or do you mean some kind of an extension to the stack depot interface?
Andrey Konovalov
reviewerRe: [PATCH 13/15] stackdepot: add backwards links to hash table buckets
In reply to Marco ElverQuoted 7 lines · Marco Elver
Quoted 7 lines
lib/stackdepot.c +0
-0@@ -58,6 +58,7 @@ union handle_parts {
Quoted 7 lines
lib/stackdepot.c union handle_parts { · line 61
Quoted 3 lines
lib/stackdepot.c +1
-0struct stack_record {struct stack_record *next;/* Link in hash table or freelist */ +struct stack_record *prev;/* Link in hash table */ At this point this could be a normal
list_head? Then you don't have to roll your own doubly-linked list manipulation (and benefit from things likeCONFIG_LIST_DEBUG).
Yeah, I think this makes sense. Will do in v2. Thanks!
Andrey Konovalov
reviewerRe: [PATCH 12/15] stackdepot: add refcount for records
In reply to Marco ElverQuoted 7 lines · Marco Elver
Quoted 4 lines
WDYT about adding a new flavor of
stack_depot_savecalledstack_depot_save_getthat would increment the refcount? And renamingstack_depot_evicttostack_depot_put.If there are no other uses of
stack_depot_get(), which seems likely, juststack_depot_save_get()seems ok.
Ok, I will implement a similar approach in v2: add another flag to __stack_depot_save to avoid multiplying API functions.
Thanks!
Andrey Konovalov
reviewerRe: [PATCH 15/15] kasan: use stack_depot_evict for tag-based modes
In reply to Marco ElverQuoted 9 lines · Marco Elver
Quoted 9 lines
Hm, I actually suspect we don't need these READ/WRITE_ONCE to entry fields at all. This seems to be a leftover from the initial series when I didn't yet have the rwlock. The rwlock prevents the entries from being read (in
kasan_complete_mode_report_info) while being written and thetry_cmpxchgprevents the same entry from being rewritten (in the unlikely case of wrapping during writing).
Quoted 3 lines
Quoted 1 line
Marco, do you think we can drop these READ/WRITE_ONCE?
Yes, I think they can be dropped.
Will drop in v2, thanks!
Andrey Konovalov
reviewerRe: [PATCH 11/15] stackdepot: use read/write lock
In reply to Marco ElverQuoted 7 lines · Marco Elver
Quoted 6 lines
Good suggestion. I propose that we keep the rwlock for now, and I'll check whether the performance is better with percpu-rwsem once I get to implementing and testing the performance changes. I'll also check whether percpu-rwsem makes sense for stack ring in tag-based KASAN modes.
Quoted 6 lines
I think it's quite obvious that the percpu-rwsem is better. A simple experiment is to measure the ratio of stackdepot hits vs misses. If the ratio is obviously skewed towards hits, then I'd just go with the percpu-rwsem.
The performance benefit may not be measurable if you use a small system.
I started looking into using percpu-rwsem, but it appears that it doesn't have the irqsave/irqrestore API flavor. I suspect that it shouldn't be hard to add it, but I'd rather not pursue this as a part of this series.
So I still propose to keep the rwlock for now, and switch to percpu-rwsem later together with the other perf changes.
Andrey Konovalov
reviewerQuoted 17 lines · Kuan-Ying Lee (李冠穎)' via kasan-dev
Quoted 9 lines
Quoted 8 lines
3. With the number of stackdepot users increasing, each having their
distinct set of stacks from others, would it make sense to create separate
"storage instance" for each user instead of putting everything in a single
shared one?Quoted 8 lines
This shouldn't be hard to implement. However, do you see any particular use cases for this?
One thing that comes to mind is that the users will then be able to create/destroy stack depot instances when required. But I don't know if any of the users need this: so far they all seem to require stack depot throughout the whole lifetime of the system.
Quoted 5 lines
Maybe we can use evition in
page_ownerandslub_debug(SLAB_STORE_USER).After we update
page_owner->handle, we could evict the previous handle?
We can definitely adapt more users to the new API. My comment was related to the suggestion of splitting stack depot storages for different users.
But actually I have a response to my question about the split: if each user has a separate stack depot storage instance, they can set the maximum stack trace size as they desire, and thus save up on memory.
Alexander Potapenko
reviewerRe: [PATCH 05/15] stackdepot: use fixed-sized slots for stack records
In reply to Andrey KonovalovQuoted 9 lines
Quoted 6 lines
As a side note,
kmsan_internal_chain_origin()
(https://elixir.bootlin.com/linux/latest/source/mm/kmsan/core.c#L214)
creates small 3-frame records in the stack depot to link two stacks together, which will add unnecessary stackdepot pressure. But this can be fixed by storing both the new stack trace and the link to the old stack trace in the same record.Do you mean this can be fixed in KMSAN? Or do you mean some kind of an extension to the stack depot interface?
Yes, I'll just fix this on the KMSAN side.
Re: [PATCH 11/15] stackdepot: use read/write lock
In reply to Andrey KonovalovQuoted 16 lines · Andrey Konovalov
Quoted 7 lines · Marco Elver
Quoted 6 lines
Good suggestion. I propose that we keep the rwlock for now, and I'll check whether the performance is better with percpu-rwsem once I get to implementing and testing the performance changes. I'll also check whether percpu-rwsem makes sense for stack ring in tag-based KASAN modes.
Quoted 6 lines
I think it's quite obvious that the percpu-rwsem is better. A simple experiment is to measure the ratio of stackdepot hits vs misses. If the ratio is obviously skewed towards hits, then I'd just go with the percpu-rwsem.
The performance benefit may not be measurable if you use a small system.
Quoted 7 lines
I started looking into using percpu-rwsem, but it appears that it doesn't have the irqsave/irqrestore API flavor. I suspect that it shouldn't be hard to add it, but I'd rather not pursue this as a part of this series.
So I still propose to keep the rwlock for now, and switch to percpu-rwsem later together with the other perf changes.
I may have gotten lost in the post-vacation email avalanche and missed
it: did you already send the percpu-rwsem optimization? I am a little worried about the contention the plain rwlock introduces on big machines.
Thanks,
-- Marco
Andrey Konovalov
reviewerRe: [PATCH 11/15] stackdepot: use read/write lock
Quoted 6 lines · Marco Elver
Quoted 6 lines
I started looking into using percpu-rwsem, but it appears that it doesn't have the irqsave/irqrestore API flavor. I suspect that it shouldn't be hard to add it, but I'd rather not pursue this as a part of this series.
Quoted 7 lines
Quoted 2 lines
So I still propose to keep the rwlock for now, and switch to percpu-rwsem later together with the other perf changes.
I may have gotten lost in the post-vacation email avalanche and missed
it: did you already send the percpu-rwsem optimization? I am a little worried about the contention the plain rwlock introduces on big machines.
I didn't get to working on that part unfortunately :(
I filed https://bugzilla.kernel.org/show_bug.cgi?id=218312 for this.