Lines Matching +full:end +full:- +full:to +full:- +full:end
1 --[[
8 http://www.apache.org/licenses/LICENSE-2.0
10 Unless required by applicable law or agreed to in writing, software
16 -- LuaJIT to BPF bytecode compiler.
17 --
18 -- The code generation phase is currently one-pass and produces:
19 -- * Compiled code in BPF bytecode format (https://www.kernel.org/doc/Documentation/networking/filt…
20 -- * Variables with liveness analysis and other meta (spill information, compile-time value)
21 --
22 -- The code generator optimises as much as possible in single pass:
23 -- * Fold compile-time expressions and constant propagation
24 -- * Basic control flow analysis with dead code elimination (based on compile-time expressions)
25 -- * Single-pass optimistic register allocation
26 --
27 -- The first pass doesn't have variable lifetime visibility yet, so it relies on rewriter for furth…
28 -- optimisations such as:
29 -- * Dead store elimination (first-pass doesn't know if/when the variable is going to be used)
30 -- * Common sub-expression elimination (relies on DCE and liveness analysis)
31 -- * Orphan JMP elimination (removing this in first pass would break previous JMP targets)
32 -- * Better register allocation (needs to be recomputed after optimisations)
42 -- Constants
43 local ALWAYS, NEVER = -1, -2
47 -- Symbolic table of constant expressions over numbers
49 ADD = function (a, b) return a + b end,
50 SUB = function (a, b) return a - b end,
51 DIV = function (a, b) return a / b end,
52 MOD = function (a, b) return a % b end,
53 JEQ = function (a, b) return a == b end,
54 JNE = function (a, b) return a ~= b end,
55 JGE = function (a, b) return a >= b end,
56 JGT = function (a, b) return a > b end,
63 -- Built-ins that are strict only (never compile-time expandable)
69 -- Deep copy a table
75 end
77 end
79 end
81 -- Return true if the constant part is a proxy
84 end
86 -- Create compiler closure
89 local V = {} -- Variable tracking / register allocator
90 local code = { -- Generated code
97 local Vstate = {} -- Track variable layout at basic block exits
99 -- Anything below this stack offset is free to use by caller
100 -- @note: There is no tracking memory allocator, so the caller may
101 -- lower it for persistent objects, but such memory will never
102 -- be reclaimed and the caller is responsible for resetting stack
103 -- top whenever the memory below is free to be reused
114 end
118 assert(vinfo.reg, 'attempt to spill VAR that doesn\'t have an allocated register')
119 vinfo.spill = (var + 1) * ffi.sizeof('uint64_t') -- Index by (variable number) * (register width)
120 emit(BPF.MEM + BPF.STX + BPF.DW, 10, vinfo.reg, -vinfo.spill, 0)
122 end
126 assert(reg, 'attempt to fill variable to register but not register is allocated')
127 assert(vinfo.spill, 'attempt to fill register with a VAR that isn\'t spilled')
128 emit(BPF.MEM + BPF.LDX + BPF.DW, reg, 10, -vinfo.spill, 0)
131 end
133 -- Allocate a register (lazy simple allocator)
135 -- Specific register requested, must spill/move existing variable
137 for k,v in pairs(V) do -- Spill any variable that has this register
141 end
142 end
144 end
145 -- Find free or least recently used slot
151 end
153 end
154 end
155 -- Attempt to select a free register from R7-R9 (callee saved)
160 end
161 -- Select another variable to be spilled
166 end
169 end
171 -- Set new variable
173 -- Must materialise all variables shadowing this variable slot, as it will be overwritten
176 -- Shadowing variable MUST share the same type and attributes,
177 -- but the register assignment may have changed
181 end
182 end
183 end
184 -- Get precise type for CDATA or attempt to narrow numeric constant
187 end
189 -- Track variable source
192 end
193 end
195 -- Materialize (or register) a variable in a register
196 -- If the register is nil, then the a new register is assigned (if not already assigned)
200 vinfo.live_to = code.pc-1
201 if (vinfo.reg and not reg) and not vinfo.shadow then return vinfo.reg end
203 -- Materialize variable shadow copy
205 while src.shadow do src = V[src.shadow] end
206 if reserve then -- luacheck: ignore
207 -- No load to register occurs
216 -- Load pointer type
218 emit(BPF.ALU64 + BPF.ADD + BPF.K, reg, 0, 0, -src.const.__base)
220 -- Load dissector offset (imm32), but keep the constant part (dissector proxy)
223 -- IMM64 must be done in two instructions with imm64 = (lo(imm32), hi(imm32))
226 vinfo.const = nil -- The variable is live
229 vinfo.const = nil -- The variable is live
230 end
231 else assert(false, 'VAR '..var..' has neither register nor constant value') end
234 vinfo.live_from = code.pc-1
237 end
239 -- Copy variable
241 if dst == src then return end
243 end
245 -- Dereference variable of pointer type
247 -- Dereference map pointers for primitive types
248 -- BPF doesn't allow pointer arithmetics, so use the entry value
249 …assert(type(vinfo.const) == 'table' and vinfo.const.__dissector, 'cannot dereference a non-pointer…
254 emit(BPF.ALU64 + BPF.MOV + BPF.X, dst_reg, src_reg, 0, 0) -- dst = src
255 end
256 -- Optimize the NULL check away if provably not NULL
258 emit(BPF.JMP + BPF.JEQ + BPF.K, src_reg, 0, 1, 0) -- if (src != NULL)
259 end
260 emit(BPF.MEM + BPF.LDX + const_width[w], dst_reg, src_reg, 0, 0) -- dst = *src;
261 end
263 -- Allocate a space for variable
268 -- Align to 8 byte boundary
270 -- Current kernel version doesn't support ARG_PTR_TO_RAW_STACK
271 -- so we always need to have memory initialized, remove this when supported
276 -- TODO: no BPF_ST + BPF_DW instruction yet
280 emit(BPF.MEM + BPF.ST + BPF.W, 10, 0, -(stack_top-sp), as_u32[0])
282 end
287 emit(BPF.MEM + BPF.STX + BPF.DW, 10, 0, -sp, 0)
288 end
289 else error('NYI: will with unknown type '..type(blank)) end
290 end
292 end
294 -- Turn variable into scalar in register (or constant)
298 -- If source is a pointer, we must dereference it first
301 local tmp_reg = reg_alloc(stackslots, 1) -- Clone variable in tmp register
304 src_reg = tmp_reg -- Materialize and dereference it
305 -- Source is a value on stack, we must load it first
308 emit(BPF.MEM + BPF.LDX + const_width[w], src_reg, 10, -V[a].const.__base, 0)
310 V[a].const = nil -- Value is dereferenced
311 -- If source is an imm32 number, avoid register load
314 -- Load variable from any other source
317 end
320 end
322 -- Emit compensation code at the end of basic block to unify variable set layout on all block exits
323 -- 1. we need to free registers by spilling
324 -- 2. fill registers to match other exits from this BB
328 -- Materialize constant or shadowing variable to be able to spill
331 end
333 end
334 end
338 end
339 -- Compensate variable metadata change
342 end
343 end
344 end
348 -- I have no better idea how to implement it than unrolled XOR loop, as we can fixup only one JMP
349 -- So: X(a,b) = a[0] ^ b[0] | a[1] ^ b[1] | ...
350 -- EQ(a,b) <=> X == 0
351 -- This could be optimised by placing early exits by rewriter in second phase for long strings
357 -- Load string chunk as imm32
361 -- TODO: make this faster by interleaved load/compare steps with DW length
362 emit(BPF.MEM + BPF.LDX + BPF.W, tmp, 10, -(base-sp), 0)
366 end
368 code.seen_cmp = code.pc-1
369 end
372 -- Fold compile-time expressions
376 -- Comparison against compile-time string or stack memory
379 end
380 -- The 0xFFFF target here has no significance, it's just a placeholder for
381 -- compiler to replace it's absolute offset to LJ bytecode insn with a relative
382 -- offset in BPF program code, verifier will accept only programs with valid JMP targets
385 code.seen_cmp = code.pc-1
386 end
387 end
391 if c and not is_proxy(c) then -- Fold compile-time expressions
394 -- Convert imm32 to number
398 -- String comparison between stack/constant string
401 -- Convert to u32 with network byte order
405 else error('NYI: compare register with string, where #string > sizeof(u32)') end
406 end
407 -- The 0xFFFF target here has no significance, it's just a placeholder for
408 -- compiler to replace it's absolute offset to LJ bytecode insn with a relative
409 -- offset in BPF program code, verifier will accept only programs with valid JMP targets
412 code.seen_cmp = code.pc-1
413 -- Remember NULL pointer checks as BPF prohibits pointer comparisons
414 -- and repeated checks wouldn't pass the verifier, only comparisons
415 -- against constants are checked.
420 end
421 -- Inverse NULL pointer check (if a ~= nil)
427 end
428 end
429 end
430 end
433 -- Fold compile-time expressions
437 -- Now we need to materialize dissected value at DST, and add it
446 end
448 end
449 end
452 -- Fold compile-time expressions
456 if type(op) == 'string' then op = const_expr[op] end
460 local src_reg = b and vreg(b) or 0 -- SRC is optional for unary operations
462 -- We have to allocate a temporary register for dereferencing to preserve
463 -- pointer in source variable that MUST NOT be altered
467 end
468 vcopy(dst, a) -- DST may alias B, so copy must occur after we materialize B
473 end
475 V[stackslots].reg = nil -- Free temporary registers
476 end
477 end
480 -- Do DST = IMM(a) op VAR(b) where we can't invert because
481 -- the registers are u64 but immediates are u32, so complement
482 -- arithmetics wouldn't work
485 end
490 local dst_reg = vreg(dst, 0, true, builtins.width_type(w)) -- Reserve R0
492 if w > 1 and ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse
493 emit(BPF.ALU + BPF.END + BPF.TO_BE, dst_reg, 0, 0, w * 8)
494 end
496 -- LD_ABS|IND prohibits DW, we need to do two W loads and combine them
497 local tmp_reg = vreg(stackslots, 0, true, builtins.width_type(w)) -- Reserve R0
499 if ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse
500 emit(BPF.ALU + BPF.END + BPF.TO_BE, tmp_reg, 0, 0, 32)
501 end
503 local dst_reg = vreg(dst, 0, true, builtins.width_type(w)) -- Reserve R0, spill tmp variable
505 if ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse
506 emit(BPF.ALU + BPF.END + BPF.TO_BE, dst_reg, 0, 0, 32)
507 end
509 V[stackslots].reg = nil -- Free temporary registers
512 end
513 end
516 local src_reg = vreg(src) -- Must materialize first in case dst == src
517 local dst_reg = vreg(dst, 0, true, builtins.width_type(w)) -- Reserve R0
519 if w > 1 and ffi.abi('le') then -- LD_ABS has htonl() semantics, reverse
520 emit(BPF.ALU + BPF.END + BPF.TO_BE, dst_reg, 0, 0, w * 8)
521 end
522 end
525 local src_reg = vreg(src) -- Must materialize first in case dst == src
526 local dst_reg = vreg(dst, nil, true, builtins.width_type(w)) -- Reserve R0
528 end
530 -- @note: This is specific now as it expects registers reserved
532 if w == 8 then -- IMM64 must be done in two instructions with imm64 = (lo(imm32), hi(imm32))
534 -- Must shift in two steps as bit.lshift supports [0..31]
538 end
539 end
543 -- Compiler primitives (work with variable slots, emit instructions)
546 -- Extensions and helpers (use with care)
550 end
556 -- Cast to different type if requested
560 -- Packet access with a dissector (use BPF_LD)
562 if base.off then -- Absolute address to payload
564 else -- Indirect address to payload
566 end
567 -- Direct access to first argument (skb fields, pt regs, ...)
570 -- Direct skb access with a dissector (use BPF_MEM)
573 -- Pointer to map-backed memory (use BPF_MEM)
576 -- Indirect read using probe (uprobe or kprobe, uses helper)
579 V[dst].source = V[src].source -- Builtin handles everything
582 end
584 V[dst].const = nil -- Dissected value is not constant anymore
585 end
588 assert(b-1 <= 1, 'NYI: CALL with >1 return values')
589 -- Perform either compile-time, helper, or builtin
591 -- Gather all arguments and check if they're constant
592 local args, const, nargs = {}, true, d - 1
593 for i = a+1, a+d-1 do
595 if not V[i].const or is_proxy(V[i].const) then const = false end
596 end
601 for i = a+1, a+nargs do table.insert(args, i) end
603 elseif V[a+2] and V[a+2].const then -- var OP imm
605 elseif nargs <= 2 then -- var OP var
608 error('NYI: CALL non-builtin with 3 or more arguments')
609 end
610 -- Call on dissector implies slice retrieval
615 local vtype = builtins.width_type(V[a+2].const - off)
616 -- Access to packet via packet (use BPF_LD)
620 error('NYI: <dissector>.slice(a, b) on non-pointer memory ' .. (V[a].source or 'unknown'))
621 end
622 -- Strict builtins cannot be expanded on compile-time
625 for i = a+1, a+nargs do table.insert(args, i) end
627 -- Attempt compile-time call expansion (expects all argument compile-time known)
631 end
632 end
637 -- Reserve R1 and load ptr for process-local map fd
639 V[map_var].reg = nil -- R1 will be invalidated after CALL, forget register allocation
640 -- Reserve R2 and load R2 = key pointer
644 local sp = stack_top + key_size -- Must use stack below spill slots
645 -- Store immediate value on stack
646 reg_alloc(stackslots, 2) -- Spill anything in R2 (unnamed tmp variable)
651 emit(BPF.MEM + BPF.ST + w, 10, 0, -sp, imm)
652 -- Key is in register, spill it
655 -- There is already pointer in register, dereference before spilling
657 emit(BPF.MEM + BPF.STX + w, 10, 2, -sp, 0)
658 else -- Variable in register is POD, spill it on the stack
659 emit(BPF.MEM + BPF.STX + w, 10, V[key].reg, -sp, 0)
660 end
661 -- Key is spilled from register to stack
664 -- Key is already on stack, write to base-relative address
669 error('VAR '..key..' is neither const-expr/register/stack/spilled')
670 end
671 -- If [FP+K] addressing, emit it
674 emit(BPF.ALU64 + BPF.ADD + BPF.K, 2, 0, 0, -sp)
675 end
676 end
681 -- Flag as pointer type and associate dissector for map value type
686 V[stackslots].reg = nil -- Free temporary registers
687 end
690 -- Set R0, R1 (map fd, preempt R0)
691 reg_alloc(stackslots, 0) -- Spill anything in R0 (unnamed tmp variable)
694 V[stackslots].reg = nil -- Free temporary registers
695 end
699 -- Delete when setting nil
702 end
703 -- Set R0, R1 (map fd, preempt R0)
704 reg_alloc(stackslots, 0) -- Spill anything in R0 (unnamed tmp variable)
706 reg_alloc(stackslots, 4) -- Spill anything in R4 (unnamed tmp variable)
707 emit(BPF.ALU64 + BPF.MOV + BPF.K, 4, 0, 0, 0) -- BPF_ANY, create new element or update existing
708 -- Reserve R3 for value pointer
709 reg_alloc(stackslots, 3) -- Spill anything in R3 (unnamed tmp variable)
713 -- Stack pointer must be aligned to both key/value size and have enough headroom for (key, value)
719 emit(BPF.MEM + BPF.ST + w, 10, 0, -sp, base)
720 -- Value is in register, spill it
722 -- Value is a pointer, derefernce it and spill it
725 emit(BPF.MEM + BPF.STX + w, 10, 3, -sp, 0)
727 emit(BPF.MEM + BPF.STX + w, 10, V[src].reg, -sp, 0)
728 end
729 -- We get a pointer to spilled register on stack
731 -- If variable is a pointer, we can load it to R3 directly (save "LEA")
734 -- If variable is a stack pointer, we don't have to check it
738 end
740 emit(BPF.MEM + BPF.STX + w, 10, 3, -sp, 0)
743 end
744 -- Value is already on stack, write to base-relative address
750 end
752 -- Value is constant, materialize it on stack
754 error('VAR '.. src ..' is neither const-expr/register/stack/spilled')
755 end
757 emit(BPF.ALU64 + BPF.ADD + BPF.K, 3, 0, 0, -sp)
759 V[stackslots].reg = nil -- Free temporary registers
760 end
762 -- Finally - this table translates LuaJIT bytecode into code emitter actions.
764 -- Constants
765 KNUM = function(a, _, c, _) -- KNUM
770 end
771 end,
772 KSHORT = function(a, _, _, d) -- KSHORT
774 end,
775 KCDATA = function(a, _, c, _) -- KCDATA
776 -- Coerce numeric types if possible
781 -- TODO: this should not be possible
785 end
786 end,
787 KPRI = function(a, _, _, d) -- KPRI
788 -- KNIL is 0, must create a special type to identify it
791 end,
792 KSTR = function(a, _, c, _) -- KSTR
794 end,
795 MOV = function(a, _, _, d) -- MOV var, var
797 end,
799 -- Comparison ops
800 -- Note: comparisons are always followed by JMP opcode, that
801 -- will fuse following JMP to JMP+CMP instruction in BPF
802 -- Note: we're narrowed to integers, so operand/operator inversion is legit
803 ISLT = function(a, _, _, d) return CMP_REG(d, a, 'JGE') end, -- (a < d) (inverted)
804 ISGE = function(a, _, _, d) return CMP_REG(a, d, 'JGE') end, -- (a >= d)
805 ISGT = function(a, _, _, d) return CMP_REG(a, d, 'JGT') end, -- (a > d)
806 ISEQV = function(a, _, _, d) return CMP_REG(a, d, 'JEQ') end, -- (a == d)
807 ISNEV = function(a, _, _, d) return CMP_REG(a, d, 'JNE') end, -- (a ~= d)
808 ISEQS = function(a, _, c, _) return CMP_IMM(a, c, 'JEQ') end, -- (a == str(c))
809 ISNES = function(a, _, c, _) return CMP_IMM(a, c, 'JNE') end, -- (a ~= str(c))
810 ISEQN = function(a, _, c, _) return CMP_IMM(a, c, 'JEQ') end, -- (a == c)
811 ISNEN = function(a, _, c, _) return CMP_IMM(a, c, 'JNE') end, -- (a ~= c)
812 IST = function(_, _, _, d) return CMP_IMM(d, 0, 'JNE') end, -- (d)
813 ISF = function(_, _, _, d) return CMP_IMM(d, 0, 'JEQ') end, -- (not d)
814 ISEQP = function(a, _, c, _) return CMP_IMM(a, c, 'JEQ') end, -- ISEQP (a == c)
815 -- Binary operations with RHS constants
816 ADDVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'ADD') end,
817 SUBVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'SUB') end,
818 MULVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'MUL') end,
819 DIVVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'DIV') end,
820 MODVN = function(a, b, c, _) return ALU_IMM(a, b, c, 'MOD') end,
821 -- Binary operations with LHS constants
822 -- Cheat code: we're narrowed to integer arithmetic, so MUL+ADD are commutative
823 ADDNV = function(a, b, c, _) return ALU_IMM(a, b, c, 'ADD') end, -- ADDNV
824 MULNV = function(a, b, c, _) return ALU_IMM(a, b, c, 'MUL') end, -- MULNV
825 SUBNV = function(a, b, c, _) return ALU_IMM_NV(a, c, b, 'SUB') end, -- SUBNV
826 DIVNV = function(a, b, c, _) return ALU_IMM_NV(a, c, b, 'DIV') end, -- DIVNV
827 -- Binary operations between registers
828 ADDVV = function(a, b, _, d) return ALU_REG(a, b, d, 'ADD') end,
829 SUBVV = function(a, b, _, d) return ALU_REG(a, b, d, 'SUB') end,
830 MULVV = function(a, b, _, d) return ALU_REG(a, b, d, 'MUL') end,
831 DIVVV = function(a, b, _, d) return ALU_REG(a, b, d, 'DIV') end,
832 MODVV = function(a, b, _, d) return ALU_REG(a, b, d, 'MOD') end,
833 -- Strings
834 CAT = function(a, b, _, d) -- CAT A = B ~ D
835 assert(V[b].const and V[d].const, 'NYI: CAT only works on compile-time expressions')
837 'NYI: CAT only works on compile-time strings')
839 end,
840 -- Tables
841 GGET = function (a, _, c, _) -- GGET (A = GLOBAL[c])
844 else error(string.format("undefined global '%s'", c)) end
845 end,
846 UGET = function (a, _, c, _) -- UGET (A = UPVALUE[c])
849 else error(string.format("undefined upvalue '%s'", c)) end
850 end,
851 TSETB = function (a, b, _, d) -- TSETB (B[D] = A)
854 if vinfo.__map then -- BPF map read (constant)
855 return MAP_SET(b, nil, d, a) -- D is literal
859 -- TODO: support vectorized moves larger than register width
862 -- If changing map value, write to absolute address + offset
865 -- Optimization: immediate values (imm32) can be stored directly
870 end
871 -- Table is already on stack, write to vinfo-relative address
873 -- Optimization: immediate values (imm32) can be stored directly
875 emit(BPF.MEM + BPF.ST + const_width[w], 10, 0, -vinfo.__base + (d * w), const)
877 emit(BPF.MEM + BPF.STX + const_width[w], 10, src_reg, -vinfo.__base + (d * w), 0)
878 end
881 end
886 end
887 end,
888 TSETV = function (a, b, _, d) -- TSETV (B[D] = A)
891 if vinfo.__map then -- BPF map read (constant)
892 return MAP_SET(b, d, nil, a) -- D is variable
896 -- TODO: support vectorized moves larger than register width
899 -- If changing map value, write to absolute address + offset
901 -- Calculate variable address from two registers
906 V[tmp_var].reg = nil -- Only temporary allocation
907 -- Optimization: immediate values (imm32) can be stored directly
912 end
913 -- Table is already on stack, write to vinfo-relative address
915 -- Calculate variable address from two registers
917 vcopy(tmp_var, d) -- Element position
919 ALU_IMM(tmp_var, tmp_var, w, 'MUL') -- multiply by element size
920 end
921 local dst_reg = vreg(tmp_var) -- add R10 (stack pointer)
923 V[tmp_var].reg = nil -- Only temporary allocation
924 -- Optimization: immediate values (imm32) can be stored directly
926 emit(BPF.MEM + BPF.ST + const_width[w], dst_reg, 0, -vinfo.__base, const)
928 emit(BPF.MEM + BPF.STX + const_width[w], dst_reg, src_reg, -vinfo.__base, 0)
929 end
932 end
937 end
938 end,
939 TSETS = function (a, b, c, _) -- TSETS (B[C] = A)
946 -- TODO: support vectorized moves larger than register width
949 -- If changing map value, write to absolute address + offset
952 -- Optimization: immediate values (imm32) can be stored directly
957 end
958 -- Table is already on stack, write to base-relative address
960 -- Optimization: immediate values (imm32) can be stored directly
962 emit(BPF.MEM + BPF.ST + const_width[w], 10, 0, -base.__base + ofs, const)
964 emit(BPF.MEM + BPF.STX + const_width[w], 10, src_reg, -base.__base + ofs, 0)
965 end
968 end
973 end
974 end,
975 TGETB = function (a, b, _, d) -- TGETB (A = B[D])
978 if a ~= b then vset(a) end
979 if base.__map then -- BPF map read (constant)
981 -- Pointer access with a dissector (traditional uses BPF_LD, direct uses BPF_MEM)
985 -- Specialise PTR[0] as dereference operator
993 end
994 end,
995 TGETV = function (a, b, _, d) -- TGETV (A = B[D])
998 if a ~= b then vset(a) end
999 if base.__map then -- BPF map read
1001 -- Pointer access with a dissector (traditional uses BPF_LD, direct uses BPF_MEM)
1005 -- Constant dereference
1010 end
1011 end,
1012 TGETS = function (a, b, c, _) -- TGETS (A = B[C])
1015 if a ~= b then vset(a) end
1018 -- Resolve table key using metatable
1022 end
1023 if not ofs and proto[c] then -- Load new dissector on given offset
1026 -- Loading register from offset is a little bit tricky as there are
1027 -- several data sources and value loading modes with different restrictions
1028 -- such as checking pointer values for NULL compared to using stack.
1030 if a ~= b then vset(a) end
1031 -- Dissected value is probably not constant anymore
1034 -- [SP+K] addressing using R10 (stack pointer)
1035 -- Doesn't need to be checked for NULL
1037 if cdef.isptr(atype) then -- If the member is pointer type, update base pointer with offset
1038 new_const = {__base = base.__base-ofs}
1041 emit(BPF.MEM + BPF.LDX + const_width[w], dst_reg, 10, -base.__base+ofs, 0)
1042 end
1043 -- Pointer access with a dissector (traditional uses BPF_LD, direct uses BPF_MEM)
1048 end
1049 -- Bitfield, must be further narrowed with a bitmask/shift
1053 mask = bit.bor(mask, bit.lshift(1, w*8-i))
1054 end
1056 -- Free optimization: single-bit values need just boolean result
1058 local shift = w*8-bsize-bpos
1061 end
1062 end
1063 end
1067 -- Track direct access to skb data
1068 -- see https://www.kernel.org/doc/Documentation/networking/filter.txt "Direct packet access"
1070 -- Direct access to skb uses skb->data and skb->data_end
1071 -- which are encoded as u32, but are actually pointers
1075 end
1076 end
1077 end
1080 end
1081 end,
1082 -- Loops and branches
1083 CALLM = function (a, b, _, d) -- A = A(A+1, ..., A+D+MULTRES)
1084 -- NYI: Support single result only
1086 end,
1087 CALL = function (a, b, _, d) -- A = A(A+1, ..., A+D-1)
1089 end,
1090 JMP = function (a, _, c, _) -- JMP
1091 -- Discard unused slots after jump
1095 end
1096 end
1097 -- Cross basic block boundary if the jump target isn't provably unreachable
1100 if code.seen_cmp ~= NEVER then -- Do not emit the jump or fixup
1101 -- Store previous CMP insn for reemitting after compensation code
1102 local jmpi = ffi.new('struct bpf_insn', code.insn[code.pc-1])
1103 code.pc = code.pc - 1
1104 -- First branch point, emit compensation code
1107 -- Select scratch register (R0-5) that isn't used as operand
1108 -- in the CMP instruction, as the variable may not be live, after
1109 -- the JMP, but it may be used in the JMP+CMP instruction itself
1115 end
1116 end
1117 -- Force materialization of constants at the end of BB
1120 vreg(i, tmp_reg) -- Load to TMP register (not saved)
1121 reg_spill(i) -- Spill caller-saved registers
1122 end
1123 end
1124 -- Record variable state
1128 -- Variable state already set, emit specific compensation code
1131 end
1132 -- Record pointer NULL check from condition
1133 -- If the condition checks pointer variable against NULL,
1134 -- we can assume it will not be NULL in the fall-through block
1137 -- The null guard can have two forms:
1138 -- if x == nil then goto
1139 -- if x ~= nil then goto
1140 -- First form guarantees that the variable will be non-nil on the following instruction
1141 -- Second form guarantees that the variable will be non-nil at the jump target
1146 vinfo.source = vinfo.source:sub(1, pos - 1)
1147 end
1148 end
1149 end
1150 -- Reemit CMP insn
1152 -- Fuse JMP into previous CMP opcode, mark JMP target for fixup
1153 -- as we don't knot the relative offset in generated code yet
1154 table.insert(val, code.pc-1)
1156 end
1160 elseif c == code.bc_pc + 1 then -- luacheck: ignore 542
1161 -- Eliminate jumps to next immediate instruction
1162 -- e.g. 0002 JMP 1 => 0003
1164 -- We need to synthesise a condition that's always true, however
1165 -- BPF prohibits pointer arithmetic to prevent pointer leaks
1166 -- so we have to clear out one register and use it for cmp that's always true
1168 V[stackslots].reg = nil -- Only temporary allocation
1169 -- First branch point, emit compensation code
1172 -- Force materialization of constants at the end of BB
1175 vreg(i, dst_reg) -- Load to TMP register (not saved)
1176 reg_spill(i) -- Spill caller-saved registers
1177 end
1178 end
1179 -- Record variable state
1182 -- Variable state already set, emit specific compensation code
1185 end
1188 table.insert(val, code.pc-1) -- Fixup JMP target
1189 code.reachable = false -- Code following the JMP is not reachable
1191 end
1192 end,
1193 RET1 = function (a, _, _, _) -- RET1
1194 -- Free optimisation: spilled variable will not be filled again
1196 if i ~= a then v.reg = nil end
1197 end
1198 if V[a].reg ~= 0 then vreg(a, 0) end
1199 -- Convenience: dereference pointer variables
1200 -- e.g. 'return map[k]' will return actual map value, not pointer
1203 end
1206 end,
1207 RET0 = function (_, _, _, _) -- RET0
1211 end,
1214 end
1217 -- Composite instructions
1218 function BC.CALLT(a, _, _, d) -- Tailcall: return A(A+1, ..., A+D-1)
1221 end
1223 -- Always initialize R6 with R1 context
1225 -- Register R6 as context variable (first argument)
1228 assert(V[0].source == V[0].const.source) -- Propagate source annotation from typeinfo
1229 end
1230 -- Register tmpvars
1237 error(string.format("NYI: opcode '0x%02x' (%-04s)", k, op_str))
1238 end
1239 end,
1242 -- Exitting BB straight through, emit compensation code
1245 -- Instruction is reachable from previous line
1246 -- so we must make the variable allocation consistent
1247 -- with the variable allocation at the jump source
1248 -- e.g. 0001 x:R0 = 5
1249 -- 0002 if rand() then goto 0005
1250 -- 0003 x:R0 -> x:stack
1251 -- 0004 y:R0 = 5
1252 -- 0005 x:? = 10 <-- x was in R0 before jump, and stack after jump
1255 -- Instruction isn't reachable from previous line, restore variable layout
1256 -- e.g. RET or condition-less JMP on previous line
1258 end
1259 end
1260 -- Perform fixup of jump targets
1261 -- We need to do this because the number of consumed and emitted
1262 -- bytecode instructions is different
1265 -- Patch JMP source insn with relative offset
1267 code.insn[pc].off = code.pc - 1 - pc
1268 end
1271 end
1272 -- Execute
1276 end
1277 end,
1279 end
1281 -- Emitted code dump
1283 -- This is a very dense MEM instruction decoder without much explanation
1284 -- Refer to https://www.kernel.org/doc/Documentation/networking/filter.txt for instruction format
1286 if mode == BPF.XADD then cls = 5 end -- The only mode
1290 local off = tonumber(ffi.cast('int16_t', ins.off)) -- Reinterpret as signed
1293 if cls == BPF.LDX then src = string.format('[R%d%+d]', ins.src_reg, off) end
1294 if mode == BPF.ABS then src = string.format('skb[%d]', ins.imm) end
1295 if mode == BPF.IND then src = string.format('skb[R%d%+d]', ins.src_reg, ins.imm) end
1297 end
1300 …{'ADD', 'SUB', 'MUL', 'DIV', 'OR', 'AND', 'LSH', 'RSH', 'NEG', 'MOD', 'XOR', 'MOV', 'ARSH', 'END' }
1309 -- This is a very dense ALU instruction decoder without much explanation
1310 -- Refer to https://www.kernel.org/doc/Documentation/networking/filter.txt for instruction format
1311 for i = 0,13 do if 0x10 * i == bit.band(ins.code, 0xf0) then op = i + 1 break end end
1315 …= 5 and op == 9 then target = string.format('\t; %s', helper[ins.imm + 1] or tostring(ins.imm)) end
1317 end
1320 if not code then return end
1327 for i = off or 0, code.pc - 1 do
1335 end
1337 end
1339 end
1342 if not code then return end
1343 print(string.format('-- BPF %s:0-%u', code.insn, code.pc))
1345 end
1348 -- Create code emitter sandbox, include caller locals
1350 -- Include upvalues up to 4 nested scopes back
1351 -- the narrower scope overrides broader scope
1352 for k = 5, 2, -1 do
1356 if not ok or not n then break end
1359 end
1360 end
1364 end
1366 -- Create code emitter and compile LuaJIT bytecode
1367 if type(prog) == 'string' then prog = loadstring(prog) end
1368 -- Create error handler to print traceback
1373 local from, to = 0, 0
1375 from = to
1376 to = string.find(funci.source, '\n', from+1, true) or 0
1377 end
1378 print(funci.loc..':'..string.sub(funci.source, from+1, to-1))
1381 end
1386 end
1387 end
1389 end
1391 -- BPF map interface
1393 __gc = function (map) S.close(map.fd) end,
1394 __len = function(map) return map.max_entries end,
1397 -- Return iterator
1400 -- Get next key
1408 end
1410 if not ok then return nil, err end
1411 -- Get next value
1414 end, map, nil
1415 -- Read for perf event map
1418 -- Caller must either specify PID or CPU
1421 pid = -1
1422 end
1423 -- Create BPF output reader
1430 local reader, err = S.t.perf_reader(S.perf_event_open(pe, pid, cpu or -1))
1431 if not reader then return nil, tostring(err) end
1432 -- Register event reader fd in BPF map
1435 -- Open memory map and start reading
1441 end
1442 -- Signalise this is a map type
1443 end
1445 end
1446 -- Retrieve key
1449 if not ok then return nil, err end
1451 end,
1456 end
1459 end,
1462 -- Linux tracing interface
1465 if S.statfs(path) then return true end
1466 return nil, 'debugfs not accessible: "mount -t debugfs nodev /sys/kernel/debug"? missing sudo?'
1467 end
1469 -- Tracepoint interface
1474 -- Create protocol parser with source probe
1476 end
1477 -- Load the BPF program
1480 -- Open tracepoint and attach
1484 end,
1487 -- Open tracepoint
1489 -- Open tracepoint and compile tracepoint type
1492 -- Open tracepoint reader and create interface
1495 end
1498 -- Load BPF program
1501 end
1504 -- Open tracepoint and attach
1509 end
1515 end
1522 end
1523 -- Create GC closure for reader to close BPF program
1524 -- and detach probe in correct order
1529 end)
1531 end
1533 -- Module interface
1540 if not key_ctype then key_ctype = ffi.typeof('uint32_t') end
1541 if not val_ctype then val_ctype = ffi.typeof('uint32_t') end
1542 if not max_entries then max_entries = 4096 end
1543 -- Special case for BPF_MAP_STACK_TRACE
1547 end
1549 if not fd then return nil, tostring(err) end
1560 end,
1562 -- Expect socket type, if sock is string then assume it's
1563 -- an interface name (e.g. 'lo'), if it's a number then typecast it as a socket
1574 elseif ffi.istype(S.t.fd, sock) then -- luacheck: ignore
1575 -- No cast required
1578 end
1579 -- Load program and attach it to socket
1582 end
1587 end,
1590 -- Return tracepoint instance if no program specified
1591 -- this allows free specialisation of arg0 to tracepoint type
1593 -- Load the BPF program
1596 end
1598 end,
1601 -- Open tracepoint and attach
1604 end,
1607 -- Translate symbol to address
1609 if not S.statfs(obj) then return nil, S.t.error(S.c.E.NOENT) end
1610 -- Resolve Elf object (no support for anything else)
1613 if not sym then return nil, 'no such symbol' end
1614 sym = sym.st_value - elf:loadaddr()
1617 -- Convert it to expected uprobe format
1621 end,
1626 end,
1629 __call = function (_, prog) return compile(prog) end,