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