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