Position-independent code
Encyclopedia
In computing
, position-independent code (PIC) or position-independent executable (PIE) is machine instruction code that executes properly regardless of where in memory
it resides. 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
, 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 copied to any memory location and executed without modification. This differs from relocatable code
, which requires special processing by a link editor or program loader
to make it suitable for execution 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.
To make things more flexible, position-independent code was invented. Position-independent code could run from any address at which the operator chose to load it.
The invention of dynamic address translation (the function provided by an MMU
) almost obsoleted position-independent code, because every process could have its own separate 32-bit address space. Because position-independent code is less efficient than position-dependent code, this was a better solution to the problem.
The next problem to be attacked was the memory waste that happens when the same code is loaded multiple times to be used by multiple simultaneous jobs. 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.
But more often, the programs are different and merely share a lot of common code. For example, the payroll program and the accounts receivable program probably both contain an identical sort subroutine. So designers invented shared modules (a shared library is a form of shared module). While the main payroll and accounts receivable programs get loaded into separate memory, the shared module gets loaded once and simply mapped into the two address spaces.
Position-independent code has been used not only to coordinate the work of user-level applications, but within operating systems as well. The earliest paging systems did not use virtual memory address spaces; instead, the operating system would explicitly load individual modules of itself as needed, overwriting less needed ones (the memory available for the operating system was much smaller than the operating system). A module had to be capable of running in whatever memory was free at the time it was needed, so individual operating system modules were made of position-independent code.
The invention of virtual memory obsoleted that method, because the operating system could have a virtual address space so big that every module of the operating system could have its own permanent virtual address.
s, 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 variable
s. 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
, probably at least some other RISC processors, ESA/390
), which can then be stored in a predefined standard register. Some processor architectures, like the Motorola 68000
, Motorola 6809
, 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.
DLL
s 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" (not to be confused with memory-mapped I/O
) 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.
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.
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 attack
s.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, position-independent code (PIC) or position-independent executable (PIE) is machine instruction code that executes properly regardless of where in memory
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
it resides. 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
Memory management unit
A memory management unit , sometimes called paged memory management unit , is a computer hardware component responsible for handling accesses to memory requested by the CPU...
, so that the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
could keep applications away from each other even within the single address space
Address space
In computing, an address space defines a range of discrete addresses, each of which may correspond to a network host, peripheral device, disk sector, a memory cell or other logical or physical entity.- Overview :...
of an MMU-less system.
Position-independent code can be copied to any memory location and executed without modification. This differs from relocatable code
Relocation (computer science)
"Relocation is the process of assigning load addresses to various parts of [a] program and adjusting the code and data in the program to reflect the assigned addresses."...
, which requires special processing by a link editor or program loader
Loader (computing)
In computing, a loader is the part of an operating system that is responsible for loading programs. 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...
to make it suitable for execution at a given location.
Position independent code must adhere to a specific set of semantics in the source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
and compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
support is required. Instructions that refer to specific memory addresses, such as absolute branches, must be replaced with equivalent program counter
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...
relative instructions. The extra indirection may cause PIC to be less efficient, although modern processors make the difference practically negligible.
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, an operator had to carefully schedule the jobs so that no two simultaneous jobs would run programs that required the same load addresses. For example, if both the payroll program and the accounts receivable program were built to run at address 32K, the operator could not run both at the same time. Sometimes, an operator would keep multiple versions of a program around, each built for a different load address, to expand his options.To make things more flexible, position-independent code was invented. Position-independent code could run from any address at which the operator chose to load it.
The invention of dynamic address translation (the function provided by an MMU
Memory management unit
A memory management unit , sometimes called paged memory management unit , is a computer hardware component responsible for handling accesses to memory requested by the CPU...
) almost obsoleted position-independent code, because every process could have its own separate 32-bit address space. Because position-independent code is less efficient than position-dependent code, this was a better solution to the problem.
The next problem to be attacked was the memory waste that happens when the same code is loaded multiple times to be used by multiple simultaneous jobs. 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.
But more often, the programs are different and merely share a lot of common code. For example, the payroll program and the accounts receivable program probably both contain an identical sort subroutine. So designers invented shared modules (a shared library is a form of shared module). While the main payroll and accounts receivable programs get loaded into separate memory, the shared module gets loaded once and simply mapped into the two address spaces.
Position-independent code has been used not only to coordinate the work of user-level applications, but within operating systems as well. The earliest paging systems did not use virtual memory address spaces; instead, the operating system would explicitly load individual modules of itself as needed, overwriting less needed ones (the memory available for the operating system was much smaller than the operating system). A module had to be capable of running in whatever memory was free at the time it was needed, so individual operating system modules were made of position-independent code.
The invention of virtual memory obsoleted that method, because the operating system could have a virtual address space so big that every module of the operating system could have its own permanent virtual address.
Technical details
Procedure calls inside a shared library are typically made through small procedure linkage table stubMethod stub
A method stub or simply stub in software development is a piece of code used to stand in for some other programming functionality. A stub may simulate the behavior of existing code or be a temporary substitute for yet-to-be-developed code...
s, 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 variable
Global variable
In computer programming, a global variable is a variable that is accessible in every scope . Interaction mechanisms with global variables are called global environment mechanisms...
s. 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
PowerPC
PowerPC is a RISC architecture created by the 1991 Apple–IBM–Motorola alliance, known as AIM...
, SPARC
SPARC
SPARC is a RISC instruction set architecture developed by Sun Microsystems and introduced in mid-1987....
, probably at least some other RISC processors, ESA/390
ESA/390
ESA/390 was introduced in September 1990 and is IBM's last 31-bit-address/32-bit-data mainframe computing design, copied by Amdahl, Hitachi, and Fujitsu among other competitors...
), which can then be stored in a predefined standard register. Some processor architectures, like the Motorola 68000
Motorola 68000
The Motorola 68000 is a 16/32-bit CISC microprocessor core designed and marketed by Freescale Semiconductor...
, Motorola 6809
Motorola 6809
The Motorola 6809 is an 8-bit microprocessor CPU from Motorola, designed by Terry Ritter and Joel Boney and introduced 1978...
, Knuth's
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....
MMIX
MMIX
MMIX is a 64-bit RISC instruction set architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites...
, ARM
ARM architecture
ARM is a 32-bit reduced instruction set computer instruction set architecture developed by ARM Holdings. It was named the Advanced RISC Machine, and before that, the Acorn RISC Machine. The ARM architecture is the most widely used 32-bit ISA in numbers produced...
and x86-64
X86-64
x86-64 is an extension of the x86 instruction set. It supports vastly larger virtual and physical address spaces than are possible on x86, thereby allowing programmers to conveniently work with much larger data sets. x86-64 also provides 64-bit general purpose registers and numerous other...
allow referencing data by offset from the program counter
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...
. This is specifically targeted at making position-independent code smaller, less register demanding and hence more efficient.
Windows DLLs
Microsoft WindowsMicrosoft Windows
Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
DLL
Dynamic-link library
Dynamic-link library , or DLL, is Microsoft's implementation of the shared library concept in the Microsoft Windows and OS/2 operating systems...
s are not shared libraries in the Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
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" (not to be confused with memory-mapped I/O
Memory-mapped I/O
Memory-mapped I/O and port I/O are two complementary methods of performing input/output between the CPU and peripheral devices in a computer...
) 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.
Other platforms such as Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
and Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
now support forms of prebinding as well. For Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
the system is called prebinding
Prebinding
Prebinding is a method for reducing the time it takes to launch executables in the Mach-O file format. For example, this is what Mac OS X is doing when in the "Optimizing" stage of installing system software or certain applications....
. Under Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, the system used is implemented via a program called prelink
Prelink
prelink is a free program written by Jakub Jelínek of Red Hat for POSIX-compliant operating systems, principally Linux . It is intended to speed up a system by reducing the time a program needs to begin...
. This is vastly different from memory mapping.
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 LinuxLinux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
distributions to allow PaX
PaX
PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. The least-privilege approach allows computer programs to do only what they have to do in order to be able to execute properly, and nothing more. PaX was first released in 2000.PaX flags data memory as...
or Exec Shield
Exec Shield
Exec Shield is a project started at Red Hat, Inc in late 2002 with the aim of reducing the risk of worm or other automated remote attacks on Linux systems. The first result of the project was a security patch for the Linux kernel that emulates an NX bit on x86 CPUs that lack a native NX...
to use address space layout randomization
Address space layout randomization
Address space layout randomization is a computer security method which involves randomly arranging the positions of key data areas, usually including the base of the executable and position of libraries, heap, and stack, in a process's address space.- Benefits :Address space randomization hinders...
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 attack
Return-to-libc attack
A return-to-libc attack is a computer security attack usually starting with a buffer overflow in which the return address on the stack is replaced by the address of another instruction and an additional portion of the stack is overwritten to provide arguments to this function...
s.