xref: /linux/arch/arc/net/bpf_jit_core.c (revision 5c1672705a1a2389f5ad78e0fea6f08ed32d6f18)

// SPDX-License-Identifier: GPL-2.0
/*
 * The back-end-agnostic part of Just-In-Time compiler for eBPF bytecode.
 *
 * Copyright (c) 2024 Synopsys Inc.
 * Author: Shahab Vahedi <shahab@synopsys.com>
 */
#include <linux/bug.h>
#include "bpf_jit.h"

/*
 * Check for the return value. A pattern used often in this file.
 * There must be a "ret" variable of type "int" in the scope.
 */
#define CHECK_RET(cmd)			\
	do {				\
		ret = (cmd);		\
		if (ret < 0)		\
			return ret;	\
	} while (0)

#ifdef ARC_BPF_JIT_DEBUG
/* Dumps bytes in /var/log/messages at KERN_INFO level (4). */
static void dump_bytes(const u8 *buf, u32 len, const char *header)
{
	u8 line[64];
	size_t i, j;

	pr_info("-----------------[ %s ]-----------------\n", header);

	for (i = 0, j = 0; i < len; i++) {
		/* Last input byte? */
		if (i == len - 1) {
			j += scnprintf(line + j, 64 - j, "0x%02x", buf[i]);
			pr_info("%s\n", line);
			break;
		}
		/* End of line? */
		else if (i % 8 == 7) {
			j += scnprintf(line + j, 64 - j, "0x%02x", buf[i]);
			pr_info("%s\n", line);
			j = 0;
		} else {
			j += scnprintf(line + j, 64 - j, "0x%02x, ", buf[i]);
		}
	}
}
#endif /* ARC_BPF_JIT_DEBUG */

/********************* JIT context ***********************/

/*
 * buf:		Translated instructions end up here.
 * len:		The length of whole block in bytes.
 * index:	The offset at which the _next_ instruction may be put.
 */
struct jit_buffer {
	u8	*buf;
	u32	len;
	u32	index;
};

/*
 * This is a subset of "struct jit_context" that its information is deemed
 * necessary for the next extra pass to come.
 *
 * bpf_header:	Needed to finally lock the region.
 * bpf2insn:	Used to find the translation for instructions of interest.
 *
 * Things like "jit.buf" and "jit.len" can be retrieved respectively from
 * "prog->bpf_func" and "prog->jited_len".
 */
struct arc_jit_data {
	struct bpf_binary_header *bpf_header;
	u32                      *bpf2insn;
};

/*
 * The JIT pertinent context that is used by different functions.
 *
 * prog:		The current eBPF program being handled.
 * orig_prog:		The original eBPF program before any possible change.
 * jit:			The JIT buffer and its length.
 * bpf_header:		The JITed program header. "jit.buf" points inside it.
 * emit:		If set, opcodes are written to memory; else, a dry-run.
 * do_zext:		If true, 32-bit sub-regs must be zero extended.
 * bpf2insn:		Maps BPF insn indices to their counterparts in jit.buf.
 * bpf2insn_valid:	Indicates if "bpf2ins" is populated with the mappings.
 * jit_data:		A piece of memory to transfer data to the next pass.
 * arc_regs_clobbered:	Each bit status determines if that arc reg is clobbered.
 * save_blink:		Whether ARC's "blink" register needs to be saved.
 * frame_size:		Derived from "prog->aux->stack_depth".
 * epilogue_offset:	Used by early "return"s in the code to jump here.
 * need_extra_pass:	A forecast if an "extra_pass" will occur.
 * is_extra_pass:	Indicates if the current pass is an extra pass.
 * user_bpf_prog:	True, if VM opcodes come from a real program.
 * blinded:		True if "constant blinding" step returned a new "prog".
 * success:		Indicates if the whole JIT went OK.
 */
struct jit_context {
	struct bpf_prog			*prog;
	struct bpf_prog			*orig_prog;
	struct jit_buffer		jit;
	struct bpf_binary_header	*bpf_header;
	bool				emit;
	bool				do_zext;
	u32				*bpf2insn;
	bool				bpf2insn_valid;
	struct arc_jit_data		*jit_data;
	u32				arc_regs_clobbered;
	bool				save_blink;
	u16				frame_size;
	u32				epilogue_offset;
	bool				need_extra_pass;
	bool				is_extra_pass;
	bool				user_bpf_prog;
	bool				blinded;
	bool				success;
};

/*
 * If we're in ARC_BPF_JIT_DEBUG mode and the debug level is right, dump the
 * input BPF stream. "bpf_jit_dump()" is not fully suited for this purpose.
 */
static void vm_dump(const struct bpf_prog *prog)
{
#ifdef ARC_BPF_JIT_DEBUG
	if (bpf_jit_enable > 1)
		dump_bytes((u8 *)prog->insns, 8 * prog->len, " VM  ");
#endif
}

/*
 * If the right level of debug is set, dump the bytes. There are 2 variants
 * of this function:
 *
 * 1. Use the standard bpf_jit_dump() which is meant only for JITed code.
 * 2. Use the dump_bytes() to match its "vm_dump()" instance.
 */
static void jit_dump(const struct jit_context *ctx)
{
#ifdef ARC_BPF_JIT_DEBUG
	u8 header[8];
#endif
	const int pass = ctx->is_extra_pass ? 2 : 1;

	if (bpf_jit_enable <= 1 || !ctx->prog->jited)
		return;

#ifdef ARC_BPF_JIT_DEBUG
	scnprintf(header, sizeof(header), "JIT:%d", pass);
	dump_bytes(ctx->jit.buf, ctx->jit.len, header);
	pr_info("\n");
#else
	bpf_jit_dump(ctx->prog->len, ctx->jit.len, pass, ctx->jit.buf);
#endif
}

/* Initialise the context so there's no garbage. */
static int jit_ctx_init(struct jit_context *ctx, struct bpf_prog *prog)
{
	memset(ctx, 0, sizeof(ctx));

	ctx->orig_prog = prog;

	/* If constant blinding was requested but failed, scram. */
	ctx->prog = bpf_jit_blind_constants(prog);
	if (IS_ERR(ctx->prog))
		return PTR_ERR(ctx->prog);
	ctx->blinded = (ctx->prog == ctx->orig_prog ? false : true);

	/* If the verifier doesn't zero-extend, then we have to do it. */
	ctx->do_zext = !ctx->prog->aux->verifier_zext;

	ctx->is_extra_pass = ctx->prog->jited;
	ctx->user_bpf_prog = ctx->prog->is_func;

	return 0;
}

