eBPF源码阅读笔记

字数统计: 12.9k字   |   阅读时长≈ 69分

最近想对kernel的一个模块进行深入研究，希望能够做到对代码流程和常见的漏洞利用方法都有了解

bpf_create_map

用户程序调用 syscall(__NR_bpf, BPF_MAP_CREATE, &attr, sizeof(attr))申请创建一个 map，在 attr结构体中指定 map的类型、大小、最大容量等属性。内核会创建一个 map数据结构，最终返回 map的文件描述符。这个文件是用户态和内核态共享的，因此后续内核态和用户态可以对这块共享内存进行读写

1
2
3
4
5
6
7
8
9
10
11
12
13
int bpf_create_map(enum bpf_map_type map_type, int key_size,
		   int value_size, int max_entries, __u32 map_flags)
{
	struct bpf_create_map_attr map_attr = {};

	map_attr.map_type = map_type;		//类型
	map_attr.map_flags = map_flags;	//属性
	map_attr.key_size = key_size;		//key数量
	map_attr.value_size = value_size;
	map_attr.max_entries = max_entries;

	return bpf_create_map_xattr(&map_attr);
}

随后会调用 bpf_create_map_xattr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int bpf_create_map_xattr(const struct bpf_create_map_attr *create_attr)
{
	union bpf_attr attr;

	memset(&attr, '\0', sizeof(attr));

	attr.map_type = create_attr->map_type;
	attr.key_size = create_attr->key_size;
	attr.value_size = create_attr->value_size;
	attr.max_entries = create_attr->max_entries;
	attr.map_flags = create_attr->map_flags;
	if (create_attr->name)
		memcpy(attr.map_name, create_attr->name,
		       min(strlen(create_attr->name), BPF_OBJ_NAME_LEN - 1));
	attr.numa_node = create_attr->numa_node;
	attr.btf_fd = create_attr->btf_fd;
	attr.btf_key_type_id = create_attr->btf_key_type_id;
	attr.btf_value_type_id = create_attr->btf_value_type_id;
	attr.map_ifindex = create_attr->map_ifindex;
	attr.inner_map_fd = create_attr->inner_map_fd;

	return sys_bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
}

前面进行了属性attr的赋值，最后执行了sys_bpf

1
2
3
4
5
static inline int sys_bpf(enum bpf_cmd cmd, union bpf_attr *attr,
			  unsigned int size)
{
	return syscall(__NR_bpf, cmd, attr, size);
}

最终会调用syscall，其中cmd为 BPF_MAP_CREATE，也就是会去执行创建MAP页面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
union bpf_attr {
	struct { /* anonymous struct used by BPF_MAP_CREATE command */
		__u32	map_type;	/* one of enum bpf_map_type */
		__u32	key_size;	/* size of key in bytes */
		__u32	value_size;	/* size of value in bytes */
		__u32	max_entries;	/* max number of entries in a map */
		__u32	map_flags;	/* BPF_MAP_CREATE related
					 * flags defined above.
					 */
		__u32	inner_map_fd;	/* fd pointing to the inner map */
		__u32	numa_node;	/* numa node (effective only if
					 * BPF_F_NUMA_NODE is set).
					 */
		char	map_name[BPF_OBJ_NAME_LEN];
		__u32	map_ifindex;	/* ifindex of netdev to create on */
		__u32	btf_fd;		/* fd pointing to a BTF type data */
		__u32	btf_key_type_id;	/* BTF type_id of the key */
		__u32	btf_value_type_id;	/* BTF type_id of the value */
	};

	struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
		__u32		map_fd;
		__aligned_u64	key;
		union {
			__aligned_u64 value;
			__aligned_u64 next_key;
		};
		__u64		flags;
	};

	struct { /* anonymous struct used by BPF_PROG_LOAD command */
		__u32		prog_type;	/* one of enum bpf_prog_type */
		__u32		insn_cnt;
		__aligned_u64	insns;
		__aligned_u64	license;
		__u32		log_level;	/* verbosity level of verifier */
		__u32		log_size;	/* size of user buffer */
		__aligned_u64	log_buf;	/* user supplied buffer */
		__u32		kern_version;	/* not used */
		__u32		prog_flags;
		char		prog_name[BPF_OBJ_NAME_LEN];
		__u32		prog_ifindex;	/* ifindex of netdev to prep for */
		/* For some prog types expected attach type must be known at
		 * load time to verify attach type specific parts of prog
		 * (context accesses, allowed helpers, etc).
		 */
		__u32		expected_attach_type;
		__u32		prog_btf_fd;	/* fd pointing to BTF type data */
		__u32		func_info_rec_size;	/* userspace bpf_func_info size */
		__aligned_u64	func_info;	/* func info */
		__u32		func_info_cnt;	/* number of bpf_func_info records */
		__u32		line_info_rec_size;	/* userspace bpf_line_info size */
		__aligned_u64	line_info;	/* line info */
		__u32		line_info_cnt;	/* number of bpf_line_info records */
		__u32		attach_btf_id;	/* in-kernel BTF type id to attach to */
		__u32		attach_prog_fd; /* 0 to attach to vmlinux */
	};

	struct { /* anonymous struct used by BPF_OBJ_* commands */
		__aligned_u64	pathname;
		__u32		bpf_fd;
		__u32		file_flags;
	};

	struct { /* anonymous struct used by BPF_PROG_ATTACH/DETACH commands */
		__u32		target_fd;	/* container object to attach to */
		__u32		attach_bpf_fd;	/* eBPF program to attach */
		__u32		attach_type;
		__u32		attach_flags;
	};

	struct { /* anonymous struct used by BPF_PROG_TEST_RUN command */
		__u32		prog_fd;
		__u32		retval;
		__u32		data_size_in;	/* input: len of data_in */
		__u32		data_size_out;	/* input/output: len of data_out
						 *   returns ENOSPC if data_out
						 *   is too small.
						 */
		__aligned_u64	data_in;
		__aligned_u64	data_out;
		__u32		repeat;
		__u32		duration;
		__u32		ctx_size_in;	/* input: len of ctx_in */
		__u32		ctx_size_out;	/* input/output: len of ctx_out
						 *   returns ENOSPC if ctx_out
						 *   is too small.
						 */
		__aligned_u64	ctx_in;
		__aligned_u64	ctx_out;
	} test;

	struct { /* anonymous struct used by BPF_*_GET_*_ID */
		union {
			__u32		start_id;
			__u32		prog_id;
			__u32		map_id;
			__u32		btf_id;
		};
		__u32		next_id;
		__u32		open_flags;
	};

	struct { /* anonymous struct used by BPF_OBJ_GET_INFO_BY_FD */
		__u32		bpf_fd;
		__u32		info_len;
		__aligned_u64	info;
	} info;

	struct { /* anonymous struct used by BPF_PROG_QUERY command */
		__u32		target_fd;	/* container object to query */
		__u32		attach_type;
		__u32		query_flags;
		__u32		attach_flags;
		__aligned_u64	prog_ids;
		__u32		prog_cnt;
	} query;

	struct {
		__u64 name;
		__u32 prog_fd;
	} raw_tracepoint;

	struct { /* anonymous struct for BPF_BTF_LOAD */
		__aligned_u64	btf;
		__aligned_u64	btf_log_buf;
		__u32		btf_size;
		__u32		btf_log_size;
		__u32		btf_log_level;
	};

	struct {
		__u32		pid;		/* input: pid */
		__u32		fd;		/* input: fd */
		__u32		flags;		/* input: flags */
		__u32		buf_len;	/* input/output: buf len */
		__aligned_u64	buf;		/* input/output:
						 *   tp_name for tracepoint
						 *   symbol for kprobe
						 *   filename for uprobe
						 */
		__u32		prog_id;	/* output: prod_id */
		__u32		fd_type;	/* output: BPF_FD_TYPE_* */
		__u64		probe_offset;	/* output: probe_offset */
		__u64		probe_addr;	/* output: probe_addr */
	} task_fd_query;
} __attribute__((aligned(8)));

