Speeding up ELF relocations for store-based systems
fzakaria.com
fzakaria.com
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.
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).
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.
EDIT: Ay, https://news.ycombinator.com/item?id=40268546 mentions this.
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.
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.
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.
> 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.