bpf_jit_machdep.c revision 179968
1169689Skan/*- 2169689Skan * Copyright (c) 2002 - 2003 NetGroup, Politecnico di Torino (Italy) 3169689Skan * Copyright (c) 2005 Jung-uk Kim <jkim@FreeBSD.org> 4169689Skan * All rights reserved. 5169689Skan * 6169689Skan * Redistribution and use in source and binary forms, with or without 7169689Skan * modification, are permitted provided that the following conditions 8169689Skan * are met: 9169689Skan * 10169689Skan * 1. Redistributions of source code must retain the above copyright 11169689Skan * notice, this list of conditions and the following disclaimer. 12169689Skan * 2. Redistributions in binary form must reproduce the above copyright 13169689Skan * notice, this list of conditions and the following disclaimer in the 14169689Skan * documentation and/or other materials provided with the distribution. 15169689Skan * 3. Neither the name of the Politecnico di Torino nor the names of its 16169689Skan * contributors may be used to endorse or promote products derived from 17169689Skan * this software without specific prior written permission. 18169689Skan * 19169689Skan * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20169689Skan * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21169689Skan * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22169689Skan * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23169689Skan * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24169689Skan * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25169689Skan * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26169689Skan * DATA, OR PROFITS; OR BUSINESS intERRUPTION) HOWEVER CAUSED AND ON ANY 27169689Skan * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28169689Skan * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29169689Skan * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30169689Skan */ 31169689Skan 32169689Skan#include <sys/cdefs.h> 33169689Skan__FBSDID("$FreeBSD: head/sys/i386/i386/bpf_jit_machdep.c 179968 2008-06-23 23:10:11Z jkim $"); 34169689Skan 35169689Skan#include "opt_bpf.h" 36169689Skan 37169689Skan#include <sys/param.h> 38169689Skan#include <sys/systm.h> 39169689Skan#include <sys/kernel.h> 40169689Skan#include <sys/types.h> 41169689Skan#include <sys/socket.h> 42169689Skan#include <sys/malloc.h> 43169689Skan 44169689Skan#include <net/if.h> 45169689Skan#include <net/bpf.h> 46169689Skan#include <net/bpf_jitter.h> 47169689Skan 48169689Skan#include <i386/i386/bpf_jit_machdep.h> 49169689Skan 50169689Skanbpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, int *); 51169689Skan 52169689Skan/* 53169689Skan * emit routine to update the jump table 54169689Skan */ 55169689Skanstatic void 56169689Skanemit_length(bpf_bin_stream *stream, u_int value, u_int len) 57169689Skan{ 58169689Skan 59169689Skan (stream->refs)[stream->bpf_pc] += len; 60169689Skan stream->cur_ip += len; 61169689Skan} 62169689Skan 63169689Skan/* 64169689Skan * emit routine to output the actual binary code 65169689Skan */ 66169689Skanstatic void 67169689Skanemit_code(bpf_bin_stream *stream, u_int value, u_int len) 68169689Skan{ 69169689Skan 70169689Skan switch (len) { 71169689Skan case 1: 72169689Skan stream->ibuf[stream->cur_ip] = (u_char)value; 73169689Skan stream->cur_ip++; 74169689Skan break; 75169689Skan 76169689Skan case 2: 77169689Skan *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 78169689Skan stream->cur_ip += 2; 79169689Skan break; 80169689Skan 81169689Skan case 4: 82169689Skan *((u_int *)(stream->ibuf + stream->cur_ip)) = value; 83169689Skan stream->cur_ip += 4; 84169689Skan break; 85169689Skan } 86169689Skan 87169689Skan return; 88169689Skan} 89169689Skan 90169689Skan/* 91169689Skan * Function that does the real stuff 92169689Skan */ 93169689Skanbpf_filter_func 94169689Skanbpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem) 95169689Skan{ 96169689Skan struct bpf_insn *ins; 97169689Skan u_int i, pass; 98169689Skan bpf_bin_stream stream; 99169689Skan 100169689Skan /* 101169689Skan * NOTE: do not modify the name of this variable, as it's used by 102169689Skan * the macros to emit code. 103169689Skan */ 104169689Skan emit_func emitm; 105169689Skan 106169689Skan /* Do not compile an empty filter. */ 107169689Skan if (nins == 0) 108169689Skan return NULL; 109169689Skan 110169689Skan /* Allocate the reference table for the jumps */ 111169689Skan stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int), 112169689Skan M_BPFJIT, M_NOWAIT); 113169689Skan if (stream.refs == NULL) 114169689Skan return NULL; 115169689Skan 116169689Skan /* Reset the reference table */ 117169689Skan for (i = 0; i < nins + 1; i++) 118169689Skan stream.refs[i] = 0; 119169689Skan 120169689Skan stream.cur_ip = 0; 121169689Skan stream.bpf_pc = 0; 122169689Skan 123169689Skan /* 124169689Skan * the first pass will emit the lengths of the instructions 125169689Skan * to create the reference table 126169689Skan */ 127169689Skan emitm = emit_length; 128169689Skan 129169689Skan pass = 0; 130169689Skan for (;;) { 131169689Skan ins = prog; 132169689Skan 133169689Skan /* create the procedure header */ 134169689Skan PUSH(EBP); 135169689Skan MOVrd(ESP, EBP); 136169689Skan PUSH(EDI); 137169689Skan PUSH(ESI); 138169689Skan PUSH(EBX); 139169689Skan MOVodd(8, EBP, EBX); 140169689Skan 141169689Skan for (i = 0; i < nins; i++) { 142169689Skan stream.bpf_pc++; 143169689Skan 144169689Skan switch (ins->code) { 145169689Skan default: 146169689Skan return NULL; 147169689Skan 148169689Skan case BPF_RET|BPF_K: 149169689Skan MOVid(ins->k, EAX); 150169689Skan POP(EBX); 151169689Skan POP(ESI); 152169689Skan POP(EDI); 153169689Skan LEAVE_RET(); 154169689Skan break; 155169689Skan 156169689Skan case BPF_RET|BPF_A: 157169689Skan POP(EBX); 158169689Skan POP(ESI); 159169689Skan POP(EDI); 160169689Skan LEAVE_RET(); 161169689Skan break; 162169689Skan 163169689Skan case BPF_LD|BPF_W|BPF_ABS: 164169689Skan MOVid(ins->k, ECX); 165169689Skan MOVrd(ECX, ESI); 166169689Skan ADDib(sizeof(int), ECX); 167169689Skan CMPodd(0x10, EBP, ECX); 168169689Skan JLEb(7); 169169689Skan ZERO_EAX(); 170169689Skan POP(EBX); 171169689Skan POP(ESI); 172169689Skan POP(EDI); 173169689Skan LEAVE_RET(); 174169689Skan MOVobd(EBX, ESI, EAX); 175169689Skan BSWAP(EAX); 176169689Skan break; 177169689Skan 178169689Skan case BPF_LD|BPF_H|BPF_ABS: 179169689Skan ZERO_EAX(); 180169689Skan MOVid(ins->k, ECX); 181169689Skan MOVrd(ECX, ESI); 182169689Skan ADDib(sizeof(short), ECX); 183169689Skan CMPodd(0x10, EBP, ECX); 184169689Skan JLEb(5); 185169689Skan POP(EBX); 186169689Skan POP(ESI); 187169689Skan POP(EDI); 188169689Skan LEAVE_RET(); 189169689Skan MOVobw(EBX, ESI, AX); 190169689Skan SWAP_AX(); 191169689Skan break; 192169689Skan 193169689Skan case BPF_LD|BPF_B|BPF_ABS: 194169689Skan ZERO_EAX(); 195169689Skan MOVid(ins->k, ECX); 196169689Skan CMPodd(0x10, EBP, ECX); 197169689Skan JLEb(5); 198169689Skan POP(EBX); 199169689Skan POP(ESI); 200169689Skan POP(EDI); 201169689Skan LEAVE_RET(); 202169689Skan MOVobb(EBX, ECX, AL); 203169689Skan break; 204169689Skan 205169689Skan case BPF_LD|BPF_W|BPF_LEN: 206169689Skan MOVodd(0xc, EBP, EAX); 207169689Skan break; 208169689Skan 209169689Skan case BPF_LDX|BPF_W|BPF_LEN: 210169689Skan MOVodd(0xc, EBP, EDX); 211169689Skan break; 212169689Skan 213169689Skan case BPF_LD|BPF_W|BPF_IND: 214169689Skan MOVid(ins->k, ECX); 215169689Skan ADDrd(EDX, ECX); 216169689Skan MOVrd(ECX, ESI); 217169689Skan ADDib(sizeof(int), ECX); 218169689Skan CMPodd(0x10, EBP, ECX); 219169689Skan JLEb(7); 220169689Skan ZERO_EAX(); 221169689Skan POP(EBX); 222169689Skan POP(ESI); 223169689Skan POP(EDI); 224169689Skan LEAVE_RET(); 225169689Skan MOVobd(EBX, ESI, EAX); 226169689Skan BSWAP(EAX); 227169689Skan break; 228169689Skan 229169689Skan case BPF_LD|BPF_H|BPF_IND: 230169689Skan ZERO_EAX(); 231169689Skan MOVid(ins->k, ECX); 232169689Skan ADDrd(EDX, ECX); 233169689Skan MOVrd(ECX, ESI); 234169689Skan ADDib(sizeof(short), ECX); 235169689Skan CMPodd(0x10, EBP, ECX); 236169689Skan JLEb(5); 237169689Skan POP(EBX); 238169689Skan POP(ESI); 239169689Skan POP(EDI); 240169689Skan LEAVE_RET(); 241169689Skan MOVobw(EBX, ESI, AX); 242169689Skan SWAP_AX(); 243169689Skan break; 244169689Skan 245169689Skan case BPF_LD|BPF_B|BPF_IND: 246169689Skan ZERO_EAX(); 247169689Skan MOVid(ins->k, ECX); 248169689Skan ADDrd(EDX, ECX); 249169689Skan CMPodd(0x10, EBP, ECX); 250169689Skan JLEb(5); 251169689Skan POP(EBX); 252169689Skan POP(ESI); 253169689Skan POP(EDI); 254169689Skan LEAVE_RET(); 255169689Skan MOVobb(EBX, ECX, AL); 256169689Skan break; 257169689Skan 258169689Skan case BPF_LDX|BPF_MSH|BPF_B: 259169689Skan MOVid(ins->k, ECX); 260169689Skan CMPodd(0x10, EBP, ECX); 261169689Skan JLEb(7); 262169689Skan ZERO_EAX(); 263169689Skan POP(EBX); 264169689Skan POP(ESI); 265169689Skan POP(EDI); 266169689Skan LEAVE_RET(); 267169689Skan ZERO_EDX(); 268169689Skan MOVobb(EBX, ECX, DL); 269169689Skan ANDib(0xf, DL); 270169689Skan SHLib(2, EDX); 271169689Skan break; 272169689Skan 273169689Skan case BPF_LD|BPF_IMM: 274169689Skan MOVid(ins->k, EAX); 275169689Skan break; 276169689Skan 277169689Skan case BPF_LDX|BPF_IMM: 278169689Skan MOVid(ins->k, EDX); 279169689Skan break; 280169689Skan 281169689Skan case BPF_LD|BPF_MEM: 282169689Skan MOVid((uintptr_t)mem, ECX); 283169689Skan MOVid(ins->k * 4, ESI); 284169689Skan MOVobd(ECX, ESI, EAX); 285169689Skan break; 286169689Skan 287169689Skan case BPF_LDX|BPF_MEM: 288169689Skan MOVid((uintptr_t)mem, ECX); 289169689Skan MOVid(ins->k * 4, ESI); 290169689Skan MOVobd(ECX, ESI, EDX); 291169689Skan break; 292169689Skan 293169689Skan case BPF_ST: 294169689Skan /* 295169689Skan * XXX this command and the following could 296169689Skan * be optimized if the previous instruction 297169689Skan * was already of this type 298169689Skan */ 299169689Skan MOVid((uintptr_t)mem, ECX); 300169689Skan MOVid(ins->k * 4, ESI); 301169689Skan MOVomd(EAX, ECX, ESI); 302169689Skan break; 303169689Skan 304169689Skan case BPF_STX: 305169689Skan MOVid((uintptr_t)mem, ECX); 306169689Skan MOVid(ins->k * 4, ESI); 307169689Skan MOVomd(EDX, ECX, ESI); 308169689Skan break; 309169689Skan 310169689Skan case BPF_JMP|BPF_JA: 311169689Skan JMP(stream.refs[stream.bpf_pc + ins->k] - 312169689Skan stream.refs[stream.bpf_pc]); 313169689Skan break; 314169689Skan 315169689Skan case BPF_JMP|BPF_JGT|BPF_K: 316169689Skan CMPid(ins->k, EAX); 317169689Skan /* 5 is the size of the following JMP */ 318169689Skan JG(stream.refs[stream.bpf_pc + ins->jt] - 319169689Skan stream.refs[stream.bpf_pc] + 5 ); 320169689Skan JMP(stream.refs[stream.bpf_pc + ins->jf] - 321169689Skan stream.refs[stream.bpf_pc]); 322169689Skan break; 323169689Skan 324169689Skan case BPF_JMP|BPF_JGE|BPF_K: 325169689Skan CMPid(ins->k, EAX); 326169689Skan JGE(stream.refs[stream.bpf_pc + ins->jt] - 327169689Skan stream.refs[stream.bpf_pc] + 5); 328169689Skan JMP(stream.refs[stream.bpf_pc + ins->jf] - 329169689Skan stream.refs[stream.bpf_pc]); 330169689Skan break; 331169689Skan 332169689Skan case BPF_JMP|BPF_JEQ|BPF_K: 333169689Skan CMPid(ins->k, EAX); 334169689Skan JE(stream.refs[stream.bpf_pc + ins->jt] - 335169689Skan stream.refs[stream.bpf_pc] + 5); 336169689Skan JMP(stream.refs[stream.bpf_pc + ins->jf] - 337169689Skan stream.refs[stream.bpf_pc]); 338169689Skan break; 339169689Skan 340169689Skan case BPF_JMP|BPF_JSET|BPF_K: 341169689Skan MOVrd(EAX, ECX); 342169689Skan ANDid(ins->k, ECX); 343169689Skan JE(stream.refs[stream.bpf_pc + ins->jf] - 344169689Skan stream.refs[stream.bpf_pc] + 5); 345169689Skan JMP(stream.refs[stream.bpf_pc + ins->jt] - 346169689Skan stream.refs[stream.bpf_pc]); 347169689Skan break; 348169689Skan 349169689Skan case BPF_JMP|BPF_JGT|BPF_X: 350169689Skan CMPrd(EDX, EAX); 351169689Skan JA(stream.refs[stream.bpf_pc + ins->jt] - 352169689Skan stream.refs[stream.bpf_pc] + 5); 353169689Skan JMP(stream.refs[stream.bpf_pc + ins->jf] - 354169689Skan stream.refs[stream.bpf_pc]); 355169689Skan break; 356169689Skan 357169689Skan case BPF_JMP|BPF_JGE|BPF_X: 358169689Skan CMPrd(EDX, EAX); 359169689Skan JAE(stream.refs[stream.bpf_pc + ins->jt] - 360169689Skan stream.refs[stream.bpf_pc] + 5); 361169689Skan JMP(stream.refs[stream.bpf_pc + ins->jf] - 362169689Skan stream.refs[stream.bpf_pc]); 363169689Skan break; 364169689Skan 365169689Skan case BPF_JMP|BPF_JEQ|BPF_X: 366169689Skan CMPrd(EDX, EAX); 367169689Skan JE(stream.refs[stream.bpf_pc + ins->jt] - 368169689Skan stream.refs[stream.bpf_pc] + 5); 369169689Skan JMP(stream.refs[stream.bpf_pc + ins->jf] - 370169689Skan stream.refs[stream.bpf_pc]); 371169689Skan break; 372169689Skan 373169689Skan case BPF_JMP|BPF_JSET|BPF_X: 374169689Skan MOVrd(EAX, ECX); 375169689Skan ANDrd(EDX, ECX); 376169689Skan JE(stream.refs[stream.bpf_pc + ins->jf] - 377169689Skan stream.refs[stream.bpf_pc] + 5); 378169689Skan JMP(stream.refs[stream.bpf_pc + ins->jt] - 379169689Skan stream.refs[stream.bpf_pc]); 380169689Skan break; 381169689Skan 382169689Skan case BPF_ALU|BPF_ADD|BPF_X: 383169689Skan ADDrd(EDX, EAX); 384169689Skan break; 385169689Skan 386169689Skan case BPF_ALU|BPF_SUB|BPF_X: 387169689Skan SUBrd(EDX, EAX); 388169689Skan break; 389169689Skan 390169689Skan case BPF_ALU|BPF_MUL|BPF_X: 391169689Skan MOVrd(EDX, ECX); 392169689Skan MULrd(EDX); 393169689Skan MOVrd(ECX, EDX); 394169689Skan break; 395169689Skan 396169689Skan case BPF_ALU|BPF_DIV|BPF_X: 397169689Skan CMPid(0, EDX); 398169689Skan JNEb(7); 399169689Skan ZERO_EAX(); 400169689Skan POP(EBX); 401169689Skan POP(ESI); 402169689Skan POP(EDI); 403169689Skan LEAVE_RET(); 404169689Skan MOVrd(EDX, ECX); 405169689Skan ZERO_EDX(); 406169689Skan DIVrd(ECX); 407169689Skan MOVrd(ECX, EDX); 408169689Skan break; 409169689Skan 410169689Skan case BPF_ALU|BPF_AND|BPF_X: 411169689Skan ANDrd(EDX, EAX); 412169689Skan break; 413169689Skan 414169689Skan case BPF_ALU|BPF_OR|BPF_X: 415169689Skan ORrd(EDX, EAX); 416169689Skan break; 417169689Skan 418169689Skan case BPF_ALU|BPF_LSH|BPF_X: 419169689Skan MOVrd(EDX, ECX); 420169689Skan SHL_CLrb(EAX); 421169689Skan break; 422169689Skan 423169689Skan case BPF_ALU|BPF_RSH|BPF_X: 424169689Skan MOVrd(EDX, ECX); 425169689Skan SHR_CLrb(EAX); 426169689Skan break; 427169689Skan 428169689Skan case BPF_ALU|BPF_ADD|BPF_K: 429169689Skan ADD_EAXi(ins->k); 430169689Skan break; 431169689Skan 432169689Skan case BPF_ALU|BPF_SUB|BPF_K: 433169689Skan SUB_EAXi(ins->k); 434169689Skan break; 435169689Skan 436169689Skan case BPF_ALU|BPF_MUL|BPF_K: 437169689Skan MOVrd(EDX, ECX); 438169689Skan MOVid(ins->k, EDX); 439169689Skan MULrd(EDX); 440169689Skan MOVrd(ECX, EDX); 441169689Skan break; 442169689Skan 443169689Skan case BPF_ALU|BPF_DIV|BPF_K: 444169689Skan MOVrd(EDX, ECX); 445169689Skan ZERO_EDX(); 446169689Skan MOVid(ins->k, ESI); 447169689Skan DIVrd(ESI); 448169689Skan MOVrd(ECX, EDX); 449169689Skan break; 450169689Skan 451169689Skan case BPF_ALU|BPF_AND|BPF_K: 452169689Skan ANDid(ins->k, EAX); 453169689Skan break; 454169689Skan 455169689Skan case BPF_ALU|BPF_OR|BPF_K: 456169689Skan ORid(ins->k, EAX); 457169689Skan break; 458169689Skan 459169689Skan case BPF_ALU|BPF_LSH|BPF_K: 460169689Skan SHLib((ins->k) & 0xff, EAX); 461169689Skan break; 462169689Skan 463169689Skan case BPF_ALU|BPF_RSH|BPF_K: 464169689Skan SHRib((ins->k) & 0xff, EAX); 465169689Skan break; 466169689Skan 467169689Skan case BPF_ALU|BPF_NEG: 468169689Skan NEGd(EAX); 469169689Skan break; 470169689Skan 471169689Skan case BPF_MISC|BPF_TAX: 472169689Skan MOVrd(EAX, EDX); 473169689Skan break; 474169689Skan 475169689Skan case BPF_MISC|BPF_TXA: 476169689Skan MOVrd(EDX, EAX); 477169689Skan break; 478169689Skan } 479169689Skan ins++; 480169689Skan } 481169689Skan 482169689Skan pass++; 483169689Skan if (pass == 2) 484169689Skan break; 485169689Skan 486169689Skan stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT); 487169689Skan if (stream.ibuf == NULL) { 488169689Skan free(stream.refs, M_BPFJIT); 489169689Skan return NULL; 490169689Skan } 491169689Skan 492169689Skan /* 493169689Skan * modify the reference table to contain the offsets and 494169689Skan * not the lengths of the instructions 495169689Skan */ 496169689Skan for (i = 1; i < nins + 1; i++) 497169689Skan stream.refs[i] += stream.refs[i - 1]; 498169689Skan 499169689Skan /* Reset the counters */ 500169689Skan stream.cur_ip = 0; 501169689Skan stream.bpf_pc = 0; 502169689Skan 503169689Skan /* the second pass creates the actual code */ 504169689Skan emitm = emit_code; 505169689Skan } 506169689Skan 507169689Skan /* 508169689Skan * the reference table is needed only during compilation, 509169689Skan * now we can free it 510169689Skan */ 511169689Skan free(stream.refs, M_BPFJIT); 512169689Skan 513169689Skan return (bpf_filter_func)stream.ibuf; 514169689Skan} 515169689Skan