Page MenuHomePhabricator

Initial (incomplete) implementation of JITLink - A replacement for RuntimeDyld.
Needs ReviewPublic

Authored by lhames on Feb 26 2019, 5:49 PM.

Details

Summary

JITLink is a jit-linker and performs the same high-level task as RuntimeDyld:
it parses relocatable object files to make their contents runnable in a target
process.

JITLink aims to improve on RuntimeDyld in two primary ways:

(1) A clear design intended to maximize code-sharing while minimizing coupling.

RuntimeDyld has been developed in an ad-hoc fashion for a number of years and
this had led to intermingling of code for multiple architectures (e.g. in
RuntimeDyldELF::processRelocationRef) in a way that makes the code more
difficult to read, reason about, extend.

(2) Native support for asynchronous linking, where the symbol resolution and
finalization steps call back to linker continuations to complete the linker's
work. This allows for cleaner interoperation with the new concurrent ORC JIT
APIs, while still being easily implementable in synchronous style where
asynchrony is not needed.

To maximise sharing, the design has a hierarchy of common code:

(1) Generic atom-graph data structure and algorithms (e.g. dead stripping and

memory allocation) that are intended to be shared by all architectures.

+ -- (2) Shared per-format code that utilizes (1), e.g. Generic MachO to

|  atom-graph parsing.
|
+ -- (3) Architecture specific code that uses (1) and (2). E.g.
         JITLinkerMachO_x86_64, which adds x86-64 specific relocation
         support to (2) to build and patch up the atom graph.

To support asynchronous symbol resolution and finalization, the callbacks for
these operations take continuations as arguments:

using JITLinkAsyncLookupContinuation =
    std::function<void(Expected<AsyncLookupResult> LR)>;

using JITLinkAsyncLookupFunction =
    std::function<void(const DenseSet<StringRef> &Symbols,
                       JITLinkAsyncLookupContinuation LookupContinuation)>;

using FinalizeContinuation = std::function<void(Error)>;

virtual void finalizeAsync(FinalizeContinuation OnFinalize);

In addition to supporting the top-level design goals, JITLink also aims to fix
a number of nitpicks. The first of these (which appears in this patch) is GOT
and stub handling: RuntimeDyld's limited 'stub management' utility allows for
the creation of stubs OR GOT entries but not both, preventing the small-code
model from being implemented on some architectures (e.g. x86-64). JITLink
addresses this by allowing mutations on the atom graph prior to finalization,
which can be used to build both GOT entries and stubs.

This patch is incomplete, but I'm posting it now to allow for early feedback.
Once it is ready to land in-tree, my aim will be to develop JITLink to the point
where it could replace RuntimeDyld for MachO, then (time permitting) look at
tackling COFF and ELF too, though I will be hoping to enlist support for those
formats as I am less familiar with them.

Diff Detail

Event Timeline

lhames created this revision.Feb 26 2019, 5:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 26 2019, 5:50 PM

My main concern with this design is how you plan to integrate this with the existing infrastructure. Are you planning on laying this under RuntimeDyLD? Or somehow factoring out common implementation to be used by both? I'm generally bothered by the seeming duplication of such a fragile piece of infrastructure.

Since you're rewrite this, is there any potential for sharing code with lld? Relocating instructions should essentially be the same between these two.

ruiu added a subscriber: ruiu.Mar 1 2019, 3:18 PM

Since you're rewrite this, is there any potential for sharing code with lld? Relocating instructions should essentially be the same between these two.

I haven't read this patch, but as a general comment, I could say that a static linker is fairly different from a JIT linker. A JIT linker is probably more close to a dynamic linker (or a loader) than a static linker. They are situated at different stages of making a program. In the pipeline of (1) compile, (2) link, (3) load and run, the static linker is the second stage and the dynamic loader and perhaps a JIT linker are the third. So, even though we call the second and the third stage "linker", they are not too similar. Even the relocation handling is pretty different -- a static linker reads relocations and possibly creates dynamic relocations if relocations cannot be resolved at link-time. A static linker may also create GOT/PLT entries and other data structures. All of them are not needed if you are creating an in-memory image of an executable. So a JIT linker and a static linker are naturally fairly different, and I don't think it is very easy to find large commonality between them.

