path: root/kernel/trace/tracing_map.c

// SPDX-License-Identifier: GPL-2.0
/*
 * tracing_map - lock-free map for tracing
 *
 * 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 <linux/kmemleak.h>

#include "tracing_map.h"
#include "trace.h"

/*
 * NOTE: For a detailed description of the data structures used by
 * these functions (such as tracing_map_elt) please see the overview
 * of tracing_map data structures at the beginning of tracing_map.h.
 */

/**
 * tracing_map_update_sum - Add a value to a tracing_map_elt's sum field
 * @elt: The tracing_map_elt
 * @i: The index of the given sum associated with the tracing_map_elt
 * @n: The value to add to the sum
 *
 * Add n to sum i associated with the specified tracing_map_elt
 * instance.  The index i is the index returned by the call to
 * tracing_map_add_sum_field() when the tracing map was set up.
 */
void tracing_map_update_sum(struct tracing_map_elt *elt, unsigned int i, u64 n)
{
	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);
}

/**
 * tracing_map_set_var - Assign a tracing_map_elt's variable field
 * @elt: The tracing_map_elt
 * @i: The index of the given variable associated with the tracing_map_elt
 * @n: The value to assign
 *
 * Assign n to variable i associated with the specified tracing_map_elt
 * instance.  The index i is the index returned by the call to
 * tracing_map_add_var() when the tracing map was set up.
 */
void tracing_map_set_var(struct tracing_map_elt *elt, unsigned int i, u64 n)
{
	atomic64_set(&elt->vars[i], n);
	elt->var_set[i] = true;
}

/**
 * tracing_map_var_set - Return whether or not a variable has been set
 * @elt: The tracing_map_elt
 * @i: The index of the given variable associated with the tracing_map_elt
 *
 * Return true if the variable has been set, false otherwise.  The
 * index i is the index returned by the call to tracing_map_add_var()
 * when the tracing map was set up.
 */
bool tracing_map_var_set(struct tracing_map_elt *elt, unsigned int i)
{
	return elt->var_set[i];
}

/**
 * tracing_map_read_var - Return the value of a tracing_map_elt's variable field
 * @elt: The tracing_map_elt
 * @i: The index of the given variable associated with the tracing_map_elt
 *
 * Retrieve the value of the variable i associated with the specified
 * tracing_map_elt instance.  The index i is the index returned by the
 * call to tracing_map_add_var() when the tracing map was set
 * up.
 *
 * Return: The variable value associated with field i for elt.
 */
u64 tracing_map_read_var(struct tracing_map_elt *elt, unsigned int i)
{
	return (u64)atomic64_read(&elt->vars[i]);
}

/**
 * tracing_map_read_var_once - Return and reset a tracing_map_elt's variable field
 * @elt: The tracing_map_elt
 * @i: The index of the given variable associated with the tracing_map_elt
 *
 * Retrieve the value of the variable i associated with the specified
 * tracing_map_elt instance, and reset the variable to the 'not set'
 * state.  The index i is the index returned by the call to
 * tracing_map_add_var() when the tracing map was set up.  The reset
 * essentially makes the variable a read-once variable if it's only
 * accessed using this function.
 *
 * Return: The variable value associated with field i for elt.
 */
u64 tracing_map_read_var_once(struct tracing_map_elt *elt, unsigned int i)
{
	elt->var_set[i] = false;
	return (u64)atomic64_read(&elt->vars[i]);
}

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)(*(u64 *)val_a);					\
	type b = (type)(*(u64 *)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