October 30, 2014 at 09:29Memory addresses: physical, virtual, logical, linear, efficient, guest
- Tutorial
I occasionally have to explain to various people some aspects of the Intel® IA-32 architecture, including the intricacy of the in-memory addressing system, which seems to have implemented almost all the ideas that were once invented. I decided to draw up a detailed answer in this article. I hope that it will be useful to someone else.
When executing machine instructions, data is read and written that can be in several places: in the registers of the processor itself, in the form of constants encoded in the instructions, as well as in RAM. If the data is in memory, then their position is determined by some number - the address. For a number of reasons, which, I hope, will become clear in the process of reading this article, the source address encoded in the instructions goes through several conversions.
The figure shows the segmentation and page translation of the address, as they looked 27 years ago. Illustration from the 1986 Intel 80386 Programmers's Reference Manual . It's funny that in the description of the drawing there are already two typos: "803 0 6 Addressing M a chanism". Nowadays, the address undergoes more complex transformations, and illustrations are no longer done in pseudo-graphics.
Let's start a little from the end - with the goal of the whole chain of transformations.
The end result of all translations of the other types of addresses listed later in this article is a physical address . It ends the work inside the central processor for address translation.
An effective address is the beginning of the journey. It is specified in the arguments of the individual machine instruction, and is calculated from the values of the registers, offsets, and scaling factors specified in it explicitly or implicitly.
For example, for an instruction (assembler in AT&T notation), the effective address of the destination operand will be calculated by the formula:
Without knowing the number and parameters of the segment in which the effective address is indicated, the latter is useless. The segment itself is selected by another number called the selector . A pair of numbers written as
Here, usually for those who are faced with these concepts for the first time, their heads begin to spin. To simplify (or complicate) the situation somewhat helps the fact that almost always the choice of the selector (and the segment associated with it) is made based on the "meaning" of access. By default, unless otherwise specified in the encoding of the machine instruction, logical addresses with the CS selector are used to obtain the code addresses, for the data from the DS, for the stack from the SS.
The effective address is the offset from the beginning of the segment - its base. If we add the base and the effective address, we get a number called a linear address : Boolean → linear conversion can not always be successful, since when it is executed, several conditions on the properties of a segment recorded in the fields of its descriptor are checked. For example, checking out of the boundaries of the segment and access rights.
Segmentation was fashionable at some stage in the development of computer technology. At present, it has been almost everywhere replaced by other mechanisms, and is used only for specific tasks. So, in IA-32e mode (64-bit), only two segments can have a nonzero base. For the other four in this mode, the linear address is always == effective.
In the literature and in the documentation of other architectures, there is another term - a virtual address . It is not used in Intel documentation for IA-32, however it is found, for example, in the Intel® Itanium description, in which segmentation is not used. We can safely assume that for IA-32 virtual == linear.
In the Soviet literature on computer engineering, this type of address was also called mathematical .
The following address translation after segmentation: linear → physical - has many variations in its algorithm, depending on what mode (32-bit, PAE or 64-bit) the processor is in.
However, the general idea is always the same: the linear address is divided into several parts, each of which serves as an index in one of the system tables stored in memory. The entries in the tables are the addresses of the beginning of the table of the next level or, for the last level, the required information about the physical address of the page in memory and its properties. The least significant bits are not converted, but are used for addressing within the found page. For example, for PAE mode with a page size of 4 KB, the conversion looks like this:
In different processor modes, the number and capacity of these tables varies. The conversion may fail if the next table does not contain valid data, or the access rights stored in the last of them prohibit access to the page; for example, when writing to regions marked as read-only, or when trying to read kernel memory from an unprivileged process.
Before the introduction of hardware virtualization capabilities in Intel processors, page conversion was the last in the chain. When several virtual machines are running on the same system, the physical addresses received in each of them have to be broadcast one more time. This can be done programmatically, or hardware if the processor supports EPT (Extended Page Table) functionality. The address, formerly called physical, was renamed the guest physical in order to distinguish it from the real physical. They are linked using the EPT transform. The algorithm of the latter is similar to the previously described page conversion: a set of related tables with a common root, the last level of which determines whether a physical page exists for the specified guest physical.
I tried to collect all the address translations into one illustration. In it, conversions are indicated by arrows, address types are circled.
As mentioned above, each of the transformations can return an error for addresses that do not have a representation in the following form of the chain. The elimination of such problems is the task of operating systems and monitors of virtual machines that implement the abstraction of virtual memory.
The evolution of what is in nature, what is in technology is a strange thing. It gives rise to unexpected structures that are inexplicable in terms of rational design. Her creations are full of atavisms, the rules of their behavior sometimes almost entirely consist of exceptions. In order to understand the operation of such a system, it is often necessary to scroll through its evolution from the very beginning, and under the piling of all layers to find the truth in the form of the principle: "do not throw anything away." I am inclined to consider IA-32 architecture as a wonderful example of evolutionary development.
Thanks for attention!
When executing machine instructions, data is read and written that can be in several places: in the registers of the processor itself, in the form of constants encoded in the instructions, as well as in RAM. If the data is in memory, then their position is determined by some number - the address. For a number of reasons, which, I hope, will become clear in the process of reading this article, the source address encoded in the instructions goes through several conversions.
The figure shows the segmentation and page translation of the address, as they looked 27 years ago. Illustration from the 1986 Intel 80386 Programmers's Reference Manual . It's funny that in the description of the drawing there are already two typos: "803 0 6 Addressing M a chanism". Nowadays, the address undergoes more complex transformations, and illustrations are no longer done in pseudo-graphics.
Let's start a little from the end - with the goal of the whole chain of transformations.
Physical adress
The end result of all translations of the other types of addresses listed later in this article is a physical address . It ends the work inside the central processor for address translation.
Final result?!
In fact, it’s easy to understand that this is not the end. In the platform, which must process the data request from the processor, there can be several DRAM chips having their own blocking structure, as well as various peripheral devices mapped to the total space of physical memory. The further transaction path with some physical address will depend on the configuration of several decoders located on its path inside the platform devices.
Effective Address
An effective address is the beginning of the journey. It is specified in the arguments of the individual machine instruction, and is calculated from the values of the registers, offsets, and scaling factors specified in it explicitly or implicitly.
For example, for an instruction (assembler in AT&T notation), the effective address of the destination operand will be calculated by the formula:
addl %eax, 0x11(%ebp, %edx, 8)
eff_addr = EBP + EDX * 8 + 0x11
Logical address
Without knowing the number and parameters of the segment in which the effective address is indicated, the latter is useless. The segment itself is selected by another number called the selector . A pair of numbers written as
selector:offsetreceived the name logical address . Since active selectors are stored in a group of special registers, most often instead of the first number in the pair, the name of the register is written, for example, ds: 0x11223344.Here, usually for those who are faced with these concepts for the first time, their heads begin to spin. To simplify (or complicate) the situation somewhat helps the fact that almost always the choice of the selector (and the segment associated with it) is made based on the "meaning" of access. By default, unless otherwise specified in the encoding of the machine instruction, logical addresses with the CS selector are used to obtain the code addresses, for the data from the DS, for the stack from the SS.
Line address
The effective address is the offset from the beginning of the segment - its base. If we add the base and the effective address, we get a number called a linear address : Boolean → linear conversion can not always be successful, since when it is executed, several conditions on the properties of a segment recorded in the fields of its descriptor are checked. For example, checking out of the boundaries of the segment and access rights.
lin_addr = segment.base + eff_addr
Real mode
The above is true when segmentation is enabled. In 16-bit real mode, the meaning of the selectors is different, they only store the base, and the conversion does not perform segment checks. In fact, the designations CS, DS, FS, GS, ES, SS have completely different meanings in these two modes, which adds to the confusion.
Segmentation was fashionable at some stage in the development of computer technology. At present, it has been almost everywhere replaced by other mechanisms, and is used only for specific tasks. So, in IA-32e mode (64-bit), only two segments can have a nonzero base. For the other four in this mode, the linear address is always == effective.
What is a virtual address?
In the literature and in the documentation of other architectures, there is another term - a virtual address . It is not used in Intel documentation for IA-32, however it is found, for example, in the Intel® Itanium description, in which segmentation is not used. We can safely assume that for IA-32 virtual == linear.
In the Soviet literature on computer engineering, this type of address was also called mathematical .
Page conversion
The following address translation after segmentation: linear → physical - has many variations in its algorithm, depending on what mode (32-bit, PAE or 64-bit) the processor is in.
What affects paging
It is noteworthy how many different bits from different processor system registers affect the page conversion process at present. I looked at the latest September edition of Intel SDM [1], and here is the complete list: CR0.WP, CR0.PG, CR4.PSE, CR4.PAE, CR4.PGE, CR4.PCIDE, CR4.SMEP, CR4.SMAP, IA32_EFER. LME, IA32_EFER.NX, EFLAGS.AC.
However, the general idea is always the same: the linear address is divided into several parts, each of which serves as an index in one of the system tables stored in memory. The entries in the tables are the addresses of the beginning of the table of the next level or, for the last level, the required information about the physical address of the page in memory and its properties. The least significant bits are not converted, but are used for addressing within the found page. For example, for PAE mode with a page size of 4 KB, the conversion looks like this:
In different processor modes, the number and capacity of these tables varies. The conversion may fail if the next table does not contain valid data, or the access rights stored in the last of them prohibit access to the page; for example, when writing to regions marked as read-only, or when trying to read kernel memory from an unprivileged process.
Guest physical
Before the introduction of hardware virtualization capabilities in Intel processors, page conversion was the last in the chain. When several virtual machines are running on the same system, the physical addresses received in each of them have to be broadcast one more time. This can be done programmatically, or hardware if the processor supports EPT (Extended Page Table) functionality. The address, formerly called physical, was renamed the guest physical in order to distinguish it from the real physical. They are linked using the EPT transform. The algorithm of the latter is similar to the previously described page conversion: a set of related tables with a common root, the last level of which determines whether a physical page exists for the specified guest physical.
Full picture
I tried to collect all the address translations into one illustration. In it, conversions are indicated by arrows, address types are circled.
As mentioned above, each of the transformations can return an error for addresses that do not have a representation in the following form of the chain. The elimination of such problems is the task of operating systems and monitors of virtual machines that implement the abstraction of virtual memory.
Conclusion
The evolution of what is in nature, what is in technology is a strange thing. It gives rise to unexpected structures that are inexplicable in terms of rational design. Her creations are full of atavisms, the rules of their behavior sometimes almost entirely consist of exceptions. In order to understand the operation of such a system, it is often necessary to scroll through its evolution from the very beginning, and under the piling of all layers to find the truth in the form of the principle: "do not throw anything away." I am inclined to consider IA-32 architecture as a wonderful example of evolutionary development.
PS Everything is like everyone else
Shortly after completing this article, I came across a presentation about the IBM System z architecture, which is notable for its long and interesting history of supporting virtualization. This document found an enumeration of all types of memory addresses used in System z:
As you can see, there are also five of them.
- Virtual: Translated by dynamic address translation (DAT) to real addresses
- Real: Translated to absolute addresses using the prefix register
- Absolute: After applying the prefix register
- Logical: The address seen by the program (this can either be a virtual or a real address)
- Physical: translated to absolute addresses by the Config Array
As you can see, there are also five of them.
Thanks for attention!
Literature
- Intel Corporation. Intel® 64 and IA-32 Architectures Software Developer's Manual. Volumes 1-3, 2014. www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html