//bpf.h
/* BPF syscall commands, see bpf(2) man-page for details. */
enum bpf_cmd {
    BPF_MAP_CREATE,
    BPF_MAP_LOOKUP_ELEM,
    BPF_MAP_UPDATE_ELEM,
    BPF_MAP_DELETE_ELEM,
    BPF_MAP_GET_NEXT_KEY,
    BPF_PROG_LOAD,
    BPF_OBJ_PIN,
    BPF_OBJ_GET,
};

BPF_PROG_LOAD

用户程序调用 syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr))来将我们写的 BPF代码加载进内核，attr结构体中包含了指令数量、指令首地址、日志级别等属性。在加载之前会利用虚拟执行的方式来做安全行校验，这个校验包括对指定语法的检查、指令数量的检查、指令中的指针和立即数的范围及读写权限检查，禁止将内核中的地址暴露给用户空间，禁止对 BPF程序 stack之外的内核地址读写。安全校验通过后，程序被成功加载至内核，后续真正执行时，不再重复做检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
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;

	if (CHECK_ATTR(BPF_PROG_LOAD))	//检查参数
		return -EINVAL;

	if (attr->prog_flags & ~(BPF_F_STRICT_ALIGNMENT |
				 BPF_F_ANY_ALIGNMENT |
				 BPF_F_TEST_STATE_FREQ |
				 BPF_F_TEST_RND_HI32))		//检查属性
		return -EINVAL;

	if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) &&
	    (attr->prog_flags & BPF_F_ANY_ALIGNMENT) &&
	    !capable(CAP_SYS_ADMIN))		//
		return -EPERM;

	/* copy eBPF program license from user space */
	if (strncpy_from_user(license, u64_to_user_ptr(attr->license),
			      sizeof(license) - 1) < 0)		//从用户态拷贝license到内核太
		return -EFAULT;
	license[sizeof(license) - 1] = 0;

	/* eBPF programs must be GPL compatible to use GPL-ed functions */
	is_gpl = license_is_gpl_compatible(license);	//检查证书是否为GPL类型

	if (attr->insn_cnt == 0 ||		//指令数量不为0，且不超过限制4096
	    attr->insn_cnt > (capable(CAP_SYS_ADMIN) ? BPF_COMPLEXITY_LIMIT_INSNS : BPF_MAXINSNS))
		return -E2BIG;
	if (type != BPF_PROG_TYPE_SOCKET_FILTER &&	//检查type
	    type != BPF_PROG_TYPE_CGROUP_SKB &&
	    !capable(CAP_SYS_ADMIN))
		return -EPERM;

	bpf_prog_load_fixup_attach_type(attr);		//
	if (bpf_prog_load_check_attach(type, attr->expected_attach_type,
				       attr->attach_btf_id,
				       attr->attach_prog_fd))
		return -EINVAL;

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

	prog->expected_attach_type = attr->expected_attach_type;	//
	prog->aux->attach_btf_id = attr->attach_btf_id;
	if (attr->attach_prog_fd) {
		struct bpf_prog *tgt_prog;

		tgt_prog = bpf_prog_get(attr->attach_prog_fd);
		if (IS_ERR(tgt_prog)) {
			err = PTR_ERR(tgt_prog);
			goto free_prog_nouncharge;
		}
		prog->aux->linked_prog = tgt_prog;
	}

	prog->aux->offload_requested = !!attr->prog_ifindex;

	err = security_bpf_prog_alloc(prog->aux);
	if (err)
		goto free_prog_nouncharge;

	err = bpf_prog_charge_memlock(prog);
	if (err)
		goto free_prog_sec;

	prog->len = attr->insn_cnt;

	err = -EFAULT;
	if (copy_from_user(prog->insns, u64_to_user_ptr(attr->insns),		//将用户传入的ebpf程序拷贝到prog->insn这个空间中
			   bpf_prog_insn_size(prog)) != 0)
		goto free_prog;

	prog->orig_prog = NULL;	//设置prog参数
	prog->jited = 0;		//

	atomic64_set(&prog->aux->refcnt, 1);
	prog->gpl_compatible = is_gpl ? 1 : 0;

	if (bpf_prog_is_dev_bound(prog->aux)) {
		err = bpf_prog_offload_init(prog, attr);
		if (err)
			goto free_prog;
	}

	/* find program type: socket_filter vs tracing_filter */
	err = find_prog_type(type, prog);		//查找过滤模式，是socket过滤还是系统调用号参数过滤seccomp
	if (err < 0)
		goto free_prog;

	prog->aux->load_time = ktime_get_boottime_ns();
	err = bpf_obj_name_cpy(prog->aux->name, attr->prog_name);
	if (err)
		goto free_prog;

	/* run eBPF verifier */
	err = bpf_check(&prog, attr, uattr);	//在执行ebpf程序之前，对bpf程序进行检查
	if (err < 0)
		goto free_used_maps;

	prog = bpf_prog_select_runtime(prog, &err);	//查好ebpf程序的运行模式，jit还是直接执行
	if (err < 0)
		goto free_used_maps;

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

	/* Upon success of bpf_prog_alloc_id(), the BPF prog is
	 * effectively publicly exposed. However, retrieving via
	 * bpf_prog_get_fd_by_id() will take another reference,
	 * therefore it cannot be gone underneath us.
	 *
	 * Only for the time /after/ successful bpf_prog_new_fd()
	 * and before returning to userspace, we might just hold
	 * one reference and any parallel close on that fd could
	 * rip everything out. Hence, below notifications must
	 * happen before bpf_prog_new_fd().
	 *
	 * Also, any failure handling from this point onwards must
	 * be using bpf_prog_put() given the program is exposed.
	 */
	bpf_prog_kallsyms_add(prog);
	perf_event_bpf_event(prog, PERF_BPF_EVENT_PROG_LOAD, 0);

	err = bpf_prog_new_fd(prog);
	if (err < 0)
		bpf_prog_put(prog);
	return err;

