Fences

[Doug Lea]

One of the last tasks in JDK7 integration is to finalize
the Fences API in light of various unresolved discussions,
most of which surround the ugly names, awkward usages,
and unwanted implications about mappings to hardware.
(Thanks in particular to Jeremy Manson for not letting
up on this!)

I placed javadocs for one possible alternative, currently
just named "FencesV2" at:
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html

Reactions would be welcome.

It differs in naming (for example "orderWrites" rather
than "preStoreFence") as well as typical usage -- by returning
the associated references, they may encourage a simpler
usage style. On the other hand, without those ugly
"pre"/"post" prefixes built into their names, they
might be more misusable.

This version also has more complete specs (although
still in need of further review) that are more clearly
tied to JLS chapter 17 terminology.

-Doug


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Christian Vest Hansen]

I like the wording better in this one. Especially the informal
phrasings and the new method names. It also made the examples clearer.

I spotted some typos (minor stuff because this is what happens to jump
out at me):
   "r2 is contrained by w" in the orderReads doc is missing an 's'
   "nonnull" vs "non-null"
   missing space in "w such thatdereferences(ref, w)" in orderWrites doc
   should @return docs not end with a period?
   "--" vs "—" or "–"
   perhaps "c.getData()" (an the like) should be in a {@code } ?
   do the sentence "(In practice, among other changes, you would use
access methods instead of a public field)." really need that
parenthesis?



On Fri, Aug 7, 2009 at 2:51 PM, Doug Lea<dl@...> wrote:

>
> One of the last tasks in JDK7 integration is to finalize
> the Fences API in light of various unresolved discussions,
> most of which surround the ugly names, awkward usages,
> and unwanted implications about mappings to hardware.
> (Thanks in particular to Jeremy Manson for not letting
> up on this!)
>
> I placed javadocs for one possible alternative, currently
> just named "FencesV2" at:
> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html
>
> Reactions would be welcome.
>
> It differs in naming (for example "orderWrites" rather
> than "preStoreFence") as well as typical usage -- by returning
> the associated references, they may encourage a simpler
> usage style. On the other hand, without those ugly
> "pre"/"post" prefixes built into their names, they
> might be more misusable.
>
> This version also has more complete specs (although
> still in need of further review) that are more clearly
> tied to JLS chapter 17 terminology.
>
> -Doug
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

--
Venlig hilsen / Kind regards,
Christian Vest Hansen.
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Christian Vest Hansen wrote:
> I spotted some typos (minor stuff because this is what happens to jump
> out at me):

Thanks! These are fixed in the regenerated version
(http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html)

-Doug




_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Endre Stølsvik-6]

On Fri, Aug 7, 2009 at 14:51, Doug Lea <dl@...> wrote:

It differs in naming (for example "orderWrites" rather
than "preStoreFence") as well as typical usage -- by returning
the associated references, they may encourage a simpler
usage style. On the other hand, without those ugly
"pre"/"post" prefixes built into their names, they
might be more misusable.

What about sticking "Before" and "After" after the method names you suggest? Unless one use these methods very often (which I understad most won't), I believe those pre of postfixes will be helpful for ones memory.

Endre.

 

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Sam Berlin]

I do not profess any knowledge of the Fences API other than the most basic cursory knowledge from reading posts on this list... but along the lines of 'before' & 'after', what about: orderEarlierWrites, orderLaterReads, etc..

Sam

2009/8/7 Endre Stølsvik <Online@...>

On Fri, Aug 7, 2009 at 14:51, Doug Lea <dl@...> wrote:

It differs in naming (for example "orderWrites" rather
than "preStoreFence") as well as typical usage -- by returning
the associated references, they may encourage a simpler
usage style. On the other hand, without those ugly
"pre"/"post" prefixes built into their names, they
might be more misusable.

