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