compiler intrinsic ExInterlockedRemoveEntryList

NTDEV
1

Hello,

I have been tasked to upgrade an exiting x86 WDM driver to a Windows x64 system. I am using the WDK 7600.16385.0 for the build process. The 32 bit version of the driver had some inline assembly code to implement the ExInterlockedRemoveEntryList() routine, which is not available in Windows.

The routine below needs to lock out interrupts as the list can be manipulated in both ISR and non-ISR context. It also needs to be multi-processor safe.

VOID ExInterlockedRemoveEntryList(PLIST_ENTRY Entry, PKSPIN_LOCK spLock)
{

#if defined(X86)

_asm {
mov edx, spLock // set pointer to lock
waitLoop:
pushfd // save current CPU flags
cli // clear the CPU interrupt mask
lock bts word ptr [edx], 0 // can we have the lock?
jnb lockHeld // yes, go do something while protected
popfd // restore the CPU flags (permit an interrupt)
jmp waitLoop // loop till lock held
lockHeld:
push edx // save index pointer
};
PLIST_ENTRY Flink=Entry->Flink,
Blink=Entry->Blink;

Blink->Flink = Flink;
Flink->Blink = Blink;

_asm {
pop edx
mov byte ptr [edx], 0 // Release the lock
popfd // Restore the CPU flags
}

#elif defined(AMD64) /*X64*/

KSPIN_LOCK prevValue,prevCopy;

_disable();

prevValue = *spLock;
do {
prevCopy = prevValue;
/* Compare current value of spLock with 0. If it 0 exchange it
* with 1. If it is already 1 don’t exchange it with 0, as it implies
* spLock has been taken by somebody else. In that case spin here
* until you get spLock.
*/
prevValue = InterlockedCompareExchange64((volatile LONG64 *)spLock,1,0);

/* When you get out of the while, you have the lock.
*/
}while(prevValue != prevCopy);

RemoveEntryList(Entry); // Remove the entry from it’s list

InterlockedExchange64((volatile LONG64 *)spLock,0);

_enable();

#endif

I am trying to use compiler intrinsic code in place of the assembly. I have have come across an issue where I have replaced the cli and re-enabling of interrupts with the _disable() and _enable(). I have a really old SDK for Windows XP and Visual Studio 2003 and the WDK build is unable to resolve these routines.

The MSDN documentation on _enable() and _disable() suggested that I could include <intrin.h> with Visual Studio 2005 for x64 architecture. Here, Would moving to VS2005 help in resolving the problem? Or is there a different approach for ExInterlockedRemoveEntryList?

Windows, probably doesn’t expect drivers to use ExInterlockedRemoveEntryList, but what is the possibility that the routine that is implemented for the x64 system has any chances of working. Insertion into the lists is performed via windows provided ExInsert… routines.

Any advise will be helpful.

Thanks,
Amit</intrin.h>

2

You should to use this code in a DPC routine not in ISR.
ISR should provide only checking interrupt and clear it by working only with hardware registers and schedule DPC.
In DPC you could safely use SpinLock or ExInterlockedInsertTailList.
But if you really want to provide synchronization to a List, which could be accessed in ISR, you could use KeSynchronizeExecution.

Igor Sharovar

3

Do you know why there is no ExInterlockedRemoveEntryList? Because such a
function can’t be implemented.

You need to supply a valid address of a list entry. But for the entry to
remain valid, you need to hold the spinlock before you found an entry and
before call the function. You can’t just pick an entry from the list and
hope nobody else pulled it from there in the meantime.

Change your code to use Windows ExInterlockedInsert* and
ExInterlockedRemove*. Only after you remove an entry from the list, you may
claim its ownership.

wrote in message news:xxxxx@ntdev…
> Hello,
>
> I have been tasked to upgrade an exiting x86 WDM driver to a Windows x64
> system. I am using the WDK 7600.16385.0 for the build process. The 32 bit
> version of the driver had some inline assembly code to implement the
> ExInterlockedRemoveEntryList() routine, which is not available in Windows.
>
> The routine below needs to lock out interrupts as the list can be
> manipulated in both ISR and non-ISR context. It also needs to be
> multi-processor safe.
>
> VOID ExInterlockedRemoveEntryList(PLIST_ENTRY Entry, PKSPIN_LOCK spLock)
> {
>
> #if defined(X86)
>
> _asm {
> mov edx, spLock // set pointer to lock
> waitLoop:
> pushfd // save current CPU flags
> cli // clear the CPU interrupt mask
> lock bts word ptr [edx], 0 // can we have the lock?
> jnb lockHeld // yes, go do something while protected
> popfd // restore the CPU flags (permit an interrupt)
> jmp waitLoop // loop till lock held
> lockHeld:
> push edx // save index pointer
> };
> PLIST_ENTRY Flink=Entry->Flink,
> Blink=Entry->Blink;
>
> Blink->Flink = Flink;
> Flink->Blink = Blink;
>
> _asm {
> pop edx
> mov byte ptr [edx], 0 // Release the lock
> popfd // Restore the CPU flags
> }
>
> #elif defined(AMD64) /X64/
>
> KSPIN_LOCK prevValue,prevCopy;
>
> _disable();
>
> prevValue = spLock;
> do {
> prevCopy = prevValue;
> / Compare current value of spLock with 0. If it 0 exchange it
> * with 1. If it is already 1 don’t exchange it with 0, as it implies
> * spLock has been taken by somebody else. In that case spin here
> * until you get spLock.
> */
> prevValue = InterlockedCompareExchange64((volatile LONG64 )spLock,1,0);
>
> / When you get out of the while, you have the lock.
> */
> }while(prevValue != prevCopy);
>
>
> RemoveEntryList(Entry); // Remove the entry from it’s list
>
> InterlockedExchange64((volatile LONG64 *)spLock,0);
>
> _enable();
>
> #endif
>
> I am trying to use compiler intrinsic code in place of the assembly. I
> have have come across an issue where I have replaced the cli and
> re-enabling of interrupts with the _disable() and _enable(). I have a
> really old SDK for Windows XP and Visual Studio 2003 and the WDK build is
> unable to resolve these routines.
>
> The MSDN documentation on _enable() and _disable() suggested that I could
> include <intrin.h> with Visual Studio 2005 for x64 architecture. Here,
> Would moving to VS2005 help in resolving the problem? Or is there a
> different approach for ExInterlockedRemoveEntryList?
>
>
> Windows, probably doesn’t expect drivers to use
> ExInterlockedRemoveEntryList, but what is the possibility that the routine
> that is implemented for the x64 system has any chances of working.
> Insertion into the lists is performed via windows provided ExInsert…
> routines.
>
> Any advise will be helpful.
>
> Thanks,
> Amit
>
>
>
></intrin.h>

4

Nonsense.

It’s entirely possible and even reasonable, depending on the circumstances, to store a pointer to an entry that can be used later to safely remove an entry from the list.

I had this exact same argument with Cutler once. It turns out that the reason Windows doesn’t have an ExInterlockedRemoveEntryList is because it’s too easy for people to misuse. And Cutler doesn’t want one.

But it certainly would be a reasonable and useful function, in certain limited circumstances.

Peter
OSR

5

I think you know by now that programmers will misuse a function if there is
just a little possibility of that… Too many examples… Starting with
MmGetPhysicalAddress…

wrote in message news:xxxxx@ntdev…
>


>
> Nonsense.
>
> It’s entirely possible and even reasonable, depending on the
> circumstances, to store a pointer to an entry that can be used later to
> safely remove an entry from the list.
>
> I had this exact same argument with Cutler once. It turns out that the
> reason Windows doesn’t have an ExInterlockedRemoveEntryList is because
> it’s too easy for people to misuse. And Cutler doesn’t want one.
>
> But it certainly would be a reasonable and useful function, in certain
> limited circumstances.
>
> Peter
> OSR
>
>

6

Perhaps then we should eliminate the entire DDI?

Mark Roddy

On Wed, Feb 24, 2010 at 9:55 AM, Alexander Grigoriev
wrote:
> I think you know by now that programmers will misuse a function if there is
> just a little possibility of that… Too many examples… Starting with
> MmGetPhysicalAddress…
>
> wrote in message news:xxxxx@ntdev…
>>


>>
>> Nonsense.
>>
>> It’s entirely possible and even reasonable, depending on the
>> circumstances, to store a pointer to an entry that can be used later to
>> safely remove an entry from the list.
>>
>> I had this exact same argument with Cutler once. ?It turns out that the
>> reason Windows doesn’t have an ExInterlockedRemoveEntryList is because
>> it’s too easy for people to misuse. ?And Cutler doesn’t want one.
>>
>> But it certainly would be a reasonable and useful function, in certain
>> limited circumstances.
>>
>> Peter
>> OSR
>>
>>
>
>
>
> —
> 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
>

7

I just curious how could people misuse ExInterlockedRemoveEntryList if such function would use a spinlock? ExInterlockedInsert* and ExInterlockedRemoveHeadList use spinlocks too.

Igor Sharovar

8

xxxxx@hotmail.com wrote:

I just curious how could people misuse ExInterlockedRemoveEntryList if such function would use a spinlock? ExInterlockedInsert* and ExInterlockedRemoveHeadList use spinlocks too.

Alexander already described the problem eloquently. In the case of
InsertXxx and RemoveHead, everything they need in order to do their job
is part of the list. When you wrap them in a spinlock, you can be
assured that the list will never be left in an inconsistent state.

RemoveEntryList is a bit different, because it operates on TWO pieces of
data: the list, and the entry you want to remove. RemoveEntryList can
protect the list pointers, but it cannot assert that the entry you want
to remove is still in the list. THAT’S the key point. To be safe,
you’d need a spin lock from the time you found the entry until the time
you removed it.

As Peter pointed out, there are safe ways to use RemoveEntryList, but it
requires knowledge that the API doesn’t have.

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

9

>WDK 7600.16385.0 for the build process. The 32 bit version of the driver had some inline assembly

code to implement the ExInterlockedRemoveEntryList() routine, which is not available in Windows.

Throw away the assembler and rewrite the routine in C. This is the simplest, and I disbelieve you will be able to outperform the compiler’s optimizer.

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

10

Maxim,

Do you mean don’t use intrinsics?

I don’t want to use any assembly code (as used by the previous
programmer for X86), that was the reason I was attempting to enclose the
code inside #elif AMD64 with _disable() and _enable(). Can I even use
_enable() and _disable() in the WDM driver? How do I link in these
routines? The WDK does not have an intrin.h. I noticed it is Visual
Studio. Can this intrin.h be used.

Thanks.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Maxim S.
Shatskih
Sent: Wednesday, February 24, 2010 2:40 PM
To: Windows System Software Devs Interest List
Subject: Re:[ntdev] compiler intrinsic ExInterlockedRemoveEntryList

WDK 7600.16385.0 for the build process. The 32 bit version of the
driver had some inline assembly
code to implement the ExInterlockedRemoveEntryList() routine, which is
not available in Windows.

Throw away the assembler and rewrite the routine in C. This is the
simplest, and I disbelieve you will be able to outperform the compiler’s
optimizer.

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

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

11

>code inside #elif AMD64 with _disable() and _enable().

Raise the IRQL to HIGL_LEVEL instead.

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

12

Lemme guess, the code also has a SPIN_TILL_HELL_FREEZES_OVER macro? One of
my more colorful attempts at defining a loop. Look at the Revision History
and you most likely will see GLittle. That’s MY code written during an early
arrogant period. It really is true that things come back to byte you in the
backside.

Personally, I’d scrap the bus and peer to peer drivers, scrap the C++
nonsense, and write them using WDF, and the latest WDK. WDF will do the
queuing for you as it should, much easier than you can, or I tried, and in
the end you will have a better, forward compatible, product.

Gary G. Little
H (952) 223-1349
C (952) 454-4629
xxxxx@comcast.net

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Amit Nadgar
Sent: Wednesday, February 24, 2010 5:30 PM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] compiler intrinsic ExInterlockedRemoveEntryList

Maxim,

Do you mean don’t use intrinsics?

I don’t want to use any assembly code (as used by the previous
programmer for X86), that was the reason I was attempting to enclose the
code inside #elif AMD64 with _disable() and _enable(). Can I even use
_enable() and _disable() in the WDM driver? How do I link in these
routines? The WDK does not have an intrin.h. I noticed it is Visual
Studio. Can this intrin.h be used.

Thanks.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Maxim S.
Shatskih
Sent: Wednesday, February 24, 2010 2:40 PM
To: Windows System Software Devs Interest List
Subject: Re:[ntdev] compiler intrinsic ExInterlockedRemoveEntryList

WDK 7600.16385.0 for the build process. The 32 bit version of the
driver had some inline assembly
code to implement the ExInterlockedRemoveEntryList() routine, which is
not available in Windows.

Throw away the assembler and rewrite the routine in C. This is the
simplest, and I disbelieve you will be able to outperform the compiler’s
optimizer.

–
Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

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

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

__________ Information from ESET Smart Security, version of virus signature
database 4893 (20100224) __________

The message was checked by ESET Smart Security.

http://www.eset.com

__________ Information from ESET Smart Security, version of virus signature
database 4893 (20100224) __________

The message was checked by ESET Smart Security.

http://www.eset.com

13

On Feb 24, 2010, at 5:44 PM, Gary G. Little wrote:

Lemme guess, the code also has a SPIN_TILL_HELL_FREEZES_OVER macro? One of
my more colorful attempts at defining a loop. Look at the Revision History
and you most likely will see GLittle. That’s MY code written during an early
arrogant period. It really is true that things come back to byte you in the
backside.

You got to be kidding !

-pro

14

Not at all. I matched the code to source files I maintain to provide
support. I got a contract with them shortly after I was laid off in 2002,
and keep the files incase something goes bump in the night and I need to fix
something.

Gary G. Little
H (952) 223-1349
C (952) 454-4629
xxxxx@comcast.net

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
Sent: Wednesday, February 24, 2010 8:19 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] compiler intrinsic ExInterlockedRemoveEntryList

