2 * Read-Copy Update mechanism for mutual exclusion (tree-based version)
3 * Internal non-public definitions that provide either classic
4 * or preemptable semantics.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 * Copyright Red Hat, 2009
21 * Copyright IBM Corporation, 2009
23 * Author: Ingo Molnar <mingo@elte.hu>
24 * Paul E. McKenney <paulmck@linux.vnet.ibm.com>
28 #ifdef CONFIG_TREE_PREEMPT_RCU
30 struct rcu_state rcu_preempt_state
= RCU_STATE_INITIALIZER(rcu_preempt_state
);
31 DEFINE_PER_CPU(struct rcu_data
, rcu_preempt_data
);
34 * Tell them what RCU they are running.
36 static void __init
rcu_bootup_announce(void)
39 "Experimental preemptable hierarchical RCU implementation.\n");
43 * Return the number of RCU-preempt batches processed thus far
44 * for debug and statistics.
46 long rcu_batches_completed_preempt(void)
48 return rcu_preempt_state
.completed
;
50 EXPORT_SYMBOL_GPL(rcu_batches_completed_preempt
);
53 * Return the number of RCU batches processed thus far for debug & stats.
55 long rcu_batches_completed(void)
57 return rcu_batches_completed_preempt();
59 EXPORT_SYMBOL_GPL(rcu_batches_completed
);
62 * Record a preemptable-RCU quiescent state for the specified CPU. Note
63 * that this just means that the task currently running on the CPU is
64 * not in a quiescent state. There might be any number of tasks blocked
65 * while in an RCU read-side critical section.
67 static void rcu_preempt_qs(int cpu
)
69 struct rcu_data
*rdp
= &per_cpu(rcu_preempt_data
, cpu
);
70 rdp
->passed_quiesc_completed
= rdp
->gpnum
- 1;
72 rdp
->passed_quiesc
= 1;
76 * We have entered the scheduler, and the current task might soon be
77 * context-switched away from. If this task is in an RCU read-side
78 * critical section, we will no longer be able to rely on the CPU to
79 * record that fact, so we enqueue the task on the appropriate entry
80 * of the blocked_tasks[] array. The task will dequeue itself when
81 * it exits the outermost enclosing RCU read-side critical section.
82 * Therefore, the current grace period cannot be permitted to complete
83 * until the blocked_tasks[] entry indexed by the low-order bit of
86 * Caller must disable preemption.
88 static void rcu_preempt_note_context_switch(int cpu
)
90 struct task_struct
*t
= current
;
96 if (t
->rcu_read_lock_nesting
&&
97 (t
->rcu_read_unlock_special
& RCU_READ_UNLOCK_BLOCKED
) == 0) {
99 /* Possibly blocking in an RCU read-side critical section. */
100 rdp
= rcu_preempt_state
.rda
[cpu
];
102 spin_lock_irqsave(&rnp
->lock
, flags
);
103 t
->rcu_read_unlock_special
|= RCU_READ_UNLOCK_BLOCKED
;
104 t
->rcu_blocked_node
= rnp
;
107 * If this CPU has already checked in, then this task
108 * will hold up the next grace period rather than the
109 * current grace period. Queue the task accordingly.
110 * If the task is queued for the current grace period
111 * (i.e., this CPU has not yet passed through a quiescent
112 * state for the current grace period), then as long
113 * as that task remains queued, the current grace period
116 * But first, note that the current CPU must still be
119 WARN_ON_ONCE((rdp
->grpmask
& rnp
->qsmaskinit
) == 0);
120 WARN_ON_ONCE(!list_empty(&t
->rcu_node_entry
));
121 phase
= (rnp
->gpnum
+ !(rnp
->qsmask
& rdp
->grpmask
)) & 0x1;
122 list_add(&t
->rcu_node_entry
, &rnp
->blocked_tasks
[phase
]);
123 spin_unlock_irqrestore(&rnp
->lock
, flags
);
127 * Either we were not in an RCU read-side critical section to
128 * begin with, or we have now recorded that critical section
129 * globally. Either way, we can now note a quiescent state
130 * for this CPU. Again, if we were in an RCU read-side critical
131 * section, and if that critical section was blocking the current
132 * grace period, then the fact that the task has been enqueued
133 * means that we continue to block the current grace period.
136 local_irq_save(flags
);
137 t
->rcu_read_unlock_special
&= ~RCU_READ_UNLOCK_NEED_QS
;
138 local_irq_restore(flags
);
142 * Tree-preemptable RCU implementation for rcu_read_lock().
143 * Just increment ->rcu_read_lock_nesting, shared state will be updated
146 void __rcu_read_lock(void)
148 ACCESS_ONCE(current
->rcu_read_lock_nesting
)++;
149 barrier(); /* needed if we ever invoke rcu_read_lock in rcutree.c */
151 EXPORT_SYMBOL_GPL(__rcu_read_lock
);
154 * Check for preempted RCU readers blocking the current grace period
155 * for the specified rcu_node structure. If the caller needs a reliable
156 * answer, it must hold the rcu_node's ->lock.
158 static int rcu_preempted_readers(struct rcu_node
*rnp
)
160 return !list_empty(&rnp
->blocked_tasks
[rnp
->gpnum
& 0x1]);
164 * Record a quiescent state for all tasks that were previously queued
165 * on the specified rcu_node structure and that were blocking the current
166 * RCU grace period. The caller must hold the specified rnp->lock with
167 * irqs disabled, and this lock is released upon return, but irqs remain
170 static void task_quiet(struct rcu_node
*rnp
, unsigned long flags
)
171 __releases(rnp
->lock
)
174 struct rcu_node
*rnp_p
;
176 if (rnp
->qsmask
!= 0 || rcu_preempted_readers(rnp
)) {
177 spin_unlock_irqrestore(&rnp
->lock
, flags
);
178 return; /* Still need more quiescent states! */
184 * Either there is only one rcu_node in the tree,
185 * or tasks were kicked up to root rcu_node due to
186 * CPUs going offline.
188 cpu_quiet_msk_finish(&rcu_preempt_state
, flags
);
192 /* Report up the rest of the hierarchy. */
194 spin_unlock(&rnp
->lock
); /* irqs remain disabled. */
195 spin_lock(&rnp_p
->lock
); /* irqs already disabled. */
196 cpu_quiet_msk(mask
, &rcu_preempt_state
, rnp_p
, flags
);
200 * Handle special cases during rcu_read_unlock(), such as needing to
201 * notify RCU core processing or task having blocked during the RCU
202 * read-side critical section.
204 static void rcu_read_unlock_special(struct task_struct
*t
)
208 struct rcu_node
*rnp
;
211 /* NMI handlers cannot block and cannot safely manipulate state. */
215 local_irq_save(flags
);
218 * If RCU core is waiting for this CPU to exit critical section,
219 * let it know that we have done so.
221 special
= t
->rcu_read_unlock_special
;
222 if (special
& RCU_READ_UNLOCK_NEED_QS
) {
223 t
->rcu_read_unlock_special
&= ~RCU_READ_UNLOCK_NEED_QS
;
224 rcu_preempt_qs(smp_processor_id());
227 /* Hardware IRQ handlers cannot block. */
229 local_irq_restore(flags
);
233 /* Clean up if blocked during RCU read-side critical section. */
234 if (special
& RCU_READ_UNLOCK_BLOCKED
) {
235 t
->rcu_read_unlock_special
&= ~RCU_READ_UNLOCK_BLOCKED
;
238 * Remove this task from the list it blocked on. The
239 * task can migrate while we acquire the lock, but at
240 * most one time. So at most two passes through loop.
243 rnp
= t
->rcu_blocked_node
;
244 spin_lock(&rnp
->lock
); /* irqs already disabled. */
245 if (rnp
== t
->rcu_blocked_node
)
247 spin_unlock(&rnp
->lock
); /* irqs remain disabled. */
249 empty
= !rcu_preempted_readers(rnp
);
250 list_del_init(&t
->rcu_node_entry
);
251 t
->rcu_blocked_node
= NULL
;
254 * If this was the last task on the current list, and if
255 * we aren't waiting on any CPUs, report the quiescent state.
256 * Note that task_quiet() releases rnp->lock.
259 spin_unlock_irqrestore(&rnp
->lock
, flags
);
261 task_quiet(rnp
, flags
);
263 local_irq_restore(flags
);
268 * Tree-preemptable RCU implementation for rcu_read_unlock().
269 * Decrement ->rcu_read_lock_nesting. If the result is zero (outermost
270 * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then
271 * invoke rcu_read_unlock_special() to clean up after a context switch
272 * in an RCU read-side critical section and other special cases.
274 void __rcu_read_unlock(void)
276 struct task_struct
*t
= current
;
278 barrier(); /* needed if we ever invoke rcu_read_unlock in rcutree.c */
279 if (--ACCESS_ONCE(t
->rcu_read_lock_nesting
) == 0 &&
280 unlikely(ACCESS_ONCE(t
->rcu_read_unlock_special
)))
281 rcu_read_unlock_special(t
);
283 EXPORT_SYMBOL_GPL(__rcu_read_unlock
);
285 #ifdef CONFIG_RCU_CPU_STALL_DETECTOR
288 * Scan the current list of tasks blocked within RCU read-side critical
289 * sections, printing out the tid of each.
291 static void rcu_print_task_stall(struct rcu_node
*rnp
)
294 struct list_head
*lp
;
296 struct task_struct
*t
;
298 if (rcu_preempted_readers(rnp
)) {
299 spin_lock_irqsave(&rnp
->lock
, flags
);
300 phase
= rnp
->gpnum
& 0x1;
301 lp
= &rnp
->blocked_tasks
[phase
];
302 list_for_each_entry(t
, lp
, rcu_node_entry
)
303 printk(" P%d", t
->pid
);
304 spin_unlock_irqrestore(&rnp
->lock
, flags
);
308 #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
311 * Check that the list of blocked tasks for the newly completed grace
312 * period is in fact empty. It is a serious bug to complete a grace
313 * period that still has RCU readers blocked! This function must be
314 * invoked -before- updating this rnp's ->gpnum, and the rnp's ->lock
315 * must be held by the caller.
317 static void rcu_preempt_check_blocked_tasks(struct rcu_node
*rnp
)
319 WARN_ON_ONCE(rcu_preempted_readers(rnp
));
320 WARN_ON_ONCE(rnp
->qsmask
);
323 #ifdef CONFIG_HOTPLUG_CPU
326 * Handle tasklist migration for case in which all CPUs covered by the
327 * specified rcu_node have gone offline. Move them up to the root
328 * rcu_node. The reason for not just moving them to the immediate
329 * parent is to remove the need for rcu_read_unlock_special() to
330 * make more than two attempts to acquire the target rcu_node's lock.
331 * Returns true if there were tasks blocking the current RCU grace
334 * Returns 1 if there was previously a task blocking the current grace
335 * period on the specified rcu_node structure.
337 * The caller must hold rnp->lock with irqs disabled.
339 static int rcu_preempt_offline_tasks(struct rcu_state
*rsp
,
340 struct rcu_node
*rnp
,
341 struct rcu_data
*rdp
)
344 struct list_head
*lp
;
345 struct list_head
*lp_root
;
347 struct rcu_node
*rnp_root
= rcu_get_root(rsp
);
348 struct task_struct
*tp
;
350 if (rnp
== rnp_root
) {
351 WARN_ONCE(1, "Last CPU thought to be offlined?");
352 return 0; /* Shouldn't happen: at least one CPU online. */
354 WARN_ON_ONCE(rnp
!= rdp
->mynode
&&
355 (!list_empty(&rnp
->blocked_tasks
[0]) ||
356 !list_empty(&rnp
->blocked_tasks
[1])));
359 * Move tasks up to root rcu_node. Rely on the fact that the
360 * root rcu_node can be at most one ahead of the rest of the
361 * rcu_nodes in terms of gp_num value. This fact allows us to
362 * move the blocked_tasks[] array directly, element by element.
364 retval
= rcu_preempted_readers(rnp
);
365 for (i
= 0; i
< 2; i
++) {
366 lp
= &rnp
->blocked_tasks
[i
];
367 lp_root
= &rnp_root
->blocked_tasks
[i
];
368 while (!list_empty(lp
)) {
369 tp
= list_entry(lp
->next
, typeof(*tp
), rcu_node_entry
);
370 spin_lock(&rnp_root
->lock
); /* irqs already disabled */
371 list_del(&tp
->rcu_node_entry
);
372 tp
->rcu_blocked_node
= rnp_root
;
373 list_add(&tp
->rcu_node_entry
, lp_root
);
374 spin_unlock(&rnp_root
->lock
); /* irqs remain disabled */
381 * Do CPU-offline processing for preemptable RCU.
383 static void rcu_preempt_offline_cpu(int cpu
)
385 __rcu_offline_cpu(cpu
, &rcu_preempt_state
);
388 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
391 * Check for a quiescent state from the current CPU. When a task blocks,
392 * the task is recorded in the corresponding CPU's rcu_node structure,
393 * which is checked elsewhere.
395 * Caller must disable hard irqs.
397 static void rcu_preempt_check_callbacks(int cpu
)
399 struct task_struct
*t
= current
;
401 if (t
->rcu_read_lock_nesting
== 0) {
402 t
->rcu_read_unlock_special
&= ~RCU_READ_UNLOCK_NEED_QS
;
406 if (per_cpu(rcu_preempt_data
, cpu
).qs_pending
)
407 t
->rcu_read_unlock_special
|= RCU_READ_UNLOCK_NEED_QS
;
411 * Process callbacks for preemptable RCU.
413 static void rcu_preempt_process_callbacks(void)
415 __rcu_process_callbacks(&rcu_preempt_state
,
416 &__get_cpu_var(rcu_preempt_data
));
420 * Queue a preemptable-RCU callback for invocation after a grace period.
422 void call_rcu(struct rcu_head
*head
, void (*func
)(struct rcu_head
*rcu
))
424 __call_rcu(head
, func
, &rcu_preempt_state
);
426 EXPORT_SYMBOL_GPL(call_rcu
);
429 * Wait for an rcu-preempt grace period. We are supposed to expedite the
430 * grace period, but this is the crude slow compatability hack, so just
431 * invoke synchronize_rcu().
433 void synchronize_rcu_expedited(void)
437 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited
);
440 * Check to see if there is any immediate preemptable-RCU-related work
443 static int rcu_preempt_pending(int cpu
)
445 return __rcu_pending(&rcu_preempt_state
,
446 &per_cpu(rcu_preempt_data
, cpu
));
450 * Does preemptable RCU need the CPU to stay out of dynticks mode?
452 static int rcu_preempt_needs_cpu(int cpu
)
454 return !!per_cpu(rcu_preempt_data
, cpu
).nxtlist
;
458 * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
460 void rcu_barrier(void)
462 _rcu_barrier(&rcu_preempt_state
, call_rcu
);
464 EXPORT_SYMBOL_GPL(rcu_barrier
);
467 * Initialize preemptable RCU's per-CPU data.
469 static void __cpuinit
rcu_preempt_init_percpu_data(int cpu
)
471 rcu_init_percpu_data(cpu
, &rcu_preempt_state
, 1);
475 * Move preemptable RCU's callbacks to ->orphan_cbs_list.
477 static void rcu_preempt_send_cbs_to_orphanage(void)
479 rcu_send_cbs_to_orphanage(&rcu_preempt_state
);
483 * Initialize preemptable RCU's state structures.
485 static void __init
__rcu_init_preempt(void)
487 RCU_INIT_FLAVOR(&rcu_preempt_state
, rcu_preempt_data
);
491 * Check for a task exiting while in a preemptable-RCU read-side
492 * critical section, clean up if so. No need to issue warnings,
493 * as debug_check_no_locks_held() already does this if lockdep
498 struct task_struct
*t
= current
;
500 if (t
->rcu_read_lock_nesting
== 0)
502 t
->rcu_read_lock_nesting
= 1;
506 #else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
509 * Tell them what RCU they are running.
511 static void __init
rcu_bootup_announce(void)
513 printk(KERN_INFO
"Hierarchical RCU implementation.\n");
517 * Return the number of RCU batches processed thus far for debug & stats.
519 long rcu_batches_completed(void)
521 return rcu_batches_completed_sched();
523 EXPORT_SYMBOL_GPL(rcu_batches_completed
);
526 * Because preemptable RCU does not exist, we never have to check for
527 * CPUs being in quiescent states.
529 static void rcu_preempt_note_context_switch(int cpu
)
534 * Because preemptable RCU does not exist, there are never any preempted
537 static int rcu_preempted_readers(struct rcu_node
*rnp
)
542 #ifdef CONFIG_HOTPLUG_CPU
544 /* Because preemptible RCU does not exist, no quieting of tasks. */
545 static void task_quiet(struct rcu_node
*rnp
, unsigned long flags
)
547 spin_unlock_irqrestore(&rnp
->lock
, flags
);
550 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
552 #ifdef CONFIG_RCU_CPU_STALL_DETECTOR
555 * Because preemptable RCU does not exist, we never have to check for
556 * tasks blocked within RCU read-side critical sections.
558 static void rcu_print_task_stall(struct rcu_node
*rnp
)
562 #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
565 * Because there is no preemptable RCU, there can be no readers blocked,
566 * so there is no need to check for blocked tasks. So check only for
567 * bogus qsmask values.
569 static void rcu_preempt_check_blocked_tasks(struct rcu_node
*rnp
)
571 WARN_ON_ONCE(rnp
->qsmask
);
574 #ifdef CONFIG_HOTPLUG_CPU
577 * Because preemptable RCU does not exist, it never needs to migrate
578 * tasks that were blocked within RCU read-side critical sections, and
579 * such non-existent tasks cannot possibly have been blocking the current
582 static int rcu_preempt_offline_tasks(struct rcu_state
*rsp
,
583 struct rcu_node
*rnp
,
584 struct rcu_data
*rdp
)
590 * Because preemptable RCU does not exist, it never needs CPU-offline
593 static void rcu_preempt_offline_cpu(int cpu
)
597 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
600 * Because preemptable RCU does not exist, it never has any callbacks
603 static void rcu_preempt_check_callbacks(int cpu
)
608 * Because preemptable RCU does not exist, it never has any callbacks
611 static void rcu_preempt_process_callbacks(void)
616 * In classic RCU, call_rcu() is just call_rcu_sched().
618 void call_rcu(struct rcu_head
*head
, void (*func
)(struct rcu_head
*rcu
))
620 call_rcu_sched(head
, func
);
622 EXPORT_SYMBOL_GPL(call_rcu
);
625 * Wait for an rcu-preempt grace period, but make it happen quickly.
626 * But because preemptable RCU does not exist, map to rcu-sched.
628 void synchronize_rcu_expedited(void)
630 synchronize_sched_expedited();
632 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited
);
635 * Because preemptable RCU does not exist, it never has any work to do.
637 static int rcu_preempt_pending(int cpu
)
643 * Because preemptable RCU does not exist, it never needs any CPU.
645 static int rcu_preempt_needs_cpu(int cpu
)
651 * Because preemptable RCU does not exist, rcu_barrier() is just
652 * another name for rcu_barrier_sched().
654 void rcu_barrier(void)
658 EXPORT_SYMBOL_GPL(rcu_barrier
);
661 * Because preemptable RCU does not exist, there is no per-CPU
662 * data to initialize.
664 static void __cpuinit
rcu_preempt_init_percpu_data(int cpu
)
669 * Because there is no preemptable RCU, there are no callbacks to move.
671 static void rcu_preempt_send_cbs_to_orphanage(void)
676 * Because preemptable RCU does not exist, it need not be initialized.
678 static void __init
__rcu_init_preempt(void)
682 #endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */