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