Alternative RCU implementation
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 10 lines · Jim Houston
The attached patch against linux-2.6.8.1-mm4 is an experimental implementation of RCU.
It uses an active synchronization between the
rcu_read_lock(),rcu_read_unlock(), and the code which starts a new RCU batch. A RCU batch can be started at an arbitrary point, and it will complete without waiting for a timer driven poll. This should help avoid large batches and their adverse cache and latency effects.
Quoted 7 lines
I did this work because Concurrent encourages its customers to isolate critical realtime processes to their own cpu and shield them from other processes and interrupts. This includes disabling the local timer interrupt. The current RCU code relies on the local timer to recognize quiescent states. If it is disabled on any cpu, RCU callbacks are never called and the system bleeds memory and hangs on calls to
synchronize_kernel().
Are these critical realtime processes user-mode only, or do they also execute kernel code? If they are user-mode only, a much more straightforward approach might be to have RCU pretend that they do not exist.
This approach would have the added benefit of keeping rcu_read_unlock() atomic-instruction free. In some cases, the overhead of the atomic exchange would overwhelm that of the read-side RCU critical section.
Taking this further, if the realtime CPUs are not allowed to execute in the kernel at all, you can avoid overhead from smp_call_function() and the like -- and avoid confusing those parts of the kernel that expect to be able to send IPIs and the like to the realtime CPU (or do you leave IPIs enabled on the realtime CPU?).
Thanx, Paul
[ . . . ]
Quoted 28 lines · Paul E. McKenney
Quoted 10 lines · Jim Houston
The attached patch against linux-2.6.8.1-mm4 is an experimental implementation of RCU.
It uses an active synchronization between the
rcu_read_lock(),rcu_read_unlock(), and the code which starts a new RCU batch. A RCU batch can be started at an arbitrary point, and it will complete without waiting for a timer driven poll. This should help avoid large batches and their adverse cache and latency effects.Quoted 7 lines
I did this work because Concurrent encourages its customers to isolate critical realtime processes to their own cpu and shield them from other processes and interrupts. This includes disabling the local timer interrupt. The current RCU code relies on the local timer to recognize quiescent states. If it is disabled on any cpu, RCU callbacks are never called and the system bleeds memory and hangs on calls to
synchronize_kernel().Are these critical realtime processes user-mode only, or do they also execute kernel code? If they are user-mode only, a much more straightforward approach might be to have RCU pretend that they do not exist.
This approach would have the added benefit of keeping
rcu_read_unlock()atomic-instruction free. In some cases, the overhead of the atomic exchange would overwhelm that of the read-side RCU critical section.
Quoted 7 lines
Taking this further, if the realtime CPUs are not allowed to execute in the kernel at all, you can avoid overhead from
smp_call_function()and the like -- and avoid confusing those parts of the kernel that expect to be able to send IPIs and the like to the realtime CPU (or do you leave IPIs enabled on the realtime CPU?).Thanx, Paul
Hi Paul,
Our customers applications vary but, in general, the realtime processes will do the usual system calls to synchronize with other processes and do I/O.
I considered tracking the user<->kernel mode transitions extending the idea of the nohz_cpu_mask. I gave up on this idea mostly because it required hooking into assembly code. Just extending the idea of this bitmap has its own scaling issues. We may have several cpus running realtime processes. The obvious answer is to keep the information in a per-cpu variable and pay the price of polling this from another cpu.
I know that I'm questioning one of your design goals for RCU by adding overhead to the read-side. I have read everything I could find on RCU. My belief is that the cost of the xchg() instruction is small compared to the cache benifit of freeing memory more quickly. I think it's more interesting to look at the impact of the xchg() at the level of an entire system call. Adding 30 nanoseconds to a open/close path that tasks 3 microseconds seems reasonable. It is hard to measure the benefit of reusing the a dcache entry more quickly.
I would be interested in suggestions for testing. I would be very interested to hear how my patch does on a large machine.
I'm also trying to figure out if I need the call_rcu_bh() changes. Since my patch will recognize a grace periods as soon as any pending read-side critical sections complete, I suspect that I don't need this change.
Jim Houston - Concurrent Computer
Quoted 20 lines · Jim Houston
Quoted 9 lines · Paul E. McKenney
Are these critical realtime processes user-mode only, or do they also execute kernel code? If they are user-mode only, a much more straightforward approach might be to have RCU pretend that they do not exist.
This approach would have the added benefit of keeping
rcu_read_unlock()atomic-instruction free. In some cases, the overhead of the atomic exchange would overwhelm that of the read-side RCU critical section.Quoted 5 lines
Taking this further, if the realtime CPUs are not allowed to execute in the kernel at all, you can avoid overhead from
smp_call_function()and the like -- and avoid confusing those parts of the kernel that expect to be able to send IPIs and the like to the realtime CPU (or do you leave IPIs enabled on the realtime CPU?).Our customers applications vary but, in general, the realtime processes will do the usual system calls to synchronize with other processes and do I/O.
Quoted 6 lines
I considered tracking the user<->kernel mode transitions extending the idea of the
nohz_cpu_mask. I gave up on this idea mostly because it required hooking into assembly code. Just extending the idea of this bitmap has its own scaling issues. We may have several cpus running realtime processes. The obvious answer is to keep the information in a per-cpu variable and pay the price of polling this from another cpu.
Tracking user<->kernel transitions and putting smarts in scheduler about RCU is the right way to go IMO.
Anything that poll other cpus and has read-side overheads will likely not be scalable. I think that is not the right way to go about solving the issue of dependency on local timer interrupt. It is a worthy goal and we need to do this anyway, but we need to do it right without hurting the current advantages as much as possible.
Quoted 11 lines
I know that I'm questioning one of your design goals for RCU by adding overhead to the read-side. I have read everything I could find on RCU. My belief is that the cost of the
xchg()instruction is small compared to the cache benifit of freeing memory more quickly. I think it's more interesting to look at the impact of thexchg()at the level of an entire system call. Adding 30 nanoseconds to a open/close path that tasks 3 microseconds seems reasonable. It is hard to measure the benefit of reusing the a dcache entry more quickly.I would be interested in suggestions for testing. I would be very interested to hear how my patch does on a large machine.
I will get you some numbers on a large machine. But I remain opposed to this approach. I believe it can be done without the read-side overheads.
Quoted 4 lines
I'm also trying to figure out if I need the
call_rcu_bh()changes. Since my patch will recognize a grace periods as soon as any pending read-side critical sections complete, I suspect that I don't need this change.
Except that under a softirq flood, a reader in a different read-side critical section may get delayed a lot holding up RCU. Let me know if I am missing something here.
Thanks
Dipankar
Quoted 8 lines · Dipankar Sarma
Quoted 4 lines
I'm also trying to figure out if I need the
call_rcu_bh()changes. Since my patch will recognize a grace periods as soon as any pending read-side critical sections complete, I suspect that I don't need this change.Except that under a softirq flood, a reader in a different read-side critical section may get delayed a lot holding up RCU. Let me know if I am missing something here.
Hi Dipankar,
O.k. That makes sense. So the rcu_read_lock_bh(), rcu_read_unlock_bh() and call_rcu_bh() would be the preferred interface. Are there cases where they can't be used? How do you decide where to use the _bh flavor?
I see that local_bh_enable() WARNS if interrupts are disabled. Is that the issue? Are rcu_read_lock()/rcu_read_unlock() ever called from code which disables interrupts?
Jim Houston - Concurrent Computer Corp.
Quoted 11 lines · Jim Houston
Quoted 8 lines · Dipankar Sarma
Quoted 4 lines
I'm also trying to figure out if I need the
call_rcu_bh()changes. Since my patch will recognize a grace periods as soon as any pending read-side critical sections complete, I suspect that I don't need this change.Except that under a softirq flood, a reader in a different read-side critical section may get delayed a lot holding up RCU. Let me know if I am missing something here.
Quoted 6 lines
Hi Dipankar,
O.k. That makes sense. So the
rcu_read_lock_bh(),rcu_read_unlock_bh()andcall_rcu_bh()would be the preferred interface. Are there cases where they can't be used? How do you decide where to use the_bhflavor?
Hello, Jim,
You would use rcu_read_lock() instead of rcu_read_lock_bh() in cases where you did not want the read-side code to disable bottom halves. This is very similar to choosing between read_lock() and read_lock_bh() -- if you unnecessarily use read_lock_bh() or rcu_read_lock_bh(), you will be unnecessarily delaying drivers' bottom-half execution.
Quoted 3 lines
I see that
local_bh_enable()WARNS if interrupts are disabled. Is that the issue? Are rcu_read_lock()/rcu_read_unlock() ever called from code which disables interrupts?
The RCU "_bh()" interfaces correspond to a different set of quiescent states than do the standard interfaces. You could indeed use rcu_read_lock() with interrupts disabled, but I don't know of any such use.
Thanx, Paul
Quoted 3 lines
Jim Houston - Concurrent Computer Corp.
Quoted 8 lines · Jim Houston
I know that I'm questioning one of your design goals for RCU by adding overhead to the read-side. I have read everything I could find on RCU. My belief is that the cost of the
xchg()instruction is small compared to the cache benifit of freeing memory more quickly. I think it's more interesting to look at the impact of thexchg()at the level of an entire system call. Adding 30 nanoseconds to a open/close path that tasks 3 microseconds seems reasonable. It is hard to measure the benefit of reusing the a dcache entry more quickly.
Hello, Jim,
The other thing to keep in mind is that reducing the grace-period duration increases the per-access overhead, since each grace period incurs a cost. So there is a balance that needs to be struck between overflowing memory with a too-long grace period and incurring too much overhead with a too-short grace period.
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
Thanx, Paul
PS. My concerns with some aspects of your design aside, your
getting a significant change to the RCU infrastructure to work reasonably well is quite impressive!
Quoted 18 lines · Paul E. McKenney
Quoted 8 lines · Jim Houston
I know that I'm questioning one of your design goals for RCU by adding overhead to the read-side. I have read everything I could find on RCU. My belief is that the cost of the
xchg()instruction is small compared to the cache benifit of freeing memory more quickly. I think it's more interesting to look at the impact of thexchg()at the level of an entire system call. Adding 30 nanoseconds to a open/close path that tasks 3 microseconds seems reasonable. It is hard to measure the benefit of reusing the a dcache entry more quickly.Hello, Jim,
The other thing to keep in mind is that reducing the grace-period duration increases the per-access overhead, since each grace period incurs a cost. So there is a balance that needs to be struck between overflowing memory with a too-long grace period and incurring too much overhead with a too-short grace period.
Quoted 8 lines
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
Thanx, Paul
PS. My concerns with some aspects of your design aside, your
getting a significant change to the RCU infrastructure to work reasonably well is quite impressive!
Hi Paul,
I have two module parameters in the patch which can be used to tune how often grace periods are started. They can be set at boot time as follows:
rcupdate.rcu_max_count=#
The per-cpu count of queued requests at which to start a new batch. Patch defaults to 256.
rcupdate.rcu_max_time=#
Timeout value in jiffies at which to start a batch. Defaults to HZ/10.
I picked the defaults to start batches with similar frequency to the existing code.
I tested a dual processor with rcupdate.rcu_max_count=0. This will start a grace period for every call_rcu(). I ran my rename test this way and it worked suprisingly well.
I maintain a nxtbatch value which lets me check if the grace period for the entries in the nxt list has started or perhaps already completed. I check this in call_rcu() and avoid mixing batches. Any requests queued before the batch was started will be completed at the end of the grace period. Unless a very small rcu_max_count value is used, there is likely to be some delay between completing a grace period and needing to start another.
Quoted 2 lines
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
It's a balancing act. In some cases we just document the missing functionality. If the local timer is disabled on a cpu, all processes are SCHED_FIFO. In the case of Posix timers, we move timers to honor the procesor shielding an the process affinity.
Jim Houston
Quoted 8 lines · Jim Houston
Quoted 2 lines · Paul E. McKenney
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
It's a balancing act. In some cases we just document the missing functionality. If the local timer is disabled on a cpu, all processes are
SCHED_FIFO. In the case of Posix timers, we move timers to honor the procesor shielding an the process affinity.
I have to ask... When you say that you move the timers, you mean that non-realtime CPU 1 managers timers for realtime CPU 0, so that CPU 1 is (effectively) taking CPU 0's timer interrupts?
Thanx, Paul
Quoted 5 lines · Paul E. McKenney
Quoted 4 lines · Jim Houston
Quoted 2 lines · Paul E. McKenney
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
Quoted 8 lines
Quoted 4 lines
It's a balancing act. In some cases we just document the missing functionality. If the local timer is disabled on a cpu, all processes are
SCHED_FIFO. In the case of Posix timers, we move timers to honor the procesor shielding an the process affinity.I have to ask... When you say that you move the timers, you mean that non-realtime CPU 1 managers timers for realtime CPU 0, so that CPU 1 is (effectively) taking CPU 0's timer interrupts?
Hi Paul,
That is part of the idea. There are lots of timers which we don't expect to have realtime behavior.
There are also services like Posix timers and nanosleep() where we want very predictable behavior. If a process does a nanosleep(), we queue that timer on the local cpu. If process affinity is changed, we will move the timer to a cpu where the process is allowed to run.
We have separate queues for high resolution timers. If the local queue is empty, we shutdown the timer.
Jim Houston - Concurrent Computer Corp.
Quoted 20 lines · Jim Houston
Quoted 5 lines · Paul E. McKenney
Quoted 4 lines · Jim Houston
Quoted 2 lines · Paul E. McKenney
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
Quoted 8 lines
Quoted 4 lines
It's a balancing act. In some cases we just document the missing functionality. If the local timer is disabled on a cpu, all processes are
SCHED_FIFO. In the case of Posix timers, we move timers to honor the procesor shielding an the process affinity.I have to ask... When you say that you move the timers, you mean that non-realtime CPU 1 managers timers for realtime CPU 0, so that CPU 1 is (effectively) taking CPU 0's timer interrupts?
Hi Paul,
That is part of the idea. There are lots of timers which we don't expect to have realtime behavior.
Quoted 7 lines
There are also services like Posix timers and
nanosleep()where we want very predictable behavior. If a process does ananosleep(), we queue that timer on the local cpu. If process affinity is changed, we will move the timer to a cpu where the process is allowed to run.We have separate queues for high resolution timers. If the local queue is empty, we shutdown the timer.
Hello, Jim,
How do you mark a given CPU as being in realtime mode? Or is the timer-shutdown decision based on the presence of a realtime process runnable on the given CPU or some such?
Still trying to figure out a way to make this work without adding overhead to rcu_read_unlock()...
Thanx, Paul
Quoted 29 lines · Paul E. McKenney
Quoted 20 lines · Jim Houston
Quoted 5 lines · Paul E. McKenney
Quoted 4 lines · Jim Houston
Quoted 2 lines · Paul E. McKenney
How does the rest of the kernel work with all interrupts to a particular CPU shut off? For example, how do you timeslice?
Quoted 8 lines
Quoted 4 lines
It's a balancing act. In some cases we just document the missing functionality. If the local timer is disabled on a cpu, all processes are
SCHED_FIFO. In the case of Posix timers, we move timers to honor the procesor shielding an the process affinity.I have to ask... When you say that you move the timers, you mean that non-realtime CPU 1 managers timers for realtime CPU 0, so that CPU 1 is (effectively) taking CPU 0's timer interrupts?
Hi Paul,
That is part of the idea. There are lots of timers which we don't expect to have realtime behavior.
Quoted 7 lines
There are also services like Posix timers and
nanosleep()where we want very predictable behavior. If a process does ananosleep(), we queue that timer on the local cpu. If process affinity is changed, we will move the timer to a cpu where the process is allowed to run.We have separate queues for high resolution timers. If the local queue is empty, we shutdown the timer.
Quoted 8 lines
Hello, Jim,
How do you mark a given CPU as being in realtime mode? Or is the timer-shutdown decision based on the presence of a realtime process runnable on the given CPU or some such?
Still trying to figure out a way to make this work without adding overhead to
rcu_read_unlock()...
Hi Paul
We add the following /proc files:
/proc/shield/irqs
Setting a bit limits the corresponding cpu to only handle interrupts which are explicitly directed to that cpu.
/proc/shield/ltmrs
Setting a bit limits the use of local timers on the corresponding cpu.
/proc/shield/procs
Setting a bit limits the cpu to only run processes which have set affinity to that cpu.
When the user changes something we adjust irq routing and migrate processes and timers appropriately.
Jim Houston - Concurrent Computer Corp.
Quoted 12 lines · Jim Houston
We add the following /proc files:
/proc/shield/irqs
Setting a bit limits the corresponding cpu to only handle interrupts which are explicitly directed to that cpu.
/proc/shield/ltmrs
Setting a bit limits the use of local timers on the corresponding cpu.
How do you handle schedule_delayed_work_on()?
slab uses it to drain the per-cpu caches. It's not fatal if a cpu doesn't drain it's caches (just some wasted memory), but it should be documented.
--
Manfred
Quoted 11 lines · Manfred Spraul
Quoted 5 lines · Jim Houston
We add the following /proc files:
/proc/shield/ltmrs
Setting a bit limits the use of local timers on the corresponding cpu.How do you handle
schedule_delayed_work_on()?
slab uses it to drain the per-cpu caches. It's not fatal if a cpu doesn't drain it's caches (just some wasted memory), but it should be documented.
Hi Manfred,
The timer shielding migrates most of the timers to non-shielded cpus but does keep track of timers queued with add_timer_on(). These are polled periodically from a non-shielded cpu, and an inter-processsor interrupt is used to force the shielded cpu to handle their expiry.
Jim Houston - Concurrent Computer Corp.