项目经验分享：Linux内核eBPF模块源码分析——verifier与jit部分

struct bpf_insn {
  __u8  code;    /* opcode */
  __u8  dst_reg:4;  /* dest register */
  __u8  src_reg:4;  /* source register */
  __s16  off;    /* signed offset */
  __s32  imm;    /* signed immediate constant */
};


struct bpf_insn insn[] = {
    BPF_LD_MAP_FD(BPF_REG_1,3),
    ......


};

static int bpf_prog_load(enum bpf_prog_type prog_type,
        const struct bpf_insn *insns, int prog_len,
        const char *license, int kern_version){


    union bpf_attr attr = {
        .prog_type = prog_type,
        .insns = (uint64_t)insns,
        .insn_cnt = prog_len / sizeof(struct bpf_insn),
        .license = (uint64_t)license,
        .log_buf = (uint64_t)bpf_log_buf,
        .log_size = LOG_BUF_SIZE,
        .log_level = 1,
    };
    attr.kern_version = kern_version;
    bpf_log_buf[0] = 0;
    return syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
}

  case BPF_PROG_LOAD:
    err = bpf_prog_load(&attr, uattr);
    break;

struct bpf_prog {
  u16      pages;    /* Number of allocated pages */
  u16      jited:1,  /* Is our filter JIT'ed? */
        jit_requested:1,/* archs need to JIT the prog */
        gpl_compatible:1, /* Is filter GPL compatible? */
        cb_access:1,  /* Is control block accessed? */
        dst_needed:1,  /* Do we need dst entry? */
        blinded:1,  /* Was blinded */
        is_func:1,  /* program is a bpf function */
        kprobe_override:1, /* Do we override a kprobe? */
        has_callchain_buf:1, /* callchain buffer allocated? */
        enforce_expected_attach_type:1; /* Enforce expected_attach_type checking at attach time */
  enum bpf_prog_type  type;    /* Type of BPF program */
  enum bpf_attach_type  expected_attach_type; /* For some prog types */
  u32      len;    /* Number of filter blocks */
  u32      jited_len;  /* Size of jited insns in bytes */
  u8      tag[BPF_TAG_SIZE];
  struct bpf_prog_aux  *aux;    /* Auxiliary fields */
  struct sock_fprog_kern  *orig_prog;  /* Original BPF program */
  unsigned int    (*bpf_func)(const void *ctx,
              const struct bpf_insn *insn);
  /* Instructions for interpreter */
  union {
    struct sock_filter  insns[0];
    struct bpf_insn    insnsi[0];
  };
};

static int bpf_prog_load(union bpf_attr *attr, union bpf_attr __user *uattr)
{
  enum bpf_prog_type type = attr->prog_type;
  struct bpf_prog *prog;
  int err;
  char license[128];
  bool is_gpl;


  ......


  /* plain bpf_prog allocation */
  prog = bpf_prog_alloc(bpf_prog_size(attr->insn_cnt), GFP_USER);
  if (!prog)
    return -ENOMEM;


  ......




  prog->len = attr->insn_cnt;


  err = -EFAULT;
  if (copy_from_user(prog->insns, u64_to_user_ptr(attr->insns),
         bpf_prog_insn_size(prog)) != 0)
    goto free_prog;


  prog->orig_prog = NULL;
  prog->jited = 0;  //还没有jit编译


  ......


  /* find program type: socket_filter vs tracing_filter */
  /*
  
  type = array_index_nospec(type, ARRAY_SIZE(bpf_prog_types));
  ops = bpf_prog_types[type];
  
  */
  err = find_prog_type(type, prog);
  if (err < 0)
    goto free_prog;


  ......


  /* run eBPF verifier */
  err = bpf_check(&prog, attr, uattr);
  if (err < 0)
    goto free_used_maps;


  prog = bpf_prog_select_runtime(prog, &err);
  if (err < 0)
    goto free_used_maps;


  err = bpf_prog_alloc_id(prog);
  if (err)
    goto free_used_maps;
  
  ......
}

  /* run eBPF verifier */
  err = bpf_check(&prog, attr, uattr);

int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
        union bpf_attr __user *uattr)
{
  u64 start_time = ktime_get_ns();
  struct bpf_verifier_env *env;
  struct bpf_verifier_log *log;
  int i, len, ret = -EINVAL;
  bool is_priv;


  ......


  len = (*prog)->len;
  env->insn_aux_data =
    vzalloc(array_size(sizeof(struct bpf_insn_aux_data), len));
  ret = -ENOMEM;
  if (!env->insn_aux_data)
    goto err_free_env;
  for (i = 0; i < len; i++)
    env->insn_aux_data[i].orig_idx = i;
  env->prog = *prog;
  env->ops = bpf_verifier_ops[env->prog->type];
  is_priv = capable(CAP_SYS_ADMIN);


  ......


  /* 设置对齐 */
  env->strict_alignment = !!(attr->prog_flags & BPF_F_STRICT_ALIGNMENT);
  if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
    env->strict_alignment = true;
  if (attr->prog_flags & BPF_F_ANY_ALIGNMENT)
    env->strict_alignment = false;


  env->allow_ptr_leaks = is_priv;


  if (is_priv)
    env->test_state_freq = attr->prog_flags & BPF_F_TEST_STATE_FREQ;


  ret = replace_map_fd_with_map_ptr(env);
  if (ret < 0)
    goto skip_full_check;


  if (bpf_prog_is_dev_bound(env->prog->aux)) {
    ret = bpf_prog_offload_verifier_prep(env->prog);
    if (ret)
      goto skip_full_check;
  }


