util/cbmem: Add FlameGraph-compatible timestamps output

Flame graphs are used to visualize hierarchical data, like call stacks.
Timestamps collected by coreboot can be processed to resemble
profiler-like output, and thus can be feed to flame graph generation
tools.

Generating flame graph using https://github.com/brendangregg/FlameGraph:
  cbmem -S > trace.txt
  FlameGraph/flamegraph.pl --flamechart trace.txt > output.svg

TEST=Run on coreboot-enabled device and extract timestamps using
     -t/-T/-S options

Signed-off-by: Jakub Czapiga <jacz@semihalf.com>
Change-Id: I3a4e20a267e9e0fbc6b3a4d6a2409b32ce8fca33
Reviewed-on: https://review.coreboot.org/c/coreboot/+/62474
Tested-by: build bot (Jenkins) <no-reply@coreboot.org>
Reviewed-by: Julius Werner <jwerner@chromium.org>

1 files changed, 117 insertions, 21 deletions

diff --git a/util/cbmem/cbmem.c b/util/cbmem/cbmem.c
index 0fd69d6e06..5b969e4b8b 100644
--- a/util/cbmem/cbmem.c
+++ b/util/cbmem/cbmem.c
@@ -1,6 +1,7 @@
 /* SPDX-License-Identifier: GPL-2.0-only */
 
 #include <inttypes.h>
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -590,14 +591,72 @@ static int compare_timestamp_entries(const void *a, const void *b)
 	return 0;
 }
 
+static int find_matching_end(struct timestamp_table *sorted_tst_p, uint32_t start, uint32_t end)
+{
+	uint32_t id = sorted_tst_p->entries[start].entry_id;
+	uint32_t possible_match = 0;
+
+	for (uint32_t i = 0; i < ARRAY_SIZE(timestamp_ids); ++i) {
+		if (timestamp_ids[i].id == id) {
+			possible_match = timestamp_ids[i].id_end;
+			break;
+		}
+	}
+
+	/* No match found or timestamp not defined in IDs table */
+	if (!possible_match)
+		return -1;
+
+	for (uint32_t i = start + 1; i < end; i++)
+		if (sorted_tst_p->entries[i].entry_id == possible_match)
+			return i;
+
+	return -1;
+}
+
+static const char *get_timestamp_name(const uint32_t id)
+{
+	for (uint32_t i = 0; i < ARRAY_SIZE(timestamp_ids); i++)
+		if (timestamp_ids[i].id == id)
+			return timestamp_ids[i].enum_name;
+
+	return "UNKNOWN";
+}
+
+struct ts_range_stack {
+	const char *name;
+	const char *end_name;
+	uint32_t end;
+};
+
+static void print_with_path(struct ts_range_stack *range_stack, const int stacklvl,
+			    const uint64_t stamp, const char *last_part)
+{
+	for (int i = 1; i <= stacklvl; ++i) {
+		printf("%s -> %s", range_stack[i].name, range_stack[i].end_name);
+		if (i < stacklvl || last_part)
+			putchar(';');
+	}
+	if (last_part)
+		printf("%s", last_part);
+	printf(" %lu\n", arch_convert_raw_ts_entry(stamp));
+}
+
+enum timestamps_print_type {
+	TIMESTAMPS_PRINT_NONE,
+	TIMESTAMPS_PRINT_NORMAL,
+	TIMESTAMPS_PRINT_MACHINE_READABLE,
+	TIMESTAMPS_PRINT_STACKED,
+};
+
 /* dump the timestamp table */
-static void dump_timestamps(int mach_readable)
+static void dump_timestamps(enum timestamps_print_type output_type)
 {
 	const struct timestamp_table *tst_p;
 	struct timestamp_table *sorted_tst_p;
 	size_t size;
-	uint64_t prev_stamp;
-	uint64_t total_time;
+	uint64_t prev_stamp = 0;
+	uint64_t total_time = 0;
 	struct mapping timestamp_mapping;
 
 	if (timestamps.tag != LB_TAG_TIMESTAMPS) {
@@ -612,7 +671,7 @@ static void dump_timestamps(int mach_readable)
 
 	timestamp_set_tick_freq(tst_p->tick_freq_mhz);
 
-	if (!mach_readable)
+	if (output_type == TIMESTAMPS_PRINT_NORMAL)
 		printf("%d entries total:\n\n", tst_p->num_entries);
 	size += tst_p->num_entries * sizeof(tst_p->entries[0]);
 
@@ -649,24 +708,54 @@ static void dump_timestamps(int mach_readable)
 		prev_stamp = tst_p->base_time;
 	}
 
-	total_time = 0;
+	struct ts_range_stack range_stack[20];
+	range_stack[0].end = sorted_tst_p->num_entries;
+	int stacklvl = 0;
+
 	for (uint32_t i = 0; i < sorted_tst_p->num_entries; i++) {
 		uint64_t stamp;
 		const struct timestamp_entry *tse = &sorted_tst_p->entries[i];
 
 		/* Make all timestamps absolute. */
 		stamp = tse->entry_stamp + sorted_tst_p->base_time;
-		if (mach_readable)
-			total_time +=
-				timestamp_print_parseable_entry(tse->entry_id,
-							stamp, prev_stamp);
-		else
-			total_time += timestamp_print_entry(tse->entry_id,
-							stamp, prev_stamp);
+		if (output_type == TIMESTAMPS_PRINT_MACHINE_READABLE) {
+			timestamp_print_parseable_entry(tse->entry_id, stamp, prev_stamp);
+		} else if (output_type == TIMESTAMPS_PRINT_NORMAL) {
+			total_time += timestamp_print_entry(tse->entry_id, stamp, prev_stamp);
+		} else if (output_type == TIMESTAMPS_PRINT_STACKED) {
+			bool end_of_range = false;
+			/* Iterate over stacked entries to pop all ranges, which are closed by
+			   current element. For example, assuming two ranges: (TS_A, TS_C),
+			   (TS_B, TS_C) it will pop all of them instead of just last one. */
+			while (stacklvl > 0 && range_stack[stacklvl].end == i) {
+				end_of_range = true;
+				stacklvl--;
+			}
+
+			int match =
+				find_matching_end(sorted_tst_p, i, range_stack[stacklvl].end);
+			if (match != -1) {
+				const uint64_t match_stamp =
+					sorted_tst_p->entries[match].entry_stamp
+					+ sorted_tst_p->base_time;
+				stacklvl++;
+				assert(stacklvl < (int)ARRAY_SIZE(range_stack));
+				range_stack[stacklvl].name = get_timestamp_name(tse->entry_id);
+				range_stack[stacklvl].end_name = get_timestamp_name(
+					sorted_tst_p->entries[match].entry_id);
+				range_stack[stacklvl].end = match;
+				print_with_path(range_stack, stacklvl, match_stamp - stamp,
+						NULL);
+			} else if (!end_of_range) {
+				print_with_path(range_stack, stacklvl, stamp - prev_stamp,
+						get_timestamp_name(tse->entry_id));
+			}
+			/* else: No match && end_of_range == true */
+		}
 		prev_stamp = stamp;
 	}
 
-	if (!mach_readable) {
+	if (output_type == TIMESTAMPS_PRINT_NORMAL) {
 		printf("\nTotal Time: ");
 		print_norm(total_time);
 		printf("\n");
@@ -1170,6 +1259,7 @@ static void print_usage(const char *name, int exit_code)
 	     "   -r | --rawdump ID:                print rawdump of specific ID (in hex) of cbtable\n"
 	     "   -t | --timestamps:                print timestamp information\n"
 	     "   -T | --parseable-timestamps:      print parseable timestamps\n"
+	     "   -S | --stacked-timestamps:        print stacked timestamps (e.g. for flame graph tools)\n"
 	     "   -L | --tcpa-log                   print TCPA log\n"
 	     "   -V | --verbose:                   verbose (debugging) output\n"
 	     "   -v | --version:                   print the version\n"
@@ -1301,9 +1391,8 @@ int main(int argc, char** argv)
 	int print_list = 0;
 	int print_hexdump = 0;
 	int print_rawdump = 0;
-	int print_timestamps = 0;
 	int print_tcpa_log = 0;
-	int machine_readable_timestamps = 0;
+	enum timestamps_print_type timestamp_type = TIMESTAMPS_PRINT_NONE;
 	enum console_print_type console_type = CONSOLE_PRINT_FULL;
 	unsigned int rawdump_id = 0;
 	int max_loglevel = BIOS_NEVER;
@@ -1320,6 +1409,7 @@ int main(int argc, char** argv)
 		{"tcpa-log", 0, 0, 'L'},
 		{"timestamps", 0, 0, 't'},
 		{"parseable-timestamps", 0, 0, 'T'},
+		{"stacked-timestamps", 0, 0, 'S'},
 		{"hexdump", 0, 0, 'x'},
 		{"rawdump", required_argument, 0, 'r'},
 		{"verbose", 0, 0, 'V'},
@@ -1327,7 +1417,7 @@ int main(int argc, char** argv)
 		{"help", 0, 0, 'h'},
 		{0, 0, 0, 0}
 	};
-	while ((opt = getopt_long(argc, argv, "c12B:CltTLxVvh?r:",
+	while ((opt = getopt_long(argc, argv, "c12B:CltTSLxVvh?r:",
 				  long_options, &option_index)) != EOF) {
 		switch (opt) {
 		case 'c':
@@ -1369,12 +1459,15 @@ int main(int argc, char** argv)
 			rawdump_id = strtoul(optarg, NULL, 16);
 			break;
 		case 't':
-			print_timestamps = 1;
+			timestamp_type = TIMESTAMPS_PRINT_NORMAL;
 			print_defaults = 0;
 			break;
 		case 'T':
-			print_timestamps = 1;
-			machine_readable_timestamps = 1;
+			timestamp_type = TIMESTAMPS_PRINT_MACHINE_READABLE;
+			print_defaults = 0;
+			break;
+		case 'S':
+			timestamp_type = TIMESTAMPS_PRINT_STACKED;
 			print_defaults = 0;
 			break;
 		case 'V':
@@ -1486,8 +1579,11 @@ int main(int argc, char** argv)
 	if (print_rawdump)
 		dump_cbmem_raw(rawdump_id);
 
-	if (print_defaults || print_timestamps)
-		dump_timestamps(machine_readable_timestamps);
+	if (print_defaults)
+		timestamp_type = TIMESTAMPS_PRINT_NORMAL;
+
+	if (timestamp_type != TIMESTAMPS_PRINT_NONE)
+		dump_timestamps(timestamp_type);
 
 	if (print_tcpa_log)
 		dump_tcpa_log();