locking/rtqspinlock: Realtime queued spinlocks

Ideally we want the CPU to be preemptible even when inside or waiting for a lock. We cannot make it preemptible when inside a lock critical section, but we can try to make the task voluntarily yield the CPU when waiting for a lock.

This patch checks the need_sched() flag and yields the CPU when the preemption count is 1. IOW, the spin_lock() call isn't done in a region that doesn't allow preemption. Otherwise, it will just perform RT spinning with a minimum priority of 1.

Signed-off-by Waiman Long <[email protected]>

---
 kernel/locking/qspinlock_rt.h | 68 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 65 insertions(+), 3 deletions(-)

kernel/locking/qspinlock_rt.h +10 -0

index 0c4d051..18ec1f8 100644
@@ -43,6 +43,16 @@
  * it will have to break out of the MCS wait queue just like what is done
  * in the OSQ lock. Then it has to retry RT spinning if it has been boosted
  * to RT priority.
+ *
+ * Another RT requirement is that the CPU need to be preemptible even when
+ * waiting for a spinlock. If the task has already acquired the lock, we
+ * will let it run to completion to release the lock and reenable preemption.
+ * For non-nested spinlock, a spinlock waiter will periodically check
+ * need_resched flag to see if it should break out of the waiting loop and
+ * yield the CPU as long as the preemption count indicates just one
+ * preempt_disabled(). For nested spinlock with outer lock acquired, it will
+ * boost its priority to the highest RT priority level to try to acquire the
+ * inner lock, finish up its work, release the locks and reenable preemption.
  */
 #include <linux/sched.h>
 

@@ -51,6 +61,15 @@
 #endif

Quoted 38 lines · Waiman Long

Ideally we want the CPU to be preemptible even when inside or waiting for a lock. We cannot make it preemptible when inside a lock critical section, but we can try to make the task voluntarily yield the CPU when waiting for a lock.

This patch checks the need_sched() flag and yields the CPU when the preemption count is 1. IOW, the spin_lock() call isn't done in a region that doesn't allow preemption. Otherwise, it will just perform RT spinning with a minimum priority of 1.

Signed-off-by Waiman Long <[email protected]>

---
 kernel/locking/qspinlock_rt.h | 68 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 65 insertions(+), 3 deletions(-)

kernel/locking/qspinlock_rt.h +10 -0

index 0c4d051..18ec1f8 100644
@@ -43,6 +43,16 @@
  * it will have to break out of the MCS wait queue just like what is done
  * in the OSQ lock. Then it has to retry RT spinning if it has been boosted
  * to RT priority.
+ *
+ * Another RT requirement is that the CPU need to be preemptible even when
+ * waiting for a spinlock. If the task has already acquired the lock, we
+ * will let it run to completion to release the lock and reenable preemption.
+ * For non-nested spinlock, a spinlock waiter will periodically check
+ * need_resched flag to see if it should break out of the waiting loop and
+ * yield the CPU as long as the preemption count indicates just one
+ * preempt_disabled(). For nested spinlock with outer lock acquired, it will
+ * boost its priority to the highest RT priority level to try to acquire the
+ * inner lock, finish up its work, release the locks and reenable preemption.
  */
 #include <linux/sched.h>
 

@@ -51,6 +61,15 @@
 #endif

kernel/locking/qspinlock_rt.h line 71

Quoted 10 lines

kernel/locking/qspinlock_rt.h +8 -0

 
 /*
+ * Rescheduling is only needed when it is in the task context, the
+ * PREEMPT_NEED_RESCHED flag is set and the preemption count is one.
+ * If only the TIF_NEED_RESCHED flag is set, it will be moved to RT
+ * spinning with a minimum priority of 1.
+ */
+#define rt_should_resched()	(preempt_count() == \
+				(PREEMPT_OFFSET | PREEMPT_NEED_RESCHED))
+

Maybe I am missing something... but

On x86, PREEMPT_NEED_RESCHED is used in an inverting style, i.e. 0 indicates "need to reschedule" and preempt_count() masks away this very bit, which makes rt_should_resched() always false. So...

Regards,
Boqun

For nested spinlock with outer lock acquired, it will
+ * boost its priority to the highest RT priority level to try to acquire the
+ * inner lock, finish up its work, release the locks and reenable preemption.

