native_client/docs/initial_dynamic_load.md

   1 # Loading the dynamic linker and executable
   2
   3 _Draft_
   4
   5 ## Overview
   6
   7 This document discusses how address space should be laid out when a dynamic
   8 linker and an executable are loaded, and how this can be orchestrated with
   9 sel\_ldr and its associated in-browser interface.
  10
  11 ## Background
  12
  13 On a typical ELF system such as Linux, the kernel is normally responsible for
  14 loading both the executable and the dynamic linker. The executable is invoked by
  15 filename with execve(). The kernel loads the executable into the process, and
  16 looks for a PT\_INTERP entry in its ELF Program Headers; this specifies the
  17 filename of the dynamic linker (/lib/ld-linux.so.2 for glibc on Linux). If there
  18 is a PT\_INTERP entry, the kernel loads this file too.
  19
  20 Either of these two ELF objects can be relocatable (ET\_DYN) or require loading
  21 at a fixed position in address space (ET\_EXEC). Most often, the dynamic linker
  22 is relocatable and the executable is fixed-position with a standard base address
  23 (0x08048000 on i386). Sometimes the executable is relocatable too (these are
  24 known as PIEs - position-independent executables). For relocatable objects, the
  25 kernel chooses the load address.
  26
  27 There is another way to load the two ELF objects: the dynamic linker can be
  28 invoked directly with execve(). If passed the filename of an executable, the
  29 dynamic linker will load the executable itself.
  30
  31 There are two ways in which we might wish to do this differently in Native
  32 Client's `sel_ldr`.
  33
  34 ### Finding the dynamic linker
  35
  36 The Linux kernel looks up PT\_INTERP in a file namespace. In NaCl, however,
  37 there is no built-in filesystem so it is not appropriate for `sel_ldr` to
  38 interpret the PT\_INTERP filename (see AcquiringDynamicLibraries). The second
  39 method -- invoking the dynamic linker directly -- is more appropriate to NaCl.
  40
  41 ### Address space allocation
  42
  43 The Linux kernel makes address space allocation decisions: * Allocation
  44 decisions have varied between versions of Linux. Sometimes libc.so and ld.so are
  45 placed below the executable, sometimes above. Additionally, recent Linux
  46 versions perform address space randomisation. * The heap (`brk()`-allocated
  47 memory) goes after whichever object was invoked with execve(). Normally it does
  48 not matter whether this is ld.so or libc.so. (The one exception I have
  49 encountered is where invoking an old version of Emacs through ld.so failed,
  50 because it caused the heap to be placed at a top-bit-set address, and Emacs
  51 wanted to use the top address bit for GC purposes.)
  52
  53 In Native Client, for portability and testability reasons, ideally we do not
  54 want address space allocation decisions to change between versions of NaCl. We
  55 want behaviour to be as deterministic as possible.
  56
  57 Furthermore, address space is likely to be more constrained under NaCl, both
  58 quantitatively (a 1GB limit) and qualitatively (a code/data split -- see
  59 DynamicLoadingOptions).
  60
  61 For these reasons, it may be better to leave load address choices to untrusted
  62 code.
  63
  64 ## Possible layouts
  65
  66 *   Load ld.so at 0x20000 (the bottom of available address space).
  67     *   This is simple and involves only minimal changes to `sel_ldr`. However,
  68         it does not take advantage of the relocatability of ld.so.
  69     *   We could pick a larger standard address at which to load the executable,
  70         e.g. 0x01000000 (16MB). This places limits on how big ld.so and the
  71         executable can grow, though not severe limits.
  72     *   Alternatively, we could attempt to place the executable at the top of
  73         the code region, so that executables grow downwards from 256MB. Hence we
  74         have a standard executable end address rather than a standard start
  75         address. This would require linker changes. It involves fixing knowledge
  76         of the code region size in executables.
  77 *   Load the executable at 0x20000 and either:
  78     *   load ld.so immediately above, or
  79     *   load ld.so at the top of the code region.
  80
  81 ### Heap placement
  82
  83 If we adopt the Big Segment Gap scheme, address space looks like this: *
  84 0-256MB: ELF code segments can mapped here * 256-512MB: ELF data segments are
  85 mapped here It may be desirable to place the heap at 512MB so that its expansion
  86 does not limit, and is not limited by, mapping of libraries.
  87
  88 If ld.so is loaded at a high address, we can arrange for the heap to start just
  89 before 512MB, at the end of ld.so's data segment's BSS, reusing an otherwise
  90 wasted page and saving upto 4k or 64k.
  91
  92 ## Interface 1: sel\_ldr loads both
  93
  94 We could change sel\_ldr to load two ELF objects instead of one, in order to
  95 load both the executable and dynamic linker. The interface for starting a NaCl
  96 process could take two file descriptors.
  97
  98 This involves adding extra complexity to the trusted codebase. Later options
  99 show that this is not necessary.
 100
 101 ## Interface 2: sel\_ldr loads ld.so
 102
 103 sel\_ldr can load ld.so, which in turns loads the executable. This requires
 104 little or no change to sel\_ldr.
 105
 106 Suppose we load ld.so at the bottom of address space, at 0x20000. This is where
 107 statically linked, ET\_EXEC executables are loaded at the moment; sel\_ldr
 108 currently only supports loading such executables. There are two ways to
 109 implement loading ld.so at this address: * Change sel\_ldr to support loading
 110 ET\_DYN executables (such as ld.so), but load them with the fixed address of
 111 0x20000. This is a small change. * Link ld.so as ET\_DYN but rewrite its ELF
 112 headers in a post-link step to be ET\_EXEC with a load address of 0x20000.
 113
 114 Alternatively, we could load ld.so at a higher address. sel\_ldr could take an
 115 extra parameter to specify the ELF object's load address, or it could default to
 116 loading the object at the highest possible address in the code region.
 117
 118 ### ld.so's PHDRs
 119
 120 ld.so normally contains ELF Program Headers that are currently rejected by
 121 sel\_ldr, in particular `PT_DYNAMIC`, `PT_GNU_EH_FRAME` and `PT_GNU_RELRO`.
 122 (`objdump -x /lib/ld-linux.so.2` also lists `PT_GNU_STACK`, but this is not
 123 relevant to NaCl because the stack is never executable.) Again there are two
 124 ways to deal with these, depending on how much we want to change sel\_ldr: *
 125 Change sel\_ldr to ignore unrecognised Program Headers. This has no security
 126 implications. It is what most ELF loaders do. Most ELF executable loaders look
 127 only at `PT_LOAD` headers. * Change ld.so so that it does not contain the
 128 headers that sel\_ldr does not like. As before, this can be done as a post-link
 129 step, so that we do not have to modify the linker to omit `PT_DYNAMIC` etc. when
 130 linking with `-shared`.
 131
 132 These headers have two uses: * ld.so can read them during initialisation.
 133 Currently, only the non-essential `PT_GNU_RELRO` is used this way. ld.so locates
 134 the `.dynamic` section statically via the symbol `_DYNAMIC` rather than by
 135 searching for `PT_DYNAMIC`. * They can be returned by libc's public interface
 136 `dl_iterate_phdr()`, which is useful for garbage collectors, debuggers, etc.
 137
 138 The ELF Program Headers are normally included at the start of the ELF object's
 139 text segment. We cannot do this under NaCl, because this data will not validate
 140 as code. But we also cannot move the Program Headers to the data segment
 141 because, while in principle they can live at any offset in the ELF file, it is
 142 only at the start of the file that file offsets are the same as in-memory
 143 offsets. glibc's ld.so is taking a shortcut by assuming that it can find its own
 144 Program Headers in memory at runtime using `e_phoff` from its own ELF header.
 145
 146 If we want to support a `dl_iterate_phdr()` that lists ld.so (which could be
 147 desirable for debugging tools), we will probably need to copy ld.so's Program
 148 Headers into ld.so's data segment as a post-link step. This is a small point and
 149 may not be important.
 150
 151 ## Interface 3: move ELF parsing out of sel\_ldr
 152
 153 Instead of passing an ELF executable to sel\_ldr, the invoker can pass a list of
 154 mapping instructions. Each instruction specifies a code or data segment to
 155 map/copy into memory. The primary difference from ELF loading is that each
 156 segment can come from a different file.
 157
 158 This arrangement means that ELF parsing can be moved out of the trusted
 159 codebase. ELF parsing could be done by untrusted NaCl code or Javascript code.
 160 Doing this in Javascript would avoid bootstrapping problems. Using Javascript
 161 for this should not be a performance problem because, even though Javascript's
 162 string manipulation facilities are limited, the task is simple and ELF Program
 163 Headers comprise only a small amount of data.
 164
 165 This scheme means we do not need to worry about whether sel\_ldr supports
 166 ET\_DYN executables or whether it rejects Program Header entries that it does
 167 not recognise.
 168
 169 The main advantage of this scheme is not so much the reduction in trusted code
 170 (instead of parsing ELF, we parse a different format), but the increase in
 171 flexibility. It reduces the need to bootstrap a process from inside the process.
 172
 173 "sel\_ldr" would no longer be an accurate name because it would no longer be an
 174 ELF loader!
 175
 176 ## Passing arguments from the web browser
 177
 178 If the dynamic linker is responsible for loading the executable, it requires a
 179 mechanism for receiving either the filename of the executable (which it can pass
 180 to open(), which works as described in AcquiringDynamicLibraries) or a file
 181 descriptor for the executable.
 182
 183 The traditional way to pass a filename is via a Unix-style argv list of strings
 184 (as used in `main()`/`execve()`). This is such a widely used interface that it
 185 would make sense to support it in NaCl. Currently `sel_ldr` supports passing
 186 argv to the NaCl process, but this is not exposed in the browser interface. We
 187 have a number of options for supporting argv from the browser:
 188
 189 *   `launch_with_argv()`: Provide a Javascript method for launching a NaCl
 190     process that takes an argv list-of-strings parameter (as in [the prototype
 191     implementation](AcquiringDynamicLibraries#Prototype_implementation.md)).
 192 *   Generic IMC messages: On startup, the NaCl process does `imc_accept()` +
 193     `imc_recvmsg()` to receive a message containing argv, which Javascript code
 194     must send.
 195 *   Generic startup message: Allow Javascript code to provide a blob of data to
 196     copy into the NaCl process on startup. This dovetails with interface 3 above
 197     in which Javascript code specifies segment layout in detail.
 198     *   This could be a blob with which to initialise the stack. argv and envp
 199         are stored at the top of the stack on ELF systems. This data structure
 200         contains pointers, so whoever provides the blob needs to know what
 201         address it will be loaded at.
 202     *   The blob could contain argv and envp in some other format.
 203
 204 `launch_with_argv()` has the disadvantage that it introduces a new type of
 205 message that is only used in the special case of process startup.
 206
 207 If we use generic messages to supply argv, we might want to remove the existing
 208 argv mechanism from `sel_ldr` so that NaCl does not have two competing
 209 mechanisms for argv.
 210
 211 ## Initial load using existing interfaces
 212
 213 Here is how the initial load can be done using existing browser interfaces where
 214 possible:
 215
 216 HTML: `<embed src="path/to/ld.so.2" type="application/x-nacl-srpc"/>
 217 `
 218
 219 Javascript: `nacl_elt.startup_argv(["arg0", "path/to/executable", "arg1",
 220 "arg2"])
 221 `
 222
 223 ld.so code in NaCl process: `fd = imc_accept(initial_fd); message =
 224 imc_recvmsg(fd); // decode argv from message // continue rest of startup using
 225 argv
 226 `
 227
 228 *   ld.so is ET\_EXEC with a start address of 0x20000.
 229 *   executable is ET\_EXEC with a start address of 0x1000000.