Position-independent code

Last updated

In computing, position-independent code [1] (PIC [1] ) or position-independent executable (PIE) [2] 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 shared libraries, so that the same library code can be loaded at a location in each program's address space where it does not overlap with other memory in use by, for example, other shared libraries. PIC was also used on older computer systems that lacked an MMU, [3] so that the operating system could keep applications away from each other even within the single address space of an MMU-less system.

Contents

Position-independent code can be executed at any memory address without modification. This differs from absolute code, [1] which must be loaded at a specific location to function correctly, [1] and load-time locatable (LTL) code, [1] in which a linker or program loader modifies a program before execution, so it can be run only from a particular memory location. [1] Generating position-independent code is often the default behavior for compilers, but they may place restrictions on the use of some language features, such as disallowing use of absolute addresses (position-independent code has to use relative addressing). Instructions that refer directly to specific memory addresses sometimes execute faster, and replacing them with equivalent relative-addressing instructions may result in slightly slower execution, although modern processors make the difference practically negligible. [4]

History

In early computers such as the IBM 701 [5] (29 April 1952) or the UNIVAC I (31 March 1951) code was not position-independent: each program was built to load into and run from a particular address. Those early computers did not have an operating system and were not multitasking-capable. Programs were loaded into main storage (or even stored on magnetic drum for execution directly from there) and run one at a time. In such an operational context, position-independent code was not necessary.

The IBM System/360 (7 April 1964) was designed with truncated addressing similar to that of the UNIVAC III, [6] with code position independence in mind. In truncated addressing, memory addresses are calculated from a base register and an offset. At the beginning of a program, the programmer must establish addressability by loading a base register; normally, the programmer also informs the assembler with a USING pseudo-op. The programmer can load the base register from a register known to contain the entry point address, typically R15, or can use the BALR (Branch And Link, Register form) instruction (with a R2 Value of 0) to store the next sequential instruction's address into the base register, which was then coded explicitly or implicitly in each instruction that referred to a storage location within the program. Multiple base registers could be used, for code or for data. Such instructions require less memory because they do not have to hold a full 24, 31, 32, or 64 bit address (4 or 8 bytes), but instead a base register number (encoded in 4 bits) and a 12–bit address offset (encoded in 12 bits), requiring only two bytes.

This programming technique is standard on IBM S/360 type systems. It has been in use through to today's IBM System/z. When coding in assembly language, the programmer has to establish addressability for the program as described above and also use other base registers for dynamically allocated storage. Compilers automatically take care of this kind of addressing.

IBM's early operating system DOS/360 (1966) was not using virtual storage (since the early models of System S/360 did not support it), but it did have the ability to place programs to an arbitrary (or automatically chosen) storage location during loading via the PHASE name,* JCL (Job Control Language) statement.

So, on S/360 systems without virtual storage, a program could be loaded at any storage location, but this required a contiguous memory area large enough to hold that program. Sometimes memory fragmentation would occur from loading and unloading differently sized modules. Virtual storage - by design - does not have that limitation.

While DOS/360 and OS/360 did not support PIC, transient SVC routines in OS/360 could not contain relocatable address constants and could run in any of the transient areas without relocation.

Virtual storage was first introduced on IBM System/360 model 67 in (1965) to support IBM's first multi-tasking operating and time-sharing operating system TSS/360. Later versions of DOS/360 (DOS/VS etc.) and later IBM operating systems all utilized virtual storage. Truncated addressing remained as part of the base architecture, and still advantageous when multiple modules must be loaded into the same virtual address space.

By way of comparison, on early segmented systems such as Burroughs MCP on the Burroughs B5000 (1961) and Multics (1964), paging systems such as IBM TSS/360 (1967) [lower-alpha 1] or base and bounds [lower-alpha 2] systems such as GECOS on the GE 625 and EXEC on the UNIVAC 1107, code was also inherently position-independent, since addresses in a program were relative to the current segment rather than absolute.

The invention of dynamic address translation (the function provided by an MMU) originally reduced the need for position-independent code because every process could have its own independent address space (range of addresses). However, multiple simultaneous jobs using the same code created a waste of physical memory. If two jobs run entirely identical programs, dynamic address translation provides a solution by allowing the system simply to map two different jobs' address 32K to the same bytes of real memory, containing the single copy of the program.

