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