/*
* 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);
}
/**
* 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 *)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);