Runtime Source Reading — Practice Tasks¶

Twenty exercises that turn $GOROOT/src/runtime from a black box into a library you can read. The goal is not to modify the runtime — it is to navigate it: find the file, locate the symbol, follow the call chain from user code into assembly, and verify what you read against a running binary. Difficulty tiers: Junior, Middle, Senior, Staff.

Each task gives a Goal, a Starter (commands or Go scaffolding), step-by-step Instructions, Acceptance Criteria, and a folded Reference walkthrough. The runnable code is small — most tasks are 5–30 lines of Go plus a sequence of grep/objdump/dlv invocations. The hard part is the reading, not the writing.

A note on Go versions. The runtime moves; line numbers and exact symbol names drift between releases. Where a task says "Go 1.22", that's the calibration version. Run with go version; if you're on 1.21 or 1.23 the structure will be recognisable but offsets will shift. Treat any number in a path like proc.go:1234 as a hint, not a contract.

A note on tools. You need go, go tool objdump, go tool trace, and dlv (Delve) for full coverage. grep -nR is enough for the first five tasks. Tasks 11 and 17 are the ones that fail noisily without their tool installed.

Task 1 — Inventory $GOROOT/src/runtime/ (J)¶

Goal. Locate the runtime source tree on your machine, count the .go files, count the .s files, and identify which assembly files are amd64-specific.

Starter.

go env GOROOT
RT="$(go env GOROOT)/src/runtime"
ls "$RT" | head

Instructions.

