Paging

Hi, this is a bit of a work in progress...

Paging is a process, usually implemented inside the CPU that allows you to 'virtualize' the memory that your OS makes available to the rest of your OS and to user level applications.

Virtualize?

How can you virtualize memory? That's a good question. What it means, essentially, is that your applications can access memory in the way that they want to, assume a consistent loading location and obtain contiguous memory addresses from the OS despite the fact that the 'real' or 'physical' location of their data is somewhere completely different.

Before we look at the implementation of paging, let's consider a scenario from your application. You need 128KiB of space to use as a buffer for some communication. You ask the OS to allocate you some and you get a pointer back. Great, so what's with all the virtualization? Well, the address to which the newly returned pointer points, is called a virtual address. When you access that memory location a part of the CPU called the Memory Management Unit or MMU converts that 'virtual' address into a 'physical' address where it can go find the data. It might be that the first 4KiB of data in your 128KiB block lives far away from the second 4KiB block, but that's ok, because, you'll never know. The MMU allows you to address each block as if they sit next to each other, only when you access it, does the MMU need to figure our where to actually look. This process is known as memory address translation.

Address Translation

When thinking about writing our OS, however, we need to provide the MMU with all the details it needs to make the translation from virtual to physical address, that's our job. So what does the MMU do during this translation?

The translation uses a two-step process involving two intermediary tables. The first table is known as a page directory and the second a page table. The MMU splits the virtual address into 3 parts, the top 10 bits, the next 10 bits and the final 12 bits (32 bit assumed). The first part is used to access the first table and finds the location of the second table. The second part is used to access the second table and return the physical address of a 4KiB page of physical memory. The third part is then added to this physical address (root) to exactly locate the memory location we want.

The virtual address is first shifted right 22 times. leaving the top 10 bits, and added to the physical address of the start of the first table that is held in register CR3. In effect, this indexes us into the table between 0 and 1023. At this index it will find a 4byte entry. This entry contains a variety of information, but it also contains a pointer to the physical address of the second table. The middle 10 bits, right shifted 12 times is then added to this base address and another 4byte entry located. This entry is similar and ultimately points to a physical address on the system where the 'real' data can be found.

As an OS writer, we need to maintain these tables and flags to ensure proper allocation and memory addressing.

More Memory than Installed

One of the benefits of using this approach is that we can translate 4GiB of addresses, regardless of how much physical RAM is installed in the machine. We can fill the tables but mark the entry in the second table as not present. If the application that requested the memory never attempts to access that address, we have lost nothing except for the overhead of allocating the page tables. If they do, then we can dynamically allocate the physical memory that we do have as needed.

This also allows us to reuse physical addresses by taking a page of memory away from a different process and giving it to another. We can move the data in that location to secondary storage such as a disk, mark the page as not present and assign the physical address to the new process. 

PDE - Page Directory Entry

; present       (0)       -------- -------1
; read/write    (1)       -------- ------1- (1=writeable)
; user/system   (2)       -------- -----0-- (1=user)
; write through (3)       -------- ----0---
; cache disabl. (4)       -------- ---0----
; accessed      (5)       -------- --0-----
; not used      (6)       -------- -0------
; size (page)   (7)       -------- 0------- (0=4kb)
; ignored       (8)       -------0 --------
; user defined  (9-11)    ----000- --------

PTE - Page Table Entry

; present       (0)       -------- -------1
; read/write    (1)       -------- ------1- (1=writeable)
; user/system   (2)       -------- -----1-- (1=user)
; write thru    (3)       -------- ----1---
; cache disabl. (4)       -------- ---1----
; accessed      (5)       -------- --1-----
; dirty         (6)       -------- -1------ (1=dirty)
; not used      (7)       -------- 1-------
; global        (8)       -------1 --------
; user defined  (9-11)    ----111- -------- (the OS can use these 3 bits for whatever it pleases)

Inside the MMU

The MMU decodes an address by first using the 10 most significant bits as an index into the Page Directory. (Since each table entry is 4 bytes the index value is 1/4 of the size of the table in bytes.) A 4Kb page contains 1024 4 byte entries. This is covered by the 10 bits.
The entry that is found at this location provides the address of the Page Table that is used in the next part. The second 10 bits are used as an index into the Page Table which gives the physical address of the page where the data is actually found. The final 12 bits are now the index to the exact byte. Since we now need to resolve to the byte (not the 4 byte entry) we need the extra 2 bits.

0000 0000 | 00-- ---- | ---- ---- | ---- ----

  Page Directory index

---- ---- | --00 0000 | 0000 ---- | ---- ----

 Page Table index

---- ---- | ---- ---- | ---- 0000 | 0000 0000

 Page offset

This breaks down as follows:

• Bit shift the virtual address 22 bits to the right, leaving the top 10 bits, and add to the address of the Page Directory (held in CR3). This is referred to as indexing into the page directory.
• This provides the MMU with the physical address of the Page Table for this particular 4MiB slice.