What about sticking "Before" and "After" after the method names you suggest? Unless one use these methods very often (which I understad most won't), I believe those pre of postfixes will be helpful for ones memory.

Endre.

 

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Sam Berlin wrote:
> I do not profess any knowledge of the Fences API other than the most
> basic cursory knowledge from reading posts on this list... but along the
> lines of 'before' & 'after', what about: orderEarlierWrites,
> orderLaterReads, etc..
>

One of the challenges in specs associated with memory models
is that there are many ordering relations, none of them
exactly corresponding to everyday terms. The current
specs use "prior" and "subsequent" with respect to
program order, which is probably the most common.
But to make methods self-documenting, you'd need to
create method names like: orderPriorWritesBeforeSubsequentWrites.
It seems marginally better to omit the adjectives
(which I did in FencesV2). Or use names like "preStoreFence"
(as in initial version) that don't have much meaning in
themselves, but have names that tell you where to place them.

-Doug
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Sam Berlin]

Longer names might actually be a good choice, if only because a name like "orderWrites" sounds a lot more simple than a name like "orderPriorWritesBeforeSubsequentWrites".  The long name gives some explanation of what's it going to do as well as sounding imposing.  "orderWrites" by itself gives some explanation, but seems so simple that people might mistake the way it's used or what it's supposed to do.  Conversely, "preStoreFence" sounds imposing, but doesn't give much explanation by itself.  The long name seems like a good middle ground.

(Of course, I don't see myself ever actually using the API... so these comments should be taken with a grain of salt.)

Sam

On Fri, Aug 7, 2009 at 12:06 PM, Doug Lea <dl@...> wrote:

Sam Berlin wrote:

I do not profess any knowledge of the Fences API other than the most basic cursory knowledge from reading posts on this list... but along the lines of 'before' & 'after', what about: orderEarlierWrites, orderLaterReads, etc..

One of the challenges in specs associated with memory models
is that there are many ordering relations, none of them
exactly corresponding to everyday terms. The current
specs use "prior" and "subsequent" with respect to
program order, which is probably the most common.
But to make methods self-documenting, you'd need to
create method names like: orderPriorWritesBeforeSubsequentWrites.
It seems marginally better to omit the adjectives
(which I did in FencesV2). Or use names like "preStoreFence"
(as in initial version) that don't have much meaning in
themselves, but have names that tell you where to place them.

-Doug

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Boehm, Hans]

Doug -

[Copying Paul McKenney, who should look at the appended message first.]

This is an improvement, but I still have some serious issues:

0. I'm fine with reachabilityFence, except for the "undefined behavior" statement.
I don't think you can do that in Java, since it destroys any hope of proving
security properties, right?  Untrusted, sandboxed code can always execute
reachabilityFence(null), and we presumably have to not allow that to do anything bad.
Requiring it to be a no-op seems fine, and doesn't slow down the obvious implementation.

1. I'm really confused by the more formal specifications.  Some of the issues there are superficial:  the orderReads specification seems to introduce constraints on a variable r that's never used.  There seems to be at least one critical typo in 17.5.1 in the definition of a dereference chain (the spurious(?) r before "dereferences(r, a)").  I don't see any obvious way to correct the latter to turn this into a proper mathematical definition of a relation, though I can sort of guess what was intended.  (I thought the earlier version of this from Jeremey looked OK.)  If we're going to use this, I'd repeat a demangled version of the definition.  Maybe the correct version is:

For a read action r, and an action a that reads or writes object o in thread t, dereferences(r, a) holds iff t did not initialize o, and a accesses the object (o)
returned by r.

Did I get that approximately correct?

2.  I still don't see how you could possibly emulate final fields without also requiring a fence on the reader side, or effectively constraining the implementation of ordinary reads.  Java implementations are only required to preserve data-dependency ordering for final fields.  For other fields, I believe an access to x.a may still appear to happen before the access to x.  It may be that this freedom is not important for any up-to-date implementations.  But it would be a change in implementation requirements.  And it would probably further slow down any (are there likely to be any any?) Java 7 implementations on Alpha.  Not that that's likely to be a big deal.

If I read the "more formally" description correctly, you are constraining reads?
What's the impact of this on the rules for common subexpression elimination?  (I know there are issues there anyway, but I'm afraid of pontentially breaking things further.)

3. The volatile emulation seems like it's at best an approximation.  If you implement it with the obvious fences, I think you end up with a PowerPC implementation which is faster than what the PowerPC guys recommend.  This leads me to suspect it's not correct there.  It generally doesn't seem to guarantee the correct outcome for IRIW.  I'm not sure about more interesting examples.  It also depends on parts of the "more formal" definitions I don't yet understand.