/*
 * Only after the first iteration of normal pass (the dry-run),
 * there are valid offsets in ctx->bpf2insn array.
 */
static inline bool offsets_available(const struct jit_context *ctx)
{
	return ctx->bpf2insn_valid;
}

/*
 * "*mem" should be freed when there is no "extra pass" to come,
 * or the compilation terminated abruptly. A few of such memory
 * allocations are: ctx->jit_data and ctx->bpf2insn.
 */
static inline void maybe_free(struct jit_context *ctx, void **mem)
{
	if (*mem) {
		if (!ctx->success || !ctx->need_extra_pass) {
			kfree(*mem);
			*mem = NULL;
		}
	}
}

/*
 * Free memories based on the status of the context.
 *
 * A note about "bpf_header": On successful runs, "bpf_header" is
 * not freed, because "jit.buf", a sub-array of it, is returned as
 * the "bpf_func". However, "bpf_header" is lost and nothing points
 * to it. This should not cause a leakage, because apparently
 * "bpf_header" can be revived by "bpf_jit_binary_hdr()". This is
 * how "bpf_jit_free()" in "kernel/bpf/core.c" releases the memory.
 */
static void jit_ctx_cleanup(struct jit_context *ctx)
{
	if (ctx->blinded) {
		/* if all went well, release the orig_prog. */
		if (ctx->success)
			bpf_jit_prog_release_other(ctx->prog, ctx->orig_prog);
		else
			bpf_jit_prog_release_other(ctx->orig_prog, ctx->prog);
	}

	maybe_free(ctx, (void **)&ctx->bpf2insn);
	maybe_free(ctx, (void **)&ctx->jit_data);

	if (!ctx->bpf2insn)
		ctx->bpf2insn_valid = false;

	/* Freeing "bpf_header" is enough. "jit.buf" is a sub-array of it. */
	if (!ctx->success && ctx->bpf_header) {
		bpf_jit_binary_free(ctx->bpf_header);
		ctx->bpf_header = NULL;
		ctx->jit.buf    = NULL;
		ctx->jit.index  = 0;
		ctx->jit.len    = 0;
	}

	ctx->emit = false;
	ctx->do_zext = false;
}

/*
 * Analyse the register usage and record the frame size.
 * The register usage is determined by consulting the back-end.
 */
static void analyze_reg_usage(struct jit_context *ctx)
{
	size_t i;
	u32 usage = 0;
	const struct bpf_insn *insn = ctx->prog->insnsi;

	for (i = 0; i < ctx->prog->len; i++) {
		u8 bpf_reg;
		bool call;

		bpf_reg = insn[i].dst_reg;
		call = (insn[i].code == (BPF_JMP | BPF_CALL)) ? true : false;
		usage |= mask_for_used_regs(bpf_reg, call);
	}

	ctx->arc_regs_clobbered = usage;
	ctx->frame_size = ctx->prog->aux->stack_depth;
}

/* Verify that no instruction will be emitted when there is no buffer. */
static inline int jit_buffer_check(const struct jit_context *ctx)
{
	if (ctx->emit) {
		if (!ctx->jit.buf) {
			pr_err("bpf-jit: inconsistence state; no "
			       "buffer to emit instructions.\n");
			return -EINVAL;
		} else if (ctx->jit.index > ctx->jit.len) {
			pr_err("bpf-jit: estimated JIT length is less "
			       "than the emitted instructions.\n");
			return -EFAULT;
		}
	}
	return 0;
}

/* On a dry-run (emit=false), "jit.len" is growing gradually. */
static inline void jit_buffer_update(struct jit_context *ctx, u32 n)
{
	if (!ctx->emit)
		ctx->jit.len += n;
	else
		ctx->jit.index += n;
}

/* Based on "emit", determine the address where instructions are emitted. */
static inline u8 *effective_jit_buf(const struct jit_context *ctx)
{
	return ctx->emit ? (ctx->jit.buf + ctx->jit.index) : NULL;
}

/* Prologue based on context variables set by "analyze_reg_usage()". */
static int handle_prologue(struct jit_context *ctx)
{
	int ret;
	u8 *buf = effective_jit_buf(ctx);
	u32 len = 0;

	CHECK_RET(jit_buffer_check(ctx));

	len = arc_prologue(buf, ctx->arc_regs_clobbered, ctx->frame_size);
	jit_buffer_update(ctx, len);

	return 0;
}

/* The counter part for "handle_prologue()". */
static int handle_epilogue(struct jit_context *ctx)
{
	int ret;
	u8 *buf = effective_jit_buf(ctx);
	u32 len = 0;

	CHECK_RET(jit_buffer_check(ctx));

	len = arc_epilogue(buf, ctx->arc_regs_clobbered, ctx->frame_size);
	jit_buffer_update(ctx, len);

	return 0;
}

/* Tell which number of the BPF instruction we are dealing with. */
static inline s32 get_index_for_insn(const struct jit_context *ctx,
				     const struct bpf_insn *insn)
{
	return (insn - ctx->prog->insnsi);
}

/*
 * In most of the cases, the "offset" is read from "insn->off". However,
 * if it is an unconditional BPF_JMP32, then it comes from "insn->imm".
 *
 * (Courtesy of "cpu=v4" support)
 */
static inline s32 get_offset(const struct bpf_insn *insn)
{
	if ((BPF_CLASS(insn->code) == BPF_JMP32) &&
	    (BPF_OP(insn->code) == BPF_JA))
		return insn->imm;
	else
		return insn->off;
}

