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