[PATCH bpf-next v2 07/22] bpf: Let the patch list remove instructions

[Qiliang Yuan <odys.yuan@gmail.com>]

verifier_remove_insns() removes a range of instructions. It moves the
tail of the program and of the aux data, walks all branches, and fixes
up the subprogs, the line info, the function pointers and the
instruction arrays, at the same O(N * M) cost as patching.

The patch list can only replace instructions, so bpf_opt_remove_nops()
and bpf_opt_remove_dead_code() can't move over to it.

Add bpf_patch_list_del() to queue the removal of an instruction along
with patches. Map a removed instruction to the next one that stays, so
that jumps to it land there. Drop the line info of removed
instructions, except that the last one moves to the next instruction
that stays if that has none of its own. Remove the subprogs whose
instructions are all removed, with their func_info, and mark the
function pointers to them and the entries of instruction arrays
deleted. Tell offloaded programs about each removed range.

Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
---
 include/linux/bpf_verifier.h |   9 +++
 kernel/bpf/bpf_insn_array.c  |  10 ++-
 kernel/bpf/core.c            |  27 +++++++-
 kernel/bpf/fixups.c          | 142 ++++++++++++++++++++++++++++++++++++++++---
 4 files changed, 176 insertions(+), 12 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 49a6e443de75d..ace314cc539dd 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1089,6 +1089,7 @@ struct bpf_patch_image {
 	u32 new_cnt;
 	s32 grow;
 	u32 bad;
+	bool del;
 };
 
 /* Map an offset in the old program, which may be past its end. */
@@ -1098,9 +1099,16 @@ static inline u32 bpf_patch_image_remap(const struct bpf_patch_image *img,
 	return off <= img->cnt ? map[off] : off + img->grow;
 }
 
+static inline bool bpf_patch_image_deleted(const struct bpf_patch_image *img, u32 off)
+{
+	return off < img->cnt && img->new_off[off] == img->new_off[off + 1];
+}
+
 struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
 				      const struct bpf_prog *prog, u32 off,
 				      const struct bpf_insn *patch, u32 len);
+int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
+			 u32 off);
 void bpf_patch_list_release(struct bpf_patch_list *pl);
 int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog *prog,
 			 struct bpf_patch_image *img);
@@ -2066,6 +2074,7 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 				    const struct bpf_insn *patch, u32 len);
 int bpf_patch_list_commit(struct bpf_verifier_env *env);
 void bpf_patch_list_free(struct bpf_verifier_env *env);
+int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off);
 
 int bpf_flip_opcode(u32 opcode);
 u8 bpf_rev_opcode(u8 opcode);
diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index dbfcf1eddb91e..5330e2d7f4062 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -254,8 +254,9 @@ void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len)
 }
 
 /*
- * Move each offset to new_off[offset], new_off[] covers [0, cnt]. Offsets
- * past the end of the old program only move by 'grow'.
+ * Move each offset to new_off[offset], new_off[] covers [0, cnt]. An insn is
+ * removed when it maps to the same offset as the next one. Offsets past the
+ * end of the old program only move by 'grow'.
  */
 void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32 grow)
 {
@@ -267,7 +268,10 @@ void bpf_insn_array_remap(struct bpf_map *map, const u32 *new_off, u32 cnt, s32
 		off = insn_array->values[i].xlated_off;
 		if (off == INSN_DELETED)
 			continue;
-		insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow;
+		if (off < cnt && new_off[off] == new_off[off + 1])
+			insn_array->values[i].xlated_off = INSN_DELETED;
+		else
+			insn_array->values[i].xlated_off = off <= cnt ? new_off[off] : off + grow;
 	}
 }
 
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index d2c36db09c8c9..75d6399ce0965 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -658,6 +658,25 @@ struct bpf_insn *__bpf_patch_list_add(struct bpf_patch_list *pl,
 	return &pl->insns[p->start + len - 1];
 }
 
