Modern dynamic linking infrastructure for PLT

Given that Unix won, I think it's interesting that dynamic languages make very little use of the dynamic linking and loading infrastructure provided by modern free Unixes such as Linux and the BSDs.

Most dynamic PLs opt to implement "dynamism" (i.e. redefining stuff, loading code at runtime) with application-specific data structures (e.g. Lisp: red-black trees for uniquifying symbols, function pointers and indirect function calls), and they do so solely at runtime (mostly using interpreters and JITs, although Scheme, one of the most advanced dynamic languages, is increasingly illuminating the possibilities of static, independent compilation of dynamic programs).

(Metaprogramming at runtime is perilous, as it is easy to mix up phase distinctions, something we can expect newer dynamic programming languages to discover in a decade (of course we don't know which decade.))

Link-time is mostly ignored. And yet, under Linux with its heavy use of shared objects, one cannot even start a single program without invoking the dynamic linker.

But some people, even some computer programmers, don't know how linkers work and what they do. Basically, a modern linking file format, such as ELF, is a declarative way to construct the memory image of a running process, with lots of features for dynamic customization of the image construction process (ELF even contains a customization hook called "program interpreter" in every executable!).

Likewise, modern compilers and runtime systems such as GNU C contain sophisticated features aimed squarely at dynamic languages: weak symbols for runtime redefinability (used by libc's malloc and in the Linux kernel, for example), computed gotos, nested functions, and increasingly, GC. And there is evidence that dynamic compilation and linking of C snippets is accepted and used in modern systems software.

I have collected some links to these topics, and would be interested to hear of languages and systems that you know that exploit them.

(Updates: added 3 ELF links; added Drepper; added Taylor)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Some dynamic languages do undertand dynamic linking

Nice collection of links, and well worth looking at, but there is support for dynamic linking in dynamic languages ... maybe not as widely used as it should be.

Ruby has long had support for dynamic loading of C (and other languages) in scripts. See for example thew articles:

Perl also has inlining and dynamic linking (and has for a long time). I'd guess that other languages do to, but I'm not sure which ones or how they support it.

Cross-platform compatibility

One pragmatic concern is that dynamic linkers are notoriously platform-specific. The three major desktop platforms all use different binary formats (PE, ELF, Mach-O), and differ significantly enough in implementations that it's difficult to write an abstraction layer. Even amongst platforms that share the same executable format, the linkers for each OS are very different.

So, unless you're happy to constrain your language to just a single platform, it'd be pretty unwise to build on top of your OS's linker for all your dynamic needs.

Portability...

... requires a layer of indirection, but can still be achieved building atop the OS linker layer.

Of course, portability is only one concern. You need a second layer-of-indirection if you wish to usefully support migration, distribution, persistence, or local singleton 'objects' that are defined or access features via the link layer.

CLI?

Even though I love to bash Microsoft on a regular basis--an activity which seems to have become passe of late--the .Net Common Language Infrastructure, which does much of its work at application deployment/start time, seems to have been utterly ignored by this post.

The Unix linkers (and Windows, of course, has binary linkers similar to those found on Unix systems), are still primarly meant to piece together binaries, and do that job well. However, ld.so and friends suffer from numerous issues which limits their applicability to higher-level languages, especially when dealing with things that are not object files.

Low-level linkers are generally type-unaware, other than trivial type distinctions like "code" and "data"--type information can be encoded in a way the linker understands via name mangling, but that's best understood as a magnificent kludge. :) And it took years of complaints from C++ users, who need things like weak symbols and such to reasonably support features like templates, to even get the Unix linker to where it was--for much of the 1990s, it seems, certain Unix system providers dismissed the concerns of C++ users as irrelevant.

In short--there's a reason many high-level languages (or language runtimes/environments) don't use the system loader in the manner you suggest.

Unix-only

For the moment I am ignoring portability, and focusing on a Linux proof-of-concept only. AFAIU, the techniques should be portable to other linking platforms.

Am I missing something?

Maybe I do not understand the claim correctly, but there is a lot of dynamic linking and loading going on in modern programming languages. In addition to the inline options mentioned by pate, here is what I found at a casual glance:

... and that's just scratching the surface. So again - maybe I'm unclear on what's being said here. I'll have to reread the links given.

Original poster is noting

that many high-level languages perform module-linking by means other than invoking the system loader. In many cases, the modules being linked are source files or bytecode, neither of which typical binary loaders deal with effectively.

Lua Alien

From its web page, Alien is a Foreign Function Interface (FFI) for Lua. An FFI lets you call functions in dynamic libraries (.so, .dylib, .dll, etc.) from Lua code without having to write, compile and link a C binding from the library to Lua. In other words, it lets you write extensions that call out to native code using just Lua.

It uses the great libffi library by Anthony Green (and others) to do the heavy lifting of calling to and from C. The name is stolen from Common Lisp FFIs.

wither c++

i wish ffis supported c++

wither indeed

I wish C++ supported FFIs. :)

Live Service Layers

Languages could easily take far more advantage of dynamic linking. But focus on ELF binaries and dynamic-loading down at the low-level code is, I believe, a harmful distraction.

More interesting is the issue of how to integrate dynamic linking with languages in an accessible, portable, flexible, and implementable manner. This requires that the language be developed with some standard abstractions that can leverage dynamically linked services, and that the dynamically linked services and virtual-machine be developed in combination to provide these abstractions. The simple 'foreign function interface' concept really isn't enough.

I have my own ideas on that subject, but they do heavily involve dynamic linking infrastructure available to the VM.

I believe that having a "live services" layer - that is, services properly abstracted as either preceding the application going live even without taking any action, as well as persisting across application upgrades - is important and useful for languages (be they static or dynamic), and that some of the better ways to achieve this are through 'service' registries that allow one to perform service matchmaking (i.e. "I require http access" matches "I provide http access").

Services can be provided from many sources - including plugins (e.g. ELF binaries), but also including CPAN databases and such. These services can be heuristically matched and filtered based on policies and requirements, and may dynamically support automatic "fallback" should a service become unavailable (i.e. because its dependencies fail). Assertions and unit-tests can be part of a service to ensure it seems to be live and sane... those could be tested at startup and periodically, especially if their side-effects can be confined.

Live services can also extend to helping hook into live dataflows and domain-addressed multicast networks, as source or sink. Further, one is may also be given capability to automatically publish one's own service for further matchmaking.

I posit that a carefully developed and effectively integrated 'live service layer', implemented with support from dynamic linking infrastructure, could eliminate much boilerplate code, eliminate most need for singletons and abstract constructor or dependency-injection frameworks (a singleton becomes an 'external service', and external dependencies are managed globally), and provide greater robustness in the face of dynamic upgrades of the environment.

Common support for persistence, such that "connections" and objects developed over the life of an application can also be resurrected (unless the developer volunteers for volatility), would probably cover even more boiler-plate and robustness. With care, it would allow switching dynamically to a new plugin without resetting the whole application. This would need to integrate with plugin-provided services and other 'live-services' in a consistent manner, such that the language knows how to resurrect services without duplicating them by accident.

My own approach has been providing these live-services in three layers recognized by the runtime, capturing different persistence, security, and distribution concerns:

  • application layer provides 'volatile' services. Volatility is contagious: if A is volatile, and the demand for service B depends on A's survival, then B is volatile. For robust persistence, higher layers can only be volatile via contagion.
  • local layer provides 'persistent' services common to the machine or local-area network. These will recover with their previous state. Applications are also free to provide local services (i.e. to automatically re-establish connections or display). Example services include local filesystem, joystick access, local print service
  • global layer provides persistent services that are pervasive among machines and have common semantics. This is a security layer for distributed or migratory agents. Services in this layer are available to remote code. Examples would include clock, timers (e.g. once-per-second event), random-number generators, an RSS feed.

Calls from higher to lower layers are possible, but would be capability based: the communication from high to low layer occurs over an opaque, unforgeable connection or name, and so must be part of the state or constructor for the high-layer service.

Services such as scripting engines might exist in more than one layer. For example, javascript could be provided at both local and global layers, providing access to more application services in the lower layer.

Good overview of important issues

Thanks. At the moment I am only trying to solve the part that you call application. And I don't think that focusing on ELF is a distraction. Contrarily, to me the linking layer appears to be the right place to implement the application part, without reinventing these things in the language runtime. Once that's taken of, I agree with you, that the higher layers (local and global), should be tackled.

linkers

@msimoni

It is true that the *nix based systems support linking, but "well" is subjective. Linux is optimized for static linking, and any run-time linking costs are immense.

Awhile back, compiler writer extraordinaire Walter Bright effectively challenged a kernel developer (Andreas Erickson) to fix this problem and I don't believe anything came of it. This challenge was right around the time Walter announced Digital Mars D v1.0.

Costs

Do you have any pointers to descriptions or measurements of these costs?

In the language implementation I am envisioning, standard techniques such as prelinking could be used to mitigate some of the costs, and at runtime, dynamic linking would only occur at the REPL, or when code in the running image is changed. Furthermore, when the highest possible performance is needed, or dynamism isn't, one could compile the executable statically and position-dependent.

No

Read the back-and-forth between Bright and Erickson, though. Walter shares his usual brilliant insights:

Sure, but I suggest that few projects reach this maxima. Case in point:
ld, the gnu linker. It's terribly slow. To see how slow it is, compare
it to optlink (the 15 years old one that comes with D for Windows). So I
don't believe there is anything inherent about linking that should make
ld so slow. There's some huge leverage possible in speeding up ld
(spreading out that saved time among all the gnu developers).

I humbly suggest running a profiler over ld before spending time fixing
the wrong thing . I haven't looked at the ld source, but being
experienced in similar projects I'd hazard a guess that there won't be a
quick fix to ld's speed problems.

Also, you can probably get more information by doing Google searches such as '"slow link" "gcc"' '"linux linker slow"'.

Compile-time, not run-time

Note that this is talking about the cost of running ld at compile-time ("saved time among all the gnu developers"), not the run-time cost of loading the resulting binaries.

Referring to both static and dynamic linking

Part of the conversation refers to the cost of starting up executables that use dynamic linking. I can't really attest to the speed either way; I don't really use linux dynamic linking much as a developer and most applications I use seem fast enough for me. So it might be slow but I don't notice so much.

Although my understanding is in terms of dynamic linking, some of Microsoft's products are the most technologically advanced, including dynamic link-time code generation for flexible calling conventions.

The static linker is not a kernel issue though

Neither is ld.so, really, but runtime linking of course needs kernel support. But Cygnus/FSF, not the Linux developers, are the guys to complain if ld is slow.

Two points perhaps

Two points perhaps addressing some contention.

1. Andreas is actually primarily a Git developer, not a kernel developer (according to my friend who read my comments)

2. I didn't mean to imply this was a kernel issue, really, and immediately edited the post once I saw I used the phrase kernel incorrectly. I changed it to "system". I also recommended searching for linux and slow linker because that is just good use of Google. In much the same way I am sure FSF would prefer I say Gnu/Linux, but the reality is linux by itself is a much better search term.

gold

FYI ld isn't the only linker: see http://en.wikipedia.org/wiki/Gold_(linker)

phase distinctions

(Metaprogramming at runtime is perilous, as it is easy to mix up phase distinctions, something we can expect newer dynamic programming languages to discover in a decade (of course we don't know which decade.))

If I had a first law of metaprogramming, it would be that every decade somebody re-invents Stephen Mellor's Executable UML work. In particular, proper object-oriented analysis and development of Mellor's Specification Object pattern seem applicable here.

In my humble experience, metaprogramming is perilous only when the meta requirements change. For example, if you suddenly need a metalogical system in your query language, then MetaLINQ (and therefore LINQ) is fundamentally the wrong starting point. For an unbeatable discussion of this, read Manuel Clavel's Reflection in Rewriting Logic: Metalogical Foundations and Metaprogramming Applications book.

Clarification

Actually, perilous is a bad choice of words on my part.

What I wanted to say is that earlier, interpreter-influenced implementations of multi-stage languages such as Lisp have a somewhat muddled phase/stage separation (cf. Common Lisp's eval-when) . R6RS and related work in Scheme makes the distinctions much clearer, lending themselves better to compiler-only implementations, which have a natural phase separation.

Chicken Scheme has done some work in this area

Chicken Scheme makes quite heavy use of dynamic linking by default.

Chicken 4 (now with hygienic macros in the core!) compiles units to FOO.import.scm (containing macro stuffs required at compile time to use this module) and FOO.so (or .dll or .dynlib or whatever) with the runtime code in.

Static linking is possible as an option, but the default is dynamic.

If you (load "foo") and there's a foo.so available, that's dynaloaded and its entry point 'run' to execute the load-time semantics of foo; if there's a foo.scm instead, then it's evaluated, with practically identical consequences (but less CPU usage if there's the .so :-)

Will investigate

Sounds good.

A more drastic approach

Unfortunately, UNIX hasn't won everywhere. The D programming language, being natively compiled, needed some way to load dynamic libs on Windows in a way that would not suck. Because static RTTI structures govern e.g. how dynamic casting and exception handling work, there was a problem of them being duplicated across the host program and DLLs. The issue with the latter is that they may contain no weak/unresolved symbols that are then pulled from the host app at runtime. As a result, using DLLs with D is a massive fail. SO is fine, but could get better still.

The DDL project took on a drastic route - implementing a complete dynamic linker that can load object files and static libs. The bad news is that the main branch is abandonware and only supports one object format (a DigitalMars flavor of OMF). The good news is that the concept actually works pretty well. I've employed it along with a custom modification of the linker for a system that can dynamically compile and link a D module. It's also easy to check for any changes in the source file and dynamically reload the module. The GC will handle the actual unloading so there are no issues of crashes due to pointers dangling into the obsoleted modules. I can basically say: 'linker.load("plugin.d")' and then e.g. iterate through all classes inside the plugin that implement a specific class or interface, then instantiate some. AFAICS, you don't get to enjoy this sort of introspection when using libdl.

Something like DDL could probably be done for other languages and systems, but having a GC is a major plus. On *NIX, libBFD could probably be used to extend the support for other object file formats, if you're fine with viral licensing.

Interesting!

The biggest problem I see in using SO/ELF for building a dynamic language seems to be that every shared object has its own global offset table. This means that redefining a function (as outlined in the article Shared library call redirection via ELF PLT infection, linked above) and having the changes ripple through to all shared objects requires some manual bookkeeping (which reminds me of your custom linker).

Yet another link

Re why has it taken so long?

Modern dynamic linking infrastructure [...]

I think it's interesting that dynamic languages make very little use of the dynamic linking and loading infrastructure provided by modern free Unixes such as Linux and the BSDs.

Linux switched to ELF almost 15 years ago. Much of a human generation. So ELF itself doesn't seem very "modern". Except compared to the PDP-11 a.out it replaced. Though if programming language evolution has been a glacial "looking forward to eventually having all good features from the 1980's", linker evolution has been even more crippled.

But playing linker games, and altering shared objects' global offset tables, in the implementation of dynamic languages, does seem to have not caught on. So now if it does, I guess that use will then be "modern".

Lots of languages use libdl. Goo (dead), for example, was built on it (to eval, it emits C, then compiles and dl links it). And Bellard's libtcc (now again undead:-) lets you compile and link C without touching disk.

But why the long delay in playing more interesting games with dynamic linkage?

One factor has been the technical and social characteristics of the gnu compiler chain. Perhaps even a primary cause. At least in the late '90's, my recollection is the roadblock was a triple of () no api for GOT writes, () gcc folks' "we can't imagine why anyone would want to do that", and () gcc/ld "ball of mud build system" entanglement defeating multiple efforts to create an independent gcc-compatible linker (to improve gcc linker tech, which even 15 years ago, was far from cutting edge). So you couldn't do it in gcc/ld, and you couldn't escape them. Several folks tried to break through, but it never worked out. I've no idea what's been happening this century. Focus has shifted to vm's.

Just so you fully appreciate the self-inflicted wound-ness of this all, here you have a little hash table from strings to function pointers, pointers you are jumping through anyway for any function not statically linked, in writable memory, and you couldn't easily change the d*mn pointers. After all, why would anyone want to write to a hash table, or wish to redefine a function?

Maybe things have now improved?

Thanks

Just so you fully appreciate the self-inflicted wound-ness of this all, here you have a little hash table from strings to function pointers, pointers you are jumping through anyway for any function not statically linked, in writable memory, and you couldn't easily change the d*mn pointers. After all, why would anyone want to write to a hash table, or wish to redefine a function?

Ha! :)

Thanks

Thanks for the many insightful comments! You've convinced me that this is the way to go :)