Opinions? ELF Binary format -- weaknesses?

[coreybrenner]

Hello,

I've been kicking around an idea for a binary format which will:

a) be fat, but separable
b) maintain a data type registry, function signature registry, external reference table per function
c) provide nested symbol scoping (i.e., true package namespacing)
d) fix weaknesses in ELF
e) provide a dependency graph that a runtime loader can use to order C++ global ctors
f) provide a way to route function calls through a contract thunk, which will check the
number and types of arguments given a function against its signature, and which can
inspect the return code and ensure that it meets a contract specification, as well

The symbol tables I've designed should pretty handily smoke ELF for lookups, and I've
got the ideas for the nestable tables, disk layouts, memory layouts, appropriate fields,
and the like. The reason I began thinking about this was because of the C++ ABI that
SVR4 and similar systems (now including Linux, since a few years ago) use. I am pretty
certain that a flat linkage space is more harmful than helpful, when working with
programming languages that want to break their namespaces up logically. Name mangling,
from a developer's point of view, is disgusting and makes it harder to develop things like
program introspection, dynamic loaders, etc.

Aside from the stuff I've mentioned above, are there any opinions as to glaring weak-
nesses in ELF, which I should consider when progressing with my binary format work?

Thanks, and this seems to be a great site...

--Corey

[Solar]

The most glaring weakness of the ELF format is that you can't find any tools to work with it. No matter if we're talking compiler backend / BFD lib, disassembler, debugger, linker... you can't even find decent documentation for it.

If you manage to get your new format to adress all the above issues, you'd really have done the world of computing a favor.

(Sorry for the cynicism. )

[coreybrenner]

I haven't found a dearth of tools to work with ELF, so I suspect your whole reply was utterly cynical.

I respect that, but I wasn't looking for cynicism. I was actually looking for a real, honest critique of the ELF format, by people who work with it at a low level, and who should know the ins and outs and deficiencies that need to be addressed.

Thanks,

--Corey

[bewing]

I've been working with dynamic loading of ELF executables (runtime linking against .so objects) recently, and I've seen a handful of glaring weaknesses -- that make me want to create my own executable format to fix them. I have also seen some things over time that ELF does not address properly.

So, some random things, in random order, as they spill out of my head:

You have a file image in memory. It contains progbits which you need to load into memory now, and other data (symbol tables, string tables, a hash table, a dynamic table, etc.) that you need to keep around for later. These are stored as both/either a program header and/or a section header. The sections are referenced as section indexes and offsets inside the file image.

Big problem #1: The sections can be stored in any order, according to the spec. Assume that you have a 100MB progbits as your first section that you need to load immediately into mem at the specified phys/virtual addresses, and after the progbits is 4K of other sections. Once you've loaded the progbits, you want to compress the progbits out of the memory image. Gasp -- you can't! If you try, you mess up every offset in the header table, and all the indexes change by 1!
Answer: All the "allocatable" progbits must be defined by the spec as being at the end of the file.

Similar problem #2: The next thing you might want to get rid of at loadtime is the "everything" symbol table. Once again, the spec says it can be anywhere -- same issue. It should be located in the file just before the progbits -- at the end.

Issue #3: At compile time, not only do you need a list of the inputs with datatypes for each function in a pre-compiled library -- you need a full clobber list. This allows much more effective caller-controlled register preservation. GCC has also recently started using the concept of "maximum ranges of function input variables" -- I think it would be a good idea to store that for each function, too.

Issue #4: For debugging, I want to be able to specify a memory/register variable map, with arbitrary strings to describe the contents of each register or any memory location -- as either data, an index, or a pointer, or an arbitrary type such as a struct. I also want to be able to handle the effects of BSWAP or BSWAP64 on registers that contain any of these variables. ie. the format needs bswap flags.

Issue #5: During dynamic loading you need to use the hash table's bucket list once for each symbol. This involves doing a modulus. This is stupid and slow. The bucket list should always be automatically extended to a power of 2, which would allow you to always use an ANDed bitmask instead of a modulus.

Issue #6: There are a huge number of indexes to sections buried inside other sections. This means you cannot rearrange sections conveniently inside an existing ELF -- you have to go and fix every copy of every index.

Issue #7: this whole "only one is allowed for now, but this restriction may be lifted in future versions" crap. Don't be wishywashy! Make it ONE and stick with ONE.[\b] One has been good enough for a couple decades. Therefore it's good enough to go with forever.

Issue #8: just use one header and always put it at the beginning. Sheesh. That is, make the "program header" be a section.

Issue #9: All these wacky load-time alignment rules. The load addresses are basically sufficient to specify progbits alignment. All the sections in the file should have 8 byte alignment. Everything else in the file should be aligned as it should be in memory. If it's not, the load should fail.

Issue #10: Of course, there should only be one format -- not a separate 32b and 64b format.

Issue #11: The frigging compiler/loader should not be trying to load extra crap into memory by default. My OS does not want ANY tables loaded into specific memory addresses. Only executable code. So do not "allocate" for hash tables, dynamic tables, string tables, symbol tables, etc.

Maybe I'll write up some more later.

[Owen]

The most glaring weakness of the ELF format is that you can't find any tools to work with it. No matter if we're talking compiler backend / BFD lib, disassembler, debugger, linker... you can't even find decent documentation for it.

If you manage to get your new format to adress all the above issues, you'd really have done the world of computing a favor.

(Sorry for the cynicism. )

Single Unix Specification, libELF. Solaris and FreeBSD have implementations shipped with the OS; Linux is behind the times and needs an external library

Issue #3: At compile time, not only do you need a list of the inputs with datatypes for each function in a pre-compiled library -- you need a full clobber list. This allows much more effective caller-controlled register preservation. GCC has also recently started using the concept of "maximum ranges of function input variables" -- I think it would be a good idea to store that for each function, too.

What use is a clobber list? The library's clobbers could change, and then every application breaks. The kind of optimizations it allows are best done using whole program optimization

Issue #4: For debugging, I want to be able to specify a memory/register variable map, with arbitrary strings to describe the contents of each register or any memory location -- as either data, an index, or a pointer, or an arbitrary type such as a struct. I also want to be able to handle the effects of BSWAP or BSWAP64 on registers that contain any of these variables. ie. the format needs bswap flags.

This is something for DWARF, not ELF. DWARF already handles all the data required by debuggers for symbolic debugging. Sure, its not perfect - but you can fix it.

Issue #5: During dynamic loading you need to use the hash table's bucket list once for each symbol. This involves doing a modulus. This is stupid and slow. The bucket list should always be automatically extended to a power of 2, which would allow you to always use an ANDed bitmask instead of a modulus.

No arguments there, really (except to note that dynamic loading involves lots of IO and is slow anyway)

Issue #6: There are a huge number of indexes to sections buried inside other sections. This means you cannot rearrange sections conveniently inside an existing ELF -- you have to go and fix every copy of every index.

Why would you want to rearrange it? And how do you propose to not have references to other sections?

Issue #8: just use one header and always put it at the beginning. Sheesh. That is, make the "program header" be a section.

Thats really a non-issue.

Issue #10: Of course, there should only be one format -- not a separate 32b and 64b format.

Perhaps - but hindsight is such a beautiful thng

Issue #11: The frigging compiler/loader should not be trying to load extra crap into memory by default. My OS does not want ANY tables loaded into specific memory addresses. Only executable code. So do not "allocate" for hash tables, dynamic tables, string tables, symbol tables, etc.

Quite a lot of these things are useful for other things later (and come at no real cost - just memory map it...)

[bewing]

I disagree with Owen on these things for what I consider very good reasons, of course.

[inx]

