ExInterlockedPopEntrySList processing by scheduler.

I believe this topic on ExInterlockedPopEntrySList might be interesting for Windows drivers developers.

Safety of using ExInterlockedPopEntrySList

The question was

To my knowledge, pre-Windows 8 x64 implementations of SList use 9-bit sequence numbers in the SLIST_HEADER. This means that 512 operations can complete concurrently (without progress from particular thread) until an ABA problem potentially manifests. I wonder whether, depending on the number of threads and physical cores, this couldn't plausibly occur. To further complicate, the kernel could run on a vcpu, creating time discontinuities. I would like to ask: 1. Does the Windows scheduler protect against ABA by, e.g., restarting interlocked operation upon preemption? 2. Is there some protection against hypervisor interference? 3. In the light of the above concerns, is SList on a pre-Windows 8 x64 deployment really safe for all workloads? I would have speculated that per-thread kernel allocator behavior was factored in for the ABA avoidance, but the primitives are in the Win32 API as well and any driver can employ custom pool allocator.
My answer was

I looked at the code again and found that interrupt processing code has a fixup for SList . There is a routine KiCheckForSListAddress. This routine is called at DISPATCH_LEVEL before returning from an interrupt and it fixes the EIP(RIP for x64) of a trap frame to restart SList pop operation if interrupt happened inside ExInterlockedPopEntrySList. So when an interrupt processing code returns execution to an interrupted code the code resumes at the beginning of ExInterlockedPopEntrySList ( namely ExpInterlockedPopEntrySListResume ). kd> uf KiCheckForSListAddress nt!KiCheckForSListAddress: 82acbdf1 0fb7416c movzx eax,word ptr [ecx+6Ch] 82acbdf5 8b5168 mov edx,dword ptr [ecx+68h] 82acbdf8 6683f808 cmp ax,8 82acbdfc 7511 jne nt!KiCheckForSListAddress+0x1e (82acbe0f) Branch nt!KiCheckForSListAddress+0xd: 82acbdfe b8f4dda882 mov eax,offset nt!ExpInterlockedPopEntrySListResume (82a8ddf4) 82acbe03 3bd0 cmp edx,eax 82acbe05 7222 jb nt!KiCheckForSListAddress+0x38 (82acbe29) Branch nt!KiCheckForSListAddress+0x16: 82acbe07 81fa1fdea882 cmp edx,offset nt!ExpInterlockedPopEntrySListEnd (82a8de1f) 82acbe0d eb15 jmp nt!KiCheckForSListAddress+0x33 (82acbe24) Branch nt!KiCheckForSListAddress+0x1e: 82acbe0f 6683f81b cmp ax,1Bh 82acbe13 7514 jne nt!KiCheckForSListAddress+0x38 (82acbe29) Branch nt!KiCheckForSListAddress+0x24: 82acbe15 a1ac69bb82 mov eax,dword ptr [nt!KeUserPopEntrySListResume (82bb69ac)] 82acbe1a 3bd0 cmp edx,eax 82acbe1c 720b jb nt!KiCheckForSListAddress+0x38 (82acbe29) Branch nt!KiCheckForSListAddress+0x2d: 82acbe1e 3b15a469bb82 cmp edx,dword ptr [nt!KeUserPopEntrySListEnd (82bb69a4)] nt!KiCheckForSListAddress+0x33: 82acbe24 7703 ja nt!KiCheckForSListAddress+0x38 (82acbe29) Branch nt!KiCheckForSListAddress+0x35: 82acbe26 894168 mov dword ptr [ecx+68h],eax nt!KiCheckForSListAddress+0x38: 82acbe29 c3 ret Branch

MacOS X hibernate path and preemption

Below is a MacOS X 10.9 callstack while processing a request to hibernate

mach_kernel`IOPMrootDomain::pmStatsRecordEvent() + 227 at IOPMrootDomain.cpp:6969

mach_kernel`hibernate_machine_init + 3160 at IOHibernateIO.cpp:3112

mach_kernel`acpi_sleep_kernel() + 503 at acpi.c:320

AppleACPIPlatform`AppleACPIPlatformExpert::sleepPlatform() + 443

AppleACPIPlatform`AppleACPICPU::haltCPU() + 117

mach_kernel`IOCPUSleepKernel() + 764 at IOCPU.cpp:403

mach_kernel`IOPMrootDomain::powerChangeDone() + 531 at IOPMrootDomain.cpp:2256

mach_kernel`IOService::all_done() + 1221 at IOServicePM.cpp:4269

mach_kernel`IOService::servicePMRequest(IOPMRequest*, IOPMWorkQueue*) [inlined] IOService::OurChangeFinish() + 8 at IOServicePM.cpp:4736

mach_kernel`IOService::servicePMRequest() + 2773 at IOServicePM.cpp:7337

mach_kernel`IOPMWorkQueue::checkRequestQueue() + 52 at IOServicePM.cpp:8236

mach_kernel`IOPMWorkQueue::checkForWork() + 127 at IOServicePM.cpp:8296

mach_kernel`IOWorkLoop::runEventSources() + 258 at IOWorkLoop.cpp:367

mach_kernel`IOWorkLoop::threadMain() + 195 at IOWorkLoop.cpp:395

The call to IOPMrootDomain::pmStatsRecordEvent is done with preemption disabled, i.e. the threads scheduling is not allowed, but IOPMrootDomain::pmStatsRecordEvent calls IORegistryEntry::setProperty that acquires a mutex and mutex acquisition can block a thread calling the scheduler in case of contention for mutex. So, is this a bug in the Apple code? I do not know but there is a workaround in the Apple code to not panic a debug kernel build when calling IORegistryEntry::setProperty with preemption disabled - a check cmpl $0,%gs:CPU_HIBERNATE bypasses the whole CHECK_PREEMPTION_LEVEL macro if a CPU is in hibernating mode. It makes sense if there are no other active CPUs in the system.

An excerpt from i386_locks.s

/*

 * If one or more simplelocks are currently held by a thread,

 * an attempt to acquire a mutex will cause this check to fail

 * (since a mutex lock may context switch, holding a simplelock

 * is not a good thing).

 */

#if MACH_RT

#define CHECK_PREEMPTION_LEVEL() \

cmpl $0,%gs:CPU_HIBERNATE ; \

jne 1f ; \

cmpl $0,%gs:CPU_PREEMPTION_LEVEL ; \

je 1f ; \

ALIGN_STACK() ; \

movl %gs:CPU_PREEMPTION_LEVEL, %eax ; \

LOAD_ARG1(%eax) ; \

LOAD_STRING_ARG0(2f) ; \

CALL_PANIC() ; \

hlt ; \

.data ; \

2: String "preemption_level(%d) != 0!" ; \

.text ; \

1:

#else /* MACH_RT */

#define CHECK_PREEMPTION_LEVEL()

#endif /* MACH_RT */