MaskRay

A lot of vendors use non-lazy binding for security reasons, and some platforms don't support anything other than RTLD_NOW (e.g., Android).

Anyway, while what you said is theoretically half-true, a fairly large number of libraries are not designed/encapsulated well. This means almost all of their symbols are exported dynamically, so, the idea that there are only "few public exported symbols" is unfortunately false.

However, something almost no one ever mentions is that ELF was actually designed to allow dynamic libraries to be fairly performant. It isn't something I would recommend, as it breaks many assumptions on Unices, (while you don't get the benefits of LTO) you can achieve code generation almost equivalent to static linking by using something like "-fno-semantic-interposition -Wl,-Bsymbolic,-z,now". MaskRay has a good explanation on it: https://maskray.me/blog/2021-05-16-elf-interposition-and-bsymbolic

Let's say you need to use a function like:

int add(int a, int b){
// Long logic and then this
return a+b;
}

Let's say this is your main.c.

#include "add.h"

int main(void) {
return add(5,6);
}

The preprocessor just copies the contents of add.h into your main.c whenever you're trying to compile main.c. (let's ignore the concept of precompiled headers for now).

What you can instead do is just put the add function declaration in add.h that just tells the compiler that add function takes two integers and returns an integer.

int add(int a, int b);

You can then put the add function definition in add.c , compile that to an add.o and link it to your main.o at link time to get your final binary - without having to recompile add.o every time you change your main.c.

Precompiled headers: https://maskray.me/blog/2023-07-16-precompiled-headers

I’m also a bit weirded out by the lack of mentions of dominators (in TFA or in the article[1] it links to). Once you have the dominator tree, though, you’re still going to need to answer LCA queries on it (in this problem and in an SSA-based compiler both), so there seems to be no way around this part.

The algorithm in the article does O(1) queries with O(V+E) preprocessing (assuming linear-preprocessing LCA, which, yeah). What’s the best algorithm for dominator trees? People usually talk about Lengauer–Tarjan[2], which is linear in practice (linear except for UNION-FIND), and not the linear one by Georgiadis[3,4]. Unfortunately, I’m not a compiler person.

[1] https://doi.org/10.1016/j.ipl.2010.02.014

[2] https://maskray.me/blog/2020-12-11-dominator-tree

[3] https://www.cs.princeton.edu/research/techreps/43

[4] https://dl.acm.org/doi/abs/10.1137/070693217

Thanks! I was able to find some additional info on no-MMU Linux [1], [2], [3]. It seems position-independent executables are the norm on regular (MMU) Linux now anyway (and probably have been for a long time). I took a look under the covers of uClibc and it seems like malloc just delegates most of its work to mmap, at least for the malloc-simple implementation [4]. That implies to me that different processes' heaps can be interleaved (without overlapping), but the kernel manages the allocations.

[1]: https://maskray.me/blog/2024-02-20-mmu-less-systems-and-fdpic

[2]: https://popovicu.com/posts/789-kb-linux-without-mmu-riscv/

[3]: https://www.kernel.org/doc/Documentation/nommu-mmap.txt

[4]: https://github.com/kraj/uClibc/blob/ca1c74d67dd115d059a875150e10b8560a9c35a8/libc/stdlib/malloc-simple/alloc.c#L23

Always quality content in that blog. We used MaskRay's article[1] on stack unwinding to improve our debuginfo (DWARF) support[2] in the past. If someone wants to have a more hands-on approach to executable file formats, e.g., XCOFF or GOFF, they can check Rizin's ideas for new formats[3] to support.

[1] https://maskray.me/blog/2020-11-08-stack-unwinding

[2] https://rizin.re/posts/gsoc-2023-dwarf/

[3] https://github.com/rizinorg/ideas/issues?q=is%3Aissue+is%3Aopen+label%3A%22New+File+Format%22