Lines Matching refs:d
3407 static void btf_dedup_free(struct btf_dedup *d);
3408 static int btf_dedup_prep(struct btf_dedup *d);
3409 static int btf_dedup_strings(struct btf_dedup *d);
3410 static int btf_dedup_prim_types(struct btf_dedup *d);
3411 static int btf_dedup_struct_types(struct btf_dedup *d);
3412 static int btf_dedup_ref_types(struct btf_dedup *d);
3413 static int btf_dedup_resolve_fwds(struct btf_dedup *d);
3414 static int btf_dedup_compact_types(struct btf_dedup *d);
3415 static int btf_dedup_remap_types(struct btf_dedup *d);
3557 struct btf_dedup *d; in btf__dedup() local
3563 d = btf_dedup_new(btf, opts); in btf__dedup()
3564 if (IS_ERR(d)) { in btf__dedup()
3565 pr_debug("btf_dedup_new failed: %ld\n", PTR_ERR(d)); in btf__dedup()
3574 err = btf_dedup_prep(d); in btf__dedup()
3579 err = btf_dedup_strings(d); in btf__dedup()
3584 err = btf_dedup_prim_types(d); in btf__dedup()
3589 err = btf_dedup_struct_types(d); in btf__dedup()
3594 err = btf_dedup_resolve_fwds(d); in btf__dedup()
3599 err = btf_dedup_ref_types(d); in btf__dedup()
3604 err = btf_dedup_compact_types(d); in btf__dedup()
3609 err = btf_dedup_remap_types(d); in btf__dedup()
3616 btf_dedup_free(d); in btf__dedup()
3664 #define for_each_dedup_cand(d, node, hash) \ argument
3665 hashmap__for_each_key_entry(d->dedup_table, node, hash)
3667 static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id) in btf_dedup_table_add() argument
3669 return hashmap__append(d->dedup_table, hash, type_id); in btf_dedup_table_add()
3672 static int btf_dedup_hypot_map_add(struct btf_dedup *d, in btf_dedup_hypot_map_add() argument
3675 if (d->hypot_cnt == d->hypot_cap) { in btf_dedup_hypot_map_add()
3678 d->hypot_cap += max((size_t)16, d->hypot_cap / 2); in btf_dedup_hypot_map_add()
3679 new_list = libbpf_reallocarray(d->hypot_list, d->hypot_cap, sizeof(__u32)); in btf_dedup_hypot_map_add()
3682 d->hypot_list = new_list; in btf_dedup_hypot_map_add()
3684 d->hypot_list[d->hypot_cnt++] = from_id; in btf_dedup_hypot_map_add()
3685 d->hypot_map[from_id] = to_id; in btf_dedup_hypot_map_add()
3689 static void btf_dedup_clear_hypot_map(struct btf_dedup *d) in btf_dedup_clear_hypot_map() argument
3693 for (i = 0; i < d->hypot_cnt; i++) in btf_dedup_clear_hypot_map()
3694 d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID; in btf_dedup_clear_hypot_map()
3695 d->hypot_cnt = 0; in btf_dedup_clear_hypot_map()
3696 d->hypot_adjust_canon = false; in btf_dedup_clear_hypot_map()
3699 static void btf_dedup_free(struct btf_dedup *d) in btf_dedup_free() argument
3701 hashmap__free(d->dedup_table); in btf_dedup_free()
3702 d->dedup_table = NULL; in btf_dedup_free()
3704 free(d->map); in btf_dedup_free()
3705 d->map = NULL; in btf_dedup_free()
3707 free(d->hypot_map); in btf_dedup_free()
3708 d->hypot_map = NULL; in btf_dedup_free()
3710 free(d->hypot_list); in btf_dedup_free()
3711 d->hypot_list = NULL; in btf_dedup_free()
3713 free(d); in btf_dedup_free()
3733 struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup)); in btf_dedup_new() local
3737 if (!d) in btf_dedup_new()
3743 d->btf = btf; in btf_dedup_new()
3744 d->btf_ext = OPTS_GET(opts, btf_ext, NULL); in btf_dedup_new()
3746 d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL); in btf_dedup_new()
3747 if (IS_ERR(d->dedup_table)) { in btf_dedup_new()
3748 err = PTR_ERR(d->dedup_table); in btf_dedup_new()
3749 d->dedup_table = NULL; in btf_dedup_new()
3754 d->map = malloc(sizeof(__u32) * type_cnt); in btf_dedup_new()
3755 if (!d->map) { in btf_dedup_new()
3760 d->map[0] = 0; in btf_dedup_new()
3762 struct btf_type *t = btf_type_by_id(d->btf, i); in btf_dedup_new()
3766 d->map[i] = i; in btf_dedup_new()
3768 d->map[i] = BTF_UNPROCESSED_ID; in btf_dedup_new()
3771 d->hypot_map = malloc(sizeof(__u32) * type_cnt); in btf_dedup_new()
3772 if (!d->hypot_map) { in btf_dedup_new()
3777 d->hypot_map[i] = BTF_UNPROCESSED_ID; in btf_dedup_new()
3781 btf_dedup_free(d); in btf_dedup_new()
3785 return d; in btf_dedup_new()
3792 static int btf_for_each_str_off(struct btf_dedup *d, str_off_visit_fn fn, void *ctx) in btf_for_each_str_off() argument
3796 for (i = 0; i < d->btf->nr_types; i++) { in btf_for_each_str_off()
3798 struct btf_type *t = btf_type_by_id(d->btf, d->btf->start_id + i); in btf_for_each_str_off()
3812 if (!d->btf_ext) in btf_for_each_str_off()
3815 r = btf_ext_visit_str_offs(d->btf_ext, fn, ctx); in btf_for_each_str_off()
3824 struct btf_dedup *d = ctx; in strs_dedup_remap_str_off() local
3830 if (str_off == 0 || str_off < d->btf->start_str_off) in strs_dedup_remap_str_off()
3833 s = btf__str_by_offset(d->btf, str_off); in strs_dedup_remap_str_off()
3834 if (d->btf->base_btf) { in strs_dedup_remap_str_off()
3835 err = btf__find_str(d->btf->base_btf, s); in strs_dedup_remap_str_off()
3844 off = strset__add_str(d->strs_set, s); in strs_dedup_remap_str_off()
3848 *str_off_ptr = d->btf->start_str_off + off; in strs_dedup_remap_str_off()
3863 static int btf_dedup_strings(struct btf_dedup *d) in btf_dedup_strings() argument
3867 if (d->btf->strs_deduped) in btf_dedup_strings()
3870 d->strs_set = strset__new(BTF_MAX_STR_OFFSET, NULL, 0); in btf_dedup_strings()
3871 if (IS_ERR(d->strs_set)) { in btf_dedup_strings()
3872 err = PTR_ERR(d->strs_set); in btf_dedup_strings()
3876 if (!d->btf->base_btf) { in btf_dedup_strings()
3880 err = strset__add_str(d->strs_set, ""); in btf_dedup_strings()
3886 err = btf_for_each_str_off(d, strs_dedup_remap_str_off, d); in btf_dedup_strings()
3891 strset__free(d->btf->strs_set); in btf_dedup_strings()
3892 d->btf->hdr->str_len = strset__data_size(d->strs_set); in btf_dedup_strings()
3893 d->btf->strs_set = d->strs_set; in btf_dedup_strings()
3894 d->strs_set = NULL; in btf_dedup_strings()
3895 d->btf->strs_deduped = true; in btf_dedup_strings()
3899 strset__free(d->strs_set); in btf_dedup_strings()
3900 d->strs_set = NULL; in btf_dedup_strings()
4200 static int btf_dedup_prep(struct btf_dedup *d) in btf_dedup_prep() argument
4206 if (!d->btf->base_btf) in btf_dedup_prep()
4209 for (type_id = 1; type_id < d->btf->start_id; type_id++) { in btf_dedup_prep()
4210 t = btf_type_by_id(d->btf, type_id); in btf_dedup_prep()
4213 d->map[type_id] = type_id; in btf_dedup_prep()
4253 if (btf_dedup_table_add(d, h, type_id)) in btf_dedup_prep()
4266 static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) in btf_dedup_prim_type() argument
4268 struct btf_type *t = btf_type_by_id(d->btf, type_id); in btf_dedup_prim_type()
4295 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_prim_type()
4297 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_prim_type()
4308 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_prim_type()
4310 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_prim_type()
4322 d->map[cand_id] = type_id; in btf_dedup_prim_type()
4330 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_prim_type()
4332 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_prim_type()
4344 d->map[type_id] = new_id; in btf_dedup_prim_type()
4345 if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) in btf_dedup_prim_type()
4351 static int btf_dedup_prim_types(struct btf_dedup *d) in btf_dedup_prim_types() argument
4355 for (i = 0; i < d->btf->nr_types; i++) { in btf_dedup_prim_types()
4356 err = btf_dedup_prim_type(d, d->btf->start_id + i); in btf_dedup_prim_types()
4366 static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id) in is_type_mapped() argument
4368 return d->map[type_id] <= BTF_MAX_NR_TYPES; in is_type_mapped()
4376 static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id) in resolve_type_id() argument
4378 while (is_type_mapped(d, type_id) && d->map[type_id] != type_id) in resolve_type_id()
4379 type_id = d->map[type_id]; in resolve_type_id()
4387 static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id) in resolve_fwd_id() argument
4391 if (!btf_is_fwd(btf__type_by_id(d->btf, type_id))) in resolve_fwd_id()
4394 while (is_type_mapped(d, type_id) && d->map[type_id] != type_id) in resolve_fwd_id()
4395 type_id = d->map[type_id]; in resolve_fwd_id()
4397 if (!btf_is_fwd(btf__type_by_id(d->btf, type_id))) in resolve_fwd_id()
4409 static bool btf_dedup_identical_types(struct btf_dedup *d, __u32 id1, __u32 id2, int depth) in btf_dedup_identical_types() argument
4417 t1 = btf_type_by_id(d->btf, id1); in btf_dedup_identical_types()
4418 t2 = btf_type_by_id(d->btf, id2); in btf_dedup_identical_types()
4458 !btf_dedup_identical_types(d, a1->index_type, a2->index_type, depth - 1)) in btf_dedup_identical_types()
4462 !btf_dedup_identical_types(d, a1->type, a2->type, depth - 1)) in btf_dedup_identical_types()
4480 if (!btf_dedup_identical_types(d, m1->type, m2->type, depth - 1)) in btf_dedup_identical_types()
4493 !btf_dedup_identical_types(d, t1->type, t2->type, depth - 1)) in btf_dedup_identical_types()
4501 if (!btf_dedup_identical_types(d, p1->type, p2->type, depth - 1)) in btf_dedup_identical_types()
4605 static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id, in btf_dedup_is_equiv() argument
4616 if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id)) in btf_dedup_is_equiv()
4619 canon_id = resolve_fwd_id(d, canon_id); in btf_dedup_is_equiv()
4621 hypot_type_id = d->hypot_map[canon_id]; in btf_dedup_is_equiv()
4636 if (btf_dedup_identical_types(d, hypot_type_id, cand_id, 16)) in btf_dedup_is_equiv()
4641 if (btf_dedup_hypot_map_add(d, canon_id, cand_id)) in btf_dedup_is_equiv()
4644 cand_type = btf_type_by_id(d->btf, cand_id); in btf_dedup_is_equiv()
4645 canon_type = btf_type_by_id(d->btf, canon_id); in btf_dedup_is_equiv()
4665 if (fwd_kind == real_kind && canon_id < d->btf->start_id) in btf_dedup_is_equiv()
4666 d->hypot_adjust_canon = true; in btf_dedup_is_equiv()
4695 return btf_dedup_is_equiv(d, cand_type->type, canon_type->type); in btf_dedup_is_equiv()
4704 eq = btf_dedup_is_equiv(d, cand_arr->index_type, canon_arr->index_type); in btf_dedup_is_equiv()
4707 return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type); in btf_dedup_is_equiv()
4721 eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type); in btf_dedup_is_equiv()
4737 eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type); in btf_dedup_is_equiv()
4744 eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type); in btf_dedup_is_equiv()
4785 static void btf_dedup_merge_hypot_map(struct btf_dedup *d) in btf_dedup_merge_hypot_map() argument
4792 for (i = 0; i < d->hypot_cnt; i++) { in btf_dedup_merge_hypot_map()
4793 canon_type_id = d->hypot_list[i]; in btf_dedup_merge_hypot_map()
4794 targ_type_id = d->hypot_map[canon_type_id]; in btf_dedup_merge_hypot_map()
4795 t_id = resolve_type_id(d, targ_type_id); in btf_dedup_merge_hypot_map()
4796 c_id = resolve_type_id(d, canon_type_id); in btf_dedup_merge_hypot_map()
4797 t_kind = btf_kind(btf__type_by_id(d->btf, t_id)); in btf_dedup_merge_hypot_map()
4798 c_kind = btf_kind(btf__type_by_id(d->btf, c_id)); in btf_dedup_merge_hypot_map()
4820 d->map[c_id] = t_id; in btf_dedup_merge_hypot_map()
4827 if (d->hypot_adjust_canon) in btf_dedup_merge_hypot_map()
4831 d->map[t_id] = c_id; in btf_dedup_merge_hypot_map()
4835 is_type_mapped(d, c_id) && in btf_dedup_merge_hypot_map()
4836 !is_type_mapped(d, t_id)) { in btf_dedup_merge_hypot_map()
4843 d->map[t_id] = c_id; in btf_dedup_merge_hypot_map()
4870 static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) in btf_dedup_struct_type() argument
4880 if (d->map[type_id] <= BTF_MAX_NR_TYPES) in btf_dedup_struct_type()
4883 t = btf_type_by_id(d->btf, type_id); in btf_dedup_struct_type()
4890 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_struct_type()
4904 cand_type = btf_type_by_id(d->btf, cand_id); in btf_dedup_struct_type()
4908 btf_dedup_clear_hypot_map(d); in btf_dedup_struct_type()
4909 eq = btf_dedup_is_equiv(d, type_id, cand_id); in btf_dedup_struct_type()
4914 btf_dedup_merge_hypot_map(d); in btf_dedup_struct_type()
4915 if (d->hypot_adjust_canon) /* not really equivalent */ in btf_dedup_struct_type()
4921 d->map[type_id] = new_id; in btf_dedup_struct_type()
4922 if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) in btf_dedup_struct_type()
4928 static int btf_dedup_struct_types(struct btf_dedup *d) in btf_dedup_struct_types() argument
4932 for (i = 0; i < d->btf->nr_types; i++) { in btf_dedup_struct_types()
4933 err = btf_dedup_struct_type(d, d->btf->start_id + i); in btf_dedup_struct_types()
4964 static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) in btf_dedup_ref_type() argument
4973 if (d->map[type_id] == BTF_IN_PROGRESS_ID) in btf_dedup_ref_type()
4975 if (d->map[type_id] <= BTF_MAX_NR_TYPES) in btf_dedup_ref_type()
4976 return resolve_type_id(d, type_id); in btf_dedup_ref_type()
4978 t = btf_type_by_id(d->btf, type_id); in btf_dedup_ref_type()
4979 d->map[type_id] = BTF_IN_PROGRESS_ID; in btf_dedup_ref_type()
4989 ref_type_id = btf_dedup_ref_type(d, t->type); in btf_dedup_ref_type()
4995 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_ref_type()
4997 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_ref_type()
5006 ref_type_id = btf_dedup_ref_type(d, t->type); in btf_dedup_ref_type()
5012 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_ref_type()
5014 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_ref_type()
5025 ref_type_id = btf_dedup_ref_type(d, info->type); in btf_dedup_ref_type()
5030 ref_type_id = btf_dedup_ref_type(d, info->index_type); in btf_dedup_ref_type()
5036 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_ref_type()
5038 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_ref_type()
5052 ref_type_id = btf_dedup_ref_type(d, t->type); in btf_dedup_ref_type()
5060 ref_type_id = btf_dedup_ref_type(d, param->type); in btf_dedup_ref_type()
5068 for_each_dedup_cand(d, hash_entry, h) { in btf_dedup_ref_type()
5070 cand = btf_type_by_id(d->btf, cand_id); in btf_dedup_ref_type()
5083 d->map[type_id] = new_id; in btf_dedup_ref_type()
5084 if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) in btf_dedup_ref_type()
5090 static int btf_dedup_ref_types(struct btf_dedup *d) in btf_dedup_ref_types() argument
5094 for (i = 0; i < d->btf->nr_types; i++) { in btf_dedup_ref_types()
5095 err = btf_dedup_ref_type(d, d->btf->start_id + i); in btf_dedup_ref_types()
5100 hashmap__free(d->dedup_table); in btf_dedup_ref_types()
5101 d->dedup_table = NULL; in btf_dedup_ref_types()
5110 static int btf_dedup_fill_unique_names_map(struct btf_dedup *d, struct hashmap *names_map) in btf_dedup_fill_unique_names_map() argument
5112 __u32 nr_types = btf__type_cnt(d->btf); in btf_dedup_fill_unique_names_map()
5123 t = btf_type_by_id(d->btf, type_id); in btf_dedup_fill_unique_names_map()
5130 if (type_id != d->map[type_id]) in btf_dedup_fill_unique_names_map()
5144 static int btf_dedup_resolve_fwd(struct btf_dedup *d, struct hashmap *names_map, __u32 type_id) in btf_dedup_resolve_fwd() argument
5146 struct btf_type *t = btf_type_by_id(d->btf, type_id); in btf_dedup_resolve_fwd()
5156 if (type_id != d->map[type_id]) in btf_dedup_resolve_fwd()
5166 cand_t = btf_type_by_id(d->btf, cand_id); in btf_dedup_resolve_fwd()
5172 d->map[type_id] = cand_id; in btf_dedup_resolve_fwd()
5209 static int btf_dedup_resolve_fwds(struct btf_dedup *d) in btf_dedup_resolve_fwds() argument
5218 err = btf_dedup_fill_unique_names_map(d, names_map); in btf_dedup_resolve_fwds()
5222 for (i = 0; i < d->btf->nr_types; i++) { in btf_dedup_resolve_fwds()
5223 err = btf_dedup_resolve_fwd(d, names_map, d->btf->start_id + i); in btf_dedup_resolve_fwds()
5244 static int btf_dedup_compact_types(struct btf_dedup *d) in btf_dedup_compact_types() argument
5247 __u32 next_type_id = d->btf->start_id; in btf_dedup_compact_types()
5253 d->hypot_map[0] = 0; in btf_dedup_compact_types()
5255 for (id = 1; id < d->btf->start_id; id++) in btf_dedup_compact_types()
5256 d->hypot_map[id] = id; in btf_dedup_compact_types()
5257 for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) in btf_dedup_compact_types()
5258 d->hypot_map[id] = BTF_UNPROCESSED_ID; in btf_dedup_compact_types()
5260 p = d->btf->types_data; in btf_dedup_compact_types()
5262 for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) { in btf_dedup_compact_types()
5263 if (d->map[id] != id) in btf_dedup_compact_types()
5266 t = btf__type_by_id(d->btf, id); in btf_dedup_compact_types()
5272 d->hypot_map[id] = next_type_id; in btf_dedup_compact_types()
5273 d->btf->type_offs[next_type_id - d->btf->start_id] = p - d->btf->types_data; in btf_dedup_compact_types()
5279 d->btf->nr_types = next_type_id - d->btf->start_id; in btf_dedup_compact_types()
5280 d->btf->type_offs_cap = d->btf->nr_types; in btf_dedup_compact_types()
5281 d->btf->hdr->type_len = p - d->btf->types_data; in btf_dedup_compact_types()
5282 new_offs = libbpf_reallocarray(d->btf->type_offs, d->btf->type_offs_cap, in btf_dedup_compact_types()
5284 if (d->btf->type_offs_cap && !new_offs) in btf_dedup_compact_types()
5286 d->btf->type_offs = new_offs; in btf_dedup_compact_types()
5287 d->btf->hdr->str_off = d->btf->hdr->type_len; in btf_dedup_compact_types()
5288 d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len; in btf_dedup_compact_types()
5300 struct btf_dedup *d = ctx; in btf_dedup_remap_type_id() local
5303 resolved_type_id = resolve_type_id(d, *type_id); in btf_dedup_remap_type_id()
5304 new_type_id = d->hypot_map[resolved_type_id]; in btf_dedup_remap_type_id()
5322 static int btf_dedup_remap_types(struct btf_dedup *d) in btf_dedup_remap_types() argument
5326 for (i = 0; i < d->btf->nr_types; i++) { in btf_dedup_remap_types()
5327 struct btf_type *t = btf_type_by_id(d->btf, d->btf->start_id + i); in btf_dedup_remap_types()
5338 resolved_id = resolve_type_id(d, *type_id); in btf_dedup_remap_types()
5339 new_id = d->hypot_map[resolved_id]; in btf_dedup_remap_types()
5347 if (!d->btf_ext) in btf_dedup_remap_types()
5350 r = btf_ext_visit_type_ids(d->btf_ext, btf_dedup_remap_type_id, d); in btf_dedup_remap_types()