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