Live data from Hacker News

Breaking java.lang.String

wouter.coekaerts.be

171–180 of 206 posts

Re: Breaking java.lang.String

#171

Earlier quoted context omitted.

Also one more argument for “parse don’t validate”. The code validates a mutable input, and assumes that validation holds thereafter. An incorrect assumption as it turns out.

While that is good advice, it can't apply to mutable input. Unless a defensive copy is made (at least, under the current system), concurrent modification can still occur. The new type's underlying data is still being accessed.

There are necessarily copies being made since it's converting a `char[]` to a `byte[]`, the problem is that they're not done correctly.

Currently the code tries to encode the chars, and if it fails it completely bails out and restarts with a code unit copy. The bailing and restarting is what offers the opportunity for TOCTOU.

But if instead of bailing it converted the data collected so far to code units, then appended the code unit on which it failed, then switched to a UTF16 copy loop, the result would necessarily be correct (at least insofar as a UTF16 string would not contain just latin1)

And in fact this would likely be more efficient than the current version, because we already know that everything we've already converted is valid latin-1, which means we can literally just copy that to every other byte. There is no need to re-do that validation and conversion work. Which is currently the case, because StringUTF16.toBytes redoes the entire thing from zero.

Re: Breaking java.lang.String

#172
post #137

Earlier quoted context omitted.

A proper implementation of hashcode can return nonsense if you mutate the object during hashing.

Sure, but here we're not mutating the object during the String.startsWith() call. Hence I'd say it's a TOCTOU bug in String.valueOf().

This is pretty much the same as breaking a Map by mutating a key during insertion.

Re: Breaking java.lang.String

#173
post #170

Earlier quoted context omitted.

Functions have an assumed pre-requirement not explicitly spelled out in every single javadoc, that the program does not have a data race. May as well ask for every javadoc to explicitly include a pre-requirement that no cosmic rays flip bits of memory. But to be serious again, I'm sure if you look at Array or whatever type is involved in char[], you'll find that it is explicitly marked as not thread-safe.

> Functions have an assumed pre-requirement not explicitly spelled out in every single javadoc, that the program does not have a data race. Maybe in your programs, not in mine. I want my classes’ instances to fulfill their contract once it has been constructed. If it can’t do so, construction should fail with an exception. Note also that for example the OpenJDK’s String::hashCode implementation is formally not data-r…

If you mean that you construct your program in such a way as to not have data races, then I do the same. Even with mutable objects like char[], it's relatively straightforward to just not share such objects, and in the limited circumstances where you must share, to synchronize.

If you mean you somehow unilaterally do away with data races on shared mutable data, even if the concurrent thread does not synchronize in any way, then I am genuinely asking what you're referring to. To be specific, I'm not aware of any implementation of `String(char[])` that operates correctly if another thread is mutating the char[] without synchronization. The JMM guarantees are extremely limited even for distinct indices, hence the need for AtomicIntegerArray, etc.

If you mean you cannot eliminate the data race, but you can do a post-condition check of the String invariants, and you want that checking code to run even in non-debug builds, then fine. I think there is a place for "production asserts" like that, but I think they need careful application, and they don't belong at every level of the stack. I'd check the validity of the String in intern(), but not in every single String ctor as a post-condition. And certainly in most languages with weaker memory models than Java, but my guess is even in Java, such checks provide no real guarantee that data races can't ruin invariants. There's no magic tape to repair that crack in the foundations.

Re: Breaking java.lang.String

#174
post #150

Earlier quoted context omitted.

If you read a double or long while writing to it from another thread, you are not guaranteed to read a value that was ever explicitly set because they update 32 bits at a time rather than atomically.

As per the specification, you are right. As per the actual implementation, no :D it is as cheap, if not cheaper to set it atomically on 64-bit.

[deleted]

Re: Breaking java.lang.String

#175
post #137

Earlier quoted context omitted.

A proper implementation of hashcode can return nonsense if you mutate the object during hashing.

Sure, but here we're not mutating the object during the String.startsWith() call. Hence I'd say it's a TOCTOU bug in String.valueOf().

Again, this is not a bug. There are many, way too many places in standard library which are thread unsafe. Some of these are actual bugs, but not this one. If Java originally moved in Odersky's direction that won't be the case but now it's way too late to point fingers at these "quirks". In order to properly fix these issues the whole standard library has to be redesigned around immutability and, probably, immutable arrays must be supported at VM level. This is not going to happen.

