diff options
Diffstat (limited to 'pkg/bpf')
| -rw-r--r-- | pkg/bpf/BUILD | 46 | ||||
| -rw-r--r-- | pkg/bpf/bpf.go | 129 | ||||
| -rw-r--r-- | pkg/bpf/decoder.go | 248 | ||||
| -rw-r--r-- | pkg/bpf/decoder_test.go | 146 | ||||
| -rw-r--r-- | pkg/bpf/input_bytes.go | 58 | ||||
| -rw-r--r-- | pkg/bpf/interpreter.go | 410 | ||||
| -rw-r--r-- | pkg/bpf/interpreter_test.go | 797 | ||||
| -rw-r--r-- | pkg/bpf/program_builder.go | 159 | ||||
| -rw-r--r-- | pkg/bpf/program_builder_test.go | 157 |
9 files changed, 2150 insertions, 0 deletions
diff --git a/pkg/bpf/BUILD b/pkg/bpf/BUILD new file mode 100644 index 000000000..d4f12f13a --- /dev/null +++ b/pkg/bpf/BUILD @@ -0,0 +1,46 @@ +package(licenses = ["notice"]) # Apache 2.0 + +load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test") +load("//tools/go_stateify:defs.bzl", "go_stateify") + +go_stateify( + name = "bpf_state", + srcs = [ + "interpreter.go", + ], + out = "bpf_state.go", + package = "bpf", +) + +go_library( + name = "bpf", + srcs = [ + "bpf.go", + "bpf_state.go", + "decoder.go", + "input_bytes.go", + "interpreter.go", + "program_builder.go", + ], + importpath = "gvisor.googlesource.com/gvisor/pkg/bpf", + visibility = ["//visibility:public"], + deps = [ + "//pkg/abi/linux", + "//pkg/state", + ], +) + +go_test( + name = "bpf_test", + size = "small", + srcs = [ + "decoder_test.go", + "interpreter_test.go", + "program_builder_test.go", + ], + embed = [":bpf"], + deps = [ + "//pkg/abi/linux", + "//pkg/binary", + ], +) diff --git a/pkg/bpf/bpf.go b/pkg/bpf/bpf.go new file mode 100644 index 000000000..757744090 --- /dev/null +++ b/pkg/bpf/bpf.go @@ -0,0 +1,129 @@ +// Copyright 2018 Google Inc. +// +// 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 provides tools for working with Berkeley Packet Filter (BPF) +// programs. More information on BPF can be found at +// https://www.freebsd.org/cgi/man.cgi?bpf(4) +package bpf + +import "gvisor.googlesource.com/gvisor/pkg/abi/linux" + +const ( + // MaxInstructions is the maximum number of instructions in a BPF program, + // and is equal to Linux's BPF_MAXINSNS. + MaxInstructions = 4096 + + // ScratchMemRegisters is the number of M registers in a BPF virtual machine, + // and is equal to Linux's BPF_MEMWORDS. + ScratchMemRegisters = 16 +) + +// Parts of a linux.BPFInstruction.OpCode. Compare to the Linux kernel's +// include/uapi/linux/filter.h. +// +// In the comments below: +// +// - A, X, and M[] are BPF virtual machine registers. +// +// - K refers to the instruction field linux.BPFInstruction.K. +// +// - Bits are counted from the LSB position. +const ( + // Instruction class, stored in bits 0-2. + Ld = 0x00 // load into A + Ldx = 0x01 // load into X + St = 0x02 // store from A + Stx = 0x03 // store from X + Alu = 0x04 // arithmetic + Jmp = 0x05 // jump + Ret = 0x06 // return + Misc = 0x07 + instructionClassMask = 0x07 + + // Size of a load, stored in bits 3-4. + W = 0x00 // 32 bits + H = 0x08 // 16 bits + B = 0x10 // 8 bits + loadSizeMask = 0x18 + + // Source operand for a load, stored in bits 5-7. + // Address mode numbers in the comments come from Linux's + // Documentation/networking/filter.txt. + Imm = 0x00 // immediate value K (mode 4) + Abs = 0x20 // data in input at byte offset K (mode 1) + Ind = 0x40 // data in input at byte offset X+K (mode 2) + Mem = 0x60 // M[K] (mode 3) + Len = 0x80 // length of the input in bytes ("BPF extension len") + Msh = 0xa0 // 4 * lower nibble of input at byte offset K (mode 5) + loadModeMask = 0xe0 + + // Source operands for arithmetic, jump, and return instructions. + // Arithmetic and jump instructions can use K or X as source operands. + // Return instructions can use K or A as source operands. + K = 0x00 // still mode 4 + X = 0x08 // mode 0 + A = 0x10 // mode 9 + srcAluJmpMask = 0x08 + srcRetMask = 0x18 + + // Arithmetic instructions, stored in bits 4-7. + Add = 0x00 + Sub = 0x10 // A - src + Mul = 0x20 + Div = 0x30 // A / src + Or = 0x40 + And = 0x50 + Lsh = 0x60 // A << src + Rsh = 0x70 // A >> src + Neg = 0x80 // -A (src ignored) + Mod = 0x90 // A % src + Xor = 0xa0 + aluMask = 0xf0 + + // Jump instructions, stored in bits 4-7. + Ja = 0x00 // unconditional (uses K for jump offset) + Jeq = 0x10 // if A == src + Jgt = 0x20 // if A > src + Jge = 0x30 // if A >= src + Jset = 0x40 // if (A & src) != 0 + jmpMask = 0xf0 + + // Miscellaneous instructions, stored in bits 3-7. + Tax = 0x00 // A = X + Txa = 0x80 // X = A + miscMask = 0xf8 + + // Masks for bits that should be zero. + unusedBitsMask = 0xff00 // all valid instructions use only bits 0-7 + storeUnusedBitsMask = 0xf8 // stores only use instruction class + retUnusedBitsMask = 0xe0 // returns only use instruction class and source operand +) + +// Stmt returns a linux.BPFInstruction representing a BPF non-jump instruction. +func Stmt(code uint16, k uint32) linux.BPFInstruction { + return linux.BPFInstruction{ + OpCode: code, + K: k, + } +} + +// Jump returns a linux.BPFInstruction representing a BPF jump instruction. +func Jump(code uint16, k uint32, jt, jf uint8) linux.BPFInstruction { + return linux.BPFInstruction{ + OpCode: code, + JumpIfTrue: jt, + JumpIfFalse: jf, + K: k, + } +} diff --git a/pkg/bpf/decoder.go b/pkg/bpf/decoder.go new file mode 100644 index 000000000..6873ffa5c --- /dev/null +++ b/pkg/bpf/decoder.go @@ -0,0 +1,248 @@ +// Copyright 2018 Google Inc. +// +// 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 ( + "bytes" + "fmt" + + "gvisor.googlesource.com/gvisor/pkg/abi/linux" +) + +// DecodeProgram translates an array of BPF instructions into text format. +func DecodeProgram(program []linux.BPFInstruction) (string, error) { + var ret bytes.Buffer + for line, s := range program { + ret.WriteString(fmt.Sprintf("%v: ", line)) + if err := decode(s, line, &ret); err != nil { + return "", err + } + ret.WriteString("\n") + } + return ret.String(), nil +} + +// Decode translates BPF instruction into text format. +func Decode(inst linux.BPFInstruction) (string, error) { + var ret bytes.Buffer + err := decode(inst, -1, &ret) + return ret.String(), err +} + +func decode(inst linux.BPFInstruction, line int, w *bytes.Buffer) error { + var err error + switch inst.OpCode & instructionClassMask { + case Ld: + err = decodeLd(inst, w) + case Ldx: + err = decodeLdx(inst, w) + case St: + w.WriteString(fmt.Sprintf("M[%v] <- A", inst.K)) + case Stx: + w.WriteString(fmt.Sprintf("M[%v] <- X", inst.K)) + case Alu: + err = decodeAlu(inst, w) + case Jmp: + err = decodeJmp(inst, line, w) + case Ret: + err = decodeRet(inst, w) + case Misc: + err = decodeMisc(inst, w) + default: + return fmt.Errorf("invalid BPF instruction: %v", inst) + } + return err +} + +// A <- P[k:4] +func decodeLd(inst linux.BPFInstruction, w *bytes.Buffer) error { + w.WriteString("A <- ") + + switch inst.OpCode & loadModeMask { + case Imm: + w.WriteString(fmt.Sprintf("%v", inst.K)) + case Abs: + w.WriteString(fmt.Sprintf("P[%v:", inst.K)) + if err := decodeLdSize(inst, w); err != nil { + return err + } + w.WriteString("]") + case Ind: + w.WriteString(fmt.Sprintf("P[X+%v:", inst.K)) + if err := decodeLdSize(inst, w); err != nil { + return err + } + w.WriteString("]") + case Mem: + w.WriteString(fmt.Sprintf("M[%v]", inst.K)) + case Len: + w.WriteString("len") + default: + return fmt.Errorf("invalid BPF LD instruction: %v", inst) + } + return nil +} + +func decodeLdSize(inst linux.BPFInstruction, w *bytes.Buffer) error { + switch inst.OpCode & loadSizeMask { + case W: + w.WriteString("4") + case H: + w.WriteString("2") + case B: + w.WriteString("1") + default: + return fmt.Errorf("Invalid BPF LD size: %v", inst) + } + return nil +} + +// X <- P[k:4] +func decodeLdx(inst linux.BPFInstruction, w *bytes.Buffer) error { + w.WriteString("X <- ") + + switch inst.OpCode & loadModeMask { + case Imm: + w.WriteString(fmt.Sprintf("%v", inst.K)) + case Mem: + w.WriteString(fmt.Sprintf("M[%v]", inst.K)) + case Len: + w.WriteString("len") + case Msh: + w.WriteString(fmt.Sprintf("4*(P[%v:1]&0xf)", inst.K)) + default: + return fmt.Errorf("invalid BPF LDX instruction: %v", inst) + } + return nil +} + +// A <- A + k +func decodeAlu(inst linux.BPFInstruction, w *bytes.Buffer) error { + code := inst.OpCode & aluMask + if code == Neg { + w.WriteString("A <- -A") + return nil + } + + w.WriteString("A <- A ") + switch code { + case Add: + w.WriteString("+ ") + case Sub: + w.WriteString("- ") + case Mul: + w.WriteString("* ") + case Div: + w.WriteString("/ ") + case Or: + w.WriteString("| ") + case And: + w.WriteString("& ") + case Lsh: + w.WriteString("<< ") + case Rsh: + w.WriteString(">> ") + case Mod: + w.WriteString("% ") + case Xor: + w.WriteString("^ ") + default: + return fmt.Errorf("invalid BPF ALU instruction: %v", inst) + } + if err := decodeSource(inst, w); err != nil { + return err + } + return nil +} + +func decodeSource(inst linux.BPFInstruction, w *bytes.Buffer) error { + switch inst.OpCode & srcAluJmpMask { + case K: + w.WriteString(fmt.Sprintf("%v", inst.K)) + case X: + w.WriteString("X") + default: + return fmt.Errorf("invalid BPF ALU/JMP source instruction: %v", inst) + } + return nil +} + +// pc += (A > k) ? jt : jf +func decodeJmp(inst linux.BPFInstruction, line int, w *bytes.Buffer) error { + code := inst.OpCode & jmpMask + + w.WriteString("pc += ") + if code == Ja { + w.WriteString(printJmpTarget(inst.K, line)) + } else { + w.WriteString("(A ") + switch code { + case Jeq: + w.WriteString("== ") + case Jgt: + w.WriteString("> ") + case Jge: + w.WriteString(">= ") + case Jset: + w.WriteString("& ") + default: + return fmt.Errorf("invalid BPF ALU instruction: %v", inst) + } + if err := decodeSource(inst, w); err != nil { + return err + } + w.WriteString( + fmt.Sprintf(") ? %s : %s", + printJmpTarget(uint32(inst.JumpIfTrue), line), + printJmpTarget(uint32(inst.JumpIfFalse), line))) + } + return nil +} + +func printJmpTarget(target uint32, line int) string { + if line == -1 { + return fmt.Sprintf("%v", target) + } + return fmt.Sprintf("%v [%v]", target, int(target)+line+1) +} + +// ret k +func decodeRet(inst linux.BPFInstruction, w *bytes.Buffer) error { + w.WriteString("ret ") + + code := inst.OpCode & srcRetMask + switch code { + case K: + w.WriteString(fmt.Sprintf("%v", inst.K)) + case A: + w.WriteString("A") + default: + return fmt.Errorf("invalid BPF RET source instruction: %v", inst) + } + return nil +} + +func decodeMisc(inst linux.BPFInstruction, w *bytes.Buffer) error { + code := inst.OpCode & miscMask + switch code { + case Tax: + w.WriteString("X <- A") + case Txa: + w.WriteString("A <- X") + default: + return fmt.Errorf("invalid BPF ALU/JMP source instruction: %v", inst) + } + return nil +} diff --git a/pkg/bpf/decoder_test.go b/pkg/bpf/decoder_test.go new file mode 100644 index 000000000..18709b944 --- /dev/null +++ b/pkg/bpf/decoder_test.go @@ -0,0 +1,146 @@ +// Copyright 2018 Google Inc. +// +// 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 ( + "testing" + + "gvisor.googlesource.com/gvisor/pkg/abi/linux" +) + +func TestDecode(t *testing.T) { + for _, test := range []struct { + filter linux.BPFInstruction + expected string + fail bool + }{ + {filter: Stmt(Ld+Imm, 10), expected: "A <- 10"}, + {filter: Stmt(Ld+Abs+W, 10), expected: "A <- P[10:4]"}, + {filter: Stmt(Ld+Ind+H, 10), expected: "A <- P[X+10:2]"}, + {filter: Stmt(Ld+Ind+B, 10), expected: "A <- P[X+10:1]"}, + {filter: Stmt(Ld+Mem, 10), expected: "A <- M[10]"}, + {filter: Stmt(Ld+Len, 0), expected: "A <- len"}, + {filter: Stmt(Ldx+Imm, 10), expected: "X <- 10"}, + {filter: Stmt(Ldx+Mem, 10), expected: "X <- M[10]"}, + {filter: Stmt(Ldx+Len, 0), expected: "X <- len"}, + {filter: Stmt(Ldx+Msh, 10), expected: "X <- 4*(P[10:1]&0xf)"}, + {filter: Stmt(St, 10), expected: "M[10] <- A"}, + {filter: Stmt(Stx, 10), expected: "M[10] <- X"}, + {filter: Stmt(Alu+Add+K, 10), expected: "A <- A + 10"}, + {filter: Stmt(Alu+Sub+K, 10), expected: "A <- A - 10"}, + {filter: Stmt(Alu+Mul+K, 10), expected: "A <- A * 10"}, + {filter: Stmt(Alu+Div+K, 10), expected: "A <- A / 10"}, + {filter: Stmt(Alu+Or+K, 10), expected: "A <- A | 10"}, + {filter: Stmt(Alu+And+K, 10), expected: "A <- A & 10"}, + {filter: Stmt(Alu+Lsh+K, 10), expected: "A <- A << 10"}, + {filter: Stmt(Alu+Rsh+K, 10), expected: "A <- A >> 10"}, + {filter: Stmt(Alu+Mod+K, 10), expected: "A <- A % 10"}, + {filter: Stmt(Alu+Xor+K, 10), expected: "A <- A ^ 10"}, + {filter: Stmt(Alu+Add+X, 0), expected: "A <- A + X"}, + {filter: Stmt(Alu+Sub+X, 0), expected: "A <- A - X"}, + {filter: Stmt(Alu+Mul+X, 0), expected: "A <- A * X"}, + {filter: Stmt(Alu+Div+X, 0), expected: "A <- A / X"}, + {filter: Stmt(Alu+Or+X, 0), expected: "A <- A | X"}, + {filter: Stmt(Alu+And+X, 0), expected: "A <- A & X"}, + {filter: Stmt(Alu+Lsh+X, 0), expected: "A <- A << X"}, + {filter: Stmt(Alu+Rsh+X, 0), expected: "A <- A >> X"}, + {filter: Stmt(Alu+Mod+X, 0), expected: "A <- A % X"}, + {filter: Stmt(Alu+Xor+X, 0), expected: "A <- A ^ X"}, + {filter: Stmt(Alu+Neg, 0), expected: "A <- -A"}, + {filter: Stmt(Jmp+Ja, 10), expected: "pc += 10"}, + {filter: Jump(Jmp+Jeq+K, 10, 2, 5), expected: "pc += (A == 10) ? 2 : 5"}, + {filter: Jump(Jmp+Jgt+K, 10, 2, 5), expected: "pc += (A > 10) ? 2 : 5"}, + {filter: Jump(Jmp+Jge+K, 10, 2, 5), expected: "pc += (A >= 10) ? 2 : 5"}, + {filter: Jump(Jmp+Jset+K, 10, 2, 5), expected: "pc += (A & 10) ? 2 : 5"}, + {filter: Jump(Jmp+Jeq+X, 0, 2, 5), expected: "pc += (A == X) ? 2 : 5"}, + {filter: Jump(Jmp+Jgt+X, 0, 2, 5), expected: "pc += (A > X) ? 2 : 5"}, + {filter: Jump(Jmp+Jge+X, 0, 2, 5), expected: "pc += (A >= X) ? 2 : 5"}, + {filter: Jump(Jmp+Jset+X, 0, 2, 5), expected: "pc += (A & X) ? 2 : 5"}, + {filter: Stmt(Ret+K, 10), expected: "ret 10"}, + {filter: Stmt(Ret+A, 0), expected: "ret A"}, + {filter: Stmt(Misc+Tax, 0), expected: "X <- A"}, + {filter: Stmt(Misc+Txa, 0), expected: "A <- X"}, + {filter: Stmt(Ld+Ind+Msh, 0), fail: true}, + } { + got, err := Decode(test.filter) + if test.fail { + if err == nil { + t.Errorf("Decode(%v) failed, expected: 'error', got: %q", test.filter, got) + continue + } + } else { + if err != nil { + t.Errorf("Decode(%v) failed for test %q, error: %q", test.filter, test.expected, err) + continue + } + if got != test.expected { + t.Errorf("Decode(%v) failed, expected: %q, got: %q", test.filter, test.expected, got) + continue + } + } + } +} + +func TestDecodeProgram(t *testing.T) { + for _, test := range []struct { + name string + program []linux.BPFInstruction + expected string + fail bool + }{ + {name: "basic with jump indexes", + program: []linux.BPFInstruction{ + Stmt(Ld+Abs+W, 10), + Stmt(Ldx+Mem, 10), + Stmt(St, 10), + Stmt(Stx, 10), + Stmt(Alu+Add+K, 10), + Stmt(Jmp+Ja, 10), + Jump(Jmp+Jeq+K, 10, 2, 5), + Jump(Jmp+Jset+X, 0, 0, 5), + Stmt(Misc+Tax, 0), + }, + expected: "0: A <- P[10:4]\n" + + "1: X <- M[10]\n" + + "2: M[10] <- A\n" + + "3: M[10] <- X\n" + + "4: A <- A + 10\n" + + "5: pc += 10 [16]\n" + + "6: pc += (A == 10) ? 2 [9] : 5 [12]\n" + + "7: pc += (A & X) ? 0 [8] : 5 [13]\n" + + "8: X <- A\n", + }, + {name: "invalid instruction", + program: []linux.BPFInstruction{Stmt(Ld+Abs+W, 10), Stmt(Ld+Len+Mem, 0)}, + fail: true}, + } { + got, err := DecodeProgram(test.program) + if test.fail { + if err == nil { + t.Errorf("%s: Decode(...) failed, expected: 'error', got: %q", test.name, got) + continue + } + } else { + if err != nil { + t.Errorf("%s: Decode failed: %v", test.name, err) + continue + } + if got != test.expected { + t.Errorf("%s: Decode(...) failed, expected: %q, got: %q", test.name, test.expected, got) + continue + } + } + } +} diff --git a/pkg/bpf/input_bytes.go b/pkg/bpf/input_bytes.go new file mode 100644 index 000000000..74af038eb --- /dev/null +++ b/pkg/bpf/input_bytes.go @@ -0,0 +1,58 @@ +// Copyright 2018 Google Inc. +// +// 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 ( + "encoding/binary" +) + +// InputBytes implements the Input interface by providing access to a byte +// slice. Unaligned loads are supported. +type InputBytes struct { + // Data is the data accessed through the Input interface. + Data []byte + + // Order is the byte order the data is accessed with. + Order binary.ByteOrder +} + +// Load32 implements Input.Load32. +func (i InputBytes) Load32(off uint32) (uint32, bool) { + if uint64(off)+4 > uint64(len(i.Data)) { + return 0, false + } + return i.Order.Uint32(i.Data[int(off):]), true +} + +// Load16 implements Input.Load16. +func (i InputBytes) Load16(off uint32) (uint16, bool) { + if uint64(off)+2 > uint64(len(i.Data)) { + return 0, false + } + return i.Order.Uint16(i.Data[int(off):]), true +} + +// Load8 implements Input.Load8. +func (i InputBytes) Load8(off uint32) (uint8, bool) { + if uint64(off)+1 > uint64(len(i.Data)) { + return 0, false + } + return i.Data[int(off)], true +} + +// Length implements Input.Length. +func (i InputBytes) Length() uint32 { + return uint32(len(i.Data)) +} diff --git a/pkg/bpf/interpreter.go b/pkg/bpf/interpreter.go new file mode 100644 index 000000000..b7dee86a8 --- /dev/null +++ b/pkg/bpf/interpreter.go @@ -0,0 +1,410 @@ +// Copyright 2018 Google Inc. +// +// 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. +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} +} diff --git a/pkg/bpf/interpreter_test.go b/pkg/bpf/interpreter_test.go new file mode 100644 index 000000000..9e5e33228 --- /dev/null +++ b/pkg/bpf/interpreter_test.go @@ -0,0 +1,797 @@ +// Copyright 2018 Google Inc. +// +// 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 ( + "testing" + + "gvisor.googlesource.com/gvisor/pkg/abi/linux" + "gvisor.googlesource.com/gvisor/pkg/binary" +) + +func TestCompilationErrors(t *testing.T) { + for _, test := range []struct { + // desc is the test's description. + desc string + + // insns is the BPF instructions to be compiled. + insns []linux.BPFInstruction + + // expectedErr is the expected compilation error. + expectedErr error + }{ + { + desc: "Instructions must not be nil", + expectedErr: Error{InvalidInstructionCount, 0}, + }, + { + desc: "Instructions must not be empty", + insns: []linux.BPFInstruction{}, + expectedErr: Error{InvalidInstructionCount, 0}, + }, + { + desc: "A program must end with a return", + insns: make([]linux.BPFInstruction, MaxInstructions), + expectedErr: Error{InvalidEndOfProgram, MaxInstructions - 1}, + }, + { + desc: "A program must have MaxInstructions or fewer instructions", + insns: append(make([]linux.BPFInstruction, MaxInstructions), Stmt(Ret|K, 0)), + expectedErr: Error{InvalidInstructionCount, MaxInstructions + 1}, + }, + { + desc: "A load from an invalid M register is a compilation error", + insns: []linux.BPFInstruction{ + Stmt(Ld|Mem|W, ScratchMemRegisters), // A = M[16] + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{InvalidRegister, 0}, + }, + { + desc: "A store to an invalid M register is a compilation error", + insns: []linux.BPFInstruction{ + Stmt(St, ScratchMemRegisters), // M[16] = A + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{InvalidRegister, 0}, + }, + { + desc: "Division by literal zero is a compilation error", + insns: []linux.BPFInstruction{ + Stmt(Alu|Div|K, 0), // A /= 0 + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{DivisionByZero, 0}, + }, + { + desc: "An unconditional jump outside of the program is a compilation error", + insns: []linux.BPFInstruction{ + Jump(Jmp|Ja, 1, 0, 0), // jmp nextpc+1 + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{InvalidJumpTarget, 0}, + }, + { + desc: "A conditional jump outside of the program in the true case is a compilation error", + insns: []linux.BPFInstruction{ + Jump(Jmp|Jeq|K, 0, 1, 0), // if (A == K) jmp nextpc+1 + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{InvalidJumpTarget, 0}, + }, + { + desc: "A conditional jump outside of the program in the false case is a compilation error", + insns: []linux.BPFInstruction{ + Jump(Jmp|Jeq|K, 0, 0, 1), // if (A != K) jmp nextpc+1 + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{InvalidJumpTarget, 0}, + }, + } { + _, err := Compile(test.insns) + if err != test.expectedErr { + t.Errorf("%s: expected error %q, got error %q", test.desc, test.expectedErr, err) + } + } +} + +func TestExecErrors(t *testing.T) { + for _, test := range []struct { + // desc is the test's description. + desc string + + // insns is the BPF instructions to be executed. + insns []linux.BPFInstruction + + // expectedErr is the expected execution error. + expectedErr error + }{ + { + desc: "An out-of-bounds load of input data is an execution error", + insns: []linux.BPFInstruction{ + Stmt(Ld|Abs|B, 0), // A = input[0] + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{InvalidLoad, 0}, + }, + { + desc: "Division by zero at runtime is an execution error", + insns: []linux.BPFInstruction{ + Stmt(Alu|Div|X, 0), // A /= X + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{DivisionByZero, 0}, + }, + { + desc: "Modulo zero at runtime is an execution error", + insns: []linux.BPFInstruction{ + Stmt(Alu|Mod|X, 0), // A %= X + Stmt(Ret|K, 0), // return 0 + }, + expectedErr: Error{DivisionByZero, 0}, + }, + } { + p, err := Compile(test.insns) + if err != nil { + t.Errorf("%s: unexpected compilation error: %v", test.desc, err) + continue + } + ret, err := Exec(p, InputBytes{nil, binary.BigEndian}) + if err != test.expectedErr { + t.Errorf("%s: expected execution error %q, got (%d, %v)", test.desc, test.expectedErr, ret, err) + } + } +} + +func TestValidInstructions(t *testing.T) { + for _, test := range []struct { + // desc is the test's description. + desc string + + // insns is the BPF instructions to be compiled. + insns []linux.BPFInstruction + + // input is the input data. Note that input will be read as big-endian. + input []byte + + // expectedRet is the expected return value of the BPF program. + expectedRet uint32 + }{ + { + desc: "Return of immediate", + insns: []linux.BPFInstruction{ + Stmt(Ret|K, 42), // return 42 + }, + expectedRet: 42, + }, + { + desc: "Load of immediate into A", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 42), // A = 42 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 42, + }, + { + desc: "Load of immediate into X and copying of X into A", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Imm|W, 42), // X = 42 + Stmt(Misc|Tax, 0), // A = X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 42, + }, + { + desc: "Copying of A into X and back", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 42), // A = 42 + Stmt(Misc|Txa, 0), // X = A + Stmt(Ld|Imm|W, 0), // A = 0 + Stmt(Misc|Tax, 0), // A = X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 42, + }, + { + desc: "Load of 32-bit input by absolute offset into A", + insns: []linux.BPFInstruction{ + Stmt(Ld|Abs|W, 1), // A = input[1..4] + Stmt(Ret|A, 0), // return A + }, + input: []byte{0x00, 0x11, 0x22, 0x33, 0x44}, + expectedRet: 0x11223344, + }, + { + desc: "Load of 16-bit input by absolute offset into A", + insns: []linux.BPFInstruction{ + Stmt(Ld|Abs|H, 1), // A = input[1..2] + Stmt(Ret|A, 0), // return A + }, + input: []byte{0x00, 0x11, 0x22}, + expectedRet: 0x1122, + }, + { + desc: "Load of 8-bit input by absolute offset into A", + insns: []linux.BPFInstruction{ + Stmt(Ld|Abs|B, 1), // A = input[1] + Stmt(Ret|A, 0), // return A + }, + input: []byte{0x00, 0x11}, + expectedRet: 0x11, + }, + { + desc: "Load of 32-bit input by relative offset into A", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Imm|W, 1), // X = 1 + Stmt(Ld|Ind|W, 1), // A = input[X+1..X+4] + Stmt(Ret|A, 0), // return A + }, + input: []byte{0x00, 0x11, 0x22, 0x33, 0x44, 0x55}, + expectedRet: 0x22334455, + }, + { + desc: "Load of 16-bit input by relative offset into A", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Imm|W, 1), // X = 1 + Stmt(Ld|Ind|H, 1), // A = input[X+1..X+2] + Stmt(Ret|A, 0), // return A + }, + input: []byte{0x00, 0x11, 0x22, 0x33}, + expectedRet: 0x2233, + }, + { + desc: "Load of 8-bit input by relative offset into A", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Imm|W, 1), // X = 1 + Stmt(Ld|Ind|B, 1), // A = input[X+1] + Stmt(Ret|A, 0), // return A + }, + input: []byte{0x00, 0x11, 0x22}, + expectedRet: 0x22, + }, + { + desc: "Load/store between A and scratch memory", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 42), // A = 42 + Stmt(St, 2), // M[2] = A + Stmt(Ld|Imm|W, 0), // A = 0 + Stmt(Ld|Mem|W, 2), // A = M[2] + Stmt(Ret|A, 0), // return A + }, + expectedRet: 42, + }, + { + desc: "Load/store between X and scratch memory", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Imm|W, 42), // X = 42 + Stmt(Stx, 3), // M[3] = X + Stmt(Ldx|Imm|W, 0), // X = 0 + Stmt(Ldx|Mem|W, 3), // X = M[3] + Stmt(Misc|Tax, 0), // A = X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 42, + }, + { + desc: "Load of input length into A", + insns: []linux.BPFInstruction{ + Stmt(Ld|Len|W, 0), // A = len(input) + Stmt(Ret|A, 0), // return A + }, + input: []byte{1, 2, 3}, + expectedRet: 3, + }, + { + desc: "Load of input length into X", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Len|W, 0), // X = len(input) + Stmt(Misc|Tax, 0), // A = X + Stmt(Ret|A, 0), // return A + }, + input: []byte{1, 2, 3}, + expectedRet: 3, + }, + { + desc: "Load of MSH (?) into X", + insns: []linux.BPFInstruction{ + Stmt(Ldx|Msh|B, 0), // X = 4*(input[0]&0xf) + Stmt(Misc|Tax, 0), // A = X + Stmt(Ret|A, 0), // return A + }, + input: []byte{0xf1}, + expectedRet: 4, + }, + { + desc: "Addition of immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Stmt(Alu|Add|K, 20), // A += 20 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 30, + }, + { + desc: "Addition of X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Stmt(Ldx|Imm|W, 20), // X = 20 + Stmt(Alu|Add|X, 0), // A += X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 30, + }, + { + desc: "Subtraction of immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 30), // A = 30 + Stmt(Alu|Sub|K, 20), // A -= 20 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 10, + }, + { + desc: "Subtraction of X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 30), // A = 30 + Stmt(Ldx|Imm|W, 20), // X = 20 + Stmt(Alu|Sub|X, 0), // A -= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 10, + }, + { + desc: "Multiplication of immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 2), // A = 2 + Stmt(Alu|Mul|K, 3), // A *= 3 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 6, + }, + { + desc: "Multiplication of X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 2), // A = 2 + Stmt(Ldx|Imm|W, 3), // X = 3 + Stmt(Alu|Mul|X, 0), // A *= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 6, + }, + { + desc: "Division by immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 6), // A = 6 + Stmt(Alu|Div|K, 3), // A /= 3 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 2, + }, + { + desc: "Division by X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 6), // A = 6 + Stmt(Ldx|Imm|W, 3), // X = 3 + Stmt(Alu|Div|X, 0), // A /= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 2, + }, + { + desc: "Modulo immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 17), // A = 17 + Stmt(Alu|Mod|K, 7), // A %= 7 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 3, + }, + { + desc: "Modulo X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 17), // A = 17 + Stmt(Ldx|Imm|W, 7), // X = 7 + Stmt(Alu|Mod|X, 0), // A %= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 3, + }, + { + desc: "Arithmetic negation", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 1), // A = 1 + Stmt(Alu|Neg, 0), // A = -A + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0xffffffff, + }, + { + desc: "Bitwise OR with immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55 + Stmt(Alu|Or|K, 0xff0055aa), // A |= 0xff0055aa + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0xff00ffff, + }, + { + desc: "Bitwise OR with X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55 + Stmt(Ldx|Imm|W, 0xff0055aa), // X = 0xff0055aa + Stmt(Alu|Or|X, 0), // A |= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0xff00ffff, + }, + { + desc: "Bitwise AND with immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55 + Stmt(Alu|And|K, 0xff0055aa), // A &= 0xff0055aa + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0xff000000, + }, + { + desc: "Bitwise AND with X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55 + Stmt(Ldx|Imm|W, 0xff0055aa), // X = 0xff0055aa + Stmt(Alu|And|X, 0), // A &= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0xff000000, + }, + { + desc: "Bitwise XOR with immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55 + Stmt(Alu|Xor|K, 0xff0055aa), // A ^= 0xff0055aa + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0x0000ffff, + }, + { + desc: "Bitwise XOR with X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55 + Stmt(Ldx|Imm|W, 0xff0055aa), // X = 0xff0055aa + Stmt(Alu|Xor|X, 0), // A ^= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 0x0000ffff, + }, + { + desc: "Left shift by immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 1), // A = 1 + Stmt(Alu|Lsh|K, 5), // A <<= 5 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 32, + }, + { + desc: "Left shift by X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 1), // A = 1 + Stmt(Ldx|Imm|W, 5), // X = 5 + Stmt(Alu|Lsh|X, 0), // A <<= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 32, + }, + { + desc: "Right shift by immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xffffffff), // A = 0xffffffff + Stmt(Alu|Rsh|K, 31), // A >>= 31 + Stmt(Ret|A, 0), // return A + }, + expectedRet: 1, + }, + { + desc: "Right shift by X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xffffffff), // A = 0xffffffff + Stmt(Ldx|Imm|W, 31), // X = 31 + Stmt(Alu|Rsh|X, 0), // A >>= X + Stmt(Ret|A, 0), // return A + }, + expectedRet: 1, + }, + { + desc: "Unconditional jump", + insns: []linux.BPFInstruction{ + Jump(Jmp|Ja, 1, 0, 0), // jmp nextpc+1 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + }, + expectedRet: 1, + }, + { + desc: "Jump when A == immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 42), // A = 42 + Jump(Jmp|Jeq|K, 42, 1, 2), // if (A == 42) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A != immediate", + insns: []linux.BPFInstruction{ + Jump(Jmp|Jeq|K, 42, 1, 2), // if (A == 42) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A == X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 42), // A = 42 + Stmt(Ldx|Imm|W, 42), // X = 42 + Jump(Jmp|Jeq|X, 0, 1, 2), // if (A == X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A != X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 42), // A = 42 + Jump(Jmp|Jeq|X, 0, 1, 2), // if (A == X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A > immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Jump(Jmp|Jgt|K, 9, 1, 2), // if (A > 9) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A <= immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Jump(Jmp|Jgt|K, 10, 1, 2), // if (A > 10) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A > X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Stmt(Ldx|Imm|W, 9), // X = 9 + Jump(Jmp|Jgt|X, 0, 1, 2), // if (A > X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A <= X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Stmt(Ldx|Imm|W, 10), // X = 10 + Jump(Jmp|Jgt|X, 0, 1, 2), // if (A > X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A >= immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Jump(Jmp|Jge|K, 10, 1, 2), // if (A >= 10) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A < immediate", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Jump(Jmp|Jge|K, 11, 1, 2), // if (A >= 11) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A >= X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Stmt(Ldx|Imm|W, 10), // X = 10 + Jump(Jmp|Jge|X, 0, 1, 2), // if (A >= X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A < X", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 10), // A = 10 + Stmt(Ldx|Imm|W, 11), // X = 11 + Jump(Jmp|Jge|X, 0, 1, 2), // if (A >= X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A & immediate != 0", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff), // A = 0xff + Jump(Jmp|Jset|K, 0x101, 1, 2), // if (A & 0x101) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A & immediate == 0", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xfe), // A = 0xfe + Jump(Jmp|Jset|K, 0x101, 1, 2), // if (A & 0x101) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + { + desc: "Jump when A & X != 0", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xff), // A = 0xff + Stmt(Ldx|Imm|W, 0x101), // X = 0x101 + Jump(Jmp|Jset|X, 0, 1, 2), // if (A & X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 1, + }, + { + desc: "Jump when A & X == 0", + insns: []linux.BPFInstruction{ + Stmt(Ld|Imm|W, 0xfe), // A = 0xfe + Stmt(Ldx|Imm|W, 0x101), // X = 0x101 + Jump(Jmp|Jset|X, 0, 1, 2), // if (A & X) jmp nextpc+1 else jmp nextpc+2 + Stmt(Ret|K, 0), // return 0 + Stmt(Ret|K, 1), // return 1 + Stmt(Ret|K, 2), // return 2 + }, + expectedRet: 2, + }, + } { + p, err := Compile(test.insns) + if err != nil { + t.Errorf("%s: unexpected compilation error: %v", test.desc, err) + continue + } + ret, err := Exec(p, InputBytes{test.input, binary.BigEndian}) + if err != nil { + t.Errorf("%s: expected return value of %d, got execution error: %v", test.desc, test.expectedRet, err) + continue + } + if ret != test.expectedRet { + t.Errorf("%s: expected return value of %d, got value %d", test.desc, test.expectedRet, ret) + } + } +} + +func TestSimpleFilter(t *testing.T) { + // Seccomp filter example given in Linux's + // Documentation/networking/filter.txt, translated to bytecode using the + // Linux kernel tree's tools/net/bpf_asm. + filter := []linux.BPFInstruction{ + {0x20, 0, 0, 0x00000004}, // ld [4] /* offsetof(struct seccomp_data, arch) */ + {0x15, 0, 11, 0xc000003e}, // jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */ + {0x20, 0, 0, 0000000000}, // ld [0] /* offsetof(struct seccomp_data, nr) */ + {0x15, 10, 0, 0x0000000f}, // jeq #15, good /* __NR_rt_sigreturn */ + {0x15, 9, 0, 0x000000e7}, // jeq #231, good /* __NR_exit_group */ + {0x15, 8, 0, 0x0000003c}, // jeq #60, good /* __NR_exit */ + {0x15, 7, 0, 0000000000}, // jeq #0, good /* __NR_read */ + {0x15, 6, 0, 0x00000001}, // jeq #1, good /* __NR_write */ + {0x15, 5, 0, 0x00000005}, // jeq #5, good /* __NR_fstat */ + {0x15, 4, 0, 0x00000009}, // jeq #9, good /* __NR_mmap */ + {0x15, 3, 0, 0x0000000e}, // jeq #14, good /* __NR_rt_sigprocmask */ + {0x15, 2, 0, 0x0000000d}, // jeq #13, good /* __NR_rt_sigaction */ + {0x15, 1, 0, 0x00000023}, // jeq #35, good /* __NR_nanosleep */ + {0x06, 0, 0, 0000000000}, // bad: ret #0 /* SECCOMP_RET_KILL */ + {0x06, 0, 0, 0x7fff0000}, // good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */ + } + p, err := Compile(filter) + if err != nil { + t.Fatalf("Unexpected compilation error: %v", err) + } + + for _, test := range []struct { + // desc is the test's description. + desc string + + // seccompData is the input data. + seccompData + + // expectedRet is the expected return value of the BPF program. + expectedRet uint32 + }{ + { + desc: "Invalid arch is rejected", + seccompData: seccompData{nr: 1 /* x86 exit */, arch: 0x40000003 /* AUDIT_ARCH_I386 */}, + expectedRet: 0, + }, + { + desc: "Disallowed syscall is rejected", + seccompData: seccompData{nr: 105 /* __NR_setuid */, arch: 0xc000003e}, + expectedRet: 0, + }, + { + desc: "Whitelisted syscall is allowed", + seccompData: seccompData{nr: 231 /* __NR_exit_group */, arch: 0xc000003e}, + expectedRet: 0x7fff0000, + }, + } { + ret, err := Exec(p, test.seccompData.asInput()) + if err != nil { + t.Errorf("%s: expected return value of %d, got execution error: %v", test.desc, test.expectedRet, err) + continue + } + if ret != test.expectedRet { + t.Errorf("%s: expected return value of %d, got value %d", test.desc, test.expectedRet, ret) + } + } +} + +// seccompData is equivalent to struct seccomp_data. +type seccompData struct { + nr uint32 + arch uint32 + instructionPointer uint64 + args [6]uint64 +} + +// asInput converts a seccompData to a bpf.Input. +func (d *seccompData) asInput() Input { + return InputBytes{binary.Marshal(nil, binary.LittleEndian, d), binary.LittleEndian} +} diff --git a/pkg/bpf/program_builder.go b/pkg/bpf/program_builder.go new file mode 100644 index 000000000..7554d47c1 --- /dev/null +++ b/pkg/bpf/program_builder.go @@ -0,0 +1,159 @@ +// Copyright 2018 Google Inc. +// +// 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" + "math" + + "gvisor.googlesource.com/gvisor/pkg/abi/linux" +) + +const labelTarget = math.MaxUint8 + +// ProgramBuilder assists with building a BPF program with jump +// labels that are resolved to their proper offsets. +type ProgramBuilder struct { + // Maps label names to label objects. + labels map[string]*label + + // Array of BPF instructions that makes up the program. + instructions []linux.BPFInstruction +} + +// NewProgramBuilder creates a new ProgramBuilder instance. +func NewProgramBuilder() *ProgramBuilder { + return &ProgramBuilder{labels: map[string]*label{}} +} + +// label contains information to resolve a label to an offset. +type label struct { + // List of locations that reference the label in the program. + sources []source + + // Program line when the label is located. + target int +} + +// source contains information about a single reference to a label. +type source struct { + // Program line where the label reference is present. + line int + + // True if label reference is in the 'jump if true' part of the jump. + // False if label reference is in the 'jump if false' part of the jump. + jt bool +} + +// AddStmt adds a new statement to the program. +func (b *ProgramBuilder) AddStmt(code uint16, k uint32) { + b.instructions = append(b.instructions, Stmt(code, k)) +} + +// AddJump adds a new jump to the program. +func (b *ProgramBuilder) AddJump(code uint16, k uint32, jt, jf uint8) { + b.instructions = append(b.instructions, Jump(code, k, jt, jf)) +} + +// AddJumpTrueLabel adds a new jump to the program where 'jump if true' is a label. +func (b *ProgramBuilder) AddJumpTrueLabel(code uint16, k uint32, jtLabel string, jf uint8) { + b.addLabelSource(jtLabel, true) + b.AddJump(code, k, labelTarget, jf) +} + +// AddJumpFalseLabel adds a new jump to the program where 'jump if false' is a label. +func (b *ProgramBuilder) AddJumpFalseLabel(code uint16, k uint32, jt uint8, jfLabel string) { + b.addLabelSource(jfLabel, false) + b.AddJump(code, k, jt, math.MaxUint8) +} + +// AddJumpLabels adds a new jump to the program where both jump targets are labels. +func (b *ProgramBuilder) AddJumpLabels(code uint16, k uint32, jtLabel, jfLabel string) { + b.addLabelSource(jtLabel, true) + b.addLabelSource(jfLabel, false) + b.AddJump(code, k, math.MaxUint8, math.MaxUint8) +} + +// AddLabel sets the given label name at the current location. The next instruction is executed +// when the any code jumps to this label. More than one label can be added to the same location. +func (b *ProgramBuilder) AddLabel(name string) error { + l, ok := b.labels[name] + if !ok { + // This is done to catch jump backwards cases, but it's not strictly wrong + // to have unused labels. + return fmt.Errorf("Adding a label that hasn't been used is not allowed: %v", name) + } + if l.target != -1 { + return fmt.Errorf("label %q target already set: %v", name, l.target) + } + l.target = len(b.instructions) + return nil +} + +// Instructions returns an array of BPF instructions representing the program with all labels +// resolved. Return error in case label resolution failed due to an invalid program. +func (b *ProgramBuilder) Instructions() ([]linux.BPFInstruction, error) { + if err := b.resolveLabels(); err != nil { + return nil, err + } + return b.instructions, nil +} + +func (b *ProgramBuilder) addLabelSource(labelName string, jt bool) { + l, ok := b.labels[labelName] + if !ok { + l = &label{sources: make([]source, 0), target: -1} + b.labels[labelName] = l + } + l.sources = append(l.sources, source{line: len(b.instructions), jt: jt}) +} + +func (b *ProgramBuilder) resolveLabels() error { + for key, v := range b.labels { + if v.target == -1 { + return fmt.Errorf("label target not set: %v", key) + } + if v.target >= len(b.instructions) { + return fmt.Errorf("target is beyond end of ProgramBuilder") + } + for _, s := range v.sources { + // Finds jump instruction that references the label. + inst := b.instructions[s.line] + if s.line >= v.target { + return fmt.Errorf("cannot jump backwards") + } + // Calculates the jump offset from current line. + offset := v.target - s.line - 1 + if offset > math.MaxUint8 { + return fmt.Errorf("jump offset to label '%v' is too large: %v", key, offset) + } + // Sets offset into jump instruction. + if s.jt { + if inst.JumpIfTrue != labelTarget { + return fmt.Errorf("jump target is not a label") + } + inst.JumpIfTrue = uint8(offset) + } else { + if inst.JumpIfFalse != labelTarget { + return fmt.Errorf("jump target is not a label") + } + inst.JumpIfFalse = uint8(offset) + } + b.instructions[s.line] = inst + } + } + b.labels = map[string]*label{} + return nil +} diff --git a/pkg/bpf/program_builder_test.go b/pkg/bpf/program_builder_test.go new file mode 100644 index 000000000..7e4f06584 --- /dev/null +++ b/pkg/bpf/program_builder_test.go @@ -0,0 +1,157 @@ +// Copyright 2018 Google Inc. +// +// 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" + "testing" + + "gvisor.googlesource.com/gvisor/pkg/abi/linux" +) + +func validate(p *ProgramBuilder, expected []linux.BPFInstruction) error { + instructions, err := p.Instructions() + if err != nil { + return fmt.Errorf("Instructions() failed: %v", err) + } + got, err := DecodeProgram(instructions) + if err != nil { + return fmt.Errorf("DecodeProgram('instructions') failed: %v", err) + } + expectedDecoded, err := DecodeProgram(expected) + if err != nil { + return fmt.Errorf("DecodeProgram('expected') failed: %v", err) + } + if got != expectedDecoded { + return fmt.Errorf("DecodeProgram() failed, expected: %q, got: %q", expectedDecoded, got) + } + return nil +} + +func TestProgramBuilderSimple(t *testing.T) { + p := NewProgramBuilder() + p.AddStmt(Ld+Abs+W, 10) + p.AddJump(Jmp+Ja, 10, 0, 0) + + expected := []linux.BPFInstruction{ + Stmt(Ld+Abs+W, 10), + Jump(Jmp+Ja, 10, 0, 0), + } + + if err := validate(p, expected); err != nil { + t.Errorf("Validate() failed: %v", err) + } +} + +func TestProgramBuilderLabels(t *testing.T) { + p := NewProgramBuilder() + p.AddJumpTrueLabel(Jmp+Jeq+K, 11, "label_1", 0) + p.AddJumpFalseLabel(Jmp+Jeq+K, 12, 0, "label_2") + p.AddJumpLabels(Jmp+Jeq+K, 13, "label_3", "label_4") + if err := p.AddLabel("label_1"); err != nil { + t.Errorf("AddLabel(label_1) failed: %v", err) + } + p.AddStmt(Ld+Abs+W, 1) + if err := p.AddLabel("label_3"); err != nil { + t.Errorf("AddLabel(label_3) failed: %v", err) + } + p.AddJumpLabels(Jmp+Jeq+K, 14, "label_4", "label_5") + if err := p.AddLabel("label_2"); err != nil { + t.Errorf("AddLabel(label_2) failed: %v", err) + } + p.AddJumpLabels(Jmp+Jeq+K, 15, "label_4", "label_6") + if err := p.AddLabel("label_4"); err != nil { + t.Errorf("AddLabel(label_4) failed: %v", err) + } + p.AddStmt(Ld+Abs+W, 4) + if err := p.AddLabel("label_5"); err != nil { + t.Errorf("AddLabel(label_5) failed: %v", err) + } + if err := p.AddLabel("label_6"); err != nil { + t.Errorf("AddLabel(label_6) failed: %v", err) + } + p.AddStmt(Ld+Abs+W, 5) + + expected := []linux.BPFInstruction{ + Jump(Jmp+Jeq+K, 11, 2, 0), + Jump(Jmp+Jeq+K, 12, 0, 3), + Jump(Jmp+Jeq+K, 13, 1, 3), + Stmt(Ld+Abs+W, 1), + Jump(Jmp+Jeq+K, 14, 1, 2), + Jump(Jmp+Jeq+K, 15, 0, 1), + Stmt(Ld+Abs+W, 4), + Stmt(Ld+Abs+W, 5), + } + if err := validate(p, expected); err != nil { + t.Errorf("Validate() failed: %v", err) + } + // Calling validate()=>p.Instructions() again to make sure + // Instructions can be called multiple times without ruining + // the program. + if err := validate(p, expected); err != nil { + t.Errorf("Validate() failed: %v", err) + } +} + +func TestProgramBuilderMissingErrorTarget(t *testing.T) { + p := NewProgramBuilder() + p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0) + if _, err := p.Instructions(); err == nil { + t.Errorf("Instructions() should have failed") + } +} + +func TestProgramBuilderLabelWithNoInstruction(t *testing.T) { + p := NewProgramBuilder() + p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0) + if err := p.AddLabel("label_1"); err != nil { + t.Errorf("AddLabel(label_1) failed: %v", err) + } + if _, err := p.Instructions(); err == nil { + t.Errorf("Instructions() should have failed") + } +} + +func TestProgramBuilderUnusedLabel(t *testing.T) { + p := NewProgramBuilder() + if err := p.AddLabel("unused"); err == nil { + t.Errorf("AddLabel(unused) should have failed") + } +} + +func TestProgramBuilderLabelAddedTwice(t *testing.T) { + p := NewProgramBuilder() + p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0) + if err := p.AddLabel("label_1"); err != nil { + t.Errorf("AddLabel(label_1) failed: %v", err) + } + p.AddStmt(Ld+Abs+W, 0) + if err := p.AddLabel("label_1"); err == nil { + t.Errorf("AddLabel(label_1) failed: %v", err) + } +} + +func TestProgramBuilderJumpBackwards(t *testing.T) { + p := NewProgramBuilder() + p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0) + if err := p.AddLabel("label_1"); err != nil { + t.Errorf("AddLabel(label_1) failed: %v", err) + } + p.AddStmt(Ld+Abs+W, 0) + p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0) + if _, err := p.Instructions(); err == nil { + t.Errorf("Instructions() should have failed") + } +} |