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