Kernel/Locking: Add lock rank tracking per thread to find deadlocks

This change adds a static lock hierarchy / ranking to the Kernel with
the goal of reducing / finding deadlocks when running with SMP enabled.

We have seen quite a few lock ordering deadlocks (locks taken in a
different order, on two different code paths). As we properly annotate
locks in the system, then these facilities will find these locking
protocol violations automatically

The `LockRank` enum documents the various locks in the system and their
rank. The implementation guarantees that a thread holding one or more
locks of a lower rank cannot acquire an additional lock with rank that
is greater or equal to any of the currently held locks.

2 files changed, 72 insertions, 0 deletions

diff --git a/Kernel/Locking/LockRank.cpp b/Kernel/Locking/LockRank.cpp
new file mode 100644
index 0000000000..62efe7400d
--- /dev/null
+++ b/Kernel/Locking/LockRank.cpp
@@ -0,0 +1,29 @@
+/*
+ * Copyright (c) 2021, Brian Gianforcaro <bgianf@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <Kernel/Locking/LockRank.h>
+#include <Kernel/Thread.h>
+
+// Note: These stubs can't be in LockRank.h as that would create
+// a cyclic dependency in the header include graph of the Kernel.
+
+namespace Kernel {
+
+void track_lock_acquire(LockRank rank)
+{
+    auto thread = Thread::current();
+    if (thread && !thread->is_crashing())
+        thread->track_lock_acquire(rank);
+}
+
+void track_lock_release(LockRank rank)
+{
+    auto thread = Thread::current();
+    if (thread && !thread->is_crashing())
+        thread->track_lock_release(rank);
+}
+
+}
diff --git a/Kernel/Locking/LockRank.h b/Kernel/Locking/LockRank.h
new file mode 100644
index 0000000000..38c76f7237
--- /dev/null
+++ b/Kernel/Locking/LockRank.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (c) 2021, Brian Gianforcaro <bgianf@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/EnumBits.h>
+
+namespace Kernel {
+// To catch bugs where locks are taken out of order, we annotate all locks
+// in the kernel with a rank. The rank describes the order in which locks
+// are allowed to be taken. If a lock is acquired, and it is of an incompatible
+// rank with the lock held by the executing thread then the system can detect
+// the lock order violation and respond appropriately (crash with error).
+//
+// A thread holding a lower ranked lock cannot acquire a lock of a greater or equal rank.
+enum class LockRank : int {
+    // Special marker for locks which haven't been annotated yet.
+    // Note: This should be removed once all locks are annotated.
+    None = 0x000,
+
+    // We need to be able to handle page faults from anywhere, so
+    // memory manager locks are our lowest rank lock.
+    MemoryManager = 0x001,
+
+    Interrupts = 0x002,
+
+    FileSystem = 0x004,
+
+    Thread = 0x008,
+
+    // Process locks are the lowest rank, as they normally are taken
+    // first thing when processing syscalls.
+    Process = 0x010,
+};
+
+AK_ENUM_BITWISE_OPERATORS(LockRank);
+
+void track_lock_acquire(LockRank);
+void track_lock_release(LockRank);
+}