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