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 <sys/mbuf.h>
  43 #include <net/if.h>
  44 #else
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <sys/mman.h>
  48 #include <sys/param.h>
  49 #endif
  50
  51 #include <sys/types.h>
  52
  53 #include <net/bpf.h>
  54 #include <net/bpf_jitter.h>
  55
  56 #include <amd64/amd64/bpf_jit_machdep.h>
  57
  58 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *);
  59
  60 /*
  61  * Emit routine to update the jump table.
  62  */
  63 static void
  64 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
  65 {
  66
  67         if (stream->refs != NULL)
  68                 (stream->refs)[stream->bpf_pc] += len;
  69         stream->cur_ip += len;
  70 }
  71
  72 /*
  73  * Emit routine to output the actual binary code.
  74  */
  75 static void
  76 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
  77 {
  78
  79         switch (len) {
  80         case 1:
  81                 stream->ibuf[stream->cur_ip] = (u_char)value;
  82                 stream->cur_ip++;
  83                 break;
  84
  85         case 2:
  86                 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
  87                 stream->cur_ip += 2;
  88                 break;
  89
  90         case 4:
  91                 *((u_int *)(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                                 if (ins->jt == ins->jf) {
 428                                         JUMP(ins->jt);
 429                                         break;
 430                                 }
 431                                 CMPid(ins->k, EAX);
 432                                 JCC(JA, JBE);
 433                                 break;
 434
 435                         case BPF_JMP|BPF_JGE|BPF_K:
 436                                 if (ins->jt == ins->jf) {
 437                                         JUMP(ins->jt);
 438                                         break;
 439                                 }
 440                                 CMPid(ins->k, EAX);
 441                                 JCC(JAE, JB);
 442                                 break;
 443
 444                         case BPF_JMP|BPF_JEQ|BPF_K:
 445                                 if (ins->jt == ins->jf) {
 446                                         JUMP(ins->jt);
 447                                         break;
 448                                 }
 449                                 CMPid(ins->k, EAX);
 450                                 JCC(JE, JNE);
 451                                 break;
 452
 453                         case BPF_JMP|BPF_JSET|BPF_K:
 454                                 if (ins->jt == ins->jf) {
 455                                         JUMP(ins->jt);
 456                                         break;
 457                                 }
 458                                 TESTid(ins->k, EAX);
 459                                 JCC(JNE, JE);
 460                                 break;
 461
 462                         case BPF_JMP|BPF_JGT|BPF_X:
 463                                 if (ins->jt == ins->jf) {
 464                                         JUMP(ins->jt);
 465                                         break;
 466                                 }
 467                                 CMPrd(EDX, EAX);
 468                                 JCC(JA, JBE);
 469                                 break;
 470
 471                         case BPF_JMP|BPF_JGE|BPF_X:
 472                                 if (ins->jt == ins->jf) {
 473                                         JUMP(ins->jt);
 474                                         break;
 475                                 }
 476                                 CMPrd(EDX, EAX);
 477                                 JCC(JAE, JB);
 478                                 break;
 479
 480                         case BPF_JMP|BPF_JEQ|BPF_X:
 481                                 if (ins->jt == ins->jf) {
 482                                         JUMP(ins->jt);
 483                                         break;
 484                                 }
 485                                 CMPrd(EDX, EAX);
 486                                 JCC(JE, JNE);
 487                                 break;
 488
 489                         case BPF_JMP|BPF_JSET|BPF_X:
 490                                 if (ins->jt == ins->jf) {
 491                                         JUMP(ins->jt);
 492                                         break;
 493                                 }
 494                                 TESTrd(EDX, EAX);
 495                                 JCC(JNE, JE);
 496                                 break;
 497
 498                         case BPF_ALU|BPF_ADD|BPF_X:
 499                                 ADDrd(EDX, EAX);
 500                                 break;
 501
 502                         case BPF_ALU|BPF_SUB|BPF_X:
 503                                 SUBrd(EDX, EAX);
 504                                 break;
 505
 506                         case BPF_ALU|BPF_MUL|BPF_X:
 507                                 MOVrd(EDX, ECX);
 508                                 MULrd(EDX);
 509                                 MOVrd(ECX, EDX);
 510                                 break;
 511
 512                         case BPF_ALU|BPF_DIV|BPF_X:
 513                                 TESTrd(EDX, EDX);
 514                                 if (fmem) {
 515                                         JNEb(4);
 516                                         ZEROrd(EAX);
 517                                         LEAVE();
 518                                 } else {
 519                                         JNEb(3);
 520                                         ZEROrd(EAX);
 521                                 }
 522                                 RET();
 523                                 MOVrd(EDX, ECX);
 524                                 ZEROrd(EDX);
 525                                 DIVrd(ECX);
 526                                 MOVrd(ECX, EDX);
 527                                 break;
 528
 529                         case BPF_ALU|BPF_AND|BPF_X:
 530                                 ANDrd(EDX, EAX);
 531                                 break;
 532
 533                         case BPF_ALU|BPF_OR|BPF_X:
 534                                 ORrd(EDX, EAX);
 535                                 break;
 536
 537                         case BPF_ALU|BPF_LSH|BPF_X:
 538                                 MOVrd(EDX, ECX);
 539                                 SHL_CLrb(EAX);
 540                                 break;
 541
 542                         case BPF_ALU|BPF_RSH|BPF_X:
 543                                 MOVrd(EDX, ECX);
 544                                 SHR_CLrb(EAX);
 545                                 break;
 546
 547                         case BPF_ALU|BPF_ADD|BPF_K:
 548                                 ADD_EAXi(ins->k);
 549                                 break;
 550
 551                         case BPF_ALU|BPF_SUB|BPF_K:
 552                                 SUB_EAXi(ins->k);
 553                                 break;
 554
 555                         case BPF_ALU|BPF_MUL|BPF_K:
 556                                 MOVrd(EDX, ECX);
 557                                 MOVid(ins->k, EDX);
 558                                 MULrd(EDX);
 559                                 MOVrd(ECX, EDX);
 560                                 break;
 561
 562                         case BPF_ALU|BPF_DIV|BPF_K:
 563                                 MOVrd(EDX, ECX);
 564                                 ZEROrd(EDX);
 565                                 MOVid(ins->k, ESI);
 566                                 DIVrd(ESI);
 567                                 MOVrd(ECX, EDX);
 568                                 break;
 569
 570                         case BPF_ALU|BPF_AND|BPF_K:
 571                                 ANDid(ins->k, EAX);
 572                                 break;
 573
 574                         case BPF_ALU|BPF_OR|BPF_K:
 575                                 ORid(ins->k, EAX);
 576                                 break;
 577
 578                         case BPF_ALU|BPF_LSH|BPF_K:
 579                                 SHLib((ins->k) & 0xff, EAX);
 580                                 break;
 581
 582                         case BPF_ALU|BPF_RSH|BPF_K:
 583                                 SHRib((ins->k) & 0xff, EAX);
 584                                 break;
 585
 586                         case BPF_ALU|BPF_NEG:
 587                                 NEGd(EAX);
 588                                 break;
 589
 590                         case BPF_MISC|BPF_TAX:
 591                                 MOVrd(EAX, EDX);
 592                                 break;
 593
 594                         case BPF_MISC|BPF_TXA:
 595                                 MOVrd(EDX, EAX);
 596                                 break;
 597                         }
 598                         ins++;
 599                 }
 600
 601                 if (pass > 0)
 602                         continue;
 603
 604                 *size = stream.cur_ip;
 605 #ifdef _KERNEL
 606                 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT);
 607                 if (stream.ibuf == NULL)
 608                         break;
 609 #else
 610                 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE,
 611                     MAP_ANON, -1, 0);
 612                 if (stream.ibuf == MAP_FAILED) {
 613                         stream.ibuf = NULL;
 614                         break;
 615                 }
 616 #endif
 617
 618                 /*
 619                  * Modify the reference table to contain the offsets and
 620                  * not the lengths of the instructions.
 621                  */
 622                 if (fjmp)
 623                         for (i = 1; i < nins + 1; i++)
 624                                 stream.refs[i] += stream.refs[i - 1];
 625
 626                 /* Reset the counters. */
 627                 stream.cur_ip = 0;
 628                 stream.bpf_pc = 0;
 629
 630                 /* The second pass creates the actual code. */
 631                 emitm = emit_code;
 632         }
 633
 634         /*
 635          * The reference table is needed only during compilation,
 636          * now we can free it.
 637          */
 638         if (fjmp)
 639 #ifdef _KERNEL
 640                 free(stream.refs, M_BPFJIT);
 641 #else
 642                 free(stream.refs);
 643 #endif
 644
 645 #ifndef _KERNEL
 646         if (stream.ibuf != NULL &&
 647             mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) {
 648                 munmap(stream.ibuf, *size);
 649                 stream.ibuf = NULL;
 650         }
 651 #endif
 652
 653         return ((bpf_filter_func)stream.ibuf);
 654 }