Kernel: Deadlock in Processor::exit_trap()

[spholz]

Running TestPThreadPriority with SMP enabled, the system locks up on my laptop (but not on my PC for some reason) due to a circular wait:

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  0x000000200020df4f in Kernel::cpu_flags () at ././Kernel/Arch/x86_64/ASM_wrapper.h:29
#1  Kernel::are_interrupts_enabled () at ././Kernel/Arch/x86_64/ASM_wrapper.h:74
#2  Kernel::ProcessorBase::are_interrupts_enabled () at ././Kernel/Arch/x86_64/Processor.h:219
#3  Kernel::InterruptDisabler::InterruptDisabler (this=0x2013fffd67) at ././Kernel/Interrupts/InterruptDisabler.h:17
#4  0x0000000000000046 in ??? ()
#5  0x000000200020c26d in Kernel::ProcessorBase::leave_critical () at ./Kernel/Arch/Processor.cpp:91
#6  0x0000002000753d0a in Kernel::Processor::smp_process_pending_messages (this=0x2001171300 <initial_kmalloc_memory+606976>) at ./Kernel/Arch/x86_64/Processor.cpp:1005
#7  0x00000020002042b5 in Kernel::ProcessorBase::wait_check () at ././Kernel/Arch/x86_64/Processor.h:262
#8  Kernel::RecursiveSpinlock<(Kernel::LockRank)0>::lock (this=0x20010dc2f0 <Kernel::g_scheduler_lock>) at ././Kernel/Locking/Spinlock.h:79
#9  0x0000002000204357 in Kernel::SpinlockLocker<Kernel::RecursiveSpinlock<(Kernel::LockRank)0> >::SpinlockLocker (this=0x2013fffe20, lock=<optimized out>) at ././Kernel/Locking/Spinlock.h:134
#10 0x000000200070c6db in Kernel::Thread::check_dispatch_pending_signal (this=this@entry=0x200148f640 <initial_kmalloc_memory+3876416>, yield_behavior=yield_behavior@entry=Kernel::YieldBehavior::FlagYield) at ./Kernel/Tasks/Thread.cpp:630
#11 0x000000200020c9ba in Kernel::ProcessorBase::exit_trap (this=0x2001171300 <initial_kmalloc_memory+606976>, trap=...) at ./Kernel/Arch/Processor.cpp:291
#12 0x000000200020f83b in Kernel::exit_trap (trap=0x2013fffed0) at ./Kernel/Arch/TrapFrame.cpp:29
#13 0x00000020007449fe in common_trap_exit ()
#14 0x0000000000000000 in ??? ()

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  Kernel::ProcessorBase::wait_check () at ././Kernel/Arch/x86_64/Processor.h:261
#1  Kernel::RecursiveSpinlock<(Kernel::LockRank)8>::lock (this=0x200148f678 <initial_kmalloc_memory+3876472>) at ././Kernel/Locking/Spinlock.h:79
#2  0x000000200020e619 in Kernel::SpinlockLocker<Kernel::RecursiveSpinlock<(Kernel::LockRank)8> >::SpinlockLocker (this=0x2013fefa88, lock=<optimized out>) at ././Kernel/Locking/Spinlock.h:134
#3  0x0000002000716358 in Kernel::Thread::try_join<Kernel::Thread::JoinBlocker::setup_blocker()::<lambda()> >(struct {...}) (this=0x200148f640 <initial_kmalloc_memory+3876416>, add_blocker=...) at ././Kernel/Tasks/Thread.h:753
#4  0x000000200071655c in Kernel::Thread::JoinBlocker::setup_blocker (this=0x2013fefbf0) at ./Kernel/Tasks/ThreadBlockers.cpp:87
#5  0x0000002000707acb in Kernel::Thread::block_impl (this=this@entry=0x2001340dc0 <initial_kmalloc_memory+2506176>, timeout=..., blocker=...) at ./Kernel/Tasks/Thread.cpp:125
#6  0x0000002000693b7d in Kernel::Thread::block<Kernel::Thread::JoinBlocker, Kernel::Thread&, AK::ErrorOr<void, AK::Error>&, void*&> (this=this@entry=0x2001340dc0 <initial_kmalloc_memory+2506176>, timeout=...) at ././Kernel/Tasks/Thread.h:825
#7  0x0000002000691f3d in Kernel::Process::sys$join_thread (this=<optimized out>, tid=<optimized out>, exit_value=...) at ./Kernel/Syscalls/thread.cpp:161
#8  0x000000200068f835 in Kernel::Syscall::handle (regs=..., function=<optimized out>, arg1=<optimized out>, arg2=<optimized out>, arg3=<optimized out>, arg4=<optimized out>) at ./Kernel/Syscalls/SyscallHandler.cpp:95
#9  0x000000200068fe6c in Kernel::syscall_handler (trap=<optimized out>) at ./Kernel/Syscalls/SyscallHandler.cpp:158
#10 0x0000002000757e0a in syscall_entry () at ./Kernel/Arch/x86_64/SyscallEntry.cpp:25
#11 0x00000003531e702b in ??? ()

CPU#1 first acquired the lock of the thread in ProcessorBase::exit_trap here:

serenity/Kernel/Arch/Processor.cpp

Line 290 in 2390680

SpinlockLocker thread_lock(current_thread->get_lock());

and then the scheduler lock here in Thread::check_dispatch_pending_signal:

serenity/Kernel/Tasks/Thread.cpp

Line 630 in 2390680

SpinlockLocker scheduler_lock(g_scheduler_lock);

CPU#0 first acquired the scheduler lock first in Thread::block_impl here:

serenity/Kernel/Tasks/Thread.cpp

Line 115 in 2390680

SpinlockLocker scheduler_lock(g_scheduler_lock);

and then tries to acquire the thread lock here in Thread::try_join:

serenity/Kernel/Tasks/Thread.h

Line 753 in 2390680

SpinlockLocker lock(m_lock);

This appears to be caused by #26469.

(cc @implicitfield)

[implicitfield]

So basically the issue is that we aren't taking these locks in the same order, I guess? I think the simplest way to fix this would be to just also take the scheduler lock in ProcessorBase::exit_trap right before taking the thread lock (so that the order matches Thread::block_impl). The scheduler lock is recursive, so it shouldn't deadlock with itself in Thread::check_dispatch_pending_signal.

Though this does mean that every instance that ever wants to lock both the scheduler lock and a thread lock will have to do it in this order. Maybe we should have distinct LockRanks for those (but that probably doesn't need to be done to fix this exact issue).

[spholz]

So basically the issue is that we aren't taking these locks in the same order, I guess? I think the simplest way to fix this would be to just also take the scheduler lock in ProcessorBase::exit_trap right before taking the thread lock (so that the order matches Thread::block_impl). The scheduler lock is recursive, so it shouldn't deadlock with itself in Thread::check_dispatch_pending_signal.

Yeah, taking the scheduler lock first should solve this issue. I could honestly have done that change myself, but I still wanted to hear your opinion.

Though this does mean that every instance that ever wants to lock both the scheduler lock and a thread lock will have to do it in this order. Maybe we should have distinct LockRanks for those (but that probably doesn't need to be done to fix this exact issue).

I also fixed a similar bug in the new WaitQueue implementation. g_scheduler_lock should likely have a pretty high lock rank. (Note that lock rank enforcement is off by default.)