Extension labs · lab 3 · The system-call and trap path · ★★☆☆☆

ps: a safe snapshot of the process table

You add a system call, procinfo(struct pinfo *buf, int max), that copies one record per in-use slot of the process table into a user buffer: pid, parent’s pid, state, size, name, and the hart the process is running on. On top of it you write ps.

Copying fields out of proc[] sounds like ten lines of code. It is, but the table is being changed by three harts while you read it: processes are created, scheduled, put to sleep, turned into zombies and reaped, and each field is guarded by a different rule. So the real questions are about reading shared state. Which lock, if any, protects each field you want? In which order may you take two of them? Is it safe to touch user memory while you hold one, in this kernel? What can a “snapshot” promise when the table never stands still, and what can it not? And why does the kernel’s own procdump get away with taking no lock at all?

You will answer each of these by reading the code, then check your answers against real runs on three harts: a deadlock caught with gdb (the GNU debugger) on all three harts, records torn in half by a missing lock, and a snapshot that honestly shows four processes running on a three-hart machine.

Read first: Tour 5: Life of a system call, Tour 6: System-call arguments and user pointers, Tour 12: One scheduler per hart, Tour 13: swtch and the lock handed across a context switch, Tour 18: Lock ordering: how xv6 avoids deadlock, Tour 20: fork, Tour 21: exit, wait and zombies, Tour 28: Crossing the user/kernel boundary in memory · Locks and interrupt state

What this lab teaches

How to find out which lock, if any, protects each field of struct proc, from the code that writes it rather than from the comments alone.
How the order of wait_lock and p->lock is fixed by code that already exists, and what three harts do when a new path takes the two locks the other way round.
What copyout can and cannot do in this tree (sleep? fault? take locks?), and what that means for calling it with a lock held.
What can a snapshot gathered one slot at a time promise, while three harts keep changing the table, and what can it not?
How the scheduler’s c->proc tells you which hart runs a process, and why the answer stops being true the moment you let go of the lock.
Why a debugging aid that runs from an interrupt handler on a possibly stuck machine follows different rules from a system call.

The reference branch

ext/03-procinfo in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 6 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-procinfo 06aad25   # start your own
git diff 06aad25 origin/ext/03-procinfo   # only when you want the answer

1. The spec

The system call. int procinfo(struct pinfo *buf, int max) fills buf with at most max records, one for each slot of proc[] that is not UNUSED, in slot order, and returns the number of records written. It returns -1 if max is negative or if buf cannot be written; max larger than NPROC is treated as NPROC. max == 0 writes nothing and returns 0. The number is 23.

The record (kernel/pinfo.h, shared by the kernel and user programs):

struct pinfo {
  int pid;
  int ppid;      // parent's pid, 0 if none
  int state;     // enum procstate in proc.h: 1 USED .. 5 ZOMBIE
  int cpu;       // hart running it if RUNNING, else -1
  uint64 sz;     // size of user memory (bytes)
  char name[16]; // always NUL-terminated
};

What a record must get right. pid and state belong to the same moment. cpu is a hart number exactly when state is RUNNING, and -1 otherwise. A non-zero ppid is the pid of the process’s parent. name is always a terminated string. The kernel must never write more than max records into the user’s buffer.

The program. ps prints one line per record:

$ ps
PID   PPID  STATE   CPU  SIZE    NAME
1     0     sleep   -    16384   init
2     1     sleep   -    20480   sh
3     2     run     1    16384   ps

The test. procinfotest checks five things and prints OK or FAIL for each: its own record (RUNNING, on a hart, with its name); a child seen as SLEEPING, then ZOMBIE, then gone after wait; that max limits what is written and returned; that bad buffers return -1 and a lazily allocated one works; and, for 20 ticks while other processes fork and exit as fast as they can, that every snapshot (taken with room for all NPROC slots) has valid pids and states, no pid twice, a hart exactly in the RUNNING records, and every non-zero ppid present in the same snapshot, and that at least 100 processes were really created meanwhile. Every check is made by the program itself, so the last line says 5 checks OK only if all five held. (It does not check that names are terminated; ps relies on that.)

Constraints. Existing behaviour must not change, and usertests -q must still print ALL TESTS PASSED on three harts. Do not change any lock rule of struct proc.

2. Think first

Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.

1Which lock protects each field you want to report?

Your record has six fields: pid, parent’s pid, state, size, name, and the hart a process is running on. For each one, find every piece of code that writes it and note which lock that code holds while it writes. Which fields can a lock you take make safe to read, and which can’t?

The reference design

Field	Written by	Lock the writer holds
`state`	`allocproc`, `userinit`, `kfork`, `kexit`, `yield`, `sleep`, `wakeup`, `kkill`, `scheduler`, `freeproc`	that process’s `p->lock`, always
`pid`	`allocproc` (`kernel/proc.c:125`), `freeproc` (`kernel/proc.c:165`)	`p->lock`
`parent`	`kfork` (`kernel/proc.c:297`), `reparent` (`kernel/proc.c:316`), `kwait` (`kernel/proc.c:397`)	`wait_lock`
`sz`	`growproc` (`kernel/proc.c:252`), lazy `sbrk` (`kernel/sysproc.c:62`), `kexec` (`kernel/exec.c:135`); also `kfork` for the child and `freeproc`	none for the process’s own writes
`name`	`kexec` (`kernel/exec.c:130`); also `kfork` for the child and `freeproc` (`name[0] = 0`)	none for `kexec`
hart	`c->proc = p` and `c->proc = 0` in `scheduler` (`kernel/proc.c:452`, `kernel/proc.c:460`)	the `p->lock` of the process `c->proc` points to

So p->lock makes state, pid and the hart readable together, wait_lock makes parent readable, and nothing you can take makes sz and name safe: their owner writes them while it runs, perhaps on another hart at this very moment, without any lock. The comment in proc.h calls them “private to the process”, which is exactly right for the process itself and exactly the problem for anybody else. (kfork and freeproc write them under p->lock, but that only covers a child that cannot run yet and a slot that is being freed.)

Check yourself

1warm-upMatch the pairs

Match each field with what protects it against concurrent writers.

p->statep->parentp->namecpus[i].proc

2solidTrue or false, and why

True or false: if procinfo holds p->lock while it copies p->name, it can never see a name that is half the old program’s and half the new one’s.

TrueFalse

Why?

False: kexec writes p->name without taking p->lock, so the copy can overlap the write.False: names are written one byte at a time by printk.True: p->lock disables interrupts, so the process cannot run while you copy.True: a process cannot run while another hart holds its p->lock.

2What do max and the return value mean?

The caller passes a buffer with room for max records. The table may hold more in-use slots than that, or fewer, and it can change between two calls. Decide what the kernel writes, what it returns, and what it does with a negative max, with max == 0 and with max larger than the table.

Check yourself

1warm-upType a number

Five slots of proc[] are in use. A program calls procinfo(buf, 2). With the reference contract, what does the call return?

decimal, 0x hex or 0b binary

3How do you read the parent's pid, and in what order do you take the locks?

