RCU for low latency [0/1]

On akpm's prodding, I have been looking at scheduling latency issues due to long running interrupts. Since RCU callbacks are invoked from softirq context, it is one of the first things needed investigation. I used a P4 2.4Ghz UP system with 256MB memory and dbench 32 in a loop to generate a large number of RCU updates and measured scheduling latency using amlat
(http://www.zipworld.com.au/~akpm/linux/schedlat.html#amlat).
All measurements were done with preemption enabled of course.

Vanilla 2.6.0-test8 kernel showed a latency of around 800 microseconds with RCU callback batches as long as 1800 callbacks. Each of these were essentially just dentries being returned to their slab and it turns out that we can return on an avarage 4 objects per microsecond in that system. Thus the longest RCU callback handling took over 400 microseconds. Clearly for sub-500 microsecond latency, we needed to do something about this.

I have a number of experimental patches that improves latency. The first approach took advantage of UP kernel and by ensuring that read-side critical sections of RCU users are not interrupted by a handler that can update it. This showed good results - consistently around 400 microseconds of latency. However since people seem to care about latency in SMP too, there is another set of patches that uses per-cpu kernel thread for RCU callback processing pretty much like ksoftirqd. Beyond a certain limit, remaining RCU callbacks are punted to the kernel thread which can be preempted for better latency. I did consider keventd, but it turned out to be problematic mainly because it can get starved and other keventd work can block for long holding up RCU. One other optimization I did at akpm's suggestion was to do the RCU callback punting only if there is a RT priority task in
the runqueue of that CPU. This approach too showed good results with latency limited to around 400 microseconds.

Of course, all these were done with one type of workload aimed at generating RCU callbacks, it would be interesting to see how they fair with other workloads. Yet another kernel thread is icky, but can't see another way to allow RT tasks to run. I have also been doing instrumentation to see where the rest of the (non-rcu-related) latency is coming from, particularly if there are long running irqs/softirqs and it apparently is not so. It looks like consecutive interrupts at inopportune moments is causing additional latency.

The actual RCU patches for low latency in SMP follows. A kernel parementer rcubhlimit sets the maximum number of callbacks invoked from softirq context before punting to krcud (default 256). rcubhlimit = 0 indicates no krcud at all.

These are meant for latency investigations, not meant for inclusion yet.

Thanks
Dipankar

Provide a rq_has_rt_task() interface to detect runqueues with real time priority tasks. Useful for RCU optimizations.

 include/linux/sched.h |    1 +
 kernel/sched.c        |   31 ++++++++++++++++++++++++++++++-
 2 files changed, 31 insertions(+), 1 deletion(-)

diff -puN include/linux/sched.h~rq-has-rt-task include/linux/sched.h
@@ -524,6 +524,7 @@ extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
 extern int task_curr(task_t *p);
 extern int idle_cpu(int cpu);
+extern int rq_has_rt_task(int cpu);
 
 void yield(void);
 

diff -puN kernel/sched.c~rq-has-rt-task kernel/sched.c
@@ -199,7 +199,7 @@ struct prio_array {
 struct runqueue {
 	spinlock_t lock;
 	unsigned long nr_running, nr_switches, expired_timestamp,
-			nr_uninterruptible;
+			nr_uninterruptible, nr_rt_running;
 	task_t *curr, *idle;
 	struct mm_struct *prev_mm;
 	prio_array_t *active, *expired, arrays[2];

@@ -275,6 +275,19 @@ __init void node_nr_running_init(void)
 
 #endif /* CONFIG_NUMA */
 
+static inline void nr_rt_running_inc(runqueue_t *rq, struct task_struct *p)
+{
+	if (rt_task(p))
+		rq->nr_rt_running++;
+}
+
+static inline void nr_rt_running_dec(runqueue_t *rq, struct task_struct *p)
+{
+	if (rt_task(p))
+		rq->nr_rt_running--;
+}
+
+
 /*
  * task_rq_lock - lock the runqueue a given task resides on and disable
  * interrupts.  Note the ordering: we can safely lookup the task_rq without

@@ -339,6 +352,17 @@ static inline void enqueue_task(struct t
 }
 
 /*
+ * rq_has_rt_task - return 1 if the runqueue has any RT task else return 0
+ * It does not lock the runqueue, the caller needs to explicitly lock
+ * the runqueue if it cares about that.
+ */
+int rq_has_rt_task(int cpu)
+{
+	struct runqueue *rq = cpu_rq(cpu);
+	return (rq->nr_rt_running != 0);
+}
+
+/*
  * effective_prio - return the priority that is based on the static
  * priority but is modified by bonuses/penalties.
  *

@@ -376,6 +400,7 @@ static inline void __activate_task(task_
 {
 	enqueue_task(p, rq->active);
 	nr_running_inc(rq);
+	nr_rt_running_inc(rq, p);
 }
 
 static void recalc_task_prio(task_t *p, unsigned long long now)

@@ -498,6 +523,7 @@ static inline void activate_task(task_t 
 static inline void deactivate_task(struct task_struct *p, runqueue_t *rq)
 {
 	nr_running_dec(rq);
+	nr_rt_running_dec(rq, p);
 	if (p->state == TASK_UNINTERRUPTIBLE)
 		rq->nr_uninterruptible++;
 	dequeue_task(p, p->array);

@@ -691,6 +717,7 @@ void wake_up_forked_process(task_t * p)
 		p->array = current->array;
 		p->array->nr_active++;
 		nr_running_inc(rq);
+		nr_rt_running_inc(rq, p);
 	}
 	task_rq_unlock(rq, &flags);
 }

@@ -1117,8 +1144,10 @@ static inline void pull_task(runqueue_t 
 {
 	dequeue_task(p, src_array);
 	nr_running_dec(src_rq);
+	nr_rt_running_dec(src_rq, p);
 	set_task_cpu(p, this_cpu);
 	nr_running_inc(this_rq);
+	nr_rt_running_inc(this_rq, p);
 	enqueue_task(p, this_rq->active);
 	/*
 	 * Note that idle threads have a prio of MAX_PRIO, for this test

_

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

 include/linux/rcupdate.h |    4 +
 kernel/rcupdate.c        |  101 ++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 103 insertions(+), 2 deletions(-)

diff -puN include/linux/rcupdate.h~rcu-reduce-bh-time include/linux/rcupdate.h
@@ -93,9 +93,11 @@ struct rcu_data {
 	long		qsctr;		 /* User-mode/idle loop etc. */
         long            last_qsctr;	 /* value of qsctr at beginning */
                                          /* of rcu grace period */
+	struct task_struct *krcud;
         long  	       	batch;           /* Batch # for current RCU batch */
         struct list_head  nxtlist;
         struct list_head  curlist;
+        struct list_head  rcudlist;
 };
 
 DECLARE_PER_CPU(struct rcu_data, rcu_data);

@@ -103,9 +105,11 @@ extern struct rcu_ctrlblk rcu_ctrlblk;
 
 #define RCU_qsctr(cpu) 		(per_cpu(rcu_data, (cpu)).qsctr)
 #define RCU_last_qsctr(cpu) 	(per_cpu(rcu_data, (cpu)).last_qsctr)
+#define RCU_krcud(cpu) 		(per_cpu(rcu_data, (cpu)).krcud)
 #define RCU_batch(cpu) 		(per_cpu(rcu_data, (cpu)).batch)
 #define RCU_nxtlist(cpu) 	(per_cpu(rcu_data, (cpu)).nxtlist)
 #define RCU_curlist(cpu) 	(per_cpu(rcu_data, (cpu)).curlist)
+#define RCU_rcudlist(cpu) 	(per_cpu(rcu_data, (cpu)).rcudlist)
 
 #define RCU_QSCTR_INVALID	0
 

_

In message <[email protected]> you write:

{
	if (in_softirq() && RCU_krcud(cpu) && rq_has_rt_task(cpu))
		return rcu_max_bh_callbacks;
	return (unsigned int)-1;
}

	unsigned int count, limit = max_rcu_at_once(cpu);

	...
		if (++count > limit)

	int pid;
	pid = kernel_thread(krcud, (void *)(long)cpu, CLONE_KERNEL);
	if (pid < 0) {
		printk(printk("krcud for %i failed\n", cpu);
		return pid;
	}

Please use module_param(). If it's a good name for a variable, it's a good name for a parameter. eg. just call the variable bhlimit, and then the boot parameter will be called "rcu.bhlimit" which fits the calling conventio we're trying to encourage.

Cheers,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

Hello Rusty,

Done, except that once we reach the callback limit, we need to check for RT tasks after every callback, instead of at the start of the RCU batch.

I will use kthread primitives once they are available in mainline.

All these go away with kthreads.

I will clean this up later should we come to a conclusion that we need the low-latency changes in mainline. I don't see any non-driver kernel code using module_param() though.

New patch below. Needs rq-has-rt-task.patch I mailed earlier. There are more issues that need investigations - can we starve RCU callbacks leading to OOMs, should we compile out krcuds based on a config option (CONFIG_PREEMPT?). Any suggestions ?

Thanks
Dipankar

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

 include/linux/rcupdate.h |    4 +
 kernel/rcupdate.c        |   99 ++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 101 insertions(+), 2 deletions(-)

diff -puN include/linux/rcupdate.h~rcu-reduce-bh-time include/linux/rcupdate.h
@@ -93,9 +93,11 @@ struct rcu_data {
 	long		qsctr;		 /* User-mode/idle loop etc. */
         long            last_qsctr;	 /* value of qsctr at beginning */
                                          /* of rcu grace period */
+	struct task_struct *krcud;
         long  	       	batch;           /* Batch # for current RCU batch */
         struct list_head  nxtlist;
         struct list_head  curlist;
+        struct list_head  rcudlist;
 };
 
 DECLARE_PER_CPU(struct rcu_data, rcu_data);

@@ -103,9 +105,11 @@ extern struct rcu_ctrlblk rcu_ctrlblk;
 
 #define RCU_qsctr(cpu) 		(per_cpu(rcu_data, (cpu)).qsctr)
 #define RCU_last_qsctr(cpu) 	(per_cpu(rcu_data, (cpu)).last_qsctr)
+#define RCU_krcud(cpu) 		(per_cpu(rcu_data, (cpu)).krcud)
 #define RCU_batch(cpu) 		(per_cpu(rcu_data, (cpu)).batch)
 #define RCU_nxtlist(cpu) 	(per_cpu(rcu_data, (cpu)).nxtlist)
 #define RCU_curlist(cpu) 	(per_cpu(rcu_data, (cpu)).curlist)
+#define RCU_rcudlist(cpu) 	(per_cpu(rcu_data, (cpu)).rcudlist)
 
 #define RCU_QSCTR_INVALID	0
 

_

AFAICT, if you're in a softirq it can't change. If you're not, there's no limit anyway.

But ulterior motive is to push the kthread primitives by making as much code depend on it as possible 8)

I'm trying to catch them as new ones get introduced. If the name is old-style, then there's little point changing (at least for 2.6).

You can screw your machine up with RT tasks, yes. This is no new problem, I think.

Depends on the neatness of the code, I think...

Cheers,
Rusty.

   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy

What if a blocked RT task was woken up by an irq that interrupted RCU callback processing ? All of a sudden you now have a RT task in the queue. Isn't this possible ?

hehe. How nefarious :-)

OK, but I am not sure how to do this for non-module code.

That is another way to look at it :)

