bpf_jit_32.c 22.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * Just-In-Time compiler for BPF filters on 32bit ARM
 *
 * Copyright (c) 2011 Mircea Gherzan <mgherzan@gmail.com>
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; version 2 of the License.
 */

#include <linux/bitops.h>
#include <linux/compiler.h>
#include <linux/errno.h>
#include <linux/filter.h>
#include <linux/moduleloader.h>
#include <linux/netdevice.h>
#include <linux/string.h>
#include <linux/slab.h>
19
#include <linux/if_vlan.h>
20 21
#include <asm/cacheflush.h>
#include <asm/hwcap.h>
22
#include <asm/opcodes.h>
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include "bpf_jit_32.h"

/*
 * ABI:
 *
 * r0	scratch register
 * r4	BPF register A
 * r5	BPF register X
 * r6	pointer to the skb
 * r7	skb->data
 * r8	skb_headlen(skb)
 */

#define r_scratch	ARM_R0
/* r1-r3 are (also) used for the unaligned loads on the non-ARMv7 slowpath */
#define r_off		ARM_R1
#define r_A		ARM_R4
#define r_X		ARM_R5
#define r_skb		ARM_R6
#define r_skb_data	ARM_R7
#define r_skb_hl	ARM_R8

#define SCRATCH_SP_OFFSET	0
47
#define SCRATCH_OFF(k)		(SCRATCH_SP_OFFSET + 4 * (k))
48 49 50 51 52 53 54 55 56 57 58

#define SEEN_MEM		((1 << BPF_MEMWORDS) - 1)
#define SEEN_MEM_WORD(k)	(1 << (k))
#define SEEN_X			(1 << BPF_MEMWORDS)
#define SEEN_CALL		(1 << (BPF_MEMWORDS + 1))
#define SEEN_SKB		(1 << (BPF_MEMWORDS + 2))
#define SEEN_DATA		(1 << (BPF_MEMWORDS + 3))

#define FLAG_NEED_X_RESET	(1 << 0)

struct jit_ctx {
59
	const struct bpf_prog *skf;
60 61 62 63 64 65 66 67 68 69 70 71 72 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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
	unsigned idx;
	unsigned prologue_bytes;
	int ret0_fp_idx;
	u32 seen;
	u32 flags;
	u32 *offsets;
	u32 *target;
#if __LINUX_ARM_ARCH__ < 7
	u16 epilogue_bytes;
	u16 imm_count;
	u32 *imms;
#endif
};

int bpf_jit_enable __read_mostly;

static u64 jit_get_skb_b(struct sk_buff *skb, unsigned offset)
{
	u8 ret;
	int err;

	err = skb_copy_bits(skb, offset, &ret, 1);

	return (u64)err << 32 | ret;
}

static u64 jit_get_skb_h(struct sk_buff *skb, unsigned offset)
{
	u16 ret;
	int err;

	err = skb_copy_bits(skb, offset, &ret, 2);

	return (u64)err << 32 | ntohs(ret);
}

static u64 jit_get_skb_w(struct sk_buff *skb, unsigned offset)
{
	u32 ret;
	int err;

	err = skb_copy_bits(skb, offset, &ret, 4);

	return (u64)err << 32 | ntohl(ret);
}

/*
 * Wrapper that handles both OABI and EABI and assures Thumb2 interworking
 * (where the assembly routines like __aeabi_uidiv could cause problems).
 */
static u32 jit_udiv(u32 dividend, u32 divisor)
{
	return dividend / divisor;
}

static inline void _emit(int cond, u32 inst, struct jit_ctx *ctx)
{
117 118 119
	inst |= (cond << 28);
	inst = __opcode_to_mem_arm(inst);

120
	if (ctx->target != NULL)
121
		ctx->target[ctx->idx] = inst;
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

	ctx->idx++;
}

/*
 * Emit an instruction that will be executed unconditionally.
 */
static inline void emit(u32 inst, struct jit_ctx *ctx)
{
	_emit(ARM_COND_AL, inst, ctx);
}

static u16 saved_regs(struct jit_ctx *ctx)
{
	u16 ret = 0;

	if ((ctx->skf->len > 1) ||
139
	    (ctx->skf->insns[0].code == (BPF_RET | BPF_A)))
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
		ret |= 1 << r_A;

#ifdef CONFIG_FRAME_POINTER
	ret |= (1 << ARM_FP) | (1 << ARM_IP) | (1 << ARM_LR) | (1 << ARM_PC);
#else
	if (ctx->seen & SEEN_CALL)
		ret |= 1 << ARM_LR;
#endif
	if (ctx->seen & (SEEN_DATA | SEEN_SKB))
		ret |= 1 << r_skb;
	if (ctx->seen & SEEN_DATA)
		ret |= (1 << r_skb_data) | (1 << r_skb_hl);
	if (ctx->seen & SEEN_X)
		ret |= 1 << r_X;

	return ret;
}