I also suspect that the orderWrites fence you need for volatile emulation is different from the one you need for final field emulation.  For volatile emulation, the new relationships really do need to compose with happens-before.  For final-field emulation, I suspect it's critical that they don't.

4. I would strongly prefer fences that order all accesses with respect to a subsequent write or all prior accesses with respect to a previous read.  Otherwise you get very strange races, e.g. (taking syntactic liberties):

T1:
x = 0;
++x;
writefence;
done_with_x = true;

T2:
while (!done_with_x);
fullfence;
r1 = x;
x = 2;  // Race! not ordered with respect to read in ++x

In real cases, this seems to make the code senstive to how a particular object is initialized;  {x = 0; ++x; } is not equivalent to {x = 1;}

And there seems to be essentially no hardware (again Alpha excepted) on which read and write fences really buy you something substantial.

5. The "more formal" definition of orderAccesses doesn't make sense to me.  You normally need a pair of fences to establish a happens-before ordering.  What does "subsequent" mean?  We have w hb f .  If we also have w hb r, or f hb r, then the added
synchronizes with relationship is redundant anyway.

Overall:  Aside from reachabilityFence, which I strongly advocate, and I think is very well understood, this still seems like we're opening a really large can of worms.  I think the downside risk here is huge, since this implicitly constrains (already insufficiently understood) compiler optimization rules for ordinary field accesses.  I think I understand the motivation for doing this.  But I'm not sure fences are sufficiently definable, especially on a reasonable schedule, that you really want to commit all future implementations to supporting them.  Getting these right seems even harder than the other parts of JSR133, and we know we didn't get those all right.  Plus this has to interact correctly with the old pieces.  (Interactions with causality, anyone?)

Since this is intended to replace even worse approaches, I'm not sure what the right solution is.  Define this API as deprecated from the start?  (I'm not sure whether I'm joking ...)

Hans

> -----Original Message-----
> From: concurrency-interest-bounces@...
> [mailto:concurrency-interest-bounces@...] On Behalf
> Of Doug Lea
> Sent: Friday, August 07, 2009 5:52 AM
> To: concurrency-interest@...
> Subject: [concurrency-interest] Fences
>
>
> One of the last tasks in JDK7 integration is to finalize the
> Fences API in light of various unresolved discussions, most
> of which surround the ugly names, awkward usages, and
> unwanted implications about mappings to hardware.
> (Thanks in particular to Jeremy Manson for not letting up on this!)
>
> I placed javadocs for one possible alternative, currently
> just named "FencesV2" at:
> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html
>
> Reactions would be welcome.
>
> It differs in naming (for example "orderWrites" rather than
> "preStoreFence") as well as typical usage -- by returning the
> associated references, they may encourage a simpler usage
> style. On the other hand, without those ugly "pre"/"post"
> prefixes built into their names, they might be more misusable.
>
> This version also has more complete specs (although still in
> need of further review) that are more clearly tied to JLS
> chapter 17 terminology.
>
> -Doug
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Thanks for the helpful comments! I remain optimistic...

Boehm, Hans wrote:
> 0. I'm fine with reachabilityFence, except for the "undefined behavior"
> statement. I don't think you can do that in Java, since it destroys any hope
> of proving security properties, right?

Well, we do this all the time (for example,
disclaimers on effects of queue.drainTo(c) if c is
independently changing), but with the implicit understanding
that the range of "undefined behavior" does not impact
security. Maybe we should do something about
making this fact explicit across JDK specs.

> Requiring it to be a no-op seems fine, and doesn't slow down the obvious
> implementation.

But you are otherwise right that we might as well say
that null args have no effect for all these methods.

This and some other changes are in regenerated version
(http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html)

>
> the orderReads specification seems to introduce constraints on a variable r
> that's never used.

Oops, should be "r1"

> There seems to be at least one critical typo in 17.5.1 in the definition of a
> dereference chain (the spurious(?) r before "dereferences(r, a)").  I don't
> see any obvious way to correct the latter to turn this into a proper
> mathematical definition of a relation, though I can sort of guess what was
> intended.  (I thought the earlier version of this from Jeremey looked OK.)
> If we're going to use this, I'd repeat a demangled version of the definition.
> Maybe the correct version is:
>
> For a read action r, and an action a that reads or writes object o in thread
> t, dereferences(r, a) holds iff t did not initialize o, and a accesses the
> object (o) returned by r.
>
> Did I get that approximately correct?

