Shim Pipeline Specification for the Unheaded Protocol Computer

1.1. Relationship to Other Specifications

The Shim pipeline operates in conjunction with several related specifications in accordance with [RFC8126]:¶

• The Protocol Foundation specification defines the Monad wire format (20-byte fixed header carried in IPv6 Hop-by-Hop options per [RFC8200]), which encodes register state and control flags at each hop¶
• The MBC ISA specification specifies the MBC instruction set architecture (48 opcodes, 16-register architecture, 32-bit words)¶
• The Sophia Dictionary specification defines dictionary lookup semantics used during MBC execution¶
• The Wotan Memory Model specification specifies the BPF map memory model backing the Shim's RAM_MAP and ROM_MAP structures¶

4.1. Input Format

MBC assembly is plain text, one instruction per line. Comments begin with '#' and extend to end of line. Blank lines are ignored. Labels are declared with a trailing colon and must appear alone on a line.¶

  # FizzBuzz example
  MOVI r0, 1        # Initialize r0 = 1

  loop:
  ADDI r0, r0, 1    # Increment r0
  JNE r0, 100, loop # Jump if not equal

  MOV r1, r0        # Move result to r1
  HALT              # Stop execution

4.2. Binary Encoding

The output is a sequence of 32-bit words in little-endian byte order. Each instruction encodes to one word with format:¶

  Bits  31-26  25-20  19-14  13-8   7-2   1-0
  ┌──────────┬──────┬──────┬──────┬────┬──┐
  │ Opcode   │ Dest │ Src1 │ Src2 │Imm │Rsvd│
  │ (6 bits) │(6b)  │(6b)  │(6b)  │(4b)│(2b)│
  └──────────┴──────┴──────┴──────┴────┴──┘

Example encoding of MOVI r0, 42:¶

  Instruction: MOVI r0, 42
  Opcode: 0x0F (MOVI)
  Destination: r0 (0)
  Immediate: 42 (0x2A)

  Binary: 0x0F00002A (little-endian)
  Bytes: 2A 00 00 0F

4.3. Label Resolution

The assembler performs two passes:¶

1. First pass: Record label offsets (word addresses in the program image)¶
2. Second pass: Replace label references in branch instructions with computed offsets¶

Label references are resolved as relative word offsets from the branch instruction's position. A label at word address N referenced from instruction at word address M becomes offset (N - M).¶

5.1. Opcode Whitelist

Only 48 opcodes are valid. The verifier MUST reject any program containing an opcode not in the following list:¶

  Valid opcodes:
  0x00 HALT      0x01 NOP       0x02 MOV       0x03 MOVI
  0x04 ADD       0x05 ADDI      0x06 SUB       0x07 SUBI
  0x08 MUL       0x09 MULI      0x0A DIV       0x0B DIVI
  0x0C MOD       0x0D MODI      0x0E AND       0x0F OR
  0x10 XOR       0x11 NOT       0x12 SHL       0x13 SHR
  0x14 LD        0x15 LDI       0x16 ST        0x17 STI
  0x18 JMP       0x19 JEQ       0x1A JNE       0x1B JLT
  0x1C JGT       0x1D CALL      0x1E RET       0x1F PUSH
  0x20 POP       0x21 PUSHI     0x22 SYSCALL   0x23 LDMAP
  0x24 STMAP     0x25 DICTLOOKUP 0x26 CRC16   0x27 FLAG
  0x28 RFLAG     0x29 RESERVED  0x2A RESERVED  0x2B RESERVED
  0x2C RESERVED  0x2D RESERVED  ...

5.2. Register Range Validation

All register references MUST be in range [0, 15]. The verifier MUST reject programs with register fields containing values greater than 15.¶

5.3. Immediate Value Range Validation

Immediate values occupy 4 bits in the instruction encoding. MOVI and ADDI instructions with immediate values larger than 15 MUST be rejected at verification time. Programs requiring larger immediates MUST use multi-instruction sequences or load from ROM_MAP.¶

5.4. Branch Target Validation

Branch instructions (JMP, JEQ, JNE, JLT, JGT) MUST have target offsets that:¶