  env->explored_states = kvcalloc(state_htab_size(env),
               sizeof(struct bpf_verifier_state_list *),
               GFP_USER);
  ret = -ENOMEM;
  if (!env->explored_states)
    goto skip_full_check;


  ret = check_subprogs(env);
  if (ret < 0)
    goto skip_full_check;


  ret = check_btf_info(env, attr, uattr);
  if (ret < 0)
    goto skip_full_check;


  ret = check_attach_btf_id(env);
  if (ret)
    goto skip_full_check;


  ret = check_cfg(env);
  if (ret < 0)
    goto skip_full_check;


  ret = do_check_subprogs(env);
  ret = ret ?: do_check_main(env);


  if (ret == 0 && bpf_prog_is_dev_bound(env->prog->aux))
    ret = bpf_prog_offload_finalize(env);


skip_full_check:
  kvfree(env->explored_states);


  if (ret == 0)
    ret = check_max_stack_depth(env);


  /* instruction rewrites happen after this point */
  if (is_priv) {
    if (ret == 0)
      opt_hard_wire_dead_code_branches(env);
    if (ret == 0)
      ret = opt_remove_dead_code(env);
    if (ret == 0)
      ret = opt_remove_nops(env);
  } else {
    if (ret == 0)
      sanitize_dead_code(env);
  }


  if (ret == 0)
    /* program is valid, convert *(u32*)(ctx + off) accesses */
    ret = convert_ctx_accesses(env);


  if (ret == 0)
    ret = fixup_bpf_calls(env);


  /* do 32-bit optimization after insn patching has done so those patched
   * insns could be handled correctly.
   */
  if (ret == 0 && !bpf_prog_is_dev_bound(env->prog->aux)) {
    ret = opt_subreg_zext_lo32_rnd_hi32(env, attr);
    env->prog->aux->verifier_zext = bpf_jit_needs_zext() ? !ret
                     : false;
  }


  if (ret == 0)
    ret = fixup_call_args(env);


  env->verification_time = ktime_get_ns() - start_time;
  print_verification_stats(env);


  if (log->level && bpf_verifier_log_full(log))
    ret = -ENOSPC;
  if (log->level && !log->ubuf) {
    ret = -EFAULT;
    goto err_release_maps;
  }


  if (ret == 0 && env->used_map_cnt) {
    /* if program passed verifier, update used_maps in bpf_prog_info */
    env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt,
                sizeof(env->used_maps[0]),
                GFP_KERNEL);


    if (!env->prog->aux->used_maps) {
      ret = -ENOMEM;
      goto err_release_maps;
    }


    memcpy(env->prog->aux->used_maps, env->used_maps,
           sizeof(env->used_maps[0]) * env->used_map_cnt);
    env->prog->aux->used_map_cnt = env->used_map_cnt;


    /* program is valid. Convert pseudo bpf_ld_imm64 into generic
     * bpf_ld_imm64 instructions
     */
    convert_pseudo_ld_imm64(env);
  }


  if (ret == 0)
    adjust_btf_func(env);


err_release_maps:
  if (!env->prog->aux->used_maps)
    /* if we didn't copy map pointers into bpf_prog_info, release
     * them now. Otherwise free_used_maps() will release them.
     */
    release_maps(env);
  *prog = env->prog;
err_unlock:
  if (!is_priv)
    mutex_unlock(&bpf_verifier_lock);
  vfree(env->insn_aux_data);
err_free_env:
  kfree(env);
  return ret;
}

int bpf_prog_calc_tag(struct bpf_prog *fp)
{
  ......
  bool was_ld_map;
  struct bpf_insn *dst;
  u8 *raw, *todo;
  ......
  raw = vmalloc(raw_size);
  if (!raw)
    return -ENOMEM;
  ......
/* We need to take out the map fd for the digest calculation
   * since they are unstable from user space side.
   */
  dst = (void *)raw;
  for (i = 0, was_ld_map = false; i < fp->len; i++) {
    dst[i] = fp->insnsi[i];
    if (!was_ld_map &&
        dst[i].code == (BPF_LD | BPF_IMM | BPF_DW) &&
        (dst[i].src_reg == BPF_PSEUDO_MAP_FD ||
         dst[i].src_reg == BPF_PSEUDO_MAP_VALUE)) {
      was_ld_map = true;
      dst[i].imm = 0;
    } else if (was_ld_map &&
         dst[i].code == 0 &&
         dst[i].dst_reg == 0 &&
         dst[i].src_reg == 0 &&
         dst[i].off == 0) {
      was_ld_map = false;
      dst[i].imm = 0;
    } else {
      was_ld_map = false;
    }
  }
  
  
  psize = bpf_prog_insn_size(fp);
  memset(&raw[psize], 0, raw_size - psize);
  raw[psize++] = 0x80;
  ......
}

/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */
#define BPF_LD_MAP_FD(DST, MAP_FD)        \
  BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD)




#define BPF_LD_IMM64_RAW(DST, SRC, IMM)        \
  ((struct bpf_insn) {          \
    .code  = BPF_LD | BPF_DW | BPF_IMM,    \
    .dst_reg = DST,          \
    .src_reg = SRC,          \
    .off   = 0,          \
    .imm   = (__u32) (IMM) }),      \
  ((struct bpf_insn) {          \
    .code  = 0, /* zero is reserved opcode */  \
    .dst_reg = 0,          \
    .src_reg = 0,          \
    .off   = 0,          \
    .imm   = ((__u64) (IMM)) >> 32 })