I think so. We'll have to file a bug report for that JLS wording
(which like a few others, could have been mangled during
JLS integration of JSR133 spec). In the mean time, I copied
corrected version into class doc.

>
> 2.  I still don't see how you could possibly emulate final fields without
> also requiring a fence on the reader side, or effectively constraining the
> implementation of ordinary reads.  Java implementations are only required to
> preserve data-dependency ordering for final fields.  For other fields, I
> believe an access to x.a may still appear to happen before the access to x.
> It may be that this freedom is not important for any up-to-date
> implementations.  But it would be a change in implementation requirements.
> And it would probably further slow down any (are there likely to be any any?)
>  Java 7 implementations on Alpha.  Not that that's likely to be a big deal.

Background for other readers: the Alpha processor (used in "Tru64"
systems) has serious problems conforming to reasonable memory
models, because its spec allows things like speculating the value
of x.a  before reading x unless prohibited by a fence instruction.
(No other MP-able processor we know of has this mis-feature.)
As a minimal accommodation to this, the JSR133 spec contains
what amounts to a loophole that only strictly requires Alpha use
these fences for fields marked as "final". But since Alpha-based
systems have been been at end-of-lifetime for a few years now,
it seems crazy to let this get in the way of solving real
programming problems people have. On the other hand, I see that
there is a JSR133/Java5 JVM for Alpha (http://www.compaq.com/java/alpha/)
so it is conceivable that this would have some impact if they
continue post-EOL updates.

>
> If I read the "more formally" description correctly, you are constraining
> reads? What's the impact of this on the rules for common subexpression
> elimination?  (I know there are issues there anyway, but I'm afraid of
> pontentially breaking things further.)

I don't see any further breakage. If those JMM/JLS issues are fixed,
then it will be comparatively trivial to make any corresponding
adjustments in these specs.

>
> 3. The volatile emulation seems like it's at best an approximation.  If you
> implement it with the obvious fences, I think you end up with a PowerPC
> implementation which is faster than what the PowerPC guys recommend.  This
> leads me to suspect it's not correct there.  It generally doesn't seem to
> guarantee the correct outcome for IRIW.

Sorry, I don't see this. Notice that orderAccesses ensures synchronizes-with.

(On PowerPC, I think both orderReads and orderWrites normally translate
to "lwsync" (plus compiler constraints), although can sometimes
be further optimized as in Paul and Raul's C++ mappings document
http://www.rdrop.com/users/paulmck/scalability/paper/N2745r.2009.02.22a.html
And orderAccesses to "hwsync". Using these seems to give heavier,
not lighter volatile implementation compared to best optimized forms
of volatiles, but not by much.

>
> I also suspect that the orderWrites fence you need for volatile emulation is
> different from the one you need for final field emulation.  For volatile
> emulation, the new relationships really do need to compose with
> happens-before.  For final-field emulation, I suspect it's critical that they
>  don't.

I don't think different ones are strictly needed, because of the
strengthening provided by the trailing orderAccesses. It may well
be that a few processors/implementations could optimize a little
better if they were separated though, but again, not by much.

>
> 4. I would strongly prefer fences that order all accesses with respect to a
> subsequent write or all prior accesses with respect to a previous read.
> Otherwise you get very strange races, e.g. (taking syntactic liberties):
>
> T1: x = 0; ++x; writefence; done_with_x = true;
>
> T2: while (!done_with_x); fullfence; r1 = x; x = 2;  // Race! not ordered
> with respect to read in ++x
>
> In real cases, this seems to make the code senstive to how a particular
> object is initialized;  {x = 0; ++x; } is not equivalent to {x = 1;}
>
> And there seems to be essentially no hardware (again Alpha excepted) on which
>  read and write fences really buy you something substantial.

Right. There is no difference in implementation of
{Load|Store}StoreFence vs just StoreStoreFence on
any other processor (and similarly for load), and
no additional interesting compiler constraints.
The reason for limiting to just StoreStore
(for orderWrites) was just a usabilility/spec/API issue when
moving from xyFence to orderX style.
But it would not hurt to broaden them.

>
> 5. The "more formal" definition of orderAccesses doesn't make sense to me.
> You normally need a pair of fences to establish a happens-before ordering.
> What does "subsequent" mean?  We have w hb f .  If we also have w hb r, or f
> hb r, then the added synchronizes with relationship is redundant anyway.

This is basically just a rephrasing of bullet two of sec 17.4.4
(http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4.4)
but I now see should also include its trailing "(where subsequent is defined
according to the synchronization order)." So much for using
"subsequent" here only  wrt program order. Sigh.

>
> Since this is intended to replace even worse approaches, I'm not sure what
> the right solution is.  Define this API as deprecated from the start?  (I'm
> not sure whether I'm joking ...)

It still seems vastly preferable that we provide a mechanism
people can use to fix serious known bugs (unsafe publication
chief among them), even at the expense of introducing some more
minor challenges to efforts to fix underlying specs.
For an example of impact, the number of memory model
bugs out there might drop significantly if dependency injection
tools inserted appropriate calls to fence methods.

-Doug





_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[tpeierls]

On Sat, Aug 8, 2009 at 8:56 AM, Doug Lea <dl@...> wrote:

For an example of impact, the number of memory model
bugs out there might drop significantly if dependency injection
tools inserted appropriate calls to fence methods.

I think this is a great selling point that we could push. (A little FUD, perhaps, but whatever works.)

--tim 

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

Doug writes:
> It still seems vastly preferable that we provide a mechanism
> people can use to fix serious known bugs (unsafe publication
> chief among them)

This statement has me concerned. Of all the ways to fix unsafe publication,
expecting people to use the Fence API does not strike me as something we'd
want to advocate.

What kind of unsafe publication scenarios do you have in mind here? And
where would the fence be applied to fix them?

David

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Péter Kovács]

On Sat, Aug 8, 2009 at 2:56 PM, Doug Lea <dl@...> wrote:

Thanks for the helpful comments! I remain optimistic...

Boehm, Hans wrote:

 

[snip]

Since this is intended to replace even worse approaches, I'm not sure what the right solution is.  Define this API as deprecated from the start?  (I'm not sure whether I'm joking ...)

It still seems vastly preferable that we provide a mechanism
people can use to fix serious known bugs (unsafe publication
chief among them), even at the expense of introducing some more
minor challenges to efforts to fix underlying specs.
For an example of impact, the number of memory model
bugs out there might drop significantly if dependency injection
tools inserted appropriate caPlls to fence methods.

 Please, could someone give (point to) some background information? Which dependency injection tools are specifically meant here? Are the issues with these dependency injection tools unsolvable using currently available API?

Thanks
Peter

-Doug





_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Péter Kovács wrote:

>     For an example of impact, the number of memory model
>     bugs out there might drop significantly if dependency injection
>     tools inserted appropriate caPlls to fence methods.
>
>
>  Please, could someone give (point to) some background information?
> Which dependency injection tools are specifically meant here? Are the
> issues with these dependency injection tools unsolvable using currently
> available API?
>

Bob Lee and/or Tim Peierls could probably provide more
details about particular frameworks, but the main
cases are of the form illustrated in the "emulating final"
examples (pasted below).
A tool arranges that fields referencing components are bound
during an initialization phase. The references act as final
fields but sometimes (depending on the way initialization
is arranged by tools) cannot be declared as final.

As Tim cryptically noted, there is some fear, uncertainty
and doubt out there about the safety of some of this generated
initialization code across various usage contexts,
that would in most cases be settled by having tools
(not the application programmers) generate orderWrites
calls as appropriate.

...
[pasting from
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html]



Emulating final. With care, method orderWrites may be used to obtain the memory
safety effects of final for a field that cannot be declared as final, because
its primary initialization cannot be performed in a constructor, in turn because
it is used in a framework requiring that all classes have a no-argument
constructor; as in:

  class WidgetHolder {
    private Widget widget;
    public WidgetHolder() {}
    public static WidgetHolder newWidgetHolder(Params params) {
      WidgetHolder h = new WidgetHolder();
      h.widget = new Widget(params);
      return orderWrites(h);
   }
  }

Here, the invocation of orderWrites makes sure that the effects of the widget
assignment are ordered before those of any (unknown) subsequent stores of h in
other variables that make h available for use by other objects. Notice that this
method observes the care required for final fields: It does not internally
"leak" the reference by using it as an argument to a callback method or adding
it to a static data structure. If such functionality were required, it may be
possible to cope using more extensive sets of fences, or as a normally better
choice, using synchronization (locking). Notice also that because final  could
not be used here, the compiler and JVM cannot help you ensure that the field is
set correctly across all usages.

An alternative approach is to place similar mechanics in the (sole) method that
makes such objects available for use by others. Here is a stripped-down example
illustrating the essentials. In practice, among other changes, you would use
access methods instead of a public field.

  class AnotherWidgetHolder {
    public Widget widget;
    void publish(Widget w) {
      this.widget = orderWrites(w);
    }
    // ...
  }




_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Doug Lea wrote:
> But to make methods self-documenting, you'd need to
> create method names like: orderPriorWritesBeforeSubsequentWrites.

This naming style is even less comprehensible when
spec'ing the store fence case to also order load->store, as
it should (see exchange with Hans). So under this style,
the shorter names seem clearer.

Since no one has responded that they prefer the old
"preStoreFence" etc names, I committed FencesV2 as
Fences. See
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/Fences.html

The "more formally" sections still need some work.

-Doug






_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[tpeierls]

On Sun, Aug 9, 2009 at 8:25 AM, Doug Lea <dl@...> wrote:

The "more formally" sections still need some work.

I find it confusing that the JLS defines deferences(r, a) with r being a read action, but the Fences javadocs say deferences(ref, a) with ref being an object reference (while still quoting the JLS definition).

Femces -> Fences in AnotherWidgetHolder

extRes -> ext in the action2 example.

--tim

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Péter Kovács]

