Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1727016 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v2 02/40] tracing: Add support to detect and avoid duplicates Tom Zanussi <tom.zanussi@linux.intel.com> - 2017-09-06 00:00 +0200
    Re: [PATCH v2 02/40] tracing: Add support to detect and avoid  duplicates Steven Rostedt <rostedt@goodmis.org> - 2017-09-06 20:40 +0200
    Re: [PATCH v2 02/40] tracing: Add support to detect and avoid  duplicates Steven Rostedt <rostedt@goodmis.org> - 2017-09-06 20:50 +0200
      Re: [PATCH v2 02/40] tracing: Add support to detect and avoid  duplicates "Patel, Vedang" <vedang.patel@intel.com> - 2017-09-06 23:00 +0200

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

From: Vedang Patel <vedang.patel@intel.com>

A duplicate in the tracing_map hash table is when 2 different entries
have the same key and, as a result, the key_hash. This is possible due
to a race condition in the algorithm. This race condition is inherent to
the algorithm and not a bug. This was fine because, until now, we were
only interested in the sum of all the values related to a particular
key (the duplicates are dealt with in tracing_map_sort_entries()). But,
with the inclusion of variables[1], we are interested in individual
values. So, it will not be clear what value to choose when
there are duplicates. So, the duplicates need to be removed.

The duplicates can occur in the code in the following scenarios:

- A thread is in the process of adding a new element. It has
successfully executed cmpxchg() and inserted the key. But, it is still
not done acquiring the trace_map_elt struct, populating it and storing
the pointer to the struct in the value field of tracing_map hash table.
If another thread comes in at this time and wants to add an element with
the same key, it will not see the current element and add a new one.

- There are multiple threads trying to execute cmpxchg at the same time,
one of the threads will succeed and the others will fail. The ones which
fail will go ahead increment 'idx' and add a new element there creating
a duplicate.

This patch detects and avoids the first condition by asking the thread
which detects the duplicate to loop one more time. There is also a
possibility of infinite loop if the thread which is trying to insert
goes to sleep indefinitely and the one which is trying to insert a new
element detects a duplicate. Which is why, the thread loops for
map_size iterations before returning NULL.

The second scenario is avoided by preventing the threads which failed
cmpxchg() from incrementing idx. This way, they will loop
around and check if the thread which succeeded in executing cmpxchg()
had the same key.

[1] - https://lkml.org/lkml/2017/6/26/751

Signed-off-by: Vedang Patel <vedang.patel@intel.com>
---
 kernel/trace/tracing_map.c | 37 +++++++++++++++++++++++++++++++++----
 1 file changed, 33 insertions(+), 4 deletions(-)

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)) {
+				/*
+				 * 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;
 			}
 		}
 
-- 
1.9.3

[toc] | [next] | [standalone]

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

On Tue,  5 Sep 2017 16:57:14 -0500
Tom Zanussi <tom.zanussi@linux.intel.com> wrote:

> From: Vedang Patel <vedang.patel@intel.com>
> 
> A duplicate in the tracing_map hash table is when 2 different entries
> have the same key and, as a result, the key_hash. This is possible due
> to a race condition in the algorithm. This race condition is inherent to
> the algorithm and not a bug. This was fine because, until now, we were
> only interested in the sum of all the values related to a particular
> key (the duplicates are dealt with in tracing_map_sort_entries()). But,
> with the inclusion of variables[1], we are interested in individual
> values. So, it will not be clear what value to choose when
> there are duplicates. So, the duplicates need to be removed.
> 


> [1] - https://lkml.org/lkml/2017/6/26/751

FYI, something like this should have:

Link: http://lkml.kernel.org/r/cover.1498510759.git.tom.zanussi@linux.intel.com

And avoid any non kernel.org archiving system.

-- Steve

> 
> Signed-off-by: Vedang Patel <vedang.patel@intel.com>
> ---
>

[toc] | [prev] | [next] | [standalone]

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

On Tue,  5 Sep 2017 16:57:14 -0500
Tom Zanussi <tom.zanussi@linux.intel.com> 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.

-- 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;
>  			}
>  		}
>  

[toc] | [prev] | [next] | [standalone]

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

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@linux.intel.com> 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;
> >  			}
> >  		}
> >  

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web