• Point to valid instruction boundaries (word-aligned addresses within the program image)¶
• Do not exceed the program image bounds¶
• Do not form backward branches with unbounded depth (prevent infinite loops without instruction limit enforcement)¶

6.1. BPF Map Structures

6.2. Loading Sequence

1. Create all BPF maps in kernel¶
2. Populate ROM_MAP with verified program image¶
3. Initialize CPU_MAP with default CPU state (all registers zero, pc=0, sp=0, flags=0)¶
4. Zero-fill RAM_MAP¶
5. Attach XDP program to network interface¶
6. Enable the program for packet processing¶

7.1. Fetch-Decode-Execute Cycle

  Loop:
  1. Fetch: Read instruction from ROM[pc]
  2. Decode: Parse opcode and operand fields
  3. Execute: Perform operation, update registers/memory
  4. Increment: pc += 1
  5. Check limit: if ticks >= 256 or HALT, exit loop
  6. Else: goto Loop

7.2. Instruction Limit and BPF Verifier Compliance

Each XDP invocation MUST execute at most 256 instructions. This limit:¶

• Prevents CPU exhaustion attacks¶
• Ensures bounded execution time¶
• Complies with BPF verifier's loop detection requirements¶
• Enables predictable per-hop processing latency¶

If an instruction limit is reached without HALT, the program suspends and resumes at the next tick packet. PC and register state persist via CPU_MAP across ticks.¶

7.3. State Persistence

Program state persists across tick packets via BPF maps:¶

• CPU_MAP: PC, registers, flags persist across ticks¶
• RAM_MAP: Memory contents persist across ticks¶
• SCREEN_MAP: Framebuffer contents persist across ticks¶

State is keyed by flow tuple (source IP, destination IP, flow label). Different flows maintain independent execution contexts.¶

8.1. Packet Structure

A tick packet consists of:¶

1. IPv6 Fixed Header (40 bytes)¶
2. Hop-by-Hop Options Header (24 bytes, containing Monad register file)¶
3. Payload (variable, application-specific data)¶

  ┌─────────────────────────────────┐
  │ IPv6 Fixed Header (40 B)        │
  │ • Version (4b)                  │
  │ • Traffic Class (8b)            │
  │ • Flow Label (20b)              │
  │ • Payload Length (16b)          │
  │ • Next Header (8b) = 0 (HbH)    │
  │ • Hop Limit (8b)                │
  │ • Source Address (128b)         │
  │ • Destination Address (128b)    │
  └─────────────────────────────────┘
           │
           ▼
  ┌─────────────────────────────────┐
  │ Hop-by-Hop Options (24 B)       │
  │ • Next Header (8b)              │
  │ • Hdr Ext Len (8b) = 2          │
  │ • Padding (16b)                 │
  │ • Option Type: 0x3E (Monad)     │
  │ • Option Data Len (8b) = 20     │
  │ • Monad Register File (20 B)    │
  │   (per draft-bellis-foundation) │
  └─────────────────────────────────┘
           │
           ▼
  ┌─────────────────────────────────┐
  │ Payload (variable)              │
  │ Application-specific data       │
  └─────────────────────────────────┘

8.2. Processing Pipeline

1. Packet arrives at ingress interface¶
2. XDP program extracts Monad state from HbH option¶
3. Load/initialize CPU_MAP entry from Monad state¶
4. Validate Monad CRC-16/CCITT (MUST reject if invalid)¶
5. Execute MBC program (up to 256 instructions)¶
6. Recompute Monad CRC-16/CCITT¶
7. Write updated Monad state to packet HbH option¶
8. Return XDP_TX (bounce packet to next hop or originating interface)¶

8.3. Tick Rates

Tick packet generation rates vary by operational mode:¶

• LOCAL mode (single-hop loopback): 35 Hz (28 ms between ticks)¶
• DISTRIBUTED mode (multi-hop propagation): ~1 kHz (1 ms between ticks, governed by network propagation)¶

Tick rate is controlled by application logic, not the Shim itself. The Shim simply processes each arriving tick packet up to its 256-instruction limit.¶

9.1. Physical Address Map

  Address Range          Size    Device                  Access
  ─────────────────────────────────────────────────────────────
  0x0000_0000-0x0003_FFFF  256 KB  ROM                     R
  0x0004_0000-0x0006_7FFF  160 KB  Reserved                -
  0x0006_8000-0x0006_8FFF  4 KB    Keyboard (KBD_MAP)      R
  0x0006_9000-0x0006_FFFF  28 KB   Reserved                -
  0x0007_0000-0x0007_FFFF  64 KB   Framebuffer             R/W
  0x0008_0000-0xFFFF_FFFF  4GB -   RAM (RAM_MAP)           R/W

9.2. Keyboard Access (0x0006_8000)

Keyboard state is exposed as an 8-entry array of 32-bit values, where each bit represents one key state (1 = pressed, 0 = released). Total of 256 keys supported.¶

  LD r0, 0x68000    # Load keyboard state word 0
  LDI r1, 1         # Shift amount for key 1 (ESC)
  SHR r0, r0, r1    # Shift right by 1
  AND r0, r0, 1     # Mask for single bit
  # r0 now contains ESC key state (1 if pressed, 0 if not)

9.3. Framebuffer Access (0x0007_0000)

The framebuffer is a 320x200 pixel display with 8-bit palette indices. Pixel (x, y) is stored at byte address 0x70000 + (y * 320) + x.¶

  # Write color 42 to pixel (x=100, y=50)
  MOVI r0, 100      # x coordinate
  MOVI r1, 50       # y coordinate

  # Calculate offset: y * 320 + x
  MULI r2, r1, 320  # r2 = y * 320
  ADD r2, r2, r0    # r2 += x

  # Add base address
  ADDI r2, r2, 0x70000

  # Write color value
  MOVI r3, 42       # Color index
  ST r2, r3         # Store at calculated address

9.4. TTY/Console I/O (0x0007_F000 – 0x0007_FFFF)

Ring buffer for terminal output. Write operations enqueue characters; read operations drain the queue.¶

10.1. Dimensions and Layout

• Width: 320 pixels¶
• Height: 200 scanlines¶
• Color depth: 8-bit palette index (256 colors)¶
• Scanline stride: 320 bytes¶
• Total size: 64 KiB¶

10.2. Pixel Address Calculation

To write a pixel at coordinate (x, y):¶

  address = 0x70000 + (y * 320) + x

Constraints:¶

• 0 ≤ x ≤ 319¶
• 0 ≤ y ≤ 199¶
• Out-of-bounds writes are silently dropped by the BPF verifier¶

10.3. Access Methods

• STB (single-byte write): ST instruction writes one pixel at a time (slowest, most precise)¶
• SYS_DRAW_FRAME (bulk copy): Syscall that copies entire 64 KiB buffer to framebuffer in one operation (fastest, for scene rendering)¶

11.1. Conformance Levels

11.2. Conformance Declaration

Implementations MUST declare which levels they support. A conforming implementation MUST support a contiguous range of levels starting from Level 0. For example:¶

• "Level 0-2": Supports Microcode, Digital, and Mechanical layers¶
• "Level 0-2a": Supports Mechanical plus Memory I/O¶
• "Level 0-4": Supports full multitasking stack¶

An implementation claiming Level N support MUST also support all levels 0 through N-1.¶

12.1. Pre-Execution Validation

When a tick packet arrives, the Shim MUST:¶

1. Extract Monad state from IPv6 HbH option¶
2. Validate CRC-16/CCITT of Monad state¶
3. If CRC is invalid: emit an Anomaly event to COMPUTE_EVENTS map and DO NOT execute MBC¶
4. If CRC is valid: proceed to stage 4 execution¶

This ensures corrupted state never affects program execution.¶

12.2. Post-Execution Recomputation

After MBC execution completes (whether via HALT or 256-instruction limit), the Shim MUST:¶

1. Recompute CRC-16/CCITT of the updated register state¶
2. Write the updated Monad state with new CRC into the outgoing packet's HbH option¶
3. Return XDP_TX to transmit the packet¶

This ensures correct state propagates to the next hop.¶

12.3. Anomaly Event Format

When CRC validation fails, an Anomaly event is written to COMPUTE_EVENTS with structure:¶

