Interlocked linked lists

[donkey]

When dealing with multithreaded programs using linked lists synchronization can be a nightmare. Lucky Windows provides the interlocked SList group of functions. Here's a quick translation of the demo at MSDN. Access to the singly linked list is synchronized across threads and multiple processors:

Code Select Expand

PROGRAM_ITEM STRUCT
ItemEntry SLIST_ENTRY
Signature DD
ENDS

#IF X64

SLIST_HEADER STRUCT
Alignment DQ
Region DQ
ENDS

#ELSE

SLIST_HEADER STRUCT
UNION
Alignment DQ
STRUCT
Next SLIST_ENTRY
Depth DW
Sequence DW
ENDS
ENDUNION
ENDS
#ENDIF

SLIST_ENTRY STRUCT
Next PTR
ENDS

CODE SECTION

SlistDemo FRAME
LOCAL pFirstEntry:%PTR
LOCAL pListEntry:%PTR
LOCAL pListHead:%PTR
LOCAL pProgramItem:%PTR

invoke VirtualAlloc,NULL,SIZEOF SLIST_HEADER,MEM_COMMIT,PAGE_READWRITE
mov [pListHead],eax

invoke InitializeSListHead,[pListHead]

// Insert 10 items into the list.
xor ebx,ebx
inc ebx
:
invoke VirtualAlloc,NULL,SIZEOF SLIST_HEADER,MEM_COMMIT,PAGE_READWRITE
mov [pProgramItem],eax

mov D[eax+PROGRAM_ITEM.Signature],ebx
invoke InterlockedPushEntrySList,[pListHead],[pProgramItem]
mov [pFirstEntry],eax
inc ebx
cmp ebx,10
jle <

// Remove 10 items from the list
dec ebx // EBX = 10
:
invoke InterlockedPopEntrySList,[pListHead]
mov [pListEntry],eax
test eax,eax
jnz >.GETENTRY
// List is empty
invoke MessageBox,0,"Error: List is empty",0,0
mov eax,-1
ret
.GETENTRY
// Data is in [eax+PROGRAM_ITEM.Signature]
invoke VirtualFree,[pListEntry],0,MEM_RELEASE
dec ebx
jnz <

invoke InterlockedFlushSList,[pListHead]
invoke InterlockedPopEntrySList,[pListHead]
test eax,eax
jz >
invoke MessageBox,0,"Error: List is not empty",0,0
:
invoke VirtualFree,[pListHead],0,MEM_RELEASE
xor eax,eax
ret
endf

Note that the SLIST_HEADER structure in X64 is more complex than the one defined here however since it is only for system use you should never have to access the bitfeilds so it does not present a problem.

Edgar

[dedndave]

wow - they have a set of functions for that   :lol

i didn't even use the MS semaphore/mutex functions
in the past, i have used my own semaphore flag with the XCHG instruction   :P
didn't seem all that hard

[donkey]

wow - they have a set of functions for that   :lol

i didn't even use the MS semaphore/mutex functions
in the past, i have used my own semaphore flag with the XCHG instruction   :P
didn't seem all that hard

Hi Dave,

I had issues when multiple threads used the affinity mask and were forced to run on separate physical processors, there were times when I seemed to get race conditions. Running on a single CPU was fine but this api set seems to have solved the problem the multiprocessor issues I was having. I'm confident that I could have worked out the linked list synchronization issues I was having in a more traditional manner, probably a spin-lock but since the api already provides the solution I avoided the work.

[dedndave]

ahhh - very good point, Edgar
i had not taken into consideration the possibility of "affinitized" threads on seperate physical cores
XCHG would not work, there, as it probably only applies bus lock to the core it's running on