+/* Queue the removal of insn 'off'. Jumps to it land on the next insn that stays. */
+int __bpf_patch_list_del(struct bpf_patch_list *pl, const struct bpf_prog *prog,
+			 u32 off)
+{
+	struct bpf_insn_patch *p;
+	int err;
+
+	err = patch_list_reserve_patch(pl);
+	if (err)
+		return err;
+
+	p = &pl->patches[pl->cnt++];
+	p->off = off;
+	p->len = 0;
+	p->start = pl->insn_cnt;
+	p->orig = prog->insnsi[off];
+	return 0;
+}
+
 void bpf_patch_list_release(struct bpf_patch_list *pl)
 {
 	kvfree(pl->patches);
@@ -684,8 +703,10 @@ int bpf_patch_list_build(const struct bpf_patch_list *pl, const struct bpf_prog
 
 	for (i = 0, k = 0; i <= cnt; i++) {
 		img->new_off[i] = i + img->grow;
-		if (k < pl->cnt && pl->patches[k].off == i)
+		if (k < pl->cnt && pl->patches[k].off == i) {
+			img->del |= !pl->patches[k].len;
 			img->grow += pl->patches[k++].len - 1;
+		}
 	}
 	img->new_cnt = cnt + img->grow;
 
@@ -724,7 +745,7 @@ void bpf_patch_image_free(struct bpf_patch_image *img)
 
 /*
  * Put the new image in 'prog', which has room for it, and move the poke
- * descriptors and the line info along.
+ * descriptors and, unless insns were removed, the line info along.
  */
 void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image *img)
 {
@@ -738,6 +759,8 @@ void bpf_patch_image_install(struct bpf_prog *prog, const struct bpf_patch_image
 			bpf_patch_image_remap(img, img->new_off,
 					      prog->aux->poke_tab[i].insn_idx);
 
+	if (img->del)
+		return;
 	for (i = 0; i < prog->aux->nr_linfo; i++)
 		prog->aux->linfo[i].insn_off =
 			bpf_patch_image_remap(img, img->new_off,
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 940265cb80ebf..1a1a374a076b1 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -408,6 +408,22 @@ struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off,
 	return __bpf_patch_list_add(pl, env->prog, off, patch, len);
 }
 
+/* Queue the removal of insn 'off' until bpf_patch_list_commit(). */
+int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off)
+{
+	struct bpf_patch_list *pl = &env->patch_list;
+
+	if (bpf_rewrite_must_abort())
+		return -EINTR;
+
+	if (verifier_bug_if(off >= env->prog->len ||
+			    (pl->cnt && off <= pl->patches[pl->cnt - 1].off),
+			    env, "insn %u removed out of order", off))
+		return -EFAULT;
+
+	return __bpf_patch_list_del(pl, env->prog, off);
+}
+
 void bpf_patch_list_free(struct bpf_verifier_env *env)
 {
 	bpf_patch_list_release(&env->patch_list);
@@ -453,9 +469,79 @@ static void patch_list_adj_aux(struct bpf_prog *prog, struct bpf_insn_patch *p,
 }
 
 /*
- * Apply all queued patches in one go. Everything that names an insn of the
- * old image follows it to the new one, a patched insn is named by the first
- * insn of its patch, like with bpf_patch_insn_data().
+ * Drop the line info of removed insns. The last one before the next insn
+ * that stays moves to it, unless that insn has its own line info.
+ */
+static void patch_list_adj_linfo(struct bpf_verifier_env *env,
+				 const struct bpf_patch_image *img, u32 *linfo_map)
+{
+	struct bpf_prog_aux *aux = env->prog->aux;
+	struct bpf_line_info *linfo = aux->linfo;
+	u32 i, j, pos, next, nr = aux->nr_linfo;
+
+	for (i = 0, j = 0; i < nr; i++) {
+		pos = bpf_patch_image_remap(img, img->new_off, linfo[i].insn_off);
+		linfo_map[i] = j;
+		if (bpf_patch_image_deleted(img, linfo[i].insn_off)) {
+			next = i + 1 < nr ?
+			       bpf_patch_image_remap(img, img->new_off, linfo[i + 1].insn_off) :
+			       U32_MAX;
+			if (pos >= img->new_cnt || next == pos)
+				continue;
+		}
+		linfo[j] = linfo[i];
+		linfo[j++].insn_off = pos;
+	}
+	linfo_map[nr] = j;
+	aux->nr_linfo = j;
+
+	/* NOTE: fake 'exit' subprog should be updated as well. */
+	for (i = 0; i <= env->subprog_cnt; i++)
+		env->subprog_info[i].linfo_idx =
+			linfo_map[min(env->subprog_info[i].linfo_idx, nr)];
+}
+
+/* Remove the subprogs whose insns are all removed, with their func_info. */
+static void patch_list_del_subprogs(struct bpf_verifier_env *env,
+				    const u32 *new_off)
+{
+	struct bpf_subprog_info *info = env->subprog_info;
+	struct bpf_prog_aux *aux = env->prog->aux;
+	int i, j, exc_cb = env->exception_callback_subprog;
+
+	for (i = 0, j = 0; i < env->subprog_cnt; i++) {
+		if (new_off[info[i].start] == new_off[info[i + 1].start]) {
+			/* The exception callback is live, so it isn't removed. */
+			if (env->exception_callback_subprog > i)
+				exc_cb--;
+			continue;
+		}
+		if (i != j) {
+			info[j] = info[i];
+			if (aux->func_info)
+				aux->func_info[j] = aux->func_info[i];
+			if (aux->func_info_aux)
+				aux->func_info_aux[j] = aux->func_info_aux[i];
+		}
+		j++;
+	}
+	if (i == j)
+		return;
+
+	/* move fake 'exit' subprog as well */
+	info[j] = info[i];
+	/* func_info->insn_off is set after all code rewrites, in adjust_btf_func() */
+	if (aux->func_info)
+		aux->func_info_cnt -= i - j;
+	env->subprog_cnt = j;
+	env->exception_callback_subprog = exc_cb;
+}
+
+/*
+ * Apply all queued patches and removals in one go. Everything that names an
+ * insn of the old image follows it to the new one. A patched insn is named by
+ * the first insn of its patch, a removed insn by the next insn that stays,
+ * like with bpf_patch_insn_data().
  */
 int bpf_patch_list_commit(struct bpf_verifier_env *env)
 {
@@ -463,7 +549,8 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 	struct bpf_insn_aux_data *data = NULL;
 	struct bpf_prog *prog = env->prog;
 	struct bpf_patch_image img = {};
-	u32 i, k, end;
+	u32 *linfo_map = NULL;
+	u32 i, k, n, end;
 	struct bpf_insn_patch *p;
 	int err = 0;
 
@@ -488,20 +575,43 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 			 GFP_KERNEL_ACCOUNT | __GFP_ZERO);
 	if (!data)
 		goto out;
+	if (img.del && prog->aux->nr_linfo) {
+		linfo_map = kvmalloc_array(prog->aux->nr_linfo + 1,
+					   sizeof(*linfo_map), GFP_KERNEL_ACCOUNT);
+		if (!linfo_map)
+			goto out;
+	}
 
 	prog = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER);
 	if (!prog)
 		goto out;
 	env->prog = prog;
 
+	if (img.del && bpf_prog_is_offloaded(prog->aux)) {
+		/* the aux data still describes the old image */
+		for (k = 0; k < pl->cnt; k = n) {
+			for (n = k; n < pl->cnt && !pl->patches[n].len &&
+			     pl->patches[n].off == pl->patches[k].off + n - k; n++)
+				;
+			if (n == k)
+				n++;
+			else
+				bpf_prog_offload_remove_insns(env, pl->patches[k].off,
+							      n - k);
+		}
+	}
+
 	bpf_patch_image_install(prog, &img);
 
 	for (i = 0, k = 0; i < img.cnt; i = end) {
 		if (k < pl->cnt && pl->patches[k].off == i) {
 			p = &pl->patches[k++];
-			patch_list_adj_aux(prog, p, &pl->insns[p->start],
-					   &env->insn_aux_data[i],
-					   &data[img.new_off[i]]);
+			if (p->len)
+				patch_list_adj_aux(prog, p, &pl->insns[p->start],
+						   &env->insn_aux_data[i],
+						   &data[img.new_off[i]]);
+			else
+				bpf_clear_insn_aux_data(env, i, 1);
 			end = i + 1;
 			continue;
 		}
@@ -514,25 +624,43 @@ int bpf_patch_list_commit(struct bpf_verifier_env *env)
 	env->insn_aux_data_len = img.new_cnt;
 	data = NULL;
 
+	/* before subprogs are removed, since it looks at them */
 	for (i = 0; i < env->func_ptr_cnt; i++) {
 		struct bpf_func_ptr *fp = &env->func_ptrs[i];
+		int subprog;
 
 		if (fp->xlated_off == BPF_FUNC_PTR_DELETED)
 			continue;
+		if (bpf_patch_image_deleted(&img, fp->xlated_off)) {
+			subprog = bpf_find_subprog(env, fp->xlated_off);
+			if (subprog <= 0 ||
+			    img.new_off[env->subprog_info[subprog].start] ==
+			    img.new_off[env->subprog_info[subprog + 1].start]) {
+				fp->xlated_off = BPF_FUNC_PTR_DELETED;
+				continue;
+			}
+		}
 		fp->xlated_off = bpf_patch_image_remap(&img, img.new_off, fp->xlated_off);
 	}
 
+	if (img.del)
+		patch_list_del_subprogs(env, img.new_off);
+
 	/* NOTE: fake 'exit' subprog should be updated as well. */
 	for (i = 0; i <= env->subprog_cnt; i++)
 		env->subprog_info[i].start =
 			bpf_patch_image_remap(&img, img.new_off, env->subprog_info[i].start);
 
+	if (linfo_map)
+		patch_list_adj_linfo(env, &img, linfo_map);
+
 	for (i = 0; i < env->insn_array_map_cnt; i++)
 		bpf_insn_array_remap(env->insn_array_maps[i], img.new_off,
 				     img.cnt, img.grow);
 
 	err = 0;
 out:
+	kvfree(linfo_map);
 	vfree(data);
 	bpf_patch_image_free(&img);
 	bpf_patch_list_release(pl);

-- 
2.43.0