Extended Berkeley Packet Filter (eBPF) assembler and virtual machine
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

460 lines
12 KiB

//go:generate antlr -package parser -Dlanguage=Go -visitor internal/parser/Assembler.g4
package ebpf
import (
"fmt"
"log"
"strconv"
"strings"
"github.com/antlr/antlr4/runtime/Go/antlr"
"maze.io/x/ebpf/internal/parser"
)
// Program is a sequence of instructions.
type Program []Instruction
func (p Program) Assemble() ([]RawInstruction, error) {
var (
ret = make([]RawInstruction, len(p))
err error
)
for i, ri := range p {
if ret[i], err = ri.Assemble(); err != nil {
return nil, fmt.Errorf("ebpf: assembling instruction %d: %w", i+1, err)
}
}
return ret, nil
}
func (p Program) Verify() error {
// TODO
return nil
}
// Assemble a program from source.
func Assemble(source string) (Program, error) {
var (
input = antlr.NewInputStream(source)
lexer = parser.NewAssemblerLexer(input)
stream = antlr.NewCommonTokenStream(lexer, 0)
parse = parser.NewAssemblerParser(stream)
)
parse.BuildParseTrees = true
asm := new(assembler)
asm.parser = parse
result := asm.Visit(parse.Program()).([]interface{})
log.Printf("result: %#+v", result)
if result[1] == nil {
return result[0].([]Instruction), nil
}
return nil, result[1].(error)
}
type assembler struct {
*antlr.BaseParseTreeVisitor
parser *parser.AssemblerParser
}
func (asm *assembler) Visit(tree antlr.ParseTree) interface{} {
log.Printf("visit: %#+v", tree)
return tree.Accept(asm)
}
func (asm *assembler) VisitChildren(node antlr.RuleNode) interface{} {
log.Printf("visit children: %#+v", node)
var results []interface{}
for _, child := range node.GetChildren() {
log.Printf(" -> %T: %#+v", child, child)
switch child := child.(type) {
case *antlr.ErrorNodeImpl:
log.Printf(" -> invalid token %q", child.GetText())
//results = append(results, fmt.Errorf("invalid token %q", child.GetText()))
return []interface{}{nil, fmt.Errorf("invalid token %q", child.GetText())}
default:
instruction := child.(antlr.ParseTree).Accept(asm)
if instruction != nil {
log.Printf(" -> instruction %T: %#+v", instruction, instruction)
results = append(results, instruction)
}
}
}
return results
}
func (asm *assembler) VisitTerminal(node antlr.TerminalNode) interface{} {
//ctx := asm.parser.GetParserRuleContext()
log.Println("consume ", node.GetText()) // + " rule " + asm.parser.GetRuleNames()[ctx.GetRuleIndex()])
return nil
}
func (asm *assembler) VisitProgram(ctx *parser.ProgramContext) interface{} {
log.Printf("visit program: %#+v", ctx)
var (
program []interface{}
labelAddresses = map[string]uint32{}
results = asm.VisitChildren(ctx)
)
for _, result := range results.([]interface{}) {
switch result := result.(type) {
case string:
labelAddresses[result] = uint32(len(program))
//log.Printf("label %q at %d", result, labelAddresses[result])
case []interface{}:
for _, word := range result {
switch word := word.(type) {
case string:
labelAddresses[word] = uint32(len(program))
default:
program = append(program, word)
}
}
case error:
return []interface{}{nil, result}
default:
program = append(program, result)
}
}
/*
resolveLabelAddress := func(i int, label string) (skip uint8, err error) {
if addr, ok := labelAddresses[label]; ok {
// log.Printf("label %q at %d -> %d", label, addr, addr-uint32(i)-1)
if addr < uint32(i) {
return 0, fmt.Errorf("instruction %d: jump to negative offset label %q", i, label)
}
return uint8(addr - uint32(i) - 1), nil
}
return 0, fmt.Errorf("instruction %d: jump to unresolved label %q", i, label)
}
*/
var instructions []Instruction
for i, word := range program {
log.Printf("program: %T: %+v", word, word)
switch word := word.(type) {
case Instruction:
instructions = append(instructions, word)
/*
case conditionalJump:
switch skip := word.skipTrue.(type) {
case uint8:
word.Instruction.SkipTrue = skip
case string:
addr, err := resolveLabelAddress(i, skip)
if err != nil {
return []interface{}{nil, err}
}
word.Instruction.SkipFalse = addr
default:
return []interface{}{nil, fmt.Errorf("instruction %d: invalid jump true %T", i, skip)}
}
switch skip := word.skipFalse.(type) {
case uint8:
word.Instruction.SkipFalse = skip
case string:
addr, err := resolveLabelAddress(i, skip)
if err != nil {
return []interface{}{nil, err}
}
word.Instruction.SkipFalse = addr
}
instructions = append(instructions, word.Instruction)
case conditionalJumpX:
switch skip := word.skipTrue.(type) {
case uint8:
word.Instruction.SkipTrue = skip
case string:
addr, err := resolveLabelAddress(i, skip)
if err != nil {
return []interface{}{nil, err}
}
word.Instruction.SkipFalse = addr
}
switch skip := word.skipFalse.(type) {
case uint8:
word.Instruction.SkipFalse = skip
case string:
addr, err := resolveLabelAddress(i, skip)
if err != nil {
return []interface{}{nil, err}
}
word.Instruction.SkipFalse = addr
}
instructions = append(instructions, word.Instruction)
*/
default:
return []interface{}{nil, fmt.Errorf("instruction %d: unknown type %T", i, word)}
}
}
return []interface{}{instructions, nil}
}
func (asm *assembler) VisitLabelDefinition(ctx *parser.LabelDefinitionContext) interface{} {
return ctx.IDENTIFIER().GetText()
}
func (asm *assembler) VisitLabel(ctx *parser.LabelContext) interface{} {
return ctx.IDENTIFIER().GetText()
}
func (asm *assembler) VisitComment(ctx *parser.CommentContext) interface{} {
return asm.VisitChildren(ctx)
}
func (asm *assembler) VisitInstruction(ctx *parser.InstructionContext) interface{} {
log.Printf("instruction: %#+v", ctx)
switch {
case ctx.AluOperation() != nil:
return asm.Visit(ctx.AluOperation())
case ctx.Alu64Operation() != nil:
return asm.Visit(ctx.Alu64Operation())
case ctx.ByteSwapOperation() != nil:
return asm.Visit(ctx.ByteSwapOperation())
case ctx.JumpOperation() != nil:
return asm.Visit(ctx.JumpOperation())
case ctx.JumpConditionalOperation() != nil:
return asm.Visit(ctx.JumpConditionalOperation())
case ctx.CallOperation() != nil:
return asm.Visit(ctx.CallOperation())
case ctx.ExitOperation() != nil:
return asm.Visit(ctx.ExitOperation())
case ctx.LoadOperation() != nil:
return asm.Visit(ctx.LoadOperation())
case ctx.StoreOperation() != nil:
return asm.Visit(ctx.StoreOperation())
default:
return fmt.Errorf("unknown instruction: %#+v", ctx)
}
}
func (asm *assembler) VisitAluOperation(ctx *parser.AluOperationContext) interface{} {
log.Printf("context: %#+v", ctx)
/*
var (
opcode = asm.Visit(ctx.AluOperator()).(ALUOp)
)
switch {
case ctx.LiteralNumber() != nil:
return bpf.ALUOpConstant{Op: opcode, Val: asm.Visit(ctx.LiteralNumber()).(uint32)}
case ctx.RegisterX() != nil:
return bpf.ALUOpX{Op: opcode}
default:
return nil
}
*/
op := asm.Visit(ctx.AluOperator()).(ALUOp)
switch {
case ctx.Immediate() != nil: // aluOperator Register ',' immediate
return ALUOpConstant{
Op: op,
Dst: asm.Visit(ctx.Register(0)).(Register),
Value: asm.Visit(ctx.Immediate()).(uint32),
}
case ctx.Register(1) != nil: // aluOperator Register ',' Register
return ALUOpRegister{
Op: op,
Dst: asm.Visit(ctx.Register(0)).(Register),
Src: asm.Visit(ctx.Register(1)).(Register),
}
case ctx.Register(0) != nil: // aluOperator Register
return Negate{
Dst: asm.Visit(ctx.Register(0)).(Register),
}
default:
return nil
}
}
func (asm *assembler) VisitAluOperator(ctx *parser.AluOperatorContext) interface{} {
switch {
case ctx.ADD32() != nil:
return ALUOpAdd // 0x00
case ctx.SUB32() != nil:
return ALUOpSub // 0x10
case ctx.MUL32() != nil:
return ALUOpMul // 0x20
case ctx.DIV32() != nil:
return ALUOpDiv // 0x30
case ctx.OR32() != nil:
return ALUOpOr // 0x40
case ctx.AND32() != nil:
return ALUOpAnd // 0x50
case ctx.LSH32() != nil:
return ALUOpShiftLeft // 0x60
case ctx.RSH32() != nil:
return ALUOpShiftRight // 0x70
case ctx.NEG32() != nil:
return aluOpNegate // 0x80
case ctx.MOD32() != nil:
return ALUOpMod // 0x90
case ctx.XOR32() != nil:
return ALUOpXor // 0xa0
case ctx.MOV32() != nil:
return ALUOpMove // 0xb0
case ctx.ARSH32() != nil:
return ALUOpArithmicShiftRight // 0xc0
default:
return ALUOp(0)
}
}
// Visit a parse tree produced by AssemblerParser#alu64Operation.
func (asm *assembler) VisitAlu64Operation(ctx *parser.Alu64OperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#alu64Operator.
func (asm *assembler) VisitAlu64Operator(ctx *parser.Alu64OperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#byteSwapOperation.
func (asm *assembler) VisitByteSwapOperation(ctx *parser.ByteSwapOperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#byteSwapOperator.
func (asm *assembler) VisitByteSwapOperator(ctx *parser.ByteSwapOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#jumpOperation.
func (asm *assembler) VisitJumpOperation(ctx *parser.JumpOperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#jumpOperator.
func (asm *assembler) VisitJumpOperator(ctx *parser.JumpOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#jumpConditionalOperation.
func (asm *assembler) VisitJumpConditionalOperation(ctx *parser.JumpConditionalOperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#jumpConditionalOperator.
func (asm *assembler) VisitJumpConditionalOperator(ctx *parser.JumpConditionalOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#callOperation.
func (asm *assembler) VisitCallOperation(ctx *parser.CallOperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#exitOperation.
func (asm *assembler) VisitExitOperation(ctx *parser.ExitOperationContext) interface{} {
return Exit{}
}
// Visit a parse tree produced by AssemblerParser#loadOperation.
func (asm *assembler) VisitLoadOperation(ctx *parser.LoadOperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#loadAbsoluteOperator.
func (asm *assembler) VisitLoadAbsoluteOperator(ctx *parser.LoadAbsoluteOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#loadOperator.
func (asm *assembler) VisitLoadOperator(ctx *parser.LoadOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#storeOperation.
func (asm *assembler) VisitStoreOperation(ctx *parser.StoreOperationContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#storeOperator.
func (asm *assembler) VisitStoreOperator(ctx *parser.StoreOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#storeXOperator.
func (asm *assembler) VisitStoreXOperator(ctx *parser.StoreXOperatorContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#number.
func (asm *assembler) VisitNumber(ctx *parser.NumberContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#literalNumber.
func (asm *assembler) VisitLiteralNumber(ctx *parser.LiteralNumberContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#offset.
func (asm *assembler) VisitOffset(ctx *parser.OffsetContext) interface{} {
return nil
}
// Visit a parse tree produced by AssemblerParser#immediate.
func (asm *assembler) VisitImmediate(ctx *parser.ImmediateContext) interface{} {
var (
number = ctx.GetText()
base int
)
switch {
case strings.HasPrefix(number, "0b"):
number = number[2:]
base = 2
case strings.HasPrefix(number, "0x"):
number = number[2:]
base = 16
default:
base = 10
}
u, _ := strconv.ParseInt(number, base, 32)
return uint32(u)
}
// Visit a parse tree produced by AssemblerParser#Register.
func (asm *assembler) VisitRegister(ctx *parser.RegisterContext) interface{} {
switch {
case ctx.REGISTER() != nil:
i, _ := strconv.ParseInt(ctx.GetText()[1:], 10, 8)
return Register(i)
case ctx.RAX() != nil:
return RAX
case ctx.RFP() != nil:
return RFP
default:
panic("unreachable")
}
}
// Visit a parse tree produced by AssemblerParser#extension.
func (asm *assembler) VisitExtension(ctx *parser.ExtensionContext) interface{} {
return nil
}