RCU for low latency (experimental)

Here is the RCU patch for low scheduling latency Andrew was talking about in the other thread. I had done some measurements with amlat on a 2.4 GHz P4 xeon box with 256MB memory running dbench and it reduced worst case scheduling latencies from 800 microseconds to about 400 microseconds.

It uses per-cpu kernel threads to execute excess callbacks and pretty much relies on preemption.

Reduce bh processing time of rcu callbacks by using tunable per-cpu krcud daemeons.

Quoted 7 lines · Dipankar Sarma

Here is the RCU patch for low scheduling latency Andrew was talking about in the other thread. I had done some measurements with amlat on a 2.4 GHz P4 xeon box with 256MB memory running dbench and it reduced worst case scheduling latencies from 800 microseconds to about 400 microseconds.

Quoted 2 lines

It uses per-cpu kernel threads to execute excess callbacks and pretty much relies on preemption.

Is simple enough. Do you expect this will help with the route cache reaping problem? I do think it's a bit hard to justify purely on the basis of the scheduling latency goodness.

Quoted 3 lines

Reduce bh processing time of rcu callbacks by using tunable per-cpu krcud daemeons.

why not just use work queues ?

Here is the RCU patch for low scheduling latency Andrew was talking about in the other thread. I had done some measurements with

Quoted 3 lines

Reduce bh processing time of rcu callbacks by using tunable per-cpu krcud daemeons.

why not just use work queues ?

Quoted 2 lines · Dipankar Sarma

Here is the RCU patch for low scheduling latency Andrew was talking about in the other thread. I had done some measurements with

I don't see why you're using an additional kernel thread. I told you one way to implement it via softirq taking advantage of the scheduler-friendy re-arming tasklets.

Quoted 5 lines · Arjan van de Ven

Quoted 3 lines

Reduce bh processing time of rcu callbacks by using tunable per-cpu krcud daemeons.

why not just use work queues ?

I don't know if work queues are scheduler friendly, but definitely the rearming tasklets are. Running a dozen callbacks per pass and queueing any remining work to a rearming tasklet should fix it.

Quoted 5 lines · Arjan van de Ven

Quoted 3 lines

Reduce bh processing time of rcu callbacks by using tunable per-cpu krcud daemeons.

why not just use work queues ?

I don't know if work queues are scheduler friendly, but definitely the rearming tasklets are. Running a dozen callbacks per pass and queueing any remining work to a rearming tasklet should fix it.

I have a patch for that too which I have been testing for DoS in route cache, not latency. It is worth testing it here, however I think re-arming tasklets is not as friendly to latency as executing the rcu callbacks from process context. One thing I have noticed is that more softirqs worsen latency irrespective of the worst-case softirq length.

Quoted 5 lines · Andrea Arcangeli

Quoted 4 lines · Arjan van de Ven

Quoted 3 lines

Reduce bh processing time of rcu callbacks by using tunable per-cpu krcud daemeons.

Quoted 5 lines

Quoted 1 line

why not just use work queues ?

I don't know if work queues are scheduler friendly, but definitely the rearming tasklets are. Running a dozen callbacks per pass and queueing any remining work to a rearming tasklet should fix it.

One problem that likely happen here is that under heavy interrupt load, large number of softirqs still starve out user processes.

In my DoS testing setup, I see that limiting RCU softirqs and re-arming tasklets has no effect on user process starvation.

Quoted 2 lines

One problem that likely happen here is that under heavy interrupt load, large number of softirqs still starve out user processes.

Disagree, run 1 callback per tasklet and then you will not measure the cost of this callback compared to the cost of talking to the hardware entering/exiting kernel etc...

Quoted 2 lines

In my DoS testing setup, I see that limiting RCU softirqs and re-arming tasklets has no effect on user process starvation.

in an irq flood load that stalls userspace anyways it's ok to spread the callback load into the irqs, 10 tasklets and in turn 10 callbacks per irqs or so. That load isn't scheduler friendly anyways.

the one property you need is not to be RT like eventd, to be scheduler friendly, but guaranteed to make progress too and that's what softirqs can give you and that's why I used only softirqs in my rcu_poll patches too ;).

Quoted 6 lines

Quoted 2 lines

One problem that likely happen here is that under heavy interrupt load, large number of softirqs still starve out user processes.