free_used_maps:
	/* In case we have subprogs, we need to wait for a grace
	 * period before we can tear down JIT memory since symbols
	 * are already exposed under kallsyms.
	 */
	__bpf_prog_put_noref(prog, prog->aux->func_cnt);
	return err;
free_prog:
	bpf_prog_uncharge_memlock(prog);
free_prog_sec:
	security_bpf_prog_free(prog->aux);
free_prog_nouncharge:
	bpf_prog_free(prog);
	return err;
}

bpf_prog_load函数主要完成了如下步骤：

  • 检查的ebpf license是否为GPL证书的一种。

  • 检查指令条数是否超过4096。

  • 利用kmalloc新建了一个bpf_prog结构体，并新建了一个用于存放EBPF程序的内存空间。

  • 将用户态的EBPF程序拷贝到刚申请的内存中。

  • 判断是哪种过滤模式，其中socket_filter是数据包过滤，而tracing_filter就是对系统调用号及参数的过滤，也就是我们常见的seccomp。

  • 对用户输入的程序进行检查。如果通过检查就将fp中执行函数赋值为 __bpf_prog_run也就是真实执行函数，并尝试JIT加载，否则用中断的方法加载。

这里的bpf_prog_alloc函数，就是创建并分配bpf_prog结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct bpf_prog *bpf_prog_alloc(unsigned int size, gfp_t gfp_extra_flags)
{
	gfp_t gfp_flags = GFP_KERNEL | __GFP_ZERO | gfp_extra_flags;
	struct bpf_prog *prog;
	int cpu;

	prog = bpf_prog_alloc_no_stats(size, gfp_extra_flags);		//调用kmalloc分配size的空间
	if (!prog)
		return NULL;

	prog->aux->stats = alloc_percpu_gfp(struct bpf_prog_stats, gfp_flags);
	if (!prog->aux->stats) {
		kfree(prog->aux);
		vfree(prog);
		return NULL;
	}

	for_each_possible_cpu(cpu) {
		struct bpf_prog_stats *pstats;

		pstats = per_cpu_ptr(prog->aux->stats, cpu);
		u64_stats_init(&pstats->syncp);
	}
	return prog;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct bpf_prog *bpf_prog_alloc_no_stats(unsigned int size, gfp_t gfp_extra_flags)
{
	gfp_t gfp_flags = GFP_KERNEL | __GFP_ZERO | gfp_extra_flags;
	struct bpf_prog_aux *aux;
	struct bpf_prog *fp;

	size = round_up(size, PAGE_SIZE);
	fp = __vmalloc(size, gfp_flags, PAGE_KERNEL);
	if (fp == NULL)
		return NULL;

	aux = kzalloc(sizeof(*aux), GFP_KERNEL | gfp_extra_flags);	//创建aux空间存储ebpf程序
	if (aux == NULL) {
		vfree(fp);
		return NULL;
	}

	fp->pages = size / PAGE_SIZE;
	fp->aux = aux;
	fp->aux->prog = fp;
	fp->jit_requested = ebpf_jit_enabled();

	INIT_LIST_HEAD_RCU(&fp->aux->ksym_lnode);

	return fp;
}

在bpf_prog结构体中，我们可以看到很多关于ebpf程序运行时的属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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];
	};
};

bpf_check

从上面可以看到真正执行ebpf程序之前会调用bpf_check函数对程序进行检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
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;

	/* no program is valid */
	if (ARRAY_SIZE(bpf_verifier_ops) == 0)
		return -EINVAL;

	/* 'struct bpf_verifier_env' can be global, but since it's not small,
	 * allocate/free it every time bpf_check() is called
	 */
	env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
	if (!env)
		return -ENOMEM;
	log = &env->log;

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

	if (!btf_vmlinux && IS_ENABLED(CONFIG_DEBUG_INFO_BTF)) {
		mutex_lock(&bpf_verifier_lock);
		if (!btf_vmlinux)
			btf_vmlinux = btf_parse_vmlinux();
		mutex_unlock(&bpf_verifier_lock);
	}

	/* grab the mutex to protect few globals used by verifier */
	if (!is_priv)
		mutex_lock(&bpf_verifier_lock);

	if (attr->log_level || attr->log_buf || attr->log_size) {
		/* user requested verbose verifier output
		 * and supplied buffer to store the verification trace
		 */
		log->level = attr->log_level;
		log->ubuf = (char __user *) (unsigned long) attr->log_buf;
		log->len_total = attr->log_size;

		ret = -EINVAL;
		/* log attributes have to be sane */
		if (log->len_total < 128 || log->len_total > UINT_MAX >> 2 ||
		    !log->level || !log->ubuf || log->level & ~BPF_LOG_MASK)
			goto err_unlock;
	}

	if (IS_ERR(btf_vmlinux)) {
		/* Either gcc or pahole or kernel are broken. */
		verbose(env, "in-kernel BTF is malformed\n");
		ret = PTR_ERR(btf_vmlinux);
		goto skip_full_check;
	}

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

	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_cfg(env);
	if (ret < 0)
		goto skip_full_check;

	ret = do_check(env);
	if (env->cur_state) {
		free_verifier_state(env->cur_state, true);
		env->cur_state = NULL;
	}

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

skip_full_check:
	while (!pop_stack(env, NULL, NULL));
	free_states(env);

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

replace_map_fd_with_map_ptr

函数主要目的：

  • 将map_fd，转换为map的地址。
  • 将加载后的map_addr分高低32位在上下两条指令中存储。
  • 简单的校验非加载map指令的操作码合法性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/* look for pseudo eBPF instructions that access map FDs and
 * replace them with actual map pointers
 */
