reduce nohz_full syscall overhead by 10%

From: Rik van Riel <[email protected]>

On syscall entry with nohz_full on, we enable interrupts, call user_exit, disable interrupts, do something, re-enable interrupts, and go on our merry way.

Profiling shows that a large amount of the nohz_full overhead comes from the extraneous disabling and re-enabling of interrupts. Andy suggested simply not enabling interrupts until after the context tracking code has done its thing, which allows us to skip a whole interrupt disable & re-enable cycle.

This patch builds on top of these patches by Paolo:
https://lkml.org/lkml/2015/4/28/188
https://lkml.org/lkml/2015/4/29/139

Together with this patch I posted earlier this week, the syscall path on a nohz_full cpu seems to be about 10% faster.
https://lkml.org/lkml/2015/4/24/394

My test is a simple microbenchmark that calls getpriority() in a loop 10 million times:

                run time        system time
vanilla         5.49s           2.08s
__acct patch    5.21s           1.92s
both patches    4.88s           1.71s

From: Rik van Riel <[email protected]>

On syscall entry with nohz_full on, we enable interrupts, call user_exit, disable interrupts, do something, re-enable interrupts, and go on our merry way.

Profiling shows that a large amount of the nohz_full overhead comes from the extraneous disabling and re-enabling of interrupts. Andy suggested simply not enabling interrupts until after the context tracking code has done its thing, which allows us to skip a whole interrupt disable & re-enable cycle.

This patch builds on top of these patches by Paolo:
https://lkml.org/lkml/2015/4/28/188
https://lkml.org/lkml/2015/4/29/139

Together with this patch I posted earlier this week, the syscall path on a nohz_full cpu seems to be about 10% faster.
https://lkml.org/lkml/2015/4/24/394

My test is a simple microbenchmark that calls getpriority() in a loop 10 million times:

run time system time
vanilla 5.49s 2.08s
__acct patch 5.21s 1.92s
both patches 4.88s 1.71s

Quoted 8 lines

This patch builds on top of these patches by Paolo:
https://lkml.org/lkml/2015/4/28/188
https://lkml.org/lkml/2015/4/29/139

Together with this patch I posted earlier this week, the syscall path on a nohz_full cpu seems to be about 10% faster.
https://lkml.org/lkml/2015/4/24/394

Quoted 7 lines

My test is a simple microbenchmark that calls getpriority() in a loop 10 million times:

run time system time
vanilla 5.49s 2.08s
__acct patch 5.21s 1.92s
both patches 4.88s 1.71s

Just curious, what are the numbers if you don't have context tracking enabled, i.e. without nohz_full?

I.e. what's the baseline we are talking about?

Quoted 1 line

I.e. what's the baseline we are talking about?

It's an astounding difference. This is not a kernel without nohz_full, just a CPU without nohz_full running the same kernel I tested with yesterday:

run time system time
vanilla 5.49s 2.08s
__acct patch 5.21s 1.92s
both patches 4.88s 1.71s
CPU w/o nohz 3.12s 1.63s <-- your numbers, mostly

What is even more interesting is that the majority of the time difference seems to come from _user_ time, which has gone down from around 3.4 seconds in the vanilla kernel to around 1.5 seconds on the CPU without nohz_full enabled...

At syscall entry time, the nohz_full context tracking code is very straightforward. We check thread_info->flags & _TIF_WORK_SYSCALL_ENTRY, and call syscall_trace_enter_phase1, which handles USER -> KERNEL context transition.

Syscall exit time is a convoluted mess. Both do_notify_resume and syscall_trace_leave call exit_user() on entry and enter_user() on exit, leaving the time spent looping around between int_with_check and syscall_return: in entry_64.S accounted as user time.

I sent an email about this last night, it may be useful to add a third test & function call point to the syscall return code, where we can call user_enter() just ONCE, and remove the other context tracking calls from that loop.

Quoted 27 lines · Rik van Riel

Quoted 1 line

I.e. what's the baseline we are talking about?

It's an astounding difference. This is not a kernel without nohz_full, just a CPU without nohz_full running the same kernel I tested with yesterday:

run time system time
vanilla 5.49s 2.08s

__acct patch  5.21s           1.92s
both patches  4.88s           1.71s
CPU w/o nohz  3.12s           1.63s    <-- your numbers, mostly

What is even more interesting is that the majority of the time difference seems to come from _user_ time, which has gone down from around 3.4 seconds in the vanilla kernel to around 1.5 seconds on the CPU without nohz_full enabled...

At syscall entry time, the nohz_full context tracking code is very straightforward. We check thread_info->flags & _TIF_WORK_SYSCALL_ENTRY, and call syscall_trace_enter_phase1, which handles USER -> KERNEL context transition.

Syscall exit time is a convoluted mess. Both do_notify_resume and syscall_trace_leave call exit_user() on entry and enter_user() on exit, leaving the time spent looping around between int_with_check and syscall_return: in entry_64.S accounted as user time.

Quoted 4 lines

I sent an email about this last night, it may be useful to add a third test & function call point to the syscall return code, where we can call user_enter() just ONCE, and remove the other context tracking calls from that loop.

So what I'm wondering about is the big picture:

- This is crazy big overhead in something as fundamental as system calls!

- We don't even have the excuse of the syscall auditing code, which kind of has to run for every syscall if it wants to do its job!

- [ The 'precise vtime' stuff that is driven from syscall entry/exit is crazy, and I hope not enabled in any distro. ]

- So why are we doing this in every syscall time at all?

Basically the whole point of user-context tracking is to be able to flush pending RCU callbacks. But that's crazy, we can sure defer a few kfree()s on this CPU, even indefinitely!

If some other CPU does a sync_rcu(), then it can very well pluck those callbacks from this super low latency CPU's RCU lists (with due care) and go and free stuff itself ... There's no need to disturb this CPU for that!

If user-space does not do anything kernel-ish then there won't be any new RCU callbacks piled up, so it's not like it's a resource leak issue either.

So what's the point? Why not remove this big source of overhead altogether?

Quoted 2 lines

So what's the point? Why not remove this big source of overhead altogether?

The last time I asked, the impression I got was that we needed two things:

1. We can't pluck things from the RCU list without knowing whether the CPU is in an RCU read-side critical section, and we can't know that unless we have regular grade periods or we know that the CPU is idle. To make the CPU detectably idle, we need to set a bit somewhere.

2. To suppress the timing tick, we need to get some timing for, um, the scheduler? I wasn't really sure about this one.

Could we reduce the overhead by making the IN_USER vs IN_KERNEL indication be a single bit and, worst case, an rdtsc and maybe a subtraction? We could probably get away with banning full nohz on non-invariant tsc systems.

(I do understand why it would be tricky to transition from IN_USER to IN_KERNEL with IRQs on. Solvable, maybe, but tricky.)

Quoted 11 lines · Andy Lutomirski

Quoted 2 lines

So what's the point? Why not remove this big source of overhead altogether?

The last time I asked, the impression I got was that we needed two things:

1. We can't pluck things from the RCU list without knowing whether the CPU is in an RCU read-side critical section, and we can't know that unless we have regular grade periods or we know that the CPU is idle. To make the CPU detectably idle, we need to set a bit somewhere.

'Idle' as in 'executing pure user-space mode, without entering the kernel and possibly doing an rcu_read_lock()', right?

So we don't have to test it from the remote CPU: we could probe such CPUs via a single low-overhead IPI. I'd much rather push such overhead to sync_rcu() than to the syscall entry code!

I can understand people running hard-RT workloads not wanting to see the overhead of a timer tick or a scheduler tick with variable (and occasionally heavy) work done in IRQ context, but the jitter caused by a single trivial IPI with constant work should be very, very low and constant.

Quoted 5 lines

I can understand people running hard-RT workloads not wanting to see the overhead of a timer tick or a scheduler tick with variable (and occasionally heavy) work done in IRQ context, but the jitter caused by a single trivial IPI with constant work should be very, very low and constant.

Not if the realtime workload is running inside a KVM guest.

At that point an IPI, either on the host or in the guest, involves a full VMEXIT & VMENTER cycle.

Quoted 7 lines · Rik van Riel

Quoted 5 lines

I can understand people running hard-RT workloads not wanting to see the overhead of a timer tick or a scheduler tick with variable (and occasionally heavy) work done in IRQ context, but the jitter caused by a single trivial IPI with constant work should be very, very low and constant.

Not if the realtime workload is running inside a KVM guest.

I don't buy this:

Quoted 2 lines

At that point an IPI, either on the host or in the guest, involves a full VMEXIT & VMENTER cycle.

So a full VMEXIT/VMENTER costs how much, 2000 cycles? That's around 1 usec on recent hardware, and I bet it will get better with time.

I'm not aware of any hard-RT workload that cannot take 1 usec latencies.

Quoted 19 lines · Ingo Molnar

Quoted 7 lines · Rik van Riel

Quoted 5 lines

I can understand people running hard-RT workloads not wanting to see the overhead of a timer tick or a scheduler tick with variable (and occasionally heavy) work done in IRQ context, but the jitter caused by a single trivial IPI with constant work should be very, very low and constant.

Not if the realtime workload is running inside a KVM guest.

I don't buy this:

Quoted 2 lines

At that point an IPI, either on the host or in the guest, involves a full VMEXIT & VMENTER cycle.

So a full VMEXIT/VMENTER costs how much, 2000 cycles? That's around 1 usec on recent hardware, and I bet it will get better with time.

Quoted 2 lines

I'm not aware of any hard-RT workload that cannot take 1 usec latencies.

Now think about doing this kind of IPI from inside a guest, to another VCPU on the same guest.

Now you are looking at VMEXIT/VMENTER on the first VCPU,

plus the cost of the IPI on the host, plus the cost of the emulation layer, plus VMEXIT/VMENTER on the second VCPU to trigger the IPI work, and possibly a second VMEXIT/VMENTER for IPI completion.

I suspect it would be better to do RCU callback offload in some other way.

Or we could do that in the syscall path with a single store of a constant flag to a location in the task struct. We have a number of natural flags that get written on syscall entry, such as:

        pushq_cfi $__USER_DS                    /* pt_regs->ss */

That goes to a constant location on the kernel stack. On return from system calls we could write 0 to that location.

