Skip to content

Commit 3860d38

Browse files
borkmannborkmann
committed
Merge branch 'bpf-dedup-fixes'
Andrii Nakryiko says: ==================== This patchset fixes a bug in btf_dedup() algorithm, which under specific hash collision causes infinite loop. It also exposes ability to tune BTF deduplication table size, with double purpose of allowing applications to adjust size according to the size of BTF data, as well as allowing a simple way to force hash collisions by setting table size to 1. - Patch #1 fixes bug in btf_dedup testing code that's checking strings - Patch #2 fixes pointer arg formatting in btf.h - Patch #3 adds option to specify custom dedup table size - Patch #4 fixes aforementioned bug in btf_dedup - Patch #5 adds test that validates the fix v1->v2: - remove "Fixes" from formatting change patch - extract roundup_pow2_max func for dedup table size - btf_equal_struct -> btf_shallow_equal_struct - explain in comment why we can't rely on just btf_dedup_is_equiv ==================== Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
2 parents 3d8669e + 7c7a489 commit 3860d38

File tree

4 files changed

+103
-23
lines changed

4 files changed

+103
-23
lines changed

‎tools/lib/bpf/btf.c

Lines changed: 53 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1070,8 +1070,8 @@ int btf__dedup(struct btf *btf, struct btf_ext *btf_ext,
10701070
return err;
10711071
}
10721072

1073-
#define BTF_DEDUP_TABLE_SIZE_LOG 14
1074-
#define BTF_DEDUP_TABLE_MOD ((1 << BTF_DEDUP_TABLE_SIZE_LOG) - 1)
1073+
#define BTF_DEDUP_TABLE_DEFAULT_SIZE (1 << 14)
1074+
#define BTF_DEDUP_TABLE_MAX_SIZE_LOG 31
10751075
#define BTF_UNPROCESSED_ID ((__u32)-1)
10761076
#define BTF_IN_PROGRESS_ID ((__u32)-2)
10771077

@@ -1128,18 +1128,21 @@ static inline __u32 hash_combine(__u32 h, __u32 value)
11281128
#undef GOLDEN_RATIO_PRIME
11291129
}
11301130

1131-
#define for_each_hash_node(table, hash, node) \
1132-
for (node = table[hash & BTF_DEDUP_TABLE_MOD]; node; node = node->next)
1131+
#define for_each_dedup_cand(d, hash, node) \
1132+
for (node = d->dedup_table[hash & (d->opts.dedup_table_size - 1)]; \
1133+
node; \
1134+
node = node->next)
11331135

11341136
static int btf_dedup_table_add(struct btf_dedup *d, __u32 hash, __u32 type_id)
11351137
{
11361138
struct btf_dedup_node *node = malloc(sizeof(struct btf_dedup_node));
1139+
int bucket = hash & (d->opts.dedup_table_size - 1);
11371140

11381141
if (!node)
11391142
return -ENOMEM;
11401143
node->type_id = type_id;
1141-
node->next = d->dedup_table[hash & BTF_DEDUP_TABLE_MOD];
1142-
d->dedup_table[hash & BTF_DEDUP_TABLE_MOD] = node;
1144+
node->next = d->dedup_table[bucket];
1145+
d->dedup_table[bucket] = node;
11431146
return 0;
11441147
}
11451148

@@ -1177,7 +1180,7 @@ static void btf_dedup_table_free(struct btf_dedup *d)
11771180
if (!d->dedup_table)
11781181
return;
11791182

1180-
for (i = 0; i < (1 << BTF_DEDUP_TABLE_SIZE_LOG); i++) {
1183+
for (i = 0; i < d->opts.dedup_table_size; i++) {
11811184
while (d->dedup_table[i]) {
11821185
tmp = d->dedup_table[i];
11831186
d->dedup_table[i] = tmp->next;
@@ -1212,19 +1215,37 @@ static void btf_dedup_free(struct btf_dedup *d)
12121215
free(d);
12131216
}
12141217

1218+
/* Find closest power of two >= to size, capped at 2^max_size_log */
1219+
static __u32 roundup_pow2_max(__u32 size, int max_size_log)
1220+
{
1221+
int i;
1222+
1223+
for (i = 0; i < max_size_log && (1U << i) < size; i++)
1224+
;
1225+
return 1U << i;
1226+
}
1227+
1228+
12151229
static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
12161230
const struct btf_dedup_opts *opts)
12171231
{
12181232
struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup));
12191233
int i, err = 0;
1234+
__u32 sz;
12201235

12211236
if (!d)
12221237
return ERR_PTR(-ENOMEM);
12231238

1239+
d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds;
1240+
sz = opts && opts->dedup_table_size ? opts->dedup_table_size
1241+
: BTF_DEDUP_TABLE_DEFAULT_SIZE;
1242+
sz = roundup_pow2_max(sz, BTF_DEDUP_TABLE_MAX_SIZE_LOG);
1243+
d->opts.dedup_table_size = sz;
1244+
12241245
d->btf = btf;
12251246
d->btf_ext = btf_ext;
12261247

