kernel/trace/pid_list.h

0001 // SPDX-License-Identifier: GPL-2.0
0002
0003 /* Do not include this file directly. */
0004
0005 #ifndef _TRACE_INTERNAL_PID_LIST_H
0006 #define _TRACE_INTERNAL_PID_LIST_H
0007
0008 /*
0009  * In order to keep track of what pids to trace, a tree is created much
0010  * like page tables are used. This creates a sparse bit map, where
0011  * the tree is filled in when needed. A PID is at most 30 bits (see
0012  * linux/thread.h), and is broken up into 3 sections based on the bit map
0013  * of the bits. The 8 MSB is the "upper1" section. The next 8 MSB is the
0014  * "upper2" section and the 14 LSB is the "lower" section.
0015  *
0016  * A trace_pid_list structure holds the "upper1" section, in an
0017  * array of 256 pointers (1 or 2K in size) to "upper_chunk" unions, where
0018  * each has an array of 256 pointers (1 or 2K in size) to the "lower_chunk"
0019  * structures, where each has an array of size 2K bytes representing a bitmask
0020  * of the 14 LSB of the PID (256 * 8 = 2048)
0021  *
0022  * When a trace_pid_list is allocated, it includes the 256 pointer array
0023  * of the upper1 unions. Then a "cache" of upper and lower is allocated
0024  * where these will be assigned as needed.
0025  *
0026  * When a bit is set in the pid_list bitmask, the pid to use has
0027  * the 8 MSB masked, and this is used to index the array in the
0028  * pid_list to find the next upper union. If the element is NULL,
0029  * then one is retrieved from the upper_list cache. If none is
0030  * available, then -ENOMEM is returned.
0031  *
0032  * The next 8 MSB is used to index into the "upper2" section. If this
0033  * element is NULL, then it is retrieved from the lower_list cache.
0034  * Again, if one is not available -ENOMEM is returned.
0035  *
0036  * Finally the 14 LSB of the PID is used to set the bit in the 16384
0037  * bitmask (made up of 2K bytes).
0038  *
0039  * When the second upper section or the lower section has their last
0040  * bit cleared, they are added back to the free list to be reused
0041  * when needed.
0042  */
0043
0044 #define UPPER_BITS  8
0045 #define UPPER_MAX   (1 << UPPER_BITS)
0046 #define UPPER1_SIZE (1 << UPPER_BITS)
0047 #define UPPER2_SIZE (1 << UPPER_BITS)
0048
0049 #define LOWER_BITS  14
0050 #define LOWER_MAX   (1 << LOWER_BITS)
0051 #define LOWER_SIZE  (LOWER_MAX / BITS_PER_LONG)
0052
0053 #define UPPER1_SHIFT    (LOWER_BITS + UPPER_BITS)
0054 #define UPPER2_SHIFT    LOWER_BITS
0055 #define LOWER_MASK  (LOWER_MAX - 1)
0056
0057 #define UPPER_MASK  (UPPER_MAX - 1)
0058
0059 /* According to linux/thread.h pids can not be bigger than or equal to 1 << 30 */
0060 #define MAX_PID     (1 << 30)
0061
0062 /* Just keep 6 chunks of both upper and lower in the cache on alloc */
0063 #define CHUNK_ALLOC 6
0064
0065 /* Have 2 chunks free, trigger a refill of the cache */
0066 #define CHUNK_REALLOC 2
0067
0068 union lower_chunk {
0069     union lower_chunk       *next;
0070     unsigned long           data[LOWER_SIZE]; // 2K in size
0071 };
0072
0073 union upper_chunk {
0074     union upper_chunk       *next;
0075     union lower_chunk       *data[UPPER2_SIZE]; // 1 or 2K in size
0076 };
0077
0078 struct trace_pid_list {
0079     raw_spinlock_t          lock;
0080     struct irq_work         refill_irqwork;
0081     union upper_chunk       *upper[UPPER1_SIZE]; // 1 or 2K in size
0082     union upper_chunk       *upper_list;
0083     union lower_chunk       *lower_list;
0084     int             free_upper_chunks;
0085     int             free_lower_chunks;
0086 };
0087
0088 #endif /* _TRACE_INTERNAL_PID_LIST_H */