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.
Prior to the advent of multiprocess systems, and still in many embedded systems, the addresses for objects were
absolute Absolute may refer to:
Companies
* Absolute Entertainment, a video game publisher
* Absolute Radio, (formerly Virgin Radio), independent national radio station in the UK
* Absolute Software Corporation, specializes in security and data risk manage ...
starting at a known location, often zero. Since multiprocessing systems dynamically link and switch between programs it became necessary to be able to relocate objects using
position-independent code
In computing, position-independent code (PIC) or position-independent executable (PIE) is a body of machine code that, being placed somewhere in the primary memory, executes properly regardless of its absolute address. PIC is commonly used for ...
.
A
linker
Linker or linkers may refer to:
Computing
* Linker (computing), a computer program that takes one or more object files generated by a compiler or generated by an assembler and links them with libraries, generating an executable program or shar ...
usually performs relocation in conjunction with symbol resolution, the process of searching files and libraries to replace symbolic references or names of
libraries
A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
with actual usable addresses in
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
before running a program.
Relocation is typically done by the linker at
link time
In computer science, link time refers to the period of time, during the creation of a computer program, in which a linker is being applied to that program. Link time occurs after compile time and before runtime (when a program is executed).
It i ...
, but it can also be done at
load time
In computer systems a loader is the part of an operating system that is responsible for loading programs and libraries. It is one of the essential stages in the process of starting a program, as it places programs into memory and prepares them ...
by a relocating
loader
Loader can refer to:
* Loader (equipment)
* Loader (computing)
** LOADER.EXE, an auto-start program loader optionally used in the startup process of Microsoft Windows ME
* Loader (surname)
* Fast loader
* Speedloader
* Boot loader
** LOADER.COM ...
, or at
run time
Run(s) or RUN may refer to:
Places
* Run (island), one of the Banda Islands in Indonesia
* Run (stream), a stream in the Dutch province of North Brabant
People
* Run (rapper), Joseph Simmons, now known as "Reverend Run", from the hip-hop group ...
by the running program
itself. Some architectures avoid relocation entirely by deferring address assignment to run time; as, for example, in stack machines with
zero address arithmetic
In computer science, computer engineering and programming language implementations, a stack machine is a computer processor or a virtual machine in which the primary interaction is moving short-lived temporary values to and from a push down s ...
or in some segmented architectures where every compilation unit is loaded into a separate segment.
Segmentation
Object file
An object file is a computer file containing object code, that is, machine code output of an assembler or compiler. The object code is usually relocatable, and not usually directly executable. There are various formats for object files, and the ...
s are segmented into various
memory segment
Memory segmentation is an operating system memory management technique of division of a computer's primary memory into segments or sections. In a computer system using segmentation, a reference to a memory location includes a value that identifie ...
types. Example segments include
code segment (.text),
initialized data segment (.data),
uninitialized data segment (.bss), or others.
Relocation table
The relocation table is a list of
pointers created by the translator (a
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
or
assembler
Assembler may refer to:
Arts and media
* Nobukazu Takemura, avant-garde electronic musician, stage name Assembler
* Assemblers, a fictional race in the ''Star Wars'' universe
* Assemblers, an alternative name of the superhero group Champions of A ...
) and stored in the object or executable file. Each entry in the table, or "fixup", is a
pointer to 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. Fixups 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
In computer architecture, 32-bit computing refers to computer systems with a processor, memory, and other major system components that operate on data in 32-bit units. Compared to smaller bit widths, 32-bit computers can perform large calculation ...
pointers with
segment:offset, used to address 20-bit 640
KB memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
space available to
DOS
DOS is shorthand for the MS-DOS and IBM PC DOS family of operating systems.
DOS may also refer to:
Computing
* Data over signalling (DoS), multiplexing data onto a signalling channel
* Denial-of-service attack (DoS), an attack on a communicatio ...
program
Program, programme, programmer, or programming may refer to:
Business and management
* Program management, the process of managing several related projects
* Time management
* Program, a part of planning
Arts and entertainment Audio
* Progra ...
s), which point to code or data within a
DOS executable
The DOS MZ executable format is the executable file format used for .EXE files in DOS.
The file can be identified by the ASCII string "MZ" (hexadecimal: 4D 5A) at the beginning of the file (the " magic number"). "MZ" are the initials of Mark Z ...
(
EXE
Exe or EXE may refer to:
* .exe, a file extension
* exe., abbreviation for executive
Places
* River Exe, in England
* Exe Estuary, in England
* Exe Island, in Exeter, England
Transportation and vehicles
* Exe (locomotive), a British locomotive
...
), do not have absolute segments, because the actual
address
An address is a collection of information, presented in a mostly fixed format, used to give the location of a building, apartment, or other structure or a plot of land, generally using political boundaries and street names as references, along w ...
of code/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
Loader can refer to:
* Loader (equipment)
* Loader (computing)
** LOADER.EXE, an auto-start program loader optionally used in the startup process of Microsoft Windows ME
* Loader (surname)
* Fast loader
* Speedloader
* Boot loader
** LOADER.COM ...
uses a relocation table to find the segments which need to be adjusted.
32-bit 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
Address space layout randomization (ASLR) is a computer security technique involved in preventing exploitation of memory corruption vulnerabilities. In order to prevent an attacker from reliably jumping to, for example, a particular exploited fu ...
(ASLR), an
exploit
Exploit means to take advantage of something (a person, situation, etc.) for one's own end, especially unethically or unjustifiably.
Exploit can mean:
*Exploitation of natural resources
*Exploit (computer security)
* Video game exploit
*Exploitat ...
mitigation technique introduced with
Windows Vista
Windows Vista is a major release of the Windows NT operating system developed by Microsoft. It was the direct successor to Windows XP, which was released five years before, at the time being the longest time span between successive releases of ...
, 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.
64-bit Windows
When running native 64-bit binaries on Windows Vista and above, ASLR is mandatory, and thus relocation sections cannot be omitted by the compiler.
Unix-like systems
The
Executable and Linkable Format
In computing, the Executable and Linkable FormatTool Interface Standard (TIS) Portable Formats SpecificationVersion 1.1'' (October 1993) (ELF, formerly named Extensible Linking Format), is a common standard file format for executable files, obj ...
(ELF) executable format 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 unique run time addresses to each section and each symbol, giving all code (functions) and data (global variables) unique run time addresses
* referring to the relocation table to modify symbols so that they point to the correct run time addresses.
Example
The following example uses
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
's
MIX
Mix, mixes or mixing may refer to:
Persons & places
* Mix (surname)
** Tom Mix (1880-1940), American film star
* nickname of Mix Diskerud (born Mikkel, 1990), Norwegian-American soccer player
* Mix camp, an informal settlement in Namibia
* 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 assembler. The compiler may start 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.
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.
49 is the MIX machine representation of 305
See also
*
Linker (computing)
In computing, a linker or link editor is a computer system program that takes one or more object files (generated by a compiler or an assembler) and combines them into a single executable file, library file, or another "object" file.
A simpler ...
*
Library (computing)
In computer science, a library is a collection of non-volatile memory, non-volatile resources used by computer programs, often for software development. These may include configuration data, documentation, help data, message templates, Code r ...
*
Object file
An object file is a computer file containing object code, that is, machine code output of an assembler or compiler. The object code is usually relocatable, and not usually directly executable. There are various formats for object files, and the ...
*
Prebinding
In computing, prebinding, also called prelinking, is a method for optimizing application load times by resolving library symbols prior to launch.
Background
Most computer programs consist of code that requires external shared libraries to execu ...
*
Static library
In computer science, a static library or statically-linked library is a set of routines, external functions and variables which are resolved in a caller at compile-time and copied into a target application by a compiler, linker, or binder, produci ...
*
Self-relocation
In computer programming, a self-relocating program is a program that relocates its own address-dependent instructions and data when run, and is therefore capable of being loaded into memory at any address. In many cases, self-relocating code is a ...
*
Position-independent code
In computing, position-independent code (PIC) or position-independent executable (PIE) is a body of machine code that, being placed somewhere in the primary memory, executes properly regardless of its absolute address. PIC is commonly used for ...
(PIC)
*
Rebasing
In computing, rebasing is the process of modifying data based on one reference to another. It can be one of the following:
Shared libraries
Rebasing is the process of creating a shared library image in such a way that it is guaranteed to use v ...
*
Garbage collection
Waste collection is a part of the process of waste management. It is the transfer of solid waste from the point of use and disposal to the point of treatment or landfill. Waste collection also includes the curbside collection of recyclable m ...
*
Pointer swizzling
In computer science, pointer swizzling is the conversion of references based on name or position into direct pointer references (memory addresses). It is typically performed during deserialization or loading of a relocatable object from a disk ...
, a lazy form of pointer modification
*
Relocatable Object Module Format
The Relocatable Object Module Format (OMF) is an object file format used primarily for software intended to run on Intel 80x86 microprocessors. Version 4.0 was released by Intel in 1981 under the name ''Object Module Format'', and is perhaps best ...
References
Further reading
*
* (3 pages) (NB. Describes a
relocatable hex format by
Mostek
Mostek was a semiconductor integrated circuit manufacturer, founded in 1969 by L. J. Sevin, Louay E. Sharif, Richard L. Petritz and other ex-employees of Texas Instruments. At its peak in the late 1970s, Mostek held an 85% market share of the d ...
.)
* (8 pages) (NB. Describes a
relocatable hex format by
TDL TDL may refer to:
Businesses and organizations
* Technical Design Labs, a former microcomputer- and software company
* Texas Digital Library, a consortium of institutions
* TDL Group, former company name of Tim Hortons
Places
* Tokyo Disneylan ...
.)
*
https://web.archive.org/web/20170819173516/http://archive.computerhistory.org/resources/access/text/2016/12/102762506-05-01-acc.pd
Originally presented at: (609 pages). (This "resize" method, named ''page boundary relocation'', could be applied statically to a
CP/M-80 disk image using in order to maximize the
TPA for programs to run. It was also utilized dynamically by the CP/M debugger
Dynamic Debugging Tool
Dynamic Debugging Technique (DDT) is a series of debugger programs originally developed for Digital Equipment Corporation (DEC) hardware, initially known as DEC Debugging Tape because it was distributed on paper tape. The name is a pun on the in ...
(DDT) to
relocate itself into higher memory. The same approach was independently developed by
Bruce H. Van Natta of
IMS Associates
IMS Associates, Inc., or IMSAI, was a microcomputer company, responsible for one of the earliest successes in personal computing, the IMSAI 8080. The company was founded in 1973 by William Millard and was based in San Leandro, California. Their ...
to produce relocatable
PL/M
The PL/M programming language
(an acronym of ''Programming Language for Microcomputers'')
is a high-level language conceived and developed by
Gary Kildall in 1973 for Hank Smith at Intel for its microprocessors.
Overview
The language incorpor ...
code. As ''paragraph boundary relocation'',
another variant of this method was later utilized by dynamically
HMA self-relocating
TSRs like
KEYB
KEYB (107.9 FM, "108 Key FM") is a radio station licensed to Altus, Oklahoma, United States. The station is currently owned by Monte Spearman and Gentry Todd Spearman, through licensee High Plains Radio Network, LLC.
KEYB has television adverti ...
,
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
In compiler theory, dead-code elimination (also known as DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove code which does not affect the program results. Removing such code has several benefits: ...
to dynamically minimize the runtime footprint of resident drivers and TSRs (like FreeKEYB).)
*
*
https://www.youtube.com/watch?v=HO6IPpL0y8g] (33 pages)
*
*
*
*
*
* (2+xiv+270+6 pages)
*
*
*
*
*
*
https://archive.org/download/80-microcomputing-magazine-1983-04/80Microcomputing_0483_text.pdf]
*
https://archive.org/download/80-microcomputing-magazine-1985-04/80Microcomputing_0485_text.pdf]
*
https://archive.org/download/the-computer-journal-32/tcj_32_May-June_1988_text.pdf]
*
https://archive.org/download/the-computer-journal-33/tcj_33_July-August_1988_text.pdf]
*
https://archive.org/download/the-computer-journal-34/tcj_34_September-October_1988_text.pd
*
https://archive.org/download/the-computer-journal-54/tcj_54_January-February_1992_text.pd
*
https://archive.org/download/the-computer-journal-55/tcj_55_March-June_1992_text.pdf]
*
{{Executables
Computer libraries
Assignment operations