Interlocked.Add Not Thread Safe with Longs on a 32bit system

[David]

Below are three classes for a console application. If put into three
separate files, the sub main() will launch multiple threads adding and
removing the same value. At the end we expect the value for all
Balances to be 0. When using an Integer things work fine. LONGS do
not.

We are using the Interlocked methods. I believe the Interlocked.Add
method is not thread safe when using longs on 32bit systems.

We are aware of Interlocked.Read (new to dotnet 2.0) which is required
for longs on 32bit systems, but is the dotnet framework missing a trick
here as Microsoft have introduced a new method for reading but haven't
got the .Add method to work correctly.

Note: This works find on single core single procssors.
But does not on muli-core or dual-core or hyper-threaded pentium 4.

Option Explicit On

Option Strict On



Module Module1





Public Tellers(99) As Teller



Private Threads(99) As Threading.Thread





Sub Main()



For i As Integer = 0 To 99

Tellers(i) = New Teller

Next





Do



For i As Integer = 0 To 99

Dim t As New Threading.Thread(AddressOf
Tellers(i).DoWork)

Threads(i) = t

t.Start()



Next



For i As Integer = 0 To 99

Threads(i).Join()

Next



Dim B2 As Integer = BankInt.Balance

Console.WriteLine("Int Balance " & B2)



Dim B1 As Long = BankLong.Balance

Console.WriteLine("Long Balance " & B1)



Loop





End Sub



End Module







Option Explicit On

Option Strict On



Imports System.Threading



Public Class Teller



Public Sub DoWork()

For i As Integer = 1 To 100000



BankInt.Deposit(50)

BankInt.Withdraw(50)



BankLong.Deposit(50)

BankLong.Withdraw(50)

Next



End Sub

End Class





Option Explicit On

Option Strict On



Imports System.Threading



Public Class BankLong



Private Shared _balance As Long



Public Shared ReadOnly Property Balance() As Long

Get

Return Interlocked.Read(_balance)

End Get

End Property



Public Shared Sub Deposit(ByVal Amount As Long)

Interlocked.Add(_balance, Amount)

End Sub



Public Shared Sub Withdraw(ByVal Amount As Long)

Interlocked.Add(_balance, -Amount)

End Sub



End Class



Public Class BankInt



Private Shared _balance As Integer



Public Shared ReadOnly Property Balance() As Integer

Get

Return _balance

End Get

End Property



Public Shared Sub Deposit(ByVal Amount As Integer)

Interlocked.Add(_balance, Amount)

End Sub



Public Shared Sub Withdraw(ByVal Amount As Integer)

Interlocked.Add(_balance, -Amount)

End Sub



End Class

 

[Brian Gideon]

David,

Interlocked.Add is thread-safe for Int64. So where's the problem? Take
a closer look at the Withdrawl method. You're doing a lock-free
negation of an Int64.

Brian

 

[Brian Gideon]

David,

Interlocked.Add is thread-safe for Int64. So where's the problem? Take
a closer look at the Withdrawl method. You're doing a lock-free
negation of an Int64.

Brian

Hmm...I believe I spoke too soon. I just noticed that Amount in the
Withdraw method is on the stack. I'll have to look at this in a little
more detail when I get time.

 

[Brian Gideon]

David,

I'm just not seeing a problem with the code. Well, except that you
really need a call Interlocked.Read in the BankInt.Balance property,
but that wouldn't cause the problem you're seeing. I'll try to
remember to run this code on my dual-core laptop (not with me at the
moment) which has VS 2005 on it.

What balance are seeing at the end with longs?

Brian

 

[Lucian Wischik]

We are using the Interlocked methods. I believe the Interlocked.Add
method is not thread safe when using longs on 32bit systems.

Nice find! I reproduced the same buggy behaviour in C# and C++/cli, so
I agree that it looks like a problem with the clr.

 

[David]

Hi Brian,

The value of the balance (long version) varies. We are not using
Interlocked.Read in the BankInt.Balance property as Interlocked.Read as
it only supports longs.

Regards

David

 

[Brian Gideon]

David,

It's strange that Add(Int32), Add(Int64), and Read(Int64) exist, but
Read(Int32) does not. I realize Read(Int32) isn't required for
atomicity's sake, but some kind of volatile read is so why not make the
API more consistent and add Read(Int32) that just calls
Thread.VolatileRead and call it good. Oh well, just use
Thread.VolatileRead instead. That will ensure that the current thread
sees changes made by other threads.