/*
 * Determine to which number of the BPF instruction we're jumping to.
 *
 * The "offset" is interpreted as the "number" of BPF instructions
 * from the _next_ BPF instruction. e.g.:
 *
 *  4 means 4 instructions after  the next insn
 *  0 means 0 instructions after  the next insn -> fallthrough.
 * -1 means 1 instruction  before the next insn -> jmp to current insn.
 *
 *  Another way to look at this, "offset" is the number of instructions
 *  that exist between the current instruction and the target instruction.
 *
 *  It is worth noting that a "mov r,i64", which is 16-byte long, is
 *  treated as two instructions long, therefore "offset" needn't be
 *  treated specially for those. Everything is uniform.
 */
static inline s32 get_target_index_for_insn(const struct jit_context *ctx,
					    const struct bpf_insn *insn)
{
	return (get_index_for_insn(ctx, insn) + 1) + get_offset(insn);
}

/* Is there an immediate operand encoded in the "insn"? */
static inline bool has_imm(const struct bpf_insn *insn)
{
	return BPF_SRC(insn->code) == BPF_K;
}

/* Is the last BPF instruction? */
static inline bool is_last_insn(const struct bpf_prog *prog, u32 idx)
{
	return idx == (prog->len - 1);
}

/*
 * Invocation of this function, conditionally signals the need for
 * an extra pass. The conditions that must be met are:
 *
 * 1. The current pass itself shouldn't be an extra pass.
 * 2. The stream of bytes being JITed must come from a user program.
 */
static inline void set_need_for_extra_pass(struct jit_context *ctx)
{
	if (!ctx->is_extra_pass)
		ctx->need_extra_pass = ctx->user_bpf_prog;
}

/*
 * Check if the "size" is valid and then transfer the control to
 * the back-end for the swap.
 */
static int handle_swap(u8 *buf, u8 rd, u8 size, u8 endian,
		       bool force, bool do_zext, u8 *len)
{
	/* Sanity check on the size. */
	switch (size) {
	case 16:
	case 32:
	case 64:
		break;
	default:
		pr_err("bpf-jit: invalid size for swap.\n");
		return -EINVAL;
	}

	*len = gen_swap(buf, rd, size, endian, force, do_zext);

	return 0;
}

/* Checks if the (instruction) index is in valid range. */
static inline bool check_insn_idx_valid(const struct jit_context *ctx,
					const s32 idx)
{
	return (idx >= 0 && idx < ctx->prog->len);
}

/*
 * Decouple the back-end from BPF by converting BPF conditions
 * to internal enum. ARC_CC_* start from 0 and are used as index
 * to an array. BPF_J* usage must end after this conversion.
 */
static int bpf_cond_to_arc(const u8 op, u8 *arc_cc)
{
	switch (op) {
	case BPF_JA:
		*arc_cc = ARC_CC_AL;
		break;
	case BPF_JEQ:
		*arc_cc = ARC_CC_EQ;
		break;
	case BPF_JGT:
		*arc_cc = ARC_CC_UGT;
		break;
	case BPF_JGE:
		*arc_cc = ARC_CC_UGE;
		break;
	case BPF_JSET:
		*arc_cc = ARC_CC_SET;
		break;
	case BPF_JNE:
		*arc_cc = ARC_CC_NE;
		break;
	case BPF_JSGT:
		*arc_cc = ARC_CC_SGT;
		break;
	case BPF_JSGE:
		*arc_cc = ARC_CC_SGE;
		break;
	case BPF_JLT:
		*arc_cc = ARC_CC_ULT;
		break;
	case BPF_JLE:
		*arc_cc = ARC_CC_ULE;
		break;
	case BPF_JSLT:
		*arc_cc = ARC_CC_SLT;
		break;
	case BPF_JSLE:
		*arc_cc = ARC_CC_SLE;
		break;
	default:
		pr_err("bpf-jit: can't handle condition 0x%02X\n", op);
		return -EINVAL;
	}
	return 0;
}

/*
 * Check a few things for a supposedly "jump" instruction:
 *
 * 0. "insn" is a "jump" instruction, but not the "call/exit" variant.
 * 1. The current "insn" index is in valid range.
 * 2. The index of target instruction is in valid range.
 */
static int check_bpf_jump(const struct jit_context *ctx,
			  const struct bpf_insn *insn)
{
	const u8 class = BPF_CLASS(insn->code);
	const u8 op = BPF_OP(insn->code);

	/* Must be a jmp(32) instruction that is not a "call/exit". */
	if ((class != BPF_JMP && class != BPF_JMP32) ||
	    (op == BPF_CALL || op == BPF_EXIT)) {
		pr_err("bpf-jit: not a jump instruction.\n");
		return -EINVAL;
	}

	if (!check_insn_idx_valid(ctx, get_index_for_insn(ctx, insn))) {
		pr_err("bpf-jit: the bpf jump insn is not in prog.\n");
		return -EINVAL;
	}

	if (!check_insn_idx_valid(ctx, get_target_index_for_insn(ctx, insn))) {
		pr_err("bpf-jit: bpf jump label is out of range.\n");
		return -EINVAL;
	}

	return 0;
}

/*
 * Based on input "insn", consult "ctx->bpf2insn" to get the
 * related index (offset) of the translation in JIT stream.
 */
static u32 get_curr_jit_off(const struct jit_context *ctx,
			    const struct bpf_insn *insn)
{
	const s32 idx = get_index_for_insn(ctx, insn);
#ifdef ARC_BPF_JIT_DEBUG
	BUG_ON(!offsets_available(ctx) || !check_insn_idx_valid(ctx, idx));
#endif
	return ctx->bpf2insn[idx];
}

/*
 * The input "insn" must be a jump instruction.
 *
 * Based on input "insn", consult "ctx->bpf2insn" to get the
 * related JIT index (offset) of "target instruction" that
 * "insn" would jump to.
 */
static u32 get_targ_jit_off(const struct jit_context *ctx,
			    const struct bpf_insn *insn)
{
	const s32 tidx = get_target_index_for_insn(ctx, insn);
#ifdef ARC_BPF_JIT_DEBUG
	BUG_ON(!offsets_available(ctx) || !check_insn_idx_valid(ctx, tidx));
#endif
	return ctx->bpf2insn[tidx];
}

/*
 * This function will return 0 for a feasible jump.
 *
 * Consult the back-end to check if it finds it feasible to emit
 * the necessary instructions based on "cond" and the displacement
 * between the "from_off" and the "to_off".
 */
static int feasible_jit_jump(u32 from_off, u32 to_off, u8 cond, bool j32)
{
	int ret = 0;

	if (j32) {
		if (!check_jmp_32(from_off, to_off, cond))
			ret = -EFAULT;
	} else {
		if (!check_jmp_64(from_off, to_off, cond))
			ret = -EFAULT;
	}

	if (ret != 0)
		pr_err("bpf-jit: the JIT displacement is not OK.\n");

	return ret;
}

/*
 * This jump handler performs the following steps:
 *
 * 1. Compute ARC's internal condition code from BPF's
 * 2. Determine the bitness of the operation (32 vs. 64)
 * 3. Sanity check on BPF stream
 * 4. Sanity check on what is supposed to be JIT's displacement
 * 5. And finally, emit the necessary instructions
 *
 * The last two steps are performed through the back-end.
 * The value of steps 1 and 2 are necessary inputs for the back-end.
 */
static int handle_jumps(const struct jit_context *ctx,
			const struct bpf_insn *insn,
			u8 *len)
{
	u8 cond;
	int ret = 0;
	u8 *buf = effective_jit_buf(ctx);
	const bool j32 = (BPF_CLASS(insn->code) == BPF_JMP32) ? true : false;
	const u8 rd = insn->dst_reg;
	u8 rs = insn->src_reg;
	u32 curr_off = 0, targ_off = 0;

	*len = 0;

	/* Map the BPF condition to internal enum. */
	CHECK_RET(bpf_cond_to_arc(BPF_OP(insn->code), &cond));

	/* Sanity check on the BPF byte stream. */
	CHECK_RET(check_bpf_jump(ctx, insn));

	/*
	 * Move the immediate into a temporary register _now_ for 2 reasons:
	 *
	 * 1. "gen_jmp_{32,64}()" deal with operands in registers.
	 *
	 * 2. The "len" parameter will grow so that the current jit offset
	 *    (curr_off) will have increased to a point where the necessary
	 *    instructions can be inserted by "gen_jmp_{32,64}()".
	 */
	if (has_imm(insn) && cond != ARC_CC_AL) {
		if (j32) {
			*len += mov_r32_i32(BUF(buf, *len), JIT_REG_TMP,
					    insn->imm);
		} else {
			*len += mov_r64_i32(BUF(buf, *len), JIT_REG_TMP,
					    insn->imm);
		}
		rs = JIT_REG_TMP;
	}

	/* If the offsets are known, check if the branch can occur. */
	if (offsets_available(ctx)) {
		curr_off = get_curr_jit_off(ctx, insn) + *len;
		targ_off = get_targ_jit_off(ctx, insn);

		/* Sanity check on the back-end side. */
		CHECK_RET(feasible_jit_jump(curr_off, targ_off, cond, j32));
	}

	if (j32) {
		*len += gen_jmp_32(BUF(buf, *len), rd, rs, cond,
				   curr_off, targ_off);
	} else {
		*len += gen_jmp_64(BUF(buf, *len), rd, rs, cond,
				   curr_off, targ_off);
	}

	return ret;
}

/* Jump to translated epilogue address. */
static int handle_jmp_epilogue(struct jit_context *ctx,
			       const struct bpf_insn *insn, u8 *len)
{
	u8 *buf = effective_jit_buf(ctx);
	u32 curr_off = 0, epi_off = 0;

	/* Check the offset only if the data is available. */
	if (offsets_available(ctx)) {
		curr_off = get_curr_jit_off(ctx, insn);
		epi_off = ctx->epilogue_offset;

		if (!check_jmp_64(curr_off, epi_off, ARC_CC_AL)) {
			pr_err("bpf-jit: epilogue offset is not valid.\n");
			return -EINVAL;
		}
	}

	/* Jump to "epilogue offset" (rd and rs don't matter). */
	*len = gen_jmp_64(buf, 0, 0, ARC_CC_AL, curr_off, epi_off);

	return 0;
}

/* Try to get the resolved address and generate the instructions. */
static int handle_call(struct jit_context *ctx,
		       const struct bpf_insn *insn,
		       u8 *len)
{
	int  ret;
	bool in_kernel_func, fixed = false;
	u64  addr = 0;
	u8  *buf = effective_jit_buf(ctx);

	ret = bpf_jit_get_func_addr(ctx->prog, insn, ctx->is_extra_pass,
				    &addr, &fixed);
	if (ret < 0) {
		pr_err("bpf-jit: can't get the address for call.\n");
		return ret;
	}
	in_kernel_func = (fixed ? true : false);

	/* No valuable address retrieved (yet). */
	if (!fixed && !addr)
		set_need_for_extra_pass(ctx);

	*len = gen_func_call(buf, (ARC_ADDR)addr, in_kernel_func);

	if (insn->src_reg != BPF_PSEUDO_CALL) {
		/* Assigning ABI's return reg to JIT's return reg. */
		*len += arc_to_bpf_return(BUF(buf, *len));
	}

	return 0;
}

/*
 * Try to generate instructions for loading a 64-bit immediate.
 * These sort of instructions are usually associated with the 64-bit
 * relocations: R_BPF_64_64. Therefore, signal the need for an extra
 * pass if the circumstances are right.
 */
static int handle_ld_imm64(struct jit_context *ctx,
			   const struct bpf_insn *insn,
			   u8 *len)
{
	const s32 idx = get_index_for_insn(ctx, insn);
	u8 *buf = effective_jit_buf(ctx);

	/* We're about to consume 2 VM instructions. */
	if (is_last_insn(ctx->prog, idx)) {
		pr_err("bpf-jit: need more data for 64-bit immediate.\n");
		return -EINVAL;
	}

	*len = mov_r64_i64(buf, insn->dst_reg, insn->imm, (insn + 1)->imm);

	if (bpf_pseudo_func(insn))
		set_need_for_extra_pass(ctx);

	return 0;
}

/*
 * Handles one eBPF instruction at a time. To make this function faster,
 * it does not call "jit_buffer_check()". Else, it would call it for every
 * instruction. As a result, it should not be invoked directly. Only
 * "handle_body()", that has already executed the "check", may call this
 * function.
 *
 * If the "ret" value is negative, something has went wrong. Else,
 * it mostly holds the value 0 and rarely 1. Number 1 signals
 * the loop in "handle_body()" to skip the next instruction, because
 * it has been consumed as part of a 64-bit immediate value.
 */
static int handle_insn(struct jit_context *ctx, u32 idx)
{
	const struct bpf_insn *insn = &ctx->prog->insnsi[idx];
	const u8  code = insn->code;
	const u8  dst  = insn->dst_reg;
	const u8  src  = insn->src_reg;
	const s16 off  = insn->off;
	const s32 imm  = insn->imm;
	u8 *buf = effective_jit_buf(ctx);
	u8  len = 0;
	int ret = 0;

	switch (code) {
	/* dst += src (32-bit) */
	case BPF_ALU | BPF_ADD | BPF_X:
		len = add_r32(buf, dst, src);
		break;
	/* dst += imm (32-bit) */
	case BPF_ALU | BPF_ADD | BPF_K:
		len = add_r32_i32(buf, dst, imm);
		break;
	/* dst -= src (32-bit) */
	case BPF_ALU | BPF_SUB | BPF_X:
		len = sub_r32(buf, dst, src);
		break;
	/* dst -= imm (32-bit) */
	case BPF_ALU | BPF_SUB | BPF_K:
		len = sub_r32_i32(buf, dst, imm);
		break;
	/* dst = -dst (32-bit) */
	case BPF_ALU | BPF_NEG:
		len = neg_r32(buf, dst);
		break;
	/* dst *= src (32-bit) */
	case BPF_ALU | BPF_MUL | BPF_X:
		len = mul_r32(buf, dst, src);
		break;
	/* dst *= imm (32-bit) */
	case BPF_ALU | BPF_MUL | BPF_K:
		len = mul_r32_i32(buf, dst, imm);
		break;
	/* dst /= src (32-bit) */
	case BPF_ALU | BPF_DIV | BPF_X:
		len = div_r32(buf, dst, src, off == 1);
		break;
	/* dst /= imm (32-bit) */
	case BPF_ALU | BPF_DIV | BPF_K:
		len = div_r32_i32(buf, dst, imm, off == 1);
		break;
	/* dst %= src (32-bit) */
	case BPF_ALU | BPF_MOD | BPF_X:
		len = mod_r32(buf, dst, src, off == 1);
		break;
	/* dst %= imm (32-bit) */
	case BPF_ALU | BPF_MOD | BPF_K:
		len = mod_r32_i32(buf, dst, imm, off == 1);
		break;
	/* dst &= src (32-bit) */
	case BPF_ALU | BPF_AND | BPF_X:
		len = and_r32(buf, dst, src);
		break;
	/* dst &= imm (32-bit) */
	case BPF_ALU | BPF_AND | BPF_K:
		len = and_r32_i32(buf, dst, imm);
		break;
	/* dst |= src (32-bit) */
	case BPF_ALU | BPF_OR | BPF_X:
		len = or_r32(buf, dst, src);
		break;
	/* dst |= imm (32-bit) */
	case BPF_ALU | BPF_OR | BPF_K:
		len = or_r32_i32(buf, dst, imm);
		break;
	/* dst ^= src (32-bit) */
	case BPF_ALU | BPF_XOR | BPF_X:
		len = xor_r32(buf, dst, src);
		break;
	/* dst ^= imm (32-bit) */
	case BPF_ALU | BPF_XOR | BPF_K:
		len = xor_r32_i32(buf, dst, imm);
		break;
	/* dst <<= src (32-bit) */
	case BPF_ALU | BPF_LSH | BPF_X:
		len = lsh_r32(buf, dst, src);
		break;
	/* dst <<= imm (32-bit) */
	case BPF_ALU | BPF_LSH | BPF_K:
		len = lsh_r32_i32(buf, dst, imm);
		break;
	/* dst >>= src (32-bit) [unsigned] */
	case BPF_ALU | BPF_RSH | BPF_X:
		len = rsh_r32(buf, dst, src);
		break;
	/* dst >>= imm (32-bit) [unsigned] */
	case BPF_ALU | BPF_RSH | BPF_K:
		len = rsh_r32_i32(buf, dst, imm);
		break;
	/* dst >>= src (32-bit) [signed] */
	case BPF_ALU | BPF_ARSH | BPF_X:
		len = arsh_r32(buf, dst, src);
		break;
	/* dst >>= imm (32-bit) [signed] */
	case BPF_ALU | BPF_ARSH | BPF_K:
		len = arsh_r32_i32(buf, dst, imm);
		break;
	/* dst = src (32-bit) */
	case BPF_ALU | BPF_MOV | BPF_X:
		len = mov_r32(buf, dst, src, (u8)off);
		break;
	/* dst = imm32 (32-bit) */
	case BPF_ALU | BPF_MOV | BPF_K:
		len = mov_r32_i32(buf, dst, imm);
		break;
	/* dst = swap(dst) */
	case BPF_ALU   | BPF_END | BPF_FROM_LE:
	case BPF_ALU   | BPF_END | BPF_FROM_BE:
	case BPF_ALU64 | BPF_END | BPF_FROM_LE: {
		CHECK_RET(handle_swap(buf, dst, imm, BPF_SRC(code),
				      BPF_CLASS(code) == BPF_ALU64,
				      ctx->do_zext, &len));
		break;
	}
	/* dst += src (64-bit) */
	case BPF_ALU64 | BPF_ADD | BPF_X:
		len = add_r64(buf, dst, src);
		break;
	/* dst += imm32 (64-bit) */
	case BPF_ALU64 | BPF_ADD | BPF_K:
		len = add_r64_i32(buf, dst, imm);
		break;
	/* dst -= src (64-bit) */
	case BPF_ALU64 | BPF_SUB | BPF_X:
		len = sub_r64(buf, dst, src);
		break;
	/* dst -= imm32 (64-bit) */
	case BPF_ALU64 | BPF_SUB | BPF_K:
		len = sub_r64_i32(buf, dst, imm);
		break;
	/* dst = -dst (64-bit) */
	case BPF_ALU64 | BPF_NEG:
		len = neg_r64(buf, dst);
		break;
	/* dst *= src (64-bit) */
	case BPF_ALU64 | BPF_MUL | BPF_X:
		len = mul_r64(buf, dst, src);
		break;
	/* dst *= imm32 (64-bit) */
	case BPF_ALU64 | BPF_MUL | BPF_K:
		len = mul_r64_i32(buf, dst, imm);
		break;
	/* dst &= src (64-bit) */
	case BPF_ALU64 | BPF_AND | BPF_X:
		len = and_r64(buf, dst, src);
		break;
	/* dst &= imm32 (64-bit) */
	case BPF_ALU64 | BPF_AND | BPF_K:
		len = and_r64_i32(buf, dst, imm);
		break;
	/* dst |= src (64-bit) */
	case BPF_ALU64 | BPF_OR | BPF_X:
		len = or_r64(buf, dst, src);
		break;
	/* dst |= imm32 (64-bit) */
	case BPF_ALU64 | BPF_OR | BPF_K:
		len = or_r64_i32(buf, dst, imm);
		break;
	/* dst ^= src (64-bit) */
	case BPF_ALU64 | BPF_XOR | BPF_X:
		len = xor_r64(buf, dst, src);
		break;
	/* dst ^= imm32 (64-bit) */
	case BPF_ALU64 | BPF_XOR | BPF_K:
		len = xor_r64_i32(buf, dst, imm);
		break;
	/* dst <<= src (64-bit) */
	case BPF_ALU64 | BPF_LSH | BPF_X:
		len = lsh_r64(buf, dst, src);
		break;
	/* dst <<= imm32 (64-bit) */
	case BPF_ALU64 | BPF_LSH | BPF_K:
		len = lsh_r64_i32(buf, dst, imm);
		break;
	/* dst >>= src (64-bit) [unsigned] */
	case BPF_ALU64 | BPF_RSH | BPF_X:
		len = rsh_r64(buf, dst, src);
		break;
	/* dst >>= imm32 (64-bit) [unsigned] */
	case BPF_ALU64 | BPF_RSH | BPF_K:
		len = rsh_r64_i32(buf, dst, imm);
		break;
	/* dst >>= src (64-bit) [signed] */
	case BPF_ALU64 | BPF_ARSH | BPF_X:
		len = arsh_r64(buf, dst, src);
		break;
	/* dst >>= imm32 (64-bit) [signed] */
	case BPF_ALU64 | BPF_ARSH | BPF_K:
		len = arsh_r64_i32(buf, dst, imm);
		break;
	/* dst = src (64-bit) */
	case BPF_ALU64 | BPF_MOV | BPF_X:
		len = mov_r64(buf, dst, src, (u8)off);
		break;
	/* dst = imm32 (sign extend to 64-bit) */
	case BPF_ALU64 | BPF_MOV | BPF_K:
		len = mov_r64_i32(buf, dst, imm);
		break;
	/* dst = imm64 */
	case BPF_LD | BPF_DW | BPF_IMM:
		CHECK_RET(handle_ld_imm64(ctx, insn, &len));
		/* Tell the loop to skip the next instruction. */
		ret = 1;
		break;
	/* 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:
		len = load_r(buf, dst, src, off, BPF_SIZE(code), false);
		break;
	case BPF_LDX | BPF_MEMSX | BPF_W:
	case BPF_LDX | BPF_MEMSX | BPF_H:
	case BPF_LDX | BPF_MEMSX | BPF_B:
		len = load_r(buf, dst, src, off, BPF_SIZE(code), true);
		break;
	/* *(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:
		len = store_r(buf, src, dst, off, BPF_SIZE(code));
		break;
	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:
		len = store_i(buf, imm, dst, off, BPF_SIZE(code));
		break;
	case BPF_JMP   | BPF_JA:
	case BPF_JMP   | BPF_JEQ  | BPF_X:
	case BPF_JMP   | BPF_JEQ  | BPF_K:
	case BPF_JMP   | BPF_JNE  | BPF_X:
	case BPF_JMP   | BPF_JNE  | BPF_K:
	case BPF_JMP   | BPF_JSET | BPF_X:
	case BPF_JMP   | BPF_JSET | BPF_K:
	case BPF_JMP   | BPF_JGT  | BPF_X:
	case BPF_JMP   | BPF_JGT  | BPF_K:
	case BPF_JMP   | BPF_JGE  | BPF_X:
	case BPF_JMP   | BPF_JGE  | BPF_K:
	case BPF_JMP   | BPF_JSGT | BPF_X:
	case BPF_JMP   | BPF_JSGT | BPF_K:
	case BPF_JMP   | BPF_JSGE | BPF_X:
	case BPF_JMP   | BPF_JSGE | BPF_K:
	case BPF_JMP   | BPF_JLT  | BPF_X:
	case BPF_JMP   | BPF_JLT  | BPF_K:
	case BPF_JMP   | BPF_JLE  | BPF_X:
	case BPF_JMP   | BPF_JLE  | BPF_K:
	case BPF_JMP   | BPF_JSLT | BPF_X:
	case BPF_JMP   | BPF_JSLT | BPF_K:
	case BPF_JMP   | BPF_JSLE | BPF_X:
	case BPF_JMP   | BPF_JSLE | BPF_K:
	case BPF_JMP32 | BPF_JA:
	case BPF_JMP32 | BPF_JEQ  | BPF_X:
	case BPF_JMP32 | BPF_JEQ  | BPF_K:
	case BPF_JMP32 | BPF_JNE  | BPF_X:
	case BPF_JMP32 | BPF_JNE  | BPF_K:
	case BPF_JMP32 | BPF_JSET | BPF_X:
	case BPF_JMP32 | BPF_JSET | BPF_K:
	case BPF_JMP32 | BPF_JGT  | BPF_X:
	case BPF_JMP32 | BPF_JGT  | BPF_K:
	case BPF_JMP32 | BPF_JGE  | BPF_X:
	case BPF_JMP32 | BPF_JGE  | BPF_K:
	case BPF_JMP32 | BPF_JSGT | BPF_X:
	case BPF_JMP32 | BPF_JSGT | BPF_K:
	case BPF_JMP32 | BPF_JSGE | BPF_X:
	case BPF_JMP32 | BPF_JSGE | BPF_K:
	case BPF_JMP32 | BPF_JLT  | BPF_X:
	case BPF_JMP32 | BPF_JLT  | BPF_K:
	case BPF_JMP32 | BPF_JLE  | BPF_X:
	case BPF_JMP32 | BPF_JLE  | BPF_K:
	case BPF_JMP32 | BPF_JSLT | BPF_X:
	case BPF_JMP32 | BPF_JSLT | BPF_K:
	case BPF_JMP32 | BPF_JSLE | BPF_X:
	case BPF_JMP32 | BPF_JSLE | BPF_K:
		CHECK_RET(handle_jumps(ctx, insn, &len));
		break;
	case BPF_JMP | BPF_CALL:
		CHECK_RET(handle_call(ctx, insn, &len));
		break;

	case BPF_JMP | BPF_EXIT:
		/* If this is the last instruction, epilogue will follow. */
		if (is_last_insn(ctx->prog, idx))
			break;
		CHECK_RET(handle_jmp_epilogue(ctx, insn, &len));
		break;
	default:
		pr_err("bpf-jit: can't handle instruction code 0x%02X\n", code);
		return -EOPNOTSUPP;
	}

	if (BPF_CLASS(code) == BPF_ALU) {
		/*
		 * Skip the "swap" instructions. Even 64-bit swaps are of type
		 * BPF_ALU (and not BPF_ALU64). Therefore, for the swaps, one
		 * has to look at the "size" of the operations rather than the
		 * ALU type. "gen_swap()" specifically takes care of that.
		 */
		if (BPF_OP(code) != BPF_END && ctx->do_zext)
			len += zext(BUF(buf, len), dst);
	}

	jit_buffer_update(ctx, len);

	return ret;
}

