fasterthanlime

Feb 08, 2021 48 min #os · #assembly · #linux · #rust · #elf

In the bowels of glibc

Thanks to my sponsors: L0r3m1p5um, teor, Jörn Huxhorn, Tyler Schmidtke, Lyssieth, John Horowitz, Ula, David Souther, Mathias Brossard, Michael, Geoff Cant, Aalekh Patel, Thehbadger, Mason Ginter, Integer 32, LLC, Matt Jadczak, Chirag Jain, Raphaël Thériault, Makoto Nakashima, Tanner Muro and 266 more L0r3m1p5um, teor, Jörn Huxhorn, Tyler Schmidtke, Lyssieth, John Horowitz, Ula, David Souther, Mathias Brossard, Michael, Geoff Cant, Aalekh Patel, Thehbadger, Mason Ginter, Integer 32, LLC, Matt Jadczak, Chirag Jain, Raphaël Thériault, Makoto Nakashima, Tanner Muro, Chris Biscardi, Marty Penner, Aljaz Erzen, Jesse Luehrs, Damir Vandic, Jake Demarest-Mays, Vincent, Richard Pringle, compwhizii, Geoffrey Thomas, notryanb, Max Bruckner, Chris Thackrey, WeblWabl, Ahmad Alhashemi, std__mpa, Thor Kamphefner, Geoffroy Couprie, Pete LeVasseur, Max von Forell, Duane Sibilly, Raine Godmaire, Johnathan Pagnutti, Dennis Henderson, Antoine Rouaze, Daniel Strittmatter, Aiden Scandella, Dimitri Merejkowsky, Chris Sims, Morgan Rosenkranz, Jelle Besseling, Kamran Khan, Michal Hošna, qrpth, Tabitha, pinkhatbeard, Andrew Neth, Luke Yue, Jan De Landtsheer, Tobias Bahls, Sean Bryant, Berkus Decker, kuerbsikakteen, Dylan Anthony, Jack Maguire, Kyle Lacy, Borys Minaiev, Dom, Helge Eichhorn, Senyo Simpson, prairiewolf, Brandon Piña, Paul Marques Mota, Mike English, Santiago Lema, medzernik, Pete Bevin, Philipp Gniewosz, Andronik, clement, Benjamin Röjder Delnavaz, Kai Kaufman, Matthew Planchard, Paul Schuberth, Andy Gocke, Jack Duvall, Dirkjan Ochtman, hgranthorner, David Barsky, Antoine Boegli, Ben Wishovich, Manuel Hutter, David White, Corey Alexander, Shane Lillie, Guillaume Demonet, Malik Bougacha, Matt Campbell, Julian Schmid, Romain Kelifa, Elijah Voigt, Sawyer Knoblich, Aleksandre Khokhiashvili, avborhanian, bbutkovic, René Ribaud, Stephan Buys, genny, callym, Ivo Murrell, Egor Ternovoi, Nicholas, Mark, ZacJW, Jonathan Adams, Adam Lassek, Gorazd Brumen, Joshua Roesslein, C J Silverio, villem, hardfist, Timothée Gerber, Romain Ruetschi, Torben Clasen, Yuriy Taraday, Astrid, Toon Willems, Adam Gutglick, Ross Williams, Noel, Das Gürteltier, Mark Old, Beat Scherrer, Sindre Johansen, Michael Mrozek, Peter Shih, Cass, Luke Konopka, Marky Mark, Mark Tomlin, SeniorMars, Chris, Zaki, Lena Schönburg, David E Disch, ofrighil, Tyler Bloom, Enrico Zschemisch, James Brown, Richard Stephens, Jean Manguy, Alex Krantz, Valentin Mariette, Tiziano Santoro, Rufus Cable, Mario Fleischhacker, James Rhodes, Josh Triplett, Sam Leonard, Mike Cripps, Steven Pham, Marco Carmosino, Scott Steele, Philipp Hatt, Braidon Whatley, Alejandro Angulo, playest, G, Lev Khoroshansky, Daniel Wagner-Hall, Radu Matei, jer, Nicolas Riebesel, Horváth-Lázár Péter, Mattia Valzelli, Christopher Valerio, Herman J. Radtke III, Zachary Thomas, Ian McLinden, Yves, Laine Taffin Altman, Andy F, Nyefan, Samit Basu, jatescher, Vladimir, Mikkel Rasmussen, Matt Jackson, Guy Waldman, Lennart Oldenburg, Ben Mitchell, Ryan, Marie Janssen, Jacob Cheriathundam, Diego Roig, Scott Sanderson, Marcus Brito, Olly Swanson, belzael, Marcus Griep, Josiah Bull, Beth Rennie, Julius Riegel, Max Heaton, Alan O'Donnell, Zoran Zaric, Johan Saf, Sonny Scroggin, James Leitch, Lucille Blumire, Ronen Ulanovsky, Marc-Andre Giroux, Leigh Oliver, Paul Horn, old.woman.josiah, Seth, Jean-David Gadina, Blake Johnson, Chris Walker, Yufan Lou, Cole Tobin, Justin Ossevoort, Chris Emery, Jon Gjengset, xales, traxys, Matěj Volf, Evan Relf, Mateusz Wykurz, David Cornu, (18D)eezNuts, Isak Sunde Singh, Luiz Ferraz, Paige Ruten, Romet Tagobert, budrick, Jim, Garret Kelly, Walther, Hadrien G., Ives van Hoorne, Niels Abildgaard, Olivia Crain, Cole Kurkowski, Gioele Pannetto, anichno, you got maiL, Michael Alyn Miller, Simon Menke, Michał Bartoszkiewicz, Urs Metz, Joseph Montanaro, Daniel Papp, AdrianEddy, John VanEnk, Kristoffer Winther Balling, Christian Bourjau, Neil Blakey-Milner, Alex Rudy, Wojciech Smołka, Marcin Kołodziej, Henrik Tudborg, Sylvie Nightshade, Antoine PESTEL-ROPARS, Matt Heise, Colin VanDervoort, Sarah Berrettini, Zeeger Lubsen, Xirvik Servers, Wyatt Herkamp, Matthew T, Jan-Stefan Janetzky, Guilherme Neubaner, Victor Song, Bob Ippolito, Daniel Silverstone, Eugene Bulkin, ACRL, Ronen Cohen, Xavier Groleau, Christoph Grabo, Boris Dolgov, Marcus Griep, ShikChen, Yann Schwartz, Guillaume E

