Linux kernel: scheduler race can leave a CPU idle with runnable tasks

In the Linux kernel, the following vulnerability has been resolved:

sched/core: Call wakeup_preempt() for queued tasks during class change

Paul reported recent RCU changes exposed a lost resched where CPU idles with a rcutorture thread waiting while being completely runnable.

Dumping the rq state at the time of idling with runnable tasks showed the following:

rq->next_class = &fair_sched_class rq->nr_running = 1 rq->cfs.h_nr_queued = 0 rq->rt.rt_nr_running = 1

Although the waiting task was an RT task, "rq->next_class" did not point to rt_sched_class and was stuck at the lower priority fair_sched_class.

Inspecting sched_change_end() revealed the following race with __sched_setscheduler() for queued, but non-running tasks:

CPU0                                   CPU1
====                                   ====

__schedule()

/*
 * rq->donor is a fair task that blocks.
 * rq->next_class = &fair_sched_class
 */

rq_lock(rq0)

pick_next_task()
  /* nr_running = 0 */
  pick_task_fair()
    sched_balance_newidle()
      raw_spin_rq_unlock(rq0)
                                rq_lock(rq0)

                                activate_task(rq0, p)
                                  /* p is a fair task */
                                  rq0->nr_running++;
                                  rq0->cfs.h_nr_queued++;
                                  wakeup_preempt(rq, p)
                                    rq->next_class = &fair_sched_class
                                    resched_curr()

                                rq_unlock(rq0)

                                __sched_setscheduler(p)
                                  /* p is moved to SCHED_RR */
                                  task_rq_lock(p)
                                  sched_change_begin()

			      rq0->cfs.h_nr_queued--;
			      rq0->rt.rt_nr_running++;

                                  sched_change_end()
                                    /*
                                     * p->on_rq = 1 (ctx->queued)
                                     * but p is not rq->donor
                                     * (!ctx->running) hence
                                     * resched_curr() is and
                                     * rq->next_class upgrade is
                                     * skipped.
                                     */

                                   task_rq_unlock()

      raw_spin_rq_lock(rq0)

      /*
       * rq->nr_running = 1
       * rq->cfs.h_nr_queued = 0
       * rq->rt.rt_nr_running = 1
       * rq->next_class = &fair_sched_class
       */

       if (rq->cfs.h_nr_queued && ...)
         /* Above is false */

       if (rq_modified_above(this_rq, &fair_sched_class))
         /* Also false since rq->next_class is still fair */

  /*
   * sched_balance_newidle() is considered to
   * have failed to pull any fair tasks and no
   * other wakeups were detected.
   */
   return NULL; /* pick_task_fair() */

pick_task_idle()
  return rq->idle;

next = rq->idle;

/* Preemption indicators are lost */
clear_tsk_need_resched(prev);
clear_preempt_need_resched();

rq->curr = rq->idle;

!!! rq->idle switches in with rq->running == 1 but !need_resched() !!!

In simple words, enqueue, followed by a class change of the newly queued task goes unnoticed in rq->next_class indicator and sched_balance_newidle() sees no fair task, nor any higher priority task enqueued.

The above sequence will lead to CPU idling with a runnable task on the CPU.

Call wakeup_preempt() for ctx->queued cases in sched_change_end() to re-evaluate rq->next_class after class change (ENQUEUE_CLASS) and set the NEED_RESCHED indicator accordingly.

Newidle balance will correctly see an enqueue of a higher priority t ---truncated---