Link Search Menu Expand Document
CS6640

OSI Lab5: Virtual Memory

Virtual memory forms a core abstraction in modern operating systems. It improves programmability, enforces isolation and protection, and enables efficient memory utilization. To realize virtual memory, RISC-V and other modern architectures employ paging with page tables, commonly organized as radix trees.

In this lab, you will add the virtual memory support to egos-2k+. In particular, you will implement the following functions in earth/mem_vm.c:

  • page_table_map: map a virtual address to a physical address for a given process
  • page_table_switch: switch the active address space between processes
  • page_table_translate: translate a virtual address to a physical address for a given process
  • page_table_free: release all pages associated with a process’s page table

Fetch lab5 from upstream repo

  • fetch lab5 branch
    $ git fetch upstream lab5

<you should see:>
...
 * [new branch]      lab5       -> upstream/lab5
  • create a local lab5 branch
    $ git checkout --no-track -b lab5 upstream/lab5
<you should see:>
Switched to a new branch 'lab5'
  • confirm you’re on local branch lab5
    $ git status
<you should see:>
On branch lab5
nothing to commit, working tree clean
  • rebase your previous labs to the current branch
    <you're now on branch lab5>
$ git rebase lab4

    You need to resolve any conflict caused by the rebase. Read how to resolve conflict here.

  • push branch lab5 to remote repo origin
    $ git push -u origin lab5

check: after rebase/merge, your initial code should have the following:

  1. use ecall to implement syscalls (i.e., turn on ECALL in Makefile)
  2. use U-Mode for user applications (privilege level switching in grass/kernel.c)

Your egos-2k+ should be able to run. Use ls and echo to confirm everything works fine.

Section 1: Understanding virtual memory

Virtual memory requires coordinated support from both software and hardware. The operating system constructs and maintains page tables, while the memory management unit (MMU) consults these tables to perform address translation and enforce memory protection. The hardware executes these checks and translations transparently during program execution.

Exercise 1 Read document and turn on virtual memory

  • Read satp Register (Ch4.1.11) and Page-Based 32-bit Virtual-Memory Systems (Ch4.3)
  • Turn on virtual memory: in Makefile, change the line IFVM=VMOFF to IFVM=VMON.
  • In grass/kernel.c, configure all processes—system processes included—to execute in user mode.
  • Make and run egos. You will see an fatal error:
    [CRITICAL] --- Booting on QEMU with core #0 ---
[SUCCESS] Finished initializing the tty and disk devices
...
[SUCCESS] Enter the grass layer
[INFO] Load kernel process #1: sys_process
[FATAL] page_table_map is not implemented.

Section 2: Implementing virtual memory

You will implement virtual memory in the file earth/mem_vm.c. The mem_vm.c’s skeleton code has:

  • pid_to_pagetable_base[] mantains the page table root for each process.
  • pmalloc and pfree allocate and free pages in M-mode, where all addresses are physical.
  • fence() ensures that all updates to the page tables are completed before execution continues.
  • setup_identity_region() is a helper function to set virtual addresses to be the same as physical addresses for a contiguous memory region.

A. Creating page tables

Next, you will implement this page_table_map().

read and understand setup_identity_region()

Exercise 2 Creating and walking page tables

  • earth->mmu_map (page_table_map) maps a page to a process’s address space.
    Read library/elf/elf.c:elf_load() to see:
    1. how earth->mmu_map (page_table_map) is used
    2. which virtual addresses are mapped for processes
  • In earth/mem_vm.c, read the comments and implement walk() and page_table_map().
  • After finished, make and run. You should see:
    ...
[SUCCESS] Enter the grass layer
[INFO] Load kernel process #1: sys_process
[INFO] Load 0x43c4 bytes to 0x80200000
[INFO] Load 0x510 bytes to 0x80208000
[FATAL] page_table_switch is not implemented.
    • The sys_proc should be able to load successfully.
    • There is a fatal error about page_table_switch.

B. Switching address spaces

After implemeing the page_table_map, egos should be able to build the page table for the first process sys_proc, load the program (elf.c:elf_load), and then switch to run sys_proc (in grass/init.c). However, the final step of switching will fail because the page_table_switch has not been implemented.

