data/lock-decoder/LockTracerDecoder.cs

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Diagnostics;
   4 using System.IO;
   5 using System.Globalization;
   6 using System.Runtime.InteropServices;
   7
   8
   9 public enum Record {
  10         MustNotHoldAny,
  11         MustNotHoldOne,
  12         MustHoldOne,
  13         LockAcquired,
  14         LockReleased
  15 }
  16
  17
  18 public struct LockRecord {
  19         public SimLock lk;
  20         public string frame;
  21
  22         public LockRecord (SimLock lk, string frame) {
  23                 this.lk = lk;
  24                 this.frame = frame;
  25         }
  26 }
  27
  28 public class SimThread
  29 {
  30         int thread;
  31         List <LockRecord> locks = new List <LockRecord> ();
  32
  33         public SimThread (int t)
  34         {
  35                 this.thread = t;
  36         }
  37
  38         public bool HoldsLock (SimLock lk) {
  39                 foreach (var l in locks) {
  40                         if (l.lk == lk)
  41                                 return true;
  42                 }
  43                 return false;
  44         }
  45
  46
  47         public int HoldCount (SimLock lk) {
  48                 int res = 0;
  49                 foreach (var l in locks)
  50                         if (l.lk == lk)
  51                                 ++res;
  52                 return res;
  53         }
  54
  55         public void Lock (SimLock lk, string frame) {
  56                 foreach (LockRecord lr in locks) {
  57                         if (lk.WarnAbout (this, lr.lk))
  58                                 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));
  59                         else if (!lk.IsValid (this, lr.lk))
  60                                 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));
  61                 }
  62                 locks.Add (new LockRecord (lk, frame));
  63         }
  64
  65         public void Release (SimLock lk, string frame) {
  66                 if (locks.Count == 0) {
  67                         Console.WriteLine ("ERROR: released lock {0} at {1} while holding no locks!", lk, frame);
  68                         return;
  69                 }
  70                 LockRecord top = locks [locks.Count - 1];
  71                 if (top.lk != lk && !(lk.IsGlobalLock && HoldCount (lk) > 1)) {
  72                         Console.WriteLine ("WARNING: released lock {0} at {1} out of order with {2} at {3}!", lk, frame, top.lk, top.frame);
  73                 }
  74                 for (int i = locks.Count -1; i >= 0; --i) {
  75                         if (locks [i].lk == lk) {
  76                                 locks.RemoveAt (i);
  77                                 break;
  78                         }
  79                 }
  80         }
  81 }
  82
  83 /*
  84 LOCK RULES
  85
  86 Simple locks:
  87         Can be acquired at any point regardless of which locks are taken or not.
  88         No other locks can be acquired or released while holding a simple lock.
  89         Reentrancy is not recomended. (warning)
  90         Simple locks are leaf locks on the lock lattice.
  91
  92 Complex locks:
  93         Must respect locking order, which form a lattice.
  94         IOW, to take a given lock, only it's parents might have been taken.
  95         Reentrancy is ok.
  96         Locks around resources count as separate instances of the hierarchy.
  97
  98 Global locks:
  99         Must respect locking order.
 100         Must be the at the botton of the locking lattice.
 101         Can be taken out-of-order by other locks given that it was previously acquired.
 102         Adding global locks is not to be taken lightly.
 103
 104 The current lock hierarchy:
 105 loader lock
 106         domain lock
 107                 domain jit lock
 108                         simple locks
 109
 110 Examples:
 111         You can take the loader lock without holding a domain lock.
 112         You cannot take a domain lock if the loader lock is held.
 113         You cannot take a domain lock while holding the lock to another domain.
 114 */
 115
 116 public enum Lock {
 117         Invalid,
 118         LoaderLock,
 119         ImageDataLock,
 120         DomainLock,
 121         DomainAssembliesLock,
 122         DomainJitCodeHashLock,
 123 }
 124
 125 public class SimLock
 126 {
 127         Lock kind;
 128         int id;
 129
 130         public SimLock (Lock kind, int id) {
 131                 this.kind = kind;
 132                 this.id = id;
 133         }
 134
 135         static int GetLockOrder (Lock kind) {
 136                 switch (kind) {
 137                         case Lock.LoaderLock:
 138                                 return 0;
 139                         case Lock.DomainLock:
 140                                 return 1;
 141                         case Lock.DomainJitCodeHashLock:
 142                                 return 2;
 143                         default:
 144                                 return 3;
 145                 }
 146         }
 147
 148         bool IsParent (SimLock other) {
 149                 return GetLockOrder (kind) > GetLockOrder (other.kind);
 150         }
 151
 152         public bool IsSimpleLock {
 153                 get { return GetLockOrder (kind) == 3; }
 154         }
 155
 156         public bool IsGlobalLock {
 157                 get { return kind == Lock.LoaderLock; }
 158         }
 159
 160         /*locked is already owned by the thread, 'this' is the new one*/
 161         bool Compare (SimThread thread, SimLock locked, out bool isWarning, out string msg)
 162         {
 163                 isWarning = false;
 164                 msg = null;
 165
 166                 if (locked != this) {
 167                         if (!IsParent (locked)) {
 168                                 if (IsGlobalLock) { /*acquiring a global lock*/
 169                                         if (!thread.HoldsLock (this)) { /*does the thread alread hold it?*/
 170                                                 msg = "Acquired a global lock after a regular lock without having it before.";
 171                                                 return false;
 172                                         }
 173                                 } else {
 174                                         msg = "Hierarchy violation.";
 175                                         return false;
 176                                 }
 177                         }
 178                 } else if (IsSimpleLock) {
 179                         msg = "Avoid taking simple locks recursively";
 180                         isWarning = true;
 181                         return false;
 182                 }
 183
 184                 return true;
 185         }
 186
 187         public bool IsValid (SimThread thread, SimLock locked) {
 188                 bool warn;
 189                 string msg;
 190                 return Compare (thread, locked, out warn, out msg);
 191         }
 192
 193         public bool WarnAbout (SimThread thread, SimLock locked) {
 194                 bool warn;
 195                 string msg;
 196                 Compare (thread, locked, out warn, out msg);
 197                 return warn;
 198         }
 199
 200         public string GetWarningMessage (SimThread thread, SimLock locked) {
 201                 bool warn;
 202                 string msg;
 203                 Compare (thread, locked, out warn, out msg);
 204                 return warn ? msg : null;
 205         }
 206
 207         public string GetErrorMessage (SimThread thread, SimLock locked) {
 208                 bool warn;
 209                 string msg;
 210                 bool res = Compare (thread, locked, out warn, out msg);
 211                 return !res && !warn ? msg : null;
 212         }
 213
 214         public override string ToString () {
 215                 return String.Format ("{0}", kind);
 216         }
 217 }
 218
 219 public class LockSimulator
 220 {
 221         static Dictionary <int, SimThread> threads = new Dictionary <int, SimThread> ();
 222         static Dictionary <int, SimLock> locks = new Dictionary <int, SimLock> ();
 223
 224         SymbolTable syms;
 225
 226         public LockSimulator (SymbolTable s) { this.syms = s; }
 227
 228         SimLock GetLock (Trace t)  {
 229                 if (locks.ContainsKey (t.lockPtr))
 230                         return locks [t.lockPtr];
 231                 else {
 232                         return locks [t.lockPtr] = new SimLock (t.lockKind, t.lockPtr);
 233                 }
 234         }
 235
 236         SimThread GetThread (Trace t) {
 237                 if (threads.ContainsKey (t.thread))
 238                         return threads [t.thread];
 239                 else
 240                         return threads [t.thread] = new SimThread (t.thread);
 241         }
 242
 243         public void PlayBack (IEnumerable<Trace> traces) {
 244                 foreach (var t in traces) {
 245                         SimThread thread = GetThread (t);
 246                         SimLock lk = GetLock (t);
 247                         string frame = t.GetUsefullTopTrace (this.syms);
 248
 249                         switch (t.record) {
 250                         case Record.MustNotHoldAny:
 251                         case Record.MustNotHoldOne:
 252                         case Record.MustHoldOne:
 253                                 throw new Exception ("not supported");
 254                         case Record.LockAcquired:
 255                                 thread.Lock (lk, frame);
 256                                 break;
 257                         case Record.LockReleased:
 258                                 thread.Release (lk, frame);
 259                                 break;
 260                         default:
 261                                 throw new Exception ("Invalid trace record: "+t.record);
 262                         }
 263                 }
 264         }
 265 }
 266
 267 public class Trace {
 268         public int thread;
 269         public Record record;
 270         public Lock lockKind;
 271         public int lockPtr;
 272         int[] frames;
 273
 274         static readonly string[] BAD_FRAME_METHODS = new string[] {
 275                 "mono_loader_lock",
 276                 "mono_loader_unlock",
 277                 "mono_image_lock",
 278                 "mono_image_unlock",
 279         };
 280
 281         public Trace (string[] fields) {
 282                 thread = fields [0].ParseHex ();
 283                 record = (Record)fields [1].ParseDec ();
 284                 lockKind = (Lock)fields [2].ParseDec ();
 285                 lockPtr = fields [3].ParseHex ();
 286                 frames = new int [fields.Length - 4];
 287                 for (int i = 0; i < frames.Length; ++i)
 288                         frames [i] = fields [i + 4].ParseHex ();
 289         }
 290
 291         public void Dump (SymbolTable table) {
 292                 Console.WriteLine ("{0:x} {1} {2} {3:x}", thread, record, lockKind, lockPtr);
 293                 for (int i = 0; i < frames.Length; ++i)
 294                         Console.WriteLine ("\t{0}", table.Translate (frames [i]));
 295         }
 296
 297         public string GetUsefullTopTrace (SymbolTable syms) {
 298                 for (int i = 0; i < frames.Length; ++i) {
 299                         string str = syms.Translate (frames [i]);
 300                         bool ok = true;
 301                         for (int j = 0; j < BAD_FRAME_METHODS.Length; ++j) {
 302                                 if (str.IndexOf (BAD_FRAME_METHODS [j]) >= 0) {
 303                                         ok = false;
 304                                         break;
 305                                 }
 306                         }
 307                         if (ok)
 308                                 return str;
 309                 }
 310                 return "[unknown]";
 311         }
 312 }
 313
 314 public class Symbol : IComparable<Symbol>
 315 {
 316         public int offset;
 317         public int size;
 318         public string name;
 319
 320         public Symbol (int o, int size, string n) {
 321                 this.offset = o;
 322                 this.size = size;
 323                 this.name = n;
 324         }
 325
 326         public int CompareTo(Symbol other) {
 327                 return offset - other.offset;
 328         }
 329 }
 330
 331 public interface SymbolTable {
 332         string Translate (int offset);
 333 }
 334
 335 public class OsxSymbolTable : SymbolTable
 336 {
 337         Symbol[] table;
 338
 339         const int MAX_FUNC_SIZE = 0x20000;
 340
 341         public OsxSymbolTable (string binary) {
 342                 Load (binary);
 343         }
 344
 345         void Load (string binary) {
 346                 ProcessStartInfo psi = new ProcessStartInfo ("gobjdump", "-t "+binary);
 347                 psi.UseShellExecute = false;
 348                 psi.RedirectStandardOutput = true;
 349
 350                 var proc = Process.Start (psi);
 351                 var list = new List<Symbol> ();
 352                 string line;
 353                 while ((line = proc.StandardOutput.ReadLine ()) != null) {
 354                         string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
 355                         if (fields.Length < 4)
 356                                 continue;
 357                         if (!(fields [1].Equals ("g") || fields [1].Equals ("d")))
 358                                 continue;
 359                         if (!fields [2].Equals ("*UND*"))
 360                                 continue;
 361
 362                         int offset = fields [0].ParseHex ();
 363                         string name = fields [3];
 364                         if (offset != 0)
 365                                 list.Add (new Symbol (offset, 0, name));
 366                 }
 367                 table = new Symbol [list.Count];
 368                 list.CopyTo (table, 0);
 369                 Array.Sort (table);
 370         }
 371
 372         public string Translate (int offset) {
 373                 Symbol sym = null;
 374                 int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
 375                 if (res >= 0)
 376                         return table [res].name;
 377                 res = ~res;
 378
 379                 if (res >= table.Length)
 380                         sym = table [table.Length - 1];
 381                 else if (res != 0)
 382                         sym = table [res - 1];
 383
 384
 385                 if (sym != null) {
 386                         int size = Math.Max (sym.size, 10);
 387                         if (offset - sym.offset < size)
 388                                 return sym.name;
 389                 }
 390                 return String.Format ("[{0:x}]", offset);
 391         }
 392 }
 393
 394 public class LinuxSymbolTable : SymbolTable
 395 {
 396         Symbol[] table;
 397
 398         const int MAX_FUNC_SIZE = 0x20000;
 399
 400         public LinuxSymbolTable (string binary) {
 401                 Load (binary);
 402         }
 403
 404         void Load (string binary) {
 405                 ProcessStartInfo psi = new ProcessStartInfo ("objdump", "-t "+binary);
 406                 psi.UseShellExecute = false;
 407                 psi.RedirectStandardOutput = true;
 408
 409                 var proc = Process.Start (psi);
 410                 var list = new List<Symbol> ();
 411                 string line;
 412                 while ((line = proc.StandardOutput.ReadLine ()) != null) {
 413                         string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
 414
 415                         if (fields.Length < 6)
 416                                 continue;
 417                         if (fields [3] != ".text" || fields [2] != "F")
 418                                 continue;
 419
 420                         int offset = fields [0].ParseHex ();
 421                         int size = fields [4].ParseHex ();
 422                         string name = fields [fields.Length - 1];
 423                         if (offset != 0)
 424                                 list.Add (new Symbol (offset, size, name));
 425                 }
 426                 table = new Symbol [list.Count];
 427                 list.CopyTo (table, 0);
 428                 Array.Sort (table);
 429         }
 430
 431         public string Translate (int offset) {
 432                 Symbol sym = null;
 433                 int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
 434                 if (res >= 0)
 435                         return table [res].name;
 436                 res = ~res;
 437
 438                 if (res >= table.Length)
 439                         sym = table [table.Length - 1];
 440                 else if (res != 0)
 441                         sym = table [res - 1];
 442
 443                 if (sym != null && offset - sym.offset < MAX_FUNC_SIZE)
 444                         return sym.name;
 445                 return String.Format ("[{0:x}]", offset);
 446         }
 447 }
 448
 449 public class TraceDecoder
 450 {
 451         string file;
 452
 453         public TraceDecoder (string file) {
 454                 this.file = file;
 455         }
 456
 457         public IEnumerable<Trace> GetTraces () {
 458                 using (StreamReader reader = new StreamReader (file)) {
 459                         string line;
 460                         while ((line = reader.ReadLine ()) != null) {
 461                                 string[] fields = line.Split(new char[] {','}, StringSplitOptions.RemoveEmptyEntries);
 462                                 if (fields.Length >= 7) {
 463                                         yield return new Trace (fields);
 464                                 }
 465                         }
 466                 }
 467         }
 468 }
 469
 470 public class Driver
 471 {
 472         [DllImport ("libc")]
 473         static extern int uname (IntPtr buf);
 474
 475         static bool IsOSX ()
 476         {
 477                 bool isOsx = false;
 478                 IntPtr buf = Marshal.AllocHGlobal (8192);
 479                 if (uname (buf) == 0) {
 480                         string os = Marshal.PtrToStringAnsi (buf);
 481                         isOsx = os == "Darwin";
 482                 }
 483
 484                 Marshal.FreeHGlobal (buf);
 485                 return isOsx;
 486         }
 487
 488
 489         static void Main (string[] args) {
 490                 SymbolTable syms;
 491                 if (args.Length != 2) {
 492                         Console.WriteLine ("usage: LockTracerDecoder.exe /path/to/mono /path/to/locks.pid");
 493                         return;
 494                 }
 495                 if (IsOSX ())
 496                         syms = new OsxSymbolTable (args [0]);
 497                 else
 498                         syms = new LinuxSymbolTable (args [0]);
 499
 500                 var decoder = new TraceDecoder (args [1]);
 501                 var sim = new LockSimulator (syms);
 502                 sim.PlayBack (decoder.GetTraces ());
 503         }
 504 }
 505
 506 public static class Utils
 507 {
 508         public static int ParseHex (this string number) {
 509                 while (number.Length > 1 && (number [0] == '0' || number [0] == 'x' || number [0] == 'X'))
 510                         number = number.Substring (1);
 511                 return int.Parse (number, NumberStyles.HexNumber);
 512         }
 513
 514         public static int ParseDec (this string number) {
 515                 while (number.Length > 1 && number [0] == '0')
 516                         number = number.Substring (1);
 517                 return int.Parse (number);
 518         }
 519 }