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 (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 spliting mono_image_init_name_cache into a locked and an unlocked variants and calling them appropriatedly.
 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                 return String.Format ("{0}", kind);
 247         }
 248 }
 249
 250 public class LockSimulator
 251 {
 252         static Dictionary <int, SimThread> threads = new Dictionary <int, SimThread> ();
 253         static Dictionary <int, SimLock> locks = new Dictionary <int, SimLock> ();
 254
 255         SymbolTable syms;
 256
 257         public LockSimulator (SymbolTable s) { this.syms = s; }
 258
 259         SimLock GetLock (Trace t)  {
 260                 if (locks.ContainsKey (t.lockPtr))
 261                         return locks [t.lockPtr];
 262                 else {
 263                         return locks [t.lockPtr] = new SimLock (t.lockKind, t.lockPtr);
 264                 }
 265         }
 266
 267         SimThread GetThread (Trace t) {
 268                 if (threads.ContainsKey (t.thread))
 269                         return threads [t.thread];
 270                 else
 271                         return threads [t.thread] = new SimThread (t.thread);
 272         }
 273
 274         public void PlayBack (IEnumerable<Trace> traces) {
 275                 foreach (var t in traces) {
 276                         SimThread thread = GetThread (t);
 277                         SimLock lk = GetLock (t);
 278                         string frame = t.GetUsefullTopTrace (this.syms);
 279
 280                         switch (t.record) {
 281                         case Record.MustNotHoldAny:
 282                         case Record.MustNotHoldOne:
 283                         case Record.MustHoldOne:
 284                                 throw new Exception ("not supported");
 285                         case Record.LockAcquired:
 286                                 thread.Lock (lk, frame);
 287                                 break;
 288                         case Record.LockReleased:
 289                                 thread.Release (lk, frame);
 290                                 break;
 291                         default:
 292                                 throw new Exception ("Invalid trace record: "+t.record);
 293                         }
 294                 }
 295         }
 296 }
 297
 298 public class Trace {
 299         public int thread;
 300         public Record record;
 301         public Lock lockKind;
 302         public int lockPtr;
 303         int[] frames;
 304
 305         static readonly string[] BAD_FRAME_METHODS = new string[] {
 306                 "mono_loader_lock",
 307                 "mono_loader_unlock",
 308                 "mono_image_lock",
 309                 "mono_image_unlock",
 310                 "mono_icall_lock",
 311                 "mono_icall_unlock",
 312                 "add_record",
 313                 "mono_locks_lock_acquired",
 314                 "mono_locks_lock_released",
 315                 "mono_threads_lock",
 316                 "mono_threads_unlock",
 317         };
 318
 319         public Trace (string[] fields) {
 320                 thread = fields [0].ParseHex ();
 321                 record = (Record)fields [1].ParseDec ();
 322                 lockKind = (Lock)fields [2].ParseDec ();
 323                 lockPtr = fields [3].ParseHex ();
 324                 frames = new int [fields.Length - 4];
 325                 for (int i = 0; i < frames.Length; ++i)
 326                         frames [i] = fields [i + 4].ParseHex ();
 327         }
 328
 329         public void Dump (SymbolTable table) {
 330                 Console.WriteLine ("{0:x} {1} {2} {3:x}", thread, record, lockKind, lockPtr);
 331                 for (int i = 0; i < frames.Length; ++i)
 332                         Console.WriteLine ("\t{0}", table.Translate (frames [i]));
 333         }
 334
 335         public string GetUsefullTopTrace (SymbolTable syms) {
 336                 for (int i = 0; i < frames.Length; ++i) {
 337                         string str = syms.Translate (frames [i]);
 338                         bool ok = true;
 339                         for (int j = 0; j < BAD_FRAME_METHODS.Length; ++j) {
 340                                 if (str.IndexOf (BAD_FRAME_METHODS [j]) >= 0) {
 341                                         ok = false;
 342                                         break;
 343                                 }
 344                         }
 345                         if (ok)
 346                                 return str;
 347                 }
 348                 return "[unknown]";
 349         }
 350 }
 351
 352 public class Symbol : IComparable<Symbol>
 353 {
 354         public int offset;
 355         public int size;
 356         public string name;
 357
 358         public Symbol (int o, int size, string n) {
 359                 this.offset = o;
 360                 this.size = size;
 361                 this.name = n;
 362         }
 363
 364         public int CompareTo(Symbol other) {
 365                 return offset - other.offset;
 366         }
 367
 368         public void AdjustSize (Symbol next) {
 369                 size = next.offset - this.offset;
 370         }
 371 }
 372
 373 public interface SymbolTable {
 374         string Translate (int offset);
 375 }
 376
 377 public class OsxSymbolTable : SymbolTable
 378 {
 379         Symbol[] table;
 380
 381         const int MAX_FUNC_SIZE = 0x20000;
 382
 383         public OsxSymbolTable (string binary) {
 384                 Load (binary);
 385         }
 386
 387         void Load (string binary) {
 388                 ProcessStartInfo psi = new ProcessStartInfo ("gobjdump", "-t "+binary);
 389                 psi.UseShellExecute = false;
 390                 psi.RedirectStandardOutput = true;
 391
 392                 var proc = Process.Start (psi);
 393                 var list = new List<Symbol> ();
 394                 string line;
 395                 while ((line = proc.StandardOutput.ReadLine ()) != null) {
 396                         string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
 397                         if (fields.Length < 7)
 398                                 continue;
 399
 400                         if (!fields [3].Equals ("FUN"))
 401                                 continue;
 402
 403                         int offset = fields [0].ParseHex ();
 404                         string name = fields [6];
 405                         if (name.StartsWith ("_"))
 406                                 name = name.Substring (1);
 407
 408                         if (offset != 0)
 409                                 list.Add (new Symbol (offset, 0, name));
 410                 }
 411                 table = new Symbol [list.Count];
 412                 list.CopyTo (table, 0);
 413                 Array.Sort (table);
 414                 for (int i = 1; i < table.Length; ++i) {
 415                         table [i - 1].AdjustSize (table [i]);
 416                 }
 417         }
 418
 419         public string Translate (int offset) {
 420                 Symbol sym = null;
 421                 int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
 422                 if (res >= 0)
 423                         return table [res].name;
 424                 res = ~res;
 425
 426                 if (res >= table.Length)
 427                         sym = table [table.Length - 1];
 428                 else if (res != 0)
 429                         sym = table [res - 1];
 430
 431
 432                 if (sym != null) {
 433                         int size = Math.Max (sym.size, 10);
 434                         if (offset - sym.offset < size)
 435                                 return sym.name;
 436                 }
 437                 return String.Format ("[{0:x}]", offset);
 438         }
 439 }
 440
 441 public class LinuxSymbolTable : SymbolTable
 442 {
 443         Symbol[] table;
 444
 445         const int MAX_FUNC_SIZE = 0x20000;
 446
 447         public LinuxSymbolTable (string binary) {
 448                 Load (binary);
 449         }
 450
 451         void Load (string binary) {
 452                 ProcessStartInfo psi = new ProcessStartInfo ("objdump", "-t "+binary);
 453                 psi.UseShellExecute = false;
 454                 psi.RedirectStandardOutput = true;
 455
 456                 var proc = Process.Start (psi);
 457                 var list = new List<Symbol> ();
 458                 string line;
 459                 while ((line = proc.StandardOutput.ReadLine ()) != null) {
 460                         string[] fields = line.Split(new char[] {' ', '\t'}, StringSplitOptions.RemoveEmptyEntries);
 461
 462                         if (fields.Length < 6)
 463                                 continue;
 464                         if (fields [3] != ".text" || fields [2] != "F")
 465                                 continue;
 466
 467                         int offset = fields [0].ParseHex ();
 468                         int size = fields [4].ParseHex ();
 469                         string name = fields [fields.Length - 1];
 470                         if (offset != 0)
 471                                 list.Add (new Symbol (offset, size, name));
 472                 }
 473                 table = new Symbol [list.Count];
 474                 list.CopyTo (table, 0);
 475                 Array.Sort (table);
 476         }
 477
 478         public string Translate (int offset) {
 479                 Symbol sym = null;
 480                 int res = Array.BinarySearch (table, new Symbol (offset, 0, null));
 481                 if (res >= 0)
 482                         return table [res].name;
 483                 res = ~res;
 484
 485                 if (res >= table.Length)
 486                         sym = table [table.Length - 1];
 487                 else if (res != 0)
 488                         sym = table [res - 1];
 489
 490                 if (sym != null && offset - sym.offset < MAX_FUNC_SIZE)
 491                         return sym.name;
 492                 return String.Format ("[{0:x}]", offset);
 493         }
 494 }
 495
 496 public class TraceDecoder
 497 {
 498         string file;
 499
 500         public TraceDecoder (string file) {
 501                 this.file = file;
 502         }
 503
 504         public IEnumerable<Trace> GetTraces () {
 505                 using (StreamReader reader = new StreamReader (file)) {
 506                         string line;
 507                         while ((line = reader.ReadLine ()) != null) {
 508                                 string[] fields = line.Split(new char[] {','}, StringSplitOptions.RemoveEmptyEntries);
 509                                 if (fields.Length >= 7) {
 510                                         yield return new Trace (fields);
 511                                 }
 512                         }
 513                 }
 514         }
 515 }
 516
 517 public class Driver
 518 {
 519         [DllImport ("libc")]
 520         static extern int uname (IntPtr buf);
 521
 522         static bool IsOSX ()
 523         {
 524                 bool isOsx = false;
 525                 IntPtr buf = Marshal.AllocHGlobal (8192);
 526                 if (uname (buf) == 0) {
 527                         string os = Marshal.PtrToStringAnsi (buf);
 528                         isOsx = os == "Darwin";
 529                 }
 530
 531                 Marshal.FreeHGlobal (buf);
 532                 return isOsx;
 533         }
 534
 535
 536         static void Main (string[] args) {
 537                 SymbolTable syms;
 538                 if (args.Length != 2) {
 539                         Console.WriteLine ("usage: LockTracerDecoder.exe /path/to/mono /path/to/locks.pid");
 540                         return;
 541                 }
 542                 if (IsOSX ())
 543                         syms = new OsxSymbolTable (args [0]);
 544                 else
 545                         syms = new LinuxSymbolTable (args [0]);
 546
 547                 var decoder = new TraceDecoder (args [1]);
 548                 var sim = new LockSimulator (syms);
 549                 sim.PlayBack (decoder.GetTraces ());
 550         }
 551 }
 552
 553 public static class Utils
 554 {
 555         public static int ParseHex (this string number) {
 556                 while (number.Length > 1 && (number [0] == '0' || number [0] == 'x' || number [0] == 'X'))
 557                         number = number.Substring (1);
 558                 return int.Parse (number, NumberStyles.HexNumber);
 559         }
 560
 561         public static int ParseDec (this string number) {
 562                 while (number.Length > 1 && number [0] == '0')
 563                         number = number.Substring (1);
 564                 return int.Parse (number);
 565         }
 566 }