static inline int mem_words_used(struct jit_ctx *ctx)
{
	/* yes, we do waste some stack space IF there are "holes" in the set" */
	return fls(ctx->seen & SEEN_MEM);
}

static inline bool is_load_to_a(u16 inst)
{
	switch (inst) {
167 168 169 170
	case BPF_LD | BPF_W | BPF_LEN:
	case BPF_LD | BPF_W | BPF_ABS:
	case BPF_LD | BPF_H | BPF_ABS:
	case BPF_LD | BPF_B | BPF_ABS:
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
		return true;
	default:
		return false;
	}
}

static void build_prologue(struct jit_ctx *ctx)
{
	u16 reg_set = saved_regs(ctx);
	u16 first_inst = ctx->skf->insns[0].code;
	u16 off;

#ifdef CONFIG_FRAME_POINTER
	emit(ARM_MOV_R(ARM_IP, ARM_SP), ctx);
	emit(ARM_PUSH(reg_set), ctx);
	emit(ARM_SUB_I(ARM_FP, ARM_IP, 4), ctx);
#else
	if (reg_set)
		emit(ARM_PUSH(reg_set), ctx);
#endif

	if (ctx->seen & (SEEN_DATA | SEEN_SKB))
		emit(ARM_MOV_R(r_skb, ARM_R0), ctx);

	if (ctx->seen & SEEN_DATA) {
		off = offsetof(struct sk_buff, data);
		emit(ARM_LDR_I(r_skb_data, r_skb, off), ctx);
		/* headlen = len - data_len */
		off = offsetof(struct sk_buff, len);
		emit(ARM_LDR_I(r_skb_hl, r_skb, off), ctx);
		off = offsetof(struct sk_buff, data_len);
		emit(ARM_LDR_I(r_scratch, r_skb, off), ctx);
		emit(ARM_SUB_R(r_skb_hl, r_skb_hl, r_scratch), ctx);
	}

	if (ctx->flags & FLAG_NEED_X_RESET)
		emit(ARM_MOV_I(r_X, 0), ctx);

	/* do not leak kernel data to userspace */
210
	if ((first_inst != (BPF_RET | BPF_K)) && !(is_load_to_a(first_inst)))
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 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 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339
		emit(ARM_MOV_I(r_A, 0), ctx);

	/* stack space for the BPF_MEM words */
	if (ctx->seen & SEEN_MEM)
		emit(ARM_SUB_I(ARM_SP, ARM_SP, mem_words_used(ctx) * 4), ctx);
}

static void build_epilogue(struct jit_ctx *ctx)
{
	u16 reg_set = saved_regs(ctx);

	if (ctx->seen & SEEN_MEM)
		emit(ARM_ADD_I(ARM_SP, ARM_SP, mem_words_used(ctx) * 4), ctx);

	reg_set &= ~(1 << ARM_LR);

#ifdef CONFIG_FRAME_POINTER
	/* the first instruction of the prologue was: mov ip, sp */
	reg_set &= ~(1 << ARM_IP);
	reg_set |= (1 << ARM_SP);
	emit(ARM_LDM(ARM_SP, reg_set), ctx);
#else
	if (reg_set) {
		if (ctx->seen & SEEN_CALL)
			reg_set |= 1 << ARM_PC;
		emit(ARM_POP(reg_set), ctx);
	}

	if (!(ctx->seen & SEEN_CALL))
		emit(ARM_BX(ARM_LR), ctx);
#endif
}

static int16_t imm8m(u32 x)
{
	u32 rot;

	for (rot = 0; rot < 16; rot++)
		if ((x & ~ror32(0xff, 2 * rot)) == 0)
			return rol32(x, 2 * rot) | (rot << 8);

	return -1;
}

#if __LINUX_ARM_ARCH__ < 7

static u16 imm_offset(u32 k, struct jit_ctx *ctx)
{
	unsigned i = 0, offset;
	u16 imm;

	/* on the "fake" run we just count them (duplicates included) */
	if (ctx->target == NULL) {
		ctx->imm_count++;
		return 0;
	}

	while ((i < ctx->imm_count) && ctx->imms[i]) {
		if (ctx->imms[i] == k)
			break;
		i++;
	}

	if (ctx->imms[i] == 0)
		ctx->imms[i] = k;

	/* constants go just after the epilogue */
	offset =  ctx->offsets[ctx->skf->len];
	offset += ctx->prologue_bytes;
	offset += ctx->epilogue_bytes;
	offset += i * 4;

	ctx->target[offset / 4] = k;

	/* PC in ARM mode == address of the instruction + 8 */
	imm = offset - (8 + ctx->idx * 4);

	return imm;
}

