Re: [PATCH v7 06/10] trace: Add lock-free tracing_map

From: Tom Zanussi
Date: Mon Jun 29 2015 - 16:21:21 EST


On Fri, 2015-06-12 at 14:17 -0400, Steven Rostedt wrote:
> On Mon, 8 Jun 2015 16:32:05 -0500
> Tom Zanussi <tom.zanussi@xxxxxxxxxxxxxxx> 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
>
> What is "elt"? I don't see it explained anywhere.
>

It's short for 'element' but I guess that's not why you're asking about
it.

Sorry for the confusion - I've written up a description of the data
structures and how they work, which is included in my next revision.

Here's that section, from the new tracing_map.h:

/*
* 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.
*/

Thanks,

Tom

>
> > 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
> >
> > Signed-off-by: Tom Zanussi <tom.zanussi@xxxxxxxxxxxxxxx>
>
>
> > +/**
> > + * tracing_map_update_sum - Add a value to a tracing_map_elt's sum
> > + * @elt: The tracing_map_elt
>
> Not a very useful comment, as I have no idea what "elt" is.
>
> I'll continue to review this patch about the mysterious element "elt".
>



> -- Steve
>
> > + * @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);
> > +}
> > +
>


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/