[Skiboot] [PATCH 14/15] external/trace: Add support for multiple trace buffers
Jordan Niethe
jniethe5 at gmail.com
Mon Mar 25 11:14:24 AEDT 2019
Currently it is only possible to dump a single trace buffer at a time.
It would be useful to be able to dump multiple trace buffers. The trace
entries should be displayed in timestamp order. As each buffer is
already in timestamp order an efficient way to do this is using a min
heap to perform a k-way merge. The ccan heap does not support a
'replace' operation so this is not as efficient as it could be.
---
ccan/Makefile.inc | 4 +-
ccan/heap/LICENSE | 1 +
ccan/heap/_info | 68 ++++++++++++++
ccan/heap/heap.c | 119 ++++++++++++++++++++++++
ccan/heap/heap.h | 122 +++++++++++++++++++++++++
ccan/heap/test/run.c | 133 +++++++++++++++++++++++++++
external/trace/Makefile | 2 +-
external/trace/dump_trace.c | 175 +++++++++++++++++++++++++++---------
external/trace/trace.h | 1 +
include/mem_region-malloc.h | 1 +
libflash/libffs.c | 8 --
11 files changed, 581 insertions(+), 53 deletions(-)
create mode 120000 ccan/heap/LICENSE
create mode 100644 ccan/heap/_info
create mode 100644 ccan/heap/heap.c
create mode 100644 ccan/heap/heap.h
create mode 100644 ccan/heap/test/run.c
diff --git a/ccan/Makefile.inc b/ccan/Makefile.inc
index 36e75774a716..546891b62328 100644
--- a/ccan/Makefile.inc
+++ b/ccan/Makefile.inc
@@ -1,7 +1,7 @@
# -*-Makefile-*-
-SUBDIRS += ccan ccan/list ccan/str
-CCAN_OBJS = list/list.o str/str.o
+SUBDIRS += ccan ccan/list ccan/str ccan/heap
+CCAN_OBJS = list/list.o str/str.o heap/heap.o
CCAN=ccan/built-in.a
$(CCAN): $(CCAN_OBJS:%=ccan/%)
diff --git a/ccan/heap/LICENSE b/ccan/heap/LICENSE
new file mode 120000
index 000000000000..2354d12945d3
--- /dev/null
+++ b/ccan/heap/LICENSE
@@ -0,0 +1 @@
+../../licenses/BSD-MIT
\ No newline at end of file
diff --git a/ccan/heap/_info b/ccan/heap/_info
new file mode 100644
index 000000000000..fe5866d04677
--- /dev/null
+++ b/ccan/heap/_info
@@ -0,0 +1,68 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * heap - a simple heap implementation
+ *
+ * Each heap entry is added as a void pointer. This means the implementation
+ * does _not_ assume you already have an array of entries. Instead, it keeps
+ * an internal array of pointers to those entries.
+ *
+ * Example:
+ * #include <stdio.h>
+ *
+ * #include <ccan/heap/heap.h>
+ *
+ * static bool less(const int *i, const int *j)
+ * {
+ * return *i < *j;
+ * }
+ *
+ * static bool __less(const void *i, const void *j)
+ * {
+ * return less(i, j);
+ * }
+ *
+ * int main(int argc, char *argv[])
+ * {
+ * struct heap *h;
+ * int arr[] = {1, 0, 2};
+ * int i;
+ *
+ * h = heap_init(__less);
+ * if (h == NULL) {
+ * perror("heap alloc");
+ * exit(1);
+ * }
+ *
+ * for (i = 0; i < 3; i++) {
+ * if (heap_push(h, &arr[i])) {
+ * perror("heap push");
+ * exit(1);
+ * }
+ * }
+ * // should print 0, 1, 2
+ * for (i = 0; i < 3; i++) {
+ * int *v = heap_pop(h);
+ * printf("%d\n", *v);
+ * }
+ * heap_free(h);
+ * return 0;
+ * }
+ *
+ * License: BSD-MIT
+ * Author: Emilio G. Cota <cota at braap.org>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/heap/heap.c b/ccan/heap/heap.c
new file mode 100644
index 000000000000..aec9016788bb
--- /dev/null
+++ b/ccan/heap/heap.c
@@ -0,0 +1,119 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#include <ccan/heap/heap.h>
+
+/*
+ * Allocating memory in chunks greater than needed does not yield measurable
+ * speedups of the test program when linking against glibc 2.15.
+ *
+ * When the data array has to be shrunk though, limiting calls to realloc
+ * does help a little bit (~7% speedup), hence the following parameter.
+ */
+#define HEAP_MEM_HYSTERESIS 4096
+
+static inline void swap(struct heap *h, size_t i, size_t j)
+{
+ void *foo = h->data[i];
+
+ h->data[i] = h->data[j];
+ h->data[j] = foo;
+}
+
+static void __up(struct heap *h, size_t j)
+{
+ size_t i; /* parent */
+
+ while (j) {
+ i = (j - 1) / 2;
+
+ if (h->less(h->data[j], h->data[i])) {
+ swap(h, i, j);
+ j = i;
+ } else {
+ break;
+ }
+ }
+}
+
+int heap_push(struct heap *h, void *data)
+{
+ if (h->len == h->cap) {
+ void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
+ if (m == NULL)
+ return -1;
+ h->data = m;
+ h->cap++;
+ }
+ h->data[h->len++] = data;
+ __up(h, h->len - 1);
+ return 0;
+}
+
+static void __down(struct heap *h, size_t i)
+{
+ size_t l, r, j; /* left, right, min child */
+
+ while (1) {
+ l = 2 * i + 1;
+ if (l >= h->len)
+ break;
+ r = l + 1;
+ if (r >= h->len)
+ j = l;
+ else
+ j = h->less(h->data[l], h->data[r]) ? l : r;
+
+ if (h->less(h->data[j], h->data[i])) {
+ swap(h, i, j);
+ i = j;
+ } else {
+ break;
+ }
+ }
+}
+
+void *heap_pop(struct heap *h)
+{
+ void *ret = h->data[0];
+ void *m;
+
+ swap(h, 0, --h->len);
+ if (h->len) {
+ __down(h, 0);
+ if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
+ m = realloc(h->data, h->len * sizeof(void *));
+ if (m == NULL)
+ return NULL;
+ h->data = m;
+ h->cap = h->len;
+ }
+ }
+
+ return ret;
+}
+
+struct heap *heap_init(heap_less_func_t less)
+{
+ struct heap *heap = calloc(1, sizeof(*heap));
+
+ if (heap == NULL)
+ return NULL;
+ heap->less = less;
+ return heap;
+}
+
+void heap_ify(struct heap *h, heap_less_func_t less)
+{
+ int i;
+
+ if (less)
+ h->less = less;
+
+ for (i = h->len / 2 - 1; i >= 0; i--)
+ __down(h, i);
+}
+
+void heap_free(struct heap *heap)
+{
+ free(heap->data);
+ free(heap);
+}
diff --git a/ccan/heap/heap.h b/ccan/heap/heap.h
new file mode 100644
index 000000000000..69368a1ce719
--- /dev/null
+++ b/ccan/heap/heap.h
@@ -0,0 +1,122 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_HEAP_H
+#define CCAN_HEAP_H
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+typedef bool (*heap_less_func_t)(const void *, const void *);
+
+/**
+ * struct heap - a simple, generic heap structure
+ * @data: array of pointers to the heap's entries
+ * @less: function to compare heap entries
+ * @cap: capacity of the heap array in @data
+ * @len: number of valid elements in the heap array
+ *
+ * The @less function determines the nature of the heap. If @less is
+ * something akin to 'return a.foo < b.foo', then the heap will be
+ * a min heap. Conversely, a '>' predicate will result in a max heap.
+ *
+ * Elements in the @data array are allocated as needed, hence the need for
+ * @cap and @len.
+ */
+struct heap {
+ void **data;
+ heap_less_func_t less;
+ size_t cap;
+ size_t len;
+};
+
+/**
+ * heap_init - allocate and initialise an empty heap
+ * @less: function to be used to compare heap entries
+ *
+ * Returns a pointer to an initialised heap struct on success, NULL if
+ * the heap could not be allocated.
+ *
+ * See also: HEAP_INIT()
+ */
+struct heap *heap_init(heap_less_func_t less);
+
+/**
+ * HEAP_INIT - initialiser for an empty heap
+ * @func: comparison function to be used in the heap
+ *
+ * Explicit initialiser for a heap.
+ *
+ * See also: heap_init()
+ */
+#define HEAP_INIT(func) { NULL, func, 0, 0 }
+
+/**
+ * heap_free - free a heap allocated via heap_init()
+ * @heap: the heap to be freed
+ *
+ * Note that this only frees the heap and its internal resources, not
+ * the entries pointed to by it.
+ *
+ * See also: heap_init()
+ */
+void heap_free(struct heap *heap);
+
+/**
+ * heap_ify - enforce the heap property based on a new comparison function
+ * @h: heap to be heapified
+ * @less: new comparison function
+ *
+ * Complexity: O(n)
+ */
+void heap_ify(struct heap *h, heap_less_func_t less);
+
+/**
+ * heap_push - push a new heap entry
+ * @h: heap to receive the new entry
+ * @data: pointer to the new entry
+ *
+ * Returns 0 on success, -1 on error.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_pop()
+ */
+int heap_push(struct heap *h, void *data);
+
+/**
+ * heap_pop - pops the root heap entry
+ * @h: heap to pop the head from
+ *
+ * Returns the root entry of the heap after extracting it, or NULL on error.
+ *
+ * Note: Calling heap_pop() on an empty heap is a bug. When in doubt,
+ * check heap->len. See heap_peek()'s documentation for an example.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_push(), heap_peek()
+ */
+void *heap_pop(struct heap *h);
+
+/**
+ * heap_peek - inspect the root entry of a heap
+ * @h: heap whose root entry is to be inspected
+ *
+ * Returns the root entry in the heap, without extracting it from @h.
+ *
+ * Note: Calling heap_peek() on an empty heap is a bug; check the heap's
+ * number of items and act accordingly, as in the example below.
+ *
+ * See also: heap_pop()
+ *
+ * Example:
+ * static inline void *heap_peek_safe(const struct heap *h)
+ * {
+ * return h->len ? heap_peek(h) : NULL;
+ * }
+ */
+static inline void *heap_peek(const struct heap *h)
+{
+ return h->data[0];
+}
+
+#endif /* CCAN_HEAP_H */
diff --git a/ccan/heap/test/run.c b/ccan/heap/test/run.c
new file mode 100644
index 000000000000..6972a6bea013
--- /dev/null
+++ b/ccan/heap/test/run.c
@@ -0,0 +1,133 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include <ccan/heap/heap.h>
+/* Include the C files directly. */
+#include <ccan/heap/heap.c>
+#include <ccan/tap/tap.h>
+
+struct item {
+ void *foobar;
+ int v;
+};
+
+static bool heap_ok(const struct heap *h, heap_less_func_t less, int i)
+{
+ int l, r;
+
+ l = 2 * i + 1;
+ r = l + 1;
+
+ if (l < h->len) {
+ if (less(h->data[l], h->data[i])) {
+ fprintf(stderr, "heap property violation\n");
+ return false;
+ }
+ if (!heap_ok(h, less, l))
+ return false;
+ }
+ if (r < h->len) {
+ if (less(h->data[r], h->data[i])) {
+ fprintf(stderr, "heap property violation\n");
+ return false;
+ }
+ if (!heap_ok(h, less, r))
+ return false;
+ }
+ return true;
+}
+
+static bool less(const struct item *a, const struct item *b)
+{
+ return a->v < b->v;
+}
+
+static bool __less(const void *a, const void *b)
+{
+ return less(a, b);
+}
+
+static bool more(const struct item *a, const struct item *b)
+{
+ return a->v > b->v;
+}
+
+static bool __more(const void *a, const void *b)
+{
+ return more(a, b);
+}
+
+static bool some_test(size_t n, bool is_less)
+{
+ struct item *items = calloc(n, sizeof(*items));
+ struct item *item, *prev;
+ struct heap *h;
+ int i;
+
+ if (items == NULL) {
+ perror("items");
+ exit(EXIT_FAILURE);
+ }
+
+ if (is_less)
+ h = heap_init(__less);
+ else
+ h = heap_init(__more);
+ if (h == NULL) {
+ perror("heap_init");
+ exit(EXIT_FAILURE);
+ }
+
+ for (i = 0; i < n; i++) {
+ item = &items[i];
+
+ item->v = rand();
+ printf("pushing %d\n", item->v);
+ heap_push(h, item);
+ if (!heap_ok(h, is_less ? __less : __more, 0))
+ return false;
+ }
+ if (is_less) {
+ heap_ify(h, __more);
+ if (!heap_ok(h, __more, 0))
+ return false;
+ heap_ify(h, __less);
+ if (!heap_ok(h, __less, 0))
+ return false;
+ } else {
+ heap_ify(h, NULL);
+ if (!heap_ok(h, __more, 0))
+ return false;
+ }
+
+ for (i = 0; i < n; i++) {
+ item = heap_pop(h);
+ if (!heap_ok(h, is_less ? __less : __more, 0))
+ return false;
+ printf("popped %d\n", item->v);
+ if (i > 0) {
+ if (is_less) {
+ if (less(item, prev))
+ return false;
+ } else {
+ if (more(item, prev))
+ return false;
+ }
+ }
+ prev = item;
+ }
+ heap_free(h);
+ free(items);
+ return true;
+}
+
+int main(void)
+{
+ plan_tests(3);
+
+ ok1(some_test(5000, true));
+ ok1(some_test(1, true));
+ ok1(some_test(33, false));
+
+ return exit_status();
+}
diff --git a/external/trace/Makefile b/external/trace/Makefile
index bff52f3a6ab2..d806046713af 100644
--- a/external/trace/Makefile
+++ b/external/trace/Makefile
@@ -1,7 +1,7 @@
HOSTEND=$(shell uname -m | sed -e 's/^i.*86$$/LITTLE/' -e 's/^x86.*/LITTLE/' -e 's/^ppc64le/LITTLE/' -e 's/^ppc.*/BIG/')
CFLAGS=-g -Wall -DHAVE_$(HOSTEND)_ENDIAN -I../../include -I../../
-dump_trace: dump_trace.c trace.c
+dump_trace: dump_trace.c trace.c ../../ccan/heap/heap.c
clean:
rm -f dump_trace *.o
diff --git a/external/trace/dump_trace.c b/external/trace/dump_trace.c
index f38b38187691..f29da62fbabc 100644
--- a/external/trace/dump_trace.c
+++ b/external/trace/dump_trace.c
@@ -30,9 +30,26 @@
#include "../../ccan/endian/endian.h"
#include "../../ccan/short_types/short_types.h"
+#include "../../ccan/heap/heap.h"
#include "trace.h"
+struct trace_entry {
+ int index;
+ union trace t;
+ struct list_node link;
+};
+
+static void *ezalloc(size_t size)
+{
+ void *p;
+
+ p = calloc(size, 1);
+ if (!p)
+ err(1, "Allocating memory");
+ return p;
+}
+
static void display_header(const struct trace_hdr *h)
{
static u64 prev_ts;
@@ -132,57 +149,131 @@ static void dump_uart(struct trace_uart *t)
}
}
-int main(int argc, char *argv[])
+static void load_traces(struct trace_reader *trs, int count)
{
- int fd;
- struct trace_reader tr;
- struct trace_info *ti;
+ struct trace_entry *te;
union trace t;
+ int i;
- if (argc != 2)
- errx(1, "Usage: dump_trace file");
+ for (i = 0; i < count; i++) {
+ while (trace_get(&t, &trs[i])) {
+ te = ezalloc(sizeof(struct trace_entry));
+ memcpy(&te->t, &t, sizeof(union trace));
+ te->index = i;
+ list_add_tail(&trs[i].traces, &te->link);
+ }
+ }
+}
- fd = open(argv[1], O_RDONLY);
- if(fd < 0)
- err(1, "Opening %s", argv[1]);
- ti = mmap(NULL, sizeof(struct trace_info) + TBUF_SZ + MAX_SIZE,
- PROT_READ, MAP_PRIVATE, fd, 0);
- if (ti == MAP_FAILED)
- err(1, "Mmaping %s", argv[1]);
+static void print_trace(union trace *t)
+{
+ display_header(&t->hdr);
+ switch (t->hdr.type) {
+ case TRACE_REPEAT:
+ printf("REPEATS: %u times\n",
+ be16_to_cpu(t->repeat.num));
+ break;
+ case TRACE_OVERFLOW:
+ printf("**OVERFLOW**: %"PRIu64" bytes missed\n",
+ be64_to_cpu(t->overflow.bytes_missed));
+ break;
+ case TRACE_OPAL:
+ dump_opal_call(&t->opal);
+ break;
+ case TRACE_FSP_MSG:
+ dump_fsp_msg(&t->fsp_msg);
+ break;
+ case TRACE_FSP_EVENT:
+ dump_fsp_event(&t->fsp_evt);
+ break;
+ case TRACE_UART:
+ dump_uart(&t->uart);
+ break;
+ default:
+ printf("UNKNOWN(%u) CPU %u length %u\n",
+ t->hdr.type, be16_to_cpu(t->hdr.cpu),
+ t->hdr.len_div_8 * 8);
+ }
+}
- memset(&tr, 0, sizeof(struct trace_reader));
- tr.tb = &ti->tb;
+/* Gives a min heap */
+bool earlier_entry(const void *va, const void *vb)
+{
+ struct trace_entry *a, *b;
+ a = (struct trace_entry*) va;
+ b = (struct trace_entry*) vb;
- while (trace_get(&t, &tr)) {
- display_header(&t.hdr);
- switch (t.hdr.type) {
- case TRACE_REPEAT:
- printf("REPEATS: %u times\n",
- be16_to_cpu(t.repeat.num));
- break;
- case TRACE_OVERFLOW:
- printf("**OVERFLOW**: %"PRIu64" bytes missed\n",
- be64_to_cpu(t.overflow.bytes_missed));
- break;
- case TRACE_OPAL:
- dump_opal_call(&t.opal);
- break;
- case TRACE_FSP_MSG:
- dump_fsp_msg(&t.fsp_msg);
- break;
- case TRACE_FSP_EVENT:
- dump_fsp_event(&t.fsp_evt);
- break;
- case TRACE_UART:
- dump_uart(&t.uart);
+ if (!a)
+ return false;
+ if (!b)
+ return true;
+ return be64_to_cpu(a->t.hdr.timestamp) < be64_to_cpu(b->t.hdr.timestamp);
+}
+
+static void display_traces(struct trace_reader *trs, int count)
+{
+ struct trace_entry *current, *next;
+ struct heap *h;
+ int i;
+
+ h = heap_init(earlier_entry);
+ if (!h)
+ err(1, "Allocating memory");
+
+ for (i = 0; i < count; i++) {
+ current = list_pop(&trs[i].traces, struct trace_entry, link);
+ /* no need to add empty ones */
+ if (current)
+ heap_push(h, current);
+ }
+
+ while (h->len) {
+ current = heap_pop(h);
+ if (!current)
break;
- default:
- printf("UNKNOWN(%u) CPU %u length %u\n",
- t.hdr.type, be16_to_cpu(t.hdr.cpu),
- t.hdr.len_div_8 * 8);
- }
+
+ print_trace(¤t->t);
+
+ next = list_pop(&trs[current->index].traces, struct trace_entry,
+ link);
+ heap_push(h, next);
+ free(current);
}
+ heap_free(h);
+}
+
+int main(int argc, char *argv[])
+{
+ struct trace_reader *trs;
+ struct trace_info *ti;
+ int fd, i;
+
+
+ if (argc < 2)
+ errx(1, "Usage: dump_trace file...");
+
+ argc--;
+ argv++;
+ trs = ezalloc(sizeof(struct trace_reader) * argc);
+
+ for (i = 0; i < argc; i++) {
+ fd = open(argv[i], O_RDONLY);
+ if(fd < 0)
+ err(1, "Opening %s", argv[i]);
+
+ ti = mmap(NULL, sizeof(struct trace_info) + TBUF_SZ + MAX_SIZE,
+ PROT_READ, MAP_PRIVATE, fd, 0);
+ if (ti == MAP_FAILED)
+ err(1, "Mmaping %s", argv[i]);
+
+ trs[i].tb = &ti->tb;
+ list_head_init(&trs[i].traces);
+ }
+
+ load_traces(trs, argc);
+ display_traces(trs, argc);
+
return 0;
}
diff --git a/external/trace/trace.h b/external/trace/trace.h
index 2c453ea3d969..3a916d8f5ef8 100644
--- a/external/trace/trace.h
+++ b/external/trace/trace.h
@@ -26,6 +26,7 @@ struct trace_reader {
be64 rpos;
/* If the last one we read was a repeat, this shows how many. */
be32 last_repeat;
+ struct list_head traces;
struct tracebuf *tb;
};
diff --git a/include/mem_region-malloc.h b/include/mem_region-malloc.h
index 58027ae7c126..80412a1d4d39 100644
--- a/include/mem_region-malloc.h
+++ b/include/mem_region-malloc.h
@@ -31,6 +31,7 @@ void *__memalign(size_t boundary, size_t size, const char *location) __warn_unus
#define malloc(size) __malloc(size, __location__)
#define zalloc(size) __zalloc(size, __location__)
+#define calloc(nmemb, size) __zalloc(nmemb * size, __location__)
#define realloc(ptr, size) __realloc(ptr, size, __location__)
#define free(ptr) __free(ptr, __location__)
#define memalign(boundary, size) __memalign(boundary, size, __location__)
diff --git a/libflash/libffs.c b/libflash/libffs.c
index 82caeb39f890..09448a073cc0 100644
--- a/libflash/libffs.c
+++ b/libflash/libffs.c
@@ -23,14 +23,6 @@
#ifndef __SKIBOOT__
#include <sys/types.h>
#include <unistd.h>
-#else
-static void *calloc(size_t num, size_t size)
-{
- void *ptr = malloc(num * size);
- if (ptr)
- memset(ptr, 0, num * size);
- return ptr;
-}
#endif
#include "ffs.h"
--
2.20.1
More information about the Skiboot
mailing list