static int replace_map_fd_with_map_ptr(struct bpf_verifier_env *env)
{
	struct bpf_insn *insn = env->prog->insnsi;	//取出env中保存的指令
	int insn_cnt = env->prog->len;		//取出env中保存的指令长度
	int i, j, err;

	err = bpf_prog_calc_tag(env->prog);		//计算ebpf程序hash
	if (err)
		return err;

	for (i = 0; i < insn_cnt; i++, insn++) {		//遍历指令
		//如果是内存加载（BPF_LDX），必须保证带有BPF_MEM，并且立即数为0
		if (BPF_CLASS(insn->code) == BPF_LDX &&
		    (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) {
			verbose(env, "BPF_LDX uses reserved fields\n");
			return -EINVAL;
		}
		//如果是内存存储(BPF_STX）,必须保证带有BPF_MEM或BPF_XADD,并且立即数为0
		if (BPF_CLASS(insn->code) == BPF_STX &&
		    ((BPF_MODE(insn->code) != BPF_MEM &&
		      BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) {
			verbose(env, "BPF_STX uses reserved fields\n");
			return -EINVAL;
		}

		//BPF_LD_IMM64_RAW ，标志为：.code = BPF_LD | BPF_DW | BPF_IMM 。即 BPF_LD_MAP_FD ，此时的code是加载map的操作
		if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {	
			struct bpf_insn_aux_data *aux;
			struct bpf_map *map;
			struct fd f;
			u64 addr;
			
			//如果是最后一条指令，或下一条指令是空指令，则跳过
			if (i == insn_cnt - 1 || insn[1].code != 0 ||
			    insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
			    insn[1].off != 0) {
				verbose(env, "invalid bpf_ld_imm64 insn\n");
				return -EINVAL;
			}
			//如果src_reg=0，即map_fd=0，则跳过进入下一条指令
			if (insn[0].src_reg == 0)
				/* valid generic load 64-bit imm */
				goto next_insn;

			/* In final convert_pseudo_ld_imm64() step, this is
			 * converted into regular 64-bit imm load insn.
			 */
			//如果当前指令的src_reg，不是BPF_PSEUDO_MAP_FD，不是BPF_PSEUDO_MAP_VALUE；或者是BPF_PSEUDO_MAP_FD但下一条指令imm不为空。abort
			if ((insn[0].src_reg != BPF_PSEUDO_MAP_FD &&
			     insn[0].src_reg != BPF_PSEUDO_MAP_VALUE) ||
			    (insn[0].src_reg == BPF_PSEUDO_MAP_FD &&
			     insn[1].imm != 0)) {
				verbose(env,
					"unrecognized bpf_ld_imm64 insn\n");
				return -EINVAL;
			}

			f = fdget(insn[0].imm);	//返回map_fd
			map = __bpf_map_get(f);	//将fd转换为map_fd结构
			if (IS_ERR(map)) {		
				verbose(env, "fd %d is not pointing to valid bpf_map\n",
					insn[0].imm);
				return PTR_ERR(map);
			}
			//检查ebpf程序与环境的相容性
			err = check_map_prog_compatibility(env, map, env->prog);
			if (err) {
				fdput(f);
				return err;
			}
			//
			aux = &env->insn_aux_data[i];
			//设置了BPF_PSEUDO_MAP_FD
			if (insn->src_reg == BPF_PSEUDO_MAP_FD) {
				addr = (unsigned long)map;	//直接将map地址赋值给addr
			} 
			//否则，通过下一条指令的imm作为off，配合虚表中的 map_direct_value_addr
			//主要实现在：array_map_direct_value_addr ，被用于bpf_array中获取到第一个value。value的地址赋值给addr。然后addr+=off
			else { 
				u32 off = insn[1].imm;		//取立即数
				//检查偏移
				if (off >= BPF_MAX_VAR_OFF) {
					verbose(env, "direct value offset of %u is not allowed\n", off);
					fdput(f);
					return -EINVAL;
				}

				if (!map->ops->map_direct_value_addr) {
					verbose(env, "no direct value access support for this map type\n");
					fdput(f);
					return -EINVAL;
				}

				err = map->ops->map_direct_value_addr(map, &addr, off);
				if (err) {
					verbose(env, "invalid access to map value pointer, value_size=%u off=%u\n",
						map->value_size, off);
					fdput(f);
					return err;
				}
				//获取map里的偏移
				aux->map_off = off;
				addr += off;		//add为off
			}

			insn[0].imm = (u32)addr;		//将map_fd转为addr低32位,赋值给第一条指令
			insn[1].imm = addr >> 32;		//将addr的高32位赋值给第二条指令

			/* check whether we recorded this map already */
			//检查当前map是否处于使用状态
			for (j = 0; j < env->used_map_cnt; j++) {
				if (env->used_maps[j] == map) {
					aux->map_index = j;
					fdput(f);
					goto next_insn;
				}
			}

			if (env->used_map_cnt >= MAX_USED_MAPS) {
				fdput(f);
				return -E2BIG;
			}

			/* hold the map. If the program is rejected by verifier,
			 * the map will be released by release_maps() or it
			 * will be used by the valid program until it's unloaded
			 * and all maps are released in free_used_maps()
			 */
			bpf_map_inc(map);
			//将当前map标记为使用中
			aux->map_index = env->used_map_cnt;
			env->used_maps[env->used_map_cnt++] = map;

			if (bpf_map_is_cgroup_storage(map) &&
			    bpf_cgroup_storage_assign(env->prog->aux, map)) {
				verbose(env, "only one cgroup storage of each type is allowed\n");
				fdput(f);
				return -EBUSY;
			}

			fdput(f);
next_insn:
			insn++;
			i++;
			continue;
		}

		/* Basic sanity check before we invest more work here. */
		//如果当前指令不是加载map的指令。调用 bpf_opcode_in_insntable 进行基本的指令unkown判断
		if (!bpf_opcode_in_insntable(insn->code)) {
			verbose(env, "unknown opcode %02x\n", insn->code);
			return -EINVAL;
		}
	}

	/* now all pseudo BPF_LD_IMM64 instructions load valid
	 * 'struct bpf_map *' into a register instead of user map_fd.
	 * These pointers will be used later by verifier to validate map access.
	 */
	return 0;
}

check_subprogs

函数主要目的：

  • 生成 env->subprog_info[] 数组，存储要跳转的函数的id。
  • 检测JMP指令的跳转范围是否在subprog中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static int check_subprogs(struct bpf_verifier_env *env)
{
	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
	struct bpf_subprog_info *subprog = env->subprog_info;
	struct bpf_insn *insn = env->prog->insnsi;
	int insn_cnt = env->prog->len;

	/* Add entry function. */
	//调用 add_subprog(env,0) ，首先在 env->subprog_info 数组中二分查找off=0，
	//此时查找失败，return -ENOENT，因为此时数组中还没有任何元素
	ret = add_subprog(env, 0);
	if (ret < 0)
		return ret;

	/* determine subprog starts. The end is one before the next starts */
	//遍历指令，找到BPF_JMP\BPF_CALL和BPF_PSEUDO_CALL三类指令
	for (i = 0; i < insn_cnt; i++) {
		if (insn[i].code != (BPF_JMP | BPF_CALL))
			continue;
		if (insn[i].src_reg != BPF_PSEUDO_CALL)
			continue;
		if (!env->allow_ptr_leaks) {
			verbose(env, "function calls to other bpf functions are allowed for root only\n");
			return -EPERM;
		}
		//将insn中需要调用的函数id二分查找插入env->subprog_info 数组中
		ret = add_subprog(env, i + insn[i].imm + 1);
		if (ret < 0)
			return ret;
	}

	/* Add a fake 'exit' subprog which could simplify subprog iteration
	 * logic. 'subprog_cnt' should not be increased.
	 */
	//在subprog数组中最后一个添加到insn_cnt
	subprog[env->subprog_cnt].start = insn_cnt;

	if (env->log.level & BPF_LOG_LEVEL2)
		for (i = 0; i < env->subprog_cnt; i++)
			verbose(env, "func#%d @%d\n", i, subprog[i].start);

	/* now check that all jumps are within the same subprog */
	//接下来检查所有跳转指令都在一个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;
		//不能是BPF_EXIT和BPF_CALL
		if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
			goto next;
		//获取跳转的off便宜
		off = i + insn[i].off + 1;
		//检查跳转偏移在subprog内
		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) {
			/* to avoid fall-through from one subprog into another
			 * the last insn of the subprog should be either exit
			 * or unconditional jump back
			 */
			//必须保证是BPF_JMP或BPF_EXIT
			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;
		}
	}
	return 0;
}

check_cfg

函数主要目的：

  • 非递归的深度优先遍历检测是否存在有向无环图（循环）
  • 检测控制流合法性。
1
2
3
4
5
struct {
    int *insn_state;
    int *insn_stack;
    int cur_stack;
} cfg;

函数流程：

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

本函数中，首先通过DFS转换成执行流tree。在这里图上的边edge被分成四种情况：

image-20210817165212028

  • tree edge：最正常的顺序执行的边。
  • forward edge：在同一侧前向跨越的边，可能由jmp指令导致。
  • cross edge：跨越左右两侧的边。
  • back edge：后向边，检测到他代表出现了循环。

同样的，图中的点也有几种情况：

  • explored，代表一个已经被DFS完毕所有（出）边的结点。
  • discovered，代表一个结点w，在上一结点t通过边e可达。
  • fallthrough，代表一个结点w为顺序执行的可达点。
  • branch，代表一个结点是条件跳转的分支可达点。

非递归的DFS大致流程如下：

  1. 首先标记第一个点v，压入栈S。
  2. 如果S不空，进入while循环。
    1. 弹出栈顶第一个元素t。如果t是我们需要找的直接return。
    2. 如果t不是，那么通过for循环扫描t结点的每一个边edge。
      1. 如果边e已经被标记了，那么跳过，扫描t的下一个边。
      2. 扫描到t通过e到达的临近顶点w。
      3. 如果w未被标记。
      4. 标记e为tree-edge。标记w为已经发现的点（discovered）。
      5. 压栈w，重新对w进行while循环。直到：
        1. 发现w又是当前路径下一个已发现的点，此时则寻找到一条back-edge，说明存在loop
        2. w已经是叶子结点或标记为探索完成explored。标记为cross或者forward。
      6. 此时t结点所有的边DFS完毕，标记结点t为explored。弹出栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/* 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 = env->cfg.insn_state = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
	if (!insn_state)
		return -ENOMEM;
	//分配指令栈空间
	insn_stack = env->cfg.insn_stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
	if (!insn_stack) {
		kvfree(insn_state);
		return -ENOMEM;
	}

	insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */
	insn_stack[0] = 0; /* 0 is the first instruction */
	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];
	//BPF_JMP和BPF_JMP32两类
	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;
			//如果压栈失败，则报错
			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;
}

push_insn

函数主要目的：

  • 对指令结点t与t+1入栈（t+1也可能是其他的分支或者函数结点），模拟执行。
  • 检测控制流合法性。
  • 返回0，代表下一条指令w不压栈，当前为退栈流程。返回1代表成功压栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/* 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;
}

Do_check

函数主要目的：

  • 刚刚那张图的分支检测等。
  • check寄存器，stack，bpf context，map等的可读写性。
  • 更新栈内存，寄存器的状态。

  1. 当遇见BPF_ALU、BPF_ALU64的指令。对多种可能的ALU操作，比如neg、add、xor、rsh等进行可能的合法性校验（源、目的操作数、寄存器等）。过度细节的校验就不贴上来了。

    检验完之后调用 adjust_reg_min_max_vals(env, insn) 计算新的min/max范围与var_off

  2. 如果是class==BPF_LDX。即加载指令。

    a. 先调用 check_reg_arg(env, insn->src_reg, SRC_OP) 检测src_reg是否可读。

    b. 再调用 check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK) 检测dst_reg是否可写。

    c. 调用 check_mem_access(env, env->insn_idx, insn->src_reg,insn->off, BPF_SIZE(insn->code),BPF_READ, insn->dst_reg, false); 检测真正要读取的位置：src_reg + off 是否可读。

  3. 除了BPF_LDX以外。本函数还对其他的类型的指令进行了对应的检查。在每个子检查中都是使用的：

    check_reg_arg check_mem_access 等进行组合检查。

相关的变量定义如下：

bpf_verifier_state:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
};

  • branch字段代表的是剩余探索的分支数量。

  • branch = 0，从这个状态出发的所有可能路径都达到了bpf_exit，或者已经被修剪了。

  • branch = 1，至少有一条路径正在被探索，这个状态还没有达到bpf_exit。

  • branch = 2，至少有两条路径正在被探索，这个状态是两个子节点的直接父节点。

    其中一个是FALLTHROUGH也就是顺序执行的状态树边。另一个（稍后将被explored的）状态也被压入栈中，也有branch=1。他的父状态结点也有branch=1。

  • 举个例子如果我们通过if的一条路径走到bpf_exit了，会调用update_branch_counts() 回溯更新每个状态树节点branches的值。if的分支节点之间通过 struct bpf_verifier_state *parent; 指针相连。

image-20210818095733392

bpf_reg_state：

维护了BPF寄存器的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
struct bpf_reg_state {
    /* Ordering of fields matters.  See states_equal() */
    enum bpf_reg_type type;	//bpf_reg_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;
};

bpf_reg_type：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* 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

当reg是一个具体的数值（范围值），本结构代表真正的值。

当reg是一个指针，这代表了到被指向对象的偏移量。

1
2
3
4
5
6
7
8
9
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 };

bpf_stack_slot_type：

1
2
3
4
5
6
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 */
};