Good morning, and welcome back to “how many executables can we run with our custom dynamic loader before things get really out of control”.

In Part 13, we “implemented” thread-local storage. I’m using scare quotes because, well, we spent most of the article blabbering about Addressing Memory Through The Ages, And Other Fun Tidbits.

But that was then, and this is now, which is, uh, nine months later. Not only am I wiser and more productive, I’m also finally done updating all the previous thirteen parts of this series to fix some inconsistencies, upgrade crate versions, and redo all the diagrams as SVG.

Without further ado, let’s finish this series, shall we?

Yay!

So far, most of the programs we’ve been able to execute using our “runtime linker/loader” were purpose-built for it. We’ve come up with quite a few sample assembly, C and Rust programs over the course of this series.

And there was a very good reason for that: it allowed us to focus on one specific aspect of loading ELF objects at a time, all the way from “what’s even in an ELF executable” to “how come different threads see different data?”, passing through “what even is memory protection” and “so you mean to tell me the linker executes some of your own code besides initializers? just to resolve symbols?”

But, just like ideologies, linkers only start being fun when you apply them to the real world.

So let’s try our best to run an actual, honest-to-blorg executable that we didn’t have any hand in making - we didn’t make the source, we didn’t compile it, we didn’t somehow patch it just so it works with our dynamic loader - an executable straight out of a Linux distribution package.

In my case, an ArchLinux package, but if there’s one thing Linux distributions agree on, it’s ELF, so, never fear.

But, just like planning a saturday night during a pandemic, the key to success is managing expectations.

We’ll start simple. Like, with /bin/ls.

Let’s look at it from a bunch of angles before we even attempt to load it with elk.

Let’s review! Just to make sure we haven’t gotten too rusty.

PHDR is?

Program headers!

INTERP?

The interpreter! ie. the program that the kernel would normally rely on to load this program, in this case /lib64/ld-linux-x86-64.so.2. But we are loading the program so this doesn’t matter.

LOAD?

Those are regions of the file actually mapped in memory! Some contain code, some contain data, or thread-local data, or constants, etc.

Everything else?

Largely irrelevant for this series!

Attabear. Thanks for the recap bear.

The pleasure is often mine.

What else can we tell from this output… well, it has an interpreter in the first place, so there’s probably relocations:

There is! And it’s dyn so it probably relies on some dynamic libraries.

It does! libcap.so.2 and libc.so.6.

Wait, don’t we usually use ldd to find that out?

Yeah, if you’re lazy.

But we are lazy.

True, true.

Oh, this also shows ld-linux.so, glibc’s dynamic linker/loader!

Yes! I guess it technically is a dependency.

The “vdso” object is also listed!

Right, to make syscalls faster.

But let’s go back to relocations - are there any relocations we don’t support yet?

Mhh, no, that looks good.

I remember all of these!

Well, there’s only thing left to do then:

Of course.

To be fair, we already tried it at the end of Part 13, and it didn’t work then either. Since we haven’t changed anything since then, it stands to reason that the result would n-

A MAN CAN DREAM, BEAR, okay?

Bear enough. I’m afraid you’ll have to actually write your way out of this one though, running it again won’t suddenly start to work.

Fine, fine. Let’s do a quick check-in with our favorite frenemy, GDB.

Okay, it also crashes under the GDB. Which is? Bear?

Good! It’s good. If it didn’t crash under GDB, our life would be significantly worse.

Correct. Also, it means it occurs even with ASLR disabled.

With what now?

Uhhh we’ll talk about it later.

Anyway, let’s find out exactly where we crashed - by using our custom GDB command, autosym.

And try to get a sense of our surroundings once again:

Interesting. Very, very interesting.

Let’s look at what’s happening here a little closer.

Except, instead of blindly looking at disassembly, we’ll pull up the glibc sources so we can see what’s actually happening.

