Re: [PATCH v2 02/40] tracing: Add support to detect and avoid duplicates

[Patel, Vedang]

On Wed, 2017-09-06 at 14:47 -0400, Steven Rostedt wrote:
> On Tue,ÂÂ5 Sep 2017 16:57:14 -0500
> Tom Zanussi <tom.zanussi@xxxxxxxxxxxxxxx> wrote:
> 
> 
> > 
> > diff --git a/kernel/trace/tracing_map.c
> > b/kernel/trace/tracing_map.c
> > index 305039b..437b490 100644
> > --- a/kernel/trace/tracing_map.c
> > +++ b/kernel/trace/tracing_map.c
> > @@ -414,6 +414,7 @@ static inline bool keys_match(void *key, void
> > *test_key, unsigned key_size)
> > Â__tracing_map_insert(struct tracing_map *map, void *key, bool
> > lookup_only)
> > Â{
> > Â	u32 idx, key_hash, test_key;
> > +	int dup_try = 0;
> > Â	struct tracing_map_entry *entry;
> > Â
> > Â	key_hash = jhash(key, map->key_size, 0);
> > @@ -426,10 +427,31 @@ static inline bool keys_match(void *key, void
> > *test_key, unsigned key_size)
> > Â		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(&map->hits);
> > -			return entry->val;
> > +		if (test_key && test_key == key_hash) {
> > +			if (entry->val &&
> > +			ÂÂÂÂkeys_match(key, entry->val->key, map-
> > >key_size)) {
> > +				atomic64_inc(&map->hits);
> > +				return entry->val;
> > +			} else if (unlikely(!entry->val)) {
> I'm thinking we need a READ_ONCE() here.
> 
> 		val = READ_ONCE(entry->val);
> 
> then use "val" instead of entry->val. Otherwise, wont it be possible
> if two tasks are inserting at the same time, to have this:
> 
> (Using reg as when the value is read into a register from memory)
> 
> 	CPU0			CPU1
> 	----			----
> Âreg = entry->val
> Â(reg == zero)
> 
> 			ÂÂÂentry->val = elt;
> 
> Âkeys_match(key, reg)
> Â(false)
> 
> Âreg = entry->val
> Â(reg = elt)
> 
> Âif (unlikely(!reg))
> 
> Causes the if to fail.
> 
> A READ_ONCE(), would make sure the entry->val used to test against
> key
> would also be the same value used to test if it is zero.
> 
Hi Steve,Â

Thanks for the input.Â

I agree with your change. Adding READ_ONCE will avoid a race condition
which might result in adding duplicates. Will add it in the next
version.

-Vedang
> -- Steve
> 
> 
> 
> > 
> > +				/*
> > +				Â* The key is present. But, val
> > (pointer to elt
> > +				Â* struct) is still NULL. which
> > means some other
> > +				Â* thread is in the process of
> > inserting an
> > +				Â* element.
> > +				Â*
> > +				Â* On top of that, it's key_hash
> > is same as the
> > +				Â* one being inserted right now.
> > So, it's
> > +				Â* possible that the element has
> > the same
> > +				Â* key as well.
> > +				Â*/
> > +
> > +				dup_try++;
> > +				if (dup_try > map->map_size) {
> > +					atomic64_inc(&map->drops);
> > +					break;
> > +				}
> > +				continue;
> > +			}
> > Â		}
> > Â
> > Â		if (!test_key) {
> > @@ -451,6 +473,13 @@ static inline bool keys_match(void *key, void
> > *test_key, unsigned key_size)
> > Â				atomic64_inc(&map->hits);
> > Â
> > Â				return entry->val;
> > +			} else {
> > +				/*
> > +				Â* cmpxchg() failed. Loop around
> > once
> > +				Â* more to check what key was
> > inserted.
> > +				Â*/
> > +				dup_try++;
> > +				continue;
> > Â			}
> > Â		}
> > Â