In software development, relocation is the process of assigning load addresses for position-dependent code and data of a program and adjusting the code and data to reflect the assigned addresses.

A linker usually performs relocation in conjunction with symbol resolution, the process of searching files and libraries to replace symbolic references or names of libraries with actual usable addresses in memory before running a program.

Relocation is typically done by the linker at link time, but it can also be done at load time by a relocating loader, or at run time by the running program itself.

Segmentation

Object files are typically segmented into various memory segment or section types. Example segment types include code segment (.text), initialized data segment (.data), uninitialized data segment (.bss), or others as established by the programmer, such as common segments, or named static segments.

Relocation table

The relocation table is a list of addresses created by a compiler or assembler and stored in the object or executable file. Each entry in the table references an absolute address in the object code that must be changed when the loader relocates the program so that it will refer to the correct location. Entries in the relocation table are known as fixups and are designed to support relocation of the program as a complete unit. In some cases, each fixup in the table is itself relative to a base address of zero, so the fixups themselves must be changed as the loader moves through the table.

In some architectures, a fixup that crosses certain boundaries (such as a segment boundary) or that is not aligned on a word boundary is illegal and flagged as an error by the linker.

DOS and 16-bit Windows

Far pointers (32-bit pointers with segment:offset, used to address 20-bit 640 KB memory space available to DOS programs), which point to code or data within a DOS executable (EXE), do not have absolute segments, because the actual address of code or data depends on where the program is loaded in memory and this is not known until the program is loaded.

Instead, segments are relative values in the DOS EXE file. These segments need to be corrected, when the executable has been loaded into memory. The EXE loader uses a relocation table to find the segments that need to be adjusted.

Windows

With 32-bit Windows operating systems, it is not mandatory to provide relocation tables for EXE files, since they are the first image loaded into the virtual address space and thus will be loaded at their preferred base address.

For both DLLs and for EXEs which opt into address space layout randomization (ASLR), an exploit mitigation technique introduced with Windows Vista, relocation tables once again become mandatory because of the possibility that the binary may be dynamically moved before being executed, even though they are still the first thing loaded in the virtual address space.

Windows executables can be marked as ASLR-compatible. The ability exists in Windows 8 and newer to enable ASLR even for applications not marked as compatible. To run successfully in this environment the relocation sections cannot be omitted by the compiler.

Unix-like systems

The Executable and Linkable Format (ELF) executable and shared library format used by most Unix-like systems allows several types of relocation to be defined.

Relocation procedure

The linker reads segment information and relocation tables in the object files and performs relocation by:

  • Merging all segments of common type into a single segment of that type
  • Assigning non-overlapping run time addresses to each segment and each symbol, assigning all code (functions) and data (global variables) unique run time addresses
  • Referring to the relocation table to modify symbol references in data and object code so that they point to the assigned run-time addresses.

Example

The following example uses Donald Knuth's MIX architecture and MIXAL assembly language. The principles are the same for any architecture, though the details will change.

  • (A) Program SUBR is compiled to produce object file (B), shown as both machine code and assembly. The compiler may designate start of the compiled code at an arbitrary location, often location 1 as shown. Location 13 contains the machine code for the jump instruction to statement ST in location 5.
  • (C) If SUBR is later linked with other code it may be stored at a location other than 1. In this example the linker places it at location 120. The address in the jump instruction, which is now at location 133, must be relocated to point to the new location of the code for statement ST, now 125. [1 61 shown in the instruction is the MIX machine code representation of 125].
  • (D) When the program is loaded into memory to run it may be loaded at some location other than the one assigned by the linker. This example shows SUBR now at location 300. The address in the jump instruction, now at 313, needs to be relocated again so that it points to the updated location of ST, 305. [4 49 is the MIX machine representation of 305].

Alternatives

Some architectures avoid relocation entirely by deferring address assignment to run time, as, for example, in stack machines with zero address arithmetic or in some segmented architectures where every compilation unit is loaded into a separate segment.

