Really having trouble understanding paging

[PatSanf]

I've been trying to implement paging for a while, and I'm having a really difficult time of it. I understand the general, overall, theory but there's something I'm missing that's keeping it from "clicking." I'm hoping you guys can help fill in the pieces of my understanding. What I'm basically needing is a step-by-step guide that's light on theory, but not actually code. I understand that most people seem to like doing things as a higher half kernel for various reasons, but I'm doing mine in the lower half. This is mainly because I want to understand paging before I start trying to remap things to funny locations. In the first 1M of memory I have the stuff that was put there by the boot loader, and Grub, which I'm not touching. I've just decided to leave that alone, and I'm putting my kernel right after that. My kernel ends wherever it happens to end, and I'm using values provided by the linker to determine where my kernel starts and ends.

You can see my code here. I've been conversing with people on other forums, and am aware that I've probably screwed up the physical memory manager. It's providing me with page aligned physical memory addresses that are available after the kernel. My allocate_block() function just gives me a page aligned address in physical memory after the kernel off a stack. Before I attempt to enable paging my memory looks like

0 - 1M: Bootloader and Grub stuff
1M - end as defined by the linker: My kernel
end - ?: A stack holding every 4096th address of the available memory. The ? is determined by the memory map provided by Grub when the system boots. Basically, it's the amount of upper memory in MB divided by 4. You can see exactly what I'm talking about here. I'm using Qemu to test things, and giving it 128 MB of memory, so my stack's holding 32768 addresses.

I'm wanting to make sure I have a good road map to follow before I attempt to redo my paging implementation for the umpteenth time. This is what I'm needing to do, as I understand it:

1. Get a physical memory address where my page directory will reside (this is the first page aligned address of physical memory after the ? from above)
2. Set all of the memory for that 4KB section to 0 to make sure there's no garbage in there.
3. Get a physical memory address where my first page table will reside. (the second page aligned address of physical memory after the ?)
4. Set all of the memory for that 4KB section to 0.
5. Start treating the 4KB sections of memory as arrays.
6. For each item on the page directory array set the attributes to 0 | 2.
7. For the 0th item on the page directory set the attributes to the address of the page table | 3.
8. Identity map all of the physical memory from 0 on up to whatever's available into the page table (which will give me 4GB of virtual memory addresses, buy only 128MB of them will actually be "real"). (How will I know which pages are present?)
9. Set the interrupt handler for my page fault handler.
10. Put the physical address of the page directory on the cr3 register.
11. Enable paging by doing | 0x80000000 on cr0.

From there I'll need to write the page fault handler, and functions to allocate, free, and map new pages as needed. How's all of that sound to you guys?

[eryjus]

I understand your pain. I have had trouble as well and I hope I can help explain it better.

First, I recommend getting a copy of the Intel Software Developer's Manuals. It's a quick Google search. Figure 4.4 in volume 3A is very helpful (assuming 32-bit, non-PAE). Second, what helped me understand everything better is to hand-code the paging tables -- at least initially; once I understood them I was able to build them at runtime. Since you are using GRUB, be sure to parse the MMAP tables for the memory you can use for your physical memory manager.

Keep in mind that there is a hierarchy of tables: a Page Directory (PD) and a Page Table (PT). Each of these tables will be a 4K page-aligned frame. A PD will point to an array of 1024 PTs and each PT will have 1024 Pages. CR3 is loaded with the Physical Address of the PD.

A PD Entry (PDE) will need to be Present (bit 0) if it points to a PT and the address of the PDE will be the physical page-aligned address of the PT.

The steps you outline look otherwise reasonable.

[PatSanf]

I think what I'm suffering from is information overload. I've read a whole bunch of stuff about paging, but it's all either broad concepts or code that was made for somebody else's OS. I might try the hand coding exercise you're recommending.

I'm thinking that would look like this:

CR3 = The physical address of the current page directory.

PDE(0) => Physical address of PTE 0
PDE(1) => Physical address of PTE 1
...
PDE(1023) => Physical address of PTE 1023

