3  * Stack depot - a stack trace storage that avoids duplication.
5  * Internally, stack depot maintains a hash table of unique stacktraces. The
6  * stack traces themselves are stored contiguously one after another in a set
57 /* Hash table of stored stack records. */
66 /* Array of memory regions that store stack records. */
74 /* Freelist of stack records within stack_pools. */
171 	 * stack traces being stored in stack depot.  in stack_depot_early_init()
213 	pr_info("allocating space for %u stack pools via memblock\n",  in stack_depot_early_init()
218 		pr_err("stack pools allocation failed, disabling\n");  in stack_depot_early_init()
273 	pr_info("allocating space for %u stack pools via kvcalloc\n",  in stack_depot_init()
277 		pr_err("stack pools allocation failed, disabling\n");  in stack_depot_init()
291  * Initializes new stack pool, and updates the list of pools.
302 		WARN_ONCE(1, "Stack depot reached limit capacity");  in depot_init_pool()
319 	 * Stack depot tries to keep an extra pool allocated even before it runs  in depot_init_pool()
340 /* Keeps the preallocated memory to be used for a new stack depot pool. */
358  * Try to initialize a new stack record from the current pool, a cached pool, or
364 	struct stack_record *stack;  in depot_pop_free_pool()  local
382 	stack = current_pool + pool_offset;  in depot_pop_free_pool()
385 	stack->handle.pool_index_plus_1 = pool_index + 1;  in depot_pop_free_pool()
386 	stack->handle.offset = pool_offset >> DEPOT_STACK_ALIGN;  in depot_pop_free_pool()
387 	stack->handle.extra = 0;  in depot_pop_free_pool()
388 	INIT_LIST_HEAD(&stack->hash_list);  in depot_pop_free_pool()
392 	return stack;  in depot_pop_free_pool()
399 	struct stack_record *stack;  in depot_pop_free()  local
412 	stack = list_first_entry(&free_stacks, struct stack_record, free_list);  in depot_pop_free()
413 	if (!poll_state_synchronize_rcu(stack->rcu_state))  in depot_pop_free()
416 	list_del(&stack->free_list);  in depot_pop_free()
419 	return stack;  in depot_pop_free()
432 /* Allocates a new stack in a stack depot pool. */
437 	struct stack_record *stack = NULL;  in depot_alloc_stack()  local
455 		record_size = depot_stack_record_size(stack, CONFIG_STACKDEPOT_MAX_FRAMES);  in depot_alloc_stack()
456 		stack = depot_pop_free();  in depot_alloc_stack()
458 		record_size = depot_stack_record_size(stack, nr_entries);  in depot_alloc_stack()
461 	if (!stack) {  in depot_alloc_stack()
462 		stack = depot_pop_free_pool(prealloc, record_size);  in depot_alloc_stack()
463 		if (!stack)  in depot_alloc_stack()
467 	/* Save the stack trace. */  in depot_alloc_stack()
468 	stack->hash = hash;  in depot_alloc_stack()
469 	stack->size = nr_entries;  in depot_alloc_stack()
470 	/* stack->handle is already filled in by depot_pop_free_pool(). */  in depot_alloc_stack()
471 	memcpy(stack->entries, entries, flex_array_size(stack, entries, nr_entries));  in depot_alloc_stack()
474 		refcount_set(&stack->count, 1);  in depot_alloc_stack()
479 		refcount_set(&stack->count, REFCOUNT_SATURATED);  in depot_alloc_stack()
485 	 * Let KMSAN know the stored stack record is initialized. This shall  in depot_alloc_stack()
488 	kmsan_unpoison_memory(stack, record_size);  in depot_alloc_stack()
490 	return stack;  in depot_alloc_stack()
501 	struct stack_record *stack;  in depot_fetch_stack()  local
506 		WARN(1, "pool index %d out of bounds (%d) for stack id %08x\n",  in depot_fetch_stack()
516 	stack = pool + offset;  in depot_fetch_stack()
517 	if (WARN_ON(!refcount_read(&stack->count)))  in depot_fetch_stack()
520 	return stack;  in depot_fetch_stack()
523 /* Links stack into the freelist. */
524 static void depot_free_stack(struct stack_record *stack)  in depot_free_stack()  argument
539 	list_del_rcu(&stack->hash_list);  in depot_free_stack()
543 	 * NMI, or even RCU itself, stack depot cannot rely on primitives that  in depot_free_stack()
545 	 * stack depot again (such as call_rcu()).  in depot_free_stack()
551 	stack->rcu_state = get_state_synchronize_rcu();  in depot_free_stack()
558 	list_add_tail(&stack->free_list, &free_stacks);  in depot_free_stack()
568 /* Calculates the hash for a stack. */
591 /* Finds a stack in a bucket of the hash table. */
596 	struct stack_record *stack, *ret = NULL;  in find_stack()  local
599 	 * Stack depot may be used from instrumentation that instruments RCU or  in find_stack()
604 	 * unused entries, because the stack record free-then-reuse code paths  in find_stack()
609 	list_for_each_entry_rcu(stack, bucket, hash_list) {  in find_stack()
610 		if (stack->hash != hash || stack->size != size)  in find_stack()
618 		if (data_race(stackdepot_memcmp(entries, stack->entries, size)))  in find_stack()
622 		 * Try to increment refcount. If this succeeds, the stack record  in find_stack()
627 		 * a stack record is never placed back on the freelist.  in find_stack()
629 		if ((flags & STACK_DEPOT_FLAG_GET) && !refcount_inc_not_zero(&stack->count))  in find_stack()
632 		ret = stack;  in find_stack()
660 	 * If this stack trace is from an interrupt, including anything before  in stack_depot_save_flags()
661 	 * interrupt entry usually leads to unbounded stack depot growth.  in stack_depot_save_flags()
663 	 * Since use of filter_irq_stacks() is a requirement to ensure stack  in stack_depot_save_flags()
665 	 * filter_irq_stacks() to simplify all callers' use of stack depot.  in stack_depot_save_flags()
675 	/* Fast path: look the stack trace up without locking. */  in stack_depot_save_flags()
710 			 * This releases the stack record into the bucket and  in stack_depot_save_flags()
720 		 * Either stack depot already contains this stack trace, or  in stack_depot_save_flags()
731 		/* Stack depot didn't use this memory, free it. */  in stack_depot_save_flags()
763 	struct stack_record *stack;  in stack_depot_fetch()  local
775 	stack = depot_fetch_stack(handle);  in stack_depot_fetch()
780 	if (WARN(!stack, "corrupt handle or use after stack_depot_put()"))  in stack_depot_fetch()
783 	*entries = stack->entries;  in stack_depot_fetch()
784 	return stack->size;  in stack_depot_fetch()
790 	struct stack_record *stack;  in stack_depot_put()  local
795 	stack = depot_fetch_stack(handle);  in stack_depot_put()
797 	 * Should always be able to find the stack record, otherwise this is an  in stack_depot_put()
800 	if (WARN(!stack, "corrupt handle or unbalanced stack_depot_put()"))  in stack_depot_put()
803 	if (refcount_dec_and_test(&stack->count))  in stack_depot_put()
804 		depot_free_stack(stack);  in stack_depot_put()
808 void stack_depot_print(depot_stack_handle_t stack)  in stack_depot_print()  argument
813 	nr_entries = stack_depot_fetch(stack, &entries);  in stack_depot_print()