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