kernel/trace/pid_list.h

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 /* Do not include this file directly. */
   4
   5 #ifndef _TRACE_INTERNAL_PID_LIST_H
   6 #define _TRACE_INTERNAL_PID_LIST_H
   7
   8 /*
   9  * In order to keep track of what pids to trace, a tree is created much
  10  * like page tables are used. This creates a sparse bit map, where
  11  * the tree is filled in when needed. A PID is at most 30 bits (see
  12  * linux/thread.h), and is broken up into 3 sections based on the bit map
  13  * of the bits. The 8 MSB is the "upper1" section. The next 8 MSB is the
  14  * "upper2" section and the 14 LSB is the "lower" section.
  15  *
  16  * A trace_pid_list structure holds the "upper1" section, in an
  17  * array of 256 pointers (1 or 2K in size) to "upper_chunk" unions, where
  18  * each has an array of 256 pointers (1 or 2K in size) to the "lower_chunk"
  19  * structures, where each has an array of size 2K bytes representing a bitmask
  20  * of the 14 LSB of the PID (256 * 8 = 2048)
  21  *
  22  * When a trace_pid_list is allocated, it includes the 256 pointer array
  23  * of the upper1 unions. Then a "cache" of upper and lower is allocated
  24  * where these will be assigned as needed.
  25  *
  26  * When a bit is set in the pid_list bitmask, the pid to use has
  27  * the 8 MSB masked, and this is used to index the array in the
  28  * pid_list to find the next upper union. If the element is NULL,
  29  * then one is retrieved from the upper_list cache. If none is
  30  * available, then -ENOMEM is returned.
  31  *
  32  * The next 8 MSB is used to index into the "upper2" section. If this
  33  * element is NULL, then it is retrieved from the lower_list cache.
  34  * Again, if one is not available -ENOMEM is returned.
  35  *
  36  * Finally the 14 LSB of the PID is used to set the bit in the 16384
  37  * bitmask (made up of 2K bytes).
  38  *
  39  * When the second upper section or the lower section has their last
  40  * bit cleared, they are added back to the free list to be reused
  41  * when needed.
  42  */
  43
  44 #define UPPER_BITS      8
  45 #define UPPER_MAX       (1 << UPPER_BITS)
  46 #define UPPER1_SIZE     (1 << UPPER_BITS)
  47 #define UPPER2_SIZE     (1 << UPPER_BITS)
  48
  49 #define LOWER_BITS      14
  50 #define LOWER_MAX       (1 << LOWER_BITS)
  51 #define LOWER_SIZE      (LOWER_MAX / BITS_PER_LONG)
  52
  53 #define UPPER1_SHIFT    (LOWER_BITS + UPPER_BITS)
  54 #define UPPER2_SHIFT    LOWER_BITS
  55 #define LOWER_MASK      (LOWER_MAX - 1)
  56
  57 #define UPPER_MASK      (UPPER_MAX - 1)
  58
  59 /* According to linux/thread.h pids can not be bigger than or equal to 1 << 30 */
  60 #define MAX_PID         (1 << 30)
  61
  62 /* Just keep 6 chunks of both upper and lower in the cache on alloc */
  63 #define CHUNK_ALLOC 6
  64
  65 /* Have 2 chunks free, trigger a refill of the cache */
  66 #define CHUNK_REALLOC 2
  67
  68 union lower_chunk {
  69         union lower_chunk               *next;
  70         unsigned long                   data[LOWER_SIZE]; // 2K in size
  71 };
  72
  73 union upper_chunk {
  74         union upper_chunk               *next;
  75         union lower_chunk               *data[UPPER2_SIZE]; // 1 or 2K in size
  76 };
  77
  78 struct trace_pid_list {
  79         raw_spinlock_t                  lock;
  80         struct irq_work                 refill_irqwork;
  81         union upper_chunk               *upper[UPPER1_SIZE]; // 1 or 2K in size
  82         union upper_chunk               *upper_list;
  83         union lower_chunk               *lower_list;
  84         int                             free_upper_chunks;
  85         int                             free_lower_chunks;
  86 };
  87
  88 #endif /* _TRACE_INTERNAL_PID_LIST_H */