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         static int jmp_label1 = -1;
 736         static int jmp_label2 = -1;
 737         static int jmp_label3 = -1;
 738         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
 739         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
 740
 741         if (dstk) {
 742                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
 743                       STACK_VAR(dst_lo));
 744                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
 745                       STACK_VAR(dst_hi));
 746         }
 747
 748         if (sstk)
 749                 /* mov ecx,dword ptr [ebp+off] */
 750                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
 751                       STACK_VAR(src_lo));
 752         else
 753                 /* mov ecx,src_lo */
 754                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_ECX));
 755
 756         /* cmp ecx,32 */
 757         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 32);
 758         /* Jumps when >= 32 */
 759         if (is_imm8(jmp_label(jmp_label1, 2)))
 760                 EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));
 761         else
 762                 EMIT2_off32(0x0F, IA32_JAE + 0x10, jmp_label(jmp_label1, 6));
 763
 764         /* < 32 */
 765         /* shl dreg_hi,cl */
 766         EMIT2(0xD3, add_1reg(0xE0, dreg_hi));
 767         /* mov ebx,dreg_lo */
 768         EMIT2(0x8B, add_2reg(0xC0, dreg_lo, IA32_EBX));
 769         /* shl dreg_lo,cl */
 770         EMIT2(0xD3, add_1reg(0xE0, dreg_lo));
 771
 772         /* IA32_ECX = -IA32_ECX + 32 */
 773         /* neg ecx */
 774         EMIT2(0xF7, add_1reg(0xD8, IA32_ECX));
 775         /* add ecx,32 */
 776         EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 32);
 777
 778         /* shr ebx,cl */
 779         EMIT2(0xD3, add_1reg(0xE8, IA32_EBX));
 780         /* or dreg_hi,ebx */
 781         EMIT2(0x09, add_2reg(0xC0, dreg_hi, IA32_EBX));
 782
 783         /* goto out; */
 784         if (is_imm8(jmp_label(jmp_label3, 2)))
 785                 EMIT2(0xEB, jmp_label(jmp_label3, 2));
 786         else
 787                 EMIT1_off32(0xE9, jmp_label(jmp_label3, 5));
 788
 789         /* >= 32 */
 790         if (jmp_label1 == -1)
 791                 jmp_label1 = cnt;
 792
 793         /* cmp ecx,64 */
 794         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 64);
 795         /* Jumps when >= 64 */
 796         if (is_imm8(jmp_label(jmp_label2, 2)))
 797                 EMIT2(IA32_JAE, jmp_label(jmp_label2, 2));
 798         else
 799                 EMIT2_off32(0x0F, IA32_JAE + 0x10, jmp_label(jmp_label2, 6));
 800
 801         /* >= 32 && < 64 */
 802         /* sub ecx,32 */
 803         EMIT3(0x83, add_1reg(0xE8, IA32_ECX), 32);
 804         /* shl dreg_lo,cl */
 805         EMIT2(0xD3, add_1reg(0xE0, dreg_lo));
 806         /* mov dreg_hi,dreg_lo */
 807         EMIT2(0x89, add_2reg(0xC0, dreg_hi, dreg_lo));
 808
 809         /* xor dreg_lo,dreg_lo */
 810         EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
 811
 812         /* goto out; */
 813         if (is_imm8(jmp_label(jmp_label3, 2)))
 814                 EMIT2(0xEB, jmp_label(jmp_label3, 2));
 815         else
 816                 EMIT1_off32(0xE9, jmp_label(jmp_label3, 5));
 817
 818         /* >= 64 */
 819         if (jmp_label2 == -1)
 820                 jmp_label2 = cnt;
 821         /* xor dreg_lo,dreg_lo */
 822         EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
 823         /* xor dreg_hi,dreg_hi */
 824         EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
 825
 826         if (jmp_label3 == -1)
 827                 jmp_label3 = cnt;
 828
 829         if (dstk) {
 830                 /* mov dword ptr [ebp+off],dreg_lo */
 831                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
 832                       STACK_VAR(dst_lo));
 833                 /* mov dword ptr [ebp+off],dreg_hi */
 834                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
 835                       STACK_VAR(dst_hi));
 836         }
 837         /* out: */
 838         *pprog = prog;
 839 }
 840
 841 /* dst = dst >> src (signed)*/
 842 static inline void emit_ia32_arsh_r64(const u8 dst[], const u8 src[],
 843                                       bool dstk, bool sstk, u8 **pprog)
 844 {
 845         u8 *prog = *pprog;
 846         int cnt = 0;
 847         static int jmp_label1 = -1;
 848         static int jmp_label2 = -1;
 849         static int jmp_label3 = -1;
 850         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
 851         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
 852
 853         if (dstk) {
 854                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
 855                       STACK_VAR(dst_lo));
 856                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
 857                       STACK_VAR(dst_hi));
 858         }
 859
 860         if (sstk)
 861                 /* mov ecx,dword ptr [ebp+off] */
 862                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
 863                       STACK_VAR(src_lo));
 864         else
 865                 /* mov ecx,src_lo */
 866                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_ECX));
 867
 868         /* cmp ecx,32 */
 869         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 32);
 870         /* Jumps when >= 32 */
 871         if (is_imm8(jmp_label(jmp_label1, 2)))
 872                 EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));
 873         else
 874                 EMIT2_off32(0x0F, IA32_JAE + 0x10, jmp_label(jmp_label1, 6));
 875
 876         /* < 32 */
 877         /* lshr dreg_lo,cl */
 878         EMIT2(0xD3, add_1reg(0xE8, dreg_lo));
 879         /* mov ebx,dreg_hi */
 880         EMIT2(0x8B, add_2reg(0xC0, dreg_hi, IA32_EBX));
 881         /* ashr dreg_hi,cl */
 882         EMIT2(0xD3, add_1reg(0xF8, dreg_hi));
 883
 884         /* IA32_ECX = -IA32_ECX + 32 */
 885         /* neg ecx */
 886         EMIT2(0xF7, add_1reg(0xD8, IA32_ECX));
 887         /* add ecx,32 */
 888         EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 32);
 889
 890         /* shl ebx,cl */
 891         EMIT2(0xD3, add_1reg(0xE0, IA32_EBX));
 892         /* or dreg_lo,ebx */
 893         EMIT2(0x09, add_2reg(0xC0, dreg_lo, IA32_EBX));
 894
 895         /* goto out; */
 896         if (is_imm8(jmp_label(jmp_label3, 2)))
 897                 EMIT2(0xEB, jmp_label(jmp_label3, 2));
 898         else
 899                 EMIT1_off32(0xE9, jmp_label(jmp_label3, 5));
 900
 901         /* >= 32 */
 902         if (jmp_label1 == -1)
 903                 jmp_label1 = cnt;
 904
 905         /* cmp ecx,64 */
 906         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 64);
 907         /* Jumps when >= 64 */
 908         if (is_imm8(jmp_label(jmp_label2, 2)))
 909                 EMIT2(IA32_JAE, jmp_label(jmp_label2, 2));
 910         else
 911                 EMIT2_off32(0x0F, IA32_JAE + 0x10, jmp_label(jmp_label2, 6));
 912
 913         /* >= 32 && < 64 */
 914         /* sub ecx,32 */
 915         EMIT3(0x83, add_1reg(0xE8, IA32_ECX), 32);
 916         /* ashr dreg_hi,cl */
 917         EMIT2(0xD3, add_1reg(0xF8, dreg_hi));
 918         /* mov dreg_lo,dreg_hi */
 919         EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
 920
 921         /* ashr dreg_hi,imm8 */
 922         EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
 923
 924         /* goto out; */
 925         if (is_imm8(jmp_label(jmp_label3, 2)))
 926                 EMIT2(0xEB, jmp_label(jmp_label3, 2));
 927         else
 928                 EMIT1_off32(0xE9, jmp_label(jmp_label3, 5));
 929
 930         /* >= 64 */
 931         if (jmp_label2 == -1)
 932                 jmp_label2 = cnt;
 933         /* ashr dreg_hi,imm8 */
 934         EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
 935         /* mov dreg_lo,dreg_hi */
 936         EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
 937
 938         if (jmp_label3 == -1)
 939                 jmp_label3 = cnt;
 940
 941         if (dstk) {
 942                 /* mov dword ptr [ebp+off],dreg_lo */
 943                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
 944                       STACK_VAR(dst_lo));
 945                 /* mov dword ptr [ebp+off],dreg_hi */
 946                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
 947                       STACK_VAR(dst_hi));
 948         }
 949         /* out: */
 950         *pprog = prog;
 951 }
 952
 953 /* dst = dst >> src */
 954 static inline void emit_ia32_rsh_r64(const u8 dst[], const u8 src[], bool dstk,
 955                                      bool sstk, u8 **pprog)
 956 {
 957         u8 *prog = *pprog;
 958         int cnt = 0;
 959         static int jmp_label1 = -1;
 960         static int jmp_label2 = -1;
 961         static int jmp_label3 = -1;
 962         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
 963         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
 964
 965         if (dstk) {
 966                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
 967                       STACK_VAR(dst_lo));
 968                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
 969                       STACK_VAR(dst_hi));
 970         }
 971
 972         if (sstk)
 973                 /* mov ecx,dword ptr [ebp+off] */
 974                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
 975                       STACK_VAR(src_lo));
 976         else
 977                 /* mov ecx,src_lo */
 978                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_ECX));
 979
 980         /* cmp ecx,32 */
 981         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 32);
 982         /* Jumps when >= 32 */
 983         if (is_imm8(jmp_label(jmp_label1, 2)))
 984                 EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));
 985         else
 986                 EMIT2_off32(0x0F, IA32_JAE + 0x10, jmp_label(jmp_label1, 6));
 987
 988         /* < 32 */
 989         /* lshr dreg_lo,cl */
 990         EMIT2(0xD3, add_1reg(0xE8, dreg_lo));
 991         /* mov ebx,dreg_hi */
 992         EMIT2(0x8B, add_2reg(0xC0, dreg_hi, IA32_EBX));
 993         /* shr dreg_hi,cl */
 994         EMIT2(0xD3, add_1reg(0xE8, dreg_hi));
 995
 996         /* IA32_ECX = -IA32_ECX + 32 */
 997         /* neg ecx */
 998         EMIT2(0xF7, add_1reg(0xD8, IA32_ECX));
 999         /* add ecx,32 */
