Kernel: Implement unveil() as a prefix-tree

Fixes #4530.

7 files changed, 106 insertions, 58 deletions

diff --git a/Kernel/FileSystem/ProcFS.cpp b/Kernel/FileSystem/ProcFS.cpp
index f85d544b10..3d281305c2 100644
--- a/Kernel/FileSystem/ProcFS.cpp
+++ b/Kernel/FileSystem/ProcFS.cpp
@@ -634,18 +634,20 @@ static OwnPtr<KBuffer> procfs$pid_unveil(InodeIdentifier identifier)
     KBufferBuilder builder;
     JsonArraySerializer array { builder };
     for (auto& unveiled_path : process->unveiled_paths()) {
+        if (!unveiled_path.was_explicitly_unveiled())
+            continue;
         auto obj = array.add_object();
-        obj.add("path", unveiled_path.path);
+        obj.add("path", unveiled_path.path());
         StringBuilder permissions_builder;
-        if (unveiled_path.permissions & UnveiledPath::Access::Read)
+        if (unveiled_path.permissions() & UnveilAccess::Read)
             permissions_builder.append('r');
-        if (unveiled_path.permissions & UnveiledPath::Access::Write)
+        if (unveiled_path.permissions() & UnveilAccess::Write)
             permissions_builder.append('w');
-        if (unveiled_path.permissions & UnveiledPath::Access::Execute)
+        if (unveiled_path.permissions() & UnveilAccess::Execute)
             permissions_builder.append('x');
-        if (unveiled_path.permissions & UnveiledPath::Access::CreateOrRemove)
+        if (unveiled_path.permissions() & UnveilAccess::CreateOrRemove)
             permissions_builder.append('c');
-        if (unveiled_path.permissions & UnveiledPath::Access::Browse)
+        if (unveiled_path.permissions() & UnveilAccess::Browse)
             permissions_builder.append('b');
         obj.add("permissions", permissions_builder.to_string());
     }
diff --git a/Kernel/FileSystem/VirtualFileSystem.cpp b/Kernel/FileSystem/VirtualFileSystem.cpp
index 2aa4663f63..aacd49f6a1 100644
--- a/Kernel/FileSystem/VirtualFileSystem.cpp
+++ b/Kernel/FileSystem/VirtualFileSystem.cpp
@@ -820,21 +820,16 @@ Custody& VFS::root_custody()
     return *m_root_custody;
 }
 
-const UnveiledPath* VFS::find_matching_unveiled_path(StringView path)
+const UnveilNode* VFS::find_matching_unveiled_path(StringView path)
 {
-    for (auto& unveiled_path : Process::current()->unveiled_paths()) {
-        if (path == unveiled_path.path)
-            return &unveiled_path;
-        if (!path.starts_with(unveiled_path.path))
-            continue;
-        // /foo/ and /foo/bar
-        if (unveiled_path.path.ends_with('/'))
-            return &unveiled_path;
-        // /foo and /foo/bar
-        if (path.length() > unveiled_path.path.length() && path[unveiled_path.path.length()] == '/')
-            return &unveiled_path;
-    }
-    return nullptr;
+    auto& unveil_root = Process::current()->unveiled_paths();
+    if (unveil_root.is_empty())
+        return nullptr;
+
+    LexicalPath lexical_path { path };
+    auto& path_parts = lexical_path.parts();
+    auto& last_matching_node = unveil_root.traverse_until_last_accessible_node(path_parts.begin(), path_parts.end());
+    return &last_matching_node;
 }
 
 KResult VFS::validate_path_against_process_veil(StringView path, int options)
@@ -856,14 +851,14 @@ KResult VFS::validate_path_against_process_veil(StringView path, int options)
     }
 
     if (options & O_CREAT) {
-        if (!(unveiled_path->permissions & UnveiledPath::Access::CreateOrRemove)) {
+        if (!(unveiled_path->permissions() & UnveilAccess::CreateOrRemove)) {
             dbg() << "Rejecting path '" << path << "' since it hasn't been unveiled with 'c' permission.";
             dump_backtrace();
             return KResult(-EACCES);
         }
     }
     if (options & O_UNLINK_INTERNAL) {
-        if (!(unveiled_path->permissions & UnveiledPath::Access::CreateOrRemove)) {
+        if (!(unveiled_path->permissions() & UnveilAccess::CreateOrRemove)) {
             dbg() << "Rejecting path '" << path << "' for unlink since it hasn't been unveiled with 'c' permission.";
             dump_backtrace();
             return KResult(-EACCES);
@@ -872,13 +867,13 @@ KResult VFS::validate_path_against_process_veil(StringView path, int options)
     }
     if (options & O_RDONLY) {
         if (options & O_DIRECTORY) {
-            if (!(unveiled_path->permissions & (UnveiledPath::Access::Read | UnveiledPath::Access::Browse))) {
+            if (!(unveiled_path->permissions() & (UnveilAccess::Read | UnveilAccess::Browse))) {
                 dbg() << "Rejecting path '" << path << "' since it hasn't been unveiled with 'r' or 'b' permissions.";
                 dump_backtrace();
                 return KResult(-EACCES);
             }
         } else {
-            if (!(unveiled_path->permissions & UnveiledPath::Access::Read)) {
+            if (!(unveiled_path->permissions() & UnveilAccess::Read)) {
                 dbg() << "Rejecting path '" << path << "' since it hasn't been unveiled with 'r' permission.";
                 dump_backtrace();
                 return KResult(-EACCES);
@@ -886,14 +881,14 @@ KResult VFS::validate_path_against_process_veil(StringView path, int options)
         }
     }
     if (options & O_WRONLY) {
-        if (!(unveiled_path->permissions & UnveiledPath::Access::Write)) {
+        if (!(unveiled_path->permissions() & UnveilAccess::Write)) {
             dbg() << "Rejecting path '" << path << "' since it hasn't been unveiled with 'w' permission.";
             dump_backtrace();
             return KResult(-EACCES);
         }
     }
     if (options & O_EXEC) {
-        if (!(unveiled_path->permissions & UnveiledPath::Access::Execute)) {
+        if (!(unveiled_path->permissions() & UnveilAccess::Execute)) {
             dbg() << "Rejecting path '" << path << "' since it hasn't been unveiled with 'x' permission.";
             dump_backtrace();
             return KResult(-EACCES);
diff --git a/Kernel/FileSystem/VirtualFileSystem.h b/Kernel/FileSystem/VirtualFileSystem.h
index f3f2ddad76..1f38b4ce6c 100644
--- a/Kernel/FileSystem/VirtualFileSystem.h
+++ b/Kernel/FileSystem/VirtualFileSystem.h
@@ -37,13 +37,13 @@
 #include <Kernel/FileSystem/InodeIdentifier.h>
 #include <Kernel/FileSystem/InodeMetadata.h>
 #include <Kernel/KResult.h>
+#include <Kernel/UnveilNode.h>
 
 namespace Kernel {
 
 class Custody;
 class Device;
 class FileDescription;
-struct UnveiledPath;
 
 struct UidAndGid {
     uid_t uid;
@@ -122,7 +122,7 @@ public:
 private:
     friend class FileDescription;
 
-    const UnveiledPath* find_matching_unveiled_path(StringView path);
+    const UnveilNode* find_matching_unveiled_path(StringView path);
     KResult validate_path_against_process_veil(StringView path, int options);
 
     bool is_vfs_root(InodeIdentifier) const;
diff --git a/Kernel/Process.h b/Kernel/Process.h
index 7054cb1753..50c7e30210 100644
--- a/Kernel/Process.h
+++ b/Kernel/Process.h
@@ -44,6 +44,7 @@
 #include <Kernel/Thread.h>
 #include <Kernel/ThreadTracer.h>
 #include <Kernel/UnixTypes.h>
+#include <Kernel/UnveilNode.h>
 #include <Kernel/VM/RangeAllocator.h>
 #include <LibC/signal_numbers.h>
 
@@ -91,19 +92,6 @@ enum class VeilState {
     Locked,
 };
 
-struct UnveiledPath {
-    enum Access {
-        Read = 1,
-        Write = 2,
-        Execute = 4,
-        CreateOrRemove = 8,
-        Browse = 16,
-    };
-
-    String path;
-    unsigned permissions { 0 };
-};
-
 class Process
     : public RefCounted<Process>
     , public InlineLinkedListNode<Process>
@@ -498,7 +486,7 @@ public:
     {
         return m_veil_state;
     }
-    const Vector<UnveiledPath>& unveiled_paths() const
+    const UnveilNode& unveiled_paths() const
     {
         return m_unveiled_paths;
     }
@@ -652,7 +640,7 @@ private:
     u32 m_execpromises { 0 };
 
     VeilState m_veil_state { VeilState::None };
-    Vector<UnveiledPath> m_unveiled_paths;
+    UnveilNode m_unveiled_paths { "/", { "/" } };
 
     WaitQueue& futex_queue(Userspace<const i32*>);
     HashMap<u32, OwnPtr<WaitQueue>> m_futex_queues;
diff --git a/Kernel/Syscalls/fork.cpp b/Kernel/Syscalls/fork.cpp
index cb215a42b2..c7bc029a55 100644
--- a/Kernel/Syscalls/fork.cpp
+++ b/Kernel/Syscalls/fork.cpp
@@ -46,7 +46,7 @@ pid_t Process::sys$fork(RegisterState& regs)
     child->m_promises = m_promises;
     child->m_execpromises = m_execpromises;
     child->m_veil_state = m_veil_state;
-    child->m_unveiled_paths = m_unveiled_paths;
+    child->m_unveiled_paths = m_unveiled_paths.deep_copy();
     child->m_fds = m_fds;
     child->m_sid = m_sid;
     child->m_pg = m_pg;
diff --git a/Kernel/Syscalls/unveil.cpp b/Kernel/Syscalls/unveil.cpp
index 57807cd8e9..74f75252c5 100644
--- a/Kernel/Syscalls/unveil.cpp
+++ b/Kernel/Syscalls/unveil.cpp
@@ -68,19 +68,19 @@ int Process::sys$unveil(Userspace<const Syscall::SC_unveil_params*> user_params)
     for (const char permission : permissions) {
         switch (permission) {
         case 'r':
-            new_permissions |= UnveiledPath::Access::Read;
+            new_permissions |= UnveilAccess::Read;
             break;
         case 'w':
-            new_permissions |= UnveiledPath::Access::Write;
+            new_permissions |= UnveilAccess::Write;
             break;
         case 'x':
-            new_permissions |= UnveiledPath::Access::Execute;
+            new_permissions |= UnveilAccess::Execute;
             break;
         case 'c':
-            new_permissions |= UnveiledPath::Access::CreateOrRemove;
+            new_permissions |= UnveilAccess::CreateOrRemove;
             break;
         case 'b':
-            new_permissions |= UnveiledPath::Access::Browse;
+            new_permissions |= UnveilAccess::Browse;
             break;
         default:
             return -EINVAL;
@@ -97,7 +97,7 @@ int Process::sys$unveil(Userspace<const Syscall::SC_unveil_params*> user_params)
     auto custody_or_error = VFS::the().resolve_path_without_veil(path.value(), root_directory(), &parent_custody);
     if (!custody_or_error.is_error()) {
         new_unveiled_path = custody_or_error.value()->absolute_path();
-    } else if (custody_or_error.error() == -ENOENT && parent_custody && (new_permissions & UnveiledPath::Access::CreateOrRemove)) {
+    } else if (custody_or_error.error() == -ENOENT && parent_custody && (new_permissions & UnveilAccess::CreateOrRemove)) {
         String basename = LexicalPath(path.value()).basename();
         new_unveiled_path = String::formatted("{}/{}", parent_custody->absolute_path(), basename);
     } else {
@@ -105,16 +105,21 @@ int Process::sys$unveil(Userspace<const Syscall::SC_unveil_params*> user_params)
         return custody_or_error.error();
     }
 
-    for (auto& unveiled_path : m_unveiled_paths) {
-        if (unveiled_path.path == new_unveiled_path) {
-            if (new_permissions & ~unveiled_path.permissions)
-                return -EPERM;
-            unveiled_path.permissions = new_permissions;
-            return 0;
-        }
+    LexicalPath lexical_path(new_unveiled_path);
+    auto it = lexical_path.parts().begin();
+    auto& matching_node = m_unveiled_paths.traverse_until_last_accessible_node(it, lexical_path.parts().end());
+    if (it.is_end()) {
+        if (new_permissions & ~matching_node.permissions())
+            return -EPERM;
+        matching_node.set_metadata({ matching_node.path(), (UnveilAccess)new_permissions, true });
+        return 0;
     }
 
-    m_unveiled_paths.append({ new_unveiled_path, new_permissions });
+    matching_node.insert(
+        it,
+        lexical_path.parts().end(),
+        { new_unveiled_path, (UnveilAccess)new_permissions, true },
+        [](auto& parent, auto& it) -> Optional<UnveilMetadata> { return UnveilMetadata { String::formatted("{}/{}", parent.path(), *it), parent.permissions(), false }; });
     ASSERT(m_veil_state != VeilState::Locked);
     m_veil_state = VeilState::Dropped;
     return 0;
diff --git a/Kernel/UnveilNode.h b/Kernel/UnveilNode.h
new file mode 100644
index 0000000000..3204493482
--- /dev/null
+++ b/Kernel/UnveilNode.h
@@ -0,0 +1,58 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/String.h>
+#include <AK/Trie.h>
+
+namespace Kernel {
+
+enum UnveilAccess {
+    Read = 1,
+    Write = 2,
+    Execute = 4,
+    CreateOrRemove = 8,
+    Browse = 16,
+
+    None = 0,
+};
+
+struct UnveilMetadata {
+    String full_path;
+    UnveilAccess permissions { None };
+    bool explicitly_unveiled { false };
+};
+
+struct UnveilNode final : public AK::Trie<String, UnveilMetadata, Traits<String>, UnveilNode> {
+    using AK::Trie<String, UnveilMetadata, Traits<String>, UnveilNode>::Trie;
+
+    bool was_explicitly_unveiled() const { return this->metadata_value().explicitly_unveiled; }
+    UnveilAccess permissions() const { return this->metadata_value().permissions; }
+    const String& path() const { return this->metadata_value().full_path; }
+};
+
+}