Well there seems to be a difference in opinion about whether the krcuds should be pervasive or not. Some think they should be, some thinks they should not be when we aren't aiming for low latency (say CONFIG_PREEMPT=n).

Thanks
Dipankar

In message <[email protected]> you write:

Yes, you're absolutely right. You could just handle this by breaking out of the loop (after processing one rcu) as soon as there's a runnable rt task, independent of limit.

Well, you don't get to be a kernel hacker simply by looking good in Speedos.

module_param() works for non-module code (it automatically inserts a "rcu." prefix in the name though).

I think it's fair, though. If you really absorb all your CPU with RT tasks, you will starve important things: that's why RT is a root priv.

Personally I don't like overloading the semantic of CONFIG_PREEMPT. But I think CONFIG_PREEMPT is a bad idea anyway: it's not really a question you can ask a user during config.

CONFIG_LOW_LATENCY (Description: Sacrifice some raw performance to increase latency) makes more sense, and would fit here, too.

Another option is to overload ksoftirq to do what krcud does: they're v. similar in nature AFAICT.

Sorry I can't be more helpful 8)
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

_high_ latency and _low_ performance.
i want one of those!

:-)

cheers,

lincoln.

Can you make rq_has_rt_task the slow path? Adding things like this can actually be noticable on microbenchmarks (eg. pipe based ctx switching). Its probably cache artifacts that I see, but it wouldn't hurt to keep the scheduler as tight as possible.

