MIT 6.828: Notes from the Legendary OS Course

After spending two years at Baidu working on heterogeneous hardware, I feel that my depth of understanding of computer architecture has improved significantly. Taking advantage of this downtime, I plan to use MIT’s classic operating systems labs to fill gaps in my knowledge system. Here I record the issues and my personal understanding from each lab.

Regarding the lab environment setup, on macOS you can directly use this repo, which includes a patched gcc and toolchain components such as bintuils. Compared with the various heavily modified exe files in 30 Days to Build Your Own OS, MIT’s labs use a fully open-source GNU toolchain, which is more conducive to transferring the corresponding knowledge and techniques into real-world applications.

2023 update: MIT made major changes to this course after 2018, including switching to the RISCV architecture, so the toolchain also changed accordingly. Given that our daily work is still mainly on x86, a deep understanding of mechanisms such as virtual memory management is still very helpful, so there is no need to use the RISCV version. On the latest macOS, you need an older version of the QEMU emulator to correctly emulate a multi-core CPU; it is recommended to build the official patched version yourself, which comes with additional debugging support. In addition, the gdb toolchain also requires some manual modifications to compile successfully.

Lab 1

Q：At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?
A：After setting the cr0 register via orl $CR0_PE_ON, %eax; movl %eax, %cr0, the CPU switches into 32-bit protected mode.
Q：What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded? Where is the first instruction of the kernel?
A：The boot loader jumps to the start of the kernel code via ((void (*)(void)) (ELFHDR->e_entry))();. The jmp corresponding to this statement is the last instruction executed by the boot loader. The kernel’s own first instruction is movw $0x1234,0x472. At this point it has already jumped to the high address where the kernel code segment is loaded: 0xf0100000.
Q：How does the boot loader decide how many sectors it must read in order to fetch the entire kernel from disk? Where does it find this information?
A：This information is encoded in the corresponding fields of the ELF file—specifically, the p_filesz/p_memsz fields of the Proghdr struct.
Q：Explain the interface between printf.c and console.c. Specifically, what function does console.c export? How is this function used by printf.c?
A：console.c provides a method for outputting a single character to the console, while printf.c provides the logic for formatting strings.
Q：Explain the following from console.c:

1      if (crt_pos >= CRT_SIZE) {
2              int i;
3              memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
4              for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
5                      crt_buf[i] = 0x0700 | ' ';
6              crt_pos -= CRT_COLS;
7      }

A：This code seems to handle line wrapping and screen scrolling: when the cursor position exceeds the screen size, it moves all previous lines up, clears the last line, and then writes new characters. Screen control is implemented by writing to VGA-mapped memory.

Lab 2

Q：We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel's memory? What specific mechanisms protect the kernel memory?
A：The permission bits PTE_W in page directory entries and page table entries can control memory access permissions for programs running at different privilege levels (Ring0/3). Even if a user-mode program has PTE_W on page table entries related to kernel code/data, it still cannot modify them without PTE_U. Therefore, when creating a new struct Env, we can safely memcpy the page directory above UTOP directly. In fact, if you check the permission bits of the page table entries above UTOP, you will find that they do not set PTE_W | PTE_U at the same time; but the permissions for the page directory entries can be loosened, because both are checked together.
Later we will notice that in a multi-process environment, when an interrupt traps into kernel mode, the handler does not need to switch to the kernel’s own page directory; it can continue to “borrow” the process’s original one. This is because the user program’s page directory above UTOP is an exact copy of the kernel’s page directory—essentially an implementation simplification: as long as we agree on which address range kernel code/data is loaded into and make it read-only to user mode, it works. However, during process switching we do need to switch to the target process’s page directory, because the memory mapping below UTOP is isolated between processes; this is a basic abstraction created by the OS for processes.
Q：What is the maximum amount of physical memory that this operating system can support? Why?
Q：How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?
Q：Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?
A：After loading the page table, the kernel address space based at 0xf0000000 (KERNBASE) can be accessed directly. At this point, %eip can jump directly into the high kernel address space. This is done via mov $relocated, %eax; jmp *%eax, where $relocated is linked to $0xf010002f. When writing such code, since the early kernel runs in the low address space rather than the linker’s target address space, before completing the address-space transition you must ensure all code is position-independent. If not, you must perform address fixups.