But it's specified that standard Java classes are thread unsafe by default. So this is a specified behaviour.

Re: Breaking java.lang.String

#176
post #137

Earlier quoted context omitted.

Sure, but here we're not mutating the object during the String.startsWith() call. Hence I'd say it's a TOCTOU bug in String.valueOf().

This is pretty much the same as breaking a Map by mutating a key during insertion.

Precisely.

Is it good that this can happen? No, Java must be more like Scala and push immutability as sane default.

Is it a bug? No.

Is it possible to "fix" the language and the VM at this stage? Yes, but that would be a new language and new VM. So, that's not going to happen.

Re: Breaking java.lang.String

#177

Earlier quoted context omitted.

It only loops if you modify the string in certain ways partway through the loop. Is that a significant problem? As soon as you stop your indefinite loop of race-condition writes, this loop is guaranteed to finish.

Well it's trading "bad code can populate the program's string intern table with invalid string objects" for "bad code can instantly deadlock the program", which is not much of an upgrade. And wouldn't you need to do this in every function that uses more than 2 or more related mutable objects 1 time each, or uses 1 mutable object more than 1 time? Do you know of any systems that work like this? This is basically a ver…

> it's trading "bad code can populate the program's string intern table with invalid string objects" for "bad code can instantly deadlock the program", which is not much of an upgrade.

A lot more harm can come from code doing the wrong thing or producing wrong answers than from deadlocks.

Re: Breaking java.lang.String

#178
post #166

Earlier quoted context omitted.

> After a defensive copy of the byte-array is made, just before returning the newly constructed string object, verify once again that the chosen coder matches the string contents. Allocating new String objects might very well be the most frequent memory allocation operation in the JVM. IMO it would be a mistake to do anything to slow this down to protect against this weird instantiation behavior, unless it implies a…

The language maintainers have already decided to slow down string-construction by calling StringUTF16.compress(value) which checks if the input can be converted into LATIN1 and if so, creating a LATIN1 byte-array representation from the ground up. Compared to this, I wager that the incremental cost is small to verify that the coder matches the content. Also, depending on the implementation of string-interning and Str…

Making the 99% case faster at the cost of making the 1% case slower, is a speedup.

Re: Breaking java.lang.String

#179
post #166

Earlier quoted context omitted.

> After a defensive copy of the byte-array is made, just before returning the newly constructed string object, verify once again that the chosen coder matches the string contents. Allocating new String objects might very well be the most frequent memory allocation operation in the JVM. IMO it would be a mistake to do anything to slow this down to protect against this weird instantiation behavior, unless it implies a…

The language maintainers have already decided to slow down string-construction by calling StringUTF16.compress(value) which checks if the input can be converted into LATIN1 and if so, creating a LATIN1 byte-array representation from the ground up. Compared to this, I wager that the incremental cost is small to verify that the coder matches the content. Also, depending on the implementation of string-interning and Str…

I don’t think you need any defensive copy, just to have compress switch to utf16 mode when it encounters a non-latin1 char and go on from there.

It would likely be faster since currently the implementation restarts the entire conversion from 0 in utf16 mode.

Re: Breaking java.lang.String

#180
post #81
post #75

Earlier quoted context omitted.

Author of the blog here. Yes, this is a bug. While the javadoc doesn't state it explicitly, immutable classes in the core library are expected to be thread safe. Java tries to be and mostly succeeds at being a safe language, where (by default) the guarantees of its internals cannot be broken no matter what user code does. The JVM preserves its own integrity. There are some other deliberate holes in that safety, such…

How would you fix this? Possibly by copying the input array to a local array as the first step? But then you might copy a lot of data, which is in 99% of the cases totally unnecessary. Have a separate threadsafe and a non-threadsafe constructor for char[]? EDIT: another idea is to do a hash of the input array, and compare between start and end. But that also requires an O(n) walk through the input...

> How would you fix this? Possibly by copying the input array to a local array as the first step?

Upon encountering a non-Latin1 char, convert the existing latin1 array to an utf16 one, append the char (converted), then resume iteration in utf16 copy mode.

This way you know the char which made you bail out on Latin1 is part of the output.

Post reply on HN