Paging Architecture in xv6 Operating System

xv6 paging architecture

It is interesting to learn about how xv6 operating system manages it's memory address space using virtual and physical addresses. Since it is a little bit complicated functionality, I decided to write a little note on how paging is used in xv6 to manage memory. There is a separate chapter called Page Tables in the xv6 book provided by MIT. At the moment I write this, the latest version of this book is revision 8. That chapter in the book clearly describe the paging functionality with an illustration in Figure 2-1. To make my own description clear, I'm using an edited version of that figure in this blog post. In that figure, I have added a number sequence with the yellow color closer to the arrows as an index for my description which comes shortly.

As we already know, each process running inside xv6 has an address space where every reference to a memory location is done using a virtual memory address. That means, there are no memory locations with such addresses in the physical memory. What happens is that the operating system with the help of a hardware component called MMU (memory management unit), is mapping those virtual memory addresses with real memory address in the physical memory. Such a functionality is achieved by breaking the physical memory into segments which we call Pages. Each process running inside xv6 has an address space which is mapped to pages in physical memory address space via MMU. Whenever a running process refers to a virtual memory address, the processor should go through a sequence of actions to find the real physical memory location which represent that virtual memory address.

Here's how this is organized. The xv6 has set up virtual to physical memory address resolution in two stages. First of all, there's something called Page directory. There's only one page directory in xv6 with 1024 entries (rows). Each entry in the page directory contains the index number of a page table. That means, there are 1024 page tables in xv6. The above figure illustrates this situation. It is important to know the composition of a virtual memory address. A virtual memory address has a length of 32 bits and and it can be considered as three components. Those are namely, a 10 bit long component called Dir, another 10 bit component called Table and finally a 12 bit long component called Offset. When such a virtual memory address is present, following list explains how it is converted to the physical address. Note that the number in the below list corresponds to the yellow colored arrow indexes in the above figure.

(1) The 10 bit long Dir part of the virtual address can have a value starting from 0 to 2^10 (ie-1024). This value points to the specific entry in the 1024 entries long page directory.

(2) The value contained in that specific page directory entry has a number which is the index number of a specific page table. That means we can find the correct page table using that value in the page table entry. It is also evident that, we can have up to 1024 unique page tables since there are 1024 entries in the page directory.

(3) After finding the correct page table, we have to look at the second part of the virtual address to proceed. This second part of the virtual address called Table has a 10 bit long value and that means it can represent a value from 0 to 2^10 (1024). This value points to a specific entry in the selected page table. Inside this page table entry, we can find a 20 bit long value called PPN (physical page number). Moreover, it hints us that a page table has 1024 entries.

(4) The value contained in the selected page table entry called PPN is what we want. This value is the first 20 bits of the physical address.

(5) Now we have found the first 20 bits of the physical memory address which should have 32 bits. That means we need to find 12 more bits of the physical address. But actually, the Offset segment which had a 12 bit value in the virtual address is exactly the same value which is in the last 12 bits of the physical address. So, we can directly take that value.

That's how the system converts a given virtual memory address to a physical memory address. Page directory and page tables are stored in the physical memory and the processor automatically converts from virtual to physical addresses using these data structures and with the help of MMU hardware.