Hi?
I know the ExInterlockedInsertHeadList API exists to implement thread-safe lists in kernel drivers.
However, there is an atomic function for inserting and retrieving data, and it seems that there is no atomic support for traversing and querying while stored in a list.
Isn’t there an atomic list support API without locks?
Should I implement it myself?
Isn’t there an atomic list support API without locks?
No, because such a thing cannot be implemented generically. Inserting an item into a list and removing an item from a list are single functions that can be done atomically. Traversing a list requires multiple steps while you DO something with the list items. Only you know how much work you have to do and when you’ll be done. The compiler can’t guess when you are done traversing.
Should I implement it myself?
Yes, you almost always need to do that with the linked list APIs, and that brings up a very important point. ExInterlockedInsertHeadList simply ensures that the the insert operation is not interrupted in the middle. If you are using your own lock to protect your list, that will be a completely separate lock, totally unsynchronized with ExInterlockedInsertHeadList. If you want to make sure the list doesn’t change while you are traversing (which you usually do), then you need to abandon ExInterlockedInsertHeadList and user your own lock around InsertHeadList. The same thing applies to WDFCOLLECTION objects, although they conveniently carry their own locks.
More should be said on this. There are many ways to enumerate or iterate lists, and many different philosophies on how it should be done.
Lists that can only ever be accessed by a single thread are uninteresting, but data structures that can be enumerated or iterated that can be accessed by multiple threads concurrently raise many choices. Whether the elements are stored as an array, linked list, binary tree or a try or anything else, the basic question comes from SQL theory. What should be the transaction isolation level for each operation?
depending on what you need, different choices make more or less sense.
If you can describe what you are trying to do, probably we can provide more specific advise