Clojure

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

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: Release 1.9
  • Component/s: None
  • Patch:
    Code
  • Approval:
    Ok

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.

Activity

Hide
thurston n added a comment -

I can of course provide a patch, but as this is my first issue and am generally unfamiliar with clojure's practices and because this issue is not restricted to APersistentVector#hashCode, I thought it best to hold off and let the stewards decide how to proceed and how I could best help

Show
thurston n added a comment - I can of course provide a patch, but as this is my first issue and am generally unfamiliar with clojure's practices and because this issue is not restricted to APersistentVector#hashCode, I thought it best to hold off and let the stewards decide how to proceed and how I could best help
Hide
Alex Miller added a comment -

Patch welcome (but please sign the contributor's agreement first - http://clojure.org/community/contributing). Also, see the processes for developing patches at http://dev.clojure.org/display/community/Developing+Patches.

AFAICT, the affected classes are APersistentVector, APersistentMap, APersistentSet, and PersistentQueue? Would be ok by me to cover all of them in a single patch.

Show
Alex Miller added a comment - Patch welcome (but please sign the contributor's agreement first - http://clojure.org/community/contributing). Also, see the processes for developing patches at http://dev.clojure.org/display/community/Developing+Patches. AFAICT, the affected classes are APersistentVector, APersistentMap, APersistentSet, and PersistentQueue? Would be ok by me to cover all of them in a single patch.
Hide
thurston n added a comment -

AFAICT, the affected classes are APersistentVector, APersistentMap, APersistentSet, and PersistentQueue?

  • Dunno. However my experience tells me that the broken idiom (racy cache/memoization) is likely elsewhere; but I know of no systematic way of finding them. Regardless, I'll just focus on those 4 classes.
  • My plan is to also fix #hasheq(). It's the same problem; if you don't want that then just let me know and I'll refrain.
  • I'm not planning to deal with the initialization of #_hash and #_hasheq (currently inline-initialized to -1); that's a separate (although related) thread-safety problem. Might they be just what we refer to as a "legacy idiosyncrasy"? If so, then they really should be changed to just be default-initialized. I did, as an experiment, change one to default initialization, and the tests passed - that should be enough, but given that the persistent classes are serializable, code-coverage, et al., I can't say for sure. So I'll leave it to others more familiar with the codebase to make that determination. I note that if it is in future determined to change them, then #hashCode() and #hasheq() will need to be modified (trivially) accordingly.

That's the plan. Sound good?

Show
thurston n added a comment -
AFAICT, the affected classes are APersistentVector, APersistentMap, APersistentSet, and PersistentQueue?
  • Dunno. However my experience tells me that the broken idiom (racy cache/memoization) is likely elsewhere; but I know of no systematic way of finding them. Regardless, I'll just focus on those 4 classes.
  • My plan is to also fix #hasheq(). It's the same problem; if you don't want that then just let me know and I'll refrain.
  • I'm not planning to deal with the initialization of #_hash and #_hasheq (currently inline-initialized to -1); that's a separate (although related) thread-safety problem. Might they be just what we refer to as a "legacy idiosyncrasy"? If so, then they really should be changed to just be default-initialized. I did, as an experiment, change one to default initialization, and the tests passed - that should be enough, but given that the persistent classes are serializable, code-coverage, et al., I can't say for sure. So I'll leave it to others more familiar with the codebase to make that determination. I note that if it is in future determined to change them, then #hashCode() and #hasheq() will need to be modified (trivially) accordingly.
That's the plan. Sound good?
Hide
Alex Miller added a comment -

I thought the non-default initialization was part of what you were describing, so now I'm not sure we're on the same page. Maybe you can just patch one so we have something concrete to talk about.

Show
Alex Miller added a comment - I thought the non-default initialization was part of what you were describing, so now I'm not sure we're on the same page. Maybe you can just patch one so we have something concrete to talk about.
Hide
thurston n added a comment -

I'm not sure what you mean by "patch one" - I just submitted a patch, did you look at that?

Show
thurston n added a comment - I'm not sure what you mean by "patch one" - I just submitted a patch, did you look at that?
Hide
Alex Miller added a comment -

I meant one class - sorry, I didn't see the patch. I will look at it tomorrow with fresh eyes.

Show
Alex Miller added a comment - I meant one class - sorry, I didn't see the patch. I will look at it tomorrow with fresh eyes.
Hide
thurston n added a comment - - edited

Sure.

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

int _hash = -1;
int _hasheq = -1;

with

int _hash;
int _hasheq;

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.

Show
thurston n added a comment - - edited Sure. To be clear, as I mentioned in today's earlier comment, I would advise removing the inline-initialization, viz.
int _hash = -1;
int _hasheq = -1;
with
int _hash;
int _hasheq;
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.
Hide
Alex Miller added a comment -

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).

Show
Alex Miller added a comment - 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).
Hide
thurston n added a comment -

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

Show
thurston n added a comment - 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
Hide
thurston n added a comment -

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

Surely not the last place either

Show
thurston n added a comment - Problem also in core.lang.ASeq#hashCode() and core.lang.ASeq#hasheq() - although thankfully without inline initialization Surely not the last place either
Hide
Alex Miller added a comment -

Feel free to update the patch if you like

Show
Alex Miller added a comment - Feel free to update the patch if you like

People

Vote (0)
Watch (5)

Dates

  • Created:
    Updated:
    Resolved: