bpf_jit_machdep.c revision 181648
167754Smsmith/*- 267754Smsmith * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy) 367754Smsmith * Copyright (C) 2005-2008 Jung-uk Kim <jkim@FreeBSD.org> 4128212Snjl * All rights reserved. 567754Smsmith * 667754Smsmith * Redistribution and use in source and binary forms, with or without 767754Smsmith * modification, are permitted provided that the following conditions 867754Smsmith * are met: 967754Smsmith * 1067754Smsmith * 1. Redistributions of source code must retain the above copyright 1167754Smsmith * notice, this list of conditions and the following disclaimer. 12126372Snjl * 2. Redistributions in binary form must reproduce the above copyright 1370243Smsmith * notice, this list of conditions and the following disclaimer in the 1467754Smsmith * documentation and/or other materials provided with the distribution. 1567754Smsmith * 3. Neither the name of the Politecnico di Torino nor the names of its 1667754Smsmith * contributors may be used to endorse or promote products derived from 1767754Smsmith * this software without specific prior written permission. 1867754Smsmith * 1967754Smsmith * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2067754Smsmith * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2167754Smsmith * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2267754Smsmith * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2367754Smsmith * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2467754Smsmith * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2567754Smsmith * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2667754Smsmith * DATA, OR PROFITS; OR BUSINESS intERRUPTION) HOWEVER CAUSED AND ON ANY 2767754Smsmith * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2867754Smsmith * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2967754Smsmith * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3067754Smsmith */ 3167754Smsmith 3267754Smsmith#include <sys/cdefs.h> 3367754Smsmith__FBSDID("$FreeBSD: head/sys/i386/i386/bpf_jit_machdep.c 181648 2008-08-12 21:31:31Z jkim $"); 3467754Smsmith 3567754Smsmith#include "opt_bpf.h" 3667754Smsmith 3767754Smsmith#include <sys/param.h> 3867754Smsmith#include <sys/systm.h> 3967754Smsmith#include <sys/kernel.h> 4067754Smsmith#include <sys/types.h> 4167754Smsmith#include <sys/socket.h> 4267754Smsmith#include <sys/malloc.h> 4367754Smsmith 4467754Smsmith#include <net/if.h> 4567754Smsmith#include <net/bpf.h> 4667754Smsmith#include <net/bpf_jitter.h> 4767754Smsmith 4867754Smsmith#include <i386/i386/bpf_jit_machdep.h> 4967754Smsmith 5067754Smsmithbpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, int *); 5167754Smsmith 5267754Smsmith/* 5367754Smsmith * emit routine to update the jump table 5467754Smsmith */ 5567754Smsmithstatic void 5667754Smsmithemit_length(bpf_bin_stream *stream, u_int value, u_int len) 5767754Smsmith{ 5867754Smsmith 5967754Smsmith (stream->refs)[stream->bpf_pc] += len; 6067754Smsmith stream->cur_ip += len; 6167754Smsmith} 6267754Smsmith 6367754Smsmith/* 6467754Smsmith * emit routine to output the actual binary code 6567754Smsmith */ 6667754Smsmithstatic void 6767754Smsmithemit_code(bpf_bin_stream *stream, u_int value, u_int len) 6867754Smsmith{ 6967754Smsmith 7067754Smsmith switch (len) { 7167754Smsmith case 1: 7267754Smsmith stream->ibuf[stream->cur_ip] = (u_char)value; 7367754Smsmith stream->cur_ip++; 7467754Smsmith break; 7567754Smsmith 7667754Smsmith case 2: 7767754Smsmith *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 7867754Smsmith stream->cur_ip += 2; 7967754Smsmith break; 8067754Smsmith 8167754Smsmith case 4: 8267754Smsmith *((u_int *)(stream->ibuf + stream->cur_ip)) = value; 8367754Smsmith stream->cur_ip += 4; 8467754Smsmith break; 8567754Smsmith } 8667754Smsmith 8767754Smsmith return; 8867754Smsmith} 8967754Smsmith 9067754Smsmith/* 9167754Smsmith * Function that does the real stuff 9267754Smsmith */ 9367754Smsmithbpf_filter_func 9467754Smsmithbpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem) 9567754Smsmith{ 9667754Smsmith struct bpf_insn *ins; 9767754Smsmith u_int i, pass; 9867754Smsmith bpf_bin_stream stream; 9967754Smsmith 10067754Smsmith /* 10167754Smsmith * NOTE: do not modify the name of this variable, as it's used by 10267754Smsmith * the macros to emit code. 10367754Smsmith */ 10467754Smsmith emit_func emitm; 10567754Smsmith 10667754Smsmith /* Do not compile an empty filter. */ 10767754Smsmith if (nins == 0) 10867754Smsmith return (NULL); 10967754Smsmith 11067754Smsmith /* Allocate the reference table for the jumps */ 11167754Smsmith stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int), 11267754Smsmith M_BPFJIT, M_NOWAIT); 11367754Smsmith if (stream.refs == NULL) 11467754Smsmith return (NULL); 11567754Smsmith 11667754Smsmith /* Reset the reference table */ 11767754Smsmith for (i = 0; i < nins + 1; i++) 11867754Smsmith stream.refs[i] = 0; 11967754Smsmith 12067754Smsmith stream.cur_ip = 0; 12167754Smsmith stream.bpf_pc = 0; 12267754Smsmith 12377424Smsmith /* 12491116Smsmith * the first pass will emit the lengths of the instructions 12567754Smsmith * to create the reference table 12667754Smsmith */ 12767754Smsmith emitm = emit_length; 12867754Smsmith 12967754Smsmith pass = 0; 13067754Smsmith for (;;) { 13167754Smsmith ins = prog; 132107325Siwasaki 13367754Smsmith /* create the procedure header */ 13477424Smsmith PUSH(EBP); 13567754Smsmith MOVrd(ESP, EBP); 13667754Smsmith PUSH(EDI); 13767754Smsmith PUSH(ESI); 138114237Snjl PUSH(EBX); 139114237Snjl MOVodd(8, EBP, EBX); 140107325Siwasaki MOVodd(16, EBP, EDI); 14167754Smsmith 14267754Smsmith for (i = 0; i < nins; i++) { 14367754Smsmith stream.bpf_pc++; 14467754Smsmith 14567754Smsmith switch (ins->code) { 14667754Smsmith default: 14767754Smsmith return (NULL); 14867754Smsmith 14967754Smsmith case BPF_RET|BPF_K: 15067754Smsmith MOVid(ins->k, EAX); 15167754Smsmith POP(EBX); 15267754Smsmith POP(ESI); 15367754Smsmith POP(EDI); 15467754Smsmith LEAVE_RET(); 15567754Smsmith break; 15667754Smsmith 15767754Smsmith case BPF_RET|BPF_A: 15891116Smsmith POP(EBX); 15967754Smsmith POP(ESI); 16067754Smsmith POP(EDI); 16167754Smsmith LEAVE_RET(); 16267754Smsmith break; 16367754Smsmith 16491116Smsmith case BPF_LD|BPF_W|BPF_ABS: 16567754Smsmith MOVid(ins->k, ECX); 16671867Smsmith MOVrd(ECX, ESI); 167102550Siwasaki ADDib(sizeof(int), ECX); 16882367Smsmith CMPrd(EDI, ECX); 16967754Smsmith JLEb(7); 170114237Snjl ZEROrd(EAX); 17177424Smsmith POP(EBX); 17291116Smsmith POP(ESI); 17371867Smsmith POP(EDI); 17471867Smsmith LEAVE_RET(); 175123315Snjl MOVobd(EBX, ESI, EAX); 17691116Smsmith BSWAP(EAX); 17771867Smsmith break; 17880062Smsmith 17971867Smsmith case BPF_LD|BPF_H|BPF_ABS: 18067754Smsmith ZEROrd(EAX); 18171867Smsmith MOVid(ins->k, ECX); 18267754Smsmith MOVrd(ECX, ESI); 18367754Smsmith ADDib(sizeof(short), ECX); 184114237Snjl CMPrd(EDI, ECX); 185107325Siwasaki JLEb(5); 18667754Smsmith POP(EBX); 18767754Smsmith POP(ESI); 18867754Smsmith POP(EDI); 18967754Smsmith LEAVE_RET(); 19067754Smsmith MOVobw(EBX, ESI, AX); 19167754Smsmith SWAP_AX(); 19299146Siwasaki break; 19367754Smsmith 194128212Snjl case BPF_LD|BPF_B|BPF_ABS: 195128212Snjl ZEROrd(EAX); 196128212Snjl MOVid(ins->k, ECX); 197128212Snjl CMPrd(EDI, ECX); 198128212Snjl JLEb(5); 199128212Snjl POP(EBX); 200128212Snjl POP(ESI); 20167754Smsmith POP(EDI); 202107325Siwasaki LEAVE_RET(); 20367754Smsmith MOVobb(EBX, ECX, AL); 20483174Smsmith break; 205123315Snjl 206117521Snjl case BPF_LD|BPF_W|BPF_LEN: 207123315Snjl MOVodd(12, EBP, EAX); 20867754Smsmith break; 20967754Smsmith 21067754Smsmith case BPF_LDX|BPF_W|BPF_LEN: 21167754Smsmith MOVodd(12, EBP, EDX); 21267754Smsmith break; 21367754Smsmith 21467754Smsmith case BPF_LD|BPF_W|BPF_IND: 21567754Smsmith MOVid(ins->k, ECX); 21667754Smsmith ADDrd(EDX, ECX); 21767754Smsmith MOVrd(ECX, ESI); 21867754Smsmith ADDib(sizeof(int), ECX); 21967754Smsmith CMPrd(EDI, ECX); 22067754Smsmith JLEb(7); 22167754Smsmith ZEROrd(EAX); 22267754Smsmith POP(EBX); 22367754Smsmith POP(ESI); 22467754Smsmith POP(EDI); 22567754Smsmith LEAVE_RET(); 22667754Smsmith MOVobd(EBX, ESI, EAX); 22767754Smsmith BSWAP(EAX); 22867754Smsmith break; 229107325Siwasaki 23067754Smsmith case BPF_LD|BPF_H|BPF_IND: 231117521Snjl ZEROrd(EAX); 232123315Snjl MOVid(ins->k, ECX); 233117521Snjl ADDrd(EDX, ECX); 234123315Snjl MOVrd(ECX, ESI); 23567754Smsmith ADDib(sizeof(short), ECX); 23667754Smsmith CMPrd(EDI, ECX); 23767754Smsmith JLEb(5); 23867754Smsmith POP(EBX); 23967754Smsmith POP(ESI); 24067754Smsmith POP(EDI); 24167754Smsmith LEAVE_RET(); 24267754Smsmith MOVobw(EBX, ESI, AX); 24367754Smsmith SWAP_AX(); 24467754Smsmith break; 245107325Siwasaki 24667754Smsmith case BPF_LD|BPF_B|BPF_IND: 24777424Smsmith ZEROrd(EAX); 24867754Smsmith MOVid(ins->k, ECX); 24967754Smsmith ADDrd(EDX, ECX); 25067754Smsmith CMPrd(EDI, ECX); 25167754Smsmith JLEb(5); 252107325Siwasaki POP(EBX); 25367754Smsmith POP(ESI); 25467754Smsmith POP(EDI); 25567754Smsmith LEAVE_RET(); 25667754Smsmith MOVobb(EBX, ECX, AL); 25767754Smsmith break; 25867754Smsmith 25967754Smsmith case BPF_LDX|BPF_MSH|BPF_B: 26067754Smsmith MOVid(ins->k, ECX); 26167754Smsmith CMPrd(EDI, ECX); 26267754Smsmith JLEb(7); 26367754Smsmith ZEROrd(EAX); 26467754Smsmith POP(EBX); 26569450Smsmith POP(ESI); 26667754Smsmith POP(EDI); 26767754Smsmith LEAVE_RET(); 26867754Smsmith ZEROrd(EDX); 26991116Smsmith MOVobb(EBX, ECX, DL); 27067754Smsmith ANDib(0x0f, DL); 27167754Smsmith SHLib(2, EDX); 27267754Smsmith break; 27367754Smsmith 27467754Smsmith case BPF_LD|BPF_IMM: 27567754Smsmith MOVid(ins->k, EAX); 27691116Smsmith break; 27767754Smsmith 27867754Smsmith case BPF_LDX|BPF_IMM: 27991116Smsmith MOVid(ins->k, EDX); 28067754Smsmith break; 28167754Smsmith 282114237Snjl case BPF_LD|BPF_MEM: 283107325Siwasaki MOVid((uintptr_t)mem, ECX); 28467754Smsmith MOVid(ins->k * 4, ESI); 285107325Siwasaki MOVobd(ECX, ESI, EAX); 28667754Smsmith break; 287107325Siwasaki 288107325Siwasaki case BPF_LDX|BPF_MEM: 289107325Siwasaki MOVid((uintptr_t)mem, ECX); 290107325Siwasaki MOVid(ins->k * 4, ESI); 29167754Smsmith MOVobd(ECX, ESI, EDX); 292107325Siwasaki break; 293107325Siwasaki 294107325Siwasaki case BPF_ST: 295107325Siwasaki /* 296107325Siwasaki * XXX this command and the following could 29767754Smsmith * be optimized if the previous instruction 29867754Smsmith * was already of this type 29967754Smsmith */ 30067754Smsmith MOVid((uintptr_t)mem, ECX); 30167754Smsmith MOVid(ins->k * 4, ESI); 30287031Smsmith MOVomd(EAX, ECX, ESI); 30367754Smsmith break; 30467754Smsmith 30567754Smsmith case BPF_STX: 30667754Smsmith MOVid((uintptr_t)mem, ECX); 30767754Smsmith MOVid(ins->k * 4, ESI); 30867754Smsmith MOVomd(EDX, ECX, ESI); 30967754Smsmith break; 31091116Smsmith 31187031Smsmith case BPF_JMP|BPF_JA: 31291116Smsmith JMP(stream.refs[stream.bpf_pc + ins->k] - 31387031Smsmith stream.refs[stream.bpf_pc]); 31487031Smsmith break; 31567754Smsmith 31667754Smsmith case BPF_JMP|BPF_JGT|BPF_K: 31767754Smsmith CMPid(ins->k, EAX); 31867754Smsmith /* 5 is the size of the following JMP */ 31967754Smsmith JG(stream.refs[stream.bpf_pc + ins->jt] - 32067754Smsmith stream.refs[stream.bpf_pc] + 5 ); 32167754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jf] - 32267754Smsmith stream.refs[stream.bpf_pc]); 32367754Smsmith break; 32467754Smsmith 32567754Smsmith case BPF_JMP|BPF_JGE|BPF_K: 32691116Smsmith CMPid(ins->k, EAX); 32767754Smsmith JGE(stream.refs[stream.bpf_pc + ins->jt] - 32867754Smsmith stream.refs[stream.bpf_pc] + 5); 32967754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jf] - 33067754Smsmith stream.refs[stream.bpf_pc]); 33167754Smsmith break; 33267754Smsmith 33367754Smsmith case BPF_JMP|BPF_JEQ|BPF_K: 33467754Smsmith CMPid(ins->k, EAX); 33567754Smsmith JE(stream.refs[stream.bpf_pc + ins->jt] - 33667754Smsmith stream.refs[stream.bpf_pc] + 5); 33767754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jf] - 33867754Smsmith stream.refs[stream.bpf_pc]); 33967754Smsmith break; 34067754Smsmith 341107325Siwasaki case BPF_JMP|BPF_JSET|BPF_K: 342107325Siwasaki MOVrd(EAX, ECX); 34367754Smsmith ANDid(ins->k, ECX); 34467754Smsmith JE(stream.refs[stream.bpf_pc + ins->jf] - 34567754Smsmith stream.refs[stream.bpf_pc] + 5); 34677424Smsmith JMP(stream.refs[stream.bpf_pc + ins->jt] - 34767754Smsmith stream.refs[stream.bpf_pc]); 34867754Smsmith break; 34967754Smsmith 350107325Siwasaki case BPF_JMP|BPF_JGT|BPF_X: 35167754Smsmith CMPrd(EDX, EAX); 35267754Smsmith JA(stream.refs[stream.bpf_pc + ins->jt] - 35367754Smsmith stream.refs[stream.bpf_pc] + 5); 35467754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jf] - 355107325Siwasaki stream.refs[stream.bpf_pc]); 35667754Smsmith break; 35767754Smsmith 35867754Smsmith case BPF_JMP|BPF_JGE|BPF_X: 35967754Smsmith CMPrd(EDX, EAX); 36067754Smsmith JAE(stream.refs[stream.bpf_pc + ins->jt] - 36167754Smsmith stream.refs[stream.bpf_pc] + 5); 36267754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jf] - 36367754Smsmith stream.refs[stream.bpf_pc]); 36467754Smsmith break; 36591116Smsmith 36691116Smsmith case BPF_JMP|BPF_JEQ|BPF_X: 36767754Smsmith CMPrd(EDX, EAX); 36867754Smsmith JE(stream.refs[stream.bpf_pc + ins->jt] - 36967754Smsmith stream.refs[stream.bpf_pc] + 5); 37067754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jf] - 37167754Smsmith stream.refs[stream.bpf_pc]); 37267754Smsmith break; 37367754Smsmith 37491116Smsmith case BPF_JMP|BPF_JSET|BPF_X: 37567754Smsmith MOVrd(EAX, ECX); 37667754Smsmith ANDrd(EDX, ECX); 37767754Smsmith JE(stream.refs[stream.bpf_pc + ins->jf] - 37867754Smsmith stream.refs[stream.bpf_pc] + 5); 37967754Smsmith JMP(stream.refs[stream.bpf_pc + ins->jt] - 38067754Smsmith stream.refs[stream.bpf_pc]); 381102550Siwasaki break; 38267754Smsmith 38367754Smsmith case BPF_ALU|BPF_ADD|BPF_X: 384102550Siwasaki ADDrd(EDX, EAX); 38567754Smsmith break; 38667754Smsmith 38767754Smsmith case BPF_ALU|BPF_SUB|BPF_X: 38867754Smsmith SUBrd(EDX, EAX); 38967754Smsmith break; 39077424Smsmith 39167754Smsmith case BPF_ALU|BPF_MUL|BPF_X: 392114237Snjl MOVrd(EDX, ECX); 39367754Smsmith MULrd(EDX); 39467754Smsmith MOVrd(ECX, EDX); 39567754Smsmith break; 39667754Smsmith 397107325Siwasaki case BPF_ALU|BPF_DIV|BPF_X: 39867754Smsmith CMPid(0, EDX); 39991116Smsmith JNEb(7); 40077424Smsmith ZEROrd(EAX); 40167754Smsmith POP(EBX); 40267754Smsmith POP(ESI); 40367754Smsmith POP(EDI); 40477424Smsmith LEAVE_RET(); 40577424Smsmith MOVrd(EDX, ECX); 40671867Smsmith ZEROrd(EDX); 40771867Smsmith DIVrd(ECX); 40891116Smsmith MOVrd(ECX, EDX); 40971867Smsmith break; 41087031Smsmith 41171867Smsmith case BPF_ALU|BPF_AND|BPF_X: 41271867Smsmith ANDrd(EDX, EAX); 41371867Smsmith break; 41467754Smsmith 41567754Smsmith case BPF_ALU|BPF_OR|BPF_X: 41667754Smsmith ORrd(EDX, EAX); 41767754Smsmith break; 41867754Smsmith 41967754Smsmith case BPF_ALU|BPF_LSH|BPF_X: 42067754Smsmith MOVrd(EDX, ECX); 42187031Smsmith SHL_CLrb(EAX); 42267754Smsmith break; 42367754Smsmith 42467754Smsmith case BPF_ALU|BPF_RSH|BPF_X: 42567754Smsmith MOVrd(EDX, ECX); 42667754Smsmith SHR_CLrb(EAX); 42767754Smsmith break; 42867754Smsmith 42991116Smsmith case BPF_ALU|BPF_ADD|BPF_K: 43091116Smsmith ADD_EAXi(ins->k); 43167754Smsmith break; 43267754Smsmith 433107325Siwasaki case BPF_ALU|BPF_SUB|BPF_K: 43467754Smsmith SUB_EAXi(ins->k); 43567754Smsmith break; 43667754Smsmith 43767754Smsmith case BPF_ALU|BPF_MUL|BPF_K: 43867754Smsmith MOVrd(EDX, ECX); 43967754Smsmith MOVid(ins->k, EDX); 44067754Smsmith MULrd(EDX); 44167754Smsmith MOVrd(ECX, EDX); 44267754Smsmith break; 44367754Smsmith 44467754Smsmith case BPF_ALU|BPF_DIV|BPF_K: 44567754Smsmith MOVrd(EDX, ECX); 44667754Smsmith ZEROrd(EDX); 44791116Smsmith MOVid(ins->k, ESI); 44867754Smsmith DIVrd(ESI); 44982367Smsmith MOVrd(ECX, EDX); 45087031Smsmith break; 45167754Smsmith 45267754Smsmith case BPF_ALU|BPF_AND|BPF_K: 45367754Smsmith ANDid(ins->k, EAX); 45467754Smsmith break; 45567754Smsmith 45667754Smsmith case BPF_ALU|BPF_OR|BPF_K: 45767754Smsmith ORid(ins->k, EAX); 45867754Smsmith break; 45967754Smsmith 46067754Smsmith case BPF_ALU|BPF_LSH|BPF_K: 46167754Smsmith SHLib((ins->k) & 0xff, EAX); 46267754Smsmith break; 46367754Smsmith 46467754Smsmith case BPF_ALU|BPF_RSH|BPF_K: 46567754Smsmith SHRib((ins->k) & 0xff, EAX); 46667754Smsmith break; 46767754Smsmith 46867754Smsmith case BPF_ALU|BPF_NEG: 46967754Smsmith NEGd(EAX); 47067754Smsmith break; 471 472 case BPF_MISC|BPF_TAX: 473 MOVrd(EAX, EDX); 474 break; 475 476 case BPF_MISC|BPF_TXA: 477 MOVrd(EDX, EAX); 478 break; 479 } 480 ins++; 481 } 482 483 pass++; 484 if (pass == 2) 485 break; 486 487 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 488 if (stream.ibuf == NULL) { 489 free(stream.refs, M_BPFJIT); 490 return (NULL); 491 } 492 493 /* 494 * modify the reference table to contain the offsets and 495 * not the lengths of the instructions 496 */ 497 for (i = 1; i < nins + 1; i++) 498 stream.refs[i] += stream.refs[i - 1]; 499 500 /* Reset the counters */ 501 stream.cur_ip = 0; 502 stream.bpf_pc = 0; 503 504 /* the second pass creates the actual code */ 505 emitm = emit_code; 506 } 507 508 /* 509 * the reference table is needed only during compilation, 510 * now we can free it 511 */ 512 free(stream.refs, M_BPFJIT); 513 514 return ((bpf_filter_func)stream.ibuf); 515} 516