From 44a8ade3ed5dc4810fd95c41dbe8ec3aa2fb0cf7 Mon Sep 17 00:00:00 2001 From: Gary Bressler Date: Mon, 1 Mar 2010 23:46:44 -0500 Subject: Reorganized tree, along with the visualizer --- .gitignore | 1 + README | 1 + TODO | 0 convert.py | 102 ++++ gedf_test.py | 163 ++++++ litmus01.pdf | Bin 0 -> 681011 bytes litmus02.pdf | Bin 0 -> 899823 bytes mac | 1 + naive_trace_reader.py | 165 ++++++ reader/__init__.py | 4 + reader/gedf_test.py | 163 ++++++ reader/naive_trace_reader.py | 165 ++++++ reader/runtests.py | 47 ++ reader/sample_script.py | 41 ++ reader/sample_script.py~ | 41 ++ reader/sanitizer.py | 53 ++ reader/stats.py | 39 ++ reader/stdout_printer.py | 69 +++ reader/test.py | 15 + reader/trace_reader.py | 245 ++++++++ runtests.py | 47 ++ sample_script.py | 41 ++ sample_traces/.runtests.py.swp | Bin 0 -> 12288 bytes sample_traces/st-g6-0.bin | Bin 0 -> 46656 bytes sample_traces/st-g6-1.bin | Bin 0 -> 53064 bytes sample_traces/st-g6-2.bin | Bin 0 -> 52368 bytes sample_traces/st-g6-3.bin | Bin 0 -> 54960 bytes sanitizer.py | 53 ++ stats.py | 39 ++ stdout_printer.py | 69 +++ trace_reader.py | 245 ++++++++ traces/g1.pdf | Bin 0 -> 12747 bytes traces/g2.pdf | Bin 0 -> 21284 bytes traces/g3.pdf | Bin 0 -> 18260 bytes traces/g4.pdf | Bin 0 -> 50607 bytes traces/g5.pdf | Bin 0 -> 141031 bytes traces/g6.pdf | Bin 0 -> 142968 bytes traces/heavy.ts | 9 + traces/heavy2.ts | 7 + traces/light.ts | 9 + traces/medium.ts | 7 + traces/mixed.ts | 15 + traces/st-g1-0.bin | Bin 0 -> 42528 bytes traces/st-g1-1.bin | Bin 0 -> 42768 bytes traces/st-g1-2.bin | Bin 0 -> 47592 bytes traces/st-g1-3.bin | Bin 0 -> 50496 bytes traces/st-g3-0.bin | Bin 0 -> 2640 bytes traces/st-g3-1.bin | Bin 0 -> 1872 bytes traces/st-g3-2.bin | Bin 0 -> 2088 bytes traces/st-g3-3.bin | Bin 0 -> 2832 bytes traces/st-g4-0.bin | Bin 0 -> 11208 bytes traces/st-g4-1.bin | Bin 0 -> 10848 bytes traces/st-g4-2.bin | Bin 0 -> 10392 bytes traces/st-g4-3.bin | Bin 0 -> 10536 bytes traces/st-g5-0.bin | Bin 0 -> 44904 bytes traces/st-g5-1.bin | Bin 0 -> 47520 bytes traces/st-g5-2.bin | Bin 0 -> 51552 bytes traces/st-g5-3.bin | Bin 0 -> 56064 bytes traces/st-g6-0.bin | Bin 0 -> 46656 bytes traces/st-g6-1.bin | Bin 0 -> 53064 bytes traces/st-g6-2.bin | Bin 0 -> 52368 bytes traces/st-g6-3.bin | Bin 0 -> 54960 bytes traces/st-heavy-0.bin | Bin 0 -> 33648 bytes traces/st-heavy-1.bin | Bin 0 -> 34224 bytes traces/st-heavy-2.bin | Bin 0 -> 35472 bytes traces/st-heavy-3.bin | Bin 0 -> 34008 bytes traces/st-heavy2-0.bin | Bin 0 -> 28608 bytes traces/st-heavy2-1.bin | Bin 0 -> 32352 bytes traces/st-heavy2-2.bin | Bin 0 -> 27864 bytes traces/st-heavy2-3.bin | Bin 0 -> 29424 bytes traces/st-heavy3-0.bin | Bin 0 -> 28896 bytes traces/st-heavy3-1.bin | Bin 0 -> 30936 bytes traces/st-heavy3-2.bin | Bin 0 -> 28704 bytes traces/st-heavy3-3.bin | Bin 0 -> 30144 bytes traces/st-mac-0.bin | Bin 0 -> 9288 bytes traces/st-mac-1.bin | Bin 0 -> 10152 bytes traces/st-mac-test-0.bin | Bin 0 -> 58944 bytes traces/st-mac2-0.bin | Bin 0 -> 10536 bytes traces/st-s1-0.bin | Bin 0 -> 47424 bytes traces/st-s1-1.bin | Bin 0 -> 61488 bytes traces/st-s1-2.bin | Bin 0 -> 57336 bytes traces/st-s1-3.bin | Bin 0 -> 48984 bytes traces/st-s2-0.bin | Bin 0 -> 82320 bytes traces/st-s2-1.bin | Bin 0 -> 135288 bytes traces/st-s2-2.bin | Bin 0 -> 93264 bytes traces/st-s2-3.bin | Bin 0 -> 58560 bytes traces/st-x10-0.bin | Bin 0 -> 44448 bytes traces/st-x10-1.bin | Bin 0 -> 7536 bytes traces/st-x10-2.bin | Bin 0 -> 30216 bytes traces/st-x10-3.bin | Bin 0 -> 7440 bytes traces/st-x11-0.bin | Bin 0 -> 33408 bytes traces/st-x11-1.bin | Bin 0 -> 34656 bytes traces/st-x11-2.bin | Bin 0 -> 33216 bytes traces/st-x11-3.bin | Bin 0 -> 33240 bytes traces/st-x12-0.bin | Bin 0 -> 80352 bytes traces/st-x12-1.bin | Bin 0 -> 174744 bytes traces/st-x12-2.bin | Bin 0 -> 90552 bytes traces/st-x12-3.bin | Bin 0 -> 104088 bytes traces/st-x13-0.bin | Bin 0 -> 72456 bytes traces/st-x13-1.bin | Bin 0 -> 315360 bytes traces/st-x13-2.bin | Bin 0 -> 318888 bytes traces/st-x13-3.bin | Bin 0 -> 258192 bytes traces/st-x14-0.bin | Bin 0 -> 73272 bytes traces/st-x14-1.bin | Bin 0 -> 336192 bytes traces/st-x14-2.bin | Bin 0 -> 309768 bytes traces/st-x14-3.bin | Bin 0 -> 268992 bytes traces/st-x15-0.bin | Bin 0 -> 86592 bytes traces/st-x15-1.bin | Bin 0 -> 371160 bytes traces/st-x15-2.bin | Bin 0 -> 365496 bytes traces/st-x15-3.bin | Bin 0 -> 301728 bytes traces/st-x16-0.bin | Bin 0 -> 44016 bytes traces/st-x16-1.bin | Bin 0 -> 77568 bytes traces/st-x16-2.bin | Bin 0 -> 76296 bytes traces/st-x16-3.bin | Bin 0 -> 65040 bytes traces/st-x17-0.bin | Bin 0 -> 203472 bytes traces/st-x17-1.bin | Bin 0 -> 484368 bytes traces/st-x17-2.bin | Bin 0 -> 331704 bytes traces/st-x17-3.bin | Bin 0 -> 280800 bytes traces/st-x18-0.bin | Bin 0 -> 49632 bytes traces/st-x18-1.bin | Bin 0 -> 61488 bytes traces/st-x18-2.bin | Bin 0 -> 60264 bytes traces/st-x18-3.bin | Bin 0 -> 54048 bytes traces/st-x19-0.bin | Bin 0 -> 81888 bytes traces/st-x19-1.bin | Bin 0 -> 185208 bytes traces/st-x19-2.bin | Bin 0 -> 135936 bytes traces/st-x19-3.bin | Bin 0 -> 102552 bytes traces/st-x2-0.bin | Bin 0 -> 24480 bytes traces/st-x2-1.bin | Bin 0 -> 25176 bytes traces/st-x2-2.bin | Bin 0 -> 1632 bytes traces/st-x2-3.bin | Bin 0 -> 1056 bytes traces/st-x3-0.bin | Bin 0 -> 34752 bytes traces/st-x3-1.bin | Bin 0 -> 36936 bytes traces/st-x3-2.bin | Bin 0 -> 36576 bytes traces/st-x3-3.bin | Bin 0 -> 33888 bytes traces/st-x4-0.bin | Bin 0 -> 20640 bytes traces/st-x4-1.bin | Bin 0 -> 22632 bytes traces/st-x4-2.bin | Bin 0 -> 1800 bytes traces/st-x4-3.bin | Bin 0 -> 936 bytes traces/st-x5-0.bin | Bin 0 -> 16824 bytes traces/st-x5-1.bin | Bin 0 -> 31824 bytes traces/st-x5-2.bin | Bin 0 -> 2544 bytes traces/st-x5-3.bin | Bin 0 -> 30048 bytes traces/st-x6-0.bin | Bin 0 -> 22632 bytes traces/st-x6-1.bin | Bin 0 -> 22728 bytes traces/st-x6-2.bin | Bin 0 -> 1848 bytes traces/st-x6-3.bin | Bin 0 -> 720 bytes traces/st-x7-0.bin | Bin 0 -> 22032 bytes traces/st-x7-1.bin | Bin 0 -> 22848 bytes traces/st-x7-2.bin | Bin 0 -> 960 bytes traces/st-x7-3.bin | Bin 0 -> 936 bytes traces/st-x9-0.bin | Bin 0 -> 33096 bytes traces/st-x9-1.bin | Bin 0 -> 33384 bytes traces/st-x9-2.bin | Bin 0 -> 33072 bytes traces/st-x9-3.bin | Bin 0 -> 33000 bytes traces/st-xxx-0.bin | Bin 0 -> 22392 bytes traces/st-xxx-1.bin | Bin 0 -> 24120 bytes traces/st-xxx-2.bin | Bin 0 -> 23784 bytes traces/st-xxx-3.bin | Bin 0 -> 1008 bytes traces/st0.fg | Bin 0 -> 319488 bytes traces/st1.fg | Bin 0 -> 286720 bytes traces/stg20.bin | Bin 0 -> 1416 bytes traces/stg21.bin | Bin 0 -> 672 bytes traces/stg22.bin | Bin 0 -> 744 bytes traces/stg23.bin | Bin 0 -> 888 bytes traces/test.pdf | Bin 0 -> 3893 bytes traces/x11.pdf | Bin 0 -> 53568 bytes traces/x12.pdf | Bin 0 -> 13280 bytes traces/x13.pdf | Bin 0 -> 113497 bytes traces/x14.pdf | Bin 0 -> 113369 bytes traces/x15.pdf | Bin 0 -> 138880 bytes traces/x16.pdf | Bin 0 -> 80694 bytes traces/x17.pdf | Bin 0 -> 374581 bytes traces/x18.pdf | Bin 0 -> 80777 bytes traces/x19.pdf | Bin 0 -> 176625 bytes visualizer.py | 31 + viz/__init__.py | 10 + viz/draw.py | 1254 ++++++++++++++++++++++++++++++++++++++++ viz/format.py | 92 +++ viz/renderer.py | 40 ++ viz/schedule.py | 571 ++++++++++++++++++ viz/util.py | 9 + viz/viewer.py | 193 +++++++ 182 files changed, 4056 insertions(+) create mode 100644 .gitignore create mode 100644 README create mode 100644 TODO create mode 100644 convert.py create mode 100644 gedf_test.py create mode 100644 litmus01.pdf create mode 100644 litmus02.pdf create mode 160000 mac create mode 100644 naive_trace_reader.py create mode 100644 reader/__init__.py create mode 100644 reader/gedf_test.py create mode 100644 reader/naive_trace_reader.py create mode 100755 reader/runtests.py create mode 100755 reader/sample_script.py create mode 100644 reader/sample_script.py~ create mode 100644 reader/sanitizer.py create mode 100644 reader/stats.py create mode 100644 reader/stdout_printer.py create mode 100755 reader/test.py create mode 100644 reader/trace_reader.py create mode 100755 runtests.py create mode 100755 sample_script.py create mode 100644 sample_traces/.runtests.py.swp create mode 100644 sample_traces/st-g6-0.bin create mode 100644 sample_traces/st-g6-1.bin create mode 100644 sample_traces/st-g6-2.bin create mode 100644 sample_traces/st-g6-3.bin create mode 100644 sanitizer.py create mode 100644 stats.py create mode 100644 stdout_printer.py create mode 100644 trace_reader.py create mode 100644 traces/g1.pdf create mode 100644 traces/g2.pdf create mode 100644 traces/g3.pdf create mode 100644 traces/g4.pdf create mode 100644 traces/g5.pdf create mode 100644 traces/g6.pdf create mode 100644 traces/heavy.ts create mode 100644 traces/heavy2.ts create mode 100644 traces/light.ts create mode 100644 traces/medium.ts create mode 100644 traces/mixed.ts create mode 100644 traces/st-g1-0.bin create mode 100644 traces/st-g1-1.bin create mode 100644 traces/st-g1-2.bin create mode 100644 traces/st-g1-3.bin create mode 100644 traces/st-g3-0.bin create mode 100644 traces/st-g3-1.bin create mode 100644 traces/st-g3-2.bin create mode 100644 traces/st-g3-3.bin create mode 100644 traces/st-g4-0.bin create mode 100644 traces/st-g4-1.bin create mode 100644 traces/st-g4-2.bin create mode 100644 traces/st-g4-3.bin create mode 100644 traces/st-g5-0.bin create mode 100644 traces/st-g5-1.bin create mode 100644 traces/st-g5-2.bin create mode 100644 traces/st-g5-3.bin create mode 100644 traces/st-g6-0.bin create mode 100644 traces/st-g6-1.bin create mode 100644 traces/st-g6-2.bin create mode 100644 traces/st-g6-3.bin create mode 100644 traces/st-heavy-0.bin create mode 100644 traces/st-heavy-1.bin create mode 100644 traces/st-heavy-2.bin create mode 100644 traces/st-heavy-3.bin create mode 100644 traces/st-heavy2-0.bin create mode 100644 traces/st-heavy2-1.bin create mode 100644 traces/st-heavy2-2.bin create mode 100644 traces/st-heavy2-3.bin create mode 100644 traces/st-heavy3-0.bin create mode 100644 traces/st-heavy3-1.bin create mode 100644 traces/st-heavy3-2.bin create mode 100644 traces/st-heavy3-3.bin create mode 100644 traces/st-mac-0.bin create mode 100644 traces/st-mac-1.bin create mode 100644 traces/st-mac-test-0.bin create mode 100644 traces/st-mac2-0.bin create mode 100644 traces/st-s1-0.bin create mode 100644 traces/st-s1-1.bin create mode 100644 traces/st-s1-2.bin create mode 100644 traces/st-s1-3.bin create mode 100644 traces/st-s2-0.bin create mode 100644 traces/st-s2-1.bin create mode 100644 traces/st-s2-2.bin create mode 100644 traces/st-s2-3.bin create mode 100644 traces/st-x10-0.bin create mode 100644 traces/st-x10-1.bin create mode 100644 traces/st-x10-2.bin create mode 100644 traces/st-x10-3.bin create mode 100644 traces/st-x11-0.bin create mode 100644 traces/st-x11-1.bin create mode 100644 traces/st-x11-2.bin create mode 100644 traces/st-x11-3.bin create mode 100644 traces/st-x12-0.bin create mode 100644 traces/st-x12-1.bin create mode 100644 traces/st-x12-2.bin create mode 100644 traces/st-x12-3.bin create mode 100644 traces/st-x13-0.bin create mode 100644 traces/st-x13-1.bin create mode 100644 traces/st-x13-2.bin create mode 100644 traces/st-x13-3.bin create mode 100644 traces/st-x14-0.bin create mode 100644 traces/st-x14-1.bin create mode 100644 traces/st-x14-2.bin create mode 100644 traces/st-x14-3.bin create mode 100644 traces/st-x15-0.bin create mode 100644 traces/st-x15-1.bin create mode 100644 traces/st-x15-2.bin create mode 100644 traces/st-x15-3.bin create mode 100644 traces/st-x16-0.bin create mode 100644 traces/st-x16-1.bin create mode 100644 traces/st-x16-2.bin create mode 100644 traces/st-x16-3.bin create mode 100644 traces/st-x17-0.bin create mode 100644 traces/st-x17-1.bin create mode 100644 traces/st-x17-2.bin create mode 100644 traces/st-x17-3.bin create mode 100644 traces/st-x18-0.bin create mode 100644 traces/st-x18-1.bin create mode 100644 traces/st-x18-2.bin create mode 100644 traces/st-x18-3.bin create mode 100644 traces/st-x19-0.bin create mode 100644 traces/st-x19-1.bin create mode 100644 traces/st-x19-2.bin create mode 100644 traces/st-x19-3.bin create mode 100644 traces/st-x2-0.bin create mode 100644 traces/st-x2-1.bin create mode 100644 traces/st-x2-2.bin create mode 100644 traces/st-x2-3.bin create mode 100644 traces/st-x3-0.bin create mode 100644 traces/st-x3-1.bin create mode 100644 traces/st-x3-2.bin create mode 100644 traces/st-x3-3.bin create mode 100644 traces/st-x4-0.bin create mode 100644 traces/st-x4-1.bin create mode 100644 traces/st-x4-2.bin create mode 100644 traces/st-x4-3.bin create mode 100644 traces/st-x5-0.bin create mode 100644 traces/st-x5-1.bin create mode 100644 traces/st-x5-2.bin create mode 100644 traces/st-x5-3.bin create mode 100644 traces/st-x6-0.bin create mode 100644 traces/st-x6-1.bin create mode 100644 traces/st-x6-2.bin create mode 100644 traces/st-x6-3.bin create mode 100644 traces/st-x7-0.bin create mode 100644 traces/st-x7-1.bin create mode 100644 traces/st-x7-2.bin create mode 100644 traces/st-x7-3.bin create mode 100644 traces/st-x9-0.bin create mode 100644 traces/st-x9-1.bin create mode 100644 traces/st-x9-2.bin create mode 100644 traces/st-x9-3.bin create mode 100644 traces/st-xxx-0.bin create mode 100644 traces/st-xxx-1.bin create mode 100644 traces/st-xxx-2.bin create mode 100644 traces/st-xxx-3.bin create mode 100644 traces/st0.fg create mode 100644 traces/st1.fg create mode 100644 traces/stg20.bin create mode 100644 traces/stg21.bin create mode 100644 traces/stg22.bin create mode 100644 traces/stg23.bin create mode 100644 traces/test.pdf create mode 100644 traces/x11.pdf create mode 100644 traces/x12.pdf create mode 100644 traces/x13.pdf create mode 100644 traces/x14.pdf create mode 100644 traces/x15.pdf create mode 100644 traces/x16.pdf create mode 100644 traces/x17.pdf create mode 100644 traces/x18.pdf create mode 100644 traces/x19.pdf create mode 100755 visualizer.py create mode 100644 viz/__init__.py create mode 100644 viz/draw.py create mode 100644 viz/format.py create mode 100644 viz/renderer.py create mode 100644 viz/schedule.py create mode 100644 viz/util.py create mode 100644 viz/viewer.py diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..0d20b64 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +*.pyc diff --git a/README b/README new file mode 100644 index 0000000..b2da190 --- /dev/null +++ b/README @@ -0,0 +1 @@ +See the LITMUS Wiki page for an explanation of this tool. diff --git a/TODO b/TODO new file mode 100644 index 0000000..e69de29 diff --git a/convert.py b/convert.py new file mode 100644 index 0000000..1db4ad0 --- /dev/null +++ b/convert.py @@ -0,0 +1,102 @@ +#!/usr/bin/env python +from viz.schedule import * +from reader.trace_reader import * + +"""Class that interprets the raw trace data, outputting it +to a Python schedule object. + +Doesn't do any checking on the logic of the schedule (except to +check for corrupted data)""" + +def get_type(type_num): + """Return the binary data type, given the type_num""" + return Trace.DATA_TYPES[type_num] + +def get_type_num(type): + nums = dict(zip(Trace.DATA_TYPES, range(0, 11))) + return nums[type] + +def _get_job_from_record(sched, record): + tname = _pid_to_task_name(record.pid) + job_no = record.job + if tname not in sched.get_tasks(): + sched.add_task(Task(tname, [])) + if job_no not in sched.get_tasks()[tname].get_jobs(): + sched.get_tasks()[tname].add_job(Job(job_no, [])) + job = sched.get_tasks()[tname].get_jobs()[job_no] + return job + +def convert_trace_to_schedule(stream): + """The main function of interest in this module. Coverts a stream of records + to a Schedule object.""" + def noop(): + pass + + num_cpus, stream = _find_num_cpus(stream) + sched = Schedule('sched', num_cpus) + for record in stream: + #if record.record_type == 'meta': + # if record.type_name == 'num_cpus': + # sched = Schedule('sched', record.num_cpus) + # continue + if record.record_type == 'event': + job = _get_job_from_record(sched, record) + cpu = record.cpu + + if not hasattr(record, 'deadline'): + record.deadline = None + + actions = { + 'name' : (noop), + 'params' : (noop), + 'release' : (lambda : + (job.add_event(ReleaseEvent(record.when, cpu)), + job.add_event(DeadlineEvent(record.deadline, cpu)))), + 'switch_to' : (lambda : + job.add_event(SwitchToEvent(record.when, cpu))), + 'switch_away' : lambda : + job.add_event(SwitchAwayEvent(record.when, cpu)), + 'assign' : (noop), + 'completion' : (lambda : + job.add_event(CompleteEvent(record.when, cpu))), + 'block' : (lambda : + job.add_event(SuspendEvent(record.when, cpu))), + 'resume' : (lambda : + job.add_event(ResumeEvent(record.when, cpu))), + 'sys_release' : (noop) + } + + actions[record.type_name]() + + elif record.record_type == 'error': + job = _get_job_from_record(sched, record.job) + + actions = { + 'inversion_start' : (lambda : + job.add_event(InversionStartEvent(record.job.inversion_start))), + 'inversion_end' : (lambda : + job.add_event(InversionEndEvent(record.job.inversion_end))) + } + + actions[record.type_name]() + + return sched + +def _pid_to_task_name(pid): + """Converts a PID to an appropriate name for a task.""" + return str(pid) + +def _find_num_cpus(stream): + """Determines the number of CPUs used by scanning the binary format.""" + max = 0 + stream_list = [] + for record in stream: + stream_list.append(record) + if record.record_type == 'event': + if record.cpu > max: + max = record.cpu + + def recycle(l): + for record in l: + yield record + return (max + 1, recycle(stream_list)) diff --git a/gedf_test.py b/gedf_test.py new file mode 100644 index 0000000..8457901 --- /dev/null +++ b/gedf_test.py @@ -0,0 +1,163 @@ +############################################################################### +# Description +############################################################################### + +# G-EDF Test + +############################################################################### +# Imports +############################################################################### + +import copy + + +############################################################################### +# Public Functions +############################################################################### + +def gedf_test(stream): + + # Two lists to model the system: tasks occupying a CPU and tasks eligible + # to do so. Also, m = the number of CPUs. + eligible = [] + on_cpu = [] + m = None + + # Time of the last record we saw. Only run the G-EDF test when the time + # is updated. + last_time = None + + for record in stream: + if record.record_type != "event": + if record.record_type == "meta" and record.type_name == "num_cpus": + m = record.num_cpus + continue + + # Check for inversion starts and ends and yield them. + # Only to the check when time has moved forward. + # (It is common to have records with simultaneous timestamps.) + if last_time is not None and last_time != record.when: + errors = _gedf_check(eligible,on_cpu,record.when,m) + for error in errors: + yield error + + # Add a newly-released Job to the eligible queue + if record.type_name == 'release': + eligible.append(Job(record)) + + # Move a Job from the eligible queue to on_cpu + elif record.type_name == 'switch_to': + pos = _find_job(record,eligible) + job = eligible[pos] + del eligible[pos] + on_cpu.append(job) + + # Mark a Job as completed. + # The only time a Job completes when it is not on a + # CPU is when it is the last job of the task. + elif record.type_name == 'completion': + pos = _find_job(record,on_cpu) + if pos is not None: + on_cpu[pos].is_complete = True + else: + pos = _find_job(record,eligible) + del eligible[pos] + + # A job is switched away from a CPU. If it has + # been marked as complete, remove it from the model. + elif record.type_name == 'switch_away': + pos = _find_job(record,on_cpu) + job = on_cpu[pos] + del on_cpu[pos] + if job.is_complete == False: + eligible.append(job) + + last_time = record.when + yield record + +############################################################################### +# Private Functions +############################################################################### + +# Internal representation of a Job +class Job(object): + def __init__(self, record): + self.pid = record.pid + self.job = record.job + self.deadline = record.deadline + self.is_complete = False + self.inversion_start = None + self.inversion_end = None + def __str__(self): + return "(%d.%d:%d)" % (self.pid,self.job,self.deadline) + +# G-EDF errors: the start or end of an inversion +class Error(object): + def __init__(self, job, eligible, on_cpu): + self.job = copy.copy(job) + self.eligible = copy.copy(eligible) + self.on_cpu = copy.copy(on_cpu) + self.record_type = 'error' + if job.inversion_end is None: + self.type_name = 'inversion_start' + else: + self.type_name = 'inversion_end' + +# Returns the position of a Job in a list, or None +def _find_job(record,list): + for i in range(0,len(list)): + if list[i].pid == record.pid and list[i].job == record.job: + return i + return None + +# Return records for any inversion_starts and inversion_ends +def _gedf_check(eligible,on_cpu,when,m): + + # List of error records to be returned + errors = [] + + # List of all jobs that are not complete + all = [] + for x in on_cpu: + if x.is_complete is not True: + all.append(x) + all += eligible + + # Sort by on_cpu and then by deadline. sort() is guaranteed to be stable. + # Thus, this gives us jobs ordered by deadline with preference to those + # actually running. + all.sort(key=lambda x: 0 if (x in on_cpu) else 1) + all.sort(key=lambda x: x.deadline) + + # Check those that actually should be running + for x in range(0,min(m,len(all))): + job = all[x] + + # It's not running and an inversion_start has not been recorded + if job not in on_cpu and job.inversion_start is None: + job.inversion_start = when + errors.append(Error(job, eligible, on_cpu)) + + # It is running and an inversion_start exists (i.e. it it still + # marked as being inverted) + elif job in on_cpu and job.inversion_start is not None: + job.inversion_end = when + errors.append(Error(job, eligible, on_cpu)) + job.inversion_start = None + job.inversion_end = None + + # Check those that actually should not be running + for x in range(m,len(all)): + job = all[x] + + # It actually is running. We don't care. + + # It isn't running, but an inversion_start exists (i.e. it is still + # marked as being inverted) + if job not in on_cpu and job.inversion_start is not None: + job.inversion_end = when + errors.append(Error(job, eligible, on_cpu)) + job.inversion_start = None + job.inversion_end = None + + return errors diff --git a/litmus01.pdf b/litmus01.pdf new file mode 100644 index 0000000..4fba2fa Binary files /dev/null and b/litmus01.pdf differ diff --git a/litmus02.pdf b/litmus02.pdf new file mode 100644 index 0000000..bcfdcab Binary files /dev/null and b/litmus02.pdf differ diff --git a/mac b/mac new file mode 160000 index 0000000..cd6e43f --- /dev/null +++ b/mac @@ -0,0 +1 @@ +Subproject commit cd6e43f37856f7fe6b60e0e2ae45f864a4bd6d64 diff --git a/naive_trace_reader.py b/naive_trace_reader.py new file mode 100644 index 0000000..0f117b8 --- /dev/null +++ b/naive_trace_reader.py @@ -0,0 +1,165 @@ +############################################################################### +# Description +############################################################################### + +# trace_reader(files) returns an iterator which produces records +# OUT OF ORDER from the files given. (the param is a list of files.) +# +# The non-naive trace_reader has a lot of complex logic which attempts to +# produce records in order (even though they are being pulled from multiple +# files which themselves are only approximately ordered). This trace_reader +# attempts to be as simple as possible and is used in the unit tests to +# make sure the total number of records read by the normal trace_reader is +# the same as the number of records read by this one. + +############################################################################### +# Imports +############################################################################### + +import struct + + +############################################################################### +# Public functions +############################################################################### + +# Generator function returning an iterable over records in a trace file. +def trace_reader(files): + for file in files: + f = open(file,'rb') + while True: + data = f.read(RECORD_HEAD_SIZE) + try: + type_num = struct.unpack_from('b',data)[0] + except struct.error: + break #We read to the end of the file + type = _get_type(type_num) + try: + values = struct.unpack_from(StHeader.format + + type.format,data) + record_dict = dict(zip(type.keys,values)) + except struct.error: + f.close() + print "Invalid record detected, stopping." + exit() + + # Convert the record_dict into an object + record = _dict2obj(record_dict) + + # Give it a type name (easier to work with than type number) + record.type_name = _get_type_name(type_num) + + # All records should have a 'record type' field. + # e.g. these are 'event's as opposed to 'error's + record.record_type = "event" + + # If there is no timestamp, set the time to 0 + if 'when' not in record.__dict__.keys(): + record.when = 0 + + yield record + +############################################################################### +# Private functions +############################################################################### + +# Convert a dict into an object +def _dict2obj(d): + class Obj: pass + o = Obj() + for key in d.keys(): + o.__dict__[key] = d[key] + return o + +############################################################################### +# Trace record data types and accessor functions +############################################################################### + +# Each class below represents a type of event record. The format attribute +# specifies how to decode the binary record and the keys attribute +# specifies how to name the pieces of information decoded. Note that all +# event records have a common initial 24 bytes, represented by the StHeader +# class. + +RECORD_HEAD_SIZE = 24 + +class StHeader(object): + format = ' output). + +# Import the modules we need. You should not need to know about +# their internals. +import trace_reader +import sanitizer +import gedf_test +import stats +import stdout_printer + +# Specify your trace files +g6 = [ +'../sample_traces/st-g6-0.bin', +'../sample_traces/st-g6-1.bin', +'../sample_traces/st-g6-2.bin', +'../sample_traces/st-g6-3.bin', +] + +# Here is an example of a custom filter function. +# It will remove from the error stream all inversion_end records indicating +# an inversion of less than 4000000 time units. Thus, you can grep through +# the output looking 'Inversion end' and find only errors for particularly +# long inversions. This is commented out in the pipeline (below) since you +# probably don't want it in general. +def my_filter(record): + if record.record_type == 'error' and record.type_name == 'inversion_end': + if record.job.inversion_end - record.job.inversion_start < 4000000: + return False + return True + +# Pipeline +stream = trace_reader.trace_reader(g6) # Read events from traces +stream = sanitizer.sanitizer(stream) # Remove garbage events +stream = gedf_test.gedf_test(stream) # Produce G-EDF error records +stream = stats.stats(stream) # Produce a statistics record +#stream = filter(my_filter, stream) # Filter some records before printing +stdout_printer.stdout_printer(stream) # Print records to stdout diff --git a/reader/sample_script.py~ b/reader/sample_script.py~ new file mode 100644 index 0000000..c3b7843 --- /dev/null +++ b/reader/sample_script.py~ @@ -0,0 +1,41 @@ +#!/usr/bin/python + +# This is a sample script for using the tool. I would recommend copying +# this and modifying it to suit your needs for a particular test. Make +# sure you redirect the output to a file (e.g. ./sample_script.py > output). + +# Import the modules we need. You should not need to know about +# their internals. +import trace_reader +import sanitizer +import gedf_test +import stats +import stdout_printer + +# Specify your trace files +g6 = [ +'./sample_traces/st-g6-0.bin', +'./sample_traces/st-g6-1.bin', +'./sample_traces/st-g6-2.bin', +'./sample_traces/st-g6-3.bin', +] + +# Here is an example of a custom filter function. +# It will remove from the error stream all inversion_end records indicating +# an inversion of less than 4000000 time units. Thus, you can grep through +# the output looking 'Inversion end' and find only errors for particularly +# long inversions. This is commented out in the pipeline (below) since you +# probably don't want it in general. +def my_filter(record): + if record.record_type == 'error' and record.type_name == 'inversion_end': + if record.job.inversion_end - record.job.inversion_start < 4000000: + return False + return True + +# Pipeline +stream = trace_reader.trace_reader(g6) # Read events from traces +stream = sanitizer.sanitizer(stream) # Remove garbage events +stream = gedf_test.gedf_test(stream) # Produce G-EDF error records +stream = stats.stats(stream) # Produce a statistics record +#stream = filter(my_filter, stream) # Filter some records before printing +stdout_printer.stdout_printer(stream) # Print records to stdout diff --git a/reader/sanitizer.py b/reader/sanitizer.py new file mode 100644 index 0000000..79315cc --- /dev/null +++ b/reader/sanitizer.py @@ -0,0 +1,53 @@ +############################################################################### +# Description +############################################################################### + +# Sanitize input. (There are a number of goofy issues with the sched_trace +# output.) + +############################################################################### +# Public functions +############################################################################### + +def sanitizer(stream): + + job_2s_released = [] # list of tasks which have released their job 2s + jobs_switched_to = [] + + for record in stream: + + # Ignore records which are not events (e.g. the num_cpus record) + if record.record_type != 'event': + yield record + continue + + # All records with job < 2 are garbage + if record.job < 2: + continue + + # Some records with job == 2 are garbage + if record.job==2: + + # There is a duplicate release of every job 2 + # This will throw away the second one + if record.type_name == 'release': + if record.pid in job_2s_released: + continue + else: + job_2s_released.append(record.pid) + + # Job 2 has a resume that is garbage + if record.type_name == 'resume': + continue + + # By default, the switch_away for a job (after it has completed) + # is maked as being for job+1, which has never been switched to. + # We can correct this if we note which jobs really + # have been switched to. + if record.type_name == 'switch_to': + jobs_switched_to.append((record.pid,record.job)) + if record.type_name == 'switch_away': + if (record.pid,record.job) not in jobs_switched_to: + record.job -= 1 + + yield record diff --git a/reader/stats.py b/reader/stats.py new file mode 100644 index 0000000..34a842f --- /dev/null +++ b/reader/stats.py @@ -0,0 +1,39 @@ +############################################################################### +# Description +############################################################################### +# Compute and produce statistics + + +############################################################################### +# Public Functions +############################################################################### + +def stats(stream): + min_inversion = -1 + max_inversion = -1 + sum_inversions = 0 + num_inversions = 0 + for record in stream: + if record.type_name == 'inversion_end': + length = record.job.inversion_end - record.job.inversion_start + if length > 0: + num_inversions += 1 + if length > max_inversion: + max_inversion = length + if length < min_inversion or min_inversion == -1: + min_inversion = length + sum_inversions += length + yield record + if num_inversions > 0: + avg_inversion = int(sum_inversions / num_inversions) + else: + avg_inversion = 0 + class Obj(object): pass + rec = Obj() + rec.record_type = "meta" + rec.type_name = "stats" + rec.num_inversions = num_inversions + rec.min_inversion = min_inversion + rec.max_inversion = max_inversion + rec.avg_inversion = avg_inversion + yield rec diff --git a/reader/stdout_printer.py b/reader/stdout_printer.py new file mode 100644 index 0000000..f8d9a84 --- /dev/null +++ b/reader/stdout_printer.py @@ -0,0 +1,69 @@ +############################################################################### +# Description +############################################################################### + +# Prints records to standard out + +############################################################################### +# Public functions +############################################################################### + +def stdout_printer(stream): + for record in stream: + if record.record_type == "event": + _print_event(record) + elif record.record_type == "meta" and record.type_name == "stats": + _print_stats(record) + elif record.record_type == "error" and record.type_name == 'inversion_start': + _print_inversion_start(record) + elif record.record_type == "error" and record.type_name == 'inversion_end': + _print_inversion_end(record) + else: + continue + print "" + +############################################################################### +# Private functions +############################################################################### + +def _print_event(record): + print "Job: %d.%d" % (record.pid,record.job) + print "Type: %s" % (record.type_name) + print "Time: %d" % (record.when) + +def _print_inversion_start(record): + print "Type: %s" % ("Inversion start") + print "Time: %d" % (record.job.inversion_start) + print "Job: %d.%d" % (record.job.pid,record.job.job) + print "Deadline: %d" % (record.job.deadline) + print "Eligible: ", + for job in record.eligible: + print str(job) + " ", + print + print "On CPU: ", + for job in record.on_cpu: + print str(job) + " ", + print #newline + +def _print_inversion_end(record): + print "Type: %s" % ("Inversion end") + print "Time: %d" % (record.job.inversion_end) + print "Duration: %d" % ( + record.job.inversion_end - record.job.inversion_start) + print "Job: %d.%d" % (record.job.pid,record.job.job) + print "Deadline: %d" % (record.job.deadline) + print "Eligible: ", + for job in record.eligible: + print str(job) + " ", + print + print "On CPU: ", + for job in record.on_cpu: + print str(job) + " ", + print #newline + +def _print_stats(record): + print "Inversion statistics" + print "Num inversions: %d" % (record.num_inversions) + print "Min inversion: %d" % (record.min_inversion) + print "Max inversion: %d" % (record.max_inversion) + print "Avg inversion: %d" % (record.avg_inversion) diff --git a/reader/test.py b/reader/test.py new file mode 100755 index 0000000..b260314 --- /dev/null +++ b/reader/test.py @@ -0,0 +1,15 @@ +#!/usr/bin/python + +import cairo + +if __name__ == '__main__': + surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, 500, 500) + ctx = cairo.Context(surface) + ctx.move_to(10, 10) + ctx.line_to(-100, 10) + ctx.set_line_width(2) + + ctx.move_to(10, 10) + ctx.line_to(20, 10) + ctx.stroke() + surface.write_to_png('test.png') diff --git a/reader/trace_reader.py b/reader/trace_reader.py new file mode 100644 index 0000000..a4ff964 --- /dev/null +++ b/reader/trace_reader.py @@ -0,0 +1,245 @@ +############################################################################### +# Description +############################################################################### + +# trace_reader(files) returns an iterator which produces records +# in order from the files given. (the param is a list of files.) +# +# Each record is just a Python object. It is guaranteed to have the following +# attributes: +# - 'pid': pid of the task +# - 'job': job number for that task +# - 'cpu', given by LITMUS +# - 'when', given by LITMUS as a timestamp. LITMUS does not provide a +# timestamp for all records. In this case, when is set to 0. +# - 'type', a numerical value given by LITMUS +# - 'type_name', a human-readable name defined in this module +# - 'record_type', set to 'event' by this module (to distinguish from, e.g., +# error records produced elsewhere). +# - Possible additional attributes, depending on the type of record. +# +# To find out exactly what attributes are set for each record type, look at +# the trace-parsing information at the bottom of this file. + +############################################################################### +# Imports +############################################################################### + +import struct + + +############################################################################### +# Public functions +############################################################################### + +# Generator function returning an iterable over records in a trace file. +def trace_reader(files): + + # Yield a record indicating the number of CPUs, used by the G-EDF test + class Obj: pass + record = Obj() + record.record_type = "meta" + record.type_name = "num_cpus" + record.num_cpus = len(files) + yield record + + # Create iterators for each file and a buffer to store records in + file_iters = [] # file iterators + file_iter_buff = [] # file iterator buffers + for file in files: + file_iter = _get_file_iter(file) + file_iters.append(file_iter) + file_iter_buff.append([file_iter.next()]) + + # We keep 100 records in each buffer and then keep the buffer sorted + # This is because records may have been recorded slightly out of order + # This cannot guarantee records are produced in order, but it makes it + # overwhelmingly probably. + for x in range(0,len(file_iter_buff)): + for y in range(0,100): + file_iter_buff[x].append(file_iters[x].next()) + for x in range(0,len(file_iter_buff)): + file_iter_buff[x] = sorted(file_iter_buff[x],key=lambda rec: rec.when) + + # Remember the time of the last record. This way, we can make sure records + # truly are produced in monotonically increasing order by time and terminate + # fatally if they are not. + last_time = None + + # Keep pulling records as long as we have a buffer + while len(file_iter_buff) > 0: + + # Select the earliest record from those at the heads of the buffers + earliest = -1 + buff_to_refill = -1 + for x in range(0,len(file_iter_buff)): + if earliest==-1 or file_iter_buff[x][0].when < earliest.when: + earliest = file_iter_buff[x][0] + buff_to_refill = x + + # Take it out of the buffer + del file_iter_buff[buff_to_refill][0] + + # Try to append a new record to the buffer (if there is another) and + # then keep the buffer sorted + try: + file_iter_buff[buff_to_refill].append(file_iters[buff_to_refill].next()) + file_iter_buff[buff_to_refill] = sorted(file_iter_buff[buff_to_refill], + key=lambda rec: rec.when) + + # If there aren't any more records, fine. Unless the buffer is also empty. + # If that is the case, delete the buffer. + except StopIteration: + if len(file_iter_buff[buff_to_refill]) < 1: + del file_iter_buff[buff_to_refill] + del file_iters[buff_to_refill] + + # Check for monotonically increasing time + if last_time is not None and earliest.when < last_time: + exit("FATAL ERROR: trace_reader.py: out-of-order record produced") + else: + last_time = earliest.when + + # Yield the record + yield earliest + +############################################################################### +# Private functions +############################################################################### + +# Returns an iterator to pull records from a file +def _get_file_iter(file): + f = open(file,'rb') + while True: + data = f.read(RECORD_HEAD_SIZE) + try: + type_num = struct.unpack_from('b',data)[0] + except struct.error: + break #We read to the end of the file + type = _get_type(type_num) + try: + values = struct.unpack_from(StHeader.format + + type.format,data) + record_dict = dict(zip(type.keys,values)) + except struct.error: + f.close() + print "Invalid record detected, stopping." + exit() + + # Convert the record_dict into an object + record = _dict2obj(record_dict) + + # Give it a type name (easier to work with than type number) + record.type_name = _get_type_name(type_num) + + # All records should have a 'record type' field. + # e.g. these are 'event's as opposed to 'error's + record.record_type = "event" + + # If there is no timestamp, set the time to 0 + if 'when' not in record.__dict__.keys(): + record.when = 0 + + yield record + +# Convert a dict into an object +def _dict2obj(d): + class Obj(object): pass + o = Obj() + for key in d.keys(): + o.__dict__[key] = d[key] + return o + +############################################################################### +# Trace record data types and accessor functions +############################################################################### + +# Each class below represents a type of event record. The format attribute +# specifies how to decode the binary record and the keys attribute +# specifies how to name the pieces of information decoded. Note that all +# event records have a common initial 24 bytes, represented by the StHeader +# class. + +RECORD_HEAD_SIZE = 24 + +class StHeader: + format = ' output). + +# Import the modules we need. You should not need to know about +# their internals. +import trace_reader +import sanitizer +import gedf_test +import stats +import stdout_printer + +# Specify your trace files +g6 = [ +'./sample_traces/st-g6-0.bin', +'./sample_traces/st-g6-1.bin', +'./sample_traces/st-g6-2.bin', +'./sample_traces/st-g6-3.bin', +] + +# Here is an example of a custom filter function. +# It will remove from the error stream all inversion_end records indicating +# an inversion of less than 4000000 time units. Thus, you can grep through +# the output looking 'Inversion end' and find only errors for particularly +# long inversions. This is commented out in the pipeline (below) since you +# probably don't want it in general. +def my_filter(record): + if record.record_type == 'error' and record.type_name == 'inversion_end': + if record.job.inversion_end - record.job.inversion_start < 4000000: + return False + return True + +# Pipeline +stream = trace_reader.trace_reader(g6) # Read events from traces +stream = sanitizer.sanitizer(stream) # Remove garbage events +stream = gedf_test.gedf_test(stream) # Produce G-EDF error records +stream = stats.stats(stream) # Produce a statistics record +#stream = filter(my_filter, stream) # Filter some records before printing +stdout_printer.stdout_printer(stream) # Print records to stdout diff --git a/sample_traces/.runtests.py.swp b/sample_traces/.runtests.py.swp new file mode 100644 index 0000000..d9a9acd Binary files /dev/null and b/sample_traces/.runtests.py.swp differ diff --git a/sample_traces/st-g6-0.bin b/sample_traces/st-g6-0.bin new file mode 100644 index 0000000..cebc7fd Binary files /dev/null and b/sample_traces/st-g6-0.bin differ diff --git a/sample_traces/st-g6-1.bin b/sample_traces/st-g6-1.bin new file mode 100644 index 0000000..a51cce9 Binary files /dev/null and b/sample_traces/st-g6-1.bin differ diff --git a/sample_traces/st-g6-2.bin b/sample_traces/st-g6-2.bin new file mode 100644 index 0000000..5d76010 Binary files /dev/null and b/sample_traces/st-g6-2.bin differ diff --git a/sample_traces/st-g6-3.bin b/sample_traces/st-g6-3.bin new file mode 100644 index 0000000..471fc8d Binary files /dev/null and b/sample_traces/st-g6-3.bin differ diff --git a/sanitizer.py b/sanitizer.py new file mode 100644 index 0000000..79315cc --- /dev/null +++ b/sanitizer.py @@ -0,0 +1,53 @@ +############################################################################### +# Description +############################################################################### + +# Sanitize input. (There are a number of goofy issues with the sched_trace +# output.) + +############################################################################### +# Public functions +############################################################################### + +def sanitizer(stream): + + job_2s_released = [] # list of tasks which have released their job 2s + jobs_switched_to = [] + + for record in stream: + + # Ignore records which are not events (e.g. the num_cpus record) + if record.record_type != 'event': + yield record + continue + + # All records with job < 2 are garbage + if record.job < 2: + continue + + # Some records with job == 2 are garbage + if record.job==2: + + # There is a duplicate release of every job 2 + # This will throw away the second one + if record.type_name == 'release': + if record.pid in job_2s_released: + continue + else: + job_2s_released.append(record.pid) + + # Job 2 has a resume that is garbage + if record.type_name == 'resume': + continue + + # By default, the switch_away for a job (after it has completed) + # is maked as being for job+1, which has never been switched to. + # We can correct this if we note which jobs really + # have been switched to. + if record.type_name == 'switch_to': + jobs_switched_to.append((record.pid,record.job)) + if record.type_name == 'switch_away': + if (record.pid,record.job) not in jobs_switched_to: + record.job -= 1 + + yield record diff --git a/stats.py b/stats.py new file mode 100644 index 0000000..34a842f --- /dev/null +++ b/stats.py @@ -0,0 +1,39 @@ +############################################################################### +# Description +############################################################################### +# Compute and produce statistics + + +############################################################################### +# Public Functions +############################################################################### + +def stats(stream): + min_inversion = -1 + max_inversion = -1 + sum_inversions = 0 + num_inversions = 0 + for record in stream: + if record.type_name == 'inversion_end': + length = record.job.inversion_end - record.job.inversion_start + if length > 0: + num_inversions += 1 + if length > max_inversion: + max_inversion = length + if length < min_inversion or min_inversion == -1: + min_inversion = length + sum_inversions += length + yield record + if num_inversions > 0: + avg_inversion = int(sum_inversions / num_inversions) + else: + avg_inversion = 0 + class Obj(object): pass + rec = Obj() + rec.record_type = "meta" + rec.type_name = "stats" + rec.num_inversions = num_inversions + rec.min_inversion = min_inversion + rec.max_inversion = max_inversion + rec.avg_inversion = avg_inversion + yield rec diff --git a/stdout_printer.py b/stdout_printer.py new file mode 100644 index 0000000..f8d9a84 --- /dev/null +++ b/stdout_printer.py @@ -0,0 +1,69 @@ +############################################################################### +# Description +############################################################################### + +# Prints records to standard out + +############################################################################### +# Public functions +############################################################################### + +def stdout_printer(stream): + for record in stream: + if record.record_type == "event": + _print_event(record) + elif record.record_type == "meta" and record.type_name == "stats": + _print_stats(record) + elif record.record_type == "error" and record.type_name == 'inversion_start': + _print_inversion_start(record) + elif record.record_type == "error" and record.type_name == 'inversion_end': + _print_inversion_end(record) + else: + continue + print "" + +############################################################################### +# Private functions +############################################################################### + +def _print_event(record): + print "Job: %d.%d" % (record.pid,record.job) + print "Type: %s" % (record.type_name) + print "Time: %d" % (record.when) + +def _print_inversion_start(record): + print "Type: %s" % ("Inversion start") + print "Time: %d" % (record.job.inversion_start) + print "Job: %d.%d" % (record.job.pid,record.job.job) + print "Deadline: %d" % (record.job.deadline) + print "Eligible: ", + for job in record.eligible: + print str(job) + " ", + print + print "On CPU: ", + for job in record.on_cpu: + print str(job) + " ", + print #newline + +def _print_inversion_end(record): + print "Type: %s" % ("Inversion end") + print "Time: %d" % (record.job.inversion_end) + print "Duration: %d" % ( + record.job.inversion_end - record.job.inversion_start) + print "Job: %d.%d" % (record.job.pid,record.job.job) + print "Deadline: %d" % (record.job.deadline) + print "Eligible: ", + for job in record.eligible: + print str(job) + " ", + print + print "On CPU: ", + for job in record.on_cpu: + print str(job) + " ", + print #newline + +def _print_stats(record): + print "Inversion statistics" + print "Num inversions: %d" % (record.num_inversions) + print "Min inversion: %d" % (record.min_inversion) + print "Max inversion: %d" % (record.max_inversion) + print "Avg inversion: %d" % (record.avg_inversion) diff --git a/trace_reader.py b/trace_reader.py new file mode 100644 index 0000000..a4ff964 --- /dev/null +++ b/trace_reader.py @@ -0,0 +1,245 @@ +############################################################################### +# Description +############################################################################### + +# trace_reader(files) returns an iterator which produces records +# in order from the files given. (the param is a list of files.) +# +# Each record is just a Python object. It is guaranteed to have the following +# attributes: +# - 'pid': pid of the task +# - 'job': job number for that task +# - 'cpu', given by LITMUS +# - 'when', given by LITMUS as a timestamp. LITMUS does not provide a +# timestamp for all records. In this case, when is set to 0. +# - 'type', a numerical value given by LITMUS +# - 'type_name', a human-readable name defined in this module +# - 'record_type', set to 'event' by this module (to distinguish from, e.g., +# error records produced elsewhere). +# - Possible additional attributes, depending on the type of record. +# +# To find out exactly what attributes are set for each record type, look at +# the trace-parsing information at the bottom of this file. + +############################################################################### +# Imports +############################################################################### + +import struct + + +############################################################################### +# Public functions +############################################################################### + +# Generator function returning an iterable over records in a trace file. +def trace_reader(files): + + # Yield a record indicating the number of CPUs, used by the G-EDF test + class Obj: pass + record = Obj() + record.record_type = "meta" + record.type_name = "num_cpus" + record.num_cpus = len(files) + yield record + + # Create iterators for each file and a buffer to store records in + file_iters = [] # file iterators + file_iter_buff = [] # file iterator buffers + for file in files: + file_iter = _get_file_iter(file) + file_iters.append(file_iter) + file_iter_buff.append([file_iter.next()]) + + # We keep 100 records in each buffer and then keep the buffer sorted + # This is because records may have been recorded slightly out of order + # This cannot guarantee records are produced in order, but it makes it + # overwhelmingly probably. + for x in range(0,len(file_iter_buff)): + for y in range(0,100): + file_iter_buff[x].append(file_iters[x].next()) + for x in range(0,len(file_iter_buff)): + file_iter_buff[x] = sorted(file_iter_buff[x],key=lambda rec: rec.when) + + # Remember the time of the last record. This way, we can make sure records + # truly are produced in monotonically increasing order by time and terminate + # fatally if they are not. + last_time = None + + # Keep pulling records as long as we have a buffer + while len(file_iter_buff) > 0: + + # Select the earliest record from those at the heads of the buffers + earliest = -1 + buff_to_refill = -1 + for x in range(0,len(file_iter_buff)): + if earliest==-1 or file_iter_buff[x][0].when < earliest.when: + earliest = file_iter_buff[x][0] + buff_to_refill = x + + # Take it out of the buffer + del file_iter_buff[buff_to_refill][0] + + # Try to append a new record to the buffer (if there is another) and + # then keep the buffer sorted + try: + file_iter_buff[buff_to_refill].append(file_iters[buff_to_refill].next()) + file_iter_buff[buff_to_refill] = sorted(file_iter_buff[buff_to_refill], + key=lambda rec: rec.when) + + # If there aren't any more records, fine. Unless the buffer is also empty. + # If that is the case, delete the buffer. + except StopIteration: + if len(file_iter_buff[buff_to_refill]) < 1: + del file_iter_buff[buff_to_refill] + del file_iters[buff_to_refill] + + # Check for monotonically increasing time + if last_time is not None and earliest.when < last_time: + exit("FATAL ERROR: trace_reader.py: out-of-order record produced") + else: + last_time = earliest.when + + # Yield the record + yield earliest + +############################################################################### +# Private functions +############################################################################### + +# Returns an iterator to pull records from a file +def _get_file_iter(file): + f = open(file,'rb') + while True: + data = f.read(RECORD_HEAD_SIZE) + try: + type_num = struct.unpack_from('b',data)[0] + except struct.error: + break #We read to the end of the file + type = _get_type(type_num) + try: + values = struct.unpack_from(StHeader.format + + type.format,data) + record_dict = dict(zip(type.keys,values)) + except struct.error: + f.close() + print "Invalid record detected, stopping." + exit() + + # Convert the record_dict into an object + record = _dict2obj(record_dict) + + # Give it a type name (easier to work with than type number) + record.type_name = _get_type_name(type_num) + + # All records should have a 'record type' field. + # e.g. these are 'event's as opposed to 'error's + record.record_type = "event" + + # If there is no timestamp, set the time to 0 + if 'when' not in record.__dict__.keys(): + record.when = 0 + + yield record + +# Convert a dict into an object +def _dict2obj(d): + class Obj(object): pass + o = Obj() + for key in d.keys(): + o.__dict__[key] = d[key] + return o + +############################################################################### +# Trace record data types and accessor functions +############################################################################### + +# Each class below represents a type of event record. The format attribute +# specifies how to decode the binary record and the keys attribute +# specifies how to name the pieces of information decoded. Note that all +# event records have a common initial 24 bytes, represented by the StHeader +# class. + +RECORD_HEAD_SIZE = 24 + +class StHeader: + format = ' end_tick or start_item > end_item: + raise ValueError('start must be less than end') + + line_width = (end_tick - start_tick) * maj_sep + line_height = (end_item - start_item) * item_size + + origin = (x, y) + + # draw horizontal lines first + x = origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + start_tick * maj_sep + y = origin[1] - height + start_item * item_size + for i in range(start_item, end_item + 1): + self.draw_line((x, y), (x + line_width, y), GraphFormat.GRID_COLOR, GraphFormat.GRID_THICKNESS) + y += item_size + + x = origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + start_tick * maj_sep + y = origin[1] - height + start_item * item_size + + if show_min: + for i in range(0, (end_tick - start_tick) * min_per_maj + 1): + self.draw_line((x, y), (x, y + line_height), GraphFormat.GRID_COLOR, GraphFormat.GRID_THICKNESS) + x += maj_sep * 1.0 / min_per_maj + else: + for i in range(start_tick, end_tick + 1): + self.draw_line((x, y), (x, y + line_height), GraphFormat.GRID_COLOR, GraphFormat.GRID_THICKNESS) + x += maj_sep + + def draw_bar(self, x, y, width, height, n, selected): + """Draws a bar with a certain set of dimensions, using pattern ``n'' from the + bar pattern list.""" + + color, thickness = {False : (GraphFormat.BORDER_COLOR, GraphFormat.BORDER_THICKNESS), + True : (GraphFormat.HIGHLIGHT_COLOR, GraphFormat.BORDER_THICKNESS * 2.0)}[selected] + + # use a pattern to be pretty + self.get_bar_pattern(n).render_on_canvas(self, x, y, width, height, True) + self.draw_rect(x, y, width, height, color, thickness) + + def add_sel_bar(self, x, y, width, height, event): + self.add_sel_region(SelectableRegion(x, y, width, height, event)) + + def draw_mini_bar(self, x, y, width, height, n, selected): + """Like the above, except it draws a miniature version. This is usually used for + secondary purposes (i.e. to show jobs that _should_ have been running at a certain time). + + Of course we don't enforce the fact that this is mini, since the user can pass in width + and height (but the mini bars do look slightly different: namely the borders are a different + color)""" + + color, thickness = {False : (GraphFormat.LITE_BORDER_COLOR, GraphFormat.BORDER_THICKNESS), + True : (GraphFormat.HIGHLIGHT_COLOR, GraphFormat.BORDER_THICKNESS * 1.5)}[selected] + + self.get_bar_pattern(n).render_on_canvas(self, x, y, width, height, True) + self.draw_rect(x, y, width, height, color, thickness) + + def add_sel_mini_bar(self, x, y, width, height, event): + self.add_sel_region(SelectableRegion(x, y, width, height, event)) + + def draw_completion_marker(self, x, y, height, selected): + """Draws the symbol that represents a job completion, using a certain height.""" + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + self.draw_line((x - height * GraphFormat.TEE_FACTOR / 2.0, y), + (x + height * GraphFormat.TEE_FACTOR / 2.0, y), + color, GraphFormat.BORDER_THICKNESS) + self.draw_line((x, y), (x, y + height), color, GraphFormat.BORDER_THICKNESS) + + def add_sel_completion_marker(self, x, y, height, event): + self.add_sel_region(SelectableRegion(x - height * GraphFormat.TEE_FACTOR / 2.0, y, + height * GraphFormat.TEE_FACTOR, height, event)) + + def draw_release_arrow_big(self, x, y, height, selected): + """Draws a release arrow of a certain height: (x, y) should give the top + (northernmost point) of the arrow. The height includes the arrowhead.""" + big_arrowhead_height = GraphFormat.BIG_ARROWHEAD_FACTOR * height + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + colors = [(1.0, 1.0, 1.0), color] + draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline] + for i in range(0, 2): + color = colors[i] + draw_func = draw_funcs[i] + + draw_func(self, [(x, y), (x - big_arrowhead_height / Canvas.SQRT3, y + big_arrowhead_height), \ + (x + big_arrowhead_height / Canvas.SQRT3, y + big_arrowhead_height), (x, y)], \ + color, GraphFormat.BORDER_THICKNESS) + + self.draw_line((x, y + big_arrowhead_height), (x, y + height), color, GraphFormat.BORDER_THICKNESS) + + def add_sel_release_arrow_big(self, x, y, height, event): + self.add_sel_arrow_big(x, y, height, event) + + def draw_deadline_arrow_big(self, x, y, height, selected): + """Draws a release arrow: x, y should give the top (northernmost + point) of the arrow. The height includes the arrowhead.""" + big_arrowhead_height = GraphFormat.BIG_ARROWHEAD_FACTOR * height + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + colors = [(1.0, 1.0, 1.0), color] + draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline] + for i in range(0, 2): + color = colors[i] + draw_func = draw_funcs[i] + + draw_func(self, [(x, y + height), (x - big_arrowhead_height / Canvas.SQRT3, \ + y + height - big_arrowhead_height), \ + (x + big_arrowhead_height / Canvas.SQRT3, \ + y + height - big_arrowhead_height), \ + (x, y + height)], color, GraphFormat.BORDER_THICKNESS) + + self.draw_line((x, y), (x, y + height - big_arrowhead_height), + color, GraphFormat.BORDER_THICKNESS) + + def add_sel_deadline_arrow_big(self, x, y, height, event): + self.add_sel_arrow_big(x, y, height, event) + + def add_sel_arrow_big(self, x, y, height, event): + big_arrowhead_height = GraphFormat.BIG_ARROWHEAD_FACTOR * height + + self.add_sel_region(SelectableRegion(x - big_arrowhead_height / Canvas.SQRT3, + y, 2.0 * big_arrowhead_height / Canvas.SQRT3, height, event)) + + def draw_release_arrow_small(self, x, y, height, selected): + """Draws a small release arrow (most likely coming off the x-axis, although + this method doesn't enforce this): x, y should give the top of the arrow""" + small_arrowhead_height = GraphFormat.SMALL_ARROWHEAD_FACTOR * height + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + + self.draw_line((x, y), (x - small_arrowhead_height, y + small_arrowhead_height), \ + color, GraphFormat.BORDER_THICKNESS) + self.draw_line((x, y), (x + small_arrowhead_height, y + small_arrowhead_height), \ + color, GraphFormat.BORDER_THICKNESS) + self.draw_line((x, y), (x, y + height), color, GraphFormat.BORDER_THICKNESS) + + def add_sel_release_arrow_small(self, x, y, height, event): + self.add_sel_arrow_small(x, y, height, event) + + def draw_deadline_arrow_small(self, x, y, height, selected): + """Draws a small deadline arrow (most likely coming off the x-axis, although + this method doesn't enforce this): x, y should give the top of the arrow""" + small_arrowhead_height = GraphFormat.SMALL_ARROWHEAD_FACTOR * height + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + + self.draw_line((x, y), (x, y + height), color, GraphFormat.BORDER_THICKNESS) + self.draw_line((x - small_arrowhead_height, y + height - small_arrowhead_height), \ + (x, y + height), color, GraphFormat.BORDER_THICKNESS) + self.draw_line((x + small_arrowhead_height, y + height - small_arrowhead_height), \ + (x, y + height), color, GraphFormat.BORDER_THICKNESS) + + def add_sel_deadline_arrow_small(self, x, y, height, event): + self.add_sel_arrow_small(x, y, height, event) + + def add_sel_arrow_small(self, x, y, height, event): + small_arrowhead_height = GraphFormat.SMALL_ARROWHEAD_FACTOR * height + + self.add_sel_region(SelectableRegion(x - small_arrowhead_height, y, + small_arrowhead_height * 2.0, height, event)) + + def draw_suspend_triangle(self, x, y, height, selected): + """Draws the triangle that marks a suspension. (x, y) gives the topmost (northernmost) point + of the symbol.""" + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + colors = [(0.0, 0.0, 0.0), color] + + draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline] + for i in range(0, 2): + color = colors[i] + draw_func = draw_funcs[i] + draw_func(self, [(x, y), (x + height / 2.0, y + height / 2.0), (x, y + height), (x, y)], \ + color, GraphFormat.BORDER_THICKNESS) + + def add_sel_suspend_triangle(self, x, y, height, event): + self.add_sel_region(SelectableRegion(x, y, height / 2.0, height, event)) + + def draw_resume_triangle(self, x, y, height, selected): + """Draws the triangle that marks a resumption. (x, y) gives the topmost (northernmost) point + of the symbol.""" + + color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected] + colors = [(1.0, 1.0, 1.0), color] + + draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline] + for i in range(0, 2): + color = colors[i] + draw_func = draw_funcs[i] + draw_func(self, [(x, y), (x - height / 2.0, y + height / 2.0), (x, y + height), (x, y)], \ + color, GraphFormat.BORDER_THICKNESS) + + def add_sel_resume_triangle(self, x, y, height, event): + self.add_sel_region(SelectableRegion(x - height / 2.0, y, height / 2.0, height, event)) + + def clear_selectable_regions(self): + self.selectable_regions = {} + + def add_sel_region(self, region): + self.selectable_regions[region.get_event()] = region + + def get_selected_regions(self, real_x, real_y): + x = real_x + self.surface.virt_x + y = real_y + self.surface.virt_y + + selected = {} + for event in self.selectable_regions: + region = self.selectable_regions[event] + if region.contains(x, y): + selected[event] = region + + return selected + + def whiteout(self): + """Overwrites the surface completely white, but technically doesn't delete anything""" + self.fill_rect(self.surface.virt_x, self.surface.virt_y, self.surface.width, + self.surface.height, (1.0, 1.0, 1.0)) + + def get_item_color(self, n): + """Gets the nth color in the item color list, which are the colors used to draw the items + on the y-axis. Note that there are conceptually infinitely + many patterns because the patterns repeat -- that is, we just mod out by the size of the pattern + list when indexing.""" + return self.item_clist[n % len(self.item_clist)] + + def get_bar_pattern(self, n): + """Gets the nth pattern in the bar pattern list, which is a list of surfaces that are used to + fill in the bars. Note that there are conceptually infinitely + many patterns because the patterns repeat -- that is, we just mod out by the size of the pattern + list when indexing.""" + return self.bar_plist[n % len(self.bar_plist)] + +class CairoCanvas(Canvas): + """This is a basic class that stores and draws on a Cairo surface, + using various primitives related to drawing a real-time graph (up-arrows, + down-arrows, bars, ...). + + This is the lowest-level non-abstract representation + (aside perhaps from the Cairo surface itself) of a real-time graph. + It allows the user to draw primitives at certain locations, but for + the most part does not know anything about real-time scheduling, + just how to draw the basic parts that make up a schedule graph. + For that, see Graph or its descendants.""" + + #def __init__(self, fname, width, height, item_clist, bar_plist, surface): + # """Creates a new Canvas of dimensions (width, height). The + # parameters ``item_plist'' and ``bar_plist'' each specify a list + # of patterns to choose from when drawing the items on the y-axis + # or filling in bars, respectively.""" + + # super(CairoCanvas, self).__init__(fname, width, height, item_clist, bar_plist, surface) + + #def clear(self): + # self.surface = self.SurfaceType(self.width, self.height, self.fname) + # self.whiteout() + + def get_surface(self): + """Gets the Surface that we are drawing on in its current state.""" + return self.surface + + def _rect_common(self, x, y, width, height, color, thickness): + x, y, width, height = self.scaled(x, y, width, height) + x, y = self.surface.get_real_coor(x, y) + self.surface.ctx.rectangle(snap(x), snap(y), width, height) + self.surface.ctx.set_line_width(thickness * self.scale) + self.surface.ctx.set_source_rgb(color[0], color[1], color[2]) + + def draw_rect(self, x, y, width, height, color, thickness): + self._rect_common(x, y, width, height, color, thickness) + self.surface.ctx.stroke() + + def fill_rect(self, x, y, width, height, color): + self._rect_common(x, y, width, height, color, 1) + self.surface.ctx.fill() + + def fill_rect_fade(self, x, y, width, height, lcolor, rcolor): + """Draws a rectangle somewhere, filled in with the fade.""" + x, y, width, height = self.scaled(x, y, width, height) + x, y = self.surface.get_real_coor(x, y) + + linear = cairo.LinearGradient(snap(x), snap(y), \ + snap(x + width), snap(y + height)) + linear.add_color_stop_rgb(0.0, lcolor[0], lcolor[1], lcolor[2]) + linear.add_color_stop_rgb(1.0, rcolor[0], rcolor[1], rcolor[2]) + self.surface.ctx.set_source(linear) + self.surface.ctx.rectangle(snap(x), snap(y), width, height) + self.surface.ctx.fill() + + def draw_line(self, p0, p1, color, thickness): + """Draws a line from p0 to p1 with a certain color and thickness.""" + p0 = self.scaled(p0[0], p0[1]) + p0 = self.surface.get_real_coor(p0[0], p0[1]) + p1 = self.scaled(p1[0], p1[1]) + p1 = self.surface.get_real_coor(p1[0], p1[1]) + self.surface.ctx.move_to(p0[0], p0[1]) + self.surface.ctx.line_to(p1[0], p1[1]) + self.surface.ctx.set_source_rgb(color[0], color[1], color[2]) + self.surface.ctx.set_line_width(thickness * self.scale) + self.surface.ctx.stroke() + + def _polyline_common(self, coor_list, color, thickness): + real_coor_list = [self.surface.get_real_coor(coor[0], coor[1]) for coor in coor_list] + self.surface.ctx.move_to(real_coor_list[0][0], real_coor_list[0][1]) + for coor in real_coor_list[1:]: + self.surface.ctx.line_to(coor[0], coor[1]) + + self.surface.ctx.set_line_width(thickness) + self.surface.ctx.set_source_rgb(color[0], color[1], color[2]) + + def draw_polyline(self, coor_list, color, thickness): + self._polyline_common(coor_list, color, thickness) + self.surface.ctx.stroke() + + def fill_polyline(self, coor_list, color, thickness): + self._polyline_common(coor_list, color, thickness) + self.surface.ctx.fill() + + def _draw_label_common(self, text, x, y, fopts, x_bearing_factor, \ + f_descent_factor, width_factor, f_height_factor): + """Helper function for drawing a label with some alignment. Instead of taking in an alignment, + it takes in the scale factor for the font extent parameters, which give the raw data of how much to adjust + the x and y parameters. Only should be used internally.""" + x, y = self.scaled(x, y) + x, y = self.surface.get_real_coor(x, y) + + self.surface.ctx.set_source_rgb(0.0, 0.0, 0.0) + + self.surface.ctx.select_font_face(fopts.name, cairo.FONT_SLANT_NORMAL, cairo.FONT_WEIGHT_BOLD) + self.surface.ctx.set_font_size(fopts.size) + + fe = self.surface.ctx.font_extents() + f_ascent, f_descent, f_height = fe[:3] + + te = self.surface.ctx.text_extents(text) + x_bearing, y_bearing, width, height = te[:4] + + actual_x = x - x_bearing * x_bearing_factor - width * width_factor + actual_y = y - f_descent * f_descent_factor + f_height * f_height_factor + + self.surface.ctx.set_source_rgb(fopts.color[0], fopts.color[1], fopts.color[2]) + + self.surface.ctx.move_to(snap(actual_x), snap(actual_y)) + + self.surface.ctx.show_text(text) + + def draw_label(self, text, x, y, fopts=GraphFormat.DEF_FOPTS_LABEL, halign=AlignMode.LEFT, valign=AlignMode.BOTTOM): + """Draws a label with the given parameters, with the given horizontal and vertical justification. One can override + the color from ``fopts'' by passing something in to ``pattern'', which overrides the color with an arbitrary + pattern.""" + x_bearing_factor, f_descent_factor, width_factor, f_height_factor = 0.0, 0.0, 0.0, 0.0 + halign_factors = {AlignMode.LEFT : (0.0, 0.0), AlignMode.CENTER : (1.0, 0.5), AlignMode.RIGHT : (1.0, 1.0)} + if halign not in halign_factors: + raise ValueError('Invalid alignment value') + x_bearing_factor, width_factor = halign_factors[halign] + + valign_factors = {AlignMode.BOTTOM : (0.0, 0.0), AlignMode.CENTER : (1.0, 0.5), AlignMode.TOP : (1.0, 1.0)} + if valign not in valign_factors: + raise ValueError('Invalid alignment value') + f_descent_factor, f_height_factor = valign_factors[valign] + + self._draw_label_common(text, x, y, fopts, x_bearing_factor, \ + f_descent_factor, width_factor, f_height_factor) + + def draw_label_with_sscripts(self, text, supscript, subscript, x, y, \ + textfopts=GraphFormat.DEF_FOPTS_LABEL, sscriptfopts=GraphFormat.DEF_FOPTS_LABEL_SSCRIPT, \ + halign=AlignMode.LEFT, valign=AlignMode.BOTTOM): + """Draws a label, but also optionally allows a superscript and subscript to be rendered.""" + self.draw_label(text, x, y, textfopts, halign, valign) + + self.surface.ctx.set_source_rgb(0.0, 0.0, 0.0) + self.surface.ctx.select_font_face(textfopts.name, cairo.FONT_SLANT_NORMAL, cairo.FONT_WEIGHT_BOLD) + self.surface.ctx.set_font_size(textfopts.size) + te = self.surface.ctx.text_extents(text) + fe = self.surface.ctx.font_extents() + if supscript is not None: + f_height = fe[2] + x_advance = te[4] + xtmp = x + x_advance + ytmp = y + ytmp = y - f_height / 4.0 + self.draw_label(supscript, xtmp, ytmp, sscriptfopts, halign, valign) + if subscript is not None: + f_height = fe[2] + x_advance = te[4] + xtmp = x + x_advance + ytmp = y + ytmp = y + f_height / 4.0 + self.draw_label(subscript, xtmp, ytmp, sscriptfopts, halign, valign) + +# represents a selectable region of the graph +class SelectableRegion(object): + def __init__(self, x, y, width, height, event): + self.x = x + self.y = y + self.width = width + self.height = height + self.event = event + + def get_dimensions(self): + return (self.x, self.y, self.width, self.height) + + def get_event(self): + return self.event + + def contains(self, x, y): + return self.x <= x <= self.x + self.width and self.y <= y <= self.y + self.height + +class Graph(object): + DEF_BAR_PLIST = [Pattern([(0.0, 0.9, 0.9)]), Pattern([(0.9, 0.3, 0.0)]), Pattern([(0.9, 0.7, 0.0)]), + Pattern([(0.0, 0.0, 0.8)]), Pattern([(0.0, 0.2, 0.9)]), Pattern([(0.0, 0.6, 0.6)]), + Pattern([(0.75, 0.75, 0.75)])] + DEF_ITEM_CLIST = [(0.3, 0.0, 0.0), (0.0, 0.3, 0.0), (0.0, 0.0, 0.3), (0.3, 0.3, 0.0), (0.0, 0.3, 0.3), + (0.3, 0.0, 0.3)] + + def __init__(self, CanvasType, surface, start_time, end_time, y_item_list, attrs=GraphFormat(), + item_clist=DEF_ITEM_CLIST, bar_plist=DEF_BAR_PLIST): + if start_time > end_time: + raise ValueError("Litmus is not a time machine") + + self.attrs = attrs + self.start_time = start_time + self.end_time = end_time + self.y_item_list = y_item_list + self.num_maj = int(math.ceil((self.end_time - self.start_time) * 1.0 / self.attrs.time_per_maj)) + 1 + + width = self.num_maj * self.attrs.maj_sep + GraphFormat.X_AXIS_MEASURE_OFS + GraphFormat.WIDTH_PAD + height = (len(self.y_item_list) + 1) * self.attrs.y_item_size + GraphFormat.HEIGHT_PAD + + # We need to stretch the width in order to fit the y-axis labels. To do this we need + # the extents information, but we haven't set up a surface yet, so we just use a + # temporary one. + extra_width = 0.0 + dummy_surface = surface.__class__() + dummy_surface.renew(10, 10) + + dummy_surface.ctx.select_font_face(self.attrs.item_fopts.name, cairo.FONT_SLANT_NORMAL, cairo.FONT_WEIGHT_BOLD) + dummy_surface.ctx.set_font_size(self.attrs.item_fopts.size) + for item in self.y_item_list: + dummy_surface.ctx.set_source_rgb(0.0, 0.0, 0.0) + te = dummy_surface.ctx.text_extents(item) + cur_width = te[2] + if cur_width > extra_width: + extra_width = cur_width + + width += extra_width + self.origin = (extra_width + GraphFormat.WIDTH_PAD / 2.0, height - GraphFormat.HEIGHT_PAD / 2.0) + + self.width = width + self.height = height + + #if surface.ctx is None: + # surface.renew(width, height) + + self.canvas = CanvasType(width, height, item_clist, bar_plist, surface) + + def get_selected_regions(self, real_x, real_y): + return self.canvas.get_selected_regions(real_x, real_y) + + def get_width(self): + return self.width + + def get_height(self): + return self.height + + def get_attrs(self): + return self.attrs + + def update_view(self, x, y, width, height, ctx): + """Proxy into the surface's pan.""" + self.canvas.surface.pan(x, y, width, height) + self.canvas.surface.change_ctx(ctx) + + def _get_time_xpos(self, time): + """get x so that x is at instant ``time'' on the graph""" + return self.origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + 1.0 * (time - self.start_time) / self.attrs.time_per_maj * self.attrs.maj_sep + + def _get_item_ypos(self, item_no): + """get y so that y is where the top of a bar would be in item #n's area""" + return self.origin[1] - self._get_y_axis_height() + self.attrs.y_item_size * (item_no + 0.5 - GraphFormat.BAR_SIZE_FACTOR / 2.0) + + def _get_bar_width(self, start_time, end_time): + return 1.0 * (end_time - start_time) / self.attrs.time_per_maj * self.attrs.maj_sep + + def _get_bar_height(self): + return self.attrs.y_item_size * GraphFormat.BAR_SIZE_FACTOR + + def _get_mini_bar_height(self): + return self.attrs.y_item_size * GraphFormat.MINI_BAR_SIZE_FACTOR + + def _get_mini_bar_ofs(self): + return self.attrs.y_item_size * (GraphFormat.MINI_BAR_SIZE_FACTOR + GraphFormat.BAR_MINI_BAR_GAP_FACTOR) + + def _get_y_axis_height(self): + return (len(self.y_item_list) + 1) * self.attrs.y_item_size + + def _get_bottom_tick(self, time): + return int(math.floor((time - self.start_time) / self.attrs.time_per_maj)) + + def _get_top_tick(self, time): + return int(math.ceil((time - self.start_time) / self.attrs.time_per_maj)) + + def get_surface(self): + """Gets the underlying surface.""" + return self.canvas.get_surface() + + def xcoor_to_time(self, x): + #x = self.origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + (time - self.start) / self.attrs.time_per_maj * self.attrs.maj_sep + return (x - self.origin[0] - GraphFormat.X_AXIS_MEASURE_OFS) / self.attrs.maj_sep \ + * self.attrs.time_per_maj + self.start_time + + def ycoor_to_item_no(self, y): + return int((y - self.origin[1] + self._get_y_axis_height()) // self.attrs.y_item_size) + + def get_offset_params(self): + start_time = self.xcoor_to_time(self.canvas.surface.virt_x) + end_time = self.xcoor_to_time(self.canvas.surface.virt_x + self.canvas.surface.width) + + start_item = self.ycoor_to_item_no(self.canvas.surface.virt_y) + end_item = 1 + self.ycoor_to_item_no(self.canvas.surface.virt_y + self.canvas.surface.height) + + return (start_time, end_time, start_item, end_item) + + def draw_skeleton(self, start_time, end_time, start_item, end_item): + self.draw_grid_at_time(start_time, end_time, start_item, end_item) + self.draw_x_axis_with_labels_at_time(start_time, end_time) + self.draw_y_axis_with_labels() + + def render_surface(self, sched, list_type): + raise NotImplementedError + + def render_all(self, schedule): + raise NotImplementedError + + def render_events(self, event_list): + for layer in Canvas.LAYERS: + prev_events = {} + for event in event_list: + event.render(self, layer, prev_events) + + def draw_axes(self, x_axis_label, y_axis_label): + """Draws and labels the axes according to the parameters that we were initialized + with.""" + self.draw_grid_at_time(self.start_time, self.end_time, 0, len(self.attrs.y_item_list) - 1) + + self.canvas.draw_x_axis(self.origin[0], self.origin[1], self.num_maj, self.attrs.maj_sep, self.attrs.min_per_maj) + self.canvas.draw_y_axis(self.origin[0], self.origin[1], self._get_y_axis_height()) + self.canvas.draw_x_axis_labels(self.origin[0], self.origin[1], 0, self.num_maj - 1,\ + self.attrs.maj_sep, self.attrs.min_per_maj, self.start_time, \ + self.attrs.time_per_maj, self.attrs.show_min, self.attrs.majfopts, self.attrs.minfopts) + self.canvas.draw_y_axis_labels(self.origin[0], self.origin[1], self._get_y_axis_height(), self.y_item_list, \ + self.attrs.y_item_size, self.attrs.item_fopts) + + def draw_grid_at_time(self, start_time, end_time, start_item, end_item): + """Draws the grid, but only in a certain time and item range.""" + start_tick = max(0, self._get_bottom_tick(start_time)) + end_tick = min(self.num_maj - 1, self._get_top_tick(end_time)) + + start_item = max(0, start_item) + end_item = min(len(self.y_item_list), end_item) + + self.canvas.draw_grid(self.origin[0], self.origin[1], self._get_y_axis_height(), + start_tick, end_tick, start_item, end_item, self.attrs.maj_sep, self.attrs.y_item_size, \ + self.attrs.min_per_maj, True) + + def draw_x_axis_with_labels_at_time(self, start_time, end_time): + start_tick = max(0, self._get_bottom_tick(start_time)) + end_tick = min(self.num_maj - 1, self._get_top_tick(end_time)) + + self.canvas.draw_x_axis(self.origin[0], self.origin[1], start_tick, end_tick, \ + self.attrs.maj_sep, self.attrs.min_per_maj) + self.canvas.draw_x_axis_labels(self.origin[0], self.origin[1], start_tick, \ + end_tick, self.attrs.maj_sep, self.attrs.min_per_maj, + self.start_time + start_tick * self.attrs.time_per_maj, + self.attrs.time_per_maj, False) + + def draw_y_axis_with_labels(self): + self.canvas.draw_y_axis(self.origin[0], self.origin[1], self._get_y_axis_height()) + self.canvas.draw_y_axis_labels(self.origin[0], self.origin[1], self._get_y_axis_height(), \ + self.y_item_list, self.attrs.y_item_size) + + def draw_suspend_triangle_at_time(self, time, task_no, cpu_no, selected=False): + """Draws a suspension symbol for a certain task at an instant in time.""" + raise NotImplementedError + + def add_sel_suspend_triangle_at_time(self, time, task_no, cpu_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + + def draw_resume_triangle_at_time(self, time, task_no, cpu_no, selected=False): + """Draws a resumption symbol for a certain task at an instant in time.""" + raise NotImplementedError + + def add_sel_resume_triangle_at_time(self, time, task_no, cpu_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + + def draw_completion_marker_at_time(self, time, task_no, cpu_no, selected=False): + """Draws a completion marker for a certain task at an instant in time.""" + raise NotImplementedError + + def add_sel_completion_marker_at_time(self, time, task_no, cpu_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + + def draw_release_arrow_at_time(self, time, task_no, job_no, selected=False): + """Draws a release arrow at a certain time for some task and job""" + raise NotImplementedError + + def add_sel_release_arrow_at_time(self, time, task_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + + def draw_deadline_arrow_at_time(self, time, task_no, job_no, selected=False): + """Draws a deadline arrow at a certain time for some task and job""" + raise NotImplementedError + + def add_sel_deadline_arrow_at_time(self, time, task_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + + def draw_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None): + """Draws a bar over a certain time period for some task, optionally labelling it.""" + raise NotImplementedError + + def add_sel_bar_at_time(self, start_time, end_time, task_no, cpu_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + + def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None): + """Draws a mini bar over a certain time period for some task, optionally labelling it.""" + raise NotImplementedError + + def add_sel_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, event): + """Same as above, except instead of drawing adds a selectable region at + a certain time.""" + raise NotImplementedError + +class TaskGraph(Graph): + def render_surface(self, sched): + self.canvas.whiteout() + self.canvas.clear_selectable_regions() + + start_time, end_time, start_item, end_item = self.get_offset_params() + + self.draw_skeleton(start_time, end_time, start_item, end_item) + + for layer in Canvas.LAYERS: + prev_events = {} + for event in sched.get_time_slot_array().iter_over_period( + start_time, end_time, start_item, end_item, + schedule.TimeSlotArray.TASK_LIST, schedule.EVENT_LIST): + event.render(self, layer, prev_events) + + def draw_suspend_triangle_at_time(self, time, task_no, cpu_no, selected=False): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0 + self.canvas.draw_suspend_triangle(x, y, height, selected) + + def add_sel_suspend_triangle_at_time(self, time, task_no, cpu_no, event): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.add_sel_suspend_triangle(x, y, height, event) + + def draw_resume_triangle_at_time(self, time, task_no, cpu_no, selected=False): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.draw_resume_triangle(x, y, height, selected) + + def add_sel_resume_triangle_at_time(self, time, task_no, cpu_no, event): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.add_sel_resume_triangle(x, y, height, event) + + def draw_completion_marker_at_time(self, time, task_no, cpu_no, selected=False): + height = self._get_bar_height() * GraphFormat.COMPLETION_MARKER_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() - height + + self.canvas.draw_completion_marker(x, y, height, selected) + + def add_sel_completion_marker_at_time(self, time, task_no, cpu_no, event): + height = self._get_bar_height() * GraphFormat.COMPLETION_MARKER_FACTOR + + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() - height + + self.canvas.add_sel_completion_marker(x, y, height, event) + + def draw_release_arrow_at_time(self, time, task_no, job_no=None, selected=False): + height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() - height + + self.canvas.draw_release_arrow_big(x, y, height, selected) + + def add_sel_release_arrow_at_time(self, time, task_no, event): + height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + self._get_bar_height() - height + + self.canvas.add_sel_release_arrow_big(x, y, height, event) + + def draw_deadline_arrow_at_time(self, time, task_no, job_no=None, selected=False): + height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + + self.canvas.draw_deadline_arrow_big(x, y, height, selected) + + def add_sel_deadline_arrow_at_time(self, time, task_no, event): + height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self._get_item_ypos(task_no) + + self.canvas.add_sel_deadline_arrow_big(x, y, height, event) + + def draw_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False): + if start_time > end_time: + raise ValueError("Litmus is not a time machine") + + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(task_no) + width = self._get_bar_width(start_time, end_time) + height = self._get_bar_height() + + self.canvas.draw_bar(x, y, width, height, cpu_no, selected) + + # if a job number is specified, we want to draw a superscript and subscript for the task and job number, respectively + if job_no is not None: + x += GraphFormat.BAR_LABEL_OFS + y += self.attrs.y_item_size * GraphFormat.BAR_SIZE_FACTOR / 2.0 + self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \ + GraphFormat.DEF_FOPTS_BAR, GraphFormat.DEF_FOPTS_BAR_SSCRIPT, AlignMode.LEFT, AlignMode.CENTER) + + def add_sel_bar_at_time(self, start_time, end_time, task_no, cpu_no, event): + if start_time > end_time: + raise ValueError("Litmus is not a time machine") + + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(task_no) + width = self._get_bar_width(start_time, end_time) + height = self._get_bar_height() + + self.canvas.add_sel_bar(x, y, width, height, event) + + def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False): + if start_time > end_time: + raise ValueError("Litmus is not a time machine") + + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(task_no) - self._get_mini_bar_ofs() + width = self._get_bar_width(start_time, end_time) + height = self._get_mini_bar_height() + + self.canvas.draw_mini_bar(x, y, width, height, cpu_no, selected) + + if job_no is not None: + x += GraphFormat.MINI_BAR_LABEL_OFS + y += self.attrs.y_item_size * GraphFormat.MINI_BAR_SIZE_FACTOR / 2.0 + self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \ + GraphFormat.DEF_FOPTS_MINI_BAR, GraphFormat.DEF_FOPTS_MINI_BAR_SSCRIPT, AlignMode.LEFT, AlignMode.CENTER) + + def add_sel_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, event): + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(task_no) - self._get_mini_bar_ofs() + width = self._get_bar_width(start_time, end_time) + height = self._get_mini_bar_height() + + self.canvas.add_sel_mini_bar(x, y, width, height, event) + +class CpuGraph(Graph): + def render_surface(self, sched): + self.canvas.whiteout() + self.canvas.clear_selectable_regions() + + start_time, end_time, start_item, end_item = self.get_offset_params() + + self.draw_skeleton(start_time, end_time, start_item, end_item) + + event_list = dict(schedule.EVENT_LIST) + + del event_list[schedule.ReleaseEvent] + del event_list[schedule.DeadlineEvent] + + for layer in Canvas.LAYERS: + prev_events = {} + for event in sched.get_time_slot_array().iter_over_period( + start_time, end_time, start_item, end_item, + schedule.TimeSlotArray.CPU_LIST, schedule.EVENT_LIST): + event.render(self, layer, prev_events) + + if end_item >= len(self.y_item_list): + # we are far down enough that we should render the releases and deadlines + for layer in Canvas.LAYERS: + prev_events = {} + for event in sched.get_time_slot_array().iter_over_period( + start_time, end_time, start_item, end_item, + schedule.TimeSlotArray.CPU_LIST, + (schedule.ReleaseEvent, schedule.DeadlineEvent)): + event.render(self, layer, prev_events) + + def render(self, schedule, start_time=None, end_time=None): + if end_time < start_time: + raise ValueError('start must be less than end') + + if start_time is None: + start_time = self.start + if end_time is None: + end_time = self.end + start_slot = self.get_time_slot(start_time) + end_slot = min(len(self.time_slots), self.get_time_slot(end_time) + 1) + + for layer in Canvas.LAYERS: + prev_events = {} + for i in range(start_slot, end_slot): + for event in self.time_slots[i]: + event.render(graph, layer, prev_events) + + def draw_suspend_triangle_at_time(self, time, task_no, cpu_no, selected=False): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0 + self.canvas.draw_suspend_triangle(x, y, height, selected) + + def add_sel_suspend_triangle_at_time(self, time, task_no, cpu_no, event): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.add_sel_suspend_triangle(x, y, height, event) + + def draw_resume_triangle_at_time(self, time, task_no, cpu_no, selected=False): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.draw_resume_triangle(x, y, height, selected) + + def add_sel_resume_triangle_at_time(self, time, task_no, cpu_no, event): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.add_sel_suspend_triangle(x, y, height, event) + + def draw_completion_marker_at_time(self, time, task_no, cpu_no, selected=False): + height = self._get_bar_height() * GraphFormat.COMPLETION_MARKER_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(cpu_no) + self._get_bar_height() - height + + self.canvas.draw_completion_marker(x, y, height, selected) + + def add_sel_completion_marker_at_time(self, time, task_no, cpu_no, event): + height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR + x = self._get_time_xpos(time) + y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0 + + self.canvas.add_sel_completion_marker(x, y, height, event) + + def draw_release_arrow_at_time(self, time, task_no, job_no=None, selected=False): + if job_no is None and task_no is not None: + raise ValueError("Must specify a job number along with the task number") + + height = self._get_bar_height() * GraphFormat.SMALL_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self.origin[1] - height + + self.canvas.draw_release_arrow_small(x, y, height, selected) + + if task_no is not None: + y -= GraphFormat.ARROW_LABEL_OFS + self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \ + GraphFormat.DEF_FOPTS_ARROW, GraphFormat.DEF_FOPTS_ARROW_SSCRIPT, \ + AlignMode.CENTER, AlignMode.BOTTOM) + + def add_sel_release_arrow_at_time(self, time, task_no, event): + height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self.origin[1] - height + + self.canvas.add_sel_release_arrow_small(x, y, height, event) + + def draw_deadline_arrow_at_time(self, time, task_no, job_no=None, selected=False): + if job_no is None and task_no is not None: + raise ValueError("Must specify a job number along with the task number") + + height = self._get_bar_height() * GraphFormat.SMALL_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self.origin[1] - height + + self.canvas.draw_deadline_arrow_small(x, y, height, selected) + + if task_no is not None: + y -= GraphFormat.ARROW_LABEL_OFS + self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \ + GraphFormat.DEF_FOPTS_ARROW, GraphFormat.DEF_FOPTS_ARROW_SSCRIPT, \ + AlignMode.CENTER, AlignMode.BOTTOM) + + def add_sel_deadline_arrow_at_time(self, time, task_no, event): + height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR + + x = self._get_time_xpos(time) + y = self.origin[1] - height + + self.canvas.add_sel_deadline_arrow_small(x, y, height, event) + + def draw_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False): + if start_time > end_time: + raise ValueError("Litmus is not a time machine") + + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(cpu_no) + width = self._get_bar_width(start_time, end_time) + height = self._get_bar_height() + + self.canvas.draw_bar(x, y, width, height, task_no, selected) + + # if a job number is specified, we want to draw a superscript and subscript for the task and job number, respectively + if job_no is not None: + x += GraphFormat.BAR_LABEL_OFS + y += self.attrs.y_item_size * GraphFormat.BAR_SIZE_FACTOR / 2.0 + self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \ + GraphFormat.DEF_FOPTS_BAR, GraphFormat.DEF_FOPTS_BAR_SSCRIPT, \ + AlignMode.LEFT, AlignMode.CENTER) + + def add_sel_bar_at_time(self, start_time, end_time, task_no, cpu_no, event): + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(cpu_no) + width = self._get_bar_width(start_time, end_time) + height = self._get_bar_height() + + self.canvas.add_sel_region(SelectableRegion(x, y, width, height, event)) + + def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False): + if start_time > end_time: + raise ValueError("Litmus is not a time machine") + + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(cpu_no) - self._get_mini_bar_ofs() + width = self._get_bar_width(start_time, end_time) + height = self._get_mini_bar_height() + + self.canvas.draw_mini_bar(x, y, width, height, cpu_no, selected) + + if job_no is not None: + x += GraphFormat.MINI_BAR_LABEL_OFS + y += self.attrs.y_item_size * GraphFormat.MINI_BAR_SIZE_FACTOR / 2.0 + self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \ + GraphFormat.DEF_FOPTS_MINI_BAR, GraphFormat.DEF_FOPTS_MINI_BAR_SSCRIPT, AlignMode.LEFT, AlignMode.CENTER) + + def add_sel_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, event): + x = self._get_time_xpos(start_time) + y = self._get_item_ypos(cpu_no) - self._get_mini_bar_ofs() + width = self._get_bar_width(start_time, end_time) + height = self._get_mini_bar_height() + + self.canvas.add_sel_mini_bar(x, y, width, height, cpu_no, selected) diff --git a/viz/format.py b/viz/format.py new file mode 100644 index 0000000..fed39f0 --- /dev/null +++ b/viz/format.py @@ -0,0 +1,92 @@ +"""Various formatting parameters intended to be accessible by the client.""" + +class FontOptions(object): + """Class for combining assorted simple font options.""" + def __init__(self, name, size, color): + self.name = name + self.size = size + self.color = color + +class AlignMode(object): + """Type that specifies the way something (probably text) + should be aligned, horizontally and/or vertically.""" + LEFT = 0 + CENTER = 1 + RIGHT = 2 + + BOTTOM = 3 + TOP = 4 + +class GraphFormat(object): + """Container class for a bunch of optional and non-optional attributes to configure the appearance of the graph + (because it would be annoying to just have these all as raw arguments to the Graph constructor, and many people + probably don't care about most of them anyway).""" + + GRID_COLOR = (0.7, 0.7, 0.7) + HIGHLIGHT_COLOR = (0.8, 0.0, 0.0) + BORDER_COLOR = (0.0, 0.0, 0.0) + LITE_BORDER_COLOR = (0.4, 0.4, 0.4) + + BORDER_THICKNESS = 1 + GRID_THICKNESS = 1 + AXIS_THICKNESS = 1 + + X_AXIS_MEASURE_OFS = 30 + X_AXIS_LABEL_GAP = 10 + Y_AXIS_ITEM_GAP = 10 + MAJ_TICK_SIZE = 20 + MIN_TICK_SIZE = 12 + + BIG_ARROWHEAD_FACTOR = 0.2 + SMALL_ARROWHEAD_FACTOR = 0.3 + TEE_FACTOR = 0.3 + + DEF_FOPTS_LABEL = FontOptions("Times", 16, (0.0, 0.0, 0.0)) + DEF_FOPTS_LABEL_SSCRIPT = FontOptions("Times", 8, (0.0, 0.0, 0.0)) + DEF_FOPTS_MAJ = FontOptions("Times", 14, (0.1, 0.1, 0.1)) + DEF_FOPTS_MIN = FontOptions("Times", 9, (0.1, 0.1, 0.1)) + DEF_FOPTS_ITEM = FontOptions("Times", 20, (0.0, 0.5, 0.1)) + DEF_FOPTS_BAR = FontOptions("Times", 14, (0.0, 0.0, 0.0)) + DEF_FOPTS_BAR_SSCRIPT = FontOptions("Times", 7, (0.0, 0.0, 0.0)) + DEF_FOPTS_MINI_BAR = FontOptions("Times", 11, (0.0, 0.0, 0.0)) + DEF_FOPTS_MINI_BAR_SSCRIPT = FontOptions("Times", 7, (0.0, 0.0, 0.0)) + DEF_FOPTS_ARROW = FontOptions("Times", 12, (0.0, 0.0, 0.0)) + DEF_FOPTS_ARROW_SSCRIPT = FontOptions("Times", 7, (0.0, 0.0, 0.0)) + + LEFT_SIDE_PAD = 30 + WIDTH_PAD = 50 + HEIGHT_PAD = 150 + Y_ITEM_PAD_FACTOR = 0.5 + + DEF_TIME_PER_MAJ = 10 + DEF_MAJ_SEP = 200 + DEF_MIN_PER_MAJ = 5 + DEF_Y_ITEM_SIZE = 50 + + AXIS_LABEL_VERT_OFS = 30 + BAR_SIZE_FACTOR = 0.4 + MINI_BAR_SIZE_FACTOR = 0.2 + BAR_MINI_BAR_GAP_FACTOR = 0.1 + + BAR_LABEL_OFS = 2 + MINI_BAR_LABEL_OFS = 1 + ARROW_LABEL_OFS = 2 + + BLOCK_TRIANGLE_FACTOR = 0.7 + BIG_ARROW_FACTOR = 1.6 + SMALL_ARROW_FACTOR = 0.6 + COMPLETION_MARKER_FACTOR = 1.6 + + def __init__(self, time_per_maj=DEF_TIME_PER_MAJ, maj_sep=DEF_MAJ_SEP, \ + min_per_maj=DEF_MIN_PER_MAJ, y_item_size=DEF_Y_ITEM_SIZE, bar_fopts=DEF_FOPTS_BAR, \ + item_fopts=DEF_FOPTS_ITEM, show_min=False, majfopts=DEF_FOPTS_MAJ, \ + minfopts=DEF_FOPTS_MIN): + self.time_per_maj = time_per_maj + self.maj_sep = maj_sep + self.min_per_maj = min_per_maj + self.y_item_size = y_item_size + self.item_fopts = item_fopts + self.bar_fopts = bar_fopts + self.show_min = show_min + self.majfopts = majfopts + self.minfopts = minfopts diff --git a/viz/renderer.py b/viz/renderer.py new file mode 100644 index 0000000..d94129c --- /dev/null +++ b/viz/renderer.py @@ -0,0 +1,40 @@ +#!/usr/bin/python +from schedule import * +from draw import * + +"""The renderer, a glue object which converts a schedule to its representation +on a graph.""" + +class Renderer(object): + def __init__(self, schedule): + self.schedule = schedule + + def prepare_task_graph(self, SurfaceType=ImageSurface, attrs=GraphFormat()): + """Outputs the fully-rendered graph (y-axis = tasks) to a Cairo ImageSurface""" + item_list = self.get_task_item_list() + start, end = self.schedule.get_time_bounds() + self.graph = TaskGraph(CairoCanvas, SurfaceType(), start, end, item_list, attrs) + + def prepare_cpu_graph(self, SurfaceType=ImageSurface, attrs=GraphFormat()): + item_list = ['CPU %d' % i for i in range(0, self.schedule.get_num_cpus())] + start, end = self.schedule.get_time_bounds() + self.graph = CpuGraph(CairoCanvas, SurfaceType(), start, end, item_list, attrs) + + def render_graph_full(self): + """Does the heavy lifting for rendering a task or CPU graph, by scanning the schedule + and drawing it piece by piece""" + #graph.draw_axes('Time', '') + self.schedule.render(self.graph) + + def write_out(self, fname): + self.graph.surface.write_out(fname) + + def get_graph(self): + return self.graph + + def get_schedule(self): + return self.schedule + + def get_task_item_list(self): + return [task.get_name() for task in self.schedule.get_task_list()] + diff --git a/viz/schedule.py b/viz/schedule.py new file mode 100644 index 0000000..f842c8d --- /dev/null +++ b/viz/schedule.py @@ -0,0 +1,571 @@ +#!/usr/bin/env python + +"""The data structures to store a schedule (task system), along with all +the job releases and other events that have occurred for each task. This gives +a high-level representation of a schedule that can be converted to, say, a +graphic.""" + +from draw import * +import util + +class TimeSlotArray(object): + """Represents another way of organizing the events. This structure organizes events by + the (approximate) time at which they occur. Events that occur at approximately the same + time are assigned the same ``slot'', and each slot organizes its events by task number + as well as by CPU.""" + + TASK_LIST = 0 + CPU_LIST = 1 + + def __init__(self, start, end, time_per_maj, num_tasks, num_cpus): + self.start = start + self.end = end + self.time_per_maj = time_per_maj + self.list_sizes = { TimeSlotArray.TASK_LIST : num_tasks, TimeSlotArray.CPU_LIST : num_cpus } + self.array = [{TimeSlotArray.TASK_LIST : [{} for i in range(0, num_tasks)], \ + TimeSlotArray.CPU_LIST : [{} for i in range (0, num_cpus)]} \ + for i in range(0, (end - start) // self.time_per_maj + 1)] + + def get_time_slot(self, time): + return int((time - self.start) // self.time_per_maj) + + def add_event_to_time_slot(self, event): + task_no = event.get_job().get_task().get_task_no() + cpu = event.get_cpu() + time_slot = self.get_time_slot(event.get_time()) + + self.array[time_slot][TimeSlotArray.TASK_LIST][task_no][event.__class__] = event + self.array[time_slot][TimeSlotArray.CPU_LIST][cpu][event.__class__] = event + + span_events = { SwitchAwayEvent : IsRunningDummy, InversionEndEvent : InversionDummy} + + for span_event in span_events: + if isinstance(event, span_event) and not event.is_erroneous(): + start_slot = self.get_time_slot(event.corresp_start_event.get_time()) + end_slot = self.get_time_slot(event.get_time()) + for slot in range(start_slot + 1, end_slot): + dummy = span_events[span_event](task_no, cpu) + dummy.corresp_start_event = event.corresp_start_event + self.array[slot][TimeSlotArray.TASK_LIST][task_no][dummy.__class__] = dummy + self.array[slot][TimeSlotArray.CPU_LIST][cpu][dummy.__class__] = dummy + + def iter_over_period(self, start, end, start_no, end_no, list_type, event_types): + if start > end: + raise ValueError('Litmus is not a time machine') + if start_no > end_no: + raise ValueError('start no should be less than end no') + + start_slot = max(0, self.get_time_slot(start)) + end_slot = min(len(self.array), self.get_time_slot(end) + 2) + + start_no = max(0, start_no) + end_no = min(self.list_sizes[list_type] - 1, end_no) + + for slot in range(start_slot, end_slot): + for no in range(start_no, end_no + 1): + for type in event_types: + if type in self.array[slot][list_type][no]: + yield self.array[slot][list_type][no][type] + +class Schedule(object): + """The total schedule (task system), consisting of a certain number of + tasks.""" + + def __init__(self, name, num_cpus, task_list=[]): + self.name = name + self.tasks = {} + self.task_list = [] + self.time_slot_array = None + self.cur_task_no = 0 + self.num_cpus = num_cpus + for task in task_list: + self.add_task(task) + + def set_time_params(self, time_per_maj=None): + if self.get_task_list() is None: + return (0, 0) + + def find_extreme_time_sched(sched, cmp): + def find_extreme_time_task(task, cmp): + def find_extreme_time_job(job, cmp): + extreme_time = None + for time in job.get_events(): + if extreme_time is None or cmp(time, extreme_time) < 0: + extreme_time = time + return extreme_time + + extreme_time = None + for job_no in task.get_jobs(): + time = find_extreme_time_job(task.get_jobs()[job_no], cmp) + if time is not None and (extreme_time is None or cmp(time, extreme_time) < 0): + extreme_time = time + return extreme_time + + extreme_time = None + for task in sched.get_task_list(): + time = find_extreme_time_task(task, cmp) + if time is not None and (extreme_time is None or cmp(time, extreme_time) < 0): + extreme_time = time + + return extreme_time + + def earliest_cmp(x, y): + diff = x - y + if diff > 0.0: + return 1 + elif diff == 0.0: + return 0 + elif diff < 0.0: + return -1 + + def latest_cmp(x, y): + diff = x - y + if diff < 0.0: + return 1 + elif diff == 0.0: + return 0 + elif diff > 0.0: + return -1 + + self.start = find_extreme_time_sched(self, earliest_cmp) + self.end = find_extreme_time_sched(self, latest_cmp) + self.time_per_maj = time_per_maj + self.time_slot_array = None + if self.time_per_maj is not None: + self.time_slot_array = TimeSlotArray(self.start, self.end, time_per_maj, \ + len(self.task_list), self.num_cpus) + + def get_time_slot_array(self): + return self.time_slot_array + + def get_time_bounds(self): + return (self.start, self.end) + + def scan(self, time_per_maj): + self.set_time_params(time_per_maj) + + # we scan the graph task by task, and job by job + switches = {} + for event in EVENT_LIST: + switches[event] = None + for task_no, task in enumerate(self.get_task_list()): + cur_cpu = [Event.NO_CPU] + for job_no in sorted(task.get_jobs().keys()): + job = task.get_jobs()[job_no] + for event_time in sorted(job.get_events().keys()): + # could have multiple events at the same time (unlikely but possible) + for event in job.get_events()[event_time]: + print "task, job, event:", task.name, job.job_no, event.__class__.__name__ + event.scan(cur_cpu, switches) + + def add_task(self, task): + if task.name in self.tasks: + raise ValueError("task already in list!") + self.tasks[task.name] = task + self.task_list.append(task) + task.schedule = self + task.task_no = self.cur_task_no + self.cur_task_no += 1 + + def get_tasks(self): + return self.tasks + + def get_task_list(self): + return self.task_list + + def get_name(self): + return self.name + + def get_num_cpus(self): + return self.num_cpus + +class Task(object): + """Represents a task, including the set of jobs that were run under + this task.""" + + def __init__(self, name, job_list=[]): + self.name = name + self.jobs = {} + self.task_no = None + self.schedule = None + for job in job_list: + self.add_job(job) + + def add_job(self, job): + if job.job_no in self.jobs: + raise ScheduleError("a job is already being released at this time for this task") + self.jobs[job.job_no] = job + job.task = self + + def get_schedule(self): + return self.schedule + + def get_jobs(self): + return self.jobs + + def get_task_no(self): + return self.task_no + + def get_name(self): + return self.name + +class Job(object): + """Represents a job, including everything that happens related to the job""" + def __init__(self, job_no, event_list=[]): + self.job_no = job_no + self.events = {} + self.task = None + for event in event_list: + self.add_event(event) + + def add_event(self, event): + if event.time not in self.events: + self.events[event.time] = [] + self.events[event.time].append(event) + event.job = self + + def get_events(self): + return self.events + + def get_task(self): + return self.task + + def get_job_no(self): + return self.job_no + +class DummyEvent(object): + """Represents some event that occurs, but might not actually be + a full-fledged ``event'' in the schedule. It might instead be a dummy + event added by the application to speed things up or keep track of + something. Such an event won't be added to the schedule tree, but + might appear in the time slot array.""" + + def __init__(self, time, cpu): + self.time = time + self.cpu = cpu + self.job = None + self.layer = None + + def __str__(self): + return '[Dummy Event]' + + def get_time(self): + return self.time + + def get_cpu(self): + return self.cpu + + def get_job(self): + return self.job + + def get_layer(self): + return self.layer + + def render(self, graph, layer, prev_events): + """Method that the visualizer calls to tell the event to render itself + Obviously only implemented by subclasses (actual event types)""" + raise NotImplementdError + +class Event(DummyEvent): + """Represents an event that occurs while a job is running (e.g. get scheduled + on a CPU, block, ...)""" + NO_CPU = -1 + NUM_DEC_PLACES = 2 + + def __init__(self, time, cpu): + super(Event, self).__init__(time, cpu) + self.erroneous = False + self.selected = False + + def __str__(self): + return '[Event]' + + def _common_str(self): + job = self.get_job() + task = job.get_task() + return ' for task ' + str(task.get_name()) + ': (TASK, JOB)=' + str((task.get_task_no(), \ + job.get_job_no())) + ', CPU=' + str(self.get_cpu()) + + def is_erroneous(self): + """An erroneous event is where something with the event is not quite right, + something significantly wrong that we don't have logical information telling + us how we should render the event.""" + return self.erroneous + + def is_selected(self): + """Returns whether the event has been selected by the user. (needed for rendering)""" + return self.selected + + def set_selected(self, sel): + """Sets the event's state to selected.""" + self.selected = sel + + def scan(self, cur_cpu, switches): + """Part of the procedure that walks through all the events and sets + some parameters that are unknown at first. For instance, a SwitchAwayEvent + should know when the previous corresponding SwitchToEvent occurred, but + the data does not tell us this, so we have to figure that out on our own + by scanning through the events. ``cur_cpu'' gives the current CPU at this + time in the scan, and ``switches'' gives the last time a certain switch + (e.g. SwitchToEvent, InversionStartEvent) occurred""" + + self.get_job().get_task().get_schedule().get_time_slot_array().add_event_to_time_slot(self) + +class ErrorEvent(Event): + pass + +class SuspendEvent(Event): + def __init__(self, time, cpu): + super(SuspendEvent, self).__init__(time, cpu) + self.layer = Canvas.MIDDLE_LAYER + + def __str__(self): + return 'Suspend' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + if self.get_cpu() != cur_cpu[0]: + self.erroneous = True + print "suspending on a CPU different from the CPU we are on!" + super(SuspendEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if layer == self.layer: + prev_events[self] = None + graph.draw_suspend_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_cpu(), self.is_selected()) + graph.add_sel_suspend_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_cpu(), self) + +class ResumeEvent(Event): + def __init__(self, time, cpu): + super(ResumeEvent, self).__init__(time, cpu) + self.layer = Canvas.MIDDLE_LAYER + + def __str__(self): + return 'Resume' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + if cur_cpu[0] != Event.NO_CPU and cur_cpu[0] != self.get_cpu(): + self.erroneous = True + print "Resuming when currently scheduled on a CPU, but on a different CPU from the current CPU!" + super(ResumeEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if layer == self.layer: + prev_events[self] = None + graph.draw_resume_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_cpu(), self.is_selected()) + graph.add_sel_resume_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_cpu(), self) + +class CompleteEvent(Event): + def __init__(self, time, cpu): + super(CompleteEvent, self).__init__(time, cpu) + self.layer = Canvas.TOP_LAYER + + def __str__(self): + return 'Complete' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + super(CompleteEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if layer == Canvas.TOP_LAYER: + prev_events[self] = None + graph.draw_completion_marker_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_cpu(), self.is_selected()) + graph.add_sel_completion_marker_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_cpu(), self) + + +class SwitchAwayEvent(Event): + def __init__(self, time, cpu): + super(SwitchAwayEvent, self).__init__(time, cpu) + self.layer = Canvas.BOTTOM_LAYER + + def __str__(self): + if self.corresp_start_event is None: + return 'Switch Away (w/o Switch To)' + self._common_str() + 'TIME=' \ + + self.get_time() + return str(self.corresp_start_event) + + def scan(self, cur_cpu, switches): + old_cur_cpu = cur_cpu[0] + + self.corresp_start_event = switches[SwitchToEvent] + + cur_cpu[0] = Event.NO_CPU + switches[SwitchToEvent] = None + + if self.corresp_start_event is not None: + self.corresp_start_event.corresp_end_event = self + + if self.get_cpu() != old_cur_cpu: + self.erroneous = True + print "switching away from a CPU different from the CPU we are currently on" + if self.corresp_start_event is None: + self.erroneous = True + print "switch away was not matched by a corresponding switch to" + elif self.get_time() < self.corresp_start_event.get_time(): + self.erroneous = True + print "switching away from a processor before we switched to it?!" + + super(SwitchAwayEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if self.corresp_start_event is None or self.corresp_start_event in prev_events: + return # erroneous switch away or already rendered + self.corresp_start_event.render(graph, layer, prev_events) + +class SwitchToEvent(Event): + def __init__(self, time, cpu): + super(SwitchToEvent, self).__init__(time, cpu) + self.layer = Canvas.BOTTOM_LAYER + + def __str__(self): + if self.corresp_end_event is None: + return 'Switch To (w/o Switch Away)' + self._common_str() + ', TIME=' \ + + self.get_time() + return 'Scheduled' + self._common_str() + ', START=' \ + + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) \ + + ', END=' + util.format_float(self.corresp_end_event.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + old_cur_cpu = cur_cpu[0] + cur_cpu[0] = self.get_cpu() + switches[SwitchToEvent] = self + self.corresp_end_event = None + + if old_cur_cpu != Event.NO_CPU: + self.erroneous = True + print "currently scheduled somewhere, can't switch to a CPU" + + super(SwitchToEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if self.is_erroneous(): + return # erroneous switch to + if layer == Canvas.BOTTOM_LAYER: + prev_events[self] = None + cpu = self.get_cpu() + task_no = self.get_job().get_task().get_task_no() + graph.draw_bar_at_time(self.get_time(), self.corresp_end_event.get_time(), + task_no, cpu, self.get_job().get_job_no(), self.is_selected()) + graph.add_sel_bar_at_time(self.get_time(), self.corresp_end_event.get_time(), + task_no, cpu, self) + +class ReleaseEvent(Event): + def __init__(self, time, cpu): + super(ReleaseEvent, self).__init__(time, cpu) + self.layer = Canvas.TOP_LAYER + + def __str__(self): + return 'Release' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + super(ReleaseEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + prev_events[self] = None + if layer == Canvas.TOP_LAYER: + graph.draw_release_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_job().get_job_no(), self.is_selected()) + graph.add_sel_release_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self) + +class DeadlineEvent(Event): + def __init__(self, time, cpu): + super(DeadlineEvent, self).__init__(time, cpu) + self.layer = Canvas.TOP_LAYER + + def __str__(self): + return 'Deadline' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + super(DeadlineEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + prev_events[self] = None + if layer == Canvas.TOP_LAYER: + graph.draw_deadline_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self.get_job().get_job_no(), self.is_selected()) + graph.add_sel_deadline_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(), + self) + +class InversionStartEvent(ErrorEvent): + def __init__(self, time): + super(InversionStartEvent, self).__init__(time, Event.NO_CPU) + self.layer = Canvas.BOTTOM_LAYER + + def __str__(self): + if self.corresp_end_event is None: + print 'Inversion Start (w/o Inversion End)' + self._common_str() \ + + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + return 'Priority Inversion' + self._common_str() + ', START=' \ + + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) \ + + ', END=' + util.format_float(self.corresp_end_event.get_time(), Event.NUM_DEC_PLACES) + + def scan(self, cur_cpu, switches): + switches[InversionStartEvent] = self + self.corresp_end_event = None + + # the corresp_end_event should already be set + super(InversionStartEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if layer == Canvas.BOTTOM_LAYER: + prev_events[self] = None + cpu = self.get_cpu() + task_no = self.get_job().get_task().get_task_no() + graph.draw_mini_bar_at_time(self.get_time(), self.corresp_end_event.get_time(), + task_no, cpu, self.get_job().get_job_no(), self.is_selected()) + graph.add_sel_mini_bar_at_time(self.get_time(), self.corresp_end_event.get_time(), + task_no, cpu, self) + +class InversionEndEvent(ErrorEvent): + def __init__(self, time): + super(InversionEndEvent, self).__init__(time, Event.NO_CPU) + self.layer = Canvas.BOTTOM_LAYER + + def __str__(self): + if self.corresp_start_event is None: + print 'Inversion End (w/o Inversion Start)' + self._common_str() \ + + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) + + return str(self.corresp_start_event) + + def scan(self, cur_cpu, switches): + self.corresp_start_event = switches[InversionStartEvent] + + cur_cpu[0] = Event.NO_CPU + switches[InversionStartEvent] = None + + if self.corresp_start_event is not None: + self.corresp_start_event.corresp_end_event = self + + if self.corresp_start_event is None: + self.erroneous = True + print "inversion end was not matched by a corresponding inversion start" + + super(InversionEndEvent, self).scan(cur_cpu, switches) + + def render(self, graph, layer, prev_events): + if self.corresp_start_event is None or self.corresp_start_event in prev_events: + return # erroneous inversion end or already rendered + self.corresp_start_event.render(graph, layer, prev_events) + +class InversionDummy(DummyEvent): + def render(self, graph, layer, prev_events): + if self.corresp_start_event in prev_events: + return # we have already been rendered + self.corresp_start_event.render(graph, layer, prev_events) + +class IsRunningDummy(DummyEvent): + def render(self, graph, layer, prev_events): + if self.corresp_start_event in prev_events: + return # we have already been rendered + self.corresp_start_event.render(graph, layer, prev_events) + +EVENT_LIST = {SuspendEvent : None, ResumeEvent : None, CompleteEvent : None, SwitchAwayEvent : None, + SwitchToEvent : None, ReleaseEvent : None, DeadlineEvent : None, IsRunningDummy : None, + InversionStartEvent : None, InversionEndEvent : None, InversionDummy : None} diff --git a/viz/util.py b/viz/util.py new file mode 100644 index 0000000..3111f39 --- /dev/null +++ b/viz/util.py @@ -0,0 +1,9 @@ +#!/usr/bin/python + +"""Miscellanious utility functions that don't fit anywhere.""" + +def format_float(num, numplaces): + if abs(round(num, numplaces) - round(num, 0)) == 0.0: + return '%.0f' % float(num) + else: + return ('%.' + numplaces + 'f') % round(float(num), numplaces) diff --git a/viz/viewer.py b/viz/viewer.py new file mode 100644 index 0000000..a695473 --- /dev/null +++ b/viz/viewer.py @@ -0,0 +1,193 @@ +#!/usr/bin/python + +"""GUI stuff.""" + +from schedule import * +from renderer import * + +import pygtk +import gtk +import gobject + +class GraphArea(gtk.DrawingArea): + DAREA_WIDTH_REQ = 500 + DAREA_HEIGHT_REQ = 300 + HORIZ_PAGE_SCROLL_FACTOR = 4.8 + HORIZ_STEP_SCROLL_FACTOR = 0.8 + VERT_PAGE_SCROLL_FACTOR = 3.0 + VERT_STEP_SCROLL_FACTOR = 0.5 + + def __init__(self, renderer): + super(GraphArea, self).__init__() + + self.renderer = renderer + + self.cur_x = 0 + self.cur_y = 0 + self.width = 0 + self.height = 0 + + self.now_selected = [] + + self.set_set_scroll_adjustments_signal('set-scroll-adjustments') + + self.add_events(gtk.gdk.BUTTON_PRESS_MASK | gtk.gdk.POINTER_MOTION_MASK | gtk.gdk.POINTER_MOTION_HINT_MASK) + + self.connect('expose-event', self.expose) + self.connect('size-allocate', self.size_allocate) + self.connect('set-scroll-adjustments', self.set_scroll_adjustments) + self.connect('button-press-event', self.button_press) + self.connect('motion-notify-event', self.motion_notify) + + self.set_size_request(GraphArea.DAREA_WIDTH_REQ, GraphArea.DAREA_HEIGHT_REQ) + + def expose(self, widget, event, data=None): + ctx = widget.window.cairo_create() + graph = self.renderer.get_graph() + graph.update_view(self.cur_x, self.cur_y, self.width, self.height, ctx) + graph.render_surface(self.renderer.get_schedule()) + + def set_scroll_adjustments(self, widget, horizontal, vertical, data=None): + graph = self.renderer.get_graph() + width = graph.get_width() + height = graph.get_height() + + self.horizontal = horizontal + self.vertical = vertical + self.config_scrollbars(self.cur_x, self.cur_y) + + self.horizontal.connect('value-changed', self.horizontal_value_changed) + self.vertical.connect('value-changed', self.vertical_value_changed) + + def horizontal_value_changed(self, adjustment): + self.cur_x = min(adjustment.value, self.renderer.get_graph().get_width()) + self.cur_x = max(adjustment.value, 0.0) + + rect = gtk.gdk.Rectangle(0, 0, self.width, self.height) + self.window.invalidate_rect(rect, True) + + def vertical_value_changed(self, adjustment): + self.cur_y = min(adjustment.value, self.renderer.get_graph().get_height()) + self.cur_y = max(adjustment.value, 0.0) + + rect = gtk.gdk.Rectangle(0, 0, self.width, self.height) + self.window.invalidate_rect(rect, True) + + def size_allocate(self, widget, allocation): + self.width = allocation.width + self.height = allocation.height + self.config_scrollbars(self.cur_x, self.cur_y) + + def config_scrollbars(self, hvalue, vvalue): + graph = self.renderer.get_graph() + width = graph.get_width() + height = graph.get_height() + + if self.horizontal is not None: + self.horizontal.set_all(hvalue, 0.0, width, graph.get_attrs().maj_sep * GraphArea.HORIZ_STEP_SCROLL_FACTOR, + graph.get_attrs().maj_sep * GraphArea.HORIZ_PAGE_SCROLL_FACTOR, self.width) + if self.vertical is not None: + self.vertical.set_all(vvalue, 0.0, height, graph.get_attrs().y_item_size * GraphArea.VERT_STEP_SCROLL_FACTOR, + graph.get_attrs().y_item_size * GraphArea.VERT_PAGE_SCROLL_FACTOR, self.height) + + def _find_max_layer(self, regions): + max_layer = Canvas.BOTTOM_LAYER + for event in regions: + if event.get_layer() > max_layer: + max_layer = event.get_layer() + return max_layer + + def motion_notify(self, widget, motion_event, data=None): + msg = None + + graph = self.renderer.get_graph() + just_selected = graph.get_selected_regions(motion_event.x, motion_event.y) + if not just_selected: + msg = '' + the_event = None + else: + max_layer = self._find_max_layer(just_selected) + + for event in just_selected: + if event.get_layer() == max_layer: + the_event = event + break + + msg = str(the_event) + + self.emit('update-event-description', the_event, msg) + + def button_press(self, widget, button_event, data=None): + graph = self.renderer.get_graph() + + if button_event.button == 1: + just_selected = graph.get_selected_regions(button_event.x, button_event.y) + + max_layer = self._find_max_layer(just_selected) + + # only select those events which were in the top layer (it's + # not intuitive to click something and then have something + # below it get selected). Also, clicking something that + # is selected deselects it + new_now_selected = {} + for event in just_selected: + if event.get_layer() == max_layer: + if not event.is_selected(): + new_now_selected[event] = None + event.set_selected(not event.is_selected()) + break + + for event in self.now_selected: + if event not in new_now_selected: + event.set_selected(False) + + self.now_selected = new_now_selected + + rect = gtk.gdk.Rectangle(0, 0, self.width, self.height) + self.window.invalidate_rect(rect, True) + +class GraphWindow(gtk.ScrolledWindow): + def __init__(self, renderer): + super(GraphWindow, self).__init__(None, None) + + self.garea = GraphArea(renderer) + self.add(self.garea) + self.garea.show() + + def get_graph_area(self): + return self.garea + +class MainWindow(object): + def __init__(self, renderer): + self.window = gtk.Window(gtk.WINDOW_TOPLEVEL) + + self.window.connect('delete_event', self.delete_event) + self.window.connect('destroy', self.destroy) + + self.vbox = gtk.VBox(False, 0) + + self.gwindow = GraphWindow(renderer) + self.gwindow.get_graph_area().connect('update-event-description', + self.update_event_description) + self.gwindow.show() + + self.desc_label = gtk.Label('') + self.desc_label.set_justify(gtk.JUSTIFY_LEFT) + self.desc_label.show() + + self.vbox.pack_start(self.gwindow, True, True, 0) + self.vbox.pack_start(self.desc_label, False, False, 0) + self.vbox.show() + + self.window.add(self.vbox) + self.window.show() + + def update_event_description(self, widget, event, msg): + self.desc_label.set_text(msg) + + def delete_event(self, widget, event, data=None): + return False + + def destroy(self, widget, data=None): + gtk.main_quit() + -- cgit v1.2.2