sys/i386/i386/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 <i386/i386/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                 PUSH(EBP);
 139                 MOVrd(ESP, EBP);
 140                 PUSH(EDI);
 141                 PUSH(ESI);
 142                 PUSH(EBX);
 143                 MOVodd(8, EBP, EBX);
 144                 MOVodd(16, EBP, EDI);
 145
 146                 for (i = 0; i < nins; i++) {
 147                         stream.bpf_pc++;
 148
 149                         switch (ins->code) {
 150                         default:
 151 #ifdef _KERNEL
 152                                 return (NULL);
 153 #else
 154                                 abort();
 155 #endif
 156
 157                         case BPF_RET|BPF_K:
 158                                 MOVid(ins->k, EAX);
 159                                 POP(EBX);
 160                                 POP(ESI);
 161                                 POP(EDI);
 162                                 LEAVE_RET();
 163                                 break;
 164
 165                         case BPF_RET|BPF_A:
 166                                 POP(EBX);
 167                                 POP(ESI);
 168                                 POP(EDI);
 169                                 LEAVE_RET();
 170                                 break;
 171
 172                         case BPF_LD|BPF_W|BPF_ABS:
 173                                 MOVid(ins->k, ESI);
 174                                 CMPrd(EDI, ESI);
 175                                 JAb(12);
 176                                 MOVrd(EDI, ECX);
 177                                 SUBrd(ESI, ECX);
 178                                 CMPid(sizeof(int32_t), ECX);
 179                                 JAEb(7);
 180                                 ZEROrd(EAX);
 181                                 POP(EBX);
 182                                 POP(ESI);
 183                                 POP(EDI);
 184                                 LEAVE_RET();
 185                                 MOVobd(EBX, ESI, EAX);
 186                                 BSWAP(EAX);
 187                                 break;
 188
 189                         case BPF_LD|BPF_H|BPF_ABS:
 190                                 ZEROrd(EAX);
 191                                 MOVid(ins->k, ESI);
 192                                 CMPrd(EDI, ESI);
 193                                 JAb(12);
 194                                 MOVrd(EDI, ECX);
 195                                 SUBrd(ESI, ECX);
 196                                 CMPid(sizeof(int16_t), ECX);
 197                                 JAEb(5);
 198                                 POP(EBX);
 199                                 POP(ESI);
 200                                 POP(EDI);
 201                                 LEAVE_RET();
 202                                 MOVobw(EBX, ESI, AX);
 203                                 SWAP_AX();
 204                                 break;
 205
 206                         case BPF_LD|BPF_B|BPF_ABS:
 207                                 ZEROrd(EAX);
 208                                 MOVid(ins->k, ESI);
 209                                 CMPrd(EDI, ESI);
 210                                 JBb(5);
 211                                 POP(EBX);
 212                                 POP(ESI);
 213                                 POP(EDI);
 214                                 LEAVE_RET();
 215                                 MOVobb(EBX, ESI, AL);
 216                                 break;
 217
 218                         case BPF_LD|BPF_W|BPF_LEN:
 219                                 MOVodd(12, EBP, EAX);
 220                                 break;
 221
 222                         case BPF_LDX|BPF_W|BPF_LEN:
 223                                 MOVodd(12, EBP, EDX);
 224                                 break;
 225
 226                         case BPF_LD|BPF_W|BPF_IND:
 227                                 CMPrd(EDI, EDX);
 228                                 JAb(27);
 229                                 MOVid(ins->k, ESI);
 230                                 MOVrd(EDI, ECX);
 231                                 SUBrd(EDX, ECX);
 232                                 CMPrd(ESI, ECX);
 233                                 JBb(14);
 234                                 ADDrd(EDX, ESI);
 235                                 MOVrd(EDI, ECX);
 236                                 SUBrd(ESI, ECX);
 237                                 CMPid(sizeof(int32_t), ECX);
 238                                 JAEb(7);
 239                                 ZEROrd(EAX);
 240                                 POP(EBX);
 241                                 POP(ESI);
 242                                 POP(EDI);
 243                                 LEAVE_RET();
 244                                 MOVobd(EBX, ESI, EAX);
 245                                 BSWAP(EAX);
 246                                 break;
 247
 248                         case BPF_LD|BPF_H|BPF_IND:
 249                                 ZEROrd(EAX);
 250                                 CMPrd(EDI, EDX);
 251                                 JAb(27);
 252                                 MOVid(ins->k, ESI);
 253                                 MOVrd(EDI, ECX);
 254                                 SUBrd(EDX, ECX);
 255                                 CMPrd(ESI, ECX);
 256                                 JBb(14);
 257                                 ADDrd(EDX, ESI);
 258                                 MOVrd(EDI, ECX);
 259                                 SUBrd(ESI, ECX);
 260                                 CMPid(sizeof(int16_t), ECX);
 261                                 JAEb(5);
 262                                 POP(EBX);
 263                                 POP(ESI);
 264                                 POP(EDI);
 265                                 LEAVE_RET();
 266                                 MOVobw(EBX, ESI, AX);
 267                                 SWAP_AX();
 268                                 break;
 269
 270                         case BPF_LD|BPF_B|BPF_IND:
 271                                 ZEROrd(EAX);
 272                                 CMPrd(EDI, EDX);
 273                                 JAEb(13);
 274                                 MOVid(ins->k, ESI);
 275                                 MOVrd(EDI, ECX);
 276                                 SUBrd(EDX, ECX);
 277                                 CMPrd(ESI, ECX);
 278                                 JAb(5);
 279                                 POP(EBX);
 280                                 POP(ESI);
 281                                 POP(EDI);
 282                                 LEAVE_RET();
 283                                 ADDrd(EDX, ESI);
 284                                 MOVobb(EBX, ESI, AL);
 285                                 break;
 286
 287                         case BPF_LDX|BPF_MSH|BPF_B:
 288                                 MOVid(ins->k, ESI);
 289                                 CMPrd(EDI, ESI);
 290                                 JBb(7);
 291                                 ZEROrd(EAX);
 292                                 POP(EBX);
 293                                 POP(ESI);
 294                                 POP(EDI);
 295                                 LEAVE_RET();
 296                                 ZEROrd(EDX);
 297                                 MOVobb(EBX, ESI, DL);
 298                                 ANDib(0x0f, DL);
 299                                 SHLib(2, EDX);
 300                                 break;
 301
 302                         case BPF_LD|BPF_IMM:
 303                                 MOVid(ins->k, EAX);
 304                                 break;
 305
 306                         case BPF_LDX|BPF_IMM:
 307                                 MOVid(ins->k, EDX);
 308                                 break;
 309
 310                         case BPF_LD|BPF_MEM:
 311                                 MOVid((uintptr_t)mem, ECX);
 312                                 MOVid(ins->k * 4, ESI);
 313                                 MOVobd(ECX, ESI, EAX);
 314                                 break;
 315
 316                         case BPF_LDX|BPF_MEM:
 317                                 MOVid((uintptr_t)mem, ECX);
 318                                 MOVid(ins->k * 4, ESI);
 319                                 MOVobd(ECX, ESI, EDX);
 320                                 break;
 321
 322                         case BPF_ST:
 323                                 /*
 324                                  * XXX this command and the following could
 325                                  * be optimized if the previous instruction
 326                                  * was already of this type
 327                                  */
 328                                 MOVid((uintptr_t)mem, ECX);
 329                                 MOVid(ins->k * 4, ESI);
 330                                 MOVomd(EAX, ECX, ESI);
 331                                 break;
 332
 333                         case BPF_STX:
 334                                 MOVid((uintptr_t)mem, ECX);
 335                                 MOVid(ins->k * 4, ESI);
 336                                 MOVomd(EDX, ECX, ESI);
 337                                 break;
 338
 339                         case BPF_JMP|BPF_JA:
 340                                 JMP(stream.refs[stream.bpf_pc + ins->k] -
 341                                     stream.refs[stream.bpf_pc]);
 342                                 break;
 343
 344                         case BPF_JMP|BPF_JGT|BPF_K:
 345                                 if (ins->jt == 0 && ins->jf == 0)
 346                                         break;
 347                                 CMPid(ins->k, EAX);
 348                                 JCC(JA, JBE);
 349                                 break;
 350
 351                         case BPF_JMP|BPF_JGE|BPF_K:
 352                                 if (ins->jt == 0 && ins->jf == 0)
 353                                         break;
 354                                 CMPid(ins->k, EAX);
 355                                 JCC(JAE, JB);
 356                                 break;
 357
 358                         case BPF_JMP|BPF_JEQ|BPF_K:
 359                                 if (ins->jt == 0 && ins->jf == 0)
 360                                         break;
 361                                 CMPid(ins->k, EAX);
 362                                 JCC(JE, JNE);
 363                                 break;
 364
 365                         case BPF_JMP|BPF_JSET|BPF_K:
 366                                 if (ins->jt == 0 && ins->jf == 0)
 367                                         break;
 368                                 TESTid(ins->k, EAX);
 369                                 JCC(JNE, JE);
 370                                 break;
 371
 372                         case BPF_JMP|BPF_JGT|BPF_X:
 373                                 if (ins->jt == 0 && ins->jf == 0)
 374                                         break;
 375                                 CMPrd(EDX, EAX);
 376                                 JCC(JA, JBE);
 377                                 break;
 378
 379                         case BPF_JMP|BPF_JGE|BPF_X:
 380                                 if (ins->jt == 0 && ins->jf == 0)
 381                                         break;
 382                                 CMPrd(EDX, EAX);
 383                                 JCC(JAE, JB);
 384                                 break;
 385
 386                         case BPF_JMP|BPF_JEQ|BPF_X:
 387                                 if (ins->jt == 0 && ins->jf == 0)
 388                                         break;
 389                                 CMPrd(EDX, EAX);
 390                                 JCC(JE, JNE);
 391                                 break;
 392
 393                         case BPF_JMP|BPF_JSET|BPF_X:
 394                                 if (ins->jt == 0 && ins->jf == 0)
 395                                         break;
 396                                 TESTrd(EDX, EAX);
 397                                 JCC(JNE, JE);
 398                                 break;
 399
 400                         case BPF_ALU|BPF_ADD|BPF_X:
 401                                 ADDrd(EDX, EAX);
 402                                 break;
 403
 404                         case BPF_ALU|BPF_SUB|BPF_X:
 405                                 SUBrd(EDX, EAX);
 406                                 break;
 407
 408                         case BPF_ALU|BPF_MUL|BPF_X:
 409                                 MOVrd(EDX, ECX);
 410                                 MULrd(EDX);
 411                                 MOVrd(ECX, EDX);
 412                                 break;
 413
 414                         case BPF_ALU|BPF_DIV|BPF_X:
 415                                 TESTrd(EDX, EDX);
 416                                 JNEb(7);
 417                                 ZEROrd(EAX);
 418                                 POP(EBX);
 419                                 POP(ESI);
 420                                 POP(EDI);
 421                                 LEAVE_RET();
 422                                 MOVrd(EDX, ECX);
 423                                 ZEROrd(EDX);
 424                                 DIVrd(ECX);
 425                                 MOVrd(ECX, EDX);
 426                                 break;
 427
 428                         case BPF_ALU|BPF_AND|BPF_X:
 429                                 ANDrd(EDX, EAX);
 430                                 break;
 431
 432                         case BPF_ALU|BPF_OR|BPF_X:
 433                                 ORrd(EDX, EAX);
 434                                 break;
 435
 436                         case BPF_ALU|BPF_LSH|BPF_X:
 437                                 MOVrd(EDX, ECX);
 438                                 SHL_CLrb(EAX);
 439                                 break;
 440
 441                         case BPF_ALU|BPF_RSH|BPF_X:
 442                                 MOVrd(EDX, ECX);
 443                                 SHR_CLrb(EAX);
 444                                 break;
 445
 446                         case BPF_ALU|BPF_ADD|BPF_K:
 447                                 ADD_EAXi(ins->k);
 448                                 break;
 449
 450                         case BPF_ALU|BPF_SUB|BPF_K:
 451                                 SUB_EAXi(ins->k);
 452                                 break;
 453
 454                         case BPF_ALU|BPF_MUL|BPF_K:
 455                                 MOVrd(EDX, ECX);
 456                                 MOVid(ins->k, EDX);
 457                                 MULrd(EDX);
 458                                 MOVrd(ECX, EDX);
 459                                 break;
 460
 461                         case BPF_ALU|BPF_DIV|BPF_K:
 462                                 MOVrd(EDX, ECX);
 463                                 ZEROrd(EDX);
 464                                 MOVid(ins->k, ESI);
 465                                 DIVrd(ESI);
 466                                 MOVrd(ECX, EDX);
 467                                 break;
 468
 469                         case BPF_ALU|BPF_AND|BPF_K:
 470                                 ANDid(ins->k, EAX);
 471                                 break;
 472
 473                         case BPF_ALU|BPF_OR|BPF_K:
 474                                 ORid(ins->k, EAX);
 475                                 break;
 476
 477                         case BPF_ALU|BPF_LSH|BPF_K:
 478                                 SHLib((ins->k) & 0xff, EAX);
 479                                 break;
 480
 481                         case BPF_ALU|BPF_RSH|BPF_K:
 482                                 SHRib((ins->k) & 0xff, EAX);
 483                                 break;
 484
 485                         case BPF_ALU|BPF_NEG:
 486                                 NEGd(EAX);
 487                                 break;
 488
 489                         case BPF_MISC|BPF_TAX:
 490                                 MOVrd(EAX, EDX);
 491                                 break;
 492
 493                         case BPF_MISC|BPF_TXA:
 494                                 MOVrd(EDX, EAX);
 495                                 break;
 496                         }
 497                         ins++;
 498                 }
 499
 500                 pass++;
 501                 if (pass == 2)
 502                         break;
 503
 504 #ifdef _KERNEL
 505                 stream.ibuf = (char *)malloc(stream.cur_ip, M_BPFJIT, M_NOWAIT);
 506                 if (stream.ibuf == NULL) {
 507                         free(stream.refs, M_BPFJIT);
 508                         return (NULL);
 509                 }
 510 #else
 511                 stream.ibuf = (char *)malloc(stream.cur_ip);
 512                 if (stream.ibuf == NULL) {
 513                         free(stream.refs);
 514                         return (NULL);
 515                 }
 516 #endif
 517
 518                 /*
 519                  * modify the reference table to contain the offsets and
 520                  * not the lengths of the instructions
 521                  */
 522                 for (i = 1; i < nins + 1; i++)
 523                         stream.refs[i] += stream.refs[i - 1];
 524
 525                 /* Reset the counters */
 526                 stream.cur_ip = 0;
 527                 stream.bpf_pc = 0;
 528
 529                 /* the second pass creates the actual code */
 530                 emitm = emit_code;
 531         }
 532
 533         /*
 534          * the reference table is needed only during compilation,
 535          * now we can free it
 536          */
 537 #ifdef _KERNEL
 538         free(stream.refs, M_BPFJIT);
 539 #else
 540         free(stream.refs);
 541 #endif
 542
 543         return ((bpf_filter_func)stream.ibuf);
 544 }