jart / blink

tiniest x86-64-linux emulator
ISC License
7k stars 225 forks source link

Linux ELF does not load correctly if page size is not 4KB #31

Closed trungnt2910 closed 1 year ago

trungnt2910 commented 1 year ago

This comment noted that when the page size is not 64KB, the loader just "forgets" to copy the data onto memory.

This problem was discovered in the first versions of blink on Emscripten before a hack hardcoding the page size to 4096 is enabled.

However, on Cygwin, this problem appears again:

Trung@DESKTOP-5OCA2N2 /cygdrive/d/CodingProjects/Blink
$ o//blink/blink -m /cygdrive/e/temporary\ media/uname
I2023-01-16T10:31:38.151550:blink/map.c:54:0 (mem) big created 16m map [0x6ffffeff0000,0x6fffffff1000)
I2023-01-16T10:31:38.152812:blink/map.c:54:8795 (mem) loader created 8872 map [0x6ffffefe0000,0x6ffffefe22a8)
I2023-01-16T10:31:38.152833:blink/map.c:54:8795 (mem) big created 256k map [0x6ffffefa0000,0x6ffffefe0000)
I2023-01-16T10:31:38.152842:blink/loader.c:61:8795 (elf) PROGRAM HEADER
I2023-01-16T10:31:38.152845:blink/loader.c:62:8795 (elf)   vaddr = 400000
I2023-01-16T10:31:38.152848:blink/loader.c:63:8795 (elf)   memsz = e8
I2023-01-16T10:31:38.152851:blink/loader.c:64:8795 (elf)   offset = 0
I2023-01-16T10:31:38.152853:blink/loader.c:65:8795 (elf)   filesz = e8
I2023-01-16T10:31:38.152856:blink/loader.c:66:8795 (elf)   pagesize = 10000
I2023-01-16T10:31:38.152858:blink/loader.c:67:8795 (elf)   start = 400000
I2023-01-16T10:31:38.152861:blink/loader.c:68:8795 (elf)   end = 410000
I2023-01-16T10:31:38.152863:blink/loader.c:69:8795 (elf)   skew = 0
I2023-01-16T10:31:38.152866:blink/loader.c:156:8795 (elf) alloc 400000-410000
I2023-01-16T10:31:38.152869:blink/memorymalloc.c:462:8795 (mem) reserving virtual [0x400000,0x410000) w/ 64 kb
I2023-01-16T10:31:38.152881:blink/loader.c:163:8795 (elf) copy 400000-4000e8 from 0-e8
I2023-01-16T10:31:38.152886:blink/loader.c:61:8795 (elf) PROGRAM HEADER
I2023-01-16T10:31:38.152888:blink/loader.c:62:8795 (elf)   vaddr = 401000
I2023-01-16T10:31:38.152891:blink/loader.c:63:8795 (elf)   memsz = 15a
I2023-01-16T10:31:38.152893:blink/loader.c:64:8795 (elf)   offset = 1000
I2023-01-16T10:31:38.152896:blink/loader.c:65:8795 (elf)   filesz = 15a
I2023-01-16T10:31:38.152898:blink/loader.c:66:8795 (elf)   pagesize = 10000
I2023-01-16T10:31:38.152901:blink/loader.c:67:8795 (elf)   start = 400000
I2023-01-16T10:31:38.152904:blink/loader.c:68:8795 (elf)   end = 410000
I2023-01-16T10:31:38.152906:blink/loader.c:69:8795 (elf)   skew = 1000
I2023-01-16T10:31:38.152909:blink/loader.c:61:8795 (elf) PROGRAM HEADER
I2023-01-16T10:31:38.152911:blink/loader.c:62:8795 (elf)   vaddr = 402000
I2023-01-16T10:31:38.152914:blink/loader.c:63:8795 (elf)   memsz = 2
I2023-01-16T10:31:38.152916:blink/loader.c:64:8795 (elf)   offset = 2000
I2023-01-16T10:31:38.152919:blink/loader.c:65:8795 (elf)   filesz = 2
I2023-01-16T10:31:38.152921:blink/loader.c:66:8795 (elf)   pagesize = 10000
I2023-01-16T10:31:38.152924:blink/loader.c:67:8795 (elf)   start = 400000
I2023-01-16T10:31:38.152926:blink/loader.c:68:8795 (elf)   end = 410000
I2023-01-16T10:31:38.152929:blink/loader.c:69:8795 (elf)   skew = 2000
I2023-01-16T10:31:38.152932:blink/memorymalloc.c:462:8795 (mem) reserving virtual [0x4fffff800000,0x500000000000) w/ 8192 kb
I2023-01-16T10:31:38.153202:blink/throw.c:91:8795 SEGMENTATION FAULT AT ADDRESS 0
         PC 401000 add %al,(%rax)
         AX 0000000000000000  CX 0000000000000000  DX 0000000000000000  BX 0000000000000000
         SP 00004fffffffdd10  BP 0000000000000000  SI 0000000000000000  DI 0000000000000000
         R8 0000000000000000  R9 0000000000000000 R10 0000000000000000 R11 0000000000000000
        R12 0000000000000000 R13 0000000000000000 R14 0000000000000000 R15 0000000000000000
         FS 0000000000000000  GS 0000000000000000 OPS 1                JIT 0
        /cygdrive/e/temporary media/uname
        000000000000 000000401000 _start
