1 // SPDX-License-Identifier: GPL-2.0-only
3 * Generic stack depot for storing stack traces.
5 * Some debugging tools need to save stack traces of certain events which can
6 * be later presented to the user. For example, KASAN needs to safe alloc and
7 * free stacks for each object, but storing two stack traces per object
8 * requires too much memory (e.g. SLUB_DEBUG needs 256 bytes per object for
11 * Instead, stack depot maintains a hashtable of unique stacktraces. Since alloc
12 * and free stacks repeat a lot, we save about 100x space.
13 * Stacks are never removed from depot, so we store them contiguously one after
14 * another in a contiguous memory allocation.
16 * Author: Alexander Potapenko <glider@google.com>
17 * Copyright (C) 2016 Google, Inc.
19 * Based on code by Dmitry Chernenkov.
22 #include <linux/gfp.h>
23 #include <linux/jhash.h>
24 #include <linux/kernel.h>
26 #include <linux/percpu.h>
27 #include <linux/printk.h>
28 #include <linux/slab.h>
29 #include <linux/stacktrace.h>
30 #include <linux/stackdepot.h>
31 #include <linux/string.h>
32 #include <linux/types.h>
33 #include <linux/memblock.h>
35 #define DEPOT_STACK_BITS (sizeof(depot_stack_handle_t) * 8)
37 #define STACK_ALLOC_NULL_PROTECTION_BITS 1
38 #define STACK_ALLOC_ORDER 2 /* 'Slab' size order for stack depot, 4 pages */
39 #define STACK_ALLOC_SIZE (1LL << (PAGE_SHIFT + STACK_ALLOC_ORDER))
40 #define STACK_ALLOC_ALIGN 4
41 #define STACK_ALLOC_OFFSET_BITS (STACK_ALLOC_ORDER + PAGE_SHIFT - \
43 #define STACK_ALLOC_INDEX_BITS (DEPOT_STACK_BITS - \
44 STACK_ALLOC_NULL_PROTECTION_BITS - STACK_ALLOC_OFFSET_BITS)
45 #define STACK_ALLOC_SLABS_CAP 8192
46 #define STACK_ALLOC_MAX_SLABS \
47 (((1LL << (STACK_ALLOC_INDEX_BITS)) < STACK_ALLOC_SLABS_CAP) ? \
48 (1LL << (STACK_ALLOC_INDEX_BITS)) : STACK_ALLOC_SLABS_CAP)
50 /* The compact structure to store the reference to stacks. */
52 depot_stack_handle_t handle
;
54 u32 slabindex
: STACK_ALLOC_INDEX_BITS
;
55 u32 offset
: STACK_ALLOC_OFFSET_BITS
;
56 u32 valid
: STACK_ALLOC_NULL_PROTECTION_BITS
;
61 struct stack_record
*next
; /* Link in the hashtable */
62 u32 hash
; /* Hash in the hastable */
63 u32 size
; /* Number of frames in the stack */
64 union handle_parts handle
;
65 unsigned long entries
[]; /* Variable-sized array of entries. */
68 static void *stack_slabs
[STACK_ALLOC_MAX_SLABS
];
70 static int depot_index
;
71 static int next_slab_inited
;
72 static size_t depot_offset
;
73 static DEFINE_RAW_SPINLOCK(depot_lock
);
75 static bool init_stack_slab(void **prealloc
)
80 * This smp_load_acquire() pairs with smp_store_release() to
81 * |next_slab_inited| below and in depot_alloc_stack().
83 if (smp_load_acquire(&next_slab_inited
))
85 if (stack_slabs
[depot_index
] == NULL
) {
86 stack_slabs
[depot_index
] = *prealloc
;
89 /* If this is the last depot slab, do not touch the next one. */
90 if (depot_index
+ 1 < STACK_ALLOC_MAX_SLABS
) {
91 stack_slabs
[depot_index
+ 1] = *prealloc
;
95 * This smp_store_release pairs with smp_load_acquire() from
96 * |next_slab_inited| above and in stack_depot_save().
98 smp_store_release(&next_slab_inited
, 1);
103 /* Allocation of a new stack in raw storage */
104 static struct stack_record
*depot_alloc_stack(unsigned long *entries
, int size
,
105 u32 hash
, void **prealloc
, gfp_t alloc_flags
)
107 struct stack_record
*stack
;
108 size_t required_size
= struct_size(stack
, entries
, size
);
110 required_size
= ALIGN(required_size
, 1 << STACK_ALLOC_ALIGN
);
112 if (unlikely(depot_offset
+ required_size
> STACK_ALLOC_SIZE
)) {
113 if (unlikely(depot_index
+ 1 >= STACK_ALLOC_MAX_SLABS
)) {
114 WARN_ONCE(1, "Stack depot reached limit capacity");
120 * smp_store_release() here pairs with smp_load_acquire() from
121 * |next_slab_inited| in stack_depot_save() and
124 if (depot_index
+ 1 < STACK_ALLOC_MAX_SLABS
)
125 smp_store_release(&next_slab_inited
, 0);
127 init_stack_slab(prealloc
);
128 if (stack_slabs
[depot_index
] == NULL
)
131 stack
= stack_slabs
[depot_index
] + depot_offset
;
135 stack
->handle
.slabindex
= depot_index
;
136 stack
->handle
.offset
= depot_offset
>> STACK_ALLOC_ALIGN
;
137 stack
->handle
.valid
= 1;
138 memcpy(stack
->entries
, entries
, flex_array_size(stack
, entries
, size
));
139 depot_offset
+= required_size
;
144 #define STACK_HASH_SIZE (1L << CONFIG_STACK_HASH_ORDER)
145 #define STACK_HASH_MASK (STACK_HASH_SIZE - 1)
146 #define STACK_HASH_SEED 0x9747b28c
148 static bool stack_depot_disable
;
149 static struct stack_record
**stack_table
;
151 static int __init
is_stack_depot_disabled(char *str
)
155 ret
= kstrtobool(str
, &stack_depot_disable
);
156 if (!ret
&& stack_depot_disable
) {
157 pr_info("Stack Depot is disabled\n");
162 early_param("stack_depot_disable", is_stack_depot_disabled
);
164 int __init
stack_depot_init(void)
166 if (!stack_depot_disable
) {
167 size_t size
= (STACK_HASH_SIZE
* sizeof(struct stack_record
*));
170 stack_table
= memblock_alloc(size
, size
);
171 for (i
= 0; i
< STACK_HASH_SIZE
; i
++)
172 stack_table
[i
] = NULL
;
177 /* Calculate hash for a stack */
178 static inline u32
hash_stack(unsigned long *entries
, unsigned int size
)
180 return jhash2((u32
*)entries
,
181 array_size(size
, sizeof(*entries
)) / sizeof(u32
),
185 /* Use our own, non-instrumented version of memcmp().
187 * We actually don't care about the order, just the equality.
190 int stackdepot_memcmp(const unsigned long *u1
, const unsigned long *u2
,
193 for ( ; n
-- ; u1
++, u2
++) {
200 /* Find a stack that is equal to the one stored in entries in the hash */
201 static inline struct stack_record
*find_stack(struct stack_record
*bucket
,
202 unsigned long *entries
, int size
,
205 struct stack_record
*found
;
207 for (found
= bucket
; found
; found
= found
->next
) {
208 if (found
->hash
== hash
&&
209 found
->size
== size
&&
210 !stackdepot_memcmp(entries
, found
->entries
, size
))
217 * stack_depot_fetch - Fetch stack entries from a depot
219 * @handle: Stack depot handle which was returned from
220 * stack_depot_save().
221 * @entries: Pointer to store the entries address
223 * Return: The number of trace entries for this depot.
225 unsigned int stack_depot_fetch(depot_stack_handle_t handle
,
226 unsigned long **entries
)
228 union handle_parts parts
= { .handle
= handle
};
230 size_t offset
= parts
.offset
<< STACK_ALLOC_ALIGN
;
231 struct stack_record
*stack
;
234 if (parts
.slabindex
> depot_index
) {
235 WARN(1, "slab index %d out of bounds (%d) for stack id %08x\n",
236 parts
.slabindex
, depot_index
, handle
);
239 slab
= stack_slabs
[parts
.slabindex
];
242 stack
= slab
+ offset
;
244 *entries
= stack
->entries
;
247 EXPORT_SYMBOL_GPL(stack_depot_fetch
);
250 * stack_depot_save - Save a stack trace from an array
252 * @entries: Pointer to storage array
253 * @nr_entries: Size of the storage array
254 * @alloc_flags: Allocation gfp flags
256 * Return: The handle of the stack struct stored in depot
258 depot_stack_handle_t
stack_depot_save(unsigned long *entries
,
259 unsigned int nr_entries
,
262 struct stack_record
*found
= NULL
, **bucket
;
263 depot_stack_handle_t retval
= 0;
264 struct page
*page
= NULL
;
265 void *prealloc
= NULL
;
269 if (unlikely(nr_entries
== 0) || stack_depot_disable
)
272 hash
= hash_stack(entries
, nr_entries
);
273 bucket
= &stack_table
[hash
& STACK_HASH_MASK
];
276 * Fast path: look the stack trace up without locking.
277 * The smp_load_acquire() here pairs with smp_store_release() to
280 found
= find_stack(smp_load_acquire(bucket
), entries
,
286 * Check if the current or the next stack slab need to be initialized.
287 * If so, allocate the memory - we won't be able to do that under the
290 * The smp_load_acquire() here pairs with smp_store_release() to
291 * |next_slab_inited| in depot_alloc_stack() and init_stack_slab().
293 if (unlikely(!smp_load_acquire(&next_slab_inited
))) {
295 * Zero out zone modifiers, as we don't have specific zone
296 * requirements. Keep the flags related to allocation in atomic
299 alloc_flags
&= ~GFP_ZONEMASK
;
300 alloc_flags
&= (GFP_ATOMIC
| GFP_KERNEL
);
301 alloc_flags
|= __GFP_NOWARN
;
302 page
= alloc_pages(alloc_flags
, STACK_ALLOC_ORDER
);
304 prealloc
= page_address(page
);
307 raw_spin_lock_irqsave(&depot_lock
, flags
);
309 found
= find_stack(*bucket
, entries
, nr_entries
, hash
);
311 struct stack_record
*new =
312 depot_alloc_stack(entries
, nr_entries
,
313 hash
, &prealloc
, alloc_flags
);
317 * This smp_store_release() pairs with
318 * smp_load_acquire() from |bucket| above.
320 smp_store_release(bucket
, new);
323 } else if (prealloc
) {
325 * We didn't need to store this stack trace, but let's keep
326 * the preallocated memory for the future.
328 WARN_ON(!init_stack_slab(&prealloc
));
331 raw_spin_unlock_irqrestore(&depot_lock
, flags
);
334 /* Nobody used this memory, ok to free it. */
335 free_pages((unsigned long)prealloc
, STACK_ALLOC_ORDER
);
338 retval
= found
->handle
.handle
;
342 EXPORT_SYMBOL_GPL(stack_depot_save
);