接下来是do_check的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
static int do_check(struct bpf_verifier_env *env)
{
	struct bpf_verifier_state *state;
	struct bpf_insn *insns = env->prog->insnsi;
	struct bpf_reg_state *regs;
	int insn_cnt = env->prog->len;
	bool do_print_state = false;
	int prev_insn_idx = -1;

	env->prev_linfo = NULL;

	state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL);
	if (!state)
		return -ENOMEM;
	state->curframe = 0;		//当前在调用栈的最上层
	state->speculative = false;
	state->branches = 1;		//当前节点branches=1
	state->frame[0] = kzalloc(sizeof(struct bpf_func_state), GFP_KERNEL);	//记录调用栈
	if (!state->frame[0]) {
		kfree(state);
		return -ENOMEM;
	}
	env->cur_state = state;		//记录当前初始节点
	//初始化函数状态与寄存器
	init_func_state(env, state->frame[0],
			BPF_MAIN_FUNC /* callsite */,
			0 /* frameno */,
			0 /* subprogno, zero == main subprog */);

	if (btf_check_func_arg_match(env, 0))
		return -EINVAL;

	for (;;) {
		struct bpf_insn *insn;
		u8 class;
		int err;

		env->prev_insn_idx = prev_insn_idx;
		//指令数量
		if (env->insn_idx >= insn_cnt) {
			verbose(env, "invalid insn idx %d insn_cnt %d\n",
				env->insn_idx, insn_cnt);
			return -EFAULT;
		}
		//指令
		insn = &insns[env->insn_idx];
		//指令类型
		class = BPF_CLASS(insn->code);
		//检查已经处理过的指令是否超过最大处理数
		if (++env->insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) {
			verbose(env,
				"BPF program is too large. Processed %d insn\n",
				env->insn_processed);
			return -E2BIG;
		}
		//指令状态检测
		err = is_state_visited(env, env->insn_idx);
		if (err < 0)
			return err;
		//
		if (err == 1) {
			/* found equivalent state, can prune the search */
			if (env->log.level & BPF_LOG_LEVEL) {
				if (do_print_state)
					verbose(env, "\nfrom %d to %d%s: safe\n",
						env->prev_insn_idx, env->insn_idx,
						env->cur_state->speculative ?
						" (speculative execution)" : "");
				else
					verbose(env, "%d: safe\n", env->insn_idx);
			}
			goto process_bpf_exit;
		}

		if (signal_pending(current))
			return -EAGAIN;

		if (need_resched())
			cond_resched();

		if (env->log.level & BPF_LOG_LEVEL2 ||
		    (env->log.level & BPF_LOG_LEVEL && do_print_state)) {
			if (env->log.level & BPF_LOG_LEVEL2)
				verbose(env, "%d:", env->insn_idx);
			else
				verbose(env, "\nfrom %d to %d%s:",
					env->prev_insn_idx, env->insn_idx,
					env->cur_state->speculative ?
					" (speculative execution)" : "");
			print_verifier_state(env, state->frame[state->curframe]);
			do_print_state = false;
		}

		if (env->log.level & BPF_LOG_LEVEL) {
			const struct bpf_insn_cbs cbs = {
				.cb_print	= verbose,
				.private_data	= env,
			};

			verbose_linfo(env, env->insn_idx, "; ");
			verbose(env, "%d: ", env->insn_idx);
			print_bpf_insn(&cbs, insn, env->allow_ptr_leaks);
		}

		if (bpf_prog_is_dev_bound(env->prog->aux)) {
			err = bpf_prog_offload_verify_insn(env, env->insn_idx,
							   env->prev_insn_idx);
			if (err)
				return err;
		}
		//取寄存器
		regs = cur_regs(env);
		//
		env->insn_aux_data[env->insn_idx].seen = true;
		//前一个指令编号
		prev_insn_idx = env->insn_idx;
		//计算指令
		if (class == BPF_ALU || class == BPF_ALU64) {
			//检查具体指令的合法性，比如是否使用了保留的field，使用的寄存器编号是否超过了模拟寄存器的最大编号
			//寄存器是否可读/写，寄存器值是否是指针等，该函数后面详细解释
			err = check_alu_op(env, insn);
			if (err)
				return err;

		} 
		//取寄存器值指令
		else if (class == BPF_LDX) {
			enum bpf_reg_type *prev_src_type, src_reg_type;

			/* check for reserved fields is already done */

			/* check src operand */
			//检测源寄存器的编号是否超过最大编号，如果为操作数其是否初始化，是否是指针
			err = check_reg_arg(env, insn->src_reg, SRC_OP);
			if (err)
				return err;

			err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
			if (err)
				return err;

			src_reg_type = regs[insn->src_reg].type;

			/* check that memory (src_reg + off) is readable,
			 * the state of dst_reg will be updated by this func
			 */
			//检查src_reg+off指向的内存是可读的
			err = check_mem_access(env, env->insn_idx, insn->src_reg,
					       insn->off, BPF_SIZE(insn->code),
					       BPF_READ, insn->dst_reg, false);
			if (err)
				return err;

			prev_src_type = &env->insn_aux_data[env->insn_idx].ptr_type;

			if (*prev_src_type == NOT_INIT) {
				/* saw a valid insn
				 * dst_reg = *(u32 *)(src_reg + off)
				 * save type to validate intersecting paths
				 */
				//判断出了一种指令类型，即地址取值指令
				*prev_src_type = src_reg_type;

			} else if (reg_type_mismatch(src_reg_type, *prev_src_type)) {
				/* ABuser program is trying to use the same insn
				 * dst_reg = *(u32*) (src_reg + off)
				 * with different pointer types:
				 * src_reg == ctx in one branch and
				 * src_reg == stack|map in some other branch.
				 * Reject it.
				 */
				verbose(env, "same insn cannot be used with different pointers\n");
				return -EINVAL;
			}

		} 
		//存储值指令
		else if (class == BPF_STX) {
			enum bpf_reg_type *prev_dst_type, dst_reg_type;

			if (BPF_MODE(insn->code) == BPF_XADD) {
				err = check_xadd(env, env->insn_idx, insn);
				if (err)
					return err;
				env->insn_idx++;
				continue;
			}

			/* check src1 operand */
			err = check_reg_arg(env, insn->src_reg, SRC_OP);
			if (err)
				return err;
			/* check src2 operand */
			err = check_reg_arg(env, insn->dst_reg, SRC_OP);
			if (err)
				return err;

			dst_reg_type = regs[insn->dst_reg].type;

			/* check that memory (dst_reg + off) is writeable */
			err = check_mem_access(env, env->insn_idx, insn->dst_reg,
					       insn->off, BPF_SIZE(insn->code),
					       BPF_WRITE, insn->src_reg, false);
			if (err)
				return err;

			prev_dst_type = &env->insn_aux_data[env->insn_idx].ptr_type;

			if (*prev_dst_type == NOT_INIT) {
				*prev_dst_type = dst_reg_type;
			} else if (reg_type_mismatch(dst_reg_type, *prev_dst_type)) {
				verbose(env, "same insn cannot be used with different pointers\n");
				return -EINVAL;
			}

		} else if (class == BPF_ST) {
			if (BPF_MODE(insn->code) != BPF_MEM ||
			    insn->src_reg != BPF_REG_0) {
				verbose(env, "BPF_ST uses reserved fields\n");
				return -EINVAL;
			}
			/* check src operand */
			err = check_reg_arg(env, insn->dst_reg, SRC_OP);
			if (err)
				return err;

			if (is_ctx_reg(env, insn->dst_reg)) {
				verbose(env, "BPF_ST stores into R%d %s is not allowed\n",
					insn->dst_reg,
					reg_type_str[reg_state(env, insn->dst_reg)->type]);
				return -EACCES;
			}

			/* check that memory (dst_reg + off) is writeable */
			err = check_mem_access(env, env->insn_idx, insn->dst_reg,
					       insn->off, BPF_SIZE(insn->code),
					       BPF_WRITE, -1, false);
			if (err)
				return err;

		} else if (class == BPF_JMP || class == BPF_JMP32) {
			u8 opcode = BPF_OP(insn->code);

			env->jmps_processed++;
			//直接跳转call
			if (opcode == BPF_CALL) {
				if (BPF_SRC(insn->code) != BPF_K ||
				    insn->off != 0 ||
				    (insn->src_reg != BPF_REG_0 &&
				     insn->src_reg != BPF_PSEUDO_CALL) ||
				    insn->dst_reg != BPF_REG_0 ||
				    class == BPF_JMP32) {
					verbose(env, "BPF_CALL uses reserved fields\n");
					return -EINVAL;
				}
				//
				if (env->cur_state->active_spin_lock &&
				    (insn->src_reg == BPF_PSEUDO_CALL ||
				     insn->imm != BPF_FUNC_spin_unlock)) {
					verbose(env, "function calls are not allowed while holding a lock\n");
					return -EINVAL;
				}
				//在这个函数中会检查跳转的地址有无超过范围，函数的五个参数的参数类型(是否是key/value/map地址/stack_size等)，更新返回值寄存器，更新reg_state等
				if (insn->src_reg == BPF_PSEUDO_CALL)
					err = check_func_call(env, insn, &env->insn_idx);
				else
					err = check_helper_call(env, insn->imm, env->insn_idx);
				if (err)
					return err;

			} 
			//跳转指令
			else if (opcode == BPF_JA) {
				if (BPF_SRC(insn->code) != BPF_K ||
				    insn->imm != 0 ||
				    insn->src_reg != BPF_REG_0 ||
				    insn->dst_reg != BPF_REG_0 ||
				    class == BPF_JMP32) {
					verbose(env, "BPF_JA uses reserved fields\n");
					return -EINVAL;
				}

				env->insn_idx += insn->off + 1;
				continue;

			} else if (opcode == BPF_EXIT) {
				if (BPF_SRC(insn->code) != BPF_K ||
				    insn->imm != 0 ||
				    insn->src_reg != BPF_REG_0 ||
				    insn->dst_reg != BPF_REG_0 ||
				    class == BPF_JMP32) {
					verbose(env, "BPF_EXIT uses reserved fields\n");
					return -EINVAL;
				}

				if (env->cur_state->active_spin_lock) {
					verbose(env, "bpf_spin_unlock is missing\n");
					return -EINVAL;
				}

				if (state->curframe) {
					/* exit from nested function */
					err = prepare_func_exit(env, &env->insn_idx);
					if (err)
						return err;
					do_print_state = true;
					continue;
				}

				err = check_reference_leak(env);
				if (err)
					return err;

				/* eBPF calling convetion is such that R0 is used
				 * to return the value from eBPF program.
				 * Make sure that it's readable at this time
				 * of bpf_exit, which means that program wrote
				 * something into it earlier
				 */
				err = check_reg_arg(env, BPF_REG_0, SRC_OP);
				if (err)
					return err;

				if (is_pointer_value(env, BPF_REG_0)) {
					verbose(env, "R0 leaks addr as return value\n");
					return -EACCES;
				}

				err = check_return_code(env);
				if (err)
					return err;
process_bpf_exit:
				update_branch_counts(env, env->cur_state);
				err = pop_stack(env, &prev_insn_idx,
						&env->insn_idx);
				if (err < 0) {
					if (err != -ENOENT)
						return err;
					break;
				} else {
					do_print_state = true;
					continue;
				}
			} else {
				err = check_cond_jmp_op(env, insn, &env->insn_idx);
				if (err)
					return err;
			}
		} else if (class == BPF_LD) {
			u8 mode = BPF_MODE(insn->code);

			if (mode == BPF_ABS || mode == BPF_IND) {
				err = check_ld_abs(env, insn);
				if (err)
					return err;

			} else if (mode == BPF_IMM) {
				err = check_ld_imm(env, insn);
				if (err)
					return err;

				env->insn_idx++;
				env->insn_aux_data[env->insn_idx].seen = true;
			} else {
				verbose(env, "invalid BPF_LD mode\n");
				return -EINVAL;
			}
		} else {
			verbose(env, "unknown insn class %d\n", class);
			return -EINVAL;
		}

		env->insn_idx++;
	}

	env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
	return 0;
}