The most glaring weakness of the ELF format is that you can't find any tools to work with it. No matter if we're talking compiler backend / BFD lib, disassembler, debugger, linker...

In the case of the GNU tools, all of this is done via the BFD lib. This makes all of these gigantic issues. I mean, it would just be so much simpler to make your own binary format if you actually had to work on all of these tools.
Damn all this code reusability making it so much harder to make standard tools work with your binary format.

you can't even find decent documentation for it.

I completely agree, it's not even remotely possible to write documentation for a new binary format. Everybody knows something has to exist for decades to have decent documentation. I mean, look at all the great, in-depth documentation for the pre-CFM Macintosh binary format, or the A/UX and Xenix binary formats. Their longevity has made for such wonderful documentation that there can be no ambiguity.

If you manage to get your new format to adress all the above issues, you'd really have done the world of computing a favor.

(Sorry for the cynicism. )

</sarcasm> Seriously, this forum is not about bettering the world of computing, never has been and never should be. It's about bettering our world of computing, and if this means we need incompatibility, so be it. Look at how well compatibility has served the x86 and Windows architectures over the years.
Also, though I don't mean to make light of anyone's (often considerable) efforts, odds are that all our projects will ever amount to is scratching our own itches. If we're in it for scratching our own itch, maybe we should be aiming for satisfaction, not hitting somewhere close to the itch and lamenting our lack of flexibility to reach the real one.

EDIT: PS. I didn't make it immediately obvious, but the first bit of my sarcasm was meant also as a pointer on how to go about this for coreybrenner

[Candy]

The one thing that I would like in ELF is fat binaries. Users don't want to consider "cpu architectures" and nonsense like that. They just want to double-click on a symbol and have it start up their game. Everything else is secondary.

Fat binaries make that much easier. You don't need to fix it in the ELF; you can fix it in a package format. The elf would just be a place I would expect such support to be. Installing a program should then diet the binary.

[coreybrenner]

The thing is, I'm familiar with ELF. I don't NEED documentation about it -- I have the header files, after all. I've written code to mmap() the files and resolve ELF symbols and do all that good junk. I've even done that for a.out, back in the day, so I could learn about the dynamic loading process.

That said, while I can tell you how these things are USED, and how and why they were designed the way they were, just like everything else, there are chinks in the armor.

I've identified a few that I'd like to fix up. I've gotten a nice list of perceived weaknesses from another forum participant, some of which I had not considered, and will now consider, along with my other ruminations. This isn't a post asking about how to DO something -- it's a post asking about how to do something BETTER. Identify the flaws, the holes in the design, of the most common binary format out there among the free and freely available systems, and discuss them.

That's what I'm asking.

The symbol table is where I've started, and have come up with a compressed radix/patricia trie idea that kills the ELF hash. It's easy to work with when building symbol tables, and can easily algorithmically be compressed into a static table with a depth-first traversal. mmap() that table, and your symbol lookups fairly fly.

See? I know how it's done NOW. I want to know where the current state of the art falls short, so that it can be done BETTER.

There's no reason a competently engineered standard, which fixes problems with the current standard, cannot eventually gain traction. Make it friendly for programmers and compiler, library and tool writers. Write loaders for existing systems. Heck... work out a set of binutils that produces this file format, and build a Linux distro around it as a display of the technology. If the binary standard does indeed meet a need for programmers and tool writers, and proves more performant when stacked against ELF, et al, why shouldn't it make inroads?

--Corey

[Candy]

The symbol table is where I've started, and have come up with a compressed radix/patricia trie idea that kills the ELF hash.

... and proves more performant when stacked against ELF...

Unless I'm mistaking, a hash is average time O(1) with worst-case O(n) versus a radix/patricia trie being O(log n) both average & worst-case timing. So, you've slowed the average case to avoid a worst-case?

Doesn't sound performant on average. Care to explain why?

[Owen]