1. Print GOROOT with go env GOROOT. Store the runtime path as RT=$(go env GOROOT)/src/runtime.
2. Count Go source files at the top level only: ls "$RT"/*.go | wc -l. Then recursively: find "$RT" -name '*.go' | wc -l. Note the difference.
3. Count assembly files top-level: ls "$RT"/*.s | wc -l. Then recursive: find "$RT" -name '*.s' | wc -l.
4. List which .s files are amd64-specific. The convention is *_amd64.s: ls "$RT"/*_amd64.s. Read the first ten lines of asm_amd64.s.
5. Note which .s files have no architecture suffix (e.g. asm.s, duff_amd64.s vs. duff_arm64.s). The unsuffixed ones are usually included via build tags inside the file itself — check with head -5 "$RT"/asm.s.
6. Write a one-line summary: "Go 1.22 ships N .go files (top-level: M) and K .s files total, of which J are amd64-specific."

Acceptance criteria.

• You can produce the four counts (top-level .go, recursive .go, top-level .s, amd64 .s) without re-running find each time.
• You can name three amd64-specific .s files from memory: asm_amd64.s, memmove_amd64.s, duff_amd64.s are good candidates.
• You can explain why runtime has both Go and assembly: the assembly files contain code that cannot be written in Go (raw stack manipulation, syscalls, atomic primitives the compiler can't emit).

$ RT="$(go env GOROOT)/src/runtime"
$ ls "$RT"/*.go | wc -l
       274
$ find "$RT" -name '*.go' | wc -l
     487
$ ls "$RT"/*.s | wc -l
      77
$ ls "$RT"/*_amd64.s
/usr/local/go/src/runtime/asm_amd64.s
/usr/local/go/src/runtime/duff_amd64.s
/usr/local/go/src/runtime/memclr_amd64.s
/usr/local/go/src/runtime/memmove_amd64.s
/usr/local/go/src/runtime/preempt_amd64.s
/usr/local/go/src/runtime/rt0_darwin_amd64.s
/usr/local/go/src/runtime/rt0_linux_amd64.s
/usr/local/go/src/runtime/rt0_windows_amd64.s
/usr/local/go/src/runtime/sys_darwin_amd64.s
/usr/local/go/src/runtime/sys_linux_amd64.s
$ ls "$RT"/*_amd64.s | wc -l
      10

Task 2 — Read hchan struct (J)¶

Goal. Open runtime/chan.go, locate the hchan struct definition, and explain each field in your own words. This is the central data structure behind every Go channel.

Starter.

RT="$(go env GOROOT)/src/runtime"
grep -n "^type hchan struct" "$RT/chan.go"

Instructions.

1. grep -n "^type hchan struct" "$RT/chan.go" — note the line number; you'll come back to it.
2. Open chan.go at that line. The struct is roughly 12 fields and fits on one screen.
3. For each field, write a one-sentence explanation. Aim for what it represents at runtime, not what its type is. "qcount uint — number of values currently in the buffer" is good. "qcount uint — an unsigned integer" is useless.
4. Pay particular attention to: buf unsafe.Pointer (where does it point? what is its size?), sendx/recvx (why two indices? what invariant connects them to qcount?), recvq/sendq (what kind of queue? what goes into them?), lock mutex (why a runtime.mutex and not sync.Mutex?).
5. Read the comment block immediately above the struct definition — it explains the memory layout in two paragraphs. Note what is not in the struct: there is no separate buffer header; the buffer is allocated contiguously with the struct itself for unbuffered+small channels.
6. Cross-reference with the makechan function (also in chan.go) to confirm your layout intuition — makechan is the only place fields are first written.

Acceptance criteria.

• You can list every field name from memory: qcount, dataqsiz, buf, elemsize, closed, timer, elemtype, sendx, recvx, recvq, sendq, lock. (Order may differ; field set should not.)
• You can answer: "Why is lock a mutex and not sync.Mutex?" — because sync.Mutex lives in sync which imports runtime; an import cycle would result. Plus runtime.mutex has no allocation and integrates with the runtime scheduler for gopark.
• You can answer: "What does dataqsiz == 0 mean?" — unbuffered channel; buf is nil; every send/recv goes through recvq/sendq.

type hchan struct {
    qcount   uint           // total data in the queue
    dataqsiz uint           // size of the circular queue
    buf      unsafe.Pointer // points to an array of dataqsiz elements
    elemsize uint16
    closed   uint32
    timer    *timer         // timer feeding this chan
    elemtype *_type         // element type
    sendx    uint           // send index
    recvx    uint           // receive index
    recvq    waitq          // list of recv waiters
    sendq    waitq          // list of send waiters
    lock     mutex
}

Task 3 — Find //go:nosplit and explain three (J)¶

Goal. Search the runtime for //go:nosplit pragma usages, pick three different functions, and explain why each must run without growing its stack.

Starter.

RT="$(go env GOROOT)/src/runtime"
grep -nR "//go:nosplit" "$RT" | head -20

Instructions.

1. Run the grep above. You'll see ~hundreds of matches across the runtime.
2. Skim the list. Look for short, low-level functions: getg, gosched_m, acquirem, releasem, atomic helpers, write barriers.
3. Pick three from these categories: (a) something that runs during stack growth (would deadlock if it grew its own stack), (b) something that runs without a valid g/m (cannot call into the scheduler safely), (c) something on the hot path where the prologue cost matters (loop bodies, atomic ops).
4. For each pick, open the file at the grep line, read the function body, and write a 2–3 sentence explanation of "why nosplit". The answer is always one of: "called during stack growth", "called without a valid g", "called on the user's signal stack", "called from assembly with non-standard frame layout", "the prologue branch is itself the perf bottleneck".
5. Use grep -A 1 "//go:nosplit" "$RT/proc.go" | head -40 to see the next-line function names quickly.

Acceptance criteria.

• You can name at least three runtime functions marked //go:nosplit and produce the correct reason for each.
• You can explain the danger: a nosplit function calling a non-nosplit function can blow past the small "nosplit budget" the linker enforces (currently 800 bytes), producing a link-time error.
• You can answer: "What is the nosplit stack budget?" — roughly 800 bytes, enforced by the linker (cmd/link/internal/ld/stackcheck.go). Functions whose worst-case call tree exceeds it fail to link.

// getg returns the pointer to the current g.
// The compiler rewrites calls to this function into instructions
// that fetch the g directly (from TLS or from the dedicated register).
//
//go:nosplit
func getg() *g

//go:nosplit
func acquirem() *m {
    gp := getg()
    gp.m.locks++
    return gp.m
}

// gogo continues the execution of gobuf.
//
//go:nosplit
func gogo(buf *gobuf)

Task 4 — Trace runtime.GOMAXPROCS (J)¶

Goal. Find the source of runtime.GOMAXPROCS, follow where the value is stored, and identify which other functions read it.

Starter.

RT="$(go env GOROOT)/src/runtime"
grep -nR "^func GOMAXPROCS" "$RT"

Instructions.

1. Locate the public GOMAXPROCS function. It lives in runtime/debug.go.
2. Read its body. Note that it both reads the current value and, if the argument is positive, sets a new one.
3. The setter path calls startTheWorldGC, stopTheWorldGC, and procresize. Open proc.go and find procresize.
4. procresize(nprocs int32) is where the actual P count is changed. Identify the global variable it writes to. The answer is gomaxprocs, a package-level int32.
5. Now search where gomaxprocs is read: grep -nR "\bgomaxprocs\b" "$RT" | head. Note hits in proc.go (scheduler decisions), mgcpacer.go (GC pacing), lock_*.go (spin-loop tuning).
6. Read the documentation comment above GOMAXPROCS. Note the constraint: "since Go 1.5, the default is the number of CPUs", and the historical "limited to 256 before 1.10".
7. Write a one-paragraph trace: "User calls runtime.GOMAXPROCS(N) in debug.go, which calls stopTheWorldGC, then procresize(N) in proc.go, which writes gomaxprocs and rebalances Ps and Ms, then startTheWorldGC resumes. Readers include the scheduler, GC pacer, and several low-level spin loops."

Acceptance criteria.

• You can name the function in runtime/debug.go that exposes GOMAXPROCS.
• You can name procresize as the function that actually changes the count.
• You can name gomaxprocs (lowercase) as the global storing the value.
• You can list at least three callers of gomaxprocs other than procresize itself.

// runtime/debug.go (Go 1.22, abridged):
func GOMAXPROCS(n int) int {
    if GOARCH == "wasm" && n > 1 {
        n = 1 // wasm has no threads
    }
    lock(&sched.lock)
    ret := int(gomaxprocs)
    unlock(&sched.lock)
    if n <= 0 || n == ret {
        return ret
    }
    stopTheWorldGC(stwGOMAXPROCS)
    // newprocs will be processed by startTheWorld
    newprocs = int32(n)
    startTheWorldGC(stwGOMAXPROCS)
    return ret
}

// runtime/proc.go (Go 1.22, abridged):
func procresize(nprocs int32) *p {
    old := gomaxprocs
    // ... handle allp slice resize ...
    // ... initialise new Ps ...
    // ... migrate runnable Gs from idle Ps to allp[0] ...
    // ... idle excess Ps ...
    gomaxprocs = nprocs
    // ... return a P for the caller to bind ...
}

Task 5 — Trace ch <- v to assembly (M)¶

Goal. Write a tiny program that sends on a channel, compile with assembly listing enabled, and identify the assembly call site that bridges into runtime.chansend1.

Starter.

// main.go
package main

func main() {
    ch := make(chan int, 1)
    ch <- 42
    <-ch
}

Instructions.

1. Save the program above as main.go.
2. Build with assembly output: go build -gcflags=-S main.go 2>asm.txt. The -S flag dumps the generated assembly to stderr; we redirect to a file.
3. Open asm.txt. It contains assembly for every function in the package — main.main, all referenced runtime functions, and stdlib helpers.
4. Find the section for main.main. Look for a CALL instruction whose target is runtime.chansend1. Note its exact form (PCREL offset, surrounding instructions).
5. Note that the Go statement ch <- 42 compiles to: load ch and &42 into argument registers (or onto stack on older ABIs), then CALL runtime.chansend1(SB). The compiler does not inline channel sends.
6. Also identify runtime.makechan and runtime.chanrecv1 calls in the same listing — make(chan int, 1) becomes runtime.makechan, <-ch becomes runtime.chanrecv1.
7. Use go tool objdump -s "main.main" main for an alternative view that operates on the compiled binary (post-link), showing real addresses.

Acceptance criteria.

• You can point at the line in asm.txt containing CALL runtime.chansend1(SB).
• You can name the three runtime helpers a make(chan int, 1); ch <- 42; <-ch program calls: makechan, chansend1, chanrecv1.
• You can answer: "Why chansend1 and not chansend?" — chansend1 is the call shim for the operator form; it's a tiny wrapper that calls chansend(c, elem, true, getcallerpc()) with the block=true argument set. The unblocked variant used by select is selectnbsend.

"".main STEXT size=152 args=0x0 locals=0x40 funcid=0x0 align=0x0
    0x0000  TEXT    "".main(SB), ABIInternal, $64-0
    0x0000  CMPQ    SP, 16(R14)
    0x0004  PCDATA  $0, $-2
    0x0004  JLS     0x8e
    0x0006  PCDATA  $0, $-1
    0x0006  SUBQ    $64, SP
    0x000a  MOVQ    BP, 56(SP)
    0x000f  LEAQ    56(SP), BP
    ; ch := make(chan int, 1)
    0x0014  LEAQ    type:chan int(SB), AX
    0x001b  MOVL    $1, BX
    0x0020  PCDATA  $1, $0
    0x0020  CALL    runtime.makechan(SB)
    0x0025  MOVQ    AX, "".ch+24(SP)   ; spill ch pointer
    ; ch <- 42
    0x002a  MOVQ    AX, AX             ; ch in AX
    0x002d  LEAQ    "".statictmp+0(SB), BX  ; addr of literal 42
    0x0034  PCDATA  $1, $1
    0x0034  CALL    runtime.chansend1(SB)
    ; <-ch
    0x0039  MOVQ    "".ch+24(SP), AX
    0x003e  LEAQ    "".tmp+16(SP), BX
    0x0043  PCDATA  $1, $2
    0x0043  CALL    runtime.chanrecv1(SB)
    0x0048  MOVQ    56(SP), BP
    0x004d  ADDQ    $64, SP
    0x0051  RET

//go:nosplit
func chansend1(c *hchan, elem unsafe.Pointer) {
    chansend(c, elem, true, getcallerpc())
}

Task 6 — Read runtime.gopark (M)¶

Goal. Open runtime.gopark in runtime/proc.go, identify its five arguments, and explain what each controls.

Starter.

grep -n "^func gopark" "$(go env GOROOT)/src/runtime/proc.go"

Instructions.

1. Locate gopark. It's defined in proc.go.
2. Read the signature: func gopark(unlockf func(*g, unsafe.Pointer) bool, lock unsafe.Pointer, reason waitReason, traceReason traceBlockReason, traceskip int).
3. For each parameter, write a sentence:
4. unlockf: callback invoked after the goroutine is marked _Gwaiting but before control transfers away. Returning false aborts the park (rare — used in racy double-check patterns).
5. lock: opaque pointer passed to unlockf. Typically the lock that protected the wait queue this goroutine just enqueued itself onto.
6. reason: a waitReason enum value. Visible in goroutine stack dumps as [chan send], [chan receive], [select], [sleep], etc.
7. traceReason: similar but for the runtime tracer (the runtime/trace machinery). Different enum because trace categories are coarser than diagnostic reasons.
8. traceskip: number of stack frames to skip when recording the park event in the trace, so the trace shows the user's frame, not gopark's.
9. Search where gopark is called from: grep -nR "gopark(" "$(go env GOROOT)/src/runtime" | head. Note hits in chan.go (channel send/recv block), sema.go (semaphore wait), time.go (sleep), select.go (select block), netpoll.go (network wait).
10. For two of those call sites, read the surrounding 10 lines and identify which waitReason is passed. Examples: chan.go::chansend passes waitReasonChanSend, time.go::timeSleep passes waitReasonSleep.
11. Look at the body of gopark: it gets the current g, calls mcall(park_m). The actual park-and-switch happens in park_m, which runs on the g0 stack.

Acceptance criteria.

• You can recite the five arguments by name and purpose without looking.
• You can name three gopark call sites and the waitReason each uses.
• You can answer: "Why does gopark use mcall?" — because the actual context switch needs to run on g0 (the system stack), not on the user goroutine's stack. mcall is the runtime primitive that switches to g0 and invokes the callback there.

// Puts the current goroutine into a waiting state and calls unlockf on the
// system stack. unlockf is called with the g's status set to _Gwaiting. If
// unlockf returns false, the goroutine is put back on the run queue.
//
// reason explains why the goroutine has been parked. It is displayed in
// stack traces and heap dumps. Reasons should be unique and descriptive.
// Do not re-use reasons, add new ones.
//
//go:nosplit
func gopark(unlockf func(*g, unsafe.Pointer) bool, lock unsafe.Pointer,
            reason waitReason, traceReason traceBlockReason, traceskip int) {
    if reason != waitReasonSleep {
        checkTimeouts() // timeouts may expire while two goroutines keep the scheduler busy
    }
    mp := acquirem()
    gp := mp.curg
    status := readgstatus(gp)
    if status != _Grunning && status != _Gscanrunning {
        throw("gopark: bad g status")
    }
    mp.waitlock = lock
    mp.waitunlockf = unlockf
    gp.waitreason = reason
    mp.waitTraceBlockReason = traceReason
    mp.waitTraceSkip = traceskip
    releasem(mp)
    mcall(park_m) // park the goroutine; runs on g0
}

Task 7 — //go:linkname to call runtime.fastrand (M)¶

Goal. Use //go:linkname from a non-runtime package to call the unexported runtime.fastrand. Print 10 values to confirm.

Starter.

// main.go
package main

import (
    "fmt"
    _ "unsafe" // required for go:linkname
)

//go:linkname runtimeFastrand runtime.fastrand
func runtimeFastrand() uint32

func main() {
    for i := 0; i < 10; i++ {
        fmt.Println(runtimeFastrand())
    }
}

Instructions.

1. Save the program above.
2. Note the import of _ "unsafe" — required by the toolchain because //go:linkname is considered an unsafe feature; without the blank import, the compiler rejects the pragma.
3. Build: go build main.go. Run: ./main.
4. Note the output: 10 32-bit unsigned integers. They're pseudo-random; running the program multiple times produces different sequences because the runtime seeds fastrand per-m at thread start.
5. Inspect fastrand in the runtime: grep -n "func fastrand" "$(go env GOROOT)/src/runtime/stubs.go". Read the body. As of Go 1.22 it's a small wyrand-style mixer using m.fastrand (per-thread state).
6. Note the trade-off: fastrand is fast (no lock, no syscall) but not cryptographically secure. The runtime uses it for things like hashmap iteration order randomisation, scheduler-victim selection, GC trigger jitter — places where speed matters and adversarial input is not a concern.
7. Be aware of breakage risk: fastrand was renamed to runtime.cheaprand in Go 1.22 in some snapshots. If the build fails with relocation target runtime.fastrand not found, switch the linkname to runtime.cheaprand (or check runtime/stubs.go for the current name on your version).

Acceptance criteria.

• Your program builds and prints 10 uint32 values.
• You can explain the role of _ "unsafe": it's a compiler gate that says "yes, I'm using unsafe pragmas".
• You can articulate the rule of thumb: //go:linkname to runtime symbols is a hack used by stdlib (os, time, net) and major libraries (runtime/pprof, cgo). Application code should avoid it — the symbols can be renamed or deleted between Go releases without warning. Go 1.22's cheaprand rename is a recent example.

$ go build main.go && ./main
3215488821
1738596234
4081722904
...

//go:nosplit
func fastrand() uint32 {
    mp := getg().m
    // ... wyrand mixer using mp.fastrand[0], mp.fastrand[1] ...
    return uint32(...)
}

Task 8 — Read gopanic and the defer chain (M)¶

Goal. Open runtime/panic.go::gopanic, read it end to end, and write a 5-step summary of the defer-chain unwind algorithm.

Starter.

grep -n "^func gopanic" "$(go env GOROOT)/src/runtime/panic.go"

Instructions.

1. Locate gopanic in panic.go. Note the size — it's one of the longer runtime functions, ~200 lines.
2. Read top-to-bottom once without taking notes. Get the shape: it's a loop over the current goroutine's _defer linked list (gp._defer), invoking each deferred function and either continuing or returning.
3. Identify the key fields touched: gp._panic, gp._defer, _defer.started, _defer.fn, _defer.sp, _defer.pc. Look at runtime2.go for the _defer struct definition if you haven't seen it.
4. Identify the four termination cases:
5. Defer calls recover(): panic is "consumed"; gopanic returns via mcall(recovery) which jumps back to the deferred function's caller's frame.
6. Defer panics again (nested panic): a new _panic is pushed; the old one is marked aborted. The loop continues unwinding under the new panic.
7. Defer returns normally: just pop and continue with the next defer.
8. No more defers: call fatalpanic which prints the panic, runs all goroutine stacks (if GOTRACEBACK=all), and exits.
9. Write a 5-step summary:
10. Push a new _panic record onto gp._panic, linking to the previous panic if any.
11. Walk gp._defer from newest to oldest. Mark each as started to detect nested panics in the same defer.
12. Invoke the deferred function. If it calls recover(), that sets _panic.recovered = true.
13. After the call, check _panic.recovered: if true, jump back via mcall(recovery) to the deferred function's caller's resumption PC.
14. If never recovered, after the last defer call fatalpanic to terminate the program.
15. Cross-check with the open-coded defer optimisation: since Go 1.14, defers in functions with simple control flow are open-coded (inlined into the function, with bitmap-tracked execution). For those, gopanic walks them by examining the stack frame's defer bitmap, not the _defer linked list. See runtime/panic.go::runOpenDeferFrame.

Acceptance criteria.

• You can sketch the 5-step algorithm from memory.
• You can name the function runtime.recovery and explain its role: it's the assembly stub that resumes execution at the deferred function's caller, restoring SP/PC from _defer.sp/_defer.pc.
• You can answer: "How does nested panic (panicking in a deferred function during another panic) work?" — the new panic pushes a fresh _panic record; the old one is marked aborted (p.aborted = true); the loop continues unwinding under the new panic; the original is never recovered.

func gopanic(e interface{}) {
    gp := getg()
    // 1. Push new _panic
    var p _panic
    p.arg = e
    p.link = gp._panic
    gp._panic = &p

    // 2. Walk defers
    for {
        d := gp._defer
        if d == nil {
            break // fall through to fatalpanic
        }

        // Bookkeeping
        if d.started {
            if d._panic != nil {
                d._panic.aborted = true
            }
            d._panic = nil
            d.fn = nil
            gp._defer = d.link
            freedefer(d)
            continue
        }
        d.started = true
        d._panic = &p

        p.argp = unsafe.Pointer(getargp())

        // 3. Call deferred function
        reflectcall(nil, unsafe.Pointer(d.fn), deferArgs(d), uint32(d.siz), uint32(d.siz), &regs)

        // ... bookkeeping ...

        // 4. Did the defer recover us?
        if p.recovered {
            atomic.Xadd(&runningPanicDefers, -1)
            gp._panic = p.link
            // Find recovery target — sp/pc to resume at
            gp.sigcode0 = uintptr(sp)
            gp.sigcode1 = pc
            mcall(recovery) // does not return
            throw("recovery failed")
        }
    }

    // 5. No defer recovered — terminal
    fatalpanic(gp._panic)
    *(*int)(nil) = 0 // not reached
}

type _defer struct {
    started bool
    heap    bool
    openDefer bool
    sp        uintptr  // sp at time of defer
    pc        uintptr  // pc at time of defer
    fn        *funcval // can be nil for open-coded defers
    _panic    *_panic  // panic that is running defer
    link      *_defer
    // ... fields for open-coded defers ...
}

func A() { defer B(); panic("boom") }
func B() { if r := recover(); r != nil { fmt.Println("got", r) } }

func C() { defer D(); panic("first") }
func D() { panic("second") }

Task 9 — Read newproc (M)¶

Goal. Open runtime/proc.go::newproc, identify which P the newly created goroutine is enqueued on, and explain the run queue layout.

Starter.

grep -n "^func newproc" "$(go env GOROOT)/src/runtime/proc.go"

Instructions.

1. Find newproc. Note the signature: func newproc(fn *funcval). It's called by the compiler for every go f(...) statement (after the args are packaged).
2. Read top-to-bottom. The function:
3. Acquires m via acquirem (pinning to the current OS thread for the duration).
4. Calls newproc1(fn, gp, callerpc) to allocate or recycle a g.
5. Calls runqput(p, newg, true) to enqueue.
6. Calls wakep() to wake a sleeping P if there is one and the work queue grew.
7. Open newproc1. It either pops a free g from p.gFree (cached free list) or sched.gFree (global free list), or allocates a fresh g with malg(stacksize). It then sets up the gobuf (saved register set) so that when the scheduler runs this g, it'll start executing at fn.
8. Open runqput. The runqueue is per-P. Layout:
9. p.runqhead, p.runqtail: atomic uint32 indices.
10. p.runq: fixed-size array of 256 *g.
11. p.runnext: a "next g to run" slot. If non-nil, it's the highest-priority work on this P.
12. runqput(p, newg, true) writes newg to p.runnext, displacing whatever was there. The displaced g goes to the tail of p.runq. If p.runq is full (256 entries), it gets bulk-moved to the global queue sched.runq along with half the local queue.
13. Conclusion: a new goroutine always goes on the current P's runnext slot first. This gives "go-then-call-now" patterns excellent locality — the new g and the launching g share whatever cache the current P was hot on.

Acceptance criteria.

• You can name newproc as the entry point, newproc1 as the allocator, and runqput as the enqueuer.
• You can describe the runqueue: per-P, ring buffer of 256, plus a one-slot runnext for the freshly-scheduled g.
• You can answer: "Why runnext?" — it's the LIFO optimisation. Programs that do go f(x); g(x) get better locality when f runs immediately after g blocks; LIFO via runnext makes that the default behaviour.
• You can answer: "What happens when the local runqueue overflows?" — half of it plus the incoming g is moved to the global sched.runq in one batch, amortising the lock cost across 128 goroutines.

func newproc(fn *funcval) {
    gp := getg()
    pc := getcallerpc()
    systemstack(func() {
        newg := newproc1(fn, gp, pc)

        pp := getg().m.p.ptr()
        runqput(pp, newg, true) // true = put in runnext slot

        if mainStarted {
            wakep()
        }
    })
}

func newproc1(fn *funcval, callergp *g, callerpc uintptr) *g {
    mp := acquirem()
    pp := mp.p.ptr()
    newg := gfget(pp)             // try local free list
    if newg == nil {
        newg = malg(stackMin)     // allocate new g with stack
        casgstatus(newg, _Gidle, _Gdead)
        allgadd(newg)              // register in global g list for GC
    }

    // Set up gobuf so the scheduler can launch this g.
    sp := newg.stack.hi
    sp -= sys.MinFrameSize
    newg.sched.sp = sp
    newg.stktopsp = sp
    newg.sched.pc = funcPC(goexit) + sys.PCQuantum
    newg.sched.g = guintptr(unsafe.Pointer(newg))
    gostartcallfn(&newg.sched, fn)
    // ... ancestor tracking, race annotations ...
    casgstatus(newg, _Gdead, _Grunnable)

    releasem(mp)
    return newg
}

func runqput(pp *p, gp *g, next bool) {
    if next {
    retryNext:
        oldnext := pp.runnext
        if !pp.runnext.cas(oldnext, guintptr(unsafe.Pointer(gp))) {
            goto retryNext
        }
        if oldnext == 0 {
            return
        }
        gp = oldnext.ptr() // displaced g goes to tail
    }

retry:
    h := atomic.LoadAcq(&pp.runqhead)
    t := pp.runqtail
    if t-h < uint32(len(pp.runq)) {
        pp.runq[t%uint32(len(pp.runq))].set(gp)
        atomic.StoreRel(&pp.runqtail, t+1)
        return
    }
    // Local queue full → push half to global
    if runqputslow(pp, gp, h, t) {
        return
    }
    goto retry
}

Task 10 — Diff chan.go between Go 1.20 and 1.22 (M)¶

Goal. Compare runtime/chan.go between Go 1.20 and Go 1.22. List the non-trivial changes — not whitespace, not comment edits.

Starter.

# Easiest: use the GitHub blob comparison directly.
# https://github.com/golang/go/blob/release-branch.go1.20/src/runtime/chan.go
# https://github.com/golang/go/blob/release-branch.go1.22/src/runtime/chan.go

Instructions.

1. If you have multiple Go installations side by side: diff -u /path/to/go1.20/src/runtime/chan.go /path/to/go1.22/src/runtime/chan.go > chan-diff.patch.
2. Otherwise, grab both files from the GitHub release branches:
3. curl -fsSL https://raw.githubusercontent.com/golang/go/release-branch.go1.20/src/runtime/chan.go -o chan-1.20.go
4. curl -fsSL https://raw.githubusercontent.com/golang/go/release-branch.go1.22/src/runtime/chan.go -o chan-1.22.go
5. diff -u chan-1.20.go chan-1.22.go | less
6. Skim the diff. Skip whitespace-only chunks (lines starting with - that are blank or comment edits).
7. Identify functionally-significant changes. Categories to look for:
8. New field added to hchan (timer *timer was added between 1.20 and 1.22 to support unified timer-driven channels).
9. Race annotations (raceacquire/racerelease) added or moved.
10. Comments correcting subtle race conditions in the lockless fast paths.
11. Changes to chansend/chanrecv parameter lists.
12. Changes to how closed channels behave under select (the 1.22 timer integration touched this).
13. For each non-trivial change, write a one-sentence note: "1.22 added hchan.timer to support time.NewTimer channels managed by the unified per-P timer heap" or "1.22 chansend removed the raceenabled check at line X because it's now hoisted into chansendN".
14. Optional: read the corresponding CL (changelist) on Gerrit. The commit messages on golang/go reference CL numbers; git log --oneline release-branch.go1.20..release-branch.go1.22 -- src/runtime/chan.go shows them.

Acceptance criteria.

• You can list at least three non-trivial diffs between 1.20 and 1.22 chan.go.
• You can identify the timer-integration change (the timer *timer field on hchan and related logic) — it's the largest single change to chan.go between those versions.
• You can answer: "What was the motivation for the 1.22 channel changes?" — primarily the unified timer rework (CL ~485815 and follow-ups). Pre-1.22, timer channels (time.After, time.Tick) used a separate mechanism with known scalability issues; 1.22 made them first-class channels driven by the per-P timer heap.

 type hchan struct {
     qcount   uint
     dataqsiz uint
     buf      unsafe.Pointer
     elemsize uint16
     closed   uint32
+    timer    *timer
     elemtype *_type
     sendx    uint
     ...
 }

 func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool {
     if c == nil {
         if !block {
             return false
         }
         gopark(nil, nil, waitReasonChanSendNilChan, traceBlockForever, 2)
         throw("unreachable")
     }
+    if c.timer != nil {
+        c.timer.maybeRunChan()
+    }
     if debugChan {
         print("chansend: chan=", c, "\n")
     }
     ...
 }

 func chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool) {
     ...
     if c == nil {
         ...
     }
+    if c.timer != nil {
+        c.timer.maybeRunChan()
+    }
     if debugChan {
         ...
     }
 }

 func closechan(c *hchan) {
+    if c.timer != nil {
+        // Closing a timer-managed channel is allowed but stops the timer.
+        c.timer.stop()
+    }
     if c == nil {
         panic(plainError("close of nil channel"))
     }
     ...
 }

Task 11 — Step into makechan with dlv (S)¶

Goal. Use Delve to step from a user program's make(chan int) into runtime.makechan and observe the parameters and local variables.

Starter.

// main.go
package main

func main() {
    ch := make(chan int, 4)
    _ = ch
}

Instructions.

1. Install Delve if not present: go install github.com/go-delve/delve/cmd/dlv@latest. Confirm: dlv version.
2. Build with debug info and no inlining: go build -gcflags='all=-N -l' -o main main.go. The flags disable optimisation (-N) and inlining (-l) — essential for debugging because optimised code reorders and elides locals.
3. Start dlv: dlv exec ./main.
4. Set a breakpoint at main.main: break main.main. Continue: continue. You stop at the first instruction of main.
5. Set another breakpoint at the runtime entry: break runtime.makechan. Continue: continue.
6. You're now in runtime.makechan with main paused. Run args to see the parameters: you'll see t *chantype, size int, and (depending on Go version) some compiler-injected return arg.
7. Print the size argument: print size. Should print 4.
8. Print the element size from the type descriptor: print t.elem.size. For chan int, should print 8.
9. Step into the function: step. Walk a few lines: next; next; next. Note what runtime does — it computes mem = elem.size * size, checks for overflow, calls mallocgc to allocate sizeof(hchan) + mem, then sets up the hchan fields.
10. When you reach the mallocgc call, examine the allocated pointer: print c. After the constructor sets fields: print c.qcount; print c.dataqsiz; print c.elemsize.
11. Continue to completion: continue. Program exits.

Acceptance criteria.

• You can drop into runtime.makechan under dlv and inspect at least size, c.dataqsiz, c.elemsize.
• You can answer: "Why -gcflags='all=-N -l'?" — without -N the optimiser eliminates locals; without -l makechan may itself be inlined into main.main. Either makes the debugging session useless.
• You can describe one runtime decision visible in the trace: e.g. "for size=4, elem.size=8, makechan chooses the buffered code path and computes mem = 32; the allocation is sizeof(hchan) + 32 in one mallocgc call".

$ go build -gcflags='all=-N -l' -o main main.go
$ dlv exec ./main
Type 'help' for list of commands.
(dlv) break main.main
Breakpoint 1 set at 0x47d18a for main.main() ./main.go:3
(dlv) continue
> main.main() ./main.go:3 (hits goroutine(1):1 total:1) (PC: 0x47d18a)
     1: package main
     2:
=>   3: func main() {
     4:     ch := make(chan int, 4)
     5:     _ = ch
     6: }
(dlv) break runtime.makechan
Breakpoint 2 set at 0x42a740 for runtime.makechan() /usr/local/go/src/runtime/chan.go:71
(dlv) continue
> runtime.makechan() /usr/local/go/src/runtime/chan.go:71 (hits goroutine(1):1 total:1) (PC: 0x42a740)
    66: //
    67: // For example, given the type-only signature
    68: //   chan int
    69: // make(chan int, n) is compiled to makechan(t, n) where t holds chan int.
    70:
=>  71: func makechan(t *chantype, size int) *hchan {
    72:     elem := t.elem
    73:
    74:     // compiler checks this but be safe.
    75:     if elem.size >= 1<<16 {
    76:         throw("makechan: invalid channel element type")
(dlv) args
t = ("*runtime.chantype")(0x49a420)
size = 4
~r0 = (unreadable empty OP stack)
(dlv) print size
4
(dlv) print t.elem.size
8
(dlv) next
> runtime.makechan() /usr/local/go/src/runtime/chan.go:72 (PC: 0x42a753)
(dlv) next
> runtime.makechan() /usr/local/go/src/runtime/chan.go:75 (PC: 0x42a756)
(dlv) next
> runtime.makechan() /usr/local/go/src/runtime/chan.go:79 (PC: 0x42a76c)
(dlv) next
> runtime.makechan() /usr/local/go/src/runtime/chan.go:84 (PC: 0x42a772)
(dlv) print mem
32
(dlv) print overflow
false
(dlv) next
(dlv) print c
("*runtime.hchan")(0xc00007e000)
(dlv) print c.qcount
0
(dlv) print c.dataqsiz
4
(dlv) print c.elemsize
8
(dlv) print c.buf
unsafe.Pointer(0xc00007e060)
(dlv) print c.elemtype
("*runtime._type")(0x49a3c0)
(dlv) continue
Process 12345 has exited with status 0

Task 12 — Read SetFinalizer and finalizer GC interaction (S)¶

Goal. Read runtime/mfinal.go::SetFinalizer, identify the data structures, and explain what the GC does when it discovers an object with a finalizer is unreferenced.

Starter.

grep -n "^func SetFinalizer" "$(go env GOROOT)/src/runtime/mfinal.go"

Instructions.

1. Open mfinal.go::SetFinalizer. Read its preconditions: argument must be a pointer to a heap-allocated object; finalizer must match the type. Many panic conditions exist; trace each to understand the API contract.
2. The function calls addfinalizer(obj, finalizer, nret, fint, ot) which stores the (object, finalizer) pair in a specialfinalizer record attached to the object's span.
3. Read mfinal.go::queuefinalizer — this is what the GC calls when it discovers a finalizer is ready to fire.
4. Read mfinal.go::runfinq — this is the finalizer goroutine. There's one per program. It loops, pulling work from finq and invoking each finalizer.
5. The GC lifecycle for finalized objects:
6. Mark phase: the GC scans roots, marks reachable objects. An object with a finalizer is marked through its finalizer reference even if the user has no other reference. So a finalized object survives the first GC after it becomes user-unreachable.
7. Finalizer queue: after marking, the GC checks each span for specialfinalizer records on objects that are NOT marked through user code. It revives those (marks them now), and enqueues their finalizers onto finq.
8. runfinq goroutine wakes, dequeues, invokes finalizers. Finalizers run on a single goroutine — order is not guaranteed across runs but is consistent within a run.
9. The object is removed from the finalizer set; on the next GC cycle, if still unreachable, it's collected.
10. Implications: a finalized object survives one extra GC cycle (the cycle where its finalizer fires). Calling SetFinalizer(p, nil) removes the finalizer and the object behaves normally thereafter.

Acceptance criteria.

• You can name specialfinalizer as the on-span record storing the finalizer.
• You can name finq and runfinq as the global queue and the dedicated finalizer goroutine.
• You can answer: "How many GC cycles does a finalized object survive?" — at least two (one to enqueue the finalizer, one to actually collect). In practice three or more if the finalizer itself re-references the object.
• You can answer: "Why is SetFinalizer discouraged?" — finalizers run on a single goroutine, possibly arbitrarily delayed; they don't run if the program exits; they can resurrect objects (calling SetFinalizer inside a finalizer with a self-reference); they break GC promptness. Prefer defer Close() for resource cleanup; SetFinalizer is only appropriate as a last-resort safety net (e.g. os.File uses it to warn about leaked FDs).

type specialfinalizer struct {
    special special    // _KindSpecialFinalizer marker, links into span's specials list
    fn      *funcval   // the finalizer function
    nret    uintptr    // bytes of return value
    fint    *_type     // type of the finalizer's argument
    ot      *ptrtype   // type of the original object (the pointer-to-T)
}

func addfinalizer(p unsafe.Pointer, fn *funcval, nret uintptr, fint *_type, ot *ptrtype) bool {
    lock(&mheap_.speciallock)
    s := (*specialfinalizer)(mheap_.specialfinalizeralloc.alloc())
    unlock(&mheap_.speciallock)
    s.special.kind = _KindSpecialFinalizer
    s.fn = fn
    s.nret = nret
    s.fint = fint
    s.ot = ot
    if addspecial(p, &s.special) {
        // Marked by GC scan to root finalizer fn.
        KeepAlive(p)
        return true
    }
    // Already had a finalizer: free and return false.
    lock(&mheap_.speciallock)
    mheap_.specialfinalizeralloc.free(unsafe.Pointer(s))
    unlock(&mheap_.speciallock)
    return false
}

func runfinq() {
    for {
        lock(&finlock)
        fb := finq
        finq = nil
        // ... wait if nothing to do ...
        unlock(&finlock)
        for fb != nil {
            for i := uint32(0); i < fb.cnt; i++ {
                f := &fb.fin[i]
                // ... arg setup ...
                reflectcall(f.fint, unsafe.Pointer(f.fn), frame, ...)
                // ... cleanup ...
            }
            // ... move fb to free list, advance to next ...
        }
    }
}

type Foo struct{}
p := &Foo{}
runtime.SetFinalizer(p, func(*Foo) { fmt.Println("finalized") })
p = nil
runtime.GC()  // first GC — finalizer queued
runtime.GC()  // second GC — object collected (only if finalizer goroutine has run)

Task 13 — Trace time.Sleep into the runtime (S)¶

Goal. Trace a time.Sleep(d) call from the time package into runtime/time.go::timeSleep, identify the call to gopark, and identify the mechanism that wakes the goroutine when the duration elapses.

Starter.

grep -n "^func Sleep" "$(go env GOROOT)/src/time/sleep.go"
grep -n "^func timeSleep" "$(go env GOROOT)/src/runtime/time.go"

Instructions.

1. Open src/time/sleep.go. time.Sleep(d) is a one-line wrapper that calls runtime.timeSleep(int64(d)) via //go:linkname. Note the linkname pragma at the top of the file.
2. Open runtime/time.go::timeSleep. Read top to bottom. The function:
3. Returns immediately if d <= 0.
4. Grabs the current g and reuses or creates the per-g timer gp.timer.
5. Sets up the timer with when = nanotime() + ns, f = goroutineReady (the wake function).
6. Calls resetForSleep (or similar — name has changed across versions) which schedules the timer.
7. Calls gopark(resetForSleep, &gp.timer, waitReasonSleep, traceBlockSleep, 2).
8. The gopark parks the goroutine. The unlockf is resetForSleep which finishes inserting the timer into the per-P timer heap (it has to be done after _Gwaiting is set, otherwise the wake could fire before park completes — a classic race).
9. When the timer fires (at when), the timer subsystem calls goroutineReady(arg, seq) which calls goready(arg.(*g), 0). goready flips the g's status from _Gwaiting to _Grunnable and puts it back on a run queue.
10. The goroutine eventually gets scheduled. From its perspective, gopark returned. timeSleep returns. time.Sleep returns.
11. Open runtime/time.go::checkTimers (called by the scheduler in findRunnable). This is where the per-P timer heap is consulted: if t.when <= now, fire the timer by calling its f.

Acceptance criteria.

• You can trace the call chain: time.Sleep → runtime.timeSleep (via linkname) → gopark → (timer expires) → goroutineReady → goready → scheduler resumes.
• You can name the wake function: goroutineReady.
• You can name the per-P timer storage: a min-heap of timers (runtime.p.timers [] and supporting heap operations in time.go).
• You can answer: "What prevents a timer firing while gopark is mid-way?" — the unlockf (resetForSleep) runs after the goroutine is marked _Gwaiting but before park yields control; the timer is only inserted into the heap at that point, so it cannot fire earlier.

// time/sleep.go
func Sleep(d Duration)

// Implementation linknamed to runtime.timeSleep:
//go:linkname runtime_timeSleep runtime.timeSleep
func runtime_timeSleep(ns int64)

func Sleep(d Duration) {
    runtime_timeSleep(int64(d))
}

// runtime/time.go (Go 1.22, abridged):
func timeSleep(ns int64) {
    if ns <= 0 {
        return
    }
    gp := getg()
    t := gp.timer
    if t == nil {
        t = new(timer)
        gp.timer = t
    }
    t.f = goroutineReady
    t.arg = gp
    t.nextwhen = nanotime() + ns
    if t.status != timerNoStatus && t.status != timerRemoved {
        throw("timeSleep: timer not stopped")
    }
    gopark(resetForSleep, unsafe.Pointer(t), waitReasonSleep, traceBlockSleep, 1)
}

// resetForSleep runs on g0 stack after the calling g is _Gwaiting.
// At this point it's safe to insert the timer; if it fires, the g
// is in _Gwaiting state and goready will promote it correctly.
func resetForSleep(gp *g, ut unsafe.Pointer) bool {
    t := (*timer)(ut)
    resettimer(t, t.nextwhen)
    return true
}

// runtime/time.go
func goroutineReady(arg any, seq uintptr) {
    goready(arg.(*g), 0)
}

// runtime/proc.go::findRunnable (abridged):
func findRunnable() (*g, bool) {
    pp := getg().m.p.ptr()
    ...
    if checkTimers(pp, 0) {
        // Wake-needed: a timer fired and produced runnable work
    }
    ...
}

// runtime/time.go::checkTimers:
func checkTimers(pp *p, now int64) (rnow, pollUntil int64, ran bool) {
    next := atomic.Load64(&pp.timer0When)
    if next == 0 || (now != 0 && next > now) {
        return now, int64(next), false
    }
    ...
    rnow, pollUntil, ran = runtimer(pp, now)
    ...
}

Task 14 — Read semacquire1 and the treap (S)¶

Goal. Open runtime/sema.go::semacquire1 and understand the treap (tree + heap) data structure used to manage waiters.

Starter.

grep -n "^func semacquire1" "$(go env GOROOT)/src/runtime/sema.go"

Instructions.

1. Open sema.go. Read the file header comment — it explains the design rationale: semaphores must be cheap when uncontested but support FIFO and LIFO release strategies on many waiters efficiently.
2. The waiter data structure is a treap (a tree that satisfies BST property on addr and heap property on ticket — a per-waiter random priority). The treap is at the leaves, and each leaf is a linked list of waiters on the same address (because multiple goroutines can wait on the same sync.Mutex).
3. Read semacquire1(addr *uint32, lifo bool, profile semaProfileFlags, skipframes int, reason waitReason). Steps:
4. Fast path: try to decrement *addr if positive. If success, no contention, return.
5. Slow path: allocate a sudog, fill in its fields (g = current goroutine, addr = addr, ticket = random).
6. Hash addr into one of semTabSize buckets (semtable). Each bucket has its own lock + root treap node.
7. Insert the sudog into the treap at addr. If a leaf at addr exists, append to its waiter linked list (FIFO at tail or LIFO at head). If no leaf, insert a new tree node and treap-rotate to maintain heap property on ticket.
8. Park the goroutine (goparkunlock — gopark variant that drops the bucket lock as unlockf).
9. The release side is semrelease1. It locks the bucket, finds the treap node for addr, pops a waiter (head for FIFO, tail for LIFO), wakes it via goready.
10. Why a treap? Because:
11. Buckets are hashed, so each bucket sees waiters at many distinct addresses. A BST on addr keeps lookups O(log W) where W is the number of distinct contended addresses in the bucket.
12. The heap property on ticket randomises the tree shape — without it, sequential lock addresses could create a degenerate linear tree, O(W) lookups.
13. Combined, you get expected O(log W) operations with no rebalancing logic (just rotate-up on insert based on ticket).
14. The number of buckets: semTabSize = 251 (a prime), so hash collisions are rare. Even on a program with thousands of mutexes, each bucket usually contains a handful of treap nodes.

Acceptance criteria.

• You can sketch the treap: BST on address, heap on random ticket priority.
• You can name sudog as the waiter record and semtable as the bucket array.
• You can answer: "Why is the treap necessary? Why not a hash table per address?" — too many addresses to keep one bucket per address; the treap inside a bucket handles collisions efficiently with constant memory per bucket.
• You can answer: "What does lifo=true change?" — when waking a goroutine on the same address, the waiter is taken from the head of the per-address linked list (most recent waiter wakes first). FIFO takes from the tail. sync.Mutex uses LIFO in starvation-prone mode, FIFO otherwise.

const semTabSize = 251

var semtable semTable

type semTable [semTabSize]struct {
    root semaRoot
    pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

type semaRoot struct {
    lock  mutex
    treap *sudog        // root of treap; sudog with smallest priority becomes root
    nwait atomic.Uint32 // number of waiters
}

type sudog struct {
    g *g

    next *sudog
    prev *sudog
    elem unsafe.Pointer // semaphore address (interpreted as *uint32 here)

    acquiretime int64
    releasetime int64
    ticket      uint32  // random priority for treap

    parent   *sudog // treap parent
    waitlink *sudog // g.waiting list or semaRoot waiters at same address
    waittail *sudog // semaRoot
    c        *hchan // channel (for chan-based sudogs; nil for sema)
    ...
}

func semacquire1(addr *uint32, lifo bool, profile semaProfileFlags, skipframes int, reason waitReason) {
    gp := getg()
    if gp != gp.m.curg {
        throw("semacquire not on the G stack")
    }
    // Fast path: 1 -> 0 transition on the semaphore.
    if cansemacquire(addr) {
        return
    }
    // Slow path: queue.
    s := acquireSudog()
    root := semtable.rootFor(addr)
    t0 := int64(0)
    s.releasetime = 0
    s.acquiretime = 0
    s.ticket = 0
    ...
    for {
        lockWithRank(&root.lock, lockRankRoot)
        // Add ourselves to nwait first to ensure release sees us.
        root.nwait.Add(1)
        if cansemacquire(addr) {
            // Raced with a fast release; reset and return.
            root.nwait.Add(-1)
            unlock(&root.lock)
            break
        }
        root.queue(addr, s, lifo)
        goparkunlock(&root.lock, reason, traceBlockSync, 4+skipframes)
        if s.ticket != 0 || cansemacquire(addr) {
            break
        }
    }
    releaseSudog(s)
}

func (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) {
    s.g = getg()
    s.elem = unsafe.Pointer(addr)
    s.next = nil
    s.prev = nil

    var last *sudog
    pt := &root.treap
    for t := *pt; t != nil; t = *pt {
        if t.elem == unsafe.Pointer(addr) {
            // Already a treap node at this address; append to its waiter list.
            if lifo {
                // New waiter takes the treap-node slot; old waiters become its list.
                *pt = s
                s.ticket = t.ticket
                s.acquiretime = t.acquiretime
                s.parent = t.parent
                s.prev = t.prev
                s.next = t.next
                if s.prev != nil { s.prev.parent = s }
                if s.next != nil { s.next.parent = s }
                s.waitlink = t
                s.waittail = t.waittail
                if s.waittail == nil { s.waittail = t }
                t.parent = nil
                t.prev = nil
                t.next = nil
                t.waittail = nil
            } else {
                // FIFO: append to tail of waiter list.
                if t.waittail == nil {
                    t.waitlink = s
                } else {
                    t.waittail.waitlink = s
                }
                t.waittail = s
                s.waitlink = nil
            }
            return
        }
        last = t
        if uintptr(unsafe.Pointer(addr)) < uintptr(t.elem) {
            pt = &t.prev
        } else {
            pt = &t.next
        }
    }
    // Insert as new treap node with random ticket.
    s.ticket = cheaprand() | 1
    s.parent = last
    *pt = s
    // Bubble up by ticket (treap heap property).
    for s.parent != nil && s.parent.ticket > s.ticket {
        if s.parent.prev == s { root.rotateRight(s.parent) } else { root.rotateLeft(s.parent) }
    }
}

Task 15 — Read selectgo and pseudo-random ordering (S)¶

Goal. Open runtime/select.go::selectgo, understand the pseudo-random case selection, and explain why the ordering matters.

Starter.

grep -n "^func selectgo" "$(go env GOROOT)/src/runtime/select.go"

Instructions.

1. Open select.go. The file is shorter than chan.go — selectgo is the meat (~300 lines).
2. Read the function signature: func selectgo(cas0 *scase, order0 *uint16, pc0 *uintptr, nsends int, nrecvs int, block bool) (int, bool). The compiler builds an array of scase (one per case), an order array of indices, and a pc array for race annotations. selectgo shuffles order and walks.
3. The algorithm:
4. Generate two random permutations of 0..ncases-1 using fastrand — pollorder (visit order for the first pass) and lockorder (lock acquisition order, sorted by channel pointer to avoid deadlock).
5. Lock all channels in lockorder. (This is where the sort matters: locking in pointer order prevents two selectgos on overlapping channel sets from deadlocking each other.)
6. First pass: walk pollorder. For each case, check if the channel is ready (send: buffer has space or recv waiting; recv: buffer has data or send waiting; closed: always ready for recv). If ready, execute the case, unlock all channels, return.
7. If no case is ready and block=false (a default case exists), return default's index.
8. Otherwise enqueue this goroutine as a waiter on every channel (a sudog per case linked via waitlink). Unlock all channels. gopark.
9. When woken, identify which case fired (the sudog whose success field is set), dequeue from all other channels, unlock, return.
10. Why pseudo-random pollorder? To prevent starvation: if cases were checked in lexical order, a busy first case could starve later cases. Random ordering ensures fairness in expectation.
11. Why sorted lockorder (by c pointer)? To avoid deadlock between two concurrent selects with overlapping channels. Without a consistent lock order, one select could hold lock A trying to acquire B while another holds B trying to acquire A.

Acceptance criteria.

• You can explain the two arrays: pollorder (random for fairness) and lockorder (sorted for deadlock avoidance).
• You can answer: "Why are channels unlocked before gopark?" — to allow other goroutines (especially senders/receivers that might unblock this select) to make progress. Holding all the channel locks across the park would serialise the entire system.
• You can answer: "Why does selectgo use fastrand and not a deterministic shuffle?" — fairness in expectation; deterministic shuffling would still allow adversarial scheduling to starve cases under specific traffic patterns.

func selectgo(cas0 *scase, order0 *uint16, ...) (int, bool) {
    cas1 := (*[1 << 16]scase)(unsafe.Pointer(cas0))[:ncases:ncases]
    order1 := (*[1 << 17]uint16)(unsafe.Pointer(order0))[:2*ncases:2*ncases]
    pollorder := order1[:ncases:ncases]
    lockorder := order1[ncases:][:ncases:ncases]

    // 1. Generate random pollorder using Fisher-Yates.
    norder := 0
    for i := range cas1 {
        cas := &cas1[i]
        if cas.c == nil {
            cas.elem = nil
            continue
        }
        j := fastrandn(uint32(norder + 1))
        pollorder[norder] = pollorder[j]
        pollorder[j] = uint16(i)
        norder++
    }
    pollorder = pollorder[:norder]
    lockorder = lockorder[:norder]

    // 2. Sort lockorder by channel pointer (heapsort).
    for i := range lockorder {
        j := i
        c := cas1[pollorder[i]].c
        for j > 0 && cas1[lockorder[(j-1)/2]].c.sortkey() < c.sortkey() {
            k := (j - 1) / 2
            lockorder[j] = lockorder[k]
            j = k
        }
        lockorder[j] = pollorder[i]
    }
    // ... heap pop to finish sort ...

    // 3. Lock all in lockorder.
    sellock(scases, lockorder)

    // 4. First pass: pollorder.
    for _, i := range pollorder {
        cas := &cas1[i]
        c := cas.c
        if casi.kind == caseRecv {
            if sg := c.sendq.dequeue(); sg != nil {
                recv(c, sg, cas.elem, func() { selunlock(scases, lockorder) }, 2)
                return int(i), true
            }
            if c.qcount > 0 {
                // unbuffered impossible if dataqsiz==0 and no senders, so this is buffered
                ...
                selunlock(scases, lockorder)
                return int(i), true
            }
            if c.closed != 0 {
                selunlock(scases, lockorder)
                return int(i), false
            }
        } else {
            // caseSend symmetric.
        }
    }

    // 5. Default?
    if !block {
        selunlock(scases, lockorder)
        return -1, false
    }

    // 6. Enqueue on all channels.
    gp := getg()
    gp.waiting = nil
    nextp := &gp.waiting
    for _, i := range lockorder {
        cas := &cas1[i]
        c := cas.c
        sg := acquireSudog()
        sg.g = gp
        sg.c = c
        sg.elem = cas.elem
        ...
        *nextp = sg
        nextp = &sg.waitlink
        if cas.kind == caseRecv { c.recvq.enqueue(sg) } else { c.sendq.enqueue(sg) }
    }

    // 7. Park.
    gp.param = nil
    gp.signal = ...
    gopark(selparkcommit, nil, waitReasonSelect, traceBlockSelect, 1)
    // selparkcommit's job: unlock all channels, return true.

    // 8. Woken. Find the fired case.
    sg := gp.param.(*sudog)
    casi := -1
    for _, i := range lockorder {
        cas := &cas1[i]
        if sg.c == cas.c { casi = int(i); break }
    }
    // ... cleanup remaining sudogs from other channels ...
    return casi, recvd
}

Task 16 — Read scanstack (S)¶

Goal. Open runtime/mgcmark.go::scanstack and identify how the GC scans a goroutine's stack for pointers.

Starter.

grep -n "^func scanstack" "$(go env GOROOT)/src/runtime/mgcmark.go"

Instructions.

1. Open mgcmark.go::scanstack. Note the preamble: it asserts the goroutine is in a scannable state (_Gwaiting, _Grunnable, or stopped under STW). It cannot scan a running g's stack because the stack is mutating.
2. The function calls scanstackblock for each frame, walking the call stack via gentraceback. For each frame:
3. The frame's PC identifies which function this is.
4. The function's stack map (generated by the compiler) is looked up: it's a bitmap where each bit says "is this 8-byte slot a pointer or not".
5. The scanner walks the bitmap, and for each "pointer" slot reads the value and calls greyobject (mark it reachable, enqueue for further scanning).
6. The stack map mechanism is the key — without it, the GC would have to treat every slot as a possible pointer (conservative GC), which would cause false retention. Go uses precise GC: the compiler tells the GC which slots are pointers.
7. Stack maps are stored in runtime.functab and accessed via funcdata(FUNCDATA_LocalsPointerMaps, ...). The GC looks up the right map at the frame's PC.
8. Special handling:
9. Argument area: scanned via FUNCDATA_ArgsPointerMaps.
10. Spilled register arguments: scanned via FUNCDATA_RegPointerMaps (since Go 1.17 register ABI).
11. Defer records, panic chain, etc., scanned separately by their own functions.
12. Stack growth interaction: when a stack is moved (Go stacks are growable, so morestack can copy the stack to a new larger area), the GC's pointers into the stack would dangle — but the runtime adjusts every stored pointer during move, using the same stack maps. This is one of the things that makes Go's GC and goroutines fast: precise stack maps enable both precise GC and stack copying.

Acceptance criteria.

• You can name the per-function bitmap as the stack map (or pointer map).
• You can name gentraceback as the frame-walker and scanstackblock as the per-frame scanner.
• You can answer: "Why does Go use precise stack maps instead of conservative GC?" — precise GC eliminates false retention (otherwise a small int that happens to look like a heap pointer would prevent collection). Also enables movable stacks: a conservative collector can't move objects because it can't distinguish pointers from non-pointers, but Go moves stacks during growth.
• You can answer: "Can the GC scan a running goroutine?" — no. The goroutine must be stopped (preempted onto a safe point) before its stack is scanned. The preemption mechanism is runtime.preemptone, which signals the goroutine to call runtime.morestack at the next safe point; that funnels through to scheduler hooks that pause the g for scanning.

func scanstack(gp *g, gcw *gcWork) int64 {
    if readgstatus(gp)&^_Gscan == _Grunning {
        throw("scanstack: g is running")
    }
    ...
    // Find the stack bounds.
    var sp, cap uintptr
    sp = gp.sched.sp
    cap = uintptr(gp.stack.hi)
    ...
    // Walk frames from inner to outer.
    var u unwinder
    u.init(gp, 0)
    for ; u.valid(); u.next() {
        scanframeworker(&u.frame, &state, gcw)
    }
    ...
    // Scan defer records, panic chain, etc.
    for d := gp._defer; d != nil; d = d.link {
        if d.fn != nil { scanblock(...) }
        ...
    }
    for p := gp._panic; p != nil; p = p.link {
        ...
    }
    return int64(scanned)
}

func scanframeworker(frame *stkframe, state *stackScanState, gcw *gcWork) {
    f := frame.fn
    ...
    // Locals.
    if locals, args, objs := frame.getStackMap(false); ... {
        scanblock(frame.varp - locals.n*goarch.PtrSize, locals.n*goarch.PtrSize, locals.bytedata, gcw, state)
        scanblock(frame.argp, args.n*goarch.PtrSize, args.bytedata, gcw, state)
    }
    ...
}

type stackmap struct {
    n        int32  // number of bitmaps
    nbit     int32  // number of bits per bitmap
    bytedata [1]byte
}

// runtime/stack.go::copystack:
func copystack(gp *g, newsize uintptr) {
    ...
    // Move pointers in the old stack to point into the new stack.
    var adjinfo adjustinfo
    adjinfo.old = old
    adjinfo.delta = new.hi - old.hi
    ...
    // Walk frames using the same stack maps as scanstack uses.
    gentraceback(...)
    for each frame {
        // Use stack maps to find pointer slots; for each, if it points
        // into the old stack, add adjinfo.delta to retarget into new stack.
    }
    ...
}

Task 17 — Trace a program with go tool trace (S)¶

Goal. Run a tiny program under the runtime tracer, open the trace in a browser, find GoCreate, GoStart, GoBlockSend events, and match each event to its origin in the runtime source.

Starter.

// main.go
package main

import (
    "os"
    "runtime/trace"
)

func main() {
    f, _ := os.Create("trace.out")
    defer f.Close()
    trace.Start(f)
    defer trace.Stop()

    ch := make(chan int)
    go func() { ch <- 42 }()
    <-ch
}

Instructions.

1. Save and run: go run main.go. This produces trace.out.
2. Open the trace: go tool trace trace.out. It starts a local web server and prints a URL; open it in a browser.
3. Navigate the trace UI:
4. The first view is the goroutine analysis overview. Click "View trace" or one of the time-window links.
5. The trace timeline shows Ps as rows, with Goroutines running bars per P.
6. Click into one of the bars to see individual events.
7. Identify three event types:
8. GoCreate: emitted when a new goroutine is created. In your program, that's the go func() { ... }() statement.
9. GoStart: emitted when a goroutine begins running on a P.
10. GoBlockSend: emitted when a goroutine parks on a channel send because no receiver is waiting.
11. For each event, find the runtime source that emits it:
12. GoCreate: emitted by runtime.newproc1 via traceGoCreate(...). Grep: grep -n "traceGoCreate" "$(go env GOROOT)/src/runtime/proc.go".
13. GoStart: emitted by runtime.execute (the function that hands control to a goroutine) via traceGoStart. Grep: grep -n "traceGoStart" "$(go env GOROOT)/src/runtime".
14. GoBlockSend: emitted by runtime.chansend when the sender parks. Look for traceBlockChan references near gopark calls in chan.go.
15. Match the trace to the source: the GoCreate in your trace corresponds to the go func() ... line; the GoBlockSend corresponds to ch <- 42 blocking because main hasn't yet executed <-ch; the GoStart corresponds to the goroutine actually running after main parks on <-ch.

Acceptance criteria.

• trace.out exists and go tool trace opens it in a browser without errors.
• You can identify at least three event types in the trace and name the runtime source location that emits each.
• You can answer: "Why does the runtime tracer have so many event types?" — to enable post-hoc analysis of every scheduler event without re-running the program. The trace is dense (~30 event types) but precise; tools like gotrace and pprof -trace consume it to produce flame graphs, blocking profiles, and STW analyses.

Time     P    Event           G      Stack
0.000ms  0    ProcStart       0
0.001ms  0    GoStart         1      main.main
0.002ms  0    HeapAlloc       1      runtime.makechan
0.003ms  0    GoCreate        2      main.main:13   (creates G2 running main.main.func1)
0.004ms  0    GoStart         2      main.main.func1
0.005ms  0    GoBlockSend     2      main.main.func1:15  (ch <- 42 blocks; G2 parks)
0.006ms  0    GoUnblock       1      runtime.chansend  (receiver wakes sender? — actually here G1 was running, G2 parked, then G1 ran <-ch and unblocked G2)
0.007ms  0    GoStart         2      runtime.gopark  (G2 resumed)
0.008ms  0    GoEnd           2
0.009ms  0    GoEnd           1

if trace.enabled { traceGoCreate(newg, newg.startpc) }

func execute(gp *g, inheritTime bool) {
    ...
    if trace.enabled { traceGoStart() }
    gogo(&gp.sched)
}

// runtime/chan.go::chansend (abridged):
gopark(chanparkcommit, unsafe.Pointer(&c.lock), waitReasonChanSend, traceBlockChan, 2)

Task 18 — Read mcall assembly (Staff)¶

Goal. Open runtime/asm_amd64.s::runtime·mcall and explain the stack switch line by line.

Starter.

grep -n "^TEXT runtime·mcall" "$(go env GOROOT)/src/runtime/asm_amd64.s"

Instructions.

1. Open asm_amd64.s. Locate TEXT runtime·mcall(SB). It's short — ~20 instructions.
2. The function signature in Go: func mcall(fn func(*g)). Calling convention: fn is passed in AX (register ABI since Go 1.17).
3. Read the assembly. The flow is:
4. Save the caller's PC and SP into the calling g's g.sched.
5. Switch SP to g0.sched.sp (the system stack).
6. Set g_register (R14) to point at g0.
7. Call fn(callergp) — the callback runs on g0's stack with the caller's g pointer as argument.
8. The callback typically doesn't return; it calls schedule() or goexit. If it does return (uncommon), control resumes here and we restore.
9. Match each instruction to a step. Annotate:

   MOVQ    fn+0(FP), DI     // save fn pointer
   MOVQ    g_m(R14), BX     // m = g.m
   MOVQ    m_g0(BX), SI     // g0 = m.g0
   CMPQ    SI, R14          // current g == g0?
   JEQ     bad              // panic if so — mcall on g0 makes no sense
   MOVQ    SP, (g_sched+gobuf_sp)(R14)  // save caller's SP into g.sched.sp
   MOVQ    PC, (g_sched+gobuf_pc)(R14)  // save caller's PC
   ...
   MOVQ    SI, R14          // switch g register to g0
   MOVQ    (g_sched+gobuf_sp)(SI), SP   // switch SP to g0's stack
   ...
   CALL    DI               // call fn — runs on g0
   

10. The "switch g" step is the magic: changing R14 changes what getg() returns to subsequent code. The runtime never holds a g pointer in a Go-visible variable; everywhere uses getg() which compiles to a single load from R14.
11. The "switch SP" step is the actual stack swap. Once SP points into g0.stack, the call to DI (the fn argument) operates entirely on g0's stack; the caller's stack is untouched.

Acceptance criteria.

• You can name the register-ABI calling convention: arguments come in AX, BX, CX, DI, SI, R8, R9, R10, R11 (in order, integer types).
• You can name R14 as the dedicated g register on amd64.
• You can explain the three writes that constitute a context switch: save caller's SP and PC into g.sched, switch R14 to g0, load g0.sched.sp into SP.
• You can answer: "Why must mcall panic if called from g0?" — because mcall switches to g0; if you're already on g0, the operation is meaningless and likely a bug.

// func mcall(fn func(*g))
// Switch to m->g0's stack, call fn(g).
// Fn must never return. It should gogo(&g->sched) to continue running g.
TEXT runtime·mcall<ABIInternal>(SB), NOSPLIT, $0-8
    MOVQ    AX, DX          // DX = fn (move from arg register AX to scratch DX)

    // Save state in g->sched. The state in this case is the resume PC and SP
    // for the calling g — when the runtime eventually calls gogo(&g.sched)
    // again, it'll come back here.
    MOVQ    0(SP), BX       // BX = caller's PC (top of stack at function entry)
    MOVQ    BX, (g_sched+gobuf_pc)(R14)  // g.sched.pc = caller's PC
    LEAQ    fn+0(FP), BX    // BX = caller's SP just above this frame
    MOVQ    BX, (g_sched+gobuf_sp)(R14)  // g.sched.sp = that SP
    MOVQ    BP, (g_sched+gobuf_bp)(R14)  // g.sched.bp = frame pointer

    // Switch to m->g0 and its stack, call fn.
    MOVQ    R14, AX         // AX = g (to be passed as fn's argument)
    MOVQ    g_m(R14), BX    // BX = g.m
    MOVQ    m_g0(BX), SI    // SI = m.g0
    CMPQ    SI, R14         // are we already on g0?
    JNE     goodm           // no, proceed
    JMP     runtime·badmcall(SB)  // yes — bug
goodm:
    MOVQ    SI, R14         // g = g0   (switch the g register)
    MOVQ    (g_sched+gobuf_sp)(SI), SP  // SP = g0.sched.sp  (switch stack)

    // We're now on g0. Push the original g as an argument and call fn.
    PUSHQ   AX              // push g (the user goroutine pointer)
    MOVQ    DX, AX          // AX = fn (the ABI register)
    MOVQ    0(DX), DX       // DX = fn's actual code address (funcval indirection)
    CALL    DX
    POPQ    AX

    JMP     runtime·badmcall2(SB)  // fn returned — bug; fn should never return
    RET