Quelle  bpf_jit_core.c

// 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);

 /* 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;
}

/*
 * jit_compile() is the real compilation phase. jit_prepare() is
 * invoked before jit_compile() as a dry-run to make sure everything
 * will go OK and allocate the necessary memory.
 *
 * In the end, jit_compile() checks if it has produced the same number
 * of instructions as jit_prepare() would.
 */
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
 * (re)locations involved that their addresses are not known
 * during the first run.
 */
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;
}