Disagree, run 1 callback per tasklet and then you will not measure the cost of this callback compared to the cost of talking to the hardware entering/exiting kernel etc...

The difficult situation is when the workload generates -lots- of RCU callbacks, such as the tiny-files workload that Andrew pointed Dipankar at. In this case, if we rely only on softirq, we are between a rock and a hard place. The rock is that if we run too many softirq handlers processing all the RCU callbacks, we will degrade realtime response. The hard place is that if we delay softirq processing in order to avoid degrading realtime response, we risk having RCU callbacks piling up, exhausting memory.

This situation is what motivated using a per-CPU kernel daemon to handle the "overflow" callbacks that could not handled by softirq without degrading realtime response. Since the kernel daemon is preemptible, it can run continuously without degrading realtime response -- it will be preempted whenever a realtime task needs to run. Therefore, the kernel-daemon approach permits safely processing RCU callbacks up to the full capacity of the CPU.

My guess is that the small-file creation/deletion workload can generate on the order of 100K RCU callbacks per second, and perhaps as many as 1M RCU callbacks per second on a fast CPU. The kernel daemon approach should be able to handle this load gracefully.

Of course, it would be possible to insert preemption points in the kernel daemon should we choose to support realtime response in absence of CONFIG_PREEMPT.

That said, it may well be necessary to use IPIs in some cases, as rcu-poll does, to accelerate RCU grace periods. For example, if low on memory or if too many callbacks have accumulated. If this ends up being necessary, it might get the best of both worlds, since one would shorten grace periods only when there are already a lot of callbacks, so that the overhead would be nicely amortized. It will be interesting to see how this goes!

Quoted 6 lines

Quoted 2 lines

In my DoS testing setup, I see that limiting RCU softirqs and re-arming tasklets has no effect on user process starvation.

in an irq flood load that stalls userspace anyways it's ok to spread the callback load into the irqs, 10 tasklets and in turn 10 callbacks per irqs or so. That load isn't scheduler friendly anyways.

The goal is to run reasonably, even under this workload, which, as you say is not scheduler friendly. Scheduler hostile, in fact. ;-)

Quoted 4 lines

the one property you need is not to be RT like eventd, to be scheduler friendly, but guaranteed to make progress too and that's what softirqs can give you and that's why I used only softirqs in my rcu_poll patches too ;).

The problem is that some of the workloads generate thousands of RCU callbacks per grace period. If we are going to provide realtime scheduling latencies in the hundreds of microseconds, we probably aren't going to get away with executing all of these callbacks in softirq context.

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 2 lines

One problem that likely happen here is that under heavy interrupt load, large number of softirqs still starve out user processes.

Disagree, run 1 callback per tasklet and then you will not measure the cost of this callback compared to the cost of talking to the hardware entering/exiting kernel etc...

The difficult situation is when the workload generates -lots- of RCU callbacks, such as the tiny-files workload that Andrew pointed Dipankar at. In this case, if we rely only on softirq, we are between a rock and a hard place. The rock is that if we run too many softirq handlers processing all the RCU callbacks, we will degrade realtime response. The hard place is that if we delay softirq processing in order to avoid degrading realtime response, we risk having RCU callbacks piling up, exhausting memory.

Quoted 7 lines

This situation is what motivated using a per-CPU kernel daemon to handle the "overflow" callbacks that could not handled by softirq without degrading realtime response. Since the kernel daemon is preemptible, it can run continuously without degrading realtime response -- it will be preempted whenever a realtime task needs to run. Therefore, the kernel-daemon approach permits safely processing RCU callbacks up to the full capacity of the CPU.

and it tends to runs the machine OOM if there's a single RT application generating the dcache load ;).

Quoted 4 lines

My guess is that the small-file creation/deletion workload can generate on the order of 100K RCU callbacks per second, and perhaps as many as 1M RCU callbacks per second on a fast CPU. The kernel daemon approach should be able to handle this load gracefully.

running 1 callback per softirq (and in turn 10 callbacks per hardware irq) shouldn't be measurable compared to the cost of the hardware handling, skb memory allocation, iommu mapping etc...

why do you care about this specific irq-flood corner case where the load is lost in the noise and there's no way to make it scheduler-friendy either since hardware irqs are involved?

the only way to make that workload scheduler friendly, is to bind the irq of the network card to cpu 1 and to bind the RT app to cpu0, no other way around it, no matter where you run the rcu callbacks (if in irq context, or non-irq context).