See also

Further reading

  • Johnson, Glenn (1975-12-21) [1975-11-13]. . Digital Equipment Corporation (DEC). MAINDEC-11-DFKTA-A-D.
  • Formaniak, Peter G.; Leitch, David (July 1977). . BYTE - the small systems journal. Technical Forum. Vol. 2, no. 7. Peterborough, New Hampshire, USA: Byte Publications, Inc. pp. 34, 62–63. ark:/13960/t32245485. (3 pages) (NB. Describes a relocatable hex format by Mostek.)
  • Ogdin, Carol Anne; Colvin, Neil; Pittman, Tom; Tubb, Philip (November 1977). . BYTE - the small systems journal. Technical Forum. Vol. 2, no. 11. Peterborough, New Hampshire, USA: Byte Publications, Inc. pp. 198–205. ark:/13960/t59c88b4h, ark:/13960/t3kw76j24. (8 pages) (NB. Describes a relocatable hex format by TDL.)
  • Kildall, Gary Arlen (February 1978) [1976]. . Dr. Dobb's Journal of Computer Calisthenics & Orthodontia. 3 (2). People's Computer Company: 10–13 (66–69). ISBN 0-8104-5490-4. #22 ark:/13960/t8hf1g21p. . Originally presented at: Kildall, Gary Arlen (1977) [22–24 November 1976]. "A Simple Technique for Static Relocation of Absolute Machine Code". Written at Naval Postgraduate School, Monterey, California, USA. In Titus, Harold A. (ed.). . Asilomar Conference on Signals, Systems & Computers. Asilomar Hotel and Conference Grounds, Pacific Grove, California, USA: Western Periodicals Company. pp. 420–424. ISSN . (609 pages). (This "resize" method, named page boundary relocation, could be applied statically to a CP/M-80 disk image using MOVCPM[pl] in order to maximize the TPA for programs to run. It was also utilized dynamically by the CP/M debugger Dynamic Debugging Tool (DDT) to relocate itself into higher memory. The same approach was independently developed by Bruce H. Van Natta of IMS Associates to produce relocatable PL/M code. As paragraph boundary relocation, another variant of this method was later utilized by dynamically HMA self-relocating TSRs like KEYB, SHARE, and NLSFUNC under DR DOS 6.0 and higher. A much more sophisticated and byte-level granular method based on a somewhat similar approach was independently conceived and implemented by Matthias R. Paul and Axel C. Frinke for their dynamic dead-code elimination to dynamically minimize the runtime footprint of resident drivers and TSRs (like FreeKEYB).)
  • Mossip, Richard H. (September–October 1980). Written at Bloomingdale, New Jersey, USA. (PDF). S-100 Microsystems. Vol. 1, no. 5. Mountainside & Springfield, New Jersey, USA: Libes, Inc. pp. 54–55. ISSN . ark:/13960/s2cfgkmxcwg. ark:/13960/s2qdm1t01nr. (PDF) from the original on 2023-11-27. (2 pages) (NB. Describes page boundary relocation and relocating assemblers.)
  • Huitt, Robert; Eubanks, Gordon; Rolander, Thomas "Tom" Alan; Laws, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison; Berg, Brian; Su, Weilian; Kildall, Scott; Kampe, Bill (2014-04-25). Laws, David (ed.). (PDF) (video transscription). Pacific Grove, California, USA: Computer History Museum. CHM Reference number: X7170.2014. (PDF) from the original on 2014-12-27. […] Laws: […] "dynamic relocation" of the OS. Can you tell us what that is and why it was important? […] Eubanks: […] what Gary did […] was […] mind boggling. […] I remember the day at the school he came bouncing into the lab and he said, I have figured out how to relocate. He took advantage of the fact that the only byte was always going to be the high order byte. And so he created a bitmap. […] it didn't matter how much memory the computer had, the operating system could always be moved into the high memory. Therefore, you could commercialize this […] on machines of different amounts of memory. […] you couldn't be selling a 64K CP/M and a 47K CP/M. It'd just be ridiculous to have a hard compile in the addresses. So Gary figured this out one night, probably in the middle of the night thinking about some coding thing, and this really made CP/M possible to commercialize. I really think that without that relocation it would have been a very tough problem. To get people to buy it, it'd seem complicated to them, and if you added more memory you'd have to go get a different operating system. […] Intel […] had the bytes reversed, right, for the memory addresses. But they were always in the same place, so you could relocate it on a 256 byte boundary, to be precise. You could therefore always relocate it with just a bitmap of where those […] Laws: Certainly the most eloquent explanation I've ever had of dynamic relocation […] (33 pages)
  • Guzis, Charles "Chuck" P. (2015-07-29). . Vintage Computer Forum. Genre: CP/M and MP/M. from the original on 2020-02-01. […] MOVCPM[pl] uses an early type of PRL format. Basically, CP/M is assembled twice; the second time is 100H bytes offset. The two binaries are compared and a bitmap constructed. A set bit implies that the high-order byte of an address is to be adjusted. Low order address bytes are not affected; hence, "Page relocatable file". Each byte in the bitmap corresponds to 8 bytes in the binary data. […] So everything to be moved in MOVCPM is part of the image and its relocation bitmap. […]
  • Guzis, Charles "Chuck" P. (2016-11-08). . Vintage Computer Forum. Genre: CP/M and MP/M. from the original on 2020-02-01. […] I've referenced PRL files and how they originally got their start with MOVCPM[pl], but became an integral part of MP/M and CP/M 3.0. But PRL files use a bit map in which every bit corresponds to a memory location; one bits indicate that a page relocation offset should be added to the corresponding memory location. If you have very few absolute memory references (as opposed to relative ones) you may want to employ a pointer list (2 bytes per reference) rather than a bitmap. This is unlikely in 8080 code which doesn't have relative jumps, but may be a consideration for Z80 code. The trick to quickly find this out is to assemble your program twice; the second time offset by 100H, then compare the two binaries. The advantage of run-time relocation is that you don't have to incur a penalty for code that attempts to get around the relocation issue--no "tricks"; just write straight code. […]
  • Roth, Richard L. (February 1978) [1977]. . Dr. Dobb's Journal of Computer Calisthenics & Orthodontia. 3 (2). Ridgefield, California, USA: People's Computer Company: 14–20 (70–76). ISBN 0-8104-5490-4. #22. from the original on 2019-04-20.
  • Calingaert, Peter (1979) [1978-11-05]. "8.2.2 Relocating Loader". Written at University of North Carolina at Chapel Hill. In Horowitz, Ellis (ed.). . Computer software engineering series (1st printing, 1st ed.). Potomac, Maryland, USA: Computer Science Press, Inc. pp. –241. ISBN 0-914894-23-4. ISSN . LCCN . (2+xiv+270+6 pages)
  • . Microsoft, Product Support Services. Application Note SS0288.{{cite book}}: CS1 maint: deprecated archival service (link)
  • Tanenbaum, Andrew Stuart; Bos, Herbert (2015). Modern Operating Systems (4 ed.). Pearson Education Inc. ISBN 978-0-13359162-0.
  • Elliott, John C. (2012-06-05) [2000-01-02]. . seasip.info. from the original on 2020-01-26. […] The REL format is generated by Microsoft's M80 and Digital Research's RMAC. […]
  • Brothers, Hardin (April 1983). . 80 Micro. The Next Step (39). 1001001, Inc.: , 40, 42, 45. ISSN .
  • Brothers, Hardin (April 1985). . 80 Micro. The Next Step (63). CW Communications/Peterborough, Inc.: , 100, 102–103. ISSN .
  • Ganssle, Jack (February 1992). . Embedded Systems Programming. The Ganssle Group - Perfecting the Art of Building Embedded Systems / TGG. from the original on 2019-07-18.