exec.gno
13.58 Kb · 432 lines
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/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/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}
