1 .. _list_rcu_doc: 1 .. _list_rcu_doc:
2 2
3 Using RCU to Protect Read-Mostly Linked Lists 3 Using RCU to Protect Read-Mostly Linked Lists
4 ============================================= 4 =============================================
5 5
6 One of the most common uses of RCU is protecti !! 6 One of the best applications of RCU is to protect read-mostly linked lists
7 (``struct list_head`` in list.h). One big adv !! 7 ("struct list_head" in list.h). One big advantage of this approach
8 that all of the required memory ordering is pr !! 8 is that all of the required memory barriers are included for you in
9 This document describes several list-based RCU !! 9 the list macros. This document describes several applications of RCU,
10 !! 10 with the best fits first.
11 When iterating a list while holding the rcu_re <<
12 modify the list. The reader is guaranteed to <<
13 which were added to the list before they acqui <<
14 and are still on the list when they drop the r <<
15 Elements which are added to, or removed from t <<
16 be seen. If the writer calls list_replace_rcu <<
17 either the old element or the new element; the <<
18 nor will they see neither. <<
19 <<
20 <<
21 Example 1: Read-mostly list: Deferred Destruct <<
22 ---------------------------------------------- <<
23 <<
24 A widely used usecase for RCU lists in the ker <<
25 all processes in the system. ``task_struct::ta <<
26 links all the processes. The list can be trave <<
27 additions or removals. <<
28 <<
29 The traversal of the list is done using ``for_ <<
30 by the 2 macros:: <<
31 <<
32 #define next_task(p) \ <<
33 list_entry_rcu((p)->tasks.next <<
34 <<
35 #define for_each_process(p) \ <<
36 for (p = &init_task ; (p = nex <<
37 <<
38 The code traversing the list of all processes <<
39 <<
40 rcu_read_lock(); <<
41 for_each_process(p) { <<
42 /* Do something with p */ <<
43 } <<
44 rcu_read_unlock(); <<
45 <<
46 The simplified and heavily inlined code for re <<
47 task list is:: <<
48 <<
49 void release_task(struct task_struct * <<
50 { <<
51 write_lock(&tasklist_lock); <<
52 list_del_rcu(&p->tasks); <<
53 write_unlock(&tasklist_lock); <<
54 call_rcu(&p->rcu, delayed_put_ <<
55 } <<
56 <<
57 When a process exits, ``release_task()`` calls <<
58 via __exit_signal() and __unhash_process() und <<
59 writer lock protection. The list_del_rcu() in <<
60 the task from the list of all tasks. The ``tas <<
61 prevents concurrent list additions/removals fr <<
62 list. Readers using ``for_each_process()`` are <<
63 ``tasklist_lock``. To prevent readers from not <<
64 pointers, the ``task_struct`` object is freed <<
65 grace periods elapse, with the help of call_rc <<
66 put_task_struct_rcu_user(). This deferring of <<
67 any readers traversing the list will see valid <<
68 and deletion/freeing can happen in parallel wi <<
69 This pattern is also called an **existence loc <<
70 from invoking the delayed_put_task_struct() ca <<
71 all existing readers finish, which guarantees <<
72 object in question will remain in existence un <<
73 of all RCU readers that might possibly have a <<
74 <<
75 11
76 Example 2: Read-Side Action Taken Outside of L !! 12 Example 1: Read-Side Action Taken Outside of Lock, No In-Place Updates
77 ---------------------------------------------- 13 ----------------------------------------------------------------------
78 14
79 Some reader-writer locking use cases compute a !! 15 The best applications are cases where, if reader-writer locking were
80 the read-side lock, but continue to use that v !! 16 used, the read-side lock would be dropped before taking any action
81 released. These use cases are often good cand !! 17 based on the results of the search. The most celebrated example is
82 to RCU. One prominent example involves networ !! 18 the routing table. Because the routing table is tracking the state of
83 Because the packet-routing data tracks the sta !! 19 equipment outside of the computer, it will at times contain stale data.
84 of the computer, it will at times contain stal !! 20 Therefore, once the route has been computed, there is no need to hold
85 the route has been computed, there is no need !! 21 the routing table static during transmission of the packet. After all,
86 static during transmission of the packet. Aft !! 22 you can hold the routing table static all you want, but that won't keep
87 routing table static all you want, but that wo !! 23 the external Internet from changing, and it is the state of the external
88 Internet from changing, and it is the state of !! 24 Internet that really matters. In addition, routing entries are typically
89 that really matters. In addition, routing ent !! 25 added or deleted, rather than being modified in place.
90 or deleted, rather than being modified in plac !! 26
91 of the finite speed of light and the non-zero !! 27 A straightforward example of this use of RCU may be found in the
92 helping make synchronization be lighter weight !! 28 system-call auditing support. For example, a reader-writer locked
93 !! 29 implementation of audit_filter_task() might be as follows::
94 A straightforward example of this type of RCU <<
95 the system-call auditing support. For example <<
96 implementation of ``audit_filter_task()`` migh <<
97 30
98 static enum audit_state audit_filter_t !! 31 static enum audit_state audit_filter_task(struct task_struct *tsk)
99 { 32 {
100 struct audit_entry *e; 33 struct audit_entry *e;
101 enum audit_state state; 34 enum audit_state state;
102 35
103 read_lock(&auditsc_lock); 36 read_lock(&auditsc_lock);
104 /* Note: audit_filter_mutex he !! 37 /* Note: audit_netlink_sem held by caller. */
105 list_for_each_entry(e, &audit_ 38 list_for_each_entry(e, &audit_tsklist, list) {
106 if (audit_filter_rules 39 if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
107 if (state == A <<
108 *key = <<
109 read_unlock(&a 40 read_unlock(&auditsc_lock);
110 return state; 41 return state;
111 } 42 }
112 } 43 }
113 read_unlock(&auditsc_lock); 44 read_unlock(&auditsc_lock);
114 return AUDIT_BUILD_CONTEXT; 45 return AUDIT_BUILD_CONTEXT;
115 } 46 }
116 47
117 Here the list is searched under the lock, but 48 Here the list is searched under the lock, but the lock is dropped before
118 the corresponding value is returned. By the t 49 the corresponding value is returned. By the time that this value is acted
119 on, the list may well have been modified. Thi 50 on, the list may well have been modified. This makes sense, since if
120 you are turning auditing off, it is OK to audi 51 you are turning auditing off, it is OK to audit a few extra system calls.
121 52
122 This means that RCU can be easily applied to t 53 This means that RCU can be easily applied to the read side, as follows::
123 54
124 static enum audit_state audit_filter_t !! 55 static enum audit_state audit_filter_task(struct task_struct *tsk)
125 { 56 {
126 struct audit_entry *e; 57 struct audit_entry *e;
127 enum audit_state state; 58 enum audit_state state;
128 59
129 rcu_read_lock(); 60 rcu_read_lock();
130 /* Note: audit_filter_mutex he !! 61 /* Note: audit_netlink_sem held by caller. */
131 list_for_each_entry_rcu(e, &au 62 list_for_each_entry_rcu(e, &audit_tsklist, list) {
132 if (audit_filter_rules 63 if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
133 if (state == A <<
134 *key = <<
135 rcu_read_unloc 64 rcu_read_unlock();
136 return state; 65 return state;
137 } 66 }
138 } 67 }
139 rcu_read_unlock(); 68 rcu_read_unlock();
140 return AUDIT_BUILD_CONTEXT; 69 return AUDIT_BUILD_CONTEXT;
141 } 70 }
142 71
143 The read_lock() and read_unlock() calls have b 72 The read_lock() and read_unlock() calls have become rcu_read_lock()
144 and rcu_read_unlock(), respectively, and the l !! 73 and rcu_read_unlock(), respectively, and the list_for_each_entry() has
145 has become list_for_each_entry_rcu(). The **_ !! 74 become list_for_each_entry_rcu(). The _rcu() list-traversal primitives
146 primitives add READ_ONCE() and diagnostic chec !! 75 insert the read-side memory barriers that are required on DEC Alpha CPUs.
147 outside of an RCU read-side critical section. !! 76
148 !! 77 The changes to the update side are also straightforward. A reader-writer
149 The changes to the update side are also straig !! 78 lock might be used as follows for deletion and insertion::
150 might be used as follows for deletion and inse <<
151 versions of audit_del_rule() and audit_add_rul <<
152 79
153 static inline int audit_del_rule(struc 80 static inline int audit_del_rule(struct audit_rule *rule,
154 struc 81 struct list_head *list)
155 { 82 {
156 struct audit_entry *e; !! 83 struct audit_entry *e;
157 84
158 write_lock(&auditsc_lock); 85 write_lock(&auditsc_lock);
159 list_for_each_entry(e, list, l 86 list_for_each_entry(e, list, list) {
160 if (!audit_compare_rul 87 if (!audit_compare_rule(rule, &e->rule)) {
161 list_del(&e->l 88 list_del(&e->list);
162 write_unlock(& 89 write_unlock(&auditsc_lock);
163 return 0; 90 return 0;
164 } 91 }
165 } 92 }
166 write_unlock(&auditsc_lock); 93 write_unlock(&auditsc_lock);
167 return -EFAULT; /* No 94 return -EFAULT; /* No matching rule */
168 } 95 }
169 96
170 static inline int audit_add_rule(struc 97 static inline int audit_add_rule(struct audit_entry *entry,
171 struc 98 struct list_head *list)
172 { 99 {
173 write_lock(&auditsc_lock); 100 write_lock(&auditsc_lock);
174 if (entry->rule.flags & AUDIT_ 101 if (entry->rule.flags & AUDIT_PREPEND) {
175 entry->rule.flags &= ~ 102 entry->rule.flags &= ~AUDIT_PREPEND;
176 list_add(&entry->list, 103 list_add(&entry->list, list);
177 } else { 104 } else {
178 list_add_tail(&entry-> 105 list_add_tail(&entry->list, list);
179 } 106 }
180 write_unlock(&auditsc_lock); 107 write_unlock(&auditsc_lock);
181 return 0; 108 return 0;
182 } 109 }
183 110
184 Following are the RCU equivalents for these tw 111 Following are the RCU equivalents for these two functions::
185 112
186 static inline int audit_del_rule(struc 113 static inline int audit_del_rule(struct audit_rule *rule,
187 struc 114 struct list_head *list)
188 { 115 {
189 struct audit_entry *e; !! 116 struct audit_entry *e;
190 117
191 /* No need to use the _rcu ite !! 118 /* Do not use the _rcu iterator here, since this is the only
192 * deletion routine. */ 119 * deletion routine. */
193 list_for_each_entry(e, list, l 120 list_for_each_entry(e, list, list) {
194 if (!audit_compare_rul 121 if (!audit_compare_rule(rule, &e->rule)) {
195 list_del_rcu(& 122 list_del_rcu(&e->list);
196 call_rcu(&e->r 123 call_rcu(&e->rcu, audit_free_rule);
197 return 0; 124 return 0;
198 } 125 }
199 } 126 }
200 return -EFAULT; /* No 127 return -EFAULT; /* No matching rule */
201 } 128 }
202 129
203 static inline int audit_add_rule(struc 130 static inline int audit_add_rule(struct audit_entry *entry,
204 struc 131 struct list_head *list)
205 { 132 {
206 if (entry->rule.flags & AUDIT_ 133 if (entry->rule.flags & AUDIT_PREPEND) {
207 entry->rule.flags &= ~ 134 entry->rule.flags &= ~AUDIT_PREPEND;
208 list_add_rcu(&entry->l 135 list_add_rcu(&entry->list, list);
209 } else { 136 } else {
210 list_add_tail_rcu(&ent 137 list_add_tail_rcu(&entry->list, list);
211 } 138 }
212 return 0; 139 return 0;
213 } 140 }
214 141
215 Normally, the write_lock() and write_unlock() !! 142 Normally, the write_lock() and write_unlock() would be replaced by
216 spin_lock() and a spin_unlock(). But in this c !! 143 a spin_lock() and a spin_unlock(), but in this case, all callers hold
217 ``audit_filter_mutex``, so no additional locki !! 144 audit_netlink_sem, so no additional locking is required. The auditsc_lock
218 auditsc_lock can therefore be eliminated, sinc !! 145 can therefore be eliminated, since use of RCU eliminates the need for
219 need for writers to exclude readers. !! 146 writers to exclude readers. Normally, the write_lock() calls would
>> 147 be converted into spin_lock() calls.
220 148
221 The list_del(), list_add(), and list_add_tail( 149 The list_del(), list_add(), and list_add_tail() primitives have been
222 replaced by list_del_rcu(), list_add_rcu(), an 150 replaced by list_del_rcu(), list_add_rcu(), and list_add_tail_rcu().
223 The **_rcu()** list-manipulation primitives ad !! 151 The _rcu() list-manipulation primitives add memory barriers that are
224 needed on weakly ordered CPUs. The list_del_r !! 152 needed on weakly ordered CPUs (most of them!). The list_del_rcu()
225 pointer poisoning debug-assist code that would !! 153 primitive omits the pointer poisoning debug-assist code that would
226 readers to fail spectacularly. !! 154 otherwise cause concurrent readers to fail spectacularly.
227 <<
228 So, when readers can tolerate stale data and w <<
229 deleted, without in-place modification, it is <<
230 155
>> 156 So, when readers can tolerate stale data and when entries are either added
>> 157 or deleted, without in-place modification, it is very easy to use RCU!
231 158
232 Example 3: Handling In-Place Updates !! 159 Example 2: Handling In-Place Updates
233 ------------------------------------ 160 ------------------------------------
234 161
235 The system-call auditing code does not update !! 162 The system-call auditing code does not update auditing rules in place.
236 if it did, the reader-writer-locked code to do !! 163 However, if it did, reader-writer-locked code to do so might look as
237 (assuming only ``field_count`` is updated, oth !! 164 follows (presumably, the field_count is only permitted to decrease,
238 need to be filled in):: !! 165 otherwise, the added fields would need to be filled in)::
239 166
240 static inline int audit_upd_rule(struc 167 static inline int audit_upd_rule(struct audit_rule *rule,
241 struc 168 struct list_head *list,
242 __u32 169 __u32 newaction,
243 __u32 170 __u32 newfield_count)
244 { 171 {
245 struct audit_entry *e; !! 172 struct audit_entry *e;
246 struct audit_entry *ne; !! 173 struct audit_newentry *ne;
247 174
248 write_lock(&auditsc_lock); 175 write_lock(&auditsc_lock);
249 /* Note: audit_filter_mutex he !! 176 /* Note: audit_netlink_sem held by caller. */
250 list_for_each_entry(e, list, l 177 list_for_each_entry(e, list, list) {
251 if (!audit_compare_rul 178 if (!audit_compare_rule(rule, &e->rule)) {
252 e->rule.action 179 e->rule.action = newaction;
253 e->rule.field_ !! 180 e->rule.file_count = newfield_count;
254 write_unlock(& 181 write_unlock(&auditsc_lock);
255 return 0; 182 return 0;
256 } 183 }
257 } 184 }
258 write_unlock(&auditsc_lock); 185 write_unlock(&auditsc_lock);
259 return -EFAULT; /* No 186 return -EFAULT; /* No matching rule */
260 } 187 }
261 188
262 The RCU version creates a copy, updates the co 189 The RCU version creates a copy, updates the copy, then replaces the old
263 entry with the newly updated entry. This sequ 190 entry with the newly updated entry. This sequence of actions, allowing
264 concurrent reads while making a copy to perfor !! 191 concurrent reads while doing a copy to perform an update, is what gives
265 RCU (*read-copy update*) its name. !! 192 RCU ("read-copy update") its name. The RCU code is as follows::
266 <<
267 The RCU version of audit_upd_rule() is as foll <<
268 193
269 static inline int audit_upd_rule(struc 194 static inline int audit_upd_rule(struct audit_rule *rule,
270 struc 195 struct list_head *list,
271 __u32 196 __u32 newaction,
272 __u32 197 __u32 newfield_count)
273 { 198 {
274 struct audit_entry *e; !! 199 struct audit_entry *e;
275 struct audit_entry *ne; !! 200 struct audit_newentry *ne;
276 201
277 list_for_each_entry(e, list, l 202 list_for_each_entry(e, list, list) {
278 if (!audit_compare_rul 203 if (!audit_compare_rule(rule, &e->rule)) {
279 ne = kmalloc(s 204 ne = kmalloc(sizeof(*entry), GFP_ATOMIC);
280 if (ne == NULL 205 if (ne == NULL)
281 return 206 return -ENOMEM;
282 audit_copy_rul 207 audit_copy_rule(&ne->rule, &e->rule);
283 ne->rule.actio 208 ne->rule.action = newaction;
284 ne->rule.field !! 209 ne->rule.file_count = newfield_count;
285 list_replace_r 210 list_replace_rcu(&e->list, &ne->list);
286 call_rcu(&e->r 211 call_rcu(&e->rcu, audit_free_rule);
287 return 0; 212 return 0;
288 } 213 }
289 } 214 }
290 return -EFAULT; /* No 215 return -EFAULT; /* No matching rule */
291 } 216 }
292 217
293 Again, this assumes that the caller holds ``au !! 218 Again, this assumes that the caller holds audit_netlink_sem. Normally,
294 writer lock would become a spinlock in this so !! 219 the reader-writer lock would become a spinlock in this sort of code.
295 <<
296 The update_lsm_rule() does something very simi <<
297 prefer to look at real Linux-kernel code. <<
298 <<
299 Another use of this pattern can be found in th <<
300 tracking table* code in ``ct_limit_set()``. T <<
301 entries and has a limit on the maximum entries <<
302 per-zone and hence one *limit* per zone. The <<
303 through a hashtable using an RCU-managed hlist <<
304 limit is set, a new limit object is allocated <<
305 to replace the old limit object with the new o <<
306 The old limit object is then freed after a gra <<
307 220
308 !! 221 Example 3: Eliminating Stale Data
309 Example 4: Eliminating Stale Data <<
310 --------------------------------- 222 ---------------------------------
311 223
312 The auditing example above tolerates stale dat !! 224 The auditing examples above tolerate stale data, as do most algorithms
313 that are tracking external state. After all, !! 225 that are tracking external state. Because there is a delay from the
314 from the time the external state changes befor !! 226 time the external state changes before Linux becomes aware of the change,
315 of the change, and so as noted earlier, a smal !! 227 additional RCU-induced staleness is normally not a problem.
316 RCU-induced staleness is generally not a probl <<
317 228
318 However, there are many examples where stale d 229 However, there are many examples where stale data cannot be tolerated.
319 One example in the Linux kernel is the System !! 230 One example in the Linux kernel is the System V IPC (see the ipc_lock()
320 function in ipc/shm.c). This code checks a *d !! 231 function in ipc/util.c). This code checks a "deleted" flag under a
321 per-entry spinlock, and, if the *deleted* flag !! 232 per-entry spinlock, and, if the "deleted" flag is set, pretends that the
322 entry does not exist. For this to be helpful, 233 entry does not exist. For this to be helpful, the search function must
323 return holding the per-entry spinlock, as shm_ !! 234 return holding the per-entry spinlock, as ipc_lock() does in fact do.
324 <<
325 .. _quick_quiz: <<
326 235
327 Quick Quiz: 236 Quick Quiz:
328 For the deleted-flag technique to be h !! 237 Why does the search function need to return holding the per-entry lock for
329 to hold the per-entry lock while retur !! 238 this deleted-flag technique to be helpful?
330 239
331 :ref:`Answer to Quick Quiz <quick_quiz_answer> !! 240 :ref:`Answer to Quick Quiz <answer_quick_quiz_list>`
332 241
333 If the system-call audit module were to ever n !! 242 If the system-call audit module were to ever need to reject stale data,
334 to accomplish this would be to add a ``deleted !! 243 one way to accomplish this would be to add a "deleted" flag and a "lock"
335 ``audit_entry`` structure, and modify audit_fi !! 244 spinlock to the audit_entry structure, and modify audit_filter_task()
>> 245 as follows::
336 246
337 static enum audit_state audit_filter_t 247 static enum audit_state audit_filter_task(struct task_struct *tsk)
338 { 248 {
339 struct audit_entry *e; 249 struct audit_entry *e;
340 enum audit_state state; 250 enum audit_state state;
341 251
342 rcu_read_lock(); 252 rcu_read_lock();
343 list_for_each_entry_rcu(e, &au 253 list_for_each_entry_rcu(e, &audit_tsklist, list) {
344 if (audit_filter_rules 254 if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
345 spin_lock(&e-> 255 spin_lock(&e->lock);
346 if (e->deleted 256 if (e->deleted) {
347 spin_u 257 spin_unlock(&e->lock);
348 rcu_re 258 rcu_read_unlock();
349 return 259 return AUDIT_BUILD_CONTEXT;
350 } 260 }
351 rcu_read_unloc 261 rcu_read_unlock();
352 if (state == A <<
353 *key = <<
354 return state; 262 return state;
355 } 263 }
356 } 264 }
357 rcu_read_unlock(); 265 rcu_read_unlock();
358 return AUDIT_BUILD_CONTEXT; 266 return AUDIT_BUILD_CONTEXT;
359 } 267 }
360 268
361 The ``audit_del_rule()`` function would need t !! 269 Note that this example assumes that entries are only added and deleted.
362 spinlock as follows:: !! 270 Additional mechanism is required to deal correctly with the
>> 271 update-in-place performed by audit_upd_rule(). For one thing,
>> 272 audit_upd_rule() would need additional memory barriers to ensure
>> 273 that the list_add_rcu() was really executed before the list_del_rcu().
>> 274
>> 275 The audit_del_rule() function would need to set the "deleted"
>> 276 flag under the spinlock as follows::
363 277
364 static inline int audit_del_rule(struc 278 static inline int audit_del_rule(struct audit_rule *rule,
365 struc 279 struct list_head *list)
366 { 280 {
367 struct audit_entry *e; !! 281 struct audit_entry *e;
368 282
369 /* No need to use the _rcu ite !! 283 /* Do not need to use the _rcu iterator here, since this
370 * is the only deletion routin 284 * is the only deletion routine. */
371 list_for_each_entry(e, list, l 285 list_for_each_entry(e, list, list) {
372 if (!audit_compare_rul 286 if (!audit_compare_rule(rule, &e->rule)) {
373 spin_lock(&e-> 287 spin_lock(&e->lock);
374 list_del_rcu(& 288 list_del_rcu(&e->list);
375 e->deleted = 1 289 e->deleted = 1;
376 spin_unlock(&e 290 spin_unlock(&e->lock);
377 call_rcu(&e->r 291 call_rcu(&e->rcu, audit_free_rule);
378 return 0; 292 return 0;
379 } 293 }
380 } 294 }
381 return -EFAULT; /* No 295 return -EFAULT; /* No matching rule */
382 } 296 }
383 297
384 This too assumes that the caller holds ``audit <<
385 <<
386 Note that this example assumes that entries ar <<
387 Additional mechanism is required to deal corre <<
388 performed by audit_upd_rule(). For one thing, <<
389 need to hold the locks of both the old ``audit <<
390 while executing the list_replace_rcu(). <<
391 <<
392 <<
393 Example 5: Skipping Stale Objects <<
394 --------------------------------- <<
395 <<
396 For some use cases, reader performance can be <<
397 stale objects during read-side list traversal, <<
398 are those that will be removed and destroyed a <<
399 periods. One such example can be found in the <<
400 ``CLOCK_REALTIME`` clock is reprogrammed (for <<
401 of the system time) then all programmed ``time <<
402 this clock get triggered and processes waiting <<
403 advance of their scheduled expiry. To facilita <<
404 are added to an RCU-managed ``cancel_list`` wh <<
405 ``timerfd_setup_cancel()``:: <<
406 <<
407 static void timerfd_setup_cancel(struc <<
408 { <<
409 spin_lock(&ctx->cancel_lock); <<
410 if ((ctx->clockid == CLOCK_REA <<
411 ctx->clockid == CLOCK_REA <<
412 (flags & TFD_TIMER_ABSTIME <<
413 if (!ctx->might_cancel <<
414 ctx->might_can <<
415 spin_lock(&can <<
416 list_add_rcu(& <<
417 spin_unlock(&c <<
418 } <<
419 } else { <<
420 __timerfd_remove_cance <<
421 } <<
422 spin_unlock(&ctx->cancel_lock) <<
423 } <<
424 <<
425 When a timerfd is freed (fd is closed), then t <<
426 flag of the timerfd object is cleared, the obj <<
427 ``cancel_list`` and destroyed, as shown in thi <<
428 version of timerfd_release():: <<
429 <<
430 int timerfd_release(struct inode *inod <<
431 { <<
432 struct timerfd_ctx *ctx = file <<
433 <<
434 spin_lock(&ctx->cancel_lock); <<
435 if (ctx->might_cancel) { <<
436 ctx->might_cancel = fa <<
437 spin_lock(&cancel_lock <<
438 list_del_rcu(&ctx->cli <<
439 spin_unlock(&cancel_lo <<
440 } <<
441 spin_unlock(&ctx->cancel_lock) <<
442 <<
443 if (isalarm(ctx)) <<
444 alarm_cancel(&ctx->t.a <<
445 else <<
446 hrtimer_cancel(&ctx->t <<
447 kfree_rcu(ctx, rcu); <<
448 return 0; <<
449 } <<
450 <<
451 If the ``CLOCK_REALTIME`` clock is set, for ex <<
452 hrtimer framework calls ``timerfd_clock_was_se <<
453 ``cancel_list`` and wakes up processes waiting <<
454 the ``cancel_list``, the ``might_cancel`` flag <<
455 objects:: <<
456 <<
457 void timerfd_clock_was_set(void) <<
458 { <<
459 ktime_t moffs = ktime_mono_to_ <<
460 struct timerfd_ctx *ctx; <<
461 unsigned long flags; <<
462 <<
463 rcu_read_lock(); <<
464 list_for_each_entry_rcu(ctx, & <<
465 if (!ctx->might_cancel <<
466 continue; <<
467 spin_lock_irqsave(&ctx <<
468 if (ctx->moffs != moff <<
469 ctx->moffs = K <<
470 ctx->ticks++; <<
471 wake_up_locked <<
472 } <<
473 spin_unlock_irqrestore <<
474 } <<
475 rcu_read_unlock(); <<
476 } <<
477 <<
478 The key point is that because RCU-protected tr <<
479 ``cancel_list`` happens concurrently with obje <<
480 sometimes the traversal can access an object t <<
481 the list. In this example, a flag is used to s <<
482 <<
483 <<
484 Summary 298 Summary
485 ------- 299 -------
486 300
487 Read-mostly list-based data structures that ca 301 Read-mostly list-based data structures that can tolerate stale data are
488 the most amenable to use of RCU. The simplest 302 the most amenable to use of RCU. The simplest case is where entries are
489 either added or deleted from the data structur 303 either added or deleted from the data structure (or atomically modified
490 in place), but non-atomic in-place modificatio 304 in place), but non-atomic in-place modifications can be handled by making
491 a copy, updating the copy, then replacing the 305 a copy, updating the copy, then replacing the original with the copy.
492 If stale data cannot be tolerated, then a *del !! 306 If stale data cannot be tolerated, then a "deleted" flag may be used
493 in conjunction with a per-entry spinlock in or 307 in conjunction with a per-entry spinlock in order to allow the search
494 function to reject newly deleted data. 308 function to reject newly deleted data.
495 309
496 .. _quick_quiz_answer: !! 310 .. _answer_quick_quiz_list:
497 311
498 Answer to Quick Quiz: 312 Answer to Quick Quiz:
499 For the deleted-flag technique to be h !! 313 Why does the search function need to return holding the per-entry
500 to hold the per-entry lock while retur !! 314 lock for this deleted-flag technique to be helpful?
501 315
502 If the search function drops the per-e 316 If the search function drops the per-entry lock before returning,
503 then the caller will be processing sta 317 then the caller will be processing stale data in any case. If it
504 is really OK to be processing stale da 318 is really OK to be processing stale data, then you don't need a
505 *deleted* flag. If processing stale d !! 319 "deleted" flag. If processing stale data really is a problem,
506 then you need to hold the per-entry lo 320 then you need to hold the per-entry lock across all of the code
507 that uses the value that was returned. 321 that uses the value that was returned.
508 <<
509 :ref:`Back to Quick Quiz <quick_quiz>` <<
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.