Different programs may share common code. For example, the payroll program and the accounts receivable program may both contain an identical sort subroutine. A shared module (a shared library is a form of shared module) gets loaded once and mapped into the two address spaces.

Technical details

Procedure calls inside a shared library are typically made through small procedure linkage table stubs, which then call the definitive function. This notably allows a shared library to inherit certain function calls from previously loaded libraries rather than using its own versions.

Data references from position-independent code are usually made indirectly, through Global Offset Tables (GOTs), which store the addresses of all accessed global variables. There is one GOT per compilation unit or object module, and it is located at a fixed offset from the code (although this offset is not known until the library is linked). When a linker links modules to create a shared library, it merges the GOTs and sets the final offsets in code. It is not necessary to adjust the offsets when loading the shared library later.

Position-independent functions accessing global data start by determining the absolute address of the GOT given their own current program counter value. This often takes the form of a fake function call in order to obtain the return value on stack (x86), in a specific standard register (SPARC, MIPS), or a special register (POWER/PowerPC/Power ISA), which can then be moved to a predefined standard register, or to obtain it into that standard register (PA-RISC, Alpha, ESA/390 and z/Architecture). Some processor architectures, such as the Motorola 68000, Motorola 6809, WDC 65C816, Knuth's MMIX, ARM and x86-64 allow referencing data by offset from the program counter. This is specifically targeted at making position-independent code smaller, less register demanding and hence more efficient.

Windows DLLs

Dynamic-link libraries (DLLs) in Microsoft Windows use variant E8 of the CALL instruction (Call near, relative, displacement relative to next instruction). These instructions do not need modification when the DLL is loaded.

Some global variables (e.g. arrays of string literals, virtual function tables) are expected to contain an address of an object in data section respectively in code section of the dynamic library; therefore, the stored address in the global variable must be updated to reflect the address where the DLL was loaded to. The dynamic loader calculates the address referred to by a global variable and stores the value in such global variable; this triggers copy-on-write of a memory page containing such global variable. Pages with code and pages with global variables that do not contain pointers to code or global data remain shared between processes. This operation must be done in any OS that can load a dynamic library at arbitrary address.

In Windows Vista and later versions of Windows, the relocation of DLLs and executables is done by the kernel memory manager, which shares the relocated binaries across multiple processes. Images are always relocated from their preferred base addresses, achieving address space layout randomization (ASLR). [7]

Versions of Windows prior to Vista require that system DLLs be prelinked at non-conflicting fixed addresses at the link time in order to avoid runtime relocation of images. Runtime relocation in these older versions of Windows is performed by the DLL loader within the context of each process, and the resulting relocated portions of each image can no longer be shared between processes.

The handling of DLLs in Windows differs from the earlier OS/2 procedure it derives from. OS/2 presents a third alternative and attempts to load DLLs that are not position-independent into a dedicated "shared arena" in memory, and maps them once they are loaded. All users of the DLL are able to use the same in-memory copy.

Multics

In Multics each procedure conceptually [lower-alpha 3] has a code segment and a linkage segment. The code segment contains only code and the linkage section serves as a template for a new linkage segment. Pointer register 4 (PR4) points to the linkage segment of the procedure. A call to a procedure saves PR4 in the stack before loading it with a pointer to the callee's linkage segment. The procedure call uses an indirect pointer pair [8] with a flag to cause a trap on the first call so that the dynamic linkage mechanism can add the new procedure and its linkage segment to the Known Segment Table (KST), construct a new linkage segment, put their segment numbers in the caller's linkage section and reset the flag in the indirect pointer pair.

TSS

In IBM S/360 Time Sharing System (TSS/360 and TSS/370) each procedure may have a read-only public CSECT and a writable private Prototype Section (PSECT). A caller loads a V-constant for the routine into General Register 15 (GR15) and copies an R-constant for the routine's PSECT into the 19th word of the save area pointed to be GR13. [9]

The Dynamic Loader [10] does not load program pages or resolve address constants until the first page fault.

Position-independent executables

