LibELF: Re-organize ELFDynamicObject::load and add PLT trampoline

ELFDynamicObject::load looks a lot better with all the steps
re-organized into helpers.

Add plt_trampoline.S to handle PLT fixups for lazy loading.
Add the needed trampoline-trampolines in ELFDynamicObject to get to
the proper relocations and to return the symbol back to the assembly
method to call into from the PLT once we return back to user code.

4 files changed, 228 insertions, 164 deletions

diff --git a/Libraries/LibC/Makefile b/Libraries/LibC/Makefile
index cd9280ee8f..c070b77375 100644
--- a/Libraries/LibC/Makefile
+++ b/Libraries/LibC/Makefile
@@ -62,7 +62,11 @@ ELF_OBJS = \
 
 OBJS = $(AK_OBJS) $(LIBC_OBJS) $(ELF_OBJS)
 
-EXTRA_OBJS = setjmp.ao crti.ao crtn.ao
+EXTRA_OBJS = \
+        setjmp.ao \
+        crti.ao \
+        crtn.ao  \
+        ../LibELF/Arch/i386/plt_trampoline.ao
 
 crt0.o: crt0.cpp
 
diff --git a/Libraries/LibELF/Arch/i386/plt_trampoline.S b/Libraries/LibELF/Arch/i386/plt_trampoline.S
new file mode 100644
index 0000000000..6eb5e96a5f
--- /dev/null
+++ b/Libraries/LibELF/Arch/i386/plt_trampoline.S
@@ -0,0 +1,58 @@
+/*-
+ * Copyright (c) 1998, 2002 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Christos Zoulas and by Charles M. Hannum.
+ *
+ * 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 NETBSD FOUNDATION, INC. 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 FOUNDATION 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.
+ */
+
+/**
+ * This asm method is copied from NetBSD. We changed the internal method that
+ * gets called and the name, but it's still essentially the same as
+ * _rtld_bind_start from libexec/ld.elf_so/arch/i386/rtld_start.S
+ */
+
+.align	4
+	.globl	_plt_trampoline
+	.hidden	_plt_trampoline
+	.type	_plt_trampoline,@function
+_plt_trampoline:	# (obj, reloff)
+	pushf				# save registers
+	pushl	%eax
+	pushl	%ecx
+	pushl	%edx
+
+	pushl	20(%esp)		 # Copy of reloff
+	pushl	20(%esp)		 # Copy of obj
+	call	_fixup_plt_entry # Call the binder
+	addl	$8,%esp			 # pop binder args
+	movl	%eax,20(%esp)	 # Store function to be called in obj
+
+	popl	%edx
+	popl	%ecx
+	popl	%eax
+	popf
+
+	leal	4(%esp),%esp		# Discard reloff, do not change eflags
+	ret
diff --git a/Libraries/LibELF/ELFDynamicObject.cpp b/Libraries/LibELF/ELFDynamicObject.cpp
index 833ef54979..ffb92d7c0e 100644
--- a/Libraries/LibELF/ELFDynamicObject.cpp
+++ b/Libraries/LibELF/ELFDynamicObject.cpp
@@ -12,10 +12,12 @@
 #ifdef DYNAMIC_LOAD_VERBOSE
 #    define VERBOSE(fmt, ...) dbgprintf(fmt, ##__VA_ARGS__)
 #else
-#    define VERBOSE(fmt, ...) do { } while (0)
+#    define VERBOSE(fmt, ...) \
+        do {                  \
+        } while (0)
 #endif
 
-static bool s_always_bind_now = true;
+static bool s_always_bind_now = false;
 
 static const char* name_for_dtag(Elf32_Sword tag);
 
@@ -79,6 +81,43 @@ ELFDynamicObject::~ELFDynamicObject()
         munmap(m_file_mapping, m_file_size);
 }
 
