* [PATCH RFC 0/8] RCU: Preemptible RCU @ 2007-09-05 21:31 Paul E. McKenney 2007-09-05 21:32 ` [PATCH RFC 1/8] RCU: Split API to permit multiple RCU implementations Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:31 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, still not for inclusion. This is a respin of the following prior postings: http://lkml.org/lkml/2007/8/7/276 (the four initial preemptible RCU patches) http://lkml.org/lkml/2007/8/17/262 (hotplug CPU for preemptible RCU) http://lkml.org/lkml/2007/8/22/348 (RCU priority boosting) http://lkml.org/lkml/2007/8/22/373 (rcutorture for RCU priority boosting) This release adds an additional patch that makes the RCU priority booster more friendly to power-savings measures by causing the booster task to sleep if there is no cause to believe that priority boosting will be required in the near future. An additional fixup and documentation patch is forthcoming. And of course, the whole thing will be rebased to a more recent version of Linux. These patches take prior feedback into account, including the bit about running checkpatch.pl. ;-) Thanx, Paul ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 1/8] RCU: Split API to permit multiple RCU implementations 2007-09-05 21:31 [PATCH RFC 0/8] RCU: Preemptible RCU Paul E. McKenney @ 2007-09-05 21:32 ` Paul E. McKenney 2007-09-05 21:33 ` [PATCH RFC 2/8] RCU: Fix barriers Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:32 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. This patch re-organizes the RCU code to enable multiple implementations of RCU. Users of RCU continues to include rcupdate.h and the RCU interfaces remain the same. This is in preparation for subsequently merging the preemptible RCU implementation. Signed-off-by: Dipankar Sarma <dipankar@in.ibm.com> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- include/linux/rcuclassic.h | 149 +++++++++++ include/linux/rcupdate.h | 151 +++--------- kernel/Makefile | 2 kernel/rcuclassic.c | 558 ++++++++++++++++++++++++++++++++++++++++++++ kernel/rcupdate.c | 561 ++------------------------------------------- 5 files changed, 779 insertions(+), 642 deletions(-) diff -urpNa -X dontdiff linux-2.6.22/include/linux/rcuclassic.h linux-2.6.22-a-splitclassic/include/linux/rcuclassic.h --- linux-2.6.22/include/linux/rcuclassic.h 1969-12-31 16:00:00.000000000 -0800 +++ linux-2.6.22-a-splitclassic/include/linux/rcuclassic.h 2007-08-22 14:42:23.000000000 -0700 @@ -0,0 +1,149 @@ +/* + * Read-Copy Update mechanism for mutual exclusion (classic version) + * + * 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, 2001 + * + * Author: Dipankar Sarma <dipankar@in.ibm.com> + * + * Based on the original work by Paul McKenney <paulmck@us.ibm.com> + * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen. + * Papers: + * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf + * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001) + * + * For detailed explanation of Read-Copy Update mechanism see - + * Documentation/RCU + * + */ + +#ifndef __LINUX_RCUCLASSIC_H +#define __LINUX_RCUCLASSIC_H + +#ifdef __KERNEL__ + +#include <linux/cache.h> +#include <linux/spinlock.h> +#include <linux/threads.h> +#include <linux/percpu.h> +#include <linux/cpumask.h> +#include <linux/seqlock.h> + + +/* Global control variables for rcupdate callback mechanism. */ +struct rcu_ctrlblk { + long cur; /* Current batch number. */ + long completed; /* Number of the last completed batch */ + int next_pending; /* Is the next batch already waiting? */ + + int signaled; + + spinlock_t lock ____cacheline_internodealigned_in_smp; + cpumask_t cpumask; /* CPUs that need to switch in order */ + /* for current batch to proceed. */ +} ____cacheline_internodealigned_in_smp; + +/* Is batch a before batch b ? */ +static inline int rcu_batch_before(long a, long b) +{ + return (a - b) < 0; +} + +/* Is batch a after batch b ? */ +static inline int rcu_batch_after(long a, long b) +{ + return (a - b) > 0; +} + +/* + * Per-CPU data for Read-Copy UPdate. + * nxtlist - new callbacks are added here + * curlist - current batch for which quiescent cycle started if any + */ +struct rcu_data { + /* 1) quiescent state handling : */ + long quiescbatch; /* Batch # for grace period */ + int passed_quiesc; /* User-mode/idle loop etc. */ + int qs_pending; /* core waits for quiesc state */ + + /* 2) batch handling */ + long batch; /* Batch # for current RCU batch */ + struct rcu_head *nxtlist; + struct rcu_head **nxttail; + long qlen; /* # of queued callbacks */ + struct rcu_head *curlist; + struct rcu_head **curtail; + struct rcu_head *donelist; + struct rcu_head **donetail; + long blimit; /* Upper limit on a processed batch */ + int cpu; + struct rcu_head barrier; +}; + +DECLARE_PER_CPU(struct rcu_data, rcu_data); +DECLARE_PER_CPU(struct rcu_data, rcu_bh_data); + +/* + * Increment the quiescent state counter. + * The counter is a bit degenerated: We do not need to know + * how many quiescent states passed, just if there was at least + * one since the start of the grace period. Thus just a flag. + */ +static inline void rcu_qsctr_inc(int cpu) +{ + struct rcu_data *rdp = &per_cpu(rcu_data, cpu); + rdp->passed_quiesc = 1; +} +static inline void rcu_bh_qsctr_inc(int cpu) +{ + struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu); + rdp->passed_quiesc = 1; +} + +extern int rcu_pending(int cpu); +extern int rcu_needs_cpu(int cpu); + +#define __rcu_read_lock() \ + do { \ + preempt_disable(); \ + __acquire(RCU); \ + } while (0) +#define __rcu_read_unlock() \ + do { \ + __release(RCU); \ + preempt_enable(); \ + } while (0) +#define __rcu_read_lock_bh() \ + do { \ + local_bh_disable(); \ + __acquire(RCU_BH); \ + } while (0) +#define __rcu_read_unlock_bh() \ + do { \ + __release(RCU_BH); \ + local_bh_enable(); \ + } while (0) + +#define __synchronize_sched() synchronize_rcu() + +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); +extern long rcu_batches_completed_bh(void); + +#endif /* __KERNEL__ */ +#endif /* __LINUX_RCUCLASSIC_H */ diff -urpNa -X dontdiff linux-2.6.22/include/linux/rcupdate.h linux-2.6.22-a-splitclassic/include/linux/rcupdate.h --- linux-2.6.22/include/linux/rcupdate.h 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-a-splitclassic/include/linux/rcupdate.h 2007-07-19 14:02:36.000000000 -0700 @@ -15,7 +15,7 @@ * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * - * Copyright (C) IBM Corporation, 2001 + * Copyright IBM Corporation, 2001 * * Author: Dipankar Sarma <dipankar@in.ibm.com> * @@ -52,6 +52,8 @@ struct rcu_head { void (*func)(struct rcu_head *head); }; +#include <linux/rcuclassic.h> + #define RCU_HEAD_INIT { .next = NULL, .func = NULL } #define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT #define INIT_RCU_HEAD(ptr) do { \ @@ -59,80 +61,6 @@ struct rcu_head { } while (0) - -/* Global control variables for rcupdate callback mechanism. */ -struct rcu_ctrlblk { - long cur; /* Current batch number. */ - long completed; /* Number of the last completed batch */ - int next_pending; /* Is the next batch already waiting? */ - - int signaled; - - spinlock_t lock ____cacheline_internodealigned_in_smp; - cpumask_t cpumask; /* CPUs that need to switch in order */ - /* for current batch to proceed. */ -} ____cacheline_internodealigned_in_smp; - -/* Is batch a before batch b ? */ -static inline int rcu_batch_before(long a, long b) -{ - return (a - b) < 0; -} - -/* Is batch a after batch b ? */ -static inline int rcu_batch_after(long a, long b) -{ - return (a - b) > 0; -} - -/* - * Per-CPU data for Read-Copy UPdate. - * nxtlist - new callbacks are added here - * curlist - current batch for which quiescent cycle started if any - */ -struct rcu_data { - /* 1) quiescent state handling : */ - long quiescbatch; /* Batch # for grace period */ - int passed_quiesc; /* User-mode/idle loop etc. */ - int qs_pending; /* core waits for quiesc state */ - - /* 2) batch handling */ - long batch; /* Batch # for current RCU batch */ - struct rcu_head *nxtlist; - struct rcu_head **nxttail; - long qlen; /* # of queued callbacks */ - struct rcu_head *curlist; - struct rcu_head **curtail; - struct rcu_head *donelist; - struct rcu_head **donetail; - long blimit; /* Upper limit on a processed batch */ - int cpu; - struct rcu_head barrier; -}; - -DECLARE_PER_CPU(struct rcu_data, rcu_data); -DECLARE_PER_CPU(struct rcu_data, rcu_bh_data); - -/* - * Increment the quiescent state counter. - * The counter is a bit degenerated: We do not need to know - * how many quiescent states passed, just if there was at least - * one since the start of the grace period. Thus just a flag. - */ -static inline void rcu_qsctr_inc(int cpu) -{ - struct rcu_data *rdp = &per_cpu(rcu_data, cpu); - rdp->passed_quiesc = 1; -} -static inline void rcu_bh_qsctr_inc(int cpu) -{ - struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu); - rdp->passed_quiesc = 1; -} - -extern int rcu_pending(int cpu); -extern int rcu_needs_cpu(int cpu); - /** * rcu_read_lock - mark the beginning of an RCU read-side critical section. * @@ -162,22 +90,14 @@ extern int rcu_needs_cpu(int cpu); * * It is illegal to block while in an RCU read-side critical section. */ -#define rcu_read_lock() \ - do { \ - preempt_disable(); \ - __acquire(RCU); \ - } while(0) +#define rcu_read_lock() __rcu_read_lock() /** * rcu_read_unlock - marks the end of an RCU read-side critical section. * * See rcu_read_lock() for more information. */ -#define rcu_read_unlock() \ - do { \ - __release(RCU); \ - preempt_enable(); \ - } while(0) +#define rcu_read_unlock() __rcu_read_unlock() /* * So where is rcu_write_lock()? It does not exist, as there is no @@ -200,22 +120,14 @@ extern int rcu_needs_cpu(int cpu); * can use just rcu_read_lock(). * */ -#define rcu_read_lock_bh() \ - do { \ - local_bh_disable(); \ - __acquire(RCU_BH); \ - } while(0) +#define rcu_read_lock_bh() __rcu_read_lock_bh() /* * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section * * See rcu_read_lock_bh() for more information. */ -#define rcu_read_unlock_bh() \ - do { \ - __release(RCU_BH); \ - local_bh_enable(); \ - } while(0) +#define rcu_read_unlock_bh() __rcu_read_unlock_bh() /** * rcu_dereference - fetch an RCU-protected pointer in an @@ -267,22 +179,49 @@ extern int rcu_needs_cpu(int cpu); * In "classic RCU", these two guarantees happen to be one and * the same, but can differ in realtime RCU implementations. */ -#define synchronize_sched() synchronize_rcu() +#define synchronize_sched() __synchronize_sched() -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); -extern long rcu_batches_completed_bh(void); - -/* Exported interfaces */ -extern void FASTCALL(call_rcu(struct rcu_head *head, - void (*func)(struct rcu_head *head))); +/** + * call_rcu - Queue an RCU callback for invocation after a grace period. + * @head: structure to be used for queueing the RCU updates. + * @func: actual update function to be invoked after the grace period + * + * The update function will be invoked some time after a full grace + * period elapses, in other words after all currently executing RCU + * read-side critical sections have completed. RCU read-side critical + * sections are delimited by rcu_read_lock() and rcu_read_unlock(), + * delimited by rcu_read_lock() and rcu_read_unlock(), + * and may be nested. + */ +extern void FASTCALL(call_rcu(struct rcu_head *head, + void (*func)(struct rcu_head *head))); + +/** + * call_rcu_bh - Queue an RCU for invocation after a quicker grace period. + * @head: structure to be used for queueing the RCU updates. + * @func: actual update function to be invoked after the grace period + * + * The update function will be invoked some time after a full grace + * period elapses, in other words after all currently executing RCU + * read-side critical sections have completed. call_rcu_bh() assumes + * that the read-side critical sections end on completion of a softirq + * handler. This means that read-side critical sections in process + * context must not be interrupted by softirqs. This interface is to be + * used when most of the read-side critical sections are in softirq context. + * RCU read-side critical sections are delimited by rcu_read_lock() and + * rcu_read_unlock(), * if in interrupt context or rcu_read_lock_bh() + * and rcu_read_unlock_bh(), if in process context. These may be nested. + */ extern void FASTCALL(call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *head))); + +/* Exported common interfaces */ extern void synchronize_rcu(void); -void synchronize_idle(void); extern void rcu_barrier(void); +/* Internal to kernel */ +extern void rcu_init(void); +extern void rcu_check_callbacks(int cpu, int user); + #endif /* __KERNEL__ */ #endif /* __LINUX_RCUPDATE_H */ diff -urpNa -X dontdiff linux-2.6.22/kernel/Makefile linux-2.6.22-a-splitclassic/kernel/Makefile --- linux-2.6.22/kernel/Makefile 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-a-splitclassic/kernel/Makefile 2007-07-19 12:16:03.000000000 -0700 @@ -6,7 +6,7 @@ obj-y = sched.o fork.o exec_domain.o exit.o itimer.o time.o softirq.o resource.o \ sysctl.o capability.o ptrace.o timer.o user.o \ signal.o sys.o kmod.o workqueue.o pid.o \ - rcupdate.o extable.o params.o posix-timers.o \ + rcupdate.o rcuclassic.o extable.o params.o posix-timers.o \ kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \ hrtimer.o rwsem.o latency.o nsproxy.o srcu.o die_notifier.o diff -urpNa -X dontdiff linux-2.6.22/kernel/rcuclassic.c linux-2.6.22-a-splitclassic/kernel/rcuclassic.c --- linux-2.6.22/kernel/rcuclassic.c 1969-12-31 16:00:00.000000000 -0800 +++ linux-2.6.22-a-splitclassic/kernel/rcuclassic.c 2007-08-22 14:47:13.000000000 -0700 @@ -0,0 +1,558 @@ +/* + * Read-Copy Update mechanism for mutual exclusion + * + * 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, 2001 + * + * Authors: Dipankar Sarma <dipankar@in.ibm.com> + * Manfred Spraul <manfred@colorfullife.com> + * + * Based on the original work by Paul McKenney <paulmck@us.ibm.com> + * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen. + * Papers: + * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf + * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001) + * + * For detailed explanation of Read-Copy Update mechanism see - + * Documentation/RCU + * + */ +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/init.h> +#include <linux/spinlock.h> +#include <linux/smp.h> +#include <linux/rcupdate.h> +#include <linux/interrupt.h> +#include <linux/sched.h> +#include <asm/atomic.h> +#include <linux/bitops.h> +#include <linux/module.h> +#include <linux/completion.h> +#include <linux/moduleparam.h> +#include <linux/percpu.h> +#include <linux/notifier.h> +/* #include <linux/rcupdate.h> @@@ */ +#include <linux/cpu.h> +#include <linux/mutex.h> + +/* Definition for rcupdate control block. */ +static struct rcu_ctrlblk rcu_ctrlblk = { + .cur = -300, + .completed = -300, + .lock = __SPIN_LOCK_UNLOCKED(&rcu_ctrlblk.lock), + .cpumask = CPU_MASK_NONE, +}; +static struct rcu_ctrlblk rcu_bh_ctrlblk = { + .cur = -300, + .completed = -300, + .lock = __SPIN_LOCK_UNLOCKED(&rcu_bh_ctrlblk.lock), + .cpumask = CPU_MASK_NONE, +}; + +DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L }; +DEFINE_PER_CPU(struct rcu_data, rcu_bh_data) = { 0L }; + +/* Fake initialization required by compiler */ +static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL}; +static int blimit = 10; +static int qhimark = 10000; +static int qlowmark = 100; + +#ifdef CONFIG_SMP +static void force_quiescent_state(struct rcu_data *rdp, + struct rcu_ctrlblk *rcp) +{ + int cpu; + cpumask_t cpumask; + set_need_resched(); + if (unlikely(!rcp->signaled)) { + rcp->signaled = 1; + /* + * Don't send IPI to itself. With irqs disabled, + * rdp->cpu is the current cpu. + */ + cpumask = rcp->cpumask; + cpu_clear(rdp->cpu, cpumask); + for_each_cpu_mask(cpu, cpumask) + smp_send_reschedule(cpu); + } +} +#else +static inline void force_quiescent_state(struct rcu_data *rdp, + struct rcu_ctrlblk *rcp) +{ + set_need_resched(); +} +#endif + +/** + * call_rcu - Queue an RCU callback for invocation after a grace period. + * @head: structure to be used for queueing the RCU updates. + * @func: actual update function to be invoked after the grace period + * + * The update function will be invoked some time after a full grace + * period elapses, in other words after all currently executing RCU + * read-side critical sections have completed. RCU read-side critical + * sections are delimited by rcu_read_lock() and rcu_read_unlock(), + * and may be nested. + */ +void fastcall call_rcu(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) +{ + unsigned long flags; + struct rcu_data *rdp; + + head->func = func; + head->next = NULL; + local_irq_save(flags); + rdp = &__get_cpu_var(rcu_data); + *rdp->nxttail = head; + rdp->nxttail = &head->next; + if (unlikely(++rdp->qlen > qhimark)) { + rdp->blimit = INT_MAX; + force_quiescent_state(rdp, &rcu_ctrlblk); + } + local_irq_restore(flags); +} +EXPORT_SYMBOL_GPL(call_rcu); + +/** + * call_rcu_bh - Queue an RCU for invocation after a quicker grace period. + * @head: structure to be used for queueing the RCU updates. + * @func: actual update function to be invoked after the grace period + * + * The update function will be invoked some time after a full grace + * period elapses, in other words after all currently executing RCU + * read-side critical sections have completed. call_rcu_bh() assumes + * that the read-side critical sections end on completion of a softirq + * handler. This means that read-side critical sections in process + * context must not be interrupted by softirqs. This interface is to be + * used when most of the read-side critical sections are in softirq context. + * RCU read-side critical sections are delimited by rcu_read_lock() and + * rcu_read_unlock(), * if in interrupt context or rcu_read_lock_bh() + * and rcu_read_unlock_bh(), if in process context. These may be nested. + */ +void fastcall call_rcu_bh(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) +{ + unsigned long flags; + struct rcu_data *rdp; + + head->func = func; + head->next = NULL; + local_irq_save(flags); + rdp = &__get_cpu_var(rcu_bh_data); + *rdp->nxttail = head; + rdp->nxttail = &head->next; + + if (unlikely(++rdp->qlen > qhimark)) { + rdp->blimit = INT_MAX; + force_quiescent_state(rdp, &rcu_bh_ctrlblk); + } + + local_irq_restore(flags); +} +EXPORT_SYMBOL_GPL(call_rcu_bh); + +/* + * Return the number of RCU batches processed thus far. Useful + * for debug and statistics. + */ +long rcu_batches_completed(void) +{ + return rcu_ctrlblk.completed; +} +EXPORT_SYMBOL_GPL(rcu_batches_completed); + +/* + * Return the number of RCU batches processed thus far. Useful + * for debug and statistics. + */ +long rcu_batches_completed_bh(void) +{ + return rcu_bh_ctrlblk.completed; +} +EXPORT_SYMBOL_GPL(rcu_batches_completed_bh); + +/* + * Invoke the completed RCU callbacks. They are expected to be in + * a per-cpu list. + */ +static void rcu_do_batch(struct rcu_data *rdp) +{ + struct rcu_head *next, *list; + int count = 0; + + list = rdp->donelist; + while (list) { + next = list->next; + prefetch(next); + list->func(list); + list = next; + if (++count >= rdp->blimit) + break; + } + rdp->donelist = list; + + local_irq_disable(); + rdp->qlen -= count; + local_irq_enable(); + if (rdp->blimit == INT_MAX && rdp->qlen <= qlowmark) + rdp->blimit = blimit; + + if (!rdp->donelist) + rdp->donetail = &rdp->donelist; + else + tasklet_schedule(&per_cpu(rcu_tasklet, rdp->cpu)); +} + +/* + * Grace period handling: + * The grace period handling consists out of two steps: + * - A new grace period is started. + * This is done by rcu_start_batch. The start is not broadcasted to + * all cpus, they must pick this up by comparing rcp->cur with + * rdp->quiescbatch. All cpus are recorded in the + * rcu_ctrlblk.cpumask bitmap. + * - All cpus must go through a quiescent state. + * Since the start of the grace period is not broadcasted, at least two + * calls to rcu_check_quiescent_state are required: + * The first call just notices that a new grace period is running. The + * following calls check if there was a quiescent state since the beginning + * of the grace period. If so, it updates rcu_ctrlblk.cpumask. If + * the bitmap is empty, then the grace period is completed. + * rcu_check_quiescent_state calls rcu_start_batch(0) to start the next grace + * period (if necessary). + */ +/* + * Register a new batch of callbacks, and start it up if there is currently no + * active batch and the batch to be registered has not already occurred. + * Caller must hold rcu_ctrlblk.lock. + */ +static void rcu_start_batch(struct rcu_ctrlblk *rcp) +{ + if (rcp->next_pending && + rcp->completed == rcp->cur) { + rcp->next_pending = 0; + /* + * next_pending == 0 must be visible in + * __rcu_process_callbacks() before it can see new value of cur. + */ + smp_wmb(); + rcp->cur++; + + /* + * Accessing nohz_cpu_mask before incrementing rcp->cur needs a + * Barrier Otherwise it can cause tickless idle CPUs to be + * included in rcp->cpumask, which will extend graceperiods + * unnecessarily. + */ + smp_mb(); + cpus_andnot(rcp->cpumask, cpu_online_map, nohz_cpu_mask); + + rcp->signaled = 0; + } +} + +/* + * cpu went through a quiescent state since the beginning of the grace period. + * Clear it from the cpu mask and complete the grace period if it was the last + * cpu. Start another grace period if someone has further entries pending + */ +static void cpu_quiet(int cpu, struct rcu_ctrlblk *rcp) +{ + cpu_clear(cpu, rcp->cpumask); + if (cpus_empty(rcp->cpumask)) { + /* batch completed ! */ + rcp->completed = rcp->cur; + rcu_start_batch(rcp); + } +} + +/* + * Check if the cpu has gone through a quiescent state (say context + * switch). If so and if it already hasn't done so in this RCU + * quiescent cycle, then indicate that it has done so. + */ +static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, + struct rcu_data *rdp) +{ + if (rdp->quiescbatch != rcp->cur) { + /* start new grace period: */ + rdp->qs_pending = 1; + rdp->passed_quiesc = 0; + rdp->quiescbatch = rcp->cur; + return; + } + + /* Grace period already completed for this cpu? + * qs_pending is checked instead of the actual bitmap to avoid + * cacheline trashing. + */ + if (!rdp->qs_pending) + return; + + /* + * Was there a quiescent state since the beginning of the grace + * period? If no, then exit and wait for the next call. + */ + if (!rdp->passed_quiesc) + return; + rdp->qs_pending = 0; + + spin_lock(&rcp->lock); + /* + * rdp->quiescbatch/rcp->cur and the cpu bitmap can come out of sync + * during cpu startup. Ignore the quiescent state. + */ + if (likely(rdp->quiescbatch == rcp->cur)) + cpu_quiet(rdp->cpu, rcp); + + spin_unlock(&rcp->lock); +} + + +#ifdef CONFIG_HOTPLUG_CPU + +/* warning! helper for rcu_offline_cpu. do not use elsewhere without reviewing + * locking requirements, the list it's pulling from has to belong to a cpu + * which is dead and hence not processing interrupts. + */ +static void rcu_move_batch(struct rcu_data *this_rdp, struct rcu_head *list, + struct rcu_head **tail) +{ + local_irq_disable(); + *this_rdp->nxttail = list; + if (list) + this_rdp->nxttail = tail; + local_irq_enable(); +} + +static void __rcu_offline_cpu(struct rcu_data *this_rdp, + struct rcu_ctrlblk *rcp, struct rcu_data *rdp) +{ + /* if the cpu going offline owns the grace period + * we can block indefinitely waiting for it, so flush + * it here + */ + spin_lock_bh(&rcp->lock); + if (rcp->cur != rcp->completed) + cpu_quiet(rdp->cpu, rcp); + spin_unlock_bh(&rcp->lock); + rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail); + rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail); + rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail); +} + +static void rcu_offline_cpu(int cpu) +{ + struct rcu_data *this_rdp = &get_cpu_var(rcu_data); + struct rcu_data *this_bh_rdp = &get_cpu_var(rcu_bh_data); + + __rcu_offline_cpu(this_rdp, &rcu_ctrlblk, + &per_cpu(rcu_data, cpu)); + __rcu_offline_cpu(this_bh_rdp, &rcu_bh_ctrlblk, + &per_cpu(rcu_bh_data, cpu)); + put_cpu_var(rcu_data); + put_cpu_var(rcu_bh_data); + tasklet_kill_immediate(&per_cpu(rcu_tasklet, cpu), cpu); +} + +#else + +static void rcu_offline_cpu(int cpu) +{ +} + +#endif + +/* + * This does the RCU processing work from tasklet context. + */ +static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp, + struct rcu_data *rdp) +{ + if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) { + *rdp->donetail = rdp->curlist; + rdp->donetail = rdp->curtail; + rdp->curlist = NULL; + rdp->curtail = &rdp->curlist; + } + + if (rdp->nxtlist && !rdp->curlist) { + local_irq_disable(); + rdp->curlist = rdp->nxtlist; + rdp->curtail = rdp->nxttail; + rdp->nxtlist = NULL; + rdp->nxttail = &rdp->nxtlist; + local_irq_enable(); + + /* + * start the next batch of callbacks + */ + + /* determine batch number */ + rdp->batch = rcp->cur + 1; + /* see the comment and corresponding wmb() in + * the rcu_start_batch() + */ + smp_rmb(); + + if (!rcp->next_pending) { + /* and start it/schedule start if it's a new batch */ + spin_lock(&rcp->lock); + rcp->next_pending = 1; + rcu_start_batch(rcp); + spin_unlock(&rcp->lock); + } + } + + rcu_check_quiescent_state(rcp, rdp); + if (rdp->donelist) + rcu_do_batch(rdp); +} + +static void rcu_process_callbacks(unsigned long unused) +{ + __rcu_process_callbacks(&rcu_ctrlblk, &__get_cpu_var(rcu_data)); + __rcu_process_callbacks(&rcu_bh_ctrlblk, &__get_cpu_var(rcu_bh_data)); +} + +static int __rcu_pending(struct rcu_ctrlblk *rcp, struct rcu_data *rdp) +{ + /* This cpu has pending rcu entries and the grace period + * for them has completed. + */ + if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) + return 1; + + /* This cpu has no pending entries, but there are new entries */ + if (!rdp->curlist && rdp->nxtlist) + return 1; + + /* This cpu has finished callbacks to invoke */ + if (rdp->donelist) + return 1; + + /* The rcu core waits for a quiescent state from the cpu */ + if (rdp->quiescbatch != rcp->cur || rdp->qs_pending) + return 1; + + /* nothing to do */ + return 0; +} + +/* + * Check to see if there is any immediate RCU-related work to be done + * by the current CPU, returning 1 if so. This function is part of the + * RCU implementation; it is -not- an exported member of the RCU API. + */ +int rcu_pending(int cpu) +{ + return __rcu_pending(&rcu_ctrlblk, &per_cpu(rcu_data, cpu)) || + __rcu_pending(&rcu_bh_ctrlblk, &per_cpu(rcu_bh_data, cpu)); +} + +/* + * Check to see if any future RCU-related work will need to be done + * by the current CPU, even if none need be done immediately, returning + * 1 if so. This function is part of the RCU implementation; it is -not- + * an exported member of the RCU API. + */ +int rcu_needs_cpu(int cpu) +{ + struct rcu_data *rdp = &per_cpu(rcu_data, cpu); + struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu); + + return (!!rdp->curlist || !!rdp_bh->curlist || rcu_pending(cpu)); +} + +void rcu_check_callbacks(int cpu, int user) +{ + if (user || + (idle_cpu(cpu) && !in_softirq() && + hardirq_count() <= (1 << HARDIRQ_SHIFT))) { + rcu_qsctr_inc(cpu); + rcu_bh_qsctr_inc(cpu); + } else if (!in_softirq()) + rcu_bh_qsctr_inc(cpu); + tasklet_schedule(&per_cpu(rcu_tasklet, cpu)); +} + +static void rcu_init_percpu_data(int cpu, struct rcu_ctrlblk *rcp, + struct rcu_data *rdp) +{ + memset(rdp, 0, sizeof(*rdp)); + rdp->curtail = &rdp->curlist; + rdp->nxttail = &rdp->nxtlist; + rdp->donetail = &rdp->donelist; + rdp->quiescbatch = rcp->completed; + rdp->qs_pending = 0; + rdp->cpu = cpu; + rdp->blimit = blimit; +} + +static void __devinit rcu_online_cpu(int cpu) +{ + struct rcu_data *rdp = &per_cpu(rcu_data, cpu); + struct rcu_data *bh_rdp = &per_cpu(rcu_bh_data, cpu); + + rcu_init_percpu_data(cpu, &rcu_ctrlblk, rdp); + rcu_init_percpu_data(cpu, &rcu_bh_ctrlblk, bh_rdp); + tasklet_init(&per_cpu(rcu_tasklet, cpu), rcu_process_callbacks, 0UL); +} + +static int __cpuinit rcu_cpu_notify(struct notifier_block *self, + unsigned long action, void *hcpu) +{ + long cpu = (long)hcpu; + switch (action) { + case CPU_UP_PREPARE: + case CPU_UP_PREPARE_FROZEN: + rcu_online_cpu(cpu); + break; + case CPU_DEAD: + case CPU_DEAD_FROZEN: + rcu_offline_cpu(cpu); + break; + default: + break; + } + return NOTIFY_OK; +} + +static struct notifier_block __cpuinitdata rcu_nb = { + .notifier_call = rcu_cpu_notify, +}; + +/* + * Initializes rcu mechanism. Assumed to be called early. + * That is before local timer(SMP) or jiffie timer (uniproc) is setup. + * Note that rcu_qsctr and friends are implicitly + * initialized due to the choice of ``0'' for RCU_CTR_INVALID. + */ +void __init __rcu_init(void) +{ + rcu_cpu_notify(&rcu_nb, CPU_UP_PREPARE, + (void *)(long)smp_processor_id()); + /* Register notifier for non-boot CPUs */ + register_cpu_notifier(&rcu_nb); +} + +module_param(blimit, int, 0); +module_param(qhimark, int, 0); +module_param(qlowmark, int, 0); diff -urpNa -X dontdiff linux-2.6.22/kernel/rcupdate.c linux-2.6.22-a-splitclassic/kernel/rcupdate.c --- linux-2.6.22/kernel/rcupdate.c 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-a-splitclassic/kernel/rcupdate.c 2007-08-22 14:47:59.000000000 -0700 @@ -15,7 +15,7 @@ * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * - * Copyright (C) IBM Corporation, 2001 + * Copyright IBM Corporation, 2001 * * Authors: Dipankar Sarma <dipankar@in.ibm.com> * Manfred Spraul <manfred@colorfullife.com> @@ -35,164 +35,65 @@ #include <linux/init.h> #include <linux/spinlock.h> #include <linux/smp.h> -#include <linux/rcupdate.h> #include <linux/interrupt.h> #include <linux/sched.h> #include <asm/atomic.h> #include <linux/bitops.h> -#include <linux/module.h> #include <linux/completion.h> -#include <linux/moduleparam.h> #include <linux/percpu.h> #include <linux/notifier.h> #include <linux/rcupdate.h> #include <linux/cpu.h> #include <linux/mutex.h> +#include <linux/module.h> -/* Definition for rcupdate control block. */ -static struct rcu_ctrlblk rcu_ctrlblk = { - .cur = -300, - .completed = -300, - .lock = __SPIN_LOCK_UNLOCKED(&rcu_ctrlblk.lock), - .cpumask = CPU_MASK_NONE, -}; -static struct rcu_ctrlblk rcu_bh_ctrlblk = { - .cur = -300, - .completed = -300, - .lock = __SPIN_LOCK_UNLOCKED(&rcu_bh_ctrlblk.lock), - .cpumask = CPU_MASK_NONE, +struct rcu_synchronize { + struct rcu_head head; + struct completion completion; }; -DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L }; -DEFINE_PER_CPU(struct rcu_data, rcu_bh_data) = { 0L }; - -/* Fake initialization required by compiler */ -static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL}; -static int blimit = 10; -static int qhimark = 10000; -static int qlowmark = 100; - +static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL}; static atomic_t rcu_barrier_cpu_count; static DEFINE_MUTEX(rcu_barrier_mutex); static struct completion rcu_barrier_completion; -#ifdef CONFIG_SMP -static void force_quiescent_state(struct rcu_data *rdp, - struct rcu_ctrlblk *rcp) -{ - int cpu; - cpumask_t cpumask; - set_need_resched(); - if (unlikely(!rcp->signaled)) { - rcp->signaled = 1; - /* - * Don't send IPI to itself. With irqs disabled, - * rdp->cpu is the current cpu. - */ - cpumask = rcp->cpumask; - cpu_clear(rdp->cpu, cpumask); - for_each_cpu_mask(cpu, cpumask) - smp_send_reschedule(cpu); - } -} -#else -static inline void force_quiescent_state(struct rcu_data *rdp, - struct rcu_ctrlblk *rcp) +/* Because of FASTCALL declaration of complete, we use this wrapper */ +static void wakeme_after_rcu(struct rcu_head *head) { - set_need_resched(); + struct rcu_synchronize *rcu; + + rcu = container_of(head, struct rcu_synchronize, head); + complete(&rcu->completion); } -#endif /** - * call_rcu - Queue an RCU callback for invocation after a grace period. - * @head: structure to be used for queueing the RCU updates. - * @func: actual update function to be invoked after the grace period + * synchronize_rcu - wait until a grace period has elapsed. * - * The update function will be invoked some time after a full grace - * period elapses, in other words after all currently executing RCU + * Control will return to the caller some time after a full grace + * period has elapsed, in other words after all currently executing RCU * read-side critical sections have completed. RCU read-side critical * sections are delimited by rcu_read_lock() and rcu_read_unlock(), * and may be nested. */ -void fastcall call_rcu(struct rcu_head *head, - void (*func)(struct rcu_head *rcu)) -{ - unsigned long flags; - struct rcu_data *rdp; - - head->func = func; - head->next = NULL; - local_irq_save(flags); - rdp = &__get_cpu_var(rcu_data); - *rdp->nxttail = head; - rdp->nxttail = &head->next; - if (unlikely(++rdp->qlen > qhimark)) { - rdp->blimit = INT_MAX; - force_quiescent_state(rdp, &rcu_ctrlblk); - } - local_irq_restore(flags); -} - -/** - * call_rcu_bh - Queue an RCU for invocation after a quicker grace period. - * @head: structure to be used for queueing the RCU updates. - * @func: actual update function to be invoked after the grace period - * - * The update function will be invoked some time after a full grace - * period elapses, in other words after all currently executing RCU - * read-side critical sections have completed. call_rcu_bh() assumes - * that the read-side critical sections end on completion of a softirq - * handler. This means that read-side critical sections in process - * context must not be interrupted by softirqs. This interface is to be - * used when most of the read-side critical sections are in softirq context. - * RCU read-side critical sections are delimited by rcu_read_lock() and - * rcu_read_unlock(), * if in interrupt context or rcu_read_lock_bh() - * and rcu_read_unlock_bh(), if in process context. These may be nested. - */ -void fastcall call_rcu_bh(struct rcu_head *head, - void (*func)(struct rcu_head *rcu)) +void synchronize_rcu(void) { - unsigned long flags; - struct rcu_data *rdp; - - head->func = func; - head->next = NULL; - local_irq_save(flags); - rdp = &__get_cpu_var(rcu_bh_data); - *rdp->nxttail = head; - rdp->nxttail = &head->next; - - if (unlikely(++rdp->qlen > qhimark)) { - rdp->blimit = INT_MAX; - force_quiescent_state(rdp, &rcu_bh_ctrlblk); - } - - local_irq_restore(flags); -} + struct rcu_synchronize rcu; -/* - * Return the number of RCU batches processed thus far. Useful - * for debug and statistics. - */ -long rcu_batches_completed(void) -{ - return rcu_ctrlblk.completed; -} + init_completion(&rcu.completion); + /* Will wake me after RCU finished */ + call_rcu(&rcu.head, wakeme_after_rcu); -/* - * Return the number of RCU batches processed thus far. Useful - * for debug and statistics. - */ -long rcu_batches_completed_bh(void) -{ - return rcu_bh_ctrlblk.completed; + /* Wait for it */ + wait_for_completion(&rcu.completion); } +EXPORT_SYMBOL_GPL(synchronize_rcu); static void rcu_barrier_callback(struct rcu_head *notused) { if (atomic_dec_and_test(&rcu_barrier_cpu_count)) complete(&rcu_barrier_completion); } +EXPORT_SYMBOL_GPL(rcu_barrier); /* * Called with preemption disabled, and from cross-cpu IRQ context. @@ -200,10 +101,8 @@ static void rcu_barrier_callback(struct static void rcu_barrier_func(void *notused) { int cpu = smp_processor_id(); - struct rcu_data *rdp = &per_cpu(rcu_data, cpu); - struct rcu_head *head; + struct rcu_head *head = &per_cpu(rcu_barrier_head, cpu); - head = &rdp->barrier; atomic_inc(&rcu_barrier_cpu_count); call_rcu(head, rcu_barrier_callback); } @@ -222,416 +121,8 @@ void rcu_barrier(void) wait_for_completion(&rcu_barrier_completion); mutex_unlock(&rcu_barrier_mutex); } -EXPORT_SYMBOL_GPL(rcu_barrier); - -/* - * Invoke the completed RCU callbacks. They are expected to be in - * a per-cpu list. - */ -static void rcu_do_batch(struct rcu_data *rdp) -{ - struct rcu_head *next, *list; - int count = 0; - - list = rdp->donelist; - while (list) { - next = list->next; - prefetch(next); - list->func(list); - list = next; - if (++count >= rdp->blimit) - break; - } - rdp->donelist = list; - - local_irq_disable(); - rdp->qlen -= count; - local_irq_enable(); - if (rdp->blimit == INT_MAX && rdp->qlen <= qlowmark) - rdp->blimit = blimit; - - if (!rdp->donelist) - rdp->donetail = &rdp->donelist; - else - tasklet_schedule(&per_cpu(rcu_tasklet, rdp->cpu)); -} - -/* - * Grace period handling: - * The grace period handling consists out of two steps: - * - A new grace period is started. - * This is done by rcu_start_batch. The start is not broadcasted to - * all cpus, they must pick this up by comparing rcp->cur with - * rdp->quiescbatch. All cpus are recorded in the - * rcu_ctrlblk.cpumask bitmap. - * - All cpus must go through a quiescent state. - * Since the start of the grace period is not broadcasted, at least two - * calls to rcu_check_quiescent_state are required: - * The first call just notices that a new grace period is running. The - * following calls check if there was a quiescent state since the beginning - * of the grace period. If so, it updates rcu_ctrlblk.cpumask. If - * the bitmap is empty, then the grace period is completed. - * rcu_check_quiescent_state calls rcu_start_batch(0) to start the next grace - * period (if necessary). - */ -/* - * Register a new batch of callbacks, and start it up if there is currently no - * active batch and the batch to be registered has not already occurred. - * Caller must hold rcu_ctrlblk.lock. - */ -static void rcu_start_batch(struct rcu_ctrlblk *rcp) -{ - if (rcp->next_pending && - rcp->completed == rcp->cur) { - rcp->next_pending = 0; - /* - * next_pending == 0 must be visible in - * __rcu_process_callbacks() before it can see new value of cur. - */ - smp_wmb(); - rcp->cur++; - - /* - * Accessing nohz_cpu_mask before incrementing rcp->cur needs a - * Barrier Otherwise it can cause tickless idle CPUs to be - * included in rcp->cpumask, which will extend graceperiods - * unnecessarily. - */ - smp_mb(); - cpus_andnot(rcp->cpumask, cpu_online_map, nohz_cpu_mask); - - rcp->signaled = 0; - } -} - -/* - * cpu went through a quiescent state since the beginning of the grace period. - * Clear it from the cpu mask and complete the grace period if it was the last - * cpu. Start another grace period if someone has further entries pending - */ -static void cpu_quiet(int cpu, struct rcu_ctrlblk *rcp) -{ - cpu_clear(cpu, rcp->cpumask); - if (cpus_empty(rcp->cpumask)) { - /* batch completed ! */ - rcp->completed = rcp->cur; - rcu_start_batch(rcp); - } -} - -/* - * Check if the cpu has gone through a quiescent state (say context - * switch). If so and if it already hasn't done so in this RCU - * quiescent cycle, then indicate that it has done so. - */ -static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, - struct rcu_data *rdp) -{ - if (rdp->quiescbatch != rcp->cur) { - /* start new grace period: */ - rdp->qs_pending = 1; - rdp->passed_quiesc = 0; - rdp->quiescbatch = rcp->cur; - return; - } - - /* Grace period already completed for this cpu? - * qs_pending is checked instead of the actual bitmap to avoid - * cacheline trashing. - */ - if (!rdp->qs_pending) - return; - - /* - * Was there a quiescent state since the beginning of the grace - * period? If no, then exit and wait for the next call. - */ - if (!rdp->passed_quiesc) - return; - rdp->qs_pending = 0; - - spin_lock(&rcp->lock); - /* - * rdp->quiescbatch/rcp->cur and the cpu bitmap can come out of sync - * during cpu startup. Ignore the quiescent state. - */ - if (likely(rdp->quiescbatch == rcp->cur)) - cpu_quiet(rdp->cpu, rcp); - - spin_unlock(&rcp->lock); -} - - -#ifdef CONFIG_HOTPLUG_CPU - -/* warning! helper for rcu_offline_cpu. do not use elsewhere without reviewing - * locking requirements, the list it's pulling from has to belong to a cpu - * which is dead and hence not processing interrupts. - */ -static void rcu_move_batch(struct rcu_data *this_rdp, struct rcu_head *list, - struct rcu_head **tail) -{ - local_irq_disable(); - *this_rdp->nxttail = list; - if (list) - this_rdp->nxttail = tail; - local_irq_enable(); -} - -static void __rcu_offline_cpu(struct rcu_data *this_rdp, - struct rcu_ctrlblk *rcp, struct rcu_data *rdp) -{ - /* if the cpu going offline owns the grace period - * we can block indefinitely waiting for it, so flush - * it here - */ - spin_lock_bh(&rcp->lock); - if (rcp->cur != rcp->completed) - cpu_quiet(rdp->cpu, rcp); - spin_unlock_bh(&rcp->lock); - rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail); - rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail); - rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail); -} - -static void rcu_offline_cpu(int cpu) -{ - struct rcu_data *this_rdp = &get_cpu_var(rcu_data); - struct rcu_data *this_bh_rdp = &get_cpu_var(rcu_bh_data); - - __rcu_offline_cpu(this_rdp, &rcu_ctrlblk, - &per_cpu(rcu_data, cpu)); - __rcu_offline_cpu(this_bh_rdp, &rcu_bh_ctrlblk, - &per_cpu(rcu_bh_data, cpu)); - put_cpu_var(rcu_data); - put_cpu_var(rcu_bh_data); - tasklet_kill_immediate(&per_cpu(rcu_tasklet, cpu), cpu); -} - -#else - -static void rcu_offline_cpu(int cpu) -{ -} - -#endif - -/* - * This does the RCU processing work from tasklet context. - */ -static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp, - struct rcu_data *rdp) -{ - if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) { - *rdp->donetail = rdp->curlist; - rdp->donetail = rdp->curtail; - rdp->curlist = NULL; - rdp->curtail = &rdp->curlist; - } - - if (rdp->nxtlist && !rdp->curlist) { - local_irq_disable(); - rdp->curlist = rdp->nxtlist; - rdp->curtail = rdp->nxttail; - rdp->nxtlist = NULL; - rdp->nxttail = &rdp->nxtlist; - local_irq_enable(); - - /* - * start the next batch of callbacks - */ - - /* determine batch number */ - rdp->batch = rcp->cur + 1; - /* see the comment and corresponding wmb() in - * the rcu_start_batch() - */ - smp_rmb(); - - if (!rcp->next_pending) { - /* and start it/schedule start if it's a new batch */ - spin_lock(&rcp->lock); - rcp->next_pending = 1; - rcu_start_batch(rcp); - spin_unlock(&rcp->lock); - } - } - - rcu_check_quiescent_state(rcp, rdp); - if (rdp->donelist) - rcu_do_batch(rdp); -} - -static void rcu_process_callbacks(unsigned long unused) -{ - __rcu_process_callbacks(&rcu_ctrlblk, &__get_cpu_var(rcu_data)); - __rcu_process_callbacks(&rcu_bh_ctrlblk, &__get_cpu_var(rcu_bh_data)); -} - -static int __rcu_pending(struct rcu_ctrlblk *rcp, struct rcu_data *rdp) -{ - /* This cpu has pending rcu entries and the grace period - * for them has completed. - */ - if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) - return 1; - - /* This cpu has no pending entries, but there are new entries */ - if (!rdp->curlist && rdp->nxtlist) - return 1; - - /* This cpu has finished callbacks to invoke */ - if (rdp->donelist) - return 1; - - /* The rcu core waits for a quiescent state from the cpu */ - if (rdp->quiescbatch != rcp->cur || rdp->qs_pending) - return 1; - - /* nothing to do */ - return 0; -} - -/* - * Check to see if there is any immediate RCU-related work to be done - * by the current CPU, returning 1 if so. This function is part of the - * RCU implementation; it is -not- an exported member of the RCU API. - */ -int rcu_pending(int cpu) -{ - return __rcu_pending(&rcu_ctrlblk, &per_cpu(rcu_data, cpu)) || - __rcu_pending(&rcu_bh_ctrlblk, &per_cpu(rcu_bh_data, cpu)); -} - -/* - * Check to see if any future RCU-related work will need to be done - * by the current CPU, even if none need be done immediately, returning - * 1 if so. This function is part of the RCU implementation; it is -not- - * an exported member of the RCU API. - */ -int rcu_needs_cpu(int cpu) -{ - struct rcu_data *rdp = &per_cpu(rcu_data, cpu); - struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu); - - return (!!rdp->curlist || !!rdp_bh->curlist || rcu_pending(cpu)); -} - -void rcu_check_callbacks(int cpu, int user) -{ - if (user || - (idle_cpu(cpu) && !in_softirq() && - hardirq_count() <= (1 << HARDIRQ_SHIFT))) { - rcu_qsctr_inc(cpu); - rcu_bh_qsctr_inc(cpu); - } else if (!in_softirq()) - rcu_bh_qsctr_inc(cpu); - tasklet_schedule(&per_cpu(rcu_tasklet, cpu)); -} - -static void rcu_init_percpu_data(int cpu, struct rcu_ctrlblk *rcp, - struct rcu_data *rdp) -{ - memset(rdp, 0, sizeof(*rdp)); - rdp->curtail = &rdp->curlist; - rdp->nxttail = &rdp->nxtlist; - rdp->donetail = &rdp->donelist; - rdp->quiescbatch = rcp->completed; - rdp->qs_pending = 0; - rdp->cpu = cpu; - rdp->blimit = blimit; -} - -static void __devinit rcu_online_cpu(int cpu) -{ - struct rcu_data *rdp = &per_cpu(rcu_data, cpu); - struct rcu_data *bh_rdp = &per_cpu(rcu_bh_data, cpu); - - rcu_init_percpu_data(cpu, &rcu_ctrlblk, rdp); - rcu_init_percpu_data(cpu, &rcu_bh_ctrlblk, bh_rdp); - tasklet_init(&per_cpu(rcu_tasklet, cpu), rcu_process_callbacks, 0UL); -} - -static int __cpuinit rcu_cpu_notify(struct notifier_block *self, - unsigned long action, void *hcpu) -{ - long cpu = (long)hcpu; - switch (action) { - case CPU_UP_PREPARE: - case CPU_UP_PREPARE_FROZEN: - rcu_online_cpu(cpu); - break; - case CPU_DEAD: - case CPU_DEAD_FROZEN: - rcu_offline_cpu(cpu); - break; - default: - break; - } - return NOTIFY_OK; -} -static struct notifier_block __cpuinitdata rcu_nb = { - .notifier_call = rcu_cpu_notify, -}; - -/* - * Initializes rcu mechanism. Assumed to be called early. - * That is before local timer(SMP) or jiffie timer (uniproc) is setup. - * Note that rcu_qsctr and friends are implicitly - * initialized due to the choice of ``0'' for RCU_CTR_INVALID. - */ void __init rcu_init(void) { - rcu_cpu_notify(&rcu_nb, CPU_UP_PREPARE, - (void *)(long)smp_processor_id()); - /* Register notifier for non-boot CPUs */ - register_cpu_notifier(&rcu_nb); -} - -struct rcu_synchronize { - struct rcu_head head; - struct completion completion; -}; - -/* Because of FASTCALL declaration of complete, we use this wrapper */ -static void wakeme_after_rcu(struct rcu_head *head) -{ - struct rcu_synchronize *rcu; - - rcu = container_of(head, struct rcu_synchronize, head); - complete(&rcu->completion); -} - -/** - * synchronize_rcu - wait until a grace period has elapsed. - * - * Control will return to the caller some time after a full grace - * period has elapsed, in other words after all currently executing RCU - * read-side critical sections have completed. RCU read-side critical - * sections are delimited by rcu_read_lock() and rcu_read_unlock(), - * and may be nested. - * - * If your read-side code is not protected by rcu_read_lock(), do -not- - * use synchronize_rcu(). - */ -void synchronize_rcu(void) -{ - struct rcu_synchronize rcu; - - init_completion(&rcu.completion); - /* Will wake me after RCU finished */ - call_rcu(&rcu.head, wakeme_after_rcu); - - /* Wait for it */ - wait_for_completion(&rcu.completion); + __rcu_init(); } - -module_param(blimit, int, 0); -module_param(qhimark, int, 0); -module_param(qlowmark, int, 0); -EXPORT_SYMBOL_GPL(rcu_batches_completed); -EXPORT_SYMBOL_GPL(rcu_batches_completed_bh); -EXPORT_SYMBOL_GPL(call_rcu); -EXPORT_SYMBOL_GPL(call_rcu_bh); -EXPORT_SYMBOL_GPL(synchronize_rcu); ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 2/8] RCU: Fix barriers 2007-09-05 21:32 ` [PATCH RFC 1/8] RCU: Split API to permit multiple RCU implementations Paul E. McKenney @ 2007-09-05 21:33 ` Paul E. McKenney 2007-09-05 21:34 ` [PATCH RFC 3/8] RCU: Preemptible RCU Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:33 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. Fix rcu_barrier() to work properly in preemptive kernel environment. Also, the ordering of callback must be preserved while moving callbacks to another CPU during CPU hotplug. Signed-off-by: Dipankar Sarma <dipankar@in.ibm.com> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- rcuclassic.c | 2 +- rcupdate.c | 10 ++++++++++ 2 files changed, 11 insertions(+), 1 deletion(-) diff -urpNa -X dontdiff linux-2.6.22-a-splitclassic/kernel/rcuclassic.c linux-2.6.22-b-fixbarriers/kernel/rcuclassic.c --- linux-2.6.22-a-splitclassic/kernel/rcuclassic.c 2007-07-19 15:03:51.000000000 -0700 +++ linux-2.6.22-b-fixbarriers/kernel/rcuclassic.c 2007-07-19 17:10:46.000000000 -0700 @@ -349,9 +349,9 @@ static void __rcu_offline_cpu(struct rcu if (rcp->cur != rcp->completed) cpu_quiet(rdp->cpu, rcp); spin_unlock_bh(&rcp->lock); + rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail); rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail); rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail); - rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail); } static void rcu_offline_cpu(int cpu) diff -urpNa -X dontdiff linux-2.6.22-a-splitclassic/kernel/rcupdate.c linux-2.6.22-b-fixbarriers/kernel/rcupdate.c --- linux-2.6.22-a-splitclassic/kernel/rcupdate.c 2007-07-19 14:19:03.000000000 -0700 +++ linux-2.6.22-b-fixbarriers/kernel/rcupdate.c 2007-07-19 17:13:31.000000000 -0700 @@ -115,7 +115,17 @@ void rcu_barrier(void) mutex_lock(&rcu_barrier_mutex); init_completion(&rcu_barrier_completion); atomic_set(&rcu_barrier_cpu_count, 0); + /* + * The queueing of callbacks in all CPUs must be atomic with + * respect to RCU, otherwise one CPU may queue a callback, + * wait for a grace period, decrement barrier count and call + * complete(), while other CPUs have not yet queued anything. + * So, we need to make sure that grace periods cannot complete + * until all the callbacks are queued. + */ + rcu_read_lock(); on_each_cpu(rcu_barrier_func, NULL, 0, 1); + rcu_read_unlock(); wait_for_completion(&rcu_barrier_completion); mutex_unlock(&rcu_barrier_mutex); } ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 3/8] RCU: Preemptible RCU 2007-09-05 21:33 ` [PATCH RFC 2/8] RCU: Fix barriers Paul E. McKenney @ 2007-09-05 21:34 ` Paul E. McKenney 2007-09-05 21:36 ` [PATCH RFC 4/8] RCU: synchronize_sched() workaround for CPU hotplug Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:34 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. 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. Also includes RCU tracing summarized in debugfs and RCU_SOFTIRQ for the preemptible variant of RCU. Signed-off-by: Dipankar Sarma <dipankar@in.ibm.com> Signed-off-by: Steven Rostedt <rostedt@goodmis.org> (for RCU_SOFTIRQ) Signed-off-by: Paul McKenney <paulmck@us.ibm.com> --- include/linux/interrupt.h | 1 include/linux/rcuclassic.h | 2 include/linux/rcupdate.h | 7 include/linux/rcupreempt.h | 78 +++ include/linux/rcupreempt_trace.h | 100 +++++ include/linux/sched.h | 5 kernel/Kconfig.preempt | 38 + kernel/Makefile | 7 kernel/fork.c | 4 kernel/rcupreempt.c | 767 +++++++++++++++++++++++++++++++++++++++ kernel/rcupreempt_trace.c | 330 ++++++++++++++++ 11 files changed, 1336 insertions(+), 3 deletions(-) diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/include/linux/interrupt.h linux-2.6.22-c-preemptrcu/include/linux/interrupt.h --- linux-2.6.22-b-fixbarriers/include/linux/interrupt.h 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/include/linux/interrupt.h 2007-08-22 15:21:06.000000000 -0700 @@ -269,6 +269,7 @@ enum #ifdef CONFIG_HIGH_RES_TIMERS HRTIMER_SOFTIRQ, #endif + RCU_SOFTIRQ, /* Preferable RCU should always be the last softirq */ }; /* softirq mask and active fields moved to irq_cpustat_t in diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/include/linux/rcuclassic.h linux-2.6.22-c-preemptrcu/include/linux/rcuclassic.h --- linux-2.6.22-b-fixbarriers/include/linux/rcuclassic.h 2007-08-22 14:42:23.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/include/linux/rcuclassic.h 2007-08-22 15:21:06.000000000 -0700 @@ -142,8 +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); -extern long rcu_batches_completed_bh(void); #endif /* __KERNEL__ */ #endif /* __LINUX_RCUCLASSIC_H */ diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/include/linux/rcupdate.h linux-2.6.22-c-preemptrcu/include/linux/rcupdate.h --- linux-2.6.22-b-fixbarriers/include/linux/rcupdate.h 2007-07-19 14:02:36.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/include/linux/rcupdate.h 2007-08-22 15:21:06.000000000 -0700 @@ -52,7 +52,11 @@ struct rcu_head { void (*func)(struct rcu_head *head); }; +#ifdef CONFIG_CLASSIC_RCU #include <linux/rcuclassic.h> +#else /* #ifdef CONFIG_CLASSIC_RCU */ +#include <linux/rcupreempt.h> +#endif /* #else #ifdef CONFIG_CLASSIC_RCU */ #define RCU_HEAD_INIT { .next = NULL, .func = NULL } #define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT @@ -218,10 +222,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 -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/include/linux/rcupreempt.h linux-2.6.22-c-preemptrcu/include/linux/rcupreempt.h --- linux-2.6.22-b-fixbarriers/include/linux/rcupreempt.h 1969-12-31 16:00:00.000000000 -0800 +++ linux-2.6.22-c-preemptrcu/include/linux/rcupreempt.h 2007-08-22 15:21:06.000000000 -0700 @@ -0,0 +1,78 @@ +/* + * 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 (C) IBM Corporation, 2006 + * + * Author: Paul McKenney <paulmck@us.ibm.com> + * + * Based on the original work by Paul McKenney <paul.mckenney@us.ibm.com> + * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen. + * Papers: + * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf + * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001) + * + * For detailed explanation of Read-Copy Update mechanism see - + * Documentation/RCU + * + */ + +#ifndef __LINUX_RCUPREEMPT_H +#define __LINUX_RCUPREEMPT_H + +#ifdef __KERNEL__ + +#include <linux/cache.h> +#include <linux/spinlock.h> +#include <linux/threads.h> +#include <linux/percpu.h> +#include <linux/cpumask.h> +#include <linux/seqlock.h> + +#define rcu_qsctr_inc(cpu) +#define rcu_bh_qsctr_inc(cpu) +#define call_rcu_bh(head, rcu) call_rcu(head, rcu) + +extern void __rcu_read_lock(void); +extern void __rcu_read_unlock(void); +extern int rcu_pending(int cpu); +extern int rcu_needs_cpu(int cpu); + +#define __rcu_read_lock_bh() { rcu_read_lock(); local_bh_disable(); } +#define __rcu_read_unlock_bh() { local_bh_enable(); rcu_read_unlock(); } + +#define __rcu_read_lock_nesting() (current->rcu_read_lock_nesting) + +extern void __synchronize_sched(void); + +extern void __rcu_init(void); +extern void rcu_check_callbacks(int cpu, int user); +extern void rcu_restart_cpu(int cpu); + +#ifdef CONFIG_RCU_TRACE +struct rcupreempt_trace; +extern int *rcupreempt_flipctr(int cpu); +extern long rcupreempt_data_completed(void); +extern int rcupreempt_flip_flag(int cpu); +extern int rcupreempt_mb_flag(int cpu); +extern char *rcupreempt_try_flip_state_name(void); +extern struct rcupreempt_trace *rcupreempt_trace_cpu(int cpu); +#endif + +struct softirq_action; + +#endif /* __KERNEL__ */ +#endif /* __LINUX_RCUPREEMPT_H */ diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/include/linux/rcupreempt_trace.h linux-2.6.22-c-preemptrcu/include/linux/rcupreempt_trace.h --- linux-2.6.22-b-fixbarriers/include/linux/rcupreempt_trace.h 1969-12-31 16:00:00.000000000 -0800 +++ linux-2.6.22-c-preemptrcu/include/linux/rcupreempt_trace.h 2007-08-22 15:21:06.000000000 -0700 @@ -0,0 +1,100 @@ +/* + * 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 (C) IBM Corporation, 2006 + * + * Author: Paul McKenney <paulmck@us.ibm.com> + * + * Based on the original work by Paul McKenney <paul.mckenney@us.ibm.com> + * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen. + * Papers: + * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf + * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001) + * + * For detailed explanation of Read-Copy Update mechanism see - + * http://lse.sourceforge.net/locking/rcupdate.html + * + */ + +#ifndef __LINUX_RCUPREEMPT_TRACE_H +#define __LINUX_RCUPREEMPT_TRACE_H + +#ifdef __KERNEL__ +#include <linux/types.h> +#include <linux/kernel.h> + +#include <asm/atomic.h> + +/* + * PREEMPT_RCU data structures. + */ + +struct rcupreempt_trace { + long next_length; + long next_add; + long wait_length; + long wait_add; + long done_length; + long done_add; + long done_remove; + atomic_t done_invoked; + long rcu_check_callbacks; + atomic_t rcu_try_flip_1; + atomic_t rcu_try_flip_e1; + long rcu_try_flip_i1; + long rcu_try_flip_ie1; + long rcu_try_flip_g1; + long rcu_try_flip_a1; + long rcu_try_flip_ae1; + long rcu_try_flip_a2; + long rcu_try_flip_z1; + long rcu_try_flip_ze1; + long rcu_try_flip_z2; + long rcu_try_flip_m1; + long rcu_try_flip_me1; + long rcu_try_flip_m2; +}; + +#ifdef CONFIG_RCU_TRACE +#define RCU_TRACE(fn, arg) fn(arg); +#else +#define RCU_TRACE(fn, arg) +#endif + +extern void rcupreempt_trace_move2done(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_move2wait(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_e1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_i1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_ie1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_g1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_a1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_ae1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_a2(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_z1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_ze1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_z2(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_m1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_me1(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_try_flip_m2(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_check_callbacks(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_done_remove(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_invoke(struct rcupreempt_trace *trace); +extern void rcupreempt_trace_next_add(struct rcupreempt_trace *trace); + +#endif /* __KERNEL__ */ +#endif /* __LINUX_RCUPREEMPT_TRACE_H */ diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/include/linux/sched.h linux-2.6.22-c-preemptrcu/include/linux/sched.h --- linux-2.6.22-b-fixbarriers/include/linux/sched.h 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/include/linux/sched.h 2007-08-22 15:21:06.000000000 -0700 @@ -850,6 +850,11 @@ struct task_struct { cpumask_t cpus_allowed; unsigned int time_slice, first_time_slice; +#ifdef CONFIG_PREEMPT_RCU + int rcu_read_lock_nesting; + int rcu_flipctr_idx; +#endif /* #ifdef CONFIG_PREEMPT_RCU */ + #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) struct sched_info sched_info; #endif diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/kernel/fork.c linux-2.6.22-c-preemptrcu/kernel/fork.c --- linux-2.6.22-b-fixbarriers/kernel/fork.c 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/kernel/fork.c 2007-08-22 15:21:06.000000000 -0700 @@ -1032,6 +1032,10 @@ static struct task_struct *copy_process( INIT_LIST_HEAD(&p->children); INIT_LIST_HEAD(&p->sibling); +#ifdef CONFIG_PREEMPT_RCU + p->rcu_read_lock_nesting = 0; + p->rcu_flipctr_idx = 0; +#endif /* #ifdef CONFIG_PREEMPT_RCU */ p->vfork_done = NULL; spin_lock_init(&p->alloc_lock); diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/kernel/Kconfig.preempt linux-2.6.22-c-preemptrcu/kernel/Kconfig.preempt --- linux-2.6.22-b-fixbarriers/kernel/Kconfig.preempt 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/kernel/Kconfig.preempt 2007-08-22 15:21:06.000000000 -0700 @@ -63,3 +63,41 @@ config PREEMPT_BKL Say Y here if you are building a kernel for a desktop system. Say N if you are unsure. +choice + prompt "RCU implementation type:" + default CLASSIC_RCU + +config CLASSIC_RCU + bool "Classic RCU" + help + This option selects the classic RCU implementation that is + designed for best read-side performance on non-realtime + systems. + + Say Y if you are unsure. + +config PREEMPT_RCU + bool "Preemptible RCU" + depends on PREEMPT + help + This option reduces the latency of the kernel by making certain + RCU sections preemptible. Normally RCU code is non-preemptible, if + this option is selected then read-only RCU sections become + preemptible. This helps latency, but may expose bugs due to + now-naive assumptions about each RCU read-side critical section + remaining on a given CPU through its execution. + + Say N if you are unsure. + +endchoice + +config RCU_TRACE + bool "Enable tracing for RCU - currently stats in debugfs" + select DEBUG_FS + default y + help + This option provides tracing in RCU which presents stats + in debugfs for debugging RCU implementation. + + Say Y here if you want to enable RCU tracing + Say N if you are unsure. diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/kernel/Makefile linux-2.6.22-c-preemptrcu/kernel/Makefile --- linux-2.6.22-b-fixbarriers/kernel/Makefile 2007-07-19 12:16:03.000000000 -0700 +++ linux-2.6.22-c-preemptrcu/kernel/Makefile 2007-08-22 15:21:06.000000000 -0700 @@ -6,7 +6,7 @@ obj-y = sched.o fork.o exec_domain.o exit.o itimer.o time.o softirq.o resource.o \ sysctl.o capability.o ptrace.o timer.o user.o \ signal.o sys.o kmod.o workqueue.o pid.o \ - rcupdate.o rcuclassic.o extable.o params.o posix-timers.o \ + rcupdate.o extable.o params.o posix-timers.o \ kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \ hrtimer.o rwsem.o latency.o nsproxy.o srcu.o die_notifier.o @@ -46,6 +46,11 @@ obj-$(CONFIG_DETECT_SOFTLOCKUP) += softl obj-$(CONFIG_GENERIC_HARDIRQS) += irq/ obj-$(CONFIG_SECCOMP) += seccomp.o obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o +obj-$(CONFIG_CLASSIC_RCU) += rcuclassic.o +obj-$(CONFIG_PREEMPT_RCU) += rcupreempt.o +ifeq ($(CONFIG_PREEMPT_RCU),y) +obj-$(CONFIG_RCU_TRACE) += rcupreempt_trace.o +endif obj-$(CONFIG_RELAY) += relay.o obj-$(CONFIG_SYSCTL) += utsname_sysctl.o obj-$(CONFIG_UTS_NS) += utsname.o diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/kernel/rcupreempt.c linux-2.6.22-c-preemptrcu/kernel/rcupreempt.c --- linux-2.6.22-b-fixbarriers/kernel/rcupreempt.c 1969-12-31 16:00:00.000000000 -0800 +++ linux-2.6.22-c-preemptrcu/kernel/rcupreempt.c 2007-08-22 15:35:19.000000000 -0700 @@ -0,0 +1,767 @@ +/* + * Read-Copy Update mechanism for mutual exclusion, realtime 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 + * + * Authors: Paul E. McKenney <paulmck@us.ibm.com> + * With thanks to Esben Nielsen, Bill Huey, and Ingo Molnar + * for pushing me away from locks and towards counters, and + * to Suparna Bhattacharya for pushing me completely away + * from atomic instructions on the read side. + * + * Papers: http://www.rdrop.com/users/paulmck/RCU + * + * For detailed explanation of Read-Copy Update mechanism see - + * Documentation/RCU/ *.txt + * + */ +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/init.h> +#include <linux/spinlock.h> +#include <linux/smp.h> +#include <linux/rcupdate.h> +#include <linux/interrupt.h> +#include <linux/sched.h> +#include <asm/atomic.h> +#include <linux/bitops.h> +#include <linux/module.h> +#include <linux/completion.h> +#include <linux/moduleparam.h> +#include <linux/percpu.h> +#include <linux/notifier.h> +#include <linux/rcupdate.h> +#include <linux/cpu.h> +#include <linux/random.h> +#include <linux/delay.h> +#include <linux/byteorder/swabb.h> +#include <linux/cpumask.h> +#include <linux/rcupreempt_trace.h> + +/* + * PREEMPT_RCU data structures. + */ + +#define GP_STAGES 4 +struct rcu_data { + spinlock_t lock; /* Protect rcu_data fields. */ + long completed; /* Number of last completed batch. */ + int waitlistcount; + struct tasklet_struct rcu_tasklet; + struct rcu_head *nextlist; + struct rcu_head **nexttail; + struct rcu_head *waitlist[GP_STAGES]; + struct rcu_head **waittail[GP_STAGES]; + struct rcu_head *donelist; + struct rcu_head **donetail; +#ifdef CONFIG_RCU_TRACE + struct rcupreempt_trace trace; +#endif /* #ifdef CONFIG_RCU_TRACE */ +}; +struct rcu_ctrlblk { + spinlock_t fliplock; /* Protect state-machine transitions. */ + long completed; /* Number of last completed batch. */ +}; +static DEFINE_PER_CPU(struct rcu_data, rcu_data); +static struct rcu_ctrlblk rcu_ctrlblk = { + .fliplock = SPIN_LOCK_UNLOCKED, + .completed = 0, +}; +static DEFINE_PER_CPU(int [2], rcu_flipctr) = { 0, 0 }; + +/* + * States for rcu_try_flip() and friends. + */ + +enum rcu_try_flip_states { + rcu_try_flip_idle_state, /* "I" */ + rcu_try_flip_waitack_state, /* "A" */ + rcu_try_flip_waitzero_state, /* "Z" */ + rcu_try_flip_waitmb_state /* "M" */ +}; +static enum rcu_try_flip_states rcu_try_flip_state = rcu_try_flip_idle_state; +#ifdef CONFIG_RCU_TRACE +static char *rcu_try_flip_state_names[] = + { "idle", "waitack", "waitzero", "waitmb" }; +#endif /* #ifdef CONFIG_RCU_TRACE */ + +/* + * Enum and per-CPU flag to determine when each CPU has seen + * the most recent counter flip. + */ + +enum rcu_flip_flag_values { + rcu_flip_seen, /* Steady/initial state, last flip seen. */ + /* Only GP detector can update. */ + rcu_flipped /* Flip just completed, need confirmation. */ + /* Only corresponding CPU can update. */ +}; +static DEFINE_PER_CPU(enum rcu_flip_flag_values, rcu_flip_flag) = rcu_flip_seen; + +/* + * Enum and per-CPU flag to determine when each CPU has executed the + * needed memory barrier to fence in memory references from its last RCU + * read-side critical section in the just-completed grace period. + */ + +enum rcu_mb_flag_values { + rcu_mb_done, /* Steady/initial state, no mb()s required. */ + /* Only GP detector can update. */ + rcu_mb_needed /* Flip just completed, need an mb(). */ + /* Only corresponding CPU can update. */ +}; +static DEFINE_PER_CPU(enum rcu_mb_flag_values, rcu_mb_flag) = rcu_mb_done; + +/* + * Macro that prevents the compiler from reordering accesses, but does + * absolutely -nothing- to prevent CPUs from reordering. This is used + * only to mediate communication between mainline code and hardware + * interrupt and NMI handlers. + */ +#define ORDERED_WRT_IRQ(x) (*(volatile typeof(x) *)&(x)) + +/* + * RCU_DATA_ME: find the current CPU's rcu_data structure. + * RCU_DATA_CPU: find the specified CPU's rcu_data structure. + */ +#define RCU_DATA_ME() (&__get_cpu_var(rcu_data)) +#define RCU_DATA_CPU(cpu) (&per_cpu(rcu_data, cpu)) + +/* + * Helper macro for tracing when the appropriate rcu_data is not + * cached in a local variable, but where the CPU number is so cached. + */ +#define RCU_TRACE_CPU(f, cpu) RCU_TRACE(f, &(RCU_DATA_CPU(cpu)->trace)); + +/* + * Helper macro for tracing when the appropriate rcu_data is not + * cached in a local variable. + */ +#define RCU_TRACE_ME(f) RCU_TRACE(f, &(RCU_DATA_ME()->trace)); + +/* + * Helper macro for tracing when the appropriate rcu_data is pointed + * to by a local variable. + */ +#define RCU_TRACE_RDP(f, rdp) RCU_TRACE(f, &((rdp)->trace)); + +/* + * Return the number of RCU batches processed thus far. Useful + * for debug and statistics. + */ +long rcu_batches_completed(void) +{ + return rcu_ctrlblk.completed; +} +EXPORT_SYMBOL_GPL(rcu_batches_completed); + +/* + * Return the number of RCU batches processed thus far. Useful for debug + * and statistics. The _bh variant is identical to straight RCU. + */ +long rcu_batches_completed_bh(void) +{ + return rcu_ctrlblk.completed; +} +EXPORT_SYMBOL_GPL(rcu_batches_completed_bh); + +void __rcu_read_lock(void) +{ + int idx; + struct task_struct *me = current; + int nesting; + + nesting = ORDERED_WRT_IRQ(me->rcu_read_lock_nesting); + if (nesting != 0) { + + /* An earlier rcu_read_lock() covers us, just count it. */ + + me->rcu_read_lock_nesting = nesting + 1; + + } else { + unsigned long oldirq; + + /* + * Disable local interrupts to prevent the grace-period + * detection state machine from seeing us half-done. + * NMIs can still occur, of course, and might themselves + * contain rcu_read_lock(). + */ + + local_irq_save(oldirq); + + /* + * Outermost nesting of rcu_read_lock(), so increment + * the current counter for the current CPU. Use volatile + * casts to prevent the compiler from reordering. + */ + + idx = ORDERED_WRT_IRQ(rcu_ctrlblk.completed) & 0x1; + smp_read_barrier_depends(); /* @@@@ might be unneeded */ + ORDERED_WRT_IRQ(__get_cpu_var(rcu_flipctr)[idx])++; + + /* + * Now that the per-CPU counter has been incremented, we + * are protected from races with rcu_read_lock() invoked + * from NMI handlers on this CPU. We can therefore safely + * increment the nesting counter, relieving further NMIs + * of the need to increment the per-CPU counter. + */ + + ORDERED_WRT_IRQ(me->rcu_read_lock_nesting) = nesting + 1; + + /* + * Now that we have preventing any NMIs from storing + * to the ->rcu_flipctr_idx, we can safely use it to + * remember which counter to decrement in the matching + * rcu_read_unlock(). + */ + + ORDERED_WRT_IRQ(me->rcu_flipctr_idx) = idx; + local_irq_restore(oldirq); + } +} +EXPORT_SYMBOL_GPL(__rcu_read_lock); + +void __rcu_read_unlock(void) +{ + int idx; + struct task_struct *me = current; + int nesting; + + nesting = ORDERED_WRT_IRQ(me->rcu_read_lock_nesting); + if (nesting > 1) { + + /* + * We are still protected by the enclosing rcu_read_lock(), + * so simply decrement the counter. + */ + + me->rcu_read_lock_nesting = nesting - 1; + + } else { + unsigned long oldirq; + + /* + * Disable local interrupts to prevent the grace-period + * detection state machine from seeing us half-done. + * NMIs can still occur, of course, and might themselves + * contain rcu_read_lock() and rcu_read_unlock(). + */ + + local_irq_save(oldirq); + + /* + * Outermost nesting of rcu_read_unlock(), so we must + * decrement the current counter for the current CPU. + * This must be done carefully, because NMIs can + * occur at any point in this code, and any rcu_read_lock() + * and rcu_read_unlock() pairs in the NMI handlers + * must interact non-destructively with this code. + * Lots of volatile casts, and -very- careful ordering. + * + * Changes to this code, including this one, must be + * inspected, validated, and tested extremely carefully!!! + */ + + /* + * First, pick up the index. Enforce ordering for + * DEC Alpha. + */ + + idx = ORDERED_WRT_IRQ(me->rcu_flipctr_idx); + smp_read_barrier_depends(); /* @@@ Needed??? */ + + /* + * Now that we have fetched the counter index, it is + * safe to decrement the per-task RCU nesting counter. + * After this, any interrupts or NMIs will increment and + * decrement the per-CPU counters. + */ + ORDERED_WRT_IRQ(me->rcu_read_lock_nesting) = nesting - 1; + + /* + * It is now safe to decrement this task's nesting count. + * NMIs that occur after this statement will route their + * rcu_read_lock() calls through this "else" clause, and + * will thus start incrementing the per-CPU coutner on + * their own. They will also clobber ->rcu_flipctr_idx, + * but that is OK, since we have already fetched it. + */ + + ORDERED_WRT_IRQ(__get_cpu_var(rcu_flipctr)[idx])--; + local_irq_restore(oldirq); + } +} +EXPORT_SYMBOL_GPL(__rcu_read_unlock); + +/* + * If a global counter flip has occurred since the last time that we + * advanced callbacks, advance them. Hardware interrupts must be + * disabled when calling this function. + */ +static void __rcu_advance_callbacks(struct rcu_data *rdp) +{ + int cpu; + int i; + int wlc = 0; + + if (rdp->completed != rcu_ctrlblk.completed) { + if (rdp->waitlist[GP_STAGES - 1] != NULL) { + *rdp->donetail = rdp->waitlist[GP_STAGES - 1]; + rdp->donetail = rdp->waittail[GP_STAGES - 1]; + RCU_TRACE_RDP(rcupreempt_trace_move2done, rdp); + } + for (i = GP_STAGES - 2; i >= 0; i--) { + if (rdp->waitlist[i] != NULL) { + rdp->waitlist[i + 1] = rdp->waitlist[i]; + rdp->waittail[i + 1] = rdp->waittail[i]; + wlc++; + } else { + rdp->waitlist[i + 1] = NULL; + rdp->waittail[i + 1] = + &rdp->waitlist[i + 1]; + } + } + if (rdp->nextlist != NULL) { + rdp->waitlist[0] = rdp->nextlist; + rdp->waittail[0] = rdp->nexttail; + wlc++; + rdp->nextlist = NULL; + rdp->nexttail = &rdp->nextlist; + RCU_TRACE_RDP(rcupreempt_trace_move2wait, rdp); + } else { + rdp->waitlist[0] = NULL; + rdp->waittail[0] = &rdp->waitlist[0]; + } + rdp->waitlistcount = wlc; + rdp->completed = rcu_ctrlblk.completed; + } + + /* + * Check to see if this CPU needs to report that it has seen + * the most recent counter flip, thereby declaring that all + * subsequent rcu_read_lock() invocations will respect this flip. + */ + + cpu = raw_smp_processor_id(); + if (per_cpu(rcu_flip_flag, cpu) == rcu_flipped) { + smp_mb(); /* Subsequent counter accesses must see new value */ + per_cpu(rcu_flip_flag, cpu) = rcu_flip_seen; + smp_mb(); /* Subsequent RCU read-side critical sections */ + /* seen -after- acknowledgement. */ + } +} + +/* + * Get here when RCU is idle. Decide whether we need to + * move out of idle state, and return non-zero if so. + * "Straightforward" approach for the moment, might later + * use callback-list lengths, grace-period duration, or + * some such to determine when to exit idle state. + * Might also need a pre-idle test that does not acquire + * the lock, but let's get the simple case working first... + */ + +static int +rcu_try_flip_idle(void) +{ + int cpu; + + RCU_TRACE_ME(rcupreempt_trace_try_flip_i1); + if (!rcu_pending(smp_processor_id())) { + RCU_TRACE_ME(rcupreempt_trace_try_flip_ie1); + return 0; + } + + /* + * Do the flip. + */ + + RCU_TRACE_ME(rcupreempt_trace_try_flip_g1); + rcu_ctrlblk.completed++; /* stands in for rcu_try_flip_g2 */ + + /* + * Need a memory barrier so that other CPUs see the new + * counter value before they see the subsequent change of all + * the rcu_flip_flag instances to rcu_flipped. + */ + + smp_mb(); /* see above block comment. */ + + /* Now ask each CPU for acknowledgement of the flip. */ + + for_each_possible_cpu(cpu) + per_cpu(rcu_flip_flag, cpu) = rcu_flipped; + + return 1; +} + +/* + * Wait for CPUs to acknowledge the flip. + */ + +static int +rcu_try_flip_waitack(void) +{ + int cpu; + + RCU_TRACE_ME(rcupreempt_trace_try_flip_a1); + for_each_possible_cpu(cpu) + if (per_cpu(rcu_flip_flag, cpu) != rcu_flip_seen) { + RCU_TRACE_ME(rcupreempt_trace_try_flip_ae1); + return 0; + } + + /* + * Make sure our checks above don't bleed into subsequent + * waiting for the sum of the counters to reach zero. + */ + + smp_mb(); /* see above block comment. */ + RCU_TRACE_ME(rcupreempt_trace_try_flip_a2); + return 1; +} + +/* + * Wait for collective ``last'' counter to reach zero, + * then tell all CPUs to do an end-of-grace-period memory barrier. + */ + +static int +rcu_try_flip_waitzero(void) +{ + int cpu; + int lastidx = !(rcu_ctrlblk.completed & 0x1); + int sum = 0; + + /* Check to see if the sum of the "last" counters is zero. */ + + RCU_TRACE_ME(rcupreempt_trace_try_flip_z1); + for_each_possible_cpu(cpu) + sum += per_cpu(rcu_flipctr, cpu)[lastidx]; + if (sum != 0) { + RCU_TRACE_ME(rcupreempt_trace_try_flip_ze1); + return 0; + } + + smp_mb(); /* Don't call for memory barriers before we see zero. */ + + /* Call for a memory barrier from each CPU. */ + + for_each_possible_cpu(cpu) + per_cpu(rcu_mb_flag, cpu) = rcu_mb_needed; + + RCU_TRACE_ME(rcupreempt_trace_try_flip_z2); + return 1; +} + +/* + * Wait for all CPUs to do their end-of-grace-period memory barrier. + * Return 0 once all CPUs have done so. + */ + +static int +rcu_try_flip_waitmb(void) +{ + int cpu; + + RCU_TRACE_ME(rcupreempt_trace_try_flip_m1); + for_each_possible_cpu(cpu) + if (per_cpu(rcu_mb_flag, cpu) != rcu_mb_done) { + RCU_TRACE_ME(rcupreempt_trace_try_flip_me1); + return 0; + } + + smp_mb(); /* Ensure that the above checks precede any following flip. */ + RCU_TRACE_ME(rcupreempt_trace_try_flip_m2); + return 1; +} + +/* + * Attempt a single flip of the counters. Remember, a single flip does + * -not- constitute a grace period. Instead, the interval between + * at least three consecutive flips is a grace period. + * + * If anyone is nuts enough to run this CONFIG_PREEMPT_RCU implementation + * on a large SMP, they might want to use a hierarchical organization of + * the per-CPU-counter pairs. + */ +static void rcu_try_flip(void) +{ + unsigned long oldirq; + + RCU_TRACE_ME(rcupreempt_trace_try_flip_1); + if (unlikely(!spin_trylock_irqsave(&rcu_ctrlblk.fliplock, oldirq))) { + RCU_TRACE_ME(rcupreempt_trace_try_flip_e1); + return; + } + + /* + * Take the next transition(s) through the RCU grace-period + * flip-counter state machine. + */ + + switch (rcu_try_flip_state) { + case rcu_try_flip_idle_state: + if (rcu_try_flip_idle()) + rcu_try_flip_state = rcu_try_flip_waitack_state; + break; + case rcu_try_flip_waitack_state: + if (rcu_try_flip_waitack()) + rcu_try_flip_state = rcu_try_flip_waitzero_state; + break; + case rcu_try_flip_waitzero_state: + if (rcu_try_flip_waitzero()) + rcu_try_flip_state = rcu_try_flip_waitmb_state; + break; + case rcu_try_flip_waitmb_state: + if (rcu_try_flip_waitmb()) + rcu_try_flip_state = rcu_try_flip_idle_state; + } + spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, oldirq); +} + +/* + * Check to see if this CPU needs to do a memory barrier in order to + * ensure that any prior RCU read-side critical sections have committed + * their counter manipulations and critical-section memory references + * before declaring the grace period to be completed. + */ +static void rcu_check_mb(int cpu) +{ + if (per_cpu(rcu_mb_flag, cpu) == rcu_mb_needed) { + smp_mb(); /* Ensure RCU read-side accesses are visible. */ + per_cpu(rcu_mb_flag, cpu) = rcu_mb_done; + } +} + +void rcu_check_callbacks(int cpu, int user) +{ + unsigned long oldirq; + struct rcu_data *rdp = RCU_DATA_CPU(cpu); + + rcu_check_mb(cpu); + if (rcu_ctrlblk.completed == rdp->completed) + rcu_try_flip(); + spin_lock_irqsave(&rdp->lock, oldirq); + RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp); + __rcu_advance_callbacks(rdp); + if (rdp->donelist == NULL) { + spin_unlock_irqrestore(&rdp->lock, oldirq); + } else { + spin_unlock_irqrestore(&rdp->lock, oldirq); + raise_softirq(RCU_SOFTIRQ); + } +} + +/* + * Needed by dynticks, to make sure all RCU processing has finished + * when we go idle: + */ +void rcu_advance_callbacks(int cpu, int user) +{ + unsigned long oldirq; + struct rcu_data *rdp = RCU_DATA_CPU(cpu); + + if (rcu_ctrlblk.completed == rdp->completed) { + rcu_try_flip(); + if (rcu_ctrlblk.completed == rdp->completed) + return; + } + spin_lock_irqsave(&rdp->lock, oldirq); + RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp); + __rcu_advance_callbacks(rdp); + spin_unlock_irqrestore(&rdp->lock, oldirq); +} + +static void rcu_process_callbacks(struct softirq_action *unused) +{ + unsigned long flags; + struct rcu_head *next, *list; + struct rcu_data *rdp = RCU_DATA_ME(); + + spin_lock_irqsave(&rdp->lock, flags); + list = rdp->donelist; + if (list == NULL) { + spin_unlock_irqrestore(&rdp->lock, flags); + return; + } + rdp->donelist = NULL; + rdp->donetail = &rdp->donelist; + RCU_TRACE_RDP(rcupreempt_trace_done_remove, rdp); + spin_unlock_irqrestore(&rdp->lock, flags); + while (list) { + next = list->next; + list->func(list); + list = next; + RCU_TRACE_ME(rcupreempt_trace_invoke); + } +} + +void fastcall call_rcu(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) +{ + unsigned long oldirq; + struct rcu_data *rdp; + + head->func = func; + head->next = NULL; + local_irq_save(oldirq); + rdp = RCU_DATA_ME(); + spin_lock(&rdp->lock); + __rcu_advance_callbacks(rdp); + *rdp->nexttail = head; + rdp->nexttail = &head->next; + RCU_TRACE_RDP(rcupreempt_trace_next_add, rdp); + spin_unlock(&rdp->lock); + local_irq_restore(oldirq); +} +EXPORT_SYMBOL_GPL(call_rcu); + +/* + * Wait until all currently running preempt_disable() code segments + * (including hardware-irq-disable segments) complete. Note that + * in -rt this does -not- necessarily result in all currently executing + * interrupt -handlers- having completed. + */ +void __synchronize_sched(void) +{ + cpumask_t oldmask; + int cpu; + + if (sched_getaffinity(0, &oldmask) < 0) + oldmask = cpu_possible_map; + for_each_online_cpu(cpu) { + sched_setaffinity(0, cpumask_of_cpu(cpu)); + schedule(); + } + sched_setaffinity(0, oldmask); +} +EXPORT_SYMBOL_GPL(__synchronize_sched); + +/* + * Check to see if any future RCU-related work will need to be done + * by the current CPU, even if none need be done immediately, returning + * 1 if so. Assumes that notifiers would take care of handling any + * outstanding requests from the RCU core. + * + * This function is part of the RCU implementation; it is -not- + * an exported member of the RCU API. + */ +int rcu_needs_cpu(int cpu) +{ + struct rcu_data *rdp = RCU_DATA_CPU(cpu); + + return (rdp->donelist != NULL || + !!rdp->waitlistcount || + rdp->nextlist != NULL); +} + +int rcu_pending(int cpu) +{ + struct rcu_data *rdp = RCU_DATA_CPU(cpu); + + /* The CPU has at least one callback queued somewhere. */ + + if (rdp->donelist != NULL || + !!rdp->waitlistcount || + rdp->nextlist != NULL) + return 1; + + /* The RCU core needs an acknowledgement from this CPU. */ + + if ((per_cpu(rcu_flip_flag, cpu) == rcu_flipped) || + (per_cpu(rcu_mb_flag, cpu) == rcu_mb_needed)) + return 1; + + /* This CPU has fallen behind the global grace-period number. */ + + if (rdp->completed != rcu_ctrlblk.completed) + return 1; + + /* Nothing needed from this CPU. */ + + return 0; +} + +void __init __rcu_init(void) +{ + int cpu; + int i; + struct rcu_data *rdp; + +/*&&&&*/printk(KERN_NOTICE "WARNING: experimental RCU implementation.\n"); + for_each_possible_cpu(cpu) { + rdp = RCU_DATA_CPU(cpu); + spin_lock_init(&rdp->lock); + rdp->completed = 0; + rdp->waitlistcount = 0; + rdp->nextlist = NULL; + rdp->nexttail = &rdp->nextlist; + for (i = 0; i < GP_STAGES; i++) { + rdp->waitlist[i] = NULL; + rdp->waittail[i] = &rdp->waitlist[i]; + } + rdp->donelist = NULL; + rdp->donetail = &rdp->donelist; + } + open_softirq(RCU_SOFTIRQ, rcu_process_callbacks, NULL); +} + +/* + * Deprecated, use synchronize_rcu() or synchronize_sched() instead. + */ +void synchronize_kernel(void) +{ + synchronize_rcu(); +} + +#ifdef CONFIG_RCU_TRACE +int *rcupreempt_flipctr(int cpu) +{ + return &per_cpu(rcu_flipctr, cpu)[0]; +} +EXPORT_SYMBOL_GPL(rcupreempt_flipctr); + +int rcupreempt_flip_flag(int cpu) +{ + return per_cpu(rcu_flip_flag, cpu); +} +EXPORT_SYMBOL_GPL(rcupreempt_flip_flag); + +int rcupreempt_mb_flag(int cpu) +{ + return per_cpu(rcu_mb_flag, cpu); +} +EXPORT_SYMBOL_GPL(rcupreempt_mb_flag); + +char *rcupreempt_try_flip_state_name(void) +{ + return rcu_try_flip_state_names[rcu_try_flip_state]; +} +EXPORT_SYMBOL_GPL(rcupreempt_try_flip_state_name); + +struct rcupreempt_trace *rcupreempt_trace_cpu(int cpu) +{ + struct rcu_data *rdp = RCU_DATA_CPU(cpu); + + return &rdp->trace; +} +EXPORT_SYMBOL_GPL(rcupreempt_trace_cpu); + +#endif /* #ifdef RCU_TRACE */ diff -urpNa -X dontdiff linux-2.6.22-b-fixbarriers/kernel/rcupreempt_trace.c linux-2.6.22-c-preemptrcu/kernel/rcupreempt_trace.c --- linux-2.6.22-b-fixbarriers/kernel/rcupreempt_trace.c 1969-12-31 16:00:00.000000000 -0800 +++ linux-2.6.22-c-preemptrcu/kernel/rcupreempt_trace.c 2007-08-22 15:36:12.000000000 -0700 @@ -0,0 +1,330 @@ +/* + * Read-Copy Update tracing for realtime 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 + * + * Papers: http://www.rdrop.com/users/paulmck/RCU + * + * For detailed explanation of Read-Copy Update mechanism see - + * Documentation/RCU/ *.txt + * + */ +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/init.h> +#include <linux/spinlock.h> +#include <linux/smp.h> +#include <linux/rcupdate.h> +#include <linux/interrupt.h> +#include <linux/sched.h> +#include <asm/atomic.h> +#include <linux/bitops.h> +#include <linux/module.h> +#include <linux/completion.h> +#include <linux/moduleparam.h> +#include <linux/percpu.h> +#include <linux/notifier.h> +#include <linux/rcupdate.h> +#include <linux/cpu.h> +#include <linux/mutex.h> +#include <linux/rcupreempt_trace.h> +#include <linux/debugfs.h> + +static struct mutex rcupreempt_trace_mutex; +static char *rcupreempt_trace_buf; +#define RCUPREEMPT_TRACE_BUF_SIZE 4096 + +void rcupreempt_trace_move2done(struct rcupreempt_trace *trace) +{ + trace->done_length += trace->wait_length; + trace->done_add += trace->wait_length; + trace->wait_length = 0; +} +void rcupreempt_trace_move2wait(struct rcupreempt_trace *trace) +{ + trace->wait_length += trace->next_length; + trace->wait_add += trace->next_length; + trace->next_length = 0; +} +void rcupreempt_trace_try_flip_1(struct rcupreempt_trace *trace) +{ + atomic_inc(&trace->rcu_try_flip_1); +} +void rcupreempt_trace_try_flip_e1(struct rcupreempt_trace *trace) +{ + atomic_inc(&trace->rcu_try_flip_e1); +} +void rcupreempt_trace_try_flip_i1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_i1++; +} +void rcupreempt_trace_try_flip_ie1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_ie1++; +} +void rcupreempt_trace_try_flip_g1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_g1++; +} +void rcupreempt_trace_try_flip_a1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_a1++; +} +void rcupreempt_trace_try_flip_ae1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_ae1++; +} +void rcupreempt_trace_try_flip_a2(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_a2++; +} +void rcupreempt_trace_try_flip_z1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_z1++; +} +void rcupreempt_trace_try_flip_ze1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_ze1++; +} +void rcupreempt_trace_try_flip_z2(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_z2++; +} +void rcupreempt_trace_try_flip_m1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_m1++; +} +void rcupreempt_trace_try_flip_me1(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_me1++; +} +void rcupreempt_trace_try_flip_m2(struct rcupreempt_trace *trace) +{ + trace->rcu_try_flip_m2++; +} +void rcupreempt_trace_check_callbacks(struct rcupreempt_trace *trace) +{ + trace->rcu_check_callbacks++; +} +void rcupreempt_trace_done_remove(struct rcupreempt_trace *trace) +{ + trace->done_remove += trace->done_length; + trace->done_length = 0; +} +void rcupreempt_trace_invoke(struct rcupreempt_trace *trace) +{ + atomic_inc(&trace->done_invoked); +} +void rcupreempt_trace_next_add(struct rcupreempt_trace *trace) +{ + trace->next_add++; + trace->next_length++; +} + +static void rcupreempt_trace_sum(struct rcupreempt_trace *sp) +{ + struct rcupreempt_trace *cp; + int cpu; + + memset(sp, 0, sizeof(*sp)); + for_each_possible_cpu(cpu) { + cp = rcupreempt_trace_cpu(cpu); + sp->next_length += cp->next_length; + sp->next_add += cp->next_add; + sp->wait_length += cp->wait_length; + sp->wait_add += cp->wait_add; + sp->done_length += cp->done_length; + sp->done_add += cp->done_add; + sp->done_remove += cp->done_remove; + atomic_set(&sp->done_invoked, atomic_read(&cp->done_invoked)); + sp->rcu_check_callbacks += cp->rcu_check_callbacks; + atomic_set(&sp->rcu_try_flip_1, + atomic_read(&cp->rcu_try_flip_1)); + atomic_set(&sp->rcu_try_flip_e1, + atomic_read(&cp->rcu_try_flip_e1)); + sp->rcu_try_flip_i1 += cp->rcu_try_flip_i1; + sp->rcu_try_flip_ie1 += cp->rcu_try_flip_ie1; + sp->rcu_try_flip_g1 += cp->rcu_try_flip_g1; + sp->rcu_try_flip_a1 += cp->rcu_try_flip_a1; + sp->rcu_try_flip_ae1 += cp->rcu_try_flip_ae1; + sp->rcu_try_flip_a2 += cp->rcu_try_flip_a2; + sp->rcu_try_flip_z1 += cp->rcu_try_flip_z1; + sp->rcu_try_flip_ze1 += cp->rcu_try_flip_ze1; + sp->rcu_try_flip_z2 += cp->rcu_try_flip_z2; + sp->rcu_try_flip_m1 += cp->rcu_try_flip_m1; + sp->rcu_try_flip_me1 += cp->rcu_try_flip_me1; + sp->rcu_try_flip_m2 += cp->rcu_try_flip_m2; + } +} + +static ssize_t rcustats_read(struct file *filp, char __user *buffer, + size_t count, loff_t *ppos) +{ + struct rcupreempt_trace trace; + ssize_t bcount; + int cnt = 0; + + rcupreempt_trace_sum(&trace); + mutex_lock(&rcupreempt_trace_mutex); + snprintf(&rcupreempt_trace_buf[cnt], RCUPREEMPT_TRACE_BUF_SIZE - cnt, + "ggp=%ld rcc=%ld\n", + rcu_batches_completed(), + trace.rcu_check_callbacks); + snprintf(&rcupreempt_trace_buf[cnt], RCUPREEMPT_TRACE_BUF_SIZE - cnt, + "na=%ld nl=%ld wa=%ld wl=%ld da=%ld dl=%ld dr=%ld di=%d\n" + "1=%d e1=%d i1=%ld ie1=%ld g1=%ld a1=%ld ae1=%ld a2=%ld\n" + "z1=%ld ze1=%ld z2=%ld m1=%ld me1=%ld m2=%ld\n", + + trace.next_add, trace.next_length, + trace.wait_add, trace.wait_length, + trace.done_add, trace.done_length, + trace.done_remove, atomic_read(&trace.done_invoked), + atomic_read(&trace.rcu_try_flip_1), + atomic_read(&trace.rcu_try_flip_e1), + trace.rcu_try_flip_i1, trace.rcu_try_flip_ie1, + trace.rcu_try_flip_g1, + trace.rcu_try_flip_a1, trace.rcu_try_flip_ae1, + trace.rcu_try_flip_a2, + trace.rcu_try_flip_z1, trace.rcu_try_flip_ze1, + trace.rcu_try_flip_z2, + trace.rcu_try_flip_m1, trace.rcu_try_flip_me1, + trace.rcu_try_flip_m2); + bcount = simple_read_from_buffer(buffer, count, ppos, + rcupreempt_trace_buf, strlen(rcupreempt_trace_buf)); + mutex_unlock(&rcupreempt_trace_mutex); + return bcount; +} + +static ssize_t rcugp_read(struct file *filp, char __user *buffer, + size_t count, loff_t *ppos) +{ + long oldgp = rcu_batches_completed(); + ssize_t bcount; + + mutex_lock(&rcupreempt_trace_mutex); + synchronize_rcu(); + snprintf(rcupreempt_trace_buf, RCUPREEMPT_TRACE_BUF_SIZE, + "oldggp=%ld newggp=%ld\n", oldgp, rcu_batches_completed()); + bcount = simple_read_from_buffer(buffer, count, ppos, + rcupreempt_trace_buf, strlen(rcupreempt_trace_buf)); + mutex_unlock(&rcupreempt_trace_mutex); + return bcount; +} + +static ssize_t rcuctrs_read(struct file *filp, char __user *buffer, + size_t count, loff_t *ppos) +{ + int cnt = 0; + int cpu; + int f = rcu_batches_completed() & 0x1; + ssize_t bcount; + + mutex_lock(&rcupreempt_trace_mutex); + + cnt += snprintf(&rcupreempt_trace_buf[cnt], RCUPREEMPT_TRACE_BUF_SIZE, + "CPU last cur F M\n"); + for_each_online_cpu(cpu) { + int *flipctr = rcupreempt_flipctr(cpu); + cnt += snprintf(&rcupreempt_trace_buf[cnt], + RCUPREEMPT_TRACE_BUF_SIZE - cnt, + "%3d %4d %3d %d %d\n", + cpu, + flipctr[!f], + flipctr[f], + rcupreempt_flip_flag(cpu), + rcupreempt_mb_flag(cpu)); + } + cnt += snprintf(&rcupreempt_trace_buf[cnt], + RCUPREEMPT_TRACE_BUF_SIZE - cnt, + "ggp = %ld, state = %s\n", + rcu_batches_completed(), + rcupreempt_try_flip_state_name()); + cnt += snprintf(&rcupreempt_trace_buf[cnt], + RCUPREEMPT_TRACE_BUF_SIZE - cnt, + "\n"); + bcount = simple_read_from_buffer(buffer, count, ppos, + rcupreempt_trace_buf, strlen(rcupreempt_trace_buf)); + mutex_unlock(&rcupreempt_trace_mutex); + return bcount; +} + +static struct file_operations rcustats_fops = { + .owner = THIS_MODULE, + .read = rcustats_read, +}; + +static struct file_operations rcugp_fops = { + .owner = THIS_MODULE, + .read = rcugp_read, +}; + +static struct file_operations rcuctrs_fops = { + .owner = THIS_MODULE, + .read = rcuctrs_read, +}; + +static struct dentry *rcudir, *statdir, *ctrsdir, *gpdir; +static int rcupreempt_debugfs_init(void) +{ + rcudir = debugfs_create_dir("rcu", NULL); + if (!rcudir) + goto out; + statdir = debugfs_create_file("rcustats", 0444, rcudir, + NULL, &rcustats_fops); + if (!statdir) + goto free_out; + + gpdir = debugfs_create_file("rcugp", 0444, rcudir, NULL, &rcugp_fops); + if (!gpdir) + goto free_out; + + ctrsdir = debugfs_create_file("rcuctrs", 0444, rcudir, + NULL, &rcuctrs_fops); + if (!ctrsdir) + goto free_out; + return 0; +free_out: + if (statdir) + debugfs_remove(statdir); + if (gpdir) + debugfs_remove(gpdir); + debugfs_remove(rcudir); +out: + return 1; +} + +static int __init rcupreempt_trace_init(void) +{ + mutex_init(&rcupreempt_trace_mutex); + rcupreempt_trace_buf = kmalloc(RCUPREEMPT_TRACE_BUF_SIZE, GFP_KERNEL); + if (!rcupreempt_trace_buf) + return 1; + return rcupreempt_debugfs_init(); +} + +static void __exit rcupreempt_trace_cleanup(void) +{ + debugfs_remove(statdir); + debugfs_remove(gpdir); + debugfs_remove(ctrsdir); + debugfs_remove(rcudir); + kfree(rcupreempt_trace_buf); +} + + +module_init(rcupreempt_trace_init); +module_exit(rcupreempt_trace_cleanup); ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 4/8] RCU: synchronize_sched() workaround for CPU hotplug 2007-09-05 21:34 ` [PATCH RFC 3/8] RCU: Preemptible RCU Paul E. McKenney @ 2007-09-05 21:36 ` Paul E. McKenney 2007-09-05 21:37 ` [PATCH RFC 5/8] RCU: CPU hotplug support for preemptible RCU Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:36 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. The combination of CPU hotplug and PREEMPT_RCU has resulted in deadlocks due to the migration-based implementation of synchronize_sched() in -rt. This experimental patch maps synchronize_sched() back onto Classic RCU, eliminating the migration, thus hopefully also eliminating the deadlocks. It is not clear that this is a good long-term approach, but it will at least permit people doing CPU hotplug in -rt kernels additional wiggle room in their design and implementation. The basic approach is to cause the -rt kernel to incorporate rcuclassic.c as well as rcupreempt.c, but to #ifdef out the conflicting portions of rcuclassic.c so that only the code needed to implement synchronize_sched() remains in a PREEMPT_RT build. Invocations of grace-period detection from the scheduling-clock interrupt go to rcuclassic.c, which then invokes the corresponding functions in rcupreempt.c (with _rt suffix added to keep the linker happy). Also applies the RCU_SOFTIRQ to classic RCU. The bulk of this patch just moves code around, but likely increases scheduling-clock latency. If this patch does turn out to be the right approach, the #ifdefs in kernel/rcuclassic.c might be dealt with. ;-) At current writing, Gautham Shenoy's most recent CPU-hotplug fixes seem likely to obsolete this patch (which would be a very good thing indeed!). Signed-off-by: Steven Rostedt <rostedt@goodmis.org> (for RCU_SOFTIRQ) Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- include/linux/rcuclassic.h | 79 +++++-------------------------------- include/linux/rcupdate.h | 30 ++++++++++++-- include/linux/rcupreempt.h | 27 ++++++------ kernel/Makefile | 2 kernel/rcuclassic.c | 95 ++++++++++++++++++++++++++++++++++++--------- kernel/rcupdate.c | 22 ++++++++-- kernel/rcupreempt.c | 50 +++++------------------ 7 files changed, 158 insertions(+), 147 deletions(-) diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/include/linux/rcuclassic.h linux-2.6.22-d-schedclassic/include/linux/rcuclassic.h --- linux-2.6.22-c-preemptrcu/include/linux/rcuclassic.h 2007-08-22 15:21:06.000000000 -0700 +++ linux-2.6.22-d-schedclassic/include/linux/rcuclassic.h 2007-08-22 17:49:35.000000000 -0700 @@ -42,80 +42,19 @@ #include <linux/cpumask.h> #include <linux/seqlock.h> - -/* Global control variables for rcupdate callback mechanism. */ -struct rcu_ctrlblk { - long cur; /* Current batch number. */ - long completed; /* Number of the last completed batch */ - int next_pending; /* Is the next batch already waiting? */ - - int signaled; - - spinlock_t lock ____cacheline_internodealigned_in_smp; - cpumask_t cpumask; /* CPUs that need to switch in order */ - /* for current batch to proceed. */ -} ____cacheline_internodealigned_in_smp; - -/* Is batch a before batch b ? */ -static inline int rcu_batch_before(long a, long b) -{ - return (a - b) < 0; -} - -/* Is batch a after batch b ? */ -static inline int rcu_batch_after(long a, long b) -{ - return (a - b) > 0; -} +DECLARE_PER_CPU(int, rcu_data_bh_passed_quiesc); /* - * Per-CPU data for Read-Copy UPdate. - * nxtlist - new callbacks are added here - * curlist - current batch for which quiescent cycle started if any - */ -struct rcu_data { - /* 1) quiescent state handling : */ - long quiescbatch; /* Batch # for grace period */ - int passed_quiesc; /* User-mode/idle loop etc. */ - int qs_pending; /* core waits for quiesc state */ - - /* 2) batch handling */ - long batch; /* Batch # for current RCU batch */ - struct rcu_head *nxtlist; - struct rcu_head **nxttail; - long qlen; /* # of queued callbacks */ - struct rcu_head *curlist; - struct rcu_head **curtail; - struct rcu_head *donelist; - struct rcu_head **donetail; - long blimit; /* Upper limit on a processed batch */ - int cpu; - struct rcu_head barrier; -}; - -DECLARE_PER_CPU(struct rcu_data, rcu_data); -DECLARE_PER_CPU(struct rcu_data, rcu_bh_data); - -/* - * Increment the quiescent state counter. + * Increment the bottom-half quiescent state counter. * The counter is a bit degenerated: We do not need to know * how many quiescent states passed, just if there was at least * one since the start of the grace period. Thus just a flag. */ -static inline void rcu_qsctr_inc(int cpu) -{ - struct rcu_data *rdp = &per_cpu(rcu_data, cpu); - rdp->passed_quiesc = 1; -} static inline void rcu_bh_qsctr_inc(int cpu) { - struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu); - rdp->passed_quiesc = 1; + per_cpu(rcu_data_bh_passed_quiesc, cpu) = 1; } -extern int rcu_pending(int cpu); -extern int rcu_needs_cpu(int cpu); - #define __rcu_read_lock() \ do { \ preempt_disable(); \ @@ -139,9 +78,15 @@ extern int rcu_needs_cpu(int cpu); #define __synchronize_sched() synchronize_rcu() -extern void __rcu_init(void); -extern void rcu_check_callbacks(int cpu, int user); -extern void rcu_restart_cpu(int cpu); +#define rcu_advance_callbacks_rt(cpu, user) do { } while (0) +#define rcu_check_callbacks_rt(cpu, user) do { } while (0) +#define rcu_init_rt() do { } while (0) +#define rcu_needs_cpu_rt(cpu) 0 +#define rcu_pending_rt(cpu) 0 +#define rcu_process_callbacks_rt(unused) do { } while (0) + +extern void FASTCALL(call_rcu_classic(struct rcu_head *head, + void (*func)(struct rcu_head *head))); #endif /* __KERNEL__ */ #endif /* __LINUX_RCUCLASSIC_H */ diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/include/linux/rcupdate.h linux-2.6.22-d-schedclassic/include/linux/rcupdate.h --- linux-2.6.22-c-preemptrcu/include/linux/rcupdate.h 2007-08-22 15:21:06.000000000 -0700 +++ linux-2.6.22-d-schedclassic/include/linux/rcupdate.h 2007-08-22 15:38:22.000000000 -0700 @@ -197,8 +197,11 @@ struct rcu_head { * delimited by rcu_read_lock() and rcu_read_unlock(), * and may be nested. */ -extern void FASTCALL(call_rcu(struct rcu_head *head, - void (*func)(struct rcu_head *head))); +#ifdef CONFIG_CLASSIC_RCU +#define call_rcu(head, func) call_rcu_classic(head, func) +#else /* #ifdef CONFIG_CLASSIC_RCU */ +#define call_rcu(head, func) call_rcu_preempt(head, func) +#endif /* #else #ifdef CONFIG_CLASSIC_RCU */ /** * call_rcu_bh - Queue an RCU for invocation after a quicker grace period. @@ -226,9 +229,28 @@ 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); +extern long rcu_batches_completed(void); +extern long rcu_batches_completed_bh(void); +extern void rcu_check_callbacks(int cpu, int user); +extern void rcu_init(void); +extern int rcu_needs_cpu(int cpu); +extern int rcu_pending(int cpu); +struct softirq_action; +extern void rcu_restart_cpu(int cpu); + +DECLARE_PER_CPU(int, rcu_data_passed_quiesc); + +/* + * Increment the quiescent state counter. + * The counter is a bit degenerated: We do not need to know + * how many quiescent states passed, just if there was at least + * one since the start of the grace period. Thus just a flag. + */ +static inline void rcu_qsctr_inc(int cpu) +{ + per_cpu(rcu_data_passed_quiesc, cpu) = 1; +} #endif /* __KERNEL__ */ #endif /* __LINUX_RCUPDATE_H */ diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/include/linux/rcupreempt.h linux-2.6.22-d-schedclassic/include/linux/rcupreempt.h --- linux-2.6.22-c-preemptrcu/include/linux/rcupreempt.h 2007-08-22 15:21:06.000000000 -0700 +++ linux-2.6.22-d-schedclassic/include/linux/rcupreempt.h 2007-08-22 17:53:25.000000000 -0700 @@ -42,25 +42,26 @@ #include <linux/cpumask.h> #include <linux/seqlock.h> -#define rcu_qsctr_inc(cpu) -#define rcu_bh_qsctr_inc(cpu) #define call_rcu_bh(head, rcu) call_rcu(head, rcu) - -extern void __rcu_read_lock(void); -extern void __rcu_read_unlock(void); -extern int rcu_pending(int cpu); -extern int rcu_needs_cpu(int cpu); - +#define rcu_bh_qsctr_inc(cpu) do { } while (0) #define __rcu_read_lock_bh() { rcu_read_lock(); local_bh_disable(); } #define __rcu_read_unlock_bh() { local_bh_enable(); rcu_read_unlock(); } - #define __rcu_read_lock_nesting() (current->rcu_read_lock_nesting) +extern void FASTCALL(call_rcu_classic(struct rcu_head *head, + void (*func)(struct rcu_head *head))); +extern void FASTCALL(call_rcu_preempt(struct rcu_head *head, + void (*func)(struct rcu_head *head))); +extern void __rcu_read_lock(void); +extern void __rcu_read_unlock(void); extern void __synchronize_sched(void); - -extern void __rcu_init(void); -extern void rcu_check_callbacks(int cpu, int user); -extern void rcu_restart_cpu(int cpu); +extern void rcu_advance_callbacks_rt(int cpu, int user); +extern void rcu_check_callbacks_rt(int cpu, int user); +extern void rcu_init_rt(void); +extern int rcu_needs_cpu_rt(int cpu); +extern int rcu_pending_rt(int cpu); +struct softirq_action; +extern void rcu_process_callbacks_rt(struct softirq_action *unused); #ifdef CONFIG_RCU_TRACE struct rcupreempt_trace; diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/kernel/Makefile linux-2.6.22-d-schedclassic/kernel/Makefile --- linux-2.6.22-c-preemptrcu/kernel/Makefile 2007-08-22 15:21:06.000000000 -0700 +++ linux-2.6.22-d-schedclassic/kernel/Makefile 2007-08-22 15:38:22.000000000 -0700 @@ -47,7 +47,7 @@ obj-$(CONFIG_GENERIC_HARDIRQS) += irq/ obj-$(CONFIG_SECCOMP) += seccomp.o obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o obj-$(CONFIG_CLASSIC_RCU) += rcuclassic.o -obj-$(CONFIG_PREEMPT_RCU) += rcupreempt.o +obj-$(CONFIG_PREEMPT_RCU) += rcuclassic.o rcupreempt.o ifeq ($(CONFIG_PREEMPT_RCU),y) obj-$(CONFIG_RCU_TRACE) += rcupreempt_trace.o endif diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/kernel/rcuclassic.c linux-2.6.22-d-schedclassic/kernel/rcuclassic.c --- linux-2.6.22-c-preemptrcu/kernel/rcuclassic.c 2007-08-22 15:18:40.000000000 -0700 +++ linux-2.6.22-d-schedclassic/kernel/rcuclassic.c 2007-08-22 18:00:17.000000000 -0700 @@ -45,10 +45,53 @@ #include <linux/moduleparam.h> #include <linux/percpu.h> #include <linux/notifier.h> -/* #include <linux/rcupdate.h> @@@ */ #include <linux/cpu.h> #include <linux/mutex.h> + +/* Global control variables for rcupdate callback mechanism. */ +struct rcu_ctrlblk { + long cur; /* Current batch number. */ + long completed; /* Number of the last completed batch */ + int next_pending; /* Is the next batch already waiting? */ + + int signaled; + + spinlock_t lock ____cacheline_internodealigned_in_smp; + cpumask_t cpumask; /* CPUs that need to switch in order */ + /* for current batch to proceed. */ +} ____cacheline_internodealigned_in_smp; + +/* Is batch a before batch b ? */ +static inline int rcu_batch_before(long a, long b) +{ + return (a - b) < 0; +} + +/* + * Per-CPU data for Read-Copy UPdate. + * nxtlist - new callbacks are added here + * curlist - current batch for which quiescent cycle started if any + */ +struct rcu_data { + /* 1) quiescent state handling : */ + long quiescbatch; /* Batch # for grace period */ + int *passed_quiesc; /* User-mode/idle loop etc. */ + int qs_pending; /* core waits for quiesc state */ + + /* 2) batch handling */ + long batch; /* Batch # for current RCU batch */ + struct rcu_head *nxtlist; + struct rcu_head **nxttail; + long qlen; /* # of queued callbacks */ + struct rcu_head *curlist; + struct rcu_head **curtail; + struct rcu_head *donelist; + struct rcu_head **donetail; + long blimit; /* Upper limit on a processed batch */ + int cpu; +}; + /* Definition for rcupdate control block. */ static struct rcu_ctrlblk rcu_ctrlblk = { .cur = -300, @@ -63,11 +106,11 @@ static struct rcu_ctrlblk rcu_bh_ctrlblk .cpumask = CPU_MASK_NONE, }; -DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L }; -DEFINE_PER_CPU(struct rcu_data, rcu_bh_data) = { 0L }; +static DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L }; +static DEFINE_PER_CPU(struct rcu_data, rcu_bh_data) = { 0L }; +DEFINE_PER_CPU(int, rcu_data_bh_passed_quiesc); /* Fake initialization required by compiler */ -static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL}; static int blimit = 10; static int qhimark = 10000; static int qlowmark = 100; @@ -110,8 +153,8 @@ static inline void force_quiescent_state * sections are delimited by rcu_read_lock() and rcu_read_unlock(), * and may be nested. */ -void fastcall call_rcu(struct rcu_head *head, - void (*func)(struct rcu_head *rcu)) +void fastcall call_rcu_classic(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) { unsigned long flags; struct rcu_data *rdp; @@ -128,7 +171,9 @@ void fastcall call_rcu(struct rcu_head * } local_irq_restore(flags); } -EXPORT_SYMBOL_GPL(call_rcu); +EXPORT_SYMBOL_GPL(call_rcu_classic); + +#ifdef CONFIG_CLASSIC_RCU /** * call_rcu_bh - Queue an RCU for invocation after a quicker grace period. @@ -166,7 +211,9 @@ void fastcall call_rcu_bh(struct rcu_hea local_irq_restore(flags); } +#ifdef CONFIG_CLASSIC_RCU EXPORT_SYMBOL_GPL(call_rcu_bh); +#endif /* #ifdef CONFIG_CLASSIC_RCU */ /* * Return the number of RCU batches processed thus far. Useful @@ -176,7 +223,9 @@ long rcu_batches_completed(void) { return rcu_ctrlblk.completed; } +#ifdef CONFIG_CLASSIC_RCU EXPORT_SYMBOL_GPL(rcu_batches_completed); +#endif /* #ifdef CONFIG_CLASSIC_RCU */ /* * Return the number of RCU batches processed thus far. Useful @@ -186,7 +235,11 @@ long rcu_batches_completed_bh(void) { return rcu_bh_ctrlblk.completed; } +#ifdef CONFIG_CLASSIC_RCU EXPORT_SYMBOL_GPL(rcu_batches_completed_bh); +#endif /* #ifdef CONFIG_CLASSIC_RCU */ + +#endif /* #ifdef CONFIG_CLASSIC_RCU */ /* * Invoke the completed RCU callbacks. They are expected to be in @@ -217,7 +270,7 @@ static void rcu_do_batch(struct rcu_data if (!rdp->donelist) rdp->donetail = &rdp->donelist; else - tasklet_schedule(&per_cpu(rcu_tasklet, rdp->cpu)); + raise_softirq(RCU_SOFTIRQ); } /* @@ -294,7 +347,7 @@ static void rcu_check_quiescent_state(st if (rdp->quiescbatch != rcp->cur) { /* start new grace period: */ rdp->qs_pending = 1; - rdp->passed_quiesc = 0; + *rdp->passed_quiesc = 0; rdp->quiescbatch = rcp->cur; return; } @@ -310,7 +363,7 @@ static void rcu_check_quiescent_state(st * Was there a quiescent state since the beginning of the grace * period? If no, then exit and wait for the next call. */ - if (!rdp->passed_quiesc) + if (!*rdp->passed_quiesc) return; rdp->qs_pending = 0; @@ -369,7 +422,6 @@ static void rcu_offline_cpu(int cpu) &per_cpu(rcu_bh_data, cpu)); put_cpu_var(rcu_data); put_cpu_var(rcu_bh_data); - tasklet_kill_immediate(&per_cpu(rcu_tasklet, cpu), cpu); } #else @@ -381,7 +433,7 @@ static void rcu_offline_cpu(int cpu) #endif /* - * This does the RCU processing work from tasklet context. + * This does the RCU processing work from softirq context. */ static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp, struct rcu_data *rdp) @@ -426,10 +478,11 @@ static void __rcu_process_callbacks(stru rcu_do_batch(rdp); } -static void rcu_process_callbacks(unsigned long unused) +static void rcu_process_callbacks(struct softirq_action *unused) { __rcu_process_callbacks(&rcu_ctrlblk, &__get_cpu_var(rcu_data)); __rcu_process_callbacks(&rcu_bh_ctrlblk, &__get_cpu_var(rcu_bh_data)); + rcu_process_callbacks_rt(unused); } static int __rcu_pending(struct rcu_ctrlblk *rcp, struct rcu_data *rdp) @@ -464,7 +517,8 @@ static int __rcu_pending(struct rcu_ctrl int rcu_pending(int cpu) { return __rcu_pending(&rcu_ctrlblk, &per_cpu(rcu_data, cpu)) || - __rcu_pending(&rcu_bh_ctrlblk, &per_cpu(rcu_bh_data, cpu)); + __rcu_pending(&rcu_bh_ctrlblk, &per_cpu(rcu_bh_data, cpu)) || + rcu_pending_rt(cpu); } /* @@ -478,7 +532,8 @@ int rcu_needs_cpu(int cpu) struct rcu_data *rdp = &per_cpu(rcu_data, cpu); struct rcu_data *rdp_bh = &per_cpu(rcu_bh_data, cpu); - return (!!rdp->curlist || !!rdp_bh->curlist || rcu_pending(cpu)); + return (!!rdp->curlist || !!rdp_bh->curlist || rcu_pending(cpu) || + rcu_needs_cpu_rt(cpu)); } void rcu_check_callbacks(int cpu, int user) @@ -490,7 +545,8 @@ void rcu_check_callbacks(int cpu, int us rcu_bh_qsctr_inc(cpu); } else if (!in_softirq()) rcu_bh_qsctr_inc(cpu); - tasklet_schedule(&per_cpu(rcu_tasklet, cpu)); + rcu_check_callbacks_rt(cpu, user); + raise_softirq(RCU_SOFTIRQ); } static void rcu_init_percpu_data(int cpu, struct rcu_ctrlblk *rcp, @@ -512,8 +568,9 @@ static void __devinit rcu_online_cpu(int struct rcu_data *bh_rdp = &per_cpu(rcu_bh_data, cpu); rcu_init_percpu_data(cpu, &rcu_ctrlblk, rdp); + rdp->passed_quiesc = &per_cpu(rcu_data_passed_quiesc, cpu); rcu_init_percpu_data(cpu, &rcu_bh_ctrlblk, bh_rdp); - tasklet_init(&per_cpu(rcu_tasklet, cpu), rcu_process_callbacks, 0UL); + bh_rdp->passed_quiesc = &per_cpu(rcu_data_bh_passed_quiesc, cpu); } static int __cpuinit rcu_cpu_notify(struct notifier_block *self, @@ -545,12 +602,14 @@ static struct notifier_block __cpuinitda * Note that rcu_qsctr and friends are implicitly * initialized due to the choice of ``0'' for RCU_CTR_INVALID. */ -void __init __rcu_init(void) +void __init rcu_init(void) { rcu_cpu_notify(&rcu_nb, CPU_UP_PREPARE, (void *)(long)smp_processor_id()); /* Register notifier for non-boot CPUs */ register_cpu_notifier(&rcu_nb); + rcu_init_rt(); + open_softirq(RCU_SOFTIRQ, rcu_process_callbacks, NULL); } module_param(blimit, int, 0); diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/kernel/rcupdate.c linux-2.6.22-d-schedclassic/kernel/rcupdate.c --- linux-2.6.22-c-preemptrcu/kernel/rcupdate.c 2007-08-22 15:18:40.000000000 -0700 +++ linux-2.6.22-d-schedclassic/kernel/rcupdate.c 2007-08-22 15:46:36.000000000 -0700 @@ -52,6 +52,7 @@ struct rcu_synchronize { struct completion completion; }; +DEFINE_PER_CPU(int, rcu_data_passed_quiesc); static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL}; static atomic_t rcu_barrier_cpu_count; static DEFINE_MUTEX(rcu_barrier_mutex); @@ -88,6 +89,22 @@ void synchronize_rcu(void) } EXPORT_SYMBOL_GPL(synchronize_rcu); +#ifdef CONFIG_PREEMPT_RCU + +/* + * Map synchronize_sched() to the classic RCU implementation. + */ +void __synchronize_sched(void) +{ + struct rcu_synchronize rcu; + + init_completion(&rcu.completion); + call_rcu_classic(&rcu.head, wakeme_after_rcu); + wait_for_completion(&rcu.completion); +} +EXPORT_SYMBOL_GPL(__synchronize_sched); +#endif /* #ifdef CONFIG_PREEMPT_RCU */ + static void rcu_barrier_callback(struct rcu_head *notused) { if (atomic_dec_and_test(&rcu_barrier_cpu_count)) @@ -131,8 +148,3 @@ void rcu_barrier(void) wait_for_completion(&rcu_barrier_completion); mutex_unlock(&rcu_barrier_mutex); } - -void __init rcu_init(void) -{ - __rcu_init(); -} diff -urpNa -X dontdiff linux-2.6.22-c-preemptrcu/kernel/rcupreempt.c linux-2.6.22-d-schedclassic/kernel/rcupreempt.c --- linux-2.6.22-c-preemptrcu/kernel/rcupreempt.c 2007-08-22 15:35:19.000000000 -0700 +++ linux-2.6.22-d-schedclassic/kernel/rcupreempt.c 2007-08-22 15:45:28.000000000 -0700 @@ -61,7 +61,6 @@ struct rcu_data { spinlock_t lock; /* Protect rcu_data fields. */ long completed; /* Number of last completed batch. */ int waitlistcount; - struct tasklet_struct rcu_tasklet; struct rcu_head *nextlist; struct rcu_head **nexttail; struct rcu_head *waitlist[GP_STAGES]; @@ -550,7 +549,7 @@ static void rcu_check_mb(int cpu) } } -void rcu_check_callbacks(int cpu, int user) +void rcu_check_callbacks_rt(int cpu, int user) { unsigned long oldirq; struct rcu_data *rdp = RCU_DATA_CPU(cpu); @@ -561,19 +560,14 @@ void rcu_check_callbacks(int cpu, int us spin_lock_irqsave(&rdp->lock, oldirq); RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp); __rcu_advance_callbacks(rdp); - if (rdp->donelist == NULL) { - spin_unlock_irqrestore(&rdp->lock, oldirq); - } else { - spin_unlock_irqrestore(&rdp->lock, oldirq); - raise_softirq(RCU_SOFTIRQ); - } + spin_unlock_irqrestore(&rdp->lock, oldirq); } /* * Needed by dynticks, to make sure all RCU processing has finished - * when we go idle: + * when we go idle. (Currently unused, needed?) */ -void rcu_advance_callbacks(int cpu, int user) +void rcu_advance_callbacks_rt(int cpu, int user) { unsigned long oldirq; struct rcu_data *rdp = RCU_DATA_CPU(cpu); @@ -589,7 +583,7 @@ void rcu_advance_callbacks(int cpu, int spin_unlock_irqrestore(&rdp->lock, oldirq); } -static void rcu_process_callbacks(struct softirq_action *unused) +void rcu_process_callbacks_rt(struct softirq_action *unused) { unsigned long flags; struct rcu_head *next, *list; @@ -613,8 +607,8 @@ static void rcu_process_callbacks(struct } } -void fastcall call_rcu(struct rcu_head *head, - void (*func)(struct rcu_head *rcu)) +void fastcall call_rcu_preempt(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) { unsigned long oldirq; struct rcu_data *rdp; @@ -631,28 +625,7 @@ void fastcall call_rcu(struct rcu_head * spin_unlock(&rdp->lock); local_irq_restore(oldirq); } -EXPORT_SYMBOL_GPL(call_rcu); - -/* - * Wait until all currently running preempt_disable() code segments - * (including hardware-irq-disable segments) complete. Note that - * in -rt this does -not- necessarily result in all currently executing - * interrupt -handlers- having completed. - */ -void __synchronize_sched(void) -{ - cpumask_t oldmask; - int cpu; - - if (sched_getaffinity(0, &oldmask) < 0) - oldmask = cpu_possible_map; - for_each_online_cpu(cpu) { - sched_setaffinity(0, cpumask_of_cpu(cpu)); - schedule(); - } - sched_setaffinity(0, oldmask); -} -EXPORT_SYMBOL_GPL(__synchronize_sched); +EXPORT_SYMBOL_GPL(call_rcu_preempt); /* * Check to see if any future RCU-related work will need to be done @@ -663,7 +636,7 @@ EXPORT_SYMBOL_GPL(__synchronize_sched); * This function is part of the RCU implementation; it is -not- * an exported member of the RCU API. */ -int rcu_needs_cpu(int cpu) +int rcu_needs_cpu_rt(int cpu) { struct rcu_data *rdp = RCU_DATA_CPU(cpu); @@ -672,7 +645,7 @@ int rcu_needs_cpu(int cpu) rdp->nextlist != NULL); } -int rcu_pending(int cpu) +int rcu_pending_rt(int cpu) { struct rcu_data *rdp = RCU_DATA_CPU(cpu); @@ -699,7 +672,7 @@ int rcu_pending(int cpu) return 0; } -void __init __rcu_init(void) +void __init rcu_init_rt(void) { int cpu; int i; @@ -720,7 +693,6 @@ void __init __rcu_init(void) rdp->donelist = NULL; rdp->donetail = &rdp->donelist; } - open_softirq(RCU_SOFTIRQ, rcu_process_callbacks, NULL); } /* ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 5/8] RCU: CPU hotplug support for preemptible RCU 2007-09-05 21:36 ` [PATCH RFC 4/8] RCU: synchronize_sched() workaround for CPU hotplug Paul E. McKenney @ 2007-09-05 21:37 ` Paul E. McKenney 2007-09-05 21:38 ` [PATCH RFC 6/8] RCU priority boosting " Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:37 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. This patch allows preemptible RCU to tolerate CPU-hotplug operations. It accomplishes this by maintaining a local copy of a map of online CPUs, which it accesses under its own lock. Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- include/linux/rcuclassic.h | 2 include/linux/rcupreempt.h | 2 kernel/rcuclassic.c | 8 +++ kernel/rcupreempt.c | 93 +++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 100 insertions(+), 5 deletions(-) diff -urpNa -X dontdiff linux-2.6.22-d-schedclassic/include/linux/rcuclassic.h linux-2.6.22-e-hotplugcpu/include/linux/rcuclassic.h --- linux-2.6.22-d-schedclassic/include/linux/rcuclassic.h 2007-08-22 15:38:22.000000000 -0700 +++ linux-2.6.22-e-hotplugcpu/include/linux/rcuclassic.h 2007-08-22 15:55:39.000000000 -0700 @@ -143,6 +143,8 @@ extern int rcu_needs_cpu(int cpu); #define rcu_check_callbacks_rt(cpu, user) #define rcu_init_rt() #define rcu_needs_cpu_rt(cpu) 0 +#define rcu_offline_cpu_rt(cpu) +#define rcu_online_cpu_rt(cpu) #define rcu_pending_rt(cpu) 0 #define rcu_process_callbacks_rt(unused) diff -urpNa -X dontdiff linux-2.6.22-d-schedclassic/include/linux/rcupreempt.h linux-2.6.22-e-hotplugcpu/include/linux/rcupreempt.h --- linux-2.6.22-d-schedclassic/include/linux/rcupreempt.h 2007-08-22 15:38:22.000000000 -0700 +++ linux-2.6.22-e-hotplugcpu/include/linux/rcupreempt.h 2007-08-22 15:55:39.000000000 -0700 @@ -59,6 +59,8 @@ extern void rcu_advance_callbacks_rt(int extern void rcu_check_callbacks_rt(int cpu, int user); extern void rcu_init_rt(void); extern int rcu_needs_cpu_rt(int cpu); +extern void rcu_offline_cpu_rt(int cpu); +extern void rcu_online_cpu_rt(int cpu); extern int rcu_pending_rt(int cpu); struct softirq_action; extern void rcu_process_callbacks_rt(struct softirq_action *unused); diff -urpNa -X dontdiff linux-2.6.22-d-schedclassic/kernel/rcuclassic.c linux-2.6.22-e-hotplugcpu/kernel/rcuclassic.c --- linux-2.6.22-d-schedclassic/kernel/rcuclassic.c 2007-08-22 15:51:22.000000000 -0700 +++ linux-2.6.22-e-hotplugcpu/kernel/rcuclassic.c 2007-08-22 15:55:39.000000000 -0700 @@ -414,14 +414,19 @@ static void __rcu_offline_cpu(struct rcu static void rcu_offline_cpu(int cpu) { struct rcu_data *this_rdp = &get_cpu_var(rcu_data); +#ifdef CONFIG_CLASSIC_RCU struct rcu_data *this_bh_rdp = &get_cpu_var(rcu_bh_data); +#endif /* #ifdef CONFIG_CLASSIC_RCU */ __rcu_offline_cpu(this_rdp, &rcu_ctrlblk, &per_cpu(rcu_data, cpu)); +#ifdef CONFIG_CLASSIC_RCU __rcu_offline_cpu(this_bh_rdp, &rcu_bh_ctrlblk, &per_cpu(rcu_bh_data, cpu)); - put_cpu_var(rcu_data); put_cpu_var(rcu_bh_data); +#endif /* #ifdef CONFIG_CLASSIC_RCU */ + put_cpu_var(rcu_data); + rcu_offline_cpu_rt(cpu); } #else @@ -571,6 +576,7 @@ static void __devinit rcu_online_cpu(int rdp->passed_quiesc = &per_cpu(rcu_data_passed_quiesc, cpu); rcu_init_percpu_data(cpu, &rcu_bh_ctrlblk, bh_rdp); bh_rdp->passed_quiesc = &per_cpu(rcu_data_bh_passed_quiesc, cpu); + rcu_online_cpu_rt(cpu); } static int __cpuinit rcu_cpu_notify(struct notifier_block *self, diff -urpNa -X dontdiff linux-2.6.22-d-schedclassic/kernel/rcupreempt.c linux-2.6.22-e-hotplugcpu/kernel/rcupreempt.c --- linux-2.6.22-d-schedclassic/kernel/rcupreempt.c 2007-08-22 15:45:28.000000000 -0700 +++ linux-2.6.22-e-hotplugcpu/kernel/rcupreempt.c 2007-08-22 15:56:22.000000000 -0700 @@ -125,6 +125,8 @@ enum rcu_mb_flag_values { }; static DEFINE_PER_CPU(enum rcu_mb_flag_values, rcu_mb_flag) = rcu_mb_done; +static cpumask_t rcu_cpu_online_map = CPU_MASK_NONE; + /* * Macro that prevents the compiler from reordering accesses, but does * absolutely -nothing- to prevent CPUs from reordering. This is used @@ -404,7 +406,7 @@ rcu_try_flip_idle(void) /* Now ask each CPU for acknowledgement of the flip. */ - for_each_possible_cpu(cpu) + for_each_cpu_mask(cpu, rcu_cpu_online_map) per_cpu(rcu_flip_flag, cpu) = rcu_flipped; return 1; @@ -420,7 +422,7 @@ rcu_try_flip_waitack(void) int cpu; RCU_TRACE_ME(rcupreempt_trace_try_flip_a1); - for_each_possible_cpu(cpu) + for_each_cpu_mask(cpu, rcu_cpu_online_map) if (per_cpu(rcu_flip_flag, cpu) != rcu_flip_seen) { RCU_TRACE_ME(rcupreempt_trace_try_flip_ae1); return 0; @@ -462,7 +464,7 @@ rcu_try_flip_waitzero(void) /* Call for a memory barrier from each CPU. */ - for_each_possible_cpu(cpu) + for_each_cpu_mask(cpu, rcu_cpu_online_map) per_cpu(rcu_mb_flag, cpu) = rcu_mb_needed; RCU_TRACE_ME(rcupreempt_trace_try_flip_z2); @@ -480,7 +482,7 @@ rcu_try_flip_waitmb(void) int cpu; RCU_TRACE_ME(rcupreempt_trace_try_flip_m1); - for_each_possible_cpu(cpu) + for_each_cpu_mask(cpu, rcu_cpu_online_map) if (per_cpu(rcu_mb_flag, cpu) != rcu_mb_done) { RCU_TRACE_ME(rcupreempt_trace_try_flip_me1); return 0; @@ -583,6 +585,89 @@ void rcu_advance_callbacks_rt(int cpu, i spin_unlock_irqrestore(&rdp->lock, oldirq); } +#ifdef CONFIG_HOTPLUG_CPU + +#define rcu_offline_cpu_rt_enqueue(srclist, srctail, dstlist, dsttail) do { \ + *dsttail = srclist; \ + if (srclist != NULL) { \ + dsttail = srctail; \ + srclist = NULL; \ + srctail = &srclist;\ + } \ + } while (0) + + +void rcu_offline_cpu_rt(int cpu) +{ + int i; + struct rcu_head *list = NULL; + unsigned long oldirq; + struct rcu_data *rdp = RCU_DATA_CPU(cpu); + struct rcu_head **tail = &list; + + /* Remove all callbacks from the newly dead CPU, retaining order. */ + + spin_lock_irqsave(&rdp->lock, oldirq); + rcu_offline_cpu_rt_enqueue(rdp->donelist, rdp->donetail, list, tail); + for (i = GP_STAGES - 1; i >= 0; i--) + rcu_offline_cpu_rt_enqueue(rdp->waitlist[i], rdp->waittail[i], + list, tail); + rcu_offline_cpu_rt_enqueue(rdp->nextlist, rdp->nexttail, list, tail); + spin_unlock_irqrestore(&rdp->lock, oldirq); + rdp->waitlistcount = 0; + + /* Disengage the newly dead CPU from grace-period computation. */ + + spin_lock_irqsave(&rcu_ctrlblk.fliplock, oldirq); + rcu_check_mb(cpu); + if (per_cpu(rcu_flip_flag, cpu) == rcu_flipped) { + smp_mb(); /* Subsequent counter accesses must see new value */ + per_cpu(rcu_flip_flag, cpu) = rcu_flip_seen; + smp_mb(); /* Subsequent RCU read-side critical sections */ + /* seen -after- acknowledgement. */ + } + cpu_clear(cpu, rcu_cpu_online_map); + spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, oldirq); + + /* + * Place the removed callbacks on the current CPU's queue. + * Make them all start a new grace period: simple approach, + * in theory could starve a given set of callbacks, but + * you would need to be doing some serious CPU hotplugging + * to make this happen. If this becomes a problem, adding + * a synchronize_rcu() to the hotplug path would be a simple + * fix. + */ + + rdp = RCU_DATA_ME(); + spin_lock_irqsave(&rdp->lock, oldirq); + *rdp->nexttail = list; + if (list) + rdp->nexttail = tail; + spin_unlock_irqrestore(&rdp->lock, oldirq); +} + +void __devinit rcu_online_cpu_rt(int cpu) +{ + unsigned long oldirq; + + spin_lock_irqsave(&rcu_ctrlblk.fliplock, oldirq); + cpu_set(cpu, rcu_cpu_online_map); + spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, oldirq); +} + +#else /* #ifdef CONFIG_HOTPLUG_CPU */ + +void rcu_offline_cpu(int cpu) +{ +} + +void __devinit rcu_online_cpu_rt(int cpu) +{ +} + +#endif /* #else #ifdef CONFIG_HOTPLUG_CPU */ + void rcu_process_callbacks_rt(struct softirq_action *unused) { unsigned long flags; ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 6/8] RCU priority boosting for preemptible RCU 2007-09-05 21:37 ` [PATCH RFC 5/8] RCU: CPU hotplug support for preemptible RCU Paul E. McKenney @ 2007-09-05 21:38 ` Paul E. McKenney 2007-09-05 21:39 ` [PATCH RFC 7/8] RCU: rcutorture testing for RCU priority boosting Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:38 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. RCU priority boosting is needed when running a workload that might include CPU-bound user tasks running at realtime priorities with preemptible RCU. In this situation, RCU priority boosting is needed to avoid OOM. Please note that because Classic RCU does not permit RCU read-side critical sections to be preempted, there is no need to boost the priority of Classic RCU readers. Boosting the priority of a running process does not make it run any faster, at least not on any hardware that I am aware of. ;-) Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- include/linux/init_task.h | 13 include/linux/rcupdate.h | 17 + include/linux/rcupreempt.h | 20 + include/linux/sched.h | 24 + init/main.c | 1 kernel/Kconfig.preempt | 14 - kernel/fork.c | 6 kernel/rcupreempt.c | 608 ++++++++++++++++++++++++++++++++++++++++++--- kernel/rtmutex.c | 7 kernel/sched.c | 5 lib/Kconfig.debug | 34 ++ 11 files changed, 703 insertions(+), 46 deletions(-) diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/include/linux/init_task.h linux-2.6.22-F-boostrcu/include/linux/init_task.h --- linux-2.6.22-E-hotplug/include/linux/init_task.h 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-F-boostrcu/include/linux/init_task.h 2007-08-31 14:09:02.000000000 -0700 @@ -87,6 +87,17 @@ extern struct nsproxy init_nsproxy; .signalfd_list = LIST_HEAD_INIT(sighand.signalfd_list), \ } +#ifdef CONFIG_PREEMPT_RCU_BOOST +#define INIT_RCU_BOOST_PRIO .rcu_prio = MAX_PRIO, +#define INIT_PREEMPT_RCU_BOOST(tsk) \ + .rcub_rbdp = NULL, \ + .rcub_state = RCU_BOOST_IDLE, \ + .rcub_entry = LIST_HEAD_INIT(tsk.rcub_entry), +#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ +#define INIT_RCU_BOOST_PRIO +#define INIT_PREEMPT_RCU_BOOST(tsk) +#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST */ + extern struct group_info init_groups; #define INIT_STRUCT_PID { \ @@ -125,6 +136,7 @@ extern struct group_info init_groups; .prio = MAX_PRIO-20, \ .static_prio = MAX_PRIO-20, \ .normal_prio = MAX_PRIO-20, \ + INIT_RCU_BOOST_PRIO \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ .mm = NULL, \ @@ -169,6 +181,7 @@ extern struct group_info init_groups; }, \ INIT_TRACE_IRQFLAGS \ INIT_LOCKDEP \ + INIT_PREEMPT_RCU_BOOST(tsk) \ } diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/include/linux/rcupdate.h linux-2.6.22-F-boostrcu/include/linux/rcupdate.h --- linux-2.6.22-E-hotplug/include/linux/rcupdate.h 2007-08-24 11:03:22.000000000 -0700 +++ linux-2.6.22-F-boostrcu/include/linux/rcupdate.h 2007-08-24 17:04:14.000000000 -0700 @@ -252,5 +252,22 @@ static inline void rcu_qsctr_inc(int cpu per_cpu(rcu_data_passed_quiesc, cpu) = 1; } +#ifdef CONFIG_PREEMPT_RCU_BOOST +extern void init_rcu_boost_late(void); +extern void __rcu_preempt_boost(void); +#define rcu_preempt_boost() /* cpp to avoid #include hell. */ \ + do { \ + if (unlikely(current->rcu_read_lock_nesting > 0)) \ + __rcu_preempt_boost(); \ + } while (0) +#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ +static inline void init_rcu_boost_late(void) +{ +} +static inline void rcu_preempt_boost(void) +{ +} +#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST */ + #endif /* __KERNEL__ */ #endif /* __LINUX_RCUPDATE_H */ diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/include/linux/rcupreempt.h linux-2.6.22-F-boostrcu/include/linux/rcupreempt.h --- linux-2.6.22-E-hotplug/include/linux/rcupreempt.h 2007-08-24 11:20:32.000000000 -0700 +++ linux-2.6.22-F-boostrcu/include/linux/rcupreempt.h 2007-08-24 11:24:59.000000000 -0700 @@ -42,6 +42,26 @@ #include <linux/cpumask.h> #include <linux/seqlock.h> +#ifdef CONFIG_PREEMPT_RCU_BOOST +/* + * Task state with respect to being RCU-boosted. This state is changed + * by the task itself in response to the following three events: + * 1. Preemption (or block on lock) while in RCU read-side critical section. + * 2. Outermost rcu_read_unlock() for blocked RCU read-side critical section. + * + * The RCU-boost task also updates the state when boosting priority. + */ +enum rcu_boost_state { + RCU_BOOST_IDLE = 0, /* Not yet blocked if in RCU read-side. */ + RCU_BOOST_BLOCKED = 1, /* Blocked from RCU read-side. */ + RCU_BOOSTED = 2, /* Boosting complete. */ + RCU_BOOST_INVALID = 3, /* For bogus state sightings. */ +}; + +#define N_RCU_BOOST_STATE (RCU_BOOST_INVALID + 1) + +#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ + #define call_rcu_bh(head, rcu) call_rcu(head, rcu) #define rcu_bh_qsctr_inc(cpu) do { } while (0) #define __rcu_read_lock_bh() { rcu_read_lock(); local_bh_disable(); } diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/include/linux/sched.h linux-2.6.22-F-boostrcu/include/linux/sched.h --- linux-2.6.22-E-hotplug/include/linux/sched.h 2007-08-24 11:00:39.000000000 -0700 +++ linux-2.6.22-F-boostrcu/include/linux/sched.h 2007-08-24 17:07:01.000000000 -0700 @@ -546,6 +546,22 @@ struct signal_struct { #define is_rt_policy(p) ((p) != SCHED_NORMAL && (p) != SCHED_BATCH) #define has_rt_policy(p) unlikely(is_rt_policy((p)->policy)) +#ifdef CONFIG_PREEMPT_RCU_BOOST +#define set_rcu_prio(p, prio) /* cpp to avoid #include hell */ \ + do { \ + (p)->rcu_prio = (prio); \ + } while (0) +#define get_rcu_prio(p) (p)->rcu_prio /* cpp to avoid #include hell */ +#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ +static inline void set_rcu_prio(struct task_struct *p, int prio) +{ +} +static inline int get_rcu_prio(struct task_struct *p) +{ + return MAX_PRIO; +} +#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST */ + /* * Some day this will be a full-fledged user tracking system.. */ @@ -834,6 +850,9 @@ struct task_struct { #endif int load_weight; /* for niceness load balancing purposes */ int prio, static_prio, normal_prio; +#ifdef CONFIG_PREEMPT_RCU_BOOST + int rcu_prio; +#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ struct list_head run_list; struct prio_array *array; @@ -858,6 +877,11 @@ struct task_struct { #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) struct sched_info sched_info; #endif +#ifdef CONFIG_PREEMPT_RCU_BOOST + struct rcu_boost_dat *rcub_rbdp; + enum rcu_boost_state rcub_state; + struct list_head rcub_entry; +#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ struct list_head tasks; /* diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/init/main.c linux-2.6.22-F-boostrcu/init/main.c --- linux-2.6.22-E-hotplug/init/main.c 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-F-boostrcu/init/main.c 2007-08-24 11:24:59.000000000 -0700 @@ -722,6 +722,7 @@ static void __init do_basic_setup(void) driver_init(); init_irq_proc(); do_initcalls(); + init_rcu_boost_late(); } static void __init do_pre_smp_initcalls(void) diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/kernel/fork.c linux-2.6.22-F-boostrcu/kernel/fork.c --- linux-2.6.22-E-hotplug/kernel/fork.c 2007-08-24 11:00:39.000000000 -0700 +++ linux-2.6.22-F-boostrcu/kernel/fork.c 2007-08-24 11:24:59.000000000 -0700 @@ -1036,6 +1036,12 @@ static struct task_struct *copy_process( p->rcu_read_lock_nesting = 0; p->rcu_flipctr_idx = 0; #endif /* #ifdef CONFIG_PREEMPT_RCU */ +#ifdef CONFIG_PREEMPT_RCU_BOOST + p->rcu_prio = MAX_PRIO; + p->rcub_rbdp = NULL; + p->rcub_state = RCU_BOOST_IDLE; + INIT_LIST_HEAD(&p->rcub_entry); +#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ p->vfork_done = NULL; spin_lock_init(&p->alloc_lock); diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/kernel/Kconfig.preempt linux-2.6.22-F-boostrcu/kernel/Kconfig.preempt --- linux-2.6.22-E-hotplug/kernel/Kconfig.preempt 2007-08-24 11:00:39.000000000 -0700 +++ linux-2.6.22-F-boostrcu/kernel/Kconfig.preempt 2007-08-24 11:24:59.000000000 -0700 @@ -91,13 +91,13 @@ config PREEMPT_RCU endchoice -config RCU_TRACE - bool "Enable tracing for RCU - currently stats in debugfs" - select DEBUG_FS - default y +config PREEMPT_RCU_BOOST + bool "Enable priority boosting of RCU read-side critical sections" + depends on PREEMPT_RCU + default n help - This option provides tracing in RCU which presents stats - in debugfs for debugging RCU implementation. + This option permits priority boosting of RCU read-side critical + sections that have been preempted in order to prevent indefinite + delay of grace periods in face of runaway non-realtime processes. - Say Y here if you want to enable RCU tracing Say N if you are unsure. diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/kernel/rcupreempt.c linux-2.6.22-F-boostrcu/kernel/rcupreempt.c --- linux-2.6.22-E-hotplug/kernel/rcupreempt.c 2007-08-24 11:20:32.000000000 -0700 +++ linux-2.6.22-F-boostrcu/kernel/rcupreempt.c 2007-08-31 14:06:49.000000000 -0700 @@ -51,6 +51,15 @@ #include <linux/byteorder/swabb.h> #include <linux/cpumask.h> #include <linux/rcupreempt_trace.h> +#include <linux/kthread.h> + +/* + * Macro that prevents the compiler from reordering accesses, but does + * absolutely -nothing- to prevent CPUs from reordering. This is used + * only to mediate communication between mainline code and hardware + * interrupt and NMI handlers. + */ +#define ORDERED_WRT_IRQ(x) (*(volatile typeof(x) *)&(x)) /* * PREEMPT_RCU data structures. @@ -82,6 +91,531 @@ static struct rcu_ctrlblk rcu_ctrlblk = }; static DEFINE_PER_CPU(int [2], rcu_flipctr) = { 0, 0 }; +#ifndef CONFIG_PREEMPT_RCU_BOOST +static inline void init_rcu_boost_early(void) { } +static inline void rcu_read_unlock_unboost(void) { } +#else /* #ifndef CONFIG_PREEMPT_RCU_BOOST */ + +/* Defines possible event indices for ->rbs_stats[] (first index). */ + +#define RCU_BOOST_DAT_BLOCK 0 +#define RCU_BOOST_DAT_BOOST 1 +#define RCU_BOOST_DAT_UNLOCK 2 +#define N_RCU_BOOST_DAT_EVENTS 3 + +/* RCU-boost per-CPU array element. */ + +struct rcu_boost_dat { + spinlock_t rbs_lock; /* Protects state/CPU slice of structures. */ + struct list_head rbs_toboost; + struct list_head rbs_boosted; + unsigned long rbs_blocked; + unsigned long rbs_boost_attempt; + unsigned long rbs_boost; + unsigned long rbs_unlock; + unsigned long rbs_unboosted; +#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS + unsigned long rbs_stats[N_RCU_BOOST_DAT_EVENTS][N_RCU_BOOST_STATE]; +#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */ +}; +#define RCU_BOOST_ELEMENTS 4 + +static int rcu_boost_idx = -1; /* invalid value for early RCU use. */ +static DEFINE_PER_CPU(struct rcu_boost_dat, rcu_boost_dat[RCU_BOOST_ELEMENTS]); +static struct task_struct *rcu_boost_task; + +#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS + +/* + * Function to increment indicated ->rbs_stats[] element. + */ +static inline void rcu_boost_dat_stat(struct rcu_boost_dat *rbdp, + int event, + enum rcu_boost_state oldstate) +{ + if (oldstate >= RCU_BOOST_IDLE && oldstate <= RCU_BOOSTED) { + rbdp->rbs_stats[event][oldstate]++; + } else { + rbdp->rbs_stats[event][RCU_BOOST_INVALID]++; + } +} + +static inline void rcu_boost_dat_stat_block(struct rcu_boost_dat *rbdp, + enum rcu_boost_state oldstate) +{ + rcu_boost_dat_stat(rbdp, RCU_BOOST_DAT_BLOCK, oldstate); +} + +static inline void rcu_boost_dat_stat_boost(struct rcu_boost_dat *rbdp, + enum rcu_boost_state oldstate) +{ + rcu_boost_dat_stat(rbdp, RCU_BOOST_DAT_BOOST, oldstate); +} + +static inline void rcu_boost_dat_stat_unlock(struct rcu_boost_dat *rbdp, + enum rcu_boost_state oldstate) +{ + rcu_boost_dat_stat(rbdp, RCU_BOOST_DAT_UNLOCK, oldstate); +} + +/* + * Prefix for kprint() strings for periodic statistics messages. + */ +static char *rcu_boost_state_event[] = { + "block: ", + "boost: ", + "unlock: ", +}; + +/* + * Indicators for numbers in kprint() strings. "!" indicates a state-event + * pair that should not happen, while "?" indicates a state that should + * not happen. + */ +static char *rcu_boost_state_error[] = { + /*ibBe*/ + " ?", /* block */ + "! ?", /* boost */ + "? ?", /* unlock */ +}; + +/* + * Print out RCU booster task statistics at the specified interval. + */ +static void rcu_boost_dat_stat_print(void) +{ + /* Three decimal digits per byte plus spacing per number and line. */ + char buf[N_RCU_BOOST_STATE * (sizeof(long) * 3 + 2) + 2]; + int cpu; + int event; + int i; + static time_t lastprint; /* static implies 0 initial value. */ + struct rcu_boost_dat *rbdp; + int state; + struct rcu_boost_dat sum; + + /* Wait a graceful interval between printk spamming. */ + /* Note: time_after() dislikes time_t. */ + + if (xtime.tv_sec - lastprint < CONFIG_PREEMPT_RCU_BOOST_STATS_INTERVAL) + return; + + /* Sum up the state/event-independent counters. */ + + sum.rbs_blocked = 0; + sum.rbs_boost_attempt = 0; + sum.rbs_boost = 0; + sum.rbs_unlock = 0; + sum.rbs_unboosted = 0; + for_each_possible_cpu(cpu) + for (i = 0; i < RCU_BOOST_ELEMENTS; i++) { + rbdp = per_cpu(rcu_boost_dat, cpu); + sum.rbs_blocked += rbdp[i].rbs_blocked; + sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt; + sum.rbs_boost += rbdp[i].rbs_boost; + sum.rbs_unlock += rbdp[i].rbs_unlock; + sum.rbs_unboosted += rbdp[i].rbs_unboosted; + } + + /* Sum up the state/event-dependent counters. */ + + for (event = 0; event < N_RCU_BOOST_DAT_EVENTS; event++) + for (state = 0; state < N_RCU_BOOST_STATE; state++) { + sum.rbs_stats[event][state] = 0; + for_each_possible_cpu(cpu) { + for (i = 0; i < RCU_BOOST_ELEMENTS; i++) + sum.rbs_stats[event][state] + += per_cpu(rcu_boost_dat, + cpu)[i].rbs_stats[event][state]; + } + } + + /* Print them out! */ + + printk(KERN_INFO + "rcu_boost_dat: idx=%d " + "b=%lu ul=%lu ub=%lu boost: a=%lu b=%lu\n", + rcu_boost_idx, + sum.rbs_blocked, sum.rbs_unlock, sum.rbs_unboosted, + sum.rbs_boost_attempt, sum.rbs_boost); + for (event = 0; event < N_RCU_BOOST_DAT_EVENTS; event++) { + i = 0; + for (state = 0; state < N_RCU_BOOST_STATE; state++) + i += sprintf(&buf[i], " %ld%c", + sum.rbs_stats[event][state], + rcu_boost_state_error[event][state]); + printk(KERN_INFO "rcu_boost_dat %s %s\n", + rcu_boost_state_event[event], buf); + } + + /* Go away and don't come back for awhile. */ + + lastprint = xtime.tv_sec; +} + +#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */ + +static inline void rcu_boost_dat_stat_block(struct rcu_boost_dat *rbdp, + enum rcu_boost_state oldstate) +{ +} +static inline void rcu_boost_dat_stat_boost(struct rcu_boost_dat *rbdp, + enum rcu_boost_state oldstate) +{ +} +static inline void rcu_boost_dat_stat_unlock(struct rcu_boost_dat *rbdp, + enum rcu_boost_state oldstate) +{ +} +static void rcu_boost_dat_stat_print(void) +{ +} + +#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */ + +/* + * Initialize RCU-boost state. This happens early in the boot process, + * when the scheduler does not yet exist. So don't try to use it. + */ +static void init_rcu_boost_early(void) +{ + struct rcu_boost_dat *rbdp; + int cpu; + int i; + + for_each_possible_cpu(cpu) { + rbdp = per_cpu(rcu_boost_dat, cpu); + for (i = 0; i < RCU_BOOST_ELEMENTS; i++) { + spin_lock_init(&rbdp[i].rbs_lock); + INIT_LIST_HEAD(&rbdp[i].rbs_toboost); + INIT_LIST_HEAD(&rbdp[i].rbs_boosted); + rbdp[i].rbs_blocked = 0; + rbdp[i].rbs_boost_attempt = 0; + rbdp[i].rbs_boost = 0; + rbdp[i].rbs_unlock = 0; + rbdp[i].rbs_unboosted = 0; +#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS + { + int j, k; + + for (j = 0; j < N_RCU_BOOST_DAT_EVENTS; j++) + for (k = 0; k < N_RCU_BOOST_STATE; k++) + rbdp[i].rbs_stats[j][k] = 0; + } +#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */ + } + smp_wmb(); /* Make sure readers see above initialization. */ + rcu_boost_idx = 0; /* Allow readers to access data. */ + } +} + +/* + * Return the list on which the calling task should add itself, or + * NULL if too early during initialization. + */ +static inline struct rcu_boost_dat *rcu_rbd_new(void) +{ + int cpu = smp_processor_id(); /* locks used, so preemption OK. */ + int idx = ORDERED_WRT_IRQ(rcu_boost_idx); + + if (unlikely(idx < 0)) + return NULL; + return &per_cpu(rcu_boost_dat, cpu)[idx]; +} + +/* + * Return the list from which to boost target tasks. + * May only be invoked by the booster task, so guaranteed to + * already be initialized. Use rcu_boost_dat element least recently + * the destination for task blocking in RCU read-side critical sections. + */ +static inline struct rcu_boost_dat *rcu_rbd_boosting(int cpu) +{ + int idx = (rcu_boost_idx + 1) & (RCU_BOOST_ELEMENTS - 1); + + return &per_cpu(rcu_boost_dat, cpu)[idx]; +} + +#define PREEMPT_RCU_BOOSTER_PRIO 49 /* Match curr_irq_prio manually. */ + /* Administrators can always adjust */ + /* via the /proc interface. */ + +/* + * Boost the specified task from an RCU viewpoint. + * Boost the target task to a priority just a bit less-favored than + * that of the RCU-boost task, but boost to a realtime priority even + * if the RCU-boost task is running at a non-realtime priority. + * We check the priority of the RCU-boost task each time we boost + * in case the sysadm manually changes the priority. + */ +static void rcu_boost_prio(struct task_struct *taskp) +{ + unsigned long flags; + int rcuprio; + + spin_lock_irqsave(¤t->pi_lock, flags); + rcuprio = rt_mutex_getprio(current) + 1; + if (rcuprio >= MAX_USER_RT_PRIO) + rcuprio = MAX_USER_RT_PRIO - 1; + spin_unlock_irqrestore(¤t->pi_lock, flags); + spin_lock_irqsave(&taskp->pi_lock, flags); + if (taskp->rcu_prio != rcuprio) { + taskp->rcu_prio = rcuprio; + if (taskp->rcu_prio < taskp->prio) + rt_mutex_setprio(taskp, taskp->rcu_prio); + } + spin_unlock_irqrestore(&taskp->pi_lock, flags); +} + +/* + * Unboost the specified task from an RCU viewpoint. + */ +static void rcu_unboost_prio(struct task_struct *taskp) +{ + int nprio; + unsigned long flags; + + spin_lock_irqsave(&taskp->pi_lock, flags); + taskp->rcu_prio = MAX_PRIO; + nprio = rt_mutex_getprio(taskp); + if (nprio > taskp->prio) + rt_mutex_setprio(taskp, nprio); + spin_unlock_irqrestore(&taskp->pi_lock, flags); +} + +/* + * Boost all of the RCU-reader tasks on the specified list. + */ +static void rcu_boost_one_reader_list(struct rcu_boost_dat *rbdp) +{ + LIST_HEAD(list); + unsigned long flags; + struct task_struct *taskp; + + /* + * Splice both lists onto a local list. We will still + * need to hold the lock when manipulating the local list + * because tasks can remove themselves at any time. + * The reason for splicing the rbs_boosted list is that + * our priority may have changed, so reboosting may be + * required. + */ + + spin_lock_irqsave(&rbdp->rbs_lock, flags); + list_splice_init(&rbdp->rbs_toboost, &list); + list_splice_init(&rbdp->rbs_boosted, &list); + while (!list_empty(&list)) { + + /* + * Pause for a bit before boosting each task. + * @@@FIXME: reduce/eliminate pausing in case of OOM. + */ + + spin_unlock_irqrestore(&rbdp->rbs_lock, flags); + schedule_timeout_uninterruptible(1); + spin_lock_irqsave(&rbdp->rbs_lock, flags); + + /* + * All tasks might have removed themselves while + * we were waiting. Recheck list emptiness. + */ + + if (list_empty(&list)) + break; + + /* Remove first task in local list, count the attempt. */ + + taskp = list_entry(list.next, typeof(*taskp), rcub_entry); + list_del_init(&taskp->rcub_entry); + rbdp->rbs_boost_attempt++; + + /* Ignore tasks in unexpected states. */ + + if (taskp->rcub_state == RCU_BOOST_IDLE) { + list_add_tail(&taskp->rcub_entry, &rbdp->rbs_toboost); + rcu_boost_dat_stat_boost(rbdp, taskp->rcub_state); + continue; + } + + /* Boost the task's priority. */ + + rcu_boost_prio(taskp); + rbdp->rbs_boost++; + rcu_boost_dat_stat_boost(rbdp, taskp->rcub_state); + taskp->rcub_state = RCU_BOOSTED; + list_add_tail(&taskp->rcub_entry, &rbdp->rbs_boosted); + } + spin_unlock_irqrestore(&rbdp->rbs_lock, flags); +} + +/* + * Priority-boost tasks stuck in RCU read-side critical sections as + * needed (presumably rarely). + */ +static int rcu_booster(void *arg) +{ + int cpu; + struct sched_param sp = { .sched_priority = PREEMPT_RCU_BOOSTER_PRIO, }; + + sched_setscheduler(current, SCHED_RR, &sp); + current->flags |= PF_NOFREEZE; + + do { + + /* Advance the lists of tasks. */ + + rcu_boost_idx = (rcu_boost_idx + 1) % RCU_BOOST_ELEMENTS; + for_each_possible_cpu(cpu) { + + /* + * Boost all sufficiently aged readers. + * Readers must first be preempted or block + * on a mutex in an RCU read-side critical section, + * then remain in that critical section for + * RCU_BOOST_ELEMENTS-1 time intervals. + * So most of the time we should end up doing + * nothing. + */ + + rcu_boost_one_reader_list(rcu_rbd_boosting(cpu)); + + /* + * Large SMP systems may need to sleep sometimes + * in this loop. Or have multiple RCU-boost tasks. + */ + } + + /* + * Sleep to allow any unstalled RCU read-side critical + * sections to age out of the list. @@@ FIXME: reduce, + * adjust, or eliminate in case of OOM. + */ + + schedule_timeout_uninterruptible(HZ); + + /* Print stats if enough time has passed. */ + + rcu_boost_dat_stat_print(); + + } while (!kthread_should_stop()); + + return 0; +} + +/* + * Perform the portions of RCU-boost initialization that require the + * scheduler to be up and running. + */ +void init_rcu_boost_late(void) +{ + + /* Spawn RCU-boost task. */ + + printk(KERN_INFO "Starting RCU priority booster\n"); + rcu_boost_task = kthread_run(rcu_booster, NULL, "RCU Prio Booster"); + if (IS_ERR(rcu_boost_task)) + panic("Unable to create RCU Priority Booster, errno %ld\n", + -PTR_ERR(rcu_boost_task)); +} + +/* + * Update task's RCU-boost state to reflect blocking in RCU read-side + * critical section, so that the RCU-boost task can find it in case it + * later needs its priority boosted. + */ +void __rcu_preempt_boost(void) +{ + struct rcu_boost_dat *rbdp; + unsigned long flags; + + /* Identify list to place task on for possible later boosting. */ + + local_irq_save(flags); + rbdp = rcu_rbd_new(); + if (rbdp == NULL) { + local_irq_restore(flags); + printk(KERN_INFO + "Preempted RCU read-side critical section too early.\n"); + return; + } + spin_lock(&rbdp->rbs_lock); + rbdp->rbs_blocked++; + + /* + * Update state. We hold the lock and aren't yet on the list, + * so the booster cannot mess with us yet. + */ + + rcu_boost_dat_stat_block(rbdp, current->rcub_state); + if (current->rcub_state != RCU_BOOST_IDLE) { + + /* + * We have been here before, so just update stats. + * It may seem strange to do all this work just to + * accumulate statistics, but this is such a + * low-probability code path that we shouldn't care. + * If it becomes a problem, it can be fixed. + */ + + spin_unlock_irqrestore(&rbdp->rbs_lock, flags); + return; + } + current->rcub_state = RCU_BOOST_BLOCKED; + + /* Now add ourselves to the list so that the booster can find us. */ + + list_add_tail(¤t->rcub_entry, &rbdp->rbs_toboost); + current->rcub_rbdp = rbdp; + spin_unlock_irqrestore(&rbdp->rbs_lock, flags); +} + +/* + * Do the list-removal and priority-unboosting "heavy lifting" when + * required. + */ +static void __rcu_read_unlock_unboost(void) +{ + unsigned long flags; + struct rcu_boost_dat *rbdp; + + /* Identify the list structure and acquire the corresponding lock. */ + + rbdp = current->rcub_rbdp; + spin_lock_irqsave(&rbdp->rbs_lock, flags); + + /* Remove task from the list it was on. */ + + list_del_init(¤t->rcub_entry); + rbdp->rbs_unlock++; + current->rcub_rbdp = NULL; + + /* Record stats, unboost if needed, and update state. */ + + rcu_boost_dat_stat_unlock(rbdp, current->rcub_state); + if (current->rcub_state == RCU_BOOSTED) { + rcu_unboost_prio(current); + rbdp->rbs_unboosted++; + } + current->rcub_state = RCU_BOOST_IDLE; + spin_unlock_irqrestore(&rbdp->rbs_lock, flags); +} + +/* + * Do any state changes and unboosting needed for rcu_read_unlock(). + * Pass any complex work on to __rcu_read_unlock_unboost(). + * The vast majority of the time, no work will be needed, as preemption + * and blocking within RCU read-side critical sections is comparatively + * rare. + */ +static inline void rcu_read_unlock_unboost(void) +{ + + if (unlikely(current->rcub_state != RCU_BOOST_IDLE)) + __rcu_read_unlock_unboost(); +} + +#endif /* #else #ifndef CONFIG_PREEMPT_RCU_BOOST */ + /* * States for rcu_try_flip() and friends. */ @@ -128,14 +662,6 @@ static DEFINE_PER_CPU(enum rcu_mb_flag_v static cpumask_t rcu_cpu_online_map = CPU_MASK_NONE; /* - * Macro that prevents the compiler from reordering accesses, but does - * absolutely -nothing- to prevent CPUs from reordering. This is used - * only to mediate communication between mainline code and hardware - * interrupt and NMI handlers. - */ -#define ORDERED_WRT_IRQ(x) (*(volatile typeof(x) *)&(x)) - -/* * RCU_DATA_ME: find the current CPU's rcu_data structure. * RCU_DATA_CPU: find the specified CPU's rcu_data structure. */ @@ -194,7 +720,7 @@ void __rcu_read_lock(void) me->rcu_read_lock_nesting = nesting + 1; } else { - unsigned long oldirq; + unsigned long flags; /* * Disable local interrupts to prevent the grace-period @@ -203,7 +729,7 @@ void __rcu_read_lock(void) * contain rcu_read_lock(). */ - local_irq_save(oldirq); + local_irq_save(flags); /* * Outermost nesting of rcu_read_lock(), so increment @@ -233,7 +759,7 @@ void __rcu_read_lock(void) */ ORDERED_WRT_IRQ(me->rcu_flipctr_idx) = idx; - local_irq_restore(oldirq); + local_irq_restore(flags); } } EXPORT_SYMBOL_GPL(__rcu_read_lock); @@ -255,7 +781,7 @@ void __rcu_read_unlock(void) me->rcu_read_lock_nesting = nesting - 1; } else { - unsigned long oldirq; + unsigned long flags; /* * Disable local interrupts to prevent the grace-period @@ -264,7 +790,7 @@ void __rcu_read_unlock(void) * contain rcu_read_lock() and rcu_read_unlock(). */ - local_irq_save(oldirq); + local_irq_save(flags); /* * Outermost nesting of rcu_read_unlock(), so we must @@ -305,7 +831,10 @@ void __rcu_read_unlock(void) */ ORDERED_WRT_IRQ(__get_cpu_var(rcu_flipctr)[idx])--; - local_irq_restore(oldirq); + + rcu_read_unlock_unboost(); + + local_irq_restore(flags); } } EXPORT_SYMBOL_GPL(__rcu_read_unlock); @@ -504,10 +1033,10 @@ rcu_try_flip_waitmb(void) */ static void rcu_try_flip(void) { - unsigned long oldirq; + unsigned long flags; RCU_TRACE_ME(rcupreempt_trace_try_flip_1); - if (unlikely(!spin_trylock_irqsave(&rcu_ctrlblk.fliplock, oldirq))) { + if (unlikely(!spin_trylock_irqsave(&rcu_ctrlblk.fliplock, flags))) { RCU_TRACE_ME(rcupreempt_trace_try_flip_e1); return; } @@ -534,7 +1063,7 @@ static void rcu_try_flip(void) if (rcu_try_flip_waitmb()) rcu_try_flip_state = rcu_try_flip_idle_state; } - spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, oldirq); + spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, flags); } /* @@ -553,16 +1082,16 @@ static void rcu_check_mb(int cpu) void rcu_check_callbacks_rt(int cpu, int user) { - unsigned long oldirq; + unsigned long flags; struct rcu_data *rdp = RCU_DATA_CPU(cpu); rcu_check_mb(cpu); if (rcu_ctrlblk.completed == rdp->completed) rcu_try_flip(); - spin_lock_irqsave(&rdp->lock, oldirq); + spin_lock_irqsave(&rdp->lock, flags); RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp); __rcu_advance_callbacks(rdp); - spin_unlock_irqrestore(&rdp->lock, oldirq); + spin_unlock_irqrestore(&rdp->lock, flags); } /* @@ -571,18 +1100,19 @@ void rcu_check_callbacks_rt(int cpu, int */ void rcu_advance_callbacks_rt(int cpu, int user) { - unsigned long oldirq; + unsigned long flags; struct rcu_data *rdp = RCU_DATA_CPU(cpu); if (rcu_ctrlblk.completed == rdp->completed) { rcu_try_flip(); if (rcu_ctrlblk.completed == rdp->completed) return; + rcu_read_unlock_unboost(); } - spin_lock_irqsave(&rdp->lock, oldirq); + spin_lock_irqsave(&rdp->lock, flags); RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp); __rcu_advance_callbacks(rdp); - spin_unlock_irqrestore(&rdp->lock, oldirq); + spin_unlock_irqrestore(&rdp->lock, flags); } #ifdef CONFIG_HOTPLUG_CPU @@ -601,24 +1131,24 @@ void rcu_offline_cpu_rt(int cpu) { int i; struct rcu_head *list = NULL; - unsigned long oldirq; + unsigned long flags; struct rcu_data *rdp = RCU_DATA_CPU(cpu); struct rcu_head **tail = &list; /* Remove all callbacks from the newly dead CPU, retaining order. */ - spin_lock_irqsave(&rdp->lock, oldirq); + spin_lock_irqsave(&rdp->lock, flags); rcu_offline_cpu_rt_enqueue(rdp->donelist, rdp->donetail, list, tail); for (i = GP_STAGES - 1; i >= 0; i--) rcu_offline_cpu_rt_enqueue(rdp->waitlist[i], rdp->waittail[i], list, tail); rcu_offline_cpu_rt_enqueue(rdp->nextlist, rdp->nexttail, list, tail); - spin_unlock_irqrestore(&rdp->lock, oldirq); + spin_unlock_irqrestore(&rdp->lock, flags); rdp->waitlistcount = 0; /* Disengage the newly dead CPU from grace-period computation. */ - spin_lock_irqsave(&rcu_ctrlblk.fliplock, oldirq); + spin_lock_irqsave(&rcu_ctrlblk.fliplock, flags); rcu_check_mb(cpu); if (per_cpu(rcu_flip_flag, cpu) == rcu_flipped) { smp_mb(); /* Subsequent counter accesses must see new value */ @@ -627,7 +1157,7 @@ void rcu_offline_cpu_rt(int cpu) /* seen -after- acknowledgement. */ } cpu_clear(cpu, rcu_cpu_online_map); - spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, oldirq); + spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, flags); /* * Place the removed callbacks on the current CPU's queue. @@ -640,20 +1170,20 @@ void rcu_offline_cpu_rt(int cpu) */ rdp = RCU_DATA_ME(); - spin_lock_irqsave(&rdp->lock, oldirq); + spin_lock_irqsave(&rdp->lock, flags); *rdp->nexttail = list; if (list) rdp->nexttail = tail; - spin_unlock_irqrestore(&rdp->lock, oldirq); + spin_unlock_irqrestore(&rdp->lock, flags); } void __devinit rcu_online_cpu_rt(int cpu) { - unsigned long oldirq; + unsigned long flags; - spin_lock_irqsave(&rcu_ctrlblk.fliplock, oldirq); + spin_lock_irqsave(&rcu_ctrlblk.fliplock, flags); cpu_set(cpu, rcu_cpu_online_map); - spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, oldirq); + spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, flags); } #else /* #ifdef CONFIG_HOTPLUG_CPU */ @@ -695,12 +1225,12 @@ void rcu_process_callbacks_rt(struct sof void fastcall call_rcu_preempt(struct rcu_head *head, void (*func)(struct rcu_head *rcu)) { - unsigned long oldirq; + unsigned long flags; struct rcu_data *rdp; head->func = func; head->next = NULL; - local_irq_save(oldirq); + local_irq_save(flags); rdp = RCU_DATA_ME(); spin_lock(&rdp->lock); __rcu_advance_callbacks(rdp); @@ -708,7 +1238,7 @@ void fastcall call_rcu_preempt(struct rc rdp->nexttail = &head->next; RCU_TRACE_RDP(rcupreempt_trace_next_add, rdp); spin_unlock(&rdp->lock); - local_irq_restore(oldirq); + local_irq_restore(flags); } EXPORT_SYMBOL_GPL(call_rcu_preempt); @@ -757,6 +1287,11 @@ int rcu_pending_rt(int cpu) return 0; } +/* + * Initialize RCU. This is called very early in boot, so is restricted + * to very simple operations. Don't even think about messing with anything + * that involves the scheduler, as it doesn't exist yet. + */ void __init rcu_init_rt(void) { int cpu; @@ -778,6 +1313,7 @@ void __init rcu_init_rt(void) rdp->donelist = NULL; rdp->donetail = &rdp->donelist; } + init_rcu_boost_early(); } /* diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/kernel/rtmutex.c linux-2.6.22-F-boostrcu/kernel/rtmutex.c --- linux-2.6.22-E-hotplug/kernel/rtmutex.c 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-F-boostrcu/kernel/rtmutex.c 2007-08-24 11:24:59.000000000 -0700 @@ -111,11 +111,12 @@ static inline void mark_rt_mutex_waiters */ int rt_mutex_getprio(struct task_struct *task) { + int prio = min(task->normal_prio, get_rcu_prio(task)); + if (likely(!task_has_pi_waiters(task))) - return task->normal_prio; + return prio; - return min(task_top_pi_waiter(task)->pi_list_entry.prio, - task->normal_prio); + return min(task_top_pi_waiter(task)->pi_list_entry.prio, prio); } /* diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/kernel/sched.c linux-2.6.22-F-boostrcu/kernel/sched.c --- linux-2.6.22-E-hotplug/kernel/sched.c 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-F-boostrcu/kernel/sched.c 2007-08-24 11:24:59.000000000 -0700 @@ -1702,6 +1702,7 @@ void fastcall sched_fork(struct task_str * Make sure we do not leak PI boosting priority to the child: */ p->prio = current->normal_prio; + set_rcu_prio(p, MAX_PRIO); INIT_LIST_HEAD(&p->run_list); p->array = NULL; @@ -1784,6 +1785,7 @@ void fastcall wake_up_new_task(struct ta else { p->prio = current->prio; p->normal_prio = current->normal_prio; + set_rcu_prio(p, MAX_PRIO); list_add_tail(&p->run_list, ¤t->run_list); p->array = current->array; p->array->nr_active++; @@ -3590,6 +3592,8 @@ asmlinkage void __sched schedule(void) } profile_hit(SCHED_PROFILING, __builtin_return_address(0)); + rcu_preempt_boost(); + need_resched: preempt_disable(); prev = current; @@ -5060,6 +5064,7 @@ void __cpuinit init_idle(struct task_str idle->sleep_avg = 0; idle->array = NULL; idle->prio = idle->normal_prio = MAX_PRIO; + set_rcu_prio(idle, MAX_PRIO); idle->state = TASK_RUNNING; idle->cpus_allowed = cpumask_of_cpu(cpu); set_task_cpu(idle, cpu); diff -urpNa -X dontdiff linux-2.6.22-E-hotplug/lib/Kconfig.debug linux-2.6.22-F-boostrcu/lib/Kconfig.debug --- linux-2.6.22-E-hotplug/lib/Kconfig.debug 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-F-boostrcu/lib/Kconfig.debug 2007-08-24 11:24:59.000000000 -0700 @@ -391,6 +391,40 @@ config RCU_TORTURE_TEST Say M if you want the RCU torture tests to build as a module. Say N if you are unsure. +config RCU_TRACE + bool "Enable tracing for RCU - currently stats in debugfs" + select DEBUG_FS + depends on DEBUG_KERNEL + default y + help + This option provides tracing in RCU which presents stats + in debugfs for debugging RCU implementation. + + Say Y here if you want to enable RCU tracing + Say N if you are unsure. + +config PREEMPT_RCU_BOOST_STATS + bool "Enable RCU priority-boosting statistic printing" + depends on PREEMPT_RCU_BOOST + depends on DEBUG_KERNEL + default n + help + This option enables debug printk()s of RCU boost statistics, + which are normally only used to debug RCU priority boost + implementations. + + Say N if you are unsure. + +config PREEMPT_RCU_BOOST_STATS_INTERVAL + int "RCU priority-boosting statistic printing interval (seconds)" + depends on PREEMPT_RCU_BOOST_STATS + default 100 + range 10 86400 + help + This option controls the timing of debug printk()s of RCU boost + statistics, which are normally only used to debug RCU priority + boost implementations. + config LKDTM tristate "Linux Kernel Dump Test Tool Module" depends on DEBUG_KERNEL ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 7/8] RCU: rcutorture testing for RCU priority boosting 2007-09-05 21:38 ` [PATCH RFC 6/8] RCU priority boosting " Paul E. McKenney @ 2007-09-05 21:39 ` Paul E. McKenney 2007-09-05 21:39 ` [PATCH RFC 8/8] RCU: Make RCU priority boosting consume less power Paul E. McKenney 0 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:39 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. Still uses xtime because this patch is still against 2.6.22. This patch modifies rcutorture to also torture RCU priority boosting. The torturing involves forcing RCU read-side critical sections (already performed as part of the torturing of RCU) to run for extremely long time periods, increasing the probability of their being preempted and thus needing priority boosting. The fact that rcutorture's "nreaders" module parameter defaults to twice the number of CPUs helps ensure lots of the needed preemption. Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- rcutorture.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 77 insertions(+), 14 deletions(-) diff -urpNa -X dontdiff linux-2.6.22-f-boost/kernel/rcutorture.c linux-2.6.22-g-boosttorture/kernel/rcutorture.c --- linux-2.6.22-f-boost/kernel/rcutorture.c 2007-07-08 16:32:17.000000000 -0700 +++ linux-2.6.22-g-boosttorture/kernel/rcutorture.c 2007-08-22 16:18:32.000000000 -0700 @@ -58,6 +58,7 @@ static int stat_interval; /* Interval be static int verbose; /* Print more debug info. */ static int test_no_idle_hz; /* Test RCU's support for tickless idle CPUs. */ static int shuffle_interval = 5; /* Interval between shuffles (in sec)*/ +static int preempt_torture; /* Realtime task preempts torture readers. */ static char *torture_type = "rcu"; /* What RCU implementation to torture. */ module_param(nreaders, int, 0444); @@ -72,6 +73,8 @@ module_param(test_no_idle_hz, bool, 0444 MODULE_PARM_DESC(test_no_idle_hz, "Test support for tickless idle CPUs"); module_param(shuffle_interval, int, 0444); MODULE_PARM_DESC(shuffle_interval, "Number of seconds between shuffles"); +module_param(preempt_torture, bool, 0444); +MODULE_PARM_DESC(preempt_torture, "Enable realtime preemption torture"); module_param(torture_type, charp, 0444); MODULE_PARM_DESC(torture_type, "Type of RCU to torture (rcu, rcu_bh, srcu)"); @@ -194,6 +197,8 @@ struct rcu_torture_ops { int (*completed)(void); void (*deferredfree)(struct rcu_torture *p); void (*sync)(void); + long (*preemptstart)(void); + void (*preemptend)(void); int (*stats)(char *page); char *name; }; @@ -258,16 +263,75 @@ static void rcu_torture_deferred_free(st call_rcu(&p->rtort_rcu, rcu_torture_cb); } +static struct task_struct *rcu_preeempt_task; +static unsigned long rcu_torture_preempt_errors; + +static int rcu_torture_preempt(void *arg) +{ + int completedstart; + int err; + time_t gcstart; + struct sched_param sp; + + sp.sched_priority = MAX_RT_PRIO - 1; + err = sched_setscheduler(current, SCHED_RR, &sp); + if (err != 0) + printk(KERN_ALERT "rcu_torture_preempt() priority err: %d\n", + err); + current->flags |= PF_NOFREEZE; + + do { + completedstart = rcu_torture_completed(); + gcstart = xtime.tv_sec; + while ((xtime.tv_sec - gcstart < 10) && + (rcu_torture_completed() == completedstart)) + cond_resched(); + if (rcu_torture_completed() == completedstart) + rcu_torture_preempt_errors++; + schedule_timeout_interruptible(HZ); + } while (!kthread_should_stop()); + return 0; +} + +static long rcu_preempt_start(void) +{ + long retval = 0; + + rcu_preeempt_task = kthread_run(rcu_torture_preempt, NULL, + "rcu_torture_preempt"); + if (IS_ERR(rcu_preeempt_task)) { + VERBOSE_PRINTK_ERRSTRING("Failed to create preempter"); + retval = PTR_ERR(rcu_preeempt_task); + rcu_preeempt_task = NULL; + } + return retval; +} + +static void rcu_preempt_end(void) +{ + if (rcu_preeempt_task != NULL) { + VERBOSE_PRINTK_STRING("Stopping rcu_preempt task"); + kthread_stop(rcu_preeempt_task); + } + rcu_preeempt_task = NULL; +} + +static int rcu_preempt_stats(char *page) +{ + return sprintf(page, + "Preemption stalls: %lu\n", rcu_torture_preempt_errors); +} + static struct rcu_torture_ops rcu_ops = { - .init = NULL, - .cleanup = NULL, .readlock = rcu_torture_read_lock, .readdelay = rcu_read_delay, .readunlock = rcu_torture_read_unlock, .completed = rcu_torture_completed, .deferredfree = rcu_torture_deferred_free, .sync = synchronize_rcu, - .stats = NULL, + .preemptstart = rcu_preempt_start, + .preemptend = rcu_preempt_end, + .stats = rcu_preempt_stats, .name = "rcu" }; @@ -299,14 +363,12 @@ static void rcu_sync_torture_init(void) static struct rcu_torture_ops rcu_sync_ops = { .init = rcu_sync_torture_init, - .cleanup = NULL, .readlock = rcu_torture_read_lock, .readdelay = rcu_read_delay, .readunlock = rcu_torture_read_unlock, .completed = rcu_torture_completed, .deferredfree = rcu_sync_torture_deferred_free, .sync = synchronize_rcu, - .stats = NULL, .name = "rcu_sync" }; @@ -358,28 +420,23 @@ static void rcu_bh_torture_synchronize(v } static struct rcu_torture_ops rcu_bh_ops = { - .init = NULL, - .cleanup = NULL, .readlock = rcu_bh_torture_read_lock, .readdelay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = rcu_bh_torture_read_unlock, .completed = rcu_bh_torture_completed, .deferredfree = rcu_bh_torture_deferred_free, .sync = rcu_bh_torture_synchronize, - .stats = NULL, .name = "rcu_bh" }; static struct rcu_torture_ops rcu_bh_sync_ops = { .init = rcu_sync_torture_init, - .cleanup = NULL, .readlock = rcu_bh_torture_read_lock, .readdelay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = rcu_bh_torture_read_unlock, .completed = rcu_bh_torture_completed, .deferredfree = rcu_sync_torture_deferred_free, .sync = rcu_bh_torture_synchronize, - .stats = NULL, .name = "rcu_bh_sync" }; @@ -491,14 +548,12 @@ static void sched_torture_synchronize(vo static struct rcu_torture_ops sched_ops = { .init = rcu_sync_torture_init, - .cleanup = NULL, .readlock = sched_torture_read_lock, .readdelay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, .completed = sched_torture_completed, .deferredfree = rcu_sync_torture_deferred_free, .sync = sched_torture_synchronize, - .stats = NULL, .name = "sched" }; @@ -793,9 +848,10 @@ rcu_torture_print_module_parms(char *tag printk(KERN_ALERT "%s" TORTURE_FLAG "--- %s: nreaders=%d nfakewriters=%d " "stat_interval=%d verbose=%d test_no_idle_hz=%d " - "shuffle_interval = %d\n", + "shuffle_interval=%d preempt_torture=%d\n", torture_type, tag, nrealreaders, nfakewriters, - stat_interval, verbose, test_no_idle_hz, shuffle_interval); + stat_interval, verbose, test_no_idle_hz, shuffle_interval, + preempt_torture); } static void @@ -848,6 +904,8 @@ rcu_torture_cleanup(void) kthread_stop(stats_task); } stats_task = NULL; + if (preempt_torture && (cur_ops->preemptend != NULL)) + cur_ops->preemptend(); /* Wait for all RCU callbacks to fire. */ rcu_barrier(); @@ -990,6 +1048,11 @@ rcu_torture_init(void) goto unwind; } } + if (preempt_torture && (cur_ops->preemptstart != NULL)) { + firsterr = cur_ops->preemptstart(); + if (firsterr != 0) + goto unwind; + } return 0; unwind: ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH RFC 8/8] RCU: Make RCU priority boosting consume less power 2007-09-05 21:39 ` [PATCH RFC 7/8] RCU: rcutorture testing for RCU priority boosting Paul E. McKenney @ 2007-09-05 21:39 ` Paul E. McKenney 0 siblings, 0 replies; 9+ messages in thread From: Paul E. McKenney @ 2007-09-05 21:39 UTC (permalink / raw) To: linux-kernel Cc: linux-rt-users, mingo, akpm, dipankar, josht, tytso, dvhltc, tglx, a.p.zijlstra, bunk, ego, oleg, srostedt Work in progress, not for inclusion. This patch modified the RCU priority booster to explicitly sleep when there are no RCU readers in need of priority boosting. This should be a power-consumption improvement over the one-second polling cycle in the underlying RCU priority-boosting patch. Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> --- include/linux/rcupreempt.h | 15 ++++++ kernel/rcupreempt.c | 102 ++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 115 insertions(+), 2 deletions(-) diff -urpNa -X dontdiff linux-2.6.22-G-boosttorture/include/linux/rcupreempt.h linux-2.6.22-H-boostsleep/include/linux/rcupreempt.h --- linux-2.6.22-G-boosttorture/include/linux/rcupreempt.h 2007-08-24 11:24:59.000000000 -0700 +++ linux-2.6.22-H-boostsleep/include/linux/rcupreempt.h 2007-08-24 18:12:41.000000000 -0700 @@ -60,6 +60,21 @@ enum rcu_boost_state { #define N_RCU_BOOST_STATE (RCU_BOOST_INVALID + 1) +/* + * RCU-booster state with respect to sleeping. The RCU booster + * sleeps when no task has recently been seen sleeping in an RCU + * read-side critical section, and is awakened when a new sleeper + * appears. + */ +enum rcu_booster_state { + RCU_BOOSTER_ACTIVE = 0, /* RCU booster actively scanning. */ + RCU_BOOSTER_DROWSY = 1, /* RCU booster is considering sleeping. */ + RCU_BOOSTER_SLEEPING = 2, /* RCU booster is asleep. */ + RCU_BOOSTER_INVALID = 3, /* For bogus state sightings. */ +}; + +#define N_RCU_BOOSTER_STATE (RCU_BOOSTER_INVALID + 1) + #endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST */ #define call_rcu_bh(head, rcu) call_rcu(head, rcu) diff -urpNa -X dontdiff linux-2.6.22-G-boosttorture/kernel/rcupreempt.c linux-2.6.22-H-boostsleep/kernel/rcupreempt.c --- linux-2.6.22-G-boosttorture/kernel/rcupreempt.c 2007-08-27 15:42:57.000000000 -0700 +++ linux-2.6.22-H-boostsleep/kernel/rcupreempt.c 2007-08-27 15:42:37.000000000 -0700 @@ -108,6 +108,7 @@ struct rcu_boost_dat { unsigned long rbs_unboosted; #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS unsigned long rbs_stats[N_RCU_BOOST_DAT_EVENTS][N_RCU_BOOST_STATE]; + unsigned long rbs_qw_stats[N_RCU_BOOSTER_STATE]; #endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */ }; #define RCU_BOOST_ELEMENTS 4 @@ -115,6 +116,10 @@ struct rcu_boost_dat { static int rcu_boost_idx = -1; /* invalid value for early RCU use. */ static DEFINE_PER_CPU(struct rcu_boost_dat, rcu_boost_dat[RCU_BOOST_ELEMENTS]); static struct task_struct *rcu_boost_task; +static DEFINE_SPINLOCK(rcu_boost_quiesce_lock); +static enum rcu_booster_state rcu_booster_quiesce_state = RCU_BOOSTER_ACTIVE; +static unsigned long rbs_qs_stats[2][N_RCU_BOOSTER_STATE]; +wait_queue_head_t rcu_booster_quiesce_wq; #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS @@ -171,6 +176,15 @@ static char *rcu_boost_state_error[] = { "? ?", /* unlock */ }; +/* Labels for RCU booster state printout. */ + +static char *rcu_booster_state_label[] = { + "Active", + "Drowsy", + "Sleeping", + "???", +}; + /* * Print out RCU booster task statistics at the specified interval. */ @@ -221,6 +235,14 @@ static void rcu_boost_dat_stat_print(voi cpu)[i].rbs_stats[event][state]; } } + for (state = 0; state < N_RCU_BOOSTER_STATE; state++) { + sum.rbs_qw_stats[state] = 0; + for_each_possible_cpu(cpu) + for (i = 0; i < RCU_BOOST_ELEMENTS; i++) + sum.rbs_qw_stats[state] += + per_cpu(rcu_boost_dat, + cpu)[i].rbs_qw_stats[state]; + } /* Print them out! */ @@ -240,6 +262,24 @@ static void rcu_boost_dat_stat_print(voi rcu_boost_state_event[event], buf); } + printk(KERN_INFO "RCU booster state: %s\n", + rcu_booster_quiesce_state >= 0 && + rcu_booster_quiesce_state < N_RCU_BOOSTER_STATE + ? rcu_booster_state_label[rcu_booster_quiesce_state] + : "???"); + i = 0; + for (state = 0; state < N_RCU_BOOSTER_STATE; state++) + i += sprintf(&buf[i], " %ld", rbs_qs_stats[0][state]); + printk(KERN_INFO "No tasks found: %s\n", buf); + i = 0; + for (state = 0; state < N_RCU_BOOSTER_STATE; state++) + i += sprintf(&buf[i], " %ld", rbs_qs_stats[1][state]); + printk(KERN_INFO "Tasks found: %s\n", buf); + i = 0; + for (state = 0; state < N_RCU_BOOSTER_STATE; state++) + i += sprintf(&buf[i], " %ld", sum.rbs_qw_stats[state]); + printk(KERN_INFO "Awaken opportunities: %s\n", buf); + /* Go away and don't come back for awhile. */ lastprint = xtime.tv_sec; @@ -293,6 +333,8 @@ static void init_rcu_boost_early(void) for (j = 0; j < N_RCU_BOOST_DAT_EVENTS; j++) for (k = 0; k < N_RCU_BOOST_STATE; k++) rbdp[i].rbs_stats[j][k] = 0; + for (j = 0; j < N_RCU_BOOSTER_STATE; j++) + rbdp[i].rbs_qw_stats[j] = 0; } #endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */ } @@ -378,10 +420,11 @@ static void rcu_unboost_prio(struct task /* * Boost all of the RCU-reader tasks on the specified list. */ -static void rcu_boost_one_reader_list(struct rcu_boost_dat *rbdp) +static int rcu_boost_one_reader_list(struct rcu_boost_dat *rbdp) { LIST_HEAD(list); unsigned long flags; + int retval = 0; struct task_struct *taskp; /* @@ -397,6 +440,7 @@ static void rcu_boost_one_reader_list(st list_splice_init(&rbdp->rbs_toboost, &list); list_splice_init(&rbdp->rbs_boosted, &list); while (!list_empty(&list)) { + retval = 1; /* * Pause for a bit before boosting each task. @@ -438,6 +482,36 @@ static void rcu_boost_one_reader_list(st list_add_tail(&taskp->rcub_entry, &rbdp->rbs_boosted); } spin_unlock_irqrestore(&rbdp->rbs_lock, flags); + return retval; +} + +/* + * Examine state to see if it is time to sleep. + */ +static void rcu_booster_try_sleep(int yo) +{ + spin_lock(&rcu_boost_quiesce_lock); + if (rcu_booster_quiesce_state < 0 || + rcu_booster_quiesce_state >= N_RCU_BOOSTER_STATE) + rcu_booster_quiesce_state = RCU_BOOST_INVALID; + rbs_qs_stats[yo != 0][rcu_booster_quiesce_state]++; + if (yo != 0) { + rcu_booster_quiesce_state = RCU_BOOSTER_ACTIVE; + } else { + if (rcu_booster_quiesce_state == RCU_BOOSTER_ACTIVE) { + rcu_booster_quiesce_state = RCU_BOOSTER_DROWSY; + } else if (rcu_booster_quiesce_state == RCU_BOOSTER_DROWSY) { + rcu_booster_quiesce_state = RCU_BOOSTER_SLEEPING; + spin_unlock(&rcu_boost_quiesce_lock); + __wait_event(rcu_booster_quiesce_wq, + rcu_booster_quiesce_state == + RCU_BOOSTER_ACTIVE); + spin_lock(&rcu_boost_quiesce_lock); + } else { + rcu_booster_quiesce_state = RCU_BOOSTER_ACTIVE; + } + } + spin_unlock(&rcu_boost_quiesce_lock); } /* @@ -448,15 +522,21 @@ static int rcu_booster(void *arg) { int cpu; struct sched_param sp = { .sched_priority = PREEMPT_RCU_BOOSTER_PRIO, }; + int yo = 0; sched_setscheduler(current, SCHED_RR, &sp); current->flags |= PF_NOFREEZE; + init_waitqueue_head(&rcu_booster_quiesce_wq); do { /* Advance the lists of tasks. */ rcu_boost_idx = (rcu_boost_idx + 1) % RCU_BOOST_ELEMENTS; + if (rcu_boost_idx == 0) { + rcu_booster_try_sleep(yo); + yo = 0; + } for_each_possible_cpu(cpu) { /* @@ -469,7 +549,7 @@ static int rcu_booster(void *arg) * nothing. */ - rcu_boost_one_reader_list(rcu_rbd_boosting(cpu)); + yo += rcu_boost_one_reader_list(rcu_rbd_boosting(cpu)); /* * Large SMP systems may need to sleep sometimes @@ -511,6 +591,23 @@ void init_rcu_boost_late(void) } /* + * Awaken the RCU priority booster if neecessary. + */ +static void rcu_preempt_wake(struct rcu_boost_dat *rbdp) +{ + spin_lock(&rcu_boost_quiesce_lock); + if (rcu_booster_quiesce_state >= N_RCU_BOOSTER_STATE) + rcu_booster_quiesce_state = RCU_BOOSTER_INVALID; + rbdp->rbs_qw_stats[rcu_booster_quiesce_state]++; + if (rcu_booster_quiesce_state == RCU_BOOSTER_SLEEPING) { + rcu_booster_quiesce_state = RCU_BOOSTER_ACTIVE; + wake_up(&rcu_booster_quiesce_wq); + } else if (rcu_booster_quiesce_state != RCU_BOOSTER_ACTIVE) + rcu_booster_quiesce_state = RCU_BOOSTER_ACTIVE; + spin_unlock(&rcu_boost_quiesce_lock); +} + +/* * Update task's RCU-boost state to reflect blocking in RCU read-side * critical section, so that the RCU-boost task can find it in case it * later needs its priority boosted. @@ -532,6 +629,7 @@ void __rcu_preempt_boost(void) } spin_lock(&rbdp->rbs_lock); rbdp->rbs_blocked++; + rcu_preempt_wake(rbdp); /* * Update state. We hold the lock and aren't yet on the list, ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2007-09-05 21:40 UTC | newest] Thread overview: 9+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2007-09-05 21:31 [PATCH RFC 0/8] RCU: Preemptible RCU Paul E. McKenney 2007-09-05 21:32 ` [PATCH RFC 1/8] RCU: Split API to permit multiple RCU implementations Paul E. McKenney 2007-09-05 21:33 ` [PATCH RFC 2/8] RCU: Fix barriers Paul E. McKenney 2007-09-05 21:34 ` [PATCH RFC 3/8] RCU: Preemptible RCU Paul E. McKenney 2007-09-05 21:36 ` [PATCH RFC 4/8] RCU: synchronize_sched() workaround for CPU hotplug Paul E. McKenney 2007-09-05 21:37 ` [PATCH RFC 5/8] RCU: CPU hotplug support for preemptible RCU Paul E. McKenney 2007-09-05 21:38 ` [PATCH RFC 6/8] RCU priority boosting " Paul E. McKenney 2007-09-05 21:39 ` [PATCH RFC 7/8] RCU: rcutorture testing for RCU priority boosting Paul E. McKenney 2007-09-05 21:39 ` [PATCH RFC 8/8] RCU: Make RCU priority boosting consume less power Paul E. McKenney
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox