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 recommended. (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 (global)
 106         domain lock (complex)
 107                 domain jit lock (complex)
 108                 marshal lock
 109                         simple locks
 110
 111 Examples:
 112         You can take the loader lock without holding a domain lock.
 113         You can take the domain load while holding the loader lock
 114         You cannot take the loader lock if only the domain lock is held.
 115         You cannot take a domain lock while holding the lock to another domain.
 116
 117
 118 TODO:
 119
 120 We have a few known ok violation. We need a way to whitelist them.
 121
 122 Known ok issues:
 123
 124 ERROR: tried to acquire lock DomainLock at mono_domain_code_reserve_align while holding DomainLock at mono_class_create_runtime_vtable: Hierarchy violation.
 125         This is triggered when building the vtable of a non-root domain and fetching a vtable trampoline for an offset that has not been built. We'll take the root
 126         domain lock while holding the other one.
 127         This is ok since we never allow locking to have in the other direction, IOW, the root-domain lock is one level down from the other domain-locks.
 128
 129 WARNING: tried to acquire lock ImageDataLock at mono_image_init_name_cache while holding ImageDataLock at mono_class_from_name
 130 WARNING: tried to acquire lock ImageDataLock at mono_image_init_name_cache while holding ImageDataLock at mono_image_add_to_name_cache
 131         Both of those happen when filling up the name_cache, as it needs to alloc image memory.
 132         This one is fixable by splitting mono_image_init_name_cache into a locked and an unlocked variants and calling them appropriately.
 133
 134 */
 135
 136 public enum Lock {
 137         Invalid,
 138         LoaderLock,
 139         ImageDataLock,
 140         DomainLock,
 141         DomainAssembliesLock,
 142         DomainJitCodeHashLock,
 143         IcallLock,
 144         AssemblyBindingLock,
 145         MarshalLock,
 146         ClassesLock,
 147         LoaderGlobalDataLock,
 148         ThreadsLock,
 149 }
 150
 151 public class SimLock
 152 {
 153         Lock kind;
 154         int id;
 155
 156         public SimLock (Lock kind, int id) {
 157                 this.kind = kind;
 158                 this.id = id;
 159         }
 160
 161         static int GetLockOrder (Lock kind) {
 162                 switch (kind) {
 163                         case Lock.LoaderLock:
 164                                 return 0;
 165                         case Lock.DomainLock:
 166                                 return 1;
 167                         case Lock.DomainJitCodeHashLock:
 168                         case Lock.MarshalLock:
 169                                 return 2;
 170                         default:
 171                                 return 3;
 172                 }
 173         }
 174
 175         bool IsParent (SimLock other) {
 176                 return GetLockOrder (kind) > GetLockOrder (other.kind);
 177         }
 178
 179         public bool IsSimpleLock {
 180                 get { return GetLockOrder (kind) == 3; }
 181         }
 182
 183         public bool IsGlobalLock {
 184                 get { return kind == Lock.LoaderLock; }
 185         }
 186
 187         public bool IsResursiveLock {
 188                 get { return kind == Lock.LoaderLock || kind == Lock.DomainLock; }
 189         }
 190
 191         /*locked is already owned by the thread, 'this' is the new one*/
 192         bool Compare (SimThread thread, SimLock locked, out bool isWarning, out string msg)
 193         {
 194                 isWarning = false;
 195                 msg = null;
 196
 197                 if (locked != this) {
 198                         if (!IsParent (locked)) {
 199                                 if (IsGlobalLock) { /*acquiring a global lock*/
 200                                         if (!thread.HoldsLock (this)) { /*does the thread alread hold it?*/
 201                                                 msg = "Acquired a global lock after a regular lock without having it before.";
 202                                                 return false;
 203                                         }
 204                                 } else {
 205                                         msg = "Hierarchy violation.";
 206                                         return false;
 207                                 }
 208                         }
 209                 } else if (IsSimpleLock) {
 210                         msg = "Avoid taking simple locks recursively";
 211                         isWarning = true;
 212                         return false;
 213                 }
 214
 215                 return true;
 216         }
 217
 218         public bool IsValid (SimThread thread, SimLock locked) {
 219                 bool warn;
 220                 string msg;
 221                 return Compare (thread, locked, out warn, out msg);
 222         }
 223
 224         public bool WarnAbout (SimThread thread, SimLock locked) {
 225                 bool warn;
 226                 string msg;
 227                 Compare (thread, locked, out warn, out msg);
 228                 return warn;
 229         }
 230
 231         public string GetWarningMessage (SimThread thread, SimLock locked) {
 232                 bool warn;
 233                 string msg;
 234                 Compare (thread, locked, out warn, out msg);
 235                 return warn ? msg : null;
 236         }
 237
 238         public string GetErrorMessage (SimThread thread, SimLock locked) {
 239                 bool warn;
 240                 string msg;
 241                 bool res = Compare (thread, locked, out warn, out msg);
 242                 return !res && !warn ? msg : null;
 243         }
 244
 245         public override string ToString () {
 246                 switch (kind) {
 247                 case Lock.LoaderLock:
 248                 case Lock.IcallLock:
 249                 case Lock.AssemblyBindingLock:
 250                 case Lock.MarshalLock:
 251                 case Lock.ClassesLock:
 252                 case Lock.LoaderGlobalDataLock:
 253                 case Lock.ThreadsLock:
 254                         return String.Format ("{0}", kind);
 255
 256                 case Lock.ImageDataLock:
 257                 case Lock.DomainLock:
 258                 case Lock.DomainAssembliesLock:
 259                 case Lock.DomainJitCodeHashLock:
 260                         return String.Format ("{0}[{1}]", kind, id);
 261                 default:
 262                         return String.Format ("Unknown({0})[{1}]", kind, id);
 263                 }
 264         }
 265 }
 266
 267 public class LockSimulator
 268 {
 269         static Dictionary <int, SimThread> threads = new Dictionary <int, SimThread> ();
 270         static Dictionary <int, SimLock> locks = new Dictionary <int, SimLock> ();
 271
 272         SymbolTable syms;
 273
 274         public LockSimulator (SymbolTable s) { this.syms = s; }
 275
 276         SimLock GetLock (Trace t)  {
 277                 if (locks.ContainsKey (t.lockPtr))
 278                         return locks [t.lockPtr];
 279                 else {
 280                         return locks [t.lockPtr] = new SimLock (t.lockKind, t.lockPtr);
 281                 }
 282         }
 283
 284         SimThread GetThread (Trace t) {
 285                 if (threads.ContainsKey (t.thread))
 286                         return threads [t.thread];
 287                 else
 288                         return threads [t.thread] = new SimThread (t.thread);
 289         }
 290
 291         public void PlayBack (IEnumerable<Trace> traces) {
 292                 foreach (var t in traces) {
 293                         SimThread thread = GetThread (t);
 294                         SimLock lk = GetLock (t);
 295                         string frame = t.GetUsefullTopTrace (this.syms);
 296
 297                         switch (t.record) {
 298                         case Record.MustNotHoldAny:
 299                         case Record.MustNotHoldOne:
 300                         case Record.MustHoldOne:
 301                                 throw new Exception ("not supported");
 302                         case Record.LockAcquired:
 303                                 thread.Lock (lk, frame);
 304                                 break;
 305                         case Record.LockReleased:
 306                                 thread.Release (lk, frame);
 307                                 break;
 308                         default:
 309                                 throw new Exception ("Invalid trace record: "+t.record);
 310                         }
 311                 }
 312         }
 313 }
 314
 315 public class Trace {
 316         public int thread;
 317         public Record record;
 318         public Lock lockKind;
 319         public int lockPtr;
 320         int[] frames;
 321
 322         static readonly string[] BAD_FRAME_METHODS = new string[] {
 323                 "mono_loader_lock",
 324                 "mono_loader_unlock",
 325                 "mono_image_lock",
 326                 "mono_image_unlock",
 327                 "mono_icall_lock",
 328                 "mono_icall_unlock",
 329                 "add_record",
 330                 "mono_locks_lock_acquired",
 331                 "mono_locks_lock_released",
 332                 "mono_threads_lock",
 333                 "mono_threads_unlock",
 334                 "mono_domain_lock",
 335                 "mono_domain_unlock",
 336         };
 337
 338         public Trace (string[] fields) {
 339                 thread = fields [0].ParseHex ();
 340                 record = (Record)fields [1].ParseDec ();
 341                 lockKind = (Lock)fields [2].ParseDec ();
 342                 lockPtr = fields [3].ParseHex ();
 343                 frames = new int [fields.Length - 4];
 344                 for (int i = 0; i < frames.Length; ++i)
 345                         frames [i] = fields [i + 4].ParseHex ();
 346         }
 347
 348         public void Dump (SymbolTable table) {
 349                 Console.WriteLine ("{0:x} {1} {2} {3:x}", thread, record, lockKind, lockPtr);
 350                 for (int i = 0; i < frames.Length; ++i)
 351                         Console.WriteLine ("\t{0}", table.Translate (frames [i]));
 352         }
 353
 354         public string GetUsefullTopTrace (SymbolTable syms) {
 355                 for (int i = 0; i < frames.Length; ++i) {
 356                         string str = syms.Translate (frames [i]);
 357                         bool ok = true;
 358                         for (int j = 0; j < BAD_FRAME_METHODS.Length; ++j) {
 359                                 if (str.IndexOf (BAD_FRAME_METHODS [j]) >= 0) {
 360                                         ok = false;
 361                                         break;
 362                                 }
 363                         }
 364                         if (ok)
 365                                 return str;
 366                 }
 367                 return "[unknown]";
 368         }
 369 }
 370
 371 public class Symbol : IComparable<Symbol>
 372 {
 373         public int offset;
 374         public int size;
 375         public string name;
 376
 377         public Symbol (int o, int size, string n) {
 378                 this.offset = o;
 379                 this.size = size;
 380                 this.name = n;
 381         }
 382
 383         public int CompareTo(Symbol other) {
 384                 return offset - other.offset;
 385         }
 386
 387         public void AdjustSize (Symbol next) {
 388                 size = next.offset - this.offset;
 389         }
 390 }
 391
 392 public interface SymbolTable {
 393         string Translate (int offset);
 394 }
 395
 396 public class OsxSymbolTable : SymbolTable
 397 {
 398         Symbol[] table;
 399
 400         const int MAX_FUNC_SIZE = 0x20000;
 401
 402         public OsxSymbolTable (string binary) {
 403                 Load (binary);
 404         }
 405
 406         void Load (string binary) {
 407                 ProcessStartInfo psi = new ProcessStartInfo ("gobjdump", "-t "+binary);
 408                 psi.UseShellExecute = false;
 409                 psi.RedirectStandardOutput = true;
 410
 411                 var proc = Process.Start (psi);
 412                 var list = new List<Symbol> ();
 413                 string line;
 414                 while ((line = proc.StandardOutput.ReadLine ()) != null) {
 415                         string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
 416                         if (fields.Length < 7)
 417                                 continue;
 418
 419                         if (!fields [3].Equals ("FUN"))
 420                                 continue;
 421
 422                         int offset = fields [0].ParseHex ();
 423                         string name = fields [6];
 424                         if (name.StartsWith ("_"))
 425                                 name = name.Substring (1);
 426
 427                         if (offset != 0)
 428                                 list.Add (new Symbol (offset, 0, name));
 429                 }
 430                 table = new Symbol [list.Count];
 431                 list.CopyTo (table, 0);
 432                 Array.Sort (table);
 433                 for (int i = 1; i < table.Length; ++i) {
 434                         table [i - 1].AdjustSize (table [i]);
 435                 }
 436         }
 437
 438         public string Translate (int offset) {
 439                 Symbol sym = null;
 440                 int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
 441                 if (res >= 0)
 442                         return table [res].name;
 443                 res = ~res;
 444
 445                 if (res >= table.Length)
 446                         sym = table [table.Length - 1];
 447                 else if (res != 0)
 448                         sym = table [res - 1];
 449
 450
 451                 if (sym != null) {
 452                         int size = Math.Max (sym.size, 10);
 453                         if (offset - sym.offset < size)
 454                                 return sym.name;
 455                 }
 456                 return String.Format ("[{0:x}]", offset);
 457         }
 458 }
 459
 460 public class LinuxSymbolTable : SymbolTable
 461 {
 462         Symbol[] table;
 463
 464         const int MAX_FUNC_SIZE = 0x20000;
 465
 466         public LinuxSymbolTable (string binary) {
 467                 Load (binary);
 468         }
 469
 470         void Load (string binary) {
 471                 ProcessStartInfo psi = new ProcessStartInfo ("objdump", "-t "+binary);
 472                 psi.UseShellExecute = false;
 473                 psi.RedirectStandardOutput = true;
 474
 475                 var proc = Process.Start (psi);
 476                 var list = new List<Symbol> ();
 477                 string line;
 478                 while ((line = proc.StandardOutput.ReadLine ()) != null) {
 479                         string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
 480
 481                         if (fields.Length < 6)
 482                                 continue;
 483                         if (fields [3] != ".text" || fields [2] != "F")
 484                                 continue;
 485
 486                         int offset = fields [0].ParseHex ();
 487                         int size = fields [4].ParseHex ();
 488                         string name = fields [fields.Length - 1];
 489                         if (offset != 0)
 490                                 list.Add (new Symbol (offset, size, name));
 491                 }
 492                 table = new Symbol [list.Count];
 493                 list.CopyTo (table, 0);
 494                 Array.Sort (table);
 495         }
 496
 497         public string Translate (int offset) {
 498                 Symbol sym = null;
 499                 int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
 500                 if (res >= 0)
 501                         return table [res].name;
 502                 res = ~res;
 503
 504                 if (res >= table.Length)
 505                         sym = table [table.Length - 1];
 506                 else if (res != 0)
 507                         sym = table [res - 1];
 508
 509                 if (sym != null && offset - sym.offset < MAX_FUNC_SIZE)
 510                         return sym.name;
 511                 return String.Format ("[{0:x}]", offset);
 512         }
 513 }
 514
 515 public class TraceDecoder
 516 {
 517         string file;
 518
 519         public TraceDecoder (string file) {
 520                 this.file = file;
 521         }
 522
 523         public IEnumerable<Trace> GetTraces () {
 524                 using (StreamReader reader = new StreamReader (file)) {
 525                         string line;
 526                         while ((line = reader.ReadLine ()) != null) {
 527                                 string[] fields = line.Split(new char[] {','}, StringSplitOptions.RemoveEmptyEntries);
 528                                 if (fields.Length >= 7) {
 529                                         yield return new Trace (fields);
 530                                 }
 531                         }
 532                 }
 533         }
 534 }
 535
 536 public class Driver
 537 {
 538         [DllImport ("libc")]
 539         static extern int uname (IntPtr buf);
 540
 541         static bool IsOSX ()
 542         {
 543                 bool isOsx = false;
 544                 IntPtr buf = Marshal.AllocHGlobal (8192);
 545                 if (uname (buf) == 0) {
 546                         string os = Marshal.PtrToStringAnsi (buf);
 547                         isOsx = os == "Darwin";
 548                 }
 549
 550                 Marshal.FreeHGlobal (buf);
 551                 return isOsx;
 552         }
 553
 554
 555         static void Main (string[] args) {
 556                 SymbolTable syms;
 557                 if (args.Length != 2) {
 558                         Console.WriteLine ("usage: LockTracerDecoder.exe /path/to/mono /path/to/locks.pid");
 559                         return;
 560                 }
 561                 if (IsOSX ())
 562                         syms = new OsxSymbolTable (args [0]);
 563                 else
 564                         syms = new LinuxSymbolTable (args [0]);
 565
 566                 var decoder = new TraceDecoder (args [1]);
 567                 var sim = new LockSimulator (syms);
 568                 sim.PlayBack (decoder.GetTraces ());
 569         }
 570 }
 571
 572 public static class Utils
 573 {
 574         public static int ParseHex (this string number) {
 575                 while (number.Length > 1 && (number [0] == '0' || number [0] == 'x' || number [0] == 'X'))
 576                         number = number.Substring (1);
 577                 return int.Parse (number, NumberStyles.HexNumber);
 578         }
 579
 580         public static int ParseDec (this string number) {
 581                 while (number.Length > 1 && number [0] == '0')
 582                         number = number.Substring (1);
 583                 return int.Parse (number);
 584         }
 585 }