2009-02-19 Rodrigo Kumpera <rkumpera@novell.com>

	* LockTracerDecoder.cs: Initial version of the lock tracers decoder.

svn path=/trunk/mono/; revision=127477

2 files changed, 525 insertions, 0 deletions

diff --git a/data/lock-decoder/ChangeLog b/data/lock-decoder/ChangeLog
new file mode 100644
index 00000000000..6316d520531
--- /dev/null
+++ b/data/lock-decoder/ChangeLog
@@ -0,0 +1,6 @@
+2009-02-19 Rodrigo Kumpera  <rkumpera@novell.com>
+
+	* LockTracerDecoder.cs: Initial version of the lock tracers decoder.
+
+	
+
diff --git a/data/lock-decoder/LockTracerDecoder.cs b/data/lock-decoder/LockTracerDecoder.cs
new file mode 100644
index 00000000000..b5a3f755ea5
--- /dev/null
+++ b/data/lock-decoder/LockTracerDecoder.cs
@@ -0,0 +1,519 @@
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.IO;
+using System.Globalization;
+using System.Runtime.InteropServices;
+
+
+public enum Record {
+	MustNotHoldAny,
+	MustNotHoldOne,
+	MustHoldOne,
+	LockAcquired,
+	LockReleased
+}
+
+
+public struct LockRecord {
+	public SimLock lk;
+	public string frame;
+
+	public LockRecord (SimLock lk, string frame) {
+		this.lk = lk;
+		this.frame = frame;
+	}
+}
+
+public class SimThread
+{
+	int thread;
+	List <LockRecord> locks = new List <LockRecord> ();
+
+	public SimThread (int t)
+	{
+		this.thread = t;
+	}
+
+	public bool HoldsLock (SimLock lk) {
+		foreach (var l in locks) {
+			if (l.lk == lk)
+				return true;
+		}
+		return false;
+	}
+
+
+	public int HoldCount (SimLock lk) {
+		int res = 0;
+		foreach (var l in locks)
+			if (l.lk == lk)
+				++res;
+		return res;
+	}
+
+	public void Lock (SimLock lk, string frame) {
+		foreach (LockRecord lr in locks) {
+			if (lk.WarnAbout (this, lr.lk)) 
+				Console.WriteLine ("WARNING: tried to acquire lock {0} at {1} while holding {2} at {3}: {4}", lk, frame, lr.lk, lr.frame, lk.GetWarningMessage (this, lr.lk));
+			else if (!lk.IsValid (this, lr.lk))
+				Console.WriteLine ("ERROR: tried to acquire lock {0} at {1} while holding {2} at {3}: {4}", lk, frame, lr.lk, lr.frame, lk.GetErrorMessage (this, lr.lk));
+		}
+		locks.Add (new LockRecord (lk, frame));
+	}
+
+	public void Release (SimLock lk, string frame) {
+		if (locks.Count == 0) {
+			Console.WriteLine ("ERROR: released lock {0} at {1} while holding no locks!", lk, frame);
+			return;
+		}
+		LockRecord top = locks [locks.Count - 1];
+		if (top.lk != lk && !(lk.IsGlobalLock && HoldCount (lk) > 1)) {
+			Console.WriteLine ("WARNING: released lock {0} at {1} out of order with {2} at {3}!", lk, frame, top.lk, top.frame);
+		}
+		for (int i = locks.Count -1; i >= 0; --i) {
+			if (locks [i].lk == lk) {
+				locks.RemoveAt (i);
+				break;
+			}
+		}
+	}
+}
+
+/*
+LOCK RULES
+
+Simple locks:
+ 	Can be acquired at any point regardless of which locks are taken or not.
+	No other locks can be acquired or released while holding a simple lock.
+	Reentrancy is not recomended. (warning)
+	Simple locks are leaf locks on the lock lattice.
+
+Complex locks:
+	Must respect locking order, which form a lattice.
+	IOW, to take a given lock, only it's parents might have been taken.
+	Reentrancy is ok.
+	Locks around resources count as separate instances of the hierarchy.
+
+Global locks:
+	Must respect locking order.
+	Must be the at the botton of the locking lattice.
+	Can be taken out-of-order by other locks given that it was previously acquired.
+	Adding global locks is not to be taken lightly.
+
+The current lock hierarchy:
+loader lock
+	domain lock
+		domain jit lock
+			simple locks
+
+Examples:
+	You can take the loader lock without holding a domain lock.
+	You cannot take a domain lock if the loader lock is held.
+	You cannot take a domain lock while holding the lock to another domain.
+*/
+
+public enum Lock {
+	Invalid,
+	LoaderLock,
+	ImageDataLock,
+	DomainLock,
+	DomainAssembliesLock,
+	DomainJitCodeHashLock,
+}
+
+public class SimLock
+{
+	Lock kind;
+	int id;
+
+	public SimLock (Lock kind, int id) {
+		this.kind = kind;
+		this.id = id;
+	}
+
+	static int GetLockOrder (Lock kind) {
+		switch (kind) {
+			case Lock.LoaderLock:
+				return 0;
+			case Lock.DomainLock:
+				return 1;
+			case Lock.DomainJitCodeHashLock:
+				return 2;
+			default:
+				return 3;
+		}
+	}
+
+	bool IsParent (SimLock other) {
+		return GetLockOrder (kind) > GetLockOrder (other.kind);
+	}
+
+	public bool IsSimpleLock {
+		get { return GetLockOrder (kind) == 3; }
+	}
+
+	public bool IsGlobalLock {
+		get { return kind == Lock.LoaderLock; }
+	}
+
+	/*locked is already owned by the thread, 'this' is the new one*/
+	bool Compare (SimThread thread, SimLock locked, out bool isWarning, out string msg)
+	{
+		isWarning = false;
+		msg = null;
+
+		if (locked != this) {
+			if (!IsParent (locked)) {
+				if (IsGlobalLock) { /*acquiring a global lock*/
+					if (!thread.HoldsLock (this)) { /*does the thread alread hold it?*/
+						msg = "Acquired a global lock after a regular lock without having it before.";
+						return false;
+					}
+				} else {
+					msg = "Hierarchy violation.";
+					return false;
+				}
+			}
+		} else if (IsSimpleLock) {
+			msg = "Avoid taking simple locks recursively";
+			isWarning = true;
+			return false;
+		}
+
+		return true;
+	}
+
+	public bool IsValid (SimThread thread, SimLock locked) {
+		bool warn;
+		string msg;
+		return Compare (thread, locked, out warn, out msg);
+	}
+
+	public bool WarnAbout (SimThread thread, SimLock locked) {
+		bool warn;
+		string msg;
+		Compare (thread, locked, out warn, out msg);
+		return warn;
+	}
+
+	public string GetWarningMessage (SimThread thread, SimLock locked) {
+		bool warn;
+		string msg;
+		Compare (thread, locked, out warn, out msg);
+		return warn ? msg : null;
+	}
+
+	public string GetErrorMessage (SimThread thread, SimLock locked) {
+		bool warn;
+		string msg;
+		bool res = Compare (thread, locked, out warn, out msg);
+		return !res && !warn ? msg : null;
+	}
+
+	public override string ToString () {
+		return String.Format ("{0}", kind);
+	}
+}
+
+public class LockSimulator
+{
+	static Dictionary <int, SimThread> threads = new Dictionary <int, SimThread> ();
+	static Dictionary <int, SimLock> locks = new Dictionary <int, SimLock> ();
+
+	SymbolTable syms;
+
+	public LockSimulator (SymbolTable s) { this.syms = s; }
+
+	SimLock GetLock (Trace t)  {
+		if (locks.ContainsKey (t.lockPtr))
+			return locks [t.lockPtr];
+		else {
+			return locks [t.lockPtr] = new SimLock (t.lockKind, t.lockPtr);
+		}
+	}
+
+	SimThread GetThread (Trace t) {
+		if (threads.ContainsKey (t.thread))
+			return threads [t.thread];
+		else
+			return threads [t.thread] = new SimThread (t.thread);		
+	}
+
+	public void PlayBack (IEnumerable<Trace> traces) {
+		foreach (var t in traces) {
+			SimThread thread = GetThread (t);
+			SimLock lk = GetLock (t);
+			string frame = t.GetUsefullTopTrace (this.syms);
+
+			switch (t.record) {
+			case Record.MustNotHoldAny:
+			case Record.MustNotHoldOne:
+			case Record.MustHoldOne:
+				throw new Exception ("not supported");
+			case Record.LockAcquired:
+				thread.Lock (lk, frame);
+				break;
+			case Record.LockReleased:
+				thread.Release (lk, frame);
+				break;
+			default:
+				throw new Exception ("Invalid trace record: "+t.record);
+			}
+		}
+	}
+}
+
+public class Trace {
+	public int thread;
+	public Record record;
+	public Lock lockKind;
+	public int lockPtr;
+	int[] frames;
+
+	static readonly string[] BAD_FRAME_METHODS = new string[] {
+		"mono_loader_lock",
+		"mono_loader_unlock",
+		"mono_image_lock",
+		"mono_image_unlock",
+	};
+
+	public Trace (string[] fields) {
+		thread = fields [0].ParseHex ();
+		record = (Record)fields [1].ParseDec ();
+		lockKind = (Lock)fields [2].ParseDec ();
+		lockPtr = fields [3].ParseHex ();
+		frames = new int [fields.Length - 4];
+		for (int i = 0; i < frames.Length; ++i)
+			frames [i] = fields [i + 4].ParseHex ();
+	}
+
+	public void Dump (SymbolTable table) {
+		Console.WriteLine ("{0:x} {1} {2} {3:x}", thread, record, lockKind, lockPtr);
+		for (int i = 0; i < frames.Length; ++i)
+			Console.WriteLine ("\t{0}", table.Translate (frames [i]));
+	}
+
+	public string GetUsefullTopTrace (SymbolTable syms) {
+		for (int i = 0; i < frames.Length; ++i) {
+			string str = syms.Translate (frames [i]);
+			bool ok = true;
+			for (int j = 0; j < BAD_FRAME_METHODS.Length; ++j) {
+				if (str.IndexOf (BAD_FRAME_METHODS [j]) >= 0) {
+					ok = false;
+					break;
+				}
+			}
+			if (ok)
+				return str;
+		}
+		return "[unknown]";
+	}
+}
+
+public class Symbol : IComparable<Symbol>
+{
+	public int offset;
+	public int size;
+	public string name;
+
+	public Symbol (int o, int size, string n) {
+		this.offset = o;
+		this.size = size;
+		this.name = n;
+	}
+
+	public int CompareTo(Symbol other) {
+		return offset - other.offset;
+	}
+}
+
+public interface SymbolTable {
+	string Translate (int offset);
+}
+
+public class OsxSymbolTable : SymbolTable
+{
+	Symbol[] table;
+
+	const int MAX_FUNC_SIZE = 0x20000;
+
+	public OsxSymbolTable (string binary) {
+		Load (binary);
+	}
+
+	void Load (string binary) {
+		ProcessStartInfo psi = new ProcessStartInfo ("gobjdump", "-t "+binary);
+		psi.UseShellExecute = false;
+		psi.RedirectStandardOutput = true;
+
+		var proc = Process.Start (psi);
+		var list = new List<Symbol> ();
+		string line;
+		while ((line = proc.StandardOutput.ReadLine ()) != null) {
+			string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
+			if (fields.Length < 4)
+				continue;
+			if (!(fields [1].Equals ("g") || fields [1].Equals ("d")))
+				continue;
+			if (!fields [2].Equals ("*UND*"))
+				continue;
+
+			int offset = fields [0].ParseHex ();
+			string name = fields [3];
+			if (offset != 0)
+				list.Add (new Symbol (offset, 0, name));
+		}
+		table = new Symbol [list.Count];
+		list.CopyTo (table, 0);
+		Array.Sort (table);
+	}
+
+	public string Translate (int offset) {
+		Symbol sym = null;
+		int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
+		if (res >= 0)
+			return table [res].name;
+		res = ~res;
+
+		if (res >= table.Length)
+			sym = table [table.Length - 1];
+		else if (res != 0)
+			sym = table [res - 1];
+
+		
+		if (sym != null) {
+			int size = Math.Max (sym.size, 10);
+			if (offset - sym.offset < size)
+				return sym.name;
+		}
+		return String.Format ("[{0:x}]", offset);
+	}
+}
+
+public class LinuxSymbolTable : SymbolTable
+{
+	Symbol[] table;
+
+	const int MAX_FUNC_SIZE = 0x20000;
+
+	public LinuxSymbolTable (string binary) {
+		Load (binary);
+	}
+
+	void Load (string binary) {
+		ProcessStartInfo psi = new ProcessStartInfo ("objdump", "-t "+binary);
+		psi.UseShellExecute = false;
+		psi.RedirectStandardOutput = true;
+
+		var proc = Process.Start (psi);
+		var list = new List<Symbol> ();
+		string line;
+		while ((line = proc.StandardOutput.ReadLine ()) != null) {
+			string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
+
+			if (fields.Length < 6)
+				continue;
+			if (fields [3] != ".text" || fields [2] != "F")
+				continue;
+
+			int offset = fields [0].ParseHex ();
+			int size = fields [4].ParseHex ();
+			string name = fields [fields.Length - 1];
+			if (offset != 0)
+				list.Add (new Symbol (offset, size, name));
+		}
+		table = new Symbol [list.Count];
+		list.CopyTo (table, 0);
+		Array.Sort (table);
+	}
+
+	public string Translate (int offset) {
+		Symbol sym = null;
+		int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
+		if (res >= 0)
+			return table [res].name;
+		res = ~res;
+
+		if (res >= table.Length)
+			sym = table [table.Length - 1];
+		else if (res != 0)
+			sym = table [res - 1];
+
+		if (sym != null && offset - sym.offset < MAX_FUNC_SIZE)
+			return sym.name;
+		return String.Format ("[{0:x}]", offset);
+	}
+}
+
+public class TraceDecoder
+{
+	string file;
+
+	public TraceDecoder (string file) {
+		this.file = file;
+	}
+
+	public IEnumerable<Trace> GetTraces () {
+		using (StreamReader reader = new StreamReader (file)) {
+			string line;
+			while ((line = reader.ReadLine ()) != null) {
+				string[] fields = line.Split(new char[] {','}, StringSplitOptions.RemoveEmptyEntries);
+				if (fields.Length >= 7) {
+					yield return new Trace (fields);
+				}
+			}
+		}
+	}
+}
+
+public class Driver
+{
+	[DllImport ("libc")]
+	static extern int uname (IntPtr buf);
+
+	static bool IsOSX ()
+	{
+		bool isOsx = false;
+		IntPtr buf = Marshal.AllocHGlobal (8192);
+		if (uname (buf) == 0) {
+			string os = Marshal.PtrToStringAnsi (buf);
+			isOsx = os == "Darwin";
+		}
+
+		Marshal.FreeHGlobal (buf);
+		return isOsx;
+	}
+
+
+	static void Main (string[] args) {
+		SymbolTable syms;
+		if (args.Length != 2) {
+			Console.WriteLine ("usage: LockTracerDecoder.exe /path/to/mono /path/to/locks.pid");
+			return;
+		}
+		if (IsOSX ())
+			syms = new OsxSymbolTable (args [0]);
+		else
+			syms = new LinuxSymbolTable (args [0]);
+
+		var decoder = new TraceDecoder (args [1]);
+		var sim = new LockSimulator (syms);
+		sim.PlayBack (decoder.GetTraces ());
+	}
+}
+
+public static class Utils
+{
+	public static int ParseHex (this string number) {
+		while (number.Length > 1 && (number [0] == '0' || number [0] == 'x' || number [0] == 'X'))
+			number = number.Substring (1);
+		return int.Parse (number, NumberStyles.HexNumber);
+	}
+
+	public static int ParseDec (this string number) {
+		while (number.Length > 1 && number [0] == '0')
+			number = number.Substring (1);
+		return int.Parse (number);
+	}
+}