Implement Your Own Operating System(week 07)

In this article, I’ll explain to you about Virtual memory and paging. First of all, shall we see what is the memory? if you didn’t study my previous articles, I recommend you to refer to them, before coming up with this article.

what is virtual memory?

A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that’s set up to emulate the computer’s RAM.

The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using the disk. Second, it allows us to have memory protection because each virtual address is translated to a physical address.

why we don’t use just segmentation for virtual memory?

Each user-mode process would get its own segment, with the base address and limit properly set up. This way no process can see the memory of another process. A problem with this is that the physical memory for a process needs to be contiguous. Either we need to know in advance how much memory the program will require, or we can move the memory segments to places where they can grow when the limit is reached. Paging solves both these problems.

Paging

Paging is a storage mechanism that allows OS to retrieve processes from the secondary storage into the main memory in the form of pages. In the Paging method, the main memory is divided into small fixed-size blocks of physical memory, which are called 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 is used for faster access to data, and it is a logical concept.

Paging in x86

Each process normally has a different set of page mappings, so that virtual(linear) memory spaces are independent of each other. In the x86 architecture (32-bit) pages are fixed at 4KB in size. Each page has a corresponding descriptor word, which tells the processor which frame it is mapped to.

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 (4 bytes), 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.

Enabling Paging

Paging is enabled by first writing the address of a page directory to cr3 and then setting bit 31 of cr0 to 1. To use 4 MB pages, set the PSE bit of cr4. The following assembly code shows an example:

Paging and the Kernel

Under this topic, I try to explain how paging affects the OS kernel.

Placing the Kernel at 0xC0000000

One of the main reasons for using virtual memory is to let user programs act as though they were loaded at address 0. Most executable formats assume they are loaded at address 0, so we would like the operating system to get out of the way and live in the higher reaches of memory, let’s say address 0xC0000000.To start with, 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. Furthermore, 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.

Higher-half Linker Script

We can modify the first linker script(The first article of this series) to implement this:

Entering the Higher Half

assembly code that doesn’t use relative jumps or relative memory addressing must be used to do the following:

• Set up a page table.
• Add identity mapping for the first 4 MB of the virtual address space.
• Add an entry for 0xC0100000 that maps to 0x0010000.

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:

Virtual Memory Through Paging

In computer operating systems, memory paging is a memory management scheme by which a computer stores and retrieves data from secondary storage[a] for use in main memory. In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. Paging is an important part of virtual memory implementations in modern operating systems, using secondary storage to let programs exceed the size of available physical memory.

Paging enables two things that are good for virtual memory. First, it allows for fine-grained access control to memory. You can mark pages as read-only, read-write, only for PL0, etc. Second, 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 not require more than two actual pages.

I hope now you have a good idea about virtual memory and paging. See you in the next week article.

Reference: Helin, E., & Renberg, A. (2015). The little book about OS development

Thank You For Reading…

Kasun Madhumal