exec.gno

  1// Package riscv is an RV32IM emulator for gno.land: 48 instructions that every
  2// real compiler already targets.
  3//
  4// A guest here is not written in a new language. `rustc --target
  5// riscv32im-unknown-none-elf`, `clang -target riscv32`, TinyGo and Zig all emit
  6// it, so a program arrives compiled by the real compiler and optimized by the
  7// real optimizer. The interpreter is a decode loop rather than a semantic
  8// minefield: fetch four bytes, switch on seven bits, do arithmetic.
  9//
 10// No F or D. No floats means no rounding-mode ambiguity and nothing that can
 11// differ between nodes. The M extension's divide-by-zero and overflow cases are
 12// defined by the spec to RETURN a value rather than trap, which is exactly what
 13// a deterministic chain wants.
 14//
 15// It implements [vmkit.Machine], so it shares the fuel meter, the snapshot
 16// codec and the instance store with [p/moul/x/vm/bf](/p/moul/x/vm/bf/v0). That
 17// sharing is the point: the second guest is what tells you whether the ABI was
 18// shaped around the first one.
 19//
 20// Live demo: [r/moul/x/vm/riscvdemo](/r/moul/x/vm/riscvdemo/v0).
 21package riscv
 22
 23import (
 24	"errors"
 25
 26	"gno.land/p/moul/x/vm/vmkit/v0"
 27)
 28
 29// VMName is the identifier this machine registers under in a vmkit.Instance.
 30const VMName = "riscv32im"
 31
 32// DefaultEntry is where a flat text image is conventionally loaded and where
 33// execution starts. Low enough to leave a scratch page below it, aligned, and
 34// nothing about the machine requires it: NewMachine takes the entry point.
 35const DefaultEntry uint32 = 0x1000
 36
 37const (
 38	snapMagic uint32 = 0x52563332 // "RV32"
 39
 40	// snapVersion 2 carries the text segment's extent, which version 1 did
 41	// not need because the interpreter decoded from memory on every fetch.
 42	// Predecoding moved that work to load time, so a restored hart has to be
 43	// told which part of its memory is code.
 44	snapVersion byte = 2
 45)
 46
 47// ErrNoProgram is returned when a Machine is stepped with no image loaded.
 48var ErrNoProgram = errors.New("riscv: machine has no program")
 49
 50// Machine is an RV32IM hart, mid-execution.
 51type Machine struct {
 52	reg [32]uint32
 53	pc  uint32
 54	mem *Memory
 55
 56	// code is the text segment with its fields already pulled apart. See
 57	// predecode.gno for why the dispatch loop reads arrays and not memory.
 58	code *code
 59
 60	status vmkit.Status
 61	trap   string
 62
 63	// out is what the guest wrote through the write syscall, mirrored to the
 64	// host as it goes. Kept here too so a snapshot round-trips it.
 65	outLen int
 66}
 67
 68// NewMachine returns a hart with the image loaded at entry, pc at entry, and
 69// the stack pointer at the top of memory.
 70func NewMachine(image []byte, entry uint32) (*Machine, error) {
 71	if entry%4 != 0 {
 72		return nil, errors.New("riscv: entry point is not 4-byte aligned")
 73	}
 74	if len(image)%4 != 0 {
 75		return nil, errors.New("riscv: image length is not a whole number of instructions")
 76	}
 77	m := &Machine{mem: NewMemory(), pc: entry, status: vmkit.Running}
 78	if !m.mem.WriteImage(entry, image) {
 79		return nil, errors.New("riscv: image does not fit at the entry point")
 80	}
 81	m.code = predecode(entry, image)
 82	// x2 is sp by convention. A guest that never touches the stack does not
 83	// care; one compiled by rustc does, immediately.
 84	m.reg[2] = MemSize
 85	return m, nil
 86}
 87
 88// LoadData places initialized data in memory, outside the text segment.
 89//
 90// The other half of a flat-image loader. A program with a .data section needs
 91// its initial bytes in memory and needs to write them back afterwards, which
 92// the text segment forbids: W xor X is what makes the predecode sound. So the
 93// linker puts data at its own address and it arrives here separately, rather
 94// than being concatenated onto the code and silently becoming read-only.
 95//
 96// The pages are marked dirty, so a snapshot carries the data the same way it
 97// carries the program.
 98func (m *Machine) LoadData(addr uint32, b []byte) error {
 99	if m.mem == nil {
100		return ErrNoProgram
101	}
102	if len(b) > 0 && m.code != nil && m.code.words > 0 {
103		lo, hi := uint64(addr), uint64(addr)+uint64(len(b))
104		if lo < uint64(m.code.end) && hi > uint64(m.code.base) {
105			return errors.New("riscv: data segment overlaps the text segment")
106		}
107	}
108	if !m.mem.WriteImage(addr, b) {
109		return errors.New("riscv: data does not fit at that address")
110	}
111	return nil
112}
113
114// Registers returns a copy of the register file, for tests and rendering.
115func (m *Machine) Registers() [32]uint32 { return m.reg }
116
117// PC returns the program counter.
118func (m *Machine) PC() uint32 { return m.pc }
119
120// Memory returns the address space.
121func (m *Machine) Memory() *Memory { return m.mem }
122
123// Status returns the machine's status.
124func (m *Machine) Status() vmkit.Status { return m.status }
125
126// Trap returns why the machine trapped, making Machine a [vmkit.Trapper].
127func (m *Machine) Trap() string { return m.trap }
128
129// Step runs until the program halts, traps, or spends `fuel` instructions.
130//
131// Written the way the bf ladder concluded, and for the same measured reasons:
132// the hot state is in locals and written back once, and the fuel counter is two
133// locals rather than a vmkit.Meter, because calling a method per instruction
134// cost 86% there and would cost more here, where an instruction is cheaper.
135//
136// Two things in this loop look like premature optimization and are not, both
137// measured in switchcost_test.gno on this VM:
138//
139//   - The case order is the internal opcode order from predecode.gno, which is
140//     by dynamic frequency, because the GnoVM scans switch cases in source
141//     order at 278 gas each. Reordering the arms below changes what the
142//     interpreter costs.
143//   - Everything the loop touches is a local. Reading cop[i] through m.code.op
144//     instead would pay for two field lookups on every instruction.
145func (m *Machine) Step(h vmkit.Host, fuel int64) (int64, vmkit.Status) {
146	if m.mem == nil || m.code == nil {
147		m.status, m.trap = vmkit.Trapped, "no program"
148		return 0, m.status
149	}
150	if m.status != vmkit.Running {
151		return 0, m.status
152	}
153
154	pc := m.pc
155	// A misaligned pc would index the word containing it rather than trap,
156	// because the index is a shift. Only a restored snapshot can get here with
157	// one, since JALR is the only instruction that can produce it and it
158	// checks its own target.
159	if pc%4 != 0 {
160		m.status, m.trap = vmkit.Trapped, "misaligned program counter"
161		return 0, m.status
162	}
163
164	reg := &m.reg
165	mem := m.mem
166
167	c := m.code
168	cop, crd, crs1, crs2, cimm := c.op, c.rd, c.rs1, c.rs2, c.imm
169	cbase, cwords, cend := c.base, c.words, c.end
170	defer func() { m.pc = pc }()
171
172	budget := fuel
173	if budget < 0 {
174		budget = vmkit.Unmetered
175	}
176	metered := budget != vmkit.Unmetered
177	var used int64
178
179	for {
180		if metered && used >= budget {
181			return used, vmkit.Running
182		}
183		used++
184
185		// One subtraction and one shift replace the fetch. A pc below the text
186		// segment underflows to a huge index and is caught by the same
187		// comparison, which is why there is no second bound here.
188		i := (pc - cbase) >> 2
189		if i >= cwords {
190			m.status, m.trap = vmkit.Trapped, "instruction fetch out of range"
191			return used, m.status
192		}
193		next := pc + 4
194
195		switch cop[i] {
196		case iADDI:
197			reg[crd[i]] = reg[crs1[i]] + cimm[i]
198		case iLW:
199			v, ok := mem.Load32(reg[crs1[i]] + cimm[i])
200			if !ok {
201				m.status, m.trap = vmkit.Trapped, "load out of range"
202				return used, m.status
203			}
204			reg[crd[i]] = v
205		case iSW:
206			addr := reg[crs1[i]] + cimm[i]
207			if addr < cend && addr+4 > cbase {
208				m.status, m.trap = vmkit.Trapped, "store into text segment"
209				return used, m.status
210			}
211			if !mem.Store32(addr, reg[crs2[i]]) {
212				m.status, m.trap = vmkit.Trapped, "store out of range"
213				return used, m.status
214			}
215		case iADD:
216			reg[crd[i]] = reg[crs1[i]] + reg[crs2[i]]
217		case iBNE:
218			if reg[crs1[i]] != reg[crs2[i]] {
219				next = pc + cimm[i]
220			}
221		case iBEQ:
222			if reg[crs1[i]] == reg[crs2[i]] {
223				next = pc + cimm[i]
224			}
225		case iJAL:
226			reg[crd[i]] = next
227			next = pc + cimm[i]
228		case iJALR:
229			// The target is computed before rd is written, because rd and rs1
230			// are allowed to be the same register and usually are: `ret` is
231			// jalr x0, 0(x1).
232			t := (reg[crs1[i]] + cimm[i]) &^ 1
233			if t%4 != 0 {
234				m.status, m.trap = vmkit.Trapped, "misaligned jump target"
235				return used, m.status
236			}
237			reg[crd[i]] = next
238			next = t
239		case iLUI:
240			reg[crd[i]] = cimm[i]
241		case iSLLI:
242			reg[crd[i]] = reg[crs1[i]] << (cimm[i] & 0x1F)
243		case iSRLI:
244			reg[crd[i]] = reg[crs1[i]] >> (cimm[i] & 0x1F)
245		case iANDI:
246			reg[crd[i]] = reg[crs1[i]] & cimm[i]
247		case iSUB:
248			reg[crd[i]] = reg[crs1[i]] - reg[crs2[i]]
249		case iORI:
250			reg[crd[i]] = reg[crs1[i]] | cimm[i]
251		case iXORI:
252			reg[crd[i]] = reg[crs1[i]] ^ cimm[i]
253		case iBLT:
254			if int32(reg[crs1[i]]) < int32(reg[crs2[i]]) {
255				next = pc + cimm[i]
256			}
257		case iBGE:
258			if int32(reg[crs1[i]]) >= int32(reg[crs2[i]]) {
259				next = pc + cimm[i]
260			}
261		case iBLTU:
262			if reg[crs1[i]] < reg[crs2[i]] {
263				next = pc + cimm[i]
264			}
265		case iBGEU:
266			if reg[crs1[i]] >= reg[crs2[i]] {
267				next = pc + cimm[i]
268			}
269		case iSRAI:
270			reg[crd[i]] = uint32(int32(reg[crs1[i]]) >> (cimm[i] & 0x1F))
271		case iSLL:
272			reg[crd[i]] = reg[crs1[i]] << (reg[crs2[i]] & 0x1F)
273		case iSRL:
274			reg[crd[i]] = reg[crs1[i]] >> (reg[crs2[i]] & 0x1F)
275		case iSRA:
276			reg[crd[i]] = uint32(int32(reg[crs1[i]]) >> (reg[crs2[i]] & 0x1F))
277		case iAND:
278			reg[crd[i]] = reg[crs1[i]] & reg[crs2[i]]
279		case iOR:
280			reg[crd[i]] = reg[crs1[i]] | reg[crs2[i]]
281		case iXOR:
282			reg[crd[i]] = reg[crs1[i]] ^ reg[crs2[i]]
283		case iLBU:
284			v, ok := mem.Load8(reg[crs1[i]] + cimm[i])
285			if !ok {
286				m.status, m.trap = vmkit.Trapped, "load out of range"
287				return used, m.status
288			}
289			reg[crd[i]] = uint32(v)
290		case iLB:
291			v, ok := mem.Load8(reg[crs1[i]] + cimm[i])
292			if !ok {
293				m.status, m.trap = vmkit.Trapped, "load out of range"
294				return used, m.status
295			}
296			reg[crd[i]] = uint32(int32(int8(v)))
297		case iLH:
298			v, ok := mem.Load16(reg[crs1[i]] + cimm[i])
299			if !ok {
300				m.status, m.trap = vmkit.Trapped, "load out of range"
301				return used, m.status
302			}
303			reg[crd[i]] = uint32(int32(int16(v)))
304		case iLHU:
305			v, ok := mem.Load16(reg[crs1[i]] + cimm[i])
306			if !ok {
307				m.status, m.trap = vmkit.Trapped, "load out of range"
308				return used, m.status
309			}
310			reg[crd[i]] = uint32(v)
311		case iSB:
312			addr := reg[crs1[i]] + cimm[i]
313			if addr < cend && addr+4 > cbase {
314				m.status, m.trap = vmkit.Trapped, "store into text segment"
315				return used, m.status
316			}
317			if !mem.Store8(addr, uint8(reg[crs2[i]])) {
318				m.status, m.trap = vmkit.Trapped, "store out of range"
319				return used, m.status
320			}
321		case iSH:
322			addr := reg[crs1[i]] + cimm[i]
323			if addr < cend && addr+4 > cbase {
324				m.status, m.trap = vmkit.Trapped, "store into text segment"
325				return used, m.status
326			}
327			if !mem.Store16(addr, uint16(reg[crs2[i]])) {
328				m.status, m.trap = vmkit.Trapped, "store out of range"
329				return used, m.status
330			}
331		case iAUIPC:
332			reg[crd[i]] = pc + cimm[i]
333		case iSLT:
334			reg[crd[i]] = b2u(int32(reg[crs1[i]]) < int32(reg[crs2[i]]))
335		case iSLTU:
336			reg[crd[i]] = b2u(reg[crs1[i]] < reg[crs2[i]])
337		case iSLTI:
338			reg[crd[i]] = b2u(int32(reg[crs1[i]]) < int32(cimm[i]))
339		case iSLTIU:
340			reg[crd[i]] = b2u(reg[crs1[i]] < cimm[i])
341		case iMUL:
342			reg[crd[i]] = reg[crs1[i]] * reg[crs2[i]]
343		case iMULH:
344			reg[crd[i]] = uint32((int64(int32(reg[crs1[i]])) * int64(int32(reg[crs2[i]]))) >> 32)
345		case iMULHSU:
346			reg[crd[i]] = uint32((int64(int32(reg[crs1[i]])) * int64(uint64(reg[crs2[i]]))) >> 32)
347		case iMULHU:
348			reg[crd[i]] = uint32((uint64(reg[crs1[i]]) * uint64(reg[crs2[i]])) >> 32)
349		case iDIV:
350			// The M extension defines divide by zero and the one signed
351			// overflow case to RETURN a value rather than trap. That is what
352			// makes it safe on a chain: there is no host arithmetic exception
353			// to differ between nodes.
354			reg[crd[i]] = divS(int32(reg[crs1[i]]), int32(reg[crs2[i]]))
355		case iDIVU:
356			if reg[crs2[i]] == 0 {
357				reg[crd[i]] = ^uint32(0)
358			} else {
359				reg[crd[i]] = reg[crs1[i]] / reg[crs2[i]]
360			}
361		case iREM:
362			reg[crd[i]] = remS(int32(reg[crs1[i]]), int32(reg[crs2[i]]))
363		case iREMU:
364			if reg[crs2[i]] == 0 {
365				reg[crd[i]] = reg[crs1[i]]
366			} else {
367				reg[crd[i]] = reg[crs1[i]] % reg[crs2[i]]
368			}
369		case iECALL:
370			st, halt := m.ecall(h)
371			if halt {
372				// pc advances past the ecall before returning, so a halted
373				// hart points at what it would run next rather than at the
374				// syscall it already made. The deferred write-back is the only
375				// thing that sets m.pc, so assigning the local is how this is
376				// said.
377				m.status = st
378				pc = next
379				return used, m.status
380			}
381		case iEBREAK:
382			m.status, m.trap = vmkit.Trapped, "ebreak"
383			pc = next
384			return used, m.status
385		case iFENCE:
386			// FENCE orders memory for a hart that has neighbours. There is
387			// exactly one here, so it is architecturally a no-op rather than
388			// an unimplemented instruction.
389		default:
390			m.status, m.trap = vmkit.Trapped, "illegal instruction"
391			return used, m.status
392		}
393
394		// x0 is hardwired to zero. Writing it is legal and discarded, and
395		// clearing after the fact is cheaper than branching on rd in every
396		// arm above.
397		reg[0] = 0
398		pc = next
399	}
400}
401
402// b2u is the spec's "set if" result: 1 or 0, never a Go bool.
403func b2u(b bool) uint32 {
404	if b {
405		return 1
406	}
407	return 0
408}
409
410// divS is DIV with the two cases the spec pins down: division by zero yields
411// all ones, and the most negative value divided by -1 overflows to itself.
412func divS(a, b int32) uint32 {
413	if b == 0 {
414		return ^uint32(0)
415	}
416	if a == -2147483648 && b == -1 {
417		return uint32(a)
418	}
419	return uint32(a / b)
420}
421
422// remS is REM, with the matching pair: remainder by zero is the dividend, and
423// the overflow case is zero.
424func remS(a, b int32) uint32 {
425	if b == 0 {
426		return uint32(a)
427	}
428	if a == -2147483648 && b == -1 {
429		return 0
430	}
431	return uint32(a % b)
432}