Is priroity Inheritance available in Windows Desktop?

[anil_kumar-3]

Is priroity Inheritance available in Windows Desktop?

We have one kmdf driver that has multiple clients in which there are few client’s threads priority is high. Few clients threads priority is low and when they are calling into our driver apis, its causing high priority thread to starve. Our driver uses spinlocks for synchronization.

Clients access our functions through interface table.

I think, bumping bup low priority thread may not be better solution as we need to do that for all the clients of our driver which doesnt look right.

Please let me know if priority inheritance concept is there in Windows Desktop for spinlocks? How to achieve the same?

Regards
Anil

[MBond]

I think you have a lot to learn, but here are a few things

1. Priority is an attribute of a thread. The scheduler considers this when there are multiple threads ready to run on a given CPU. The there are more CPUs available than threads ready to run, then this does not matter as every thread gets to run. Also, priority is only considered when a scheduling decision is to be made.
2. Spin locks do not consider thread priorities. They can?t as they don?t interact with the scheduler. Any thread of any priority holding a spin lock will prevent all other threads of all priorities from acquiring it until it is finished
3. Calls to drivers at the top of the stack are generally made in the context of the calling UM thread ? including priority, but after that it is usually arbitrary thread context with no way to associate back to the original unless it can somehow be determined from the IRP (I.e. this one is a ?high? priority IRP and that one is a ?low? priority IRP based on the code etc.)

Without knowing what your driver does, or anything about your design, my guess would be that you need to fix your threading design. There won?t be any quick fix

Sent from Mailhttps: for Windows 10

________________________________
From: xxxxx@lists.osr.com on behalf of xxxxx@gmail.com
Sent: Friday, July 20, 2018 5:08:00 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Is priroity Inheritance available in Windows Desktop?

Is priroity Inheritance available in Windows Desktop?

We have one kmdf driver that has multiple clients in which there are few client’s threads priority is high. Few clients threads priority is low and when they are calling into our driver apis, its causing high priority thread to starve. Our driver uses spinlocks for synchronization.

Clients access our functions through interface table.

I think, bumping bup low priority thread may not be better solution as we need to do that for all the clients of our driver which doesnt look right.

Please let me know if priority inheritance concept is there in Windows Desktop for spinlocks? How to achieve the same?

Regards
Anil

—
NTDEV is sponsored by OSR

Visit the list online at: http:

MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
Details at http:

To unsubscribe, visit the List Server section of OSR Online at http:</http:></http:></http:></https:>

[Tim_Roberts]

xxxxx@gmail.com wrote:

Is priroity Inheritance available in Windows Desktop?

We have one kmdf driver that has multiple clients in which there are few client’s threads priority is high. Few clients threads priority is low and when they are calling into our driver apis, its causing high priority thread to starve. Our driver uses spinlocks for synchronization.

Clients access our functions through interface table.

I think, bumping bup low priority thread may not be better solution as we need to do that for all the clients of our driver which doesnt look right.

Please let me know if priority inheritance concept is there in Windows Desktop for spinlocks? How to achieve the same?

How do you think that would work?  When a driver grabs a spinlock, it’s
saying "I have a resource to protect; I cannot be interrupted while I
update this resource."  If a request from a higher-priority thread comes
in, what do you expect the system to do?  The driver already said it’s
in a critical region.  If you interrupt it, you’re going to have data
structures in an inconsistent state.  On the other hand, if your driver
is doing things that can be interrupted, then it should not be holding a
spinlock.

Your only choice is to reduce your spinlock-protected regions to their
absolute minimum.  It’s easy to oversynchronize a driver.

As a general rule, messing with thread priorities always leads to tears. 

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

[anton_bassov]

> Please let me know if priority inheritance concept is there in Windows Desktop for spinlocks?

There is no such thing as “priority inheritance for spinlock owner” - this kind of thing is impossible even in theory, because thread priority management is the scheduler’s responsibility, and spinlock holderis beyond the scheduler’s control by the virtue of holding a spinlock, which can be done only in the atomic context.

This concept in itself may apply only to mutex owners. It is normally associated with the world of hard RTOSes, although some GPOSes may provide a certain level of support for it as well
(Solaris is the very first example that gets into my head). IIRC, Windows NT does not really support it, although an interactive GUI thread with a window may get a priority boost when the target thread’s window gets the user focus. However, such priority adjustment is totally unrelated to the concept of priority inheritance per se…

Anton Bassov

[Prokash_Sinha-1]

Usually wait-able locks are the candidates for priority inversions. Spin lock by name and nature not wait-able. As, Anton mentioned Solaris tried these quite a bit. But except mutex, or binary semaphore ( which is essentially mutex) there are not much improvements I’m aware of ( i.e. semaphore with count > 1 ; read write lock, condition variables ).

-Pro

On Jul 20, 2018, at 10:45 AM, xxxxx@hotmail.com wrote:
>
>> Please let me know if priority inheritance concept is there in Windows Desktop for spinlocks?
>
> There is no such thing as “priority inheritance for spinlock owner” - this kind of thing is impossible even in theory, because thread priority management is the scheduler’s responsibility, and spinlock holderis beyond the scheduler’s control by the virtue of holding a spinlock, which can be done only in the atomic context.
>
> This concept in itself may apply only to mutex owners. It is normally associated with the world of hard RTOSes, although some GPOSes may provide a certain level of support for it as well
> (Solaris is the very first example that gets into my head). IIRC, Windows NT does not really support it, although an interactive GUI thread with a window may get a priority boost when the target thread’s window gets the user focus. However, such priority adjustment is totally unrelated to the concept of priority inheritance per se…
>
>
> Anton Bassov
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list online at: http:
>
> MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
> Details at http:
>
> To unsubscribe, visit the List Server section of OSR Online at http:</http:></http:></http:>

[anton_bassov]

> binary semaphore ( which is essentially mutex)

It is not, Pro…

Although you can use a binary semaphore for ensuring that only one thread may have an access to the target resource at a time, it is not a mutex - unlike mutex,a binary semaphore does not have an owner and can be signaled by anyone. This subtle difference may look insignificant unless you want to add a support for priority inheritance/priority ceiling protocols. At this point it will become just of a crucial importance to you - in order to be able to implement these protocols you have to ensure that your target synch resource may be signaled only by one thread at a time (i.e.by its owner).

Certainly, you may think of the binary semaphore as of a mutex and of the last thread that had called down() successfully as of its owner when it comes to adjusting tread priorities,
but even this approach still cannot give you any guarantees as far as priority inversion is concerned. Just consider the scenario when thread X calls down(), but up() is going to get called by the thread Y (i.e. the scenario that happens to be impossible with a mutex but may very well occur with a binary semaphore). In such case increasing the priority of thread X is not going to solve the priority inversion problem, is it…

Anton Bassov

[Prokash_Sinha-1]

You got a point there …

As long as ownership is unique, a lower priority owner can be determined in a deterministic way, and run thru the scheduler path after boosting the priority. Though detail native sem_ops including data structures may not have that.

—Give a wrapper

-Pro

On Jul 20, 2018, at 2:14 PM, xxxxx@hotmail.com wrote:
>
>> binary semaphore ( which is essentially mutex)
>
> It is not, Pro…
>
> Although you can use a binary semaphore for ensuring that only one thread may have an access to the target resource at a time, it is not a mutex - unlike mutex,a binary semaphore does not have an owner and can be signaled by anyone. This subtle difference may look insignificant unless you want to add a support for priority inheritance/priority ceiling protocols. At this point it will become just of a crucial importance to you - in order to be able to implement these protocols you have to ensure that your target synch resource may be signaled only by one thread at a time (i.e.by its owner).
>
>
> Certainly, you may think of the binary semaphore as of a mutex and of the last thread that had called down() successfully as of its owner when it comes to adjusting tread priorities,
> but even this approach still cannot give you any guarantees as far as priority inversion is concerned. Just consider the scenario when thread X calls down(), but up() is going to get called by the thread Y (i.e. the scenario that happens to be impossible with a mutex but may very well occur with a binary semaphore). In such case increasing the priority of thread X is not going to solve the priority inversion problem, is it…
>
>
>
> Anton Bassov
>
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list online at: http:
>
> MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
> Details at http:
>
> To unsubscribe, visit the List Server section of OSR Online at http:</http:></http:></http:>

[anton_bassov]

> As long as ownership is unique, a lower priority owner can be determined in a deterministic

way, and run thru the scheduler path after boosting the priority.

In theory, yes…

However, there are a couple of “nasty details” that one may encounter because of the owner’s possible use of other dispatcher-level constructs. Let’s consider the following two scenarios:

1. Mutex owner goes blocking on semaphore, read-write lock or condvar (there is nothing in POSIX semantics that precludes it from doing so, right). Meanwhile, a thread of higher priority tries to acquire the mutex in question. At this point we.again, subjected to the priority inversion. In fact, this silly move scuppers the whole thing and invalidates all our efforts, and defeats the very purpose of priority inheritance, in the first place.

2. Mutex owner acquires a mutex that supports priority ceiling protocol, rather than priority inheritance one. Again, there is nothing in POSIX semantics that precludes it from doing so.
   If you try to raise its priority above the ceiling you are going to violate the priority ceiling protocol, so that it obviously cannot be done. However, a thread of a priority well above the target ceiling still may try to acquire the original mutex that supports the priority inheritance protocol. If it does,we are, again,going to encounter the same old priority inversion problem

In other words, a priority inheritance protocol is not going to solve the priority inversion problem unless we impose very strict rules and limitations on what an owner of a mutex with support for
priority inheritance protocol is allowed to do…

Anton Bassov

[MBond]

All of this should confirm to the OP that he hasn?t asked a valid question from the point of view that a problem well stated is a problem mostly solved.

I strongly suspect that the choice of which kind of lock is the least of his problems. Priority inversion (as we expect his problem is based on the description) has little or nothing to do with the choice of locking primitive in the code. It has everything to do with the overall design and especially with the threading and locking design.

If that is the case, then there will be no silver bullet ? like bumping up thread priority or changing from spin lock to eresource or something where the scheduler might help. It will be the hard job of refactoring the design to work properly on Windows.

Its not really hard per se, but if you are porting code from *nix or don;t know anything about Windows it can be hard.

Sent from Mailhttps: for Windows 10

________________________________
From: xxxxx@lists.osr.com on behalf of xxxxx@garlic.com
Sent: Friday, July 20, 2018 6:12:42 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Is priroity Inheritance available in Windows Desktop?

You got a point there ?

As long as ownership is unique, a lower priority owner can be determined in a deterministic way, and run thru the scheduler path after boosting the priority. Though detail native sem_ops including data structures may not have that.

?Give a wrapper

-Pro
> On Jul 20, 2018, at 2:14 PM, xxxxx@hotmail.com wrote:
>
>> binary semaphore ( which is essentially mutex)
>
> It is not, Pro…
>
> Although you can use a binary semaphore for ensuring that only one thread may have an access to the target resource at a time, it is not a mutex - unlike mutex,a binary semaphore does not have an owner and can be signaled by anyone. This subtle difference may look insignificant unless you want to add a support for priority inheritance/priority ceiling protocols. At this point it will become just of a crucial importance to you - in order to be able to implement these protocols you have to ensure that your target synch resource may be signaled only by one thread at a time (i.e.by its owner).
>
>
> Certainly, you may think of the binary semaphore as of a mutex and of the last thread that had called down() successfully as of its owner when it comes to adjusting tread priorities,
> but even this approach still cannot give you any guarantees as far as priority inversion is concerned. Just consider the scenario when thread X calls down(), but up() is going to get called by the thread Y (i.e. the scenario that happens to be impossible with a mutex but may very well occur with a binary semaphore). In such case increasing the priority of thread X is not going to solve the priority inversion problem, is it…
>
>
>
> Anton Bassov
>
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list online at: http:
>
> MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
> Details at http:
>
> To unsubscribe, visit the List Server section of OSR Online at http:

