Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

Hi Namhyung,

On Wed, 2015-11-04 at 11:26 +0900, Namhyung Kim wrote:
> Hi Tom,
> 
> On Tue, Nov 03, 2015 at 07:47:52PM -0600, Tom Zanussi wrote:
> > Hi Namhyung,
> > 
> > On Mon, 2015-11-02 at 16:08 +0900, Namhyung Kim wrote:
> > > I thought it'd be better if users can see which one is the real drop
> > > or not.  IOW if drop count is much smaller than the normal event
> > > count, [s]he might want to ignore the occasional drops.  Otherwise,
> > > [s]he should restart with a bigger table.  This requires accurate
> > > counts of events and drops though.
> > > 
> > 
> > OK, how about the below - it basically moves the drops set/test/inc into
> > tracing_map_insert(), as well as a total hits count.  So those values
> > will be available for users to use in deciding whether to use the data
> > or restart with a bigger table, and the loop is bailed out of only if no
> > matching keys are found and there are drops, so callers can continue
> > updating existing entries.
> 
> But if a key didn't get a desired index, it'd still fail to update..
> 
> 
> > 
> > Users who want the original behavior still get the NULL return and can
> > stop calling tracing_map_insert() as before:
> > 
> > struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void 
> > *key)
> > {
> > u32 idx, key_hash, test_key;
> > struct tracing_map_entry *entry;
> > 
> > key_hash = jhash(key, map->key_size, 0);
> > if (key_hash == 0)
> > key_hash = 1;
> > idx = key_hash >> (32 - (map->map_bits + 1));
> > 
> > while (1) {
> > idx &= (map->map_size - 1);
> > entry = TRACING_MAP_ENTRY(map->map, idx);
> > test_key = entry->key;
> > 
> > if (test_key && test_key == key_hash && entry->val &&
> > keys_match(key, entry->val->key, map->key_size)) {
> > atomic64_inc(>hits);
> > return entry->val;
> > }
> > 
> > if (atomic64_read(>drops)) {
> > atomic64_inc(>drops);
> > break;
> > }
> 
> IMHO it should be removed.
> 
> > 
> > if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> > struct tracing_map_elt *elt;
> > 
> > elt = get_free_elt(map);
> > if (!elt) {
> > atomic64_inc(>drops);
> 
> And reset entry->key here..
> 
> > break;
> > }
> > memcpy(elt->key, key, map->key_size);
> > entry->val = elt;
> > 
> > atomic64_inc(>hits);
> > return entry->val;
> > }
> > idx++;
> > }
> > 
> > return NULL;
> > }
> 
> 
> Then tracing_map_lookup() can be implemented like *_insert but bail out
> from the loop if test_key is 0.  The caller might do like this:
> 
>   if (!atomic64_read(>drops))
>   elt = tracing_map_insert(...);
>   else
>   elt = tracing_map_lookup(...);
> 

Yeah, I think that should work - let me try that in the next version...

Thanks,

Tom

> Thanks,
> Namhyung


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

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Namhyung Kim]

Hi Tom,

On Tue, Nov 03, 2015 at 07:47:52PM -0600, Tom Zanussi wrote:
> Hi Namhyung,
> 
> On Mon, 2015-11-02 at 16:08 +0900, Namhyung Kim wrote:
> > I thought it'd be better if users can see which one is the real drop
> > or not.  IOW if drop count is much smaller than the normal event
> > count, [s]he might want to ignore the occasional drops.  Otherwise,
> > [s]he should restart with a bigger table.  This requires accurate
> > counts of events and drops though.
> > 
> 
> OK, how about the below - it basically moves the drops set/test/inc into
> tracing_map_insert(), as well as a total hits count.  So those values
> will be available for users to use in deciding whether to use the data
> or restart with a bigger table, and the loop is bailed out of only if no
> matching keys are found and there are drops, so callers can continue
> updating existing entries.

But if a key didn't get a desired index, it'd still fail to update..


