1 /*- 2 * Copyright (c) 2011-2012 Alexander Nasonov. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in 13 * the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 20 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 #include <net/bpfjit.h> 31 32 #ifndef _KERNEL 33 #include <assert.h> 34 #define BPFJIT_ASSERT(c) assert(c) 35 #else 36 #define BPFJIT_ASSERT(c) KASSERT(c) 37 #endif 38 39 #ifndef _KERNEL 40 #include <stdlib.h> 41 #define BPFJIT_MALLOC(sz) malloc(sz) 42 #define BPFJIT_FREE(p) free(p) 43 #else 44 #include <sys/malloc.h> 45 #define BPFJIT_MALLOC(sz) kern_malloc(sz, M_WAITOK) 46 #define BPFJIT_FREE(p) kern_free(p) 47 #endif 48 49 #ifndef _KERNEL 50 #include <limits.h> 51 #include <stdbool.h> 52 #include <stddef.h> 53 #include <stdint.h> 54 #else 55 #include <machine/limits.h> 56 #include <sys/null.h> 57 #include <sys/types.h> 58 #include <sys/atomic.h> 59 #include <sys/module.h> 60 #endif 61 62 #include <sys/queue.h> 63 #include <sys/types.h> 64 65 #include <sljitLir.h> 66 67 #if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE 68 #include <stdio.h> /* for stderr */ 69 #endif 70 71 72 #define BPFJIT_A SLJIT_TEMPORARY_REG1 73 #define BPFJIT_X SLJIT_TEMPORARY_EREG1 74 #define BPFJIT_TMP1 SLJIT_TEMPORARY_REG2 75 #define BPFJIT_TMP2 SLJIT_TEMPORARY_REG3 76 #define BPFJIT_BUF SLJIT_SAVED_REG1 77 #define BPFJIT_WIRELEN SLJIT_SAVED_REG2 78 #define BPFJIT_BUFLEN SLJIT_SAVED_REG3 79 #define BPFJIT_KERN_TMP SLJIT_TEMPORARY_EREG2 80 81 /* 82 * Flags for bpfjit_optimization_hints(). 83 */ 84 #define BPFJIT_INIT_X 0x10000 85 #define BPFJIT_INIT_A 0x20000 86 87 88 /* 89 * Node of bj_jumps list. 90 */ 91 struct bpfjit_jump 92 { 93 struct sljit_jump *bj_jump; 94 SLIST_ENTRY(bpfjit_jump) bj_entries; 95 uint32_t bj_safe_length; 96 }; 97 98 /* 99 * Data for BPF_JMP instruction. 100 */ 101 struct bpfjit_jump_data 102 { 103 /* 104 * These entries make up bj_jumps list: 105 * bj_jtf[0] - when coming from jt path, 106 * bj_jtf[1] - when coming from jf path. 107 */ 108 struct bpfjit_jump bj_jtf[2]; 109 }; 110 111 /* 112 * Data for "read from packet" instructions. 113 * See also read_pkt_insn() function below. 114 */ 115 struct bpfjit_read_pkt_data 116 { 117 /* 118 * If positive, emit "if (buflen < bj_check_length) return 0". 119 * We assume that buflen is never equal to UINT32_MAX (otherwise, 120 * we need a special bool variable to emit unconditional "return 0"). 121 */ 122 uint32_t bj_check_length; 123 }; 124 125 /* 126 * Additional (optimization-related) data for bpf_insn. 127 */ 128 struct bpfjit_insn_data 129 { 130 /* List of jumps to this insn. */ 131 SLIST_HEAD(, bpfjit_jump) bj_jumps; 132 133 union { 134 struct bpfjit_jump_data bj_jdata; 135 struct bpfjit_read_pkt_data bj_rdata; 136 } bj_aux; 137 138 bool bj_unreachable; 139 }; 140 141 #ifdef _KERNEL 142 143 uint32_t m_xword(const struct mbuf *, uint32_t, int *); 144 uint32_t m_xhalf(const struct mbuf *, uint32_t, int *); 145 uint32_t m_xbyte(const struct mbuf *, uint32_t, int *); 146 147 MODULE(MODULE_CLASS_MISC, bpfjit, "sljit") 148 149 static int 150 bpfjit_modcmd(modcmd_t cmd, void *arg) 151 { 152 153 switch (cmd) { 154 case MODULE_CMD_INIT: 155 bpfjit_module_ops.bj_free_code = &bpfjit_free_code; 156 membar_producer(); 157 bpfjit_module_ops.bj_generate_code = &bpfjit_generate_code; 158 membar_producer(); 159 return 0; 160 161 case MODULE_CMD_FINI: 162 return EOPNOTSUPP; 163 164 default: 165 return ENOTTY; 166 } 167 } 168 #endif 169 170 static uint32_t 171 read_width(struct bpf_insn *pc) 172 { 173 174 switch (BPF_SIZE(pc->code)) { 175 case BPF_W: 176 return 4; 177 case BPF_H: 178 return 2; 179 case BPF_B: 180 return 1; 181 default: 182 BPFJIT_ASSERT(false); 183 return 0; 184 } 185 } 186 187 /* 188 * Get offset of M[k] on the stack. 189 */ 190 static int 191 mem_local_offset(uint32_t k, int minm) 192 { 193 int moff = (k - minm) * sizeof(uint32_t); 194 195 #ifdef _KERNEL 196 /* 197 * 4 bytes for the third argument of m_xword/m_xhalf/m_xbyte. 198 */ 199 return sizeof(uint32_t) + moff; 200 #else 201 return moff; 202 #endif 203 } 204 205 /* 206 * Generate code for BPF_LD+BPF_B+BPF_ABS A <- P[k:1]. 207 */ 208 static int 209 emit_read8(struct sljit_compiler* compiler, uint32_t k) 210 { 211 212 return sljit_emit_op1(compiler, 213 SLJIT_MOV_UB, 214 BPFJIT_A, 0, 215 SLJIT_MEM1(BPFJIT_BUF), k); 216 } 217 218 /* 219 * Generate code for BPF_LD+BPF_H+BPF_ABS A <- P[k:2]. 220 */ 221 static int 222 emit_read16(struct sljit_compiler* compiler, uint32_t k) 223 { 224 int status; 225 226 /* tmp1 = buf[k]; */ 227 status = sljit_emit_op1(compiler, 228 SLJIT_MOV_UB, 229 BPFJIT_TMP1, 0, 230 SLJIT_MEM1(BPFJIT_BUF), k); 231 if (status != SLJIT_SUCCESS) 232 return status; 233 234 /* A = buf[k+1]; */ 235 status = sljit_emit_op1(compiler, 236 SLJIT_MOV_UB, 237 BPFJIT_A, 0, 238 SLJIT_MEM1(BPFJIT_BUF), k+1); 239 if (status != SLJIT_SUCCESS) 240 return status; 241 242 /* tmp1 = tmp1 << 8; */ 243 status = sljit_emit_op2(compiler, 244 SLJIT_SHL, 245 BPFJIT_TMP1, 0, 246 BPFJIT_TMP1, 0, 247 SLJIT_IMM, 8); 248 if (status != SLJIT_SUCCESS) 249 return status; 250 251 /* A = A + tmp1; */ 252 status = sljit_emit_op2(compiler, 253 SLJIT_ADD, 254 BPFJIT_A, 0, 255 BPFJIT_A, 0, 256 BPFJIT_TMP1, 0); 257 return status; 258 } 259 260 /* 261 * Generate code for BPF_LD+BPF_W+BPF_ABS A <- P[k:4]. 262 */ 263 static int 264 emit_read32(struct sljit_compiler* compiler, uint32_t k) 265 { 266 int status; 267 268 /* tmp1 = buf[k]; */ 269 status = sljit_emit_op1(compiler, 270 SLJIT_MOV_UB, 271 BPFJIT_TMP1, 0, 272 SLJIT_MEM1(BPFJIT_BUF), k); 273 if (status != SLJIT_SUCCESS) 274 return status; 275 276 /* tmp2 = buf[k+1]; */ 277 status = sljit_emit_op1(compiler, 278 SLJIT_MOV_UB, 279 BPFJIT_TMP2, 0, 280 SLJIT_MEM1(BPFJIT_BUF), k+1); 281 if (status != SLJIT_SUCCESS) 282 return status; 283 284 /* A = buf[k+3]; */ 285 status = sljit_emit_op1(compiler, 286 SLJIT_MOV_UB, 287 BPFJIT_A, 0, 288 SLJIT_MEM1(BPFJIT_BUF), k+3); 289 if (status != SLJIT_SUCCESS) 290 return status; 291 292 /* tmp1 = tmp1 << 24; */ 293 status = sljit_emit_op2(compiler, 294 SLJIT_SHL, 295 BPFJIT_TMP1, 0, 296 BPFJIT_TMP1, 0, 297 SLJIT_IMM, 24); 298 if (status != SLJIT_SUCCESS) 299 return status; 300 301 /* A = A + tmp1; */ 302 status = sljit_emit_op2(compiler, 303 SLJIT_ADD, 304 BPFJIT_A, 0, 305 BPFJIT_A, 0, 306 BPFJIT_TMP1, 0); 307 if (status != SLJIT_SUCCESS) 308 return status; 309 310 /* tmp1 = buf[k+2]; */ 311 status = sljit_emit_op1(compiler, 312 SLJIT_MOV_UB, 313 BPFJIT_TMP1, 0, 314 SLJIT_MEM1(BPFJIT_BUF), k+2); 315 if (status != SLJIT_SUCCESS) 316 return status; 317 318 /* tmp2 = tmp2 << 16; */ 319 status = sljit_emit_op2(compiler, 320 SLJIT_SHL, 321 BPFJIT_TMP2, 0, 322 BPFJIT_TMP2, 0, 323 SLJIT_IMM, 16); 324 if (status != SLJIT_SUCCESS) 325 return status; 326 327 /* A = A + tmp2; */ 328 status = sljit_emit_op2(compiler, 329 SLJIT_ADD, 330 BPFJIT_A, 0, 331 BPFJIT_A, 0, 332 BPFJIT_TMP2, 0); 333 if (status != SLJIT_SUCCESS) 334 return status; 335 336 /* tmp1 = tmp1 << 8; */ 337 status = sljit_emit_op2(compiler, 338 SLJIT_SHL, 339 BPFJIT_TMP1, 0, 340 BPFJIT_TMP1, 0, 341 SLJIT_IMM, 8); 342 if (status != SLJIT_SUCCESS) 343 return status; 344 345 /* A = A + tmp1; */ 346 status = sljit_emit_op2(compiler, 347 SLJIT_ADD, 348 BPFJIT_A, 0, 349 BPFJIT_A, 0, 350 BPFJIT_TMP1, 0); 351 return status; 352 } 353 354 #ifdef _KERNEL 355 /* 356 * Generate m_xword/m_xhalf/m_xbyte call. 357 * 358 * pc is one of: 359 * BPF_LD+BPF_W+BPF_ABS A <- P[k:4] 360 * BPF_LD+BPF_H+BPF_ABS A <- P[k:2] 361 * BPF_LD+BPF_B+BPF_ABS A <- P[k:1] 362 * BPF_LD+BPF_W+BPF_IND A <- P[X+k:4] 363 * BPF_LD+BPF_H+BPF_IND A <- P[X+k:2] 364 * BPF_LD+BPF_B+BPF_IND A <- P[X+k:1] 365 * BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) 366 * 367 * dst must be BPFJIT_A for BPF_LD instructions and BPFJIT_X 368 * or any of BPFJIT_TMP* registrers for BPF_MSH instruction. 369 */ 370 static int 371 emit_xcall(struct sljit_compiler* compiler, struct bpf_insn *pc, 372 int dst, sljit_w dstw, struct sljit_jump **ret0_jump, 373 uint32_t (*fn)(const struct mbuf *, uint32_t, int *)) 374 { 375 #if BPFJIT_X != SLJIT_TEMPORARY_EREG1 || \ 376 BPFJIT_X == SLJIT_RETURN_REG 377 #error "Not supported assignment of registers." 378 #endif 379 int status; 380 381 /* 382 * The third argument of fn is an address on stack. 383 */ 384 const int arg3_offset = 0; 385 386 if (BPF_CLASS(pc->code) == BPF_LDX) { 387 /* save A */ 388 status = sljit_emit_op1(compiler, 389 SLJIT_MOV, 390 BPFJIT_KERN_TMP, 0, 391 BPFJIT_A, 0); 392 if (status != SLJIT_SUCCESS) 393 return status; 394 } 395 396 /* 397 * Prepare registers for fn(buf, k, &err) call. 398 */ 399 status = sljit_emit_op1(compiler, 400 SLJIT_MOV, 401 SLJIT_TEMPORARY_REG1, 0, 402 BPFJIT_BUF, 0); 403 if (status != SLJIT_SUCCESS) 404 return status; 405 406 if (BPF_CLASS(pc->code) == BPF_LD && BPF_MODE(pc->code) == BPF_IND) { 407 status = sljit_emit_op2(compiler, 408 SLJIT_ADD, 409 SLJIT_TEMPORARY_REG2, 0, 410 BPFJIT_X, 0, 411 SLJIT_IMM, (uint32_t)pc->k); 412 } else { 413 status = sljit_emit_op1(compiler, 414 SLJIT_MOV, 415 SLJIT_TEMPORARY_REG2, 0, 416 SLJIT_IMM, (uint32_t)pc->k); 417 } 418 419 if (status != SLJIT_SUCCESS) 420 return status; 421 422 status = sljit_get_local_base(compiler, 423 SLJIT_TEMPORARY_REG3, 0, arg3_offset); 424 if (status != SLJIT_SUCCESS) 425 return status; 426 427 /* fn(buf, k, &err); */ 428 status = sljit_emit_ijump(compiler, 429 SLJIT_CALL3, 430 SLJIT_IMM, SLJIT_FUNC_OFFSET(fn)); 431 432 if (BPF_CLASS(pc->code) == BPF_LDX) { 433 434 /* move return value to dst */ 435 BPFJIT_ASSERT(dst != SLJIT_RETURN_REG); 436 status = sljit_emit_op1(compiler, 437 SLJIT_MOV, 438 dst, dstw, 439 SLJIT_RETURN_REG, 0); 440 if (status != SLJIT_SUCCESS) 441 return status; 442 443 /* restore A */ 444 status = sljit_emit_op1(compiler, 445 SLJIT_MOV, 446 BPFJIT_A, 0, 447 BPFJIT_KERN_TMP, 0); 448 if (status != SLJIT_SUCCESS) 449 return status; 450 451 } else if (dst != SLJIT_RETURN_REG) { 452 status = sljit_emit_op1(compiler, 453 SLJIT_MOV, 454 dst, dstw, 455 SLJIT_RETURN_REG, 0); 456 if (status != SLJIT_SUCCESS) 457 return status; 458 } 459 460 /* tmp3 = *err; */ 461 status = sljit_emit_op1(compiler, 462 SLJIT_MOV_UI, 463 SLJIT_TEMPORARY_REG3, 0, 464 SLJIT_MEM1(SLJIT_LOCALS_REG), arg3_offset); 465 if (status != SLJIT_SUCCESS) 466 return status; 467 468 /* if (tmp3 != 0) return 0; */ 469 *ret0_jump = sljit_emit_cmp(compiler, 470 SLJIT_C_NOT_EQUAL, 471 SLJIT_TEMPORARY_REG3, 0, 472 SLJIT_IMM, 0); 473 if (*ret0_jump == NULL) 474 return SLJIT_ERR_ALLOC_FAILED; 475 476 return status; 477 } 478 #endif 479 480 /* 481 * Generate code for 482 * BPF_LD+BPF_W+BPF_ABS A <- P[k:4] 483 * BPF_LD+BPF_H+BPF_ABS A <- P[k:2] 484 * BPF_LD+BPF_B+BPF_ABS A <- P[k:1] 485 * BPF_LD+BPF_W+BPF_IND A <- P[X+k:4] 486 * BPF_LD+BPF_H+BPF_IND A <- P[X+k:2] 487 * BPF_LD+BPF_B+BPF_IND A <- P[X+k:1] 488 */ 489 static int 490 emit_pkt_read(struct sljit_compiler* compiler, 491 struct bpf_insn *pc, struct sljit_jump *to_mchain_jump, 492 struct sljit_jump **ret0, size_t *ret0_size) 493 { 494 int status; 495 uint32_t width; 496 struct sljit_jump *jump; 497 #ifdef _KERNEL 498 struct sljit_label *label; 499 struct sljit_jump *over_mchain_jump; 500 const bool check_zero_buflen = (to_mchain_jump != NULL); 501 #endif 502 const uint32_t k = pc->k; 503 504 #ifdef _KERNEL 505 if (to_mchain_jump == NULL) { 506 to_mchain_jump = sljit_emit_cmp(compiler, 507 SLJIT_C_EQUAL, 508 BPFJIT_BUFLEN, 0, 509 SLJIT_IMM, 0); 510 if (to_mchain_jump == NULL) 511 return SLJIT_ERR_ALLOC_FAILED; 512 } 513 #endif 514 515 width = read_width(pc); 516 517 if (BPF_MODE(pc->code) == BPF_IND) { 518 /* tmp1 = buflen - (pc->k + width); */ 519 status = sljit_emit_op2(compiler, 520 SLJIT_SUB, 521 BPFJIT_TMP1, 0, 522 BPFJIT_BUFLEN, 0, 523 SLJIT_IMM, k + width); 524 if (status != SLJIT_SUCCESS) 525 return status; 526 527 /* buf += X; */ 528 status = sljit_emit_op2(compiler, 529 SLJIT_ADD, 530 BPFJIT_BUF, 0, 531 BPFJIT_BUF, 0, 532 BPFJIT_X, 0); 533 if (status != SLJIT_SUCCESS) 534 return status; 535 536 /* if (tmp1 < X) return 0; */ 537 jump = sljit_emit_cmp(compiler, 538 SLJIT_C_LESS, 539 BPFJIT_TMP1, 0, 540 BPFJIT_X, 0); 541 if (jump == NULL) 542 return SLJIT_ERR_ALLOC_FAILED; 543 ret0[(*ret0_size)++] = jump; 544 } 545 546 switch (width) { 547 case 4: 548 status = emit_read32(compiler, k); 549 break; 550 case 2: 551 status = emit_read16(compiler, k); 552 break; 553 case 1: 554 status = emit_read8(compiler, k); 555 break; 556 } 557 558 if (status != SLJIT_SUCCESS) 559 return status; 560 561 if (BPF_MODE(pc->code) == BPF_IND) { 562 /* buf -= X; */ 563 status = sljit_emit_op2(compiler, 564 SLJIT_SUB, 565 BPFJIT_BUF, 0, 566 BPFJIT_BUF, 0, 567 BPFJIT_X, 0); 568 if (status != SLJIT_SUCCESS) 569 return status; 570 } 571 572 #ifdef _KERNEL 573 over_mchain_jump = sljit_emit_jump(compiler, SLJIT_JUMP); 574 if (over_mchain_jump == NULL) 575 return SLJIT_ERR_ALLOC_FAILED; 576 577 /* entry point to mchain handler */ 578 label = sljit_emit_label(compiler); 579 if (label == NULL) 580 return SLJIT_ERR_ALLOC_FAILED; 581 sljit_set_label(to_mchain_jump, label); 582 583 if (check_zero_buflen) { 584 /* if (buflen != 0) return 0; */ 585 jump = sljit_emit_cmp(compiler, 586 SLJIT_C_NOT_EQUAL, 587 BPFJIT_BUFLEN, 0, 588 SLJIT_IMM, 0); 589 if (jump == NULL) 590 return SLJIT_ERR_ALLOC_FAILED; 591 ret0[(*ret0_size)++] = jump; 592 } 593 594 switch (width) { 595 case 4: 596 status = emit_xcall(compiler, pc, BPFJIT_A, 0, &jump, &m_xword); 597 break; 598 case 2: 599 status = emit_xcall(compiler, pc, BPFJIT_A, 0, &jump, &m_xhalf); 600 break; 601 case 1: 602 status = emit_xcall(compiler, pc, BPFJIT_A, 0, &jump, &m_xbyte); 603 break; 604 } 605 606 if (status != SLJIT_SUCCESS) 607 return status; 608 609 ret0[(*ret0_size)++] = jump; 610 611 label = sljit_emit_label(compiler); 612 if (label == NULL) 613 return SLJIT_ERR_ALLOC_FAILED; 614 sljit_set_label(over_mchain_jump, label); 615 #endif 616 617 return status; 618 } 619 620 /* 621 * Generate code for BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf). 622 */ 623 static int 624 emit_msh(struct sljit_compiler* compiler, 625 struct bpf_insn *pc, struct sljit_jump *to_mchain_jump, 626 struct sljit_jump **ret0, size_t *ret0_size) 627 { 628 int status; 629 #ifdef _KERNEL 630 struct sljit_label *label; 631 struct sljit_jump *jump, *over_mchain_jump; 632 const bool check_zero_buflen = (to_mchain_jump != NULL); 633 #endif 634 const uint32_t k = pc->k; 635 636 #ifdef _KERNEL 637 if (to_mchain_jump == NULL) { 638 to_mchain_jump = sljit_emit_cmp(compiler, 639 SLJIT_C_EQUAL, 640 BPFJIT_BUFLEN, 0, 641 SLJIT_IMM, 0); 642 if (to_mchain_jump == NULL) 643 return SLJIT_ERR_ALLOC_FAILED; 644 } 645 #endif 646 647 /* tmp1 = buf[k] */ 648 status = sljit_emit_op1(compiler, 649 SLJIT_MOV_UB, 650 BPFJIT_TMP1, 0, 651 SLJIT_MEM1(BPFJIT_BUF), k); 652 if (status != SLJIT_SUCCESS) 653 return status; 654 655 /* tmp1 &= 0xf */ 656 status = sljit_emit_op2(compiler, 657 SLJIT_AND, 658 BPFJIT_TMP1, 0, 659 BPFJIT_TMP1, 0, 660 SLJIT_IMM, 0xf); 661 if (status != SLJIT_SUCCESS) 662 return status; 663 664 /* tmp1 = tmp1 << 2 */ 665 status = sljit_emit_op2(compiler, 666 SLJIT_SHL, 667 BPFJIT_X, 0, 668 BPFJIT_TMP1, 0, 669 SLJIT_IMM, 2); 670 if (status != SLJIT_SUCCESS) 671 return status; 672 673 #ifdef _KERNEL 674 over_mchain_jump = sljit_emit_jump(compiler, SLJIT_JUMP); 675 if (over_mchain_jump == NULL) 676 return SLJIT_ERR_ALLOC_FAILED; 677 678 /* entry point to mchain handler */ 679 label = sljit_emit_label(compiler); 680 if (label == NULL) 681 return SLJIT_ERR_ALLOC_FAILED; 682 sljit_set_label(to_mchain_jump, label); 683 684 if (check_zero_buflen) { 685 /* if (buflen != 0) return 0; */ 686 jump = sljit_emit_cmp(compiler, 687 SLJIT_C_NOT_EQUAL, 688 BPFJIT_BUFLEN, 0, 689 SLJIT_IMM, 0); 690 if (jump == NULL) 691 return SLJIT_ERR_ALLOC_FAILED; 692 ret0[(*ret0_size)++] = jump; 693 } 694 695 status = emit_xcall(compiler, pc, BPFJIT_TMP1, 0, &jump, &m_xbyte); 696 if (status != SLJIT_SUCCESS) 697 return status; 698 ret0[(*ret0_size)++] = jump; 699 700 /* tmp1 &= 0xf */ 701 status = sljit_emit_op2(compiler, 702 SLJIT_AND, 703 BPFJIT_TMP1, 0, 704 BPFJIT_TMP1, 0, 705 SLJIT_IMM, 0xf); 706 if (status != SLJIT_SUCCESS) 707 return status; 708 709 /* tmp1 = tmp1 << 2 */ 710 status = sljit_emit_op2(compiler, 711 SLJIT_SHL, 712 BPFJIT_X, 0, 713 BPFJIT_TMP1, 0, 714 SLJIT_IMM, 2); 715 if (status != SLJIT_SUCCESS) 716 return status; 717 718 719 label = sljit_emit_label(compiler); 720 if (label == NULL) 721 return SLJIT_ERR_ALLOC_FAILED; 722 sljit_set_label(over_mchain_jump, label); 723 #endif 724 725 return status; 726 } 727 728 static int 729 emit_pow2_division(struct sljit_compiler* compiler, uint32_t k) 730 { 731 int shift = 0; 732 int status = SLJIT_SUCCESS; 733 734 while (k > 1) { 735 k >>= 1; 736 shift++; 737 } 738 739 BPFJIT_ASSERT(k == 1 && shift < 32); 740 741 if (shift != 0) { 742 status = sljit_emit_op2(compiler, 743 SLJIT_LSHR|SLJIT_INT_OP, 744 BPFJIT_A, 0, 745 BPFJIT_A, 0, 746 SLJIT_IMM, shift); 747 } 748 749 return status; 750 } 751 752 #if !defined(BPFJIT_USE_UDIV) 753 static sljit_uw 754 divide(sljit_uw x, sljit_uw y) 755 { 756 757 return (uint32_t)x / (uint32_t)y; 758 } 759 #endif 760 761 /* 762 * Generate A = A / div. 763 * divt,divw are either SLJIT_IMM,pc->k or BPFJIT_X,0. 764 */ 765 static int 766 emit_division(struct sljit_compiler* compiler, int divt, sljit_w divw) 767 { 768 int status; 769 770 #if BPFJIT_X == SLJIT_TEMPORARY_REG1 || \ 771 BPFJIT_X == SLJIT_RETURN_REG || \ 772 BPFJIT_X == SLJIT_TEMPORARY_REG2 || \ 773 BPFJIT_A == SLJIT_TEMPORARY_REG2 774 #error "Not supported assignment of registers." 775 #endif 776 777 #if BPFJIT_A != SLJIT_TEMPORARY_REG1 778 status = sljit_emit_op1(compiler, 779 SLJIT_MOV, 780 SLJIT_TEMPORARY_REG1, 0, 781 BPFJIT_A, 0); 782 if (status != SLJIT_SUCCESS) 783 return status; 784 #endif 785 786 status = sljit_emit_op1(compiler, 787 SLJIT_MOV, 788 SLJIT_TEMPORARY_REG2, 0, 789 divt, divw); 790 if (status != SLJIT_SUCCESS) 791 return status; 792 793 #if defined(BPFJIT_USE_UDIV) 794 status = sljit_emit_op0(compiler, SLJIT_UDIV|SLJIT_INT_OP); 795 796 #if BPFJIT_A != SLJIT_TEMPORARY_REG1 797 status = sljit_emit_op1(compiler, 798 SLJIT_MOV, 799 BPFJIT_A, 0, 800 SLJIT_TEMPORARY_REG1, 0); 801 if (status != SLJIT_SUCCESS) 802 return status; 803 #endif 804 #else 805 status = sljit_emit_ijump(compiler, 806 SLJIT_CALL2, 807 SLJIT_IMM, SLJIT_FUNC_OFFSET(divide)); 808 809 #if BPFJIT_A != SLJIT_RETURN_REG 810 status = sljit_emit_op1(compiler, 811 SLJIT_MOV, 812 BPFJIT_A, 0, 813 SLJIT_RETURN_REG, 0); 814 if (status != SLJIT_SUCCESS) 815 return status; 816 #endif 817 #endif 818 819 return status; 820 } 821 822 /* 823 * Count BPF_RET instructions. 824 */ 825 static size_t 826 count_returns(struct bpf_insn *insns, size_t insn_count) 827 { 828 size_t i; 829 size_t rv; 830 831 rv = 0; 832 for (i = 0; i < insn_count; i++) { 833 if (BPF_CLASS(insns[i].code) == BPF_RET) 834 rv++; 835 } 836 837 return rv; 838 } 839 840 /* 841 * Return true if pc is a "read from packet" instruction. 842 * If length is not NULL and return value is true, *length will 843 * be set to a safe length required to read a packet. 844 */ 845 static bool 846 read_pkt_insn(struct bpf_insn *pc, uint32_t *length) 847 { 848 bool rv; 849 uint32_t width; 850 851 switch (BPF_CLASS(pc->code)) { 852 default: 853 rv = false; 854 break; 855 856 case BPF_LD: 857 rv = BPF_MODE(pc->code) == BPF_ABS || 858 BPF_MODE(pc->code) == BPF_IND; 859 if (rv) 860 width = read_width(pc); 861 break; 862 863 case BPF_LDX: 864 rv = pc->code == (BPF_LDX|BPF_B|BPF_MSH); 865 width = 1; 866 break; 867 } 868 869 if (rv && length != NULL) { 870 *length = (pc->k > UINT32_MAX - width) ? 871 UINT32_MAX : pc->k + width; 872 } 873 874 return rv; 875 } 876 877 /* 878 * Set bj_check_length for all "read from packet" instructions 879 * in a linear block of instructions [from, to). 880 */ 881 static void 882 set_check_length(struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, 883 size_t from, size_t to, uint32_t length) 884 { 885 886 for (; from < to; from++) { 887 if (read_pkt_insn(&insns[from], NULL)) { 888 insn_dat[from].bj_aux.bj_rdata.bj_check_length = length; 889 length = 0; 890 } 891 } 892 } 893 894 /* 895 * The function divides instructions into blocks. Destination of a jump 896 * instruction starts a new block. BPF_RET and BPF_JMP instructions 897 * terminate a block. Blocks are linear, that is, there are no jumps out 898 * from the middle of a block and there are no jumps in to the middle of 899 * a block. 900 * If a block has one or more "read from packet" instructions, 901 * bj_check_length will be set to one value for the whole block and that 902 * value will be equal to the greatest value of safe lengths of "read from 903 * packet" instructions inside the block. 904 */ 905 static int 906 optimize(struct bpf_insn *insns, 907 struct bpfjit_insn_data *insn_dat, size_t insn_count) 908 { 909 size_t i; 910 size_t first_read; 911 bool unreachable; 912 uint32_t jt, jf; 913 uint32_t length, safe_length; 914 struct bpfjit_jump *jmp, *jtf; 915 916 for (i = 0; i < insn_count; i++) 917 SLIST_INIT(&insn_dat[i].bj_jumps); 918 919 safe_length = 0; 920 unreachable = false; 921 first_read = SIZE_MAX; 922 923 for (i = 0; i < insn_count; i++) { 924 925 if (!SLIST_EMPTY(&insn_dat[i].bj_jumps)) { 926 unreachable = false; 927 928 set_check_length(insns, insn_dat, 929 first_read, i, safe_length); 930 first_read = SIZE_MAX; 931 932 safe_length = UINT32_MAX; 933 SLIST_FOREACH(jmp, &insn_dat[i].bj_jumps, bj_entries) { 934 if (jmp->bj_safe_length < safe_length) 935 safe_length = jmp->bj_safe_length; 936 } 937 } 938 939 insn_dat[i].bj_unreachable = unreachable; 940 if (unreachable) 941 continue; 942 943 if (read_pkt_insn(&insns[i], &length)) { 944 if (first_read == SIZE_MAX) 945 first_read = i; 946 if (length > safe_length) 947 safe_length = length; 948 } 949 950 switch (BPF_CLASS(insns[i].code)) { 951 case BPF_RET: 952 unreachable = true; 953 continue; 954 955 case BPF_JMP: 956 if (insns[i].code == (BPF_JMP|BPF_JA)) { 957 jt = jf = insns[i].k; 958 } else { 959 jt = insns[i].jt; 960 jf = insns[i].jf; 961 } 962 963 if (jt >= insn_count - (i + 1) || 964 jf >= insn_count - (i + 1)) { 965 return -1; 966 } 967 968 if (jt > 0 && jf > 0) 969 unreachable = true; 970 971 jtf = insn_dat[i].bj_aux.bj_jdata.bj_jtf; 972 973 jtf[0].bj_jump = NULL; 974 jtf[0].bj_safe_length = safe_length; 975 SLIST_INSERT_HEAD(&insn_dat[i + 1 + jt].bj_jumps, 976 &jtf[0], bj_entries); 977 978 if (jf != jt) { 979 jtf[1].bj_jump = NULL; 980 jtf[1].bj_safe_length = safe_length; 981 SLIST_INSERT_HEAD(&insn_dat[i + 1 + jf].bj_jumps, 982 &jtf[1], bj_entries); 983 } 984 985 continue; 986 } 987 } 988 989 set_check_length(insns, insn_dat, first_read, insn_count, safe_length); 990 991 return 0; 992 } 993 994 /* 995 * Count out-of-bounds and division by zero jumps. 996 * 997 * insn_dat should be initialized by optimize(). 998 */ 999 static size_t 1000 get_ret0_size(struct bpf_insn *insns, struct bpfjit_insn_data *insn_dat, 1001 size_t insn_count) 1002 { 1003 size_t rv = 0; 1004 size_t i; 1005 1006 for (i = 0; i < insn_count; i++) { 1007 1008 if (read_pkt_insn(&insns[i], NULL)) { 1009 if (insn_dat[i].bj_aux.bj_rdata.bj_check_length > 0) 1010 rv++; 1011 #ifdef _KERNEL 1012 rv++; 1013 #endif 1014 } 1015 1016 if (insns[i].code == (BPF_LD|BPF_IND|BPF_B) || 1017 insns[i].code == (BPF_LD|BPF_IND|BPF_H) || 1018 insns[i].code == (BPF_LD|BPF_IND|BPF_W)) { 1019 rv++; 1020 } 1021 1022 if (insns[i].code == (BPF_ALU|BPF_DIV|BPF_X)) 1023 rv++; 1024 1025 if (insns[i].code == (BPF_ALU|BPF_DIV|BPF_K) && 1026 insns[i].k == 0) { 1027 rv++; 1028 } 1029 } 1030 1031 return rv; 1032 } 1033 1034 /* 1035 * Convert BPF_ALU operations except BPF_NEG and BPF_DIV to sljit operation. 1036 */ 1037 static int 1038 bpf_alu_to_sljit_op(struct bpf_insn *pc) 1039 { 1040 1041 /* 1042 * Note: all supported 64bit arches have 32bit multiply 1043 * instruction so SLJIT_INT_OP doesn't have any overhead. 1044 */ 1045 switch (BPF_OP(pc->code)) { 1046 case BPF_ADD: return SLJIT_ADD; 1047 case BPF_SUB: return SLJIT_SUB; 1048 case BPF_MUL: return SLJIT_MUL|SLJIT_INT_OP; 1049 case BPF_OR: return SLJIT_OR; 1050 case BPF_AND: return SLJIT_AND; 1051 case BPF_LSH: return SLJIT_SHL; 1052 case BPF_RSH: return SLJIT_LSHR|SLJIT_INT_OP; 1053 default: 1054 BPFJIT_ASSERT(false); 1055 return 0; 1056 } 1057 } 1058 1059 /* 1060 * Convert BPF_JMP operations except BPF_JA to sljit condition. 1061 */ 1062 static int 1063 bpf_jmp_to_sljit_cond(struct bpf_insn *pc, bool negate) 1064 { 1065 /* 1066 * Note: all supported 64bit arches have 32bit comparison 1067 * instructions so SLJIT_INT_OP doesn't have any overhead. 1068 */ 1069 int rv = SLJIT_INT_OP; 1070 1071 switch (BPF_OP(pc->code)) { 1072 case BPF_JGT: 1073 rv |= negate ? SLJIT_C_LESS_EQUAL : SLJIT_C_GREATER; 1074 break; 1075 case BPF_JGE: 1076 rv |= negate ? SLJIT_C_LESS : SLJIT_C_GREATER_EQUAL; 1077 break; 1078 case BPF_JEQ: 1079 rv |= negate ? SLJIT_C_NOT_EQUAL : SLJIT_C_EQUAL; 1080 break; 1081 case BPF_JSET: 1082 rv |= negate ? SLJIT_C_EQUAL : SLJIT_C_NOT_EQUAL; 1083 break; 1084 default: 1085 BPFJIT_ASSERT(false); 1086 } 1087 1088 return rv; 1089 } 1090 1091 static unsigned int 1092 bpfjit_optimization_hints(struct bpf_insn *insns, size_t insn_count) 1093 { 1094 unsigned int rv = BPFJIT_INIT_A; 1095 struct bpf_insn *pc; 1096 int minm, maxm; 1097 1098 BPFJIT_ASSERT(BPF_MEMWORDS - 1 <= 0xff); 1099 1100 maxm = 0; 1101 minm = BPF_MEMWORDS - 1; 1102 1103 for (pc = insns; pc != insns + insn_count; pc++) { 1104 switch (BPF_CLASS(pc->code)) { 1105 case BPF_LD: 1106 if (BPF_MODE(pc->code) == BPF_IND) 1107 rv |= BPFJIT_INIT_X; 1108 if (BPF_MODE(pc->code) == BPF_MEM && 1109 (uint32_t)pc->k < BPF_MEMWORDS) { 1110 if (pc->k > maxm) 1111 maxm = pc->k; 1112 if (pc->k < minm) 1113 minm = pc->k; 1114 } 1115 continue; 1116 case BPF_LDX: 1117 rv |= BPFJIT_INIT_X; 1118 if (BPF_MODE(pc->code) == BPF_MEM && 1119 (uint32_t)pc->k < BPF_MEMWORDS) { 1120 if (pc->k > maxm) 1121 maxm = pc->k; 1122 if (pc->k < minm) 1123 minm = pc->k; 1124 } 1125 continue; 1126 case BPF_ST: 1127 if ((uint32_t)pc->k < BPF_MEMWORDS) { 1128 if (pc->k > maxm) 1129 maxm = pc->k; 1130 if (pc->k < minm) 1131 minm = pc->k; 1132 } 1133 continue; 1134 case BPF_STX: 1135 rv |= BPFJIT_INIT_X; 1136 if ((uint32_t)pc->k < BPF_MEMWORDS) { 1137 if (pc->k > maxm) 1138 maxm = pc->k; 1139 if (pc->k < minm) 1140 minm = pc->k; 1141 } 1142 continue; 1143 case BPF_ALU: 1144 if (pc->code == (BPF_ALU|BPF_NEG)) 1145 continue; 1146 if (BPF_SRC(pc->code) == BPF_X) 1147 rv |= BPFJIT_INIT_X; 1148 continue; 1149 case BPF_JMP: 1150 if (pc->code == (BPF_JMP|BPF_JA)) 1151 continue; 1152 if (BPF_SRC(pc->code) == BPF_X) 1153 rv |= BPFJIT_INIT_X; 1154 continue; 1155 case BPF_RET: 1156 continue; 1157 case BPF_MISC: 1158 rv |= BPFJIT_INIT_X; 1159 continue; 1160 default: 1161 BPFJIT_ASSERT(false); 1162 } 1163 } 1164 1165 return rv | (maxm << 8) | minm; 1166 } 1167 1168 /* 1169 * Convert BPF_K and BPF_X to sljit register. 1170 */ 1171 static int 1172 kx_to_reg(struct bpf_insn *pc) 1173 { 1174 1175 switch (BPF_SRC(pc->code)) { 1176 case BPF_K: return SLJIT_IMM; 1177 case BPF_X: return BPFJIT_X; 1178 default: 1179 BPFJIT_ASSERT(false); 1180 return 0; 1181 } 1182 } 1183 1184 static sljit_w 1185 kx_to_reg_arg(struct bpf_insn *pc) 1186 { 1187 1188 switch (BPF_SRC(pc->code)) { 1189 case BPF_K: return (uint32_t)pc->k; /* SLJIT_IMM, pc->k, */ 1190 case BPF_X: return 0; /* BPFJIT_X, 0, */ 1191 default: 1192 BPFJIT_ASSERT(false); 1193 return 0; 1194 } 1195 } 1196 1197 bpfjit_function_t 1198 bpfjit_generate_code(struct bpf_insn *insns, size_t insn_count) 1199 { 1200 void *rv; 1201 size_t i; 1202 int status; 1203 int branching, negate; 1204 unsigned int rval, mode, src; 1205 int ntmp; 1206 int locals_size; 1207 int minm, maxm; /* min/max k for M[k] */ 1208 int mem_locals_start; /* start of M[] array */ 1209 unsigned int opts; 1210 struct bpf_insn *pc; 1211 struct sljit_compiler* compiler; 1212 1213 /* a list of jumps to a normal return from a generated function */ 1214 struct sljit_jump **returns; 1215 size_t returns_size, returns_maxsize; 1216 1217 /* a list of jumps to out-of-bound return from a generated function */ 1218 struct sljit_jump **ret0; 1219 size_t ret0_size, ret0_maxsize; 1220 1221 struct bpfjit_insn_data *insn_dat; 1222 1223 /* for local use */ 1224 struct sljit_label *label; 1225 struct sljit_jump *jump; 1226 struct bpfjit_jump *bjump, *jtf; 1227 1228 struct sljit_jump *to_mchain_jump; 1229 1230 uint32_t jt, jf; 1231 1232 rv = NULL; 1233 compiler = NULL; 1234 insn_dat = NULL; 1235 returns = NULL; 1236 ret0 = NULL; 1237 1238 opts = bpfjit_optimization_hints(insns, insn_count); 1239 minm = opts & 0xff; 1240 maxm = (opts >> 8) & 0xff; 1241 mem_locals_start = mem_local_offset(0, 0); 1242 locals_size = (minm <= maxm) ? 1243 mem_local_offset(maxm + 1, minm) : mem_locals_start; 1244 1245 ntmp = 4; 1246 #ifdef _KERNEL 1247 ntmp += 1; /* for BPFJIT_KERN_TMP */ 1248 #endif 1249 1250 returns_maxsize = count_returns(insns, insn_count); 1251 if (returns_maxsize == 0) 1252 goto fail; 1253 1254 insn_dat = BPFJIT_MALLOC(insn_count * sizeof(insn_dat[0])); 1255 if (insn_dat == NULL) 1256 goto fail; 1257 1258 if (optimize(insns, insn_dat, insn_count) < 0) 1259 goto fail; 1260 1261 ret0_size = 0; 1262 ret0_maxsize = get_ret0_size(insns, insn_dat, insn_count); 1263 if (ret0_maxsize > 0) { 1264 ret0 = BPFJIT_MALLOC(ret0_maxsize * sizeof(ret0[0])); 1265 if (ret0 == NULL) 1266 goto fail; 1267 } 1268 1269 returns_size = 0; 1270 returns = BPFJIT_MALLOC(returns_maxsize * sizeof(returns[0])); 1271 if (returns == NULL) 1272 goto fail; 1273 1274 compiler = sljit_create_compiler(); 1275 if (compiler == NULL) 1276 goto fail; 1277 1278 #if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE 1279 sljit_compiler_verbose(compiler, stderr); 1280 #endif 1281 1282 status = sljit_emit_enter(compiler, 3, ntmp, 3, locals_size); 1283 if (status != SLJIT_SUCCESS) 1284 goto fail; 1285 1286 for (i = mem_locals_start; i < locals_size; i+= sizeof(uint32_t)) { 1287 status = sljit_emit_op1(compiler, 1288 SLJIT_MOV_UI, 1289 SLJIT_MEM1(SLJIT_LOCALS_REG), i, 1290 SLJIT_IMM, 0); 1291 if (status != SLJIT_SUCCESS) 1292 goto fail; 1293 } 1294 1295 if (opts & BPFJIT_INIT_A) { 1296 /* A = 0; */ 1297 status = sljit_emit_op1(compiler, 1298 SLJIT_MOV, 1299 BPFJIT_A, 0, 1300 SLJIT_IMM, 0); 1301 if (status != SLJIT_SUCCESS) 1302 goto fail; 1303 } 1304 1305 if (opts & BPFJIT_INIT_X) { 1306 /* X = 0; */ 1307 status = sljit_emit_op1(compiler, 1308 SLJIT_MOV, 1309 BPFJIT_X, 0, 1310 SLJIT_IMM, 0); 1311 if (status != SLJIT_SUCCESS) 1312 goto fail; 1313 } 1314 1315 for (i = 0; i < insn_count; i++) { 1316 if (insn_dat[i].bj_unreachable) 1317 continue; 1318 1319 to_mchain_jump = NULL; 1320 1321 /* 1322 * Resolve jumps to the current insn. 1323 */ 1324 label = NULL; 1325 SLIST_FOREACH(bjump, &insn_dat[i].bj_jumps, bj_entries) { 1326 if (bjump->bj_jump != NULL) { 1327 if (label == NULL) 1328 label = sljit_emit_label(compiler); 1329 if (label == NULL) 1330 goto fail; 1331 sljit_set_label(bjump->bj_jump, label); 1332 } 1333 } 1334 1335 if (read_pkt_insn(&insns[i], NULL) && 1336 insn_dat[i].bj_aux.bj_rdata.bj_check_length > 0) { 1337 /* if (buflen < bj_check_length) return 0; */ 1338 jump = sljit_emit_cmp(compiler, 1339 SLJIT_C_LESS, 1340 BPFJIT_BUFLEN, 0, 1341 SLJIT_IMM, 1342 insn_dat[i].bj_aux.bj_rdata.bj_check_length); 1343 if (jump == NULL) 1344 goto fail; 1345 #ifdef _KERNEL 1346 to_mchain_jump = jump; 1347 #else 1348 ret0[ret0_size++] = jump; 1349 #endif 1350 } 1351 1352 pc = &insns[i]; 1353 switch (BPF_CLASS(pc->code)) { 1354 1355 default: 1356 goto fail; 1357 1358 case BPF_LD: 1359 /* BPF_LD+BPF_IMM A <- k */ 1360 if (pc->code == (BPF_LD|BPF_IMM)) { 1361 status = sljit_emit_op1(compiler, 1362 SLJIT_MOV, 1363 BPFJIT_A, 0, 1364 SLJIT_IMM, (uint32_t)pc->k); 1365 if (status != SLJIT_SUCCESS) 1366 goto fail; 1367 1368 continue; 1369 } 1370 1371 /* BPF_LD+BPF_MEM A <- M[k] */ 1372 if (pc->code == (BPF_LD|BPF_MEM)) { 1373 if (pc->k < minm || pc->k > maxm) 1374 goto fail; 1375 status = sljit_emit_op1(compiler, 1376 SLJIT_MOV_UI, 1377 BPFJIT_A, 0, 1378 SLJIT_MEM1(SLJIT_LOCALS_REG), 1379 mem_local_offset(pc->k, minm)); 1380 if (status != SLJIT_SUCCESS) 1381 goto fail; 1382 1383 continue; 1384 } 1385 1386 /* BPF_LD+BPF_W+BPF_LEN A <- len */ 1387 if (pc->code == (BPF_LD|BPF_W|BPF_LEN)) { 1388 status = sljit_emit_op1(compiler, 1389 SLJIT_MOV, 1390 BPFJIT_A, 0, 1391 BPFJIT_WIRELEN, 0); 1392 if (status != SLJIT_SUCCESS) 1393 goto fail; 1394 1395 continue; 1396 } 1397 1398 mode = BPF_MODE(pc->code); 1399 if (mode != BPF_ABS && mode != BPF_IND) 1400 goto fail; 1401 1402 status = emit_pkt_read(compiler, pc, 1403 to_mchain_jump, ret0, &ret0_size); 1404 if (status != SLJIT_SUCCESS) 1405 goto fail; 1406 1407 continue; 1408 1409 case BPF_LDX: 1410 mode = BPF_MODE(pc->code); 1411 1412 /* BPF_LDX+BPF_W+BPF_IMM X <- k */ 1413 if (mode == BPF_IMM) { 1414 if (BPF_SIZE(pc->code) != BPF_W) 1415 goto fail; 1416 status = sljit_emit_op1(compiler, 1417 SLJIT_MOV, 1418 BPFJIT_X, 0, 1419 SLJIT_IMM, (uint32_t)pc->k); 1420 if (status != SLJIT_SUCCESS) 1421 goto fail; 1422 1423 continue; 1424 } 1425 1426 /* BPF_LDX+BPF_W+BPF_LEN X <- len */ 1427 if (mode == BPF_LEN) { 1428 if (BPF_SIZE(pc->code) != BPF_W) 1429 goto fail; 1430 status = sljit_emit_op1(compiler, 1431 SLJIT_MOV, 1432 BPFJIT_X, 0, 1433 BPFJIT_WIRELEN, 0); 1434 if (status != SLJIT_SUCCESS) 1435 goto fail; 1436 1437 continue; 1438 } 1439 1440 /* BPF_LDX+BPF_W+BPF_MEM X <- M[k] */ 1441 if (mode == BPF_MEM) { 1442 if (BPF_SIZE(pc->code) != BPF_W) 1443 goto fail; 1444 if (pc->k < minm || pc->k > maxm) 1445 goto fail; 1446 status = sljit_emit_op1(compiler, 1447 SLJIT_MOV_UI, 1448 BPFJIT_X, 0, 1449 SLJIT_MEM1(SLJIT_LOCALS_REG), 1450 mem_local_offset(pc->k, minm)); 1451 if (status != SLJIT_SUCCESS) 1452 goto fail; 1453 1454 continue; 1455 } 1456 1457 /* BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) */ 1458 if (mode != BPF_MSH || BPF_SIZE(pc->code) != BPF_B) 1459 goto fail; 1460 1461 status = emit_msh(compiler, pc, 1462 to_mchain_jump, ret0, &ret0_size); 1463 if (status != SLJIT_SUCCESS) 1464 goto fail; 1465 1466 continue; 1467 1468 case BPF_ST: 1469 if (pc->code != BPF_ST || pc->k < minm || pc->k > maxm) 1470 goto fail; 1471 1472 status = sljit_emit_op1(compiler, 1473 SLJIT_MOV_UI, 1474 SLJIT_MEM1(SLJIT_LOCALS_REG), 1475 mem_local_offset(pc->k, minm), 1476 BPFJIT_A, 0); 1477 if (status != SLJIT_SUCCESS) 1478 goto fail; 1479 1480 continue; 1481 1482 case BPF_STX: 1483 if (pc->code != BPF_STX || pc->k < minm || pc->k > maxm) 1484 goto fail; 1485 1486 status = sljit_emit_op1(compiler, 1487 SLJIT_MOV_UI, 1488 SLJIT_MEM1(SLJIT_LOCALS_REG), 1489 mem_local_offset(pc->k, minm), 1490 BPFJIT_X, 0); 1491 if (status != SLJIT_SUCCESS) 1492 goto fail; 1493 1494 continue; 1495 1496 case BPF_ALU: 1497 1498 if (pc->code == (BPF_ALU|BPF_NEG)) { 1499 status = sljit_emit_op1(compiler, 1500 SLJIT_NEG, 1501 BPFJIT_A, 0, 1502 BPFJIT_A, 0); 1503 if (status != SLJIT_SUCCESS) 1504 goto fail; 1505 1506 continue; 1507 } 1508 1509 if (BPF_OP(pc->code) != BPF_DIV) { 1510 status = sljit_emit_op2(compiler, 1511 bpf_alu_to_sljit_op(pc), 1512 BPFJIT_A, 0, 1513 BPFJIT_A, 0, 1514 kx_to_reg(pc), kx_to_reg_arg(pc)); 1515 if (status != SLJIT_SUCCESS) 1516 goto fail; 1517 1518 continue; 1519 } 1520 1521 /* BPF_DIV */ 1522 1523 src = BPF_SRC(pc->code); 1524 if (src != BPF_X && src != BPF_K) 1525 goto fail; 1526 1527 /* division by zero? */ 1528 if (src == BPF_X) { 1529 jump = sljit_emit_cmp(compiler, 1530 SLJIT_C_EQUAL|SLJIT_INT_OP, 1531 BPFJIT_X, 0, 1532 SLJIT_IMM, 0); 1533 if (jump == NULL) 1534 goto fail; 1535 ret0[ret0_size++] = jump; 1536 } else if (pc->k == 0) { 1537 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1538 if (jump == NULL) 1539 goto fail; 1540 ret0[ret0_size++] = jump; 1541 } 1542 1543 if (src == BPF_X) { 1544 status = emit_division(compiler, BPFJIT_X, 0); 1545 if (status != SLJIT_SUCCESS) 1546 goto fail; 1547 } else if (pc->k != 0) { 1548 if (pc->k & (pc->k - 1)) { 1549 status = emit_division(compiler, 1550 SLJIT_IMM, (uint32_t)pc->k); 1551 } else { 1552 status = emit_pow2_division(compiler, 1553 (uint32_t)pc->k); 1554 } 1555 if (status != SLJIT_SUCCESS) 1556 goto fail; 1557 } 1558 1559 continue; 1560 1561 case BPF_JMP: 1562 1563 if (pc->code == (BPF_JMP|BPF_JA)) { 1564 jt = jf = pc->k; 1565 } else { 1566 jt = pc->jt; 1567 jf = pc->jf; 1568 } 1569 1570 negate = (jt == 0) ? 1 : 0; 1571 branching = (jt == jf) ? 0 : 1; 1572 jtf = insn_dat[i].bj_aux.bj_jdata.bj_jtf; 1573 1574 if (branching) { 1575 if (BPF_OP(pc->code) != BPF_JSET) { 1576 jump = sljit_emit_cmp(compiler, 1577 bpf_jmp_to_sljit_cond(pc, negate), 1578 BPFJIT_A, 0, 1579 kx_to_reg(pc), kx_to_reg_arg(pc)); 1580 } else { 1581 status = sljit_emit_op2(compiler, 1582 SLJIT_AND, 1583 BPFJIT_TMP1, 0, 1584 BPFJIT_A, 0, 1585 kx_to_reg(pc), kx_to_reg_arg(pc)); 1586 if (status != SLJIT_SUCCESS) 1587 goto fail; 1588 1589 jump = sljit_emit_cmp(compiler, 1590 bpf_jmp_to_sljit_cond(pc, negate), 1591 BPFJIT_TMP1, 0, 1592 SLJIT_IMM, 0); 1593 } 1594 1595 if (jump == NULL) 1596 goto fail; 1597 1598 BPFJIT_ASSERT(jtf[negate].bj_jump == NULL); 1599 jtf[negate].bj_jump = jump; 1600 } 1601 1602 if (!branching || (jt != 0 && jf != 0)) { 1603 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1604 if (jump == NULL) 1605 goto fail; 1606 1607 BPFJIT_ASSERT(jtf[branching].bj_jump == NULL); 1608 jtf[branching].bj_jump = jump; 1609 } 1610 1611 continue; 1612 1613 case BPF_RET: 1614 1615 rval = BPF_RVAL(pc->code); 1616 if (rval == BPF_X) 1617 goto fail; 1618 1619 /* BPF_RET+BPF_K accept k bytes */ 1620 if (rval == BPF_K) { 1621 status = sljit_emit_op1(compiler, 1622 SLJIT_MOV, 1623 BPFJIT_A, 0, 1624 SLJIT_IMM, (uint32_t)pc->k); 1625 if (status != SLJIT_SUCCESS) 1626 goto fail; 1627 } 1628 1629 /* BPF_RET+BPF_A accept A bytes */ 1630 if (rval == BPF_A) { 1631 #if BPFJIT_A != SLJIT_RETURN_REG 1632 status = sljit_emit_op1(compiler, 1633 SLJIT_MOV, 1634 SLJIT_RETURN_REG, 0, 1635 BPFJIT_A, 0); 1636 if (status != SLJIT_SUCCESS) 1637 goto fail; 1638 #endif 1639 } 1640 1641 /* 1642 * Save a jump to a normal return. If the program 1643 * ends with BPF_RET, no jump is needed because 1644 * the normal return is generated right after the 1645 * last instruction. 1646 */ 1647 if (i != insn_count - 1) { 1648 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1649 if (jump == NULL) 1650 goto fail; 1651 returns[returns_size++] = jump; 1652 } 1653 1654 continue; 1655 1656 case BPF_MISC: 1657 1658 if (pc->code == (BPF_MISC|BPF_TAX)) { 1659 status = sljit_emit_op1(compiler, 1660 SLJIT_MOV_UI, 1661 BPFJIT_X, 0, 1662 BPFJIT_A, 0); 1663 if (status != SLJIT_SUCCESS) 1664 goto fail; 1665 1666 continue; 1667 } 1668 1669 if (pc->code == (BPF_MISC|BPF_TXA)) { 1670 status = sljit_emit_op1(compiler, 1671 SLJIT_MOV, 1672 BPFJIT_A, 0, 1673 BPFJIT_X, 0); 1674 if (status != SLJIT_SUCCESS) 1675 goto fail; 1676 1677 continue; 1678 } 1679 1680 goto fail; 1681 } /* switch */ 1682 } /* main loop */ 1683 1684 BPFJIT_ASSERT(ret0_size == ret0_maxsize); 1685 BPFJIT_ASSERT(returns_size <= returns_maxsize); 1686 1687 if (returns_size > 0) { 1688 label = sljit_emit_label(compiler); 1689 if (label == NULL) 1690 goto fail; 1691 for (i = 0; i < returns_size; i++) 1692 sljit_set_label(returns[i], label); 1693 } 1694 1695 status = sljit_emit_return(compiler, 1696 SLJIT_MOV_UI, 1697 BPFJIT_A, 0); 1698 if (status != SLJIT_SUCCESS) 1699 goto fail; 1700 1701 if (ret0_size > 0) { 1702 label = sljit_emit_label(compiler); 1703 if (label == NULL) 1704 goto fail; 1705 1706 for (i = 0; i < ret0_size; i++) 1707 sljit_set_label(ret0[i], label); 1708 1709 status = sljit_emit_op1(compiler, 1710 SLJIT_MOV, 1711 SLJIT_RETURN_REG, 0, 1712 SLJIT_IMM, 0); 1713 if (status != SLJIT_SUCCESS) 1714 goto fail; 1715 1716 status = sljit_emit_return(compiler, 1717 SLJIT_MOV_UI, 1718 SLJIT_RETURN_REG, 0); 1719 if (status != SLJIT_SUCCESS) 1720 goto fail; 1721 } 1722 1723 rv = sljit_generate_code(compiler); 1724 1725 fail: 1726 if (compiler != NULL) 1727 sljit_free_compiler(compiler); 1728 1729 if (insn_dat != NULL) 1730 BPFJIT_FREE(insn_dat); 1731 1732 if (returns != NULL) 1733 BPFJIT_FREE(returns); 1734 1735 if (ret0 != NULL) 1736 BPFJIT_FREE(ret0); 1737 1738 return (bpfjit_function_t)rv; 1739 } 1740 1741 void 1742 bpfjit_free_code(bpfjit_function_t code) 1743 { 1744 1745 sljit_free_code((void *)code); 1746 } 1747