1import{_ as n,c as a,e,o as p}from"./app-CjUkjRdW.js";const t={};function o(l,s){return p(),a("div",null,s[0]||(s[0]=[e(`<h1 id="virtual-memory" tabindex="-1"><a class="header-anchor" href="#virtual-memory"><span>Virtual Memory</span></a></h1><p>So we have a working physical memory manager. But we can't keep using physical memory directly; sooner or later we'll run out of it. This is where virtual memory comes in. Virtual memory allows us to use more memory than we actually have, by mapping virtual addresses to physical addresses. In this section we'll implement a <strong>Virtual Memory Manager</strong> (VMM).</p><p>When we booted through UEFI, the firmware had already enabled virtual memory for us, but it has been identity-mapped to physical memory. This makes it easy to manage memory during the boot process, but to take advantage of virtual memory we need to set it up ourselves. Let's first take a look at how the x86-64 virtual memory system works.</p><h2 id="virtual-address-space" tabindex="-1"><a class="header-anchor" href="#virtual-address-space"><span>Virtual address space</span></a></h2><p>The 64-bit virtual address space on x86-64 is 48 bits (or 57 bits if you enable the 5-level paging extension). Virtual addresses use a canonical address format, where the most significant 16 bits of the 64-bit address must be either all 0s or all 1s. This means that the address space is split into two parts: the lower half (from <code>0x0000000000000000</code> to <code>0x00007FFFFFFFFFFF</code>), and the higher half (from <code>0xFFFF800000000000</code> to <code>0xFFFFFFFFFFFFFFFF</code>). Each is 47 bits in size, which is equivalent to 128 TiB. This is more than enough for our purposes. We'll use the lower half (128 TiB) for user processes (<strong>user space</strong>), and the higher half (128 TiB) for the kernel (<strong>kernel space</strong>). This is a diagram of the virtual address space:</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre><code><span class="line"> 0xFFFFFFFFFFFFFFFF (16 EiB) ââââââââââââââââââââââââââââââââ</span> 2<span class="line"> â Kernel Space â</span> 3<span class="line"> 0xFFFF800000000000 (-128 TiB) ââââââââââââââââââââââââââââââââ¤</span> 4<span class="line"> â â</span> 5<span class="line"> â â</span> 6<span class="line"> â Canonical Address â</span> 7<span class="line"> â Gap â</span> 8<span class="line"> â â</span> 9<span class="line"> â â</span> 10<span class="line"> 0x00007FFFFFFFFFFF (128 TiB) ââââââââââââââââââââââââââââââââ¤</span> 11<span class="line"> â User Space â</span> 12<span class="line"> 0x0000000000000000 (0 TiB) ââââââââââââââââââââââââââââââââ</span> 13<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>We'll start by introducing some concepts about how address translation works. The main idea is that the CPU makes use of a set of hierarchical page tables to translate virtual addresses to physical addresses. Let's take a look at the structure of these page tables.</p><h2 id="page-tables-structure" tabindex="-1"><a class="header-anchor" href="#page-tables-structure"><span>Page tables structure</span></a></h2><p>In x64 mode, page tables are used to translate virtual addresses to physical addresses. They are structured as a tree.</p><ul><li>The root of the tree is a <strong>Page Map Level 4</strong>
13 table (PML4), which contains 512 entries.</li><li>Each entry points to a <strong>Page Directory Pointer Table</strong> (PDPT), which also contains 512 entries.</li><li>Each entry in the PDPT points to a <strong>Page Directory</strong> (PD), which contains 512 entries.</li><li>Each entry in the PD points to a <strong>Page Table</strong> (PT), which contains 512 entries.</li><li>Each entry in the PT points to a physical page frame. The page frame size is 4 KiB of physical memory.</li></ul><p>The page tables are stored in memory, and the physical address of the root of the tree (the PML4 table) is stored in the <code>CR3</code> control register. We can have different page tables at different times by changing the value of <code>CR3</code>. This is how we can switch between different address spaces.</p><p>The virtual address is split into 5 parts:</p><ul><li>Bits 48-63: Unused (16 bits) <ul><li>These are sign-extended from bit 47, and indicate whether the address is in the lower half (bit 47 is <code>0</code>) or the higher half (bit 47 is <code>1</code>) of the address space.</li></ul></li><li>Bits 39-47: Index into the PML4 (9 bits)</li><li>Bits 30-38: Index into the PDPT (9 bits)</li><li>Bits 21-29: Index into the PD (9 bits)</li><li>Bits 12-20: Index into the PT (9 bits)</li><li>Bits 0-11: Offset within the physical page frame (12 bits)</li></ul><p>Here's a diagram of a virtual address, and how each section of the address maps to the paging tables:</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre><code><span class="line">ââââââââââââââââââââ¬âââââââââââââââââ¬âââââââââââââââââ¬âââââââââââââââ¬âââââââââââââââ¬ââââââââââââââ</span> 14<span class="line">â 63:49 â 48:39 â 38:30 â 29:21 â 20:12 â 11:0 â</span> 15<span class="line">ââââââââââââââââââââ¼âââââââââââââââââ¼âââââââââââââââââ¼âââââââââââââââ¼âââââââââââââââ¼ââââââââââââââ¤</span> 16<span class="line">â Unused (16 bits) â PML4 index (9) â PDPT index (9) â PD index (9) â PT index (9) â Offset (12) â</span> 17<span class="line">ââââââââââââââââââââ´âââââââââââââââââ´âââââââââââââââââ´âââââââââââââââ´âââââââââââââââ´ââââââââââââââ</span> 18<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>So in order to link the kernel at the start of the higher half of the address space (<code>0xFFFF800000100000</code>), we need to map the virtual pages at <code>0xFFFF800000100000</code> to <code>0xFFFF800000100000 + (kernel size)</code> to the physical pages at <code>0x100000</code> to <code>0x100000 + (kernel size)</code>. We'll need to create a PML4 table, a PDPT, a PD, and a PT, and fill them with the appropriate entries.</p><p>Let's break down the higher half address <code>0xFFFF800000100000</code> according to the above diagram:</p><ul><li>Bits 63:49: <code>0xFFFF</code> (sign-extended from bit 47)</li><li>Bits 48:39: <code>0x100</code> (index 256 in the PML4 table)</li><li>Bits 38:30: <code>0x000</code> (index 0 in the PDP table)</li><li>Bits 29:21: <code>0x000</code> (index 0 in the PD table)</li><li>Bits 20:12: <code>0x100</code> (index 256 in the PT table)</li><li>Bits 11:0: <code>0x000</code> (offset 0 within the page frame)</li></ul><p>To map this virtual address to physical address <code>0x100000</code>
18, we need to set the following entries:</p><ul><li>PML4Table: PML4Entry at index 256 points to PDPTable</li><li>PDPTable: PDPTEntry at index 0 points to PDTable</li><li>PDTable: PDEntry at index 0 points to PTable</li><li>PTable: PTEntry at index 256 points to physical address <code>0x100000</code></li></ul><p>Here's a diagram of the page tables after we've set the entries:</p><div class="language-text line-numbers-mode" data-highlighter="prismjs" data-ext="text" data-title="text"><pre><code><span class="line"> âââââââââââââââââââ âââ>âââââââââââââââââââ âââ>âââââââââââââââââââ âââ>âââââââââââââââââââ</span> 19<span class="line"> â PML4Table â â â PDPTable â â â PDTable â â â PTable â</span> 20<span class="line"> ââââââââââââââââââ⤠â ââââââââââââââââââ⤠â ââââââââââââââââââ⤠â âââââââââââââââââââ¤</span> 21<span class="line"> â PML4Entry 0 â â *â PDPTEntry 0 ââââ *â PDEntry 0 ââââ â PTEntry 0 â</span> 22<span class="line"> â PML4Entry 1 â â â PDPTEntry 1 â â PDEntry 1 â â PTEntry 1 â</span> 23<span class="line"> â ... â â â â â â â ... â</span> 24<span class="line"> *â PML4Entry 256 ââââ â ... â â ... â *â PTEntry 256 âââ> 0x100000</span> 25<span class="line"> â ... â â â â â â ... â</span> 26<span class="line"> â PML4Entry 511 â â PDPTEntry 511 â â PDEntry 511 â â PTEntry 511 â</span> 27<span class="line"> âââââââââââââââââââ âââââââââââââââââââ âââââââââââââââââââ âââââââââââââââââââ</span> 28<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h2 id="defining-page-tables" tabindex="-1"><a class="header-anchor" href="#defining-page-tables"><span>Defining page tables</span></a></h2><p>Let's start by defining the structures for 4-level paging. Since we're going to need this both in the bootloader and in the kernel, we'll put it in a common module under <code>common/pagetables.nim</code>. One important point that we need to keep in mind is that the page tables need to be aligned on a 4 KiB boundary. We'll use Nim's <code>align</code> pragma to do this.</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line"><span class="token comment"># src/common/pagetables.nim</span></span> 29<span class="line"></span> 30<span class="line"><span class="token keyword">const</span></span> 31<span class="line"> PageSize<span class="token operator">*</span> <span class="token operator">=</span> <span class="token number">4096</span></span> 32<span class="line"></span> 33<span class="line"><span class="token keyword">type</span></span> 34<span class="line"> <span class="token comment"># Page Map Level 4 Entry</span></span> 35<span class="line"> PML4Entry<span class="token operator">*</span> <span class="token punctuation">{.</span>packed<span class="token punctuation">.}</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 36<span class="line"> present<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span>
36 uint64 <span class="token comment"># bit 0</span></span> 37<span class="line"> write<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 1</span></span> 38<span class="line"> user<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 2</span></span> 39<span class="line"> writeThrough<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 3</span></span> 40<span class="line"> cacheDisable<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 4</span></span> 41<span class="line"> accessed<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 5</span></span> 42<span class="line"> ignored1<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 6</span></span> 43<span class="line"> reserved1<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 7</span></span> 44<span class="line"> ignored2<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">4.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 11: 8</span></span> 45<span class="line"> physAddress<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">40.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 51:12</span></span> 46<span class="line"> ignored3<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">11.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 62:52</span></span> 47<span class="line"> xd<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 63</span></span> 48<span class="line"></span> 49<span class="line"> <span class="token comment"># Page Directory Pointer Table Entry</span></span> 50<span class="line"> PDPTEntry<span class="token operator">*</span> <span class="token punctuation">{.</span>packed<span class="token punctuation">.}</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 51<span class="line"> present<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span>
51 uint64 <span class="token comment"># bit 0</span></span> 52<span class="line"> write<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 1</span></span> 53<span class="line"> user<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 2</span></span> 54<span class="line"> writeThrough<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 3</span></span> 55<span class="line"> cacheDisable<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 4</span></span> 56<span class="line"> accessed<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 5</span></span> 57<span class="line"> ignored1<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 6</span></span> 58<span class="line"> pageSize<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 7</span></span> 59<span class="line"> ignored2<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">4.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 11: 8</span></span> 60<span class="line"> physAddress<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">40.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 51:12</span></span> 61<span class="line"> ignored3<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">11.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 62:52</span></span> 62<span class="line"> xd<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 63</span></span> 63<span class="line"></span> 64<span class="line"> <span class="token comment"># Page Directory Entry</span></span> 65<span class="line"> PDEntry<span class="token operator">*</span> <span class="token punctuation">{.</span>packed<span class="token punctuation">.}</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 66<span class="line"> present<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span>
66 uint64 <span class="token comment"># bit 0</span></span> 67<span class="line"> write<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 1</span></span> 68<span class="line"> user<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 2</span></span> 69<span class="line"> writeThrough<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 3</span></span> 70<span class="line"> cacheDisable<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 4</span></span> 71<span class="line"> accessed<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 5</span></span> 72<span class="line"> ignored1<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 6</span></span> 73<span class="line"> pageSize<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 7</span></span> 74<span class="line"> ignored2<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">4.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 11: 8</span></span> 75<span class="line"> physAddress<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">40.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 51:12</span></span> 76<span class="line"> ignored3<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">11.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 62:52</span></span> 77<span class="line"> xd<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 63</span></span> 78<span class="line"></span> 79<span class="line"> <span class="token comment"># Page Table Entry</span></span> 80<span class="line"> PTEntry<span class="token operator">*</span> <span class="token punctuation">{.</span>packed<span class="token punctuation">.}</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 81<span class="line"> present<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span>
81 uint64 <span class="token comment"># bit 0</span></span> 82<span class="line"> write<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 1</span></span> 83<span class="line"> user<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 2</span></span> 84<span class="line"> writeThrough<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 3</span></span> 85<span class="line"> cacheDisable<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 4</span></span> 86<span class="line"> accessed<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 5</span></span> 87<span class="line"> dirty<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 6</span></span> 88<span class="line"> pat<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 7</span></span> 89<span class="line"> global<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 8</span></span> 90<span class="line"> ignored1<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">3.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 11: 9</span></span> 91<span class="line"> physAddress<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">40.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 51:12</span></span> 92<span class="line"> ignored2<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">11.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bits 62:52</span></span> 93<span class="line"> xd<span class="token operator">*</span> <span class="token punctuation">{.</span>bitsize<span class="token operator">:</span> <span class="token number">1.</span><span class="token punctuation">}</span><span class="token operator">:</span> uint64 <span class="token comment"># bit 63</span></span> 94<span class="line"></span> 95<span class="line"> <span class="token comment"># Page Map Level 4 Table</span></span> 96<span class="line">
96 PML4Table<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 97<span class="line"> entries<span class="token operator">*</span> <span class="token punctuation">{.</span><span class="token function">align</span><span class="token punctuation">(</span>PageSize<span class="token punctuation">)</span><span class="token punctuation">.}</span><span class="token operator">:</span> array<span class="token punctuation">[</span><span class="token number">512</span><span class="token punctuation">,</span> PML4Entry<span class="token punctuation">]</span></span> 98<span class="line"></span> 99<span class="line"> <span class="token comment"># Page Directory Pointer Table</span></span> 100<span class="line"> PDPTable<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 101<span class="line"> entries<span class="token operator">*</span> <span class="token punctuation">{.</span><span class="token function">align</span><span class="token punctuation">(</span>PageSize<span class="token punctuation">)</span><span class="token punctuation">.}</span><span class="token operator">:</span> array<span class="token punctuation">[</span><span class="token number">512</span><span class="token punctuation">,</span> PDPTEntry<span class="token punctuation">]</span></span> 102<span class="line"></span> 103<span class="line"> <span class="token comment"># Page Directory</span></span> 104<span class="line"> PDTable<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 105<span class="line"> entries<span class="token operator">*</span> <span class="token punctuation">{.</span><span class="token function">align</span><span class="token punctuation">(</span>PageSize<span class="token punctuation">)</span><span class="token punctuation">.}</span><span class="token operator">:</span> array<span class="token punctuation">[</span><span class="token number">512</span><span class="token punctuation">,</span> PDEntry<span class="token punctuation">]</span></span> 106<span class="line"></span> 107<span class="line"> <span class="token comment"># Page Table</span></span> 108<span class="line"> PTable<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">object</span></span> 109<span class="line"> entries<span class="token operator">*</span> <span class="token punctuation">{.</span><span class="token function">align</span><span class="token punctuation">(</span>PageSize<span class="token punctuation">)</span><span class="token punctuation">.}</span><span class="token operator">:</span> array<span class="token punctuation">[</span><span class="token number">512</span><span class="token punctuation">,</span> PTEntry<span class="token punctuation">]</span></span> 110<span class="line"></span> 111<span class="line"> PageAccess<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">enum</span></span> 112<span class="line"> paRead <span class="token operator">=</span> <span class="token number">0</span></span> 113<span class="line"> paReadWrite <span class="token operator">=</span> <span class="token number">1</span></span> 114<span class="line"></span> 115<span class="line"> PageMode<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">enum</span></span> 116<span class="line"> pmSupervisor <span class="token operator">=</span> <span class="token number">0</span></span> 117<span class="line"> pmUser <span class="token operator">=</span> <span class="token number">1</span></span> 118<span class="line"></span> 119<span class="line"><span class="token keyword">proc</span> <span class="token function">\`[]\`<span class="token operator">*</span></span><span class="token punctuation">(</span>pml4<span class="token operator">:</span> <span class="token keyword">ptr</span> PML4Table; index<span class="token operator">:</span> uint64<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token keyword">var</span> PML4Entry <span class="token punctuation">{.</span>inline<span class="token punctuation">.}</span> <span class="token operator">=</span> pml4<span class="token operator">.</span>entries<span class="token punctuation">[</span>index<span class="token punctuation">]</span></span> 120<span class="line"><span class="token keyword">proc</span> <span class="token function">\`[]\`<span class="token operator">*</span></span><span class="token punctuation">(</span>pdpt<span class="token operator">:</span> <span class="token keyword">ptr</span> PDPTable; index<span class="token operator">:</span>
120 uint64<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token keyword">var</span> PDPTEntry <span class="token punctuation">{.</span>inline<span class="token punctuation">.}</span> <span class="token operator">=</span> pdpt<span class="token operator">.</span>entries<span class="token punctuation">[</span>index<span class="token punctuation">]</span></span> 121<span class="line"><span class="token keyword">proc</span> <span class="token function">\`[]\`<span class="token operator">*</span></span><span class="token punctuation">(</span>pd<span class="token operator">:</span> <span class="token keyword">ptr</span> PDTable; index<span class="token operator">:</span> uint64<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token keyword">var</span> PDEntry <span class="token punctuation">{.</span>inline<span class="token punctuation">.}</span> <span class="token operator">=</span> pd<span class="token operator">.</span>entries<span class="token punctuation">[</span>index<span class="token punctuation">]</span></span> 122<span class="line"><span class="token keyword">proc</span> <span class="token function">\`[]\`<span class="token operator">*</span></span><span class="token punctuation">(</span>pt<span class="token operator">:</span> <span class="token keyword">ptr</span> PTable; index<span class="token operator">:</span> uint64<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token keyword">var</span> PTEntry <span class="token punctuation">{.</span>inline<span class="token punctuation">.}</span> <span class="token operator">=</span> pt<span class="token operator">.</span>entries<span class="token punctuation">[</span>index<span class="token punctuation">]</span></span> 123<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><div class="hint-container tip"><p class="hint-container-title">Note Ideally we wouldn't need to define an \`entries\` array field within each</p><p>object, and we could just define the tables like so:</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line">
123PML4Table<span class="token operator">*</span> <span class="token punctuation">{.</span><span class="token function">align</span><span class="token punctuation">(</span>PageSize<span class="token punctuation">)</span><span class="token punctuation">.}</span> <span class="token operator">=</span> array<span class="token punctuation">[</span><span class="token number">512</span><span class="token punctuation">,</span> PML4Entry<span class="token punctuation">]</span></span> 124<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div></div></div><p>Then we could access the table by indexing directly into its variable, e.g. <code>pml4[i]</code>, instead of <code>pml4.entries[i]</code>. Unfortunately Nim doesn't support type-level alignment (yet). See this <a href="https://github.com/nim-lang/RFCs/issues/545" target="_blank" rel="noopener noreferrer">RFC</a>. So, as a workaround, I defined index operators for each table type, which just forward the indexing to the <code>entries</code> field.</p></div><h2 id="accessing-page-tables" tabindex="-1"><a class="header-anchor" href="#accessing-page-tables"><span>Accessing page tables</span></a></h2><p>OK, we have the page table structures defined. But before we start using them, we need to think about how we're going to access them. Let's look at a simple example:</p><ul><li>We allocate a <code>PML4Table</code> instance (call it <code>pml4</code>).</li><li>We allocate a <code>PDPTable</code> instance.</li><li>We modify <code>pml4[0].physAddress</code> to point to the physical address of the <code>PDPTable</code> instance.</li><li>At some later point, we want to modify that <code>PDPTable</code> instance. But how do we get its virtual address? All we have is its physical address through <code>pml4[0].physAddress</code>.</li></ul><p>We need a way to reverse map a physical address to a virtual address. Here are some solutions:</p><ul><li>Identity-mapping the page tables <ul><li>Pros: simple; no need to reverse map</li><li>Cons: pollutes the user address space (since physical memory is in the lower half)</li></ul></li><li>Mapping page tables at a constant offset from their physical addresses <ul><li>Pros: simple; reverse mapping is trivial</li><li>Cons: requires creating new mappings for each page table</li></ul></li><li>Mapping the entire physical memory at a known virtual address <ul><li>Pros: simple; reverse mapping is trivial</li><li>Cons: requires dedicating a range of virtual addresses for the entire physical memory</li></ul></li><li>Recursive page tables <ul><li>Pros: doesn't require additional mappings</li><li>Cons: complex; accessing a page table requires that it be currently active, which means we need to switch to it first (sometimes this is not feasible)</li></ul></li></ul><p>We'll go with the third option (mapping the entire physical memory at a known virtual address). This makes reverse mapping trivial, and also gives us the ability to address any location in physical memory in a simple way. We'll use the virtual address <code>0xFFFFFFFF80000000</code> for this purpose.</p><h2 id="mapping-pages" tabindex="-1"><a class="header-anchor" href="#mapping-pages"><span>Mapping pages</span></a></h2><p>Mapping pages will require allocating physical memory frames to hold the page tables themselves. In the kernel, we'll use the physical memory manager to allocate these frames. However, we'll also need to create page tables in the bootloader to map a few regions before we jump to the kernel. So instead of letting the VMM use the PMM implicitly, we'll pass our VMM a callback that it can use to allocate physical memory frames. This will allow us to use the VMM from both the kernel and the bootloader.</p><p>Let's define a couple of types and a <code>vmInit</code> proc that initializes the VMM.</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line"><span class="token comment"># src/boot/vmm.nim</span></span> 125<span class="line"></span> 126<span class="line"><span class="token keyword">type</span></span> 127<span class="line"> VirtAddr<span class="token operator">*</span> <span class="token operator">=</span> <span class="token keyword">distinct</span> uint64</span> 128<span class="line"> PhysAlloc<span class="token operator">*</span> <span class="token operator">=</span> <span class="token function">proc</span> <span class="token punctuation">(</span>nframes<span class="token operator">:</span>
128 uint64<span class="token punctuation">)</span><span class="token operator">:</span> Option<span class="token punctuation">[</span>PhysAddr<span class="token punctuation">]</span></span> 129<span class="line"></span> 130<span class="line"><span class="token keyword">var</span></span> 131<span class="line"> physicalMemoryVirtualBase<span class="token operator">:</span> uint64</span> 132<span class="line"> pmalloc<span class="token operator">:</span> PhysAlloc</span> 133<span class="line"></span> 134<span class="line"><span class="token keyword">proc</span> <span class="token function">vmInit<span class="token operator">*</span></span><span class="token punctuation">(</span>physMemoryVirtualBase<span class="token operator">:</span> uint64<span class="token punctuation">,</span> physAlloc<span class="token operator">:</span> PhysAlloc<span class="token punctuation">)</span> <span class="token operator">=</span></span> 135<span class="line"> physicalMemoryVirtualBase <span class="token operator">=</span> physMemoryVirtualBase</span> 136<span class="line"> pmalloc <span class="token operator">=</span> physAlloc</span> 137<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>Let's also add a couple of templates for pointer arithmetic on virtual addresses, which will make our code more readable.</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line"><span class="token comment"># src/boot/vmm.nim</span></span> 138<span class="line"><span class="token operator">...</span></span> 139<span class="line"></span> 140<span class="line"><span class="token keyword">template</span> <span class="token function">\`+!\`<span class="token operator">*</span></span><span class="token punctuation">(</span>p<span class="token operator">:</span> VirtAddr<span class="token punctuation">,</span> offset<span class="token operator">:</span> uint64<span class="token punctuation">)</span><span class="token operator">:</span> VirtAddr <span class="token operator">=</span></span> 141<span class="line"> <span class="token function">VirtAddr</span><span class="token punctuation">(</span><span class="token function">cast[uint64]</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span> <span class="token operator">+</span> offset<span class="token punctuation">)</span></span> 142<span class="line"></span> 143<span class="line"><span class="token keyword">template</span> <span class="token function">\`-!\`<span class="token operator">*</span></span><span class="token punctuation">(</span>p<span class="token operator">:</span> VirtAddr<span class="token punctuation">,</span> offset<span class="token operator">:</span> uint64<span class="token punctuation">)</span><span class="token operator">:</span> VirtAddr <span class="token operator">=</span></span> 144<span class="line"> <span class="token function">VirtAddr</span><span class="token punctuation">(</span><span class="token function">cast[uint64]</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span> <span class="token operator">-</span> offset<span class="token punctuation">)</span></span> 145<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>We'll also need two procs that map virtual addresses to physical addresses and vice versa. We'll call them <code>p2v</code> and <code>v2p</code>. The <code>p2v</code> proc is simple: it just adds the virtual memory base to the physical address. The <code>v2p</code> proc is more complex. It needs to traverse the page tables to find the physical address that corresponds to the virtual address. In order to do this, it needs to know the current active page table, so we'll add a <code>getActivePML4</code> proc that returns a pointer to the active PML4 table. We'll also add a <code>setActivePML4</code> proc that sets the active PML4 table. (The <code>{.experimental: "codeReordering".}</code> pragma is optional, but it lets us use procs before they are defined, thus avoiding the need to forward-declare them.)</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line"><span class="token comment"># src/boot/vmm.nim</span></span> 146<span class="line"></span> 147<span class="line"><span class="token keyword">
147import</span> common<span class="token operator">/</span>pagetables</span> 148<span class="line"><span class="token keyword">import</span> pmm <span class="token comment"># only needed for PhysAddr</span></span> 149<span class="line"></span> 150<span class="line"><span class="token punctuation">{.</span>experimental<span class="token operator">:</span> <span class="token string">"codeReordering"</span><span class="token punctuation">.}</span></span> 151<span class="line"></span> 152<span class="line"><span class="token keyword">proc</span> <span class="token function">p2v<span class="token operator">*</span></span><span class="token punctuation">(</span>phys<span class="token operator">:</span> PhysAddr<span class="token punctuation">)</span><span class="token operator">:</span> VirtAddr <span class="token operator">=</span></span> 153<span class="line"> result <span class="token operator">=</span> <span class="token function">cast[VirtAddr]</span><span class="token punctuation">(</span>phys <span class="token operator">+!</span> physicalMemoryVirtualBase<span class="token punctuation">)</span></span> 154<span class="line"></span> 155<span class="line"><span class="token keyword">proc</span> <span class="token function">v2p<span class="token operator">*</span></span><span class="token punctuation">(</span>virt<span class="token operator">:</span> VirtAddr<span class="token punctuation">)</span><span class="token operator">:</span> Option<span class="token punctuation">[</span>PhysAddr<span class="token punctuation">]</span> <span class="token operator">=</span></span> 156<span class="line"> <span class="token keyword">let</span> pml4 <span class="token operator">=</span> <span class="token function">getActivePML4</span><span class="token punctuation">(</span><span class="token punctuation">)</span></span> 157<span class="line"></span> 158<span class="line"> <span class="token keyword">var</span> pml4Index <span class="token operator">=</span> <span class="token punctuation">(</span>virt<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">39</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 159<span class="line"> <span class="token keyword">var</span> pdptIndex <span class="token operator">=</span> <span class="token punctuation">(</span>virt<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">30</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 160<span class="line"> <span class="token keyword">var</span> pdIndex <span class="token operator">=</span> <span class="token punctuation">(</span>virt<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">21</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 161<span class="line"> <span class="token keyword">var</span> ptIndex <span class="token operator">=</span> <span class="token punctuation">(</span>virt<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">12</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 162<span class="line"></span> 163<span class="line"> <span class="token keyword">if</span> pml4<span class="token operator">.</span>entries<span class="token punctuation">[</span>pml4Index<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">==</span> <span class="token number">0</span><span class="token operator">:</span></span> 164<span class="line"> result <span class="token operator">=</span> <span class="token function">none</span><span class="token punctuation">(</span>PhysAddr<span class="token punctuation">)</span></span> 165<span class="line"> <span class="token keyword">return</span></span> 166<span class="line"></span> 167<span class="line"> <span class="token keyword">let</span> pdptPhysAddr <span class="token operator">=</span> <span class="token function">PhysAddr</span><span class="token punctuation">(</span>pml4<span class="token operator">.</span>entries<span class="token punctuation">[</span>pml4Index<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">
167shl</span> <span class="token number">12</span><span class="token punctuation">)</span></span> 168<span class="line"> <span class="token keyword">let</span> pdpt <span class="token operator">=</span> <span class="token function">cast[ptr PDPTable]</span><span class="token punctuation">(</span><span class="token function">p2v</span><span class="token punctuation">(</span>pdptPhysAddr<span class="token punctuation">)</span><span class="token punctuation">)</span></span> 169<span class="line"></span> 170<span class="line"> <span class="token keyword">if</span> pdpt<span class="token operator">.</span>entries<span class="token punctuation">[</span>pdptIndex<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">==</span> <span class="token number">0</span><span class="token operator">:</span></span> 171<span class="line"> result <span class="token operator">=</span> <span class="token function">none</span><span class="token punctuation">(</span>PhysAddr<span class="token punctuation">)</span></span> 172<span class="line"> <span class="token keyword">return</span></span> 173<span class="line"></span> 174<span class="line"> <span class="token keyword">let</span> pdPhysAddr <span class="token operator">=</span> <span class="token function">PhysAddr</span><span class="token punctuation">(</span>pdpt<span class="token operator">.</span>entries<span class="token punctuation">[</span>pdptIndex<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">shl</span> <span class="token number">12</span><span class="token punctuation">)</span></span> 175<span class="line"> <span class="token keyword">let</span> pd <span class="token operator">=</span> <span class="token function">cast[ptr PDTable]</span><span class="token punctuation">(</span><span class="token function">p2v</span><span class="token punctuation">(</span>pdPhysAddr<span class="token punctuation">)</span><span class="token punctuation">)</span></span> 176<span class="line"></span> 177<span class="line"> <span class="token keyword">if</span> pd<span class="token operator">.</span>entries<span class="token punctuation">[</span>pdIndex<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">==</span> <span class="token number">0</span><span class="token operator">:</span></span> 178<span class="line"> result <span class="token operator">=</span> <span class="token function">none</span><span class="token punctuation">(</span>PhysAddr<span class="token punctuation">)</span></span> 179<span class="line"> <span class="token keyword">return</span></span> 180<span class="line"></span> 181<span class="line"> <span class="token keyword">let</span> ptPhysAddr <span class="token operator">=</span> <span class="token function">PhysAddr</span><span class="token punctuation">(</span>pd<span class="token operator">.</span>entries<span class="token punctuation">[</span>pdIndex<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">shl</span> <span class="token number">12</span><span class="token punctuation">)</span></span> 182<span class="line"> <span class="token keyword">let</span> pt <span class="token operator">=</span> <span class="token function">cast[ptr PTable]</span><span class="token punctuation">(</span><span class="token function">p2v</span><span class="token punctuation">(</span>ptPhysAddr<span class="token punctuation">)</span><span class="token punctuation">)</span></span> 183<span class="line"></span> 184<span class="line"> <span class="token keyword">if</span> pt<span class="token operator">.</span>entries<span class="token punctuation">[</span>ptIndex<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">==</span> <span class="token number">0</span><span class="token operator">:</span></span> 185<span class="line"> result <span class="token operator">=</span> <span class="token function">none</span><span class="token punctuation">(</span>PhysAddr<span class="token punctuation">)</span></span> 186<span class="line"> <span class="token keyword">return</span></span> 187<span class="line"></span> 188<span class="line"> result <span class="token operator">=</span> some <span class="token function">PhysAddr</span><span class="token punctuation">(</span>pt<span class="token operator">.</span>entries<span class="token punctuation">[</span>ptIndex<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">
188shl</span> <span class="token number">12</span><span class="token punctuation">)</span></span> 189<span class="line"></span> 190<span class="line"><span class="token keyword">proc</span> <span class="token function">getActivePML4<span class="token operator">*</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">:</span> <span class="token keyword">ptr</span> PML4Table <span class="token operator">=</span></span> 191<span class="line"> <span class="token keyword">var</span> cr3<span class="token operator">:</span> uint64</span> 192<span class="line"> <span class="token keyword">asm</span> <span class="token string">"""</span> 193<span class="line"> mov %0, cr3</span> 194<span class="line"> : "=r"(\`cr3\`)</span> 195<span class="line"> """</span></span> 196<span class="line"> result <span class="token operator">=</span> <span class="token function">cast[ptr PML4Table]</span><span class="token punctuation">(</span><span class="token function">p2v</span><span class="token punctuation">(</span>cr3<span class="token operator">.</span>PhysAddr<span class="token punctuation">)</span><span class="token punctuation">)</span></span> 197<span class="line"></span> 198<span class="line"><span class="token keyword">proc</span> <span class="token function">setActivePML4<span class="token operator">*</span></span><span class="token punctuation">(</span>pml4<span class="token operator">:</span> <span class="token keyword">ptr</span> PML4Table<span class="token punctuation">)</span> <span class="token operator">=</span></span> 199<span class="line"> <span class="token keyword">var</span> cr3 <span class="token operator">=</span> <span class="token function">v2p</span><span class="token punctuation">(</span><span class="token function">cast[VirtAddr]</span><span class="token punctuation">(</span>pml4<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">.</span>get</span> 200<span class="line"> <span class="token keyword">asm</span> <span class="token string">"""</span> 201<span class="line"> mov cr3, %0</span> 202<span class="line"> :</span> 203<span class="line"> : "r"(\`cr3\`)</span> 204<span class="line"> """</span></span> 205<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>We can now write a function to map a virtual page to a physical page. We'll extract 4 index values from the virtual address, and use them to insert (or update) the appropriate entries in the page tables. To avoid repeating a lot of the code, I created a <code>getOrCreateEntry</code> generic proc, which will return an entry if it exists in the parent table, or allocate a new page (for the child table) if it doesn't and sets the appropriate entry in the parent table.</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line"><span class="token comment"># src/boot/vmm.nim</span></span> 206<span class="line"><span class="token operator">...</span></span> 207<span class="line"></span> 208<span class="line"><span class="token keyword">proc</span> <span class="token function">getOrCreateEntry[TP, TC]</span><span class="token punctuation">(</span>parent<span class="token operator">:</span> <span class="token keyword">ptr</span> TP<span class="token punctuation">,</span> index<span class="token operator">:</span>
208 uint64<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token keyword">ptr</span> TC <span class="token operator">=</span></span> 209<span class="line"> <span class="token keyword">var</span> physAddr<span class="token operator">:</span> PhysAddr</span> 210<span class="line"> <span class="token keyword">if</span> parent<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">==</span> <span class="token number">1</span><span class="token operator">:</span></span> 211<span class="line"> physAddr <span class="token operator">=</span> <span class="token function">PhysAddr</span><span class="token punctuation">(</span>parent<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">shl</span> <span class="token number">12</span><span class="token punctuation">)</span></span> 212<span class="line"> <span class="token keyword">else</span><span class="token operator">:</span></span> 213<span class="line"> physAddr <span class="token operator">=</span> <span class="token function">pmalloc</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">.</span>get <span class="token comment"># TODO: handle allocation failure</span></span> 214<span class="line"> parent<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">=</span> physAddr<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">12</span></span> 215<span class="line"> parent<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">=</span> <span class="token number">1</span></span> 216<span class="line"> result <span class="token operator">=</span> <span class="token function">cast[ptr TC]</span><span class="token punctuation">(</span><span class="token function">p2v</span><span class="token punctuation">(</span>physAddr<span class="token punctuation">)</span><span class="token punctuation">)</span></span> 217<span class="line"></span> 218<span class="line"><span class="token keyword">proc</span> <span class="token function">mapPage</span><span class="token punctuation">(</span></span> 219<span class="line"> pml4<span class="token operator">:</span> <span class="token keyword">ptr</span> PML4Table<span class="token punctuation">,</span></span> 220<span class="line"> virtAddr<span class="token operator">:</span> VirtAddr<span class="token punctuation">,</span></span> 221<span class="line"> physAddr<span class="token operator">:</span> PhysAddr<span class="token punctuation">,</span></span> 222<span class="line"> pageAccess<span class="token operator">:</span> PageAccess<span class="token punctuation">,</span></span> 223<span class="line"> pageMode<span class="token operator">:</span> PageMode<span class="token punctuation">,</span></span> 224<span class="line"><span class="token punctuation">)</span> <span class="token operator">=</span></span> 225<span class="line"> <span class="token keyword">let</span> pml4Index <span class="token operator">=</span> <span class="token punctuation">(</span>virtAddr<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">39</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 226<span class="line"> <span class="token keyword">let</span> pdptIndex <span class="token operator">=</span> <span class="token punctuation">(</span>virtAddr<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">30</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 227<span class="line"> <span class="token keyword">let</span> pdIndex <span class="token operator">=</span> <span class="token punctuation">(</span>virtAddr<span class="token operator">.</span>
227uint64 <span class="token operator">shr</span> <span class="token number">21</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 228<span class="line"> <span class="token keyword">let</span> ptIndex <span class="token operator">=</span> <span class="token punctuation">(</span>virtAddr<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">12</span><span class="token punctuation">)</span> <span class="token operator">and</span> <span class="token number">0x1FF</span></span> 229<span class="line"></span> 230<span class="line"> <span class="token keyword">let</span> access <span class="token operator">=</span> <span class="token function">cast[uint64]</span><span class="token punctuation">(</span>pageAccess<span class="token punctuation">)</span></span> 231<span class="line"> <span class="token keyword">let</span> mode <span class="token operator">=</span> <span class="token function">cast[uint64]</span><span class="token punctuation">(</span>pageMode<span class="token punctuation">)</span></span> 232<span class="line"></span> 233<span class="line"> <span class="token comment"># Page Map Level 4 Table</span></span> 234<span class="line"> pml4<span class="token punctuation">[</span>pml4Index<span class="token punctuation">]</span><span class="token operator">.</span>write <span class="token operator">=</span> access</span> 235<span class="line"> pml4<span class="token punctuation">[</span>pml4Index<span class="token punctuation">]</span><span class="token operator">.</span>user <span class="token operator">=</span> mode</span> 236<span class="line"> <span class="token keyword">var</span> pdpt <span class="token operator">=</span> <span class="token function">getOrCreateEntry[PML4Table, PDPTable]</span><span class="token punctuation">(</span>pml4<span class="token punctuation">,</span> pml4Index<span class="token punctuation">)</span></span> 237<span class="line"></span> 238<span class="line"> <span class="token comment"># Page Directory Pointer Table</span></span> 239<span class="line"> pdpt<span class="token punctuation">[</span>pdptIndex<span class="token punctuation">]</span><span class="token operator">.</span>write <span class="token operator">=</span> access</span> 240<span class="line"> pdpt<span class="token punctuation">[</span>pdptIndex<span class="token punctuation">]</span><span class="token operator">.</span>user <span class="token operator">=</span> mode</span> 241<span class="line"> <span class="token keyword">var</span> pd <span class="token operator">=</span> <span class="token function">getOrCreateEntry[PDPTable, PDTable]</span><span class="token punctuation">(</span>pdpt<span class="token punctuation">,</span> pdptIndex<span class="token punctuation">)</span></span> 242<span class="line"></span> 243<span class="line"> <span class="token comment"># Page Directory</span></span> 244<span class="line"> pd<span class="token punctuation">[</span>pdIndex<span class="token punctuation">]</span><span class="token operator">.</span>write <span class="token operator">=</span> access</span> 245<span class="line"> pd<span class="token punctuation">[</span>pdIndex<span class="token punctuation">]</span><span class="token operator">.</span>user <span class="token operator">=</span> mode</span> 246<span class="line"> <span class="token keyword">var</span> pt <span class="token operator">=</span> <span class="token function">getOrCreateEntry[PDTable, PTable]</span><span class="token punctuation">(</span>pd<span class="token punctuation">,</span> pdIndex<span class="token punctuation">)</span></span> 247<span class="line"></span> 248<span class="line"> <span class="token comment"># Page Table</span></span> 249<span class="line"> pt<span class="token punctuation">[</span>ptIndex<span class="token punctuation">]</span><span class="token operator">.</span>physAddress <span class="token operator">=</span> physAddr<span class="token operator">.</span>uint64 <span class="token operator">shr</span> <span class="token number">12</span></span> 250<span class="line"> pt<span class="token punctuation">[</span>ptIndex<span class="token punctuation">]</span><span class="token operator">.</span>present <span class="token operator">=</span> <span class="token number">1</span></span> 251<span class="line"> pt<span class="token punctuation">[</span>ptIndex<span class="token punctuation">]</span><span class="token operator">.</span>write <span class="token operator">=</span> access</span> 252<span class="line"> pt<span class="token punctuation">[</span>ptIndex<span class="token punctuation">]</span><span class="token operator">.</span>user <span class="token operator">=</span> mode</span> 253<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><blockquote><p>Notice the power of Nim generics here, which is structurally typed. The <code>getOrCreateEntry</code> proc accesses fields of the <code>TP</code> generic type (the parent table type), and the compiler will make sure that the fields exist in the object that is passed to the proc. We don't have to provide type constraints on the generic types, and we don't have to use inheritance or interfaces.</p></blockquote><p>The caller needs to pass a pointer to <code>PML4Table</code> (the root of the page tables), which they are responsible for allocating. At every level of the table hierarchy, we check if the entry is present. If it is, we use the physical address stored in the entry to get the virtual address of the next table. If it isn't, we allocate a new physical memory frame and store its address in the entry (and set the <code>present</code> bit in the entry to <code>1</code>). We also update the <code>write</code> and <code>user</code> bits at every level, so that the page is accessible in the way that the caller requested.</p><p>In addition to mapping a single page, we'll occasionally need to map a range of pages. We'
253ll also need to identity-map pages in some cases. Let's add procs for these as well.</p><div class="language-nim line-numbers-mode" data-highlighter="prismjs" data-ext="nim" data-title="nim"><pre><code><span class="line"><span class="token comment"># src/boot/vmm.nim</span></span> 254<span class="line"></span> 255<span class="line"><span class="token keyword">proc</span> <span class="token function">mapRegion<span class="token operator">*</span></span><span class="token punctuation">(</span></span> 256<span class="line"> pml4<span class="token operator">:</span> <span class="token keyword">ptr</span> PML4Table<span class="token punctuation">,</span></span> 257<span class="line"> virtAddr<span class="token operator">:</span> VirtAddr<span class="token punctuation">,</span></span> 258<span class="line"> physAddr<span class="token operator">:</span> PhysAddr<span class="token punctuation">,</span></span> 259<span class="line"> pageCount<span class="token operator">:</span> uint64<span class="token punctuation">,</span></span> 260<span class="line"> pageAccess<span class="token operator">:</span> PageAccess<span class="token punctuation">,</span></span> 261<span class="line"> pageMode<span class="token operator">:</span> PageMode<span class="token punctuation">,</span></span> 262<span class="line"><span class="token punctuation">)</span> <span class="token operator">=</span></span> 263<span class="line"> <span class="token keyword">for</span> i <span class="token operator">in</span> <span class="token number">0</span> <span class="token operator">..<</span>
263 pageCount<span class="token operator">:</span></span> 264<span class="line"> <span class="token function">mapPage</span><span class="token punctuation">(</span>pml4<span class="token punctuation">,</span> virtAddr <span class="token operator">+!</span> i <span class="token operator">*</span> PageSize<span class="token punctuation">,</span> physAddr <span class="token operator">+!</span> i <span class="token operator">*</span> PageSize<span class="token punctuation">,</span> pageAccess<span class="token punctuation">,</span> pageMode<span class="token punctuation">)</span></span> 265<span class="line"></span> 266<span class="line"><span class="token keyword">proc</span> <span class="token function">identityMapRegion<span class="token operator">*</span></span><span class="token punctuation">(</span></span> 267<span class="line"> pml4<span class="token operator">:</span> <span class="token keyword">ptr</span> PML4Table<span class="token punctuation">,</span></span> 268<span class="line"> physAddr<span class="token operator">:</span> PhysAddr<span class="token punctuation">,</span></span> 269<span class="line"> pageCount<span class="token operator">:</span> uint64<span class="token punctuation">,</span></span> 270<span class="line"> pageAccess<span class="token operator">:</span> PageAccess<span class="token punctuation">,</span></span> 271<span class="line"> pageMode<span class="token operator">:</span> PageMode<span class="token punctuation">,</span></span> 272<span class="line"><span class="token punctuation">)</span> <span class="token operator">=</span></span> 273<span class="line"> <span class="token function">mapRegion</span><span class="token punctuation">(</span>pml4<span class="token punctuation">,</span> physAddr<span class="token operator">.</span>VirtAddr<span class="token punctuation">,</span> physAddr<span class="token punctuation">,</span>
273 pageCount<span class="token punctuation">,</span> pageAccess<span class="token punctuation">,</span> pageMode<span class="token punctuation">)</span></span> 274<span class="line"></span></code></pre><div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0;"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>OK, we should have everything we need to set up the page tables. In the next section we'll look into modifying the bootloader to load the kernel into the higher half of the address space.</p>`,47)]))}const c=n(t,[["render",o],["__file","12-virtual-memory.html.vue"]]),r=JSON.parse(`{"path":"/osdev/12-virtual-memory.html","title":"Virtual Memory","lang":"en-US","frontmatter":{},"headers":[{"level":2,"title":"Virtual address space","slug":"virtual-address-space","link":"#virtual-address-space","children":[]},{"level":2,"title":"Page tables structure","slug":"page-tables-structure","link":"#page-tables-structure","children":[]},{"level":2,"title":"Defining page tables","slug":"defining-page-tables","link":"#defining-page-tables","children":[]},{"level":2,"title":"Accessing page tables","slug":"accessing-page-tables","link":"#accessing-page-tables","children":[]},{"level":2,"title":"Mapping pages","slug":"mapping-pages","link":"#mapping-pages","children":[]}],"git":{"updatedTime":1744638230000},"filePathRelative":"osdev/12-virtual-memory.md","excerpt":"\\n<p>So we have a working physical memory manager. But we can't keep using physical memory\\ndirectly; sooner or later we'll run out of it. This is where virtual memory comes in.\\nVirtual memory allows us to use more memory than we actually have, by mapping virtual\\naddresses to physical addresses. In this section we'll implement a <strong>Virtual Memory\\nManager</strong> (VMM).</p>"}`);export{c as comp,r as data};
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.