machine.gno
8.04 Kb · 287 lines
1package bf
2
3import (
4 "errors"
5
6 "gno.land/p/moul/x/vm/vmkit/v0"
7)
8
9// VMName is the identifier this machine registers under in a
10// [vmkit.Instance].
11const VMName = "bf"
12
13// snapMagic and snapVersion tag a snapshot so a machine refuses bytes that
14// were not written by this machine at this version, instead of decoding them
15// into a plausible-looking wrong state.
16const (
17 snapMagic uint32 = 0x62660001 // "bf" 0001
18 snapVersion byte = 1
19)
20
21// ErrNoProgram is returned when a [Machine] is stepped without a program.
22var ErrNoProgram = errors.New("bf: machine has no program")
23
24// Machine is a compiled Brainfuck program, mid-execution: a
25// [vmkit.Machine] with a fixed tape, a fuel-metered step loop, input and
26// output through the host, and a snapshot small enough that pausing is
27// cheaper than starting over.
28//
29// The tape is a fixed-size array rather than a slice: that is rung 4 of the
30// ladder, and the README reports what it actually bought.
31type Machine struct {
32 prog *Program
33
34 tape [TapeSize]byte
35 ptr int
36 pc int
37 inPos int // read cursor into Host.Input, carried across slices
38
39 status vmkit.Status
40 trap string
41
42 // hi is the highest tape index written so far, so a snapshot can stop
43 // there instead of carrying 30,000 bytes of zeros.
44 hi int
45}
46
47// NewMachine returns a machine ready to run prog from the start.
48func NewMachine(prog *Program) *Machine {
49 return &Machine{prog: prog, status: vmkit.Running}
50}
51
52// Load compiles src at [Default] and returns a machine for it.
53func Load(src string) (*Machine, error) {
54 prog, err := CompileDefault(src)
55 if err != nil {
56 return nil, err
57 }
58 return NewMachine(prog), nil
59}
60
61// Program returns the program the machine is running.
62func (m *Machine) Program() *Program { return m.prog }
63
64// Status returns the machine's current status.
65func (m *Machine) Status() vmkit.Status { return m.status }
66
67// Trap returns the reason the machine trapped, or "". It makes Machine a
68// [vmkit.Trapper].
69func (m *Machine) Trap() string { return m.trap }
70
71// Pointer returns the tape pointer.
72func (m *Machine) Pointer() int { return m.ptr }
73
74// PC returns the index of the next op to execute.
75func (m *Machine) PC() int { return m.pc }
76
77// Cell returns the tape byte at i, wrapped into range.
78func (m *Machine) Cell(i int) byte { return m.tape[wrap(i)] }
79
80// Touched returns how many tape cells the program has reached, which is the
81// length a snapshot has to carry.
82func (m *Machine) Touched() int { return m.hi + 1 }
83
84// Step runs until the program halts, traps, or spends `fuel` units, charging
85// one unit per op executed and one per cell a scan walks over. Pass
86// [vmkit.Unmetered] to run to completion.
87//
88// Fuel is charged before the op runs, so a machine that stops for lack of
89// fuel has not half-executed anything: it is exactly at the op it could not
90// pay for, and resuming re-executes that op and nothing else.
91//
92// Three things in here are written the way they are because the alternative
93// was measured and lost. The README has the table.
94//
95// - The fuel counter is two locals, not a [vmkit.Meter]. Calling
96// Meter.Charge once per instruction costs 86% on top of the whole
97// dispatch loop and triples the allocation count. Meter stays the type
98// at the API boundary, where it is called once; it is not a hot-path
99// type, and no guest VM should treat it as one.
100// - The program counter and the tape pointer are locals, written back once
101// by the deferred closure. Reaching through m. for them on every
102// instruction costs 16%.
103// - The pc range check happens once, before the loop, not per op. Every
104// jump target is produced by [Compile] and every restored pc is
105// validated by [Machine.Restore], so per-op checking buys nothing.
106func (m *Machine) Step(h vmkit.Host, fuel int64) (int64, vmkit.Status) {
107 if m.prog == nil {
108 m.status, m.trap = vmkit.Trapped, "no program"
109 return 0, m.status
110 }
111 if m.status != vmkit.Running {
112 return 0, m.status
113 }
114
115 ops := m.prog.ops
116 pc, ptr, hi := m.pc, m.ptr, m.hi
117 // One write-back, on every return path, including a panic.
118 defer func() { m.pc, m.ptr, m.hi = pc, ptr, hi }()
119
120 if pc < 0 || pc >= len(ops) {
121 m.status, m.trap = vmkit.Trapped, "pc out of range"
122 return 0, m.status
123 }
124
125 // budget < 0 is vmkit.Unmetered.
126 budget := fuel
127 if budget < 0 {
128 budget = vmkit.Unmetered
129 }
130 var used int64
131
132 for {
133 if budget != vmkit.Unmetered && used >= budget {
134 return used, vmkit.Running
135 }
136 used++
137
138 switch ops[pc].code {
139 case opAdd:
140 m.tape[ptr] += byte(ops[pc].arg)
141 case opMove:
142 ptr = wrap(ptr + ops[pc].arg)
143 if ptr > hi {
144 hi = ptr
145 }
146 case opSet:
147 m.tape[ptr] = byte(ops[pc].arg)
148 case opAddMul:
149 if v := m.tape[ptr]; v != 0 {
150 t := wrap(ptr + ops[pc].off)
151 m.tape[t] += v * byte(ops[pc].arg)
152 if t > hi {
153 hi = t
154 }
155 }
156 case opScan:
157 // A scan is charged per cell, so it cannot be a way to
158 // buy unbounded work for one unit of fuel. Stopping
159 // mid-scan is safe: the pointer has moved, the pc has
160 // not, so resuming continues the same walk.
161 for m.tape[ptr] != 0 {
162 if budget != vmkit.Unmetered && used >= budget {
163 return used, vmkit.Running
164 }
165 used++
166 ptr = wrap(ptr + ops[pc].arg)
167 if ptr > hi {
168 hi = ptr
169 }
170 }
171 case opOut:
172 h.Output([]byte{m.tape[ptr]})
173 case opIn:
174 in := h.Input()
175 if m.inPos < len(in) {
176 m.tape[ptr] = in[m.inPos]
177 m.inPos++
178 } else {
179 // End of input is a zero cell, the most common
180 // of the three conventions the language never
181 // settled.
182 m.tape[ptr] = 0
183 }
184 case opJmpZ:
185 if m.tape[ptr] == 0 {
186 pc = ops[pc].arg
187 }
188 case opJmpNZ:
189 if m.tape[ptr] != 0 {
190 pc = ops[pc].arg
191 }
192 case opHalt:
193 m.status = vmkit.Halted
194 return used, m.status
195 default:
196 m.status, m.trap = vmkit.Trapped, "unknown opcode"
197 return used, m.status
198 }
199 pc++
200 }
201}
202
203// Snapshot serializes the machine. The tape is truncated at the highest cell
204// the program has reached, which is what makes pausing affordable: a hello
205// world that touched six cells snapshots six bytes of tape, not 30,000.
206func (m *Machine) Snapshot() []byte {
207 w := vmkit.NewWriter(m.hi + 48)
208 w.Uint32(snapMagic)
209 w.Byte(snapVersion)
210 w.Int(int64(m.pc))
211 w.Int(int64(m.ptr))
212 w.Int(int64(m.inPos))
213 w.Byte(byte(m.status))
214 w.String(m.trap)
215
216 n := m.hi + 1
217 if n > TapeSize {
218 n = TapeSize
219 }
220 w.Bytes(m.tape[:n])
221 return w.Out()
222}
223
224// Restore loads a snapshot into a machine that already carries the program
225// the snapshot was taken from. The program is not in the snapshot: a realm
226// stores it once, beside the instance, instead of once per pause.
227func (m *Machine) Restore(b []byte) error {
228 r := vmkit.NewReader(b)
229 if r.Uint32() != snapMagic {
230 return vmkit.ErrBadSnapshot
231 }
232 if r.Byte() != snapVersion {
233 return vmkit.ErrBadSnapshot
234 }
235 pc := int(r.Int())
236 ptr := int(r.Int())
237 inPos := int(r.Int())
238 status := vmkit.Status(r.Byte())
239 trap := r.String()
240 tape := r.Bytes()
241 if err := r.Err(); err != nil {
242 return err
243 }
244 if len(tape) > TapeSize || ptr < 0 || ptr >= TapeSize || inPos < 0 {
245 return vmkit.ErrBadSnapshot
246 }
247 if m.prog != nil && (pc < 0 || pc > len(m.prog.ops)) {
248 return vmkit.ErrBadSnapshot
249 }
250
251 m.pc, m.ptr, m.inPos = pc, ptr, inPos
252 m.status, m.trap = status, trap
253 // Zero only what this machine could have written: hi bounds every
254 // write it has made, and a 30,000 element composite literal is not
255 // something to put in a restore path.
256 for i := 0; i <= m.hi && i < TapeSize; i++ {
257 m.tape[i] = 0
258 }
259 copy(m.tape[:], tape)
260 m.hi = len(tape) - 1
261 if m.hi < 0 {
262 m.hi = 0
263 }
264 return nil
265}
266
267// Run compiles src at [Default] and runs it to completion against h, with no
268// fuel bound. It is the one-shot path: convenient for a test or a small
269// program, and exactly the thing a realm should not do with untrusted input.
270func Run(src string, h vmkit.Host) (vmkit.Status, error) {
271 m, err := Load(src)
272 if err != nil {
273 return vmkit.Trapped, err
274 }
275 _, status := m.Step(h, vmkit.Unmetered)
276 return status, nil
277}
278
279// wrap folds a tape index into range, the way the naive interpreter does one
280// step at a time.
281func wrap(i int) int {
282 i %= TapeSize
283 if i < 0 {
284 i += TapeSize
285 }
286 return i
287}
