David K. Bainbridge | 215e024 | 2017-09-05 23:18:24 -0700 | [diff] [blame] | 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 | // Check for division or modulus by zero |
| 39 | case ALUOpConstant: |
| 40 | if ins.Val != 0 { |
| 41 | break |
| 42 | } |
| 43 | |
| 44 | switch ins.Op { |
| 45 | case ALUOpDiv, ALUOpMod: |
| 46 | return nil, errors.New("cannot divide by zero using ALUOpConstant") |
| 47 | } |
| 48 | // Check for unknown extensions |
| 49 | case LoadExtension: |
| 50 | switch ins.Num { |
| 51 | case ExtLen: |
| 52 | default: |
| 53 | return nil, fmt.Errorf("extension %d not implemented", ins.Num) |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | // Make sure last instruction is a return instruction |
| 59 | switch filter[len(filter)-1].(type) { |
| 60 | case RetA, RetConstant: |
| 61 | default: |
| 62 | return nil, errors.New("BPF program must end with RetA or RetConstant") |
| 63 | } |
| 64 | |
| 65 | // Though our VM works using disassembled instructions, we |
| 66 | // attempt to assemble the input filter anyway to ensure it is compatible |
| 67 | // with an operating system VM. |
| 68 | _, err := Assemble(filter) |
| 69 | |
| 70 | return &VM{ |
| 71 | filter: filter, |
| 72 | }, err |
| 73 | } |
| 74 | |
| 75 | // Run runs the VM's BPF program against the input bytes. |
| 76 | // Run returns the number of bytes accepted by the BPF program, and any errors |
| 77 | // which occurred while processing the program. |
| 78 | func (v *VM) Run(in []byte) (int, error) { |
| 79 | var ( |
| 80 | // Registers of the virtual machine |
| 81 | regA uint32 |
| 82 | regX uint32 |
| 83 | regScratch [16]uint32 |
| 84 | |
| 85 | // OK is true if the program should continue processing the next |
| 86 | // instruction, or false if not, causing the loop to break |
| 87 | ok = true |
| 88 | ) |
| 89 | |
| 90 | // TODO(mdlayher): implement: |
| 91 | // - NegateA: |
| 92 | // - would require a change from uint32 registers to int32 |
| 93 | // registers |
| 94 | |
| 95 | // TODO(mdlayher): add interop tests that check signedness of ALU |
| 96 | // operations against kernel implementation, and make sure Go |
| 97 | // implementation matches behavior |
| 98 | |
| 99 | for i := 0; i < len(v.filter) && ok; i++ { |
| 100 | ins := v.filter[i] |
| 101 | |
| 102 | switch ins := ins.(type) { |
| 103 | case ALUOpConstant: |
| 104 | regA = aluOpConstant(ins, regA) |
| 105 | case ALUOpX: |
| 106 | regA, ok = aluOpX(ins, regA, regX) |
| 107 | case Jump: |
| 108 | i += int(ins.Skip) |
| 109 | case JumpIf: |
| 110 | jump := jumpIf(ins, regA) |
| 111 | i += jump |
| 112 | case LoadAbsolute: |
| 113 | regA, ok = loadAbsolute(ins, in) |
| 114 | case LoadConstant: |
| 115 | regA, regX = loadConstant(ins, regA, regX) |
| 116 | case LoadExtension: |
| 117 | regA = loadExtension(ins, in) |
| 118 | case LoadIndirect: |
| 119 | regA, ok = loadIndirect(ins, in, regX) |
| 120 | case LoadMemShift: |
| 121 | regX, ok = loadMemShift(ins, in) |
| 122 | case LoadScratch: |
| 123 | regA, regX = loadScratch(ins, regScratch, regA, regX) |
| 124 | case RetA: |
| 125 | return int(regA), nil |
| 126 | case RetConstant: |
| 127 | return int(ins.Val), nil |
| 128 | case StoreScratch: |
| 129 | regScratch = storeScratch(ins, regScratch, regA, regX) |
| 130 | case TAX: |
| 131 | regX = regA |
| 132 | case TXA: |
| 133 | regA = regX |
| 134 | default: |
| 135 | return 0, fmt.Errorf("unknown Instruction at index %d: %T", i, ins) |
| 136 | } |
| 137 | } |
| 138 | |
| 139 | return 0, nil |
| 140 | } |