Explanation

Paging

Caution

This summary note focuses on IA-32e mode's 2MB-4stages paging mode

What problem does Paging solve?

Segmentation offers multiple linear memory spaces, so it is great for organizing code. For example, a process can have segments for code, data sections or more sections if it want. However, reassigning a segment to different process or caching segment to disk are challenging because segment is usually a big chunk. If each process gives up using segments, has an virtual linear address space, and lets OS and CPU maps each small piece of virtual linear space to small piece of physical memory space. This method is called Paging

I said 'gives up using segments' in the explanation to help you to understand by making your imagination as simple as possible. Actually, you can still make your program use segmentation with paging. Without paging, segmentation maps address directly to physical address, and with paging on, segmentation maps address to virtual address. And then the virtual address is mapped to real physical address.

In modern operating system, segmentation is not utilized. It is considered legacy. However, so you can still utilize segmentation.

Overview of Paging

Segmentation converts logical addresses to linear addresses, and Paging is the process of translating linear addresses to physical addresses.
- logical address -> linear address -> physical address
- Without paging, segmentation is only used and the converted linear address is literally physical address
Paging feature depends on segmentation feature. Paging works on top of segmentation. No matter what memory management you decided to utilize, segmentation must be part of overall address conversion calculation. It sounds weird, but this is how the CPU works. If you want to utilize only virtual address, you need two stops. First, set base address of segment descriptor to 0 and limit to maximum. Second, make processes share the same descriptor.
- The figure can make you think that linear address is in physical memory, so cpu need to access linear address in memory and convert it to physical memory. No, linear address is just (segment descriptor base addr + offset)
IA-32 paging diagram
- In IA-32e mode, you cannot only utilize segmentation. The mode ignores base address and limit in segment descriptor. CPU thinks that base address is 0 and limit is maximum. This means that you are forced to use paging feature. Like other modes, segmentation is still part of overall memory conversion calculation in IA-32e mode.
IA-32e segmentation characteristics
For paging mapping, a hierarchical tree data structure is utilized.
- The tree stays in memory.
- each process can have its own tree, so completely independent virtual address can be implemented
  - but, shared-memory mapping between processes are also possible.
- Depending on mode and page size, tree depth is different.
Linear address contains two values
1. multiple indices that locate a leaf in the tree
  - size of a index depends on paging mode
  - number of indices depends on paging mode
2. page offset
  - size of a index depends on paging mode

Paging Modes

To enable Paging, CR0, CR2, CR3, and CR4 are needed. IA32_EFER is for switching to IA-32e Mode.

CR0 has paging enable
CR3 has address to paging related table
CR4 has switches for paging-related features
- PAE is paging extension. IA-32e paging depends on it, so it must be set in CR4 for IA-32e
- Execute-Disable is for security

properties of different paging modes

state machine of paging

IA-32e Mode paging modes

Each part in linear address is for finding entry in each table. The tables are in tree structure and linear address is for locating leaf in the tree

IA-32e paging 4k 5stages

IA-32e paging 2MB 4stages

paging entries (figures are all for IA-32e Mode)

paging entry that references to page frame is only one that has different structure from other entries
- bit 7 (PS) decides if the entry has different structure. This bit lets CPU know that level of stages and paging size
- only this entry is related to accessible maximum physical memory size
  - For example, in some computer, 2MB-4stages paging can have 256TB of linear address and 1TB of physical address (2^48 = 256TB, 2MB * 2^19 = 1TB)
  - In 2MB-4stages, this entry uses 19 bits for finding page frame
- (base addr * page_size) = physical address of page frame
the structure is similar to that of segment descriptor
- A: access bit (did cpu access the entry)
- PCD: page cache disable (paging has paging-specific cache feature)
- PWT: page write-through (paging cache mode)
- U/S: user/super (0: prevent user(ring 3) from accessing)
- R/W: read/write (0: prevent user(ring 3) from writing)
- By default, super user(ring 0~2) can access any pages. this setting can be changed by setting CR4. If this is configured, then bit 64(EXB) in entry is used