So the remote CPU would have to do a read of this location. There are two cases:

- If it's 0, then it has observed quiescent state on that CPU. (It does not have to be atomics anymore, as we'd only observe the value and MESI coherency takes care of it.)

- If it's not 0 then the remote CPU is not executing user-space code and we can install (remotely) a TIF_NOHZ flag in it and expect it to process it either on return to user-space or on a context switch.

This way, unless I'm missing something, reduces the overhead to a single store to a hot cacheline on return-to-userspace - which instruction if we place it well might as well be close to zero cost. No syscall entry cost. Slow-return cost only in the (rare) case of someone using synchronize_rcu().

Quoted 8 lines · Ingo Molnar

Or we could do that in the syscall path with a single store of a constant flag to a location in the task struct. We have a number of natural flags that get written on syscall entry, such as:

        pushq_cfi $__USER_DS                    /* pt_regs->ss */

That goes to a constant location on the kernel stack. On return from system calls we could write 0 to that location.

Quoted 6 lines · Rik van Riel

Quoted 4 lines · Ingo Molnar

Or we could do that in the syscall path with a single store of a constant flag to a location in the task struct. We have a number of natural flags that get written on syscall entry, such as:

Quoted 4 lines

Quoted 4 lines

        pushq_cfi $__USER_DS                    /* pt_regs->ss */

That goes to a constant location on the kernel stack. On return from system calls we could write 0 to that location.

Huh? IRET with zero there will fault, and we can't guarantee that all syscalls return using sysret. [...]

[...] Also, we'd have to audit all the entries, and system_call_after_swapgs currently enables interrupts early enough that an interrupt before all the pushes will do unpredictable things to pt_regs.

We could further abuse orig_ax, but that would require a lot of auditing. Honestly, though, I think keeping a flag in an otherwise-hot cache line is a better bet. [...]

[...] Also, making it per-cpu instead of per-task will probably be easier on the RCU code, since otherwise the RCU code will have to do some kind of synchronization (even if it's a wait-free probe of the rq lock or similar) to figure out which pt_regs to look at.

If we went that route, I'd advocate sticking the flag in tss->sp1. That cacheline is unconditionally read on kernel entry already, and sp1 is available in tip:x86/asm (and maybe even in Linus' tree -- I lost track). [1]

Alternatively, I'd suggest that we actually add a whole new word to pt_regs.

Regarding the user/kernel execution time split measurement:

1) the same flag could be used to sample a remote CPU's statistics from another CPU and update the stats in the currently executing task. As long as there's at least one non-nohz-full CPU, this would work. Or are there systems were all CPUs are nohz-full?

2) Alternatively we could just drive user/kernel split statistics from context switches, which would be inaccurate if the workload is SCHED_FIFO that only rarely context switches.

How does this sound?

Quoted 9 lines · Andy Lutomirski

Quoted 8 lines · Rik van Riel

Quoted 6 lines · Ingo Molnar

Or we could do that in the syscall path with a single store of a constant flag to a location in the task struct. We have a number of natural flags that get written on syscall entry, such as:

        pushq_cfi $__USER_DS                    /* pt_regs->ss */

Quoted 5 lines

Quoted 2 lines

Quoted 2 lines

That goes to a constant location on the kernel stack. On return from system calls we could write 0 to that location.

Huh? IRET with zero there will fault, and we can't guarantee that all syscalls return using sysret. [...]

So IRET is a slowpath - I was thinking about the fastpath mainly.

Quoted 5 lines

[...] Also, we'd have to audit all the entries, and system_call_after_swapgs currently enables interrupts early enough that an interrupt before all the pushes will do unpredictable things to pt_regs.

An irq hardware frame won't push zero to that selector value, right? That's the only bad thing that would confuse the code.

But yes, safely accessing the remote task is a complication, but with such a scheme we cannot avoid it, we'd still have to set TIF_NOHZ. So even if we do:

Quoted 7 lines

If we went that route, I'd advocate sticking the flag in tss->sp1. That cacheline is unconditionally read on kernel entry already, and sp1 is available in tip:x86/asm (and maybe even in Linus' tree -- I lost track). [1]

Alternatively, I'd suggest that we actually add a whole new word to pt_regs.

... we'd still have to set TIF_NOHZ and are back to square one in terms of race complexity.

But it's not overly complex: by taking the remote CPU's rq-lock from synchronize_rcu() we could get a stable pointer to the currently executing task.

And if we do that, we might as well use the opportunity and take a look at pt_regs as well - this is why sticking it into pt_regs might be better.

So I'd:

- enlarge pt_regs by a word and stick the flag there (this allocation is essentially free)

- update the word from entry/exit

- synchronize_rcu() avoids having to send an IPI by taking a peak at rq->curr's pt_regs::flag, and if:

- the flag is 0 then it has observed a quiescent state.

- the flag is 1, then it would set TIF_NOHZ and wait for a completion from a TIF_NOHZ callback.

Quoted 8 lines

Quoted 4 lines

[...] Also, we'd have to audit all the entries, and system_call_after_swapgs currently enables interrupts early enough that an interrupt before all the pushes will do unpredictable things to pt_regs.

An irq hardware frame won't push zero to that selector value, right? That's the only bad thing that would confuse the code.

I think it's not quite that simple. The syscall entry looks like, roughly:

fix rsp;
sti;
push ss;
push rsp;
push flags;
push cs;
push rip;

We can get an interrupt part-way through those pushes. Maybe there's no bad place where we could get an IRQ since SS is first, [...]

[...] but this is still nasty.

I think I prefer a per-cpu approach over a per-task approach, since it's easier to reason about and it should still only require one instruction on entry and one instruction on exit.

- synchronize_rcu() avoids having to send an IPI by taking a peak at rq->curr's pt_regs::flag, and if:

- the flag is 0 then it has observed a quiescent state.

- the flag is 1, then it would set TIF_NOHZ and wait for a completion from a TIF_NOHZ callback.

Quoted 8 lines · Ingo Molnar

- synchronize_rcu() avoids having to send an IPI by taking a peak at rq->curr's pt_regs::flag, and if:

- the flag is 0 then it has observed a quiescent state.

- the flag is 1, then it would set TIF_NOHZ and wait for a completion from a TIF_NOHZ callback.

Isn't this racy?

synchronize_rcu CPU nohz CPU
---------------------------------------------------------
set flag = 0
read flag = 0
return to userspace
set TIF_NOHZ

and there's no guarantee that TIF_NOHZ is ever processed by the nohz CPU.

Quoted 8 lines · Ingo Molnar

- synchronize_rcu() avoids having to send an IPI by taking a peak at rq->curr's pt_regs::flag, and if:

- the flag is 0 then it has observed a quiescent state.

- the flag is 1, then it would set TIF_NOHZ and wait for a completion from a TIF_NOHZ callback.

Isn't this racy?

synchronize_rcu CPU nohz CPU
---------------------------------------------------------
set flag = 0
read flag = 0
return to userspace
set TIF_NOHZ

and there's no guarantee that TIF_NOHZ is ever processed by the nohz CPU.

Quoted 8 lines · Ingo Molnar

- synchronize_rcu() avoids having to send an IPI by taking a peak at rq->curr's pt_regs::flag, and if:

- the flag is 0 then it has observed a quiescent state.

- the flag is 1, then it would set TIF_NOHZ and wait for a completion from a TIF_NOHZ callback.

Isn't this racy?

synchronize_rcu CPU nohz CPU
---------------------------------------------------------
set flag = 0
read flag = 0
return to userspace
set TIF_NOHZ

and there's no guarantee that TIF_NOHZ is ever processed by the nohz CPU.

Isn't this racy?

synchronize_rcu CPU nohz CPU
---------------------------------------------------------
set flag = 0
read flag = 0
return to userspace
set TIF_NOHZ

and there's no guarantee that TIF_NOHZ is ever processed by the nohz CPU.

Quoted 10 lines · Paolo Bonzini

Isn't this racy?

synchronize_rcu CPU nohz CPU
---------------------------------------------------------
set flag = 0
read flag = 0
return to userspace
set TIF_NOHZ

and there's no guarantee that TIF_NOHZ is ever processed by the nohz CPU.

Looking at the code some more, a flag is not going to be enough.

An irq can hit while we are in kernel mode, leading to the task's "rcu active" counter being incremented twice.

However, currently the RCU code seems to use a much more complex counting scheme, with a different increment for kernel/task use, and irq use.

This counter seems to be modeled on the task preempt_counter, where we do care about whether we are in task context, irq context, or softirq context.

On the other hand, the RCU code only seems to care about whether or not a CPU is in an extended quiescent state, or is potentially in an RCU critical section.

Paul, what is the reason for RCU using a complex counter, instead of a simple increment for each potential kernel/RCU entry, like rcu_read_lock() does with CONFIG_PREEMPT_RCU enabled?

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

Quoted 3 lines · Rik van Riel

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

Depends on exactly what you are asking. If you are asking if I could add a few more checks to preemptible RCU and speed up grace-period detection in a number of cases, the answer is very likely "yes". This is on my list, but not particularly high priority. If you are asking whether CPU 0 could access ->rcu_read_lock_nesting of some task running on some other CPU, in theory, the answer is "yes", but in practice that would require putting full memory barriers in both rcu_read_lock() and rcu_read_unlock(), so the real answer is "no".

Or am I missing your point?

Quoted 15 lines · Paul E. McKenney

Quoted 3 lines · Rik van Riel

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

Depends on exactly what you are asking. If you are asking if I could add a few more checks to preemptible RCU and speed up grace-period detection in a number of cases, the answer is very likely "yes". This is on my list, but not particularly high priority. If you are asking whether CPU 0 could access ->rcu_read_lock_nesting of some task running on some other CPU, in theory, the answer is "yes", but in practice that would require putting full memory barriers in both rcu_read_lock() and rcu_read_unlock(), so the real answer is "no".

Quoted 1 line

Or am I missing your point?

The main question is "how can we greatly reduce the overhead of nohz_full, by simplifying the RCU extended quiescent state code called in the syscall fast path, and maybe piggyback on that to do time accounting for remote CPUs?"

Your memory barrier answer above makes it clear we will still want to do the RCU stuff at syscall entry & exit time, at least on x86, where we already have automatic and implicit memory barriers.

