Step 1 of 15 · commit 1: Declare procinfo and struct pinfo

A record both sides agree on

The story for this tour is a recorded run on three harts: at a fresh shell you type ps. ps is pid 3, running on hart 1; init (pid 1) and the shell (pid 2) are asleep, init in wait for the shell and the shell in wait for ps. The machine-state values in the steps for sys_procinfo and procinfo come from that run, with QEMU started halted and breakpoints set before it ran.

The first commit defines the record. It lives in its own header because two programs compiled separately, the kernel and ps, must agree on it byte for byte: the kernel fills it, copyout copies its bytes, and ps reads them through the same declaration.

The layout has no padding: four ints (16 bytes), then the 8-byte sz at offset 16, already aligned, then 16 characters, 40 bytes in all. That matters for a structure the kernel hands to user space: a padding hole would be a few bytes the kernel copies out without ever writing, whatever happened to be in its buffer before.

state is the kernel’s enum procstate number. User programs cannot include kernel/proc.h (it needs the kernel’s spinlock and page-table types), so ps keeps its own table of names for 1 to 5.

Step 2 of 15 · commit 1: Declare procinfo and struct pinfo

One forward declaration, one stub

The rest of the plumbing is what every system call needs (Tour 5: Life of a system call): number 23 in kernel/syscall.h, entry("procinfo") in user/usys.pl to generate the stub (li a7, SYS_procinfo, ecall, ret), and the prototype on line 29.

Line 4 is the one new idea. user.h is included by every user program, and most of them never include pinfo.h. A prototype that mentions struct pinfo * where no struct pinfo has been declared makes the compiler declare a new structure type valid only inside that parameter list, and it warns. Under -Werror the build stops: 'struct pinfo' declared inside parameter list will not be visible outside of this definition or declaration (recorded by removing line 4). struct pinfo; declares the tag without its contents, exactly as struct stat; on line 3 does for fstat. A pointer to an incomplete structure is enough for a prototype.

At this commit the kernel has no handler yet: a call would reach syscall, fail its range check, print an “unknown sys call 23” message and return -1.

Step 3 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

sys_procinfo checks its arguments

ps called procinfo(buf, 64), its stub put 23 in a7, and usertrap sent the trap to syscall with interrupts back on (in the recorded run sstatus was 0x200000022 at line 126: SIE set). The handler fetches its two arguments from the trapframe: the buffer address with argaddr (in the run 0x1010, ps’s global array) and max with argint.

Neither is trusted. argaddr does not check the address at all; the copyout at the end will, page by page, against ps’s own page table. max is checked here: negative is refused, and anything above NPROC is clamped, since the table cannot hold more and the kernel’s buffer is sized for exactly NPROC records.

The stack is ps’s kernel stack, which was empty when the trap arrived: here it holds just the frames of usertrap, syscall and sys_procinfo.

Step 4 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

A private page to gather into

The records are gathered in a page from kalloc (0x87f26000 in the recorded run), not on the stack and not in a global array. The stack is a single page: in the recorded run procinfo ran with sp at 0x3fffff9f20, 224 bytes below the top, and a 2,560-byte array would have taken more than half of what is left before the guard page. A global array would be shared by three harts calling procinfo at once. The page belongs to this call alone.

Line 135 checks that 64 records fit in the page. Both sides of the comparison are constants, so the compiler decides it at compile time; the built kernel contains no code for it. It still documents the assumption and would fire at once (in the first call) if someone grew NPROC or the record. log.c uses the same kind of check for its header.

kalloc fills the page with the byte 5, so nothing of a previous owner can leak out, and the scan writes every field of every record it returns.

Step 5 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

The scan, one slot at a time, under p->lock

procinfo walks all 64 slots and takes each slot’s lock in turn, the same pattern as scheduler, wakeup and kkill. Here it is at slot 0, init. Holding p->lock means interrupts are off on this hart and noff is 1; intena is 1 because interrupts were on when the system call took its first lock. (At this commit there is no wait_lock yet; the recorded run, on the final branch, showed noff 2 at this line, one more for wait_lock.)

What the lock buys: state and pid are written only under it, so the UNUSED test, the copy of pid and the copy of state all see one moment of this process’s life. A process that is being freed by freeproc on another hart is either fully there or fully UNUSED; one being created by allocproc either has its pid and USED, or neither.

The loop condition also stops at max records. In the recorded run max was 64 and three slots were in use, so all 64 slots were visited and three records filled.

Step 6 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

name and sz, read the way procdump reads them

sz and name are a different matter. The process writes them about itself with no lock: growproc and lazy sbrk change sz, and kexec writes both. Holding p->lock excludes none of those writes, so these two fields are read without any protection, exactly as procdump reads them.

