Re: [mm PATCH 4/6] RCU: preemptible RCU
On Sat, 27 Jan 2007 02:30:17 +0530 Dipankar Sarma <[EMAIL PROTECTED]> wrote: > > > As a consequence of keeping track of RCU readers, the readers > > > have a slight overhead (optimizations in the paper). > > > This implementation co-exists with the "classic" RCU > > > implementations and can be switched to at compiler. > > > > That's yet another question we need to ask people when their kernel dies, > > and yet another deviation between the kernels which we all test, causing > > more dilution of testing efforts. It would be much better if we could > > remove classic RCU. You say this would incur extra cost, but the magnitude > > of that cost is not clear. Please help us make that decision. > > See the Table 2, page 10 of the paper mentioned above. argh. Seems I have to wade through half the paper to understand Table 2. > There is a > ~100ns cost per read-side critical section involved in the preemptible > version of RCU at the moment. Until, we are sure that we don't have > an impact on common workloads, we need to keep the "classic" > implementation around. Ratios, please.. that 100ns appears to be a 100% increase. ie 100ns -> 200ns. There are a couple of ways of working out how much that really matters: a) run a workload or b) instrument a kernel, work out how many times/sec the kernel runs rcu_read_lock(). I suspect b) would be more useful and informative. Either way, please always prepare such info up-front and summarise in the changelog? It's kinda important... - 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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Tue, Jan 23, 2007 at 04:32:59PM -0800, Andrew Morton wrote: > On Tue, 16 Jan 2007 00:58:58 +0530 > Dipankar Sarma <[EMAIL PROTECTED]> wrote: > > > This patch implements a new version of RCU which allows its read-side > > critical sections to be preempted. > > Why is it selectable if CONFIG_PREEMPT=n? It would probably make sense to make CONFIG_RCU_PREEMPT dependent on CONFIG_PREEMPT. I kept it independent because I wanted to test rcupreempt as an equivalent RCU implementation not just for its "preemptibility". > > It uses a set of counter pairs > > to keep track of the read-side critical sections and flips them > > when all tasks exit read-side critical section. The details > > of this implementation can be found in this paper - > > > > http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf > > > > This patch was developed as a part of the -rt kernel > > development and meant to provide better latencies when > > read-side critical sections of RCU don't disable preemption. > > Does it succeed in that attempt? Thus far you've given no reason for > merging this code.. > > This is a pile of tricky new core kernel code for us to test, maintain, > understand, debug, etc. It needs to provide a substantial benefit. Does > it? I am working to compare some latency numbers between different implementations. I will have them out soon. > > As a consequence of keeping track of RCU readers, the readers > > have a slight overhead (optimizations in the paper). > > This implementation co-exists with the "classic" RCU > > implementations and can be switched to at compiler. > > That's yet another question we need to ask people when their kernel dies, > and yet another deviation between the kernels which we all test, causing > more dilution of testing efforts. It would be much better if we could > remove classic RCU. You say this would incur extra cost, but the magnitude > of that cost is not clear. Please help us make that decision. See the Table 2, page 10 of the paper mentioned above. There is a ~100ns cost per read-side critical section involved in the preemptible version of RCU at the moment. Until, we are sure that we don't have an impact on common workloads, we need to keep the "classic" implementation around. Thanks Dipankar - 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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Tue, Jan 23, 2007 at 04:32:59PM -0800, Andrew Morton wrote: On Tue, 16 Jan 2007 00:58:58 +0530 Dipankar Sarma [EMAIL PROTECTED] wrote: This patch implements a new version of RCU which allows its read-side critical sections to be preempted. Why is it selectable if CONFIG_PREEMPT=n? It would probably make sense to make CONFIG_RCU_PREEMPT dependent on CONFIG_PREEMPT. I kept it independent because I wanted to test rcupreempt as an equivalent RCU implementation not just for its preemptibility. It uses a set of counter pairs to keep track of the read-side critical sections and flips them when all tasks exit read-side critical section. The details of this implementation can be found in this paper - http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf This patch was developed as a part of the -rt kernel development and meant to provide better latencies when read-side critical sections of RCU don't disable preemption. Does it succeed in that attempt? Thus far you've given no reason for merging this code.. This is a pile of tricky new core kernel code for us to test, maintain, understand, debug, etc. It needs to provide a substantial benefit. Does it? I am working to compare some latency numbers between different implementations. I will have them out soon. As a consequence of keeping track of RCU readers, the readers have a slight overhead (optimizations in the paper). This implementation co-exists with the classic RCU implementations and can be switched to at compiler. That's yet another question we need to ask people when their kernel dies, and yet another deviation between the kernels which we all test, causing more dilution of testing efforts. It would be much better if we could remove classic RCU. You say this would incur extra cost, but the magnitude of that cost is not clear. Please help us make that decision. See the Table 2, page 10 of the paper mentioned above. There is a ~100ns cost per read-side critical section involved in the preemptible version of RCU at the moment. Until, we are sure that we don't have an impact on common workloads, we need to keep the classic implementation around. Thanks Dipankar - 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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Sat, 27 Jan 2007 02:30:17 +0530 Dipankar Sarma [EMAIL PROTECTED] wrote: As a consequence of keeping track of RCU readers, the readers have a slight overhead (optimizations in the paper). This implementation co-exists with the classic RCU implementations and can be switched to at compiler. That's yet another question we need to ask people when their kernel dies, and yet another deviation between the kernels which we all test, causing more dilution of testing efforts. It would be much better if we could remove classic RCU. You say this would incur extra cost, but the magnitude of that cost is not clear. Please help us make that decision. See the Table 2, page 10 of the paper mentioned above. argh. Seems I have to wade through half the paper to understand Table 2. There is a ~100ns cost per read-side critical section involved in the preemptible version of RCU at the moment. Until, we are sure that we don't have an impact on common workloads, we need to keep the classic implementation around. Ratios, please.. that 100ns appears to be a 100% increase. ie 100ns - 200ns. There are a couple of ways of working out how much that really matters: a) run a workload or b) instrument a kernel, work out how many times/sec the kernel runs rcu_read_lock(). I suspect b) would be more useful and informative. Either way, please always prepare such info up-front and summarise in the changelog? It's kinda important... - 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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Tue, 16 Jan 2007 00:58:58 +0530
Dipankar Sarma <[EMAIL PROTECTED]> wrote:
> +/*
> + * Wait for CPUs to acknowledge the flip.
> + */
> +static int rcu_try_flip_waitack(int flipctr)
> +{
> + int cpu;
> +
> + for_each_possible_cpu(cpu)
> + if (per_cpu(rcu_flip_flag, cpu) != RCU_FLIP_SEEN)
> + return 1;
> +
> + /*
> + * Make sure our checks above don't bleed into subsequent
> + * waiting for the sum of the counters to reach zero.
> + */
> + smp_mb();
> + return 0;
> +}
Confused. If some of the possible cpus aren't online, doesn't the
state machine get stuck??
-
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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Tue, 16 Jan 2007 00:58:58 +0530 Dipankar Sarma <[EMAIL PROTECTED]> wrote: > This patch implements a new version of RCU which allows its read-side > critical sections to be preempted. Why is it selectable if CONFIG_PREEMPT=n? > It uses a set of counter pairs > to keep track of the read-side critical sections and flips them > when all tasks exit read-side critical section. The details > of this implementation can be found in this paper - > > http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf > > This patch was developed as a part of the -rt kernel > development and meant to provide better latencies when > read-side critical sections of RCU don't disable preemption. Does it succeed in that attempt? Thus far you've given no reason for merging this code.. This is a pile of tricky new core kernel code for us to test, maintain, understand, debug, etc. It needs to provide a substantial benefit. Does it? > As a consequence of keeping track of RCU readers, the readers > have a slight overhead (optimizations in the paper). > This implementation co-exists with the "classic" RCU > implementations and can be switched to at compiler. That's yet another question we need to ask people when their kernel dies, and yet another deviation between the kernels which we all test, causing more dilution of testing efforts. It would be much better if we could remove classic RCU. You say this would incur extra cost, but the magnitude of that cost is not clear. Please help us make that decision. - 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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Tue, 16 Jan 2007 00:58:58 +0530 Dipankar Sarma [EMAIL PROTECTED] wrote: This patch implements a new version of RCU which allows its read-side critical sections to be preempted. Why is it selectable if CONFIG_PREEMPT=n? It uses a set of counter pairs to keep track of the read-side critical sections and flips them when all tasks exit read-side critical section. The details of this implementation can be found in this paper - http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf This patch was developed as a part of the -rt kernel development and meant to provide better latencies when read-side critical sections of RCU don't disable preemption. Does it succeed in that attempt? Thus far you've given no reason for merging this code.. This is a pile of tricky new core kernel code for us to test, maintain, understand, debug, etc. It needs to provide a substantial benefit. Does it? As a consequence of keeping track of RCU readers, the readers have a slight overhead (optimizations in the paper). This implementation co-exists with the classic RCU implementations and can be switched to at compiler. That's yet another question we need to ask people when their kernel dies, and yet another deviation between the kernels which we all test, causing more dilution of testing efforts. It would be much better if we could remove classic RCU. You say this would incur extra cost, but the magnitude of that cost is not clear. Please help us make that decision. - 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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
On Tue, 16 Jan 2007 00:58:58 +0530
Dipankar Sarma [EMAIL PROTECTED] wrote:
+/*
+ * Wait for CPUs to acknowledge the flip.
+ */
+static int rcu_try_flip_waitack(int flipctr)
+{
+ int cpu;
+
+ for_each_possible_cpu(cpu)
+ if (per_cpu(rcu_flip_flag, cpu) != RCU_FLIP_SEEN)
+ return 1;
+
+ /*
+ * Make sure our checks above don't bleed into subsequent
+ * waiting for the sum of the counters to reach zero.
+ */
+ smp_mb();
+ return 0;
+}
Confused. If some of the possible cpus aren't online, doesn't the
state machine get stuck??
-
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/
Re: [mm PATCH 4/6] RCU: preemptible RCU
From: Paul McKenney <[EMAIL PROTECTED]> This patch implements a new version of RCU which allows its read-side critical sections to be preempted. It uses a set of counter pairs to keep track of the read-side critical sections and flips them when all tasks exit read-side critical section. The details of this implementation can be found in this paper - http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf This patch was developed as a part of the -rt kernel development and meant to provide better latencies when read-side critical sections of RCU don't disable preemption. As a consequence of keeping track of RCU readers, the readers have a slight overhead (optimizations in the paper). This implementation co-exists with the "classic" RCU implementations and can be switched to at compiler. Signed-off-by: Paul McKenney <[EMAIL PROTECTED]> Signed-off-by: Dipankar Sarma <[EMAIL PROTECTED]> diff -puN include/linux/init_task.h~rcu-preempt include/linux/init_task.h --- linux-2.6.20-rc3-mm1-rcu/include/linux/init_task.h~rcu-preempt 2007-01-15 15:36:51.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/init_task.h 2007-01-15 15:36:51.0 +0530 @@ -90,6 +90,14 @@ extern struct nsproxy init_nsproxy; extern struct group_info init_groups; +#ifdef CONFIG_PREEMPT_RCU +#define INIT_PREEMPT_RCU \ + .rcu_read_lock_nesting = 0, \ + .rcu_flipctr_idx = 0, +#else +#define INIT_PREEMPT_RCU +#endif + /* * INIT_TASK is used to set up the first task table, touch at * your own risk!. Base=0, limit=0x1f (=2MB) @@ -111,6 +119,7 @@ extern struct group_info init_groups; .run_list = LIST_HEAD_INIT(tsk.run_list), \ .ioprio = 0,\ .time_slice = HZ, \ + INIT_PREEMPT_RCU\ .tasks = LIST_HEAD_INIT(tsk.tasks),\ .ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children), \ .ptrace_list= LIST_HEAD_INIT(tsk.ptrace_list), \ diff -puN include/linux/rcuclassic.h~rcu-preempt include/linux/rcuclassic.h --- linux-2.6.20-rc3-mm1-rcu/include/linux/rcuclassic.h~rcu-preempt 2007-01-15 15:36:51.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/rcuclassic.h 2007-01-15 15:36:51.0 +0530 @@ -142,7 +142,6 @@ extern int rcu_needs_cpu(int cpu); extern void __rcu_init(void); extern void rcu_check_callbacks(int cpu, int user); extern void rcu_restart_cpu(int cpu); -extern long rcu_batches_completed(void); #endif /* __KERNEL__ */ #endif /* __LINUX_RCUCLASSIC_H */ diff -puN include/linux/rcupdate.h~rcu-preempt include/linux/rcupdate.h --- linux-2.6.20-rc3-mm1-rcu/include/linux/rcupdate.h~rcu-preempt 2007-01-15 15:36:51.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/rcupdate.h 2007-01-15 15:36:51.0 +0530 @@ -41,7 +41,11 @@ #include #include #include +#ifdef CONFIG_CLASSIC_RCU #include +#else +#include +#endif /** * struct rcu_head - callback structure for use with RCU @@ -216,10 +220,13 @@ extern void FASTCALL(call_rcu_bh(struct /* Exported common interfaces */ extern void synchronize_rcu(void); extern void rcu_barrier(void); +extern long rcu_batches_completed(void); +extern long rcu_batches_completed_bh(void); /* Internal to kernel */ extern void rcu_init(void); extern void rcu_check_callbacks(int cpu, int user); +extern int rcu_needs_cpu(int cpu); #endif /* __KERNEL__ */ #endif /* __LINUX_RCUPDATE_H */ diff -puN /dev/null include/linux/rcupreempt.h --- /dev/null 2006-03-26 18:34:52.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/rcupreempt.h 2007-01-15 15:36:51.0 +0530 @@ -0,0 +1,65 @@ +/* + * Read-Copy Update mechanism for mutual exclusion (RT implementation) + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Copyright IBM Corporation, 2006 + * + * Author: Paul McKenney <[EMAIL PROTECTED]> + * + * Based on the original work by Paul McKenney <[EMAIL PROTECTED]> + * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
Re: [mm PATCH 4/6] RCU: preemptible RCU
From: Paul McKenney [EMAIL PROTECTED] This patch implements a new version of RCU which allows its read-side critical sections to be preempted. It uses a set of counter pairs to keep track of the read-side critical sections and flips them when all tasks exit read-side critical section. The details of this implementation can be found in this paper - http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf This patch was developed as a part of the -rt kernel development and meant to provide better latencies when read-side critical sections of RCU don't disable preemption. As a consequence of keeping track of RCU readers, the readers have a slight overhead (optimizations in the paper). This implementation co-exists with the classic RCU implementations and can be switched to at compiler. Signed-off-by: Paul McKenney [EMAIL PROTECTED] Signed-off-by: Dipankar Sarma [EMAIL PROTECTED] diff -puN include/linux/init_task.h~rcu-preempt include/linux/init_task.h --- linux-2.6.20-rc3-mm1-rcu/include/linux/init_task.h~rcu-preempt 2007-01-15 15:36:51.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/init_task.h 2007-01-15 15:36:51.0 +0530 @@ -90,6 +90,14 @@ extern struct nsproxy init_nsproxy; extern struct group_info init_groups; +#ifdef CONFIG_PREEMPT_RCU +#define INIT_PREEMPT_RCU \ + .rcu_read_lock_nesting = 0, \ + .rcu_flipctr_idx = 0, +#else +#define INIT_PREEMPT_RCU +#endif + /* * INIT_TASK is used to set up the first task table, touch at * your own risk!. Base=0, limit=0x1f (=2MB) @@ -111,6 +119,7 @@ extern struct group_info init_groups; .run_list = LIST_HEAD_INIT(tsk.run_list), \ .ioprio = 0,\ .time_slice = HZ, \ + INIT_PREEMPT_RCU\ .tasks = LIST_HEAD_INIT(tsk.tasks),\ .ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children), \ .ptrace_list= LIST_HEAD_INIT(tsk.ptrace_list), \ diff -puN include/linux/rcuclassic.h~rcu-preempt include/linux/rcuclassic.h --- linux-2.6.20-rc3-mm1-rcu/include/linux/rcuclassic.h~rcu-preempt 2007-01-15 15:36:51.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/rcuclassic.h 2007-01-15 15:36:51.0 +0530 @@ -142,7 +142,6 @@ extern int rcu_needs_cpu(int cpu); extern void __rcu_init(void); extern void rcu_check_callbacks(int cpu, int user); extern void rcu_restart_cpu(int cpu); -extern long rcu_batches_completed(void); #endif /* __KERNEL__ */ #endif /* __LINUX_RCUCLASSIC_H */ diff -puN include/linux/rcupdate.h~rcu-preempt include/linux/rcupdate.h --- linux-2.6.20-rc3-mm1-rcu/include/linux/rcupdate.h~rcu-preempt 2007-01-15 15:36:51.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/rcupdate.h 2007-01-15 15:36:51.0 +0530 @@ -41,7 +41,11 @@ #include linux/percpu.h #include linux/cpumask.h #include linux/seqlock.h +#ifdef CONFIG_CLASSIC_RCU #include linux/rcuclassic.h +#else +#include linux/rcupreempt.h +#endif /** * struct rcu_head - callback structure for use with RCU @@ -216,10 +220,13 @@ extern void FASTCALL(call_rcu_bh(struct /* Exported common interfaces */ extern void synchronize_rcu(void); extern void rcu_barrier(void); +extern long rcu_batches_completed(void); +extern long rcu_batches_completed_bh(void); /* Internal to kernel */ extern void rcu_init(void); extern void rcu_check_callbacks(int cpu, int user); +extern int rcu_needs_cpu(int cpu); #endif /* __KERNEL__ */ #endif /* __LINUX_RCUPDATE_H */ diff -puN /dev/null include/linux/rcupreempt.h --- /dev/null 2006-03-26 18:34:52.0 +0530 +++ linux-2.6.20-rc3-mm1-rcu-dipankar/include/linux/rcupreempt.h 2007-01-15 15:36:51.0 +0530 @@ -0,0 +1,65 @@ +/* + * Read-Copy Update mechanism for mutual exclusion (RT implementation) + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Copyright IBM Corporation, 2006 + * + * Author: Paul McKenney [EMAIL PROTECTED] + * + * Based on the original work by Paul McKenney [EMAIL PROTECTED]
