sys/amd64/amd64/bpf_jit_machdep.c

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