Merge branch 'ptrace' of git://git.kernel.org/pub/scm/linux/kernel/git/oleg/misc
[platform/adaptation/renesas_rcar/renesas_kernel.git] / kernel / rcutiny_plugin.h
1 /*
2  * Read-Copy Update mechanism for mutual exclusion, the Bloatwatch edition
3  * Internal non-public definitions that provide either classic
4  * or preemptible 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 (c) 2010 Linaro
21  *
22  * Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
23  */
24
25 #include <linux/kthread.h>
26 #include <linux/debugfs.h>
27 #include <linux/seq_file.h>
28
29 #ifdef CONFIG_RCU_TRACE
30 #define RCU_TRACE(stmt) stmt
31 #else /* #ifdef CONFIG_RCU_TRACE */
32 #define RCU_TRACE(stmt)
33 #endif /* #else #ifdef CONFIG_RCU_TRACE */
34
35 /* Global control variables for rcupdate callback mechanism. */
36 struct rcu_ctrlblk {
37         struct rcu_head *rcucblist;     /* List of pending callbacks (CBs). */
38         struct rcu_head **donetail;     /* ->next pointer of last "done" CB. */
39         struct rcu_head **curtail;      /* ->next pointer of last CB. */
40         RCU_TRACE(long qlen);           /* Number of pending CBs. */
41 };
42
43 /* Definition for rcupdate control block. */
44 static struct rcu_ctrlblk rcu_sched_ctrlblk = {
45         .donetail       = &rcu_sched_ctrlblk.rcucblist,
46         .curtail        = &rcu_sched_ctrlblk.rcucblist,
47 };
48
49 static struct rcu_ctrlblk rcu_bh_ctrlblk = {
50         .donetail       = &rcu_bh_ctrlblk.rcucblist,
51         .curtail        = &rcu_bh_ctrlblk.rcucblist,
52 };
53
54 #ifdef CONFIG_DEBUG_LOCK_ALLOC
55 int rcu_scheduler_active __read_mostly;
56 EXPORT_SYMBOL_GPL(rcu_scheduler_active);
57 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
58
59 #ifdef CONFIG_TINY_PREEMPT_RCU
60
61 #include <linux/delay.h>
62
63 /* Global control variables for preemptible RCU. */
64 struct rcu_preempt_ctrlblk {
65         struct rcu_ctrlblk rcb; /* curtail: ->next ptr of last CB for GP. */
66         struct rcu_head **nexttail;
67                                 /* Tasks blocked in a preemptible RCU */
68                                 /*  read-side critical section while an */
69                                 /*  preemptible-RCU grace period is in */
70                                 /*  progress must wait for a later grace */
71                                 /*  period.  This pointer points to the */
72                                 /*  ->next pointer of the last task that */
73                                 /*  must wait for a later grace period, or */
74                                 /*  to &->rcb.rcucblist if there is no */
75                                 /*  such task. */
76         struct list_head blkd_tasks;
77                                 /* Tasks blocked in RCU read-side critical */
78                                 /*  section.  Tasks are placed at the head */
79                                 /*  of this list and age towards the tail. */
80         struct list_head *gp_tasks;
81                                 /* Pointer to the first task blocking the */
82                                 /*  current grace period, or NULL if there */
83                                 /*  is no such task. */
84         struct list_head *exp_tasks;
85                                 /* Pointer to first task blocking the */
86                                 /*  current expedited grace period, or NULL */
87                                 /*  if there is no such task.  If there */
88                                 /*  is no current expedited grace period, */
89                                 /*  then there cannot be any such task. */
90 #ifdef CONFIG_RCU_BOOST
91         struct list_head *boost_tasks;
92                                 /* Pointer to first task that needs to be */
93                                 /*  priority-boosted, or NULL if no priority */
94                                 /*  boosting is needed.  If there is no */
95                                 /*  current or expedited grace period, there */
96                                 /*  can be no such task. */
97 #endif /* #ifdef CONFIG_RCU_BOOST */
98         u8 gpnum;               /* Current grace period. */
99         u8 gpcpu;               /* Last grace period blocked by the CPU. */
100         u8 completed;           /* Last grace period completed. */
101                                 /*  If all three are equal, RCU is idle. */
102 #ifdef CONFIG_RCU_BOOST
103         unsigned long boost_time; /* When to start boosting (jiffies) */
104 #endif /* #ifdef CONFIG_RCU_BOOST */
105 #ifdef CONFIG_RCU_TRACE
106         unsigned long n_grace_periods;
107 #ifdef CONFIG_RCU_BOOST
108         unsigned long n_tasks_boosted;
109                                 /* Total number of tasks boosted. */
110         unsigned long n_exp_boosts;
111                                 /* Number of tasks boosted for expedited GP. */
112         unsigned long n_normal_boosts;
113                                 /* Number of tasks boosted for normal GP. */
114         unsigned long n_balk_blkd_tasks;
115                                 /* Refused to boost: no blocked tasks. */
116         unsigned long n_balk_exp_gp_tasks;
117                                 /* Refused to boost: nothing blocking GP. */
118         unsigned long n_balk_boost_tasks;
119                                 /* Refused to boost: already boosting. */
120         unsigned long n_balk_notyet;
121                                 /* Refused to boost: not yet time. */
122         unsigned long n_balk_nos;
123                                 /* Refused to boost: not sure why, though. */
124                                 /*  This can happen due to race conditions. */
125 #endif /* #ifdef CONFIG_RCU_BOOST */
126 #endif /* #ifdef CONFIG_RCU_TRACE */
127 };
128
129 static struct rcu_preempt_ctrlblk rcu_preempt_ctrlblk = {
130         .rcb.donetail = &rcu_preempt_ctrlblk.rcb.rcucblist,
131         .rcb.curtail = &rcu_preempt_ctrlblk.rcb.rcucblist,
132         .nexttail = &rcu_preempt_ctrlblk.rcb.rcucblist,
133         .blkd_tasks = LIST_HEAD_INIT(rcu_preempt_ctrlblk.blkd_tasks),
134 };
135
136 static int rcu_preempted_readers_exp(void);
137 static void rcu_report_exp_done(void);
138
139 /*
140  * Return true if the CPU has not yet responded to the current grace period.
141  */
142 static int rcu_cpu_blocking_cur_gp(void)
143 {
144         return rcu_preempt_ctrlblk.gpcpu != rcu_preempt_ctrlblk.gpnum;
145 }
146
147 /*
148  * Check for a running RCU reader.  Because there is only one CPU,
149  * there can be but one running RCU reader at a time.  ;-)
150  */
151 static int rcu_preempt_running_reader(void)
152 {
153         return current->rcu_read_lock_nesting;
154 }
155
156 /*
157  * Check for preempted RCU readers blocking any grace period.
158  * If the caller needs a reliable answer, it must disable hard irqs.
159  */
160 static int rcu_preempt_blocked_readers_any(void)
161 {
162         return !list_empty(&rcu_preempt_ctrlblk.blkd_tasks);
163 }
164
165 /*
166  * Check for preempted RCU readers blocking the current grace period.
167  * If the caller needs a reliable answer, it must disable hard irqs.
168  */
169 static int rcu_preempt_blocked_readers_cgp(void)
170 {
171         return rcu_preempt_ctrlblk.gp_tasks != NULL;
172 }
173
174 /*
175  * Return true if another preemptible-RCU grace period is needed.
176  */
177 static int rcu_preempt_needs_another_gp(void)
178 {
179         return *rcu_preempt_ctrlblk.rcb.curtail != NULL;
180 }
181
182 /*
183  * Return true if a preemptible-RCU grace period is in progress.
184  * The caller must disable hardirqs.
185  */
186 static int rcu_preempt_gp_in_progress(void)
187 {
188         return rcu_preempt_ctrlblk.completed != rcu_preempt_ctrlblk.gpnum;
189 }
190
191 /*
192  * Advance a ->blkd_tasks-list pointer to the next entry, instead
193  * returning NULL if at the end of the list.
194  */
195 static struct list_head *rcu_next_node_entry(struct task_struct *t)
196 {
197         struct list_head *np;
198
199         np = t->rcu_node_entry.next;
200         if (np == &rcu_preempt_ctrlblk.blkd_tasks)
201                 np = NULL;
202         return np;
203 }
204
205 #ifdef CONFIG_RCU_TRACE
206
207 #ifdef CONFIG_RCU_BOOST
208 static void rcu_initiate_boost_trace(void);
209 #endif /* #ifdef CONFIG_RCU_BOOST */
210
211 /*
212  * Dump additional statistice for TINY_PREEMPT_RCU.
213  */
214 static void show_tiny_preempt_stats(struct seq_file *m)
215 {
216         seq_printf(m, "rcu_preempt: qlen=%ld gp=%lu g%u/p%u/c%u tasks=%c%c%c\n",
217                    rcu_preempt_ctrlblk.rcb.qlen,
218                    rcu_preempt_ctrlblk.n_grace_periods,
219                    rcu_preempt_ctrlblk.gpnum,
220                    rcu_preempt_ctrlblk.gpcpu,
221                    rcu_preempt_ctrlblk.completed,
222                    "T."[list_empty(&rcu_preempt_ctrlblk.blkd_tasks)],
223                    "N."[!rcu_preempt_ctrlblk.gp_tasks],
224                    "E."[!rcu_preempt_ctrlblk.exp_tasks]);
225 #ifdef CONFIG_RCU_BOOST
226         seq_printf(m, "%sttb=%c ntb=%lu neb=%lu nnb=%lu j=%04x bt=%04x\n",
227                    "             ",
228                    "B."[!rcu_preempt_ctrlblk.boost_tasks],
229                    rcu_preempt_ctrlblk.n_tasks_boosted,
230                    rcu_preempt_ctrlblk.n_exp_boosts,
231                    rcu_preempt_ctrlblk.n_normal_boosts,
232                    (int)(jiffies & 0xffff),
233                    (int)(rcu_preempt_ctrlblk.boost_time & 0xffff));
234         seq_printf(m, "%s: nt=%lu egt=%lu bt=%lu ny=%lu nos=%lu\n",
235                    "             balk",
236                    rcu_preempt_ctrlblk.n_balk_blkd_tasks,
237                    rcu_preempt_ctrlblk.n_balk_exp_gp_tasks,
238                    rcu_preempt_ctrlblk.n_balk_boost_tasks,
239                    rcu_preempt_ctrlblk.n_balk_notyet,
240                    rcu_preempt_ctrlblk.n_balk_nos);
241 #endif /* #ifdef CONFIG_RCU_BOOST */
242 }
243
244 #endif /* #ifdef CONFIG_RCU_TRACE */
245
246 #ifdef CONFIG_RCU_BOOST
247
248 #include "rtmutex_common.h"
249
250 /*
251  * Carry out RCU priority boosting on the task indicated by ->boost_tasks,
252  * and advance ->boost_tasks to the next task in the ->blkd_tasks list.
253  */
254 static int rcu_boost(void)
255 {
256         unsigned long flags;
257         struct rt_mutex mtx;
258         struct task_struct *t;
259         struct list_head *tb;
260
261         if (rcu_preempt_ctrlblk.boost_tasks == NULL &&
262             rcu_preempt_ctrlblk.exp_tasks == NULL)
263                 return 0;  /* Nothing to boost. */
264
265         raw_local_irq_save(flags);
266
267         /*
268          * Recheck with irqs disabled: all tasks in need of boosting
269          * might exit their RCU read-side critical sections on their own
270          * if we are preempted just before disabling irqs.
271          */
272         if (rcu_preempt_ctrlblk.boost_tasks == NULL &&
273             rcu_preempt_ctrlblk.exp_tasks == NULL) {
274                 raw_local_irq_restore(flags);
275                 return 0;
276         }
277
278         /*
279          * Preferentially boost tasks blocking expedited grace periods.
280          * This cannot starve the normal grace periods because a second
281          * expedited grace period must boost all blocked tasks, including
282          * those blocking the pre-existing normal grace period.
283          */
284         if (rcu_preempt_ctrlblk.exp_tasks != NULL) {
285                 tb = rcu_preempt_ctrlblk.exp_tasks;
286                 RCU_TRACE(rcu_preempt_ctrlblk.n_exp_boosts++);
287         } else {
288                 tb = rcu_preempt_ctrlblk.boost_tasks;
289                 RCU_TRACE(rcu_preempt_ctrlblk.n_normal_boosts++);
290         }
291         RCU_TRACE(rcu_preempt_ctrlblk.n_tasks_boosted++);
292
293         /*
294          * We boost task t by manufacturing an rt_mutex that appears to
295          * be held by task t.  We leave a pointer to that rt_mutex where
296          * task t can find it, and task t will release the mutex when it
297          * exits its outermost RCU read-side critical section.  Then
298          * simply acquiring this artificial rt_mutex will boost task
299          * t's priority.  (Thanks to tglx for suggesting this approach!)
300          */
301         t = container_of(tb, struct task_struct, rcu_node_entry);
302         rt_mutex_init_proxy_locked(&mtx, t);
303         t->rcu_boost_mutex = &mtx;
304         t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BOOSTED;
305         raw_local_irq_restore(flags);
306         rt_mutex_lock(&mtx);
307         rt_mutex_unlock(&mtx);  /* Keep lockdep happy. */
308
309         return rcu_preempt_ctrlblk.boost_tasks != NULL ||
310                rcu_preempt_ctrlblk.exp_tasks != NULL;
311 }
312
313 /*
314  * Check to see if it is now time to start boosting RCU readers blocking
315  * the current grace period, and, if so, tell the rcu_kthread_task to
316  * start boosting them.  If there is an expedited boost in progress,
317  * we wait for it to complete.
318  *
319  * If there are no blocked readers blocking the current grace period,
320  * return 0 to let the caller know, otherwise return 1.  Note that this
321  * return value is independent of whether or not boosting was done.
322  */
323 static int rcu_initiate_boost(void)
324 {
325         if (!rcu_preempt_blocked_readers_cgp() &&
326             rcu_preempt_ctrlblk.exp_tasks == NULL) {
327                 RCU_TRACE(rcu_preempt_ctrlblk.n_balk_exp_gp_tasks++);
328                 return 0;
329         }
330         if (rcu_preempt_ctrlblk.exp_tasks != NULL ||
331             (rcu_preempt_ctrlblk.gp_tasks != NULL &&
332              rcu_preempt_ctrlblk.boost_tasks == NULL &&
333              ULONG_CMP_GE(jiffies, rcu_preempt_ctrlblk.boost_time))) {
334                 if (rcu_preempt_ctrlblk.exp_tasks == NULL)
335                         rcu_preempt_ctrlblk.boost_tasks =
336                                 rcu_preempt_ctrlblk.gp_tasks;
337                 invoke_rcu_kthread();
338         } else
339                 RCU_TRACE(rcu_initiate_boost_trace());
340         return 1;
341 }
342
343 #define RCU_BOOST_DELAY_JIFFIES DIV_ROUND_UP(CONFIG_RCU_BOOST_DELAY * HZ, 1000)
344
345 /*
346  * Do priority-boost accounting for the start of a new grace period.
347  */
348 static void rcu_preempt_boost_start_gp(void)
349 {
350         rcu_preempt_ctrlblk.boost_time = jiffies + RCU_BOOST_DELAY_JIFFIES;
351 }
352
353 #else /* #ifdef CONFIG_RCU_BOOST */
354
355 /*
356  * If there is no RCU priority boosting, we don't boost.
357  */
358 static int rcu_boost(void)
359 {
360         return 0;
361 }
362
363 /*
364  * If there is no RCU priority boosting, we don't initiate boosting,
365  * but we do indicate whether there are blocked readers blocking the
366  * current grace period.
367  */
368 static int rcu_initiate_boost(void)
369 {
370         return rcu_preempt_blocked_readers_cgp();
371 }
372
373 /*
374  * If there is no RCU priority boosting, nothing to do at grace-period start.
375  */
376 static void rcu_preempt_boost_start_gp(void)
377 {
378 }
379
380 #endif /* else #ifdef CONFIG_RCU_BOOST */
381
382 /*
383  * Record a preemptible-RCU quiescent state for the specified CPU.  Note
384  * that this just means that the task currently running on the CPU is
385  * in a quiescent state.  There might be any number of tasks blocked
386  * while in an RCU read-side critical section.
387  *
388  * Unlike the other rcu_*_qs() functions, callers to this function
389  * must disable irqs in order to protect the assignment to
390  * ->rcu_read_unlock_special.
391  *
392  * Because this is a single-CPU implementation, the only way a grace
393  * period can end is if the CPU is in a quiescent state.  The reason is
394  * that a blocked preemptible-RCU reader can exit its critical section
395  * only if the CPU is running it at the time.  Therefore, when the
396  * last task blocking the current grace period exits its RCU read-side
397  * critical section, neither the CPU nor blocked tasks will be stopping
398  * the current grace period.  (In contrast, SMP implementations
399  * might have CPUs running in RCU read-side critical sections that
400  * block later grace periods -- but this is not possible given only
401  * one CPU.)
402  */
403 static void rcu_preempt_cpu_qs(void)
404 {
405         /* Record both CPU and task as having responded to current GP. */
406         rcu_preempt_ctrlblk.gpcpu = rcu_preempt_ctrlblk.gpnum;
407         current->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
408
409         /* If there is no GP then there is nothing more to do.  */
410         if (!rcu_preempt_gp_in_progress())
411                 return;
412         /*
413          * Check up on boosting.  If there are readers blocking the
414          * current grace period, leave.
415          */
416         if (rcu_initiate_boost())
417                 return;
418
419         /* Advance callbacks. */
420         rcu_preempt_ctrlblk.completed = rcu_preempt_ctrlblk.gpnum;
421         rcu_preempt_ctrlblk.rcb.donetail = rcu_preempt_ctrlblk.rcb.curtail;
422         rcu_preempt_ctrlblk.rcb.curtail = rcu_preempt_ctrlblk.nexttail;
423
424         /* If there are no blocked readers, next GP is done instantly. */
425         if (!rcu_preempt_blocked_readers_any())
426                 rcu_preempt_ctrlblk.rcb.donetail = rcu_preempt_ctrlblk.nexttail;
427
428         /* If there are done callbacks, cause them to be invoked. */
429         if (*rcu_preempt_ctrlblk.rcb.donetail != NULL)
430                 invoke_rcu_kthread();
431 }
432
433 /*
434  * Start a new RCU grace period if warranted.  Hard irqs must be disabled.
435  */
436 static void rcu_preempt_start_gp(void)
437 {
438         if (!rcu_preempt_gp_in_progress() && rcu_preempt_needs_another_gp()) {
439
440                 /* Official start of GP. */
441                 rcu_preempt_ctrlblk.gpnum++;
442                 RCU_TRACE(rcu_preempt_ctrlblk.n_grace_periods++);
443
444                 /* Any blocked RCU readers block new GP. */
445                 if (rcu_preempt_blocked_readers_any())
446                         rcu_preempt_ctrlblk.gp_tasks =
447                                 rcu_preempt_ctrlblk.blkd_tasks.next;
448
449                 /* Set up for RCU priority boosting. */
450                 rcu_preempt_boost_start_gp();
451
452                 /* If there is no running reader, CPU is done with GP. */
453                 if (!rcu_preempt_running_reader())
454                         rcu_preempt_cpu_qs();
455         }
456 }
457
458 /*
459  * We have entered the scheduler, and the current task might soon be
460  * context-switched away from.  If this task is in an RCU read-side
461  * critical section, we will no longer be able to rely on the CPU to
462  * record that fact, so we enqueue the task on the blkd_tasks list.
463  * If the task started after the current grace period began, as recorded
464  * by ->gpcpu, we enqueue at the beginning of the list.  Otherwise
465  * before the element referenced by ->gp_tasks (or at the tail if
466  * ->gp_tasks is NULL) and point ->gp_tasks at the newly added element.
467  * The task will dequeue itself when it exits the outermost enclosing
468  * RCU read-side critical section.  Therefore, the current grace period
469  * cannot be permitted to complete until the ->gp_tasks pointer becomes
470  * NULL.
471  *
472  * Caller must disable preemption.
473  */
474 void rcu_preempt_note_context_switch(void)
475 {
476         struct task_struct *t = current;
477         unsigned long flags;
478
479         local_irq_save(flags); /* must exclude scheduler_tick(). */
480         if (rcu_preempt_running_reader() &&
481             (t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {
482
483                 /* Possibly blocking in an RCU read-side critical section. */
484                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
485
486                 /*
487                  * If this CPU has already checked in, then this task
488                  * will hold up the next grace period rather than the
489                  * current grace period.  Queue the task accordingly.
490                  * If the task is queued for the current grace period
491                  * (i.e., this CPU has not yet passed through a quiescent
492                  * state for the current grace period), then as long
493                  * as that task remains queued, the current grace period
494                  * cannot end.
495                  */
496                 list_add(&t->rcu_node_entry, &rcu_preempt_ctrlblk.blkd_tasks);
497                 if (rcu_cpu_blocking_cur_gp())
498                         rcu_preempt_ctrlblk.gp_tasks = &t->rcu_node_entry;
499         }
500
501         /*
502          * Either we were not in an RCU read-side critical section to
503          * begin with, or we have now recorded that critical section
504          * globally.  Either way, we can now note a quiescent state
505          * for this CPU.  Again, if we were in an RCU read-side critical
506          * section, and if that critical section was blocking the current
507          * grace period, then the fact that the task has been enqueued
508          * means that current grace period continues to be blocked.
509          */
510         rcu_preempt_cpu_qs();
511         local_irq_restore(flags);
512 }
513
514 /*
515  * Tiny-preemptible RCU implementation for rcu_read_lock().
516  * Just increment ->rcu_read_lock_nesting, shared state will be updated
517  * if we block.
518  */
519 void __rcu_read_lock(void)
520 {
521         current->rcu_read_lock_nesting++;
522         barrier();  /* needed if we ever invoke rcu_read_lock in rcutiny.c */
523 }
524 EXPORT_SYMBOL_GPL(__rcu_read_lock);
525
526 /*
527  * Handle special cases during rcu_read_unlock(), such as needing to
528  * notify RCU core processing or task having blocked during the RCU
529  * read-side critical section.
530  */
531 static void rcu_read_unlock_special(struct task_struct *t)
532 {
533         int empty;
534         int empty_exp;
535         unsigned long flags;
536         struct list_head *np;
537         int special;
538
539         /*
540          * NMI handlers cannot block and cannot safely manipulate state.
541          * They therefore cannot possibly be special, so just leave.
542          */
543         if (in_nmi())
544                 return;
545
546         local_irq_save(flags);
547
548         /*
549          * If RCU core is waiting for this CPU to exit critical section,
550          * let it know that we have done so.
551          */
552         special = t->rcu_read_unlock_special;
553         if (special & RCU_READ_UNLOCK_NEED_QS)
554                 rcu_preempt_cpu_qs();
555
556         /* Hardware IRQ handlers cannot block. */
557         if (in_irq()) {
558                 local_irq_restore(flags);
559                 return;
560         }
561
562         /* Clean up if blocked during RCU read-side critical section. */
563         if (special & RCU_READ_UNLOCK_BLOCKED) {
564                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
565
566                 /*
567                  * Remove this task from the ->blkd_tasks list and adjust
568                  * any pointers that might have been referencing it.
569                  */
570                 empty = !rcu_preempt_blocked_readers_cgp();
571                 empty_exp = rcu_preempt_ctrlblk.exp_tasks == NULL;
572                 np = rcu_next_node_entry(t);
573                 list_del_init(&t->rcu_node_entry);
574                 if (&t->rcu_node_entry == rcu_preempt_ctrlblk.gp_tasks)
575                         rcu_preempt_ctrlblk.gp_tasks = np;
576                 if (&t->rcu_node_entry == rcu_preempt_ctrlblk.exp_tasks)
577                         rcu_preempt_ctrlblk.exp_tasks = np;
578 #ifdef CONFIG_RCU_BOOST
579                 if (&t->rcu_node_entry == rcu_preempt_ctrlblk.boost_tasks)
580                         rcu_preempt_ctrlblk.boost_tasks = np;
581 #endif /* #ifdef CONFIG_RCU_BOOST */
582
583                 /*
584                  * If this was the last task on the current list, and if
585                  * we aren't waiting on the CPU, report the quiescent state
586                  * and start a new grace period if needed.
587                  */
588                 if (!empty && !rcu_preempt_blocked_readers_cgp()) {
589                         rcu_preempt_cpu_qs();
590                         rcu_preempt_start_gp();
591                 }
592
593                 /*
594                  * If this was the last task on the expedited lists,
595                  * then we need wake up the waiting task.
596                  */
597                 if (!empty_exp && rcu_preempt_ctrlblk.exp_tasks == NULL)
598                         rcu_report_exp_done();
599         }
600 #ifdef CONFIG_RCU_BOOST
601         /* Unboost self if was boosted. */
602         if (special & RCU_READ_UNLOCK_BOOSTED) {
603                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BOOSTED;
604                 rt_mutex_unlock(t->rcu_boost_mutex);
605                 t->rcu_boost_mutex = NULL;
606         }
607 #endif /* #ifdef CONFIG_RCU_BOOST */
608         local_irq_restore(flags);
609 }
610
611 /*
612  * Tiny-preemptible RCU implementation for rcu_read_unlock().
613  * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
614  * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then
615  * invoke rcu_read_unlock_special() to clean up after a context switch
616  * in an RCU read-side critical section and other special cases.
617  */
618 void __rcu_read_unlock(void)
619 {
620         struct task_struct *t = current;
621
622         barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
623         --t->rcu_read_lock_nesting;
624         barrier();  /* decrement before load of ->rcu_read_unlock_special */
625         if (t->rcu_read_lock_nesting == 0 &&
626             unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))
627                 rcu_read_unlock_special(t);
628 #ifdef CONFIG_PROVE_LOCKING
629         WARN_ON_ONCE(t->rcu_read_lock_nesting < 0);
630 #endif /* #ifdef CONFIG_PROVE_LOCKING */
631 }
632 EXPORT_SYMBOL_GPL(__rcu_read_unlock);
633
634 /*
635  * Check for a quiescent state from the current CPU.  When a task blocks,
636  * the task is recorded in the rcu_preempt_ctrlblk structure, which is
637  * checked elsewhere.  This is called from the scheduling-clock interrupt.
638  *
639  * Caller must disable hard irqs.
640  */
641 static void rcu_preempt_check_callbacks(void)
642 {
643         struct task_struct *t = current;
644
645         if (rcu_preempt_gp_in_progress() &&
646             (!rcu_preempt_running_reader() ||
647              !rcu_cpu_blocking_cur_gp()))
648                 rcu_preempt_cpu_qs();
649         if (&rcu_preempt_ctrlblk.rcb.rcucblist !=
650             rcu_preempt_ctrlblk.rcb.donetail)
651                 invoke_rcu_kthread();
652         if (rcu_preempt_gp_in_progress() &&
653             rcu_cpu_blocking_cur_gp() &&
654             rcu_preempt_running_reader())
655                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;
656 }
657
658 /*
659  * TINY_PREEMPT_RCU has an extra callback-list tail pointer to
660  * update, so this is invoked from rcu_process_callbacks() to
661  * handle that case.  Of course, it is invoked for all flavors of
662  * RCU, but RCU callbacks can appear only on one of the lists, and
663  * neither ->nexttail nor ->donetail can possibly be NULL, so there
664  * is no need for an explicit check.
665  */
666 static void rcu_preempt_remove_callbacks(struct rcu_ctrlblk *rcp)
667 {
668         if (rcu_preempt_ctrlblk.nexttail == rcp->donetail)
669                 rcu_preempt_ctrlblk.nexttail = &rcp->rcucblist;
670 }
671
672 /*
673  * Process callbacks for preemptible RCU.
674  */
675 static void rcu_preempt_process_callbacks(void)
676 {
677         rcu_process_callbacks(&rcu_preempt_ctrlblk.rcb);
678 }
679
680 /*
681  * Queue a preemptible -RCU callback for invocation after a grace period.
682  */
683 void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
684 {
685         unsigned long flags;
686
687         debug_rcu_head_queue(head);
688         head->func = func;
689         head->next = NULL;
690
691         local_irq_save(flags);
692         *rcu_preempt_ctrlblk.nexttail = head;
693         rcu_preempt_ctrlblk.nexttail = &head->next;
694         RCU_TRACE(rcu_preempt_ctrlblk.rcb.qlen++);
695         rcu_preempt_start_gp();  /* checks to see if GP needed. */
696         local_irq_restore(flags);
697 }
698 EXPORT_SYMBOL_GPL(call_rcu);
699
700 void rcu_barrier(void)
701 {
702         struct rcu_synchronize rcu;
703
704         init_rcu_head_on_stack(&rcu.head);
705         init_completion(&rcu.completion);
706         /* Will wake me after RCU finished. */
707         call_rcu(&rcu.head, wakeme_after_rcu);
708         /* Wait for it. */
709         wait_for_completion(&rcu.completion);
710         destroy_rcu_head_on_stack(&rcu.head);
711 }
712 EXPORT_SYMBOL_GPL(rcu_barrier);
713
714 /*
715  * synchronize_rcu - wait until a grace period has elapsed.
716  *
717  * Control will return to the caller some time after a full grace
718  * period has elapsed, in other words after all currently executing RCU
719  * read-side critical sections have completed.  RCU read-side critical
720  * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
721  * and may be nested.
722  */
723 void synchronize_rcu(void)
724 {
725 #ifdef CONFIG_DEBUG_LOCK_ALLOC
726         if (!rcu_scheduler_active)
727                 return;
728 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
729
730         WARN_ON_ONCE(rcu_preempt_running_reader());
731         if (!rcu_preempt_blocked_readers_any())
732                 return;
733
734         /* Once we get past the fastpath checks, same code as rcu_barrier(). */
735         rcu_barrier();
736 }
737 EXPORT_SYMBOL_GPL(synchronize_rcu);
738
739 static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);
740 static unsigned long sync_rcu_preempt_exp_count;
741 static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);
742
743 /*
744  * Return non-zero if there are any tasks in RCU read-side critical
745  * sections blocking the current preemptible-RCU expedited grace period.
746  * If there is no preemptible-RCU expedited grace period currently in
747  * progress, returns zero unconditionally.
748  */
749 static int rcu_preempted_readers_exp(void)
750 {
751         return rcu_preempt_ctrlblk.exp_tasks != NULL;
752 }
753
754 /*
755  * Report the exit from RCU read-side critical section for the last task
756  * that queued itself during or before the current expedited preemptible-RCU
757  * grace period.
758  */
759 static void rcu_report_exp_done(void)
760 {
761         wake_up(&sync_rcu_preempt_exp_wq);
762 }
763
764 /*
765  * Wait for an rcu-preempt grace period, but expedite it.  The basic idea
766  * is to rely in the fact that there is but one CPU, and that it is
767  * illegal for a task to invoke synchronize_rcu_expedited() while in a
768  * preemptible-RCU read-side critical section.  Therefore, any such
769  * critical sections must correspond to blocked tasks, which must therefore
770  * be on the ->blkd_tasks list.  So just record the current head of the
771  * list in the ->exp_tasks pointer, and wait for all tasks including and
772  * after the task pointed to by ->exp_tasks to drain.
773  */
774 void synchronize_rcu_expedited(void)
775 {
776         unsigned long flags;
777         struct rcu_preempt_ctrlblk *rpcp = &rcu_preempt_ctrlblk;
778         unsigned long snap;
779
780         barrier(); /* ensure prior action seen before grace period. */
781
782         WARN_ON_ONCE(rcu_preempt_running_reader());
783
784         /*
785          * Acquire lock so that there is only one preemptible RCU grace
786          * period in flight.  Of course, if someone does the expedited
787          * grace period for us while we are acquiring the lock, just leave.
788          */
789         snap = sync_rcu_preempt_exp_count + 1;
790         mutex_lock(&sync_rcu_preempt_exp_mutex);
791         if (ULONG_CMP_LT(snap, sync_rcu_preempt_exp_count))
792                 goto unlock_mb_ret; /* Others did our work for us. */
793
794         local_irq_save(flags);
795
796         /*
797          * All RCU readers have to already be on blkd_tasks because
798          * we cannot legally be executing in an RCU read-side critical
799          * section.
800          */
801
802         /* Snapshot current head of ->blkd_tasks list. */
803         rpcp->exp_tasks = rpcp->blkd_tasks.next;
804         if (rpcp->exp_tasks == &rpcp->blkd_tasks)
805                 rpcp->exp_tasks = NULL;
806
807         /* Wait for tail of ->blkd_tasks list to drain. */
808         if (!rcu_preempted_readers_exp())
809                 local_irq_restore(flags);
810         else {
811                 rcu_initiate_boost();
812                 local_irq_restore(flags);
813                 wait_event(sync_rcu_preempt_exp_wq,
814                            !rcu_preempted_readers_exp());
815         }
816
817         /* Clean up and exit. */
818         barrier(); /* ensure expedited GP seen before counter increment. */
819         sync_rcu_preempt_exp_count++;
820 unlock_mb_ret:
821         mutex_unlock(&sync_rcu_preempt_exp_mutex);
822         barrier(); /* ensure subsequent action seen after grace period. */
823 }
824 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
825
826 /*
827  * Does preemptible RCU need the CPU to stay out of dynticks mode?
828  */
829 int rcu_preempt_needs_cpu(void)
830 {
831         if (!rcu_preempt_running_reader())
832                 rcu_preempt_cpu_qs();
833         return rcu_preempt_ctrlblk.rcb.rcucblist != NULL;
834 }
835
836 /*
837  * Check for a task exiting while in a preemptible -RCU read-side
838  * critical section, clean up if so.  No need to issue warnings,
839  * as debug_check_no_locks_held() already does this if lockdep
840  * is enabled.
841  */
842 void exit_rcu(void)
843 {
844         struct task_struct *t = current;
845
846         if (t->rcu_read_lock_nesting == 0)
847                 return;
848         t->rcu_read_lock_nesting = 1;
849         __rcu_read_unlock();
850 }
851
852 #else /* #ifdef CONFIG_TINY_PREEMPT_RCU */
853
854 #ifdef CONFIG_RCU_TRACE
855
856 /*
857  * Because preemptible RCU does not exist, it is not necessary to
858  * dump out its statistics.
859  */
860 static void show_tiny_preempt_stats(struct seq_file *m)
861 {
862 }
863
864 #endif /* #ifdef CONFIG_RCU_TRACE */
865
866 /*
867  * Because preemptible RCU does not exist, it is never necessary to
868  * boost preempted RCU readers.
869  */
870 static int rcu_boost(void)
871 {
872         return 0;
873 }
874
875 /*
876  * Because preemptible RCU does not exist, it never has any callbacks
877  * to check.
878  */
879 static void rcu_preempt_check_callbacks(void)
880 {
881 }
882
883 /*
884  * Because preemptible RCU does not exist, it never has any callbacks
885  * to remove.
886  */
887 static void rcu_preempt_remove_callbacks(struct rcu_ctrlblk *rcp)
888 {
889 }
890
891 /*
892  * Because preemptible RCU does not exist, it never has any callbacks
893  * to process.
894  */
895 static void rcu_preempt_process_callbacks(void)
896 {
897 }
898
899 #endif /* #else #ifdef CONFIG_TINY_PREEMPT_RCU */
900
901 #ifdef CONFIG_DEBUG_LOCK_ALLOC
902 #include <linux/kernel_stat.h>
903
904 /*
905  * During boot, we forgive RCU lockdep issues.  After this function is
906  * invoked, we start taking RCU lockdep issues seriously.
907  */
908 void __init rcu_scheduler_starting(void)
909 {
910         WARN_ON(nr_context_switches() > 0);
911         rcu_scheduler_active = 1;
912 }
913
914 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
915
916 #ifdef CONFIG_RCU_BOOST
917 #define RCU_BOOST_PRIO CONFIG_RCU_BOOST_PRIO
918 #else /* #ifdef CONFIG_RCU_BOOST */
919 #define RCU_BOOST_PRIO 1
920 #endif /* #else #ifdef CONFIG_RCU_BOOST */
921
922 #ifdef CONFIG_RCU_TRACE
923
924 #ifdef CONFIG_RCU_BOOST
925
926 static void rcu_initiate_boost_trace(void)
927 {
928         if (list_empty(&rcu_preempt_ctrlblk.blkd_tasks))
929                 rcu_preempt_ctrlblk.n_balk_blkd_tasks++;
930         else if (rcu_preempt_ctrlblk.gp_tasks == NULL &&
931                  rcu_preempt_ctrlblk.exp_tasks == NULL)
932                 rcu_preempt_ctrlblk.n_balk_exp_gp_tasks++;
933         else if (rcu_preempt_ctrlblk.boost_tasks != NULL)
934                 rcu_preempt_ctrlblk.n_balk_boost_tasks++;
935         else if (!ULONG_CMP_GE(jiffies, rcu_preempt_ctrlblk.boost_time))
936                 rcu_preempt_ctrlblk.n_balk_notyet++;
937         else
938                 rcu_preempt_ctrlblk.n_balk_nos++;
939 }
940
941 #endif /* #ifdef CONFIG_RCU_BOOST */
942
943 static void rcu_trace_sub_qlen(struct rcu_ctrlblk *rcp, int n)
944 {
945         unsigned long flags;
946
947         raw_local_irq_save(flags);
948         rcp->qlen -= n;
949         raw_local_irq_restore(flags);
950 }
951
952 /*
953  * Dump statistics for TINY_RCU, such as they are.
954  */
955 static int show_tiny_stats(struct seq_file *m, void *unused)
956 {
957         show_tiny_preempt_stats(m);
958         seq_printf(m, "rcu_sched: qlen: %ld\n", rcu_sched_ctrlblk.qlen);
959         seq_printf(m, "rcu_bh: qlen: %ld\n", rcu_bh_ctrlblk.qlen);
960         return 0;
961 }
962
963 static int show_tiny_stats_open(struct inode *inode, struct file *file)
964 {
965         return single_open(file, show_tiny_stats, NULL);
966 }
967
968 static const struct file_operations show_tiny_stats_fops = {
969         .owner = THIS_MODULE,
970         .open = show_tiny_stats_open,
971         .read = seq_read,
972         .llseek = seq_lseek,
973         .release = single_release,
974 };
975
976 static struct dentry *rcudir;
977
978 static int __init rcutiny_trace_init(void)
979 {
980         struct dentry *retval;
981
982         rcudir = debugfs_create_dir("rcu", NULL);
983         if (!rcudir)
984                 goto free_out;
985         retval = debugfs_create_file("rcudata", 0444, rcudir,
986                                      NULL, &show_tiny_stats_fops);
987         if (!retval)
988                 goto free_out;
989         return 0;
990 free_out:
991         debugfs_remove_recursive(rcudir);
992         return 1;
993 }
994
995 static void __exit rcutiny_trace_cleanup(void)
996 {
997         debugfs_remove_recursive(rcudir);
998 }
999
1000 module_init(rcutiny_trace_init);
1001 module_exit(rcutiny_trace_cleanup);
1002
1003 MODULE_AUTHOR("Paul E. McKenney");
1004 MODULE_DESCRIPTION("Read-Copy Update tracing for tiny implementation");
1005 MODULE_LICENSE("GPL");
1006
1007 #endif /* #ifdef CONFIG_RCU_TRACE */