bpf_jit_machdep.c revision 330897
1/*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy) 5 * Copyright (C) 2005-2009 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: stable/11/sys/i386/i386/bpf_jit_machdep.c 330897 2018-03-14 03:19:51Z eadler $"); 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/mbuf.h> 43#include <sys/socket.h> 44#include <sys/malloc.h> 45#include <net/if.h> 46#else 47#include <stdlib.h> 48#include <string.h> 49#include <sys/mman.h> 50#include <sys/param.h> 51#endif 52 53#include <sys/types.h> 54 55#include <net/bpf.h> 56#include <net/bpf_jitter.h> 57 58#include <i386/i386/bpf_jit_machdep.h> 59 60bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *); 61 62/* 63 * Emit routine to update the jump table. 64 */ 65static void 66emit_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 */ 77static void 78emit_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 *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 89 stream->cur_ip += 2; 90 break; 91 92 case 4: 93 *((u_int *)(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 */ 104static int 105bpf_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 flags |= BPF_JIT_FADK; 144 break; 145 } 146 if (flags == BPF_JIT_FLAG_ALL) 147 break; 148 } 149 150 return (flags); 151} 152 153/* 154 * Function that does the real stuff. 155 */ 156bpf_filter_func 157bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size) 158{ 159 bpf_bin_stream stream; 160 struct bpf_insn *ins; 161 int flags, fret, fpkt, fmem, fjmp, fadk; 162 int save_esp; 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 fadk = (flags & BPF_JIT_FADK) != 0; 177 save_esp = (fpkt || fmem || fadk); /* Stack is used. */ 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 (save_esp) { 207 PUSH(EBP); 208 MOVrd(ESP, EBP); 209 } 210 if (fmem) 211 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP); 212 if (save_esp) 213 PUSH(ESI); 214 if (fpkt) { 215 PUSH(EDI); 216 PUSH(EBX); 217 MOVodd(8, EBP, EBX); 218 MOVodd(16, EBP, EDI); 219 } 220 221 for (i = 0; i < nins; i++) { 222 stream.bpf_pc++; 223 224 switch (ins->code) { 225 default: 226#ifdef _KERNEL 227 return (NULL); 228#else 229 abort(); 230#endif 231 232 case BPF_RET|BPF_K: 233 MOVid(ins->k, EAX); 234 if (save_esp) { 235 if (fpkt) { 236 POP(EBX); 237 POP(EDI); 238 } 239 POP(ESI); 240 LEAVE(); 241 } 242 RET(); 243 break; 244 245 case BPF_RET|BPF_A: 246 if (save_esp) { 247 if (fpkt) { 248 POP(EBX); 249 POP(EDI); 250 } 251 POP(ESI); 252 LEAVE(); 253 } 254 RET(); 255 break; 256 257 case BPF_LD|BPF_W|BPF_ABS: 258 MOVid(ins->k, ESI); 259 CMPrd(EDI, ESI); 260 JAb(12); 261 MOVrd(EDI, ECX); 262 SUBrd(ESI, ECX); 263 CMPid(sizeof(int32_t), ECX); 264 JAEb(7); 265 ZEROrd(EAX); 266 POP(EBX); 267 POP(EDI); 268 POP(ESI); 269 LEAVE(); 270 RET(); 271 MOVobd(EBX, ESI, EAX); 272 BSWAP(EAX); 273 break; 274 275 case BPF_LD|BPF_H|BPF_ABS: 276 ZEROrd(EAX); 277 MOVid(ins->k, ESI); 278 CMPrd(EDI, ESI); 279 JAb(12); 280 MOVrd(EDI, ECX); 281 SUBrd(ESI, ECX); 282 CMPid(sizeof(int16_t), ECX); 283 JAEb(5); 284 POP(EBX); 285 POP(EDI); 286 POP(ESI); 287 LEAVE(); 288 RET(); 289 MOVobw(EBX, ESI, AX); 290 SWAP_AX(); 291 break; 292 293 case BPF_LD|BPF_B|BPF_ABS: 294 ZEROrd(EAX); 295 MOVid(ins->k, ESI); 296 CMPrd(EDI, ESI); 297 JBb(5); 298 POP(EBX); 299 POP(EDI); 300 POP(ESI); 301 LEAVE(); 302 RET(); 303 MOVobb(EBX, ESI, AL); 304 break; 305 306 case BPF_LD|BPF_W|BPF_LEN: 307 if (save_esp) 308 MOVodd(12, EBP, EAX); 309 else { 310 MOVrd(ESP, ECX); 311 MOVodd(12, ECX, EAX); 312 } 313 break; 314 315 case BPF_LDX|BPF_W|BPF_LEN: 316 if (save_esp) 317 MOVodd(12, EBP, EDX); 318 else { 319 MOVrd(ESP, ECX); 320 MOVodd(12, ECX, EDX); 321 } 322 break; 323 324 case BPF_LD|BPF_W|BPF_IND: 325 CMPrd(EDI, EDX); 326 JAb(27); 327 MOVid(ins->k, ESI); 328 MOVrd(EDI, ECX); 329 SUBrd(EDX, ECX); 330 CMPrd(ESI, ECX); 331 JBb(14); 332 ADDrd(EDX, ESI); 333 MOVrd(EDI, ECX); 334 SUBrd(ESI, ECX); 335 CMPid(sizeof(int32_t), ECX); 336 JAEb(7); 337 ZEROrd(EAX); 338 POP(EBX); 339 POP(EDI); 340 POP(ESI); 341 LEAVE(); 342 RET(); 343 MOVobd(EBX, ESI, EAX); 344 BSWAP(EAX); 345 break; 346 347 case BPF_LD|BPF_H|BPF_IND: 348 ZEROrd(EAX); 349 CMPrd(EDI, EDX); 350 JAb(27); 351 MOVid(ins->k, ESI); 352 MOVrd(EDI, ECX); 353 SUBrd(EDX, ECX); 354 CMPrd(ESI, ECX); 355 JBb(14); 356 ADDrd(EDX, ESI); 357 MOVrd(EDI, ECX); 358 SUBrd(ESI, ECX); 359 CMPid(sizeof(int16_t), ECX); 360 JAEb(5); 361 POP(EBX); 362 POP(EDI); 363 POP(ESI); 364 LEAVE(); 365 RET(); 366 MOVobw(EBX, ESI, AX); 367 SWAP_AX(); 368 break; 369 370 case BPF_LD|BPF_B|BPF_IND: 371 ZEROrd(EAX); 372 CMPrd(EDI, EDX); 373 JAEb(13); 374 MOVid(ins->k, ESI); 375 MOVrd(EDI, ECX); 376 SUBrd(EDX, ECX); 377 CMPrd(ESI, ECX); 378 JAb(5); 379 POP(EBX); 380 POP(EDI); 381 POP(ESI); 382 LEAVE(); 383 RET(); 384 ADDrd(EDX, ESI); 385 MOVobb(EBX, ESI, AL); 386 break; 387 388 case BPF_LDX|BPF_MSH|BPF_B: 389 MOVid(ins->k, ESI); 390 CMPrd(EDI, ESI); 391 JBb(7); 392 ZEROrd(EAX); 393 POP(EBX); 394 POP(EDI); 395 POP(ESI); 396 LEAVE(); 397 RET(); 398 ZEROrd(EDX); 399 MOVobb(EBX, ESI, DL); 400 ANDib(0x0f, DL); 401 SHLib(2, EDX); 402 break; 403 404 case BPF_LD|BPF_IMM: 405 MOVid(ins->k, EAX); 406 break; 407 408 case BPF_LDX|BPF_IMM: 409 MOVid(ins->k, EDX); 410 break; 411 412 case BPF_LD|BPF_MEM: 413 MOVrd(EBP, ECX); 414 MOVid(((int)ins->k - BPF_MEMWORDS) * 415 sizeof(uint32_t), ESI); 416 MOVobd(ECX, ESI, EAX); 417 break; 418 419 case BPF_LDX|BPF_MEM: 420 MOVrd(EBP, ECX); 421 MOVid(((int)ins->k - BPF_MEMWORDS) * 422 sizeof(uint32_t), ESI); 423 MOVobd(ECX, ESI, EDX); 424 break; 425 426 case BPF_ST: 427 /* 428 * XXX this command and the following could 429 * be optimized if the previous instruction 430 * was already of this type 431 */ 432 MOVrd(EBP, ECX); 433 MOVid(((int)ins->k - BPF_MEMWORDS) * 434 sizeof(uint32_t), ESI); 435 MOVomd(EAX, ECX, ESI); 436 break; 437 438 case BPF_STX: 439 MOVrd(EBP, ECX); 440 MOVid(((int)ins->k - BPF_MEMWORDS) * 441 sizeof(uint32_t), ESI); 442 MOVomd(EDX, ECX, ESI); 443 break; 444 445 case BPF_JMP|BPF_JA: 446 JUMP(ins->k); 447 break; 448 449 case BPF_JMP|BPF_JGT|BPF_K: 450 if (ins->jt == ins->jf) { 451 JUMP(ins->jt); 452 break; 453 } 454 CMPid(ins->k, EAX); 455 JCC(JA, JBE); 456 break; 457 458 case BPF_JMP|BPF_JGE|BPF_K: 459 if (ins->jt == ins->jf) { 460 JUMP(ins->jt); 461 break; 462 } 463 CMPid(ins->k, EAX); 464 JCC(JAE, JB); 465 break; 466 467 case BPF_JMP|BPF_JEQ|BPF_K: 468 if (ins->jt == ins->jf) { 469 JUMP(ins->jt); 470 break; 471 } 472 CMPid(ins->k, EAX); 473 JCC(JE, JNE); 474 break; 475 476 case BPF_JMP|BPF_JSET|BPF_K: 477 if (ins->jt == ins->jf) { 478 JUMP(ins->jt); 479 break; 480 } 481 TESTid(ins->k, EAX); 482 JCC(JNE, JE); 483 break; 484 485 case BPF_JMP|BPF_JGT|BPF_X: 486 if (ins->jt == ins->jf) { 487 JUMP(ins->jt); 488 break; 489 } 490 CMPrd(EDX, EAX); 491 JCC(JA, JBE); 492 break; 493 494 case BPF_JMP|BPF_JGE|BPF_X: 495 if (ins->jt == ins->jf) { 496 JUMP(ins->jt); 497 break; 498 } 499 CMPrd(EDX, EAX); 500 JCC(JAE, JB); 501 break; 502 503 case BPF_JMP|BPF_JEQ|BPF_X: 504 if (ins->jt == ins->jf) { 505 JUMP(ins->jt); 506 break; 507 } 508 CMPrd(EDX, EAX); 509 JCC(JE, JNE); 510 break; 511 512 case BPF_JMP|BPF_JSET|BPF_X: 513 if (ins->jt == ins->jf) { 514 JUMP(ins->jt); 515 break; 516 } 517 TESTrd(EDX, EAX); 518 JCC(JNE, JE); 519 break; 520 521 case BPF_ALU|BPF_ADD|BPF_X: 522 ADDrd(EDX, EAX); 523 break; 524 525 case BPF_ALU|BPF_SUB|BPF_X: 526 SUBrd(EDX, EAX); 527 break; 528 529 case BPF_ALU|BPF_MUL|BPF_X: 530 MOVrd(EDX, ECX); 531 MULrd(EDX); 532 MOVrd(ECX, EDX); 533 break; 534 535 case BPF_ALU|BPF_DIV|BPF_X: 536 TESTrd(EDX, EDX); 537 if (save_esp) { 538 if (fpkt) { 539 JNEb(7); 540 ZEROrd(EAX); 541 POP(EBX); 542 POP(EDI); 543 } else { 544 JNEb(5); 545 ZEROrd(EAX); 546 } 547 POP(ESI); 548 LEAVE(); 549 } else { 550 JNEb(3); 551 ZEROrd(EAX); 552 } 553 RET(); 554 MOVrd(EDX, ECX); 555 ZEROrd(EDX); 556 DIVrd(ECX); 557 MOVrd(ECX, EDX); 558 break; 559 560 case BPF_ALU|BPF_AND|BPF_X: 561 ANDrd(EDX, EAX); 562 break; 563 564 case BPF_ALU|BPF_OR|BPF_X: 565 ORrd(EDX, EAX); 566 break; 567 568 case BPF_ALU|BPF_LSH|BPF_X: 569 MOVrd(EDX, ECX); 570 SHL_CLrb(EAX); 571 break; 572 573 case BPF_ALU|BPF_RSH|BPF_X: 574 MOVrd(EDX, ECX); 575 SHR_CLrb(EAX); 576 break; 577 578 case BPF_ALU|BPF_ADD|BPF_K: 579 ADD_EAXi(ins->k); 580 break; 581 582 case BPF_ALU|BPF_SUB|BPF_K: 583 SUB_EAXi(ins->k); 584 break; 585 586 case BPF_ALU|BPF_MUL|BPF_K: 587 MOVrd(EDX, ECX); 588 MOVid(ins->k, EDX); 589 MULrd(EDX); 590 MOVrd(ECX, EDX); 591 break; 592 593 case BPF_ALU|BPF_DIV|BPF_K: 594 MOVrd(EDX, ECX); 595 ZEROrd(EDX); 596 MOVid(ins->k, ESI); 597 DIVrd(ESI); 598 MOVrd(ECX, EDX); 599 break; 600 601 case BPF_ALU|BPF_AND|BPF_K: 602 ANDid(ins->k, EAX); 603 break; 604 605 case BPF_ALU|BPF_OR|BPF_K: 606 ORid(ins->k, EAX); 607 break; 608 609 case BPF_ALU|BPF_LSH|BPF_K: 610 SHLib((ins->k) & 0xff, EAX); 611 break; 612 613 case BPF_ALU|BPF_RSH|BPF_K: 614 SHRib((ins->k) & 0xff, EAX); 615 break; 616 617 case BPF_ALU|BPF_NEG: 618 NEGd(EAX); 619 break; 620 621 case BPF_MISC|BPF_TAX: 622 MOVrd(EAX, EDX); 623 break; 624 625 case BPF_MISC|BPF_TXA: 626 MOVrd(EDX, EAX); 627 break; 628 } 629 ins++; 630 } 631 632 if (pass > 0) 633 continue; 634 635 *size = stream.cur_ip; 636#ifdef _KERNEL 637 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT); 638 if (stream.ibuf == NULL) 639 break; 640#else 641 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE, 642 MAP_ANON, -1, 0); 643 if (stream.ibuf == MAP_FAILED) { 644 stream.ibuf = NULL; 645 break; 646 } 647#endif 648 649 /* 650 * Modify the reference table to contain the offsets and 651 * not the lengths of the instructions. 652 */ 653 if (fjmp) 654 for (i = 1; i < nins + 1; i++) 655 stream.refs[i] += stream.refs[i - 1]; 656 657 /* Reset the counters. */ 658 stream.cur_ip = 0; 659 stream.bpf_pc = 0; 660 661 /* The second pass creates the actual code. */ 662 emitm = emit_code; 663 } 664 665 /* 666 * The reference table is needed only during compilation, 667 * now we can free it. 668 */ 669 if (fjmp) 670#ifdef _KERNEL 671 free(stream.refs, M_BPFJIT); 672#else 673 free(stream.refs); 674#endif 675 676#ifndef _KERNEL 677 if (stream.ibuf != NULL && 678 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) { 679 munmap(stream.ibuf, *size); 680 stream.ibuf = NULL; 681 } 682#endif 683 684 return ((bpf_filter_func)stream.ibuf); 685} 686