bpf_jit_machdep.c revision 199619
11590Srgrimes/*- 21590Srgrimes * Copyright (C) 2002-2003 NetGroup, Politecnico di Torino (Italy) 31590Srgrimes * Copyright (C) 2005-2009 Jung-uk Kim <jkim@FreeBSD.org> 41590Srgrimes * All rights reserved. 51590Srgrimes * 61590Srgrimes * Redistribution and use in source and binary forms, with or without 71590Srgrimes * modification, are permitted provided that the following conditions 81590Srgrimes * are met: 91590Srgrimes * 101590Srgrimes * 1. Redistributions of source code must retain the above copyright 111590Srgrimes * notice, this list of conditions and the following disclaimer. 121590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 131590Srgrimes * notice, this list of conditions and the following disclaimer in the 141590Srgrimes * documentation and/or other materials provided with the distribution. 151590Srgrimes * 3. Neither the name of the Politecnico di Torino nor the names of its 161590Srgrimes * contributors may be used to endorse or promote products derived from 171590Srgrimes * this software without specific prior written permission. 181590Srgrimes * 191590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 201590Srgrimes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 211590Srgrimes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 221590Srgrimes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 231590Srgrimes * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 241590Srgrimes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 251590Srgrimes * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 261590Srgrimes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 271590Srgrimes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 281590Srgrimes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 291590Srgrimes * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 301590Srgrimes */ 311590Srgrimes 321590Srgrimes#include <sys/cdefs.h> 331590Srgrimes__FBSDID("$FreeBSD: head/sys/i386/i386/bpf_jit_machdep.c 199619 2009-11-21 00:19:09Z jkim $"); 341590Srgrimes 351590Srgrimes#ifdef _KERNEL 361590Srgrimes#include "opt_bpf.h" 371590Srgrimes#include <sys/param.h> 3853948Sache#include <sys/systm.h> 391590Srgrimes#include <sys/kernel.h> 401590Srgrimes#include <sys/socket.h> 411590Srgrimes#include <sys/malloc.h> 421590Srgrimes#include <net/if.h> 431590Srgrimes#else 441590Srgrimes#include <stdlib.h> 451590Srgrimes#include <string.h> 461590Srgrimes#include <sys/mman.h> 471590Srgrimes#include <sys/param.h> 481590Srgrimes#endif 491590Srgrimes 501590Srgrimes#include <sys/types.h> 511590Srgrimes 521590Srgrimes#include <net/bpf.h> 531590Srgrimes#include <net/bpf_jitter.h> 541590Srgrimes 551590Srgrimes#include <i386/i386/bpf_jit_machdep.h> 561590Srgrimes 571590Srgrimesbpf_filter_func bpf_jit_compile(struct bpf_insn *, u_int, size_t *); 581590Srgrimes 591590Srgrimes/* 601590Srgrimes * Emit routine to update the jump table. 611590Srgrimes */ 6274575Sachestatic void 6374575Sacheemit_length(bpf_bin_stream *stream, __unused u_int value, u_int len) 641590Srgrimes{ 651590Srgrimes 661590Srgrimes if (stream->refs != NULL) 671590Srgrimes (stream->refs)[stream->bpf_pc] += len; 681590Srgrimes stream->cur_ip += len; 691590Srgrimes} 701590Srgrimes 711590Srgrimes/* 721590Srgrimes * Emit routine to output the actual binary code. 731590Srgrimes */ 741590Srgrimesstatic 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_ret) { 184 PUSH(EBP); 185 MOVrd(ESP, EBP); 186 } 187 if (flag_mem) 188 SUBib(BPF_MEMWORDS * sizeof(uint32_t), ESP); 189 if (!flag_ret) { 190 PUSH(EDI); 191 PUSH(ESI); 192 PUSH(EBX); 193 MOVodd(8, EBP, EBX); 194 MOVodd(16, EBP, EDI); 195 } 196 197 for (i = 0; i < nins; i++) { 198 stream.bpf_pc++; 199 200 switch (ins->code) { 201 default: 202#ifdef _KERNEL 203 return (NULL); 204#else 205 abort(); 206#endif 207 208 case BPF_RET|BPF_K: 209 MOVid(ins->k, EAX); 210 if (!flag_ret) { 211 POP(EBX); 212 POP(ESI); 213 POP(EDI); 214 LEAVE(); 215 } 216 RET(); 217 break; 218 219 case BPF_RET|BPF_A: 220 if (!flag_ret) { 221 POP(EBX); 222 POP(ESI); 223 POP(EDI); 224 LEAVE(); 225 } 226 RET(); 227 break; 228 229 case BPF_LD|BPF_W|BPF_ABS: 230 MOVid(ins->k, ESI); 231 CMPrd(EDI, ESI); 232 JAb(12); 233 MOVrd(EDI, ECX); 234 SUBrd(ESI, ECX); 235 CMPid(sizeof(int32_t), ECX); 236 JAEb(7); 237 ZEROrd(EAX); 238 POP(EBX); 239 POP(ESI); 240 POP(EDI); 241 LEAVE(); 242 RET(); 243 MOVobd(EBX, ESI, EAX); 244 BSWAP(EAX); 245 break; 246 247 case BPF_LD|BPF_H|BPF_ABS: 248 ZEROrd(EAX); 249 MOVid(ins->k, ESI); 250 CMPrd(EDI, ESI); 251 JAb(12); 252 MOVrd(EDI, ECX); 253 SUBrd(ESI, ECX); 254 CMPid(sizeof(int16_t), ECX); 255 JAEb(5); 256 POP(EBX); 257 POP(ESI); 258 POP(EDI); 259 LEAVE(); 260 RET(); 261 MOVobw(EBX, ESI, AX); 262 SWAP_AX(); 263 break; 264 265 case BPF_LD|BPF_B|BPF_ABS: 266 ZEROrd(EAX); 267 MOVid(ins->k, ESI); 268 CMPrd(EDI, ESI); 269 JBb(5); 270 POP(EBX); 271 POP(ESI); 272 POP(EDI); 273 LEAVE(); 274 RET(); 275 MOVobb(EBX, ESI, AL); 276 break; 277 278 case BPF_LD|BPF_W|BPF_LEN: 279 MOVodd(12, EBP, EAX); 280 break; 281 282 case BPF_LDX|BPF_W|BPF_LEN: 283 MOVodd(12, EBP, EDX); 284 break; 285 286 case BPF_LD|BPF_W|BPF_IND: 287 CMPrd(EDI, EDX); 288 JAb(27); 289 MOVid(ins->k, ESI); 290 MOVrd(EDI, ECX); 291 SUBrd(EDX, ECX); 292 CMPrd(ESI, ECX); 293 JBb(14); 294 ADDrd(EDX, ESI); 295 MOVrd(EDI, ECX); 296 SUBrd(ESI, ECX); 297 CMPid(sizeof(int32_t), ECX); 298 JAEb(7); 299 ZEROrd(EAX); 300 POP(EBX); 301 POP(ESI); 302 POP(EDI); 303 LEAVE(); 304 RET(); 305 MOVobd(EBX, ESI, EAX); 306 BSWAP(EAX); 307 break; 308 309 case BPF_LD|BPF_H|BPF_IND: 310 ZEROrd(EAX); 311 CMPrd(EDI, EDX); 312 JAb(27); 313 MOVid(ins->k, ESI); 314 MOVrd(EDI, ECX); 315 SUBrd(EDX, ECX); 316 CMPrd(ESI, ECX); 317 JBb(14); 318 ADDrd(EDX, ESI); 319 MOVrd(EDI, ECX); 320 SUBrd(ESI, ECX); 321 CMPid(sizeof(int16_t), ECX); 322 JAEb(5); 323 POP(EBX); 324 POP(ESI); 325 POP(EDI); 326 LEAVE(); 327 RET(); 328 MOVobw(EBX, ESI, AX); 329 SWAP_AX(); 330 break; 331 332 case BPF_LD|BPF_B|BPF_IND: 333 ZEROrd(EAX); 334 CMPrd(EDI, EDX); 335 JAEb(13); 336 MOVid(ins->k, ESI); 337 MOVrd(EDI, ECX); 338 SUBrd(EDX, ECX); 339 CMPrd(ESI, ECX); 340 JAb(5); 341 POP(EBX); 342 POP(ESI); 343 POP(EDI); 344 LEAVE(); 345 RET(); 346 ADDrd(EDX, ESI); 347 MOVobb(EBX, ESI, AL); 348 break; 349 350 case BPF_LDX|BPF_MSH|BPF_B: 351 MOVid(ins->k, ESI); 352 CMPrd(EDI, ESI); 353 JBb(7); 354 ZEROrd(EAX); 355 POP(EBX); 356 POP(ESI); 357 POP(EDI); 358 LEAVE(); 359 RET(); 360 ZEROrd(EDX); 361 MOVobb(EBX, ESI, DL); 362 ANDib(0x0f, DL); 363 SHLib(2, EDX); 364 break; 365 366 case BPF_LD|BPF_IMM: 367 MOVid(ins->k, EAX); 368 break; 369 370 case BPF_LDX|BPF_IMM: 371 MOVid(ins->k, EDX); 372 break; 373 374 case BPF_LD|BPF_MEM: 375 MOVrd(EBP, ECX); 376 MOVid(((int)ins->k - BPF_MEMWORDS) * 377 sizeof(uint32_t), ESI); 378 MOVobd(ECX, ESI, EAX); 379 break; 380 381 case BPF_LDX|BPF_MEM: 382 MOVrd(EBP, ECX); 383 MOVid(((int)ins->k - BPF_MEMWORDS) * 384 sizeof(uint32_t), ESI); 385 MOVobd(ECX, ESI, EDX); 386 break; 387 388 case BPF_ST: 389 /* 390 * XXX this command and the following could 391 * be optimized if the previous instruction 392 * was already of this type 393 */ 394 MOVrd(EBP, ECX); 395 MOVid(((int)ins->k - BPF_MEMWORDS) * 396 sizeof(uint32_t), ESI); 397 MOVomd(EAX, ECX, ESI); 398 break; 399 400 case BPF_STX: 401 MOVrd(EBP, ECX); 402 MOVid(((int)ins->k - BPF_MEMWORDS) * 403 sizeof(uint32_t), ESI); 404 MOVomd(EDX, ECX, ESI); 405 break; 406 407 case BPF_JMP|BPF_JA: 408 JMP(stream.refs[stream.bpf_pc + ins->k] - 409 stream.refs[stream.bpf_pc]); 410 break; 411 412 case BPF_JMP|BPF_JGT|BPF_K: 413 if (ins->jt == 0 && ins->jf == 0) 414 break; 415 CMPid(ins->k, EAX); 416 JCC(JA, JBE); 417 break; 418 419 case BPF_JMP|BPF_JGE|BPF_K: 420 if (ins->jt == 0 && ins->jf == 0) 421 break; 422 CMPid(ins->k, EAX); 423 JCC(JAE, JB); 424 break; 425 426 case BPF_JMP|BPF_JEQ|BPF_K: 427 if (ins->jt == 0 && ins->jf == 0) 428 break; 429 CMPid(ins->k, EAX); 430 JCC(JE, JNE); 431 break; 432 433 case BPF_JMP|BPF_JSET|BPF_K: 434 if (ins->jt == 0 && ins->jf == 0) 435 break; 436 TESTid(ins->k, EAX); 437 JCC(JNE, JE); 438 break; 439 440 case BPF_JMP|BPF_JGT|BPF_X: 441 if (ins->jt == 0 && ins->jf == 0) 442 break; 443 CMPrd(EDX, EAX); 444 JCC(JA, JBE); 445 break; 446 447 case BPF_JMP|BPF_JGE|BPF_X: 448 if (ins->jt == 0 && ins->jf == 0) 449 break; 450 CMPrd(EDX, EAX); 451 JCC(JAE, JB); 452 break; 453 454 case BPF_JMP|BPF_JEQ|BPF_X: 455 if (ins->jt == 0 && ins->jf == 0) 456 break; 457 CMPrd(EDX, EAX); 458 JCC(JE, JNE); 459 break; 460 461 case BPF_JMP|BPF_JSET|BPF_X: 462 if (ins->jt == 0 && ins->jf == 0) 463 break; 464 TESTrd(EDX, EAX); 465 JCC(JNE, JE); 466 break; 467 468 case BPF_ALU|BPF_ADD|BPF_X: 469 ADDrd(EDX, EAX); 470 break; 471 472 case BPF_ALU|BPF_SUB|BPF_X: 473 SUBrd(EDX, EAX); 474 break; 475 476 case BPF_ALU|BPF_MUL|BPF_X: 477 MOVrd(EDX, ECX); 478 MULrd(EDX); 479 MOVrd(ECX, EDX); 480 break; 481 482 case BPF_ALU|BPF_DIV|BPF_X: 483 TESTrd(EDX, EDX); 484 JNEb(7); 485 ZEROrd(EAX); 486 POP(EBX); 487 POP(ESI); 488 POP(EDI); 489 LEAVE(); 490 RET(); 491 MOVrd(EDX, ECX); 492 ZEROrd(EDX); 493 DIVrd(ECX); 494 MOVrd(ECX, EDX); 495 break; 496 497 case BPF_ALU|BPF_AND|BPF_X: 498 ANDrd(EDX, EAX); 499 break; 500 501 case BPF_ALU|BPF_OR|BPF_X: 502 ORrd(EDX, EAX); 503 break; 504 505 case BPF_ALU|BPF_LSH|BPF_X: 506 MOVrd(EDX, ECX); 507 SHL_CLrb(EAX); 508 break; 509 510 case BPF_ALU|BPF_RSH|BPF_X: 511 MOVrd(EDX, ECX); 512 SHR_CLrb(EAX); 513 break; 514 515 case BPF_ALU|BPF_ADD|BPF_K: 516 ADD_EAXi(ins->k); 517 break; 518 519 case BPF_ALU|BPF_SUB|BPF_K: 520 SUB_EAXi(ins->k); 521 break; 522 523 case BPF_ALU|BPF_MUL|BPF_K: 524 MOVrd(EDX, ECX); 525 MOVid(ins->k, EDX); 526 MULrd(EDX); 527 MOVrd(ECX, EDX); 528 break; 529 530 case BPF_ALU|BPF_DIV|BPF_K: 531 MOVrd(EDX, ECX); 532 ZEROrd(EDX); 533 MOVid(ins->k, ESI); 534 DIVrd(ESI); 535 MOVrd(ECX, EDX); 536 break; 537 538 case BPF_ALU|BPF_AND|BPF_K: 539 ANDid(ins->k, EAX); 540 break; 541 542 case BPF_ALU|BPF_OR|BPF_K: 543 ORid(ins->k, EAX); 544 break; 545 546 case BPF_ALU|BPF_LSH|BPF_K: 547 SHLib((ins->k) & 0xff, EAX); 548 break; 549 550 case BPF_ALU|BPF_RSH|BPF_K: 551 SHRib((ins->k) & 0xff, EAX); 552 break; 553 554 case BPF_ALU|BPF_NEG: 555 NEGd(EAX); 556 break; 557 558 case BPF_MISC|BPF_TAX: 559 MOVrd(EAX, EDX); 560 break; 561 562 case BPF_MISC|BPF_TXA: 563 MOVrd(EDX, EAX); 564 break; 565 } 566 ins++; 567 } 568 569 if (pass > 0) 570 continue; 571 572 *size = stream.cur_ip; 573#ifdef _KERNEL 574 stream.ibuf = malloc(*size, M_BPFJIT, M_NOWAIT); 575 if (stream.ibuf == NULL) 576 break; 577#else 578 stream.ibuf = mmap(NULL, *size, PROT_READ | PROT_WRITE, 579 MAP_ANON, -1, 0); 580 if (stream.ibuf == MAP_FAILED) { 581 stream.ibuf = NULL; 582 break; 583 } 584#endif 585 586 /* 587 * Modify the reference table to contain the offsets and 588 * not the lengths of the instructions. 589 */ 590 if (flag_jmp) 591 for (i = 1; i < nins + 1; i++) 592 stream.refs[i] += stream.refs[i - 1]; 593 594 /* Reset the counters. */ 595 stream.cur_ip = 0; 596 stream.bpf_pc = 0; 597 598 /* The second pass creates the actual code. */ 599 emitm = emit_code; 600 } 601 602 /* 603 * The reference table is needed only during compilation, 604 * now we can free it. 605 */ 606 if (flag_jmp) 607#ifdef _KERNEL 608 free(stream.refs, M_BPFJIT); 609#else 610 free(stream.refs); 611#endif 612 613#ifndef _KERNEL 614 if (stream.ibuf != NULL && 615 mprotect(stream.ibuf, *size, PROT_READ | PROT_EXEC) != 0) { 616 munmap(stream.ibuf, *size); 617 stream.ibuf = NULL; 618 } 619#endif 620 621 return ((bpf_filter_func)stream.ibuf); 622} 623