+void* ELFDynamicObject::symbol_for_name(const char* name)
+{
+    // FIXME: If we enable gnu hash in the compiler, we should use that here instead
+    //     The algo is way better with less collisions
+    uint32_t hash_value = calculate_elf_hash(name);
+
+    u8* load_addr = m_text_region->load_address().as_ptr();
+
+    // NOTE: We need to use the loaded hash/string/symbol tables here to get the right
+    //    addresses. The ones that are in the ELFImage won't cut it, they aren't relocated
+    u32* hash_table_begin = (u32*)(load_addr + m_hash_table_offset);
+    Elf32_Sym* symtab = (Elf32_Sym*)(load_addr + m_symbol_table_offset);
+    const char* strtab = (const char*)load_addr + m_string_table_offset;
+
+    size_t num_buckets = hash_table_begin[0];
+
+    // This is here for completeness, but, since we're using the fact that every chain
+    // will end at chain 0 (which means 'not found'), we don't need to check num_chains.
+    // Interestingly, num_chains is required to be num_symbols
+    //size_t num_chains = hash_table_begin[1];
+
+    u32* buckets = &hash_table_begin[2];
+    u32* chains = &buckets[num_buckets];
+
+    for (u32 i = buckets[hash_value % num_buckets]; i; i = chains[i]) {
+        if (strcmp(name, strtab + symtab[i].st_name) == 0) {
+            void* symbol_address = load_addr + symtab[i].st_value;
+#ifdef DYNAMIC_LOAD_DEBUG
+            dbgprintf("Returning dynamic symbol with index %d for %s: %p\n", i, strtab + symtab[i].st_name, symbol_address);
+#endif
+            return symbol_address;
+        }
+    }
+
+    return nullptr;
+}
+
 void ELFDynamicObject::dump()
 {
     auto dynamic_section = m_image->dynamic_section();
@@ -194,8 +233,37 @@ bool ELFDynamicObject::load(unsigned flags)
 #endif
 
     parse_dynamic_section();
+    load_program_headers();
+
+    if (m_has_text_relocations) {
+        if (0 > mprotect(m_text_region->load_address().as_ptr(), m_text_region->required_load_size(), PROT_READ | PROT_WRITE)) {
+            perror("mprotect"); // FIXME: dlerror?
+            return false;
+        }
+    }
+
+    do_relocations();
+    setup_plt_trampoline();
+
+    // Clean up our setting of .text to PROT_READ | PROT_WRITE
+    if (m_has_text_relocations) {
+        if (0 > mprotect(m_text_region->load_address().as_ptr(), m_text_region->required_load_size(), PROT_READ | PROT_EXEC)) {
+            perror("mprotect"); // FIXME: dlerror?
+            return false;
+        }
+    }
+
+    call_object_init_functions();
+
+#ifdef DYNAMIC_LOAD_DEBUG
+    dbgprintf("Loaded %s\n", m_filename.characters());
+#endif
+    // FIXME: return false sometimes? missing symbol etc
+    return true;
+}
 
