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 shared libraries, so that the same library code can be loaded in a location in each program address space where it will not overlap any other uses of memory (for example, other shared libraries). PIC was also used on older computer systems lacking an MMU,^[1] so that the operating system could keep applications away from each other even within the single address space of an MMU-less system.

Position-independent code can be executed at any memory address without modification. This differs from relocatable code, where a link editor or program loader modifies a program so that it can be run only at a given location. Position independent code must adhere to a specific set of semantics in the source code and compiler support is required. Instructions that refer to specific memory addresses, such as absolute branches, must be replaced with equivalent program counter relative instructions. The extra indirection may cause PIC to be less efficient, although modern processors make the difference practically negligible.^[2]

History

In early computers, code was position-dependent: each program was built to be loaded into, and run from, a particular address. In order to run multiple jobs using separate programs at the same time jobs had to be scheduled such that no two concurrent jobs would run programs that required the same load addresses. For example, both a payroll program and an accounts receivable program built to run at address 32K could not both be run at the same time. Sometimes multiple versions of a program were maintained, each built for a different load address. This was the situation on IBM DOS/360 (1966) except for a special class of self-relocating programs.

An improvement on this situation was the ability to relocate executable programs when they were loaded into memory. Only one copy of the program was required, but once loaded the program could not be moved. IBM OS/360 programs (1966) fit this model.

In segmented systems such as Multics (1964), code is inherently position-independent, since addresses in a program are relative to the current segment rather than absolute.

Position-independent code was developed to eliminate these restrictions for non-segmented systems. A position-independent program could be loaded at any address in memory.

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, use the same code by multiple simultaneous jobs created a waste of virtual 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) or in a special register (PowerPC, SPARC, MIPS, probably at least some other RISC processors, ESA/390), which can then be stored in a predefined standard register. 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

Microsoft Windows DLLs are not shared libraries in the Unix sense and do not use position independent code. This means they cannot have their routines overridden by previously loaded DLLs and require small tricks for sharing selected global data. Code has to be relocated after it has been loaded from disk, making it potentially non-shareable between processes; sharing mostly occurs on disk.

To alleviate this limitation, almost all Windows system DLLs are pre-mapped at different fixed addresses in such a way that there is no conflict. It is not necessary to relocate the libraries before using them and memory can be shared. Even pre-mapped DLLs still contain information which allows them to be loaded at arbitrary addresses if necessary.

A sharing technique Windows calls "memory mapping" is sometimes able to allow multiple processes to share an instance of a DLL loaded into memory. However, the reality is that Windows is not always able to share one instance of a DLL loaded by multiple processes.^[3] Windows requires each compiled program to know where in its address space each DLL will be accessed — there is no support for position independence.

A DLL specifies its desired base address when it is created, called its RVA (Visual C++ defaults to an offset of 0x10000000). However, if multiple DLLs have the same desired base address, a program cannot relocate them all to that base offset and must specify new offsets when linking. When the Windows loader loads an executable into memory for execution, it checks to see if each DLL has already been loaded with the offset used when the executable was created (not the DLL). If the DLL is not already loaded with that offset, it is relocated to the base requested by the executable. Note that this will provide sharing across multiple processes of the same executable (e.g. if started in different accounts via Fast User Switching), but not necessarily across different programs that link to the same DLL.^[4]

Other platforms such as Mac OS X and Linux now support forms of prebinding as well. For Mac OS X the system is called prebinding. Under Linux, the system used is implemented via a program called prelink. This is vastly different from memory mapping.

In the Itanium version of Microsoft Windows, the system has been altered to use position-independent code,^[5] however X64 versions still use standard relocation techniques alongside position independent methods and thus cannot be considered true "position independent" libraries.^[6]

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 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. Windows NT uses address space layout randomization since Windows Vista.

Apple's Mac OS X and iOS fully support PIE executables as of versions 10.7 and 4.3, respectively; a warning issued when non-PIE iOS executable submitted for approval to Apple's App Store but there's no hard requirement yet and non-PIE applications are not rejected.^[7][8]

OpenBSD has PIE enabled by default on most architectures since OpenBSD 5.3, released on 1 May 2013.^[9]

See also

• Dynamic linker
• Code segment
• Core War: Key features
• COM file (although not a true PIE)

References

Further reading

• John R. Levine (October 1999). "Chapter 8: Loading and overlays". Linkers and Loaders. Morgan-Kauffman. ISBN 1-55860-496-0. 

External links

• Introduction to Position Independent Code
• Position Independent Code internals
• Programming in Assembly Language with PIC