Commit | Line | Data |
---|---|---|
c942fddf | 1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
cd11016e | 2 | /* |
b232b999 | 3 | * Stack depot - a stack trace storage that avoids duplication. |
cd11016e | 4 | * |
0621d160 AK |
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 | * | |
cd11016e AP |
14 | * Author: Alexander Potapenko <glider@google.com> |
15 | * Copyright (C) 2016 Google, Inc. | |
16 | * | |
b232b999 | 17 | * Based on the code by Dmitry Chernenkov. |
cd11016e AP |
18 | */ |
19 | ||
20 | #ifndef _LINUX_STACKDEPOT_H | |
21 | #define _LINUX_STACKDEPOT_H | |
22 | ||
7857ccdf ME |
23 | #include <linux/gfp.h> |
24 | ||
cd11016e | 25 | typedef u32 depot_stack_handle_t; |
15ef6a98 | 26 | |
83a4f1ef AP |
27 | /* |
28 | * Number of bits in the handle that stack depot doesn't use. Users may store | |
b232b999 | 29 | * information in them via stack_depot_set/get_extra_bits. |
83a4f1ef AP |
30 | */ |
31 | #define STACK_DEPOT_EXTRA_BITS 5 | |
cd11016e | 32 | |
8151c7a3 OS |
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 { | |
a6c1d9cb PC |
47 | u32 pool_index_plus_1 : DEPOT_POOL_INDEX_BITS; |
48 | u32 offset : DEPOT_OFFSET_BITS; | |
49 | u32 extra : STACK_DEPOT_EXTRA_BITS; | |
8151c7a3 OS |
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 | ||
022012dc AK |
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) | |
410b764f | 86 | #define STACK_DEPOT_FLAG_GET ((depot_flags_t)0x0002) |
022012dc | 87 | |
410b764f | 88 | #define STACK_DEPOT_FLAGS_NUM 2 |
022012dc AK |
89 | #define STACK_DEPOT_FLAGS_MASK ((depot_flags_t)((1 << STACK_DEPOT_FLAGS_NUM) - 1)) |
90 | ||
2dba5eb1 | 91 | /* |
b232b999 | 92 | * Using stack depot requires its initialization, which can be done in 3 ways: |
2dba5eb1 | 93 | * |
b232b999 AK |
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(). | |
a5f1783b | 97 | * |
b232b999 AK |
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. | |
a5f1783b | 105 | * |
1c0310ad | 106 | * stack_depot_init() and stack_depot_request_early_init() can be called |
b232b999 AK |
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. | |
2dba5eb1 | 111 | */ |
a5f1783b | 112 | #ifdef CONFIG_STACKDEPOT |
2dba5eb1 VB |
113 | int stack_depot_init(void); |
114 | ||
1c0310ad | 115 | void __init stack_depot_request_early_init(void); |
a5f1783b | 116 | |
b232b999 | 117 | /* Must be only called from mm_init(). */ |
a5f1783b | 118 | int __init stack_depot_early_init(void); |
2dba5eb1 | 119 | #else |
a5f1783b VB |
120 | static inline int stack_depot_init(void) { return 0; } |
121 | ||
1c0310ad | 122 | static inline void stack_depot_request_early_init(void) { } |
a5f1783b | 123 | |
2dba5eb1 VB |
124 | static inline int stack_depot_early_init(void) { return 0; } |
125 | #endif | |
126 | ||
0621d160 | 127 | /** |
022012dc | 128 | * stack_depot_save_flags - Save a stack trace to stack depot |
0621d160 AK |
129 | * |
130 | * @entries: Pointer to the stack trace | |
131 | * @nr_entries: Number of frames in the stack | |
132 | * @alloc_flags: Allocation GFP flags | |
022012dc AK |
133 | * @depot_flags: Stack depot flags |
134 | * | |
135 | * Saves a stack trace from @entries array of size @nr_entries. | |
0621d160 | 136 | * |
022012dc AK |
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. | |
0621d160 | 141 | * |
410b764f AK |
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. | |
108be8de AK |
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. | |
410b764f | 146 | * |
0621d160 AK |
147 | * If the provided stack trace comes from the interrupt context, only the part |
148 | * up to the interrupt entry is saved. | |
149 | * | |
022012dc | 150 | * Context: Any context, but setting STACK_DEPOT_FLAG_CAN_ALLOC is required if |
0621d160 AK |
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 | */ | |
022012dc AK |
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); | |
15ef6a98 | 161 | |
0621d160 AK |
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 | * | |
410b764f AK |
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. | |
0621d160 AK |
174 | * |
175 | * Return: Handle of the stack trace stored in depot, 0 on failure | |
176 | */ | |
c0cfc337 TG |
177 | depot_stack_handle_t stack_depot_save(unsigned long *entries, |
178 | unsigned int nr_entries, gfp_t gfp_flags); | |
cd11016e | 179 | |
4bedfb31 OS |
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 | ||
0621d160 AK |
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 | */ | |
c0cfc337 TG |
199 | unsigned int stack_depot_fetch(depot_stack_handle_t handle, |
200 | unsigned long **entries); | |
cd11016e | 201 | |
0621d160 AK |
202 | /** |
203 | * stack_depot_print - Print a stack trace from stack depot | |
204 | * | |
205 | * @stack: Stack depot handle returned from stack_depot_save() | |
206 | */ | |
15ef6a98 | 207 | void stack_depot_print(depot_stack_handle_t stack); |
83a4f1ef | 208 | |
0621d160 AK |
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 | */ | |
0f68d45e IK |
219 | int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size, |
220 | int spaces); | |
221 | ||
108be8de AK |
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 | ||
0621d160 AK |
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 | */ | |
36aa1e67 AK |
245 | depot_stack_handle_t __must_check stack_depot_set_extra_bits( |
246 | depot_stack_handle_t handle, unsigned int extra_bits); | |
247 | ||
0621d160 AK |
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 | */ | |
15ef6a98 | 255 | unsigned int stack_depot_get_extra_bits(depot_stack_handle_t handle); |
505be481 | 256 | |
cd11016e | 257 | #endif |