Quoted 3 lines

Of course, it would be possible to insert preemption points in the kernel daemon should we choose to support realtime response in absence of CONFIG_PREEMPT.

2.6 support realtime response with PREEMPT=y and =n, infact preempt doesn't affect the worst case RT latency at all, it can't.

So you shouldn't relay on preempt to avoid explicit schedule points there.

Quoted 7 lines

That said, it may well be necessary to use IPIs in some cases, as rcu-poll does, to accelerate RCU grace periods. For example, if low on memory or if too many callbacks have accumulated. If this ends up being necessary, it might get the best of both worlds, since one would shorten grace periods only when there are already a lot of callbacks, so that the overhead would be nicely amortized. It will be interesting to see how this goes!

I'm not sure in this case if IPI are needed just for offloading the remaining work to a rearming tasklet.

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

In my DoS testing setup, I see that limiting RCU softirqs and re-arming tasklets has no effect on user process starvation.

in an irq flood load that stalls userspace anyways it's ok to spread the callback load into the irqs, 10 tasklets and in turn 10 callbacks per irqs or so. That load isn't scheduler friendly anyways.

Quoted 2 lines

The goal is to run reasonably, even under this workload, which, as you say is not scheduler friendly. Scheduler hostile, in fact. ;-)

Indeed it is, and I'm simply expecting not any real difference by running 10 callbacks per hardware irq, so I find it a non very interesting workload to choose between a softirq or the kernel thread, but maybe I'm overlooking something.

Quoted 10 lines

Quoted 4 lines

the one property you need is not to be RT like eventd, to be scheduler friendly, but guaranteed to make progress too and that's what softirqs can give you and that's why I used only softirqs in my rcu_poll patches too ;).

The problem is that some of the workloads generate thousands of RCU callbacks per grace period. If we are going to provide realtime scheduling latencies in the hundreds of microseconds, we probably aren't going to get away with executing all of these callbacks in softirq context.

it should, you just need to run 1 callback per re-arming tasklet (then after the list is empty you stop re-arming), the softirq code will do the rest for you offloading it immediatly to ksoftirqd after 10 callbacks, and ksoftirqd will reschedule explicitly once every 10 callbacks too. The whole point of ksoftirqd is to make re-arming tasklets irq-friendy. Though there's a cost in offloading the work to a daemon, so we must not do it too frequently, so we retry 10 times before giving up and claiming the tasklet re-entrant.

On Wed, Mar 24, 2004 at 09:26:57AM -0800, Paul E. McKenney wrote:
running 1 callback per softirq (and in turn 10 callbacks per hardware irq) shouldn't be measurable compared to the cost of the hardware handling, skb memory allocation, iommu mapping etc...

why do you care about this specific irq-flood corner case where the load is lost in the noise and there's no way to make it scheduler-friendy either since hardware irqs are involved?

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

In my DoS testing setup, I see that limiting RCU softirqs and re-arming tasklets has no effect on user process starvation.

in an irq flood load that stalls userspace anyways it's ok to spread the callback load into the irqs, 10 tasklets and in turn 10 callbacks per irqs or so. That load isn't scheduler friendly anyways.

Quoted 2 lines

The goal is to run reasonably, even under this workload, which, as you say is not scheduler friendly. Scheduler hostile, in fact. ;-)

Indeed it is, and I'm simply expecting not any real difference by running 10 callbacks per hardware irq, so I find it a non very interesting workload to choose between a softirq or the kernel thread, but maybe I'm overlooking something.

Quoted 5 lines

The problem is that some of the workloads generate thousands of RCU callbacks per grace period. If we are going to provide realtime scheduling latencies in the hundreds of microseconds, we probably aren't going to get away with executing all of these callbacks in softirq context.

it should, you just need to run 1 callback per re-arming tasklet (then after the list is empty you stop re-arming), the softirq code will do the rest for you offloading it immediatly to ksoftirqd after 10 callbacks, and ksoftirqd will reschedule explicitly once every 10 callbacks too. The whole point of ksoftirqd is to make re-arming tasklets irq-friendy. Though there's a cost in offloading the work to a daemon, so we must not do it too frequently, so we retry 10 times before giving up and claiming the tasklet re-entrant.

Quoted 5 lines · Andrea Arcangeli

