stringCache is only ever assigned to with an initialised string (the output of stringCache()), so given Strings are immutable and assuming Java's assignment is atomic, how can you get a race condition that causes a problem? There shouldn't be a TOCTTOU issue either given stringCache is copied to sc before being null-checked.
What is the statement reordering doing here to break this? How can it be prevented? (Does it need write barriers or something?)
Using the Java terminology, there is no "happens-before" edge. So every action must appear as if it occurred in the specified order in that thread, but other threads are free to see those actions in a different order.
On some machines/CPUs/architectures, this is very easy to organise, since the writes can and will be re-ordered. When this happens you can get the pointer to the string being set, before the contents of the string are actually set. Within the thread, you won't see this, since reorders within the thread of context are done "safely", or at least are visible, but to a different thread/core/CPU those writes may arrive out of order.
Looking at the article I see he's running on a raspberry pi. I would guess the problem is that the openjdk aarch32 jit is not correctly implementing the java memory model as final fields should have been initialised before an object is visible in another thread.
So it's not really that BigDecimal isn't thread safe, but that there's a bug in the JIT.
I agree. The Java memory model explicitly stated that final fields will be correctly initialized in any object reference visible from another thread, provided a reference to that object is only stored after the constructor completes.
That would be consistent with my understanding of the JMM and unfortunately my prejudices against "community maintained" backends and ports of OpenJDK.
I'm not sure if this is the case for the JVM, but for .NET it is perfectly legal for the VM to store the object address somewhere after allocation but prior to the constructor running/becoming visible. All of the fields objects will be zeroed so this won't cause memory unsafety, but it's rarely what you expect to happen.
Forgetting this is a big source of bugs in double checked locking in .NET.
That seems like a bad thing. I'd think that you'd want your language to guarantee an initializer has completed before letting an object/structure/whatever be visible. At least as the default.
I mean, that doesn't even give an object a chance to initialize a synchronization mechanism before it's thrown into the wild where it needs one.
It sounds like initializing fields to zero is guaranteed, but is that flexible enough to generally base synchronization on?
It's a performance trade off, because in general it's hard for the compiler to know whether it needs to insert a memory barrier or not if you do something like:
this.fooField = new Something()
which would need a memory barrier if another thread is expected to access fooField concurrently, and not need one otherwise. Putting memory barriers on every field assignment of a constructed object would be pretty expensive.
It's also worth noting there's not anything that special about constructors here; there's a million other ways you can get similar issues when you try to handle concurrency at this level. For example if you do:
Come to think of it, I objected because I thought it doesn't give you a chance to initialize whatever your object/structure/whatever's synchronization mechanism is. But that's not really true. The call to initialize your synchronization mechanism would contain the barrier you need so a general initialization doesn't generally need one.
It could cause other correctness issues that could break CAS, for instance (which yeah seems like a poor idea in hindsight since it's so complicated). If this is actually allowed it seems like a huge mistake in the .NET memory model. I've never seen a definitive answer on it (not saying you're wrong).
It has to be legal for the VM to store the object before it has been entirely initialised, but the question is whether other threads will be able to see it in that uninitialised state. If other threads can see a partially initialised object then you remove most of the nice guarantees final fields give the JIT.
NB. You can break all the JMM guarantees by having the constructor share the object reference with another thread. The JMM even says:
> If a reference to an object is shared with other threads during the initial construction of an
object, most of the guarantees for final fields of that object can go kerflooey; this includes cases in
which other parts of a program continue to use the original value of this field.
If you do it from the constructor (assign this to a shared field) then that seems acceptable and narrows the scope of issues a ton.
Do you know of a definitive answer on this by an actual team member with citations? I've seen well respected community people assert that partially constructed objects can be visible but that seems wrong. I would expect this to have practical memory safety issues: somewhere in the standard libraries there have to be interoperability classes that could result in unsafe access if partially constructed.
The safety guarantees only apply to final fields, it's entirely possible to see non-final fields in a half initialized state, and even half written longs because the memory model does not guarantee those operations are atomic. To be safe in those cases you must use synchronization or something else that establishes a happens before relationship.
I think there's some good talks on the JMM on YouTube, and stuff on Shipilev"s blog.
Java is the same, but final fields are special. The object cannot be published until they're completely initialized (unless the constructor unsafely publishes them).
That's a confusing and glossed over bit in the article. After all the talk of BigDecimal, the test produces an NPE in String but then the conclusion is the problem is in BigDecimal. The String thing should be far more surprising and unexpected than any secondary effect in BigDecimal.
But the stringCache reference is not final, it's just transient. Because there is nothing within the toString() implementation that enforces a happens-before effect, nor is there anything similar on stringCache itself (such as volatile), threads are not guaranteed to see anything correctly with respect to stringCache, or the layoutChars() method.
The problems in layoutChars also affect the thread-safe behavior of toEngineeringString() as well.
If you have a reference to a junk instance, which is what can happen with an unsafe publication (which is what is going on with the stringCache member variable) then all bets are off in terms of what you can expect to see.
Step back a bit: where did the junk instance come from? The Java rules guarantee that a String created through the String constructors is valid on any thread that can see it. There are no "junk instances" of String. Also, writing to an object reference variable is indivisible: either a thread doesn't see the write, or it sees the full write.
So there are only two states in which a thread can see the stringCache field: either it is null, or it has a reference to a valid String. It might not see the field write from another thread, but in this case this only leads to duplicating work and leaving a bit of garbage on the heap for the GC to clean.
(Of course, once you start using reflection to manipulate internal fields of an object, then all bets are off, but that's not the case here.)
Within a thread that sees "sc == null" the assignment of stringCache and sc to the result of layoutChars(true); will be legitimate (they will see a valid, fully-formed, correct String).
Another thread calling toString() may or may not see sc, or stringCache, assigned to a legitimate String instance, due to the Java Memory Model (happens-before, memory barriers, CPU implementation details, cache levels, etc.).
The data within the String created by layoutChars will be consistent to anybody who has established a happens-before relationship with respect to stringCache (either the thread who created it, or if stringCache was volatile, or if stringCache was final, or if a memory-barrier (synchronized, atomic primitive, etc.) has been erected around it.
None of that is present in this implementation of BigDecimal.toString(), which is why stringCache (and the vars used in layoutChars()) is not a valid publication in the Java Memory Model.
It has nothing to do with whether String is correct, and it's not a defect in the JRE implementation. No safe publication was established with respect to stringCache, therefore the data that other threads see is undefined.
It has nothing to do with whether String is correct
It has everything to do with it. You have to explain how you ended up with a broken instance of String. The internal state of a String instance is hosed, which is a massive violation of all sorts of JVM guarantees and assumptions - this is the OG immutable class, after all. There are two options - a broken String implementation or a broken JVM implementation.
Why is the JIT not allowed to do this? (Assuming publishing isn't volatile)
The reordering could also be caused by the CPU, not only by the JIT.
If the JIT isn't allowed to reorder, we also need to prevent the CPU from reordering.
Otherwise it doesn't make sense to restrict the JIT from reordering if the CPU could still reorder later.
We would need to emit memory barriers for non-volatile loads & stores to prevent reordering on architectures like ARM.
This sounds quite expensive.
This doesn't make sense to me. Am I thinking wrong? Can you point me to documentation/reference that states that the JIT isn't allowed to do this?
An object is considered to be completely initialized when its constructor finishes.
A thread that can only see a reference to an object after that object has been completely
initialized is guaranteed to see the correctly initialized values for that object's final fields.
Thanks, that explains it! Didn't know that final fields have this special rule and that the value field in the String class is final.
So to recap: this shouldn't be possible for Strings, since the value field in the String class is final and therefore has a memory barrier. But it could happen for other classes with non-final fields.
It cannot do that, value is final, so value has to be fully initialized before publishing. The only way that could happen is if the String constructor unsafely published the string (which is not the case)
The issue may be to do with the guarantees that the JVM gives you about orders of operations and write visibility across threads.
The author hints at a possible solution when they say "As we see a non-volatile field stringCache", the key being 'volatile' which is a Java keyword with a specific meaning that constrains the order of operations and write visibility across threads.
> the key being 'volatile' which is a Java keyword with a specific meaning that constrains the order of operations and write visibility across threads.
I must point out that "volatile" in Java means something completely different than what it means in C and related languages.
In multithreaded C code, "volatile" is almost always incorrect. There are only a few correct and portable uses of volatile (such as dealing with setjmp or unix signal handlers).
The most important thing being that in Java, volatile is a memory barrier, whereas in C it isn't.
One thing I'm unsure of: I think in C, a volatile write to some location and a volatile write to another location (even without any data dependency) may not be reordered); is this correct?
C's volatile guarantees very little. It's mostly there for compilers to implement in whatever way is useful for the environment they run in, and so there isn't much portable code you can usefully write using volatile.
All it really guarantees is that reads and writes won't be elided. For example:
*x = 42;
*x = 43;
If x is a normal pointer, the compiler can eliminate the first line. If it's a pointer to volatile, the compiler must write both values.
Volatile predates multithreading in C (it was meant for memory-mapped IO and similar things) and hasn't been updated for it, so it has pretty much no useful properties for multithreading. There are no guarantees about reordering when it comes to multiple threads. You're guaranteed to see reads and writes in the correct order from the perspective of the thread your code is running on, but the compiler won't insert any memory barriers, so it's completely up for grabs how other threads might see it.
(More completely, it depends entirely on your CPU's memory model. If you're on an architecture which does strict ordering at the hardware level then you could potentially take advantage of that. If you aren't then you'll see whatever crazy results hardware reordering might produce.)
In contrast, Java's volatile is only about multi-threading. So really, the only thing that's similar between the two languages' use of volatile is how they spell the keyword.
It's a bug in the JVM, value is final and assigned in the constructor after the array is fully initialized, so it's impossible as per the JMM to see a partially initialized string. My guess is that the RaspPi VM is buggy.
You can see a partially constructed String is the problem. Assignment is atomic, but it's not guaranteed to not be reordered with operations done in the constructor.
I disagree that the others' points about Strings having final values make this irrelevant.
It's the references that must be final in order for things to be irrelevant, but stringCache (nor the other instance-level variables used by layoutChars() such as scale, intCompact, etc.) is not final. It's just transient, which doesn't affect anything with respect to thread-safe behavior.
If stringCache was final then this problem wouldn't exist. Neither would it exist if stringCache was volatile (though you would potentially duplicate work).
The implementation of toString() (specifically the assignment of stringCache) is a perfect example of an unsafe publication in the Java Memory Model world.
At most, per the JMM this can only initialize the cached string in BigDecimal more than once, but you can never see a partially initialized string. This is a JVM bug.
You'd have to point out specifics you're mentioning, but the read of stringCache is not through a final field, and that's the source of the problem for any thread that did not initialize or otherwise set stringCache to a value.
The JLS specifically points out string's final fields as being important to the memory model for security purposes. This is a JVM implementation bug.
Quote:
>String objects are intended to be immutable and string operations do not perform synchronization. While the String implementation does not have any data races, other code could have data races involving the use of String objects, and the memory model makes weak guarantees for programs that have data races. In particular, if the fields of the String class were not final, then it would be possible (although unlikely) that thread 2 could initially see the default value of 0 for the offset of the string object, allowing it to compare as equal to "/tmp". A later operation on the String object might see the correct offset of 4, so that the String object is perceived as being "/usr". Many security features of the Java programming language depend upon String objects being perceived as truly immutable, even if malicious code is using data races to pass String references between threads.
This is only true if you have a safe reference to that String. No safe reference has been established between stringCache and the String instance it points to.
Assuming you have a safe reference (through a safe publication), then what you quoted comes into play. You do not need any synchronization mechanisms around a String in order to see its correct data, because the String instance is immutable.
Or to put it another way, why do you think other threads would see the value of stringCache change from
stringCache = "this is my value in thread 1.";
to
stringCache = "this is a different value set by another thread without a safe publication of the stringCache reference.";
without establishing a happens-before relationship through a memory barrier?
You wouldn't. That's why there are AtomicLong, AtomicBoolean, and AtomicInteger. Long, Boolean, and Integer are all immutable, but you can't use them without establishing happens-before. AtomicReference could have been used to get the correct behavior intended by stringCache, but AtomicReference didn't exist until 1.5.
> Or to put it another way, why do you think other threads would see the value of stringCache change
True, other threads might not see the value of stringCache change. However, if and when they see it change, they will see it change to another valid String. They will never see an incompletely initialized String.
Using AtomicReference or volatile gives you stronger guarantees, but they're not necessary here.
The fact that value on string is a final field is meant to give you a guarantee that it will have been initialised before any other thread can see the object (assuming the object does not leak itself deliberately in the constructor). This does not depend on the reference to the string itself being final.
Very similar bug was in Digitalk Smalltalk 25 years ago: conversion from integer to string used a global cache... I notices this while running a batch with progress indicator on UI. Sometimes integer to string conversion in batch didn't work and I couldn't find the reason. After loooooooong period of extensive debugging the issue was pinned down to global cache in integer to string conversion, which was not thread safe. At first Digitalk didn't want to fix it "because of performance issues", but in later versions it was fixed... This bug can cause very serious side effects...
BigDecimal has nothing to do with the issue.
There is no race conditional. The code is textbook example how to use (cheap) unsafe publishing with no locks/CAS -- assign to local variable and 'return' the variable value (not a class member one). There is no global cache, it's per BigDecimal instance.
As for 'this bug', yes JVM concurrency bugs are serious by definition.
How does this assign an uninitialized String to stringCache? I thought String is immutable and the String object is fully calculated at assignment? Where is the StringBuilder used when stringCache and sc are objects of type "String?"
Shouldn't the "problem" be that two threads might call layoutChars at the same time, leading to some extra CPU cycles wasted and some extra garbage?
I suspect that the real source code is different, or the real problem that leads to the NRE is different.
You are correct that this is allowed by the Java spec (1). Final fields are guaranteed to happen before reference assignment, and strings are explicitly mentioned. It appears to be an ARM JVM bug.
Not sure if late for the party... But there is no bug int the impl. BigDecimal.toString(). It's a JVM bug. It blatantly violates the spec of the original JMM (as of Java 1.5 and backported to 1.4)
Not only that but it lacks optimization/intrinsics for String. String.length() should never/ever yield a NPE. I'd expect a process crash than adding metadata for trapping read access faults.
---
Edit: final fields have become ubiquitous even for objects that are safely published [via volatile, synchronizeed, CAS, before thread.start()]. All wrapper classes Integer, Long, etc. have them. Final fields are very much advised to be used and they do help reliability and readability by making it easy to reason about object state (i.e. it doesn't change once seen).
On x86 field fields require a compiler barrier at best as the writes are not reordered. In other words they are extremely cheap. Stuff like AtomicReference.lazySet is next to free and a welcome way to build fast concurrency primitives.
There is Doug Lea's parer[0] for the improved jmm.
There are different versions of ARM architecture with different memory models, overall ARM is considered weak.
v7 has dmb[1] only, and to my knowledge it's not cheap. Skipping dmb requires rather deep analysis, so I wonder if that was the case experienced by the poster.
ARMv8 has store-release fence but I don't know how efficient would be spamming it.
In java lang specs: "A thread that can only see a reference to an object after that object has been completely initialized is guaranteed to see the correctly initialized values for that object's final fields."
This makes it a JVM bug because no thread should be able to see uninitialized final fields of an object.
Agree with others that String.length() should never ever throw NPE from within String, regardless of it being called from whatever thread.
Now, in the comments there's another idea suggesting the unsafe publication of String (partially constructed). This would be the case if String.value wasn't final (essentially the case of double-checked locking). But that's not the case here because String.value is final[0]
While it's a JVM bug, making stringCache volatile would be one way to fix it - unless the JVM is also broken around volatile...
is there even a good reason for this to be cached. this almost like a memory leak. if someone wants to cache the result of toString they should be doing it in client code. this shouldn't be something that is forced on everyone.
And yet, it's an interface, as a user you don't notice this performance improvement at all - it returns a string version of an (immutable) data structure, how it does that and whether it caches it is not something that the client can control, and thus not something they should care about too much.
What they should and will care about is the performance of BigDecimal.toString(), and if it's cached then the 2nd and onward calls will be very fast.
Mind you, I'm sure there's a lot of similar optimizations in a lot of toString() implementations; a generic implementation that is threadsafe would be preferable to a roll-your-own-caching.
Fyi, there are well-known safe approaches like memoize() to do that instead of roll-your-own. Selecting hidden cache field for every damn value seems like the legacy architectural error. Also, on some platforms not caching this at all would be better than caching under atomic primitive.
"BigDecimal is an immutable data type. So every method of this class should be thread safe."
I'm not familiar with the ins and outs of Java's API and memory model and this is unexpected, but should it? If so, where does the documentation make that promise?
Also (nitpick) one _can_ subclass BigDecimal and make it mutable (a design error that won't be fixed because of backward compatibility)
And yes, I think it has to define what it means by those terms before one can assume that seemingly obvious claim to be true. Reason? Both thread-safe and immutable are fairly vague terms that different readers can interpret differently. For example, BigDecimal is declared to be immutable, but, in the implementation being discussed, has a field that can get modified when one calls toString() on it.
Immutable implies thread safe. Somewhere in the concurrency section of Effective Java, it both that this is true and that documenting a class as immutable is good enough to document that it's thread safe.
Not sure if the spec lays it out, but it's a consequence of the spec.
I am a complete java noob, but it seems like in the test program the same variable testBigDecimal is being shared by different threads without any lock or mutex or any sort of concurrency control! Won't any function working on testBigDecimal be thread unsafe if it was not specifically written assuming it was working on a shared object? Why is this news?
Disclaimer: I am so java illiterate that I am applying my C understanding to the code snippet.
It's immutable, and immutable objects are thread safe. This is also true in C: you can safely pass references to structs between threads with no locks, as long as you never mutate them. Java just enforces that immutability if you write the class the right way.
...the bug is that it's not really immutable, insofar as it's using an unsafe mutation under the hood to implement its toString method. So it either needs to document the fact that it's not immutable despite the appearance otherwise (crazy), or fix the problem.
The rules for C and Java are different. In Java, it's guaranteed that the assignments in the constructor to fields marked as final is visible to other threads before the newly constructed object is (unless you stash a reference to it before returning to the constructor), but C has no such guarantee, so in C you have to put the memory barriers yourself.
Yes, what Java gives you for immutable objects is a guarantee of safe publication. In both languages, once you have the object published, you can freely share it between threads.
BigDecimal does not contain any mutable user visible state, so it should be usable by different threads without synchronisation of any kind (except the implicit synchronisation by means of "can I see pointer to that instance")
It is news because either there is bug in the BigDecimal or JVM in question that causes the above assumption to not hold.
BigDecimal claims to be an immutable class, with only non-mutating public methods. In C, the equivalent would be that every exposed function takes `const BigDecimal *`.
Even in C, it is fine for multiple threads to access the same data as long as they all read and don't write it.
stringCache is only ever assigned to with an initialised string (the output of stringCache()), so given Strings are immutable and assuming Java's assignment is atomic, how can you get a race condition that causes a problem? There shouldn't be a TOCTTOU issue either given stringCache is copied to sc before being null-checked.
What is the statement reordering doing here to break this? How can it be prevented? (Does it need write barriers or something?)