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 <net/if.h> 43#else 44#include <stdlib.h> 45#include <string.h> 46#include <sys/mman.h> 47#include <sys/param.h> 48#endif 49 50#include <sys/types.h> 51 52#include <net/bpf.h> 53#include <net/bpf_jitter.h> 54 55#include <amd64/amd64/bpf_jit_machdep.h> 56 57bpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *); 58 59/* 60 * Emit routine to update the jump table. 61 */ 62static void 63emit_length(bpf_bin_stream *stream, __unused u_int value, u_int len) 64{ 65 66 if (stream->refs != NULL) 67 (stream->refs)[stream->bpf_pc] += len; 68 stream->cur_ip += len; 69} 70 71/* 72 * Emit routine to output the actual binary code. 73 */ 74static void 75emit_code(bpf_bin_stream *stream, u_int value, u_int len) 76{ 77 78 switch (len) { 79 case 1: 80 stream->ibuf[stream->cur_ip] = (u_char)value; 81 stream->cur_ip++; 82 break; 83 84 case 2: 85 *((u_short *)(stream->ibuf + stream->cur_ip)) = (u_short)value; 86 stream->cur_ip += 2; 87 break; 88 89 case 4: 90 *((u_int *)(stream->ibuf + stream->cur_ip)) = value; 91 stream->cur_ip += 4; 92 break; 93 } 94 95 return; 96} 97 98/* 99 * Scan the filter program and find possible optimization. 100 */ 101static int 102bpf_jit_optimize(struct bpf_insn *prog, u_int nins) 103{ 104 int flags; 105 u_int i; 106 107 /* Do we return immediately? */ 108 if (BPF_CLASS(prog[0].code) == BPF_RET) 109 return (BPF_JIT_FRET); 110 111 for (flags = 0, i = 0; i < nins; i++) { 112 switch (prog[i].code) { 113 case BPF_LD|BPF_W|BPF_ABS: 114 case BPF_LD|BPF_H|BPF_ABS: 115 case BPF_LD|BPF_B|BPF_ABS: 116 case BPF_LD|BPF_W|BPF_IND: 117 case BPF_LD|BPF_H|BPF_IND: 118 case BPF_LD|BPF_B|BPF_IND: 119 case BPF_LDX|BPF_MSH|BPF_B: 120 flags |= BPF_JIT_FPKT; 121 break; 122 case BPF_LD|BPF_MEM: 123 case BPF_LDX|BPF_MEM: 124 case BPF_ST: 125 case BPF_STX: 126 flags |= BPF_JIT_FMEM; 127 break; 128 case BPF_LD|BPF_W|BPF_LEN: 129 case BPF_LDX|BPF_W|BPF_LEN: 130 flags |= BPF_JIT_FLEN; 131 break; 132 case BPF_JMP|BPF_JA: 133 case BPF_JMP|BPF_JGT|BPF_K: 134 case BPF_JMP|BPF_JGE|BPF_K: 135 case BPF_JMP|BPF_JEQ|BPF_K: 136 case BPF_JMP|BPF_JSET|BPF_K: 137 case BPF_JMP|BPF_JGT|BPF_X: 138 case BPF_JMP|BPF_JGE|BPF_X: 139 case BPF_JMP|BPF_JEQ|BPF_X: 140 case BPF_JMP|BPF_JSET|BPF_X: 141 flags |= BPF_JIT_FJMP; 142 break; 143 } 144 if (flags == BPF_JIT_FLAG_ALL) 145 break; 146 } 147 148 return (flags); 149} 150 151/* 152 * Function that does the real stuff. 153 */ 154bpf_filter_func 155bpf_jit_compile(struct bpf_insn *prog, u_int nins, size_t *size) 156{ 157 bpf_bin_stream stream; 158 struct bpf_insn *ins; 159 int flags, fret, fpkt, fmem, fjmp, flen; 160 u_int i, pass; 161 162 /* 163 * NOTE: Do not modify the name of this variable, as it's used by 164 * the macros to emit code. 165 */ 166 emit_func emitm; 167 168 flags = bpf_jit_optimize(prog, nins); 169 fret = (flags & BPF_JIT_FRET) != 0; 170 fpkt = (flags & BPF_JIT_FPKT) != 0; 171 fmem = (flags & BPF_JIT_FMEM) != 0; 172 fjmp = (flags & BPF_JIT_FJMP) != 0; 173 flen = (flags & BPF_JIT_FLEN) != 0; 174 175 if (fret) 176 nins = 1; 177 178 memset(&stream, 0, sizeof(stream)); 179 180 /* Allocate the reference table for the jumps. */ 181 if (fjmp) { 182#ifdef _KERNEL 183 stream.refs = malloc((nins + 1) * sizeof(u_int), M_BPFJIT, 184 M_NOWAIT | M_ZERO); 185#else 186 stream.refs = calloc(nins + 1, sizeof(u_int)); 187#endif 188 if (stream.refs == NULL) 189 return (NULL); 190 } 191 192 /* 193 * The first pass will emit the lengths of the instructions 194 * to create the reference table. 195 */ 196 emitm = emit_length; 197 198 for (pass = 0; pass < 2; pass++) { 199 ins = prog; 200 201 /* Create the procedure header. */ 202 if (fmem) { 203 PUSH(RBP); 204 MOVrq(RSP, RBP); 205 SUBib(BPF_MEMWORDS * sizeof(uint32_t), RSP); 206 } 207 if (flen) 208 MOVrd2(ESI, R9D); 209 if (fpkt) { 210 MOVrq2(RDI, R8); 211 MOVrd(EDX, EDI); 212 } 213 214 for (i = 0; i < nins; i++) { 215 stream.bpf_pc++; 216 217 switch (ins->code) { 218 default: 219#ifdef _KERNEL 220 return (NULL); 221#else 222 abort(); 223#endif 224 225 case BPF_RET|BPF_K: 226 MOVid(ins->k, EAX); 227 if (fmem) 228 LEAVE(); 229 RET(); 230 break; 231 232 case BPF_RET|BPF_A: 233 if (fmem) 234 LEAVE(); 235 RET(); 236 break; 237 238 case BPF_LD|BPF_W|BPF_ABS: 239 MOVid(ins->k, ESI); 240 CMPrd(EDI, ESI); 241 JAb(12); 242 MOVrd(EDI, ECX); 243 SUBrd(ESI, ECX); 244 CMPid(sizeof(int32_t), ECX); 245 if (fmem) { 246 JAEb(4); 247 ZEROrd(EAX); 248 LEAVE(); 249 } else { 250 JAEb(3); 251 ZEROrd(EAX); 252 } 253 RET(); 254 MOVrq3(R8, RCX); 255 MOVobd(RCX, RSI, EAX); 256 BSWAP(EAX); 257 break; 258 259 case BPF_LD|BPF_H|BPF_ABS: 260 ZEROrd(EAX); 261 MOVid(ins->k, ESI); 262 CMPrd(EDI, ESI); 263 JAb(12); 264 MOVrd(EDI, ECX); 265 SUBrd(ESI, ECX); 266 CMPid(sizeof(int16_t), ECX); 267 if (fmem) { 268 JAEb(2); 269 LEAVE(); 270 } else 271 JAEb(1); 272 RET(); 273 MOVrq3(R8, RCX); 274 MOVobw(RCX, RSI, AX); 275 SWAP_AX(); 276 break; 277 278 case BPF_LD|BPF_B|BPF_ABS: 279 ZEROrd(EAX); 280 MOVid(ins->k, ESI); 281 CMPrd(EDI, ESI); 282 if (fmem) { 283 JBb(2); 284 LEAVE(); 285 } else 286 JBb(1); 287 RET(); 288 MOVrq3(R8, RCX); 289 MOVobb(RCX, RSI, AL); 290 break; 291 292 case BPF_LD|BPF_W|BPF_LEN: 293 MOVrd3(R9D, EAX); 294 break; 295 296 case BPF_LDX|BPF_W|BPF_LEN: 297 MOVrd3(R9D, EDX); 298 break; 299 300 case BPF_LD|BPF_W|BPF_IND: 301 CMPrd(EDI, EDX); 302 JAb(27); 303 MOVid(ins->k, ESI); 304 MOVrd(EDI, ECX); 305 SUBrd(EDX, ECX); 306 CMPrd(ESI, ECX); 307 JBb(14); 308 ADDrd(EDX, ESI); 309 MOVrd(EDI, ECX); 310 SUBrd(ESI, ECX); 311 CMPid(sizeof(int32_t), ECX); 312 if (fmem) { 313 JAEb(4); 314 ZEROrd(EAX); 315 LEAVE(); 316 } else { 317 JAEb(3); 318 ZEROrd(EAX); 319 } 320 RET(); 321 MOVrq3(R8, RCX); 322 MOVobd(RCX, RSI, EAX); 323 BSWAP(EAX); 324 break; 325 326 case BPF_LD|BPF_H|BPF_IND: 327 ZEROrd(EAX); 328 CMPrd(EDI, EDX); 329 JAb(27); 330 MOVid(ins->k, ESI); 331 MOVrd(EDI, ECX); 332 SUBrd(EDX, ECX); 333 CMPrd(ESI, ECX); 334 JBb(14); 335 ADDrd(EDX, ESI); 336 MOVrd(EDI, ECX); 337 SUBrd(ESI, ECX); 338 CMPid(sizeof(int16_t), ECX); 339 if (fmem) { 340 JAEb(2); 341 LEAVE(); 342 } else 343 JAEb(1); 344 RET(); 345 MOVrq3(R8, RCX); 346 MOVobw(RCX, RSI, AX); 347 SWAP_AX(); 348 break; 349 350 case BPF_LD|BPF_B|BPF_IND: 351 ZEROrd(EAX); 352 CMPrd(EDI, EDX); 353 JAEb(13); 354 MOVid(ins->k, ESI); 355 MOVrd(EDI, ECX); 356 SUBrd(EDX, ECX); 357 CMPrd(ESI, ECX); 358 if (fmem) { 359 JAb(2); 360 LEAVE(); 361 } else 362 JAb(1); 363 RET(); 364 MOVrq3(R8, RCX); 365 ADDrd(EDX, ESI); 366 MOVobb(RCX, RSI, AL); 367 break; 368 369 case BPF_LDX|BPF_MSH|BPF_B: 370 MOVid(ins->k, ESI); 371 CMPrd(EDI, ESI); 372 if (fmem) { 373 JBb(4); 374 ZEROrd(EAX); 375 LEAVE(); 376 } else { 377 JBb(3); 378 ZEROrd(EAX); 379 } 380 RET(); 381 ZEROrd(EDX); 382 MOVrq3(R8, RCX); 383 MOVobb(RCX, RSI, DL); 384 ANDib(0x0f, DL); 385 SHLib(2, EDX); 386 break; 387 388 case BPF_LD|BPF_IMM: 389 MOVid(ins->k, EAX); 390 break; 391 392 case BPF_LDX|BPF_IMM: 393 MOVid(ins->k, EDX); 394 break; 395 396 case BPF_LD|BPF_MEM: 397 MOVid(ins->k * sizeof(uint32_t), ESI); 398 MOVobd(RSP, RSI, EAX); 399 break; 400 401 case BPF_LDX|BPF_MEM: 402 MOVid(ins->k * sizeof(uint32_t), ESI); 403 MOVobd(RSP, RSI, EDX); 404 break; 405 406 case BPF_ST: 407 /* 408 * XXX this command and the following could 409 * be optimized if the previous instruction 410 * was already of this type 411 */ 412 MOVid(ins->k * sizeof(uint32_t), ESI); 413 MOVomd(EAX, RSP, RSI); 414 break; 415 416 case BPF_STX: 417 MOVid(ins->k * sizeof(uint32_t), ESI); 418 MOVomd(EDX, RSP, RSI); 419 break; 420 421 case BPF_JMP|BPF_JA: 422 JUMP(ins->k); 423 break; 424 425 case BPF_JMP|BPF_JGT|BPF_K: 426 if (ins->jt == ins->jf) { 427 JUMP(ins->jt); 428 break; 429 } 430 CMPid(ins->k, EAX); 431 JCC(JA, JBE); 432 break; 433 434 case BPF_JMP|BPF_JGE|BPF_K: 435 if (ins->jt == ins->jf) { 436 JUMP(ins->jt); 437 break; 438 } 439 CMPid(ins->k, EAX); 440 JCC(JAE, JB); 441 break; 442 443 case BPF_JMP|BPF_JEQ|BPF_K: 444 if (ins->jt == ins->jf) { 445 JUMP(ins->jt); 446 break; 447 } 448 CMPid(ins->k, EAX); 449 JCC(JE, JNE); 450 break; 451 452 case BPF_JMP|BPF_JSET|BPF_K: 453 if (ins->jt == ins->jf) { 454 JUMP(ins->jt); 455 break; 456 } 457 TESTid(ins->k, EAX); 458 JCC(JNE, JE); 459 break; 460 461 case BPF_JMP|BPF_JGT|BPF_X: 462 if (ins->jt == ins->jf) { 463 JUMP(ins->jt); 464 break; 465 } 466 CMPrd(EDX, EAX); 467 JCC(JA, JBE); 468 break; 469 470 case BPF_JMP|BPF_JGE|BPF_X: 471 if (ins->jt == ins->jf) { 472 JUMP(ins->jt); 473 break; 474 } 475 CMPrd(EDX, EAX); 476 JCC(JAE, JB); 477 break; 478 479 case BPF_JMP|BPF_JEQ|BPF_X: 480 if (ins->jt == ins->jf) { 481 JUMP(ins->jt); 482 break; 483 } 484 CMPrd(EDX, EAX); 485 JCC(JE, JNE); 486 break; 487 488 case BPF_JMP|BPF_JSET|BPF_X: 489 if (ins->jt == ins->jf) { 490 JUMP(ins->jt); 491 break; 492 } 493 TESTrd(EDX, EAX); 494 JCC(JNE, JE); 495 break; 496 497 case BPF_ALU|BPF_ADD|BPF_X: 498 ADDrd(EDX, EAX); 499 break; 500 501 case BPF_ALU|BPF_SUB|BPF_X: 502 SUBrd(EDX, EAX); 503 break; 504 505 case BPF_ALU|BPF_MUL|BPF_X: 506 MOVrd(EDX, ECX); 507 MULrd(EDX); 508 MOVrd(ECX, EDX); 509 break; 510 511 case BPF_ALU|BPF_DIV|BPF_X: 512 TESTrd(EDX, EDX); 513 if (fmem) { 514 JNEb(4); 515 ZEROrd(EAX); 516 LEAVE(); 517 } else { 518 JNEb(3); 519 ZEROrd(EAX); 520 } 521 RET(); 522 MOVrd(EDX, ECX); 523 ZEROrd(EDX); 524 DIVrd(ECX); 525 MOVrd(ECX, EDX); 526 break; 527 528 case BPF_ALU|BPF_AND|BPF_X: 529 ANDrd(EDX, EAX); 530 break; 531 532 case BPF_ALU|BPF_OR|BPF_X: 533 ORrd(EDX, EAX); 534 break; 535 536 case BPF_ALU|BPF_LSH|BPF_X: 537 MOVrd(EDX, ECX); 538 SHL_CLrb(EAX); 539 break; 540 541 case BPF_ALU|BPF_RSH|BPF_X: 542 MOVrd(EDX, ECX); 543 SHR_CLrb(EAX); 544 break; 545 546 case BPF_ALU|BPF_ADD|BPF_K: 547 ADD_EAXi(ins->k); 548 break; 549 550 case BPF_ALU|BPF_SUB|BPF_K: 551 SUB_EAXi(ins->k); 552 break; 553 554 case BPF_ALU|BPF_MUL|BPF_K: 555 MOVrd(EDX, ECX); 556 MOVid(ins->k, EDX); 557 MULrd(EDX); 558 MOVrd(ECX, EDX); 559 break; 560 561 case BPF_ALU|BPF_DIV|BPF_K: 562 MOVrd(EDX, ECX); 563 ZEROrd(EDX); 564 MOVid(ins->k, ESI); 565 DIVrd(ESI); 566 MOVrd(ECX, EDX); 567 break; 568 569 case BPF_ALU|BPF_AND|BPF_K: 570 ANDid(ins->k, EAX); 571 break; 572 573 case BPF_ALU|BPF_OR|BPF_K: 574 ORid(ins->k, EAX); 575 break; 576 577 case BPF_ALU|BPF_LSH|BPF_K: 578 SHLib((ins->k) & 0xff, EAX); 579 break; 580 581 case BPF_ALU|BPF_RSH|BPF_K: 582 SHRib((ins->k) & 0xff, EAX); 583 break; 584 585 case BPF_ALU|BPF_NEG: 586 NEGd(EAX); 587 break; 588 589 case BPF_MISC|BPF_TAX: 590 MOVrd(EAX, EDX); 591 break; 592 593 case BPF_MISC|BPF_TXA: 594 MOVrd(EDX, EAX); 595 break; 596 } 597 ins++; 598 } 599 600 if (pass > 0) 601 continue; 602 603 *size = stream.cur_ip; 604#ifdef _KERNEL 605 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT); 606 if (stream.ibuf == NULL) 607 break; 608#else 609 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE, 610 MAP_ANON, -1, 0); 611 if (stream.ibuf == MAP_FAILED) { 612 stream.ibuf = NULL; 613 break; 614 } 615#endif 616 617 /* 618 * Modify the reference table to contain the offsets and 619 * not the lengths of the instructions. 620 */ 621 if (fjmp) 622 for (i = 1; i < nins + 1; i++) 623 stream.refs[i] += stream.refs[i - 1]; 624 625 /* Reset the counters. */ 626 stream.cur_ip = 0; 627 stream.bpf_pc = 0; 628 629 /* The second pass creates the actual code. */ 630 emitm = emit_code; 631 } 632 633 /* 634 * The reference table is needed only during compilation, 635 * now we can free it. 636 */ 637 if (fjmp) 638#ifdef _KERNEL 639 free(stream.refs, M_BPFJIT); 640#else 641 free(stream.refs); 642#endif 643 644#ifndef _KERNEL 645 if (stream.ibuf != NULL && 646 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) { 647 munmap(stream.ibuf, *size); 648 stream.ibuf = NULL; 649 } 650#endif 651 652 return ((bpf_filter_func)stream.ibuf); 653} 654