This creates and populates the main oracle map for our BPF program. The map is populated with the inner oracle map created and populated in previous patches. This main oracle map is a hashmap of maps with pruning point indexes as keys and inner oracle maps as values. Map flag BPF_F_INNER_MAP is required because our inner oracle maps won't all hold the same number of states. Signed-off-by: Paul Chaignon --- include/linux/bpf.h | 3 + include/linux/bpf_verifier.h | 2 + kernel/bpf/hashtab.c | 6 +- kernel/bpf/oracle.c | 130 +++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 5 ++ 5 files changed, 143 insertions(+), 3 deletions(-) diff --git a/include/linux/bpf.h b/include/linux/bpf.h index 6bec31816485..58cba1b48f80 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -2794,6 +2794,9 @@ int bpf_fd_array_map_update_elem(struct bpf_map *map, struct file *map_file, int bpf_fd_array_map_lookup_elem(struct bpf_map *map, void *key, u32 *value); int bpf_fd_htab_map_update_elem(struct bpf_map *map, struct file *map_file, void *key, void *value, u64 map_flags); +long htab_map_update_elem_in_place(struct bpf_map *map, void *key, + void *value, u64 map_flags, + bool percpu, bool onallcpus); int bpf_fd_htab_map_lookup_elem(struct bpf_map *map, void *key, u32 *value); int bpf_get_file_flag(int flags); diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index a93b5e2f4d7f..cffbd0552b43 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -846,6 +846,7 @@ struct bpf_verifier_env { u32 longest_mark_read_walk; u32 free_list_size; u32 explored_states_size; + u32 num_prune_points; u32 num_backedges; bpfptr_t fd_array; @@ -1128,5 +1129,6 @@ void bpf_reset_live_stack_callchain(struct bpf_verifier_env *env); int save_state_in_oracle(struct bpf_verifier_env *env, int insn_idx); struct bpf_prog *patch_oracle_check_insn(struct bpf_verifier_env *env, struct bpf_insn *insn, int i, int *cnt); +int create_and_populate_oracle_map(struct bpf_verifier_env *env); #endif /* _LINUX_BPF_VERIFIER_H */ diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index c8a9b27f8663..0cf286ff0084 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -1249,9 +1249,9 @@ static long htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value return ret; } -static long htab_map_update_elem_in_place(struct bpf_map *map, void *key, - void *value, u64 map_flags, - bool percpu, bool onallcpus) +long htab_map_update_elem_in_place(struct bpf_map *map, void *key, + void *value, u64 map_flags, + bool percpu, bool onallcpus) { struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct htab_elem *l_new, *l_old; diff --git a/kernel/bpf/oracle.c b/kernel/bpf/oracle.c index 404c641cb3f6..44b86e6ef3b2 100644 --- a/kernel/bpf/oracle.c +++ b/kernel/bpf/oracle.c @@ -190,3 +190,133 @@ struct bpf_prog *patch_oracle_check_insn(struct bpf_verifier_env *env, struct bp *cnt = 1; return new_prog; } + +static int populate_oracle_map(struct bpf_verifier_env *env, struct bpf_map *oracle_map) +{ + struct bpf_insn_aux_data *aux; + int i, err; + + /* Oracle checks are always before pruning points, so they cannot be the last + * instruction. + */ + for (i = 0; i < env->prog->len - 1; i++) { + aux = &env->insn_aux_data[i]; + if (!aux->oracle_inner_map || !aux->oracle_inner_map->max_entries) + continue; + + bpf_map_inc(aux->oracle_inner_map); + + rcu_read_lock(); + err = htab_map_update_elem_in_place(oracle_map, &i, &aux->oracle_inner_map, + BPF_NOEXIST, false, false); + rcu_read_unlock(); + if (err) { + bpf_map_put(aux->oracle_inner_map); + return err; + } + } + + return 0; +} + +static struct bpf_map *alloc_oracle_inner_map_meta(void) +{ + struct bpf_array *inner_array_meta; + struct bpf_map *inner_map_meta; + + inner_map_meta = kzalloc(sizeof(*inner_map_meta), GFP_USER); + if (!inner_map_meta) + return ERR_PTR(-ENOMEM); + + inner_map_meta->map_type = BPF_MAP_TYPE_ARRAY; + inner_map_meta->key_size = sizeof(__u32); + inner_map_meta->value_size = sizeof(struct bpf_oracle_state); + inner_map_meta->map_flags = BPF_F_INNER_MAP; + inner_map_meta->max_entries = 1; + + inner_map_meta->ops = &array_map_ops; + + inner_array_meta = container_of(inner_map_meta, struct bpf_array, map); + inner_array_meta->index_mask = 0; + inner_array_meta->elem_size = round_up(inner_map_meta->value_size, 8); + inner_map_meta->bypass_spec_v1 = true; + + return inner_map_meta; +} + +static struct bpf_map *create_oracle_map(struct bpf_verifier_env *env) +{ + struct bpf_map *map = NULL, *inner_map; + int err; + + union bpf_attr map_attr = { + .map_type = BPF_MAP_TYPE_HASH_OF_MAPS, + .key_size = sizeof(__u32), + .value_size = sizeof(__u32), + .max_entries = env->num_prune_points, + .map_flags = BPF_F_RDONLY, + .map_name = "oracle_map", + }; + /* We don't want to use htab_of_maps_map_ops here because it expects map_attr.inner_map_fd + * to be set to the fd of inner_map_meta, which we don't have. Instead we can allocate and + * set inner_map_meta ourselves. + */ + map = htab_map_ops.map_alloc(&map_attr); + if (IS_ERR(map)) + return map; + + map->ops = &htab_of_maps_map_ops; + map->map_type = BPF_MAP_TYPE_HASH_OF_MAPS; + + inner_map = alloc_oracle_inner_map_meta(); + if (IS_ERR(inner_map)) { + err = PTR_ERR(inner_map); + goto free_map; + } + map->inner_map_meta = inner_map; + + err = bpf_obj_name_cpy(map->name, map_attr.map_name, + sizeof(map_attr.map_name)); + if (err < 0) + goto free_map; + + mutex_init(&map->freeze_mutex); + spin_lock_init(&map->owner_lock); + + err = security_bpf_map_create(map, &map_attr, NULL, false); + if (err) + goto free_map_sec; + + err = bpf_map_alloc_id(map); + if (err) + goto free_map_sec; + + bpf_map_save_memcg(map); + + return map; + +free_map_sec: + security_bpf_map_free(map); +free_map: + bpf_map_free(map); + return ERR_PTR(err); +} + +int create_and_populate_oracle_map(struct bpf_verifier_env *env) +{ + struct bpf_map *oracle_map; + int err; + + if (env->num_prune_points == 0 || env->subprog_cnt > 1) + return 0; + + oracle_map = create_oracle_map(env); + if (IS_ERR(oracle_map)) + return PTR_ERR(oracle_map); + + err = __add_used_map(env, oracle_map); + if (err < 0) + return err; + + return populate_oracle_map(env, oracle_map); +} diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 74fc568c1bc8..9b39bc2ca7f1 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17560,6 +17560,8 @@ enum { static void mark_prune_point(struct bpf_verifier_env *env, int idx) { + if (!env->insn_aux_data[idx].prune_point) + env->num_prune_points++; env->insn_aux_data[idx].prune_point = true; } @@ -25301,6 +25303,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3 if (ret == 0) ret = do_misc_fixups(env); + if (ret == 0) + ret = create_and_populate_oracle_map(env); + /* do 32-bit optimization after insn patching has done so those patched * insns could be handled correctly. */ -- 2.43.0