1// Copyright 2016 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bpf
6
7import (
8	"errors"
9	"fmt"
10)
11
12// A VM is an emulated BPF virtual machine.
13type VM struct {
14	filter []Instruction
15}
16
17// NewVM returns a new VM using the input BPF program.
18func NewVM(filter []Instruction) (*VM, error) {
19	if len(filter) == 0 {
20		return nil, errors.New("one or more Instructions must be specified")
21	}
22
23	for i, ins := range filter {
24		check := len(filter) - (i + 1)
25		switch ins := ins.(type) {
26		// Check for out-of-bounds jumps in instructions
27		case Jump:
28			if check <= int(ins.Skip) {
29				return nil, fmt.Errorf("cannot jump %d instructions; jumping past program bounds", ins.Skip)
30			}
31		case JumpIf:
32			if check <= int(ins.SkipTrue) {
33				return nil, fmt.Errorf("cannot jump %d instructions in true case; jumping past program bounds", ins.SkipTrue)
34			}
35			if check <= int(ins.SkipFalse) {
36				return nil, fmt.Errorf("cannot jump %d instructions in false case; jumping past program bounds", ins.SkipFalse)
37			}
38		case JumpIfX:
39			if check <= int(ins.SkipTrue) {
40				return nil, fmt.Errorf("cannot jump %d instructions in true case; jumping past program bounds", ins.SkipTrue)
41			}
42			if check <= int(ins.SkipFalse) {
43				return nil, fmt.Errorf("cannot jump %d instructions in false case; jumping past program bounds", ins.SkipFalse)
44			}
45		// Check for division or modulus by zero
46		case ALUOpConstant:
47			if ins.Val != 0 {
48				break
49			}
50
51			switch ins.Op {
52			case ALUOpDiv, ALUOpMod:
53				return nil, errors.New("cannot divide by zero using ALUOpConstant")
54			}
55		// Check for unknown extensions
56		case LoadExtension:
57			switch ins.Num {
58			case ExtLen:
59			default:
60				return nil, fmt.Errorf("extension %d not implemented", ins.Num)
61			}
62		}
63	}
64
65	// Make sure last instruction is a return instruction
66	switch filter[len(filter)-1].(type) {
67	case RetA, RetConstant:
68	default:
69		return nil, errors.New("BPF program must end with RetA or RetConstant")
70	}
71
72	// Though our VM works using disassembled instructions, we
73	// attempt to assemble the input filter anyway to ensure it is compatible
74	// with an operating system VM.
75	_, err := Assemble(filter)
76
77	return &VM{
78		filter: filter,
79	}, err
80}
81
82// Run runs the VM's BPF program against the input bytes.
83// Run returns the number of bytes accepted by the BPF program, and any errors
84// which occurred while processing the program.
85func (v *VM) Run(in []byte) (int, error) {
86	var (
87		// Registers of the virtual machine
88		regA       uint32
89		regX       uint32
90		regScratch [16]uint32
91
92		// OK is true if the program should continue processing the next
93		// instruction, or false if not, causing the loop to break
94		ok = true
95	)
96
97	// TODO(mdlayher): implement:
98	// - NegateA:
99	//   - would require a change from uint32 registers to int32
100	//     registers
101
102	// TODO(mdlayher): add interop tests that check signedness of ALU
103	// operations against kernel implementation, and make sure Go
104	// implementation matches behavior
105
106	for i := 0; i < len(v.filter) && ok; i++ {
107		ins := v.filter[i]
108
109		switch ins := ins.(type) {
110		case ALUOpConstant:
111			regA = aluOpConstant(ins, regA)
112		case ALUOpX:
113			regA, ok = aluOpX(ins, regA, regX)
114		case Jump:
115			i += int(ins.Skip)
116		case JumpIf:
117			jump := jumpIf(ins, regA)
118			i += jump
119		case JumpIfX:
120			jump := jumpIfX(ins, regA, regX)
121			i += jump
122		case LoadAbsolute:
123			regA, ok = loadAbsolute(ins, in)
124		case LoadConstant:
125			regA, regX = loadConstant(ins, regA, regX)
126		case LoadExtension:
127			regA = loadExtension(ins, in)
128		case LoadIndirect:
129			regA, ok = loadIndirect(ins, in, regX)
130		case LoadMemShift:
131			regX, ok = loadMemShift(ins, in)
132		case LoadScratch:
133			regA, regX = loadScratch(ins, regScratch, regA, regX)
134		case RetA:
135			return int(regA), nil
136		case RetConstant:
137			return int(ins.Val), nil
138		case StoreScratch:
139			regScratch = storeScratch(ins, regScratch, regA, regX)
140		case TAX:
141			regX = regA
142		case TXA:
143			regA = regX
144		default:
145			return 0, fmt.Errorf("unknown Instruction at index %d: %T", i, ins)
146		}
147	}
148
149	return 0, nil
150}
151