bool bpf_opcode_in_insntable(u8 code)
{
#define BPF_INSN_2_TBL(x, y)    [BPF_##x | BPF_##y] = true
#define BPF_INSN_3_TBL(x, y, z) [BPF_##x | BPF_##y | BPF_##z] = true
  static const bool public_insntable[256] = {
    [0 ... 255] = false,
    /* Now overwrite non-defaults ... */
    BPF_INSN_MAP(BPF_INSN_2_TBL, BPF_INSN_3_TBL),
    /* UAPI exposed, but rewritten opcodes. cBPF carry-over. */
    [BPF_LD | BPF_ABS | BPF_B] = true,
    [BPF_LD | BPF_ABS | BPF_H] = true,
    [BPF_LD | BPF_ABS | BPF_W] = true,
    [BPF_LD | BPF_IND | BPF_B] = true,
    [BPF_LD | BPF_IND | BPF_H] = true,
    [BPF_LD | BPF_IND | BPF_W] = true,
  };
#undef BPF_INSN_3_TBL
#undef BPF_INSN_2_TBL
  return public_insntable[code];
}

/* now check that all jumps are within the same subprog */
  subprog_start = subprog[cur_subprog].start;
  subprog_end = subprog[cur_subprog + 1].start;
  for (i = 0; i < insn_cnt; i++) {
    u8 code = insn[i].code;


    if (BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32)
      goto next;
    if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
      goto next;
    off = i + insn[i].off + 1;
    if (off < subprog_start || off >= subprog_end) {
      verbose(env, "jump out of range from insn %d to %d\n", i, off);
      return -EINVAL;
    }
next:
    if (i == subprog_end - 1) {
      if (code != (BPF_JMP | BPF_EXIT) &&
          code != (BPF_JMP | BPF_JA)) {
        verbose(env, "last insn is not an exit or jmp\n");
        return -EINVAL;
      }
      subprog_start = subprog_end;
      cur_subprog++;
      if (cur_subprog < env->subprog_cnt)
        subprog_end = subprog[cur_subprog + 1].start;
    }
  }

  struct {
    int *insn_state;
    int *insn_stack;
    int cur_stack;
  } cfg;

enum {
  DISCOVERED = 0x10,
  EXPLORED = 0x20,    
  FALLTHROUGH = 1,    //顺序执行
  BRANCH = 2,          //条件跳转
};

/* non-recursive depth-first-search to detect loops in BPF program
 * loop == back-edge in directed graph
 */
static int check_cfg(struct bpf_verifier_env *env)
{
  struct bpf_insn *insns = env->prog->insnsi;
  int insn_cnt = env->prog->len;
  int *insn_stack, *insn_state;
  int ret = 0;
  int i, t;


  //分配空间
  //insn_state 用来记录指令的状态
  insn_state = env->cfg.insn_state = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
  if (!insn_state)
    return -ENOMEM;
  
  //insn_stack 是存储指令的栈
  insn_stack = env->cfg.insn_stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
  if (!insn_stack) {
    kvfree(insn_state);
    return -ENOMEM;
  }


  //首先将第一个结点的状态标记为 discovered
  insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */
  //第一条指令为0
  insn_stack[0] = 0; /* 0 is the first instruction */
  //cfg_cur_stack指向指令栈中当前指令的位置（index）
  env->cfg.cur_stack = 1;


peek_stack:
  //如果栈中已经没有元素，全部退栈，检查所有指令的状态是否都为explored。
  //若有不是explored说明不可达。
  if (env->cfg.cur_stack == 0)
    goto check_state;
  
  //取当前的指令为结点t。
  t = insn_stack[env->cfg.cur_stack - 1];


  if (BPF_CLASS(insns[t].code) == BPF_JMP ||
      BPF_CLASS(insns[t].code) == BPF_JMP32) 
  {
    u8 opcode = BPF_OP(insns[t].code);


    if (opcode == BPF_EXIT) {
      //如果是exit，则标记为explored。
      //因为exit不可能再有出边了。
      goto mark_explored;
    } else if (opcode == BPF_CALL) {
      //当前指令如果是call调用函数
      //将下一条指令压栈，在push中做了loop detect
      ret = push_insn(t, t + 1, FALLTHROUGH, env, false);  
      //如果压栈成功，ret=1
      if (ret == 1)
        goto peek_stack;
      //如果压栈失败，ret<0
      else if (ret < 0)
        goto err_free;
      if (t + 1 < insn_cnt)
        init_explored_state(env, t + 1);
      
      //这里对应两种BPF_CALL
      //若果是bpf函数调用，将被调用函数入栈，标记结点为branch
      //如果src_reg = 0，说明是kernel func，不需要对被调用函数入栈的操作
      if (insns[t].src_reg == BPF_PSEUDO_CALL) {
        init_explored_state(env, t);
        ret = push_insn(t, t + insns[t].imm + 1, BRANCH,
            env, false);
        if (ret == 1)
          goto peek_stack;
        else if (ret < 0)
          goto err_free;
      }
    } else if (opcode == BPF_JA) {
      //如果是无条件跳转
      if (BPF_SRC(insns[t].code) != BPF_K) {
        ret = -EINVAL;
        goto err_free;
      }
      /* unconditional jump with single edge */
      //将跳转的对应跳转分支结点入栈
      ret = push_insn(t, t + insns[t].off + 1,
          FALLTHROUGH, env, true);
      if (ret == 1)
        goto peek_stack;
      else if (ret < 0)
        goto err_free;
      /* unconditional jmp is not a good pruning point,
       * but it's marked, since backtracking needs
       * to record jmp history in is_state_visited().
       */
      init_explored_state(env, t + insns[t].off + 1);
      /* tell verifier to check for equivalent states
       * after every call and jump
       */
      if (t + 1 < insn_cnt)
        init_explored_state(env, t + 1);
    } else {
      /* conditional jump with two edges */
      //有双分支结点的条件跳转指令
      //两个分支都进行压栈，模拟执行
      init_explored_state(env, t);
      //先压fasle分支
      ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
      if (ret == 1)
        goto peek_stack;
      else if (ret < 0)
        goto err_free;
      //再压true分支
      ret = push_insn(t, t + insns[t].off + 1, BRANCH, env, true);
      if (ret == 1)
        goto peek_stack;
      else if (ret < 0)
        goto err_free;
    }
  } else {
    /* all other non-branch instructions with single
     * fall-through edge
     */
    //不存在分支的正常指令入栈
    ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
    if (ret == 1)
      goto peek_stack;
    else if (ret < 0)
      goto err_free;
  }


//exit指令，标记当前结点为explored状态。栈指针减一，退栈。
mark_explored:
  insn_state[t] = EXPLORED;
  if (env->cfg.cur_stack-- <= 0) {
    verbose(env, "pop stack internal bug\n");
    ret = -EFAULT;
    goto err_free;
  }
  goto peek_stack;


//检测是否最终所有指令结点都被扫描完了
check_state:
  for (i = 0; i < insn_cnt; i++) {
    if (insn_state[i] != EXPLORED) {
      verbose(env, "unreachable insn %d\n", i);
      ret = -EINVAL;
      goto err_free;
    }
  }
  ret = 0; /* cfg looks good */


err_free:
  kvfree(insn_state);
  kvfree(insn_stack);
  env->cfg.insn_state = env->cfg.insn_stack = NULL;
  return ret;
}

