linux-kernel - Re: Possible lock-less list race in scheduler

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: <402283060.238174.1425652523685.JavaMail.zimbra@efficios.com>
Date:	Fri, 6 Mar 2015 14:35:23 +0000 (UTC)
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
Cc:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Huang Ying <ying.huang@...el.com>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	Lai Jiangshan <eag0628@...il.com>,
	Peter Zijlstra <peterz@...radead.org>,
	LKML <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...nel.org>,
	Steven Rostedt <rostedt@...dmis.org>
Subject: Re: Possible lock-less list race in scheduler_ipi()

----- Original Message -----
> From: "Linus Torvalds" <torvalds@...ux-foundation.org>
> To: "Mathieu Desnoyers" <mathieu.desnoyers@...icios.com>
> Cc: "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>, "Huang Ying" <ying.huang@...el.com>, "Lai Jiangshan"
> <laijs@...fujitsu.com>, "Lai Jiangshan" <eag0628@...il.com>, "Peter Zijlstra" <peterz@...radead.org>, "LKML"
> <linux-kernel@...r.kernel.org>, "Ingo Molnar" <mingo@...nel.org>, "Steven Rostedt" <rostedt@...dmis.org>
> Sent: Thursday, March 5, 2015 8:02:06 PM
> Subject: Re: Possible lock-less list race in scheduler_ipi()
> 
> On Thu, Mar 5, 2015 at 3:48 PM, Mathieu Desnoyers
> <mathieu.desnoyers@...icios.com> wrote:
> >
> > llist_next() is pretty simple:
> >
> > static inline struct llist_node *llist_next(struct llist_node *node)
> > {
> >         return node->next;
> > }
> >
> > It is so simple that I wonder if the compiler would be
> > within its rights to reorder the load of node->next
> > after some operations within ttwu_do_activate(), thus
> > causing corruption of this linked-list due to a
> > concurrent try_to_wake_up() performed by another core.
> >
> > Am I too paranoid about the possible compiler mishaps
> > there, or are my concerns justified ?
> 
> I *think* you are too paranoid, because that would be a major compiler
> bug anyway - gcc cannot reorder the load against anything that might
> be changing the value.  Which obviously includes calling non-inlined
> functions.
> 
> At least the code generation I see doesn't seem to say that gcc gets this
> wrong:
> 
>         ...
>         leaq    -32(%rbx), %rsi #, p
>         movq    (%rbx), %rbx    # MEM[(struct llist_node
> *)__mptr_19].next, __mptr
>         movq    %r12, %rdi      # tcp_ptr__,
>         call    ttwu_do_activate.constprop.85   #
>         ...
> 
> that "movq (%rbx), %rbx" is the "llist = llist_next(llist);" thing.

Indeed, the compiler should never reorder loads/stores from/to
same memory location from a program order POV. What I had in mind
is a bit more far-fetched though: it would involve having the compiler
reorder this load after a store to another memory location, which
would in turn allow another execution context (interrupt or thread)
to corrupt the list.

The assembly snippet you show above appears to be OK. However, another
compiler may choose to inline ttwu_do_activate, leaving room for
more aggressive optimizations.

But I agree that it is rather far-fetched.

Thanks,

Mathieu


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