Quoted 23 lines · Rik van Riel

Quoted 15 lines · Paul E. McKenney

Quoted 3 lines · Rik van Riel

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

Depends on exactly what you are asking. If you are asking if I could add a few more checks to preemptible RCU and speed up grace-period detection in a number of cases, the answer is very likely "yes". This is on my list, but not particularly high priority. If you are asking whether CPU 0 could access ->rcu_read_lock_nesting of some task running on some other CPU, in theory, the answer is "yes", but in practice that would require putting full memory barriers in both rcu_read_lock() and rcu_read_unlock(), so the real answer is "no".

Quoted 1 line

Or am I missing your point?

The main question is "how can we greatly reduce the overhead of nohz_full, by simplifying the RCU extended quiescent state code called in the syscall fast path, and maybe piggyback on that to do time accounting for remote CPUs?"

Quoted 4 lines

Your memory barrier answer above makes it clear we will still want to do the RCU stuff at syscall entry & exit time, at least on x86, where we already have automatic and implicit memory barriers.

We do need to keep in mind that x86's automatic and implicit memory barriers do not order prior stores against later loads.

Hmmm... But didn't earlier performance measurements show that the bulk of the overhead was the delta-time computations rather than RCU accounting?

Quoted 29 lines · Paul E. McKenney

Quoted 27 lines · Rik van Riel

Quoted 15 lines · Paul E. McKenney

Quoted 3 lines · Rik van Riel

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

Depends on exactly what you are asking. If you are asking if I could add a few more checks to preemptible RCU and speed up grace-period detection in a number of cases, the answer is very likely "yes". This is on my list, but not particularly high priority. If you are asking whether CPU 0 could access ->rcu_read_lock_nesting of some task running on some other CPU, in theory, the answer is "yes", but in practice that would require putting full memory barriers in both rcu_read_lock() and rcu_read_unlock(), so the real answer is "no".

Quoted 1 line

Or am I missing your point?

The main question is "how can we greatly reduce the overhead of nohz_full, by simplifying the RCU extended quiescent state code called in the syscall fast path, and maybe piggyback on that to do time accounting for remote CPUs?"

Your memory barrier answer above makes it clear we will still want to do the RCU stuff at syscall entry & exit time, at least on x86, where we already have automatic and implicit memory barriers.

Quoted 5 lines

We do need to keep in mind that x86's automatic and implicit memory barriers do not order prior stores against later loads.

Hmmm... But didn't earlier performance measurements show that the bulk of the overhead was the delta-time computations rather than RCU accounting?

The bulk of the overhead was disabling and re-enabling irqs around the calls to rcu_user_exit and rcu_user_enter :)

Of the remaining time, about 2/3 seems to be the vtime stuff, and the other 1/3 the rcu code.

I suspect it makes sense to optimize both, though the vtime code may be the easiest :)

Quoted 7 lines · Rik van Riel

Quoted 2 lines · Paul E. McKenney

Hmmm... But didn't earlier performance measurements show that the bulk of the overhead was the delta-time computations rather than RCU accounting?

The bulk of the overhead was disabling and re-enabling irqs around the calls to rcu_user_exit and rcu_user_enter :)

Really??? OK... How about software irq masking? (I know, that is probably a bit of a scary change as well.)

Quoted 2 lines

Of the remaining time, about 2/3 seems to be the vtime stuff, and the other 1/3 the rcu code.

OK, worth some thought, then.

Quoted 2 lines

I suspect it makes sense to optimize both, though the vtime code may be the easiest :)

Making a crude version that does jiffies (or whatever) instead of fine-grained computations might give good bang for the buck. ;-)

Quoted 15 lines · Paul E. McKenney

Quoted 7 lines · Rik van Riel

Quoted 2 lines · Paul E. McKenney

Hmmm... But didn't earlier performance measurements show that the bulk of the overhead was the delta-time computations rather than RCU accounting?

The bulk of the overhead was disabling and re-enabling irqs around the calls to rcu_user_exit and rcu_user_enter :)

Really??? OK... How about software irq masking? (I know, that is probably a bit of a scary change as well.)

Quoted 2 lines

Of the remaining time, about 2/3 seems to be the vtime stuff, and the other 1/3 the rcu code.

Quoted 7 lines

OK, worth some thought, then.

Quoted 2 lines

I suspect it makes sense to optimize both, though the vtime code may be the easiest :)

Making a crude version that does jiffies (or whatever) instead of fine-grained computations might give good bang for the buck. ;-)

Ingo's idea is to simply have cpu 0 check the current task on all other CPUs, see whether that task is running in system mode, user mode, guest mode, irq mode, etc and update that task's vtime accordingly.

I suspect the runqueue lock is probably enough to do that, and between rcu state and PF_VCPU we probably have enough information to see what mode the task is running in, with just remote memory reads.

I looked at implementing the vtime bits (and am pretty sure how to do those now), and then spent some hours looking at the RCU bits, to see if we could not simplify both things at once, especially considering that the current RCU context tracking bits need to be called with irqs disabled.

You have RCU_FAST_NO_HZ=y, correct? Could you please try measuring with RCU_FAST_NO_HZ=n?

Quoted 2 lines · Paul E. McKenney

You have RCU_FAST_NO_HZ=y, correct? Could you please try measuring with RCU_FAST_NO_HZ=n?

FWIW, the syscall numbers I posted were RCU_FAST_NO_HZ=n. (I didn't profile to see where costs lie though)

Quoted 7 lines · Mike Galbraith

Quoted 2 lines · Paul E. McKenney

You have RCU_FAST_NO_HZ=y, correct? Could you please try measuring with RCU_FAST_NO_HZ=n?

FWIW, the syscall numbers I posted were RCU_FAST_NO_HZ=n. (I didn't profile to see where costs lie though)

(did that)

100000000 * stat() on isolated cpu

NO_HZ_FULL off        inactive     housekeeper    nohz_full
real    0m14.266s     0m14.367s    0m20.427s      0m27.921s 
user    0m1.756s      0m1.553s     0m1.976s       0m10.447s
sys     0m12.508s     0m12.769s    0m18.400s      0m17.464s
(real)  1.000         1.007        1.431          1.957

inactive housekeeper nohz_full
----------------------------------------------------------------------------------------------------------------------------------------------

 7.61%  [.] __xstat64                             11.12%  [k] context_tracking_exit                  7.41%  [k] context_tracking_exit
 7.04%  [k] system_call                            6.18%  [k] context_tracking_enter                 6.02%  [k] native_sched_clock
 6.96%  [k] copy_user_enhanced_fast_string         5.18%  [.] __xstat64                              4.69%  [k] rcu_eqs_enter_common.isra.37
 6.57%  [k] path_init                              4.89%  [k] system_call                            4.35%  [k] _raw_spin_lock
 5.92%  [k] system_call_after_swapgs               4.84%  [k] copy_user_enhanced_fast_string         4.30%  [k] context_tracking_enter
 5.44%  [k] lockref_put_return                     4.46%  [k] path_init                              4.25%  [k] kmem_cache_alloc
 4.69%  [k] link_path_walk                         4.30%  [k] system_call_after_swapgs               4.14%  [.] __xstat64
 4.47%  [k] lockref_get_not_dead                   4.12%  [k] kmem_cache_free                        3.89%  [k] rcu_eqs_exit_common.isra.38
 4.46%  [k] kmem_cache_free                        3.78%  [k] link_path_walk                         3.50%  [k] system_call
 4.20%  [k] kmem_cache_alloc                       3.62%  [k] lockref_put_return                     3.48%  [k] copy_user_enhanced_fast_string
 4.09%  [k] cp_new_stat                            3.43%  [k] kmem_cache_alloc                       3.02%  [k] system_call_after_swapgs
 3.38%  [k] vfs_getattr_nosec                      2.95%  [k] lockref_get_not_dead                   2.97%  [k] kmem_cache_free
 2.82%  [k] vfs_fstatat                            2.87%  [k] cp_new_stat                            2.88%  [k] lockref_put_return
 2.60%  [k] user_path_at_empty                     2.62%  [k] syscall_trace_leave                    2.61%  [k] link_path_walk
 2.47%  [k] path_lookupat                          1.91%  [k] vfs_getattr_nosec                      2.58%  [k] path_init
 2.14%  [k] strncpy_from_user                      1.89%  [k] syscall_trace_enter_phase1             2.15%  [k] lockref_get_not_dead
 2.11%  [k] getname_flags                          1.77%  [k] path_lookupat                          2.04%  [k] cp_new_stat
 2.10%  [k] generic_fillattr                       1.67%  [k] complete_walk                          1.89%  [k] generic_fillattr
 2.05%  [.] main                                   1.65%  [k] vfs_fstatat                            1.67%  [k] syscall_trace_leave
 1.89%  [k] complete_walk                          1.56%  [k] generic_fillattr                       1.59%  [k] vfs_getattr_nosec
 1.73%  [k] generic_permission                     1.55%  [k] user_path_at_empty                     1.49%  [k] get_vtime_delta
 1.50%  [k] system_call_fastpath                   1.54%  [k] strncpy_from_user                      1.32%  [k] user_path_at_empty
 1.37%  [k] legitimize_mnt                         1.53%  [k] getname_flags                          1.30%  [k] syscall_trace_enter_phase1

 1.30%  [k] dput                                   1.46%  [k] legitimize_mnt                         1.21%  [k] rcu_eqs_exit
 1.26%  [k] putname                                1.34%  [.] main                                   1.21%  [k] vfs_fstatat
 1.19%  [k] path_put                               1.32%  [k] int_with_check                         1.18%  [k] path_lookupat
 1.18%  [k] filename_lookup                        1.28%  [k] generic_permission                     1.15%  [k] getname_flags
 1.01%  [k] SYSC_newstat                           1.16%  [k] int_very_careful                       1.03%  [k] strncpy_from_user
 0.96%  [k] mntput_no_expire                       1.04%  [k] putname                                1.01%  [k] account_system_time
 0.79%  [k] path_cleanup                           0.94%  [k] dput                                   1.00%  [k] complete_walk
 0.79%  [k] mntput                                 0.91%  [k] context_tracking_user_exit             0.99%  [k] vtime_account_user

Quoted 7 lines

100000000 * stat() on isolated cpu

NO_HZ_FULL off        inactive     housekeeper    nohz_full
real    0m14.266s     0m14.367s    0m20.427s      0m27.921s 
user    0m1.756s      0m1.553s     0m1.976s       0m10.447s
sys     0m12.508s     0m12.769s    0m18.400s      0m17.464s
(real)  1.000         1.007        1.431          1.957

Does the attached patch help at all?

Quoted 7 lines · Paul E. McKenney

Quoted 7 lines

100000000 * stat() on isolated cpu

NO_HZ_FULL off        inactive     housekeeper    nohz_full
real    0m14.266s     0m14.367s    0m20.427s      0m27.921s 
user    0m1.756s      0m1.553s     0m1.976s       0m10.447s
sys     0m12.508s     0m12.769s    0m18.400s      0m17.464s
(real)  1.000         1.007        1.431          1.957

Quoted 1 line

Does the attached patch help at all?

nohz_full
0m27.073s
0m9.423s
0m17.602s

Not a complete retest, and a pull in between, but I'd say that's a no.

Quoted 15 lines · Paul E. McKenney

Quoted 7 lines · Rik van Riel

Quoted 2 lines · Paul E. McKenney

Hmmm... But didn't earlier performance measurements show that the bulk of the overhead was the delta-time computations rather than RCU accounting?

The bulk of the overhead was disabling and re-enabling irqs around the calls to rcu_user_exit and rcu_user_enter :)

Really??? OK... How about software irq masking? (I know, that is probably a bit of a scary change as well.)

Quoted 2 lines

Of the remaining time, about 2/3 seems to be the vtime stuff, and the other 1/3 the rcu code.

Quoted 7 lines

OK, worth some thought, then.

Quoted 2 lines

I suspect it makes sense to optimize both, though the vtime code may be the easiest :)