—
NTDEV is sponsored by OSR

Visit the list online at: http:

MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
Details at http:

To unsubscribe, visit the List Server section of OSR Online at http:</http:></http:></http:></http:></http:></http:></https:>

[Prokash_Sinha-1]

I will be more aligned with Marion here !

Posix does not have it for reasons !. Off hand, I don’t know if Posix has Tunstile mechanism, but Solaris and BSD both have it. It is exactly to handle priority problem when one process with low priority goes to sleep while holding a mutex type lock. Inside the kernel, it tries to (1) find the unique process that is blocked with lower priority. If it could not find such process - it panic(). If it finds, then as I said earlier, it boost the priority and makes the scheduler takes that event. The actual high priority process goes to sleep. That is the overall processing logic, but, of course, there is more processing it does. BSD 5.x to 6.x has this.

Semaphore, condition vars, MRSW locks does not have these, simply because knowing unique culprit is not impossible, but the overhead in most cases. For each of these lock semantics there are one or more problems…

At any rate, we should live it at that. OP probably need, as Marion said, is to restructure, and fairly thorough understanding of the Win Kern locking mechanism.

-Pro

On Jul 20, 2018, at 5:32 PM, xxxxx@hotmail.com wrote:
>
>> As long as ownership is unique, a lower priority owner can be determined in a deterministic
>> way, and run thru the scheduler path after boosting the priority.
>
>
> In theory, yes…
>
>
> However, there are a couple of “nasty details” that one may encounter because of the owner’s possible use of other dispatcher-level constructs. Let’s consider the following two scenarios:
>
>
> 1. Mutex owner goes blocking on semaphore, read-write lock or condvar (there is nothing in POSIX semantics that precludes it from doing so, right). Meanwhile, a thread of higher priority tries to acquire the mutex in question. At this point we.again, subjected to the priority inversion. In fact, this silly move scuppers the whole thing and invalidates all our efforts, and defeats the very purpose of priority inheritance, in the first place.
>
>
> 2. Mutex owner acquires a mutex that supports priority ceiling protocol, rather than priority inheritance one. Again, there is nothing in POSIX semantics that precludes it from doing so.
> If you try to raise its priority above the ceiling you are going to violate the priority ceiling protocol, so that it obviously cannot be done. However, a thread of a priority well above the target ceiling still may try to acquire the original mutex that supports the priority inheritance protocol. If it does,we are, again,going to encounter the same old priority inversion problem
>
>
>
> In other words, a priority inheritance protocol is not going to solve the priority inversion problem unless we impose very strict rules and limitations on what an owner of a mutex with support for
> priority inheritance protocol is allowed to do…
>
>
> Anton Bassov
>
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list online at: http:
>
> MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
> Details at http:
>
> To unsubscribe, visit the List Server section of OSR Online at http:</http:></http:></http:>

[anton_bassov]

Posix does not have it for reasons !. Off hand, I don???t know if Posix has Tunstile mechanism, but Solaris and BSD both have it. It is exactly to handle priority problem when one process with low priority goes to sleep while holding a mutex type lock. Inside the kernel, it tries to (1) find the unique process that is blocked with lower priority. If it could not find such process - it panic(). If it finds, then as I said earlier, it boost the priority and makes the scheduler takes that event.

Try to think logically about the whole thing…

