bpf_jit_comp.c 24.5 KB
Newer Older
Zi Shen Lim's avatar
Zi Shen Lim committed
1
2
3
/*
 * BPF JIT compiler for ARM64
 *
4
 * Copyright (C) 2014-2016 Zi Shen Lim <zlim.lnx@gmail.com>
Zi Shen Lim's avatar
Zi Shen Lim committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#define pr_fmt(fmt) "bpf_jit: " fmt

21
#include <linux/bpf.h>
Zi Shen Lim's avatar
Zi Shen Lim committed
22
23
24
25
#include <linux/filter.h>
#include <linux/printk.h>
#include <linux/skbuff.h>
#include <linux/slab.h>
26

Zi Shen Lim's avatar
Zi Shen Lim committed
27
28
#include <asm/byteorder.h>
#include <asm/cacheflush.h>
29
#include <asm/debug-monitors.h>
Laura Abbott's avatar
Laura Abbott committed
30
#include <asm/set_memory.h>
Zi Shen Lim's avatar
Zi Shen Lim committed
31
32
33

#include "bpf_jit.h"

34
35
#define TMP_REG_1 (MAX_BPF_JIT_REG + 0)
#define TMP_REG_2 (MAX_BPF_JIT_REG + 1)
36
#define TCALL_CNT (MAX_BPF_JIT_REG + 2)
37
#define TMP_REG_3 (MAX_BPF_JIT_REG + 3)
Zi Shen Lim's avatar
Zi Shen Lim committed
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/* Map BPF registers to A64 registers */
static const int bpf2a64[] = {
	/* return value from in-kernel function, and exit value from eBPF */
	[BPF_REG_0] = A64_R(7),
	/* arguments from eBPF program to in-kernel function */
	[BPF_REG_1] = A64_R(0),
	[BPF_REG_2] = A64_R(1),
	[BPF_REG_3] = A64_R(2),
	[BPF_REG_4] = A64_R(3),
	[BPF_REG_5] = A64_R(4),
	/* callee saved registers that in-kernel function will preserve */
	[BPF_REG_6] = A64_R(19),
	[BPF_REG_7] = A64_R(20),
	[BPF_REG_8] = A64_R(21),
	[BPF_REG_9] = A64_R(22),
	/* read-only frame pointer to access stack */
55
	[BPF_REG_FP] = A64_R(25),
56
57
58
	/* temporary registers for internal BPF JIT */
	[TMP_REG_1] = A64_R(10),
	[TMP_REG_2] = A64_R(11),
59
	[TMP_REG_3] = A64_R(12),
60
61
	/* tail_call_cnt */
	[TCALL_CNT] = A64_R(26),
62
63
	/* temporary register for blinding constants */
	[BPF_REG_AX] = A64_R(9),
Zi Shen Lim's avatar
Zi Shen Lim committed
64
65
66
67
68
};

struct jit_ctx {
	const struct bpf_prog *prog;
	int idx;
69
	int epilogue_offset;
Zi Shen Lim's avatar
Zi Shen Lim committed
70
	int *offset;
71
	__le32 *image;
72
	u32 stack_size;
Zi Shen Lim's avatar
Zi Shen Lim committed
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
};

static inline void emit(const u32 insn, struct jit_ctx *ctx)
{
	if (ctx->image != NULL)
		ctx->image[ctx->idx] = cpu_to_le32(insn);

	ctx->idx++;
}

static inline void emit_a64_mov_i64(const int reg, const u64 val,
				    struct jit_ctx *ctx)
{
	u64 tmp = val;
	int shift = 0;

	emit(A64_MOVZ(1, reg, tmp & 0xffff, shift), ctx);
	tmp >>= 16;
	shift += 16;
	while (tmp) {
		if (tmp & 0xffff)
			emit(A64_MOVK(1, reg, tmp & 0xffff, shift), ctx);
		tmp >>= 16;
		shift += 16;
	}
}

100
101
102
103
104
105
106
107
108
109
110
111
112
113
static inline void emit_addr_mov_i64(const int reg, const u64 val,
				     struct jit_ctx *ctx)
{
	u64 tmp = val;
	int shift = 0;

	emit(A64_MOVZ(1, reg, tmp & 0xffff, shift), ctx);
	for (;shift < 48;) {
		tmp >>= 16;
		shift += 16;
		emit(A64_MOVK(1, reg, tmp & 0xffff, shift), ctx);
	}
}

Zi Shen Lim's avatar
Zi Shen Lim committed
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
static inline void emit_a64_mov_i(const int is64, const int reg,
				  const s32 val, struct jit_ctx *ctx)
{
	u16 hi = val >> 16;
	u16 lo = val & 0xffff;

	if (hi & 0x8000) {
		if (hi == 0xffff) {
			emit(A64_MOVN(is64, reg, (u16)~lo, 0), ctx);
		} else {
			emit(A64_MOVN(is64, reg, (u16)~hi, 16), ctx);
			emit(A64_MOVK(is64, reg, lo, 0), ctx);
		}
	} else {
		emit(A64_MOVZ(is64, reg, lo, 0), ctx);
		if (hi)
			emit(A64_MOVK(is64, reg, hi, 16), ctx);
	}
}