First off, on frame 9, we have __libc_start_main. This is hardly our first rodeo, we’ve seen that one before, and it goes places. It stands to reason that eventually, at some point, glibc would want to initializes its own allocator - which is why on line 2, we have ptmalloc_init.

Why ptmalloc? Well, it stands for “pthreads malloc”, which is derived from “dlmalloc” (Doug Lea malloc). That’s right — we can’t escape history no matter how hard we try.

How interesting! How very, very interesting.

There’s so much to look at here. First of, there’s a global variable that stores whether or not malloc was already initialized. It’s set to -1 by default.

So, at the very start of ptmalloc_init, if that variable is 0 or greater, we have nothing to do. Otherwise, we ourselves set it to zero.

Weird boolean but okay.

Well, it’s actually set to 1 when ptmalloc_init finishes successfully.

It’s.. a bit hard to follow, let’s not go there for now.

And then, only if this code is compiled into a dynamic ELF object (which it is, here, because we’re executing it straight out of /lib/libc-2.32.so), we check if that ELF has been opened dynamically, or if it’s in a non-default namespace:

And depending on that, it decides whether to use brk or not.

And that’s exciting!

It is?

Yes! Because we’ve never talked about brk before!

So we’re not getting ls to run for another page or six, is what you’re getting at?

Exactly!

Let’s cut to the chase. brk is, pretty much, the end of the heap.

And we’ve talked about the heap before!

Typically when you read about the heap in articles like this one, you tend to see diagrams like these:

Which basically says: variables can live in the stack or the heap, and you can even have stack variables point or refer to heap variables. And you allocate heap variables with malloc, or Box::new, or something.

Of course it’s a bit nebulous where the heap is in that diagram — it’s just a cloud.

And it’s not exactly clear why we need the heap anyway. Couldn’t we just put everything on the stack?

Well, no, the article keeps on going, because the stack is small. On my current machine, the stack size for a newly-launched executable is 8MiB:

And that’s not enough! But of course, you can always ask for more stack, either system-wide or just for your process. You can even use something like Split Stacks.

So that’s not the real reason why we need the heap.

The real reason we need the heap becomes clearer if we make our diagram a little closer to reality.

Let’s say we have a program like this:

At the very beginning of our program, the stack only contains whatever the operating system saw fit to give us - environment variables, arguments, and auxiliary vectors:

Cool Bear's hot tip

The left area represents code, each outer box is a function, and each inner box is an “instruction”, although it’s shown as C code. $rip here is the Instruction Pointer, ie. what we’re currently executing.

Then, the locals for our main function are allocated on the stack, and initialized:

The following line, str = f(42) is a bit complicated - showing C sources isn’t ideal here, because several things are happening out of order.

Before thinking about str, we must call f! Let’s split that line into two blocks on the diagram, in an attempt at making things clearer:

So first, we push our argument to the stack.

Wait, would an argument like that really be passed on the stack?

Not in this specific case, under the System V AMD64 ABI, no.

These diagrams are also lie, they’re just slightly closer to reality. We’re just pretending registers don’t exist for the time being.

But if we had lots of arguments, or large arguments, some of them would be pushed to the stack.

So, we push our argument, and then we have to push the return address - so that when f is done, we know where to resume execution of our program.

And then we reserve enough space for the local variables of f, and initialize them as well:

And here’s the important bit - when we return, everything that’s related to f on the stack is “popped off”. It just disappears.

Its locals are “freed”, the arguments are freed as well, and the return address is, well, where we return to.

…but we returned the address of a local of f(), which has just been freed! That is actually why we need the heap. Because sometimes, we need variables to live longer than a function.

Wait, does that mean…

…we have to think about lifetimes even when we write C?

Especially* when you write C, because the compiler is not looking out for you, save for a few specific cases (like this one here — returning the address of a local is a pretty obvious giveaway that something is wrong).

The thing is… those bugs are not always easy to find. Here for example, as long as nothing else is allocated on the stack, str will point to a region of memory that contains the string “hi!\0”.

Because “freeing memory from the stack” does not actually free it — it just changes the value of the %rsp register. Everything is still there, in memory!

Of course, if we were to call another function, which also had locals, then everything would become corrupted.

This is typically the kind of bug that memory-safe languages like Rust would prevent and the reason why should really consid-

Amos, amos, this is not that kind of article.

Oh, right, ELF.

Anyway, if f() allocated data on the heap instead, it would still be valid by the time it returned to main(), like so:

And then we could forget to free it, which would result in a memory leak, another problem that a language like Rus-

Amos! Focus!!

Right, right.

But where is the heap?

Well, this kind of diagram is very common:

And it’s honestly not that bad? There’s a lot worse out there.

The stack does grow down on 64-bit Linux, the heap does grow up, it is indeed right after the last “load section” mapped from our main executable file. There’s a lot about this diagram I agree with!

But also, those arrows look awfully close. As if… as if the stack and the heap could somehow collide. And, well, if you’re stuck a few decades in the past or programming for very small devices, that’s an actual risk!

But on contemporary 64-bit Linux, that’s, uhhh, not an issue.

