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