This is the second article covering the memory management of xv6, continuing from the previous article which covered the memory management at the early stages of xv6’s kernel initialization before getting into its main function.
In this article, the memory management mechanism in both kernel mode and user mode is covered. Specifically xv6 uses 2-level memory paging supported by MMU (memory management unit). This is essentially the same mechanism that Linux kernel manages its memory though the number of levels is different.
entry.S jumps to
main function, it starts with the memory management setup. The first two functions,
kvmalloc set up the 2-level paging mechanism for kernel mode. After all the device initialization and interrupt setup,
userinit functions set up the memory for user mode.
Let’s take a look at the memory setup for kernel mode first. Going through it would cover the fundamentals of paging setup and actually the kernel page mapping is used in user mode memory setup as well.
The first line of
main function runs
kinit1 function which takes
*vend arguments. The call is made to allocate the memory from
end (first address after kernel loaded from ELF file) to
P2V(4*1024*1024) which would be
0x80400000 (4MB from KERNBASE: 0x80000000).
kinit1 function allocates memory space as follows:
- As covered in the part 1, kernel instructions are based on the virtual address of
- At this point, the kernel is still using the 2-level mapping,
freerange after initializing lock for the data structure of kernel memory:
vend by every
kfree casts the specified pointer to
run struct which is a single-linked list and push it into the head of
kalloc function is used to retrieve the pointer to the requested page from
We have covered how kernel allocates memory for a range by pages. Now let’s look into
kvmalloc to find out how the 2-level paging is set up.
Once you search “paging x86” or something similar online, we see this common diagram as below explaining how a virtual address is split into 3 different parts, eventually forming a physical address. At a glance, I got the idea of this conversion from virtual addresses to physical addresses, however I had difficulty understanding how an OS would make use of it. The key point here is to understand that an OS needs to setup these maps. Specifically an OS would allocate one page for a page directory and another for page table first, and it maps the arbitrary virtual address to the targeted physical address by creating the page directory entries and the page table entries. It’s also important to understand this mapping is based on the page directory address which would be stored in
CR3register. So switching the
CR3register value would change the virtual-to-physical mapping and xv6 does it per process. This whole flow is exactly what
kvmallocfunction does and its details are explained as follows.
setupkvm which sets up the 2-level memory paging structure. It starts by allocating a new page directory,
pgdir by calling
kalloc. After that, the key function here is
mappages which sets a range of physical addresses into the page tables in a specified page directory and a starting virtual address:
mappages writes physical address into the page table entries by a page size and loops till it writes all the pages in the specified size. Page table entries are retrieved by another function,
walkpgdir firstly makes the pointer to the page directory entry,
pde from the pointer to the page directory,
pgdir and the specified virtual address,
va using its highest 10 bits. Then it checks with
PTE_P flag if the page directory entry has already been allocated or not. If it’s present, it means the page directory entry already has the pointer value to the page table, so it dereferences the pointer to the page table from the page directory entry. If it’s not present, it allocates a new page for the page table, and write its address on the page directory entry. Lastly, it returns the pointer to the page table entry specified with the page table and the specified virtual address using its 10 bits in the middle:
We have covered the workflow of setting up the 2-level paging. Now we should look into the actual mapping created for the kernel:
The actual addresses of the mapping above look like this:
KERNBASE(0x80000000) to physical:
KERNLINK(0x80100000) to physical:
V2P(data)(rodata in kernel image)
DEVSPACE(0xFE000000) to physical:
kvmalloc function creates the memory mapping as above, and calls
switchkvm function which activates it by writing the address of the returned page directory on
CR3 register. The execution proceeds straight as the virtual address mapping to the physical kernel instructions are the same as the previous page directory,
Back in the kernel’s
main function, there are two calls made for user processes:
kinit2(P2V(4*1024*1024), P2V(PHYSTOP)) and
userinit(). The first call is for allocating the memory from
0x8E000000. The second call takes care of multiple things for a process including context, memory, and trap frame.
We can see
userinit function calling
setupkvm function below. This is to enable the switch to kernel mode for system calls and interrupts without switching the page directories.
setupkvm sets up the page tables for kernal codes,
inituvm, passing the page directory created and a pointer to and the size of
kalloc function to allocate a new page and resets its content to
0. After that, it calls
mappages with the virtual address
0 and the physical address of the new page, which means the virtual address
0 would be pointing to this new page in this page directory. Lastly
memmove is called to write the
init codes into the newly allocated page. This achieves the memory structure for a user process where it can just start with the
0 while keeping the access to kernel pages.
It became quite a lengthy article, but I hope I could cover how memory is managed by xv6 using the 2-level paging structure step-by-step. It was a good exercise for myself to organize my learnings as well. I hope someone would find it useful.