/* * tracing_map - lock-free map for tracing * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * Copyright (C) 2015 Tom Zanussi <tom.zanussi@linux.intel.com> * * 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 "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){ atomic64_add(n, &elt->fields[i].sum);} /** * 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){ return (u64)atomic64_read(&elt->fields[i].sum);} int tracing_map_cmp_string(void *val_a, void *val_b){ char *a = val_a; char *b = val_b; return strcmp(a, b);} int tracing_map_cmp_none(void *val_a, void *val_b){ return 0;} static int tracing_map_cmp_atomic64(void *val_a, void *val_b){ u64 a = atomic64_read((atomic64_t *)val_a); u64 b = atomic64_read((atomic64_t *)val_b); return (a > b) ? 1 : ((a < b) ? -1 : 0);} #define DEFINE_TRACING_MAP_CMP_FN(type) \static int tracing_map_cmp_##type(void *val_a, void *val_b) \{ \ type a = *(type *)val_a; \ type b = *(type *)val_b; \ \ return (a > b) ? 1 : ((a < b) ? -1 : 0); \} 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){ tracing_map_cmp_fn_t fn = tracing_map_cmp_none; switch (field_size) { case 8: if (field_is_signed) fn = tracing_map_cmp_s64; else fn = tracing_map_cmp_u64; break; case 4: if (field_is_signed) fn = tracing_map_cmp_s32; else fn = tracing_map_cmp_u32; break; case 2: if (field_is_signed) fn = tracing_map_cmp_s16; else fn = tracing_map_cmp_u16; break; case 1: if (field_is_signed) fn = tracing_map_cmp_s8; else fn = tracing_map_cmp_u8; break; } return fn;} static int tracing_map_add_field(struct tracing_map *map, tracing_map_cmp_fn_t cmp_fn){ int ret = -EINVAL; if (map->n_fields < TRACING_MAP_FIELDS_MAX) { ret = map->n_fields; map->fields[map->n_fields++].cmp_fn = cmp_fn; } return ret;} /** * 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){ return tracing_map_add_field(map, tracing_map_cmp_atomic64);} /** * 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 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) { int idx = tracing_map_add_field(map, cmp_fn); if (idx < 0) return idx; map->fields[idx].offset = offset; map->key_idx[map->n_keys++] = idx; return idx;} void tracing_map_array_clear(struct tracing_map_array *a){ unsigned int i; if (!a->pages) return; for (i = 0; i < a->n_pages; i++) memset(a->pages[i], 0, PAGE_SIZE);} void tracing_map_array_free(struct tracing_map_array *a){ unsigned int i; if (!a) return; if (!a->pages) goto free; for (i = 0; i < a->n_pages; i++) { if (!a->pages[i]) break; free_page((unsigned long)a->pages[i]); } kfree(a->pages); free: kfree(a);} struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts, unsigned int entry_size){ struct tracing_map_array *a; unsigned int i; a = kzalloc(sizeof(*a), GFP_KERNEL); if (!a) return NULL; a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1); a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift); a->n_pages = n_elts / a->entries_per_page; if (!a->n_pages) a->n_pages = 1; a->entry_shift = fls(a->entries_per_page) - 1; a->entry_mask = (1 << a->entry_shift) - 1; a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL); if (!a->pages) goto free; for (i = 0; i < a->n_pages; i++) { a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL); if (!a->pages[i]) goto free; } out: return a; free: tracing_map_array_free(a); a = NULL; goto out;} static void tracing_map_elt_clear(struct tracing_map_elt *elt){ unsigned i; for (i = 0; i < elt->map->n_fields; i++) if (elt->fields[i].cmp_fn == tracing_map_cmp_atomic64) atomic64_set(&elt->fields[i].sum, 0); if (elt->map->ops && elt->map->ops->elt_clear) elt->map->ops->elt_clear(elt);} static void tracing_map_elt_init_fields(struct tracing_map_elt *elt){ unsigned int i; tracing_map_elt_clear(elt); for (i = 0; i < elt->map->n_fields; i++) { elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn; if (elt->fields[i].cmp_fn != tracing_map_cmp_atomic64) elt->fields[i].offset = elt->map->fields[i].offset; }} static void tracing_map_elt_free(struct tracing_map_elt *elt){ if (!elt) return; if (elt->map->ops && elt->map->ops->elt_free) elt->map->ops->elt_free(elt); kfree(elt->fields); kfree(elt->key); kfree(elt);} static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map){ struct tracing_map_elt *elt; int err = 0; elt = kzalloc(sizeof(*elt), GFP_KERNEL); if (!elt) return ERR_PTR(-ENOMEM); elt->map = map; elt->key = kzalloc(map->key_size, GFP_KERNEL); if (!elt->key) { err = -ENOMEM; goto free; } elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL); if (!elt->fields) { err = -ENOMEM; goto free; } tracing_map_elt_init_fields(elt); if (map->ops && map->ops->elt_alloc) { err = map->ops->elt_alloc(elt); if (err) goto free; } return elt; free: tracing_map_elt_free(elt); return ERR_PTR(err);} static struct tracing_map_elt *get_free_elt(struct tracing_map *map){ struct tracing_map_elt *elt = NULL; int idx; idx = atomic_inc_return(&map->next_elt); if (idx < map->max_elts) { elt = *(TRACING_MAP_ELT(map->elts, idx)); if (map->ops && map->ops->elt_init) map->ops->elt_init(elt); } return elt;} static void tracing_map_free_elts(struct tracing_map *map){ unsigned int i; if (!map->elts) return; for (i = 0; i < map->max_elts; i++) { tracing_map_elt_free(*(TRACING_MAP_ELT(map->elts, i))); *(TRACING_MAP_ELT(map->elts, i)) = NULL; } tracing_map_array_free(map->elts); map->elts = NULL;} static int tracing_map_alloc_elts(struct tracing_map *map){ unsigned int i; map->elts = tracing_map_array_alloc(map->max_elts, sizeof(struct tracing_map_elt *)); if (!map->elts) return -ENOMEM; for (i = 0; i < map->max_elts; i++) { *(TRACING_MAP_ELT(map->elts, i)) = tracing_map_elt_alloc(map); if (IS_ERR(*(TRACING_MAP_ELT(map->elts, i)))) { *(TRACING_MAP_ELT(map->elts, i)) = NULL; tracing_map_free_elts(map); return -ENOMEM; } } return 0;} static inline bool keys_match(void *key, void *test_key, unsigned key_size){ bool match = true; if (memcmp(key, test_key, key_size)) match = false; return match;} static inline struct tracing_map_elt *__tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only){ u32 idx, key_hash, test_key; struct tracing_map_entry *entry; key_hash = jhash(key, map->key_size, 0); if (key_hash == 0) key_hash = 1; idx = key_hash >> (32 - (map->map_bits + 1)); while (1) { idx &= (map->map_size - 1); entry = TRACING_MAP_ENTRY(map->map, idx); test_key = entry->key; if (test_key && test_key == key_hash && entry->val && keys_match(key, entry->val->key, map->key_size)) { atomic64_inc(&map->hits); return entry->val; } if (!test_key) { if (lookup_only) break; if (!cmpxchg(&entry->key, 0, key_hash)) { struct tracing_map_elt *elt; elt = get_free_elt(map); if (!elt) { atomic64_inc(&map->drops); entry->key = 0; break; } memcpy(elt->key, key, map->key_size); entry->val = elt; atomic64_inc(&map->hits); return entry->val; } } idx++; } return NULL;} /** * 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 incrememented. 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)Lines 1–500 of 1065. Load more
/* * tracing_map - lock-free map for tracing * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * Copyright (C) 2015 Tom Zanussi <tom.zanussi@linux.intel.com> * * 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 "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) { atomic64_add(n, &elt->fields[i].sum); } /** * 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) { return (u64)atomic64_read(&elt->fields[i].sum); } int tracing_map_cmp_string(void *val_a, void *val_b) { char *a = val_a; char *b = val_b; return strcmp(a, b); } int tracing_map_cmp_none(void *val_a, void *val_b) { return 0; } static int tracing_map_cmp_atomic64(void *val_a, void *val_b) { u64 a = atomic64_read((atomic64_t *)val_a); u64 b = atomic64_read((atomic64_t *)val_b); return (a > b) ? 1 : ((a < b) ? -1 : 0); } #define DEFINE_TRACING_MAP_CMP_FN(type) \ static int tracing_map_cmp_##type(void *val_a, void *val_b) \ { \ type a = *(type *)val_a; \ type b = *(type *)val_b; \ \ return (a > b) ? 1 : ((a < b) ? -1 : 0); \ } 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) { tracing_map_cmp_fn_t fn = tracing_map_cmp_none; switch (field_size) { case 8: if (field_is_signed) fn = tracing_map_cmp_s64; else fn = tracing_map_cmp_u64; break; case 4: if (field_is_signed) fn = tracing_map_cmp_s32; else fn = tracing_map_cmp_u32; break; case 2: if (field_is_signed) fn = tracing_map_cmp_s16; else fn = tracing_map_cmp_u16; break; case 1: if (field_is_signed) fn = tracing_map_cmp_s8; else fn = tracing_map_cmp_u8; break; } return fn; } static int tracing_map_add_field(struct tracing_map *map, tracing_map_cmp_fn_t cmp_fn) { int ret = -EINVAL; if (map->n_fields < TRACING_MAP_FIELDS_MAX) { ret = map->n_fields; map->fields[map->n_fields++].cmp_fn = cmp_fn; } return ret; } /** * 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) { return tracing_map_add_field(map, tracing_map_cmp_atomic64); } /** * 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 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) { int idx = tracing_map_add_field(map, cmp_fn); if (idx < 0) return idx; map->fields[idx].offset = offset; map->key_idx[map->n_keys++] = idx; return idx; } void tracing_map_array_clear(struct tracing_map_array *a) { unsigned int i; if (!a->pages) return; for (i = 0; i < a->n_pages; i++) memset(a->pages[i], 0, PAGE_SIZE); } void tracing_map_array_free(struct tracing_map_array *a) { unsigned int i; if (!a) return; if (!a->pages) goto free; for (i = 0; i < a->n_pages; i++) { if (!a->pages[i]) break; free_page((unsigned long)a->pages[i]); } kfree(a->pages); free: kfree(a); } struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts, unsigned int entry_size) { struct tracing_map_array *a; unsigned int i; a = kzalloc(sizeof(*a), GFP_KERNEL); if (!a) return NULL; a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1); a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift); a->n_pages = n_elts / a->entries_per_page; if (!a->n_pages) a->n_pages = 1; a->entry_shift = fls(a->entries_per_page) - 1; a->entry_mask = (1 << a->entry_shift) - 1; a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL); if (!a->pages) goto free; for (i = 0; i < a->n_pages; i++) { a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL); if (!a->pages[i]) goto free; } out: return a; free: tracing_map_array_free(a); a = NULL; goto out; } static void tracing_map_elt_clear(struct tracing_map_elt *elt) { unsigned i; for (i = 0; i < elt->map->n_fields; i++) if (elt->fields[i].cmp_fn == tracing_map_cmp_atomic64) atomic64_set(&elt->fields[i].sum, 0); if (elt->map->ops && elt->map->ops->elt_clear) elt->map->ops->elt_clear(elt); } static void tracing_map_elt_init_fields(struct tracing_map_elt *elt) { unsigned int i; tracing_map_elt_clear(elt); for (i = 0; i < elt->map->n_fields; i++) { elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn; if (elt->fields[i].cmp_fn != tracing_map_cmp_atomic64) elt->fields[i].offset = elt->map->fields[i].offset; } } static void tracing_map_elt_free(struct tracing_map_elt *elt) { if (!elt) return; if (elt->map->ops && elt->map->ops->elt_free) elt->map->ops->elt_free(elt); kfree(elt->fields); kfree(elt->key); kfree(elt); } static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map) { struct tracing_map_elt *elt; int err = 0; elt = kzalloc(sizeof(*elt), GFP_KERNEL); if (!elt) return ERR_PTR(-ENOMEM); elt->map = map; elt->key = kzalloc(map->key_size, GFP_KERNEL); if (!elt->key) { err = -ENOMEM; goto free; } elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL); if (!elt->fields) { err = -ENOMEM; goto free; } tracing_map_elt_init_fields(elt); if (map->ops && map->ops->elt_alloc) { err = map->ops->elt_alloc(elt); if (err) goto free; } return elt; free: tracing_map_elt_free(elt); return ERR_PTR(err); } static struct tracing_map_elt *get_free_elt(struct tracing_map *map) { struct tracing_map_elt *elt = NULL; int idx; idx = atomic_inc_return(&map->next_elt); if (idx < map->max_elts) { elt = *(TRACING_MAP_ELT(map->elts, idx)); if (map->ops && map->ops->elt_init) map->ops->elt_init(elt); } return elt; } static void tracing_map_free_elts(struct tracing_map *map) { unsigned int i; if (!map->elts) return; for (i = 0; i < map->max_elts; i++) { tracing_map_elt_free(*(TRACING_MAP_ELT(map->elts, i))); *(TRACING_MAP_ELT(map->elts, i)) = NULL; } tracing_map_array_free(map->elts); map->elts = NULL; } static int tracing_map_alloc_elts(struct tracing_map *map) { unsigned int i; map->elts = tracing_map_array_alloc(map->max_elts, sizeof(struct tracing_map_elt *)); if (!map->elts) return -ENOMEM; for (i = 0; i < map->max_elts; i++) { *(TRACING_MAP_ELT(map->elts, i)) = tracing_map_elt_alloc(map); if (IS_ERR(*(TRACING_MAP_ELT(map->elts, i)))) { *(TRACING_MAP_ELT(map->elts, i)) = NULL; tracing_map_free_elts(map); return -ENOMEM; } } return 0; } static inline bool keys_match(void *key, void *test_key, unsigned key_size) { bool match = true; if (memcmp(key, test_key, key_size)) match = false; return match; } static inline struct tracing_map_elt * __tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only) { u32 idx, key_hash, test_key; struct tracing_map_entry *entry; key_hash = jhash(key, map->key_size, 0); if (key_hash == 0) key_hash = 1; idx = key_hash >> (32 - (map->map_bits + 1)); while (1) { idx &= (map->map_size - 1); entry = TRACING_MAP_ENTRY(map->map, idx); test_key = entry->key; if (test_key && test_key == key_hash && entry->val && keys_match(key, entry->val->key, map->key_size)) { atomic64_inc(&map->hits); return entry->val; } if (!test_key) { if (lookup_only) break; if (!cmpxchg(&entry->key, 0, key_hash)) { struct tracing_map_elt *elt; elt = get_free_elt(map); if (!elt) { atomic64_inc(&map->drops); entry->key = 0; break; } memcpy(elt->key, key, map->key_size); entry->val = elt; atomic64_inc(&map->hits); return entry->val; } } idx++; } return NULL; } /** * 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 incrememented. 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)