xref: /freebsd/tools/sched/schedgraph.py (revision 7bd6fde3) 
1#!/usr/local/bin/python
2
3# Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org>
4# All rights reserved.
5#
6# Redistribution and use in source and binary forms, with or without
7# modification, are permitted provided that the following conditions
8# are met:
9# 1. Redistributions of source code must retain the above copyright
10#    notice unmodified, this list of conditions, and the following
11#    disclaimer.
12# 2. Redistributions in binary form must reproduce the above copyright
13#    notice, this list of conditions and the following disclaimer in the
14#     documentation and/or other materials provided with the distribution.
15#
16# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26#
27# $FreeBSD$
28
29import sys
30import re
31from Tkinter import *
32
33# To use:
34# - Install the ports/x11-toolkits/py-tkinter package.
35# - Add KTR_SCHED to KTR_COMPILE and KTR_MASK in your KERNCONF
36# - It is encouraged to increase KTR_ENTRIES size to 32768 to gather
37#    enough information for analysis.
38# - Rebuild kernel with proper changes to KERNCONF.
39# - Dump the trace to a file: 'ktrdump -ct > ktr.out'
40# - Run the python script: 'python schedgraph.py ktr.out'
41#
42# To do:
43# 1)  Add a per-thread summary display
44# 2)  Add bounding box style zoom.
45# 3)  Click to center.
46# 4)  Implement some sorting mechanism.
47
48ticksps = None
49status = None
50configtypes = []
51
52def ticks2sec(ticks):
53	us = ticksps / 1000000
54	ticks /= us
55	if (ticks < 1000):
56		return (str(ticks) + "us")
57	ticks /= 1000
58	if (ticks < 1000):
59		return (str(ticks) + "ms")
60	ticks /= 1000
61	return (str(ticks) + "s")
62
63class Scaler(Frame):
64	def __init__(self, master, target):
65		Frame.__init__(self, master)
66		self.scale = Scale(self, command=self.scaleset,
67		    from_=1000, to_=10000000, orient=HORIZONTAL,
68		    resolution=1000)
69		self.label = Label(self, text="Ticks per pixel")
70		self.label.pack(side=LEFT)
71		self.scale.pack(fill="both", expand=1)
72		self.target = target
73		self.scale.set(target.scaleget())
74		self.initialized = 1
75
76	def scaleset(self, value):
77		self.target.scaleset(int(value))
78
79	def set(self, value):
80		self.scale.set(value)
81
82class Status(Frame):
83	def __init__(self, master):
84		Frame.__init__(self, master)
85		self.label = Label(self, bd=1, relief=SUNKEN, anchor=W)
86		self.label.pack(fill="both", expand=1)
87		self.clear()
88
89	def set(self, str):
90		self.label.config(text=str)
91
92	def clear(self):
93		self.label.config(text="")
94
95	def startup(self, str):
96		self.set(str)
97		root.update()
98
99class EventConf(Frame):
100	def __init__(self, master, name, color, enabled):
101		Frame.__init__(self, master)
102		self.name = name
103		self.color = StringVar()
104		self.color_default = color
105		self.color_current = color
106		self.color.set(color)
107		self.enabled = IntVar()
108		self.enabled_default = enabled
109		self.enabled_current = enabled
110		self.enabled.set(enabled)
111		self.draw()
112
113	def draw(self):
114		self.label = Label(self, text=self.name, anchor=W)
115		self.sample = Canvas(self, width=24, height=24,
116		    bg='grey')
117		self.rect = self.sample.create_rectangle(0, 0, 24, 24,
118		    fill=self.color.get())
119		self.list = OptionMenu(self, self.color,
120		    "dark red", "red", "pink",
121		    "dark orange", "orange",
122		    "yellow", "light yellow",
123		    "dark green", "green", "light green",
124		    "dark blue", "blue", "light blue",
125		    "dark violet", "violet", "purple",
126		    "dark grey", "light grey",
127		    "white", "black",
128		    command=self.setcolor)
129		self.checkbox = Checkbutton(self, text="enabled",
130		    variable=self.enabled)
131		self.label.grid(row=0, column=0, sticky=E+W)
132		self.sample.grid(row=0, column=1)
133		self.list.grid(row=0, column=2, sticky=E+W)
134		self.checkbox.grid(row=0, column=3)
135		self.columnconfigure(0, weight=1)
136		self.columnconfigure(2, minsize=110)
137
138	def setcolor(self, color):
139		self.color.set(color)
140		self.sample.itemconfigure(self.rect, fill=color)
141
142	def apply(self):
143		cchange = 0
144		echange = 0
145		if (self.color_current != self.color.get()):
146			cchange = 1
147		if (self.enabled_current != self.enabled.get()):
148			echange = 1
149		self.color_current = self.color.get()
150		self.enabled_current = self.enabled.get()
151		if (echange != 0):
152			if (self.enabled_current):
153				graph.setcolor(self.name, self.color_current)
154			else:
155				graph.hide(self.name)
156			return
157		if (cchange != 0):
158			graph.setcolor(self.name, self.color_current)
159
160	def revert(self):
161		self.setcolor(self.color_current)
162		self.enabled.set(self.enabled_current)
163
164	def default(self):
165		self.setcolor(self.color_default)
166		self.enabled.set(self.enabled_default)
167
168class EventConfigure(Toplevel):
169	def __init__(self):
170		Toplevel.__init__(self)
171		self.resizable(0, 0)
172		self.title("Event Configuration")
173		self.items = LabelFrame(self, text="Event Type")
174		self.buttons = Frame(self)
175		self.drawbuttons()
176		self.items.grid(row=0, column=0, sticky=E+W)
177		self.columnconfigure(0, weight=1)
178		self.buttons.grid(row=1, column=0, sticky=E+W)
179		self.types = []
180		self.irow = 0
181		for type in configtypes:
182			self.additem(type.name, type.color, type.enabled)
183
184	def additem(self, name, color, enabled=1):
185		item = EventConf(self.items, name, color, enabled)
186		self.types.append(item)
187		item.grid(row=self.irow, column=0, sticky=E+W)
188		self.irow += 1
189
190	def drawbuttons(self):
191		self.apply = Button(self.buttons, text="Apply",
192		    command=self.apress)
193		self.revert = Button(self.buttons, text="Revert",
194		    command=self.rpress)
195		self.default = Button(self.buttons, text="Default",
196		    command=self.dpress)
197		self.apply.grid(row=0, column=0, sticky=E+W)
198		self.revert.grid(row=0, column=1, sticky=E+W)
199		self.default.grid(row=0, column=2, sticky=E+W)
200		self.buttons.columnconfigure(0, weight=1)
201		self.buttons.columnconfigure(1, weight=1)
202		self.buttons.columnconfigure(2, weight=1)
203
204	def apress(self):
205		for item in self.types:
206			item.apply()
207
208	def rpress(self):
209		for item in self.types:
210			item.revert()
211
212	def dpress(self):
213		for item in self.types:
214			item.default()
215
216class EventView(Toplevel):
217	def __init__(self, event, canvas):
218		Toplevel.__init__(self)
219		self.resizable(0, 0)
220		self.title("Event")
221		self.event = event
222		self.frame = Frame(self)
223		self.frame.grid(row=0, column=0, sticky=N+S+E+W)
224		self.buttons = Frame(self)
225		self.buttons.grid(row=1, column=0, sticky=E+W)
226		self.canvas = canvas
227		self.drawlabels()
228		self.drawbuttons()
229		event.displayref(canvas)
230		self.bind("<Destroy>", self.destroycb)
231
232	def destroycb(self, event):
233		self.unbind("<Destroy>")
234		if (self.event != None):
235			self.event.displayunref(self.canvas)
236			self.event = None
237		self.destroy()
238
239	def clearlabels(self):
240		for label in self.frame.grid_slaves():
241			label.grid_remove()
242
243	def drawlabels(self):
244		ypos = 0
245		labels = self.event.labels()
246		while (len(labels) < 7):
247			labels.append(("", "", 0))
248		for label in labels:
249			name, value, linked = label
250			l = Label(self.frame, text=name, bd=1, width=15,
251			    relief=SUNKEN, anchor=W)
252			if (linked):
253				fgcolor = "blue"
254			else:
255				fgcolor = "black"
256			r = Label(self.frame, text=value, bd=1,
257			    relief=SUNKEN, anchor=W, fg=fgcolor)
258			l.grid(row=ypos, column=0, sticky=E+W)
259			r.grid(row=ypos, column=1, sticky=E+W)
260			if (linked):
261				r.bind("<Button-1>", self.linkpress)
262			ypos += 1
263		self.frame.columnconfigure(1, minsize=80)
264
265	def drawbuttons(self):
266		self.back = Button(self.buttons, text="<", command=self.bpress)
267		self.forw = Button(self.buttons, text=">", command=self.fpress)
268		self.new = Button(self.buttons, text="new", command=self.npress)
269		self.back.grid(row=0, column=0, sticky=E+W)
270		self.forw.grid(row=0, column=1, sticky=E+W)
271		self.new.grid(row=0, column=2, sticky=E+W)
272		self.buttons.columnconfigure(2, weight=1)
273
274	def newevent(self, event):
275		self.event.displayunref(self.canvas)
276		self.clearlabels()
277		self.event = event
278		self.event.displayref(self.canvas)
279		self.drawlabels()
280
281	def npress(self):
282		EventView(self.event, self.canvas)
283
284	def bpress(self):
285		prev = self.event.prev()
286		if (prev == None):
287			return
288		while (prev.real == 0):
289			prev = prev.prev()
290			if (prev == None):
291				return
292		self.newevent(prev)
293
294	def fpress(self):
295		next = self.event.next()
296		if (next == None):
297			return
298		while (next.real == 0):
299			next = next.next()
300			if (next == None):
301				return
302		self.newevent(next)
303
304	def linkpress(self, wevent):
305		event = self.event.getlinked()
306		if (event != None):
307			self.newevent(event)
308
309class Event:
310	name = "none"
311	color = "grey"
312	def __init__(self, source, cpu, timestamp, last=0):
313		self.source = source
314		self.cpu = cpu
315		self.timestamp = int(timestamp)
316		self.entries = []
317		self.real = 1
318		self.idx = None
319		self.state = 0
320		self.item = None
321		self.dispcnt = 0
322		self.linked = None
323		if (last):
324			source.lastevent(self)
325		else:
326			source.event(self)
327
328	def status(self):
329		statstr = self.name + " " + self.source.name
330		statstr += " on: cpu" + str(self.cpu)
331		statstr += " at: " + str(self.timestamp)
332		statstr += self.stattxt()
333		status.set(statstr)
334
335	def stattxt(self):
336		return ""
337
338	def textadd(self, tuple):
339		pass
340		self.entries.append(tuple)
341
342	def labels(self):
343		return [("Source:", self.source.name, 0),
344				("Event:", self.name, 0),
345				("CPU:", self.cpu, 0),
346				("Timestamp:", self.timestamp, 0)] + self.entries
347	def mouseenter(self, canvas, item):
348		self.displayref(canvas)
349		self.status()
350
351	def mouseexit(self, canvas, item):
352		self.displayunref(canvas)
353		status.clear()
354
355	def mousepress(self, canvas, item):
356		EventView(self, canvas)
357
358	def next(self):
359		return self.source.eventat(self.idx + 1)
360
361	def prev(self):
362		return self.source.eventat(self.idx - 1)
363
364	def displayref(self, canvas):
365		if (self.dispcnt == 0):
366			canvas.itemconfigure(self.item, width=2)
367		self.dispcnt += 1
368
369	def displayunref(self, canvas):
370		self.dispcnt -= 1
371		if (self.dispcnt == 0):
372			canvas.itemconfigure(self.item, width=0)
373			canvas.tag_raise("point", "state")
374
375	def getlinked(self):
376		return self.linked.findevent(self.timestamp)
377
378class PointEvent(Event):
379	def __init__(self, thread, cpu, timestamp, last=0):
380		Event.__init__(self, thread, cpu, timestamp, last)
381
382	def draw(self, canvas, xpos, ypos):
383		l = canvas.create_oval(xpos - 6, ypos + 1, xpos + 6, ypos - 11,
384		    fill=self.color, tags=("all", "point", "event")
385		    + (self.name,), width=0)
386		canvas.events[l] = self
387		self.item = l
388		if (self.enabled == 0):
389			canvas.itemconfigure(l, state="hidden")
390
391		return (xpos)
392
393class StateEvent(Event):
394	def __init__(self, thread, cpu, timestamp, last=0):
395		Event.__init__(self, thread, cpu, timestamp, last)
396		self.duration = 0
397		self.skipnext = 0
398		self.skipself = 0
399		self.state = 1
400
401	def draw(self, canvas, xpos, ypos):
402		next = self.nextstate()
403		if (self.skipself == 1 or next == None):
404			return (xpos)
405		while (self.skipnext):
406			skipped = next
407			next.skipself = 1
408			next.real = 0
409			next = next.nextstate()
410			if (next == None):
411				next = skipped
412			self.skipnext -= 1
413		self.duration = next.timestamp - self.timestamp
414		if (self.duration < 0):
415			self.duration = 0
416			print "Unsynchronized timestamp"
417			print self.cpu, self.timestamp
418			print next.cpu, next.timestamp
419		delta = self.duration / canvas.ratio
420		l = canvas.create_rectangle(xpos, ypos,
421		    xpos + delta, ypos - 10, fill=self.color, width=0,
422		    tags=("all", "state", "event") + (self.name,))
423		canvas.events[l] = self
424		self.item = l
425		if (self.enabled == 0):
426			canvas.itemconfigure(l, state="hidden")
427
428		return (xpos + delta)
429
430	def stattxt(self):
431		return " duration: " + ticks2sec(self.duration)
432
433	def nextstate(self):
434		next = self.next()
435		while (next != None and next.state == 0):
436			next = next.next()
437		return (next)
438
439	def labels(self):
440		return [("Source:", self.source.name, 0),
441				("Event:", self.name, 0),
442				("Timestamp:", self.timestamp, 0),
443				("CPU:", self.cpu, 0),
444				("Duration:", ticks2sec(self.duration), 0)] \
445				 + self.entries
446
447class Count(Event):
448	name = "Count"
449	color = "red"
450	enabled = 1
451	def __init__(self, source, cpu, timestamp, count):
452		self.count = int(count)
453		Event.__init__(self, source, cpu, timestamp)
454		self.duration = 0
455		self.textadd(("count:", self.count, 0))
456
457	def draw(self, canvas, xpos, ypos):
458		next = self.next()
459		self.duration = next.timestamp - self.timestamp
460		delta = self.duration / canvas.ratio
461		yhight = self.source.yscale() * self.count
462		l = canvas.create_rectangle(xpos, ypos - yhight,
463		    xpos + delta, ypos, fill=self.color, width=0,
464		    tags=("all", "count", "event") + (self.name,))
465		canvas.events[l] = self
466		self.item = l
467		if (self.enabled == 0):
468			canvas.itemconfigure(l, state="hidden")
469		return (xpos + delta)
470
471	def stattxt(self):
472		return " count: " + str(self.count)
473
474configtypes.append(Count)
475
476class Running(StateEvent):
477	name = "running"
478	color = "green"
479	enabled = 1
480	def __init__(self, thread, cpu, timestamp, prio):
481		StateEvent.__init__(self, thread, cpu, timestamp)
482		self.prio = prio
483		self.textadd(("prio:", self.prio, 0))
484
485configtypes.append(Running)
486
487class Idle(StateEvent):
488	name = "idle"
489	color = "grey"
490	enabled = 0
491	def __init__(self, thread, cpu, timestamp, prio):
492		StateEvent.__init__(self, thread, cpu, timestamp)
493		self.prio = prio
494		self.textadd(("prio:", self.prio, 0))
495
496configtypes.append(Idle)
497
498class Yielding(StateEvent):
499	name = "yielding"
500	color = "yellow"
501	enabled = 1
502	def __init__(self, thread, cpu, timestamp, prio):
503		StateEvent.__init__(self, thread, cpu, timestamp)
504		self.skipnext = 1
505		self.prio = prio
506		self.textadd(("prio:", self.prio, 0))
507
508configtypes.append(Yielding)
509
510class Swapped(StateEvent):
511	name = "swapped"
512	color = "violet"
513	enabled = 1
514	def __init__(self, thread, cpu, timestamp, prio):
515		StateEvent.__init__(self, thread, cpu, timestamp)
516		self.prio = prio
517		self.textadd(("prio:", self.prio, 0))
518
519configtypes.append(Swapped)
520
521class Suspended(StateEvent):
522	name = "suspended"
523	color = "purple"
524	enabled = 1
525	def __init__(self, thread, cpu, timestamp, prio):
526		StateEvent.__init__(self, thread, cpu, timestamp)
527		self.prio = prio
528		self.textadd(("prio:", self.prio, 0))
529
530configtypes.append(Suspended)
531
532class Iwait(StateEvent):
533	name = "iwait"
534	color = "grey"
535	enabled = 0
536	def __init__(self, thread, cpu, timestamp, prio):
537		StateEvent.__init__(self, thread, cpu, timestamp)
538		self.prio = prio
539		self.textadd(("prio:", self.prio, 0))
540
541configtypes.append(Iwait)
542
543class Preempted(StateEvent):
544	name = "preempted"
545	color = "red"
546	enabled = 1
547	def __init__(self, thread, cpu, timestamp, prio, bythread):
548		StateEvent.__init__(self, thread, cpu, timestamp)
549		self.skipnext = 1
550		self.prio = prio
551		self.linked = bythread
552		self.textadd(("prio:", self.prio, 0))
553		self.textadd(("by thread:", self.linked.name, 1))
554
555configtypes.append(Preempted)
556
557class Sleep(StateEvent):
558	name = "sleep"
559	color = "blue"
560	enabled = 1
561	def __init__(self, thread, cpu, timestamp, prio, wmesg):
562		StateEvent.__init__(self, thread, cpu, timestamp)
563		self.prio = prio
564		self.wmesg = wmesg
565		self.textadd(("prio:", self.prio, 0))
566		self.textadd(("wmesg:", self.wmesg, 0))
567
568	def stattxt(self):
569		statstr = StateEvent.stattxt(self)
570		statstr += " sleeping on: " + self.wmesg
571		return (statstr)
572
573configtypes.append(Sleep)
574
575class Blocked(StateEvent):
576	name = "blocked"
577	color = "dark red"
578	enabled = 1
579	def __init__(self, thread, cpu, timestamp, prio, lock):
580		StateEvent.__init__(self, thread, cpu, timestamp)
581		self.prio = prio
582		self.lock = lock
583		self.textadd(("prio:", self.prio, 0))
584		self.textadd(("lock:", self.lock, 0))
585
586	def stattxt(self):
587		statstr = StateEvent.stattxt(self)
588		statstr += " blocked on: " + self.lock
589		return (statstr)
590
591configtypes.append(Blocked)
592
593class KsegrpRunq(StateEvent):
594	name = "KsegrpRunq"
595	color = "orange"
596	enabled = 1
597	def __init__(self, thread, cpu, timestamp, prio, bythread):
598		StateEvent.__init__(self, thread, cpu, timestamp)
599		self.prio = prio
600		self.linked = bythread
601		self.textadd(("prio:", self.prio, 0))
602		self.textadd(("by thread:", self.linked.name, 1))
603
604configtypes.append(KsegrpRunq)
605
606class Runq(StateEvent):
607	name = "Runq"
608	color = "yellow"
609	enabled = 1
610	def __init__(self, thread, cpu, timestamp, prio, bythread):
611		StateEvent.__init__(self, thread, cpu, timestamp)
612		self.prio = prio
613		self.linked = bythread
614		self.textadd(("prio:", self.prio, 0))
615		self.textadd(("by thread:", self.linked.name, 1))
616
617configtypes.append(Runq)
618
619class Sched_exit(StateEvent):
620	name = "exit"
621	color = "grey"
622	enabled = 0
623	def __init__(self, thread, cpu, timestamp, prio):
624		StateEvent.__init__(self, thread, cpu, timestamp)
625		self.name = "sched_exit"
626		self.prio = prio
627		self.textadd(("prio:", self.prio, 0))
628
629configtypes.append(Sched_exit)
630
631class Padevent(StateEvent):
632	def __init__(self, thread, cpu, timestamp, last=0):
633		StateEvent.__init__(self, thread, cpu, timestamp, last)
634		self.name = "pad"
635		self.real = 0
636
637	def draw(self, canvas, xpos, ypos):
638		next = self.next()
639		if (next == None):
640			return (xpos)
641		self.duration = next.timestamp - self.timestamp
642		delta = self.duration / canvas.ratio
643		return (xpos + delta)
644
645class Tick(PointEvent):
646	name = "tick"
647	color = "black"
648	enabled = 0
649	def __init__(self, thread, cpu, timestamp, prio, stathz):
650		PointEvent.__init__(self, thread, cpu, timestamp)
651		self.prio = prio
652		self.textadd(("prio:", self.prio, 0))
653
654configtypes.append(Tick)
655
656class Prio(PointEvent):
657	name = "prio"
658	color = "black"
659	enabled = 0
660	def __init__(self, thread, cpu, timestamp, prio, newprio, bythread):
661		PointEvent.__init__(self, thread, cpu, timestamp)
662		self.prio = prio
663		self.newprio = newprio
664		self.linked = bythread
665		self.textadd(("new prio:", self.newprio, 0))
666		self.textadd(("prio:", self.prio, 0))
667		if (self.linked != self.source):
668			self.textadd(("by thread:", self.linked.name, 1))
669		else:
670			self.textadd(("by thread:", self.linked.name, 0))
671
672configtypes.append(Prio)
673
674class Lend(PointEvent):
675	name = "lend"
676	color = "black"
677	enabled = 0
678	def __init__(self, thread, cpu, timestamp, prio, tothread):
679		PointEvent.__init__(self, thread, cpu, timestamp)
680		self.prio = prio
681		self.linked = tothread
682		self.textadd(("prio:", self.prio, 0))
683		self.textadd(("to thread:", self.linked.name, 1))
684
685configtypes.append(Lend)
686
687class Wokeup(PointEvent):
688	name = "wokeup"
689	color = "black"
690	enabled = 0
691	def __init__(self, thread, cpu, timestamp, ranthread):
692		PointEvent.__init__(self, thread, cpu, timestamp)
693		self.linked = ranthread
694		self.textadd(("ran thread:", self.linked.name, 1))
695
696configtypes.append(Wokeup)
697
698class EventSource:
699	def __init__(self, name):
700		self.name = name
701		self.events = []
702		self.cpu = 0
703		self.cpux = 0
704
705	def fixup(self):
706		pass
707
708	def event(self, event):
709		self.events.insert(0, event)
710
711	def remove(self, event):
712		self.events.remove(event)
713
714	def lastevent(self, event):
715		self.events.append(event)
716
717	def draw(self, canvas, ypos):
718		xpos = 10
719		self.cpux = 10
720		self.cpu = self.events[1].cpu
721		for i in range(0, len(self.events)):
722			self.events[i].idx = i
723		for event in self.events:
724			if (event.cpu != self.cpu and event.cpu != -1):
725				self.drawcpu(canvas, xpos, ypos)
726				self.cpux = xpos
727				self.cpu = event.cpu
728			xpos = event.draw(canvas, xpos, ypos)
729		self.drawcpu(canvas, xpos, ypos)
730
731	def drawname(self, canvas, ypos):
732		ypos = ypos - (self.ysize() / 2)
733		canvas.create_text(10, ypos, anchor="w", text=self.name)
734
735	def drawcpu(self, canvas, xpos, ypos):
736		cpu = int(self.cpu)
737		if (cpu == 0):
738			color = 'light grey'
739		elif (cpu == 1):
740			color = 'dark grey'
741		elif (cpu == 2):
742			color = 'light blue'
743		elif (cpu == 3):
744			color = 'light green'
745		elif (cpu == 4):
746			color = 'blanched almond'
747		elif (cpu == 5):
748			color = 'slate grey'
749		elif (cpu == 6):
750			color = 'light slate blue'
751		elif (cpu == 7):
752			color = 'thistle'
753		else:
754			color = "white"
755		l = canvas.create_rectangle(self.cpux,
756		    ypos - self.ysize() - canvas.bdheight,
757		    xpos, ypos + canvas.bdheight, fill=color, width=0,
758		    tags=("all", "cpuinfo"))
759
760	def ysize(self):
761		return (None)
762
763	def eventat(self, i):
764		if (i >= len(self.events)):
765			return (None)
766		event = self.events[i]
767		return (event)
768
769	def findevent(self, timestamp):
770		for event in self.events:
771			if (event.timestamp >= timestamp and event.real):
772				return (event)
773		return (None)
774
775class Thread(EventSource):
776	names = {}
777	def __init__(self, td, pcomm):
778		EventSource.__init__(self, pcomm)
779		self.str = td
780		try:
781			cnt = Thread.names[pcomm]
782		except:
783			Thread.names[pcomm] = 0
784			return
785		Thread.names[pcomm] = cnt + 1
786
787	def fixup(self):
788		cnt = Thread.names[self.name]
789		if (cnt == 0):
790			return
791		cnt -= 1
792		Thread.names[self.name] = cnt
793		self.name += " td" + str(cnt)
794
795	def ysize(self):
796		return (10)
797
798class Counter(EventSource):
799	max = 0
800	def __init__(self, name):
801		EventSource.__init__(self, name)
802
803	def event(self, event):
804		EventSource.event(self, event)
805		try:
806			count = event.count
807		except:
808			return
809		count = int(count)
810		if (count > Counter.max):
811			Counter.max = count
812
813	def ysize(self):
814		return (80)
815
816	def yscale(self):
817		return (self.ysize() / Counter.max)
818
819
820class KTRFile:
821	def __init__(self, file):
822		self.timestamp_first = {}
823		self.timestamp_last = {}
824		self.timestamp_adjust = {}
825		self.timestamp_f = None
826		self.timestamp_l = None
827		self.lineno = -1
828		self.threads = []
829		self.sources = []
830		self.ticks = {}
831		self.load = {}
832		self.crit = {}
833		self.stathz = 0
834
835		self.parse(file)
836		self.fixup()
837		global ticksps
838		print "first", self.timestamp_f, "last", self.timestamp_l
839		print "time span", self.timespan()
840		print "stathz", self.stathz
841		ticksps = self.ticksps()
842		print "Ticks per second", ticksps
843
844	def parse(self, file):
845		try:
846			ifp = open(file)
847		except:
848			print "Can't open", file
849			sys.exit(1)
850
851		ktrhdr = "\s+\d+\s+(\d+)\s+(\d+)\s+"
852		tdname = "(\S+)\(([^)]*)\)"
853		crittdname = "(\S+)\s+\(\d+,\s+([^)]*)\)"
854
855		ktrstr = "mi_switch: " + tdname
856		ktrstr += " prio (\d+) inhibit (\d+) wmesg (\S+) lock (\S+)"
857		switchout_re = re.compile(ktrhdr + ktrstr)
858
859		ktrstr = "mi_switch: " + tdname + " prio (\d+) idle"
860		idled_re = re.compile(ktrhdr + ktrstr)
861
862		ktrstr = "mi_switch: " + tdname + " prio (\d+) preempted by "
863		ktrstr += tdname
864		preempted_re = re.compile(ktrhdr + ktrstr)
865
866		ktrstr = "mi_switch: running " + tdname + " prio (\d+)"
867		switchin_re = re.compile(ktrhdr + ktrstr)
868
869		ktrstr = "sched_add: " + tdname + " prio (\d+) by " + tdname
870		sched_add_re = re.compile(ktrhdr + ktrstr)
871
872		ktrstr = "setrunqueue: " + tdname + " prio (\d+) by " + tdname
873		setrunqueue_re = re.compile(ktrhdr + ktrstr)
874
875		ktrstr = "sched_rem: " + tdname + " prio (\d+) by " + tdname
876		sched_rem_re = re.compile(ktrhdr + ktrstr)
877
878		ktrstr = "sched_exit_thread: " + tdname + " prio (\d+)"
879		sched_exit_re = re.compile(ktrhdr + ktrstr)
880
881		ktrstr = "statclock: " + tdname + " prio (\d+)"
882		ktrstr += " stathz (\d+)"
883		sched_clock_re = re.compile(ktrhdr + ktrstr)
884
885		ktrstr = "sched_prio: " + tdname + " prio (\d+)"
886		ktrstr += " newprio (\d+) by " + tdname
887		sched_prio_re = re.compile(ktrhdr + ktrstr)
888
889		cpuload_re = re.compile(ktrhdr + "load: (\d+)")
890		loadglobal_re = re.compile(ktrhdr + "global load: (\d+)")
891
892		ktrstr = "critical_\S+ by thread " + crittdname + " to (\d+)"
893		critsec_re = re.compile(ktrhdr + ktrstr)
894
895		parsers = [[cpuload_re, self.cpuload],
896			   [loadglobal_re, self.loadglobal],
897			   [switchin_re, self.switchin],
898			   [switchout_re, self.switchout],
899			   [sched_add_re, self.sched_add],
900			   [setrunqueue_re, self.sched_rem],
901			   [sched_prio_re, self.sched_prio],
902			   [preempted_re, self.preempted],
903			   [sched_rem_re, self.sched_rem],
904			   [sched_exit_re, self.sched_exit],
905			   [sched_clock_re, self.sched_clock],
906			   [critsec_re, self.critsec],
907			   [idled_re, self.idled]]
908
909		lines = ifp.readlines()
910		self.synchstamp(lines)
911		for line in lines:
912			self.lineno += 1
913			if ((self.lineno % 1024) == 0):
914				status.startup("Parsing line " +
915				    str(self.lineno))
916			for p in parsers:
917				m = p[0].match(line)
918				if (m != None):
919					p[1](*m.groups())
920					break
921			# if (m == None):
922			# 	print line,
923
924	def synchstamp(self, lines):
925		status.startup("Rationalizing Timestamps")
926		tstamp_re = re.compile("\s+\d+\s+(\d+)\s+(\d+)\s+.*")
927		for line in lines:
928			m = tstamp_re.match(line)
929			if (m != None):
930				self.addstamp(*m.groups())
931		self.pickstamp()
932		self.monostamp(lines)
933
934
935	def monostamp(self, lines):
936		laststamp = None
937		tstamp_re = re.compile("\s+\d+\s+(\d+)\s+(\d+)\s+.*")
938		for line in lines:
939			m = tstamp_re.match(line)
940			if (m == None):
941				continue
942			(cpu, timestamp) = m.groups()
943			timestamp = int(timestamp)
944			cpu = int(cpu)
945			timestamp -= self.timestamp_adjust[cpu]
946			if (laststamp != None and timestamp > laststamp):
947				self.timestamp_adjust[cpu] += timestamp - laststamp
948			laststamp = timestamp
949
950	def addstamp(self, cpu, timestamp):
951		timestamp = int(timestamp)
952		cpu = int(cpu)
953		try:
954			if (timestamp > self.timestamp_first[cpu]):
955				return
956		except:
957			self.timestamp_first[cpu] = timestamp
958		self.timestamp_last[cpu] = timestamp
959
960	def pickstamp(self):
961		base = self.timestamp_last[0]
962		for i in range(0, len(self.timestamp_last)):
963			if (self.timestamp_last[i] < base):
964				base = self.timestamp_last[i]
965
966		print "Adjusting to base stamp", base
967		for i in range(0, len(self.timestamp_last)):
968			self.timestamp_adjust[i] = self.timestamp_last[i] - base;
969			print "CPU ", i, "adjust by ", self.timestamp_adjust[i]
970
971		self.timestamp_f = 0
972		for i in range(0, len(self.timestamp_first)):
973			first = self.timestamp_first[i] - self.timestamp_adjust[i]
974			if (first > self.timestamp_f):
975				self.timestamp_f = first
976
977		self.timestamp_l = 0
978		for i in range(0, len(self.timestamp_last)):
979			last = self.timestamp_last[i] - self.timestamp_adjust[i]
980			if (last > self.timestamp_l):
981				self.timestamp_l = last
982
983
984	def checkstamp(self, cpu, timestamp):
985		cpu = int(cpu)
986		timestamp = int(timestamp)
987		if (timestamp > self.timestamp_first[cpu]):
988			print "Bad timestamp on line ", self.lineno
989			return (0)
990		timestamp -= self.timestamp_adjust[cpu]
991		return (timestamp)
992
993	def timespan(self):
994		return (self.timestamp_f - self.timestamp_l);
995
996	def ticksps(self):
997		return (self.timespan() / self.ticks[0]) * int(self.stathz)
998
999	def switchout(self, cpu, timestamp, td, pcomm, prio, inhibit, wmesg, lock):
1000		TDI_SUSPENDED = 0x0001
1001		TDI_SLEEPING = 0x0002
1002		TDI_SWAPPED = 0x0004
1003		TDI_LOCK = 0x0008
1004		TDI_IWAIT = 0x0010
1005
1006		timestamp = self.checkstamp(cpu, timestamp)
1007		if (timestamp == 0):
1008			return
1009		inhibit = int(inhibit)
1010		thread = self.findtd(td, pcomm)
1011		if (inhibit & TDI_SWAPPED):
1012			Swapped(thread, cpu, timestamp, prio)
1013		elif (inhibit & TDI_SLEEPING):
1014			Sleep(thread, cpu, timestamp, prio, wmesg)
1015		elif (inhibit & TDI_LOCK):
1016			Blocked(thread, cpu, timestamp, prio, lock)
1017		elif (inhibit & TDI_IWAIT):
1018			Iwait(thread, cpu, timestamp, prio)
1019		elif (inhibit & TDI_SUSPENDED):
1020			Suspended(thread, cpu, timestamp, prio)
1021		elif (inhibit == 0):
1022			Yielding(thread, cpu, timestamp, prio)
1023		else:
1024			print "Unknown event", inhibit
1025			sys.exit(1)
1026
1027	def idled(self, cpu, timestamp, td, pcomm, prio):
1028		timestamp = self.checkstamp(cpu, timestamp)
1029		if (timestamp == 0):
1030			return
1031		thread = self.findtd(td, pcomm)
1032		Idle(thread, cpu, timestamp, prio)
1033
1034	def preempted(self, cpu, timestamp, td, pcomm, prio, bytd, bypcomm):
1035		timestamp = self.checkstamp(cpu, timestamp)
1036		if (timestamp == 0):
1037			return
1038		thread = self.findtd(td, pcomm)
1039		Preempted(thread, cpu, timestamp, prio,
1040		    self.findtd(bytd, bypcomm))
1041
1042	def switchin(self, cpu, timestamp, td, pcomm, prio):
1043		timestamp = self.checkstamp(cpu, timestamp)
1044		if (timestamp == 0):
1045			return
1046		thread = self.findtd(td, pcomm)
1047		Running(thread, cpu, timestamp, prio)
1048
1049	def sched_add(self, cpu, timestamp, td, pcomm, prio, bytd, bypcomm):
1050		timestamp = self.checkstamp(cpu, timestamp)
1051		if (timestamp == 0):
1052			return
1053		thread = self.findtd(td, pcomm)
1054		bythread = self.findtd(bytd, bypcomm)
1055		Runq(thread, cpu, timestamp, prio, bythread)
1056		Wokeup(bythread, cpu, timestamp, thread)
1057
1058	def sched_rem(self, cpu, timestamp, td, pcomm, prio, bytd, bypcomm):
1059		timestamp = self.checkstamp(cpu, timestamp)
1060		if (timestamp == 0):
1061			return
1062		thread = self.findtd(td, pcomm)
1063		KsegrpRunq(thread, cpu, timestamp, prio,
1064		    self.findtd(bytd, bypcomm))
1065
1066	def sched_exit(self, cpu, timestamp, td, pcomm, prio):
1067		timestamp = self.checkstamp(cpu, timestamp)
1068		if (timestamp == 0):
1069			return
1070		thread = self.findtd(td, pcomm)
1071		Sched_exit(thread, cpu, timestamp, prio)
1072
1073	def sched_clock(self, cpu, timestamp, td, pcomm, prio, stathz):
1074		timestamp = self.checkstamp(cpu, timestamp)
1075		if (timestamp == 0):
1076			return
1077		self.stathz = stathz
1078		cpu = int(cpu)
1079		try:
1080			ticks = self.ticks[cpu]
1081		except:
1082			self.ticks[cpu] = 0
1083		self.ticks[cpu] += 1
1084		thread = self.findtd(td, pcomm)
1085		Tick(thread, cpu, timestamp, prio, stathz)
1086
1087	def sched_prio(self, cpu, timestamp, td, pcomm, prio, newprio, bytd, bypcomm):
1088		if (prio == newprio):
1089			return
1090		timestamp = self.checkstamp(cpu, timestamp)
1091		if (timestamp == 0):
1092			return
1093		thread = self.findtd(td, pcomm)
1094		bythread = self.findtd(bytd, bypcomm)
1095		Prio(thread, cpu, timestamp, prio, newprio, bythread)
1096		Lend(bythread, cpu, timestamp, newprio, thread)
1097
1098	def cpuload(self, cpu, timestamp, count):
1099		timestamp = self.checkstamp(cpu, timestamp)
1100		if (timestamp == 0):
1101			return
1102		cpu = int(cpu)
1103		try:
1104			load = self.load[cpu]
1105		except:
1106			load = Counter("cpu" + str(cpu) + " load")
1107			self.load[cpu] = load
1108			self.sources.insert(0, load)
1109		Count(load, cpu, timestamp, count)
1110
1111	def loadglobal(self, cpu, timestamp, count):
1112		timestamp = self.checkstamp(cpu, timestamp)
1113		if (timestamp == 0):
1114			return
1115		cpu = 0
1116		try:
1117			load = self.load[cpu]
1118		except:
1119			load = Counter("CPU load")
1120			self.load[cpu] = load
1121			self.sources.insert(0, load)
1122		Count(load, cpu, timestamp, count)
1123
1124	def critsec(self, cpu, timestamp, td, pcomm, to):
1125		timestamp = self.checkstamp(cpu, timestamp)
1126		if (timestamp == 0):
1127			return
1128		cpu = int(cpu)
1129		try:
1130			crit = self.crit[cpu]
1131		except:
1132			crit = Counter("Critical Section")
1133			self.crit[cpu] = crit
1134			self.sources.insert(0, crit)
1135		Count(crit, cpu, timestamp, to)
1136
1137	def findtd(self, td, pcomm):
1138		for thread in self.threads:
1139			if (thread.str == td and thread.name == pcomm):
1140				return thread
1141		thread = Thread(td, pcomm)
1142		self.threads.append(thread)
1143		self.sources.append(thread)
1144		return (thread)
1145
1146	def fixup(self):
1147		for source in self.sources:
1148			Padevent(source, -1, self.timestamp_l)
1149			Padevent(source, -1, self.timestamp_f, last=1)
1150			source.fixup()
1151
1152class SchedDisplay(Canvas):
1153	def __init__(self, master):
1154		self.ratio = 1
1155		self.ktrfile = None
1156		self.sources = None
1157		self.bdheight = 10
1158		self.events = {}
1159
1160		Canvas.__init__(self, master, width=800, height=500, bg='grey',
1161		     scrollregion=(0, 0, 800, 500))
1162
1163	def setfile(self, ktrfile):
1164		self.ktrfile = ktrfile
1165		self.sources = ktrfile.sources
1166
1167	def draw(self):
1168		ypos = 0
1169		xsize = self.xsize()
1170		for source in self.sources:
1171			status.startup("Drawing " + source.name)
1172			self.create_line(0, ypos, xsize, ypos,
1173			    width=1, fill="black", tags=("all",))
1174			ypos += self.bdheight
1175			ypos += source.ysize()
1176			source.draw(self, ypos)
1177			ypos += self.bdheight
1178			try:
1179				self.tag_raise("point", "state")
1180				self.tag_lower("cpuinfo", "all")
1181			except:
1182				pass
1183		self.create_line(0, ypos, xsize, ypos,
1184		    width=1, fill="black", tags=("all",))
1185		self.tag_bind("event", "<Enter>", self.mouseenter)
1186		self.tag_bind("event", "<Leave>", self.mouseexit)
1187		self.tag_bind("event", "<Button-1>", self.mousepress)
1188
1189	def mouseenter(self, event):
1190		item, = self.find_withtag(CURRENT)
1191		event = self.events[item]
1192		event.mouseenter(self, item)
1193
1194	def mouseexit(self, event):
1195		item, = self.find_withtag(CURRENT)
1196		event = self.events[item]
1197		event.mouseexit(self, item)
1198
1199	def mousepress(self, event):
1200		item, = self.find_withtag(CURRENT)
1201		event = self.events[item]
1202		event.mousepress(self, item)
1203
1204	def drawnames(self, canvas):
1205		status.startup("Drawing names")
1206		ypos = 0
1207		canvas.configure(scrollregion=(0, 0,
1208		    canvas["width"], self.ysize()))
1209		for source in self.sources:
1210			canvas.create_line(0, ypos, canvas["width"], ypos,
1211			    width=1, fill="black", tags=("all",))
1212			ypos += self.bdheight
1213			ypos += source.ysize()
1214			source.drawname(canvas, ypos)
1215			ypos += self.bdheight
1216		canvas.create_line(0, ypos, canvas["width"], ypos,
1217		    width=1, fill="black", tags=("all",))
1218
1219	def xsize(self):
1220		return ((self.ktrfile.timespan() / self.ratio) + 20)
1221
1222	def ysize(self):
1223		ysize = 0
1224		for source in self.sources:
1225			ysize += source.ysize() + (self.bdheight * 2)
1226		return (ysize)
1227
1228	def scaleset(self, ratio):
1229		if (self.ktrfile == None):
1230			return
1231		oldratio = self.ratio
1232		xstart, ystart = self.xview()
1233		length = (float(self["width"]) / self.xsize())
1234		middle = xstart + (length / 2)
1235
1236		self.ratio = ratio
1237		self.configure(scrollregion=(0, 0, self.xsize(), self.ysize()))
1238		self.scale("all", 0, 0, float(oldratio) / ratio, 1)
1239
1240		length = (float(self["width"]) / self.xsize())
1241		xstart = middle - (length / 2)
1242		self.xview_moveto(xstart)
1243
1244	def scaleget(self):
1245		return self.ratio
1246
1247	def setcolor(self, tag, color):
1248		self.itemconfigure(tag, state="normal", fill=color)
1249
1250	def hide(self, tag):
1251		self.itemconfigure(tag, state="hidden")
1252
1253class GraphMenu(Frame):
1254	def __init__(self, master):
1255		Frame.__init__(self, master, bd=2, relief=RAISED)
1256		self.view = Menubutton(self, text="Configure")
1257		self.viewmenu = Menu(self.view, tearoff=0)
1258		self.viewmenu.add_command(label="Events",
1259		    command=self.econf)
1260		self.view["menu"] = self.viewmenu
1261		self.view.pack(side=LEFT)
1262
1263	def econf(self):
1264		EventConfigure()
1265
1266
1267class SchedGraph(Frame):
1268	def __init__(self, master):
1269		Frame.__init__(self, master)
1270		self.menu = None
1271		self.names = None
1272		self.display = None
1273		self.scale = None
1274		self.status = None
1275		self.pack(expand=1, fill="both")
1276		self.buildwidgets()
1277		self.layout()
1278		self.draw(sys.argv[1])
1279
1280	def buildwidgets(self):
1281		global status
1282		self.menu = GraphMenu(self)
1283		self.display = SchedDisplay(self)
1284		self.names = Canvas(self,
1285		    width=100, height=self.display["height"],
1286		    bg='grey', scrollregion=(0, 0, 50, 100))
1287		self.scale = Scaler(self, self.display)
1288		status = self.status = Status(self)
1289		self.scrollY = Scrollbar(self, orient="vertical",
1290		    command=self.display_yview)
1291		self.display.scrollX = Scrollbar(self, orient="horizontal",
1292		    command=self.display.xview)
1293		self.display["xscrollcommand"] = self.display.scrollX.set
1294		self.display["yscrollcommand"] = self.scrollY.set
1295		self.names["yscrollcommand"] = self.scrollY.set
1296
1297	def layout(self):
1298		self.columnconfigure(1, weight=1)
1299		self.rowconfigure(1, weight=1)
1300		self.menu.grid(row=0, column=0, columnspan=3, sticky=E+W)
1301		self.names.grid(row=1, column=0, sticky=N+S)
1302		self.display.grid(row=1, column=1, sticky=W+E+N+S)
1303		self.scrollY.grid(row=1, column=2, sticky=N+S)
1304		self.display.scrollX.grid(row=2, column=0, columnspan=2,
1305		    sticky=E+W)
1306		self.scale.grid(row=3, column=0, columnspan=3, sticky=E+W)
1307		self.status.grid(row=4, column=0, columnspan=3, sticky=E+W)
1308
1309	def draw(self, file):
1310		self.master.update()
1311		ktrfile = KTRFile(file)
1312		self.display.setfile(ktrfile)
1313		self.display.drawnames(self.names)
1314		self.display.draw()
1315		self.scale.set(250000)
1316		self.display.xview_moveto(0)
1317
1318	def display_yview(self, *args):
1319		self.names.yview(*args)
1320		self.display.yview(*args)
1321
1322	def setcolor(self, tag, color):
1323		self.display.setcolor(tag, color)
1324
1325	def hide(self, tag):
1326		self.display.hide(tag)
1327
1328if (len(sys.argv) != 2):
1329	print "usage:", sys.argv[0], "<ktr file>"
1330	sys.exit(1)
1331
1332root = Tk()
1333root.title("Scheduler Graph")
1334graph = SchedGraph(root)
1335root.mainloop()
1336