Again, other than that I don't see anything else wrong with your code.
Unless I'm missing something obvious I think you may have found a bug.
I guess I was a little too naive which is why I jumped the gun in my
first post...sorry about that.

Brian

 

[Lucian Wischik]

We are using the Interlocked methods. I believe the Interlocked.Add
method is not thread safe when using longs on 32bit systems.

Okay, I've filed it with the System.Threading team at microsoft, who
agree it looks like a bug as you say.

I was wondering about possible workarounds. On a 32bit machine, the
64bit Interlocked.Add is inevitably going to be implemented with a
busy-loop involving two interlocked operations anyway. So if you
wanted to write a fixed version of Interlocked.Add(Int64) yourself,
it'd look a bit like the following (untested):

Function MyInterlockedAdd(ByVal x As Long, ByVal i As Long)
retry:
Dim oldval As Long = Interlocked.Read(x)
Dim newval As Long = oldval + i
Dim fresholdval = Interlocked.CompareExchange(x, newval, oldval)
If fresholdval <> oldval Then GoTo retry
Return newval
End Function

 

[David]

Hi Lucian,

Nice idea with the Interlocked.CompareExchange. Should be able to get
the time to test this in a day or so.

I'll keep you posted

David

 

[Brian Gideon]

Function MyInterlockedAdd(ByVal x As Long, ByVal i As Long)
retry:
Dim oldval As Long = Interlocked.Read(x)
Dim newval As Long = oldval + i
Dim fresholdval = Interlocked.CompareExchange(x, newval, oldval)
If fresholdval <> oldval Then GoTo retry
Return newval
End Function

The variable x should be passed ByRef. Also, make sure to test i = 0
to prevent an infinite loop.

 

[Lucian Wischik]

The variable x should be passed ByRef. Also, make sure to test i = 0
to prevent an infinite loop.

Nice catch on the ByRef. But I don't think i=0 will cause an infinite
loop?

PS. I'd written "the solution inevitably involves two interlocked
operations". Just goes to show how bad I am at multithreaded
programming. The .net guy who's just fixed the bug came up with a
solution that involves only one interlocked read, a solution that's 1
byte smaller codesize than the current Interlocked.Add(Int64), that
saves multiple memory-reads, and that is at last correct!

It goes something like this (again, completely untested, because I'm
coming up with VB on the code while the .net person wrote in
assembler):

Dim val as Long = x
retry:
Dim oldval as Long = val
Dim newval as Long = oldval+i
val = Interlocked.CompareExchange(x,newval,oldval)
if val<>oldval Then GoTo retry
Return val


The idea here is this:

(1) We're just reading "x" on its own, without an Interlocked.Read.
This is fine. Even if someone came along and modified x while we were
half way through reading it, and we end up with an inconsistent "val",
this will be picked up by the CompareExchange statement. The ABA
problem of nonblocking data structures doesn't matter here because
we're doing arithmetic, not reusing pointers.

(2) Within the loop we don't need an explicit statement to re-read
"x". That's because Interlocked.CompareExchange will return the old
value of "x" anyway.

 

[Brian Gideon]

Nice catch on the ByRef. But I don't think i=0 will cause an infinite
loop?

Ah...yeah, you're right. I have no idea what I was thinking.

PS. I'd written "the solution inevitably involves two interlocked
operations". Just goes to show how bad I am at multithreaded
programming. The .net guy who's just fixed the bug came up with a
solution that involves only one interlocked read, a solution that's 1
byte smaller codesize than the current Interlocked.Add(Int64), that
saves multiple memory-reads, and that is at last correct!

Well, I missed it too so don't feel bad. Multithreaded programming is
insanely difficult. The added complexity of lock-free strategies makes
it seem down-right impossible.

I've seen worse bugs, but don't you think it's strange that a bug like
that made it into a release? That's why I was so quick to the blame
the OP's code at first.

 

[David]

Lucian

We have tried the Interlocked.CompareExchange solution which works
fine. Many thanks for the idea.

If you get any feed back from the System.Threading team at microsoft I
would be very interested to see what they say.

Public Class MyInterlocked
Public Shared Function Add(ByRef x As Long, ByVal y As Long) As
Long
Dim val As Long = x
retry:
Dim oldVal As Long = val
Dim newVal As Long = oldVal + x
val = Interlocked.CompareExchange(x, newVal, oldVal)
If val <> oldVal Then GoTo retry

Return val

End Function
End Class