The symbol table is where I've started, and have come up with a compressed radix/patricia trie idea that kills the ELF hash.

... and proves more performant when stacked against ELF...

Unless I'm mistaking, a hash is average time O(1) with worst-case O(n) versus a radix/patricia trie being O(log n) both average & worst-case timing. So, you've slowed the average case to avoid a worst-case?

Doesn't sound performant on average. Care to explain why?

Because Elf's hash table pretty quickly moves away from best case - and its worst case is often pathological due to C++ name mangling creating long common prefixes. Particularly for the case of C++ libraries a tree structure is a good idea

[Candy]

Because Elf's hash table pretty quickly moves away from best case - and its worst case is often pathological due to C++ name mangling creating long common prefixes. Particularly for the case of C++ libraries a tree structure is a good idea

If that's the case I'd rather have a good hash instead. Why didn't they pick md5 or such?

[coreybrenner]

Radix tree is O(K) in the number of bits in the symbol. But so is the hash table.

The thing about it is the way that the comparison shakes out:

Given a symbol name, you can inspect, for example, bit 3, bit 9, bit 30, bit 84 of the symbol itself. This keeps the cache hot. Based upon this inspection, and moving down the static table which, if constructed correctly should be moving into the cache fairly sequentially, so prefetch can be triggered before the bit comparison takes place. At any time along the path, the symbol can be rejected. Once you've reached a place where you may have found a matching symbol, you perform exactly one comparison. If it matches, Bob's your uncle. If not, move along to the next library.

Contrast that with the ELF hash, where you read through the whole symbol first, applying a hash transformation on it to produce a key. You've now done O(K) work in the hash table, to start with. Now, you take the modulus of the key against the number of buckets. This brings you to a list of possible matches, since they're not using a perfect hash algorithm for constructing each symbol table. I don't remember now whether the ELF hash stores the key in the hash (but if not, this scenario becomes worse.) You traverse the bucket searching for a matching key. Upon finding a matching key, you perform the comparison against your own symbol. You've now done approximately the same amount of work as the radix tree implementation. Except you might have had a true hash collision, so if that symbol is rejected, you must continue to the end of the bucket inspecting keys and then comparing symbols if you have a match. If, by the end of the bucket, you've found no match, your symbol is rejected.

The runtime of the ELF hash isn't bad, but a radix tree is better.

--Corey

[coreybrenner]

As to why they didn't pick MD5 or similar...

If I'm not mistaken, the transformation of data through the MD5/SHA/whatever hash scheme is very much more compute intensive than the very simple transformation done by the ELF hash. Also, the ELF hash yields a 32bit sum, which is easily operated upon with standard integer instructions (modulus), where you'd have to write a lengthy routine to take the modulus of an MD5 hash. Once you've determined a bucket by way of the long modulus routine, you have to traverse it comparing hash keys. MD5 keys are what, 40 bytes long? Longer, by far, than the average symbol name (especially in a C program or library.) Then, you still have to take into account the possibility, however unlikely, of a collision in MD5/SHA space. You must compare the symbols themselves. And if they do not match, you still have to continue down the bucket.

With MD5, you've drastically increased the time it takes to look up a symbol. Unless you've figured out a way to take an MD5 sum of a symbol name, and somehow perform an instant lookup, you still have to slog through it. In this case, you'd be better off sticking the MD5'ed symbols in a radix tree, where the operations to find bit differences are fairly cheap and, since it's a fixed-length bit string, it can be optimized versus the pure string-based radix lookup. But, then, you've done the MD5 transformation on the symbol to produce the key, and you'd still need to consider an MD5 collision, so you'd have to perform an MD5 comparison, and then a symbol comparison. Much better to use a radix tree with the symbol names themselves.

--Corey

[coreybrenner]

It occurs to me why they are not using a power-of-two for the ELF hash table lengths. On average, you'll get a better bucket distribution if you take the modulus of a hash key against a prime number.

--Corey