On Feb 24, 2010, at 5:44 PM, Gary G. Little wrote:

Lemme guess, the code also has a SPIN_TILL_HELL_FREEZES_OVER macro? One of
my more colorful attempts at defining a loop. Look at the Revision History
and you most likely will see GLittle. That’s MY code written during an
early
arrogant period. It really is true that things come back to byte you in
the
backside.

You got to be kidding !

-pro

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

__________ Information from ESET Smart Security, version of virus signature
database 4893 (20100224) __________

The message was checked by ESET Smart Security.

http://www.eset.com

__________ Information from ESET Smart Security, version of virus signature
database 4895 (20100225) __________

The message was checked by ESET Smart Security.

http://www.eset.com

15

Oh, I see …

You had to support whatever they had, but not coming up with a very innovative name for a macro that defines a loop in kernel mode component! – I know there are people who goes miles to defend assembler code like the one posted by OP and names like the one you cited. But both of them are bad practices. For most of the assembler codes, it lacks justifications. For defining a loop using such a macro is at best for debugging then at the stroke of a pen it is undefed - still noise to the inline code unless someone take sed like flat substitution to make it blank.

-pro

On Feb 25, 2010, at 7:02 AM, Gary G. Little wrote:

Not at all. I matched the code to source files I maintain to provide
support. I got a contract with them shortly after I was laid off in 2002,
and keep the files incase something goes bump in the night and I need to fix
something.

