1bb730b58SSteven Rostedt (VMware) // SPDX-License-Identifier: GPL-2.0 208d43a5fSTom Zanussi #ifndef __TRACING_MAP_H 308d43a5fSTom Zanussi #define __TRACING_MAP_H 408d43a5fSTom Zanussi 508d43a5fSTom Zanussi #define TRACING_MAP_BITS_DEFAULT 11 608d43a5fSTom Zanussi #define TRACING_MAP_BITS_MAX 17 708d43a5fSTom Zanussi #define TRACING_MAP_BITS_MIN 7 808d43a5fSTom Zanussi 94f36c2d8STom Zanussi #define TRACING_MAP_KEYS_MAX 3 103b772b96STom Zanussi #define TRACING_MAP_VALS_MAX 3 113b772b96STom Zanussi #define TRACING_MAP_FIELDS_MAX (TRACING_MAP_KEYS_MAX + \ 123b772b96STom Zanussi TRACING_MAP_VALS_MAX) 132734b629STom Zanussi #define TRACING_MAP_VARS_MAX 16 1408d43a5fSTom Zanussi #define TRACING_MAP_SORT_KEYS_MAX 2 1508d43a5fSTom Zanussi 1608d43a5fSTom Zanussi typedef int (*tracing_map_cmp_fn_t) (void *val_a, void *val_b); 1708d43a5fSTom Zanussi 1808d43a5fSTom Zanussi /* 1908d43a5fSTom Zanussi * This is an overview of the tracing_map data structures and how they 2008d43a5fSTom Zanussi * relate to the tracing_map API. The details of the algorithms 2108d43a5fSTom Zanussi * aren't discussed here - this is just a general overview of the data 2208d43a5fSTom Zanussi * structures and how they interact with the API. 2308d43a5fSTom Zanussi * 2408d43a5fSTom Zanussi * The central data structure of the tracing_map is an initially 2508d43a5fSTom Zanussi * zeroed array of struct tracing_map_entry (stored in the map field 2608d43a5fSTom Zanussi * of struct tracing_map). tracing_map_entry is a very simple data 2708d43a5fSTom Zanussi * structure containing only two fields: a 32-bit unsigned 'key' 2808d43a5fSTom Zanussi * variable and a pointer named 'val'. This array of struct 2908d43a5fSTom Zanussi * tracing_map_entry is essentially a hash table which will be 3008d43a5fSTom Zanussi * modified by a single function, tracing_map_insert(), but which can 3108d43a5fSTom Zanussi * be traversed and read by a user at any time (though the user does 3208d43a5fSTom Zanussi * this indirectly via an array of tracing_map_sort_entry - see the 3308d43a5fSTom Zanussi * explanation of that data structure in the discussion of the 3408d43a5fSTom Zanussi * sorting-related data structures below). 3508d43a5fSTom Zanussi * 3608d43a5fSTom Zanussi * The central function of the tracing_map API is 3708d43a5fSTom Zanussi * tracing_map_insert(). tracing_map_insert() hashes the 3808d43a5fSTom Zanussi * arbitrarily-sized key passed into it into a 32-bit unsigned key. 3908d43a5fSTom Zanussi * It then uses this key, truncated to the array size, as an index 4008d43a5fSTom Zanussi * into the array of tracing_map_entries. If the value of the 'key' 4108d43a5fSTom Zanussi * field of the tracing_map_entry found at that location is 0, then 4208d43a5fSTom Zanussi * that entry is considered to be free and can be claimed, by 4308d43a5fSTom Zanussi * replacing the 0 in the 'key' field of the tracing_map_entry with 4408d43a5fSTom Zanussi * the new 32-bit hashed key. Once claimed, that tracing_map_entry's 4508d43a5fSTom Zanussi * 'val' field is then used to store a unique element which will be 4608d43a5fSTom Zanussi * forever associated with that 32-bit hashed key in the 4708d43a5fSTom Zanussi * tracing_map_entry. 4808d43a5fSTom Zanussi * 4908d43a5fSTom Zanussi * That unique element now in the tracing_map_entry's 'val' field is 5008d43a5fSTom Zanussi * an instance of tracing_map_elt, where 'elt' in the latter part of 5108d43a5fSTom Zanussi * that variable name is short for 'element'. The purpose of a 528d44f2f3SSteven Rostedt (Red Hat) * tracing_map_elt is to hold values specific to the particular 53*2b5894ccSQiujun Huang * 32-bit hashed key it's associated with. Things such as the unique 5408d43a5fSTom Zanussi * set of aggregated sums associated with the 32-bit hashed key, along 5508d43a5fSTom Zanussi * with a copy of the full key associated with the entry, and which 5608d43a5fSTom Zanussi * was used to produce the 32-bit hashed key. 5708d43a5fSTom Zanussi * 5808d43a5fSTom Zanussi * When tracing_map_create() is called to create the tracing map, the 5908d43a5fSTom Zanussi * user specifies (indirectly via the map_bits param, the details are 6008d43a5fSTom Zanussi * unimportant for this discussion) the maximum number of elements 6108d43a5fSTom Zanussi * that the map can hold (stored in the max_elts field of struct 6208d43a5fSTom Zanussi * tracing_map). This is the maximum possible number of 6308d43a5fSTom Zanussi * tracing_map_entries in the tracing_map_entry array which can be 6408d43a5fSTom Zanussi * 'claimed' as described in the above discussion, and therefore is 6508d43a5fSTom Zanussi * also the maximum number of tracing_map_elts that can be associated 6608d43a5fSTom Zanussi * with the tracing_map_entry array in the tracing_map. Because of 6708d43a5fSTom Zanussi * the way the insertion algorithm works, the size of the allocated 6808d43a5fSTom Zanussi * tracing_map_entry array is always twice the maximum number of 6908d43a5fSTom Zanussi * elements (2 * max_elts). This value is stored in the map_size 7008d43a5fSTom Zanussi * field of struct tracing_map. 7108d43a5fSTom Zanussi * 7208d43a5fSTom Zanussi * Because tracing_map_insert() needs to work from any context, 7308d43a5fSTom Zanussi * including from within the memory allocation functions themselves, 7408d43a5fSTom Zanussi * both the tracing_map_entry array and a pool of max_elts 7508d43a5fSTom Zanussi * tracing_map_elts are pre-allocated before any call is made to 7608d43a5fSTom Zanussi * tracing_map_insert(). 7708d43a5fSTom Zanussi * 7808d43a5fSTom Zanussi * The tracing_map_entry array is allocated as a single block by 7908d43a5fSTom Zanussi * tracing_map_create(). 8008d43a5fSTom Zanussi * 8108d43a5fSTom Zanussi * Because the tracing_map_elts are much larger objects and can't 8208d43a5fSTom Zanussi * generally be allocated together as a single large array without 8308d43a5fSTom Zanussi * failure, they're allocated individually, by tracing_map_init(). 8408d43a5fSTom Zanussi * 8508d43a5fSTom Zanussi * The pool of tracing_map_elts are allocated by tracing_map_init() 8608d43a5fSTom Zanussi * rather than by tracing_map_create() because at the time 8708d43a5fSTom Zanussi * tracing_map_create() is called, there isn't enough information to 8808d43a5fSTom Zanussi * create the tracing_map_elts. Specifically,the user first needs to 8908d43a5fSTom Zanussi * tell the tracing_map implementation how many fields the 9008d43a5fSTom Zanussi * tracing_map_elts contain, and which types of fields they are (key 9108d43a5fSTom Zanussi * or sum). The user does this via the tracing_map_add_sum_field() 9208d43a5fSTom Zanussi * and tracing_map_add_key_field() functions, following which the user 9308d43a5fSTom Zanussi * calls tracing_map_init() to finish up the tracing map setup. The 9408d43a5fSTom Zanussi * array holding the pointers which make up the pre-allocated pool of 9508d43a5fSTom Zanussi * tracing_map_elts is allocated as a single block and is stored in 9608d43a5fSTom Zanussi * the elts field of struct tracing_map. 9708d43a5fSTom Zanussi * 9808d43a5fSTom Zanussi * There is also a set of structures used for sorting that might 9908d43a5fSTom Zanussi * benefit from some minimal explanation. 10008d43a5fSTom Zanussi * 10108d43a5fSTom Zanussi * struct tracing_map_sort_key is used to drive the sort at any given 10208d43a5fSTom Zanussi * time. By 'any given time' we mean that a different 10308d43a5fSTom Zanussi * tracing_map_sort_key will be used at different times depending on 10408d43a5fSTom Zanussi * whether the sort currently being performed is a primary or a 10508d43a5fSTom Zanussi * secondary sort. 10608d43a5fSTom Zanussi * 10708d43a5fSTom Zanussi * The sort key is very simple, consisting of the field index of the 10808d43a5fSTom Zanussi * tracing_map_elt field to sort on (which the user saved when adding 10908d43a5fSTom Zanussi * the field), and whether the sort should be done in an ascending or 11008d43a5fSTom Zanussi * descending order. 11108d43a5fSTom Zanussi * 11208d43a5fSTom Zanussi * For the convenience of the sorting code, a tracing_map_sort_entry 11308d43a5fSTom Zanussi * is created for each tracing_map_elt, again individually allocated 11408d43a5fSTom Zanussi * to avoid failures that might be expected if allocated as a single 11508d43a5fSTom Zanussi * large array of struct tracing_map_sort_entry. 11608d43a5fSTom Zanussi * tracing_map_sort_entry instances are the objects expected by the 11708d43a5fSTom Zanussi * various internal sorting functions, and are also what the user 11808d43a5fSTom Zanussi * ultimately receives after calling tracing_map_sort_entries(). 11908d43a5fSTom Zanussi * Because it doesn't make sense for users to access an unordered and 12008d43a5fSTom Zanussi * sparsely populated tracing_map directly, the 12108d43a5fSTom Zanussi * tracing_map_sort_entries() function is provided so that users can 12208d43a5fSTom Zanussi * retrieve a sorted list of all existing elements. In addition to 12308d43a5fSTom Zanussi * the associated tracing_map_elt 'elt' field contained within the 12408d43a5fSTom Zanussi * tracing_map_sort_entry, which is the object of interest to the 12508d43a5fSTom Zanussi * user, tracing_map_sort_entry objects contain a number of additional 12608d43a5fSTom Zanussi * fields which are used for caching and internal purposes and can 12708d43a5fSTom Zanussi * safely be ignored. 12808d43a5fSTom Zanussi */ 12908d43a5fSTom Zanussi 13008d43a5fSTom Zanussi struct tracing_map_field { 13108d43a5fSTom Zanussi tracing_map_cmp_fn_t cmp_fn; 13208d43a5fSTom Zanussi union { 13308d43a5fSTom Zanussi atomic64_t sum; 13408d43a5fSTom Zanussi unsigned int offset; 13508d43a5fSTom Zanussi }; 13608d43a5fSTom Zanussi }; 13708d43a5fSTom Zanussi 13808d43a5fSTom Zanussi struct tracing_map_elt { 13908d43a5fSTom Zanussi struct tracing_map *map; 14008d43a5fSTom Zanussi struct tracing_map_field *fields; 1412734b629STom Zanussi atomic64_t *vars; 1422734b629STom Zanussi bool *var_set; 14308d43a5fSTom Zanussi void *key; 14408d43a5fSTom Zanussi void *private_data; 14508d43a5fSTom Zanussi }; 14608d43a5fSTom Zanussi 14708d43a5fSTom Zanussi struct tracing_map_entry { 14808d43a5fSTom Zanussi u32 key; 14908d43a5fSTom Zanussi struct tracing_map_elt *val; 15008d43a5fSTom Zanussi }; 15108d43a5fSTom Zanussi 15208d43a5fSTom Zanussi struct tracing_map_sort_key { 15308d43a5fSTom Zanussi unsigned int field_idx; 15408d43a5fSTom Zanussi bool descending; 15508d43a5fSTom Zanussi }; 15608d43a5fSTom Zanussi 15708d43a5fSTom Zanussi struct tracing_map_sort_entry { 15808d43a5fSTom Zanussi void *key; 15908d43a5fSTom Zanussi struct tracing_map_elt *elt; 16008d43a5fSTom Zanussi bool elt_copied; 16108d43a5fSTom Zanussi bool dup; 16208d43a5fSTom Zanussi }; 16308d43a5fSTom Zanussi 16408d43a5fSTom Zanussi struct tracing_map_array { 16508d43a5fSTom Zanussi unsigned int entries_per_page; 16608d43a5fSTom Zanussi unsigned int entry_size_shift; 16708d43a5fSTom Zanussi unsigned int entry_shift; 16808d43a5fSTom Zanussi unsigned int entry_mask; 16908d43a5fSTom Zanussi unsigned int n_pages; 17008d43a5fSTom Zanussi void **pages; 17108d43a5fSTom Zanussi }; 17208d43a5fSTom Zanussi 17308d43a5fSTom Zanussi #define TRACING_MAP_ARRAY_ELT(array, idx) \ 17408d43a5fSTom Zanussi (array->pages[idx >> array->entry_shift] + \ 17508d43a5fSTom Zanussi ((idx & array->entry_mask) << array->entry_size_shift)) 17608d43a5fSTom Zanussi 17708d43a5fSTom Zanussi #define TRACING_MAP_ENTRY(array, idx) \ 17808d43a5fSTom Zanussi ((struct tracing_map_entry *)TRACING_MAP_ARRAY_ELT(array, idx)) 17908d43a5fSTom Zanussi 18008d43a5fSTom Zanussi #define TRACING_MAP_ELT(array, idx) \ 18108d43a5fSTom Zanussi ((struct tracing_map_elt **)TRACING_MAP_ARRAY_ELT(array, idx)) 18208d43a5fSTom Zanussi 18308d43a5fSTom Zanussi struct tracing_map { 18408d43a5fSTom Zanussi unsigned int key_size; 18508d43a5fSTom Zanussi unsigned int map_bits; 18608d43a5fSTom Zanussi unsigned int map_size; 18708d43a5fSTom Zanussi unsigned int max_elts; 18808d43a5fSTom Zanussi atomic_t next_elt; 18908d43a5fSTom Zanussi struct tracing_map_array *elts; 19008d43a5fSTom Zanussi struct tracing_map_array *map; 19108d43a5fSTom Zanussi const struct tracing_map_ops *ops; 19208d43a5fSTom Zanussi void *private_data; 19308d43a5fSTom Zanussi struct tracing_map_field fields[TRACING_MAP_FIELDS_MAX]; 19408d43a5fSTom Zanussi unsigned int n_fields; 19508d43a5fSTom Zanussi int key_idx[TRACING_MAP_KEYS_MAX]; 19608d43a5fSTom Zanussi unsigned int n_keys; 19708d43a5fSTom Zanussi struct tracing_map_sort_key sort_key; 1982734b629STom Zanussi unsigned int n_vars; 19908d43a5fSTom Zanussi atomic64_t hits; 20008d43a5fSTom Zanussi atomic64_t drops; 20108d43a5fSTom Zanussi }; 20208d43a5fSTom Zanussi 20308d43a5fSTom Zanussi /** 20408d43a5fSTom Zanussi * struct tracing_map_ops - callbacks for tracing_map 20508d43a5fSTom Zanussi * 20608d43a5fSTom Zanussi * The methods in this structure define callback functions for various 20708d43a5fSTom Zanussi * operations on a tracing_map or objects related to a tracing_map. 20808d43a5fSTom Zanussi * 20908d43a5fSTom Zanussi * For a detailed description of tracing_map_elt objects please see 21008d43a5fSTom Zanussi * the overview of tracing_map data structures at the beginning of 21108d43a5fSTom Zanussi * this file. 21208d43a5fSTom Zanussi * 21308d43a5fSTom Zanussi * All the methods below are optional. 21408d43a5fSTom Zanussi * 21508d43a5fSTom Zanussi * @elt_alloc: When a tracing_map_elt is allocated, this function, if 21608d43a5fSTom Zanussi * defined, will be called and gives clients the opportunity to 21708d43a5fSTom Zanussi * allocate additional data and attach it to the element 21808d43a5fSTom Zanussi * (tracing_map_elt->private_data is meant for that purpose). 21908d43a5fSTom Zanussi * Element allocation occurs before tracing begins, when the 22008d43a5fSTom Zanussi * tracing_map_init() call is made by client code. 22108d43a5fSTom Zanussi * 22208d43a5fSTom Zanussi * @elt_free: When a tracing_map_elt is freed, this function is called 22308d43a5fSTom Zanussi * and allows client-allocated per-element data to be freed. 22408d43a5fSTom Zanussi * 22508d43a5fSTom Zanussi * @elt_clear: This callback allows per-element client-defined data to 22608d43a5fSTom Zanussi * be cleared, if applicable. 22708d43a5fSTom Zanussi * 22808d43a5fSTom Zanussi * @elt_init: This callback allows per-element client-defined data to 22908d43a5fSTom Zanussi * be initialized when used i.e. when the element is actually 23008d43a5fSTom Zanussi * claimed by tracing_map_insert() in the context of the map 23108d43a5fSTom Zanussi * insertion. 23208d43a5fSTom Zanussi */ 23308d43a5fSTom Zanussi struct tracing_map_ops { 23408d43a5fSTom Zanussi int (*elt_alloc)(struct tracing_map_elt *elt); 23508d43a5fSTom Zanussi void (*elt_free)(struct tracing_map_elt *elt); 23608d43a5fSTom Zanussi void (*elt_clear)(struct tracing_map_elt *elt); 23708d43a5fSTom Zanussi void (*elt_init)(struct tracing_map_elt *elt); 23808d43a5fSTom Zanussi }; 23908d43a5fSTom Zanussi 24008d43a5fSTom Zanussi extern struct tracing_map * 24108d43a5fSTom Zanussi tracing_map_create(unsigned int map_bits, 24208d43a5fSTom Zanussi unsigned int key_size, 24308d43a5fSTom Zanussi const struct tracing_map_ops *ops, 24408d43a5fSTom Zanussi void *private_data); 24508d43a5fSTom Zanussi extern int tracing_map_init(struct tracing_map *map); 24608d43a5fSTom Zanussi 24708d43a5fSTom Zanussi extern int tracing_map_add_sum_field(struct tracing_map *map); 2482734b629STom Zanussi extern int tracing_map_add_var(struct tracing_map *map); 24908d43a5fSTom Zanussi extern int tracing_map_add_key_field(struct tracing_map *map, 25008d43a5fSTom Zanussi unsigned int offset, 25108d43a5fSTom Zanussi tracing_map_cmp_fn_t cmp_fn); 25208d43a5fSTom Zanussi 25308d43a5fSTom Zanussi extern void tracing_map_destroy(struct tracing_map *map); 25408d43a5fSTom Zanussi extern void tracing_map_clear(struct tracing_map *map); 25508d43a5fSTom Zanussi 25608d43a5fSTom Zanussi extern struct tracing_map_elt * 25708d43a5fSTom Zanussi tracing_map_insert(struct tracing_map *map, void *key); 25808d43a5fSTom Zanussi extern struct tracing_map_elt * 25908d43a5fSTom Zanussi tracing_map_lookup(struct tracing_map *map, void *key); 26008d43a5fSTom Zanussi 26108d43a5fSTom Zanussi extern tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size, 26208d43a5fSTom Zanussi int field_is_signed); 26308d43a5fSTom Zanussi extern int tracing_map_cmp_string(void *val_a, void *val_b); 26408d43a5fSTom Zanussi extern int tracing_map_cmp_none(void *val_a, void *val_b); 26508d43a5fSTom Zanussi 26608d43a5fSTom Zanussi extern void tracing_map_update_sum(struct tracing_map_elt *elt, 26708d43a5fSTom Zanussi unsigned int i, u64 n); 2682734b629STom Zanussi extern void tracing_map_set_var(struct tracing_map_elt *elt, 2692734b629STom Zanussi unsigned int i, u64 n); 2702734b629STom Zanussi extern bool tracing_map_var_set(struct tracing_map_elt *elt, unsigned int i); 27108d43a5fSTom Zanussi extern u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i); 2722734b629STom Zanussi extern u64 tracing_map_read_var(struct tracing_map_elt *elt, unsigned int i); 2732734b629STom Zanussi extern u64 tracing_map_read_var_once(struct tracing_map_elt *elt, unsigned int i); 2742734b629STom Zanussi 27508d43a5fSTom Zanussi extern int 27608d43a5fSTom Zanussi tracing_map_sort_entries(struct tracing_map *map, 27708d43a5fSTom Zanussi struct tracing_map_sort_key *sort_keys, 27808d43a5fSTom Zanussi unsigned int n_sort_keys, 27908d43a5fSTom Zanussi struct tracing_map_sort_entry ***sort_entries); 28008d43a5fSTom Zanussi 28108d43a5fSTom Zanussi extern void 28208d43a5fSTom Zanussi tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries, 28308d43a5fSTom Zanussi unsigned int n_entries); 28408d43a5fSTom Zanussi #endif /* __TRACING_MAP_H */ 285