bpfjit.c revision 1.9
1 /* $NetBSD: bpfjit.c,v 1.9 2014/05/23 19:11:22 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.9 2014/05/23 19:11:22 alnsn Exp $"); 35 #else 36 __RCSID("$NetBSD: bpfjit.c,v 1.9 2014/05/23 19:11:22 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_init_mask_t invalid; /* borrowed from bpf_filter() */ 949 bool unreachable; 950 951 *nscratches = 2; 952 *initmask = BJ_INIT_NOBITS; 953 954 unreachable = false; 955 invalid = ~BJ_INIT_NOBITS; 956 957 for (i = 0; i < insn_count; i++) { 958 if (!SLIST_EMPTY(&insn_dat[i].bjumps)) 959 unreachable = false; 960 insn_dat[i].unreachable = unreachable; 961 962 if (unreachable) 963 continue; 964 965 invalid |= insn_dat[i].invalid; 966 967 switch (BPF_CLASS(insns[i].code)) { 968 case BPF_RET: 969 if (BPF_RVAL(insns[i].code) == BPF_A) 970 *initmask |= invalid & BJ_INIT_ABIT; 971 972 unreachable = true; 973 continue; 974 975 case BPF_LD: 976 if (BPF_MODE(insns[i].code) == BPF_IND || 977 BPF_MODE(insns[i].code) == BPF_ABS) { 978 if (BPF_MODE(insns[i].code) == BPF_IND && 979 *nscratches < 4) { 980 /* uses BJ_XREG */ 981 *nscratches = 4; 982 } 983 if (*nscratches < 3 && 984 read_width(&insns[i]) == 4) { 985 /* uses BJ_TMP2REG */ 986 *nscratches = 3; 987 } 988 } 989 990 if (BPF_MODE(insns[i].code) == BPF_IND) 991 *initmask |= invalid & BJ_INIT_XBIT; 992 993 if (BPF_MODE(insns[i].code) == BPF_MEM && 994 (uint32_t)insns[i].k < BPF_MEMWORDS) { 995 *initmask |= invalid & BJ_INIT_MBIT(insns[i].k); 996 } 997 998 invalid &= ~BJ_INIT_ABIT; 999 continue; 1000 1001 case BPF_LDX: 1002 #if defined(_KERNEL) 1003 /* uses BJ_TMP3REG */ 1004 *nscratches = 5; 1005 #endif 1006 /* uses BJ_XREG */ 1007 if (*nscratches < 4) 1008 *nscratches = 4; 1009 1010 if (BPF_MODE(insns[i].code) == BPF_MEM && 1011 (uint32_t)insns[i].k < BPF_MEMWORDS) { 1012 *initmask |= invalid & BJ_INIT_MBIT(insns[i].k); 1013 } 1014 1015 invalid &= ~BJ_INIT_XBIT; 1016 continue; 1017 1018 case BPF_ST: 1019 *initmask |= invalid & BJ_INIT_ABIT; 1020 1021 if ((uint32_t)insns[i].k < BPF_MEMWORDS) 1022 invalid &= ~BJ_INIT_MBIT(insns[i].k); 1023 1024 continue; 1025 1026 case BPF_STX: 1027 /* uses BJ_XREG */ 1028 if (*nscratches < 4) 1029 *nscratches = 4; 1030 1031 *initmask |= invalid & BJ_INIT_XBIT; 1032 1033 if ((uint32_t)insns[i].k < BPF_MEMWORDS) 1034 invalid &= ~BJ_INIT_MBIT(insns[i].k); 1035 1036 continue; 1037 1038 case BPF_ALU: 1039 *initmask |= invalid & BJ_INIT_ABIT; 1040 1041 if (insns[i].code != (BPF_ALU|BPF_NEG) && 1042 BPF_SRC(insns[i].code) == BPF_X) { 1043 *initmask |= invalid & BJ_INIT_XBIT; 1044 /* uses BJ_XREG */ 1045 if (*nscratches < 4) 1046 *nscratches = 4; 1047 1048 } 1049 1050 invalid &= ~BJ_INIT_ABIT; 1051 continue; 1052 1053 case BPF_MISC: 1054 switch (BPF_MISCOP(insns[i].code)) { 1055 case BPF_TAX: // X <- A 1056 /* uses BJ_XREG */ 1057 if (*nscratches < 4) 1058 *nscratches = 4; 1059 1060 *initmask |= invalid & BJ_INIT_ABIT; 1061 invalid &= ~BJ_INIT_XBIT; 1062 continue; 1063 1064 case BPF_TXA: // A <- X 1065 /* uses BJ_XREG */ 1066 if (*nscratches < 4) 1067 *nscratches = 4; 1068 1069 *initmask |= invalid & BJ_INIT_XBIT; 1070 invalid &= ~BJ_INIT_ABIT; 1071 continue; 1072 } 1073 1074 continue; 1075 1076 case BPF_JMP: 1077 /* Initialize abc_length for ABC pass. */ 1078 insn_dat[i].u.jdata.abc_length = MAX_ABC_LENGTH; 1079 1080 if (BPF_OP(insns[i].code) == BPF_JA) { 1081 jt = jf = insns[i].k; 1082 } else { 1083 jt = insns[i].jt; 1084 jf = insns[i].jf; 1085 } 1086 1087 if (jt >= insn_count - (i + 1) || 1088 jf >= insn_count - (i + 1)) { 1089 return false; 1090 } 1091 1092 if (jt > 0 && jf > 0) 1093 unreachable = true; 1094 1095 jt += i + 1; 1096 jf += i + 1; 1097 1098 jtf = insn_dat[i].u.jdata.jtf; 1099 1100 jtf[0].sjump = NULL; 1101 jtf[0].jdata = &insn_dat[i].u.jdata; 1102 SLIST_INSERT_HEAD(&insn_dat[jt].bjumps, 1103 &jtf[0], entries); 1104 1105 if (jf != jt) { 1106 jtf[1].sjump = NULL; 1107 jtf[1].jdata = &insn_dat[i].u.jdata; 1108 SLIST_INSERT_HEAD(&insn_dat[jf].bjumps, 1109 &jtf[1], entries); 1110 } 1111 1112 insn_dat[jf].invalid |= invalid; 1113 insn_dat[jt].invalid |= invalid; 1114 invalid = 0; 1115 1116 continue; 1117 } 1118 } 1119 1120 return true; 1121 } 1122 1123 /* 1124 * Array Bounds Check Elimination (ABC) pass. 1125 */ 1126 static void 1127 optimize_pass2(const struct bpf_insn *insns, 1128 struct bpfjit_insn_data *insn_dat, size_t insn_count) 1129 { 1130 struct bpfjit_jump *jmp; 1131 const struct bpf_insn *pc; 1132 struct bpfjit_insn_data *pd; 1133 size_t i; 1134 bpfjit_abc_length_t length, abc_length = 0; 1135 1136 for (i = insn_count; i != 0; i--) { 1137 pc = &insns[i-1]; 1138 pd = &insn_dat[i-1]; 1139 1140 if (pd->unreachable) 1141 continue; 1142 1143 switch (BPF_CLASS(pc->code)) { 1144 case BPF_RET: 1145 abc_length = 0; 1146 break; 1147 1148 case BPF_JMP: 1149 abc_length = pd->u.jdata.abc_length; 1150 break; 1151 1152 default: 1153 if (read_pkt_insn(pc, &length)) { 1154 if (abc_length < length) 1155 abc_length = length; 1156 pd->u.rdata.abc_length = abc_length; 1157 } 1158 break; 1159 } 1160 1161 SLIST_FOREACH(jmp, &pd->bjumps, entries) { 1162 if (jmp->jdata->abc_length > abc_length) 1163 jmp->jdata->abc_length = abc_length; 1164 } 1165 } 1166 } 1167 1168 static void 1169 optimize_pass3(const struct bpf_insn *insns, 1170 struct bpfjit_insn_data *insn_dat, size_t insn_count) 1171 { 1172 struct bpfjit_jump *jmp; 1173 size_t i; 1174 bpfjit_abc_length_t checked_length = 0; 1175 1176 for (i = 0; i < insn_count; i++) { 1177 if (insn_dat[i].unreachable) 1178 continue; 1179 1180 SLIST_FOREACH(jmp, &insn_dat[i].bjumps, entries) { 1181 if (jmp->jdata->checked_length < checked_length) 1182 checked_length = jmp->jdata->checked_length; 1183 } 1184 1185 if (BPF_CLASS(insns[i].code) == BPF_JMP) { 1186 insn_dat[i].u.jdata.checked_length = checked_length; 1187 } else if (read_pkt_insn(&insns[i], NULL)) { 1188 struct bpfjit_read_pkt_data *rdata = 1189 &insn_dat[i].u.rdata; 1190 rdata->check_length = 0; 1191 if (checked_length < rdata->abc_length) { 1192 checked_length = rdata->abc_length; 1193 rdata->check_length = checked_length; 1194 } 1195 } 1196 } 1197 } 1198 1199 static bool 1200 optimize(const struct bpf_insn *insns, 1201 struct bpfjit_insn_data *insn_dat, size_t insn_count, 1202 bpfjit_init_mask_t *initmask, int *nscratches) 1203 { 1204 1205 optimize_init(insn_dat, insn_count); 1206 1207 if (!optimize_pass1(insns, insn_dat, insn_count, 1208 initmask, nscratches)) { 1209 return false; 1210 } 1211 1212 optimize_pass2(insns, insn_dat, insn_count); 1213 optimize_pass3(insns, insn_dat, insn_count); 1214 1215 return true; 1216 } 1217 1218 /* 1219 * Convert BPF_ALU operations except BPF_NEG and BPF_DIV to sljit operation. 1220 */ 1221 static int 1222 bpf_alu_to_sljit_op(const struct bpf_insn *pc) 1223 { 1224 1225 /* 1226 * Note: all supported 64bit arches have 32bit multiply 1227 * instruction so SLJIT_INT_OP doesn't have any overhead. 1228 */ 1229 switch (BPF_OP(pc->code)) { 1230 case BPF_ADD: return SLJIT_ADD; 1231 case BPF_SUB: return SLJIT_SUB; 1232 case BPF_MUL: return SLJIT_MUL|SLJIT_INT_OP; 1233 case BPF_OR: return SLJIT_OR; 1234 case BPF_AND: return SLJIT_AND; 1235 case BPF_LSH: return SLJIT_SHL; 1236 case BPF_RSH: return SLJIT_LSHR|SLJIT_INT_OP; 1237 default: 1238 BJ_ASSERT(false); 1239 return 0; 1240 } 1241 } 1242 1243 /* 1244 * Convert BPF_JMP operations except BPF_JA to sljit condition. 1245 */ 1246 static int 1247 bpf_jmp_to_sljit_cond(const struct bpf_insn *pc, bool negate) 1248 { 1249 /* 1250 * Note: all supported 64bit arches have 32bit comparison 1251 * instructions so SLJIT_INT_OP doesn't have any overhead. 1252 */ 1253 int rv = SLJIT_INT_OP; 1254 1255 switch (BPF_OP(pc->code)) { 1256 case BPF_JGT: 1257 rv |= negate ? SLJIT_C_LESS_EQUAL : SLJIT_C_GREATER; 1258 break; 1259 case BPF_JGE: 1260 rv |= negate ? SLJIT_C_LESS : SLJIT_C_GREATER_EQUAL; 1261 break; 1262 case BPF_JEQ: 1263 rv |= negate ? SLJIT_C_NOT_EQUAL : SLJIT_C_EQUAL; 1264 break; 1265 case BPF_JSET: 1266 rv |= negate ? SLJIT_C_EQUAL : SLJIT_C_NOT_EQUAL; 1267 break; 1268 default: 1269 BJ_ASSERT(false); 1270 } 1271 1272 return rv; 1273 } 1274 1275 /* 1276 * Convert BPF_K and BPF_X to sljit register. 1277 */ 1278 static int 1279 kx_to_reg(const struct bpf_insn *pc) 1280 { 1281 1282 switch (BPF_SRC(pc->code)) { 1283 case BPF_K: return SLJIT_IMM; 1284 case BPF_X: return BJ_XREG; 1285 default: 1286 BJ_ASSERT(false); 1287 return 0; 1288 } 1289 } 1290 1291 static sljit_w 1292 kx_to_reg_arg(const struct bpf_insn *pc) 1293 { 1294 1295 switch (BPF_SRC(pc->code)) { 1296 case BPF_K: return (uint32_t)pc->k; /* SLJIT_IMM, pc->k, */ 1297 case BPF_X: return 0; /* BJ_XREG, 0, */ 1298 default: 1299 BJ_ASSERT(false); 1300 return 0; 1301 } 1302 } 1303 1304 bpfjit_func_t 1305 bpfjit_generate_code(bpf_ctx_t *bc, struct bpf_insn *insns, size_t insn_count) 1306 { 1307 void *rv; 1308 struct sljit_compiler *compiler; 1309 1310 size_t i; 1311 int status; 1312 int branching, negate; 1313 unsigned int rval, mode, src; 1314 1315 /* optimization related */ 1316 bpfjit_init_mask_t initmask; 1317 int nscratches; 1318 1319 /* a list of jumps to out-of-bound return from a generated function */ 1320 struct sljit_jump **ret0; 1321 size_t ret0_size, ret0_maxsize; 1322 1323 const struct bpf_insn *pc; 1324 struct bpfjit_insn_data *insn_dat; 1325 1326 /* for local use */ 1327 struct sljit_label *label; 1328 struct sljit_jump *jump; 1329 struct bpfjit_jump *bjump, *jtf; 1330 1331 struct sljit_jump *to_mchain_jump; 1332 bool unconditional_ret; 1333 1334 uint32_t jt, jf; 1335 1336 rv = NULL; 1337 compiler = NULL; 1338 insn_dat = NULL; 1339 ret0 = NULL; 1340 1341 if (insn_count == 0 || insn_count > SIZE_MAX / sizeof(insn_dat[0])) 1342 goto fail; 1343 1344 insn_dat = BJ_ALLOC(insn_count * sizeof(insn_dat[0])); 1345 if (insn_dat == NULL) 1346 goto fail; 1347 1348 if (!optimize(insns, insn_dat, insn_count, 1349 &initmask, &nscratches)) { 1350 goto fail; 1351 } 1352 1353 #if defined(_KERNEL) 1354 /* bpf_filter() checks initialization of memwords. */ 1355 BJ_ASSERT((initmask & BJ_INIT_MMASK) == 0); 1356 #endif 1357 1358 ret0_size = 0; 1359 ret0_maxsize = 64; 1360 ret0 = BJ_ALLOC(ret0_maxsize * sizeof(ret0[0])); 1361 if (ret0 == NULL) 1362 goto fail; 1363 1364 compiler = sljit_create_compiler(); 1365 if (compiler == NULL) 1366 goto fail; 1367 1368 #if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE 1369 sljit_compiler_verbose(compiler, stderr); 1370 #endif 1371 1372 status = sljit_emit_enter(compiler, 1373 3, nscratches, 3, sizeof(struct bpfjit_stack)); 1374 if (status != SLJIT_SUCCESS) 1375 goto fail; 1376 1377 for (i = 0; i < BPF_MEMWORDS; i++) { 1378 if (initmask & BJ_INIT_MBIT(i)) { 1379 status = sljit_emit_op1(compiler, 1380 SLJIT_MOV_UI, 1381 SLJIT_MEM1(SLJIT_LOCALS_REG), 1382 offsetof(struct bpfjit_stack, mem) + 1383 i * sizeof(uint32_t), 1384 SLJIT_IMM, 0); 1385 if (status != SLJIT_SUCCESS) 1386 goto fail; 1387 } 1388 } 1389 1390 if (initmask & BJ_INIT_ABIT) { 1391 /* A = 0; */ 1392 status = sljit_emit_op1(compiler, 1393 SLJIT_MOV, 1394 BJ_AREG, 0, 1395 SLJIT_IMM, 0); 1396 if (status != SLJIT_SUCCESS) 1397 goto fail; 1398 } 1399 1400 if (initmask & BJ_INIT_XBIT) { 1401 /* X = 0; */ 1402 status = sljit_emit_op1(compiler, 1403 SLJIT_MOV, 1404 BJ_XREG, 0, 1405 SLJIT_IMM, 0); 1406 if (status != SLJIT_SUCCESS) 1407 goto fail; 1408 } 1409 1410 for (i = 0; i < insn_count; i++) { 1411 if (insn_dat[i].unreachable) 1412 continue; 1413 1414 /* 1415 * Resolve jumps to the current insn. 1416 */ 1417 label = NULL; 1418 SLIST_FOREACH(bjump, &insn_dat[i].bjumps, entries) { 1419 if (bjump->sjump != NULL) { 1420 if (label == NULL) 1421 label = sljit_emit_label(compiler); 1422 if (label == NULL) 1423 goto fail; 1424 sljit_set_label(bjump->sjump, label); 1425 } 1426 } 1427 1428 to_mchain_jump = NULL; 1429 unconditional_ret = false; 1430 1431 if (read_pkt_insn(&insns[i], NULL)) { 1432 if (insn_dat[i].u.rdata.check_length > UINT32_MAX) { 1433 /* Jump to "return 0" unconditionally. */ 1434 unconditional_ret = true; 1435 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1436 if (jump == NULL) 1437 goto fail; 1438 if (!append_jump(jump, &ret0, 1439 &ret0_size, &ret0_maxsize)) 1440 goto fail; 1441 } else if (insn_dat[i].u.rdata.check_length > 0) { 1442 /* if (buflen < check_length) return 0; */ 1443 jump = sljit_emit_cmp(compiler, 1444 SLJIT_C_LESS, 1445 BJ_BUFLEN, 0, 1446 SLJIT_IMM, 1447 insn_dat[i].u.rdata.check_length); 1448 if (jump == NULL) 1449 goto fail; 1450 #ifdef _KERNEL 1451 to_mchain_jump = jump; 1452 #else 1453 if (!append_jump(jump, &ret0, 1454 &ret0_size, &ret0_maxsize)) 1455 goto fail; 1456 #endif 1457 } 1458 } 1459 1460 pc = &insns[i]; 1461 switch (BPF_CLASS(pc->code)) { 1462 1463 default: 1464 goto fail; 1465 1466 case BPF_LD: 1467 /* BPF_LD+BPF_IMM A <- k */ 1468 if (pc->code == (BPF_LD|BPF_IMM)) { 1469 status = sljit_emit_op1(compiler, 1470 SLJIT_MOV, 1471 BJ_AREG, 0, 1472 SLJIT_IMM, (uint32_t)pc->k); 1473 if (status != SLJIT_SUCCESS) 1474 goto fail; 1475 1476 continue; 1477 } 1478 1479 /* BPF_LD+BPF_MEM A <- M[k] */ 1480 if (pc->code == (BPF_LD|BPF_MEM)) { 1481 if ((uint32_t)pc->k >= BPF_MEMWORDS) 1482 goto fail; 1483 status = sljit_emit_op1(compiler, 1484 SLJIT_MOV_UI, 1485 BJ_AREG, 0, 1486 SLJIT_MEM1(SLJIT_LOCALS_REG), 1487 offsetof(struct bpfjit_stack, mem) + 1488 pc->k * sizeof(uint32_t)); 1489 if (status != SLJIT_SUCCESS) 1490 goto fail; 1491 1492 continue; 1493 } 1494 1495 /* BPF_LD+BPF_W+BPF_LEN A <- len */ 1496 if (pc->code == (BPF_LD|BPF_W|BPF_LEN)) { 1497 status = sljit_emit_op1(compiler, 1498 SLJIT_MOV, 1499 BJ_AREG, 0, 1500 BJ_WIRELEN, 0); 1501 if (status != SLJIT_SUCCESS) 1502 goto fail; 1503 1504 continue; 1505 } 1506 1507 mode = BPF_MODE(pc->code); 1508 if (mode != BPF_ABS && mode != BPF_IND) 1509 goto fail; 1510 1511 if (unconditional_ret) 1512 continue; 1513 1514 status = emit_pkt_read(compiler, pc, 1515 to_mchain_jump, &ret0, &ret0_size, &ret0_maxsize); 1516 if (status != SLJIT_SUCCESS) 1517 goto fail; 1518 1519 continue; 1520 1521 case BPF_LDX: 1522 mode = BPF_MODE(pc->code); 1523 1524 /* BPF_LDX+BPF_W+BPF_IMM X <- k */ 1525 if (mode == BPF_IMM) { 1526 if (BPF_SIZE(pc->code) != BPF_W) 1527 goto fail; 1528 status = sljit_emit_op1(compiler, 1529 SLJIT_MOV, 1530 BJ_XREG, 0, 1531 SLJIT_IMM, (uint32_t)pc->k); 1532 if (status != SLJIT_SUCCESS) 1533 goto fail; 1534 1535 continue; 1536 } 1537 1538 /* BPF_LDX+BPF_W+BPF_LEN X <- len */ 1539 if (mode == BPF_LEN) { 1540 if (BPF_SIZE(pc->code) != BPF_W) 1541 goto fail; 1542 status = sljit_emit_op1(compiler, 1543 SLJIT_MOV, 1544 BJ_XREG, 0, 1545 BJ_WIRELEN, 0); 1546 if (status != SLJIT_SUCCESS) 1547 goto fail; 1548 1549 continue; 1550 } 1551 1552 /* BPF_LDX+BPF_W+BPF_MEM X <- M[k] */ 1553 if (mode == BPF_MEM) { 1554 if (BPF_SIZE(pc->code) != BPF_W) 1555 goto fail; 1556 if ((uint32_t)pc->k >= BPF_MEMWORDS) 1557 goto fail; 1558 status = sljit_emit_op1(compiler, 1559 SLJIT_MOV_UI, 1560 BJ_XREG, 0, 1561 SLJIT_MEM1(SLJIT_LOCALS_REG), 1562 offsetof(struct bpfjit_stack, mem) + 1563 pc->k * sizeof(uint32_t)); 1564 if (status != SLJIT_SUCCESS) 1565 goto fail; 1566 1567 continue; 1568 } 1569 1570 /* BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) */ 1571 if (mode != BPF_MSH || BPF_SIZE(pc->code) != BPF_B) 1572 goto fail; 1573 1574 if (unconditional_ret) 1575 continue; 1576 1577 status = emit_msh(compiler, pc, 1578 to_mchain_jump, &ret0, &ret0_size, &ret0_maxsize); 1579 if (status != SLJIT_SUCCESS) 1580 goto fail; 1581 1582 continue; 1583 1584 case BPF_ST: 1585 if (pc->code != BPF_ST || 1586 (uint32_t)pc->k >= BPF_MEMWORDS) { 1587 goto fail; 1588 } 1589 1590 status = sljit_emit_op1(compiler, 1591 SLJIT_MOV_UI, 1592 SLJIT_MEM1(SLJIT_LOCALS_REG), 1593 offsetof(struct bpfjit_stack, mem) + 1594 pc->k * sizeof(uint32_t), 1595 BJ_AREG, 0); 1596 if (status != SLJIT_SUCCESS) 1597 goto fail; 1598 1599 continue; 1600 1601 case BPF_STX: 1602 if (pc->code != BPF_STX || 1603 (uint32_t)pc->k >= BPF_MEMWORDS) { 1604 goto fail; 1605 } 1606 1607 status = sljit_emit_op1(compiler, 1608 SLJIT_MOV_UI, 1609 SLJIT_MEM1(SLJIT_LOCALS_REG), 1610 offsetof(struct bpfjit_stack, mem) + 1611 pc->k * sizeof(uint32_t), 1612 BJ_XREG, 0); 1613 if (status != SLJIT_SUCCESS) 1614 goto fail; 1615 1616 continue; 1617 1618 case BPF_ALU: 1619 if (pc->code == (BPF_ALU|BPF_NEG)) { 1620 status = sljit_emit_op1(compiler, 1621 SLJIT_NEG, 1622 BJ_AREG, 0, 1623 BJ_AREG, 0); 1624 if (status != SLJIT_SUCCESS) 1625 goto fail; 1626 1627 continue; 1628 } 1629 1630 if (BPF_OP(pc->code) != BPF_DIV) { 1631 status = sljit_emit_op2(compiler, 1632 bpf_alu_to_sljit_op(pc), 1633 BJ_AREG, 0, 1634 BJ_AREG, 0, 1635 kx_to_reg(pc), kx_to_reg_arg(pc)); 1636 if (status != SLJIT_SUCCESS) 1637 goto fail; 1638 1639 continue; 1640 } 1641 1642 /* BPF_DIV */ 1643 1644 src = BPF_SRC(pc->code); 1645 if (src != BPF_X && src != BPF_K) 1646 goto fail; 1647 1648 /* division by zero? */ 1649 if (src == BPF_X) { 1650 jump = sljit_emit_cmp(compiler, 1651 SLJIT_C_EQUAL|SLJIT_INT_OP, 1652 BJ_XREG, 0, 1653 SLJIT_IMM, 0); 1654 if (jump == NULL) 1655 goto fail; 1656 if (!append_jump(jump, &ret0, 1657 &ret0_size, &ret0_maxsize)) 1658 goto fail; 1659 } else if (pc->k == 0) { 1660 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1661 if (jump == NULL) 1662 goto fail; 1663 if (!append_jump(jump, &ret0, 1664 &ret0_size, &ret0_maxsize)) 1665 goto fail; 1666 } 1667 1668 if (src == BPF_X) { 1669 status = emit_division(compiler, BJ_XREG, 0); 1670 if (status != SLJIT_SUCCESS) 1671 goto fail; 1672 } else if (pc->k != 0) { 1673 if (pc->k & (pc->k - 1)) { 1674 status = emit_division(compiler, 1675 SLJIT_IMM, (uint32_t)pc->k); 1676 } else { 1677 status = emit_pow2_division(compiler, 1678 (uint32_t)pc->k); 1679 } 1680 if (status != SLJIT_SUCCESS) 1681 goto fail; 1682 } 1683 1684 continue; 1685 1686 case BPF_JMP: 1687 if (BPF_OP(pc->code) == BPF_JA) { 1688 jt = jf = pc->k; 1689 } else { 1690 jt = pc->jt; 1691 jf = pc->jf; 1692 } 1693 1694 negate = (jt == 0) ? 1 : 0; 1695 branching = (jt == jf) ? 0 : 1; 1696 jtf = insn_dat[i].u.jdata.jtf; 1697 1698 if (branching) { 1699 if (BPF_OP(pc->code) != BPF_JSET) { 1700 jump = sljit_emit_cmp(compiler, 1701 bpf_jmp_to_sljit_cond(pc, negate), 1702 BJ_AREG, 0, 1703 kx_to_reg(pc), kx_to_reg_arg(pc)); 1704 } else { 1705 status = sljit_emit_op2(compiler, 1706 SLJIT_AND, 1707 BJ_TMP1REG, 0, 1708 BJ_AREG, 0, 1709 kx_to_reg(pc), kx_to_reg_arg(pc)); 1710 if (status != SLJIT_SUCCESS) 1711 goto fail; 1712 1713 jump = sljit_emit_cmp(compiler, 1714 bpf_jmp_to_sljit_cond(pc, negate), 1715 BJ_TMP1REG, 0, 1716 SLJIT_IMM, 0); 1717 } 1718 1719 if (jump == NULL) 1720 goto fail; 1721 1722 BJ_ASSERT(jtf[negate].sjump == NULL); 1723 jtf[negate].sjump = jump; 1724 } 1725 1726 if (!branching || (jt != 0 && jf != 0)) { 1727 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1728 if (jump == NULL) 1729 goto fail; 1730 1731 BJ_ASSERT(jtf[branching].sjump == NULL); 1732 jtf[branching].sjump = jump; 1733 } 1734 1735 continue; 1736 1737 case BPF_RET: 1738 rval = BPF_RVAL(pc->code); 1739 if (rval == BPF_X) 1740 goto fail; 1741 1742 /* BPF_RET+BPF_K accept k bytes */ 1743 if (rval == BPF_K) { 1744 status = sljit_emit_return(compiler, 1745 SLJIT_MOV_UI, 1746 SLJIT_IMM, (uint32_t)pc->k); 1747 if (status != SLJIT_SUCCESS) 1748 goto fail; 1749 } 1750 1751 /* BPF_RET+BPF_A accept A bytes */ 1752 if (rval == BPF_A) { 1753 status = sljit_emit_return(compiler, 1754 SLJIT_MOV_UI, 1755 BJ_AREG, 0); 1756 if (status != SLJIT_SUCCESS) 1757 goto fail; 1758 } 1759 1760 continue; 1761 1762 case BPF_MISC: 1763 switch (BPF_MISCOP(pc->code)) { 1764 case BPF_TAX: 1765 status = sljit_emit_op1(compiler, 1766 SLJIT_MOV_UI, 1767 BJ_XREG, 0, 1768 BJ_AREG, 0); 1769 if (status != SLJIT_SUCCESS) 1770 goto fail; 1771 1772 continue; 1773 1774 case BPF_TXA: 1775 status = sljit_emit_op1(compiler, 1776 SLJIT_MOV, 1777 BJ_AREG, 0, 1778 BJ_XREG, 0); 1779 if (status != SLJIT_SUCCESS) 1780 goto fail; 1781 1782 continue; 1783 } 1784 1785 goto fail; 1786 } /* switch */ 1787 } /* main loop */ 1788 1789 BJ_ASSERT(ret0_size <= ret0_maxsize); 1790 1791 if (ret0_size > 0) { 1792 label = sljit_emit_label(compiler); 1793 if (label == NULL) 1794 goto fail; 1795 for (i = 0; i < ret0_size; i++) 1796 sljit_set_label(ret0[i], label); 1797 } 1798 1799 status = sljit_emit_return(compiler, 1800 SLJIT_MOV_UI, 1801 SLJIT_IMM, 0); 1802 if (status != SLJIT_SUCCESS) 1803 goto fail; 1804 1805 rv = sljit_generate_code(compiler); 1806 1807 fail: 1808 if (compiler != NULL) 1809 sljit_free_compiler(compiler); 1810 1811 if (insn_dat != NULL) 1812 BJ_FREE(insn_dat, insn_count * sizeof(insn_dat[0])); 1813 1814 if (ret0 != NULL) 1815 BJ_FREE(ret0, ret0_maxsize * sizeof(ret0[0])); 1816 1817 return (bpfjit_func_t)rv; 1818 } 1819 1820 void 1821 bpfjit_free_code(bpfjit_func_t code) 1822 { 1823 1824 sljit_free_code((void *)code); 1825 } 1826
Indexes created Sat Sep 27 14:09:57 GMT 2025