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