arch/mips/net/ebpf_jit.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Just-In-Time compiler for eBPF filters on MIPS
   4  *
   5  * Copyright (c) 2017 Cavium, Inc.
   6  *
   7  * Based on code from:
   8  *
   9  * Copyright (c) 2014 Imagination Technologies Ltd.
  10  * Author: Markos Chandras <markos.chandras@imgtec.com>
  11  */
  12
  13 #include <linux/bitops.h>
  14 #include <linux/errno.h>
  15 #include <linux/filter.h>
  16 #include <linux/bpf.h>
  17 #include <linux/slab.h>
  18 #include <asm/bitops.h>
  19 #include <asm/byteorder.h>
  20 #include <asm/cacheflush.h>
  21 #include <asm/cpu-features.h>
  22 #include <asm/isa-rev.h>
  23 #include <asm/uasm.h>
  24
  25 /* Registers used by JIT */
  26 #define MIPS_R_ZERO     0
  27 #define MIPS_R_AT       1
  28 #define MIPS_R_V0       2       /* BPF_R0 */
  29 #define MIPS_R_V1       3
  30 #define MIPS_R_A0       4       /* BPF_R1 */
  31 #define MIPS_R_A1       5       /* BPF_R2 */
  32 #define MIPS_R_A2       6       /* BPF_R3 */
  33 #define MIPS_R_A3       7       /* BPF_R4 */
  34 #define MIPS_R_A4       8       /* BPF_R5 */
  35 #define MIPS_R_T4       12      /* BPF_AX */
  36 #define MIPS_R_T5       13
  37 #define MIPS_R_T6       14
  38 #define MIPS_R_T7       15
  39 #define MIPS_R_S0       16      /* BPF_R6 */
  40 #define MIPS_R_S1       17      /* BPF_R7 */
  41 #define MIPS_R_S2       18      /* BPF_R8 */
  42 #define MIPS_R_S3       19      /* BPF_R9 */
  43 #define MIPS_R_S4       20      /* BPF_TCC */
  44 #define MIPS_R_S5       21
  45 #define MIPS_R_S6       22
  46 #define MIPS_R_S7       23
  47 #define MIPS_R_T8       24
  48 #define MIPS_R_T9       25
  49 #define MIPS_R_SP       29
  50 #define MIPS_R_RA       31
  51
  52 /* eBPF flags */
  53 #define EBPF_SAVE_S0    BIT(0)
  54 #define EBPF_SAVE_S1    BIT(1)
  55 #define EBPF_SAVE_S2    BIT(2)
  56 #define EBPF_SAVE_S3    BIT(3)
  57 #define EBPF_SAVE_S4    BIT(4)
  58 #define EBPF_SAVE_RA    BIT(5)
  59 #define EBPF_SEEN_FP    BIT(6)
  60 #define EBPF_SEEN_TC    BIT(7)
  61 #define EBPF_TCC_IN_V1  BIT(8)
  62
  63 /*
  64  * For the mips64 ISA, we need to track the value range or type for
  65  * each JIT register.  The BPF machine requires zero extended 32-bit
  66  * values, but the mips64 ISA requires sign extended 32-bit values.
  67  * At each point in the BPF program we track the state of every
  68  * register so that we can zero extend or sign extend as the BPF
  69  * semantics require.
  70  */
  71 enum reg_val_type {
  72         /* uninitialized */
  73         REG_UNKNOWN,
  74         /* not known to be 32-bit compatible. */
  75         REG_64BIT,
  76         /* 32-bit compatible, no truncation needed for 64-bit ops. */
  77         REG_64BIT_32BIT,
  78         /* 32-bit compatible, need truncation for 64-bit ops. */
  79         REG_32BIT,
  80         /* 32-bit no sign/zero extension needed. */
  81         REG_32BIT_POS
  82 };
  83
  84 /*
  85  * high bit of offsets indicates if long branch conversion done at
  86  * this insn.
  87  */
  88 #define OFFSETS_B_CONV  BIT(31)
  89
  90 /**
  91  * struct jit_ctx - JIT context
  92  * @skf:                The sk_filter
  93  * @stack_size:         eBPF stack size
  94  * @idx:                Instruction index
  95  * @flags:              JIT flags
  96  * @offsets:            Instruction offsets
  97  * @target:             Memory location for the compiled filter
  98  * @reg_val_types       Packed enum reg_val_type for each register.
  99  */
 100 struct jit_ctx {
 101         const struct bpf_prog *skf;
 102         int stack_size;
 103         u32 idx;
 104         u32 flags;
 105         u32 *offsets;
 106         u32 *target;
 107         u64 *reg_val_types;
 108         unsigned int long_b_conversion:1;
 109         unsigned int gen_b_offsets:1;
 110         unsigned int use_bbit_insns:1;
 111 };
 112
 113 static void set_reg_val_type(u64 *rvt, int reg, enum reg_val_type type)
 114 {
 115         *rvt &= ~(7ull << (reg * 3));
 116         *rvt |= ((u64)type << (reg * 3));
 117 }
 118
 119 static enum reg_val_type get_reg_val_type(const struct jit_ctx *ctx,
 120                                           int index, int reg)
 121 {
 122         return (ctx->reg_val_types[index] >> (reg * 3)) & 7;
 123 }
 124
 125 /* Simply emit the instruction if the JIT memory space has been allocated */
 126 #define emit_instr_long(ctx, func64, func32, ...)               \
 127 do {                                                            \
 128         if ((ctx)->target != NULL) {                            \
 129                 u32 *p = &(ctx)->target[ctx->idx];              \
 130                 if (IS_ENABLED(CONFIG_64BIT))                   \
 131                         uasm_i_##func64(&p, ##__VA_ARGS__);     \
 132                 else                                            \
 133                         uasm_i_##func32(&p, ##__VA_ARGS__);     \
 134         }                                                       \
 135         (ctx)->idx++;                                           \
 136 } while (0)
 137
 138 #define emit_instr(ctx, func, ...)                              \
 139         emit_instr_long(ctx, func, func, ##__VA_ARGS__)
 140
 141 static unsigned int j_target(struct jit_ctx *ctx, int target_idx)
 142 {
 143         unsigned long target_va, base_va;
 144         unsigned int r;
 145
 146         if (!ctx->target)
 147                 return 0;
 148
 149         base_va = (unsigned long)ctx->target;
 150         target_va = base_va + (ctx->offsets[target_idx] & ~OFFSETS_B_CONV);
 151
 152         if ((base_va & ~0x0ffffffful) != (target_va & ~0x0ffffffful))
 153                 return (unsigned int)-1;
 154         r = target_va & 0x0ffffffful;
 155         return r;
 156 }
 157
 158 /* Compute the immediate value for PC-relative branches. */
 159 static u32 b_imm(unsigned int tgt, struct jit_ctx *ctx)
 160 {
 161         if (!ctx->gen_b_offsets)
 162                 return 0;
 163
 164         /*
 165          * We want a pc-relative branch.  tgt is the instruction offset
 166          * we want to jump to.
 167
 168          * Branch on MIPS:
 169          * I: target_offset <- sign_extend(offset)
 170          * I+1: PC += target_offset (delay slot)
 171          *
 172          * ctx->idx currently points to the branch instruction
 173          * but the offset is added to the delay slot so we need
 174          * to subtract 4.
 175          */
 176         return (ctx->offsets[tgt] & ~OFFSETS_B_CONV) -
 177                 (ctx->idx * 4) - 4;
 178 }
 179
 180 enum which_ebpf_reg {
 181         src_reg,
 182         src_reg_no_fp,
 183         dst_reg,
 184         dst_reg_fp_ok
 185 };
 186
 187 /*
 188  * For eBPF, the register mapping naturally falls out of the
 189  * requirements of eBPF and the MIPS n64 ABI.  We don't maintain a
 190  * separate frame pointer, so BPF_REG_10 relative accesses are
 191  * adjusted to be $sp relative.
 192  */
 193 static int ebpf_to_mips_reg(struct jit_ctx *ctx,
 194                             const struct bpf_insn *insn,
 195                             enum which_ebpf_reg w)
 196 {
 197         int ebpf_reg = (w == src_reg || w == src_reg_no_fp) ?
 198                 insn->src_reg : insn->dst_reg;
 199
 200         switch (ebpf_reg) {
 201         case BPF_REG_0:
 202                 return MIPS_R_V0;
 203         case BPF_REG_1:
 204                 return MIPS_R_A0;
 205         case BPF_REG_2:
 206                 return MIPS_R_A1;
 207         case BPF_REG_3:
 208                 return MIPS_R_A2;
 209         case BPF_REG_4:
 210                 return MIPS_R_A3;
 211         case BPF_REG_5:
 212                 return MIPS_R_A4;
 213         case BPF_REG_6:
 214                 ctx->flags |= EBPF_SAVE_S0;
 215                 return MIPS_R_S0;
 216         case BPF_REG_7:
 217                 ctx->flags |= EBPF_SAVE_S1;
 218                 return MIPS_R_S1;
 219         case BPF_REG_8:
 220                 ctx->flags |= EBPF_SAVE_S2;
 221                 return MIPS_R_S2;
 222         case BPF_REG_9:
 223                 ctx->flags |= EBPF_SAVE_S3;
 224                 return MIPS_R_S3;
 225         case BPF_REG_10:
 226                 if (w == dst_reg || w == src_reg_no_fp)
 227                         goto bad_reg;
 228                 ctx->flags |= EBPF_SEEN_FP;
 229                 /*
 230                  * Needs special handling, return something that
 231                  * cannot be clobbered just in case.
 232                  */
 233                 return MIPS_R_ZERO;
 234         case BPF_REG_AX:
 235                 return MIPS_R_T4;
 236         default:
 237 bad_reg:
 238                 WARN(1, "Illegal bpf reg: %d\n", ebpf_reg);
 239                 return -EINVAL;
 240         }
 241 }
 242 /*
 243  * eBPF stack frame will be something like:
 244  *
 245  *  Entry $sp ------>   +--------------------------------+
 246  *                      |   $ra  (optional)              |
 247  *                      +--------------------------------+
 248  *                      |   $s0  (optional)              |
 249  *                      +--------------------------------+
 250  *                      |   $s1  (optional)              |
 251  *                      +--------------------------------+
 252  *                      |   $s2  (optional)              |
 253  *                      +--------------------------------+
 254  *                      |   $s3  (optional)              |
 255  *                      +--------------------------------+
 256  *                      |   $s4  (optional)              |
 257  *                      +--------------------------------+
 258  *                      |   tmp-storage  (if $ra saved)  |
 259  * $sp + tmp_offset --> +--------------------------------+ <--BPF_REG_10
 260  *                      |   BPF_REG_10 relative storage  |
 261  *                      |    MAX_BPF_STACK (optional)    |
 262  *                      |      .                         |
 263  *                      |      .                         |
 264  *                      |      .                         |
 265  *     $sp -------->    +--------------------------------+
 266  *
 267  * If BPF_REG_10 is never referenced, then the MAX_BPF_STACK sized
 268  * area is not allocated.
 269  */
 270 static int gen_int_prologue(struct jit_ctx *ctx)
 271 {
 272         int stack_adjust = 0;
 273         int store_offset;
 274         int locals_size;
 275
 276         if (ctx->flags & EBPF_SAVE_RA)
 277                 /*
 278                  * If RA we are doing a function call and may need
 279                  * extra 8-byte tmp area.
 280                  */
 281                 stack_adjust += 2 * sizeof(long);
 282         if (ctx->flags & EBPF_SAVE_S0)
 283                 stack_adjust += sizeof(long);
 284         if (ctx->flags & EBPF_SAVE_S1)
 285                 stack_adjust += sizeof(long);
 286         if (ctx->flags & EBPF_SAVE_S2)
 287                 stack_adjust += sizeof(long);
 288         if (ctx->flags & EBPF_SAVE_S3)
 289                 stack_adjust += sizeof(long);
 290         if (ctx->flags & EBPF_SAVE_S4)
 291                 stack_adjust += sizeof(long);
 292
 293         BUILD_BUG_ON(MAX_BPF_STACK & 7);
 294         locals_size = (ctx->flags & EBPF_SEEN_FP) ? MAX_BPF_STACK : 0;
 295
 296         stack_adjust += locals_size;
 297
 298         ctx->stack_size = stack_adjust;
 299
 300         /*
 301          * First instruction initializes the tail call count (TCC).
 302          * On tail call we skip this instruction, and the TCC is
 303          * passed in $v1 from the caller.
 304          */
 305         emit_instr(ctx, addiu, MIPS_R_V1, MIPS_R_ZERO, MAX_TAIL_CALL_CNT);
 306         if (stack_adjust)
 307                 emit_instr_long(ctx, daddiu, addiu,
 308                                         MIPS_R_SP, MIPS_R_SP, -stack_adjust);
 309         else
 310                 return 0;
 311
 312         store_offset = stack_adjust - sizeof(long);
 313
 314         if (ctx->flags & EBPF_SAVE_RA) {
 315                 emit_instr_long(ctx, sd, sw,
 316                                         MIPS_R_RA, store_offset, MIPS_R_SP);
 317                 store_offset -= sizeof(long);
 318         }
 319         if (ctx->flags & EBPF_SAVE_S0) {
 320                 emit_instr_long(ctx, sd, sw,
 321                                         MIPS_R_S0, store_offset, MIPS_R_SP);
 322                 store_offset -= sizeof(long);
 323         }
 324         if (ctx->flags & EBPF_SAVE_S1) {
 325                 emit_instr_long(ctx, sd, sw,
 326                                         MIPS_R_S1, store_offset, MIPS_R_SP);
 327                 store_offset -= sizeof(long);
 328         }
 329         if (ctx->flags & EBPF_SAVE_S2) {
 330                 emit_instr_long(ctx, sd, sw,
 331                                         MIPS_R_S2, store_offset, MIPS_R_SP);
 332                 store_offset -= sizeof(long);
 333         }
 334         if (ctx->flags & EBPF_SAVE_S3) {
 335                 emit_instr_long(ctx, sd, sw,
 336                                         MIPS_R_S3, store_offset, MIPS_R_SP);
 337                 store_offset -= sizeof(long);
 338         }
 339         if (ctx->flags & EBPF_SAVE_S4) {
 340                 emit_instr_long(ctx, sd, sw,
 341                                         MIPS_R_S4, store_offset, MIPS_R_SP);
 342                 store_offset -= sizeof(long);
 343         }
 344
 345         if ((ctx->flags & EBPF_SEEN_TC) && !(ctx->flags & EBPF_TCC_IN_V1))
 346                 emit_instr_long(ctx, daddu, addu,
 347                                         MIPS_R_S4, MIPS_R_V1, MIPS_R_ZERO);
 348
 349         return 0;
 350 }
 351
 352 static int build_int_epilogue(struct jit_ctx *ctx, int dest_reg)
 353 {
 354         const struct bpf_prog *prog = ctx->skf;
 355         int stack_adjust = ctx->stack_size;
 356         int store_offset = stack_adjust - sizeof(long);
 357         enum reg_val_type td;
 358         int r0 = MIPS_R_V0;
 359
 360         if (dest_reg == MIPS_R_RA) {
 361                 /* Don't let zero extended value escape. */
 362                 td = get_reg_val_type(ctx, prog->len, BPF_REG_0);
 363                 if (td == REG_64BIT)
 364                         emit_instr(ctx, sll, r0, r0, 0);
 365         }
 366
 367         if (ctx->flags & EBPF_SAVE_RA) {
 368                 emit_instr_long(ctx, ld, lw,
 369                                         MIPS_R_RA, store_offset, MIPS_R_SP);
 370                 store_offset -= sizeof(long);
 371         }
 372         if (ctx->flags & EBPF_SAVE_S0) {
 373                 emit_instr_long(ctx, ld, lw,
 374                                         MIPS_R_S0, store_offset, MIPS_R_SP);
 375                 store_offset -= sizeof(long);
 376         }
 377         if (ctx->flags & EBPF_SAVE_S1) {
 378                 emit_instr_long(ctx, ld, lw,
 379                                         MIPS_R_S1, store_offset, MIPS_R_SP);
 380                 store_offset -= sizeof(long);
 381         }
 382         if (ctx->flags & EBPF_SAVE_S2) {
 383                 emit_instr_long(ctx, ld, lw,
 384                                 MIPS_R_S2, store_offset, MIPS_R_SP);
 385                 store_offset -= sizeof(long);
 386         }
 387         if (ctx->flags & EBPF_SAVE_S3) {
 388                 emit_instr_long(ctx, ld, lw,
 389                                         MIPS_R_S3, store_offset, MIPS_R_SP);
 390                 store_offset -= sizeof(long);
 391         }
 392         if (ctx->flags & EBPF_SAVE_S4) {
 393                 emit_instr_long(ctx, ld, lw,
 394                                         MIPS_R_S4, store_offset, MIPS_R_SP);
 395                 store_offset -= sizeof(long);
 396         }
 397         emit_instr(ctx, jr, dest_reg);
 398
 399         if (stack_adjust)
 400                 emit_instr_long(ctx, daddiu, addiu,
 401                                         MIPS_R_SP, MIPS_R_SP, stack_adjust);
 402         else
 403                 emit_instr(ctx, nop);
 404
 405         return 0;
 406 }
 407
 408 static void gen_imm_to_reg(const struct bpf_insn *insn, int reg,
 409                            struct jit_ctx *ctx)
 410 {
 411         if (insn->imm >= S16_MIN && insn->imm <= S16_MAX) {
 412                 emit_instr(ctx, addiu, reg, MIPS_R_ZERO, insn->imm);
 413         } else {
 414                 int lower = (s16)(insn->imm & 0xffff);
 415                 int upper = insn->imm - lower;
 416
 417                 emit_instr(ctx, lui, reg, upper >> 16);
 418                 emit_instr(ctx, addiu, reg, reg, lower);
 419         }
 420 }
 421
 422 static int gen_imm_insn(const struct bpf_insn *insn, struct jit_ctx *ctx,
 423                         int idx)
 424 {
 425         int upper_bound, lower_bound;
 426         int dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 427
 428         if (dst < 0)
 429                 return dst;
 430
 431         switch (BPF_OP(insn->code)) {
 432         case BPF_MOV:
 433         case BPF_ADD:
 434                 upper_bound = S16_MAX;
 435                 lower_bound = S16_MIN;
 436                 break;
 437         case BPF_SUB:
 438                 upper_bound = -(int)S16_MIN;
 439                 lower_bound = -(int)S16_MAX;
 440                 break;
 441         case BPF_AND:
 442         case BPF_OR:
 443         case BPF_XOR:
 444                 upper_bound = 0xffff;
 445                 lower_bound = 0;
 446                 break;
 447         case BPF_RSH:
 448         case BPF_LSH:
 449         case BPF_ARSH:
 450                 /* Shift amounts are truncated, no need for bounds */
 451                 upper_bound = S32_MAX;
 452                 lower_bound = S32_MIN;
 453                 break;
 454         default:
 455                 return -EINVAL;
 456         }
 457
 458         /*
 459          * Immediate move clobbers the register, so no sign/zero
 460          * extension needed.
 461          */
 462         if (BPF_CLASS(insn->code) == BPF_ALU64 &&
 463             BPF_OP(insn->code) != BPF_MOV &&
 464             get_reg_val_type(ctx, idx, insn->dst_reg) == REG_32BIT)
 465                 emit_instr(ctx, dinsu, dst, MIPS_R_ZERO, 32, 32);
 466         /* BPF_ALU | BPF_LSH doesn't need separate sign extension */
 467         if (BPF_CLASS(insn->code) == BPF_ALU &&
 468             BPF_OP(insn->code) != BPF_LSH &&
 469             BPF_OP(insn->code) != BPF_MOV &&
 470             get_reg_val_type(ctx, idx, insn->dst_reg) != REG_32BIT)
 471                 emit_instr(ctx, sll, dst, dst, 0);
 472
 473         if (insn->imm >= lower_bound && insn->imm <= upper_bound) {
 474                 /* single insn immediate case */
 475                 switch (BPF_OP(insn->code) | BPF_CLASS(insn->code)) {
 476                 case BPF_ALU64 | BPF_MOV:
 477                         emit_instr(ctx, daddiu, dst, MIPS_R_ZERO, insn->imm);
 478                         break;
 479                 case BPF_ALU64 | BPF_AND:
 480                 case BPF_ALU | BPF_AND:
 481                         emit_instr(ctx, andi, dst, dst, insn->imm);
 482                         break;
 483                 case BPF_ALU64 | BPF_OR:
 484                 case BPF_ALU | BPF_OR:
 485                         emit_instr(ctx, ori, dst, dst, insn->imm);
 486                         break;
 487                 case BPF_ALU64 | BPF_XOR:
 488                 case BPF_ALU | BPF_XOR:
 489                         emit_instr(ctx, xori, dst, dst, insn->imm);
 490                         break;
 491                 case BPF_ALU64 | BPF_ADD:
 492                         emit_instr(ctx, daddiu, dst, dst, insn->imm);
 493                         break;
 494                 case BPF_ALU64 | BPF_SUB:
 495                         emit_instr(ctx, daddiu, dst, dst, -insn->imm);
 496                         break;
 497                 case BPF_ALU64 | BPF_RSH:
 498                         emit_instr(ctx, dsrl_safe, dst, dst, insn->imm & 0x3f);
 499                         break;
 500                 case BPF_ALU | BPF_RSH:
 501                         emit_instr(ctx, srl, dst, dst, insn->imm & 0x1f);
 502                         break;
 503                 case BPF_ALU64 | BPF_LSH:
 504                         emit_instr(ctx, dsll_safe, dst, dst, insn->imm & 0x3f);
 505                         break;
 506                 case BPF_ALU | BPF_LSH:
 507                         emit_instr(ctx, sll, dst, dst, insn->imm & 0x1f);
 508                         break;
 509                 case BPF_ALU64 | BPF_ARSH:
 510                         emit_instr(ctx, dsra_safe, dst, dst, insn->imm & 0x3f);
 511                         break;
 512                 case BPF_ALU | BPF_ARSH:
 513                         emit_instr(ctx, sra, dst, dst, insn->imm & 0x1f);
 514                         break;
 515                 case BPF_ALU | BPF_MOV:
 516                         emit_instr(ctx, addiu, dst, MIPS_R_ZERO, insn->imm);
 517                         break;
 518                 case BPF_ALU | BPF_ADD:
 519                         emit_instr(ctx, addiu, dst, dst, insn->imm);
 520                         break;
 521                 case BPF_ALU | BPF_SUB:
 522                         emit_instr(ctx, addiu, dst, dst, -insn->imm);
 523                         break;
 524                 default:
 525                         return -EINVAL;
 526                 }
 527         } else {
 528                 /* multi insn immediate case */
 529                 if (BPF_OP(insn->code) == BPF_MOV) {
 530                         gen_imm_to_reg(insn, dst, ctx);
 531                 } else {
 532                         gen_imm_to_reg(insn, MIPS_R_AT, ctx);
 533                         switch (BPF_OP(insn->code) | BPF_CLASS(insn->code)) {
 534                         case BPF_ALU64 | BPF_AND:
 535                         case BPF_ALU | BPF_AND:
 536                                 emit_instr(ctx, and, dst, dst, MIPS_R_AT);
 537                                 break;
 538                         case BPF_ALU64 | BPF_OR:
 539                         case BPF_ALU | BPF_OR:
 540                                 emit_instr(ctx, or, dst, dst, MIPS_R_AT);
 541                                 break;
 542                         case BPF_ALU64 | BPF_XOR:
 543                         case BPF_ALU | BPF_XOR:
 544                                 emit_instr(ctx, xor, dst, dst, MIPS_R_AT);
 545                                 break;
 546                         case BPF_ALU64 | BPF_ADD:
 547                                 emit_instr(ctx, daddu, dst, dst, MIPS_R_AT);
 548                                 break;
 549                         case BPF_ALU64 | BPF_SUB:
 550                                 emit_instr(ctx, dsubu, dst, dst, MIPS_R_AT);
 551                                 break;
 552                         case BPF_ALU | BPF_ADD:
 553                                 emit_instr(ctx, addu, dst, dst, MIPS_R_AT);
 554                                 break;
 555                         case BPF_ALU | BPF_SUB:
 556                                 emit_instr(ctx, subu, dst, dst, MIPS_R_AT);
 557                                 break;
 558                         default:
 559                                 return -EINVAL;
 560                         }
 561                 }
 562         }
 563
 564         return 0;
 565 }
 566
 567 static void emit_const_to_reg(struct jit_ctx *ctx, int dst, u64 value)
 568 {
 569         if (value >= 0xffffffffffff8000ull || value < 0x8000ull) {
 570                 emit_instr(ctx, daddiu, dst, MIPS_R_ZERO, (int)value);
 571         } else if (value >= 0xffffffff80000000ull ||
 572                    (value < 0x80000000 && value > 0xffff)) {
 573                 emit_instr(ctx, lui, dst, (s32)(s16)(value >> 16));
 574                 emit_instr(ctx, ori, dst, dst, (unsigned int)(value & 0xffff));
 575         } else {
 576                 int i;
 577                 bool seen_part = false;
 578                 int needed_shift = 0;
 579
 580                 for (i = 0; i < 4; i++) {
 581                         u64 part = (value >> (16 * (3 - i))) & 0xffff;
 582
 583                         if (seen_part && needed_shift > 0 && (part || i == 3)) {
 584                                 emit_instr(ctx, dsll_safe, dst, dst, needed_shift);
 585                                 needed_shift = 0;
 586                         }
 587                         if (part) {
 588                                 if (i == 0 || (!seen_part && i < 3 && part < 0x8000)) {
 589                                         emit_instr(ctx, lui, dst, (s32)(s16)part);
 590                                         needed_shift = -16;
 591                                 } else {
 592                                         emit_instr(ctx, ori, dst,
 593                                                    seen_part ? dst : MIPS_R_ZERO,
 594                                                    (unsigned int)part);
 595                                 }
 596                                 seen_part = true;
 597                         }
 598                         if (seen_part)
 599                                 needed_shift += 16;
 600                 }
 601         }
 602 }
 603
 604 static int emit_bpf_tail_call(struct jit_ctx *ctx, int this_idx)
 605 {
 606         int off, b_off;
 607         int tcc_reg;
 608
 609         ctx->flags |= EBPF_SEEN_TC;
 610         /*
 611          * if (index >= array->map.max_entries)
 612          *     goto out;
 613          */
 614         off = offsetof(struct bpf_array, map.max_entries);
 615         emit_instr(ctx, lwu, MIPS_R_T5, off, MIPS_R_A1);
 616         emit_instr(ctx, sltu, MIPS_R_AT, MIPS_R_T5, MIPS_R_A2);
 617         b_off = b_imm(this_idx + 1, ctx);
 618         emit_instr(ctx, bne, MIPS_R_AT, MIPS_R_ZERO, b_off);
 619         /*
 620          * if (TCC-- < 0)
 621          *     goto out;
 622          */
 623         /* Delay slot */
 624         tcc_reg = (ctx->flags & EBPF_TCC_IN_V1) ? MIPS_R_V1 : MIPS_R_S4;
 625         emit_instr(ctx, daddiu, MIPS_R_T5, tcc_reg, -1);
 626         b_off = b_imm(this_idx + 1, ctx);
 627         emit_instr(ctx, bltz, tcc_reg, b_off);
 628         /*
 629          * prog = array->ptrs[index];
 630          * if (prog == NULL)
 631          *     goto out;
 632          */
 633         /* Delay slot */
 634         emit_instr(ctx, dsll, MIPS_R_T8, MIPS_R_A2, 3);
 635         emit_instr(ctx, daddu, MIPS_R_T8, MIPS_R_T8, MIPS_R_A1);
 636         off = offsetof(struct bpf_array, ptrs);
 637         emit_instr(ctx, ld, MIPS_R_AT, off, MIPS_R_T8);
 638         b_off = b_imm(this_idx + 1, ctx);
 639         emit_instr(ctx, beq, MIPS_R_AT, MIPS_R_ZERO, b_off);
 640         /* Delay slot */
 641         emit_instr(ctx, nop);
 642
 643         /* goto *(prog->bpf_func + 4); */
 644         off = offsetof(struct bpf_prog, bpf_func);
 645         emit_instr(ctx, ld, MIPS_R_T9, off, MIPS_R_AT);
 646         /* All systems are go... propagate TCC */
 647         emit_instr(ctx, daddu, MIPS_R_V1, MIPS_R_T5, MIPS_R_ZERO);
 648         /* Skip first instruction (TCC initialization) */
 649         emit_instr(ctx, daddiu, MIPS_R_T9, MIPS_R_T9, 4);
 650         return build_int_epilogue(ctx, MIPS_R_T9);
 651 }
 652
 653 static bool is_bad_offset(int b_off)
 654 {
 655         return b_off > 0x1ffff || b_off < -0x20000;
 656 }
 657
 658 /* Returns the number of insn slots consumed. */
 659 static int build_one_insn(const struct bpf_insn *insn, struct jit_ctx *ctx,
 660                           int this_idx, int exit_idx)
 661 {
 662         int src, dst, r, td, ts, mem_off, b_off;
 663         bool need_swap, did_move, cmp_eq;
 664         unsigned int target = 0;
 665         u64 t64;
 666         s64 t64s;
 667         int bpf_op = BPF_OP(insn->code);
 668
 669         if (IS_ENABLED(CONFIG_32BIT) && ((BPF_CLASS(insn->code) == BPF_ALU64)
 670                                                 || (bpf_op == BPF_DW)))
 671                 return -EINVAL;
 672
 673         switch (insn->code) {
 674         case BPF_ALU64 | BPF_ADD | BPF_K: /* ALU64_IMM */
 675         case BPF_ALU64 | BPF_SUB | BPF_K: /* ALU64_IMM */
 676         case BPF_ALU64 | BPF_OR | BPF_K: /* ALU64_IMM */
 677         case BPF_ALU64 | BPF_AND | BPF_K: /* ALU64_IMM */
 678         case BPF_ALU64 | BPF_LSH | BPF_K: /* ALU64_IMM */
 679         case BPF_ALU64 | BPF_RSH | BPF_K: /* ALU64_IMM */
 680         case BPF_ALU64 | BPF_XOR | BPF_K: /* ALU64_IMM */
 681         case BPF_ALU64 | BPF_ARSH | BPF_K: /* ALU64_IMM */
 682         case BPF_ALU64 | BPF_MOV | BPF_K: /* ALU64_IMM */
 683         case BPF_ALU | BPF_MOV | BPF_K: /* ALU32_IMM */
 684         case BPF_ALU | BPF_ADD | BPF_K: /* ALU32_IMM */
 685         case BPF_ALU | BPF_SUB | BPF_K: /* ALU32_IMM */
 686         case BPF_ALU | BPF_OR | BPF_K: /* ALU64_IMM */
 687         case BPF_ALU | BPF_AND | BPF_K: /* ALU64_IMM */
 688         case BPF_ALU | BPF_LSH | BPF_K: /* ALU64_IMM */
 689         case BPF_ALU | BPF_RSH | BPF_K: /* ALU64_IMM */
 690         case BPF_ALU | BPF_XOR | BPF_K: /* ALU64_IMM */
 691         case BPF_ALU | BPF_ARSH | BPF_K: /* ALU64_IMM */
 692                 r = gen_imm_insn(insn, ctx, this_idx);
 693                 if (r < 0)
 694                         return r;
 695                 break;
 696         case BPF_ALU64 | BPF_MUL | BPF_K: /* ALU64_IMM */
 697                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 698                 if (dst < 0)
 699                         return dst;
 700                 if (get_reg_val_type(ctx, this_idx, insn->dst_reg) == REG_32BIT)
 701                         emit_instr(ctx, dinsu, dst, MIPS_R_ZERO, 32, 32);
 702                 if (insn->imm == 1) /* Mult by 1 is a nop */
 703                         break;
 704                 gen_imm_to_reg(insn, MIPS_R_AT, ctx);
 705                 if (MIPS_ISA_REV >= 6) {
 706                         emit_instr(ctx, dmulu, dst, dst, MIPS_R_AT);
 707                 } else {
 708                         emit_instr(ctx, dmultu, MIPS_R_AT, dst);
 709                         emit_instr(ctx, mflo, dst);
 710                 }
 711                 break;
 712         case BPF_ALU64 | BPF_NEG | BPF_K: /* ALU64_IMM */
 713                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 714                 if (dst < 0)
 715                         return dst;
 716                 if (get_reg_val_type(ctx, this_idx, insn->dst_reg) == REG_32BIT)
 717                         emit_instr(ctx, dinsu, dst, MIPS_R_ZERO, 32, 32);
 718                 emit_instr(ctx, dsubu, dst, MIPS_R_ZERO, dst);
 719                 break;
 720         case BPF_ALU | BPF_MUL | BPF_K: /* ALU_IMM */
 721                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 722                 if (dst < 0)
 723                         return dst;
 724                 td = get_reg_val_type(ctx, this_idx, insn->dst_reg);
 725                 if (td == REG_64BIT) {
 726                         /* sign extend */
 727                         emit_instr(ctx, sll, dst, dst, 0);
 728                 }
 729                 if (insn->imm == 1) /* Mult by 1 is a nop */
 730                         break;
 731                 gen_imm_to_reg(insn, MIPS_R_AT, ctx);
 732                 if (MIPS_ISA_REV >= 6) {
 733                         emit_instr(ctx, mulu, dst, dst, MIPS_R_AT);
 734                 } else {
 735                         emit_instr(ctx, multu, dst, MIPS_R_AT);
 736                         emit_instr(ctx, mflo, dst);
 737                 }
 738                 break;
 739         case BPF_ALU | BPF_NEG | BPF_K: /* ALU_IMM */
 740                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 741                 if (dst < 0)
 742                         return dst;
 743                 td = get_reg_val_type(ctx, this_idx, insn->dst_reg);
 744                 if (td == REG_64BIT) {
 745                         /* sign extend */
 746                         emit_instr(ctx, sll, dst, dst, 0);
 747                 }
 748                 emit_instr(ctx, subu, dst, MIPS_R_ZERO, dst);
 749                 break;
 750         case BPF_ALU | BPF_DIV | BPF_K: /* ALU_IMM */
 751         case BPF_ALU | BPF_MOD | BPF_K: /* ALU_IMM */
 752                 if (insn->imm == 0)
 753                         return -EINVAL;
 754                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 755                 if (dst < 0)
 756                         return dst;
 757                 td = get_reg_val_type(ctx, this_idx, insn->dst_reg);
 758                 if (td == REG_64BIT)
 759                         /* sign extend */
 760                         emit_instr(ctx, sll, dst, dst, 0);
 761                 if (insn->imm == 1) {
 762                         /* div by 1 is a nop, mod by 1 is zero */
 763                         if (bpf_op == BPF_MOD)
 764                                 emit_instr(ctx, addu, dst, MIPS_R_ZERO, MIPS_R_ZERO);
 765                         break;
 766                 }
 767                 gen_imm_to_reg(insn, MIPS_R_AT, ctx);
 768                 if (MIPS_ISA_REV >= 6) {
 769                         if (bpf_op == BPF_DIV)
 770                                 emit_instr(ctx, divu_r6, dst, dst, MIPS_R_AT);
 771                         else
 772                                 emit_instr(ctx, modu, dst, dst, MIPS_R_AT);
 773                         break;
 774                 }
 775                 emit_instr(ctx, divu, dst, MIPS_R_AT);
 776                 if (bpf_op == BPF_DIV)
 777                         emit_instr(ctx, mflo, dst);
 778                 else
 779                         emit_instr(ctx, mfhi, dst);
 780                 break;
 781         case BPF_ALU64 | BPF_DIV | BPF_K: /* ALU_IMM */
 782         case BPF_ALU64 | BPF_MOD | BPF_K: /* ALU_IMM */
 783                 if (insn->imm == 0)
 784                         return -EINVAL;
 785                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 786                 if (dst < 0)
 787                         return dst;
 788                 if (get_reg_val_type(ctx, this_idx, insn->dst_reg) == REG_32BIT)
 789                         emit_instr(ctx, dinsu, dst, MIPS_R_ZERO, 32, 32);
 790                 if (insn->imm == 1) {
 791                         /* div by 1 is a nop, mod by 1 is zero */
 792                         if (bpf_op == BPF_MOD)
 793                                 emit_instr(ctx, addu, dst, MIPS_R_ZERO, MIPS_R_ZERO);
 794                         break;
 795                 }
 796                 gen_imm_to_reg(insn, MIPS_R_AT, ctx);
 797                 if (MIPS_ISA_REV >= 6) {
 798                         if (bpf_op == BPF_DIV)
 799                                 emit_instr(ctx, ddivu_r6, dst, dst, MIPS_R_AT);
 800                         else
 801                                 emit_instr(ctx, modu, dst, dst, MIPS_R_AT);
 802                         break;
 803                 }
 804                 emit_instr(ctx, ddivu, dst, MIPS_R_AT);
 805                 if (bpf_op == BPF_DIV)
 806                         emit_instr(ctx, mflo, dst);
 807                 else
 808                         emit_instr(ctx, mfhi, dst);
 809                 break;
 810         case BPF_ALU64 | BPF_MOV | BPF_X: /* ALU64_REG */
 811         case BPF_ALU64 | BPF_ADD | BPF_X: /* ALU64_REG */
 812         case BPF_ALU64 | BPF_SUB | BPF_X: /* ALU64_REG */
 813         case BPF_ALU64 | BPF_XOR | BPF_X: /* ALU64_REG */
 814         case BPF_ALU64 | BPF_OR | BPF_X: /* ALU64_REG */
 815         case BPF_ALU64 | BPF_AND | BPF_X: /* ALU64_REG */
 816         case BPF_ALU64 | BPF_MUL | BPF_X: /* ALU64_REG */
 817         case BPF_ALU64 | BPF_DIV | BPF_X: /* ALU64_REG */
 818         case BPF_ALU64 | BPF_MOD | BPF_X: /* ALU64_REG */
 819         case BPF_ALU64 | BPF_LSH | BPF_X: /* ALU64_REG */
 820         case BPF_ALU64 | BPF_RSH | BPF_X: /* ALU64_REG */
 821         case BPF_ALU64 | BPF_ARSH | BPF_X: /* ALU64_REG */
 822                 src = ebpf_to_mips_reg(ctx, insn, src_reg);
 823                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 824                 if (src < 0 || dst < 0)
 825                         return -EINVAL;
 826                 if (get_reg_val_type(ctx, this_idx, insn->dst_reg) == REG_32BIT)
 827                         emit_instr(ctx, dinsu, dst, MIPS_R_ZERO, 32, 32);
 828                 did_move = false;
 829                 if (insn->src_reg == BPF_REG_10) {
 830                         if (bpf_op == BPF_MOV) {
 831                                 emit_instr(ctx, daddiu, dst, MIPS_R_SP, MAX_BPF_STACK);
 832                                 did_move = true;
 833                         } else {
 834                                 emit_instr(ctx, daddiu, MIPS_R_AT, MIPS_R_SP, MAX_BPF_STACK);
 835                                 src = MIPS_R_AT;
 836                         }
 837                 } else if (get_reg_val_type(ctx, this_idx, insn->src_reg) == REG_32BIT) {
 838                         int tmp_reg = MIPS_R_AT;
 839
 840                         if (bpf_op == BPF_MOV) {
 841                                 tmp_reg = dst;
 842                                 did_move = true;
 843                         }
 844                         emit_instr(ctx, daddu, tmp_reg, src, MIPS_R_ZERO);
 845                         emit_instr(ctx, dinsu, tmp_reg, MIPS_R_ZERO, 32, 32);
 846                         src = MIPS_R_AT;
 847                 }
 848                 switch (bpf_op) {
 849                 case BPF_MOV:
 850                         if (!did_move)
 851                                 emit_instr(ctx, daddu, dst, src, MIPS_R_ZERO);
 852                         break;
 853                 case BPF_ADD:
 854                         emit_instr(ctx, daddu, dst, dst, src);
 855                         break;
 856                 case BPF_SUB:
 857                         emit_instr(ctx, dsubu, dst, dst, src);
 858                         break;
 859                 case BPF_XOR:
 860                         emit_instr(ctx, xor, dst, dst, src);
 861                         break;
 862                 case BPF_OR:
 863                         emit_instr(ctx, or, dst, dst, src);
 864                         break;
 865                 case BPF_AND:
 866                         emit_instr(ctx, and, dst, dst, src);
 867                         break;
 868                 case BPF_MUL:
 869                         if (MIPS_ISA_REV >= 6) {
 870                                 emit_instr(ctx, dmulu, dst, dst, src);
 871                         } else {
 872                                 emit_instr(ctx, dmultu, dst, src);
 873                                 emit_instr(ctx, mflo, dst);
 874                         }
 875                         break;
 876                 case BPF_DIV:
 877                 case BPF_MOD:
 878                         if (MIPS_ISA_REV >= 6) {
 879                                 if (bpf_op == BPF_DIV)
 880                                         emit_instr(ctx, ddivu_r6,
 881                                                         dst, dst, src);
 882                                 else
 883                                         emit_instr(ctx, modu, dst, dst, src);
 884                                 break;
 885                         }
 886                         emit_instr(ctx, ddivu, dst, src);
 887                         if (bpf_op == BPF_DIV)
 888                                 emit_instr(ctx, mflo, dst);
 889                         else
 890                                 emit_instr(ctx, mfhi, dst);
 891                         break;
 892                 case BPF_LSH:
 893                         emit_instr(ctx, dsllv, dst, dst, src);
 894                         break;
 895                 case BPF_RSH:
 896                         emit_instr(ctx, dsrlv, dst, dst, src);
 897                         break;
 898                 case BPF_ARSH:
 899                         emit_instr(ctx, dsrav, dst, dst, src);
 900                         break;
 901                 default:
 902                         pr_err("ALU64_REG NOT HANDLED\n");
 903                         return -EINVAL;
 904                 }
 905                 break;
 906         case BPF_ALU | BPF_MOV | BPF_X: /* ALU_REG */
 907         case BPF_ALU | BPF_ADD | BPF_X: /* ALU_REG */
 908         case BPF_ALU | BPF_SUB | BPF_X: /* ALU_REG */
 909         case BPF_ALU | BPF_XOR | BPF_X: /* ALU_REG */
 910         case BPF_ALU | BPF_OR | BPF_X: /* ALU_REG */
 911         case BPF_ALU | BPF_AND | BPF_X: /* ALU_REG */
 912         case BPF_ALU | BPF_MUL | BPF_X: /* ALU_REG */
 913         case BPF_ALU | BPF_DIV | BPF_X: /* ALU_REG */
 914         case BPF_ALU | BPF_MOD | BPF_X: /* ALU_REG */
 915         case BPF_ALU | BPF_LSH | BPF_X: /* ALU_REG */
 916         case BPF_ALU | BPF_RSH | BPF_X: /* ALU_REG */
 917         case BPF_ALU | BPF_ARSH | BPF_X: /* ALU_REG */
 918                 src = ebpf_to_mips_reg(ctx, insn, src_reg_no_fp);
 919                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
 920                 if (src < 0 || dst < 0)
 921                         return -EINVAL;
 922                 td = get_reg_val_type(ctx, this_idx, insn->dst_reg);
 923                 if (td == REG_64BIT) {
 924                         /* sign extend */
 925                         emit_instr(ctx, sll, dst, dst, 0);
 926                 }
 927                 did_move = false;
 928                 ts = get_reg_val_type(ctx, this_idx, insn->src_reg);
 929                 if (ts == REG_64BIT) {
 930                         int tmp_reg = MIPS_R_AT;
 931
 932                         if (bpf_op == BPF_MOV) {
 933                                 tmp_reg = dst;
 934                                 did_move = true;
 935                         }
 936                         /* sign extend */
 937                         emit_instr(ctx, sll, tmp_reg, src, 0);
 938                         src = MIPS_R_AT;
 939                 }
 940                 switch (bpf_op) {
 941                 case BPF_MOV:
 942                         if (!did_move)
 943                                 emit_instr(ctx, addu, dst, src, MIPS_R_ZERO);
 944                         break;
 945                 case BPF_ADD:
 946                         emit_instr(ctx, addu, dst, dst, src);
 947                         break;
 948                 case BPF_SUB:
 949                         emit_instr(ctx, subu, dst, dst, src);
 950                         break;
 951                 case BPF_XOR:
 952                         emit_instr(ctx, xor, dst, dst, src);
 953                         break;
 954                 case BPF_OR:
 955                         emit_instr(ctx, or, dst, dst, src);
 956                         break;
 957                 case BPF_AND:
 958                         emit_instr(ctx, and, dst, dst, src);
 959                         break;
 960                 case BPF_MUL:
 961                         emit_instr(ctx, mul, dst, dst, src);
 962                         break;
 963                 case BPF_DIV:
 964                 case BPF_MOD:
 965                         if (MIPS_ISA_REV >= 6) {
 966                                 if (bpf_op == BPF_DIV)
 967                                         emit_instr(ctx, divu_r6, dst, dst, src);
 968                                 else
 969                                         emit_instr(ctx, modu, dst, dst, src);
 970                                 break;
 971                         }
 972                         emit_instr(ctx, divu, dst, src);
 973                         if (bpf_op == BPF_DIV)
 974                                 emit_instr(ctx, mflo, dst);
 975                         else
 976                                 emit_instr(ctx, mfhi, dst);
 977                         break;
 978                 case BPF_LSH:
 979                         emit_instr(ctx, sllv, dst, dst, src);
 980                         break;
 981                 case BPF_RSH:
 982                         emit_instr(ctx, srlv, dst, dst, src);
 983                         break;
 984                 case BPF_ARSH:
 985                         emit_instr(ctx, srav, dst, dst, src);
 986                         break;
 987                 default:
 988                         pr_err("ALU_REG NOT HANDLED\n");
 989                         return -EINVAL;
 990                 }
 991                 break;
 992         case BPF_JMP | BPF_EXIT:
 993                 if (this_idx + 1 < exit_idx) {
 994                         b_off = b_imm(exit_idx, ctx);
 995                         if (is_bad_offset(b_off))
 996                                 return -E2BIG;
 997                         emit_instr(ctx, beq, MIPS_R_ZERO, MIPS_R_ZERO, b_off);
 998                         emit_instr(ctx, nop);
 999                 }
1000                 break;
1001         case BPF_JMP | BPF_JEQ | BPF_K: /* JMP_IMM */
1002         case BPF_JMP | BPF_JNE | BPF_K: /* JMP_IMM */
1003                 cmp_eq = (bpf_op == BPF_JEQ);
1004                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg_fp_ok);
1005                 if (dst < 0)
1006                         return dst;
1007                 if (insn->imm == 0) {
1008                         src = MIPS_R_ZERO;
1009                 } else {
1010                         gen_imm_to_reg(insn, MIPS_R_AT, ctx);
1011                         src = MIPS_R_AT;
1012                 }
1013                 goto jeq_common;
1014         case BPF_JMP | BPF_JEQ | BPF_X: /* JMP_REG */
1015         case BPF_JMP | BPF_JNE | BPF_X:
1016         case BPF_JMP | BPF_JSLT | BPF_X:
1017         case BPF_JMP | BPF_JSLE | BPF_X:
1018         case BPF_JMP | BPF_JSGT | BPF_X:
1019         case BPF_JMP | BPF_JSGE | BPF_X:
1020         case BPF_JMP | BPF_JLT | BPF_X:
1021         case BPF_JMP | BPF_JLE | BPF_X:
1022         case BPF_JMP | BPF_JGT | BPF_X:
1023         case BPF_JMP | BPF_JGE | BPF_X:
1024         case BPF_JMP | BPF_JSET | BPF_X:
1025                 src = ebpf_to_mips_reg(ctx, insn, src_reg_no_fp);
1026                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
1027                 if (src < 0 || dst < 0)
1028                         return -EINVAL;
1029                 td = get_reg_val_type(ctx, this_idx, insn->dst_reg);
1030                 ts = get_reg_val_type(ctx, this_idx, insn->src_reg);
1031                 if (td == REG_32BIT && ts != REG_32BIT) {
1032                         emit_instr(ctx, sll, MIPS_R_AT, src, 0);
1033                         src = MIPS_R_AT;
1034                 } else if (ts == REG_32BIT && td != REG_32BIT) {
1035                         emit_instr(ctx, sll, MIPS_R_AT, dst, 0);
1036                         dst = MIPS_R_AT;
1037                 }
1038                 if (bpf_op == BPF_JSET) {
1039                         emit_instr(ctx, and, MIPS_R_AT, dst, src);
1040                         cmp_eq = false;
1041                         dst = MIPS_R_AT;
1042                         src = MIPS_R_ZERO;
1043                 } else if (bpf_op == BPF_JSGT || bpf_op == BPF_JSLE) {
1044                         emit_instr(ctx, dsubu, MIPS_R_AT, dst, src);
1045                         if ((insn + 1)->code == (BPF_JMP | BPF_EXIT) && insn->off == 1) {
1046                                 b_off = b_imm(exit_idx, ctx);
1047                                 if (is_bad_offset(b_off))
1048                                         return -E2BIG;
1049                                 if (bpf_op == BPF_JSGT)
1050                                         emit_instr(ctx, blez, MIPS_R_AT, b_off);
1051                                 else
1052                                         emit_instr(ctx, bgtz, MIPS_R_AT, b_off);
1053                                 emit_instr(ctx, nop);
1054                                 return 2; /* We consumed the exit. */
1055                         }
1056                         b_off = b_imm(this_idx + insn->off + 1, ctx);
1057                         if (is_bad_offset(b_off))
1058                                 return -E2BIG;
1059                         if (bpf_op == BPF_JSGT)
1060                                 emit_instr(ctx, bgtz, MIPS_R_AT, b_off);
1061                         else
1062                                 emit_instr(ctx, blez, MIPS_R_AT, b_off);
1063                         emit_instr(ctx, nop);
1064                         break;
1065                 } else if (bpf_op == BPF_JSGE || bpf_op == BPF_JSLT) {
1066                         emit_instr(ctx, slt, MIPS_R_AT, dst, src);
1067                         cmp_eq = bpf_op == BPF_JSGE;
1068                         dst = MIPS_R_AT;
1069                         src = MIPS_R_ZERO;
1070                 } else if (bpf_op == BPF_JGT || bpf_op == BPF_JLE) {
1071                         /* dst or src could be AT */
1072                         emit_instr(ctx, dsubu, MIPS_R_T8, dst, src);
1073                         emit_instr(ctx, sltu, MIPS_R_AT, dst, src);
1074                         /* SP known to be non-zero, movz becomes boolean not */
1075                         if (MIPS_ISA_REV >= 6) {
1076                                 emit_instr(ctx, seleqz, MIPS_R_T9,
1077                                                 MIPS_R_SP, MIPS_R_T8);
1078                         } else {
1079                                 emit_instr(ctx, movz, MIPS_R_T9,
1080                                                 MIPS_R_SP, MIPS_R_T8);
1081                                 emit_instr(ctx, movn, MIPS_R_T9,
1082                                                 MIPS_R_ZERO, MIPS_R_T8);
1083                         }
1084                         emit_instr(ctx, or, MIPS_R_AT, MIPS_R_T9, MIPS_R_AT);
1085                         cmp_eq = bpf_op == BPF_JGT;
1086                         dst = MIPS_R_AT;
1087                         src = MIPS_R_ZERO;
1088                 } else if (bpf_op == BPF_JGE || bpf_op == BPF_JLT) {
1089                         emit_instr(ctx, sltu, MIPS_R_AT, dst, src);
1090                         cmp_eq = bpf_op == BPF_JGE;
1091                         dst = MIPS_R_AT;
1092                         src = MIPS_R_ZERO;
1093                 } else { /* JNE/JEQ case */
1094                         cmp_eq = (bpf_op == BPF_JEQ);
1095                 }
1096 jeq_common:
1097                 /*
1098                  * If the next insn is EXIT and we are jumping arround
1099                  * only it, invert the sense of the compare and
1100                  * conditionally jump to the exit.  Poor man's branch
1101                  * chaining.
1102                  */
1103                 if ((insn + 1)->code == (BPF_JMP | BPF_EXIT) && insn->off == 1) {
1104                         b_off = b_imm(exit_idx, ctx);
1105                         if (is_bad_offset(b_off)) {
1106                                 target = j_target(ctx, exit_idx);
1107                                 if (target == (unsigned int)-1)
1108                                         return -E2BIG;
1109                                 cmp_eq = !cmp_eq;
1110                                 b_off = 4 * 3;
1111                                 if (!(ctx->offsets[this_idx] & OFFSETS_B_CONV)) {
1112                                         ctx->offsets[this_idx] |= OFFSETS_B_CONV;
1113                                         ctx->long_b_conversion = 1;
1114                                 }
1115                         }
1116
1117                         if (cmp_eq)
1118                                 emit_instr(ctx, bne, dst, src, b_off);
1119                         else
1120                                 emit_instr(ctx, beq, dst, src, b_off);
1121                         emit_instr(ctx, nop);
1122                         if (ctx->offsets[this_idx] & OFFSETS_B_CONV) {
1123                                 emit_instr(ctx, j, target);
1124                                 emit_instr(ctx, nop);
1125                         }
1126                         return 2; /* We consumed the exit. */
1127                 }
1128                 b_off = b_imm(this_idx + insn->off + 1, ctx);
1129                 if (is_bad_offset(b_off)) {
1130                         target = j_target(ctx, this_idx + insn->off + 1);
1131                         if (target == (unsigned int)-1)
1132                                 return -E2BIG;
1133                         cmp_eq = !cmp_eq;
1134                         b_off = 4 * 3;
1135                         if (!(ctx->offsets[this_idx] & OFFSETS_B_CONV)) {
1136                                 ctx->offsets[this_idx] |= OFFSETS_B_CONV;
1137                                 ctx->long_b_conversion = 1;
1138                         }
1139                 }
1140
1141                 if (cmp_eq)
1142                         emit_instr(ctx, beq, dst, src, b_off);
1143                 else
1144                         emit_instr(ctx, bne, dst, src, b_off);
1145                 emit_instr(ctx, nop);
1146                 if (ctx->offsets[this_idx] & OFFSETS_B_CONV) {
1147                         emit_instr(ctx, j, target);
1148                         emit_instr(ctx, nop);
1149                 }
1150                 break;
1151         case BPF_JMP | BPF_JSGT | BPF_K: /* JMP_IMM */
1152         case BPF_JMP | BPF_JSGE | BPF_K: /* JMP_IMM */
1153         case BPF_JMP | BPF_JSLT | BPF_K: /* JMP_IMM */
1154         case BPF_JMP | BPF_JSLE | BPF_K: /* JMP_IMM */
1155                 cmp_eq = (bpf_op == BPF_JSGE);
1156                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg_fp_ok);
1157                 if (dst < 0)
1158                         return dst;
1159
1160                 if (insn->imm == 0) {
1161                         if ((insn + 1)->code == (BPF_JMP | BPF_EXIT) && insn->off == 1) {
1162                                 b_off = b_imm(exit_idx, ctx);
1163                                 if (is_bad_offset(b_off))
1164                                         return -E2BIG;
1165                                 switch (bpf_op) {
1166                                 case BPF_JSGT:
1167                                         emit_instr(ctx, blez, dst, b_off);
1168                                         break;
1169                                 case BPF_JSGE:
1170                                         emit_instr(ctx, bltz, dst, b_off);
1171                                         break;
1172                                 case BPF_JSLT:
1173                                         emit_instr(ctx, bgez, dst, b_off);
1174                                         break;
1175                                 case BPF_JSLE:
1176                                         emit_instr(ctx, bgtz, dst, b_off);
1177                                         break;
1178                                 }
1179                                 emit_instr(ctx, nop);
1180                                 return 2; /* We consumed the exit. */
1181                         }
1182                         b_off = b_imm(this_idx + insn->off + 1, ctx);
1183                         if (is_bad_offset(b_off))
1184                                 return -E2BIG;
1185                         switch (bpf_op) {
1186                         case BPF_JSGT:
1187                                 emit_instr(ctx, bgtz, dst, b_off);
1188                                 break;
1189                         case BPF_JSGE:
1190                                 emit_instr(ctx, bgez, dst, b_off);
1191                                 break;
1192                         case BPF_JSLT:
1193                                 emit_instr(ctx, bltz, dst, b_off);
1194                                 break;
1195                         case BPF_JSLE:
1196                                 emit_instr(ctx, blez, dst, b_off);
1197                                 break;
1198                         }
1199                         emit_instr(ctx, nop);
1200                         break;
1201                 }
1202                 /*
1203                  * only "LT" compare available, so we must use imm + 1
1204                  * to generate "GT" and imm -1 to generate LE
1205                  */
1206                 if (bpf_op == BPF_JSGT)
1207                         t64s = insn->imm + 1;
1208                 else if (bpf_op == BPF_JSLE)
1209                         t64s = insn->imm + 1;
1210                 else
1211                         t64s = insn->imm;
1212
1213                 cmp_eq = bpf_op == BPF_JSGT || bpf_op == BPF_JSGE;
1214                 if (t64s >= S16_MIN && t64s <= S16_MAX) {
1215                         emit_instr(ctx, slti, MIPS_R_AT, dst, (int)t64s);
1216                         src = MIPS_R_AT;
1217                         dst = MIPS_R_ZERO;
1218                         goto jeq_common;
1219                 }
1220                 emit_const_to_reg(ctx, MIPS_R_AT, (u64)t64s);
1221                 emit_instr(ctx, slt, MIPS_R_AT, dst, MIPS_R_AT);
1222                 src = MIPS_R_AT;
1223                 dst = MIPS_R_ZERO;
1224                 goto jeq_common;
1225
1226         case BPF_JMP | BPF_JGT | BPF_K:
1227         case BPF_JMP | BPF_JGE | BPF_K:
1228         case BPF_JMP | BPF_JLT | BPF_K:
1229         case BPF_JMP | BPF_JLE | BPF_K:
1230                 cmp_eq = (bpf_op == BPF_JGE);
1231                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg_fp_ok);
1232                 if (dst < 0)
1233                         return dst;
1234                 /*
1235                  * only "LT" compare available, so we must use imm + 1
1236                  * to generate "GT" and imm -1 to generate LE
1237                  */
1238                 if (bpf_op == BPF_JGT)
1239                         t64s = (u64)(u32)(insn->imm) + 1;
1240                 else if (bpf_op == BPF_JLE)
1241                         t64s = (u64)(u32)(insn->imm) + 1;
1242                 else
1243                         t64s = (u64)(u32)(insn->imm);
1244
1245                 cmp_eq = bpf_op == BPF_JGT || bpf_op == BPF_JGE;
1246
1247                 emit_const_to_reg(ctx, MIPS_R_AT, (u64)t64s);
1248                 emit_instr(ctx, sltu, MIPS_R_AT, dst, MIPS_R_AT);
1249                 src = MIPS_R_AT;
1250                 dst = MIPS_R_ZERO;
1251                 goto jeq_common;
1252
1253         case BPF_JMP | BPF_JSET | BPF_K: /* JMP_IMM */
1254                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg_fp_ok);
1255                 if (dst < 0)
1256                         return dst;
1257
1258                 if (ctx->use_bbit_insns && hweight32((u32)insn->imm) == 1) {
1259                         if ((insn + 1)->code == (BPF_JMP | BPF_EXIT) && insn->off == 1) {
1260                                 b_off = b_imm(exit_idx, ctx);
1261                                 if (is_bad_offset(b_off))
1262                                         return -E2BIG;
1263                                 emit_instr(ctx, bbit0, dst, ffs((u32)insn->imm) - 1, b_off);
1264                                 emit_instr(ctx, nop);
1265                                 return 2; /* We consumed the exit. */
1266                         }
1267                         b_off = b_imm(this_idx + insn->off + 1, ctx);
1268                         if (is_bad_offset(b_off))
1269                                 return -E2BIG;
1270                         emit_instr(ctx, bbit1, dst, ffs((u32)insn->imm) - 1, b_off);
1271                         emit_instr(ctx, nop);
1272                         break;
1273                 }
1274                 t64 = (u32)insn->imm;
1275                 emit_const_to_reg(ctx, MIPS_R_AT, t64);
1276                 emit_instr(ctx, and, MIPS_R_AT, dst, MIPS_R_AT);
1277                 src = MIPS_R_AT;
1278                 dst = MIPS_R_ZERO;
1279                 cmp_eq = false;
1280                 goto jeq_common;
1281
1282         case BPF_JMP | BPF_JA:
1283                 /*
1284                  * Prefer relative branch for easier debugging, but
1285                  * fall back if needed.
1286                  */
1287                 b_off = b_imm(this_idx + insn->off + 1, ctx);
1288                 if (is_bad_offset(b_off)) {
1289                         target = j_target(ctx, this_idx + insn->off + 1);
1290                         if (target == (unsigned int)-1)
1291                                 return -E2BIG;
1292                         emit_instr(ctx, j, target);
1293                 } else {
1294                         emit_instr(ctx, b, b_off);
1295                 }
1296                 emit_instr(ctx, nop);
1297                 break;
1298         case BPF_LD | BPF_DW | BPF_IMM:
1299                 if (insn->src_reg != 0)
1300                         return -EINVAL;
1301                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
1302                 if (dst < 0)
1303                         return dst;
1304                 t64 = ((u64)(u32)insn->imm) | ((u64)(insn + 1)->imm << 32);
1305                 emit_const_to_reg(ctx, dst, t64);
1306                 return 2; /* Double slot insn */
1307
1308         case BPF_JMP | BPF_CALL:
1309                 ctx->flags |= EBPF_SAVE_RA;
1310                 t64s = (s64)insn->imm + (long)__bpf_call_base;
1311                 emit_const_to_reg(ctx, MIPS_R_T9, (u64)t64s);
1312                 emit_instr(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
1313                 /* delay slot */
1314                 emit_instr(ctx, nop);
1315                 break;
1316
1317         case BPF_JMP | BPF_TAIL_CALL:
1318                 if (emit_bpf_tail_call(ctx, this_idx))
1319                         return -EINVAL;
1320                 break;
1321
1322         case BPF_ALU | BPF_END | BPF_FROM_BE:
1323         case BPF_ALU | BPF_END | BPF_FROM_LE:
1324                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
1325                 if (dst < 0)
1326                         return dst;
1327                 td = get_reg_val_type(ctx, this_idx, insn->dst_reg);
1328                 if (insn->imm == 64 && td == REG_32BIT)
1329                         emit_instr(ctx, dinsu, dst, MIPS_R_ZERO, 32, 32);
1330
1331                 if (insn->imm != 64 && td == REG_64BIT) {
1332                         /* sign extend */
1333                         emit_instr(ctx, sll, dst, dst, 0);
1334                 }
1335
1336 #ifdef __BIG_ENDIAN
1337                 need_swap = (BPF_SRC(insn->code) == BPF_FROM_LE);
1338 #else
1339                 need_swap = (BPF_SRC(insn->code) == BPF_FROM_BE);
1340 #endif
1341                 if (insn->imm == 16) {
1342                         if (need_swap)
1343                                 emit_instr(ctx, wsbh, dst, dst);
1344                         emit_instr(ctx, andi, dst, dst, 0xffff);
1345                 } else if (insn->imm == 32) {
1346                         if (need_swap) {
1347                                 emit_instr(ctx, wsbh, dst, dst);
1348                                 emit_instr(ctx, rotr, dst, dst, 16);
1349                         }
1350                 } else { /* 64-bit*/
1351                         if (need_swap) {
1352                                 emit_instr(ctx, dsbh, dst, dst);
1353                                 emit_instr(ctx, dshd, dst, dst);
1354                         }
1355                 }
1356                 break;
1357
1358         case BPF_ST | BPF_NOSPEC: /* speculation barrier */
1359                 break;
1360
1361         case BPF_ST | BPF_B | BPF_MEM:
1362         case BPF_ST | BPF_H | BPF_MEM:
1363         case BPF_ST | BPF_W | BPF_MEM:
1364         case BPF_ST | BPF_DW | BPF_MEM:
1365                 if (insn->dst_reg == BPF_REG_10) {
1366                         ctx->flags |= EBPF_SEEN_FP;
1367                         dst = MIPS_R_SP;
1368                         mem_off = insn->off + MAX_BPF_STACK;
1369                 } else {
1370                         dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
1371                         if (dst < 0)
1372                                 return dst;
1373                         mem_off = insn->off;
1374                 }
1375                 gen_imm_to_reg(insn, MIPS_R_AT, ctx);
1376                 switch (BPF_SIZE(insn->code)) {
1377                 case BPF_B:
1378                         emit_instr(ctx, sb, MIPS_R_AT, mem_off, dst);
1379                         break;
1380                 case BPF_H:
1381                         emit_instr(ctx, sh, MIPS_R_AT, mem_off, dst);
1382                         break;
1383                 case BPF_W:
1384                         emit_instr(ctx, sw, MIPS_R_AT, mem_off, dst);
1385                         break;
1386                 case BPF_DW:
1387                         emit_instr(ctx, sd, MIPS_R_AT, mem_off, dst);
1388                         break;
1389                 }
1390                 break;
1391
1392         case BPF_LDX | BPF_B | BPF_MEM:
1393         case BPF_LDX | BPF_H | BPF_MEM:
1394         case BPF_LDX | BPF_W | BPF_MEM:
1395         case BPF_LDX | BPF_DW | BPF_MEM:
1396                 if (insn->src_reg == BPF_REG_10) {
1397                         ctx->flags |= EBPF_SEEN_FP;
1398                         src = MIPS_R_SP;
1399                         mem_off = insn->off + MAX_BPF_STACK;
1400                 } else {
1401                         src = ebpf_to_mips_reg(ctx, insn, src_reg_no_fp);
1402                         if (src < 0)
1403                                 return src;
1404                         mem_off = insn->off;
1405                 }
1406                 dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
1407                 if (dst < 0)
1408                         return dst;
1409                 switch (BPF_SIZE(insn->code)) {
1410                 case BPF_B:
1411                         emit_instr(ctx, lbu, dst, mem_off, src);
1412                         break;
1413                 case BPF_H:
1414                         emit_instr(ctx, lhu, dst, mem_off, src);
1415                         break;
1416                 case BPF_W:
1417                         emit_instr(ctx, lw, dst, mem_off, src);
1418                         break;
1419                 case BPF_DW:
1420                         emit_instr(ctx, ld, dst, mem_off, src);
1421                         break;
1422                 }
1423                 break;
1424
1425         case BPF_STX | BPF_B | BPF_MEM:
1426         case BPF_STX | BPF_H | BPF_MEM:
1427         case BPF_STX | BPF_W | BPF_MEM:
1428         case BPF_STX | BPF_DW | BPF_MEM:
1429         case BPF_STX | BPF_W | BPF_ATOMIC:
1430         case BPF_STX | BPF_DW | BPF_ATOMIC:
1431                 if (insn->dst_reg == BPF_REG_10) {
1432                         ctx->flags |= EBPF_SEEN_FP;
1433                         dst = MIPS_R_SP;
1434                         mem_off = insn->off + MAX_BPF_STACK;
1435                 } else {
1436                         dst = ebpf_to_mips_reg(ctx, insn, dst_reg);
1437                         if (dst < 0)
1438                                 return dst;
1439                         mem_off = insn->off;
1440                 }
1441                 src = ebpf_to_mips_reg(ctx, insn, src_reg_no_fp);
1442                 if (src < 0)
1443                         return src;
1444                 if (BPF_MODE(insn->code) == BPF_ATOMIC) {
1445                         if (insn->imm != BPF_ADD) {
1446                                 pr_err("ATOMIC OP %02x NOT HANDLED\n", insn->imm);
1447                                 return -EINVAL;
1448                         }
1449
1450                         /*
1451                          * If mem_off does not fit within the 9 bit ll/sc
1452                          * instruction immediate field, use a temp reg.
1453                          */
1454                         if (MIPS_ISA_REV >= 6 &&
1455                             (mem_off >= BIT(8) || mem_off < -BIT(8))) {
1456                                 emit_instr(ctx, daddiu, MIPS_R_T6,
1457                                                 dst, mem_off);
1458                                 mem_off = 0;
1459                                 dst = MIPS_R_T6;
1460                         }
1461                         switch (BPF_SIZE(insn->code)) {
1462                         case BPF_W:
1463                                 if (get_reg_val_type(ctx, this_idx, insn->src_reg) == REG_32BIT) {
1464                                         emit_instr(ctx, sll, MIPS_R_AT, src, 0);
1465                                         src = MIPS_R_AT;
1466                                 }
1467                                 emit_instr(ctx, ll, MIPS_R_T8, mem_off, dst);
1468                                 emit_instr(ctx, addu, MIPS_R_T8, MIPS_R_T8, src);
1469                                 emit_instr(ctx, sc, MIPS_R_T8, mem_off, dst);
1470                                 /*
1471                                  * On failure back up to LL (-4
1472                                  * instructions of 4 bytes each
1473                                  */
1474                                 emit_instr(ctx, beq, MIPS_R_T8, MIPS_R_ZERO, -4 * 4);
1475                                 emit_instr(ctx, nop);
1476                                 break;
1477                         case BPF_DW:
1478                                 if (get_reg_val_type(ctx, this_idx, insn->src_reg) == REG_32BIT) {
1479                                         emit_instr(ctx, daddu, MIPS_R_AT, src, MIPS_R_ZERO);
1480                                         emit_instr(ctx, dinsu, MIPS_R_AT, MIPS_R_ZERO, 32, 32);
1481                                         src = MIPS_R_AT;
1482                                 }
1483                                 emit_instr(ctx, lld, MIPS_R_T8, mem_off, dst);
1484                                 emit_instr(ctx, daddu, MIPS_R_T8, MIPS_R_T8, src);
1485                                 emit_instr(ctx, scd, MIPS_R_T8, mem_off, dst);
1486                                 emit_instr(ctx, beq, MIPS_R_T8, MIPS_R_ZERO, -4 * 4);
1487                                 emit_instr(ctx, nop);
1488                                 break;
1489                         }
1490                 } else { /* BPF_MEM */
1491                         switch (BPF_SIZE(insn->code)) {
1492                         case BPF_B:
1493                                 emit_instr(ctx, sb, src, mem_off, dst);
1494                                 break;
1495                         case BPF_H:
1496                                 emit_instr(ctx, sh, src, mem_off, dst);
1497                                 break;
1498                         case BPF_W:
1499                                 emit_instr(ctx, sw, src, mem_off, dst);
1500                                 break;
1501                         case BPF_DW:
1502                                 if (get_reg_val_type(ctx, this_idx, insn->src_reg) == REG_32BIT) {
1503                                         emit_instr(ctx, daddu, MIPS_R_AT, src, MIPS_R_ZERO);
1504                                         emit_instr(ctx, dinsu, MIPS_R_AT, MIPS_R_ZERO, 32, 32);
1505                                         src = MIPS_R_AT;
1506                                 }
1507                                 emit_instr(ctx, sd, src, mem_off, dst);
1508                                 break;
1509                         }
1510                 }
1511                 break;
1512
1513         default:
1514                 pr_err("NOT HANDLED %d - (%02x)\n",
1515                        this_idx, (unsigned int)insn->code);
1516                 return -EINVAL;
1517         }
1518         return 1;
1519 }
1520
1521 #define RVT_VISITED_MASK 0xc000000000000000ull
1522 #define RVT_FALL_THROUGH 0x4000000000000000ull
1523 #define RVT_BRANCH_TAKEN 0x8000000000000000ull
1524 #define RVT_DONE (RVT_FALL_THROUGH | RVT_BRANCH_TAKEN)
1525
1526 static int build_int_body(struct jit_ctx *ctx)
1527 {
1528         const struct bpf_prog *prog = ctx->skf;
1529         const struct bpf_insn *insn;
1530         int i, r;
1531
1532         for (i = 0; i < prog->len; ) {
1533                 insn = prog->insnsi + i;
1534                 if ((ctx->reg_val_types[i] & RVT_VISITED_MASK) == 0) {
1535                         /* dead instruction, don't emit it. */
1536                         i++;
1537                         continue;
1538                 }
1539
1540                 if (ctx->target == NULL)
1541                         ctx->offsets[i] = (ctx->offsets[i] & OFFSETS_B_CONV) | (ctx->idx * 4);
1542
1543                 r = build_one_insn(insn, ctx, i, prog->len);
1544                 if (r < 0)
1545                         return r;
1546                 i += r;
1547         }
1548         /* epilogue offset */
1549         if (ctx->target == NULL)
1550                 ctx->offsets[i] = ctx->idx * 4;
1551
1552         /*
1553          * All exits have an offset of the epilogue, some offsets may
1554          * not have been set due to banch-around threading, so set
1555          * them now.
1556          */
1557         if (ctx->target == NULL)
1558                 for (i = 0; i < prog->len; i++) {
1559                         insn = prog->insnsi + i;
1560                         if (insn->code == (BPF_JMP | BPF_EXIT))
1561                                 ctx->offsets[i] = ctx->idx * 4;
1562                 }
1563         return 0;
1564 }
1565
1566 /* return the last idx processed, or negative for error */
1567 static int reg_val_propagate_range(struct jit_ctx *ctx, u64 initial_rvt,
1568                                    int start_idx, bool follow_taken)
1569 {
1570         const struct bpf_prog *prog = ctx->skf;
1571         const struct bpf_insn *insn;
1572         u64 exit_rvt = initial_rvt;
1573         u64 *rvt = ctx->reg_val_types;
1574         int idx;
1575         int reg;
1576
1577         for (idx = start_idx; idx < prog->len; idx++) {
1578                 rvt[idx] = (rvt[idx] & RVT_VISITED_MASK) | exit_rvt;
1579                 insn = prog->insnsi + idx;
1580                 switch (BPF_CLASS(insn->code)) {
1581                 case BPF_ALU:
1582                         switch (BPF_OP(insn->code)) {
1583                         case BPF_ADD:
1584                         case BPF_SUB:
1585                         case BPF_MUL:
1586                         case BPF_DIV:
1587                         case BPF_OR:
1588                         case BPF_AND:
1589                         case BPF_LSH:
1590                         case BPF_RSH:
1591                         case BPF_NEG:
1592                         case BPF_MOD:
1593                         case BPF_XOR:
1594                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT);
1595                                 break;
1596                         case BPF_MOV:
1597                                 if (BPF_SRC(insn->code)) {
1598                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT);
1599                                 } else {
1600                                         /* IMM to REG move*/
1601                                         if (insn->imm >= 0)
1602                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT_POS);
1603                                         else
1604                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT);
1605                                 }
1606                                 break;
1607                         case BPF_END:
1608                                 if (insn->imm == 64)
1609                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT);
1610                                 else if (insn->imm == 32)
1611                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT);
1612                                 else /* insn->imm == 16 */
1613                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT_POS);
1614                                 break;
1615                         }
1616                         rvt[idx] |= RVT_DONE;
1617                         break;
1618                 case BPF_ALU64:
1619                         switch (BPF_OP(insn->code)) {
1620                         case BPF_MOV:
1621                                 if (BPF_SRC(insn->code)) {
1622                                         /* REG to REG move*/
1623                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT);
1624                                 } else {
1625                                         /* IMM to REG move*/
1626                                         if (insn->imm >= 0)
1627                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT_POS);
1628                                         else
1629                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT_32BIT);
1630                                 }
1631                                 break;
1632                         default:
1633                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT);
1634                         }
1635                         rvt[idx] |= RVT_DONE;
1636                         break;
1637                 case BPF_LD:
1638                         switch (BPF_SIZE(insn->code)) {
1639                         case BPF_DW:
1640                                 if (BPF_MODE(insn->code) == BPF_IMM) {
1641                                         s64 val;
1642
1643                                         val = (s64)((u32)insn->imm | ((u64)(insn + 1)->imm << 32));
1644                                         if (val > 0 && val <= S32_MAX)
1645                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT_POS);
1646                                         else if (val >= S32_MIN && val <= S32_MAX)
1647                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT_32BIT);
1648                                         else
1649                                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT);
1650                                         rvt[idx] |= RVT_DONE;
1651                                         idx++;
1652                                 } else {
1653                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT);
1654                                 }
1655                                 break;
1656                         case BPF_B:
1657                         case BPF_H:
1658                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT_POS);
1659                                 break;
1660                         case BPF_W:
1661                                 if (BPF_MODE(insn->code) == BPF_IMM)
1662                                         set_reg_val_type(&exit_rvt, insn->dst_reg,
1663                                                          insn->imm >= 0 ? REG_32BIT_POS : REG_32BIT);
1664                                 else
1665                                         set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT);
1666                                 break;
1667                         }
1668                         rvt[idx] |= RVT_DONE;
1669                         break;
1670                 case BPF_LDX:
1671                         switch (BPF_SIZE(insn->code)) {
1672                         case BPF_DW:
1673                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_64BIT);
1674                                 break;
1675                         case BPF_B:
1676                         case BPF_H:
1677                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT_POS);
1678                                 break;
1679                         case BPF_W:
1680                                 set_reg_val_type(&exit_rvt, insn->dst_reg, REG_32BIT);
1681                                 break;
1682                         }
1683                         rvt[idx] |= RVT_DONE;
1684                         break;
1685                 case BPF_JMP:
1686                         switch (BPF_OP(insn->code)) {
1687                         case BPF_EXIT:
1688                                 rvt[idx] = RVT_DONE | exit_rvt;
1689                                 rvt[prog->len] = exit_rvt;
1690                                 return idx;
1691                         case BPF_JA:
1692                                 rvt[idx] |= RVT_DONE;
1693                                 idx += insn->off;
1694                                 break;
1695                         case BPF_JEQ:
1696                         case BPF_JGT:
1697                         case BPF_JGE:
1698                         case BPF_JLT:
1699                         case BPF_JLE:
1700                         case BPF_JSET:
1701                         case BPF_JNE:
1702                         case BPF_JSGT:
1703                         case BPF_JSGE:
1704                         case BPF_JSLT:
1705                         case BPF_JSLE:
1706                                 if (follow_taken) {
1707                                         rvt[idx] |= RVT_BRANCH_TAKEN;
1708                                         idx += insn->off;
1709                                         follow_taken = false;
1710                                 } else {
1711                                         rvt[idx] |= RVT_FALL_THROUGH;
1712                                 }
1713                                 break;
1714                         case BPF_CALL:
1715                                 set_reg_val_type(&exit_rvt, BPF_REG_0, REG_64BIT);
1716                                 /* Upon call return, argument registers are clobbered. */
1717                                 for (reg = BPF_REG_0; reg <= BPF_REG_5; reg++)
1718                                         set_reg_val_type(&exit_rvt, reg, REG_64BIT);
1719
1720                                 rvt[idx] |= RVT_DONE;
1721                                 break;
1722                         default:
1723                                 WARN(1, "Unhandled BPF_JMP case.\n");
1724                                 rvt[idx] |= RVT_DONE;
1725                                 break;
1726                         }
1727                         break;
1728                 default:
1729                         rvt[idx] |= RVT_DONE;
1730                         break;
1731                 }
1732         }
1733         return idx;
1734 }
1735
1736 /*
1737  * Track the value range (i.e. 32-bit vs. 64-bit) of each register at
1738  * each eBPF insn.  This allows unneeded sign and zero extension
1739  * operations to be omitted.
1740  *
1741  * Doesn't handle yet confluence of control paths with conflicting
1742  * ranges, but it is good enough for most sane code.
1743  */
1744 static int reg_val_propagate(struct jit_ctx *ctx)
1745 {
1746         const struct bpf_prog *prog = ctx->skf;
1747         u64 exit_rvt;
1748         int reg;
1749         int i;
1750
1751         /*
1752          * 11 registers * 3 bits/reg leaves top bits free for other
1753          * uses.  Bit-62..63 used to see if we have visited an insn.
1754          */
1755         exit_rvt = 0;
1756
1757         /* Upon entry, argument registers are 64-bit. */
1758         for (reg = BPF_REG_1; reg <= BPF_REG_5; reg++)
1759                 set_reg_val_type(&exit_rvt, reg, REG_64BIT);
1760
1761         /*
1762          * First follow all conditional branches on the fall-through
1763          * edge of control flow..
1764          */
1765         reg_val_propagate_range(ctx, exit_rvt, 0, false);
1766 restart_search:
1767         /*
1768          * Then repeatedly find the first conditional branch where
1769          * both edges of control flow have not been taken, and follow
1770          * the branch taken edge.  We will end up restarting the
1771          * search once per conditional branch insn.
1772          */
1773         for (i = 0; i < prog->len; i++) {
1774                 u64 rvt = ctx->reg_val_types[i];
1775
1776                 if ((rvt & RVT_VISITED_MASK) == RVT_DONE ||
1777                     (rvt & RVT_VISITED_MASK) == 0)
1778                         continue;
1779                 if ((rvt & RVT_VISITED_MASK) == RVT_FALL_THROUGH) {
1780                         reg_val_propagate_range(ctx, rvt & ~RVT_VISITED_MASK, i, true);
1781                 } else { /* RVT_BRANCH_TAKEN */
1782                         WARN(1, "Unexpected RVT_BRANCH_TAKEN case.\n");
1783                         reg_val_propagate_range(ctx, rvt & ~RVT_VISITED_MASK, i, false);
1784                 }
1785                 goto restart_search;
1786         }
1787         /*
1788          * Eventually all conditional branches have been followed on
1789          * both branches and we are done.  Any insn that has not been
1790          * visited at this point is dead.
1791          */
1792
1793         return 0;
1794 }
1795
1796 static void jit_fill_hole(void *area, unsigned int size)
1797 {
1798         u32 *p;
1799
1800         /* We are guaranteed to have aligned memory. */
1801         for (p = area; size >= sizeof(u32); size -= sizeof(u32))
1802                 uasm_i_break(&p, BRK_BUG); /* Increments p */
1803 }
1804
1805 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
1806 {
1807         struct bpf_prog *orig_prog = prog;
1808         bool tmp_blinded = false;
1809         struct bpf_prog *tmp;
1810         struct bpf_binary_header *header = NULL;
1811         struct jit_ctx ctx;
1812         unsigned int image_size;
1813         u8 *image_ptr;
1814
1815         if (!prog->jit_requested)
1816                 return prog;
1817
1818         tmp = bpf_jit_blind_constants(prog);
1819         /* If blinding was requested and we failed during blinding,
1820          * we must fall back to the interpreter.
1821          */
1822         if (IS_ERR(tmp))
1823                 return orig_prog;
1824         if (tmp != prog) {
1825                 tmp_blinded = true;
1826                 prog = tmp;
1827         }
1828
1829         memset(&ctx, 0, sizeof(ctx));
1830
1831         preempt_disable();
1832         switch (current_cpu_type()) {
1833         case CPU_CAVIUM_OCTEON:
1834         case CPU_CAVIUM_OCTEON_PLUS:
1835         case CPU_CAVIUM_OCTEON2:
1836         case CPU_CAVIUM_OCTEON3:
1837                 ctx.use_bbit_insns = 1;
1838                 break;
1839         default:
1840                 ctx.use_bbit_insns = 0;
1841         }
1842         preempt_enable();
1843
1844         ctx.offsets = kcalloc(prog->len + 1, sizeof(*ctx.offsets), GFP_KERNEL);
1845         if (ctx.offsets == NULL)
1846                 goto out_err;
1847
1848         ctx.reg_val_types = kcalloc(prog->len + 1, sizeof(*ctx.reg_val_types), GFP_KERNEL);
1849         if (ctx.reg_val_types == NULL)
1850                 goto out_err;
1851
1852         ctx.skf = prog;
1853
1854         if (reg_val_propagate(&ctx))
1855                 goto out_err;
1856
1857         /*
1858          * First pass discovers used resources and instruction offsets
1859          * assuming short branches are used.
1860          */
1861         if (build_int_body(&ctx))
1862                 goto out_err;
1863
1864         /*
1865          * If no calls are made (EBPF_SAVE_RA), then tail call count
1866          * in $v1, else we must save in n$s4.
1867          */
1868         if (ctx.flags & EBPF_SEEN_TC) {
1869                 if (ctx.flags & EBPF_SAVE_RA)
1870                         ctx.flags |= EBPF_SAVE_S4;
1871                 else
1872                         ctx.flags |= EBPF_TCC_IN_V1;
1873         }
1874
1875         /*
1876          * Second pass generates offsets, if any branches are out of
1877          * range a jump-around long sequence is generated, and we have
1878          * to try again from the beginning to generate the new
1879          * offsets.  This is done until no additional conversions are
1880          * necessary.
1881          */
1882         do {
1883                 ctx.idx = 0;
1884                 ctx.gen_b_offsets = 1;
1885                 ctx.long_b_conversion = 0;
1886                 if (gen_int_prologue(&ctx))
1887                         goto out_err;
1888                 if (build_int_body(&ctx))
1889                         goto out_err;
1890                 if (build_int_epilogue(&ctx, MIPS_R_RA))
1891                         goto out_err;
1892         } while (ctx.long_b_conversion);
1893
1894         image_size = 4 * ctx.idx;
1895
1896         header = bpf_jit_binary_alloc(image_size, &image_ptr,
1897                                       sizeof(u32), jit_fill_hole);
1898         if (header == NULL)
1899                 goto out_err;
1900
1901         ctx.target = (u32 *)image_ptr;
1902
1903         /* Third pass generates the code */
1904         ctx.idx = 0;
1905         if (gen_int_prologue(&ctx))
1906                 goto out_err;
1907         if (build_int_body(&ctx))
1908                 goto out_err;
1909         if (build_int_epilogue(&ctx, MIPS_R_RA))
1910                 goto out_err;
1911
1912         /* Update the icache */
1913         flush_icache_range((unsigned long)ctx.target,
1914                            (unsigned long)&ctx.target[ctx.idx]);
1915
1916         if (bpf_jit_enable > 1)
1917                 /* Dump JIT code */
1918                 bpf_jit_dump(prog->len, image_size, 2, ctx.target);
1919
1920         bpf_jit_binary_lock_ro(header);
1921         prog->bpf_func = (void *)ctx.target;
1922         prog->jited = 1;
1923         prog->jited_len = image_size;
1924 out_normal:
1925         if (tmp_blinded)
1926                 bpf_jit_prog_release_other(prog, prog == orig_prog ?
1927                                            tmp : orig_prog);
1928         kfree(ctx.offsets);
1929         kfree(ctx.reg_val_types);
1930
1931         return prog;
1932
1933 out_err:
1934         prog = orig_prog;
1935         if (header)
1936                 bpf_jit_binary_free(header);
1937         goto out_normal;
1938 }