Gary G. Little
H (952) 223-1349
C (952) 454-4629
xxxxx@comcast.net

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
Sent: Wednesday, February 24, 2010 8:19 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] compiler intrinsic ExInterlockedRemoveEntryList

On Feb 24, 2010, at 5:44 PM, Gary G. Little wrote:

> Lemme guess, the code also has a SPIN_TILL_HELL_FREEZES_OVER macro? One of
> my more colorful attempts at defining a loop. Look at the Revision History
> and you most likely will see GLittle. That’s MY code written during an
early
> arrogant period. It really is true that things come back to byte you in
the
> backside.
>

You got to be kidding !

-pro

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

__________ Information from ESET Smart Security, version of virus signature
database 4893 (20100224) __________

The message was checked by ESET Smart Security.

http://www.eset.com

__________ Information from ESET Smart Security, version of virus signature
database 4895 (20100225) __________

The message was checked by ESET Smart Security.

http://www.eset.com

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

16

>Alexander already described the problem eloquently. In the case of InsertXxx and RemoveHead, >everything they need in order to do their job is part of the list. When you wrap them in a spinlock, you >can be assured that the list will never be left in an inconsistent state. RemoveEntryList is a bit >different, because it operates on TWO pieces of data: the list, and the entry you want to remove. >RemoveEntryList can protect the list pointers, but it cannot assert that the entry you want to remove is >still in the list. THAT’S the key point. To be safe, you’d need a spin lock from the time you found the >entry until the time you removed it.
Thanks Tim. I initially missed differences in implementation InsertXxx and RemoveEntryList.

