summaryrefslogtreecommitdiffhomepage
path: root/pkg/bpf/interpreter.go
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/bpf/interpreter.go')
-rw-r--r--pkg/bpf/interpreter.go412
1 files changed, 412 insertions, 0 deletions
diff --git a/pkg/bpf/interpreter.go b/pkg/bpf/interpreter.go
new file mode 100644
index 000000000..86de523a2
--- /dev/null
+++ b/pkg/bpf/interpreter.go
@@ -0,0 +1,412 @@
+// Copyright 2018 The gVisor Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+ "fmt"
+
+ "gvisor.googlesource.com/gvisor/pkg/abi/linux"
+)
+
+// Possible values for ProgramError.Code.
+const (
+ // DivisionByZero indicates that a program contains, or executed, a
+ // division or modulo by zero.
+ DivisionByZero = iota
+
+ // InvalidEndOfProgram indicates that the last instruction of a program is
+ // not a return.
+ InvalidEndOfProgram
+
+ // InvalidInstructionCount indicates that a program has zero instructions
+ // or more than MaxInstructions instructions.
+ InvalidInstructionCount
+
+ // InvalidJumpTarget indicates that a program contains a jump whose target
+ // is outside of the program's bounds.
+ InvalidJumpTarget
+
+ // InvalidLoad indicates that a program executed an invalid load of input
+ // data.
+ InvalidLoad
+
+ // InvalidOpcode indicates that a program contains an instruction with an
+ // invalid opcode.
+ InvalidOpcode
+
+ // InvalidRegister indicates that a program contains a load from, or store
+ // to, a non-existent M register (index >= ScratchMemRegisters).
+ InvalidRegister
+)
+
+// Error is an error encountered while compiling or executing a BPF program.
+type Error struct {
+ // Code indicates the kind of error that occurred.
+ Code int
+
+ // PC is the program counter (index into the list of instructions) at which
+ // the error occurred.
+ PC int
+}
+
+func (e Error) codeString() string {
+ switch e.Code {
+ case DivisionByZero:
+ return "division by zero"
+ case InvalidEndOfProgram:
+ return "last instruction must be a return"
+ case InvalidInstructionCount:
+ return "invalid number of instructions"
+ case InvalidJumpTarget:
+ return "jump target out of bounds"
+ case InvalidLoad:
+ return "load out of bounds or violates input alignment requirements"
+ case InvalidOpcode:
+ return "invalid instruction opcode"
+ case InvalidRegister:
+ return "invalid M register"
+ default:
+ return "unknown error"
+ }
+}
+
+// Error implements error.Error.
+func (e Error) Error() string {
+ return fmt.Sprintf("at l%d: %s", e.PC, e.codeString())
+}
+
+// Program is a BPF program that has been validated for consistency.
+//
+// +stateify savable
+type Program struct {
+ instructions []linux.BPFInstruction
+}
+
+// Length returns the number of instructions in the program.
+func (p Program) Length() int {
+ return len(p.instructions)
+}
+
+// Compile performs validation on a sequence of BPF instructions before
+// wrapping them in a Program.
+func Compile(insns []linux.BPFInstruction) (Program, error) {
+ if len(insns) == 0 || len(insns) > MaxInstructions {
+ return Program{}, Error{InvalidInstructionCount, len(insns)}
+ }
+
+ // The last instruction must be a return.
+ if last := insns[len(insns)-1]; last.OpCode != (Ret|K) && last.OpCode != (Ret|A) {
+ return Program{}, Error{InvalidEndOfProgram, len(insns) - 1}
+ }
+
+ // Validate each instruction. Note that we skip a validation Linux does:
+ // Linux additionally verifies that every load from an M register is
+ // preceded, in every path, by a store to the same M register, in order to
+ // avoid having to clear M between programs
+ // (net/core/filter.c:check_load_and_stores). We always start with a zeroed
+ // M array.
+ for pc, i := range insns {
+ if i.OpCode&unusedBitsMask != 0 {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ switch i.OpCode & instructionClassMask {
+ case Ld:
+ mode := i.OpCode & loadModeMask
+ switch i.OpCode & loadSizeMask {
+ case W:
+ if mode != Imm && mode != Abs && mode != Ind && mode != Mem && mode != Len {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ if mode == Mem && i.K >= ScratchMemRegisters {
+ return Program{}, Error{InvalidRegister, pc}
+ }
+ case H, B:
+ if mode != Abs && mode != Ind {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ default:
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ case Ldx:
+ mode := i.OpCode & loadModeMask
+ switch i.OpCode & loadSizeMask {
+ case W:
+ if mode != Imm && mode != Mem && mode != Len {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ if mode == Mem && i.K >= ScratchMemRegisters {
+ return Program{}, Error{InvalidRegister, pc}
+ }
+ case B:
+ if mode != Msh {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ default:
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ case St, Stx:
+ if i.OpCode&storeUnusedBitsMask != 0 {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ if i.K >= ScratchMemRegisters {
+ return Program{}, Error{InvalidRegister, pc}
+ }
+ case Alu:
+ switch i.OpCode & aluMask {
+ case Add, Sub, Mul, Or, And, Lsh, Rsh, Xor:
+ break
+ case Div, Mod:
+ if src := i.OpCode & srcAluJmpMask; src == K && i.K == 0 {
+ return Program{}, Error{DivisionByZero, pc}
+ }
+ case Neg:
+ // Negation doesn't take a source operand.
+ if i.OpCode&srcAluJmpMask != 0 {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ default:
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ case Jmp:
+ switch i.OpCode & jmpMask {
+ case Ja:
+ // Unconditional jump doesn't take a source operand.
+ if i.OpCode&srcAluJmpMask != 0 {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ // Do the comparison in 64 bits to avoid the possibility of
+ // overflow from a very large i.K.
+ if uint64(pc)+uint64(i.K)+1 >= uint64(len(insns)) {
+ return Program{}, Error{InvalidJumpTarget, pc}
+ }
+ case Jeq, Jgt, Jge, Jset:
+ // jt and jf are uint16s, so there's no threat of overflow.
+ if pc+int(i.JumpIfTrue)+1 >= len(insns) {
+ return Program{}, Error{InvalidJumpTarget, pc}
+ }
+ if pc+int(i.JumpIfFalse)+1 >= len(insns) {
+ return Program{}, Error{InvalidJumpTarget, pc}
+ }
+ default:
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ case Ret:
+ if i.OpCode&retUnusedBitsMask != 0 {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ if src := i.OpCode & srcRetMask; src != K && src != A {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ case Misc:
+ if misc := i.OpCode & miscMask; misc != Tax && misc != Txa {
+ return Program{}, Error{InvalidOpcode, pc}
+ }
+ }
+ }
+
+ return Program{insns}, nil
+}
+
+// Input represents a source of input data for a BPF program. (BPF
+// documentation sometimes refers to the input data as the "packet" due to its
+// origins as a packet processing DSL.)
+//
+// For all of Input's Load methods:
+//
+// - The second (bool) return value is true if the load succeeded and false
+// otherwise.
+//
+// - Inputs should not assume that the loaded range falls within the input
+// data's length. Inputs should return false if the load falls outside of the
+// input data.
+//
+// - Inputs should not assume that the offset is correctly aligned. Inputs may
+// choose to service or reject loads to unaligned addresses.
+type Input interface {
+ // Load32 reads 32 bits from the input starting at the given byte offset.
+ Load32(off uint32) (uint32, bool)
+
+ // Load16 reads 16 bits from the input starting at the given byte offset.
+ Load16(off uint32) (uint16, bool)
+
+ // Load8 reads 8 bits from the input starting at the given byte offset.
+ Load8(off uint32) (uint8, bool)
+
+ // Length returns the length of the input in bytes.
+ Length() uint32
+}
+
+// machine represents the state of a BPF virtual machine.
+type machine struct {
+ A uint32
+ X uint32
+ M [ScratchMemRegisters]uint32
+}
+
+func conditionalJumpOffset(insn linux.BPFInstruction, cond bool) int {
+ if cond {
+ return int(insn.JumpIfTrue)
+ }
+ return int(insn.JumpIfFalse)
+}
+
+// Exec executes a BPF program over the given input and returns its return
+// value.
+func Exec(p Program, in Input) (uint32, error) {
+ var m machine
+ var pc int
+ for ; pc < len(p.instructions); pc++ {
+ i := p.instructions[pc]
+ switch i.OpCode {
+ case Ld | Imm | W:
+ m.A = i.K
+ case Ld | Abs | W:
+ val, ok := in.Load32(i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.A = val
+ case Ld | Abs | H:
+ val, ok := in.Load16(i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.A = uint32(val)
+ case Ld | Abs | B:
+ val, ok := in.Load8(i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.A = uint32(val)
+ case Ld | Ind | W:
+ val, ok := in.Load32(m.X + i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.A = val
+ case Ld | Ind | H:
+ val, ok := in.Load16(m.X + i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.A = uint32(val)
+ case Ld | Ind | B:
+ val, ok := in.Load8(m.X + i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.A = uint32(val)
+ case Ld | Mem | W:
+ m.A = m.M[int(i.K)]
+ case Ld | Len | W:
+ m.A = in.Length()
+ case Ldx | Imm | W:
+ m.X = i.K
+ case Ldx | Mem | W:
+ m.X = m.M[int(i.K)]
+ case Ldx | Len | W:
+ m.X = in.Length()
+ case Ldx | Msh | B:
+ val, ok := in.Load8(i.K)
+ if !ok {
+ return 0, Error{InvalidLoad, pc}
+ }
+ m.X = 4 * uint32(val&0xf)
+ case St:
+ m.M[int(i.K)] = m.A
+ case Stx:
+ m.M[int(i.K)] = m.X
+ case Alu | Add | K:
+ m.A += i.K
+ case Alu | Add | X:
+ m.A += m.X
+ case Alu | Sub | K:
+ m.A -= i.K
+ case Alu | Sub | X:
+ m.A -= m.X
+ case Alu | Mul | K:
+ m.A *= i.K
+ case Alu | Mul | X:
+ m.A *= m.X
+ case Alu | Div | K:
+ // K != 0 already checked by Compile.
+ m.A /= i.K
+ case Alu | Div | X:
+ if m.X == 0 {
+ return 0, Error{DivisionByZero, pc}
+ }
+ m.A /= m.X
+ case Alu | Or | K:
+ m.A |= i.K
+ case Alu | Or | X:
+ m.A |= m.X
+ case Alu | And | K:
+ m.A &= i.K
+ case Alu | And | X:
+ m.A &= m.X
+ case Alu | Lsh | K:
+ m.A <<= i.K
+ case Alu | Lsh | X:
+ m.A <<= m.X
+ case Alu | Rsh | K:
+ m.A >>= i.K
+ case Alu | Rsh | X:
+ m.A >>= m.X
+ case Alu | Neg:
+ m.A = uint32(-int32(m.A))
+ case Alu | Mod | K:
+ // K != 0 already checked by Compile.
+ m.A %= i.K
+ case Alu | Mod | X:
+ if m.X == 0 {
+ return 0, Error{DivisionByZero, pc}
+ }
+ m.A %= m.X
+ case Alu | Xor | K:
+ m.A ^= i.K
+ case Alu | Xor | X:
+ m.A ^= m.X
+ case Jmp | Ja:
+ pc += int(i.K)
+ case Jmp | Jeq | K:
+ pc += conditionalJumpOffset(i, m.A == i.K)
+ case Jmp | Jeq | X:
+ pc += conditionalJumpOffset(i, m.A == m.X)
+ case Jmp | Jgt | K:
+ pc += conditionalJumpOffset(i, m.A > i.K)
+ case Jmp | Jgt | X:
+ pc += conditionalJumpOffset(i, m.A > m.X)
+ case Jmp | Jge | K:
+ pc += conditionalJumpOffset(i, m.A >= i.K)
+ case Jmp | Jge | X:
+ pc += conditionalJumpOffset(i, m.A >= m.X)
+ case Jmp | Jset | K:
+ pc += conditionalJumpOffset(i, (m.A&i.K) != 0)
+ case Jmp | Jset | X:
+ pc += conditionalJumpOffset(i, (m.A&m.X) != 0)
+ case Ret | K:
+ return i.K, nil
+ case Ret | A:
+ return m.A, nil
+ case Misc | Tax:
+ m.A = m.X
+ case Misc | Txa:
+ m.X = m.A
+ default:
+ return 0, Error{InvalidOpcode, pc}
+ }
+ }
+ return 0, Error{InvalidEndOfProgram, pc}
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-01 14:30:34 +0000