> 
> Users who want the original behavior still get the NULL return and can
> stop calling tracing_map_insert() as before:
> 
> struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)
> {
> u32 idx, key_hash, test_key;
> struct tracing_map_entry *entry;
> 
> key_hash = jhash(key, map->key_size, 0);
> if (key_hash == 0)
> key_hash = 1;
> idx = key_hash >> (32 - (map->map_bits + 1));
> 
> while (1) {
> idx &= (map->map_size - 1);
> entry = TRACING_MAP_ENTRY(map->map, idx);
> test_key = entry->key;
> 
> if (test_key && test_key == key_hash && entry->val &&
> keys_match(key, entry->val->key, map->key_size)) {
> atomic64_inc(>hits);
> return entry->val;
> }
> 
> if (atomic64_read(>drops)) {
> atomic64_inc(>drops);
> break;
> }

IMHO it should be removed.

> 
> if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> struct tracing_map_elt *elt;
> 
> elt = get_free_elt(map);
> if (!elt) {
> atomic64_inc(>drops);

And reset entry->key here..

> break;
> }
> memcpy(elt->key, key, map->key_size);
> entry->val = elt;
> 
> atomic64_inc(>hits);
> return entry->val;
> }
> idx++;
> }
> 
> return NULL;
> }


Then tracing_map_lookup() can be implemented like *_insert but bail out
from the loop if test_key is 0.  The caller might do like this:

if (!atomic64_read(>drops))
elt = tracing_map_insert(...);
else
elt = tracing_map_lookup(...);

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

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

Hi Namhyung,

