# Shells, and the Reference Kernel ## CS 326 Operating Systems L20 · November 12, 2026 · exercise `46k_shell` --- ## Learning Objectives - Explain the OSlings staging model and what survives an unfinished exercise - Distinguish **building** a kernel from **extending** one - Trace a keystroke from UART through PLIC and ring buffer to the line buffer - Describe tokenization as producing **borrowed views**, not new strings - Argue from `fork`/`exec` why `cd` must be a shell built-in - Enumerate the kernel shell's privileges and name the exercises that remove them --- ## First: what is in your tree today Exercise `46k_shell` stages **20 files** into `rv6/src`. - **17 are byte-identical** to the exercise-15 *reference* solution - `fs.rs` = the exercise-10 filesystem + `is_dir` (`fs.rs:169`) and `for_each_entry` (`fs.rs:175`) - `main.rs` gains a test harness - `shell.rs` is new, and is the **only file with an `IMPLEMENT` marker** <div class="highlight-box"> The kernel underneath your shell is the <strong>reference</strong> kernel — not necessarily the code you typed. </div> --- ## This is the mechanic, not a judgment It has worked this way since exercise `30k`: - Every skeleton contains the **reference version of everything before it** - `archive_work` (`model.rs:712`) copies your whole staging directory into `my-work/<exercise>/` before *any* overwrite - `stage_exercise` (`model.rs:740`) restores from `my-work/<target>/` when it exists <div class="info-box"> The kernel you extend today is the reference one; your own code is archived in <code>my-work/</code> and one command away. </div> --- ## `goto` is lossless in both directions <div class="mermaid"> flowchart LR A["you are at 46k_shell"] -->|"oslings goto 43k"| B["archive_work:\nrv6/src to my-work/46k_shell/"] B --> C{"my-work/43k_traps\nexists?"} C -->|yes| D["restore YOUR 43k code"] C -->|no| E["stage the 43k skeleton"] D --> F["edit, run, learn"] E --> F F -->|"oslings goto 46k"| G["archive 43k work,\nrestore my-work/46k_shell/"] </div> Two caveats: `my-work/<ex>/` is **one snapshot per exercise**, and `oslings reset` always stages the pristine skeleton. Git is the durable record — `oslings submit` every session, red or green. --- ## From building to extending Until now: *this subsystem does not exist; write it.* From here: *this kernel exists; add a capability without breaking it.* Reading for **interfaces**, not implementations. Three questions: 1. **What does it promise?** `dirlookup(dir, name)` → `Ok(inum)` / `Err(FsError)` (`fs.rs:109`) 2. **What does it require?** names are raw bytes; the FS is behind one lock (`fs.rs:277`) 3. **What invariant must I not break?** do not hold the guard longer than needed That is what almost all real kernel work is. --- ## The rest of the map | Exercise | What it adds | The wall | |---|---|---| | `46k_shell` | a REPL and four commands, in the kernel | none yet | | `47k_file_commands` | `touch`, `cat`, `rm`, `rmdir`, `echo >` | none yet | | `48k_user_mode` | U-mode, `PTE_U`, trampoline, trapframe | **built here** | | `49k_exec` | load a program image, push `argv` | behind it | | `50k_file_descriptors` | per-process fd table | behind it | | `51k_fork_wait` | make a process, reap it | behind it | | `52k_userland` | the shell moves into user mode | behind it | --- ## A shell is a loop ```text print "rv6$ " loop { c = getc() # READ (one byte, blocking) if c is Enter: exec(line) # EVALUATE + PRINT line.clear() print "rv6$ " # LOOP else if c is Backspace: erase one character else if c is printable: line.push(c); echo it else: drop it } ``` `run` (`shell.rs:343`), about 30 lines. Signature is `pub fn run() -> !`: it never returns, because there is no `init` to return to. --- ## Shells since 1971 - **"Shell"** is Louis Pouzin's word — CTSS RUNCOM, then Multics: the replaceable outer layer around the resident supervisor - **Thompson's sh** (V1 Unix, 1971): a few hundred lines, already had `<` and `>` - **Pipes** arrive 1973, at McIlroy's insistence - **Bourne sh** (V7, 1979): the grammar we still write - **csh** (1978), **ksh**, **bash** (1989), **zsh** <div class="info-box"> Every one of them is still that loop. What differs is only how hard the <em>evaluate</em> step works. </div> --- ## Where the bytes come from ```text you press 'k' | v +-----------+ raises IRQ 10 +--------+ S-mode external +-----------+ | UART 16550| ---------------->| PLIC | ------------------->| kerneltrap| +-----------+ +--------+ (scause = 9) +-----------+ | console::intr (console.rs:68) | claim -> drain -> complete v +-----------------+ | ring buffer | | BUF[256] | | HEAD ... TAIL | +-----------------+ ^ shell::run -> console::getc (console.rs:47) | loop { try_getc()? ; wfi } ---- pops one byte ----+ ``` --- ## Three details that matter - **The handler does almost nothing.** Claim, drain into the ring (`console.rs:18`), complete. No parsing, no printing — the top-half / bottom-half split every driver uses - **The ring needs no lock.** One producer, one consumer, separate `HEAD`/`TAIL` (`console.rs:14`) — airtight on one hart, dead on two - **`wfi` is not a busy-wait.** Empty buffer halts the CPU until an interrupt (`console.rs:52`); an idle prompt burns no cycles --- ## Line discipline: who owns the backspace? Something must buffer the line, erase a character, make it vanish from the screen, and decide Enter ends the line. | | rv6 | Unix | |---|---|---| | Lives in | the shell (`shell.rs:349`-`371`) | the kernel tty layer | | Mode | there is only one | *canonical*; `ICANON` off for raw | | Echo done by | the shell (`shell.rs:366`) | the tty driver | <div class="highlight-box"> Because the shell echoes, a password prompt is impossible today: nothing can read a byte without showing it. </div> --- ## Two consequences you can read off the code ```rust 0x7f | 0x08 => { // shell.rs:357 if line.pop().is_some() { out.puts("\x08 \x08"); } } c if c.is_ascii_graphic() || c == b' ' => { /* keep + echo */ } _ => {} // shell.rs:370 — silently dropped ``` - Erasing takes **three bytes**: backspace, space, backspace. A terminal's BS only moves the cursor - Tab, Ctrl-C, ESC: no echo, no beep, no entry in the line - Up-arrow is `1B 5B 41` → `ESC` dropped, `[` and `A` are graphic → your line grows `[A` --- ## Tokenizing: words, not characters ```rust let mut words = line.split_whitespace(); // shell.rs:40 let cmd = match words.next() { Some(c) => c, None => return, // blank line: do nothing }; let arg = words.next().unwrap_or(""); ``` `split_whitespace` **allocates nothing and copies nothing**. This heap serves one whole 4 KiB page per allocation (`kheap.rs:26`) and can fail — a parser that allocates per token can fail on a long command line. --- ## A token is a *view* ```text line: String "mkdir docs\0..." ^^^^^ ^^^^ | | cmd ----+ | cmd = &line[0..5] len 5 arg --------------+ arg = &line[8..12] len 4 no allocation, no copy, no NUL bytes written ``` It borrows the line, so the line must outlive it: `line.clear()` happens **after** `exec` returns (`shell.rs:354`), and the borrow checker enforces that. C's `strtok` instead writes `\0` over each separator — input destroyed, position kept in a **static**, not reentrant. rv6's user-mode shell does exactly that, in assembly (`exec.rs:389`-`421`). One idea, length kept in two places: Rust in the slice, C in a terminator. --- ## Where rv6's parser stops | Feature | rv6 kernel sh | rv6 user `sh` | xv6 `sh` | bash | |---|---|---|---|---| | split on whitespace | yes | yes | yes | yes | | quoting, escapes | no | no | no | yes | | globbing, `$VAR` | no | no | no | yes | | redirection | one special case | no | yes | yes | | pipelines | no | no | yes | yes | | job control, scripts | no | no | no | yes | `echo "hello world"` writes the quote characters literally. Not a bug — the scope line. <div class="info-box"> A shell is a <strong>text-to-argv transformer</strong>. Every feature above is a rule about that: quoting says "these spaces are not separators", globbing says "this word expands to many". xv6's <code>sh.c</code> does the Bourne core in ~400 lines of C. </div> --- ## Why `echo >` has to cheat ```rust // cmd_echo — shell.rs:212. Takes the RAW LINE, not the tokens. let rest = line.strip_prefix("echo").unwrap_or(line).trim_start(); match rest.split_once('>') { None => { out.puts(rest); out.puts("\n"); } Some((text, file)) => { /* write text.trim() + '\n' into file.trim() */ } } ``` `split_whitespace` already destroyed what a redirect needs: where words ended, whether `>` was attached, where the text stops. <div class="highlight-box"> Words are a <strong>lossy</strong> representation of a command line. Real shells emit typed tokens (WORD, IO_NUMBER, <code>></code>, <code>|</code>) and parse a tree. </div> --- ## Dispatch: one table ```rust match cmd { // shell.rs:47-63 "pwd" => self.cmd_pwd(out), "ls" => self.cmd_ls(out), "cd" => self.cmd_cd(arg, out), "mkdir" => self.cmd_mkdir(arg, out), // touch, cat, rm, rmdir, echo, run, progs _ => { out.puts(cmd); out.puts(": command not found\n"); } } ``` --- ## Why a table, not a chain of `if`s - **One point of truth** — the whole language in 15 lines; a new command touches two places - **Uniform handler signature** — `fn(&mut self, arg, &mut dyn Out)`, which is what lets a table later become *data* (see `syscall.rs:35`) - **Exhaustiveness** — `match` forces the `_` arm, so "command not found" exists once (`shell.rs:59`) - **Separation** — `exec` decides *which*, the handler decides *how* Cost: a `match` on `&str` is a decision tree (length, then `memcmp`) — never a jump table. And it is **compiled in**, which is why bash needs a `$PATH` hash instead. --- ## Built-in, or program? <div class="mermaid"> flowchart TD A["line"] --> B["tokenize to argv"] B --> C{"argv[0] is a built-in?"} C -->|yes| D["call it in THIS process\ncd, exit, export, umask"] C -->|no| E["search PATH for an executable"] E --> F["fork: make a child"] F --> G["child: exec the program\nnever returns on success"] G --> H["parent: wait for the child"] D --> I["print prompt"] H --> I </div> Everything today takes the left branch — rv6 cannot start a process at all yet. --- ## The `Out` trait: where output goes ```rust pub trait Out { // shell.rs:17 fn puts(&mut self, s: &str); } ``` - `ConsoleOut` (`shell.rs:334`) → the UART - the harness's `BufOut` → a 512-byte array a test can read back <div class="info-box"> Same idea as file descriptor 1: a program does not know where its output goes. <code>Out</code> is the kernel-sized version — and exercise 50k replaces it with the real thing. </div> --- ## The cwd: two places you could keep it | | rv6 today | Unix | |---|---|---| | Stored in | the shell's `Vec` (`shell.rs:23`) | the PCB (`p->cwd`, `fs_struct`) | | Known to the kernel | no | yes | | Inherited by `fork` | n/a | yes — a **copy** | | Survives `exec` | n/a | yes | | Changed by | mutating a `Vec` | the `chdir` system call | Path resolution happens in the kernel on every `open` — so the cwd has to be somewhere the kernel can see. --- ## Why `cd` cannot be a program <div class="mermaid"> sequenceDiagram participant S as shell (cwd = /) participant C as child process participant K as kernel S->>K: fork() K-->>C: child created, cwd = / (a COPY) C->>K: chdir("/docs") K-->>C: child cwd = /docs C->>K: exit(0) S->>K: wait() Note over S: shell cwd is STILL / </div> xv6 `sh.c`: *"Chdir must be called by the parent, not the child."* The rule: **anything that must mutate the shell's own process state must be a built-in** — `cd`, `exit`, `export`, `umask`, `ulimit`, `exec`, `read`. --- ## An inode number is an index, not a claim - **`pwd` prints remembered names**, captured at `cd` time (`shell.rs:69`). Real `getcwd(3)` walks *upward* through `..` and fails with `ENOENT` if the directory was deleted - **rv6 cannot walk upward**: no `.` or `..` entries exist, so `cd ..` is a `Vec::pop` (`shell.rs:94`) — the stack is the only record of the parent chain - **Nothing stops `rmdir` freeing the inode you are standing in.** In Unix a cwd is a *reference*; the inode survives until the last one goes — which is why deleting an open file works rv6 has **no `chdir`** at all (`syscall.rs:21`-`29`), so the 52k user shell has no `cd`. --- ## The design smell, said plainly `shell.rs` is compiled into the kernel and runs in **S-mode**. It can: - read and write **any** page the kernel maps — all of RAM - write any CSR: disable interrupts, replace `stvec`, change `satp` - touch every device register, including the one that halts QEMU - corrupt the free list, process table, or filesystem with one bad index - take a spinlock and never give it back `cmd_ls` holds the FS lock across `out.puts` (`shell.rs:79`-`88`), and `SpinLock::lock` (`spinlock.rs:22`) is **not reentrant**. --- ## What that costs | Property | Kernel shell (today) | User shell (52k) | |---|---|---| | A bad index | panics the kernel | faults the process | | Blast radius | the whole machine | one address space | | Replaceable | rebuild the kernel | it is a file | | Runs untrusted code | never | that is the point | | Interface to the OS | direct calls | nine system calls | <div class="highlight-box"> The last row is the deep one: the wall is what forces the kernel to have an <strong>ABI</strong> instead of "whatever happens to be <code>pub</code>". </div> --- ## The fix, by exercise number - **`48k_user_mode`** builds the wall: `sstatus.SPP` + `sret`, `PTE_U`, trampoline, trapframe, the first `ecall` - **`49k_exec`** loads a program image and pushes `argv` - **`50k_file_descriptors`** makes `write(1, ...)` mean something - **`51k_fork_wait`** makes and reaps processes - **`52k_userland`** moves the shell across: `sh` (`exec.rs:354`) prompts `$ `, reads with `read(0, ...)`, and runs commands with `fork` + `exec` + `wait` (`exec.rs:437`-`458`) Why write the privileged one at all? Because you cannot write the unprivileged one yet. --- ## Why Unix drew the line here - Every system had a command interpreter; the question is whether it is **privileged and fixed** - CP/M and MS-DOS: `COMMAND.COM` had unlimited access because the hardware offered no alternative - Ritchie and Thompson (CACM, 1974): the shell is an **ordinary, unprivileged user program with no special status** - So you can replace it (`chsh`), nest it, script it, debug it, kill it - And permission checks belong to the **kernel** — the shell asks, the kernel decides --- ## Summary 1. **Your tree holds the reference kernel** — 17 of 20 files byte-identical to 45k; `shell.rs` is the only `IMPLEMENT` 2. **Nothing you wrote is gone** — `my-work/` + `oslings goto`, lossless both ways 3. **The job is now extending, not building** — read for interfaces 4. **A shell is a loop**: read, evaluate, print, repeat (`shell.rs:343`) 5. **Tokens borrow, they do not allocate** (`shell.rs:40`) 6. **Dispatch belongs in a table** (`shell.rs:47`) — and the second branch is fork/exec/wait 7. **cwd is process state**, which is why `cd` is a built-in 8. **This shell has powers no shell should have** — 48k builds the wall, 52k moves the shell behind it --- ## Today's exercise ```sh oslings update oslings run 46k_shell # or: oslings watch cd rv6 && cargo run # boots to a rv6$ prompt ``` Try: `mkdir docs`, `ls`, `cd docs`, `pwd`, `mkdir notes`, `ls`, `cd ..`, `pwd`. Exit QEMU with **Ctrl-A** then **X**. <div class="info-box"> Read the exercise README first — it teaches <em>how</em>. This deck was the <em>why</em>. </div>