LKML Archive on lore.kernel.org
 help / color / Atom feed
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
To: linux-kernel@vger.kernel.org, c++std-parallel@accu.org,
	linux-arch@vger.kernel.org, gcc@gcc.gnu.org
Cc: Peter.Sewell@cl.cam.ac.uk, torvalds@linux-foundation.org,
	Mark.Batty@cl.cam.ac.uk, peterz@infradead.org,
	will.deacon@arm.com, Ramana.Radhakrishnan@arm.com,
	dhowells@redhat.com, akpm@linux-foundation.org, mingo@kernel.org,
	michaelw@ca.ibm.com
Subject: Compilers and RCU readers: Once more unto the breach!
Date: Tue, 19 May 2015 17:55:10 -0700
Message-ID: <20150520005510.GA23559@linux.vnet.ibm.com> (raw)

Hello!

Following up on last year's discussion (https://lwn.net/Articles/586838/,
https://lwn.net/Articles/588300/), I believe that we have a solution.  If
I am wrong, I am sure you all will let me know, and in great detail.  ;-)

The key simplification is to "just say no" to RCU-protected array indexes:
https://lkml.org/lkml/2015/5/12/827, as was suggested by several people.
This simplification means that rcu_dereference (AKA memory_order_consume)
need only return pointers.  This in ture avoids things like (x-x),
(x*0), and (x%1) because if "x" is a pointer, these expressions either
return non-pointers are compilation errors.  With a very few exceptions,
dependency chains can lead -to- non-pointers, but cannot pass -through-
them.

The result is that dependencies are carried only by operations for
which the compiler cannot easily optimize the away those dependencies,
these operations including simple assignment, integer offset (including
indexing), dereferencing, casts, passing as a function argument, return
values from functions and so on.  A complete list with commentary starts
on page 28 of:

	http://www.rdrop.com/users/paulmck/RCU/consume.2015.05.18a.pdf

Dependency chains are broken if a pointer compares equal to some other
pointer not part of the same dependency chain, if too many bits are ORed
onto or ANDed off of a intptr_t or uintptr_t, or if the dependency is
explicitly killed (which should now strictly speaking never be necessary,
but which might allow better diagnostics).  These are set out in more
detail on page 30 of the above PDF.

This covers all the uses in the Linux kernel that I am aware of without
any source-code changes (other than to the rcu_dereference() primitives
themselves) and should also work for compilers and standards.

Thoughts?

							Thanx, Paul


             reply index

Thread overview: 44+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-05-20  0:55 Paul E. McKenney [this message]
2015-05-20  1:57 ` Linus Torvalds
2015-05-20  2:10   ` Linus Torvalds
2015-05-20  2:41     ` Paul E. McKenney
2015-05-20 11:47       ` Will Deacon
2015-05-20 12:15         ` Paul E. McKenney
2015-05-20 15:46           ` Will Deacon
2015-05-20 15:54             ` Andrew Haley
2015-05-20 18:16               ` [c++std-parallel-1632] " Paul E. McKenney
2015-05-21 14:22                 ` Michael Matz
2015-05-21 15:10                   ` Paul E. McKenney
2015-05-21 16:17                     ` Michael Matz
2015-05-21 18:37                       ` Paul E. McKenney
2015-05-20 18:16             ` Paul E. McKenney
2015-05-21 19:24               ` Will Deacon
2015-05-21 20:02                 ` Paul E. McKenney
2015-05-21 20:42                   ` Linus Torvalds
2015-05-21 22:02                     ` Paul E. McKenney
2015-05-22  6:43                     ` Ingo Molnar
2015-05-22 10:43                       ` Richard Kenner
2015-05-22 13:11                         ` Paul E. McKenney
2015-05-22 13:12                       ` Paul E. McKenney
2015-05-26 17:37                     ` [c++std-parallel-1641] " Torvald Riegel
2015-05-22 17:30                   ` Will Deacon
2015-05-22 18:55                     ` Paul E. McKenney
2015-05-20 13:18         ` David Howells
2015-05-20 13:30           ` Paul E. McKenney
2015-05-20 13:37           ` David Howells
2015-05-20 13:44             ` Ramana Radhakrishnan
2015-05-20 14:03               ` Paul E. McKenney
2015-05-20 14:15                 ` Ramana Radhakrishnan
2015-05-20 15:12                   ` Paul E. McKenney
2015-05-20 15:46                   ` David Howells
2015-05-20 14:02             ` [c++std-parallel-1624] " Paul E. McKenney
2015-05-20  2:34   ` Paul E. McKenney
2015-05-20  7:34     ` [c++std-parallel-1614] " Jens Maurer
2015-05-20  9:03       ` Richard Biener
2015-05-20 12:02         ` Paul E. McKenney
2015-05-20 12:01       ` [c++std-parallel-1616] " Paul E. McKenney
2015-05-26 17:08 ` [c++std-parallel-1611] " Torvald Riegel
2015-05-27  1:41   ` [c++std-parallel-1651] " Paul E. McKenney
2015-07-14  0:44 ` Paul E. McKenney
2015-09-22 17:00   ` Paul E. McKenney
     [not found]     ` <CAPUmR1aqV_cQWjE8qC9x2sfmW-1ocKKMtCgNbjZH0cJ-AO2WTg@mail.gmail.com>
2015-09-23 23:26       ` [c++std-parallel-2008] " Paul E. McKenney

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20150520005510.GA23559@linux.vnet.ibm.com \
    --to=paulmck@linux.vnet.ibm.com \
    --cc=Mark.Batty@cl.cam.ac.uk \
    --cc=Peter.Sewell@cl.cam.ac.uk \
    --cc=Ramana.Radhakrishnan@arm.com \
    --cc=akpm@linux-foundation.org \
    --cc=c++std-parallel@accu.org \
    --cc=dhowells@redhat.com \
    --cc=gcc@gcc.gnu.org \
    --cc=linux-arch@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=michaelw@ca.ibm.com \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=torvalds@linux-foundation.org \
    --cc=will.deacon@arm.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lore.kernel.org/lkml/8 lkml/git/8.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git