1  using ARMeilleure.Diagnostics;
  2  using System;
  3  using System.Collections.Generic;
  4  using System.Runtime.InteropServices;
  5  
  6  namespace ARMeilleure.Common
  7  {
  8      /// <summary>
  9      /// Represents a table of guest address to a value.
 10      /// </summary>
 11      /// <typeparam name="TEntry">Type of the value</typeparam>
 12      public unsafe class AddressTable<TEntry> : IDisposable where TEntry : unmanaged
 13      {
 14          /// <summary>
 15          /// Represents a level in an <see cref="AddressTable{TEntry}"/>.
 16          /// </summary>
 17          public readonly struct Level
 18          {
 19              /// <summary>
 20              /// Gets the index of the <see cref="Level"/> in the guest address.
 21              /// </summary>
 22              public int Index { get; }
 23  
 24              /// <summary>
 25              /// Gets the length of the <see cref="Level"/> in the guest address.
 26              /// </summary>
 27              public int Length { get; }
 28  
 29              /// <summary>
 30              /// Gets the mask which masks the bits used by the <see cref="Level"/>.
 31              /// </summary>
 32              public ulong Mask => ((1ul << Length) - 1) << Index;
 33  
 34              /// <summary>
 35              /// Initializes a new instance of the <see cref="Level"/> structure with the specified
 36              /// <paramref name="index"/> and <paramref name="length"/>.
 37              /// </summary>
 38              /// <param name="index">Index of the <see cref="Level"/></param>
 39              /// <param name="length">Length of the <see cref="Level"/></param>
 40              public Level(int index, int length)
 41              {
 42                  (Index, Length) = (index, length);
 43              }
 44  
 45              /// <summary>
 46              /// Gets the value of the <see cref="Level"/> from the specified guest <paramref name="address"/>.
 47              /// </summary>
 48              /// <param name="address">Guest address</param>
 49              /// <returns>Value of the <see cref="Level"/> from the specified guest <paramref name="address"/></returns>
 50              public int GetValue(ulong address)
 51              {
 52                  return (int)((address & Mask) >> Index);
 53              }
 54          }
 55  
 56          private bool _disposed;
 57          private TEntry** _table;
 58          private readonly List<IntPtr> _pages;
 59  
 60          /// <summary>
 61          /// Gets the bits used by the <see cref="Levels"/> of the <see cref="AddressTable{TEntry}"/> instance.
 62          /// </summary>
 63          public ulong Mask { get; }
 64  
 65          /// <summary>
 66          /// Gets the <see cref="Level"/>s used by the <see cref="AddressTable{TEntry}"/> instance.
 67          /// </summary>
 68          public Level[] Levels { get; }
 69  
 70          /// <summary>
 71          /// Gets or sets the default fill value of newly created leaf pages.
 72          /// </summary>
 73          public TEntry Fill { get; set; }
 74  
 75          /// <summary>
 76          /// Gets the base address of the <see cref="EntryTable{TEntry}"/>.
 77          /// </summary>
 78          /// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
 79          public IntPtr Base
 80          {
 81              get
 82              {
 83                  ObjectDisposedException.ThrowIf(_disposed, this);
 84  
 85                  lock (_pages)
 86                  {
 87                      return (IntPtr)GetRootPage();
 88                  }
 89              }
 90          }
 91  
 92          /// <summary>
 93          /// Constructs a new instance of the <see cref="AddressTable{TEntry}"/> class with the specified list of
 94          /// <see cref="Level"/>.
 95          /// </summary>
 96          /// <exception cref="ArgumentNullException"><paramref name="levels"/> is null</exception>
 97          /// <exception cref="ArgumentException">Length of <paramref name="levels"/> is less than 2</exception>
 98          public AddressTable(Level[] levels)
 99          {
100              ArgumentNullException.ThrowIfNull(levels);
101  
102              if (levels.Length < 2)
103              {
104                  throw new ArgumentException("Table must be at least 2 levels deep.", nameof(levels));
105              }
106  
107              _pages = new List<IntPtr>(capacity: 16);
108  
109              Levels = levels;
110              Mask = 0;
111  
112              foreach (var level in Levels)
113              {
114                  Mask |= level.Mask;
115              }
116          }
117  
118          /// <summary>
119          /// Determines if the specified <paramref name="address"/> is in the range of the
120          /// <see cref="AddressTable{TEntry}"/>.
121          /// </summary>
122          /// <param name="address">Guest address</param>
123          /// <returns><see langword="true"/> if is valid; otherwise <see langword="false"/></returns>
124          public bool IsValid(ulong address)
125          {
126              return (address & ~Mask) == 0;
127          }
128  
129          /// <summary>
130          /// Gets a reference to the value at the specified guest <paramref name="address"/>.
131          /// </summary>
132          /// <param name="address">Guest address</param>
133          /// <returns>Reference to the value at the specified guest <paramref name="address"/></returns>
134          /// <exception cref="ObjectDisposedException"><see cref="EntryTable{TEntry}"/> instance was disposed</exception>
135          /// <exception cref="ArgumentException"><paramref name="address"/> is not mapped</exception>
136          public ref TEntry GetValue(ulong address)
137          {
138              ObjectDisposedException.ThrowIf(_disposed, this);
139  
140              if (!IsValid(address))
141              {
142                  throw new ArgumentException($"Address 0x{address:X} is not mapped onto the table.", nameof(address));
143              }
144  
145              lock (_pages)
146              {
147                  return ref GetPage(address)[Levels[^1].GetValue(address)];
148              }
149          }
150  
151          /// <summary>
152          /// Gets the leaf page for the specified guest <paramref name="address"/>.
153          /// </summary>
154          /// <param name="address">Guest address</param>
155          /// <returns>Leaf page for the specified guest <paramref name="address"/></returns>
156          private TEntry* GetPage(ulong address)
157          {
158              TEntry** page = GetRootPage();
159  
160              for (int i = 0; i < Levels.Length - 1; i++)
161              {
162                  ref Level level = ref Levels[i];
163                  ref TEntry* nextPage = ref page[level.GetValue(address)];
164  
165                  if (nextPage == null)
166                  {
167                      ref Level nextLevel = ref Levels[i + 1];
168  
169                      nextPage = i == Levels.Length - 2 ?
170                          (TEntry*)Allocate(1 << nextLevel.Length, Fill, leaf: true) :
171                          (TEntry*)Allocate(1 << nextLevel.Length, IntPtr.Zero, leaf: false);
172                  }
173  
174                  page = (TEntry**)nextPage;
175              }
176  
177              return (TEntry*)page;
178          }
179  
180          /// <summary>
181          /// Lazily initialize and get the root page of the <see cref="AddressTable{TEntry}"/>.
182          /// </summary>
183          /// <returns>Root page of the <see cref="AddressTable{TEntry}"/></returns>
184          private TEntry** GetRootPage()
185          {
186              if (_table == null)
187              {
188                  _table = (TEntry**)Allocate(1 << Levels[0].Length, fill: IntPtr.Zero, leaf: false);
189              }
190  
191              return _table;
192          }
193  
194          /// <summary>
195          /// Allocates a block of memory of the specified type and length.
196          /// </summary>
197          /// <typeparam name="T">Type of elements</typeparam>
198          /// <param name="length">Number of elements</param>
199          /// <param name="fill">Fill value</param>
200          /// <param name="leaf"><see langword="true"/> if leaf; otherwise <see langword="false"/></param>
201          /// <returns>Allocated block</returns>
202          private IntPtr Allocate<T>(int length, T fill, bool leaf) where T : unmanaged
203          {
204              var size = sizeof(T) * length;
205              var page = (IntPtr)NativeAllocator.Instance.Allocate((uint)size);
206              var span = new Span<T>((void*)page, length);
207  
208              span.Fill(fill);
209  
210              _pages.Add(page);
211  
212              TranslatorEventSource.Log.AddressTableAllocated(size, leaf);
213  
214              return page;
215          }
216  
217          /// <summary>
218          /// Releases all resources used by the <see cref="AddressTable{TEntry}"/> instance.
219          /// </summary>
220          public void Dispose()
221          {
222              Dispose(true);
223              GC.SuppressFinalize(this);
224          }
225  
226          /// <summary>
227          /// Releases all unmanaged and optionally managed resources used by the <see cref="AddressTable{TEntry}"/>
228          /// instance.
229          /// </summary>
230          /// <param name="disposing"><see langword="true"/> to dispose managed resources also; otherwise just unmanaged resouces</param>
231          protected virtual void Dispose(bool disposing)
232          {
233              if (!_disposed)
234              {
235                  foreach (var page in _pages)
236                  {
237                      Marshal.FreeHGlobal(page);
238                  }
239  
240                  _disposed = true;
241              }
242          }
243  
244          /// <summary>
245          /// Frees resources used by the <see cref="AddressTable{TEntry}"/> instance.
246          /// </summary>
247          ~AddressTable()
248          {
249              Dispose(false);
250          }
251      }
252  }