1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (C) 2024 Google LLC
4 */
5
6 #include <string.h>
7 #include "gendwarfksyms.h"
8
9 #define DIE_HASH_BITS 15
10
11 /* {die->addr, state} -> struct die * */
12 static HASHTABLE_DEFINE(die_map, 1 << DIE_HASH_BITS);
13
14 static unsigned int map_hits;
15 static unsigned int map_misses;
16
die_hash(uintptr_t addr,enum die_state state)17 static inline unsigned int die_hash(uintptr_t addr, enum die_state state)
18 {
19 return hash_32(addr_hash(addr) ^ (unsigned int)state);
20 }
21
init_die(struct die * cd)22 static void init_die(struct die *cd)
23 {
24 cd->state = DIE_INCOMPLETE;
25 cd->mapped = false;
26 cd->fqn = NULL;
27 cd->tag = -1;
28 cd->addr = 0;
29 INIT_LIST_HEAD(&cd->fragments);
30 }
31
create_die(Dwarf_Die * die,enum die_state state)32 static struct die *create_die(Dwarf_Die *die, enum die_state state)
33 {
34 struct die *cd;
35
36 cd = xmalloc(sizeof(struct die));
37 init_die(cd);
38 cd->addr = (uintptr_t)die->addr;
39
40 hash_add(die_map, &cd->hash, die_hash(cd->addr, state));
41 return cd;
42 }
43
__die_map_get(uintptr_t addr,enum die_state state,struct die ** res)44 int __die_map_get(uintptr_t addr, enum die_state state, struct die **res)
45 {
46 struct die *cd;
47
48 hash_for_each_possible(die_map, cd, hash, die_hash(addr, state)) {
49 if (cd->addr == addr && cd->state == state) {
50 *res = cd;
51 return 0;
52 }
53 }
54
55 return -1;
56 }
57
die_map_get(Dwarf_Die * die,enum die_state state)58 struct die *die_map_get(Dwarf_Die *die, enum die_state state)
59 {
60 struct die *cd;
61
62 if (__die_map_get((uintptr_t)die->addr, state, &cd) == 0) {
63 map_hits++;
64 return cd;
65 }
66
67 map_misses++;
68 return create_die(die, state);
69 }
70
reset_die(struct die * cd)71 static void reset_die(struct die *cd)
72 {
73 struct die_fragment *tmp;
74 struct die_fragment *df;
75
76 list_for_each_entry_safe(df, tmp, &cd->fragments, list) {
77 if (df->type == FRAGMENT_STRING)
78 free(df->data.str);
79 free(df);
80 }
81
82 if (cd->fqn && *cd->fqn)
83 free(cd->fqn);
84 init_die(cd);
85 }
86
die_map_for_each(die_map_callback_t func,void * arg)87 void die_map_for_each(die_map_callback_t func, void *arg)
88 {
89 struct hlist_node *tmp;
90 struct die *cd;
91
92 hash_for_each_safe(die_map, cd, tmp, hash) {
93 func(cd, arg);
94 }
95 }
96
die_map_free(void)97 void die_map_free(void)
98 {
99 struct hlist_node *tmp;
100 unsigned int stats[DIE_LAST + 1];
101 struct die *cd;
102 int i;
103
104 memset(stats, 0, sizeof(stats));
105
106 hash_for_each_safe(die_map, cd, tmp, hash) {
107 stats[cd->state]++;
108 reset_die(cd);
109 free(cd);
110 }
111 hash_init(die_map);
112
113 if (map_hits + map_misses > 0)
114 debug("hits %u, misses %u (hit rate %.02f%%)", map_hits,
115 map_misses,
116 (100.0f * map_hits) / (map_hits + map_misses));
117
118 for (i = 0; i <= DIE_LAST; i++)
119 debug("%s: %u entries", die_state_name(i), stats[i]);
120 }
121
append_item(struct die * cd)122 static struct die_fragment *append_item(struct die *cd)
123 {
124 struct die_fragment *df;
125
126 df = xmalloc(sizeof(struct die_fragment));
127 df->type = FRAGMENT_EMPTY;
128 list_add_tail(&df->list, &cd->fragments);
129 return df;
130 }
131
die_map_add_string(struct die * cd,const char * str)132 void die_map_add_string(struct die *cd, const char *str)
133 {
134 struct die_fragment *df;
135
136 if (!cd)
137 return;
138
139 df = append_item(cd);
140 df->data.str = xstrdup(str);
141 df->type = FRAGMENT_STRING;
142 }
143
die_map_add_linebreak(struct die * cd,int linebreak)144 void die_map_add_linebreak(struct die *cd, int linebreak)
145 {
146 struct die_fragment *df;
147
148 if (!cd)
149 return;
150
151 df = append_item(cd);
152 df->data.linebreak = linebreak;
153 df->type = FRAGMENT_LINEBREAK;
154 }
155
die_map_add_die(struct die * cd,struct die * child)156 void die_map_add_die(struct die *cd, struct die *child)
157 {
158 struct die_fragment *df;
159
160 if (!cd)
161 return;
162
163 df = append_item(cd);
164 df->data.addr = child->addr;
165 df->type = FRAGMENT_DIE;
166 }
167