I think this should cover it.

int rq_has_rt_task(int cpu)

{
	runqueue_t *rq = cpu_rq(cpu);
	return (sched_find_first_bit(rq->active) < MAX_RT_PRIO);
}

Any good?

Much better, except, well, rq->active->bitmap. Here is the new rq_has_rt_task() patch.

Thanks
Dipankar

Provide a rq_has_rt_task() interface to detect runqueues with real time priority tasks. Useful for RCU optimizations.

 include/linux/sched.h |    1 +
 kernel/sched.c        |    6 ++++++
 2 files changed, 7 insertions(+)

diff -puN kernel/sched.c~rq-has-rt-task kernel/sched.c
@@ -338,6 +338,12 @@ static inline void enqueue_task(struct t
 	p->array = array;
 }
 
+int rq_has_rt_task(int cpu)
+{
+        runqueue_t *rq = cpu_rq(cpu);
+        return (sched_find_first_bit(rq->active->bitmap) < MAX_RT_PRIO);
+}
+
 /*
  * effective_prio - return the priority that is based on the static
  * priority but is modified by bonuses/penalties.

diff -puN include/linux/sched.h~rq-has-rt-task include/linux/sched.h
@@ -525,6 +525,7 @@ extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
 extern int task_curr(task_t *p);
 extern int idle_cpu(int cpu);
+extern int rq_has_rt_task(int cpu);
 
 void yield(void);
 

_