Position-independent executables (PIE) are executable binaries made entirely from position-independent code. While some systems only run PIC executables, there are other reasons they are used. PIE binaries are used in some security-focused Linux distributions to allow PaX or Exec Shield to use address space layout randomization (ASLR) to prevent attackers from knowing where existing executable code is during a security attack using exploits that rely on knowing the offset of the executable code in the binary, such as return-to-libc attacks. (The official Linux kernel since 2.6.12 of 2005 has a weaker ASLR that also works with PIE. It is weak in that randomness is applied to whole ELF file units.) [11]

Apple's macOS and iOS fully support PIE executables as of versions 10.7 and 4.3, respectively; a warning is issued when non-PIE iOS executables are submitted for approval to Apple's App Store but there's no hard requirement yet [ when? ] and non-PIE applications are not rejected. [12] [13]

OpenBSD has PIE enabled by default on most architectures since OpenBSD 5.3, released on 1 May 2013. [14] Support for PIE in statically linked binaries, such as the executables in /bin and /sbin directories, was added near the end of 2014. [15] openSUSE added PIE as a default in 2015-02. Beginning with Fedora  23, Fedora maintainers decided to build packages with PIE enabled as the default. [16] Ubuntu 17.10 has PIE enabled by default across all architectures. [17] Gentoo's new profiles now support PIE by default. [18] Around July 2017, Debian enabled PIE by default. [19]

Android enabled support for PIEs in Jelly Bean [20] and removed non-PIE linker support in Lollipop. [21]

See also

Notes

  1. ↑ While TSS/360 supported shared PIC, that was not true of all paging systems
  2. ↑ But a separate copy of the code was loaded for each job.
  3. ↑ There are some technical deviations for performance reasons that are beyond the scope of this article.

Related Research Articles

<span class="mw-page-title-main">Linker (computing)</span> Computer program which combines multiple object files into a single file

In computing, a linker or link editor is a computer system program that takes one or more object files and combines them into a single executable file, library file, or another "object" file.

The Portable Executable (PE) format is a file format for executables, object code, DLLs and others used in 32-bit and 64-bit versions of Windows operating systems. The PE format is a data structure that encapsulates the information necessary for the Windows OS loader to manage the wrapped executable code. This includes dynamic library references for linking, API export and import tables, resource management data and thread-local storage (TLS) data. On NT operating systems, the PE format is used for EXE, DLL, SYS, MUI and other file types. The Unified Extensible Firmware Interface (UEFI) specification states that PE is the standard executable format in EFI environments.

<span class="mw-page-title-main">Library (computing)</span> Collection of non-volatile resources used by computer programs

In computer science, a library is a collection of non-volatile resources used by computer programs, often for software development. These may include configuration data, documentation, help data, message templates, pre-written code and subroutines, classes, values or type specifications. In IBM's OS/360 and its successors they are referred to as partitioned data sets.

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 same machine code can be packaged in different object file formats. An object file may also work like a shared library.

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 for execution. Loading a program involves either memory-mapping or copying the contents of the executable file containing the program instructions into memory, and then carrying out other required preparatory tasks to prepare the executable for running. Once loading is complete, the operating system starts the program by passing control to the loaded program code.

Addressing modes are an aspect of the instruction set architecture in most central processing unit (CPU) designs. The various addressing modes that are defined in a given instruction set architecture define how the machine language instructions in that architecture identify the operand(s) of each instruction. An addressing mode specifies how to calculate the effective memory address of an operand by using information held in registers and/or constants contained within a machine instruction or elsewhere.

Memory segmentation is an operating system memory management technique of dividing 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 identifies a segment and an offset within that segment. Segments or sections are also used in object files of compiled programs when they are linked together into a program image and when the image is loaded into memory.

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 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. 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.

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, producing an object file and a stand-alone executable. This executable and the process of compiling it are both known as a static build of the program. Historically, libraries could only be static. Static libraries are either merged with other static libraries and object files during building/linking to form a single executable or loaded at run-time into the address space of their corresponding executable at a static memory offset determined at compile-time/link-time.

