1 /*
2 * Control Flow plugin
3 *
4 * This plugin will track changes to control flow and detect where
5 * instructions fault.
6 *
7 * Copyright (c) 2024 Linaro Ltd
8 *
9 * SPDX-License-Identifier: GPL-2.0-or-later
10 */
11 #include <glib.h>
12 #include <inttypes.h>
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 #include <unistd.h>
17
18 #include <qemu-plugin.h>
19
20 QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
21
22 typedef enum {
23 SORT_HOTTEST, /* hottest branch insn */
24 SORT_EXCEPTION, /* most early exits */
25 SORT_POPDEST, /* most destinations (usually ret's) */
26 } ReportType;
27
28 ReportType report = SORT_HOTTEST;
29 int topn = 10;
30
31 typedef struct {
32 uint64_t daddr;
33 uint64_t dcount;
34 } DestData;
35
36 /* A node is an address where we can go to multiple places */
37 typedef struct {
38 GMutex lock;
39 /* address of the branch point */
40 uint64_t addr;
41 /* array of DestData */
42 GArray *dests;
43 /* early exit/fault count */
44 uint64_t early_exit;
45 /* jump destination count */
46 uint64_t dest_count;
47 /* instruction data */
48 char *insn_disas;
49 /* symbol? */
50 const char *symbol;
51 /* times translated as last in block? */
52 int last_count;
53 /* times translated in the middle of block? */
54 int mid_count;
55 } NodeData;
56
57 typedef enum {
58 /* last insn in block, expected flow control */
59 LAST_INSN = (1 << 0),
60 /* mid-block insn, can only be an exception */
61 EXCP_INSN = (1 << 1),
62 /* multiple disassembly, may have changed */
63 MULT_INSN = (1 << 2),
64 } InsnTypes;
65
66 typedef struct {
67 /* address of the branch point */
68 uint64_t addr;
69 /* disassembly */
70 char *insn_disas;
71 /* symbol? */
72 const char *symbol;
73 /* types */
74 InsnTypes type_flag;
75 } InsnData;
76
77 /* We use this to track the current execution state */
78 typedef struct {
79 /* address of current translated block */
80 uint64_t tb_pc;
81 /* address of end of block */
82 uint64_t end_block;
83 /* next pc after end of block */
84 uint64_t pc_after_block;
85 /* address of last executed PC */
86 uint64_t last_pc;
87 } VCPUScoreBoard;
88
89 /* descriptors for accessing the above scoreboard */
90 static qemu_plugin_u64 tb_pc;
91 static qemu_plugin_u64 end_block;
92 static qemu_plugin_u64 pc_after_block;
93 static qemu_plugin_u64 last_pc;
94
95
96 static GMutex node_lock;
97 static GHashTable *nodes;
98 struct qemu_plugin_scoreboard *state;
99
100 /* SORT_HOTTEST */
hottest(gconstpointer a,gconstpointer b,gpointer d)101 static gint hottest(gconstpointer a, gconstpointer b, gpointer d)
102 {
103 NodeData *na = (NodeData *) a;
104 NodeData *nb = (NodeData *) b;
105
106 return na->dest_count > nb->dest_count ? -1 :
107 na->dest_count == nb->dest_count ? 0 : 1;
108 }
109
exception(gconstpointer a,gconstpointer b,gpointer d)110 static gint exception(gconstpointer a, gconstpointer b, gpointer d)
111 {
112 NodeData *na = (NodeData *) a;
113 NodeData *nb = (NodeData *) b;
114
115 return na->early_exit > nb->early_exit ? -1 :
116 na->early_exit == nb->early_exit ? 0 : 1;
117 }
118
popular(gconstpointer a,gconstpointer b,gpointer d)119 static gint popular(gconstpointer a, gconstpointer b, gpointer d)
120 {
121 NodeData *na = (NodeData *) a;
122 NodeData *nb = (NodeData *) b;
123
124 return na->dests->len > nb->dests->len ? -1 :
125 na->dests->len == nb->dests->len ? 0 : 1;
126 }
127
128 /* Filter out non-branches - returns true to remove entry */
filter_non_branches(gpointer key,gpointer value,gpointer user_data)129 static gboolean filter_non_branches(gpointer key, gpointer value,
130 gpointer user_data)
131 {
132 NodeData *node = (NodeData *) value;
133
134 return node->dest_count == 0;
135 }
136
plugin_exit(qemu_plugin_id_t id,void * p)137 static void plugin_exit(qemu_plugin_id_t id, void *p)
138 {
139 g_autoptr(GString) result = g_string_new("collected ");
140 GList *data;
141 GCompareDataFunc sort = &hottest;
142 int i = 0;
143
144 g_mutex_lock(&node_lock);
145 g_string_append_printf(result, "%d control flow nodes in the hash table\n",
146 g_hash_table_size(nodes));
147
148 /* remove all nodes that didn't branch */
149 g_hash_table_foreach_remove(nodes, filter_non_branches, NULL);
150
151 data = g_hash_table_get_values(nodes);
152
153 switch (report) {
154 case SORT_HOTTEST:
155 sort = &hottest;
156 break;
157 case SORT_EXCEPTION:
158 sort = &exception;
159 break;
160 case SORT_POPDEST:
161 sort = &popular;
162 break;
163 }
164
165 data = g_list_sort_with_data(data, sort, NULL);
166
167 for (GList *l = data;
168 l != NULL && i < topn;
169 l = l->next, i++) {
170 NodeData *n = l->data;
171 const char *type = n->mid_count ? "sync fault" : "branch";
172 g_string_append_printf(result, " addr: 0x%"PRIx64 " %s: %s (%s)\n",
173 n->addr, n->symbol, n->insn_disas, type);
174 if (n->early_exit) {
175 g_string_append_printf(result, " early exits %"PRId64"\n",
176 n->early_exit);
177 }
178 g_string_append_printf(result, " branches %"PRId64"\n",
179 n->dest_count);
180 for (int j = 0; j < n->dests->len; j++) {
181 DestData *dd = &g_array_index(n->dests, DestData, j);
182 g_string_append_printf(result, " to 0x%"PRIx64" (%"PRId64")\n",
183 dd->daddr, dd->dcount);
184 }
185 }
186
187 qemu_plugin_outs(result->str);
188
189 g_mutex_unlock(&node_lock);
190 }
191
plugin_init(void)192 static void plugin_init(void)
193 {
194 g_mutex_init(&node_lock);
195 nodes = g_hash_table_new(g_int64_hash, g_int64_equal);
196 state = qemu_plugin_scoreboard_new(sizeof(VCPUScoreBoard));
197
198 /* score board declarations */
199 tb_pc = qemu_plugin_scoreboard_u64_in_struct(state, VCPUScoreBoard, tb_pc);
200 end_block = qemu_plugin_scoreboard_u64_in_struct(state, VCPUScoreBoard,
201 end_block);
202 pc_after_block = qemu_plugin_scoreboard_u64_in_struct(state, VCPUScoreBoard,
203 pc_after_block);
204 last_pc = qemu_plugin_scoreboard_u64_in_struct(state, VCPUScoreBoard,
205 last_pc);
206 }
207
create_node(uint64_t addr)208 static NodeData *create_node(uint64_t addr)
209 {
210 NodeData *node = g_new0(NodeData, 1);
211 g_mutex_init(&node->lock);
212 node->addr = addr;
213 node->dests = g_array_new(true, true, sizeof(DestData));
214 return node;
215 }
216
fetch_node(uint64_t addr,bool create_if_not_found)217 static NodeData *fetch_node(uint64_t addr, bool create_if_not_found)
218 {
219 NodeData *node = NULL;
220
221 g_mutex_lock(&node_lock);
222 node = (NodeData *) g_hash_table_lookup(nodes, &addr);
223 if (!node && create_if_not_found) {
224 node = create_node(addr);
225 g_hash_table_insert(nodes, &node->addr, node);
226 }
227 g_mutex_unlock(&node_lock);
228 return node;
229 }
230
231 /*
232 * Called when we detect a non-linear execution (pc !=
233 * pc_after_block). This could be due to a fault causing some sort of
234 * exit exception (if last_pc != block_end) or just a taken branch.
235 */
vcpu_tb_branched_exec(unsigned int cpu_index,void * udata)236 static void vcpu_tb_branched_exec(unsigned int cpu_index, void *udata)
237 {
238 uint64_t lpc = qemu_plugin_u64_get(last_pc, cpu_index);
239 uint64_t ebpc = qemu_plugin_u64_get(end_block, cpu_index);
240 uint64_t npc = qemu_plugin_u64_get(pc_after_block, cpu_index);
241 uint64_t pc = qemu_plugin_u64_get(tb_pc, cpu_index);
242
243 /* return early for address 0 */
244 if (!lpc) {
245 return;
246 }
247
248 NodeData *node = fetch_node(lpc, true);
249 DestData *data = NULL;
250 bool early_exit = (lpc != ebpc);
251 GArray *dests;
252
253 /* the condition should never hit */
254 g_assert(pc != npc);
255
256 g_mutex_lock(&node->lock);
257
258 if (early_exit) {
259 fprintf(stderr, "%s: pc=%"PRIx64", epbc=%"PRIx64
260 " npc=%"PRIx64", lpc=%"PRIx64"\n",
261 __func__, pc, ebpc, npc, lpc);
262 node->early_exit++;
263 if (!node->mid_count) {
264 /* count now as we've only just allocated */
265 node->mid_count++;
266 }
267 }
268
269 dests = node->dests;
270 for (int i = 0; i < dests->len; i++) {
271 if (g_array_index(dests, DestData, i).daddr == pc) {
272 data = &g_array_index(dests, DestData, i);
273 }
274 }
275
276 /* we've never seen this before, allocate a new entry */
277 if (!data) {
278 DestData new_entry = { .daddr = pc };
279 g_array_append_val(dests, new_entry);
280 data = &g_array_index(dests, DestData, dests->len - 1);
281 g_assert(data->daddr == pc);
282 }
283
284 data->dcount++;
285 node->dest_count++;
286
287 g_mutex_unlock(&node->lock);
288 }
289
290 /*
291 * At the start of each block we need to resolve two things:
292 *
293 * - is last_pc == block_end, if not we had an early exit
294 * - is start of block last_pc + insn width, if not we jumped
295 *
296 * Once those are dealt with we can instrument the rest of the
297 * instructions for their execution.
298 *
299 */
vcpu_tb_trans(qemu_plugin_id_t id,struct qemu_plugin_tb * tb)300 static void vcpu_tb_trans(qemu_plugin_id_t id, struct qemu_plugin_tb *tb)
301 {
302 uint64_t pc = qemu_plugin_tb_vaddr(tb);
303 size_t insns = qemu_plugin_tb_n_insns(tb);
304 struct qemu_plugin_insn *first_insn = qemu_plugin_tb_get_insn(tb, 0);
305 struct qemu_plugin_insn *last_insn = qemu_plugin_tb_get_insn(tb, insns - 1);
306
307 /*
308 * check if we are executing linearly after the last block. We can
309 * handle both early block exits and normal branches in the
310 * callback if we hit it.
311 */
312 qemu_plugin_register_vcpu_tb_exec_inline_per_vcpu(
313 tb, QEMU_PLUGIN_INLINE_STORE_U64, tb_pc, pc);
314 qemu_plugin_register_vcpu_tb_exec_cond_cb(
315 tb, vcpu_tb_branched_exec, QEMU_PLUGIN_CB_NO_REGS,
316 QEMU_PLUGIN_COND_NE, pc_after_block, pc, NULL);
317
318 /*
319 * Now we can set start/end for this block so the next block can
320 * check where we are at. Do this on the first instruction and not
321 * the TB so we don't get mixed up with above.
322 */
323 qemu_plugin_register_vcpu_insn_exec_inline_per_vcpu(first_insn,
324 QEMU_PLUGIN_INLINE_STORE_U64,
325 end_block, qemu_plugin_insn_vaddr(last_insn));
326 qemu_plugin_register_vcpu_insn_exec_inline_per_vcpu(first_insn,
327 QEMU_PLUGIN_INLINE_STORE_U64,
328 pc_after_block,
329 qemu_plugin_insn_vaddr(last_insn) +
330 qemu_plugin_insn_size(last_insn));
331
332 for (int idx = 0; idx < qemu_plugin_tb_n_insns(tb); ++idx) {
333 struct qemu_plugin_insn *insn = qemu_plugin_tb_get_insn(tb, idx);
334 uint64_t ipc = qemu_plugin_insn_vaddr(insn);
335 /*
336 * If this is a potential branch point check if we could grab
337 * the disassembly for it. If it is the last instruction
338 * always create an entry.
339 */
340 NodeData *node = fetch_node(ipc, last_insn);
341 if (node) {
342 g_mutex_lock(&node->lock);
343 if (!node->insn_disas) {
344 node->insn_disas = qemu_plugin_insn_disas(insn);
345 }
346 if (!node->symbol) {
347 node->symbol = qemu_plugin_insn_symbol(insn);
348 }
349 if (last_insn == insn) {
350 node->last_count++;
351 } else {
352 node->mid_count++;
353 }
354 g_mutex_unlock(&node->lock);
355 }
356
357 /* Store the PC of what we are about to execute */
358 qemu_plugin_register_vcpu_insn_exec_inline_per_vcpu(insn,
359 QEMU_PLUGIN_INLINE_STORE_U64,
360 last_pc, ipc);
361 }
362 }
363
364 QEMU_PLUGIN_EXPORT
qemu_plugin_install(qemu_plugin_id_t id,const qemu_info_t * info,int argc,char ** argv)365 int qemu_plugin_install(qemu_plugin_id_t id, const qemu_info_t *info,
366 int argc, char **argv)
367 {
368 for (int i = 0; i < argc; i++) {
369 char *opt = argv[i];
370 g_auto(GStrv) tokens = g_strsplit(opt, "=", 2);
371 if (g_strcmp0(tokens[0], "sort") == 0) {
372 if (g_strcmp0(tokens[1], "hottest") == 0) {
373 report = SORT_HOTTEST;
374 } else if (g_strcmp0(tokens[1], "early") == 0) {
375 report = SORT_EXCEPTION;
376 } else if (g_strcmp0(tokens[1], "exceptions") == 0) {
377 report = SORT_POPDEST;
378 } else {
379 fprintf(stderr, "failed to parse: %s\n", tokens[1]);
380 return -1;
381 }
382 } else {
383 fprintf(stderr, "option parsing failed: %s\n", opt);
384 return -1;
385 }
386 }
387
388 plugin_init();
389
390 qemu_plugin_register_vcpu_tb_trans_cb(id, vcpu_tb_trans);
391 qemu_plugin_register_atexit_cb(id, plugin_exit, NULL);
392 return 0;
393 }
394