static inline int bpf2a64_offset(int bpf_to, int bpf_from,
				 const struct jit_ctx *ctx)
{
137
	int to = ctx->offset[bpf_to];
Zi Shen Lim's avatar
Zi Shen Lim committed
138
	/* -1 to account for the Branch instruction */
139
	int from = ctx->offset[bpf_from] - 1;
Zi Shen Lim's avatar
Zi Shen Lim committed
140
141
142
143

	return to - from;
}

144
145
static void jit_fill_hole(void *area, unsigned int size)
{
146
	__le32 *ptr;
147
148
149
150
151
	/* We are guaranteed to have aligned memory. */
	for (ptr = area; size >= sizeof(u32); size -= sizeof(u32))
		*ptr++ = cpu_to_le32(AARCH64_BREAK_FAULT);
}

Zi Shen Lim's avatar
Zi Shen Lim committed
152
153
static inline int epilogue_offset(const struct jit_ctx *ctx)
{
154
155
	int to = ctx->epilogue_offset;
	int from = ctx->idx;
Zi Shen Lim's avatar
Zi Shen Lim committed
156
157
158
159
160
161
162

	return to - from;
}

/* Stack must be multiples of 16B */
#define STACK_ALIGN(sz) (((sz) + 15) & ~15)

163
164
/* Tail call offset to jump into */
#define PROLOGUE_OFFSET 7
165
166

static int build_prologue(struct jit_ctx *ctx)
Zi Shen Lim's avatar
Zi Shen Lim committed
167
{
168
	const struct bpf_prog *prog = ctx->prog;
Zi Shen Lim's avatar
Zi Shen Lim committed
169
170
171
172
173
	const u8 r6 = bpf2a64[BPF_REG_6];
	const u8 r7 = bpf2a64[BPF_REG_7];
	const u8 r8 = bpf2a64[BPF_REG_8];
	const u8 r9 = bpf2a64[BPF_REG_9];
	const u8 fp = bpf2a64[BPF_REG_FP];
174
175
176
	const u8 tcc = bpf2a64[TCALL_CNT];
	const int idx0 = ctx->idx;
	int cur_offset;
Zi Shen Lim's avatar
Zi Shen Lim committed
177

178
179
180
181
182
183
184
185
	/*
	 * BPF prog stack layout
	 *
	 *                         high
	 * original A64_SP =>   0:+-----+ BPF prologue
	 *                        |FP/LR|
	 * current A64_FP =>  -16:+-----+
	 *                        | ... | callee saved registers
186
	 * BPF fp register => -64:+-----+ <= (BPF_FP)
187
188
189
	 *                        |     |
	 *                        | ... | BPF prog stack
	 *                        |     |
190
	 *                        +-----+ <= (BPF_FP - prog->aux->stack_depth)
Zi Shen Lim's avatar
Zi Shen Lim committed
191
	 *                        |RSVD | JIT scratchpad
192
	 * current A64_SP =>      +-----+ <= (BPF_FP - ctx->stack_size)
193
194
195
196
197
198
199
200
201
202
203
204
	 *                        |     |
	 *                        | ... | Function call stack
	 *                        |     |
	 *                        +-----+
	 *                          low
	 *
	 */

	/* Save FP and LR registers to stay align with ARM64 AAPCS */
	emit(A64_PUSH(A64_FP, A64_LR, A64_SP), ctx);
	emit(A64_MOV(1, A64_FP, A64_SP), ctx);

205
	/* Save callee-saved registers */
Zi Shen Lim's avatar
Zi Shen Lim committed
206
207
	emit(A64_PUSH(r6, r7, A64_SP), ctx);
	emit(A64_PUSH(r8, r9, A64_SP), ctx);
208
	emit(A64_PUSH(fp, tcc, A64_SP), ctx);
Zi Shen Lim's avatar
Zi Shen Lim committed
209

210
	/* Set up BPF prog stack base register */
Zi Shen Lim's avatar
Zi Shen Lim committed
211
212
	emit(A64_MOV(1, fp, A64_SP), ctx);

213
214
215
216
217
218
219
220
221
	/* Initialize tail_call_cnt */
	emit(A64_MOVZ(1, tcc, 0, 0), ctx);

	cur_offset = ctx->idx - idx0;
	if (cur_offset != PROLOGUE_OFFSET) {
		pr_err_once("PROLOGUE_OFFSET = %d, expected %d!\n",
			    cur_offset, PROLOGUE_OFFSET);
		return -1;
	}
222
223
224
225
226
227
228

	/* 4 byte extra for skb_copy_bits buffer */
	ctx->stack_size = prog->aux->stack_depth + 4;
	ctx->stack_size = STACK_ALIGN(ctx->stack_size);

	/* Set up function call stack */
	emit(A64_SUB_I(1, A64_SP, A64_SP, ctx->stack_size), ctx);
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
	return 0;
}

static int out_offset = -1; /* initialized on the first pass of build_body() */
static int emit_bpf_tail_call(struct jit_ctx *ctx)
{
	/* bpf_tail_call(void *prog_ctx, struct bpf_array *array, u64 index) */
	const u8 r2 = bpf2a64[BPF_REG_2];
	const u8 r3 = bpf2a64[BPF_REG_3];

	const u8 tmp = bpf2a64[TMP_REG_1];
	const u8 prg = bpf2a64[TMP_REG_2];
	const u8 tcc = bpf2a64[TCALL_CNT];
	const int idx0 = ctx->idx;
#define cur_offset (ctx->idx - idx0)
#define jmp_offset (out_offset - (cur_offset))
	size_t off;

	/* if (index >= array->map.max_entries)
	 *     goto out;
	 */
	off = offsetof(struct bpf_array, map.max_entries);
	emit_a64_mov_i64(tmp, off, ctx);
	emit(A64_LDR32(tmp, r2, tmp), ctx);
	emit(A64_CMP(0, r3, tmp), ctx);
	emit(A64_B_(A64_COND_GE, jmp_offset), ctx);

	/* if (tail_call_cnt > MAX_TAIL_CALL_CNT)
	 *     goto out;
	 * tail_call_cnt++;
	 */
	emit_a64_mov_i64(tmp, MAX_TAIL_CALL_CNT, ctx);
	emit(A64_CMP(1, tcc, tmp), ctx);
	emit(A64_B_(A64_COND_GT, jmp_offset), ctx);
	emit(A64_ADD_I(1, tcc, tcc, 1), ctx);

	/* prog = array->ptrs[index];
	 * if (prog == NULL)
	 *     goto out;
	 */
	off = offsetof(struct bpf_array, ptrs);
	emit_a64_mov_i64(tmp, off, ctx);
271
272
273
	emit(A64_ADD(1, tmp, r2, tmp), ctx);
	emit(A64_LSL(1, prg, r3, 3), ctx);
	emit(A64_LDR64(prg, tmp, prg), ctx);
274
275
	emit(A64_CBZ(1, prg, jmp_offset), ctx);

276
	/* goto *(prog->bpf_func + prologue_offset); */
277
278
279
280
	off = offsetof(struct bpf_prog, bpf_func);
	emit_a64_mov_i64(tmp, off, ctx);
	emit(A64_LDR64(tmp, prg, tmp), ctx);
	emit(A64_ADD_I(1, tmp, tmp, sizeof(u32) * PROLOGUE_OFFSET), ctx);
281
	emit(A64_ADD_I(1, A64_SP, A64_SP, ctx->stack_size), ctx);
282
283
284
285
286
287
288
289
290
291
292
293
294
	emit(A64_BR(tmp), ctx);

	/* out: */
	if (out_offset == -1)
		out_offset = cur_offset;
	if (cur_offset != out_offset) {
		pr_err_once("tail_call out_offset = %d, expected %d!\n",
			    cur_offset, out_offset);
		return -1;
	}
	return 0;
#undef cur_offset
#undef jmp_offset
Zi Shen Lim's avatar
Zi Shen Lim committed
295
296
297
298
299
300
301
302
303
304
305
306
}

static void build_epilogue(struct jit_ctx *ctx)
{
	const u8 r0 = bpf2a64[BPF_REG_0];
	const u8 r6 = bpf2a64[BPF_REG_6];
	const u8 r7 = bpf2a64[BPF_REG_7];
	const u8 r8 = bpf2a64[BPF_REG_8];
	const u8 r9 = bpf2a64[BPF_REG_9];
	const u8 fp = bpf2a64[BPF_REG_FP];

	/* We're done with BPF stack */
307
	emit(A64_ADD_I(1, A64_SP, A64_SP, ctx->stack_size), ctx);
Zi Shen Lim's avatar
Zi Shen Lim committed
308

309
310
311
	/* Restore fs (x25) and x26 */
	emit(A64_POP(fp, A64_R(26), A64_SP), ctx);

Zi Shen Lim's avatar
Zi Shen Lim committed
312
313
314
315
	/* Restore callee-saved register */
	emit(A64_POP(r8, r9, A64_SP), ctx);
	emit(A64_POP(r6, r7, A64_SP), ctx);

316
317
	/* Restore FP/LR registers */
	emit(A64_POP(A64_FP, A64_LR, A64_SP), ctx);
Zi Shen Lim's avatar
Zi Shen Lim committed
318
319
320
321
322
323
324

	/* Set return value */
	emit(A64_MOV(1, A64_R(0), r0), ctx);

	emit(A64_RET(A64_LR), ctx);
}

325
326
327
328
329
330
/* JITs an eBPF instruction.
 * Returns:
 * 0  - successfully JITed an 8-byte eBPF instruction.
 * >0 - successfully JITed a 16-byte eBPF instruction.
 * <0 - failed to JIT.
 */
Zi Shen Lim's avatar
Zi Shen Lim committed
331
332
333
334
335
336
337
static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)
{
	const u8 code = insn->code;
	const u8 dst = bpf2a64[insn->dst_reg];
	const u8 src = bpf2a64[insn->src_reg];
	const u8 tmp = bpf2a64[TMP_REG_1];
	const u8 tmp2 = bpf2a64[TMP_REG_2];
338
	const u8 tmp3 = bpf2a64[TMP_REG_3];
Zi Shen Lim's avatar
Zi Shen Lim committed
339
340
341
342
	const s16 off = insn->off;
	const s32 imm = insn->imm;
	const int i = insn - ctx->prog->insnsi;
	const bool is64 = BPF_CLASS(code) == BPF_ALU64;
343
	const bool isdw = BPF_SIZE(code) == BPF_DW;
Zi Shen Lim's avatar
Zi Shen Lim committed
344
345
346
	u8 jmp_cond;
	s32 jmp_offset;

Zi Shen Lim's avatar
Zi Shen Lim committed
347
348
349
350
351
352
353
354
355
356
357
#define check_imm(bits, imm) do {				\
	if ((((imm) > 0) && ((imm) >> (bits))) ||		\
	    (((imm) < 0) && (~(imm) >> (bits)))) {		\
		pr_info("[%2d] imm=%d(0x%x) out of range\n",	\
			i, imm, imm);				\
		return -EINVAL;					\
	}							\
} while (0)
#define check_imm19(imm) check_imm(19, imm)
#define check_imm26(imm) check_imm(26, imm)

