xref: /openbmc/qemu/contrib/plugins/cflow.c (revision 2b74dd91)
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 */
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 
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 
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 */
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 
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 n = 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 && n < topn;
166          l = l->next, n++) {
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 
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 
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 
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  */
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  */
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
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