1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Generic stack depot for storing stack traces. 4 * 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 9 * that). 10 * 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. 15 * 16 * Author: Alexander Potapenko <glider@google.com> 17 * Copyright (C) 2016 Google, Inc. 18 * 19 * Based on code by Dmitry Chernenkov. 20 */ 21 22 #include <linux/gfp.h> 23 #include <linux/jhash.h> 24 #include <linux/kernel.h> 25 #include <linux/mm.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> 34 35 #define DEPOT_STACK_BITS (sizeof(depot_stack_handle_t) * 8) 36 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 - \ 42 STACK_ALLOC_ALIGN) 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) 49 50 /* The compact structure to store the reference to stacks. */ 51 union handle_parts { 52 depot_stack_handle_t handle; 53 struct { 54 u32 slabindex : STACK_ALLOC_INDEX_BITS; 55 u32 offset : STACK_ALLOC_OFFSET_BITS; 56 u32 valid : STACK_ALLOC_NULL_PROTECTION_BITS; 57 }; 58 }; 59 60 struct stack_record { 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. */ 66 }; 67 68 static void *stack_slabs[STACK_ALLOC_MAX_SLABS]; 69 70 static int depot_index; 71 static int next_slab_inited; 72 static size_t depot_offset; 73 static DEFINE_RAW_SPINLOCK(depot_lock); 74 75 static bool init_stack_slab(void **prealloc) 76 { 77 if (!*prealloc) 78 return false; 79 /* 80 * This smp_load_acquire() pairs with smp_store_release() to 81 * |next_slab_inited| below and in depot_alloc_stack(). 82 */ 83 if (smp_load_acquire(&next_slab_inited)) 84 return true; 85 if (stack_slabs[depot_index] == NULL) { 86 stack_slabs[depot_index] = *prealloc; 87 *prealloc = NULL; 88 } else { 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; 92 *prealloc = NULL; 93 } 94 /* 95 * This smp_store_release pairs with smp_load_acquire() from 96 * |next_slab_inited| above and in stack_depot_save(). 97 */ 98 smp_store_release(&next_slab_inited, 1); 99 } 100 return true; 101 } 102 103 /* Allocation of a new stack in raw storage */ 104 static struct stack_record * 105 depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) 106 { 107 struct stack_record *stack; 108 size_t required_size = struct_size(stack, entries, size); 109 110 required_size = ALIGN(required_size, 1 << STACK_ALLOC_ALIGN); 111 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"); 115 return NULL; 116 } 117 depot_index++; 118 depot_offset = 0; 119 /* 120 * smp_store_release() here pairs with smp_load_acquire() from 121 * |next_slab_inited| in stack_depot_save() and 122 * init_stack_slab(). 123 */ 124 if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) 125 smp_store_release(&next_slab_inited, 0); 126 } 127 init_stack_slab(prealloc); 128 if (stack_slabs[depot_index] == NULL) 129 return NULL; 130 131 stack = stack_slabs[depot_index] + depot_offset; 132 133 stack->hash = hash; 134 stack->size = size; 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; 140 141 return stack; 142 } 143 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 147 148 static bool stack_depot_disable; 149 static struct stack_record **stack_table; 150 151 static int __init is_stack_depot_disabled(char *str) 152 { 153 int ret; 154 155 ret = kstrtobool(str, &stack_depot_disable); 156 if (!ret && stack_depot_disable) { 157 pr_info("Stack Depot is disabled\n"); 158 stack_table = NULL; 159 } 160 return 0; 161 } 162 early_param("stack_depot_disable", is_stack_depot_disabled); 163 164 int __init stack_depot_init(void) 165 { 166 if (!stack_depot_disable) { 167 size_t size = (STACK_HASH_SIZE * sizeof(struct stack_record *)); 168 int i; 169 170 stack_table = memblock_alloc(size, size); 171 for (i = 0; i < STACK_HASH_SIZE; i++) 172 stack_table[i] = NULL; 173 } 174 return 0; 175 } 176 177 /* Calculate hash for a stack */ 178 static inline u32 hash_stack(unsigned long *entries, unsigned int size) 179 { 180 return jhash2((u32 *)entries, 181 array_size(size, sizeof(*entries)) / sizeof(u32), 182 STACK_HASH_SEED); 183 } 184 185 /* Use our own, non-instrumented version of memcmp(). 186 * 187 * We actually don't care about the order, just the equality. 188 */ 189 static inline 190 int stackdepot_memcmp(const unsigned long *u1, const unsigned long *u2, 191 unsigned int n) 192 { 193 for ( ; n-- ; u1++, u2++) { 194 if (*u1 != *u2) 195 return 1; 196 } 197 return 0; 198 } 199 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, 203 u32 hash) 204 { 205 struct stack_record *found; 206 207 for (found = bucket; found; found = found->next) { 208 if (found->hash == hash && 209 found->size == size && 210 !stackdepot_memcmp(entries, found->entries, size)) 211 return found; 212 } 213 return NULL; 214 } 215 216 /** 217 * stack_depot_fetch - Fetch stack entries from a depot 218 * 219 * @handle: Stack depot handle which was returned from 220 * stack_depot_save(). 221 * @entries: Pointer to store the entries address 222 * 223 * Return: The number of trace entries for this depot. 224 */ 225 unsigned int stack_depot_fetch(depot_stack_handle_t handle, 226 unsigned long **entries) 227 { 228 union handle_parts parts = { .handle = handle }; 229 void *slab; 230 size_t offset = parts.offset << STACK_ALLOC_ALIGN; 231 struct stack_record *stack; 232 233 *entries = NULL; 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); 237 return 0; 238 } 239 slab = stack_slabs[parts.slabindex]; 240 if (!slab) 241 return 0; 242 stack = slab + offset; 243 244 *entries = stack->entries; 245 return stack->size; 246 } 247 EXPORT_SYMBOL_GPL(stack_depot_fetch); 248 249 /** 250 * __stack_depot_save - Save a stack trace from an array 251 * 252 * @entries: Pointer to storage array 253 * @nr_entries: Size of the storage array 254 * @alloc_flags: Allocation gfp flags 255 * @can_alloc: Allocate stack slabs (increased chance of failure if false) 256 * 257 * Saves a stack trace from @entries array of size @nr_entries. If @can_alloc is 258 * %true, is allowed to replenish the stack slab pool in case no space is left 259 * (allocates using GFP flags of @alloc_flags). If @can_alloc is %false, avoids 260 * any allocations and will fail if no space is left to store the stack trace. 261 * 262 * Context: Any context, but setting @can_alloc to %false is required if 263 * alloc_pages() cannot be used from the current context. Currently 264 * this is the case from contexts where neither %GFP_ATOMIC nor 265 * %GFP_NOWAIT can be used (NMI, raw_spin_lock). 266 * 267 * Return: The handle of the stack struct stored in depot, 0 on failure. 268 */ 269 depot_stack_handle_t __stack_depot_save(unsigned long *entries, 270 unsigned int nr_entries, 271 gfp_t alloc_flags, bool can_alloc) 272 { 273 struct stack_record *found = NULL, **bucket; 274 depot_stack_handle_t retval = 0; 275 struct page *page = NULL; 276 void *prealloc = NULL; 277 unsigned long flags; 278 u32 hash; 279 280 if (unlikely(nr_entries == 0) || stack_depot_disable) 281 goto fast_exit; 282 283 hash = hash_stack(entries, nr_entries); 284 bucket = &stack_table[hash & STACK_HASH_MASK]; 285 286 /* 287 * Fast path: look the stack trace up without locking. 288 * The smp_load_acquire() here pairs with smp_store_release() to 289 * |bucket| below. 290 */ 291 found = find_stack(smp_load_acquire(bucket), entries, 292 nr_entries, hash); 293 if (found) 294 goto exit; 295 296 /* 297 * Check if the current or the next stack slab need to be initialized. 298 * If so, allocate the memory - we won't be able to do that under the 299 * lock. 300 * 301 * The smp_load_acquire() here pairs with smp_store_release() to 302 * |next_slab_inited| in depot_alloc_stack() and init_stack_slab(). 303 */ 304 if (unlikely(can_alloc && !smp_load_acquire(&next_slab_inited))) { 305 /* 306 * Zero out zone modifiers, as we don't have specific zone 307 * requirements. Keep the flags related to allocation in atomic 308 * contexts and I/O. 309 */ 310 alloc_flags &= ~GFP_ZONEMASK; 311 alloc_flags &= (GFP_ATOMIC | GFP_KERNEL); 312 alloc_flags |= __GFP_NOWARN; 313 page = alloc_pages(alloc_flags, STACK_ALLOC_ORDER); 314 if (page) 315 prealloc = page_address(page); 316 } 317 318 raw_spin_lock_irqsave(&depot_lock, flags); 319 320 found = find_stack(*bucket, entries, nr_entries, hash); 321 if (!found) { 322 struct stack_record *new = depot_alloc_stack(entries, nr_entries, hash, &prealloc); 323 324 if (new) { 325 new->next = *bucket; 326 /* 327 * This smp_store_release() pairs with 328 * smp_load_acquire() from |bucket| above. 329 */ 330 smp_store_release(bucket, new); 331 found = new; 332 } 333 } else if (prealloc) { 334 /* 335 * We didn't need to store this stack trace, but let's keep 336 * the preallocated memory for the future. 337 */ 338 WARN_ON(!init_stack_slab(&prealloc)); 339 } 340 341 raw_spin_unlock_irqrestore(&depot_lock, flags); 342 exit: 343 if (prealloc) { 344 /* Nobody used this memory, ok to free it. */ 345 free_pages((unsigned long)prealloc, STACK_ALLOC_ORDER); 346 } 347 if (found) 348 retval = found->handle.handle; 349 fast_exit: 350 return retval; 351 } 352 EXPORT_SYMBOL_GPL(__stack_depot_save); 353 354 /** 355 * stack_depot_save - Save a stack trace from an array 356 * 357 * @entries: Pointer to storage array 358 * @nr_entries: Size of the storage array 359 * @alloc_flags: Allocation gfp flags 360 * 361 * Context: Contexts where allocations via alloc_pages() are allowed. 362 * See __stack_depot_save() for more details. 363 * 364 * Return: The handle of the stack struct stored in depot, 0 on failure. 365 */ 366 depot_stack_handle_t stack_depot_save(unsigned long *entries, 367 unsigned int nr_entries, 368 gfp_t alloc_flags) 369 { 370 return __stack_depot_save(entries, nr_entries, alloc_flags, true); 371 } 372 EXPORT_SYMBOL_GPL(stack_depot_save); 373