1227-
d->dedup_table = calloc(1 << BTF_DEDUP_TABLE_SIZE_LOG,
1248+
d->dedup_table = calloc(d->opts.dedup_table_size,
12281249
sizeof(struct btf_dedup_node *));
12291250
if (!d->dedup_table) {
12301251
err = -ENOMEM;
@@ -1249,8 +1270,6 @@ static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
12491270
for (i = 0; i <= btf->nr_types; i++)
12501271
d->hypot_map[i] = BTF_UNPROCESSED_ID;
12511272

1252-
d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds;
1253-
12541273
done:
12551274
if (err) {
12561275
btf_dedup_free(d);
@@ -1644,7 +1663,7 @@ static __u32 btf_hash_struct(struct btf_type *t)
16441663
* IDs. This check is performed during type graph equivalence check and
16451664
* referenced types equivalence is checked separately.
16461665
*/
1647-
static bool btf_equal_struct(struct btf_type *t1, struct btf_type *t2)
1666+
static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
16481667
{
16491668
struct btf_member *m1, *m2;
16501669
__u16 vlen;
@@ -1824,7 +1843,7 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
18241843

18251844
case BTF_KIND_INT:
18261845
h = btf_hash_int(t);
1827-
for_each_hash_node(d->dedup_table, h, cand_node) {
1846+
for_each_dedup_cand(d, h, cand_node) {
18281847
cand = d->btf->types[cand_node->type_id];
18291848
if (btf_equal_int(t, cand)) {
18301849
new_id = cand_node->type_id;
@@ -1835,7 +1854,7 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
18351854

18361855
case BTF_KIND_ENUM:
18371856
h = btf_hash_enum(t);
1838-
for_each_hash_node(d->dedup_table, h, cand_node) {
1857+
for_each_dedup_cand(d, h, cand_node) {
18391858
cand = d->btf->types[cand_node->type_id];
18401859
if (btf_equal_enum(t, cand)) {
18411860
new_id = cand_node->type_id;
@@ -1846,7 +1865,7 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
18461865

18471866
case BTF_KIND_FWD:
18481867
h = btf_hash_common(t);
1849-
for_each_hash_node(d->dedup_table, h, cand_node) {
1868+
for_each_dedup_cand(d, h, cand_node) {
18501869
cand = d->btf->types[cand_node->type_id];
18511870
if (btf_equal_common(t, cand)) {
18521871
new_id = cand_node->type_id;
@@ -2105,7 +2124,7 @@ static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
21052124
struct btf_member *cand_m, *canon_m;
21062125
__u16 vlen;
21072126

2108-
if (!btf_equal_struct(cand_type, canon_type))
2127+
if (!btf_shallow_equal_struct(cand_type, canon_type))
21092128
return 0;
21102129
vlen = BTF_INFO_VLEN(cand_type->info);
21112130
cand_m = (struct btf_member *)(cand_type + 1);
@@ -2246,7 +2265,7 @@ static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
22462265
static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
22472266
{
22482267
struct btf_dedup_node *cand_node;
2249-
struct btf_type *t;
2268+
struct btf_type *cand_type, *t;
22502269
/* if we don't find equivalent type, then we are canonical */
22512270
__u32 new_id = type_id;
22522271
__u16 kind;
@@ -2263,9 +2282,23 @@ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
22632282
return 0;
22642283

22652284
h = btf_hash_struct(t);
2266-
for_each_hash_node(d->dedup_table, h, cand_node) {
2285+
for_each_dedup_cand(d, h, cand_node) {
22672286
int eq;
22682287

2288+
/*
2289+
* Even though btf_dedup_is_equiv() checks for
2290+
* btf_shallow_equal_struct() internally when checking two
2291+
* structs (unions) for equivalence, we need to guard here
2292+
* from picking matching FWD type as a dedup candidate.
2293+
* This can happen due to hash collision. In such case just
2294+
* relying on btf_dedup_is_equiv() would lead to potentially
2295+
* creating a loop (FWD -> STRUCT and STRUCT -> FWD), because
2296+
* FWD and compatible STRUCT/UNION are considered equivalent.
2297+
*/
2298+
cand_type = d->btf->types[cand_node->type_id];
2299+
if (!btf_shallow_equal_struct(t, cand_type))
2300+
continue;
2301+
22692302
btf_dedup_clear_hypot_map(d);
22702303
eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id);
22712304
if (eq < 0)
@@ -2350,7 +2383,7 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
23502383
t->type = ref_type_id;
23512384

23522385
h = btf_hash_common(t);
2353-
for_each_hash_node(d->dedup_table, h, cand_node) {
2386+
for_each_dedup_cand(d, h, cand_node) {
23542387
cand = d->btf->types[cand_node->type_id];
23552388
if (btf_equal_common(t, cand)) {
23562389
new_id = cand_node->type_id;
@@ -2373,7 +2406,7 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
23732406
info->index_type = ref_type_id;
23742407

23752408
h = btf_hash_array(t);
2376-
for_each_hash_node(d->dedup_table, h, cand_node) {
2409+
for_each_dedup_cand(d, h, cand_node) {
23772410
cand = d->btf->types[cand_node->type_id];
23782411
if (btf_equal_array(t, cand)) {
23792412
new_id = cand_node->type_id;
@@ -2404,7 +2437,7 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
24042437
}
24052438

24062439
h = btf_hash_fnproto(t);
2407-
for_each_hash_node(d->dedup_table, h, cand_node) {
2440+
for_each_dedup_cand(d, h, cand_node) {
24082441
cand = d->btf->types[cand_node->type_id];
24092442
if (btf_equal_fnproto(t, cand)) {
24102443
new_id = cand_node->type_id;

‎tools/lib/bpf/btf.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,7 @@ LIBBPF_API int btf__get_map_kv_tids(const struct btf *btf, const char *map_name,
7676

7777
LIBBPF_API struct btf_ext *btf_ext__new(__u8 *data, __u32 size);
7878
LIBBPF_API void btf_ext__free(struct btf_ext *btf_ext);
79-
LIBBPF_API const void *btf_ext__get_raw_data(const struct btf_ext* btf_ext,
79+
LIBBPF_API const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext,
8080
__u32 *size);
8181
LIBBPF_API int btf_ext__reloc_func_info(const struct btf *btf,
8282
const struct btf_ext *btf_ext,
@@ -90,6 +90,7 @@ LIBBPF_API __u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext);
9090
LIBBPF_API __u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext);
9191

9292
struct btf_dedup_opts {
93+
unsigned int dedup_table_size;
9394
bool dont_resolve_fwds;
9495
};
9596

‎tools/testing/selftests/bpf/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ feature
1414
test_libbpf_open
1515
test_sock
1616
test_sock_addr
17+
test_sock_fields
1718
urandom_read
1819
test_btf
1920
test_sockmap

‎tools/testing/selftests/bpf/test_btf.c

Lines changed: 47 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5731,6 +5731,51 @@ const struct btf_dedup_test dedup_tests[] = {
57315731
.dont_resolve_fwds = false,
57325732
},
57335733
},
5734+
{
5735+
.descr = "dedup: struct <-> fwd resolution w/ hash collision",
5736+
/*
5737+
* // CU 1:
5738+
* struct x;
5739+
* struct s {
5740+
* struct x *x;
5741+
* };
5742+
* // CU 2:
5743+
* struct x {};
5744+
* struct s {
5745+
* struct x *x;
5746+
* };
5747+
*/
5748+
.input = {
5749+
.raw_types = {
5750+
/* CU 1 */
5751+
BTF_FWD_ENC(NAME_TBD, 0 /* struct fwd */), /* [1] fwd x */
5752+
BTF_PTR_ENC(1), /* [2] ptr -> [1] */
5753+
BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [3] struct s */
5754+
BTF_MEMBER_ENC(NAME_TBD, 2, 0),
5755+
/* CU 2 */
5756+
BTF_STRUCT_ENC(NAME_TBD, 0, 0), /* [4] struct x */
5757+
BTF_PTR_ENC(4), /* [5] ptr -> [4] */
5758+
BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [6] struct s */
5759+
BTF_MEMBER_ENC(NAME_TBD, 5, 0),
5760+
BTF_END_RAW,
5761+
},
5762+
BTF_STR_SEC("\0x\0s\0x\0x\0s\0x\0"),
5763+
},
5764+
.expect = {
5765+
.raw_types = {
5766+
BTF_PTR_ENC(3), /* [1] ptr -> [3] */
5767+
BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [2] struct s */
5768+
BTF_MEMBER_ENC(NAME_TBD, 1, 0),
5769+
BTF_STRUCT_ENC(NAME_NTH(2), 0, 0), /* [3] struct x */
5770+
BTF_END_RAW,
5771+
},
5772+
BTF_STR_SEC("\0s\0x"),
5773+
},
5774+
.opts = {
5775+
.dont_resolve_fwds = false,
5776+
.dedup_table_size = 1, /* force hash collisions */
5777+
},
5778+
},
57345779
{
57355780
.descr = "dedup: all possible kinds (no duplicates)",
57365781
.input = {
@@ -5936,9 +5981,9 @@ static int do_test_dedup(unsigned int test_num)
59365981
}
59375982

59385983
test_hdr = test_btf_data;
5939-
test_strs = test_btf_data + test_hdr->str_off;
5984+
test_strs = test_btf_data + sizeof(*test_hdr) + test_hdr->str_off;
59405985
expect_hdr = expect_btf_data;
5941-
expect_strs = expect_btf_data + expect_hdr->str_off;
5986+
expect_strs = expect_btf_data + sizeof(*test_hdr) + expect_hdr->str_off;
59425987
if (CHECK(test_hdr->str_len != expect_hdr->str_len,
59435988
"test_hdr->str_len:%u != expect_hdr->str_len:%u",
59445989
test_hdr->str_len, expect_hdr->str_len)) {

0 commit comments

Comments
 (0)