-    // FIXME: be more flexible?
+void ELFDynamicObject::load_program_headers()
+{
     size_t total_required_allocation_size = 0;
 
     // FIXME: Can we re-use ELFLoader? This and what follows looks a lot like what's in there...
@@ -245,149 +313,6 @@ bool ELFDynamicObject::load(unsigned flags)
     // sanity check
     u8* end_of_in_memory_image = (u8*)data_segment_begin + data_segment_size;
     ASSERT((ptrdiff_t)total_required_allocation_size == (ptrdiff_t)(end_of_in_memory_image - (u8*)text_segment_begin));
-
-    if (m_has_text_relocations) {
-        if (0 > mprotect(m_text_region->load_address().as_ptr(), m_text_region->required_load_size(), PROT_READ | PROT_WRITE)) {
-            perror("mprotect"); // FIXME: dlerror?
-            return false;
-        }
-    }
-
-    do_relocations();
-
-#ifdef DYNAMIC_LOAD_DEBUG
-    dbgprintf("Done relocating!\n");
-#endif
-
-    // FIXME: PLT patching doesn't seem to work as expected.
-    //     Need to dig into the spec to see what we're doing wrong
-    //     Hopefully it won't need an assembly entry point... :/
-    ///    For now we can just BIND_NOW every time
-
-    // This should be the address of section ".got.plt"
-    const ELFImage::Section& got_section = m_image->lookup_section(".got.plt");
-    VirtualAddress got_address = m_text_region->load_address().offset(got_section.address());
-
-    u32* got_u32_ptr = reinterpret_cast<u32*>(got_address.as_ptr());
-    got_u32_ptr[1] = (u32)this;
-    got_u32_ptr[2] = (u32)&ELFDynamicObject::patch_plt_entry;
-
-#ifdef DYNAMIC_LOAD_DEBUG
-    dbgprintf("Set GOT PLT entries at %p: [0] = %p [1] = %p, [2] = %p\n", got_u32_ptr, got_u32_ptr[0], got_u32_ptr[1], got_u32_ptr[2]);
-#endif
-
-    // Clean up our setting of .text to PROT_READ | PROT_WRITE
-    if (m_has_text_relocations) {
-        if (0 > mprotect(m_text_region->load_address().as_ptr(), m_text_region->required_load_size(), PROT_READ | PROT_EXEC)) {
-            perror("mprotect"); // FIXME: dlerror?
-            return false;
-        }
-    }
-
-    u8* load_addr = m_text_region->load_address().as_ptr();
-    InitFunc init_function = (InitFunc)(load_addr + m_init_offset);
-
-#ifdef DYNAMIC_LOAD_DEBUG
-    dbgprintf("Calling DT_INIT at %p\n", init_function);
-#endif
-
-    (init_function)();
-
-    InitFunc* init_begin = (InitFunc*)(load_addr + m_init_array_offset);
-    u32 init_end = (u32)((u8*)init_begin + m_init_array_size);
-    while ((u32)init_begin < init_end) {
-        // Andriod sources claim that these can be -1, to be ignored.
-        // 0 definitely shows up. Apparently 0/-1 are valid? Confusing.
-        if (!*init_begin || ((i32)*init_begin == -1))
-            continue;
-#ifdef DYNAMIC_LOAD_DEBUG
-        dbgprintf("Calling DT_INITARRAY entry at %p\n", *init_begin);
-#endif
-        (*init_begin)();
-        ++init_begin;
-    }
-
-#ifdef DYNAMIC_LOAD_DEBUG
-    dbgprintf("Loaded %s\n", m_filename.characters());
-#endif
-    // FIXME: return false sometimes? missing symbol etc
-    return true;
-}
-
-void* ELFDynamicObject::symbol_for_name(const char* name)
-{
-    // FIXME: If we enable gnu hash in the compiler, we should use that here instead
-    //     The algo is way better with less collisions
-    uint32_t hash_value = calculate_elf_hash(name);
-
-    u8* load_addr = m_text_region->load_address().as_ptr();
-
-    // NOTE: We need to use the loaded hash/string/symbol tables here to get the right
-    //    addresses. The ones that are in the ELFImage won't cut it, they aren't relocated
-    u32* hash_table_begin = (u32*)(load_addr + m_hash_table_offset);
-    Elf32_Sym* symtab = (Elf32_Sym*)(load_addr + m_symbol_table_offset);
-    const char* strtab = (const char*)load_addr + m_string_table_offset;
-
-    size_t num_buckets = hash_table_begin[0];
-
-    // This is here for completeness, but, since we're using the fact that every chain
-    // will end at chain 0 (which means 'not found'), we don't need to check num_chains.
-    // Interestingly, num_chains is required to be num_symbols
-    //size_t num_chains = hash_table_begin[1];
-
-    u32* buckets = &hash_table_begin[2];
-    u32* chains = &buckets[num_buckets];
-
-    for (u32 i = buckets[hash_value % num_buckets]; i; i = chains[i]) {
-        if (strcmp(name, strtab + symtab[i].st_name) == 0) {
-            void* retval = load_addr + symtab[i].st_value;
-#ifdef DYNAMIC_LOAD_DEBUG
-            dbgprintf("Returning dynamic symbol with index %d for %s: %p\n", i, strtab + symtab[i].st_name, retval);
-#endif
-            return retval;
-        }
-    }
-
-    return nullptr;
-}
-
-// offset is from PLT entry
-// Tag is inserted into GOT #2 for 'this' DSO (literally the this pointer)
-void ELFDynamicObject::patch_plt_entry(u32 got_offset, void* dso_got_tag)
-{
-    // FIXME: This is never called :(
-    CRASH();
-    dbgprintf("------ PATCHING PLT ENTRY -------");
-    // NOTE: We put 'this' into the GOT when we loaded it into memory
-    auto* dynamic_object_object = reinterpret_cast<ELFDynamicObject*>(dso_got_tag);
-
-    // FIXME: might actually be a RelA, check m_plt_relocation_type
-    // u32 base_addr_offset = dynamic_object_object->m_relocation_table_offset + got_offset;
-    // Elf32_Rel relocation = *reinterpret_cast<Elf32_Rel*>(&((u8*)dynamic_object_object->m_file_mapping)[base_addr_offset]);
-    u32 relocation_index = got_offset / dynamic_object_object->m_size_of_relocation_entry;
-    auto relocation = dynamic_object_object->m_image->dynamic_relocation_section().relocation(relocation_index);
-
-    ASSERT(relocation.type() == R_386_JMP_SLOT);
-
-    auto sym = relocation.symbol();
-
-    auto* text_load_address = dynamic_object_object->m_text_region->load_address().as_ptr();
-    u8* relocation_address = text_load_address + relocation.offset();
-
-    if (0 > mprotect(text_load_address, dynamic_object_object->m_text_region->required_load_size(), PROT_READ | PROT_WRITE)) {
-        ASSERT_NOT_REACHED(); // uh oh, no can do boss
-    }
-
-    dbgprintf("Found relocation address: %p for %s", relocation_address, sym.name());
-
-    *(u32*)relocation_address = (u32)(text_load_address + sym.value());
-
-    if (0 > mprotect(text_load_address, dynamic_object_object->m_text_region->required_load_size(), PROT_READ | PROT_EXEC)) {
-        ASSERT_NOT_REACHED(); // uh oh, no can do boss
-    }
-
-    CRASH();
-    // FIXME: Call the relocated method here?
 }
 
 void ELFDynamicObject::do_relocations()
