Implementing Interlocked for 64-bit values

NTDEV
1

I would appreciate an advice in creating my own interlocked operation for 64-bit values.
I do a busy waiting using the standard Interlocked operations.

enum
{
LOCK_TAKEN = 0x51ab3456,
LOCK_FREE = 0x4d3e76bb
};

#define SA_UTILS_INTERLOCKED_CS_ENTER(pLock) \
{ \
while (InterlockedCompareExchange((pLock), LOCK_TAKEN, LOCK_FREE) != LOCK_FREE); \
}

#define SA_UTILS_INTERLOCKED_CS_EXIT(pLock) \
{ \
LONG prevLockValue = InterlockedCompareExchange((pLock), LOCK_FREE, LOCK_TAKEN); \
\
SAUTILS_ASSERT(prevLockValue == LOCK_TAKEN); \
}

VOID SaUtilsInitInterlocked64Lock(PLONG pLock)
{
*pLock = LOCK_FREE;
}

UINT64 SaUtilsInterlockedExchangeAdd64(PUINT64 pTarget, UINT64 value, PLONG pLock)
{
UINT64 result = 0;

SA_UTILS_INTERLOCKED_CS_ENTER(pLock);

result = *pTarget;
*pTarget += value;

SA_UTILS_INTERLOCKED_CS_EXIT(pLock);

return result;
}

UINT64 SaUtilsInterlockedGet64(PUINT64 pTarget, PLONG pLock)
{
UINT64 result = 0;

SA_UTILS_INTERLOCKED_CS_ENTER(pLock);

result = *pTarget;

SA_UTILS_INTERLOCKED_CS_EXIT(pLock);

return result;
}

UINT64 SaUtilsInterlockedExchange64(PUINT64 pTarget, UINT64 value, PLONG pLock)
{
UINT64 prevValue = 0;

SA_UTILS_INTERLOCKED_CS_ENTER(pLock);

prevValue = *pTarget;
*pTarget = value;

SA_UTILS_INTERLOCKED_CS_EXIT(pLock);

return prevValue;
}

However,
from time to time I receive a deadlock in SaUtilsInterlockedExchangeAdd64.
I never get out of the while loop and the value of the lock is LOCK_TAKEN.
It’s like somebody has never set the lock to LOCK_FREE.
It’s not clear how this can happen.

I would appreciate your advice.

Thanks,
Alex.

2

You’ve implemented a crappy spinlock. Spinning on an interlocked operation is not a very good idea. By the way the 64bit interlocked operations already exist. (See ntddk.h InterlockedCompareExchangeAcquire64 for example.)

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:bounce-296426-
xxxxx@lists.osr.com] On Behalf Of xxxxx@storeage.com
Sent: Sunday, August 05, 2007 2:23 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Implementing Interlocked for 64-bit values

I would appreciate an advice in creating my own interlocked operation
for 64-bit values.
I do a busy waiting using the standard Interlocked operations.

enum
{
LOCK_TAKEN = 0x51ab3456,
LOCK_FREE = 0x4d3e76bb
};

#define SA_UTILS_INTERLOCKED_CS_ENTER(pLock)
\
{
\
while (InterlockedCompareExchange((pLock), LOCK_TAKEN,
LOCK_FREE) != LOCK_FREE); \
}

#define SA_UTILS_INTERLOCKED_CS_EXIT(pLock)
\
{
\
LONG prevLockValue = InterlockedCompareExchange((pLock),
LOCK_FREE, LOCK_TAKEN); \

\
SAUTILS_ASSERT(prevLockValue == LOCK_TAKEN);
\
}

VOID SaUtilsInitInterlocked64Lock(PLONG pLock)
{
*pLock = LOCK_FREE;
}

UINT64 SaUtilsInterlockedExchangeAdd64(PUINT64 pTarget, UINT64 value,
PLONG pLock)
{
UINT64 result = 0;

SA_UTILS_INTERLOCKED_CS_ENTER(pLock);

result = *pTarget;
*pTarget += value;

SA_UTILS_INTERLOCKED_CS_EXIT(pLock);

return result;
}

UINT64 SaUtilsInterlockedGet64(PUINT64 pTarget, PLONG pLock)
{
UINT64 result = 0;

SA_UTILS_INTERLOCKED_CS_ENTER(pLock);

result = *pTarget;

SA_UTILS_INTERLOCKED_CS_EXIT(pLock);

return result;
}

UINT64 SaUtilsInterlockedExchange64(PUINT64 pTarget, UINT64 value,
PLONG pLock)
{
UINT64 prevValue = 0;

SA_UTILS_INTERLOCKED_CS_ENTER(pLock);

prevValue = *pTarget;
*pTarget = value;

SA_UTILS_INTERLOCKED_CS_EXIT(pLock);

return prevValue;
}

However,
from time to time I receive a deadlock in
SaUtilsInterlockedExchangeAdd64.
I never get out of the while loop and the value of the lock is
LOCK_TAKEN.
It’s like somebody has never set the lock to LOCK_FREE.
It’s not clear how this can happen.

I would appreciate your advice.

Thanks,
Alex.

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

3

> I do a busy waiting using the standard Interlocked operations.

What can you possibly archieve this way??? Look - intelocked operation in itself is done by a *SINGLE* instruction, and interlocked function insures that bus is locked while this instruction is executed. Unless this instruction is XCHG, which results in automatic bus locking anyway, interlocked function insures bus locking by pre-pending LOCK prefix to the target instruction. All code in InterlockedXXX function is just a wrapper around this instruction.

