xref: /openbmc/linux/arch/x86/net/bpf_jit_comp32.c (revision f89d416a)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Just-In-Time compiler for eBPF filters on IA32 (32bit x86)
4  *
5  * Author: Wang YanQing (udknight@gmail.com)
6  * The code based on code and ideas from:
7  * Eric Dumazet (eric.dumazet@gmail.com)
8  * and from:
9  * Shubham Bansal <illusionist.neo@gmail.com>
10  */
11 
12 #include <linux/netdevice.h>
13 #include <linux/filter.h>
14 #include <linux/if_vlan.h>
15 #include <asm/cacheflush.h>
16 #include <asm/set_memory.h>
17 #include <asm/nospec-branch.h>
18 #include <linux/bpf.h>
19 
20 /*
21  * eBPF prog stack layout:
22  *
23  *                         high
24  * original ESP =>        +-----+
25  *                        |     | callee saved registers
26  *                        +-----+
27  *                        | ... | eBPF JIT scratch space
28  * BPF_FP,IA32_EBP  =>    +-----+
29  *                        | ... | eBPF prog stack
30  *                        +-----+
31  *                        |RSVD | JIT scratchpad
32  * current ESP =>         +-----+
33  *                        |     |
34  *                        | ... | Function call stack
35  *                        |     |
36  *                        +-----+
37  *                          low
38  *
39  * The callee saved registers:
40  *
41  *                                high
42  * original ESP =>        +------------------+ \
43  *                        |        ebp       | |
44  * current EBP =>         +------------------+ } callee saved registers
45  *                        |    ebx,esi,edi   | |
46  *                        +------------------+ /
47  *                                low
48  */
49 
50 static u8 *emit_code(u8 *ptr, u32 bytes, unsigned int len)
51 {
52 	if (len == 1)
53 		*ptr = bytes;
54 	else if (len == 2)
55 		*(u16 *)ptr = bytes;
56 	else {
57 		*(u32 *)ptr = bytes;
58 		barrier();
59 	}
60 	return ptr + len;
61 }
62 
63 #define EMIT(bytes, len) \
64 	do { prog = emit_code(prog, bytes, len); cnt += len; } while (0)
65 
66 #define EMIT1(b1)		EMIT(b1, 1)
67 #define EMIT2(b1, b2)		EMIT((b1) + ((b2) << 8), 2)
68 #define EMIT3(b1, b2, b3)	EMIT((b1) + ((b2) << 8) + ((b3) << 16), 3)
69 #define EMIT4(b1, b2, b3, b4)   \
70 	EMIT((b1) + ((b2) << 8) + ((b3) << 16) + ((b4) << 24), 4)
71 
72 #define EMIT1_off32(b1, off) \
73 	do { EMIT1(b1); EMIT(off, 4); } while (0)
74 #define EMIT2_off32(b1, b2, off) \
75 	do { EMIT2(b1, b2); EMIT(off, 4); } while (0)
76 #define EMIT3_off32(b1, b2, b3, off) \
77 	do { EMIT3(b1, b2, b3); EMIT(off, 4); } while (0)
78 #define EMIT4_off32(b1, b2, b3, b4, off) \
79 	do { EMIT4(b1, b2, b3, b4); EMIT(off, 4); } while (0)
80 
81 #define jmp_label(label, jmp_insn_len) (label - cnt - jmp_insn_len)
82 
83 static bool is_imm8(int value)
84 {
85 	return value <= 127 && value >= -128;
86 }
87 
88 static bool is_simm32(s64 value)
89 {
90 	return value == (s64) (s32) value;
91 }
92 
93 #define STACK_OFFSET(k)	(k)
94 #define TCALL_CNT	(MAX_BPF_JIT_REG + 0)	/* Tail Call Count */
95 
96 #define IA32_EAX	(0x0)
97 #define IA32_EBX	(0x3)
98 #define IA32_ECX	(0x1)
99 #define IA32_EDX	(0x2)
100 #define IA32_ESI	(0x6)
101 #define IA32_EDI	(0x7)
102 #define IA32_EBP	(0x5)
103 #define IA32_ESP	(0x4)
104 
105 /*
106  * List of x86 cond jumps opcodes (. + s8)
107  * Add 0x10 (and an extra 0x0f) to generate far jumps (. + s32)
108  */
109 #define IA32_JB  0x72
110 #define IA32_JAE 0x73
111 #define IA32_JE  0x74
112 #define IA32_JNE 0x75
113 #define IA32_JBE 0x76
114 #define IA32_JA  0x77
115 #define IA32_JL  0x7C
116 #define IA32_JGE 0x7D
117 #define IA32_JLE 0x7E
118 #define IA32_JG  0x7F
119 
120 #define COND_JMP_OPCODE_INVALID	(0xFF)
121 
122 /*
123  * Map eBPF registers to IA32 32bit registers or stack scratch space.
124  *
125  * 1. All the registers, R0-R10, are mapped to scratch space on stack.
126  * 2. We need two 64 bit temp registers to do complex operations on eBPF
127  *    registers.
128  * 3. For performance reason, the BPF_REG_AX for blinding constant, is
129  *    mapped to real hardware register pair, IA32_ESI and IA32_EDI.
130  *
131  * As the eBPF registers are all 64 bit registers and IA32 has only 32 bit
132  * registers, we have to map each eBPF registers with two IA32 32 bit regs
133  * or scratch memory space and we have to build eBPF 64 bit register from those.
134  *
135  * We use IA32_EAX, IA32_EDX, IA32_ECX, IA32_EBX as temporary registers.
136  */
137 static const u8 bpf2ia32[][2] = {
138 	/* Return value from in-kernel function, and exit value from eBPF */
139 	[BPF_REG_0] = {STACK_OFFSET(0), STACK_OFFSET(4)},
140 
141 	/* The arguments from eBPF program to in-kernel function */
142 	/* Stored on stack scratch space */
143 	[BPF_REG_1] = {STACK_OFFSET(8), STACK_OFFSET(12)},
144 	[BPF_REG_2] = {STACK_OFFSET(16), STACK_OFFSET(20)},
145 	[BPF_REG_3] = {STACK_OFFSET(24), STACK_OFFSET(28)},
146 	[BPF_REG_4] = {STACK_OFFSET(32), STACK_OFFSET(36)},
147 	[BPF_REG_5] = {STACK_OFFSET(40), STACK_OFFSET(44)},
148 
149 	/* Callee saved registers that in-kernel function will preserve */
150 	/* Stored on stack scratch space */
151 	[BPF_REG_6] = {STACK_OFFSET(48), STACK_OFFSET(52)},
152 	[BPF_REG_7] = {STACK_OFFSET(56), STACK_OFFSET(60)},
153 	[BPF_REG_8] = {STACK_OFFSET(64), STACK_OFFSET(68)},
154 	[BPF_REG_9] = {STACK_OFFSET(72), STACK_OFFSET(76)},
155 
156 	/* Read only Frame Pointer to access Stack */
157 	[BPF_REG_FP] = {STACK_OFFSET(80), STACK_OFFSET(84)},
158 
159 	/* Temporary register for blinding constants. */
160 	[BPF_REG_AX] = {IA32_ESI, IA32_EDI},
161 
162 	/* Tail call count. Stored on stack scratch space. */
163 	[TCALL_CNT] = {STACK_OFFSET(88), STACK_OFFSET(92)},
164 };
165 
166 #define dst_lo	dst[0]
167 #define dst_hi	dst[1]
168 #define src_lo	src[0]
169 #define src_hi	src[1]
170 
171 #define STACK_ALIGNMENT	8
172 /*
173  * Stack space for BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4,
174  * BPF_REG_5, BPF_REG_6, BPF_REG_7, BPF_REG_8, BPF_REG_9,
175  * BPF_REG_FP, BPF_REG_AX and Tail call counts.
176  */
177 #define SCRATCH_SIZE 96
178 
179 /* Total stack size used in JITed code */
180 #define _STACK_SIZE	(stack_depth + SCRATCH_SIZE)
181 
182 #define STACK_SIZE ALIGN(_STACK_SIZE, STACK_ALIGNMENT)
183 
184 /* Get the offset of eBPF REGISTERs stored on scratch space. */
185 #define STACK_VAR(off) (off)
186 
187 /* Encode 'dst_reg' register into IA32 opcode 'byte' */
188 static u8 add_1reg(u8 byte, u32 dst_reg)
189 {
190 	return byte + dst_reg;
191 }
192 
193 /* Encode 'dst_reg' and 'src_reg' registers into IA32 opcode 'byte' */
194 static u8 add_2reg(u8 byte, u32 dst_reg, u32 src_reg)
195 {
196 	return byte + dst_reg + (src_reg << 3);
197 }
198 
199 static void jit_fill_hole(void *area, unsigned int size)
200 {
201 	/* Fill whole space with int3 instructions */
202 	memset(area, 0xcc, size);
203 }
204 
205 static inline void emit_ia32_mov_i(const u8 dst, const u32 val, bool dstk,
206 				   u8 **pprog)
207 {
208 	u8 *prog = *pprog;
209 	int cnt = 0;
210 
211 	if (dstk) {
212 		if (val == 0) {
213 			/* xor eax,eax */
214 			EMIT2(0x33, add_2reg(0xC0, IA32_EAX, IA32_EAX));
215 			/* mov dword ptr [ebp+off],eax */
216 			EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
217 			      STACK_VAR(dst));
218 		} else {
219 			EMIT3_off32(0xC7, add_1reg(0x40, IA32_EBP),
220 				    STACK_VAR(dst), val);
221 		}
222 	} else {
223 		if (val == 0)
224 			EMIT2(0x33, add_2reg(0xC0, dst, dst));
225 		else
226 			EMIT2_off32(0xC7, add_1reg(0xC0, dst),
227 				    val);
228 	}
229 	*pprog = prog;
230 }
231 
232 /* dst = imm (4 bytes)*/
233 static inline void emit_ia32_mov_r(const u8 dst, const u8 src, bool dstk,
234 				   bool sstk, u8 **pprog)
235 {
236 	u8 *prog = *pprog;
237 	int cnt = 0;
238 	u8 sreg = sstk ? IA32_EAX : src;
239 
240 	if (sstk)
241 		/* mov eax,dword ptr [ebp+off] */
242 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(src));
243 	if (dstk)
244 		/* mov dword ptr [ebp+off],eax */
245 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, sreg), STACK_VAR(dst));
246 	else
247 		/* mov dst,sreg */
248 		EMIT2(0x89, add_2reg(0xC0, dst, sreg));
249 
250 	*pprog = prog;
251 }
252 
253 /* dst = src */
254 static inline void emit_ia32_mov_r64(const bool is64, const u8 dst[],
255 				     const u8 src[], bool dstk,
256 				     bool sstk, u8 **pprog,
257 				     const struct bpf_prog_aux *aux)
258 {
259 	emit_ia32_mov_r(dst_lo, src_lo, dstk, sstk, pprog);
260 	if (is64)
261 		/* complete 8 byte move */
262 		emit_ia32_mov_r(dst_hi, src_hi, dstk, sstk, pprog);
263 	else if (!aux->verifier_zext)
264 		/* zero out high 4 bytes */
265 		emit_ia32_mov_i(dst_hi, 0, dstk, pprog);
266 }
267 
268 /* Sign extended move */
269 static inline void emit_ia32_mov_i64(const bool is64, const u8 dst[],
270 				     const u32 val, bool dstk, u8 **pprog)
271 {
272 	u32 hi = 0;
273 
274 	if (is64 && (val & (1<<31)))
275 		hi = (u32)~0;
276 	emit_ia32_mov_i(dst_lo, val, dstk, pprog);
277 	emit_ia32_mov_i(dst_hi, hi, dstk, pprog);
278 }
279 
280 /*
281  * ALU operation (32 bit)
282  * dst = dst * src
283  */
284 static inline void emit_ia32_mul_r(const u8 dst, const u8 src, bool dstk,
285 				   bool sstk, u8 **pprog)
286 {
287 	u8 *prog = *pprog;
288 	int cnt = 0;
289 	u8 sreg = sstk ? IA32_ECX : src;
290 
291 	if (sstk)
292 		/* mov ecx,dword ptr [ebp+off] */
293 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src));
294 
295 	if (dstk)
296 		/* mov eax,dword ptr [ebp+off] */
297 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(dst));
298 	else
299 		/* mov eax,dst */
300 		EMIT2(0x8B, add_2reg(0xC0, dst, IA32_EAX));
301 
302 
303 	EMIT2(0xF7, add_1reg(0xE0, sreg));
304 
305 	if (dstk)
306 		/* mov dword ptr [ebp+off],eax */
307 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
308 		      STACK_VAR(dst));
309 	else
310 		/* mov dst,eax */
311 		EMIT2(0x89, add_2reg(0xC0, dst, IA32_EAX));
312 
313 	*pprog = prog;
314 }
315 
316 static inline void emit_ia32_to_le_r64(const u8 dst[], s32 val,
317 					 bool dstk, u8 **pprog,
318 					 const struct bpf_prog_aux *aux)
319 {
320 	u8 *prog = *pprog;
321 	int cnt = 0;
322 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
323 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
324 
325 	if (dstk && val != 64) {
326 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
327 		      STACK_VAR(dst_lo));
328 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
329 		      STACK_VAR(dst_hi));
330 	}
331 	switch (val) {
332 	case 16:
333 		/*
334 		 * Emit 'movzwl eax,ax' to zero extend 16-bit
335 		 * into 64 bit
336 		 */
337 		EMIT2(0x0F, 0xB7);
338 		EMIT1(add_2reg(0xC0, dreg_lo, dreg_lo));
339 		if (!aux->verifier_zext)
340 			/* xor dreg_hi,dreg_hi */
341 			EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
342 		break;
343 	case 32:
344 		if (!aux->verifier_zext)
345 			/* xor dreg_hi,dreg_hi */
346 			EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
347 		break;
348 	case 64:
349 		/* nop */
350 		break;
351 	}
352 
353 	if (dstk && val != 64) {
354 		/* mov dword ptr [ebp+off],dreg_lo */
355 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
356 		      STACK_VAR(dst_lo));
357 		/* mov dword ptr [ebp+off],dreg_hi */
358 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
359 		      STACK_VAR(dst_hi));
360 	}
361 	*pprog = prog;
362 }
363 
364 static inline void emit_ia32_to_be_r64(const u8 dst[], s32 val,
365 				       bool dstk, u8 **pprog,
366 				       const struct bpf_prog_aux *aux)
367 {
368 	u8 *prog = *pprog;
369 	int cnt = 0;
370 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
371 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
372 
373 	if (dstk) {
374 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
375 		      STACK_VAR(dst_lo));
376 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
377 		      STACK_VAR(dst_hi));
378 	}
379 	switch (val) {
380 	case 16:
381 		/* Emit 'ror %ax, 8' to swap lower 2 bytes */
382 		EMIT1(0x66);
383 		EMIT3(0xC1, add_1reg(0xC8, dreg_lo), 8);
384 
385 		EMIT2(0x0F, 0xB7);
386 		EMIT1(add_2reg(0xC0, dreg_lo, dreg_lo));
387 
388 		if (!aux->verifier_zext)
389 			/* xor dreg_hi,dreg_hi */
390 			EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
391 		break;
392 	case 32:
393 		/* Emit 'bswap eax' to swap lower 4 bytes */
394 		EMIT1(0x0F);
395 		EMIT1(add_1reg(0xC8, dreg_lo));
396 
397 		if (!aux->verifier_zext)
398 			/* xor dreg_hi,dreg_hi */
399 			EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
400 		break;
401 	case 64:
402 		/* Emit 'bswap eax' to swap lower 4 bytes */
403 		EMIT1(0x0F);
404 		EMIT1(add_1reg(0xC8, dreg_lo));
405 
406 		/* Emit 'bswap edx' to swap lower 4 bytes */
407 		EMIT1(0x0F);
408 		EMIT1(add_1reg(0xC8, dreg_hi));
409 
410 		/* mov ecx,dreg_hi */
411 		EMIT2(0x89, add_2reg(0xC0, IA32_ECX, dreg_hi));
412 		/* mov dreg_hi,dreg_lo */
413 		EMIT2(0x89, add_2reg(0xC0, dreg_hi, dreg_lo));
414 		/* mov dreg_lo,ecx */
415 		EMIT2(0x89, add_2reg(0xC0, dreg_lo, IA32_ECX));
416 
417 		break;
418 	}
419 	if (dstk) {
420 		/* mov dword ptr [ebp+off],dreg_lo */
421 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
422 		      STACK_VAR(dst_lo));
423 		/* mov dword ptr [ebp+off],dreg_hi */
424 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
425 		      STACK_VAR(dst_hi));
426 	}
427 	*pprog = prog;
428 }
429 
430 /*
431  * ALU operation (32 bit)
432  * dst = dst (div|mod) src
433  */
434 static inline void emit_ia32_div_mod_r(const u8 op, const u8 dst, const u8 src,
435 				       bool dstk, bool sstk, u8 **pprog)
436 {
437 	u8 *prog = *pprog;
438 	int cnt = 0;
439 
440 	if (sstk)
441 		/* mov ecx,dword ptr [ebp+off] */
442 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
443 		      STACK_VAR(src));
444 	else if (src != IA32_ECX)
445 		/* mov ecx,src */
446 		EMIT2(0x8B, add_2reg(0xC0, src, IA32_ECX));
447 
448 	if (dstk)
449 		/* mov eax,dword ptr [ebp+off] */
450 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
451 		      STACK_VAR(dst));
452 	else
453 		/* mov eax,dst */
454 		EMIT2(0x8B, add_2reg(0xC0, dst, IA32_EAX));
455 
456 	/* xor edx,edx */
457 	EMIT2(0x31, add_2reg(0xC0, IA32_EDX, IA32_EDX));
458 	/* div ecx */
459 	EMIT2(0xF7, add_1reg(0xF0, IA32_ECX));
460 
461 	if (op == BPF_MOD) {
462 		if (dstk)
463 			EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
464 			      STACK_VAR(dst));
465 		else
466 			EMIT2(0x89, add_2reg(0xC0, dst, IA32_EDX));
467 	} else {
468 		if (dstk)
469 			EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
470 			      STACK_VAR(dst));
471 		else
472 			EMIT2(0x89, add_2reg(0xC0, dst, IA32_EAX));
473 	}
474 	*pprog = prog;
475 }
476 
477 /*
478  * ALU operation (32 bit)
479  * dst = dst (shift) src
480  */
481 static inline void emit_ia32_shift_r(const u8 op, const u8 dst, const u8 src,
482 				     bool dstk, bool sstk, u8 **pprog)
483 {
484 	u8 *prog = *pprog;
485 	int cnt = 0;
486 	u8 dreg = dstk ? IA32_EAX : dst;
487 	u8 b2;
488 
489 	if (dstk)
490 		/* mov eax,dword ptr [ebp+off] */
491 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(dst));
492 
493 	if (sstk)
494 		/* mov ecx,dword ptr [ebp+off] */
495 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src));
496 	else if (src != IA32_ECX)
497 		/* mov ecx,src */
498 		EMIT2(0x8B, add_2reg(0xC0, src, IA32_ECX));
499 
500 	switch (op) {
501 	case BPF_LSH:
502 		b2 = 0xE0; break;
503 	case BPF_RSH:
504 		b2 = 0xE8; break;
505 	case BPF_ARSH:
506 		b2 = 0xF8; break;
507 	default:
508 		return;
509 	}
510 	EMIT2(0xD3, add_1reg(b2, dreg));
511 
512 	if (dstk)
513 		/* mov dword ptr [ebp+off],dreg */
514 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg), STACK_VAR(dst));
515 	*pprog = prog;
516 }
517 
518 /*
519  * ALU operation (32 bit)
520  * dst = dst (op) src
521  */
522 static inline void emit_ia32_alu_r(const bool is64, const bool hi, const u8 op,
523 				   const u8 dst, const u8 src, bool dstk,
524 				   bool sstk, u8 **pprog)
525 {
526 	u8 *prog = *pprog;
527 	int cnt = 0;
528 	u8 sreg = sstk ? IA32_EAX : src;
529 	u8 dreg = dstk ? IA32_EDX : dst;
530 
531 	if (sstk)
532 		/* mov eax,dword ptr [ebp+off] */
533 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(src));
534 
535 	if (dstk)
536 		/* mov eax,dword ptr [ebp+off] */
537 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX), STACK_VAR(dst));
538 
539 	switch (BPF_OP(op)) {
540 	/* dst = dst + src */
541 	case BPF_ADD:
542 		if (hi && is64)
543 			EMIT2(0x11, add_2reg(0xC0, dreg, sreg));
544 		else
545 			EMIT2(0x01, add_2reg(0xC0, dreg, sreg));
546 		break;
547 	/* dst = dst - src */
548 	case BPF_SUB:
549 		if (hi && is64)
550 			EMIT2(0x19, add_2reg(0xC0, dreg, sreg));
551 		else
552 			EMIT2(0x29, add_2reg(0xC0, dreg, sreg));
553 		break;
554 	/* dst = dst | src */
555 	case BPF_OR:
556 		EMIT2(0x09, add_2reg(0xC0, dreg, sreg));
557 		break;
558 	/* dst = dst & src */
559 	case BPF_AND:
560 		EMIT2(0x21, add_2reg(0xC0, dreg, sreg));
561 		break;
562 	/* dst = dst ^ src */
563 	case BPF_XOR:
564 		EMIT2(0x31, add_2reg(0xC0, dreg, sreg));
565 		break;
566 	}
567 
568 	if (dstk)
569 		/* mov dword ptr [ebp+off],dreg */
570 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg),
571 		      STACK_VAR(dst));
572 	*pprog = prog;
573 }
574 
575 /* ALU operation (64 bit) */
576 static inline void emit_ia32_alu_r64(const bool is64, const u8 op,
577 				     const u8 dst[], const u8 src[],
578 				     bool dstk,  bool sstk,
579 				     u8 **pprog, const struct bpf_prog_aux *aux)
580 {
581 	u8 *prog = *pprog;
582 
583 	emit_ia32_alu_r(is64, false, op, dst_lo, src_lo, dstk, sstk, &prog);
584 	if (is64)
585 		emit_ia32_alu_r(is64, true, op, dst_hi, src_hi, dstk, sstk,
586 				&prog);
587 	else if (!aux->verifier_zext)
588 		emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
589 	*pprog = prog;
590 }
591 
592 /*
593  * ALU operation (32 bit)
594  * dst = dst (op) val
595  */
596 static inline void emit_ia32_alu_i(const bool is64, const bool hi, const u8 op,
597 				   const u8 dst, const s32 val, bool dstk,
598 				   u8 **pprog)
599 {
600 	u8 *prog = *pprog;
601 	int cnt = 0;
602 	u8 dreg = dstk ? IA32_EAX : dst;
603 	u8 sreg = IA32_EDX;
604 
605 	if (dstk)
606 		/* mov eax,dword ptr [ebp+off] */
607 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(dst));
608 
609 	if (!is_imm8(val))
610 		/* mov edx,imm32*/
611 		EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EDX), val);
612 
613 	switch (op) {
614 	/* dst = dst + val */
615 	case BPF_ADD:
616 		if (hi && is64) {
617 			if (is_imm8(val))
618 				EMIT3(0x83, add_1reg(0xD0, dreg), val);
619 			else
620 				EMIT2(0x11, add_2reg(0xC0, dreg, sreg));
621 		} else {
622 			if (is_imm8(val))
623 				EMIT3(0x83, add_1reg(0xC0, dreg), val);
624 			else
625 				EMIT2(0x01, add_2reg(0xC0, dreg, sreg));
626 		}
627 		break;
628 	/* dst = dst - val */
629 	case BPF_SUB:
630 		if (hi && is64) {
631 			if (is_imm8(val))
632 				EMIT3(0x83, add_1reg(0xD8, dreg), val);
633 			else
634 				EMIT2(0x19, add_2reg(0xC0, dreg, sreg));
635 		} else {
636 			if (is_imm8(val))
637 				EMIT3(0x83, add_1reg(0xE8, dreg), val);
638 			else
639 				EMIT2(0x29, add_2reg(0xC0, dreg, sreg));
640 		}
641 		break;
642 	/* dst = dst | val */
643 	case BPF_OR:
644 		if (is_imm8(val))
645 			EMIT3(0x83, add_1reg(0xC8, dreg), val);
646 		else
647 			EMIT2(0x09, add_2reg(0xC0, dreg, sreg));
648 		break;
649 	/* dst = dst & val */
650 	case BPF_AND:
651 		if (is_imm8(val))
652 			EMIT3(0x83, add_1reg(0xE0, dreg), val);
653 		else
654 			EMIT2(0x21, add_2reg(0xC0, dreg, sreg));
655 		break;
656 	/* dst = dst ^ val */
657 	case BPF_XOR:
658 		if (is_imm8(val))
659 			EMIT3(0x83, add_1reg(0xF0, dreg), val);
660 		else
661 			EMIT2(0x31, add_2reg(0xC0, dreg, sreg));
662 		break;
663 	case BPF_NEG:
664 		EMIT2(0xF7, add_1reg(0xD8, dreg));
665 		break;
666 	}
667 
668 	if (dstk)
669 		/* mov dword ptr [ebp+off],dreg */
670 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg),
671 		      STACK_VAR(dst));
672 	*pprog = prog;
673 }
674 
675 /* ALU operation (64 bit) */
676 static inline void emit_ia32_alu_i64(const bool is64, const u8 op,
677 				     const u8 dst[], const u32 val,
678 				     bool dstk, u8 **pprog,
679 				     const struct bpf_prog_aux *aux)
680 {
681 	u8 *prog = *pprog;
682 	u32 hi = 0;
683 
684 	if (is64 && (val & (1<<31)))
685 		hi = (u32)~0;
686 
687 	emit_ia32_alu_i(is64, false, op, dst_lo, val, dstk, &prog);
688 	if (is64)
689 		emit_ia32_alu_i(is64, true, op, dst_hi, hi, dstk, &prog);
690 	else if (!aux->verifier_zext)
691 		emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
692 
693 	*pprog = prog;
694 }
695 
696 /* dst = ~dst (64 bit) */
697 static inline void emit_ia32_neg64(const u8 dst[], bool dstk, u8 **pprog)
698 {
699 	u8 *prog = *pprog;
700 	int cnt = 0;
701 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
702 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
703 
704 	if (dstk) {
705 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
706 		      STACK_VAR(dst_lo));
707 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
708 		      STACK_VAR(dst_hi));
709 	}
710 
711 	/* neg dreg_lo */
712 	EMIT2(0xF7, add_1reg(0xD8, dreg_lo));
713 	/* adc dreg_hi,0x0 */
714 	EMIT3(0x83, add_1reg(0xD0, dreg_hi), 0x00);
715 	/* neg dreg_hi */
716 	EMIT2(0xF7, add_1reg(0xD8, dreg_hi));
717 
718 	if (dstk) {
719 		/* mov dword ptr [ebp+off],dreg_lo */
720 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
721 		      STACK_VAR(dst_lo));
722 		/* mov dword ptr [ebp+off],dreg_hi */
723 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
724 		      STACK_VAR(dst_hi));
725 	}
726 	*pprog = prog;
727 }
728 
729 /* dst = dst << src */
730 static inline void emit_ia32_lsh_r64(const u8 dst[], const u8 src[],
731 				     bool dstk, bool sstk, u8 **pprog)
732 {
733 	u8 *prog = *pprog;
734 	int cnt = 0;
735 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
736 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
737 
738 	if (dstk) {
739 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
740 		      STACK_VAR(dst_lo));
741 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
742 		      STACK_VAR(dst_hi));
743 	}
744 
745 	if (sstk)
746 		/* mov ecx,dword ptr [ebp+off] */
747 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
748 		      STACK_VAR(src_lo));
749 	else
750 		/* mov ecx,src_lo */
751 		EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_ECX));
752 
753 	/* shld dreg_hi,dreg_lo,cl */
754 	EMIT3(0x0F, 0xA5, add_2reg(0xC0, dreg_hi, dreg_lo));
755 	/* shl dreg_lo,cl */
756 	EMIT2(0xD3, add_1reg(0xE0, dreg_lo));
757 
758 	/* if ecx >= 32, mov dreg_lo into dreg_hi and clear dreg_lo */
759 
760 	/* cmp ecx,32 */
761 	EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 32);
762 	/* skip the next two instructions (4 bytes) when < 32 */
763 	EMIT2(IA32_JB, 4);
764 
765 	/* mov dreg_hi,dreg_lo */
766 	EMIT2(0x89, add_2reg(0xC0, dreg_hi, dreg_lo));
767 	/* xor dreg_lo,dreg_lo */
768 	EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
769 
770 	if (dstk) {
771 		/* mov dword ptr [ebp+off],dreg_lo */
772 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
773 		      STACK_VAR(dst_lo));
774 		/* mov dword ptr [ebp+off],dreg_hi */
775 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
776 		      STACK_VAR(dst_hi));
777 	}
778 	/* out: */
779 	*pprog = prog;
780 }
781 
782 /* dst = dst >> src (signed)*/
783 static inline void emit_ia32_arsh_r64(const u8 dst[], const u8 src[],
784 				      bool dstk, bool sstk, u8 **pprog)
785 {
786 	u8 *prog = *pprog;
787 	int cnt = 0;
788 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
789 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
790 
791 	if (dstk) {
792 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
793 		      STACK_VAR(dst_lo));
794 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
795 		      STACK_VAR(dst_hi));
796 	}
797 
798 	if (sstk)
799 		/* mov ecx,dword ptr [ebp+off] */
800 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
801 		      STACK_VAR(src_lo));
802 	else
803 		/* mov ecx,src_lo */
804 		EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_ECX));
805 
806 	/* shrd dreg_lo,dreg_hi,cl */
807 	EMIT3(0x0F, 0xAD, add_2reg(0xC0, dreg_lo, dreg_hi));
808 	/* sar dreg_hi,cl */
809 	EMIT2(0xD3, add_1reg(0xF8, dreg_hi));
810 
811 	/* if ecx >= 32, mov dreg_hi to dreg_lo and set/clear dreg_hi depending on sign */
812 
813 	/* cmp ecx,32 */
814 	EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 32);
815 	/* skip the next two instructions (5 bytes) when < 32 */
816 	EMIT2(IA32_JB, 5);
817 
818 	/* mov dreg_lo,dreg_hi */
819 	EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
820 	/* sar dreg_hi,31 */
821 	EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
822 
823 	if (dstk) {
824 		/* mov dword ptr [ebp+off],dreg_lo */
825 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
826 		      STACK_VAR(dst_lo));
827 		/* mov dword ptr [ebp+off],dreg_hi */
828 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
829 		      STACK_VAR(dst_hi));
830 	}
831 	/* out: */
832 	*pprog = prog;
833 }
834 
835 /* dst = dst >> src */
836 static inline void emit_ia32_rsh_r64(const u8 dst[], const u8 src[], bool dstk,
837 				     bool sstk, u8 **pprog)
838 {
839 	u8 *prog = *pprog;
840 	int cnt = 0;
841 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
842 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
843 
844 	if (dstk) {
845 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
846 		      STACK_VAR(dst_lo));
847 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
848 		      STACK_VAR(dst_hi));
849 	}
850 
851 	if (sstk)
852 		/* mov ecx,dword ptr [ebp+off] */
853 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
854 		      STACK_VAR(src_lo));
855 	else
856 		/* mov ecx,src_lo */
857 		EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_ECX));
858 
859 	/* shrd dreg_lo,dreg_hi,cl */
860 	EMIT3(0x0F, 0xAD, add_2reg(0xC0, dreg_lo, dreg_hi));
861 	/* shr dreg_hi,cl */
862 	EMIT2(0xD3, add_1reg(0xE8, dreg_hi));
863 
864 	/* if ecx >= 32, mov dreg_hi to dreg_lo and clear dreg_hi */
865 
866 	/* cmp ecx,32 */
867 	EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 32);
868 	/* skip the next two instructions (4 bytes) when < 32 */
869 	EMIT2(IA32_JB, 4);
870 
871 	/* mov dreg_lo,dreg_hi */
872 	EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
873 	/* xor dreg_hi,dreg_hi */
874 	EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
875 
876 	if (dstk) {
877 		/* mov dword ptr [ebp+off],dreg_lo */
878 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
879 		      STACK_VAR(dst_lo));
880 		/* mov dword ptr [ebp+off],dreg_hi */
881 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
882 		      STACK_VAR(dst_hi));
883 	}
884 	/* out: */
885 	*pprog = prog;
886 }
887 
888 /* dst = dst << val */
889 static inline void emit_ia32_lsh_i64(const u8 dst[], const u32 val,
890 				     bool dstk, u8 **pprog)
891 {
892 	u8 *prog = *pprog;
893 	int cnt = 0;
894 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
895 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
896 
897 	if (dstk) {
898 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
899 		      STACK_VAR(dst_lo));
900 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
901 		      STACK_VAR(dst_hi));
902 	}
903 	/* Do LSH operation */
904 	if (val < 32) {
905 		/* shld dreg_hi,dreg_lo,imm8 */
906 		EMIT4(0x0F, 0xA4, add_2reg(0xC0, dreg_hi, dreg_lo), val);
907 		/* shl dreg_lo,imm8 */
908 		EMIT3(0xC1, add_1reg(0xE0, dreg_lo), val);
909 	} else if (val >= 32 && val < 64) {
910 		u32 value = val - 32;
911 
912 		/* shl dreg_lo,imm8 */
913 		EMIT3(0xC1, add_1reg(0xE0, dreg_lo), value);
914 		/* mov dreg_hi,dreg_lo */
915 		EMIT2(0x89, add_2reg(0xC0, dreg_hi, dreg_lo));
916 		/* xor dreg_lo,dreg_lo */
917 		EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
918 	} else {
919 		/* xor dreg_lo,dreg_lo */
920 		EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
921 		/* xor dreg_hi,dreg_hi */
922 		EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
923 	}
924 
925 	if (dstk) {
926 		/* mov dword ptr [ebp+off],dreg_lo */
927 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
928 		      STACK_VAR(dst_lo));
929 		/* mov dword ptr [ebp+off],dreg_hi */
930 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
931 		      STACK_VAR(dst_hi));
932 	}
933 	*pprog = prog;
934 }
935 
936 /* dst = dst >> val */
937 static inline void emit_ia32_rsh_i64(const u8 dst[], const u32 val,
938 				     bool dstk, u8 **pprog)
939 {
940 	u8 *prog = *pprog;
941 	int cnt = 0;
942 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
943 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
944 
945 	if (dstk) {
946 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
947 		      STACK_VAR(dst_lo));
948 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
949 		      STACK_VAR(dst_hi));
950 	}
951 
952 	/* Do RSH operation */
953 	if (val < 32) {
954 		/* shrd dreg_lo,dreg_hi,imm8 */
955 		EMIT4(0x0F, 0xAC, add_2reg(0xC0, dreg_lo, dreg_hi), val);
956 		/* shr dreg_hi,imm8 */
957 		EMIT3(0xC1, add_1reg(0xE8, dreg_hi), val);
958 	} else if (val >= 32 && val < 64) {
959 		u32 value = val - 32;
960 
961 		/* shr dreg_hi,imm8 */
962 		EMIT3(0xC1, add_1reg(0xE8, dreg_hi), value);
963 		/* mov dreg_lo,dreg_hi */
964 		EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
965 		/* xor dreg_hi,dreg_hi */
966 		EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
967 	} else {
968 		/* xor dreg_lo,dreg_lo */
969 		EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
970 		/* xor dreg_hi,dreg_hi */
971 		EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
972 	}
973 
974 	if (dstk) {
975 		/* mov dword ptr [ebp+off],dreg_lo */
976 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
977 		      STACK_VAR(dst_lo));
978 		/* mov dword ptr [ebp+off],dreg_hi */
979 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
980 		      STACK_VAR(dst_hi));
981 	}
982 	*pprog = prog;
983 }
984 
985 /* dst = dst >> val (signed) */
986 static inline void emit_ia32_arsh_i64(const u8 dst[], const u32 val,
987 				      bool dstk, u8 **pprog)
988 {
989 	u8 *prog = *pprog;
990 	int cnt = 0;
991 	u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
992 	u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
993 
994 	if (dstk) {
995 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
996 		      STACK_VAR(dst_lo));
997 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
998 		      STACK_VAR(dst_hi));
999 	}
1000 	/* Do RSH operation */
1001 	if (val < 32) {
1002 		/* shrd dreg_lo,dreg_hi,imm8 */
1003 		EMIT4(0x0F, 0xAC, add_2reg(0xC0, dreg_lo, dreg_hi), val);
1004 		/* ashr dreg_hi,imm8 */
1005 		EMIT3(0xC1, add_1reg(0xF8, dreg_hi), val);
1006 	} else if (val >= 32 && val < 64) {
1007 		u32 value = val - 32;
1008 
1009 		/* ashr dreg_hi,imm8 */
1010 		EMIT3(0xC1, add_1reg(0xF8, dreg_hi), value);
1011 		/* mov dreg_lo,dreg_hi */
1012 		EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
1013 
1014 		/* ashr dreg_hi,imm8 */
1015 		EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
1016 	} else {
1017 		/* ashr dreg_hi,imm8 */
1018 		EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
1019 		/* mov dreg_lo,dreg_hi */
1020 		EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
1021 	}
1022 
1023 	if (dstk) {
1024 		/* mov dword ptr [ebp+off],dreg_lo */
1025 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
1026 		      STACK_VAR(dst_lo));
1027 		/* mov dword ptr [ebp+off],dreg_hi */
1028 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
1029 		      STACK_VAR(dst_hi));
1030 	}
1031 	*pprog = prog;
1032 }
1033 
1034 static inline void emit_ia32_mul_r64(const u8 dst[], const u8 src[], bool dstk,
1035 				     bool sstk, u8 **pprog)
1036 {
1037 	u8 *prog = *pprog;
1038 	int cnt = 0;
1039 
1040 	if (dstk)
1041 		/* mov eax,dword ptr [ebp+off] */
1042 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1043 		      STACK_VAR(dst_hi));
1044 	else
1045 		/* mov eax,dst_hi */
1046 		EMIT2(0x8B, add_2reg(0xC0, dst_hi, IA32_EAX));
1047 
1048 	if (sstk)
1049 		/* mul dword ptr [ebp+off] */
1050 		EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(src_lo));
1051 	else
1052 		/* mul src_lo */
1053 		EMIT2(0xF7, add_1reg(0xE0, src_lo));
1054 
1055 	/* mov ecx,eax */
1056 	EMIT2(0x89, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1057 
1058 	if (dstk)
1059 		/* mov eax,dword ptr [ebp+off] */
1060 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1061 		      STACK_VAR(dst_lo));
1062 	else
1063 		/* mov eax,dst_lo */
1064 		EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1065 
1066 	if (sstk)
1067 		/* mul dword ptr [ebp+off] */
1068 		EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(src_hi));
1069 	else
1070 		/* mul src_hi */
1071 		EMIT2(0xF7, add_1reg(0xE0, src_hi));
1072 
1073 	/* add eax,eax */
1074 	EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1075 
1076 	if (dstk)
1077 		/* mov eax,dword ptr [ebp+off] */
1078 		EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1079 		      STACK_VAR(dst_lo));
1080 	else
1081 		/* mov eax,dst_lo */
1082 		EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1083 
1084 	if (sstk)
1085 		/* mul dword ptr [ebp+off] */
1086 		EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(src_lo));
1087 	else
1088 		/* mul src_lo */
1089 		EMIT2(0xF7, add_1reg(0xE0, src_lo));
1090 
1091 	/* add ecx,edx */
1092 	EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EDX));
1093 
1094 	if (dstk) {
1095 		/* mov dword ptr [ebp+off],eax */
1096 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
1097 		      STACK_VAR(dst_lo));
1098 		/* mov dword ptr [ebp+off],ecx */
1099 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_ECX),
1100 		      STACK_VAR(dst_hi));
1101 	} else {
1102 		/* mov dst_lo,eax */
1103 		EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EAX));
1104 		/* mov dst_hi,ecx */
1105 		EMIT2(0x89, add_2reg(0xC0, dst_hi, IA32_ECX));
1106 	}
1107 
1108 	*pprog = prog;
1109 }
1110 
1111 static inline void emit_ia32_mul_i64(const u8 dst[], const u32 val,
1112 				     bool dstk, u8 **pprog)
1113 {
1114 	u8 *prog = *pprog;
1115 	int cnt = 0;
1116 	u32 hi;
1117 
1118 	hi = val & (1<<31) ? (u32)~0 : 0;
1119 	/* movl eax,imm32 */
1120 	EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EAX), val);
1121 	if (dstk)
1122 		/* mul dword ptr [ebp+off] */
1123 		EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(dst_hi));
1124 	else
1125 		/* mul dst_hi */
1126 		EMIT2(0xF7, add_1reg(0xE0, dst_hi));
1127 
1128 	/* mov ecx,eax */
1129 	EMIT2(0x89, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1130 
1131 	/* movl eax,imm32 */
1132 	EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EAX), hi);
1133 	if (dstk)
1134 		/* mul dword ptr [ebp+off] */
1135 		EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(dst_lo));
1136 	else
1137 		/* mul dst_lo */
1138 		EMIT2(0xF7, add_1reg(0xE0, dst_lo));
1139 	/* add ecx,eax */
1140 	EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1141 
1142 	/* movl eax,imm32 */
1143 	EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EAX), val);
1144 	if (dstk)
1145 		/* mul dword ptr [ebp+off] */
1146 		EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(dst_lo));
1147 	else
1148 		/* mul dst_lo */
1149 		EMIT2(0xF7, add_1reg(0xE0, dst_lo));
1150 
1151 	/* add ecx,edx */
1152 	EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EDX));
1153 
1154 	if (dstk) {
1155 		/* mov dword ptr [ebp+off],eax */
1156 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
1157 		      STACK_VAR(dst_lo));
1158 		/* mov dword ptr [ebp+off],ecx */
1159 		EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_ECX),
1160 		      STACK_VAR(dst_hi));
1161 	} else {
1162 		/* mov dword ptr [ebp+off],eax */
1163 		EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EAX));
1164 		/* mov dword ptr [ebp+off],ecx */
1165 		EMIT2(0x89, add_2reg(0xC0, dst_hi, IA32_ECX));
1166 	}
1167 
1168 	*pprog = prog;
1169 }
1170 
1171 static int bpf_size_to_x86_bytes(int bpf_size)
1172 {
1173 	if (bpf_size == BPF_W)
1174 		return 4;
1175 	else if (bpf_size == BPF_H)
1176 		return 2;
1177 	else if (bpf_size == BPF_B)
1178 		return 1;
1179 	else if (bpf_size == BPF_DW)
1180 		return 4; /* imm32 */
1181 	else
1182 		return 0;
1183 }
1184 
1185 struct jit_context {
1186 	int cleanup_addr; /* Epilogue code offset */
1187 };
1188 
1189 /* Maximum number of bytes emitted while JITing one eBPF insn */
1190 #define BPF_MAX_INSN_SIZE	128
1191 #define BPF_INSN_SAFETY		64
1192 
1193 #define PROLOGUE_SIZE 35
1194 
1195 /*
1196  * Emit prologue code for BPF program and check it's size.
1197  * bpf_tail_call helper will skip it while jumping into another program.
1198  */
1199 static void emit_prologue(u8 **pprog, u32 stack_depth)
1200 {
1201 	u8 *prog = *pprog;
1202 	int cnt = 0;
1203 	const u8 *r1 = bpf2ia32[BPF_REG_1];
1204 	const u8 fplo = bpf2ia32[BPF_REG_FP][0];
1205 	const u8 fphi = bpf2ia32[BPF_REG_FP][1];
1206 	const u8 *tcc = bpf2ia32[TCALL_CNT];
1207 
1208 	/* push ebp */
1209 	EMIT1(0x55);
1210 	/* mov ebp,esp */
1211 	EMIT2(0x89, 0xE5);
1212 	/* push edi */
1213 	EMIT1(0x57);
1214 	/* push esi */
1215 	EMIT1(0x56);
1216 	/* push ebx */
1217 	EMIT1(0x53);
1218 
1219 	/* sub esp,STACK_SIZE */
1220 	EMIT2_off32(0x81, 0xEC, STACK_SIZE);
1221 	/* sub ebp,SCRATCH_SIZE+12*/
1222 	EMIT3(0x83, add_1reg(0xE8, IA32_EBP), SCRATCH_SIZE + 12);
1223 	/* xor ebx,ebx */
1224 	EMIT2(0x31, add_2reg(0xC0, IA32_EBX, IA32_EBX));
1225 
1226 	/* Set up BPF prog stack base register */
1227 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBP), STACK_VAR(fplo));
1228 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(fphi));
1229 
1230 	/* Move BPF_CTX (EAX) to BPF_REG_R1 */
1231 	/* mov dword ptr [ebp+off],eax */
1232 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r1[0]));
1233 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(r1[1]));
1234 
1235 	/* Initialize Tail Count */
1236 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[0]));
1237 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[1]));
1238 
1239 	BUILD_BUG_ON(cnt != PROLOGUE_SIZE);
1240 	*pprog = prog;
1241 }
1242 
1243 /* Emit epilogue code for BPF program */
1244 static void emit_epilogue(u8 **pprog, u32 stack_depth)
1245 {
1246 	u8 *prog = *pprog;
1247 	const u8 *r0 = bpf2ia32[BPF_REG_0];
1248 	int cnt = 0;
1249 
1250 	/* mov eax,dword ptr [ebp+off]*/
1251 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r0[0]));
1252 	/* mov edx,dword ptr [ebp+off]*/
1253 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX), STACK_VAR(r0[1]));
1254 
1255 	/* add ebp,SCRATCH_SIZE+12*/
1256 	EMIT3(0x83, add_1reg(0xC0, IA32_EBP), SCRATCH_SIZE + 12);
1257 
1258 	/* mov ebx,dword ptr [ebp-12]*/
1259 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EBX), -12);
1260 	/* mov esi,dword ptr [ebp-8]*/
1261 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ESI), -8);
1262 	/* mov edi,dword ptr [ebp-4]*/
1263 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDI), -4);
1264 
1265 	EMIT1(0xC9); /* leave */
1266 	EMIT1(0xC3); /* ret */
1267 	*pprog = prog;
1268 }
1269 
1270 /*
1271  * Generate the following code:
1272  * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ...
1273  *   if (index >= array->map.max_entries)
1274  *     goto out;
1275  *   if (++tail_call_cnt > MAX_TAIL_CALL_CNT)
1276  *     goto out;
1277  *   prog = array->ptrs[index];
1278  *   if (prog == NULL)
1279  *     goto out;
1280  *   goto *(prog->bpf_func + prologue_size);
1281  * out:
1282  */
1283 static void emit_bpf_tail_call(u8 **pprog)
1284 {
1285 	u8 *prog = *pprog;
1286 	int cnt = 0;
1287 	const u8 *r1 = bpf2ia32[BPF_REG_1];
1288 	const u8 *r2 = bpf2ia32[BPF_REG_2];
1289 	const u8 *r3 = bpf2ia32[BPF_REG_3];
1290 	const u8 *tcc = bpf2ia32[TCALL_CNT];
1291 	u32 lo, hi;
1292 	static int jmp_label1 = -1;
1293 
1294 	/*
1295 	 * if (index >= array->map.max_entries)
1296 	 *     goto out;
1297 	 */
1298 	/* mov eax,dword ptr [ebp+off] */
1299 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r2[0]));
1300 	/* mov edx,dword ptr [ebp+off] */
1301 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX), STACK_VAR(r3[0]));
1302 
1303 	/* cmp dword ptr [eax+off],edx */
1304 	EMIT3(0x39, add_2reg(0x40, IA32_EAX, IA32_EDX),
1305 	      offsetof(struct bpf_array, map.max_entries));
1306 	/* jbe out */
1307 	EMIT2(IA32_JBE, jmp_label(jmp_label1, 2));
1308 
1309 	/*
1310 	 * if (tail_call_cnt > MAX_TAIL_CALL_CNT)
1311 	 *     goto out;
1312 	 */
1313 	lo = (u32)MAX_TAIL_CALL_CNT;
1314 	hi = (u32)((u64)MAX_TAIL_CALL_CNT >> 32);
1315 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(tcc[0]));
1316 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[1]));
1317 
1318 	/* cmp edx,hi */
1319 	EMIT3(0x83, add_1reg(0xF8, IA32_EBX), hi);
1320 	EMIT2(IA32_JNE, 3);
1321 	/* cmp ecx,lo */
1322 	EMIT3(0x83, add_1reg(0xF8, IA32_ECX), lo);
1323 
1324 	/* ja out */
1325 	EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));
1326 
1327 	/* add eax,0x1 */
1328 	EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 0x01);
1329 	/* adc ebx,0x0 */
1330 	EMIT3(0x83, add_1reg(0xD0, IA32_EBX), 0x00);
1331 
1332 	/* mov dword ptr [ebp+off],eax */
1333 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(tcc[0]));
1334 	/* mov dword ptr [ebp+off],edx */
1335 	EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[1]));
1336 
1337 	/* prog = array->ptrs[index]; */
1338 	/* mov edx, [eax + edx * 4 + offsetof(...)] */
1339 	EMIT3_off32(0x8B, 0x94, 0x90, offsetof(struct bpf_array, ptrs));
1340 
1341 	/*
1342 	 * if (prog == NULL)
1343 	 *     goto out;
1344 	 */
1345 	/* test edx,edx */
1346 	EMIT2(0x85, add_2reg(0xC0, IA32_EDX, IA32_EDX));
1347 	/* je out */
1348 	EMIT2(IA32_JE, jmp_label(jmp_label1, 2));
1349 
1350 	/* goto *(prog->bpf_func + prologue_size); */
1351 	/* mov edx, dword ptr [edx + 32] */
1352 	EMIT3(0x8B, add_2reg(0x40, IA32_EDX, IA32_EDX),
1353 	      offsetof(struct bpf_prog, bpf_func));
1354 	/* add edx,prologue_size */
1355 	EMIT3(0x83, add_1reg(0xC0, IA32_EDX), PROLOGUE_SIZE);
1356 
1357 	/* mov eax,dword ptr [ebp+off] */
1358 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r1[0]));
1359 
1360 	/*
1361 	 * Now we're ready to jump into next BPF program:
1362 	 * eax == ctx (1st arg)
1363 	 * edx == prog->bpf_func + prologue_size
1364 	 */
1365 	RETPOLINE_EDX_BPF_JIT();
1366 
1367 	if (jmp_label1 == -1)
1368 		jmp_label1 = cnt;
1369 
1370 	/* out: */
1371 	*pprog = prog;
1372 }
1373 
1374 /* Push the scratch stack register on top of the stack. */
1375 static inline void emit_push_r64(const u8 src[], u8 **pprog)
1376 {
1377 	u8 *prog = *pprog;
1378 	int cnt = 0;
1379 
1380 	/* mov ecx,dword ptr [ebp+off] */
1381 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src_hi));
1382 	/* push ecx */
1383 	EMIT1(0x51);
1384 
1385 	/* mov ecx,dword ptr [ebp+off] */
1386 	EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src_lo));
1387 	/* push ecx */
1388 	EMIT1(0x51);
1389 
1390 	*pprog = prog;
1391 }
1392 
1393 static u8 get_cond_jmp_opcode(const u8 op, bool is_cmp_lo)
1394 {
1395 	u8 jmp_cond;
1396 
1397 	/* Convert BPF opcode to x86 */
1398 	switch (op) {
1399 	case BPF_JEQ:
1400 		jmp_cond = IA32_JE;
1401 		break;
1402 	case BPF_JSET:
1403 	case BPF_JNE:
1404 		jmp_cond = IA32_JNE;
1405 		break;
1406 	case BPF_JGT:
1407 		/* GT is unsigned '>', JA in x86 */
1408 		jmp_cond = IA32_JA;
1409 		break;
1410 	case BPF_JLT:
1411 		/* LT is unsigned '<', JB in x86 */
1412 		jmp_cond = IA32_JB;
1413 		break;
1414 	case BPF_JGE:
1415 		/* GE is unsigned '>=', JAE in x86 */
1416 		jmp_cond = IA32_JAE;
1417 		break;
1418 	case BPF_JLE:
1419 		/* LE is unsigned '<=', JBE in x86 */
1420 		jmp_cond = IA32_JBE;
1421 		break;
1422 	case BPF_JSGT:
1423 		if (!is_cmp_lo)
1424 			/* Signed '>', GT in x86 */
1425 			jmp_cond = IA32_JG;
1426 		else
1427 			/* GT is unsigned '>', JA in x86 */
1428 			jmp_cond = IA32_JA;
1429 		break;
1430 	case BPF_JSLT:
1431 		if (!is_cmp_lo)
1432 			/* Signed '<', LT in x86 */
1433 			jmp_cond = IA32_JL;
1434 		else
1435 			/* LT is unsigned '<', JB in x86 */
1436 			jmp_cond = IA32_JB;
1437 		break;
1438 	case BPF_JSGE:
1439 		if (!is_cmp_lo)
1440 			/* Signed '>=', GE in x86 */
1441 			jmp_cond = IA32_JGE;
1442 		else
1443 			/* GE is unsigned '>=', JAE in x86 */
1444 			jmp_cond = IA32_JAE;
1445 		break;
1446 	case BPF_JSLE:
1447 		if (!is_cmp_lo)
1448 			/* Signed '<=', LE in x86 */
1449 			jmp_cond = IA32_JLE;
1450 		else
1451 			/* LE is unsigned '<=', JBE in x86 */
1452 			jmp_cond = IA32_JBE;
1453 		break;
1454 	default: /* to silence GCC warning */
1455 		jmp_cond = COND_JMP_OPCODE_INVALID;
1456 		break;
1457 	}
1458 
1459 	return jmp_cond;
1460 }
1461 
1462 static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
1463 		  int oldproglen, struct jit_context *ctx)
1464 {
1465 	struct bpf_insn *insn = bpf_prog->insnsi;
1466 	int insn_cnt = bpf_prog->len;
1467 	bool seen_exit = false;
1468 	u8 temp[BPF_MAX_INSN_SIZE + BPF_INSN_SAFETY];
1469 	int i, cnt = 0;
1470 	int proglen = 0;
1471 	u8 *prog = temp;
1472 
1473 	emit_prologue(&prog, bpf_prog->aux->stack_depth);
1474 
1475 	for (i = 0; i < insn_cnt; i++, insn++) {
1476 		const s32 imm32 = insn->imm;
1477 		const bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
1478 		const bool dstk = insn->dst_reg == BPF_REG_AX ? false : true;
1479 		const bool sstk = insn->src_reg == BPF_REG_AX ? false : true;
1480 		const u8 code = insn->code;
1481 		const u8 *dst = bpf2ia32[insn->dst_reg];
1482 		const u8 *src = bpf2ia32[insn->src_reg];
1483 		const u8 *r0 = bpf2ia32[BPF_REG_0];
1484 		s64 jmp_offset;
1485 		u8 jmp_cond;
1486 		int ilen;
1487 		u8 *func;
1488 
1489 		switch (code) {
1490 		/* ALU operations */
1491 		/* dst = src */
1492 		case BPF_ALU | BPF_MOV | BPF_K:
1493 		case BPF_ALU | BPF_MOV | BPF_X:
1494 		case BPF_ALU64 | BPF_MOV | BPF_K:
1495 		case BPF_ALU64 | BPF_MOV | BPF_X:
1496 			switch (BPF_SRC(code)) {
1497 			case BPF_X:
1498 				if (imm32 == 1) {
1499 					/* Special mov32 for zext. */
1500 					emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1501 					break;
1502 				}
1503 				emit_ia32_mov_r64(is64, dst, src, dstk, sstk,
1504 						  &prog, bpf_prog->aux);
1505 				break;
1506 			case BPF_K:
1507 				/* Sign-extend immediate value to dst reg */
1508 				emit_ia32_mov_i64(is64, dst, imm32,
1509 						  dstk, &prog);
1510 				break;
1511 			}
1512 			break;
1513 		/* dst = dst + src/imm */
1514 		/* dst = dst - src/imm */
1515 		/* dst = dst | src/imm */
1516 		/* dst = dst & src/imm */
1517 		/* dst = dst ^ src/imm */
1518 		/* dst = dst * src/imm */
1519 		/* dst = dst << src */
1520 		/* dst = dst >> src */
1521 		case BPF_ALU | BPF_ADD | BPF_K:
1522 		case BPF_ALU | BPF_ADD | BPF_X:
1523 		case BPF_ALU | BPF_SUB | BPF_K:
1524 		case BPF_ALU | BPF_SUB | BPF_X:
1525 		case BPF_ALU | BPF_OR | BPF_K:
1526 		case BPF_ALU | BPF_OR | BPF_X:
1527 		case BPF_ALU | BPF_AND | BPF_K:
1528 		case BPF_ALU | BPF_AND | BPF_X:
1529 		case BPF_ALU | BPF_XOR | BPF_K:
1530 		case BPF_ALU | BPF_XOR | BPF_X:
1531 		case BPF_ALU64 | BPF_ADD | BPF_K:
1532 		case BPF_ALU64 | BPF_ADD | BPF_X:
1533 		case BPF_ALU64 | BPF_SUB | BPF_K:
1534 		case BPF_ALU64 | BPF_SUB | BPF_X:
1535 		case BPF_ALU64 | BPF_OR | BPF_K:
1536 		case BPF_ALU64 | BPF_OR | BPF_X:
1537 		case BPF_ALU64 | BPF_AND | BPF_K:
1538 		case BPF_ALU64 | BPF_AND | BPF_X:
1539 		case BPF_ALU64 | BPF_XOR | BPF_K:
1540 		case BPF_ALU64 | BPF_XOR | BPF_X:
1541 			switch (BPF_SRC(code)) {
1542 			case BPF_X:
1543 				emit_ia32_alu_r64(is64, BPF_OP(code), dst,
1544 						  src, dstk, sstk, &prog,
1545 						  bpf_prog->aux);
1546 				break;
1547 			case BPF_K:
1548 				emit_ia32_alu_i64(is64, BPF_OP(code), dst,
1549 						  imm32, dstk, &prog,
1550 						  bpf_prog->aux);
1551 				break;
1552 			}
1553 			break;
1554 		case BPF_ALU | BPF_MUL | BPF_K:
1555 		case BPF_ALU | BPF_MUL | BPF_X:
1556 			switch (BPF_SRC(code)) {
1557 			case BPF_X:
1558 				emit_ia32_mul_r(dst_lo, src_lo, dstk,
1559 						sstk, &prog);
1560 				break;
1561 			case BPF_K:
1562 				/* mov ecx,imm32*/
1563 				EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1564 					    imm32);
1565 				emit_ia32_mul_r(dst_lo, IA32_ECX, dstk,
1566 						false, &prog);
1567 				break;
1568 			}
1569 			if (!bpf_prog->aux->verifier_zext)
1570 				emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1571 			break;
1572 		case BPF_ALU | BPF_LSH | BPF_X:
1573 		case BPF_ALU | BPF_RSH | BPF_X:
1574 		case BPF_ALU | BPF_ARSH | BPF_K:
1575 		case BPF_ALU | BPF_ARSH | BPF_X:
1576 			switch (BPF_SRC(code)) {
1577 			case BPF_X:
1578 				emit_ia32_shift_r(BPF_OP(code), dst_lo, src_lo,
1579 						  dstk, sstk, &prog);
1580 				break;
1581 			case BPF_K:
1582 				/* mov ecx,imm32*/
1583 				EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1584 					    imm32);
1585 				emit_ia32_shift_r(BPF_OP(code), dst_lo,
1586 						  IA32_ECX, dstk, false,
1587 						  &prog);
1588 				break;
1589 			}
1590 			if (!bpf_prog->aux->verifier_zext)
1591 				emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1592 			break;
1593 		/* dst = dst / src(imm) */
1594 		/* dst = dst % src(imm) */
1595 		case BPF_ALU | BPF_DIV | BPF_K:
1596 		case BPF_ALU | BPF_DIV | BPF_X:
1597 		case BPF_ALU | BPF_MOD | BPF_K:
1598 		case BPF_ALU | BPF_MOD | BPF_X:
1599 			switch (BPF_SRC(code)) {
1600 			case BPF_X:
1601 				emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
1602 						    src_lo, dstk, sstk, &prog);
1603 				break;
1604 			case BPF_K:
1605 				/* mov ecx,imm32*/
1606 				EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1607 					    imm32);
1608 				emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
1609 						    IA32_ECX, dstk, false,
1610 						    &prog);
1611 				break;
1612 			}
1613 			if (!bpf_prog->aux->verifier_zext)
1614 				emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1615 			break;
1616 		case BPF_ALU64 | BPF_DIV | BPF_K:
1617 		case BPF_ALU64 | BPF_DIV | BPF_X:
1618 		case BPF_ALU64 | BPF_MOD | BPF_K:
1619 		case BPF_ALU64 | BPF_MOD | BPF_X:
1620 			goto notyet;
1621 		/* dst = dst >> imm */
1622 		/* dst = dst << imm */
1623 		case BPF_ALU | BPF_RSH | BPF_K:
1624 		case BPF_ALU | BPF_LSH | BPF_K:
1625 			if (unlikely(imm32 > 31))
1626 				return -EINVAL;
1627 			/* mov ecx,imm32*/
1628 			EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
1629 			emit_ia32_shift_r(BPF_OP(code), dst_lo, IA32_ECX, dstk,
1630 					  false, &prog);
1631 			if (!bpf_prog->aux->verifier_zext)
1632 				emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1633 			break;
1634 		/* dst = dst << imm */
1635 		case BPF_ALU64 | BPF_LSH | BPF_K:
1636 			if (unlikely(imm32 > 63))
1637 				return -EINVAL;
1638 			emit_ia32_lsh_i64(dst, imm32, dstk, &prog);
1639 			break;
1640 		/* dst = dst >> imm */
1641 		case BPF_ALU64 | BPF_RSH | BPF_K:
1642 			if (unlikely(imm32 > 63))
1643 				return -EINVAL;
1644 			emit_ia32_rsh_i64(dst, imm32, dstk, &prog);
1645 			break;
1646 		/* dst = dst << src */
1647 		case BPF_ALU64 | BPF_LSH | BPF_X:
1648 			emit_ia32_lsh_r64(dst, src, dstk, sstk, &prog);
1649 			break;
1650 		/* dst = dst >> src */
1651 		case BPF_ALU64 | BPF_RSH | BPF_X:
1652 			emit_ia32_rsh_r64(dst, src, dstk, sstk, &prog);
1653 			break;
1654 		/* dst = dst >> src (signed) */
1655 		case BPF_ALU64 | BPF_ARSH | BPF_X:
1656 			emit_ia32_arsh_r64(dst, src, dstk, sstk, &prog);
1657 			break;
1658 		/* dst = dst >> imm (signed) */
1659 		case BPF_ALU64 | BPF_ARSH | BPF_K:
1660 			if (unlikely(imm32 > 63))
1661 				return -EINVAL;
1662 			emit_ia32_arsh_i64(dst, imm32, dstk, &prog);
1663 			break;
1664 		/* dst = ~dst */
1665 		case BPF_ALU | BPF_NEG:
1666 			emit_ia32_alu_i(is64, false, BPF_OP(code),
1667 					dst_lo, 0, dstk, &prog);
1668 			if (!bpf_prog->aux->verifier_zext)
1669 				emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1670 			break;
1671 		/* dst = ~dst (64 bit) */
1672 		case BPF_ALU64 | BPF_NEG:
1673 			emit_ia32_neg64(dst, dstk, &prog);
1674 			break;
1675 		/* dst = dst * src/imm */
1676 		case BPF_ALU64 | BPF_MUL | BPF_X:
1677 		case BPF_ALU64 | BPF_MUL | BPF_K:
1678 			switch (BPF_SRC(code)) {
1679 			case BPF_X:
1680 				emit_ia32_mul_r64(dst, src, dstk, sstk, &prog);
1681 				break;
1682 			case BPF_K:
1683 				emit_ia32_mul_i64(dst, imm32, dstk, &prog);
1684 				break;
1685 			}
1686 			break;
1687 		/* dst = htole(dst) */
1688 		case BPF_ALU | BPF_END | BPF_FROM_LE:
1689 			emit_ia32_to_le_r64(dst, imm32, dstk, &prog,
1690 					    bpf_prog->aux);
1691 			break;
1692 		/* dst = htobe(dst) */
1693 		case BPF_ALU | BPF_END | BPF_FROM_BE:
1694 			emit_ia32_to_be_r64(dst, imm32, dstk, &prog,
1695 					    bpf_prog->aux);
1696 			break;
1697 		/* dst = imm64 */
1698 		case BPF_LD | BPF_IMM | BPF_DW: {
1699 			s32 hi, lo = imm32;
1700 
1701 			hi = insn[1].imm;
1702 			emit_ia32_mov_i(dst_lo, lo, dstk, &prog);
1703 			emit_ia32_mov_i(dst_hi, hi, dstk, &prog);
1704 			insn++;
1705 			i++;
1706 			break;
1707 		}
1708 		/* ST: *(u8*)(dst_reg + off) = imm */
1709 		case BPF_ST | BPF_MEM | BPF_H:
1710 		case BPF_ST | BPF_MEM | BPF_B:
1711 		case BPF_ST | BPF_MEM | BPF_W:
1712 		case BPF_ST | BPF_MEM | BPF_DW:
1713 			if (dstk)
1714 				/* mov eax,dword ptr [ebp+off] */
1715 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1716 				      STACK_VAR(dst_lo));
1717 			else
1718 				/* mov eax,dst_lo */
1719 				EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1720 
1721 			switch (BPF_SIZE(code)) {
1722 			case BPF_B:
1723 				EMIT(0xC6, 1); break;
1724 			case BPF_H:
1725 				EMIT2(0x66, 0xC7); break;
1726 			case BPF_W:
1727 			case BPF_DW:
1728 				EMIT(0xC7, 1); break;
1729 			}
1730 
1731 			if (is_imm8(insn->off))
1732 				EMIT2(add_1reg(0x40, IA32_EAX), insn->off);
1733 			else
1734 				EMIT1_off32(add_1reg(0x80, IA32_EAX),
1735 					    insn->off);
1736 			EMIT(imm32, bpf_size_to_x86_bytes(BPF_SIZE(code)));
1737 
1738 			if (BPF_SIZE(code) == BPF_DW) {
1739 				u32 hi;
1740 
1741 				hi = imm32 & (1<<31) ? (u32)~0 : 0;
1742 				EMIT2_off32(0xC7, add_1reg(0x80, IA32_EAX),
1743 					    insn->off + 4);
1744 				EMIT(hi, 4);
1745 			}
1746 			break;
1747 
1748 		/* STX: *(u8*)(dst_reg + off) = src_reg */
1749 		case BPF_STX | BPF_MEM | BPF_B:
1750 		case BPF_STX | BPF_MEM | BPF_H:
1751 		case BPF_STX | BPF_MEM | BPF_W:
1752 		case BPF_STX | BPF_MEM | BPF_DW:
1753 			if (dstk)
1754 				/* mov eax,dword ptr [ebp+off] */
1755 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1756 				      STACK_VAR(dst_lo));
1757 			else
1758 				/* mov eax,dst_lo */
1759 				EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1760 
1761 			if (sstk)
1762 				/* mov edx,dword ptr [ebp+off] */
1763 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1764 				      STACK_VAR(src_lo));
1765 			else
1766 				/* mov edx,src_lo */
1767 				EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_EDX));
1768 
1769 			switch (BPF_SIZE(code)) {
1770 			case BPF_B:
1771 				EMIT(0x88, 1); break;
1772 			case BPF_H:
1773 				EMIT2(0x66, 0x89); break;
1774 			case BPF_W:
1775 			case BPF_DW:
1776 				EMIT(0x89, 1); break;
1777 			}
1778 
1779 			if (is_imm8(insn->off))
1780 				EMIT2(add_2reg(0x40, IA32_EAX, IA32_EDX),
1781 				      insn->off);
1782 			else
1783 				EMIT1_off32(add_2reg(0x80, IA32_EAX, IA32_EDX),
1784 					    insn->off);
1785 
1786 			if (BPF_SIZE(code) == BPF_DW) {
1787 				if (sstk)
1788 					/* mov edi,dword ptr [ebp+off] */
1789 					EMIT3(0x8B, add_2reg(0x40, IA32_EBP,
1790 							     IA32_EDX),
1791 					      STACK_VAR(src_hi));
1792 				else
1793 					/* mov edi,src_hi */
1794 					EMIT2(0x8B, add_2reg(0xC0, src_hi,
1795 							     IA32_EDX));
1796 				EMIT1(0x89);
1797 				if (is_imm8(insn->off + 4)) {
1798 					EMIT2(add_2reg(0x40, IA32_EAX,
1799 						       IA32_EDX),
1800 					      insn->off + 4);
1801 				} else {
1802 					EMIT1(add_2reg(0x80, IA32_EAX,
1803 						       IA32_EDX));
1804 					EMIT(insn->off + 4, 4);
1805 				}
1806 			}
1807 			break;
1808 
1809 		/* LDX: dst_reg = *(u8*)(src_reg + off) */
1810 		case BPF_LDX | BPF_MEM | BPF_B:
1811 		case BPF_LDX | BPF_MEM | BPF_H:
1812 		case BPF_LDX | BPF_MEM | BPF_W:
1813 		case BPF_LDX | BPF_MEM | BPF_DW:
1814 			if (sstk)
1815 				/* mov eax,dword ptr [ebp+off] */
1816 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1817 				      STACK_VAR(src_lo));
1818 			else
1819 				/* mov eax,dword ptr [ebp+off] */
1820 				EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_EAX));
1821 
1822 			switch (BPF_SIZE(code)) {
1823 			case BPF_B:
1824 				EMIT2(0x0F, 0xB6); break;
1825 			case BPF_H:
1826 				EMIT2(0x0F, 0xB7); break;
1827 			case BPF_W:
1828 			case BPF_DW:
1829 				EMIT(0x8B, 1); break;
1830 			}
1831 
1832 			if (is_imm8(insn->off))
1833 				EMIT2(add_2reg(0x40, IA32_EAX, IA32_EDX),
1834 				      insn->off);
1835 			else
1836 				EMIT1_off32(add_2reg(0x80, IA32_EAX, IA32_EDX),
1837 					    insn->off);
1838 
1839 			if (dstk)
1840 				/* mov dword ptr [ebp+off],edx */
1841 				EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
1842 				      STACK_VAR(dst_lo));
1843 			else
1844 				/* mov dst_lo,edx */
1845 				EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EDX));
1846 			switch (BPF_SIZE(code)) {
1847 			case BPF_B:
1848 			case BPF_H:
1849 			case BPF_W:
1850 				if (!bpf_prog->aux->verifier_zext)
1851 					break;
1852 				if (dstk) {
1853 					EMIT3(0xC7, add_1reg(0x40, IA32_EBP),
1854 					      STACK_VAR(dst_hi));
1855 					EMIT(0x0, 4);
1856 				} else {
1857 					EMIT3(0xC7, add_1reg(0xC0, dst_hi), 0);
1858 				}
1859 				break;
1860 			case BPF_DW:
1861 				EMIT2_off32(0x8B,
1862 					    add_2reg(0x80, IA32_EAX, IA32_EDX),
1863 					    insn->off + 4);
1864 				if (dstk)
1865 					EMIT3(0x89,
1866 					      add_2reg(0x40, IA32_EBP,
1867 						       IA32_EDX),
1868 					      STACK_VAR(dst_hi));
1869 				else
1870 					EMIT2(0x89,
1871 					      add_2reg(0xC0, dst_hi, IA32_EDX));
1872 				break;
1873 			default:
1874 				break;
1875 			}
1876 			break;
1877 		/* call */
1878 		case BPF_JMP | BPF_CALL:
1879 		{
1880 			const u8 *r1 = bpf2ia32[BPF_REG_1];
1881 			const u8 *r2 = bpf2ia32[BPF_REG_2];
1882 			const u8 *r3 = bpf2ia32[BPF_REG_3];
1883 			const u8 *r4 = bpf2ia32[BPF_REG_4];
1884 			const u8 *r5 = bpf2ia32[BPF_REG_5];
1885 
1886 			if (insn->src_reg == BPF_PSEUDO_CALL)
1887 				goto notyet;
1888 
1889 			func = (u8 *) __bpf_call_base + imm32;
1890 			jmp_offset = func - (image + addrs[i]);
1891 
1892 			if (!imm32 || !is_simm32(jmp_offset)) {
1893 				pr_err("unsupported BPF func %d addr %p image %p\n",
1894 				       imm32, func, image);
1895 				return -EINVAL;
1896 			}
1897 
1898 			/* mov eax,dword ptr [ebp+off] */
1899 			EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1900 			      STACK_VAR(r1[0]));
1901 			/* mov edx,dword ptr [ebp+off] */
1902 			EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1903 			      STACK_VAR(r1[1]));
1904 
1905 			emit_push_r64(r5, &prog);
1906 			emit_push_r64(r4, &prog);
1907 			emit_push_r64(r3, &prog);
1908 			emit_push_r64(r2, &prog);
1909 
1910 			EMIT1_off32(0xE8, jmp_offset + 9);
1911 
1912 			/* mov dword ptr [ebp+off],eax */
1913 			EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
1914 			      STACK_VAR(r0[0]));
1915 			/* mov dword ptr [ebp+off],edx */
1916 			EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
1917 			      STACK_VAR(r0[1]));
1918 
1919 			/* add esp,32 */
1920 			EMIT3(0x83, add_1reg(0xC0, IA32_ESP), 32);
1921 			break;
1922 		}
1923 		case BPF_JMP | BPF_TAIL_CALL:
1924 			emit_bpf_tail_call(&prog);
1925 			break;
1926 
1927 		/* cond jump */
1928 		case BPF_JMP | BPF_JEQ | BPF_X:
1929 		case BPF_JMP | BPF_JNE | BPF_X:
1930 		case BPF_JMP | BPF_JGT | BPF_X:
1931 		case BPF_JMP | BPF_JLT | BPF_X:
1932 		case BPF_JMP | BPF_JGE | BPF_X:
1933 		case BPF_JMP | BPF_JLE | BPF_X:
1934 		case BPF_JMP32 | BPF_JEQ | BPF_X:
1935 		case BPF_JMP32 | BPF_JNE | BPF_X:
1936 		case BPF_JMP32 | BPF_JGT | BPF_X:
1937 		case BPF_JMP32 | BPF_JLT | BPF_X:
1938 		case BPF_JMP32 | BPF_JGE | BPF_X:
1939 		case BPF_JMP32 | BPF_JLE | BPF_X:
1940 		case BPF_JMP32 | BPF_JSGT | BPF_X:
1941 		case BPF_JMP32 | BPF_JSLE | BPF_X:
1942 		case BPF_JMP32 | BPF_JSLT | BPF_X:
1943 		case BPF_JMP32 | BPF_JSGE | BPF_X: {
1944 			bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
1945 			u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
1946 			u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
1947 			u8 sreg_lo = sstk ? IA32_ECX : src_lo;
1948 			u8 sreg_hi = sstk ? IA32_EBX : src_hi;
1949 
1950 			if (dstk) {
1951 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1952 				      STACK_VAR(dst_lo));
1953 				if (is_jmp64)
1954 					EMIT3(0x8B,
1955 					      add_2reg(0x40, IA32_EBP,
1956 						       IA32_EDX),
1957 					      STACK_VAR(dst_hi));
1958 			}
1959 
1960 			if (sstk) {
1961 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
1962 				      STACK_VAR(src_lo));
1963 				if (is_jmp64)
1964 					EMIT3(0x8B,
1965 					      add_2reg(0x40, IA32_EBP,
1966 						       IA32_EBX),
1967 					      STACK_VAR(src_hi));
1968 			}
1969 
1970 			if (is_jmp64) {
1971 				/* cmp dreg_hi,sreg_hi */
1972 				EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
1973 				EMIT2(IA32_JNE, 2);
1974 			}
1975 			/* cmp dreg_lo,sreg_lo */
1976 			EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
1977 			goto emit_cond_jmp;
1978 		}
1979 		case BPF_JMP | BPF_JSGT | BPF_X:
1980 		case BPF_JMP | BPF_JSLE | BPF_X:
1981 		case BPF_JMP | BPF_JSLT | BPF_X:
1982 		case BPF_JMP | BPF_JSGE | BPF_X: {
1983 			u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
1984 			u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
1985 			u8 sreg_lo = sstk ? IA32_ECX : src_lo;
1986 			u8 sreg_hi = sstk ? IA32_EBX : src_hi;
1987 
1988 			if (dstk) {
1989 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1990 				      STACK_VAR(dst_lo));
1991 				EMIT3(0x8B,
1992 				      add_2reg(0x40, IA32_EBP,
1993 					       IA32_EDX),
1994 				      STACK_VAR(dst_hi));
1995 			}
1996 
1997 			if (sstk) {
1998 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
1999 				      STACK_VAR(src_lo));
2000 				EMIT3(0x8B,
2001 				      add_2reg(0x40, IA32_EBP,
2002 					       IA32_EBX),
2003 				      STACK_VAR(src_hi));
2004 			}
2005 
2006 			/* cmp dreg_hi,sreg_hi */
2007 			EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2008 			EMIT2(IA32_JNE, 10);
2009 			/* cmp dreg_lo,sreg_lo */
2010 			EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2011 			goto emit_cond_jmp_signed;
2012 		}
2013 		case BPF_JMP | BPF_JSET | BPF_X:
2014 		case BPF_JMP32 | BPF_JSET | BPF_X: {
2015 			bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2016 			u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2017 			u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2018 			u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2019 			u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2020 
2021 			if (dstk) {
2022 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2023 				      STACK_VAR(dst_lo));
2024 				if (is_jmp64)
2025 					EMIT3(0x8B,
2026 					      add_2reg(0x40, IA32_EBP,
2027 						       IA32_EDX),
2028 					      STACK_VAR(dst_hi));
2029 			}
2030 
2031 			if (sstk) {
2032 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2033 				      STACK_VAR(src_lo));
2034 				if (is_jmp64)
2035 					EMIT3(0x8B,
2036 					      add_2reg(0x40, IA32_EBP,
2037 						       IA32_EBX),
2038 					      STACK_VAR(src_hi));
2039 			}
2040 			/* and dreg_lo,sreg_lo */
2041 			EMIT2(0x23, add_2reg(0xC0, sreg_lo, dreg_lo));
2042 			/* and dreg_hi,sreg_hi */
2043 			EMIT2(0x23, add_2reg(0xC0, sreg_hi, dreg_hi));
2044 			/* or dreg_lo,dreg_hi */
2045 			EMIT2(0x09, add_2reg(0xC0, dreg_lo, dreg_hi));
2046 			goto emit_cond_jmp;
2047 		}
2048 		case BPF_JMP | BPF_JSET | BPF_K:
2049 		case BPF_JMP32 | BPF_JSET | BPF_K: {
2050 			bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2051 			u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2052 			u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2053 			u8 sreg_lo = IA32_ECX;
2054 			u8 sreg_hi = IA32_EBX;
2055 			u32 hi;
2056 
2057 			if (dstk) {
2058 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2059 				      STACK_VAR(dst_lo));
2060 				if (is_jmp64)
2061 					EMIT3(0x8B,
2062 					      add_2reg(0x40, IA32_EBP,
2063 						       IA32_EDX),
2064 					      STACK_VAR(dst_hi));
2065 			}
2066 
2067 			/* mov ecx,imm32 */
2068 			EMIT2_off32(0xC7, add_1reg(0xC0, sreg_lo), imm32);
2069 
2070 			/* and dreg_lo,sreg_lo */
2071 			EMIT2(0x23, add_2reg(0xC0, sreg_lo, dreg_lo));
2072 			if (is_jmp64) {
2073 				hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2074 				/* mov ebx,imm32 */
2075 				EMIT2_off32(0xC7, add_1reg(0xC0, sreg_hi), hi);
2076 				/* and dreg_hi,sreg_hi */
2077 				EMIT2(0x23, add_2reg(0xC0, sreg_hi, dreg_hi));
2078 				/* or dreg_lo,dreg_hi */
2079 				EMIT2(0x09, add_2reg(0xC0, dreg_lo, dreg_hi));
2080 			}
2081 			goto emit_cond_jmp;
2082 		}
2083 		case BPF_JMP | BPF_JEQ | BPF_K:
2084 		case BPF_JMP | BPF_JNE | BPF_K:
2085 		case BPF_JMP | BPF_JGT | BPF_K:
2086 		case BPF_JMP | BPF_JLT | BPF_K:
2087 		case BPF_JMP | BPF_JGE | BPF_K:
2088 		case BPF_JMP | BPF_JLE | BPF_K:
2089 		case BPF_JMP32 | BPF_JEQ | BPF_K:
2090 		case BPF_JMP32 | BPF_JNE | BPF_K:
2091 		case BPF_JMP32 | BPF_JGT | BPF_K:
2092 		case BPF_JMP32 | BPF_JLT | BPF_K:
2093 		case BPF_JMP32 | BPF_JGE | BPF_K:
2094 		case BPF_JMP32 | BPF_JLE | BPF_K:
2095 		case BPF_JMP32 | BPF_JSGT | BPF_K:
2096 		case BPF_JMP32 | BPF_JSLE | BPF_K:
2097 		case BPF_JMP32 | BPF_JSLT | BPF_K:
2098 		case BPF_JMP32 | BPF_JSGE | BPF_K: {
2099 			bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2100 			u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2101 			u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2102 			u8 sreg_lo = IA32_ECX;
2103 			u8 sreg_hi = IA32_EBX;
2104 			u32 hi;
2105 
2106 			if (dstk) {
2107 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2108 				      STACK_VAR(dst_lo));
2109 				if (is_jmp64)
2110 					EMIT3(0x8B,
2111 					      add_2reg(0x40, IA32_EBP,
2112 						       IA32_EDX),
2113 					      STACK_VAR(dst_hi));
2114 			}
2115 
2116 			/* mov ecx,imm32 */
2117 			EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
2118 			if (is_jmp64) {
2119 				hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2120 				/* mov ebx,imm32 */
2121 				EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EBX), hi);
2122 				/* cmp dreg_hi,sreg_hi */
2123 				EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2124 				EMIT2(IA32_JNE, 2);
2125 			}
2126 			/* cmp dreg_lo,sreg_lo */
2127 			EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2128 
2129 emit_cond_jmp:		jmp_cond = get_cond_jmp_opcode(BPF_OP(code), false);
2130 			if (jmp_cond == COND_JMP_OPCODE_INVALID)
2131 				return -EFAULT;
2132 			jmp_offset = addrs[i + insn->off] - addrs[i];
2133 			if (is_imm8(jmp_offset)) {
2134 				EMIT2(jmp_cond, jmp_offset);
2135 			} else if (is_simm32(jmp_offset)) {
2136 				EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2137 			} else {
2138 				pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2139 				return -EFAULT;
2140 			}
2141 			break;
2142 		}
2143 		case BPF_JMP | BPF_JSGT | BPF_K:
2144 		case BPF_JMP | BPF_JSLE | BPF_K:
2145 		case BPF_JMP | BPF_JSLT | BPF_K:
2146 		case BPF_JMP | BPF_JSGE | BPF_K: {
2147 			u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2148 			u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2149 			u8 sreg_lo = IA32_ECX;
2150 			u8 sreg_hi = IA32_EBX;
2151 			u32 hi;
2152 
2153 			if (dstk) {
2154 				EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2155 				      STACK_VAR(dst_lo));
2156 				EMIT3(0x8B,
2157 				      add_2reg(0x40, IA32_EBP,
2158 					       IA32_EDX),
2159 				      STACK_VAR(dst_hi));
2160 			}
2161 
2162 			/* mov ecx,imm32 */
2163 			EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
2164 			hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2165 			/* mov ebx,imm32 */
2166 			EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EBX), hi);
2167 			/* cmp dreg_hi,sreg_hi */
2168 			EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2169 			EMIT2(IA32_JNE, 10);
2170 			/* cmp dreg_lo,sreg_lo */
2171 			EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2172 
2173 			/*
2174 			 * For simplicity of branch offset computation,
2175 			 * let's use fixed jump coding here.
2176 			 */
2177 emit_cond_jmp_signed:	/* Check the condition for low 32-bit comparison */
2178 			jmp_cond = get_cond_jmp_opcode(BPF_OP(code), true);
2179 			if (jmp_cond == COND_JMP_OPCODE_INVALID)
2180 				return -EFAULT;
2181 			jmp_offset = addrs[i + insn->off] - addrs[i] + 8;
2182 			if (is_simm32(jmp_offset)) {
2183 				EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2184 			} else {
2185 				pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2186 				return -EFAULT;
2187 			}
2188 			EMIT2(0xEB, 6);
2189 
2190 			/* Check the condition for high 32-bit comparison */
2191 			jmp_cond = get_cond_jmp_opcode(BPF_OP(code), false);
2192 			if (jmp_cond == COND_JMP_OPCODE_INVALID)
2193 				return -EFAULT;
2194 			jmp_offset = addrs[i + insn->off] - addrs[i];
2195 			if (is_simm32(jmp_offset)) {
2196 				EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2197 			} else {
2198 				pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2199 				return -EFAULT;
2200 			}
2201 			break;
2202 		}
2203 		case BPF_JMP | BPF_JA:
2204 			if (insn->off == -1)
2205 				/* -1 jmp instructions will always jump
2206 				 * backwards two bytes. Explicitly handling
2207 				 * this case avoids wasting too many passes
2208 				 * when there are long sequences of replaced
2209 				 * dead code.
2210 				 */
2211 				jmp_offset = -2;
2212 			else
2213 				jmp_offset = addrs[i + insn->off] - addrs[i];
2214 
2215 			if (!jmp_offset)
2216 				/* Optimize out nop jumps */
2217 				break;
2218 emit_jmp:
2219 			if (is_imm8(jmp_offset)) {
2220 				EMIT2(0xEB, jmp_offset);
2221 			} else if (is_simm32(jmp_offset)) {
2222 				EMIT1_off32(0xE9, jmp_offset);
2223 			} else {
2224 				pr_err("jmp gen bug %llx\n", jmp_offset);
2225 				return -EFAULT;
2226 			}
2227 			break;
2228 		/* STX XADD: lock *(u32 *)(dst + off) += src */
2229 		case BPF_STX | BPF_XADD | BPF_W:
2230 		/* STX XADD: lock *(u64 *)(dst + off) += src */
2231 		case BPF_STX | BPF_XADD | BPF_DW:
2232 			goto notyet;
2233 		case BPF_JMP | BPF_EXIT:
2234 			if (seen_exit) {
2235 				jmp_offset = ctx->cleanup_addr - addrs[i];
2236 				goto emit_jmp;
2237 			}
2238 			seen_exit = true;
2239 			/* Update cleanup_addr */
2240 			ctx->cleanup_addr = proglen;
2241 			emit_epilogue(&prog, bpf_prog->aux->stack_depth);
2242 			break;
2243 notyet:
2244 			pr_info_once("*** NOT YET: opcode %02x ***\n", code);
2245 			return -EFAULT;
2246 		default:
2247 			/*
2248 			 * This error will be seen if new instruction was added
2249 			 * to interpreter, but not to JIT or if there is junk in
2250 			 * bpf_prog
2251 			 */
2252 			pr_err("bpf_jit: unknown opcode %02x\n", code);
2253 			return -EINVAL;
2254 		}
2255 
2256 		ilen = prog - temp;
2257 		if (ilen > BPF_MAX_INSN_SIZE) {
2258 			pr_err("bpf_jit: fatal insn size error\n");
2259 			return -EFAULT;
2260 		}
2261 
2262 		if (image) {
2263 			if (unlikely(proglen + ilen > oldproglen)) {
2264 				pr_err("bpf_jit: fatal error\n");
2265 				return -EFAULT;
2266 			}
2267 			memcpy(image + proglen, temp, ilen);
2268 		}
2269 		proglen += ilen;
2270 		addrs[i] = proglen;
2271 		prog = temp;
2272 	}
2273 	return proglen;
2274 }
2275 
2276 bool bpf_jit_needs_zext(void)
2277 {
2278 	return true;
2279 }
2280 
2281 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
2282 {
2283 	struct bpf_binary_header *header = NULL;
2284 	struct bpf_prog *tmp, *orig_prog = prog;
2285 	int proglen, oldproglen = 0;
2286 	struct jit_context ctx = {};
2287 	bool tmp_blinded = false;
2288 	u8 *image = NULL;
2289 	int *addrs;
2290 	int pass;
2291 	int i;
2292 
2293 	if (!prog->jit_requested)
2294 		return orig_prog;
2295 
2296 	tmp = bpf_jit_blind_constants(prog);
2297 	/*
2298 	 * If blinding was requested and we failed during blinding,
2299 	 * we must fall back to the interpreter.
2300 	 */
2301 	if (IS_ERR(tmp))
2302 		return orig_prog;
2303 	if (tmp != prog) {
2304 		tmp_blinded = true;
2305 		prog = tmp;
2306 	}
2307 
2308 	addrs = kmalloc_array(prog->len, sizeof(*addrs), GFP_KERNEL);
2309 	if (!addrs) {
2310 		prog = orig_prog;
2311 		goto out;
2312 	}
2313 
2314 	/*
2315 	 * Before first pass, make a rough estimation of addrs[]
2316 	 * each BPF instruction is translated to less than 64 bytes
2317 	 */
2318 	for (proglen = 0, i = 0; i < prog->len; i++) {
2319 		proglen += 64;
2320 		addrs[i] = proglen;
2321 	}
2322 	ctx.cleanup_addr = proglen;
2323 
2324 	/*
2325 	 * JITed image shrinks with every pass and the loop iterates
2326 	 * until the image stops shrinking. Very large BPF programs
2327 	 * may converge on the last pass. In such case do one more
2328 	 * pass to emit the final image.
2329 	 */
2330 	for (pass = 0; pass < 20 || image; pass++) {
2331 		proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
2332 		if (proglen <= 0) {
2333 out_image:
2334 			image = NULL;
2335 			if (header)
2336 				bpf_jit_binary_free(header);
2337 			prog = orig_prog;
2338 			goto out_addrs;
2339 		}
2340 		if (image) {
2341 			if (proglen != oldproglen) {
2342 				pr_err("bpf_jit: proglen=%d != oldproglen=%d\n",
2343 				       proglen, oldproglen);
2344 				goto out_image;
2345 			}
2346 			break;
2347 		}
2348 		if (proglen == oldproglen) {
2349 			header = bpf_jit_binary_alloc(proglen, &image,
2350 						      1, jit_fill_hole);
2351 			if (!header) {
2352 				prog = orig_prog;
2353 				goto out_addrs;
2354 			}
2355 		}
2356 		oldproglen = proglen;
2357 		cond_resched();
2358 	}
2359 
2360 	if (bpf_jit_enable > 1)
2361 		bpf_jit_dump(prog->len, proglen, pass + 1, image);
2362 
2363 	if (image) {
2364 		bpf_jit_binary_lock_ro(header);
2365 		prog->bpf_func = (void *)image;
2366 		prog->jited = 1;
2367 		prog->jited_len = proglen;
2368 	} else {
2369 		prog = orig_prog;
2370 	}
2371 
2372 out_addrs:
2373 	kfree(addrs);
2374 out:
2375 	if (tmp_blinded)
2376 		bpf_jit_prog_release_other(prog, prog == orig_prog ?
2377 					   tmp : orig_prog);
2378 	return prog;
2379 }
2380