clojure.lang.APersistentVector#hashCode is not thread-safe

Description

Problem: clojure.lang.APersistentVector#hashCode contain a deliberate data race on hash computation. However, the code as written does not follow safe practices for the intended data race. Specifically, the problem arises because the hashCode() (and hasheq()) method make multiple reads of the (unsynchronized) _hash field. The JMM permits these reads to return different values. Specifically, the last read in the return may return the pre-computed value -1, which is not the desired hash value. This problem also applies to APersistentMap, APersistentSet, and PersistentQueue.

See: http://jeremymanson.blogspot.com/2008/12/benign-data-races-in-java.html for a good description of the problem.

Fix: The main fix is to read the cached hash field only once and return the value of the local computation, not the value of the field.

A secondary change that is also beneficial is to use the default initializer value (which has special ordering in the JMM to the beginning of the thread) rather than setting and using -1 as the sentinel value.

In both cases these changes follow the canonical idioms used in java.lang.String for lazy hash computation. The patch covers both.

Patch: clj-2091-default-initialization.diff - note that this patch will indicate whitespace errors when applied due to the wacky line endings in PersistentQueue. The problem here is really the PQ formatting, not the patch.

Prescreened by: Alex Miller

There are some hash-related tests already but I also spot-checked that hash computations are returning the same value with and without the patch for the collections in question.

Environment

None

Attachments

2

Activity

Show:

Alex Miller January 10, 2017 at 2:33 PM

Feel free to update the patch if you like

thurston nb January 10, 2017 at 2:16 AM

Problem also in core.lang.ASeq#hashCode() and core.lang.ASeq#hasheq() - although thankfully without inline initialization

Surely not the last place either

thurston nb January 7, 2017 at 5:36 AM

Combines the 2 commits into a single commit patch
So incorporates the original patch changes (single read) with default initialization and checks for zero
Don't know what to do with PersistentQueue's mixed line-endings – that I'll leave to you to deal with

Alex Miller January 6, 2017 at 9:19 PM

Ok, I went over all this again and it makes sense to me. I think you should proceed and also make the initializer change (remove the -1 as sentinel and replace with no initializer and 0 for the comparison checks in the methods).

thurston nb January 4, 2017 at 5:02 AM

Sure.

To be clear, as I mentioned in today's earlier comment, I would advise removing the inline-initialization, viz.

with

As I wrote, the extant tests would pass (of course, changing #hashCode() and #hasheq() appropriately)

But the initialization issue is a different, although certainly not orthogonal, issue than the one my patch addresses.

Currently, (i.e. pre-patch), #hashCode() can return a spurious -1 even if an APersistentVector instance is safely published - my patch fixes that.

However, because of the inline-initialization, an APersistentVector instance that is not safely published could return a spurious 0 from #hashCode(), even with my patch.

Now if the inline-initialization is just a "legacy idiosyncrasy" (and we all do that at one time or another), then it could be safely replaced (along with the appropriate modification to my patch) and all APersistentVector instances (safely published or not), would have #hashCode() implementations that are correct.

Completed

Details

Assignee

Reporter

Approval

Ok

Patch

Code

Priority

Fix versions

Created December 24, 2016 at 10:33 PM
Updated May 12, 2017 at 6:40 PM
Resolved May 12, 2017 at 6:40 PM