Lab 3

Q1

What is the purpose of having an individual handler function for each exception/interrupt? (i.e., if all exceptions/interrupts were delivered to the same handler, what feature that exists in the current implementation could not be provided?)

From the code implementation, most handlers actually reuse the same logic. The only difference is distinguishing whether the interrupt carries an error code. So if only one handler could be set, all interrupts would by default need to push an error code. That said, my understanding is that this seems like a historical compatibility artifact.

2023 update: When the CPU receives an interrupt, it only looks up the handler in the IDT, but it does not know which specific interrupt was triggered. Therefore, if all interrupts were handled by a single handler, software would be unable to distinguish the interrupt vector.

Q2

Did you have to do anything to make the user/softint program behave correctly? The grade script expects it to produce a general protection fault (trap 13), but softint's code says int 14. Why should this produce interrupt vector 13? What happens if the kernel actually allows softint's int 14 instruction to invoke the kernel's page fault handler (which is interrupt vector 14)?

The DPL of the PAGEFAULT interrupt should be set to disallow user access, because a page fault should only be triggered when accessing an unmapped memory region. If user space is allowed to trigger this interrupt directly, the CR2 register is not set correctly, which may lead to incorrect operations on the page tables.

Q3

The break point test case will either generate a break point exception or a general protection fault depending on how you initialized the break point entry in the IDT (i.e., your call to SETGATE from trap_init). Why? How do you need to set it up in order to get the breakpoint exception to work as specified above and what incorrect setup would cause it to trigger a general protection fault?

It depends on the DPL (Descriptor Privilege Level) set during initialization—if it is 3, user mode is allowed to trap via int3; otherwise, it triggers a protection exception.

Q4

What do you think is the point of these mechanisms, particularly in light of what the user/softint test program does?

Interrupt service routines must not be callable arbitrarily by user programs; otherwise they create kernel security risks, so their privileges must be strictly constrained. This involves a question: which interrupts are allowed to be invoked by user space? The Intel manuals specify the following:

The INTO, INT 3, and BOUND instructions permit exceptions to be generated in software. These instructions allow checks for exception conditions to be performed at points in the instruction stream. For example, INT 3 causes a breakpoint exception to be generated.

About the interrupt masking bit

A concept that is somewhat hard to distinguish here is what to set istrap to when setting up interrupt vectors. Stack Overflow has the following concise summary:

A trap is an exception in a user process. It's caused by division by zero or invalid memory access. It's also the usual way to invoke a kernel routine (a system call) because those run with a higher priority than user code. Handling is synchronous (so the user code is suspended and continues afterwards). In a sense they are "active" - most of the time, the code expects the trap to happen and relies on this fact.

