include/linux/stackdepot.h

   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
  25 typedef 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. */
  44 union 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
  54 struct 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
  80 typedef 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
 114 int stack_depot_init(void);
 115
 116 void __init stack_depot_request_early_init(void);
 117
 118 /* Must be only called from mm_init(). */
 119 int __init stack_depot_early_init(void);
 120 #else
 121 static inline int stack_depot_init(void) { return 0; }
 122
 123 static inline void stack_depot_request_early_init(void) { }
 124
 125 static 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  */
 158 depot_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  */
 178 depot_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  */
 190 struct 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  */
 200 unsigned 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  */
 208 void 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  */
 220 int 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  */
 233 void 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  */
 246 depot_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  */
 256 unsigned int stack_depot_get_extra_bits(depot_stack_handle_t handle);
 257
 258 #endif