OSDev.org

I think I understood somewhat.
Now, the implementation for me can actually be a problem, because of how i've set it up before. Sorry if I didn't explain it well. I clarify my intentions, so you can help me better, if you want. I want to enable 4KB paging, not 4MB. I guess I copied the code for BootPageDirectory without a really understanding of what it does. I've managed something, but I cannot get that well. I mean, I got that but I can't change that to use 4KB pages. Here you are the mess I did:

I will then delete this page directory as the tutorial I followed suggested:

Said this, I want to talk about PAE a little. I'd like to activate PAE to make virtual space larger, and maybe expandable to 64 bit one day. But I read that I should change my target, from i686 to... what? It isn't x86_64 nor x86 (at this point)! Then should I change something in the bootloader, the GDT (the most likely) or the PMM I already set up? Is the VGA memory always at 0xC00B8000 (with the kernel's offset being at 0xC00000000)?


Yeah... hmm. The higher half should be there, but I think that if I enable PAE, I can theoretically move the kernel offset at more than 3GB, no? Otherwise I can map an entire page table to it and expect to not overflow, I guess. And well, the processes should get as much space as they can, I think.


The only difference between this and the PMM is that this returns an already mapped pointer? Can those (malloc() and free()) functions be system calls?

OK, from this, you are building this statically and you are using assembly to build the Page Directory. You want to use 4K pages. I have not gone through to bit-check your values, but I'm certain they will not work. Start by adding the word "physical" or "virtual" in front of "memory" or "frame" or any other such word so you get used to properly describing what you are referring to. I will help and you need to train your brain to understand the difference.

I'm going to stay away from PAE for the moment, for 2 reasons: 1) I have never worked with it directly and likely never will, and 2) it is just complicated enough to really make a mess of the conversation before you get your head around the 2-level Paging Table structure. This was mentioned before, and I suggest you take that advice for now.

Now statically building the paging structures might be OK for the short term and on 32-bit. I tried this in assembly for 64-bit. Once. I found it far easier to build them in code -- but that was my own experience. One thing to keep in mind as you continue to build out your kernel and statically build your paging tables: When your kernel pierces a new 4096 boundary, you will need to go back to your statically built paging tables and update them again. At some point down the road, you will need to dynamically build the tables anyway.

As a side note, if you do decide to build this in code, you will just go get a physical frame from your PMM to put the Page Directory (singular for the kernel) and Page Tables (multiple) in. These structure fit perfectly in a physical frame (all are 4096 bytes). You will see you need 3 frames to get started and more as you add on.

You have a Page Directory in your code above. That Page Directory has some flaws (which you might have corrected but did not share that bit of the code):
* It MUST be 4K aligned.
* It MUST be 4K in length.
* Each Entry is 4 bytes long (a quick Google search shows the last 2 fields might be switched, but that might be assembler dependent)

So, let's say that you load your kernel at physical address 0x100000 (1MB). Your Page Directory is statically allocated and the linker puts that at (and I'm making this up, the actual physical address is not important) 0x10c000. The unused parts of this table need to be zero-initialized (which is what I think you wanted to do above).

Now, you need to identity map the first 1MB of the Virtual Address space. To do this you will need a Page Table. You do not have one yet. This will look exactly like the Page Directory but will be in a different Physical Address. Let's assume your linker put your static one at 0x10d000. Now, the actual address does not matter if you are building these in code. However, if you are building these statically in assembly language you are going to have to take great care with the linker script to make sure you *know* where they reside.

With this knowledge, you will map Entry 0 in your Page Directory to point to the Physical Frame number where your first Page Table resides. In other words, you will set PD[0] = 0x10d000 >> 12 = 0x10d and set all the other proper bits for the entry (p for sure, but there are a couple of others ).

Now we can actually identity map the first Page. These will point to the same Physical Address. However, the physical frame number is (Physical_Address / 4096) or (Physical_Address >> 12), as I did above.

Now, (IPT is short for "Identity Page Table") IPT[0] = 0 >> 12. What is this? Well, I mapped the first Virtual Address Page (0x00000000) to Physical Frame (0x00000000 >> 12). Well, that's pretty boring, so let's do the next one.

IPT[1] = 0x1000 >> 12. This is the Virtual Address Space from 0x00001000 to 0x00001fff is contained in the 4K Physical frame 0x00001000 >> 12. Or put another way, Virtual Address 0x00001000 is contained on Frame 1.

