xref: /linux/include/linux/stackdepot.h (revision 9b61b2069681b60d0d0bedbd0fe3c70123dddb19)
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 /*
3  * Stack depot - a stack trace storage that avoids duplication.
4  *
5  * Stack depot is intended to be used by subsystems that need to store and
6  * later retrieve many potentially duplicated stack traces without wasting
7  * memory.
8  *
9  * For example, KASAN needs to save allocation and free stack traces for each
10  * object. Storing two stack traces per object requires a lot of memory (e.g.
11  * SLUB_DEBUG needs 256 bytes per object for that). Since allocation and free
12  * stack traces often repeat, using stack depot allows to save about 100x space.
13  *
14  * Author: Alexander Potapenko <glider@google.com>
15  * Copyright (C) 2016 Google, Inc.
16  *
17  * Based on the code by Dmitry Chernenkov.
18  */
19 
20 #ifndef _LINUX_STACKDEPOT_H
21 #define _LINUX_STACKDEPOT_H
22 
23 #include <linux/gfp.h>
24 
25 typedef u32 depot_stack_handle_t;
26 
27 /*
28  * Number of bits in the handle that stack depot doesn't use. Users may store
29  * information in them via stack_depot_set/get_extra_bits.
30  */
31 #define STACK_DEPOT_EXTRA_BITS 5
32 
33 #define DEPOT_HANDLE_BITS (sizeof(depot_stack_handle_t) * 8)
34 
35 #define DEPOT_POOL_ORDER 2 /* Pool size order, 4 pages */
36 #define DEPOT_POOL_SIZE (1LL << (PAGE_SHIFT + DEPOT_POOL_ORDER))
37 #define DEPOT_STACK_ALIGN 4
38 #define DEPOT_OFFSET_BITS (DEPOT_POOL_ORDER + PAGE_SHIFT - DEPOT_STACK_ALIGN)
39 #define DEPOT_POOL_INDEX_BITS (DEPOT_HANDLE_BITS - DEPOT_OFFSET_BITS - \
40 			       STACK_DEPOT_EXTRA_BITS)
41 
42 #ifdef CONFIG_STACKDEPOT
43 /* Compact structure that stores a reference to a stack. */
44 union handle_parts {
45 	depot_stack_handle_t handle;
46 	struct {
47 		u32 pool_index_plus_1	: DEPOT_POOL_INDEX_BITS;
48 		u32 offset		: DEPOT_OFFSET_BITS;
49 		u32 extra		: STACK_DEPOT_EXTRA_BITS;
50 	};
51 };
52 
53 struct stack_record {
54 	struct list_head hash_list;	/* Links in the hash table */
55 	u32 hash;			/* Hash in hash table */
56 	u32 size;			/* Number of stored frames */
57 	union handle_parts handle;	/* Constant after initialization */
58 	refcount_t count;
59 	union {
60 		unsigned long entries[CONFIG_STACKDEPOT_MAX_FRAMES];	/* Frames */
61 		struct {
62 			/*
63 			 * An important invariant of the implementation is to
64 			 * only place a stack record onto the freelist iff its
65 			 * refcount is zero. Because stack records with a zero
66 			 * refcount are never considered as valid, it is safe to
67 			 * union @entries and freelist management state below.
68 			 * Conversely, as soon as an entry is off the freelist
69 			 * and its refcount becomes non-zero, the below must not
70 			 * be accessed until being placed back on the freelist.
71 			 */
72 			struct list_head free_list;	/* Links in the freelist */
73 			unsigned long rcu_state;	/* RCU cookie */
74 		};
75 	};
76 };
77 #endif
78 
79 typedef u32 depot_flags_t;
80 
81 /*
82  * Flags that can be passed to stack_depot_save_flags(); see the comment next
83  * to its declaration for more details.
84  */
85 #define STACK_DEPOT_FLAG_CAN_ALLOC	((depot_flags_t)0x0001)
86 #define STACK_DEPOT_FLAG_GET		((depot_flags_t)0x0002)
87 
88 #define STACK_DEPOT_FLAGS_NUM	2
89 #define STACK_DEPOT_FLAGS_MASK	((depot_flags_t)((1 << STACK_DEPOT_FLAGS_NUM) - 1))
90 
91 /*
92  * Using stack depot requires its initialization, which can be done in 3 ways:
93  *
94  * 1. Selecting CONFIG_STACKDEPOT_ALWAYS_INIT. This option is suitable in
95  *    scenarios where it's known at compile time that stack depot will be used.
96  *    Enabling this config makes the kernel initialize stack depot in mm_init().
97  *
98  * 2. Calling stack_depot_request_early_init() during early boot, before
99  *    stack_depot_early_init() in mm_init() completes. For example, this can
100  *    be done when evaluating kernel boot parameters.
101  *
102  * 3. Calling stack_depot_init(). Possible after boot is complete. This option
103  *    is recommended for modules initialized later in the boot process, after
104  *    mm_init() completes.
105  *
106  * stack_depot_init() and stack_depot_request_early_init() can be called
107  * regardless of whether CONFIG_STACKDEPOT is enabled and are no-op when this
108  * config is disabled. The save/fetch/print stack depot functions can only be
109  * called from the code that makes sure CONFIG_STACKDEPOT is enabled _and_
110  * initializes stack depot via one of the ways listed above.
111  */
112 #ifdef CONFIG_STACKDEPOT
113 int stack_depot_init(void);
114 
115 void __init stack_depot_request_early_init(void);
116 
117 /* Must be only called from mm_init(). */
118 int __init stack_depot_early_init(void);
119 #else
stack_depot_init(void)120 static inline int stack_depot_init(void) { return 0; }
121 
stack_depot_request_early_init(void)122 static inline void stack_depot_request_early_init(void) { }
123 
stack_depot_early_init(void)124 static inline int stack_depot_early_init(void)	{ return 0; }
125 #endif
126 
127 /**
128  * stack_depot_save_flags - Save a stack trace to stack depot
129  *
130  * @entries:		Pointer to the stack trace
131  * @nr_entries:		Number of frames in the stack
132  * @alloc_flags:	Allocation GFP flags
133  * @depot_flags:	Stack depot flags
134  *
135  * Saves a stack trace from @entries array of size @nr_entries.
136  *
137  * If STACK_DEPOT_FLAG_CAN_ALLOC is set in @depot_flags, stack depot can
138  * replenish the stack pools in case no space is left (allocates using GFP
139  * flags of @alloc_flags). Otherwise, stack depot avoids any allocations and
140  * fails if no space is left to store the stack trace.
141  *
142  * If STACK_DEPOT_FLAG_GET is set in @depot_flags, stack depot will increment
143  * the refcount on the saved stack trace if it already exists in stack depot.
144  * Users of this flag must also call stack_depot_put() when keeping the stack
145  * trace is no longer required to avoid overflowing the refcount.
146  *
147  * If the provided stack trace comes from the interrupt context, only the part
148  * up to the interrupt entry is saved.
149  *
150  * Context: Any context, but setting STACK_DEPOT_FLAG_CAN_ALLOC is required if
151  *          alloc_pages() cannot be used from the current context. Currently
152  *          this is the case for contexts where neither %GFP_ATOMIC nor
153  *          %GFP_NOWAIT can be used (NMI, raw_spin_lock).
154  *
155  * Return: Handle of the stack struct stored in depot, 0 on failure
156  */
157 depot_stack_handle_t stack_depot_save_flags(unsigned long *entries,
158 					    unsigned int nr_entries,
159 					    gfp_t gfp_flags,
160 					    depot_flags_t depot_flags);
161 
162 /**
163  * stack_depot_save - Save a stack trace to stack depot
164  *
165  * @entries:		Pointer to the stack trace
166  * @nr_entries:		Number of frames in the stack
167  * @alloc_flags:	Allocation GFP flags
168  *
169  * Does not increment the refcount on the saved stack trace; see
170  * stack_depot_save_flags() for more details.
171  *
172  * Context: Contexts where allocations via alloc_pages() are allowed;
173  *          see stack_depot_save_flags() for more details.
174  *
175  * Return: Handle of the stack trace stored in depot, 0 on failure
176  */
177 depot_stack_handle_t stack_depot_save(unsigned long *entries,
178 				      unsigned int nr_entries, gfp_t gfp_flags);
179 
180 /**
181  * __stack_depot_get_stack_record - Get a pointer to a stack_record struct
182  *
183  * @handle: Stack depot handle
184  *
185  * This function is only for internal purposes.
186  *
187  * Return: Returns a pointer to a stack_record struct
188  */
189 struct stack_record *__stack_depot_get_stack_record(depot_stack_handle_t handle);
190 
191 /**
192  * stack_depot_fetch - Fetch a stack trace from stack depot
193  *
194  * @handle:	Stack depot handle returned from stack_depot_save()
195  * @entries:	Pointer to store the address of the stack trace
196  *
197  * Return: Number of frames for the fetched stack
198  */
199 unsigned int stack_depot_fetch(depot_stack_handle_t handle,
200 			       unsigned long **entries);
201 
202 /**
203  * stack_depot_print - Print a stack trace from stack depot
204  *
205  * @stack:	Stack depot handle returned from stack_depot_save()
206  */
207 void stack_depot_print(depot_stack_handle_t stack);
208 
209 /**
210  * stack_depot_snprint - Print a stack trace from stack depot into a buffer
211  *
212  * @handle:	Stack depot handle returned from stack_depot_save()
213  * @buf:	Pointer to the print buffer
214  * @size:	Size of the print buffer
215  * @spaces:	Number of leading spaces to print
216  *
217  * Return:	Number of bytes printed
218  */
219 int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size,
220 		       int spaces);
221 
222 /**
223  * stack_depot_put - Drop a reference to a stack trace from stack depot
224  *
225  * @handle:	Stack depot handle returned from stack_depot_save()
226  *
227  * The stack trace is evicted from stack depot once all references to it have
228  * been dropped (once the number of stack_depot_evict() calls matches the
229  * number of stack_depot_save_flags() calls with STACK_DEPOT_FLAG_GET set for
230  * this stack trace).
231  */
232 void stack_depot_put(depot_stack_handle_t handle);
233 
234 /**
235  * stack_depot_set_extra_bits - Set extra bits in a stack depot handle
236  *
237  * @handle:	Stack depot handle returned from stack_depot_save()
238  * @extra_bits:	Value to set the extra bits
239  *
240  * Return: Stack depot handle with extra bits set
241  *
242  * Stack depot handles have a few unused bits, which can be used for storing
243  * user-specific information. These bits are transparent to the stack depot.
244  */
245 depot_stack_handle_t __must_check stack_depot_set_extra_bits(
246 			depot_stack_handle_t handle, unsigned int extra_bits);
247 
248 /**
249  * stack_depot_get_extra_bits - Retrieve extra bits from a stack depot handle
250  *
251  * @handle:	Stack depot handle with extra bits saved
252  *
253  * Return: Extra bits retrieved from the stack depot handle
254  */
255 unsigned int stack_depot_get_extra_bits(depot_stack_handle_t handle);
256 
257 #endif
258