Thank you, Doug, for the clarification!

Peter

2009/8/9 Doug Lea <dl@...>

Péter Kovács wrote:

   For an example of impact, the number of memory model
   bugs out there might drop significantly if dependency injection
   tools inserted appropriate caPlls to fence methods.


 Please, could someone give (point to) some background information? Which dependency injection tools are specifically meant here? Are the issues with these dependency injection tools unsolvable using currently available API?

Bob Lee and/or Tim Peierls could probably provide more
details about particular frameworks, but the main
cases are of the form illustrated in the "emulating final"
examples (pasted below).
A tool arranges that fields referencing components are bound
during an initialization phase. The references act as final
fields but sometimes (depending on the way initialization
is arranged by tools) cannot be declared as final.

As Tim cryptically noted, there is some fear, uncertainty
and doubt out there about the safety of some of this generated
initialization code across various usage contexts,
that would in most cases be settled by having tools
(not the application programmers) generate orderWrites
calls as appropriate.

...
[pasting from http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/FencesV2.html]



Emulating final. With care, method orderWrites may be used to obtain the memory safety effects of final for a field that cannot be declared as final, because its primary initialization cannot be performed in a constructor, in turn because it is used in a framework requiring that all classes have a no-argument constructor; as in:

 class WidgetHolder {
  private Widget widget;
  public WidgetHolder() {}
  public static WidgetHolder newWidgetHolder(Params params) {
    WidgetHolder h = new WidgetHolder();
    h.widget = new Widget(params);
    return orderWrites(h);
 }
 }

