Merge tag 'io_uring-5.14-2021-08-13' of git://git.kernel.dk/linux-block
[linux-2.6-microblaze.git] / arch / x86 / net / bpf_jit_comp32.c
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 void emit_push_r32(const u8 src[], u8 **pprog)
1394 {
1395         u8 *prog = *pprog;
1396         int cnt = 0;
1397
1398         /* mov ecx,dword ptr [ebp+off] */
1399         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src_lo));
1400         /* push ecx */
1401         EMIT1(0x51);
1402
1403         *pprog = prog;
1404 }
1405
1406 static u8 get_cond_jmp_opcode(const u8 op, bool is_cmp_lo)
1407 {
1408         u8 jmp_cond;
1409
1410         /* Convert BPF opcode to x86 */
1411         switch (op) {
1412         case BPF_JEQ:
1413                 jmp_cond = IA32_JE;
1414                 break;
1415         case BPF_JSET:
1416         case BPF_JNE:
1417                 jmp_cond = IA32_JNE;
1418                 break;
1419         case BPF_JGT:
1420                 /* GT is unsigned '>', JA in x86 */
1421                 jmp_cond = IA32_JA;
1422                 break;
1423         case BPF_JLT:
1424                 /* LT is unsigned '<', JB in x86 */
1425                 jmp_cond = IA32_JB;
1426                 break;
1427         case BPF_JGE:
1428                 /* GE is unsigned '>=', JAE in x86 */
1429                 jmp_cond = IA32_JAE;
1430                 break;
1431         case BPF_JLE:
1432                 /* LE is unsigned '<=', JBE in x86 */
1433                 jmp_cond = IA32_JBE;
1434                 break;
1435         case BPF_JSGT:
1436                 if (!is_cmp_lo)
1437                         /* Signed '>', GT in x86 */
1438                         jmp_cond = IA32_JG;
1439                 else
1440                         /* GT is unsigned '>', JA in x86 */
1441                         jmp_cond = IA32_JA;
1442                 break;
1443         case BPF_JSLT:
1444                 if (!is_cmp_lo)
1445                         /* Signed '<', LT in x86 */
1446                         jmp_cond = IA32_JL;
1447                 else
1448                         /* LT is unsigned '<', JB in x86 */
1449                         jmp_cond = IA32_JB;
1450                 break;
1451         case BPF_JSGE:
1452                 if (!is_cmp_lo)
1453                         /* Signed '>=', GE in x86 */
1454                         jmp_cond = IA32_JGE;
1455                 else
1456                         /* GE is unsigned '>=', JAE in x86 */
1457                         jmp_cond = IA32_JAE;
1458                 break;
1459         case BPF_JSLE:
1460                 if (!is_cmp_lo)
1461                         /* Signed '<=', LE in x86 */
1462                         jmp_cond = IA32_JLE;
1463                 else
1464                         /* LE is unsigned '<=', JBE in x86 */
1465                         jmp_cond = IA32_JBE;
1466                 break;
1467         default: /* to silence GCC warning */
1468                 jmp_cond = COND_JMP_OPCODE_INVALID;
1469                 break;
1470         }
1471
1472         return jmp_cond;
1473 }
1474
1475 /* i386 kernel compiles with "-mregparm=3".  From gcc document:
1476  *
1477  * ==== snippet ====
1478  * regparm (number)
1479  *      On x86-32 targets, the regparm attribute causes the compiler
1480  *      to pass arguments number one to (number) if they are of integral
1481  *      type in registers EAX, EDX, and ECX instead of on the stack.
1482  *      Functions that take a variable number of arguments continue
1483  *      to be passed all of their arguments on the stack.
1484  * ==== snippet ====
1485  *
1486  * The first three args of a function will be considered for
1487  * putting into the 32bit register EAX, EDX, and ECX.
1488  *
1489  * Two 32bit registers are used to pass a 64bit arg.
1490  *
1491  * For example,
1492  * void foo(u32 a, u32 b, u32 c, u32 d):
1493  *      u32 a: EAX
1494  *      u32 b: EDX
1495  *      u32 c: ECX
1496  *      u32 d: stack
1497  *
1498  * void foo(u64 a, u32 b, u32 c):
1499  *      u64 a: EAX (lo32) EDX (hi32)
1500  *      u32 b: ECX
1501  *      u32 c: stack
1502  *
1503  * void foo(u32 a, u64 b, u32 c):
1504  *      u32 a: EAX
1505  *      u64 b: EDX (lo32) ECX (hi32)
1506  *      u32 c: stack
1507  *
1508  * void foo(u32 a, u32 b, u64 c):
1509  *      u32 a: EAX
1510  *      u32 b: EDX
1511  *      u64 c: stack
1512  *
1513  * The return value will be stored in the EAX (and EDX for 64bit value).
1514  *
1515  * For example,
1516  * u32 foo(u32 a, u32 b, u32 c):
1517  *      return value: EAX
1518  *
1519  * u64 foo(u32 a, u32 b, u32 c):
1520  *      return value: EAX (lo32) EDX (hi32)
1521  *
1522  * Notes:
1523  *      The verifier only accepts function having integer and pointers
1524  *      as its args and return value, so it does not have
1525  *      struct-by-value.
1526  *
1527  * emit_kfunc_call() finds out the btf_func_model by calling
1528  * bpf_jit_find_kfunc_model().  A btf_func_model
1529  * has the details about the number of args, size of each arg,
1530  * and the size of the return value.
1531  *
1532  * It first decides how many args can be passed by EAX, EDX, and ECX.
1533  * That will decide what args should be pushed to the stack:
1534  * [first_stack_regno, last_stack_regno] are the bpf regnos
1535  * that should be pushed to the stack.
1536  *
1537  * It will first push all args to the stack because the push
1538  * will need to use ECX.  Then, it moves
1539  * [BPF_REG_1, first_stack_regno) to EAX, EDX, and ECX.
1540  *
1541  * When emitting a call (0xE8), it needs to figure out
1542  * the jmp_offset relative to the jit-insn address immediately
1543  * following the call (0xE8) instruction.  At this point, it knows
1544  * the end of the jit-insn address after completely translated the
1545  * current (BPF_JMP | BPF_CALL) bpf-insn.  It is passed as "end_addr"
1546  * to the emit_kfunc_call().  Thus, it can learn the "immediate-follow-call"
1547  * address by figuring out how many jit-insn is generated between
1548  * the call (0xE8) and the end_addr:
1549  *      - 0-1 jit-insn (3 bytes each) to restore the esp pointer if there
1550  *        is arg pushed to the stack.
1551  *      - 0-2 jit-insns (3 bytes each) to handle the return value.
1552  */
1553 static int emit_kfunc_call(const struct bpf_prog *bpf_prog, u8 *end_addr,
1554                            const struct bpf_insn *insn, u8 **pprog)
1555 {
1556         const u8 arg_regs[] = { IA32_EAX, IA32_EDX, IA32_ECX };
1557         int i, cnt = 0, first_stack_regno, last_stack_regno;
1558         int free_arg_regs = ARRAY_SIZE(arg_regs);
1559         const struct btf_func_model *fm;
1560         int bytes_in_stack = 0;
1561         const u8 *cur_arg_reg;
1562         u8 *prog = *pprog;
1563         s64 jmp_offset;
1564
1565         fm = bpf_jit_find_kfunc_model(bpf_prog, insn);
1566         if (!fm)
1567                 return -EINVAL;
1568
1569         first_stack_regno = BPF_REG_1;
1570         for (i = 0; i < fm->nr_args; i++) {
1571                 int regs_needed = fm->arg_size[i] > sizeof(u32) ? 2 : 1;
1572
1573                 if (regs_needed > free_arg_regs)
1574                         break;
1575
1576                 free_arg_regs -= regs_needed;
1577                 first_stack_regno++;
1578         }
1579
1580         /* Push the args to the stack */
1581         last_stack_regno = BPF_REG_0 + fm->nr_args;
1582         for (i = last_stack_regno; i >= first_stack_regno; i--) {
1583                 if (fm->arg_size[i - 1] > sizeof(u32)) {
1584                         emit_push_r64(bpf2ia32[i], &prog);
1585                         bytes_in_stack += 8;
1586                 } else {
1587                         emit_push_r32(bpf2ia32[i], &prog);
1588                         bytes_in_stack += 4;
1589                 }
1590         }
1591
1592         cur_arg_reg = &arg_regs[0];
1593         for (i = BPF_REG_1; i < first_stack_regno; i++) {
1594                 /* mov e[adc]x,dword ptr [ebp+off] */
1595                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, *cur_arg_reg++),
1596                       STACK_VAR(bpf2ia32[i][0]));
1597                 if (fm->arg_size[i - 1] > sizeof(u32))
1598                         /* mov e[adc]x,dword ptr [ebp+off] */
1599                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, *cur_arg_reg++),
1600                               STACK_VAR(bpf2ia32[i][1]));
1601         }
1602
1603         if (bytes_in_stack)
1604                 /* add esp,"bytes_in_stack" */
1605                 end_addr -= 3;
1606
1607         /* mov dword ptr [ebp+off],edx */
1608         if (fm->ret_size > sizeof(u32))
1609                 end_addr -= 3;
1610
1611         /* mov dword ptr [ebp+off],eax */
1612         if (fm->ret_size)
1613                 end_addr -= 3;
1614
1615         jmp_offset = (u8 *)__bpf_call_base + insn->imm - end_addr;
1616         if (!is_simm32(jmp_offset)) {
1617                 pr_err("unsupported BPF kernel function jmp_offset:%lld\n",
1618                        jmp_offset);
1619                 return -EINVAL;
1620         }
1621
1622         EMIT1_off32(0xE8, jmp_offset);
1623
1624         if (fm->ret_size)
1625                 /* mov dword ptr [ebp+off],eax */
1626                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
1627                       STACK_VAR(bpf2ia32[BPF_REG_0][0]));
1628
1629         if (fm->ret_size > sizeof(u32))
1630                 /* mov dword ptr [ebp+off],edx */
1631                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
1632                       STACK_VAR(bpf2ia32[BPF_REG_0][1]));
1633
1634         if (bytes_in_stack)
1635                 /* add esp,"bytes_in_stack" */
1636                 EMIT3(0x83, add_1reg(0xC0, IA32_ESP), bytes_in_stack);
1637
1638         *pprog = prog;
1639
1640         return 0;
1641 }
1642
1643 static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
1644                   int oldproglen, struct jit_context *ctx)
1645 {
1646         struct bpf_insn *insn = bpf_prog->insnsi;
1647         int insn_cnt = bpf_prog->len;
1648         bool seen_exit = false;
1649         u8 temp[BPF_MAX_INSN_SIZE + BPF_INSN_SAFETY];
1650         int i, cnt = 0;
1651         int proglen = 0;
1652         u8 *prog = temp;
1653
1654         emit_prologue(&prog, bpf_prog->aux->stack_depth);
1655
1656         for (i = 0; i < insn_cnt; i++, insn++) {
1657                 const s32 imm32 = insn->imm;
1658                 const bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
1659                 const bool dstk = insn->dst_reg != BPF_REG_AX;
1660                 const bool sstk = insn->src_reg != BPF_REG_AX;
1661                 const u8 code = insn->code;
1662                 const u8 *dst = bpf2ia32[insn->dst_reg];
1663                 const u8 *src = bpf2ia32[insn->src_reg];
1664                 const u8 *r0 = bpf2ia32[BPF_REG_0];
1665                 s64 jmp_offset;
1666                 u8 jmp_cond;
1667                 int ilen;
1668                 u8 *func;
1669
1670                 switch (code) {
1671                 /* ALU operations */
1672                 /* dst = src */
1673                 case BPF_ALU | BPF_MOV | BPF_K:
1674                 case BPF_ALU | BPF_MOV | BPF_X:
1675                 case BPF_ALU64 | BPF_MOV | BPF_K:
1676                 case BPF_ALU64 | BPF_MOV | BPF_X:
1677                         switch (BPF_SRC(code)) {
1678                         case BPF_X:
1679                                 if (imm32 == 1) {
1680                                         /* Special mov32 for zext. */
1681                                         emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1682                                         break;
1683                                 }
1684                                 emit_ia32_mov_r64(is64, dst, src, dstk, sstk,
1685                                                   &prog, bpf_prog->aux);
1686                                 break;
1687                         case BPF_K:
1688                                 /* Sign-extend immediate value to dst reg */
1689                                 emit_ia32_mov_i64(is64, dst, imm32,
1690                                                   dstk, &prog);
1691                                 break;
1692                         }
1693                         break;
1694                 /* dst = dst + src/imm */
1695                 /* dst = dst - src/imm */
1696                 /* dst = dst | src/imm */
1697                 /* dst = dst & src/imm */
1698                 /* dst = dst ^ src/imm */
1699                 /* dst = dst * src/imm */
1700                 /* dst = dst << src */
1701                 /* dst = dst >> src */
1702                 case BPF_ALU | BPF_ADD | BPF_K:
1703                 case BPF_ALU | BPF_ADD | BPF_X:
1704                 case BPF_ALU | BPF_SUB | BPF_K:
1705                 case BPF_ALU | BPF_SUB | BPF_X:
1706                 case BPF_ALU | BPF_OR | BPF_K:
1707                 case BPF_ALU | BPF_OR | BPF_X:
1708                 case BPF_ALU | BPF_AND | BPF_K:
1709                 case BPF_ALU | BPF_AND | BPF_X:
1710                 case BPF_ALU | BPF_XOR | BPF_K:
1711                 case BPF_ALU | BPF_XOR | BPF_X:
1712                 case BPF_ALU64 | BPF_ADD | BPF_K:
1713                 case BPF_ALU64 | BPF_ADD | BPF_X:
1714                 case BPF_ALU64 | BPF_SUB | BPF_K:
1715                 case BPF_ALU64 | BPF_SUB | BPF_X:
1716                 case BPF_ALU64 | BPF_OR | BPF_K:
1717                 case BPF_ALU64 | BPF_OR | BPF_X:
1718                 case BPF_ALU64 | BPF_AND | BPF_K:
1719                 case BPF_ALU64 | BPF_AND | BPF_X:
1720                 case BPF_ALU64 | BPF_XOR | BPF_K:
1721                 case BPF_ALU64 | BPF_XOR | BPF_X:
1722                         switch (BPF_SRC(code)) {
1723                         case BPF_X:
1724                                 emit_ia32_alu_r64(is64, BPF_OP(code), dst,
1725                                                   src, dstk, sstk, &prog,
1726                                                   bpf_prog->aux);
1727                                 break;
1728                         case BPF_K:
1729                                 emit_ia32_alu_i64(is64, BPF_OP(code), dst,
1730                                                   imm32, dstk, &prog,
1731                                                   bpf_prog->aux);
1732                                 break;
1733                         }
1734                         break;
1735                 case BPF_ALU | BPF_MUL | BPF_K:
1736                 case BPF_ALU | BPF_MUL | BPF_X:
1737                         switch (BPF_SRC(code)) {
1738                         case BPF_X:
1739                                 emit_ia32_mul_r(dst_lo, src_lo, dstk,
1740                                                 sstk, &prog);
1741                                 break;
1742                         case BPF_K:
1743                                 /* mov ecx,imm32*/
1744                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1745                                             imm32);
1746                                 emit_ia32_mul_r(dst_lo, IA32_ECX, dstk,
1747                                                 false, &prog);
1748                                 break;
1749                         }
1750                         if (!bpf_prog->aux->verifier_zext)
1751                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1752                         break;
1753                 case BPF_ALU | BPF_LSH | BPF_X:
1754                 case BPF_ALU | BPF_RSH | BPF_X:
1755                 case BPF_ALU | BPF_ARSH | BPF_K:
1756                 case BPF_ALU | BPF_ARSH | BPF_X:
1757                         switch (BPF_SRC(code)) {
1758                         case BPF_X:
1759                                 emit_ia32_shift_r(BPF_OP(code), dst_lo, src_lo,
1760                                                   dstk, sstk, &prog);
1761                                 break;
1762                         case BPF_K:
1763                                 /* mov ecx,imm32*/
1764                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1765                                             imm32);
1766                                 emit_ia32_shift_r(BPF_OP(code), dst_lo,
1767                                                   IA32_ECX, dstk, false,
1768                                                   &prog);
1769                                 break;
1770                         }
1771                         if (!bpf_prog->aux->verifier_zext)
1772                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1773                         break;
1774                 /* dst = dst / src(imm) */
1775                 /* dst = dst % src(imm) */
1776                 case BPF_ALU | BPF_DIV | BPF_K:
1777                 case BPF_ALU | BPF_DIV | BPF_X:
1778                 case BPF_ALU | BPF_MOD | BPF_K:
1779                 case BPF_ALU | BPF_MOD | BPF_X:
1780                         switch (BPF_SRC(code)) {
1781                         case BPF_X:
1782                                 emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
1783                                                     src_lo, dstk, sstk, &prog);
1784                                 break;
1785                         case BPF_K:
1786                                 /* mov ecx,imm32*/
1787                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1788                                             imm32);
1789                                 emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
1790                                                     IA32_ECX, dstk, false,
1791                                                     &prog);
1792                                 break;
1793                         }
1794                         if (!bpf_prog->aux->verifier_zext)
1795                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1796                         break;
1797                 case BPF_ALU64 | BPF_DIV | BPF_K:
1798                 case BPF_ALU64 | BPF_DIV | BPF_X:
1799                 case BPF_ALU64 | BPF_MOD | BPF_K:
1800                 case BPF_ALU64 | BPF_MOD | BPF_X:
1801                         goto notyet;
1802                 /* dst = dst >> imm */
1803                 /* dst = dst << imm */
1804                 case BPF_ALU | BPF_RSH | BPF_K:
1805                 case BPF_ALU | BPF_LSH | BPF_K:
1806                         if (unlikely(imm32 > 31))
1807                                 return -EINVAL;
1808                         /* mov ecx,imm32*/
1809                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
1810                         emit_ia32_shift_r(BPF_OP(code), dst_lo, IA32_ECX, dstk,
1811                                           false, &prog);
1812                         if (!bpf_prog->aux->verifier_zext)
1813                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1814                         break;
1815                 /* dst = dst << imm */
1816                 case BPF_ALU64 | BPF_LSH | BPF_K:
1817                         if (unlikely(imm32 > 63))
1818                                 return -EINVAL;
1819                         emit_ia32_lsh_i64(dst, imm32, dstk, &prog);
1820                         break;
1821                 /* dst = dst >> imm */
1822                 case BPF_ALU64 | BPF_RSH | BPF_K:
1823                         if (unlikely(imm32 > 63))
1824                                 return -EINVAL;
1825                         emit_ia32_rsh_i64(dst, imm32, dstk, &prog);
1826                         break;
1827                 /* dst = dst << src */
1828                 case BPF_ALU64 | BPF_LSH | BPF_X:
1829                         emit_ia32_lsh_r64(dst, src, dstk, sstk, &prog);
1830                         break;
1831                 /* dst = dst >> src */
1832                 case BPF_ALU64 | BPF_RSH | BPF_X:
1833                         emit_ia32_rsh_r64(dst, src, dstk, sstk, &prog);
1834                         break;
1835                 /* dst = dst >> src (signed) */
1836                 case BPF_ALU64 | BPF_ARSH | BPF_X:
1837                         emit_ia32_arsh_r64(dst, src, dstk, sstk, &prog);
1838                         break;
1839                 /* dst = dst >> imm (signed) */
1840                 case BPF_ALU64 | BPF_ARSH | BPF_K:
1841                         if (unlikely(imm32 > 63))
1842                                 return -EINVAL;
1843                         emit_ia32_arsh_i64(dst, imm32, dstk, &prog);
1844                         break;
1845                 /* dst = ~dst */
1846                 case BPF_ALU | BPF_NEG:
1847                         emit_ia32_alu_i(is64, false, BPF_OP(code),
1848                                         dst_lo, 0, dstk, &prog);
1849                         if (!bpf_prog->aux->verifier_zext)
1850                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1851                         break;
1852                 /* dst = ~dst (64 bit) */
1853                 case BPF_ALU64 | BPF_NEG:
1854                         emit_ia32_neg64(dst, dstk, &prog);
1855                         break;
1856                 /* dst = dst * src/imm */
1857                 case BPF_ALU64 | BPF_MUL | BPF_X:
1858                 case BPF_ALU64 | BPF_MUL | BPF_K:
1859                         switch (BPF_SRC(code)) {
1860                         case BPF_X:
1861                                 emit_ia32_mul_r64(dst, src, dstk, sstk, &prog);
1862                                 break;
1863                         case BPF_K:
1864                                 emit_ia32_mul_i64(dst, imm32, dstk, &prog);
1865                                 break;
1866                         }
1867                         break;
1868                 /* dst = htole(dst) */
1869                 case BPF_ALU | BPF_END | BPF_FROM_LE:
1870                         emit_ia32_to_le_r64(dst, imm32, dstk, &prog,
1871                                             bpf_prog->aux);
1872                         break;
1873                 /* dst = htobe(dst) */
1874                 case BPF_ALU | BPF_END | BPF_FROM_BE:
1875                         emit_ia32_to_be_r64(dst, imm32, dstk, &prog,
1876                                             bpf_prog->aux);
1877                         break;
1878                 /* dst = imm64 */
1879                 case BPF_LD | BPF_IMM | BPF_DW: {
1880                         s32 hi, lo = imm32;
1881
1882                         hi = insn[1].imm;
1883                         emit_ia32_mov_i(dst_lo, lo, dstk, &prog);
1884                         emit_ia32_mov_i(dst_hi, hi, dstk, &prog);
1885                         insn++;
1886                         i++;
1887                         break;
1888                 }
1889                 /* speculation barrier */
1890                 case BPF_ST | BPF_NOSPEC:
1891                         if (boot_cpu_has(X86_FEATURE_XMM2))
1892                                 /* Emit 'lfence' */
1893                                 EMIT3(0x0F, 0xAE, 0xE8);
1894                         break;
1895                 /* ST: *(u8*)(dst_reg + off) = imm */
1896                 case BPF_ST | BPF_MEM | BPF_H:
1897                 case BPF_ST | BPF_MEM | BPF_B:
1898                 case BPF_ST | BPF_MEM | BPF_W:
1899                 case BPF_ST | BPF_MEM | BPF_DW:
1900                         if (dstk)
1901                                 /* mov eax,dword ptr [ebp+off] */
1902                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1903                                       STACK_VAR(dst_lo));
1904                         else
1905                                 /* mov eax,dst_lo */
1906                                 EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1907
1908                         switch (BPF_SIZE(code)) {
1909                         case BPF_B:
1910                                 EMIT(0xC6, 1); break;
1911                         case BPF_H:
1912                                 EMIT2(0x66, 0xC7); break;
1913                         case BPF_W:
1914                         case BPF_DW:
1915                                 EMIT(0xC7, 1); break;
1916                         }
1917
1918                         if (is_imm8(insn->off))
1919                                 EMIT2(add_1reg(0x40, IA32_EAX), insn->off);
1920                         else
1921                                 EMIT1_off32(add_1reg(0x80, IA32_EAX),
1922                                             insn->off);
1923                         EMIT(imm32, bpf_size_to_x86_bytes(BPF_SIZE(code)));
1924
1925                         if (BPF_SIZE(code) == BPF_DW) {
1926                                 u32 hi;
1927
1928                                 hi = imm32 & (1<<31) ? (u32)~0 : 0;
1929                                 EMIT2_off32(0xC7, add_1reg(0x80, IA32_EAX),
1930                                             insn->off + 4);
1931                                 EMIT(hi, 4);
1932                         }
1933                         break;
1934
1935                 /* STX: *(u8*)(dst_reg + off) = src_reg */
1936                 case BPF_STX | BPF_MEM | BPF_B:
1937                 case BPF_STX | BPF_MEM | BPF_H:
1938                 case BPF_STX | BPF_MEM | BPF_W:
1939                 case BPF_STX | BPF_MEM | BPF_DW:
1940                         if (dstk)
1941                                 /* mov eax,dword ptr [ebp+off] */
1942                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1943                                       STACK_VAR(dst_lo));
1944                         else
1945                                 /* mov eax,dst_lo */
1946                                 EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1947
1948                         if (sstk)
1949                                 /* mov edx,dword ptr [ebp+off] */
1950                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1951                                       STACK_VAR(src_lo));
1952                         else
1953                                 /* mov edx,src_lo */
1954                                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_EDX));
1955
1956                         switch (BPF_SIZE(code)) {
1957                         case BPF_B:
1958                                 EMIT(0x88, 1); break;
1959                         case BPF_H:
1960                                 EMIT2(0x66, 0x89); break;
1961                         case BPF_W:
1962                         case BPF_DW:
1963                                 EMIT(0x89, 1); break;
1964                         }
1965
1966                         if (is_imm8(insn->off))
1967                                 EMIT2(add_2reg(0x40, IA32_EAX, IA32_EDX),
1968                                       insn->off);
1969                         else
1970                                 EMIT1_off32(add_2reg(0x80, IA32_EAX, IA32_EDX),
1971                                             insn->off);
1972
1973                         if (BPF_SIZE(code) == BPF_DW) {
1974                                 if (sstk)
1975                                         /* mov edi,dword ptr [ebp+off] */
1976                                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP,
1977                                                              IA32_EDX),
1978                                               STACK_VAR(src_hi));
1979                                 else
1980                                         /* mov edi,src_hi */
1981                                         EMIT2(0x8B, add_2reg(0xC0, src_hi,
1982                                                              IA32_EDX));
1983                                 EMIT1(0x89);
1984                                 if (is_imm8(insn->off + 4)) {
1985                                         EMIT2(add_2reg(0x40, IA32_EAX,
1986                                                        IA32_EDX),
1987                                               insn->off + 4);
1988                                 } else {
1989                                         EMIT1(add_2reg(0x80, IA32_EAX,
1990                                                        IA32_EDX));
1991                                         EMIT(insn->off + 4, 4);
1992                                 }
1993                         }
1994                         break;
1995
1996                 /* LDX: dst_reg = *(u8*)(src_reg + off) */
1997                 case BPF_LDX | BPF_MEM | BPF_B:
1998                 case BPF_LDX | BPF_MEM | BPF_H:
1999                 case BPF_LDX | BPF_MEM | BPF_W:
2000                 case BPF_LDX | BPF_MEM | BPF_DW:
2001                         if (sstk)
2002                                 /* mov eax,dword ptr [ebp+off] */
2003                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2004                                       STACK_VAR(src_lo));
2005                         else
2006                                 /* mov eax,dword ptr [ebp+off] */
2007                                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_EAX));
2008
2009                         switch (BPF_SIZE(code)) {
2010                         case BPF_B:
2011                                 EMIT2(0x0F, 0xB6); break;
2012                         case BPF_H:
2013                                 EMIT2(0x0F, 0xB7); break;
2014                         case BPF_W:
2015                         case BPF_DW:
2016                                 EMIT(0x8B, 1); break;
2017                         }
2018
2019                         if (is_imm8(insn->off))
2020                                 EMIT2(add_2reg(0x40, IA32_EAX, IA32_EDX),
2021                                       insn->off);
2022                         else
2023                                 EMIT1_off32(add_2reg(0x80, IA32_EAX, IA32_EDX),
2024                                             insn->off);
2025
2026                         if (dstk)
2027                                 /* mov dword ptr [ebp+off],edx */
2028                                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
2029                                       STACK_VAR(dst_lo));
2030                         else
2031                                 /* mov dst_lo,edx */
2032                                 EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EDX));
2033                         switch (BPF_SIZE(code)) {
2034                         case BPF_B:
2035                         case BPF_H:
2036                         case BPF_W:
2037                                 if (bpf_prog->aux->verifier_zext)
2038                                         break;
2039                                 if (dstk) {
2040                                         EMIT3(0xC7, add_1reg(0x40, IA32_EBP),
2041                                               STACK_VAR(dst_hi));
2042                                         EMIT(0x0, 4);
2043                                 } else {
2044                                         /* xor dst_hi,dst_hi */
2045                                         EMIT2(0x33,
2046                                               add_2reg(0xC0, dst_hi, dst_hi));
2047                                 }
2048                                 break;
2049                         case BPF_DW:
2050                                 EMIT2_off32(0x8B,
2051                                             add_2reg(0x80, IA32_EAX, IA32_EDX),
2052                                             insn->off + 4);
2053                                 if (dstk)
2054                                         EMIT3(0x89,
2055                                               add_2reg(0x40, IA32_EBP,
2056                                                        IA32_EDX),
2057                                               STACK_VAR(dst_hi));
2058                                 else
2059                                         EMIT2(0x89,
2060                                               add_2reg(0xC0, dst_hi, IA32_EDX));
2061                                 break;
2062                         default:
2063                                 break;
2064                         }
2065                         break;
2066                 /* call */
2067                 case BPF_JMP | BPF_CALL:
2068                 {
2069                         const u8 *r1 = bpf2ia32[BPF_REG_1];
2070                         const u8 *r2 = bpf2ia32[BPF_REG_2];
2071                         const u8 *r3 = bpf2ia32[BPF_REG_3];
2072                         const u8 *r4 = bpf2ia32[BPF_REG_4];
2073                         const u8 *r5 = bpf2ia32[BPF_REG_5];
2074
2075                         if (insn->src_reg == BPF_PSEUDO_CALL)
2076                                 goto notyet;
2077
2078                         if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
2079                                 int err;
2080
2081                                 err = emit_kfunc_call(bpf_prog,
2082                                                       image + addrs[i],
2083                                                       insn, &prog);
2084
2085                                 if (err)
2086                                         return err;
2087                                 break;
2088                         }
2089
2090                         func = (u8 *) __bpf_call_base + imm32;
2091                         jmp_offset = func - (image + addrs[i]);
2092
2093                         if (!imm32 || !is_simm32(jmp_offset)) {
2094                                 pr_err("unsupported BPF func %d addr %p image %p\n",
2095                                        imm32, func, image);
2096                                 return -EINVAL;
2097                         }
2098
2099                         /* mov eax,dword ptr [ebp+off] */
2100                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2101                               STACK_VAR(r1[0]));
2102                         /* mov edx,dword ptr [ebp+off] */
2103                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
2104                               STACK_VAR(r1[1]));
2105
2106                         emit_push_r64(r5, &prog);
2107                         emit_push_r64(r4, &prog);
2108                         emit_push_r64(r3, &prog);
2109                         emit_push_r64(r2, &prog);
2110
2111                         EMIT1_off32(0xE8, jmp_offset + 9);
2112
2113                         /* mov dword ptr [ebp+off],eax */
2114                         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
2115                               STACK_VAR(r0[0]));
2116                         /* mov dword ptr [ebp+off],edx */
2117                         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
2118                               STACK_VAR(r0[1]));
2119
2120                         /* add esp,32 */
2121                         EMIT3(0x83, add_1reg(0xC0, IA32_ESP), 32);
2122                         break;
2123                 }
2124                 case BPF_JMP | BPF_TAIL_CALL:
2125                         emit_bpf_tail_call(&prog);
2126                         break;
2127
2128                 /* cond jump */
2129                 case BPF_JMP | BPF_JEQ | BPF_X:
2130                 case BPF_JMP | BPF_JNE | BPF_X:
2131                 case BPF_JMP | BPF_JGT | BPF_X:
2132                 case BPF_JMP | BPF_JLT | BPF_X:
2133                 case BPF_JMP | BPF_JGE | BPF_X:
2134                 case BPF_JMP | BPF_JLE | BPF_X:
2135                 case BPF_JMP32 | BPF_JEQ | BPF_X:
2136                 case BPF_JMP32 | BPF_JNE | BPF_X:
2137                 case BPF_JMP32 | BPF_JGT | BPF_X:
2138                 case BPF_JMP32 | BPF_JLT | BPF_X:
2139                 case BPF_JMP32 | BPF_JGE | BPF_X:
2140                 case BPF_JMP32 | BPF_JLE | BPF_X:
2141                 case BPF_JMP32 | BPF_JSGT | BPF_X:
2142                 case BPF_JMP32 | BPF_JSLE | BPF_X:
2143                 case BPF_JMP32 | BPF_JSLT | BPF_X:
2144                 case BPF_JMP32 | BPF_JSGE | BPF_X: {
2145                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2146                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2147                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2148                         u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2149                         u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2150
2151                         if (dstk) {
2152                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2153                                       STACK_VAR(dst_lo));
2154                                 if (is_jmp64)
2155                                         EMIT3(0x8B,
2156                                               add_2reg(0x40, IA32_EBP,
2157                                                        IA32_EDX),
2158                                               STACK_VAR(dst_hi));
2159                         }
2160
2161                         if (sstk) {
2162                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2163                                       STACK_VAR(src_lo));
2164                                 if (is_jmp64)
2165                                         EMIT3(0x8B,
2166                                               add_2reg(0x40, IA32_EBP,
2167                                                        IA32_EBX),
2168                                               STACK_VAR(src_hi));
2169                         }
2170
2171                         if (is_jmp64) {
2172                                 /* cmp dreg_hi,sreg_hi */
2173                                 EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2174                                 EMIT2(IA32_JNE, 2);
2175                         }
2176                         /* cmp dreg_lo,sreg_lo */
2177                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2178                         goto emit_cond_jmp;
2179                 }
2180                 case BPF_JMP | BPF_JSGT | BPF_X:
2181                 case BPF_JMP | BPF_JSLE | BPF_X:
2182                 case BPF_JMP | BPF_JSLT | BPF_X:
2183                 case BPF_JMP | BPF_JSGE | BPF_X: {
2184                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2185                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2186                         u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2187                         u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2188
2189                         if (dstk) {
2190                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2191                                       STACK_VAR(dst_lo));
2192                                 EMIT3(0x8B,
2193                                       add_2reg(0x40, IA32_EBP,
2194                                                IA32_EDX),
2195                                       STACK_VAR(dst_hi));
2196                         }
2197
2198                         if (sstk) {
2199                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2200                                       STACK_VAR(src_lo));
2201                                 EMIT3(0x8B,
2202                                       add_2reg(0x40, IA32_EBP,
2203                                                IA32_EBX),
2204                                       STACK_VAR(src_hi));
2205                         }
2206
2207                         /* cmp dreg_hi,sreg_hi */
2208                         EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2209                         EMIT2(IA32_JNE, 10);
2210                         /* cmp dreg_lo,sreg_lo */
2211                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2212                         goto emit_cond_jmp_signed;
2213                 }
2214                 case BPF_JMP | BPF_JSET | BPF_X:
2215                 case BPF_JMP32 | BPF_JSET | BPF_X: {
2216                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2217                         u8 dreg_lo = IA32_EAX;
2218                         u8 dreg_hi = IA32_EDX;
2219                         u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2220                         u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2221
2222                         if (dstk) {
2223                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2224                                       STACK_VAR(dst_lo));
2225                                 if (is_jmp64)
2226                                         EMIT3(0x8B,
2227                                               add_2reg(0x40, IA32_EBP,
2228                                                        IA32_EDX),
2229                                               STACK_VAR(dst_hi));
2230                         } else {
2231                                 /* mov dreg_lo,dst_lo */
2232                                 EMIT2(0x89, add_2reg(0xC0, dreg_lo, dst_lo));
2233                                 if (is_jmp64)
2234                                         /* mov dreg_hi,dst_hi */
2235                                         EMIT2(0x89,
2236                                               add_2reg(0xC0, dreg_hi, dst_hi));
2237                         }
2238
2239                         if (sstk) {
2240                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2241                                       STACK_VAR(src_lo));
2242                                 if (is_jmp64)
2243                                         EMIT3(0x8B,
2244                                               add_2reg(0x40, IA32_EBP,
2245                                                        IA32_EBX),
2246                                               STACK_VAR(src_hi));
2247                         }
2248                         /* and dreg_lo,sreg_lo */
2249                         EMIT2(0x23, add_2reg(0xC0, sreg_lo, dreg_lo));
2250                         if (is_jmp64) {
2251                                 /* and dreg_hi,sreg_hi */
2252                                 EMIT2(0x23, add_2reg(0xC0, sreg_hi, dreg_hi));
2253                                 /* or dreg_lo,dreg_hi */
2254                                 EMIT2(0x09, add_2reg(0xC0, dreg_lo, dreg_hi));
2255                         }
2256                         goto emit_cond_jmp;
2257                 }
2258                 case BPF_JMP | BPF_JSET | BPF_K:
2259                 case BPF_JMP32 | BPF_JSET | BPF_K: {
2260                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2261                         u8 dreg_lo = IA32_EAX;
2262                         u8 dreg_hi = IA32_EDX;
2263                         u8 sreg_lo = IA32_ECX;
2264                         u8 sreg_hi = IA32_EBX;
2265                         u32 hi;
2266
2267                         if (dstk) {
2268                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2269                                       STACK_VAR(dst_lo));
2270                                 if (is_jmp64)
2271                                         EMIT3(0x8B,
2272                                               add_2reg(0x40, IA32_EBP,
2273                                                        IA32_EDX),
2274                                               STACK_VAR(dst_hi));
2275                         } else {
2276                                 /* mov dreg_lo,dst_lo */
2277                                 EMIT2(0x89, add_2reg(0xC0, dreg_lo, dst_lo));
2278                                 if (is_jmp64)
2279                                         /* mov dreg_hi,dst_hi */
2280                                         EMIT2(0x89,
2281                                               add_2reg(0xC0, dreg_hi, dst_hi));
2282                         }
2283
2284                         /* mov ecx,imm32 */
2285                         EMIT2_off32(0xC7, add_1reg(0xC0, sreg_lo), imm32);
2286
2287                         /* and dreg_lo,sreg_lo */
2288                         EMIT2(0x23, add_2reg(0xC0, sreg_lo, dreg_lo));
2289                         if (is_jmp64) {
2290                                 hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2291                                 /* mov ebx,imm32 */
2292                                 EMIT2_off32(0xC7, add_1reg(0xC0, sreg_hi), hi);
2293                                 /* and dreg_hi,sreg_hi */
2294                                 EMIT2(0x23, add_2reg(0xC0, sreg_hi, dreg_hi));
2295                                 /* or dreg_lo,dreg_hi */
2296                                 EMIT2(0x09, add_2reg(0xC0, dreg_lo, dreg_hi));
2297                         }
2298                         goto emit_cond_jmp;
2299                 }
2300                 case BPF_JMP | BPF_JEQ | BPF_K:
2301                 case BPF_JMP | BPF_JNE | BPF_K:
2302                 case BPF_JMP | BPF_JGT | BPF_K:
2303                 case BPF_JMP | BPF_JLT | BPF_K:
2304                 case BPF_JMP | BPF_JGE | BPF_K:
2305                 case BPF_JMP | BPF_JLE | BPF_K:
2306                 case BPF_JMP32 | BPF_JEQ | BPF_K:
2307                 case BPF_JMP32 | BPF_JNE | BPF_K:
2308                 case BPF_JMP32 | BPF_JGT | BPF_K:
2309                 case BPF_JMP32 | BPF_JLT | BPF_K:
2310                 case BPF_JMP32 | BPF_JGE | BPF_K:
2311                 case BPF_JMP32 | BPF_JLE | BPF_K:
2312                 case BPF_JMP32 | BPF_JSGT | BPF_K:
2313                 case BPF_JMP32 | BPF_JSLE | BPF_K:
2314                 case BPF_JMP32 | BPF_JSLT | BPF_K:
2315                 case BPF_JMP32 | BPF_JSGE | BPF_K: {
2316                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2317                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2318                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2319                         u8 sreg_lo = IA32_ECX;
2320                         u8 sreg_hi = IA32_EBX;
2321                         u32 hi;
2322
2323                         if (dstk) {
2324                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2325                                       STACK_VAR(dst_lo));
2326                                 if (is_jmp64)
2327                                         EMIT3(0x8B,
2328                                               add_2reg(0x40, IA32_EBP,
2329                                                        IA32_EDX),
2330                                               STACK_VAR(dst_hi));
2331                         }
2332
2333                         /* mov ecx,imm32 */
2334                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
2335                         if (is_jmp64) {
2336                                 hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2337                                 /* mov ebx,imm32 */
2338                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EBX), hi);
2339                                 /* cmp dreg_hi,sreg_hi */
2340                                 EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2341                                 EMIT2(IA32_JNE, 2);
2342                         }
2343                         /* cmp dreg_lo,sreg_lo */
2344                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2345
2346 emit_cond_jmp:          jmp_cond = get_cond_jmp_opcode(BPF_OP(code), false);
2347                         if (jmp_cond == COND_JMP_OPCODE_INVALID)
2348                                 return -EFAULT;
2349                         jmp_offset = addrs[i + insn->off] - addrs[i];
2350                         if (is_imm8(jmp_offset)) {
2351                                 EMIT2(jmp_cond, jmp_offset);
2352                         } else if (is_simm32(jmp_offset)) {
2353                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2354                         } else {
2355                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2356                                 return -EFAULT;
2357                         }
2358                         break;
2359                 }
2360                 case BPF_JMP | BPF_JSGT | BPF_K:
2361                 case BPF_JMP | BPF_JSLE | BPF_K:
2362                 case BPF_JMP | BPF_JSLT | BPF_K:
2363                 case BPF_JMP | BPF_JSGE | BPF_K: {
2364                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2365                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2366                         u8 sreg_lo = IA32_ECX;
2367                         u8 sreg_hi = IA32_EBX;
2368                         u32 hi;
2369
2370                         if (dstk) {
2371                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2372                                       STACK_VAR(dst_lo));
2373                                 EMIT3(0x8B,
2374                                       add_2reg(0x40, IA32_EBP,
2375                                                IA32_EDX),
2376                                       STACK_VAR(dst_hi));
2377                         }
2378
2379                         /* mov ecx,imm32 */
2380                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
2381                         hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2382                         /* mov ebx,imm32 */
2383                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EBX), hi);
2384                         /* cmp dreg_hi,sreg_hi */
2385                         EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2386                         EMIT2(IA32_JNE, 10);
2387                         /* cmp dreg_lo,sreg_lo */
2388                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2389
2390                         /*
2391                          * For simplicity of branch offset computation,
2392                          * let's use fixed jump coding here.
2393                          */
2394 emit_cond_jmp_signed:   /* Check the condition for low 32-bit comparison */
2395                         jmp_cond = get_cond_jmp_opcode(BPF_OP(code), true);
2396                         if (jmp_cond == COND_JMP_OPCODE_INVALID)
2397                                 return -EFAULT;
2398                         jmp_offset = addrs[i + insn->off] - addrs[i] + 8;
2399                         if (is_simm32(jmp_offset)) {
2400                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2401                         } else {
2402                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2403                                 return -EFAULT;
2404                         }
2405                         EMIT2(0xEB, 6);
2406
2407                         /* Check the condition for high 32-bit comparison */
2408                         jmp_cond = get_cond_jmp_opcode(BPF_OP(code), false);
2409                         if (jmp_cond == COND_JMP_OPCODE_INVALID)
2410                                 return -EFAULT;
2411                         jmp_offset = addrs[i + insn->off] - addrs[i];
2412                         if (is_simm32(jmp_offset)) {
2413                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2414                         } else {
2415                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2416                                 return -EFAULT;
2417                         }
2418                         break;
2419                 }
2420                 case BPF_JMP | BPF_JA:
2421                         if (insn->off == -1)
2422                                 /* -1 jmp instructions will always jump
2423                                  * backwards two bytes. Explicitly handling
2424                                  * this case avoids wasting too many passes
2425                                  * when there are long sequences of replaced
2426                                  * dead code.
2427                                  */
2428                                 jmp_offset = -2;
2429                         else
2430                                 jmp_offset = addrs[i + insn->off] - addrs[i];
2431
2432                         if (!jmp_offset)
2433                                 /* Optimize out nop jumps */
2434                                 break;
2435 emit_jmp:
2436                         if (is_imm8(jmp_offset)) {
2437                                 EMIT2(0xEB, jmp_offset);
2438                         } else if (is_simm32(jmp_offset)) {
2439                                 EMIT1_off32(0xE9, jmp_offset);
2440                         } else {
2441                                 pr_err("jmp gen bug %llx\n", jmp_offset);
2442                                 return -EFAULT;
2443                         }
2444                         break;
2445                 case BPF_STX | BPF_ATOMIC | BPF_W:
2446                 case BPF_STX | BPF_ATOMIC | BPF_DW:
2447                         goto notyet;
2448                 case BPF_JMP | BPF_EXIT:
2449                         if (seen_exit) {
2450                                 jmp_offset = ctx->cleanup_addr - addrs[i];
2451                                 goto emit_jmp;
2452                         }
2453                         seen_exit = true;
2454                         /* Update cleanup_addr */
2455                         ctx->cleanup_addr = proglen;
2456                         emit_epilogue(&prog, bpf_prog->aux->stack_depth);
2457                         break;
2458 notyet:
2459                         pr_info_once("*** NOT YET: opcode %02x ***\n", code);
2460                         return -EFAULT;
2461                 default:
2462                         /*
2463                          * This error will be seen if new instruction was added
2464                          * to interpreter, but not to JIT or if there is junk in
2465                          * bpf_prog
2466                          */
2467                         pr_err("bpf_jit: unknown opcode %02x\n", code);
2468                         return -EINVAL;
2469                 }
2470
2471                 ilen = prog - temp;
2472                 if (ilen > BPF_MAX_INSN_SIZE) {
2473                         pr_err("bpf_jit: fatal insn size error\n");
2474                         return -EFAULT;
2475                 }
2476
2477                 if (image) {
2478                         /*
2479                          * When populating the image, assert that:
2480                          *
2481                          *  i) We do not write beyond the allocated space, and
2482                          * ii) addrs[i] did not change from the prior run, in order
2483                          *     to validate assumptions made for computing branch
2484                          *     displacements.
2485                          */
2486                         if (unlikely(proglen + ilen > oldproglen ||
2487                                      proglen + ilen != addrs[i])) {
2488                                 pr_err("bpf_jit: fatal error\n");
2489                                 return -EFAULT;
2490                         }
2491                         memcpy(image + proglen, temp, ilen);
2492                 }
2493                 proglen += ilen;
2494                 addrs[i] = proglen;
2495                 prog = temp;
2496         }
2497         return proglen;
2498 }
2499
2500 bool bpf_jit_needs_zext(void)
2501 {
2502         return true;
2503 }
2504
2505 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
2506 {
2507         struct bpf_binary_header *header = NULL;
2508         struct bpf_prog *tmp, *orig_prog = prog;
2509         int proglen, oldproglen = 0;
2510         struct jit_context ctx = {};
2511         bool tmp_blinded = false;
2512         u8 *image = NULL;
2513         int *addrs;
2514         int pass;
2515         int i;
2516
2517         if (!prog->jit_requested)
2518                 return orig_prog;
2519
2520         tmp = bpf_jit_blind_constants(prog);
2521         /*
2522          * If blinding was requested and we failed during blinding,
2523          * we must fall back to the interpreter.
2524          */
2525         if (IS_ERR(tmp))
2526                 return orig_prog;
2527         if (tmp != prog) {
2528                 tmp_blinded = true;
2529                 prog = tmp;
2530         }
2531
2532         addrs = kmalloc_array(prog->len, sizeof(*addrs), GFP_KERNEL);
2533         if (!addrs) {
2534                 prog = orig_prog;
2535                 goto out;
2536         }
2537
2538         /*
2539          * Before first pass, make a rough estimation of addrs[]
2540          * each BPF instruction is translated to less than 64 bytes
2541          */
2542         for (proglen = 0, i = 0; i < prog->len; i++) {
2543                 proglen += 64;
2544                 addrs[i] = proglen;
2545         }
2546         ctx.cleanup_addr = proglen;
2547
2548         /*
2549          * JITed image shrinks with every pass and the loop iterates
2550          * until the image stops shrinking. Very large BPF programs
2551          * may converge on the last pass. In such case do one more
2552          * pass to emit the final image.
2553          */
2554         for (pass = 0; pass < 20 || image; pass++) {
2555                 proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
2556                 if (proglen <= 0) {
2557 out_image:
2558                         image = NULL;
2559                         if (header)
2560                                 bpf_jit_binary_free(header);
2561                         prog = orig_prog;
2562                         goto out_addrs;
2563                 }
2564                 if (image) {
2565                         if (proglen != oldproglen) {
2566                                 pr_err("bpf_jit: proglen=%d != oldproglen=%d\n",
2567                                        proglen, oldproglen);
2568                                 goto out_image;
2569                         }
2570                         break;
2571                 }
2572                 if (proglen == oldproglen) {
2573                         header = bpf_jit_binary_alloc(proglen, &image,
2574                                                       1, jit_fill_hole);
2575                         if (!header) {
2576                                 prog = orig_prog;
2577                                 goto out_addrs;
2578                         }
2579                 }
2580                 oldproglen = proglen;
2581                 cond_resched();
2582         }
2583
2584         if (bpf_jit_enable > 1)
2585                 bpf_jit_dump(prog->len, proglen, pass + 1, image);
2586
2587         if (image) {
2588                 bpf_jit_binary_lock_ro(header);
2589                 prog->bpf_func = (void *)image;
2590                 prog->jited = 1;
2591                 prog->jited_len = proglen;
2592         } else {
2593                 prog = orig_prog;
2594         }
2595
2596 out_addrs:
2597         kfree(addrs);
2598 out:
2599         if (tmp_blinded)
2600                 bpf_jit_prog_release_other(prog, prog == orig_prog ?
2601                                            tmp : orig_prog);
2602         return prog;
2603 }
2604
2605 bool bpf_jit_supports_kfunc_call(void)
2606 {
2607         return true;
2608 }