Support emitting more than 0x10000 functions in a file

[zhuowei]

I tried to generate an ELF object with 65536 functions with faerie and received an integer overflow error in debug mode when faerie calculates the number of sections (src/elf.rs:571) In release mode, faerie simply generates an invalid .o file.

Is it possible for faerie to generate less ELF sections/avoid generating a separate section for each function, so it can generate larger files?

Test code and crash log:

extern crate faerie;
#[macro_use]
extern crate target_lexicon;
use faerie::*;
use std::fs::*;
use std::path::*;
use std::str::FromStr;
fn main() {
  let name = "test.o";
  let file = File::create(Path::new(name)).unwrap();
  let mut obj = ArtifactBuilder::new(triple!("x86_64-unknown-unknown-unknown-elf"))
    .name(name.to_string())
    .finish();
  for i in 0..0x10000 {
    let n = format!("func{}", i);
    let decl:Decl = Decl::function().global().into();
    obj.declare(n, decl).unwrap();
  }
  for i in 0..0x10000 {
    let n = format!("func{}", i);
    obj.define(n,
      vec![0xcc]).unwrap();
  }
  obj.write(file).unwrap();
}

$ RUST_BACKTRACE=1 target/debug/ReproFaerie 
thread 'main' panicked at 'attempt to add with overflow', /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/elf.rs:571:9
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:70
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:58
             at src/libstd/panicking.rs:200
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:215
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:478
   5: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:385
   6: rust_begin_unwind
             at src/libstd/panicking.rs:312
   7: core::panicking::panic_fmt
             at src/libcore/panicking.rs:85
   8: core::panicking::panic
             at src/libcore/panicking.rs:49
   9: faerie::elf::Elf::add_progbits
             at /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/elf.rs:571
  10: faerie::elf::Elf::add_definition
             at /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/elf.rs:516
  11: faerie::elf::to_bytes
             at /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/elf.rs:889
  12: faerie::artifact::Artifact::emit_as
             at /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/artifact.rs:450
  13: faerie::artifact::Artifact::write_as
             at /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/artifact.rs:473
  14: faerie::artifact::Artifact::write
             at /home/zhuowei/.cargo/registry/src/github.com-1ecc6299db9ec823/faerie-0.10.0/src/artifact.rs:468
  15: ReproFaerie::main
             at src/main.rs:24
  16: std::rt::lang_start::{{closure}}
             at /rustc/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/rt.rs:64
  17: std::panicking::try::do_call
             at src/libstd/rt.rs:49
             at src/libstd/panicking.rs:297
  18: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:87
  19: std::rt::lang_start_internal
             at src/libstd/panicking.rs:276
             at src/libstd/panic.rs:388
             at src/libstd/rt.rs:48
  20: std::rt::lang_start
             at /rustc/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/rt.rs:64
  21: main
  22: __libc_start_main
  23: _start

[m4b]

Haha, awesome bug find! :)
So I thought that ELF supported > u16 sections in the elf header by marking u16::MAX_VALUE as a sigil value meaning look for the actual number elsewhere (in the first section), but maybe I'm just imagining/confusing it with something else.

If that isn't the case then:

1. I think the only option forward is to disable essentially -ffunction-sections in our backend.

This could be straightforward, or more difficult, not sure yet; I'm guessing harder, since I think we assume function sections throughout, but like I said, not exactly sure.
We'd also have to expose the option in the artifact builder, etc.

Anyway, yes it's something we should fix (or at least fail in a controller manner instead of overflow bugs causing mayhem in release code), but it is slightly niche, since i think it's somewhat unusual for a single compilation unit to have 65k functions.

Anyway, great find though!

[zhuowei]

@m4b Whoa, thank you so much for the super fast response during a holiday!

I'm currently trying to compile a really large WASM file using Fastly's Lucet, which emits the entire translated .wasm as one single .o file - that's how I ran into this.

You're probably right about the extra sections magic value.