/* t, w, e - match pseudo-code above:
 * t - index of current instruction
 * w - next instruction
 * e - edge
 */
static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
         bool loop_ok)
{


  int *insn_stack = env->cfg.insn_stack;
  int *insn_state = env->cfg.insn_state;
  
  //e是fallthrough代表顺序执行（t到w）
  if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
    return 0;
  //如果遇见分支跳转指令
  if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
    return 0;


  //判断下一条指令的范围
  if (w < 0 || w >= env->prog->len) {
    verbose_linfo(env, t, "%d: ", t);
    verbose(env, "jump out of range from insn %d to %d\n", t, w);
    return -EINVAL;
  }


  //如果当前的边是branch，分支。
  if (e == BRANCH)
    /* mark branch target for state pruning */
    init_explored_state(env, w);


  //如果下一条指令还没有入栈，没有设置标志
  if (insn_state[w] == 0) {
    //对下一条指令进行压栈操作。
    /* tree-edge */
    insn_state[t] = DISCOVERED | e;  //补充标记当前结点状态
    insn_state[w] = DISCOVERED;    //标记下一条结点状态为discovered
    
    //保证栈大小合法
    if (env->cfg.cur_stack >= env->prog->len)
      return -E2BIG;
    
    //下一条指令进入insn_stack栈中，栈指针后移。
    insn_stack[env->cfg.cur_stack++] = w;
    //返回1，压栈成功
    return 1;
  } 
  //如果下一条指令已经处于discovered状态
  else if ((insn_state[w] & 0xF0) == DISCOVERED) {
    //如果设置了允许loop，且允许ptr leak，返回0
    if (loop_ok && env->allow_ptr_leaks)
      return 0;
    //否则，检测到back-edge，提示存在loop
    verbose_linfo(env, t, "%d: ", t);
    verbose_linfo(env, w, "%d: ", w);
    verbose(env, "back-edge from insn %d to %d\n", t, w);
    return -EINVAL;
  } 
  //如果下一条指令结点已经是explored状态，说明是cross或者forward，正常标记当前结点
  else if (insn_state[w] == EXPLORED) {
    /* forward- or cross-edge */
    insn_state[t] = DISCOVERED | e;
  } 
  else {
    verbose(env, "insn state internal bug\n");
    return -EFAULT;
  }
  return 0;
}

#define MAX_CALL_FRAMES 8
struct bpf_verifier_state {
  struct bpf_func_state *frame[MAX_CALL_FRAMES];  //保存调用栈
  struct bpf_verifier_state *parent;
  /*
   * 'branches' field is the number of branches left to explore:
   * 0 - all possible paths from this state reached bpf_exit or
   * were safely pruned
   * 1 - at least one path is being explored.
   * This state hasn't reached bpf_exit
   * 2 - at least two paths are being explored.
   * This state is an immediate parent of two children.
   * One is fallthrough branch with branches==1 and another
   * state is pushed into stack (to be explored later) also with
   * branches==1. The parent of this state has branches==1.
   * The verifier state tree connected via 'parent' pointer looks like:
   * 1
   * 1
   * 2 -> 1 (first 'if' pushed into stack)
   * 1
   * 2 -> 1 (second 'if' pushed into stack)
   * 1
   * 1
   * 1 bpf_exit.
   *
   * Once do_check() reaches bpf_exit, it calls update_branch_counts()
   * and the verifier state tree will look:
   * 1
   * 1
   * 2 -> 1 (first 'if' pushed into stack)
   * 1
   * 1 -> 1 (second 'if' pushed into stack)
   * 0
   * 0
   * 0 bpf_exit.
   * After pop_stack() the do_check() will resume at second 'if'.
   *
   * If is_state_visited() sees a state with branches > 0 it means
   * there is a loop. If such state is exactly equal to the current state
   * it's an infinite loop. Note states_equal() checks for states
   * equvalency, so two states being 'states_equal' does not mean
   * infinite loop. The exact comparison is provided by
   * states_maybe_looping() function. It's a stronger pre-check and
   * much faster than states_equal().
   *
   * This algorithm may not find all possible infinite loops or
   * loop iteration count may be too high.
   * In such cases BPF_COMPLEXITY_LIMIT_INSNS limit kicks in.
   */
  u32 branches;
  u32 insn_idx;
  u32 curframe;
  u32 active_spin_lock;
  bool speculative;