static int handle_body(struct jit_context *ctx)
{
	int ret;
	bool populate_bpf2insn = false;
	const struct bpf_prog *prog = ctx->prog;

	CHECK_RET(jit_buffer_check(ctx));

	/*
	 * Record the mapping for the instructions during the dry-run.
	 * Doing it this way allows us to have the mapping ready for
	 * the jump instructions during the real compilation phase.
	 */
	if (!ctx->emit)
		populate_bpf2insn = true;

	for (u32 i = 0; i < prog->len; i++) {
		/* During the dry-run, jit.len grows gradually per BPF insn. */
		if (populate_bpf2insn)
			ctx->bpf2insn[i] = ctx->jit.len;

		CHECK_RET(handle_insn(ctx, i));
		if (ret > 0) {
			/* "ret" is 1 if two (64-bit) chunks were consumed. */
			ctx->bpf2insn[i + 1] = ctx->bpf2insn[i];
			i++;
		}
	}

	/* If bpf2insn had to be populated, then it is done at this point. */
	if (populate_bpf2insn)
		ctx->bpf2insn_valid = true;

	return 0;
}

/*
 * Initialize the memory with "unimp_s" which is the mnemonic for
 * "unimplemented" instruction and always raises an exception.
 *
 * The instruction is 2 bytes. If "size" is odd, there is not much
 * that can be done about the last byte in "area". Because, the
 * CPU always fetches instructions in two bytes. Therefore, the
 * byte beyond the last one is going to accompany it during a
 * possible fetch. In the most likely case of a little endian
 * system, that beyond-byte will become the major opcode and
 * we have no control over its initialisation.
 */
