possible recursive locking in numasched code
Hi Peter,
While running tests with patches for sched-numa rewrite posted at
http://permalink.gmane.org/gmane.linux.kernel/1335968, I came across a possible recursive locking scenaio.
Please see approaches and a possible patch to avoid the same.
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc1-numasched_v2_100912+ #2 Not tainted
-------------------------------------------------------
gzip/54680 is trying to acquire lock:
(&p->pi_lock){-.-.-.}, at: [<ffffffff81078b08>] task_work_add+0x38/0xb0
but task is already holding lock:
(&rq->lock){-.-.-.}, at: [<ffffffff8108e203>] scheduler_tick+0x53/0x150
which lock already depends on the new lock.
the existing dependency chain (in reverse order) is:
-> #1 (&rq->lock){-.-.-.}:
[<ffffffff810be782>] lock_acquire+0xa2/0x130
[<ffffffff81551866>] _raw_spin_lock+0x36/0x70
[<ffffffff810903c7>] wake_up_new_task+0xa7/0x1c0
[<ffffffff8105259b>] do_fork+0xcb/0x380
[<ffffffff8101cef6>] kernel_thread+0x76/0x80
[<ffffffff81535036>] rest_init+0x26/0x160
[<ffffffff81ca6d93>] start_kernel+0x3b6/0x3c3
[<ffffffff81ca6356>] x86_64_start_reservations+0x131/0x136
[<ffffffff81ca645e>] x86_64_start_kernel+0x103/0x112-> #0 (&p->pi_lock){-.-.-.}:
[<ffffffff810be478>] __lock_acquire+0x1428/0x1690
[<ffffffff810be782>] lock_acquire+0xa2/0x130
[<ffffffff81551a15>] _raw_spin_lock_irqsave+0x55/0xa0
[<ffffffff81078b08>] task_work_add+0x38/0xb0
[<ffffffff8109920f>] task_tick_numa+0xcf/0xe0
[<ffffffff81099fb9>] task_tick_fair+0x129/0x160
[<ffffffff8108e28e>] scheduler_tick+0xde/0x150
[<ffffffff81064dfe>] update_process_times+0x6e/0x90
[<ffffffff810b68d6>] tick_sched_timer+0x76/0xe0
[<ffffffff81084ec8>] __run_hrtimer+0x78/0x1b0
[<ffffffff810852a6>] hrtimer_interrupt+0x106/0x280
[<ffffffff8155cc39>] smp_apic_timer_interrupt+0x69/0x99
[<ffffffff8155bb2f>] apic_timer_interrupt+0x6f/0x80other info that might help us debug this:
Possible unsafe locking scenario:
CPU0 CPU1
---- ----
lock(&rq->lock);
lock(&p->pi_lock);
lock(&rq->lock); lock(&p->pi_lock);
*** DEADLOCK ***
1 lock held by gzip/54680:
#0: (&rq->lock){-.-.-.}, at: [<ffffffff8108e203>] scheduler_tick+0x53/0x150
stack backtrace: Pid: 54680, comm: gzip Not tainted 3.6.0-rc1-numasched_v2_100912+ #2 Call Trace: <IRQ> [<ffffffff810bbc6a>] print_circular_bug+0x21a/0x2f0 [<ffffffff810be478>] __lock_acquire+0x1428/0x1690 [<ffffffff81096ab8>] ? sched_clock_cpu+0xb8/0x110 [<ffffffff810be782>] lock_acquire+0xa2/0x130 [<ffffffff81078b08>] ? task_work_add+0x38/0xb0 [<ffffffff81096b7f>] ? local_clock+0x6f/0x80 [<ffffffff81551a15>] _raw_spin_lock_irqsave+0x55/0xa0 [<ffffffff81078b08>] ? task_work_add+0x38/0xb0 [<ffffffff81078b08>] task_work_add+0x38/0xb0 [<ffffffff8109920f>] task_tick_numa+0xcf/0xe0 [<ffffffff81099fb9>] task_tick_fair+0x129/0x160 [<ffffffff8108e28e>] scheduler_tick+0xde/0x150 [<ffffffff81064dfe>] update_process_times+0x6e/0x90 [<ffffffff810b68d6>] tick_sched_timer+0x76/0xe0 [<ffffffff81084ec8>] __run_hrtimer+0x78/0x1b0 [<ffffffff810b6860>] ? tick_setup_sched_timer+0x100/0x100 [<ffffffff810852a6>] hrtimer_interrupt+0x106/0x280 [<ffffffff8155cc39>] smp_apic_timer_interrupt+0x69/0x99 [<ffffffff8155bb2f>] apic_timer_interrupt+0x6f/0x80 <EOI> [<ffffffff81552595>] ? retint_swapgs+0x13/0x1b
So its clear that we are calling task_work_add from scheduler_tick. scheduler_tick has already taken rq->lock and task_work_add needs to take the same rq->lock.
I figured out that this deadlock can be resolved in more than one way.
1. Add a new callback in sched_class.
May be the cleanest but not sure if its worth adding a callback just
for sched class.
2. Have a modified task_work_add that assumes rq->lock is already taken. We have to export such an interface and that seems risky if somebody
unknowingly uses such an interface instead of main interface.
3. Move the task_tick_numa to sleep/wakeup.
Not sure about the overheads.
4. Move the call to task_tick_numa to outside the rq->lock.
Not a clean approach as in we end up calling a sched/fair.c defined
function in sched/core.c explicitly.
The below patch tries to implement 4th approach.
---
From: Srikar Dronamraju <[email protected]>
Date: Tue, 25 Sep 2012 02:37:55 -0700
Subject: [PATCH] Dont call task_tick_numa while holding the rq->lock
task_tick_numa() calls task_work_add() which also needs rq->lock. However task_tick_numa() gets called under rq->lock. This leads to recursive locking. Avoid recursive locking by calling task_tick_numa() outside the rq->lock.
---
kernel/sched/core.c +3 -0
@@ -3236,6 +3236,9 @@ void scheduler_tick(void) curr->sched_class->task_tick (rq, curr,0 );raw_spin_unlock (&rq->lock); +if (sched_feat_numa (NUMA ) && curr->sched_class == &fair_sched_class) +task_tick_numa (rq, curr); +perf_event_task_tick ();#ifdef CONFIG_SMP
kernel/sched/fair.c +0 -2
@@ -5417,8 +5417,6 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)entity_tick (cfs_rq, se, queued); } -if (sched_feat_numa (NUMA )) -task_tick_numa (rq, curr); }/*
kernel/sched/sched.h +1 -0
@@ -913,6 +913,7 @@ extern struct rt_bandwidth def_rt_bandwidth;extern void init_rt_bandwidth (struct rt_bandwidth *rt_b,u64 period,u64 runtime);extern void update_idle_cpu_load (struct rq *this_rq); +extern void task_tick_numa (struct rq *rq,struct task_struct *curr);#ifdef CONFIG_CGROUP_CPUACCT #include <linux/cgroup.h>
Quoted 11 lines · Srikar Dronamraju
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc1-numasched_v2_100912+ #2 Not tainted
--------------------------------------------------------> #0 (&p->pi_lock){-.-.-.}:
[<ffffffff810be478>] __lock_acquire+0x1428/0x1690 [<ffffffff810be782>] lock_acquire+0xa2/0x130 [<ffffffff81551a15>] _raw_spin_lock_irqsave+0x55/0xa0 [<ffffffff81078b08>] task_work_add+0x38/0xb0
Yes. This should be fixed by ac3d0da8 from tip:core/urgent, attached below.
Oleg.
task_work: Make task_work_add() lockless
Change task_work's to use llist-like code to avoid pi_lock in task_work_add(), this makes it useable under rq->lock.
task_work_cancel() and task_work_run() still use pi_lock to synchronize with each other.
(This is in preparation for a deadlock fix.)
--- kernel/task_work.c | 95 ++++++++++++++++++++++++++------------------------- 1 files changed, 48 insertions(+), 47 deletions(-)
kernel/task_work.c +48 -47
@@ -3,25 +3,18 @@#include <linux/tracehook.h> int -task_work_add (struct task_struct *task,struct callback_head *twork,bool notify) +task_work_add (struct task_struct *task,struct callback_head *work,bool notify) { -struct callback_head *last, *first; -unsigned long flags; - +struct callback_head *head;/* * Not inserting the new work if the task has already passed * exit_task_work() is the responisbility of callers. */ -raw_spin_lock_irqsave (&task->pi_lock, flags); - last = task->task_works; - first = last ? last->next : twork; - twork->next = first; -if (last) - last->next = twork; - task->task_works = twork; -raw_spin_unlock_irqrestore (&task->pi_lock, flags); +do { + head =ACCESS_ONCE (task->task_works); + work->next = head; + }while (cmpxchg (&task->task_works, head, work) != head); -/* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */ if (notify)set_notify_resume (task);return 0 ;
@@ -30,52 +23,60 @@ task_work_add(struct task_struct *task, struct callback_head *twork, bool notifystruct callback_head *task_work_cancel (struct task_struct *task,task_work_func_t func) { +struct callback_head **pprev = &task->task_works; +struct callback_head *work =NULL ;unsigned long flags; -struct callback_head *last, *res =NULL ; - +/* +* If cmpxchg() fails we continue without updating pprev. +* Either we raced with task_work_add() which added the +* new entry before this work, we will find it again. Or +* we raced with task_work_run(), *pprev == NULL. +*/ raw_spin_lock_irqsave (&task->pi_lock, flags); - last = task->task_works; -if (last) { -struct callback_head *q = last, *p = q->next; -while (1 ) { -if (p->func == func) { - q->next = p->next; -if (p == last) - task->task_works = q == p ?NULL : q; - res = p; -break ; - } -if (p == last) -break ; - q = p; - p = q->next; - } +while ((work =ACCESS_ONCE (*pprev))) { +read_barrier_depends (); +if (work->func != func) + pprev = &work->next; +else if (cmpxchg (pprev, work, work->next) == work) +break ; }raw_spin_unlock_irqrestore (&task->pi_lock, flags); -return res; + +return work; }void task_work_run (void ) {struct task_struct *task = current; -struct callback_head *p, *q; +struct callback_head *work, *head, *next; -while (1 ) { -raw_spin_lock_irq (&task->pi_lock); - p = task->task_works; - task->task_works =NULL ; -raw_spin_unlock_irq (&task->pi_lock); +for (;;) { + work =xchg (&task->task_works,NULL ); +if (!work) +break ; +/* +* Synchronize with task_work_cancel(). It can't remove +* the first entry == work, cmpxchg(task_works) should +* fail, but it can play with *work and other entries. +*/ +raw_spin_unlock_wait (&task->pi_lock); +smp_mb (); -if (unlikely (!p)) -return ; +/* Reverse the list to run the works in fifo order */ + head =NULL ; +do { + next = work->next; + work->next = head; + head = work; + work = next; + }while (work); - q = p->next;/* head */ - p->next =NULL ;/* cut it */ -while (q) { - p = q->next; - q->func (q); - q = p; + work = head; +do { + next = work->next; + work->func (work); + work = next;cond_resched (); - } + }while (work); } }