fs: lockup on rename_mutex in fs/dcache.c:1035
Hi all,
While fuzzing with trinity inside a KVM tools guest running the latest -next kernel, I've stumbled on the following spew:
[ 6172.870045] =============================================
[ 6172.870045] [ INFO: possible recursive locking detected ]
[ 6172.870045] 3.18.0-rc1-next-20141023-sasha-00036-g4dcabd5 #1415 Not tainted
[ 6172.870045] ---------------------------------------------
[ 6172.870045] trinity-c55/12752 is trying to acquire lock:
[ 6172.870045] (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045]
[ 6172.870045] but task is already holding lock:
[ 6172.870045] (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045]
[ 6172.870045] other info that might help us debug this:
[ 6172.900904] FAULT_INJECTION: forcing a failure
[ 6172.870045] Possible unsafe locking scenario:
[ 6172.870045]
[ 6172.870045] CPU0
[ 6172.870045] ----
[ 6172.870045] lock(rename_lock);
[ 6172.870045] lock(rename_lock);
[ 6172.870045]
[ 6172.870045] *** DEADLOCK ***
[ 6172.870045]
[ 6172.870045] May be due to missing lock nesting notation
[ 6172.870045]
[ 6172.870045] 1 lock held by trinity-c55/12752:
[ 6172.870045] #0: (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045]
[ 6172.870045] stack backtrace:
[ 6172.870045] CPU: 1 PID: 12752 Comm: trinity-c55 Not tainted 3.18.0-rc1-next-20141023-sasha-00036-g4dcabd5 #1415
[ 6172.870045] ffff88070945b000 0000000000000000 ffffffffb6312fd0 ffff8806d69ff728
[ 6172.870045] ffffffffa8ff75ca 0000000000000011 ffffffffb6312fd0 ffff8806d69ff828
[ 6172.870045] ffffffff9f3a012b ffff880107fd76c0 ffff880107fd76c0 0000000000000001
[ 6172.870045] Call Trace:
[ 6172.870045] dump_stack (lib/dump_stack.c:52)
[ 6172.870045] validate_chain.isra.10 (kernel/locking/lockdep.c:2134)
[ 6172.870045] ? kvm_clock_read (./arch/x86/include/asm/preempt.h:90 arch/x86/kernel/kvmclock.c:86)
[ 6172.870045] ? sched_clock_cpu (kernel/sched/clock.c:311)
[ 6172.870045] __lock_acquire (kernel/locking/lockdep.c:3184)
[ 6172.870045] lock_acquire (./arch/x86/include/asm/current.h:14 kernel/locking/lockdep.c:3604)
[ 6172.870045] ? d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045] ? put_lock_stats.isra.7 (./arch/x86/include/asm/preempt.h:98 kernel/locking/lockdep.c:254)
[ 6172.870045] _raw_spin_lock (include/linux/spinlock_api_smp.h:143 kernel/locking/spinlock.c:151)
[ 6172.870045] ? d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045] d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045] ? d_walk (fs/dcache.c:1087)
[ 6172.870045] ? d_drop (fs/dcache.c:1336)
[ 6172.870045] ? select_collect (fs/dcache.c:1323)
[ 6172.870045] d_invalidate (fs/dcache.c:1381)
[ 6172.870045] lookup_fast (fs/namei.c:1440)
[ 6172.870045] ? _raw_spin_unlock (./arch/x86/include/asm/preempt.h:98 include/linux/spinlock_api_smp.h:152 kernel/locking/spinlock.c:183)
[ 6172.870045] ? lockref_put_or_lock (lib/lockref.c:135)
[ 6172.870045] ? dput (fs/dcache.c:626)
[ 6172.870045] walk_component (fs/namei.c:1545)
[ 6172.870045] ? security_inode_permission (security/security.c:573)
[ 6172.870045] ? __inode_permission (fs/namei.c:418)
[ 6172.870045] link_path_walk (fs/namei.c:1805)
[ 6172.870045] ? __this_cpu_preempt_check (lib/smp_processor_id.c:63)
[ 6172.870045] ? trace_hardirqs_on_caller (kernel/locking/lockdep.c:2559 kernel/locking/lockdep.c:2601)
[ 6172.870045] ? getname_flags (fs/namei.c:145)
[ 6172.870045] path_lookupat (fs/namei.c:1956)
[ 6172.870045] ? kmem_cache_alloc (include/linux/rcupdate.h:479 include/trace/events/kmem.h:53 mm/slub.c:2463)
[ 6172.870045] ? getname_flags (fs/namei.c:145)
[ 6172.870045] filename_lookup (fs/namei.c:2000)
[ 6172.870045] user_path_at_empty (fs/namei.c:2151)
[ 6172.870045] ? preempt_count_sub (kernel/sched/core.c:2662)
[ 6172.870045] user_path_at (fs/namei.c:2162)
[ 6172.870045] vfs_fstatat (fs/stat.c:106)
[ 6172.870045] SYSC_newlstat (fs/stat.c:284)
[ 6172.870045] ? syscall_trace_enter_phase2 (arch/x86/kernel/ptrace.c:1598)
[ 6172.870045] ? tracesys_phase2 (arch/x86/kernel/entry_64.S:518)
[ 6172.870045] SyS_newlstat (fs/stat.c:277)
[ 6172.870045] tracesys_phase2 (arch/x86/kernel/entry_64.S:529)The machine proceeded to actually lock up, so this isn't a false positive.
Thanks,
Sasha
Al Viro
maintainerQuoted 5 lines · Sasha Levin
[ 6172.870045] trinity-c55/12752 is trying to acquire lock:
[ 6172.870045] (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)
[ 6172.870045]
[ 6172.870045] but task is already holding lock:
[ 6172.870045] (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035)Umm... So we either have left d_walk() without dropping rename_lock, or we have called d_walk() from something called from d_walk()? And the trace would seem to point towards the former...
Ouch. For that to happen, we would need to
* get to rename_retry with retry being true
* after that get D_WALK_NORETRY from enter()
* somehow get to rename_retry *again*
Moreover, we couldn't get there via
if (need_seqretry(&rename_lock, seq)) {
spin_unlock(&this_parent->d_lock);
goto rename_retry;
- seq is 1 by that point, and need_seqretry() returns 0 in that case. IOW,
it must have been this:
/*
* might go back up the wrong parent if we have had a rename
* or deletion
*/
if (this_parent != child->d_parent ||
(child->d_flags & DCACHE_DENTRY_KILLED) ||
need_seqretry(&rename_lock, seq)) {
spin_unlock(&this_parent->d_lock);
rcu_read_unlock();
goto rename_retry;
}
And we had been holding rename_lock in that walk, so d_move() should've
been excluded... Which leaves us with
(child->d_flags & DCACHE_DENTRY_KILLED)
being true... Hrm. AFAICS, it *is* possible to hit that one - just have
the last reference to child dropped between
spin_unlock(&child->d_lock);
and
spin_lock(&this_parent->d_lock);a few lines above. And yes, if that happens we are in shit - rename_retry will see retry being false and return, without noticing that on this pass we had been holding rename_lock. Easily fixed, fortunately - delta below ought to take care of that...
Comments? AFAICS, it's -stable fodder, the bug going all way back to at least 3.7...
fs/dcache.c +2 -1
@@ -1114,12 +1114,13 @@ resume: out_unlock:spin_unlock (&this_parent->d_lock); +out:done_seqretry (&rename_lock, seq);return ; rename_retry:if (!retry) -return ; + goto out; seq =1 ; goto again; }
Quoted 4 lines · Sasha Levin
Hi all,
While fuzzing with trinity inside a KVM tools guest running the latest -next kernel, I've stumbled on the following spew:
Weird. I took a quick look and I don't see any changes in d_walk that in Al's tree or in Linus's kernel for years.
Has read_seqbegin_or_lock changed somewhere?
Quoted 1 line
From a quick reading of the code it simply isn't possible for
d_walkto
take the lock twice short of memory corruption. And the fact that the code has not changed in years seems to suggest it isn't the obvious cause of d_walk talking the rename_lock twice.
Eric
Quoted 77 lines
[ 6172.870045] ============================================= [ 6172.870045] [ INFO: possible recursive locking detected ] [ 6172.870045] 3.18.0-rc1-next-20141023-sasha-00036-g4dcabd5 #1415 Not tainted [ 6172.870045] --------------------------------------------- [ 6172.870045] trinity-c55/12752 is trying to acquire lock: [ 6172.870045] (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035) [ 6172.870045] [ 6172.870045] but task is already holding lock: [ 6172.870045] (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035) [ 6172.870045] [ 6172.870045] other info that might help us debug this: [ 6172.900904] FAULT_INJECTION: forcing a failure [ 6172.870045] Possible unsafe locking scenario: [ 6172.870045] [ 6172.870045] CPU0 [ 6172.870045] ---- [ 6172.870045] lock(rename_lock); [ 6172.870045] lock(rename_lock); [ 6172.870045] [ 6172.870045] *** DEADLOCK *** [ 6172.870045] [ 6172.870045] May be due to missing lock nesting notation [ 6172.870045] [ 6172.870045] 1 lock held by trinity-c55/12752: [ 6172.870045] #0: (rename_lock){+.+...}, at: d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035) [ 6172.870045] [ 6172.870045] stack backtrace: [ 6172.870045] CPU: 1 PID: 12752 Comm: trinity-c55 Not tainted 3.18.0-rc1-next-20141023-sasha-00036-g4dcabd5 #1415 [ 6172.870045] ffff88070945b000 0000000000000000 ffffffffb6312fd0 ffff8806d69ff728 [ 6172.870045] ffffffffa8ff75ca 0000000000000011 ffffffffb6312fd0 ffff8806d69ff828 [ 6172.870045] ffffffff9f3a012b ffff880107fd76c0 ffff880107fd76c0 0000000000000001 [ 6172.870045] Call Trace: [ 6172.870045] dump_stack (lib/dump_stack.c:52) [ 6172.870045] validate_chain.isra.10 (kernel/locking/lockdep.c:2134) [ 6172.870045] ? kvm_clock_read (./arch/x86/include/asm/preempt.h:90 arch/x86/kernel/kvmclock.c:86) [ 6172.870045] ? sched_clock_cpu (kernel/sched/clock.c:311) [ 6172.870045] __lock_acquire (kernel/locking/lockdep.c:3184) [ 6172.870045] lock_acquire (./arch/x86/include/asm/current.h:14 kernel/locking/lockdep.c:3604) [ 6172.870045] ? d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035) [ 6172.870045] ? put_lock_stats.isra.7 (./arch/x86/include/asm/preempt.h:98 kernel/locking/lockdep.c:254) [ 6172.870045] _raw_spin_lock (include/linux/spinlock_api_smp.h:143 kernel/locking/spinlock.c:151) [ 6172.870045] ? d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035) [ 6172.870045] d_walk (include/linux/spinlock.h:309 fs/dcache.c:1035) [ 6172.870045] ? d_walk (fs/dcache.c:1087) [ 6172.870045] ? d_drop (fs/dcache.c:1336) [ 6172.870045] ? select_collect (fs/dcache.c:1323) [ 6172.870045] d_invalidate (fs/dcache.c:1381) [ 6172.870045] lookup_fast (fs/namei.c:1440) [ 6172.870045] ? _raw_spin_unlock (./arch/x86/include/asm/preempt.h:98 include/linux/spinlock_api_smp.h:152 kernel/locking/spinlock.c:183) [ 6172.870045] ? lockref_put_or_lock (lib/lockref.c:135) [ 6172.870045] ? dput (fs/dcache.c:626) [ 6172.870045] walk_component (fs/namei.c:1545) [ 6172.870045] ? security_inode_permission (security/security.c:573) [ 6172.870045] ? __inode_permission (fs/namei.c:418) [ 6172.870045] link_path_walk (fs/namei.c:1805) [ 6172.870045] ? __this_cpu_preempt_check (lib/smp_processor_id.c:63) [ 6172.870045] ? trace_hardirqs_on_caller (kernel/locking/lockdep.c:2559 kernel/locking/lockdep.c:2601) [ 6172.870045] ? getname_flags (fs/namei.c:145) [ 6172.870045] path_lookupat (fs/namei.c:1956) [ 6172.870045] ? kmem_cache_alloc (include/linux/rcupdate.h:479 include/trace/events/kmem.h:53 mm/slub.c:2463) [ 6172.870045] ? getname_flags (fs/namei.c:145) [ 6172.870045] filename_lookup (fs/namei.c:2000) [ 6172.870045] user_path_at_empty (fs/namei.c:2151) [ 6172.870045] ? preempt_count_sub (kernel/sched/core.c:2662) [ 6172.870045] user_path_at (fs/namei.c:2162) [ 6172.870045] vfs_fstatat (fs/stat.c:106) [ 6172.870045] SYSC_newlstat (fs/stat.c:284) [ 6172.870045] ? syscall_trace_enter_phase2 (arch/x86/kernel/ptrace.c:1598) [ 6172.870045] ? tracesys_phase2 (arch/x86/kernel/entry_64.S:518) [ 6172.870045] SyS_newlstat (fs/stat.c:277) [ 6172.870045] tracesys_phase2 (arch/x86/kernel/entry_64.S:529)The machine proceeded to actually lock up, so this isn't a false positive.
Thanks,
Sasha
Al Viro
maintainerQuoted 10 lines · Eric W. Biederman
Quoted 4 lines · Sasha Levin
Hi all,
While fuzzing with trinity inside a KVM tools guest running the latest -next kernel, I've stumbled on the following spew:
Weird. I took a quick look and I don't see any changes in
d_walkthat in Al's tree or in Linus's kernel for years.
Quoted 6 lines
Has
read_seqbegin_or_lockchanged somewhere?Quoted 1 line
From a quick reading of the code it simply isn't possible for
d_walktotake the lock twice short of memory corruption. And the fact that the code has not changed in years seems to suggest it isn't the obvious cause of
d_walktalking therename_locktwice.
It is a fairly obvious case of d_walk() forgetting to drop rename_lock. See upthread for analysis and (hopefully) a fix.
Al Viro
maintainerQuoted 7 lines · Al Viro
Quoted 4 lines
Quoted 1 line
From a quick reading of the code it simply isn't possible for
d_walktotake the lock twice short of memory corruption. And the fact that the code has not changed in years seems to suggest it isn't the obvious cause of
d_walktalking therename_locktwice.It is a fairly obvious case of
d_walk()forgetting to droprename_lock. See upthread for analysis and (hopefully) a fix.
... except that it's not a full fix. If we get there that way with retry being true, we will immediately deadlock at again:...
Which might very well has happened in this case - i.e. it might be a single call of d_walk() taking the sucker twice that way.
Hmm... Actually, the comment in there is simply wrong - if the child got killed between unlocking the child and locking the parent, it's not ascending to the wrong parent, it's having no way to find the next sibling.
OK, so basically it came from Nick's "fs: dcache avoid starvation in dcache multi-step operations" and mistake was in the assumption that once we hold rename_lock, nothing is going to need rename_retry. Which isn't true - dentry_kill() on child while we are trying to get ->d_lock on parent requires a restart and that isn't excluded by rename_lock at all.
Well, brute-force fix would be this, but I wonder if it's going to create livelocks...
fs/dcache.c +1 -0
@@ -1118,6 +1118,7 @@ out_unlock:return ; rename_retry: +done_seqretry (&rename_lock, seq);if (!retry)return ; seq =1 ;
Al Viro
maintainer[context for Linus]
Fuzzer has triggered deadlock in d_walk() with rename_lock taken twice. AFAICS, the plausible scenario is
(child->d_flags & DCACHE_DENTRY_KILLED) ||
triggering while ascending to parent, on the pass with rename_lock already held exclusive. In that case we go to rename_retry and either return without unlocking rename_lock, or try to take in exclusive one more time, again without unlocking it first.
Quoted 31 lines
Hmm... Actually, the comment in there is simply wrong - if the child got killed between unlocking the child and locking the parent, it's not ascending to the wrong parent, it's having no way to find the next sibling.
OK, so basically it came from Nick's "fs: dcache avoid starvation in dcache multi-step operations" and mistake was in the assumption that once we hold
rename_lock, nothing is going to needrename_retry. Which isn't true -dentry_kill()on child while we are trying to get ->d_lock on parent requires a restart and that isn't excluded byrename_lockat all.Well, brute-force fix would be this, but I wonder if it's going to create livelocks...
fs/dcache.c +1
-1@@ -1118,6 +1118,7 @@ out_unlock:return ; rename_retry: +done_seqretry (&rename_lock, seq);if (!retry)return ; seq =1 ; --To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 9 lines · Al Viro
[context for Linus]
Fuzzer has triggered deadlock in
d_walk()withrename_locktaken twice. AFAICS, the plausible scenario is(child->d_flags & DCACHE_DENTRY_KILLED) ||triggering while ascending to parent, on the pass with
rename_lockalready held exclusive. In that case we go torename_retryand either return without unlockingrename_lock, or try to take in exclusive one more time, again without unlocking it first.
Your patch looks fine, and I don't think we can livelock - because we always set 'seq' to 1 if we retry, and that causes us to get the exclusive lock, so we'd better not then enter the retry loop again. Although I guess not only renames cause it - looks like we get to that mis-named "rename_retry" for a deletion too according to the comment. Although I'm not sure that comment is correct - I don't think we change d_parent for deletes, do we?
So at a quick glance, the one-liner patch looks fine. That said, I really detest how that code is written. Especially if the rename_retry really can only happen once, I get the feeling that we would be *much* better off doing this explicitly with a wrapper function, and do something like
void d_walk(,..)
{
/* Try non-exclusive first */
seq = read_seqbegin(lock);
retry = __d_walk(.. seq);
if (retry) {
read_seqlock_excl(lock);
// lock->seqcount is now guaranteed stable
retry = __d_walk(.. lock->seqcount);
read_sequnlock_excl(lock);
WARN_ON_ONCE(retry, "Really?");
}
}or whatever. But maybe I'm missing some reason why the above is just crazy, and I'm a moron. Entirely possible.
Linus
Al Viro
maintainerQuoted 8 lines · Linus Torvalds
On Sat, Oct 25, 2014 at 8:57 PM, Al Viro <[email protected]> wrote:
Your patch looks fine, and I don't think we can livelock - because we always set 'seq' to 1 if we retry, and that causes us to get the exclusive lock, so we'd better not then enter the retry loop again. Although I guess not only renames cause it - looks like we get to that mis-named "rename_retry" for a deletion too according to the comment. Although I'm not sure that comment is correct - I don't think we changed_parentfor deletes, do we?
The comment is not correct. dentry_kill() won't screw the pointer to parent; it will, however, screw the pointer to next sibling.
It used to screw the pointer to parent (which is what the first part of condition was about). After Nick's series back in January 2011 that has stopped being true. However, dentry_kill() does list_del(&dentry->d_u.d_child). Which means that we can't continue past that point if it has happened. Trond has noticed the breakage a bit later and added explicit check for ->d_flags, but the damage was more extensive - Nick had missed the restarts-on-killed logics hidden in the check for changed ->d_parent and assumed that it's all about renames, meaning that once rename_lock has been taken exclusive we won't have restarts at all. With restart-on-killed restored that wasn't true anymore, invalidating the assumption that we only get to rename_retry without rename_lock held exclusive. With deadlocks happening if we ever get there on such pass.
We used to have several copies of that logics, before it all got consolidated into d_walk(), which probably contributed to the mess...
BTW, the first part of condition (->d_parent hasn't changed since before the "unlock child, lock parent" sequence) is really pointless these days - check for rename_lock will fail if ->d_parent has changed...
Al Viro
maintainerQuoted 16 lines · Al Viro
The comment is not correct.
dentry_kill()won't screw the pointer to parent; it will, however, screw the pointer to next sibling.It used to screw the pointer to parent (which is what the first part of condition was about). After Nick's series back in January 2011 that has stopped being true. However,
dentry_kill()doeslist_del(&dentry->d_u.d_child). Which means that we can't continue past that point if it has happened. Trond has noticed the breakage a bit later and added explicit check for ->d_flags, but the damage was more extensive - Nick had missed the restarts-on-killed logics hidden in the check for changed ->d_parent and assumed that it's all about renames, meaning that oncerename_lockhas been taken exclusive we won't have restarts at all. With restart-on-killed restored that wasn't true anymore, invalidating the assumption that we only get torename_retrywithoutrename_lockheld exclusive. With deadlocks happening if we ever get there on such pass.
Actually, it's even worse than just list_del() possibly screwing .next - that could be worked around by use of __list_del() (and skipping them until we come to one that isn't marked DCACHE_DENTRY_KILLED). Note that d_child shares memory with d_rcu, and _that_ is really nasty - if __dentry_kill() has progressed to dentry_free(), we have ->d_u.d_child.next hopelessly trashed.
OTOH, we could make d_rcu share memory with d_alias instead. Hrm... OK, then we'd have
rcu_read_lock();
ascend:
if (this_parent != parent) {
struct dentry *child = this_parent;
this_parent = child->d_parent;
spin_unlock(&child->d_lock);
spin_lock(&this_parent->d_lock);
if (need_seqretry(&rename_lock, seq)) {
spin_unlock(&this_parent->d_lock);
rcu_read_unlock();
goto rename_retry;
}
next = child->d_child.next;
while (unlikely(child->d_flags & DCACHE_DENTRY_KILLED)) {
if (next == &this_parent.d_subdirs)
goto ascend;
child = list_entry(next, struct dentry, d_child);
next = next->next;
}
rcu_read_unlock();
goto resume;
}
rcu_read_unlock();
if (need_seqretry(&rename_lock, seq)) {
spin_unlock(&this_parent->d_lock);
goto rename_retry;
}in d_walk(), __list_del() instead of list_del() in __dentry_kill(), d_u.d_child turning into d_child everywhere, while d_alias turns into d_u.d_alias...
It looks like that way we would get no retries on the second pass. Comments?
Quoted 5 lines · Al Viro
.. snip ..
ind_walk(),__list_del()instead oflist_del()in__dentry_kill(), d_u.d_child turning intod_childeverywhere, whiled_aliasturns into d_u.d_alias...It looks like that way we would get no retries on the second pass. Comments?
Since I missed the whole issue with d_child.next, I'm not sure any comments from me would be helpful.
It does sound like trying to be more careful with d_child and using d_alias instead is a good idea. d_alias is only used under the dentry lock, and not in any horribly subtle situations, right? So that sounds like a good change regardless of this particular fix - making the union happen in a less nasty place..
Linus
Al Viro
maintainerQuoted 7 lines · Linus Torvalds
Quoted 5 lines · Al Viro
.. snip ..
ind_walk(),__list_del()instead oflist_del()in__dentry_kill(), d_u.d_child turning intod_childeverywhere, whiled_aliasturns into d_u.d_alias...It looks like that way we would get no retries on the second pass. Comments?
Quoted 8 lines
Since I missed the whole issue with d_child.next, I'm not sure any comments from me would be helpful.
It does sound like trying to be more careful with
d_childand usingd_aliasinstead is a good idea.d_aliasis only used under the dentry lock, and not in any horribly subtle situations, right? So that sounds like a good change regardless of this particular fix - making the union happen in a less nasty place..
OK... See vfs.git#experimental-d_walk - the first commit there moves d_rcu from d_child to d_alias, the second is basically "skip the killed siblings rather than restarting the tree walk".