sys/amd64/amd64/bpf_jit_machdep.c

   1 /*-
   2  * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy)
   3  * Copyright (C) 2005-2008 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 #endif
  46
  47 #include <sys/types.h>
  48
  49 #include <net/bpf.h>
  50 #include <net/bpf_jitter.h>
  51
  52 #include <amd64/amd64/bpf_jit_machdep.h>
  53
  54 bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, int *);
  55
  56 /*
  57  * emit routine to update the jump table
  58  */
  59 static void
  60 emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len)
  61 {
  62
  63         (stream->refs)[stream->bpf_pc] += len;
  64         stream->cur_ip += len;
  65 }
  66
  67 /*
  68  * emit routine to output the actual binary code
  69  */
  70 static void
  71 emit_code(bpf_bin_stream *stream, u_int value, u_int len)
  72 {
  73
  74         switch (len) {
  75         case 1:
  76                 stream->ibuf[stream->cur_ip] = (u_char)value;
  77                 stream->cur_ip++;
  78                 break;
  79
  80         case 2:
  81                 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value;
  82                 stream->cur_ip += 2;
  83                 break;
  84
  85         case 4:
  86                 *((u_int *)(stream->ibuf + stream->cur_ip)) = value;
  87                 stream->cur_ip += 4;
  88                 break;
  89         }
  90
  91         return;
  92 }
  93
  94 /*
  95  * Function that does the real stuff
  96  */
  97 bpf_filter_func
  98 bpf_jit_compile(struct bpf_insn *prog, u_int nins, int *mem)
  99 {
 100         struct bpf_insn *ins;
 101         u_int i, pass;
 102         bpf_bin_stream stream;
 103
 104         /*
 105          * NOTE: do not modify the name of this variable, as it's used by
 106          * the macros to emit code.
 107          */
 108         emit_func emitm;
 109
 110         /* Allocate the reference table for the jumps */
 111 #ifdef _KERNEL
 112         stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int),
 113             M_BPFJIT, M_NOWAIT);
 114 #else
 115         stream.refs = (u_int *)malloc((nins + 1) * sizeof(u_int));
 116 #endif
 117         if (stream.refs == NULL)
 118                 return (NULL);
 119
 120         /* Reset the reference table */
 121         for (i = 0; i < nins + 1; i++)
 122                 stream.refs[i] = 0;
 123
 124         stream.cur_ip = 0;
 125         stream.bpf_pc = 0;
 126
 127         /*
 128          * the first pass will emit the lengths of the instructions
 129          * to create the reference table
 130          */
 131         emitm = emit_length;
 132
 133         pass = 0;
 134         for (;;) {
 135                 ins = prog;
 136
 137                 /* create the procedure header */
 138                 MOVrq2(RBX, R8);
 139                 MOVrq(RDI, RBX);
 140                 MOVrd2(ESI, R9D);
 141                 MOVrd(EDX, EDI);
 142
 143                 for (i = 0; i < nins; i++) {
 144                         stream.bpf_pc++;
 145
 146                         switch (ins->code) {
 147                         default:
 148 #ifdef _KERNEL
 149                                 return (NULL);
 150 #else
 151                                 abort();
 152 #endif
 153
 154                         case BPF_RET|BPF_K:
 155                                 MOVid(ins->k, EAX);
 156                                 MOVrq3(R8, RBX);
 157                                 RET();
 158                                 break;
 159
 160                         case BPF_RET|BPF_A:
 161                                 MOVrq3(R8, RBX);
 162                                 RET();
 163                                 break;
 164
 165                         case BPF_LD|BPF_W|BPF_ABS:
 166                                 MOVid(ins->k, ESI);
 167                                 CMPrd(EDI, ESI);
 168                                 JAb(12);
 169                                 MOVrd(EDI, ECX);
 170                                 SUBrd(ESI, ECX);
 171                                 CMPid(sizeof(int32_t), ECX);
 172                                 JAEb(6);
 173                                 ZEROrd(EAX);
 174                                 MOVrq3(R8, RBX);
 175                                 RET();
 176                                 MOVobd(RBX, RSI, EAX);
 177                                 BSWAP(EAX);
 178                                 break;
 179
 180                         case BPF_LD|BPF_H|BPF_ABS:
 181                                 ZEROrd(EAX);
 182                                 MOVid(ins->k, ESI);
 183                                 CMPrd(EDI, ESI);
 184                                 JAb(12);
 185                                 MOVrd(EDI, ECX);
 186                                 SUBrd(ESI, ECX);
 187                                 CMPid(sizeof(int16_t), ECX);
 188                                 JAEb(4);
 189                                 MOVrq3(R8, RBX);
 190                                 RET();
 191                                 MOVobw(RBX, RSI, AX);
 192                                 SWAP_AX();
 193                                 break;
 194
 195                         case BPF_LD|BPF_B|BPF_ABS:
 196                                 ZEROrd(EAX);
 197                                 MOVid(ins->k, ESI);
 198                                 CMPrd(EDI, ESI);
 199                                 JBb(4);
 200                                 MOVrq3(R8, RBX);
 201                                 RET();
 202                                 MOVobb(RBX, RSI, AL);
 203                                 break;
 204
 205                         case BPF_LD|BPF_W|BPF_LEN:
 206                                 MOVrd3(R9D, EAX);
 207                                 break;
 208
 209                         case BPF_LDX|BPF_W|BPF_LEN:
 210                                 MOVrd3(R9D, EDX);
 211                                 break;
 212
 213                         case BPF_LD|BPF_W|BPF_IND:
 214                                 CMPrd(EDI, EDX);
 215                                 JAb(27);
 216                                 MOVid(ins->k, ESI);
 217                                 MOVrd(EDI, ECX);
 218                                 SUBrd(EDX, ECX);
 219                                 CMPrd(ESI, ECX);
 220                                 JBb(14);
 221                                 ADDrd(EDX, ESI);
 222                                 MOVrd(EDI, ECX);
 223                                 SUBrd(ESI, ECX);
 224                                 CMPid(sizeof(int32_t), ECX);
 225                                 JAEb(6);
 226                                 ZEROrd(EAX);
 227                                 MOVrq3(R8, RBX);
 228                                 RET();
 229                                 MOVobd(RBX, RSI, EAX);
 230                                 BSWAP(EAX);
 231                                 break;
 232
 233                         case BPF_LD|BPF_H|BPF_IND:
 234                                 ZEROrd(EAX);
 235                                 CMPrd(EDI, EDX);
 236                                 JAb(27);
 237                                 MOVid(ins->k, ESI);
 238                                 MOVrd(EDI, ECX);
 239                                 SUBrd(EDX, ECX);
 240                                 CMPrd(ESI, ECX);
 241                                 JBb(14);
 242                                 ADDrd(EDX, ESI);
 243                                 MOVrd(EDI, ECX);
 244                                 SUBrd(ESI, ECX);
 245                                 CMPid(sizeof(int16_t), ECX);
 246                                 JAEb(4);
 247                                 MOVrq3(R8, RBX);
 248                                 RET();
 249                                 MOVobw(RBX, RSI, AX);
 250                                 SWAP_AX();
 251                                 break;
 252
 253                         case BPF_LD|BPF_B|BPF_IND:
 254                                 ZEROrd(EAX);
 255                                 CMPrd(EDI, EDX);
 256                                 JAEb(13);
 257                                 MOVid(ins->k, ESI);
 258                                 MOVrd(EDI, ECX);
 259                                 SUBrd(EDX, ECX);
 260                                 CMPrd(ESI, ECX);
 261                                 JAb(4);
 262                                 MOVrq3(R8, RBX);
 263                                 RET();
 264                                 ADDrd(EDX, ESI);
 265                                 MOVobb(RBX, RSI, AL);
 266                                 break;
 267
 268                         case BPF_LDX|BPF_MSH|BPF_B:
 269                                 MOVid(ins->k, ESI);
 270                                 CMPrd(EDI, ESI);
 271                                 JBb(6);
 272                                 ZEROrd(EAX);
 273                                 MOVrq3(R8, RBX);
 274                                 RET();
 275                                 ZEROrd(EDX);
 276                                 MOVobb(RBX, RSI, DL);
 277                                 ANDib(0x0f, DL);
 278                                 SHLib(2, EDX);
 279                                 break;
 280
 281                         case BPF_LD|BPF_IMM:
 282                                 MOVid(ins->k, EAX);
 283                                 break;
 284
 285                         case BPF_LDX|BPF_IMM:
 286                                 MOVid(ins->k, EDX);
 287                                 break;
 288
 289                         case BPF_LD|BPF_MEM:
 290                                 MOViq((uintptr_t)mem, RCX);
 291                                 MOVid(ins->k * 4, ESI);
 292                                 MOVobd(RCX, RSI, EAX);
 293                                 break;
 294
 295                         case BPF_LDX|BPF_MEM:
 296                                 MOViq((uintptr_t)mem, RCX);
 297                                 MOVid(ins->k * 4, ESI);
 298                                 MOVobd(RCX, RSI, EDX);
 299                                 break;
 300
 301                         case BPF_ST:
 302                                 /*
 303                                  * XXX this command and the following could
 304                                  * be optimized if the previous instruction
 305                                  * was already of this type
 306                                  */
 307                                 MOViq((uintptr_t)mem, RCX);
 308                                 MOVid(ins->k * 4, ESI);
 309                                 MOVomd(EAX, RCX, RSI);
 310                                 break;
 311
 312                         case BPF_STX:
 313                                 MOViq((uintptr_t)mem, RCX);
 314                                 MOVid(ins->k * 4, ESI);
 315                                 MOVomd(EDX, RCX, RSI);
 316                                 break;
 317
 318                         case BPF_JMP|BPF_JA:
 319                                 JMP(stream.refs[stream.bpf_pc + ins->k] -
 320                                     stream.refs[stream.bpf_pc]);
 321                                 break;
 322
 323                         case BPF_JMP|BPF_JGT|BPF_K:
 324                                 if (ins->jt == 0 && ins->jf == 0)
 325                                         break;
 326                                 CMPid(ins->k, EAX);
 327                                 JCC(JA, JBE);
 328                                 break;
 329
 330                         case BPF_JMP|BPF_JGE|BPF_K:
 331                                 if (ins->jt == 0 && ins->jf == 0)
 332                                         break;
 333                                 CMPid(ins->k, EAX);
 334                                 JCC(JAE, JB);
 335                                 break;
 336
 337                         case BPF_JMP|BPF_JEQ|BPF_K:
 338                                 if (ins->jt == 0 && ins->jf == 0)
 339                                         break;
 340                                 CMPid(ins->k, EAX);
 341                                 JCC(JE, JNE);
 342                                 break;
 343
 344                         case BPF_JMP|BPF_JSET|BPF_K:
 345                                 if (ins->jt == 0 && ins->jf == 0)
 346                                         break;
 347                                 TESTid(ins->k, EAX);
 348                                 JCC(JNE, JE);
 349                                 break;
 350
 351                         case BPF_JMP|BPF_JGT|BPF_X:
 352                                 if (ins->jt == 0 && ins->jf == 0)
 353                                         break;
 354                                 CMPrd(EDX, EAX);
 355                                 JCC(JA, JBE);
 356                                 break;
 357
 358                         case BPF_JMP|BPF_JGE|BPF_X:
 359                                 if (ins->jt == 0 && ins->jf == 0)
 360                                         break;
 361                                 CMPrd(EDX, EAX);
 362                                 JCC(JAE, JB);
 363                                 break;
 364
 365                         case BPF_JMP|BPF_JEQ|BPF_X:
 366                                 if (ins->jt == 0 && ins->jf == 0)
 367                                         break;
 368                                 CMPrd(EDX, EAX);
 369                                 JCC(JE, JNE);
 370                                 break;
 371
 372                         case BPF_JMP|BPF_JSET|BPF_X:
 373                                 if (ins->jt == 0 && ins->jf == 0)
 374                                         break;
 375                                 TESTrd(EDX, EAX);
 376                                 JCC(JNE, JE);
 377                                 break;
 378
 379                         case BPF_ALU|BPF_ADD|BPF_X:
 380                                 ADDrd(EDX, EAX);
 381                                 break;
 382
 383                         case BPF_ALU|BPF_SUB|BPF_X:
 384                                 SUBrd(EDX, EAX);
 385                                 break;
 386
 387                         case BPF_ALU|BPF_MUL|BPF_X:
 388                                 MOVrd(EDX, ECX);
 389                                 MULrd(EDX);
 390                                 MOVrd(ECX, EDX);
 391                                 break;
 392
 393                         case BPF_ALU|BPF_DIV|BPF_X:
 394                                 TESTrd(EDX, EDX);
 395                                 JNEb(6);
 396                                 ZEROrd(EAX);
 397                                 MOVrq3(R8, RBX);
 398                                 RET();
 399                                 MOVrd(EDX, ECX);
 400                                 ZEROrd(EDX);
 401                                 DIVrd(ECX);
 402                                 MOVrd(ECX, EDX);
 403                                 break;
 404
 405                         case BPF_ALU|BPF_AND|BPF_X:
 406                                 ANDrd(EDX, EAX);
 407                                 break;
 408
 409                         case BPF_ALU|BPF_OR|BPF_X:
 410                                 ORrd(EDX, EAX);
 411                                 break;
 412
 413                         case BPF_ALU|BPF_LSH|BPF_X:
 414                                 MOVrd(EDX, ECX);
 415                                 SHL_CLrb(EAX);
 416                                 break;
 417
 418                         case BPF_ALU|BPF_RSH|BPF_X:
 419                                 MOVrd(EDX, ECX);
 420                                 SHR_CLrb(EAX);
 421                                 break;
 422
 423                         case BPF_ALU|BPF_ADD|BPF_K:
 424                                 ADD_EAXi(ins->k);
 425                                 break;
 426
 427                         case BPF_ALU|BPF_SUB|BPF_K:
 428                                 SUB_EAXi(ins->k);
 429                                 break;
 430
 431                         case BPF_ALU|BPF_MUL|BPF_K:
 432                                 MOVrd(EDX, ECX);
 433                                 MOVid(ins->k, EDX);
 434                                 MULrd(EDX);
 435                                 MOVrd(ECX, EDX);
 436                                 break;
 437
 438                         case BPF_ALU|BPF_DIV|BPF_K:
 439                                 MOVrd(EDX, ECX);
 440                                 ZEROrd(EDX);
 441                                 MOVid(ins->k, ESI);
 442                                 DIVrd(ESI);
 443                                 MOVrd(ECX, EDX);
 444                                 break;
 445
 446                         case BPF_ALU|BPF_AND|BPF_K:
 447                                 ANDid(ins->k, EAX);
 448                                 break;
 449
 450                         case BPF_ALU|BPF_OR|BPF_K:
 451                                 ORid(ins->k, EAX);
 452                                 break;
 453
 454                         case BPF_ALU|BPF_LSH|BPF_K:
 455                                 SHLib((ins->k) & 0xff, EAX);
 456                                 break;
 457
 458                         case BPF_ALU|BPF_RSH|BPF_K:
 459                                 SHRib((ins->k) & 0xff, EAX);
 460                                 break;
 461
 462                         case BPF_ALU|BPF_NEG:
 463                                 NEGd(EAX);
 464                                 break;
 465
 466                         case BPF_MISC|BPF_TAX:
 467                                 MOVrd(EAX, EDX);
 468                                 break;
 469
 470                         case BPF_MISC|BPF_TXA:
 471                                 MOVrd(EDX, EAX);
 472                                 break;
 473                         }
 474                         ins++;
 475                 }
 476
 477                 pass++;
 478                 if (pass == 2)
 479                         break;
 480
 481 #ifdef _KERNEL
 482                 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT);
 483                 if (stream.ibuf == NULL) {
 484                         free(stream.refs, M_BPFJIT);
 485                         return (NULL);
 486                 }
 487 #else
 488                 stream.ibuf = (char *)malloc(stream.cur_ip);
 489                 if (stream.ibuf == NULL) {
 490                         free(stream.refs);
 491                         return (NULL);
 492                 }
 493 #endif
 494
 495                 /*
 496                  * modify the reference table to contain the offsets and
 497                  * not the lengths of the instructions
 498                  */
 499                 for (i = 1; i < nins + 1; i++)
 500                         stream.refs[i] += stream.refs[i - 1];
 501
 502                 /* Reset the counters */
 503                 stream.cur_ip = 0;
 504                 stream.bpf_pc = 0;
 505
 506                 /* the second pass creates the actual code */
 507                 emitm = emit_code;
 508         }
 509
 510         /*
 511          * the reference table is needed only during compilation,
 512          * now we can free it
 513          */
 514 #ifdef _KERNEL
 515         free(stream.refs, M_BPFJIT);
 516 #else
 517         free(stream.refs);
 518 #endif
 519
 520         return ((bpf_filter_func)stream.ibuf);
 521 }