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 5 package bpf
6 7 import (
8 "errors"
9 "fmt"
10 )
11 12 // A VM is an emulated BPF virtual machine.
13 type VM struct {
14 filter []Instruction
15 }
16 17 // NewVM returns a new VM using the input BPF program.
18 func 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.
85 func (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