Zi Shen Lim's avatar
Zi Shen Lim committed
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
	switch (code) {
	/* dst = src */
	case BPF_ALU | BPF_MOV | BPF_X:
	case BPF_ALU64 | BPF_MOV | BPF_X:
		emit(A64_MOV(is64, dst, src), ctx);
		break;
	/* dst = dst OP src */
	case BPF_ALU | BPF_ADD | BPF_X:
	case BPF_ALU64 | BPF_ADD | BPF_X:
		emit(A64_ADD(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_SUB | BPF_X:
	case BPF_ALU64 | BPF_SUB | BPF_X:
		emit(A64_SUB(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_AND | BPF_X:
	case BPF_ALU64 | BPF_AND | BPF_X:
		emit(A64_AND(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_OR | BPF_X:
	case BPF_ALU64 | BPF_OR | BPF_X:
		emit(A64_ORR(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_XOR | BPF_X:
	case BPF_ALU64 | BPF_XOR | BPF_X:
		emit(A64_EOR(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_MUL | BPF_X:
	case BPF_ALU64 | BPF_MUL | BPF_X:
		emit(A64_MUL(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_DIV | BPF_X:
	case BPF_ALU64 | BPF_DIV | BPF_X:
	case BPF_ALU | BPF_MOD | BPF_X:
	case BPF_ALU64 | BPF_MOD | BPF_X:
Zi Shen Lim's avatar
Zi Shen Lim committed
393
394
395
396
397
398
399
400
401
402
		switch (BPF_OP(code)) {
		case BPF_DIV:
			emit(A64_UDIV(is64, dst, dst, src), ctx);
			break;
		case BPF_MOD:
			emit(A64_UDIV(is64, tmp, dst, src), ctx);
			emit(A64_MUL(is64, tmp, tmp, src), ctx);
			emit(A64_SUB(is64, dst, dst, tmp), ctx);
			break;
		}
Zi Shen Lim's avatar
Zi Shen Lim committed
403
		break;
404
405
406
407
408
409
410
411
412
413
414
415
	case BPF_ALU | BPF_LSH | BPF_X:
	case BPF_ALU64 | BPF_LSH | BPF_X:
		emit(A64_LSLV(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_RSH | BPF_X:
	case BPF_ALU64 | BPF_RSH | BPF_X:
		emit(A64_LSRV(is64, dst, dst, src), ctx);
		break;
	case BPF_ALU | BPF_ARSH | BPF_X:
	case BPF_ALU64 | BPF_ARSH | BPF_X:
		emit(A64_ASRV(is64, dst, dst, src), ctx);
		break;
Zi Shen Lim's avatar
Zi Shen Lim committed
416
417
418
419
420
421
422
423
424
425
	/* dst = -dst */
	case BPF_ALU | BPF_NEG:
	case BPF_ALU64 | BPF_NEG:
		emit(A64_NEG(is64, dst, dst), ctx);
		break;
	/* dst = BSWAP##imm(dst) */
	case BPF_ALU | BPF_END | BPF_FROM_LE:
	case BPF_ALU | BPF_END | BPF_FROM_BE:
#ifdef CONFIG_CPU_BIG_ENDIAN
		if (BPF_SRC(code) == BPF_FROM_BE)
426
			goto emit_bswap_uxt;
Zi Shen Lim's avatar
Zi Shen Lim committed
427
428
#else /* !CONFIG_CPU_BIG_ENDIAN */
		if (BPF_SRC(code) == BPF_FROM_LE)
429
			goto emit_bswap_uxt;
Zi Shen Lim's avatar
Zi Shen Lim committed
430
431
432
433
#endif
		switch (imm) {
		case 16:
			emit(A64_REV16(is64, dst, dst), ctx);
434
435
			/* zero-extend 16 bits into 64 bits */
			emit(A64_UXTH(is64, dst, dst), ctx);
Zi Shen Lim's avatar
Zi Shen Lim committed
436
437
438
			break;
		case 32:
			emit(A64_REV32(is64, dst, dst), ctx);
439
			/* upper 32 bits already cleared */
Zi Shen Lim's avatar
Zi Shen Lim committed
440
441
442
443
444
445
			break;
		case 64:
			emit(A64_REV64(dst, dst), ctx);
			break;
		}
		break;
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
emit_bswap_uxt:
		switch (imm) {
		case 16:
			/* zero-extend 16 bits into 64 bits */
			emit(A64_UXTH(is64, dst, dst), ctx);
			break;
		case 32:
			/* zero-extend 32 bits into 64 bits */
			emit(A64_UXTW(is64, dst, dst), ctx);
			break;
		case 64:
			/* nop */
			break;
		}
		break;
Zi Shen Lim's avatar
Zi Shen Lim committed
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
	/* dst = imm */
	case BPF_ALU | BPF_MOV | BPF_K:
	case BPF_ALU64 | BPF_MOV | BPF_K:
		emit_a64_mov_i(is64, dst, imm, ctx);
		break;
	/* dst = dst OP imm */
	case BPF_ALU | BPF_ADD | BPF_K:
	case BPF_ALU64 | BPF_ADD | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_ADD(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_SUB | BPF_K:
	case BPF_ALU64 | BPF_SUB | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_SUB(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_AND | BPF_K:
	case BPF_ALU64 | BPF_AND | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_AND(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_OR | BPF_K:
	case BPF_ALU64 | BPF_OR | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_ORR(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_XOR | BPF_K:
	case BPF_ALU64 | BPF_XOR | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_EOR(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_MUL | BPF_K:
	case BPF_ALU64 | BPF_MUL | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_MUL(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_DIV | BPF_K:
	case BPF_ALU64 | BPF_DIV | BPF_K:
		emit_a64_mov_i(is64, tmp, imm, ctx);
		emit(A64_UDIV(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_MOD | BPF_K:
	case BPF_ALU64 | BPF_MOD | BPF_K:
		emit_a64_mov_i(is64, tmp2, imm, ctx);
		emit(A64_UDIV(is64, tmp, dst, tmp2), ctx);
		emit(A64_MUL(is64, tmp, tmp, tmp2), ctx);
		emit(A64_SUB(is64, dst, dst, tmp), ctx);
		break;
	case BPF_ALU | BPF_LSH | BPF_K:
	case BPF_ALU64 | BPF_LSH | BPF_K:
		emit(A64_LSL(is64, dst, dst, imm), ctx);
		break;
	case BPF_ALU | BPF_RSH | BPF_K:
	case BPF_ALU64 | BPF_RSH | BPF_K:
		emit(A64_LSR(is64, dst, dst, imm), ctx);
		break;
	case BPF_ALU | BPF_ARSH | BPF_K:
	case BPF_ALU64 | BPF_ARSH | BPF_K:
		emit(A64_ASR(is64, dst, dst, imm), ctx);
		break;

	/* JUMP off */
	case BPF_JMP | BPF_JA:
		jmp_offset = bpf2a64_offset(i + off, i, ctx);
		check_imm26(jmp_offset);
		emit(A64_B(jmp_offset), ctx);
		break;
	/* IF (dst COND src) JUMP off */
	case BPF_JMP | BPF_JEQ | BPF_X:
	case BPF_JMP | BPF_JGT | BPF_X:
531
	case BPF_JMP | BPF_JLT | BPF_X:
Zi Shen Lim's avatar
Zi Shen Lim committed
532
	case BPF_JMP | BPF_JGE | BPF_X:
533
	case BPF_JMP | BPF_JLE | BPF_X:
Zi Shen Lim's avatar
Zi Shen Lim committed
534
535
	case BPF_JMP | BPF_JNE | BPF_X:
	case BPF_JMP | BPF_JSGT | BPF_X:
536
	case BPF_JMP | BPF_JSLT | BPF_X:
Zi Shen Lim's avatar
Zi Shen Lim committed
537
	case BPF_JMP | BPF_JSGE | BPF_X:
538
	case BPF_JMP | BPF_JSLE | BPF_X:
Zi Shen Lim's avatar
Zi Shen Lim committed
539
540
541
542
543
544
545
546
547
548
549
		emit(A64_CMP(1, dst, src), ctx);
emit_cond_jmp:
		jmp_offset = bpf2a64_offset(i + off, i, ctx);
		check_imm19(jmp_offset);
		switch (BPF_OP(code)) {
		case BPF_JEQ:
			jmp_cond = A64_COND_EQ;
			break;
		case BPF_JGT:
			jmp_cond = A64_COND_HI;
			break;
550
551
552
		case BPF_JLT:
			jmp_cond = A64_COND_CC;
			break;
Zi Shen Lim's avatar
Zi Shen Lim committed
553
554
555
		case BPF_JGE:
			jmp_cond = A64_COND_CS;
			break;
556
557
558
		case BPF_JLE:
			jmp_cond = A64_COND_LS;
			break;
Zi Shen Lim's avatar
Zi Shen Lim committed
559
		case BPF_JSET:
Zi Shen Lim's avatar
Zi Shen Lim committed
560
561
562
563
564
565
		case BPF_JNE:
			jmp_cond = A64_COND_NE;
			break;
		case BPF_JSGT:
			jmp_cond = A64_COND_GT;
			break;
566
567
568
		case BPF_JSLT:
			jmp_cond = A64_COND_LT;
			break;
Zi Shen Lim's avatar
Zi Shen Lim committed
569
570
571
		case BPF_JSGE:
			jmp_cond = A64_COND_GE;
			break;
572
573
574
		case BPF_JSLE:
			jmp_cond = A64_COND_LE;
			break;
Zi Shen Lim's avatar
Zi Shen Lim committed
575
576
577
578
579
580
581
582
583
584
585
		default:
			return -EFAULT;
		}
		emit(A64_B_(jmp_cond, jmp_offset), ctx);
		break;
	case BPF_JMP | BPF_JSET | BPF_X:
		emit(A64_TST(1, dst, src), ctx);
		goto emit_cond_jmp;
	/* IF (dst COND imm) JUMP off */
	case BPF_JMP | BPF_JEQ | BPF_K:
	case BPF_JMP | BPF_JGT | BPF_K:
586
	case BPF_JMP | BPF_JLT | BPF_K:
Zi Shen Lim's avatar
Zi Shen Lim committed
587
	case BPF_JMP | BPF_JGE | BPF_K:
588
	case BPF_JMP | BPF_JLE | BPF_K:
Zi Shen Lim's avatar
Zi Shen Lim committed
589
590
	case BPF_JMP | BPF_JNE | BPF_K:
	case BPF_JMP | BPF_JSGT | BPF_K:
591
	case BPF_JMP | BPF_JSLT | BPF_K:
Zi Shen Lim's avatar
Zi Shen Lim committed
592
	case BPF_JMP | BPF_JSGE | BPF_K:
593
	case BPF_JMP | BPF_JSLE | BPF_K:
Zi Shen Lim's avatar
Zi Shen Lim committed
594
595
596
597
598
599
600
601
602
603
604
605
606
		emit_a64_mov_i(1, tmp, imm, ctx);
		emit(A64_CMP(1, dst, tmp), ctx);
		goto emit_cond_jmp;
	case BPF_JMP | BPF_JSET | BPF_K:
		emit_a64_mov_i(1, tmp, imm, ctx);
		emit(A64_TST(1, dst, tmp), ctx);
		goto emit_cond_jmp;
	/* function call */
	case BPF_JMP | BPF_CALL:
	{
		const u8 r0 = bpf2a64[BPF_REG_0];
		const u64 func = (u64)__bpf_call_base + imm;

607
608
609
610
		if (ctx->prog->is_func)
			emit_addr_mov_i64(tmp, func, ctx);
		else
			emit_a64_mov_i64(tmp, func, ctx);
Zi Shen Lim's avatar
Zi Shen Lim committed
611
612
613
614
		emit(A64_BLR(tmp), ctx);
		emit(A64_MOV(1, r0, A64_R(0)), ctx);
		break;
	}
615
	/* tail call */
616
	case BPF_JMP | BPF_TAIL_CALL:
617
618
619
		if (emit_bpf_tail_call(ctx))
			return -EFAULT;
		break;
Zi Shen Lim's avatar
Zi Shen Lim committed
620
621
	/* function return */
	case BPF_JMP | BPF_EXIT:
622
623
		/* Optimization: when last instruction is EXIT,
		   simply fallthrough to epilogue. */
Zi Shen Lim's avatar
Zi Shen Lim committed
624
625
626
627
628
629
630
		if (i == ctx->prog->len - 1)
			break;
		jmp_offset = epilogue_offset(ctx);
		check_imm26(jmp_offset);
		emit(A64_B(jmp_offset), ctx);
		break;

631
632
633
634
635
636
	/* dst = imm64 */
	case BPF_LD | BPF_IMM | BPF_DW:
	{
		const struct bpf_insn insn1 = insn[1];
		u64 imm64;

637
		imm64 = (u64)insn1.imm << 32 | (u32)imm;
638
639
640
641
642
		emit_a64_mov_i64(dst, imm64, ctx);

		return 1;
	}

Zi Shen Lim's avatar
Zi Shen Lim committed
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
	/* LDX: dst = *(size *)(src + off) */
	case BPF_LDX | BPF_MEM | BPF_W:
	case BPF_LDX | BPF_MEM | BPF_H:
	case BPF_LDX | BPF_MEM | BPF_B:
	case BPF_LDX | BPF_MEM | BPF_DW:
		emit_a64_mov_i(1, tmp, off, ctx);
		switch (BPF_SIZE(code)) {
		case BPF_W:
			emit(A64_LDR32(dst, src, tmp), ctx);
			break;
		case BPF_H:
			emit(A64_LDRH(dst, src, tmp), ctx);
			break;
		case BPF_B:
			emit(A64_LDRB(dst, src, tmp), ctx);
			break;
		case BPF_DW:
			emit(A64_LDR64(dst, src, tmp), ctx);
			break;
		}
		break;

	/* ST: *(size *)(dst + off) = imm */
	case BPF_ST | BPF_MEM | BPF_W:
	case BPF_ST | BPF_MEM | BPF_H:
	case BPF_ST | BPF_MEM | BPF_B:
	case BPF_ST | BPF_MEM | BPF_DW:
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
		/* Load imm to a register then store it */
		emit_a64_mov_i(1, tmp2, off, ctx);
		emit_a64_mov_i(1, tmp, imm, ctx);
		switch (BPF_SIZE(code)) {
		case BPF_W:
			emit(A64_STR32(tmp, dst, tmp2), ctx);
			break;
		case BPF_H:
			emit(A64_STRH(tmp, dst, tmp2), ctx);
			break;
		case BPF_B:
			emit(A64_STRB(tmp, dst, tmp2), ctx);
			break;
		case BPF_DW:
			emit(A64_STR64(tmp, dst, tmp2), ctx);
			break;
		}
		break;
Zi Shen Lim's avatar
Zi Shen Lim committed
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713

	/* STX: *(size *)(dst + off) = src */
	case BPF_STX | BPF_MEM | BPF_W:
	case BPF_STX | BPF_MEM | BPF_H:
	case BPF_STX | BPF_MEM | BPF_B:
	case BPF_STX | BPF_MEM | BPF_DW:
		emit_a64_mov_i(1, tmp, off, ctx);
		switch (BPF_SIZE(code)) {
		case BPF_W:
			emit(A64_STR32(src, dst, tmp), ctx);
			break;
		case BPF_H:
			emit(A64_STRH(src, dst, tmp), ctx);
			break;
		case BPF_B:
			emit(A64_STRB(src, dst, tmp), ctx);
			break;
		case BPF_DW:
			emit(A64_STR64(src, dst, tmp), ctx);
			break;
		}
		break;
	/* STX XADD: lock *(u32 *)(dst + off) += src */
	case BPF_STX | BPF_XADD | BPF_W:
	/* STX XADD: lock *(u64 *)(dst + off) += src */
	case BPF_STX | BPF_XADD | BPF_DW:
714
715
716
717
718
		emit_a64_mov_i(1, tmp, off, ctx);
		emit(A64_ADD(1, tmp, tmp, dst), ctx);
		emit(A64_PRFM(tmp, PST, L1, STRM), ctx);
		emit(A64_LDXR(isdw, tmp2, tmp), ctx);
		emit(A64_ADD(isdw, tmp2, tmp2, src), ctx);
719
		emit(A64_STXR(isdw, tmp2, tmp, tmp3), ctx);
720
721
		jmp_offset = -3;
		check_imm19(jmp_offset);
722
		emit(A64_CBNZ(0, tmp3, jmp_offset), ctx);
723
		break;
Zi Shen Lim's avatar
Zi Shen Lim committed
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761

	/* R0 = ntohx(*(size *)(((struct sk_buff *)R6)->data + imm)) */
	case BPF_LD | BPF_ABS | BPF_W:
	case BPF_LD | BPF_ABS | BPF_H:
	case BPF_LD | BPF_ABS | BPF_B:
	/* R0 = ntohx(*(size *)(((struct sk_buff *)R6)->data + src + imm)) */
	case BPF_LD | BPF_IND | BPF_W:
	case BPF_LD | BPF_IND | BPF_H:
	case BPF_LD | BPF_IND | BPF_B:
	{
		const u8 r0 = bpf2a64[BPF_REG_0]; /* r0 = return value */
		const u8 r6 = bpf2a64[BPF_REG_6]; /* r6 = pointer to sk_buff */
		const u8 fp = bpf2a64[BPF_REG_FP];
		const u8 r1 = bpf2a64[BPF_REG_1]; /* r1: struct sk_buff *skb */
		const u8 r2 = bpf2a64[BPF_REG_2]; /* r2: int k */
		const u8 r3 = bpf2a64[BPF_REG_3]; /* r3: unsigned int size */
		const u8 r4 = bpf2a64[BPF_REG_4]; /* r4: void *buffer */
		const u8 r5 = bpf2a64[BPF_REG_5]; /* r5: void *(*func)(...) */
		int size;

		emit(A64_MOV(1, r1, r6), ctx);
		emit_a64_mov_i(0, r2, imm, ctx);
		if (BPF_MODE(code) == BPF_IND)
			emit(A64_ADD(0, r2, r2, src), ctx);
		switch (BPF_SIZE(code)) {
		case BPF_W:
			size = 4;
			break;
		case BPF_H:
			size = 2;
			break;
		case BPF_B:
			size = 1;
			break;
		default:
			return -EINVAL;
		}
		emit_a64_mov_i64(r3, size, ctx);
762
		emit(A64_SUB_I(1, r4, fp, ctx->stack_size), ctx);
Zi Shen Lim's avatar
Zi Shen Lim committed
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
		emit_a64_mov_i64(r5, (unsigned long)bpf_load_pointer, ctx);
		emit(A64_BLR(r5), ctx);
		emit(A64_MOV(1, r0, A64_R(0)), ctx);

		jmp_offset = epilogue_offset(ctx);
		check_imm19(jmp_offset);
		emit(A64_CBZ(1, r0, jmp_offset), ctx);
		emit(A64_MOV(1, r5, r0), ctx);
		switch (BPF_SIZE(code)) {
		case BPF_W:
			emit(A64_LDR32(r0, r5, A64_ZR), ctx);
#ifndef CONFIG_CPU_BIG_ENDIAN
			emit(A64_REV32(0, r0, r0), ctx);
#endif
			break;
		case BPF_H:
			emit(A64_LDRH(r0, r5, A64_ZR), ctx);
#ifndef CONFIG_CPU_BIG_ENDIAN
			emit(A64_REV16(0, r0, r0), ctx);
#endif
			break;
		case BPF_B:
			emit(A64_LDRB(r0, r5, A64_ZR), ctx);
			break;
		}
		break;
	}
	default:
		pr_err_once("unknown opcode %02x\n", code);
		return -EINVAL;
	}

	return 0;
}

static int build_body(struct jit_ctx *ctx)
{
	const struct bpf_prog *prog = ctx->prog;
	int i;

	for (i = 0; i < prog->len; i++) {
		const struct bpf_insn *insn = &prog->insnsi[i];
		int ret;

807
		ret = build_insn(insn, ctx);
808
809
		if (ret > 0) {
			i++;
810
811
			if (ctx->image == NULL)
				ctx->offset[i] = ctx->idx;
812
813
			continue;
		}
814
815
		if (ctx->image == NULL)
			ctx->offset[i] = ctx->idx;
Zi Shen Lim's avatar
Zi Shen Lim committed
816
817
818
819
820
821
822
		if (ret)
			return ret;
	}

	return 0;
}

823
824
825
826
827
828
829
830
831
832
833
834
835
836
static int validate_code(struct jit_ctx *ctx)
{
	int i;

	for (i = 0; i < ctx->idx; i++) {
		u32 a64_insn = le32_to_cpu(ctx->image[i]);

		if (a64_insn == AARCH64_BREAK_FAULT)
			return -1;
	}

	return 0;
}

Zi Shen Lim's avatar
Zi Shen Lim committed
837
838
839
840
841
static inline void bpf_flush_icache(void *start, void *end)
{
	flush_icache_range((unsigned long)start, (unsigned long)end);
}

842
843
844
845
846
847
struct arm64_jit_data {
	struct bpf_binary_header *header;
	u8 *image;
	struct jit_ctx ctx;
};

848
struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
Zi Shen Lim's avatar
Zi Shen Lim committed
849
{
850
	struct bpf_prog *tmp, *orig_prog = prog;
851
	struct bpf_binary_header *header;
852
	struct arm64_jit_data *jit_data;
853
	bool tmp_blinded = false;
854
	bool extra_pass = false;
Zi Shen Lim's avatar
Zi Shen Lim committed
855
856
	struct jit_ctx ctx;
	int image_size;
857
	u8 *image_ptr;
Zi Shen Lim's avatar
Zi Shen Lim committed
858

859
	if (!prog->jit_requested)
860
861
862
863
864
865
866
867
868
869
870
871
		return orig_prog;

	tmp = bpf_jit_blind_constants(prog);
	/* If blinding was requested and we failed during blinding,
	 * we must fall back to the interpreter.
	 */
	if (IS_ERR(tmp))
		return orig_prog;
	if (tmp != prog) {
		tmp_blinded = true;
		prog = tmp;
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
872

873
874
875
876
877
878
879
880
881
882
883
884
885
886
	jit_data = prog->aux->jit_data;
	if (!jit_data) {
		jit_data = kzalloc(sizeof(*jit_data), GFP_KERNEL);
		if (!jit_data) {
			prog = orig_prog;
			goto out;
		}
		prog->aux->jit_data = jit_data;
	}
	if (jit_data->ctx.offset) {
		ctx = jit_data->ctx;
		image_ptr = jit_data->image;
		header = jit_data->header;
		extra_pass = true;
887
		image_size = sizeof(u32) * ctx.idx;
888
889
		goto skip_init_ctx;
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
890
891
892
893
	memset(&ctx, 0, sizeof(ctx));
	ctx.prog = prog;

	ctx.offset = kcalloc(prog->len, sizeof(int), GFP_KERNEL);
894
895
	if (ctx.offset == NULL) {
		prog = orig_prog;
896
		goto out_off;
897
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
898
899
900

	/* 1. Initial fake pass to compute ctx->idx. */

901
	/* Fake pass to fill in ctx->offset. */
902
903
904
905
	if (build_body(&ctx)) {
		prog = orig_prog;
		goto out_off;
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
906

907
908
909
910
	if (build_prologue(&ctx)) {
		prog = orig_prog;
		goto out_off;
	}
911
912

	ctx.epilogue_offset = ctx.idx;
Zi Shen Lim's avatar
Zi Shen Lim committed
913
914
915
916
	build_epilogue(&ctx);

	/* Now we know the actual image size. */
	image_size = sizeof(u32) * ctx.idx;
917
918
	header = bpf_jit_binary_alloc(image_size, &image_ptr,
				      sizeof(u32), jit_fill_hole);
919
920
921
922
	if (header == NULL) {
		prog = orig_prog;
		goto out_off;
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
923
924
925

	/* 2. Now, the actual pass. */

926
	ctx.image = (__le32 *)image_ptr;
927
skip_init_ctx:
Zi Shen Lim's avatar
Zi Shen Lim committed
928
	ctx.idx = 0;
929

Zi Shen Lim's avatar
Zi Shen Lim committed
930
931
	build_prologue(&ctx);

932
	if (build_body(&ctx)) {
933
		bpf_jit_binary_free(header);
934
935
		prog = orig_prog;
		goto out_off;
936
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
937
938
939

	build_epilogue(&ctx);

940
941
942
	/* 3. Extra pass to validate JITed code. */
	if (validate_code(&ctx)) {
		bpf_jit_binary_free(header);
943
944
		prog = orig_prog;
		goto out_off;
945
946
	}

Zi Shen Lim's avatar
Zi Shen Lim committed
947
948
949
950
	/* And we're done. */
	if (bpf_jit_enable > 1)
		bpf_jit_dump(prog->len, image_size, 2, ctx.image);

951
	bpf_flush_icache(header, ctx.image + ctx.idx);
952

953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
	if (!prog->is_func || extra_pass) {
		if (extra_pass && ctx.idx != jit_data->ctx.idx) {
			pr_err_once("multi-func JIT bug %d != %d\n",
				    ctx.idx, jit_data->ctx.idx);
			bpf_jit_binary_free(header);
			prog->bpf_func = NULL;
			prog->jited = 0;
			goto out_off;
		}
		bpf_jit_binary_lock_ro(header);
	} else {
		jit_data->ctx = ctx;
		jit_data->image = image_ptr;
		jit_data->header = header;
	}
Zi Shen Lim's avatar
Zi Shen Lim committed
968
	prog->bpf_func = (void *)ctx.image;
969
	prog->jited = 1;
970
	prog->jited_len = image_size;
971

972
	if (!prog->is_func || extra_pass) {
973
out_off:
974
975
976
977
		kfree(ctx.offset);
		kfree(jit_data);
		prog->aux->jit_data = NULL;
	}
978
979
980
981
out:
	if (tmp_blinded)
		bpf_jit_prog_release_other(prog, prog == orig_prog ?
					   tmp : orig_prog);
982
	return prog;
Zi Shen Lim's avatar
Zi Shen Lim committed
983
}