Port st-dump and st-job-stats

Include st-dump (formerly 'st_show') and st-job-stats (formerly
'st_job_stats') from https://github.com/brandenburg/sched-trace-tools
in this repository.

4 files changed, 632 insertions, 0 deletions

diff --git a/include/eheap.h b/include/eheap.h
new file mode 100644
index 0000000..323fa30
--- /dev/null
+++ b/include/eheap.h
@@ -0,0 +1,12 @@
+#ifndef EHEAP_H
+#define EHEAP_H
+
+#include <limits.h>
+#include "heap.h"
+
+int earlier_event(struct heap_node* _a, struct heap_node* _b);
+
+struct heap* heapify_events(struct st_event_record *ev, unsigned int count);
+
+
+#endif
diff --git a/include/heap.h b/include/heap.h
new file mode 100644
index 0000000..e46b0eb
--- /dev/null
+++ b/include/heap.h
@@ -0,0 +1,379 @@
+/* heap.h -- Binomial Heaps
+ *
+ * Copyright (c) 2008, Bjoern B. Brandenburg <bbb [at] cs.unc.edu>
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in the
+ *       documentation and/or other materials provided with the distribution.
+ *     * Neither the name of the University of North Carolina nor the
+ *       names of its contributors may be used to endorse or promote products
+ *       derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY  COPYRIGHT OWNER AND CONTRIBUTERS ``AS IS'' AND
+ * ANY  EXPRESS OR  IMPLIED  WARRANTIES,  INCLUDING, BUT  NOT  LIMITED TO,  THE
+ * IMPLIED WARRANTIES  OF MERCHANTABILITY AND FITNESS FOR  A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO  EVENT SHALL THE  COPYRIGHT OWNER OR  CONTRIBUTERS BE
+ * LIABLE  FOR  ANY  DIRECT,   INDIRECT,  INCIDENTAL,  SPECIAL,  EXEMPLARY,  OR
+ * CONSEQUENTIAL  DAMAGES  (INCLUDING,  BUT  NOT  LIMITED  TO,  PROCUREMENT  OF
+ * SUBSTITUTE GOODS  OR SERVICES;  LOSS OF USE,  DATA, OR PROFITS;  OR BUSINESS
+ * INTERRUPTION)  HOWEVER CAUSED  AND ON  ANY THEORY  OF LIABILITY,  WHETHER IN
+ * CONTRACT,  STRICT LIABILITY,  OR  TORT (INCLUDING  NEGLIGENCE OR  OTHERWISE)
+ * ARISING IN ANY WAY  OUT OF THE USE OF THIS SOFTWARE,  EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef HEAP_H
+#define HEAP_H
+
+#define NOT_IN_HEAP UINT_MAX
+
+struct heap_node {
+        struct heap_node*       parent;
+        struct heap_node*       next;
+        struct heap_node*       child;
+
+        unsigned int            degree;
+        void*                   value;
+        struct heap_node**      ref;
+};
+
+struct heap {
+        struct heap_node*       head;
+        /* We cache the minimum of the heap.
+         * This speeds up repeated peek operations.
+         */
+        struct heap_node*       min;
+};
+
+/* item comparison function:
+ * return 1 if a has higher prio than b, 0 otherwise
+ */
+typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b);
+
+static inline void heap_init(struct heap* heap)
+{
+        heap->head = NULL;
+        heap->min  = NULL;
+}
+
+static inline void heap_node_init_ref(struct heap_node** _h, void* value)
+{
+        struct heap_node* h = *_h;
+        h->parent = NULL;
+        h->next   = NULL;
+        h->child  = NULL;
+        h->degree = NOT_IN_HEAP;
+        h->value  = value;
+        h->ref    = _h;
+}
+
+static inline void heap_node_init(struct heap_node* h, void* value)
+{
+        h->parent = NULL;
+        h->next   = NULL;
+        h->child  = NULL;
+        h->degree = NOT_IN_HEAP;
+        h->value  = value;
+        h->ref    = NULL;
+}
+
+static inline void* heap_node_value(struct heap_node* h)
+{
+        return h->value;
+}
+
+static inline int heap_node_in_heap(struct heap_node* h)
+{
+        return h->degree != NOT_IN_HEAP;
+}
+
+static inline int heap_empty(struct heap* heap)
+{
+        return heap->head == NULL && heap->min == NULL;
+}
+
+/* make child a subtree of root */
+static inline void __heap_link(struct heap_node* root,
+                               struct heap_node* child)
+{
+        child->parent = root;
+        child->next   = root->child;
+        root->child   = child;
+        root->degree++;
+}
+
+/* merge root lists */
+static inline struct heap_node* __heap_merge(struct heap_node* a,
+                                             struct heap_node* b)
+{
+        struct heap_node* head = NULL;
+        struct heap_node** pos = &head;
+
+        while (a && b) {
+                if (a->degree < b->degree) {
+                        *pos = a;
+                        a = a->next;
+                } else {
+                        *pos = b;
+                        b = b->next;
+                }
+                pos = &(*pos)->next;
+        }
+        if (a)
+                *pos = a;
+        else
+                *pos = b;
+        return head;
+}
+
+/* reverse a linked list of nodes. also clears parent pointer */
+static inline struct heap_node* __heap_reverse(struct heap_node* h)
+{
+        struct heap_node* tail = NULL;
+        struct heap_node* next;
+
+        if (!h)
+                return h;
+
+        h->parent = NULL;
+        while (h->next) {
+                next    = h->next;
+                h->next = tail;
+                tail    = h;
+                h       = next;
+                h->parent = NULL;
+        }
+        h->next = tail;
+        return h;
+}
+
+static inline void __heap_min(heap_prio_t higher_prio, struct heap* heap,
+                              struct heap_node** prev, struct heap_node** node)
+{
+        struct heap_node *_prev, *cur;
+        *prev = NULL;
+
+        if (!heap->head) {
+                *node = NULL;
+                return;
+        }
+
+        *node = heap->head;
+        _prev = heap->head;
+        cur   = heap->head->next;
+        while (cur) {
+                if (higher_prio(cur, *node)) {
+                        *node = cur;
+                        *prev = _prev;
+                }
+                _prev = cur;
+                cur   = cur->next;
+        }
+}
+
+static inline void __heap_union(heap_prio_t higher_prio, struct heap* heap,
+                                struct heap_node* h2)
+{
+        struct heap_node* h1;
+        struct heap_node *prev, *x, *next;
+        if (!h2)
+                return;
+        h1 = heap->head;
+        if (!h1) {
+                heap->head = h2;
+                return;
+        }
+        h1 = __heap_merge(h1, h2);
+        prev = NULL;
+        x    = h1;
+        next = x->next;
+        while (next) {
+                if (x->degree != next->degree ||
+                    (next->next && next->next->degree == x->degree)) {
+                        /* nothing to do, advance */
+                        prev = x;
+                        x    = next;
+                } else if (higher_prio(x, next)) {
+                        /* x becomes the root of next */
+                        x->next = next->next;
+                        __heap_link(x, next);
+                } else {
+                        /* next becomes the root of x */
+                        if (prev)
+                                prev->next = next;
+                        else
+                                h1 = next;
+                        __heap_link(next, x);
+                        x = next;
+                }
+                next = x->next;
+        }
+        heap->head = h1;
+}
+
+static inline struct heap_node* __heap_extract_min(heap_prio_t higher_prio,
+                                                   struct heap* heap)
+{
+        struct heap_node *prev, *node;
+        __heap_min(higher_prio, heap, &prev, &node);
+        if (!node)
+                return NULL;
+        if (prev)
+                prev->next = node->next;
+        else
+                heap->head = node->next;
+        __heap_union(higher_prio, heap, __heap_reverse(node->child));
+        return node;
+}
+
+/* insert (and reinitialize) a node into the heap */
+static inline void heap_insert(heap_prio_t higher_prio, struct heap* heap,
+                               struct heap_node* node)
+{
+        struct heap_node *min;
+        node->child  = NULL;
+        node->parent = NULL;
+        node->next   = NULL;
+        node->degree = 0;
+        if (heap->min && higher_prio(node, heap->min)) {
+                /* swap min cache */
+                min = heap->min;
+                min->child  = NULL;
+                min->parent = NULL;
+                min->next   = NULL;
+                min->degree = 0;
+                __heap_union(higher_prio, heap, min);
+                heap->min   = node;
+        } else
+                __heap_union(higher_prio, heap, node);
+}
+
+static inline void __uncache_min(heap_prio_t higher_prio, struct heap* heap)
+{
+        struct heap_node* min;
+        if (heap->min) {
+                min = heap->min;
+                heap->min = NULL;
+                heap_insert(higher_prio, heap, min);
+        }
+}
+
+/* merge addition into target */
+static inline void heap_union(heap_prio_t higher_prio,
+                              struct heap* target, struct heap* addition)
+{
+        /* first insert any cached minima, if necessary */
+        __uncache_min(higher_prio, target);
+        __uncache_min(higher_prio, addition);
+        __heap_union(higher_prio, target, addition->head);
+        /* this is a destructive merge */
+        addition->head = NULL;
+}
+
+static inline struct heap_node* heap_peek(heap_prio_t higher_prio,
+                                          struct heap* heap)
+{
+        if (!heap->min)
+                heap->min = __heap_extract_min(higher_prio, heap);
+        return heap->min;
+}
+
+static inline struct heap_node* heap_take(heap_prio_t higher_prio,
+                                          struct heap* heap)
+{
+        struct heap_node *node;
+        if (!heap->min)
+                heap->min = __heap_extract_min(higher_prio, heap);
+        node = heap->min;
+        heap->min = NULL;
+        if (node)
+                node->degree = NOT_IN_HEAP;
+        return node;
+}
+
+static inline void heap_decrease(heap_prio_t higher_prio, struct heap* heap,
+                                 struct heap_node* node)
+{
+        struct heap_node *parent;
+        struct heap_node** tmp_ref;
+        void* tmp;
+
+        /* node's priority was decreased, we need to update its position */
+        if (!node->ref)
+                return;
+        if (heap->min != node) {
+                /* bubble up */
+                parent = node->parent;
+                while (parent && higher_prio(node, parent)) {
+                        /* swap parent and node */
+                        tmp           = parent->value;
+                        parent->value = node->value;
+                        node->value   = tmp;
+                        /* swap references */
+                        if (parent->ref)
+                                *(parent->ref) = node;
+                        *(node->ref)   = parent;
+                        tmp_ref        = parent->ref;
+                        parent->ref    = node->ref;
+                        node->ref      = tmp_ref;
+                        /* step up */
+                        node   = parent;
+                        parent = node->parent;
+                }
+        }
+}
+
+static inline void heap_delete(heap_prio_t higher_prio, struct heap* heap,
+                               struct heap_node* node)
+{
+        struct heap_node *parent, *prev, *pos;
+        struct heap_node** tmp_ref;
+        void* tmp;
+
+        if (!node->ref) /* can only delete if we have a reference */
+                return;
+        if (heap->min != node) {
+                /* bubble up */
+                parent = node->parent;
+                while (parent) {
+                        /* swap parent and node */
+                        tmp           = parent->value;
+                        parent->value = node->value;
+                        node->value   = tmp;
+                        /* swap references */
+                        if (parent->ref)
+                                *(parent->ref) = node;
+                        *(node->ref)   = parent;
+                        tmp_ref        = parent->ref;
+                        parent->ref    = node->ref;
+                        node->ref      = tmp_ref;
+                        /* step up */
+                        node   = parent;
+                        parent = node->parent;
+                }
+                /* now delete:
+                 * first find prev */
+                prev = NULL;
+                pos  = heap->head;
+                while (pos != node) {
+                        prev = pos;
+                        pos  = pos->next;
+                }
+                /* we have prev, now remove node */
+                if (prev)
+                        prev->next = node->next;
+                else
+                        heap->head = node->next;
+                __heap_union(higher_prio, heap, __heap_reverse(node->child));
+        } else
+                heap->min = NULL;
+        node->degree = NOT_IN_HEAP;
+}
+
+#endif /* HEAP_H */
diff --git a/include/load.h b/include/load.h
new file mode 100644
index 0000000..c0d10aa
--- /dev/null
+++ b/include/load.h
@@ -0,0 +1,92 @@
+#ifndef LOAD_H
+#define LOAD_H
+
+#include "sched_trace.h"
+
+int map_trace(const char *name, void **start, void **end, size_t *size);
+struct heap* load(char **files, int no_files, unsigned int *count);
+
+struct evlink {
+        struct evlink *next;
+        struct st_event_record* rec;
+};
+
+struct task {
+        int pid;
+        unsigned int no_events;
+        struct st_event_record* name;
+        struct st_event_record* param;
+        struct evlink* events;
+        struct evlink** next;
+};
+
+#define MAX_TASKS 512
+
+extern struct task tasks[MAX_TASKS];
+extern struct evlink* sys_events;
+extern u64 time0;
+extern u32 g_min_task;
+extern u32 g_max_task;
+
+static inline double ns2ms(u64 ns)
+{
+        return ns / 1000000.0;
+}
+
+static inline double ns2ms_adj(u64 ns)
+{
+        return ns2ms(ns - time0);
+}
+
+static inline double evtime(struct st_event_record* rec)
+{
+        return ns2ms_adj(event_time(rec));
+}
+
+
+void crop_events(struct task* t, double min, double max);
+void crop_events_all(double min, double max);
+
+struct task* by_pid(int pid);
+
+void init_tasks(void);
+void split(struct heap* h, unsigned int count, int find_time0);
+
+const char* tsk_name(struct task* t);
+int tsk_cpu(struct task *t);
+u32 per(struct task* t);
+u32 exe(struct task* t);
+u32 idx(struct task* t);
+
+
+u32 count_tasks(void);
+
+#define CHECK(_e, test) if (test) fprintf(stderr, "'%s' failed.\n", #test);
+
+#define for_each_task(t) \
+        for (t = tasks + g_min_task; t < tasks + g_max_task && t->pid; t++)
+
+#define for_each_event(t, e) \
+        for (e = t->events; e; e = e->next)
+
+#define for_each_event_t(t, e, evtype) \
+        for_each_event(t, e) if (e->rec->hdr.type == evtype)
+
+#define find_evtype(e, evtype) \
+        while (e && e->rec->hdr.type != evtype) e = e->next;
+
+#define find(e, evtype) \
+        while (e && e->rec->hdr.type != evtype) e = e->next; if (!e) break;
+
+
+static inline struct st_event_record *find_sys_event(u8 type)
+{
+        struct evlink* pos = sys_events;
+        find_evtype(pos, type);
+        if (pos)
+                return pos->rec;
+        else
+                return NULL;
+}
+
+#endif
diff --git a/include/sched_trace.h b/include/sched_trace.h
new file mode 100644
index 0000000..0f6828c
--- /dev/null
+++ b/include/sched_trace.h
@@ -0,0 +1,149 @@
+#ifndef __SCHED_TRACE_H_
+#define __SCHED_TRACE_H_
+
+#include <stdint.h>
+
+typedef uint8_t  u8;
+typedef uint32_t u32;
+typedef uint16_t u16;
+typedef uint64_t u64;
+
+/* A couple of notes about the format:
+ *
+ * - make sure it is in sync with the kernel
+ * - all times in nanoseconds
+ * - endianess issues are the problem of the app
+ */
+
+struct st_trace_header {
+        u8      type;           /* Of what type is this record?  */
+        u8      cpu;            /* On which CPU was it recorded? */
+        u16     pid;            /* PID of the task.              */
+        u32     job;            /* The job sequence number.      */
+};
+
+#define ST_NAME_LEN 16
+struct st_name_data {
+        char    cmd[ST_NAME_LEN];/* The name of the executable of this process. */
+};
+
+struct st_param_data {          /* regular params */
+        u32     wcet;
+        u32     period;
+        u32     phase;
+        u8      partition;
+        u8      __unused[3];
+};
+
+struct st_release_data {        /* A job is was/is going to be released. */
+        u64     release;        /* What's the release time?              */
+        u64     deadline;       /* By when must it finish?               */
+};
+
+struct st_assigned_data {       /* A job was asigned to a CPU.           */
+        u64     when;
+        u8      target;         /* Where should it execute?              */
+        u8      __unused[3];
+};
+
+struct st_switch_to_data {      /* A process was switched to on a given CPU.   */
+        u64     when;           /* When did this occur?                        */
+        u32     exec_time;      /* Time the current job has executed.          */
+
+};
+
+struct st_switch_away_data {    /* A process was switched away from on a given CPU. */
+        u64     when;
+        u64     exec_time;
+};
+
+struct st_completion_data {     /* A job completed. */
+        u64     when;
+        u64     forced:1;       /* Set to 1 if job overran and kernel advanced to the
+                                 * next job automatically; set to 0 otherwise.
+                                 */
+        u64     exec_time:63; /* Actual execution time of job. */
+};
+
+struct st_block_data {          /* A task blocks. */
+        u64     when;
+        u64     __unused;
+};
+
+struct st_resume_data {         /* A task resumes. */
+        u64     when;
+        u64     __unused;
+};
+
+struct st_np_enter_data {       /* A task becomes non-preemptable.  */
+        u64     when;
+        u64     __unused;
+};
+
+struct st_np_exit_data {        /* A task becomes preemptable again. */
+        u64     when;
+        u64     __unused;
+};
+
+struct st_action_data {         /* Catch-all for misc. events. */
+        u64     when;
+        u8      action;
+        u8      __unused[7];
+};
+
+struct st_sys_release_data {
+        u64     when;
+        u64     release;
+};
+
+#define DATA(x) struct st_ ## x ## _data x;
+
+typedef enum {
+        ST_NAME = 1,            /* Start at one, so that we can spot
+                                 * uninitialized records. */
+        ST_PARAM,
+        ST_RELEASE,
+        ST_ASSIGNED,
+        ST_SWITCH_TO,
+        ST_SWITCH_AWAY,
+        ST_COMPLETION,
+        ST_BLOCK,
+        ST_RESUME,
+        ST_ACTION,
+        ST_SYS_RELEASE,
+        ST_NP_ENTER,
+        ST_NP_EXIT,
+
+        ST_INVALID              /* Dummy ID to catch too-large IDs. */
+} st_event_record_type_t;
+
+struct st_event_record {
+        struct st_trace_header hdr;
+        union {
+                u64 raw[2];
+
+                DATA(name);
+                DATA(param);
+                DATA(release);
+                DATA(assigned);
+                DATA(switch_to);
+                DATA(switch_away);
+                DATA(completion);
+                DATA(block);
+                DATA(resume);
+                DATA(action);
+                DATA(sys_release);
+                DATA(np_enter);
+                DATA(np_exit);
+        } data;
+};
+
+#undef DATA
+
+const char* event2name(unsigned int id);
+u64 event_time(struct st_event_record* rec);
+
+void print_event(struct st_event_record *rec);
+void print_all(struct st_event_record *rec, unsigned int count);
+
+#endif