Virtual Memory manager

[Xcp]

While following this (http://www.brokenthorn.com/Resources/OSDev18.html) tutorial about memory management, I've found that when he starts the virtual memory manager, vmmngr_initialize() identity maps the first 4MB and maps the kernel at 0xC0000000. Why do I have to identity map the first 4MB? I tried anyway declaring a pointer to the page table and identity map it but it crashes when I try to access firstTable->entries[PAGE_TABLE_INDEX(virtual)]:

Code: Select all

// First 4MB page table
ptable_t *firstTable = (ptable_t *)allocBlocks(1);
if(!firstTable)
    return;
...

// First 4MB are identity mapped
for(i = 0, frame = 0x0, virtual = 0x00000000; i < 1024; i++, frame += BLOCK_SIZE, virtual += BLOCK_SIZE) {
    // Create a page
    pt_entry_t page = 0;
    ptAddAttrib(&page, I86_PTE_PRESENT);
    ptSetFrame(&page, frame);

    // Add to the page table
    firstTable->entries[PAGE_TABLE_INDEX(virtual)] = page;
}
...

Plus I think that the tutorial is not expecting multitasking because it only maps the kernel in the init function. Should I make a function that create another page directory and already maps in the kernel when a process is created?

[nullplan]

You need the identity map because Intel says so.

In the 386's manual they stated that when turning on paging, the MOV instruction that actually flips the switch must be in an identity mapped page, or else the very next instruction must be a jump instruction. Then the 486 came out and they quietly dropped that second part, because the built-in cache made their earlier trick not work anymore. That is also why SCO Unix 1 won't work on anything newer than a 386.

This way also makes way more sense. The moment you flip the PG bit, you have an indirect control transfer (from physical address 0x0010XXXX to virtual address 0x0010XXXX). Many things in the CPU, like cache control, TLBs, and the like, are not set up to handle this correctly, unless there really is no transfer at all, which is only the case if the MOV instruction that turns on paging is in an identity-mapped area. You should be able to throw out the identity map the moment the jump to higher half occurred.

When you add multitasking, you are going to need to manage your own page tables. Most common choice is to have pne paging structure per process. The high part of the page directory can be copied, but the low part is specific to each process.

[Xcp]

Ok... another question raised my mind: For every process do i have to map the entire physical space or just the requested bytes? Then when I know whenever it wants/needs more space?

[linguofreak]

You need the identity map because Intel says so.

In the 386's manual they stated that when turning on paging, the MOV instruction that actually flips the switch must be in an identity mapped page, or else the very next instruction must be a jump instruction. Then the 486 came out and they quietly dropped that second part, because the built-in cache made their earlier trick not work anymore. That is also why SCO Unix 1 won't work on anything newer than a 386.

Will the CPU actually fault on the attempt to enable paging itself if the page that makes the switch isn't identity mapped, or is it a matter of "without making the code that enables paging a Lovecraftian horror, you will incur a page fault in short order if you try this"? I could imagine some ugly kludge like "paging is enabled by the instruction at physical address X. The page at mapped at virtual address X+1 is a different page, but has identical code in the vicinity of virtual address X to that which exists at physical address X", but I don' know when you say "Intel says so" if you mean that the CPU assumes you will identity map the page and makes no effort to save you from your own stupidity if you try not doing so, or if it will actively refuse to enable paging if it finds that the page table does not identity map the location of the IP.

@XCP: Whatever the case as to the actual architecture of the CPU, you want to identity map the page for the sake of your own sanity in reasoning about what's happening in the code that switches on paging, and in debugging anything that goes wrong.

[eryjus]

From experience, the CPU will Page Fault as soon as you enable paging and you do not have the next instruction mapped. But don't be short sighted by mapping a single page.

Consider for example that you have an instruction to enable paging near the end of any given page and the next instruction is a jump instruction that resides on the next page. Or, if you are writing your kernel in C, it is completely likely that you will have a short assembly function to perform that move after which you would return to the calling function in a completely different page.

Now, even if it happened to be in the same page, your stack probably is not. Yup, that needs to be mapped as well until you get setup again in higher memroy. As well as any data that might be accessed between enabling paging and actually establishing your kernel properly running in higher memory.

It is common to identity map all of the kernel space to the physical addresses where it was loaded and to its higher memory location. I believe this is partly what the OP was asking -- why 4MB? I have not read that particular tutorial, but it most likely covers the kernel with all its data.

As for low memory, there are some structures that Multiboot will create and other things you might want to access from their original addresses until you capture all the information you need. You may want to write to video buffer at the low memory address. Again, it is common to identity map the first MB of memory at least during initialization, and then possibly even hold that aside for things can only operate in low memory (IIRC DMA falls into this category).

[neon]

Hi,

Your recent posts suggests you may be using a free stack and GrUB. Please let us know the current environment the code is being executed in.

Regarding the crash... Given the current information, we can only assume that paging is already enabled prior to the code presented (the boot loader provided by the tutorial enables paging) in which case we would expect firstTables->entries result in a page fault since it would be dereferencing a physical address not yet mapped. Note that in the tutorial we can directly reference it because the boot loader already identity mapped the current address space. However if this assumption is not met, it would be a page fault. If you are using GrUB, we would need to know if you are performing relocation or a stub program to enable paging.

I typically recommend recursive paging since it simplifies a lot of the problems with mapping/accessing page tables. Since page tables must be mapped in kernel space, another solution is to allocate free virtual memory blocks from kernel space and map the page table to write to it. Basically, there should be a way to manage what regions of the kernel address space are free to use and you can map to them (typically a memory region allocator or a PTE free list. A bitmap can also be used.) No matter which way you decide to go, the basic idea is that firstTable must be accessible (mapped) into the address space before you write to it.

For multitasking... Typically kernel space is shared among processes (it is shared memory.) The current address space the kernel starts up in will typically become a root process. Each process control block would have a pointer to a page directory which represents its address space. Having functions like CreateAddressSpace and MapKernelSpace are a good idea. In fact, tutorials 24 and 25 extend the memory manager as needed to support it.

Why 4MB identity space... It requires a single page table (i.e. one 4K page for the table itself) and we do not need to make much assumption about current memory allocations in use or reserved (i.e. kernel size, physical frame bitmap location and size, stack, video memory identity mapped, CMOS area identity mapped, and any additional buffers reserved for the DMAC are all preserved. It also keeps the boot loader in tact for a fallback on triple fault during very early boot.)

[Xcp]

Your recent posts suggests you may be using a free stack and GrUB. Please let us know the current environment the code is being executed in.

Regarding the crash... Given the current information, we can only assume that paging is already enabled prior to the code presented (the boot loader provided by the tutorial enables paging) in which case we would expect firstTables->entries result in a page fault since it would be dereferencing a physical address not yet mapped. Note that in the tutorial we can directly reference it because the boot loader already identity mapped the current address space. However if this assumption is not met, it would be a page fault. If you are using GrUB, we would need to know if you are performing relocation or a stub program to enable paging.

Yes, paging is enabled so I think it's a triple fault. I've identity mapped and enabled paging in my boot.S.

Code: Select all

BootPageDirectory:
    .int 0x00000083   
    .fill KERNEL_PAGE_NUMBER - 1, 4, 0

    .int 0x00000083
    .fill 0x4000 - KERNEL_PAGE_NUMBER - 1, 4, 0

    ...

    mov $BootPageDirectory, %ecx
    mov %ecx, %cr3                                       
   
    mov %cr4, %ecx
    or $0x00000010, %ecx                          
    mov %ecx, %cr4   
   
    mov %cr0, %ecx
    or $0x80000000, %ecx                                   
    mov %ecx, %cr0

    jmp higherHalf   

I did it to map the kernel in the higher half at 0xC0000000. Now I can't disable it, though. Should I wait to move the kernel in the higher half in the virtual memory manager?

Code: Select all

__attribute__ ((noreturn));
void main(multiboot_info_t* map, unsigned int magicNumber) {       
    gdt(); 
    
    initScreen();
    printf("magic number = %d\n", magicNumber);

    // Start the physical and virtual memory manager
    initPMM(map);
    initVMM();
}

Where initPMM(map) starts a stack of free addresses.

I typically recommend recursive paging since it simplifies a lot of the problems with mapping/accessing page tables. Since page tables must be mapped in kernel space, another solution is to allocate free virtual memory blocks from kernel space and map the page table to write to it. Basically, there should be a way to manage what regions of the kernel address space are free to use and you can map to them (typically a memory region allocator or a PTE free list. A bitmap can also be used.) No matter which way you decide to go, the basic idea is that firstTable must be accessible (mapped) into the address space before you write to it.

Didn't understand well this. Firstly, what recursive paging is? Then, does it means that I have to map all the virtual space per process? If it is yes, should I have to disable paging every time to do it? How? Another, do I need something like the physical stack but in a virtual way?

[neon]

Hi,

In BootPageDirectory, the 0x4000 should be 0x400 or 1024 since the table only has 1024 entries. Additionally, it is only mapping two active pages -- the zero page and one at 3GB. If allocBlocks returns a physical address outside of this region, it will page fault on any access to it. You will need to map a new page for the pointers returned by allocBlocks.

In practice, you should have (1) a kernel heap allocator, (2) address space manager, (3) virtual memory manager, and (4) page frame allocator. The virtual memory manager would have an AllocPage function that calls the page frame allocator and works with the address space manager to find a free page to map it. The heap allocator can then call the virtual memory manager to reserve a region for pool memory.

With recursive paging, the page tables and page directory would always be at the same location in the virtual address space so you would only need to call the page frame allocator to find a free frame and map it. It is effectively what it is used for -- so you don't need to manage what virtual addresses are mapped to what page tables.

Should I wait to move the kernel in the higher half in the virtual memory manager?

What you have is fine for now -- all you need is a way to map frames to free pages.

Firstly, what recursive paging is? Then, does it means that I have to map all the virtual space per process? If it is yes, should I have to disable paging every time to do it? How? Another, do I need something like the physical stack but in a virtual way?

When creating a new process, you would typically just copy over kernel page table entries into the new address space. The rest of the process can remain unmapped. Each thread has its own kernel mode stack. So at a minimum, you need CreateAddressSpace, MapKernelSpace, CreateKernelStack, and CreateTask.

[eryjus]

Didn't understand well this. Firstly, what recursive paging is? Then, does it means that I have to map all the virtual space per process? If it is yes, should I have to disable paging every time to do it? How? Another, do I need something like the physical stack but in a virtual way?

First, I hope you have been able to read this wiki topic: https://wiki.osdev.org/Page_Tables

I also had trouble with this in the beginning and it took me some effort to get my head around this: viewtopic.php?f=1&t=28734

And, here is another thread which will be helpful: viewtopic.php?f=1&t=32036

Now with that said, recursive mapping is where you take one Page Directory Entry and point it back to the Page Directory itself. This will allow you to access the entire kernel paging structure by access the address range of that Page Directory Entry. For example PD[1023] = PD, then the address of the Page Directory is 0xfffff000 and you can access it via normal virtual addresses. Take some time to convince yourself that this works and how. You will spend some time coding functions to perform many processes with this information.

Your other question about disabling paging is one I suffered through in the beginning as well. Once you have paging enabled, you typically will not want to disable it. The reason is you have to get into some identity mapped portion of code to disable paging since the next instruction will be executes in physical memory 0xc-whatever -- your higher memory location of the kernel. Simply replacing cr3 with the paging tables for any running processes (if they differ for your kernel -- that decision is up to you) during a process switch.

Your stack is memory just like your code and data. It is also accessed via virtual addresses. So, you will need to have a stack properly mapped in virtual memory to physical memory frames.

Now when you say 'physical stack', are you referring to your Physical Memory Manager allocation method? If so, then no. If each process has its own Page Directory and Page Tables, then they own that address space. You will construct them, not release them like physical memory. What will count is to what frames that memory is mapped. Some hypothetical examples (and may not relate directly to your situation, but for understanding):

* The kernel is mapped from 0xc0000000 and up. It is mapped to the physical frames from 0x00100000 to, say 0x00200000 (this is where GRUB would have put your kernel). This will cover all your kernel code and data. I would also presume your kernel stack would be in this space somewhere as well.
* Now you kick off process A. This process might get its own Page Directory and its own Page Tables. This job will run in address space from 0x00100000 to 0x80000000 (not to be confused with the physical space where your kernel was placed). You will map those pages to the physical frames that were allocated from your stack for this process. You will also need to be able to access the kernel space for System Calls, so you will map the Page Directory for the memory above 0xc0000000 and up for process A to match the kernel (except for the recursive mapping at PD[1023], which of course still points to itself.
* Now you kick off process B. This follows the same rules as process A, but is a totally different binary. It also uses the same memory space. However, the key here is that the pages of the virtual address space map to different physical frames that contain the new and different code.

Since you were wise and planned to put your kernel where you did, you only need to set the ProcessA.PD[768] = Kernel.PD[768] (and so on) and what you have done is mapped to the same physical frame for the kernel Page Table and there is no need to duplicate the physical memory or even set up additional Page Tables for this space. These blocks cover 4MB each (in 32-bit mode) -- 1 Page Directory Entry = 1 Page Table (the whole thing) = 4MB. There can be 4MB page sizes, but let's keep it simple for now. I took the time to break my virtual memory map into 4MB sections of like data.

Also, you can do something like this for shared memory: ProcessB.PD[511] = ProcessA.PD[511] and you are using the same 4MB of frames for both processes. They share the same physical frames.

One key takeaway is to spend some time getting to know how the tables work together. Convince yourself that a page eventually points to a frame of physical memory. Then convince yourself that with different cr3 values, you can actually get different frames for the same virtual address (Process A and Process B). Finally, now is the time to plan out your virtual memory map and where you want to put everything (this is an address space exercise, not a physical memory exercise).

EDIT: clean up some typos

[nullplan]

Your boot page directory and paging setup do not fit together. As is, you have enabled PAE paging, but are still using the old structures. With PAE, each page table entry doubles in size, which reduces the number of entries to 512 per page, which introduces a third layer of paging on the top, and it changes the shift counts (Instead of a 32-bit address being 10 bits page directory offset, 10 bits page table offset, and 12 bits page offset, it is now 2 bits page directory pointer offset, 9 bits page directory offset, 9 bits page table offset, and 12 bits page offset).

And unless you modify the paging structures later, the page directory you have won't work even without PAE. You are telling the CPU that the page table for the first 4MB can be fount at address 0, not the address you are using for it.

Recursive paging has been explained well enough. One problem with it is that it wastes one entry on the highest level paging structure you have. That isn't a problem in 32-bit paging without PAE, as there it is just 1/1024 of virtual space. It also isn't a problem with 64-bit paging with PAE, as there it is 1/512 of available virtual address space, and address space is virtually infinite. But 32-bit paging with PAE has a 4-entry page directory pointer at the top, so using recursive paging here wastes 1/4 of address space.

It's still a possibility. You are using C0000000 as kernel base address, so we can have PDP[2] = PDP. That means, the paging structure is available between addresses 0x80000000 and 0xBFFFFFFF. Ultimate self recursion is at 0x80402010. PDP[x] is available at 0x80402000 + (x*8). PD[x,y] is available at 0x80400000 + (x << 12) + (y << 3), for x != 2 (x == 2 is the recursion entry, so it's special). PT[x,y,z] is available at 0x80000000 + (x << 21) + (y << 12) + (z << 3), again, for x != 2. Access with x > 3 leads to undefined behavior.

My suggestion to you would be to get a handle on paging, paging structures, PAE, all that stuff, so you know what is happening when you turn on that bit.

[Xcp]

Thanks all for the replies.

I've been studying a bit, because although I understood the Page_Tables wiki article, I wasn't really confident with this argument. I'm losing my mind because of this so please be nice with me...

In practice, you should have (1) a kernel heap allocator, (2) address space manager, (3) virtual memory manager, and (4) page frame allocator. The virtual memory manager would have an AllocPage function that calls the page frame allocator and works with the address space manager to find a free page to map it. The heap allocator can then call the virtual memory manager to reserve a region for pool memory.

Are pages mapped just "|=" with 3 (present and writable), right? Like... sorry but I'm blocked right now 0.0. I think that I did what you are describing but I was directly reserve a region from the virtual memory manager without passing by a kernel heap allocator. Should I add it?
I find a physical block that best-fits and return a pointer to that region of memory. Once I did this, I make a page setting it as present and to the frame (from 0 to 4MB). Then I add it to the page table. Should I map the page table before accessing it? Always "|=" it with 3?? And before it the page directory too? I don't know what I'm talking about at this point.
By the way I didn't really get these 2 functions, I would be so glad if someone is so nice to explain them:

Code: Select all

inline void pt_entry_set_frame (pt_entry* e, physical_addr addr) {
	*e = (*e & ~I86_PTE_FRAME) | addr;
}
inline physical_addr pt_entry_pfn (pt_entry e) {
	return e & I86_PTE_FRAME;
}

where I86_PTE_FRAME = 0x7FFFF000

I also had trouble with this in the beginning and it took me some effort to get my head around this: viewtopic.php?f=1&t=28734

This 64-bit paging thread is shaking my mind. I understood something, but is this sentence:

The position of the PML4 depends entirely on where you map it. If you map the PML4 to its own last entry, then it will be in the last 4k of the address space because it will be recursively mapped to the end of (itself viewed as) a PDPT, the end of a PD, and finally the end of a PT. If you map it to its first entry, it will be in the first page of the address space, and the same for any of the 512 positions available for it, evenly spaced throughout the address space.

that has got something in me.

Now when you say 'physical stack', are you referring to your Physical Memory Manager allocation method?

Yes, I am. I mean, @neon wrote that I should maintain a memory region allocator or a PTE free list. Isn't that just like the one I use to keep the physical frames, but with virtual pages?

* Now you kick off process A. This process might get its own Page Directory and its own Page Tables. This job will run in address space from 0x00100000 to 0x80000000 (not to be confused with the physical space where your kernel was placed). You will map those pages to the physical frames that were allocated from your stack for this process. You will also need to be able to access the kernel space for System Calls, so you will map the Page Directory for the memory above 0xc0000000 and up for process A to match the kernel (except for the recursive mapping at PD[1023], which of course still points to itself.

Here you're talking about the process A that starts from 0x00100000. Is this because the first megabyte is always identity mapped (the pointer to the page table should always be the same as the one for the kernel)?

Your boot page directory and paging setup do not fit together. As is, you have enabled PAE paging, but are still using the old structures. With PAE, each page table entry doubles in size, which reduces the number of entries to 512 per page, which introduces a third layer of paging on the top, and it changes the shift counts (Instead of a 32-bit address being 10 bits page directory offset, 10 bits page table offset, and 12 bits page offset, it is now 2 bits page directory pointer offset, 9 bits page directory offset, 9 bits page table offset, and 12 bits page offset).

I think that I just set up 4MB pages and not PAE, however I'm considering it. I've read something about. Before I thought it was ok to not implement it, but now I think it's good and useful, isn't it?

And unless you modify the paging structures later, the page directory you have won't work even without PAE. You are telling the CPU that the page table for the first 4MB can be fount at address 0, not the address you are using for it.

Should I map the addresses near eip so?

Recursive paging has been explained well enough. One problem with it is that it wastes one entry on the highest level paging structure you have. That isn't a problem in 32-bit paging without PAE, as there it is just 1/1024 of virtual space. It also isn't a problem with 64-bit paging with PAE, as there it is 1/512 of available virtual address space, and address space is virtually infinite. But 32-bit paging with PAE has a 4-entry page directory pointer at the top, so using recursive paging here wastes 1/4 of address space.

It's still a possibility. You are using C0000000 as kernel base address, so we can have PDP[2] = PDP. That means, the paging structure is available between addresses 0x80000000 and 0xBFFFFFFF. Ultimate self recursion is at 0x80402010. PDP[x] is available at 0x80402000 + (x*8). PD[x,y] is available at 0x80400000 + (x << 12) + (y << 3), for x != 2 (x == 2 is the recursion entry, so it's special). PT[x,y,z] is available at 0x80000000 + (x << 21) + (y << 12) + (z << 3), again, for x != 2. Access with x > 3 leads to undefined behavior.

What are you suggesting in here? I'm wasting 25% of the address space, is it sill worth it?

Finally I'm trying to enable 4kb paging, but it triple faults if I not turn on that bit before enable paging. I thought that it was a previous paging set up just to put the kernel on the higher half and then disable it. Then, if I'm not disabling it, I have to manage the BootPageDirectory mapping to make it works. I have tried something but it doesn't seem to change anything.

[neon]

Hi,

find a physical block that best-fits and return a pointer to that region of memory. Once I did this, I make a page setting it as present and to the frame (from 0 to 4MB). Then I add it to the page table. Should I map the page table before accessing it? Always "|=" it with 3?? And before it the page directory too?

You do need to map the page table and page directory before using it. When paging is enabled, all addresses are virtual so you can't access through any pointer that isn't mapped. This is what is causing the page fault -- you allocate a physical frame for the page table, but then your code accesses it without mapping it - thereby creating a page fault.

pt_entry_set_frame sets the physical address as part of the page table entry (that is, it maps the page.) pt_entry_pfn returns the physical address that is mapped to the page table entry. Please see the PTE format here. Basically they read and write the "4k aligned address" part of the page table entry. When you do pte |= 3 that sets the read/write bit and the present bit which enables the page. This field is the page frame number (pfn).

I mean, @neon wrote that I should maintain a memory region allocator or a PTE free list. Isn't that just like the one I use to keep the physical frames, but with virtual pages?

There are lots of ways to go about it -- basically, you just need a way to allocate free pages in the address space that you can map to frames. You only need it for a part of kernel space that you want to use as a "free memory pool" where you can allocate and free virtual pages that you can map to those page tables. Of course, with recursive paging you wouldn't need this for page tables - it is still useful for general memory management (i.e. creating a kernel heap.)

[linguofreak]

What are you suggesting in here? I'm wasting 25% of the address space, is it sill worth it?

Generally, yes. For your first operating system, you'll likely use 32-bits because a lot of the example code and tutorials you'll find are 32-bit, as 32-bit paging structures are somewhat simpler, and as modern computers tend to have gigabytes of memory available, you may not be able to utilize all your RAM due to address space limitations, but your first operating system (or any hobby operating system, in general) is not likely to be running application software that uses gigabytes of RAM at a time, so it's not likely to be relevant. By the time you're working an OS that is running such software, you'll likely be primarily, if not exclusively, writing for 64-bit systems, and thus will have a virtual address space that is much, much larger than the RAM available, and if you're not, you'll have developed the experience to have a good feel for the tradeoffs. But for your first forays into paging, don't worry about wasting virtual address space. (It was only in the latter part of the 32-bit era, once computers started having on the order of 1 or 2 GiB of RAM, that address space congestion was a problem even for 32-bit systems).

[eryjus]

@Xcp -- -- I promise it will get better. I'm laughing because I've been there, every bit as bad as you are and here I am answering questions about it. I could quote every one of your lines and respond, but I think there is a slightly bigger conversation here, so I want to take a step back. Let me preface this by saying that there are a lot of decisions you can make about exactly how you want to go about all of this, and the answers are in your own creativity. I will have different solutions than you will, but I will try to offer some examples. I will also try to expand more on @neon's 4 buckets.

Physical memory frames

First, you will want to know what kind of physical memory is available on your system at any given point in time. These are broken up into frames, or 4K chunks of memory. You have a stack to keep track of those. I use a bitmap. In either solution you are going to need some space allocated to keep track of the free frames. Some people will use the first bytes of the frames as the structure to insert into a linked list, but then you will need some method of reading and writing this data once a frame is freed.

At a high level, you will need an AllocFrame() and FreeFrame() operation. You might want to plan for an AllowFrameLow() for low memory. And you might consider AllocFrameRange() and FreeFrameRenge(). I am not sure of your overall design, but you may find use for the latter functions down the road and spending some time up front on how you would do that if you needed to will save you some trouble. Only the first 2 functions are essential at this early stage.

Virtual memory layout map

There is no coding involved here. This is the part of OS development which becomes a research project. Put pencil to paper and come up with an overall virtual memory layout design. This will have nothing to do with the physical memory -- at least not once you have completed initialization. You sound like you want your kernel to live in the upper virtual memory address space. That's fine. What is the address range? This also implies that the user code will live in the lower range. What is that range? Keep in mind that this is a plan and each process can have the same address range if they have different paging tables because they can have different cr3 values which will be replaced on a task swap. Let that sink in... it is a key concept.

This virtual memory map will become part of your OS plan. Take the time to document it and put is some place you can refer to it regularly. You will do so while you build out your kernel and get the rest of the system.

Now, yes, you can have a user process start at 0x100000 (1MB) and still have the kernel identity mapped to the same space. However, once your initialization is complete and you are fully established in upper memory you can remove the identity map for the kernel. You may need to access the frames in low memory, but you can also map that physical memory to somewhere in your kernel address space.

Page Table Manager

You are going to need some way to create and destroy the paging tables in your system. The hardware will refer to these from their physical memory addresses. But you will need some way to construct a Page Table and add it into the Page Directory. Backing each of these is a physical frame that you will allocate from your Physical Memory Manager. This is why the recursive mapping trick is so attractive: it allows the process to access the paging tables using the virtual memory address space rather than forcing the entire memory space to be identity mapped so you can find a page.

When you need to add a new Page Table, you can get a frame from the PMM and then using the Recursive Mapping address, add that into the Page Directory (setting the 'p' bit of course).

One of the tasks this Page Table Manager will also do is help you by copying the kernel pages into your user ones so that when you issue a system call the CPU has the code to execute in the current process's running virtual address space. This is as simple as taking your kernel Page Directory and finding the Page Directory Entries for the kernel space (and video buffer and mapped memory IO and... this is why the virtual memory map is so important) to the process's Page Directory in the same location. In this way you are re-using your existing frames in multiple address spaced -- but for the same reason (i.e. kernel is still kernel) -- but you do not have to re-construct new Page Tables for the kernel when you launch a new process.

You will need MapPageToFrame() and UnmapPage() functions for this. Once you unmap a page, you will need to determine if it is safe to release the frame it pointed to back the PMM. You may not want to if this is shared kernel space -- undesirable results will occur. Similarly, MapPageToFrame() will accept a frame number, not allocate one. This will give you the freedom to create shared memory.

Do yourself a favor and build a DumpPageTables() function to walk the Page Tables and dump the contents needed to get to a frame mapped to any given address. Dump that output somewhere useful. You will use that function a lot when debugging.

Kernel Heap

Yes, like any other program, your kernel will occasionally need to malloc() some memory. This will also be somewhere in your kernel space. You will start with a small amount at boot and then add more as you need it by calling your AllocFrame() function to get some physical memory and then your recursive mapping setup to add the page into the proper location of the proper Page Table. You will need to write a heap manager for this. Of course, you do not want to leak memory so you will need a free() function as well.

Initialization

The order that things happen can be difficult to get your head around as well. You will come to more than 1 chicken-and-egg situation. I recommend that you think about statically allocating many of your early initialization structures in the compiler rather than through any memory manager -- at least until you can properly put them in charge. This is particularly true for structures that do not need to be released back to the heap. Some things to think about (and this is not an exhaustive list):

* Your kernel will take up a number of frames which you want to make sure you do not allocate. You will need to identify them and let your PMM know what those are.
* You may or may not have GRUB load a number of additional modules for you as well (disk IO?) and you will need to be able to identify the frames that those take up.
* GDT/IDT/TSS all need space. But they can all also exist in the same physical frame if you want.
* Your initial paging table will need space and they need to be 4K-aligned. You can include them in the binary or you can allocate them and build them before you get paging fully implemented.
* Once you get to upper memory, some portions of the identify-mapped space may be able to be released sooner than others. When will depend on your design and your own decisions.

[nullplan]

I'm losing my mind because of this so please be nice with me...

BTDT, so I can relate.

Are pages mapped just "|=" with 3 (present and writable), right? Like... sorry but I'm blocked right now 0.0. I think that I did what you are describing but I was directly reserve a region from the virtual memory manager without passing by a kernel heap allocator. Should I add it?

Slow down a little. At the moment you are trying to enable paging. To that end, it is perfectly acceptable to use a temporary environment that gets fixed up for use with the kernel later when you're trying to actually manage paging.

I find a physical block that best-fits and return a pointer to that region of memory. Once I did this, I make a page setting it as present and to the frame (from 0 to 4MB). Then I add it to the page table. Should I map the page table before accessing it? Always "|=" it with 3?? And before it the page directory too? I don't know what I'm talking about at this point.

That is what the recursive paging hack is all about: You always have all the paging structures mapped, at constant addresses, so yes, mapping is just "set the value at that address to that value". So, if we return to the PAE example from my last post, and eliding any error handling for clarity:

Code: Select all

#define PTE_RECURSE 2
#define PTE(x, y, z) (*(uint64_t*)(0x80000000 | (x << 21) | (y << 12) | (z << 3)))
#define PF_PRESENT (1ull << 0)
#define PF_WRITABLE (1ull << 1)
#define PF_USER (1ull << 2)

uint64_t alloc_phys_page(void); /* have fun writing that one. */
void map_vaddr(uint32_t vaddr, uint64_t paddr, size_t len, uint64_t flags) {
  uint32_t al = (vaddr & 4095);
  len += al;
  vaddr -= al;
  paddr -= al;
  assert(!(paddr & 4095));
  len = (len + 4095) & -4096;
  while (len) {
    int pdpi = (vaddr >> 30) & 3;
    int pdi = (vaddr >> 21) & 0x1ff;
    int pti = (vaddr >> 12) & 0x1ff;
    assert(pdpi != PTE_RECURSE);
    if (!(PTE(PTE_RECURSE, PTE_RECURSE, pdpi) & PF_PRESENT))
      PTE(PTE_RECURSE, PTE_RECURSE, pdpi) = alloc_phys_page() | PF_PRESENT | PF_WRITABLE;
    if (!(PTE(PTE_RECURSE, pdpi, pdi) & PF_PRESENT))
      PTE(PTE_RECURSE, pdpi, pdi) = alloc_phys_page() | PF_PRESENT | PF_WRITABLE;
    PTE(pdpi, pdi, pti) = paddr | flags;
    asm("invlpg %0" : : "m"((char*)vaddr) : "memory");
    vaddr += 4096;
    paddr += 4096;
    len -= 4096;
  }
}

The flags argument is 64 bits to support the NX bit, for which you need PAE, by the way. And the invlpg is only there to support remapping an area. Still, the code might cause spurious page faults, which you might need to handle (that is, you will get a page fault and then notice that the address is actually mapped in, so you just return from the page fault handler).

Here you're talking about the process A that starts from 0x00100000. Is this because the first megabyte is always identity mapped (the pointer to the page table should always be the same as the one for the kernel)?

Nope. You need the identity map only to turn paging on and jump to the kernel (higher half). Then you can remove it. You only ever need it again for SMP trampolines (though the other processors have their own CR3 and thus can have their own paging structures) or to turn paging off again, should you wish to shutdown with APM. Most BIOSes these days don't support APM, tho.

I think that I just set up 4MB pages and not PAE, however I'm considering it. I've read something about. Before I thought it was ok to not implement it, but now I think it's good and useful, isn't it?

You are entirely correct. 0x10 is bit 4, which is the PSE bit. PAE is bit 5, which would be 0x20.

PSE defines bit 7 of the page directory entry to be the page size bit. If set, the page directory defines a 4MB translation (else it's a normal 4kB translation). And it appears (I hadn't read that part of the handbook yet) that AMD extended PSE paging to allow for a 40-bit physical address space when using 4MB paging. So, as long as you are OK with the coarse-grained paging, there is hardly a need for PAE, now.

PAE is useful if you ever decide to go 64-bit, or you want more than 4GB of physical memory without giving up 4kB pages. Or (I don't know about this) maybe AMD's extension to the 4MB page directory entry is not portable to Intel CPUs.

Should I map the addresses near eip so?

Sorry, I was confused. Your code should actually work out. It's just a bit of a hack. The way it was written, you just add 0xc0000000 to every address in your kernel and are done. Meanwhile, I have my entire kernel linked to the -2GB line, and the code which initializes paging does so by parsing the ELF header. My loader also does not depend on the physical load address of the kernel. I have to have something like that since multiboot 1 does ot support 64-bit files.

But for starters your code should work.

What are you suggesting in here? I'm wasting 25% of the address space, is it sill worth it?

Depends. What else would you have put there? Remember, we are only talking about virtual space here, you're not wasting any RAM. The kernel is loaded to 0xc0000000, userspace will likely not be able to use memory above 0x80000000 anyway, so you might as well put the recursive map there. There is more than enough space for kernel vspace left after the end of the kernel. And virtual memory is a ressource that is wasted if unused. A glass half full is a glass 50% larger than it needs to be!

Finally I'm trying to enable 4kb paging, but it triple faults if I not turn on that bit before enable paging. I thought that it was a previous paging set up just to put the kernel on the higher half and then disable it. Then, if I'm not disabling it, I have to manage the BootPageDirectory mapping to make it works. I have tried something but it doesn't seem to change anything.

And all that just from me mixing up the bits in CR4.

No actually, if you put back the code you had, then your page directory needs to have a 4MB page at physical address 0 right at the start, which it does have. It needs the same entry at index 768. That is, if your kernel is below 3MB in size (it gets loaded to 1MB, right? The end of the kernel must not exceed the 4MB line). So that is:

Code: Select all

.p2align 12
BootPD: .int 0x83 /* present writable supervisor 4MB page at 0 */
.fill 767, 4, 0
.int 0x83
.fill 254, 4, 0
.int BootPD | 3 

That should do it. Maps 4MB from 0 to 0 and from 0xc0000000 to 0. And puts a recursive mapping right at the end (conflicts with Xen but who cares). Works so long as the kernel is small enough (its end must be before the 4MB line). If it gets larger, just extend the second mapping (.int 0x00400083; .int 0x00800083; .int 0x00c00083; etc.) and reduce the second repeat count accordingly.