// SPDX-License-Identifier: GPL-2.0 /* * tracing_map - lock-free map for tracing * * Copyright (C) 2015 Tom Zanussi <[email protected]> * * tracing_map implementation inspired by lock-free map algorithms * originated by Dr. Cliff Click: * * http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable * http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf */ #include <linux/vmalloc.h> #include <linux/jhash.h> #include <linux/slab.h> #include <linux/sort.h> #include <linux/kmemleak.h> #include "tracing_map.h" #include "trace.h" /* * NOTE: For a detailed description of the data structures used by * these functions (such as tracing_map_elt) please see the overview * of tracing_map data structures at the beginning of tracing_map.h. */ /** * tracing_map_update_sum - Add a value to a tracing_map_elt's sum field * @elt: The tracing_map_elt * @i: The index of the given sum associated with the tracing_map_elt * @n: The value to add to the sum * * Add n to sum i associated with the specified tracing_map_elt * instance. The index i is the index returned by the call to * tracing_map_add_sum_field() when the tracing map was set up. */ void tracing_map_update_sum(struct tracing_map_elt *elt, unsigned int i, u64 n) { … } /** * tracing_map_read_sum - Return the value of a tracing_map_elt's sum field * @elt: The tracing_map_elt * @i: The index of the given sum associated with the tracing_map_elt * * Retrieve the value of the sum i associated with the specified * tracing_map_elt instance. The index i is the index returned by the * call to tracing_map_add_sum_field() when the tracing map was set * up. * * Return: The sum associated with field i for elt. */ u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i) { … } /** * tracing_map_set_var - Assign a tracing_map_elt's variable field * @elt: The tracing_map_elt * @i: The index of the given variable associated with the tracing_map_elt * @n: The value to assign * * Assign n to variable i associated with the specified tracing_map_elt * instance. The index i is the index returned by the call to * tracing_map_add_var() when the tracing map was set up. */ void tracing_map_set_var(struct tracing_map_elt *elt, unsigned int i, u64 n) { … } /** * tracing_map_var_set - Return whether or not a variable has been set * @elt: The tracing_map_elt * @i: The index of the given variable associated with the tracing_map_elt * * Return true if the variable has been set, false otherwise. The * index i is the index returned by the call to tracing_map_add_var() * when the tracing map was set up. */ bool tracing_map_var_set(struct tracing_map_elt *elt, unsigned int i) { … } /** * tracing_map_read_var - Return the value of a tracing_map_elt's variable field * @elt: The tracing_map_elt * @i: The index of the given variable associated with the tracing_map_elt * * Retrieve the value of the variable i associated with the specified * tracing_map_elt instance. The index i is the index returned by the * call to tracing_map_add_var() when the tracing map was set * up. * * Return: The variable value associated with field i for elt. */ u64 tracing_map_read_var(struct tracing_map_elt *elt, unsigned int i) { … } /** * tracing_map_read_var_once - Return and reset a tracing_map_elt's variable field * @elt: The tracing_map_elt * @i: The index of the given variable associated with the tracing_map_elt * * Retrieve the value of the variable i associated with the specified * tracing_map_elt instance, and reset the variable to the 'not set' * state. The index i is the index returned by the call to * tracing_map_add_var() when the tracing map was set up. The reset * essentially makes the variable a read-once variable if it's only * accessed using this function. * * Return: The variable value associated with field i for elt. */ u64 tracing_map_read_var_once(struct tracing_map_elt *elt, unsigned int i) { … } int tracing_map_cmp_string(void *val_a, void *val_b) { … } int tracing_map_cmp_none(void *val_a, void *val_b) { … } static int tracing_map_cmp_atomic64(void *val_a, void *val_b) { … } #define DEFINE_TRACING_MAP_CMP_FN(type) … DEFINE_TRACING_MAP_CMP_FN(s64); DEFINE_TRACING_MAP_CMP_FN(u64); DEFINE_TRACING_MAP_CMP_FN(s32); DEFINE_TRACING_MAP_CMP_FN(u32); DEFINE_TRACING_MAP_CMP_FN(s16); DEFINE_TRACING_MAP_CMP_FN(u16); DEFINE_TRACING_MAP_CMP_FN(s8); DEFINE_TRACING_MAP_CMP_FN(u8); tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size, int field_is_signed) { … } static int tracing_map_add_field(struct tracing_map *map, tracing_map_cmp_fn_t cmp_fn) { … } /** * tracing_map_add_sum_field - Add a field describing a tracing_map sum * @map: The tracing_map * * Add a sum field to the key and return the index identifying it in * the map and associated tracing_map_elts. This is the index used * for instance to update a sum for a particular tracing_map_elt using * tracing_map_update_sum() or reading it via tracing_map_read_sum(). * * Return: The index identifying the field in the map and associated * tracing_map_elts, or -EINVAL on error. */ int tracing_map_add_sum_field(struct tracing_map *map) { … } /** * tracing_map_add_var - Add a field describing a tracing_map var * @map: The tracing_map * * Add a var to the map and return the index identifying it in the map * and associated tracing_map_elts. This is the index used for * instance to update a var for a particular tracing_map_elt using * tracing_map_update_var() or reading it via tracing_map_read_var(). * * Return: The index identifying the var in the map and associated * tracing_map_elts, or -EINVAL on error. */ int tracing_map_add_var(struct tracing_map *map) { … } /** * tracing_map_add_key_field - Add a field describing a tracing_map key * @map: The tracing_map * @offset: The offset within the key * @cmp_fn: The comparison function that will be used to sort on the key * * Let the map know there is a key and that if it's used as a sort key * to use cmp_fn. * * A key can be a subset of a compound key; for that purpose, the * offset param is used to describe where within the compound key * the key referenced by this key field resides. * * Return: The index identifying the field in the map and associated * tracing_map_elts, or -EINVAL on error. */ int tracing_map_add_key_field(struct tracing_map *map, unsigned int offset, tracing_map_cmp_fn_t cmp_fn) { … } static void tracing_map_array_clear(struct tracing_map_array *a) { … } static void tracing_map_array_free(struct tracing_map_array *a) { … } static struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts, unsigned int entry_size) { … } static void tracing_map_elt_clear(struct tracing_map_elt *elt) { … } static void tracing_map_elt_init_fields(struct tracing_map_elt *elt) { … } static void tracing_map_elt_free(struct tracing_map_elt *elt) { … } static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map) { … } static struct tracing_map_elt *get_free_elt(struct tracing_map *map) { … } static void tracing_map_free_elts(struct tracing_map *map) { … } static int tracing_map_alloc_elts(struct tracing_map *map) { … } static inline bool keys_match(void *key, void *test_key, unsigned key_size) { … } static inline struct tracing_map_elt * __tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only) { … } /** * tracing_map_insert - Insert key and/or retrieve val from a tracing_map * @map: The tracing_map to insert into * @key: The key to insert * * Inserts a key into a tracing_map and creates and returns a new * tracing_map_elt for it, or if the key has already been inserted by * a previous call, returns the tracing_map_elt already associated * with it. When the map was created, the number of elements to be * allocated for the map was specified (internally maintained as * 'max_elts' in struct tracing_map), and that number of * tracing_map_elts was created by tracing_map_init(). This is the * pre-allocated pool of tracing_map_elts that tracing_map_insert() * will allocate from when adding new keys. Once that pool is * exhausted, tracing_map_insert() is useless and will return NULL to * signal that state. There are two user-visible tracing_map * variables, 'hits' and 'drops', which are updated by this function. * Every time an element is either successfully inserted or retrieved, * the 'hits' value is incremented. Every time an element insertion * fails, the 'drops' value is incremented. * * This is a lock-free tracing map insertion function implementing a * modified form of Cliff Click's basic insertion algorithm. It * requires the table size be a power of two. To prevent any * possibility of an infinite loop we always make the internal table * size double the size of the requested table size (max_elts * 2). * Likewise, we never reuse a slot or resize or delete elements - when * we've reached max_elts entries, we simply return NULL once we've * run out of entries. Readers can at any point in time traverse the * tracing map and safely access the key/val pairs. * * Return: the tracing_map_elt pointer val associated with the key. * If this was a newly inserted key, the val will be a newly allocated * and associated tracing_map_elt pointer val. If the key wasn't * found and the pool of tracing_map_elts has been exhausted, NULL is * returned and no further insertions will succeed. */ struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key) { … } /** * tracing_map_lookup - Retrieve val from a tracing_map * @map: The tracing_map to perform the lookup on * @key: The key to look up * * Looks up key in tracing_map and if found returns the matching * tracing_map_elt. This is a lock-free lookup; see * tracing_map_insert() for details on tracing_map and how it works. * Every time an element is retrieved, the 'hits' value is * incremented. There is one user-visible tracing_map variable, * 'hits', which is updated by this function. Every time an element * is successfully retrieved, the 'hits' value is incremented. The * 'drops' value is never updated by this function. * * Return: the tracing_map_elt pointer val associated with the key. * If the key wasn't found, NULL is returned. */ struct tracing_map_elt *tracing_map_lookup(struct tracing_map *map, void *key) { … } /** * tracing_map_destroy - Destroy a tracing_map * @map: The tracing_map to destroy * * Frees a tracing_map along with its associated array of * tracing_map_elts. * * Callers should make sure there are no readers or writers actively * reading or inserting into the map before calling this. */ void tracing_map_destroy(struct tracing_map *map) { … } /** * tracing_map_clear - Clear a tracing_map * @map: The tracing_map to clear * * Resets the tracing map to a cleared or initial state. The * tracing_map_elts are all cleared, and the array of struct * tracing_map_entry is reset to an initialized state. * * Callers should make sure there are no writers actively inserting * into the map before calling this. */ void tracing_map_clear(struct tracing_map *map) { … } static void set_sort_key(struct tracing_map *map, struct tracing_map_sort_key *sort_key) { … } /** * tracing_map_create - Create a lock-free map and element pool * @map_bits: The size of the map (2 ** map_bits) * @key_size: The size of the key for the map in bytes * @ops: Optional client-defined tracing_map_ops instance * @private_data: Client data associated with the map * * Creates and sets up a map to contain 2 ** map_bits number of * elements (internally maintained as 'max_elts' in struct * tracing_map). Before using, map fields should be added to the map * with tracing_map_add_sum_field() and tracing_map_add_key_field(). * tracing_map_init() should then be called to allocate the array of * tracing_map_elts, in order to avoid allocating anything in the map * insertion path. The user-specified map size reflects the maximum * number of elements that can be contained in the table requested by * the user - internally we double that in order to keep the table * sparse and keep collisions manageable. * * A tracing_map is a special-purpose map designed to aggregate or * 'sum' one or more values associated with a specific object of type * tracing_map_elt, which is attached by the map to a given key. * * tracing_map_create() sets up the map itself, and provides * operations for inserting tracing_map_elts, but doesn't allocate the * tracing_map_elts themselves, or provide a means for describing the * keys or sums associated with the tracing_map_elts. All * tracing_map_elts for a given map have the same set of sums and * keys, which are defined by the client using the functions * tracing_map_add_key_field() and tracing_map_add_sum_field(). Once * the fields are defined, the pool of elements allocated for the map * can be created, which occurs when the client code calls * tracing_map_init(). * * When tracing_map_init() returns, tracing_map_elt elements can be * inserted into the map using tracing_map_insert(). When called, * tracing_map_insert() grabs a free tracing_map_elt from the pool, or * finds an existing match in the map and in either case returns it. * The client can then use tracing_map_update_sum() and * tracing_map_read_sum() to update or read a given sum field for the * tracing_map_elt. * * The client can at any point retrieve and traverse the current set * of inserted tracing_map_elts in a tracing_map, via * tracing_map_sort_entries(). Sorting can be done on any field, * including keys. * * See tracing_map.h for a description of tracing_map_ops. * * Return: the tracing_map pointer if successful, ERR_PTR if not. */ struct tracing_map *tracing_map_create(unsigned int map_bits, unsigned int key_size, const struct tracing_map_ops *ops, void *private_data) { … } /** * tracing_map_init - Allocate and clear a map's tracing_map_elts * @map: The tracing_map to initialize * * Allocates a clears a pool of tracing_map_elts equal to the * user-specified size of 2 ** map_bits (internally maintained as * 'max_elts' in struct tracing_map). Before using, the map fields * should be added to the map with tracing_map_add_sum_field() and * tracing_map_add_key_field(). tracing_map_init() should then be * called to allocate the array of tracing_map_elts, in order to avoid * allocating anything in the map insertion path. The user-specified * map size reflects the max number of elements requested by the user * - internally we double that in order to keep the table sparse and * keep collisions manageable. * * See tracing_map.h for a description of tracing_map_ops. * * Return: the tracing_map pointer if successful, ERR_PTR if not. */ int tracing_map_init(struct tracing_map *map) { … } static int cmp_entries_dup(const void *A, const void *B) { … } static int cmp_entries_sum(const void *A, const void *B) { … } static int cmp_entries_key(const void *A, const void *B) { … } static void destroy_sort_entry(struct tracing_map_sort_entry *entry) { … } /** * tracing_map_destroy_sort_entries - Destroy an array of sort entries * @entries: The entries to destroy * @n_entries: The number of entries in the array * * Destroy the elements returned by a tracing_map_sort_entries() call. */ void tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries, unsigned int n_entries) { … } static struct tracing_map_sort_entry * create_sort_entry(void *key, struct tracing_map_elt *elt) { … } static void detect_dups(struct tracing_map_sort_entry **sort_entries, int n_entries, unsigned int key_size) { … } static bool is_key(struct tracing_map *map, unsigned int field_idx) { … } static void sort_secondary(struct tracing_map *map, const struct tracing_map_sort_entry **entries, unsigned int n_entries, struct tracing_map_sort_key *primary_key, struct tracing_map_sort_key *secondary_key) { … } /** * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map * @map: The tracing_map * @sort_keys: The sort key to use for sorting * @n_sort_keys: hitcount, always have at least one * @sort_entries: outval: pointer to allocated and sorted array of entries * * tracing_map_sort_entries() sorts the current set of entries in the * map and returns the list of tracing_map_sort_entries containing * them to the client in the sort_entries param. The client can * access the struct tracing_map_elt element of interest directly as * the 'elt' field of a returned struct tracing_map_sort_entry object. * * The sort_key has only two fields: idx and descending. 'idx' refers * to the index of the field added via tracing_map_add_sum_field() or * tracing_map_add_key_field() when the tracing_map was initialized. * 'descending' is a flag that if set reverses the sort order, which * by default is ascending. * * The client should not hold on to the returned array but should use * it and call tracing_map_destroy_sort_entries() when done. * * Return: the number of sort_entries in the struct tracing_map_sort_entry * array, negative on error */ int tracing_map_sort_entries(struct tracing_map *map, struct tracing_map_sort_key *sort_keys, unsigned int n_sort_keys, struct tracing_map_sort_entry ***sort_entries) { … }
Codebase Browser
linux