^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * tracing_map - lock-free map for tracing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (C) 2015 Tom Zanussi <tom.zanussi@linux.intel.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * tracing_map implementation inspired by lock-free map algorithms
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * originated by Dr. Cliff Click:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #include <linux/vmalloc.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <linux/jhash.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include <linux/sort.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include <linux/kmemleak.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) #include "tracing_map.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #include "trace.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * NOTE: For a detailed description of the data structures used by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * these functions (such as tracing_map_elt) please see the overview
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * of tracing_map data structures at the beginning of tracing_map.h.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * tracing_map_update_sum - Add a value to a tracing_map_elt's sum field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * @elt: The tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * @i: The index of the given sum associated with the tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * @n: The value to add to the sum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * Add n to sum i associated with the specified tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * instance. The index i is the index returned by the call to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * tracing_map_add_sum_field() when the tracing map was set up.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) void tracing_map_update_sum(struct tracing_map_elt *elt, unsigned int i, u64 n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) atomic64_add(n, &elt->fields[i].sum);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) * tracing_map_read_sum - Return the value of a tracing_map_elt's sum field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * @elt: The tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * @i: The index of the given sum associated with the tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * Retrieve the value of the sum i associated with the specified
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * tracing_map_elt instance. The index i is the index returned by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * call to tracing_map_add_sum_field() when the tracing map was set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * up.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * Return: The sum associated with field i for elt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) return (u64)atomic64_read(&elt->fields[i].sum);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * tracing_map_set_var - Assign a tracing_map_elt's variable field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * @elt: The tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * @i: The index of the given variable associated with the tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * @n: The value to assign
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * Assign n to variable i associated with the specified tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * instance. The index i is the index returned by the call to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * tracing_map_add_var() when the tracing map was set up.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) void tracing_map_set_var(struct tracing_map_elt *elt, unsigned int i, u64 n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) atomic64_set(&elt->vars[i], n);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) elt->var_set[i] = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) * tracing_map_var_set - Return whether or not a variable has been set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) * @elt: The tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) * @i: The index of the given variable associated with the tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) * Return true if the variable has been set, false otherwise. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * index i is the index returned by the call to tracing_map_add_var()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * when the tracing map was set up.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) bool tracing_map_var_set(struct tracing_map_elt *elt, unsigned int i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) return elt->var_set[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * tracing_map_read_var - Return the value of a tracing_map_elt's variable field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * @elt: The tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * @i: The index of the given variable associated with the tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * Retrieve the value of the variable i associated with the specified
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) * tracing_map_elt instance. The index i is the index returned by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * call to tracing_map_add_var() when the tracing map was set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * up.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * Return: The variable value associated with field i for elt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) u64 tracing_map_read_var(struct tracing_map_elt *elt, unsigned int i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) return (u64)atomic64_read(&elt->vars[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) * tracing_map_read_var_once - Return and reset a tracing_map_elt's variable field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) * @elt: The tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) * @i: The index of the given variable associated with the tracing_map_elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) * Retrieve the value of the variable i associated with the specified
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) * tracing_map_elt instance, and reset the variable to the 'not set'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) * state. The index i is the index returned by the call to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) * tracing_map_add_var() when the tracing map was set up. The reset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) * essentially makes the variable a read-once variable if it's only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) * accessed using this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) * Return: The variable value associated with field i for elt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) u64 tracing_map_read_var_once(struct tracing_map_elt *elt, unsigned int i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) elt->var_set[i] = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) return (u64)atomic64_read(&elt->vars[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) int tracing_map_cmp_string(void *val_a, void *val_b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) char *a = val_a;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) char *b = val_b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) return strcmp(a, b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) int tracing_map_cmp_none(void *val_a, void *val_b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) static int tracing_map_cmp_atomic64(void *val_a, void *val_b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) u64 a = atomic64_read((atomic64_t *)val_a);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) u64 b = atomic64_read((atomic64_t *)val_b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) return (a > b) ? 1 : ((a < b) ? -1 : 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) #define DEFINE_TRACING_MAP_CMP_FN(type) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) static int tracing_map_cmp_##type(void *val_a, void *val_b) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) type a = (type)(*(u64 *)val_a); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) type b = (type)(*(u64 *)val_b); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) return (a > b) ? 1 : ((a < b) ? -1 : 0); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) DEFINE_TRACING_MAP_CMP_FN(s64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) DEFINE_TRACING_MAP_CMP_FN(u64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) DEFINE_TRACING_MAP_CMP_FN(s32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) DEFINE_TRACING_MAP_CMP_FN(u32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) DEFINE_TRACING_MAP_CMP_FN(s16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) DEFINE_TRACING_MAP_CMP_FN(u16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) DEFINE_TRACING_MAP_CMP_FN(s8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) DEFINE_TRACING_MAP_CMP_FN(u8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) int field_is_signed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) tracing_map_cmp_fn_t fn = tracing_map_cmp_none;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) switch (field_size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) case 8:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) if (field_is_signed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) fn = tracing_map_cmp_s64;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) fn = tracing_map_cmp_u64;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) case 4:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) if (field_is_signed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) fn = tracing_map_cmp_s32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) fn = tracing_map_cmp_u32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) case 2:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) if (field_is_signed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) fn = tracing_map_cmp_s16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) fn = tracing_map_cmp_u16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) case 1:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) if (field_is_signed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) fn = tracing_map_cmp_s8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) fn = tracing_map_cmp_u8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) return fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) static int tracing_map_add_field(struct tracing_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) tracing_map_cmp_fn_t cmp_fn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) int ret = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) if (map->n_fields < TRACING_MAP_FIELDS_MAX) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) ret = map->n_fields;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) map->fields[map->n_fields++].cmp_fn = cmp_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) * tracing_map_add_sum_field - Add a field describing a tracing_map sum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) * @map: The tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) * Add a sum field to the key and return the index identifying it in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) * the map and associated tracing_map_elts. This is the index used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) * for instance to update a sum for a particular tracing_map_elt using
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) * tracing_map_update_sum() or reading it via tracing_map_read_sum().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) * Return: The index identifying the field in the map and associated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) * tracing_map_elts, or -EINVAL on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) int tracing_map_add_sum_field(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) return tracing_map_add_field(map, tracing_map_cmp_atomic64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) * tracing_map_add_var - Add a field describing a tracing_map var
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) * @map: The tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) * Add a var to the map and return the index identifying it in the map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) * and associated tracing_map_elts. This is the index used for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) * instance to update a var for a particular tracing_map_elt using
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) * tracing_map_update_var() or reading it via tracing_map_read_var().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) * Return: The index identifying the var in the map and associated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) * tracing_map_elts, or -EINVAL on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) int tracing_map_add_var(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) int ret = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) if (map->n_vars < TRACING_MAP_VARS_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) ret = map->n_vars++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) * tracing_map_add_key_field - Add a field describing a tracing_map key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) * @map: The tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) * @offset: The offset within the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) * @cmp_fn: The comparison function that will be used to sort on the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) * Let the map know there is a key and that if it's used as a sort key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) * to use cmp_fn.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) * A key can be a subset of a compound key; for that purpose, the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) * offset param is used to describe where within the compound key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) * the key referenced by this key field resides.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) * Return: The index identifying the field in the map and associated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) * tracing_map_elts, or -EINVAL on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) int tracing_map_add_key_field(struct tracing_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) unsigned int offset,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) tracing_map_cmp_fn_t cmp_fn)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) int idx = tracing_map_add_field(map, cmp_fn);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) if (idx < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) return idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) map->fields[idx].offset = offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) map->key_idx[map->n_keys++] = idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) return idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) static void tracing_map_array_clear(struct tracing_map_array *a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) if (!a->pages)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) for (i = 0; i < a->n_pages; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) memset(a->pages[i], 0, PAGE_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) static void tracing_map_array_free(struct tracing_map_array *a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) if (!a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) if (!a->pages)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) for (i = 0; i < a->n_pages; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) if (!a->pages[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) kmemleak_free(a->pages[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) free_page((unsigned long)a->pages[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) kfree(a->pages);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) free:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) kfree(a);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) static struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) unsigned int entry_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) struct tracing_map_array *a;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) a = kzalloc(sizeof(*a), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) if (!a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) a->n_pages = n_elts / a->entries_per_page;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) if (!a->n_pages)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) a->n_pages = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) a->entry_shift = fls(a->entries_per_page) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) a->entry_mask = (1 << a->entry_shift) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) if (!a->pages)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) for (i = 0; i < a->n_pages; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) if (!a->pages[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) kmemleak_alloc(a->pages[i], PAGE_SIZE, 1, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) return a;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) free:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) tracing_map_array_free(a);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) a = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) static void tracing_map_elt_clear(struct tracing_map_elt *elt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) unsigned i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) for (i = 0; i < elt->map->n_fields; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) if (elt->fields[i].cmp_fn == tracing_map_cmp_atomic64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) atomic64_set(&elt->fields[i].sum, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) for (i = 0; i < elt->map->n_vars; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) atomic64_set(&elt->vars[i], 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) elt->var_set[i] = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) if (elt->map->ops && elt->map->ops->elt_clear)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) elt->map->ops->elt_clear(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) static void tracing_map_elt_init_fields(struct tracing_map_elt *elt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) tracing_map_elt_clear(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) for (i = 0; i < elt->map->n_fields; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) if (elt->fields[i].cmp_fn != tracing_map_cmp_atomic64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) elt->fields[i].offset = elt->map->fields[i].offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) static void tracing_map_elt_free(struct tracing_map_elt *elt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) if (!elt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) if (elt->map->ops && elt->map->ops->elt_free)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) elt->map->ops->elt_free(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) kfree(elt->fields);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) kfree(elt->vars);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) kfree(elt->var_set);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) kfree(elt->key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) kfree(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) struct tracing_map_elt *elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) int err = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) elt = kzalloc(sizeof(*elt), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) if (!elt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) return ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) elt->map = map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) elt->key = kzalloc(map->key_size, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) if (!elt->key) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) err = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) if (!elt->fields) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) err = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) elt->vars = kcalloc(map->n_vars, sizeof(*elt->vars), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) if (!elt->vars) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) err = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) elt->var_set = kcalloc(map->n_vars, sizeof(*elt->var_set), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) if (!elt->var_set) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) err = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) tracing_map_elt_init_fields(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) if (map->ops && map->ops->elt_alloc) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) err = map->ops->elt_alloc(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) return elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) free:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) tracing_map_elt_free(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) return ERR_PTR(err);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) static struct tracing_map_elt *get_free_elt(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) struct tracing_map_elt *elt = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) int idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) idx = atomic_inc_return(&map->next_elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) if (idx < map->max_elts) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) elt = *(TRACING_MAP_ELT(map->elts, idx));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) if (map->ops && map->ops->elt_init)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) map->ops->elt_init(elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) return elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) static void tracing_map_free_elts(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) if (!map->elts)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) for (i = 0; i < map->max_elts; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) tracing_map_elt_free(*(TRACING_MAP_ELT(map->elts, i)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) *(TRACING_MAP_ELT(map->elts, i)) = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) tracing_map_array_free(map->elts);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) map->elts = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) static int tracing_map_alloc_elts(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) map->elts = tracing_map_array_alloc(map->max_elts,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) sizeof(struct tracing_map_elt *));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) if (!map->elts)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) for (i = 0; i < map->max_elts; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) *(TRACING_MAP_ELT(map->elts, i)) = tracing_map_elt_alloc(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) if (IS_ERR(*(TRACING_MAP_ELT(map->elts, i)))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) *(TRACING_MAP_ELT(map->elts, i)) = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) tracing_map_free_elts(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) static inline bool keys_match(void *key, void *test_key, unsigned key_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) bool match = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) if (memcmp(key, test_key, key_size))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) match = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) return match;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) static inline struct tracing_map_elt *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) __tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) u32 idx, key_hash, test_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) int dup_try = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) struct tracing_map_entry *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) struct tracing_map_elt *val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) key_hash = jhash(key, map->key_size, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) if (key_hash == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) key_hash = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) idx = key_hash >> (32 - (map->map_bits + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) idx &= (map->map_size - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) entry = TRACING_MAP_ENTRY(map->map, idx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) test_key = entry->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) if (test_key && test_key == key_hash) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) val = READ_ONCE(entry->val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) if (val &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) keys_match(key, val->key, map->key_size)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) if (!lookup_only)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) atomic64_inc(&map->hits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) return val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) } else if (unlikely(!val)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) * The key is present. But, val (pointer to elt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) * struct) is still NULL. which means some other
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) * thread is in the process of inserting an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) * element.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) * On top of that, it's key_hash is same as the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) * one being inserted right now. So, it's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) * possible that the element has the same
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) * key as well.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) dup_try++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) if (dup_try > map->map_size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) atomic64_inc(&map->drops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) if (!test_key) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) if (lookup_only)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) if (!cmpxchg(&entry->key, 0, key_hash)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) struct tracing_map_elt *elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) elt = get_free_elt(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) if (!elt) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) atomic64_inc(&map->drops);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) entry->key = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) memcpy(elt->key, key, map->key_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) entry->val = elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) atomic64_inc(&map->hits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) return entry->val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) * cmpxchg() failed. Loop around once
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) * more to check what key was inserted.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) dup_try++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) idx++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) * tracing_map_insert - Insert key and/or retrieve val from a tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) * @map: The tracing_map to insert into
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) * @key: The key to insert
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) * Inserts a key into a tracing_map and creates and returns a new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) * tracing_map_elt for it, or if the key has already been inserted by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) * a previous call, returns the tracing_map_elt already associated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) * with it. When the map was created, the number of elements to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) * allocated for the map was specified (internally maintained as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) * 'max_elts' in struct tracing_map), and that number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) * tracing_map_elts was created by tracing_map_init(). This is the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) * pre-allocated pool of tracing_map_elts that tracing_map_insert()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) * will allocate from when adding new keys. Once that pool is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) * exhausted, tracing_map_insert() is useless and will return NULL to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) * signal that state. There are two user-visible tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) * variables, 'hits' and 'drops', which are updated by this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) * Every time an element is either successfully inserted or retrieved,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) * the 'hits' value is incrememented. Every time an element insertion
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) * fails, the 'drops' value is incremented.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) * This is a lock-free tracing map insertion function implementing a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) * modified form of Cliff Click's basic insertion algorithm. It
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) * requires the table size be a power of two. To prevent any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) * possibility of an infinite loop we always make the internal table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) * size double the size of the requested table size (max_elts * 2).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) * Likewise, we never reuse a slot or resize or delete elements - when
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) * we've reached max_elts entries, we simply return NULL once we've
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) * run out of entries. Readers can at any point in time traverse the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) * tracing map and safely access the key/val pairs.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) * Return: the tracing_map_elt pointer val associated with the key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) * If this was a newly inserted key, the val will be a newly allocated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) * and associated tracing_map_elt pointer val. If the key wasn't
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) * found and the pool of tracing_map_elts has been exhausted, NULL is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) * returned and no further insertions will succeed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) return __tracing_map_insert(map, key, false);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) * tracing_map_lookup - Retrieve val from a tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) * @map: The tracing_map to perform the lookup on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) * @key: The key to look up
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) * Looks up key in tracing_map and if found returns the matching
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) * tracing_map_elt. This is a lock-free lookup; see
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) * tracing_map_insert() for details on tracing_map and how it works.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) * Every time an element is retrieved, the 'hits' value is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) * incrememented. There is one user-visible tracing_map variable,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) * 'hits', which is updated by this function. Every time an element
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) * is successfully retrieved, the 'hits' value is incrememented. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) * 'drops' value is never updated by this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) * Return: the tracing_map_elt pointer val associated with the key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) * If the key wasn't found, NULL is returned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) struct tracing_map_elt *tracing_map_lookup(struct tracing_map *map, void *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) return __tracing_map_insert(map, key, true);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) * tracing_map_destroy - Destroy a tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) * @map: The tracing_map to destroy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) * Frees a tracing_map along with its associated array of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) * tracing_map_elts.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) * Callers should make sure there are no readers or writers actively
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) * reading or inserting into the map before calling this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) void tracing_map_destroy(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) if (!map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) tracing_map_free_elts(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) tracing_map_array_free(map->map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) kfree(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) * tracing_map_clear - Clear a tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) * @map: The tracing_map to clear
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) * Resets the tracing map to a cleared or initial state. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) * tracing_map_elts are all cleared, and the array of struct
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) * tracing_map_entry is reset to an initialized state.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) * Callers should make sure there are no writers actively inserting
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) * into the map before calling this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) void tracing_map_clear(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) atomic_set(&map->next_elt, -1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) atomic64_set(&map->hits, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) atomic64_set(&map->drops, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) tracing_map_array_clear(map->map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) for (i = 0; i < map->max_elts; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) tracing_map_elt_clear(*(TRACING_MAP_ELT(map->elts, i)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) static void set_sort_key(struct tracing_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) struct tracing_map_sort_key *sort_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) map->sort_key = *sort_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) * tracing_map_create - Create a lock-free map and element pool
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) * @map_bits: The size of the map (2 ** map_bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) * @key_size: The size of the key for the map in bytes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) * @ops: Optional client-defined tracing_map_ops instance
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) * @private_data: Client data associated with the map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) * Creates and sets up a map to contain 2 ** map_bits number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) * elements (internally maintained as 'max_elts' in struct
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) * tracing_map). Before using, map fields should be added to the map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) * with tracing_map_add_sum_field() and tracing_map_add_key_field().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) * tracing_map_init() should then be called to allocate the array of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) * tracing_map_elts, in order to avoid allocating anything in the map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) * insertion path. The user-specified map size reflects the maximum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) * number of elements that can be contained in the table requested by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) * the user - internally we double that in order to keep the table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) * sparse and keep collisions manageable.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) * A tracing_map is a special-purpose map designed to aggregate or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) * 'sum' one or more values associated with a specific object of type
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) * tracing_map_elt, which is attached by the map to a given key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) * tracing_map_create() sets up the map itself, and provides
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) * operations for inserting tracing_map_elts, but doesn't allocate the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) * tracing_map_elts themselves, or provide a means for describing the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) * keys or sums associated with the tracing_map_elts. All
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) * tracing_map_elts for a given map have the same set of sums and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) * keys, which are defined by the client using the functions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) * tracing_map_add_key_field() and tracing_map_add_sum_field(). Once
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) * the fields are defined, the pool of elements allocated for the map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) * can be created, which occurs when the client code calls
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) * tracing_map_init().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) * When tracing_map_init() returns, tracing_map_elt elements can be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) * inserted into the map using tracing_map_insert(). When called,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) * tracing_map_insert() grabs a free tracing_map_elt from the pool, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) * finds an existing match in the map and in either case returns it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) * The client can then use tracing_map_update_sum() and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) * tracing_map_read_sum() to update or read a given sum field for the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) * tracing_map_elt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) * The client can at any point retrieve and traverse the current set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) * of inserted tracing_map_elts in a tracing_map, via
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) * tracing_map_sort_entries(). Sorting can be done on any field,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) * including keys.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) * See tracing_map.h for a description of tracing_map_ops.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) * Return: the tracing_map pointer if successful, ERR_PTR if not.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) struct tracing_map *tracing_map_create(unsigned int map_bits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) unsigned int key_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) const struct tracing_map_ops *ops,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) void *private_data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) struct tracing_map *map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) if (map_bits < TRACING_MAP_BITS_MIN ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) map_bits > TRACING_MAP_BITS_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) return ERR_PTR(-EINVAL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) map = kzalloc(sizeof(*map), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) if (!map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) return ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) map->map_bits = map_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) map->max_elts = (1 << map_bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) atomic_set(&map->next_elt, -1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) map->map_size = (1 << (map_bits + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) map->ops = ops;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) map->private_data = private_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) map->map = tracing_map_array_alloc(map->map_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) sizeof(struct tracing_map_entry));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) if (!map->map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) map->key_size = key_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) for (i = 0; i < TRACING_MAP_KEYS_MAX; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) map->key_idx[i] = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) return map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) free:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) tracing_map_destroy(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) map = ERR_PTR(-ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) * tracing_map_init - Allocate and clear a map's tracing_map_elts
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) * @map: The tracing_map to initialize
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) * Allocates a clears a pool of tracing_map_elts equal to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) * user-specified size of 2 ** map_bits (internally maintained as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) * 'max_elts' in struct tracing_map). Before using, the map fields
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) * should be added to the map with tracing_map_add_sum_field() and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) * tracing_map_add_key_field(). tracing_map_init() should then be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) * called to allocate the array of tracing_map_elts, in order to avoid
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) * allocating anything in the map insertion path. The user-specified
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) * map size reflects the max number of elements requested by the user
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) * - internally we double that in order to keep the table sparse and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) * keep collisions manageable.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) * See tracing_map.h for a description of tracing_map_ops.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) * Return: the tracing_map pointer if successful, ERR_PTR if not.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) int tracing_map_init(struct tracing_map *map)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) int err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) if (map->n_fields < 2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) return -EINVAL; /* need at least 1 key and 1 val */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) err = tracing_map_alloc_elts(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) tracing_map_clear(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) static int cmp_entries_dup(const void *A, const void *B)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842) const struct tracing_map_sort_entry *a, *b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845) a = *(const struct tracing_map_sort_entry **)A;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) b = *(const struct tracing_map_sort_entry **)B;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) if (memcmp(a->key, b->key, a->elt->map->key_size))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) ret = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) static int cmp_entries_sum(const void *A, const void *B)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) const struct tracing_map_elt *elt_a, *elt_b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857) const struct tracing_map_sort_entry *a, *b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) struct tracing_map_sort_key *sort_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) struct tracing_map_field *field;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) tracing_map_cmp_fn_t cmp_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) void *val_a, *val_b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) a = *(const struct tracing_map_sort_entry **)A;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) b = *(const struct tracing_map_sort_entry **)B;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) elt_a = a->elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) elt_b = b->elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) sort_key = &elt_a->map->sort_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872) field = &elt_a->fields[sort_key->field_idx];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) cmp_fn = field->cmp_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) val_a = &elt_a->fields[sort_key->field_idx].sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876) val_b = &elt_b->fields[sort_key->field_idx].sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) ret = cmp_fn(val_a, val_b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879) if (sort_key->descending)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880) ret = -ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885) static int cmp_entries_key(const void *A, const void *B)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887) const struct tracing_map_elt *elt_a, *elt_b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) const struct tracing_map_sort_entry *a, *b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) struct tracing_map_sort_key *sort_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) struct tracing_map_field *field;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891) tracing_map_cmp_fn_t cmp_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892) void *val_a, *val_b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895) a = *(const struct tracing_map_sort_entry **)A;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896) b = *(const struct tracing_map_sort_entry **)B;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) elt_a = a->elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) elt_b = b->elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901) sort_key = &elt_a->map->sort_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903) field = &elt_a->fields[sort_key->field_idx];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905) cmp_fn = field->cmp_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) val_a = elt_a->key + field->offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908) val_b = elt_b->key + field->offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) ret = cmp_fn(val_a, val_b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) if (sort_key->descending)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) ret = -ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) static void destroy_sort_entry(struct tracing_map_sort_entry *entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) if (!entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922) if (entry->elt_copied)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923) tracing_map_elt_free(entry->elt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) kfree(entry);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929) * tracing_map_destroy_sort_entries - Destroy an array of sort entries
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) * @entries: The entries to destroy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931) * @n_entries: The number of entries in the array
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) * Destroy the elements returned by a tracing_map_sort_entries() call.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935) void tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) unsigned int n_entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) for (i = 0; i < n_entries; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941) destroy_sort_entry(entries[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943) vfree(entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946) static struct tracing_map_sort_entry *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947) create_sort_entry(void *key, struct tracing_map_elt *elt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) struct tracing_map_sort_entry *sort_entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951) sort_entry = kzalloc(sizeof(*sort_entry), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) if (!sort_entry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) sort_entry->key = key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956) sort_entry->elt = elt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) return sort_entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) static void detect_dups(struct tracing_map_sort_entry **sort_entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) int n_entries, unsigned int key_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) unsigned int dups = 0, total_dups = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) void *key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) if (n_entries < 2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) sort(sort_entries, n_entries, sizeof(struct tracing_map_sort_entry *),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) (int (*)(const void *, const void *))cmp_entries_dup, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974) key = sort_entries[0]->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) for (i = 1; i < n_entries; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976) if (!memcmp(sort_entries[i]->key, key, key_size)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977) dups++; total_dups++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) key = sort_entries[i]->key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) dups = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) WARN_ONCE(total_dups > 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) "Duplicates detected: %d\n", total_dups);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988) static bool is_key(struct tracing_map *map, unsigned int field_idx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992) for (i = 0; i < map->n_keys; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993) if (map->key_idx[i] == field_idx)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998) static void sort_secondary(struct tracing_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) const struct tracing_map_sort_entry **entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) unsigned int n_entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001) struct tracing_map_sort_key *primary_key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002) struct tracing_map_sort_key *secondary_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004) int (*primary_fn)(const void *, const void *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005) int (*secondary_fn)(const void *, const void *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006) unsigned i, start = 0, n_sub = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008) if (is_key(map, primary_key->field_idx))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) primary_fn = cmp_entries_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) primary_fn = cmp_entries_sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013) if (is_key(map, secondary_key->field_idx))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014) secondary_fn = cmp_entries_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1015) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1016) secondary_fn = cmp_entries_sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1017)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1018) for (i = 0; i < n_entries - 1; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1019) const struct tracing_map_sort_entry **a = &entries[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1020) const struct tracing_map_sort_entry **b = &entries[i + 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1021)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1022) if (primary_fn(a, b) == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1023) n_sub++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1024) if (i < n_entries - 2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1025) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1026) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1027)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1028) if (n_sub < 2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1029) start = i + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1030) n_sub = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1031) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1032) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1033)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1034) set_sort_key(map, secondary_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1035) sort(&entries[start], n_sub,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1036) sizeof(struct tracing_map_sort_entry *),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1037) (int (*)(const void *, const void *))secondary_fn, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1038) set_sort_key(map, primary_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1039)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1040) start = i + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1041) n_sub = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1042) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1043) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1044)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1045) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1046) * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1047) * @map: The tracing_map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1048) * @sort_key: The sort key to use for sorting
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1049) * @sort_entries: outval: pointer to allocated and sorted array of entries
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1050) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1051) * tracing_map_sort_entries() sorts the current set of entries in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1052) * map and returns the list of tracing_map_sort_entries containing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1053) * them to the client in the sort_entries param. The client can
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1054) * access the struct tracing_map_elt element of interest directly as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1055) * the 'elt' field of a returned struct tracing_map_sort_entry object.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1056) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1057) * The sort_key has only two fields: idx and descending. 'idx' refers
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1058) * to the index of the field added via tracing_map_add_sum_field() or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1059) * tracing_map_add_key_field() when the tracing_map was initialized.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1060) * 'descending' is a flag that if set reverses the sort order, which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1061) * by default is ascending.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1062) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1063) * The client should not hold on to the returned array but should use
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1064) * it and call tracing_map_destroy_sort_entries() when done.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1065) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1066) * Return: the number of sort_entries in the struct tracing_map_sort_entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1067) * array, negative on error
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1068) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1069) int tracing_map_sort_entries(struct tracing_map *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1070) struct tracing_map_sort_key *sort_keys,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1071) unsigned int n_sort_keys,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1072) struct tracing_map_sort_entry ***sort_entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1073) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1074) int (*cmp_entries_fn)(const void *, const void *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1075) struct tracing_map_sort_entry *sort_entry, **entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1076) int i, n_entries, ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1077)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1078) entries = vmalloc(array_size(sizeof(sort_entry), map->max_elts));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1079) if (!entries)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1080) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1081)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1082) for (i = 0, n_entries = 0; i < map->map_size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1083) struct tracing_map_entry *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1084)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1085) entry = TRACING_MAP_ENTRY(map->map, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1086)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1087) if (!entry->key || !entry->val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1088) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1089)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1090) entries[n_entries] = create_sort_entry(entry->val->key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1091) entry->val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1092) if (!entries[n_entries++]) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1093) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1094) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1095) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1096) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1097)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1098) if (n_entries == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1099) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1100) goto free;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1101) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1103) if (n_entries == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1104) *sort_entries = entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1105) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1106) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1107)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1108) detect_dups(entries, n_entries, map->key_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1109)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1110) if (is_key(map, sort_keys[0].field_idx))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1111) cmp_entries_fn = cmp_entries_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1112) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1113) cmp_entries_fn = cmp_entries_sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1114)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1115) set_sort_key(map, &sort_keys[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1117) sort(entries, n_entries, sizeof(struct tracing_map_sort_entry *),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1118) (int (*)(const void *, const void *))cmp_entries_fn, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1120) if (n_sort_keys > 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1121) sort_secondary(map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1122) (const struct tracing_map_sort_entry **)entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1123) n_entries,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1124) &sort_keys[0],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1125) &sort_keys[1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1127) *sort_entries = entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1128)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1129) return n_entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1130) free:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1131) tracing_map_destroy_sort_entries(entries, n_entries);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1132)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1133) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1134) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags
| Donate