How To Build An Operating System: Virtual Memory and Paging- Part 07
This is the seventh article of this building an own operating system article series. If you didn’t read the first six articles in this series, I recommend you to read those articles first.
Virtual Memory
Virtual Memory is a storage scheme that provides users the illusion of having a very big main memory. This is done by treating a part of secondary memory as the main memory. In this technique, the user can load the bigger size processes than the available main memory by having the illusion that the memory is available to load the process. Instead of loading one big process in the main memory, the OS loads the different parts of more than one process in the main memory. By doing this, the degree of multiprogramming will be increased and CPU utilization will be increased.
Advantages of Virtual Memory
- It allows users to run more applications at a time.
- Users can run a large application with less RAM.
- Users can fit many large programs into smaller programs.
- A multiprogramming environment can be easily implemented.
- Data should be read from the disk at the time when required.
- Common data can be shared easily between memory.
Paging is the most common method to accomplish virtual memory. Segmentation is also used in some scenarios. Paging and page frame allocation deals with memory management in an operating system.
Paging
Paging is a memory management technique in which the memory is divided into fixed-size pages. Paging is used for faster access to data. When a program needs a page, it is available in the main memory as the operating system copies a certain number of pages from your storage device to the main memory. Paging allows the physical address space of a process to be noncontiguous. Data is retrieved from storage media by OS, in the same sized blocks called pages. Paging allows the physical address space of the process to be non-contiguous. The whole program had to fit into storage contiguously.
Paging is to deal with external fragmentation problems. This is to allow the logical address space of a process to be noncontiguous, which makes the process to be allocated physical memory.
Paging in x86
Paging in x86 consists of a page directory that can contain references to 1024 page tables, each of which can point to 1024 sections of physical memory called page frames. Each page frame is 4096 bytes large. In a virtual address, the highest 10 bits specifies the offset of a page directory entry in the current PDT, 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 PDT, PT, or PF with just the highest 20 bits of a 32-bit address since the lowest 12 need to be zero. The PDE and PTE structure is very similar to each other: 32 bits, where the highest 20 bits point to a PTE or PF, and the lowest 12 bits control access rights and other configurations. 4 bytes times 1024 equals 4096 bytes, so a page directory and page table both fit in a page frame themselves.
The translation of linear addresses to physical addresses is described in the figure below.
While pages are normally 4096 bytes, it is also possible to use 4 MB pages. A PDE then points directly to a 4 MB page frame, which needs to be aligned on a 4 MB address boundary. The address translation is almost the same as in the figure, with just the page table step removed. It is possible to mix 4 MB and 4 KB pages.
The 20 bits pointing to the current PDT is stored in the register cr3. The lower 12 bits of cr3 are used for configuration.
Identity Paging
Identity paging is the simplest kind of paging. When we map each virtual address onto the same physical address it is called identity paging. This 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). It can also be done at run-time by using ordinary assembly code instructions.
Enabling Paging
Paging is enabled 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.
The following assembly code shows an example:
Paging and the Kernel
We want the kernel to be part of the user-mode process’ address space. During system calls, we don’t have to change any paging structures to get access to the kernel’s code and data. The kernel pages will require privilege level 0 for access, to prevent a user process from reading or writing kernel memory.
Placing the Kernel at 0xC0000000
The kernel should be placed at a very high virtual memory address, for example 0xC0000000 (3 GB). The user-mode process is not likely to be 3 GB large, which is now the only way that it can conflict with the kernel. When the kernel uses virtual addresses at 3 GB and above it is called a higher-half kernel. The kernel can be placed at any address higher than 0 to get the same benefits. If the user-mode process is larger than 3 GB, some pages will need to be swapped out by the kernel. We won't be discussing swapping pages in this article series.
It is better to place the kernel at 0xC0100000 than 0xC0000000, since this makes it 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").
The reason for having the kernel loaded at 1 MB is because it can’t be loaded at 0x00000000, since there is BIOS and GRUB code loaded below 1 MB. We cannot assume that we can load the kernel at 0xC0100000, since the machine might not have 3 GB of physical memory.
This can be solved by 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 the base in address calculations. AT specifies 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 shows an example:
Entering the Higher Half
When GRUB jumps to the kernel code, there is 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 (GPE) at the very best, otherwise if the computer has more than 3 GB of memory the computer will just crash.
If we skip the identity mapping for the first 4 MB, the CPU would generate a page fault immediately after paging was enabled when trying to fetch the next instruction from memory. After the table has been created, a jump can be done to a label to make eip point to a virtual address in the higher half.
The frame buffer is located at 0x000B8000, but since there is no entry in the page table for the address 0x000B8000 any longer, the address 0xC00B8000 must be used, since the virtual address 0xC0000000 maps to the physical address 0x00000000. Creating a higher-half kernel mapped in as 4 KB pages save memory but are harder to set up. Memory for the page directory and one-page table can be reserved in the .data section, but one needs to configure the mappings from virtual to physical addresses at run-time. The size of the kernel can be determined by exporting labels from the linker script.
Virtual Memory Through Paging
Paging enables allows for fine-grained access control to memory. and 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 the need to move data around in memory. We can also allow the user-mode programs access to all memory below 3 GB, but unless they actually use it, we don’t have to assign page frames to the pages. This allows processes to have code located near 0x00000000 and the stack at just below 0xC0000000, and still does not require more than two actual pages.
This is the end of this week’s article. See you in the next one.
Thanks for reading!.
References,
