1

What is a Relocatable Binary?

I tried doing some search on Google, but I am still confused.

Also: what is the difference between an Executable and a Relocatable Binary?

  • 5
    I think this question needs a bit more detail. What exactly do you find confusing about the concept of relocatable binaries? You mention you've done some googling around the concept, what did you get out of it, if anything? Have you checked the wikipedia page for relocation? – Iker Mar 31 '16 at 7:05
  • 1
    Related question: Purpose of Base Address? – CodesInChaos Mar 31 '16 at 7:29
2

Although this has been accepted as the corrrect answer, Basile's answer better describes the current use of the term. i.e. Data used as the input to a linking and loading process.

However, I have heard the term used to describe relocatable binary as an executable that can be loaded at any memory address, and does not need any addressing "fix-ups" after loading. (The entry address will of course be different depending on where it is loaded). This is more correctly known as position independent code.

The need for position independent code was mainly driven by real-time operating systems, where programs were typically executed directly out of EPROM or ROM, and fix-ups were just not possible.

In the early 1990s I worked with such a system. I thought it was OS-9 (not the Apple version) as described in this Wikipedea article. But after reading it, I may be mistaken. But I'll call it OS-9 anyway.

For such a system to work, several component parts need to mesh:

  • The CPU instruction set has to strongly support program-counter relative addressing. The Intel CPUs did not do this well for anything but trivially small programs. The Motorola 68000 processors were better, but even they needed some help to emulate a "long branch to subroutine" instruction.

  • The compilers need to know to generate code that uses relative branching always. They also need to know how to emulate instructions that the CPU does not natively support.

  • The OS needs to support finding programs in memory and adding them to its directory structures. OS-9 did this by stepping through the memory space at boot time (in 4k? increments), looking for a magic number that identified a program header block. If found, it would compute a CRC of the header. If that matched the CRC stored in the header, then it would compute the CRC of the whole program. If that matched another value in the header, the program would be added to the directory. The advantage was that we could take our diagnostics EPROMs to a client site, plug them into any empty slots on the CPU board and reboot - voila the diagnostics were than available.

But position independent code went out of fashion for many reasons:

  • The rise of the IBM PC architecture, hence the Intel processor, and hence the 8086 instruction set.
  • RAM became cheap and large. There was no longer a driving need to execute code directly from read-only memory.
  • Hard disks became cheap and ubiquitous. As you need to load a program off hard disk into memory for execution, running some trivial code to perform fixups was not a big problem.
  • The rise of portable operating systems like Linux led to a looser coupling between the compiler and machine code. Position independent code was simply a complexity that could be dropped.
  • Shared libraries are a real problem. The address at which the library is loaded cannot be known in advance, so linking position independent code to shared code is difficult.

So another good computing idea fades into history, and relocatable binaries that need fixups are now common. In some languages (e.g. Assembler and C) there are files that contain the relocatable binary. Other languages may hide this step e.g. Java does everything inside the JVM and no intermediate files are produced.

  • An interesting answer, but frankly I'm not sure the phrase is usually intended to mean this. I would generally call what you're talking about "position independent", and the converse (i.e. code that can be relocated via fixing up addresses at load time and/or lazily at run time) as "relocatable". – Jules Apr 1 '16 at 13:49
  • @Jules Thanks for the well-considered feedback. I've taken it on board and updated my answer. – kiwiron Apr 1 '16 at 21:25
5

Relocation is related to linking and loading. Read Levine's book Linkers & Loaders for details. Long time ago (at the beginning of Unix, 1970s) the kernel loaded and started an executable by simply copying blocks -memory segments- from disk to RAM, but today, with virtual memory & paging enabling shared libraries, things are much more complex.

(I'm taking mostly a Linux perspective below; but I guess you can adapt my answer to your OS.)

Usually object files (or libraries) -sometimes called relocatable binaries- contain not only some binary sections (containing machine code and/or data) but also some relocation sections containing a sequence of relocation directives to modify the segment containing the section at link or load time. Even some executables (notably those dynamically linked) may contain relocation directives ... A relocation directive might be: in memory at address A loaded by offset B in file, replace the three following bytes by the 24 lowest bits of difference between A and the value of the linker symbol (e.g. the address of function named) printf

Read more about ELF, and read the ABI specification relevant to your system (e.g. this one for Linux/x86_64 ABI), for details about the particular relocation directives possible on your computer. The actual relocation directives depend upon the processor's instruction set & addressing modes and the flexibility of the linker or operating system kernel.

Read also about position-independent code, self-relocation, dynamic linker, ASLR. See also ld-linux(8) & elf(5). Use and play with readelf(1), objdump(1), ldd(1) to explore and understand some particular ELF binary (e.g. /bin/ls), and execute it with strace(1) to understand the system calls (listed in syscalls(2)...) involved when running it. See also execve(2) & read Advanced Linux Programming to get a broader picture.

In some systems, the relocation directives (actually some bytecode for the linker) may be complex enough to make them Turing complete (iirc, some versions of HPUX for some HPPA RISC processors had very complex relocations, with conditionals; arithmetic; loops).

And you might consider that link time optimization could be seen as some very complex relocation; but most people view it as some weird compiler optimization happening at link time (In fact, the border between compilation & linking & running is unclear, see also just-in-time compilation).

  • What's their reason for such complicated fixups? Why isn't pointer sized addition enough? (At least for load-time relocation, at link time you might want to do more complicated optimizations, like shortening jumps, but I'd expect those to happen on an intermediate representation) – CodesInChaos Mar 31 '16 at 7:42
  • IIRC, some addressing modes are complex enough to be Turing complete. – Basile Starynkevitch Mar 31 '16 at 7:45
  • 1
    @BasileStarynkevitch: The Intel MMU certainly is, or, as the author of that talk so eloquently put it: "Any sufficiently complex input is indistinguishable from byte code; any code that takes such input is indistinguishable from a VM". – Jörg W Mittag Mar 31 '16 at 11:30
  • "Even some executables (notably those dynamically linked) ..." -- not just those that are dynamically linked, as (1) there's a tendence to use the same file format for both static executables and dynamic objects, and unless you specifically strip the relocation entries out of a static executable (and most tools don't tend to bother) they'll stay there, and (2) these days even static executables need to be relocated in order for ASLR to work... – Jules Apr 1 '16 at 13:55
  • I'm not sure I'd recommend starting to learn about object formats by reading about ELF... it's a pretty heavyweight format, that's difficult to grasp easily. Same goes for COFF (and its bastard offspring, Portable Executable). For a beginner, I'd recommend downloading the source code for the NASM assembler. It has a very simple object format, callled RDOFF, that's designed to be easy to understand. It's not a great format, but it works, and there's source code there for a very simple linker and loader, too. – Jules Apr 1 '16 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.