Remove cold methods from the CPU cache (#224)

* Remove unused tracing functionality from the CPU

* GetNsoExecutable -> GetExecutable

* Unsigned comparison

* Re-add cpu tracing

* Config change

* Remove cold methods from the translation cache on the cpu

* Replace lock with try lock, pass new ATranslatorCache instead of ATranslator

* Rebase fixups

2 files changed, 100 insertions, 57 deletions

diff --git a/Ryujinx.HLE/HOS/Process.cs b/Ryujinx.HLE/HOS/Process.cs
index 0bc95f0c..f7ec2604 100644
--- a/Ryujinx.HLE/HOS/Process.cs
+++ b/Ryujinx.HLE/HOS/Process.cs
@@ -55,8 +55,6 @@ namespace Ryujinx.HLE.HOS
 
         private List<Executable> Executables;
 
-        private Dictionary<long, string> SymbolTable;
-
         private long ImageBase;
 
         private bool Disposed;
@@ -122,8 +120,6 @@ namespace Ryujinx.HLE.HOS
                 return false;
             }
 
-            MakeSymbolTable();
-
             long MainStackTop = MemoryManager.CodeRegionEnd - KMemoryManager.PageSize;
 
             long MainStackSize = 1 * 1024 * 1024;
@@ -256,69 +252,65 @@ namespace Ryujinx.HLE.HOS
             throw new UndefinedInstructionException(e.Position, e.RawOpCode);
         }
 
-        private void MakeSymbolTable()
+        public void EnableCpuTracing()
         {
-            SymbolTable = new Dictionary<long, string>();
+            Translator.EnableCpuTrace = true;
+        }
 
-            foreach (Executable Exe in Executables)
-            {
-                foreach (KeyValuePair<long, string> KV in Exe.SymbolTable)
-                {
-                    SymbolTable.TryAdd(Exe.ImageBase + KV.Key, KV.Value);
-                }
-            }
+        public void DisableCpuTracing()
+        {
+            Translator.EnableCpuTrace = false;
         }
 
-        private ATranslator GetTranslator()
+        private void CpuTraceHandler(object sender, ACpuTraceEventArgs e)
         {
-            if (Translator == null)
+            Executable Exe = GetExecutable(e.Position);
+
+            if (Exe == null)
             {
-                Translator = new ATranslator(SymbolTable);
+                return;
+            }
 
-                Translator.CpuTrace += CpuTraceHandler;
+            if (!TryGetSubName(Exe, e.Position, out string SubName))
+            {
+                SubName = string.Empty;
             }
 
-            return Translator;
-        }
+            long Offset = e.Position - Exe.ImageBase;
 
-        public void EnableCpuTracing()
-        {
-            Translator.EnableCpuTrace = true;
-        }
+            string ExeNameWithAddr = $"{Exe.Name}:0x{Offset:x8}";
 
-        public void DisableCpuTracing()
-        {
-            Translator.EnableCpuTrace = false;
+            Device.Log.PrintDebug(LogClass.Cpu, ExeNameWithAddr + " " + SubName);
         }
 
-        private void CpuTraceHandler(object sender, ACpuTraceEventArgs e)
+        private ATranslator GetTranslator()
         {
-            string NsoName = string.Empty;
-
-            for (int Index = Executables.Count - 1; Index >= 0; Index--)
+            if (Translator == null)
             {
-                if (e.Position >= Executables[Index].ImageBase)
-                {
-                    NsoName = $"{(e.Position - Executables[Index].ImageBase):x16}";
+                Translator = new ATranslator();
 
-                    break;
-                }
+                Translator.CpuTrace += CpuTraceHandler;
             }
 
-            Device.Log.PrintDebug(LogClass.Cpu, $"Executing at 0x{e.Position:x16} {e.SubName} {NsoName}");
+            return Translator;
         }
 
         public void PrintStackTrace(AThreadState ThreadState)
         {
-            long[] Positions = ThreadState.GetCallStack();
-
             StringBuilder Trace = new StringBuilder();
 
             Trace.AppendLine("Guest stack trace:");
 
-            foreach (long Position in Positions)
+            void AppendTrace(long Position)
             {
-                if (!SymbolTable.TryGetValue(Position, out string SubName))
+                Executable Exe = GetExecutable(Position);
+
+                if (Exe == null)
+                {
+                    return;
+                }
+
+                if (!TryGetSubName(Exe, Position, out string SubName))
                 {
                     SubName = $"Sub{Position:x16}";
                 }
@@ -327,29 +319,77 @@ namespace Ryujinx.HLE.HOS
                     SubName = Demangler.Parse(SubName);
                 }
 
-                Trace.AppendLine(" " + SubName + " (" + GetNsoNameAndAddress(Position) + ")");
+                long Offset = Position - Exe.ImageBase;
+
+                string ExeNameWithAddr = $"{Exe.Name}:0x{Offset:x8}";
+
+                Trace.AppendLine(" " + ExeNameWithAddr + " " + SubName);
+            }
+
+            long FramePointer = (long)ThreadState.X29;
+
+            while (FramePointer != 0)
+            {
+                AppendTrace(Memory.ReadInt64(FramePointer + 8));
+
+                FramePointer = Memory.ReadInt64(FramePointer);
             }
 
             Device.Log.PrintInfo(LogClass.Cpu, Trace.ToString());
         }
 
