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