[Skiboot] [PATCH 14/15] external/trace: Add support for multiple trace buffers
Oliver
oohall at gmail.com
Mon Mar 25 13:18:40 AEDT 2019
On Mon, Mar 25, 2019 at 11:19 AM Jordan Niethe <jniethe5 at gmail.com> wrote:
>
> 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 --
This needs to be cracked into seperate patches:
1) Prep-work for adding the heap code to ccan
2a) Add the ccan code verbatium
2b) Any changes needed to integrate the ccan code with skiboot
3) Modifications to dump_trace to make it use the heap.
It's a big of a pain to review otherwise. I assume the change to
libffs is safe, but uh...
> 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
Stewart, this is compatible with Apache right?
> + * 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
>
> _______________________________________________
> Skiboot mailing list
> Skiboot at lists.ozlabs.org
> https://lists.ozlabs.org/listinfo/skiboot
More information about the Skiboot
mailing list