sys/amd64/amd64/bpf_jit_machdep.c

   1 /*-
   2  * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
   3  * Copyright (C) 2005-2009 Jung-uk Kim <jkim@FreeBSD.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  * notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the Politecnico di Torino nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #include <sys/cdefs.h>
  33 __FBSDID("$FreeBSD$");
  34
  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/socket.h>
  41 #include <sys/malloc.h>
  42 #include <net/if.h>
  43 #else
  44 #include <stdlib.h>
  45 #include <string.h>
  46 #include <sys/mman.h>
  47 #include <sys/param.h>
  48 #endif
  49
  50 #include <sys/types.h>
  51
  52 #include <net/bpf.h>
  53 #include <net/bpf_jitter.h>
  54
  55 #include <amd64/amd64/bpf_jit_machdep.h>
  56
  57 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *);
  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 *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
  86                 stream->cur_ip += 2;
  87                 break;
  88
  89         case 4:
  90                 *((u_int *)(stream->ibuf + stream->cur_ip)) = value;
  91                 stream->cur_ip += 4;
  92                 break;
  93         }
  94
  95         return;
  96 }
  97
  98 /*
  99  * Scan the filter program and find possible optimization.
 100  */
 101 static int
 102 bpf_jit_optimize(struct bpf_insn *prog, u_int nins)
 103 {
 104         int flags;
 105         u_int i;
 106
 107         /* Do we return immediately? */
 108         if (BPF_CLASS(prog[0].code) == BPF_RET)
 109                 return (BPF_JIT_FRET);
 110
 111         for (flags = 0, i = 0; i < nins; i++) {
 112                 switch (prog[i].code) {
 113                 case BPF_LD|BPF_W|BPF_ABS:
 114                 case BPF_LD|BPF_H|BPF_ABS:
 115                 case BPF_LD|BPF_B|BPF_ABS:
 116                 case BPF_LD|BPF_W|BPF_IND:
 117                 case BPF_LD|BPF_H|BPF_IND:
 118                 case BPF_LD|BPF_B|BPF_IND:
 119                 case BPF_LDX|BPF_MSH|BPF_B:
 120                         flags |= BPF_JIT_FPKT;
 121                         break;
 122                 case BPF_LD|BPF_MEM:
 123                 case BPF_LDX|BPF_MEM:
 124                 case BPF_ST:
 125                 case BPF_STX:
 126                         flags |= BPF_JIT_FMEM;
 127                         break;
 128                 case BPF_LD|BPF_W|BPF_LEN:
 129                 case BPF_LDX|BPF_W|BPF_LEN:
 130                         flags |= BPF_JIT_FLEN;
 131                         break;
 132                 case BPF_JMP|BPF_JA:
 133                 case BPF_JMP|BPF_JGT|BPF_K:
 134                 case BPF_JMP|BPF_JGE|BPF_K:
 135                 case BPF_JMP|BPF_JEQ|BPF_K:
 136                 case BPF_JMP|BPF_JSET|BPF_K:
 137                 case BPF_JMP|BPF_JGT|BPF_X:
 138                 case BPF_JMP|BPF_JGE|BPF_X:
 139                 case BPF_JMP|BPF_JEQ|BPF_X:
 140                 case BPF_JMP|BPF_JSET|BPF_X:
 141                         flags |= BPF_JIT_FJMP;
 142                         break;
 143                 }
 144                 if (flags == BPF_JIT_FLAG_ALL)
 145                         break;
 146         }
 147
 148         return (flags);
 149 }
 150
 151 /*
 152  * Function that does the real stuff.
 153  */
 154 bpf_filter_func
 155 bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size)
 156 {
 157         bpf_bin_stream stream;
 158         struct bpf_insn *ins;
 159         int flags, fret, fpkt, fmem, fjmp, flen;
 160         u_int i, pass;
 161
 162         /*
 163          * NOTE: Do not modify the name of this variable, as it's used by
 164          * the macros to emit code.
 165          */
 166         emit_func emitm;
 167
 168         flags = bpf_jit_optimize(prog, nins);
 169         fret = (flags & BPF_JIT_FRET) != 0;
 170         fpkt = (flags & BPF_JIT_FPKT) != 0;
 171         fmem = (flags & BPF_JIT_FMEM) != 0;
 172         fjmp = (flags & BPF_JIT_FJMP) != 0;
 173         flen = (flags & BPF_JIT_FLEN) != 0;
 174
 175         if (fret)
 176                 nins = 1;
 177
 178         memset(&stream, 0, sizeof(stream));
 179
 180         /* Allocate the reference table for the jumps. */
 181         if (fjmp) {
 182 #ifdef _KERNEL
 183                 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT,
 184                     M_NOWAIT | M_ZERO);
 185 #else
 186                 stream.refs = calloc(nins + 1, sizeof(u_int));
 187 #endif
 188                 if (stream.refs == NULL)
 189                         return (NULL);
 190         }
 191
 192         /*
 193          * The first pass will emit the lengths of the instructions
 194          * to create the reference table.
 195          */
 196         emitm = emit_length;
 197
 198         for (pass = 0; pass < 2; pass++) {
 199                 ins = prog;
 200
 201                 /* Create the procedure header. */
 202                 if (fmem) {
 203                         PUSH(RBP);
 204                         MOVrq(RSP, RBP);
 205                         SUBib(BPF_MEMWORDS * sizeof(uint32_t), RSP);
 206                 }
 207                 if (flen)
 208                         MOVrd2(ESI, R9D);
 209                 if (fpkt) {
 210                         MOVrq2(RDI, R8);
 211                         MOVrd(EDX, EDI);
 212                 }
 213
 214                 for (i = 0; i < nins; i++) {
 215                         stream.bpf_pc++;
 216
 217                         switch (ins->code) {
 218                         default:
 219 #ifdef _KERNEL
 220                                 return (NULL);
 221 #else
 222                                 abort();
 223 #endif
 224
 225                         case BPF_RET|BPF_K:
 226                                 MOVid(ins->k, EAX);
 227                                 if (fmem)
 228                                         LEAVE();
 229                                 RET();
 230                                 break;
 231
 232                         case BPF_RET|BPF_A:
 233                                 if (fmem)
 234                                         LEAVE();
 235                                 RET();
 236                                 break;
 237
 238                         case BPF_LD|BPF_W|BPF_ABS:
 239                                 MOVid(ins->k, ESI);
 240                                 CMPrd(EDI, ESI);
 241                                 JAb(12);
 242                                 MOVrd(EDI, ECX);
 243                                 SUBrd(ESI, ECX);
 244                                 CMPid(sizeof(int32_t), ECX);
 245                                 if (fmem) {
 246                                         JAEb(4);
 247                                         ZEROrd(EAX);
 248                                         LEAVE();
 249                                 } else {
 250                                         JAEb(3);
 251                                         ZEROrd(EAX);
 252                                 }
 253                                 RET();
 254                                 MOVrq3(R8, RCX);
 255                                 MOVobd(RCX, RSI, EAX);
 256                                 BSWAP(EAX);
 257                                 break;
 258
 259                         case BPF_LD|BPF_H|BPF_ABS:
 260                                 ZEROrd(EAX);
 261                                 MOVid(ins->k, ESI);
 262                                 CMPrd(EDI, ESI);
 263                                 JAb(12);
 264                                 MOVrd(EDI, ECX);
 265                                 SUBrd(ESI, ECX);
 266                                 CMPid(sizeof(int16_t), ECX);
 267                                 if (fmem) {
 268                                         JAEb(2);
 269                                         LEAVE();
 270                                 } else
 271                                         JAEb(1);
 272                                 RET();
 273                                 MOVrq3(R8, RCX);
 274                                 MOVobw(RCX, RSI, AX);
 275                                 SWAP_AX();
 276                                 break;
 277
 278                         case BPF_LD|BPF_B|BPF_ABS:
 279                                 ZEROrd(EAX);
 280                                 MOVid(ins->k, ESI);
 281                                 CMPrd(EDI, ESI);
 282                                 if (fmem) {
 283                                         JBb(2);
 284                                         LEAVE();
 285                                 } else
 286                                         JBb(1);
 287                                 RET();
 288                                 MOVrq3(R8, RCX);
 289                                 MOVobb(RCX, RSI, AL);
 290                                 break;
 291
 292                         case BPF_LD|BPF_W|BPF_LEN:
 293                                 MOVrd3(R9D, EAX);
 294                                 break;
 295
 296                         case BPF_LDX|BPF_W|BPF_LEN:
 297                                 MOVrd3(R9D, EDX);
 298                                 break;
 299
 300                         case BPF_LD|BPF_W|BPF_IND:
 301                                 CMPrd(EDI, EDX);
 302                                 JAb(27);
 303                                 MOVid(ins->k, ESI);
 304                                 MOVrd(EDI, ECX);
 305                                 SUBrd(EDX, ECX);
 306                                 CMPrd(ESI, ECX);
 307                                 JBb(14);
 308                                 ADDrd(EDX, ESI);
 309                                 MOVrd(EDI, ECX);
 310                                 SUBrd(ESI, ECX);
 311                                 CMPid(sizeof(int32_t), ECX);
 312                                 if (fmem) {
 313                                         JAEb(4);
 314                                         ZEROrd(EAX);
 315                                         LEAVE();
 316                                 } else {
 317                                         JAEb(3);
 318                                         ZEROrd(EAX);
 319                                 }
 320                                 RET();
 321                                 MOVrq3(R8, RCX);
 322                                 MOVobd(RCX, RSI, EAX);
 323                                 BSWAP(EAX);
 324                                 break;
 325
 326                         case BPF_LD|BPF_H|BPF_IND:
 327                                 ZEROrd(EAX);
 328                                 CMPrd(EDI, EDX);
 329                                 JAb(27);
 330                                 MOVid(ins->k, ESI);
 331                                 MOVrd(EDI, ECX);
 332                                 SUBrd(EDX, ECX);
 333                                 CMPrd(ESI, ECX);
 334                                 JBb(14);
 335                                 ADDrd(EDX, ESI);
 336                                 MOVrd(EDI, ECX);
 337                                 SUBrd(ESI, ECX);
 338                                 CMPid(sizeof(int16_t), ECX);
 339                                 if (fmem) {
 340                                         JAEb(2);
 341                                         LEAVE();
 342                                 } else
 343                                         JAEb(1);
 344                                 RET();
 345                                 MOVrq3(R8, RCX);
 346                                 MOVobw(RCX, RSI, AX);
 347                                 SWAP_AX();
 348                                 break;
 349
 350                         case BPF_LD|BPF_B|BPF_IND:
 351                                 ZEROrd(EAX);
 352                                 CMPrd(EDI, EDX);
 353                                 JAEb(13);
 354                                 MOVid(ins->k, ESI);
 355                                 MOVrd(EDI, ECX);
 356                                 SUBrd(EDX, ECX);
 357                                 CMPrd(ESI, ECX);
 358                                 if (fmem) {
 359                                         JAb(2);
 360                                         LEAVE();
 361                                 } else
 362                                         JAb(1);
 363                                 RET();
 364                                 MOVrq3(R8, RCX);
 365                                 ADDrd(EDX, ESI);
 366                                 MOVobb(RCX, RSI, AL);
 367                                 break;
 368
 369                         case BPF_LDX|BPF_MSH|BPF_B:
 370                                 MOVid(ins->k, ESI);
 371                                 CMPrd(EDI, ESI);
 372                                 if (fmem) {
 373                                         JBb(4);
 374                                         ZEROrd(EAX);
 375                                         LEAVE();
 376                                 } else {
 377                                         JBb(3);
 378                                         ZEROrd(EAX);
 379                                 }
 380                                 RET();
 381                                 ZEROrd(EDX);
 382                                 MOVrq3(R8, RCX);
 383                                 MOVobb(RCX, RSI, DL);
 384                                 ANDib(0x0f, DL);
 385                                 SHLib(2, EDX);
 386                                 break;
 387
 388                         case BPF_LD|BPF_IMM:
 389                                 MOVid(ins->k, EAX);
 390                                 break;
 391
 392                         case BPF_LDX|BPF_IMM:
 393                                 MOVid(ins->k, EDX);
 394                                 break;
 395
 396                         case BPF_LD|BPF_MEM:
 397                                 MOVid(ins->k * sizeof(uint32_t), ESI);
 398                                 MOVobd(RSP, RSI, EAX);
 399                                 break;
 400
 401                         case BPF_LDX|BPF_MEM:
 402                                 MOVid(ins->k * sizeof(uint32_t), ESI);
 403                                 MOVobd(RSP, RSI, EDX);
 404                                 break;
 405
 406                         case BPF_ST:
 407                                 /*
 408                                  * XXX this command and the following could
 409                                  * be optimized if the previous instruction
 410                                  * was already of this type
 411                                  */
 412                                 MOVid(ins->k * sizeof(uint32_t), ESI);
 413                                 MOVomd(EAX, RSP, RSI);
 414                                 break;
 415
 416                         case BPF_STX:
 417                                 MOVid(ins->k * sizeof(uint32_t), ESI);
 418                                 MOVomd(EDX, RSP, RSI);
 419                                 break;
 420
 421                         case BPF_JMP|BPF_JA:
 422                                 JUMP(ins->k);
 423                                 break;
 424
 425                         case BPF_JMP|BPF_JGT|BPF_K:
 426                                 if (ins->jt == ins->jf) {
 427                                         JUMP(ins->jt);
 428                                         break;
 429                                 }
 430                                 CMPid(ins->k, EAX);
 431                                 JCC(JA, JBE);
 432                                 break;
 433
 434                         case BPF_JMP|BPF_JGE|BPF_K:
 435                                 if (ins->jt == ins->jf) {
 436                                         JUMP(ins->jt);
 437                                         break;
 438                                 }
 439                                 CMPid(ins->k, EAX);
 440                                 JCC(JAE, JB);
 441                                 break;
 442
 443                         case BPF_JMP|BPF_JEQ|BPF_K:
 444                                 if (ins->jt == ins->jf) {
 445                                         JUMP(ins->jt);
 446                                         break;
 447                                 }
 448                                 CMPid(ins->k, EAX);
 449                                 JCC(JE, JNE);
 450                                 break;
 451
 452                         case BPF_JMP|BPF_JSET|BPF_K:
 453                                 if (ins->jt == ins->jf) {
 454                                         JUMP(ins->jt);
 455                                         break;
 456                                 }
 457                                 TESTid(ins->k, EAX);
 458                                 JCC(JNE, JE);
 459                                 break;
 460
 461                         case BPF_JMP|BPF_JGT|BPF_X:
 462                                 if (ins->jt == ins->jf) {
 463                                         JUMP(ins->jt);
 464                                         break;
 465                                 }
 466                                 CMPrd(EDX, EAX);
 467                                 JCC(JA, JBE);
 468                                 break;
 469
 470                         case BPF_JMP|BPF_JGE|BPF_X:
 471                                 if (ins->jt == ins->jf) {
 472                                         JUMP(ins->jt);
 473                                         break;
 474                                 }
 475                                 CMPrd(EDX, EAX);
 476                                 JCC(JAE, JB);
 477                                 break;
 478
 479                         case BPF_JMP|BPF_JEQ|BPF_X:
 480                                 if (ins->jt == ins->jf) {
 481                                         JUMP(ins->jt);
 482                                         break;
 483                                 }
 484                                 CMPrd(EDX, EAX);
 485                                 JCC(JE, JNE);
 486                                 break;
 487
 488                         case BPF_JMP|BPF_JSET|BPF_X:
 489                                 if (ins->jt == ins->jf) {
 490                                         JUMP(ins->jt);
 491                                         break;
 492                                 }
 493                                 TESTrd(EDX, EAX);
 494                                 JCC(JNE, JE);
 495                                 break;
 496
 497                         case BPF_ALU|BPF_ADD|BPF_X:
 498                                 ADDrd(EDX, EAX);
 499                                 break;
 500
 501                         case BPF_ALU|BPF_SUB|BPF_X:
 502                                 SUBrd(EDX, EAX);
 503                                 break;
 504
 505                         case BPF_ALU|BPF_MUL|BPF_X:
 506                                 MOVrd(EDX, ECX);
 507                                 MULrd(EDX);
 508                                 MOVrd(ECX, EDX);
 509                                 break;
 510
 511                         case BPF_ALU|BPF_DIV|BPF_X:
 512                                 TESTrd(EDX, EDX);
 513                                 if (fmem) {
 514                                         JNEb(4);
 515                                         ZEROrd(EAX);
 516                                         LEAVE();
 517                                 } else {
 518                                         JNEb(3);
 519                                         ZEROrd(EAX);
 520                                 }
 521                                 RET();
 522                                 MOVrd(EDX, ECX);
 523                                 ZEROrd(EDX);
 524                                 DIVrd(ECX);
 525                                 MOVrd(ECX, EDX);
 526                                 break;
 527
 528                         case BPF_ALU|BPF_AND|BPF_X:
 529                                 ANDrd(EDX, EAX);
 530                                 break;
 531
 532                         case BPF_ALU|BPF_OR|BPF_X:
 533                                 ORrd(EDX, EAX);
 534                                 break;
 535
 536                         case BPF_ALU|BPF_LSH|BPF_X:
 537                                 MOVrd(EDX, ECX);
 538                                 SHL_CLrb(EAX);
 539                                 break;
 540
 541                         case BPF_ALU|BPF_RSH|BPF_X:
 542                                 MOVrd(EDX, ECX);
 543                                 SHR_CLrb(EAX);
 544                                 break;
 545
 546                         case BPF_ALU|BPF_ADD|BPF_K:
 547                                 ADD_EAXi(ins->k);
 548                                 break;
 549
 550                         case BPF_ALU|BPF_SUB|BPF_K:
 551                                 SUB_EAXi(ins->k);
 552                                 break;
 553
 554                         case BPF_ALU|BPF_MUL|BPF_K:
 555                                 MOVrd(EDX, ECX);
 556                                 MOVid(ins->k, EDX);
 557                                 MULrd(EDX);
 558                                 MOVrd(ECX, EDX);
 559                                 break;
 560
 561                         case BPF_ALU|BPF_DIV|BPF_K:
 562                                 MOVrd(EDX, ECX);
 563                                 ZEROrd(EDX);
 564                                 MOVid(ins->k, ESI);
 565                                 DIVrd(ESI);
 566                                 MOVrd(ECX, EDX);
 567                                 break;
 568
 569                         case BPF_ALU|BPF_AND|BPF_K:
 570                                 ANDid(ins->k, EAX);
 571                                 break;
 572
 573                         case BPF_ALU|BPF_OR|BPF_K:
 574                                 ORid(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(*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)stream.ibuf);
 653 }