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