On Wed, Mar 24, 2004 at 09:26:57AM -0800, Paul E. McKenney wrote:
running 1 callback per softirq (and in turn 10 callbacks per hardware irq) shouldn't be measurable compared to the cost of the hardware handling, skb memory allocation, iommu mapping etc...

Quoted 3 lines

why do you care about this specific irq-flood corner case where the load is lost in the noise and there's no way to make it scheduler-friendy either since hardware irqs are involved?

We are looking at two different problems. Scheduling latency and DoS on route cache that results in dst cache overflows. The second one is an irq-flood, but latency is the least of the problems there.

Quoted 10 lines

Quoted 9 lines

Quoted 6 lines

Quoted 2 lines

In my DoS testing setup, I see that limiting RCU softirqs and re-arming tasklets has no effect on user process starvation.

in an irq flood load that stalls userspace anyways it's ok to spread the callback load into the irqs, 10 tasklets and in turn 10 callbacks per irqs or so. That load isn't scheduler friendly anyways.

The goal is to run reasonably, even under this workload, which, as you say is not scheduler friendly. Scheduler hostile, in fact. ;-)

Quoted 4 lines

Indeed it is, and I'm simply expecting not any real difference by running 10 callbacks per hardware irq, so I find it a non very interesting workload to choose between a softirq or the kernel thread, but maybe I'm overlooking something.

The difference here is that during the callbacks in the kernel thread, I don't disable softirqs unlike ksoftirqd thus giving it more opportunity for preemption.

I had already been testing this for the DoS issue, but I tried it with amlat on a 2.4 GHz (UP) P4 xeon with 256MB ram and dbench 32 in a loop. Here are the results (CONFIG_PREEMPT = y) -

2.6.0 vanilla - 711 microseconds
2.6.0 + throttle-rcu - 439 microseconds
2.6.0 + rcu-low-lat - 413 microseconds

So under dbench workload atleast, throttling RCU works just as good as offloading them to a kernel thread (krcud) as rcu-low-lat does.

I used the following throttle-rcu patch with rcupdate.rcumaxbatch set to 16 and rcupdate.rcuplugticks set to 0. That is essentially equvalent to Andrea's earler suggestion. I have so many knobs in the patch because I had written it earlier for other experiments. Anyway, if throttling works as well as this in terms of latency for other workloads as well and there isn't any OOM situations, it is preferable to creating another per-cpu thread.

Quoted 4 lines · Dipankar Sarma

The difference here is that during the callbacks in the kernel thread, I don't disable softirqs unlike ksoftirqd thus giving it more opportunity for preemption.

preemption where? in irq? softirqd will preempt just fine.

Also not that while we process the callbacks in softirqd, the irqs will stop running the callbacks, just like in your scenario. the callbacks and the other softirqs will be processed from user context, and it won't be different from scheduling krcud first and ksoftirqd later.

Quoted 8 lines

I had already been testing this for the DoS issue, but I tried it with amlat on a 2.4 GHz (UP) P4 xeon with 256MB ram and dbench 32 in a loop. Here are the results (CONFIG_PREEMPT = y) -

2.6.0 vanilla - 711 microseconds
2.6.0 + throttle-rcu - 439 microseconds
2.6.0 + rcu-low-lat - 413 microseconds

Quoted 3 lines

So under dbench workload atleast, throttling RCU works just as good as offloading them to a kernel thread (krcud) as rcu-low-lat does.

very nice.

Quoted 7 lines

I used the following throttle-rcu patch with rcupdate.rcumaxbatch set to 16 and rcupdate.rcuplugticks set to 0. That is essentially equvalent to Andrea's earler suggestion. I have so many knobs in the patch because I had written it earlier for other experiments. Anyway, if throttling works as well as this in terms of latency for other workloads as well and there isn't any OOM situations, it is preferable to creating another per-cpu thread.

I don't think this is enough (it is enough for the above workload though, maybe for the dcache too, but it's not generic enough), 16 callbacks per tick too low frequency, it may not keep up, that's why I

But I certainly agree this is a nice solution in practice (at least with all the common usages).

That was not 16 callbacks per tick, it was 16 callbacks in one batch of a single softirq. And then I reschedule the RCU tasklet

to process the rest. I am planning to vary this and see if we should do even less per softirq.

If the "nice" value does not matter, this seems reasonable, at least for some value of 10. ;-)

Quoted 2 lines · Dipankar Sarma