Let’s take an actual look at where our heap and stack are for /bin/ls:

Oh ok. They’re real far from each other.

I know, that’s what I’m getting at!

Amos, I don’t think you understand just how far they are. Let me do a quick calculation here, to get them to collide, you would have to allocate… 47 terabytes!

And there you have it. For systems where memory is scarce, and memory protection does not exist, there is a real risk of the heap and the stack overwriting each other. And a real opportunity to free up some heap to allow using more stack, or the other way around.

On a consumer-grade desktop or laptop computer in 2021, running 64-bit Linux though? Nah.

So. We’ve found out that, at least on my system, processes start with an 8MB stack, and looking at this line in /proc/:pid/maps:

…this is not 8MB. It’s more like 136 kibibytes. An odd number.

So what was that 8MB value? Let’s find out:

Ah, right. It’s more of a maximum — hence why the command to query the system-wide parameter is called ulimit, and the relevant system calls are called getrlimit and setrlimit.

Anyway, to recap:

• The stack grows down, because that’s how we’ve always done things
• “Allocating on the stack” is just setting the %rsp register
• There is a maximum amount of stack the kernel will allow, after which you’ll get a segmentation fault.
• You can ask the kernel for more stack with the setrlimit syscall.

…but what about the heap?

Well, it’s pretty much the same thing, only instead of using setrlimit, you use the brk syscall.

When /bin/ls just starts up, it has a heap of 4KiB:

And then, if it calls brk, it can get more.

Well.. does it call brk?

Yes it does! Let’s look at what its heap is just when it’s about to exit.

The heap has grown from 0x1000 to 0x22000! That’s 136 KiB.

But here’s an important question. A very important question.

A dynamically-linked program is typically made up of a bunch of different pieces of code, who all must share the same stack, the same registers, and the same heap.

For the stack and registers, it’s easy. The System V AMD64 ABI says exactly what registers must be used when passing arguments to functions, when returning values from functions, etc. It also says where to put what on the stack so that neither the caller nor the callee step on each other’s toes.

But for the heap, well… it’s not that simple.

Because the heap is pretty much a stack as well. “Allocating on the heap”, when using the brk syscall, just means “moving the program break”, just like “allocating on the stack” means “changing the value of %rsp”.

And so, if some function uses brk to allocate some memory, then calls another function that also uses brk, and that second function returns a pointer to its newly-allocated memory, there’s a risk that the function could deallocate it accidentally, by restoring the program break to what it was before!

So, how do we get all programs to play nice together?

It’s simple! We don’t actually use brk.

We let the C library do it.

C programs typically use malloc (and friends) rather than brk directly.

So when you malloc something, the glibc allocator tries to find a place in the heap that’s already reserved. And if there isn’t any, it can use brk to reserve more.

And when a block of memory is freed, it doesn’t necessarily use brk to actually free up that memory. It just makes a note that this block is now free, and it can be re-used for future allocations.

So the scenario from before is no issue! malloc is in charge of setting the program break (brk), and it handles all allocations and deallocations on the heap.

As long as all the bits of codes (shared libraries) used by a program all let glibc’s memory allocator deal with brk, there are no conflicts, and everything works great.

Which is exactly what ptmalloc_init is trying to assess here:

See, if a program links directly against glibc, it’s fair to assume that ptmalloc has full control of the program break: it can use brk as it pleases.

But if glibc was somehow loaded dynamically, or something else fishy is going on, it’s entirely possible that brk is controlled by some other piece of code, and if glibc started messing with it haphazardly, chaos would ensue.

So, if it detects a fishy scenario, it sets __morecore, its brk helper, to __failing_morecore, which pretty much simulates failures of the brk system call, making it behave as if we already ran out of heap!

Otherwise, it uses __default_morecore, which just calls the brk syscall:

Cool Bear's hot tip

There is only one brk system call: it takes the address of the program break you want to set, and returns the new address of the program break.

In case of failures, it just returns the old program break. Passing the address 0x0 will always fail, so it can be used to query the current program break.

The C library, however (well, the Single Unix Specification - it’s been deprecated in POSIX.1-2001), makes everything more confusing by having two functions.

The brk() function sets the location of the program break, and returns zero on success. The sbrk() function takes a delta, so that it can increment or decrement the program break, and returns the previous program break, or (void*) -1 in case of failures.

This was presumably to make it easier to use sbrk() in application code, since the previous program break would point to the start of the newly-allocated memory block.

Which brings us to our next question: if ptmalloc decides that it cannot use brk, then what is it going to use?

Well, mmap of course! It’s what we’ve been using in elk all along.

mmap is a perfectly fine way to ask the kernel for some memory. It just has higher overhead, because instead of just keeping track of the “end of the heap”, the kernel has to keep track of which regions are mapped, whether they correspond to a file descriptor, their permissions, whether they ought to be be merged, etc.

And now, let’s get back to trying to run /bin/ls with elk.

Let’s get back to our GDB session:

We’ve seen that ptmalloc_init calls _dl_addr to determine how it’s been loaded exactly. But why do we end up jumping to 0x0?

Let’s see what’s happening in frame 1:

