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