parent is protected by wait_lock, the rest of the record by p->lock. Where do you take wait_lock: once around the whole scan, once per slot just before its p->lock, or per slot after its p->lock? What does each choice guarantee, and what does it cost? And once you have the parent pointer, may you read the parent’s pid without holding the parent’s p->lock?

The reference design

The order is fixed by the code that already holds both. kwait holds wait_lock and acquires each child’s p->lock (kernel/proc.c:384), and while still holding it calls killed, which takes its own p->lock (kernel/proc.c:408). kexit holds wait_lock while wakeup takes every p->lock in turn (kernel/proc.c:353), then takes its own (kernel/proc.c:355). The comment says it plainly: wait_lock “must be acquired before any p->lock”. kfork even releases the child’s lock (line 294) before taking wait_lock, to obey it. So procinfo takes wait_lock first.

Taking it inside the loop, after p->lock, closes a cycle:

Time	Hart 1: `kwait` in a parent	Hart 2: `procinfo` (wrong order)
1	acquires `wait_lock`	acquires the parent’s `p->lock` (slot 4)
2	`killed(p)`: wants slot 4’s `p->lock`, spins	wants `wait_lock`, spins
3	spins forever	spins forever

Clinic 2 is a recording of exactly this, with the third hart caught too.

Taking wait_lock per slot, before that slot’s p->lock, respects the order and keeps each hold short, and it still gives every record a correct ppid for the moment it was read. What it loses is the table-wide part: between two slots a parent can exit and be reaped, so a child’s ppid may name a process missing from the snapshot. Holding wait_lock around the whole scan buys exactly that: no parent link can change, no process can become a zombie (kexit sets ZOMBIE under it) and none can be reaped until the scan is over, so the parent column is consistent across the snapshot. That guarantee is why the reference holds it for the whole scan.

The cost is that every fork, exit and wait on the other harts waits for the scan. That is the same kind of hold the kernel already makes: kexit holds wait_lock across wakeup(p->parent), a scan of all 64 p->locks, and kwait scans every slot under it. An instrumented run under procinfotest’s fork/exit churn measured procinfo’s scan at about 50 to 80 µs on average, comparable to how long kfork, kexit and kwait each already wait for wait_lock under that churn without any procinfo (means of about 40 to 95 µs); with procinfo called back to back, forks per 20 ticks fell by 0 to 35% across runs (noisy).

The parent’s pid needs no second p->lock. pid is written by allocproc, on a slot that is UNUSED and so nobody’s parent, and by freeproc. A process that has children is freed only by kwait, under wait_lock; its children were handed to init by reparent in its kexit, also under wait_lock. (freeproc is also called on a half-built child when allocproc or kfork fails, but such a slot has no children.) So while you hold wait_lock, no writer of the parent’s pid can run. Taking the parent’s p->lock as well would mean holding two p->locks at once, which nothing in xv6 does and which no rule orders: better not to invent that.

4Where do the records wait, and when do they reach user memory?

You will be holding locks while you read each slot. The records must end up in the user’s buffer, and only copyout can write there. Is it safe, in this kernel, to call copyout while holding a spinlock? Whatever your answer, where should the records live until they are copied, and why there?

The reference design

The truth in this tree: copyout never sleeps and never faults. It looks the page up with walkaddr. If the page is lazily allocated and below sz, vmfault calls kalloc (which only spins on kmem.lock), zeroes the page and maps it with mappages (which may kalloc page-table pages). Then it copies with memmove to the physical address, through the kernel’s direct map: the kernel never touches the user virtual address, so there is nothing to fault on. No path sleeps. The kernel relies on this already: kwait calls copyout for the exit status while holding wait_lock and the child’s p->lock (kernel/proc.c:391). Clinic 1 ran a procinfo that copies each record out under both locks: every test passed, and the measured lock-hold times were no different.

So why does the reference gather first and copy once, after releasing?

It keeps the locked code independent of copyout’s insides. In a kernel where a user page can be somewhere slow (on disk, in a file), the fault path sleeps, and a copyout under a spinlock would panic in sched with sched locks. That is reasoned, not run here, but it is the reason the rule exists.
Error handling stays simple. A failed copyout in the middle of the scan has to release two locks before returning; one copyout after the scan has nothing to undo.
The scan stays short. While it runs, interrupts are off on this hart and every fork, exit and wait on the other harts waits for wait_lock.

Where the records live meanwhile:

Home	Problem
an array on the kernel stack	2,560 bytes of a 4,096-byte kernel stack. In the recorded run the kernel stack was 224 bytes deep inside `procinfo` (its own frame is 96 bytes), so it would fit today, but it leaves little room, and with 128 slots it would run into the guard page
a global array	three harts can call `procinfo` at once; they would overwrite each other’s records unless a lock serialized them, and that lock would have to be held across the `copyout`
a page from `kalloc`	private to this call, 4,096 bytes ≥ 2,560, freed right after the `copyout`

The reference uses a page from kalloc, and checks once that sizeof(struct pinfo) * NPROC fits in it (the compiler evaluates that test at compile time; the build contains no call for it).

Check yourself

1deepChoose one

In a variant of the lab, procinfo calls copyout for each record while holding wait_lock and that slot’s p->lock. The user’s buffer is in lazily allocated memory that has never been touched. What happens in this tree?

The kernel panics with sched locks, because the lazy page must be read in and copyout sleeps.The kernel takes a page fault in supervisor mode on the user address and panics in kerneltrap.It deadlocks: kalloc needs kmem.lock, and kmem is never taken under p->lock.It works. copyout’s fault path only calls kalloc and mappages, which spin briefly but never sleep, so no lock rule is broken.

2solidFill in the machine state

sys_procinfo has called procinfo, which released every lock, and is now inside the single copyout at the end. Fill in the state of the hart running it.

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

5How can you tell which hart is running a process?

struct proc has no “hart” field. Where is that information, who writes it, under which lock, and how long does the answer you copy stay true?

Check yourself

1solidChoose one

procinfo holds p->lock, finds p->state == RUNNING, and loops over cpus[] comparing each cpus[i].proc with p. It holds no lock of the other harts. Why is the answer reliable?

Because cpus[] is protected by wait_lock.Because a hart’s c->proc never changes during a system call.Because acquire turns interrupts off on every hart, so no scheduler can run.Because a hart’s c->proc can change to or from p only while p->lock is held, and procinfo holds it.

6What does "consistent" mean for this snapshot?

Each record is read under its own p->lock, one slot after another, with wait_lock held for the whole scan. Which of these can a correct snapshot contain: two RUNNING records naming the same hart; more RUNNING records than there are harts; a record whose ppid is missing from the snapshot; a USED record with no parent; a ZOMBIE? What would it take to make the whole table consistent at one instant, and what would that cost?

Check yourself

1deepChoose all that apply

procinfo is implemented as in the reference (wait_lock around the scan, each record under its p->lock), called with max = NPROC. Which of these can appear in one snapshot on three harts?

7name and sz, and what procdump gets away with

procdump prints pid, state and name with no lock at all. Why is that acceptable there? Your call returns records to a user program: you take p->lock for state, pid and the hart, but what do you do about name and sz, which p->lock does not protect?

Check yourself

1solidChoose one

Why does procdump read the process table without taking any lock?