  /* first and last insn idx of this verifier state */
  u32 first_insn_idx;
  u32 last_insn_idx;
  /* jmp history recorded from first to last.
   * backtracking is using it to go from last to first.
   * For most states jmp_history_cnt is [0-3].
   * For loops can go up to ~40.
   */
  struct bpf_idx_pair *jmp_history;
  u32 jmp_history_cnt;
};

struct bpf_reg_state {
  /* Ordering of fields matters.  See states_equal() */
  enum bpf_reg_type type;
  union {
    /* valid when type == PTR_TO_PACKET */
    u16 range;


    /* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE |
     *   PTR_TO_MAP_VALUE_OR_NULL
     */
    struct bpf_map *map_ptr;


    u32 btf_id; /* for PTR_TO_BTF_ID */


    /* Max size from any of the above. */
    unsigned long raw;
  };
  /* Fixed part of pointer offset, pointer types only */
  s32 off;
  /* For PTR_TO_PACKET, used to find other pointers with the same variable
   * offset, so they can share range knowledge.
   * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
   * came from, when one is tested for != NULL.
   * For PTR_TO_SOCKET this is used to share which pointers retain the
   * same reference to the socket, to determine proper reference freeing.
   */
  u32 id;
  /* PTR_TO_SOCKET and PTR_TO_TCP_SOCK could be a ptr returned
   * from a pointer-cast helper, bpf_sk_fullsock() and
   * bpf_tcp_sock().
   *
   * Consider the following where "sk" is a reference counted
   * pointer returned from "sk = bpf_sk_lookup_tcp();":
   *
   * 1: sk = bpf_sk_lookup_tcp();
   * 2: if (!sk) { return 0; }
   * 3: fullsock = bpf_sk_fullsock(sk);
   * 4: if (!fullsock) { bpf_sk_release(sk); return 0; }
   * 5: tp = bpf_tcp_sock(fullsock);
   * 6: if (!tp) { bpf_sk_release(sk); return 0; }
   * 7: bpf_sk_release(sk);
   * 8: snd_cwnd = tp->snd_cwnd;  // verifier will complain
   *
   * After bpf_sk_release(sk) at line 7, both "fullsock" ptr and
   * "tp" ptr should be invalidated also.  In order to do that,
   * the reg holding "fullsock" and "sk" need to remember
   * the original refcounted ptr id (i.e. sk_reg->id) in ref_obj_id
   * such that the verifier can reset all regs which have
   * ref_obj_id matching the sk_reg->id.
   *
   * sk_reg->ref_obj_id is set to sk_reg->id at line 1.
   * sk_reg->id will stay as NULL-marking purpose only.
   * After NULL-marking is done, sk_reg->id can be reset to 0.
   *
   * After "fullsock = bpf_sk_fullsock(sk);" at line 3,
   * fullsock_reg->ref_obj_id is set to sk_reg->ref_obj_id.
   *
   * After "tp = bpf_tcp_sock(fullsock);" at line 5,
   * tp_reg->ref_obj_id is set to fullsock_reg->ref_obj_id
   * which is the same as sk_reg->ref_obj_id.
   *
   * From the verifier perspective, if sk, fullsock and tp
   * are not NULL, they are the same ptr with different
   * reg->type.  In particular, bpf_sk_release(tp) is also
   * allowed and has the same effect as bpf_sk_release(sk).
   */
  u32 ref_obj_id;
  /* For scalar types (SCALAR_VALUE), this represents our knowledge of
   * the actual value.
   * For pointer types, this represents the variable part of the offset
   * from the pointed-to object, and is shared with all bpf_reg_states
   * with the same id as us.
   */
  struct tnum var_off;
  /* Used to determine if any memory access using this register will
   * result in a bad access.
   * These refer to the same value as var_off, not necessarily the actual
   * contents of the register.
   */
  s64 smin_value; /* minimum possible (s64)value */
  s64 smax_value; /* maximum possible (s64)value */
  u64 umin_value; /* minimum possible (u64)value */
  u64 umax_value; /* maximum possible (u64)value */
  /* parentage chain for liveness checking */
  struct bpf_reg_state *parent;
  /* Inside the callee two registers can be both PTR_TO_STACK like
   * R1=fp-8 and R2=fp-8, but one of them points to this function stack
   * while another to the caller's stack. To differentiate them 'frameno'
   * is used which is an index in bpf_verifier_state->frame[] array
   * pointing to bpf_func_state.
   */
  u32 frameno;
  /* Tracks subreg definition. The stored value is the insn_idx of the
   * writing insn. This is safe because subreg_def is used before any insn
   * patching which only happens after main verification finished.
   */
  s32 subreg_def;
  enum bpf_reg_liveness live;
  /* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
  bool precise;
};

/* types of values stored in eBPF registers */
/* Pointer types represent:
 * pointer
 * pointer + imm
 * pointer + (u16) var
 * pointer + (u16) var + imm
 * if (range > 0) then [ptr, ptr + range - off) is safe to access
 * if (id > 0) means that some 'var' was added
 * if (off > 0) means that 'imm' was added
 */
enum bpf_reg_type {
  NOT_INIT = 0,     /* nothing was written into register */
  SCALAR_VALUE,     /* reg doesn't contain a valid pointer */
  PTR_TO_CTX,     /* reg points to bpf_context */
  CONST_PTR_TO_MAP,   /* reg points to struct bpf_map */
  PTR_TO_MAP_VALUE,   /* reg points to map element value */
  PTR_TO_MAP_VALUE_OR_NULL,/* points to map elem value or NULL */
  PTR_TO_STACK,     /* reg == frame_pointer + offset */
  PTR_TO_PACKET_META,   /* skb->data - meta_len */
  PTR_TO_PACKET,     /* reg points to skb->data */
  PTR_TO_PACKET_END,   /* skb->data + headlen */
  PTR_TO_FLOW_KEYS,   /* reg points to bpf_flow_keys */
  PTR_TO_SOCKET,     /* reg points to struct bpf_sock */
  PTR_TO_SOCKET_OR_NULL,   /* reg points to struct bpf_sock or NULL */
  PTR_TO_SOCK_COMMON,   /* reg points to sock_common */
  PTR_TO_SOCK_COMMON_OR_NULL, /* reg points to sock_common or NULL */
  PTR_TO_TCP_SOCK,   /* reg points to struct tcp_sock */
  PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
  PTR_TO_TP_BUFFER,   /* reg points to a writable raw tp's buffer */
  PTR_TO_XDP_SOCK,   /* reg points to struct xdp_sock */
  PTR_TO_BTF_ID,     /* reg points to kernel struct */
};

struct tnum {
  u64 value;
  u64 mask;
};


#define TNUM(_v, _m)  (struct tnum){.value = _v, .mask = _m}


/* A completely unknown value */
const struct tnum tnum_unknown = { .value = 0, .mask = -1 };

enum bpf_stack_slot_type {
  STACK_INVALID,    /* nothing was stored in this stack slot */
  STACK_SPILL,      /* register spilled into stack */
  STACK_MISC,    /* BPF program wrote some data into this slot */
  STACK_ZERO,    /* BPF program wrote constant zero */
};