Making a crude version that does jiffies (or whatever) instead of fine-grained computations might give good bang for the buck. ;-)

Ingo's idea is to simply have cpu 0 check the current task on all other CPUs, see whether that task is running in system mode, user mode, guest mode, irq mode, etc and update that task's vtime accordingly.

I suspect the runqueue lock is probably enough to do that, and between rcu state and PF_VCPU we probably have enough information to see what mode the task is running in, with just remote memory reads.

Quoted 9 lines · Rik van Riel

Ingo's idea is to simply have cpu 0 check the current task on all other CPUs, see whether that task is running in system mode, user mode, guest mode, irq mode, etc and update that task's vtime accordingly.

I suspect the runqueue lock is probably enough to do that, and between rcu state and PF_VCPU we probably have enough information to see what mode the task is running in, with just remote memory reads.

Note that we could significantly reduce the overhead of vtime accounting by only accumulate utime/stime on per cpu buffers and actually account it on context switch or task_cputime() calls. That way we remove the overhead of the account_user/system_time() functions and the vtime locks.

But doing the accounting from CPU 0 by just accounting 1 tick to the context we remotely observe would certainly reduce the local accounting overhead to the strict minimum. And I think we shouldn't even lock rq for that, we can live with some lack of precision.

Now we must expect quite some overhead on CPU 0. Perhaps it should be an option as I'm not sure every full dynticks usecases want that.

However, currently the RCU code seems to use a much more complex counting scheme, with a different increment for kernel/task use, and irq use.

This counter seems to be modeled on the task preempt_counter, where we do care about whether we are in task context, irq context, or softirq context.

On the other hand, the RCU code only seems to care about whether or not a CPU is in an extended quiescent state, or is potentially in an RCU critical section.

Paul, what is the reason for RCU using a complex counter, instead of a simple increment for each potential kernel/RCU entry, like rcu_read_lock() does with CONFIG_PREEMPT_RCU enabled?

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

Quoted 12 lines · Rik van Riel

However, currently the RCU code seems to use a much more complex counting scheme, with a different increment for kernel/task use, and irq use.

This counter seems to be modeled on the task preempt_counter, where we do care about whether we are in task context, irq context, or softirq context.

On the other hand, the RCU code only seems to care about whether or not a CPU is in an extended quiescent state, or is potentially in an RCU critical section.

Quoted 4 lines

Paul, what is the reason for RCU using a complex counter, instead of a simple increment for each potential kernel/RCU entry, like rcu_read_lock() does with CONFIG_PREEMPT_RCU enabled?

Looking at the code for a while more, I have not found any reason why the rcu dynticks counter is so complex.

The rdtp->dynticks atomic seems to be used as a serial number. Odd means the cpu is in an rcu quiescent state, even means it is not.

This test is used to verify whether or not a CPU is in rcu quiescent state. Presumably the atomic_add_return is used to add a memory barrier.

	atomic_add_return(0, &rdtp->dynticks) & 0x1)

Quoted 3 lines

In fact, would we be able to simply use tsk->rcu_read_lock_nesting as an indicator of whether or not we should bother waiting on that task or CPU when doing synchronize_rcu?

We seem to have two variants of __rcu_read_lock().

One increments current->rcu_read_lock_nesting, the other calls preempt_disable().

In case of the non-preemptible RCU, we could easily also increase current->rcu_read_lock_nesting at the same time we increase the preempt counter, and use that as the indicator to test whether the cpu is in an extended rcu quiescent state. That way there would be no extra overhead at syscall entry or exit at all. The trick would be getting the preempt count and the rcu read lock nesting count in the same cache line for each task.

In case of the preemptible RCU scheme, we would have to examine the per-task state (under the runqueue lock) to get the current task info of all CPUs, and in addition wait for the blkd_tasks list to empty out when doing a synchronize_rcu().

That does not appear to require special per-cpu counters; examining the per-cpu rdp and the lists inside it, with the rnp->lock held if doing any list manipulation, looks like it would be enough.

However, the current code is a lot more complicated than that. Am I overlooking something obvious, Paul? Maybe something non-obvious? :)

Quoted 8 lines · Rik van Riel

In case of the non-preemptible RCU, we could easily also increase current->rcu_read_lock_nesting at the same time we increase the preempt counter, and use that as the indicator to test whether the cpu is in an extended rcu quiescent state. That way there would be no extra overhead at syscall entry or exit at all. The trick would be getting the preempt count and the rcu read lock nesting count in the same cache line for each task.

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

Quoted 6 lines

In case of the preemptible RCU scheme, we would have to examine the per-task state (under the runqueue lock) to get the current task info of all CPUs, and in addition wait for the blkd_tasks list to empty out when doing a synchronize_rcu().

Quoted 8 lines

That does not appear to require special per-cpu counters; examining the per-cpu rdp and the lists inside it, with the rnp->lock held if doing any list manipulation, looks like it would be enough.

However, the current code is a lot more complicated than that. Am I overlooking something obvious, Paul? Maybe something non-obvious? :)

Ummm... The need to maintain memory ordering when sampling task state from remote CPUs?

Or am I completely confused about what you are suggesting?

That said, are you chasing a real system-visible performance issue that you tracked to RCU's dyntick-idle system?

Quoted 11 lines · Paul E. McKenney

Quoted 8 lines · Rik van Riel

In case of the non-preemptible RCU, we could easily also increase current->rcu_read_lock_nesting at the same time we increase the preempt counter, and use that as the indicator to test whether the cpu is in an extended rcu quiescent state. That way there would be no extra overhead at syscall entry or exit at all. The trick would be getting the preempt count and the rcu read lock nesting count in the same cache line for each task.

Quoted 5 lines

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

CONFIG_PREEMPT_RCU seems to be independent of CONFIG_PREEMPT. Not sure why, but they are :)

Quoted 20 lines

Quoted 6 lines

In case of the preemptible RCU scheme, we would have to examine the per-task state (under the runqueue lock) to get the current task info of all CPUs, and in addition wait for the blkd_tasks list to empty out when doing a synchronize_rcu().

Quoted 8 lines

That does not appear to require special per-cpu counters; examining the per-cpu rdp and the lists inside it, with the rnp->lock held if doing any list manipulation, looks like it would be enough.

However, the current code is a lot more complicated than that. Am I overlooking something obvious, Paul? Maybe something non-obvious? :)

Ummm... The need to maintain memory ordering when sampling task state from remote CPUs?

Or am I completely confused about what you are suggesting?

Quoted 2 lines

That said, are you chasing a real system-visible performance issue that you tracked to RCU's dyntick-idle system?

The goal is to reduce the syscall overhead of nohz_full.

Part of the overhead is in the vtime updates, part of it is in the way RCU extended quiescent state is tracked.

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

Quoted 5 lines · Paul E. McKenney

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

We unconditionally have the preempt_count, its just not used much for PREEMPT_COUNT=n kernels.

Quoted 7 lines · Peter Zijlstra

Quoted 5 lines · Paul E. McKenney

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

Quoted 2 lines

We unconditionally have the preempt_count, its just not used much for PREEMPT_COUNT=n kernels.

We have the field, you mean? I might be missing something, but it still appears to me thta preempt_disable() does nothing for PREEMPT=n kernels. So what am I missing?

Quoted 11 lines · Paul E. McKenney

Quoted 9 lines · Peter Zijlstra

Quoted 5 lines · Paul E. McKenney

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

We unconditionally have the preempt_count, its just not used much for PREEMPT_COUNT=n kernels.

Quoted 3 lines

We have the field, you mean? I might be missing something, but it still appears to me thta preempt_disable() does nothing for PREEMPT=n kernels. So what am I missing?

There's another layer of accessors that can in fact manipulate the preempt_count even for !PREEMPT_COUNT kernels. They are currently used by things like pagefault_disable().

Quoted 12 lines · Peter Zijlstra

Quoted 11 lines · Paul E. McKenney

Quoted 9 lines · Peter Zijlstra

Quoted 5 lines · Paul E. McKenney

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

We unconditionally have the preempt_count, its just not used much for PREEMPT_COUNT=n kernels.

Quoted 7 lines

Quoted 3 lines

We have the field, you mean? I might be missing something, but it still appears to me thta preempt_disable() does nothing for PREEMPT=n kernels. So what am I missing?

There's another layer of accessors that can in fact manipulate the preempt_count even for !PREEMPT_COUNT kernels. They are currently used by things like pagefault_disable().

OK, fair enough.

I am going to focus first on getting rid of (or at least greatly reducing) RCU's interrupt disabling on the user-kernel entry/exit paths, since that seems to be the biggest cost.

