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