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