kernel/rcu/tasks.h

   1 /* SPDX-License-Identifier: GPL-2.0+ */
   2 /*
   3  * Task-based RCU implementations.
   4  *
   5  * Copyright (C) 2020 Paul E. McKenney
   6  */
   7
   8 #ifdef CONFIG_TASKS_RCU_GENERIC
   9 #include "rcu_segcblist.h"
  10
  11 ////////////////////////////////////////////////////////////////////////
  12 //
  13 // Generic data structures.
  14
  15 struct rcu_tasks;
  16 typedef void (*rcu_tasks_gp_func_t)(struct rcu_tasks *rtp);
  17 typedef void (*pregp_func_t)(struct list_head *hop);
  18 typedef void (*pertask_func_t)(struct task_struct *t, struct list_head *hop);
  19 typedef void (*postscan_func_t)(struct list_head *hop);
  20 typedef void (*holdouts_func_t)(struct list_head *hop, bool ndrpt, bool *frptp);
  21 typedef void (*postgp_func_t)(struct rcu_tasks *rtp);
  22
  23 /**
  24  * struct rcu_tasks_percpu - Per-CPU component of definition for a Tasks-RCU-like mechanism.
  25  * @cblist: Callback list.
  26  * @lock: Lock protecting per-CPU callback list.
  27  * @rtp_jiffies: Jiffies counter value for statistics.
  28  * @rtp_n_lock_retries: Rough lock-contention statistic.
  29  * @rtp_work: Work queue for invoking callbacks.
  30  * @rtp_irq_work: IRQ work queue for deferred wakeups.
  31  * @barrier_q_head: RCU callback for barrier operation.
  32  * @rtp_blkd_tasks: List of tasks blocked as readers.
  33  * @cpu: CPU number corresponding to this entry.
  34  * @rtpp: Pointer to the rcu_tasks structure.
  35  */
  36 struct rcu_tasks_percpu {
  37         struct rcu_segcblist cblist;
  38         raw_spinlock_t __private lock;
  39         unsigned long rtp_jiffies;
  40         unsigned long rtp_n_lock_retries;
  41         struct work_struct rtp_work;
  42         struct irq_work rtp_irq_work;
  43         struct rcu_head barrier_q_head;
  44         struct list_head rtp_blkd_tasks;
  45         int cpu;
  46         struct rcu_tasks *rtpp;
  47 };
  48
  49 /**
  50  * struct rcu_tasks - Definition for a Tasks-RCU-like mechanism.
  51  * @cbs_wait: RCU wait allowing a new callback to get kthread's attention.
  52  * @cbs_gbl_lock: Lock protecting callback list.
  53  * @tasks_gp_mutex: Mutex protecting grace period, needed during mid-boot dead zone.
  54  * @kthread_ptr: This flavor's grace-period/callback-invocation kthread.
  55  * @gp_func: This flavor's grace-period-wait function.
  56  * @gp_state: Grace period's most recent state transition (debugging).
  57  * @gp_sleep: Per-grace-period sleep to prevent CPU-bound looping.
  58  * @init_fract: Initial backoff sleep interval.
  59  * @gp_jiffies: Time of last @gp_state transition.
  60  * @gp_start: Most recent grace-period start in jiffies.
  61  * @tasks_gp_seq: Number of grace periods completed since boot.
  62  * @n_ipis: Number of IPIs sent to encourage grace periods to end.
  63  * @n_ipis_fails: Number of IPI-send failures.
  64  * @pregp_func: This flavor's pre-grace-period function (optional).
  65  * @pertask_func: This flavor's per-task scan function (optional).
  66  * @postscan_func: This flavor's post-task scan function (optional).
  67  * @holdouts_func: This flavor's holdout-list scan function (optional).
  68  * @postgp_func: This flavor's post-grace-period function (optional).
  69  * @call_func: This flavor's call_rcu()-equivalent function.
  70  * @rtpcpu: This flavor's rcu_tasks_percpu structure.
  71  * @percpu_enqueue_shift: Shift down CPU ID this much when enqueuing callbacks.
  72  * @percpu_enqueue_lim: Number of per-CPU callback queues in use for enqueuing.
  73  * @percpu_dequeue_lim: Number of per-CPU callback queues in use for dequeuing.
  74  * @percpu_dequeue_gpseq: RCU grace-period number to propagate enqueue limit to dequeuers.
  75  * @barrier_q_mutex: Serialize barrier operations.
  76  * @barrier_q_count: Number of queues being waited on.
  77  * @barrier_q_completion: Barrier wait/wakeup mechanism.
  78  * @barrier_q_seq: Sequence number for barrier operations.
  79  * @name: This flavor's textual name.
  80  * @kname: This flavor's kthread name.
  81  */
  82 struct rcu_tasks {
  83         struct rcuwait cbs_wait;
  84         raw_spinlock_t cbs_gbl_lock;
  85         struct mutex tasks_gp_mutex;
  86         int gp_state;
  87         int gp_sleep;
  88         int init_fract;
  89         unsigned long gp_jiffies;
  90         unsigned long gp_start;
  91         unsigned long tasks_gp_seq;
  92         unsigned long n_ipis;
  93         unsigned long n_ipis_fails;
  94         struct task_struct *kthread_ptr;
  95         rcu_tasks_gp_func_t gp_func;
  96         pregp_func_t pregp_func;
  97         pertask_func_t pertask_func;
  98         postscan_func_t postscan_func;
  99         holdouts_func_t holdouts_func;
 100         postgp_func_t postgp_func;
 101         call_rcu_func_t call_func;
 102         struct rcu_tasks_percpu __percpu *rtpcpu;
 103         int percpu_enqueue_shift;
 104         int percpu_enqueue_lim;
 105         int percpu_dequeue_lim;
 106         unsigned long percpu_dequeue_gpseq;
 107         struct mutex barrier_q_mutex;
 108         atomic_t barrier_q_count;
 109         struct completion barrier_q_completion;
 110         unsigned long barrier_q_seq;
 111         char *name;
 112         char *kname;
 113 };
 114
 115 static void call_rcu_tasks_iw_wakeup(struct irq_work *iwp);
 116
 117 #define DEFINE_RCU_TASKS(rt_name, gp, call, n)                                          \
 118 static DEFINE_PER_CPU(struct rcu_tasks_percpu, rt_name ## __percpu) = {                 \
 119         .lock = __RAW_SPIN_LOCK_UNLOCKED(rt_name ## __percpu.cbs_pcpu_lock),            \
 120         .rtp_irq_work = IRQ_WORK_INIT_HARD(call_rcu_tasks_iw_wakeup),                   \
 121 };                                                                                      \
 122 static struct rcu_tasks rt_name =                                                       \
 123 {                                                                                       \
 124         .cbs_wait = __RCUWAIT_INITIALIZER(rt_name.wait),                                \
 125         .cbs_gbl_lock = __RAW_SPIN_LOCK_UNLOCKED(rt_name.cbs_gbl_lock),                 \
 126         .tasks_gp_mutex = __MUTEX_INITIALIZER(rt_name.tasks_gp_mutex),                  \
 127         .gp_func = gp,                                                                  \
 128         .call_func = call,                                                              \
 129         .rtpcpu = &rt_name ## __percpu,                                                 \
 130         .name = n,                                                                      \
 131         .percpu_enqueue_shift = order_base_2(CONFIG_NR_CPUS),                           \
 132         .percpu_enqueue_lim = 1,                                                        \
 133         .percpu_dequeue_lim = 1,                                                        \
 134         .barrier_q_mutex = __MUTEX_INITIALIZER(rt_name.barrier_q_mutex),                \
 135         .barrier_q_seq = (0UL - 50UL) << RCU_SEQ_CTR_SHIFT,                             \
 136         .kname = #rt_name,                                                              \
 137 }
 138
 139 #ifdef CONFIG_TASKS_RCU
 140 /* Track exiting tasks in order to allow them to be waited for. */
 141 DEFINE_STATIC_SRCU(tasks_rcu_exit_srcu);
 142 #endif
 143
 144 #ifdef CONFIG_TASKS_RCU
 145 /* Report delay in synchronize_srcu() completion in rcu_tasks_postscan(). */
 146 static void tasks_rcu_exit_srcu_stall(struct timer_list *unused);
 147 static DEFINE_TIMER(tasks_rcu_exit_srcu_stall_timer, tasks_rcu_exit_srcu_stall);
 148 #endif
 149
 150 /* Avoid IPIing CPUs early in the grace period. */
 151 #define RCU_TASK_IPI_DELAY (IS_ENABLED(CONFIG_TASKS_TRACE_RCU_READ_MB) ? HZ / 2 : 0)
 152 static int rcu_task_ipi_delay __read_mostly = RCU_TASK_IPI_DELAY;
 153 module_param(rcu_task_ipi_delay, int, 0644);
 154
 155 /* Control stall timeouts.  Disable with <= 0, otherwise jiffies till stall. */
 156 #define RCU_TASK_BOOT_STALL_TIMEOUT (HZ * 30)
 157 #define RCU_TASK_STALL_TIMEOUT (HZ * 60 * 10)
 158 static int rcu_task_stall_timeout __read_mostly = RCU_TASK_STALL_TIMEOUT;
 159 module_param(rcu_task_stall_timeout, int, 0644);
 160 #define RCU_TASK_STALL_INFO (HZ * 10)
 161 static int rcu_task_stall_info __read_mostly = RCU_TASK_STALL_INFO;
 162 module_param(rcu_task_stall_info, int, 0644);
 163 static int rcu_task_stall_info_mult __read_mostly = 3;
 164 module_param(rcu_task_stall_info_mult, int, 0444);
 165
 166 static int rcu_task_enqueue_lim __read_mostly = -1;
 167 module_param(rcu_task_enqueue_lim, int, 0444);
 168
 169 static bool rcu_task_cb_adjust;
 170 static int rcu_task_contend_lim __read_mostly = 100;
 171 module_param(rcu_task_contend_lim, int, 0444);
 172 static int rcu_task_collapse_lim __read_mostly = 10;
 173 module_param(rcu_task_collapse_lim, int, 0444);
 174
 175 /* RCU tasks grace-period state for debugging. */
 176 #define RTGS_INIT                0
 177 #define RTGS_WAIT_WAIT_CBS       1
 178 #define RTGS_WAIT_GP             2
 179 #define RTGS_PRE_WAIT_GP         3
 180 #define RTGS_SCAN_TASKLIST       4
 181 #define RTGS_POST_SCAN_TASKLIST  5
 182 #define RTGS_WAIT_SCAN_HOLDOUTS  6
 183 #define RTGS_SCAN_HOLDOUTS       7
 184 #define RTGS_POST_GP             8
 185 #define RTGS_WAIT_READERS        9
 186 #define RTGS_INVOKE_CBS         10
 187 #define RTGS_WAIT_CBS           11
 188 #ifndef CONFIG_TINY_RCU
 189 static const char * const rcu_tasks_gp_state_names[] = {
 190         "RTGS_INIT",
 191         "RTGS_WAIT_WAIT_CBS",
 192         "RTGS_WAIT_GP",
 193         "RTGS_PRE_WAIT_GP",
 194         "RTGS_SCAN_TASKLIST",
 195         "RTGS_POST_SCAN_TASKLIST",
 196         "RTGS_WAIT_SCAN_HOLDOUTS",
 197         "RTGS_SCAN_HOLDOUTS",
 198         "RTGS_POST_GP",
 199         "RTGS_WAIT_READERS",
 200         "RTGS_INVOKE_CBS",
 201         "RTGS_WAIT_CBS",
 202 };
 203 #endif /* #ifndef CONFIG_TINY_RCU */
 204
 205 ////////////////////////////////////////////////////////////////////////
 206 //
 207 // Generic code.
 208
 209 static void rcu_tasks_invoke_cbs_wq(struct work_struct *wp);
 210
 211 /* Record grace-period phase and time. */
 212 static void set_tasks_gp_state(struct rcu_tasks *rtp, int newstate)
 213 {
 214         rtp->gp_state = newstate;
 215         rtp->gp_jiffies = jiffies;
 216 }
 217
 218 #ifndef CONFIG_TINY_RCU
 219 /* Return state name. */
 220 static const char *tasks_gp_state_getname(struct rcu_tasks *rtp)
 221 {
 222         int i = data_race(rtp->gp_state); // Let KCSAN detect update races
 223         int j = READ_ONCE(i); // Prevent the compiler from reading twice
 224
 225         if (j >= ARRAY_SIZE(rcu_tasks_gp_state_names))
 226                 return "???";
 227         return rcu_tasks_gp_state_names[j];
 228 }
 229 #endif /* #ifndef CONFIG_TINY_RCU */
 230
 231 // Initialize per-CPU callback lists for the specified flavor of
 232 // Tasks RCU.
 233 static void cblist_init_generic(struct rcu_tasks *rtp)
 234 {
 235         int cpu;
 236         unsigned long flags;
 237         int lim;
 238         int shift;
 239
 240         raw_spin_lock_irqsave(&rtp->cbs_gbl_lock, flags);
 241         if (rcu_task_enqueue_lim < 0) {
 242                 rcu_task_enqueue_lim = 1;
 243                 rcu_task_cb_adjust = true;
 244         } else if (rcu_task_enqueue_lim == 0) {
 245                 rcu_task_enqueue_lim = 1;
 246         }
 247         lim = rcu_task_enqueue_lim;
 248
 249         if (lim > nr_cpu_ids)
 250                 lim = nr_cpu_ids;
 251         shift = ilog2(nr_cpu_ids / lim);
 252         if (((nr_cpu_ids - 1) >> shift) >= lim)
 253                 shift++;
 254         WRITE_ONCE(rtp->percpu_enqueue_shift, shift);
 255         WRITE_ONCE(rtp->percpu_dequeue_lim, lim);
 256         smp_store_release(&rtp->percpu_enqueue_lim, lim);
 257         for_each_possible_cpu(cpu) {
 258                 struct rcu_tasks_percpu *rtpcp = per_cpu_ptr(rtp->rtpcpu, cpu);
 259
 260                 WARN_ON_ONCE(!rtpcp);
 261                 if (cpu)
 262                         raw_spin_lock_init(&ACCESS_PRIVATE(rtpcp, lock));
 263                 raw_spin_lock_rcu_node(rtpcp); // irqs already disabled.
 264                 if (rcu_segcblist_empty(&rtpcp->cblist))
 265                         rcu_segcblist_init(&rtpcp->cblist);
 266                 INIT_WORK(&rtpcp->rtp_work, rcu_tasks_invoke_cbs_wq);
 267                 rtpcp->cpu = cpu;
 268                 rtpcp->rtpp = rtp;
 269                 if (!rtpcp->rtp_blkd_tasks.next)
 270                         INIT_LIST_HEAD(&rtpcp->rtp_blkd_tasks);
 271                 raw_spin_unlock_rcu_node(rtpcp); // irqs remain disabled.
 272         }
 273         raw_spin_unlock_irqrestore(&rtp->cbs_gbl_lock, flags);
 274
 275         pr_info("%s: Setting shift to %d and lim to %d rcu_task_cb_adjust=%d.\n", rtp->name,
 276                         data_race(rtp->percpu_enqueue_shift), data_race(rtp->percpu_enqueue_lim), rcu_task_cb_adjust);
 277 }
 278
 279 // IRQ-work handler that does deferred wakeup for call_rcu_tasks_generic().
 280 static void call_rcu_tasks_iw_wakeup(struct irq_work *iwp)
 281 {
 282         struct rcu_tasks *rtp;
 283         struct rcu_tasks_percpu *rtpcp = container_of(iwp, struct rcu_tasks_percpu, rtp_irq_work);
 284
 285         rtp = rtpcp->rtpp;
 286         rcuwait_wake_up(&rtp->cbs_wait);
 287 }
 288
 289 // Enqueue a callback for the specified flavor of Tasks RCU.
 290 static void call_rcu_tasks_generic(struct rcu_head *rhp, rcu_callback_t func,
 291                                    struct rcu_tasks *rtp)
 292 {
 293         int chosen_cpu;
 294         unsigned long flags;
 295         int ideal_cpu;
 296         unsigned long j;
 297         bool needadjust = false;
 298         bool needwake;
 299         struct rcu_tasks_percpu *rtpcp;
 300
 301         rhp->next = NULL;
 302         rhp->func = func;
 303         local_irq_save(flags);
 304         rcu_read_lock();
 305         ideal_cpu = smp_processor_id() >> READ_ONCE(rtp->percpu_enqueue_shift);
 306         chosen_cpu = cpumask_next(ideal_cpu - 1, cpu_possible_mask);
 307         rtpcp = per_cpu_ptr(rtp->rtpcpu, chosen_cpu);
 308         if (!raw_spin_trylock_rcu_node(rtpcp)) { // irqs already disabled.
 309                 raw_spin_lock_rcu_node(rtpcp); // irqs already disabled.
 310                 j = jiffies;
 311                 if (rtpcp->rtp_jiffies != j) {
 312                         rtpcp->rtp_jiffies = j;
 313                         rtpcp->rtp_n_lock_retries = 0;
 314                 }
 315                 if (rcu_task_cb_adjust && ++rtpcp->rtp_n_lock_retries > rcu_task_contend_lim &&
 316                     READ_ONCE(rtp->percpu_enqueue_lim) != nr_cpu_ids)
 317                         needadjust = true;  // Defer adjustment to avoid deadlock.
 318         }
 319         if (!rcu_segcblist_is_enabled(&rtpcp->cblist)) {
 320                 raw_spin_unlock_rcu_node(rtpcp); // irqs remain disabled.
 321                 cblist_init_generic(rtp);
 322                 raw_spin_lock_rcu_node(rtpcp); // irqs already disabled.
 323         }
 324         needwake = rcu_segcblist_empty(&rtpcp->cblist);
 325         rcu_segcblist_enqueue(&rtpcp->cblist, rhp);
 326         raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
 327         if (unlikely(needadjust)) {
 328                 raw_spin_lock_irqsave(&rtp->cbs_gbl_lock, flags);
 329                 if (rtp->percpu_enqueue_lim != nr_cpu_ids) {
 330                         WRITE_ONCE(rtp->percpu_enqueue_shift, 0);
 331                         WRITE_ONCE(rtp->percpu_dequeue_lim, nr_cpu_ids);
 332                         smp_store_release(&rtp->percpu_enqueue_lim, nr_cpu_ids);
 333                         pr_info("Switching %s to per-CPU callback queuing.\n", rtp->name);
 334                 }
 335                 raw_spin_unlock_irqrestore(&rtp->cbs_gbl_lock, flags);
 336         }
 337         rcu_read_unlock();
 338         /* We can't create the thread unless interrupts are enabled. */
 339         if (needwake && READ_ONCE(rtp->kthread_ptr))
 340                 irq_work_queue(&rtpcp->rtp_irq_work);
 341 }
 342
 343 // RCU callback function for rcu_barrier_tasks_generic().
 344 static void rcu_barrier_tasks_generic_cb(struct rcu_head *rhp)
 345 {
 346         struct rcu_tasks *rtp;
 347         struct rcu_tasks_percpu *rtpcp;
 348
 349         rtpcp = container_of(rhp, struct rcu_tasks_percpu, barrier_q_head);
 350         rtp = rtpcp->rtpp;
 351         if (atomic_dec_and_test(&rtp->barrier_q_count))
 352                 complete(&rtp->barrier_q_completion);
 353 }
 354
 355 // Wait for all in-flight callbacks for the specified RCU Tasks flavor.
 356 // Operates in a manner similar to rcu_barrier().
 357 static void rcu_barrier_tasks_generic(struct rcu_tasks *rtp)
 358 {
 359         int cpu;
 360         unsigned long flags;
 361         struct rcu_tasks_percpu *rtpcp;
 362         unsigned long s = rcu_seq_snap(&rtp->barrier_q_seq);
 363
 364         mutex_lock(&rtp->barrier_q_mutex);
 365         if (rcu_seq_done(&rtp->barrier_q_seq, s)) {
 366                 smp_mb();
 367                 mutex_unlock(&rtp->barrier_q_mutex);
 368                 return;
 369         }
 370         rcu_seq_start(&rtp->barrier_q_seq);
 371         init_completion(&rtp->barrier_q_completion);
 372         atomic_set(&rtp->barrier_q_count, 2);
 373         for_each_possible_cpu(cpu) {
 374                 if (cpu >= smp_load_acquire(&rtp->percpu_dequeue_lim))
 375                         break;
 376                 rtpcp = per_cpu_ptr(rtp->rtpcpu, cpu);
 377                 rtpcp->barrier_q_head.func = rcu_barrier_tasks_generic_cb;
 378                 raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
 379                 if (rcu_segcblist_entrain(&rtpcp->cblist, &rtpcp->barrier_q_head))
 380                         atomic_inc(&rtp->barrier_q_count);
 381                 raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
 382         }
 383         if (atomic_sub_and_test(2, &rtp->barrier_q_count))
 384                 complete(&rtp->barrier_q_completion);
 385         wait_for_completion(&rtp->barrier_q_completion);
 386         rcu_seq_end(&rtp->barrier_q_seq);
 387         mutex_unlock(&rtp->barrier_q_mutex);
 388 }
 389
 390 // Advance callbacks and indicate whether either a grace period or
 391 // callback invocation is needed.
 392 static int rcu_tasks_need_gpcb(struct rcu_tasks *rtp)
 393 {
 394         int cpu;
 395         unsigned long flags;
 396         bool gpdone = poll_state_synchronize_rcu(rtp->percpu_dequeue_gpseq);
 397         long n;
 398         long ncbs = 0;
 399         long ncbsnz = 0;
 400         int needgpcb = 0;
 401
 402         for (cpu = 0; cpu < smp_load_acquire(&rtp->percpu_dequeue_lim); cpu++) {
 403                 struct rcu_tasks_percpu *rtpcp = per_cpu_ptr(rtp->rtpcpu, cpu);
 404
 405                 /* Advance and accelerate any new callbacks. */
 406                 if (!rcu_segcblist_n_cbs(&rtpcp->cblist))
 407                         continue;
 408                 raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
 409                 // Should we shrink down to a single callback queue?
 410                 n = rcu_segcblist_n_cbs(&rtpcp->cblist);
 411                 if (n) {
 412                         ncbs += n;
 413                         if (cpu > 0)
 414                                 ncbsnz += n;
 415                 }
 416                 rcu_segcblist_advance(&rtpcp->cblist, rcu_seq_current(&rtp->tasks_gp_seq));
 417                 (void)rcu_segcblist_accelerate(&rtpcp->cblist, rcu_seq_snap(&rtp->tasks_gp_seq));
 418                 if (rcu_segcblist_pend_cbs(&rtpcp->cblist))
 419                         needgpcb |= 0x3;
 420                 if (!rcu_segcblist_empty(&rtpcp->cblist))
 421                         needgpcb |= 0x1;
 422                 raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
 423         }
 424
 425         // Shrink down to a single callback queue if appropriate.
 426         // This is done in two stages: (1) If there are no more than
 427         // rcu_task_collapse_lim callbacks on CPU 0 and none on any other
 428         // CPU, limit enqueueing to CPU 0.  (2) After an RCU grace period,
 429         // if there has not been an increase in callbacks, limit dequeuing
 430         // to CPU 0.  Note the matching RCU read-side critical section in
 431         // call_rcu_tasks_generic().
 432         if (rcu_task_cb_adjust && ncbs <= rcu_task_collapse_lim) {
 433                 raw_spin_lock_irqsave(&rtp->cbs_gbl_lock, flags);
 434                 if (rtp->percpu_enqueue_lim > 1) {
 435                         WRITE_ONCE(rtp->percpu_enqueue_shift, order_base_2(nr_cpu_ids));
 436                         smp_store_release(&rtp->percpu_enqueue_lim, 1);
 437                         rtp->percpu_dequeue_gpseq = get_state_synchronize_rcu();
 438                         gpdone = false;
 439                         pr_info("Starting switch %s to CPU-0 callback queuing.\n", rtp->name);
 440                 }
 441                 raw_spin_unlock_irqrestore(&rtp->cbs_gbl_lock, flags);
 442         }
 443         if (rcu_task_cb_adjust && !ncbsnz && gpdone) {
 444                 raw_spin_lock_irqsave(&rtp->cbs_gbl_lock, flags);
 445                 if (rtp->percpu_enqueue_lim < rtp->percpu_dequeue_lim) {
 446                         WRITE_ONCE(rtp->percpu_dequeue_lim, 1);
 447                         pr_info("Completing switch %s to CPU-0 callback queuing.\n", rtp->name);
 448                 }
 449                 if (rtp->percpu_dequeue_lim == 1) {
 450                         for (cpu = rtp->percpu_dequeue_lim; cpu < nr_cpu_ids; cpu++) {
 451                                 struct rcu_tasks_percpu *rtpcp = per_cpu_ptr(rtp->rtpcpu, cpu);
 452
 453                                 WARN_ON_ONCE(rcu_segcblist_n_cbs(&rtpcp->cblist));
 454                         }
 455                 }
 456                 raw_spin_unlock_irqrestore(&rtp->cbs_gbl_lock, flags);
 457         }
 458
 459         return needgpcb;
 460 }
 461
 462 // Advance callbacks and invoke any that are ready.
 463 static void rcu_tasks_invoke_cbs(struct rcu_tasks *rtp, struct rcu_tasks_percpu *rtpcp)
 464 {
 465         int cpu;
 466         int cpunext;
 467         int cpuwq;
 468         unsigned long flags;
 469         int len;
 470         struct rcu_head *rhp;
 471         struct rcu_cblist rcl = RCU_CBLIST_INITIALIZER(rcl);
 472         struct rcu_tasks_percpu *rtpcp_next;
 473
 474         cpu = rtpcp->cpu;
 475         cpunext = cpu * 2 + 1;
 476         if (cpunext < smp_load_acquire(&rtp->percpu_dequeue_lim)) {
 477                 rtpcp_next = per_cpu_ptr(rtp->rtpcpu, cpunext);
 478                 cpuwq = rcu_cpu_beenfullyonline(cpunext) ? cpunext : WORK_CPU_UNBOUND;
 479                 queue_work_on(cpuwq, system_wq, &rtpcp_next->rtp_work);
 480                 cpunext++;
 481                 if (cpunext < smp_load_acquire(&rtp->percpu_dequeue_lim)) {
 482                         rtpcp_next = per_cpu_ptr(rtp->rtpcpu, cpunext);
 483                         cpuwq = rcu_cpu_beenfullyonline(cpunext) ? cpunext : WORK_CPU_UNBOUND;
 484                         queue_work_on(cpuwq, system_wq, &rtpcp_next->rtp_work);
 485                 }
 486         }
 487
 488         if (rcu_segcblist_empty(&rtpcp->cblist) || !cpu_possible(cpu))
 489                 return;
 490         raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
 491         rcu_segcblist_advance(&rtpcp->cblist, rcu_seq_current(&rtp->tasks_gp_seq));
 492         rcu_segcblist_extract_done_cbs(&rtpcp->cblist, &rcl);
 493         raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
 494         len = rcl.len;
 495         for (rhp = rcu_cblist_dequeue(&rcl); rhp; rhp = rcu_cblist_dequeue(&rcl)) {
 496                 local_bh_disable();
 497                 rhp->func(rhp);
 498                 local_bh_enable();
 499                 cond_resched();
 500         }
 501         raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
 502         rcu_segcblist_add_len(&rtpcp->cblist, -len);
 503         (void)rcu_segcblist_accelerate(&rtpcp->cblist, rcu_seq_snap(&rtp->tasks_gp_seq));
 504         raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
 505 }
 506
 507 // Workqueue flood to advance callbacks and invoke any that are ready.
 508 static void rcu_tasks_invoke_cbs_wq(struct work_struct *wp)
 509 {
 510         struct rcu_tasks *rtp;
 511         struct rcu_tasks_percpu *rtpcp = container_of(wp, struct rcu_tasks_percpu, rtp_work);
 512
 513         rtp = rtpcp->rtpp;
 514         rcu_tasks_invoke_cbs(rtp, rtpcp);
 515 }
 516
 517 // Wait for one grace period.
 518 static void rcu_tasks_one_gp(struct rcu_tasks *rtp, bool midboot)
 519 {
 520         int needgpcb;
 521
 522         mutex_lock(&rtp->tasks_gp_mutex);
 523
 524         // If there were none, wait a bit and start over.
 525         if (unlikely(midboot)) {
 526                 needgpcb = 0x2;
 527         } else {
 528                 set_tasks_gp_state(rtp, RTGS_WAIT_CBS);
 529                 rcuwait_wait_event(&rtp->cbs_wait,
 530                                    (needgpcb = rcu_tasks_need_gpcb(rtp)),
 531                                    TASK_IDLE);
 532         }
 533
 534         if (needgpcb & 0x2) {
 535                 // Wait for one grace period.
 536                 set_tasks_gp_state(rtp, RTGS_WAIT_GP);
 537                 rtp->gp_start = jiffies;
 538                 rcu_seq_start(&rtp->tasks_gp_seq);
 539                 rtp->gp_func(rtp);
 540                 rcu_seq_end(&rtp->tasks_gp_seq);
 541         }
 542
 543         // Invoke callbacks.
 544         set_tasks_gp_state(rtp, RTGS_INVOKE_CBS);
 545         rcu_tasks_invoke_cbs(rtp, per_cpu_ptr(rtp->rtpcpu, 0));
 546         mutex_unlock(&rtp->tasks_gp_mutex);
 547 }
 548
 549 // RCU-tasks kthread that detects grace periods and invokes callbacks.
 550 static int __noreturn rcu_tasks_kthread(void *arg)
 551 {
 552         struct rcu_tasks *rtp = arg;
 553
 554         /* Run on housekeeping CPUs by default.  Sysadm can move if desired. */
 555         housekeeping_affine(current, HK_TYPE_RCU);
 556         WRITE_ONCE(rtp->kthread_ptr, current); // Let GPs start!
 557
 558         /*
 559          * Each pass through the following loop makes one check for
 560          * newly arrived callbacks, and, if there are some, waits for
 561          * one RCU-tasks grace period and then invokes the callbacks.
 562          * This loop is terminated by the system going down.  ;-)
 563          */
 564         for (;;) {
 565                 // Wait for one grace period and invoke any callbacks
 566                 // that are ready.
 567                 rcu_tasks_one_gp(rtp, false);
 568
 569                 // Paranoid sleep to keep this from entering a tight loop.
 570                 schedule_timeout_idle(rtp->gp_sleep);
 571         }
 572 }
 573
 574 // Wait for a grace period for the specified flavor of Tasks RCU.
 575 static void synchronize_rcu_tasks_generic(struct rcu_tasks *rtp)
 576 {
 577         /* Complain if the scheduler has not started.  */
 578         if (WARN_ONCE(rcu_scheduler_active == RCU_SCHEDULER_INACTIVE,
 579                          "synchronize_%s() called too soon", rtp->name))
 580                 return;
 581
 582         // If the grace-period kthread is running, use it.
 583         if (READ_ONCE(rtp->kthread_ptr)) {
 584                 wait_rcu_gp(rtp->call_func);
 585                 return;
 586         }
 587         rcu_tasks_one_gp(rtp, true);
 588 }
 589
 590 /* Spawn RCU-tasks grace-period kthread. */
 591 static void __init rcu_spawn_tasks_kthread_generic(struct rcu_tasks *rtp)
 592 {
 593         struct task_struct *t;
 594
 595         t = kthread_run(rcu_tasks_kthread, rtp, "%s_kthread", rtp->kname);
 596         if (WARN_ONCE(IS_ERR(t), "%s: Could not start %s grace-period kthread, OOM is now expected behavior\n", __func__, rtp->name))
 597                 return;
 598         smp_mb(); /* Ensure others see full kthread. */
 599 }
 600
 601 #ifndef CONFIG_TINY_RCU
 602
 603 /*
 604  * Print any non-default Tasks RCU settings.
 605  */
 606 static void __init rcu_tasks_bootup_oddness(void)
 607 {
 608 #if defined(CONFIG_TASKS_RCU) || defined(CONFIG_TASKS_TRACE_RCU)
 609         int rtsimc;
 610
 611         if (rcu_task_stall_timeout != RCU_TASK_STALL_TIMEOUT)
 612                 pr_info("\tTasks-RCU CPU stall warnings timeout set to %d (rcu_task_stall_timeout).\n", rcu_task_stall_timeout);
 613         rtsimc = clamp(rcu_task_stall_info_mult, 1, 10);
 614         if (rtsimc != rcu_task_stall_info_mult) {
 615                 pr_info("\tTasks-RCU CPU stall info multiplier clamped to %d (rcu_task_stall_info_mult).\n", rtsimc);
 616                 rcu_task_stall_info_mult = rtsimc;
 617         }
 618 #endif /* #ifdef CONFIG_TASKS_RCU */
 619 #ifdef CONFIG_TASKS_RCU
 620         pr_info("\tTrampoline variant of Tasks RCU enabled.\n");
 621 #endif /* #ifdef CONFIG_TASKS_RCU */
 622 #ifdef CONFIG_TASKS_RUDE_RCU
 623         pr_info("\tRude variant of Tasks RCU enabled.\n");
 624 #endif /* #ifdef CONFIG_TASKS_RUDE_RCU */
 625 #ifdef CONFIG_TASKS_TRACE_RCU
 626         pr_info("\tTracing variant of Tasks RCU enabled.\n");
 627 #endif /* #ifdef CONFIG_TASKS_TRACE_RCU */
 628 }
 629
 630 #endif /* #ifndef CONFIG_TINY_RCU */
 631
 632 #ifndef CONFIG_TINY_RCU
 633 /* Dump out rcutorture-relevant state common to all RCU-tasks flavors. */
 634 static void show_rcu_tasks_generic_gp_kthread(struct rcu_tasks *rtp, char *s)
 635 {
 636         int cpu;
 637         bool havecbs = false;
 638
 639         for_each_possible_cpu(cpu) {
 640                 struct rcu_tasks_percpu *rtpcp = per_cpu_ptr(rtp->rtpcpu, cpu);
 641
 642                 if (!data_race(rcu_segcblist_empty(&rtpcp->cblist))) {
 643                         havecbs = true;
 644                         break;
 645                 }
 646         }
 647         pr_info("%s: %s(%d) since %lu g:%lu i:%lu/%lu %c%c %s\n",
 648                 rtp->kname,
 649                 tasks_gp_state_getname(rtp), data_race(rtp->gp_state),
 650                 jiffies - data_race(rtp->gp_jiffies),
 651                 data_race(rcu_seq_current(&rtp->tasks_gp_seq)),
 652                 data_race(rtp->n_ipis_fails), data_race(rtp->n_ipis),
 653                 ".k"[!!data_race(rtp->kthread_ptr)],
 654                 ".C"[havecbs],
 655                 s);
 656 }
 657 #endif // #ifndef CONFIG_TINY_RCU
 658
 659 static void exit_tasks_rcu_finish_trace(struct task_struct *t);
 660
 661 #if defined(CONFIG_TASKS_RCU) || defined(CONFIG_TASKS_TRACE_RCU)
 662
 663 ////////////////////////////////////////////////////////////////////////
 664 //
 665 // Shared code between task-list-scanning variants of Tasks RCU.
 666
 667 /* Wait for one RCU-tasks grace period. */
 668 static void rcu_tasks_wait_gp(struct rcu_tasks *rtp)
 669 {
 670         struct task_struct *g;
 671         int fract;
 672         LIST_HEAD(holdouts);
 673         unsigned long j;
 674         unsigned long lastinfo;
 675         unsigned long lastreport;
 676         bool reported = false;
 677         int rtsi;
 678         struct task_struct *t;
 679
 680         set_tasks_gp_state(rtp, RTGS_PRE_WAIT_GP);
 681         rtp->pregp_func(&holdouts);
 682
 683         /*
 684          * There were callbacks, so we need to wait for an RCU-tasks
 685          * grace period.  Start off by scanning the task list for tasks
 686          * that are not already voluntarily blocked.  Mark these tasks
 687          * and make a list of them in holdouts.
 688          */
 689         set_tasks_gp_state(rtp, RTGS_SCAN_TASKLIST);
 690         if (rtp->pertask_func) {
 691                 rcu_read_lock();
 692                 for_each_process_thread(g, t)
 693                         rtp->pertask_func(t, &holdouts);
 694                 rcu_read_unlock();
 695         }
 696
 697         set_tasks_gp_state(rtp, RTGS_POST_SCAN_TASKLIST);
 698         rtp->postscan_func(&holdouts);
 699
 700         /*
 701          * Each pass through the following loop scans the list of holdout
 702          * tasks, removing any that are no longer holdouts.  When the list
 703          * is empty, we are done.
 704          */
 705         lastreport = jiffies;
 706         lastinfo = lastreport;
 707         rtsi = READ_ONCE(rcu_task_stall_info);
 708
 709         // Start off with initial wait and slowly back off to 1 HZ wait.
 710         fract = rtp->init_fract;
 711
 712         while (!list_empty(&holdouts)) {
 713                 ktime_t exp;
 714                 bool firstreport;
 715                 bool needreport;
 716                 int rtst;
 717
 718                 // Slowly back off waiting for holdouts
 719                 set_tasks_gp_state(rtp, RTGS_WAIT_SCAN_HOLDOUTS);
 720                 if (!IS_ENABLED(CONFIG_PREEMPT_RT)) {
 721                         schedule_timeout_idle(fract);
 722                 } else {
 723                         exp = jiffies_to_nsecs(fract);
 724                         __set_current_state(TASK_IDLE);
 725                         schedule_hrtimeout_range(&exp, jiffies_to_nsecs(HZ / 2), HRTIMER_MODE_REL_HARD);
 726                 }
 727
 728                 if (fract < HZ)
 729                         fract++;
 730
 731                 rtst = READ_ONCE(rcu_task_stall_timeout);
 732                 needreport = rtst > 0 && time_after(jiffies, lastreport + rtst);
 733                 if (needreport) {
 734                         lastreport = jiffies;
 735                         reported = true;
 736                 }
 737                 firstreport = true;
 738                 WARN_ON(signal_pending(current));
 739                 set_tasks_gp_state(rtp, RTGS_SCAN_HOLDOUTS);
 740                 rtp->holdouts_func(&holdouts, needreport, &firstreport);
 741
 742                 // Print pre-stall informational messages if needed.
 743                 j = jiffies;
 744                 if (rtsi > 0 && !reported && time_after(j, lastinfo + rtsi)) {
 745                         lastinfo = j;
 746                         rtsi = rtsi * rcu_task_stall_info_mult;
 747                         pr_info("%s: %s grace period number %lu (since boot) is %lu jiffies old.\n",
 748                                 __func__, rtp->kname, rtp->tasks_gp_seq, j - rtp->gp_start);
 749                 }
 750         }
 751
 752         set_tasks_gp_state(rtp, RTGS_POST_GP);
 753         rtp->postgp_func(rtp);
 754 }
 755
 756 #endif /* #if defined(CONFIG_TASKS_RCU) || defined(CONFIG_TASKS_TRACE_RCU) */
 757
 758 #ifdef CONFIG_TASKS_RCU
 759
 760 ////////////////////////////////////////////////////////////////////////
 761 //
 762 // Simple variant of RCU whose quiescent states are voluntary context
 763 // switch, cond_resched_tasks_rcu_qs(), user-space execution, and idle.
 764 // As such, grace periods can take one good long time.  There are no
 765 // read-side primitives similar to rcu_read_lock() and rcu_read_unlock()
 766 // because this implementation is intended to get the system into a safe
 767 // state for some of the manipulations involved in tracing and the like.
 768 // Finally, this implementation does not support high call_rcu_tasks()
 769 // rates from multiple CPUs.  If this is required, per-CPU callback lists
 770 // will be needed.
 771 //
 772 // The implementation uses rcu_tasks_wait_gp(), which relies on function
 773 // pointers in the rcu_tasks structure.  The rcu_spawn_tasks_kthread()
 774 // function sets these function pointers up so that rcu_tasks_wait_gp()
 775 // invokes these functions in this order:
 776 //
 777 // rcu_tasks_pregp_step():
 778 //      Invokes synchronize_rcu() in order to wait for all in-flight
 779 //      t->on_rq and t->nvcsw transitions to complete.  This works because
 780 //      all such transitions are carried out with interrupts disabled.
 781 // rcu_tasks_pertask(), invoked on every non-idle task:
 782 //      For every runnable non-idle task other than the current one, use
 783 //      get_task_struct() to pin down that task, snapshot that task's
 784 //      number of voluntary context switches, and add that task to the
 785 //      holdout list.
 786 // rcu_tasks_postscan():
 787 //      Invoke synchronize_srcu() to ensure that all tasks that were
 788 //      in the process of exiting (and which thus might not know to
 789 //      synchronize with this RCU Tasks grace period) have completed
 790 //      exiting.
 791 // check_all_holdout_tasks(), repeatedly until holdout list is empty:
 792 //      Scans the holdout list, attempting to identify a quiescent state
 793 //      for each task on the list.  If there is a quiescent state, the
 794 //      corresponding task is removed from the holdout list.
 795 // rcu_tasks_postgp():
 796 //      Invokes synchronize_rcu() in order to ensure that all prior
 797 //      t->on_rq and t->nvcsw transitions are seen by all CPUs and tasks
 798 //      to have happened before the end of this RCU Tasks grace period.
 799 //      Again, this works because all such transitions are carried out
 800 //      with interrupts disabled.
 801 //
 802 // For each exiting task, the exit_tasks_rcu_start() and
 803 // exit_tasks_rcu_finish() functions begin and end, respectively, the SRCU
 804 // read-side critical sections waited for by rcu_tasks_postscan().
 805 //
 806 // Pre-grace-period update-side code is ordered before the grace
 807 // via the raw_spin_lock.*rcu_node().  Pre-grace-period read-side code
 808 // is ordered before the grace period via synchronize_rcu() call in
 809 // rcu_tasks_pregp_step() and by the scheduler's locks and interrupt
 810 // disabling.
 811
 812 /* Pre-grace-period preparation. */
 813 static void rcu_tasks_pregp_step(struct list_head *hop)
 814 {
 815         /*
 816          * Wait for all pre-existing t->on_rq and t->nvcsw transitions
 817          * to complete.  Invoking synchronize_rcu() suffices because all
 818          * these transitions occur with interrupts disabled.  Without this
 819          * synchronize_rcu(), a read-side critical section that started
 820          * before the grace period might be incorrectly seen as having
 821          * started after the grace period.
 822          *
 823          * This synchronize_rcu() also dispenses with the need for a
 824          * memory barrier on the first store to t->rcu_tasks_holdout,
 825          * as it forces the store to happen after the beginning of the
 826          * grace period.
 827          */
 828         synchronize_rcu();
 829 }
 830
 831 /* Per-task initial processing. */
 832 static void rcu_tasks_pertask(struct task_struct *t, struct list_head *hop)
 833 {
 834         if (t != current && READ_ONCE(t->on_rq) && !is_idle_task(t)) {
 835                 get_task_struct(t);
 836                 t->rcu_tasks_nvcsw = READ_ONCE(t->nvcsw);
 837                 WRITE_ONCE(t->rcu_tasks_holdout, true);
 838                 list_add(&t->rcu_tasks_holdout_list, hop);
 839         }
 840 }
 841
 842 /* Processing between scanning taskslist and draining the holdout list. */
 843 static void rcu_tasks_postscan(struct list_head *hop)
 844 {
 845         int rtsi = READ_ONCE(rcu_task_stall_info);
 846
 847         if (!IS_ENABLED(CONFIG_TINY_RCU)) {
 848                 tasks_rcu_exit_srcu_stall_timer.expires = jiffies + rtsi;
 849                 add_timer(&tasks_rcu_exit_srcu_stall_timer);
 850         }
 851
 852         /*
 853          * Exiting tasks may escape the tasklist scan. Those are vulnerable
 854          * until their final schedule() with TASK_DEAD state. To cope with
 855          * this, divide the fragile exit path part in two intersecting
 856          * read side critical sections:
 857          *
 858          * 1) An _SRCU_ read side starting before calling exit_notify(),
 859          *    which may remove the task from the tasklist, and ending after
 860          *    the final preempt_disable() call in do_exit().
 861          *
 862          * 2) An _RCU_ read side starting with the final preempt_disable()
 863          *    call in do_exit() and ending with the final call to schedule()
 864          *    with TASK_DEAD state.
 865          *
 866          * This handles the part 1). And postgp will handle part 2) with a
 867          * call to synchronize_rcu().
 868          */
 869         synchronize_srcu(&tasks_rcu_exit_srcu);
 870
 871         if (!IS_ENABLED(CONFIG_TINY_RCU))
 872                 del_timer_sync(&tasks_rcu_exit_srcu_stall_timer);
 873 }
 874
 875 /* See if tasks are still holding out, complain if so. */
 876 static void check_holdout_task(struct task_struct *t,
 877                                bool needreport, bool *firstreport)
 878 {
 879         int cpu;
 880
 881         if (!READ_ONCE(t->rcu_tasks_holdout) ||
 882             t->rcu_tasks_nvcsw != READ_ONCE(t->nvcsw) ||
 883             !READ_ONCE(t->on_rq) ||
 884             (IS_ENABLED(CONFIG_NO_HZ_FULL) &&
 885              !is_idle_task(t) && t->rcu_tasks_idle_cpu >= 0)) {
 886                 WRITE_ONCE(t->rcu_tasks_holdout, false);
 887                 list_del_init(&t->rcu_tasks_holdout_list);
 888                 put_task_struct(t);
 889                 return;
 890         }
 891         rcu_request_urgent_qs_task(t);
 892         if (!needreport)
 893                 return;
 894         if (*firstreport) {
 895                 pr_err("INFO: rcu_tasks detected stalls on tasks:\n");
 896                 *firstreport = false;
 897         }
 898         cpu = task_cpu(t);
 899         pr_alert("%p: %c%c nvcsw: %lu/%lu holdout: %d idle_cpu: %d/%d\n",
 900                  t, ".I"[is_idle_task(t)],
 901                  "N."[cpu < 0 || !tick_nohz_full_cpu(cpu)],
 902                  t->rcu_tasks_nvcsw, t->nvcsw, t->rcu_tasks_holdout,
 903                  t->rcu_tasks_idle_cpu, cpu);
 904         sched_show_task(t);
 905 }
 906
 907 /* Scan the holdout lists for tasks no longer holding out. */
 908 static void check_all_holdout_tasks(struct list_head *hop,
 909                                     bool needreport, bool *firstreport)
 910 {
 911         struct task_struct *t, *t1;
 912
 913         list_for_each_entry_safe(t, t1, hop, rcu_tasks_holdout_list) {
 914                 check_holdout_task(t, needreport, firstreport);
 915                 cond_resched();
 916         }
 917 }
 918
 919 /* Finish off the Tasks-RCU grace period. */
 920 static void rcu_tasks_postgp(struct rcu_tasks *rtp)
 921 {
 922         /*
 923          * Because ->on_rq and ->nvcsw are not guaranteed to have a full
 924          * memory barriers prior to them in the schedule() path, memory
 925          * reordering on other CPUs could cause their RCU-tasks read-side
 926          * critical sections to extend past the end of the grace period.
 927          * However, because these ->nvcsw updates are carried out with
 928          * interrupts disabled, we can use synchronize_rcu() to force the
 929          * needed ordering on all such CPUs.
 930          *
 931          * This synchronize_rcu() also confines all ->rcu_tasks_holdout
 932          * accesses to be within the grace period, avoiding the need for
 933          * memory barriers for ->rcu_tasks_holdout accesses.
 934          *
 935          * In addition, this synchronize_rcu() waits for exiting tasks
 936          * to complete their final preempt_disable() region of execution,
 937          * cleaning up after synchronize_srcu(&tasks_rcu_exit_srcu),
 938          * enforcing the whole region before tasklist removal until
 939          * the final schedule() with TASK_DEAD state to be an RCU TASKS
 940          * read side critical section.
 941          */
 942         synchronize_rcu();
 943 }
 944
 945 void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func);
 946 DEFINE_RCU_TASKS(rcu_tasks, rcu_tasks_wait_gp, call_rcu_tasks, "RCU Tasks");
 947
 948 static void tasks_rcu_exit_srcu_stall(struct timer_list *unused)
 949 {
 950 #ifndef CONFIG_TINY_RCU
 951         int rtsi;
 952
 953         rtsi = READ_ONCE(rcu_task_stall_info);
 954         pr_info("%s: %s grace period number %lu (since boot) gp_state: %s is %lu jiffies old.\n",
 955                 __func__, rcu_tasks.kname, rcu_tasks.tasks_gp_seq,
 956                 tasks_gp_state_getname(&rcu_tasks), jiffies - rcu_tasks.gp_jiffies);
 957         pr_info("Please check any exiting tasks stuck between calls to exit_tasks_rcu_start() and exit_tasks_rcu_finish()\n");
 958         tasks_rcu_exit_srcu_stall_timer.expires = jiffies + rtsi;
 959         add_timer(&tasks_rcu_exit_srcu_stall_timer);
 960 #endif // #ifndef CONFIG_TINY_RCU
 961 }
 962
 963 /**
 964  * call_rcu_tasks() - Queue an RCU for invocation task-based grace period
 965  * @rhp: structure to be used for queueing the RCU updates.
 966  * @func: actual callback function to be invoked after the grace period
 967  *
 968  * The callback function will be invoked some time after a full grace
 969  * period elapses, in other words after all currently executing RCU
 970  * read-side critical sections have completed. call_rcu_tasks() assumes
 971  * that the read-side critical sections end at a voluntary context
 972  * switch (not a preemption!), cond_resched_tasks_rcu_qs(), entry into idle,
 973  * or transition to usermode execution.  As such, there are no read-side
 974  * primitives analogous to rcu_read_lock() and rcu_read_unlock() because
 975  * this primitive is intended to determine that all tasks have passed
 976  * through a safe state, not so much for data-structure synchronization.
 977  *
 978  * See the description of call_rcu() for more detailed information on
 979  * memory ordering guarantees.
 980  */
 981 void call_rcu_tasks(struct rcu_head *rhp, rcu_callback_t func)
 982 {
 983         call_rcu_tasks_generic(rhp, func, &rcu_tasks);
 984 }
 985 EXPORT_SYMBOL_GPL(call_rcu_tasks);
 986
 987 /**
 988  * synchronize_rcu_tasks - wait until an rcu-tasks grace period has elapsed.
 989  *
 990  * Control will return to the caller some time after a full rcu-tasks
 991  * grace period has elapsed, in other words after all currently
 992  * executing rcu-tasks read-side critical sections have elapsed.  These
 993  * read-side critical sections are delimited by calls to schedule(),
 994  * cond_resched_tasks_rcu_qs(), idle execution, userspace execution, calls
 995  * to synchronize_rcu_tasks(), and (in theory, anyway) cond_resched().
 996  *
 997  * This is a very specialized primitive, intended only for a few uses in
 998  * tracing and other situations requiring manipulation of function
 999  * preambles and profiling hooks.  The synchronize_rcu_tasks() function
1000  * is not (yet) intended for heavy use from multiple CPUs.
1001  *
1002  * See the description of synchronize_rcu() for more detailed information
1003  * on memory ordering guarantees.
1004  */
1005 void synchronize_rcu_tasks(void)
1006 {
1007         synchronize_rcu_tasks_generic(&rcu_tasks);
1008 }
1009 EXPORT_SYMBOL_GPL(synchronize_rcu_tasks);
1010
1011 /**
1012  * rcu_barrier_tasks - Wait for in-flight call_rcu_tasks() callbacks.
1013  *
1014  * Although the current implementation is guaranteed to wait, it is not
1015  * obligated to, for example, if there are no pending callbacks.
1016  */
1017 void rcu_barrier_tasks(void)
1018 {
1019         rcu_barrier_tasks_generic(&rcu_tasks);
1020 }
1021 EXPORT_SYMBOL_GPL(rcu_barrier_tasks);
1022
1023 static int __init rcu_spawn_tasks_kthread(void)
1024 {
1025         cblist_init_generic(&rcu_tasks);
1026         rcu_tasks.gp_sleep = HZ / 10;
1027         rcu_tasks.init_fract = HZ / 10;
1028         rcu_tasks.pregp_func = rcu_tasks_pregp_step;
1029         rcu_tasks.pertask_func = rcu_tasks_pertask;
1030         rcu_tasks.postscan_func = rcu_tasks_postscan;
1031         rcu_tasks.holdouts_func = check_all_holdout_tasks;
1032         rcu_tasks.postgp_func = rcu_tasks_postgp;
1033         rcu_spawn_tasks_kthread_generic(&rcu_tasks);
1034         return 0;
1035 }
1036
1037 #if !defined(CONFIG_TINY_RCU)
1038 void show_rcu_tasks_classic_gp_kthread(void)
1039 {
1040         show_rcu_tasks_generic_gp_kthread(&rcu_tasks, "");
1041 }
1042 EXPORT_SYMBOL_GPL(show_rcu_tasks_classic_gp_kthread);
1043 #endif // !defined(CONFIG_TINY_RCU)
1044
1045 /*
1046  * Contribute to protect against tasklist scan blind spot while the
1047  * task is exiting and may be removed from the tasklist. See
1048  * corresponding synchronize_srcu() for further details.
1049  */
1050 void exit_tasks_rcu_start(void) __acquires(&tasks_rcu_exit_srcu)
1051 {
1052         current->rcu_tasks_idx = __srcu_read_lock(&tasks_rcu_exit_srcu);
1053 }
1054
1055 /*
1056  * Contribute to protect against tasklist scan blind spot while the
1057  * task is exiting and may be removed from the tasklist. See
1058  * corresponding synchronize_srcu() for further details.
1059  */
1060 void exit_tasks_rcu_stop(void) __releases(&tasks_rcu_exit_srcu)
1061 {
1062         struct task_struct *t = current;
1063
1064         __srcu_read_unlock(&tasks_rcu_exit_srcu, t->rcu_tasks_idx);
1065 }
1066
1067 /*
1068  * Contribute to protect against tasklist scan blind spot while the
1069  * task is exiting and may be removed from the tasklist. See
1070  * corresponding synchronize_srcu() for further details.
1071  */
1072 void exit_tasks_rcu_finish(void)
1073 {
1074         exit_tasks_rcu_stop();
1075         exit_tasks_rcu_finish_trace(current);
1076 }
1077
1078 #else /* #ifdef CONFIG_TASKS_RCU */
1079 void exit_tasks_rcu_start(void) { }
1080 void exit_tasks_rcu_stop(void) { }
1081 void exit_tasks_rcu_finish(void) { exit_tasks_rcu_finish_trace(current); }
1082 #endif /* #else #ifdef CONFIG_TASKS_RCU */
1083
1084 #ifdef CONFIG_TASKS_RUDE_RCU
1085
1086 ////////////////////////////////////////////////////////////////////////
1087 //
1088 // "Rude" variant of Tasks RCU, inspired by Steve Rostedt's trick of
1089 // passing an empty function to schedule_on_each_cpu().  This approach
1090 // provides an asynchronous call_rcu_tasks_rude() API and batching of
1091 // concurrent calls to the synchronous synchronize_rcu_tasks_rude() API.
1092 // This invokes schedule_on_each_cpu() in order to send IPIs far and wide
1093 // and induces otherwise unnecessary context switches on all online CPUs,
1094 // whether idle or not.
1095 //
1096 // Callback handling is provided by the rcu_tasks_kthread() function.
1097 //
1098 // Ordering is provided by the scheduler's context-switch code.
1099
1100 // Empty function to allow workqueues to force a context switch.
1101 static void rcu_tasks_be_rude(struct work_struct *work)
1102 {
1103 }
1104
1105 // Wait for one rude RCU-tasks grace period.
1106 static void rcu_tasks_rude_wait_gp(struct rcu_tasks *rtp)
1107 {
1108         rtp->n_ipis += cpumask_weight(cpu_online_mask);
1109         schedule_on_each_cpu(rcu_tasks_be_rude);
1110 }
1111
1112 void call_rcu_tasks_rude(struct rcu_head *rhp, rcu_callback_t func);
1113 DEFINE_RCU_TASKS(rcu_tasks_rude, rcu_tasks_rude_wait_gp, call_rcu_tasks_rude,
1114                  "RCU Tasks Rude");
1115
1116 /**
1117  * call_rcu_tasks_rude() - Queue a callback rude task-based grace period
1118  * @rhp: structure to be used for queueing the RCU updates.
1119  * @func: actual callback function to be invoked after the grace period
1120  *
1121  * The callback function will be invoked some time after a full grace
1122  * period elapses, in other words after all currently executing RCU
1123  * read-side critical sections have completed. call_rcu_tasks_rude()
1124  * assumes that the read-side critical sections end at context switch,
1125  * cond_resched_tasks_rcu_qs(), or transition to usermode execution (as
1126  * usermode execution is schedulable). As such, there are no read-side
1127  * primitives analogous to rcu_read_lock() and rcu_read_unlock() because
1128  * this primitive is intended to determine that all tasks have passed
1129  * through a safe state, not so much for data-structure synchronization.
1130  *
1131  * See the description of call_rcu() for more detailed information on
1132  * memory ordering guarantees.
1133  */
1134 void call_rcu_tasks_rude(struct rcu_head *rhp, rcu_callback_t func)
1135 {
1136         call_rcu_tasks_generic(rhp, func, &rcu_tasks_rude);
1137 }
1138 EXPORT_SYMBOL_GPL(call_rcu_tasks_rude);
1139
1140 /**
1141  * synchronize_rcu_tasks_rude - wait for a rude rcu-tasks grace period
1142  *
1143  * Control will return to the caller some time after a rude rcu-tasks
1144  * grace period has elapsed, in other words after all currently
1145  * executing rcu-tasks read-side critical sections have elapsed.  These
1146  * read-side critical sections are delimited by calls to schedule(),
1147  * cond_resched_tasks_rcu_qs(), userspace execution (which is a schedulable
1148  * context), and (in theory, anyway) cond_resched().
1149  *
1150  * This is a very specialized primitive, intended only for a few uses in
1151  * tracing and other situations requiring manipulation of function preambles
1152  * and profiling hooks.  The synchronize_rcu_tasks_rude() function is not
1153  * (yet) intended for heavy use from multiple CPUs.
1154  *
1155  * See the description of synchronize_rcu() for more detailed information
1156  * on memory ordering guarantees.
1157  */
1158 void synchronize_rcu_tasks_rude(void)
1159 {
1160         synchronize_rcu_tasks_generic(&rcu_tasks_rude);
1161 }
1162 EXPORT_SYMBOL_GPL(synchronize_rcu_tasks_rude);
1163
1164 /**
1165  * rcu_barrier_tasks_rude - Wait for in-flight call_rcu_tasks_rude() callbacks.
1166  *
1167  * Although the current implementation is guaranteed to wait, it is not
1168  * obligated to, for example, if there are no pending callbacks.
1169  */
1170 void rcu_barrier_tasks_rude(void)
1171 {
1172         rcu_barrier_tasks_generic(&rcu_tasks_rude);
1173 }
1174 EXPORT_SYMBOL_GPL(rcu_barrier_tasks_rude);
1175
1176 static int __init rcu_spawn_tasks_rude_kthread(void)
1177 {
1178         cblist_init_generic(&rcu_tasks_rude);
1179         rcu_tasks_rude.gp_sleep = HZ / 10;
1180         rcu_spawn_tasks_kthread_generic(&rcu_tasks_rude);
1181         return 0;
1182 }
1183
1184 #if !defined(CONFIG_TINY_RCU)
1185 void show_rcu_tasks_rude_gp_kthread(void)
1186 {
1187         show_rcu_tasks_generic_gp_kthread(&rcu_tasks_rude, "");
1188 }
1189 EXPORT_SYMBOL_GPL(show_rcu_tasks_rude_gp_kthread);
1190 #endif // !defined(CONFIG_TINY_RCU)
1191 #endif /* #ifdef CONFIG_TASKS_RUDE_RCU */
1192
1193 ////////////////////////////////////////////////////////////////////////
1194 //
1195 // Tracing variant of Tasks RCU.  This variant is designed to be used
1196 // to protect tracing hooks, including those of BPF.  This variant
1197 // therefore:
1198 //
1199 // 1.   Has explicit read-side markers to allow finite grace periods
1200 //      in the face of in-kernel loops for PREEMPT=n builds.
1201 //
1202 // 2.   Protects code in the idle loop, exception entry/exit, and
1203 //      CPU-hotplug code paths, similar to the capabilities of SRCU.
1204 //
1205 // 3.   Avoids expensive read-side instructions, having overhead similar
1206 //      to that of Preemptible RCU.
1207 //
1208 // There are of course downsides.  For example, the grace-period code
1209 // can send IPIs to CPUs, even when those CPUs are in the idle loop or
1210 // in nohz_full userspace.  If needed, these downsides can be at least
1211 // partially remedied.
1212 //
1213 // Perhaps most important, this variant of RCU does not affect the vanilla
1214 // flavors, rcu_preempt and rcu_sched.  The fact that RCU Tasks Trace
1215 // readers can operate from idle, offline, and exception entry/exit in no
1216 // way allows rcu_preempt and rcu_sched readers to also do so.
1217 //
1218 // The implementation uses rcu_tasks_wait_gp(), which relies on function
1219 // pointers in the rcu_tasks structure.  The rcu_spawn_tasks_trace_kthread()
1220 // function sets these function pointers up so that rcu_tasks_wait_gp()
1221 // invokes these functions in this order:
1222 //
1223 // rcu_tasks_trace_pregp_step():
1224 //      Disables CPU hotplug, adds all currently executing tasks to the
1225 //      holdout list, then checks the state of all tasks that blocked
1226 //      or were preempted within their current RCU Tasks Trace read-side
1227 //      critical section, adding them to the holdout list if appropriate.
1228 //      Finally, this function re-enables CPU hotplug.
1229 // The ->pertask_func() pointer is NULL, so there is no per-task processing.
1230 // rcu_tasks_trace_postscan():
1231 //      Invokes synchronize_rcu() to wait for late-stage exiting tasks
1232 //      to finish exiting.
1233 // check_all_holdout_tasks_trace(), repeatedly until holdout list is empty:
1234 //      Scans the holdout list, attempting to identify a quiescent state
1235 //      for each task on the list.  If there is a quiescent state, the
1236 //      corresponding task is removed from the holdout list.  Once this
1237 //      list is empty, the grace period has completed.
1238 // rcu_tasks_trace_postgp():
1239 //      Provides the needed full memory barrier and does debug checks.
1240 //
1241 // The exit_tasks_rcu_finish_trace() synchronizes with exiting tasks.
1242 //
1243 // Pre-grace-period update-side code is ordered before the grace period
1244 // via the ->cbs_lock and barriers in rcu_tasks_kthread().  Pre-grace-period
1245 // read-side code is ordered before the grace period by atomic operations
1246 // on .b.need_qs flag of each task involved in this process, or by scheduler
1247 // context-switch ordering (for locked-down non-running readers).
1248
1249 // The lockdep state must be outside of #ifdef to be useful.
1250 #ifdef CONFIG_DEBUG_LOCK_ALLOC
1251 static struct lock_class_key rcu_lock_trace_key;
1252 struct lockdep_map rcu_trace_lock_map =
1253         STATIC_LOCKDEP_MAP_INIT("rcu_read_lock_trace", &rcu_lock_trace_key);
1254 EXPORT_SYMBOL_GPL(rcu_trace_lock_map);
1255 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
1256
1257 #ifdef CONFIG_TASKS_TRACE_RCU
1258
1259 // Record outstanding IPIs to each CPU.  No point in sending two...
1260 static DEFINE_PER_CPU(bool, trc_ipi_to_cpu);
1261
1262 // The number of detections of task quiescent state relying on
1263 // heavyweight readers executing explicit memory barriers.
1264 static unsigned long n_heavy_reader_attempts;
1265 static unsigned long n_heavy_reader_updates;
1266 static unsigned long n_heavy_reader_ofl_updates;
1267 static unsigned long n_trc_holdouts;
1268
1269 void call_rcu_tasks_trace(struct rcu_head *rhp, rcu_callback_t func);
1270 DEFINE_RCU_TASKS(rcu_tasks_trace, rcu_tasks_wait_gp, call_rcu_tasks_trace,
1271                  "RCU Tasks Trace");
1272
1273 /* Load from ->trc_reader_special.b.need_qs with proper ordering. */
1274 static u8 rcu_ld_need_qs(struct task_struct *t)
1275 {
1276         smp_mb(); // Enforce full grace-period ordering.
1277         return smp_load_acquire(&t->trc_reader_special.b.need_qs);
1278 }
1279
1280 /* Store to ->trc_reader_special.b.need_qs with proper ordering. */
1281 static void rcu_st_need_qs(struct task_struct *t, u8 v)
1282 {
1283         smp_store_release(&t->trc_reader_special.b.need_qs, v);
1284         smp_mb(); // Enforce full grace-period ordering.
1285 }
1286
1287 /*
1288  * Do a cmpxchg() on ->trc_reader_special.b.need_qs, allowing for
1289  * the four-byte operand-size restriction of some platforms.
1290  * Returns the old value, which is often ignored.
1291  */
1292 u8 rcu_trc_cmpxchg_need_qs(struct task_struct *t, u8 old, u8 new)
1293 {
1294         union rcu_special ret;
1295         union rcu_special trs_old = READ_ONCE(t->trc_reader_special);
1296         union rcu_special trs_new = trs_old;
1297
1298         if (trs_old.b.need_qs != old)
1299                 return trs_old.b.need_qs;
1300         trs_new.b.need_qs = new;
1301         ret.s = cmpxchg(&t->trc_reader_special.s, trs_old.s, trs_new.s);
1302         return ret.b.need_qs;
1303 }
1304 EXPORT_SYMBOL_GPL(rcu_trc_cmpxchg_need_qs);
1305
1306 /*
1307  * If we are the last reader, signal the grace-period kthread.
1308  * Also remove from the per-CPU list of blocked tasks.
1309  */
1310 void rcu_read_unlock_trace_special(struct task_struct *t)
1311 {
1312         unsigned long flags;
1313         struct rcu_tasks_percpu *rtpcp;
1314         union rcu_special trs;
1315
1316         // Open-coded full-word version of rcu_ld_need_qs().
1317         smp_mb(); // Enforce full grace-period ordering.
1318         trs = smp_load_acquire(&t->trc_reader_special);
1319
1320         if (IS_ENABLED(CONFIG_TASKS_TRACE_RCU_READ_MB) && t->trc_reader_special.b.need_mb)
1321                 smp_mb(); // Pairs with update-side barriers.
1322         // Update .need_qs before ->trc_reader_nesting for irq/NMI handlers.
1323         if (trs.b.need_qs == (TRC_NEED_QS_CHECKED | TRC_NEED_QS)) {
1324                 u8 result = rcu_trc_cmpxchg_need_qs(t, TRC_NEED_QS_CHECKED | TRC_NEED_QS,
1325                                                        TRC_NEED_QS_CHECKED);
1326
1327                 WARN_ONCE(result != trs.b.need_qs, "%s: result = %d", __func__, result);
1328         }
1329         if (trs.b.blocked) {
1330                 rtpcp = per_cpu_ptr(rcu_tasks_trace.rtpcpu, t->trc_blkd_cpu);
1331                 raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
1332                 list_del_init(&t->trc_blkd_node);
1333                 WRITE_ONCE(t->trc_reader_special.b.blocked, false);
1334                 raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
1335         }
1336         WRITE_ONCE(t->trc_reader_nesting, 0);
1337 }
1338 EXPORT_SYMBOL_GPL(rcu_read_unlock_trace_special);
1339
1340 /* Add a newly blocked reader task to its CPU's list. */
1341 void rcu_tasks_trace_qs_blkd(struct task_struct *t)
1342 {
1343         unsigned long flags;
1344         struct rcu_tasks_percpu *rtpcp;
1345
1346         local_irq_save(flags);
1347         rtpcp = this_cpu_ptr(rcu_tasks_trace.rtpcpu);
1348         raw_spin_lock_rcu_node(rtpcp); // irqs already disabled
1349         t->trc_blkd_cpu = smp_processor_id();
1350         if (!rtpcp->rtp_blkd_tasks.next)
1351                 INIT_LIST_HEAD(&rtpcp->rtp_blkd_tasks);
1352         list_add(&t->trc_blkd_node, &rtpcp->rtp_blkd_tasks);
1353         WRITE_ONCE(t->trc_reader_special.b.blocked, true);
1354         raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
1355 }
1356 EXPORT_SYMBOL_GPL(rcu_tasks_trace_qs_blkd);
1357
1358 /* Add a task to the holdout list, if it is not already on the list. */
1359 static void trc_add_holdout(struct task_struct *t, struct list_head *bhp)
1360 {
1361         if (list_empty(&t->trc_holdout_list)) {
1362                 get_task_struct(t);
1363                 list_add(&t->trc_holdout_list, bhp);
1364                 n_trc_holdouts++;
1365         }
1366 }
1367
1368 /* Remove a task from the holdout list, if it is in fact present. */
1369 static void trc_del_holdout(struct task_struct *t)
1370 {
1371         if (!list_empty(&t->trc_holdout_list)) {
1372                 list_del_init(&t->trc_holdout_list);
1373                 put_task_struct(t);
1374                 n_trc_holdouts--;
1375         }
1376 }
1377
1378 /* IPI handler to check task state. */
1379 static void trc_read_check_handler(void *t_in)
1380 {
1381         int nesting;
1382         struct task_struct *t = current;
1383         struct task_struct *texp = t_in;
1384
1385         // If the task is no longer running on this CPU, leave.
1386         if (unlikely(texp != t))
1387                 goto reset_ipi; // Already on holdout list, so will check later.
1388
1389         // If the task is not in a read-side critical section, and
1390         // if this is the last reader, awaken the grace-period kthread.
1391         nesting = READ_ONCE(t->trc_reader_nesting);
1392         if (likely(!nesting)) {
1393                 rcu_trc_cmpxchg_need_qs(t, 0, TRC_NEED_QS_CHECKED);
1394                 goto reset_ipi;
1395         }
1396         // If we are racing with an rcu_read_unlock_trace(), try again later.
1397         if (unlikely(nesting < 0))
1398                 goto reset_ipi;
1399
1400         // Get here if the task is in a read-side critical section.
1401         // Set its state so that it will update state for the grace-period
1402         // kthread upon exit from that critical section.
1403         rcu_trc_cmpxchg_need_qs(t, 0, TRC_NEED_QS | TRC_NEED_QS_CHECKED);
1404
1405 reset_ipi:
1406         // Allow future IPIs to be sent on CPU and for task.
1407         // Also order this IPI handler against any later manipulations of
1408         // the intended task.
1409         smp_store_release(per_cpu_ptr(&trc_ipi_to_cpu, smp_processor_id()), false); // ^^^
1410         smp_store_release(&texp->trc_ipi_to_cpu, -1); // ^^^
1411 }
1412
1413 /* Callback function for scheduler to check locked-down task.  */
1414 static int trc_inspect_reader(struct task_struct *t, void *bhp_in)
1415 {
1416         struct list_head *bhp = bhp_in;
1417         int cpu = task_cpu(t);
1418         int nesting;
1419         bool ofl = cpu_is_offline(cpu);
1420
1421         if (task_curr(t) && !ofl) {
1422                 // If no chance of heavyweight readers, do it the hard way.
1423                 if (!IS_ENABLED(CONFIG_TASKS_TRACE_RCU_READ_MB))
1424                         return -EINVAL;
1425
1426                 // If heavyweight readers are enabled on the remote task,
1427                 // we can inspect its state despite its currently running.
1428                 // However, we cannot safely change its state.
1429                 n_heavy_reader_attempts++;
1430                 // Check for "running" idle tasks on offline CPUs.
1431                 if (!rcu_dynticks_zero_in_eqs(cpu, &t->trc_reader_nesting))
1432                         return -EINVAL; // No quiescent state, do it the hard way.
1433                 n_heavy_reader_updates++;
1434                 nesting = 0;
1435         } else {
1436                 // The task is not running, so C-language access is safe.
1437                 nesting = t->trc_reader_nesting;
1438                 WARN_ON_ONCE(ofl && task_curr(t) && !is_idle_task(t));
1439                 if (IS_ENABLED(CONFIG_TASKS_TRACE_RCU_READ_MB) && ofl)
1440                         n_heavy_reader_ofl_updates++;
1441         }
1442
1443         // If not exiting a read-side critical section, mark as checked
1444         // so that the grace-period kthread will remove it from the
1445         // holdout list.
1446         if (!nesting) {
1447                 rcu_trc_cmpxchg_need_qs(t, 0, TRC_NEED_QS_CHECKED);
1448                 return 0;  // In QS, so done.
1449         }
1450         if (nesting < 0)
1451                 return -EINVAL; // Reader transitioning, try again later.
1452
1453         // The task is in a read-side critical section, so set up its
1454         // state so that it will update state upon exit from that critical
1455         // section.
1456         if (!rcu_trc_cmpxchg_need_qs(t, 0, TRC_NEED_QS | TRC_NEED_QS_CHECKED))
1457                 trc_add_holdout(t, bhp);
1458         return 0;
1459 }
1460
1461 /* Attempt to extract the state for the specified task. */
1462 static void trc_wait_for_one_reader(struct task_struct *t,
1463                                     struct list_head *bhp)
1464 {
1465         int cpu;
1466
1467         // If a previous IPI is still in flight, let it complete.
1468         if (smp_load_acquire(&t->trc_ipi_to_cpu) != -1) // Order IPI
1469                 return;
1470
1471         // The current task had better be in a quiescent state.
1472         if (t == current) {
1473                 rcu_trc_cmpxchg_need_qs(t, 0, TRC_NEED_QS_CHECKED);
1474                 WARN_ON_ONCE(READ_ONCE(t->trc_reader_nesting));
1475                 return;
1476         }
1477
1478         // Attempt to nail down the task for inspection.
1479         get_task_struct(t);
1480         if (!task_call_func(t, trc_inspect_reader, bhp)) {
1481                 put_task_struct(t);
1482                 return;
1483         }
1484         put_task_struct(t);
1485
1486         // If this task is not yet on the holdout list, then we are in
1487         // an RCU read-side critical section.  Otherwise, the invocation of
1488         // trc_add_holdout() that added it to the list did the necessary
1489         // get_task_struct().  Either way, the task cannot be freed out
1490         // from under this code.
1491
1492         // If currently running, send an IPI, either way, add to list.
1493         trc_add_holdout(t, bhp);
1494         if (task_curr(t) &&
1495             time_after(jiffies + 1, rcu_tasks_trace.gp_start + rcu_task_ipi_delay)) {
1496                 // The task is currently running, so try IPIing it.
1497                 cpu = task_cpu(t);
1498
1499                 // If there is already an IPI outstanding, let it happen.
1500                 if (per_cpu(trc_ipi_to_cpu, cpu) || t->trc_ipi_to_cpu >= 0)
1501                         return;
1502
1503                 per_cpu(trc_ipi_to_cpu, cpu) = true;
1504                 t->trc_ipi_to_cpu = cpu;
1505                 rcu_tasks_trace.n_ipis++;
1506                 if (smp_call_function_single(cpu, trc_read_check_handler, t, 0)) {
1507                         // Just in case there is some other reason for
1508                         // failure than the target CPU being offline.
1509                         WARN_ONCE(1, "%s():  smp_call_function_single() failed for CPU: %d\n",
1510                                   __func__, cpu);
1511                         rcu_tasks_trace.n_ipis_fails++;
1512                         per_cpu(trc_ipi_to_cpu, cpu) = false;
1513                         t->trc_ipi_to_cpu = -1;
1514                 }
1515         }
1516 }
1517
1518 /*
1519  * Initialize for first-round processing for the specified task.
1520  * Return false if task is NULL or already taken care of, true otherwise.
1521  */
1522 static bool rcu_tasks_trace_pertask_prep(struct task_struct *t, bool notself)
1523 {
1524         // During early boot when there is only the one boot CPU, there
1525         // is no idle task for the other CPUs.  Also, the grace-period
1526         // kthread is always in a quiescent state.  In addition, just return
1527         // if this task is already on the list.
1528         if (unlikely(t == NULL) || (t == current && notself) || !list_empty(&t->trc_holdout_list))
1529                 return false;
1530
1531         rcu_st_need_qs(t, 0);
1532         t->trc_ipi_to_cpu = -1;
1533         return true;
1534 }
1535
1536 /* Do first-round processing for the specified task. */
1537 static void rcu_tasks_trace_pertask(struct task_struct *t, struct list_head *hop)
1538 {
1539         if (rcu_tasks_trace_pertask_prep(t, true))
1540                 trc_wait_for_one_reader(t, hop);
1541 }
1542
1543 /* Initialize for a new RCU-tasks-trace grace period. */
1544 static void rcu_tasks_trace_pregp_step(struct list_head *hop)
1545 {
1546         LIST_HEAD(blkd_tasks);
1547         int cpu;
1548         unsigned long flags;
1549         struct rcu_tasks_percpu *rtpcp;
1550         struct task_struct *t;
1551
1552         // There shouldn't be any old IPIs, but...
1553         for_each_possible_cpu(cpu)
1554                 WARN_ON_ONCE(per_cpu(trc_ipi_to_cpu, cpu));
1555
1556         // Disable CPU hotplug across the CPU scan for the benefit of
1557         // any IPIs that might be needed.  This also waits for all readers
1558         // in CPU-hotplug code paths.
1559         cpus_read_lock();
1560
1561         // These rcu_tasks_trace_pertask_prep() calls are serialized to
1562         // allow safe access to the hop list.
1563         for_each_online_cpu(cpu) {
1564                 rcu_read_lock();
1565                 t = cpu_curr_snapshot(cpu);
1566                 if (rcu_tasks_trace_pertask_prep(t, true))
1567                         trc_add_holdout(t, hop);
1568                 rcu_read_unlock();
1569                 cond_resched_tasks_rcu_qs();
1570         }
1571
1572         // Only after all running tasks have been accounted for is it
1573         // safe to take care of the tasks that have blocked within their
1574         // current RCU tasks trace read-side critical section.
1575         for_each_possible_cpu(cpu) {
1576                 rtpcp = per_cpu_ptr(rcu_tasks_trace.rtpcpu, cpu);
1577                 raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
1578                 list_splice_init(&rtpcp->rtp_blkd_tasks, &blkd_tasks);
1579                 while (!list_empty(&blkd_tasks)) {
1580                         rcu_read_lock();
1581                         t = list_first_entry(&blkd_tasks, struct task_struct, trc_blkd_node);
1582                         list_del_init(&t->trc_blkd_node);
1583                         list_add(&t->trc_blkd_node, &rtpcp->rtp_blkd_tasks);
1584                         raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
1585                         rcu_tasks_trace_pertask(t, hop);
1586                         rcu_read_unlock();
1587                         raw_spin_lock_irqsave_rcu_node(rtpcp, flags);
1588                 }
1589                 raw_spin_unlock_irqrestore_rcu_node(rtpcp, flags);
1590                 cond_resched_tasks_rcu_qs();
1591         }
1592
1593         // Re-enable CPU hotplug now that the holdout list is populated.
1594         cpus_read_unlock();
1595 }
1596
1597 /*
1598  * Do intermediate processing between task and holdout scans.
1599  */
1600 static void rcu_tasks_trace_postscan(struct list_head *hop)
1601 {
1602         // Wait for late-stage exiting tasks to finish exiting.
1603         // These might have passed the call to exit_tasks_rcu_finish().
1604
1605         // If you remove the following line, update rcu_trace_implies_rcu_gp()!!!
1606         synchronize_rcu();
1607         // Any tasks that exit after this point will set
1608         // TRC_NEED_QS_CHECKED in ->trc_reader_special.b.need_qs.
1609 }
1610
1611 /* Communicate task state back to the RCU tasks trace stall warning request. */
1612 struct trc_stall_chk_rdr {
1613         int nesting;
1614         int ipi_to_cpu;
1615         u8 needqs;
1616 };
1617
1618 static int trc_check_slow_task(struct task_struct *t, void *arg)
1619 {
1620         struct trc_stall_chk_rdr *trc_rdrp = arg;
1621
1622         if (task_curr(t) && cpu_online(task_cpu(t)))
1623                 return false; // It is running, so decline to inspect it.
1624         trc_rdrp->nesting = READ_ONCE(t->trc_reader_nesting);
1625         trc_rdrp->ipi_to_cpu = READ_ONCE(t->trc_ipi_to_cpu);
1626         trc_rdrp->needqs = rcu_ld_need_qs(t);
1627         return true;
1628 }
1629
1630 /* Show the state of a task stalling the current RCU tasks trace GP. */
1631 static void show_stalled_task_trace(struct task_struct *t, bool *firstreport)
1632 {
1633         int cpu;
1634         struct trc_stall_chk_rdr trc_rdr;
1635         bool is_idle_tsk = is_idle_task(t);
1636
1637         if (*firstreport) {
1638                 pr_err("INFO: rcu_tasks_trace detected stalls on tasks:\n");
1639                 *firstreport = false;
1640         }
1641         cpu = task_cpu(t);
1642         if (!task_call_func(t, trc_check_slow_task, &trc_rdr))
1643                 pr_alert("P%d: %c%c\n",
1644                          t->pid,
1645                          ".I"[t->trc_ipi_to_cpu >= 0],
1646                          ".i"[is_idle_tsk]);
1647         else
1648                 pr_alert("P%d: %c%c%c%c nesting: %d%c%c cpu: %d%s\n",
1649                          t->pid,
1650                          ".I"[trc_rdr.ipi_to_cpu >= 0],
1651                          ".i"[is_idle_tsk],
1652                          ".N"[cpu >= 0 && tick_nohz_full_cpu(cpu)],
1653                          ".B"[!!data_race(t->trc_reader_special.b.blocked)],
1654                          trc_rdr.nesting,
1655                          " !CN"[trc_rdr.needqs & 0x3],
1656                          " ?"[trc_rdr.needqs > 0x3],
1657                          cpu, cpu_online(cpu) ? "" : "(offline)");
1658         sched_show_task(t);
1659 }
1660
1661 /* List stalled IPIs for RCU tasks trace. */
1662 static void show_stalled_ipi_trace(void)
1663 {
1664         int cpu;
1665
1666         for_each_possible_cpu(cpu)
1667                 if (per_cpu(trc_ipi_to_cpu, cpu))
1668                         pr_alert("\tIPI outstanding to CPU %d\n", cpu);
1669 }
1670
1671 /* Do one scan of the holdout list. */
1672 static void check_all_holdout_tasks_trace(struct list_head *hop,
1673                                           bool needreport, bool *firstreport)
1674 {
1675         struct task_struct *g, *t;
1676
1677         // Disable CPU hotplug across the holdout list scan for IPIs.
1678         cpus_read_lock();
1679
1680         list_for_each_entry_safe(t, g, hop, trc_holdout_list) {
1681                 // If safe and needed, try to check the current task.
1682                 if (READ_ONCE(t->trc_ipi_to_cpu) == -1 &&
1683                     !(rcu_ld_need_qs(t) & TRC_NEED_QS_CHECKED))
1684                         trc_wait_for_one_reader(t, hop);
1685
1686                 // If check succeeded, remove this task from the list.
1687                 if (smp_load_acquire(&t->trc_ipi_to_cpu) == -1 &&
1688                     rcu_ld_need_qs(t) == TRC_NEED_QS_CHECKED)
1689                         trc_del_holdout(t);
1690                 else if (needreport)
1691                         show_stalled_task_trace(t, firstreport);
1692                 cond_resched_tasks_rcu_qs();
1693         }
1694
1695         // Re-enable CPU hotplug now that the holdout list scan has completed.
1696         cpus_read_unlock();
1697
1698         if (needreport) {
1699                 if (*firstreport)
1700                         pr_err("INFO: rcu_tasks_trace detected stalls? (Late IPI?)\n");
1701                 show_stalled_ipi_trace();
1702         }
1703 }
1704
1705 static void rcu_tasks_trace_empty_fn(void *unused)
1706 {
1707 }
1708
1709 /* Wait for grace period to complete and provide ordering. */
1710 static void rcu_tasks_trace_postgp(struct rcu_tasks *rtp)
1711 {
1712         int cpu;
1713
1714         // Wait for any lingering IPI handlers to complete.  Note that
1715         // if a CPU has gone offline or transitioned to userspace in the
1716         // meantime, all IPI handlers should have been drained beforehand.
1717         // Yes, this assumes that CPUs process IPIs in order.  If that ever
1718         // changes, there will need to be a recheck and/or timed wait.
1719         for_each_online_cpu(cpu)
1720                 if (WARN_ON_ONCE(smp_load_acquire(per_cpu_ptr(&trc_ipi_to_cpu, cpu))))
1721                         smp_call_function_single(cpu, rcu_tasks_trace_empty_fn, NULL, 1);
1722
1723         smp_mb(); // Caller's code must be ordered after wakeup.
1724                   // Pairs with pretty much every ordering primitive.
1725 }
1726
1727 /* Report any needed quiescent state for this exiting task. */
1728 static void exit_tasks_rcu_finish_trace(struct task_struct *t)
1729 {
1730         union rcu_special trs = READ_ONCE(t->trc_reader_special);
1731
1732         rcu_trc_cmpxchg_need_qs(t, 0, TRC_NEED_QS_CHECKED);
1733         WARN_ON_ONCE(READ_ONCE(t->trc_reader_nesting));
1734         if (WARN_ON_ONCE(rcu_ld_need_qs(t) & TRC_NEED_QS || trs.b.blocked))
1735                 rcu_read_unlock_trace_special(t);
1736         else
1737                 WRITE_ONCE(t->trc_reader_nesting, 0);
1738 }
1739
1740 /**
1741  * call_rcu_tasks_trace() - Queue a callback trace task-based grace period
1742  * @rhp: structure to be used for queueing the RCU updates.
1743  * @func: actual callback function to be invoked after the grace period
1744  *
1745  * The callback function will be invoked some time after a trace rcu-tasks
1746  * grace period elapses, in other words after all currently executing
1747  * trace rcu-tasks read-side critical sections have completed. These
1748  * read-side critical sections are delimited by calls to rcu_read_lock_trace()
1749  * and rcu_read_unlock_trace().
1750  *
1751  * See the description of call_rcu() for more detailed information on
1752  * memory ordering guarantees.
1753  */
1754 void call_rcu_tasks_trace(struct rcu_head *rhp, rcu_callback_t func)
1755 {
1756         call_rcu_tasks_generic(rhp, func, &rcu_tasks_trace);
1757 }
1758 EXPORT_SYMBOL_GPL(call_rcu_tasks_trace);
1759
1760 /**
1761  * synchronize_rcu_tasks_trace - wait for a trace rcu-tasks grace period
1762  *
1763  * Control will return to the caller some time after a trace rcu-tasks
1764  * grace period has elapsed, in other words after all currently executing
1765  * trace rcu-tasks read-side critical sections have elapsed. These read-side
1766  * critical sections are delimited by calls to rcu_read_lock_trace()
1767  * and rcu_read_unlock_trace().
1768  *
1769  * This is a very specialized primitive, intended only for a few uses in
1770  * tracing and other situations requiring manipulation of function preambles
1771  * and profiling hooks.  The synchronize_rcu_tasks_trace() function is not
1772  * (yet) intended for heavy use from multiple CPUs.
1773  *
1774  * See the description of synchronize_rcu() for more detailed information
1775  * on memory ordering guarantees.
1776  */
1777 void synchronize_rcu_tasks_trace(void)
1778 {
1779         RCU_LOCKDEP_WARN(lock_is_held(&rcu_trace_lock_map), "Illegal synchronize_rcu_tasks_trace() in RCU Tasks Trace read-side critical section");
1780         synchronize_rcu_tasks_generic(&rcu_tasks_trace);
1781 }
1782 EXPORT_SYMBOL_GPL(synchronize_rcu_tasks_trace);
1783
1784 /**
1785  * rcu_barrier_tasks_trace - Wait for in-flight call_rcu_tasks_trace() callbacks.
1786  *
1787  * Although the current implementation is guaranteed to wait, it is not
1788  * obligated to, for example, if there are no pending callbacks.
1789  */
1790 void rcu_barrier_tasks_trace(void)
1791 {
1792         rcu_barrier_tasks_generic(&rcu_tasks_trace);
1793 }
1794 EXPORT_SYMBOL_GPL(rcu_barrier_tasks_trace);
1795
1796 static int __init rcu_spawn_tasks_trace_kthread(void)
1797 {
1798         cblist_init_generic(&rcu_tasks_trace);
1799         if (IS_ENABLED(CONFIG_TASKS_TRACE_RCU_READ_MB)) {
1800                 rcu_tasks_trace.gp_sleep = HZ / 10;
1801                 rcu_tasks_trace.init_fract = HZ / 10;
1802         } else {
1803                 rcu_tasks_trace.gp_sleep = HZ / 200;
1804                 if (rcu_tasks_trace.gp_sleep <= 0)
1805                         rcu_tasks_trace.gp_sleep = 1;
1806                 rcu_tasks_trace.init_fract = HZ / 200;
1807                 if (rcu_tasks_trace.init_fract <= 0)
1808                         rcu_tasks_trace.init_fract = 1;
1809         }
1810         rcu_tasks_trace.pregp_func = rcu_tasks_trace_pregp_step;
1811         rcu_tasks_trace.postscan_func = rcu_tasks_trace_postscan;
1812         rcu_tasks_trace.holdouts_func = check_all_holdout_tasks_trace;
1813         rcu_tasks_trace.postgp_func = rcu_tasks_trace_postgp;
1814         rcu_spawn_tasks_kthread_generic(&rcu_tasks_trace);
1815         return 0;
1816 }
1817
1818 #if !defined(CONFIG_TINY_RCU)
1819 void show_rcu_tasks_trace_gp_kthread(void)
1820 {
1821         char buf[64];
1822
1823         sprintf(buf, "N%lu h:%lu/%lu/%lu",
1824                 data_race(n_trc_holdouts),
1825                 data_race(n_heavy_reader_ofl_updates),
1826                 data_race(n_heavy_reader_updates),
1827                 data_race(n_heavy_reader_attempts));
1828         show_rcu_tasks_generic_gp_kthread(&rcu_tasks_trace, buf);
1829 }
1830 EXPORT_SYMBOL_GPL(show_rcu_tasks_trace_gp_kthread);
1831 #endif // !defined(CONFIG_TINY_RCU)
1832
1833 #else /* #ifdef CONFIG_TASKS_TRACE_RCU */
1834 static void exit_tasks_rcu_finish_trace(struct task_struct *t) { }
1835 #endif /* #else #ifdef CONFIG_TASKS_TRACE_RCU */
1836
1837 #ifndef CONFIG_TINY_RCU
1838 void show_rcu_tasks_gp_kthreads(void)
1839 {
1840         show_rcu_tasks_classic_gp_kthread();
1841         show_rcu_tasks_rude_gp_kthread();
1842         show_rcu_tasks_trace_gp_kthread();
1843 }
1844 #endif /* #ifndef CONFIG_TINY_RCU */
1845
1846 #ifdef CONFIG_PROVE_RCU
1847 struct rcu_tasks_test_desc {
1848         struct rcu_head rh;
1849         const char *name;
1850         bool notrun;
1851         unsigned long runstart;
1852 };
1853
1854 static struct rcu_tasks_test_desc tests[] = {
1855         {
1856                 .name = "call_rcu_tasks()",
1857                 /* If not defined, the test is skipped. */
1858                 .notrun = IS_ENABLED(CONFIG_TASKS_RCU),
1859         },
1860         {
1861                 .name = "call_rcu_tasks_rude()",
1862                 /* If not defined, the test is skipped. */
1863                 .notrun = IS_ENABLED(CONFIG_TASKS_RUDE_RCU),
1864         },
1865         {
1866                 .name = "call_rcu_tasks_trace()",
1867                 /* If not defined, the test is skipped. */
1868                 .notrun = IS_ENABLED(CONFIG_TASKS_TRACE_RCU)
1869         }
1870 };
1871
1872 static void test_rcu_tasks_callback(struct rcu_head *rhp)
1873 {
1874         struct rcu_tasks_test_desc *rttd =
1875                 container_of(rhp, struct rcu_tasks_test_desc, rh);
1876
1877         pr_info("Callback from %s invoked.\n", rttd->name);
1878
1879         rttd->notrun = false;
1880 }
1881
1882 static void rcu_tasks_initiate_self_tests(void)
1883 {
1884         pr_info("Running RCU-tasks wait API self tests\n");
1885 #ifdef CONFIG_TASKS_RCU
1886         tests[0].runstart = jiffies;
1887         synchronize_rcu_tasks();
1888         call_rcu_tasks(&tests[0].rh, test_rcu_tasks_callback);
1889 #endif
1890
1891 #ifdef CONFIG_TASKS_RUDE_RCU
1892         tests[1].runstart = jiffies;
1893         synchronize_rcu_tasks_rude();
1894         call_rcu_tasks_rude(&tests[1].rh, test_rcu_tasks_callback);
1895 #endif
1896
1897 #ifdef CONFIG_TASKS_TRACE_RCU
1898         tests[2].runstart = jiffies;
1899         synchronize_rcu_tasks_trace();
1900         call_rcu_tasks_trace(&tests[2].rh, test_rcu_tasks_callback);
1901 #endif
1902 }
1903
1904 /*
1905  * Return:  0 - test passed
1906  *          1 - test failed, but have not timed out yet
1907  *         -1 - test failed and timed out
1908  */
1909 static int rcu_tasks_verify_self_tests(void)
1910 {
1911         int ret = 0;
1912         int i;
1913         unsigned long bst = rcu_task_stall_timeout;
1914
1915         if (bst <= 0 || bst > RCU_TASK_BOOT_STALL_TIMEOUT)
1916                 bst = RCU_TASK_BOOT_STALL_TIMEOUT;
1917         for (i = 0; i < ARRAY_SIZE(tests); i++) {
1918                 while (tests[i].notrun) {               // still hanging.
1919                         if (time_after(jiffies, tests[i].runstart + bst)) {
1920                                 pr_err("%s has failed boot-time tests.\n", tests[i].name);
1921                                 ret = -1;
1922                                 break;
1923                         }
1924                         ret = 1;
1925                         break;
1926                 }
1927         }
1928         WARN_ON(ret < 0);
1929
1930         return ret;
1931 }
1932
1933 /*
1934  * Repeat the rcu_tasks_verify_self_tests() call once every second until the
1935  * test passes or has timed out.
1936  */
1937 static struct delayed_work rcu_tasks_verify_work;
1938 static void rcu_tasks_verify_work_fn(struct work_struct *work __maybe_unused)
1939 {
1940         int ret = rcu_tasks_verify_self_tests();
1941
1942         if (ret <= 0)
1943                 return;
1944
1945         /* Test fails but not timed out yet, reschedule another check */
1946         schedule_delayed_work(&rcu_tasks_verify_work, HZ);
1947 }
1948
1949 static int rcu_tasks_verify_schedule_work(void)
1950 {
1951         INIT_DELAYED_WORK(&rcu_tasks_verify_work, rcu_tasks_verify_work_fn);
1952         rcu_tasks_verify_work_fn(NULL);
1953         return 0;
1954 }
1955 late_initcall(rcu_tasks_verify_schedule_work);
1956 #else /* #ifdef CONFIG_PROVE_RCU */
1957 static void rcu_tasks_initiate_self_tests(void) { }
1958 #endif /* #else #ifdef CONFIG_PROVE_RCU */
1959
1960 void __init rcu_init_tasks_generic(void)
1961 {
1962 #ifdef CONFIG_TASKS_RCU
1963         rcu_spawn_tasks_kthread();
1964 #endif
1965
1966 #ifdef CONFIG_TASKS_RUDE_RCU
1967         rcu_spawn_tasks_rude_kthread();
1968 #endif
1969
1970 #ifdef CONFIG_TASKS_TRACE_RCU
1971         rcu_spawn_tasks_trace_kthread();
1972 #endif
1973
1974         // Run the self-tests.
1975         rcu_tasks_initiate_self_tests();
1976 }
1977
1978 #else /* #ifdef CONFIG_TASKS_RCU_GENERIC */
1979 static inline void rcu_tasks_bootup_oddness(void) {}
1980 #endif /* #else #ifdef CONFIG_TASKS_RCU_GENERIC */