#endif /* __LINUX_ARM_ARCH__ */

/*
 * Move an immediate that's not an imm8m to a core register.
 */
static inline void emit_mov_i_no8m(int rd, u32 val, struct jit_ctx *ctx)
{
#if __LINUX_ARM_ARCH__ < 7
	emit(ARM_LDR_I(rd, ARM_PC, imm_offset(val, ctx)), ctx);
#else
	emit(ARM_MOVW(rd, val & 0xffff), ctx);
	if (val > 0xffff)
		emit(ARM_MOVT(rd, val >> 16), ctx);
#endif
}

static inline void emit_mov_i(int rd, u32 val, struct jit_ctx *ctx)
{
	int imm12 = imm8m(val);

	if (imm12 >= 0)
		emit(ARM_MOV_I(rd, imm12), ctx);
	else
		emit_mov_i_no8m(rd, val, ctx);
}

#if __LINUX_ARM_ARCH__ < 6

static void emit_load_be32(u8 cond, u8 r_res, u8 r_addr, struct jit_ctx *ctx)
{
	_emit(cond, ARM_LDRB_I(ARM_R3, r_addr, 1), ctx);
	_emit(cond, ARM_LDRB_I(ARM_R1, r_addr, 0), ctx);
	_emit(cond, ARM_LDRB_I(ARM_R2, r_addr, 3), ctx);
	_emit(cond, ARM_LSL_I(ARM_R3, ARM_R3, 16), ctx);
	_emit(cond, ARM_LDRB_I(ARM_R0, r_addr, 2), ctx);
	_emit(cond, ARM_ORR_S(ARM_R3, ARM_R3, ARM_R1, SRTYPE_LSL, 24), ctx);
	_emit(cond, ARM_ORR_R(ARM_R3, ARM_R3, ARM_R2), ctx);
	_emit(cond, ARM_ORR_S(r_res, ARM_R3, ARM_R0, SRTYPE_LSL, 8), ctx);
}

static void emit_load_be16(u8 cond, u8 r_res, u8 r_addr, struct jit_ctx *ctx)
{
	_emit(cond, ARM_LDRB_I(ARM_R1, r_addr, 0), ctx);
	_emit(cond, ARM_LDRB_I(ARM_R2, r_addr, 1), ctx);
	_emit(cond, ARM_ORR_S(r_res, ARM_R2, ARM_R1, SRTYPE_LSL, 8), ctx);
}

static inline void emit_swap16(u8 r_dst, u8 r_src, struct jit_ctx *ctx)
{
340 341 342 343 344 345 346 347 348 349 350
	/* r_dst = (r_src << 8) | (r_src >> 8) */
	emit(ARM_LSL_I(ARM_R1, r_src, 8), ctx);
	emit(ARM_ORR_S(r_dst, ARM_R1, r_src, SRTYPE_LSR, 8), ctx);

	/*
	 * we need to mask out the bits set in r_dst[23:16] due to
	 * the first shift instruction.
	 *
	 * note that 0x8ff is the encoded immediate 0x00ff0000.
	 */
	emit(ARM_BIC_I(r_dst, r_dst, 0x8ff), ctx);
351 352 353 354 355 356 357 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 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467
}

#else  /* ARMv6+ */

static void emit_load_be32(u8 cond, u8 r_res, u8 r_addr, struct jit_ctx *ctx)
{
	_emit(cond, ARM_LDR_I(r_res, r_addr, 0), ctx);
#ifdef __LITTLE_ENDIAN
	_emit(cond, ARM_REV(r_res, r_res), ctx);
#endif
}

static void emit_load_be16(u8 cond, u8 r_res, u8 r_addr, struct jit_ctx *ctx)
{
	_emit(cond, ARM_LDRH_I(r_res, r_addr, 0), ctx);
#ifdef __LITTLE_ENDIAN
	_emit(cond, ARM_REV16(r_res, r_res), ctx);
#endif
}

static inline void emit_swap16(u8 r_dst __maybe_unused,
			       u8 r_src __maybe_unused,
			       struct jit_ctx *ctx __maybe_unused)
{
#ifdef __LITTLE_ENDIAN
	emit(ARM_REV16(r_dst, r_src), ctx);
#endif
}

#endif /* __LINUX_ARM_ARCH__ < 6 */


/* Compute the immediate value for a PC-relative branch. */
static inline u32 b_imm(unsigned tgt, struct jit_ctx *ctx)
{
	u32 imm;

	if (ctx->target == NULL)
		return 0;
	/*
	 * BPF allows only forward jumps and the offset of the target is
	 * still the one computed during the first pass.
	 */
	imm  = ctx->offsets[tgt] + ctx->prologue_bytes - (ctx->idx * 4 + 8);

	return imm >> 2;
}

