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