Develop Your Own x86 Operating System(OS) #8
Introduction to Virtual Memory and Paging
Previous article onwards we are walking in the path to execute a program in user mode. If you haven’t gone through the previous article on road to user mode, please read it from here to understand the process going on, in this article.
Through this article let’s have a quick overview on virtual memory and dive deep to learn about paging, a method of organizing the memory.
Physical memory is the computer’s random access memory (RAM), typically contained in DIMM cards attached to the computer’s motherboard. Virtual memory is a portion of an HDD or SSD that is reserved to emulate RAM. The memory management unit(MMU) serves up virtual memory from disk to the CPU to reduce the workload on physical memory.
Introduction to Virtual Memory
In computing, virtual memory is a memory management technique which provides an abstraction of physical memory available on a given machine, creating the illusion to users of a very large main memory. The purpose of virtual memory is generally to simplify application development, to let processes address more memory than what is actually physically present in the machine and to stop applications messing with the kernel or other applications’ memory due to security.
In the x86 architecture, virtual memory can be accomplished in two ways: segmentation and paging. Paging is a computer memory management function that presents storage locations to the computer’s CPU as additional memory, called virtual memory. Segmentation is a virtual process that creates variable-sized address spaces in computer storage for related data, called segments.
Paging is by far the most common and versatile technique, but some use of segmentation is still needed to allow for a program to execute under different privilege levels. So, let’s run through these two ways separately.
Virtual Memory Through Segmentation
We have discussed about memory management through segmentation in details through a previous article(#5). Segmentation can be used entirely for virtual memory, ignoring paging completely. If we continue this way, no process can see the memory of another process and each user mode process would get its own segment, with base address and limit properly set up. It seems fine and better to take into action, but the problem prevailing in this method is that, the physical memory for a process needs to be contiguous. Moreover, we must know in advance how much memory the program will require (which is not pragmatic), or we can move the memory segments to places where they can grow when the limit is reached (which is expensive and causes fragmentation).
Both the methods mentioned above that arises with using segmentation for virtual memory, are troublesome. So, it is better if we can follow another way for virtual memory that avoids these problems. Amazingly, Paging solves both of these problems.
Prior to discussion on virtual memory through paging, let’s see what is paging.
Paging
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. It is the process of translating linear addresses converted in segmentation, onto the physical address space and determining access rights and the way memory should be cached.
In paging, secondary memory and main memory are divided into equal fixed size partitions. The partitions of secondary memory (logical memory) are called as pages while the partitions of main memory (physical memory) are called as frames. The size of a frame should be kept the same as that of a page to have maximum utilization of the main memory and to avoid external fragmentation.
Paging in x86
Paging is achieved through the use of the Memory Management Unit (MMU). On the x86, the MMU maps memory through a series of tables, two to be exact. They are the paging directory (PD), and the paging table (PT).
Page directory (PD) can contain references to 1024 page tables (PT), each of which can point to 1024 sections of physical memory called page frames (PF).
A page frame is the smallest fixed-length contiguous block of physical memory into which memory pages are mapped by the operating system. Each page frame is 4096 byte large.
The topmost paging structure is the page directory. It is essentially an array of page directory entries that take the following form.
Page Table is a data structure used by the virtual memory system to store the mapping between logical addresses and physical addresses. It converts the page number of the logical address to the frame number of the physical address. In each page table there are also 1024 entries. These are called page table entries, and are similar to page directory entries.
The bits U/S determines what privilege levels can access this page (PL0 or PL3), and R/W bits makes the memory in the page read-write(set) or read-only(unset). 4 bytes times 1024 equals 4096 bytes, so a page directory and page table both fit in a page frame themselves.
Note:
An instruction that can be used when updating a PD or PT is invlpg. It invalidates the Translation Lookaside Buffer (TLB) entry for a virtual address. The TLB is a cache for translated addresses, mapping physical addresses corresponding to virtual addresses. This instruction is only required if we have to change a PDE or PTE that was previously mapped to something else. If the PDE or PTE had previously been marked as absent, executing invlpg instruction is unnecessary. Changing the value of cr3 will cause all entries in the TLB to be invalidated.
Invalidating a TLB entry can be presented as below:
; invalidate any TLB references to virtual address 0
invlpg [0]In a virtual (linear) address, the highest 10 bits specifies the offset of a page directory entry (PDE) in the current PD, the next 10 bits the offset of a page table entry (PTE) within the page table pointed to by that PDE. The lowest 12 bits in the address is the offset within the page frame to be addressed.
All page directories, page tables and page frames need to be aligned on 4096 byte addresses. This makes it possible to address a PD, PT or PF with just the highest 20 bits of a 32 bit address, since the lowest 12 need to be zero.
The translation of linear addresses to physical addresses (the process of paging) is shown in the figure below:
The linear address gets translated to a physical address by the MMU and the page table. If the virtual address isn’t mapped to a physical address, the CPU will raise a page fault interrupt.
Pages are normally 4096 bytes, but it is also possible to use 4 MB pages. Then a PDE points directly to a 4 MB page frame, which needs to be aligned on a 4 MB address boundary. In this way also the address translation is almost the same as in the figure, except the page table step. It is possible to mix 4 MB and 4 KB pages.
Identity Paging
This is the simplest kind of paging. Identity Paging, Identity Mapped Paging and 1:1 Paging are terms often used for mapping virtual addresses to physical addresses that have the same value. This means that if paging is enabled with identity paging, 0xb8000 is 0xb8000. Identity paging can be done at compile time by creating a page directory where each entry points to its corresponding 4 MB frame. In NASM this can be done with macros and commands (% rep, times and dd). And also this can be done at run-time by using ordinary assembly code instructions.
Enabling Paging
The 20 bits pointing to the current PDT is stored in the cr3 register and the lower 12 bits of cr3 are used for configuration.
Enabling paging is done by first writing the address of a page directory to cr3 and then setting bit 31, the PG “paging-enable” bit of cr0 to 1. To use 4 MB pages, set the PSE bit (Page Size Extensions, bit 4) of cr4.
C code cannot directly access the registers, so assembly code is used to access CR3.The following assembly code shows how this can be done:
Create page_enable.s file in your working directory and save the above code in it.
Don’t forget to put page_enable.o in the OBJECT variable of Makefile.
It is better to run your OS using identity paging before trying to implement a more advanced paging setup, as it can be hard to debug a malfunctioning page table set up through assembly code.
Note that all addresses within the page directory, page tables and in cr3 should be physical addresses to the structures not virtual.
Paging and the Kernel
Now let’s see how this paging effects the heart of OS, the Kernel.
Generally, in the linking process, the linker assumes that the code will be loaded into the memory position 0x00000000. Therefore, when resolving absolute references, 0x00000000 will be the base address for calculating the exact position. But if the kernel is mapped on the beginning of the virtual address space (0x00000000, “Size of kernel”), the user mode process cannot be loaded at virtual address 0x00000000. Therefore, the assumption from the linker that the user mode process is loaded into memory at position 0x00000000 becomes wrong. Although this can be corrected by using a linker script which tells the linker to assume a different starting address, it will be unmanageable for the users of the operating system.
That being the case, the kernel should be placed at a very high virtual memory address, for example 0xC0000000(3 GB). Now the only way that a user mode process can conflict with the kernel is it’s being 3 GB large, but it is not a common scenario.
When the kernel uses virtual addresses at 3 GB and above it is called a higher-half kernel. Selecting the correct address to place the kernel depends on how much virtual memory should be available for the kernel and how much virtual memory should be available for the process. If the user mode process is larger than 3 GB, some pages will be needed to swap out by the kernel. But, we are not discussing about swapping pages here.
Placing the Kernel at 0xC0000000
As taken in the example above, now let’s see how we can place the Kernel at 0xC0000000.
At first, place the kernel at oxC0100000 than 0xC0000000. This way it is possible to map (0x00000000, 0x00100000) to (0xC0000000, 0xC0100000). This way, the entire range (0x00000000, “Size of kernel”) of memory is mapped to the range (0xC0000000, 0xC0000000 + "“Size of kernel”).
When the linker resolves all absolute references in the kernel, it will make the assumption that the kernel is loaded at physical memory location 0x00100000 not at 0x00000000 as we used relocation in the linker script. We want the jumps to be resolved using 0xC0100000 as base address, otherwise a kernel jump will jump straight into the user mode process code as user mode process is loaded at virtual memory 0x00000000.
We want kernel to be loaded at the physical address 0x00100000. So, this cannot be done by simply telling the linker to assume that the kernel loads at 0xC0100000. There is BIOS and GRUB code loaded below 1 MB and so it is good to load the kernel at 1 MB. Furthermore, the computer might not have 3 GB of physical memory so, loading the the kernel at 0xC0100000 is not a good idea either. This problem can be given a solution using both relocation (.=0xC0100000) and the AT instruction in the linker script. Relocation specifies that non-relative memory-references should use the relocation address as base in address calculations. AT instruction specifies the place where the kernel should be loaded into memory. Relocation is done at link time by GNU ld, the load address specified by AT is handled by GRUB when loading the kernel, and is part of the ELF format.
Higher-half Linker Script
For this we have to modify the link.ld to implement this. The following code can be used:
When GRUB jumps to the kernel code, there will be no paging table. Therefore, all references to 0xC0100000 + x won’t be mapped to the correct physical address, and will therefore cause a general protection exception or the computer will just crash.
Therefore, using the C language we have to set up a page table and page directory.
Virtual Memory Through Paging
Paging is an important part of virtual memory implementations in modern operating systems. It is the most common technique used in x86 to enable virtual memory. Virtual memory through paging means that each process will have the feeling that the available memory range is 0x00000000–0xFFFFFFFF although the actual size of the memory might be much less than that. This also means that when a process addresses a byte of memory it will use a virtual (linear) address instead of physical one.
Paging enables two things that are good for virtual memory.
<> It allows for fine access control to memory (Pages can be marked as read-only, read-write, only for PL0 etc.).
<>It creates the illusion of contiguous memory. User mode processes, and the kernel, can access memory as if it were contiguous, and the contiguous memory can be extended without moving data around in memory.
Paging is optional, and some operating systems do not make use of it. But if we want to have processes running at different privilege levels, paging is the best way to do it.
Now, you have learnt many of theories related to paging. It’s time use them practically in order to initiate paging using the C language. Let’s create files needed for this one by one.
First let’s create common.h, which is a simple header file. Save the file with the following code:
Now create common.c file and save this code in it:
As the next step create kheap.h header file for the heap of kernel with the below code:
and kheap.c file with the code given below:
It’s time for enabling paging using C language. For this we have to first create paging.h file that contains function declarations and Page Directory Entity structure as well as Page Table Entity structure. Following code can be used for paging.h:
Using the paging.c file we can specify function definitions. The following code can be used for it:
Again it’s time to update your Makefile with .o files:
Now the kmain.c file should be updated including only these two highlighted lines:
We created files for interrupt handling in a previous article (#6). In this step we have to update some of those files to obtain an interrupt handler for page faults.
Now, boot your OS using the “make run” command, if the process end successfully you have integrated paging.
Now you have learnt about virtual memory and paging in x86. In the next article you will be able to study about page frame allocation.
References
Hope you understand what is paging and virtual memory. Let’s meet with the next article of Develop Your Own x86 Operating System(OS) series. Thank you so much for reading!!!!!!!!!!
Isuruni Rathnayaka
