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