Exercise 3 Switching address spaces

  • Read and implement page_table_switch.
  • Make and run. You should see:
    ...
[SUCCESS] Enter kernel process GPID_PROCESS
[INFO] Load kernel process #2: sys_terminal
[INFO] Load 0x3624 bytes to 0x80200000
[INFO] Load 0x254 bytes to 0x80208000
[FATAL] page_table_translate is not implemented.
    • The boot process should load the sys_terminal.
    • But booting fails because of unimplemented page_table_translate

Exercise 4 Translate addresses

  • Read and implement page_table_translate.
  • Make and run. You should see:
    ...
[SUCCESS] Enter kernel process GPID_FILE
[INFO] sys_process receives: Finish GPID_FILE initialization
[INFO] Load kernel process #4: sys_shell
[INFO] Load 0x4d68 bytes to 0x80200000
[INFO] Load 0x87c bytes to 0x80208000
[CRITICAL] Welcome to the egos-2k+ shell!
[FATAL] page_table_free is not implemented.
    • The booting should complete and egos-2k+ launches the shell.
    • The unimplemented page_table_free() is invoked by the first terminating process, cd, issued from the shell.

C. Free page tables

When a user application terminates, the kernel must reclaim all memory associated with the process. The process’s memory footprint can be identified by traversing its page table starting from the root. Implement page_table_free to release all allocated data pages, as well as the page table structures themselves.

Exercise 5 Free page tables

  • Read and implement page_table_free.
  • When finished, make and run. You should see the shell prompt.
  • To test memory leak, try to run a lot of cmds, for example:
    (echo;echo;echo;echo;echo;echo;echo;echo;echo;echo)
    to see if you run out of memory (you shouldn’t).
  • Also, there is a helper function provided by physical memory allocator (earth/mem_alloc.c) for you to check the number of free pages.
  • Read and implement page_table_free.
  • After implementation, make and run.
    The shell prompt should appear.
  • To test for memory leaks, execute many batched commands, for example: (echo; echo; echo; echo; echo; echo; echo; echo; echo; echo). Make sure that egos-2k+ does not run out of physical memory.
  • A helper function in the physical memory allocator (earth/mem_alloc.c) reports the number of free pages. I can help debug.

Finally, submit your work

Submitting consists of three steps:

  1. Executing this checklist:
    • Fill in ~/osi/egos/slack/lab5.txt.
    • Make sure that your code build with no warnings.

  2. Push your code to GitHub:

     $ cd ~/osi/egos/
 $ git commit -am 'submit lab5'
 $ git push origin lab5

 Counting objects: ...
  ....
  To github.com/NEU-CS6640-labs/egos-<YOUR_ID>.git
     c1c38e6..59c0c6e  lab5 -> lab5

  3. Actually commit your lab (with timestamp and git commit id):

    1. Get the git commit id of your work. A commit id is a 40-character hexadecimal string. You can obtain the commit id for the last commit by running the command git log -1 --format=oneline.

    2. Submit a file named git.txt to Canvas. (there will be an assignment for this lab on Canvas.) The file git.txt contains two lines: the first line is your github repo url; the second line is the git commit id that you want us to grade. Here is an example:
       git@github.com:NEU-CS6640-labs/egos-<YOUR_ID>.git
 29dfdadeadbeefe33421f242b5dd8312732fd3c9

      Notice: the repo address must start with git@github.com:... (not https://...). You can get your repo address on GitHub repo page by clicking the green “Code” button, then choose “SSH”.

    3. Note: You can submit as many times as you want; we will grade the last commit id submitted to Canvas. Also, you can submit any commit id in your pushed git history; again, we will grade the commit id submitted to Canvas.
      Notice: if you submit multiple times, the file name (git.txt) changes to git-N.txt where N is an integer and represents how many times you’ve submitted. We will grade the file with the largest N.

NOTE: Ground truth is what and when you submitted to Canvas.

  • A non-existent repo address or a non-existent commit id in Canvas means that you have not submitted the lab, regardless of what you have pushed to GitHub—we will not grade it. So, please double check your submitted repo and commit id!

  • The time of your submission for the purposes of tracking lateness is the timestamp on Canvas, not the timestamp on GitHub.

This completes the lab.