bpf_jit_machdep.c revision 199721
1/*- 2 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy) 3 * Copyright (C) 2005-2009 Jung-uk Kim <jkim@FreeBSD.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the Politecnico di Torino nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32#include <sys/cdefs.h> 33__FBSDID("$FreeBSD: head/sys/i386/i386/bpf_jit_machdep.c 199721 2009-11-23 22:23:19Z jkim $"); 34 35#ifdef _KERNEL 36#include "opt_bpf.h" 37#include <sys/param.h> 38#include <sys/systm.h> 39#include <sys/kernel.h> 40#include <sys/socket.h> 41#include <sys/malloc.h> 42#include <net/if.h> 43#else 44#include <stdlib.h> 45#include <string.h> 46#include <sys/mman.h> 47#include <sys/param.h> 48#endif 49 50#include <sys/types.h> 51 52#include <net/bpf.h> 53#include <net/bpf_jitter.h> 54 55#include <i386/i386/bpf_jit_machdep.h> 56 57bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *); 58 59/* 60 * Emit routine to update the jump table. 61 */ 62static void 63emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len) 64{ 65 66 if (stream->refs != NULL) 67 (stream->refs)[stream->bpf_pc] += len; 68 stream->cur_ip += len; 69} 70 71/* 72 * Emit routine to output the actual binary code. 73 */ 74static void 75emit_code(bpf_bin_stream *stream, u_int value, u_int len) 76{ 77 78 switch (len) { 79 case 1: 80 stream->ibuf[stream->cur_ip] = (u_char)value; 81 stream->cur_ip++; 82 break; 83 84 case 2: 85 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 86 stream->cur_ip += 2; 87 break; 88 89 case 4: 90 *((u_int *)(stream->ibuf + stream->cur_ip)) = value; 91 stream->cur_ip += 4; 92 break; 93 } 94 95 return; 96} 97 98/* 99 * Scan the filter program and find possible optimization. 100 */ 101static int 102bpf_jit_optimize(struct bpf_insn *prog, u_int nins) 103{ 104 int flags; 105 u_int i; 106 107 /* Do we return immediately? */ 108 if (BPF_CLASS(prog[0].code) == BPF_RET) 109 return (BPF_JIT_FRET); 110 111 for (flags = 0, i = 0; i < nins; i++) { 112 switch (prog[i].code) { 113 case BPF_LD|BPF_W|BPF_ABS: 114 case BPF_LD|BPF_H|BPF_ABS: 115 case BPF_LD|BPF_B|BPF_ABS: 116 case BPF_LD|BPF_W|BPF_IND: 117 case BPF_LD|BPF_H|BPF_IND: 118 case BPF_LD|BPF_B|BPF_IND: 119 case BPF_LDX|BPF_MSH|BPF_B: 120 flags |= BPF_JIT_FPKT; 121 break; 122 case BPF_LD|BPF_MEM: 123 case BPF_LDX|BPF_MEM: 124 case BPF_ST: 125 case BPF_STX: 126 flags |= BPF_JIT_FMEM; 127 break; 128 case BPF_JMP|BPF_JA: 129 case BPF_JMP|BPF_JGT|BPF_K: 130 case BPF_JMP|BPF_JGE|BPF_K: 131 case BPF_JMP|BPF_JEQ|BPF_K: 132 case BPF_JMP|BPF_JSET|BPF_K: 133 case BPF_JMP|BPF_JGT|BPF_X: 134 case BPF_JMP|BPF_JGE|BPF_X: 135 case BPF_JMP|BPF_JEQ|BPF_X: 136 case BPF_JMP|BPF_JSET|BPF_X: 137 flags |= BPF_JIT_FJMP; 138 break; 139 case BPF_ALU|BPF_DIV|BPF_K: 140 flags |= BPF_JIT_FADK; 141 break; 142 } 143 if (flags == BPF_JIT_FLAG_ALL) 144 break; 145 } 146 147 return (flags); 148} 149 150/* 151 * Function that does the real stuff. 152 */ 153bpf_filter_func 154bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size) 155{ 156 bpf_bin_stream stream; 157 struct bpf_insn *ins; 158 int flags, fret, fpkt, fmem, fjmp, fadk; 159 int save_esp; 160 u_int i, pass; 161 162 /* 163 * NOTE: Do not modify the name of this variable, as it's used by 164 * the macros to emit code. 165 */ 166 emit_func emitm; 167 168 flags = bpf_jit_optimize(prog, nins); 169 fret = (flags & BPF_JIT_FRET) != 0; 170 fpkt = (flags & BPF_JIT_FPKT) != 0; 171 fmem = (flags & BPF_JIT_FMEM) != 0; 172 fjmp = (flags & BPF_JIT_FJMP) != 0; 173 fadk = (flags & BPF_JIT_FADK) != 0; 174 save_esp = (fpkt || fmem || fadk); /* Stack is used. */ 175 176 if (fret) 177 nins = 1; 178 179 memset(&stream, 0, sizeof(stream)); 180 181 /* Allocate the reference table for the jumps. */ 182 if (fjmp) { 183#ifdef _KERNEL 184 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT, 185 M_NOWAIT | M_ZERO); 186#else 187 stream.refs = calloc(nins + 1, sizeof(u_int)); 188#endif 189 if (stream.refs == NULL) 190 return (NULL); 191 } 192 193 /* 194 * The first pass will emit the lengths of the instructions 195 * to create the reference table. 196 */ 197 emitm = emit_length; 198 199 for (pass = 0; pass < 2; pass++) { 200 ins = prog; 201 202 /* Create the procedure header. */ 203 if (save_esp) { 204 PUSH(EBP); 205 MOVrd(ESP, EBP); 206 } 207 if (fmem) 208 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP); 209 if (save_esp) 210 PUSH(ESI); 211 if (fpkt) { 212 PUSH(EDI); 213 PUSH(EBX); 214 MOVodd(8, EBP, EBX); 215 MOVodd(16, EBP, EDI); 216 } 217 218 for (i = 0; i < nins; i++) { 219 stream.bpf_pc++; 220 221 switch (ins->code) { 222 default: 223#ifdef _KERNEL 224 return (NULL); 225#else 226 abort(); 227#endif 228 229 case BPF_RET|BPF_K: 230 MOVid(ins->k, EAX); 231 if (save_esp) { 232 if (fpkt) { 233 POP(EBX); 234 POP(EDI); 235 } 236 POP(ESI); 237 LEAVE(); 238 } 239 RET(); 240 break; 241 242 case BPF_RET|BPF_A: 243 if (save_esp) { 244 if (fpkt) { 245 POP(EBX); 246 POP(EDI); 247 } 248 POP(ESI); 249 LEAVE(); 250 } 251 RET(); 252 break; 253 254 case BPF_LD|BPF_W|BPF_ABS: 255 MOVid(ins->k, ESI); 256 CMPrd(EDI, ESI); 257 JAb(12); 258 MOVrd(EDI, ECX); 259 SUBrd(ESI, ECX); 260 CMPid(sizeof(int32_t), ECX); 261 JAEb(7); 262 ZEROrd(EAX); 263 POP(EBX); 264 POP(EDI); 265 POP(ESI); 266 LEAVE(); 267 RET(); 268 MOVobd(EBX, ESI, EAX); 269 BSWAP(EAX); 270 break; 271 272 case BPF_LD|BPF_H|BPF_ABS: 273 ZEROrd(EAX); 274 MOVid(ins->k, ESI); 275 CMPrd(EDI, ESI); 276 JAb(12); 277 MOVrd(EDI, ECX); 278 SUBrd(ESI, ECX); 279 CMPid(sizeof(int16_t), ECX); 280 JAEb(5); 281 POP(EBX); 282 POP(EDI); 283 POP(ESI); 284 LEAVE(); 285 RET(); 286 MOVobw(EBX, ESI, AX); 287 SWAP_AX(); 288 break; 289 290 case BPF_LD|BPF_B|BPF_ABS: 291 ZEROrd(EAX); 292 MOVid(ins->k, ESI); 293 CMPrd(EDI, ESI); 294 JBb(5); 295 POP(EBX); 296 POP(EDI); 297 POP(ESI); 298 LEAVE(); 299 RET(); 300 MOVobb(EBX, ESI, AL); 301 break; 302 303 case BPF_LD|BPF_W|BPF_LEN: 304 if (save_esp) 305 MOVodd(12, EBP, EAX); 306 else { 307 MOVrd(ESP, ECX); 308 MOVodd(12, ECX, EAX); 309 } 310 break; 311 312 case BPF_LDX|BPF_W|BPF_LEN: 313 if (save_esp) 314 MOVodd(12, EBP, EDX); 315 else { 316 MOVrd(ESP, ECX); 317 MOVodd(12, ECX, EDX); 318 } 319 break; 320 321 case BPF_LD|BPF_W|BPF_IND: 322 CMPrd(EDI, EDX); 323 JAb(27); 324 MOVid(ins->k, ESI); 325 MOVrd(EDI, ECX); 326 SUBrd(EDX, ECX); 327 CMPrd(ESI, ECX); 328 JBb(14); 329 ADDrd(EDX, ESI); 330 MOVrd(EDI, ECX); 331 SUBrd(ESI, ECX); 332 CMPid(sizeof(int32_t), ECX); 333 JAEb(7); 334 ZEROrd(EAX); 335 POP(EBX); 336 POP(EDI); 337 POP(ESI); 338 LEAVE(); 339 RET(); 340 MOVobd(EBX, ESI, EAX); 341 BSWAP(EAX); 342 break; 343 344 case BPF_LD|BPF_H|BPF_IND: 345 ZEROrd(EAX); 346 CMPrd(EDI, EDX); 347 JAb(27); 348 MOVid(ins->k, ESI); 349 MOVrd(EDI, ECX); 350 SUBrd(EDX, ECX); 351 CMPrd(ESI, ECX); 352 JBb(14); 353 ADDrd(EDX, ESI); 354 MOVrd(EDI, ECX); 355 SUBrd(ESI, ECX); 356 CMPid(sizeof(int16_t), ECX); 357 JAEb(5); 358 POP(EBX); 359 POP(EDI); 360 POP(ESI); 361 LEAVE(); 362 RET(); 363 MOVobw(EBX, ESI, AX); 364 SWAP_AX(); 365 break; 366 367 case BPF_LD|BPF_B|BPF_IND: 368 ZEROrd(EAX); 369 CMPrd(EDI, EDX); 370 JAEb(13); 371 MOVid(ins->k, ESI); 372 MOVrd(EDI, ECX); 373 SUBrd(EDX, ECX); 374 CMPrd(ESI, ECX); 375 JAb(5); 376 POP(EBX); 377 POP(EDI); 378 POP(ESI); 379 LEAVE(); 380 RET(); 381 ADDrd(EDX, ESI); 382 MOVobb(EBX, ESI, AL); 383 break; 384 385 case BPF_LDX|BPF_MSH|BPF_B: 386 MOVid(ins->k, ESI); 387 CMPrd(EDI, ESI); 388 JBb(7); 389 ZEROrd(EAX); 390 POP(EBX); 391 POP(EDI); 392 POP(ESI); 393 LEAVE(); 394 RET(); 395 ZEROrd(EDX); 396 MOVobb(EBX, ESI, DL); 397 ANDib(0x0f, DL); 398 SHLib(2, EDX); 399 break; 400 401 case BPF_LD|BPF_IMM: 402 MOVid(ins->k, EAX); 403 break; 404 405 case BPF_LDX|BPF_IMM: 406 MOVid(ins->k, EDX); 407 break; 408 409 case BPF_LD|BPF_MEM: 410 MOVrd(EBP, ECX); 411 MOVid(((int)ins->k - BPF_MEMWORDS) * 412 sizeof(uint32_t), ESI); 413 MOVobd(ECX, ESI, EAX); 414 break; 415 416 case BPF_LDX|BPF_MEM: 417 MOVrd(EBP, ECX); 418 MOVid(((int)ins->k - BPF_MEMWORDS) * 419 sizeof(uint32_t), ESI); 420 MOVobd(ECX, ESI, EDX); 421 break; 422 423 case BPF_ST: 424 /* 425 * XXX this command and the following could 426 * be optimized if the previous instruction 427 * was already of this type 428 */ 429 MOVrd(EBP, ECX); 430 MOVid(((int)ins->k - BPF_MEMWORDS) * 431 sizeof(uint32_t), ESI); 432 MOVomd(EAX, ECX, ESI); 433 break; 434 435 case BPF_STX: 436 MOVrd(EBP, ECX); 437 MOVid(((int)ins->k - BPF_MEMWORDS) * 438 sizeof(uint32_t), ESI); 439 MOVomd(EDX, ECX, ESI); 440 break; 441 442 case BPF_JMP|BPF_JA: 443 JMP(stream.refs[stream.bpf_pc + ins->k] - 444 stream.refs[stream.bpf_pc]); 445 break; 446 447 case BPF_JMP|BPF_JGT|BPF_K: 448 if (ins->jt == 0 && ins->jf == 0) 449 break; 450 CMPid(ins->k, EAX); 451 JCC(JA, JBE); 452 break; 453 454 case BPF_JMP|BPF_JGE|BPF_K: 455 if (ins->jt == 0 && ins->jf == 0) 456 break; 457 CMPid(ins->k, EAX); 458 JCC(JAE, JB); 459 break; 460 461 case BPF_JMP|BPF_JEQ|BPF_K: 462 if (ins->jt == 0 && ins->jf == 0) 463 break; 464 CMPid(ins->k, EAX); 465 JCC(JE, JNE); 466 break; 467 468 case BPF_JMP|BPF_JSET|BPF_K: 469 if (ins->jt == 0 && ins->jf == 0) 470 break; 471 TESTid(ins->k, EAX); 472 JCC(JNE, JE); 473 break; 474 475 case BPF_JMP|BPF_JGT|BPF_X: 476 if (ins->jt == 0 && ins->jf == 0) 477 break; 478 CMPrd(EDX, EAX); 479 JCC(JA, JBE); 480 break; 481 482 case BPF_JMP|BPF_JGE|BPF_X: 483 if (ins->jt == 0 && ins->jf == 0) 484 break; 485 CMPrd(EDX, EAX); 486 JCC(JAE, JB); 487 break; 488 489 case BPF_JMP|BPF_JEQ|BPF_X: 490 if (ins->jt == 0 && ins->jf == 0) 491 break; 492 CMPrd(EDX, EAX); 493 JCC(JE, JNE); 494 break; 495 496 case BPF_JMP|BPF_JSET|BPF_X: 497 if (ins->jt == 0 && ins->jf == 0) 498 break; 499 TESTrd(EDX, EAX); 500 JCC(JNE, JE); 501 break; 502 503 case BPF_ALU|BPF_ADD|BPF_X: 504 ADDrd(EDX, EAX); 505 break; 506 507 case BPF_ALU|BPF_SUB|BPF_X: 508 SUBrd(EDX, EAX); 509 break; 510 511 case BPF_ALU|BPF_MUL|BPF_X: 512 MOVrd(EDX, ECX); 513 MULrd(EDX); 514 MOVrd(ECX, EDX); 515 break; 516 517 case BPF_ALU|BPF_DIV|BPF_X: 518 TESTrd(EDX, EDX); 519 if (save_esp) { 520 if (fpkt) { 521 JNEb(7); 522 ZEROrd(EAX); 523 POP(EBX); 524 POP(EDI); 525 } else { 526 JNEb(5); 527 ZEROrd(EAX); 528 } 529 POP(ESI); 530 LEAVE(); 531 } else { 532 JNEb(3); 533 ZEROrd(EAX); 534 } 535 RET(); 536 MOVrd(EDX, ECX); 537 ZEROrd(EDX); 538 DIVrd(ECX); 539 MOVrd(ECX, EDX); 540 break; 541 542 case BPF_ALU|BPF_AND|BPF_X: 543 ANDrd(EDX, EAX); 544 break; 545 546 case BPF_ALU|BPF_OR|BPF_X: 547 ORrd(EDX, EAX); 548 break; 549 550 case BPF_ALU|BPF_LSH|BPF_X: 551 MOVrd(EDX, ECX); 552 SHL_CLrb(EAX); 553 break; 554 555 case BPF_ALU|BPF_RSH|BPF_X: 556 MOVrd(EDX, ECX); 557 SHR_CLrb(EAX); 558 break; 559 560 case BPF_ALU|BPF_ADD|BPF_K: 561 ADD_EAXi(ins->k); 562 break; 563 564 case BPF_ALU|BPF_SUB|BPF_K: 565 SUB_EAXi(ins->k); 566 break; 567 568 case BPF_ALU|BPF_MUL|BPF_K: 569 MOVrd(EDX, ECX); 570 MOVid(ins->k, EDX); 571 MULrd(EDX); 572 MOVrd(ECX, EDX); 573 break; 574 575 case BPF_ALU|BPF_DIV|BPF_K: 576 MOVrd(EDX, ECX); 577 ZEROrd(EDX); 578 MOVid(ins->k, ESI); 579 DIVrd(ESI); 580 MOVrd(ECX, EDX); 581 break; 582 583 case BPF_ALU|BPF_AND|BPF_K: 584 ANDid(ins->k, EAX); 585 break; 586 587 case BPF_ALU|BPF_OR|BPF_K: 588 ORid(ins->k, EAX); 589 break; 590 591 case BPF_ALU|BPF_LSH|BPF_K: 592 SHLib((ins->k) & 0xff, EAX); 593 break; 594 595 case BPF_ALU|BPF_RSH|BPF_K: 596 SHRib((ins->k) & 0xff, EAX); 597 break; 598 599 case BPF_ALU|BPF_NEG: 600 NEGd(EAX); 601 break; 602 603 case BPF_MISC|BPF_TAX: 604 MOVrd(EAX, EDX); 605 break; 606 607 case BPF_MISC|BPF_TXA: 608 MOVrd(EDX, EAX); 609 break; 610 } 611 ins++; 612 } 613 614 if (pass > 0) 615 continue; 616 617 *size = stream.cur_ip; 618#ifdef _KERNEL 619 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT); 620 if (stream.ibuf == NULL) 621 break; 622#else 623 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE, 624 MAP_ANON, -1, 0); 625 if (stream.ibuf == MAP_FAILED) { 626 stream.ibuf = NULL; 627 break; 628 } 629#endif 630 631 /* 632 * Modify the reference table to contain the offsets and 633 * not the lengths of the instructions. 634 */ 635 if (fjmp) 636 for (i = 1; i < nins + 1; i++) 637 stream.refs[i] += stream.refs[i - 1]; 638 639 /* Reset the counters. */ 640 stream.cur_ip = 0; 641 stream.bpf_pc = 0; 642 643 /* The second pass creates the actual code. */ 644 emitm = emit_code; 645 } 646 647 /* 648 * The reference table is needed only during compilation, 649 * now we can free it. 650 */ 651 if (fjmp) 652#ifdef _KERNEL 653 free(stream.refs, M_BPFJIT); 654#else 655 free(stream.refs); 656#endif 657 658#ifndef _KERNEL 659 if (stream.ibuf != NULL && 660 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) { 661 munmap(stream.ibuf, *size); 662 stream.ibuf = NULL; 663 } 664#endif 665 666 return ((bpf_filter_func)stream.ibuf); 667} 668