PTE(0) => Physical address 0
PTE(1) => Physical address 1024
PTE(2) => Physical address 2048
...
PTE(1023) => Physical address 1,047,552

Where the numbers between the ( and ) are array indices, and the numbers to the right of => are physical memory addresses. Is that correct? Or should those physical addresses be the individual bits of the logical address as outlined here? Meaning that PDE(0) would be bits 31-22 which translate from binary into the index in the page directory?

I looked at the manual you recommended. It looks like that information is the same stuff that's on the wiki's paging article.

[Rusky]

Your first diagram is the closest. When the CPU goes to access a particular memory location when paging is enabled, it splits up the address into several pieces- 10 bits, 10 bits, 12 bits. So if you want to access address 0xffeeddcc, it gets split up like this:

Bits 31-22 (0x3ff) are the index into the page directory, whose physical address is stored in CR3. At that index in the page directory is a page directory entry, with the physical address of a page table, and some flags stored in the lower bits (which are available because the page table is page-aligned).

Bits 21-12 (0x2ed) are the index into the page table, whose physical address was obtained from the page directory. At that index in the page table is a page table entry, with the physical address of a page (and some flags).

Bits 11-0 (0xdcc) are the index into the actual page, whose physical address was obtained from the page table.

[PatSanf]

Alright, I understand the concept of splitting the address into pieces, but is that a virtual address, and where is the translation into the proper physical address done? I was thinking that once paging is enabled that any reference to a memory address would be a virtual address, and the system would automagically translate that into the proper physical address with the MMU. Is this where functions translating virtual addresses into physical addresses come in to play? Also, once the virtual address is translated into a physical address how does the system make use of it without throwing another page fault?

[JAAman]

(almost) all addresses are virtual once paging is enabled.