I hope by now you understand that 2 independent InterlockedXXX calls just cannot make your
operation interlocked - instead, there are just 2 memory accesses that are completely independent from one another. If you want 64-bit operation to be interlocked, you have to do it with a single instruction. However, don’t forget that using assembly instructions in your code makes it platform-specific, so that, if you want your code to be portable across platforms, use a spinlock instead of custom 64-bit interlocked functions…

Anton Bassov

4

Thanks for your replies.
I realize that my code here is quite crappy.
Mark, I do not find the Interlocked64 functions in my DDK (3790.1830).
Anton, thanks, I guess I should have used a spinlock.

Also, I have a theory why this does not work.
The problem is “priority inversion”.
If I call my function from high IRQL and there is a thread inside with a lower IRQL,
then the higher IRQL thread will not give the lower one a chance to release the “lock”.
I do not have hard evidence, since I don’t see the “lower IRQL thread” in WinDbg.
I see only the one, which deadlocks (and has a high IRQL).

I guess this is quite an amateur error.
I will just use good old spinlocks.

Thanks!

5

Alexander,

If I call my function from high IRQL and there is a thread inside with a lower IRQL,
then the higher IRQL thread will not give the lower one a chance to release the “lock”.
I do not have hard evidence, since I don’t see the “lower IRQL thread” in WinDbg.

IRQL applies only to the CPU and not to the thread. If CPU’s IRQL>= DPC level , it is unable to run any thread, apart from the one it currently executes, until IRQL drops below DPC level - only at this point some other thread may be scheduled to run on a given CPU.

I will just use good old spinlocks.

When you use a spinlock, you synchronize not other threads but with other CPUs - once operation, protected by a spinlock, runs at elevated IRQL, no other thread can run on a given CPU until IRQL
drops below DPC level. The only thing that a given CPU is able to process while holding a spinlock
is its current operation, plus interrupts. This is why you cannot use “regular” spinlocks in order to synchronize with ISR.

When you use dispatcher objects (event,mutexes,etc), you are synchronizing with other threads,
regardless of CPU they run on.

Anton Bassov

6

Anton,
you are of course right.
“Lower/higher IRQL thread” has no meaning.
Spinlocks synchronize between CPUs and not other threads.

I am just trying to prove a theory that there was a thread inside my “lock”
and the CPU was running at PASSIVE_LEVEL.
Then there was another thread that raised the CPU’s IRQL and tried to acquire the “lock”,
which caused a deadlock.
So I should still see both my threads in WinDbg.
I see the one that tries to acquire the “lock”.
But I do not see the one that holds the “lock”.

The IRQLs are:
0: kd> !irql 0
Debugger saved IRQL for processor 0x0 – 28 (CLOCK2_LEVEL)
0: kd> !irql 1
Debugger saved IRQL for processor 0x1 – 0 (LOW_LEVEL)

Thanks anyway,
Alex.

7

Please note that you will not see two different threads.
You will see one thread that is holding the lock, and doing the work.
This same thread will become* a DPC and will try to take the lock.

Thanks
Tzachi
Becoming a DPC means that the scheduler has taken your time slice and is
running a DPC on your processor.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of
xxxxx@storeage.com
Sent: Sunday, August 05, 2007 11:35 PM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Implementing Interlocked for 64-bit values

Anton,
you are of course right.
“Lower/higher IRQL thread” has no meaning.
Spinlocks synchronize between CPUs and not other threads.

I am just trying to prove a theory that there was a thread
inside my “lock”
and the CPU was running at PASSIVE_LEVEL.
Then there was another thread that raised the CPU’s IRQL and
tried to acquire the “lock”, which caused a deadlock.
So I should still see both my threads in WinDbg.
I see the one that tries to acquire the “lock”.
But I do not see the one that holds the “lock”.

The IRQLs are:
0: kd> !irql 0
Debugger saved IRQL for processor 0x0 – 28 (CLOCK2_LEVEL)
0: kd> !irql 1
Debugger saved IRQL for processor 0x1 – 0 (LOW_LEVEL)

Thanks anyway,
Alex.

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online
at http://www.osronline.com/page.cfm?name=ListServer

8

You should upgrade your ddk to the WDK 6000 release. The interlocked64 operations are only available for 64bit target OS’s. The best documentation is over in the Visual Studio 2005 docs section for compiler intrinsic, the DDK docs are a bit stale and incomplete.

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:bounce-296433-
xxxxx@lists.osr.com] On Behalf Of xxxxx@storeage.com
Sent: Sunday, August 05, 2007 4:05 PM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Implementing Interlocked for 64-bit values

Thanks for your replies.
I realize that my code here is quite crappy.
Mark, I do not find the Interlocked64 functions in my DDK (3790.1830).
Anton, thanks, I guess I should have used a spinlock.

Also, I have a theory why this does not work.
The problem is “priority inversion”.
If I call my function from high IRQL and there is a thread inside with
a lower IRQL,
then the higher IRQL thread will not give the lower one a chance to
release the “lock”.
I do not have hard evidence, since I don’t see the “lower IRQL thread”
in WinDbg.
I see only the one, which deadlocks (and has a high IRQL).

I guess this is quite an amateur error.
I will just use good old spinlocks.

Thanks!

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

9

Tzachi,
I suspected something like this.

Thanks,
Alex.