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