Is LockFreeBucket tryConsumeImpl Thread Safe?

[zhangchengkai826]

protected boolean tryConsumeImpl(long tokensToConsume) {
    StateWithConfiguration previousState = stateRef.get(); // <- At Time T2: thread B reads the reference to StateWithConfiguration object 
    StateWithConfiguration newState = previousState.copy();  // <- At Time T3: thread B reads members of StateWithConfiguration object X
    long currentTimeNanos = timeMeter.currentTimeNanos();

    while (true) {
        newState.refillAllBandwidth(currentTimeNanos); 
        long availableToConsume = newState.getAvailableTokens();
        if (tokensToConsume > availableToConsume) {
            return false;
        }
        newState.consume(tokensToConsume);
        if (stateRef.compareAndSet(previousState, newState)) { // <- At Time T1: thread A publishes StateWithConfiguration object X
            return true;
        } else {
            previousState = stateRef.get();
            newState.copyStateFrom(previousState);  // <- At Time T0: thread A writes to members of StateWithConfiguration object X
        }
    }
}

However, members of StateWithConfiguration are not marked as final.

According to Java Language Specs:

final fields also allow programmers to implement thread-safe immutable objects without synchronization. A thread-safe immutable object is seen as immutable by all threads, even if a data race is used to pass references to the immutable object between threads. This can provide safety guarantees against misuse of an immutable class by incorrect or malicious code. final fields must be used correctly to provide a guarantee of immutability.

An object is considered to be completely initialized when its constructor finishes. A thread that can only see a reference to an object after that object has been completely initialized is guaranteed to see the correctly initialized values for that object's final fields.

The usage model for final fields is a simple one: Set the final fields for an object in that object's constructor; and do not write a reference to the object being constructed in a place where another thread can see it before the object's constructor is finished. If this is followed, then when the object is seen by another thread, that thread will always see the correctly constructed version of that object's final fields. It will also see versions of any object or array referenced by those final fields that are at least as up-to-date as the final fields are.

So, I think the writes at time T0 may not be visible to the reads at time T2, and thus this method is not thread safe.

Am I right? Or I just misunderstood the java specification..

[vladimir-bukhtoyarov]

@zhangchengkai826 hello,

JMM is the hardest part of java specification. Typically regular developer need to read it 10-20 times in combination with reading non-formal JMM explanations like this Java Memory Model Pragmatics and others.

Let's check the statement that reading in action T3 does not see the write that was made by action T0.
We have two thread A and B and four actions:

• T0 in thread A - write to a field X of StateWithConfiguration.
• T1 in thread A - the write of reference to StateWithConfiguration.
• T2 in thread B - the read of reference to StateWithConfiguration.
• T3 in thread B - read of a field X of StateWithConfiguration.

It worse to mention the following facts about the actions above:

• T1 is a synchronized action according to 17.4.2 Actions that says Volatile write. A volatile write of a variable. and writing to AtomicReference produces the same JMM effects as volatile write(according to javadocs).
• T2 is a synchronized action according to 17.4.2 Actions that says Volatile read. A volatile read of a variable. and reading from AtomicReference produces the same JMM effects as volatile read(according to javadocs).
• T1 is related to T2 by synchronized-with relation according to 17.4.4. Synchronization Order that says A write to a volatile variable v (§8.3.1.4) synchronizes-with all subsequent reads of v by any thread (where "subsequent" is defined according to the synchronization order).

To confirm our statement that it is possible to have a valid execution where T0 is not related with happens-before with T3 we need to provide a possible example of execution which is not contradictory with happens-before rules. Also, it needs to keep in mind that following happens-before relations between actions above:

• Obviously, T0 happen before T1 If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).
• Because of the same reason, T2 happen before T3 If x and y are actions of the same thread and x comes before y in program order, then hb(x, y)
• T1 happen before T2 according to 17.4.5. Happens-before Order that says If an action x synchronizes-with a following action y, then we also have hb(x, y).

First attemp:

	thread A	thread B
1	T1
2		T2
3		T3
4	T0

In the table above T0 is not hb to T3, but execution above is not valid because as was mentioned above T0 related with hb to T1.

Second attemp:

	thread A	thread B
1		T2
2		T3
3	T0
4	T1

In the table above T0 is not hb to T3, but execution above is not valid because as was mentioned above T1 related with hb to T2.

Third attemp:

	thread A	thread B
1		T3
2	T0
3	T1
4		T2

In the table above T0 is not hb to T3, but execution above is not valid because as was mentioned above T2 related with hb to T3.

... So, you can continue this exercise but all attempts to build an order where there is not hb(T0, T3) will be failed.
Of coarse we need to provide execution order where hb(T0, T3) = true, this execution will be following:

	thread A	thread B
1	T0
2	T1
3		T2
4		T3

Because of the transient property of happens-before order and hb(T0, T1) and hb(T1, T2) we have that hb(T0, T2). Also because hb(T2, T3) we have that hb(T0, T3). So our code is correct because we found one execution where hb(T0, T3) and failed to find any execution where not hb(T0, T3).

P.S.
I know it was long explanation. In real life developers do not verify parallel code in this way. We have just a strong rule:

If a thread T1 sees a value written to a volatile variable(or atomic reference) by thread T2, that also T1 sees all other writes to memory that T2 had made before wrote value to this volatile variable(or atomic reference).

According to your original question this rule says that if thread B sees T1 it also sees T0 as well.

[zhangchengkai826]

Thanks for your detailed reply. Now I think I know where I was wrong. I only considered the semantics of final but overlooked the effects of volatile write/read. JMM is harder than I thought, and I will try to be more familiar with it. Thanks for the article link you provided at the begging of your reply, it is a great learning material.