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

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1504731482.21216.8.camel@intel.com>
Date:   Wed, 6 Sep 2017 20:58:03 +0000
From:   "Patel, Vedang" <vedang.patel@...el.com>
To:     "rostedt@...dmis.org" <rostedt@...dmis.org>,
        "tom.zanussi@...ux.intel.com" <tom.zanussi@...ux.intel.com>
CC:     "bigeasy@...utronix.de" <bigeasy@...utronix.de>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "tglx@...utronix.de" <tglx@...utronix.de>,
        "namhyung@...nel.org" <namhyung@...nel.org>,
        "joelaf@...gle.com" <joelaf@...gle.com>,
        "mhiramat@...nel.org" <mhiramat@...nel.org>,
        "linux-rt-users@...r.kernel.org" <linux-rt-users@...r.kernel.org>,
        "mathieu.desnoyers@...icios.com" <mathieu.desnoyers@...icios.com>,
        "joel.opensrc@...il.com" <joel.opensrc@...il.com>,
        "Liu, Baohong" <baohong.liu@...el.com>
Subject: 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@...ux.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;
> >  			}
> >  		}
> >