Here, the invocation of orderWrites makes sure that the effects of the widget assignment are ordered before those of any (unknown) subsequent stores of h in other variables that make h available for use by other objects. Notice that this method observes the care required for final fields: It does not internally "leak" the reference by using it as an argument to a callback method or adding it to a static data structure. If such functionality were required, it may be possible to cope using more extensive sets of fences, or as a normally better choice, using synchronization (locking). Notice also that because final  could not be used here, the compiler and JVM cannot help you ensure that the field is set correctly across all usages.

An alternative approach is to place similar mechanics in the (sole) method that makes such objects available for use by others. Here is a stripped-down example illustrating the essentials. In practice, among other changes, you would use access methods instead of a public field.

 class AnotherWidgetHolder {
  public Widget widget;
  void publish(Widget w) {
    this.widget = orderWrites(w);
  }
  // ...
 }

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Boehm, Hans wrote:
> If I read the "more formally" description correctly, you are constraining reads?

Yes, now I see what you mean...

> ...
> You normally need a pair of fences to establish a happens-before ordering.

I had forgotten about a lingering spec problem here.
(Thanks also to Bill Pugh for pointing it out in a discussion.)
You are right that the non-initialization case only implicitly
required pairings of order{Writes,Accesses} with corresponding
orderReads. And because of this, orderReads spec was too strong,
implying orderings even when not paired.
The ground-rules here make this tricky to fix. You'd
like spec to refer to paired-up fences associated
with the actual reads/writes. But we cannot express
this because we don't have call-by-ref or address-of,
so people cannot say for example (C-ish) orderWrites(&r.x).
Another way out would be to require people to create
instances of Fence objects so they could be matched up
by identity. (As Bill and I sketched out, doing this
seems to lead to fairly pleasant and non-controversial specs.)
But this would require for example creating
entire arrays of them when used to control orderings
on other arrays, which would entail a lot of useless overhead.
The only way out that I can see is to implicitly identify
the pairings using scopes, which I'll try working out.

