Speeding up ELF relocations for store-based systems

Windows and macOS both use a form of two level name-spacing, which does the same sort of direct binding to a target library for each symbol. Retrofitting that into a binary format is pretty simple, but retrofitting it into an ecosystem that depends on the existing flat namespace look up semantics is not. I think it is pretty clever that the author noticed the static nature of the nix store allows them to statically evaluate the symbol resolutions and get the launch time benefits of two level namespaces.<p>I do wonder if it might make more sense to rewrite the binaries to use Direct Binding[1]. That is an existing encoding of library targets for symbols in ELF that has been used by Solaris for a number of years.<p>1: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Direct_binding" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Direct_binding</a>

This is interesting, but I&#x27;m not sure it actually makes much difference for realistic workloads. ffmpeg probably has the most link-time dynamic linking of any Linux package, and ffmpeg -loglevel quiet takes only ~40 ms on Alpine and ~60 ms on Debian. Other programs using ffmpeg tend to either statically link it (Chromium) or link it at run-time (Firefox, most video editors), neither of which would be improved by this optimization.<p>Would it be nice to shave 60 ms off of every ffmpeg&#x2F;mpv invocation? In isolation, sure, but considering the maintenance burden and potential inconsistencies I don&#x27;t think it&#x27;s worth it. Nix is supposed to ensure that the dependencies are always the same, but currently if something breaks somehow, the wrong version will be loaded or an error will be emitted, whereas with this optimization, it will crash or silently invoke the wrong functions which seems extremely difficult to debug.

Another option is the Solaris&#x2F;Illumos &quot;direct binding&quot; scheme where each object stores for each external symbol the SONAME of the object meant to provide it. It&#x27;s a lot like pre-linking, but a) less intrusive, b) less fast (because it&#x27;s less intrusive).<p>EDIT: Ay, <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=40268546">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=40268546</a> mentions this.

<i>&gt; This optimization is only possible for store-based systems since the set of shared libraries is fixed and immutable. In a traditional Linux distribution, each shared library could be updated at any time, which would invalidate the cached symbol resolutions and their offsets.</i><p>Yes and no.<p>The optimisation of having a cache could be implemented on more traditional linux systems. You would just need to check the modification time of all the shared libraries hasn&#x27;t changed before using the cache. Alternatively, the job could be given to the package manager, make it invalidate and regenerate the cache for any binaries that that use and shared libraries that have been updated.<p>What a store-based system does is make it so much simpler to implement such optimisations, because you simply don&#x27;t need to worry about various invalidation based edge cases.

I don&#x27;t like the term &quot;store-based&quot; for what Nix does. Nix uses a partial transitive universe hash to compute deploy-time locations for built artifacts at build configuration time so that those can be hard-coded into built artifacts -- &quot;store-based&quot; <i>hardly</i> captures this. I don&#x27;t know what to call this, but &quot;store-based&quot; is insufficiently suggestive.

Hahaha funny seeing you @fzakaria here, knew I recognized that name! We worked on a hypemachine scraper a long time ago 12 or 13 years ago, glad to see you are still around writing great software and interesting articles!

This is really neat! I’ll have to take a closer look and see if some ideas could be reused in zephyr’s new elf loading facilities

This article confuses static linking and deterministic builds. I.e Nix, a &quot;store-based system&quot; (author&#x27;s term), still very much dynamically links. Static linking means copying actual program code from libraries into the executable itself, such that external .so files don&#x27;t need to be loaded.