1000         EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 32);
1001
1002         /* shl ebx,cl */
1003         EMIT2(0xD3, add_1reg(0xE0, IA32_EBX));
1004         /* or dreg_lo,ebx */
1005         EMIT2(0x09, add_2reg(0xC0, dreg_lo, IA32_EBX));
1006
1007         /* goto out; */
1008         if (is_imm8(jmp_label(jmp_label3, 2)))
1009                 EMIT2(0xEB, jmp_label(jmp_label3, 2));
1010         else
1011                 EMIT1_off32(0xE9, jmp_label(jmp_label3, 5));
1012
1013         /* >= 32 */
1014         if (jmp_label1 == -1)
1015                 jmp_label1 = cnt;
1016         /* cmp ecx,64 */
1017         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), 64);
1018         /* Jumps when >= 64 */
1019         if (is_imm8(jmp_label(jmp_label2, 2)))
1020                 EMIT2(IA32_JAE, jmp_label(jmp_label2, 2));
1021         else
1022                 EMIT2_off32(0x0F, IA32_JAE + 0x10, jmp_label(jmp_label2, 6));
1023
1024         /* >= 32 && < 64 */
1025         /* sub ecx,32 */
1026         EMIT3(0x83, add_1reg(0xE8, IA32_ECX), 32);
1027         /* shr dreg_hi,cl */
1028         EMIT2(0xD3, add_1reg(0xE8, dreg_hi));
1029         /* mov dreg_lo,dreg_hi */
1030         EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
1031         /* xor dreg_hi,dreg_hi */
1032         EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
1033
1034         /* goto out; */
1035         if (is_imm8(jmp_label(jmp_label3, 2)))
1036                 EMIT2(0xEB, jmp_label(jmp_label3, 2));
1037         else
1038                 EMIT1_off32(0xE9, jmp_label(jmp_label3, 5));
1039
1040         /* >= 64 */
1041         if (jmp_label2 == -1)
1042                 jmp_label2 = cnt;
1043         /* xor dreg_lo,dreg_lo */
1044         EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
1045         /* xor dreg_hi,dreg_hi */
1046         EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
1047
1048         if (jmp_label3 == -1)
1049                 jmp_label3 = cnt;
1050
1051         if (dstk) {
1052                 /* mov dword ptr [ebp+off],dreg_lo */
1053                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
1054                       STACK_VAR(dst_lo));
1055                 /* mov dword ptr [ebp+off],dreg_hi */
1056                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
1057                       STACK_VAR(dst_hi));
1058         }
1059         /* out: */
1060         *pprog = prog;
1061 }
1062
1063 /* dst = dst << val */
1064 static inline void emit_ia32_lsh_i64(const u8 dst[], const u32 val,
1065                                      bool dstk, u8 **pprog)
1066 {
1067         u8 *prog = *pprog;
1068         int cnt = 0;
1069         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
1070         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
1071
1072         if (dstk) {
1073                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1074                       STACK_VAR(dst_lo));
1075                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1076                       STACK_VAR(dst_hi));
1077         }
1078         /* Do LSH operation */
1079         if (val < 32) {
1080                 /* shl dreg_hi,imm8 */
1081                 EMIT3(0xC1, add_1reg(0xE0, dreg_hi), val);
1082                 /* mov ebx,dreg_lo */
1083                 EMIT2(0x8B, add_2reg(0xC0, dreg_lo, IA32_EBX));
1084                 /* shl dreg_lo,imm8 */
1085                 EMIT3(0xC1, add_1reg(0xE0, dreg_lo), val);
1086
1087                 /* IA32_ECX = 32 - val */
1088                 /* mov ecx,val */
1089                 EMIT2(0xB1, val);
1090                 /* movzx ecx,ecx */
1091                 EMIT3(0x0F, 0xB6, add_2reg(0xC0, IA32_ECX, IA32_ECX));
1092                 /* neg ecx */
1093                 EMIT2(0xF7, add_1reg(0xD8, IA32_ECX));
1094                 /* add ecx,32 */
1095                 EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 32);
1096
1097                 /* shr ebx,cl */
1098                 EMIT2(0xD3, add_1reg(0xE8, IA32_EBX));
1099                 /* or dreg_hi,ebx */
1100                 EMIT2(0x09, add_2reg(0xC0, dreg_hi, IA32_EBX));
1101         } else if (val >= 32 && val < 64) {
1102                 u32 value = val - 32;
1103
1104                 /* shl dreg_lo,imm8 */
1105                 EMIT3(0xC1, add_1reg(0xE0, dreg_lo), value);
1106                 /* mov dreg_hi,dreg_lo */
1107                 EMIT2(0x89, add_2reg(0xC0, dreg_hi, dreg_lo));
1108                 /* xor dreg_lo,dreg_lo */
1109                 EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
1110         } else {
1111                 /* xor dreg_lo,dreg_lo */
1112                 EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
1113                 /* xor dreg_hi,dreg_hi */
1114                 EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
1115         }
1116
1117         if (dstk) {
1118                 /* mov dword ptr [ebp+off],dreg_lo */
1119                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
1120                       STACK_VAR(dst_lo));
1121                 /* mov dword ptr [ebp+off],dreg_hi */
1122                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
1123                       STACK_VAR(dst_hi));
1124         }
1125         *pprog = prog;
1126 }
1127
1128 /* dst = dst >> val */
1129 static inline void emit_ia32_rsh_i64(const u8 dst[], const u32 val,
1130                                      bool dstk, u8 **pprog)
1131 {
1132         u8 *prog = *pprog;
1133         int cnt = 0;
1134         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
1135         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
1136
1137         if (dstk) {
1138                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1139                       STACK_VAR(dst_lo));
1140                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1141                       STACK_VAR(dst_hi));
1142         }
1143
1144         /* Do RSH operation */
1145         if (val < 32) {
1146                 /* shr dreg_lo,imm8 */
1147                 EMIT3(0xC1, add_1reg(0xE8, dreg_lo), val);
1148                 /* mov ebx,dreg_hi */
1149                 EMIT2(0x8B, add_2reg(0xC0, dreg_hi, IA32_EBX));
1150                 /* shr dreg_hi,imm8 */
1151                 EMIT3(0xC1, add_1reg(0xE8, dreg_hi), val);
1152
1153                 /* IA32_ECX = 32 - val */
1154                 /* mov ecx,val */
1155                 EMIT2(0xB1, val);
1156                 /* movzx ecx,ecx */
1157                 EMIT3(0x0F, 0xB6, add_2reg(0xC0, IA32_ECX, IA32_ECX));
1158                 /* neg ecx */
1159                 EMIT2(0xF7, add_1reg(0xD8, IA32_ECX));
1160                 /* add ecx,32 */
1161                 EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 32);
1162
1163                 /* shl ebx,cl */
1164                 EMIT2(0xD3, add_1reg(0xE0, IA32_EBX));
1165                 /* or dreg_lo,ebx */
1166                 EMIT2(0x09, add_2reg(0xC0, dreg_lo, IA32_EBX));
1167         } else if (val >= 32 && val < 64) {
1168                 u32 value = val - 32;
1169
1170                 /* shr dreg_hi,imm8 */
1171                 EMIT3(0xC1, add_1reg(0xE8, dreg_hi), value);
1172                 /* mov dreg_lo,dreg_hi */
1173                 EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
1174                 /* xor dreg_hi,dreg_hi */
1175                 EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
1176         } else {
1177                 /* xor dreg_lo,dreg_lo */
1178                 EMIT2(0x33, add_2reg(0xC0, dreg_lo, dreg_lo));
1179                 /* xor dreg_hi,dreg_hi */
1180                 EMIT2(0x33, add_2reg(0xC0, dreg_hi, dreg_hi));
1181         }
1182
1183         if (dstk) {
1184                 /* mov dword ptr [ebp+off],dreg_lo */
1185                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
1186                       STACK_VAR(dst_lo));
1187                 /* mov dword ptr [ebp+off],dreg_hi */
1188                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
1189                       STACK_VAR(dst_hi));
1190         }
1191         *pprog = prog;
1192 }
1193
1194 /* dst = dst >> val (signed) */
1195 static inline void emit_ia32_arsh_i64(const u8 dst[], const u32 val,
1196                                       bool dstk, u8 **pprog)
1197 {
1198         u8 *prog = *pprog;
1199         int cnt = 0;
1200         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
1201         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
1202
1203         if (dstk) {
1204                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1205                       STACK_VAR(dst_lo));
1206                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1207                       STACK_VAR(dst_hi));
1208         }
1209         /* Do RSH operation */
1210         if (val < 32) {
1211                 /* shr dreg_lo,imm8 */
1212                 EMIT3(0xC1, add_1reg(0xE8, dreg_lo), val);
1213                 /* mov ebx,dreg_hi */
1214                 EMIT2(0x8B, add_2reg(0xC0, dreg_hi, IA32_EBX));
1215                 /* ashr dreg_hi,imm8 */
1216                 EMIT3(0xC1, add_1reg(0xF8, dreg_hi), val);
1217
1218                 /* IA32_ECX = 32 - val */
1219                 /* mov ecx,val */
1220                 EMIT2(0xB1, val);
1221                 /* movzx ecx,ecx */
1222                 EMIT3(0x0F, 0xB6, add_2reg(0xC0, IA32_ECX, IA32_ECX));
1223                 /* neg ecx */
1224                 EMIT2(0xF7, add_1reg(0xD8, IA32_ECX));
1225                 /* add ecx,32 */
1226                 EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 32);
1227
1228                 /* shl ebx,cl */
1229                 EMIT2(0xD3, add_1reg(0xE0, IA32_EBX));
1230                 /* or dreg_lo,ebx */
1231                 EMIT2(0x09, add_2reg(0xC0, dreg_lo, IA32_EBX));
1232         } else if (val >= 32 && val < 64) {
1233                 u32 value = val - 32;
1234
1235                 /* ashr dreg_hi,imm8 */
1236                 EMIT3(0xC1, add_1reg(0xF8, dreg_hi), value);
1237                 /* mov dreg_lo,dreg_hi */
1238                 EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
1239
1240                 /* ashr dreg_hi,imm8 */
1241                 EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
1242         } else {
1243                 /* ashr dreg_hi,imm8 */
1244                 EMIT3(0xC1, add_1reg(0xF8, dreg_hi), 31);
1245                 /* mov dreg_lo,dreg_hi */
1246                 EMIT2(0x89, add_2reg(0xC0, dreg_lo, dreg_hi));
1247         }
1248
1249         if (dstk) {
1250                 /* mov dword ptr [ebp+off],dreg_lo */
1251                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_lo),
1252                       STACK_VAR(dst_lo));
1253                 /* mov dword ptr [ebp+off],dreg_hi */
1254                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, dreg_hi),
1255                       STACK_VAR(dst_hi));
1256         }
1257         *pprog = prog;
1258 }
1259
1260 static inline void emit_ia32_mul_r64(const u8 dst[], const u8 src[], bool dstk,
1261                                      bool sstk, u8 **pprog)
1262 {
1263         u8 *prog = *pprog;
1264         int cnt = 0;
1265
1266         if (dstk)
1267                 /* mov eax,dword ptr [ebp+off] */
1268                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1269                       STACK_VAR(dst_hi));
1270         else
1271                 /* mov eax,dst_hi */
1272                 EMIT2(0x8B, add_2reg(0xC0, dst_hi, IA32_EAX));
1273
1274         if (sstk)
1275                 /* mul dword ptr [ebp+off] */
1276                 EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(src_lo));
1277         else
1278                 /* mul src_lo */
1279                 EMIT2(0xF7, add_1reg(0xE0, src_lo));
1280
1281         /* mov ecx,eax */
1282         EMIT2(0x89, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1283
1284         if (dstk)
1285                 /* mov eax,dword ptr [ebp+off] */
1286                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1287                       STACK_VAR(dst_lo));
1288         else
1289                 /* mov eax,dst_lo */
1290                 EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1291
1292         if (sstk)
1293                 /* mul dword ptr [ebp+off] */
1294                 EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(src_hi));
1295         else
1296                 /* mul src_hi */
1297                 EMIT2(0xF7, add_1reg(0xE0, src_hi));
1298
1299         /* add eax,eax */
1300         EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1301
1302         if (dstk)
1303                 /* mov eax,dword ptr [ebp+off] */
1304                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1305                       STACK_VAR(dst_lo));
1306         else
1307                 /* mov eax,dst_lo */
1308                 EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1309
1310         if (sstk)
1311                 /* mul dword ptr [ebp+off] */
1312                 EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(src_lo));
1313         else
1314                 /* mul src_lo */
1315                 EMIT2(0xF7, add_1reg(0xE0, src_lo));
1316
1317         /* add ecx,edx */
1318         EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EDX));
1319
1320         if (dstk) {
1321                 /* mov dword ptr [ebp+off],eax */
1322                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
1323                       STACK_VAR(dst_lo));
1324                 /* mov dword ptr [ebp+off],ecx */
1325                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_ECX),
1326                       STACK_VAR(dst_hi));
1327         } else {
1328                 /* mov dst_lo,eax */
1329                 EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EAX));
1330                 /* mov dst_hi,ecx */
1331                 EMIT2(0x89, add_2reg(0xC0, dst_hi, IA32_ECX));
1332         }
1333
1334         *pprog = prog;
1335 }
1336
1337 static inline void emit_ia32_mul_i64(const u8 dst[], const u32 val,
1338                                      bool dstk, u8 **pprog)
1339 {
1340         u8 *prog = *pprog;
1341         int cnt = 0;
1342         u32 hi;
1343
1344         hi = val & (1<<31) ? (u32)~0 : 0;
1345         /* movl eax,imm32 */
1346         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EAX), val);
1347         if (dstk)
1348                 /* mul dword ptr [ebp+off] */
1349                 EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(dst_hi));
1350         else
1351                 /* mul dst_hi */
1352                 EMIT2(0xF7, add_1reg(0xE0, dst_hi));
1353
1354         /* mov ecx,eax */
1355         EMIT2(0x89, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1356
1357         /* movl eax,imm32 */
1358         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EAX), hi);
1359         if (dstk)
1360                 /* mul dword ptr [ebp+off] */
1361                 EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(dst_lo));
1362         else
1363                 /* mul dst_lo */
1364                 EMIT2(0xF7, add_1reg(0xE0, dst_lo));
1365         /* add ecx,eax */
1366         EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EAX));
1367
1368         /* movl eax,imm32 */
1369         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EAX), val);
1370         if (dstk)
1371                 /* mul dword ptr [ebp+off] */
1372                 EMIT3(0xF7, add_1reg(0x60, IA32_EBP), STACK_VAR(dst_lo));
1373         else
1374                 /* mul dst_lo */
1375                 EMIT2(0xF7, add_1reg(0xE0, dst_lo));
1376
1377         /* add ecx,edx */
1378         EMIT2(0x01, add_2reg(0xC0, IA32_ECX, IA32_EDX));
1379
1380         if (dstk) {
1381                 /* mov dword ptr [ebp+off],eax */
1382                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
1383                       STACK_VAR(dst_lo));
1384                 /* mov dword ptr [ebp+off],ecx */
1385                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_ECX),
1386                       STACK_VAR(dst_hi));
1387         } else {
1388                 /* mov dword ptr [ebp+off],eax */
1389                 EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EAX));
1390                 /* mov dword ptr [ebp+off],ecx */
1391                 EMIT2(0x89, add_2reg(0xC0, dst_hi, IA32_ECX));
1392         }
1393
1394         *pprog = prog;
1395 }
1396
1397 static int bpf_size_to_x86_bytes(int bpf_size)
1398 {
1399         if (bpf_size == BPF_W)
1400                 return 4;
1401         else if (bpf_size == BPF_H)
1402                 return 2;
1403         else if (bpf_size == BPF_B)
1404                 return 1;
1405         else if (bpf_size == BPF_DW)
1406                 return 4; /* imm32 */
1407         else
1408                 return 0;
1409 }
1410
1411 struct jit_context {
1412         int cleanup_addr; /* Epilogue code offset */
1413 };
1414
1415 /* Maximum number of bytes emitted while JITing one eBPF insn */
1416 #define BPF_MAX_INSN_SIZE       128
1417 #define BPF_INSN_SAFETY         64
1418
1419 #define PROLOGUE_SIZE 35
1420
1421 /*
1422  * Emit prologue code for BPF program and check it's size.
1423  * bpf_tail_call helper will skip it while jumping into another program.
1424  */
1425 static void emit_prologue(u8 **pprog, u32 stack_depth)
1426 {
1427         u8 *prog = *pprog;
1428         int cnt = 0;
1429         const u8 *r1 = bpf2ia32[BPF_REG_1];
1430         const u8 fplo = bpf2ia32[BPF_REG_FP][0];
1431         const u8 fphi = bpf2ia32[BPF_REG_FP][1];
1432         const u8 *tcc = bpf2ia32[TCALL_CNT];
1433
1434         /* push ebp */
1435         EMIT1(0x55);
1436         /* mov ebp,esp */
1437         EMIT2(0x89, 0xE5);
1438         /* push edi */
1439         EMIT1(0x57);
1440         /* push esi */
1441         EMIT1(0x56);
1442         /* push ebx */
1443         EMIT1(0x53);
1444
1445         /* sub esp,STACK_SIZE */
1446         EMIT2_off32(0x81, 0xEC, STACK_SIZE);
1447         /* sub ebp,SCRATCH_SIZE+12*/
1448         EMIT3(0x83, add_1reg(0xE8, IA32_EBP), SCRATCH_SIZE + 12);
1449         /* xor ebx,ebx */
1450         EMIT2(0x31, add_2reg(0xC0, IA32_EBX, IA32_EBX));
1451
1452         /* Set up BPF prog stack base register */
1453         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBP), STACK_VAR(fplo));
1454         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(fphi));
1455
1456         /* Move BPF_CTX (EAX) to BPF_REG_R1 */
1457         /* mov dword ptr [ebp+off],eax */
1458         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r1[0]));
1459         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(r1[1]));
1460
1461         /* Initialize Tail Count */
1462         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[0]));
1463         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[1]));
1464
1465         BUILD_BUG_ON(cnt != PROLOGUE_SIZE);
1466         *pprog = prog;
1467 }
1468
1469 /* Emit epilogue code for BPF program */
1470 static void emit_epilogue(u8 **pprog, u32 stack_depth)
1471 {
1472         u8 *prog = *pprog;
1473         const u8 *r0 = bpf2ia32[BPF_REG_0];
1474         int cnt = 0;
1475
1476         /* mov eax,dword ptr [ebp+off]*/
1477         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r0[0]));
1478         /* mov edx,dword ptr [ebp+off]*/
1479         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX), STACK_VAR(r0[1]));
1480
1481         /* add ebp,SCRATCH_SIZE+12*/
1482         EMIT3(0x83, add_1reg(0xC0, IA32_EBP), SCRATCH_SIZE + 12);
1483
1484         /* mov ebx,dword ptr [ebp-12]*/
1485         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EBX), -12);
1486         /* mov esi,dword ptr [ebp-8]*/
1487         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ESI), -8);
1488         /* mov edi,dword ptr [ebp-4]*/
1489         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDI), -4);
1490
1491         EMIT1(0xC9); /* leave */
1492         EMIT1(0xC3); /* ret */
1493         *pprog = prog;
1494 }
1495
1496 /*
1497  * Generate the following code:
1498  * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ...
1499  *   if (index >= array->map.max_entries)
1500  *     goto out;
1501  *   if (++tail_call_cnt > MAX_TAIL_CALL_CNT)
1502  *     goto out;
1503  *   prog = array->ptrs[index];
1504  *   if (prog == NULL)
1505  *     goto out;
1506  *   goto *(prog->bpf_func + prologue_size);
1507  * out:
1508  */
1509 static void emit_bpf_tail_call(u8 **pprog)
1510 {
1511         u8 *prog = *pprog;
1512         int cnt = 0;
1513         const u8 *r1 = bpf2ia32[BPF_REG_1];
1514         const u8 *r2 = bpf2ia32[BPF_REG_2];
1515         const u8 *r3 = bpf2ia32[BPF_REG_3];
1516         const u8 *tcc = bpf2ia32[TCALL_CNT];
1517         u32 lo, hi;
1518         static int jmp_label1 = -1;
1519
1520         /*
1521          * if (index >= array->map.max_entries)
1522          *     goto out;
1523          */
1524         /* mov eax,dword ptr [ebp+off] */
1525         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r2[0]));
1526         /* mov edx,dword ptr [ebp+off] */
1527         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX), STACK_VAR(r3[0]));
1528
1529         /* cmp dword ptr [eax+off],edx */
1530         EMIT3(0x39, add_2reg(0x40, IA32_EAX, IA32_EDX),
1531               offsetof(struct bpf_array, map.max_entries));
1532         /* jbe out */
1533         EMIT2(IA32_JBE, jmp_label(jmp_label1, 2));
1534
1535         /*
1536          * if (tail_call_cnt > MAX_TAIL_CALL_CNT)
1537          *     goto out;
1538          */
1539         lo = (u32)MAX_TAIL_CALL_CNT;
1540         hi = (u32)((u64)MAX_TAIL_CALL_CNT >> 32);
1541         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(tcc[0]));
1542         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[1]));
1543
1544         /* cmp edx,hi */
1545         EMIT3(0x83, add_1reg(0xF8, IA32_EBX), hi);
1546         EMIT2(IA32_JNE, 3);
1547         /* cmp ecx,lo */
1548         EMIT3(0x83, add_1reg(0xF8, IA32_ECX), lo);
1549
1550         /* ja out */
1551         EMIT2(IA32_JAE, jmp_label(jmp_label1, 2));
1552
1553         /* add eax,0x1 */
1554         EMIT3(0x83, add_1reg(0xC0, IA32_ECX), 0x01);
1555         /* adc ebx,0x0 */
1556         EMIT3(0x83, add_1reg(0xD0, IA32_EBX), 0x00);
1557
1558         /* mov dword ptr [ebp+off],eax */
1559         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(tcc[0]));
1560         /* mov dword ptr [ebp+off],edx */
1561         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EBX), STACK_VAR(tcc[1]));
1562
1563         /* prog = array->ptrs[index]; */
1564         /* mov edx, [eax + edx * 4 + offsetof(...)] */
1565         EMIT3_off32(0x8B, 0x94, 0x90, offsetof(struct bpf_array, ptrs));
1566
1567         /*
1568          * if (prog == NULL)
1569          *     goto out;
1570          */
1571         /* test edx,edx */
1572         EMIT2(0x85, add_2reg(0xC0, IA32_EDX, IA32_EDX));
1573         /* je out */
1574         EMIT2(IA32_JE, jmp_label(jmp_label1, 2));
1575
1576         /* goto *(prog->bpf_func + prologue_size); */
1577         /* mov edx, dword ptr [edx + 32] */
1578         EMIT3(0x8B, add_2reg(0x40, IA32_EDX, IA32_EDX),
1579               offsetof(struct bpf_prog, bpf_func));
1580         /* add edx,prologue_size */
1581         EMIT3(0x83, add_1reg(0xC0, IA32_EDX), PROLOGUE_SIZE);
1582
1583         /* mov eax,dword ptr [ebp+off] */
1584         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX), STACK_VAR(r1[0]));
1585
1586         /*
1587          * Now we're ready to jump into next BPF program:
1588          * eax == ctx (1st arg)
1589          * edx == prog->bpf_func + prologue_size
1590          */
1591         RETPOLINE_EDX_BPF_JIT();
1592
1593         if (jmp_label1 == -1)
1594                 jmp_label1 = cnt;
1595
1596         /* out: */
1597         *pprog = prog;
1598 }
1599
1600 /* Push the scratch stack register on top of the stack. */
1601 static inline void emit_push_r64(const u8 src[], u8 **pprog)
1602 {
1603         u8 *prog = *pprog;
1604         int cnt = 0;
1605
1606         /* mov ecx,dword ptr [ebp+off] */
1607         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src_hi));
1608         /* push ecx */
1609         EMIT1(0x51);
1610
1611         /* mov ecx,dword ptr [ebp+off] */
1612         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX), STACK_VAR(src_lo));
1613         /* push ecx */
1614         EMIT1(0x51);
1615
1616         *pprog = prog;
1617 }
1618
1619 static u8 get_cond_jmp_opcode(const u8 op, bool is_cmp_lo)
1620 {
1621         u8 jmp_cond;
1622
1623         /* Convert BPF opcode to x86 */
1624         switch (op) {
1625         case BPF_JEQ:
1626                 jmp_cond = IA32_JE;
1627                 break;
1628         case BPF_JSET:
1629         case BPF_JNE:
1630                 jmp_cond = IA32_JNE;
1631                 break;
1632         case BPF_JGT:
1633                 /* GT is unsigned '>', JA in x86 */
1634                 jmp_cond = IA32_JA;
1635                 break;
1636         case BPF_JLT:
1637                 /* LT is unsigned '<', JB in x86 */
1638                 jmp_cond = IA32_JB;
1639                 break;
1640         case BPF_JGE:
1641                 /* GE is unsigned '>=', JAE in x86 */
1642                 jmp_cond = IA32_JAE;
1643                 break;
1644         case BPF_JLE:
1645                 /* LE is unsigned '<=', JBE in x86 */
1646                 jmp_cond = IA32_JBE;
1647                 break;
1648         case BPF_JSGT:
1649                 if (!is_cmp_lo)
1650                         /* Signed '>', GT in x86 */
1651                         jmp_cond = IA32_JG;
1652                 else
1653                         /* GT is unsigned '>', JA in x86 */
1654                         jmp_cond = IA32_JA;
1655                 break;
1656         case BPF_JSLT:
1657                 if (!is_cmp_lo)
1658                         /* Signed '<', LT in x86 */
1659                         jmp_cond = IA32_JL;
1660                 else
1661                         /* LT is unsigned '<', JB in x86 */
1662                         jmp_cond = IA32_JB;
1663                 break;
1664         case BPF_JSGE:
1665                 if (!is_cmp_lo)
1666                         /* Signed '>=', GE in x86 */
1667                         jmp_cond = IA32_JGE;
1668                 else
1669                         /* GE is unsigned '>=', JAE in x86 */
1670                         jmp_cond = IA32_JAE;
1671                 break;
1672         case BPF_JSLE:
1673                 if (!is_cmp_lo)
1674                         /* Signed '<=', LE in x86 */
1675                         jmp_cond = IA32_JLE;
1676                 else
1677                         /* LE is unsigned '<=', JBE in x86 */
1678                         jmp_cond = IA32_JBE;
1679                 break;
1680         default: /* to silence GCC warning */
1681                 jmp_cond = COND_JMP_OPCODE_INVALID;
1682                 break;
1683         }
1684
1685         return jmp_cond;
1686 }
1687
1688 static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
1689                   int oldproglen, struct jit_context *ctx)
1690 {
1691         struct bpf_insn *insn = bpf_prog->insnsi;
1692         int insn_cnt = bpf_prog->len;
1693         bool seen_exit = false;
1694         u8 temp[BPF_MAX_INSN_SIZE + BPF_INSN_SAFETY];
1695         int i, cnt = 0;
1696         int proglen = 0;
1697         u8 *prog = temp;
1698
1699         emit_prologue(&prog, bpf_prog->aux->stack_depth);
1700
1701         for (i = 0; i < insn_cnt; i++, insn++) {
1702                 const s32 imm32 = insn->imm;
1703                 const bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
1704                 const bool dstk = insn->dst_reg == BPF_REG_AX ? false : true;
1705                 const bool sstk = insn->src_reg == BPF_REG_AX ? false : true;
1706                 const u8 code = insn->code;
1707                 const u8 *dst = bpf2ia32[insn->dst_reg];
1708                 const u8 *src = bpf2ia32[insn->src_reg];
1709                 const u8 *r0 = bpf2ia32[BPF_REG_0];
1710                 s64 jmp_offset;
1711                 u8 jmp_cond;
1712                 int ilen;
1713                 u8 *func;
1714
1715                 switch (code) {
1716                 /* ALU operations */
1717                 /* dst = src */
1718                 case BPF_ALU | BPF_MOV | BPF_K:
1719                 case BPF_ALU | BPF_MOV | BPF_X:
1720                 case BPF_ALU64 | BPF_MOV | BPF_K:
1721                 case BPF_ALU64 | BPF_MOV | BPF_X:
1722                         switch (BPF_SRC(code)) {
1723                         case BPF_X:
1724                                 if (imm32 == 1) {
1725                                         /* Special mov32 for zext. */
1726                                         emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1727                                         break;
1728                                 }
1729                                 emit_ia32_mov_r64(is64, dst, src, dstk, sstk,
1730                                                   &prog, bpf_prog->aux);
1731                                 break;
1732                         case BPF_K:
1733                                 /* Sign-extend immediate value to dst reg */
1734                                 emit_ia32_mov_i64(is64, dst, imm32,
1735                                                   dstk, &prog);
1736                                 break;
1737                         }
1738                         break;
1739                 /* dst = dst + src/imm */
1740                 /* dst = dst - src/imm */
1741                 /* dst = dst | src/imm */
1742                 /* dst = dst & src/imm */
1743                 /* dst = dst ^ src/imm */
1744                 /* dst = dst * src/imm */
1745                 /* dst = dst << src */
1746                 /* dst = dst >> src */
1747                 case BPF_ALU | BPF_ADD | BPF_K:
1748                 case BPF_ALU | BPF_ADD | BPF_X:
1749                 case BPF_ALU | BPF_SUB | BPF_K:
1750                 case BPF_ALU | BPF_SUB | BPF_X:
1751                 case BPF_ALU | BPF_OR | BPF_K:
1752                 case BPF_ALU | BPF_OR | BPF_X:
1753                 case BPF_ALU | BPF_AND | BPF_K:
1754                 case BPF_ALU | BPF_AND | BPF_X:
1755                 case BPF_ALU | BPF_XOR | BPF_K:
1756                 case BPF_ALU | BPF_XOR | BPF_X:
1757                 case BPF_ALU64 | BPF_ADD | BPF_K:
1758                 case BPF_ALU64 | BPF_ADD | BPF_X:
1759                 case BPF_ALU64 | BPF_SUB | BPF_K:
1760                 case BPF_ALU64 | BPF_SUB | BPF_X:
1761                 case BPF_ALU64 | BPF_OR | BPF_K:
1762                 case BPF_ALU64 | BPF_OR | BPF_X:
1763                 case BPF_ALU64 | BPF_AND | BPF_K:
1764                 case BPF_ALU64 | BPF_AND | BPF_X:
1765                 case BPF_ALU64 | BPF_XOR | BPF_K:
1766                 case BPF_ALU64 | BPF_XOR | BPF_X:
1767                         switch (BPF_SRC(code)) {
1768                         case BPF_X:
1769                                 emit_ia32_alu_r64(is64, BPF_OP(code), dst,
1770                                                   src, dstk, sstk, &prog,
1771                                                   bpf_prog->aux);
1772                                 break;
1773                         case BPF_K:
1774                                 emit_ia32_alu_i64(is64, BPF_OP(code), dst,
1775                                                   imm32, dstk, &prog,
1776                                                   bpf_prog->aux);
1777                                 break;
1778                         }
1779                         break;
1780                 case BPF_ALU | BPF_MUL | BPF_K:
1781                 case BPF_ALU | BPF_MUL | BPF_X:
1782                         switch (BPF_SRC(code)) {
1783                         case BPF_X:
1784                                 emit_ia32_mul_r(dst_lo, src_lo, dstk,
1785                                                 sstk, &prog);
1786                                 break;
1787                         case BPF_K:
1788                                 /* mov ecx,imm32*/
1789                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1790                                             imm32);
1791                                 emit_ia32_mul_r(dst_lo, IA32_ECX, dstk,
1792                                                 false, &prog);
1793                                 break;
1794                         }
1795                         if (!bpf_prog->aux->verifier_zext)
1796                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1797                         break;
1798                 case BPF_ALU | BPF_LSH | BPF_X:
1799                 case BPF_ALU | BPF_RSH | BPF_X:
1800                 case BPF_ALU | BPF_ARSH | BPF_K:
1801                 case BPF_ALU | BPF_ARSH | BPF_X:
1802                         switch (BPF_SRC(code)) {
1803                         case BPF_X:
1804                                 emit_ia32_shift_r(BPF_OP(code), dst_lo, src_lo,
1805                                                   dstk, sstk, &prog);
1806                                 break;
1807                         case BPF_K:
1808                                 /* mov ecx,imm32*/
1809                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1810                                             imm32);
1811                                 emit_ia32_shift_r(BPF_OP(code), dst_lo,
1812                                                   IA32_ECX, dstk, false,
1813                                                   &prog);
1814                                 break;
1815                         }
1816                         if (!bpf_prog->aux->verifier_zext)
1817                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1818                         break;
1819                 /* dst = dst / src(imm) */
1820                 /* dst = dst % src(imm) */
1821                 case BPF_ALU | BPF_DIV | BPF_K:
1822                 case BPF_ALU | BPF_DIV | BPF_X:
1823                 case BPF_ALU | BPF_MOD | BPF_K:
1824                 case BPF_ALU | BPF_MOD | BPF_X:
1825                         switch (BPF_SRC(code)) {
1826                         case BPF_X:
1827                                 emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
1828                                                     src_lo, dstk, sstk, &prog);
1829                                 break;
1830                         case BPF_K:
1831                                 /* mov ecx,imm32*/
1832                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
1833                                             imm32);
1834                                 emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
1835                                                     IA32_ECX, dstk, false,
1836                                                     &prog);
1837                                 break;
1838                         }
1839                         if (!bpf_prog->aux->verifier_zext)
1840                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1841                         break;
1842                 case BPF_ALU64 | BPF_DIV | BPF_K:
1843                 case BPF_ALU64 | BPF_DIV | BPF_X:
1844                 case BPF_ALU64 | BPF_MOD | BPF_K:
1845                 case BPF_ALU64 | BPF_MOD | BPF_X:
1846                         goto notyet;
1847                 /* dst = dst >> imm */
1848                 /* dst = dst << imm */
1849                 case BPF_ALU | BPF_RSH | BPF_K:
1850                 case BPF_ALU | BPF_LSH | BPF_K:
1851                         if (unlikely(imm32 > 31))
1852                                 return -EINVAL;
1853                         /* mov ecx,imm32*/
1854                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
1855                         emit_ia32_shift_r(BPF_OP(code), dst_lo, IA32_ECX, dstk,
1856                                           false, &prog);
1857                         if (!bpf_prog->aux->verifier_zext)
1858                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1859                         break;
1860                 /* dst = dst << imm */
1861                 case BPF_ALU64 | BPF_LSH | BPF_K:
1862                         if (unlikely(imm32 > 63))
1863                                 return -EINVAL;
1864                         emit_ia32_lsh_i64(dst, imm32, dstk, &prog);
1865                         break;
1866                 /* dst = dst >> imm */
1867                 case BPF_ALU64 | BPF_RSH | BPF_K:
1868                         if (unlikely(imm32 > 63))
1869                                 return -EINVAL;
1870                         emit_ia32_rsh_i64(dst, imm32, dstk, &prog);
1871                         break;
1872                 /* dst = dst << src */
1873                 case BPF_ALU64 | BPF_LSH | BPF_X:
1874                         emit_ia32_lsh_r64(dst, src, dstk, sstk, &prog);
1875                         break;
1876                 /* dst = dst >> src */
1877                 case BPF_ALU64 | BPF_RSH | BPF_X:
1878                         emit_ia32_rsh_r64(dst, src, dstk, sstk, &prog);
1879                         break;
1880                 /* dst = dst >> src (signed) */
1881                 case BPF_ALU64 | BPF_ARSH | BPF_X:
1882                         emit_ia32_arsh_r64(dst, src, dstk, sstk, &prog);
1883                         break;
1884                 /* dst = dst >> imm (signed) */
1885                 case BPF_ALU64 | BPF_ARSH | BPF_K:
1886                         if (unlikely(imm32 > 63))
1887                                 return -EINVAL;
1888                         emit_ia32_arsh_i64(dst, imm32, dstk, &prog);
1889                         break;
1890                 /* dst = ~dst */
1891                 case BPF_ALU | BPF_NEG:
1892                         emit_ia32_alu_i(is64, false, BPF_OP(code),
1893                                         dst_lo, 0, dstk, &prog);
1894                         if (!bpf_prog->aux->verifier_zext)
1895                                 emit_ia32_mov_i(dst_hi, 0, dstk, &prog);
1896                         break;
1897                 /* dst = ~dst (64 bit) */
1898                 case BPF_ALU64 | BPF_NEG:
1899                         emit_ia32_neg64(dst, dstk, &prog);
1900                         break;
1901                 /* dst = dst * src/imm */
1902                 case BPF_ALU64 | BPF_MUL | BPF_X:
1903                 case BPF_ALU64 | BPF_MUL | BPF_K:
1904                         switch (BPF_SRC(code)) {
1905                         case BPF_X:
1906                                 emit_ia32_mul_r64(dst, src, dstk, sstk, &prog);
1907                                 break;
1908                         case BPF_K:
1909                                 emit_ia32_mul_i64(dst, imm32, dstk, &prog);
1910                                 break;
1911                         }
1912                         break;
1913                 /* dst = htole(dst) */
1914                 case BPF_ALU | BPF_END | BPF_FROM_LE:
1915                         emit_ia32_to_le_r64(dst, imm32, dstk, &prog,
1916                                             bpf_prog->aux);
1917                         break;
1918                 /* dst = htobe(dst) */
1919                 case BPF_ALU | BPF_END | BPF_FROM_BE:
1920                         emit_ia32_to_be_r64(dst, imm32, dstk, &prog,
1921                                             bpf_prog->aux);
1922                         break;
1923                 /* dst = imm64 */
1924                 case BPF_LD | BPF_IMM | BPF_DW: {
1925                         s32 hi, lo = imm32;
1926
1927                         hi = insn[1].imm;
1928                         emit_ia32_mov_i(dst_lo, lo, dstk, &prog);
1929                         emit_ia32_mov_i(dst_hi, hi, dstk, &prog);
1930                         insn++;
1931                         i++;
1932                         break;
1933                 }
1934                 /* ST: *(u8*)(dst_reg + off) = imm */
1935                 case BPF_ST | BPF_MEM | BPF_H:
1936                 case BPF_ST | BPF_MEM | BPF_B:
1937                 case BPF_ST | BPF_MEM | BPF_W:
1938                 case BPF_ST | BPF_MEM | BPF_DW:
1939                         if (dstk)
1940                                 /* mov eax,dword ptr [ebp+off] */
1941                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1942                                       STACK_VAR(dst_lo));
1943                         else
1944                                 /* mov eax,dst_lo */
1945                                 EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1946
1947                         switch (BPF_SIZE(code)) {
1948                         case BPF_B:
1949                                 EMIT(0xC6, 1); break;
1950                         case BPF_H:
1951                                 EMIT2(0x66, 0xC7); break;
1952                         case BPF_W:
1953                         case BPF_DW:
1954                                 EMIT(0xC7, 1); break;
1955                         }
1956
1957                         if (is_imm8(insn->off))
1958                                 EMIT2(add_1reg(0x40, IA32_EAX), insn->off);
1959                         else
1960                                 EMIT1_off32(add_1reg(0x80, IA32_EAX),
1961                                             insn->off);
1962                         EMIT(imm32, bpf_size_to_x86_bytes(BPF_SIZE(code)));
1963
1964                         if (BPF_SIZE(code) == BPF_DW) {
1965                                 u32 hi;
1966
1967                                 hi = imm32 & (1<<31) ? (u32)~0 : 0;
1968                                 EMIT2_off32(0xC7, add_1reg(0x80, IA32_EAX),
1969                                             insn->off + 4);
1970                                 EMIT(hi, 4);
1971                         }
1972                         break;
1973
1974                 /* STX: *(u8*)(dst_reg + off) = src_reg */
1975                 case BPF_STX | BPF_MEM | BPF_B:
1976                 case BPF_STX | BPF_MEM | BPF_H:
1977                 case BPF_STX | BPF_MEM | BPF_W:
1978                 case BPF_STX | BPF_MEM | BPF_DW:
1979                         if (dstk)
1980                                 /* mov eax,dword ptr [ebp+off] */
1981                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
1982                                       STACK_VAR(dst_lo));
1983                         else
1984                                 /* mov eax,dst_lo */
1985                                 EMIT2(0x8B, add_2reg(0xC0, dst_lo, IA32_EAX));
1986
1987                         if (sstk)
1988                                 /* mov edx,dword ptr [ebp+off] */
1989                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
1990                                       STACK_VAR(src_lo));
1991                         else
1992                                 /* mov edx,src_lo */
1993                                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_EDX));
1994
1995                         switch (BPF_SIZE(code)) {
1996                         case BPF_B:
1997                                 EMIT(0x88, 1); break;
1998                         case BPF_H:
1999                                 EMIT2(0x66, 0x89); break;
2000                         case BPF_W:
2001                         case BPF_DW:
2002                                 EMIT(0x89, 1); break;
2003                         }
2004
2005                         if (is_imm8(insn->off))
2006                                 EMIT2(add_2reg(0x40, IA32_EAX, IA32_EDX),
2007                                       insn->off);
2008                         else
2009                                 EMIT1_off32(add_2reg(0x80, IA32_EAX, IA32_EDX),
2010                                             insn->off);
2011
2012                         if (BPF_SIZE(code) == BPF_DW) {
2013                                 if (sstk)
2014                                         /* mov edi,dword ptr [ebp+off] */
2015                                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP,
2016                                                              IA32_EDX),
2017                                               STACK_VAR(src_hi));
2018                                 else
2019                                         /* mov edi,src_hi */
2020                                         EMIT2(0x8B, add_2reg(0xC0, src_hi,
2021                                                              IA32_EDX));
2022                                 EMIT1(0x89);
2023                                 if (is_imm8(insn->off + 4)) {
2024                                         EMIT2(add_2reg(0x40, IA32_EAX,
2025                                                        IA32_EDX),
2026                                               insn->off + 4);
2027                                 } else {
2028                                         EMIT1(add_2reg(0x80, IA32_EAX,
2029                                                        IA32_EDX));
2030                                         EMIT(insn->off + 4, 4);
2031                                 }
2032                         }
2033                         break;
2034
2035                 /* LDX: dst_reg = *(u8*)(src_reg + off) */
2036                 case BPF_LDX | BPF_MEM | BPF_B:
2037                 case BPF_LDX | BPF_MEM | BPF_H:
2038                 case BPF_LDX | BPF_MEM | BPF_W:
2039                 case BPF_LDX | BPF_MEM | BPF_DW:
2040                         if (sstk)
2041                                 /* mov eax,dword ptr [ebp+off] */
2042                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2043                                       STACK_VAR(src_lo));
2044                         else
2045                                 /* mov eax,dword ptr [ebp+off] */
2046                                 EMIT2(0x8B, add_2reg(0xC0, src_lo, IA32_EAX));
2047
2048                         switch (BPF_SIZE(code)) {
2049                         case BPF_B:
2050                                 EMIT2(0x0F, 0xB6); break;
2051                         case BPF_H:
2052                                 EMIT2(0x0F, 0xB7); break;
2053                         case BPF_W:
2054                         case BPF_DW:
2055                                 EMIT(0x8B, 1); break;
2056                         }
2057
2058                         if (is_imm8(insn->off))
2059                                 EMIT2(add_2reg(0x40, IA32_EAX, IA32_EDX),
2060                                       insn->off);
2061                         else
2062                                 EMIT1_off32(add_2reg(0x80, IA32_EAX, IA32_EDX),
2063                                             insn->off);
2064
2065                         if (dstk)
2066                                 /* mov dword ptr [ebp+off],edx */
2067                                 EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
2068                                       STACK_VAR(dst_lo));
2069                         else
2070                                 /* mov dst_lo,edx */
2071                                 EMIT2(0x89, add_2reg(0xC0, dst_lo, IA32_EDX));
2072                         switch (BPF_SIZE(code)) {
2073                         case BPF_B:
2074                         case BPF_H:
2075                         case BPF_W:
2076                                 if (!bpf_prog->aux->verifier_zext)
2077                                         break;
2078                                 if (dstk) {
2079                                         EMIT3(0xC7, add_1reg(0x40, IA32_EBP),
2080                                               STACK_VAR(dst_hi));
2081                                         EMIT(0x0, 4);
2082                                 } else {
2083                                         EMIT3(0xC7, add_1reg(0xC0, dst_hi), 0);
2084                                 }
2085                                 break;
2086                         case BPF_DW:
2087                                 EMIT2_off32(0x8B,
2088                                             add_2reg(0x80, IA32_EAX, IA32_EDX),
2089                                             insn->off + 4);
2090                                 if (dstk)
2091                                         EMIT3(0x89,
2092                                               add_2reg(0x40, IA32_EBP,
2093                                                        IA32_EDX),
2094                                               STACK_VAR(dst_hi));
2095                                 else
2096                                         EMIT2(0x89,
2097                                               add_2reg(0xC0, dst_hi, IA32_EDX));
2098                                 break;
2099                         default:
2100                                 break;
2101                         }
2102                         break;
2103                 /* call */
2104                 case BPF_JMP | BPF_CALL:
2105                 {
2106                         const u8 *r1 = bpf2ia32[BPF_REG_1];
2107                         const u8 *r2 = bpf2ia32[BPF_REG_2];
2108                         const u8 *r3 = bpf2ia32[BPF_REG_3];
2109                         const u8 *r4 = bpf2ia32[BPF_REG_4];
2110                         const u8 *r5 = bpf2ia32[BPF_REG_5];
2111
2112                         if (insn->src_reg == BPF_PSEUDO_CALL)
2113                                 goto notyet;
2114
2115                         func = (u8 *) __bpf_call_base + imm32;
2116                         jmp_offset = func - (image + addrs[i]);
2117
2118                         if (!imm32 || !is_simm32(jmp_offset)) {
2119                                 pr_err("unsupported BPF func %d addr %p image %p\n",
2120                                        imm32, func, image);
2121                                 return -EINVAL;
2122                         }
2123
2124                         /* mov eax,dword ptr [ebp+off] */
2125                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2126                               STACK_VAR(r1[0]));
2127                         /* mov edx,dword ptr [ebp+off] */
2128                         EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EDX),
2129                               STACK_VAR(r1[1]));
2130
2131                         emit_push_r64(r5, &prog);
2132                         emit_push_r64(r4, &prog);
2133                         emit_push_r64(r3, &prog);
2134                         emit_push_r64(r2, &prog);
2135
2136                         EMIT1_off32(0xE8, jmp_offset + 9);
2137
2138                         /* mov dword ptr [ebp+off],eax */
2139                         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EAX),
2140                               STACK_VAR(r0[0]));
2141                         /* mov dword ptr [ebp+off],edx */
2142                         EMIT3(0x89, add_2reg(0x40, IA32_EBP, IA32_EDX),
2143                               STACK_VAR(r0[1]));
2144
2145                         /* add esp,32 */
2146                         EMIT3(0x83, add_1reg(0xC0, IA32_ESP), 32);
2147                         break;
2148                 }
2149                 case BPF_JMP | BPF_TAIL_CALL:
2150                         emit_bpf_tail_call(&prog);
2151                         break;
2152
2153                 /* cond jump */
2154                 case BPF_JMP | BPF_JEQ | BPF_X:
2155                 case BPF_JMP | BPF_JNE | BPF_X:
2156                 case BPF_JMP | BPF_JGT | BPF_X:
2157                 case BPF_JMP | BPF_JLT | BPF_X:
2158                 case BPF_JMP | BPF_JGE | BPF_X:
2159                 case BPF_JMP | BPF_JLE | BPF_X:
2160                 case BPF_JMP32 | BPF_JEQ | BPF_X:
2161                 case BPF_JMP32 | BPF_JNE | BPF_X:
2162                 case BPF_JMP32 | BPF_JGT | BPF_X:
2163                 case BPF_JMP32 | BPF_JLT | BPF_X:
2164                 case BPF_JMP32 | BPF_JGE | BPF_X:
2165                 case BPF_JMP32 | BPF_JLE | BPF_X:
2166                 case BPF_JMP32 | BPF_JSGT | BPF_X:
2167                 case BPF_JMP32 | BPF_JSLE | BPF_X:
2168                 case BPF_JMP32 | BPF_JSLT | BPF_X:
2169                 case BPF_JMP32 | BPF_JSGE | BPF_X: {
2170                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2171                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2172                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2173                         u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2174                         u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2175
2176                         if (dstk) {
2177                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2178                                       STACK_VAR(dst_lo));
2179                                 if (is_jmp64)
2180                                         EMIT3(0x8B,
2181                                               add_2reg(0x40, IA32_EBP,
2182                                                        IA32_EDX),
2183                                               STACK_VAR(dst_hi));
2184                         }
2185
2186                         if (sstk) {
2187                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2188                                       STACK_VAR(src_lo));
2189                                 if (is_jmp64)
2190                                         EMIT3(0x8B,
2191                                               add_2reg(0x40, IA32_EBP,
2192                                                        IA32_EBX),
2193                                               STACK_VAR(src_hi));
2194                         }
2195
2196                         if (is_jmp64) {
2197                                 /* cmp dreg_hi,sreg_hi */
2198                                 EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2199                                 EMIT2(IA32_JNE, 2);
2200                         }
2201                         /* cmp dreg_lo,sreg_lo */
2202                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2203                         goto emit_cond_jmp;
2204                 }
2205                 case BPF_JMP | BPF_JSGT | BPF_X:
2206                 case BPF_JMP | BPF_JSLE | BPF_X:
2207                 case BPF_JMP | BPF_JSLT | BPF_X:
2208                 case BPF_JMP | BPF_JSGE | BPF_X: {
2209                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2210                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2211                         u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2212                         u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2213
2214                         if (dstk) {
2215                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2216                                       STACK_VAR(dst_lo));
2217                                 EMIT3(0x8B,
2218                                       add_2reg(0x40, IA32_EBP,
2219                                                IA32_EDX),
2220                                       STACK_VAR(dst_hi));
2221                         }
2222
2223                         if (sstk) {
2224                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2225                                       STACK_VAR(src_lo));
2226                                 EMIT3(0x8B,
2227                                       add_2reg(0x40, IA32_EBP,
2228                                                IA32_EBX),
2229                                       STACK_VAR(src_hi));
2230                         }
2231
2232                         /* cmp dreg_hi,sreg_hi */
2233                         EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2234                         EMIT2(IA32_JNE, 10);
2235                         /* cmp dreg_lo,sreg_lo */
2236                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2237                         goto emit_cond_jmp_signed;
2238                 }
2239                 case BPF_JMP | BPF_JSET | BPF_X:
2240                 case BPF_JMP32 | BPF_JSET | BPF_X: {
2241                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2242                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2243                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2244                         u8 sreg_lo = sstk ? IA32_ECX : src_lo;
2245                         u8 sreg_hi = sstk ? IA32_EBX : src_hi;
2246
2247                         if (dstk) {
2248                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2249                                       STACK_VAR(dst_lo));
2250                                 if (is_jmp64)
2251                                         EMIT3(0x8B,
2252                                               add_2reg(0x40, IA32_EBP,
2253                                                        IA32_EDX),
2254                                               STACK_VAR(dst_hi));
2255                         }
2256
2257                         if (sstk) {
2258                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_ECX),
2259                                       STACK_VAR(src_lo));
2260                                 if (is_jmp64)
2261                                         EMIT3(0x8B,
2262                                               add_2reg(0x40, IA32_EBP,
2263                                                        IA32_EBX),
2264                                               STACK_VAR(src_hi));
2265                         }
2266                         /* and dreg_lo,sreg_lo */
2267                         EMIT2(0x23, add_2reg(0xC0, sreg_lo, dreg_lo));
2268                         /* and dreg_hi,sreg_hi */
2269                         EMIT2(0x23, add_2reg(0xC0, sreg_hi, dreg_hi));
2270                         /* or dreg_lo,dreg_hi */
2271                         EMIT2(0x09, add_2reg(0xC0, dreg_lo, dreg_hi));
2272                         goto emit_cond_jmp;
2273                 }
2274                 case BPF_JMP | BPF_JSET | BPF_K:
2275                 case BPF_JMP32 | BPF_JSET | BPF_K: {
2276                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2277                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2278                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2279                         u8 sreg_lo = IA32_ECX;
2280                         u8 sreg_hi = IA32_EBX;
2281                         u32 hi;
2282
2283                         if (dstk) {
2284                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2285                                       STACK_VAR(dst_lo));
2286                                 if (is_jmp64)
2287                                         EMIT3(0x8B,
2288                                               add_2reg(0x40, IA32_EBP,
2289                                                        IA32_EDX),
2290                                               STACK_VAR(dst_hi));
2291                         }
2292
2293                         /* mov ecx,imm32 */
2294                         EMIT2_off32(0xC7, add_1reg(0xC0, sreg_lo), imm32);
2295
2296                         /* and dreg_lo,sreg_lo */
2297                         EMIT2(0x23, add_2reg(0xC0, sreg_lo, dreg_lo));
2298                         if (is_jmp64) {
2299                                 hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2300                                 /* mov ebx,imm32 */
2301                                 EMIT2_off32(0xC7, add_1reg(0xC0, sreg_hi), hi);
2302                                 /* and dreg_hi,sreg_hi */
2303                                 EMIT2(0x23, add_2reg(0xC0, sreg_hi, dreg_hi));
2304                                 /* or dreg_lo,dreg_hi */
2305                                 EMIT2(0x09, add_2reg(0xC0, dreg_lo, dreg_hi));
2306                         }
2307                         goto emit_cond_jmp;
2308                 }
2309                 case BPF_JMP | BPF_JEQ | BPF_K:
2310                 case BPF_JMP | BPF_JNE | BPF_K:
2311                 case BPF_JMP | BPF_JGT | BPF_K:
2312                 case BPF_JMP | BPF_JLT | BPF_K:
2313                 case BPF_JMP | BPF_JGE | BPF_K:
2314                 case BPF_JMP | BPF_JLE | BPF_K:
2315                 case BPF_JMP32 | BPF_JEQ | BPF_K:
2316                 case BPF_JMP32 | BPF_JNE | BPF_K:
2317                 case BPF_JMP32 | BPF_JGT | BPF_K:
2318                 case BPF_JMP32 | BPF_JLT | BPF_K:
2319                 case BPF_JMP32 | BPF_JGE | BPF_K:
2320                 case BPF_JMP32 | BPF_JLE | BPF_K:
2321                 case BPF_JMP32 | BPF_JSGT | BPF_K:
2322                 case BPF_JMP32 | BPF_JSLE | BPF_K:
2323                 case BPF_JMP32 | BPF_JSLT | BPF_K:
2324                 case BPF_JMP32 | BPF_JSGE | BPF_K: {
2325                         bool is_jmp64 = BPF_CLASS(insn->code) == BPF_JMP;
2326                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2327                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2328                         u8 sreg_lo = IA32_ECX;
2329                         u8 sreg_hi = IA32_EBX;
2330                         u32 hi;
2331
2332                         if (dstk) {
2333                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2334                                       STACK_VAR(dst_lo));
2335                                 if (is_jmp64)
2336                                         EMIT3(0x8B,
2337                                               add_2reg(0x40, IA32_EBP,
2338                                                        IA32_EDX),
2339                                               STACK_VAR(dst_hi));
2340                         }
2341
2342                         /* mov ecx,imm32 */
2343                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
2344                         if (is_jmp64) {
2345                                 hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2346                                 /* mov ebx,imm32 */
2347                                 EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EBX), hi);
2348                                 /* cmp dreg_hi,sreg_hi */
2349                                 EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2350                                 EMIT2(IA32_JNE, 2);
2351                         }
2352                         /* cmp dreg_lo,sreg_lo */
2353                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2354
2355 emit_cond_jmp:          jmp_cond = get_cond_jmp_opcode(BPF_OP(code), false);
2356                         if (jmp_cond == COND_JMP_OPCODE_INVALID)
2357                                 return -EFAULT;
2358                         jmp_offset = addrs[i + insn->off] - addrs[i];
2359                         if (is_imm8(jmp_offset)) {
2360                                 EMIT2(jmp_cond, jmp_offset);
2361                         } else if (is_simm32(jmp_offset)) {
2362                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2363                         } else {
2364                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2365                                 return -EFAULT;
2366                         }
2367                         break;
2368                 }
2369                 case BPF_JMP | BPF_JSGT | BPF_K:
2370                 case BPF_JMP | BPF_JSLE | BPF_K:
2371                 case BPF_JMP | BPF_JSLT | BPF_K:
2372                 case BPF_JMP | BPF_JSGE | BPF_K: {
2373                         u8 dreg_lo = dstk ? IA32_EAX : dst_lo;
2374                         u8 dreg_hi = dstk ? IA32_EDX : dst_hi;
2375                         u8 sreg_lo = IA32_ECX;
2376                         u8 sreg_hi = IA32_EBX;
2377                         u32 hi;
2378
2379                         if (dstk) {
2380                                 EMIT3(0x8B, add_2reg(0x40, IA32_EBP, IA32_EAX),
2381                                       STACK_VAR(dst_lo));
2382                                 EMIT3(0x8B,
2383                                       add_2reg(0x40, IA32_EBP,
2384                                                IA32_EDX),
2385                                       STACK_VAR(dst_hi));
2386                         }
2387
2388                         /* mov ecx,imm32 */
2389                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX), imm32);
2390                         hi = imm32 & (1 << 31) ? (u32)~0 : 0;
2391                         /* mov ebx,imm32 */
2392                         EMIT2_off32(0xC7, add_1reg(0xC0, IA32_EBX), hi);
2393                         /* cmp dreg_hi,sreg_hi */
2394                         EMIT2(0x39, add_2reg(0xC0, dreg_hi, sreg_hi));
2395                         EMIT2(IA32_JNE, 10);
2396                         /* cmp dreg_lo,sreg_lo */
2397                         EMIT2(0x39, add_2reg(0xC0, dreg_lo, sreg_lo));
2398
2399                         /*
2400                          * For simplicity of branch offset computation,
2401                          * let's use fixed jump coding here.
2402                          */
2403 emit_cond_jmp_signed:   /* Check the condition for low 32-bit comparison */
2404                         jmp_cond = get_cond_jmp_opcode(BPF_OP(code), true);
2405                         if (jmp_cond == COND_JMP_OPCODE_INVALID)
2406                                 return -EFAULT;
2407                         jmp_offset = addrs[i + insn->off] - addrs[i] + 8;
2408                         if (is_simm32(jmp_offset)) {
2409                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2410                         } else {
2411                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2412                                 return -EFAULT;
2413                         }
2414                         EMIT2(0xEB, 6);
2415
2416                         /* Check the condition for high 32-bit comparison */
2417                         jmp_cond = get_cond_jmp_opcode(BPF_OP(code), false);
2418                         if (jmp_cond == COND_JMP_OPCODE_INVALID)
2419                                 return -EFAULT;
2420                         jmp_offset = addrs[i + insn->off] - addrs[i];
2421                         if (is_simm32(jmp_offset)) {
2422                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
2423                         } else {
2424                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
2425                                 return -EFAULT;
2426                         }
2427                         break;
2428                 }
2429                 case BPF_JMP | BPF_JA:
2430                         if (insn->off == -1)
2431                                 /* -1 jmp instructions will always jump
2432                                  * backwards two bytes. Explicitly handling
2433                                  * this case avoids wasting too many passes
2434                                  * when there are long sequences of replaced
2435                                  * dead code.
2436                                  */
2437                                 jmp_offset = -2;
2438                         else
2439                                 jmp_offset = addrs[i + insn->off] - addrs[i];
2440
2441                         if (!jmp_offset)
2442                                 /* Optimize out nop jumps */
2443                                 break;
2444 emit_jmp:
2445                         if (is_imm8(jmp_offset)) {
2446                                 EMIT2(0xEB, jmp_offset);
2447                         } else if (is_simm32(jmp_offset)) {
2448                                 EMIT1_off32(0xE9, jmp_offset);
2449                         } else {
2450                                 pr_err("jmp gen bug %llx\n", jmp_offset);
2451                                 return -EFAULT;
2452                         }
2453                         break;
2454                 /* STX XADD: lock *(u32 *)(dst + off) += src */
2455                 case BPF_STX | BPF_XADD | BPF_W:
2456                 /* STX XADD: lock *(u64 *)(dst + off) += src */
2457                 case BPF_STX | BPF_XADD | BPF_DW:
2458                         goto notyet;
2459                 case BPF_JMP | BPF_EXIT:
2460                         if (seen_exit) {
2461                                 jmp_offset = ctx->cleanup_addr - addrs[i];
2462                                 goto emit_jmp;
2463                         }
2464                         seen_exit = true;
2465                         /* Update cleanup_addr */
2466                         ctx->cleanup_addr = proglen;
2467                         emit_epilogue(&prog, bpf_prog->aux->stack_depth);
2468                         break;
2469 notyet:
2470                         pr_info_once("*** NOT YET: opcode %02x ***\n", code);
2471                         return -EFAULT;
2472                 default:
2473                         /*
2474                          * This error will be seen if new instruction was added
2475                          * to interpreter, but not to JIT or if there is junk in
2476                          * bpf_prog
2477                          */
2478                         pr_err("bpf_jit: unknown opcode %02x\n", code);
2479                         return -EINVAL;
2480                 }
2481
2482                 ilen = prog - temp;
2483                 if (ilen > BPF_MAX_INSN_SIZE) {
2484                         pr_err("bpf_jit: fatal insn size error\n");
2485                         return -EFAULT;
2486                 }
2487
2488                 if (image) {
2489                         if (unlikely(proglen + ilen > oldproglen)) {
2490                                 pr_err("bpf_jit: fatal error\n");
2491                                 return -EFAULT;
2492                         }
2493                         memcpy(image + proglen, temp, ilen);
2494                 }
2495                 proglen += ilen;
2496                 addrs[i] = proglen;
2497                 prog = temp;
2498         }
2499         return proglen;
2500 }
2501
2502 bool bpf_jit_needs_zext(void)
2503 {
2504         return true;
2505 }
2506
2507 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
2508 {
2509         struct bpf_binary_header *header = NULL;
2510         struct bpf_prog *tmp, *orig_prog = prog;
2511         int proglen, oldproglen = 0;
2512         struct jit_context ctx = {};
2513         bool tmp_blinded = false;
2514         u8 *image = NULL;
2515         int *addrs;
2516         int pass;
2517         int i;
2518
2519         if (!prog->jit_requested)
2520                 return orig_prog;
2521
2522         tmp = bpf_jit_blind_constants(prog);
2523         /*
2524          * If blinding was requested and we failed during blinding,
2525          * we must fall back to the interpreter.
2526          */
2527         if (IS_ERR(tmp))
2528                 return orig_prog;
2529         if (tmp != prog) {
2530                 tmp_blinded = true;
2531                 prog = tmp;
2532         }
2533
2534         addrs = kmalloc_array(prog->len, sizeof(*addrs), GFP_KERNEL);
2535         if (!addrs) {
2536                 prog = orig_prog;
2537                 goto out;
2538         }
2539
2540         /*
2541          * Before first pass, make a rough estimation of addrs[]
2542          * each BPF instruction is translated to less than 64 bytes
2543          */
2544         for (proglen = 0, i = 0; i < prog->len; i++) {
2545                 proglen += 64;
2546                 addrs[i] = proglen;
2547         }
2548         ctx.cleanup_addr = proglen;
2549
2550         /*
2551          * JITed image shrinks with every pass and the loop iterates
2552          * until the image stops shrinking. Very large BPF programs
2553          * may converge on the last pass. In such case do one more
2554          * pass to emit the final image.
2555          */
2556         for (pass = 0; pass < 20 || image; pass++) {
2557                 proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
2558                 if (proglen <= 0) {
2559 out_image:
2560                         image = NULL;
2561                         if (header)
2562                                 bpf_jit_binary_free(header);
2563                         prog = orig_prog;
2564                         goto out_addrs;
2565                 }
2566                 if (image) {
2567                         if (proglen != oldproglen) {
2568                                 pr_err("bpf_jit: proglen=%d != oldproglen=%d\n",
2569                                        proglen, oldproglen);
2570                                 goto out_image;
2571                         }
2572                         break;
2573                 }
2574                 if (proglen == oldproglen) {
2575                         header = bpf_jit_binary_alloc(proglen, &image,
2576                                                       1, jit_fill_hole);
2577                         if (!header) {
2578                                 prog = orig_prog;
2579                                 goto out_addrs;
2580                         }
2581                 }
2582                 oldproglen = proglen;
2583                 cond_resched();
2584         }
2585
2586         if (bpf_jit_enable > 1)
2587                 bpf_jit_dump(prog->len, proglen, pass + 1, image);
2588
2589         if (image) {
2590                 bpf_jit_binary_lock_ro(header);
2591                 prog->bpf_func = (void *)image;
2592                 prog->jited = 1;
2593                 prog->jited_len = proglen;
2594         } else {
2595                 prog = orig_prog;
2596         }
2597
2598 out_addrs:
2599         kfree(addrs);
2600 out:
2601         if (tmp_blinded)
2602                 bpf_jit_prog_release_other(prog, prog == orig_prog ?
2603                                            tmp : orig_prog);
2604         return prog;
2605 }