Removing global state from LLD, the LLVM linker

79 pointsposted 4 days ago
by ingve

24 Comments

mingodad

14 hours ago

I did the same for tinycc here https://github.com/mingodad/tinycc and used Netbeans IDE that has great refactoring options for C/C++/Java.

Benchmarking the reentrant result showed it to be around 5% slower.

Now I'm trying to redo it again but this time scripting the refactoring using sparse https://github.com/lucvoo/sparse to parse and using it's error messages with with line/column to guide the refactoring, I already got an initial script that performs some initial transformations and is repeatable, but more work need to be done, mainly enhance/extend the info that sparse provide while parsing the code.

mingodad

14 hours ago

Also for C/C++ binaries with debug info gdb is one of the ingredients used to show where and how much globals exists:

gdb -batch -ex "info variables" -ex quit --args binary-to-examine

beeforpork

a day ago

Why not use thread_local instead of passing a param everywhere? What's the drawback there?

ComputerGuru

21 hours ago

thread_local is usually considered the hack to make unthreaded code littered with static variables useable from multiple thread contexts. It has overhead and reduces the compiler’s ability to optimize the code as compared to when parameters are used.

Also, until very recently, a lot compilers/platforms were unable to handle thread_local variables larger than a pointer size making it difficult to retrofit a lot of old code.

o11c

14 hours ago

It's worth noting that `thread_local` does reduce register pressure. Unfortunately, almost no languages actually natively support the scoping that sane use of this requires.

spijdar

11 hours ago

I’m curious, what’s a language/compiler that does?

o11c

9 hours ago

I'm not aware of one, but it probably exists in some obscure language. I can describe how it should work though:

  * ideally, thread-local variables should not be directly exposed at all
  * variables intended to be dynamically scoped should be explicitly declared using the `dynamic` keyword at top level, using a thread-local variable (possibly of a different type) under the hood (contrary to languages that use dynamic scoping for all variables, this is opt-in, explicit, and more efficient. Note also that many languages do not have real thread-locals, they just pass the thread ID to a map, thus have atrocious performance.)
  * reading a dynamically-scoped variable just accesses the thread-local, after unwrapping the container if needed. If the top level declaration didn't have an initializer, maybe this should throw an error?
  * mutations  to the dynamically-scoped variable require an explicit keyword, and involve saving the old value as if in a block-scoped local variable, and restoring it on unwind. If there's more than one mutation in a single block this can be optimized out.
  * note that "assign a value wholesale" is only the most basic mutation; sometimes a stack is wanted (in which case the saved local value is just the depth) or a set (in which case the saved local value is the key to remove; this needs to be conditional)
  * there should be escape hatches to manually do a save, restore, or write-without-saving. These should be used only to implement nontrivial mutations in the library or to port code using unsafe thread-locals.
It's possible to write a reasonable library implementation of this using macros in C++, GNU C, or maybe standard C23.

(an alternate approach would be to write code as if it were passing arguments to functions, but internally change them to writes to thread-local variables (only if not passed from a parameter of the same name) purely for register-pressure-optimization reasons)

rwmj

a day ago

Certain linker operations can be multi-threaded (not sure if this is specifically true for LLD). Particularly LTO in the GNU toolchain, but also there's been a lot of effort recently to make linking faster by actually having it use all available cores.

mrkeen

a day ago

Thread-local is way too magical for me. I wouldn't want to debug a system that made use of it.

Also, if you pass a param, then it can be shared.

geocar

a day ago

> Thread-local is way too magical for me. I wouldn't want to debug a system that made use of it.

There's a perfectly cromulent register just begging to be used; the circuitry has already been paid for, generating heat whether you like it or not, what magic are you afraid of here?

> Also, if you pass a param, then it can be shared.

Maybe, but if you design for sharing you'll never use your program might be bigger and slower as a result. Sometimes that matters.

cesarb

a day ago

> > Thread-local is way too magical for me.

> There's a perfectly cromulent register just begging to be used; [...] what magic are you afraid of here?

Most of the magic is not when using the thread-local variable, but when allocating it. When you declare a "static __thread char *p", how do you know that for instance this is located at the 123th word of the per-thread area? What if that declaration is on a dynamic library, which was loaded late (dlopen) into the process? What about threads which were started before that dynamic library was loaded, and therefore did not have enough space in their per-thread area for that thread-local variable, when they call into code which references it? What happens if the thread-local variable has an initializer?

The documentation at https://gcc.gnu.org/onlinedocs/gcc/Thread-Local.html links to a 81-page document describing four TLS access models, and that's just for Unix-style ELF; Windows platforms have their own complexities (which IIRC includes a per-process maximum of 64 or 1088 TLS slots, with slots above the first 64 being handled in a slightly different way).

