What is paging exactly? OSDEV

0

I am trying to write my own operating system and I came to the point where I need to set up paging. I wrote some code that seems to be working but I realized I don't understand how paging works. Now I'll try to explain how I understood things and I will have some questions!

So as far as I understood paging is a way of mapping addresses to other addresses so that each application can see a full address space(?). There is something called a page directory which stores 1024 entries of 4 bytes each containing a pointer to a page table which also has 1024 entries. Each entry of a page table has a pointer that points to the start of the physical address block of 4 KiB. which means 4096 bytes * 1024 entries in the page table * 1024 entries in the page directory = 4 GiB of Ram that can be mapped. For example I can load an application to 0x80000000 and map that address to 0x00000000 and the app will see that its address starts from 0x00000000.

Questions:

  1. Does each application have their own page directory or is there one page directory, how does applications access the pages and what do they do exactly?
  2. How is an application supposed to see the full address space if they are given 4 KiB block of space or one page?
  3. How do you write the pages to the hard drive?
  4. How are we supposed to allocate pages for applications to use?
x86
paging
virtual-memory
osdev
page-tables
asked on Stack Overflow Apr 10, 2021 by Özgür Güzeldereli • edited Apr 10, 2021 by Peter Cordes

1 Answer

4

You are right that applications see a full address space. Normally, applications are called processes. Each process sees a full virtual address space but this is due to the fact that its page tables are set up so that it will be able to access the whole virtual address space without interfering with other processes (its address accesses will translate to different places than other processes).

Does each application have their own page directory or is there one page directory, how does applications access the pages and what do they do exactly?

Each process/app have their own page directory. On x86 32 bits systems, the virtual address will be translated by the MMU starting with the CR3 register. So you load the CR3 register with the bottom of the page directory, and the MMU does the rest by itself. Each core of the processor runs only one process at a time. Each core has its own CR3 register for the current process. When a context switch occurs (due to timer interrupt), the OS changes the CR3 register to point to the bottom of the page directoy of the new process taking place.

For example, Linux does so by saving a pointer to the page directory in the mm struct of the task_struct for each process. The mm struct is a memory map for the process. The task_struct is a process descriptor (sometimes known as Process Control Block or PCB). When a context switch occurs, Linux loads the CR3 register with the address pointed to by the pgd pointer in the mm struct.

Processes don't really access the pages. Processes just execute code and their code (containing only virtual addresses) is automatically translated by the MMU to physical addresses. To translate a virtual address on x86 32 bits systems, the MMU takes the virtual address and splits it into 3 parts. For example virtual address 0x12345678 will have the following split (all addresses are split the same way):

             Offset in pd     Offset in pt     Offset in physical page      
0x12345678 = 0001 0010 00     1101 0001 01     0110 0111 1000

The 10 most significat bits represent the offset in the page directory. The 10 bits in the middle are the offset in the page table and the 12 last bits to the right are the offset in the physical page. The example address above references offset 0x48 in the pd, offset 0x345 in the pt and offset 0x678 in the physical page. The MMU will thus use the CR3 register to find the bottom of the pd. Then it will use entry 0x48 in the pd to find the address of the page table. Once it finds the address of the page table, it will use entry 0x345 to find the address of the physical page. It will then access address 0x678 in that physical page.

How is an application supposed to see the full address space if they are given 4 KiB block of space or one page?

When you compile a program written in C/C++, you compile most parts statically. Most parts of your program will be in the executable. Today, executables support virtual addressing. Mostly, the virtual addresses at which the program parts will be loaded are stored in the executable. When you launch that executable, the OS will load the executable from the hard-disk and then set up the page tables for that new process. It will map the virtual addresses so that the process's memory accesses are mapped to its own code.

For example, an executable could tell Linux to map its first segment (first part of the code) to 0x400000. Linux will then allocate memory for that process anywhere in RAM. Linux will then create the page tables for that process. The page tables will tell the MMU where to go when the CPU fetches the instructions of that process. When the process will be given a CPU to run by the scheduler, Linux will jump to the first instruction of that process (at 0x400000). When the CPU fetches the instruction at 0x400000, the MMU translates that address to anywhere in RAM (where Linux decided to actually place that process) using the page tables.

You are right that processes don't have access to the whole virtual address space at first. They can reference it in code, but mostly it will jump to nowhere and trigger a page fault. Linux will probably kill the process. Virtually, the process has access to the whole virtual address space because pages can be swapped to the hard disk. If a process allocates 4GB of RAM (and there are other processes running), the process won't see that RAM is full and that the OS is actually swapping pages to the hard-disk to make that process work with the rest of the system. This is why a process has virtual access to the whole virtual address space (which has the same size then physical memory).

How do you write the pages to the hard drive?

In a hobby OS written just for fun, mostly you won't have to. It is sometimes necessary when there is so much going on that RAM is full. Linux thus takes pages in RAM and loads them in the hard disk keeping track of where they are. When a process accesses a page that's not present in RAM (because it has its present bit not set in the page table), the CPU triggers a page fault. The page fault handler (registered by the OS at boot) has access to all kernel structures. It will thus find the evicted page on the hard-disk and swap that page back to RAM (evicting another page in the meantime).

I'm not totally aware since I never wrote an actual modern hard-disk driver. The easiest way to store stuff on the hard-disk in 32 bits mode is by using PIO mode which works with LBA. You can read more on that on osdev.org in the article dedicated to PIO mode for ATA disks.

In most modern hardware I think it is mostly done with the DMA controller which works with PCI. You enumerate the PCI devices by reading some registers. You find the base of the PCI configuration space by looking in the MCFG ACPI table. Afterwards, if you find a PCI DMA controller, you use the specific registers of that controller to trigger read/write cycles to/from the hard-disk.

How are we supposed to allocate pages for applications to use?

You need an algorithm which will determine where a process will land in physical memory. Linux uses the buddy algorithm to find un-allocated pages when you launch a process to avoid external fragmentation. The compiler/linker of your OS should split the compiled program into pages already (which is done by ld and g++/gcc).

answered on Stack Overflow Apr 10, 2021 by user123

User contributions licensed under CC BY-SA 3.0