Wait, that’s a mov, not a call - I think we need to disassemble the instruction right before $rip:

There. That’s the one. And it corresponds to this line of code:

But wait. Let’s look at the address of this frame: 0x00007ffff78c6058. Where does it come from?

libc-2.32.so, okay.

And the address it’s trying to call, what is it?

It’s.. in ld-2.32.so, okay. And it’s null, right?

Yeah, it’s null. And what is it supposed to be?

It’s supposed to be… 0xf88 into _rtld_global@@GLIBC_PRIVATE:

Yup. And it just happens to be zero here.

So what is this _rtld_global symbol? Let’s try running /bin/ls on its own and stepping through _dl_addr

Let’s set a breakpoint riiiiight before that call:

Perfect. Now, what address are we calling exactly?

Interesting, interesting. It’s definitely not null this time.

But what is it?

Whoa. WHOA! It’s a function provided by ld-linux-x86-64.so.2!

Yes!

glibc’s dynamic linker slash loader!

Yes!!

Well yeah! It’s freaking dladdr, what did you expect?

ld-linux.so, the loader, loads the binary, ls, which is itself linked against libc.so, which ends up calling back into ld.so, which is really what ld-linux.so (which is a symlink) points to!

Which makes sense! Because ld-linux.so is the dynamic loader, so it’s the one in charge of looking up symbols. If we want our programs to be able to look up symbols at runtime, they need to be able to call back into the loader.

If we did lazy loading, like we said we wouldn’t in Part 9, we’d set the address of one of elk’s function into the GOT (Global Offset Table), so that the first time a function like printf@plt is called, control goes back to the loader, we can resolve the function, overwrite the GOT, and call the actual function.

But we don’t do lazy loading, we resolve everything ahead of time, for simplicity. Something we cannot really do here for dladdr, because we can’t know ahead of time which symbol is going to be looked up with it.

Heck, the name passed to dladdr might be a string provided by the user! It might be randomly generated! It might be received over the network! We just cannot tell.

But to be honest, implementing dladdr within elk doesn’t sound too hard. The problem is: it goes deeper. Way deeper.

We mentioned that ls links against libc.so, which in turns links against ld.so, which is literally the same file as ld-linux.so.

So ld-linux.so is already loaded into the process’s memory space, even though it wasn’t the loader. And ld-linux.so, aka ld.so, already provides an implementation of dladdr, whose internal name is _dl_addr.

But it relies on some internal state, defined here:

…which was never initialized in the first place! Either because our loader is incomplete, or because ld-linux.so only initializes it when it’s loaded by the kernel as an executable through its entry point, not as a dynamic library.

But say we somehow manage to either fix up our loader or fake that data structure somehow, the disassembly for __GI__dl_addr (the real internal name of _dl_addr, itself an internal name for dladdr) has further bad news:

uwu, what’s this? _dl_find_dso_for_object? This also looks like something that should be provided by the dynamic loader itself.

Where is it exactly?

Oh.. oh no…

Wait a minute… plt.sec… there’s a second PLT?

Apparently so, yes.

So yeah. Turns out, when you want to make an ELF object that’s a dynamic loader, and an executable, and also a library, but can also be linked statically with other code to make mostly-static executables, you have to use a couple tricks.

And this part right there blew my mind, and I hope it blows yours too.

Let’s make a simple C program.

And build it, and run it:

What’s in there?

(Newlines added for readability).

Okay, it’s dynamically-linked, it relies on /lib64/ld-linux-x86-64.so.2, glibc’s dynamic loader (or dynamic linker, I know, words are confusing).

So obviously, it has relocations:

Which is fine! Because ld-linux.so loads it, and ld-linux.so knows about relocations, so it can apply them before jumping to what’s entry point.

Everything makes sense so far.

Now let’s make it into a static executable:

And look at it:

Okay! This time it does not have an interpreter, so that means it cannot have relocations, right?

In fact, if we look at the program headers:

We can see that they start at 0x400000, which is a perfectly fine base address for an executable.

Now let’s make it a static-pie.

And look at it:

Wait, dynamically linked?

What?

What?

Wait, so does that mean it has relocations?

Oh gosh, it does.

What about the fully-static version?

It does too!

…what about ld-linux.so?

It does too! What?

Who processes the relocations for ld-2.32.so?

Is it the kernel?

We know that when we launch /bin/ls, for example, it’s first loaded by the Linux kernel, which knows about the INTERP section, and so it also loads /lib/ld-linux-x86-64.so.2, and eventually transfers to control to the entry point of ld-linux.so.

So, since the kernel knows about interpreters, maybe it also knows about some relocations? The simple ones?

Let’s find out.

If the kernel knew about relocations, and applied some of them, then they would be applied when a “static” build of what.c starts executing, right? It would happen before transferring control to its entry point.

So, let’s find out.

Okay, we got a couple relocations here we can check.

Let’s start up what under GDB and break as soon as we can, with starti, which means “Start the debugged program stopping at the first instruction”.

Great. Now we need to figure out where the relocations above actually are in the memory space of our process.

This should be simple maths, but it can be error-prone so let’s be super careful.