• timestamp: 64-bit Unix nanoseconds¶
• event_type: 8-bit code (0x01 = CRC_FAILED)¶
• flow_tuple: Source IP, Dest IP, Flow Label (for correlation)¶
• monad_state: Copy of corrupted Monad state¶
• expected_crc: Expected CRC value¶
• computed_crc: Computed CRC value¶

13.1. Shim Pipeline Stage Registry

Registry Name: Unheaded Shim Pipeline Stages¶

Range: 0-255¶

Initial assignments:¶

• 1: Assembly¶
• 2: Verification¶
• 3: Loading¶
• 4: Execution¶

13.2. BPF Map Type Registry for UPC

Registry Name: Unheaded BPF Map Types¶

Range: 0-255¶

Initial assignments:¶

• 1: ROM_MAP (read-only program image)¶
• 2: RAM_MAP (read-write memory)¶
• 3: CPU_MAP (register state)¶
• 4: SCREEN_MAP (framebuffer)¶
• 5: KBD_MAP (keyboard input)¶
• 6: TTY_MAP (terminal output)¶
• 7: PROC_TABLE (process state)¶
• 8: SCHED_STATE (scheduler state)¶
• 9: TLB_MAP (virtual memory)¶
• 10: COMPUTE_EVENTS (event log)¶

13.3. Dream Ladder Level Registry

Registry Name: Unheaded Dream Ladder Levels¶

Range: 0-7¶

Initial assignments:¶

• 0: Microcode (required)¶
• 1: Digital (required)¶
• 2: Mechanical (required)¶
• 2a: Memory I/O (recommended)¶
• 3: Interrupts and Exceptions (optional)¶
• 4: Scheduling and Multitasking (optional)¶
• 5-7: Reserved for future use¶

14.1. Primary Security Boundary: eBPF Verifier

The eBPF verifier is the primary security boundary. All MBC execution occurs within eBPF context, subject to kernel verification rules following principles established in [RFC9000] for transport reliability:¶

• Memory access must be in-bounds (BPF map bounds enforce this)¶
• Loops must be bounded (256-instruction limit enforces this)¶
• Privilege escalation is not possible (XDP context isolation enforces this)¶

14.2. CPU Exhaustion Prevention

The 256-instruction limit per tick prevents malicious programs from consuming excessive CPU resources. Programs exceeding this limit are suspended and resume at the next tick. Over a period of N ticks, the maximum total instructions executed is 256 * N, providing predictable resource consumption.¶

14.3. Memory Access Control

BPF maps provide bounds checking:¶

• ROM_MAP: Out-of-bounds reads return zero¶
• RAM_MAP: Out-of-bounds writes are silently dropped¶
• SCREEN_MAP: Out-of-bounds pixel writes are silently dropped¶

The kernel enforces all bounds checks; the Shim does not need to replicate this.¶

14.4. Packet Leakage Prevention

All Shim processing returns XDP_TX (bounce packet to sender or next hop). Return codes XDP_DROP and XDP_PASS are never used, preventing accidental packet leakage into the host stack or transmission to unintended recipients.¶

14.5. Tick Packet Injection Trust Model

Any node on the network path can inject tick packets. The Shim does not authenticate the origin of tick packets. This is an architectural assumption: use network ACLs and IPSec if authentication is required. The Shim's responsibility is to:¶

• Validate CRC to detect corruption (but not forgery)¶
• Process only valid, well-formed MBC instructions¶
• Prevent execution of out-of-spec opcodes¶

14.6. Register State Confidentiality

Monad register contents are visible in plaintext at each hop (in the IPv6 HbH option). There is no confidentiality for register state. If confidentiality is required, apply TLS or IPSec encryption at a layer above the Shim.¶

14.7. Verification as a Security Gate

The Verification stage MUST reject programs with:¶

• Invalid opcodes (prevents execution of undefined instructions)¶
• Out-of-range registers (prevents register field corruption)¶
• Out-of-range immediates (prevents encoding errors)¶
• Invalid branch targets (prevents control flow attacks)¶

Programs that fail verification MUST NEVER be loaded. No exceptions.¶