Quoted 21 lines · Paul E. McKenney

Quoted 12 lines · Peter Zijlstra

Quoted 11 lines · Paul E. McKenney

Quoted 9 lines · Peter Zijlstra

Quoted 5 lines · Paul E. McKenney

But in non-preemptible RCU, we have PREEMPT=n, so there is no preempt counter in production kernels. Even if there was, we have to sample this on other CPUs, so the overhead of preempt_disable() and preempt_enable() would be where kernel entry/exit is, so I expect that this would be a net loss in overall performance.

We unconditionally have the preempt_count, its just not used much for PREEMPT_COUNT=n kernels.

Quoted 7 lines

Quoted 3 lines

We have the field, you mean? I might be missing something, but it still appears to me thta preempt_disable() does nothing for PREEMPT=n kernels. So what am I missing?

There's another layer of accessors that can in fact manipulate the preempt_count even for !PREEMPT_COUNT kernels. They are currently used by things like pagefault_disable().

Quoted 5 lines

OK, fair enough.

I am going to focus first on getting rid of (or at least greatly reducing) RCU's interrupt disabling on the user-kernel entry/exit paths, since that seems to be the biggest cost.

Interrupts are already disabled on kernel-user and kernel-guest switches. Paolo and I have patches to move a bunch of the calls to user_enter, user_exit, guest_enter, and guest_exit to places where interrupts are already disabled, so we do not need to disable them again.

With those in place, the vtime calculations are the largest CPU user. I am working on those.

increase current->rcu_read_lock_nesting at the same time we increase the preempt counter, and use that as the indicator to test whether the cpu is in an extended rcu quiescent state. That way there would be no extra overhead at syscall entry or exit at all. The trick would be getting the preempt count and the rcu read lock nesting count in the same cache line for each task.

On Mon, May 04, 2015 at 03:00:44PM -0400, Rik van Riel wrote:
In case of the non-preemptible RCU, we could easily also

Quoted 7 lines

increase current->rcu_read_lock_nesting at the same time we increase the preempt counter, and use that as the indicator to test whether the cpu is in an extended rcu quiescent state. That way there would be no extra overhead at syscall entry or exit at all. The trick would be getting the preempt count and the rcu read lock nesting count in the same cache line for each task.

Can't do that. Remember, on x86 we have per-cpu preempt count, and your rcu_read_lock_nesting is per task.

Quoted 10 lines · Peter Zijlstra

On Mon, May 04, 2015 at 03:00:44PM -0400, Rik van Riel wrote:
In case of the non-preemptible RCU, we could easily also

Quoted 7 lines

increase current->rcu_read_lock_nesting at the same time we increase the preempt counter, and use that as the indicator to test whether the cpu is in an extended rcu quiescent state. That way there would be no extra overhead at syscall entry or exit at all. The trick would be getting the preempt count and the rcu read lock nesting count in the same cache line for each task.

Quoted 2 lines

Can't do that. Remember, on x86 we have per-cpu preempt count, and your rcu_read_lock_nesting is per task.

Hmm, I suppose you could do the rcu_read_lock_nesting thing in a per-cpu counter too and transfer that into the task_struct on context switch.

If you manage to put both sides of that in the same cache things should not add significant overhead.

You'd have to move the rcu_read_lock_nesting into the thread_info, which would be painful as you'd have to go touch all archs etc..

Quoted 13 lines · Ingo Molnar

Quoted 7 lines · Rik van Riel

Quoted 5 lines

I can understand people running hard-RT workloads not wanting to see the overhead of a timer tick or a scheduler tick with variable (and occasionally heavy) work done in IRQ context, but the jitter caused by a single trivial IPI with constant work should be very, very low and constant.

Not if the realtime workload is running inside a KVM guest.

I don't buy this:

Quoted 8 lines

Quoted 2 lines

At that point an IPI, either on the host or in the guest, involves a full VMEXIT & VMENTER cycle.

So a full VMEXIT/VMENTER costs how much, 2000 cycles? That's around 1 usec on recent hardware, and I bet it will get better with time.

I'm not aware of any hard-RT workload that cannot take 1 usec latencies.

Now think about doing this kind of IPI from inside a guest, to another VCPU on the same guest.

Now you are looking at VMEXIT/VMENTER on the first VCPU, plus the cost of the IPI on the host, plus the cost of the emulation layer, plus VMEXIT/VMENTER on the second VCPU to trigger the IPI work, and possibly a second VMEXIT/VMENTER for IPI completion.

I suspect it would be better to do RCU callback offload in some other way.

Quoted 2 lines

2. To suppress the timing tick, we need to get some timing for, um, the scheduler? I wasn't really sure about this one.

So we have variable timeslice timers for the scheduler implemented, they are off by default but they worked last someone tried them. See the 'HRTICK' scheduler feature.

And for SCHED_FIFO that timeout can be 'never' - i.e. essentially stopping the scheduler tick. (within reason.)

Also note that this bit in context_tracking_enter():

                        if (state == CONTEXT_USER) {
                                trace_user_enter(0);
                                vtime_user_enter(current);
                        }

is related to precise time measurement of user/kernel execution times, it's not needed by the scheduler at all, it's just exported to tooling. It's not fundamental to the scheduler.

Quoted 8 lines · Ingo Molnar

Also note that this bit in context_tracking_enter():

                        if (state == CONTEXT_USER) {
                                trace_user_enter(0);
                                vtime_user_enter(current);
                        }

Quoted 3 lines

is related to precise time measurement of user/kernel execution times, it's not needed by the scheduler at all, it's just exported to tooling. It's not fundamental to the scheduler.

Any objections to the idea from the other thread to simply keep the time accumulating in buffers in local_clock() units, and only update the task vtime once a second or so?

Quoted 10 lines · Rik van Riel

Quoted 8 lines · Ingo Molnar

Also note that this bit in context_tracking_enter():

                        if (state == CONTEXT_USER) {
                                trace_user_enter(0);
                                vtime_user_enter(current);
                        }

Quoted 7 lines

Quoted 3 lines

is related to precise time measurement of user/kernel execution times, it's not needed by the scheduler at all, it's just exported to tooling. It's not fundamental to the scheduler.

Any objections to the idea from the other thread to simply keep the time accumulating in buffers in local_clock() units, and only update the task vtime once a second or so?

So I really think per syscall overhead is the wrong thing to do for anything that a common distro enables.

I see very little use for such precise, high-freq measurements on normal systems - and abnormal systems could enable it dynamically just like they can enable syscall auditing.

I.e. I don't mind the occasional crazy piece of code, as long as it does not hurt the innocent.

Quoted 28 lines · Ingo Molnar

Quoted 10 lines · Rik van Riel

Quoted 8 lines · Ingo Molnar

Also note that this bit in context_tracking_enter():

                        if (state == CONTEXT_USER) {
                                trace_user_enter(0);
                                vtime_user_enter(current);
                        }

Quoted 7 lines

Quoted 3 lines

is related to precise time measurement of user/kernel execution times, it's not needed by the scheduler at all, it's just exported to tooling. It's not fundamental to the scheduler.

Any objections to the idea from the other thread to simply keep the time accumulating in buffers in local_clock() units, and only update the task vtime once a second or so?

So I really think per syscall overhead is the wrong thing to do for anything that a common distro enables.

I see very little use for such precise, high-freq measurements on normal systems - and abnormal systems could enable it dynamically just like they can enable syscall auditing.

Quoted 2 lines

I.e. I don't mind the occasional crazy piece of code, as long as it does not hurt the innocent.

Then how should/could we keep a rough idea of user / system / guest time when running without a periodic timer tick?

Quoted 29 lines · Rik van Riel

Quoted 28 lines · Ingo Molnar

Quoted 10 lines · Rik van Riel

Quoted 8 lines · Ingo Molnar

Also note that this bit in context_tracking_enter():

                        if (state == CONTEXT_USER) {
                                trace_user_enter(0);
                                vtime_user_enter(current);
                        }

Quoted 7 lines

Quoted 3 lines

is related to precise time measurement of user/kernel execution times, it's not needed by the scheduler at all, it's just exported to tooling. It's not fundamental to the scheduler.

Any objections to the idea from the other thread to simply keep the time accumulating in buffers in local_clock() units, and only update the task vtime once a second or so?

So I really think per syscall overhead is the wrong thing to do for anything that a common distro enables.

I see very little use for such precise, high-freq measurements on normal systems - and abnormal systems could enable it dynamically just like they can enable syscall auditing.

Quoted 5 lines

Quoted 2 lines

I.e. I don't mind the occasional crazy piece of code, as long as it does not hurt the innocent.

Then how should/could we keep a rough idea of user / system / guest time when running without a periodic timer tick?

So I'd split the timer tick into two parts: just the constant-work sampling bit that doesn't do much, and the variable-work part which gets essentially shut off when the timeout is far into the future.

Then we could do IRQ driven sampling without introducing variable amount jitter into hard-RT execution time.

I.e. much of what we do today, except that we could skip variable work such as the scheduler tick or (unforced) RCU processing like the RCU softirq work.

Quoted 3 lines

I.e. much of what we do today, except that we could skip variable work such as the scheduler tick or (unforced) RCU processing like the RCU softirq work.

Any ideas how we could avoid that sampling timer interrupt latency stacking up when dealing with both guest and host?

The last time I asked, the impression I got was that we needed two things:

1. We can't pluck things from the RCU list without knowing whether the CPU is in an RCU read-side critical section, and we can't know that unless we have regular grade periods or we know that the CPU is idle. To make the CPU detectably idle, we need to set a bit somewhere.

2. To suppress the timing tick, we need to get some timing for, um, the scheduler? I wasn't really sure about this one.

Could we reduce the overhead by making the IN_USER vs IN_KERNEL indication be a single bit and, worst case, an rdtsc and maybe a subtraction? We could probably get away with banning full nohz on non-invariant tsc systems.

Quoted 6 lines · Andy Lutomirski

The last time I asked, the impression I got was that we needed two things:

1. We can't pluck things from the RCU list without knowing whether the CPU is in an RCU read-side critical section, and we can't know that unless we have regular grade periods or we know that the CPU is idle. To make the CPU detectably idle, we need to set a bit somewhere.

