Hacker News Reader

Comment by dundarious | Hacker News Reader

Calling this a "bug in java.lang.String" is silly. The same "bug" exists for all functions that take mutable objects. If you take a map and lookup two different keys, yep, that's a "bug".

The bug is the other piece of code that introduces the data race in the first place. You can argue the case for languages like Rust with it's borrow system, or others that use linear types or something along those lines, to eliminate the possibility of this happening, but it's quite misleading to say that the innocent user of a mutable object is the source of a bug. You may as well say there's a bug in `printf("Hello, World!\n");` in C because you could have another thread writing random values to random memory, running `while(1) { *((unsigned char*)(void*)rand()) = rand(); }`

View on HN

This bug can change the meaning of code in third party libraries by altering the set of interned strings.

If any input to a program can be converted into this race, then it becomes a security vulnerability. It would already be a security vulnerability in the old Java sandbox model.

If you have a data race, your program can have all sorts of inconsistent state in all sorts of objects -- even standard ones. In Java, I don't think you have anything like "undefined behavior", sometimes jokingly but meaningfully called catch-fire or launch-the-nukes semantics, but that doesn't prevent a data race from breaking program invariants in ways that don't immediately or ever generate exceptions.

There was a little optimization post a few days ago: https://news.ycombinator.com/item?id=36618344. Basic summary of the program, given a NUL terminated buffer like "spppssss", return an int where each 's' adds 1, and each 'p' takes 1 away. Several of the alternate implementations in the HN comments involved using strlen first, which has the nice of effect of being highly vectorized, and knowing the size, the compiler can better vectorize the actual logic loop, and a human can vectorize better still. If we imagine another piece of code that concurrently modifies the input buffer to write a NUL to the 0 index, it would change the length to 0. To be generous and to simplify the discussion, let's say the concurrent modification happens to become visible to our thread after strlen but before the following loop. Is there now a bug in this implementation?

If the point is that java.lang.String must ensure its pre-conditions and post-conditions are always maintained, because it's so fundamental to other security functions of the JVM, then there is no solution that allows for untrusted/buggy shared memory concurrency. Any suggested modifications to the constructor like "add a lock" or "copy the buffer first" will not work, and are missing the point entirely.

If the issue is the string intern-ing of such a dodgy String, then the best you can do is code intern() more defensively, to throw out detectably dodgy input. I could then understand saying intern() has a bug, but I don't think that was the point of the post, since there is no discussion of the intern() code.

That's a lot of talking around the issue and I think you're missing it.

We're talking about constants being corrupted in code which has has no control or data flow relationship with the code doing the corrupting. Code which is totally bug free can exhibit impossible behavior.

That might not sound disturbing to you if you're taking about strlen(), because languages with unrestricted pointers are full of undefined behavior. But Java isn't like that. Java doesn't come with nasal demons.

I didn't say intern() has a bug.

The bug is Java having undefined behavior of the kind which breaks a language invariant as strong as string equality.

You're arguing that there isn't a bug because non-determinism comes from concurrency. Well, you can't have concurrency without non-determinism. That doesn't mean the language needs to stop working.

This is perhaps an unnecessary clarification, but there's plenty of non-determinism that's perfectly fine. Data races are non-deterministic and bad, but "non-determinism" itself is not a scare word.

I spent a good decade of my career writing C#, which is similar enough to Java for these discussions, and the strlen issue I talked about is not limited to C -- it is also an issue for a managed language like C# or Java. I think you would do well to discuss the problem, instead of dismissing it because myself and the original post I referenced are tainted by the nasal demons of undefined behavior in C. Don't use that as an escape hatch from dealing with the general issue presented in the problem.

I know of no language in existence where even in the face of data races, there is a guarantee that all data invariants are maintained otherwise an exception is thrown. Note that Rust is not such a language, as its goal is to make data races compilation errors, but unsafe code can introduce data races that do not generate compilation errors.

I would also suggest you offer even a sketch of a fix for the String(char[]) constructor if you think that is the source of the bug. I don't think one is possible. I'm not aware of any method to unilaterally atomically copy an unbounded char[], for example. Even if there is, I suggest you go look for other functions that take other kinds of mutable objects as parameters -- I doubt that for each and every case there is a method to unilaterally atomically deep copy those objects. Such copying is just one suggestion, feel free to resolve it any way you think works.

If you don't want to sketch a solution, another experiment you can try is to use a non-thread-safe mapping type like TreeMap, and make structural modifications (add/remove elements, not just modify existing values) from multiple concurrent threads without any synchronization. Can you guarantee that in all cases where invariants are broken, that an exception will be thrown?

I think it would be prudent to do something in intern(), and one could arguably call this a bug in intern(). The string intern table is invisibly and pervasively read shared state, and relatively uncommonly mutated. It would make sense to take extra care when mutating the shared state to attempt to ensure no invalid strings are added.

It’s a bug for constructor functions, in my book. I certainly always code defensively to prevent such misbehavior. A successfully constructed object should obey its documented interface contract, period.

> A successfully constructed object should obey its documented interface contract, period.

Could you provide the contract you are talking about?

Yes, the contract of String::equals: The result is true if and only if the argument is not null and is a String object that represents the same sequence of characters as this object.

The article constructs two String objects representing the same character sequence, for which however equals() returns false, in violation of the above-quoted contract.

So they should add that mutating arguments during object construction may lead to not-so-successfully constructed (invalid) object. __Mission failed successfully__

No. The job of a constructor is to establish the class’s invariants for the new instance, or else fail with an exception. This bug in the String class fails to do so.

> The job of a constructor is to establish the class’s invariants for the new instance, or else fail with an exception.

Could you refer such statement in Java specification?

Invariants and all methods -- including constructors -- enforcing them is OOP 101. I would be surprised if they felt the need to make such a callout in the language specification.

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-race free (racy single-check idiom), so your assumption as stated doesn’t hold.

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.

It is probably a gotcha. But yeah if you hit this problem you have bigger worries, the code immediately before the constructor is not thread safe.

Reply on news.ycombinator.com