#define OP_IMM3(op, r1, r2, imm_val, ctx)				\
	do {								\
		imm12 = imm8m(imm_val);					\
		if (imm12 < 0) {					\
			emit_mov_i_no8m(r_scratch, imm_val, ctx);	\
			emit(op ## _R((r1), (r2), r_scratch), ctx);	\
		} else {						\
			emit(op ## _I((r1), (r2), imm12), ctx);		\
		}							\
	} while (0)

static inline void emit_err_ret(u8 cond, struct jit_ctx *ctx)
{
	if (ctx->ret0_fp_idx >= 0) {
		_emit(cond, ARM_B(b_imm(ctx->ret0_fp_idx, ctx)), ctx);
		/* NOP to keep the size constant between passes */
		emit(ARM_MOV_R(ARM_R0, ARM_R0), ctx);
	} else {
		_emit(cond, ARM_MOV_I(ARM_R0, 0), ctx);
		_emit(cond, ARM_B(b_imm(ctx->skf->len, ctx)), ctx);
	}
}

static inline void emit_blx_r(u8 tgt_reg, struct jit_ctx *ctx)
{
#if __LINUX_ARM_ARCH__ < 5
	emit(ARM_MOV_R(ARM_LR, ARM_PC), ctx);

	if (elf_hwcap & HWCAP_THUMB)
		emit(ARM_BX(tgt_reg), ctx);
	else
		emit(ARM_MOV_R(ARM_PC, tgt_reg), ctx);
#else
	emit(ARM_BLX_R(tgt_reg), ctx);
#endif
}

static inline void emit_udiv(u8 rd, u8 rm, u8 rn, struct jit_ctx *ctx)
{
#if __LINUX_ARM_ARCH__ == 7
	if (elf_hwcap & HWCAP_IDIVA) {
		emit(ARM_UDIV(rd, rm, rn), ctx);
		return;
	}
#endif
	if (rm != ARM_R0)
		emit(ARM_MOV_R(ARM_R0, rm), ctx);
	if (rn != ARM_R1)
		emit(ARM_MOV_R(ARM_R1, rn), ctx);

	ctx->seen |= SEEN_CALL;
	emit_mov_i(ARM_R3, (u32)jit_udiv, ctx);
	emit_blx_r(ARM_R3, ctx);

	if (rd != ARM_R0)
		emit(ARM_MOV_R(rd, ARM_R0), ctx);
}

static inline void update_on_xread(struct jit_ctx *ctx)
{
	if (!(ctx->seen & SEEN_X))
		ctx->flags |= FLAG_NEED_X_RESET;

	ctx->seen |= SEEN_X;
}

static int build_body(struct jit_ctx *ctx)
{
	void *load_func[] = {jit_get_skb_b, jit_get_skb_h, jit_get_skb_w};
468
	const struct bpf_prog *prog = ctx->skf;
469 470 471 472 473 474
	const struct sock_filter *inst;
	unsigned i, load_order, off, condt;
	int imm12;
	u32 k;

	for (i = 0; i < prog->len; i++) {
475 476
		u16 code;

477 478 479
		inst = &(prog->insns[i]);
		/* K as an immediate value operand */
		k = inst->k;
480
		code = bpf_anc_helper(inst);
481 482 483 484 485

		/* compute offsets only in the fake pass */
		if (ctx->target == NULL)
			ctx->offsets[i] = ctx->idx * 4;

486 487
		switch (code) {
		case BPF_LD | BPF_IMM:
488 489
			emit_mov_i(r_A, k, ctx);
			break;
490
		case BPF_LD | BPF_W | BPF_LEN:
491 492 493 494 495
			ctx->seen |= SEEN_SKB;
			BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, len) != 4);
			emit(ARM_LDR_I(r_A, r_skb,
				       offsetof(struct sk_buff, len)), ctx);
			break;
496
		case BPF_LD | BPF_MEM:
497 498 499 500
			/* A = scratch[k] */
			ctx->seen |= SEEN_MEM_WORD(k);
			emit(ARM_LDR_I(r_A, ARM_SP, SCRATCH_OFF(k)), ctx);
			break;
501
		case BPF_LD | BPF_W | BPF_ABS:
502 503
			load_order = 2;
			goto load;
504
		case BPF_LD | BPF_H | BPF_ABS:
505 506
			load_order = 1;
			goto load;
507
		case BPF_LD | BPF_B | BPF_ABS:
508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549
			load_order = 0;
load:
			/* the interpreter will deal with the negative K */
			if ((int)k < 0)
				return -ENOTSUPP;
			emit_mov_i(r_off, k, ctx);
load_common:
			ctx->seen |= SEEN_DATA | SEEN_CALL;

			if (load_order > 0) {
				emit(ARM_SUB_I(r_scratch, r_skb_hl,
					       1 << load_order), ctx);
				emit(ARM_CMP_R(r_scratch, r_off), ctx);
				condt = ARM_COND_HS;
			} else {
				emit(ARM_CMP_R(r_skb_hl, r_off), ctx);
				condt = ARM_COND_HI;
			}

			_emit(condt, ARM_ADD_R(r_scratch, r_off, r_skb_data),
			      ctx);

			if (load_order == 0)
				_emit(condt, ARM_LDRB_I(r_A, r_scratch, 0),
				      ctx);
			else if (load_order == 1)
				emit_load_be16(condt, r_A, r_scratch, ctx);
			else if (load_order == 2)
				emit_load_be32(condt, r_A, r_scratch, ctx);

			_emit(condt, ARM_B(b_imm(i + 1, ctx)), ctx);

			/* the slowpath */
			emit_mov_i(ARM_R3, (u32)load_func[load_order], ctx);
			emit(ARM_MOV_R(ARM_R0, r_skb), ctx);
			/* the offset is already in R1 */
			emit_blx_r(ARM_R3, ctx);
			/* check the result of skb_copy_bits */
			emit(ARM_CMP_I(ARM_R1, 0), ctx);
			emit_err_ret(ARM_COND_NE, ctx);
			emit(ARM_MOV_R(r_A, ARM_R0), ctx);
			break;
550
		case BPF_LD | BPF_W | BPF_IND:
551 552
			load_order = 2;
			goto load_ind;
553
		case BPF_LD | BPF_H | BPF_IND:
554 555
			load_order = 1;
			goto load_ind;
556
		case BPF_LD | BPF_B | BPF_IND:
557 558 559 560
			load_order = 0;
load_ind:
			OP_IMM3(ARM_ADD, r_off, r_X, k, ctx);
			goto load_common;
561
		case BPF_LDX | BPF_IMM:
562 563 564
			ctx->seen |= SEEN_X;
			emit_mov_i(r_X, k, ctx);
			break;
565
		case BPF_LDX | BPF_W | BPF_LEN:
566 567 568 569
			ctx->seen |= SEEN_X | SEEN_SKB;
			emit(ARM_LDR_I(r_X, r_skb,
				       offsetof(struct sk_buff, len)), ctx);
			break;
570
		case BPF_LDX | BPF_MEM:
571 572 573
			ctx->seen |= SEEN_X | SEEN_MEM_WORD(k);
			emit(ARM_LDR_I(r_X, ARM_SP, SCRATCH_OFF(k)), ctx);
			break;
574
		case BPF_LDX | BPF_B | BPF_MSH:
575 576 577
			/* x = ((*(frame + k)) & 0xf) << 2; */
			ctx->seen |= SEEN_X | SEEN_DATA | SEEN_CALL;
			/* the interpreter should deal with the negative K */
578
			if ((int)k < 0)
579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603
				return -1;
			/* offset in r1: we might have to take the slow path */
			emit_mov_i(r_off, k, ctx);
			emit(ARM_CMP_R(r_skb_hl, r_off), ctx);

			/* load in r0: common with the slowpath */
			_emit(ARM_COND_HI, ARM_LDRB_R(ARM_R0, r_skb_data,
						      ARM_R1), ctx);
			/*
			 * emit_mov_i() might generate one or two instructions,
			 * the same holds for emit_blx_r()
			 */
			_emit(ARM_COND_HI, ARM_B(b_imm(i + 1, ctx) - 2), ctx);

			emit(ARM_MOV_R(ARM_R0, r_skb), ctx);
			/* r_off is r1 */
			emit_mov_i(ARM_R3, (u32)jit_get_skb_b, ctx);
			emit_blx_r(ARM_R3, ctx);
			/* check the return value of skb_copy_bits */
			emit(ARM_CMP_I(ARM_R1, 0), ctx);
			emit_err_ret(ARM_COND_NE, ctx);

			emit(ARM_AND_I(r_X, ARM_R0, 0x00f), ctx);
			emit(ARM_LSL_I(r_X, r_X, 2), ctx);
			break;
604
		case BPF_ST:
605 606 607
			ctx->seen |= SEEN_MEM_WORD(k);
			emit(ARM_STR_I(r_A, ARM_SP, SCRATCH_OFF(k)), ctx);
			break;
608
		case BPF_STX:
609 610 611 612
			update_on_xread(ctx);
			ctx->seen |= SEEN_MEM_WORD(k);
			emit(ARM_STR_I(r_X, ARM_SP, SCRATCH_OFF(k)), ctx);
			break;
613
		case BPF_ALU | BPF_ADD | BPF_K:
614 615 616
			/* A += K */
			OP_IMM3(ARM_ADD, r_A, r_A, k, ctx);
			break;
617
		case BPF_ALU | BPF_ADD | BPF_X:
618 619 620
			update_on_xread(ctx);
			emit(ARM_ADD_R(r_A, r_A, r_X), ctx);
			break;
621
		case BPF_ALU | BPF_SUB | BPF_K:
622 623 624
			/* A -= K */
			OP_IMM3(ARM_SUB, r_A, r_A, k, ctx);
			break;
625
		case BPF_ALU | BPF_SUB | BPF_X:
626 627 628
			update_on_xread(ctx);
			emit(ARM_SUB_R(r_A, r_A, r_X), ctx);
			break;
629
		case BPF_ALU | BPF_MUL | BPF_K:
630 631 632 633
			/* A *= K */
			emit_mov_i(r_scratch, k, ctx);
			emit(ARM_MUL(r_A, r_A, r_scratch), ctx);
			break;
634
		case BPF_ALU | BPF_MUL | BPF_X:
635 636 637
			update_on_xread(ctx);
			emit(ARM_MUL(r_A, r_A, r_X), ctx);
			break;
638
		case BPF_ALU | BPF_DIV | BPF_K:
E
Eric Dumazet 已提交
639 640
			if (k == 1)
				break;
641
			emit_mov_i(r_scratch, k, ctx);
E
Eric Dumazet 已提交
642
			emit_udiv(r_A, r_A, r_scratch, ctx);
643
			break;
644
		case BPF_ALU | BPF_DIV | BPF_X:
645 646 647 648 649
			update_on_xread(ctx);
			emit(ARM_CMP_I(r_X, 0), ctx);
			emit_err_ret(ARM_COND_EQ, ctx);
			emit_udiv(r_A, r_A, r_X, ctx);
			break;
650
		case BPF_ALU | BPF_OR | BPF_K:
651 652 653
			/* A |= K */
			OP_IMM3(ARM_ORR, r_A, r_A, k, ctx);
			break;
654
		case BPF_ALU | BPF_OR | BPF_X:
655 656 657
			update_on_xread(ctx);
			emit(ARM_ORR_R(r_A, r_A, r_X), ctx);
			break;
658
		case BPF_ALU | BPF_XOR | BPF_K:
659 660 661
			/* A ^= K; */
			OP_IMM3(ARM_EOR, r_A, r_A, k, ctx);
			break;
662 663
		case BPF_ANC | SKF_AD_ALU_XOR_X:
		case BPF_ALU | BPF_XOR | BPF_X:
664 665 666 667
			/* A ^= X */
			update_on_xread(ctx);
			emit(ARM_EOR_R(r_A, r_A, r_X), ctx);
			break;
668
		case BPF_ALU | BPF_AND | BPF_K:
669 670 671
			/* A &= K */
			OP_IMM3(ARM_AND, r_A, r_A, k, ctx);
			break;
672
		case BPF_ALU | BPF_AND | BPF_X:
673 674 675
			update_on_xread(ctx);
			emit(ARM_AND_R(r_A, r_A, r_X), ctx);
			break;
676
		case BPF_ALU | BPF_LSH | BPF_K:
677 678 679 680
			if (unlikely(k > 31))
				return -1;
			emit(ARM_LSL_I(r_A, r_A, k), ctx);
			break;
681
		case BPF_ALU | BPF_LSH | BPF_X:
682 683 684
			update_on_xread(ctx);
			emit(ARM_LSL_R(r_A, r_A, r_X), ctx);
			break;
685
		case BPF_ALU | BPF_RSH | BPF_K:
686 687 688 689
			if (unlikely(k > 31))
				return -1;
			emit(ARM_LSR_I(r_A, r_A, k), ctx);
			break;
690
		case BPF_ALU | BPF_RSH | BPF_X:
691 692 693
			update_on_xread(ctx);
			emit(ARM_LSR_R(r_A, r_A, r_X), ctx);
			break;
694
		case BPF_ALU | BPF_NEG:
695 696 697
			/* A = -A */
			emit(ARM_RSB_I(r_A, r_A, 0), ctx);
			break;
698
		case BPF_JMP | BPF_JA:
699 700 701
			/* pc += K */
			emit(ARM_B(b_imm(i + k + 1, ctx)), ctx);
			break;
702
		case BPF_JMP | BPF_JEQ | BPF_K:
703 704 705
			/* pc += (A == K) ? pc->jt : pc->jf */
			condt  = ARM_COND_EQ;
			goto cmp_imm;
706
		case BPF_JMP | BPF_JGT | BPF_K:
707 708 709
			/* pc += (A > K) ? pc->jt : pc->jf */
			condt  = ARM_COND_HI;
			goto cmp_imm;
710
		case BPF_JMP | BPF_JGE | BPF_K:
711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728
			/* pc += (A >= K) ? pc->jt : pc->jf */
			condt  = ARM_COND_HS;
cmp_imm:
			imm12 = imm8m(k);
			if (imm12 < 0) {
				emit_mov_i_no8m(r_scratch, k, ctx);
				emit(ARM_CMP_R(r_A, r_scratch), ctx);
			} else {
				emit(ARM_CMP_I(r_A, imm12), ctx);
			}
cond_jump:
			if (inst->jt)
				_emit(condt, ARM_B(b_imm(i + inst->jt + 1,
						   ctx)), ctx);
			if (inst->jf)
				_emit(condt ^ 1, ARM_B(b_imm(i + inst->jf + 1,
							     ctx)), ctx);
			break;
729
		case BPF_JMP | BPF_JEQ | BPF_X:
730 731 732
			/* pc += (A == X) ? pc->jt : pc->jf */
			condt   = ARM_COND_EQ;
			goto cmp_x;
733
		case BPF_JMP | BPF_JGT | BPF_X:
734 735 736
			/* pc += (A > X) ? pc->jt : pc->jf */
			condt   = ARM_COND_HI;
			goto cmp_x;
737
		case BPF_JMP | BPF_JGE | BPF_X:
738 739 740 741 742 743
			/* pc += (A >= X) ? pc->jt : pc->jf */
			condt   = ARM_COND_CS;
cmp_x:
			update_on_xread(ctx);
			emit(ARM_CMP_R(r_A, r_X), ctx);
			goto cond_jump;
744
		case BPF_JMP | BPF_JSET | BPF_K:
745 746 747 748 749 750 751 752 753 754 755 756
			/* pc += (A & K) ? pc->jt : pc->jf */
			condt  = ARM_COND_NE;
			/* not set iff all zeroes iff Z==1 iff EQ */

			imm12 = imm8m(k);
			if (imm12 < 0) {
				emit_mov_i_no8m(r_scratch, k, ctx);
				emit(ARM_TST_R(r_A, r_scratch), ctx);
			} else {
				emit(ARM_TST_I(r_A, imm12), ctx);
			}
			goto cond_jump;
757
		case BPF_JMP | BPF_JSET | BPF_X:
758 759 760 761 762
			/* pc += (A & X) ? pc->jt : pc->jf */
			update_on_xread(ctx);
			condt  = ARM_COND_NE;
			emit(ARM_TST_R(r_A, r_X), ctx);
			goto cond_jump;
763
		case BPF_RET | BPF_A:
764 765
			emit(ARM_MOV_R(ARM_R0, r_A), ctx);
			goto b_epilogue;
766
		case BPF_RET | BPF_K:
767 768 769 770 771 772 773
			if ((k == 0) && (ctx->ret0_fp_idx < 0))
				ctx->ret0_fp_idx = i;
			emit_mov_i(ARM_R0, k, ctx);
b_epilogue:
			if (i != ctx->skf->len - 1)
				emit(ARM_B(b_imm(prog->len, ctx)), ctx);
			break;
774
		case BPF_MISC | BPF_TAX:
775 776 777 778
			/* X = A */
			ctx->seen |= SEEN_X;
			emit(ARM_MOV_R(r_X, r_A), ctx);
			break;
779
		case BPF_MISC | BPF_TXA:
780 781 782 783
			/* A = X */
			update_on_xread(ctx);
			emit(ARM_MOV_R(r_A, r_X), ctx);
			break;
784
		case BPF_ANC | SKF_AD_PROTOCOL:
785 786 787 788 789 790 791 792
			/* A = ntohs(skb->protocol) */
			ctx->seen |= SEEN_SKB;
			BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff,
						  protocol) != 2);
			off = offsetof(struct sk_buff, protocol);
			emit(ARM_LDRH_I(r_scratch, r_skb, off), ctx);
			emit_swap16(r_A, r_scratch, ctx);
			break;
793
		case BPF_ANC | SKF_AD_CPU:
794 795 796 797 798 799 800
			/* r_scratch = current_thread_info() */
			OP_IMM3(ARM_BIC, r_scratch, ARM_SP, THREAD_SIZE - 1, ctx);
			/* A = current_thread_info()->cpu */
			BUILD_BUG_ON(FIELD_SIZEOF(struct thread_info, cpu) != 4);
			off = offsetof(struct thread_info, cpu);
			emit(ARM_LDR_I(r_A, r_scratch, off), ctx);
			break;
801
		case BPF_ANC | SKF_AD_IFINDEX:
802 803 804 805 806 807 808 809 810 811 812 813 814
			/* A = skb->dev->ifindex */
			ctx->seen |= SEEN_SKB;
			off = offsetof(struct sk_buff, dev);
			emit(ARM_LDR_I(r_scratch, r_skb, off), ctx);

			emit(ARM_CMP_I(r_scratch, 0), ctx);
			emit_err_ret(ARM_COND_EQ, ctx);

			BUILD_BUG_ON(FIELD_SIZEOF(struct net_device,
						  ifindex) != 4);
			off = offsetof(struct net_device, ifindex);
			emit(ARM_LDR_I(r_A, r_scratch, off), ctx);
			break;
815
		case BPF_ANC | SKF_AD_MARK:
816 817 818 819 820
			ctx->seen |= SEEN_SKB;
			BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, mark) != 4);
			off = offsetof(struct sk_buff, mark);
			emit(ARM_LDR_I(r_A, r_skb, off), ctx);
			break;