I was actually thinking about handling of target-specific relocations, and applying them to instructions. We used to have a large chunk of auto-generated code that did that. The implementation in lld is much shorter, so it's probably not a big deal if it needs to be repeated.

ruiu added a comment.Mar 1 2019, 3:48 PM

I was actually thinking about handling of target-specific relocations, and applying them to instructions. We used to have a large chunk of auto-generated code that did that. The implementation in lld is much shorter, so it's probably not a big deal if it needs to be repeated.

Yeah, applying a target-specific relocation is essentially just one line of code per a relocation type in lld, and given that the types of relocations that a JIT linker has to handle is more limited than a static linker, the duplication is pretty limited.

(food for thought, not a "this must be answered now" sort of thing, but "Generic atom-graph data structure and algorithms " does sound a bit like the original LLD design, which didn't turn out to be a great fit (at least the way it ended up) for ELF, at least - any ideas on what might be done differently to avoid the same situation here when adding ELF support down the line? (my naive perspective is that the mismatch was around slicing up ELF sections into MachO-like atoms on symbol boundaries was the mismatch - rather than adding support for an atom with multiple symbols (that may not be at the start of the atom) and then having a one atom to one ELF section mapping))

include/llvm/ExecutionEngine/JITLink/JITLink.h
224–225

Might be able to get away without having specific begin/end accessors - everyone can use the range accessor instead?

(similar feedback for other range accessors in this patch)

253–254

Any chance this container could be one of unique_ptr? I guess DenseSet doesn't support that? Could it?

455

Should this be 'mutable' (since it's modified from a const member function like "getAddrToAtomMap() const")?

Also, I'd tend to implement the non-const version of a function in terms of the const version, rather than the other way around. That way if the object is actually const, the code doesn't hit UB.

(currently calling getAddrToAtomMap() on an actually const object would be UB)

lib/ExecutionEngine/JITLink/JITLink.cpp
58–60

Could use

= default?

here. No big deal, but might give the frontend extra info about the triviality, etc.

lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
231–235

This leaks or double frees if this lambda is either not called, or called more than once.

Perhaps it'd be worth using shared_ptr here for simplicity/robustness?

(fixme would still apply and worth migrating to a unique_ptr captured by move at that point)

283–289

might be easier written as:

return std::tie(LHSP.getSectionOrdinal(), LHS->getOrdinal()) < std::tie(RHSP.getSectionOrdinal(), RHS->getOrdinal());
294–298

Indentation seems off here

382–383

Seem to be a few negatives in here, maybe:

assert(std::all_of(... isResolved()); ...

would be a more direct expression/match the phrasing of the assertion text below?

Oh, and there's probably llvm::all_of that takes a range directly rather than needing to decompose into begin/end

389

I tend to advocate for [&] whenever a lambda is used within the scope it's defined (ie: doesn't leak out via a std::function or similar) - it's just another scope & seems fine for it to have access to all of the names in the outer scope without having to explicitly opt in, etc.

409

reinterpret_casts (especially of references, I think - I'd worry about potentially turning a non-reference/pointer/thing into a reference with such a cast) make me a bit twitchy - any chance of wrapping the reinterpret_casting up in something more type safe at both ends?

lib/ExecutionEngine/JITLink/JITLinkMachO_x86_64.cpp
46–82 ↗(On Diff #188488)

Worth a small .def file or local macro to reduce the duplication?

#define MY_CASE(n) case n: return #n
MY_CASE(NegDelta32);
MY_CASE(NegDelta64);

etc...

232–238 ↗(On Diff #188488)

elses-after-returns can be removed, I think

lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp
122–128

else-after-continues can be removed

unittests/ExecutionEngine/JITLink/JITLinkTestCommon.cpp
45–46

Using '&' capture for a lambda that escapes the current scope makes me a bit twitchy - would it be worth enumerating the things being captured here? I guess they're all members, so it's capturing 'this' by value, but still - I'd be more comfortable with that spelled out.

unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h
98–100

else-after-return

Ah, I see, scoping because of "DA" - I'd probably move DA out of the condition and early return for the error case instead:

auto DA = G.find...;
if (!DA)
  return DA.takeError();
return support::endian::read<>(...);

Reduces indentation of the main path

lhames added a comment.Mar 4 2019, 8:21 AM

My main concern with this design is how you plan to integrate this with the existing infrastructure. Are you planning on laying this under RuntimeDyLD? Or somehow factoring out common implementation to be used by both? I'm generally bothered by the seeming duplication of such a fragile piece of infrastructure.

JITLink should be more-or-less a drop-in replacement for RuntimeDyld, with a few minor API changes. My intention is to substitute it for MachO handling, first in ORC (where switching out the JIT linker is easy) and then potentially in MCJIT with something like:

if (isa<MachOObjectFile>(Obj))
  jitLink(Obj)
else
  Dyld.loadObject(Obj);

The duplication should only be until we are confident in it. If/when JITLink has proved itself a viable replacement we should deprecate and then remove RuntimeDyldMachO. Ideally we will do the same for RuntimeDyldCOFF and RuntimeDyldELF too.

lhames added a comment.Mar 4 2019, 8:42 AM

Since you're rewrite this, is there any potential for sharing code with lld? Relocating instructions should essentially be the same between these two.

I haven't read this patch, but as a general comment, I could say that a static linker is fairly different from a JIT linker...

Actually they’ve got much more in common than you would think. The commonality comes from the input format: relocatable object files. The JIT linker does indeed need to create GOT entries, PLTs, etc. It is the output formats that are really different: A static linker needs to be able to output its data structures as executables, shared objects, or relocatable object files, which requires some non-trivial formatting. A JIT linker just needs to arrange the atom contents into memory segments with the right permissions. The other big differences are that the JIT linker only links one relocatable object file at a time (at least for now), and that it requires some asynchronous callbacks to make it efficient to use within the concurrent JIT APIs.

I did think about using the atom-based LLD for this, but it’s a big dependence to bring in to LLVM, and lacked the asynchronous API support that the JIT needed. In the end I opted for a cut down initial design inspired by the atom-based LLD.

I was actually thinking about handling of target-specific relocations, and applying them to instructions. We used to have a large chunk of auto-generated code that did that. The implementation in lld is much shorter, so it's probably not a big deal if it needs to be repeated.

Yeah, applying a target-specific relocation is essentially just one line of code per a relocation type in lld, and given that the types of relocations that a JIT linker has to handle is more limited than a static linker, the duplication is pretty limited.

As noted, we actually do need to handle the full scope of relocations supported by the static linker (on the input side). There is not a lot of duplication to eliminate, but I’m thinking about switching to a named function for each relocation expression to support sharing between JITLink and its test infrastructure.

lhames marked 13 inline comments as done.Mar 6 2019, 4:01 PM

Thanks Dave! I've got a patch that addresses your feedback that I will post from the bus in a minute.

include/llvm/ExecutionEngine/JITLink/JITLink.h
224–225

Yeah — I like that idea.

253–254

I had not thought of that. I can’t see any reason that would not work. I will try it out.

455

Good call.

lib/ExecutionEngine/JITLink/JITLink.cpp
58–60

It had never occurred to me to use =default in an out-of-line definition before. :P

Good call.

lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
231–235

Yep. The problem is that once you convert to shared_ptr you cannot convert back. I think I opted to keep this as a raw pointer for ease of conversion, on the assumption that we're switching to c++14 *reasonably* soon.

283–289

That's a neat trick, but once formatted for 80 columns I am not sure it's any more readable.

294–298

Hrm. Clang format is doing awful things to this. Will hand-format.

382–383

There is! Thanks. :)

409

Huh. This was a think-o: it should have been a static_cast. Fixed in the latest iteration of the dead-stripping code.

lib/ExecutionEngine/JITLink/JITLinkMachO_x86_64.cpp
232–238 ↗(On Diff #188488)

Indeed.

lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp
122–128

Updated.

unittests/ExecutionEngine/JITLink/JITLinkTestCommon.cpp
45–46

Yep -- 'this' would be better here. Fixed.

unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h
98–100

Interesting. I tend to prefer the if/else framing because it feels like the "success/failure" state on each path is more obvious. I only switch to early outs for Expected values if I think the indentation will make things really unreadable.

lhames updated this revision to Diff 189615.Mar 6 2019, 4:34 PM
  • Change the way dead stripping is performed.
  • Flesh out initial JITLink MachO/x86-64 unit test.
  • clang-format
  • Address dblaikie's review feedback, also make Atom/DefinedAtom/Section
This comment was removed by sgraenitz.
lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
294–298
LLVM_DEBUG({
  ...
});

usually works well

As a side note: it would be very helpful if you could add links to the specs you used to implement relocations.

include/llvm/ExecutionEngine/JITLink/JITLink.h
243

There seems to be a discrepancy: within the Edge, the Offset and Addend are defined as uint32_t and int64_t respectively, but here they are initialized with JITTargetAddress which is uint64_t.

415

Just curious, is it necessary to have both getAtomByName/findAtomByName publicly available (same for ..AtomByAddress)?
As an LLVM APIs user, I always confused when I see such duality.
Also, I think the getAtomByName/Address are dangerous: if you have assertions disabled (as it is in release builds), then a user will get undefined behavior if the element is not in the container.

lib/ExecutionEngine/JITLink/JITLinkGeneric.h
36

Seeing a unique_ptr here, does it mean that a user of the API would have to give up the ownership of the object file?
If that's the case, then, in my humble opinion, this API should be reconsidered: either take ownership from the very beginning or do not take it at all.

55

How does dead-strip work? Is it possible to control what is stripped?
Here is the use-case I'm concerned about:

void *address = 0;
void driver() {
  void (*fun)() = address;
  fun();
}

void foo() {}
void bar() {}

There is a function that loads the address of another function from a global variable and calls it. Initially, the global address is zero, but it is changed by the JIT client, like this (pseudo-code):

address = jit.getAddress("foo")
jit.callFunction("driver")
address = jit.getAddress("bar")
jit.callFunction("driver")

Techically, the foo and bar are dead, but in fact they are used.

lib/ExecutionEngine/JITLink/JITLink_MachO_x86_64.cpp
563

Does it make sense to at least add some logs here, so that an end user will see what's going wrong with their code?

dblaikie added inline comments.Sun, Mar 31, 9:00 AM
lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
283–289

FWIW, I find the tie version easier to read because I don't have to think about the interesting true/false/less than/greater than cases in the custom version you have here. I can't eyeball exactly what this ordering is.

unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h
98–100

*nod*

For myself, I prefer the "conditionalize the failure/error handling" as a consistent strategy (since it's more necessary in longer functions (where indenting every successful branch starts to get a bit arrow-y ( https://blog.codinghorror.com/flattening-arrow-code/ )) , but I like to adopt a format that's consistent across short and longer code (so it doesn't need to be restructured if there ends up being a second error path in the code)

Yeah, I wish there was slightly tidier syntax for it - for sure (the convenience of variable declared in if scopes is kinda nice - makes it very clear that the if/else block only occurs when the entity is true/false - rather than having to parse some (even just slightly, with a single !) non-trivial condition to check)

lhames marked 6 inline comments as done.Mon, Apr 8, 5:01 PM

New patch coming soon: more complete relocation support, weak symbol support, testing infrastructure, and a new llvm-jitlink tool (the jitlink counterpart to llvm-rtdyld).

include/llvm/ExecutionEngine/JITLink/JITLink.h
243

Good point. This will be fixed in the upcoming patch.

415

Their purposes are slightly different: Sometimes you know from context that a certain address or symbol name is *definitely* present (usually because you would have error’d out earlier in the code if it wasn’t). In this case you can use the “get*” versions of the APIs and bypass the redundant error check. By contract you are only allowed to call these atoms if you are certain they will succeed.

Otherwise you should use the find* APIs, which do not assume that the query will succeed.

Of note: JITLink implementations should assume potentially malicious input: just because a well formed binary *should* have a particular symbol in it, does not mean that you are allow to assume that it will.

lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp
294–298

That's a handy tip. Thanks Stefan!

lib/ExecutionEngine/JITLink/JITLinkGeneric.h
36

I am not quite sure what you mean here? Passing ownership into the constructor seems like taking ownership from the get-go?

In any case this has actually changed in the most recent version of the patch, which I will upload shortly: The new version takes ownership of a Context object instead, and its up to the client whether or not their context class owns the underlying buffer.

55

The details of dead-stripping have changed a little bit in the yet-to-be-posted patch, but the basic idea is that the target provides a sensible default “live-marker” pass which sets the live symbol roots.

Clients are definitely free to add passes to mark additional definitions live (or remove the live markers), and there is a convenience pass for tagging all atoms live.

The default MachO live-marker pass marks all external symbols live, so in your example ‘foo’ and ‘bar’ would be kept by default.

lib/ExecutionEngine/JITLink/JITLink_MachO_x86_64.cpp
563

I should have used a different comment for these: they are “precommit fixmes”. I wanted to get the high level API design up for review while I worked on the details. The intention is that all relocations should be supported by the time this review is complete. :)

lhames updated this revision to Diff 194414.Tue, Apr 9, 3:57 PM
  • Lots of changes. Headlines:
lhames added a comment.Tue, Apr 9, 3:57 PM
  • Lots of changes. Headlines:

Oops. The commit message got cut off in this update. Here it is:

Lots of changes. Headlines:

(1) Changes the way dead stripping is performed: Atoms now have a 'live' flag,
which should be set by a pass (that may be supplied by the target or the
client). The dead-strip algorithm propagates liveness from the original set of
live atoms along edges to all reachable atoms, then deletes any atoms not marked
live.

(2) Weak symbol support: JITLink now supports discarding duplicate weak
definitions (despite JITLink operating on a single file at a time) by setting a
"should-discard" flag on definitions to be dropped. If the should-discard flag
is set on an atom it will be discarded during dead-stripping. (Liveness flags
are not propagated through atoms marked should-discard, to prevent them from
spuriously keeping other atoms live).

(3) New 'llvm-jitlink' tool for testing: This is the JITLink equivalent of
llvm-rtdyld: it allows us to link object files from the command line and execute
their contents or perform tests.

(4) New JITLink based ObjectLinkingLayer in ORC: This is the JITLink equivalent
RTDyldObjectLinkingLayer, and is used in the implementation of llvm-jitlink.

(5) Most MachO/x86-64 relocations now supported. More to come before commit.
lhames updated this revision to Diff 195605.Wed, Apr 17, 11:27 AM

Another big update.

  • Improved eh-frame support. C++ exception handling now works in JIT'd code (for MachO/x86-64).
  • The llvm-jitlink tool now supports basic RuntimeDyld checker tests (support for remapping sections and injecting symbols still to come)
  • Add a 'global' flag to atoms so that we don't try to resolve local symbols in Orc (avoiding 'resolving outside responsibility set' assertions in ORC Core).
  • Supports all MachO/x86-64 relocations except for TLV.

Regression test cases and full RuntimeDyldChecker support still to come.

lhames updated this revision to Diff 195669.Wed, Apr 17, 8:42 PM
  • Fix some section layout and test infrastructure bugs, start work on an initial testcase.