Root/kernel/rcutree_plugin.h

1/*
2 * Read-Copy Update mechanism for mutual exclusion (tree-based version)
3 * Internal non-public definitions that provide either classic
4 * or preemptable semantics.
5 *
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.
10 *
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.
15 *
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.
19 *
20 * Copyright Red Hat, 2009
21 * Copyright IBM Corporation, 2009
22 *
23 * Author: Ingo Molnar <mingo@elte.hu>
24 * Paul E. McKenney <paulmck@linux.vnet.ibm.com>
25 */
26
27
28#ifdef CONFIG_TREE_PREEMPT_RCU
29
30struct rcu_state rcu_preempt_state = RCU_STATE_INITIALIZER(rcu_preempt_state);
31DEFINE_PER_CPU(struct rcu_data, rcu_preempt_data);
32
33/*
34 * Tell them what RCU they are running.
35 */
36static void rcu_bootup_announce(void)
37{
38    printk(KERN_INFO
39           "Experimental preemptable hierarchical RCU implementation.\n");
40}
41
42/*
43 * Return the number of RCU-preempt batches processed thus far
44 * for debug and statistics.
45 */
46long rcu_batches_completed_preempt(void)
47{
48    return rcu_preempt_state.completed;
49}
50EXPORT_SYMBOL_GPL(rcu_batches_completed_preempt);
51
52/*
53 * Return the number of RCU batches processed thus far for debug & stats.
54 */
55long rcu_batches_completed(void)
56{
57    return rcu_batches_completed_preempt();
58}
59EXPORT_SYMBOL_GPL(rcu_batches_completed);
60
61/*
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.
66 */
67static void rcu_preempt_qs(int cpu)
68{
69    struct rcu_data *rdp = &per_cpu(rcu_preempt_data, cpu);
70    rdp->passed_quiesc_completed = rdp->completed;
71    barrier();
72    rdp->passed_quiesc = 1;
73}
74
75/*
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
84 * rnp->gpnum empties.
85 *
86 * Caller must disable preemption.
87 */
88static void rcu_preempt_note_context_switch(int cpu)
89{
90    struct task_struct *t = current;
91    unsigned long flags;
92    int phase;
93    struct rcu_data *rdp;
94    struct rcu_node *rnp;
95
96    if (t->rcu_read_lock_nesting &&
97        (t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {
98
99        /* Possibly blocking in an RCU read-side critical section. */
100        rdp = rcu_preempt_state.rda[cpu];
101        rnp = rdp->mynode;
102        spin_lock_irqsave(&rnp->lock, flags);
103        t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
104        t->rcu_blocked_node = rnp;
105
106        /*
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
114         * cannot end.
115         *
116         * But first, note that the current CPU must still be
117         * on line!
118         */
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);
124    }
125
126    /*
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.
134     */
135    rcu_preempt_qs(cpu);
136    local_irq_save(flags);
137    t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
138    local_irq_restore(flags);
139}
140
141/*
142 * Tree-preemptable RCU implementation for rcu_read_lock().
143 * Just increment ->rcu_read_lock_nesting, shared state will be updated
144 * if we block.
145 */
146void __rcu_read_lock(void)
147{
148    ACCESS_ONCE(current->rcu_read_lock_nesting)++;
149    barrier(); /* needed if we ever invoke rcu_read_lock in rcutree.c */
150}
151EXPORT_SYMBOL_GPL(__rcu_read_lock);
152
153/*
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.
157 */
158static int rcu_preempted_readers(struct rcu_node *rnp)
159{
160    return !list_empty(&rnp->blocked_tasks[rnp->gpnum & 0x1]);
161}
162
163static void rcu_read_unlock_special(struct task_struct *t)
164{
165    int empty;
166    unsigned long flags;
167    unsigned long mask;
168    struct rcu_node *rnp;
169    int special;
170
171    /* NMI handlers cannot block and cannot safely manipulate state. */
172    if (in_nmi())
173        return;
174
175    local_irq_save(flags);
176
177    /*
178     * If RCU core is waiting for this CPU to exit critical section,
179     * let it know that we have done so.
180     */
181    special = t->rcu_read_unlock_special;
182    if (special & RCU_READ_UNLOCK_NEED_QS) {
183        t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
184        rcu_preempt_qs(smp_processor_id());
185    }
186
187    /* Hardware IRQ handlers cannot block. */
188    if (in_irq()) {
189        local_irq_restore(flags);
190        return;
191    }
192
193    /* Clean up if blocked during RCU read-side critical section. */
194    if (special & RCU_READ_UNLOCK_BLOCKED) {
195        t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
196
197        /*
198         * Remove this task from the list it blocked on. The
199         * task can migrate while we acquire the lock, but at
200         * most one time. So at most two passes through loop.
201         */
202        for (;;) {
203            rnp = t->rcu_blocked_node;
204            spin_lock(&rnp->lock); /* irqs already disabled. */
205            if (rnp == t->rcu_blocked_node)
206                break;
207            spin_unlock(&rnp->lock); /* irqs remain disabled. */
208        }
209        empty = !rcu_preempted_readers(rnp);
210        list_del_init(&t->rcu_node_entry);
211        t->rcu_blocked_node = NULL;
212
213        /*
214         * If this was the last task on the current list, and if
215         * we aren't waiting on any CPUs, report the quiescent state.
216         * Note that both cpu_quiet_msk_finish() and cpu_quiet_msk()
217         * drop rnp->lock and restore irq.
218         */
219        if (!empty && rnp->qsmask == 0 &&
220            !rcu_preempted_readers(rnp)) {
221            struct rcu_node *rnp_p;
222
223            if (rnp->parent == NULL) {
224                /* Only one rcu_node in the tree. */
225                cpu_quiet_msk_finish(&rcu_preempt_state, flags);
226                return;
227            }
228            /* Report up the rest of the hierarchy. */
229            mask = rnp->grpmask;
230            spin_unlock_irqrestore(&rnp->lock, flags);
231            rnp_p = rnp->parent;
232            spin_lock_irqsave(&rnp_p->lock, flags);
233            WARN_ON_ONCE(rnp->qsmask);
234            cpu_quiet_msk(mask, &rcu_preempt_state, rnp_p, flags);
235            return;
236        }
237        spin_unlock(&rnp->lock);
238    }
239    local_irq_restore(flags);
240}
241
242/*
243 * Tree-preemptable RCU implementation for rcu_read_unlock().
244 * Decrement ->rcu_read_lock_nesting. If the result is zero (outermost
245 * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then
246 * invoke rcu_read_unlock_special() to clean up after a context switch
247 * in an RCU read-side critical section and other special cases.
248 */
249void __rcu_read_unlock(void)
250{
251    struct task_struct *t = current;
252
253    barrier(); /* needed if we ever invoke rcu_read_unlock in rcutree.c */
254    if (--ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
255        unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))
256        rcu_read_unlock_special(t);
257}
258EXPORT_SYMBOL_GPL(__rcu_read_unlock);
259
260#ifdef CONFIG_RCU_CPU_STALL_DETECTOR
261
262/*
263 * Scan the current list of tasks blocked within RCU read-side critical
264 * sections, printing out the tid of each.
265 */
266static void rcu_print_task_stall(struct rcu_node *rnp)
267{
268    unsigned long flags;
269    struct list_head *lp;
270    int phase;
271    struct task_struct *t;
272
273    if (rcu_preempted_readers(rnp)) {
274        spin_lock_irqsave(&rnp->lock, flags);
275        phase = rnp->gpnum & 0x1;
276        lp = &rnp->blocked_tasks[phase];
277        list_for_each_entry(t, lp, rcu_node_entry)
278            printk(" P%d", t->pid);
279        spin_unlock_irqrestore(&rnp->lock, flags);
280    }
281}
282
283#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
284
285/*
286 * Check that the list of blocked tasks for the newly completed grace
287 * period is in fact empty. It is a serious bug to complete a grace
288 * period that still has RCU readers blocked! This function must be
289 * invoked -before- updating this rnp's ->gpnum, and the rnp's ->lock
290 * must be held by the caller.
291 */
292static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
293{
294    WARN_ON_ONCE(rcu_preempted_readers(rnp));
295    WARN_ON_ONCE(rnp->qsmask);
296}
297
298#ifdef CONFIG_HOTPLUG_CPU
299
300/*
301 * Handle tasklist migration for case in which all CPUs covered by the
302 * specified rcu_node have gone offline. Move them up to the root
303 * rcu_node. The reason for not just moving them to the immediate
304 * parent is to remove the need for rcu_read_unlock_special() to
305 * make more than two attempts to acquire the target rcu_node's lock.
306 *
307 * Returns 1 if there was previously a task blocking the current grace
308 * period on the specified rcu_node structure.
309 *
310 * The caller must hold rnp->lock with irqs disabled.
311 */
312static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
313                     struct rcu_node *rnp,
314                     struct rcu_data *rdp)
315{
316    int i;
317    struct list_head *lp;
318    struct list_head *lp_root;
319    int retval = rcu_preempted_readers(rnp);
320    struct rcu_node *rnp_root = rcu_get_root(rsp);
321    struct task_struct *tp;
322
323    if (rnp == rnp_root) {
324        WARN_ONCE(1, "Last CPU thought to be offlined?");
325        return 0; /* Shouldn't happen: at least one CPU online. */
326    }
327    WARN_ON_ONCE(rnp != rdp->mynode &&
328             (!list_empty(&rnp->blocked_tasks[0]) ||
329              !list_empty(&rnp->blocked_tasks[1])));
330
331    /*
332     * Move tasks up to root rcu_node. Rely on the fact that the
333     * root rcu_node can be at most one ahead of the rest of the
334     * rcu_nodes in terms of gp_num value. This fact allows us to
335     * move the blocked_tasks[] array directly, element by element.
336     */
337    for (i = 0; i < 2; i++) {
338        lp = &rnp->blocked_tasks[i];
339        lp_root = &rnp_root->blocked_tasks[i];
340        while (!list_empty(lp)) {
341            tp = list_entry(lp->next, typeof(*tp), rcu_node_entry);
342            spin_lock(&rnp_root->lock); /* irqs already disabled */
343            list_del(&tp->rcu_node_entry);
344            tp->rcu_blocked_node = rnp_root;
345            list_add(&tp->rcu_node_entry, lp_root);
346            spin_unlock(&rnp_root->lock); /* irqs remain disabled */
347        }
348    }
349
350    return retval;
351}
352
353/*
354 * Do CPU-offline processing for preemptable RCU.
355 */
356static void rcu_preempt_offline_cpu(int cpu)
357{
358    __rcu_offline_cpu(cpu, &rcu_preempt_state);
359}
360
361#endif /* #ifdef CONFIG_HOTPLUG_CPU */
362
363/*
364 * Check for a quiescent state from the current CPU. When a task blocks,
365 * the task is recorded in the corresponding CPU's rcu_node structure,
366 * which is checked elsewhere.
367 *
368 * Caller must disable hard irqs.
369 */
370static void rcu_preempt_check_callbacks(int cpu)
371{
372    struct task_struct *t = current;
373
374    if (t->rcu_read_lock_nesting == 0) {
375        t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
376        rcu_preempt_qs(cpu);
377        return;
378    }
379    if (per_cpu(rcu_preempt_data, cpu).qs_pending)
380        t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;
381}
382
383/*
384 * Process callbacks for preemptable RCU.
385 */
386static void rcu_preempt_process_callbacks(void)
387{
388    __rcu_process_callbacks(&rcu_preempt_state,
389                &__get_cpu_var(rcu_preempt_data));
390}
391
392/*
393 * Queue a preemptable-RCU callback for invocation after a grace period.
394 */
395void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
396{
397    __call_rcu(head, func, &rcu_preempt_state);
398}
399EXPORT_SYMBOL_GPL(call_rcu);
400
401/*
402 * Wait for an rcu-preempt grace period. We are supposed to expedite the
403 * grace period, but this is the crude slow compatability hack, so just
404 * invoke synchronize_rcu().
405 */
406void synchronize_rcu_expedited(void)
407{
408    synchronize_rcu();
409}
410EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
411
412/*
413 * Check to see if there is any immediate preemptable-RCU-related work
414 * to be done.
415 */
416static int rcu_preempt_pending(int cpu)
417{
418    return __rcu_pending(&rcu_preempt_state,
419                 &per_cpu(rcu_preempt_data, cpu));
420}
421
422/*
423 * Does preemptable RCU need the CPU to stay out of dynticks mode?
424 */
425static int rcu_preempt_needs_cpu(int cpu)
426{
427    return !!per_cpu(rcu_preempt_data, cpu).nxtlist;
428}
429
430/**
431 * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
432 */
433void rcu_barrier(void)
434{
435    _rcu_barrier(&rcu_preempt_state, call_rcu);
436}
437EXPORT_SYMBOL_GPL(rcu_barrier);
438
439/*
440 * Initialize preemptable RCU's per-CPU data.
441 */
442static void __cpuinit rcu_preempt_init_percpu_data(int cpu)
443{
444    rcu_init_percpu_data(cpu, &rcu_preempt_state, 1);
445}
446
447/*
448 * Move preemptable RCU's callbacks to ->orphan_cbs_list.
449 */
450static void rcu_preempt_send_cbs_to_orphanage(void)
451{
452    rcu_send_cbs_to_orphanage(&rcu_preempt_state);
453}
454
455/*
456 * Initialize preemptable RCU's state structures.
457 */
458static void __init __rcu_init_preempt(void)
459{
460    RCU_INIT_FLAVOR(&rcu_preempt_state, rcu_preempt_data);
461}
462
463/*
464 * Check for a task exiting while in a preemptable-RCU read-side
465 * critical section, clean up if so. No need to issue warnings,
466 * as debug_check_no_locks_held() already does this if lockdep
467 * is enabled.
468 */
469void exit_rcu(void)
470{
471    struct task_struct *t = current;
472
473    if (t->rcu_read_lock_nesting == 0)
474        return;
475    t->rcu_read_lock_nesting = 1;
476    rcu_read_unlock();
477}
478
479#else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
480
481/*
482 * Tell them what RCU they are running.
483 */
484static void rcu_bootup_announce(void)
485{
486    printk(KERN_INFO "Hierarchical RCU implementation.\n");
487}
488
489/*
490 * Return the number of RCU batches processed thus far for debug & stats.
491 */
492long rcu_batches_completed(void)
493{
494    return rcu_batches_completed_sched();
495}
496EXPORT_SYMBOL_GPL(rcu_batches_completed);
497
498/*
499 * Because preemptable RCU does not exist, we never have to check for
500 * CPUs being in quiescent states.
501 */
502static void rcu_preempt_note_context_switch(int cpu)
503{
504}
505
506/*
507 * Because preemptable RCU does not exist, there are never any preempted
508 * RCU readers.
509 */
510static int rcu_preempted_readers(struct rcu_node *rnp)
511{
512    return 0;
513}
514
515#ifdef CONFIG_RCU_CPU_STALL_DETECTOR
516
517/*
518 * Because preemptable RCU does not exist, we never have to check for
519 * tasks blocked within RCU read-side critical sections.
520 */
521static void rcu_print_task_stall(struct rcu_node *rnp)
522{
523}
524
525#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
526
527/*
528 * Because there is no preemptable RCU, there can be no readers blocked,
529 * so there is no need to check for blocked tasks. So check only for
530 * bogus qsmask values.
531 */
532static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
533{
534    WARN_ON_ONCE(rnp->qsmask);
535}
536
537#ifdef CONFIG_HOTPLUG_CPU
538
539/*
540 * Because preemptable RCU does not exist, it never needs to migrate
541 * tasks that were blocked within RCU read-side critical sections, and
542 * such non-existent tasks cannot possibly have been blocking the current
543 * grace period.
544 */
545static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
546                     struct rcu_node *rnp,
547                     struct rcu_data *rdp)
548{
549    return 0;
550}
551
552/*
553 * Because preemptable RCU does not exist, it never needs CPU-offline
554 * processing.
555 */
556static void rcu_preempt_offline_cpu(int cpu)
557{
558}
559
560#endif /* #ifdef CONFIG_HOTPLUG_CPU */
561
562/*
563 * Because preemptable RCU does not exist, it never has any callbacks
564 * to check.
565 */
566static void rcu_preempt_check_callbacks(int cpu)
567{
568}
569
570/*
571 * Because preemptable RCU does not exist, it never has any callbacks
572 * to process.
573 */
574static void rcu_preempt_process_callbacks(void)
575{
576}
577
578/*
579 * In classic RCU, call_rcu() is just call_rcu_sched().
580 */
581void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
582{
583    call_rcu_sched(head, func);
584}
585EXPORT_SYMBOL_GPL(call_rcu);
586
587/*
588 * Wait for an rcu-preempt grace period, but make it happen quickly.
589 * But because preemptable RCU does not exist, map to rcu-sched.
590 */
591void synchronize_rcu_expedited(void)
592{
593    synchronize_sched_expedited();
594}
595EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
596
597/*
598 * Because preemptable RCU does not exist, it never has any work to do.
599 */
600static int rcu_preempt_pending(int cpu)
601{
602    return 0;
603}
604
605/*
606 * Because preemptable RCU does not exist, it never needs any CPU.
607 */
608static int rcu_preempt_needs_cpu(int cpu)
609{
610    return 0;
611}
612
613/*
614 * Because preemptable RCU does not exist, rcu_barrier() is just
615 * another name for rcu_barrier_sched().
616 */
617void rcu_barrier(void)
618{
619    rcu_barrier_sched();
620}
621EXPORT_SYMBOL_GPL(rcu_barrier);
622
623/*
624 * Because preemptable RCU does not exist, there is no per-CPU
625 * data to initialize.
626 */
627static void __cpuinit rcu_preempt_init_percpu_data(int cpu)
628{
629}
630
631/*
632 * Because there is no preemptable RCU, there are no callbacks to move.
633 */
634static void rcu_preempt_send_cbs_to_orphanage(void)
635{
636}
637
638/*
639 * Because preemptable RCU does not exist, it need not be initialized.
640 */
641static void __init __rcu_init_preempt(void)
642{
643}
644
645#endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */
646

Archive Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9



interactive