zero-copy elf

[m4b]

Like incoming mach parser, add "zero-copy" implementation to elf.

E.g.:

https://github.com/m4b/goblin/blob/better_mach/src/mach/mod.rs#L21-L33

This will require removal of try_from api for taking owned fd and creating struct, as well as updating the Strtab's to use the lifetime of the Elf struct, and a couple more optimizations we can perform.

In addition, might be nice to add Exports, Imports, and relocations for lazy parsing, but that can be a future issue.

[le-jzr]

I can't help but notice that the Mach parser still contains vectors, which means heap allocations. Isn't it possible to make a parser that doesn't use heap at all? Osdev interested person here. :-P

[m4b]

@le-jzr hello!

Zero copy was in quotes ;)

So before I get into the fine grained nature of this, and please don't take this as me explaining to you things, as some or all you probably already know, just clarifying the terms but:

1. Zero copy doesn't necessarily mean no allocations, just means we don't copy things when we don't strictly need to. Strings and block delimited things a prime example (The Mach export trie walker is an excellent example of this - the name must be allocated because it's non-contiguous.)
2. Vectors are so nice and easy
3. We could make the load commands parser not allocate but why ?

Last point I'm actually interested in your use case, are you:

1. Writing a Mach-o loader for a kernel?
2. Writing a Mach dynamic linker ?
3. Want a zero-allocation parser (for use in some no std environment)

So 3 seems very unusual, and I can't think of a single use case. E.g., why are you doing binary analysis on a machine that can't allocate ?

From a theoretical perspective it could be fun, but I simply don't have the time to think up and write up a good API which doesn't allocate, is easy to use, and works well.

Of course I will consider any PR that does! So you're welcome to post suggestions or tinker around with a form that does.

For 2., OS X dyld allocates - at the very least it needs an array of libraries which gets indexed by imports. Similarly the Linux dynamic linker also allocates for the library array (and a whole bunch of other shit). Either that or every time someone indexes the libs, it iterates through the load commands, counts lib commands, and stops at the correct lib command. But this is literally linked list indexing :]

Importantly though, it doesn't allocate a vector for the load commands because it's not providing them to a consumer - it is the consumer of the load commands! So it can iterate through the bytes and perform the command as required, and then forget about them - e.g. no allocation required. But the parser makes no such assumption - it provides the post-parsed out structure for a consumer.

On this note it would be pretty easy to manipulate the load commands if we simply read them in native byte order. But we don't. In principle, the parser will correctly read them on a big median machine intended for a little endian kernel/loader.

Nevertheless I suppose we could introduce an iterator API for the load commands which takes the byte array at an offset and returns an interpreted load command for consumption, but it would only be iterable. I have an unpublished crate which generalizes this idea, but I never got around to using it. This might be the best approach and again I'm willing to merge any pr which does this cleanly but I simply don't have the time to work on it.

But again we may want to pause and ask what's all the work for. There are at most 15-20 load commands which is just such a trivial allocation it won't even show up in benchmarks is my guess ...

On the other hand, If you're writing a kernel loader or some kind usually the loader reads the fat header, selects the architecture that is valid for its arch that it's loading and then casts the header bytes and performs basic sanitization on it, and then memmaps the bytes as per the offset and size given by the fat header and sends it to whatever needs them.

So you don't really need a parser for this, let alone an endian aware one.

So again, I'm curious what the actual use case you have is for a non-allocating, zero copy, endian aware 32 AND 64 bit Mach parser, for use in some kind of os dev...? Perhaps some kind of binary translation framework ?

[le-jzr]

I see I badly formulated my question. I didn't intend to make you write up such an extensive reply. :)
First off, I have no use for Mach parser in particular, only seeing it as template for the others. My real motivation is about reading ELF files early in boot process, when there is no heap available.

While you don't really need a parser for it, some kind of safe generic code seems way better than something that's essentially unsafe-powered direct translation of C (otherwise why bother using Rust at all?). And if it can be part of a library that's used by multiple different projects, then all the better, as bugs get found faster that way.

[le-jzr]

As you pointed out, taking advantage of assumptions like native endianity makes things vastly simpler, so the real question is whether that simplification warrants a separate code base that does essentially the same thing. I suspect it does, but you'd have more experience to answer it. :)

[m4b]

Ah I see what you mean now. You want an Elf like struct which you create via some bytes and it returns the parsed out structure, and with whatever endianity the machine is, with ideally no allocation AND lazy parsing if possible.

So the parser here was always intended to be used for arbitrary endianity.

A native endian elf parser is easily possible, with very likely zero allocation as well. For an example of this I think the SharedObject struct in image.rs in https://github.com/m4b/dryad is a close candidate for this, but specifically geared towards shared libraries. But it's not lazy ( because it uses everything)

It's an interesting idea though, will think about this

[m4b]

This is basically done; can add lazy relocation parsing later, via another issue