Message ID | 20190325001425.29483-15-jniethe5@gmail.com |
---|---|
State | Superseded |
Headers | show |
Series | Improve usability of skiboot traces | expand |
Context | Check | Description |
---|---|---|
snowpatch_ozlabs/apply_patch | success | Successfully applied on branch master (b392d785eb49630b9f00fef8d17944ed82b2c1fe) |
snowpatch_ozlabs/snowpatch_job_snowpatch-skiboot | success | Test snowpatch/job/snowpatch-skiboot on branch master |
snowpatch_ozlabs/snowpatch_job_snowpatch-skiboot-dco | fail | Signed-off-by missing |
On Mon, Mar 25, 2019 at 11:19 AM Jordan Niethe <jniethe5@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@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@lists.ozlabs.org > https://lists.ozlabs.org/listinfo/skiboot
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@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"