In the mean time, I did at least clarify the non-formal
descriptions.
(http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/Fences.html)

-Doug

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Tim Peierls wrote:

> I find it confusing that the JLS defines deferences(r, a) with r being a
> read action, but the Fences javadocs say deferences(ref, a) with ref
> being an object reference (while still quoting the JLS definition).
>

The "ref" argument here is intrinsically the result of some read,
so this part works out, although suggested clarifications would be
welcome.

> Femces -> Fences in AnotherWidgetHolder
>
> extRes -> ext in the action2 example.

Thanks!

-Doug

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Boehm, Hans]

 

> -----Original Message-----
> From: Doug Lea [mailto:dl@...]
> >
> > 2.  I still don't see how you could possibly emulate final fields
> > without also requiring a fence on the reader side, or effectively
> > constraining the implementation of ordinary reads.  Java
> > implementations are only required to preserve
> data-dependency ordering
> > for final fields.  For other fields, I believe an access to
> x.a may still appear to happen before the access to x.
> > It may be that this freedom is not important for any up-to-date
> > implementations.  But it would be a change in
> implementation requirements.
> > And it would probably further slow down any (are there likely to be
> > any any?)  Java 7 implementations on Alpha.  Not that
> that's likely to be a big deal.
>
> Background for other readers: the Alpha processor (used in "Tru64"
> systems) has serious problems conforming to reasonable memory
> models, because its spec allows things like speculating the
> value of x.a  before reading x unless prohibited by a fence
> instruction.
> (No other MP-able processor we know of has this mis-feature.)
> As a minimal accommodation to this, the JSR133 spec contains
> what amounts to a loophole that only strictly requires Alpha
> use these fences for fields marked as "final". But since
> Alpha-based systems have been been at end-of-lifetime for a
> few years now, it seems crazy to let this get in the way of
> solving real programming problems people have. On the other
> hand, I see that there is a JSR133/Java5 JVM for Alpha
> (http://www.compaq.com/java/alpha/)
> so it is conceivable that this would have some impact if they
> continue post-EOL updates.

I'm personally not so concerned about Alpha either.  It just serves as a useful illustration that we are imposing additional read-side constraints as well.
The real concerns I have are more along the lines of:

1) Other architectures do generally impose ordering based on data dependencies.
But the specific rules are often not that simple.  I don't understand, for example, whether PowerPC's rules for data dependency ordering are sufficiently strong to generally and cheaply provide the guarantees here.  Do they compose sufficiently with happens-before?  Currently I don't remember/understand either PowerPC rules nor the fence/final field rules well enough to answer that question.

2) My mental picture has always been that final field accesses are compiled under completely different rules than ordinary field accesses.  Final fields allow certain additional optimizations, like CSE across synchronization, but require that certain kinds of dependency ordering be maintained by the compiler.  I think Doug is implicitly claiming that the way normal fields are compiled in reality is also good enough for final fields.  He may be right because only very restricted data dependencies have to be preserved, and real compilers don't speculate on pointer values.  But I'm not sure.  If I understand the current spec correctly, if I write a[x.f] where f is a final field, the accesses to x.f and a[x.f] are already unordered?