An interrupt is something generated by the hardware (devices like the hard disk, graphics card, I/O ports, etc). These are asynchronous (i.e. they don't happen at predictable places in the user code) or "passive" since the interrupt handler has to wait for them to happen eventually.

But in xv6’s code, you can see that except for SYSCALL, all other interrupt vectors are set as istrap=false, i.e., interrupts are masked during handler execution. This is because JOS makes an important simplification compared to xv6: external interrupts are not re-entrant, so we only need to care about saving and restoring EFLAGS when entering and leaving kernel mode.

Extending the discussion: what happens if we continuously do not respond to any external hardware interrupts? For timer hardware, if the interrupt cannot be delivered, it just tries again next time; it does not maintain any internal state for this. For more complex devices such as a hardware accelerator card on PCIe, there may be a FIFO storing interrupt information for completed tasks. Once the FIFO is full, it will apply backpressure to all hardware units, blocking the execution of more tasks.

Exercise 9

If you now run user/breakpoint, you should be able to run backtrace from the kernel monitor and see the backtrace traverse into lib/libmain.c before the kernel panics with a page fault. What causes this page fault? You don't need to fix it, but you should understand why it happens.

Because when backtracing %ebp, it accesses a page that is not mapped in kernel mode—the page used by the user stack.

Lab 4

Q1

Compare kern/mpentry.S side by side with boot/boot.S. Bearing in mind that kern/mpentry.S is compiled and linked to run above KERNBASE just like everything else in the kernel, what is the purpose of macro MPBOOTPHYS? Why is it necessary in kern/mpentry.S but not in boot/boot.S? In other words, what could go wrong if it were omitted in kern/mpentry.S?
Hint: recall the differences between the link address and the load address that we have discussed in Lab 1.

Because this assembly code mpentry.S is linked at the high kernel address KERNBASE, but at runtime it is loaded into a low physical address. Therefore, all instructions involving address symbols need to be recalculated—i.e., relocated to use MPENTRY_PADDR as the base address. This is not needed for boot.S because the linker script loads it at 0x7C00 in the first place.

Q2

It seems that using the big kernel lock guarantees that only one CPU can run the kernel code at a time. Why do we still need separate kernel stacks for each CPU? Describe a scenario in which using a shared kernel stack will go wrong, even with the protection of the big kernel lock.

The main reason each core uses its own stack is interrupt safety. When interrupts occur simultaneously on multiple cores, using a shared stack space will create data hazards when pushing registers, because the hardware’s automatic stack push behavior is not protected by the big kernel lock.

Q3

In your implementation of env_run() you should have called lcr3(). Before and after the call to lcr3(), your code makes references (at least it should) to the variable e, the argument to env_run. Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. But a virtual address (namely e) has meaning relative to a given address context--the address context specifies the physical address to which the virtual address maps. Why can the pointer e be dereferenced both before and after the addressing switch?

struct Env *e is essentially a variable on the kernel stack. Since the user address space mappings are copied from the kernel address space, the mapping for the kernel stack is also copied, so this pointer can be accessed in user mode in a read-only way—but it cannot be modified.

Q4

Whenever the kernel switches from one environment to another, it must ensure the old environment's registers are saved so they can be restored properly later. Why? Where does this happen?

We need to save the previous user program’s context because the next scheduled program will clobber all register state. A user-mode program traps into the kernel via the int 0x30 software interrupt. In _alltraps, pushal saves all user-mode context onto the kernel stack, and it is then copied into the current Env struct (curenv->env_tf = *tf). Therefore, in env_run(), we can switch back to the correct context via env_pop_tf().

About `UVPT`

When implementing the user-space fork() call, to establish the child process’s page table mappings we need to access the current process’s page tables. Since this is fundamentally a safe operation, there is no need to provide this functionality as a system call; instead, we directly map the page tables into the kernel address space.

About the marking order of `PTE_COW`

Note: The ordering here (i.e., marking a page as COW in the child before marking it in the parent) actually matters! Can you see why? Try to think of a specific case where reversing the order could cause trouble.

Why do we need to mark ours copy-on-write again if it was already copy-on-write at the beginning of this function (duppage())?

If we mark the parent’s page as COW first, it may be written within the fork() context and trigger a page fault (for example, if the page is stack space). That would allocate a new page with write permission; after the old page’s reference count is decremented by 1, it could be reclaimed immediately. Then we map the new page to the child process, resulting in an error where for a given physical page, the child has COW permission while the parent can write to it directly. If we map the page as COW to the child first, the page’s reference count is increased, preventing it from being freed incorrectly.

For similar reasons, even if the current page is COW at the beginning of the function, it may still be written during execution. This can cause the current page to become writable and be mapped to the child process. Therefore, at the end of the function we need to mark it as COW again to avoid permission errors.

About system call overhead

The Challenge section mentions using batching to issue syscalls in bulk to reduce user-kernel switching overhead. Considering the substantial overhead introduced by a switch—saving/restoring context and jumps—modern Linux systems do optimize this in practice. Another thing worth noting is that QEMU is only a functional emulator and does not accurately emulate TSC-related instructions, so it cannot be used for performance profiling; you must use real hardware. In fact, there should currently be no cycle-accurate x86 simulator.

Lab 5

Q1

Do you have to do anything else to ensure that this I/O privilege setting is saved and restored properly when you subsequently switch from one environment to another? Why?

No, because management of the EFLAGS register is automatically included in the process context switch.

Q2

We implemented spawn rather than a UNIX-style exec because spawn is easier to implement from user space in "exokernel fashion", without special help from the kernel. Think about what you would have to do in order to implement exec in user space, and be sure you understand why it is harder.

Here, spawn essentially creates a new process, sets its entry point, and then changes its status to RUNNABLE. If we wanted to implement exec, the difficulty is how to correctly overwrite the current process’s code segment: for spawn, the process is not running so it can be overwritten freely; but for exec, the current process is still executing user-space code, so overwriting it arbitrarily would break the next instruction.

Lab 6

Q1

How did you structure your transmit implementation? In particular, what do you do if the transmit ring is full?

My choice was: if the syscall fails, occupy the CPU and poll until the packet can be transmitted. Given the NIC hardware efficiency, this is a low-probability event, so it is acceptable to sacrifice CPU efficiency to reduce latency. Since in the TCP/IP stack implementation it directly calls blocking ipc_send to send packets to the output process, if the NIC driver’s ring buffer is full and the syscall fails, the output process will not enter the IPC recv state, which then causes the core network process to enter sys_yield and be suspended until the ring buffer has a free slot to send a packet. A further optimization would be to introduce an additional dynamically allocated buffer in the output process to handle driver ring buffer overflow, so the core network process can avoid being suspended. Fundamentally, when production exceeds consumption, you must introduce additional buffering to avoid blocking.

Q2

How did you structure your receive implementation? In particular, what do you do if the receive queue is empty and a user environment requests the next incoming packet?

Compared with transmitting packets, the receive ring buffer is trickier. First, in hardware it relies only on RDH==RDT to determine whether the buffer is full, so the key is how to initialize RDT. Since hardware must write the buffer sequentially, we assume the driver maintains a variable read_pos pointing to the first readable position in the buffer. After each successful read, we update RDT = read_pos; read_pos += 1. This is because one packet has been consumed, so the freed descriptor can be placed at the tail of the ring buffer, and the next readable descriptor must be at the next position. This update logic implies that after every successful read, read_pos=RDT+1 always holds. Therefore, as long as we also make this condition hold initially, we can avoid maintaining the intermediate variable read_pos in the driver. On the first read, clearly we need read_pos=0, which means RDT=RDLEN-1.

Challenge 1

These extra “challenge” problems in the lab are not that hard to think through, but since there is a lack of framework code and “pitfall avoidance” guidance, it is still easy to step on landmines during implementation. I only picked one that was relatively easy to test, but it still took me a full day. The final code is this commit.

If the transmit queue is full or the receive queue is empty, the environment and your driver may spend a significant amount of CPU cycles polling, waiting for a descriptor. The E1000 can generate an interrupt once it is finished with a transmit or receive descriptor, avoiding the need for polling. Modify your driver so that processing the both the transmit and receive queues is interrupt driven instead of polling.

Below are some points to pay attention to:

Receiving and responding to PCI device interrupts requires some background knowledge of the 8259A. The OSDev wiki has detailed explanations and sample code. Pay attention to the difference between the two interrupt-state-related registers IRR and ISR.
A PCI device’s IRQ line is assigned when the device is enabled, but the interrupt vector table is initialized in a fixed manner by the system, so you need to design some mechanism to register the device driver’s interrupt handler into the IDT.
In the implementation of the NIC driver e1000_recv_packet, after the user process traps into the kernel via a syscall, if it needs to wait for I/O and the process is suspended, there is no way to save and restore the kernel-mode execution context exactly. Then, when a “data readable” interrupt arrives, we do not know where to write the data back. My implementation used a shortcut: modify eax to return an error code to user mode, and then set curenv->env_status = ENV_NOT_RUNNABLE to suspend the process; then in user-mode sys_packet_recv, if it detects the error code it keeps retrying. This way, after the interrupt handler marks the process as ENV_RUNNABLE and execution resumes, although it returns an error code directly to user mode, the data is already readable, and user space retries after seeing the error, naturally obtaining the data, while also avoiding the complex logic of saving execution context in kernel mode.
In the interrupt handler context, how do we know which input process to wake up? My approach is simple and somewhat brute-force: since there is only one process responsible for network input, just store its env ID in a static variable. Strictly speaking, the NIC driver should maintain a data structure to record suspended processes.