I2023-01-16T10:31:38.153217:blink/blink.c:67:8795 terminating due to signal SIGSEGV
Segmentation fault (core dumped)

While Windows can use 4096-byte page sizes for mprotect and stuff, it can only allocate pages with 64kb granularity.

trungnt2910 commented 1 year ago

For Windows, this hack seems to work:

diff --git a/blink/map.c b/blink/map.c
index a14c120..f8274f2 100644
--- a/blink/map.c
+++ b/blink/map.c
@@ -20,6 +20,10 @@
 #include <string.h>
 #include <unistd.h>

+#ifdef __CYGWIN__
+#include <windows.h>
+#endif
+
 #include "blink/assert.h"
 #include "blink/log.h"
 #include "blink/macros.h"
@@ -32,6 +36,12 @@ long GetSystemPageSize(void) {
   // "pages" in Emscripten only refer to the granularity the memory
   // buffer can be grown at but does not affect functions like mmap.
   return 4096;
+#endif
+#ifdef __CYGWIN__
+  SYSTEM_INFO si;
+  GetSystemInfo(&si);
+  unassert(IS2POW(si.dwPageSize));
+  return si.dwPageSize;
 #endif
   long z;
   unassert((z = sysconf(_SC_PAGESIZE)) > 0);
@@ -47,6 +57,17 @@ void *Mmap(void *addr,     //
            off_t offset,   //
            const char *owner) {
   void *res = mmap(addr, length, prot, flags, fd, offset);
+#if __CYGWIN__
+  if (res == MAP_FAILED && (flags & MAP_FIXED) && fd == -1) {
+    SYSTEM_INFO si;
+    GetSystemInfo(&si);
+    void* nearest_addr = (void*)ROUNDDOWN((u64)addr,
+                                          (u64)si.dwAllocationGranularity);
+    size_t new_length = length + (u64)addr - (u64)nearest_addr;
+    res = mmap(nearest_addr, new_length, prot, flags, fd, offset);
+    unassert(mprotect(nearest_addr, new_length - length, PROT_NONE));
+  }
+#endif
 #if LOG_MEM
   char szbuf[16];
   FormatSize(szbuf, length, 1024);

This hack aligns the base address to the nearest allocatable address. This might leak some bytes, but because JIT (the only ones using MAP_FIXED in this case) never calls munmap, it doesn't really matter.

For other purposes other than MAP_FIXED, 4096 is good enough on Windows.

This hack still does not address the loader's problem though. And after reading your loader code for a while, I seem to understand what it does, step-by-step, but I do not understand why. Many ELF tutorials that I learned from take all the program headers, calculate a start and end address, allocate all pages at the same time before copying the data, and handles page permissions through mprotect calls later.

trungnt2910 commented 1 year ago

When this hack is applied, the log changes to:

$ o//blink/blink -m /cygdrive/e/temporary\ media/uname
I2023-01-16T23:31:14.282980:blink/map.c:75:0 (mem) big created 16m map [0x6ffffeff0000,0x6fffffff1000)
I2023-01-16T23:31:14.284657:blink/map.c:75:2951 (mem) loader created 8872 map [0x6ffffefe0000,0x6ffffefe22a8)
I2023-01-16T23:31:14.284695:blink/map.c:75:2951 (mem) big created 256k map [0x6ffffefa0000,0x6ffffefe0000)
I2023-01-16T23:31:14.284716:blink/loader.c:61:2951 (elf) PROGRAM HEADER
I2023-01-16T23:31:14.284722:blink/loader.c:62:2951 (elf)   vaddr = 400000
I2023-01-16T23:31:14.284726:blink/loader.c:63:2951 (elf)   memsz = e8
I2023-01-16T23:31:14.284730:blink/loader.c:64:2951 (elf)   offset = 0
I2023-01-16T23:31:14.284734:blink/loader.c:65:2951 (elf)   filesz = e8
I2023-01-16T23:31:14.284739:blink/loader.c:66:2951 (elf)   pagesize = 1000
I2023-01-16T23:31:14.284743:blink/loader.c:67:2951 (elf)   start = 400000
I2023-01-16T23:31:14.284748:blink/loader.c:68:2951 (elf)   end = 401000
I2023-01-16T23:31:14.284752:blink/loader.c:69:2951 (elf)   skew = 0
I2023-01-16T23:31:14.284756:blink/loader.c:156:2951 (elf) alloc 400000-401000
I2023-01-16T23:31:14.284761:blink/memorymalloc.c:462:2951 (mem) reserving virtual [0x400000,0x401000) w/ 4 kb
I2023-01-16T23:31:14.284788:blink/loader.c:163:2951 (elf) copy 400000-4000e8 from 0-e8
I2023-01-16T23:31:14.284797:blink/loader.c:61:2951 (elf) PROGRAM HEADER
I2023-01-16T23:31:14.284801:blink/loader.c:62:2951 (elf)   vaddr = 401000
I2023-01-16T23:31:14.284805:blink/loader.c:63:2951 (elf)   memsz = 15a
I2023-01-16T23:31:14.284809:blink/loader.c:64:2951 (elf)   offset = 1000
I2023-01-16T23:31:14.284814:blink/loader.c:65:2951 (elf)   filesz = 15a
I2023-01-16T23:31:14.284818:blink/loader.c:66:2951 (elf)   pagesize = 1000
I2023-01-16T23:31:14.284822:blink/loader.c:67:2951 (elf)   start = 401000
I2023-01-16T23:31:14.284827:blink/loader.c:68:2951 (elf)   end = 402000
I2023-01-16T23:31:14.284831:blink/loader.c:69:2951 (elf)   skew = 0
I2023-01-16T23:31:14.284835:blink/loader.c:156:2951 (elf) alloc 401000-402000
I2023-01-16T23:31:14.284839:blink/memorymalloc.c:462:2951 (mem) reserving virtual [0x401000,0x402000) w/ 4 kb
I2023-01-16T23:31:14.284844:blink/loader.c:163:2951 (elf) copy 401000-40115a from 1000-115a
I2023-01-16T23:31:14.284855:blink/loader.c:61:2951 (elf) PROGRAM HEADER
I2023-01-16T23:31:14.284859:blink/loader.c:62:2951 (elf)   vaddr = 402000
I2023-01-16T23:31:14.284863:blink/loader.c:63:2951 (elf)   memsz = 2
I2023-01-16T23:31:14.284868:blink/loader.c:64:2951 (elf)   offset = 2000
I2023-01-16T23:31:14.284872:blink/loader.c:65:2951 (elf)   filesz = 2
I2023-01-16T23:31:14.284877:blink/loader.c:66:2951 (elf)   pagesize = 1000
I2023-01-16T23:31:14.284881:blink/loader.c:67:2951 (elf)   start = 402000
I2023-01-16T23:31:14.284885:blink/loader.c:68:2951 (elf)   end = 403000
I2023-01-16T23:31:14.284889:blink/loader.c:69:2951 (elf)   skew = 0
I2023-01-16T23:31:14.284894:blink/loader.c:156:2951 (elf) alloc 402000-403000
I2023-01-16T23:31:14.284898:blink/memorymalloc.c:462:2951 (mem) reserving virtual [0x402000,0x403000) w/ 4 kb
I2023-01-16T23:31:14.284903:blink/loader.c:163:2951 (elf) copy 402000-402002 from 2000-2002
I2023-01-16T23:31:14.284912:blink/memorymalloc.c:462:2951 (mem) reserving virtual [0x4fffff800000,0x500000000000) w/ 8192 kb
blink DESKTOP-5OCA2N2 4.0 blink 4.0 x86_64

Note that I'm running master, the cygwin branch with JIT currently just crashes without a log for every binary (either crafted by me or obtained from the o//test folder).

jart commented 1 year ago

This hack still does not address the loader's problem though. And after reading your loader code for a while, I seem to understand what it does, step-by-step, but I do not understand why. Many ELF tutorials that I learned from take all the program headers, calculate a start and end address, allocate all pages at the same time before copying the data, and handles page permissions through mprotect calls later.

The problem with doing that is it'll cause a page fault on every single page in the program image. Our loader code is complicated because it loads the program image into memory without copying it. This is important when loading programs like GCC CC1 which might have a ~33mb binary. Only a small number of those pages in the program image will ever be touched. So using our technique, they'll never become resident memory.

jart commented 1 year ago

Note that I'm running master, the cygwin branch with JIT currently just crashes without a log for every binary (either crafted by me or obtained from the o//test folder).

I recommend enabling these:

https://github.com/jart/blink/blob/8ae81a27595269685a1d395464b1127920b7f376/blink/log.h#L17-L18

trungnt2910 commented 1 year ago

Closing this, the sample mentioned in the issue works with the latest code from master.