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