Because it runs with interrupts off, so no other hart can change the table.Because cons.lock, which its caller holds, protects the process table.So that a dump still prints on a machine that is stuck with some lock held forever.Because it only runs at boot, before any other process exists.

3. Build it

Start from the frozen commit, in your own clone of xv6 (not this site’s xv6/):

git checkout -b my-procinfo 06aad25

Work in this order; each milestone can be tested before the next.

The interface. Write kernel/pinfo.h. Add SYS_procinfo (23) to kernel/syscall.h, entry("procinfo") to user/usys.pl, and to user/user.h both struct pinfo; (near struct stat;) and int procinfo(struct pinfo *, int);. Without the forward declaration, -Werror stops the build with 'struct pinfo' declared inside parameter list will not be visible outside of this definition or declaration.
The handler and the scan. sys_procinfo in kernel/sysproc.c (fetch the two arguments, check and clamp max, kalloc a page, call the scan, one copyout, kfree) and a procinfo(struct pinfo *, int) in kernel/proc.c that takes each slot’s p->lock in turn. Add the prototype to kernel/defs.h and the table entry in kernel/syscall.c. Fill ppid with 0 and cpu with -1 for now. Write a ten-line test program, or go straight to step 5 and use ps.
The parent. wait_lock around the scan; ppid from p->parent.
The hart. The cpus[] loop for RUNNING records.
ps, and $U/_ps in UPROGS. Try ps, then ps & (the background shell’s records are interesting).
The test. procinfotest (or your own), then usertests -q, then procinfotest again: the second run has thousands of pids behind it.

Debugging. Run QEMU with three harts. If a run hangs, attach gdb (the GNU debugger) (make qemu-gdb in one terminal, ${TOOLPREFIX}gdb kernel/kernel and target remote in another), then info threads and thread apply all bt: every hart’s backtrace, as in clinic 2. TOOLPREFIX is your RISC-V toolchain’s prefix, the same one xv6’s Makefile detects (riscv64-unknown-elf-, riscv64-linux-gnu- or riscv64-elf-); set it with export TOOLPREFIX=riscv64-unknown-elf- or whichever you have. On Debian/Ubuntu/WSL, gdb-multiarch also works as the debugger. To see who holds a lock, print it: p wait_lock shows cpu = 0x8000fa50 <cpus+128>, and each struct cpu is 128 bytes, so that is hart 1. To watch the scan, start QEMU halted (-S) and set breakpoints before you continue, for example on the line after acquire(&p->lock), and print p - proc, p->pid and cpus[$tp].noff (tp holds the hart number in the kernel). A test that passes once proves little here: clinic 3’s bug passed on four of six runs.

4. Debugging clinic

Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.

1Copied each record out while holding the locks

No kernel buffer: procinfo gets the user address and copies each record as soon as it is filled, inside both locks, releasing them on failure:

-      n++;
-    }
-    release(&p->lock);
+      if (copyout(me->pagetable, me->sz, addr + n * sizeof(rec),
+                  (char *)&rec, sizeof(rec)) < 0) {
+        release(&p->lock);
+        release(&wait_lock);
+        return -1;
+      }
+      n++;
+    }
+    release(&p->lock);

(rec is a single struct pinfo on the stack, me is myproc(); sys_procinfo no longer allocates a page.)

What happened when we ran it

$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: OK
procinfotest: bad buffers return -1; a lazy buffer works: OK
procinfotest: 7581 snapshots, 0 bad, newest pid seen 1647, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 5 checks OK
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED
$ procinfotest
[...]
procinfotest: 6849 snapshots, 0 bad, newest pid seen 9756, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 5 checks OK

2Took p->lock, then wait_lock

wait_lock is taken only around the parent read, inside the loop, after the slot’s p->lock:

