~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/arch/mips/net/ebpf_jit.c

Version: ~ [ linux-4.18 ] ~ [ linux-4.17.14 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.62 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.119 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.147 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.118 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.57 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.27.62 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~ [ linux-next-20180810 ] ~ [ linux-next-20180813 ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp