aboutsummaryrefslogtreecommitdiffstats
path: root/kernel/rcutiny.c
diff options
context:
space:
mode:
authorPaul E. McKenney <paulmck@linux.vnet.ibm.com>2009-10-25 22:03:50 -0400
committerIngo Molnar <mingo@elte.hu>2009-10-26 04:40:29 -0400
commit9b1d82fa1611706fa7ee1505f290160a18caf95d (patch)
tree7b2eed068360465d0b028d345eb318b1a8217305 /kernel/rcutiny.c
parent0edf1a683e499191b27a067956ae9f5fa6e046c6 (diff)
rcu: "Tiny RCU", The Bloatwatch Edition
This patch is a version of RCU designed for !SMP provided for a small-footprint RCU implementation. In particular, the implementation of synchronize_rcu() is extremely lightweight and high performance. It passes rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves about 1K bytes compared to old Classic RCU (which is no longer in mainline), and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30): CONFIG_TREE_RCU: text data bss dec filename 183 4 0 187 kernel/rcupdate.o 2783 520 36 3339 kernel/rcutree.o 3526 Total (vs 4565 for v7) CONFIG_TREE_PREEMPT_RCU: text data bss dec filename 263 4 0 267 kernel/rcupdate.o 4594 776 52 5422 kernel/rcutree.o 5689 Total (6155 for v7) CONFIG_TINY_RCU: text data bss dec filename 96 4 0 100 kernel/rcupdate.o 734 24 0 758 kernel/rcutiny.o 858 Total (vs 848 for v7) The above is for x86. Your mileage may vary on other platforms. Further compression is possible, but is being procrastinated. Changes from v7 (http://lkml.org/lkml/2009/10/9/388) o Apply Lai Jiangshan's review comments (aside from might_sleep() in synchronize_sched(), which is covered by SMP builds). o Fix up expedited primitives. Changes from v6 (http://lkml.org/lkml/2009/9/23/293). o Forward ported to put it into the 2.6.33 stream. o Added lockdep support. o Make lightweight rcu_barrier. Changes from v5 (http://lkml.org/lkml/2009/6/23/12). o Ported to latest pre-2.6.32 merge window kernel. - Renamed rcu_qsctr_inc() to rcu_sched_qs(). - Renamed rcu_bh_qsctr_inc() to rcu_bh_qs(). - Provided trivial rcu_cpu_notify(). - Provided trivial exit_rcu(). - Provided trivial rcu_needs_cpu(). - Fixed up the rcu_*_enter/exit() functions in linux/hardirq.h. o Removed the dependence on EMBEDDED, with a view to making TINY_RCU default for !SMP at some time in the future. o Added (trivial) support for expedited grace periods. Changes from v4 (http://lkml.org/lkml/2009/5/2/91) include: o Squeeze the size down a bit further by removing the ->completed field from struct rcu_ctrlblk. o This permits synchronize_rcu() to become the empty function. Previous concerns about rcutorture were unfounded, as rcutorture correctly handles a constant value from rcu_batches_completed() and rcu_batches_completed_bh(). Changes from v3 (http://lkml.org/lkml/2009/3/29/221) include: o Changed rcu_batches_completed(), rcu_batches_completed_bh() rcu_enter_nohz(), rcu_exit_nohz(), rcu_nmi_enter(), and rcu_nmi_exit(), to be static inlines, as suggested by David Howells. Doing this saves about 100 bytes from rcutiny.o. (The numbers between v3 and this v4 of the patch are not directly comparable, since they are against different versions of Linux.) Changes from v2 (http://lkml.org/lkml/2009/2/3/333) include: o Fix whitespace issues. o Change short-circuit "||" operator to instead be "+" in order to fix performance bug noted by "kraai" on LWN. (http://lwn.net/Articles/324348/) Changes from v1 (http://lkml.org/lkml/2009/1/13/440) include: o This version depends on EMBEDDED as well as !SMP, as suggested by Ingo. o Updated rcu_needs_cpu() to unconditionally return zero, permitting the CPU to enter dynticks-idle mode at any time. This works because callbacks can be invoked upon entry to dynticks-idle mode. o Paul is now OK with this being included, based on a poll at the Kernel Miniconf at linux.conf.au, where about ten people said that they cared about saving 900 bytes on single-CPU systems. o Applies to both mainline and tip/core/rcu. Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Acked-by: David Howells <dhowells@redhat.com> Acked-by: Josh Triplett <josh@joshtriplett.org> Reviewed-by: Lai Jiangshan <laijs@cn.fujitsu.com> Cc: dipankar@in.ibm.com Cc: mathieu.desnoyers@polymtl.ca Cc: dvhltc@us.ibm.com Cc: niv@us.ibm.com Cc: peterz@infradead.org Cc: rostedt@goodmis.org Cc: Valdis.Kletnieks@vt.edu Cc: avi@redhat.com Cc: mtosatti@redhat.com LKML-Reference: <12565226351355-git-send-email-> Signed-off-by: Ingo Molnar <mingo@elte.hu>
Diffstat (limited to 'kernel/rcutiny.c')
-rw-r--r--kernel/rcutiny.c294
1 files changed, 294 insertions, 0 deletions
diff --git a/kernel/rcutiny.c b/kernel/rcutiny.c
new file mode 100644
index 00000000000..0b54efde66a
--- /dev/null
+++ b/kernel/rcutiny.c
@@ -0,0 +1,294 @@
1/*
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 -
23 * Documentation/RCU
24 */
25
26#include <linux/types.h>
27#include <linux/kernel.h>
28#include <linux/init.h>
29#include <linux/rcupdate.h>
30#include <linux/interrupt.h>
31#include <linux/sched.h>
32#include <linux/module.h>
33#include <linux/completion.h>
34#include <linux/moduleparam.h>
35#include <linux/notifier.h>
36#include <linux/cpu.h>
37#include <linux/mutex.h>
38#include <linux/time.h>
39
40/* Global control variables for rcupdate callback mechanism. */
41struct rcu_ctrlblk {
42 struct rcu_head *rcucblist; /* List of pending callbacks (CBs). */
43 struct rcu_head **donetail; /* ->next pointer of last "done" CB. */
44 struct rcu_head **curtail; /* ->next pointer of last CB. */
45};
46
47/* Definition for rcupdate control block. */
48static struct rcu_ctrlblk rcu_ctrlblk = {
49 .rcucblist = NULL,
50 .donetail = &rcu_ctrlblk.rcucblist,
51 .curtail = &rcu_ctrlblk.rcucblist,
52};
53static struct rcu_ctrlblk rcu_bh_ctrlblk = {
54 .rcucblist = NULL,
55 .donetail = &rcu_bh_ctrlblk.rcucblist,
56 .curtail = &rcu_bh_ctrlblk.rcucblist,
57};
58
59#ifdef CONFIG_NO_HZ
60
61static long rcu_dynticks_nesting = 1;
62
63/*
64 * Enter dynticks-idle mode, which is an extended quiescent state
65 * if we have fully entered that mode (i.e., if the new value of
66 * dynticks_nesting is zero).
67 */
68void rcu_enter_nohz(void)
69{
70 if (--rcu_dynticks_nesting == 0)
71 rcu_sched_qs(0); /* implies rcu_bh_qsctr_inc(0) */
72}
73
74/*
75 * Exit dynticks-idle mode, so that we are no longer in an extended
76 * quiescent state.
77 */
78void rcu_exit_nohz(void)
79{
80 rcu_dynticks_nesting++;
81}
82
83#endif /* #ifdef CONFIG_NO_HZ */
84
85/*
86 * Helper function for rcu_qsctr_inc() and rcu_bh_qsctr_inc().
87 * Also disable irqs to avoid confusion due to interrupt handlers invoking
88 * call_rcu().
89 */
90static int rcu_qsctr_help(struct rcu_ctrlblk *rcp)
91{
92 unsigned long flags;
93
94 local_irq_save(flags);
95 if (rcp->rcucblist != NULL &&
96 rcp->donetail != rcp->curtail) {
97 rcp->donetail = rcp->curtail;
98 local_irq_restore(flags);
99 return 1;
100 }
101 local_irq_restore(flags);
102 return 0;
103}
104
105/*
106 * Record an rcu quiescent state. And an rcu_bh quiescent state while we
107 * are at it, given that any rcu quiescent state is also an rcu_bh
108 * quiescent state. Use "+" instead of "||" to defeat short circuiting.
109 */
110void rcu_sched_qs(int cpu)
111{
112 if (rcu_qsctr_help(&rcu_ctrlblk) + rcu_qsctr_help(&rcu_bh_ctrlblk))
113 raise_softirq(RCU_SOFTIRQ);
114}
115
116/*
117 * Record an rcu_bh quiescent state.
118 */
119void rcu_bh_qs(int cpu)
120{
121 if (rcu_qsctr_help(&rcu_bh_ctrlblk))
122 raise_softirq(RCU_SOFTIRQ);
123}
124
125/*
126 * Check to see if the scheduling-clock interrupt came from an extended
127 * quiescent state, and, if so, tell RCU about it.
128 */
129void rcu_check_callbacks(int cpu, int user)
130{
131 if (user ||
132 (idle_cpu(cpu) &&
133 !in_softirq() &&
134 hardirq_count() <= (1 << HARDIRQ_SHIFT)))
135 rcu_sched_qs(cpu);
136 else if (!in_softirq())
137 rcu_bh_qs(cpu);
138}
139
140/*
141 * Helper function for rcu_process_callbacks() that operates on the
142 * specified rcu_ctrlkblk structure.
143 */
144static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
145{
146 unsigned long flags;
147 struct rcu_head *next, *list;
148
149 /* If no RCU callbacks ready to invoke, just return. */
150 if (&rcp->rcucblist == rcp->donetail)
151 return;
152
153 /* Move the ready-to-invoke callbacks to a local list. */
154 local_irq_save(flags);
155 list = rcp->rcucblist;
156 rcp->rcucblist = *rcp->donetail;
157 *rcp->donetail = NULL;
158 if (rcp->curtail == rcp->donetail)
159 rcp->curtail = &rcp->rcucblist;
160 rcp->donetail = &rcp->rcucblist;
161 local_irq_restore(flags);
162
163 /* Invoke the callbacks on the local list. */
164 while (list) {
165 next = list->next;
166 prefetch(next);
167 list->func(list);
168 list = next;
169 }
170}
171
172/*
173 * Invoke any callbacks whose grace period has completed.
174 */
175static void rcu_process_callbacks(struct softirq_action *unused)
176{
177 __rcu_process_callbacks(&rcu_ctrlblk);
178 __rcu_process_callbacks(&rcu_bh_ctrlblk);
179}
180
181/*
182 * Null function to handle CPU being onlined. Longer term, we want to
183 * make TINY_RCU avoid using rcupdate.c, but later...
184 */
185int rcu_cpu_notify(struct notifier_block *self,
186 unsigned long action, void *hcpu)
187{
188 return NOTIFY_OK;
189}
190
191/*
192 * Wait for a grace period to elapse. But it is illegal to invoke
193 * synchronize_sched() from within an RCU read-side critical section.
194 * Therefore, any legal call to synchronize_sched() is a quiescent
195 * state, and so on a UP system, synchronize_sched() need do nothing.
196 * Ditto for synchronize_rcu_bh(). (But Lai Jiangshan points out the
197 * benefits of doing might_sleep() to reduce latency.)
198 *
199 * Cool, huh? (Due to Josh Triplett.)
200 *
201 * But we want to make this a static inline later.
202 */
203void synchronize_sched(void)
204{
205 cond_resched();
206}
207EXPORT_SYMBOL_GPL(synchronize_sched);
208
209void synchronize_rcu_bh(void)
210{
211 synchronize_sched();
212}
213EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
214
215/*
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
224 head->func = func;
225 head->next = NULL;
226 local_irq_save(flags);
227 *rcp->curtail = head;
228 rcp->curtail = &head->next;
229 local_irq_restore(flags);
230}
231
232/*
233 * Post an RCU callback to be invoked after the end of an RCU grace
234 * period. But since we have but one CPU, that would be after any
235 * quiescent state.
236 */
237void call_rcu(struct rcu_head *head,
238 void (*func)(struct rcu_head *rcu))
239{
240 __call_rcu(head, func, &rcu_ctrlblk);
241}
242EXPORT_SYMBOL_GPL(call_rcu);
243
244/*
245 * Post an RCU bottom-half callback to be invoked after any subsequent
246 * quiescent state.
247 */
248void call_rcu_bh(struct rcu_head *head,
249 void (*func)(struct rcu_head *rcu))
250{
251 __call_rcu(head, func, &rcu_bh_ctrlblk);
252}
253EXPORT_SYMBOL_GPL(call_rcu_bh);
254
255void rcu_barrier(void)
256{
257 struct rcu_synchronize rcu;
258
259 init_completion(&rcu.completion);
260 /* Will wake me after RCU finished. */
261 call_rcu(&rcu.head, wakeme_after_rcu);
262 /* Wait for it. */
263 wait_for_completion(&rcu.completion);
264}
265EXPORT_SYMBOL_GPL(rcu_barrier);
266
267void rcu_barrier_bh(void)
268{
269 struct rcu_synchronize rcu;
270
271 init_completion(&rcu.completion);
272 /* Will wake me after RCU finished. */
273 call_rcu_bh(&rcu.head, wakeme_after_rcu);
274 /* Wait for it. */
275 wait_for_completion(&rcu.completion);
276}
277EXPORT_SYMBOL_GPL(rcu_barrier_bh);
278
279void rcu_barrier_sched(void)
280{
281 struct rcu_synchronize rcu;
282
283 init_completion(&rcu.completion);
284 /* Will wake me after RCU finished. */
285 call_rcu_sched(&rcu.head, wakeme_after_rcu);
286 /* Wait for it. */
287 wait_for_completion(&rcu.completion);
288}
289EXPORT_SYMBOL_GPL(rcu_barrier_sched);
290
291void __rcu_init(void)
292{
293 open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
294}