Dynamic-link library (DLL) is Microsoft's implementation of the shared library concept in the Microsoft Windows and OS/2 operating systems. These libraries usually have the file extension DLL, OCX, or DRV . The file formats for DLLs are the same as for Windows EXE files – that is, Portable Executable (PE) for 32-bit and 64-bit Windows, and New Executable (NE) for 16-bit Windows. As with EXEs, DLLs can contain code, data, and resources, in any combination.

In computing, a dynamic linker is the part of an operating system that loads and links the shared libraries needed by an executable when it is executed, by copying the content of libraries from persistent storage to RAM, filling jump tables and relocating pointers. The specific operating system and executable format determine how the dynamic linker functions and how it is implemented.

In computer programming, DLL injection is a technique used for running code within the address space of another process by forcing it to load a dynamic-link library. DLL injection is often used by external programs to influence the behavior of another program in a way its authors did not anticipate or intend. For example, the injected code could hook system function calls, or read the contents of password textboxes, which cannot be done the usual way. A program used to inject arbitrary code into arbitrary processes is called a DLL injector.

<span class="mw-page-title-main">Overlay (programming)</span>

In a general computing sense, overlaying means "the process of transferring a block of program code or other data into main memory, replacing what is already stored". Overlaying is a programming method that allows programs to be larger than the computer's main memory. An embedded system would normally use overlays because of the limitation of physical memory, which is internal memory for a system-on-chip, and the lack of virtual memory facilities.

<span class="mw-page-title-main">TSS (operating system)</span> 1960s era timesharing operating system for IBM mainframes

The IBM Time Sharing System TSS/360 is a discontinued early time-sharing operating system designed exclusively for a special model of the System/360 line of mainframes, the Model 67. Made available on a trial basis to a limited set of customers in 1967, it was never officially released as a supported product by IBM. TSS pioneered a number of novel features, some of which later appeared in more popular systems such as MVS. TSS was migrated to System/370 and 303x systems, but despite its many advances and novel capabilities, TSS failed to meet expectations and was eventually canceled. TSS/370 was used as the basis for a port of UNIX to the IBM mainframe. TSS/360 also inspired the development of the TSS/8 operating system.

Dynamic loading is a mechanism by which a computer program can, at run time, load a library into memory, retrieve the addresses of functions and variables contained in the library, execute those functions or access those variables, and unload the library from memory. It is one of the 3 mechanisms by which a computer program can use some other software; the other two are static linking and dynamic linking. Unlike static linking and dynamic linking, dynamic loading allows a computer program to start up in the absence of these libraries, to discover available libraries, and to potentially gain additional functionality.

In IBM mainframe operating systems, basic partitioned access method (BPAM) is an access method for libraries, called partitioned datasets (PDSes) in IBM terminology. BPAM is used in OS/360, OS/VS2, MVS, z/OS, and others.

<span class="mw-page-title-main">OS/360 and successors</span> Operating system for IBM S/360 and later mainframes

OS/360, officially known as IBM System/360 Operating System, is a discontinued batch processing operating system developed by IBM for their then-new System/360 mainframe computer, announced in 1964; it was influenced by the earlier IBSYS/IBJOB and Input/Output Control System (IOCS) packages for the IBM 7090/7094 and even more so by the PR155 Operating System for the IBM 1410/7010 processors. It was one of the earliest operating systems to require the computer hardware to include at least one direct access storage device.

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 also a form of self-modifying code.

In IBM System/360 through present day z/Architecture, an address constant or "adcon" is an assembly language data type which contains the address of a location in computer memory. An address constant can be one, two, three or four bytes long, although an adcon of less than four bytes is conventionally used to hold an expression for a small integer such as a length, a relative address, or an index value, and does not represent an address at all. Address constants are defined using an assembler language "DC" statement.

The Global Offset Table, or GOT, is a section of a computer program's memory used to enable computer program code compiled as an ELF file to run correctly, independent of the memory address where the program's code or data is loaded at runtime.

