Kernel: Cache Custody objects (weakly) to avoid expensive reconstruction

This patch adds a (spinlock-protected) custody cache. It's a simple
intrusive list containing all currently live custody objects.

This allows us to re-use existing custodies instead of creating them
again and again.

This gives a pretty decent performance improvement on "find /" :^)

2 files changed, 52 insertions, 8 deletions

diff --git a/Kernel/FileSystem/Custody.cpp b/Kernel/FileSystem/Custody.cpp
index 8eb00b56e3..d211c37684 100644
--- a/Kernel/FileSystem/Custody.cpp
+++ b/Kernel/FileSystem/Custody.cpp
@@ -4,23 +4,59 @@
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
+#include <AK/Singleton.h>
 #include <AK/StringBuilder.h>
 #include <AK/StringView.h>
 #include <AK/Vector.h>
 #include <Kernel/FileSystem/Custody.h>
 #include <Kernel/FileSystem/Inode.h>
+#include <Kernel/Locking/SpinLockProtectedValue.h>
 
 namespace Kernel {
 
+static Singleton<SpinLockProtectedValue<Custody::AllCustodiesList>> s_all_custodies;
+
+static SpinLockProtectedValue<Custody::AllCustodiesList>& all_custodies()
+{
+    return s_all_custodies;
+}
+
 KResultOr<NonnullRefPtr<Custody>> Custody::try_create(Custody* parent, StringView name, Inode& inode, int mount_flags)
 {
-    auto name_kstring = KString::try_create(name);
-    if (!name_kstring)
-        return ENOMEM;
-    auto custody = adopt_ref_if_nonnull(new (nothrow) Custody(parent, name_kstring.release_nonnull(), inode, mount_flags));
-    if (!custody)
-        return ENOMEM;
-    return custody.release_nonnull();
+    return all_custodies().with([&](auto& all_custodies) -> KResultOr<NonnullRefPtr<Custody>> {
+        for (Custody& custody : all_custodies) {
+            if (custody.parent() == parent
+                && custody.name() == name
+                && &custody.inode() == &inode
+                && custody.mount_flags() == mount_flags) {
+                return custody;
+            }
+        }
+
+        auto name_kstring = KString::try_create(name);
+        if (!name_kstring)
+            return ENOMEM;
+        auto custody = adopt_ref_if_nonnull(new (nothrow) Custody(parent, name_kstring.release_nonnull(), inode, mount_flags));
+        if (!custody)
+            return ENOMEM;
+
+        all_custodies.append(*custody);
+        return custody.release_nonnull();
+    });
+}
+
+bool Custody::unref() const
+{
+    bool should_destroy = all_custodies().with([&](auto&) {
+        if (deref_base())
+            return false;
+        m_all_custodies_list_node.remove();
+        return true;
+    });
+
+    if (should_destroy)
+        delete this;
+    return should_destroy;
 }
 
 Custody::Custody(Custody* parent, NonnullOwnPtr<KString> name, Inode& inode, int mount_flags)
diff --git a/Kernel/FileSystem/Custody.h b/Kernel/FileSystem/Custody.h
index ca54e9e35c..9e7a81fc87 100644
--- a/Kernel/FileSystem/Custody.h
+++ b/Kernel/FileSystem/Custody.h
@@ -6,6 +6,7 @@
 
 #pragma once
 
+#include <AK/IntrusiveList.h>
 #include <AK/RefCounted.h>
 #include <AK/RefPtr.h>
 #include <AK/String.h>
@@ -18,9 +19,11 @@ namespace Kernel {
 
 // FIXME: Custody needs some locking.
 
-class Custody : public RefCounted<Custody> {
+class Custody : public RefCountedBase {
     MAKE_SLAB_ALLOCATED(Custody)
 public:
+    bool unref() const;
+
     static KResultOr<NonnullRefPtr<Custody>> try_create(Custody* parent, StringView name, Inode&, int mount_flags);
 
     ~Custody();
@@ -43,6 +46,11 @@ private:
     NonnullOwnPtr<KString> m_name;
     NonnullRefPtr<Inode> m_inode;
     int m_mount_flags { 0 };
+
+    mutable IntrusiveListNode<Custody> m_all_custodies_list_node;
+
+public:
+    using AllCustodiesList = IntrusiveList<Custody, RawPtr<Custody>, &Custody::m_all_custodies_list_node>;
 };
 
 }