The code makes the read safe rather than exact. sz is one aligned 8-byte load: it can be stale (from just before a sbrk), never half of one value and half of another. name is copied as a fixed 16 bytes, and byte 15 is set to 0, so whatever kexec's safestrcpy is doing at that instant, ps receives a terminated string of at most 15 characters: perhaps an old name, perhaps a mixture (reasoned, not observed). In the recorded run the three names were init, sh and ps.

Making these fields exact would mean changing their writers to take p->lock, and moving them into the locked section of struct proc for every future writer too.

Step 7 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

What procdump does, and why it may

For comparison, the kernel’s own process listing. The state shown is an illustration, not part of the recorded run: you typed Ctrl-P while hart 0 was idle in its scheduler, the UART interrupt landed there, and consoleintr called procdump holding cons.lock, with interrupts off and intena 0 because the interrupt handler started with them off.

procdump takes no lock at all: no p->lock for state and pid, nothing for name. The comment on line 676 gives the reason: it is meant for a machine that may be stuck, and the usual cause of a stuck machine is a lock that is never released. A dump that took p->lock would hang on exactly the slot you want to see. A torn line on the console is the price, and nobody acts on that line.

procinfo runs as an ordinary system call on a working machine, and its records go to a program that may act on them. So it takes the locks that make state, pid and the hart true, and treats only name and sz the way procdump treats everything. Notice also the continue on line 696: harmless here, because procdump holds nothing; with a lock added at the top of the loop it would skip the release (clinic 6).

Step 8 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

Release everything, then one copyout

procinfo has returned with every lock released: in the recorded run, at line 140, noff was 0, sstatus was 0x200000022 (interrupts on again), n was 3 and the page held {pid 1, ppid 0, sleeping, cpu -1, 16384, "init"}, {2, 1, sleeping, -1, 20480, "sh"} and {3, 2, running, 1, 16384, "ps"}.

Now one copyout moves n * 40 bytes to ps’s buffer at 0x1010, translating the address through ps’s page table. If the buffer is bad (not mapped, not writable, or above sz), it returns -1 and so does the call. Either way the page goes back with kfree.

The copy happens outside every lock. In this tree that is a choice, not a necessity: the next step shows that copyout can neither sleep nor fault, and kwait calls it under two spinlocks. Clinic 1 ran the version that copies under the locks and found no failure and no measurable difference. What the choice buys is independence: the locked code does not depend on what copyout might do, and a failure has no lock to unwind.

Step 9 of 15 · commit 2: Gather a snapshot under p->lock, then copy out once

What copyout can do while you wait for it

To decide whether copyout may run under a spinlock, list what it can do. For each page of the destination:

• walkaddr looks up the user address in the process’s page table: a pure software walk, no lock.
• If nothing is mapped there, vmfault is called (line 357). It refuses addresses at or above sz; otherwise it calls kalloc, which takes kmem.lock for a few instructions, zeroes the new page, and maps it with mappages, which may kalloc page-table pages too. It never sleeps.
• The PTE must be writable, which rejects ps’s text.
• memmove copies to pa0, the physical address, through the kernel’s direct map. The kernel never uses the user virtual address, so the hardware has nothing to fault on.

So in this kernel copyout is safe under a spinlock: no sleep (which sched would catch with sched locks), no fault, and only kmem.lock nested inside, which takes nothing else. That is exactly why kwait can copy the exit status out while holding wait_lock and the child’s p->lock. The reference still keeps the copy outside, so that a future vmfault that waits for a disk does not turn procinfo into a panic.

Step 10 of 15 · commit 3: Report the parent's pid, under wait_lock

wait_lock around the scan, for the parent

parent is protected by wait_lock, and the rule (comment at kernel/proc.c:26) is that wait_lock comes before any p->lock. So procinfo takes it once, before the loop, and holds it to the end. In the recorded run, at the first record noff was 1 at line 719 (only wait_lock, whose cpu field pointed at hart 1’s struct cpu) and 2 at line 723; intena stayed 1.

For slot 1, the shell, p->parent was 0x8000fdd0 <proc>: slot 0, init, so ppid is

1. For init itself the pointer is 0 and ppid is 0.

Reading the parent’s pid without the parent’s p->lock is safe here, and the comment says why: pid changes only when a slot is allocated or freed, a process with children is freed only by kwait under wait_lock, and its children are handed to init under wait_lock before that. Holding wait_lock for the whole scan also freezes every parent link, every exit and every reap until the scan ends, so a non-zero ppid names a process that is in the same snapshot, as long as max did not cut the scan short.