More than that. We also need a way for another CPU to identify the callbacks they could run for us, without confusing them with new callbacks queued after we transitioned back from USER to KERNEL context.

Quoted 16 lines · Ingo Molnar

Quoted 8 lines

This patch builds on top of these patches by Paolo:
https://lkml.org/lkml/2015/4/28/188
https://lkml.org/lkml/2015/4/29/139

Together with this patch I posted earlier this week, the syscall path on a nohz_full cpu seems to be about 10% faster.
https://lkml.org/lkml/2015/4/24/394

Quoted 7 lines

My test is a simple microbenchmark that calls getpriority() in a loop 10 million times:

run time system time
vanilla 5.49s 2.08s
__acct patch 5.21s 1.92s
both patches 4.88s 1.71s

Quoted 4 lines

Just curious, what are the numbers if you don't have context tracking enabled, i.e. without nohz_full?

I.e. what's the baseline we are talking about?

It's an astounding difference. This is not a kernel without nohz_full, just a CPU without nohz_full running the same kernel I tested with yesterday:

run time system time
vanilla 5.49s 2.08s
__acct patch 5.21s 1.92s
both patches 4.88s 1.71s
CPU w/o nohz 3.12s 1.63s <-- your numbers, mostly

Below are v4.1-rc1-172-g6c3c1eb3c35e + patches measurements.

100M * stat() on isolated cpu

NO_HZ_FULL off        inactive     housekeeper    nohz_full
real    0m14.266s     0m14.367s    0m20.427s      0m27.921s
user    0m1.756s      0m1.553s     0m1.976s       0m10.447s
sys     0m12.508s     0m12.769s    0m18.400s      0m17.464s
(real)  1.000         1.007        1.431          1.957
                                   1.000          1.000

                         real      0m20.423s      0m27.930s  +rik 1,2
                         user      0m2.072s       0m10.450s
                         sys       0m18.304s      0m17.471s
                         vs off    1.431          1.957
                         vs prev   1.000          1.000

                         real      0m20.256s      0m27.803s  +paolo 1,2 (2 missing prototypes)
                         user      0m1.884s       0m10.551s
                         sys       0m18.353s      0m17.242s
                         vs off    1.419          1.948
                         vs prev    .991           .995

                         real      0m19.122s      0m26.946s  +rik 3
                         user      0m1.896s       0m10.292s
                         sys       0m17.198s      0m16.644s
                         vs off    1.340          1.888
                         vs prev   .944            .969

Quoted 17 lines · Mike Galbraith

Below are v4.1-rc1-172-g6c3c1eb3c35e + patches measurements.

100M * stat() on isolated cpu

NO_HZ_FULL off        inactive     housekeeper    nohz_full
real    0m14.266s     0m14.367s    0m20.427s      0m27.921s
user    0m1.756s      0m1.553s     0m1.976s       0m10.447s
sys     0m12.508s     0m12.769s    0m18.400s      0m17.464s
(real)  1.000         1.007        1.431          1.957
                                   1.000          1.000

                         real      0m20.423s      0m27.930s  +rik 1,2
                         user      0m2.072s       0m10.450s
                         sys       0m18.304s      0m17.471s
                         vs off    1.431          1.957
                         vs prev   1.000          1.000

Quoted 11 lines

                         real      0m20.256s      0m27.803s  +paolo 1,2 (2 missing prototypes)
                         user      0m1.884s       0m10.551s
                         sys       0m18.353s      0m17.242s
                         vs off    1.419          1.948
                         vs prev    .991           .995

                         real      0m19.122s      0m26.946s  +rik 3
                         user      0m1.896s       0m10.292s
                         sys       0m17.198s      0m16.644s
                         vs off    1.340          1.888
                         vs prev   .944            .969

I'm convinced.

Time to try the remote sampling of CPU use statistics, and lighten up the RCU overhead of context tracking.

Quoted 12 lines · Rik van Riel

Quoted 9 lines · Mike Galbraith

Below are v4.1-rc1-172-g6c3c1eb3c35e + patches measurements.

100M * stat() on isolated cpu

NO_HZ_FULL off        inactive     housekeeper    nohz_full
real    0m14.266s     0m14.367s    0m20.427s      0m27.921s
user    0m1.756s      0m1.553s     0m1.976s       0m10.447s
sys     0m12.508s     0m12.769s    0m18.400s      0m17.464s
(real)  1.000         1.007        1.431          1.957

Quoted 5 lines

I'm convinced.

Time to try the remote sampling of CPU use statistics, and lighten up the RCU overhead of context tracking.

I don't understand the remote sampling proposal. Isn't the whole point of full nohz to avoid periodically interrupting a busy CPU? If what you have in mind is sending IPIs, then that's just as bad, right?

If, on the other hand, you're just going to remotely sample the in-memory context, that sounds good.

Quoted 2 lines

If, on the other hand, you're just going to remotely sample the in-memory context, that sounds good.

It's the latter.

If you look at /proc/<pid>/{stack,syscall,wchan} and other files, you will see we already have ways to determine, from in memory content, where a program is running at a certain point in time.

In fact, the timer interrupt based accounting does a similar thing. It has a task examine its own in-memory state to figure out what it was doing before the timer interrupt happened.

The kernel side stack pointer is probably enough to tell us whether a task is active in kernel space, on an irq stack, or (maybe) in user space. Not convinced about the latter, we may need to look at the same state the RCU code keeps track of to see what mode a task is in...

I am looking at the code to see what locks we need to grab.

I suspect the runqueue lock may be enough, to ensure that the task struct, and stack do not go away while we are looking at them.

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

Quoted 19 lines · Rik van Riel

Quoted 2 lines

If, on the other hand, you're just going to remotely sample the in-memory context, that sounds good.

It's the latter.

If you look at /proc/<pid>/{stack,syscall,wchan} and other files, you will see we already have ways to determine, from in memory content, where a program is running at a certain point in time.

In fact, the timer interrupt based accounting does a similar thing. It has a task examine its own in-memory state to figure out what it was doing before the timer interrupt happened.

The kernel side stack pointer is probably enough to tell us whether a task is active in kernel space, on an irq stack, or (maybe) in user space. Not convinced about the latter, we may need to look at the same state the RCU code keeps track of to see what mode a task is in...

Quoted 4 lines

I am looking at the code to see what locks we need to grab.

I suspect the runqueue lock may be enough, to ensure that the task struct, and stack do not go away while we are looking at them.

That will be enough, especially if you get to the task reference via rq->curr.

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

We'll need that percpu flag I suspect.

And once we have the flag, we can get rid of the per syscall RCU callback as well, relatively easily: with CMPXCHG (in synchronize_rcu()!) we can reliably sample whether a CPU is in user mode right now, while the syscall entry/exit path does not use any atomics, we can just use a simple MOV.

Once we observe 'user mode', then we have observed quiescent state and synchronize_rcu() can continue. If we've observed kernel mode we can frob the remote task's TIF_ flags to make it go into a quiescent state publishing routine on syscall-return.

The only hard requirement of this scheme from the RCU synchronization POV is that all kernel contexts that may touch RCU state need to flip this flag reliably to 'kernel mode': i.e. all irq handlers, traps, NMIs and all syscall variants need to do this.

But once it's there, it's really neat.

Thanks,

Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 10 lines

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

Quoted 1 line

We'll need that percpu flag I suspect.

Note we have the context tracking state which tells where the current task is: user/system/guest.

Quoted 10 lines · Frederic Weisbecker

Quoted 10 lines

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

Quoted 4 lines

Quoted 1 line

We'll need that percpu flag I suspect.

Note we have the context tracking state which tells where the current task is: user/system/guest.

Yes, but that overhead is what I'm suggesting we get rid of, I thought Rik was trying to find a mechanism that would be independent of that?

Quoted 13 lines · Ingo Molnar

Quoted 10 lines · Frederic Weisbecker

Quoted 10 lines

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

Quoted 7 lines

Quoted 4 lines

Quoted 1 line

We'll need that percpu flag I suspect.

Note we have the context tracking state which tells where the current task is: user/system/guest.

Yes, but that overhead is what I'm suggesting we get rid of, I thought Rik was trying to find a mechanism that would be independent of that?

One thing at a time :)

I am working on the timer sampling stuff, which should be easy to adapt to a different user/system/guest/irq/softirq/... tracking thing, if somebody else comes up with a more efficient way to do that.

Quoted 19 lines · Rik van Riel

Quoted 2 lines

If, on the other hand, you're just going to remotely sample the in-memory context, that sounds good.

It's the latter.

If you look at /proc/<pid>/{stack,syscall,wchan} and other files, you will see we already have ways to determine, from in memory content, where a program is running at a certain point in time.

In fact, the timer interrupt based accounting does a similar thing. It has a task examine its own in-memory state to figure out what it was doing before the timer interrupt happened.

The kernel side stack pointer is probably enough to tell us whether a task is active in kernel space, on an irq stack, or (maybe) in user space. Not convinced about the latter, we may need to look at the same state the RCU code keeps track of to see what mode a task is in...

Quoted 4 lines

I am looking at the code to see what locks we need to grab.

I suspect the runqueue lock may be enough, to ensure that the task struct, and stack do not go away while we are looking at them.

That will be enough, especially if you get to the task reference via rq->curr.

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

We'll need that percpu flag I suspect.

And once we have the flag, we can get rid of the per syscall RCU callback as well, relatively easily: with CMPXCHG (in synchronize_rcu()!) we can reliably sample whether a CPU is in user mode right now, while the syscall entry/exit path does not use any atomics, we can just use a simple MOV.

Once we observe 'user mode', then we have observed quiescent state and synchronize_rcu() can continue. If we've observed kernel mode we can frob the remote task's TIF_ flags to make it go into a quiescent state publishing routine on syscall-return.

The only hard requirement of this scheme from the RCU synchronization POV is that all kernel contexts that may touch RCU state need to flip this flag reliably to 'kernel mode': i.e. all irq handlers, traps, NMIs and all syscall variants need to do this.

But once it's there, it's really neat.

Thanks,

Ingo

Quoted 18 lines

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

We'll need that percpu flag I suspect.

And once we have the flag, we can get rid of the per syscall RCU callback as well, relatively easily: with CMPXCHG (in synchronize_rcu()!) we can reliably sample whether a CPU is in user mode right now, while the syscall entry/exit path does not use any atomics, we can just use a simple MOV.

