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 */ |
89 | |