AshamedCaptain

14 hours ago

When you declare a `static char *p;', how do you even know in which address of memory it is going to end up ?? How do you know what will happen if another compilation unit declares another variable of the same name? Another static library? Another dynamic library? What about initialization, what about other constructors that may read memory before main() runs? What about injected threads that are started before that? Madness, I tell you, absolute and utter madness.

maccard

20 hours ago

The initialisation model in c++ is totally and utterly broken and indecipherable. That doesn’t stop me from doing vector<int> foo = {1,2, 3};

intelVISA

20 hours ago

Avoiding thread locals due to dynamic libraries being bad is justified but still doesn't feel like the right tradeoff.

malkia

20 hours ago

I use thread_local a lot, but until recently, on Windows a delay-loaded dll with thread_local would've not worked, and the fix that is in place today is costly, okay that may not be the typical case, but it shows that support for such feature can create a lot of cost elsewhere.

Another pitfall with these is with thread-stealing concurrent schedulers - e.g. your worker thread now waits on something, and the scheduler decides to reuse the current thread for another worker - what is the meaning of thread_local there?

Another one would be coroutines (though haven't used them a lot in C/C++).

high_na_euv

a day ago

Ive always struggled to understand the need to have linker

Like, you could easily write your compiler to do not have to rely on such machinery

Meanwhile they add complexity and decrease quality of error messages (in cpp)

Joker_vD

a day ago

Separate compilation. Of course, if your compiler is fast enough to rebuild the whole universe in 6 seconds and then rest on the seventh — an approach Wirth advocated in one of his papers about an implementation of Pascal system — you won't need a linker. But most compilers are not that fast.

Besides, there is more than one programming language, so that's something we have to deal with somehow.

And to be fair, merging modules in the compiler, as you go by, while not that difficult, is just annoying. If you link them properly together, into big amalgamated text/rodata/data sections, then you need to apply relocations (and have them in the first place). If you just place them next to each other, then you have to organize the inter-module calls via some moral equivalent of GOT/PLT. In any case, all this logic really doesn't have much to do with code generation proper, it's administrativia — and logic for dealing with has already been written for you and packed in the so called "link editor".

uptownfunk

17 hours ago

What are the bottlenecks that make this so slow

wyldfire

18 hours ago

All but the most trivial programs require a linker to resolve references among object files. And while "int main() {}" might seem like a trivial C program, it's not (by that definition, at least).

Your favorite toolchain will often include archives and objects that you might take for granted like crt0.o, init.o, fini.o, libgcc/clang_rt.builtins and more.

The compiler's design is simplified by not having to resolve references among symbols. The assembler can do this for references within a section and linkers can do it among sections. Linkers might have to add trampolines/thunks for relocations that span a distance longer than the opcode could reach. Loaders do this symbol resolution and relocation at runtime.

high_na_euv

3 hours ago

So, if hello world is not trivial

Then you can easily generate e.g web assembly from your own lang input without linker and it will run fine

Aint the same viable for x86?

ChadNauseam

19 hours ago

When I first came to C++ from Rust I was surprised by the regularity of linker errors. Rust must be compiled with a linker as well but I don't think I've ever seen a linker error, except when doing exotic things far outside of my typical day-to-day.

I guess rustc detects the situations in which the linker would throw an error and then throws its own error preemptively. It leads to a much better user experience than the C++ one, since the error messages produced by the linker are always unnecessarily terrible

Joker_vD

19 hours ago

> I guess rustc detects the situations in which the linker would throw an error and then throws its own error preemptively.

Pretty much. The crucial difference between C and Rust which enables Rust to do this sort of detection is that in Rust, the extern things are anchored in modules (crates? whatever), and so when you import things, you have to say where you are importing them from.

    extern void *magic_init(int);
    extern void *magic_stuff(void*, const char*, int);
    extern void magic_fini(void*);
versus

    use crate_of_magic::{init, stuff, fini};
It even enables one to actually type-check against the imported crate during the compilation (IIRC if Cargo can't locate the imported crate to look into it, it will refuse to build the project), as opposed to hoping that the headers you've included are correctly describing the object file you'll be linking against.

0x457

19 hours ago

Only time I get linker errors in rust is when it's linking some dynamic library written in C.

mschuster91

a day ago

> Like, you could easily write your compiler to do not have to rely on such machinery

You need a linker as soon as you are dealing with either multiple languages in one project (say, C++ and ASM) or if you include other libraries.