Let’s compare with our first relocation:

Oh, actually there’s no maths at all, because this is a “fully static” build of “what”, so it has a fixed entry point, so it cannot be moved around, so the virtual address of a relocation in the process’s address space is the exact same as the “offset” shown by readelf.

Very well then, what’s in that first relocation slot?

Ah. That’s not null at all.

What is it even?

Cool Bear's hot tip

For the dig command below to work, you’ll need to cargo install --path ./elk again, since we only recently added support for TLS symbols, and what definitely has some.

Mhhokay, somewhere in the PLT (Program Linkage Table).

Does it look valid code?

Not really?

Okay, not much makes sense right now, but let’s keep looking.

Can we check to see if it’s ever written to? Answer, yes: GDB has the watch command for that.

If it is being relocated after program startup, it’s definitely going to be written to, so:

And then we continue program execution:

AhAH! Caught in the act!!!

Let’s see here… the old value is…

Yeah, same as before. And the new value is?

Ohhhhhhhhhhhh!!!! strchr!

Better! The AVX2 variant of strchr!

Righhhhhhht. Right right right. This is what IRELATIVE relocations do. Hey, it’s been a while - no judgement.

Although everything is statically linked, glibc is still trying to give us the fastest available variants of some functions.

And an IRELATIVE relocation is a perfectly fine mechanism to pick a function variant at runtime! Why reinvent the wheel? Just do it the same as a dynamically linked executable.

So in fact those addresses on the right:

Are just selector functions!

Of course for IRELATIVE relocations to work, someone has to call those functions, and the kernel sure doesn’t do it (can you imagine? if the kernel called into userland just to load an executable? yeesh).

So what do we do? We just embed a bit of the dynamic loader in our static executable! What’s the harm?

GDB is a little out of its depth here — it’s not able to show us the corresponding sources.

So let’s try it on the actual dynamic loader. After all, it has relocations too!

And it doesn’t ask for an interpreter (which.. would be itself, anyway):

So again, someone has to process those relocations right?

Well…

We can see it was mapped by the kernel at a base address of 0x7ffff7fd0000, and so if we want to watch for the relocation at offset 0x000000000002c6c0, that’s what we need to add to it:

And then, well, then…

…then we end up right in the middle of ld-2.32.so relocating itself.

Which is a good opportunity to compare our code with the equivalent glibc code, since we also implemented relocations. So, this should look very familiar:

No? It doesn’t look familiar?

Uhhh….

Well, let’s just be thankful we didn’t pick C for this project. And that our loader doesn’t need to understand versioning, and run in an as many scenarios as the glibc loader.

Anyway, the smoking gun was in _dl_start all along:

Which is freaking fascinating, if you ask me.

Because up until now, we’ve sorta had two mental categories in which executables fell:

• Either they’re statically linked, and the kernel can map them into memory and immediately jump to the entry point with no relocations to worry about.
• Or they’re dynamically linked, and they need an interpreter, which the kernel also needs to map in memory and then jump to the intepreter’s entry point so that it can perform the required relocations.

But that turned out to be a little simplistic didn’t it!

Because it’s not like there’s a binary flag in the ELF format that says “static” or “dynamic”. All of the following things are involved in determining how an executable works:

• Does it have an INTERP section?
• Does its first LOAD section start at 0x0?
• Does it contain relocations?
• Does it have NEEDED entries in its DYNAMIC section?

And some of these are connected, but there’s nothing that really forces all of these to be in a certain combination.

For example, you can have NEEDED entries in the DYNAMIC section: the kernel is not going to anything with it! Unless you have an interpreter that specifically looks for those sections and does something with them, nothing’s going to happen!

Similarly, if you have an executable whose LOAD sections start at 0x0, but its code is not relocatable, well, things are going to get complicated.

On some level, it’s intuitive — “of course, we need 0x0 to be NULL!”. But turns out, no we don’t, because the bit-representation of NULL is implementation-defined, see Kate’s excellent thread about NULL in C.

So our intuition is wrong… well surely mmap prevents us from mapping 0x0 then? Because gcc is definitely using 0x0 as a bit representation for NULL, at least by default.

Let’s look at mmap’s man page:

Notes

The portable way to create a mapping is to specify addr as 0 (NULL), and omit MAP_FIXED from flags. In this case, the system chooses the address for the mapping; the address is chosen so as not to conflict with any existing mapping, and will not be 0. If the MAP_FIXED flag is specified, and addr is 0 (NULL), then the mapped address will be 0 (NULL).

On the surface it looks fishy, but no, it says if we try to map 0x0, it’ll return 0x0, which is what it would do if it succeeded.

So… we can map 0x0?

Mhhh, no we can’t? Let’s check strace to be sure:

Oh! Not permitted? So that means…

Innnteresting.

So, wait, can we actually have an executable that asks to be mapped at 0x0?

Because by default, GNU ld gives us a base address of 0x400000:

Because, well, because that’s what’s in its default linker script:

But could we convince GNU ld to use 0x0 as a base address instead?

Whoa. Whoa!

Does it run?

Oh, right, permission denied.

