Add multi-level function table (#2228)

* Add AddressTable<T>

* Use AddressTable<T> for dispatch

* Remove JumpTable & co.

* Add fallback for out of range addresses

* Add PPTC support

* Add documentation to `AddressTable<T>`

* Make AddressTable<T> configurable

* Fix table walk

* Fix IsMapped check

* Remove CountTableCapacity

* Add PPTC support for fast path

* Rename IsMapped to IsValid

* Remove stale comment

* Change format of address in exception message

* Add TranslatorStubs

* Split DispatchStub

Avoids recompilation of stubs during tests.

* Add hint for 64bit or 32bit

* Add documentation to `Symbol`

* Add documentation to `TranslatorStubs`

Make `TranslatorStubs` disposable as well.

* Add documentation to `SymbolType`

* Add `AddressTableEventSource` to monitor function table size

Add an EventSource which measures the amount of unmanaged bytes
allocated by AddressTable<T> instances.

 dotnet-counters monitor -n Ryujinx --counters ARMeilleure

* Add `AllowLcqInFunctionTable` optimization toggle

This is to reduce the impact this change has on the test duration.
Before everytime a test was ran, the FunctionTable would be initialized
and populated so that the newly compiled test would get registered to
it.

* Implement unmanaged dispatcher

Uses the DispatchStub to dispatch into the next translation, which
allows execution to stay in unmanaged for longer and skips a
ConcurrentDictionary look up when the target translation has been
registered to the FunctionTable.

* Remove redundant null check

* Tune levels of FunctionTable

Uses 5 levels instead of 4 and change unit of AddressTableEventSource
from KB to MB.

* Use 64-bit function table

Improves codegen for direct branches:

    mov qword [rax+0x408],0x10603560
 -  mov rcx,sub_10603560_OFFSET
 -  mov ecx,[rcx]
 -  mov ecx,ecx
 -  mov rdx,JIT_CACHE_BASE
 -  add rdx,rcx
 +  mov rcx,sub_10603560
 +  mov rdx,[rcx]
    mov rcx,rax

Improves codegen for dispatch stub:

    and rax,byte +0x1f
 -  mov eax,[rcx+rax*4]
 -  mov eax,eax
 -  mov rcx,JIT_CACHE_BASE
 -  lea rax,[rcx+rax]
 +  mov rax,[rcx+rax*8]
    mov rcx,rbx

* Remove `JitCacheSymbol` & `JitCache.Offset`

* Turn `Translator.Translate` into an instance method

We do not have to add more parameter to this method and related ones as
new structures are added & needed for translation.

* Add symbol only when PTC is enabled

Address LDj3SNuD's feedback

* Change `NativeContext.Running` to a 32-bit integer

* Fix PageTable symbol for host mapped

3 files changed, 2 insertions, 351 deletions

diff --git a/ARMeilleure/Translation/Cache/JitCache.cs b/ARMeilleure/Translation/Cache/JitCache.cs
index db45c608..c0d0a25d 100644
--- a/ARMeilleure/Translation/Cache/JitCache.cs
+++ b/ARMeilleure/Translation/Cache/JitCache.cs
@@ -25,6 +25,8 @@ namespace ARMeilleure.Translation.Cache
         private static readonly object _lock = new object();
         private static bool _initialized;
 
+        public static IntPtr Base => _jitRegion.Pointer;
+
         public static void Initialize(IJitMemoryAllocator allocator)
         {
             if (_initialized) return;
diff --git a/ARMeilleure/Translation/Cache/JumpTable.cs b/ARMeilleure/Translation/Cache/JumpTable.cs
deleted file mode 100644
index aa3b6caf..00000000
--- a/ARMeilleure/Translation/Cache/JumpTable.cs
+++ /dev/null
@@ -1,279 +0,0 @@
-using ARMeilleure.Diagnostics;
-using ARMeilleure.Memory;
-using ARMeilleure.Translation.PTC;
-using System;
-using System.Collections.Concurrent;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Runtime.InteropServices;
-
-namespace ARMeilleure.Translation.Cache
-{
-    class JumpTable : IDisposable
-    {
-        // The jump table is a block of (guestAddress, hostAddress) function mappings.
-        // Each entry corresponds to one branch in a JIT compiled function. The entries are
-        // reserved specifically for each call.
-        // The Dependants dictionary can be used to update the hostAddress for any functions that change.
-
-        public const int JumpTableStride = 16; // 8 byte guest address, 8 byte host address.
-
-        private const int JumpTableSize = 1048576;
-        private const int JumpTableByteSize = JumpTableSize * JumpTableStride;
-
-        // The dynamic table is also a block of (guestAddress, hostAddress) function mappings.
-        // The main difference is that indirect calls and jumps reserve _multiple_ entries on the table.
-        // These start out as all 0. When an indirect call is made, it tries to find the guest address on the table.
-
-        // If we get to an empty address, the guestAddress is set to the call that we want.
-
-        // If we get to a guestAddress that matches our own (or we just claimed it), the hostAddress is read.
-        // If it is non-zero, we immediately branch or call the host function.
-        // If it is 0, NativeInterface is called to find the rejited address of the call.
-        // If none is found, the hostAddress entry stays at 0. Otherwise, the new address is placed in the entry.
-
-        // If the table size is exhausted and we didn't find our desired address, we fall back to requesting
-        // the function from the JIT.
-
-        public const int DynamicTableElems = 1;
-
-        public const int DynamicTableStride = DynamicTableElems * JumpTableStride;
-
-        private const int DynamicTableSize = 1048576;
-        private const int DynamicTableByteSize = DynamicTableSize * DynamicTableStride;
-
-        public const int DynamicEntryTag = 1 << 31;
-
-        private readonly ReservedRegion _jumpRegion;
-        private readonly ReservedRegion _dynamicRegion;
-
-        public IntPtr JumpPointer => _jumpRegion.Pointer;
-        public IntPtr DynamicPointer => _dynamicRegion.Pointer;
-
-        public JumpTableEntryAllocator Table { get; }
-        public JumpTableEntryAllocator DynTable { get; }
-
-        public ConcurrentDictionary<ulong, TranslatedFunction> Targets { get; }
-        public ConcurrentDictionary<ulong, List<int>> Dependants { get; } // TODO: Attach to TranslatedFunction or a wrapper class.
-        public ConcurrentDictionary<ulong, List<int>> Owners { get; }
-
-        public JumpTable(IJitMemoryAllocator allocator)
-        {
-            _jumpRegion = new ReservedRegion(allocator, JumpTableByteSize);
-            _dynamicRegion = new ReservedRegion(allocator, DynamicTableByteSize);
-
-            Table = new JumpTableEntryAllocator();
-            DynTable = new JumpTableEntryAllocator();
-
-            Targets = new ConcurrentDictionary<ulong, TranslatedFunction>();
-            Dependants = new ConcurrentDictionary<ulong, List<int>>();
-            Owners = new ConcurrentDictionary<ulong, List<int>>();
-
-            Symbols.Add((ulong)_jumpRegion.Pointer.ToInt64(), JumpTableByteSize, JumpTableStride, "JMP_TABLE");
-            Symbols.Add((ulong)_dynamicRegion.Pointer.ToInt64(), DynamicTableByteSize, DynamicTableStride, "DYN_TABLE");
-        }
-
-        public void Initialize(PtcJumpTable ptcJumpTable, ConcurrentDictionary<ulong, TranslatedFunction> funcs)
-        {
-            foreach (ulong guestAddress in ptcJumpTable.Targets)
-            {
-                if (funcs.TryGetValue(guestAddress, out TranslatedFunction func))
-                {
-                    Targets.TryAdd(guestAddress, func);
-                }
-                else
-                {
-                    throw new KeyNotFoundException($"({nameof(guestAddress)} = 0x{guestAddress:X16})");
-                }
-            }
-
-            foreach (var kv in ptcJumpTable.Dependants)
-            {
-                Dependants.TryAdd(kv.Key, new List<int>(kv.Value));
-            }
-
-            foreach (var kv in ptcJumpTable.Owners)
-            {
-                Owners.TryAdd(kv.Key, new List<int>(kv.Value));
-            }
-        }
-
-        public void RegisterFunction(ulong address, TranslatedFunction func)
-        {
-            Targets.AddOrUpdate(address, func, (key, oldFunc) => func);
-            long funcPtr = func.FuncPtr.ToInt64();
-
-            // Update all jump table entries that target this address.
-            if (Dependants.TryGetValue(address, out List<int> myDependants))
-            {
-                lock (myDependants)
-                {
-                    foreach (int entry in myDependants)
-                    {
-                        IntPtr addr = GetEntryAddressJumpTable(entry);
-
-                        Marshal.WriteInt64(addr, 8, funcPtr);
-                    }
-                }
-            }
-        }
-
-        public int ReserveTableEntry(ulong ownerGuestAddress, ulong address, bool isJump)
-        {
-            int entry = Table.AllocateEntry();
-
-            ExpandIfNeededJumpTable(entry);
-
-            // Is the address we have already registered? If so, put the function address in the jump table.
-            // If not, it will point to the direct call stub.
-            long value = DirectCallStubs.DirectCallStub(isJump).ToInt64();
-            if (Targets.TryGetValue(address, out TranslatedFunction func))
-            {
-                value = func.FuncPtr.ToInt64();
-            }
-
-            // Make sure changes to the function at the target address update this jump table entry.
-            List<int> targetDependants = Dependants.GetOrAdd(address, (addr) => new List<int>());
-            lock (targetDependants)
-            {
-                targetDependants.Add(entry);
-            }
-
-            // Keep track of ownership for jump table entries.
-            List<int> ownerEntries = Owners.GetOrAdd(ownerGuestAddress, (addr) => new List<int>());
-            lock (ownerEntries)
-            {
-                ownerEntries.Add(entry);
-            }
-
-            IntPtr addr = GetEntryAddressJumpTable(entry);
-
-            Marshal.WriteInt64(addr, 0, (long)address);
-            Marshal.WriteInt64(addr, 8, value);
-
-            return entry;
-        }
-
-        public int ReserveDynamicEntry(ulong ownerGuestAddress, bool isJump)
-        {
-            int entry = DynTable.AllocateEntry();
-
-            ExpandIfNeededDynamicTable(entry);
-
-            // Keep track of ownership for jump table entries.
-            List<int> ownerEntries = Owners.GetOrAdd(ownerGuestAddress, (addr) => new List<int>());
-            lock (ownerEntries)
-            {
-                ownerEntries.Add(entry | DynamicEntryTag);
-            }
-
-            // Initialize all host function pointers to the indirect call stub.
-            IntPtr addr = GetEntryAddressDynamicTable(entry);
-            long stubPtr = DirectCallStubs.IndirectCallStub(isJump).ToInt64();
-
-            for (int i = 0; i < DynamicTableElems; i++)
-            {
-                Marshal.WriteInt64(addr, i * JumpTableStride + 8, stubPtr);
-            }
-
-            return entry;
-        }
-
-        // For future use.
-        public void RemoveFunctionEntries(ulong guestAddress)
-        {
-            Targets.TryRemove(guestAddress, out _);
-            Dependants.TryRemove(guestAddress, out _);
-
-            if (Owners.TryRemove(guestAddress, out List<int> entries))
-            {
-                foreach (int entry in entries)
-                {
-                    if ((entry & DynamicEntryTag) == 0)
-                    {
-                        IntPtr addr = GetEntryAddressJumpTable(entry);
-
-                        Marshal.WriteInt64(addr, 0, 0L);
-                        Marshal.WriteInt64(addr, 8, 0L);
-
-                        Table.FreeEntry(entry);
-                    }
-                    else
-                    {
-                        IntPtr addr = GetEntryAddressDynamicTable(entry & ~DynamicEntryTag);
-
-                        for (int j = 0; j < DynamicTableElems; j++)
-                        {
-                            Marshal.WriteInt64(addr + j * JumpTableStride, 0, 0L);
-                            Marshal.WriteInt64(addr + j * JumpTableStride, 8, 0L);
-                        }
-
-                        DynTable.FreeEntry(entry & ~DynamicEntryTag);
-                    }
-                }
-            }
-        }
-
-        public void ExpandIfNeededJumpTable(int entry)
-        {
-            Debug.Assert(entry >= 0);
-
-            if (entry < JumpTableSize)
-            {
-                _jumpRegion.ExpandIfNeeded((ulong)((entry + 1) * JumpTableStride));
-            }
-            else
-            {
-                throw new OutOfMemoryException("JIT Direct Jump Table exhausted.");
-            }
-        }
-
-        public void ExpandIfNeededDynamicTable(int entry)
-        {
-            Debug.Assert(entry >= 0);
-
-            if (entry < DynamicTableSize)
-            {
-                _dynamicRegion.ExpandIfNeeded((ulong)((entry + 1) * DynamicTableStride));
-            }
-            else
-            {
-                throw new OutOfMemoryException("JIT Dynamic Jump Table exhausted.");
-            }
-        }
-
-        public IntPtr GetEntryAddressJumpTable(int entry)
-        {
-            Debug.Assert(Table.EntryIsValid(entry));
-
-            return _jumpRegion.Pointer + entry * JumpTableStride;
-        }
-
-        public IntPtr GetEntryAddressDynamicTable(int entry)
-        {
-            Debug.Assert(DynTable.EntryIsValid(entry));
-
-            return _dynamicRegion.Pointer + entry * DynamicTableStride;
-        }
-
-        public bool CheckEntryFromAddressJumpTable(IntPtr entryAddress)
-        {
-            int entry = Math.DivRem((int)((ulong)entryAddress - (ulong)_jumpRegion.Pointer), JumpTableStride, out int rem);
-
-            return rem == 0 && Table.EntryIsValid(entry);
-        }
-
-        public bool CheckEntryFromAddressDynamicTable(IntPtr entryAddress)
-        {
-            int entry = Math.DivRem((int)((ulong)entryAddress - (ulong)_dynamicRegion.Pointer), DynamicTableStride, out int rem);
-
-            return rem == 0 && DynTable.EntryIsValid(entry);
-        }
-
-        public void Dispose()
-        {
-            _jumpRegion.Dispose();
-            _dynamicRegion.Dispose();
-        }
-    }
-}
diff --git a/ARMeilleure/Translation/Cache/JumpTableEntryAllocator.cs b/ARMeilleure/Translation/Cache/JumpTableEntryAllocator.cs
deleted file mode 100644
index ae2c075e..00000000
--- a/ARMeilleure/Translation/Cache/JumpTableEntryAllocator.cs
+++ /dev/null
@@ -1,72 +0,0 @@
-using ARMeilleure.Common;
-using System.Collections.Generic;
-using System.Diagnostics;
-
-namespace ARMeilleure.Translation.Cache
-{
-    class JumpTableEntryAllocator
-    {
-        private readonly BitMap _bitmap;
-        private int _freeHint;
-
-        public JumpTableEntryAllocator()
-        {
-            _bitmap = new BitMap();
-        }
-
-        public bool EntryIsValid(int entryIndex)
-        {
-            lock (_bitmap)
-            {
-                return _bitmap.IsSet(entryIndex);
-            }
-        }
-
-        public void SetEntry(int entryIndex)
-        {
-            lock (_bitmap)
-            {
-                _bitmap.Set(entryIndex);
-            }
-        }
-
-        public int AllocateEntry()
-        {
-            lock (_bitmap)
-            {
-                int entryIndex;
-
-                if (!_bitmap.IsSet(_freeHint))
-                {
-                    entryIndex = _freeHint;
-                }
-                else
-                {
-                    entryIndex = _bitmap.FindFirstUnset();
-                }
-
-                _freeHint = entryIndex + 1;
-
-                bool wasSet = _bitmap.Set(entryIndex);
-                Debug.Assert(wasSet);
-
-                return entryIndex;
-            }
-        }
-
-        public void FreeEntry(int entryIndex)
-        {
-            lock (_bitmap)
-            {
-                _bitmap.Clear(entryIndex);
-
-                _freeHint = entryIndex;
-            }
-        }
-
-        public IEnumerable<int> GetEntries()
-        {
-            return _bitmap;
-        }
-    }
-}