Hello everyone!
While I was working on a project I became curious to see the implementation
of interlocked single lists in windows because I realized I couldn’t figure
out how it’s possible to atomically determine the second element in the
list so as to put it in place of the first one.
So I took a look at the ExpInterlockedPopEntrySList (this is taken from a
W10 x64 system but on W8.1 x64 it’s almost the same) function - also on
pastebin http://pastebin.com/LJ8UJ2WU# :
nt!ExpInterlockedPopEntrySList:
prefetchw [rcx] ; ListHead
push rbx
mov r10,rcx ; r10 <- ListHead
nt!ExpInterlockedPopEntrySListResume:
mov rax,qword ptr [r10] ; rax <- ListHead->Sequence Depth
mov rdx,qword ptr [r10+8] ; rdx <- ListHead->NextEntry Rsvd
mov r8,rdx
and r8,0FFFFFFFFFFFFFFF0h ; r8 <- ListHead->NextEntry
je nt!ExpInterlockedPopEntrySListEnd+0xc ; if NULL => ret
nt!ExpInterlockedPopEntrySListFault:
*mov rcx,qword ptr [r8]* ; rcx <- ListHead->NextEntry->Next
mov rbx,rax ; rbx <- ListHead->Sequence Depth
dec bx ; decrement Depth
lock cmpxchg16b oword ptr [r10] ; compare rdx:rax with m128; If equal
; [m128] <- rcx:rbx
and set ZF
jnz nt!ExpInterlockedPopEntrySListResume ; exchange failed => try again
nt!ExpInterlockedPopEntrySListEnd+0x7:
mov rax,r8 ; rax <- element popped
pop rbx
ret
nt!ExpInterlockedPopEntrySListEnd+0xc:
lock or qword ptr [r10],0 ; not sure what this is for
jmp nt!ExpInterlockedPopEntrySListEnd+0x7 ; ret
SLIST_HEADER definition (x64):
typedef union DECLSPEC_ALIGN(16) _SLIST_HEADER {
struct { // original struct
ULONGLONG Alignment;
ULONGLONG Region;
} DUMMYSTRUCTNAME;
struct { // x64 16-byte header
ULONGLONG Depth:16;
ULONGLONG Sequence:48;
ULONGLONG Reserved:4;
ULONGLONG NextEntry:60; // last 4 bits are always 0’s
} HeaderX64;
} SLIST_HEADER, *PSLIST_HEADER;
I *commented* the code to better understand what’s happening and from what
I see two conclusions can be drawn:
-
Because it is IMPOSSIBLE to atomically determine the second element in
the list there is a chance memory is used after free and in some cases
(with EXTREMELY LOW probability) it is possible this could lead to a BSOD
(say if virtual page has no corresponding physical frame).
-
Because of the way SLIST_HEADER is implemented even if the SLIST_ENTRY
memory is used after free the function will work as expected, i.e. in that
case the cmpxchg16b will fail because the initial DepthSequence values do
not match the current values and the function will retry to place the new
second element in the list to the first one.
The reason I’ve posted this was more out of curiosity of the following
things:
- Am I the only person who didn’t know and didn’t expect this?
- When you were designing a project did you ever have to make this
trade-off? (a significant performance boost over an extremely unlikely
crash) And if so, what was your decision?
Awaiting your replies!
There’s a special case in the page fault handler that takes care of this. I
even wrote a little blog post about it a few years ago:
http://blogs.microsoft.co.il/sasha/2012/08/11/windows-memory-managers-preferential-treatment-of-access-faults-in-the-interlocked-singly-linked-list-pop-implementation/
On Mon, Dec 7, 2015 at 4:57 PM Gurzou Alexandru
wrote:
> Hello everyone!
>
>
>
> While I was working on a project I became curious to see the
> implementation of interlocked single lists in windows because I realized I
> couldn’t figure out how it’s possible to atomically determine the second
> element in the list so as to put it in place of the first one.
>
> So I took a look at the ExpInterlockedPopEntrySList (this is taken from a
> W10 x64 system but on W8.1 x64 it’s almost the same) function - also on
> pastebin http://pastebin.com/LJ8UJ2WU# :
>
> nt!ExpInterlockedPopEntrySList:
> prefetchw [rcx] ; ListHead
> push rbx
> mov r10,rcx ; r10 <- ListHead
>
> nt!ExpInterlockedPopEntrySListResume:
> mov rax,qword ptr [r10] ; rax <- ListHead->Sequence Depth
> mov rdx,qword ptr [r10+8] ; rdx <- ListHead->NextEntry Rsvd
> mov r8,rdx
> and r8,0FFFFFFFFFFFFFFF0h ; r8 <- ListHead->NextEntry
> je nt!ExpInterlockedPopEntrySListEnd+0xc ; if NULL => ret
>
> nt!ExpInterlockedPopEntrySListFault:
> mov rcx,qword ptr [r8] ; rcx <- ListHead->NextEntry->Next
> mov rbx,rax ; rbx <- ListHead->Sequence Depth
> dec bx ; decrement Depth
> lock cmpxchg16b oword ptr [r10] ; compare rdx:rax with m128; If equal
> ; [m128] <- rcx:rbx
> and set ZF
> jnz nt!ExpInterlockedPopEntrySListResume ; exchange failed => try again
>
> nt!ExpInterlockedPopEntrySListEnd+0x7:
> mov rax,r8 ; rax <- element popped
> pop rbx
> ret
>
> nt!ExpInterlockedPopEntrySListEnd+0xc:
> lock or qword ptr [r10],0 ; not sure what this is for
> jmp nt!ExpInterlockedPopEntrySListEnd+0x7 ; ret
>
>
> SLIST_HEADER definition (x64):
> typedef union DECLSPEC_ALIGN(16) _SLIST_HEADER {
> struct { // original struct
> ULONGLONG Alignment;
> ULONGLONG Region;
> } DUMMYSTRUCTNAME;
> struct { // x64 16-byte header
> ULONGLONG Depth:16;
> ULONGLONG Sequence:48;
> ULONGLONG Reserved:4;
> ULONGLONG NextEntry:60; // last 4 bits are always 0’s
> } HeaderX64;
> } SLIST_HEADER, *PSLIST_HEADER;
>
>
> I commented the code to better understand what’s happening and from what
> I see two conclusions can be drawn:
>
> 1. Because it is IMPOSSIBLE to atomically determine the second element in
> the list there is a chance memory is used after free and in some cases
> (with EXTREMELY LOW probability) it is possible this could lead to a BSOD
> (say if virtual page has no corresponding physical frame).
>
> 2. Because of the way SLIST_HEADER is implemented even if the SLIST_ENTRY
> memory is used after free the function will work as expected, i.e. in that
> case the cmpxchg16b will fail because the initial DepthSequence values do
> not match the current values and the function will retry to place the new
> second element in the list to the first one.
>
>
> The reason I’ve posted this was more out of curiosity of the following
> things:
> 1. Am I the only person who didn’t know and didn’t expect this?
> 2. When you were designing a project did you ever have to make this
> trade-off? (a significant performance boost over an extremely unlikely
> crash) And if so, what was your decision?
>
>
> Awaiting your replies!
> — NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars
> on crash dump analysis, WDF, Windows internals and software drivers!
> Details at To unsubscribe, visit the List Server section of OSR Online at
Wow, wasn’t expecting that (neither an article, neither the modification
made to the page fault handler), thanks very much!
Every time I learn of such internal windows mechanisms I can’t help but be
amazed by the people who designed it.
On 7 December 2015 at 17:03, Sasha Goldshtein wrote:
> There’s a special case in the page fault handler that takes care of this.
> I even wrote a little blog post about it a few years ago:
> http://blogs.microsoft.co.il/sasha/2012/08/11/windows-memory-managers-preferential-treatment-of-access-faults-in-the-interlocked-singly-linked-list-pop-implementation/
>
> On Mon, Dec 7, 2015 at 4:57 PM Gurzou Alexandru <
> xxxxx@gmail.com> wrote:
>
>> Hello everyone!
>>
>>
>>
>> While I was working on a project I became curious to see the
>> implementation of interlocked single lists in windows because I realized I
>> couldn’t figure out how it’s possible to atomically determine the second
>> element in the list so as to put it in place of the first one.
>>
>> So I took a look at the ExpInterlockedPopEntrySList (this is taken from a
>> W10 x64 system but on W8.1 x64 it’s almost the same) function - also on
>> pastebin http://pastebin.com/LJ8UJ2WU# :
>>
>> nt!ExpInterlockedPopEntrySList:
>> prefetchw [rcx] ; ListHead
>> push rbx
>> mov r10,rcx ; r10 <- ListHead
>>
>> nt!ExpInterlockedPopEntrySListResume:
>> mov rax,qword ptr [r10] ; rax <- ListHead->Sequence Depth
>> mov rdx,qword ptr [r10+8] ; rdx <- ListHead->NextEntry Rsvd
>> mov r8,rdx
>> and r8,0FFFFFFFFFFFFFFF0h ; r8 <- ListHead->NextEntry
>> je nt!ExpInterlockedPopEntrySListEnd+0xc ; if NULL => ret
>>
>> nt!ExpInterlockedPopEntrySListFault:
>> mov rcx,qword ptr [r8] ; rcx <- ListHead->NextEntry->Next
>> mov rbx,rax ; rbx <- ListHead->Sequence Depth
>> dec bx ; decrement Depth
>> lock cmpxchg16b oword ptr [r10] ; compare rdx:rax with m128; If
>> equal
>> ; [m128] <- rcx:rbx
>> and set ZF
>> jnz nt!ExpInterlockedPopEntrySListResume ; exchange failed => try
>> again
>>
>> nt!ExpInterlockedPopEntrySListEnd+0x7:
>> mov rax,r8 ; rax <- element popped
>> pop rbx
>> ret
>>
>> nt!ExpInterlockedPopEntrySListEnd+0xc:
>> lock or qword ptr [r10],0 ; not sure what this is for
>> jmp nt!ExpInterlockedPopEntrySListEnd+0x7 ; ret
>>
>>
>> SLIST_HEADER definition (x64):
>> typedef union DECLSPEC_ALIGN(16) _SLIST_HEADER {
>> struct { // original struct
>> ULONGLONG Alignment;
>> ULONGLONG Region;
>> } DUMMYSTRUCTNAME;
>> struct { // x64 16-byte header
>> ULONGLONG Depth:16;
>> ULONGLONG Sequence:48;
>> ULONGLONG Reserved:4;
>> ULONGLONG NextEntry:60; // last 4 bits are always 0’s
>> } HeaderX64;
>> } SLIST_HEADER, *PSLIST_HEADER;
>>
>>
>> I commented the code to better understand what’s happening and from
>> what I see two conclusions can be drawn:
>>
>> 1. Because it is IMPOSSIBLE to atomically determine the second element in
>> the list there is a chance memory is used after free and in some cases
>> (with EXTREMELY LOW probability) it is possible this could lead to a BSOD
>> (say if virtual page has no corresponding physical frame).
>>
>> 2. Because of the way SLIST_HEADER is implemented even if the SLIST_ENTRY
>> memory is used after free the function will work as expected, i.e. in that
>> case the cmpxchg16b will fail because the initial DepthSequence values do
>> not match the current values and the function will retry to place the new
>> second element in the list to the first one.
>>
>>
>> The reason I’ve posted this was more out of curiosity of the following
>> things:
>> 1. Am I the only person who didn’t know and didn’t expect this?
>> 2. When you were designing a project did you ever have to make this
>> trade-off? (a significant performance boost over an extremely unlikely
>> crash) And if so, what was your decision?
>>
>>
>> Awaiting your replies!
>> — NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars
>> on crash dump analysis, WDF, Windows internals and software drivers!
>> Details at To unsubscribe, visit the List Server section of OSR Online
>> at
>
> — NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars
> on crash dump analysis, WDF, Windows internals and software drivers!
> Details at To unsubscribe, visit the List Server section of OSR Online at