static void fill_ill_insn(void *area, unsigned int size)
{
	const u16 unimp_s = 0x79e0;

	if (size & 1) {
		*((u8 *)area + (size - 1)) = 0xff;
		size -= 1;
	}

	memset16(area, unimp_s, size >> 1);
}

/* Piece of memory that can be allocated at the beginning of jit_prepare(). */
static int jit_prepare_early_mem_alloc(struct jit_context *ctx)
{
	ctx->bpf2insn = kcalloc(ctx->prog->len, sizeof(ctx->jit.len),
				GFP_KERNEL);

	if (!ctx->bpf2insn) {
		pr_err("bpf-jit: could not allocate memory for "
		       "mapping of the instructions.\n");
		return -ENOMEM;
	}

	return 0;
}

/*
 * Memory allocations that rely on parameters known at the end of
 * jit_prepare().
 */
static int jit_prepare_final_mem_alloc(struct jit_context *ctx)
{
	const size_t alignment = sizeof(u32);

	ctx->bpf_header = bpf_jit_binary_alloc(ctx->jit.len, &ctx->jit.buf,
					       alignment, fill_ill_insn);
	if (!ctx->bpf_header) {
		pr_err("bpf-jit: could not allocate memory for translation.\n");
		return -ENOMEM;
	}

	if (ctx->need_extra_pass) {
		ctx->jit_data = kzalloc(sizeof(*ctx->jit_data), GFP_KERNEL);
		if (!ctx->jit_data)
			return -ENOMEM;
	}

	return 0;
}

/*
 * The first phase of the translation without actually emitting any
 * instruction. It helps in getting a forecast on some aspects, such
 * as the length of the whole program or where the epilogue starts.
 *
 * Whenever the necessary parameters are known, memories are allocated.
 */
static int jit_prepare(struct jit_context *ctx)
{
	int ret;

	/* Dry run. */
	ctx->emit = false;

	CHECK_RET(jit_prepare_early_mem_alloc(ctx));

	/* Get the length of prologue section after some register analysis. */
	analyze_reg_usage(ctx);
	CHECK_RET(handle_prologue(ctx));

	CHECK_RET(handle_body(ctx));

	/* Record at which offset epilogue begins. */
	ctx->epilogue_offset = ctx->jit.len;

	/* Process the epilogue section now. */
	CHECK_RET(handle_epilogue(ctx));

	CHECK_RET(jit_prepare_final_mem_alloc(ctx));

	return 0;
}

/*
 * All the "handle_*()" functions have been called before by the
 * "jit_prepare()". If there was an error, we would know by now.
 * Therefore, no extra error checking at this point, other than
 * a sanity check at the end that expects the calculated length
 * (jit.len) to be equal to the length of generated instructions
 * (jit.index).
 */