Okay, so, see? Pretty much everything we’ve taken for granted was… not that simple. You can map to 0x0, in fact, Linus says it’s required by some programs:

From: Linus Torvalds torvalds@linux-foundation.org Newsgroups: fa.linux.kernel Subject: Re: Security fix for remapping of page 0 Date: Wed, 03 Jun 2009 15:08:52 UTC Message-ID: fa.KTGzEOLON4iMwM7Le/G/y2O3kF4@ifi.uio.no

On Wed, 3 Jun 2009, Christoph Lameter wrote:

Ok. So what we need to do is stop this toying around with remapping of page 0. The following patch contains a fix and a test program that demonstrates the issue.

No, we need to be able to map to address zero.

It may not be very common, but things like vm86 require it - vm86 mode always starts at virtual address zero.

For similar reasons, some other emulation environments will want it too, simply because they want to emulate another environment that has an address space starting at 0, and don’t want to add a base to all address calculations.

There are historically even some crazy optimizing compilers that decided that they need to be able to optimize accesses of a pointer across a NULL pointer check, so that they can turn code like

if (!ptr) return; val = ptr->member;

into doing the load early. In order to support that optimization, they have a runtime that always maps some garbage at virtual address zero.

(I don’t remember who did this, but my dim memory wants to say it was some HP-UX compiler. Scheduling loads early can be a big deal on especially in-order machines with nonblocking cache accesses).

The point being that we do need to support mmap at zero. Not necessarily universally, but it can’t be some fixed “we don’t allow that”.

— Linus

So sometimes you really do need to be able to map 0x0. But it’s kinda dangerous, so you need to be root or have capability CAP_SYS_RAWIO.

From man 7 capabilities:

CAP_SYS_RAWIO

• Perform I/O port operations (iopl(2) and ioperm(2));
• access /proc/kcore;
• employ the FIBMAP ioctl(2) operation;
• open devices for accessing x86 model-specific registers (MSRs, see msr(4));
• update /proc/sys/vm/mmap_min_addr;
• create memory mappings at addresses below the value specified by /proc/sys/vm/mmap_min_addr;
• map files in /proc/bus/pci;
• open /dev/mem and /dev/kmem;
• perform various SCSI device commands;
• perform certain operations on hpsa(4) and cciss(4) devices;
• perform a range of device-specific operations on other devices.

But most commonly, executables that have their first LOAD section at 0x0 don’t actually require privileges to be executed — they just don’t fall neatly into one of our two earlier categories, because:

• They don’t have an INTERP section
• They do have relocations

ie., they self-relocate.

That’s the case for /lib64/ld-linux-x86-64.so.

Starts at 0x0:

No interpreter:

Has relocations:

And that’s why file and ldd give conflicting output — because they’re looking at different things.

file looks at the ELF file type - if it’s DYN, it’s dynamically-linked!

Whereas ldd looks for NEEDED dynamic entries. If there’s none, it’s statically-linked!

Well, the truth is, there is no such thing as a statically-linked or dynamically-linked executable.

Or, to be more precise, some executables are.. a little bit of both.

Let’s look at some of the comments from the glibc sources:

This is just before the “call” to ELF_DYNAMIC_RELOCATE (actually a macro).

Shortly after, we have this comment:

And that’s one of the many reasons the code for glibc is so hard to read.

It is written extremely carefully so that some parts can execute before it was relocated. Sure, it has inline assembly as well, but as we’ve seen, functions like elf_dynamic_do_Rel (and elf_dynamic_do_Rela) are written in C!

They’re just inlined, and they avoid accessing any static data, or calling other functions, etc. They avoid anything that would require relocations to be processed.

Okay, okay, that’s amazing and all, we’ve all learned a lot, blah blah.

But how are we actually going to run /bin/ls?

Oh, that’s easy!

Well, we’re going to cheat.

If we can’t run glibc’s _dl_addr function, why don’t we provide our own?

It’s not like /bin/ls actually needs to open libraries at runtime anyway. It’s just a trick glibc uses at startup to determine if it’s being dlopen’d or not.

So, we’re gonna replace _dl_addr with a version that always fails!

And since I have time travelling abilities, we’re also going to replace exit. It is way deep into glibc internals as well, and is going to cause problems if we don’t nip it in the bud.

All we need our _dl_addr to do is return 0, and in the System V AMD64 ABI, we return things in the %rax register, so, with a little help from our neighborhood assembler:

Wonderful!

So, what’s the easiest way to replace _dl_addr and exit in libc? Just straight up overwrite them in memory.

That’s right. We’ve got the technology.

And now we just have to call patch_libc! It’s implemented against Process<Loading>, so we need to call it at this stage:

And just like that:

…it still doesn’t work.

So we forgot about a few things! To err is human.

For example, we forgot that shared libraries also have entry points. Well, they have initializers and finalizers.

We’ll care mostly about the initializers here.

Let’s add a field for them in Object:

And let’s read them in Process::<Loading>::load_object:

Next, we’ll introduce a method to get all initializers in the order in which they should be called:

And now, of course, we’ll need to call them.

Apparently, glibc calls them with argc, argv, envp:

…so that’s what we’ll do too!

The call_init function is just a small, unsafe helper:

