Relocation (computing)
   HOME

TheInfoList




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
absoluteAbsolute 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 managem ...
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 Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and softw ...
. A
linker Linker or linkers may refer to: Computing * Linker (computing) In computing, a linker or link editor is a computer System software, system program that takes one or more object files (generated by a compiler or an assembler (computing), asse ...
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 easily accessible for use and not just for display purposes. It is responsible for housing updated information in order to meet the user's needs on a daily basis. A library provi ...
with actual usable addresses in
memory Memory is the faculty of the brain A brain is an organ Organ may refer to: Biology * Organ (anatomy) An organ is a group of Tissue (biology), tissues with similar functions. Plant life and animal life rely on many organs that co-exis ...
before running a program. Relocation is typically done by the linker at
link time In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algori ...
, but it can also be done at
load time In computer systems A computer is a machine A machine is a man-made device that uses power to apply forces and control movement to perform an action. Machines can be driven by animals and people A people is a plurality of perso ...
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 (ak ...
, or at run time by the running program itself. Some architectures avoid relocation entirely; for example 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 In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and ...
s are segmented into various
memory segment Memory segmentation is an operating system memory management (operating systems), memory management technique of division of a computer's primary memory into segments or sections. In a Computer architecture, computer system using segmentation, a r ...
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 Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...

compiler
or
assembler Assembler may refer to: Arts and media * Nobukazu Takemura Nobukazu Takemura (竹村延和 ''Takemura Nobukazu'') is a Japanese musician and artist. Born in Hirakata, Osaka in August 1968, he became interested in music at a young age by listenin ...

assembler
) 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 32-bit microcomputer A microcomputer is a small, relatively inexpensive computer with a microprocessor as its central processing unit (CPU). It includes a microprocessor, Computer memory, memory and minimal input/output (I/O) circuitry mount ...
pointers with
segment Segment or segmentation may refer to: Biology *Segmentation (biology), the division of body plans into a series of repetitive segments **Segmentation in the human nervous system *Internodal segment, the portion of a nerve fiber between two Nodes of ...
:offset, used to address 20-bit 640 KB
memory Memory is the faculty of the brain A brain is an organ Organ may refer to: Biology * Organ (anatomy) An organ is a group of Tissue (biology), tissues with similar functions. Plant life and animal life rely on many organs that co-exis ...
space available to
DOS DOS (, ) is a platform-independent acronym for disk operating system which later became a common shorthand for disk-based operating systems on IBM PC compatible IBM PC compatible computers are similar to the original IBM Personal Computer, IB ...

DOS
programs), 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 (programming), magic number"). "MZ" a ...
(
EXE .exe is a common filename extension A filename extension, file extension or file type is an identifier specified as a suffix to the name A name is a term used for identification by an external observer. They can identify a class or category ...
), 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 Borders are geographic Geogr ...
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 (ak ...
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 ...
(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 The exploitation of natural resources is the use of natural ...
mitigation technique introduced with
Windows Vista Windows Vista is a major release of the Windows NT Windows NT is a Proprietary software, proprietary Graphical user interface, graphical operating system produced by Microsoft, the first version of which was released on July 27, 1993. It i ...
, 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 Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and soft ...
(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 A computer scientist is a person who has acquired the knowledge of computer science Computer science deals with the theoretical foundations of information, ...
's
MIX MIX is a hypothetical computer used in Donald Knuth's monograph, '' The Art of Computer Programming'' (''TAOCP''). MIX's model number is 1009, which was derived by combining the model numbers and names of several contemporaneous, commercial machi ...
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 Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and sof ...
*
Library (computing) In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of ...
*
Object file An object file is a computer file containing object code In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and ...
* Prebinding *
Static library In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of comp ...
*
Self-relocation In computer programming, a self-relocating program is a program that relocation (computer science), relocates its own address-dependent instructions and data when run, and is therefore capable of being loaded into memory at any address. In many case ...
*
Position-independent code In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and softw ...
(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 vir ...
*
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 list of waste treatment technologies, treatment or landfill. Waste collection also includes the ...
*
Pointer swizzling In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , ...
, a lazy form of pointer modification *
Relocatable Object Module Format The Relocatable Object Module Format (OMF) is an object file An object file is a computer file containing object code In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It inclu ...


References


Further reading

* * (3 pages) (NB. Describes a relocatable hex format by
Mostek Mostek was an integrated circuit manufacturer, founded in 1969 by L. J. Sevin, Louay E. Sharif, Richard L. Petritz and other ex-employees of Texas Instruments. Initially their products were manufactured in Worcester, Massachusetts, however by 1 ...
.) * (8 pages) (NB. Describes a relocatable hex format by TDL.) *

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 (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 The PL/M programming language (an acronym of ''Programming Language for Microcomputers'') is a high-level language A language is a structured system of communication Communication (from Latin Latin (, or , ) is a classical langua ...
code. As ''paragraph boundary relocation'', another variant of this method was later utilized by dynamically HMA self-relocating
TSR TSR may refer to: Science and technology * Terminate and stay resident program, a type of MS-DOS computer program * Thermochemical sulfate reduction, reducing sulfate to sulfide * Tip-speed ratio, of a wind turbines * Temporary speed restriction#TS ...
s like
KEYB KEYB (107.9 FM, "108 Key FM") is a radio station Radio broadcasting is transmission of audio signal, audio (sound), sometimes with related metadata, by radio waves intended to reach a wide audience. In terrestrial radio broadcasting the ...
,
SHARE Share may refer to: * Share, to make joint use of a resource (such as food, money, or space); see Sharing * Share (finance), a stock or other financial security (such as a mutual fund) * Share, Kwara, a town and LGA in Kwara State, Nigeria Share ma ...
, 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