That was not 16 callbacks per tick, it was 16 callbacks in one batch of a single softirq. And then I reschedule the RCU tasklet

sorry so you're already using tasklets in current code? I misunderstood the current code then.

Quoted 6 lines · Andrea Arcangeli

Quoted 2 lines · Dipankar Sarma

That was not 16 callbacks per tick, it was 16 callbacks in one batch of a single softirq. And then I reschedule the RCU tasklet

sorry so you're already using tasklets in current code? I misunderstood the current code then.

kernel/rcupdate.c renamed from kernel/rcupdate.c~throttle-rcu +6 -0

+               if (count >= rcumaxbatch) {
+                       RCU_plugticks(cpu) = rcuplugticks;
+                       if (!RCU_plugticks(cpu))
+                               tasklet_hi_schedule(&RCU_tasklet(cpu));
+                       break;
+               }

That does it. Although, the tasklet handler needs to optimized

Quoted 2 lines · Paul E. McKenney

If the "nice" value does not matter, this seems reasonable, at least for some value of 10. ;-)

the nice value should no matter for this.

btw, (just to avoid misunderstanding) the number 10 is MAX_SOFTIRQ_RESTART.

Quoted 6 lines · Andrea Arcangeli

Quoted 2 lines · Dipankar Sarma

That was not 16 callbacks per tick, it was 16 callbacks in one batch of a single softirq. And then I reschedule the RCU tasklet

sorry so you're already using tasklets in current code? I misunderstood the current code then.

At Thu, 25 Mar 2004 05:16:43 +0530,

Quoted 9 lines · Dipankar Sarma

Quoted 6 lines · Andrea Arcangeli

Quoted 2 lines · Dipankar Sarma

That was not 16 callbacks per tick, it was 16 callbacks in one batch of a single softirq. And then I reschedule the RCU tasklet

sorry so you're already using tasklets in current code? I misunderstood the current code then.

kernel/rcupdate.c void fastcall call_rcu(struct rcu_head * · line 105

Quoted 6 lines

kernel/rcupdate.c renamed from kernel/rcupdate.c~throttle-rcu +6 -0

+               if (count >= rcumaxbatch) {
+                       RCU_plugticks(cpu) = rcuplugticks;
+                       if (!RCU_plugticks(cpu))
+                               tasklet_hi_schedule(&RCU_tasklet(cpu));
+                       break;
+               }

it seems count is never incremented in your patch... or am i missing something?

anyway, i confirmed that with the original krcud patch the latency with dcache flood can be eliminated.

for the non-preemptive case, rcu_bh_callback_limit() should return bhlimit always, though. otherwise cond_resched() isn't called in the callback loop properly.

Quoted 2 lines · Takashi Iwai

it seems count is never incremented in your patch... or am i missing something?

I messed it up when I forward ported the throttle-rcu.patch from 2.6.0+lots-of-instrumentation to 2.6.4-vanilla in order to publish in lkml. The original patch did this -

Quoted 2 lines

anyway, i confirmed that with the original krcud patch the latency with dcache flood can be eliminated.

Does the throttle-rcu patch also help eliminate dcache flood ? You can try by just changing count >= rcumaxbatch to ++count > rcumaxbatch.

Quoted 3 lines

for the non-preemptive case, rcu_bh_callback_limit() should return bhlimit always, though. otherwise cond_resched() isn't called in the callback loop properly.

Yes, I think we should consider using limiting even in the non-preemptive case.

Quoted 6 lines

Quoted 3 lines

anyway, i confirmed that with the original krcud patch the latency with dcache flood can be eliminated.

Does the throttle-rcu patch also help eliminate dcache flood ? You can try by just changing count >= rcumaxbatch to ++count > rcumaxbatch.

i'll try it later.

At Sun, 28 Mar 2004 19:28:41 +0200,

Quoted 7 lines · I wrote:

Quoted 6 lines

Quoted 3 lines

anyway, i confirmed that with the original krcud patch the latency with dcache flood can be eliminated.

Does the throttle-rcu patch also help eliminate dcache flood ? You can try by just changing count >= rcumaxbatch to ++count > rcumaxbatch.

Quoted 1 line

i'll try it later.

the throttle-rcu patch does work indeed well even without preemption. i've tested maxbatch=16 and plugticks=0. in the older version, there was 20ms long latency, while in the patched version, no measurable latency more than 1ms.