Good! Now, does it work?

Of course not! We’ve still got a bit of work.

Remember Part 9? That’s where we first learned about indirect relocations.

Back then, we thought all indirect relocations were of type R_X86_64_IRELATIVE. But we were wrong! We were so wrong.

As it turns out, any relocation can be indirect, if it points to a symbol of type IFUNC.

We don’t even have to look particularly hard to find some. A bunch of glibc’s functions are IFUNCs, ie. they provide several variants, one of which is selected at runtime:

And /bin/ls uses some of those:

See that? Those aren’t IRELATIVE relocations. They’re GLOB_DAT!

So, we have to care the type of a symbol a relocation is pointing to.

In ObjectSym::value, we can’t just return base + value. We have to add a special case for IFUNC symbols:

But that’s not enough. /bin/ls still segfaults under elk, this time while running initializers:

Hunting down those mistakes took me days, so I’ll cut to the chase.

The problem with IFUNC selectors is that… they’re just functions. And they can call other functions. And access static data. They don’t assume anything specific about the environment — anything is fair game.

So, for IFUNC selectors to run properly, we need to first apply all the direct relocations, and then all the indirect ones.

For that, we’ll add a getter:

An enum to describe our two “relocation groups”:

Since we’ll need to process relocations in two passes, we’ll adjust apply_relocation slightly.

This change also requires changing the callsite — but only minimally!

It’s still fairly short and sweet (if you like iterators):

Okay, how about now. Surely now we’re done?

looks at article estimated reading time I sure hope so!

Mhh, not quite.

Ever wondered why, in the output of readelf, they list the zeroth symbol?

Well, because, as it turns out, some relocations use that symbol.

That’s right. Shock! Awe! Career changes!

And so, when a relocation asks for the zeroth symbol, it wants the zeroth symbol of the object file the relocation is in.

Well, we can do that.

First a handy getter:

And then, in apply_relocation:

Is that it? Are we done? Can we go home?

Well, let’s find out:

…holy crap. Are we running /bin/ls?

We’re running /bin/ls!

All that hard work finally paid off!

Can you believe it?

But of course, now I can’t help but wonder… what else can we run?

Can we run nano?

No we can’t. Well..

No. NO! No cliffhangers this time around! I WANT TO RUN NANO.

Okay, okay… let’s look at the stack trace.

Interesting! It crashes right at the end of this loop:

…when trying to free some memory.

Waaaaaaait a minute. elk is just a regular Rust program. It also uses libc by default. Including its memory allocator.

And you know what the glibc memory allocator loooooves? Thread locals! So it’s all nice and fast.

There’s just one problem. We’ve just messed with the value of the %fs segment register (as seen in Part 13).

So, there’s no memory allocating or freeing for us after that point.

And a for elem in coll loop allocates an iterator. Maybe if we did a release build the iterator would be optimized away?

Or maybe we can just iterate through those initializers a simpler way…

Let’s give it a shot?

So we made an ELF dynamic loader / runtime linker / whatever you want to call it really.

But is that really what this series is about?

Wait, your series have topics?

Uhhh occasionally yeah.

It’s not! It’s not what this series is about.

This series is, apart from a great excuse to learn more about ELF files, about building an executable packer.

And if there’s one thing that’s become crystal clear, especially in this last part, it’s that trying to compete with glibc’s dynamic loader is a bit silly.

Don’t get me wrong, we got far.

But consider what else we’d have to support.

All of these.

Notice how our loader crashed and burned when we so much as iterated through a collection after setting the %fs register? Well, we’d have to run a whole lot of code to support dlopen, dlclose, dladdr, dlsym etc., at runtime. After transferring control to the program’s entry point.

That’s not gonna be easy.

And have you considered: threads? Yes, threads!

What if multiple threads open the same library concurrently? What did you think that dl_load_lock was about? 😅

What if the same library is opened N times? And closed only N-1 times?

Oh, I forgot! What if we dlopen a library that needs thread-local storage? What if, god forbid, we run out of thread-local storage while opening a library?

The GNU C Library’s initial release was 34 years ago.

We can’t catch up. We simply don’t have that kind of time.

Cool Bear's hot tip

Others do, apparently, but they’re taking a much simpler approach to things than glibc does. I don’t think the musl ELF loader can load glibc-linked binaries!

So, what are we to do?

Well, we can just use glibc’s dynamic loader!

We don’t need to bring our own.

After all, /lib64/ld-linux-x86-64.so is already self-relocating… so all our executable packer would need to do is map it at the right address, adjust protections, maybe take care of some other minor details, and then, hey, ho, away we go.

Right?

🙃 🙃 🙃

Comment on /r/fasterthanlime

Here's another article just for you:

Why is my Rust build so slow?

Dec 30, 2021

36 min #rust · #release-engineering

I’ve recently come back to an older project of mine (that powers this website), and as I did some maintenance work: upgrade to newer crates, upgrade to a newer rustc, I noticed that my build was taking too damn long!

For me, this is a big issue. Because I juggle a lot of things at any given time, and I have less and less time to just hyperfocus on an issue, I try to make my setup as productive as possible.

Read more