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/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 57 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *); 58 59 /* 60 * Emit routine to update the jump table. 61 */ 62 static void 63 emit_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 */ 74 static void 75 emit_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 */ 101 static int 102 bpf_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 */ 153 bpf_filter_func 154 bpf_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 JUMP(ins->k); 444 break; 445 446 case BPF_JMP|BPF_JGT|BPF_K: 447 if (ins->jt == ins->jf) { 448 JUMP(ins->jt); 449 break; 450 } 451 CMPid(ins->k, EAX); 452 JCC(JA, JBE); 453 break; 454 455 case BPF_JMP|BPF_JGE|BPF_K: 456 if (ins->jt == ins->jf) { 457 JUMP(ins->jt); 458 break; 459 } 460 CMPid(ins->k, EAX); 461 JCC(JAE, JB); 462 break; 463 464 case BPF_JMP|BPF_JEQ|BPF_K: 465 if (ins->jt == ins->jf) { 466 JUMP(ins->jt); 467 break; 468 } 469 CMPid(ins->k, EAX); 470 JCC(JE, JNE); 471 break; 472 473 case BPF_JMP|BPF_JSET|BPF_K: 474 if (ins->jt == ins->jf) { 475 JUMP(ins->jt); 476 break; 477 } 478 TESTid(ins->k, EAX); 479 JCC(JNE, JE); 480 break; 481 482 case BPF_JMP|BPF_JGT|BPF_X: 483 if (ins->jt == ins->jf) { 484 JUMP(ins->jt); 485 break; 486 } 487 CMPrd(EDX, EAX); 488 JCC(JA, JBE); 489 break; 490 491 case BPF_JMP|BPF_JGE|BPF_X: 492 if (ins->jt == ins->jf) { 493 JUMP(ins->jt); 494 break; 495 } 496 CMPrd(EDX, EAX); 497 JCC(JAE, JB); 498 break; 499 500 case BPF_JMP|BPF_JEQ|BPF_X: 501 if (ins->jt == ins->jf) { 502 JUMP(ins->jt); 503 break; 504 } 505 CMPrd(EDX, EAX); 506 JCC(JE, JNE); 507 break; 508 509 case BPF_JMP|BPF_JSET|BPF_X: 510 if (ins->jt == ins->jf) { 511 JUMP(ins->jt); 512 break; 513 } 514 TESTrd(EDX, EAX); 515 JCC(JNE, JE); 516 break; 517 518 case BPF_ALU|BPF_ADD|BPF_X: 519 ADDrd(EDX, EAX); 520 break; 521 522 case BPF_ALU|BPF_SUB|BPF_X: 523 SUBrd(EDX, EAX); 524 break; 525 526 case BPF_ALU|BPF_MUL|BPF_X: 527 MOVrd(EDX, ECX); 528 MULrd(EDX); 529 MOVrd(ECX, EDX); 530 break; 531 532 case BPF_ALU|BPF_DIV|BPF_X: 533 TESTrd(EDX, EDX); 534 if (save_esp) { 535 if (fpkt) { 536 JNEb(7); 537 ZEROrd(EAX); 538 POP(EBX); 539 POP(EDI); 540 } else { 541 JNEb(5); 542 ZEROrd(EAX); 543 } 544 POP(ESI); 545 LEAVE(); 546 } else { 547 JNEb(3); 548 ZEROrd(EAX); 549 } 550 RET(); 551 MOVrd(EDX, ECX); 552 ZEROrd(EDX); 553 DIVrd(ECX); 554 MOVrd(ECX, EDX); 555 break; 556 557 case BPF_ALU|BPF_AND|BPF_X: 558 ANDrd(EDX, EAX); 559 break; 560 561 case BPF_ALU|BPF_OR|BPF_X: 562 ORrd(EDX, EAX); 563 break; 564 565 case BPF_ALU|BPF_LSH|BPF_X: 566 MOVrd(EDX, ECX); 567 SHL_CLrb(EAX); 568 break; 569 570 case BPF_ALU|BPF_RSH|BPF_X: 571 MOVrd(EDX, ECX); 572 SHR_CLrb(EAX); 573 break; 574 575 case BPF_ALU|BPF_ADD|BPF_K: 576 ADD_EAXi(ins->k); 577 break; 578 579 case BPF_ALU|BPF_SUB|BPF_K: 580 SUB_EAXi(ins->k); 581 break; 582 583 case BPF_ALU|BPF_MUL|BPF_K: 584 MOVrd(EDX, ECX); 585 MOVid(ins->k, EDX); 586 MULrd(EDX); 587 MOVrd(ECX, EDX); 588 break; 589 590 case BPF_ALU|BPF_DIV|BPF_K: 591 MOVrd(EDX, ECX); 592 ZEROrd(EDX); 593 MOVid(ins->k, ESI); 594 DIVrd(ESI); 595 MOVrd(ECX, EDX); 596 break; 597 598 case BPF_ALU|BPF_AND|BPF_K: 599 ANDid(ins->k, EAX); 600 break; 601 602 case BPF_ALU|BPF_OR|BPF_K: 603 ORid(ins->k, EAX); 604 break; 605 606 case BPF_ALU|BPF_LSH|BPF_K: 607 SHLib((ins->k) & 0xff, EAX); 608 break; 609 610 case BPF_ALU|BPF_RSH|BPF_K: 611 SHRib((ins->k) & 0xff, EAX); 612 break; 613 614 case BPF_ALU|BPF_NEG: 615 NEGd(EAX); 616 break; 617 618 case BPF_MISC|BPF_TAX: 619 MOVrd(EAX, EDX); 620 break; 621 622 case BPF_MISC|BPF_TXA: 623 MOVrd(EDX, EAX); 624 break; 625 } 626 ins++; 627 } 628 629 if (pass > 0) 630 continue; 631 632 *size = stream.cur_ip; 633 #ifdef _KERNEL 634 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT); 635 if (stream.ibuf == NULL) 636 break; 637 #else 638 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE, 639 MAP_ANON, -1, 0); 640 if (stream.ibuf == MAP_FAILED) { 641 stream.ibuf = NULL; 642 break; 643 } 644 #endif 645 646 /* 647 * Modify the reference table to contain the offsets and 648 * not the lengths of the instructions. 649 */ 650 if (fjmp) 651 for (i = 1; i < nins + 1; i++) 652 stream.refs[i] += stream.refs[i - 1]; 653 654 /* Reset the counters. */ 655 stream.cur_ip = 0; 656 stream.bpf_pc = 0; 657 658 /* The second pass creates the actual code. */ 659 emitm = emit_code; 660 } 661 662 /* 663 * The reference table is needed only during compilation, 664 * now we can free it. 665 */ 666 if (fjmp) 667 #ifdef _KERNEL 668 free(stream.refs, M_BPFJIT); 669 #else 670 free(stream.refs); 671 #endif 672 673 #ifndef _KERNEL 674 if (stream.ibuf != NULL && 675 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) { 676 munmap(stream.ibuf, *size); 677 stream.ibuf = NULL; 678 } 679 #endif 680 681 return ((bpf_filter_func)stream.ibuf); 682 } 683