Quoted 5 lines

Once we observe 'user mode', then we have observed quiescent state and synchronize_rcu() can continue. If we've observed kernel mode we can frob the remote task's TIF_ flags to make it go into a quiescent state publishing routine on syscall-return.

How does that work?

If the exit code writes the per-cpu flag and then checks TIF_whatever, we need a barrier to avoid a race where we end up in user mode without seeing the flag.

I think the right solution is to accept that race and just have the RCU code send an IPI (or check again) if it sees too long of a period elapse in kernel mode.

I think the flag should be a counter, though. That way a workload that makes lots of syscalls will be quickly detected as going through quiescent states even if it's never actually observed in user mode.

Quoted 7 lines

The only hard requirement of this scheme from the RCU synchronization POV is that all kernel contexts that may touch RCU state need to flip this flag reliably to 'kernel mode': i.e. all irq handlers, traps, NMIs and all syscall variants need to do this.

But once it's there, it's really neat.

We already have to do this with the current code. I went through and checked all of the IST entries a couple versions ago.

The TIF_RCU_QS thing is just a fancy way for synchronize_rcu() (being executed on some other CPU not doing RT work) to intelligently wait for the remote (RT work doing) CPU to finish executing kernel code, without polling or so.

Quoted 4 lines · Ingo Molnar

The TIF_RCU_QS thing is just a fancy way for synchronize_rcu() (being executed on some other CPU not doing RT work) to intelligently wait for the remote (RT work doing) CPU to finish executing kernel code, without polling or so.

it's basically a cheap IPI being inserted on the remote CPU.

We need the TIF_RCU_QS callback not just to wait intelligently, but mainly to elapse a grace period, otherwise synchronize_rcu() might not ever make progress: think a SCHED_FIFO task doing some kernel work, synchronize_rcu() stumbling upon it - but the SCHED_FIFO task otherwise never scheduling and never getting any timer irqs either, and thus never entering quiescent state.

(Cc:-ed Paul too, he might be interested in this as well.)

Quoted 24 lines · Andy Lutomirski

Quoted 18 lines

Quoted 3 lines

We cannot take the lock_trace(task) from irq context, and we probably do not need to anyway, since we do not care about a precise stack trace for the task.

So one worry with this and similar approaches of statistically detecting user mode would be the fact that on the way out to user-space we don't really destroy the previous call trace - we just pop off the stack (non-destructively), restore RIPs and are gone.

We'll need that percpu flag I suspect.

And once we have the flag, we can get rid of the per syscall RCU callback as well, relatively easily: with CMPXCHG (in synchronize_rcu()!) we can reliably sample whether a CPU is in user mode right now, while the syscall entry/exit path does not use any atomics, we can just use a simple MOV.

Quoted 5 lines

Once we observe 'user mode', then we have observed quiescent state and synchronize_rcu() can continue. If we've observed kernel mode we can frob the remote task's TIF_ flags to make it go into a quiescent state publishing routine on syscall-return.

Quoted 5 lines

How does that work?

If the exit code writes the per-cpu flag and then checks TIF_whatever, we need a barrier to avoid a race where we end up in user mode without seeing the flag.

No, the TIF_RCU_SYNC flag would be independent of the user-mode flag.

Also, the user-mode flag would be changed from the 'kernel-mode' value to the 'user-mode' value after we do the regular TIF checks - just before we hit user-space.

The TIF_RCU_QS thing is just a fancy way for synchronize_rcu() (being executed on some other CPU not doing RT work) to intelligently wait for the remote (RT work doing) CPU to finish executing kernel code, without polling or so.

And yes, the TIF_RCU_QS handler on the remote CPU would have to execute an SMP barrier, before it allows an RCU quiescent state to pass. Note that the regular RCU code for quiescent state publishing already has that barrier, typically something like:

        this_cpu_inc(rcu_qs_ctr);

That in itself is enough for synchronize_rcu(), it could do a small timing loop with short sleeps, until it waits for rcu_qs_ctr to increase.

I think one or both of us is missing something or we're just talking about different things.

If the nohz/RT cpu is about to enter user mode and stay there for a long time, it does:

  this_cpu_inc(rcu_qs_ctr);

or whatever. Maybe we add:

  this_cpu_set(rcu_state) = IN_USER;

or however it's spelled.

The remote CPU wants to check our state. If this happens just before the IN_USER write or rcu_qs_ctr increment becomes visible, then it'll think we're in kernel mode. Now it either has to poll (which is fine) or try to get us to tell the RCU core when we become quiescent by setting TIF_RCU_THINGY.

The problem is that I don't see how TIF_RCU_THINGY can work reliably. If the remote CPU sets it, it'll be too late and we'll still enter user mode without seeing it. If it's just an optimization, though, then it should be fine.

I still feel like this is all overengineered. Shouldn't rcu_qs_ctr be enough for all of the above?

Quoted 2 lines · Andy Lutomirski

I think one or both of us is missing something or we're just talking about different things.

That's very much possible!

I think part of the problem is that I called the 'remote CPU' the RT CPU, while you seem to be calling it the CPU that does the synchronize_rcu().

So lets start again, with calling the synchronize_rcu() the 'remote CPU', and the one doing the RT workload the 'RT CPU':

Quoted 9 lines

If the nohz/RT cpu is about to enter user mode and stay there for a long time, it does:

  this_cpu_inc(rcu_qs_ctr);

or whatever. Maybe we add:

  this_cpu_set(rcu_state) = IN_USER;

Quoted 7 lines

or however it's spelled.

The remote CPU wants to check our state. If this happens just before the IN_USER write or rcu_qs_ctr increment becomes visible, then it'll think we're in kernel mode. Now it either has to poll (which is fine) or try to get us to tell the RCU core when we become quiescent by setting TIF_RCU_THINGY.

So do you mean:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_inc(rcu_qs_ctr);
   this_cpu_set(rcu_state) = IN_USER;

?

So in your proposal we'd have an INC and two MOVs. I think we can make it just two simple stores into a byte flag, one on entry and one on exit:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_set(rcu_state) = IN_USER;

plus the rare but magic TIF_RCU_THINGY that tells a waiting synchronize_rcu() about the next quiescent state.

Quoted 4 lines

The problem is that I don't see how TIF_RCU_THINGY can work reliably. If the remote CPU sets it, it'll be too late and we'll still enter user mode without seeing it. If it's just an optimization, though, then it should be fine.

Well, after setting it, the remote CPU has to re-check whether the RT CPU has entered user-mode - before it goes to wait.

Quoted 9 lines

So do you mean:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_inc(rcu_qs_ctr);
   this_cpu_set(rcu_state) = IN_USER;

?

Quoted 8 lines

So in your proposal we'd have an INC and two MOVs. I think we can make it just two simple stores into a byte flag, one on entry and one on exit:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_set(rcu_state) = IN_USER;

I was thinking that either a counter or a state flag could make sense. Doing both would be pointless. The counter could use the low bits to indicate the state. The benefit of the counter would be that the RCU-waiting CPU could observe that the counter has incremented and that therefore a grace period has elapsed. Getting it right would require lots of care.

Quoted 7 lines

Quoted 4 lines

The problem is that I don't see how TIF_RCU_THINGY can work reliably. If the remote CPU sets it, it'll be too late and we'll still enter user mode without seeing it. If it's just an optimization, though, then it should be fine.

Well, after setting it, the remote CPU has to re-check whether the RT CPU has entered user-mode - before it goes to wait.

How?

Suppose the exit path looked like:

this_cpu_write(rcu_state, IN_USER);

if (ti->flags & _TIF_RCU_NOTIFY) {
    if (test_and_clear_bit(TIF_RCU_NOTIFY, &ti->flags))
        slow_notify_rcu_that_we_are_exiting();
}

iret or sysret;

The RCU-waiting CPU sees that rcu_state == IN_KERNEL and sets _TIF_RCU_NOTIFY. This could happen arbitrarily late before IRET because stores can be delayed. (It could even happen after sysret, IIRC, but IRET is serializing.)

If we put an mfence after this_cpu_set or did an unconditional test_and_clear_bit on ti->flags then this problem goes away, but that would probably be slower than we'd like.

Quoted 18 lines · Andy Lutomirski

Quoted 9 lines

So do you mean:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_inc(rcu_qs_ctr);
   this_cpu_set(rcu_state) = IN_USER;

?

Quoted 8 lines

So in your proposal we'd have an INC and two MOVs. I think we can make it just two simple stores into a byte flag, one on entry and one on exit:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_set(rcu_state) = IN_USER;

Quoted 6 lines

I was thinking that either a counter or a state flag could make sense. Doing both would be pointless. The counter could use the low bits to indicate the state. The benefit of the counter would be that the RCU-waiting CPU could observe that the counter has incremented and that therefore a grace period has elapsed. Getting it right would require lots of care.

So if you mean:

       <syscall entry>
       ...
       this_cpu_inc(rcu_qs_ctr);
       <syscall exit>

I don't see how this would work reliably: how do you handle the case of a SCHED_FIFO task never returning from user-space (common technique in RT apps)? synchronize_rcu() would block indefinitely as it would never see rcu_qs_ctr increase.

We have to be able to observe user-mode anyway, for system-time statistics purposes, and that flag could IMHO also drive the RCU GC machinery.

Quoted 13 lines

Quoted 8 lines

Quoted 5 lines

The problem is that I don't see how TIF_RCU_THINGY can work reliably. If the remote CPU sets it, it'll be too late and we'll still enter user mode without seeing it. If it's just an optimization, though, then it should be fine.

Well, after setting it, the remote CPU has to re-check whether the RT CPU has entered user-mode - before it goes to wait.

How?

Suppose the exit path looked like:

Quoted 8 lines

this_cpu_write(rcu_state, IN_USER);

if (ti->flags & _TIF_RCU_NOTIFY) {
    if (test_and_clear_bit(TIF_RCU_NOTIFY, &ti->flags))
        slow_notify_rcu_that_we_are_exiting();
}

iret or sysret;

No, it would look like this:

   this_cpu_write(rcu_state, IN_USER);
   iret or sysret;