static int jit_compile(struct jit_context *ctx)
{
	int ret;

	/* Let there be code. */
	ctx->emit = true;

	CHECK_RET(handle_prologue(ctx));

	CHECK_RET(handle_body(ctx));

	CHECK_RET(handle_epilogue(ctx));

	if (ctx->jit.index != ctx->jit.len) {
		pr_err("bpf-jit: divergence between the phases; "
		       "%u vs. %u (bytes).\n",
		       ctx->jit.len, ctx->jit.index);
		return -EFAULT;
	}

	return 0;
}

/*
 * Calling this function implies a successful JIT. A successful
 * translation is signaled by setting the right parameters:
 *
 * prog->jited=1, prog->jited_len=..., prog->bpf_func=...
 */
static int jit_finalize(struct jit_context *ctx)
{
	struct bpf_prog *prog = ctx->prog;

	/* We're going to need this information for the "do_extra_pass()". */
	if (ctx->need_extra_pass) {
		ctx->jit_data->bpf_header = ctx->bpf_header;
		ctx->jit_data->bpf2insn = ctx->bpf2insn;
		prog->aux->jit_data = (void *)ctx->jit_data;
	} else {
		/*
		 * If things seem finalised, then mark the JITed memory
		 * as R-X and flush it.
		 */
		if (bpf_jit_binary_lock_ro(ctx->bpf_header)) {
			pr_err("bpf-jit: Could not lock the JIT memory.\n");
			return -EFAULT;
		}
		flush_icache_range((unsigned long)ctx->bpf_header,
				   (unsigned long)
				   BUF(ctx->jit.buf, ctx->jit.len));
		prog->aux->jit_data = NULL;
		bpf_prog_fill_jited_linfo(prog, ctx->bpf2insn);
	}

	ctx->success = true;
	prog->bpf_func = (void *)ctx->jit.buf;
	prog->jited_len = ctx->jit.len;
	prog->jited = 1;

	jit_ctx_cleanup(ctx);
	jit_dump(ctx);

	return 0;
}

/*
 * A lenient verification for the existence of JIT context in "prog".
 * Apparently the JIT internals, namely jit_subprogs() in bpf/verifier.c,
 * may request for a second compilation although nothing needs to be done.
 */
static inline int check_jit_context(const struct bpf_prog *prog)
{
	if (!prog->aux->jit_data) {
		pr_notice("bpf-jit: no jit data for the extra pass.\n");
		return 1;
	} else {
		return 0;
	}
}

/* Reuse the previous pass's data. */
static int jit_resume_context(struct jit_context *ctx)
{
	struct arc_jit_data *jdata =
		(struct arc_jit_data *)ctx->prog->aux->jit_data;

	if (!jdata) {
		pr_err("bpf-jit: no jit data for the extra pass.\n");
		return -EINVAL;
	}

	ctx->jit.buf = (u8 *)ctx->prog->bpf_func;
	ctx->jit.len = ctx->prog->jited_len;
	ctx->bpf_header = jdata->bpf_header;
	ctx->bpf2insn = (u32 *)jdata->bpf2insn;
	ctx->bpf2insn_valid = ctx->bpf2insn ? true : false;
	ctx->jit_data = jdata;

	return 0;
}

/*
 * Patch in the new addresses. The instructions of interest are:
 *
 * - call
 * - ld r64, imm64
 *
 * For "call"s, it resolves the addresses one more time through the
 * handle_call().
 *
 * For 64-bit immediate loads, it just retranslates them, because the BPF
 * core in kernel might have changed the value since the normal pass.
 */
static int jit_patch_relocations(struct jit_context *ctx)
{
	const u8 bpf_opc_call = BPF_JMP | BPF_CALL;
	const u8 bpf_opc_ldi64 = BPF_LD | BPF_DW | BPF_IMM;
	const struct bpf_prog *prog = ctx->prog;
	int ret;

	ctx->emit = true;
	for (u32 i = 0; i < prog->len; i++) {
		const struct bpf_insn *insn = &prog->insnsi[i];
		u8 dummy;
		/*
		 * Adjust "ctx.jit.index", so "gen_*()" functions below
		 * can use it for their output addresses.
		 */
		ctx->jit.index = ctx->bpf2insn[i];

		if (insn->code == bpf_opc_call) {
			CHECK_RET(handle_call(ctx, insn, &dummy));
		} else if (insn->code == bpf_opc_ldi64) {
			CHECK_RET(handle_ld_imm64(ctx, insn, &dummy));
			/* Skip the next instruction. */
			++i;
		}
	}
	return 0;
}

/*
 * A normal pass that involves a "dry-run" phase, jit_prepare(),
 * to get the necessary data for the real compilation phase,
 * jit_compile().
 */
static struct bpf_prog *do_normal_pass(struct bpf_prog *prog)
{
	struct jit_context ctx;

	/* Bail out if JIT is disabled. */
	if (!prog->jit_requested)
		return prog;

	if (jit_ctx_init(&ctx, prog)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	/* Get the lengths and allocate buffer. */
	if (jit_prepare(&ctx)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	if (jit_compile(&ctx)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	if (jit_finalize(&ctx)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	return ctx.prog;
}

/*
 * If there are multi-function BPF programs that call each other,
 * their translated addresses are not known all at once. Therefore,
 * an extra pass is needed to consult the bpf_jit_get_func_addr()
 * again to get the newly translated addresses in order to resolve
 * the "call"s.
 */
static struct bpf_prog *do_extra_pass(struct bpf_prog *prog)
{
	struct jit_context ctx;

	/* Skip if there's no context to resume from. */
	if (check_jit_context(prog))
		return prog;

	if (jit_ctx_init(&ctx, prog)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	if (jit_resume_context(&ctx)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	if (jit_patch_relocations(&ctx)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	if (jit_finalize(&ctx)) {
		jit_ctx_cleanup(&ctx);
		return prog;
	}

	return ctx.prog;
}

/*
 * This function may be invoked twice for the same stream of BPF
 * instructions. The "extra pass" happens, when there are "call"s
 * involved that their addresses are not known during the first
 * invocation.
 */
struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
{
	vm_dump(prog);

	/* Was this program already translated? */
	if (!prog->jited)
		return do_normal_pass(prog);
	else
		return do_extra_pass(prog);

	return prog;
}