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 <amd64/amd64/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_LD|BPF_W|BPF_LEN: 132 case BPF_LDX|BPF_W|BPF_LEN: 133 flags |= BPF_JIT_FLEN; 134 break; 135 case BPF_JMP|BPF_JA: 136 case BPF_JMP|BPF_JGT|BPF_K: 137 case BPF_JMP|BPF_JGE|BPF_K: 138 case BPF_JMP|BPF_JEQ|BPF_K: 139 case BPF_JMP|BPF_JSET|BPF_K: 140 case BPF_JMP|BPF_JGT|BPF_X: 141 case BPF_JMP|BPF_JGE|BPF_X: 142 case BPF_JMP|BPF_JEQ|BPF_X: 143 case BPF_JMP|BPF_JSET|BPF_X: 144 flags |= BPF_JIT_FJMP; 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, flen; 163 u_int i, pass; 164 165 /* 166 * NOTE: Do not modify the name of this variable, as it's used by 167 * the macros to emit code. 168 */ 169 emit_func emitm; 170 171 flags = bpf_jit_optimize(prog, nins); 172 fret = (flags & BPF_JIT_FRET) != 0; 173 fpkt = (flags & BPF_JIT_FPKT) != 0; 174 fmem = (flags & BPF_JIT_FMEM) != 0; 175 fjmp = (flags & BPF_JIT_FJMP) != 0; 176 flen = (flags & BPF_JIT_FLEN) != 0; 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 (fmem) { 206 PUSH(RBP); 207 MOVrq(RSP, RBP); 208 SUBib(BPF_MEMWORDS * sizeof(uint32_t), RSP); 209 } 210 if (flen) 211 MOVrd2(ESI, R9D); 212 if (fpkt) { 213 MOVrq2(RDI, R8); 214 MOVrd(EDX, EDI); 215 } 216 217 for (i = 0; i < nins; i++) { 218 stream.bpf_pc++; 219 220 switch (ins->code) { 221 default: 222 #ifdef _KERNEL 223 return (NULL); 224 #else 225 abort(); 226 #endif 227 228 case BPF_RET|BPF_K: 229 MOVid(ins->k, EAX); 230 if (fmem) 231 LEAVE(); 232 RET(); 233 break; 234 235 case BPF_RET|BPF_A: 236 if (fmem) 237 LEAVE(); 238 RET(); 239 break; 240 241 case BPF_LD|BPF_W|BPF_ABS: 242 MOVid(ins->k, ESI); 243 CMPrd(EDI, ESI); 244 JAb(12); 245 MOVrd(EDI, ECX); 246 SUBrd(ESI, ECX); 247 CMPid(sizeof(int32_t), ECX); 248 if (fmem) { 249 JAEb(4); 250 ZEROrd(EAX); 251 LEAVE(); 252 } else { 253 JAEb(3); 254 ZEROrd(EAX); 255 } 256 RET(); 257 MOVrq3(R8, RCX); 258 MOVobd(RCX, RSI, EAX); 259 BSWAP(EAX); 260 break; 261 262 case BPF_LD|BPF_H|BPF_ABS: 263 ZEROrd(EAX); 264 MOVid(ins->k, ESI); 265 CMPrd(EDI, ESI); 266 JAb(12); 267 MOVrd(EDI, ECX); 268 SUBrd(ESI, ECX); 269 CMPid(sizeof(int16_t), ECX); 270 if (fmem) { 271 JAEb(2); 272 LEAVE(); 273 } else 274 JAEb(1); 275 RET(); 276 MOVrq3(R8, RCX); 277 MOVobw(RCX, RSI, AX); 278 SWAP_AX(); 279 break; 280 281 case BPF_LD|BPF_B|BPF_ABS: 282 ZEROrd(EAX); 283 MOVid(ins->k, ESI); 284 CMPrd(EDI, ESI); 285 if (fmem) { 286 JBb(2); 287 LEAVE(); 288 } else 289 JBb(1); 290 RET(); 291 MOVrq3(R8, RCX); 292 MOVobb(RCX, RSI, AL); 293 break; 294 295 case BPF_LD|BPF_W|BPF_LEN: 296 MOVrd3(R9D, EAX); 297 break; 298 299 case BPF_LDX|BPF_W|BPF_LEN: 300 MOVrd3(R9D, EDX); 301 break; 302 303 case BPF_LD|BPF_W|BPF_IND: 304 CMPrd(EDI, EDX); 305 JAb(27); 306 MOVid(ins->k, ESI); 307 MOVrd(EDI, ECX); 308 SUBrd(EDX, ECX); 309 CMPrd(ESI, ECX); 310 JBb(14); 311 ADDrd(EDX, ESI); 312 MOVrd(EDI, ECX); 313 SUBrd(ESI, ECX); 314 CMPid(sizeof(int32_t), ECX); 315 if (fmem) { 316 JAEb(4); 317 ZEROrd(EAX); 318 LEAVE(); 319 } else { 320 JAEb(3); 321 ZEROrd(EAX); 322 } 323 RET(); 324 MOVrq3(R8, RCX); 325 MOVobd(RCX, RSI, EAX); 326 BSWAP(EAX); 327 break; 328 329 case BPF_LD|BPF_H|BPF_IND: 330 ZEROrd(EAX); 331 CMPrd(EDI, EDX); 332 JAb(27); 333 MOVid(ins->k, ESI); 334 MOVrd(EDI, ECX); 335 SUBrd(EDX, ECX); 336 CMPrd(ESI, ECX); 337 JBb(14); 338 ADDrd(EDX, ESI); 339 MOVrd(EDI, ECX); 340 SUBrd(ESI, ECX); 341 CMPid(sizeof(int16_t), ECX); 342 if (fmem) { 343 JAEb(2); 344 LEAVE(); 345 } else 346 JAEb(1); 347 RET(); 348 MOVrq3(R8, RCX); 349 MOVobw(RCX, RSI, AX); 350 SWAP_AX(); 351 break; 352 353 case BPF_LD|BPF_B|BPF_IND: 354 ZEROrd(EAX); 355 CMPrd(EDI, EDX); 356 JAEb(13); 357 MOVid(ins->k, ESI); 358 MOVrd(EDI, ECX); 359 SUBrd(EDX, ECX); 360 CMPrd(ESI, ECX); 361 if (fmem) { 362 JAb(2); 363 LEAVE(); 364 } else 365 JAb(1); 366 RET(); 367 MOVrq3(R8, RCX); 368 ADDrd(EDX, ESI); 369 MOVobb(RCX, RSI, AL); 370 break; 371 372 case BPF_LDX|BPF_MSH|BPF_B: 373 MOVid(ins->k, ESI); 374 CMPrd(EDI, ESI); 375 if (fmem) { 376 JBb(4); 377 ZEROrd(EAX); 378 LEAVE(); 379 } else { 380 JBb(3); 381 ZEROrd(EAX); 382 } 383 RET(); 384 ZEROrd(EDX); 385 MOVrq3(R8, RCX); 386 MOVobb(RCX, RSI, DL); 387 ANDib(0x0f, DL); 388 SHLib(2, EDX); 389 break; 390 391 case BPF_LD|BPF_IMM: 392 MOVid(ins->k, EAX); 393 break; 394 395 case BPF_LDX|BPF_IMM: 396 MOVid(ins->k, EDX); 397 break; 398 399 case BPF_LD|BPF_MEM: 400 MOVid(ins->k * sizeof(uint32_t), ESI); 401 MOVobd(RSP, RSI, EAX); 402 break; 403 404 case BPF_LDX|BPF_MEM: 405 MOVid(ins->k * sizeof(uint32_t), ESI); 406 MOVobd(RSP, RSI, EDX); 407 break; 408 409 case BPF_ST: 410 /* 411 * XXX this command and the following could 412 * be optimized if the previous instruction 413 * was already of this type 414 */ 415 MOVid(ins->k * sizeof(uint32_t), ESI); 416 MOVomd(EAX, RSP, RSI); 417 break; 418 419 case BPF_STX: 420 MOVid(ins->k * sizeof(uint32_t), ESI); 421 MOVomd(EDX, RSP, RSI); 422 break; 423 424 case BPF_JMP|BPF_JA: 425 JUMP(ins->k); 426 break; 427 428 case BPF_JMP|BPF_JGT|BPF_K: 429 case BPF_JMP|BPF_JGE|BPF_K: 430 case BPF_JMP|BPF_JEQ|BPF_K: 431 case BPF_JMP|BPF_JSET|BPF_K: 432 case BPF_JMP|BPF_JGT|BPF_X: 433 case BPF_JMP|BPF_JGE|BPF_X: 434 case BPF_JMP|BPF_JEQ|BPF_X: 435 case BPF_JMP|BPF_JSET|BPF_X: 436 if (ins->jt == ins->jf) { 437 JUMP(ins->jt); 438 break; 439 } 440 switch (ins->code) { 441 case BPF_JMP|BPF_JGT|BPF_K: 442 CMPid(ins->k, EAX); 443 JCC(JA, JBE); 444 break; 445 446 case BPF_JMP|BPF_JGE|BPF_K: 447 CMPid(ins->k, EAX); 448 JCC(JAE, JB); 449 break; 450 451 case BPF_JMP|BPF_JEQ|BPF_K: 452 CMPid(ins->k, EAX); 453 JCC(JE, JNE); 454 break; 455 456 case BPF_JMP|BPF_JSET|BPF_K: 457 TESTid(ins->k, EAX); 458 JCC(JNE, JE); 459 break; 460 461 case BPF_JMP|BPF_JGT|BPF_X: 462 CMPrd(EDX, EAX); 463 JCC(JA, JBE); 464 break; 465 466 case BPF_JMP|BPF_JGE|BPF_X: 467 CMPrd(EDX, EAX); 468 JCC(JAE, JB); 469 break; 470 471 case BPF_JMP|BPF_JEQ|BPF_X: 472 CMPrd(EDX, EAX); 473 JCC(JE, JNE); 474 break; 475 476 case BPF_JMP|BPF_JSET|BPF_X: 477 TESTrd(EDX, EAX); 478 JCC(JNE, JE); 479 break; 480 } 481 break; 482 483 case BPF_ALU|BPF_ADD|BPF_X: 484 ADDrd(EDX, EAX); 485 break; 486 487 case BPF_ALU|BPF_SUB|BPF_X: 488 SUBrd(EDX, EAX); 489 break; 490 491 case BPF_ALU|BPF_MUL|BPF_X: 492 MOVrd(EDX, ECX); 493 MULrd(EDX); 494 MOVrd(ECX, EDX); 495 break; 496 497 case BPF_ALU|BPF_DIV|BPF_X: 498 case BPF_ALU|BPF_MOD|BPF_X: 499 TESTrd(EDX, EDX); 500 if (fmem) { 501 JNEb(4); 502 ZEROrd(EAX); 503 LEAVE(); 504 } else { 505 JNEb(3); 506 ZEROrd(EAX); 507 } 508 RET(); 509 MOVrd(EDX, ECX); 510 ZEROrd(EDX); 511 DIVrd(ECX); 512 if (BPF_OP(ins->code) == BPF_MOD) 513 MOVrd(EDX, EAX); 514 MOVrd(ECX, EDX); 515 break; 516 517 case BPF_ALU|BPF_AND|BPF_X: 518 ANDrd(EDX, EAX); 519 break; 520 521 case BPF_ALU|BPF_OR|BPF_X: 522 ORrd(EDX, EAX); 523 break; 524 525 case BPF_ALU|BPF_XOR|BPF_X: 526 XORrd(EDX, EAX); 527 break; 528 529 case BPF_ALU|BPF_LSH|BPF_X: 530 MOVrd(EDX, ECX); 531 SHL_CLrb(EAX); 532 break; 533 534 case BPF_ALU|BPF_RSH|BPF_X: 535 MOVrd(EDX, ECX); 536 SHR_CLrb(EAX); 537 break; 538 539 case BPF_ALU|BPF_ADD|BPF_K: 540 ADD_EAXi(ins->k); 541 break; 542 543 case BPF_ALU|BPF_SUB|BPF_K: 544 SUB_EAXi(ins->k); 545 break; 546 547 case BPF_ALU|BPF_MUL|BPF_K: 548 MOVrd(EDX, ECX); 549 MOVid(ins->k, EDX); 550 MULrd(EDX); 551 MOVrd(ECX, EDX); 552 break; 553 554 case BPF_ALU|BPF_DIV|BPF_K: 555 case BPF_ALU|BPF_MOD|BPF_K: 556 MOVrd(EDX, ECX); 557 ZEROrd(EDX); 558 MOVid(ins->k, ESI); 559 DIVrd(ESI); 560 if (BPF_OP(ins->code) == BPF_MOD) 561 MOVrd(EDX, EAX); 562 MOVrd(ECX, EDX); 563 break; 564 565 case BPF_ALU|BPF_AND|BPF_K: 566 ANDid(ins->k, EAX); 567 break; 568 569 case BPF_ALU|BPF_OR|BPF_K: 570 ORid(ins->k, EAX); 571 break; 572 573 case BPF_ALU|BPF_XOR|BPF_K: 574 XORid(ins->k, EAX); 575 break; 576 577 case BPF_ALU|BPF_LSH|BPF_K: 578 SHLib((ins->k) & 0xff, EAX); 579 break; 580 581 case BPF_ALU|BPF_RSH|BPF_K: 582 SHRib((ins->k) & 0xff, EAX); 583 break; 584 585 case BPF_ALU|BPF_NEG: 586 NEGd(EAX); 587 break; 588 589 case BPF_MISC|BPF_TAX: 590 MOVrd(EAX, EDX); 591 break; 592 593 case BPF_MISC|BPF_TXA: 594 MOVrd(EDX, EAX); 595 break; 596 } 597 ins++; 598 } 599 600 if (pass > 0) 601 continue; 602 603 *size = stream.cur_ip; 604 #ifdef _KERNEL 605 stream.ibuf = malloc_exec(*size, M_BPFJIT, M_NOWAIT); 606 if (stream.ibuf == NULL) 607 break; 608 #else 609 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE, 610 MAP_ANON, -1, 0); 611 if (stream.ibuf == MAP_FAILED) { 612 stream.ibuf = NULL; 613 break; 614 } 615 #endif 616 617 /* 618 * Modify the reference table to contain the offsets and 619 * not the lengths of the instructions. 620 */ 621 if (fjmp) 622 for (i = 1; i < nins + 1; i++) 623 stream.refs[i] += stream.refs[i - 1]; 624 625 /* Reset the counters. */ 626 stream.cur_ip = 0; 627 stream.bpf_pc = 0; 628 629 /* The second pass creates the actual code. */ 630 emitm = emit_code; 631 } 632 633 /* 634 * The reference table is needed only during compilation, 635 * now we can free it. 636 */ 637 if (fjmp) 638 #ifdef _KERNEL 639 free(stream.refs, M_BPFJIT); 640 #else 641 free(stream.refs); 642 #endif 643 644 #ifndef _KERNEL 645 if (stream.ibuf != NULL && 646 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) { 647 munmap(stream.ibuf, *size); 648 stream.ibuf = NULL; 649 } 650 #endif 651 652 return ((bpf_filter_func)(void *)stream.ibuf); 653 } 654