arch/mips/net/ebpf_jit.c

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