lkml.org 
[lkml]   [2014]   [Feb]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC][PATCH 0/5] arch: atomic rework
On Sat, Feb 22, 2014 at 01:53:30PM -0800, Linus Torvalds wrote:
> On Sat, Feb 22, 2014 at 10:53 AM, Torvald Riegel <triegel@redhat.com> wrote:
> >
> > Stating that (1) "the standard is wrong" and (2) that you think that
> > mo_consume semantics are not good is two different things.
>
> I do agree. They are two independent things.
>
> I think the standard is wrong, because it's overly complex, hard to
> understand, and nigh unimplementable. As shown by the bugzilla
> example, "carries a dependency" encompasses things that are *not* just
> synchronizing things just through a pointer, and as a result it's
> actually very complicated, since they could have been optimized away,
> or done in non-local code that wasn't even aware of the dependency
> carrying.
>
> That said, I'm reconsidering my suggested stricter semantics, because
> for RCU we actually do want to test the resulting pointer against NULL
> _without_ any implied serialization.
>
> So I still feel that the standard as written is fragile and confusing
> (and the bugzilla entry pretty much proves that it is also practically
> unimplementable as written), but strengthening the serialization may
> be the wrong thing.
>
> Within the kernel, the RCU use for this is literally purely about
> loading a pointer, and doing either:
>
> - testing its value against NULL (without any implied synchronization at all)
>
> - using it as a pointer to an object, and expecting that any accesses
> to that object are ordered wrt the consuming load.

Agreed, by far the most frequent use is "->" to dereference and assignment
to store into a local variable. The other operations where the kernel
expects ordering to be maintained are:

o Bitwise "&" to strip off low-order bits. The FIB tree does
this, for example in fib_table_lookup() in net/ipv4/fib_trie.c.
The low-order bit is used to distinguish internal nodes from
leaves -- nodes and leaves are different types of structures.
(There are a few others.)

o Uses "?:" to substitute defaults in case of NULL pointers,
but ordering must be maintained in the non-default case.
Most, perhaps all, of these could be converted to "if" should
"?:" prove problematic.

o Addition and subtraction to adjust both pointers to and indexes
into RCU-protected arrays. There are not that many indexes,
and they could be converted to pointers, but the addition and
subtraction looks necessary in a some cases.

o Array indexing. The value from rcu_dereference() is used both
before and inside the "[]", interestingly enough.

o Casts along with unary "&" and "*".

That said, I did not see any code that dependended on ordering through
the function-call "()", boolean complement "!", comparison (only "=="
and "!="), logical operators ("&&" and "||"), and the "*", "/", and "%"
arithmetic operators.

> So I actually have a suggested *very* different model that people
> might find more acceptable.
>
> How about saying that the result of a "atomic_read(&a, mo_consume)" is
> required to be a _restricted_ pointer type, and that the consume
> ordering guarantees the ordering between that atomic read and the
> accesses to the object that the pointer points to.
>
> No "carries a dependency", no nothing.

In the case of arrays, the object that the pointer points to is
considered to be the full array, right?

> Now, there's two things to note in there:
>
> - the "restricted pointer" part means that the compiler does not need
> to worry about serialization to that object through other possible
> pointers - we have basically promised that the *only* pointer to that
> object comes from the mo_consume. So that part makes it clear that the
> "consume" ordering really only is valid wrt that particular pointer
> load.

That could work, though there are some cases where a multi-linked
structure is made visible using a single rcu_assign_pointer(), and
rcu_dereference() is used only for the pointer leading to that
multi-linked structure, not for the pointers among the elements
making up that structure. One way to handle this would be to
require rcu_dereference() to be used within the structure an well
as upon first traversal to the structure.

> - the "to the object that the pointer points to" makes it clear that
> you can't use the pointer to generate arbitrary other values and claim
> to serialize that way.
>
> IOW, with those alternate semantics, that gcc bugzilla example is
> utterly bogus, and a compiler can ignore it, because while it tries to
> synchronize through the "dependency chain" created with that "p-i+i"
> expression, that is completely irrelevant when you use the above rules
> instead.
>
> In the bugzilla example, the object that "*(p-i+i)" accesses isn't
> actually the object pointed to by the pointer, so no serialization is
> implied. And if it actually *were* to be the same object, because "p"
> happens to have the same value as "i", then the "restrict" part of the
> rule pops up and the compiler can again say that there is no ordering
> guarantee, since the programmer lied to it and used a restricted
> pointer that aliased with another one.
>
> So the above suggestion basically tightens the semantics of "consume"
> in a totally different way - it doesn't make it serialize more, in
> fact it weakens the serialization guarantees a lot, but it weakens
> them in a way that makes the semantics a lot simpler and clearer.

It does look simpler and does look like it handles a large fraction of
the Linux-kernel uses.

But now it is time for some bullshit syntax for the RCU-protected arrays
in the Linux kernel:

p = atomic_load_explicit(gp, memory_order_consume);
r1 = *p; /* Ordering maintained. */
r2 = p[5]; /* Ordering maintained? */
r3 = p + 5; /* Ordering maintained? */
n = get_an_index();
r4 = p[n]; /* Ordering maintained? */

If the answer to the three questions is "no", then perhaps some special
function takes care of accesses to RCU-protected arrays.

Thanx, Paul



\
 
 \ /
  Last update: 2014-02-23 02:21    [W:0.243 / U:0.316 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site