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