IPT[2] = 2 and so on up to PT[0xff] = 0xff or 1MB. As a matter of fact you should continue this for your kernel as well up to the upper space of your kernel binary:

IPT[0x100] = 0x100
IPT[0x101] = 0x101
(and so on)

You can get your linker script to provide you with this limit in a variable if you build this in code.

How about the upper memory? Well you need another Page Table for that, just like above (assume 0x10e000). You will need to add this into the Page Directory. Since you are putting your kernel at Virtual Address 0xc0000000, you will need to point your Page Directory to the additional Page Table: PD[768] = 0x10e000 > 12 = 0x10e.

Now, your kernel is located at physical address 0x00100000 or physical frame 0x00100000 >> 12 = 0x100. What you want is to make sure that virtual address 0xc0000000 points to the kernel physical frames. To do this, you will set ("UPT" means "Upper Page Table", to differentiate from the other one above):
UPT[0] = 0x100
UPT[1] = 0x101
(and so on)

I want you to notice that you now have 2 virtual address pages pointing to the same physical memory addresses. You will be able to access the exact same bits of physical memory from both addresses.

When you are ready, you can load the Physical Address (not the frame number) of your Page Directory into cr3 and then enable paging. Well, there's a lot that can go wrong as you are figuring out, but these steps are where the "magic" happens.

I tried some assembly but then I wasn't been able to set it right, so now I don't set the higher half kernel in boot.S (with) but rather in the initialization of the virtual memory manager (in C). There is no need to say that it equally triple-faults. I followed a bit what was the previous scheme showed in the tutorial, and here it is what is came out:

I only didn't understand 1 thing from that tutorial: why when allocating dir I need 3 blocks and not just 2?

Hi,

If you are attempting to enable paging and a higher half kernel directly within the kernel program, you would either need to initialize the paging structures with position independent code (if base address is different then load address) or have the kernel relocate itself to 3GB (if they are the same and at 1MB initially.) In other words, you will have a little more work to do. I believe three blocks were allocated initially for debugging only; however you only need one block for the page directory and page tables.

Since you will need a way to allocate and dynamically map page tables, we are not quite sure what the end goal of rewriting and moving the initialization code is. It is easier to enable paging in the boot loader and set up a virtual address space layout for the kernel. The reason the original code didn't work was because allocBlocks returns a physical address. However, by keeping the paging code in the kernel only, its load address will be 1MB (most probably) that will need to be relocated to 3GB when the higher half gets mapped.

@Xcp,

I feel like you are writing code without fully understanding what your target should be. As a result, I keep walking backward to find a good place to start. I have deliberately left out several details because I am hoping you are comparing my responses to the Intel manuals and coming up with your own plan to code your solution. I'm here to help you understand, but it goes against my better judgement to provide a comprehensive solution. I have always maintained that writing a hobby OS is a research project long before it is a coding project.

From your code, you are still confusing a page with a frame with a physical (or linear) address with a virtual address in at least some combination. Sticking with 4K pages:
* A page is a 4K block of virtual address space that is mapped to a frame and may or may not be present. These are 4K aligned.
* A frame is a 4K block of physical memory that is referenced by one or more pages. These are also 4K aligned, and I refer to frame numbers as 0, 1, 2, 3, ... and is calculated as (physical_address >> 12).
* Physical or linear address is the location of the actual bits of memory on the system.
* Virtual address is just an address space that your programs use to refer to the elements within itself. This virtual address carved up to select the index of the Page Directory, the frame of the Page Table, the index of the Page Table (and at this point its page), the frame of the physical memory, and the offset into that frame.

I would suggest you compare what I wrote (particularly the last bullet on how a virtual address is carved up) to the Intel manuals for Paging. I have an older copy so the figure number might not be the same as what you have (you do have them, right?), but Figure 4-2 illustrates this. I would spend more time gaining an understanding of this figure and the text descriptions in the manuals for now over trying to get the kernel running.

Now, everyone learns differently. If you need to write code to cement your understanding, then here is an assignment . Write the following for yourself:
* FrameToLinear()
* LinearToFrame()
* GetPDIndexFromVirtualAddr()
* GetPTIndexFromVirtualAddr()

Then write a normal user space program that will take an address from you as input and report the PD index, PT index, and the offset into the page as output (using your functions above). You won't need any actual "tables" to write these functions or the program. Check your output with the Figure 4-2. Check several addresses by hand and look for bugs.

