The question this layer answers
How does a processor execute one instruction after another?
The machine’s vocabulary. This layer connects Assembly, Calling conventions, Pipelines, Binaries to the rest of the computing stack.
Execution is a sequence of explicit states
Source code hides bookkeeping. To understand execution, expose a machine state: the program counter PC, registers, memory, and any relevant flags. An instruction reads some state, computes a result, and defines the next state. Modern processors overlap work internally, but the instruction-set contract still constrains observable results.
Consider a toy machine with unbounded nonnegative integer registers. JZ R, label branches when R is zero; JMP always branches. This model deliberately avoids machine-specific encodings and overflow so we can study control flow first.
R0 = n
R1 = 0
loop:
JZ R0, done
R1 = R1 + R0
R0 = R0 - 1
JMP loop
done:
HALT
For n = 3, the state at loop changes as follows:
| Visit | R0 | R1 | Next action |
|---|
| 1 | 3 | 0 | Add 3 |
| 2 | 2 | 3 | Add 2 |
| 3 | 1 | 5 | Add 1 |
| 4 | 0 | 6 | Branch to done |
Checking zero before subtracting makes n = 0 terminate immediately. Moving the check after a decrement changes that boundary case. In fixed-width unsigned arithmetic, decrementing zero wraps to the largest representable value; in our unbounded signed alternative it becomes negative. Either change invalidates the simple termination argument unless the program is revised.
Calls need a place to return
A function call must preserve a return location and any state the calling convention requires. Recursion means multiple invocations of the same function can be unfinished simultaneously. Each invocation needs its own arguments, locals, and return information. A stack frame is a common organization for that information; it is not a property of every possible language implementation.
For factorial(3), calls descend through factorial(2) and factorial(1). Results return in reverse order. The pending multiplication by 3 belongs to a different invocation from the pending multiplication by 2. Sharing one slot for both would destroy information needed on return.
A program file is not a running process
Compiling translates source into lower-level representations. Linking resolves references among object files and libraries. Loading maps the executable and required runtime state into a process. These are distinct jobs, even when a tool hides them behind one command. An undefined symbol is usually a different class of failure from an invalid memory access during execution.
Practice habit: record PC as well as values when tracing. For each branch, say which condition was read and which instruction executes next. Then test the smallest allowed input before the typical one. The lab makes this habit concrete without requiring assembly tooling.
Free Machine code & execution lessons
Registers, addresses, and control flow
An instruction decodes into an operation over registers, immediates, memory, flags, and the program counter. Loads and stores move data across the register–memory boundary. Branches choose the next instruction according to values or flags. The ISA defines the result even when the processor overlaps many instructions internally.
An instruction such as load r0, [base + index×4] first computes an effective address. It then requests bytes from that address and interprets their width and signedness. Confusing the address with the stored value is the classic pointer mistake in another costume.
Calling conventions and stack frames
A calling convention assigns argument and return locations, classifies caller- and callee-saved registers, defines stack alignment, and specifies how control returns. A stack frame may hold saved state, local storage, spilled registers, and metadata. The compiler may omit or reshape it when the observable contract still holds.
A call records where execution should resume, often in a register or on the stack. Corrupting it can redirect control, which is why stack bounds, non-executable memory, address randomization, control-flow protections, and memory-safe languages matter. A software convention becomes a security boundary when data controls execution.
Symbols, relocation, linking, and loading
An object file contains machine code and data plus symbols, sections, and relocation records. A linker resolves cross-file references and lays out an executable or shared object. A loader maps segments, establishes process state, and performs required dynamic resolution before transferring control to an entry point.
Static linking copies selected library code into the executable, increasing independence and size. Dynamic linking resolves shared libraries at load or run time, enabling sharing and updates but adding deployment and compatibility dependencies. Neither is universally superior; the product’s update, footprint, security, and portability needs decide.
Pipelines, hazards, prediction, and precise state
Fetch, decode, execute, memory, and retirement can operate on different instructions simultaneously. Data hazards arise from dependencies; control hazards arise before a branch outcome is known; structural hazards compete for hardware. Forwarding, stalling, prediction, and speculation recover throughput while retirement preserves defined order and exceptions.
The processor predicts a path and executes ahead. If the guess is wrong, younger speculative instructions are discarded and fetching restarts at the correct target. The architectural state must look as if only the correct path executed, though microarchitectural traces can still matter for timing and security.
Trace arguments, saved registers, local storage, and return addresses.
Decode endianness and alignment without confusing them with pointer validity.
Follow definitions, references, and address-dependent fields through linking.
Trace traps, system calls, interrupt state, and resumption.
Practice lab: Execute a program by hand
About 30 minutes. Know variables, loops, and state from the Core study guide. This is a teaching ISA, not assembly for a real processor.
Registers r0 and r1 hold integers. Instructions: 0: SET r0, 3; 1: SET r1, 0; 2: ADD r1, r0; 3: SUB r0, 1; 4: JNZ r0, 2; 5: HALT. ADD adds into its first register; SUB subtracts from it. JNZ jumps if the register is nonzero. Otherwise execution advances by one.
- Create a table of (program counter, r0, r1) after each instruction.
- State the final r1 and the number of ADD executions. Explain why the loop terminates for this initial state.
- Replace the initial 3 with 0. Find the defect and propose a pre-loop guard. Assume unbounded mathematical integers for this part.
Hint
The loop checks r0 after subtracting. Starting at zero is not the same as running zero iterations.
Worked solution
After SETs, (PC,r0,r1) = (2,3,0). The loop boundaries are (2,2,3), (2,1,5), then (5,0,6). Three ADDs produce 6, the sum 3 + 2 + 1. For a positive initial value, r0 decreases toward zero. Starting at zero executes ADD once and SUB changes r0 to −1; it then decreases forever under the unbounded-integer model. Add a zero check before the first ADD, and either reject negative inputs or define a separate policy. Real fixed-width arithmetic wraps or traps according to its ISA, so the unbounded trace must not be silently applied to real hardware.
- Track control flow as well as register values.
- Explain termination with a decreasing nonnegative measure.
- Find the zero-input bug and state the numeric model.
Change one assumption
Change ADD r1, r0 to ADD r1, 1. Predict the new final value for input 3 before tracing it.
Trace the contracts beneath source code
Use explicitly defined toy machines and interfaces. Distinguish a rule of this exercise from a guarantee supplied by a real instruction set, ABI, executable format, or operating system.
1. Execution trace · allow 35 minutes
An instruction trace that exposes two independent bugs
A toy machine has 8-bit unsigned registers, wrapping addition, and byte memory M[0]=5,M[1]=250,M[2]=10. All other addresses are unmapped. A program initializes i=0,s=0, then while i<3 executes s=(s+M[i]) mod 256 and i=i+1. Trace every loop-head state and the final result.
A programmer claims the result is the mathematical sum. Another changes the condition to i≤3 to “include the last byte.” Diagnose both claims separately. State the register width or overflow policy needed for the mathematical sum and what the off-by-one version does at its final iteration.
Get a starting hint
The representation contract and the address-bound contract are independent. Write the byte indices before reasoning about the loop bound.
Compare your reasoning with the worked solution
Loop-head states (i,s) are(0,0),(1,5),(2,255),(3,9). The mathematical sum is 265, but 8-bit modular arithmetic retains 265 mod 256=9. The loop is correct for its wrapping-sum contract and incorrect for an unbounded-sum contract. A 9-bit unsigned accumulator can represent this particular sum; a general n-byte sum needs a range that covers 255n or an explicit checked/bignum policy.
The condition i≤3 admits a fourth iteration and attempts M[3], which is unmapped. The byte indices 0,1,2 already cover all three elements. Under a machine that faults before completing that load, the iteration cannot update s or i, so the last successful state remains(3,9). Any precise statement about fault state must use the machine's exception contract.
Changing the loop condition cannot repair arithmetic overflow, and widening the accumulator cannot repair the invalid address. Tests should separately cover zero-length input, exact range boundaries, overflow, and unmapped access.
Check your reasoning
- Track values modulo 256 at every update.
- Separate an arithmetic-contract error from an address-bound error.
- State the width needed for a general input bound.
2. Calling-convention design · allow 40 minutes
Keep a caller alive through a nested call
A toy ABI has argument/return register r0, caller-saved r1..r3, callee-saved r4..r5, a return-address register ra, and a downward-growing stack aligned to 16 bytes at every call. Function F must keep a value in r4, call G, then use that value and return. G may overwrite r0..r3 and ra.
Design F's prologue, call sequence, and epilogue using a 32-byte frame starting from SP=0x1000. Use 8-byte save slots for this exercise. Explain why F must preserve the incoming r4 even if G follows the ABI, and why a leaf function may have a different frame. Show the failure if F saves only r4 but not ra.
Get a starting hint
F is both a callee of its own caller and a caller of G. Those two roles impose different preservation duties.
Compare your reasoning with the worked solution
F subtracts 32 from SP, obtaining 0x0FE0, still 16-byte aligned. It saves incoming r4 at a designated 8-byte slot such as SP+16 and incoming ra at SP+24. It then puts its own long-lived value in r4, prepares r0, and calls G. G must restore r4 if it uses it, so F's value survives the nested call. F uses the returned r0 as needed, restores incoming r4 and ra, adds 32 to SP, and returns through restored ra.
Preserving r4 for G's caller does not release F from preserving the earlier value belonging to F's caller. Saving only r4 leaves ra containing the address after F's call to G. Returning through it can re-enter F's post-call code instead of returning to F's caller.
A leaf function makes no nested call, so it may avoid saving ra and may need no stack frame if its register and local-storage requirements permit. These offsets and register names define a toy ABI; real ABIs differ in reserved registers, stack layouts, red zones, unwind data, and return conventions.
Check your reasoning
- Account for both caller and callee obligations.
- Preserve stack alignment and restore the original SP.
- Explain the nested-call return-address failure with control flow.
3. Representation and alignment · allow 35 minutes
Decode bytes without assuming a packed structure
A toy C-like ABI gives an 8-bit flag alignment 1, a 32-bit count alignment 4, and a 16-bit code alignment 2. Structure fields appear in that order; the structure alignment is the largest field alignment, and total size is rounded up to it. Find offsets, internal padding, trailing padding, and total size.
With flag=1,count=0x12345678,code=0x9ABC on a little-endian machine, show defined bytes at each field offset. Mark padding as unspecified. Compare a packed 7-byte wire format and explain why copying raw structure memory is a poor portable serialization contract.
Get a starting hint
Advance each field to its own alignment boundary, then round the total size to the structure alignment.
Compare your reasoning with the worked solution
flag occupies offset 0. count begins at 4 after three padding bytes and occupies 4..7. code begins at 8 and occupies 8..9. The end at 10 is rounded to 12, adding two trailing padding bytes. Structure alignment is 4 and total size 12.
Defined bytes are offset 0:01; offsets 4..7:78 56 34 12; offsets 8..9:BC 9A. Offsets 1..3 and 10..11 are padding whose contents were not specified. A packed wire format can use offsets 0,1,5 and total size 7, but must explicitly define endianness and each field's meaning.
Raw memory can contain padding, implementation-dependent layout, host byte order, and potentially stale data in unused bytes. A receiver may also have stricter alignment rules than the sender. Serialize fields deliberately into bytes, validate ranges and length when decoding, and avoid treating a byte buffer as a naturally aligned host object without checking the language and platform rules.
Check your reasoning
- Include both internal and trailing padding.
- Mark unspecified bytes rather than invent their values.
- Define a wire format independently of host object layout.
4. Linking calculation · allow 35 minutes
Resolve a relative reference at the correct base
A toy 4-byte instruction at address 0x1000 has a signed 12-bit byte displacement measured from the next instruction address. Its target is 0x1200. Calculate the relocation value and check that it fits.
The loader moves both instruction and target upward by 0x4000. Recalculate the relative displacement and an absolute-address relocation. Then move only the target to 0x2000 and decide whether the relative field still fits. Explain how using the instruction's own address instead of the next address creates a systematic error.
Get a starting hint
Write target−base with the exact base specified by the instruction format. Signed 12-bit range is−2048 through 2047.
Compare your reasoning with the worked solution
The next instruction is 0x1004, so displacement 0x1200−0x1004=0x1FC=508 bytes, within range. After moving both locations, the addresses are 0x5000 and 0x5200; displacement remains 0x5200−0x5004=508. An absolute target field would instead change from 0x1200 to 0x5200.
If only the target moves to 0x2000, displacement is 0xFFC=4092, outside the signed 12-bit range. Truncating the bits would encode a different displacement and silently misdirect execution. A linker needs a supported longer sequence, a suitable intermediate stub, or a diagnostic; the exact repair depends on the real ISA and relocation type.
Subtracting 0x1000 produces 512, four bytes too large for this defined next-address-relative instruction. Executing that encoded displacement from 0x1004 would reach 0x1204. Real instruction sets can use different bases, scaling, and bit layouts, so “PC-relative” by itself is not enough to compute a relocation.
Check your reasoning
- Use the specified next-instruction base.
- Check signed range before encoding.
- Separate a shared load bias from moving only one symbol.
5. Precise-state reasoning · allow 40 minutes
Define what survives a fault
A processor executes three instructions in program order: I1 adds 1 to r1; I2 loads r2 from an unmapped address; I3 stores r3 to memory location A. It may execute speculatively but promises precise exceptions. Starting with r1=4,r2=8,A=0,r3=9, state the architectural state when I2 faults.
Explain which speculative results must not become architectural state. Now consider an operating-system service receiving a user pointer and length. Explain why entering privileged mode does not make those values trustworthy, and describe validation, bounded copying, and failure reporting for a deliberately all-or-error toy service.
Get a starting hint
A precise exception makes completed older instructions visible and prevents the faulting and younger instructions from appearing completed.
Compare your reasoning with the worked solution
At the precise exception, r1=5 because I1 precedes the fault. r2 remains 8 because I2 did not complete, and A remains 0 because I3 is younger. The saved fault location identifies I2 so the system can apply its defined fault policy. A speculative arithmetic value or store must be withheld or discarded if exposing it would violate this ordered architectural state. Microarchitectural effects such as cache changes are a separate issue and can matter for security even when architectural state is precise.
A privileged service still receives values chosen by an unprivileged caller. It must check length and arithmetic overflow, enforce permitted address ranges through safe access mechanisms, and avoid treating user memory as permanently stable after one check. A bounded copy into owned storage gives the service a private buffer that user writes cannot change afterward. It does not by itself provide an atomic snapshot of concurrently changing user memory: the copy may combine values from different moments. Validate the copied representation and use an explicit synchronization or versioning protocol when cross-field consistency is required.
For the toy all-or-error contract, validate/copy the complete bounded request before committing any external effect, and return a specified error on invalid access. Real system calls can allow partial results; their documented contracts, not this classroom policy, determine the correct behavior.
Check your reasoning
- Separate older, faulting, and younger architectural effects.
- Avoid equating precise exceptions with absence of side channels.
- Treat privilege and input validity as independent properties.
Study the underlying methods
Section project: Write an assembler and traceable machine interpreter
6 to 8 hours. Define and implement a tiny instruction machine with eight unsigned 16-bit registers, 256 bytes of data memory, a program counter measured in instructions, and separate instruction storage. Support immediate loads, register addition, byte loads, byte stores, conditional jumps, and halt. Specify operand order, zero-extension for loads, low-byte truncation for stores, and arithmetic wraparound modulo 65536. Assembly input is text with labels and comments; output is a resolved instruction list and an execution trace containing the old PC, instruction, changed registers, memory effects, and next PC. Use a two-pass assembler so forward label references work. Invalid addresses or instructions must produce a structured trap before any effect of the failing instruction. A configurable instruction budget prevents an accidental loop from hanging the tool; exhausting it is a resource stop, not proof of nontermination. Write small programs for a counted sum and copying a byte range. The project makes source translation, machine state, and control flow concrete without pretending to implement a commercial instruction set. Include one annotated trace with a taken jump and one with an untaken jump. Explain why an instruction address and a data-memory address belong to different spaces in this machine model.
Milestones
- Publish an instruction reference and precise initial-state and trap rules.
- Build label collection and instruction resolution as separate assembler passes.
- Implement one-step execution and a bounded run loop with trace output.
- Write and hand-trace counted-sum and byte-copy programs.
- Test malformed assembly, arithmetic boundaries, and machine traps.
Acceptance criteria
- A program summing integers one through five halts with result 15 in its declared result register.
- Adding one to register value 65535 yields zero, with all other registers unchanged unless specified by the instruction.
- A forward label jump lands on the same instruction index shown in the assembler listing.
- A store writes only the low eight bits, and a later load returns that byte zero-extended.
- An invalid memory access leaves registers and memory unchanged for that instruction and reports its PC.
- An intentional infinite loop stops at the configured budget with a distinct budget-exhausted result.
Add a documented call/return convention and stack pointer, then implement one nested function call and show exactly which values the caller and callee preserve.
Practise Machine code & execution free →