  state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL);
  state->curframe = 0;          //当前在调用栈的最上层
  state->speculative = false;
  state->branches = 1;          //当前节点branches = 1
  state->frame[0] = kzalloc(sizeof(struct bpf_func_state), GFP_KERNEL);  //记录调用栈


  env->cur_state = state;        //记录当前初始的state节点

init_func_state(env, state->frame[0],BPF_MAIN_FUNC /* callsite */, 0 /* frameno */, subprog);

static void init_reg_state(struct bpf_verifier_env *env,
         struct bpf_func_state *state)
{
  struct bpf_reg_state *regs = state->regs;
  int i;
  //挨个扫描当前state中的寄存器
  for (i = 0; i < MAX_BPF_REG; i++) {
    //将一个寄存器标识为unknown
    mark_reg_not_init(env, regs, i);
    regs[i].live = REG_LIVE_NONE;  //生存期？
    regs[i].parent = NULL;
    regs[i].subreg_def = DEF_NOT_SUBREG;
  }


  /* frame pointer */
  regs[BPF_REG_FP].type = PTR_TO_STACK;        //设置栈帧寄存器r10,指向BPF栈数据
  mark_reg_known_zero(env, regs, BPF_REG_FP); //将reg的信息都设置为0
  regs[BPF_REG_FP].frameno = state->frameno;  //当前r10的栈帧号等于初始化的state栈帧号。
}

/* check whether memory at (regno + off) is accessible for t = (read | write)
 * if t==write, value_regno is a register which value is stored into memory
 * if t==read, value_regno is a register which will receive the value from memory
 * if t==write && value_regno==-1, some unknown value is stored into memory
 * if t==read && value_regno==-1, don't care what we read from memory
 */