I.e. IN_USER is set well after all notifications are checked. No kernel execution happens afterwards. (No extra checks added - the regular return-to-user-work checks would handle TIF_RCU_NOTIFY.)

( Same goes for idle: we just mark it IN_IDLE and move it back to
IN_KERNEL after the idling ends. )

Quoted 4 lines

The RCU-waiting CPU sees that rcu_state == IN_KERNEL and sets _TIF_RCU_NOTIFY. This could happen arbitrarily late before IRET because stores can be delayed. (It could even happen after sysret, IIRC, but IRET is serializing.)

All it has to do in the synchronize_rcu() slowpath is something like:

        if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL) {
                smp_mb__before_atomic();
                set_tsk_thread_flag(remote_task, TIF_RCU_NOTIFY);
                smp_rmb();
                if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL)

                        ... go wait ...
        }
        /* Cool, we observed quiescent state: */

The cost of the trivial barrier is nothing compared to the 'go wait' cost which we will pay in 99.9% of the cases!

Quoted 3 lines

If we put an mfence after this_cpu_set or did an unconditional test_and_clear_bit on ti->flags then this problem goes away, but that would probably be slower than we'd like.

We are talking about a dozen cycles, while a typical synchronize_rcu() will wait millions (sometimes billions) of cycles. There's absolutely zero performance concern here and it's all CPU local in any case.

In fact a user-mode/kernel-mode flag speeds up naive implementations of synchronize_rcu(): because it's able to observe extended quiescent state immediately, without having to wait for a counter to increase (which was always the classic way to observe grace periods).

If all CPUs are in user mode or are idle (which is rather common!) then synchronize_rcu() could return almost immediately - while previously it had to wait for scheduling or periodic timer irqs to trigger on all CPUs - adding many millisecs of delay even in the best of cases.

Quoted 36 lines · Ingo Molnar

Quoted 18 lines · Andy Lutomirski

Quoted 9 lines

So do you mean:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_inc(rcu_qs_ctr);
   this_cpu_set(rcu_state) = IN_USER;

?

Quoted 8 lines

So in your proposal we'd have an INC and two MOVs. I think we can make it just two simple stores into a byte flag, one on entry and one on exit:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_set(rcu_state) = IN_USER;

Quoted 6 lines

I was thinking that either a counter or a state flag could make sense. Doing both would be pointless. The counter could use the low bits to indicate the state. The benefit of the counter would be that the RCU-waiting CPU could observe that the counter has incremented and that therefore a grace period has elapsed. Getting it right would require lots of care.

So if you mean:

       <syscall entry>
       ...
       this_cpu_inc(rcu_qs_ctr);
       <syscall exit>

Quoted 8 lines

I don't see how this would work reliably: how do you handle the case of a SCHED_FIFO task never returning from user-space (common technique in RT apps)? synchronize_rcu() would block indefinitely as it would never see rcu_qs_ctr increase.

We have to be able to observe user-mode anyway, for system-time statistics purposes, and that flag could IMHO also drive the RCU GC machinery.

The counter would have to be fancier than that to work. We could say that an even value means user mode, for example. IOW the high bits of the counter would count transitions to quiescent and the low bits would indicate the state.

Actually, I'd count backwards. We could use an andl instruction to go to user mode and a decl to go to kernel mode.

Quoted 7 lines

Quoted 4 lines

The RCU-waiting CPU sees that rcu_state == IN_KERNEL and sets _TIF_RCU_NOTIFY. This could happen arbitrarily late before IRET because stores can be delayed. (It could even happen after sysret, IIRC, but IRET is serializing.)

All it has to do in the synchronize_rcu() slowpath is something like:

I don't think this works. Suppose rt_cpu starts in kernel mode. Then it checks ti flags.

Quoted 1 line

Quoted 5 lines

        if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL) {
                smp_mb__before_atomic();
                set_tsk_thread_flag(remote_task, TIF_RCU_NOTIFY);
                smp_rmb();
                if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL)

Now it sets rcu_state and exits to user mode. It never notices TIF_RCU_NOTIFY.

[...] We could fix this by sending an IPI to kick it.

Quoted 4 lines

We are talking about a dozen cycles, while a typical synchronize_rcu() will wait millions (sometimes billions) of cycles. There's absolutely zero performance concern here and it's all CPU local in any case.

The barrier would affect all syscalls, though. [...]

Quoted 5 lines

        if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL) {
                smp_mb__before_atomic();
                set_tsk_thread_flag(remote_task, TIF_RCU_NOTIFY);
                smp_rmb();
                if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL)

Quoted 46 lines · Andy Lutomirski

Quoted 36 lines · Ingo Molnar

Quoted 18 lines · Andy Lutomirski

Quoted 9 lines

So do you mean:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_inc(rcu_qs_ctr);
   this_cpu_set(rcu_state) = IN_USER;

?

Quoted 8 lines

So in your proposal we'd have an INC and two MOVs. I think we can make it just two simple stores into a byte flag, one on entry and one on exit:

   this_cpu_set(rcu_state) = IN_KERNEL;
   ...
   this_cpu_set(rcu_state) = IN_USER;

Quoted 6 lines

I was thinking that either a counter or a state flag could make sense. Doing both would be pointless. The counter could use the low bits to indicate the state. The benefit of the counter would be that the RCU-waiting CPU could observe that the counter has incremented and that therefore a grace period has elapsed. Getting it right would require lots of care.

So if you mean:

       <syscall entry>
       ...
       this_cpu_inc(rcu_qs_ctr);
       <syscall exit>

Quoted 8 lines

I don't see how this would work reliably: how do you handle the case of a SCHED_FIFO task never returning from user-space (common technique in RT apps)? synchronize_rcu() would block indefinitely as it would never see rcu_qs_ctr increase.

We have to be able to observe user-mode anyway, for system-time statistics purposes, and that flag could IMHO also drive the RCU GC machinery.

Quoted 7 lines

The counter would have to be fancier than that to work. We could say that an even value means user mode, for example. IOW the high bits of the counter would count transitions to quiescent and the low bits would indicate the state.

Actually, I'd count backwards. We could use an andl instruction to go to user mode and a decl to go to kernel mode.

at which point it's not really a monotonic quiescent state counter - which your naming suggested before.

Also it would have to be done both at entry and at exit.

But yes, if you replace a state flag with a recursive state flag that is INC/DEC maintained that would work as well. That's not a counter though.

Quoted 13 lines

Quoted 8 lines

Quoted 5 lines

The RCU-waiting CPU sees that rcu_state == IN_KERNEL and sets _TIF_RCU_NOTIFY. This could happen arbitrarily late before IRET because stores can be delayed. (It could even happen after sysret, IIRC, but IRET is serializing.)

All it has to do in the synchronize_rcu() slowpath is something like:

I don't think this works. Suppose rt_cpu starts in kernel mode. Then it checks ti flags.

Quoted 1 line

Quoted 8 lines

Quoted 5 lines

        if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL) {
                smp_mb__before_atomic();
                set_tsk_thread_flag(remote_task, TIF_RCU_NOTIFY);
                smp_rmb();
                if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL)

Now it sets rcu_state and exits to user mode. It never notices TIF_RCU_NOTIFY.

Indeed, you are right, that's racy.

Quoted 1 line

[...] We could fix this by sending an IPI to kick it.

With an IPI we won't need any flags or counters on the RT CPU - it's the IPI we are trying to avoid.

So how about the following way to fix the race: simply do a poll loop with a fixed timeout sleep: like it would do anyway if synchronize_rcu() was waiting for the timer irq to end the grace period on the RT-CPU.

The TIF flag would cause an RCU grace period to lapse, no need to wake up the synchronize_rcu() side: it will notice the (regular) increased RCU counter.

Quoted 5 lines

Quoted 4 lines

We are talking about a dozen cycles, while a typical synchronize_rcu() will wait millions (sometimes billions) of cycles. There's absolutely zero performance concern here and it's all CPU local in any case.

Quoted 1 line

The barrier would affect all syscalls, though. [...]

What barrier? I never suggested any barrier in the syscall fast path, this bit:

Quoted 6 lines

Quoted 6 lines

        if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL) {
                smp_mb__before_atomic();
                set_tsk_thread_flag(remote_task, TIF_RCU_NOTIFY);
                smp_rmb();
                if (per_cpu(rcu_state, rt_cpu) == IN_KERNEL)

runs inside synchronize_rcu() or so.

But none of that is needed if we do:

- simple IN_KERNEL/IN_USER/[/IN_IDLE] flag updated at context entry/exit time, straight in the assembly

- TIF_RCU_QS to trigger a TIF slowpath on the RT-CPU that does nothing but: this_cpu_inc(rcu_qs_ctr).

- synchronize_rcu() injects TIF_RCU_QS into the RT-CPU and then does a timeout-poll-loop with jiffies granular timeouts, simulating a timer IRQ in essence. It will either observe IN_USER or will see the regular RCU qs counter increase.

this should be race free.

Alternatively we can even get rid of the TIF flag by merging the percpu counter with the percpu state. Quiescent states are recorded via a counter shifted by two bits:

        rcu_qs_ctr += 4;

while user/kernel/idle mode is recorded in the lower 2 bits.

So on entering the kernel we'd do:

        rcu_qs_ctr += 4+1; /* Register QS and set bit 0 to IN_KERNEL */

on returning to user-space we'd do:

        rcu_qs_ctr += 4-1; /* We have bit 0 set already, clear it and register a QS */

on going idle we'd do:

        rcu_qs_ctr += 4+2; /* Register QS, set bit 1 */

on return from idle we'd do:

        rcu_qs_ctr += 4-2+1; /* Register QS, clear bit 1, set bit 0 */

etc. On all boundary transitions we can use a constant ADD on a suitable percpu variable.

Quoted 6 lines

on return from idle we'd do:

        rcu_qs_ctr += 4-2+1; /* Register QS, clear bit 1, set bit 0 */

etc. On all boundary transitions we can use a constant ADD on a suitable percpu variable.

Sounds good to me, except that we need to be careful to distinguish between non-syscall entries from quiescent states
and non-syscall entries from quiescent states.

[...] We could save the old state (as the current exception_enter code does) or we could allocate enough low bits for the state that the problem goes away.

I don't think the TIF_RCU_QS variant is worthwhile -- merging the counter and state is probably both easier and faster.