From b06db0322429df80ee0fe09d257520f0c5b71901 Mon Sep 17 00:00:00 2001 From: Bjoern Brandenburg Date: Wed, 23 Mar 2016 23:22:01 +0100 Subject: 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. --- include/eheap.h | 12 ++ include/heap.h | 379 ++++++++++++++++++++++++++++++++++++++++++++++++++ include/load.h | 92 ++++++++++++ include/sched_trace.h | 149 ++++++++++++++++++++ 4 files changed, 632 insertions(+) create mode 100644 include/eheap.h create mode 100644 include/heap.h create mode 100644 include/load.h create mode 100644 include/sched_trace.h (limited to 'include') 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 +#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 + * + * 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 + +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 -- cgit v1.2.2