static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno,
          int off, int bpf_size, enum bpf_access_type t,
          int value_regno, bool strict_alignment_once)
{
  struct bpf_reg_state *regs = cur_regs(env);
  struct bpf_reg_state *reg = regs + regno;
  struct bpf_func_state *state;
  int size, err = 0;


  size = bpf_size_to_bytes(bpf_size);
  if (size < 0)
    return size;


  /* alignment checks will add in reg->off themselves */
  //检查指针对齐
  err = check_ptr_alignment(env, reg, off, size, strict_alignment_once);
  if (err)
    return err;


  /* for access checks, reg->off is just part of off */


  off += reg->off;


  //如果reg指向的是map中的值
  if (reg->type == PTR_TO_MAP_VALUE) {
    
   ......
  }
  //如果reg指向bpf_context
  else if (reg->type == PTR_TO_CTX) {
    ......
  } 
  //如果reg指向stack
  else if (reg->type == PTR_TO_STACK) {
    off += reg->var_off.value;        //
    err = check_stack_access(env, reg, off, size);
    if (err)
      return err;


    state = func(env, reg);
    err = update_stack_depth(env, state, off);
    if (err)
      return err;


    if (t == BPF_WRITE)
      err = check_stack_write(env, state, off, size,
            value_regno, insn_idx);
    else
      err = check_stack_read(env, state, off, size,
                 value_regno);
  }
  ......

static int check_stack_access(struct bpf_verifier_env *env,
            const struct bpf_reg_state *reg,
            int off, int size)
{
  /* Stack accesses must be at a fixed offset, so that we
   * can determine what type of data were returned. See
   * check_stack_read().
   */
  //tnum_is_const检测我们要访问的offset必须是一个常量
  if (!tnum_is_const(reg->var_off)) {
    char tn_buf[48];


    tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
    verbose(env, "variable stack access var_off=%s off=%d size=%d\n",
      tn_buf, off, size);
    return -EACCES;
  }
  //我们访问的位置必须在合法范围内，最大offset不超过-512字节
  if (off >= 0 || off < -MAX_BPF_STACK) {
    verbose(env, "invalid stack off=%d size=%d\n", off, size);
    return -EACCES;
  }


  return 0;
}

/* check_stack_read/write functions track spill/fill of registers,
 * stack boundary and alignment are checked in check_mem_access()
 */
static int check_stack_write(struct bpf_verifier_env *env,
           struct bpf_func_state *state, /* func where register points to */
           int off, int size, int value_regno, int insn_idx)
{
  struct bpf_func_state *cur; /* state of the current function */
  int i, slot = -off - 1, spi = slot / BPF_REG_SIZE, err;
  u32 dst_reg = env->prog->insnsi[insn_idx].dst_reg;
  struct bpf_reg_state *reg = NULL;


  //由于栈扩展导致的需要重新申请空间放state跟踪stack状态
  err = realloc_func_state(state, round_up(slot + 1, BPF_REG_SIZE),
         state->acquired_refs, true);
  if (err)
    return err;
  /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
   * so it's aligned access and [off, off + size) are within stack limits
   */
  //不允许非特权用户由于部分写破坏栈上合法指针
  if (!env->allow_ptr_leaks &&
      state->stack[spi].slot_type[0] == STACK_SPILL &&
      size != BPF_REG_SIZE) {
    verbose(env, "attempt to corrupt spilled pointer on stack\n");
    return -EACCES;
  }


  cur = env->cur_state->frame[env->cur_state->curframe];
  if (value_regno >= 0)
    reg = &cur->regs[value_regno];


  //优化回溯
  if (reg && size == BPF_REG_SIZE && register_is_const(reg) &&
      !register_is_null(reg) && env->allow_ptr_leaks) {
    if (dst_reg != BPF_REG_FP) {
      /* The backtracking logic can only recognize explicit
       * stack slot address like [fp - 8]. Other spill of
       * scalar via different register has to be conervative.
       * Backtrack from here and mark all registers as precise
       * that contributed into 'reg' being a constant.
       */
      err = mark_chain_precision(env, value_regno);
      if (err)
        return err;
    }
    save_register_state(state, spi, reg);
  } 
  else if (reg && is_spillable_regtype(reg->type)) {
    /* register containing pointer is being spilled into stack */
    //源寄存器是STACK_SPILL，部分写不允许
    if (size != BPF_REG_SIZE) {
      verbose_linfo(env, insn_idx, "; ");
      verbose(env, "invalid size of register spill\n");
      return -EACCES;
    }


    if (state != cur && reg->type == PTR_TO_STACK) {
      verbose(env, "cannot spill pointers to stack into stack frame of the caller\n");
      return -EINVAL;
    }


    //引入sanitize，防止stack的重用，防范侧信道攻击？
    if (!env->allow_ptr_leaks) 
    {
      bool sanitize = false;


      if (state->stack[spi].slot_type[0] == STACK_SPILL &&
          register_is_const(&state->stack[spi].spilled_ptr))
        sanitize = true;
      for (i = 0; i < BPF_REG_SIZE; i++)
        if (state->stack[spi].slot_type[i] == STACK_MISC) {
          sanitize = true;
          break;
        }
      if (sanitize) {
        int *poff = &env->insn_aux_data[insn_idx].sanitize_stack_off;
        int soff = (-spi - 1) * BPF_REG_SIZE;


        /* detected reuse of integer stack slot with a pointer
         * which means either llvm is reusing stack slot or
         * an attacker is trying to exploit CVE-2018-3639
         * (speculative store bypass)
         * Have to sanitize that slot with preemptive
         * store of zero.
         */
        if (*poff && *poff != soff) {
          /* disallow programs where single insn stores
           * into two different stack slots, since verifier
           * cannot sanitize them
           */
          verbose(env,
            "insn %d cannot access two stack slots fp%d and fp%d",
            insn_idx, *poff, soff);
          return -EINVAL;
        }
        *poff = soff;
      }
    }
    save_register_state(state, spi, reg);
  } else {
    //reg是非有效指针
    u8 type = STACK_MISC;


    /* regular write of data into stack destroys any spilled ptr */
    state->stack[spi].spilled_ptr.type = NOT_INIT;
    
    //标记栈为STACK_SPILL， 代表包含非指针、非0变量等
    /* Mark slots as STACK_MISC if they belonged to spilled ptr. */
    if (state->stack[spi].slot_type[0] == STACK_SPILL)
      for (i = 0; i < BPF_REG_SIZE; i++)
        state->stack[spi].slot_type[i] = STACK_MISC;


    /* only mark the slot as written if all 8 bytes were written
     * otherwise read propagation may incorrectly stop too soon
     * when stack slots are partially written.
     * This heuristic means that read propagation will be
     * conservative, since it will add reg_live_read marks
     * to stack slots all the way to first state when programs
     * writes+reads less than 8 bytes
     */
    if (size == BPF_REG_SIZE)
      state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;


    /* when we zero initialize stack slots mark them as such */
    //reg为0
    if (reg && register_is_null(reg)) {
      /* backtracking doesn't work for STACK_ZERO yet. */
      err = mark_chain_precision(env, value_regno);
      if (err)
        return err;
      type = STACK_ZERO;  //设置为STACK_ZERO
    }


    /* Mark slots affected by this stack write. */
    //reg为0，标记所写栈的slot类型为设置为STACK_ZERO，否则仍然是一开始的MISC
    for (i = 0; i < size; i++)
      state->stack[spi].slot_type[(slot - i) % BPF_REG_SIZE] =
        type;
  }
  return 0;
}

/* starting from main bpf function walk all instructions of the function
 * and recursively walk all callees that given function can call.
 * Ignore jump and exit insns.
 * Since recursion is prevented by check_cfg() this algorithm
 * only needs a local stack of MAX_CALL_FRAMES to remember callsites
 */
static int check_max_stack_depth(struct bpf_verifier_env *env)
{
  int depth = 0, frame = 0, idx = 0, i = 0, subprog_end;
  struct bpf_subprog_info *subprog = env->subprog_info;
  struct bpf_insn *insn = env->prog->insnsi;
  int ret_insn[MAX_CALL_FRAMES];  //函数返回地址
  int ret_prog[MAX_CALL_FRAMES];  //函数返回地址的index


process_func:
  /* round up to 32-bytes, since this is granularity
   * of interpreter stack size
   */
  depth += round_up(max_t(u32, subprog[idx].stack_depth, 1), 32);
  //栈不能不超过512
  if (depth > MAX_BPF_STACK) {
    verbose(env, "combined stack size of %d calls is %d. Too large\n",
      frame + 1, depth);
    return -EACCES;
  }
//subprog[0]为main函数，取下一个函数
continue_func:
  subprog_end = subprog[idx + 1].start;
  for (; i < subprog_end; i++) {
    if (insn[i].code != (BPF_JMP | BPF_CALL))
      continue;
    if (insn[i].src_reg != BPF_PSEUDO_CALL)
      continue;
    /* remember insn and function to return to */
    //bpf fun之间的调用
    ret_insn[frame] = i + 1;//记录返回地址
    ret_prog[frame] = idx;  //记录idx


    /* find the callee */
    i = i + insn[i].imm + 1;//找到callee的地址
    idx = find_subprog(env, i);//查找callee的idx
    if (idx < 0) {
      WARN_ONCE(1, "verifier bug. No program starts at insn %d\n",
          i);
      return -EFAULT;
    }
    frame++;//深度++
    //调用深度限制小于8
    if (frame >= MAX_CALL_FRAMES) {
      verbose(env, "the call stack of %d frames is too deep !\n",
        frame);
      return -E2BIG;
    }
    goto process_func;
  }
  /* end of for() loop means the last insn of the 'subprog'
   * was reached. Doesn't matter whether it was JA or EXIT
   */
  //深度为0说明之行结束，返回
  if (frame == 0)
    return 0;
  depth -= round_up(max_t(u32, subprog[idx].stack_depth, 1), 32);
  frame--;
  i = ret_insn[frame];  //弹出返回地址
  idx = ret_prog[frame];  //弹出上层函数idx
  goto continue_func;    //返回
}

{
    if (insn->code == (BPF_ALU64 | BPF_MOD | BPF_X) ||
        insn->code == (BPF_ALU64 | BPF_DIV | BPF_X) ||
        insn->code == (BPF_ALU | BPF_MOD | BPF_X) ||
        insn->code == (BPF_ALU | BPF_DIV | BPF_X)) {
      bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
      //将div指令扩展为4个指令。
      //如果源操作数为0，清零dst
      //跳转到下一条指令执行
      //类似一个security hook？
      struct bpf_insn mask_and_div[] = {
        BPF_MOV32_REG(insn->src_reg, insn->src_reg),
        /* Rx div 0 -> 0 */
        BPF_JMP_IMM(BPF_JNE, insn->src_reg, 0, 2),
        BPF_ALU32_REG(BPF_XOR, insn->dst_reg, insn->dst_reg),
        BPF_JMP_IMM(BPF_JA, 0, 0, 1),
        *insn,
      };
      
      //将mod指令扩展为两个指令
      //如果源操作数为0，目的操作数不变，跳到原指令的下一条执行
      struct bpf_insn mask_and_mod[] = {
        BPF_MOV32_REG(insn->src_reg, insn->src_reg),
        /* Rx mod 0 -> Rx */
        BPF_JMP_IMM(BPF_JEQ, insn->src_reg, 0, 1),
        *insn,
      };
      
      //用patch指令替换源指令。
      struct bpf_insn *patchlet;


      if (insn->code == (BPF_ALU64 | BPF_DIV | BPF_X) ||
          insn->code == (BPF_ALU | BPF_DIV | BPF_X)) {
        patchlet = mask_and_div + (is64 ? 1 : 0);
        cnt = ARRAY_SIZE(mask_and_div) - (is64 ? 1 : 0);
      } else {
        patchlet = mask_and_mod + (is64 ? 1 : 0);
        cnt = ARRAY_SIZE(mask_and_mod) - (is64 ? 1 : 0);
      }


      new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt);
      if (!new_prog)
        return -ENOMEM;


      delta    += cnt - 1;
      env->prog = prog = new_prog;
      insn      = new_prog->insnsi + i + delta;
      continue;
    }
  ......
    //修正跳转距离，imm为调用函数到当前指令的距离。
    //通过BPF_CAST_CALL获取该函数的地址直接减去内核的__bpf_call_base，做的实际只是部分修正。
    switch (insn->imm) {
      case BPF_FUNC_map_lookup_elem:
        insn->imm = BPF_CAST_CALL(ops->map_lookup_elem) -
              __bpf_call_base;
        continue;
      case BPF_FUNC_map_update_elem:
        insn->imm = BPF_CAST_CALL(ops->map_update_elem) -
              __bpf_call_base;
        continue;
      case BPF_FUNC_map_delete_elem:
        insn->imm = BPF_CAST_CALL(ops->map_delete_elem) -
              __bpf_call_base;
        continue;
      case BPF_FUNC_map_push_elem:
        insn->imm = BPF_CAST_CALL(ops->map_push_elem) -
              __bpf_call_base;
        continue;
      case BPF_FUNC_map_pop_elem:
        insn->imm = BPF_CAST_CALL(ops->map_pop_elem) -
              __bpf_call_base;
        continue;
      case BPF_FUNC_map_peek_elem:
        insn->imm = BPF_CAST_CALL(ops->map_peek_elem) -
              __bpf_call_base;
        continue;
      }


      goto patch_call_imm;
    }