821
		case BPF_ANC | SKF_AD_RXHASH:
822
			ctx->seen |= SEEN_SKB;
823 824
			BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, hash) != 4);
			off = offsetof(struct sk_buff, hash);
825 826
			emit(ARM_LDR_I(r_A, r_skb, off), ctx);
			break;
827 828
		case BPF_ANC | SKF_AD_VLAN_TAG:
		case BPF_ANC | SKF_AD_VLAN_TAG_PRESENT:
829 830 831 832
			ctx->seen |= SEEN_SKB;
			BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, vlan_tci) != 2);
			off = offsetof(struct sk_buff, vlan_tci);
			emit(ARM_LDRH_I(r_A, r_skb, off), ctx);
833
			if (code == (BPF_ANC | SKF_AD_VLAN_TAG))
834 835 836 837
				OP_IMM3(ARM_AND, r_A, r_A, VLAN_VID_MASK, ctx);
			else
				OP_IMM3(ARM_AND, r_A, r_A, VLAN_TAG_PRESENT, ctx);
			break;
838
		case BPF_ANC | SKF_AD_QUEUE:
839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859
			ctx->seen |= SEEN_SKB;
			BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff,
						  queue_mapping) != 2);
			BUILD_BUG_ON(offsetof(struct sk_buff,
					      queue_mapping) > 0xff);
			off = offsetof(struct sk_buff, queue_mapping);
			emit(ARM_LDRH_I(r_A, r_skb, off), ctx);
			break;
		default:
			return -1;
		}
	}

	/* compute offsets only during the first pass */
	if (ctx->target == NULL)
		ctx->offsets[i] = ctx->idx * 4;

	return 0;
}


860
void bpf_jit_compile(struct bpf_prog *fp)
861 862 863 864 865 866 867 868 869 870 871 872
{
	struct jit_ctx ctx;
	unsigned tmp_idx;
	unsigned alloc_size;

	if (!bpf_jit_enable)
		return;

	memset(&ctx, 0, sizeof(ctx));
	ctx.skf		= fp;
	ctx.ret0_fp_idx = -1;

873
	ctx.offsets = kzalloc(4 * (ctx.skf->len + 1), GFP_KERNEL);
874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891
	if (ctx.offsets == NULL)
		return;

	/* fake pass to fill in the ctx->seen */
	if (unlikely(build_body(&ctx)))
		goto out;

	tmp_idx = ctx.idx;
	build_prologue(&ctx);
	ctx.prologue_bytes = (ctx.idx - tmp_idx) * 4;

#if __LINUX_ARM_ARCH__ < 7
	tmp_idx = ctx.idx;
	build_epilogue(&ctx);
	ctx.epilogue_bytes = (ctx.idx - tmp_idx) * 4;

	ctx.idx += ctx.imm_count;
	if (ctx.imm_count) {
892
		ctx.imms = kzalloc(4 * ctx.imm_count, GFP_KERNEL);
893 894 895 896 897 898 899 900 901
		if (ctx.imms == NULL)
			goto out;
	}
#else
	/* there's nothing after the epilogue on ARMv7 */
	build_epilogue(&ctx);
#endif

	alloc_size = 4 * ctx.idx;
902
	ctx.target = module_alloc(alloc_size);
903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918
	if (unlikely(ctx.target == NULL))
		goto out;

	ctx.idx = 0;
	build_prologue(&ctx);
	build_body(&ctx);
	build_epilogue(&ctx);

	flush_icache_range((u32)ctx.target, (u32)(ctx.target + ctx.idx));

#if __LINUX_ARM_ARCH__ < 7
	if (ctx.imm_count)
		kfree(ctx.imms);
#endif

	if (bpf_jit_enable > 1)
919 920
		/* there are 2 passes here */
		bpf_jit_dump(fp->len, alloc_size, 2, ctx.target);
921 922

	fp->bpf_func = (void *)ctx.target;
923
	fp->jited = 1;
924 925 926 927 928
out:
	kfree(ctx.offsets);
	return;
}

929
void bpf_jit_free(struct bpf_prog *fp)
930
{
931
	if (fp->jited)
932
		module_free(NULL, fp->bpf_func);
933 934

	bpf_prog_unlock_free(fp);
935
}