linux-kernel - Further adventures of rcu_dereference() and the C standard

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>] [day] [month] [year] [list]

Date:	Fri, 24 Oct 2014 16:39:22 -0700
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	linux-kernel@...r.kernel.org
Cc:	torvalds@...ux-foundation.org, dhowells@...hat.com,
	linux@...izon.com, joseph@...esourcery.com, law@...hat.com,
	matz@...e.de, peterz@...radead.org, will.deacon@....com,
	corbet@....net
Subject: Further adventures of rcu_dereference() and the C standard

Hello!

Just a follow-up on the spirited LKML thread last February
(http://lwn.net/Articles/586838/, https://lwn.net/Articles/588300/).

Although we don't yet have anything resembling full solution, there has
been some good progress, which is documented in SC22/WG21 document N4215.
The official copy is at:

	http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4215.pdf

If you have trouble accessing it, here is a copy on my web site:

	http://www2.rdrop.com/users/paulmck/RCU/consume.2014.10.11a.pdf

The table on page 23 shows the current state.  To satisfy the key players,
we need "dep" in the "Dependency Type" column, either blank or "k" in
the "End-of-Chain Handling" column, and blank everywhere else.  As you
can see, none of the current proposals make the cut.  On the other hand,
we do at least have a variety of proposals.

The key players are as follows:

1.	The Linux kernel community.
2.	The compiler writers.
3.	The standards committee.
4.	Selected theorists (we need them for analysis tools).

We should also spare a thought for other communities using or that might
use RCU.

My current focus is to see if there is something that can be done to make
"sdep" rather than "dep" acceptable to the theorists.  The "dep" is a
simple syntactic dependency, similar to "carries a dependency" in C11.
In contrast, "sdep" is a semantic dependency, which requires that there
be some values at the head of the dependency chain that cause different
values to appear at the tail of that same chain.  This motivates a detour
through the "out of thin air" (OOTA) problem, which the Java guys have
been beating their heads against for more than ten years and which was
the subject of a meeting in Cambridge UK at the end of last month.
Several of us think we might have a way to make this work, but also
requires semantic rather than simple syntactic dependencies.  For the
sufficiently masochistic, the current state of OOTA is here:

	http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4216.html

If you have trouble accessing it, here is a copy on my web site:

	http://www.rdrop.com/users/paulmck/scalability/paper/OOTA.2014.10.10a.html

So no solution yet, but hopefully getting there.  Next step is the C++
standards committee meeting at UIUC the first full week of November.

							Thanx, Paul

--
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/