1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #ifndef __TRACING_MAP_H |
3 | #define __TRACING_MAP_H |
4 | |
5 | #define TRACING_MAP_BITS_DEFAULT 11 |
6 | #define TRACING_MAP_BITS_MAX 17 |
7 | #define TRACING_MAP_BITS_MIN 7 |
8 | |
9 | #define TRACING_MAP_KEYS_MAX 3 |
10 | #define TRACING_MAP_VALS_MAX 3 |
11 | #define TRACING_MAP_FIELDS_MAX (TRACING_MAP_KEYS_MAX + \ |
12 | TRACING_MAP_VALS_MAX) |
13 | #define TRACING_MAP_VARS_MAX 16 |
14 | #define TRACING_MAP_SORT_KEYS_MAX 2 |
15 | |
16 | typedef int (*tracing_map_cmp_fn_t) (void *val_a, void *val_b); |
17 | |
18 | /* |
19 | * This is an overview of the tracing_map data structures and how they |
20 | * relate to the tracing_map API. The details of the algorithms |
21 | * aren't discussed here - this is just a general overview of the data |
22 | * structures and how they interact with the API. |
23 | * |
24 | * The central data structure of the tracing_map is an initially |
25 | * zeroed array of struct tracing_map_entry (stored in the map field |
26 | * of struct tracing_map). tracing_map_entry is a very simple data |
27 | * structure containing only two fields: a 32-bit unsigned 'key' |
28 | * variable and a pointer named 'val'. This array of struct |
29 | * tracing_map_entry is essentially a hash table which will be |
30 | * modified by a single function, tracing_map_insert(), but which can |
31 | * be traversed and read by a user at any time (though the user does |
32 | * this indirectly via an array of tracing_map_sort_entry - see the |
33 | * explanation of that data structure in the discussion of the |
34 | * sorting-related data structures below). |
35 | * |
36 | * The central function of the tracing_map API is |
37 | * tracing_map_insert(). tracing_map_insert() hashes the |
38 | * arbitrarily-sized key passed into it into a 32-bit unsigned key. |
39 | * It then uses this key, truncated to the array size, as an index |
40 | * into the array of tracing_map_entries. If the value of the 'key' |
41 | * field of the tracing_map_entry found at that location is 0, then |
42 | * that entry is considered to be free and can be claimed, by |
43 | * replacing the 0 in the 'key' field of the tracing_map_entry with |
44 | * the new 32-bit hashed key. Once claimed, that tracing_map_entry's |
45 | * 'val' field is then used to store a unique element which will be |
46 | * forever associated with that 32-bit hashed key in the |
47 | * tracing_map_entry. |
48 | * |
49 | * That unique element now in the tracing_map_entry's 'val' field is |
50 | * an instance of tracing_map_elt, where 'elt' in the latter part of |
51 | * that variable name is short for 'element'. The purpose of a |
52 | * tracing_map_elt is to hold values specific to the particular |
53 | * 32-bit hashed key it's associated with. Things such as the unique |
54 | * set of aggregated sums associated with the 32-bit hashed key, along |
55 | * with a copy of the full key associated with the entry, and which |
56 | * was used to produce the 32-bit hashed key. |
57 | * |
58 | * When tracing_map_create() is called to create the tracing map, the |
59 | * user specifies (indirectly via the map_bits param, the details are |
60 | * unimportant for this discussion) the maximum number of elements |
61 | * that the map can hold (stored in the max_elts field of struct |
62 | * tracing_map). This is the maximum possible number of |
63 | * tracing_map_entries in the tracing_map_entry array which can be |
64 | * 'claimed' as described in the above discussion, and therefore is |
65 | * also the maximum number of tracing_map_elts that can be associated |
66 | * with the tracing_map_entry array in the tracing_map. Because of |
67 | * the way the insertion algorithm works, the size of the allocated |
68 | * tracing_map_entry array is always twice the maximum number of |
69 | * elements (2 * max_elts). This value is stored in the map_size |
70 | * field of struct tracing_map. |
71 | * |
72 | * Because tracing_map_insert() needs to work from any context, |
73 | * including from within the memory allocation functions themselves, |
74 | * both the tracing_map_entry array and a pool of max_elts |
75 | * tracing_map_elts are pre-allocated before any call is made to |
76 | * tracing_map_insert(). |
77 | * |
78 | * The tracing_map_entry array is allocated as a single block by |
79 | * tracing_map_create(). |
80 | * |
81 | * Because the tracing_map_elts are much larger objects and can't |
82 | * generally be allocated together as a single large array without |
83 | * failure, they're allocated individually, by tracing_map_init(). |
84 | * |
85 | * The pool of tracing_map_elts are allocated by tracing_map_init() |
86 | * rather than by tracing_map_create() because at the time |
87 | * tracing_map_create() is called, there isn't enough information to |
88 | * create the tracing_map_elts. Specifically,the user first needs to |
89 | * tell the tracing_map implementation how many fields the |
90 | * tracing_map_elts contain, and which types of fields they are (key |
91 | * or sum). The user does this via the tracing_map_add_sum_field() |
92 | * and tracing_map_add_key_field() functions, following which the user |
93 | * calls tracing_map_init() to finish up the tracing map setup. The |
94 | * array holding the pointers which make up the pre-allocated pool of |
95 | * tracing_map_elts is allocated as a single block and is stored in |
96 | * the elts field of struct tracing_map. |
97 | * |
98 | * There is also a set of structures used for sorting that might |
99 | * benefit from some minimal explanation. |
100 | * |
101 | * struct tracing_map_sort_key is used to drive the sort at any given |
102 | * time. By 'any given time' we mean that a different |
103 | * tracing_map_sort_key will be used at different times depending on |
104 | * whether the sort currently being performed is a primary or a |
105 | * secondary sort. |
106 | * |
107 | * The sort key is very simple, consisting of the field index of the |
108 | * tracing_map_elt field to sort on (which the user saved when adding |
109 | * the field), and whether the sort should be done in an ascending or |
110 | * descending order. |
111 | * |
112 | * For the convenience of the sorting code, a tracing_map_sort_entry |
113 | * is created for each tracing_map_elt, again individually allocated |
114 | * to avoid failures that might be expected if allocated as a single |
115 | * large array of struct tracing_map_sort_entry. |
116 | * tracing_map_sort_entry instances are the objects expected by the |
117 | * various internal sorting functions, and are also what the user |
118 | * ultimately receives after calling tracing_map_sort_entries(). |
119 | * Because it doesn't make sense for users to access an unordered and |
120 | * sparsely populated tracing_map directly, the |
121 | * tracing_map_sort_entries() function is provided so that users can |
122 | * retrieve a sorted list of all existing elements. In addition to |
123 | * the associated tracing_map_elt 'elt' field contained within the |
124 | * tracing_map_sort_entry, which is the object of interest to the |
125 | * user, tracing_map_sort_entry objects contain a number of additional |
126 | * fields which are used for caching and internal purposes and can |
127 | * safely be ignored. |
128 | */ |
129 | |
130 | struct tracing_map_field { |
131 | tracing_map_cmp_fn_t cmp_fn; |
132 | union { |
133 | atomic64_t sum; |
134 | unsigned int offset; |
135 | }; |
136 | }; |
137 | |
138 | struct tracing_map_elt { |
139 | struct tracing_map *map; |
140 | struct tracing_map_field *fields; |
141 | atomic64_t *vars; |
142 | bool *var_set; |
143 | void *key; |
144 | void *private_data; |
145 | }; |
146 | |
147 | struct tracing_map_entry { |
148 | u32 key; |
149 | struct tracing_map_elt *val; |
150 | }; |
151 | |
152 | struct tracing_map_sort_key { |
153 | unsigned int field_idx; |
154 | bool descending; |
155 | }; |
156 | |
157 | struct tracing_map_sort_entry { |
158 | void *key; |
159 | struct tracing_map_elt *elt; |
160 | bool elt_copied; |
161 | bool dup; |
162 | }; |
163 | |
164 | struct tracing_map_array { |
165 | unsigned int entries_per_page; |
166 | unsigned int entry_size_shift; |
167 | unsigned int entry_shift; |
168 | unsigned int entry_mask; |
169 | unsigned int n_pages; |
170 | void **pages; |
171 | }; |
172 | |
173 | #define TRACING_MAP_ARRAY_ELT(array, idx) \ |
174 | (array->pages[idx >> array->entry_shift] + \ |
175 | ((idx & array->entry_mask) << array->entry_size_shift)) |
176 | |
177 | #define TRACING_MAP_ENTRY(array, idx) \ |
178 | ((struct tracing_map_entry *)TRACING_MAP_ARRAY_ELT(array, idx)) |
179 | |
180 | #define TRACING_MAP_ELT(array, idx) \ |
181 | ((struct tracing_map_elt **)TRACING_MAP_ARRAY_ELT(array, idx)) |
182 | |
183 | struct tracing_map { |
184 | unsigned int key_size; |
185 | unsigned int map_bits; |
186 | unsigned int map_size; |
187 | unsigned int max_elts; |
188 | atomic_t next_elt; |
189 | struct tracing_map_array *elts; |
190 | struct tracing_map_array *map; |
191 | const struct tracing_map_ops *ops; |
192 | void *private_data; |
193 | struct tracing_map_field fields[TRACING_MAP_FIELDS_MAX]; |
194 | unsigned int n_fields; |
195 | int key_idx[TRACING_MAP_KEYS_MAX]; |
196 | unsigned int n_keys; |
197 | struct tracing_map_sort_key sort_key; |
198 | unsigned int n_vars; |
199 | atomic64_t hits; |
200 | atomic64_t drops; |
201 | }; |
202 | |
203 | /** |
204 | * struct tracing_map_ops - callbacks for tracing_map |
205 | * |
206 | * The methods in this structure define callback functions for various |
207 | * operations on a tracing_map or objects related to a tracing_map. |
208 | * |
209 | * For a detailed description of tracing_map_elt objects please see |
210 | * the overview of tracing_map data structures at the beginning of |
211 | * this file. |
212 | * |
213 | * All the methods below are optional. |
214 | * |
215 | * @elt_alloc: When a tracing_map_elt is allocated, this function, if |
216 | * defined, will be called and gives clients the opportunity to |
217 | * allocate additional data and attach it to the element |
218 | * (tracing_map_elt->private_data is meant for that purpose). |
219 | * Element allocation occurs before tracing begins, when the |
220 | * tracing_map_init() call is made by client code. |
221 | * |
222 | * @elt_free: When a tracing_map_elt is freed, this function is called |
223 | * and allows client-allocated per-element data to be freed. |
224 | * |
225 | * @elt_clear: This callback allows per-element client-defined data to |
226 | * be cleared, if applicable. |
227 | * |
228 | * @elt_init: This callback allows per-element client-defined data to |
229 | * be initialized when used i.e. when the element is actually |
230 | * claimed by tracing_map_insert() in the context of the map |
231 | * insertion. |
232 | */ |
233 | struct tracing_map_ops { |
234 | int (*elt_alloc)(struct tracing_map_elt *elt); |
235 | void (*elt_free)(struct tracing_map_elt *elt); |
236 | void (*elt_clear)(struct tracing_map_elt *elt); |
237 | void (*elt_init)(struct tracing_map_elt *elt); |
238 | }; |
239 | |
240 | extern struct tracing_map * |
241 | tracing_map_create(unsigned int map_bits, |
242 | unsigned int key_size, |
243 | const struct tracing_map_ops *ops, |
244 | void *private_data); |
245 | extern int tracing_map_init(struct tracing_map *map); |
246 | |
247 | extern int tracing_map_add_sum_field(struct tracing_map *map); |
248 | extern int tracing_map_add_var(struct tracing_map *map); |
249 | extern int tracing_map_add_key_field(struct tracing_map *map, |
250 | unsigned int offset, |
251 | tracing_map_cmp_fn_t cmp_fn); |
252 | |
253 | extern void tracing_map_destroy(struct tracing_map *map); |
254 | extern void tracing_map_clear(struct tracing_map *map); |
255 | |
256 | extern struct tracing_map_elt * |
257 | tracing_map_insert(struct tracing_map *map, void *key); |
258 | extern struct tracing_map_elt * |
259 | tracing_map_lookup(struct tracing_map *map, void *key); |
260 | |
261 | extern tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size, |
262 | int field_is_signed); |
263 | extern int tracing_map_cmp_string(void *val_a, void *val_b); |
264 | extern int tracing_map_cmp_none(void *val_a, void *val_b); |
265 | |
266 | extern void tracing_map_update_sum(struct tracing_map_elt *elt, |
267 | unsigned int i, u64 n); |
268 | extern void tracing_map_set_var(struct tracing_map_elt *elt, |
269 | unsigned int i, u64 n); |
270 | extern bool tracing_map_var_set(struct tracing_map_elt *elt, unsigned int i); |
271 | extern u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i); |
272 | extern u64 tracing_map_read_var(struct tracing_map_elt *elt, unsigned int i); |
273 | extern u64 tracing_map_read_var_once(struct tracing_map_elt *elt, unsigned int i); |
274 | |
275 | extern int |
276 | tracing_map_sort_entries(struct tracing_map *map, |
277 | struct tracing_map_sort_key *sort_keys, |
278 | unsigned int n_sort_keys, |
279 | struct tracing_map_sort_entry ***sort_entries); |
280 | |
281 | extern void |
282 | tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries, |
283 | unsigned int n_entries); |
284 | #endif /* __TRACING_MAP_H */ |
285 | |