This patchset introduces a new variant of queued spinlocks - the realtime queued spinlocks. The purpose of this new variant is to support real spinlock in a realtime environment where high priority RT tasks should be allowed to complete its work ASAP. This means as little waiting time for spinlocks as possible.

Non-RT tasks will wait for spinlocks in the MCS waiting queue as usual. RT tasks and interrupts will spin directly on the spinlocks and use the priority value in the pending byte to arbitrate who get the lock first.

Patch 1 removes the unused spin_lock_bh_nested() API.

Patch 2 introduces the basic realtime queued spinlocks where the pending byte is used for storing the priority of the highest priority RT task that is waiting on the spinlock. All the RT tasks will spin directly on the spinlock instead of waiting in the queue.

Quoted 11 lines · Waiman Long

This patchset introduces a new variant of queued spinlocks - the realtime queued spinlocks. The purpose of this new variant is to support real spinlock in a realtime environment where high priority RT tasks should be allowed to complete its work ASAP. This means as little waiting time for spinlocks as possible.

Non-RT tasks will wait for spinlocks in the MCS waiting queue as usual. RT tasks and interrupts will spin directly on the spinlocks and use the priority value in the pending byte to arbitrate who get the lock first.

Quoted 7 lines

Patch 1 removes the unused spin_lock_bh_nested() API.

Patch 2 introduces the basic realtime queued spinlocks where the pending byte is used for storing the priority of the highest priority RT task that is waiting on the spinlock. All the RT tasks will spin directly on the spinlock instead of waiting in the queue.

OK, so a single numerical field isn't sufficient to describe priority anymore, since we added DEADLINE support things have gotten a lot more complex.

From what I read from the code, DL tasks all have the same priority that

Also, the whole approach worries me, it has the very real possibility of re-introducing a bunch of starvation cases avoided by the fair lock.

Is there a real problem with -RT that inspired these patches?

I know that in -RT kernel, all the non-raw spinlocks are replaced by rtmutex which is a sleeping lock. This can have a real performance impact on systems with more than a few cores. The rtmutex isn't fair either.

Do you think it is better to keep the raw spinlocks fair and only have the non-raw spinlocks use the RT version?

Quoted 3 lines · On Wed, 4 Jan 2017 10:25:14 -0500 Waiman Long <[email protected]> wrote:

I know that in -RT kernel, all the non-raw spinlocks are replaced by rtmutex which is a sleeping lock. This can have a real performance impact on systems with more than a few cores. The rtmutex isn't fair either.

We do fine on 80+ CPUs. Is that enough cores for you ;-)

Note, it's not a true sleeping lock, because of the adaptive nature. That is, it spins unless the owner of the lock is sleeping, in which case, it too will sleep (why spin waiting for a task that isn't running). But if the owner is running, it will spin too.

We also have tricks to keep normal preemption (like SCHED_OTHER tasks running out of their time slot) when they have a lock. This keeps contention down on tasks owning locks while sleeping.

Quoted 2 lines

Do you think it is better to keep the raw spinlocks fair and only have the non-raw spinlocks use the RT version?

Yes.

Note, I also want to get rt_mutex into the kernel first for all sleeping locks. That is, get the logic in before we convert spin_locks to sleeping locks.

-- Steve

Quoted 7 lines · Steven Rostedt

Quoted 3 lines · On Wed, 4 Jan 2017 10:25:14 -0500 Waiman Long <[email protected]> wrote:

I know that in -RT kernel, all the non-raw spinlocks are replaced by rtmutex which is a sleeping lock. This can have a real performance impact on systems with more than a few cores. The rtmutex isn't fair either.

Quoted 1 line

We do fine on 80+ CPUs. Is that enough cores for you ;-)

It depends on what you mean fine. I haven't done the actual benchmark yet, but I believe that a -RT system with 80+ CPUs will feel noticeably slower for non-RT tasks than a system with non-RT kernel. I am not saying that the system will slow down significantly, but the slow down will certainly be noticeable.

Quoted 5 lines

Note, it's not a true sleeping lock, because of the adaptive nature. That is, it spins unless the owner of the lock is sleeping, in which case, it too will sleep (why spin waiting for a task that isn't running). But if the owner is running, it will spin too.