init_func_state

1
2
3
4
5
6
7
8
9
10
11
#define BPF_MAIN_FUNC (-1)
static void init_func_state(struct bpf_verifier_env *env,
			    struct bpf_func_state *state,
			    int callsite, int frameno, int subprogno)
{
	state->callsite = callsite;
	state->frameno = frameno;
	state->subprogno = subprogno;
	//初始化函数状态与寄存器
	init_reg_state(env, state);
}

init_reg_state

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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_alu_op

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
/* check validity of 32-bit and 64-bit arithmetic operations */
static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
{	
	//获取寄存器状态
	struct bpf_reg_state *regs = cur_regs(env);
	u8 opcode = BPF_OP(insn->code);
	int err;
	//
	if (opcode == BPF_END || opcode == BPF_NEG) {
		//not eaqul and greate
		if (opcode == BPF_NEG) {
			//源寄存器不能为reg0,偏移或imm不能为0
			if (BPF_SRC(insn->code) != 0 ||
			    insn->src_reg != BPF_REG_0 ||
			    insn->off != 0 || insn->imm != 0) {
				verbose(env, "BPF_NEG uses reserved fields\n");
				return -EINVAL;
			}
		} else {
			if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
			    (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) ||
			    BPF_CLASS(insn->code) == BPF_ALU64) {
				verbose(env, "BPF_END uses reserved fields\n");
				return -EINVAL;
			}
		}

		/* check src operand */
		err = check_reg_arg(env, insn->dst_reg, SRC_OP);
		if (err)
			return err;
		//检查指针是否合法
		if (is_pointer_value(env, insn->dst_reg)) {
			verbose(env, "R%d pointer arithmetic prohibited\n",
				insn->dst_reg);
			return -EACCES;
		}

		/* check dest operand */
		//检查目标参数是否合法
		err = check_reg_arg(env, insn->dst_reg, DST_OP);
		if (err)
			return err;

	} 
	//mov赋值指令
	else if (opcode == BPF_MOV) {

		if (BPF_SRC(insn->code) == BPF_X) {
			if (insn->imm != 0 || insn->off != 0) {
				verbose(env, "BPF_MOV uses reserved fields\n");
				return -EINVAL;
			}

			/* check src operand */
			err = check_reg_arg(env, insn->src_reg, SRC_OP);
			if (err)
				return err;
		} else {
			if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
				verbose(env, "BPF_MOV uses reserved fields\n");
				return -EINVAL;
			}
		}

		/* check dest operand, mark as required later */
		err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
		if (err)
			return err;

		if (BPF_SRC(insn->code) == BPF_X) {
			struct bpf_reg_state *src_reg = regs + insn->src_reg;
			struct bpf_reg_state *dst_reg = regs + insn->dst_reg;

			if (BPF_CLASS(insn->code) == BPF_ALU64) {
				/* case: R1 = R2
				 * copy register state to dest reg
				 */
				*dst_reg = *src_reg;
				dst_reg->live |= REG_LIVE_WRITTEN;
				dst_reg->subreg_def = DEF_NOT_SUBREG;
			} else {
				/* R1 = (u32) R2 */
				if (is_pointer_value(env, insn->src_reg)) {
					verbose(env,
						"R%d partial copy of pointer\n",
						insn->src_reg);
					return -EACCES;
				} else if (src_reg->type == SCALAR_VALUE) {
					*dst_reg = *src_reg;
					dst_reg->live |= REG_LIVE_WRITTEN;
					dst_reg->subreg_def = env->insn_idx + 1;
				} else {
					mark_reg_unknown(env, regs,
							 insn->dst_reg);
				}
				coerce_reg_to_size(dst_reg, 4);
			}
		} else {
			/* case: R = imm
			 * remember the value we stored into this reg
			 */
			/* clear any state __mark_reg_known doesn't set */
			mark_reg_unknown(env, regs, insn->dst_reg);
			regs[insn->dst_reg].type = SCALAR_VALUE;
			if (BPF_CLASS(insn->code) == BPF_ALU64) {
				__mark_reg_known(regs + insn->dst_reg,
						 insn->imm);
			} else {
				__mark_reg_known(regs + insn->dst_reg,
						 (u32)insn->imm);
			}
		}

	} else if (opcode > BPF_END) {
		verbose(env, "invalid BPF_ALU opcode %x\n", opcode);
		return -EINVAL;

	} else {	/* all other ALU ops: and, sub, xor, add, ... */

		if (BPF_SRC(insn->code) == BPF_X) {
			if (insn->imm != 0 || insn->off != 0) {
				verbose(env, "BPF_ALU uses reserved fields\n");
				return -EINVAL;
			}
			/* check src1 operand */
			err = check_reg_arg(env, insn->src_reg, SRC_OP);
			if (err)
				return err;
		} else {
			if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
				verbose(env, "BPF_ALU uses reserved fields\n");
				return -EINVAL;
			}
		}

		/* check src2 operand */
		err = check_reg_arg(env, insn->dst_reg, SRC_OP);
		if (err)
			return err;

		if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
		    BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
			verbose(env, "div by zero\n");
			return -EINVAL;
		}

		if ((opcode == BPF_LSH || opcode == BPF_RSH ||
		     opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
			int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;

			if (insn->imm < 0 || insn->imm >= size) {
				verbose(env, "invalid shift %d\n", insn->imm);
				return -EINVAL;
			}
		}

		/* check dest operand */
		err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
		if (err)
			return err;

		return adjust_reg_min_max_vals(env, insn);
	}

	return 0;
}

