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