Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 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 | |
Joonsoo Kim | 7c31190 | 2016-05-05 16:22:35 -0700 | [diff] [blame] | 45 | #define STACK_ALLOC_NULL_PROTECTION_BITS 1 |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 46 | #define STACK_ALLOC_ORDER 2 /* 'Slab' size order for stack depot, 4 pages */ |
| 47 | #define STACK_ALLOC_SIZE (1LL << (PAGE_SHIFT + STACK_ALLOC_ORDER)) |
| 48 | #define STACK_ALLOC_ALIGN 4 |
| 49 | #define STACK_ALLOC_OFFSET_BITS (STACK_ALLOC_ORDER + PAGE_SHIFT - \ |
| 50 | STACK_ALLOC_ALIGN) |
Joonsoo Kim | 7c31190 | 2016-05-05 16:22:35 -0700 | [diff] [blame] | 51 | #define STACK_ALLOC_INDEX_BITS (DEPOT_STACK_BITS - \ |
| 52 | STACK_ALLOC_NULL_PROTECTION_BITS - STACK_ALLOC_OFFSET_BITS) |
Dmitry Vyukov | 02754e0 | 2016-10-27 17:46:44 -0700 | [diff] [blame] | 53 | #define STACK_ALLOC_SLABS_CAP 8192 |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 54 | #define STACK_ALLOC_MAX_SLABS \ |
| 55 | (((1LL << (STACK_ALLOC_INDEX_BITS)) < STACK_ALLOC_SLABS_CAP) ? \ |
| 56 | (1LL << (STACK_ALLOC_INDEX_BITS)) : STACK_ALLOC_SLABS_CAP) |
| 57 | |
| 58 | /* The compact structure to store the reference to stacks. */ |
| 59 | union handle_parts { |
| 60 | depot_stack_handle_t handle; |
| 61 | struct { |
| 62 | u32 slabindex : STACK_ALLOC_INDEX_BITS; |
| 63 | u32 offset : STACK_ALLOC_OFFSET_BITS; |
Joonsoo Kim | 7c31190 | 2016-05-05 16:22:35 -0700 | [diff] [blame] | 64 | u32 valid : STACK_ALLOC_NULL_PROTECTION_BITS; |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 65 | }; |
| 66 | }; |
| 67 | |
| 68 | struct stack_record { |
| 69 | struct stack_record *next; /* Link in the hashtable */ |
| 70 | u32 hash; /* Hash in the hastable */ |
| 71 | u32 size; /* Number of frames in the stack */ |
| 72 | union handle_parts handle; |
| 73 | unsigned long entries[1]; /* Variable-sized array of entries. */ |
| 74 | }; |
| 75 | |
| 76 | static void *stack_slabs[STACK_ALLOC_MAX_SLABS]; |
| 77 | |
| 78 | static int depot_index; |
| 79 | static int next_slab_inited; |
| 80 | static size_t depot_offset; |
Zqiang | e7f7cf9 | 2021-05-06 18:03:40 -0700 | [diff] [blame] | 81 | static DEFINE_RAW_SPINLOCK(depot_lock); |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 82 | |
| 83 | static bool init_stack_slab(void **prealloc) |
| 84 | { |
| 85 | if (!*prealloc) |
| 86 | return false; |
| 87 | /* |
| 88 | * This smp_load_acquire() pairs with smp_store_release() to |
| 89 | * |next_slab_inited| below and in depot_alloc_stack(). |
| 90 | */ |
| 91 | if (smp_load_acquire(&next_slab_inited)) |
| 92 | return true; |
| 93 | if (stack_slabs[depot_index] == NULL) { |
| 94 | stack_slabs[depot_index] = *prealloc; |
Alexander Potapenko | 719742a | 2020-02-20 20:04:30 -0800 | [diff] [blame] | 95 | *prealloc = NULL; |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 96 | } else { |
Alexander Potapenko | 719742a | 2020-02-20 20:04:30 -0800 | [diff] [blame] | 97 | /* If this is the last depot slab, do not touch the next one. */ |
| 98 | if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) { |
| 99 | stack_slabs[depot_index + 1] = *prealloc; |
| 100 | *prealloc = NULL; |
| 101 | } |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 102 | /* |
| 103 | * This smp_store_release pairs with smp_load_acquire() from |
| 104 | * |next_slab_inited| above and in depot_save_stack(). |
| 105 | */ |
| 106 | smp_store_release(&next_slab_inited, 1); |
| 107 | } |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 108 | return true; |
| 109 | } |
| 110 | |
| 111 | /* Allocation of a new stack in raw storage */ |
| 112 | static struct stack_record *depot_alloc_stack(unsigned long *entries, int size, |
| 113 | u32 hash, void **prealloc, gfp_t alloc_flags) |
| 114 | { |
| 115 | int required_size = offsetof(struct stack_record, entries) + |
| 116 | sizeof(unsigned long) * size; |
| 117 | struct stack_record *stack; |
| 118 | |
| 119 | required_size = ALIGN(required_size, 1 << STACK_ALLOC_ALIGN); |
| 120 | |
| 121 | if (unlikely(depot_offset + required_size > STACK_ALLOC_SIZE)) { |
| 122 | if (unlikely(depot_index + 1 >= STACK_ALLOC_MAX_SLABS)) { |
| 123 | WARN_ONCE(1, "Stack depot reached limit capacity"); |
| 124 | return NULL; |
| 125 | } |
| 126 | depot_index++; |
| 127 | depot_offset = 0; |
| 128 | /* |
| 129 | * smp_store_release() here pairs with smp_load_acquire() from |
| 130 | * |next_slab_inited| in depot_save_stack() and |
| 131 | * init_stack_slab(). |
| 132 | */ |
| 133 | if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) |
| 134 | smp_store_release(&next_slab_inited, 0); |
| 135 | } |
| 136 | init_stack_slab(prealloc); |
| 137 | if (stack_slabs[depot_index] == NULL) |
| 138 | return NULL; |
| 139 | |
| 140 | stack = stack_slabs[depot_index] + depot_offset; |
| 141 | |
| 142 | stack->hash = hash; |
| 143 | stack->size = size; |
| 144 | stack->handle.slabindex = depot_index; |
| 145 | stack->handle.offset = depot_offset >> STACK_ALLOC_ALIGN; |
Joonsoo Kim | 7c31190 | 2016-05-05 16:22:35 -0700 | [diff] [blame] | 146 | stack->handle.valid = 1; |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 147 | memcpy(stack->entries, entries, size * sizeof(unsigned long)); |
| 148 | depot_offset += required_size; |
| 149 | |
| 150 | return stack; |
| 151 | } |
| 152 | |
| 153 | #define STACK_HASH_ORDER 20 |
| 154 | #define STACK_HASH_SIZE (1L << STACK_HASH_ORDER) |
| 155 | #define STACK_HASH_MASK (STACK_HASH_SIZE - 1) |
| 156 | #define STACK_HASH_SEED 0x9747b28c |
| 157 | |
| 158 | static struct stack_record *stack_table[STACK_HASH_SIZE] = { |
| 159 | [0 ... STACK_HASH_SIZE - 1] = NULL |
| 160 | }; |
| 161 | |
| 162 | /* Calculate hash for a stack */ |
| 163 | static inline u32 hash_stack(unsigned long *entries, unsigned int size) |
| 164 | { |
| 165 | return jhash2((u32 *)entries, |
| 166 | size * sizeof(unsigned long) / sizeof(u32), |
| 167 | STACK_HASH_SEED); |
| 168 | } |
| 169 | |
| 170 | /* Find a stack that is equal to the one stored in entries in the hash */ |
| 171 | static inline struct stack_record *find_stack(struct stack_record *bucket, |
| 172 | unsigned long *entries, int size, |
| 173 | u32 hash) |
| 174 | { |
| 175 | struct stack_record *found; |
| 176 | |
| 177 | for (found = bucket; found; found = found->next) { |
| 178 | if (found->hash == hash && |
| 179 | found->size == size && |
| 180 | !memcmp(entries, found->entries, |
| 181 | size * sizeof(unsigned long))) { |
| 182 | return found; |
| 183 | } |
| 184 | } |
| 185 | return NULL; |
| 186 | } |
| 187 | |
| 188 | void depot_fetch_stack(depot_stack_handle_t handle, struct stack_trace *trace) |
| 189 | { |
| 190 | union handle_parts parts = { .handle = handle }; |
| 191 | void *slab = stack_slabs[parts.slabindex]; |
| 192 | size_t offset = parts.offset << STACK_ALLOC_ALIGN; |
| 193 | struct stack_record *stack = slab + offset; |
| 194 | |
| 195 | trace->nr_entries = trace->max_entries = stack->size; |
| 196 | trace->entries = stack->entries; |
| 197 | trace->skip = 0; |
| 198 | } |
Chris Wilson | ae65a21 | 2016-11-10 10:46:47 -0800 | [diff] [blame] | 199 | EXPORT_SYMBOL_GPL(depot_fetch_stack); |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 200 | |
| 201 | /** |
| 202 | * depot_save_stack - save stack in a stack depot. |
| 203 | * @trace - the stacktrace to save. |
| 204 | * @alloc_flags - flags for allocating additional memory if required. |
| 205 | * |
| 206 | * Returns the handle of the stack struct stored in depot. |
| 207 | */ |
| 208 | depot_stack_handle_t depot_save_stack(struct stack_trace *trace, |
| 209 | gfp_t alloc_flags) |
| 210 | { |
| 211 | u32 hash; |
| 212 | depot_stack_handle_t retval = 0; |
| 213 | struct stack_record *found = NULL, **bucket; |
| 214 | unsigned long flags; |
| 215 | struct page *page = NULL; |
| 216 | void *prealloc = NULL; |
| 217 | |
| 218 | if (unlikely(trace->nr_entries == 0)) |
| 219 | goto fast_exit; |
| 220 | |
| 221 | hash = hash_stack(trace->entries, trace->nr_entries); |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 222 | bucket = &stack_table[hash & STACK_HASH_MASK]; |
| 223 | |
| 224 | /* |
| 225 | * Fast path: look the stack trace up without locking. |
| 226 | * The smp_load_acquire() here pairs with smp_store_release() to |
| 227 | * |bucket| below. |
| 228 | */ |
| 229 | found = find_stack(smp_load_acquire(bucket), trace->entries, |
| 230 | trace->nr_entries, hash); |
| 231 | if (found) |
| 232 | goto exit; |
| 233 | |
| 234 | /* |
| 235 | * Check if the current or the next stack slab need to be initialized. |
| 236 | * If so, allocate the memory - we won't be able to do that under the |
| 237 | * lock. |
| 238 | * |
| 239 | * The smp_load_acquire() here pairs with smp_store_release() to |
| 240 | * |next_slab_inited| in depot_alloc_stack() and init_stack_slab(). |
| 241 | */ |
| 242 | if (unlikely(!smp_load_acquire(&next_slab_inited))) { |
| 243 | /* |
| 244 | * Zero out zone modifiers, as we don't have specific zone |
| 245 | * requirements. Keep the flags related to allocation in atomic |
Andrey Ryabinin | 9485c0d | 2024-04-18 16:11:33 +0200 | [diff] [blame] | 246 | * contexts, I/O, nolockdep. |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 247 | */ |
| 248 | alloc_flags &= ~GFP_ZONEMASK; |
Andrey Ryabinin | 9485c0d | 2024-04-18 16:11:33 +0200 | [diff] [blame] | 249 | alloc_flags &= (GFP_ATOMIC | GFP_KERNEL | __GFP_NOLOCKDEP); |
Kirill A. Shutemov | 87cc271 | 2016-07-28 15:49:10 -0700 | [diff] [blame] | 250 | alloc_flags |= __GFP_NOWARN; |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 251 | page = alloc_pages(alloc_flags, STACK_ALLOC_ORDER); |
| 252 | if (page) |
| 253 | prealloc = page_address(page); |
| 254 | } |
| 255 | |
Zqiang | e7f7cf9 | 2021-05-06 18:03:40 -0700 | [diff] [blame] | 256 | raw_spin_lock_irqsave(&depot_lock, flags); |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 257 | |
| 258 | found = find_stack(*bucket, trace->entries, trace->nr_entries, hash); |
| 259 | if (!found) { |
| 260 | struct stack_record *new = |
| 261 | depot_alloc_stack(trace->entries, trace->nr_entries, |
| 262 | hash, &prealloc, alloc_flags); |
| 263 | if (new) { |
| 264 | new->next = *bucket; |
| 265 | /* |
| 266 | * This smp_store_release() pairs with |
| 267 | * smp_load_acquire() from |bucket| above. |
| 268 | */ |
| 269 | smp_store_release(bucket, new); |
| 270 | found = new; |
| 271 | } |
| 272 | } else if (prealloc) { |
| 273 | /* |
| 274 | * We didn't need to store this stack trace, but let's keep |
| 275 | * the preallocated memory for the future. |
| 276 | */ |
| 277 | WARN_ON(!init_stack_slab(&prealloc)); |
| 278 | } |
| 279 | |
Zqiang | e7f7cf9 | 2021-05-06 18:03:40 -0700 | [diff] [blame] | 280 | raw_spin_unlock_irqrestore(&depot_lock, flags); |
Alexander Potapenko | cd11016 | 2016-03-25 14:22:08 -0700 | [diff] [blame] | 281 | exit: |
| 282 | if (prealloc) { |
| 283 | /* Nobody used this memory, ok to free it. */ |
| 284 | free_pages((unsigned long)prealloc, STACK_ALLOC_ORDER); |
| 285 | } |
| 286 | if (found) |
| 287 | retval = found->handle.handle; |
| 288 | fast_exit: |
| 289 | return retval; |
| 290 | } |
Chris Wilson | ae65a21 | 2016-11-10 10:46:47 -0800 | [diff] [blame] | 291 | EXPORT_SYMBOL_GPL(depot_save_stack); |