-  acquire(&wait_lock);
   for (p = proc; p < &proc[NPROC] && n < max; p++) {
     acquire(&p->lock);
     if (p->state != UNUSED) {
       ...
+      acquire(&wait_lock);
       out[n].ppid = p->parent ? p->parent->pid : 0;
+      release(&wait_lock);
       ...
   }
-  release(&wait_lock);

It looks tidier: wait_lock is held for one line instead of the whole scan.

What happened when we ran it

$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: OK
procinfotest: bad buffers return -1; a lazy buffer works: OK

(no further output; after 120 seconds, gdb attached:)
acquire (lk=lk@entry=0x80010370 <proc+1440>) at kernel/spinlock.c:37
warning: 37	kernel/spinlock.c: No such file or directory
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [running]) acquire (lk=lk@entry=0x80010370 <proc+1440>) at kernel/spinlock.c:37
  2    Thread 1.2 (CPU#1 [running]) acquire (lk=lk@entry=0x80010370 <proc+1440>) at kernel/spinlock.c:37
  3    Thread 1.3 (CPU#2 [running]) acquire (lk=lk@entry=0x8000f9b8 <wait_lock>) at kernel/spinlock.c:37

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  acquire (lk=lk@entry=0x8000f9b8 <wait_lock>) at kernel/spinlock.c:37
#1  0x0000000080002490 in procinfo (out=out@entry=0x87f10000, max=64) at kernel/proc.c:727
#2  0x0000000080002c70 in sys_procinfo () at kernel/sysproc.c:139
#3  0x0000000080002a02 in syscall () at kernel/syscall.c:148
#4  0x0000000080002788 in usertrap () at kernel/trap.c:68
#5  0x0000003ffffff09c in ?? ()

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  acquire (lk=lk@entry=0x80010370 <proc+1440>) at kernel/spinlock.c:37
#1  0x0000000080002182 in killed (p=p@entry=0x80010370 <proc+1440>) at kernel/proc.c:638
#2  0x0000000080002270 in kwait (addr=0) at kernel/proc.c:409
#3  0x0000000080002a94 in sys_wait () at kernel/sysproc.c:37
#4  0x0000000080002a02 in syscall () at kernel/syscall.c:148
#5  0x0000000080002788 in usertrap () at kernel/trap.c:68
#6  0x0000003ffffff09c in ?? ()

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  acquire (lk=lk@entry=0x80010370 <proc+1440>) at kernel/spinlock.c:37
#1  0x0000000080001fbc in wakeup (chan=chan@entry=0x80007880 <ticks>) at kernel/proc.c:582
#2  0x000000008000265e in clockintr () at kernel/trap.c:172
#3  0x00000000800026de in devintr () at kernel/trap.c:215
#4  0x0000000080002720 in usertrap () at kernel/trap.c:69
#5  0x0000003ffffff09c in ?? ()
$1 = {locked = 1, name = 0x80007168 "wait_lock", cpu = 0x8000fa50 <cpus+128>}
cpus[0].proc = 0x80010208 <proc+1080> noff = 2
cpus[1].proc = 0x80010370 <proc+1440> noff = 2
cpus[2].proc = 0x800100a0 <proc+720> noff = 2
[...]
slot  2 pid     3 state RUNNING   name procinfotest  lock.locked 0 lock.cpu 0x0 parent 0x8000ff38 <proc+360>
slot  3 pid     5 state RUNNING   name procinfotest  lock.locked 0 lock.cpu 0x0 parent 0x800100a0 <proc+720>
slot  4 pid     6 state RUNNING   name procinfotest  lock.locked 1 lock.cpu 0x8000fad0 <cpus+256> parent 0x800100a0 <proc+720>
[...]

The test got through its first four checks, in which procinfo overlaps another process’s exit at most once (check 2’s child), a window far too short to hit; the stress phase overlaps thousands, and the test hung there. Each struct proc is 360 bytes and each struct cpu 128, so the addresses decode as follows (the line numbers in the backtraces are those of this build, one more than the site’s source for kwait):

Hart 2 runs procinfotest (pid 3, slot 2: cpus[2].proc is proc+720). Its procinfo holds slot 4’s lock (lock.cpu is cpus+256, hart 2) and spins for wait_lock at the line the change added.
Hart 1 runs pid 6, a churning child in slot 4 (proc+1440). Its kwait holds wait_lock (cpu = cpus+128, hart 1) and calls killed on itself (kernel/proc.c:408), which spins for slot 4’s lock: its own, held by hart 2.
Hart 0 runs pid 5, the spinning child in slot 3. A timer interrupt arrived in user mode; clockintr took tickslock and called wakeup on ticks, which takes every p->lock in turn and now spins on slot 4’s. Hart 0 is not part of the cycle, but it is caught anyway, holding tickslock.

Hart 1 waits for hart 2 and hart 2 waits for hart 1: a two-lock cycle, made of the wait_lock → p->lock order that kwait uses and the p->lock → wait_lock order the change introduced. Every noff is 2: one lock held plus the push_off of the acquire that spins. Interrupts are off on all three harts, so no timer can ever move anything again, and since hart 0 holds tickslock, even uptime would hang now.

The partner varies from run to run. Another run of the same variant closed the cycle with kwait’s scan of its children instead: hart 1 in kwait holding wait_lock at proc.c:385 (this build’s numbering), acquiring a child’s lock (slot 6) that hart 0’s procinfo held, with hart 2 in kwait at line 418 as a victim spinning on wait_lock (noff 1). That is the first option of the check in question 3. Lock order is a property of the whole kernel: a new function must follow the order every existing path already uses.

3No locks at all, like procdump

procinfo copies procdump’s approach: no wait_lock, no p->lock, everything else unchanged:

-  acquire(&wait_lock);
   for (p = proc; p < &proc[NPROC] && n < max; p++) {
-    acquire(&p->lock);
     if (p->state != UNUSED) {
       ...
     }
-    release(&p->lock);
   }
-  release(&wait_lock);

What happened when we ran it

$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: OK
procinfotest: bad buffers return -1; a lazy buffer works: OK
procinfotest: first bad snapshot: running, but on no hart: pid 127 ppid 7 state 4 cpu -1
procinfotest: 44970 snapshots, 3 bad, newest pid seen 2675, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: FAIL
procinfotest: 1 FAILED
$ procinfotest
[...]
procinfotest: first bad snapshot: on a hart, but not running: pid 2681 ppid 2677 state 3 cpu 2
procinfotest: 37677 snapshots, 1 bad, newest pid seen 5101, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: FAIL
procinfotest: 1 FAILED
$ procinfotest
[...]
procinfotest: 34453 snapshots, 0 bad, newest pid seen 7202, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 5 checks OK

Torn records do show up, but rarely per snapshot: on one boot, six runs took 213,431 snapshots in all and only 4 were inconsistent (3 in the first run, 1 in the second, none in the other four, which printed 5 checks OK). Per run it is less rare: a second series of six runs failed 4 of them. Each bad record mixes two moments:

state 4 cpu -1, “running, but on no hart”. The compiled loop loads p->state three separate times (three lw a5,24(s1) in this build: the UNUSED test, the copy into the record, and the RUNNING test before the cpus[] loop). The copy saw RUNNING, and by the time the cpus[] loop ran, no hart’s c->proc pointed at the process: it had just yielded or slept, or the scheduler had set RUNNING (kernel/proc.c:451) but not yet c->proc (line 452).
state 3 cpu 2, “on a hart, but not running”. The reverse: the copy saw RUNNABLE, then the scheduler on hart 2 picked the process, and the third load saw RUNNING, so the loop found it on hart 2.
pid 8223 ppid 0 state 0, “bad pid or state” (seen in that second series). The first load saw a live state, so the slot was recorded with its pid, but the copy of state came after freeproc on another hart had set UNUSED: a record of a process that, as far as the record says, does not exist.

With p->lock held, the scheduler cannot be between those lines, and all three loads see the same value. Without it, the program receives a record that was never true at any moment. Nothing crashed: this build loads p->parent once into a register, checks it for 0 and then dereferences that same register, so the parent pointer could not be read as non-zero and then as zero. That is luck of code generation, not a guarantee.

A second variant kept p->lock but dropped wait_lock. Six runs (60,643 snapshots) printed no bad snapshot at all: this workload’s parents (the test and its two churning children) never exit while their children live, so no parent link changes during a scan. It still gives up layer 2 of question 6 (parent links may now change while the scan runs); a measurement saw only milder effects (see Measure): some children caught mid-fork already had a parent, and snapshots with two RUNNING records on one hart became more common. Rare is not never: a race test that passes is weak evidence.

4Ignored max

The scan stops only at the end of the table:

-  for (p = proc; p < &proc[NPROC] && n < max; p++) {
+  for (p = proc; p < &proc[NPROC]; p++) {

sys_procinfo still copies out n records.

What happened when we ran it

$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: procinfo(buf, 1) returned 3 and changed 80 bytes after buf[0]; procinfo(buf, 0) returned 3
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: FAIL
procinfotest: bad buffers return -1; a lazy buffer works: OK
procinfotest: 5977 snapshots, 0 bad, newest pid seen 1654, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 1 FAILED
$ ps
PID   PPID  STATE   CPU  SIZE    NAME
1     0     sleep   -    16384   init
2     1     sleep   -    20480   sh
1656  2     run     2    16384   ps

5Returned the count, not the number written

Records are written only while there is room, but the count keeps going, and that total is returned:

-  for (p = proc; p < &proc[NPROC] && n < max; p++) {
+  for (p = proc; p < &proc[NPROC]; p++) {
     acquire(&p->lock);
-    if (p->state != UNUSED) {
+    if (p->state != UNUSED && n >= max) {
+      n++; // count it, but there is no room
+    } else if (p->state != UNUSED) {

and sys_procinfo copies out min(n, max) records.

What happened when we ran it

$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: procinfo(buf, 1) returned 3 and changed 0 bytes after buf[0]; procinfo(buf, 0) returned 3
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: FAIL
procinfotest: bad buffers return -1; a lazy buffer works: OK
procinfotest: 11082 snapshots, 0 bad, newest pid seen 2820, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 1 FAILED

6procdump’s loop, with a lock added

The loop is written like procdump's, which skips unused slots with continue, and the lock is added at the top:

     acquire(&p->lock);
-    if (p->state != UNUSED) {
+    if (p->state == UNUSED)
+      continue;
+    {

The continue jumps past the release(&p->lock) at the bottom of the loop.

What happened when we ran it

$ ps
Ppanic: acquire

(gdb attached:)
acquire (lk=lk@entry=0x80010208 <proc+1080>) at kernel/spinlock.c:37
warning: 37	kernel/spinlock.c: No such file or directory
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [running]) acquire (lk=lk@entry=0x80010208 <proc+1080>) at kernel/spinlock.c:37
  2    Thread 1.2 (CPU#1 [running]) acquire (lk=lk@entry=0x80010208 <proc+1080>) at kernel/spinlock.c:37
  3    Thread 1.3 (CPU#2 [running]) panic (s=s@entry=0x80007048 "acquire") at kernel/printk.c:144

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  panic (s=s@entry=0x80007048 "acquire") at kernel/printk.c:144
#1  0x0000000080000c28 in acquire (lk=lk@entry=0x80010208 <proc+1080>) at kernel/spinlock.c:26
#2  0x0000000080001fbc in wakeup (chan=chan@entry=0x8000f950 <tx_lock>) at kernel/proc.c:582
#3  0x00000000800041cc in releasesleep (lk=lk@entry=0x8000f950 <tx_lock>) at kernel/sleeplock.c:42
#4  0x0000000080000964 in uartwrite (buf=buf@entry=0x3fffff9eb0 "P", n=n@entry=1) at kernel/uart.c:95
#5  0x000000008000012c in consolewrite (user_src=1, src=16015, n=1) at kernel/console.c:74
#6  0x000000008000456e in filewrite (f=0x8001fad0 <ftable+24>, addr=16015, n=1) at kernel/file.c:147
#7  0x0000000080004fb6 in sys_write () at kernel/sysfile.c:94
#8  0x00000000800029fc in syscall () at kernel/syscall.c:148
#9  0x0000000080002782 in usertrap () at kernel/trap.c:68
#10 0x0000003ffffff09c in ?? ()

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  acquire (lk=lk@entry=0x80010208 <proc+1080>) at kernel/spinlock.c:37
#1  0x0000000080001fbc in wakeup (chan=chan@entry=0x80007868 <tx_chan>) at kernel/proc.c:582
#2  0x0000000080000a18 in uartintr () at kernel/uart.c:145
#3  0x00000000800026b2 in devintr () at kernel/trap.c:199
#4  0x0000000080002812 in kerneltrap () at kernel/trap.c:149
#5  0x0000000080005778 in kernelvec () at kernel/kernelvec.S:38
Backtrace stopped: frame did not save the PC

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  acquire (lk=lk@entry=0x80010208 <proc+1080>) at kernel/spinlock.c:37
#1  0x0000000080001dd8 in scheduler () at kernel/proc.c:447
#2  0x0000000080000ea0 in main () at kernel/main.c:44
$1 = {locked = 0, name = 0x80007168 "wait_lock", cpu = 0x0}
cpus[0].proc = 0x0 noff = 1
cpus[1].proc = 0x0 noff = 1
cpus[2].proc = 0x800100a0 <proc+720> noff = 63
[...]
UNUSED slots whose p->lock is held: 61 (slots 3..63), lk->cpu of the first: 0x8000fad0 <cpus+256>

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

e56b55c Declare procinfo and struct pinfo
kernel/pinfo.h
@@ -0,0 +1,10 @@
1// One record of a process-table snapshot, as procinfo()
2// copies it out to user space.
3struct pinfo {
4 int pid;
5 int ppid; // parent's pid, 0 if none
6 int state; // enum procstate in proc.h: 1 USED .. 5 ZOMBIE
7 int cpu; // hart running it if RUNNING, else -1
8 uint64 sz; // size of user memory (bytes)
9 char name[16]; // always NUL-terminated
10};
kernel/syscall.h
@@ -20,4 +20,5 @@
2020#define SYS_link 19
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
24#define SYS_procinfo 23
user/user.h
@@ -1,7 +1,8 @@
11#define SBRK_ERROR ((char *)-1)
22
33struct stat;
4struct pinfo;
45
56// system calls
67int fork(void);
78int exit(int) __attribute__((noreturn));
@@ -24,8 +25,9 @@ int getpid(void);
2425char *sys_sbrk(int, int);
2526int pause(int);
2627int uptime(void);
2728int sync(void);
29int procinfo(struct pinfo *, int);
2830
2931// ulib.c
3032int stat(const char *, struct stat *);
3133char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,5 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("procinfo");
74cd0c4 Gather a snapshot under p->lock, then copy out once
kernel/defs.h
@@ -3,8 +3,9 @@ struct buf;
33struct context;
44struct file;
55struct inode;
66struct pipe;
7struct pinfo;
78struct proc;
89struct spinlock;
910struct sleeplock;
1011struct stat;
@@ -102,8 +103,9 @@ void wakeup(void*);
102103void yield(void);
103104int either_copyout(int user_dst, uint64 dst, void *src, uint64 len);
104105int either_copyin(void *dst, int user_src, uint64 src, uint64 len);
105106void procdump(void);
107int procinfo(struct pinfo*, int);
106108
107109// swtch.S
108110void swtch(struct context*, struct context*);
109111
kernel/proc.c
@@ -4,8 +4,9 @@
44#include "riscv.h"
55#include "spinlock.h"
66#include "proc.h"
77#include "defs.h"
8#include "pinfo.h"
89
910struct cpu cpus[NCPU];
1011
1112struct proc proc[NPROC];
@@ -700,4 +701,37 @@ procdump(void)
700701 printk("%d %s %s", p->pid, state, p->name);
701702 printk("\n");
702703 }
703704}
705
706// Fill out[] with at most max records, one per in-use slot
707// of proc[], and return how many were filled. out is a
708// kernel buffer: nothing here touches user memory.
709int
710procinfo(struct pinfo *out, int max)
711{
712 struct proc *p;
713 int n = 0;
714
715 for (p = proc; p < &proc[NPROC] && n < max; p++) {
716 acquire(&p->lock);
717 if (p->state != UNUSED) {
718 // state and pid are protected by p->lock, so the
719 // pair belongs to one moment in this process's life.
720 out[n].pid = p->pid;
721 out[n].state = p->state;
722 out[n].ppid = 0;
723 out[n].cpu = -1;
724 // sz and name are private to p, which writes them
725 // without p->lock (growproc, kexec), so they may be
726 // stale, and name may be half old, half new. procdump
727 // reads them the same way. The copy is bounded and
728 // always terminated.
729 out[n].sz = p->sz;
730 memmove(out[n].name, p->name, sizeof(out[n].name));
731 out[n].name[sizeof(out[n].name) - 1] = 0;
732 n++;
733 }
734 release(&p->lock);
735 }
736 return n;
737}
kernel/syscall.c
@@ -102,8 +102,9 @@ extern uint64 sys_unlink(void);
102102extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106extern uint64 sys_procinfo(void);
106107
107108// An array mapping syscall numbers from syscall.h
108109// to the function that handles the system call.
109110static uint64 (*syscalls[])(void) = {
@@ -129,8 +130,9 @@ static uint64 (*syscalls[])(void) = {
129130 [SYS_link] = sys_link,
130131 [SYS_mkdir] = sys_mkdir,
131132 [SYS_close] = sys_close,
132133 [SYS_sync] = sys_sync,
134 [SYS_procinfo] = sys_procinfo,
133135 // clang-format on
134136};
135137
136138void
kernel/sysproc.c
@@ -5,8 +5,9 @@
55#include "memlayout.h"
66#include "spinlock.h"
77#include "proc.h"
88#include "vm.h"
9#include "pinfo.h"
910
1011uint64
1112sys_exit(void)
1213{
@@ -109,4 +110,36 @@ sys_uptime(void)
109110 xticks = ticks;
110111 release(&tickslock);
111112 return xticks;
112113}
114
115// procinfo(struct pinfo *buf, int max): copy a snapshot of
116// at most max in-use process slots to buf; return how many
117// records were copied, or -1.
118uint64
119sys_procinfo(void)
120{
121 uint64 addr;
122 int max, n;
123 struct pinfo *buf;
124 struct proc *p = myproc();
125
126 argaddr(0, &addr);
127 argint(1, &max);
128 if (max < 0)
129 return -1;
130 if (max > NPROC)
131 max = NPROC;
132
133 // gather into a kernel page while holding the locks,
134 // then copy out with no lock held.
135 if (sizeof(struct pinfo) * NPROC > PGSIZE)
136 panic("sys_procinfo: pinfo");
137 if ((buf = (struct pinfo *)kalloc()) == 0)
138 return -1;
139 n = procinfo(buf, max);
140 if (copyout(p->pagetable, p->sz, addr, (char *)buf,
141 n * sizeof(struct pinfo)) < 0)
142 n = -1;
143 kfree((void *)buf);
144 return n;
145}
a01f203 Report the parent's pid, under wait_lock
kernel/proc.c
@@ -711,16 +711,22 @@ procinfo(struct pinfo *out, int max)
711711{
712712 struct proc *p;
713713 int n = 0;
714714
715 // p->parent is protected by wait_lock, which must be
716 // acquired before any p->lock.
717 acquire(&wait_lock);
715718 for (p = proc; p < &proc[NPROC] && n < max; p++) {
716719 acquire(&p->lock);
717720 if (p->state != UNUSED) {
718721 // state and pid are protected by p->lock, so the
719722 // pair belongs to one moment in this process's life.
720723 out[n].pid = p->pid;
721724 out[n].state = p->state;
722 out[n].ppid = 0;
725 // the parent cannot be reaped while we hold
726 // wait_lock (kwait frees under it), so its pid is
727 // stable even though we do not hold its p->lock.
728 out[n].ppid = p->parent ? p->parent->pid : 0;
723729 out[n].cpu = -1;
724730 // sz and name are private to p, which writes them
725731 // without p->lock (growproc, kexec), so they may be
726732 // stale, and name may be half old, half new. procdump
@@ -732,6 +738,7 @@ procinfo(struct pinfo *out, int max)
732738 n++;
733739 }
734740 release(&p->lock);
735741 }
742 release(&wait_lock);
736743 return n;
737744}
43308ef Show which hart runs a RUNNING process
kernel/proc.c
@@ -709,9 +709,9 @@ procdump(void)
709709int
710710procinfo(struct pinfo *out, int max)
711711{
712712 struct proc *p;
713 int n = 0;
713 int i, n = 0;
714714
715715 // p->parent is protected by wait_lock, which must be
716716 // acquired before any p->lock.
717717 acquire(&wait_lock);
@@ -725,9 +725,17 @@ procinfo(struct pinfo *out, int max)
725725 // the parent cannot be reaped while we hold
726726 // wait_lock (kwait frees under it), so its pid is
727727 // stable even though we do not hold its p->lock.
728728 out[n].ppid = p->parent ? p->parent->pid : 0;
729 // a hart's c->proc changes to and from p only while
730 // p->lock is held (scheduler()), so while we hold it,
731 // p is RUNNING exactly when one c->proc points at it.
729732 out[n].cpu = -1;
733 if (p->state == RUNNING) {
734 for (i = 0; i < NCPU; i++)
735 if (cpus[i].proc == p)
736 out[n].cpu = i;
737 }
730738 // sz and name are private to p, which writes them
731739 // without p->lock (growproc, kexec), so they may be
732740 // stale, and name may be half old, half new. procdump
733741 // reads them the same way. The copy is bounded and
2b96e2b Add the ps user program
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_ps\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/ps.c
@@ -0,0 +1,67 @@
1// ps: list the processes, from one procinfo() snapshot.
2
3#include "kernel/types.h"
4#include "kernel/param.h"
5#include "kernel/pinfo.h"
6#include "user/user.h"
7
8static char *states[] = {
9 [1] = "used", [2] = "sleep", [3] = "runble", [4] = "run", [5] = "zombie",
10};
11
12struct pinfo buf[NPROC];
13
14// print s, then spaces up to width w.
15void
16col(char *s, int w)
17{
18 int n = strlen(s);
19
20 printf("%s", s);
21 while (n++ < w)
22 printf(" ");
23}
24
25// format a small non-negative int, or "-" for -1.
26char *
27itoa(int x, char *s)
28{
29 char t[12];
30 int i = 0, j = 0;
31
32 if (x < 0)
33 return "-";
34 do
35 t[i++] = '0' + x % 10;
36 while ((x /= 10) != 0);
37 while (i > 0)
38 s[j++] = t[--i];
39 s[j] = 0;
40 return s;
41}
42
43int
44main(void)
45{
46 char a[12];
47 int i, n;
48
49 n = procinfo(buf, NPROC);
50 if (n < 0) {
51 printf("ps: procinfo failed\n");
52 exit(1);
53 }
54 printf("PID PPID STATE CPU SIZE NAME\n");
55 for (i = 0; i < n; i++) {
56 col(itoa(buf[i].pid, a), 6);
57 col(itoa(buf[i].ppid, a), 6);
58 if (buf[i].state >= 1 && buf[i].state <= 5)
59 col(states[buf[i].state], 8);
60 else
61 col("???", 8);
62 col(itoa(buf[i].cpu, a), 5);
63 col(itoa((int)buf[i].sz, a), 8);
64 printf("%s\n", buf[i].name);
65 }
66 exit(0);
67}
f1065c9 Add procinfotest
Makefile
@@ -150,8 +150,9 @@ UPROGS=\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153153 $U/_ps\
154 $U/_procinfotest\
154155
155156fs.img: mkfs/mkfs README $(UPROGS)
156157 mkfs/mkfs fs.img README $(UPROGS)
157158
user/procinfotest.c
@@ -0,0 +1,231 @@
1// Tests for the procinfo system call.
2
3#include "kernel/types.h"
4#include "kernel/param.h"
5#include "kernel/pinfo.h"
6#include "kernel/riscv.h"
7#include "kernel/memlayout.h"
8#include "user/user.h"
9
10#define USED 1
11#define SLEEPING 2
12#define RUNNING 4
13#define ZOMBIE 5
14
15struct pinfo buf[NPROC + 1];
16int fails, checks;
17
18void
19check(int ok, char *what)
20{
21 printf("procinfotest: %s: %s\n", what, ok ? "OK" : "FAIL");
22 checks++;
23 if (!ok)
24 fails++;
25}
26
27// the record for pid in buf[0..n-1], or 0.
28struct pinfo *
29find(int pid, int n)
30{
31 for (int i = 0; i < n; i++)
32 if (buf[i].pid == pid)
33 return &buf[i];
34 return 0;
35}
36
37// the snapshot's own record: we are running, on some hart.
38void
39selftest(void)
40{
41 int n = procinfo(buf, NPROC);
42 struct pinfo *me = find(getpid(), n);
43
44 check(n >= 3 && me != 0 && me->state == RUNNING && me->cpu >= 0 &&
45 me->cpu < NCPU && strcmp(me->name, "procinfotest") == 0,
46 "own record: running on a hart, right name");
47}
48
49// a child blocked in read shows as SLEEPING with us as parent,
50// then as a ZOMBIE until we wait, then not at all.
51void
52childtest(void)
53{
54 int fds[2], pid, n, sawsleep, sawzombie, gone;
55 struct pinfo *c;
56 char ch;
57
58 pipe(fds);
59 pid = fork();
60 if (pid == 0) {
61 read(fds[0], &ch, 1);
62 exit(0);
63 }
64 sawsleep = 0;
65 for (int i = 0; i < 100 && !sawsleep; i++) {
66 n = procinfo(buf, NPROC);
67 c = find(pid, n);
68 sawsleep = c && c->state == SLEEPING && c->ppid == getpid() &&
69 c->cpu == -1;
70 if (!sawsleep)
71 pause(1);
72 }
73 write(fds[1], "x", 1);
74 sawzombie = 0;
75 for (int i = 0; i < 100 && !sawzombie; i++) {
76 n = procinfo(buf, NPROC);
77 c = find(pid, n);
78 sawzombie = c && c->state == ZOMBIE && c->ppid == getpid();
79 if (!sawzombie)
80 pause(1);
81 }
82 wait(0);
83 n = procinfo(buf, NPROC);
84 gone = find(pid, n) == 0;
85 check(sawsleep && sawzombie && gone,
86 "child: sleeping, then zombie, then gone after wait");
87 close(fds[0]);
88 close(fds[1]);
89}
90
91// max limits both what is written and what is returned.
92void
93maxtest(void)
94{
95 int n1, n0, pid0, changed = 0, ok;
96
97 memset(buf, 0xab, sizeof(buf));
98 n1 = procinfo(buf, 1);
99 pid0 = buf[0].pid;
100 for (char *b = (char *)&buf[1]; b < (char *)&buf[NPROC + 1]; b++)
101 if (*b != (char)0xab)
102 changed++;
103 memset(buf, 0xab, sizeof(buf));
104 n0 = procinfo(buf, 0);
105 ok = n1 == 1 && pid0 > 0 && changed == 0 && n0 == 0 &&
106 *(char *)&buf[0] == (char)0xab && procinfo(buf, -1) == -1;
107 if (!ok)
108 printf("procinfotest: procinfo(buf, 1) returned %d and changed %d "
109 "bytes after buf[0]; procinfo(buf, 0) returned %d\n",
110 n1, changed, n0);
111 check(ok, "max=1 writes one record, max=0 none, max=-1 fails");
112}
113
114// bad buffers fail cleanly; a lazily allocated one works.
115void
116addrtest(void)
117{
118 struct pinfo *lazy;
119 int n, ok = 1;
120
121 // address 0 is our text: mapped, but not writable.
122 ok = ok && procinfo((struct pinfo *)0, 1) == -1;
123 // above the program's size: not ours.
124 ok = ok && procinfo((struct pinfo *)(sbrk(0) + 8192), 1) == -1;
125 // the trapframe page is mapped, but not for user access.
126 ok = ok && procinfo((struct pinfo *)TRAPFRAME, 1) == -1;
127 lazy = (struct pinfo *)sbrklazy(2 * 4096);
128 // slot 0 is always init's.
129 n = procinfo(lazy, NPROC);
130 ok = ok && n >= 3 && lazy[0].pid == 1 && lazy[0].ppid == 0;
131 check(ok, "bad buffers return -1; a lazy buffer works");
132}
133
134// check what the design guarantees about one snapshot: each
135// record on its own, and the parent links (frozen by wait_lock
136// during the scan). Not checked: that no two records claim the
137// same hart, since records are taken at different moments.
138// Return 0 if all hold, else what is wrong, with *bad set to
139// the record's index. *running counts the RUNNING records.
140char *
141inconsistent(int n, int *running, int *bad)
142{
143 *running = 0;
144 for (int i = 0; i < n; i++) {
145 struct pinfo *p = &buf[i];
146 *bad = i;
147 if (p->pid <= 0 || p->state < USED || p->state > ZOMBIE)
148 return "bad pid or state";
149 for (int j = 0; j < i; j++)
150 if (buf[j].pid == p->pid)
151 return "pid twice";
152 if (p->state == RUNNING) {
153 if (p->cpu < 0 || p->cpu >= NCPU)
154 return "running, but on no hart";
155 (*running)++;
156 } else if (p->cpu != -1) {
157 return "on a hart, but not running";
158 }
159 // with wait_lock held for the whole scan, a parent
160 // cannot disappear before the scan is over.
161 if (p->ppid != 0 && find(p->ppid, n) == 0)
162 return "parent not in snapshot";
163 }
164 return 0;
165}
166
167// snapshots taken for 2 seconds while one child spins and
168// two others fork and reap children as fast as they can.
169void
170stresstest(void)
171{
172 int pids[3], n, running, most = 0, bad = 0, snaps = 0, maxpid = 0;
173 int t0, i;
174 char *why;
175
176 for (int k = 0; k < 3; k++) {
177 pids[k] = fork();
178 if (pids[k] == 0) {
179 for (;;) {
180 if (k == 0) {
181 for (volatile int j = 0; j < 100000; j++)
182 ;
183 } else {
184 int c = fork();
185 if (c == 0)
186 exit(0);
187 if (c > 0)
188 wait(0);
189 }
190 }
191 }
192 }
193 t0 = uptime();
194 while (uptime() - t0 < 20) {
195 n = procinfo(buf, NPROC);
196 snaps++;
197 if ((why = inconsistent(n, &running, &i)) != 0 && bad++ == 0)
198 printf("procinfotest: first bad snapshot: %s: "
199 "pid %d ppid %d state %d cpu %d\n",
200 why, buf[i].pid, buf[i].ppid, buf[i].state, buf[i].cpu);
201 if (running > most)
202 most = running;
203 for (int j = 0; j < n; j++)
204 if (buf[j].pid > maxpid)
205 maxpid = buf[j].pid;
206 }
207 for (int k = 0; k < 3; k++)
208 kill(pids[k]);
209 for (int k = 0; k < 3; k++)
210 wait(0);
211 printf("procinfotest: %d snapshots, %d bad, newest pid seen %d, "
212 "most RUNNING at once %d\n",
213 snaps, bad, maxpid, most);
214 check(bad == 0 && maxpid > pids[2] + 100,
215 "snapshots during fork/exit churn: every one consistent");
216}
217
218int
219main(int argc, char *argv[])
220{
221 selftest();
222 childtest();
223 maxtest();
224 addrtest();
225 stresstest();
226 if (fails == 0)
227 printf("procinfotest: %d checks OK\n", checks);
228 else
229 printf("procinfotest: %d FAILED\n", fails);
230 exit(fails != 0);
231}

6. Verify and measure

On the branch, on three harts, procinfotest passes, usertests -q passes, and procinfotest passes again on the same boot:

$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: OK
procinfotest: bad buffers return -1; a lazy buffer works: OK
procinfotest: 8318 snapshots, 0 bad, newest pid seen 2222, most RUNNING at once 3
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 5 checks OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test partial_write: OK
test unlinkcwd: OK
ALL TESTS PASSED
$ procinfotest
procinfotest: own record: running on a hart, right name: OK
procinfotest: child: sleeping, then zombie, then gone after wait: OK
procinfotest: max=1 writes one record, max=0 none, max=-1 fails: OK
procinfotest: bad buffers return -1; a lazy buffer works: OK
procinfotest: 5757 snapshots, 0 bad, newest pid seen 10350, most RUNNING at once 4
procinfotest: snapshots during fork/exit churn: every one consistent: OK
procinfotest: 5 checks OK
$ ps
PID   PPID  STATE   CPU  SIZE    NAME
1     0     sleep   -    16384   init
2     1     sleep   -    20480   sh
10351 2     run     0    16384   ps

What this shows: about fourteen thousand snapshots taken while thousands of processes were created and destroyed around them (pids climbed to 2222 during the first run alone), each one keeping its promises (records consistent with themselves, parents present). The second run’s most RUNNING at once 4 on three harts is not a failure: it is the evidence that a snapshot read slot by slot is not an instant of the whole table, which is why the test does not check for it. usertests makes no procinfo calls, so it shows that nothing else changed. The snapshot count varies between runs: timings on QEMU depend on what else the computer is doing.

All numbers come from runs on three harts under QEMU, using a scratch measurement program (not part of the branch) on a copy of the branch’s kernel. One tick is 0.1 s (the timer is set 1,000,000 time units ahead, and QEMU’s time runs at 10 MHz), so tick counts are coarse.

What a call costs. 50,000 calls each, on an otherwise idle system, measured with uptime (two runs, same results):

Call	Ticks for 50,000	Per call, roughly
`getpid()`	5	10 µs
`procinfo(buf, 1)`	11 and 10	21 µs
`procinfo(buf, 64)`	23	46 µs

A full snapshot costs about four getpids. Even max = 1, which stops the scan at the first in-use slot, costs twice a getpid: allocating and freeing the page and the copyout are not free.

How often a snapshot catches the table mid-change. For 50 ticks, one child spun and two forked and reaped children as fast as they could, while the program took snapshots and counted (two runs on the reference kernel):

	Run 1	Run 2
snapshots	31,691	32,315
records (about 7.7 per snapshot)	244,204	247,093
records RUNNING / RUNNABLE / SLEEPING	90,198 / 36,593 / 85,945	89,999 / 39,283 / 86,834
snapshots with a child caught mid-fork (USED)	8,796 (28%)	8,721 (27%)
… of those USED records, with `ppid` 0	8,802 of 8,802	8,721 of 8,721
snapshots with a ZOMBIE	18,254 (58%)	17,887 (55%)
snapshots with 3 RUNNING records	27,032	26,637
snapshots with two RUNNING records on one hart	0	0
snapshots with a parent missing	0	0

A quarter of the snapshots show a process that does not fully exist yet, and more than half show one that no longer runs: a ps on a busy machine sees processes in transition all the time, and correctly so. Every child caught mid-fork had no parent yet, because kfork sets the parent under wait_lock, which the scan holds. (That is what the runs showed, not a guarantee: a child whose parent was set just before the scan began, but which is not yet RUNNABLE, would show its parent.) Two RUNNING records on one hart did not occur in these 64,006 snapshots, but did occur in the procinfotest run in Verify (four RUNNING on three harts): rare, possible.

The same program on a kernel with wait_lock removed from procinfo (keeping every p->lock): 29,802 and 29,507 snapshots; USED records with a parent already set, 7 of 8,208 and 4 of 8,179; snapshots with two RUNNING records on one hart, 16 and 10; parent missing, 0 and 0. A likely explanation (reasoned, not measured): holding wait_lock also keeps the churning children from sleeping and waking in wait while the scan runs, so harts switch processes mid-scan less often.

Does copying out under the locks cost anything? A copy of each kernel recorded the time CSR after taking wait_lock and before releasing it (units of 0.1 µs), for the reference and for clinic 1’s version that copies each record out inside the locks:

Workload (calls)	Reference: mean, max (run 1; run 2)	Copy under locks: mean, max (run 1; run 2)
mapped buffer (20,000)	346, 2,191; 535, 36,129	338, 2,249; 285, 654
a fresh lazy page each call (300)	303, 421; 534, 910	420, 1,040; 363, 665
mapped buffer during fork/exit churn (20,000)	9,136, 110,339; 11,803, 128,434	9,312, 147,157; 6,209, 62,429

No consistent difference: run-to-run variation (timings on QEMU depend on what else the computer is doing) is larger than any effect of three or four 40-byte copies, even when the first one allocates a page.

A caution about the churn row. Its mean near 1 ms is an artefact of the measurement program, not a typical scan. Its lazy-page phase ran first and grew it to about 300 pages, so every fork in the churn copied about 1.2 MB in uvmcopy while holding the new child’s p->lock (which kfork holds from allocproc until line 294), and the scan waited at that USED slot. An instrumented run that timed each acquire in the scan confirmed it: with churners of 16 KB (procinfotest’s workload) the scan held wait_lock for 50 to 80 µs on average (worst case under 0.5 ms), while after growing to 304 pages it averaged 573 µs, almost all of it spent waiting at USED slots. The row is still a fair A/B comparison of the two kernels. The lesson is that the longest p->lock hold in this kernel is kfork’s, not the schedulers’, and that a scan pays for whatever the other holders of the locks it visits are doing.

7. Go further

A top. Take two snapshots a second apart and show what changed. Pids are never reused here (nextpid only grows), so matching records across snapshots is easy; with the per-process CPU time of lab 4 you can sort by usage. Teaches why a snapshot is always about the past.
Exact names. Make kexec write p->name under p->lock, or give each process a sequence counter that kexec bumps before and after the write, and have procinfo retry while the counter is odd or changed. Teaches the seqlock pattern: consistent reads without blocking the writer.
A consistent instant. Take all 64 p->locks in slot order (plus wait_lock), read everything, release in reverse. Measure how long the other harts stall, and whether two such scans on two harts can deadlock (they take the locks in the same order). Teaches what global consistency costs.
One process. procinfo1(pid, struct pinfo *) for a single process. With pids never reused, a kill-style “find, then act” stays safe even when the process exits in between. Teaches the difference between naming a process by pid and by slot.
Wedge-proof dump. Change procdump to try each p->lock a bounded number of times and mark slots it could not lock. Teaches why a debugging path must never block, and what a try-lock looks like on RISC-V.