I think this is a recent change by Davidlohr. However, the spinning is limited to the top waiter. The rests will still go to sleep.

Quoted 4 lines

Note, I also want to get rt_mutex into the kernel first for all sleeping locks. That is, get the logic in before we convert spin_locks to sleeping locks.

The rtmutex code is already in the upstream kernel. It is just that there isn't any code yet that can let you flip a switch (a config option) and change all sleeping locks to use rtmutex.

Quoted 3 lines

OK, so a single numerical field isn't sufficient to describe priority anymore, since we added DEADLINE support things have gotten a lot more complex.

From what I read from the code, DL tasks all have the same priority that is higher than any of the RT tasks. So you mean DL tasks have other property that kind of categorizing them into different sub-priorities that is not being reflected in their priority level. Is that right?

Quoted 20 lines · Peter Zijlstra

Quoted 18 lines · Waiman Long

This patchset introduces a new variant of queued spinlocks - the realtime queued spinlocks. The purpose of this new variant is to support real spinlock in a realtime environment where high priority RT tasks should be allowed to complete its work ASAP. This means as little waiting time for spinlocks as possible.

Non-RT tasks will wait for spinlocks in the MCS waiting queue as usual. RT tasks and interrupts will spin directly on the spinlocks and use the priority value in the pending byte to arbitrate who get the lock first.

Patch 1 removes the unused spin_lock_bh_nested() API.

Patch 2 introduces the basic realtime queued spinlocks where the pending byte is used for storing the priority of the highest priority RT task that is waiting on the spinlock. All the RT tasks will spin directly on the spinlock instead of waiting in the queue.

Quoted 3 lines

OK, so a single numerical field isn't sufficient to describe priority anymore, since we added DEADLINE support things have gotten a lot more complex.

From what I read from the code, DL tasks all have the same priority that is higher than any of the RT tasks. So you mean DL tasks have other property that kind of categorizing them into different sub-priorities that is not being reflected in their priority level. Is that right?

Quoted 2 lines

Also, the whole approach worries me, it has the very real possibility of re-introducing a bunch of starvation cases avoided by the fair lock.

Starvation can happen when there is a constant stream of RT or DL tasks grabbing the lock, or when there is an interrupt storm. However I am making the assumption that RT systems should have sufficient resource available that the RT tasks won't saturate the hardware or we can't have RT guarantee in this case.

Quoted 2 lines

Is there a real problem with -RT that inspired these patches?

I know that in -RT kernel, all the non-raw spinlocks are replaced by rtmutex which is a sleeping lock. This can have a real performance impact on systems with more than a few cores. The rtmutex isn't fair either.

Do you think it is better to keep the raw spinlocks fair and only have the non-raw spinlocks use the RT version?

Quoted 23 lines · Waiman Long

Quoted 22 lines · Peter Zijlstra

Quoted 11 lines · Waiman Long

This patchset introduces a new variant of queued spinlocks - the realtime queued spinlocks. The purpose of this new variant is to support real spinlock in a realtime environment where high priority RT tasks should be allowed to complete its work ASAP. This means as little waiting time for spinlocks as possible.

Non-RT tasks will wait for spinlocks in the MCS waiting queue as usual. RT tasks and interrupts will spin directly on the spinlocks and use the priority value in the pending byte to arbitrate who get the lock first.

Quoted 7 lines

Patch 1 removes the unused spin_lock_bh_nested() API.

Patch 2 introduces the basic realtime queued spinlocks where the pending byte is used for storing the priority of the highest priority RT task that is waiting on the spinlock. All the RT tasks will spin directly on the spinlock instead of waiting in the queue.

OK, so a single numerical field isn't sufficient to describe priority anymore, since we added DEADLINE support things have gotten a lot more complex.

Quoted 4 lines

From what I read from the code, DL tasks all have the same priority that is higher than any of the RT tasks. So you mean DL tasks have other property that kind of categorizing them into different sub-priorities that is not being reflected in their priority level. Is that right?

Correct, primarily their deadline. That is, the scheduling function for the class picks the task with the earliest deadline.

Quoted 7 lines

Quoted 2 lines

Also, the whole approach worries me, it has the very real possibility of re-introducing a bunch of starvation cases avoided by the fair lock.

