Hello guys! I’m very grateful for the help everyone on this forum!
Now I try create lock-free double linked list based on ExInterlockedXXXX functions.
But maybe I’m in a dead end,because I can’t find a way to search for a specific item in the list when find operation is performed by few threads.
Please help help to understand how to achieve goals if it’s real.
Why do you think you need a lock free version?
d
Bent from my phone
From: xxxxx@gmail.commailto:xxxxx
Sent: ?9/?19/?2014 6:46 AM
To: Windows System Software Devs Interest Listmailto:xxxxx
Subject: [ntdev] Lock-free find/add/read in double linked list
Hello guys! I’m very grateful for the help everyone on this forum!
Now I try create lock-free double linked list based on ExInterlockedXXXX functions.
But maybe I’m in a dead end,because I can’t find a way to search for a specific item in the list when find operation is performed by few threads.
Please help help to understand how to achieve goals if it’s real.
—
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
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</mailto:xxxxx></mailto:xxxxx>
This ain’t gonna work.
Why double linked and not slink?
T.
Sent from my Windows Phone From: xxxxx@gmail.com
Sent: 9/19/2014 6:46 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Lock-free find/add/read in double linked list
Hello guys! I’m very grateful for the help everyone on this forum!
Now I try create lock-free double linked list based on
ExInterlockedXXXX functions.
But maybe I’m in a dead end,because I can’t find a way to search for a
specific item in the list when find operation is performed by few
threads.
Please help help to understand how to achieve goals if it’s real.
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
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
By definition, you need some kind of lock if you want to iterate a list which may be modified by other threads. Especially if other threads may delete items from the list. You need to hold the lock for all time you walk the list. You cannot release the lock and reacquire it. Every time you release the lock, the pointer to the list item you’re holding may become invalid.
xxxxx@gmail.com wrote:
Hello guys! I’m very grateful for the help everyone on this forum!
Now I try create lock-free double linked list based on ExInterlockedXXXX functions.
I find this sentence to be bizarre. The DDK already has
ExInterlockedInsertHeadList, ExInterlockedRemoveHeadList, etc. However,
those are not lock-free. You have to hand a spin lock to every API.
And that is for a very good reason. You cannot implement a truly
lock-free doubly-linked list. It’s impossible. You have two pointers
to update, so no matter how clever you are, during every update there
will always be a small window during which the pointers are inconsistent.
–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.
Okey, I wrote file system filter driver, and in IRP_MJ_CREATE I post files name in list, then from user mode I want to get files from this list with a specific name (find in list) .
as I understand, IRP_MJ_CREATE can be called in arbitary thread on IRQL <= DISPATCH_LEVEL, but in this case I can’t blocking list?
Your followup is probably more appropriate for the NTFsd list … but to
clarify IRP_MJ_CREATE will be called at IRQL <= APC and if it is called
at APC then a filter above you is holding a lock they shouldn’t be
across the call. The ‘rule’ is that it should always be called at PASSIVE.
But aside from this, you can still use a SPIN_LOCK to protect your list
if you think there are cases where you need to search your tree at
DISPATCH. But if it is only in the IRP_MJ_CREATE path then use an
ERESOURCE so you have the option to acquire shared or exclusive,
depending on what you are doing.
Pete
On 9/19/2014 12:17 PM, xxxxx@gmail.com wrote:
Okey, I wrote file system filter driver, and in IRP_MJ_CREATE I post files name in list, then from user mode I want to get files from this list with a specific name (find in list) .
as I understand, IRP_MJ_CREATE can be called in arbitary thread on IRQL <= DISPATCH_LEVEL, but in this case I can’t blocking list?
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminarsTo unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer
–
Kernel Drivers
Windows File System and Device Driver Consulting
www.KernelDrivers.com
866.263.9295
Yes, you also have the option to use EX_PUSH_LOCK for the purpose of locking data as shared (read access) or exclusive (write access). EX_PUSH_LOCK are said to be more efficient but can’t be acquired recursively.
Well… not unless he’s writing a file system filter driver he doesn’t have that options. They’re not documented except as they’re exported by Filter Manager.
I seem to recall being told (by the guy who wrote the code) that Push Locks are only significantly less overhead when the lock is mostly NOT contended. For the contested case, they’re slower? Does anybody but me think that’s true?
And, to complete our tour of reader/writer type locks in Windows, let us not forget the device driver developer’s friend: The Reader/Writer Spin Lock. THIS lock was a long time coming, for sure.
Peter
OSR
@OSRDrivers
Right, he mentioned a file system filter driver hence my comment about
the NTFsd list … but, like I said, in the IRP_MJ_CREATE path in a file
system filter driver an ERESOURCE is fine and, as far as I know, they
are not tracked by the system, something which is very helpful when
debugging. But an EX_PUSH_LOCK would also work just as good noting the
caveats for them.
Pete
On 9/19/2014 3:43 PM, xxxxx@osr.com wrote:
Well… not unless he’s writing a file system filter driver he doesn’t have that options. They’re not documented except as they’re exported by Filter Manager.
I seem to recall being told (by the guy who wrote the code) that Push Locks are only significantly less overhead when the lock is mostly NOT contended. For the contested case, they’re slower? Does anybody but me think that’s true?
And, to complete our tour of reader/writer type locks in Windows, let us not forget the device driver developer’s friend: The Reader/Writer Spin Lock. THIS lock was a long time coming, for sure.
Peter
OSR
@OSRDrivers
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminarsTo unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer
–
Kernel Drivers
Windows File System and Device Driver Consulting
www.KernelDrivers.com
866.263.9295
Thank guys for help!
But what about perfomance? When list has large size find operation takes times and I lock (all system?) all IRP_MJ_CREATE in system by acquire spin-lock?
> > You cannot implement a truly lock-free doubly-linked list. It’s impossible. You have two pointers
to update, so no matter how clever you are, during every update there
will always be a small window during which the pointers are inconsistent.
I?m not sure this is still true. Intel?s recently added TSX transactional memory feature might allow double linked lists without the performance hit of locks. Of course this only works on TSX capable processors. See http://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions for a quick overview or the Intel processor manuals for the details.
My (incomplete) understanding of TSX is the processor will internally detect when there are conflicting memory accesses, and either rolls back memory changes made by one thread and/or notifies software that was a conflict, so it can retry the operation. In most cases, locks don?t serve any purpose, and are just overhead. Only in the cases when a conflict would have happened do the locks serve a purpose. TSX optimizes the path where there was no conflict, and has a way to deal with the case where there is a conflict. The conflict is detected by hardware, like the cache coherency mechanism.
When TSX came out, I looked at it in detail, but didn?t write any code since I didn?t have a TSX cable processor. I like the concept, but being an old assembly hacker, I?ll wait to see how well it really works before having an opinion. As I now have a couple of processors at my disposal that support TSX (or maybe not, as the wikipedia article says Haswell processor TSX has a bug), it might be fun to see what TSX can really do. I suppose it?s a question of your definition of ?lock free?, and using TSX may or may not be defined as a lock. I would probably view that if performance is generally not degraded using TSX vs not having any locks, that?s essentially lock free. Making the common case fast, even if the rare case is slower, is at the core or many performance optimizations.
There are people who say they already have lock free double linked list algorithms, which you can find with Google, like for example http://www.cse.chalmers.se/~tsigas/papers/Lock-Free%20Doubly%20Linked%20lists%20and%20Deques%20-OPODIS04.pdf
Jan
So split the list into pieces with individual list heads and locks, and a
hash function to start the search. If this is a file system mini-filter
keep the hash index in the appropriate context.
Don Burn
Windows Filesystem and Driver Consulting
Website: http://www.windrvr.com
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of
xxxxx@gmail.com
Sent: Friday, September 19, 2014 7:27 PM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Lock-free find/add/read in double linked list
Thank guys for help!
But what about perfomance? When list has large size find operation takes
times and I lock (all system?) all IRP_MJ_CREATE in system by acquire
spin-lock?
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
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
And to add to other comments, if you utilize a reader/writer lock such
as an ERESOURCE or PushLock then the lookup would only need to acquire
the list shared, depending on your design of course. And possibly if you
have your lookup tree volume based then it would only be locks on that
volumes tree, not across the entire system … again, dependent on your
design.
Pete
On 9/19/2014 5:27 PM, xxxxx@gmail.com wrote:
Thank guys for help!
But what about perfomance? When list has large size find operation takes times and I lock (all system?) all IRP_MJ_CREATE in system by acquire spin-lock?
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminarsTo unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer
–
Kernel Drivers
Windows File System and Device Driver Consulting
www.KernelDrivers.com
866.263.9295
You are also prematurely optimizing. You don’t know your perf characteristics yet. Design simple and then measure. If you think you will have a high contention list, lock free usually had worse characteristics than a simple lock due to the spinning/repeating
d
Bent from my phone
From: Peter Scottmailto:xxxxx
Sent: ?9/?19/?2014 5:37 PM
To: Windows System Software Devs Interest Listmailto:xxxxx
Cc: xxxxx@KernelDrivers.commailto:xxxxx
Subject: Re: [ntdev] Lock-free find/add/read in double linked list
And to add to other comments, if you utilize a reader/writer lock such
as an ERESOURCE or PushLock then the lookup would only need to acquire
the list shared, depending on your design of course. And possibly if you
have your lookup tree volume based then it would only be locks on that
volumes tree, not across the entire system … again, dependent on your
design.
Pete
On 9/19/2014 5:27 PM, xxxxx@gmail.com wrote:
> Thank guys for help!
> But what about perfomance? When list has large size find operation takes times and I lock (all system?) all IRP_MJ_CREATE in system by acquire spin-lock?
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> 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
–
Kernel Drivers
Windows File System and Device Driver Consulting
www.KernelDrivers.comhttp:
866.263.9295
—
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
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</http:></mailto:xxxxx></mailto:xxxxx></mailto:xxxxx>