check_func_call

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
			   int *insn_idx)
{
	struct bpf_verifier_state *state = env->cur_state;
	struct bpf_func_state *caller, *callee;
	int i, err, subprog, target_insn;
	//栈地址是否超过最大栈帧环境
	if (state->curframe + 1 >= MAX_CALL_FRAMES) {
		verbose(env, "the call stack of %d frames is too deep\n",
			state->curframe + 2);
		return -E2BIG;
	}
	//目标指令
	target_insn = *insn_idx + insn->imm;
	//通过目标指令找到ebpf程序
	subprog = find_subprog(env, target_insn + 1);
	if (subprog < 0) {
		verbose(env, "verifier bug. No program starts at insn %d\n",
			target_insn + 1);
		return -EFAULT;
	}
	//call调用者
	caller = state->frame[state->curframe];
	//目标栈帧环境
	if (state->frame[state->curframe + 1]) {
		verbose(env, "verifier bug. Frame %d already allocated\n",
			state->curframe + 1);
		return -EFAULT;
	}

	callee = kzalloc(sizeof(*callee), GFP_KERNEL);
	if (!callee)
		return -ENOMEM;
	//更新栈帧
	state->frame[state->curframe + 1] = callee;

	/* callee cannot access r0, r6 - r9 for reading and has to write
	 * into its own stack before reading from it.
	 * callee can read/write into caller's stack
	 */
	init_func_state(env, callee,
			/* remember the callsite, it will be used by bpf_exit */
			*insn_idx /* callsite */,
			state->curframe + 1 /* frameno within this callchain */,
			subprog /* subprog number within this prog */);

	/* Transfer references to the callee */
	err = transfer_reference_state(callee, caller);
	if (err)
		return err;

	/* copy r1 - r5 args that callee can access.  The copy includes parent
	 * pointers, which connects us up to the liveness chain
	 */
	for (i = BPF_REG_1; i <= BPF_REG_5; i++)
		callee->regs[i] = caller->regs[i];

	/* after the call registers r0 - r5 were scratched */
	for (i = 0; i < CALLER_SAVED_REGS; i++) {
		mark_reg_not_init(env, caller->regs, caller_saved[i]);
		check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
	}

	/* only increment it after check_reg_arg() finished */
	state->curframe++;

	if (btf_check_func_arg_match(env, subprog))
		return -EINVAL;

	/* and go analyze first insn of the callee */
	*insn_idx = target_insn;

	if (env->log.level & BPF_LOG_LEVEL) {
		verbose(env, "caller:\n");
		print_verifier_state(env, caller);
		verbose(env, "callee:\n");
		print_verifier_state(env, callee);
	}
	return 0;
}

check_mem_access

这个函数是check中用来检查内存访问非常重要的一个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* 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);
    }
  ......

check_stack_access

通过 check_stack_access 检测栈的可访问状况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}

接下来通过func函数查找当前的调用栈。

然后通过 update_stack_depth 对每个函数的栈消耗进行维护。如果当前访问的地址超出当前函数的栈范围，那么对当前函数进行栈扩充。

接下来判断读or写操作。

  • 写操作，调用 check_stack_write 检测栈的可写性。
    • 未设置 allow_ptr_leaks不允许部分写STACK_SPILL类型的栈数据。
    • reg是STACK_SPILL，部分写不允许。
    • reg是非STACK_SPILL，根据reg和写入字节的情况设置栈相应的slot类型，支持部分写。
    • state->stack[spi].slot_type[]中低地址保存实际栈高地址的数据类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/* 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;
}

check_max_stack_depth

我们重新回到上层的 bpf_check 中。

函数目的：

  • 保证函数调用深度不超过 MAX_BPF_STACK
  • 挑选出code为BPF_JMP , BPF_CALL ；src_reg为：BPF_PSEUDO_CALL，即eBPF到eBPF的函数调用。记录对应的深度与返回地址，调用完返回上层subprog。在这之间如果调用深度超过8或者最大栈消耗超过512字节，abort。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/* 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;        //返回
}

fixup_bpf_calls

函数目的：

  • 修复bpf_call指令的insn->imm字段，并将符合条件的helper func内联为明确的BPF指令序列。

首先，本函数对指令做了patch，修复一些不合法的指令。处理尾调用等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
{
        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;
        }

JIT

赏

只要你支持她，我们就是好朋友2333

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要研究：
二进制安全、漏洞挖掘
CTF菜鸡一只

天枢Dubhe 学习ing