References

  1. 1 2 3 4 5 6 "Types of Object Code". iRMX 86 Application Loader Reference Manual (PDF). Intel. pp. 1-2, 1-3. Retrieved 2017-08-21. […] Absolute code, and an absolute object module, is code that has been processed by LOC86 to run only at a specific location in memory. The Loader loads an absolute object module only into the specific location the module must occupy. Position-independent code (commonly referred to as PIC) differs from absolute code in that PIC can be loaded into any memory location. The advantage of PIC over absolute code is that PIC does not require you to reserve a specific block of memory. When the Loader loads PIC, it obtains iRMX 86 memory segments from the pool of the calling task's job and loads the PIC into the segments. A restriction concerning PIC is that, as in the PL/M-86 COMPACT model of segmentation […], it can have only one code segment and one data segment, rather than letting the base addresses of these segments, and therefore the segments themselves, vary dynamically. This means that PIC programs are necessarily less than 64K bytes in length. PIC code can be produced by means of the BIND control of LINK86. Load-time locatable code (commonly referred to as LTL code) is the third form of object code. LTL code is similar to PIC in that LTL code can be loaded anywhere in memory. However, when loading LTL code, the Loader changes the base portion of pointers so that the pointers are independent of the initial contents of the registers in the microprocessor. Because of this fixup (adjustment of base addresses), LTL code can be used by tasks having more than one code segment or more than one data segment. This means that LTL programs may be more than 64K bytes in length. FORTRAN 86 and Pascal 86 automatically produce LTL code, even for short programs. LTL code can be produced by means of the BIND control of LINK86. […]
  2. ↑ "Position Independent Executables (PIE)".
  3. ↑ Levine, John R. (2000) [October 1999]. "Chapter 8: Loading and overlays". Linkers and Loaders. The Morgan Kaufmann Series in Software Engineering and Programming (1 ed.). San Francisco, USA: Morgan Kaufmann. pp. 170–171. ISBN   1-55860-496-0. OCLC   42413382. ISBN   978-1-55860-496-4. Archived from the original on 2012-12-05. Retrieved 2020-01-12. Code: Errata:
  4. ↑ Gabert, Alexander (January 2004). "Position Independent Code internals". Hardened Gentoo . Retrieved 2009-12-03. […] direct non-PIC-aware addressing is always cheaper (read: faster) than PIC addressing. […]
  5. ↑ "701 Announced", IBM, 1952-04-29
  6. ↑ Reference Manual UNIVAC III Data Processing System (PDF). Sperry Rand Corporation. 1962. UT-2488.
  7. ↑ "Advances in Memory Management for Windows". View.officeapps.live.com. Retrieved 2017-06-23.
  8. ↑ "Section 6 Virtual Address Formation", DPS/LEVEL 68 & DPS 8M MULTICS PROCESSOR MANUAL (PDF) (Rev. 1 ed.), Honeywell Information Systems Inc., 1982, pp. 6–21, AL39, retrieved 2023-03-25
  9. ↑ "Section 3: TSS for the: Svslcm Programmer". IBM Time Sharing System Concepts and Facilities (PDF) (Seventh ed.). April 1978. p. 61. GC28-2003-6.
  10. ↑ IBM System/360 Time Sharing System Dynamic Loader (PDF) (Fourth ed.). September 1971. GY28-2031-3.
  11. ↑ Lettieri, G. "Address Space Layout Randomization" (PDF).
  12. ↑ "iphone - Non-PIE Binary - The executable 'project name' is not a Position Independent Executable. - Stack Overflow". stackoverflow.com.
  13. ↑ "iOS Developer Library". apple.com.
  14. ↑ "OpenBSD 5.3 Release". 2013-05-01. Retrieved 2020-05-09.
  15. ↑ "Heads Up: Snapshot Upgrades for Static PIE". 2014-12-24. Retrieved 2014-12-24.
  16. ↑ "Changes/Harden All Packages - FedoraProject". fedoraproject.org.
  17. ↑ "Ubuntu Foundations Team - Weekly Newsletter, 2017-06-15". 2017-06-15. Retrieved 2017-06-17.
  18. ↑ "New 17.0 profiles in the Gentoo repository". 2017-11-30. Retrieved 2017-12-10.
  19. ↑ Liang, Mudong (2017-08-08). "When did Debian decide to enabled PIE by default?". debian.org. Retrieved 2021-07-06.
  20. ↑ "Security Enhancements in Android 1.5 through 4.1  -  Android Open Source Project". Android Open Source Project.
  21. ↑ "Security Enhancements in Android 5.0  -  Android Open Source Project". Android Open Source Project.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.