Step 11 of 15 · commit 3: Report the parent's pid, under wait_lock

The paths that fix the order

Why must procinfo take wait_lock first? Because this code, and kexit, already hold wait_lock while they take p->locks. The state shown is an illustration (the hart is a guess): after ps exits, the shell wakes in kwait, holding wait_lock, and takes ps’s lock at line 385 to look at its state. Then, still holding wait_lock, it may call killed at line 409, which takes the shell’s own p->lock. kexit does the same with wakeup(p->parent), which takes every p->lock in turn.

If procinfo held some p->lock and then asked for wait_lock, one of these paths holding wait_lock and asking for that same p->lock closes a cycle:

Clinic 2 recorded this exact pair, with hart 0 trapped as well. Lock order is not a local decision: a new function must follow the order every existing path already uses.

Step 12 of 15 · commit 4: Show which hart runs a RUNNING process

Which hart, from c->proc

The scan has reached slot 2, ps itself: it holds its own p->lock now, which is allowed, since a running process does not hold its own lock. The state is RUNNING, so the loop looks for a hart whose c->proc points here. In the recorded run, at line 736, i was 1, and cpus[0].proc and cpus[2].proc were 0 (both harts idle) while cpus[1].proc was 0x800100a0 <proc+720>, slot 2. So ps’s record says cpu 1, and that is the line ps printed.

The answer is reliable because of the lock, not because of anything about the other harts: c->proc changes to or from p only while p->lock is held (next step). And it is reliable only until the release on line 748. A moment after the system call returns, ps may take a timer interrupt, yield, and continue on hart 0.

NCPU is 8 and QEMU has three harts here; cpus[3] to cpus[7] never run a scheduler, so their proc stays 0 and the loop simply finds nothing there.

Step 13 of 15 · commit 4: Show which hart runs a RUNNING process

Why state and c->proc agree under p->lock

Here is the other side, on any hart’s scheduler (shown on hart 2). With the slot’s p->lock held it sets p->state = RUNNING (line 452) and c->proc = p (453), and switches to the process. When the process gives the CPU back, it has already taken its own p->lock in yield, sleep or kexit and changed its state, and the scheduler clears c->proc (461) before releasing that lock (464). Both changes happen inside the lock, so a reader holding p->lock can never see one without the other. (intena is 0 because the scheduler took the lock after intr_off() on line 443.)

This also explains the results of question 6. Each record is true at the moment its slot was locked, but the scheduler is free to run on other slots meanwhile. Suppose the scan has passed slot 3, read RUNNING on hart 0, and hart 0 then yields that process and picks the one in slot 9: the scan will find slot 9 RUNNING on hart 0 as well. The recorded run after usertests reported most RUNNING at once 4 on three harts, for exactly this reason.

Step 14 of 15 · commit 5: Add the ps user program

ps prints the snapshot

Back in user mode, ps holds a private copy of the snapshot in buf, its global array (at 0x1010 in this build). It makes one call with room for NPROC records, so it can never be truncated, and prints n lines. The user printf has no field widths, so the small helpers above main (col and itoa) pad the columns; itoa prints - for the -1 of a process that is not running.

Every line comes from one scan, but by the time they are printed the table has moved on: the shell may have woken up, and ps itself, listed as run 1, may already be on another hart. A ps can only ever report the past; what the kernel guarantees is that each line was true together at one moment, and that the parent links all belong to one moment too.

The recorded output:

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

Step 15 of 15 · commit 6: Add procinfotest

The test checks only what the design promises

The last part of procinfotest forks a child that spins and two that fork and wait in a loop, then calls procinfo for 20 ticks and checks every snapshot with this function. It checks exactly the promises of question 6: a valid pid and state in every record; no pid twice; a hart in a record exactly when it is RUNNING (the per-record guarantee of p->lock); and every non-zero ppid present in the same snapshot (the test asks for all 64 slots, so max never cuts the scan short; the guarantee of wait_lock).

It deliberately does not check that no two RUNNING records name the same hart, and the comment says why. A test that checked it would pass thousands of snapshots and then fail in the run after usertests, which saw four RUNNING records at once on three harts: a correct kernel, an over-strict test. A test must claim no more than the design guarantees.

The other checks: the test’s own record; a child seen sleeping in read, then as a zombie, then gone after wait; max values of 1, 0 and -1 against a buffer filled with 0xab; and bad buffers (address 0, which is read-only text; an address above sz; the trapframe page, which has no PTE_U) plus a lazily allocated one. Each prints OK or FAIL, and on failure the max check and the stress check print what they saw.