xref: /linux/arch/mips/net/bpf_jit_comp32.c (revision 06d07429858317ded2db7986113a9e0129cd599b) 
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Just-In-Time compiler for eBPF bytecode on MIPS.
4  * Implementation of JIT functions for 32-bit CPUs.
5  *
6  * Copyright (c) 2021 Anyfi Networks AB.
7  * Author: Johan Almbladh <johan.almbladh@gmail.com>
8  *
9  * Based on code and ideas from
10  * Copyright (c) 2017 Cavium, Inc.
11  * Copyright (c) 2017 Shubham Bansal <illusionist.neo@gmail.com>
12  * Copyright (c) 2011 Mircea Gherzan <mgherzan@gmail.com>
13  */
14 
15 #include <linux/math64.h>
16 #include <linux/errno.h>
17 #include <linux/filter.h>
18 #include <linux/bpf.h>
19 #include <asm/cpu-features.h>
20 #include <asm/isa-rev.h>
21 #include <asm/uasm.h>
22 
23 #include "bpf_jit_comp.h"
24 
25 /* MIPS a4-a7 are not available in the o32 ABI */
26 #undef MIPS_R_A4
27 #undef MIPS_R_A5
28 #undef MIPS_R_A6
29 #undef MIPS_R_A7
30 
31 /* Stack is 8-byte aligned in o32 ABI */
32 #define MIPS_STACK_ALIGNMENT 8
33 
34 /*
35  * The top 16 bytes of a stack frame is reserved for the callee in O32 ABI.
36  * This corresponds to stack space for register arguments a0-a3.
37  */
38 #define JIT_RESERVED_STACK 16
39 
40 /* Temporary 64-bit register used by JIT */
41 #define JIT_REG_TMP MAX_BPF_JIT_REG
42 
43 /*
44  * Number of prologue bytes to skip when doing a tail call.
45  * Tail call count (TCC) initialization (8 bytes) always, plus
46  * R0-to-v0 assignment (4 bytes) if big endian.
47  */
48 #ifdef __BIG_ENDIAN
49 #define JIT_TCALL_SKIP 12
50 #else
51 #define JIT_TCALL_SKIP 8
52 #endif
53 
54 /* CPU registers holding the callee return value */
55 #define JIT_RETURN_REGS	  \
56 	(BIT(MIPS_R_V0) | \
57 	 BIT(MIPS_R_V1))
58 
59 /* CPU registers arguments passed to callee directly */
60 #define JIT_ARG_REGS      \
61 	(BIT(MIPS_R_A0) | \
62 	 BIT(MIPS_R_A1) | \
63 	 BIT(MIPS_R_A2) | \
64 	 BIT(MIPS_R_A3))
65 
66 /* CPU register arguments passed to callee on stack */
67 #define JIT_STACK_REGS    \
68 	(BIT(MIPS_R_T0) | \
69 	 BIT(MIPS_R_T1) | \
70 	 BIT(MIPS_R_T2) | \
71 	 BIT(MIPS_R_T3) | \
72 	 BIT(MIPS_R_T4) | \
73 	 BIT(MIPS_R_T5))
74 
75 /* Caller-saved CPU registers */
76 #define JIT_CALLER_REGS    \
77 	(JIT_RETURN_REGS | \
78 	 JIT_ARG_REGS    | \
79 	 JIT_STACK_REGS)
80 
81 /* Callee-saved CPU registers */
82 #define JIT_CALLEE_REGS   \
83 	(BIT(MIPS_R_S0) | \
84 	 BIT(MIPS_R_S1) | \
85 	 BIT(MIPS_R_S2) | \
86 	 BIT(MIPS_R_S3) | \
87 	 BIT(MIPS_R_S4) | \
88 	 BIT(MIPS_R_S5) | \
89 	 BIT(MIPS_R_S6) | \
90 	 BIT(MIPS_R_S7) | \
91 	 BIT(MIPS_R_GP) | \
92 	 BIT(MIPS_R_FP) | \
93 	 BIT(MIPS_R_RA))
94 
95 /*
96  * Mapping of 64-bit eBPF registers to 32-bit native MIPS registers.
97  *
98  * 1) Native register pairs are ordered according to CPU endianness, following
99  *    the MIPS convention for passing 64-bit arguments and return values.
100  * 2) The eBPF return value, arguments and callee-saved registers are mapped
101  *    to their native MIPS equivalents.
102  * 3) Since the 32 highest bits in the eBPF FP register are always zero,
103  *    only one general-purpose register is actually needed for the mapping.
104  *    We use the fp register for this purpose, and map the highest bits to
105  *    the MIPS register r0 (zero).
106  * 4) We use the MIPS gp and at registers as internal temporary registers
107  *    for constant blinding. The gp register is callee-saved.
108  * 5) One 64-bit temporary register is mapped for use when sign-extending
109  *    immediate operands. MIPS registers t6-t9 are available to the JIT
110  *    for as temporaries when implementing complex 64-bit operations.
111  *
112  * With this scheme all eBPF registers are being mapped to native MIPS
113  * registers without having to use any stack scratch space. The direct
114  * register mapping (2) simplifies the handling of function calls.
115  */
116 static const u8 bpf2mips32[][2] = {
117 	/* Return value from in-kernel function, and exit value from eBPF */
118 	[BPF_REG_0] = {MIPS_R_V1, MIPS_R_V0},
119 	/* Arguments from eBPF program to in-kernel function */
120 	[BPF_REG_1] = {MIPS_R_A1, MIPS_R_A0},
121 	[BPF_REG_2] = {MIPS_R_A3, MIPS_R_A2},
122 	/* Remaining arguments, to be passed on the stack per O32 ABI */
123 	[BPF_REG_3] = {MIPS_R_T1, MIPS_R_T0},
124 	[BPF_REG_4] = {MIPS_R_T3, MIPS_R_T2},
125 	[BPF_REG_5] = {MIPS_R_T5, MIPS_R_T4},
126 	/* Callee-saved registers that in-kernel function will preserve */
127 	[BPF_REG_6] = {MIPS_R_S1, MIPS_R_S0},
128 	[BPF_REG_7] = {MIPS_R_S3, MIPS_R_S2},
129 	[BPF_REG_8] = {MIPS_R_S5, MIPS_R_S4},
130 	[BPF_REG_9] = {MIPS_R_S7, MIPS_R_S6},
131 	/* Read-only frame pointer to access the eBPF stack */
132 #ifdef __BIG_ENDIAN
133 	[BPF_REG_FP] = {MIPS_R_FP, MIPS_R_ZERO},
134 #else
135 	[BPF_REG_FP] = {MIPS_R_ZERO, MIPS_R_FP},
136 #endif
137 	/* Temporary register for blinding constants */
138 	[BPF_REG_AX] = {MIPS_R_GP, MIPS_R_AT},
139 	/* Temporary register for internal JIT use */
140 	[JIT_REG_TMP] = {MIPS_R_T7, MIPS_R_T6},
141 };
142 
143 /* Get low CPU register for a 64-bit eBPF register mapping */
lo(const u8 reg[])144 static inline u8 lo(const u8 reg[])
145 {
146 #ifdef __BIG_ENDIAN
147 	return reg[0];
148 #else
149 	return reg[1];
150 #endif
151 }
152 
153 /* Get high CPU register for a 64-bit eBPF register mapping */
hi(const u8 reg[])154 static inline u8 hi(const u8 reg[])
155 {
156 #ifdef __BIG_ENDIAN
157 	return reg[1];
158 #else
159 	return reg[0];
160 #endif
161 }
162 
163 /*
164  * Mark a 64-bit CPU register pair as clobbered, it needs to be
165  * saved/restored by the program if callee-saved.
166  */
clobber_reg64(struct jit_context * ctx,const u8 reg[])167 static void clobber_reg64(struct jit_context *ctx, const u8 reg[])
168 {
169 	clobber_reg(ctx, reg[0]);
170 	clobber_reg(ctx, reg[1]);
171 }
172 
173 /* dst = imm (sign-extended) */
emit_mov_se_i64(struct jit_context * ctx,const u8 dst[],s32 imm)174 static void emit_mov_se_i64(struct jit_context *ctx, const u8 dst[], s32 imm)
175 {
176 	emit_mov_i(ctx, lo(dst), imm);
177 	if (imm < 0)
178 		emit(ctx, addiu, hi(dst), MIPS_R_ZERO, -1);
179 	else
180 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
181 	clobber_reg64(ctx, dst);
182 }
183 
184 /* Zero extension, if verifier does not do it for us  */
emit_zext_ver(struct jit_context * ctx,const u8 dst[])185 static void emit_zext_ver(struct jit_context *ctx, const u8 dst[])
186 {
187 	if (!ctx->program->aux->verifier_zext) {
188 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
189 		clobber_reg(ctx, hi(dst));
190 	}
191 }
192 
193 /* Load delay slot, if ISA mandates it */
emit_load_delay(struct jit_context * ctx)194 static void emit_load_delay(struct jit_context *ctx)
195 {
196 	if (!cpu_has_mips_2_3_4_5_r)
197 		emit(ctx, nop);
198 }
199 
200 /* ALU immediate operation (64-bit) */
emit_alu_i64(struct jit_context * ctx,const u8 dst[],s32 imm,u8 op)201 static void emit_alu_i64(struct jit_context *ctx,
202 			 const u8 dst[], s32 imm, u8 op)
203 {
204 	u8 src = MIPS_R_T6;
205 
206 	/*
207 	 * ADD/SUB with all but the max negative imm can be handled by
208 	 * inverting the operation and the imm value, saving one insn.
209 	 */
210 	if (imm > S32_MIN && imm < 0)
211 		switch (op) {
212 		case BPF_ADD:
213 			op = BPF_SUB;
214 			imm = -imm;
215 			break;
216 		case BPF_SUB:
217 			op = BPF_ADD;
218 			imm = -imm;
219 			break;
220 		}
221 
222 	/* Move immediate to temporary register */
223 	emit_mov_i(ctx, src, imm);
224 
225 	switch (op) {
226 	/* dst = dst + imm */
227 	case BPF_ADD:
228 		emit(ctx, addu, lo(dst), lo(dst), src);
229 		emit(ctx, sltu, MIPS_R_T9, lo(dst), src);
230 		emit(ctx, addu, hi(dst), hi(dst), MIPS_R_T9);
231 		if (imm < 0)
232 			emit(ctx, addiu, hi(dst), hi(dst), -1);
233 		break;
234 	/* dst = dst - imm */
235 	case BPF_SUB:
236 		emit(ctx, sltu, MIPS_R_T9, lo(dst), src);
237 		emit(ctx, subu, lo(dst), lo(dst), src);
238 		emit(ctx, subu, hi(dst), hi(dst), MIPS_R_T9);
239 		if (imm < 0)
240 			emit(ctx, addiu, hi(dst), hi(dst), 1);
241 		break;
242 	/* dst = dst | imm */
243 	case BPF_OR:
244 		emit(ctx, or, lo(dst), lo(dst), src);
245 		if (imm < 0)
246 			emit(ctx, addiu, hi(dst), MIPS_R_ZERO, -1);
247 		break;
248 	/* dst = dst & imm */
249 	case BPF_AND:
250 		emit(ctx, and, lo(dst), lo(dst), src);
251 		if (imm >= 0)
252 			emit(ctx, move, hi(dst), MIPS_R_ZERO);
253 		break;
254 	/* dst = dst ^ imm */
255 	case BPF_XOR:
256 		emit(ctx, xor, lo(dst), lo(dst), src);
257 		if (imm < 0) {
258 			emit(ctx, subu, hi(dst), MIPS_R_ZERO, hi(dst));
259 			emit(ctx, addiu, hi(dst), hi(dst), -1);
260 		}
261 		break;
262 	}
263 	clobber_reg64(ctx, dst);
264 }
265 
266 /* ALU register operation (64-bit) */
emit_alu_r64(struct jit_context * ctx,const u8 dst[],const u8 src[],u8 op)267 static void emit_alu_r64(struct jit_context *ctx,
268 			 const u8 dst[], const u8 src[], u8 op)
269 {
270 	switch (BPF_OP(op)) {
271 	/* dst = dst + src */
272 	case BPF_ADD:
273 		if (src == dst) {
274 			emit(ctx, srl, MIPS_R_T9, lo(dst), 31);
275 			emit(ctx, addu, lo(dst), lo(dst), lo(dst));
276 		} else {
277 			emit(ctx, addu, lo(dst), lo(dst), lo(src));
278 			emit(ctx, sltu, MIPS_R_T9, lo(dst), lo(src));
279 		}
280 		emit(ctx, addu, hi(dst), hi(dst), hi(src));
281 		emit(ctx, addu, hi(dst), hi(dst), MIPS_R_T9);
282 		break;
283 	/* dst = dst - src */
284 	case BPF_SUB:
285 		emit(ctx, sltu, MIPS_R_T9, lo(dst), lo(src));
286 		emit(ctx, subu, lo(dst), lo(dst), lo(src));
287 		emit(ctx, subu, hi(dst), hi(dst), hi(src));
288 		emit(ctx, subu, hi(dst), hi(dst), MIPS_R_T9);
289 		break;
290 	/* dst = dst | src */
291 	case BPF_OR:
292 		emit(ctx, or, lo(dst), lo(dst), lo(src));
293 		emit(ctx, or, hi(dst), hi(dst), hi(src));
294 		break;
295 	/* dst = dst & src */
296 	case BPF_AND:
297 		emit(ctx, and, lo(dst), lo(dst), lo(src));
298 		emit(ctx, and, hi(dst), hi(dst), hi(src));
299 		break;
300 	/* dst = dst ^ src */
301 	case BPF_XOR:
302 		emit(ctx, xor, lo(dst), lo(dst), lo(src));
303 		emit(ctx, xor, hi(dst), hi(dst), hi(src));
304 		break;
305 	}
306 	clobber_reg64(ctx, dst);
307 }
308 
309 /* ALU invert (64-bit) */
emit_neg_i64(struct jit_context * ctx,const u8 dst[])310 static void emit_neg_i64(struct jit_context *ctx, const u8 dst[])
311 {
312 	emit(ctx, sltu, MIPS_R_T9, MIPS_R_ZERO, lo(dst));
313 	emit(ctx, subu, lo(dst), MIPS_R_ZERO, lo(dst));
314 	emit(ctx, subu, hi(dst), MIPS_R_ZERO, hi(dst));
315 	emit(ctx, subu, hi(dst), hi(dst), MIPS_R_T9);
316 
317 	clobber_reg64(ctx, dst);
318 }
319 
320 /* ALU shift immediate (64-bit) */
emit_shift_i64(struct jit_context * ctx,const u8 dst[],u32 imm,u8 op)321 static void emit_shift_i64(struct jit_context *ctx,
322 			   const u8 dst[], u32 imm, u8 op)
323 {
324 	switch (BPF_OP(op)) {
325 	/* dst = dst << imm */
326 	case BPF_LSH:
327 		if (imm < 32) {
328 			emit(ctx, srl, MIPS_R_T9, lo(dst), 32 - imm);
329 			emit(ctx, sll, lo(dst), lo(dst), imm);
330 			emit(ctx, sll, hi(dst), hi(dst), imm);
331 			emit(ctx, or, hi(dst), hi(dst), MIPS_R_T9);
332 		} else {
333 			emit(ctx, sll, hi(dst), lo(dst), imm - 32);
334 			emit(ctx, move, lo(dst), MIPS_R_ZERO);
335 		}
336 		break;
337 	/* dst = dst >> imm */
338 	case BPF_RSH:
339 		if (imm < 32) {
340 			emit(ctx, sll, MIPS_R_T9, hi(dst), 32 - imm);
341 			emit(ctx, srl, lo(dst), lo(dst), imm);
342 			emit(ctx, srl, hi(dst), hi(dst), imm);
343 			emit(ctx, or, lo(dst), lo(dst), MIPS_R_T9);
344 		} else {
345 			emit(ctx, srl, lo(dst), hi(dst), imm - 32);
346 			emit(ctx, move, hi(dst), MIPS_R_ZERO);
347 		}
348 		break;
349 	/* dst = dst >> imm (arithmetic) */
350 	case BPF_ARSH:
351 		if (imm < 32) {
352 			emit(ctx, sll, MIPS_R_T9, hi(dst), 32 - imm);
353 			emit(ctx, srl, lo(dst), lo(dst), imm);
354 			emit(ctx, sra, hi(dst), hi(dst), imm);
355 			emit(ctx, or, lo(dst), lo(dst), MIPS_R_T9);
356 		} else {
357 			emit(ctx, sra, lo(dst), hi(dst), imm - 32);
358 			emit(ctx, sra, hi(dst), hi(dst), 31);
359 		}
360 		break;
361 	}
362 	clobber_reg64(ctx, dst);
363 }
364 
365 /* ALU shift register (64-bit) */
emit_shift_r64(struct jit_context * ctx,const u8 dst[],u8 src,u8 op)366 static void emit_shift_r64(struct jit_context *ctx,
367 			   const u8 dst[], u8 src, u8 op)
368 {
369 	u8 t1 = MIPS_R_T8;
370 	u8 t2 = MIPS_R_T9;
371 
372 	emit(ctx, andi, t1, src, 32);              /* t1 = src & 32          */
373 	emit(ctx, beqz, t1, 16);                   /* PC += 16 if t1 == 0    */
374 	emit(ctx, nor, t2, src, MIPS_R_ZERO);      /* t2 = ~src (delay slot) */
375 
376 	switch (BPF_OP(op)) {
377 	/* dst = dst << src */
378 	case BPF_LSH:
379 		/* Next: shift >= 32 */
380 		emit(ctx, sllv, hi(dst), lo(dst), src);    /* dh = dl << src */
381 		emit(ctx, move, lo(dst), MIPS_R_ZERO);     /* dl = 0         */
382 		emit(ctx, b, 20);                          /* PC += 20       */
383 		/* +16: shift < 32 */
384 		emit(ctx, srl, t1, lo(dst), 1);            /* t1 = dl >> 1   */
385 		emit(ctx, srlv, t1, t1, t2);               /* t1 = t1 >> t2  */
386 		emit(ctx, sllv, lo(dst), lo(dst), src);    /* dl = dl << src */
387 		emit(ctx, sllv, hi(dst), hi(dst), src);    /* dh = dh << src */
388 		emit(ctx, or, hi(dst), hi(dst), t1);       /* dh = dh | t1   */
389 		break;
390 	/* dst = dst >> src */
391 	case BPF_RSH:
392 		/* Next: shift >= 32 */
393 		emit(ctx, srlv, lo(dst), hi(dst), src);    /* dl = dh >> src */
394 		emit(ctx, move, hi(dst), MIPS_R_ZERO);     /* dh = 0         */
395 		emit(ctx, b, 20);                          /* PC += 20       */
396 		/* +16: shift < 32 */
397 		emit(ctx, sll, t1, hi(dst), 1);            /* t1 = dl << 1   */
398 		emit(ctx, sllv, t1, t1, t2);               /* t1 = t1 << t2  */
399 		emit(ctx, srlv, lo(dst), lo(dst), src);    /* dl = dl >> src */
400 		emit(ctx, srlv, hi(dst), hi(dst), src);    /* dh = dh >> src */
401 		emit(ctx, or, lo(dst), lo(dst), t1);       /* dl = dl | t1   */
402 		break;
403 	/* dst = dst >> src (arithmetic) */
404 	case BPF_ARSH:
405 		/* Next: shift >= 32 */
406 		emit(ctx, srav, lo(dst), hi(dst), src);   /* dl = dh >>a src */
407 		emit(ctx, sra, hi(dst), hi(dst), 31);     /* dh = dh >>a 31  */
408 		emit(ctx, b, 20);                         /* PC += 20        */
409 		/* +16: shift < 32 */
410 		emit(ctx, sll, t1, hi(dst), 1);           /* t1 = dl << 1    */
411 		emit(ctx, sllv, t1, t1, t2);              /* t1 = t1 << t2   */
412 		emit(ctx, srlv, lo(dst), lo(dst), src);   /* dl = dl >>a src */
413 		emit(ctx, srav, hi(dst), hi(dst), src);   /* dh = dh >> src  */
414 		emit(ctx, or, lo(dst), lo(dst), t1);      /* dl = dl | t1    */
415 		break;
416 	}
417 
418 	/* +20: Done */
419 	clobber_reg64(ctx, dst);
420 }
421 
422 /* ALU mul immediate (64x32-bit) */
emit_mul_i64(struct jit_context * ctx,const u8 dst[],s32 imm)423 static void emit_mul_i64(struct jit_context *ctx, const u8 dst[], s32 imm)
424 {
425 	u8 src = MIPS_R_T6;
426 	u8 tmp = MIPS_R_T9;
427 
428 	switch (imm) {
429 	/* dst = dst * 1 is a no-op */
430 	case 1:
431 		break;
432 	/* dst = dst * -1 */
433 	case -1:
434 		emit_neg_i64(ctx, dst);
435 		break;
436 	case 0:
437 		emit_mov_r(ctx, lo(dst), MIPS_R_ZERO);
438 		emit_mov_r(ctx, hi(dst), MIPS_R_ZERO);
439 		break;
440 	/* Full 64x32 multiply */
441 	default:
442 		/* hi(dst) = hi(dst) * src(imm) */
443 		emit_mov_i(ctx, src, imm);
444 		if (cpu_has_mips32r1 || cpu_has_mips32r6) {
445 			emit(ctx, mul, hi(dst), hi(dst), src);
446 		} else {
447 			emit(ctx, multu, hi(dst), src);
448 			emit(ctx, mflo, hi(dst));
449 		}
450 
451 		/* hi(dst) = hi(dst) - lo(dst) */
452 		if (imm < 0)
453 			emit(ctx, subu, hi(dst), hi(dst), lo(dst));
454 
455 		/* tmp = lo(dst) * src(imm) >> 32 */
456 		/* lo(dst) = lo(dst) * src(imm) */
457 		if (cpu_has_mips32r6) {
458 			emit(ctx, muhu, tmp, lo(dst), src);
459 			emit(ctx, mulu, lo(dst), lo(dst), src);
460 		} else {
461 			emit(ctx, multu, lo(dst), src);
462 			emit(ctx, mflo, lo(dst));
463 			emit(ctx, mfhi, tmp);
464 		}
465 
466 		/* hi(dst) += tmp */
467 		emit(ctx, addu, hi(dst), hi(dst), tmp);
468 		clobber_reg64(ctx, dst);
469 		break;
470 	}
471 }
472 
473 /* ALU mul register (64x64-bit) */
emit_mul_r64(struct jit_context * ctx,const u8 dst[],const u8 src[])474 static void emit_mul_r64(struct jit_context *ctx,
475 			 const u8 dst[], const u8 src[])
476 {
477 	u8 acc = MIPS_R_T8;
478 	u8 tmp = MIPS_R_T9;
479 
480 	/* acc = hi(dst) * lo(src) */
481 	if (cpu_has_mips32r1 || cpu_has_mips32r6) {
482 		emit(ctx, mul, acc, hi(dst), lo(src));
483 	} else {
484 		emit(ctx, multu, hi(dst), lo(src));
485 		emit(ctx, mflo, acc);
486 	}
487 
488 	/* tmp = lo(dst) * hi(src) */
489 	if (cpu_has_mips32r1 || cpu_has_mips32r6) {
490 		emit(ctx, mul, tmp, lo(dst), hi(src));
491 	} else {
492 		emit(ctx, multu, lo(dst), hi(src));
493 		emit(ctx, mflo, tmp);
494 	}
495 
496 	/* acc += tmp */
497 	emit(ctx, addu, acc, acc, tmp);
498 
499 	/* tmp = lo(dst) * lo(src) >> 32 */
500 	/* lo(dst) = lo(dst) * lo(src) */
501 	if (cpu_has_mips32r6) {
502 		emit(ctx, muhu, tmp, lo(dst), lo(src));
503 		emit(ctx, mulu, lo(dst), lo(dst), lo(src));
504 	} else {
505 		emit(ctx, multu, lo(dst), lo(src));
506 		emit(ctx, mflo, lo(dst));
507 		emit(ctx, mfhi, tmp);
508 	}
509 
510 	/* hi(dst) = acc + tmp */
511 	emit(ctx, addu, hi(dst), acc, tmp);
512 	clobber_reg64(ctx, dst);
513 }
514 
515 /* Helper function for 64-bit modulo */
jit_mod64(u64 a,u64 b)516 static u64 jit_mod64(u64 a, u64 b)
517 {
518 	u64 rem;
519 
520 	div64_u64_rem(a, b, &rem);
521 	return rem;
522 }
523 
524 /* ALU div/mod register (64-bit) */
emit_divmod_r64(struct jit_context * ctx,const u8 dst[],const u8 src[],u8 op)525 static void emit_divmod_r64(struct jit_context *ctx,
526 			    const u8 dst[], const u8 src[], u8 op)
527 {
528 	const u8 *r0 = bpf2mips32[BPF_REG_0]; /* Mapped to v0-v1 */
529 	const u8 *r1 = bpf2mips32[BPF_REG_1]; /* Mapped to a0-a1 */
530 	const u8 *r2 = bpf2mips32[BPF_REG_2]; /* Mapped to a2-a3 */
531 	int exclude, k;
532 	u32 addr = 0;
533 
534 	/* Push caller-saved registers on stack */
535 	push_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
536 		  0, JIT_RESERVED_STACK);
537 
538 	/* Put 64-bit arguments 1 and 2 in registers a0-a3 */
539 	for (k = 0; k < 2; k++) {
540 		emit(ctx, move, MIPS_R_T9, src[k]);
541 		emit(ctx, move, r1[k], dst[k]);
542 		emit(ctx, move, r2[k], MIPS_R_T9);
543 	}
544 
545 	/* Emit function call */
546 	switch (BPF_OP(op)) {
547 	/* dst = dst / src */
548 	case BPF_DIV:
549 		addr = (u32)&div64_u64;
550 		break;
551 	/* dst = dst % src */
552 	case BPF_MOD:
553 		addr = (u32)&jit_mod64;
554 		break;
555 	}
556 	emit_mov_i(ctx, MIPS_R_T9, addr);
557 	emit(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
558 	emit(ctx, nop); /* Delay slot */
559 
560 	/* Store the 64-bit result in dst */
561 	emit(ctx, move, dst[0], r0[0]);
562 	emit(ctx, move, dst[1], r0[1]);
563 
564 	/* Restore caller-saved registers, excluding the computed result */
565 	exclude = BIT(lo(dst)) | BIT(hi(dst));
566 	pop_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
567 		 exclude, JIT_RESERVED_STACK);
568 	emit_load_delay(ctx);
569 
570 	clobber_reg64(ctx, dst);
571 	clobber_reg(ctx, MIPS_R_V0);
572 	clobber_reg(ctx, MIPS_R_V1);
573 	clobber_reg(ctx, MIPS_R_RA);
574 }
575 
576 /* Swap bytes in a register word */
emit_swap8_r(struct jit_context * ctx,u8 dst,u8 src,u8 mask)577 static void emit_swap8_r(struct jit_context *ctx, u8 dst, u8 src, u8 mask)
578 {
579 	u8 tmp = MIPS_R_T9;
580 
581 	emit(ctx, and, tmp, src, mask); /* tmp = src & 0x00ff00ff */
582 	emit(ctx, sll, tmp, tmp, 8);    /* tmp = tmp << 8         */
583 	emit(ctx, srl, dst, src, 8);    /* dst = src >> 8         */
584 	emit(ctx, and, dst, dst, mask); /* dst = dst & 0x00ff00ff */
585 	emit(ctx, or,  dst, dst, tmp);  /* dst = dst | tmp        */
586 }
587 
588 /* Swap half words in a register word */
emit_swap16_r(struct jit_context * ctx,u8 dst,u8 src)589 static void emit_swap16_r(struct jit_context *ctx, u8 dst, u8 src)
590 {
591 	u8 tmp = MIPS_R_T9;
592 
593 	emit(ctx, sll, tmp, src, 16);  /* tmp = src << 16 */
594 	emit(ctx, srl, dst, src, 16);  /* dst = src >> 16 */
595 	emit(ctx, or,  dst, dst, tmp); /* dst = dst | tmp */
596 }
597 
598 /* Swap bytes and truncate a register double word, word or half word */
emit_bswap_r64(struct jit_context * ctx,const u8 dst[],u32 width)599 static void emit_bswap_r64(struct jit_context *ctx, const u8 dst[], u32 width)
600 {
601 	u8 tmp = MIPS_R_T8;
602 
603 	switch (width) {
604 	/* Swap bytes in a double word */
605 	case 64:
606 		if (cpu_has_mips32r2 || cpu_has_mips32r6) {
607 			emit(ctx, rotr, tmp, hi(dst), 16);
608 			emit(ctx, rotr, hi(dst), lo(dst), 16);
609 			emit(ctx, wsbh, lo(dst), tmp);
610 			emit(ctx, wsbh, hi(dst), hi(dst));
611 		} else {
612 			emit_swap16_r(ctx, tmp, lo(dst));
613 			emit_swap16_r(ctx, lo(dst), hi(dst));
614 			emit(ctx, move, hi(dst), tmp);
615 
616 			emit(ctx, lui, tmp, 0xff);      /* tmp = 0x00ff0000 */
617 			emit(ctx, ori, tmp, tmp, 0xff); /* tmp = 0x00ff00ff */
618 			emit_swap8_r(ctx, lo(dst), lo(dst), tmp);
619 			emit_swap8_r(ctx, hi(dst), hi(dst), tmp);
620 		}
621 		break;
622 	/* Swap bytes in a word */
623 	/* Swap bytes in a half word */
624 	case 32:
625 	case 16:
626 		emit_bswap_r(ctx, lo(dst), width);
627 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
628 		break;
629 	}
630 	clobber_reg64(ctx, dst);
631 }
632 
633 /* Truncate a register double word, word or half word */
emit_trunc_r64(struct jit_context * ctx,const u8 dst[],u32 width)634 static void emit_trunc_r64(struct jit_context *ctx, const u8 dst[], u32 width)
635 {
636 	switch (width) {
637 	case 64:
638 		break;
639 	/* Zero-extend a word */
640 	case 32:
641 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
642 		clobber_reg(ctx, hi(dst));
643 		break;
644 	/* Zero-extend a half word */
645 	case 16:
646 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
647 		emit(ctx, andi, lo(dst), lo(dst), 0xffff);
648 		clobber_reg64(ctx, dst);
649 		break;
650 	}
651 }
652 
653 /* Load operation: dst = *(size*)(src + off) */
emit_ldx(struct jit_context * ctx,const u8 dst[],u8 src,s16 off,u8 size)654 static void emit_ldx(struct jit_context *ctx,
655 		     const u8 dst[], u8 src, s16 off, u8 size)
656 {
657 	switch (size) {
658 	/* Load a byte */
659 	case BPF_B:
660 		emit(ctx, lbu, lo(dst), off, src);
661 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
662 		break;
663 	/* Load a half word */
664 	case BPF_H:
665 		emit(ctx, lhu, lo(dst), off, src);
666 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
667 		break;
668 	/* Load a word */
669 	case BPF_W:
670 		emit(ctx, lw, lo(dst), off, src);
671 		emit(ctx, move, hi(dst), MIPS_R_ZERO);
672 		break;
673 	/* Load a double word */
674 	case BPF_DW:
675 		if (dst[1] == src) {
676 			emit(ctx, lw, dst[0], off + 4, src);
677 			emit(ctx, lw, dst[1], off, src);
678 		} else {
679 			emit(ctx, lw, dst[1], off, src);
680 			emit(ctx, lw, dst[0], off + 4, src);
681 		}
682 		emit_load_delay(ctx);
683 		break;
684 	}
685 	clobber_reg64(ctx, dst);
686 }
687 
688 /* Store operation: *(size *)(dst + off) = src */
emit_stx(struct jit_context * ctx,const u8 dst,const u8 src[],s16 off,u8 size)689 static void emit_stx(struct jit_context *ctx,
690 		     const u8 dst, const u8 src[], s16 off, u8 size)
691 {
692 	switch (size) {
693 	/* Store a byte */
694 	case BPF_B:
695 		emit(ctx, sb, lo(src), off, dst);
696 		break;
697 	/* Store a half word */
698 	case BPF_H:
699 		emit(ctx, sh, lo(src), off, dst);
700 		break;
701 	/* Store a word */
702 	case BPF_W:
703 		emit(ctx, sw, lo(src), off, dst);
704 		break;
705 	/* Store a double word */
706 	case BPF_DW:
707 		emit(ctx, sw, src[1], off, dst);
708 		emit(ctx, sw, src[0], off + 4, dst);
709 		break;
710 	}
711 }
712 
713 /* Atomic read-modify-write (32-bit, non-ll/sc fallback) */
emit_atomic_r32(struct jit_context * ctx,u8 dst,u8 src,s16 off,u8 code)714 static void emit_atomic_r32(struct jit_context *ctx,
715 			    u8 dst, u8 src, s16 off, u8 code)
716 {
717 	u32 exclude = 0;
718 	u32 addr = 0;
719 
720 	/* Push caller-saved registers on stack */
721 	push_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
722 		  0, JIT_RESERVED_STACK);
723 	/*
724 	 * Argument 1: dst+off if xchg, otherwise src, passed in register a0
725 	 * Argument 2: src if xchg, otherwise dst+off, passed in register a1
726 	 */
727 	emit(ctx, move, MIPS_R_T9, dst);
728 	if (code == BPF_XCHG) {
729 		emit(ctx, move, MIPS_R_A1, src);
730 		emit(ctx, addiu, MIPS_R_A0, MIPS_R_T9, off);
731 	} else {
732 		emit(ctx, move, MIPS_R_A0, src);
733 		emit(ctx, addiu, MIPS_R_A1, MIPS_R_T9, off);
734 	}
735 
736 	/* Emit function call */
737 	switch (code) {
738 	case BPF_ADD:
739 		addr = (u32)&atomic_add;
740 		break;
741 	case BPF_ADD | BPF_FETCH:
742 		addr = (u32)&atomic_fetch_add;
743 		break;
744 	case BPF_SUB:
745 		addr = (u32)&atomic_sub;
746 		break;
747 	case BPF_SUB | BPF_FETCH:
748 		addr = (u32)&atomic_fetch_sub;
749 		break;
750 	case BPF_OR:
751 		addr = (u32)&atomic_or;
752 		break;
753 	case BPF_OR | BPF_FETCH:
754 		addr = (u32)&atomic_fetch_or;
755 		break;
756 	case BPF_AND:
757 		addr = (u32)&atomic_and;
758 		break;
759 	case BPF_AND | BPF_FETCH:
760 		addr = (u32)&atomic_fetch_and;
761 		break;
762 	case BPF_XOR:
763 		addr = (u32)&atomic_xor;
764 		break;
765 	case BPF_XOR | BPF_FETCH:
766 		addr = (u32)&atomic_fetch_xor;
767 		break;
768 	case BPF_XCHG:
769 		addr = (u32)&atomic_xchg;
770 		break;
771 	}
772 	emit_mov_i(ctx, MIPS_R_T9, addr);
773 	emit(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
774 	emit(ctx, nop); /* Delay slot */
775 
776 	/* Update src register with old value, if specified */
777 	if (code & BPF_FETCH) {
778 		emit(ctx, move, src, MIPS_R_V0);
779 		exclude = BIT(src);
780 		clobber_reg(ctx, src);
781 	}
782 
783 	/* Restore caller-saved registers, except any fetched value */
784 	pop_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
785 		 exclude, JIT_RESERVED_STACK);
786 	emit_load_delay(ctx);
787 	clobber_reg(ctx, MIPS_R_RA);
788 }
789 
790 /* Helper function for 64-bit atomic exchange */
jit_xchg64(s64 a,atomic64_t * v)791 static s64 jit_xchg64(s64 a, atomic64_t *v)
792 {
793 	return atomic64_xchg(v, a);
794 }
795 
796 /* Atomic read-modify-write (64-bit) */
emit_atomic_r64(struct jit_context * ctx,u8 dst,const u8 src[],s16 off,u8 code)797 static void emit_atomic_r64(struct jit_context *ctx,
798 			    u8 dst, const u8 src[], s16 off, u8 code)
799 {
800 	const u8 *r0 = bpf2mips32[BPF_REG_0]; /* Mapped to v0-v1 */
801 	const u8 *r1 = bpf2mips32[BPF_REG_1]; /* Mapped to a0-a1 */
802 	u32 exclude = 0;
803 	u32 addr = 0;
804 
805 	/* Push caller-saved registers on stack */
806 	push_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
807 		  0, JIT_RESERVED_STACK);
808 	/*
809 	 * Argument 1: 64-bit src, passed in registers a0-a1
810 	 * Argument 2: 32-bit dst+off, passed in register a2
811 	 */
812 	emit(ctx, move, MIPS_R_T9, dst);
813 	emit(ctx, move, r1[0], src[0]);
814 	emit(ctx, move, r1[1], src[1]);
815 	emit(ctx, addiu, MIPS_R_A2, MIPS_R_T9, off);
816 
817 	/* Emit function call */
818 	switch (code) {
819 	case BPF_ADD:
820 		addr = (u32)&atomic64_add;
821 		break;
822 	case BPF_ADD | BPF_FETCH:
823 		addr = (u32)&atomic64_fetch_add;
824 		break;
825 	case BPF_SUB:
826 		addr = (u32)&atomic64_sub;
827 		break;
828 	case BPF_SUB | BPF_FETCH:
829 		addr = (u32)&atomic64_fetch_sub;
830 		break;
831 	case BPF_OR:
832 		addr = (u32)&atomic64_or;
833 		break;
834 	case BPF_OR | BPF_FETCH:
835 		addr = (u32)&atomic64_fetch_or;
836 		break;
837 	case BPF_AND:
838 		addr = (u32)&atomic64_and;
839 		break;
840 	case BPF_AND | BPF_FETCH:
841 		addr = (u32)&atomic64_fetch_and;
842 		break;
843 	case BPF_XOR:
844 		addr = (u32)&atomic64_xor;
845 		break;
846 	case BPF_XOR | BPF_FETCH:
847 		addr = (u32)&atomic64_fetch_xor;
848 		break;
849 	case BPF_XCHG:
850 		addr = (u32)&jit_xchg64;
851 		break;
852 	}
853 	emit_mov_i(ctx, MIPS_R_T9, addr);
854 	emit(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
855 	emit(ctx, nop); /* Delay slot */
856 
857 	/* Update src register with old value, if specified */
858 	if (code & BPF_FETCH) {
859 		emit(ctx, move, lo(src), lo(r0));
860 		emit(ctx, move, hi(src), hi(r0));
861 		exclude = BIT(src[0]) | BIT(src[1]);
862 		clobber_reg64(ctx, src);
863 	}
864 
865 	/* Restore caller-saved registers, except any fetched value */
866 	pop_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
867 		 exclude, JIT_RESERVED_STACK);
868 	emit_load_delay(ctx);
869 	clobber_reg(ctx, MIPS_R_RA);
870 }
871 
872 /* Atomic compare-and-exchange (32-bit, non-ll/sc fallback) */
emit_cmpxchg_r32(struct jit_context * ctx,u8 dst,u8 src,s16 off)873 static void emit_cmpxchg_r32(struct jit_context *ctx, u8 dst, u8 src, s16 off)
874 {
875 	const u8 *r0 = bpf2mips32[BPF_REG_0];
876 
877 	/* Push caller-saved registers on stack */
878 	push_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
879 		  JIT_RETURN_REGS, JIT_RESERVED_STACK + 2 * sizeof(u32));
880 	/*
881 	 * Argument 1: 32-bit dst+off, passed in register a0
882 	 * Argument 2: 32-bit r0, passed in register a1
883 	 * Argument 3: 32-bit src, passed in register a2
884 	 */
885 	emit(ctx, addiu, MIPS_R_T9, dst, off);
886 	emit(ctx, move, MIPS_R_T8, src);
887 	emit(ctx, move, MIPS_R_A1, lo(r0));
888 	emit(ctx, move, MIPS_R_A0, MIPS_R_T9);
889 	emit(ctx, move, MIPS_R_A2, MIPS_R_T8);
890 
891 	/* Emit function call */
892 	emit_mov_i(ctx, MIPS_R_T9, (u32)&atomic_cmpxchg);
893 	emit(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
894 	emit(ctx, nop); /* Delay slot */
895 
896 #ifdef __BIG_ENDIAN
897 	emit(ctx, move, lo(r0), MIPS_R_V0);
898 #endif
899 	/* Restore caller-saved registers, except the return value */
900 	pop_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
901 		 JIT_RETURN_REGS, JIT_RESERVED_STACK + 2 * sizeof(u32));
902 	emit_load_delay(ctx);
903 	clobber_reg(ctx, MIPS_R_V0);
904 	clobber_reg(ctx, MIPS_R_V1);
905 	clobber_reg(ctx, MIPS_R_RA);
906 }
907 
908 /* Atomic compare-and-exchange (64-bit) */
emit_cmpxchg_r64(struct jit_context * ctx,u8 dst,const u8 src[],s16 off)909 static void emit_cmpxchg_r64(struct jit_context *ctx,
910 			     u8 dst, const u8 src[], s16 off)
911 {
912 	const u8 *r0 = bpf2mips32[BPF_REG_0];
913 	const u8 *r2 = bpf2mips32[BPF_REG_2];
914 
915 	/* Push caller-saved registers on stack */
916 	push_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
917 		  JIT_RETURN_REGS, JIT_RESERVED_STACK + 2 * sizeof(u32));
918 	/*
919 	 * Argument 1: 32-bit dst+off, passed in register a0 (a1 unused)
920 	 * Argument 2: 64-bit r0, passed in registers a2-a3
921 	 * Argument 3: 64-bit src, passed on stack
922 	 */
923 	push_regs(ctx, BIT(src[0]) | BIT(src[1]), 0, JIT_RESERVED_STACK);
924 	emit(ctx, addiu, MIPS_R_T9, dst, off);
925 	emit(ctx, move, r2[0], r0[0]);
926 	emit(ctx, move, r2[1], r0[1]);
927 	emit(ctx, move, MIPS_R_A0, MIPS_R_T9);
928 
929 	/* Emit function call */
930 	emit_mov_i(ctx, MIPS_R_T9, (u32)&atomic64_cmpxchg);
931 	emit(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
932 	emit(ctx, nop); /* Delay slot */
933 
934 	/* Restore caller-saved registers, except the return value */
935 	pop_regs(ctx, ctx->clobbered & JIT_CALLER_REGS,
936 		 JIT_RETURN_REGS, JIT_RESERVED_STACK + 2 * sizeof(u32));
937 	emit_load_delay(ctx);
938 	clobber_reg(ctx, MIPS_R_V0);
939 	clobber_reg(ctx, MIPS_R_V1);
940 	clobber_reg(ctx, MIPS_R_RA);
941 }
942 
943 /*
944  * Conditional movz or an emulated equivalent.
945  * Note that the rs register may be modified.
946  */
emit_movz_r(struct jit_context * ctx,u8 rd,u8 rs,u8 rt)947 static void emit_movz_r(struct jit_context *ctx, u8 rd, u8 rs, u8 rt)
948 {
949 	if (cpu_has_mips_2) {
950 		emit(ctx, movz, rd, rs, rt);           /* rd = rt ? rd : rs  */
951 	} else if (cpu_has_mips32r6) {
952 		if (rs != MIPS_R_ZERO)
953 			emit(ctx, seleqz, rs, rs, rt); /* rs = 0 if rt == 0  */
954 		emit(ctx, selnez, rd, rd, rt);         /* rd = 0 if rt != 0  */
955 		if (rs != MIPS_R_ZERO)
956 			emit(ctx, or, rd, rd, rs);     /* rd = rd | rs       */
957 	} else {
958 		emit(ctx, bnez, rt, 8);                /* PC += 8 if rd != 0 */
959 		emit(ctx, nop);                        /* +0: delay slot     */
960 		emit(ctx, or, rd, rs, MIPS_R_ZERO);    /* +4: rd = rs        */
961 	}
962 	clobber_reg(ctx, rd);
963 	clobber_reg(ctx, rs);
964 }
965 
966 /*
967  * Conditional movn or an emulated equivalent.
968  * Note that the rs register may be modified.
969  */
emit_movn_r(struct jit_context * ctx,u8 rd,u8 rs,u8 rt)970 static void emit_movn_r(struct jit_context *ctx, u8 rd, u8 rs, u8 rt)
971 {
972 	if (cpu_has_mips_2) {
973 		emit(ctx, movn, rd, rs, rt);           /* rd = rt ? rs : rd  */
974 	} else if (cpu_has_mips32r6) {
975 		if (rs != MIPS_R_ZERO)
976 			emit(ctx, selnez, rs, rs, rt); /* rs = 0 if rt == 0  */
977 		emit(ctx, seleqz, rd, rd, rt);         /* rd = 0 if rt != 0  */
978 		if (rs != MIPS_R_ZERO)
979 			emit(ctx, or, rd, rd, rs);     /* rd = rd | rs       */
980 	} else {
981 		emit(ctx, beqz, rt, 8);                /* PC += 8 if rd == 0 */
982 		emit(ctx, nop);                        /* +0: delay slot     */
983 		emit(ctx, or, rd, rs, MIPS_R_ZERO);    /* +4: rd = rs        */
984 	}
985 	clobber_reg(ctx, rd);
986 	clobber_reg(ctx, rs);
987 }
988 
989 /* Emulation of 64-bit sltiu rd, rs, imm, where imm may be S32_MAX + 1 */
emit_sltiu_r64(struct jit_context * ctx,u8 rd,const u8 rs[],s64 imm)990 static void emit_sltiu_r64(struct jit_context *ctx, u8 rd,
991 			   const u8 rs[], s64 imm)
992 {
993 	u8 tmp = MIPS_R_T9;
994 
995 	if (imm < 0) {
996 		emit_mov_i(ctx, rd, imm);                 /* rd = imm        */
997 		emit(ctx, sltu, rd, lo(rs), rd);          /* rd = rsl < rd   */
998 		emit(ctx, sltiu, tmp, hi(rs), -1);        /* tmp = rsh < ~0U */
999 		emit(ctx, or, rd, rd, tmp);               /* rd = rd | tmp   */
1000 	} else { /* imm >= 0 */
1001 		if (imm > 0x7fff) {
1002 			emit_mov_i(ctx, rd, (s32)imm);     /* rd = imm       */
1003 			emit(ctx, sltu, rd, lo(rs), rd);   /* rd = rsl < rd  */
1004 		} else {
1005 			emit(ctx, sltiu, rd, lo(rs), imm); /* rd = rsl < imm */
1006 		}
1007 		emit_movn_r(ctx, rd, MIPS_R_ZERO, hi(rs)); /* rd = 0 if rsh  */
1008 	}
1009 }
1010 
1011 /* Emulation of 64-bit sltu rd, rs, rt */
emit_sltu_r64(struct jit_context * ctx,u8 rd,const u8 rs[],const u8 rt[])1012 static void emit_sltu_r64(struct jit_context *ctx, u8 rd,
1013 			  const u8 rs[], const u8 rt[])
1014 {
1015 	u8 tmp = MIPS_R_T9;
1016 
1017 	emit(ctx, sltu, rd, lo(rs), lo(rt));           /* rd = rsl < rtl     */
1018 	emit(ctx, subu, tmp, hi(rs), hi(rt));          /* tmp = rsh - rth    */
1019 	emit_movn_r(ctx, rd, MIPS_R_ZERO, tmp);        /* rd = 0 if tmp != 0 */
1020 	emit(ctx, sltu, tmp, hi(rs), hi(rt));          /* tmp = rsh < rth    */
1021 	emit(ctx, or, rd, rd, tmp);                    /* rd = rd | tmp      */
1022 }
1023 
1024 /* Emulation of 64-bit slti rd, rs, imm, where imm may be S32_MAX + 1 */
emit_slti_r64(struct jit_context * ctx,u8 rd,const u8 rs[],s64 imm)1025 static void emit_slti_r64(struct jit_context *ctx, u8 rd,
1026 			  const u8 rs[], s64 imm)
1027 {
1028 	u8 t1 = MIPS_R_T8;
1029 	u8 t2 = MIPS_R_T9;
1030 	u8 cmp;
1031 
1032 	/*
1033 	 * if ((rs < 0) ^ (imm < 0)) t1 = imm >u rsl
1034 	 * else                      t1 = rsl <u imm
1035 	 */
1036 	emit_mov_i(ctx, rd, (s32)imm);
1037 	emit(ctx, sltu, t1, lo(rs), rd);               /* t1 = rsl <u imm   */
1038 	emit(ctx, sltu, t2, rd, lo(rs));               /* t2 = imm <u rsl   */
1039 	emit(ctx, srl, rd, hi(rs), 31);                /* rd = rsh >> 31    */
1040 	if (imm < 0)
1041 		emit_movz_r(ctx, t1, t2, rd);          /* t1 = rd ? t1 : t2 */
1042 	else
1043 		emit_movn_r(ctx, t1, t2, rd);          /* t1 = rd ? t2 : t1 */
1044 	/*
1045 	 * if ((imm < 0 && rsh != 0xffffffff) ||
1046 	 *     (imm >= 0 && rsh != 0))
1047 	 *      t1 = 0
1048 	 */
1049 	if (imm < 0) {
1050 		emit(ctx, addiu, rd, hi(rs), 1);       /* rd = rsh + 1 */
1051 		cmp = rd;
1052 	} else { /* imm >= 0 */
1053 		cmp = hi(rs);
1054 	}
1055 	emit_movn_r(ctx, t1, MIPS_R_ZERO, cmp);        /* t1 = 0 if cmp != 0 */
1056 
1057 	/*
1058 	 * if (imm < 0) rd = rsh < -1
1059 	 * else         rd = rsh != 0
1060 	 * rd = rd | t1
1061 	 */
1062 	emit(ctx, slti, rd, hi(rs), imm < 0 ? -1 : 0); /* rd = rsh < hi(imm) */
1063 	emit(ctx, or, rd, rd, t1);                     /* rd = rd | t1       */
1064 }
1065 
1066 /* Emulation of 64-bit(slt rd, rs, rt) */
emit_slt_r64(struct jit_context * ctx,u8 rd,const u8 rs[],const u8 rt[])1067 static void emit_slt_r64(struct jit_context *ctx, u8 rd,
1068 			 const u8 rs[], const u8 rt[])
1069 {
1070 	u8 t1 = MIPS_R_T7;
1071 	u8 t2 = MIPS_R_T8;
1072 	u8 t3 = MIPS_R_T9;
1073 
1074 	/*
1075 	 * if ((rs < 0) ^ (rt < 0)) t1 = rtl <u rsl
1076 	 * else                     t1 = rsl <u rtl
1077 	 * if (rsh == rth)          t1 = 0
1078 	 */
1079 	emit(ctx, sltu, t1, lo(rs), lo(rt));           /* t1 = rsl <u rtl   */
1080 	emit(ctx, sltu, t2, lo(rt), lo(rs));           /* t2 = rtl <u rsl   */
1081 	emit(ctx, xor, t3, hi(rs), hi(rt));            /* t3 = rlh ^ rth    */
1082 	emit(ctx, srl, rd, t3, 31);                    /* rd = t3 >> 31     */
1083 	emit_movn_r(ctx, t1, t2, rd);                  /* t1 = rd ? t2 : t1 */
1084 	emit_movn_r(ctx, t1, MIPS_R_ZERO, t3);         /* t1 = 0 if t3 != 0 */
1085 
1086 	/* rd = (rsh < rth) | t1 */
1087 	emit(ctx, slt, rd, hi(rs), hi(rt));            /* rd = rsh <s rth   */
1088 	emit(ctx, or, rd, rd, t1);                     /* rd = rd | t1      */
1089 }
1090 
1091 /* Jump immediate (64-bit) */
emit_jmp_i64(struct jit_context * ctx,const u8 dst[],s32 imm,s32 off,u8 op)1092 static void emit_jmp_i64(struct jit_context *ctx,
1093 			 const u8 dst[], s32 imm, s32 off, u8 op)
1094 {
1095 	u8 tmp = MIPS_R_T6;
1096 
1097 	switch (op) {
1098 	/* No-op, used internally for branch optimization */
1099 	case JIT_JNOP:
1100 		break;
1101 	/* PC += off if dst == imm */
1102 	/* PC += off if dst != imm */
1103 	case BPF_JEQ:
1104 	case BPF_JNE:
1105 		if (imm >= -0x7fff && imm <= 0x8000) {
1106 			emit(ctx, addiu, tmp, lo(dst), -imm);
1107 		} else if ((u32)imm <= 0xffff) {
1108 			emit(ctx, xori, tmp, lo(dst), imm);
1109 		} else {       /* Register fallback */
1110 			emit_mov_i(ctx, tmp, imm);
1111 			emit(ctx, xor, tmp, lo(dst), tmp);
1112 		}
1113 		if (imm < 0) { /* Compare sign extension */
1114 			emit(ctx, addu, MIPS_R_T9, hi(dst), 1);
1115 			emit(ctx, or, tmp, tmp, MIPS_R_T9);
1116 		} else {       /* Compare zero extension */
1117 			emit(ctx, or, tmp, tmp, hi(dst));
1118 		}
1119 		if (op == BPF_JEQ)
1120 			emit(ctx, beqz, tmp, off);
1121 		else   /* BPF_JNE */
1122 			emit(ctx, bnez, tmp, off);
1123 		break;
1124 	/* PC += off if dst & imm */
1125 	/* PC += off if (dst & imm) == 0 (not in BPF, used for long jumps) */
1126 	case BPF_JSET:
1127 	case JIT_JNSET:
1128 		if ((u32)imm <= 0xffff) {
1129 			emit(ctx, andi, tmp, lo(dst), imm);
1130 		} else {     /* Register fallback */
1131 			emit_mov_i(ctx, tmp, imm);
1132 			emit(ctx, and, tmp, lo(dst), tmp);
1133 		}
1134 		if (imm < 0) /* Sign-extension pulls in high word */
1135 			emit(ctx, or, tmp, tmp, hi(dst));
1136 		if (op == BPF_JSET)
1137 			emit(ctx, bnez, tmp, off);
1138 		else   /* JIT_JNSET */
1139 			emit(ctx, beqz, tmp, off);
1140 		break;
1141 	/* PC += off if dst > imm */
1142 	case BPF_JGT:
1143 		emit_sltiu_r64(ctx, tmp, dst, (s64)imm + 1);
1144 		emit(ctx, beqz, tmp, off);
1145 		break;
1146 	/* PC += off if dst >= imm */
1147 	case BPF_JGE:
1148 		emit_sltiu_r64(ctx, tmp, dst, imm);
1149 		emit(ctx, beqz, tmp, off);
1150 		break;
1151 	/* PC += off if dst < imm */
1152 	case BPF_JLT:
1153 		emit_sltiu_r64(ctx, tmp, dst, imm);
1154 		emit(ctx, bnez, tmp, off);
1155 		break;
1156 	/* PC += off if dst <= imm */
1157 	case BPF_JLE:
1158 		emit_sltiu_r64(ctx, tmp, dst, (s64)imm + 1);
1159 		emit(ctx, bnez, tmp, off);
1160 		break;
1161 	/* PC += off if dst > imm (signed) */
1162 	case BPF_JSGT:
1163 		emit_slti_r64(ctx, tmp, dst, (s64)imm + 1);
1164 		emit(ctx, beqz, tmp, off);
1165 		break;
1166 	/* PC += off if dst >= imm (signed) */
1167 	case BPF_JSGE:
1168 		emit_slti_r64(ctx, tmp, dst, imm);
1169 		emit(ctx, beqz, tmp, off);
1170 		break;
1171 	/* PC += off if dst < imm (signed) */
1172 	case BPF_JSLT:
1173 		emit_slti_r64(ctx, tmp, dst, imm);
1174 		emit(ctx, bnez, tmp, off);
1175 		break;
1176 	/* PC += off if dst <= imm (signed) */
1177 	case BPF_JSLE:
1178 		emit_slti_r64(ctx, tmp, dst, (s64)imm + 1);
1179 		emit(ctx, bnez, tmp, off);
1180 		break;
1181 	}
1182 }
1183 
1184 /* Jump register (64-bit) */
emit_jmp_r64(struct jit_context * ctx,const u8 dst[],const u8 src[],s32 off,u8 op)1185 static void emit_jmp_r64(struct jit_context *ctx,
1186 			 const u8 dst[], const u8 src[], s32 off, u8 op)
1187 {
1188 	u8 t1 = MIPS_R_T6;
1189 	u8 t2 = MIPS_R_T7;
1190 
1191 	switch (op) {
1192 	/* No-op, used internally for branch optimization */
1193 	case JIT_JNOP:
1194 		break;
1195 	/* PC += off if dst == src */
1196 	/* PC += off if dst != src */
1197 	case BPF_JEQ:
1198 	case BPF_JNE:
1199 		emit(ctx, subu, t1, lo(dst), lo(src));
1200 		emit(ctx, subu, t2, hi(dst), hi(src));
1201 		emit(ctx, or, t1, t1, t2);
1202 		if (op == BPF_JEQ)
1203 			emit(ctx, beqz, t1, off);
1204 		else   /* BPF_JNE */
1205 			emit(ctx, bnez, t1, off);
1206 		break;
1207 	/* PC += off if dst & src */
1208 	/* PC += off if (dst & imm) == 0 (not in BPF, used for long jumps) */
1209 	case BPF_JSET:
1210 	case JIT_JNSET:
1211 		emit(ctx, and, t1, lo(dst), lo(src));
1212 		emit(ctx, and, t2, hi(dst), hi(src));
1213 		emit(ctx, or, t1, t1, t2);
1214 		if (op == BPF_JSET)
1215 			emit(ctx, bnez, t1, off);
1216 		else   /* JIT_JNSET */
1217 			emit(ctx, beqz, t1, off);
1218 		break;
1219 	/* PC += off if dst > src */
1220 	case BPF_JGT:
1221 		emit_sltu_r64(ctx, t1, src, dst);
1222 		emit(ctx, bnez, t1, off);
1223 		break;
1224 	/* PC += off if dst >= src */
1225 	case BPF_JGE:
1226 		emit_sltu_r64(ctx, t1, dst, src);
1227 		emit(ctx, beqz, t1, off);
1228 		break;
1229 	/* PC += off if dst < src */
1230 	case BPF_JLT:
1231 		emit_sltu_r64(ctx, t1, dst, src);
1232 		emit(ctx, bnez, t1, off);
1233 		break;
1234 	/* PC += off if dst <= src */
1235 	case BPF_JLE:
1236 		emit_sltu_r64(ctx, t1, src, dst);
1237 		emit(ctx, beqz, t1, off);
1238 		break;
1239 	/* PC += off if dst > src (signed) */
1240 	case BPF_JSGT:
1241 		emit_slt_r64(ctx, t1, src, dst);
1242 		emit(ctx, bnez, t1, off);
1243 		break;
1244 	/* PC += off if dst >= src (signed) */
1245 	case BPF_JSGE:
1246 		emit_slt_r64(ctx, t1, dst, src);
1247 		emit(ctx, beqz, t1, off);
1248 		break;
1249 	/* PC += off if dst < src (signed) */
1250 	case BPF_JSLT:
1251 		emit_slt_r64(ctx, t1, dst, src);
1252 		emit(ctx, bnez, t1, off);
1253 		break;
1254 	/* PC += off if dst <= src (signed) */
1255 	case BPF_JSLE:
1256 		emit_slt_r64(ctx, t1, src, dst);
1257 		emit(ctx, beqz, t1, off);
1258 		break;
1259 	}
1260 }
1261 
1262 /* Function call */
emit_call(struct jit_context * ctx,const struct bpf_insn * insn)1263 static int emit_call(struct jit_context *ctx, const struct bpf_insn *insn)
1264 {
1265 	bool fixed;
1266 	u64 addr;
1267 
1268 	/* Decode the call address */
1269 	if (bpf_jit_get_func_addr(ctx->program, insn, false,
1270 				  &addr, &fixed) < 0)
1271 		return -1;
1272 	if (!fixed)
1273 		return -1;
1274 
1275 	/* Push stack arguments */
1276 	push_regs(ctx, JIT_STACK_REGS, 0, JIT_RESERVED_STACK);
1277 
1278 	/* Emit function call */
1279 	emit_mov_i(ctx, MIPS_R_T9, addr);
1280 	emit(ctx, jalr, MIPS_R_RA, MIPS_R_T9);
1281 	emit(ctx, nop); /* Delay slot */
1282 
1283 	clobber_reg(ctx, MIPS_R_RA);
1284 	clobber_reg(ctx, MIPS_R_V0);
1285 	clobber_reg(ctx, MIPS_R_V1);
1286 	return 0;
1287 }
1288 
1289 /* Function tail call */
emit_tail_call(struct jit_context * ctx)1290 static int emit_tail_call(struct jit_context *ctx)
1291 {
1292 	u8 ary = lo(bpf2mips32[BPF_REG_2]);
1293 	u8 ind = lo(bpf2mips32[BPF_REG_3]);
1294 	u8 t1 = MIPS_R_T8;
1295 	u8 t2 = MIPS_R_T9;
1296 	int off;
1297 
1298 	/*
1299 	 * Tail call:
1300 	 * eBPF R1   - function argument (context ptr), passed in a0-a1
1301 	 * eBPF R2   - ptr to object with array of function entry points
1302 	 * eBPF R3   - array index of function to be called
1303 	 * stack[sz] - remaining tail call count, initialized in prologue
1304 	 */
1305 
1306 	/* if (ind >= ary->map.max_entries) goto out */
1307 	off = offsetof(struct bpf_array, map.max_entries);
1308 	if (off > 0x7fff)
1309 		return -1;
1310 	emit(ctx, lw, t1, off, ary);             /* t1 = ary->map.max_entries*/
1311 	emit_load_delay(ctx);                    /* Load delay slot          */
1312 	emit(ctx, sltu, t1, ind, t1);            /* t1 = ind < t1            */
1313 	emit(ctx, beqz, t1, get_offset(ctx, 1)); /* PC += off(1) if t1 == 0  */
1314 						 /* (next insn delay slot)   */
1315 	/* if (TCC-- <= 0) goto out */
1316 	emit(ctx, lw, t2, ctx->stack_size, MIPS_R_SP);  /* t2 = *(SP + size) */
1317 	emit_load_delay(ctx);                     /* Load delay slot         */
1318 	emit(ctx, blez, t2, get_offset(ctx, 1));  /* PC += off(1) if t2 <= 0 */
1319 	emit(ctx, addiu, t2, t2, -1);             /* t2-- (delay slot)       */
1320 	emit(ctx, sw, t2, ctx->stack_size, MIPS_R_SP);  /* *(SP + size) = t2 */
1321 
1322 	/* prog = ary->ptrs[ind] */
1323 	off = offsetof(struct bpf_array, ptrs);
1324 	if (off > 0x7fff)
1325 		return -1;
1326 	emit(ctx, sll, t1, ind, 2);               /* t1 = ind << 2           */
1327 	emit(ctx, addu, t1, t1, ary);             /* t1 += ary               */
1328 	emit(ctx, lw, t2, off, t1);               /* t2 = *(t1 + off)        */
1329 	emit_load_delay(ctx);                     /* Load delay slot         */
1330 
1331 	/* if (prog == 0) goto out */
1332 	emit(ctx, beqz, t2, get_offset(ctx, 1));  /* PC += off(1) if t2 == 0 */
1333 	emit(ctx, nop);                           /* Delay slot              */
1334 
1335 	/* func = prog->bpf_func + 8 (prologue skip offset) */
1336 	off = offsetof(struct bpf_prog, bpf_func);
1337 	if (off > 0x7fff)
1338 		return -1;
1339 	emit(ctx, lw, t1, off, t2);                /* t1 = *(t2 + off)       */
1340 	emit_load_delay(ctx);                      /* Load delay slot        */
1341 	emit(ctx, addiu, t1, t1, JIT_TCALL_SKIP);  /* t1 += skip (8 or 12)   */
1342 
1343 	/* goto func */
1344 	build_epilogue(ctx, t1);
1345 	return 0;
1346 }
1347 
1348 /*
1349  * Stack frame layout for a JITed program (stack grows down).
1350  *
1351  * Higher address  : Caller's stack frame       :
1352  *                 :----------------------------:
1353  *                 : 64-bit eBPF args r3-r5     :
1354  *                 :----------------------------:
1355  *                 : Reserved / tail call count :
1356  *                 +============================+  <--- MIPS sp before call
1357  *                 | Callee-saved registers,    |
1358  *                 | including RA and FP        |
1359  *                 +----------------------------+  <--- eBPF FP (MIPS zero,fp)
1360  *                 | Local eBPF variables       |
1361  *                 | allocated by program       |
1362  *                 +----------------------------+
1363  *                 | Reserved for caller-saved  |
1364  *                 | registers                  |
1365  *                 +----------------------------+
1366  *                 | Reserved for 64-bit eBPF   |
1367  *                 | args r3-r5 & args passed   |
1368  *                 | on stack in kernel calls   |
1369  * Lower address   +============================+  <--- MIPS sp
1370  */
1371 
1372 /* Build program prologue to set up the stack and registers */
build_prologue(struct jit_context * ctx)1373 void build_prologue(struct jit_context *ctx)
1374 {
1375 	const u8 *r1 = bpf2mips32[BPF_REG_1];
1376 	const u8 *fp = bpf2mips32[BPF_REG_FP];
1377 	int stack, saved, locals, reserved;
1378 
1379 	/*
1380 	 * In the unlikely event that the TCC limit is raised to more
1381 	 * than 16 bits, it is clamped to the maximum value allowed for
1382 	 * the generated code (0xffff). It is better fail to compile
1383 	 * instead of degrading gracefully.
1384 	 */
1385 	BUILD_BUG_ON(MAX_TAIL_CALL_CNT > 0xffff);
1386 
1387 	/*
1388 	 * The first two instructions initialize TCC in the reserved (for us)
1389 	 * 16-byte area in the parent's stack frame. On a tail call, the
1390 	 * calling function jumps into the prologue after these instructions.
1391 	 */
1392 	emit(ctx, ori, MIPS_R_T9, MIPS_R_ZERO, MAX_TAIL_CALL_CNT);
1393 	emit(ctx, sw, MIPS_R_T9, 0, MIPS_R_SP);
1394 
1395 	/*
1396 	 * Register eBPF R1 contains the 32-bit context pointer argument.
1397 	 * A 32-bit argument is always passed in MIPS register a0, regardless
1398 	 * of CPU endianness. Initialize R1 accordingly and zero-extend.
1399 	 */
1400 #ifdef __BIG_ENDIAN
1401 	emit(ctx, move, lo(r1), MIPS_R_A0);
1402 #endif
1403 
1404 	/* === Entry-point for tail calls === */
1405 
1406 	/* Zero-extend the 32-bit argument */
1407 	emit(ctx, move, hi(r1), MIPS_R_ZERO);
1408 
1409 	/* If the eBPF frame pointer was accessed it must be saved */
1410 	if (ctx->accessed & BIT(BPF_REG_FP))
1411 		clobber_reg64(ctx, fp);
1412 
1413 	/* Compute the stack space needed for callee-saved registers */
1414 	saved = hweight32(ctx->clobbered & JIT_CALLEE_REGS) * sizeof(u32);
1415 	saved = ALIGN(saved, MIPS_STACK_ALIGNMENT);
1416 
1417 	/* Stack space used by eBPF program local data */
1418 	locals = ALIGN(ctx->program->aux->stack_depth, MIPS_STACK_ALIGNMENT);
1419 
1420 	/*
1421 	 * If we are emitting function calls, reserve extra stack space for
1422 	 * caller-saved registers and function arguments passed on the stack.
1423 	 * The required space is computed automatically during resource
1424 	 * usage discovery (pass 1).
1425 	 */
1426 	reserved = ctx->stack_used;
1427 
1428 	/* Allocate the stack frame */
1429 	stack = ALIGN(saved + locals + reserved, MIPS_STACK_ALIGNMENT);
1430 	emit(ctx, addiu, MIPS_R_SP, MIPS_R_SP, -stack);
1431 
1432 	/* Store callee-saved registers on stack */
1433 	push_regs(ctx, ctx->clobbered & JIT_CALLEE_REGS, 0, stack - saved);
1434 
1435 	/* Initialize the eBPF frame pointer if accessed */
1436 	if (ctx->accessed & BIT(BPF_REG_FP))
1437 		emit(ctx, addiu, lo(fp), MIPS_R_SP, stack - saved);
1438 
1439 	ctx->saved_size = saved;
1440 	ctx->stack_size = stack;
1441 }
1442 
1443 /* Build the program epilogue to restore the stack and registers */
build_epilogue(struct jit_context * ctx,int dest_reg)1444 void build_epilogue(struct jit_context *ctx, int dest_reg)
1445 {
1446 	/* Restore callee-saved registers from stack */
1447 	pop_regs(ctx, ctx->clobbered & JIT_CALLEE_REGS, 0,
1448 		 ctx->stack_size - ctx->saved_size);
1449 	/*
1450 	 * A 32-bit return value is always passed in MIPS register v0,
1451 	 * but on big-endian targets the low part of R0 is mapped to v1.
1452 	 */
1453 #ifdef __BIG_ENDIAN
1454 	emit(ctx, move, MIPS_R_V0, MIPS_R_V1);
1455 #endif
1456 
1457 	/* Jump to the return address and adjust the stack pointer */
1458 	emit(ctx, jr, dest_reg);
1459 	emit(ctx, addiu, MIPS_R_SP, MIPS_R_SP, ctx->stack_size);
1460 }
1461 
1462 /* Build one eBPF instruction */
build_insn(const struct bpf_insn * insn,struct jit_context * ctx)1463 int build_insn(const struct bpf_insn *insn, struct jit_context *ctx)
1464 {
1465 	const u8 *dst = bpf2mips32[insn->dst_reg];
1466 	const u8 *src = bpf2mips32[insn->src_reg];
1467 	const u8 *res = bpf2mips32[BPF_REG_0];
1468 	const u8 *tmp = bpf2mips32[JIT_REG_TMP];
1469 	u8 code = insn->code;
1470 	s16 off = insn->off;
1471 	s32 imm = insn->imm;
1472 	s32 val, rel;
1473 	u8 alu, jmp;
1474 
1475 	switch (code) {
1476 	/* ALU operations */
1477 	/* dst = imm */
1478 	case BPF_ALU | BPF_MOV | BPF_K:
1479 		emit_mov_i(ctx, lo(dst), imm);
1480 		emit_zext_ver(ctx, dst);
1481 		break;
1482 	/* dst = src */
1483 	case BPF_ALU | BPF_MOV | BPF_X:
1484 		if (imm == 1) {
1485 			/* Special mov32 for zext */
1486 			emit_mov_i(ctx, hi(dst), 0);
1487 		} else {
1488 			emit_mov_r(ctx, lo(dst), lo(src));
1489 			emit_zext_ver(ctx, dst);
1490 		}
1491 		break;
1492 	/* dst = -dst */
1493 	case BPF_ALU | BPF_NEG:
1494 		emit_alu_i(ctx, lo(dst), 0, BPF_NEG);
1495 		emit_zext_ver(ctx, dst);
1496 		break;
1497 	/* dst = dst & imm */
1498 	/* dst = dst | imm */
1499 	/* dst = dst ^ imm */
1500 	/* dst = dst << imm */
1501 	/* dst = dst >> imm */
1502 	/* dst = dst >> imm (arithmetic) */
1503 	/* dst = dst + imm */
1504 	/* dst = dst - imm */
1505 	/* dst = dst * imm */
1506 	/* dst = dst / imm */
1507 	/* dst = dst % imm */
1508 	case BPF_ALU | BPF_OR | BPF_K:
1509 	case BPF_ALU | BPF_AND | BPF_K:
1510 	case BPF_ALU | BPF_XOR | BPF_K:
1511 	case BPF_ALU | BPF_LSH | BPF_K:
1512 	case BPF_ALU | BPF_RSH | BPF_K:
1513 	case BPF_ALU | BPF_ARSH | BPF_K:
1514 	case BPF_ALU | BPF_ADD | BPF_K:
1515 	case BPF_ALU | BPF_SUB | BPF_K:
1516 	case BPF_ALU | BPF_MUL | BPF_K:
1517 	case BPF_ALU | BPF_DIV | BPF_K:
1518 	case BPF_ALU | BPF_MOD | BPF_K:
1519 		if (!valid_alu_i(BPF_OP(code), imm)) {
1520 			emit_mov_i(ctx, MIPS_R_T6, imm);
1521 			emit_alu_r(ctx, lo(dst), MIPS_R_T6, BPF_OP(code));
1522 		} else if (rewrite_alu_i(BPF_OP(code), imm, &alu, &val)) {
1523 			emit_alu_i(ctx, lo(dst), val, alu);
1524 		}
1525 		emit_zext_ver(ctx, dst);
1526 		break;
1527 	/* dst = dst & src */
1528 	/* dst = dst | src */
1529 	/* dst = dst ^ src */
1530 	/* dst = dst << src */
1531 	/* dst = dst >> src */
1532 	/* dst = dst >> src (arithmetic) */
1533 	/* dst = dst + src */
1534 	/* dst = dst - src */
1535 	/* dst = dst * src */
1536 	/* dst = dst / src */
1537 	/* dst = dst % src */
1538 	case BPF_ALU | BPF_AND | BPF_X:
1539 	case BPF_ALU | BPF_OR | BPF_X:
1540 	case BPF_ALU | BPF_XOR | BPF_X:
1541 	case BPF_ALU | BPF_LSH | BPF_X:
1542 	case BPF_ALU | BPF_RSH | BPF_X:
1543 	case BPF_ALU | BPF_ARSH | BPF_X:
1544 	case BPF_ALU | BPF_ADD | BPF_X:
1545 	case BPF_ALU | BPF_SUB | BPF_X:
1546 	case BPF_ALU | BPF_MUL | BPF_X:
1547 	case BPF_ALU | BPF_DIV | BPF_X:
1548 	case BPF_ALU | BPF_MOD | BPF_X:
1549 		emit_alu_r(ctx, lo(dst), lo(src), BPF_OP(code));
1550 		emit_zext_ver(ctx, dst);
1551 		break;
1552 	/* dst = imm (64-bit) */
1553 	case BPF_ALU64 | BPF_MOV | BPF_K:
1554 		emit_mov_se_i64(ctx, dst, imm);
1555 		break;
1556 	/* dst = src (64-bit) */
1557 	case BPF_ALU64 | BPF_MOV | BPF_X:
1558 		emit_mov_r(ctx, lo(dst), lo(src));
1559 		emit_mov_r(ctx, hi(dst), hi(src));
1560 		break;
1561 	/* dst = -dst (64-bit) */
1562 	case BPF_ALU64 | BPF_NEG:
1563 		emit_neg_i64(ctx, dst);
1564 		break;
1565 	/* dst = dst & imm (64-bit) */
1566 	case BPF_ALU64 | BPF_AND | BPF_K:
1567 		emit_alu_i64(ctx, dst, imm, BPF_OP(code));
1568 		break;
1569 	/* dst = dst | imm (64-bit) */
1570 	/* dst = dst ^ imm (64-bit) */
1571 	/* dst = dst + imm (64-bit) */
1572 	/* dst = dst - imm (64-bit) */
1573 	case BPF_ALU64 | BPF_OR | BPF_K:
1574 	case BPF_ALU64 | BPF_XOR | BPF_K:
1575 	case BPF_ALU64 | BPF_ADD | BPF_K:
1576 	case BPF_ALU64 | BPF_SUB | BPF_K:
1577 		if (imm)
1578 			emit_alu_i64(ctx, dst, imm, BPF_OP(code));
1579 		break;
1580 	/* dst = dst << imm (64-bit) */
1581 	/* dst = dst >> imm (64-bit) */
1582 	/* dst = dst >> imm (64-bit, arithmetic) */
1583 	case BPF_ALU64 | BPF_LSH | BPF_K:
1584 	case BPF_ALU64 | BPF_RSH | BPF_K:
1585 	case BPF_ALU64 | BPF_ARSH | BPF_K:
1586 		if (imm)
1587 			emit_shift_i64(ctx, dst, imm, BPF_OP(code));
1588 		break;
1589 	/* dst = dst * imm (64-bit) */
1590 	case BPF_ALU64 | BPF_MUL | BPF_K:
1591 		emit_mul_i64(ctx, dst, imm);
1592 		break;
1593 	/* dst = dst / imm (64-bit) */
1594 	/* dst = dst % imm (64-bit) */
1595 	case BPF_ALU64 | BPF_DIV | BPF_K:
1596 	case BPF_ALU64 | BPF_MOD | BPF_K:
1597 		/*
1598 		 * Sign-extend the immediate value into a temporary register,
1599 		 * and then do the operation on this register.
1600 		 */
1601 		emit_mov_se_i64(ctx, tmp, imm);
1602 		emit_divmod_r64(ctx, dst, tmp, BPF_OP(code));
1603 		break;
1604 	/* dst = dst & src (64-bit) */
1605 	/* dst = dst | src (64-bit) */
1606 	/* dst = dst ^ src (64-bit) */
1607 	/* dst = dst + src (64-bit) */
1608 	/* dst = dst - src (64-bit) */
1609 	case BPF_ALU64 | BPF_AND | BPF_X:
1610 	case BPF_ALU64 | BPF_OR | BPF_X:
1611 	case BPF_ALU64 | BPF_XOR | BPF_X:
1612 	case BPF_ALU64 | BPF_ADD | BPF_X:
1613 	case BPF_ALU64 | BPF_SUB | BPF_X:
1614 		emit_alu_r64(ctx, dst, src, BPF_OP(code));
1615 		break;
1616 	/* dst = dst << src (64-bit) */
1617 	/* dst = dst >> src (64-bit) */
1618 	/* dst = dst >> src (64-bit, arithmetic) */
1619 	case BPF_ALU64 | BPF_LSH | BPF_X:
1620 	case BPF_ALU64 | BPF_RSH | BPF_X:
1621 	case BPF_ALU64 | BPF_ARSH | BPF_X:
1622 		emit_shift_r64(ctx, dst, lo(src), BPF_OP(code));
1623 		break;
1624 	/* dst = dst * src (64-bit) */
1625 	case BPF_ALU64 | BPF_MUL | BPF_X:
1626 		emit_mul_r64(ctx, dst, src);
1627 		break;
1628 	/* dst = dst / src (64-bit) */
1629 	/* dst = dst % src (64-bit) */
1630 	case BPF_ALU64 | BPF_DIV | BPF_X:
1631 	case BPF_ALU64 | BPF_MOD | BPF_X:
1632 		emit_divmod_r64(ctx, dst, src, BPF_OP(code));
1633 		break;
1634 	/* dst = htole(dst) */
1635 	/* dst = htobe(dst) */
1636 	case BPF_ALU | BPF_END | BPF_FROM_LE:
1637 	case BPF_ALU | BPF_END | BPF_FROM_BE:
1638 		if (BPF_SRC(code) ==
1639 #ifdef __BIG_ENDIAN
1640 		    BPF_FROM_LE
1641 #else
1642 		    BPF_FROM_BE
1643 #endif
1644 		    )
1645 			emit_bswap_r64(ctx, dst, imm);
1646 		else
1647 			emit_trunc_r64(ctx, dst, imm);
1648 		break;
1649 	/* dst = imm64 */
1650 	case BPF_LD | BPF_IMM | BPF_DW:
1651 		emit_mov_i(ctx, lo(dst), imm);
1652 		emit_mov_i(ctx, hi(dst), insn[1].imm);
1653 		return 1;
1654 	/* LDX: dst = *(size *)(src + off) */
1655 	case BPF_LDX | BPF_MEM | BPF_W:
1656 	case BPF_LDX | BPF_MEM | BPF_H:
1657 	case BPF_LDX | BPF_MEM | BPF_B:
1658 	case BPF_LDX | BPF_MEM | BPF_DW:
1659 		emit_ldx(ctx, dst, lo(src), off, BPF_SIZE(code));
1660 		break;
1661 	/* ST: *(size *)(dst + off) = imm */
1662 	case BPF_ST | BPF_MEM | BPF_W:
1663 	case BPF_ST | BPF_MEM | BPF_H:
1664 	case BPF_ST | BPF_MEM | BPF_B:
1665 	case BPF_ST | BPF_MEM | BPF_DW:
1666 		switch (BPF_SIZE(code)) {
1667 		case BPF_DW:
1668 			/* Sign-extend immediate value into temporary reg */
1669 			emit_mov_se_i64(ctx, tmp, imm);
1670 			break;
1671 		case BPF_W:
1672 		case BPF_H:
1673 		case BPF_B:
1674 			emit_mov_i(ctx, lo(tmp), imm);
1675 			break;
1676 		}
1677 		emit_stx(ctx, lo(dst), tmp, off, BPF_SIZE(code));
1678 		break;
1679 	/* STX: *(size *)(dst + off) = src */
1680 	case BPF_STX | BPF_MEM | BPF_W:
1681 	case BPF_STX | BPF_MEM | BPF_H:
1682 	case BPF_STX | BPF_MEM | BPF_B:
1683 	case BPF_STX | BPF_MEM | BPF_DW:
1684 		emit_stx(ctx, lo(dst), src, off, BPF_SIZE(code));
1685 		break;
1686 	/* Speculation barrier */
1687 	case BPF_ST | BPF_NOSPEC:
1688 		break;
1689 	/* Atomics */
1690 	case BPF_STX | BPF_ATOMIC | BPF_W:
1691 		switch (imm) {
1692 		case BPF_ADD:
1693 		case BPF_ADD | BPF_FETCH:
1694 		case BPF_AND:
1695 		case BPF_AND | BPF_FETCH:
1696 		case BPF_OR:
1697 		case BPF_OR | BPF_FETCH:
1698 		case BPF_XOR:
1699 		case BPF_XOR | BPF_FETCH:
1700 		case BPF_XCHG:
1701 			if (cpu_has_llsc)
1702 				emit_atomic_r(ctx, lo(dst), lo(src), off, imm);
1703 			else /* Non-ll/sc fallback */
1704 				emit_atomic_r32(ctx, lo(dst), lo(src),
1705 						off, imm);
1706 			if (imm & BPF_FETCH)
1707 				emit_zext_ver(ctx, src);
1708 			break;
1709 		case BPF_CMPXCHG:
1710 			if (cpu_has_llsc)
1711 				emit_cmpxchg_r(ctx, lo(dst), lo(src),
1712 					       lo(res), off);
1713 			else /* Non-ll/sc fallback */
1714 				emit_cmpxchg_r32(ctx, lo(dst), lo(src), off);
1715 			/* Result zero-extension inserted by verifier */
1716 			break;
1717 		default:
1718 			goto notyet;
1719 		}
1720 		break;
1721 	/* Atomics (64-bit) */
1722 	case BPF_STX | BPF_ATOMIC | BPF_DW:
1723 		switch (imm) {
1724 		case BPF_ADD:
1725 		case BPF_ADD | BPF_FETCH:
1726 		case BPF_AND:
1727 		case BPF_AND | BPF_FETCH:
1728 		case BPF_OR:
1729 		case BPF_OR | BPF_FETCH:
1730 		case BPF_XOR:
1731 		case BPF_XOR | BPF_FETCH:
1732 		case BPF_XCHG:
1733 			emit_atomic_r64(ctx, lo(dst), src, off, imm);
1734 			break;
1735 		case BPF_CMPXCHG:
1736 			emit_cmpxchg_r64(ctx, lo(dst), src, off);
1737 			break;
1738 		default:
1739 			goto notyet;
1740 		}
1741 		break;
1742 	/* PC += off if dst == src */
1743 	/* PC += off if dst != src */
1744 	/* PC += off if dst & src */
1745 	/* PC += off if dst > src */
1746 	/* PC += off if dst >= src */
1747 	/* PC += off if dst < src */
1748 	/* PC += off if dst <= src */
1749 	/* PC += off if dst > src (signed) */
1750 	/* PC += off if dst >= src (signed) */
1751 	/* PC += off if dst < src (signed) */
1752 	/* PC += off if dst <= src (signed) */
1753 	case BPF_JMP32 | BPF_JEQ | BPF_X:
1754 	case BPF_JMP32 | BPF_JNE | BPF_X:
1755 	case BPF_JMP32 | BPF_JSET | BPF_X:
1756 	case BPF_JMP32 | BPF_JGT | BPF_X:
1757 	case BPF_JMP32 | BPF_JGE | BPF_X:
1758 	case BPF_JMP32 | BPF_JLT | BPF_X:
1759 	case BPF_JMP32 | BPF_JLE | BPF_X:
1760 	case BPF_JMP32 | BPF_JSGT | BPF_X:
1761 	case BPF_JMP32 | BPF_JSGE | BPF_X:
1762 	case BPF_JMP32 | BPF_JSLT | BPF_X:
1763 	case BPF_JMP32 | BPF_JSLE | BPF_X:
1764 		if (off == 0)
1765 			break;
1766 		setup_jmp_r(ctx, dst == src, BPF_OP(code), off, &jmp, &rel);
1767 		emit_jmp_r(ctx, lo(dst), lo(src), rel, jmp);
1768 		if (finish_jmp(ctx, jmp, off) < 0)
1769 			goto toofar;
1770 		break;
1771 	/* PC += off if dst == imm */
1772 	/* PC += off if dst != imm */
1773 	/* PC += off if dst & imm */
1774 	/* PC += off if dst > imm */
1775 	/* PC += off if dst >= imm */
1776 	/* PC += off if dst < imm */
1777 	/* PC += off if dst <= imm */
1778 	/* PC += off if dst > imm (signed) */
1779 	/* PC += off if dst >= imm (signed) */
1780 	/* PC += off if dst < imm (signed) */
1781 	/* PC += off if dst <= imm (signed) */
1782 	case BPF_JMP32 | BPF_JEQ | BPF_K:
1783 	case BPF_JMP32 | BPF_JNE | BPF_K:
1784 	case BPF_JMP32 | BPF_JSET | BPF_K:
1785 	case BPF_JMP32 | BPF_JGT | BPF_K:
1786 	case BPF_JMP32 | BPF_JGE | BPF_K:
1787 	case BPF_JMP32 | BPF_JLT | BPF_K:
1788 	case BPF_JMP32 | BPF_JLE | BPF_K:
1789 	case BPF_JMP32 | BPF_JSGT | BPF_K:
1790 	case BPF_JMP32 | BPF_JSGE | BPF_K:
1791 	case BPF_JMP32 | BPF_JSLT | BPF_K:
1792 	case BPF_JMP32 | BPF_JSLE | BPF_K:
1793 		if (off == 0)
1794 			break;
1795 		setup_jmp_i(ctx, imm, 32, BPF_OP(code), off, &jmp, &rel);
1796 		if (valid_jmp_i(jmp, imm)) {
1797 			emit_jmp_i(ctx, lo(dst), imm, rel, jmp);
1798 		} else {
1799 			/* Move large immediate to register */
1800 			emit_mov_i(ctx, MIPS_R_T6, imm);
1801 			emit_jmp_r(ctx, lo(dst), MIPS_R_T6, rel, jmp);
1802 		}
1803 		if (finish_jmp(ctx, jmp, off) < 0)
1804 			goto toofar;
1805 		break;
1806 	/* PC += off if dst == src */
1807 	/* PC += off if dst != src */
1808 	/* PC += off if dst & src */
1809 	/* PC += off if dst > src */
1810 	/* PC += off if dst >= src */
1811 	/* PC += off if dst < src */
1812 	/* PC += off if dst <= src */
1813 	/* PC += off if dst > src (signed) */
1814 	/* PC += off if dst >= src (signed) */
1815 	/* PC += off if dst < src (signed) */
1816 	/* PC += off if dst <= src (signed) */
1817 	case BPF_JMP | BPF_JEQ | BPF_X:
1818 	case BPF_JMP | BPF_JNE | BPF_X:
1819 	case BPF_JMP | BPF_JSET | BPF_X:
1820 	case BPF_JMP | BPF_JGT | BPF_X:
1821 	case BPF_JMP | BPF_JGE | BPF_X:
1822 	case BPF_JMP | BPF_JLT | BPF_X:
1823 	case BPF_JMP | BPF_JLE | BPF_X:
1824 	case BPF_JMP | BPF_JSGT | BPF_X:
1825 	case BPF_JMP | BPF_JSGE | BPF_X:
1826 	case BPF_JMP | BPF_JSLT | BPF_X:
1827 	case BPF_JMP | BPF_JSLE | BPF_X:
1828 		if (off == 0)
1829 			break;
1830 		setup_jmp_r(ctx, dst == src, BPF_OP(code), off, &jmp, &rel);
1831 		emit_jmp_r64(ctx, dst, src, rel, jmp);
1832 		if (finish_jmp(ctx, jmp, off) < 0)
1833 			goto toofar;
1834 		break;
1835 	/* PC += off if dst == imm */
1836 	/* PC += off if dst != imm */
1837 	/* PC += off if dst & imm */
1838 	/* PC += off if dst > imm */
1839 	/* PC += off if dst >= imm */
1840 	/* PC += off if dst < imm */
1841 	/* PC += off if dst <= imm */
1842 	/* PC += off if dst > imm (signed) */
1843 	/* PC += off if dst >= imm (signed) */
1844 	/* PC += off if dst < imm (signed) */
1845 	/* PC += off if dst <= imm (signed) */
1846 	case BPF_JMP | BPF_JEQ | BPF_K:
1847 	case BPF_JMP | BPF_JNE | BPF_K:
1848 	case BPF_JMP | BPF_JSET | BPF_K:
1849 	case BPF_JMP | BPF_JGT | BPF_K:
1850 	case BPF_JMP | BPF_JGE | BPF_K:
1851 	case BPF_JMP | BPF_JLT | BPF_K:
1852 	case BPF_JMP | BPF_JLE | BPF_K:
1853 	case BPF_JMP | BPF_JSGT | BPF_K:
1854 	case BPF_JMP | BPF_JSGE | BPF_K:
1855 	case BPF_JMP | BPF_JSLT | BPF_K:
1856 	case BPF_JMP | BPF_JSLE | BPF_K:
1857 		if (off == 0)
1858 			break;
1859 		setup_jmp_i(ctx, imm, 64, BPF_OP(code), off, &jmp, &rel);
1860 		emit_jmp_i64(ctx, dst, imm, rel, jmp);
1861 		if (finish_jmp(ctx, jmp, off) < 0)
1862 			goto toofar;
1863 		break;
1864 	/* PC += off */
1865 	case BPF_JMP | BPF_JA:
1866 		if (off == 0)
1867 			break;
1868 		if (emit_ja(ctx, off) < 0)
1869 			goto toofar;
1870 		break;
1871 	/* Tail call */
1872 	case BPF_JMP | BPF_TAIL_CALL:
1873 		if (emit_tail_call(ctx) < 0)
1874 			goto invalid;
1875 		break;
1876 	/* Function call */
1877 	case BPF_JMP | BPF_CALL:
1878 		if (emit_call(ctx, insn) < 0)
1879 			goto invalid;
1880 		break;
1881 	/* Function return */
1882 	case BPF_JMP | BPF_EXIT:
1883 		/*
1884 		 * Optimization: when last instruction is EXIT
1885 		 * simply continue to epilogue.
1886 		 */
1887 		if (ctx->bpf_index == ctx->program->len - 1)
1888 			break;
1889 		if (emit_exit(ctx) < 0)
1890 			goto toofar;
1891 		break;
1892 
1893 	default:
1894 invalid:
1895 		pr_err_once("unknown opcode %02x\n", code);
1896 		return -EINVAL;
1897 notyet:
1898 		pr_info_once("*** NOT YET: opcode %02x ***\n", code);
1899 		return -EFAULT;
1900 toofar:
1901 		pr_info_once("*** TOO FAR: jump at %u opcode %02x ***\n",
1902 			     ctx->bpf_index, code);
1903 		return -E2BIG;
1904 	}
1905 	return 0;
1906 }
1907