Commit | Line | Data |
---|---|---|
cd11016e AP |
1 | /* |
2 | * Generic stack depot for storing stack traces. | |
3 | * | |
4 | * Some debugging tools need to save stack traces of certain events which can | |
5 | * be later presented to the user. For example, KASAN needs to safe alloc and | |
6 | * free stacks for each object, but storing two stack traces per object | |
7 | * requires too much memory (e.g. SLUB_DEBUG needs 256 bytes per object for | |
8 | * that). | |
9 | * | |
10 | * Instead, stack depot maintains a hashtable of unique stacktraces. Since alloc | |
11 | * and free stacks repeat a lot, we save about 100x space. | |
12 | * Stacks are never removed from depot, so we store them contiguously one after | |
13 | * another in a contiguos memory allocation. | |
14 | * | |
15 | * Author: Alexander Potapenko <glider@google.com> | |
16 | * Copyright (C) 2016 Google, Inc. | |
17 | * | |
18 | * Based on code by Dmitry Chernenkov. | |
19 | * | |
20 | * This program is free software; you can redistribute it and/or | |
21 | * modify it under the terms of the GNU General Public License | |
22 | * version 2 as published by the Free Software Foundation. | |
23 | * | |
24 | * This program is distributed in the hope that it will be useful, but | |
25 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
26 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
27 | * General Public License for more details. | |
28 | * | |
29 | */ | |
30 | ||
31 | #include <linux/gfp.h> | |
32 | #include <linux/jhash.h> | |
33 | #include <linux/kernel.h> | |
34 | #include <linux/mm.h> | |
35 | #include <linux/percpu.h> | |
36 | #include <linux/printk.h> | |
37 | #include <linux/slab.h> | |
38 | #include <linux/stacktrace.h> | |
39 | #include <linux/stackdepot.h> | |
40 | #include <linux/string.h> | |
41 | #include <linux/types.h> | |
42 | ||
43 | #define DEPOT_STACK_BITS (sizeof(depot_stack_handle_t) * 8) | |
44 | ||
45 | #define STACK_ALLOC_ORDER 2 /* 'Slab' size order for stack depot, 4 pages */ | |
46 | #define STACK_ALLOC_SIZE (1LL << (PAGE_SHIFT + STACK_ALLOC_ORDER)) | |
47 | #define STACK_ALLOC_ALIGN 4 | |
48 | #define STACK_ALLOC_OFFSET_BITS (STACK_ALLOC_ORDER + PAGE_SHIFT - \ | |
49 | STACK_ALLOC_ALIGN) | |
50 | #define STACK_ALLOC_INDEX_BITS (DEPOT_STACK_BITS - STACK_ALLOC_OFFSET_BITS) | |
51 | #define STACK_ALLOC_SLABS_CAP 1024 | |
52 | #define STACK_ALLOC_MAX_SLABS \ | |
53 | (((1LL << (STACK_ALLOC_INDEX_BITS)) < STACK_ALLOC_SLABS_CAP) ? \ | |
54 | (1LL << (STACK_ALLOC_INDEX_BITS)) : STACK_ALLOC_SLABS_CAP) | |
55 | ||
56 | /* The compact structure to store the reference to stacks. */ | |
57 | union handle_parts { | |
58 | depot_stack_handle_t handle; | |
59 | struct { | |
60 | u32 slabindex : STACK_ALLOC_INDEX_BITS; | |
61 | u32 offset : STACK_ALLOC_OFFSET_BITS; | |
62 | }; | |
63 | }; | |
64 | ||
65 | struct stack_record { | |
66 | struct stack_record *next; /* Link in the hashtable */ | |
67 | u32 hash; /* Hash in the hastable */ | |
68 | u32 size; /* Number of frames in the stack */ | |
69 | union handle_parts handle; | |
70 | unsigned long entries[1]; /* Variable-sized array of entries. */ | |
71 | }; | |
72 | ||
73 | static void *stack_slabs[STACK_ALLOC_MAX_SLABS]; | |
74 | ||
75 | static int depot_index; | |
76 | static int next_slab_inited; | |
77 | static size_t depot_offset; | |
78 | static DEFINE_SPINLOCK(depot_lock); | |
79 | ||
80 | static bool init_stack_slab(void **prealloc) | |
81 | { | |
82 | if (!*prealloc) | |
83 | return false; | |
84 | /* | |
85 | * This smp_load_acquire() pairs with smp_store_release() to | |
86 | * |next_slab_inited| below and in depot_alloc_stack(). | |
87 | */ | |
88 | if (smp_load_acquire(&next_slab_inited)) | |
89 | return true; | |
90 | if (stack_slabs[depot_index] == NULL) { | |
91 | stack_slabs[depot_index] = *prealloc; | |
92 | } else { | |
93 | stack_slabs[depot_index + 1] = *prealloc; | |
94 | /* | |
95 | * This smp_store_release pairs with smp_load_acquire() from | |
96 | * |next_slab_inited| above and in depot_save_stack(). | |
97 | */ | |
98 | smp_store_release(&next_slab_inited, 1); | |
99 | } | |
100 | *prealloc = NULL; | |
101 | return true; | |
102 | } | |
103 | ||
104 | /* Allocation of a new stack in raw storage */ | |
105 | static struct stack_record *depot_alloc_stack(unsigned long *entries, int size, | |
106 | u32 hash, void **prealloc, gfp_t alloc_flags) | |
107 | { | |
108 | int required_size = offsetof(struct stack_record, entries) + | |
109 | sizeof(unsigned long) * size; | |
110 | struct stack_record *stack; | |
111 | ||
112 | required_size = ALIGN(required_size, 1 << STACK_ALLOC_ALIGN); | |
113 | ||
114 | if (unlikely(depot_offset + required_size > STACK_ALLOC_SIZE)) { | |
115 | if (unlikely(depot_index + 1 >= STACK_ALLOC_MAX_SLABS)) { | |
116 | WARN_ONCE(1, "Stack depot reached limit capacity"); | |
117 | return NULL; | |
118 | } | |
119 | depot_index++; | |
120 | depot_offset = 0; | |
121 | /* | |
122 | * smp_store_release() here pairs with smp_load_acquire() from | |
123 | * |next_slab_inited| in depot_save_stack() and | |
124 | * init_stack_slab(). | |
125 | */ | |
126 | if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) | |
127 | smp_store_release(&next_slab_inited, 0); | |
128 | } | |
129 | init_stack_slab(prealloc); | |
130 | if (stack_slabs[depot_index] == NULL) | |
131 | return NULL; | |
132 | ||
133 | stack = stack_slabs[depot_index] + depot_offset; | |
134 | ||
135 | stack->hash = hash; | |
136 | stack->size = size; | |
137 | stack->handle.slabindex = depot_index; | |
138 | stack->handle.offset = depot_offset >> STACK_ALLOC_ALIGN; | |
139 | memcpy(stack->entries, entries, size * sizeof(unsigned long)); | |
140 | depot_offset += required_size; | |
141 | ||
142 | return stack; | |
143 | } | |
144 | ||
145 | #define STACK_HASH_ORDER 20 | |
146 | #define STACK_HASH_SIZE (1L << STACK_HASH_ORDER) | |
147 | #define STACK_HASH_MASK (STACK_HASH_SIZE - 1) | |
148 | #define STACK_HASH_SEED 0x9747b28c | |
149 | ||
150 | static struct stack_record *stack_table[STACK_HASH_SIZE] = { | |
151 | [0 ... STACK_HASH_SIZE - 1] = NULL | |
152 | }; | |
153 | ||
154 | /* Calculate hash for a stack */ | |
155 | static inline u32 hash_stack(unsigned long *entries, unsigned int size) | |
156 | { | |
157 | return jhash2((u32 *)entries, | |
158 | size * sizeof(unsigned long) / sizeof(u32), | |
159 | STACK_HASH_SEED); | |
160 | } | |
161 | ||
162 | /* Find a stack that is equal to the one stored in entries in the hash */ | |
163 | static inline struct stack_record *find_stack(struct stack_record *bucket, | |
164 | unsigned long *entries, int size, | |
165 | u32 hash) | |
166 | { | |
167 | struct stack_record *found; | |
168 | ||
169 | for (found = bucket; found; found = found->next) { | |
170 | if (found->hash == hash && | |
171 | found->size == size && | |
172 | !memcmp(entries, found->entries, | |
173 | size * sizeof(unsigned long))) { | |
174 | return found; | |
175 | } | |
176 | } | |
177 | return NULL; | |
178 | } | |
179 | ||
180 | void depot_fetch_stack(depot_stack_handle_t handle, struct stack_trace *trace) | |
181 | { | |
182 | union handle_parts parts = { .handle = handle }; | |
183 | void *slab = stack_slabs[parts.slabindex]; | |
184 | size_t offset = parts.offset << STACK_ALLOC_ALIGN; | |
185 | struct stack_record *stack = slab + offset; | |
186 | ||
187 | trace->nr_entries = trace->max_entries = stack->size; | |
188 | trace->entries = stack->entries; | |
189 | trace->skip = 0; | |
190 | } | |
191 | ||
192 | /** | |
193 | * depot_save_stack - save stack in a stack depot. | |
194 | * @trace - the stacktrace to save. | |
195 | * @alloc_flags - flags for allocating additional memory if required. | |
196 | * | |
197 | * Returns the handle of the stack struct stored in depot. | |
198 | */ | |
199 | depot_stack_handle_t depot_save_stack(struct stack_trace *trace, | |
200 | gfp_t alloc_flags) | |
201 | { | |
202 | u32 hash; | |
203 | depot_stack_handle_t retval = 0; | |
204 | struct stack_record *found = NULL, **bucket; | |
205 | unsigned long flags; | |
206 | struct page *page = NULL; | |
207 | void *prealloc = NULL; | |
208 | ||
209 | if (unlikely(trace->nr_entries == 0)) | |
210 | goto fast_exit; | |
211 | ||
212 | hash = hash_stack(trace->entries, trace->nr_entries); | |
213 | /* Bad luck, we won't store this stack. */ | |
214 | if (hash == 0) | |
215 | goto exit; | |
216 | ||
217 | bucket = &stack_table[hash & STACK_HASH_MASK]; | |
218 | ||
219 | /* | |
220 | * Fast path: look the stack trace up without locking. | |
221 | * The smp_load_acquire() here pairs with smp_store_release() to | |
222 | * |bucket| below. | |
223 | */ | |
224 | found = find_stack(smp_load_acquire(bucket), trace->entries, | |
225 | trace->nr_entries, hash); | |
226 | if (found) | |
227 | goto exit; | |
228 | ||
229 | /* | |
230 | * Check if the current or the next stack slab need to be initialized. | |
231 | * If so, allocate the memory - we won't be able to do that under the | |
232 | * lock. | |
233 | * | |
234 | * The smp_load_acquire() here pairs with smp_store_release() to | |
235 | * |next_slab_inited| in depot_alloc_stack() and init_stack_slab(). | |
236 | */ | |
237 | if (unlikely(!smp_load_acquire(&next_slab_inited))) { | |
238 | /* | |
239 | * Zero out zone modifiers, as we don't have specific zone | |
240 | * requirements. Keep the flags related to allocation in atomic | |
241 | * contexts and I/O. | |
242 | */ | |
243 | alloc_flags &= ~GFP_ZONEMASK; | |
244 | alloc_flags &= (GFP_ATOMIC | GFP_KERNEL); | |
245 | page = alloc_pages(alloc_flags, STACK_ALLOC_ORDER); | |
246 | if (page) | |
247 | prealloc = page_address(page); | |
248 | } | |
249 | ||
250 | spin_lock_irqsave(&depot_lock, flags); | |
251 | ||
252 | found = find_stack(*bucket, trace->entries, trace->nr_entries, hash); | |
253 | if (!found) { | |
254 | struct stack_record *new = | |
255 | depot_alloc_stack(trace->entries, trace->nr_entries, | |
256 | hash, &prealloc, alloc_flags); | |
257 | if (new) { | |
258 | new->next = *bucket; | |
259 | /* | |
260 | * This smp_store_release() pairs with | |
261 | * smp_load_acquire() from |bucket| above. | |
262 | */ | |
263 | smp_store_release(bucket, new); | |
264 | found = new; | |
265 | } | |
266 | } else if (prealloc) { | |
267 | /* | |
268 | * We didn't need to store this stack trace, but let's keep | |
269 | * the preallocated memory for the future. | |
270 | */ | |
271 | WARN_ON(!init_stack_slab(&prealloc)); | |
272 | } | |
273 | ||
274 | spin_unlock_irqrestore(&depot_lock, flags); | |
275 | exit: | |
276 | if (prealloc) { | |
277 | /* Nobody used this memory, ok to free it. */ | |
278 | free_pages((unsigned long)prealloc, STACK_ALLOC_ORDER); | |
279 | } | |
280 | if (found) | |
281 | retval = found->handle.handle; | |
282 | fast_exit: | |
283 | return retval; | |
284 | } |