Starvation can happen when there is a constant stream of RT or DL tasks grabbing the lock, or when there is an interrupt storm. However I am making the assumption that RT systems should have sufficient resource available that the RT tasks won't saturate the hardware or we can't have RT guarantee in this case.

That only works on UP, on SMP you only need a combined utilization of 1 to completely saturate a lock.

Quoted 5 lines

Quoted 1 line

Is there a real problem with -RT that inspired these patches?

I know that in -RT kernel, all the non-raw spinlocks are replaced by rtmutex which is a sleeping lock. This can have a real performance impact on systems with more than a few cores. The rtmutex isn't fair either.

Quoted 2 lines

Do you think it is better to keep the raw spinlocks fair and only have the non-raw spinlocks use the RT version?

I don't get what you're saying here. Are you proposing to replace the rtmutex with this rtspinlock? That will very fundamentally not work. The important part of the conversion of spinlock -> rtmutex is acquiring the preemptability. Using this rtspinlock looses that and breaks the entirety of what -rt is about.

What I am saying that we don't need to change spinlock to rtmutex in a -RT kernel. Instead, we can use rtqspinlock for this purpose. All the sleeping locks will still be converted to rtmutex.

Conversion of rtmutex does allow forced CPU preemption when there is a need for that. What rtqspinlock can provide is voluntary preemption where the lock waiters explicitly yield the CPU while waiting for the lock. I use the need_resched() to detect if CPU yielding is necessary. However, if the CPU was in a preempt disabled region before the spin_lock() call, we can't yield the CPU. The only way is to raise its priority and try to get the lock ASAP.

Quoted 3 lines · Waiman Long

What I am saying that we don't need to change spinlock to rtmutex in a -RT kernel. Instead, we can use rtqspinlock for this purpose. All the sleeping locks will still be converted to rtmutex.

No-no-no..

Quoted 7 lines

Conversion of rtmutex does allow forced CPU preemption when there is a need for that. What rtqspinlock can provide is voluntary preemption where the lock waiters explicitly yield the CPU while waiting for the lock. I use the need_resched() to detect if CPU yielding is necessary. However, if the CPU was in a preempt disabled region before the spin_lock() call, we can't yield the CPU. The only way is to raise its priority and try to get the lock ASAP.

And here you've lost your finger because the saw-blade didn't stop in time.

RT very fundamentally relies on the spinlock->rtmutex conversion to allow preempting things when a higher priority task comes along. A spinlock, of any kind, requires having preemption disabled while holding the lock. If the critical section is of unbounded latency, you have unbounded preemption latency and RT is no more.

Its not about PI on contention, although that helps inversion scenarios. Its about allowing preemption, which fundamentally requires a sleeping lock to be used.

Many of the spinlock sections of mainline are not well behaved in an RT sense and therefore must not disable preemption. Similar for the IRQ disable regions and hence we have the whole threaded interrupt stuff.

I do make the assumption that spinlock critical sections are behaving well enough. Apparently, that is not a valid assumption. I sent these RFC patches out to see if it was an idea worth pursuing. If not, I can drop these patches. Anyway, thanks for the feedback.

Quoted 4 lines · On Thu, 5 Jan 2017 12:07:21 -0500 Waiman Long <[email protected]> wrote:

I do make the assumption that spinlock critical sections are behaving well enough. Apparently, that is not a valid assumption. I sent these RFC patches out to see if it was an idea worth pursuing. If not, I can drop these patches. Anyway, thanks for the feedback.

Yes, the assumption is incorrect. There are places that can hold a spin lock for several hundreds of microseconds. If you can't preempt them, you'll never get below several hundreds of microseconds in latency.

And it would be hard to pick and choose (we already do this to decide what can be a raw_spin_lock), because you need to audit all use cases of a spin_lock as well as all the locks taken while holding that spin_lock.

-- Steve

RT very fundamentally relies on the spinlock->rtmutex conversion to allow preempting things when a higher priority task comes along. A spinlock, of any kind, requires having preemption disabled while holding the lock. If the critical section is of unbounded latency, you have unbounded preemption latency and RT is no more.

Its not about PI on contention, although that helps inversion scenarios. Its about allowing preemption, which fundamentally requires a sleeping lock to be used.