bpfjit.c revision 1.33
1 /* $NetBSD: bpfjit.c,v 1.33 2014/11/19 19:34:43 christos 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.33 2014/11/19 19:34:43 christos Exp $"); 35 #else 36 __RCSID("$NetBSD: bpfjit.c,v 1.33 2014/11/19 19:34:43 christos 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 * XXX: Until we support SLJIT_UMOD properly 80 */ 81 #undef BPFJIT_USE_UDIV 82 83 /* 84 * Arguments of generated bpfjit_func_t. 85 * The first argument is reassigned upon entry 86 * to a more frequently used buf argument. 87 */ 88 #define BJ_CTX_ARG SLJIT_SAVED_REG1 89 #define BJ_ARGS SLJIT_SAVED_REG2 90 91 /* 92 * Permanent register assignments. 93 */ 94 #define BJ_BUF SLJIT_SAVED_REG1 95 //#define BJ_ARGS SLJIT_SAVED_REG2 96 #define BJ_BUFLEN SLJIT_SAVED_REG3 97 #define BJ_AREG SLJIT_SCRATCH_REG1 98 #define BJ_TMP1REG SLJIT_SCRATCH_REG2 99 #define BJ_TMP2REG SLJIT_SCRATCH_REG3 100 #define BJ_XREG SLJIT_TEMPORARY_EREG1 101 #define BJ_TMP3REG SLJIT_TEMPORARY_EREG2 102 103 #ifdef _KERNEL 104 #define MAX_MEMWORDS BPF_MAX_MEMWORDS 105 #else 106 #define MAX_MEMWORDS BPF_MEMWORDS 107 #endif 108 109 #define BJ_INIT_NOBITS ((bpf_memword_init_t)0) 110 #define BJ_INIT_MBIT(k) BPF_MEMWORD_INIT(k) 111 #define BJ_INIT_ABIT BJ_INIT_MBIT(MAX_MEMWORDS) 112 #define BJ_INIT_XBIT BJ_INIT_MBIT(MAX_MEMWORDS + 1) 113 114 /* 115 * Get a number of memwords and external memwords from a bpf_ctx object. 116 */ 117 #define GET_EXTWORDS(bc) ((bc) ? (bc)->extwords : 0) 118 #define GET_MEMWORDS(bc) (GET_EXTWORDS(bc) ? GET_EXTWORDS(bc) : BPF_MEMWORDS) 119 120 /* 121 * Optimization hints. 122 */ 123 typedef unsigned int bpfjit_hint_t; 124 #define BJ_HINT_ABS 0x01 /* packet read at absolute offset */ 125 #define BJ_HINT_IND 0x02 /* packet read at variable offset */ 126 #define BJ_HINT_MSH 0x04 /* BPF_MSH instruction */ 127 #define BJ_HINT_COP 0x08 /* BPF_COP or BPF_COPX instruction */ 128 #define BJ_HINT_COPX 0x10 /* BPF_COPX instruction */ 129 #define BJ_HINT_XREG 0x20 /* BJ_XREG is needed */ 130 #define BJ_HINT_LDX 0x40 /* BPF_LDX instruction */ 131 #define BJ_HINT_PKT (BJ_HINT_ABS|BJ_HINT_IND|BJ_HINT_MSH) 132 133 /* 134 * Datatype for Array Bounds Check Elimination (ABC) pass. 135 */ 136 typedef uint64_t bpfjit_abc_length_t; 137 #define MAX_ABC_LENGTH (UINT32_MAX + UINT64_C(4)) /* max. width is 4 */ 138 139 struct bpfjit_stack 140 { 141 bpf_ctx_t *ctx; 142 uint32_t *extmem; /* pointer to external memory store */ 143 uint32_t reg; /* saved A or X register */ 144 #ifdef _KERNEL 145 int err; /* 3rd argument for m_xword/m_xhalf/m_xbyte function call */ 146 #endif 147 uint32_t mem[BPF_MEMWORDS]; /* internal memory store */ 148 }; 149 150 /* 151 * Data for BPF_JMP instruction. 152 * Forward declaration for struct bpfjit_jump. 153 */ 154 struct bpfjit_jump_data; 155 156 /* 157 * Node of bjumps list. 158 */ 159 struct bpfjit_jump { 160 struct sljit_jump *sjump; 161 SLIST_ENTRY(bpfjit_jump) entries; 162 struct bpfjit_jump_data *jdata; 163 }; 164 165 /* 166 * Data for BPF_JMP instruction. 167 */ 168 struct bpfjit_jump_data { 169 /* 170 * These entries make up bjumps list: 171 * jtf[0] - when coming from jt path, 172 * jtf[1] - when coming from jf path. 173 */ 174 struct bpfjit_jump jtf[2]; 175 /* 176 * Length calculated by Array Bounds Check Elimination (ABC) pass. 177 */ 178 bpfjit_abc_length_t abc_length; 179 /* 180 * Length checked by the last out-of-bounds check. 181 */ 182 bpfjit_abc_length_t checked_length; 183 }; 184 185 /* 186 * Data for "read from packet" instructions. 187 * See also read_pkt_insn() function below. 188 */ 189 struct bpfjit_read_pkt_data { 190 /* 191 * Length calculated by Array Bounds Check Elimination (ABC) pass. 192 */ 193 bpfjit_abc_length_t abc_length; 194 /* 195 * If positive, emit "if (buflen < check_length) return 0" 196 * out-of-bounds check. 197 * Values greater than UINT32_MAX generate unconditional "return 0". 198 */ 199 bpfjit_abc_length_t check_length; 200 }; 201 202 /* 203 * Additional (optimization-related) data for bpf_insn. 204 */ 205 struct bpfjit_insn_data { 206 /* List of jumps to this insn. */ 207 SLIST_HEAD(, bpfjit_jump) bjumps; 208 209 union { 210 struct bpfjit_jump_data jdata; 211 struct bpfjit_read_pkt_data rdata; 212 } u; 213 214 bpf_memword_init_t invalid; 215 bool unreachable; 216 }; 217 218 #ifdef _KERNEL 219 220 uint32_t m_xword(const struct mbuf *, uint32_t, int *); 221 uint32_t m_xhalf(const struct mbuf *, uint32_t, int *); 222 uint32_t m_xbyte(const struct mbuf *, uint32_t, int *); 223 224 MODULE(MODULE_CLASS_MISC, bpfjit, "sljit") 225 226 static int 227 bpfjit_modcmd(modcmd_t cmd, void *arg) 228 { 229 230 switch (cmd) { 231 case MODULE_CMD_INIT: 232 bpfjit_module_ops.bj_free_code = &bpfjit_free_code; 233 membar_producer(); 234 bpfjit_module_ops.bj_generate_code = &bpfjit_generate_code; 235 membar_producer(); 236 return 0; 237 238 case MODULE_CMD_FINI: 239 return EOPNOTSUPP; 240 241 default: 242 return ENOTTY; 243 } 244 } 245 #endif 246 247 /* 248 * Return a number of scratch registers to pass 249 * to sljit_emit_enter() function. 250 */ 251 static sljit_si 252 nscratches(bpfjit_hint_t hints) 253 { 254 sljit_si rv = 2; 255 256 #ifdef _KERNEL 257 if (hints & BJ_HINT_PKT) 258 rv = 3; /* xcall with three arguments */ 259 #endif 260 261 if (hints & BJ_HINT_IND) 262 rv = 3; /* uses BJ_TMP2REG */ 263 264 if (hints & BJ_HINT_COP) 265 rv = 3; /* calls copfunc with three arguments */ 266 267 if (hints & BJ_HINT_XREG) 268 rv = 4; /* uses BJ_XREG */ 269 270 #ifdef _KERNEL 271 if (hints & BJ_HINT_LDX) 272 rv = 5; /* uses BJ_TMP3REG */ 273 #endif 274 275 if (hints & BJ_HINT_COPX) 276 rv = 5; /* uses BJ_TMP3REG */ 277 278 return rv; 279 } 280 281 /* 282 * Return a number of saved registers to pass 283 * to sljit_emit_enter() function. 284 */ 285 static sljit_si 286 nsaveds(bpfjit_hint_t hints) 287 { 288 sljit_si rv = 3; 289 290 return rv; 291 } 292 293 static uint32_t 294 read_width(const struct bpf_insn *pc) 295 { 296 297 switch (BPF_SIZE(pc->code)) { 298 case BPF_W: 299 return 4; 300 case BPF_H: 301 return 2; 302 case BPF_B: 303 return 1; 304 default: 305 BJ_ASSERT(false); 306 return 0; 307 } 308 } 309 310 /* 311 * Copy buf and buflen members of bpf_args from BJ_ARGS 312 * pointer to BJ_BUF and BJ_BUFLEN registers. 313 */ 314 static int 315 load_buf_buflen(struct sljit_compiler *compiler) 316 { 317 int status; 318 319 status = sljit_emit_op1(compiler, 320 SLJIT_MOV_P, 321 BJ_BUF, 0, 322 SLJIT_MEM1(BJ_ARGS), 323 offsetof(struct bpf_args, pkt)); 324 if (status != SLJIT_SUCCESS) 325 return status; 326 327 status = sljit_emit_op1(compiler, 328 SLJIT_MOV, /* size_t source */ 329 BJ_BUFLEN, 0, 330 SLJIT_MEM1(BJ_ARGS), 331 offsetof(struct bpf_args, buflen)); 332 333 return status; 334 } 335 336 static bool 337 grow_jumps(struct sljit_jump ***jumps, size_t *size) 338 { 339 struct sljit_jump **newptr; 340 const size_t elemsz = sizeof(struct sljit_jump *); 341 size_t old_size = *size; 342 size_t new_size = 2 * old_size; 343 344 if (new_size < old_size || new_size > SIZE_MAX / elemsz) 345 return false; 346 347 newptr = BJ_ALLOC(new_size * elemsz); 348 if (newptr == NULL) 349 return false; 350 351 memcpy(newptr, *jumps, old_size * elemsz); 352 BJ_FREE(*jumps, old_size * elemsz); 353 354 *jumps = newptr; 355 *size = new_size; 356 return true; 357 } 358 359 static bool 360 append_jump(struct sljit_jump *jump, struct sljit_jump ***jumps, 361 size_t *size, size_t *max_size) 362 { 363 if (*size == *max_size && !grow_jumps(jumps, max_size)) 364 return false; 365 366 (*jumps)[(*size)++] = jump; 367 return true; 368 } 369 370 /* 371 * Emit code for BPF_LD+BPF_B+BPF_ABS A <- P[k:1]. 372 */ 373 static int 374 emit_read8(struct sljit_compiler *compiler, sljit_si src, uint32_t k) 375 { 376 377 return sljit_emit_op1(compiler, 378 SLJIT_MOV_UB, 379 BJ_AREG, 0, 380 SLJIT_MEM1(src), k); 381 } 382 383 /* 384 * Emit code for BPF_LD+BPF_H+BPF_ABS A <- P[k:2]. 385 */ 386 static int 387 emit_read16(struct sljit_compiler *compiler, sljit_si src, uint32_t k) 388 { 389 int status; 390 391 BJ_ASSERT(k <= UINT32_MAX - 1); 392 393 /* A = buf[k]; */ 394 status = sljit_emit_op1(compiler, 395 SLJIT_MOV_UB, 396 BJ_AREG, 0, 397 SLJIT_MEM1(src), k); 398 if (status != SLJIT_SUCCESS) 399 return status; 400 401 /* tmp1 = buf[k+1]; */ 402 status = sljit_emit_op1(compiler, 403 SLJIT_MOV_UB, 404 BJ_TMP1REG, 0, 405 SLJIT_MEM1(src), k+1); 406 if (status != SLJIT_SUCCESS) 407 return status; 408 409 /* A = A << 8; */ 410 status = sljit_emit_op2(compiler, 411 SLJIT_SHL, 412 BJ_AREG, 0, 413 BJ_AREG, 0, 414 SLJIT_IMM, 8); 415 if (status != SLJIT_SUCCESS) 416 return status; 417 418 /* A = A + tmp1; */ 419 status = sljit_emit_op2(compiler, 420 SLJIT_ADD, 421 BJ_AREG, 0, 422 BJ_AREG, 0, 423 BJ_TMP1REG, 0); 424 return status; 425 } 426 427 /* 428 * Emit code for BPF_LD+BPF_W+BPF_ABS A <- P[k:4]. 429 */ 430 static int 431 emit_read32(struct sljit_compiler *compiler, sljit_si src, uint32_t k) 432 { 433 int status; 434 435 BJ_ASSERT(k <= UINT32_MAX - 3); 436 437 /* A = buf[k]; */ 438 status = sljit_emit_op1(compiler, 439 SLJIT_MOV_UB, 440 BJ_AREG, 0, 441 SLJIT_MEM1(src), k); 442 if (status != SLJIT_SUCCESS) 443 return status; 444 445 /* tmp1 = buf[k+1]; */ 446 status = sljit_emit_op1(compiler, 447 SLJIT_MOV_UB, 448 BJ_TMP1REG, 0, 449 SLJIT_MEM1(src), k+1); 450 if (status != SLJIT_SUCCESS) 451 return status; 452 453 /* A = A << 8; */ 454 status = sljit_emit_op2(compiler, 455 SLJIT_SHL, 456 BJ_AREG, 0, 457 BJ_AREG, 0, 458 SLJIT_IMM, 8); 459 if (status != SLJIT_SUCCESS) 460 return status; 461 462 /* A = A + tmp1; */ 463 status = sljit_emit_op2(compiler, 464 SLJIT_ADD, 465 BJ_AREG, 0, 466 BJ_AREG, 0, 467 BJ_TMP1REG, 0); 468 if (status != SLJIT_SUCCESS) 469 return status; 470 471 /* tmp1 = buf[k+2]; */ 472 status = sljit_emit_op1(compiler, 473 SLJIT_MOV_UB, 474 BJ_TMP1REG, 0, 475 SLJIT_MEM1(src), k+2); 476 if (status != SLJIT_SUCCESS) 477 return status; 478 479 /* A = A << 8; */ 480 status = sljit_emit_op2(compiler, 481 SLJIT_SHL, 482 BJ_AREG, 0, 483 BJ_AREG, 0, 484 SLJIT_IMM, 8); 485 if (status != SLJIT_SUCCESS) 486 return status; 487 488 /* A = A + tmp1; */ 489 status = sljit_emit_op2(compiler, 490 SLJIT_ADD, 491 BJ_AREG, 0, 492 BJ_AREG, 0, 493 BJ_TMP1REG, 0); 494 if (status != SLJIT_SUCCESS) 495 return status; 496 497 /* tmp1 = buf[k+3]; */ 498 status = sljit_emit_op1(compiler, 499 SLJIT_MOV_UB, 500 BJ_TMP1REG, 0, 501 SLJIT_MEM1(src), k+3); 502 if (status != SLJIT_SUCCESS) 503 return status; 504 505 /* A = A << 8; */ 506 status = sljit_emit_op2(compiler, 507 SLJIT_SHL, 508 BJ_AREG, 0, 509 BJ_AREG, 0, 510 SLJIT_IMM, 8); 511 if (status != SLJIT_SUCCESS) 512 return status; 513 514 /* A = A + tmp1; */ 515 status = sljit_emit_op2(compiler, 516 SLJIT_ADD, 517 BJ_AREG, 0, 518 BJ_AREG, 0, 519 BJ_TMP1REG, 0); 520 return status; 521 } 522 523 #ifdef _KERNEL 524 /* 525 * Emit code for m_xword/m_xhalf/m_xbyte call. 526 * 527 * @pc 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 * BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) 534 */ 535 static int 536 emit_xcall(struct sljit_compiler *compiler, bpfjit_hint_t hints, 537 const struct bpf_insn *pc, int dst, struct sljit_jump ***ret0, 538 size_t *ret0_size, size_t *ret0_maxsize, 539 uint32_t (*fn)(const struct mbuf *, uint32_t, int *)) 540 { 541 #if BJ_XREG == SLJIT_RETURN_REG || \ 542 BJ_XREG == SLJIT_SCRATCH_REG1 || \ 543 BJ_XREG == SLJIT_SCRATCH_REG2 || \ 544 BJ_XREG == SLJIT_SCRATCH_REG3 545 #error "Not supported assignment of registers." 546 #endif 547 struct sljit_jump *jump; 548 sljit_si save_reg; 549 int status; 550 551 save_reg = (BPF_CLASS(pc->code) == BPF_LDX) ? BJ_AREG : BJ_XREG; 552 553 if (save_reg == BJ_AREG || (hints & BJ_HINT_XREG)) { 554 /* save A or X */ 555 status = sljit_emit_op1(compiler, 556 SLJIT_MOV_UI, /* uint32_t destination */ 557 SLJIT_MEM1(SLJIT_LOCALS_REG), 558 offsetof(struct bpfjit_stack, reg), 559 save_reg, 0); 560 if (status != SLJIT_SUCCESS) 561 return status; 562 } 563 564 /* 565 * Prepare registers for fn(mbuf, k, &err) call. 566 */ 567 status = sljit_emit_op1(compiler, 568 SLJIT_MOV, 569 SLJIT_SCRATCH_REG1, 0, 570 BJ_BUF, 0); 571 if (status != SLJIT_SUCCESS) 572 return status; 573 574 if (BPF_CLASS(pc->code) == BPF_LD && BPF_MODE(pc->code) == BPF_IND) { 575 if (pc->k == 0) { 576 /* k = X; */ 577 status = sljit_emit_op1(compiler, 578 SLJIT_MOV, 579 SLJIT_SCRATCH_REG2, 0, 580 BJ_XREG, 0); 581 if (status != SLJIT_SUCCESS) 582 return status; 583 } else { 584 /* if (X > UINT32_MAX - pc->k) return 0; */ 585 jump = sljit_emit_cmp(compiler, 586 SLJIT_C_GREATER, 587 BJ_XREG, 0, 588 SLJIT_IMM, UINT32_MAX - pc->k); 589 if (jump == NULL) 590 return SLJIT_ERR_ALLOC_FAILED; 591 if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) 592 return SLJIT_ERR_ALLOC_FAILED; 593 594 /* k = X + pc->k; */ 595 status = sljit_emit_op2(compiler, 596 SLJIT_ADD, 597 SLJIT_SCRATCH_REG2, 0, 598 BJ_XREG, 0, 599 SLJIT_IMM, (uint32_t)pc->k); 600 if (status != SLJIT_SUCCESS) 601 return status; 602 } 603 } else { 604 /* k = pc->k */ 605 status = sljit_emit_op1(compiler, 606 SLJIT_MOV, 607 SLJIT_SCRATCH_REG2, 0, 608 SLJIT_IMM, (uint32_t)pc->k); 609 if (status != SLJIT_SUCCESS) 610 return status; 611 } 612 613 /* 614 * The third argument of fn is an address on stack. 615 */ 616 status = sljit_get_local_base(compiler, 617 SLJIT_SCRATCH_REG3, 0, 618 offsetof(struct bpfjit_stack, err)); 619 if (status != SLJIT_SUCCESS) 620 return status; 621 622 /* fn(buf, k, &err); */ 623 status = sljit_emit_ijump(compiler, 624 SLJIT_CALL3, 625 SLJIT_IMM, SLJIT_FUNC_OFFSET(fn)); 626 if (status != SLJIT_SUCCESS) 627 return status; 628 629 if (dst != SLJIT_RETURN_REG) { 630 /* move return value to dst */ 631 status = sljit_emit_op1(compiler, 632 SLJIT_MOV, 633 dst, 0, 634 SLJIT_RETURN_REG, 0); 635 if (status != SLJIT_SUCCESS) 636 return status; 637 } 638 639 /* if (*err != 0) return 0; */ 640 jump = sljit_emit_cmp(compiler, 641 SLJIT_C_NOT_EQUAL|SLJIT_INT_OP, 642 SLJIT_MEM1(SLJIT_LOCALS_REG), 643 offsetof(struct bpfjit_stack, err), 644 SLJIT_IMM, 0); 645 if (jump == NULL) 646 return SLJIT_ERR_ALLOC_FAILED; 647 648 if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) 649 return SLJIT_ERR_ALLOC_FAILED; 650 651 if (save_reg == BJ_AREG || (hints & BJ_HINT_XREG)) { 652 /* restore A or X */ 653 status = sljit_emit_op1(compiler, 654 SLJIT_MOV_UI, /* uint32_t source */ 655 save_reg, 0, 656 SLJIT_MEM1(SLJIT_LOCALS_REG), 657 offsetof(struct bpfjit_stack, reg)); 658 if (status != SLJIT_SUCCESS) 659 return status; 660 } 661 662 return SLJIT_SUCCESS; 663 } 664 #endif 665 666 /* 667 * Emit code for BPF_COP and BPF_COPX instructions. 668 */ 669 static int 670 emit_cop(struct sljit_compiler *compiler, bpfjit_hint_t hints, 671 const bpf_ctx_t *bc, const struct bpf_insn *pc, 672 struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize) 673 { 674 #if BJ_XREG == SLJIT_RETURN_REG || \ 675 BJ_XREG == SLJIT_SCRATCH_REG1 || \ 676 BJ_XREG == SLJIT_SCRATCH_REG2 || \ 677 BJ_XREG == SLJIT_SCRATCH_REG3 || \ 678 BJ_TMP3REG == SLJIT_SCRATCH_REG1 || \ 679 BJ_TMP3REG == SLJIT_SCRATCH_REG2 || \ 680 BJ_TMP3REG == SLJIT_SCRATCH_REG3 681 #error "Not supported assignment of registers." 682 #endif 683 684 struct sljit_jump *jump; 685 sljit_si call_reg; 686 sljit_sw call_off; 687 int status; 688 689 BJ_ASSERT(bc != NULL && bc->copfuncs != NULL); 690 691 if (hints & BJ_HINT_LDX) { 692 /* save X */ 693 status = sljit_emit_op1(compiler, 694 SLJIT_MOV_UI, /* uint32_t destination */ 695 SLJIT_MEM1(SLJIT_LOCALS_REG), 696 offsetof(struct bpfjit_stack, reg), 697 BJ_XREG, 0); 698 if (status != SLJIT_SUCCESS) 699 return status; 700 } 701 702 if (BPF_MISCOP(pc->code) == BPF_COP) { 703 call_reg = SLJIT_IMM; 704 call_off = SLJIT_FUNC_OFFSET(bc->copfuncs[pc->k]); 705 } else { 706 /* if (X >= bc->nfuncs) return 0; */ 707 jump = sljit_emit_cmp(compiler, 708 SLJIT_C_GREATER_EQUAL, 709 BJ_XREG, 0, 710 SLJIT_IMM, bc->nfuncs); 711 if (jump == NULL) 712 return SLJIT_ERR_ALLOC_FAILED; 713 if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) 714 return SLJIT_ERR_ALLOC_FAILED; 715 716 /* tmp1 = ctx; */ 717 status = sljit_emit_op1(compiler, 718 SLJIT_MOV_P, 719 BJ_TMP1REG, 0, 720 SLJIT_MEM1(SLJIT_LOCALS_REG), 721 offsetof(struct bpfjit_stack, ctx)); 722 if (status != SLJIT_SUCCESS) 723 return status; 724 725 /* tmp1 = ctx->copfuncs; */ 726 status = sljit_emit_op1(compiler, 727 SLJIT_MOV_P, 728 BJ_TMP1REG, 0, 729 SLJIT_MEM1(BJ_TMP1REG), 730 offsetof(struct bpf_ctx, copfuncs)); 731 if (status != SLJIT_SUCCESS) 732 return status; 733 734 /* tmp2 = X; */ 735 status = sljit_emit_op1(compiler, 736 SLJIT_MOV, 737 BJ_TMP2REG, 0, 738 BJ_XREG, 0); 739 if (status != SLJIT_SUCCESS) 740 return status; 741 742 /* tmp3 = ctx->copfuncs[tmp2]; */ 743 call_reg = BJ_TMP3REG; 744 call_off = 0; 745 status = sljit_emit_op1(compiler, 746 SLJIT_MOV_P, 747 call_reg, call_off, 748 SLJIT_MEM2(BJ_TMP1REG, BJ_TMP2REG), 749 SLJIT_WORD_SHIFT); 750 if (status != SLJIT_SUCCESS) 751 return status; 752 } 753 754 /* 755 * Copy bpf_copfunc_t arguments to registers. 756 */ 757 #if BJ_AREG != SLJIT_SCRATCH_REG3 758 status = sljit_emit_op1(compiler, 759 SLJIT_MOV_UI, 760 SLJIT_SCRATCH_REG3, 0, 761 BJ_AREG, 0); 762 if (status != SLJIT_SUCCESS) 763 return status; 764 #endif 765 766 status = sljit_emit_op1(compiler, 767 SLJIT_MOV_P, 768 SLJIT_SCRATCH_REG1, 0, 769 SLJIT_MEM1(SLJIT_LOCALS_REG), 770 offsetof(struct bpfjit_stack, ctx)); 771 if (status != SLJIT_SUCCESS) 772 return status; 773 774 status = sljit_emit_op1(compiler, 775 SLJIT_MOV_P, 776 SLJIT_SCRATCH_REG2, 0, 777 BJ_ARGS, 0); 778 if (status != SLJIT_SUCCESS) 779 return status; 780 781 status = sljit_emit_ijump(compiler, 782 SLJIT_CALL3, call_reg, call_off); 783 if (status != SLJIT_SUCCESS) 784 return status; 785 786 #if BJ_AREG != SLJIT_RETURN_REG 787 status = sljit_emit_op1(compiler, 788 SLJIT_MOV, 789 BJ_AREG, 0, 790 SLJIT_RETURN_REG, 0); 791 if (status != SLJIT_SUCCESS) 792 return status; 793 #endif 794 795 if (hints & BJ_HINT_LDX) { 796 /* restore X */ 797 status = sljit_emit_op1(compiler, 798 SLJIT_MOV_UI, /* uint32_t source */ 799 BJ_XREG, 0, 800 SLJIT_MEM1(SLJIT_LOCALS_REG), 801 offsetof(struct bpfjit_stack, reg)); 802 if (status != SLJIT_SUCCESS) 803 return status; 804 } 805 806 return SLJIT_SUCCESS; 807 } 808 809 /* 810 * Generate code for 811 * BPF_LD+BPF_W+BPF_ABS A <- P[k:4] 812 * BPF_LD+BPF_H+BPF_ABS A <- P[k:2] 813 * BPF_LD+BPF_B+BPF_ABS A <- P[k:1] 814 * BPF_LD+BPF_W+BPF_IND A <- P[X+k:4] 815 * BPF_LD+BPF_H+BPF_IND A <- P[X+k:2] 816 * BPF_LD+BPF_B+BPF_IND A <- P[X+k:1] 817 */ 818 static int 819 emit_pkt_read(struct sljit_compiler *compiler, bpfjit_hint_t hints, 820 const struct bpf_insn *pc, struct sljit_jump *to_mchain_jump, 821 struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize) 822 { 823 int status = SLJIT_ERR_ALLOC_FAILED; 824 uint32_t width; 825 sljit_si ld_reg; 826 struct sljit_jump *jump; 827 #ifdef _KERNEL 828 struct sljit_label *label; 829 struct sljit_jump *over_mchain_jump; 830 const bool check_zero_buflen = (to_mchain_jump != NULL); 831 #endif 832 const uint32_t k = pc->k; 833 834 #ifdef _KERNEL 835 if (to_mchain_jump == NULL) { 836 to_mchain_jump = sljit_emit_cmp(compiler, 837 SLJIT_C_EQUAL, 838 BJ_BUFLEN, 0, 839 SLJIT_IMM, 0); 840 if (to_mchain_jump == NULL) 841 return SLJIT_ERR_ALLOC_FAILED; 842 } 843 #endif 844 845 ld_reg = BJ_BUF; 846 width = read_width(pc); 847 848 if (BPF_MODE(pc->code) == BPF_IND) { 849 /* tmp1 = buflen - (pc->k + width); */ 850 status = sljit_emit_op2(compiler, 851 SLJIT_SUB, 852 BJ_TMP1REG, 0, 853 BJ_BUFLEN, 0, 854 SLJIT_IMM, k + width); 855 if (status != SLJIT_SUCCESS) 856 return status; 857 858 /* ld_reg = buf + X; */ 859 ld_reg = BJ_TMP2REG; 860 status = sljit_emit_op2(compiler, 861 SLJIT_ADD, 862 ld_reg, 0, 863 BJ_BUF, 0, 864 BJ_XREG, 0); 865 if (status != SLJIT_SUCCESS) 866 return status; 867 868 /* if (tmp1 < X) return 0; */ 869 jump = sljit_emit_cmp(compiler, 870 SLJIT_C_LESS, 871 BJ_TMP1REG, 0, 872 BJ_XREG, 0); 873 if (jump == NULL) 874 return SLJIT_ERR_ALLOC_FAILED; 875 if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) 876 return SLJIT_ERR_ALLOC_FAILED; 877 } 878 879 switch (width) { 880 case 4: 881 status = emit_read32(compiler, ld_reg, k); 882 break; 883 case 2: 884 status = emit_read16(compiler, ld_reg, k); 885 break; 886 case 1: 887 status = emit_read8(compiler, ld_reg, k); 888 break; 889 } 890 891 if (status != SLJIT_SUCCESS) 892 return status; 893 894 #ifdef _KERNEL 895 over_mchain_jump = sljit_emit_jump(compiler, SLJIT_JUMP); 896 if (over_mchain_jump == NULL) 897 return SLJIT_ERR_ALLOC_FAILED; 898 899 /* entry point to mchain handler */ 900 label = sljit_emit_label(compiler); 901 if (label == NULL) 902 return SLJIT_ERR_ALLOC_FAILED; 903 sljit_set_label(to_mchain_jump, label); 904 905 if (check_zero_buflen) { 906 /* if (buflen != 0) return 0; */ 907 jump = sljit_emit_cmp(compiler, 908 SLJIT_C_NOT_EQUAL, 909 BJ_BUFLEN, 0, 910 SLJIT_IMM, 0); 911 if (jump == NULL) 912 return SLJIT_ERR_ALLOC_FAILED; 913 if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) 914 return SLJIT_ERR_ALLOC_FAILED; 915 } 916 917 switch (width) { 918 case 4: 919 status = emit_xcall(compiler, hints, pc, BJ_AREG, 920 ret0, ret0_size, ret0_maxsize, &m_xword); 921 break; 922 case 2: 923 status = emit_xcall(compiler, hints, pc, BJ_AREG, 924 ret0, ret0_size, ret0_maxsize, &m_xhalf); 925 break; 926 case 1: 927 status = emit_xcall(compiler, hints, pc, BJ_AREG, 928 ret0, ret0_size, ret0_maxsize, &m_xbyte); 929 break; 930 } 931 932 if (status != SLJIT_SUCCESS) 933 return status; 934 935 label = sljit_emit_label(compiler); 936 if (label == NULL) 937 return SLJIT_ERR_ALLOC_FAILED; 938 sljit_set_label(over_mchain_jump, label); 939 #endif 940 941 return SLJIT_SUCCESS; 942 } 943 944 static int 945 emit_memload(struct sljit_compiler *compiler, 946 sljit_si dst, uint32_t k, size_t extwords) 947 { 948 int status; 949 sljit_si src; 950 sljit_sw srcw; 951 952 srcw = k * sizeof(uint32_t); 953 954 if (extwords == 0) { 955 src = SLJIT_MEM1(SLJIT_LOCALS_REG); 956 srcw += offsetof(struct bpfjit_stack, mem); 957 } else { 958 /* copy extmem pointer to the tmp1 register */ 959 status = sljit_emit_op1(compiler, 960 SLJIT_MOV_P, 961 BJ_TMP1REG, 0, 962 SLJIT_MEM1(SLJIT_LOCALS_REG), 963 offsetof(struct bpfjit_stack, extmem)); 964 if (status != SLJIT_SUCCESS) 965 return status; 966 src = SLJIT_MEM1(BJ_TMP1REG); 967 } 968 969 return sljit_emit_op1(compiler, SLJIT_MOV_UI, dst, 0, src, srcw); 970 } 971 972 static int 973 emit_memstore(struct sljit_compiler *compiler, 974 sljit_si src, uint32_t k, size_t extwords) 975 { 976 int status; 977 sljit_si dst; 978 sljit_sw dstw; 979 980 dstw = k * sizeof(uint32_t); 981 982 if (extwords == 0) { 983 dst = SLJIT_MEM1(SLJIT_LOCALS_REG); 984 dstw += offsetof(struct bpfjit_stack, mem); 985 } else { 986 /* copy extmem pointer to the tmp1 register */ 987 status = sljit_emit_op1(compiler, 988 SLJIT_MOV_P, 989 BJ_TMP1REG, 0, 990 SLJIT_MEM1(SLJIT_LOCALS_REG), 991 offsetof(struct bpfjit_stack, extmem)); 992 if (status != SLJIT_SUCCESS) 993 return status; 994 dst = SLJIT_MEM1(BJ_TMP1REG); 995 } 996 997 return sljit_emit_op1(compiler, SLJIT_MOV_UI, dst, dstw, src, 0); 998 } 999 1000 /* 1001 * Emit code for BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf). 1002 */ 1003 static int 1004 emit_msh(struct sljit_compiler *compiler, bpfjit_hint_t hints, 1005 const struct bpf_insn *pc, struct sljit_jump *to_mchain_jump, 1006 struct sljit_jump ***ret0, size_t *ret0_size, size_t *ret0_maxsize) 1007 { 1008 int status; 1009 #ifdef _KERNEL 1010 struct sljit_label *label; 1011 struct sljit_jump *jump, *over_mchain_jump; 1012 const bool check_zero_buflen = (to_mchain_jump != NULL); 1013 #endif 1014 const uint32_t k = pc->k; 1015 1016 #ifdef _KERNEL 1017 if (to_mchain_jump == NULL) { 1018 to_mchain_jump = sljit_emit_cmp(compiler, 1019 SLJIT_C_EQUAL, 1020 BJ_BUFLEN, 0, 1021 SLJIT_IMM, 0); 1022 if (to_mchain_jump == NULL) 1023 return SLJIT_ERR_ALLOC_FAILED; 1024 } 1025 #endif 1026 1027 /* tmp1 = buf[k] */ 1028 status = sljit_emit_op1(compiler, 1029 SLJIT_MOV_UB, 1030 BJ_TMP1REG, 0, 1031 SLJIT_MEM1(BJ_BUF), k); 1032 if (status != SLJIT_SUCCESS) 1033 return status; 1034 1035 #ifdef _KERNEL 1036 over_mchain_jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1037 if (over_mchain_jump == NULL) 1038 return SLJIT_ERR_ALLOC_FAILED; 1039 1040 /* entry point to mchain handler */ 1041 label = sljit_emit_label(compiler); 1042 if (label == NULL) 1043 return SLJIT_ERR_ALLOC_FAILED; 1044 sljit_set_label(to_mchain_jump, label); 1045 1046 if (check_zero_buflen) { 1047 /* if (buflen != 0) return 0; */ 1048 jump = sljit_emit_cmp(compiler, 1049 SLJIT_C_NOT_EQUAL, 1050 BJ_BUFLEN, 0, 1051 SLJIT_IMM, 0); 1052 if (jump == NULL) 1053 return SLJIT_ERR_ALLOC_FAILED; 1054 if (!append_jump(jump, ret0, ret0_size, ret0_maxsize)) 1055 return SLJIT_ERR_ALLOC_FAILED; 1056 } 1057 1058 status = emit_xcall(compiler, hints, pc, BJ_TMP1REG, 1059 ret0, ret0_size, ret0_maxsize, &m_xbyte); 1060 if (status != SLJIT_SUCCESS) 1061 return status; 1062 1063 label = sljit_emit_label(compiler); 1064 if (label == NULL) 1065 return SLJIT_ERR_ALLOC_FAILED; 1066 sljit_set_label(over_mchain_jump, label); 1067 #endif 1068 1069 /* tmp1 &= 0xf */ 1070 status = sljit_emit_op2(compiler, 1071 SLJIT_AND, 1072 BJ_TMP1REG, 0, 1073 BJ_TMP1REG, 0, 1074 SLJIT_IMM, 0xf); 1075 if (status != SLJIT_SUCCESS) 1076 return status; 1077 1078 /* X = tmp1 << 2 */ 1079 status = sljit_emit_op2(compiler, 1080 SLJIT_SHL, 1081 BJ_XREG, 0, 1082 BJ_TMP1REG, 0, 1083 SLJIT_IMM, 2); 1084 if (status != SLJIT_SUCCESS) 1085 return status; 1086 1087 return SLJIT_SUCCESS; 1088 } 1089 1090 static int 1091 emit_pow2_division(struct sljit_compiler *compiler, uint32_t k) 1092 { 1093 int shift = 0; 1094 int status = SLJIT_SUCCESS; 1095 1096 while (k > 1) { 1097 k >>= 1; 1098 shift++; 1099 } 1100 1101 BJ_ASSERT(k == 1 && shift < 32); 1102 1103 if (shift != 0) { 1104 status = sljit_emit_op2(compiler, 1105 SLJIT_LSHR|SLJIT_INT_OP, 1106 BJ_AREG, 0, 1107 BJ_AREG, 0, 1108 SLJIT_IMM, shift); 1109 } 1110 1111 return status; 1112 } 1113 1114 #if !defined(BPFJIT_USE_UDIV) 1115 static sljit_uw 1116 divide(sljit_uw x, sljit_uw y) 1117 { 1118 1119 return (uint32_t)x / (uint32_t)y; 1120 } 1121 1122 static sljit_uw 1123 modulus(sljit_uw x, sljit_uw y) 1124 { 1125 1126 return (uint32_t)x % (uint32_t)y; 1127 } 1128 #endif 1129 1130 /* 1131 * Emit code for A = A / div or A = A % div 1132 * divt,divw are either SLJIT_IMM,pc->k or BJ_XREG,0. 1133 */ 1134 static int 1135 emit_moddiv(bool div, struct sljit_compiler *compiler, int divt, sljit_sw divw) 1136 { 1137 int status; 1138 1139 #if BJ_XREG == SLJIT_RETURN_REG || \ 1140 BJ_XREG == SLJIT_SCRATCH_REG1 || \ 1141 BJ_XREG == SLJIT_SCRATCH_REG2 || \ 1142 BJ_AREG == SLJIT_SCRATCH_REG2 1143 #error "Not supported assignment of registers." 1144 #endif 1145 1146 #if BJ_AREG != SLJIT_SCRATCH_REG1 1147 status = sljit_emit_op1(compiler, 1148 SLJIT_MOV, 1149 SLJIT_SCRATCH_REG1, 0, 1150 BJ_AREG, 0); 1151 if (status != SLJIT_SUCCESS) 1152 return status; 1153 #endif 1154 1155 status = sljit_emit_op1(compiler, 1156 SLJIT_MOV, 1157 SLJIT_SCRATCH_REG2, 0, 1158 divt, divw); 1159 if (status != SLJIT_SUCCESS) 1160 return status; 1161 1162 #if defined(BPFJIT_USE_UDIV) 1163 status = sljit_emit_op0(compiler, SLJIT_UDIV|SLJIT_INT_OP); 1164 1165 #if BJ_AREG != SLJIT_SCRATCH_REG1 1166 status = sljit_emit_op1(compiler, 1167 SLJIT_MOV, 1168 BJ_AREG, 0, 1169 SLJIT_SCRATCH_REG1, 0); 1170 if (status != SLJIT_SUCCESS) 1171 return status; 1172 #endif 1173 #else 1174 status = sljit_emit_ijump(compiler, 1175 SLJIT_CALL2, 1176 SLJIT_IMM, div ? SLJIT_FUNC_OFFSET(divide) : 1177 SLJIT_FUNC_OFFSET(modulus)); 1178 1179 #if BJ_AREG != SLJIT_RETURN_REG 1180 status = sljit_emit_op1(compiler, 1181 SLJIT_MOV, 1182 BJ_AREG, 0, 1183 SLJIT_RETURN_REG, 0); 1184 if (status != SLJIT_SUCCESS) 1185 return status; 1186 #endif 1187 #endif 1188 1189 return status; 1190 } 1191 1192 /* 1193 * Return true if pc is a "read from packet" instruction. 1194 * If length is not NULL and return value is true, *length will 1195 * be set to a safe length required to read a packet. 1196 */ 1197 static bool 1198 read_pkt_insn(const struct bpf_insn *pc, bpfjit_abc_length_t *length) 1199 { 1200 bool rv; 1201 bpfjit_abc_length_t width; 1202 1203 switch (BPF_CLASS(pc->code)) { 1204 default: 1205 rv = false; 1206 break; 1207 1208 case BPF_LD: 1209 rv = BPF_MODE(pc->code) == BPF_ABS || 1210 BPF_MODE(pc->code) == BPF_IND; 1211 if (rv) 1212 width = read_width(pc); 1213 break; 1214 1215 case BPF_LDX: 1216 rv = pc->code == (BPF_LDX|BPF_B|BPF_MSH); 1217 width = 1; 1218 break; 1219 } 1220 1221 if (rv && length != NULL) { 1222 /* 1223 * Values greater than UINT32_MAX will generate 1224 * unconditional "return 0". 1225 */ 1226 *length = (uint32_t)pc->k + width; 1227 } 1228 1229 return rv; 1230 } 1231 1232 static void 1233 optimize_init(struct bpfjit_insn_data *insn_dat, size_t insn_count) 1234 { 1235 size_t i; 1236 1237 for (i = 0; i < insn_count; i++) { 1238 SLIST_INIT(&insn_dat[i].bjumps); 1239 insn_dat[i].invalid = BJ_INIT_NOBITS; 1240 } 1241 } 1242 1243 /* 1244 * The function divides instructions into blocks. Destination of a jump 1245 * instruction starts a new block. BPF_RET and BPF_JMP instructions 1246 * terminate a block. Blocks are linear, that is, there are no jumps out 1247 * from the middle of a block and there are no jumps in to the middle of 1248 * a block. 1249 * 1250 * The function also sets bits in *initmask for memwords that 1251 * need to be initialized to zero. Note that this set should be empty 1252 * for any valid kernel filter program. 1253 */ 1254 static bool 1255 optimize_pass1(const bpf_ctx_t *bc, const struct bpf_insn *insns, 1256 struct bpfjit_insn_data *insn_dat, size_t insn_count, 1257 bpf_memword_init_t *initmask, bpfjit_hint_t *hints) 1258 { 1259 struct bpfjit_jump *jtf; 1260 size_t i; 1261 uint32_t jt, jf; 1262 bpfjit_abc_length_t length; 1263 bpf_memword_init_t invalid; /* borrowed from bpf_filter() */ 1264 bool unreachable; 1265 1266 const size_t memwords = GET_MEMWORDS(bc); 1267 1268 *hints = 0; 1269 *initmask = BJ_INIT_NOBITS; 1270 1271 unreachable = false; 1272 invalid = ~BJ_INIT_NOBITS; 1273 1274 for (i = 0; i < insn_count; i++) { 1275 if (!SLIST_EMPTY(&insn_dat[i].bjumps)) 1276 unreachable = false; 1277 insn_dat[i].unreachable = unreachable; 1278 1279 if (unreachable) 1280 continue; 1281 1282 invalid |= insn_dat[i].invalid; 1283 1284 if (read_pkt_insn(&insns[i], &length) && length > UINT32_MAX) 1285 unreachable = true; 1286 1287 switch (BPF_CLASS(insns[i].code)) { 1288 case BPF_RET: 1289 if (BPF_RVAL(insns[i].code) == BPF_A) 1290 *initmask |= invalid & BJ_INIT_ABIT; 1291 1292 unreachable = true; 1293 continue; 1294 1295 case BPF_LD: 1296 if (BPF_MODE(insns[i].code) == BPF_ABS) 1297 *hints |= BJ_HINT_ABS; 1298 1299 if (BPF_MODE(insns[i].code) == BPF_IND) { 1300 *hints |= BJ_HINT_IND | BJ_HINT_XREG; 1301 *initmask |= invalid & BJ_INIT_XBIT; 1302 } 1303 1304 if (BPF_MODE(insns[i].code) == BPF_MEM && 1305 (uint32_t)insns[i].k < memwords) { 1306 *initmask |= invalid & BJ_INIT_MBIT(insns[i].k); 1307 } 1308 1309 invalid &= ~BJ_INIT_ABIT; 1310 continue; 1311 1312 case BPF_LDX: 1313 *hints |= BJ_HINT_XREG | BJ_HINT_LDX; 1314 1315 if (BPF_MODE(insns[i].code) == BPF_MEM && 1316 (uint32_t)insns[i].k < memwords) { 1317 *initmask |= invalid & BJ_INIT_MBIT(insns[i].k); 1318 } 1319 1320 if (BPF_MODE(insns[i].code) == BPF_MSH && 1321 BPF_SIZE(insns[i].code) == BPF_B) { 1322 *hints |= BJ_HINT_MSH; 1323 } 1324 1325 invalid &= ~BJ_INIT_XBIT; 1326 continue; 1327 1328 case BPF_ST: 1329 *initmask |= invalid & BJ_INIT_ABIT; 1330 1331 if ((uint32_t)insns[i].k < memwords) 1332 invalid &= ~BJ_INIT_MBIT(insns[i].k); 1333 1334 continue; 1335 1336 case BPF_STX: 1337 *hints |= BJ_HINT_XREG; 1338 *initmask |= invalid & BJ_INIT_XBIT; 1339 1340 if ((uint32_t)insns[i].k < memwords) 1341 invalid &= ~BJ_INIT_MBIT(insns[i].k); 1342 1343 continue; 1344 1345 case BPF_ALU: 1346 *initmask |= invalid & BJ_INIT_ABIT; 1347 1348 if (insns[i].code != (BPF_ALU|BPF_NEG) && 1349 BPF_SRC(insns[i].code) == BPF_X) { 1350 *hints |= BJ_HINT_XREG; 1351 *initmask |= invalid & BJ_INIT_XBIT; 1352 } 1353 1354 invalid &= ~BJ_INIT_ABIT; 1355 continue; 1356 1357 case BPF_MISC: 1358 switch (BPF_MISCOP(insns[i].code)) { 1359 case BPF_TAX: // X <- A 1360 *hints |= BJ_HINT_XREG; 1361 *initmask |= invalid & BJ_INIT_ABIT; 1362 invalid &= ~BJ_INIT_XBIT; 1363 continue; 1364 1365 case BPF_TXA: // A <- X 1366 *hints |= BJ_HINT_XREG; 1367 *initmask |= invalid & BJ_INIT_XBIT; 1368 invalid &= ~BJ_INIT_ABIT; 1369 continue; 1370 1371 case BPF_COPX: 1372 *hints |= BJ_HINT_XREG | BJ_HINT_COPX; 1373 /* FALLTHROUGH */ 1374 1375 case BPF_COP: 1376 *hints |= BJ_HINT_COP; 1377 *initmask |= invalid & BJ_INIT_ABIT; 1378 invalid &= ~BJ_INIT_ABIT; 1379 continue; 1380 } 1381 1382 continue; 1383 1384 case BPF_JMP: 1385 /* Initialize abc_length for ABC pass. */ 1386 insn_dat[i].u.jdata.abc_length = MAX_ABC_LENGTH; 1387 1388 if (BPF_OP(insns[i].code) == BPF_JA) { 1389 jt = jf = insns[i].k; 1390 } else { 1391 jt = insns[i].jt; 1392 jf = insns[i].jf; 1393 } 1394 1395 if (jt >= insn_count - (i + 1) || 1396 jf >= insn_count - (i + 1)) { 1397 return false; 1398 } 1399 1400 if (jt > 0 && jf > 0) 1401 unreachable = true; 1402 1403 jt += i + 1; 1404 jf += i + 1; 1405 1406 jtf = insn_dat[i].u.jdata.jtf; 1407 1408 jtf[0].jdata = &insn_dat[i].u.jdata; 1409 SLIST_INSERT_HEAD(&insn_dat[jt].bjumps, 1410 &jtf[0], entries); 1411 1412 if (jf != jt) { 1413 jtf[1].jdata = &insn_dat[i].u.jdata; 1414 SLIST_INSERT_HEAD(&insn_dat[jf].bjumps, 1415 &jtf[1], entries); 1416 } 1417 1418 insn_dat[jf].invalid |= invalid; 1419 insn_dat[jt].invalid |= invalid; 1420 invalid = 0; 1421 1422 continue; 1423 } 1424 } 1425 1426 return true; 1427 } 1428 1429 /* 1430 * Array Bounds Check Elimination (ABC) pass. 1431 */ 1432 static void 1433 optimize_pass2(const bpf_ctx_t *bc, const struct bpf_insn *insns, 1434 struct bpfjit_insn_data *insn_dat, size_t insn_count) 1435 { 1436 struct bpfjit_jump *jmp; 1437 const struct bpf_insn *pc; 1438 struct bpfjit_insn_data *pd; 1439 size_t i; 1440 bpfjit_abc_length_t length, abc_length = 0; 1441 1442 const size_t extwords = GET_EXTWORDS(bc); 1443 1444 for (i = insn_count; i != 0; i--) { 1445 pc = &insns[i-1]; 1446 pd = &insn_dat[i-1]; 1447 1448 if (pd->unreachable) 1449 continue; 1450 1451 switch (BPF_CLASS(pc->code)) { 1452 case BPF_RET: 1453 /* 1454 * It's quite common for bpf programs to 1455 * check packet bytes in increasing order 1456 * and return zero if bytes don't match 1457 * specified critetion. Such programs disable 1458 * ABC optimization completely because for 1459 * every jump there is a branch with no read 1460 * instruction. 1461 * With no side effects, BPF_STMT(BPF_RET+BPF_K, 0) 1462 * is indistinguishable from out-of-bound load. 1463 * Therefore, abc_length can be set to 1464 * MAX_ABC_LENGTH and enable ABC for many 1465 * bpf programs. 1466 * If this optimization encounters any 1467 * instruction with a side effect, it will 1468 * reset abc_length. 1469 */ 1470 if (BPF_RVAL(pc->code) == BPF_K && pc->k == 0) 1471 abc_length = MAX_ABC_LENGTH; 1472 else 1473 abc_length = 0; 1474 break; 1475 1476 case BPF_MISC: 1477 if (BPF_MISCOP(pc->code) == BPF_COP || 1478 BPF_MISCOP(pc->code) == BPF_COPX) { 1479 /* COP instructions can have side effects. */ 1480 abc_length = 0; 1481 } 1482 break; 1483 1484 case BPF_ST: 1485 case BPF_STX: 1486 if (extwords != 0) { 1487 /* Write to memory is visible after a call. */ 1488 abc_length = 0; 1489 } 1490 break; 1491 1492 case BPF_JMP: 1493 abc_length = pd->u.jdata.abc_length; 1494 break; 1495 1496 default: 1497 if (read_pkt_insn(pc, &length)) { 1498 if (abc_length < length) 1499 abc_length = length; 1500 pd->u.rdata.abc_length = abc_length; 1501 } 1502 break; 1503 } 1504 1505 SLIST_FOREACH(jmp, &pd->bjumps, entries) { 1506 if (jmp->jdata->abc_length > abc_length) 1507 jmp->jdata->abc_length = abc_length; 1508 } 1509 } 1510 } 1511 1512 static void 1513 optimize_pass3(const struct bpf_insn *insns, 1514 struct bpfjit_insn_data *insn_dat, size_t insn_count) 1515 { 1516 struct bpfjit_jump *jmp; 1517 size_t i; 1518 bpfjit_abc_length_t checked_length = 0; 1519 1520 for (i = 0; i < insn_count; i++) { 1521 if (insn_dat[i].unreachable) 1522 continue; 1523 1524 SLIST_FOREACH(jmp, &insn_dat[i].bjumps, entries) { 1525 if (jmp->jdata->checked_length < checked_length) 1526 checked_length = jmp->jdata->checked_length; 1527 } 1528 1529 if (BPF_CLASS(insns[i].code) == BPF_JMP) { 1530 insn_dat[i].u.jdata.checked_length = checked_length; 1531 } else if (read_pkt_insn(&insns[i], NULL)) { 1532 struct bpfjit_read_pkt_data *rdata = 1533 &insn_dat[i].u.rdata; 1534 rdata->check_length = 0; 1535 if (checked_length < rdata->abc_length) { 1536 checked_length = rdata->abc_length; 1537 rdata->check_length = checked_length; 1538 } 1539 } 1540 } 1541 } 1542 1543 static bool 1544 optimize(const bpf_ctx_t *bc, const struct bpf_insn *insns, 1545 struct bpfjit_insn_data *insn_dat, size_t insn_count, 1546 bpf_memword_init_t *initmask, bpfjit_hint_t *hints) 1547 { 1548 1549 optimize_init(insn_dat, insn_count); 1550 1551 if (!optimize_pass1(bc, insns, insn_dat, insn_count, initmask, hints)) 1552 return false; 1553 1554 optimize_pass2(bc, insns, insn_dat, insn_count); 1555 optimize_pass3(insns, insn_dat, insn_count); 1556 1557 return true; 1558 } 1559 1560 /* 1561 * Convert BPF_ALU operations except BPF_NEG and BPF_DIV to sljit operation. 1562 */ 1563 static int 1564 bpf_alu_to_sljit_op(const struct bpf_insn *pc) 1565 { 1566 1567 /* 1568 * Note: all supported 64bit arches have 32bit multiply 1569 * instruction so SLJIT_INT_OP doesn't have any overhead. 1570 */ 1571 switch (BPF_OP(pc->code)) { 1572 case BPF_ADD: return SLJIT_ADD; 1573 case BPF_SUB: return SLJIT_SUB; 1574 case BPF_MUL: return SLJIT_MUL|SLJIT_INT_OP; 1575 case BPF_OR: return SLJIT_OR; 1576 case BPF_XOR: return SLJIT_XOR; 1577 case BPF_AND: return SLJIT_AND; 1578 case BPF_LSH: return SLJIT_SHL; 1579 case BPF_RSH: return SLJIT_LSHR|SLJIT_INT_OP; 1580 default: 1581 BJ_ASSERT(false); 1582 return 0; 1583 } 1584 } 1585 1586 /* 1587 * Convert BPF_JMP operations except BPF_JA to sljit condition. 1588 */ 1589 static int 1590 bpf_jmp_to_sljit_cond(const struct bpf_insn *pc, bool negate) 1591 { 1592 /* 1593 * Note: all supported 64bit arches have 32bit comparison 1594 * instructions so SLJIT_INT_OP doesn't have any overhead. 1595 */ 1596 int rv = SLJIT_INT_OP; 1597 1598 switch (BPF_OP(pc->code)) { 1599 case BPF_JGT: 1600 rv |= negate ? SLJIT_C_LESS_EQUAL : SLJIT_C_GREATER; 1601 break; 1602 case BPF_JGE: 1603 rv |= negate ? SLJIT_C_LESS : SLJIT_C_GREATER_EQUAL; 1604 break; 1605 case BPF_JEQ: 1606 rv |= negate ? SLJIT_C_NOT_EQUAL : SLJIT_C_EQUAL; 1607 break; 1608 case BPF_JSET: 1609 rv |= negate ? SLJIT_C_EQUAL : SLJIT_C_NOT_EQUAL; 1610 break; 1611 default: 1612 BJ_ASSERT(false); 1613 } 1614 1615 return rv; 1616 } 1617 1618 /* 1619 * Convert BPF_K and BPF_X to sljit register. 1620 */ 1621 static int 1622 kx_to_reg(const struct bpf_insn *pc) 1623 { 1624 1625 switch (BPF_SRC(pc->code)) { 1626 case BPF_K: return SLJIT_IMM; 1627 case BPF_X: return BJ_XREG; 1628 default: 1629 BJ_ASSERT(false); 1630 return 0; 1631 } 1632 } 1633 1634 static sljit_sw 1635 kx_to_reg_arg(const struct bpf_insn *pc) 1636 { 1637 1638 switch (BPF_SRC(pc->code)) { 1639 case BPF_K: return (uint32_t)pc->k; /* SLJIT_IMM, pc->k, */ 1640 case BPF_X: return 0; /* BJ_XREG, 0, */ 1641 default: 1642 BJ_ASSERT(false); 1643 return 0; 1644 } 1645 } 1646 1647 static bool 1648 generate_insn_code(struct sljit_compiler *compiler, bpfjit_hint_t hints, 1649 const bpf_ctx_t *bc, const struct bpf_insn *insns, 1650 struct bpfjit_insn_data *insn_dat, size_t insn_count) 1651 { 1652 /* a list of jumps to out-of-bound return from a generated function */ 1653 struct sljit_jump **ret0; 1654 size_t ret0_size, ret0_maxsize; 1655 1656 struct sljit_jump *jump; 1657 struct sljit_label *label; 1658 const struct bpf_insn *pc; 1659 struct bpfjit_jump *bjump, *jtf; 1660 struct sljit_jump *to_mchain_jump; 1661 1662 size_t i; 1663 int status; 1664 int branching, negate; 1665 unsigned int rval, mode, src, op; 1666 uint32_t jt, jf; 1667 1668 bool unconditional_ret; 1669 bool rv; 1670 1671 const size_t extwords = GET_EXTWORDS(bc); 1672 const size_t memwords = GET_MEMWORDS(bc); 1673 1674 ret0 = NULL; 1675 rv = false; 1676 1677 ret0_size = 0; 1678 ret0_maxsize = 64; 1679 ret0 = BJ_ALLOC(ret0_maxsize * sizeof(ret0[0])); 1680 if (ret0 == NULL) 1681 goto fail; 1682 1683 /* reset sjump members of jdata */ 1684 for (i = 0; i < insn_count; i++) { 1685 if (insn_dat[i].unreachable || 1686 BPF_CLASS(insns[i].code) != BPF_JMP) { 1687 continue; 1688 } 1689 1690 jtf = insn_dat[i].u.jdata.jtf; 1691 jtf[0].sjump = jtf[1].sjump = NULL; 1692 } 1693 1694 /* main loop */ 1695 for (i = 0; i < insn_count; i++) { 1696 if (insn_dat[i].unreachable) 1697 continue; 1698 1699 /* 1700 * Resolve jumps to the current insn. 1701 */ 1702 label = NULL; 1703 SLIST_FOREACH(bjump, &insn_dat[i].bjumps, entries) { 1704 if (bjump->sjump != NULL) { 1705 if (label == NULL) 1706 label = sljit_emit_label(compiler); 1707 if (label == NULL) 1708 goto fail; 1709 sljit_set_label(bjump->sjump, label); 1710 } 1711 } 1712 1713 to_mchain_jump = NULL; 1714 unconditional_ret = false; 1715 1716 if (read_pkt_insn(&insns[i], NULL)) { 1717 if (insn_dat[i].u.rdata.check_length > UINT32_MAX) { 1718 /* Jump to "return 0" unconditionally. */ 1719 unconditional_ret = true; 1720 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1721 if (jump == NULL) 1722 goto fail; 1723 if (!append_jump(jump, &ret0, 1724 &ret0_size, &ret0_maxsize)) 1725 goto fail; 1726 } else if (insn_dat[i].u.rdata.check_length > 0) { 1727 /* if (buflen < check_length) return 0; */ 1728 jump = sljit_emit_cmp(compiler, 1729 SLJIT_C_LESS, 1730 BJ_BUFLEN, 0, 1731 SLJIT_IMM, 1732 insn_dat[i].u.rdata.check_length); 1733 if (jump == NULL) 1734 goto fail; 1735 #ifdef _KERNEL 1736 to_mchain_jump = jump; 1737 #else 1738 if (!append_jump(jump, &ret0, 1739 &ret0_size, &ret0_maxsize)) 1740 goto fail; 1741 #endif 1742 } 1743 } 1744 1745 pc = &insns[i]; 1746 switch (BPF_CLASS(pc->code)) { 1747 1748 default: 1749 goto fail; 1750 1751 case BPF_LD: 1752 /* BPF_LD+BPF_IMM A <- k */ 1753 if (pc->code == (BPF_LD|BPF_IMM)) { 1754 status = sljit_emit_op1(compiler, 1755 SLJIT_MOV, 1756 BJ_AREG, 0, 1757 SLJIT_IMM, (uint32_t)pc->k); 1758 if (status != SLJIT_SUCCESS) 1759 goto fail; 1760 1761 continue; 1762 } 1763 1764 /* BPF_LD+BPF_MEM A <- M[k] */ 1765 if (pc->code == (BPF_LD|BPF_MEM)) { 1766 if ((uint32_t)pc->k >= memwords) 1767 goto fail; 1768 status = emit_memload(compiler, 1769 BJ_AREG, pc->k, extwords); 1770 if (status != SLJIT_SUCCESS) 1771 goto fail; 1772 1773 continue; 1774 } 1775 1776 /* BPF_LD+BPF_W+BPF_LEN A <- len */ 1777 if (pc->code == (BPF_LD|BPF_W|BPF_LEN)) { 1778 status = sljit_emit_op1(compiler, 1779 SLJIT_MOV, /* size_t source */ 1780 BJ_AREG, 0, 1781 SLJIT_MEM1(BJ_ARGS), 1782 offsetof(struct bpf_args, wirelen)); 1783 if (status != SLJIT_SUCCESS) 1784 goto fail; 1785 1786 continue; 1787 } 1788 1789 mode = BPF_MODE(pc->code); 1790 if (mode != BPF_ABS && mode != BPF_IND) 1791 goto fail; 1792 1793 if (unconditional_ret) 1794 continue; 1795 1796 status = emit_pkt_read(compiler, hints, pc, 1797 to_mchain_jump, &ret0, &ret0_size, &ret0_maxsize); 1798 if (status != SLJIT_SUCCESS) 1799 goto fail; 1800 1801 continue; 1802 1803 case BPF_LDX: 1804 mode = BPF_MODE(pc->code); 1805 1806 /* BPF_LDX+BPF_W+BPF_IMM X <- k */ 1807 if (mode == BPF_IMM) { 1808 if (BPF_SIZE(pc->code) != BPF_W) 1809 goto fail; 1810 status = sljit_emit_op1(compiler, 1811 SLJIT_MOV, 1812 BJ_XREG, 0, 1813 SLJIT_IMM, (uint32_t)pc->k); 1814 if (status != SLJIT_SUCCESS) 1815 goto fail; 1816 1817 continue; 1818 } 1819 1820 /* BPF_LDX+BPF_W+BPF_LEN X <- len */ 1821 if (mode == BPF_LEN) { 1822 if (BPF_SIZE(pc->code) != BPF_W) 1823 goto fail; 1824 status = sljit_emit_op1(compiler, 1825 SLJIT_MOV, /* size_t source */ 1826 BJ_XREG, 0, 1827 SLJIT_MEM1(BJ_ARGS), 1828 offsetof(struct bpf_args, wirelen)); 1829 if (status != SLJIT_SUCCESS) 1830 goto fail; 1831 1832 continue; 1833 } 1834 1835 /* BPF_LDX+BPF_W+BPF_MEM X <- M[k] */ 1836 if (mode == BPF_MEM) { 1837 if (BPF_SIZE(pc->code) != BPF_W) 1838 goto fail; 1839 if ((uint32_t)pc->k >= memwords) 1840 goto fail; 1841 status = emit_memload(compiler, 1842 BJ_XREG, pc->k, extwords); 1843 if (status != SLJIT_SUCCESS) 1844 goto fail; 1845 1846 continue; 1847 } 1848 1849 /* BPF_LDX+BPF_B+BPF_MSH X <- 4*(P[k:1]&0xf) */ 1850 if (mode != BPF_MSH || BPF_SIZE(pc->code) != BPF_B) 1851 goto fail; 1852 1853 if (unconditional_ret) 1854 continue; 1855 1856 status = emit_msh(compiler, hints, pc, 1857 to_mchain_jump, &ret0, &ret0_size, &ret0_maxsize); 1858 if (status != SLJIT_SUCCESS) 1859 goto fail; 1860 1861 continue; 1862 1863 case BPF_ST: 1864 if (pc->code != BPF_ST || 1865 (uint32_t)pc->k >= memwords) { 1866 goto fail; 1867 } 1868 1869 status = emit_memstore(compiler, 1870 BJ_AREG, pc->k, extwords); 1871 if (status != SLJIT_SUCCESS) 1872 goto fail; 1873 1874 continue; 1875 1876 case BPF_STX: 1877 if (pc->code != BPF_STX || 1878 (uint32_t)pc->k >= memwords) { 1879 goto fail; 1880 } 1881 1882 status = emit_memstore(compiler, 1883 BJ_XREG, pc->k, extwords); 1884 if (status != SLJIT_SUCCESS) 1885 goto fail; 1886 1887 continue; 1888 1889 case BPF_ALU: 1890 if (pc->code == (BPF_ALU|BPF_NEG)) { 1891 status = sljit_emit_op1(compiler, 1892 SLJIT_NEG, 1893 BJ_AREG, 0, 1894 BJ_AREG, 0); 1895 if (status != SLJIT_SUCCESS) 1896 goto fail; 1897 1898 continue; 1899 } 1900 1901 op = BPF_OP(pc->code); 1902 if (op != BPF_DIV && op != BPF_MOD) { 1903 status = sljit_emit_op2(compiler, 1904 bpf_alu_to_sljit_op(pc), 1905 BJ_AREG, 0, 1906 BJ_AREG, 0, 1907 kx_to_reg(pc), kx_to_reg_arg(pc)); 1908 if (status != SLJIT_SUCCESS) 1909 goto fail; 1910 1911 continue; 1912 } 1913 1914 /* BPF_DIV/BPF_MOD */ 1915 1916 src = BPF_SRC(pc->code); 1917 if (src != BPF_X && src != BPF_K) 1918 goto fail; 1919 1920 /* division by zero? */ 1921 if (src == BPF_X) { 1922 jump = sljit_emit_cmp(compiler, 1923 SLJIT_C_EQUAL|SLJIT_INT_OP, 1924 BJ_XREG, 0, 1925 SLJIT_IMM, 0); 1926 if (jump == NULL) 1927 goto fail; 1928 if (!append_jump(jump, &ret0, 1929 &ret0_size, &ret0_maxsize)) 1930 goto fail; 1931 } else if (pc->k == 0) { 1932 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 1933 if (jump == NULL) 1934 goto fail; 1935 if (!append_jump(jump, &ret0, 1936 &ret0_size, &ret0_maxsize)) 1937 goto fail; 1938 } 1939 1940 if (src == BPF_X) { 1941 status = emit_moddiv(op == BPF_DIV, 1942 compiler, BJ_XREG, 0); 1943 if (status != SLJIT_SUCCESS) 1944 goto fail; 1945 } else if (pc->k != 0) { 1946 /* XXX: We can do better here for MOD */ 1947 if ((pc->k & (pc->k - 1)) || op == BPF_MOD) { 1948 status = emit_moddiv(op == BPF_DIV, 1949 compiler, SLJIT_IMM, (uint32_t)pc->k); 1950 } else { 1951 status = emit_pow2_division(compiler, 1952 (uint32_t)pc->k); 1953 } 1954 if (status != SLJIT_SUCCESS) 1955 goto fail; 1956 } 1957 1958 continue; 1959 1960 case BPF_JMP: 1961 op = BPF_OP(pc->code); 1962 if (op == BPF_JA) { 1963 jt = jf = pc->k; 1964 } else { 1965 jt = pc->jt; 1966 jf = pc->jf; 1967 } 1968 1969 negate = (jt == 0) ? 1 : 0; 1970 branching = (jt == jf) ? 0 : 1; 1971 jtf = insn_dat[i].u.jdata.jtf; 1972 1973 if (branching) { 1974 if (op != BPF_JSET) { 1975 jump = sljit_emit_cmp(compiler, 1976 bpf_jmp_to_sljit_cond(pc, negate), 1977 BJ_AREG, 0, 1978 kx_to_reg(pc), kx_to_reg_arg(pc)); 1979 } else { 1980 status = sljit_emit_op2(compiler, 1981 SLJIT_AND, 1982 BJ_TMP1REG, 0, 1983 BJ_AREG, 0, 1984 kx_to_reg(pc), kx_to_reg_arg(pc)); 1985 if (status != SLJIT_SUCCESS) 1986 goto fail; 1987 1988 jump = sljit_emit_cmp(compiler, 1989 bpf_jmp_to_sljit_cond(pc, negate), 1990 BJ_TMP1REG, 0, 1991 SLJIT_IMM, 0); 1992 } 1993 1994 if (jump == NULL) 1995 goto fail; 1996 1997 BJ_ASSERT(jtf[negate].sjump == NULL); 1998 jtf[negate].sjump = jump; 1999 } 2000 2001 if (!branching || (jt != 0 && jf != 0)) { 2002 jump = sljit_emit_jump(compiler, SLJIT_JUMP); 2003 if (jump == NULL) 2004 goto fail; 2005 2006 BJ_ASSERT(jtf[branching].sjump == NULL); 2007 jtf[branching].sjump = jump; 2008 } 2009 2010 continue; 2011 2012 case BPF_RET: 2013 rval = BPF_RVAL(pc->code); 2014 if (rval == BPF_X) 2015 goto fail; 2016 2017 /* BPF_RET+BPF_K accept k bytes */ 2018 if (rval == BPF_K) { 2019 status = sljit_emit_return(compiler, 2020 SLJIT_MOV_UI, 2021 SLJIT_IMM, (uint32_t)pc->k); 2022 if (status != SLJIT_SUCCESS) 2023 goto fail; 2024 } 2025 2026 /* BPF_RET+BPF_A accept A bytes */ 2027 if (rval == BPF_A) { 2028 status = sljit_emit_return(compiler, 2029 SLJIT_MOV_UI, 2030 BJ_AREG, 0); 2031 if (status != SLJIT_SUCCESS) 2032 goto fail; 2033 } 2034 2035 continue; 2036 2037 case BPF_MISC: 2038 switch (BPF_MISCOP(pc->code)) { 2039 case BPF_TAX: 2040 status = sljit_emit_op1(compiler, 2041 SLJIT_MOV_UI, 2042 BJ_XREG, 0, 2043 BJ_AREG, 0); 2044 if (status != SLJIT_SUCCESS) 2045 goto fail; 2046 2047 continue; 2048 2049 case BPF_TXA: 2050 status = sljit_emit_op1(compiler, 2051 SLJIT_MOV, 2052 BJ_AREG, 0, 2053 BJ_XREG, 0); 2054 if (status != SLJIT_SUCCESS) 2055 goto fail; 2056 2057 continue; 2058 2059 case BPF_COP: 2060 case BPF_COPX: 2061 if (bc == NULL || bc->copfuncs == NULL) 2062 goto fail; 2063 if (BPF_MISCOP(pc->code) == BPF_COP && 2064 (uint32_t)pc->k >= bc->nfuncs) { 2065 goto fail; 2066 } 2067 2068 status = emit_cop(compiler, hints, bc, pc, 2069 &ret0, &ret0_size, &ret0_maxsize); 2070 if (status != SLJIT_SUCCESS) 2071 goto fail; 2072 2073 continue; 2074 } 2075 2076 goto fail; 2077 } /* switch */ 2078 } /* main loop */ 2079 2080 BJ_ASSERT(ret0_size <= ret0_maxsize); 2081 2082 if (ret0_size > 0) { 2083 label = sljit_emit_label(compiler); 2084 if (label == NULL) 2085 goto fail; 2086 for (i = 0; i < ret0_size; i++) 2087 sljit_set_label(ret0[i], label); 2088 } 2089 2090 status = sljit_emit_return(compiler, 2091 SLJIT_MOV_UI, 2092 SLJIT_IMM, 0); 2093 if (status != SLJIT_SUCCESS) 2094 goto fail; 2095 2096 rv = true; 2097 2098 fail: 2099 if (ret0 != NULL) 2100 BJ_FREE(ret0, ret0_maxsize * sizeof(ret0[0])); 2101 2102 return rv; 2103 } 2104 2105 bpfjit_func_t 2106 bpfjit_generate_code(const bpf_ctx_t *bc, 2107 const struct bpf_insn *insns, size_t insn_count) 2108 { 2109 void *rv; 2110 struct sljit_compiler *compiler; 2111 2112 size_t i; 2113 int status; 2114 2115 /* optimization related */ 2116 bpf_memword_init_t initmask; 2117 bpfjit_hint_t hints; 2118 2119 /* memory store location for initial zero initialization */ 2120 sljit_si mem_reg; 2121 sljit_sw mem_off; 2122 2123 struct bpfjit_insn_data *insn_dat; 2124 2125 const size_t extwords = GET_EXTWORDS(bc); 2126 const size_t memwords = GET_MEMWORDS(bc); 2127 const bpf_memword_init_t preinited = extwords ? bc->preinited : 0; 2128 2129 rv = NULL; 2130 compiler = NULL; 2131 insn_dat = NULL; 2132 2133 if (memwords > MAX_MEMWORDS) 2134 goto fail; 2135 2136 if (insn_count == 0 || insn_count > SIZE_MAX / sizeof(insn_dat[0])) 2137 goto fail; 2138 2139 insn_dat = BJ_ALLOC(insn_count * sizeof(insn_dat[0])); 2140 if (insn_dat == NULL) 2141 goto fail; 2142 2143 if (!optimize(bc, insns, insn_dat, insn_count, &initmask, &hints)) 2144 goto fail; 2145 2146 compiler = sljit_create_compiler(); 2147 if (compiler == NULL) 2148 goto fail; 2149 2150 #if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE 2151 sljit_compiler_verbose(compiler, stderr); 2152 #endif 2153 2154 status = sljit_emit_enter(compiler, 2155 2, nscratches(hints), nsaveds(hints), sizeof(struct bpfjit_stack)); 2156 if (status != SLJIT_SUCCESS) 2157 goto fail; 2158 2159 if (hints & BJ_HINT_COP) { 2160 /* save ctx argument */ 2161 status = sljit_emit_op1(compiler, 2162 SLJIT_MOV_P, 2163 SLJIT_MEM1(SLJIT_LOCALS_REG), 2164 offsetof(struct bpfjit_stack, ctx), 2165 BJ_CTX_ARG, 0); 2166 if (status != SLJIT_SUCCESS) 2167 goto fail; 2168 } 2169 2170 if (extwords == 0) { 2171 mem_reg = SLJIT_MEM1(SLJIT_LOCALS_REG); 2172 mem_off = offsetof(struct bpfjit_stack, mem); 2173 } else { 2174 /* copy "mem" argument from bpf_args to bpfjit_stack */ 2175 status = sljit_emit_op1(compiler, 2176 SLJIT_MOV_P, 2177 BJ_TMP1REG, 0, 2178 SLJIT_MEM1(BJ_ARGS), offsetof(struct bpf_args, mem)); 2179 if (status != SLJIT_SUCCESS) 2180 goto fail; 2181 2182 status = sljit_emit_op1(compiler, 2183 SLJIT_MOV_P, 2184 SLJIT_MEM1(SLJIT_LOCALS_REG), 2185 offsetof(struct bpfjit_stack, extmem), 2186 BJ_TMP1REG, 0); 2187 if (status != SLJIT_SUCCESS) 2188 goto fail; 2189 2190 mem_reg = SLJIT_MEM1(BJ_TMP1REG); 2191 mem_off = 0; 2192 } 2193 2194 /* 2195 * Exclude pre-initialised external memory words but keep 2196 * initialization statuses of A and X registers in case 2197 * bc->preinited wrongly sets those two bits. 2198 */ 2199 initmask &= ~preinited | BJ_INIT_ABIT | BJ_INIT_XBIT; 2200 2201 #if defined(_KERNEL) 2202 /* bpf_filter() checks initialization of memwords. */ 2203 BJ_ASSERT((initmask & (BJ_INIT_MBIT(memwords) - 1)) == 0); 2204 #endif 2205 for (i = 0; i < memwords; i++) { 2206 if (initmask & BJ_INIT_MBIT(i)) { 2207 /* M[i] = 0; */ 2208 status = sljit_emit_op1(compiler, 2209 SLJIT_MOV_UI, 2210 mem_reg, mem_off + i * sizeof(uint32_t), 2211 SLJIT_IMM, 0); 2212 if (status != SLJIT_SUCCESS) 2213 goto fail; 2214 } 2215 } 2216 2217 if (initmask & BJ_INIT_ABIT) { 2218 /* A = 0; */ 2219 status = sljit_emit_op1(compiler, 2220 SLJIT_MOV, 2221 BJ_AREG, 0, 2222 SLJIT_IMM, 0); 2223 if (status != SLJIT_SUCCESS) 2224 goto fail; 2225 } 2226 2227 if (initmask & BJ_INIT_XBIT) { 2228 /* X = 0; */ 2229 status = sljit_emit_op1(compiler, 2230 SLJIT_MOV, 2231 BJ_XREG, 0, 2232 SLJIT_IMM, 0); 2233 if (status != SLJIT_SUCCESS) 2234 goto fail; 2235 } 2236 2237 status = load_buf_buflen(compiler); 2238 if (status != SLJIT_SUCCESS) 2239 goto fail; 2240 2241 if (!generate_insn_code(compiler, hints, 2242 bc, insns, insn_dat, insn_count)) { 2243 goto fail; 2244 } 2245 2246 rv = sljit_generate_code(compiler); 2247 2248 fail: 2249 if (compiler != NULL) 2250 sljit_free_compiler(compiler); 2251 2252 if (insn_dat != NULL) 2253 BJ_FREE(insn_dat, insn_count * sizeof(insn_dat[0])); 2254 2255 return (bpfjit_func_t)rv; 2256 } 2257 2258 void 2259 bpfjit_free_code(bpfjit_func_t code) 2260 { 2261 2262 sljit_free_code((void *)code); 2263 } 2264
Indexes created Fri Sep 26 20:09:58 GMT 2025