Igor Sharovar

17

>>code inside #elif AMD64 with _disable() and _enable().

Raise the IRQL to HIGL_LEVEL instead.

How is it legitimate and safe call KeRaiseIrql with HIGL_LEVEL as a new IRQL, especially in multiprocessor environment ? Why do we need to call KeSynchronizeExecution if we could just rise IRQ?

Igor Sharovar

18

wrote in message news:xxxxx@ntdev…
>>>code inside #elif AMD64 with _disable() and _enable().
>>Raise the IRQL to HIGL_LEVEL instead.
>
> How is it legitimate and safe call KeRaiseIrql with HIGL_LEVEL as a new
> IRQL, especially in multiprocessor environment ?

How KeRaiseIrql(HIGH_LEVEL) can be such a big deal - especially in
multiprocessor environment?
There are several CPUs, all horribly fast, compared to what was on the scene
20 years ago.
KeRaiseIrql(HIGH_LEVEL) is just one quick “cli” instruction.

>Why do we need to call KeSynchronizeExecution if we could just rise IRQ?

It also acquires the internal spinlock of the interrupt object.

–pa

19

Huh?

I’m not sure I understand the question, so I’ll take it as face value and answer that.

Because the operations aren’t equivalent. KeRaiseIrql does what the name suggests… it raises the IRQL and nothing more. KeSynchronizeExecution acquires the interrupt spin lock (which implies raising the IRQL to the driver’s synchronize IRQL). Both useful operations, but not the same.

Consider that you could (COULD, I’m not recommending this, but it’s entirely possible) build your own locking primitive using a the IRQL of your choice and an interlocked bit test and set operation (or interlocked exchange or… you pick one).

You’re asserting that KeRaiseIrql to IRQL HIGH_LEVEL is special cased in Windows? Are you sure of this?

Peter
OSR

20

“Pavel A.” wrote in message news:xxxxx@ntdev:

> KeRaiseIrql(HIGH_LEVEL) is just one quick “cli” instruction.

When did this change occur? I know it was not the case for all versions
of NT and for Windows 2000. Since then I have not walked that path, but
AFAIK it is not a “CLI”.

Don Burn (MVP, Windows DKD)
Windows Filesystem and Driver Consulting
Website: http://www.windrvr.com
Blog: http://msmvps.com/blogs/WinDrvr

Information from ESET Smart Security, version of virus
signature database 4900 (20100227)

The message was checked by ESET Smart Security.

http://www.eset.com