These functions (and more importantly the operations they perform) are foundational to understanding and implementing paging. But be warned -- it's a start but it's not everything.

Can you give me some examples, please, about initialize with position independent code?

I tried to fill the page table in assembly but I wasn't entirely able to do that, so I thought that in C would have been easier and better to understand later on.

So what should I do to the returned physical address?

@eryjus I read the Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A and the Figure 4-2 explains it. I think I understood the 32-bit paging addressing method. I only have some doubts about it:
- Take as an example a Page Table, I have a PD pointer (4k aligned) from CR3, then with the 31:22 bits of the virtual address I "index" through the PDirectory to find a pointer to a PTable, right? Once I've found that, I start compose the new address to find a PTE like this (as described in the Intel Manual):
* 39:32 = 0
* 31:12 = PT pointer from the PD (4k aligned)
* 11:2 = bits 21:12 of the actual virtual address
* 1:0 = 0
In the memory location that the "generated" address points to, there will be (in the 31:12 bits, in 11:0 there will be flags) a physical address of a page (a 4k aligned pointer). I find the physical address by setting 11:0 bits as the 11:0 from the virtual address, besides setting 31:12 with the PTE pointer from the PT.
Am I right?

BTW, I'll try to implement those functions, thanks.

Sorry, I thought I had responded to this last night from a different computer.



Not yet.



Sorry, this is not right either.

Let's see what your test program comes back with and I will drill into some real examples with your sample output.

Ouch!
Maybe I confused something in the explanation. I thought I've got something from the Intel Manual. I tried anyway.
GetPDIndexFromVirtualAddr(), GetPTIndexFromVirtualAddr(), GetPageOffsetFromVirtualAddr() weren't hard to code as they just shift bits, however I think those are right. If I insert 0xC0000000 the PD index is 0x300, the other two are 0x0, so I think it's right.


I think that I cannot code LinearToFrame() yet, because it wants the paging structures set up, but it shouldn't be that hard.
The one who I had some trouble thinking about is FrameToLinear(). I guess that I should find the nearest 4k aligned address (or page start) and build backwards from there, right?

Awesome.

Hang onto those functions. They are all pretty easy and can even be reimplemented as macros.

So, FrameToLinear and LinearToFrame are not any more difficult -- they just shift bits. I may not have been clear in my explanation. I may have further confused the issue by not calling them PhysicalToFrame() and FrameToPhysical() -- which more accurately describes their purpose.

Physical address 0x00100000 sits in frame 0x00000100. Physical address 0x00100334 also sits in frame 0x00000100. The conversion from physical address to the frame number is: pAddr >> 12. As you can imagine the conversion the other direction is frame << 12 -- which will give you the starting address for the frame. You will want to implement these as functions/macros as well and will likely use them in your final code.

So, let's pick apart a more interesting address using your functions before I get into the actual page entry structure: 0xc0651234 -- let's say somewhere in your kernel data (heap). If you put this through your program, you will see the PD index is 0b1100000001 or 0x301 or 769. Moreover your PT index is 0b1001010001 or 0x251 or 593. This then leaves the index into the page, which is 0x234.

Taking this address, the MMU will look in the cr3 register for the frame number of the Page Directory (it has a frame number plus 12 additional bits where there are flags, which might have been what you were trying to say earlier). This frame number is converted to a physical address (recall: pAddr = frame << 12).

The PD index is then used to calculate an offset into the Page Directory (0x301 or 769 from my example address).

