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