(Edit: see http://man7.org/linux/man-pages/man5/elf.5.html and search for SHN_LORESERVE)

Clang can emit a .o file with all sections when I compile a .c file with 0x10000 functions. readelf correctly finds all 65545 sections in the result:

$ clang -ffunction-sections -o hostHuge2.o -c huge.c
$ readelf -a -W hostHuge2.o |less
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          9164352 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         0 (65546)
  Section header string table index: 1 <corrupt: out of range>

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            0000000000000000 000000 01000a 00      0   0  0
<snip>
  [65535] .text.func65532   PROGBITS        0000000000000000 100000 000006 00  AX  0   0 16
  [65536] .text.func65533   PROGBITS        0000000000000000 100010 000006 00  AX  0   0 16
  [65537] .text.func65534   PROGBITS        0000000000000000 100020 000006 00  AX  0   0 16
  [65538] .text.func65535   PROGBITS        0000000000000000 100030 000006 00  AX  0   0 16
  [65539] .text.main        PROGBITS        0000000000000000 100040 000008 00  AX  0   0 16
  [65540] .comment          PROGBITS        0000000000000000 100048 000037 01  MS  0   0  1
  [65541] .note.GNU-stack   PROGBITS        0000000000000000 10007f 000000 00      0   0  1
  [65542] .eh_frame         X86_64_UNWIND   0000000000000000 100080 1c0038 00   A  0   0  8
  [65543] .rela.eh_frame    RELA            0000000000000000 640128 180018 18     65544 65542  8
  [65544] .symtab           SYMTAB          0000000000000000 2c00b8 300060 18      1 65539  8
  [65545] .symtab_shndxr    SYMTAB SECTION INDICIES 0000000000000000 5c0118 080010 04     65544   0  4
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

There are no section groups in this file.

There are no program headers in this file.

There is no dynamic section in this file.

[zhuowei]

@m4b According to https://docs.oracle.com/cd/E37838_01/pdf/E36783.pdf p373, to support more than SHN_LORESERVE (0xff00) sections:

• we have to emit 0 in the header's e_shnum
• write the actual section count into the first section's sh_size
• then emit an extended symbol table, SHT_SYMTAB_SHNDX

I can try doing the first two, but the last seems complicated.

[m4b]

That's a start. We should also update phdrs, and strtab with same logic, it looks like it just places all the real values in the first null entry of the section table headers. Will have to investigate SHT_SYMTAB_SHNDX issues; may be able to get away with it? Not sure; anyway feel free to pickup that PR, or base some stuff off of it if you feel like giving it a try :)

[zhuowei]

@m4b I tried doing something similar and hit this assert: https://github.com/m4b/faerie/blob/master/src/elf.rs#L115

So it looks like we do need the extended symbol table. I'll try to look into this tomorrow, but I'm not too familiar with how to generate ELF.

Thank you so much!

[zhuowei]

@m4b I tried adding a sections indices table and it just completely broke readelf and llvm-objdump:

https://github.com/swiftwasm/faerie/tree/i-cant-implement-shndxr

So I guess I don't know how to implement this - is there any other ways I can help?

  [65539] .symtab_shndxr    SYMTAB SECTION INDICIES 0000000000000000 010040 04000c 04      2   0  4
  [65540] .note.GNU-stack   PROGBITS        0000000000000000 000000 000000 00      0   0  1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

There are no section groups in this file.

There are no program headers in this file.

There is no dynamic section in this file.

There are no relocations in this file.

The decoding of unwind sections for machine type Advanced Micro Devices X86-64 is not currently supported.

Symbol table '.symtab' contains 131075 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name

No version information found in this file.

[m4b]

@zhuowei it's hard to see without a PR showing the diff, but it looks like you were close? As I think you've discovered, these kind of things are extremely brittle, and minor changes can make object file parsers explode :D On the other hand, it can be misleading, because with a minor change here or there, the whole thing might start working 😆
If you want to keep at it, that's fine of course, or if you're too busy, that's cool too :) I can take a look this weekend, might be easier if you pushed your changes into a PR so I can see what you did?

[zhuowei]

@m4b PR opened.

This is my first time working with Rust code outside the Rust tutorial, and the ... third? time I ever tried to emit an ELF file, so I'm sorry in advance for the code. I suspect there's probably a cleaner way to generate the extra table.

Thank you so much for your work on this project. Getting this to work is probably beyond my current abilities, so I'll really appreciate it if you can take a look at this issue.

PS: for future reference: GitHub lets you open pull requests using other people's branches if you want a diff view.

[m4b]

Well hey welcome ! :) thanks for the tip did not know could open PRs using other branches ! I’ll take a look soon and thanks for your work :)

[zhuowei]

This was solved by #78 - closing. Thank you so much for fixing this!