This article confuses static linking and deterministic builds. I.e Nix, a "store-based system" (author'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't need to be loaded.
> Store-based systems, however, are static in nature, with all dependencies being resolved at build time.
I think the author is saying that the shared libraries (.so) are available at build time on store-based systems and never change. Thus, the dynamic linker can speed up symbol resolution by doing the symbol resolution at build time and sticking the result in output binary. This is distinct from static linking which sticks the entire library (.a) into the output binary.
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.
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.
Not only is there less crawling around looking for symbols, you're no longer in trouble when two libraries export the same symbol.
Especially given libraries are found by name, and symbols by name, where "type information" or "is that actually the library I wanted" are afterthoughts.
> you're no longer in trouble when two libraries export the same symbol.
Whether you use direct binding or symbol versioning, either way you don't have a problem with multiple libraries exporting the same symbol.
By the way, this is the fundamental problem with static linking for C: it's still stuck with 1970s semantics and you can't get the same symbol conflict resolution semantics as with ELF because the static linker-editors do not record dependencies in static link archives.
The key insight is that when you link-edit your libraries and programs you should provide only the direct dependencies, and the linker-editor should then record in its output which one of those provided which symbol. Compare to static linking where only the final edit gets the dependency information and that dependency tree has to get flattened (because it has to fit on a command-line, which is linear in nature).
You can get the same semantics as for direct binding using symbol versioning, but direct binding is faster.
Also, symbol versioning is only really better than direct binding if you end up having multiple versions of the same symbol provided by the same object, but that's relatively hard to use, so it's really only ever used for things like the C library itself. Mind you, that is a very valuable feature when you need it. In Solaris itself when we needed to deal with the various different behaviors of snprintf() there just wasn't a good way to do it, and only symbol versioning with support for multiple versions of a symbol would have helped.
Not really... symbol versioning is a form of namespacing, but it is somewhat orthogonal to this.
Symbol versioning allows you to have multiple symbols with the same name namespaced by version, but you still have no control over what library in the search path they will be found in. So it does not improve the speed of the runtime searching (since they could be in any library an the search path and you still need to search for them in order), and it does not provide the the same binary compatibility support and dylib hijacking protection (since again, any dylibs earlier in the search path could declare a symbol with he same name.
One could use symbol versioning to construct a system where you had the same binary protection guarantees, but it would involve every library declaring a unique version string, and guaranteeing there are no collisions. The obvious way to do that would be to use the file path as the symbol version, at which point you have reinvented mach-o install names, except:
1. You still do not get the runtime speed ups unless you change the dynamic linker behavior to use the version string as the search path, which would require ecosystem wide changes.
2. You can't actually use symbol versioning to do versioned symbols any more, since you overloaded the use of version strings (mach-o binaries end up accomplishing symbol versioning through header tricks with `asmname`, so it is not completely intractable to do even without explicit support).
> Symbol versioning allows you to have multiple symbols with the same name namespaced by version, but you still have no control over what library in the search path they will be found in.
Yes, but since the convention is to use the SONAME and SOVERSION in the symbol version therefore in practice the symbol version does -when adhering to this convention- help in binding symbols to objects.
Still, because this is an indirect scheme it does not help speed up relocation processing.
As you say, direct binding is better for safety and speed.
Absolutely, I just think "when adhering to this convention" is a high risk. Admittedly I mostly work on macOS so I don't have a nearly as deep of an experience with ELF, but in my experience even when a system looks to be well maintained that you often find surprising numbers of projects being "clever" and breaking conventions as soon as you try to do something that depends on everyone actually globally following the convention.
> You still do not get the runtime speed ups unless you change the dynamic linker behavior to use the version string as the search path, which would require ecosystem wide changes.
Each ELF library declares the symbol versions it provides. The dynamic linker could track which library declares which versions, and cross reference that when it looks symbols up. I though it did, but from empirical testing, it doesn't. But if it did, it would get similar speed improvements, assuming all libraries provide at least one version each (and of course, assuming no overlaps).
Another option is the Solaris/Illumos "direct binding" scheme where each object stores for each external symbol the SONAME of the object meant to provide it. It's a lot like pre-linking, but a) less intrusive, b) less fast (because it's less intrusive).
I don't like the term "store-based" 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 -- "store-based" hardly captures this. I don't know what to call this, but "store-based" is insufficiently suggestive.
This is interesting, but I'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.
Would it be nice to shave 60 ms off of every ffmpeg/mpv invocation? In isolation, sure, but considering the maintenance burden and potential inconsistencies I don't think it'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.
40ms might matter if you consider the number of times a process might restart, the number of instances you run and on how many hosts. That could be considerable wasted cycles in aggregate.
(i.e. cloud provider)
Also it's not only a function of how many shared libraries but how many symbols they each individually have as well -- also their symbol length as well.
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!
The knowledge of that scraper went into a Chrome extension that sees some good downloads to this day
(I guess people this use hypemachine... I have kids now so my music listening time is on a pause)
> 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.
Yes and no.
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'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.
What a store-based system does is make it so much simpler to implement such optimisations, because you simply don't need to worry about various invalidation based edge cases.
26 comments
[ 3.5 ms ] story [ 73.9 ms ] thread> Store-based systems, however, are static in nature, with all dependencies being resolved at build time.
I think the author is saying that the shared libraries (.so) are available at build time on store-based systems and never change. Thus, the dynamic linker can speed up symbol resolution by doing the symbol resolution at build time and sticking the result in output binary. This is distinct from static linking which sticks the entire library (.a) into the output binary.
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.
1: https://en.wikipedia.org/wiki/Direct_binding
Not only is there less crawling around looking for symbols, you're no longer in trouble when two libraries export the same symbol.
Especially given libraries are found by name, and symbols by name, where "type information" or "is that actually the library I wanted" are afterthoughts.
Whether you use direct binding or symbol versioning, either way you don't have a problem with multiple libraries exporting the same symbol.
By the way, this is the fundamental problem with static linking for C: it's still stuck with 1970s semantics and you can't get the same symbol conflict resolution semantics as with ELF because the static linker-editors do not record dependencies in static link archives.
The key insight is that when you link-edit your libraries and programs you should provide only the direct dependencies, and the linker-editor should then record in its output which one of those provided which symbol. Compare to static linking where only the final edit gets the dependency information and that dependency tree has to get flattened (because it has to fit on a command-line, which is linear in nature).
Also, symbol versioning is only really better than direct binding if you end up having multiple versions of the same symbol provided by the same object, but that's relatively hard to use, so it's really only ever used for things like the C library itself. Mind you, that is a very valuable feature when you need it. In Solaris itself when we needed to deal with the various different behaviors of snprintf() there just wasn't a good way to do it, and only symbol versioning with support for multiple versions of a symbol would have helped.
Symbol versioning allows you to have multiple symbols with the same name namespaced by version, but you still have no control over what library in the search path they will be found in. So it does not improve the speed of the runtime searching (since they could be in any library an the search path and you still need to search for them in order), and it does not provide the the same binary compatibility support and dylib hijacking protection (since again, any dylibs earlier in the search path could declare a symbol with he same name.
One could use symbol versioning to construct a system where you had the same binary protection guarantees, but it would involve every library declaring a unique version string, and guaranteeing there are no collisions. The obvious way to do that would be to use the file path as the symbol version, at which point you have reinvented mach-o install names, except:
1. You still do not get the runtime speed ups unless you change the dynamic linker behavior to use the version string as the search path, which would require ecosystem wide changes.
2. You can't actually use symbol versioning to do versioned symbols any more, since you overloaded the use of version strings (mach-o binaries end up accomplishing symbol versioning through header tricks with `asmname`, so it is not completely intractable to do even without explicit support).
Yes, but since the convention is to use the SONAME and SOVERSION in the symbol version therefore in practice the symbol version does -when adhering to this convention- help in binding symbols to objects.
Still, because this is an indirect scheme it does not help speed up relocation processing.
As you say, direct binding is better for safety and speed.
Each ELF library declares the symbol versions it provides. The dynamic linker could track which library declares which versions, and cross reference that when it looks symbols up. I though it did, but from empirical testing, it doesn't. But if it did, it would get similar speed improvements, assuming all libraries provide at least one version each (and of course, assuming no overlaps).
EDIT: Ay, https://news.ycombinator.com/item?id=40268546 mentions this.
Would it be nice to shave 60 ms off of every ffmpeg/mpv invocation? In isolation, sure, but considering the maintenance burden and potential inconsistencies I don't think it'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.
40ms might matter if you consider the number of times a process might restart, the number of instances you run and on how many hosts. That could be considerable wasted cycles in aggregate. (i.e. cloud provider)
Also it's not only a function of how many shared libraries but how many symbols they each individually have as well -- also their symbol length as well.
I'd love to experiment with this + additional ideas that further OS when more control is known such as in NixOS.
I have another idea that's quite crazy but I have done some rough benchmarking to prove its efficacy.
The knowledge of that scraper went into a Chrome extension that sees some good downloads to this day (I guess people this use hypemachine... I have kids now so my music listening time is on a pause)
Hope you are well as well.
Yes and no.
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'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.
What a store-based system does is make it so much simpler to implement such optimisations, because you simply don't need to worry about various invalidation based edge cases.
unfortunately on a traditional system nothing is stopping anything (user?) from mucking with the system outside the knowledge of the package manager.