The PageTableEntry_t at that physical address is then loaded, which contains the frame number of the Page Table (I did not offer a concrete frame number for my example -- don't let that throw you). That frame number is then turned into a physical address.

Now, the PT index is then used ot calculate the offset into the Page Table (0x251 or 593 from above).

At that point, you will have a PageTableEntry_t for the frame of real physical memory that is backing your virtual address of 0xc0651234.

The offset into the start of the frame is the same as the offset into the Page.

All of this happens with each virtual address you reference and if any of this breaks for any reason (page is not present, table missing, other flags set wrong, really lots of reasons) you will end up with a #PF Page Fault.

But this is also useful information as you can use that to write a DumpPageTables() function to use when you are debugging your initialization code -- I really think a function like this is useful and should be implemented. This also gives you how the system will translate a virtual address into a physical one. It also helps because you will need to build your tables to support all this work.

To help me keep things straight when I come back to my code days/weeks/months later, I like to do something like the following:



And of course there is the magical Page Table Entry:



I have not seen all your code, but I assume you have something like this somewhere. What I want to call out here is that I have a 'frame' field whose size matches the range I want to use with 'frame_t' (20 bits). This is where your FrameToPhysical() and PhysicalToFrame() come in.

The real magic is how to populate the tables such that none of the rules are broken and you end up with a #PF (and if you don't have a interrupt handler a triple fault).

So, the first thing you will do is allocate a Page Directory from your PMM (whether you are allocating physical addresses or frames is up to you). This is the Physical Address and while you are constructing your initial tables you can use the physical address. I recommend initializing this to all 0's -- in particular to set the p flag to be 'not present'.

So let's go through mapping the example address above for 0xc0651234. You need Page Directory Entry 0x301. You get the Page Directory Entry (really PageTableEntry_t type) for that offset and realize that the p flag is 0. OK, there is no Page Table for that Entry -- let's make one!

Go get another frame from your PMM. Initialize the associated physical memory to 0. (Are you starting to see the value of FrameToPhysical() and PhysicalToFrame()?) Place the frame in PageTableEntry_t.frame of your Page Directory Entry from above and set all the other bits (especially p!). With that, now you can get the Page Table Entry at 0x251. I the p flag set? Nope (well we just initialized it) -- good!! If we are trying to map an address to a frame that already is mapped to a different frame, this might be a bug. It's better to umap before you try to remap and trap this condition.

Anyway, now we can map this page to the desired frame, setting all the proper bits here as well (p!). Congratulations, you have mapped a virtual address to point to a physical frame (and by extension the physical memory).

Now, if you look at the next page in virtual address space (0xc0652000), the Page Directory Entry 0x301 is the same. No problem there, we already have that mapped to a Page Table. The Page Table Entry (0x252 this time) is not mapped (p == 0), so we will map it to the proper physical frame.

This gives you enough information to build your paging tables for your initialization code. This would be a MapVirtualAddressToFrame() function. Using similar logic, you will implement an UnMapVirtualAddress() function.


Now, once you are established in higher memory, you will need to use recursive mapping to do all this work -- a clever trick to set aside some of the virtual address space (not physical memory) for managing these tables using virtual addresses rather than physical addresses. They will be readily available using the address space from 0xffc00000 to 0xfffff000 -- assuming you map PD[1023] to its own frame. When you get to that point, refer back to the wiki.

One final note -- when you get to the point where you are beyond your identity mapped space, you will have trouble with page faults. For this reason I use a bitmap and frame number to manage my physical memory. I am not saying that your implementation is wrong -- quite the opposite. But it is something to think about how you will handle this later.

Well, that's it. My moral is smashing down. I'm still wrong somewhere in here. I think that I followed your advices with caution, but it didn't work: it still triple-faults after I get paging enabled. Can you please take a look at my initialization code? I would be so grateful, after all you did for me...

I will take a look at it, but tonight I am performing a Disaster Recovery test for my real job -- an all night exercise. It might be some time tomorrow or Sunday before I can get to it and spend some real time reviewing it.



A triple fault is not the end of the world, but a debugging exercise. You have to learn to expect them and how to deal with them. They are going to happen and more frequently than you want.

For the record, I have been dealing with general protection fault, page fault and triple fault debugging myself for the better part of a week. A good part of the new code included setting up user-space and paging for a user-space process and I only got a good execution today. In the meantime, check out my journal about these experiences -- you might pick up a debugging trick or two.

https://github.com/eryjus/century-os/bl ... JOURNAL.md

I taught my daughter to always write down the units of measure when doing math since is serves as a sanity check to make sure you are doing the right operations. The same lesson applies here. I am going to update some of your variable names.



You are declaring a variable pdAddr which in obviously intended to be a location in memory. I can deduce this solely based on its resulting type. I assume that assocBlocks() returns a physical address because you feel you need to pass that through PhysicalToFrame() to convert it. So, in the above block of code, i read that you are getting a physical address, converting it to a frame, and then pretending it is still a physical address. That's not going to work.

Now, in the very next section of code:



First, I can see confirmation my deduction that you still using that is essentially a frame as an address is accurate. Now, you are only initializing the present bit in each of those entries, leaving the rest to be in whatever state they happen to be in and hoping for the best. Not to be too harsh on this, but this is a rookie programming mistake -- and is especially true with OS development: You must assume that nothing is in a state you want it to be in and initialize everything so you know it is valid. What is to say that your table does not have (and in my mind it does until you can prove to me you initialized it somehow) some invalid bit set that you did not initialize to a state you control causing your #PF? I was clear about initializing the entire entry to 0. You do have a kmemset() function? Now it the time to write it and use it:





Wow, there is a lot going on here, and I think you got lost in your own code. What is PAGE_SIZE? I believe it to be the size of a page of virtual memory (or 4096). If that assumption is correct, what the heck is "i < PAGE_SIZE >> 4"? 'i' appears to be used as a counter, but I do not understand how it would relate. It looks like you are mixing units of measure and later down the road when you are reading your own code, you will also be confused.

Then, there is this whole 'frame' thing. On the first iteration, frame is set to 0, and with each subsequent iteration frame is set to BLOCK_SIZE. Again, I see this as a rookie debugging mistake -- you have to learn to read your own code objectively to look for errors. You may or may not be able to get your code working the first time through and the reality is very few of us do. Instead, we all typically write a small block of code and then write a test for it and debug it. Then we move on and write another small block of code and test that. This iterative approach keeps the focus of debugging relatively small. And, yes, sometimes you will need to just set it aside for a short time and come back to it with a clear mind and look at it again. But you are not going to get instant gratification when writing an OS -- it can take weeks/months to get a section of code written and tested and working.

At this point, I have to wonder if you have the Required Knowledge to take on writing an operating system from the ground up, or if you are struggling with comprehension because English is not your primary language. Either situation (or both or something else entirely) are fine, but you need to be able to assess your own skill levels and brush up where you have deficiencies. One essential skill is to read a technical manual and be able to code meet that specification.

First of all, thank you for reviewing my code.
I'm going to make some fix to the quoted code to show how it is now.

allocBlocks() doesn't necessarily return a 4k aligned address so, I don't know why, I felt like the frame was going to be ok. I was wrong. I should '&' the physical address with 0xfffff000 to get a 4k aligned address, yes, but then the stack wouldn't be right, so I got to fix this.


Yes, my fault. I wrongly thought that this was going to be ok, but actually you're right. Why only the 'p' flag should be unset? So, I am going to write functions like kmemset(), kmemcpy()...


I was thinking that if a page is 4096 byte big, then to map 1MB, 256 cycles would be enough since 256 * 4096 = 1048576. And yes, I didn't use it, but if I do i < PAGE_SIZE >> 4, frame < 0x100000 or (in the second loop) virtual < KERNEL_BASE_ADDRESS + 0x100000 isn't it the same?


Oh come on, you're completely right in every word you said, but that was clearly a typo I didn't see... I'll test every page table/directory and see if they are as they should are.

Hi,

If using bit fields, entries[0].frame is a Page Frame Number (PFN) not a physical address. So to identity map, your code might look something like this (consider how this can be simplified farther) :Also, you need to map the currently executing code and data. In other words, identitySpaceEnd must be large enough to encapsulate everything needed by the currently executing code. Don't use 1MB when the kernel starts at 1MB. Consider how the above can be modified to map 1MB->3GB. Note that page directories have the same structure as page tables -- they reference page tables by PFN as well.

You will need two page tables and one page directory. One page table for identity mapping the kernel, and another page table to map the kernel to 3GB. At a minimum, your code can look something like this:Finally, note that as soon as paging is enabled, all addresses will be virtual so code like the above won't work after that point. (This is, in fact, why your original code was page faulting.) Careful not to mix virtual addresses with physical frames. There is a chicken-egg scenario: how do you map a page table when you need an existing page table already mapped to map the new one? I.e. you use pointers (virtual addresses) to set up page tables, which means those virtual addresses you are using must already be mapped or you'll get a page fault. This is what recursive paging tries to solve.

About the present bit... the processor will ignore all other bits when the present bit is clear. It will only raise a page fault if the code attempts to read/write its respective page in the address space. This allows operating system designers to implement custom PTE types, such as Prototype PTE's, Transitional PTE's, PTE free lists, etc that are used in shared memory systems, page swapping, and others. I.e. if the present bit is clear, the operating system is free to use the remaining bits for any purpose.