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