On Mon, 2015-11-02 at 16:08 +0900, Namhyung Kim wrote:
> Hi Tom,
> 
> On Thu, Oct 29, 2015 at 01:35:43PM -0500, Tom Zanussi wrote:
> > Hi Namhyung,
> > 
> > On Thu, 2015-10-29 at 17:31 +0900, Namhyung Kim wrote:
> > > Hi Tom,
> > > 
> > > On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> > > > 
> > > > Signed-off-by: Tom Zanussi 
> > > > Tested-by: Masami Hiramatsu 
> > > > ---
> > > > +/**
> > > > + * 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;
> > > > +   struct tracing_map_entry *entry;
> > > > +
> > > > +   key_hash = jhash(key, map->key_size, 0);
> > > > +   if (key_hash == 0)
> > > > +   key_hash = 1;
> > > > +   idx = key_hash >> (32 - (map->map_bits + 1));
> > > > +
> > > > +   while (1) {
> > > > +   idx &= (map->map_size - 1);
> > > > +   entry = TRACING_MAP_ENTRY(map->map, idx);
> > > > +   test_key = entry->key;
> > > > +
> > > > +   if (test_key && test_key == key_hash && entry->val &&
> > > > +   keys_match(key, entry->val->key, map->key_size))
> > > > +   return entry->val;
> > > > +
> > > > +   if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> > > > +   struct tracing_map_elt *elt;
> > > > +
> > > > +   elt = get_free_elt(map);
> > > > +   if (!elt)
> > > > +   break;
> > > > +   memcpy(elt->key, key, map->key_size);
> > > > +   entry->val = elt;
> > > > +
> > > > +   return entry->val;
> > > > +   }
> > > > +   idx++;
> > > > +   }
> > > > +
> > > > +   return NULL;
> > > > +}
> > > 
> > > IIUC this always insert new entry if no matching key found.  And if
> > > the map is full, it only fails after walking through the entries to
> > > find an empty one, mark the entry with the key and call to
> > > get_free_elt() returns NULL.  As 

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

Hi Namhyung,

On Mon, 2015-11-02 at 16:08 +0900, Namhyung Kim wrote:
> Hi Tom,
> 
> On Thu, Oct 29, 2015 at 01:35:43PM -0500, Tom Zanussi wrote:
> > Hi Namhyung,
> > 
> > On Thu, 2015-10-29 at 17:31 +0900, Namhyung Kim wrote:
> > > Hi Tom,
> > > 
> > > On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> > > > 
> > > > Signed-off-by: Tom Zanussi 
> > > > Tested-by: Masami Hiramatsu 
> > > > ---
> > > > +/**
> > > > + * 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;
> > > > +   struct tracing_map_entry *entry;
> > > > +
> > > > +   key_hash = jhash(key, map->key_size, 0);
> > > > +   if (key_hash == 0)
> > > > +   key_hash = 1;
> > > > +   idx = key_hash >> (32 - (map->map_bits + 1));
> > > > +
> > > > +   while (1) {
> > > > +   idx &= (map->map_size - 1);
> > > > +   entry = TRACING_MAP_ENTRY(map->map, idx);
> > > > +   test_key = entry->key;
> > > > +
> > > > +   if (test_key && test_key == key_hash && entry->val &&
> > > > +   keys_match(key, entry->val->key, map->key_size))
> > > > +   return entry->val;
> > > > +
> > > > +   if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> > > > +   struct tracing_map_elt *elt;
> > > > +
> > > > +   elt = get_free_elt(map);
> > > > +   if (!elt)
> > > > +   break;
> > > > +   memcpy(elt->key, key, map->key_size);
> > > > +   entry->val = elt;
> > > > +
> > > > +   return entry->val;
> > > > +   }
> > > > +   idx++;
> > > > +   }
> > > > +
> > > > +   return NULL;
> > > > +}
> > > 
> > > IIUC this always insert new entry if no matching key found.  And if
> > > the map is full, it only fails after walking through the entries to
> > > find an empty one, mark the entry 

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Namhyung Kim]

Hi Tom,

On Tue, Nov 03, 2015 at 07:47:52PM -0600, Tom Zanussi wrote:
> Hi Namhyung,
> 
> On Mon, 2015-11-02 at 16:08 +0900, Namhyung Kim wrote:
> > I thought it'd be better if users can see which one is the real drop
> > or not.  IOW if drop count is much smaller than the normal event
> > count, [s]he might want to ignore the occasional drops.  Otherwise,
> > [s]he should restart with a bigger table.  This requires accurate
> > counts of events and drops though.
> > 
> 
> OK, how about the below - it basically moves the drops set/test/inc into
> tracing_map_insert(), as well as a total hits count.  So those values
> will be available for users to use in deciding whether to use the data
> or restart with a bigger table, and the loop is bailed out of only if no
> matching keys are found and there are drops, so callers can continue
> updating existing entries.

But if a key didn't get a desired index, it'd still fail to update..


> 
> Users who want the original behavior still get the NULL return and can
> stop calling tracing_map_insert() as before:
> 
> struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void *key)
> {
> u32 idx, key_hash, test_key;
> struct tracing_map_entry *entry;
> 
> key_hash = jhash(key, map->key_size, 0);
> if (key_hash == 0)
> key_hash = 1;
> idx = key_hash >> (32 - (map->map_bits + 1));
> 
> while (1) {
> idx &= (map->map_size - 1);
> entry = TRACING_MAP_ENTRY(map->map, idx);
> test_key = entry->key;
> 
> if (test_key && test_key == key_hash && entry->val &&
> keys_match(key, entry->val->key, map->key_size)) {
> atomic64_inc(>hits);
> return entry->val;
> }
> 
> if (atomic64_read(>drops)) {
> atomic64_inc(>drops);
> break;
> }

IMHO it should be removed.

> 
> if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> struct tracing_map_elt *elt;
> 
> elt = get_free_elt(map);
> if (!elt) {
> atomic64_inc(>drops);

And reset entry->key here..

> break;
> }
> memcpy(elt->key, key, map->key_size);
> entry->val = elt;
> 
> atomic64_inc(>hits);
> return entry->val;
> }
> idx++;
> }
> 
> return NULL;
> }


Then tracing_map_lookup() can be implemented like *_insert but bail out
from the loop if test_key is 0.  The caller might do like this:

if (!atomic64_read(>drops))
elt = tracing_map_insert(...);
else
elt = tracing_map_lookup(...);

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

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

Hi Namhyung,

On Wed, 2015-11-04 at 11:26 +0900, Namhyung Kim wrote:
> Hi Tom,
> 
> On Tue, Nov 03, 2015 at 07:47:52PM -0600, Tom Zanussi wrote:
> > Hi Namhyung,
> > 
> > On Mon, 2015-11-02 at 16:08 +0900, Namhyung Kim wrote:
> > > I thought it'd be better if users can see which one is the real drop
> > > or not.  IOW if drop count is much smaller than the normal event
> > > count, [s]he might want to ignore the occasional drops.  Otherwise,
> > > [s]he should restart with a bigger table.  This requires accurate
> > > counts of events and drops though.
> > > 
> > 
> > OK, how about the below - it basically moves the drops set/test/inc into
> > tracing_map_insert(), as well as a total hits count.  So those values
> > will be available for users to use in deciding whether to use the data
> > or restart with a bigger table, and the loop is bailed out of only if no
> > matching keys are found and there are drops, so callers can continue
> > updating existing entries.
> 
> But if a key didn't get a desired index, it'd still fail to update..
> 
> 
> > 
> > Users who want the original behavior still get the NULL return and can
> > stop calling tracing_map_insert() as before:
> > 
> > struct tracing_map_elt *tracing_map_insert(struct tracing_map *map, void 
> > *key)
> > {
> > u32 idx, key_hash, test_key;
> > struct tracing_map_entry *entry;
> > 
> > key_hash = jhash(key, map->key_size, 0);
> > if (key_hash == 0)
> > key_hash = 1;
> > idx = key_hash >> (32 - (map->map_bits + 1));
> > 
> > while (1) {
> > idx &= (map->map_size - 1);
> > entry = TRACING_MAP_ENTRY(map->map, idx);
> > test_key = entry->key;
> > 
> > if (test_key && test_key == key_hash && entry->val &&
> > keys_match(key, entry->val->key, map->key_size)) {
> > atomic64_inc(>hits);
> > return entry->val;
> > }
> > 
> > if (atomic64_read(>drops)) {
> > atomic64_inc(>drops);
> > break;
> > }
> 
> IMHO it should be removed.
> 
> > 
> > if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> > struct tracing_map_elt *elt;
> > 
> > elt = get_free_elt(map);
> > if (!elt) {
> > atomic64_inc(>drops);
> 
> And reset entry->key here..
> 
> > break;
> > }
> > memcpy(elt->key, key, map->key_size);
> > entry->val = elt;
> > 
> > atomic64_inc(>hits);
> > return entry->val;
> > }
> > idx++;
> > }
> > 
> > return NULL;
> > }
> 
> 
> Then tracing_map_lookup() can be implemented like *_insert but bail out
> from the loop if test_key is 0.  The caller might do like this:
> 
>   if (!atomic64_read(>drops))
>   elt = tracing_map_insert(...);
>   else
>   elt = tracing_map_lookup(...);
> 

Yeah, I think that should work - let me try that in the next version...

Thanks,

Tom

> Thanks,
> Namhyung


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

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Namhyung Kim]

Hi Tom,

On Thu, Oct 29, 2015 at 01:35:43PM -0500, Tom Zanussi wrote:
> Hi Namhyung,
> 
> On Thu, 2015-10-29 at 17:31 +0900, Namhyung Kim wrote:
> > Hi Tom,
> > 
> > On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> > > 
> > > Signed-off-by: Tom Zanussi 
> > > Tested-by: Masami Hiramatsu 
> > > ---
> > > +/**
> > > + * 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;
> > > + struct tracing_map_entry *entry;
> > > +
> > > + key_hash = jhash(key, map->key_size, 0);
> > > + if (key_hash == 0)
> > > + key_hash = 1;
> > > + idx = key_hash >> (32 - (map->map_bits + 1));
> > > +
> > > + while (1) {
> > > + idx &= (map->map_size - 1);
> > > + entry = TRACING_MAP_ENTRY(map->map, idx);
> > > + test_key = entry->key;
> > > +
> > > + if (test_key && test_key == key_hash && entry->val &&
> > > + keys_match(key, entry->val->key, map->key_size))
> > > + return entry->val;
> > > +
> > > + if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> > > + struct tracing_map_elt *elt;
> > > +
> > > + elt = get_free_elt(map);
> > > + if (!elt)
> > > + break;
> > > + memcpy(elt->key, key, map->key_size);
> > > + entry->val = elt;
> > > +
> > > + return entry->val;
> > > + }
> > > + idx++;
> > > + }
> > > +
> > > + return NULL;
> > > +}
> > 
> > IIUC this always insert new entry if no matching key found.  And if
> > the map is full, it only fails after walking through the entries to
> > find an empty one, mark the entry with the key and call to
> > get_free_elt() returns NULL.  As more key added, it worsenes the
> > problem since more entries will be marked with no value IMHO.
> > 
> > I can see you checked hist_data->drops in the next patch to work
> > around this problem.  But IMHO it's suboptimal since it cannot update
> > the existing entries too.  I think it'd be better having lookup-only
> > version of this function and use it after it sees drops.  The lookup
> > function can bail out from the loop 

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Namhyung Kim]

Hi Tom,

On Thu, Oct 29, 2015 at 01:35:43PM -0500, Tom Zanussi wrote:
> Hi Namhyung,
> 
> On Thu, 2015-10-29 at 17:31 +0900, Namhyung Kim wrote:
> > Hi Tom,
> > 
> > On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> > > 
> > > Signed-off-by: Tom Zanussi 
> > > Tested-by: Masami Hiramatsu 
> > > ---
> > > +/**
> > > + * 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;
> > > + struct tracing_map_entry *entry;
> > > +
> > > + key_hash = jhash(key, map->key_size, 0);
> > > + if (key_hash == 0)
> > > + key_hash = 1;
> > > + idx = key_hash >> (32 - (map->map_bits + 1));
> > > +
> > > + while (1) {
> > > + idx &= (map->map_size - 1);
> > > + entry = TRACING_MAP_ENTRY(map->map, idx);
> > > + test_key = entry->key;
> > > +
> > > + if (test_key && test_key == key_hash && entry->val &&
> > > + keys_match(key, entry->val->key, map->key_size))
> > > + return entry->val;
> > > +
> > > + if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> > > + struct tracing_map_elt *elt;
> > > +
> > > + elt = get_free_elt(map);
> > > + if (!elt)
> > > + break;
> > > + memcpy(elt->key, key, map->key_size);
> > > + entry->val = elt;
> > > +
> > > + return entry->val;
> > > + }
> > > + idx++;
> > > + }
> > > +
> > > + return NULL;
> > > +}
> > 
> > IIUC this always insert new entry if no matching key found.  And if
> > the map is full, it only fails after walking through the entries to
> > find an empty one, mark the entry with the key and call to
> > get_free_elt() returns NULL.  As more key added, it worsenes the
> > problem since more entries will be marked with no value IMHO.
> > 
> > I can see you checked hist_data->drops in the next patch to work
> > around this problem.  But IMHO it's suboptimal since it cannot update
> > the existing entries too.  I think it'd be better having lookup-only
> > version of this function and use it after it 

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

Hi Namhyung,

On Thu, 2015-10-29 at 17:31 +0900, Namhyung Kim wrote:
> Hi Tom,
> 
> On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> > 
> > Signed-off-by: Tom Zanussi 
> > Tested-by: Masami Hiramatsu 
> > ---
> 
> [SNIP]
> > +void tracing_map_array_free(struct tracing_map_array *a)
> > +{
> > +   unsigned int i;
> > +
> > +   if (!a->pages)
> > +   return;
> 
> You need to free 'a' anyway..  Or did you want to check 'a' being NULL?
> 

Both, I think.  Thanks for pointing this out, will fix in the next
version.

> 
> > +
> > +   for (i = 0; i < a->n_pages; i++)
> > +   free_page((unsigned long)a->pages[i]);
> > +
> > +   kfree(a);
> > +}
> > +
> > +struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts,
> > + unsigned int entry_size)
> > +{
> > +   struct tracing_map_array *a;
> > +   unsigned int i;
> > +
> > +   a = kzalloc(sizeof(*a), GFP_KERNEL);
> > +   if (!a)
> > +   return NULL;
> > +
> > +   a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);
> > +   a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);
> > +   a->n_pages = n_elts / a->entries_per_page;
> > +   if (!a->n_pages)
> > +   a->n_pages = 1;
> > +   a->entry_shift = fls(a->entries_per_page) - 1;
> > +   a->entry_mask = (1 << a->entry_shift) - 1;
> > +
> > +   a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);
> > +   if (!a->pages)
> > +   goto free;
> > +
> > +   for (i = 0; i < a->n_pages; i++) {
> > +   a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);
> > +   if (!a->pages)
> 
>   if (!a->pages[i])
> 

And this obvious error too, thanks.

> 
> > +   goto free;
> > +   }
> > + out:
> > +   return a;
> > + free:
> > +   tracing_map_array_free(a);
> > +   a = NULL;
> > +
> > +   goto out;
> > +}
> > +
> 
> [SNIP]
> > +/**
> > + * 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;
> > +   struct tracing_map_entry *entry;
> > +
> > +   key_hash = jhash(key, map->key_size, 0);
> > +   if (key_hash == 0)
> > +   key_hash = 1;
> > +   idx = key_hash >> (32 - (map->map_bits + 1));
> > +
> > +   while (1) {
> > +   idx &= 

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Namhyung Kim]

Hi Tom,

On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> 
> Signed-off-by: Tom Zanussi 
> Tested-by: Masami Hiramatsu 
> ---

[SNIP]
> +void tracing_map_array_free(struct tracing_map_array *a)
> +{
> + unsigned int i;
> +
> + if (!a->pages)
> + return;

You need to free 'a' anyway..  Or did you want to check 'a' being NULL?


> +
> + for (i = 0; i < a->n_pages; i++)
> + free_page((unsigned long)a->pages[i]);
> +
> + kfree(a);
> +}
> +
> +struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts,
> +   unsigned int entry_size)
> +{
> + struct tracing_map_array *a;
> + unsigned int i;
> +
> + a = kzalloc(sizeof(*a), GFP_KERNEL);
> + if (!a)
> + return NULL;
> +
> + a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);
> + a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);
> + a->n_pages = n_elts / a->entries_per_page;
> + if (!a->n_pages)
> + a->n_pages = 1;
> + a->entry_shift = fls(a->entries_per_page) - 1;
> + a->entry_mask = (1 << a->entry_shift) - 1;
> +
> + a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);
> + if (!a->pages)
> + goto free;
> +
> + for (i = 0; i < a->n_pages; i++) {
> + a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);
> + if (!a->pages)

if (!a->pages[i])


> + goto free;
> + }
> + out:
> + return a;
> + free:
> + tracing_map_array_free(a);
> + a = NULL;
> +
> + goto out;
> +}
> +

[SNIP]
> +/**
> + * 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;
> + struct tracing_map_entry *entry;
> +
> + key_hash = jhash(key, map->key_size, 0);
> + if (key_hash == 0)
> + key_hash = 1;
> + idx = key_hash >> (32 - (map->map_bits + 1));
> +
> + while (1) {
> + idx &= (map->map_size - 1);
> + entry = TRACING_MAP_ENTRY(map->map, idx);
> + test_key = entry->key;
> +
> + if (test_key && test_key == key_hash && entry->val &&
> + keys_match(key, entry->val->key, map->key_size))
> + return entry->val;
> +
> + if (!test_key && !cmpxchg(>key, 0, key_hash)) {
> +

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

Hi Namhyung,

On Thu, 2015-10-29 at 17:31 +0900, Namhyung Kim wrote:
> Hi Tom,
> 
> On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> > 
> > Signed-off-by: Tom Zanussi 
> > Tested-by: Masami Hiramatsu 
> > ---
> 
> [SNIP]
> > +void tracing_map_array_free(struct tracing_map_array *a)
> > +{
> > +   unsigned int i;
> > +
> > +   if (!a->pages)
> > +   return;
> 
> You need to free 'a' anyway..  Or did you want to check 'a' being NULL?
> 

Both, I think.  Thanks for pointing this out, will fix in the next
version.

> 
> > +
> > +   for (i = 0; i < a->n_pages; i++)
> > +   free_page((unsigned long)a->pages[i]);
> > +
> > +   kfree(a);
> > +}
> > +
> > +struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts,
> > + unsigned int entry_size)
> > +{
> > +   struct tracing_map_array *a;
> > +   unsigned int i;
> > +
> > +   a = kzalloc(sizeof(*a), GFP_KERNEL);
> > +   if (!a)
> > +   return NULL;
> > +
> > +   a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);
> > +   a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);
> > +   a->n_pages = n_elts / a->entries_per_page;
> > +   if (!a->n_pages)
> > +   a->n_pages = 1;
> > +   a->entry_shift = fls(a->entries_per_page) - 1;
> > +   a->entry_mask = (1 << a->entry_shift) - 1;
> > +
> > +   a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);
> > +   if (!a->pages)
> > +   goto free;
> > +
> > +   for (i = 0; i < a->n_pages; i++) {
> > +   a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);
> > +   if (!a->pages)
> 
>   if (!a->pages[i])
> 

And this obvious error too, thanks.

> 
> > +   goto free;
> > +   }
> > + out:
> > +   return a;
> > + free:
> > +   tracing_map_array_free(a);
> > +   a = NULL;
> > +
> > +   goto out;
> > +}
> > +
> 
> [SNIP]
> > +/**
> > + * 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;
> > +   struct tracing_map_entry *entry;
> > +
> > +   key_hash = jhash(key, map->key_size, 0);
> > +   if (key_hash == 0)
> > +   key_hash = 1;
> > +   idx = key_hash >> (32 - (map->map_bits + 1));

Re: [PATCH v11 08/28] tracing: Add lock-free tracing_map

[Namhyung Kim]

Hi Tom,

On Thu, Oct 22, 2015 at 01:14:12PM -0500, 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
> 
> Signed-off-by: Tom Zanussi 
> Tested-by: Masami Hiramatsu 
> ---

[SNIP]
> +void tracing_map_array_free(struct tracing_map_array *a)
> +{
> + unsigned int i;
> +
> + if (!a->pages)
> + return;

You need to free 'a' anyway..  Or did you want to check 'a' being NULL?


> +
> + for (i = 0; i < a->n_pages; i++)
> + free_page((unsigned long)a->pages[i]);
> +
> + kfree(a);
> +}
> +
> +struct tracing_map_array *tracing_map_array_alloc(unsigned int n_elts,
> +   unsigned int entry_size)
> +{
> + struct tracing_map_array *a;
> + unsigned int i;
> +
> + a = kzalloc(sizeof(*a), GFP_KERNEL);
> + if (!a)
> + return NULL;
> +
> + a->entry_size_shift = fls(roundup_pow_of_two(entry_size) - 1);
> + a->entries_per_page = PAGE_SIZE / (1 << a->entry_size_shift);
> + a->n_pages = n_elts / a->entries_per_page;
> + if (!a->n_pages)
> + a->n_pages = 1;
> + a->entry_shift = fls(a->entries_per_page) - 1;
> + a->entry_mask = (1 << a->entry_shift) - 1;
> +
> + a->pages = kcalloc(a->n_pages, sizeof(void *), GFP_KERNEL);
> + if (!a->pages)
> + goto free;
> +
> + for (i = 0; i < a->n_pages; i++) {
> + a->pages[i] = (void *)get_zeroed_page(GFP_KERNEL);
> + if (!a->pages)

if (!a->pages[i])


> + goto free;
> + }
> + out:
> + return a;
> + free:
> + tracing_map_array_free(a);
> + a = NULL;
> +
> + goto out;
> +}
> +

[SNIP]
> +/**
> + * 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;
> + struct tracing_map_entry *entry;
> +
> + key_hash = jhash(key, map->key_size, 0);
> + if (key_hash == 0)
> + key_hash = 1;
> + idx = key_hash >> (32 - (map->map_bits + 1));
> +
> + while (1) {
> + idx &= (map->map_size - 1);
> + entry = TRACING_MAP_ENTRY(map->map, idx);
> + test_key = entry->key;
> +
> + if (test_key && test_key == key_hash && entry->val &&
> + keys_match(key, entry->val->key, map->key_size))
> + return entry->val;
> +
> +  

[PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

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

Signed-off-by: Tom Zanussi 
Tested-by: Masami Hiramatsu 
---
 kernel/trace/Kconfig   |   13 +
 kernel/trace/Makefile  |1 +
 kernel/trace/tracing_map.c | 1005 
 kernel/trace/tracing_map.h |  277 
 4 files changed, 1296 insertions(+)
 create mode 100644 kernel/trace/tracing_map.c
 create mode 100644 kernel/trace/tracing_map.h

diff --git a/kernel/trace/Kconfig b/kernel/trace/Kconfig
index 8d6363f..0c61e98 100644
--- a/kernel/trace/Kconfig
+++ b/kernel/trace/Kconfig
@@ -528,6 +528,19 @@ config MMIOTRACE
  See Documentation/trace/mmiotrace.txt.
  If you are not helping to develop drivers, say N.
 
+config TRACING_MAP
+   bool
+   depends on ARCH_HAVE_NMI_SAFE_CMPXCHG
+   default n
+   help
+ tracing_map is a special-purpose lock-free map for tracing,
+ separated out as a stand-alone facility in order to allow it
+ to be shared between multiple tracers.  It isn't meant to be
+ generally used outside of that context, and is normally
+ selected by tracers that use it.
+
+ If in doubt, say N.
+
 config MMIOTRACE_TEST
tristate "Test module for mmiotrace"
depends on MMIOTRACE && m
diff --git a/kernel/trace/Makefile b/kernel/trace/Makefile
index 9b1044e..4255c40 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_MAP) += 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 000..c67ef12
--- /dev/null
+++ b/kernel/trace/tracing_map.c
@@ -0,0 +1,1005 @@
+/*
+ * 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 
+ *
+ * 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 
+#include 
+#include 
+#include 
+
+#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, >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(>fields[i].sum);
+}
+
+int 

[PATCH v11 08/28] tracing: Add lock-free tracing_map

[Tom Zanussi]

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

Signed-off-by: Tom Zanussi 
Tested-by: Masami Hiramatsu 
---
 kernel/trace/Kconfig   |   13 +
 kernel/trace/Makefile  |1 +
 kernel/trace/tracing_map.c | 1005 
 kernel/trace/tracing_map.h |  277 
 4 files changed, 1296 insertions(+)
 create mode 100644 kernel/trace/tracing_map.c
 create mode 100644 kernel/trace/tracing_map.h

diff --git a/kernel/trace/Kconfig b/kernel/trace/Kconfig
index 8d6363f..0c61e98 100644
--- a/kernel/trace/Kconfig
+++ b/kernel/trace/Kconfig
@@ -528,6 +528,19 @@ config MMIOTRACE
  See Documentation/trace/mmiotrace.txt.
  If you are not helping to develop drivers, say N.
 
+config TRACING_MAP
+   bool
+   depends on ARCH_HAVE_NMI_SAFE_CMPXCHG
+   default n
+   help
+ tracing_map is a special-purpose lock-free map for tracing,
+ separated out as a stand-alone facility in order to allow it
+ to be shared between multiple tracers.  It isn't meant to be
+ generally used outside of that context, and is normally
+ selected by tracers that use it.
+
+ If in doubt, say N.
+
 config MMIOTRACE_TEST
tristate "Test module for mmiotrace"
depends on MMIOTRACE && m
diff --git a/kernel/trace/Makefile b/kernel/trace/Makefile
index 9b1044e..4255c40 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_MAP) += 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 000..c67ef12
--- /dev/null
+++ b/kernel/trace/tracing_map.c
@@ -0,0 +1,1005 @@
+/*
+ * 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 
+ *
+ * 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 
+#include 
+#include 
+#include 
+
+#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, >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