The only thing that turnstiles allow you to do is to identify the “culprit” so that you can boost its priority. However, it does not always solve the priority inversion problem.

Let’s assume the “culprit” had been identified and its priority boosted. As long as it keeps on running everything is going to be fine and dandy. If it goes blocking on other mutex that support priority inheritance protocol everything is going to be fine and dandy as well - the whole mechanism works recursively, so that we are always in a position to find “the end culprit” and boost its priority, i.e. the whole situation is going to get eventually resolved anyway. This is what turnstiles are for.

However, what are you going to do if the"end culprit" goes blocking on semaphore or condvar while holding the target mutex??? How are you going to locate the process that may release it???
Once a mutex owner enters the unbounded wait, this “unboundedness” is going to propagate all over the chain, and affect anyone who somehow depends (even indirectly, in case of a long recursive chain with multiple mutexes involved) on the target mutex getting released.

This is the problem that I was speaking about in my previous post, and the only possible way of solving it is to prohibit RT mutex owners from entering unbounded wait (i.e the one on any dispatcher-level construct other that RT mutex) right at the system level…

Semaphore, condition vars, MRSW locks does not have these, simply
because knowing unique culprit is not impossible, but the overhead in most cases.

As long as you are speaking about the RW locks locating the culprit(s) is, indeed, theoretically feasible, although may be impractical. However, for semaphores and condvars the task of locating the “end culprit” is simply infeasible - basically, this is just another formulation of the halting problem.

Anton Bassov

[MBond]

IIRC the Windows locks which interact with the scheduler have a similar feature where the owning thread ?inherits? the priority of the highest waiting thread. This all works great as long as the lock will be held for a long time ? and if it is not held for a long time, entirely irrelevant.

For modern systems, any design that holds locks for a long time is a bad one and so all of this priority inheritance stuff is mostly irrelevant. Except to put band-aids over the aorta to stop the bleeding.

Sent from Mailhttps: for Windows 10

________________________________
From: xxxxx@lists.osr.com on behalf of xxxxx@hotmail.com
Sent: Saturday, July 21, 2018 1:32:48 AM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Is priroity Inheritance available in Windows Desktop?

Posix does not have it for reasons !. Off hand, I don???t know if Posix has Tunstile mechanism, but Solaris and BSD both have it. It is exactly to handle priority problem when one process with low priority goes to sleep while holding a mutex type lock. Inside the kernel, it tries to (1) find the unique process that is blocked with lower priority. If it could not find such process - it panic(). If it finds, then as I said earlier, it boost the priority and makes the scheduler takes that event.

Try to think logically about the whole thing…

The only thing that turnstiles allow you to do is to identify the “culprit” so that you can boost its priority. However, it does not always solve the priority inversion problem.

Let’s assume the “culprit” had been identified and its priority boosted. As long as it keeps on running everything is going to be fine and dandy. If it goes blocking on other mutex that support priority inheritance protocol everything is going to be fine and dandy as well - the whole mechanism works recursively, so that we are always in a position to find “the end culprit” and boost its priority, i.e. the whole situation is going to get eventually resolved anyway. This is what turnstiles are for.

However, what are you going to do if the"end culprit" goes blocking on semaphore or condvar while holding the target mutex??? How are you going to locate the process that may release it???
Once a mutex owner enters the unbounded wait, this “unboundedness” is going to propagate all over the chain, and affect anyone who somehow depends (even indirectly, in case of a long recursive chain with multiple mutexes involved) on the target mutex getting released.

This is the problem that I was speaking about in my previous post, and the only possible way of solving it is to prohibit RT mutex owners from entering unbounded wait (i.e the one on any dispatcher-level construct other that RT mutex) right at the system level…

> Semaphore, condition vars, MRSW locks does not have these, simply
>because knowing unique culprit is not impossible, but the overhead in most cases.