>
> >
> > If I read the "more formally" description correctly, you are
> > constraining reads? What's the impact of this on the rules
> for common
> > subexpression elimination?  (I know there are issues there
> anyway, but
> > I'm afraid of pontentially breaking things further.)
>
> I don't see any further breakage. If those JMM/JLS issues are
> fixed, then it will be comparatively trivial to make any
> corresponding adjustments in these specs.
>
> >
> > 3. The volatile emulation seems like it's at best an
> approximation.  
> > If you implement it with the obvious fences, I think you
> end up with a
> > PowerPC implementation which is faster than what the PowerPC guys
> > recommend.  This leads me to suspect it's not correct there.  It
> > generally doesn't seem to guarantee the correct outcome for IRIW.
>
> Sorry, I don't see this. Notice that orderAccesses ensures
> synchronizes-with.
>
> (On PowerPC, I think both orderReads and orderWrites normally
> translate to "lwsync" (plus compiler constraints), although
> can sometimes be further optimized as in Paul and Raul's C++
> mappings document
> http://www.rdrop.com/users/paulmck/scalability/paper/N2745r.2009.02.22a.html
> And orderAccesses to "hwsync". Using these seems to give
> heavier, not lighter volatile implementation compared to best
> optimized forms of volatiles, but not by much.

Paul and Raul's implementation uses a hwsync for Load Seq Cst, which is essentially a Java volatile store.  That's painful, since loads are presumably more frequent than stores, and you're adding a hwsync for accesses that you might expect to ususally hit in the cache.  If I understand correctly, the emulation with fences would only use an lwsync on the load side which, if correct, would solve this problem since it uses only an orderReads, which is presumably an lwsync, right?
...

> >
> > Since this is intended to replace even worse approaches,
> I'm not sure
> > what the right solution is.  Define this API as deprecated from the
> > start?  (I'm not sure whether I'm joking ...)
>
> It still seems vastly preferable that we provide a mechanism
> people can use to fix serious known bugs (unsafe publication
> chief among them), even at the expense of introducing some
> more minor challenges to efforts to fix underlying specs.

A bit more on that in another message ...

> For an example of impact, the number of memory model bugs out
> there might drop significantly if dependency injection tools
> inserted appropriate calls to fence methods.
As a practical matter, I agree.  Adding the fences would help code reliability.  Whether or not we can actually get the spec sufficiently bulletproof to actually eliminate the bugs as opposed to making them much less likely, I'm not sure.

Hans
>
> -Doug
>
 
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Boehm, Hans]

> From: Doug Lea
>
> Péter Kovács wrote:
> >     For an example of impact, the number of memory model
> >     bugs out there might drop significantly if dependency injection
> >     tools inserted appropriate caPlls to fence methods.
> >
> >
> >  Please, could someone give (point to) some background information?
> > Which dependency injection tools are specifically meant
> here? Are the
> > issues with these dependency injection tools unsolvable using
> > currently available API?
> >
>
> Bob Lee and/or Tim Peierls could probably provide more
> details about particular frameworks, but the main cases are
> of the form illustrated in the "emulating final"
> examples (pasted below).
> A tool arranges that fields referencing components are bound
> during an initialization phase. The references act as final
> fields but sometimes (depending on the way initialization is
> arranged by tools) cannot be declared as final.
>
> As Tim cryptically noted, there is some fear, uncertainty and
> doubt out there about the safety of some of this generated
> initialization code across various usage contexts, that would
> in most cases be settled by having tools (not the application
> programmers) generate orderWrites calls as appropriate.
>

The question in my mind here is whether there is some way to avoid the underlying data race on the reference r to the object O containing the emulated final fields.  If the reference were communicated without a data race (e.g. by declaring r volatile, or by protecting it with a lock), clearly the whole issue would go away.

I understand that you might not be able to guarantee this, because there might be a security risk if O is created by untrusted code, and it can see an inconsistent version of O by creating an unprotected reference to it.  It's also conceivable that declaring r to be volatile might be too expensive.

But I think the first line of defense here should be to avoid the underlying data races, without which none of this matters.

Hans
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest