Kernel: Avoid collision between dynamic loader and main program

When loading non position-independent programs, we now take care not to
load the dynamic loader at an address that collides with the location
the main program wants to load at.

Fixes #4847.

2 files changed, 99 insertions, 5 deletions

diff --git a/Kernel/Process.h b/Kernel/Process.h
index 40202cd88f..e5f7fbdf77 100644
--- a/Kernel/Process.h
+++ b/Kernel/Process.h
@@ -433,6 +433,7 @@ public:
 
     KResultOr<LoadResult> load(NonnullRefPtr<FileDescription> main_program_description, RefPtr<FileDescription> interpreter_description, const Elf32_Ehdr& main_program_header);
     KResultOr<LoadResult> load_elf_object(FileDescription& object_description, FlatPtr load_offset, ShouldAllocateTls);
+    KResultOr<FlatPtr> get_interpreter_load_offset(const Elf32_Ehdr& main_program_header, FileDescription& main_program_description, FileDescription& interpreter_description);
 
     bool is_superuser() const
     {
diff --git a/Kernel/Syscalls/execve.cpp b/Kernel/Syscalls/execve.cpp
index 3538f1aa57..b02c45bd77 100644
--- a/Kernel/Syscalls/execve.cpp
+++ b/Kernel/Syscalls/execve.cpp
@@ -317,11 +317,12 @@ KResultOr<Process::LoadResult> Process::load(NonnullRefPtr<FileDescription> main
         return result;
     }
 
-    // TODO: I'm sure this can be randomized even better. :^)
-    FlatPtr random_offset = get_good_random<u16>() * PAGE_SIZE;
-    FlatPtr interpreter_load_offset = 0x08000000 + random_offset;
+    auto interpreter_load_offset = get_interpreter_load_offset(main_program_header, main_program_description, *interpreter_description);
+    if (interpreter_load_offset.is_error()) {
+        return interpreter_load_offset.error();
+    }
 
-    auto interpreter_load_result = load_elf_object((interpreter_description) ? *interpreter_description : *main_program_description, interpreter_load_offset, ShouldAllocateTls::No);
+    auto interpreter_load_result = load_elf_object(*interpreter_description, interpreter_load_offset.value(), ShouldAllocateTls::No);
 
     if (interpreter_load_result.is_error())
         return interpreter_load_result.error();
@@ -335,7 +336,99 @@ KResultOr<Process::LoadResult> Process::load(NonnullRefPtr<FileDescription> main
     return interpreter_load_result;
 }
 
-int Process::do_exec(NonnullRefPtr<FileDescription> main_program_description, Vector<String> arguments, Vector<String> environment, RefPtr<FileDescription> interpreter_description, Thread*& new_main_thread, u32& prev_flags, bool is_dynamic)
+struct RequiredLoadRange {
+    FlatPtr start { 0 };
+    FlatPtr end { 0 };
+};
+
+static KResultOr<RequiredLoadRange> get_required_load_range(FileDescription& program_description)
+{
+    auto& inode = *(program_description.inode());
+    auto vmobject = SharedInodeVMObject::create_with_inode(inode);
+
+    size_t executable_size = inode.size();
+
+    auto region = MM.allocate_kernel_region_with_vmobject(*vmobject, PAGE_ROUND_UP(executable_size), "ELF memory range calculation", Region::Access::Read);
+    if (!region) {
+        dbgln("Could not allocate memory for ELF");
+        return KResult(-ENOMEM);
+    }
+
+    auto elf_image = ELF::Image(region->vaddr().as_ptr(), executable_size);
+    if (!elf_image.is_valid()) {
+        return -EINVAL;
+    }
+
+    RequiredLoadRange range {};
+    elf_image.for_each_program_header([&range](const auto& pheader) {
+        if (pheader.type() != PT_LOAD)
+            return IterationDecision::Continue;
+
+        auto region_start = (FlatPtr)pheader.vaddr().as_ptr();
+        auto region_end = region_start + pheader.size_in_memory();
+        if (range.start == 0 || region_start < range.start)
+            range.start = region_start;
+        if (range.end == 0 || region_end > range.end)
+            range.end = region_end;
+        return IterationDecision::Continue;
+    });
+
+    ASSERT(range.end > range.start);
+    return range;
+};
+
+KResultOr<FlatPtr> Process::get_interpreter_load_offset(const Elf32_Ehdr& main_program_header, FileDescription& main_program_description, FileDescription& interpreter_description)
+{
+    constexpr FlatPtr interpreter_load_range_start = 0x08000000;
+    constexpr FlatPtr interpreter_load_range_size = 65536 * PAGE_SIZE; // 2**16 * PAGE_SIZE = 256MB
+    constexpr FlatPtr minimum_interpreter_load_offset_randomization_size = 10 * MiB;
+
+    auto random_load_offset_in_range([](auto start, auto size) {
+        return PAGE_ROUND_DOWN(start + get_good_random<FlatPtr>() % size);
+    });
+
+    if (main_program_header.e_type == ET_DYN) {
+        return random_load_offset_in_range(interpreter_load_range_start, interpreter_load_range_size);
+    }
+
+    if (main_program_header.e_type != ET_EXEC)
+        return -EINVAL;
+
+    auto main_program_load_range_result = get_required_load_range(main_program_description);
+    if (main_program_load_range_result.is_error())
+        return main_program_load_range_result.error();
+
+    auto main_program_load_range = main_program_load_range_result.value();
+
+    auto interpreter_load_range_result = get_required_load_range(interpreter_description);
+    if (interpreter_load_range_result.is_error())
+        return interpreter_load_range_result.error();
+
+    auto interpreter_size_in_memory = interpreter_load_range_result.value().end - interpreter_load_range_result.value().start;
+    auto interpreter_load_range_end = interpreter_load_range_start + interpreter_load_range_size - interpreter_size_in_memory;
+
+    // No intersection
+    if (main_program_load_range.end < interpreter_load_range_start || main_program_load_range.start > interpreter_load_range_end)
+        return random_load_offset_in_range(interpreter_load_range_start, interpreter_load_range_size);
+
+    RequiredLoadRange first_available_part = { interpreter_load_range_start, main_program_load_range.start };
+    RequiredLoadRange second_available_part = { main_program_load_range.end, interpreter_load_range_end };
+
+    RequiredLoadRange selected_range {};
+    // Select larger part
+    if (first_available_part.end - first_available_part.start > second_available_part.end - second_available_part.start)
+        selected_range = first_available_part;
+    else
+        selected_range = second_available_part;
+
+    // If main program is too big and leaves us without enough space for adequate loader randmoization
+    if (selected_range.end - selected_range.start < minimum_interpreter_load_offset_randomization_size)
+        return -E2BIG;
+
+    return random_load_offset_in_range(selected_range.start, selected_range.end - selected_range.start);
+}
+
+int Process::do_exec(NonnullRefPtr<FileDescription> main_program_description, Vector<String> arguments, Vector<String> environment, RefPtr<FileDescription> interpreter_description, Thread*& new_main_thread, u32& prev_flags, const Elf32_Ehdr& main_program_header)
 {
     ASSERT(is_user_process());
     ASSERT(!Processor::current().in_critical());