GNU Linux-libre 4.14.266-gnu1
[releases.git] / arch / x86 / net / bpf_jit_comp.c
1 /* bpf_jit_comp.c : BPF JIT compiler
2  *
3  * Copyright (C) 2011-2013 Eric Dumazet (eric.dumazet@gmail.com)
4  * Internal BPF Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; version 2
9  * of the License.
10  */
11 #include <linux/netdevice.h>
12 #include <linux/filter.h>
13 #include <linux/if_vlan.h>
14 #include <asm/cacheflush.h>
15 #include <asm/set_memory.h>
16 #include <asm/nospec-branch.h>
17 #include <linux/bpf.h>
18
19 /*
20  * assembly code in arch/x86/net/bpf_jit.S
21  */
22 extern u8 sk_load_word[], sk_load_half[], sk_load_byte[];
23 extern u8 sk_load_word_positive_offset[], sk_load_half_positive_offset[];
24 extern u8 sk_load_byte_positive_offset[];
25 extern u8 sk_load_word_negative_offset[], sk_load_half_negative_offset[];
26 extern u8 sk_load_byte_negative_offset[];
27
28 static u8 *emit_code(u8 *ptr, u32 bytes, unsigned int len)
29 {
30         if (len == 1)
31                 *ptr = bytes;
32         else if (len == 2)
33                 *(u16 *)ptr = bytes;
34         else {
35                 *(u32 *)ptr = bytes;
36                 barrier();
37         }
38         return ptr + len;
39 }
40
41 #define EMIT(bytes, len) \
42         do { prog = emit_code(prog, bytes, len); cnt += len; } while (0)
43
44 #define EMIT1(b1)               EMIT(b1, 1)
45 #define EMIT2(b1, b2)           EMIT((b1) + ((b2) << 8), 2)
46 #define EMIT3(b1, b2, b3)       EMIT((b1) + ((b2) << 8) + ((b3) << 16), 3)
47 #define EMIT4(b1, b2, b3, b4)   EMIT((b1) + ((b2) << 8) + ((b3) << 16) + ((b4) << 24), 4)
48 #define EMIT1_off32(b1, off) \
49         do {EMIT1(b1); EMIT(off, 4); } while (0)
50 #define EMIT2_off32(b1, b2, off) \
51         do {EMIT2(b1, b2); EMIT(off, 4); } while (0)
52 #define EMIT3_off32(b1, b2, b3, off) \
53         do {EMIT3(b1, b2, b3); EMIT(off, 4); } while (0)
54 #define EMIT4_off32(b1, b2, b3, b4, off) \
55         do {EMIT4(b1, b2, b3, b4); EMIT(off, 4); } while (0)
56
57 static bool is_imm8(int value)
58 {
59         return value <= 127 && value >= -128;
60 }
61
62 static bool is_simm32(s64 value)
63 {
64         return value == (s64) (s32) value;
65 }
66
67 /* mov dst, src */
68 #define EMIT_mov(DST, SRC) \
69         do {if (DST != SRC) \
70                 EMIT3(add_2mod(0x48, DST, SRC), 0x89, add_2reg(0xC0, DST, SRC)); \
71         } while (0)
72
73 static int bpf_size_to_x86_bytes(int bpf_size)
74 {
75         if (bpf_size == BPF_W)
76                 return 4;
77         else if (bpf_size == BPF_H)
78                 return 2;
79         else if (bpf_size == BPF_B)
80                 return 1;
81         else if (bpf_size == BPF_DW)
82                 return 4; /* imm32 */
83         else
84                 return 0;
85 }
86
87 /* list of x86 cond jumps opcodes (. + s8)
88  * Add 0x10 (and an extra 0x0f) to generate far jumps (. + s32)
89  */
90 #define X86_JB  0x72
91 #define X86_JAE 0x73
92 #define X86_JE  0x74
93 #define X86_JNE 0x75
94 #define X86_JBE 0x76
95 #define X86_JA  0x77
96 #define X86_JL  0x7C
97 #define X86_JGE 0x7D
98 #define X86_JLE 0x7E
99 #define X86_JG  0x7F
100
101 static void bpf_flush_icache(void *start, void *end)
102 {
103         mm_segment_t old_fs = get_fs();
104
105         set_fs(KERNEL_DS);
106         smp_wmb();
107         flush_icache_range((unsigned long)start, (unsigned long)end);
108         set_fs(old_fs);
109 }
110
111 #define CHOOSE_LOAD_FUNC(K, func) \
112         ((int)K < 0 ? ((int)K >= SKF_LL_OFF ? func##_negative_offset : func) : func##_positive_offset)
113
114 /* pick a register outside of BPF range for JIT internal work */
115 #define AUX_REG (MAX_BPF_JIT_REG + 1)
116
117 /* The following table maps BPF registers to x64 registers.
118  *
119  * x64 register r12 is unused, since if used as base address
120  * register in load/store instructions, it always needs an
121  * extra byte of encoding and is callee saved.
122  *
123  *  r9 caches skb->len - skb->data_len
124  * r10 caches skb->data, and used for blinding (if enabled)
125  */
126 static const int reg2hex[] = {
127         [BPF_REG_0] = 0,  /* rax */
128         [BPF_REG_1] = 7,  /* rdi */
129         [BPF_REG_2] = 6,  /* rsi */
130         [BPF_REG_3] = 2,  /* rdx */
131         [BPF_REG_4] = 1,  /* rcx */
132         [BPF_REG_5] = 0,  /* r8 */
133         [BPF_REG_6] = 3,  /* rbx callee saved */
134         [BPF_REG_7] = 5,  /* r13 callee saved */
135         [BPF_REG_8] = 6,  /* r14 callee saved */
136         [BPF_REG_9] = 7,  /* r15 callee saved */
137         [BPF_REG_FP] = 5, /* rbp readonly */
138         [BPF_REG_AX] = 2, /* r10 temp register */
139         [AUX_REG] = 3,    /* r11 temp register */
140 };
141
142 /* is_ereg() == true if BPF register 'reg' maps to x64 r8..r15
143  * which need extra byte of encoding.
144  * rax,rcx,...,rbp have simpler encoding
145  */
146 static bool is_ereg(u32 reg)
147 {
148         return (1 << reg) & (BIT(BPF_REG_5) |
149                              BIT(AUX_REG) |
150                              BIT(BPF_REG_7) |
151                              BIT(BPF_REG_8) |
152                              BIT(BPF_REG_9) |
153                              BIT(BPF_REG_AX));
154 }
155
156 /*
157  * is_ereg_8l() == true if BPF register 'reg' is mapped to access x86-64
158  * lower 8-bit registers dil,sil,bpl,spl,r8b..r15b, which need extra byte
159  * of encoding. al,cl,dl,bl have simpler encoding.
160  */
161 static bool is_ereg_8l(u32 reg)
162 {
163         return is_ereg(reg) ||
164             (1 << reg) & (BIT(BPF_REG_1) |
165                           BIT(BPF_REG_2) |
166                           BIT(BPF_REG_FP));
167 }
168
169 /* add modifiers if 'reg' maps to x64 registers r8..r15 */
170 static u8 add_1mod(u8 byte, u32 reg)
171 {
172         if (is_ereg(reg))
173                 byte |= 1;
174         return byte;
175 }
176
177 static u8 add_2mod(u8 byte, u32 r1, u32 r2)
178 {
179         if (is_ereg(r1))
180                 byte |= 1;
181         if (is_ereg(r2))
182                 byte |= 4;
183         return byte;
184 }
185
186 /* encode 'dst_reg' register into x64 opcode 'byte' */
187 static u8 add_1reg(u8 byte, u32 dst_reg)
188 {
189         return byte + reg2hex[dst_reg];
190 }
191
192 /* encode 'dst_reg' and 'src_reg' registers into x64 opcode 'byte' */
193 static u8 add_2reg(u8 byte, u32 dst_reg, u32 src_reg)
194 {
195         return byte + reg2hex[dst_reg] + (reg2hex[src_reg] << 3);
196 }
197
198 static void jit_fill_hole(void *area, unsigned int size)
199 {
200         /* fill whole space with int3 instructions */
201         memset(area, 0xcc, size);
202 }
203
204 struct jit_context {
205         int cleanup_addr; /* epilogue code offset */
206         bool seen_ld_abs;
207         bool seen_ax_reg;
208 };
209
210 /* maximum number of bytes emitted while JITing one eBPF insn */
211 #define BPF_MAX_INSN_SIZE       128
212 #define BPF_INSN_SAFETY         64
213
214 #define AUX_STACK_SPACE \
215         (32 /* space for rbx, r13, r14, r15 */ + \
216          8 /* space for skb_copy_bits() buffer */)
217
218 #define PROLOGUE_SIZE 37
219
220 /* emit x64 prologue code for BPF program and check it's size.
221  * bpf_tail_call helper will skip it while jumping into another program
222  */
223 static void emit_prologue(u8 **pprog, u32 stack_depth)
224 {
225         u8 *prog = *pprog;
226         int cnt = 0;
227
228         EMIT1(0x55); /* push rbp */
229         EMIT3(0x48, 0x89, 0xE5); /* mov rbp,rsp */
230
231         /* sub rsp, rounded_stack_depth + AUX_STACK_SPACE */
232         EMIT3_off32(0x48, 0x81, 0xEC,
233                     round_up(stack_depth, 8) + AUX_STACK_SPACE);
234
235         /* sub rbp, AUX_STACK_SPACE */
236         EMIT4(0x48, 0x83, 0xED, AUX_STACK_SPACE);
237
238         /* all classic BPF filters use R6(rbx) save it */
239
240         /* mov qword ptr [rbp+0],rbx */
241         EMIT4(0x48, 0x89, 0x5D, 0);
242
243         /* bpf_convert_filter() maps classic BPF register X to R7 and uses R8
244          * as temporary, so all tcpdump filters need to spill/fill R7(r13) and
245          * R8(r14). R9(r15) spill could be made conditional, but there is only
246          * one 'bpf_error' return path out of helper functions inside bpf_jit.S
247          * The overhead of extra spill is negligible for any filter other
248          * than synthetic ones. Therefore not worth adding complexity.
249          */
250
251         /* mov qword ptr [rbp+8],r13 */
252         EMIT4(0x4C, 0x89, 0x6D, 8);
253         /* mov qword ptr [rbp+16],r14 */
254         EMIT4(0x4C, 0x89, 0x75, 16);
255         /* mov qword ptr [rbp+24],r15 */
256         EMIT4(0x4C, 0x89, 0x7D, 24);
257
258         /* Clear the tail call counter (tail_call_cnt): for eBPF tail calls
259          * we need to reset the counter to 0. It's done in two instructions,
260          * resetting rax register to 0 (xor on eax gets 0 extended), and
261          * moving it to the counter location.
262          */
263
264         /* xor eax, eax */
265         EMIT2(0x31, 0xc0);
266         /* mov qword ptr [rbp+32], rax */
267         EMIT4(0x48, 0x89, 0x45, 32);
268
269         BUILD_BUG_ON(cnt != PROLOGUE_SIZE);
270         *pprog = prog;
271 }
272
273 /* generate the following code:
274  * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ...
275  *   if (index >= array->map.max_entries)
276  *     goto out;
277  *   if (++tail_call_cnt > MAX_TAIL_CALL_CNT)
278  *     goto out;
279  *   prog = array->ptrs[index];
280  *   if (prog == NULL)
281  *     goto out;
282  *   goto *(prog->bpf_func + prologue_size);
283  * out:
284  */
285 static void emit_bpf_tail_call(u8 **pprog)
286 {
287         u8 *prog = *pprog;
288         int label1, label2, label3;
289         int cnt = 0;
290
291         /* rdi - pointer to ctx
292          * rsi - pointer to bpf_array
293          * rdx - index in bpf_array
294          */
295
296         /* if (index >= array->map.max_entries)
297          *   goto out;
298          */
299         EMIT2(0x89, 0xD2);                        /* mov edx, edx */
300         EMIT3(0x39, 0x56,                         /* cmp dword ptr [rsi + 16], edx */
301               offsetof(struct bpf_array, map.max_entries));
302 #define OFFSET1 (41 + RETPOLINE_RAX_BPF_JIT_SIZE) /* number of bytes to jump */
303         EMIT2(X86_JBE, OFFSET1);                  /* jbe out */
304         label1 = cnt;
305
306         /* if (tail_call_cnt > MAX_TAIL_CALL_CNT)
307          *   goto out;
308          */
309         EMIT2_off32(0x8B, 0x85, 36);              /* mov eax, dword ptr [rbp + 36] */
310         EMIT3(0x83, 0xF8, MAX_TAIL_CALL_CNT);     /* cmp eax, MAX_TAIL_CALL_CNT */
311 #define OFFSET2 (30 + RETPOLINE_RAX_BPF_JIT_SIZE)
312         EMIT2(X86_JA, OFFSET2);                   /* ja out */
313         label2 = cnt;
314         EMIT3(0x83, 0xC0, 0x01);                  /* add eax, 1 */
315         EMIT2_off32(0x89, 0x85, 36);              /* mov dword ptr [rbp + 36], eax */
316
317         /* prog = array->ptrs[index]; */
318         EMIT4_off32(0x48, 0x8B, 0x84, 0xD6,       /* mov rax, [rsi + rdx * 8 + offsetof(...)] */
319                     offsetof(struct bpf_array, ptrs));
320
321         /* if (prog == NULL)
322          *   goto out;
323          */
324         EMIT3(0x48, 0x85, 0xC0);                  /* test rax,rax */
325 #define OFFSET3 (8 + RETPOLINE_RAX_BPF_JIT_SIZE)
326         EMIT2(X86_JE, OFFSET3);                   /* je out */
327         label3 = cnt;
328
329         /* goto *(prog->bpf_func + prologue_size); */
330         EMIT4(0x48, 0x8B, 0x40,                   /* mov rax, qword ptr [rax + 32] */
331               offsetof(struct bpf_prog, bpf_func));
332         EMIT4(0x48, 0x83, 0xC0, PROLOGUE_SIZE);   /* add rax, prologue_size */
333
334         /* now we're ready to jump into next BPF program
335          * rdi == ctx (1st arg)
336          * rax == prog->bpf_func + prologue_size
337          */
338         RETPOLINE_RAX_BPF_JIT();
339
340         /* out: */
341         BUILD_BUG_ON(cnt - label1 != OFFSET1);
342         BUILD_BUG_ON(cnt - label2 != OFFSET2);
343         BUILD_BUG_ON(cnt - label3 != OFFSET3);
344         *pprog = prog;
345 }
346
347
348 static void emit_load_skb_data_hlen(u8 **pprog)
349 {
350         u8 *prog = *pprog;
351         int cnt = 0;
352
353         /* r9d = skb->len - skb->data_len (headlen)
354          * r10 = skb->data
355          */
356         /* mov %r9d, off32(%rdi) */
357         EMIT3_off32(0x44, 0x8b, 0x8f, offsetof(struct sk_buff, len));
358
359         /* sub %r9d, off32(%rdi) */
360         EMIT3_off32(0x44, 0x2b, 0x8f, offsetof(struct sk_buff, data_len));
361
362         /* mov %r10, off32(%rdi) */
363         EMIT3_off32(0x4c, 0x8b, 0x97, offsetof(struct sk_buff, data));
364         *pprog = prog;
365 }
366
367 static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
368                   int oldproglen, struct jit_context *ctx)
369 {
370         struct bpf_insn *insn = bpf_prog->insnsi;
371         int insn_cnt = bpf_prog->len;
372         bool seen_ld_abs = ctx->seen_ld_abs | (oldproglen == 0);
373         bool seen_ax_reg = ctx->seen_ax_reg | (oldproglen == 0);
374         bool seen_exit = false;
375         u8 temp[BPF_MAX_INSN_SIZE + BPF_INSN_SAFETY];
376         int i, cnt = 0;
377         int proglen = 0;
378         u8 *prog = temp;
379
380         emit_prologue(&prog, bpf_prog->aux->stack_depth);
381
382         if (seen_ld_abs)
383                 emit_load_skb_data_hlen(&prog);
384
385         for (i = 0; i < insn_cnt; i++, insn++) {
386                 const s32 imm32 = insn->imm;
387                 u32 dst_reg = insn->dst_reg;
388                 u32 src_reg = insn->src_reg;
389                 u8 b1 = 0, b2 = 0, b3 = 0;
390                 s64 jmp_offset;
391                 u8 jmp_cond;
392                 bool reload_skb_data;
393                 int ilen;
394                 u8 *func;
395
396                 if (dst_reg == BPF_REG_AX || src_reg == BPF_REG_AX)
397                         ctx->seen_ax_reg = seen_ax_reg = true;
398
399                 switch (insn->code) {
400                         /* ALU */
401                 case BPF_ALU | BPF_ADD | BPF_X:
402                 case BPF_ALU | BPF_SUB | BPF_X:
403                 case BPF_ALU | BPF_AND | BPF_X:
404                 case BPF_ALU | BPF_OR | BPF_X:
405                 case BPF_ALU | BPF_XOR | BPF_X:
406                 case BPF_ALU64 | BPF_ADD | BPF_X:
407                 case BPF_ALU64 | BPF_SUB | BPF_X:
408                 case BPF_ALU64 | BPF_AND | BPF_X:
409                 case BPF_ALU64 | BPF_OR | BPF_X:
410                 case BPF_ALU64 | BPF_XOR | BPF_X:
411                         switch (BPF_OP(insn->code)) {
412                         case BPF_ADD: b2 = 0x01; break;
413                         case BPF_SUB: b2 = 0x29; break;
414                         case BPF_AND: b2 = 0x21; break;
415                         case BPF_OR: b2 = 0x09; break;
416                         case BPF_XOR: b2 = 0x31; break;
417                         }
418                         if (BPF_CLASS(insn->code) == BPF_ALU64)
419                                 EMIT1(add_2mod(0x48, dst_reg, src_reg));
420                         else if (is_ereg(dst_reg) || is_ereg(src_reg))
421                                 EMIT1(add_2mod(0x40, dst_reg, src_reg));
422                         EMIT2(b2, add_2reg(0xC0, dst_reg, src_reg));
423                         break;
424
425                         /* mov dst, src */
426                 case BPF_ALU64 | BPF_MOV | BPF_X:
427                         EMIT_mov(dst_reg, src_reg);
428                         break;
429
430                         /* mov32 dst, src */
431                 case BPF_ALU | BPF_MOV | BPF_X:
432                         if (is_ereg(dst_reg) || is_ereg(src_reg))
433                                 EMIT1(add_2mod(0x40, dst_reg, src_reg));
434                         EMIT2(0x89, add_2reg(0xC0, dst_reg, src_reg));
435                         break;
436
437                         /* neg dst */
438                 case BPF_ALU | BPF_NEG:
439                 case BPF_ALU64 | BPF_NEG:
440                         if (BPF_CLASS(insn->code) == BPF_ALU64)
441                                 EMIT1(add_1mod(0x48, dst_reg));
442                         else if (is_ereg(dst_reg))
443                                 EMIT1(add_1mod(0x40, dst_reg));
444                         EMIT2(0xF7, add_1reg(0xD8, dst_reg));
445                         break;
446
447                 case BPF_ALU | BPF_ADD | BPF_K:
448                 case BPF_ALU | BPF_SUB | BPF_K:
449                 case BPF_ALU | BPF_AND | BPF_K:
450                 case BPF_ALU | BPF_OR | BPF_K:
451                 case BPF_ALU | BPF_XOR | BPF_K:
452                 case BPF_ALU64 | BPF_ADD | BPF_K:
453                 case BPF_ALU64 | BPF_SUB | BPF_K:
454                 case BPF_ALU64 | BPF_AND | BPF_K:
455                 case BPF_ALU64 | BPF_OR | BPF_K:
456                 case BPF_ALU64 | BPF_XOR | BPF_K:
457                         if (BPF_CLASS(insn->code) == BPF_ALU64)
458                                 EMIT1(add_1mod(0x48, dst_reg));
459                         else if (is_ereg(dst_reg))
460                                 EMIT1(add_1mod(0x40, dst_reg));
461
462                         switch (BPF_OP(insn->code)) {
463                         case BPF_ADD: b3 = 0xC0; break;
464                         case BPF_SUB: b3 = 0xE8; break;
465                         case BPF_AND: b3 = 0xE0; break;
466                         case BPF_OR: b3 = 0xC8; break;
467                         case BPF_XOR: b3 = 0xF0; break;
468                         }
469
470                         if (is_imm8(imm32))
471                                 EMIT3(0x83, add_1reg(b3, dst_reg), imm32);
472                         else
473                                 EMIT2_off32(0x81, add_1reg(b3, dst_reg), imm32);
474                         break;
475
476                 case BPF_ALU64 | BPF_MOV | BPF_K:
477                         /* optimization: if imm32 is positive,
478                          * use 'mov eax, imm32' (which zero-extends imm32)
479                          * to save 2 bytes
480                          */
481                         if (imm32 < 0) {
482                                 /* 'mov rax, imm32' sign extends imm32 */
483                                 b1 = add_1mod(0x48, dst_reg);
484                                 b2 = 0xC7;
485                                 b3 = 0xC0;
486                                 EMIT3_off32(b1, b2, add_1reg(b3, dst_reg), imm32);
487                                 break;
488                         }
489
490                 case BPF_ALU | BPF_MOV | BPF_K:
491                         /* optimization: if imm32 is zero, use 'xor <dst>,<dst>'
492                          * to save 3 bytes.
493                          */
494                         if (imm32 == 0) {
495                                 if (is_ereg(dst_reg))
496                                         EMIT1(add_2mod(0x40, dst_reg, dst_reg));
497                                 b2 = 0x31; /* xor */
498                                 b3 = 0xC0;
499                                 EMIT2(b2, add_2reg(b3, dst_reg, dst_reg));
500                                 break;
501                         }
502
503                         /* mov %eax, imm32 */
504                         if (is_ereg(dst_reg))
505                                 EMIT1(add_1mod(0x40, dst_reg));
506                         EMIT1_off32(add_1reg(0xB8, dst_reg), imm32);
507                         break;
508
509                 case BPF_LD | BPF_IMM | BPF_DW:
510                         /* optimization: if imm64 is zero, use 'xor <dst>,<dst>'
511                          * to save 7 bytes.
512                          */
513                         if (insn[0].imm == 0 && insn[1].imm == 0) {
514                                 b1 = add_2mod(0x48, dst_reg, dst_reg);
515                                 b2 = 0x31; /* xor */
516                                 b3 = 0xC0;
517                                 EMIT3(b1, b2, add_2reg(b3, dst_reg, dst_reg));
518
519                                 insn++;
520                                 i++;
521                                 break;
522                         }
523
524                         /* movabsq %rax, imm64 */
525                         EMIT2(add_1mod(0x48, dst_reg), add_1reg(0xB8, dst_reg));
526                         EMIT(insn[0].imm, 4);
527                         EMIT(insn[1].imm, 4);
528
529                         insn++;
530                         i++;
531                         break;
532
533                         /* dst %= src, dst /= src, dst %= imm32, dst /= imm32 */
534                 case BPF_ALU | BPF_MOD | BPF_X:
535                 case BPF_ALU | BPF_DIV | BPF_X:
536                 case BPF_ALU | BPF_MOD | BPF_K:
537                 case BPF_ALU | BPF_DIV | BPF_K:
538                 case BPF_ALU64 | BPF_MOD | BPF_X:
539                 case BPF_ALU64 | BPF_DIV | BPF_X:
540                 case BPF_ALU64 | BPF_MOD | BPF_K:
541                 case BPF_ALU64 | BPF_DIV | BPF_K:
542                         EMIT1(0x50); /* push rax */
543                         EMIT1(0x52); /* push rdx */
544
545                         if (BPF_SRC(insn->code) == BPF_X)
546                                 /* mov r11, src_reg */
547                                 EMIT_mov(AUX_REG, src_reg);
548                         else
549                                 /* mov r11, imm32 */
550                                 EMIT3_off32(0x49, 0xC7, 0xC3, imm32);
551
552                         /* mov rax, dst_reg */
553                         EMIT_mov(BPF_REG_0, dst_reg);
554
555                         /* xor edx, edx
556                          * equivalent to 'xor rdx, rdx', but one byte less
557                          */
558                         EMIT2(0x31, 0xd2);
559
560                         if (BPF_SRC(insn->code) == BPF_X) {
561                                 /* if (src_reg == 0) return 0 */
562
563                                 /* cmp r11, 0 */
564                                 EMIT4(0x49, 0x83, 0xFB, 0x00);
565
566                                 /* jne .+9 (skip over pop, pop, xor and jmp) */
567                                 EMIT2(X86_JNE, 1 + 1 + 2 + 5);
568                                 EMIT1(0x5A); /* pop rdx */
569                                 EMIT1(0x58); /* pop rax */
570                                 EMIT2(0x31, 0xc0); /* xor eax, eax */
571
572                                 /* jmp cleanup_addr
573                                  * addrs[i] - 11, because there are 11 bytes
574                                  * after this insn: div, mov, pop, pop, mov
575                                  */
576                                 jmp_offset = ctx->cleanup_addr - (addrs[i] - 11);
577                                 EMIT1_off32(0xE9, jmp_offset);
578                         }
579
580                         if (BPF_CLASS(insn->code) == BPF_ALU64)
581                                 /* div r11 */
582                                 EMIT3(0x49, 0xF7, 0xF3);
583                         else
584                                 /* div r11d */
585                                 EMIT3(0x41, 0xF7, 0xF3);
586
587                         if (BPF_OP(insn->code) == BPF_MOD)
588                                 /* mov r11, rdx */
589                                 EMIT3(0x49, 0x89, 0xD3);
590                         else
591                                 /* mov r11, rax */
592                                 EMIT3(0x49, 0x89, 0xC3);
593
594                         EMIT1(0x5A); /* pop rdx */
595                         EMIT1(0x58); /* pop rax */
596
597                         /* mov dst_reg, r11 */
598                         EMIT_mov(dst_reg, AUX_REG);
599                         break;
600
601                 case BPF_ALU | BPF_MUL | BPF_K:
602                 case BPF_ALU | BPF_MUL | BPF_X:
603                 case BPF_ALU64 | BPF_MUL | BPF_K:
604                 case BPF_ALU64 | BPF_MUL | BPF_X:
605                         EMIT1(0x50); /* push rax */
606                         EMIT1(0x52); /* push rdx */
607
608                         /* mov r11, dst_reg */
609                         EMIT_mov(AUX_REG, dst_reg);
610
611                         if (BPF_SRC(insn->code) == BPF_X)
612                                 /* mov rax, src_reg */
613                                 EMIT_mov(BPF_REG_0, src_reg);
614                         else
615                                 /* mov rax, imm32 */
616                                 EMIT3_off32(0x48, 0xC7, 0xC0, imm32);
617
618                         if (BPF_CLASS(insn->code) == BPF_ALU64)
619                                 EMIT1(add_1mod(0x48, AUX_REG));
620                         else if (is_ereg(AUX_REG))
621                                 EMIT1(add_1mod(0x40, AUX_REG));
622                         /* mul(q) r11 */
623                         EMIT2(0xF7, add_1reg(0xE0, AUX_REG));
624
625                         /* mov r11, rax */
626                         EMIT_mov(AUX_REG, BPF_REG_0);
627
628                         EMIT1(0x5A); /* pop rdx */
629                         EMIT1(0x58); /* pop rax */
630
631                         /* mov dst_reg, r11 */
632                         EMIT_mov(dst_reg, AUX_REG);
633                         break;
634
635                         /* shifts */
636                 case BPF_ALU | BPF_LSH | BPF_K:
637                 case BPF_ALU | BPF_RSH | BPF_K:
638                 case BPF_ALU | BPF_ARSH | BPF_K:
639                 case BPF_ALU64 | BPF_LSH | BPF_K:
640                 case BPF_ALU64 | BPF_RSH | BPF_K:
641                 case BPF_ALU64 | BPF_ARSH | BPF_K:
642                         if (BPF_CLASS(insn->code) == BPF_ALU64)
643                                 EMIT1(add_1mod(0x48, dst_reg));
644                         else if (is_ereg(dst_reg))
645                                 EMIT1(add_1mod(0x40, dst_reg));
646
647                         switch (BPF_OP(insn->code)) {
648                         case BPF_LSH: b3 = 0xE0; break;
649                         case BPF_RSH: b3 = 0xE8; break;
650                         case BPF_ARSH: b3 = 0xF8; break;
651                         }
652                         EMIT3(0xC1, add_1reg(b3, dst_reg), imm32);
653                         break;
654
655                 case BPF_ALU | BPF_LSH | BPF_X:
656                 case BPF_ALU | BPF_RSH | BPF_X:
657                 case BPF_ALU | BPF_ARSH | BPF_X:
658                 case BPF_ALU64 | BPF_LSH | BPF_X:
659                 case BPF_ALU64 | BPF_RSH | BPF_X:
660                 case BPF_ALU64 | BPF_ARSH | BPF_X:
661
662                         /* check for bad case when dst_reg == rcx */
663                         if (dst_reg == BPF_REG_4) {
664                                 /* mov r11, dst_reg */
665                                 EMIT_mov(AUX_REG, dst_reg);
666                                 dst_reg = AUX_REG;
667                         }
668
669                         if (src_reg != BPF_REG_4) { /* common case */
670                                 EMIT1(0x51); /* push rcx */
671
672                                 /* mov rcx, src_reg */
673                                 EMIT_mov(BPF_REG_4, src_reg);
674                         }
675
676                         /* shl %rax, %cl | shr %rax, %cl | sar %rax, %cl */
677                         if (BPF_CLASS(insn->code) == BPF_ALU64)
678                                 EMIT1(add_1mod(0x48, dst_reg));
679                         else if (is_ereg(dst_reg))
680                                 EMIT1(add_1mod(0x40, dst_reg));
681
682                         switch (BPF_OP(insn->code)) {
683                         case BPF_LSH: b3 = 0xE0; break;
684                         case BPF_RSH: b3 = 0xE8; break;
685                         case BPF_ARSH: b3 = 0xF8; break;
686                         }
687                         EMIT2(0xD3, add_1reg(b3, dst_reg));
688
689                         if (src_reg != BPF_REG_4)
690                                 EMIT1(0x59); /* pop rcx */
691
692                         if (insn->dst_reg == BPF_REG_4)
693                                 /* mov dst_reg, r11 */
694                                 EMIT_mov(insn->dst_reg, AUX_REG);
695                         break;
696
697                 case BPF_ALU | BPF_END | BPF_FROM_BE:
698                         switch (imm32) {
699                         case 16:
700                                 /* emit 'ror %ax, 8' to swap lower 2 bytes */
701                                 EMIT1(0x66);
702                                 if (is_ereg(dst_reg))
703                                         EMIT1(0x41);
704                                 EMIT3(0xC1, add_1reg(0xC8, dst_reg), 8);
705
706                                 /* emit 'movzwl eax, ax' */
707                                 if (is_ereg(dst_reg))
708                                         EMIT3(0x45, 0x0F, 0xB7);
709                                 else
710                                         EMIT2(0x0F, 0xB7);
711                                 EMIT1(add_2reg(0xC0, dst_reg, dst_reg));
712                                 break;
713                         case 32:
714                                 /* emit 'bswap eax' to swap lower 4 bytes */
715                                 if (is_ereg(dst_reg))
716                                         EMIT2(0x41, 0x0F);
717                                 else
718                                         EMIT1(0x0F);
719                                 EMIT1(add_1reg(0xC8, dst_reg));
720                                 break;
721                         case 64:
722                                 /* emit 'bswap rax' to swap 8 bytes */
723                                 EMIT3(add_1mod(0x48, dst_reg), 0x0F,
724                                       add_1reg(0xC8, dst_reg));
725                                 break;
726                         }
727                         break;
728
729                 case BPF_ALU | BPF_END | BPF_FROM_LE:
730                         switch (imm32) {
731                         case 16:
732                                 /* emit 'movzwl eax, ax' to zero extend 16-bit
733                                  * into 64 bit
734                                  */
735                                 if (is_ereg(dst_reg))
736                                         EMIT3(0x45, 0x0F, 0xB7);
737                                 else
738                                         EMIT2(0x0F, 0xB7);
739                                 EMIT1(add_2reg(0xC0, dst_reg, dst_reg));
740                                 break;
741                         case 32:
742                                 /* emit 'mov eax, eax' to clear upper 32-bits */
743                                 if (is_ereg(dst_reg))
744                                         EMIT1(0x45);
745                                 EMIT2(0x89, add_2reg(0xC0, dst_reg, dst_reg));
746                                 break;
747                         case 64:
748                                 /* nop */
749                                 break;
750                         }
751                         break;
752
753                         /* ST: *(u8*)(dst_reg + off) = imm */
754                 case BPF_ST | BPF_MEM | BPF_B:
755                         if (is_ereg(dst_reg))
756                                 EMIT2(0x41, 0xC6);
757                         else
758                                 EMIT1(0xC6);
759                         goto st;
760                 case BPF_ST | BPF_MEM | BPF_H:
761                         if (is_ereg(dst_reg))
762                                 EMIT3(0x66, 0x41, 0xC7);
763                         else
764                                 EMIT2(0x66, 0xC7);
765                         goto st;
766                 case BPF_ST | BPF_MEM | BPF_W:
767                         if (is_ereg(dst_reg))
768                                 EMIT2(0x41, 0xC7);
769                         else
770                                 EMIT1(0xC7);
771                         goto st;
772                 case BPF_ST | BPF_MEM | BPF_DW:
773                         EMIT2(add_1mod(0x48, dst_reg), 0xC7);
774
775 st:                     if (is_imm8(insn->off))
776                                 EMIT2(add_1reg(0x40, dst_reg), insn->off);
777                         else
778                                 EMIT1_off32(add_1reg(0x80, dst_reg), insn->off);
779
780                         EMIT(imm32, bpf_size_to_x86_bytes(BPF_SIZE(insn->code)));
781                         break;
782
783                         /* STX: *(u8*)(dst_reg + off) = src_reg */
784                 case BPF_STX | BPF_MEM | BPF_B:
785                         /* emit 'mov byte ptr [rax + off], al' */
786                         if (is_ereg(dst_reg) || is_ereg_8l(src_reg))
787                                 /* Add extra byte for eregs or SIL,DIL,BPL in src_reg */
788                                 EMIT2(add_2mod(0x40, dst_reg, src_reg), 0x88);
789                         else
790                                 EMIT1(0x88);
791                         goto stx;
792                 case BPF_STX | BPF_MEM | BPF_H:
793                         if (is_ereg(dst_reg) || is_ereg(src_reg))
794                                 EMIT3(0x66, add_2mod(0x40, dst_reg, src_reg), 0x89);
795                         else
796                                 EMIT2(0x66, 0x89);
797                         goto stx;
798                 case BPF_STX | BPF_MEM | BPF_W:
799                         if (is_ereg(dst_reg) || is_ereg(src_reg))
800                                 EMIT2(add_2mod(0x40, dst_reg, src_reg), 0x89);
801                         else
802                                 EMIT1(0x89);
803                         goto stx;
804                 case BPF_STX | BPF_MEM | BPF_DW:
805                         EMIT2(add_2mod(0x48, dst_reg, src_reg), 0x89);
806 stx:                    if (is_imm8(insn->off))
807                                 EMIT2(add_2reg(0x40, dst_reg, src_reg), insn->off);
808                         else
809                                 EMIT1_off32(add_2reg(0x80, dst_reg, src_reg),
810                                             insn->off);
811                         break;
812
813                         /* LDX: dst_reg = *(u8*)(src_reg + off) */
814                 case BPF_LDX | BPF_MEM | BPF_B:
815                         /* emit 'movzx rax, byte ptr [rax + off]' */
816                         EMIT3(add_2mod(0x48, src_reg, dst_reg), 0x0F, 0xB6);
817                         goto ldx;
818                 case BPF_LDX | BPF_MEM | BPF_H:
819                         /* emit 'movzx rax, word ptr [rax + off]' */
820                         EMIT3(add_2mod(0x48, src_reg, dst_reg), 0x0F, 0xB7);
821                         goto ldx;
822                 case BPF_LDX | BPF_MEM | BPF_W:
823                         /* emit 'mov eax, dword ptr [rax+0x14]' */
824                         if (is_ereg(dst_reg) || is_ereg(src_reg))
825                                 EMIT2(add_2mod(0x40, src_reg, dst_reg), 0x8B);
826                         else
827                                 EMIT1(0x8B);
828                         goto ldx;
829                 case BPF_LDX | BPF_MEM | BPF_DW:
830                         /* emit 'mov rax, qword ptr [rax+0x14]' */
831                         EMIT2(add_2mod(0x48, src_reg, dst_reg), 0x8B);
832 ldx:                    /* if insn->off == 0 we can save one extra byte, but
833                          * special case of x86 r13 which always needs an offset
834                          * is not worth the hassle
835                          */
836                         if (is_imm8(insn->off))
837                                 EMIT2(add_2reg(0x40, src_reg, dst_reg), insn->off);
838                         else
839                                 EMIT1_off32(add_2reg(0x80, src_reg, dst_reg),
840                                             insn->off);
841                         break;
842
843                         /* STX XADD: lock *(u32*)(dst_reg + off) += src_reg */
844                 case BPF_STX | BPF_XADD | BPF_W:
845                         /* emit 'lock add dword ptr [rax + off], eax' */
846                         if (is_ereg(dst_reg) || is_ereg(src_reg))
847                                 EMIT3(0xF0, add_2mod(0x40, dst_reg, src_reg), 0x01);
848                         else
849                                 EMIT2(0xF0, 0x01);
850                         goto xadd;
851                 case BPF_STX | BPF_XADD | BPF_DW:
852                         EMIT3(0xF0, add_2mod(0x48, dst_reg, src_reg), 0x01);
853 xadd:                   if (is_imm8(insn->off))
854                                 EMIT2(add_2reg(0x40, dst_reg, src_reg), insn->off);
855                         else
856                                 EMIT1_off32(add_2reg(0x80, dst_reg, src_reg),
857                                             insn->off);
858                         break;
859
860                         /* call */
861                 case BPF_JMP | BPF_CALL:
862                         func = (u8 *) __bpf_call_base + imm32;
863                         jmp_offset = func - (image + addrs[i]);
864                         if (seen_ld_abs) {
865                                 reload_skb_data = bpf_helper_changes_pkt_data(func);
866                                 if (reload_skb_data) {
867                                         EMIT1(0x57); /* push %rdi */
868                                         jmp_offset += 22; /* pop, mov, sub, mov */
869                                 } else {
870                                         EMIT2(0x41, 0x52); /* push %r10 */
871                                         EMIT2(0x41, 0x51); /* push %r9 */
872                                         /* need to adjust jmp offset, since
873                                          * pop %r9, pop %r10 take 4 bytes after call insn
874                                          */
875                                         jmp_offset += 4;
876                                 }
877                         }
878                         if (!imm32 || !is_simm32(jmp_offset)) {
879                                 pr_err("unsupported bpf func %d addr %p image %p\n",
880                                        imm32, func, image);
881                                 return -EINVAL;
882                         }
883                         EMIT1_off32(0xE8, jmp_offset);
884                         if (seen_ld_abs) {
885                                 if (reload_skb_data) {
886                                         EMIT1(0x5F); /* pop %rdi */
887                                         emit_load_skb_data_hlen(&prog);
888                                 } else {
889                                         EMIT2(0x41, 0x59); /* pop %r9 */
890                                         EMIT2(0x41, 0x5A); /* pop %r10 */
891                                 }
892                         }
893                         break;
894
895                 case BPF_JMP | BPF_TAIL_CALL:
896                         emit_bpf_tail_call(&prog);
897                         break;
898
899                         /* cond jump */
900                 case BPF_JMP | BPF_JEQ | BPF_X:
901                 case BPF_JMP | BPF_JNE | BPF_X:
902                 case BPF_JMP | BPF_JGT | BPF_X:
903                 case BPF_JMP | BPF_JLT | BPF_X:
904                 case BPF_JMP | BPF_JGE | BPF_X:
905                 case BPF_JMP | BPF_JLE | BPF_X:
906                 case BPF_JMP | BPF_JSGT | BPF_X:
907                 case BPF_JMP | BPF_JSLT | BPF_X:
908                 case BPF_JMP | BPF_JSGE | BPF_X:
909                 case BPF_JMP | BPF_JSLE | BPF_X:
910                         /* cmp dst_reg, src_reg */
911                         EMIT3(add_2mod(0x48, dst_reg, src_reg), 0x39,
912                               add_2reg(0xC0, dst_reg, src_reg));
913                         goto emit_cond_jmp;
914
915                 case BPF_JMP | BPF_JSET | BPF_X:
916                         /* test dst_reg, src_reg */
917                         EMIT3(add_2mod(0x48, dst_reg, src_reg), 0x85,
918                               add_2reg(0xC0, dst_reg, src_reg));
919                         goto emit_cond_jmp;
920
921                 case BPF_JMP | BPF_JSET | BPF_K:
922                         /* test dst_reg, imm32 */
923                         EMIT1(add_1mod(0x48, dst_reg));
924                         EMIT2_off32(0xF7, add_1reg(0xC0, dst_reg), imm32);
925                         goto emit_cond_jmp;
926
927                 case BPF_JMP | BPF_JEQ | BPF_K:
928                 case BPF_JMP | BPF_JNE | BPF_K:
929                 case BPF_JMP | BPF_JGT | BPF_K:
930                 case BPF_JMP | BPF_JLT | BPF_K:
931                 case BPF_JMP | BPF_JGE | BPF_K:
932                 case BPF_JMP | BPF_JLE | BPF_K:
933                 case BPF_JMP | BPF_JSGT | BPF_K:
934                 case BPF_JMP | BPF_JSLT | BPF_K:
935                 case BPF_JMP | BPF_JSGE | BPF_K:
936                 case BPF_JMP | BPF_JSLE | BPF_K:
937                         /* cmp dst_reg, imm8/32 */
938                         EMIT1(add_1mod(0x48, dst_reg));
939
940                         if (is_imm8(imm32))
941                                 EMIT3(0x83, add_1reg(0xF8, dst_reg), imm32);
942                         else
943                                 EMIT2_off32(0x81, add_1reg(0xF8, dst_reg), imm32);
944
945 emit_cond_jmp:          /* convert BPF opcode to x86 */
946                         switch (BPF_OP(insn->code)) {
947                         case BPF_JEQ:
948                                 jmp_cond = X86_JE;
949                                 break;
950                         case BPF_JSET:
951                         case BPF_JNE:
952                                 jmp_cond = X86_JNE;
953                                 break;
954                         case BPF_JGT:
955                                 /* GT is unsigned '>', JA in x86 */
956                                 jmp_cond = X86_JA;
957                                 break;
958                         case BPF_JLT:
959                                 /* LT is unsigned '<', JB in x86 */
960                                 jmp_cond = X86_JB;
961                                 break;
962                         case BPF_JGE:
963                                 /* GE is unsigned '>=', JAE in x86 */
964                                 jmp_cond = X86_JAE;
965                                 break;
966                         case BPF_JLE:
967                                 /* LE is unsigned '<=', JBE in x86 */
968                                 jmp_cond = X86_JBE;
969                                 break;
970                         case BPF_JSGT:
971                                 /* signed '>', GT in x86 */
972                                 jmp_cond = X86_JG;
973                                 break;
974                         case BPF_JSLT:
975                                 /* signed '<', LT in x86 */
976                                 jmp_cond = X86_JL;
977                                 break;
978                         case BPF_JSGE:
979                                 /* signed '>=', GE in x86 */
980                                 jmp_cond = X86_JGE;
981                                 break;
982                         case BPF_JSLE:
983                                 /* signed '<=', LE in x86 */
984                                 jmp_cond = X86_JLE;
985                                 break;
986                         default: /* to silence gcc warning */
987                                 return -EFAULT;
988                         }
989                         jmp_offset = addrs[i + insn->off] - addrs[i];
990                         if (is_imm8(jmp_offset)) {
991                                 EMIT2(jmp_cond, jmp_offset);
992                         } else if (is_simm32(jmp_offset)) {
993                                 EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
994                         } else {
995                                 pr_err("cond_jmp gen bug %llx\n", jmp_offset);
996                                 return -EFAULT;
997                         }
998
999                         break;
1000
1001                 case BPF_JMP | BPF_JA:
1002                         jmp_offset = addrs[i + insn->off] - addrs[i];
1003                         if (!jmp_offset)
1004                                 /* optimize out nop jumps */
1005                                 break;
1006 emit_jmp:
1007                         if (is_imm8(jmp_offset)) {
1008                                 EMIT2(0xEB, jmp_offset);
1009                         } else if (is_simm32(jmp_offset)) {
1010                                 EMIT1_off32(0xE9, jmp_offset);
1011                         } else {
1012                                 pr_err("jmp gen bug %llx\n", jmp_offset);
1013                                 return -EFAULT;
1014                         }
1015                         break;
1016
1017                 case BPF_LD | BPF_IND | BPF_W:
1018                         func = sk_load_word;
1019                         goto common_load;
1020                 case BPF_LD | BPF_ABS | BPF_W:
1021                         func = CHOOSE_LOAD_FUNC(imm32, sk_load_word);
1022 common_load:
1023                         ctx->seen_ld_abs = seen_ld_abs = true;
1024                         jmp_offset = func - (image + addrs[i]);
1025                         if (!func || !is_simm32(jmp_offset)) {
1026                                 pr_err("unsupported bpf func %d addr %p image %p\n",
1027                                        imm32, func, image);
1028                                 return -EINVAL;
1029                         }
1030                         if (BPF_MODE(insn->code) == BPF_ABS) {
1031                                 /* mov %esi, imm32 */
1032                                 EMIT1_off32(0xBE, imm32);
1033                         } else {
1034                                 /* mov %rsi, src_reg */
1035                                 EMIT_mov(BPF_REG_2, src_reg);
1036                                 if (imm32) {
1037                                         if (is_imm8(imm32))
1038                                                 /* add %esi, imm8 */
1039                                                 EMIT3(0x83, 0xC6, imm32);
1040                                         else
1041                                                 /* add %esi, imm32 */
1042                                                 EMIT2_off32(0x81, 0xC6, imm32);
1043                                 }
1044                         }
1045                         /* skb pointer is in R6 (%rbx), it will be copied into
1046                          * %rdi if skb_copy_bits() call is necessary.
1047                          * sk_load_* helpers also use %r10 and %r9d.
1048                          * See bpf_jit.S
1049                          */
1050                         if (seen_ax_reg)
1051                                 /* r10 = skb->data, mov %r10, off32(%rbx) */
1052                                 EMIT3_off32(0x4c, 0x8b, 0x93,
1053                                             offsetof(struct sk_buff, data));
1054                         EMIT1_off32(0xE8, jmp_offset); /* call */
1055                         break;
1056
1057                 case BPF_LD | BPF_IND | BPF_H:
1058                         func = sk_load_half;
1059                         goto common_load;
1060                 case BPF_LD | BPF_ABS | BPF_H:
1061                         func = CHOOSE_LOAD_FUNC(imm32, sk_load_half);
1062                         goto common_load;
1063                 case BPF_LD | BPF_IND | BPF_B:
1064                         func = sk_load_byte;
1065                         goto common_load;
1066                 case BPF_LD | BPF_ABS | BPF_B:
1067                         func = CHOOSE_LOAD_FUNC(imm32, sk_load_byte);
1068                         goto common_load;
1069
1070                 case BPF_JMP | BPF_EXIT:
1071                         if (seen_exit) {
1072                                 jmp_offset = ctx->cleanup_addr - addrs[i];
1073                                 goto emit_jmp;
1074                         }
1075                         seen_exit = true;
1076                         /* update cleanup_addr */
1077                         ctx->cleanup_addr = proglen;
1078                         /* mov rbx, qword ptr [rbp+0] */
1079                         EMIT4(0x48, 0x8B, 0x5D, 0);
1080                         /* mov r13, qword ptr [rbp+8] */
1081                         EMIT4(0x4C, 0x8B, 0x6D, 8);
1082                         /* mov r14, qword ptr [rbp+16] */
1083                         EMIT4(0x4C, 0x8B, 0x75, 16);
1084                         /* mov r15, qword ptr [rbp+24] */
1085                         EMIT4(0x4C, 0x8B, 0x7D, 24);
1086
1087                         /* add rbp, AUX_STACK_SPACE */
1088                         EMIT4(0x48, 0x83, 0xC5, AUX_STACK_SPACE);
1089                         EMIT1(0xC9); /* leave */
1090                         EMIT1(0xC3); /* ret */
1091                         break;
1092
1093                 default:
1094                         /* By design x64 JIT should support all BPF instructions
1095                          * This error will be seen if new instruction was added
1096                          * to interpreter, but not to JIT
1097                          * or if there is junk in bpf_prog
1098                          */
1099                         pr_err("bpf_jit: unknown opcode %02x\n", insn->code);
1100                         return -EINVAL;
1101                 }
1102
1103                 ilen = prog - temp;
1104                 if (ilen > BPF_MAX_INSN_SIZE) {
1105                         pr_err("bpf_jit: fatal insn size error\n");
1106                         return -EFAULT;
1107                 }
1108
1109                 if (image) {
1110                         /*
1111                          * When populating the image, assert that:
1112                          *
1113                          *  i) We do not write beyond the allocated space, and
1114                          * ii) addrs[i] did not change from the prior run, in order
1115                          *     to validate assumptions made for computing branch
1116                          *     displacements.
1117                          */
1118                         if (unlikely(proglen + ilen > oldproglen ||
1119                                      proglen + ilen != addrs[i])) {
1120                                 pr_err("bpf_jit: fatal error\n");
1121                                 return -EFAULT;
1122                         }
1123                         memcpy(image + proglen, temp, ilen);
1124                 }
1125                 proglen += ilen;
1126                 addrs[i] = proglen;
1127                 prog = temp;
1128         }
1129         return proglen;
1130 }
1131
1132 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
1133 {
1134         struct bpf_binary_header *header = NULL;
1135         struct bpf_prog *tmp, *orig_prog = prog;
1136         int proglen, oldproglen = 0;
1137         struct jit_context ctx = {};
1138         bool tmp_blinded = false;
1139         u8 *image = NULL;
1140         int *addrs;
1141         int pass;
1142         int i;
1143
1144         if (!bpf_jit_enable)
1145                 return orig_prog;
1146
1147         tmp = bpf_jit_blind_constants(prog);
1148         /* If blinding was requested and we failed during blinding,
1149          * we must fall back to the interpreter.
1150          */
1151         if (IS_ERR(tmp))
1152                 return orig_prog;
1153         if (tmp != prog) {
1154                 tmp_blinded = true;
1155                 prog = tmp;
1156         }
1157
1158         addrs = kmalloc(prog->len * sizeof(*addrs), GFP_KERNEL);
1159         if (!addrs) {
1160                 prog = orig_prog;
1161                 goto out;
1162         }
1163
1164         /* Before first pass, make a rough estimation of addrs[]
1165          * each bpf instruction is translated to less than 64 bytes
1166          */
1167         for (proglen = 0, i = 0; i < prog->len; i++) {
1168                 proglen += 64;
1169                 addrs[i] = proglen;
1170         }
1171         ctx.cleanup_addr = proglen;
1172
1173         /* JITed image shrinks with every pass and the loop iterates
1174          * until the image stops shrinking. Very large bpf programs
1175          * may converge on the last pass. In such case do one more
1176          * pass to emit the final image
1177          */
1178         for (pass = 0; pass < 20 || image; pass++) {
1179                 proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
1180                 if (proglen <= 0) {
1181 out_image:
1182                         image = NULL;
1183                         if (header)
1184                                 bpf_jit_binary_free(header);
1185                         prog = orig_prog;
1186                         goto out_addrs;
1187                 }
1188                 if (image) {
1189                         if (proglen != oldproglen) {
1190                                 pr_err("bpf_jit: proglen=%d != oldproglen=%d\n",
1191                                        proglen, oldproglen);
1192                                 goto out_image;
1193                         }
1194                         break;
1195                 }
1196                 if (proglen == oldproglen) {
1197                         header = bpf_jit_binary_alloc(proglen, &image,
1198                                                       1, jit_fill_hole);
1199                         if (!header) {
1200                                 prog = orig_prog;
1201                                 goto out_addrs;
1202                         }
1203                 }
1204                 oldproglen = proglen;
1205                 cond_resched();
1206         }
1207
1208         if (bpf_jit_enable > 1)
1209                 bpf_jit_dump(prog->len, proglen, pass + 1, image);
1210
1211         if (image) {
1212                 bpf_flush_icache(header, image + proglen);
1213                 bpf_jit_binary_lock_ro(header);
1214                 prog->bpf_func = (void *)image;
1215                 prog->jited = 1;
1216                 prog->jited_len = proglen;
1217         } else {
1218                 prog = orig_prog;
1219         }
1220
1221 out_addrs:
1222         kfree(addrs);
1223 out:
1224         if (tmp_blinded)
1225                 bpf_jit_prog_release_other(prog, prog == orig_prog ?
1226                                            tmp : orig_prog);
1227         return prog;
1228 }