@@ -476,28 +401,101 @@ void ELFDynamicObject::do_relocations()
         return IterationDecision::Continue;
     });
 
-    // FIXME: Or BIND_NOW flag passed in?
-    if (m_must_bind_now || s_always_bind_now) {
-        // FIXME: Why do we keep jumping to the entry in the GOT without going to our callback first?
-        //     that would make this s_always_bind_now redundant
-
-        for (size_t idx = 0; idx < m_size_of_plt_relocation_entry_list; idx += m_size_of_relocation_entry) {
+    // Handle PLT Global offset table relocations.
+    for (size_t idx = 0; idx < m_size_of_plt_relocation_entry_list; idx += m_size_of_relocation_entry) {
+        // FIXME: Or BIND_NOW flag passed in?
+        if (m_must_bind_now || s_always_bind_now) {
+            // Eagerly BIND_NOW the PLT entries, doing all the symbol looking goodness
+            // The patch method returns the address for the LAZY fixup path, but we don't need it here
+            (void)patch_plt_entry(idx);
+        } else {
+            // LAZY-ily bind the PLT slots by just adding the base address to the offsets stored there
+            // This avoids doing symbol lookup, which might be expensive
             VirtualAddress relocation_vaddr = m_text_region->load_address().offset(m_plt_relocation_offset_location).offset(idx);
             Elf32_Rel* jump_slot_relocation = (Elf32_Rel*)relocation_vaddr.as_ptr();
 
             ASSERT(ELF32_R_TYPE(jump_slot_relocation->r_info) == R_386_JMP_SLOT);
 
-            auto sym = m_image->dynamic_symbol(ELF32_R_SYM(jump_slot_relocation->r_info));
-
             auto* image_base_address = m_text_region->base_address().as_ptr();
             u8* relocation_address = image_base_address + jump_slot_relocation->r_offset;
-            u32 symbol_location = (u32)(image_base_address + sym.value());
 
-            VERBOSE("ELFDynamicObject: Jump slot relocation: putting %s (%p) into PLT at %p\n", sym.name(), symbol_location, relocation_address);
-
-            *(u32*)relocation_address = symbol_location;
+            *(u32*)relocation_address += (u32)image_base_address;
         }
     }
+
+#ifdef DYNAMIC_LOAD_DEBUG
+    dbgprintf("Done relocating!\n");
+#endif
+}
+
+// Defined in <arch>/plt_trampoline.S
+extern "C" void _plt_trampoline(void) __attribute__((visibility("hidden")));
+
+void ELFDynamicObject::setup_plt_trampoline()
+{
+    const ELFImage::Section& got_section = m_image->lookup_section(".got.plt");
+    VirtualAddress got_address = m_text_region->load_address().offset(got_section.address());
+
+    u32* got_u32_ptr = reinterpret_cast<u32*>(got_address.as_ptr());
+    got_u32_ptr[1] = (u32)this;
+    got_u32_ptr[2] = (u32)&_plt_trampoline;
+
+#ifdef DYNAMIC_LOAD_DEBUG
+    dbgprintf("Set GOT PLT entries at %p offset(%p): [0] = %p [1] = %p, [2] = %p\n", got_u32_ptr, got_section.offset(), got_u32_ptr[0], got_u32_ptr[1], got_u32_ptr[2]);
+#endif
+}
+
+// Called from our ASM routine _plt_trampoline
+extern "C" Elf32_Addr _fixup_plt_entry(ELFDynamicObject* object, u32 relocation_idx)
+{
+    return object->patch_plt_entry(relocation_idx);
+}
+
+// offset is in PLT relocation table
+Elf32_Addr ELFDynamicObject::patch_plt_entry(u32 relocation_idx)
+{
+    VirtualAddress plt_relocation_table_address = m_text_region->load_address().offset(m_plt_relocation_offset_location);
+    VirtualAddress relocation_entry_address = plt_relocation_table_address.offset(relocation_idx);
+    Elf32_Rel* jump_slot_relocation = (Elf32_Rel*)relocation_entry_address.as_ptr();
+
+    ASSERT(ELF32_R_TYPE(jump_slot_relocation->r_info) == R_386_JMP_SLOT);
+
+    auto sym = m_image->dynamic_symbol(ELF32_R_SYM(jump_slot_relocation->r_info));
+
+    auto* image_base_address = m_text_region->base_address().as_ptr();
+    u8* relocation_address = image_base_address + jump_slot_relocation->r_offset;
+    u32 symbol_location = (u32)(image_base_address + sym.value());
+
+    VERBOSE("ELFDynamicObject: Jump slot relocation: putting %s (%p) into PLT at %p\n", sym.name(), symbol_location, relocation_address);
+
+    *(u32*)relocation_address = symbol_location;
+
+    return symbol_location;
+}
+
+void ELFDynamicObject::call_object_init_functions()
+{
+    u8* load_addr = m_text_region->load_address().as_ptr();
+    InitFunc init_function = (InitFunc)(load_addr + m_init_offset);
+
+#ifdef DYNAMIC_LOAD_DEBUG
+    dbgprintf("Calling DT_INIT at %p\n", init_function);
+#endif
+    (init_function)();
+
+    InitFunc* init_begin = (InitFunc*)(load_addr + m_init_array_offset);
+    u32 init_end = (u32)((u8*)init_begin + m_init_array_size);
+    while ((u32)init_begin < init_end) {
+        // Andriod sources claim that these can be -1, to be ignored.
+        // 0 definitely shows up. Apparently 0/-1 are valid? Confusing.
+        if (!*init_begin || ((i32)*init_begin == -1))
+            continue;
+#ifdef DYNAMIC_LOAD_DEBUG
+        dbgprintf("Calling DT_INITARRAY entry at %p\n", *init_begin);
+#endif
+        (*init_begin)();
+        ++init_begin;
+    }
 }
 
 u32 ELFDynamicObject::ProgramHeaderRegion::mmap_prot() const
diff --git a/Libraries/LibELF/ELFDynamicObject.h b/Libraries/LibELF/ELFDynamicObject.h
index 98f09e9b1a..5abedb0abb 100644
--- a/Libraries/LibELF/ELFDynamicObject.h
+++ b/Libraries/LibELF/ELFDynamicObject.h
@@ -28,6 +28,9 @@ public:
 
     void dump();
 
+    // Will be called from _fixup_plt_entry, as part of the PLT trampoline
+    Elf32_Addr patch_plt_entry(u32 relocation_offset);
+
 private:
     class ProgramHeaderRegion {
     public:
@@ -68,6 +71,12 @@ private:
 
     explicit ELFDynamicObject(const char* filename, int fd, size_t file_size);
 
+    void parse_dynamic_section();
+    void load_program_headers();
+    void do_relocations();
+    void setup_plt_trampoline();
+    void call_object_init_functions();
+
     String m_filename;
     size_t m_file_size { 0 };
     int m_image_fd { -1 };
@@ -76,11 +85,6 @@ private:
 
     OwnPtr<ELFImage> m_image;
 
-    void parse_dynamic_section();
-    void do_relocations();
-
-    static void patch_plt_entry(u32 got_offset, void* dso_got_tag);
-
     Vector<ProgramHeaderRegion> m_program_header_regions;
     ProgramHeaderRegion* m_text_region { nullptr };
     ProgramHeaderRegion* m_data_region { nullptr };