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. */
64 /* Array of memory regions that store stack records. */
72 /* Freelist of stack records within stack_pools. */
143 	 * stack traces being stored in stack depot.  in stack_depot_early_init()
242  * Initializes new stack pool, and updates the list of pools.
252 		WARN_ONCE(1, "Stack depot reached limit capacity");  in depot_init_pool()
269 	 * Stack depot tries to keep an extra pool allocated even before it runs  in depot_init_pool()
290 /* Keeps the preallocated memory to be used for a new stack depot pool. */
307  * Try to initialize a new stack record from the current pool, a cached pool, or
312 	struct stack_record *stack;  in depot_pop_free_pool()  local
330 	stack = current_pool + pool_offset;  in depot_pop_free_pool()
333 	stack->handle.pool_index_plus_1 = pool_index + 1;  in depot_pop_free_pool()
334 	stack->handle.offset = pool_offset >> DEPOT_STACK_ALIGN;  in depot_pop_free_pool()
335 	stack->handle.extra = 0;  in depot_pop_free_pool()
336 	INIT_LIST_HEAD(&stack->hash_list);  in depot_pop_free_pool()
340 	return stack;  in depot_pop_free_pool()
346 	struct stack_record *stack;  in depot_pop_free()  local
359 	stack = list_first_entry(&free_stacks, struct stack_record, free_list);  in depot_pop_free()
360 	if (!poll_state_synchronize_rcu(stack->rcu_state))  in depot_pop_free()
363 	list_del(&stack->free_list);  in depot_pop_free()
366 	return stack;  in depot_pop_free()
379 /* Allocates a new stack in a stack depot pool. */
383 	struct stack_record *stack = NULL;  in depot_alloc_stack()  local
401 		record_size = depot_stack_record_size(stack, CONFIG_STACKDEPOT_MAX_FRAMES);  in depot_alloc_stack()
402 		stack = depot_pop_free();  in depot_alloc_stack()
404 		record_size = depot_stack_record_size(stack, nr_entries);  in depot_alloc_stack()
407 	if (!stack) {  in depot_alloc_stack()
408 		stack = depot_pop_free_pool(prealloc, record_size);  in depot_alloc_stack()
409 		if (!stack)  in depot_alloc_stack()
413 	/* Save the stack trace. */  in depot_alloc_stack()
414 	stack->hash = hash;  in depot_alloc_stack()
415 	stack->size = nr_entries;  in depot_alloc_stack()
416 	/* stack->handle is already filled in by depot_pop_free_pool(). */  in depot_alloc_stack()
417 	memcpy(stack->entries, entries, flex_array_size(stack, entries, nr_entries));  in depot_alloc_stack()
420 		refcount_set(&stack->count, 1);  in depot_alloc_stack()
425 		refcount_set(&stack->count, REFCOUNT_SATURATED);  in depot_alloc_stack()
431 	 * Let KMSAN know the stored stack record is initialized. This shall  in depot_alloc_stack()
434 	kmsan_unpoison_memory(stack, record_size);  in depot_alloc_stack()
436 	return stack;  in depot_alloc_stack()
446 	struct stack_record *stack;  in depot_fetch_stack()  local
451 		WARN(1, "pool index %d out of bounds (%d) for stack id %08x\n",  in depot_fetch_stack()
460 	stack = pool + offset;  in depot_fetch_stack()
461 	if (WARN_ON(!refcount_read(&stack->count)))  in depot_fetch_stack()
464 	return stack;  in depot_fetch_stack()
467 /* Links stack into the freelist. */
468 static void depot_free_stack(struct stack_record *stack)  in depot_free_stack()  argument
482 	list_del_rcu(&stack->hash_list);  in depot_free_stack()
486 	 * NMI, or even RCU itself, stack depot cannot rely on primitives that  in depot_free_stack()
488 	 * stack depot again (such as call_rcu()).  in depot_free_stack()
494 	stack->rcu_state = get_state_synchronize_rcu();  in depot_free_stack()
501 	list_add_tail(&stack->free_list, &free_stacks);  in depot_free_stack()
511 /* Calculates the hash for a stack. */
534 /* Finds a stack in a bucket of the hash table. */
539 	struct stack_record *stack, *ret = NULL;  in find_stack()  local
542 	 * Stack depot may be used from instrumentation that instruments RCU or  in find_stack()
547 	 * unused entries, because the stack record free-then-reuse code paths  in find_stack()
552 	list_for_each_entry_rcu(stack, bucket, hash_list) {  in find_stack()
553 		if (stack->hash != hash || stack->size != size)  in find_stack()
561 		if (data_race(stackdepot_memcmp(entries, stack->entries, size)))  in find_stack()
565 		 * Try to increment refcount. If this succeeds, the stack record  in find_stack()
570 		 * a stack record is never placed back on the freelist.  in find_stack()
572 		if ((flags & STACK_DEPOT_FLAG_GET) && !refcount_inc_not_zero(&stack->count))  in find_stack()
575 		ret = stack;  in find_stack()
602 	 * If this stack trace is from an interrupt, including anything before  in stack_depot_save_flags()
603 	 * interrupt entry usually leads to unbounded stack depot growth.  in stack_depot_save_flags()
605 	 * Since use of filter_irq_stacks() is a requirement to ensure stack  in stack_depot_save_flags()
607 	 * filter_irq_stacks() to simplify all callers' use of stack depot.  in stack_depot_save_flags()
617 	/* Fast path: look the stack trace up without locking. */  in stack_depot_save_flags()
644 			 * This releases the stack record into the bucket and  in stack_depot_save_flags()
654 		 * Either stack depot already contains this stack trace, or  in stack_depot_save_flags()
665 		/* Stack depot didn't use this memory, free it. */  in stack_depot_save_flags()
694 	struct stack_record *stack;  in stack_depot_fetch()  local
706 	stack = depot_fetch_stack(handle);  in stack_depot_fetch()
711 	if (WARN(!stack, "corrupt handle or use after stack_depot_put()"))  in stack_depot_fetch()
714 	*entries = stack->entries;  in stack_depot_fetch()
715 	return stack->size;  in stack_depot_fetch()
721 	struct stack_record *stack;  in stack_depot_put()  local
726 	stack = depot_fetch_stack(handle);  in stack_depot_put()
728 	 * Should always be able to find the stack record, otherwise this is an  in stack_depot_put()
731 	if (WARN(!stack, "corrupt handle or unbalanced stack_depot_put()"))  in stack_depot_put()
734 	if (refcount_dec_and_test(&stack->count))  in stack_depot_put()
735 		depot_free_stack(stack);  in stack_depot_put()
739 void stack_depot_print(depot_stack_handle_t stack)  in stack_depot_print()  argument
744 	nr_entries = stack_depot_fetch(stack, &entries);  in stack_depot_print()