--[[ Copyright 2016 Marek Vavrusa 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. ]] -- LuaJIT to BPF bytecode compiler. -- -- The code generation phase is currently one-pass and produces: -- * Compiled code in BPF bytecode format (https://www.kernel.org/doc/Documentation/networking/filter.txt) -- * Variables with liveness analysis and other meta (spill information, compile-time value) -- -- The code generator optimises as much as possible in single pass: -- * Fold compile-time expressions and constant propagation -- * Basic control flow analysis with dead code elimination (based on compile-time expressions) -- * Single-pass optimistic register allocation -- -- The first pass doesn't have variable lifetime visibility yet, so it relies on rewriter for further -- optimisations such as: -- * Dead store elimination (first-pass doesn't know if/when the variable is going to be used) -- * Common sub-expression elimination (relies on DCE and liveness analysis) -- * Orphan JMP elimination (removing this in first pass would break previous JMP targets) -- * Better register allocation (needs to be recomputed after optimisations) local ffi = require('ffi') local bit = require('bit') local S = require('syscall') local bytecode = require('bpf.ljbytecode') local cdef = require('bpf.cdef') local proto = require('bpf.proto') local builtins = require('bpf.builtins') -- Constants local ALWAYS, NEVER = -1, -2 local BPF = ffi.typeof('struct bpf') local HELPER = ffi.typeof('struct bpf_func_id') -- Symbolic table of constant expressions over numbers local const_expr = { ADD = function (a, b) return a + b end, SUB = function (a, b) return a - b end, DIV = function (a, b) return a / b end, MOD = function (a, b) return a % b end, JEQ = function (a, b) return a == b end, JNE = function (a, b) return a ~= b end, JGE = function (a, b) return a >= b end, JGT = function (a, b) return a > b end, } local const_width = { [1] = BPF.B, [2] = BPF.H, [4] = BPF.W, [8] = BPF.DW, } -- Built-ins that are strict only (never compile-time expandable) local builtins_strict = { [ffi.new] = true, [print] = true, } -- Deep copy a table local function table_copy(t) local copy = {} for n,v in pairs(t) do if type(v) == 'table' then v = table_copy(v) end copy[n] = v end return copy end -- Return true if the constant part is a proxy local function is_proxy(x) return type(x) == 'table' and (x.__dissector or x.__map or x.__base) end -- Create compiler closure local function create_emitter(env, stackslots, params, param_types) local V = {} -- Variable tracking / register allocator local code = { -- Generated code pc = 0, bc_pc = 0, insn = ffi.new('struct bpf_insn[4096]'), fixup = {}, reachable = true, seen_cmp = nil, } local Vstate = {} -- Track variable layout at basic block exits -- Anything below this stack offset is free to use by caller -- @note: There is no tracking memory allocator, so the caller may -- lower it for persistent objects, but such memory will never -- be reclaimed and the caller is responsible for resetting stack -- top whenever the memory below is free to be reused local stack_top = (stackslots + 1) * ffi.sizeof('uint64_t') local function emit(op, dst, src, off, imm) local ins = code.insn[code.pc] ins.code = op ins.dst_reg = dst ins.src_reg = src ins.off = off ins.imm = imm code.pc = code.pc + 1 end local function reg_spill(var) local vinfo = V[var] assert(vinfo.reg, 'attempt to spill VAR that doesn\'t have an allocated register') vinfo.spill = (var + 1) * ffi.sizeof('uint64_t') -- Index by (variable number) * (register width) emit(BPF.MEM + BPF.STX + BPF.DW, 10, vinfo.reg, -vinfo.spill, 0) vinfo.reg = nil end local function reg_fill(var, reg) local vinfo = V[var] assert(reg, 'attempt to fill variable to register but not register is allocated') assert(vinfo.spill, 'attempt to fill register with a VAR that isn\'t spilled') emit(BPF.MEM + BPF.LDX + BPF.DW, reg, 10, -vinfo.spill, 0) vinfo.reg = reg vinfo.spill = nil end -- Allocate a register (lazy simple allocator) local function reg_alloc(var, reg) -- Specific register requested, must spill/move existing variable if reg then for k,v in pairs(V) do -- Spill any variable that has this register if v.reg == reg and not v.shadow then reg_spill(k) break end end return reg end -- Find free or least recently used slot local last, last_seen, used = nil, 0xffff, 0 for k,v in pairs(V) do if v.reg then if not v.live_to or v.live_to < last_seen then last, last_seen = k, v.live_to or last_seen end used = bit.bor(used, bit.lshift(1, v.reg)) end end -- Attempt to select a free register from R7-R9 (callee saved) local free = bit.bnot(used) if bit.band(free, 0x80) ~= 0 then reg = 7 elseif bit.band(free,0x100) ~= 0 then reg = 8 elseif bit.band(free,0x200) ~= 0 then reg = 9 end -- Select another variable to be spilled if not reg then assert(last) reg = V[last].reg reg_spill(last) end assert(reg, 'VAR '..var..'fill/spill failed') return reg end -- Set new variable local function vset(var, reg, const, vtype) -- Must materialise all variables shadowing this variable slot, as it will be overwritten if V[var] and V[var].reg then for _, vinfo in pairs(V) do -- Shadowing variable MUST share the same type and attributes, -- but the register assignment may have changed if vinfo.shadow == var then vinfo.reg = V[var].reg vinfo.shadow = nil end end end -- Get precise type for CDATA or attempt to narrow numeric constant if not vtype and type(const) == 'cdata' then vtype = ffi.typeof(const) end V[var] = {reg=reg, const=const, type=vtype} -- Track variable source if V[var].const and type(const) == 'table' then V[var].source = V[var].const.source end end -- Materialize (or register) a variable in a register -- If the register is nil, then the a new register is assigned (if not already assigned) local function vreg(var, reg, reserve, vtype) local vinfo = V[var] assert(vinfo, 'VAR '..var..' not registered') vinfo.live_to = code.pc-1 if (vinfo.reg and not reg) and not vinfo.shadow then return vinfo.reg end reg = reg_alloc(var, reg) -- Materialize variable shadow copy local src = vinfo while src.shadow do src = V[src.shadow] end if reserve then -- luacheck: ignore -- No load to register occurs elseif src.reg then emit(BPF.ALU64 + BPF.MOV + BPF.X, reg, src.reg, 0, 0) elseif src.spill then vinfo.spill = src.spill reg_fill(var, reg) elseif src.const then vtype = vtype or src.type if type(src.const) == 'table' and src.const.__base then -- Load pointer type emit(BPF.ALU64 + BPF.MOV + BPF.X, reg, 10, 0, 0) emit(BPF.ALU64 + BPF.ADD + BPF.K, reg, 0, 0, -src.const.__base) elseif type(src.const) == 'table' and src.const.__dissector then -- Load dissector offset (imm32), but keep the constant part (dissector proxy) emit(BPF.ALU64 + BPF.MOV + BPF.K, reg, 0, 0, src.const.off or 0) elseif vtype and ffi.sizeof(vtype) == 8 then -- IMM64 must be done in two instructions with imm64 = (lo(imm32), hi(imm32)) emit(BPF.LD + BPF.DW, reg, 0, 0, ffi.cast('uint32_t', src.const)) emit(0, 0, 0, 0, ffi.cast('uint32_t', bit.rshift(bit.rshift(src.const, 16), 16))) vinfo.const = nil -- The variable is live else emit(BPF.ALU64 + BPF.MOV + BPF.K, reg, 0, 0, src.const) vinfo.const = nil -- The variable is live end else assert(false, 'VAR '..var..' has neither register nor constant value') end vinfo.reg = reg vinfo.shadow = nil vinfo.live_from = code.pc-1 vinfo.type = vtype or vinfo.type return reg end -- Copy variable local function vcopy(dst, src) if dst == src then return end V[dst] = {reg=V[src].reg, const=V[src].const, shadow=src, source=V[src].source, type=V[src].type} end -- Dereference variable of pointer type local function vderef(dst_reg, src_reg, vinfo) -- Dereference map pointers for primitive types -- BPF doesn't allow pointer arithmetics, so use the entry value assert(type(vinfo.const) == 'table' and vinfo.const.__dissector, 'cannot dereference a non-pointer variable') local vtype = vinfo.const.__dissector local w = ffi.sizeof(vtype) assert(const_width[w], 'NYI: sizeof('..tostring(vtype)..') not 1/2/4/8 bytes') if dst_reg ~= src_reg then emit(BPF.ALU64 + BPF.MOV + BPF.X, dst_reg, src_reg, 0, 0) -- dst = src end -- Optimize the NULL check away if provably not NULL if not vinfo.source or vinfo.source:find('_or_null', 1, true) then emit(BPF.JMP + BPF.JEQ + BPF.K, src_reg, 0, 1, 0) -- if (src != NULL) end emit(BPF.MEM + BPF.LDX + const_width[w], dst_reg, src_reg, 0, 0) -- dst = *src; end -- Allocate a space for variable local function valloc(size, blank) local base = stack_top assert(stack_top + size < 512 * 1024, 'exceeded maximum stack size of 512kB') stack_top = stack_top + size -- Align to 8 byte boundary stack_top = math.ceil(stack_top/8)*8 -- Current kernel version doesn't support ARG_PTR_TO_RAW_STACK -- so we always need to have memory initialized, remove this when supported if blank then if type(blank) == 'string' then local sp = 0 while sp < size do -- TODO: no BPF_ST + BPF_DW instruction yet local as_u32 = ffi.new('uint32_t [1]') local sub = blank:sub(sp+1, sp+ffi.sizeof(as_u32)) ffi.copy(as_u32, sub, #sub) emit(BPF.MEM + BPF.ST + BPF.W, 10, 0, -(stack_top-sp), as_u32[0]) sp = sp + ffi.sizeof(as_u32) end elseif type(blank) == 'boolean' then reg_alloc(stackslots, 0) emit(BPF.ALU64 + BPF.MOV + BPF.K, 0, 0, 0, 0) for sp = base+8,stack_top,8 do emit(BPF.MEM + BPF.STX + BPF.DW, 10, 0, -sp, 0) end else error('NYI: will with unknown type '..type(blank)) end end return stack_top end -- Turn variable into scalar in register (or constant) local function vscalar(a, w) assert(const_width[w], 'sizeof(scalar variable) must be 1/2/4/8') local src_reg -- If source is a pointer, we must dereference it first if cdef.isptr(V[a].type) then src_reg = vreg(a) local tmp_reg = reg_alloc(stackslots, 1) -- Clone variable in tmp register emit(BPF.ALU64 + BPF.MOV + BPF.X, tmp_reg, src_reg, 0, 0) vderef(tmp_reg, tmp_reg, V[a]) src_reg = tmp_reg -- Materialize and dereference it -- Source is a value on stack, we must load it first elseif type(V[a].const) == 'table' and V[a].const.__base > 0 then src_reg = vreg(a) emit(BPF.MEM + BPF.LDX + const_width[w], src_reg, 10, -V[a].const.__base, 0) V[a].type = V[a].const.__dissector V[a].const = nil -- Value is dereferenced -- If source is an imm32 number, avoid register load elseif type(V[a].const) == 'number' and w < 8 then return nil, V[a].const -- Load variable from any other source else src_reg = vreg(a) end return src_reg, nil end -- Emit compensation code at the end of basic block to unify variable set layout on all block exits -- 1. we need to free registers by spilling -- 2. fill registers to match other exits from this BB local function bb_end(Vcomp) for i,v in pairs(V) do if Vcomp[i] and Vcomp[i].spill and not v.spill then -- Materialize constant or shadowing variable to be able to spill if not v.reg and (v.shadow or cdef.isimmconst(v)) then vreg(i) end reg_spill(i) end end for i,v in pairs(V) do if Vcomp[i] and Vcomp[i].reg and not v.reg then vreg(i, Vcomp[i].reg) end -- Compensate variable metadata change if Vcomp[i] and Vcomp[i].source then V[i].source = Vcomp[i].source end end end local function CMP_STR(a, b, op) assert(op == 'JEQ' or op == 'JNE', 'NYI: only equivallence stack/string only supports == or ~=') -- I have no better idea how to implement it than unrolled XOR loop, as we can fixup only one JMP -- So: X(a,b) = a[0] ^ b[0] | a[1] ^ b[1] | ... -- EQ(a,b) <=> X == 0 -- This could be optimised by placing early exits by rewriter in second phase for long strings local base, size = V[a].const.__base, math.min(#b, ffi.sizeof(V[a].type)) local acc, tmp = reg_alloc(stackslots, 0), reg_alloc(stackslots+1, 1) local sp = 0 emit(BPF.ALU64 + BPF.MOV + BPF.K, acc, 0, 0, 0) while sp < size do -- Load string chunk as imm32 local as_u32 = ffi.new('uint32_t [1]') local sub = b:sub(sp+1, sp+ffi.sizeof(as_u32)) ffi.copy(as_u32, sub, #sub) -- TODO: make this faster by interleaved load/compare steps with DW length emit(BPF.MEM + BPF.LDX + BPF.W, tmp, 10, -(base-sp), 0) emit(BPF.ALU64 + BPF.XOR + BPF.K, tmp, 0, 0, as_u32[0]) emit(BPF.ALU64 + BPF.OR + BPF.X, acc, tmp, 0, 0) sp = sp + ffi.sizeof(as_u32) end emit(BPF.JMP + BPF[op] + BPF.K, acc, 0, 0xffff, 0) code.seen_cmp = code.pc-1 end local function CMP_REG(a, b, op) -- Fold compile-time expressions if V[a].const and V[b].const and not (is_proxy(V[a].const) or is_proxy(V[b].const)) then code.seen_cmp = const_expr[op](V[a].const, V[b].const) and ALWAYS or NEVER else -- Comparison against compile-time string or stack memory if V[b].const and type(V[b].const) == 'string' then return CMP_STR(a, V[b].const, op) end -- The 0xFFFF target here has no significance, it's just a placeholder for -- compiler to replace it's absolute offset to LJ bytecode insn with a relative -- offset in BPF program code, verifier will accept only programs with valid JMP targets local a_reg, b_reg = vreg(a), vreg(b) emit(BPF.JMP + BPF[op] + BPF.X, a_reg, b_reg, 0xffff, 0) code.seen_cmp = code.pc-1 end end local function CMP_IMM(a, b, op) local c = V[a].const if c and not is_proxy(c) then -- Fold compile-time expressions code.seen_cmp = const_expr[op](c, b) and ALWAYS or NEVER else -- Convert imm32 to number if type(b) == 'string' then if #b == 1 then b = b:byte() elseif cdef.isptr(V[a].type) then -- String comparison between stack/constant string return CMP_STR(a, b, op) elseif #b <= 4 then -- Convert to u32 with network byte order local imm = ffi.new('uint32_t[1]') ffi.copy(imm, b, #b) b = builtins.hton(imm[0]) else error('NYI: compare register with string, where #string > sizeof(u32)') end end -- The 0xFFFF target here has no significance, it's just a placeholder for -- compiler to replace it's absolute offset to LJ bytecode insn with a relative -- offset in BPF program code, verifier will accept only programs with valid JMP targets local reg = vreg(a) emit(BPF.JMP + BPF[op] + BPF.K, reg, 0, 0xffff, b) code.seen_cmp = code.pc-1 -- Remember NULL pointer checks as BPF prohibits pointer comparisons -- and repeated checks wouldn't pass the verifier, only comparisons -- against constants are checked. if op == 'JEQ' and tonumber(b) == 0 and V[a].source then local pos = V[a].source:find('_or_null', 1, true) if pos then code.seen_null_guard = a end -- Inverse NULL pointer check (if a ~= nil) elseif op == 'JNE' and tonumber(b) == 0 and V[a].source then local pos = V[a].source:find('_or_null', 1, true) if pos then code.seen_null_guard = a code.seen_null_guard_inverse = true end end end end local function ALU_IMM(dst, a, b, op) -- Fold compile-time expressions if V[a].const and not is_proxy(V[a].const) then assert(cdef.isimmconst(V[a]), 'VAR '..a..' must be numeric') vset(dst, nil, const_expr[op](V[a].const, b)) -- Now we need to materialize dissected value at DST, and add it else vcopy(dst, a) local dst_reg = vreg(dst) if cdef.isptr(V[a].type) then vderef(dst_reg, dst_reg, V[a]) V[dst].type = V[a].const.__dissector else V[dst].type = V[a].type end emit(BPF.ALU64 + BPF[op] + BPF.K, dst_reg, 0, 0, b) end end local function ALU_REG(dst, a, b, op) -- Fold compile-time expressions if V[a].const and not (is_proxy(V[a].const) or is_proxy(V[b].const)) then assert(cdef.isimmconst(V[a]), 'VAR '..a..' must be numeric') assert(cdef.isimmconst(V[b]), 'VAR '..b..' must be numeric') if type(op) == 'string' then op = const_expr[op] end vcopy(dst, a) V[dst].const = op(V[a].const, V[b].const) else local src_reg = b and vreg(b) or 0 -- SRC is optional for unary operations if b and cdef.isptr(V[b].type) then -- We have to allocate a temporary register for dereferencing to preserve -- pointer in source variable that MUST NOT be altered reg_alloc(stackslots, 2) vderef(2, src_reg, V[b]) src_reg = 2 end vcopy(dst, a) -- DST may alias B, so copy must occur after we materialize B local dst_reg = vreg(dst) if cdef.isptr(V[a].type) then vderef(dst_reg, dst_reg, V[a]) V[dst].type = V[a].const.__dissector end emit(BPF.ALU64 + BPF[op] + BPF.X, dst_reg, src_reg, 0, 0) V[stackslots].reg = nil -- Free temporary registers end end local function ALU_IMM_NV(dst, a, b, op) -- Do DST = IMM(a) op VAR(b) where we can't invert because -- the registers are u64 but immediates are u32, so complement -- arithmetics wouldn't work vset(stackslots+1, nil, a) ALU_REG(dst, stackslots+1, b, op) end local function LD_ABS(dst, w, off) assert(off, 'LD_ABS called without offset') if w < 8 then local dst_reg = vreg(dst, 0, true, builtins.width_type(w)) -- Reserve R0 emit(BPF.LD + BPF.ABS + const_width[w], dst_reg, 0, 0, off) if w > 1 and ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse emit(BPF.ALU + BPF.END + BPF.TO_BE, dst_reg, 0, 0, w * 8) end elseif w == 8 then -- LD_ABS|IND prohibits DW, we need to do two W loads and combine them local tmp_reg = vreg(stackslots, 0, true, builtins.width_type(w)) -- Reserve R0 emit(BPF.LD + BPF.ABS + const_width[4], tmp_reg, 0, 0, off + 4) if ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse emit(BPF.ALU + BPF.END + BPF.TO_BE, tmp_reg, 0, 0, 32) end ALU_IMM(stackslots, stackslots, 32, 'LSH') local dst_reg = vreg(dst, 0, true, builtins.width_type(w)) -- Reserve R0, spill tmp variable emit(BPF.LD + BPF.ABS + const_width[4], dst_reg, 0, 0, off) if ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse emit(BPF.ALU + BPF.END + BPF.TO_BE, dst_reg, 0, 0, 32) end ALU_REG(dst, dst, stackslots, 'OR') V[stackslots].reg = nil -- Free temporary registers else assert(w < 8, 'NYI: only LD_ABS of 1/2/4/8 is supported') end end local function LD_IND(dst, src, w, off) local src_reg = vreg(src) -- Must materialize first in case dst == src local dst_reg = vreg(dst, 0, true, builtins.width_type(w)) -- Reserve R0 emit(BPF.LD + BPF.IND + const_width[w], dst_reg, src_reg, 0, off or 0) if w > 1 and ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse emit(BPF.ALU + BPF.END + BPF.TO_BE, dst_reg, 0, 0, w * 8) end end local function LD_MEM(dst, src, w, off) local src_reg = vreg(src) -- Must materialize first in case dst == src local dst_reg = vreg(dst, nil, true, builtins.width_type(w)) -- Reserve R0 emit(BPF.MEM + BPF.LDX + const_width[w], dst_reg, src_reg, off or 0, 0) end -- @note: This is specific now as it expects registers reserved local function LD_IMM_X(dst_reg, src_type, imm, w) if w == 8 then -- IMM64 must be done in two instructions with imm64 = (lo(imm32), hi(imm32)) emit(BPF.LD + const_width[w], dst_reg, src_type, 0, ffi.cast('uint32_t', imm)) -- Must shift in two steps as bit.lshift supports [0..31] emit(0, 0, 0, 0, ffi.cast('uint32_t', bit.lshift(bit.lshift(imm, 16), 16))) else emit(BPF.LD + const_width[w], dst_reg, src_type, 0, imm) end end local function BUILTIN(func, ...) local builtin_export = { -- Compiler primitives (work with variable slots, emit instructions) V=V, vreg=vreg, vset=vset, vcopy=vcopy, vderef=vderef, valloc=valloc, emit=emit, reg_alloc=reg_alloc, reg_spill=reg_spill, tmpvar=stackslots, const_width=const_width, -- Extensions and helpers (use with care) LD_IMM_X = LD_IMM_X, } func(builtin_export, ...) end local function LOAD(dst, src, off, vtype) local base = V[src].const assert(base and base.__dissector, 'NYI: load() on variable that doesn\'t have dissector') assert(V[src].source, 'NYI: load() on variable with unknown source') -- Cast to different type if requested vtype = vtype or base.__dissector local w = ffi.sizeof(vtype) assert(const_width[w], 'NYI: load() supports 1/2/4/8 bytes at a time only, wanted ' .. tostring(w)) -- Packet access with a dissector (use BPF_LD) if V[src].source:find('ptr_to_pkt', 1, true) then if base.off then -- Absolute address to payload LD_ABS(dst, w, off + base.off) else -- Indirect address to payload LD_IND(dst, src, w, off) end -- Direct access to first argument (skb fields, pt regs, ...) elseif V[src].source:find('ptr_to_ctx', 1, true) then LD_MEM(dst, src, w, off) -- Direct skb access with a dissector (use BPF_MEM) elseif V[src].source:find('ptr_to_skb', 1, true) then LD_MEM(dst, src, w, off) -- Pointer to map-backed memory (use BPF_MEM) elseif V[src].source:find('ptr_to_map_value', 1, true) then LD_MEM(dst, src, w, off) -- Indirect read using probe (uprobe or kprobe, uses helper) elseif V[src].source:find('ptr_to_probe', 1, true) then BUILTIN(builtins[builtins.probe_read], nil, dst, src, vtype, off) V[dst].source = V[src].source -- Builtin handles everything else error('NYI: load() on variable from ' .. V[src].source) end V[dst].type = vtype V[dst].const = nil -- Dissected value is not constant anymore end local function CALL(a, b, d) assert(b-1 <= 1, 'NYI: CALL with >1 return values') -- Perform either compile-time, helper, or builtin local func = V[a].const -- Gather all arguments and check if they're constant local args, const, nargs = {}, true, d - 1 for i = a+1, a+d-1 do table.insert(args, V[i].const) if not V[i].const or is_proxy(V[i].const) then const = false end end local builtin = builtins[func] if not const or nargs == 0 then if builtin and type(builtin) == 'function' then args = {a} for i = a+1, a+nargs do table.insert(args, i) end BUILTIN(builtin, unpack(args)) elseif V[a+2] and V[a+2].const then -- var OP imm ALU_IMM(a, a+1, V[a+2].const, builtin) elseif nargs <= 2 then -- var OP var ALU_REG(a, a+1, V[a+2] and a+2, builtin) else error('NYI: CALL non-builtin with 3 or more arguments') end -- Call on dissector implies slice retrieval elseif type(func) == 'table' and func.__dissector then assert(nargs >= 2, 'NYI: .slice(a, b) must have at least two arguments') assert(V[a+1].const and V[a+2].const, 'NYI: slice() arguments must be constant') local off = V[a+1].const local vtype = builtins.width_type(V[a+2].const - off) -- Access to packet via packet (use BPF_LD) if V[a].source and V[a].source:find('ptr_to_', 1, true) then LOAD(a, a, off, vtype) else error('NYI: .slice(a, b) on non-pointer memory ' .. (V[a].source or 'unknown')) end -- Strict builtins cannot be expanded on compile-time elseif builtins_strict[func] and builtin then args = {a} for i = a+1, a+nargs do table.insert(args, i) end BUILTIN(builtin, unpack(args)) -- Attempt compile-time call expansion (expects all argument compile-time known) else assert(const, 'NYI: CALL attempted on constant arguments, but at least one argument is not constant') V[a].const = func(unpack(args)) end end local function MAP_INIT(map_var, key, imm) local map = V[map_var].const vreg(map_var, 1, true, ffi.typeof('uint64_t')) -- Reserve R1 and load ptr for process-local map fd LD_IMM_X(1, BPF.PSEUDO_MAP_FD, map.fd, ffi.sizeof(V[map_var].type)) V[map_var].reg = nil -- R1 will be invalidated after CALL, forget register allocation -- Reserve R2 and load R2 = key pointer local key_size = ffi.sizeof(map.key_type) local w = const_width[key_size] or BPF.DW local pod_type = const_width[key_size] local sp = stack_top + key_size -- Must use stack below spill slots -- Store immediate value on stack reg_alloc(stackslots, 2) -- Spill anything in R2 (unnamed tmp variable) local key_base = key and V[key].const imm = imm or key_base if imm and (not key or not is_proxy(key_base)) then assert(pod_type, 'NYI: map[const K], K width must be 1/2/4/8') emit(BPF.MEM + BPF.ST + w, 10, 0, -sp, imm) -- Key is in register, spill it elseif V[key].reg and pod_type then if cdef.isptr(V[key].type) then -- There is already pointer in register, dereference before spilling emit(BPF.MEM + BPF.LDX + w, 2, V[key].reg, 0, 0) emit(BPF.MEM + BPF.STX + w, 10, 2, -sp, 0) else -- Variable in register is POD, spill it on the stack emit(BPF.MEM + BPF.STX + w, 10, V[key].reg, -sp, 0) end -- Key is spilled from register to stack elseif V[key].spill then sp = V[key].spill -- Key is already on stack, write to base-relative address elseif key_base.__base then assert(key_size == ffi.sizeof(V[key].type), 'VAR '..key..' type incompatible with BPF map key type') sp = key_base.__base else error('VAR '..key..' is neither const-expr/register/stack/spilled') end -- If [FP+K] addressing, emit it if sp then emit(BPF.ALU64 + BPF.MOV + BPF.X, 2, 10, 0, 0) emit(BPF.ALU64 + BPF.ADD + BPF.K, 2, 0, 0, -sp) end end local function MAP_GET(dst, map_var, key, imm) local map = V[map_var].const MAP_INIT(map_var, key, imm) -- Flag as pointer type and associate dissector for map value type vreg(dst, 0, true, ffi.typeof('uint8_t *')) V[dst].const = {__dissector=map.val_type} V[dst].source = 'ptr_to_map_value_or_null' emit(BPF.JMP + BPF.CALL, 0, 0, 0, HELPER.map_lookup_elem) V[stackslots].reg = nil -- Free temporary registers end local function MAP_DEL(map_var, key, key_imm) -- Set R0, R1 (map fd, preempt R0) reg_alloc(stackslots, 0) -- Spill anything in R0 (unnamed tmp variable) MAP_INIT(map_var, key, key_imm) emit(BPF.JMP + BPF.CALL, 0, 0, 0, HELPER.map_delete_elem) V[stackslots].reg = nil -- Free temporary registers end local function MAP_SET(map_var, key, key_imm, src) local map = V[map_var].const -- Delete when setting nil if V[src].type == ffi.typeof('void') then return MAP_DEL(map_var, key, key_imm) end -- Set R0, R1 (map fd, preempt R0) reg_alloc(stackslots, 0) -- Spill anything in R0 (unnamed tmp variable) MAP_INIT(map_var, key, key_imm) reg_alloc(stackslots, 4) -- Spill anything in R4 (unnamed tmp variable) emit(BPF.ALU64 + BPF.MOV + BPF.K, 4, 0, 0, 0) -- BPF_ANY, create new element or update existing -- Reserve R3 for value pointer reg_alloc(stackslots, 3) -- Spill anything in R3 (unnamed tmp variable) local val_size = ffi.sizeof(map.val_type) local w = const_width[val_size] or BPF.DW local pod_type = const_width[val_size] -- Stack pointer must be aligned to both key/value size and have enough headroom for (key, value) local sp = stack_top + ffi.sizeof(map.key_type) + val_size sp = sp + (sp % val_size) local base = V[src].const if base and not is_proxy(base) then assert(pod_type, 'NYI: MAP[K] = imm V; V width must be 1/2/4/8') emit(BPF.MEM + BPF.ST + w, 10, 0, -sp, base) -- Value is in register, spill it elseif V[src].reg and pod_type then -- Value is a pointer, derefernce it and spill it if cdef.isptr(V[src].type) then vderef(3, V[src].reg, V[src]) emit(BPF.MEM + BPF.STX + w, 10, 3, -sp, 0) else emit(BPF.MEM + BPF.STX + w, 10, V[src].reg, -sp, 0) end -- We get a pointer to spilled register on stack elseif V[src].spill then -- If variable is a pointer, we can load it to R3 directly (save "LEA") if cdef.isptr(V[src].type) then reg_fill(src, 3) -- If variable is a stack pointer, we don't have to check it if base.__base then emit(BPF.JMP + BPF.CALL, 0, 0, 0, HELPER.map_update_elem) return end vderef(3, V[src].reg, V[src]) emit(BPF.MEM + BPF.STX + w, 10, 3, -sp, 0) else sp = V[src].spill end -- Value is already on stack, write to base-relative address elseif base.__base then if val_size ~= ffi.sizeof(V[src].type) then local err = string.format('VAR %d type (%s) incompatible with BPF map value type (%s): expected %d, got %d', src, V[src].type, map.val_type, val_size, ffi.sizeof(V[src].type)) error(err) end sp = base.__base -- Value is constant, materialize it on stack else error('VAR '.. src ..' is neither const-expr/register/stack/spilled') end emit(BPF.ALU64 + BPF.MOV + BPF.X, 3, 10, 0, 0) emit(BPF.ALU64 + BPF.ADD + BPF.K, 3, 0, 0, -sp) emit(BPF.JMP + BPF.CALL, 0, 0, 0, HELPER.map_update_elem) V[stackslots].reg = nil -- Free temporary registers end -- Finally - this table translates LuaJIT bytecode into code emitter actions. local BC = { -- Constants KNUM = function(a, _, c, _) -- KNUM if c < 2147483648 then vset(a, nil, c, ffi.typeof('int32_t')) else vset(a, nil, c, ffi.typeof('uint64_t')) end end, KSHORT = function(a, _, _, d) -- KSHORT vset(a, nil, d, ffi.typeof('int16_t')) end, KCDATA = function(a, _, c, _) -- KCDATA -- Coerce numeric types if possible local ct = ffi.typeof(c) if ffi.istype(ct, ffi.typeof('uint64_t')) or ffi.istype(ct, ffi.typeof('int64_t')) then vset(a, nil, c, ct) elseif tonumber(c) ~= nil then -- TODO: this should not be possible vset(a, nil, tonumber(c), ct) else error('NYI: cannot use CDATA constant of type ' .. ct) end end, KPRI = function(a, _, _, d) -- KPRI -- KNIL is 0, must create a special type to identify it local vtype = (d < 1) and ffi.typeof('void') or ffi.typeof('uint8_t') vset(a, nil, (d < 2) and 0 or 1, vtype) end, KSTR = function(a, _, c, _) -- KSTR vset(a, nil, c, ffi.typeof('const char[?]')) end, MOV = function(a, _, _, d) -- MOV var, var vcopy(a, d) end, -- Comparison ops -- Note: comparisons are always followed by JMP opcode, that -- will fuse following JMP to JMP+CMP instruction in BPF -- Note: we're narrowed to integers, so operand/operator inversion is legit ISLT = function(a, _, _, d) return CMP_REG(d, a, 'JGE') end, -- (a < d) (inverted) ISGE = function(a, _, _, d) return CMP_REG(a, d, 'JGE') end, -- (a >= d) ISGT = function(a, _, _, d) return CMP_REG(a, d, 'JGT') end, -- (a > d) ISEQV = function(a, _, _, d) return CMP_REG(a, d, 'JEQ') end, -- (a == d) ISNEV = function(a, _, _, d) return CMP_REG(a, d, 'JNE') end, -- (a ~= d) ISEQS = function(a, _, c, _) return CMP_IMM(a, c, 'JEQ') end, -- (a == str(c)) ISNES = function(a, _, c, _) return CMP_IMM(a, c, 'JNE') end, -- (a ~= str(c)) ISEQN = function(a, _, c, _) return CMP_IMM(a, c, 'JEQ') end, -- (a == c) ISNEN = function(a, _, c, _) return CMP_IMM(a, c, 'JNE') end, -- (a ~= c) IST = function(_, _, _, d) return CMP_IMM(d, 0, 'JNE') end, -- (d) ISF = function(_, _, _, d) return CMP_IMM(d, 0, 'JEQ') end, -- (not d) ISEQP = function(a, _, c, _) return CMP_IMM(a, c, 'JEQ') end, -- ISEQP (a == c) -- Binary operations with RHS constants ADDVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'ADD') end, SUBVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'SUB') end, MULVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'MUL') end, DIVVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'DIV') end, MODVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'MOD') end, -- Binary operations with LHS constants -- Cheat code: we're narrowed to integer arithmetic, so MUL+ADD are commutative ADDNV = function(a, b, c, _) return ALU_IMM(a, b, c, 'ADD') end, -- ADDNV MULNV = function(a, b, c, _) return ALU_IMM(a, b, c, 'MUL') end, -- MULNV SUBNV = function(a, b, c, _) return ALU_IMM_NV(a, c, b, 'SUB') end, -- SUBNV DIVNV = function(a, b, c, _) return ALU_IMM_NV(a, c, b, 'DIV') end, -- DIVNV -- Binary operations between registers ADDVV = function(a, b, _, d) return ALU_REG(a, b, d, 'ADD') end, SUBVV = function(a, b, _, d) return ALU_REG(a, b, d, 'SUB') end, MULVV = function(a, b, _, d) return ALU_REG(a, b, d, 'MUL') end, DIVVV = function(a, b, _, d) return ALU_REG(a, b, d, 'DIV') end, MODVV = function(a, b, _, d) return ALU_REG(a, b, d, 'MOD') end, -- Strings CAT = function(a, b, _, d) -- CAT A = B ~ D assert(V[b].const and V[d].const, 'NYI: CAT only works on compile-time expressions') assert(type(V[b].const) == 'string' and type(V[d].const) == 'string', 'NYI: CAT only works on compile-time strings') vset(a, nil, V[b].const .. V[d].const) end, -- Tables GGET = function (a, _, c, _) -- GGET (A = GLOBAL[c]) if env[c] ~= nil then vset(a, nil, env[c]) else error(string.format("undefined global '%s'", c)) end end, UGET = function (a, _, c, _) -- UGET (A = UPVALUE[c]) if env[c] ~= nil then vset(a, nil, env[c]) else error(string.format("undefined upvalue '%s'", c)) end end, TSETB = function (a, b, _, d) -- TSETB (B[D] = A) assert(V[b] and type(V[b].const) == 'table', 'NYI: B[D] where B is not Lua table, BPF map, or pointer') local vinfo = V[b].const if vinfo.__map then -- BPF map read (constant) return MAP_SET(b, nil, d, a) -- D is literal elseif vinfo.__dissector then assert(vinfo.__dissector, 'NYI: B[D] where B does not have a known element size') local w = ffi.sizeof(vinfo.__dissector) -- TODO: support vectorized moves larger than register width assert(const_width[w], 'B[C] = A, sizeof(A) must be 1/2/4/8') local src_reg, const = vscalar(a, w) -- If changing map value, write to absolute address + offset if V[b].source and V[b].source:find('ptr_to_map_value', 1, true) then local dst_reg = vreg(b) -- Optimization: immediate values (imm32) can be stored directly if type(const) == 'number' then emit(BPF.MEM + BPF.ST + const_width[w], dst_reg, 0, d, const) else emit(BPF.MEM + BPF.STX + const_width[w], dst_reg, src_reg, d, 0) end -- Table is already on stack, write to vinfo-relative address elseif vinfo.__base then -- Optimization: immediate values (imm32) can be stored directly if type(const) == 'number' then emit(BPF.MEM + BPF.ST + const_width[w], 10, 0, -vinfo.__base + (d * w), const) else emit(BPF.MEM + BPF.STX + const_width[w], 10, src_reg, -vinfo.__base + (d * w), 0) end else error('NYI: B[D] where B is not Lua table, BPF map, or pointer') end elseif vinfo and vinfo and V[a].const then vinfo[V[d].const] = V[a].const else error('NYI: B[D] where B is not Lua table, BPF map, or pointer') end end, TSETV = function (a, b, _, d) -- TSETV (B[D] = A) assert(V[b] and type(V[b].const) == 'table', 'NYI: B[D] where B is not Lua table, BPF map, or pointer') local vinfo = V[b].const if vinfo.__map then -- BPF map read (constant) return MAP_SET(b, d, nil, a) -- D is variable elseif vinfo.__dissector then assert(vinfo.__dissector, 'NYI: B[D] where B does not have a known element size') local w = ffi.sizeof(vinfo.__dissector) -- TODO: support vectorized moves larger than register width assert(const_width[w], 'B[C] = A, sizeof(A) must be 1/2/4/8') local src_reg, const = vscalar(a, w) -- If changing map value, write to absolute address + offset if V[b].source and V[b].source:find('ptr_to_map_value', 1, true) then -- Calculate variable address from two registers local tmp_var = stackslots + 1 vset(tmp_var, nil, d) ALU_REG(tmp_var, tmp_var, b, 'ADD') local dst_reg = vreg(tmp_var) V[tmp_var].reg = nil -- Only temporary allocation -- Optimization: immediate values (imm32) can be stored directly if type(const) == 'number' and w < 8 then emit(BPF.MEM + BPF.ST + const_width[w], dst_reg, 0, 0, const) else emit(BPF.MEM + BPF.STX + const_width[w], dst_reg, src_reg, 0, 0) end -- Table is already on stack, write to vinfo-relative address elseif vinfo.__base then -- Calculate variable address from two registers local tmp_var = stackslots + 1 vcopy(tmp_var, d) -- Element position if w > 1 then ALU_IMM(tmp_var, tmp_var, w, 'MUL') -- multiply by element size end local dst_reg = vreg(tmp_var) -- add R10 (stack pointer) emit(BPF.ALU64 + BPF.ADD + BPF.X, dst_reg, 10, 0, 0) V[tmp_var].reg = nil -- Only temporary allocation -- Optimization: immediate values (imm32) can be stored directly if type(const) == 'number' and w < 8 then emit(BPF.MEM + BPF.ST + const_width[w], dst_reg, 0, -vinfo.__base, const) else emit(BPF.MEM + BPF.STX + const_width[w], dst_reg, src_reg, -vinfo.__base, 0) end else error('NYI: B[D] where B is not Lua table, BPF map, or pointer') end elseif vinfo and V[d].const and V[a].const then vinfo[V[d].const] = V[a].const else error('NYI: B[D] where B is not Lua table, BPF map, or pointer') end end, TSETS = function (a, b, c, _) -- TSETS (B[C] = A) assert(V[b] and V[b].const, 'NYI: B[D] where B is not Lua table, BPF map, or pointer') local base = V[b].const if base.__dissector then local ofs,bpos = ffi.offsetof(base.__dissector, c) assert(not bpos, 'NYI: B[C] = A, where C is a bitfield') local w = builtins.sizeofattr(base.__dissector, c) -- TODO: support vectorized moves larger than register width assert(const_width[w], 'B[C] = A, sizeof(A) must be 1/2/4/8') local src_reg, const = vscalar(a, w) -- If changing map value, write to absolute address + offset if V[b].source and V[b].source:find('ptr_to_map_value', 1, true) then local dst_reg = vreg(b) -- Optimization: immediate values (imm32) can be stored directly if type(const) == 'number' and w < 8 then emit(BPF.MEM + BPF.ST + const_width[w], dst_reg, 0, ofs, const) else emit(BPF.MEM + BPF.STX + const_width[w], dst_reg, src_reg, ofs, 0) end -- Table is already on stack, write to base-relative address elseif base.__base then -- Optimization: immediate values (imm32) can be stored directly if type(const) == 'number' and w < 8 then emit(BPF.MEM + BPF.ST + const_width[w], 10, 0, -base.__base + ofs, const) else emit(BPF.MEM + BPF.STX + const_width[w], 10, src_reg, -base.__base + ofs, 0) end else error('NYI: B[C] where B is not Lua table, BPF map, or pointer') end elseif V[a].const then base[c] = V[a].const else error('NYI: B[C] where B is not Lua table, BPF map, or pointer') end end, TGETB = function (a, b, _, d) -- TGETB (A = B[D]) local base = V[b].const assert(type(base) == 'table', 'NYI: B[C] where C is string and B not Lua table or BPF map') if a ~= b then vset(a) end if base.__map then -- BPF map read (constant) MAP_GET(a, b, nil, d) -- Pointer access with a dissector (traditional uses BPF_LD, direct uses BPF_MEM) elseif V[b].source and V[b].source:find('ptr_to_') then local vtype = base.__dissector and base.__dissector or ffi.typeof('uint8_t') LOAD(a, b, d, vtype) -- Specialise PTR[0] as dereference operator elseif cdef.isptr(V[b].type) and d == 0 then vcopy(a, b) local dst_reg = vreg(a) vderef(dst_reg, dst_reg, V[a]) V[a].type = V[a].const.__dissector else error('NYI: A = B[D], where B is not Lua table or packet dissector or pointer dereference') end end, TGETV = function (a, b, _, d) -- TGETV (A = B[D]) local base = V[b].const assert(type(base) == 'table', 'NYI: B[C] where C is string and B not Lua table or BPF map') if a ~= b then vset(a) end if base.__map then -- BPF map read MAP_GET(a, b, d) -- Pointer access with a dissector (traditional uses BPF_LD, direct uses BPF_MEM) elseif V[b].source and V[b].source:find('ptr_to_') then local vtype = base.__dissector and base.__dissector or ffi.typeof('uint8_t') LOAD(a, b, d, vtype) -- Constant dereference elseif type(V[d].const) == 'number' then V[a].const = base[V[d].const] else error('NYI: A = B[D], where B is not Lua table or packet dissector or pointer dereference') end end, TGETS = function (a, b, c, _) -- TGETS (A = B[C]) local base = V[b].const assert(type(base) == 'table', 'NYI: B[C] where C is string and B not Lua table or BPF map') if a ~= b then vset(a) end if base.__dissector then local ofs,bpos,bsize = ffi.offsetof(base.__dissector, c) -- Resolve table key using metatable if not ofs and type(base.__dissector[c]) == 'string' then c = base.__dissector[c] ofs,bpos,bsize = ffi.offsetof(base.__dissector, c) end if not ofs and proto[c] then -- Load new dissector on given offset BUILTIN(proto[c], a, b, c) else -- Loading register from offset is a little bit tricky as there are -- several data sources and value loading modes with different restrictions -- such as checking pointer values for NULL compared to using stack. assert(ofs, tostring(base.__dissector)..'.'..c..' attribute not exists') if a ~= b then vset(a) end -- Dissected value is probably not constant anymore local new_const = nil local w, atype = builtins.sizeofattr(base.__dissector, c) -- [SP+K] addressing using R10 (stack pointer) -- Doesn't need to be checked for NULL if base.__base and base.__base > 0 then if cdef.isptr(atype) then -- If the member is pointer type, update base pointer with offset new_const = {__base = base.__base-ofs} else local dst_reg = vreg(a, nil, true) emit(BPF.MEM + BPF.LDX + const_width[w], dst_reg, 10, -base.__base+ofs, 0) end -- Pointer access with a dissector (traditional uses BPF_LD, direct uses BPF_MEM) elseif V[b].source and V[b].source:find('ptr_to_') then LOAD(a, b, ofs, atype) else error('NYI: B[C] where B is not Lua table, BPF map, or pointer') end -- Bitfield, must be further narrowed with a bitmask/shift if bpos then local mask = 0 for i=bpos+1,bpos+bsize do mask = bit.bor(mask, bit.lshift(1, w*8-i)) end emit(BPF.ALU64 + BPF.AND + BPF.K, vreg(a), 0, 0, mask) -- Free optimization: single-bit values need just boolean result if bsize > 1 then local shift = w*8-bsize-bpos if shift > 0 then emit(BPF.ALU64 + BPF.RSH + BPF.K, vreg(a), 0, 0, shift) end end end V[a].type = atype V[a].const = new_const V[a].source = V[b].source -- Track direct access to skb data -- see https://www.kernel.org/doc/Documentation/networking/filter.txt "Direct packet access" if ffi.istype(base.__dissector, ffi.typeof('struct sk_buff')) then -- Direct access to skb uses skb->data and skb->data_end -- which are encoded as u32, but are actually pointers if c == 'data' or c == 'data_end' then V[a].const = {__dissector = ffi.typeof('uint8_t')} V[a].source = 'ptr_to_skb' end end end else V[a].const = base[c] end end, -- Loops and branches CALLM = function (a, b, _, d) -- A = A(A+1, ..., A+D+MULTRES) -- NYI: Support single result only CALL(a, b, d+2) end, CALL = function (a, b, _, d) -- A = A(A+1, ..., A+D-1) CALL(a, b, d) end, JMP = function (a, _, c, _) -- JMP -- Discard unused slots after jump for i, _ in pairs(V) do if i >= a and i < stackslots then V[i] = nil end end -- Cross basic block boundary if the jump target isn't provably unreachable local val = code.fixup[c] or {} if code.seen_cmp and code.seen_cmp ~= ALWAYS then if code.seen_cmp ~= NEVER then -- Do not emit the jump or fixup -- Store previous CMP insn for reemitting after compensation code local jmpi = ffi.new('struct bpf_insn', code.insn[code.pc-1]) code.pc = code.pc - 1 -- First branch point, emit compensation code local Vcomp = Vstate[c] if not Vcomp then -- Select scratch register (R0-5) that isn't used as operand -- in the CMP instruction, as the variable may not be live, after -- the JMP, but it may be used in the JMP+CMP instruction itself local tmp_reg = 0 for reg = 0, 5 do if reg ~= jmpi.dst_reg and reg ~= jmpi.src_reg then tmp_reg = reg break end end -- Force materialization of constants at the end of BB for i, v in pairs(V) do if not v.reg and cdef.isimmconst(v) then vreg(i, tmp_reg) -- Load to TMP register (not saved) reg_spill(i) -- Spill caller-saved registers end end -- Record variable state Vstate[c] = V Vcomp = V V = table_copy(V) -- Variable state already set, emit specific compensation code else bb_end(Vcomp) end -- Record pointer NULL check from condition -- If the condition checks pointer variable against NULL, -- we can assume it will not be NULL in the fall-through block if code.seen_null_guard then local var = code.seen_null_guard -- The null guard can have two forms: -- if x == nil then goto -- if x ~= nil then goto -- First form guarantees that the variable will be non-nil on the following instruction -- Second form guarantees that the variable will be non-nil at the jump target local vinfo = code.seen_null_guard_inverse and Vcomp[var] or V[var] if vinfo.source then local pos = vinfo.source:find('_or_null', 1, true) if pos then vinfo.source = vinfo.source:sub(1, pos - 1) end end end -- Reemit CMP insn emit(jmpi.code, jmpi.dst_reg, jmpi.src_reg, jmpi.off, jmpi.imm) -- Fuse JMP into previous CMP opcode, mark JMP target for fixup -- as we don't knot the relative offset in generated code yet table.insert(val, code.pc-1) code.fixup[c] = val end code.seen_cmp = nil code.seen_null_guard = nil code.seen_null_guard_inverse = nil elseif c == code.bc_pc + 1 then -- luacheck: ignore 542 -- Eliminate jumps to next immediate instruction -- e.g. 0002 JMP 1 => 0003 else -- We need to synthesise a condition that's always true, however -- BPF prohibits pointer arithmetic to prevent pointer leaks -- so we have to clear out one register and use it for cmp that's always true local dst_reg = reg_alloc(stackslots) V[stackslots].reg = nil -- Only temporary allocation -- First branch point, emit compensation code local Vcomp = Vstate[c] if not Vcomp then -- Force materialization of constants at the end of BB for i, v in pairs(V) do if not v.reg and cdef.isimmconst(v) then vreg(i, dst_reg) -- Load to TMP register (not saved) reg_spill(i) -- Spill caller-saved registers end end -- Record variable state Vstate[c] = V V = table_copy(V) -- Variable state already set, emit specific compensation code else bb_end(Vcomp) end emit(BPF.ALU64 + BPF.MOV + BPF.K, dst_reg, 0, 0, 0) emit(BPF.JMP + BPF.JEQ + BPF.K, dst_reg, 0, 0xffff, 0) table.insert(val, code.pc-1) -- Fixup JMP target code.reachable = false -- Code following the JMP is not reachable code.fixup[c] = val end end, RET1 = function (a, _, _, _) -- RET1 -- Free optimisation: spilled variable will not be filled again for i, v in pairs(V) do if i ~= a then v.reg = nil end end if V[a].reg ~= 0 then vreg(a, 0) end -- Convenience: dereference pointer variables -- e.g. 'return map[k]' will return actual map value, not pointer if cdef.isptr(V[a].type) then vderef(0, 0, V[a]) end emit(BPF.JMP + BPF.EXIT, 0, 0, 0, 0) code.reachable = false end, RET0 = function (_, _, _, _) -- RET0 emit(BPF.ALU64 + BPF.MOV + BPF.K, 0, 0, 0, 0) emit(BPF.JMP + BPF.EXIT, 0, 0, 0, 0) code.reachable = false end, compile = function () return code end } -- Composite instructions function BC.CALLT(a, _, _, d) -- Tailcall: return A(A+1, ..., A+D-1) CALL(a, 1, d) BC.RET1(a) end -- Always initialize R6 with R1 context emit(BPF.ALU64 + BPF.MOV + BPF.X, 6, 1, 0, 0) -- Register R6 as context variable (first argument) if params and params > 0 then vset(0, 6, param_types[1] or proto.skb) assert(V[0].source == V[0].const.source) -- Propagate source annotation from typeinfo end -- Register tmpvars vset(stackslots) vset(stackslots+1) return setmetatable(BC, { __index = function (_, k, _) if type(k) == 'number' then local op_str = string.sub(require('jit.vmdef').bcnames, 6*k+1, 6*k+6) error(string.format("NYI: opcode '0x%02x' (%-04s)", k, op_str)) end end, __call = function (t, op, a, b, c, d) code.bc_pc = code.bc_pc + 1 -- Exitting BB straight through, emit compensation code if Vstate[code.bc_pc] then if code.reachable then -- Instruction is reachable from previous line -- so we must make the variable allocation consistent -- with the variable allocation at the jump source -- e.g. 0001 x:R0 = 5 -- 0002 if rand() then goto 0005 -- 0003 x:R0 -> x:stack -- 0004 y:R0 = 5 -- 0005 x:? = 10 <-- x was in R0 before jump, and stack after jump bb_end(Vstate[code.bc_pc]) else -- Instruction isn't reachable from previous line, restore variable layout -- e.g. RET or condition-less JMP on previous line V = table_copy(Vstate[code.bc_pc]) end end -- Perform fixup of jump targets -- We need to do this because the number of consumed and emitted -- bytecode instructions is different local fixup = code.fixup[code.bc_pc] if fixup ~= nil then -- Patch JMP source insn with relative offset for _,pc in ipairs(fixup) do code.insn[pc].off = code.pc - 1 - pc end code.fixup[code.bc_pc] = nil code.reachable = true end -- Execute if code.reachable then assert(t[op], string.format('NYI: instruction %s, parameters: %s,%s,%s,%s', op,a,b,c,d)) return t[op](a, b, c, d) end end, }) end -- Emitted code dump local function dump_mem(cls, ins, _, fuse) -- This is a very dense MEM instruction decoder without much explanation -- Refer to https://www.kernel.org/doc/Documentation/networking/filter.txt for instruction format local mode = bit.band(ins.code, 0xe0) if mode == BPF.XADD then cls = 5 end -- The only mode local op_1 = {'LD', 'LDX', 'ST', 'STX', '', 'XADD'} local op_2 = {[0]='W', [8]='H', [16]='B', [24]='DW'} local name = op_1[cls+1] .. op_2[bit.band(ins.code, 0x18)] local off = tonumber(ffi.cast('int16_t', ins.off)) -- Reinterpret as signed local dst = cls < 2 and 'R'..ins.dst_reg or string.format('[R%d%+d]', ins.dst_reg, off) local src = cls % 2 == 0 and '#'..ins.imm or 'R'..ins.src_reg if cls == BPF.LDX then src = string.format('[R%d%+d]', ins.src_reg, off) end if mode == BPF.ABS then src = string.format('skb[%d]', ins.imm) end if mode == BPF.IND then src = string.format('skb[R%d%+d]', ins.src_reg, ins.imm) end return string.format('%s\t%s\t%s', fuse and '' or name, fuse and '' or dst, src) end local function dump_alu(cls, ins, pc) local alu = {'ADD', 'SUB', 'MUL', 'DIV', 'OR', 'AND', 'LSH', 'RSH', 'NEG', 'MOD', 'XOR', 'MOV', 'ARSH', 'END' } local jmp = {'JA', 'JEQ', 'JGT', 'JGE', 'JSET', 'JNE', 'JSGT', 'JSGE', 'CALL', 'EXIT'} local helper = {'unspec', 'map_lookup_elem', 'map_update_elem', 'map_delete_elem', 'probe_read', 'ktime_get_ns', 'trace_printk', 'get_prandom_u32', 'get_smp_processor_id', 'skb_store_bytes', 'l3_csum_replace', 'l4_csum_replace', 'tail_call', 'clone_redirect', 'get_current_pid_tgid', 'get_current_uid_gid', 'get_current_comm', 'get_cgroup_classid', 'skb_vlan_push', 'skb_vlan_pop', 'skb_get_tunnel_key', 'skb_set_tunnel_key', 'perf_event_read', 'redirect', 'get_route_realm', 'perf_event_output', 'skb_load_bytes'} local op = 0 -- This is a very dense ALU instruction decoder without much explanation -- Refer to https://www.kernel.org/doc/Documentation/networking/filter.txt for instruction format for i = 0,13 do if 0x10 * i == bit.band(ins.code, 0xf0) then op = i + 1 break end end local name = (cls == 5) and jmp[op] or alu[op] local src = (bit.band(ins.code, 0x08) == BPF.X) and 'R'..ins.src_reg or '#'..ins.imm local target = (cls == 5 and op < 9) and string.format('\t=> %04d', pc + ins.off + 1) or '' if cls == 5 and op == 9 then target = string.format('\t; %s', helper[ins.imm + 1] or tostring(ins.imm)) end return string.format('%s\t%s\t%s%s', name, 'R'..ins.dst_reg, src, target) end local function dump_string(code, off, hide_counter) if not code then return end local cls_map = { [0] = dump_mem, [1] = dump_mem, [2] = dump_mem, [3] = dump_mem, [4] = dump_alu, [5] = dump_alu, [7] = dump_alu, } local result = {} local fused = false for i = off or 0, code.pc - 1 do local ins = code.insn[i] local cls = bit.band(ins.code, 0x07) local line = cls_map[cls](cls, ins, i, fused) if hide_counter then table.insert(result, line) else table.insert(result, string.format('%04u\t%s', i, line)) end fused = string.find(line, 'LDDW', 1) end return table.concat(result, '\n') end local function dump(code) if not code then return end print(string.format('-- BPF %s:0-%u', code.insn, code.pc)) print(dump_string(code)) end local function compile(prog, params) -- Create code emitter sandbox, include caller locals local env = { pkt=proto.pkt, eth=proto.pkt, BPF=BPF, ffi=ffi } -- Include upvalues up to 4 nested scopes back -- the narrower scope overrides broader scope for k = 5, 2, -1 do local i = 1 while true do local ok, n, v = pcall(debug.getlocal, k, i) if not ok or not n then break end env[n] = v i = i + 1 end end setmetatable(env, { __index = function (_, k) return proto[k] or builtins[k] or _G[k] end }) -- Create code emitter and compile LuaJIT bytecode if type(prog) == 'string' then prog = loadstring(prog) end -- Create error handler to print traceback local funci, pc = bytecode.funcinfo(prog), 0 local E = create_emitter(env, funci.stackslots, funci.params, params or {}) local on_err = function (e) funci = bytecode.funcinfo(prog, pc) local from, to = 0, 0 for _ = 1, funci.currentline do from = to to = string.find(funci.source, '\n', from+1, true) or 0 end print(funci.loc..':'..string.sub(funci.source, from+1, to-1)) print('error: '..e) print(debug.traceback()) end for _,op,a,b,c,d in bytecode.decoder(prog) do local ok, _, err = xpcall(E,on_err,op,a,b,c,d) if not ok then return nil, err end end return E:compile() end -- BPF map interface local bpf_map_mt = { __gc = function (map) S.close(map.fd) end, __len = function(map) return map.max_entries end, __index = function (map, k) if type(k) == 'string' then -- Return iterator if k == 'pairs' then return function(t, key) -- Get next key local next_key = ffi.new(ffi.typeof(t.key)) local cur_key if key then cur_key = t.key t.key[0] = key else cur_key = ffi.new(ffi.typeof(t.key)) end local ok, err = S.bpf_map_op(S.c.BPF_CMD.MAP_GET_NEXT_KEY, map.fd, cur_key, next_key) if not ok then return nil, err end -- Get next value assert(S.bpf_map_op(S.c.BPF_CMD.MAP_LOOKUP_ELEM, map.fd, next_key, map.val)) return next_key[0], map.val[0] end, map, nil -- Read for perf event map elseif k == 'reader' then return function (pmap, pid, cpu, event_type) -- Caller must either specify PID or CPU if not pid or pid < 0 then assert((cpu and cpu >= 0), 'NYI: creating composed reader for all CPUs') pid = -1 end -- Create BPF output reader local pe = S.t.perf_event_attr1() pe[0].type = 'software' pe[0].config = 'sw_bpf_output' pe[0].sample_type = 'raw' pe[0].sample_period = 1 pe[0].wakeup_events = 1 local reader, err = S.t.perf_reader(S.perf_event_open(pe, pid, cpu or -1)) if not reader then return nil, tostring(err) end -- Register event reader fd in BPF map assert(cpu < pmap.max_entries, string.format('BPF map smaller than read CPU %d', cpu)) pmap[cpu] = reader.fd -- Open memory map and start reading local ok, err = reader:start() assert(ok, tostring(err)) ok, err = reader:mmap() assert(ok, tostring(err)) return cdef.event_reader(reader, event_type) end -- Signalise this is a map type end return k == '__map' end -- Retrieve key map.key[0] = k local ok, err = S.bpf_map_op(S.c.BPF_CMD.MAP_LOOKUP_ELEM, map.fd, map.key, map.val) if not ok then return nil, err end return ffi.new(map.val_type, map.val[0]) end, __newindex = function (map, k, v) map.key[0] = k if v == nil then return S.bpf_map_op(map.fd, S.c.BPF_CMD.MAP_DELETE_ELEM, map.key, nil) end map.val[0] = v return S.bpf_map_op(S.c.BPF_CMD.MAP_UPDATE_ELEM, map.fd, map.key, map.val) end, } -- Linux tracing interface local function trace_check_enabled(path) path = path or '/sys/kernel/debug/tracing' if S.statfs(path) then return true end return nil, 'debugfs not accessible: "mount -t debugfs nodev /sys/kernel/debug"? missing sudo?' end -- Tracepoint interface local tracepoint_mt = { __index = { bpf = function (t, prog) if type(prog) ~= 'table' then -- Create protocol parser with source probe prog = compile(prog, {proto.type(t.type, {source='ptr_to_probe'})}) end -- Load the BPF program local prog_fd, err, log = S.bpf_prog_load(S.c.BPF_PROG.TRACEPOINT, prog.insn, prog.pc) assert(prog_fd, tostring(err)..': '..tostring(log)) -- Open tracepoint and attach t.reader:setbpf(prog_fd:getfd()) table.insert(t.progs, prog_fd) return prog_fd end, } } -- Open tracepoint local function tracepoint_open(path, pid, cpu, group_fd) -- Open tracepoint and compile tracepoint type local tp = assert(S.perf_tracepoint('/sys/kernel/debug/tracing/events/'..path)) local tp_type = assert(cdef.tracepoint_type(path)) -- Open tracepoint reader and create interface local reader = assert(S.perf_attach_tracepoint(tp, pid, cpu, group_fd)) return setmetatable({tp=tp,type=tp_type,reader=reader,progs={}}, tracepoint_mt) end local function trace_bpf(ptype, pname, pdef, retprobe, prog, pid, cpu, group_fd) -- Load BPF program if type(prog) ~= 'table' then prog = compile(prog, {proto.pt_regs}) end local prog_fd, err, log = S.bpf_prog_load(S.c.BPF_PROG.KPROBE, prog.insn, prog.pc) assert(prog_fd, tostring(err)..': '..tostring(log)) -- Open tracepoint and attach local tp, err = S.perf_probe(ptype, pname, pdef, retprobe) if not tp then prog_fd:close() return nil, tostring(err) end local reader, err = S.perf_attach_tracepoint(tp, pid, cpu, group_fd, {sample_type='raw, callchain'}) if not reader then prog_fd:close() S.perf_probe(ptype, pname, false) return nil, tostring(err) end local ok, err = reader:setbpf(prog_fd:getfd()) if not ok then prog_fd:close() reader:close() S.perf_probe(ptype, pname, false) return nil, tostring(err)..' (kernel version should be at least 4.1)' end -- Create GC closure for reader to close BPF program -- and detach probe in correct order ffi.gc(reader, function () prog_fd:close() reader:close() S.perf_probe(ptype, pname, false) end) return {reader=reader, prog=prog_fd, probe=pname, probe_type=ptype} end -- Module interface return setmetatable({ new = create_emitter, dump = dump, dump_string = dump_string, maps = {}, map = function (type, max_entries, key_ctype, val_ctype) if not key_ctype then key_ctype = ffi.typeof('uint32_t') end if not val_ctype then val_ctype = ffi.typeof('uint32_t') end if not max_entries then max_entries = 4096 end -- Special case for BPF_MAP_STACK_TRACE if S.c.BPF_MAP[type] == S.c.BPF_MAP.STACK_TRACE then key_ctype = ffi.typeof('int32_t') val_ctype = ffi.typeof('struct bpf_stacktrace') end local fd, err = S.bpf_map_create(S.c.BPF_MAP[type], ffi.sizeof(key_ctype), ffi.sizeof(val_ctype), max_entries) if not fd then return nil, tostring(err) end local map = setmetatable({ max_entries = max_entries, key = ffi.new(ffi.typeof('$ [1]', key_ctype)), val = ffi.new(ffi.typeof('$ [1]', val_ctype)), map_type = S.c.BPF_MAP[type], key_type = key_ctype, val_type = val_ctype, fd = fd:nogc():getfd(), }, bpf_map_mt) return map end, socket = function (sock, prog) -- Expect socket type, if sock is string then assume it's -- an interface name (e.g. 'lo'), if it's a number then typecast it as a socket local ok, err if type(sock) == 'string' then local iface = assert(S.nl.getlink())[sock] assert(iface, sock..' is not interface name') sock, err = S.socket('packet', 'raw') assert(sock, tostring(err)) ok, err = sock:bind(S.t.sockaddr_ll({protocol='all', ifindex=iface.index})) assert(ok, tostring(err)) elseif type(sock) == 'number' then sock = S.t.fd(sock):nogc() elseif ffi.istype(S.t.fd, sock) then -- luacheck: ignore -- No cast required else return nil, 'socket must either be an fd number, an interface name, or an ljsyscall socket' end -- Load program and attach it to socket if type(prog) ~= 'table' then prog = compile(prog, {proto.skb}) end local prog_fd, err, log = S.bpf_prog_load(S.c.BPF_PROG.SOCKET_FILTER, prog.insn, prog.pc) assert(prog_fd, tostring(err)..': '..tostring(log)) assert(sock:setsockopt('socket', 'attach_bpf', prog_fd:getfd())) return prog_fd, err end, tracepoint = function(tp, prog, pid, cpu, group_fd) assert(trace_check_enabled()) -- Return tracepoint instance if no program specified -- this allows free specialisation of arg0 to tracepoint type local probe = tracepoint_open(tp, pid, cpu, group_fd) -- Load the BPF program if prog then probe:bpf(prog) end return probe end, kprobe = function(tp, prog, retprobe, pid, cpu, group_fd) assert(trace_check_enabled()) -- Open tracepoint and attach local pname, pdef = tp:match('([^:]+):(.+)') return trace_bpf('kprobe', pname, pdef, retprobe, prog, pid, cpu, group_fd) end, uprobe = function(tp, prog, retprobe, pid, cpu, group_fd) assert(trace_check_enabled()) -- Translate symbol to address local obj, sym_want = tp:match('([^:]+):(.+)') if not S.statfs(obj) then return nil, S.t.error(S.c.E.NOENT) end -- Resolve Elf object (no support for anything else) local elf = require('bpf.elf').open(obj) local sym = elf:resolve(sym_want) if not sym then return nil, 'no such symbol' end sym = sym.st_value - elf:loadaddr() local sym_addr = string.format('%x%04x', tonumber(bit.rshift(sym, 32)), tonumber(ffi.cast('uint32_t', sym))) -- Convert it to expected uprobe format local pname = string.format('%s_%s', obj:gsub('.*/', ''), sym_addr) local pdef = obj..':0x'..sym_addr return trace_bpf('uprobe', pname, pdef, retprobe, prog, pid, cpu, group_fd) end, tracelog = function(path) assert(trace_check_enabled()) path = path or '/sys/kernel/debug/tracing/trace_pipe' return io.open(path, 'r') end, ntoh = builtins.ntoh, hton = builtins.hton, }, { __call = function (_, prog) return compile(prog) end, })