CVE-2011-4621: Loop with Unreachable Exit Condition ('Infinite Loop') (CWE-835)
value: The Linux kernel before 2.6.37 does not properly implement a certain clock-update optimization, which allows local users to cause a denial of service (system hang) via an application that executes code in a loop.
CWE description: The product contains an iteration or loop with an exit condition that cannot be reached, i.e., an infinite loop.
CVSS v3 base score: 5.5
Published: 2012-05-17T11:00Z
Repository: https://github.com/torvalds/linux
Language: C
Files changed: kernel/fork.c, kernel/sched.c
Commit date: 2010-12-08 20:15:06 +0100
Commit message: Sched: fix skip_clock_update optimization

idle_balance() drops/retakes rq->lock, leaving the previous task
vulnerable to set_tsk_need_resched().  Clear it after we return
from balancing instead, and in setup_thread_stack() as well, so
no successfully descheduled or never scheduled task has it set.

Need resched confused the skip_clock_update logic, which assumes
that the next call to update_rq_clock() will come nearly immediately
after being set.  Make the optimization robust against the waking
a sleeper before it sucessfully deschedules case by checking that
the current task has not been dequeued before setting the flag,
since it is that useless clock update we're trying to save, and
clear unconditionally in schedule() proper instead of conditionally
in put_prev_task().

Signed-off-by: Mike Galbraith <efault@gmx.de>
Reported-by: Bjoern B. Brandenburg <bbb.lst@gmail.com>
Tested-by: Yong Zhang <yong.zhang0@gmail.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: stable@kernel.org
LKML-Reference: <1291802742.1417.9.camel@marge.simson.net>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

Diff: diff --git a/kernel/fork.c b/kernel/fork.c
index 3b159c5991b75..5447dc7defa95 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -271,10 +271,11 @@ static struct task_struct *dup_task_struct(struct task_struct *orig)
 	if (err)
 		goto out;
 
 	setup_thread_stack(tsk, orig);
 	clear_user_return_notifier(tsk);
+	clear_tsk_need_resched(tsk);
 	stackend = end_of_stack(tsk);
 	*stackend = STACK_END_MAGIC;	/* for overflow detection */
 
 #ifdef CONFIG_CC_STACKPROTECTOR
 	tsk->stack_canary = get_random_int();
diff --git a/kernel/sched.c b/kernel/sched.c
index 6b7c26a1a097e..da14302a98571 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -639,21 +639,22 @@ static inline struct task_group *task_group(struct task_struct *p)
 static u64 irq_time_cpu(int cpu);
 static void sched_irq_time_avg_update(struct rq *rq, u64 irq_time);
 
 inline void update_rq_clock(struct rq *rq)
 {
-	if (!rq->skip_clock_update) {
-		int cpu = cpu_of(rq);
-		u64 irq_time;
+	int cpu = cpu_of(rq);
+	u64 irq_time;
 
-		rq->clock = sched_clock_cpu(cpu);
-		irq_time = irq_time_cpu(cpu);
-		if (rq->clock - irq_time > rq->clock_task)
-			rq->clock_task = rq->clock - irq_time;
+	if (rq->skip_clock_update)
+		return;
 
-		sched_irq_time_avg_update(rq, irq_time);
-	}
+	rq->clock = sched_clock_cpu(cpu);
+	irq_time = irq_time_cpu(cpu);
+	if (rq->clock - irq_time > rq->clock_task)
+		rq->clock_task = rq->clock - irq_time;
+
+	sched_irq_time_avg_update(rq, irq_time);
 }
 
 /*
  * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
  */
@@ -2127,11 +2128,11 @@ static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
 
 	/*
 	 * A queue event has occurred, and we're going to schedule.  In
 	 * this case, we can save a useless back to back clock update.
 	 */
-	if (test_tsk_need_resched(rq->curr))
+	if (rq->curr->se.on_rq && test_tsk_need_resched(rq->curr))
 		rq->skip_clock_update = 1;
 }
 
 #ifdef CONFIG_SMP
 /*
@@ -3971,11 +3972,10 @@ static inline void schedule_debug(struct task_struct *prev)
 
 static void put_prev_task(struct rq *rq, struct task_struct *prev)
 {
 	if (prev->se.on_rq)
 		update_rq_clock(rq);
-	rq->skip_clock_update = 0;
 	prev->sched_class->put_prev_task(rq, prev);
 }
 
 /*
  * Pick up the highest-prio task:
@@ -4029,11 +4029,10 @@ asmlinkage void __sched schedule(void)
 
 	if (sched_feat(HRTICK))
 		hrtick_clear(rq);
 
 	raw_spin_lock_irq(&rq->lock);
-	clear_tsk_need_resched(prev);
 
 	switch_count = &prev->nivcsw;
 	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
 		if (unlikely(signal_pending_state(prev->state, prev))) {
 			prev->state = TASK_RUNNING;
@@ -4061,18 +4060,21 @@ asmlinkage void __sched schedule(void)
 	if (unlikely(!rq->nr_running))
 		idle_balance(cpu, rq);
 
 	put_prev_task(rq, prev);
 	next = pick_next_task(rq);
+	clear_tsk_need_resched(prev);
+	rq->skip_clock_update = 0;
 
 	if (likely(prev != next)) {
 		sched_info_switch(prev, next);
 		perf_event_task_sched_out(prev, next);
 
 		rq->nr_switches++;
 		rq->curr = next;
 		++*switch_count;
+		WARN_ON_ONCE(test_tsk_need_resched(next));
 
 		context_switch(rq, prev, next); /* unlocks the rq */
 		/*
 		 * The context switch have flipped the stack from under us
 		 * and restored the local variables which were saved when

Vulnerable code: 	if (!rq->skip_clock_update) {
		int cpu = cpu_of(rq);
		u64 irq_time;
		rq->clock = sched_clock_cpu(cpu);
		irq_time = irq_time_cpu(cpu);
		if (rq->clock - irq_time > rq->clock_task)
			rq->clock_task = rq->clock - irq_time;
		sched_irq_time_avg_update(rq, irq_time);
	}
	if (test_tsk_need_resched(rq->curr))
	rq->skip_clock_update = 0;
	clear_tsk_need_resched(prev);
Fixed code: 	clear_tsk_need_resched(tsk);
	int cpu = cpu_of(rq);
	u64 irq_time;
	if (rq->skip_clock_update)
		return;
	rq->clock = sched_clock_cpu(cpu);
	irq_time = irq_time_cpu(cpu);
	if (rq->clock - irq_time > rq->clock_task)
		rq->clock_task = rq->clock - irq_time;

	sched_irq_time_avg_update(rq, irq_time);
	if (rq->curr->se.on_rq && test_tsk_need_resched(rq->curr))
	clear_tsk_need_resched(prev);
	rq->skip_clock_update = 0;
		WARN_ON_ONCE(test_tsk_need_resched(next));