sys/amd64/amd64/bpf_jit_machdep.c

   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 }