/*
* tracing_map - lock-free map for tracing
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* Copyright (C) 2015 Tom Zanussi <tom.zanussi@linux.intel.com>
*
* tracing_map implementation inspired by lock-free map algorithms
* originated by Dr. Cliff Click:
*
* http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable
* http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
*/
#include <linux/vmalloc.h>
#include <linux/jhash.h>
#include <linux/slab.h>
#include <linux/sort.h>
#include "tracing_map.h"
#include "trace.h"
/*
* NOTE: For a detailed description of the data structures used by
* these functions (such as tracing_map_elt) please see the overview
* of tracing_map data structures at the beginning of tracing_map.h.
*/
/**
* tracing_map_update_sum - Add a value to a tracing_map_elt's sum field
* @elt: The tracing_map_elt
* @i: The index of the given sum associated with the tracing_map_elt
* @n: The value to add to the sum
*
* Add n to sum i associated with the specified tracing_map_elt
* instance. The index i is the index returned by the call to
* tracing_map_add_sum_field() when the tracing map was set up.
*/
void tracing_map_update_sum(struct tracing_map_elt *elt, unsigned int i, u64 n)
{
atomic64_add(n, &elt->fields[i].sum);
}
/**
* tracing_map_read_sum - Return the value of a tracing_map_elt's sum field
* @elt: The tracing_map_elt
* @i: The index of the given sum associated with the tracing_map_elt
*
* Retrieve the value of the sum i associated with the specified
* tracing_map_elt instance. The index i is the index returned by the
* call to tracing_map_add_sum_field() when the tracing map was set
* up.
*
* Return: The sum associated with field i for elt.
*/
u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i)
{
return (u64)atomic64_read(&elt->fields[i].sum);
}
int tracing_map_cmp_string(void *val_a, void *val_b)
{
char *a = val_a;
char *b = val_b;
return strcmp(a, b);
}
int tracing_map_cmp_none(void *val_a, void *val_b)
{
return 0;
}
static int tracing_map_cmp_atomic64(void *val_a, void *val_b)
{
u64 a = atomic64_read((atomic64_t *)val_a);
u64 b = atomic64_read((atomic64_t *)val_b);
return (a > b) ? 1 : ((a < b) ? -1 : 0);
}
#define DEFINE_TRACING_MAP_CMP_FN(type) \
static int tracing_map_cmp_##type(void *val_a, void *val_b) \
{ \
type a = *(type *)val_a; \
type b = *(type *)val_b; \
\
return (a > b) ? 1 : ((a < b) ? -1 : 0); \
}
DEFINE_TRACING_MAP_CMP_FN(s64);
DEFINE_TRACING_MAP_CMP_FN(u64);
DEFINE_TRACING_MAP_CMP_FN(s32);
DEFINE_TRACING_MAP_CMP_FN(u32);
DEFINE_TRACING_MAP_CMP_FN(s16);
DEFINE_TRACING_MAP_CMP_FN(u16);
DEFINE_TRACING_MAP_CMP_FN(s8);
DEFINE_TRACING_MAP_CMP_FN(u8);
tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size,
int field_is_signed)
{
tracing_map_cmp_fn_t fn = tracing_map_cmp_none;
switch (field_size) {
case 8:
if (field_is_signed)
fn = tracing_map_cmp_s64;
else
fn = tracing_map_cmp_u64;
break;
case 4:
if (field_is_signed)
fn = tracing_map_cmp_s32;
else
fn = tracing_map_cmp_u32;
break;
case 2:
if (field_is_signed)
fn = tracing_map_cmp_s16;
else
fn = tracing_map_cmp_u16;
break;
case 1:
if (field_is_signed)
fn = tracing_map_cmp_s8;
else
fn = tracing_map_cmp_u8;
break;
}
return fn;
}
static int tracing_map_add_field(struct tracing_map *map,
tracing_map_cmp_fn_t cmp_fn)
{
int ret = -EINVAL;
if (map->n_fields < TRACING_MAP_FIELDS_MAX) {
ret = map->n_fields;
map->fields[map->n_fields++].cmp_fn = cmp_fn;
}
return ret;
}
/**
* tracing_map_add_sum_field - Add a field describing a tracing_map sum
* @map: The tracing_map
*
* Add a sum field to the key and return the index identifying it in
* the map and associated tracing_map_elts. This is the index used
* for instance to update a sum for a particular tracing_map_elt using
* tracing_map_update_sum() or reading it via tracing_map_read_sum().
*
* Return: The index identifying the field in the map and associated
* tracing_map_elts, or -EINVAL on error.
*/
int tracing_map_add_sum_field(struct tracing_map *map)
{
return tracing_map_add_field(map, tracing_map_cmp_atomic64);
}
/**
* tracing_map_add_key_field - Add a field describing a tracing_map key
* @map: The tracing_map
* @offset: The offset within the key
* @cmp_fn: The comparison function that will be used to sort on the key
*
* Let the map know there is a key and that if it's used as a sort key
* to use cmp_fn.
*
* A key can be a subset of a compound key; for that purpose, the
* offset param is used to describe where within the the compound key
* the key referenced by this key field resides.
*
* Return: The index identifying the field in the map and associated
* tracing_map_elts, or -EINVAL on error.
*/
int tracing_map_add_key_field(struct tracing_map *map,
unsigned int offset,
tracing_map_cmp_fn_t cmp_fn)
{
int idx