Rate my object format and ABI

[Korona]

Looks mostly good. I did not read the entire relocation process though. Some comments:

• You're using the same hash function as ELF. That function performs notoriously bad. In my compiler stack, I noticed that sometimes the chain lengths are extremely skewed (e.g. 50% of all symbols are in a single chain).
• The major bottleneck of ELF relocation is the fact that it needs to search O(n) DSOs to find a symbol (compare that to the O(1) operations that are required to search for the symbol inside a DSO). If I were to design a new binary format, I'd make the providing DSO part of the symbol so that only one DSO needs to be searched.
• Why did you choose to use a __init() function instead of a more flexible .init_array mechanism? IIRC, GCC (for example) does not even support __init() on x86_64 (and unconditionally sets --enable-initfini array in configure.ac unless you're cross-compiling) because of stack alignment issues: it's not enough to concat multiple functions to a single __init(), a modified prologue would need to be emitted to realign the stack. I'd do it the other way around -- get rid of __init and only use .init_array.
• I'd consider renaming your SYM_SCOPE_WEAK to something else (SYM_SCOPE_OVERRIDABLE?). In the context of ELF, a weak symbol is a symbol that is allowed to be missing, it is not a symbol that can be overriden by a global one. For ELF, if symbol X is defined weakly in DSO A and globally in DSO B and A < B in the resolution order, the weak definition in A will override the global definition in B. (This is the source of a lot of confusion by people encountering ELF for the first time, partially due to buggy implementations in early glibc versions.)
• Also be aware that your definition of weak symbols requires Omega(n) DSO lookups -- all DSOs need to be searched for an overriding global symbol. (Copy relocations prevent this issue for ELF.)
• Can the ABI support varargs?

EDIT: To demonstrate why the second point is an issue, let's look at the seemingly lightweight gedit application, check how many DSOs it requires and how many relocations need to be done:

Code: Select all

$ ldd /usr/bin/gedit | wc -l
78
$ ldd /usr/bin/gedit | cut '-d ' -f3 | xargs readelf -r | grep R_X86_64_GLOB_DAT | wc -l # Looking at GLOB_DAT should be enough, although this misses some other relocation types that also refer to symbols.
8745

In the worst case, those 8745 relocations need to be looked up in all 78 DSOs! If DSOs are part of the symbol name, this cost is decreased considerably.

[Korona]

If you generate the prologues etc. correctly, __init() should work of course. I think I'd still consider .init_array slightly cleaner as it requires no linker magic or correct order of input files. But that might be mostly personal taste.

For the hash function: this StackOverflow post has some comparison. AFAIK Python used FNV in the past with reasonably good results. DJB2 probably offers a good tradeoff between simplicity and quality. SipHash (SSE/AVX implementation by Google) is a high quality hash function while still performing surprisingly good (~3 cycles per byte for 64-byte strings, according to the original paper). However, its resistance against denial-of-service (by producing strings that intentionally hash to the same value) requires storing a key and is not needed in this context.

Out of curiosity, how many symbols does your libc contain in this example with 512 buckets?