-        private string GetNsoNameAndAddress(long Position)
+        private bool TryGetSubName(Executable Exe, long Position, out string Name)
         {
-            string Name = string.Empty;
+            Position -= Exe.ImageBase;
 
-            for (int Index = Executables.Count - 1; Index >= 0; Index--)
+            int Left  = 0;
+            int Right = Exe.SymbolTable.Count - 1;
+
+            while (Left <= Right)
             {
-                if (Position >= Executables[Index].ImageBase)
+                int Size = Right - Left;
+
+                int Middle = Left + (Size >> 1);
+
+                ElfSym Symbol = Exe.SymbolTable[Middle];
+
+                long EndPosition = Symbol.Value + Symbol.Size;
+
+                if ((ulong)Position >= (ulong)Symbol.Value && (ulong)Position < (ulong)EndPosition)
+                {
+                    Name = Symbol.Name;
+
+                    return true;
+                }
+
+                if ((ulong)Position < (ulong)Symbol.Value)
                 {
-                    long Offset = Position - Executables[Index].ImageBase;
+                    Right = Middle - 1;
+                }
+                else
+                {
+                    Left = Middle + 1;
+                }
+            }
+
+            Name = null;
 
-                    Name = $"{Executables[Index].Name}:{Offset:x8}";
+            return false;
+        }
 
-                    break;
+        private Executable GetExecutable(long Position)
+        {
+            string Name = string.Empty;
+
+            for (int Index = Executables.Count - 1; Index >= 0; Index--)
+            {
+                if ((ulong)Position >= (ulong)Executables[Index].ImageBase)
+                {
+                    return Executables[Index];
                 }
             }
 
-            return Name;
+            return null;
         }
 
         private void ThreadFinished(object sender, EventArgs e)
diff --git a/Ryujinx.HLE/Loaders/Executable.cs b/Ryujinx.HLE/Loaders/Executable.cs
index 6a3f0b97..a9850e4a 100644
--- a/Ryujinx.HLE/Loaders/Executable.cs
+++ b/Ryujinx.HLE/Loaders/Executable.cs
@@ -3,18 +3,21 @@ using Ryujinx.HLE.HOS;
 using Ryujinx.HLE.HOS.Kernel;
 using Ryujinx.HLE.Loaders.Executables;
 using Ryujinx.HLE.Utilities;
+using System;
 using System.Collections.Generic;
+using System.Collections.ObjectModel;
 using System.IO;
+using System.Linq;
 
 namespace Ryujinx.HLE.Loaders
 {
     class Executable
     {
-        private List<ElfDyn> Dynamic;
+        private AMemory Memory;
 
-        private Dictionary<long, string> m_SymbolTable;
+        private List<ElfDyn> Dynamic;
 
-        public IReadOnlyDictionary<long, string> SymbolTable => m_SymbolTable;
+        public ReadOnlyCollection<ElfSym> SymbolTable;
 
         public string Name { get; private set; }
 
@@ -23,16 +26,12 @@ namespace Ryujinx.HLE.Loaders
         public long ImageBase { get; private set; }
         public long ImageEnd  { get; private set; }
 
-        private AMemory Memory;
-
         private KMemoryManager MemoryManager;
 
         public Executable(IExecutable Exe, KMemoryManager MemoryManager, AMemory Memory, long ImageBase)
         {
             Dynamic = new List<ElfDyn>();
 
-            m_SymbolTable = new Dictionary<long, string>();
-
             FilePath = Exe.FilePath;
 
             if (FilePath != null)
@@ -103,14 +102,18 @@ namespace Ryujinx.HLE.Loaders
 
             long SymEntSize = GetFirstValue(ElfDynTag.DT_SYMENT);
 
+            List<ElfSym> Symbols = new List<ElfSym>();
+
             while ((ulong)SymTblAddr < (ulong)StrTblAddr)
             {
                 ElfSym Sym = GetSymbol(SymTblAddr, StrTblAddr);
 
-                m_SymbolTable.TryAdd(Sym.Value, Sym.Name);
+                Symbols.Add(Sym);
 
                 SymTblAddr += SymEntSize;
             }
+
+            SymbolTable = Array.AsReadOnly(Symbols.OrderBy(x => x.Value).ToArray());
         }
 
         private ElfRel GetRelocation(long Position)