blob: 636af6d9c6e565ca6e6d7010941501901c8322b4 [file] [log] [blame]
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -07001/*
2 * Read-Copy Update mechanism for mutual exclusion, the Bloatwatch edition.
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 *
18 * Copyright IBM Corporation, 2008
19 *
20 * Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
21 *
22 * For detailed explanation of Read-Copy Update mechanism see -
Ingo Molnar4ce5b902009-10-26 07:55:55 +010023 * Documentation/RCU
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070024 */
Ingo Molnar4ce5b902009-10-26 07:55:55 +010025#include <linux/completion.h>
26#include <linux/interrupt.h>
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070027#include <linux/notifier.h>
Ingo Molnar4ce5b902009-10-26 07:55:55 +010028#include <linux/rcupdate.h>
29#include <linux/kernel.h>
Paul Gortmaker9984de12011-05-23 14:51:41 -040030#include <linux/export.h>
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070031#include <linux/mutex.h>
Ingo Molnar4ce5b902009-10-26 07:55:55 +010032#include <linux/sched.h>
33#include <linux/types.h>
34#include <linux/init.h>
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070035#include <linux/time.h>
Ingo Molnar4ce5b902009-10-26 07:55:55 +010036#include <linux/cpu.h>
Linus Torvalds268bb0c2011-05-20 12:50:29 -070037#include <linux/prefetch.h>
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070038
Paul E. McKenney29c00b42011-06-17 15:53:19 -070039#ifdef CONFIG_RCU_TRACE
Paul E. McKenney29c00b42011-06-17 15:53:19 -070040#include <trace/events/rcu.h>
Paul E. McKenney29c00b42011-06-17 15:53:19 -070041#endif /* #else #ifdef CONFIG_RCU_TRACE */
42
43#include "rcu.h"
44
Paul E. McKenneya57eb942010-06-29 16:49:16 -070045/* Forward declarations for rcutiny_plugin.h. */
Paul E. McKenney24278d12010-09-27 17:25:23 -070046struct rcu_ctrlblk;
Paul E. McKenney965a0022011-06-18 09:55:39 -070047static void invoke_rcu_callbacks(void);
48static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp);
49static void rcu_process_callbacks(struct softirq_action *unused);
Paul E. McKenneya57eb942010-06-29 16:49:16 -070050static void __call_rcu(struct rcu_head *head,
51 void (*func)(struct rcu_head *rcu),
52 struct rcu_ctrlblk *rcp);
53
54#include "rcutiny_plugin.h"
55
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070056#ifdef CONFIG_NO_HZ
57
58static long rcu_dynticks_nesting = 1;
59
60/*
61 * Enter dynticks-idle mode, which is an extended quiescent state
62 * if we have fully entered that mode (i.e., if the new value of
63 * dynticks_nesting is zero).
64 */
65void rcu_enter_nohz(void)
66{
67 if (--rcu_dynticks_nesting == 0)
68 rcu_sched_qs(0); /* implies rcu_bh_qsctr_inc(0) */
69}
70
71/*
72 * Exit dynticks-idle mode, so that we are no longer in an extended
73 * quiescent state.
74 */
75void rcu_exit_nohz(void)
76{
77 rcu_dynticks_nesting++;
78}
79
80#endif /* #ifdef CONFIG_NO_HZ */
81
82/*
Eric Dumazetb554d7de2011-04-28 07:23:45 +020083 * Helper function for rcu_sched_qs() and rcu_bh_qs().
84 * Also irqs are disabled to avoid confusion due to interrupt handlers
Ingo Molnar4ce5b902009-10-26 07:55:55 +010085 * invoking call_rcu().
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070086 */
87static int rcu_qsctr_help(struct rcu_ctrlblk *rcp)
88{
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070089 if (rcp->rcucblist != NULL &&
90 rcp->donetail != rcp->curtail) {
91 rcp->donetail = rcp->curtail;
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070092 return 1;
93 }
Ingo Molnar4ce5b902009-10-26 07:55:55 +010094
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -070095 return 0;
96}
97
98/*
99 * Record an rcu quiescent state. And an rcu_bh quiescent state while we
100 * are at it, given that any rcu quiescent state is also an rcu_bh
101 * quiescent state. Use "+" instead of "||" to defeat short circuiting.
102 */
103void rcu_sched_qs(int cpu)
104{
Eric Dumazetb554d7de2011-04-28 07:23:45 +0200105 unsigned long flags;
106
107 local_irq_save(flags);
Paul E. McKenney99652b52010-03-30 15:50:01 -0700108 if (rcu_qsctr_help(&rcu_sched_ctrlblk) +
109 rcu_qsctr_help(&rcu_bh_ctrlblk))
Paul E. McKenney965a0022011-06-18 09:55:39 -0700110 invoke_rcu_callbacks();
Eric Dumazetb554d7de2011-04-28 07:23:45 +0200111 local_irq_restore(flags);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700112}
113
114/*
115 * Record an rcu_bh quiescent state.
116 */
117void rcu_bh_qs(int cpu)
118{
Eric Dumazetb554d7de2011-04-28 07:23:45 +0200119 unsigned long flags;
120
121 local_irq_save(flags);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700122 if (rcu_qsctr_help(&rcu_bh_ctrlblk))
Paul E. McKenney965a0022011-06-18 09:55:39 -0700123 invoke_rcu_callbacks();
Eric Dumazetb554d7de2011-04-28 07:23:45 +0200124 local_irq_restore(flags);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700125}
126
127/*
128 * Check to see if the scheduling-clock interrupt came from an extended
129 * quiescent state, and, if so, tell RCU about it.
130 */
131void rcu_check_callbacks(int cpu, int user)
132{
133 if (user ||
134 (idle_cpu(cpu) &&
135 !in_softirq() &&
136 hardirq_count() <= (1 << HARDIRQ_SHIFT)))
137 rcu_sched_qs(cpu);
138 else if (!in_softirq())
139 rcu_bh_qs(cpu);
Paul E. McKenneya57eb942010-06-29 16:49:16 -0700140 rcu_preempt_check_callbacks();
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700141}
142
143/*
Paul E. McKenneyb2c07102010-09-09 13:40:39 -0700144 * Invoke the RCU callbacks on the specified rcu_ctrlkblk structure
145 * whose grace period has elapsed.
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700146 */
Paul E. McKenney965a0022011-06-18 09:55:39 -0700147static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700148{
Paul E. McKenneyd4c08f22011-06-25 06:36:56 -0700149 char *rn = NULL;
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700150 struct rcu_head *next, *list;
Ingo Molnar4ce5b902009-10-26 07:55:55 +0100151 unsigned long flags;
Paul E. McKenney9e571a82010-09-30 21:26:52 -0700152 RCU_TRACE(int cb_count = 0);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700153
154 /* If no RCU callbacks ready to invoke, just return. */
Paul E. McKenney29c00b42011-06-17 15:53:19 -0700155 if (&rcp->rcucblist == rcp->donetail) {
Paul E. McKenney72fe7012011-06-21 01:14:54 -0700156 RCU_TRACE(trace_rcu_batch_start(rcp->name, 0, -1));
157 RCU_TRACE(trace_rcu_batch_end(rcp->name, 0));
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700158 return;
Paul E. McKenney29c00b42011-06-17 15:53:19 -0700159 }
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700160
161 /* Move the ready-to-invoke callbacks to a local list. */
162 local_irq_save(flags);
Paul E. McKenney72fe7012011-06-21 01:14:54 -0700163 RCU_TRACE(trace_rcu_batch_start(rcp->name, 0, -1));
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700164 list = rcp->rcucblist;
165 rcp->rcucblist = *rcp->donetail;
166 *rcp->donetail = NULL;
167 if (rcp->curtail == rcp->donetail)
168 rcp->curtail = &rcp->rcucblist;
Paul E. McKenneya57eb942010-06-29 16:49:16 -0700169 rcu_preempt_remove_callbacks(rcp);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700170 rcp->donetail = &rcp->rcucblist;
171 local_irq_restore(flags);
172
173 /* Invoke the callbacks on the local list. */
Paul E. McKenneyd4c08f22011-06-25 06:36:56 -0700174 RCU_TRACE(rn = rcp->name);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700175 while (list) {
176 next = list->next;
177 prefetch(next);
Mathieu Desnoyers551d55a2010-04-17 08:48:42 -0400178 debug_rcu_head_unqueue(list);
Paul E. McKenneyb2c07102010-09-09 13:40:39 -0700179 local_bh_disable();
Paul E. McKenneyd4c08f22011-06-25 06:36:56 -0700180 __rcu_reclaim(rn, list);
Paul E. McKenneyb2c07102010-09-09 13:40:39 -0700181 local_bh_enable();
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700182 list = next;
Paul E. McKenney9e571a82010-09-30 21:26:52 -0700183 RCU_TRACE(cb_count++);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700184 }
Paul E. McKenney9e571a82010-09-30 21:26:52 -0700185 RCU_TRACE(rcu_trace_sub_qlen(rcp, cb_count));
Paul E. McKenney72fe7012011-06-21 01:14:54 -0700186 RCU_TRACE(trace_rcu_batch_end(rcp->name, cb_count));
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700187}
188
Paul E. McKenney965a0022011-06-18 09:55:39 -0700189static void rcu_process_callbacks(struct softirq_action *unused)
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700190{
Paul E. McKenney965a0022011-06-18 09:55:39 -0700191 __rcu_process_callbacks(&rcu_sched_ctrlblk);
192 __rcu_process_callbacks(&rcu_bh_ctrlblk);
193 rcu_preempt_process_callbacks();
Paul E. McKenneyb2c07102010-09-09 13:40:39 -0700194}
195
196/*
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700197 * Wait for a grace period to elapse. But it is illegal to invoke
198 * synchronize_sched() from within an RCU read-side critical section.
199 * Therefore, any legal call to synchronize_sched() is a quiescent
200 * state, and so on a UP system, synchronize_sched() need do nothing.
201 * Ditto for synchronize_rcu_bh(). (But Lai Jiangshan points out the
202 * benefits of doing might_sleep() to reduce latency.)
203 *
204 * Cool, huh? (Due to Josh Triplett.)
205 *
Paul E. McKenneyda848c42010-03-30 15:46:01 -0700206 * But we want to make this a static inline later. The cond_resched()
207 * currently makes this problematic.
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700208 */
209void synchronize_sched(void)
210{
211 cond_resched();
212}
213EXPORT_SYMBOL_GPL(synchronize_sched);
214
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700215/*
216 * Helper function for call_rcu() and call_rcu_bh().
217 */
218static void __call_rcu(struct rcu_head *head,
219 void (*func)(struct rcu_head *rcu),
220 struct rcu_ctrlblk *rcp)
221{
222 unsigned long flags;
223
Mathieu Desnoyers551d55a2010-04-17 08:48:42 -0400224 debug_rcu_head_queue(head);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700225 head->func = func;
226 head->next = NULL;
Ingo Molnar4ce5b902009-10-26 07:55:55 +0100227
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700228 local_irq_save(flags);
229 *rcp->curtail = head;
230 rcp->curtail = &head->next;
Paul E. McKenney9e571a82010-09-30 21:26:52 -0700231 RCU_TRACE(rcp->qlen++);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700232 local_irq_restore(flags);
233}
234
235/*
Paul E. McKenneya57eb942010-06-29 16:49:16 -0700236 * Post an RCU callback to be invoked after the end of an RCU-sched grace
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700237 * period. But since we have but one CPU, that would be after any
238 * quiescent state.
239 */
Paul E. McKenneya57eb942010-06-29 16:49:16 -0700240void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700241{
Paul E. McKenney99652b52010-03-30 15:50:01 -0700242 __call_rcu(head, func, &rcu_sched_ctrlblk);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700243}
Paul E. McKenneya57eb942010-06-29 16:49:16 -0700244EXPORT_SYMBOL_GPL(call_rcu_sched);
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700245
246/*
247 * Post an RCU bottom-half callback to be invoked after any subsequent
248 * quiescent state.
249 */
Ingo Molnar4ce5b902009-10-26 07:55:55 +0100250void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
Paul E. McKenney9b1d82f2009-10-25 19:03:50 -0700251{
252 __call_rcu(head, func, &rcu_bh_ctrlblk);
253}
254EXPORT_SYMBOL_GPL(call_rcu_bh);