1RCU and Unloadable Modules
2
3[Originally published in LWN Jan. 14, 2007: http://lwn.net/Articles/217484/]
4
5RCU (read-copy update) is a synchronization mechanism that can be thought
6of as a replacement for read-writer locking (among other things), but with
7very low-overhead readers that are immune to deadlock, priority inversion,
8and unbounded latency. RCU read-side critical sections are delimited
9by rcu_read_lock() and rcu_read_unlock(), which, in non-CONFIG_PREEMPT
10kernels, generate no code whatsoever.
11
12This means that RCU writers are unaware of the presence of concurrent
13readers, so that RCU updates to shared data must be undertaken quite
14carefully, leaving an old version of the data structure in place until all
15pre-existing readers have finished. These old versions are needed because
16such readers might hold a reference to them. RCU updates can therefore be
17rather expensive, and RCU is thus best suited for read-mostly situations.
18
19How can an RCU writer possibly determine when all readers are finished,
20given that readers might well leave absolutely no trace of their
21presence? There is a synchronize_rcu() primitive that blocks until all
22pre-existing readers have completed. An updater wishing to delete an
23element p from a linked list might do the following, while holding an
24appropriate lock, of course:
25
26	list_del_rcu(p);
27	synchronize_rcu();
28	kfree(p);
29
30But the above code cannot be used in IRQ context -- the call_rcu()
31primitive must be used instead. This primitive takes a pointer to an
32rcu_head struct placed within the RCU-protected data structure and
33another pointer to a function that may be invoked later to free that
34structure. Code to delete an element p from the linked list from IRQ
35context might then be as follows:
36
37	list_del_rcu(p);
38	call_rcu(&p->rcu, p_callback);
39
40Since call_rcu() never blocks, this code can safely be used from within
41IRQ context. The function p_callback() might be defined as follows:
42
43	static void p_callback(struct rcu_head *rp)
44	{
45		struct pstruct *p = container_of(rp, struct pstruct, rcu);
46
47		kfree(p);
48	}
49
50
51Unloading Modules That Use call_rcu()
52
53But what if p_callback is defined in an unloadable module?
54
55If we unload the module while some RCU callbacks are pending,
56the CPUs executing these callbacks are going to be severely
57disappointed when they are later invoked, as fancifully depicted at
58http://lwn.net/images/ns/kernel/rcu-drop.jpg.
59
60We could try placing a synchronize_rcu() in the module-exit code path,
61but this is not sufficient. Although synchronize_rcu() does wait for a
62grace period to elapse, it does not wait for the callbacks to complete.
63
64One might be tempted to try several back-to-back synchronize_rcu()
65calls, but this is still not guaranteed to work. If there is a very
66heavy RCU-callback load, then some of the callbacks might be deferred
67in order to allow other processing to proceed. Such deferral is required
68in realtime kernels in order to avoid excessive scheduling latencies.
69
70
71rcu_barrier()
72
73We instead need the rcu_barrier() primitive.  Rather than waiting for
74a grace period to elapse, rcu_barrier() waits for all outstanding RCU
75callbacks to complete.  Please note that rcu_barrier() does -not- imply
76synchronize_rcu(), in particular, if there are no RCU callbacks queued
77anywhere, rcu_barrier() is within its rights to return immediately,
78without waiting for a grace period to elapse.
79
80Pseudo-code using rcu_barrier() is as follows:
81
82   1. Prevent any new RCU callbacks from being posted.
83   2. Execute rcu_barrier().
84   3. Allow the module to be unloaded.
85
86There are also rcu_barrier_bh(), rcu_barrier_sched(), and srcu_barrier()
87functions for the other flavors of RCU, and you of course must match
88the flavor of rcu_barrier() with that of call_rcu().  If your module
89uses multiple flavors of call_rcu(), then it must also use multiple
90flavors of rcu_barrier() when unloading that module.  For example, if
91it uses call_rcu_bh(), call_srcu() on srcu_struct_1, and call_srcu() on
92srcu_struct_2(), then the following three lines of code will be required
93when unloading:
94
95 1 rcu_barrier_bh();
96 2 srcu_barrier(&srcu_struct_1);
97 3 srcu_barrier(&srcu_struct_2);
98
99The rcutorture module makes use of rcu_barrier() in its exit function
100as follows:
101
102 1 static void
103 2 rcu_torture_cleanup(void)
104 3 {
105 4   int i;
106 5
107 6   fullstop = 1;
108 7   if (shuffler_task != NULL) {
109 8     VERBOSE_PRINTK_STRING("Stopping rcu_torture_shuffle task");
110 9     kthread_stop(shuffler_task);
11110   }
11211   shuffler_task = NULL;
11312
11413   if (writer_task != NULL) {
11514     VERBOSE_PRINTK_STRING("Stopping rcu_torture_writer task");
11615     kthread_stop(writer_task);
11716   }
11817   writer_task = NULL;
11918
12019   if (reader_tasks != NULL) {
12120     for (i = 0; i < nrealreaders; i++) {
12221       if (reader_tasks[i] != NULL) {
12322         VERBOSE_PRINTK_STRING(
12423           "Stopping rcu_torture_reader task");
12524         kthread_stop(reader_tasks[i]);
12625       }
12726       reader_tasks[i] = NULL;
12827     }
12928     kfree(reader_tasks);
13029     reader_tasks = NULL;
13130   }
13231   rcu_torture_current = NULL;
13332
13433   if (fakewriter_tasks != NULL) {
13534     for (i = 0; i < nfakewriters; i++) {
13635       if (fakewriter_tasks[i] != NULL) {
13736         VERBOSE_PRINTK_STRING(
13837           "Stopping rcu_torture_fakewriter task");
13938         kthread_stop(fakewriter_tasks[i]);
14039       }
14140       fakewriter_tasks[i] = NULL;
14241     }
14342     kfree(fakewriter_tasks);
14443     fakewriter_tasks = NULL;
14544   }
14645
14746   if (stats_task != NULL) {
14847     VERBOSE_PRINTK_STRING("Stopping rcu_torture_stats task");
14948     kthread_stop(stats_task);
15049   }
15150   stats_task = NULL;
15251
15352   /* Wait for all RCU callbacks to fire. */
15453   rcu_barrier();
15554
15655   rcu_torture_stats_print(); /* -After- the stats thread is stopped! */
15756
15857   if (cur_ops->cleanup != NULL)
15958     cur_ops->cleanup();
16059   if (atomic_read(&n_rcu_torture_error))
16160     rcu_torture_print_module_parms("End of test: FAILURE");
16261   else
16362     rcu_torture_print_module_parms("End of test: SUCCESS");
16463 }
165
166Line 6 sets a global variable that prevents any RCU callbacks from
167re-posting themselves. This will not be necessary in most cases, since
168RCU callbacks rarely include calls to call_rcu(). However, the rcutorture
169module is an exception to this rule, and therefore needs to set this
170global variable.
171
172Lines 7-50 stop all the kernel tasks associated with the rcutorture
173module. Therefore, once execution reaches line 53, no more rcutorture
174RCU callbacks will be posted. The rcu_barrier() call on line 53 waits
175for any pre-existing callbacks to complete.
176
177Then lines 55-62 print status and do operation-specific cleanup, and
178then return, permitting the module-unload operation to be completed.
179
180Quick Quiz #1: Is there any other situation where rcu_barrier() might
181	be required?
182
183Your module might have additional complications. For example, if your
184module invokes call_rcu() from timers, you will need to first cancel all
185the timers, and only then invoke rcu_barrier() to wait for any remaining
186RCU callbacks to complete.
187
188Of course, if you module uses call_rcu_bh(), you will need to invoke
189rcu_barrier_bh() before unloading.  Similarly, if your module uses
190call_rcu_sched(), you will need to invoke rcu_barrier_sched() before
191unloading.  If your module uses call_rcu(), call_rcu_bh(), -and-
192call_rcu_sched(), then you will need to invoke each of rcu_barrier(),
193rcu_barrier_bh(), and rcu_barrier_sched().
194
195
196Implementing rcu_barrier()
197
198Dipankar Sarma's implementation of rcu_barrier() makes use of the fact
199that RCU callbacks are never reordered once queued on one of the per-CPU
200queues. His implementation queues an RCU callback on each of the per-CPU
201callback queues, and then waits until they have all started executing, at
202which point, all earlier RCU callbacks are guaranteed to have completed.
203
204The original code for rcu_barrier() was as follows:
205
206 1 void rcu_barrier(void)
207 2 {
208 3   BUG_ON(in_interrupt());
209 4   /* Take cpucontrol mutex to protect against CPU hotplug */
210 5   mutex_lock(&rcu_barrier_mutex);
211 6   init_completion(&rcu_barrier_completion);
212 7   atomic_set(&rcu_barrier_cpu_count, 0);
213 8   on_each_cpu(rcu_barrier_func, NULL, 0, 1);
214 9   wait_for_completion(&rcu_barrier_completion);
21510   mutex_unlock(&rcu_barrier_mutex);
21611 }
217
218Line 3 verifies that the caller is in process context, and lines 5 and 10
219use rcu_barrier_mutex to ensure that only one rcu_barrier() is using the
220global completion and counters at a time, which are initialized on lines
2216 and 7. Line 8 causes each CPU to invoke rcu_barrier_func(), which is
222shown below. Note that the final "1" in on_each_cpu()'s argument list
223ensures that all the calls to rcu_barrier_func() will have completed
224before on_each_cpu() returns. Line 9 then waits for the completion.
225
226This code was rewritten in 2008 to support rcu_barrier_bh() and
227rcu_barrier_sched() in addition to the original rcu_barrier().
228
229The rcu_barrier_func() runs on each CPU, where it invokes call_rcu()
230to post an RCU callback, as follows:
231
232 1 static void rcu_barrier_func(void *notused)
233 2 {
234 3 int cpu = smp_processor_id();
235 4 struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
236 5 struct rcu_head *head;
237 6
238 7 head = &rdp->barrier;
239 8 atomic_inc(&rcu_barrier_cpu_count);
240 9 call_rcu(head, rcu_barrier_callback);
24110 }
242
243Lines 3 and 4 locate RCU's internal per-CPU rcu_data structure,
244which contains the struct rcu_head that needed for the later call to
245call_rcu(). Line 7 picks up a pointer to this struct rcu_head, and line
2468 increments a global counter. This counter will later be decremented
247by the callback. Line 9 then registers the rcu_barrier_callback() on
248the current CPU's queue.
249
250The rcu_barrier_callback() function simply atomically decrements the
251rcu_barrier_cpu_count variable and finalizes the completion when it
252reaches zero, as follows:
253
254 1 static void rcu_barrier_callback(struct rcu_head *notused)
255 2 {
256 3 if (atomic_dec_and_test(&rcu_barrier_cpu_count))
257 4 complete(&rcu_barrier_completion);
258 5 }
259
260Quick Quiz #2: What happens if CPU 0's rcu_barrier_func() executes
261	immediately (thus incrementing rcu_barrier_cpu_count to the
262	value one), but the other CPU's rcu_barrier_func() invocations
263	are delayed for a full grace period? Couldn't this result in
264	rcu_barrier() returning prematurely?
265
266
267rcu_barrier() Summary
268
269The rcu_barrier() primitive has seen relatively little use, since most
270code using RCU is in the core kernel rather than in modules. However, if
271you are using RCU from an unloadable module, you need to use rcu_barrier()
272so that your module may be safely unloaded.
273
274
275Answers to Quick Quizzes
276
277Quick Quiz #1: Is there any other situation where rcu_barrier() might
278	be required?
279
280Answer: Interestingly enough, rcu_barrier() was not originally
281	implemented for module unloading. Nikita Danilov was using
282	RCU in a filesystem, which resulted in a similar situation at
283	filesystem-unmount time. Dipankar Sarma coded up rcu_barrier()
284	in response, so that Nikita could invoke it during the
285	filesystem-unmount process.
286
287	Much later, yours truly hit the RCU module-unload problem when
288	implementing rcutorture, and found that rcu_barrier() solves
289	this problem as well.
290
291Quick Quiz #2: What happens if CPU 0's rcu_barrier_func() executes
292	immediately (thus incrementing rcu_barrier_cpu_count to the
293	value one), but the other CPU's rcu_barrier_func() invocations
294	are delayed for a full grace period? Couldn't this result in
295	rcu_barrier() returning prematurely?
296
297Answer: This cannot happen. The reason is that on_each_cpu() has its last
298	argument, the wait flag, set to "1". This flag is passed through
299	to smp_call_function() and further to smp_call_function_on_cpu(),
300	causing this latter to spin until the cross-CPU invocation of
301	rcu_barrier_func() has completed. This by itself would prevent
302	a grace period from completing on non-CONFIG_PREEMPT kernels,
303	since each CPU must undergo a context switch (or other quiescent
304	state) before the grace period can complete. However, this is
305	of no use in CONFIG_PREEMPT kernels.
306
307	Therefore, on_each_cpu() disables preemption across its call
308	to smp_call_function() and also across the local call to
309	rcu_barrier_func(). This prevents the local CPU from context
310	switching, again preventing grace periods from completing. This
311	means that all CPUs have executed rcu_barrier_func() before
312	the first rcu_barrier_callback() can possibly execute, in turn
313	preventing rcu_barrier_cpu_count from prematurely reaching zero.
314
315	Currently, -rt implementations of RCU keep but a single global
316	queue for RCU callbacks, and thus do not suffer from this
317	problem. However, when the -rt RCU eventually does have per-CPU
318	callback queues, things will have to change. One simple change
319	is to add an rcu_read_lock() before line 8 of rcu_barrier()
320	and an rcu_read_unlock() after line 8 of this same function. If
321	you can think of a better change, please let me know!
322