in order to translate the linear address into physical address (linear address is the address after segmentation has been applied)
here I am specifically looking at 4k pages, using standard (not PAE, not PSE-36, not IA-32e) mode, this information can be found in Intel 3A:3.7 and especially the figure connected to section 3.7.1 (note while figure, table, and page numbers are sequential, and therefore change on different revisions of the manuals, the section numbers do not, if you don't have them there is a link to the latest copy of the Intel manuals in my signature)

linear address:
31...0

this is then broken into 3 parts:
31...22 | 21...12 | 11...0

the CR3 register points to the Page Directory in memory, the first (high order) 10 bits of the address are an index within that directory like this:
(index * sizeof(directoryEntry) + CR3) is the physical address of the entry, which contains the physical address of the page table (call this tableBase)

the second section (bits 21...12 -- another 10 bits) contain the index within that page table like this:
(index * sizeof(tableEntry) + tableBase) is the physical address of the entry, which contains the physical address of the page in memory (call this pageBase)

the final section (bits 11...0 -- 12 bits, enough to address 4k memory) is actually already the physical address, and is added to the pageBase address found in the previous step

now you have the full physical address, where the first 20 bits are found in the page table, and the last 12 bits are used directly from the linear address



note all this is done in hardware, none of this needs to be done in software, so don't need to do this yourself (unless for some reason you need to discover where a page is mapped... for instance to copy memory (or mapping) into another process

once it has this address, then it can use it to access the memory for whatever it needed it for -- the translation is done automatically (by the hardware) each time the address is needed (although the contents of the tables are cached in the CPU for better performance), the addresses in the program/memory are never changed, all addresses that the CPU receives are always virtual addresses, which are first translated into linear addresses by the segmentation system, and then the linear addresses are translated into physical addresses by the paging system (note that there are several different paging systems on x86, but all operate on the same basic principles)

the #PF exception is called when the translation fails for some reason: either the page (or page table) does not have the permissions needed for the use of the final address, or the present bit is clear (meaning the entry doesn't exist, this can be either the page table which doesn't exist if it is in the page directory, or the physical page doesn't exist if it is in the page table) -- it can also be triggered if a reserved bit is incorrectly set (usually this means the entry is malformed, and therefore not correct and cannot be relied on) this should never be the case for a working system, but might be on an incomplete system (where you have accidentally mistyped something or gotten the bit order mixed up)

[Combuster]

The physical address is what the processor gives to other hardware. The virtual address is taken from a pointer currently being used by the code that's running. Code is only ever able to use virtual addresses directly. Anything that is not considered a virtual address has to be handed to the MMU first as a "rule on converting a virtual address to a physical address". For instance

(almost) all addresses are virtual once paging is enabled.

is wrong because paging doesn't change which addresses are which category. Disabling paging only sets a rule that addresses are not to be changed any further in the process of converting from virtual to physical.

There are two steps involved: segmentation and paging. Segmentation goes first and adds a fixed number to the virtual address to get a new address, or refuses to do so if the privileges are wrong. To change it, you set a segment register or a descriptor table register to a new value. The intermediate result before paging is called the "linear address" and anything in this step except the input works on linear addresses to prevent chicken-and-egg problems. Because Grub set this to zero for you in advance so that adding zero to the input doesn't change that input when turned into output, people conveniently forget that this step does actually keep happening and subsequently forget the proper terminology as a result.

Paging uses a b-tree to map linear addresses to the last step in the processor: physical addresses. Again to avoid chicken-and-egg problems, everything paging related is stored as physical addresses: CR3, but also the content of the page directory and page tables. That way there's always a predictable and short path to calculate the result.

[Rusky]

Alright, I understand the concept of splitting the address into pieces, but is that a virtual address, and where is the translation into the proper physical address done? I was thinking that once paging is enabled that any reference to a memory address would be a virtual address, and the system would automagically translate that into the proper physical address with the MMU. Is this where functions translating virtual addresses into physical addresses come in to play? Also, once the virtual address is translated into a physical address how does the system make use of it without throwing another page fault?

Yes, the program uses a virtual address, which is handed to the MMU, which then splits it up and walks the page tables to find a physical address. As Combuster said, there's no need to worry about page faults at this point, because it's already past the MMU (which would have triggered any potential page faults) and gets handed to the memory controller (or whatever is using it) as a physical address.

[PatSanf]

Alright, I've started coding, using my list from above as my road map. I'd like to ask for some feedback before I shoot myself in the foot.

Here are some links to the code I'm working on, and a screen shot.
These are the assembly functions I'm going to use to interact with CR0, CR2, and CR3.
This is the header file for my paging code.
Here's my paging code, so far.
Here's a screen shot of what I'm getting.

So, I've pulled in the memory map from my kernel, and I'm using that to get an idea of what I'm needing to do. I'm planing on using identity mapping, and I'm kind of confused as to how I should lay out the page tables, and the page directory. Before I started this iteration of my attempts to implement paging I was under the impression that I'd be making one page directory with one page table on it, but the math is saying I should have 32 page tables. OMGWTFBBQ?! I'm still flaky on exactly what I should be putting in each page table, and how the page tables should be put on the page directory. I'm also starting to think that I don't understand what I should put on the CR3 register before I enable paging.

I'm thinking I'll only need to have one page directory, with 1024 entries, to represent the full 4GB of virtual address space. Most of the entries on my page directory will actually be empty, to represent non-present page tables. I'll be putting the physical address of my sole page directory on the CR3 register, and that'll be that. What's confusing me is this graphic from the wiki. It's showing the CR3 register pointing to a page directory, but leads me to think that it's representing a system with multiple page directories. Is that something to do with task switching which will come up later, or am I missing a concept again? On top of that, this image from James Malloy tells me I should be putting pointers on my page directory, and page tables. Hrm.

Here's what I'm thinking I'll need to do, based off my screen shot. Please correct me where I'm going wrong.

CR3 will be the physical address of my single page directory. That will be 0x109000.
My single page directory will have 1024 entries for completeness, but most of those will be 0x2 for non-present page tables.
For the 32 page tables that are present, what should I put in each entry of the page directory? Right now I have 4KB of space set aside for my page directory. I don't think, at this point, that I'm supposed to put the physical address for each page in there. Are those supposed to be the physical address where my page tables will go? Things will be very easy if that's the case! Based on what I've learned, I'm supposed to have a page table index in each entry on the page directory? I dunno. I can easily manage to set aside 32 4KB sections of memory for my page tables, but I'm not sure how to populate the page tables. Is each of my 32 page tables supposed to have 1024 entries consisting of physical memory addresses beyond the memory where my page tables live?

Here's what I'm thinking.

Code: Select all

CR3 = 0x109000 (the address of my page directory)

My page directory will be...

PD[0] = 0x10A000 (the address of my first page table)
PD[1] = 0x10B000 (the address of my second page table)
...
PD[31] = 0x13C000 (the address of my 32nd page table, assuming my math is correct)
PD[32] = 0x2 (for a non-present page table)
PD[33] = 0x2
...
PD[1023] = 0x2

This will take up the 4KB of space for my page directory.

My page tables will be

Page_Table_One[0] = 0x0 (the first physical memory address)
Page_Table_One[1] = 0x1000 (the physical address where the second 4K section of memory starts)
Page_Table_One[2] = 0x2000 (the physical address where the third 4K section of memory starts)
...
Page_Table_One[1023] = Whatever address is used for the 1024th piece of 4KB memory that's used.

Page_Table_Two[0] = The value from Page_Table_One[1023] + 0x1000
...
And so on for all 32 page tables.

Is that right?
What I'm trying to do is hand code my page directory, and page tables, as eryjus suggested. I'm obviously not going to hand code 32768 lines of code for all of them, but I need to know if my thinking is correct before I write the loops that'll be needed to populate the arrays.

Also, when I look at other people's OS's they all seem to have some form of physical memory manager (PMM), and I thought that was a required step on the road to paging. Is that wrong? I'm looking at the code from the paging section of the James Malloy tutorial, and he doesn't have any kind of PMM at all. In fact, I got rid of my PMM that was returning page aligned addresses after my kernel. He has a kmalloc() function, but all that does is apparently increment a placement address by an arbitrary value, and return it. I'm planning on just identity mapping all of the available memory into my page tables, and page directory, then going from there. I'm thinking that the user/supervisor bit will offer memory protection to keep me from doing stupid stuff to my kernel once I have paging done properly. Am I correct to think this way, or am I setting myself up for failure?

I'm thinking that I'm chasing my tail, and going in circles. The last time I had this much difficulty with learning something was calculus.

[eryjus]

I'm going to go out on a limb here and say that you are probably trying to convert (at least in your thinking) a physical address to a virtual one. I kept trying to do the same thing and nothing made any sense. Anyway, I feel your pain.

Instead consider that your entire system will be working on a virtual address scheme only. The physical memory that backs this virtual address scheme will be referred to as a frame. Frames are 4K aligned (meaning the last 12 bits are 0 -- this is critical since the offset into the page [the virtual memory equivalent to a frame] has a 12 bit offset). Therefore, a virtual memory page refers to a physical memory frame, and they do not have to have the same address.

So, say you want to map virtual address 0x0 to a frame to use. Starting with the Page Directory (which you will store the physical frame in CR3), you will need to have a 4K frame for this table (start by allocating this statically in your code). Your Page Directory will have 1024 entries, each entry will be 4 bytes long (4096 bytes for the whole table -- no more; no less). Bits 31..22 of your virtual address (0x0) are 0, so the system will look at entry 0 in your Page Directory and find a physical frame for your Page Table.

Again, I recommend you start by allocating this table statically in your code. Again, it will have 1024 entries, and again each entry will be 4 bytes long. Again, the total size will be 4K -- no more and no less. Now, bits 21..12 of your virtual address will also be 0, so the system will look at entry 0 of this Page Table to find the Page Table Entry (also referred to as a Page). Within these 4 bytes is a reference to the physical frame where the bytes are really stored.

Finally, bits 11..0 are an offset from the start of this Page (or frame) for the real byte you want to read/write.

Now, for your example, say you start with your Page Directory at 0x109000 and you have Page Tables that follow at 0x10a000, 0x10b000, 0x10c000, 0x10d000, 0x10e000, and 0x10f000 (which will map 24MB). You will do the following:

• PD[0] will have the address 0x10a000 | 1 [bit 0 means the table is present] | 2 [bit 1 means the table can be read and written]
• PD[1] = 0x10b000 | 3 (same as above)
• PD[2] = 0x10c000 | 3
• PD[3] = 0x10d000 | 3
• PD[4] = 0x10e000 | 3
• PD[5] = 0x10f000 | 3
• PD[6] .. PD[1023] = 0 -- I prefer 0 to 2 so that I will be able to control access in the future; in reality, you only need (& ~1)

Now, I think you mentioned that you want to identity map your virtual memory pages to the physical frames so that virtual address 0x0 points to physical frame 0x0.

So, you will take your PT @ 0x10a000 and make the following entries:

• PT[0] = 0 | 3 (same as above: bit 0 = Present and bit 1 = Read/Write)
• PT[1] = 0x1000 | 3 (do the math here... for virtual address 0x1000 the system will look at PD[0] and then PT[1] and then offset 0x000
• PT[2] = 0x2000 | 3
• PT[3] = 0x3000 | 3
• and so on (this is what I meant by hand-coding)

Now, since your Page Tables are contiguous, you can just continue on and load all the memory for these tables from 0x10a000 to 0x10ffff inclusive.

Once you have your tables built, the PD physical frame loaded in CR3, and paging enabled, you will be able to tell pretty quick if you have a problem with your tables.

One other tip -- get Bochs for testing. Build a version with the debugger enabled. With that, the 'page' and 'creg' debugging commands will be your best friends for a while.


Good luck!

[PatSanf]

Now, for your example, say you start with your Page Directory at 0x109000 and you have Page Tables that follow at 0x10a000, 0x10b000, 0x10c000, 0x10d000, 0x10e000, and 0x10f000 (which will map 24MB). You will do the following:

• PD[0] will have the address 0x10a000 | 1 [bit 0 means the table is present] | 2 [bit 1 means the table can be read and written]
• PD[1] = 0x10b000 | 3 (same as above)
• PD[2] = 0x10c000 | 3
• PD[3] = 0x10d000 | 3
• PD[4] = 0x10e000 | 3
• PD[5] = 0x10f000 | 3
• PD[6] .. PD[1023] = 0 -- I prefer 0 to 2 so that I will be able to control access in the future; in reality, you only need (& ~1)

Now, I think you mentioned that you want to identity map your virtual memory pages to the physical frames so that virtual address 0x0 points to physical frame 0x0.

So, you will take your PT @ 0x10a000 and make the following entries:

• PT[0] = 0 | 3 (same as above: bit 0 = Present and bit 1 = Read/Write)
• PT[1] = 0x1000 | 3 (do the math here... for virtual address 0x1000 the system will look at PD[0] and then PT[1] and then offset 0x000
• PT[2] = 0x2000 | 3
• PT[3] = 0x3000 | 3
• and so on (this is what I meant by hand-coding)

Now, since your Page Tables are contiguous, you can just continue on and load all the memory for these tables from 0x10a000 to 0x10ffff inclusive.

Once you have your tables built, the PD physical frame loaded in CR3, and paging enabled, you will be able to tell pretty quick if you have a problem with your tables.

One other tip -- get Bochs for testing. Build a version with the debugger enabled. With that, the 'page' and 'creg' debugging commands will be your best friends for a while.


Good luck!

That was the biggest help anyone could have provided because that bit of information was causing the most confusion. Thank you SO MUCH! I started working in that direction last night, and you've confirmed that I'm doing it properly. I already have the first page table getting filled as you described, and put in PD[0] at the address you specified. Here are a couple of screenshots of what I'm getting so far. I'm just running some step-by-step code with a couple of loops to fill things in as described. I believe that everything is correct, and once I have my page tables built I'll be able to continue with my project.