Operating System : Paging
This article is part of a series of articles explaining the development of an x86 Operating System. You can find all of the previous articles at the end.
In one of my previous articles, I explained something called Memory Segmentation. If you seem confused you can go back to that article to know all about integrating segmentation into the memory.
This article will contain a way to organize memory as well; called Paging. Now you might be thinking, “Didn’t we already organized the memory of our OS two articles ago? Why do we need to mess with that again?”
So first let’s talk about why we need paging in our OS?
Why Use Paging?
Now paging isn’t mandatory (although Linux uses it) and you can just use segmentation. Each user-mode process will be quite happy with its own segment, along with the base address and limit properly set up. All of them will have the privacy of not knowing the memory of other processes. A problem is process won’t be contiguous.
In order to solve this issue, we either need to beforehand the total amount of memory the program needs or we can transfer the memory segments to places where they can grow when the limit is reached (which can result in external fragmentation.)
To get an idea of Memory fragmentation, check out this diagram of Segmentation used in physical memory below.
Notice how there’s a lot of small segments with gaps in between. Sometimes larger segments might not even be allowed in the memory at all. Here the segments can be “pushed together” to make room for that larger segments.
But the ideal way to get around these issues is by using Paging.
Virtual Memory Through Paging
In paging, the memory is split up into small, equal-sized sections, which we call pages(or page frames). One process can occupy multiple pages. But these pages don’t need to be contiguous.
Each process has its own view of the memory, known as logical memory. So they will get the impression that the available memory range is 0x00000000 - 0xFFFFFFFF even though the actual size of the memory might be much less.
Segmentation turns a logical address into a linear address. Then Paging translates them onto the physical address space. Here it determines access rights and how the memory should be cached as well.
The OS maintains a page table with information about which logical location maps to which physical location. Where different pages of a process are located in physical memory. To see how different pages of a process are mapped in physical memory, check out this diagram of Paging used in physical memory below.
Shown above is the simplest kind of paging there is, called identity paging. It’s when we map each virtual address onto the same physical address. This can be done at compile time by creating a page directory where each entry points to its corresponding 4 MB frame.
Paging in x86
To understand paging you need to know what is a Page Directory, a Page Table, and a Page Frame.
Page Directory — A table in memory which the MMU uses to find the page tables.
Each index in the Page Directory is a pointer to a Page table. It can contain references to 1024 page tables.
So the Page Directory Entity structure would look something like this,
Page Table — A table in memory that describes how the MMU should translate a certain range of addresses.
Each index in a Page Table contains the physical memory address to which a certain page should be mapped. It can point to 1024 sections of physical memory called page frames (PF).
So the Page Entity structure would look something like this,
Page Frame —A fixed-length contiguous block of physical memory into which memory pages are mapped. Each page frame is 4096 byte large.
The 32-bit linear address derived from the selector and offset is divided into three fields. The first 10 bits are used as the index of the page directory. The page directory entry points to a page table. The next 10 bits of the linear address provide the index of the table. The page table entry provides the base address of a 4 KB page in physical memory called a page frame. The last 12 bits of the original linear address provide the page frame offset. Each task has its own page directory, which is pointed to by the CR3 processor control register.
The changing of linear addresses to physical addresses is shown in the figure below.
Enabling Paging
Loading Page Directory
The first step is to tell the processor where to find our page directory by putting it’s address into the CR3 register. Because C code cannot directly access the computer’s registers, we will need to use assembly code to access CR3. The following assembly is written for NASM. ( If you use a different assembler then you will need to translate between this assembly format and the format supported by your assembler.)
Enabling Paging
Enabling paging is actually very simple. All that is needed is to load CR3 with the address of the page directory and to set the paging (PG) and protection (PE) bits of CR0 to 1.
Handling Page Faults
A Page Fault is just an indication from the hardware that the required Virtual address is not mapped in the page table.
The page could simply have been swapped out. In that case the OS can service the page fault and the execution can continue as if nothing happened.
If the CPU find the page actually doens’t exist, it fires a page-not-present exception. The upper 10 bits specify the page directory entry (PDE) and the middle 10 bits specify the page table entry (PTE). First check the PDE and see if it’s present bit is set, if not setup a page table and point the PDE to the base address of the page table, set the present bit and iretd. If the PDE is present then the present bit of the PTE will be cleared. Then you’ll need to map some physical memory to the page table, set the present bit and then iretd to continue processing.
Summary
Paging is optional, and some operating systems do not make use of it. But if we want to be able to have processes running at different privilege levels paging is the neatest way to do it.
We only talked about implementing the simplest kind of paging, called identity paging. If you can successfully run your OS using identity paging then you can try implementing a more advanced paging setup.
It’s quite simple to configure paging into your OS. You can get the complete code for paging from my github below.
Hope to see you in the next article as well!
Thank you!
Reference: Helin, E., & Renberg, A. (2015). The little book about OS development
