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