Skip to main content

Concurrency bug in Collections.java (build 65)

6 replies [Last post]
doronrajwan
Offline
Joined: 2005-06-30
Points: 0

Collections.java, line 412:
- The varaible 'r' is non-volatile, so there is no safe-publication between concurrent threads.
- Inside Random, the 'seed' variable is not final, so Random is not an immutable class.
- Thus, a second thread can see null 'seed', which will cause NullPointerException.

Doron.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
briangoetz
Offline
Joined: 2003-06-11
Points: 0

I agree that this could throw NPE.

There are two bugs here: one is that Collections uses a data race to lazily initialize the cached Random; the second is that 'seed' in Random should be final. Either would fix the problem.

dholmes
Offline
Joined: 2005-12-11
Points: 0

I stand corrected. My apologies.

A bug now exists for this:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6379897

and it should appear soon.

dholmes
Offline
Joined: 2005-12-11
Points: 0

The race in Collections is benign: at worst more than one instance of Random will be constructed.

A NullPointerException is not possible due to the volatile accesses in the Random constructors.

tackline
Offline
Joined: 2003-06-19
Points: 0

> The race in Collections is benign: at worst more than
> one instance of Random will be constructed.

Agreed. Although the nested class static initialiser hack^W workaround wouldn't be out of place.

> A NullPointerException is not possible due to the
> volatile accesses in the Random constructors.

I disagree with you analysis here.

The two volatiles involved are the static seedUniquifier variable, and the hidden volatile in the seed AtomicInteger. seedUniquifier is finished with before so much as the Object constructor is run, and is therefore irrelevant.

The this.seed AtomicInteger is written before an effective volatile write (a set operation on the object itself). This will ensure that after this.seed.get() is called, then the calling thread will definitely see the Random object as initialised. Unfortunately, to call this.seed.get() the thread would first have read this.seed.

It's broke.

As is Random's Serialisation.

Although I wouldn't want to have to actually demonstrate the fault in practice.

tackline
Offline
Joined: 2003-06-19
Points: 0

I mean AtomicLong, not AtomicInteger.

Now I look at it again, that compareAndSet should be replaced by weakCompareAndSet.

tackline
Offline
Joined: 2003-06-19
Points: 0

More of a bug in Random than Collections, I think.

My solution is to add a base class to Random to create the final atomic variable, like so:

abstract class RandomBase { // Does not implement Serializable
final AtomicLong seed;
RandomBase(long seed) {
this.seed = new AtomicLong(seed);
}
// For serialization only.
RandomBase() {
this(0L);
}
}

Change the Random constructor (long) to use the base:

public Random(long seed) {
super((seed ^ multiplier) & mask);
}

Remove the extraneous initialisation on haveNextNextGaussian. And set rather than create the atomic in readObject (which should probably also be synchronised).