Author: Doug, 10+ years embedded development veteran, focusing on: C/C++, embedded, Linux.
Paging in memory management is very important on x86 systems, and it is featured in various books on the Linux operating system.
If you’ve read any books about the Linux kernel, you’ll be familiar with, and afraid of, the following graph:
This is the multi – level page table query of the page processing unit in Linux system.
The yellow background part: the upper page directory index and the middle page directory index, is the Linux system’s own extension, does not exist in the original x86 processor, which is also the reason for the related part of Linux code is more complex.
In the last article, we mainly illustrated the “reverse construction” and “forward lookup” processes of page directories and page tables in x86. The article is linked here: Linux Ab Initio 15: [page table and table] – theory + example + graphic most complete, most down-to-earth explanation, but there is one link that has been deliberately omitted.
How do operating systems address and manipulate page directories and page tables themselves as they construct them?
This is where the complexity of memory management comes in. It’s like a doctor performing an operation on a patient, but the patient is “the doctor”.
In this article, we continue to look at how kernel code typically performs these “manipulations” by using images and examples.
When you look at the Linux kernel code, you won’t get confused.
Problem description
In the last article, we gave an example like this:
Assume that the actual physical memory is 1 GB;
User program files on hard disk are 20 MB in length;
When the operating system loads the user program into memory, the storage starts at the virtual memory address 0x4000_0000.
After the operating system reading program ends, the page directory and page table are constructed for all the addresses.
As shown below:
For each valid entry in the page directory and page table, the address stored is the first 20 bits of an actual physical page (because a physical page is fixed at 4KB in length, it is aligned when allocated, and the last 12 bits are all zeros).
And page directories and page tables themselves take up space on a physical page, so they have their own physical address.
When the page directory and page table are properly constructed and the processor is faced with a linear address, such as 0x4100_1800, the page processing unit converts the linear address to a physical address in a hierarchical look-up mode:
Split linear address: 0x4100_1800 = 0100_0001_0000_0000___0001_1000_0000_0000;
The physical address of the page table is 0x0800_4000 (the value of the entry is 0x08004, plus 12 low zeros).
Find index 1 in the page table 0x0800_4000 based on the middle 10 bits of the linear address, so that the physical address of the normal physical page is 0x0210_1000 (the value of the entry is 0x02101, and 12 low zeros are added).
Based on the last 12 bits of the linear address, determine that the offset within the normal page is 2048. Add the offset to the start address of the normal page to get the final physical address 0x0210_1800.
For a detailed discussion of the process, please refer to the previous article: Linux From Scratch 15: [page table and table] – theory + example + graphic most complete, most down-to-earth explanation.
So, here’s the question:
With the page-processing unit on, the processor faces a linear address, so how does the operating system address each entry in the page directory as it constructs it?
When the operating system wants to enter the physical address 0x0800_0000 of the first page table into the 256th entry in the page directory, the CPU needs to find this entry, which must have a physical address.
However, we cannot tell the physical address of this entry directly to the CPU, because the CPU only receives linear addresses, which are automatically processed by the paging unit to get the corresponding physical address.
So, what is the value of this linear address?
Let’s go ahead and do it by example, so it’s easy to understand.
Assuming that the physical page start address of the page directory is 0x0100_0000, the physical address of the 256th entry is 0x0100_0400.
Some people might say, “Why not just tell the processor the physical address 0x0100_0400?”
This is wrong!
The processor receives linear addresses, not physical addresses
Because the paging unit is now enabled, 0x0100_0400 is the last physical address we want, and the processor only accepts a linear address, even though we know it’s a physical address, but the processor doesn’t know it.
When we give the processor an address, the processor performs a sequence of [segment translation] and then [page translation] to get what it considers a physical address.
Because we use a “flat” segment structure, we ignore segment processing here and go straight to page processing.
So, we should use some method to construct a linear address addr and let this address pass through the page processing unit to get the physical address 0x0100_0400:
It’s a bit recursive, and a bit like a doctor performing a surgical procedure on himself!
Now, do you see what you’re dealing with?
The goal is to somehow construct a linear address ADDR that is converted by the page processing unit to the physical address 0x0100_0400.
Perform operations on the page directory
If an operation is performed on an address in an ordinary physical page, three look-up operations are required:
The physical address found from an entry in the page table is the last normal physical page to operate on.
Now we have a problem: we need the page directory as the final action object.
That is, the physical address of the “normal page” found in the page table should be equal to the physical address of the page directory!
As a software developer, recursion is all there is to it.
Let’s construct a linear address ADDR that points to the physical address of the page directory after three table look-up operations.
Table lookup: Construct the first 10 bits of a linear address to determine the physical address of the page table
Level 1 table lookup: The object to look up is the page directory.
The first 10 bits of the linear address ADDR determine the index in the page directory.
Obviously, the address registered in the entry corresponding to the index must point to the page directory itself.
A common solution is to take the last entry in the page directory and make the address recorded in this entry point to the page directory itself, as shown in the following figure:
In other words, the last entry of the page directory is filled with the physical address of the page directory itself, and the first 10 bits of the linear address ADDR are 1023.
It is easy to find that the first 10 bits of addr should be: 0x3FF(binary: 1111_1111_11).
Since the address stored in this entry is the starting address of the page directory itself (0x0100_0000, the last 12 zeros are automatically filled in), this is equivalent to: the page directory is about to be used as a “page table” when we enter the second level of the search.
As shown below:
The “page table” of the red dotted line is actually the page table itself, just a shadow.
Secondary lookup: Construct the middle 10 bits of the linear address to determine the physical address of the “normal page”
Level-2 table lookup: The search object is the page table, that is, the “page table” obtained by level-1 table lookup.
Although the result of a first-level table lookup is the page directory itself, the processor does not care about this and uses the table as a page table.
Now consider the middle 10 bits of linear address ADDR, which determines the index number in the page table.
Obviously, the address of the record in the entry corresponding to the index number must continue to point to the page directory itself.
Use the last entry in the “page table” (which is actually the page table), which is the index = 1023 entry.
The physical address stored in this entry will be the physical address of the “normal page” eventually retrieved from the table lookup.
Since this entry is prefilled with 0x01000, after 12 zeros at the end, 0x0100_0000 still points to the page directory itself. Perfect!
The result is the middle 10 bits: 0x3FF(binary: 11_1111_1111).
As shown below:
The “physical page” on the far right, with the red dotted line, is the result of a secondary search, which is still essentially the page catalog itself, but is about to be used as a normal physical page.
Tertiary lookup: Construct the last 12 bits of a linear address to determine the in-page offset of a “normal page”
We have now constructed the first 20 bits of the linear address ADDR (which is our ultimate goal) and successfully located the page directory itself through the first two levels of table lookup!
Just one last step away!
As we know, the last 12 bits represent the in-page offset in the translation from the linear address to the physical address, and are taken directly from the linear address.
The last 12-bit offset of a linear address is the same as the last 12-bit offset of a physical address.
So, let’s work backwards:
We finally want to operate on the 256th entry in the page directory, whose physical address is 0x0100_0400 and whose offset from the page directory’s starting address is 0x400(0x0100_0400 minus 0x0100_0000).
Therefore, the last 12 bits in the linear address ADDR should also have a value of 0x400.
Three address segments combined
Aggregate the addresses obtained in the three steps above:
0xFFFF_F400 is the desired linear address!
In other words, we simply tell the processor the linear address 0xFFFF_F400, and it will go through the page processing unit to find the 256th entry in the physical page of the page directory, which is the physical address 0x0100_0400.
For example, mov [0xFFFF_4000], XXXX
This is the strategy that the operating system takes when operating on the page directory itself.
It may be slightly different for each operating system, but the idea is the same.
For example, in the first figure at the beginning of this article, Linux uses a 4-level table for lookup, and the middle two tables can be omitted.
The code in the Linux kernel code is a little more complicated, but the strategy is the same.
Perform operations on the page table
Now that you understand how the operating system operates on page directories, manipulating page tables is not a big deal.
Like this one:
Target: Put the normal physical page address 0x0200_0000 on the right into the first entry of the page table 0x0800_0000 (only the first 20 bits are needed). What linear address should be passed to the processor?
The idea is exactly the same.
Level 1 look-up table
Follow the normal paging lookup process to find the page table we want to operate on from an entry in the page directory.
This entry in the page directory is at index value 256, so the first 10 bits of the linear address can be constructed as: 0100_0000_00(0x100).
So, the physical address of the page table is 0x0800_0000 after a table lookup.
The secondary look-up table
Using the last entry of the page table (index = 1023), prefill an address (0x08000) that points to the page table’s own starting physical address.
Thus, the middle 10 bits of the linear address can be constructed as: 11_1111_1111(0x3FF).
Since the address stored in this entry is 0x0800_0000, it points to the page table itself, but it is immediately used as a normal physical page.
Level 3 look-up table
At this point, the last normal physical page has been found (which is actually a page table and is used as a normal physical page).
The last 12 bits of the linear address can be taken directly from the last 12 bits of the target physical address that you want to operate on.
Our goal is to operate on the 0th entry in the page table, which has a physical address of 0x0800_0000 and a last 12-bit offset of 0000_0000_0000.
The correct linear address can be obtained by combining the above three address segments:
The approach discussed here is not the only way to deal with page directories and page tables.
As the processing logic becomes more complex, you may need to do some special preprocessing for more entries in the page directory or page table.
If you want to challenge yourself, take a look at the documentation or code in the Linux kernel!
This is the end of the page table and table series.
If there is any mistake or misdirection in the article, I am looking forward to discussing and learning with you!
It was not easy to write this article, which made me deeply appreciate the sentence:
Writing is all about articulating reticulated thoughts – through tree-like structures – in linear language.
If you think it’s good, please give it a thumbs up, encourage it, and forward it to your technical friends. Thank you very much!
Recommended reading
[1] Series of articles on Linux From Scratch
[2] C language pointer – from the underlying principles to fancy skills, with graphics and code to help you explain thoroughly
[3] The underlying debugging principle of GDB is so simple
[4] Is inline assembly terrible? Finish this article and end it!
Other series: featured articles, Application design, Internet of Things, C language.