As long as you are speaking about the RW locks locating the culprit(s) is, indeed, theoretically feasible, although may be impractical. However, for semaphores and condvars the task of locating the “end culprit” is simply infeasible - basically, this is just another formulation of the halting problem.

Anton Bassov

—
NTDEV is sponsored by OSR

Visit the list online at: http:

MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
Details at http:

To unsubscribe, visit the List Server section of OSR Online at http:</http:></http:></http:></https:>

[anton_bassov]

> IIRC the Windows locks which interact with the scheduler have a similar feature

where the owning thread ?inherits? the priority of the highest waiting thread.

In fact, I was totally unaware of the priority inheritance support under Windows NT up to this point, but I have to admit that my knowledge of Windows NT may be rather outdated. In which OS version did they introduce it?

This all works great as long as the lock will be held for a long time ? and if it is not held
for a long time, entirely irrelevant.

For modern systems, any design that holds locks for a long time is a bad
one and so all of this priority inheritance stuff is mostly irrelevant.

Well, strictly speaking, you don’t have to hold a lock for too long in order to be in a position to cause the priority inversion scenario - the only thing that you need is to get preempted while holding the lock. OTOH, the longer you hold locks, the more likely the above "unfortunate scenario’ to occur.

Concerning the (ir)relevance part, the whole thing is, indeed, mostly irrelevant in the world of GPOSes. It mainly applies in the world of hard RTOSes where “missed_deadline==failure” statement alway holds true. Therefore, such an OS has to be 100% predictable, because you have to be always in a position to evaluate the worst possible case/scenario, i.e. the longest delay that is theoretically possible.

The most likely scenario when you may need something like that under GPOS is deferred interrupt processing in context of a thread, rather than in an atomic one. Some GPOSes like Solaris and FreeBSD (and, to some extent,Linux) allow you to defer interrupt processing to so-called “interrupt thread”, effectively giving you an option of using dispatcher-level synch constructs in your DPCs.
Unless you are using a dedicated thread for every deferred processing item (which may be simply an overkill), putting such a thread out of play for too long may have very negative overall consequences for the system. This is why both Solaris and FreeBSD support the turnstiles
that allow you to deal with the priority inversion problem to some extent (although don’t provide a 100%-reliable solution to it for the reasons that I have explained in my previous post)

When it comes to Windows NT, there is no such thing as “interrupt thread” in the Windows world.
The only thing that Windows offers is a ridiculous concept of a “threaded DPC”,
i.e. the one that may , but is not guaranteed to, run at IRQL<dispatch_level.>Once you are not guaranteed that your routine is going to run at IRQL<dispatch_level you cannot use dispatcher-level synch constructs in it which simply defeats the purpose of whole exercise>


OK, it is time for me to shut up - the new list management platform with “scary” troll-management features is on the way, and must be already somewhere pretty close. After all, the term “trolling” seems to have a wide range of interpretations in this NG, and may include something as innocuous as questioning the practical usefulness of “typedef int INT”-like declarations. Therefore, it is better for me not to provoke “The Hanging Judge’s” wrath by criticising “the genius” of Windows NT design.



Anton Bassov</dispatch_level></dispatch_level.>

[anil_kumar-3]

Thank you all for your valuable inputs and as said by M M, may be my query for spinlocks is invalid.
I understand that Spinlocks doesnt care about priority.
Also once a thread acquires spinlock it should not matter what is the priority of various threads as that will never get preempted. In such case priority inversion will not happen.

Now i recall priority inversion can happen in following scenarios. Let A, B, C are threads with A highest, B middle, C the least. Say, if C took a mutex that is needed by A as well. But if C is gets preempted by B while A is waiting for the mutex. Now B has got the cpu w.r.to A and thus priority inversion happens.

I guess w.r.to Spinlocks, there is no preemption (alteast by low irql threads) and priority inversion idea may not apply. Thus priorities may not apply.

Thanks for all the inputs.