| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Fri, 17 Jul 2015 18:44:40 -0500
From: Tom Zanussi <tom.zanussi@...ux.intel.com>
To: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: rostedt <rostedt@...dmis.org>,
daniel wagner <daniel.wagner@...-carit.de>,
masami hiramatsu pt <masami.hiramatsu.pt@...achi.com>,
namhyung@...nel.org, josh@...htriplett.org,
Andi Kleen <andi@...stfloor.org>, linux-kernel@...r.kernel.org,
Julien Desfossez <jdesfossez@...icios.com>,
Lai Jiangshan <eag0628@...il.com>
Subject: Re: [PATCH v9 07/22] tracing: Add lock-free tracing_map
On Fri, 2015-07-17 at 15:48 +0000, Mathieu Desnoyers wrote:
> ----- On Jul 16, 2015, at 9:35 PM, Tom Zanussi tom.zanussi@...ux.intel.com wrote:
>
> > Hi Mathieu,
> >
> > On Thu, 2015-07-16 at 23:25 +0000, Mathieu Desnoyers wrote:
> >> * Tom Zanussi wrote:
> >> >> Add tracing_map, a special-purpose lock-free map for tracing.
> >> >>
> >> >> tracing_map is designed to aggregate or 'sum' one or more values
> >> >> associated with a specific object of type tracing_map_elt, which
> >> >> is associated by the map to a given key.
> >> >>
> >> >> It provides various hooks allowing per-tracer customization and is
> >> >> separated out into a separate file in order to allow it to be shared
> >> >> between multiple tracers, but isn't meant to be generally used outside
> >> >> of that context.
> >> >>
> >> >> The tracing_map implementation was 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
> >>
> >> Hi Tom,
> >>
> >> First question: what is the rationale for implementing another
> >> hash table from scratch here ? What is missing in the pre-existing
> >> hash table implementations ?
> >>
> >
> > None of the other hash tables allow for lock-free insertion (and I
> > didn't see an easy way to add it).
>
> This is one of the nice things about the Userspace RCU lock-free hash
> table we've done a few years ago: it provides lock-free add, add_unique,
> removal, and replace, as well as RCU wait-free lookups and traversals.
> Resize can be done concurrently by a worker thread. I ported it to the
> Linux kernel for Julien's work on latency tracker. You can find the
> implementation here: https://github.com/jdesfossez/latency_tracker
> (see rculfhash*)
> It is a simplified version that has the "resize" feature removed for
> simplicity sake. The "insert and lookup" feature you need is called
> "add_unique" in our API: it behaves both as a lookup and as an atomic
> insert if the key is not found.
>
Interesting, but it's just as much not upstream as mine is. ;-)
>From the perspective of the hist triggers, it doesn't matter what hash
table implementation it uses as long as whatever it is supports
insertion in any context. In fact the current tracing_map
implementation is already the second completely different implementation
it's plugged into (see v2 of this patchset for the first). If yours is
better and going upstream, I'd be happy to make it the third and forget
about mine.
Tom
> Thanks,
>
> Mathieu
>
> >
> >> Moreover, you might want to handle the case where jhash() returns
> >> 0. AFAIU, there is a race on "insert" in this scenario.
> >>
> >
> > You're right, in that case you'd accidentally overwrite an already
> > claimed slot. Thanks for pointing that out.
> >
> > Tom
> >
> >> Thanks,
> >>
> >> Mathieu
> >>
> >> >>
> >> >> Signed-off-by: Tom Zanussi <tom.zanussi@...ux.intel.com>
> >> >> ---
> >> >> kernel/trace/Makefile | 1 +
> >> >> kernel/trace/tracing_map.c | 935 +++++++++++++++++++++++++++++++++++++++++++++
> >> >> kernel/trace/tracing_map.h | 258 +++++++++++++
> >> >> 3 files changed, 1194 insertions(+)
> >> >> create mode 100644 kernel/trace/tracing_map.c
> >> >> create mode 100644 kernel/trace/tracing_map.h
> >> >>
> >> >> diff --git a/kernel/trace/Makefile b/kernel/trace/Makefile
> >> >> index 9b1044e..3b26cfb 100644
> >> >> --- a/kernel/trace/Makefile
> >> >> +++ b/kernel/trace/Makefile
> >> >> @@ -31,6 +31,7 @@ obj-$(CONFIG_TRACING) += trace_output.o
> >> >> obj-$(CONFIG_TRACING) += trace_seq.o
> >> >> obj-$(CONFIG_TRACING) += trace_stat.o
> >> >> obj-$(CONFIG_TRACING) += trace_printk.o
> >> >> +obj-$(CONFIG_TRACING) += tracing_map.o
> >> >> obj-$(CONFIG_CONTEXT_SWITCH_TRACER) += trace_sched_switch.o
> >> >> obj-$(CONFIG_FUNCTION_TRACER) += trace_functions.o
> >> >> obj-$(CONFIG_IRQSOFF_TRACER) += trace_irqsoff.o
> >> >> diff --git a/kernel/trace/tracing_map.c b/kernel/trace/tracing_map.c
> >> >> new file mode 100644
> >> >> index 0000000..a505025
> >> >> --- /dev/null
> >> >> +++ b/kernel/trace/tracing_map.c
> >> >> @@ -0,0 +1,935 @@
> >> >> +/*
> >> >> + * 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@...ux.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/slab.h>
> >> >> +#include <linux/jhash.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.
> >> >> + */
> >> >> +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.
> >> >> + */
> >> >> +int tracing_map_add_key_field(struct tracing_map *map,
> >> >> + unsigned int offset,
> >> >> + tracing_map_cmp_fn_t cmp_fn)
> >> >> +
> >> >> +{
> >> >> + int idx = tracing_map_add_field(map, cmp_fn);
> >> >> +
> >> >> + if (idx < 0)
> >> >> + return idx;
> >> >> +
> >> >> + map->fields[idx].offset = offset;
> >> >> +
> >> >> + map->key_idx[map->n_keys++] = idx;
> >> >> +
> >> >> + return idx;
> >> >> +}
> >> >> +
> >> >> +static void tracing_map_elt_clear(struct tracing_map_elt *elt)
> >> >> +{
> >> >> + unsigned i;
> >> >> +
> >> >> + for (i = 0; i < elt->map->n_fields; i++)
> >> >> + if (elt->fields[i].cmp_fn == tracing_map_cmp_atomic64)
> >> >> + atomic64_set(&elt->fields[i].sum, 0);
> >> >> +
> >> >> + if (elt->map->ops && elt->map->ops->elt_clear)
> >> >> + elt->map->ops->elt_clear(elt);
> >> >> +}
> >> >> +
> >> >> +static void tracing_map_elt_init_fields(struct tracing_map_elt *elt)
> >> >> +{
> >> >> + unsigned int i;
> >> >> +
> >> >> + tracing_map_elt_clear(elt);
> >> >> +
> >> >> + for (i = 0; i < elt->map->n_fields; i++) {
> >> >> + elt->fields[i].cmp_fn = elt->map->fields[i].cmp_fn;
> >> >> +
> >> >> + if (elt->fields[i].cmp_fn != tracing_map_cmp_atomic64)
> >> >> + elt->fields[i].offset = elt->map->fields[i].offset;
> >> >> + }
> >> >> +}
> >> >> +
> >> >> +static void tracing_map_elt_free(struct tracing_map_elt *elt)
> >> >> +{
> >> >> + if (!elt)
> >> >> + return;
> >> >> +
> >> >> + if (elt->map->ops && elt->map->ops->elt_free)
> >> >> + elt->map->ops->elt_free(elt);
> >> >> + kfree(elt->fields);
> >> >> + kfree(elt->key);
> >> >> + kfree(elt);
> >> >> +}
> >> >> +
> >> >> +static struct tracing_map_elt *tracing_map_elt_alloc(struct tracing_map *map)
> >> >> +{
> >> >> + struct tracing_map_elt *elt;
> >> >> + int err = 0;
> >> >> +
> >> >> + elt = kzalloc(sizeof(*elt), GFP_KERNEL);
> >> >> + if (!elt)
> >> >> + return ERR_PTR(-ENOMEM);
> >> >> +
> >> >> + elt->map = map;
> >> >> +
> >> >> + elt->key = kzalloc(map->key_size, GFP_KERNEL);
> >> >> + if (!elt->key) {
> >> >> + err = -ENOMEM;
> >> >> + goto free;
> >> >> + }
> >> >> +
> >> >> + elt->fields = kcalloc(map->n_fields, sizeof(*elt->fields), GFP_KERNEL);
> >> >> + if (!elt->fields) {
> >> >> + err = -ENOMEM;
> >> >> + goto free;
> >> >> + }
> >> >> +
> >> >> + tracing_map_elt_init_fields(elt);
> >> >> +
> >> >> + if (map->ops && map->ops->elt_alloc) {
> >> >> + err = map->ops->elt_alloc(elt);
> >> >> + if (err)
> >> >> + goto free;
> >> >> + }
> >> >> + return elt;
> >> >> + free:
> >> >> + tracing_map_elt_free(elt);
> >> >> +
> >> >> + return ERR_PTR(err);
> >> >> +}
> >> >> +
> >> >> +static struct tracing_map_elt *get_free_elt(struct tracing_map *map)
> >> >> +{
> >> >> + struct tracing_map_elt *elt = NULL;
> >> >> + int idx;
> >> >> +
> >> >> + idx = atomic_inc_return(&map->next_elt);
> >> >> + if (idx < map->max_elts) {
> >> >> + elt = map->elts[idx];
> >> >> + if (map->ops && map->ops->elt_init)
> >> >> + map->ops->elt_init(elt);
> >> >> + }
> >> >> +
> >> >> + return elt;
> >> >> +}
> >> >> +
> >> >> +static void tracing_map_free_elts(struct tracing_map *map)
> >> >> +{
> >> >> + unsigned int i;
> >> >> +
> >> >> + if (!map->elts)
> >> >> + return;
> >> >> +
> >> >> + for (i = 0; i < map->max_elts; i++)
> >> >> + tracing_map_elt_free(map->elts[i]);
> >> >> +
> >> >> + kfree(map->elts);
> >> >> +}
> >> >> +
> >> >> +static int tracing_map_alloc_elts(struct tracing_map *map)
> >> >> +{
> >> >> + unsigned int i;
> >> >> +
> >> >> + map->elts = kcalloc(map->max_elts, sizeof(struct tracing_map_elt *),
> >> >> + GFP_KERNEL);
> >> >> + if (!map->elts)
> >> >> + return -ENOMEM;
> >> >> +
> >> >> + for (i = 0; i < map->max_elts; i++) {
> >> >> + map->elts[i] = tracing_map_elt_alloc(map);
> >> >> + if (!map->elts[i]) {
> >> >> + tracing_map_free_elts(map);
> >> >> +
> >> >> + return -ENOMEM;
> >> >> + }
> >> >> + }
> >> >> +
> >> >> + return 0;
> >> >> +}
> >> >> +
> >> >> +static inline bool keys_match(void *key, void *test_key, unsigned key_size)
> >> >> +{
> >> >> + bool match = true;
> >> >> +
> >> >> + if (memcmp(key, test_key, key_size))
> >> >> + match = false;
> >> >> +
> >> >> + return match;
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_insert - Insert key and/or retrieve val from a tracing_map
> >> >> + * @map: The tracing_map to insert into
> >> >> + * @key: The key to insert
> >> >> + *
> >> >> + * Inserts a key into a tracing_map and creates and returns a new
> >> >> + * tracing_map_elt for it, or if the key has already been inserted by
> >> >> + * a previous call, returns the tracing_map_elt already associated
> >> >> + * with it. When the map was created, the number of elements to be
> >> >> + * allocated for the map was specified (internally maintained as
> >> >> + * 'max_elts' in struct tracing_map), and that number of
> >> >> + * tracing_map_elts was created by tracing_map_init(). This is the
> >> >> + * pre-allocated pool of tracing_map_elts that tracing_map_insert()
> >> >> + * will allocate from when adding new keys. Once that pool is
> >> >> + * exhausted, tracing_map_insert() is useless and will return NULL to
> >> >> + * signal that state.
> >> >> + *
> >> >> + * This is a lock-free tracing map insertion function implementing a
> >> >> + * modified form of Cliff Click's basic insertion algorithm. It
> >> >> + * requires the table size be a power of two. To prevent any
> >> >> + * possibility of an infinite loop we always make the internal table
> >> >> + * size double the size of the requested table size (max_elts * 2).
> >> >> + * Likewise, we never reuse a slot or resize or delete elements - when
> >> >> + * we've reached max_elts entries, we simply return NULL once we've
> >> >> + * run out of entries. Readers can at any point in time traverse the
> >> >> + * tracing map and safely access the key/val pairs.
> >> >> + *
> >> >> + * Return: the tracing_map_elt pointer val associated with the key.
> >> >> + * If this was a newly inserted key, the val will be a newly allocated
> >> >> + * and associated tracing_map_elt pointer val. If the key wasn't
> >> >> + * found and the pool of tracing_map_elts has been exhausted, NULL is
> >> >> + * returned and no further insertions will succeed.
> >> >> + */
> >> >> +struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)
> >> >> +{
> >> >> + u32 idx, key_hash, test_key;
> >> >> +
> >> >> + key_hash = jhash(key, map->key_size, 0);
> >> >> + idx = key_hash >> (32 - (map->map_bits + 1));
> >> >> +
> >> >> + while (1) {
> >> >> + idx &= (map->map_size - 1);
> >> >> + test_key = map->map[idx].key;
> >> >> +
> >> >> + if (test_key && test_key == key_hash && map->map[idx].val &&
> >> >> + keys_match(key, map->map[idx].val->key, map->key_size))
> >> >> + return map->map[idx].val;
> >> >> +
> >> >> + if (!test_key && !cmpxchg(&map->map[idx].key, 0, key_hash)) {
> >> >> + struct tracing_map_elt *elt;
> >> >> +
> >> >> + elt = get_free_elt(map);
> >> >> + if (!elt)
> >> >> + break;
> >> >> + memcpy(elt->key, key, map->key_size);
> >> >> + map->map[idx].val = elt;
> >> >> +
> >> >> + return map->map[idx].val;
> >> >> + }
> >> >> + idx++;
> >> >> + }
> >> >> +
> >> >> + return NULL;
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_destroy - Destroy a tracing_map
> >> >> + * @map: The tracing_map to destroy
> >> >> + *
> >> >> + * Frees a tracing_map along with its associated array of
> >> >> + * tracing_map_elts.
> >> >> + *
> >> >> + * Callers should make sure there are no readers or writers actively
> >> >> + * reading or inserting into the map before calling this.
> >> >> + */
> >> >> +void tracing_map_destroy(struct tracing_map *map)
> >> >> +{
> >> >> + if (!map)
> >> >> + return;
> >> >> +
> >> >> + tracing_map_free_elts(map);
> >> >> +
> >> >> + kfree(map->map);
> >> >> + kfree(map);
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_clear - Clear a tracing_map
> >> >> + * @map: The tracing_map to clear
> >> >> + *
> >> >> + * Resets the tracing map to a cleared or initial state. The
> >> >> + * tracing_map_elts are all cleared, and the array of struct
> >> >> + * tracing_map_entry is reset to an initialized state.
> >> >> + *
> >> >> + * Callers should make sure there are no writers actively inserting
> >> >> + * into the map before calling this.
> >> >> + */
> >> >> +void tracing_map_clear(struct tracing_map *map)
> >> >> +{
> >> >> + unsigned int i, size;
> >> >> +
> >> >> + atomic_set(&map->next_elt, -1);
> >> >> +
> >> >> + size = map->map_size * sizeof(struct tracing_map_entry);
> >> >> + memset(map->map, 0, size);
> >> >> +
> >> >> + for (i = 0; i < map->max_elts; i++)
> >> >> + tracing_map_elt_clear(map->elts[i]);
> >> >> +}
> >> >> +
> >> >> +static void set_sort_key(struct tracing_map *map,
> >> >> + struct tracing_map_sort_key *sort_key)
> >> >> +{
> >> >> + map->sort_key = *sort_key;
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_create - Create a lock-free map and element pool
> >> >> + * @map_bits: The size of the map (2 ** map_bits)
> >> >> + * @key_size: The size of the key for the map in bytes
> >> >> + * @ops: Optional client-defined tracing_map_ops instance
> >> >> + * @private_data: Client data associated with the map
> >> >> + *
> >> >> + * Creates and sets up a map to contain 2 ** map_bits number of
> >> >> + * elements (internally maintained as 'max_elts' in struct
> >> >> + * tracing_map). Before using, map fields should be added to the map
> >> >> + * with tracing_map_add_sum_field() and tracing_map_add_key_field().
> >> >> + * tracing_map_init() should then be called to allocate the array of
> >> >> + * tracing_map_elts, in order to avoid allocating anything in the map
> >> >> + * insertion path. The user-specified map size reflects the maximum
> >> >> + * number of elements that can be contained in the table requested by
> >> >> + * the user - internally we double that in order to keep the table
> >> >> + * sparse and keep collisions manageable.
> >> >> + *
> >> >> + * A tracing_map is a special-purpose map designed to aggregate or
> >> >> + * 'sum' one or more values associated with a specific object of type
> >> >> + * tracing_map_elt, which is attached by the map to a given key.
> >> >> + *
> >> >> + * tracing_map_create() sets up the map itself, and provides
> >> >> + * operations for inserting tracing_map_elts, but doesn't allocate the
> >> >> + * tracing_map_elts themselves, or provide a means for describing the
> >> >> + * keys or sums associated with the tracing_map_elts. All
> >> >> + * tracing_map_elts for a given map have the same set of sums and
> >> >> + * keys, which are defined by the client using the functions
> >> >> + * tracing_map_add_key_field() and tracing_map_add_sum_field(). Once
> >> >> + * the fields are defined, the pool of elements allocated for the map
> >> >> + * can be created, which occurs when the client code calls
> >> >> + * tracing_map_init().
> >> >> + *
> >> >> + * When tracing_map_init() returns, tracing_map_elt elements can be
> >> >> + * inserted into the map using tracing_map_insert(). When called,
> >> >> + * tracing_map_insert() grabs a free tracing_map_elt from the pool, or
> >> >> + * finds an existing match in the map and in either case returns it.
> >> >> + * The client can then use tracing_map_update_sum() and
> >> >> + * tracing_map_read_sum() to update or read a given sum field for the
> >> >> + * tracing_map_elt.
> >> >> + *
> >> >> + * The client can at any point retrieve and traverse the current set
> >> >> + * of inserted tracing_map_elts in a tracing_map, via
> >> >> + * tracing_map_sort_entries(). Sorting can be done on any field,
> >> >> + * including keys.
> >> >> + *
> >> >> + * See tracing_map.h for a description of tracing_map_ops.
> >> >> + *
> >> >> + * Return: the tracing_map pointer if successful, ERR_PTR if not.
> >> >> + */
> >> >> +struct tracing_map *tracing_map_create(unsigned int map_bits,
> >> >> + unsigned int key_size,
> >> >> + struct tracing_map_ops *ops,
> >> >> + void *private_data)
> >> >> +{
> >> >> + struct tracing_map *map;
> >> >> + unsigned int i;
> >> >> +
> >> >> + if (map_bits < TRACING_MAP_BITS_MIN ||
> >> >> + map_bits > TRACING_MAP_BITS_MAX)
> >> >> + return ERR_PTR(-EINVAL);
> >> >> +
> >> >> + map = kzalloc(sizeof(*map), GFP_KERNEL);
> >> >> + if (!map)
> >> >> + return ERR_PTR(-ENOMEM);
> >> >> +
> >> >> + map->map_bits = map_bits;
> >> >> + map->max_elts = (1 << map_bits);
> >> >> + atomic_set(&map->next_elt, -1);
> >> >> +
> >> >> + map->map_size = (1 << (map_bits + 1));
> >> >> + map->ops = ops;
> >> >> +
> >> >> + map->private_data = private_data;
> >> >> +
> >> >> + map->map = kcalloc(map->map_size, sizeof(struct tracing_map_entry),
> >> >> + GFP_KERNEL);
> >> >> + if (!map->map)
> >> >> + goto free;
> >> >> +
> >> >> + map->key_size = key_size;
> >> >> + for (i = 0; i < TRACING_MAP_KEYS_MAX; i++)
> >> >> + map->key_idx[i] = -1;
> >> >> + out:
> >> >> + return map;
> >> >> + free:
> >> >> + tracing_map_destroy(map);
> >> >> + map = ERR_PTR(-ENOMEM);
> >> >> +
> >> >> + goto out;
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_init - Allocate and clear a map's tracing_map_elts
> >> >> + * @map: The tracing_map to initialize
> >> >> + *
> >> >> + * Allocates a clears a pool of tracing_map_elts equal to the
> >> >> + * user-specified size of 2 ** map_bits (internally maintained as
> >> >> + * 'max_elts' in struct tracing_map). Before using, the map fields
> >> >> + * should be added to the map with tracing_map_add_sum_field() and
> >> >> + * tracing_map_add_key_field(). tracing_map_init() should then be
> >> >> + * called to allocate the array of tracing_map_elts, in order to avoid
> >> >> + * allocating anything in the map insertion path. The user-specified
> >> >> + * map size reflects the max number of elements requested by the user
> >> >> + * - internally we double that in order to keep the table sparse and
> >> >> + * keep collisions manageable.
> >> >> + *
> >> >> + * See tracing_map.h for a description of tracing_map_ops.
> >> >> + *
> >> >> + * Return: the tracing_map pointer if successful, ERR_PTR if not.
> >> >> + */
> >> >> +int tracing_map_init(struct tracing_map *map)
> >> >> +{
> >> >> + int err;
> >> >> +
> >> >> + if (map->n_fields < 2)
> >> >> + return -EINVAL; /* need at least 1 key and 1 val */
> >> >> +
> >> >> + err = tracing_map_alloc_elts(map);
> >> >> + if (err)
> >> >> + return err;
> >> >> +
> >> >> + tracing_map_clear(map);
> >> >> +
> >> >> + return err;
> >> >> +}
> >> >> +
> >> >> +static int cmp_entries_dup(const struct tracing_map_sort_entry **a,
> >> >> + const struct tracing_map_sort_entry **b)
> >> >> +{
> >> >> + int ret = 0;
> >> >> +
> >> >> + if (memcmp((*a)->key, (*b)->key, (*a)->elt->map->key_size))
> >> >> + ret = 1;
> >> >> +
> >> >> + return ret;
> >> >> +}
> >> >> +
> >> >> +static int cmp_entries_sum(const struct tracing_map_sort_entry **a,
> >> >> + const struct tracing_map_sort_entry **b)
> >> >> +{
> >> >> + const struct tracing_map_elt *elt_a, *elt_b;
> >> >> + struct tracing_map_sort_key *sort_key;
> >> >> + struct tracing_map_field *field;
> >> >> + tracing_map_cmp_fn_t cmp_fn;
> >> >> + void *val_a, *val_b;
> >> >> + int ret = 0;
> >> >> +
> >> >> + elt_a = (*a)->elt;
> >> >> + elt_b = (*b)->elt;
> >> >> +
> >> >> + sort_key = &elt_a->map->sort_key;
> >> >> +
> >> >> + field = &elt_a->fields[sort_key->field_idx];
> >> >> + cmp_fn = field->cmp_fn;
> >> >> +
> >> >> + val_a = &elt_a->fields[sort_key->field_idx].sum;
> >> >> + val_b = &elt_b->fields[sort_key->field_idx].sum;
> >> >> +
> >> >> + ret = cmp_fn(val_a, val_b);
> >> >> + if (sort_key->descending)
> >> >> + ret = -ret;
> >> >> +
> >> >> + return ret;
> >> >> +}
> >> >> +
> >> >> +static int cmp_entries_key(const struct tracing_map_sort_entry **a,
> >> >> + const struct tracing_map_sort_entry **b)
> >> >> +{
> >> >> + const struct tracing_map_elt *elt_a, *elt_b;
> >> >> + struct tracing_map_sort_key *sort_key;
> >> >> + struct tracing_map_field *field;
> >> >> + tracing_map_cmp_fn_t cmp_fn;
> >> >> + void *val_a, *val_b;
> >> >> + int ret = 0;
> >> >> +
> >> >> + elt_a = (*a)->elt;
> >> >> + elt_b = (*b)->elt;
> >> >> +
> >> >> + sort_key = &elt_a->map->sort_key;
> >> >> +
> >> >> + field = &elt_a->fields[sort_key->field_idx];
> >> >> +
> >> >> + cmp_fn = field->cmp_fn;
> >> >> +
> >> >> + val_a = elt_a->key + field->offset;
> >> >> + val_b = elt_b->key + field->offset;
> >> >> +
> >> >> + ret = cmp_fn(val_a, val_b);
> >> >> + if (sort_key->descending)
> >> >> + ret = -ret;
> >> >> +
> >> >> + return ret;
> >> >> +}
> >> >> +
> >> >> +static void destroy_sort_entry(struct tracing_map_sort_entry *entry)
> >> >> +{
> >> >> + if (!entry)
> >> >> + return;
> >> >> +
> >> >> + if (entry->elt_copied)
> >> >> + tracing_map_elt_free(entry->elt);
> >> >> +
> >> >> + kfree(entry);
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_destroy_entries - Destroy a tracing_map_sort_entries() array
> >> >> + * @entries: The entries to destroy
> >> >> + * @n_entries: The number of entries in the array
> >> >> + *
> >> >> + * Destroy the elements returned by a tracing_map_sort_entries() call.
> >> >> + */
> >> >> +void tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries,
> >> >> + unsigned int n_entries)
> >> >> +{
> >> >> + unsigned int i;
> >> >> +
> >> >> + for (i = 0; i < n_entries; i++)
> >> >> + destroy_sort_entry(entries[i]);
> >> >> +}
> >> >> +
> >> >> +static struct tracing_map_sort_entry *
> >> >> +create_sort_entry(void *key, struct tracing_map_elt *elt)
> >> >> +{
> >> >> + struct tracing_map_sort_entry *sort_entry;
> >> >> +
> >> >> + sort_entry = kzalloc(sizeof(*sort_entry), GFP_KERNEL);
> >> >> + if (!sort_entry)
> >> >> + return NULL;
> >> >> +
> >> >> + sort_entry->key = key;
> >> >> + sort_entry->elt = elt;
> >> >> +
> >> >> + return sort_entry;
> >> >> +}
> >> >> +
> >> >> +static struct tracing_map_elt *copy_elt(struct tracing_map_elt *elt)
> >> >> +{
> >> >> + struct tracing_map_elt *dup_elt;
> >> >> + unsigned int i;
> >> >> +
> >> >> + dup_elt = tracing_map_elt_alloc(elt->map);
> >> >> + if (!dup_elt)
> >> >> + return NULL;
> >> >> +
> >> >> + if (elt->map->ops && elt->map->ops->elt_copy)
> >> >> + elt->map->ops->elt_copy(dup_elt, elt);
> >> >> +
> >> >> + dup_elt->private_data = elt->private_data;
> >> >> + memcpy(dup_elt->key, elt->key, elt->map->key_size);
> >> >> +
> >> >> + for (i = 0; i < elt->map->n_fields; i++) {
> >> >> + atomic64_set(&dup_elt->fields[i].sum,
> >> >> + atomic64_read(&elt->fields[i].sum));
> >> >> + dup_elt->fields[i].cmp_fn = elt->fields[i].cmp_fn;
> >> >> + }
> >> >> +
> >> >> + return dup_elt;
> >> >> +}
> >> >> +
> >> >> +static int merge_dup(struct tracing_map_sort_entry **sort_entries,
> >> >> + unsigned int target, unsigned int dup)
> >> >> +{
> >> >> + struct tracing_map_elt *target_elt, *elt;
> >> >> + bool first_dup = (target - dup) == 1;
> >> >> + int i;
> >> >> +
> >> >> + if (first_dup) {
> >> >> + elt = sort_entries[target]->elt;
> >> >> + target_elt = copy_elt(elt);
> >> >> + if (!target_elt)
> >> >> + return -ENOMEM;
> >> >> + sort_entries[target]->elt = target_elt;
> >> >> + sort_entries[target]->elt_copied = true;
> >> >> + } else
> >> >> + target_elt = sort_entries[target]->elt;
> >> >> +
> >> >> + elt = sort_entries[dup]->elt;
> >> >> +
> >> >> + for (i = 0; i < elt->map->n_fields; i++)
> >> >> + atomic64_add(atomic64_read(&elt->fields[i].sum),
> >> >> + &target_elt->fields[i].sum);
> >> >> +
> >> >> + sort_entries[dup]->dup = true;
> >> >> +
> >> >> + return 0;
> >> >> +}
> >> >> +
> >> >> +static int merge_dups(struct tracing_map_sort_entry **sort_entries,
> >> >> + int n_entries, unsigned int key_size)
> >> >> +{
> >> >> + unsigned int dups = 0, total_dups = 0;
> >> >> + int err, i, j;
> >> >> + void *key;
> >> >> +
> >> >> + if (n_entries < 2)
> >> >> + return total_dups;
> >> >> +
> >> >> + sort(sort_entries, n_entries, sizeof(struct tracing_map_sort_entry *),
> >> >> + (int (*)(const void *, const void *))cmp_entries_dup, NULL);
> >> >> +
> >> >> + key = sort_entries[0]->key;
> >> >> + for (i = 1; i < n_entries; i++) {
> >> >> + if (!memcmp(sort_entries[i]->key, key, key_size)) {
> >> >> + dups++; total_dups++;
> >> >> + err = merge_dup(sort_entries, i - dups, i);
> >> >> + if (err)
> >> >> + return err;
> >> >> + continue;
> >> >> + }
> >> >> + key = sort_entries[i]->key;
> >> >> + dups = 0;
> >> >> + }
> >> >> +
> >> >> + if (!total_dups)
> >> >> + return total_dups;
> >> >> +
> >> >> + for (i = 0, j = 0; i < n_entries; i++) {
> >> >> + if (!sort_entries[i]->dup) {
> >> >> + sort_entries[j] = sort_entries[i];
> >> >> + if (j++ != i)
> >> >> + sort_entries[i] = NULL;
> >> >> + } else {
> >> >> + destroy_sort_entry(sort_entries[i]);
> >> >> + sort_entries[i] = NULL;
> >> >> + }
> >> >> + }
> >> >> +
> >> >> + return total_dups;
> >> >> +}
> >> >> +
> >> >> +static bool is_key(struct tracing_map *map, unsigned int field_idx)
> >> >> +{
> >> >> + unsigned int i;
> >> >> +
> >> >> + for (i = 0; i < map->n_keys; i++)
> >> >> + if (map->key_idx[i] == field_idx)
> >> >> + return true;
> >> >> + return false;
> >> >> +}
> >> >> +
> >> >> +static void sort_secondary(struct tracing_map *map,
> >> >> + const struct tracing_map_sort_entry **entries,
> >> >> + unsigned int n_entries,
> >> >> + struct tracing_map_sort_key *primary_key,
> >> >> + struct tracing_map_sort_key *secondary_key)
> >> >> +{
> >> >> + int (*primary_fn)(const struct tracing_map_sort_entry **,
> >> >> + const struct tracing_map_sort_entry **);
> >> >> + int (*secondary_fn)(const struct tracing_map_sort_entry **,
> >> >> + const struct tracing_map_sort_entry **);
> >> >> + unsigned i, start = 0, n_sub = 1;
> >> >> +
> >> >> + if (is_key(map, primary_key->field_idx))
> >> >> + primary_fn = cmp_entries_key;
> >> >> + else
> >> >> + primary_fn = cmp_entries_sum;
> >> >> +
> >> >> + if (is_key(map, secondary_key->field_idx))
> >> >> + secondary_fn = cmp_entries_key;
> >> >> + else
> >> >> + secondary_fn = cmp_entries_sum;
> >> >> +
> >> >> + for (i = 0; i < n_entries - 1; i++) {
> >> >> + const struct tracing_map_sort_entry **a = &entries[i];
> >> >> + const struct tracing_map_sort_entry **b = &entries[i + 1];
> >> >> +
> >> >> + if (primary_fn(a, b) == 0) {
> >> >> + n_sub++;
> >> >> + if (i < n_entries - 2)
> >> >> + continue;
> >> >> + }
> >> >> +
> >> >> + if (n_sub < 2) {
> >> >> + start = i + 1;
> >> >> + n_sub = 1;
> >> >> + continue;
> >> >> + }
> >> >> +
> >> >> + set_sort_key(map, secondary_key);
> >> >> + sort(&entries[start], n_sub,
> >> >> + sizeof(struct tracing_map_sort_entry *),
> >> >> + (int (*)(const void *, const void *))secondary_fn, NULL);
> >> >> + set_sort_key(map, primary_key);
> >> >> +
> >> >> + start = i + 1;
> >> >> + n_sub = 1;
> >> >> + }
> >> >> +}
> >> >> +
> >> >> +/**
> >> >> + * tracing_map_sort_entries - Sort the current set of tracing_map_elts in a map
> >> >> + * @map: The tracing_map
> >> >> + * @sort_key: The sort key to use for sorting
> >> >> + * @sort_entries: outval: pointer to allocated and sorted array of entries
> >> >> + *
> >> >> + * tracing_map_sort_entries() sorts the current set of entries in the
> >> >> + * map and returns the list of tracing_map_sort_entries containing
> >> >> + * them to the client in the sort_entries param. The client can
> >> >> + * access the struct tracing_map_elt element of interest directly as
> >> >> + * the 'elt' field of a returned struct tracing_map_sort_entry object.
> >> >> + *
> >> >> + * The sort_key has only two fields: idx and descending. 'idx' refers
> >> >> + * to the index of the field added via tracing_map_add_sum_field() or
> >> >> + * tracing_map_add_key_field() when the tracing_map was initialized.
> >> >> + * 'descending' is a flag that if set reverses the sort order, which
> >> >> + * by default is ascending.
> >> >> + *
> >> >> + * The client should not hold on to the returned array but should use
> >> >> + * it and call tracing_map_destroy_sort_entries() when done.
> >> >> + *
> >> >> + * Return: the number of sort_entries in the struct tracing_map_sort_entry
> >> >> + * array, negative on error
> >> >> + */
> >> >> +int tracing_map_sort_entries(struct tracing_map *map,
> >> >> + struct tracing_map_sort_key *sort_keys,
> >> >> + unsigned int n_sort_keys,
> >> >> + struct tracing_map_sort_entry ***sort_entries)
> >> >> +{
> >> >> + int (*cmp_entries_fn)(const struct tracing_map_sort_entry **,
> >> >> + const struct tracing_map_sort_entry **);
> >> >> + struct tracing_map_sort_entry *sort_entry, **entries;
> >> >> + int i, n_entries, ret;
> >> >> +
> >> >> + entries = kcalloc(map->max_elts, sizeof(sort_entry), GFP_KERNEL);
> >> >> + if (!entries)
> >> >> + return -ENOMEM;
> >> >> +
> >> >> + for (i = 0, n_entries = 0; i < map->map_size; i++) {
> >> >> + if (!map->map[i].key || !map->map[i].val)
> >> >> + continue;
> >> >> +
> >> >> + entries[n_entries] = create_sort_entry(map->map[i].val->key,
> >> >> + map->map[i].val);
> >> >> + if (!entries[n_entries++]) {
> >> >> + ret = -ENOMEM;
> >> >> + goto free;
> >> >> + }
> >> >> + }
> >> >> +
> >> >> + if (n_entries == 0) {
> >> >> + ret = 0;
> >> >> + goto free;
> >> >> + }
> >> >> +
> >> >> + if (n_entries == 1) {
> >> >> + *sort_entries = entries;
> >> >> + return 1;
> >> >> + }
> >> >> +
> >> >> + ret = merge_dups(entries, n_entries, map->key_size);
> >> >> + if (ret < 0)
> >> >> + goto free;
> >> >> + n_entries -= ret;
> >> >> +
> >> >> + if (is_key(map, sort_keys[0].field_idx))
> >> >> + cmp_entries_fn = cmp_entries_key;
> >> >> + else
> >> >> + cmp_entries_fn = cmp_entries_sum;
> >> >> +
> >> >> + set_sort_key(map, &sort_keys[0]);
> >> >> +
> >> >> + sort(entries, n_entries, sizeof(struct tracing_map_sort_entry *),
> >> >> + (int (*)(const void *, const void *))cmp_entries_fn, NULL);
> >> >> +
> >> >> + if (n_sort_keys > 1)
> >> >> + sort_secondary(map,
> >> >> + (const struct tracing_map_sort_entry **)entries,
> >> >> + n_entries,
> >> >> + &sort_keys[0],
> >> >> + &sort_keys[1]);
> >> >> +
> >> >> + *sort_entries = entries;
> >> >> +
> >> >> + return n_entries;
> >> >> + free:
> >> >> + tracing_map_destroy_sort_entries(entries, n_entries);
> >> >> +
> >> >> + return ret;
> >> >> +}
> >> >> diff --git a/kernel/trace/tracing_map.h b/kernel/trace/tracing_map.h
> >> >> new file mode 100644
> >> >> index 0000000..2e63c5c
> >> >> --- /dev/null
> >> >> +++ b/kernel/trace/tracing_map.h
> >> >> @@ -0,0 +1,258 @@
> >> >> +#ifndef __TRACING_MAP_H
> >> >> +#define __TRACING_MAP_H
> >> >> +
> >> >> +#define TRACING_MAP_BITS_DEFAULT 11
> >> >> +#define TRACING_MAP_BITS_MAX 17
> >> >> +#define TRACING_MAP_BITS_MIN 7
> >> >> +
> >> >> +#define TRACING_MAP_FIELDS_MAX 4
> >> >> +#define TRACING_MAP_KEYS_MAX 2
> >> >> +
> >> >> +#define TRACING_MAP_SORT_KEYS_MAX 2
> >> >> +
> >> >> +typedef int (*tracing_map_cmp_fn_t) (void *val_a, void *val_b);
> >> >> +
> >> >> +/*
> >> >> + * This is an overview of the tracing_map data structures and how they
> >> >> + * relate to the tracing_map API. The details of the algorithms
> >> >> + * aren't discussed here - this is just a general overview of the data
> >> >> + * structures and how they interact with the API.
> >> >> + *
> >> >> + * The central data structure of the tracing_map is an initially
> >> >> + * zeroed array of struct tracing_map_entry (stored in the map field
> >> >> + * of struct tracing_map). tracing_map_entry is a very simple data
> >> >> + * structure containing only two fields: a 32-bit unsigned 'key'
> >> >> + * variable and a pointer named 'val'. This array of struct
> >> >> + * tracing_map_entry is essentially a hash table which will be
> >> >> + * modified by a single function, tracing_map_insert(), but which can
> >> >> + * be traversed and read by a user at any time (though the user does
> >> >> + * this indirectly via an array of tracing_map_sort_entry - see the
> >> >> + * explanation of that data structure in the discussion of the
> >> >> + * sorting-related data structures below).
> >> >> + *
> >> >> + * The central function of the tracing_map API is
> >> >> + * tracing_map_insert(). tracing_map_insert() hashes the
> >> >> + * arbitrarily-sized key passed into it into a 32-bit unsigned key.
> >> >> + * It then uses this key, truncated to the array size, as an index
> >> >> + * into the array of tracing_map_entries. If the value of the 'key'
> >> >> + * field of the tracing_map_entry found at that location is 0, then
> >> >> + * that entry is considered to be free and can be claimed, by
> >> >> + * replacing the 0 in the 'key' field of the tracing_map_entry with
> >> >> + * the new 32-bit hashed key. Once claimed, that tracing_map_entry's
> >> >> + * 'val' field is then used to store a unique element which will be
> >> >> + * forever associated with that 32-bit hashed key in the
> >> >> + * tracing_map_entry.
> >> >> + *
> >> >> + * That unique element now in the tracing_map_entry's 'val' field is
> >> >> + * an instance of tracing_map_elt, where 'elt' in the latter part of
> >> >> + * that variable name is short for 'element'. The purpose of a
> >> >> + * tracing_map_elt is to hold values specific to the the particular
> >> >> + * 32-bit hashed key it's assocated with. Things such as the unique
> >> >> + * set of aggregated sums associated with the 32-bit hashed key, along
> >> >> + * with a copy of the full key associated with the entry, and which
> >> >> + * was used to produce the 32-bit hashed key.
> >> >> + *
> >> >> + * When tracing_map_create() is called to create the tracing map, the
> >> >> + * user specifies (indirectly via the map_bits param, the details are
> >> >> + * unimportant for this discussion) the maximum number of elements
> >> >> + * that the map can hold (stored in the max_elts field of struct
> >> >> + * tracing_map). This is the maximum possible number of
> >> >> + * tracing_map_entries in the tracing_map_entry array which can be
> >> >> + * 'claimed' as described in the above discussion, and therefore is
> >> >> + * also the maximum number of tracing_map_elts that can be associated
> >> >> + * with the tracing_map_entry array in the tracing_map. Because of
> >> >> + * the way the insertion algorithm works, the size of the allocated
> >> >> + * tracing_map_entry array is always twice the maximum number of
> >> >> + * elements (2 * max_elts). This value is stored in the map_size
> >> >> + * field of struct tracing_map.
> >> >> + *
> >> >> + * Because tracing_map_insert() needs to work from any context,
> >> >> + * including from within the memory allocation functions themselves,
> >> >> + * both the tracing_map_entry array and a pool of max_elts
> >> >> + * tracing_map_elts are pre-allocated before any call is made to
> >> >> + * tracing_map_insert().
> >> >> + *
> >> >> + * The tracing_map_entry array is allocated as a single block by
> >> >> + * tracing_map_create().
> >> >> + *
> >> >> + * Because the tracing_map_elts are much larger objects and can't
> >> >> + * generally be allocated together as a single large array without
> >> >> + * failure, they're allocated individually, by tracing_map_init().
> >> >> + *
> >> >> + * The pool of tracing_map_elts are allocated by tracing_map_init()
> >> >> + * rather than by tracing_map_create() because at the time
> >> >> + * tracing_map_create() is called, there isn't enough information to
> >> >> + * create the tracing_map_elts. Specifically,the user first needs to
> >> >> + * tell the tracing_map implementation how many fields the
> >> >> + * tracing_map_elts contain, and which types of fields they are (key
> >> >> + * or sum). The user does this via the tracing_map_add_sum_field()
> >> >> + * and tracing_map_add_key_field() functions, following which the user
> >> >> + * calls tracing_map_init() to finish up the tracing map setup. The
> >> >> + * array holding the pointers which make up the pre-allocated pool of
> >> >> + * tracing_map_elts is allocated as a single block and is stored in
> >> >> + * the elts field of struct tracing_map.
> >> >> + *
> >> >> + * There is also a set of structures used for sorting that might
> >> >> + * benefit from some minimal explanation.
> >> >> + *
> >> >> + * struct tracing_map_sort_key is used to drive the sort at any given
> >> >> + * time. By 'any given time' we mean that a different
> >> >> + * tracing_map_sort_key will be used at different times depending on
> >> >> + * whether the sort currently being performed is a primary or a
> >> >> + * secondary sort.
> >> >> + *
> >> >> + * The sort key is very simple, consisting of the field index of the
> >> >> + * tracing_map_elt field to sort on (which the user saved when adding
> >> >> + * the field), and whether the sort should be done in an ascending or
> >> >> + * descending order.
> >> >> + *
> >> >> + * For the convenience of the sorting code, a tracing_map_sort_entry
> >> >> + * is created for each tracing_map_elt, again individually allocated
> >> >> + * to avoid failures that might be expected if allocated as a single
> >> >> + * large array of struct tracing_map_sort_entry.
> >> >> + * tracing_map_sort_entry instances are the objects expected by the
> >> >> + * various internal sorting functions, and are also what the user
> >> >> + * ultimately receives after calling tracing_map_sort_entries().
> >> >> + * Because it doesn't make sense for users to access an unordered and
> >> >> + * sparsely populated tracing_map directly, the
> >> >> + * tracing_map_sort_entries() function is provided so that users can
> >> >> + * retrieve a sorted list of all existing elements. In addition to
> >> >> + * the associated tracing_map_elt 'elt' field contained within the
> >> >> + * tracing_map_sort_entry, which is the object of interest to the
> >> >> + * user, tracing_map_sort_entry objects contain a number of additional
> >> >> + * fields which are used for caching and internal purposes and can
> >> >> + * safely be ignored.
> >> >> +*/
> >> >> +
> >> >> +struct tracing_map_field {
> >> >> + tracing_map_cmp_fn_t cmp_fn;
> >> >> + union {
> >> >> + atomic64_t sum;
> >> >> + unsigned int offset;
> >> >> + };
> >> >> +};
> >> >> +
> >> >> +struct tracing_map_elt {
> >> >> + struct tracing_map *map;
> >> >> + struct tracing_map_field *fields;
> >> >> + void *key;
> >> >> + void *private_data;
> >> >> +};
> >> >> +
> >> >> +struct tracing_map_entry {
> >> >> + u32 key;
> >> >> + struct tracing_map_elt *val;
> >> >> +};
> >> >> +
> >> >> +struct tracing_map_sort_key {
> >> >> + unsigned int field_idx;
> >> >> + bool descending;
> >> >> +};
> >> >> +
> >> >> +struct tracing_map_sort_entry {
> >> >> + void *key;
> >> >> + struct tracing_map_elt *elt;
> >> >> + bool elt_copied;
> >> >> + bool dup;
> >> >> +};
> >> >> +
> >> >> +struct tracing_map {
> >> >> + unsigned int key_size;
> >> >> + unsigned int map_bits;
> >> >> + unsigned int map_size;
> >> >> + unsigned int max_elts;
> >> >> + atomic_t next_elt;
> >> >> + struct tracing_map_elt **elts;
> >> >> + struct tracing_map_entry *map;
> >> >> + struct tracing_map_ops *ops;
> >> >> + void *private_data;
> >> >> + struct tracing_map_field fields[TRACING_MAP_FIELDS_MAX];
> >> >> + unsigned int n_fields;
> >> >> + int key_idx[TRACING_MAP_KEYS_MAX];
> >> >> + unsigned int n_keys;
> >> >> + struct tracing_map_sort_key sort_key;
> >> >> +};
> >> >> +
> >> >> +/**
> >> >> + * struct tracing_map_ops - callbacks for tracing_map
> >> >> + *
> >> >> + * The methods in this structure define callback functions for various
> >> >> + * operations on a tracing_map or objects related to a tracing_map.
> >> >> + *
> >> >> + * For a detailed description of tracing_map_elt objects please see
> >> >> + * the overview of tracing_map data structures at the beginning of
> >> >> + * this file.
> >> >> + *
> >> >> + * All the methods below are optional.
> >> >> + *
> >> >> + * @elt_alloc: When a tracing_map_elt is allocated, this function, if
> >> >> + * defined, will be called and gives clients the opportunity to
> >> >> + * allocate additional data and attach it to the element
> >> >> + * (tracing_map_elt->private_data is meant for that purpose).
> >> >> + * Element allocation occurs before tracing begins, when the
> >> >> + * tracing_map_init() call is made by client code.
> >> >> + *
> >> >> + * @elt_copy: At certain points in the lifetime of an element, it may
> >> >> + * need to be copied. The copy should include a copy of the
> >> >> + * client-allocated data, which can be copied into the 'to'
> >> >> + * element from the 'from' element.
> >> >> + *
> >> >> + * @elt_free: When a tracing_map_elt is freed, this function is called
> >> >> + * and allows client-allocated per-element data to be freed.
> >> >> + *
> >> >> + * @elt_clear: This callback allows per-element client-defined data to
> >> >> + * be cleared, if applicable.
> >> >> + *
> >> >> + * @elt_init: This callback allows per-element client-defined data to
> >> >> + * be initialized when used i.e. when the element is actually
> >> >> + * claimed by tracing_map_insert() in the context of the map
> >> >> + * insertion.
> >> >> + */
> >> >> +struct tracing_map_ops {
> >> >> + int (*elt_alloc)(struct tracing_map_elt *elt);
> >> >> + void (*elt_copy)(struct tracing_map_elt *to,
> >> >> + struct tracing_map_elt *from);
> >> >> + void (*elt_free)(struct tracing_map_elt *elt);
> >> >> + void (*elt_clear)(struct tracing_map_elt *elt);
> >> >> + void (*elt_init)(struct tracing_map_elt *elt);
> >> >> +};
> >> >> +
> >> >> +extern struct tracing_map *tracing_map_create(unsigned int map_bits,
> >> >> + unsigned int key_size,
> >> >> + struct tracing_map_ops *ops,
> >> >> + void *private_data);
> >> >> +extern int tracing_map_init(struct tracing_map *map);
> >> >> +
> >> >> +extern int tracing_map_add_sum_field(struct tracing_map *map);
> >> >> +extern int tracing_map_add_key_field(struct tracing_map *map,
> >> >> + unsigned int offset,
> >> >> + tracing_map_cmp_fn_t cmp_fn);
> >> >> +
> >> >> +extern void tracing_map_destroy(struct tracing_map *map);
> >> >> +extern void tracing_map_clear(struct tracing_map *map);
> >> >> +
> >> >> +extern struct tracing_map_elt *
> >> >> +tracing_map_insert(struct tracing_map *map, void *key);
> >> >> +
> >> >> +extern tracing_map_cmp_fn_t tracing_map_cmp_num(int field_size,
> >> >> + int field_is_signed);
> >> >> +extern int tracing_map_cmp_string(void *val_a, void *val_b);
> >> >> +extern int tracing_map_cmp_none(void *val_a, void *val_b);
> >> >> +
> >> >> +extern void tracing_map_update_sum(struct tracing_map_elt *elt,
> >> >> + unsigned int i, u64 n);
> >> >> +extern u64 tracing_map_read_sum(struct tracing_map_elt *elt, unsigned int i);
> >> >> +extern void tracing_map_set_field_descr(struct tracing_map *map,
> >> >> + unsigned int i,
> >> >> + unsigned int key_offset,
> >> >> + tracing_map_cmp_fn_t cmp_fn);
> >> >> +extern int
> >> >> +tracing_map_sort_entries(struct tracing_map *map,
> >> >> + struct tracing_map_sort_key *sort_keys,
> >> >> + unsigned int n_sort_keys,
> >> >> + struct tracing_map_sort_entry ***sort_entries);
> >> >> +
> >> >> +extern void
> >> >> +tracing_map_destroy_sort_entries(struct tracing_map_sort_entry **entries,
> >> >> + unsigned int n_entries);
> >> >> +#endif /* __TRACING_MAP_H */
> >> >> --
> >> >> 1.9.3
> >> >>
> >> >> --
> >> >> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> >> >> the body of a message to majordomo@...r.kernel.org
> >> >> More majordomo info at http://vger.kernel.org/majordomo-info.html
> >> >> Please read the FAQ at http://www.tux.org/lkml/
> >> >
> >> > --
> >> > Mathieu Desnoyers
> >> > EfficiOS Inc.
> >> > http://www.efficios.com
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists