tracing_map.h 11 KB

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