1  using Ryujinx.Cpu.AppleHv.Arm;
  2  using System;
  3  using System.Diagnostics;
  4  using System.Runtime.InteropServices;
  5  using System.Runtime.Versioning;
  6  using System.Threading;
  7  
  8  namespace Ryujinx.Cpu.AppleHv
  9  {
 10      [SupportedOSPlatform("macos")]
 11      class HvAddressSpaceRange : IDisposable
 12      {
 13          private const ulong AllocationGranule = 1UL << 14;
 14  
 15          private const ulong AttributesMask = (0x3ffUL << 2) | (0x3fffUL << 50);
 16  
 17          private const ulong BaseAttributes = (1UL << 10) | (3UL << 8); // Access flag set, inner shareable.
 18  
 19          private const int LevelBits = 9;
 20          private const int LevelCount = 1 << LevelBits;
 21          private const int LevelMask = LevelCount - 1;
 22          private const int PageBits = 12;
 23          private const int PageSize = 1 << PageBits;
 24          private const int PageMask = PageSize - 1;
 25          private const int AllLevelsMask = PageMask | (LevelMask << PageBits) | (LevelMask << (PageBits + LevelBits));
 26  
 27          private class PtLevel
 28          {
 29              public ulong Address => Allocation.Ipa + Allocation.Offset;
 30              public int EntriesCount;
 31              public readonly HvMemoryBlockAllocation Allocation;
 32              public readonly PtLevel[] Next;
 33  
 34              public PtLevel(HvMemoryBlockAllocator blockAllocator, int count, bool hasNext)
 35              {
 36                  ulong size = (ulong)count * sizeof(ulong);
 37                  Allocation = blockAllocator.Allocate(size, PageSize);
 38  
 39                  AsSpan().Clear();
 40  
 41                  if (hasNext)
 42                  {
 43                      Next = new PtLevel[count];
 44                  }
 45              }
 46  
 47              public Span<ulong> AsSpan()
 48              {
 49                  return MemoryMarshal.Cast<byte, ulong>(Allocation.Memory.GetSpan(Allocation.Offset, (int)Allocation.Size));
 50              }
 51          }
 52  
 53          private PtLevel _level0;
 54  
 55          private int _tlbInvalidationPending;
 56  
 57          private readonly HvMemoryBlockAllocator _blockAllocator;
 58  
 59          public HvAddressSpaceRange(HvIpaAllocator ipaAllocator)
 60          {
 61              _blockAllocator = new HvMemoryBlockAllocator(ipaAllocator, (int)AllocationGranule);
 62          }
 63  
 64          public ulong GetIpaBase()
 65          {
 66              return EnsureLevel0().Address;
 67          }
 68  
 69          public bool GetAndClearTlbInvalidationPending()
 70          {
 71              return Interlocked.Exchange(ref _tlbInvalidationPending, 0) != 0;
 72          }
 73  
 74          public void Map(ulong va, ulong pa, ulong size, ApFlags accessPermission)
 75          {
 76              MapImpl(va, pa, size, (ulong)accessPermission | BaseAttributes);
 77          }
 78  
 79          public void Unmap(ulong va, ulong size)
 80          {
 81              UnmapImpl(EnsureLevel0(), 0, va, size);
 82              Interlocked.Exchange(ref _tlbInvalidationPending, 1);
 83          }
 84  
 85          public void Reprotect(ulong va, ulong size, ApFlags accessPermission)
 86          {
 87              UpdateAttributes(va, size, (ulong)accessPermission | BaseAttributes);
 88          }
 89  
 90          private void MapImpl(ulong va, ulong pa, ulong size, ulong attr)
 91          {
 92              PtLevel level0 = EnsureLevel0();
 93  
 94              ulong endVa = va + size;
 95  
 96              while (va < endVa)
 97              {
 98                  (ulong mapSize, int depth) = GetMapSizeAndDepth(va, pa, endVa);
 99  
100                  PtLevel currentLevel = level0;
101  
102                  for (int i = 0; i < depth; i++)
103                  {
104                      int l = (int)(va >> (PageBits + (2 - i) * LevelBits)) & LevelMask;
105                      EnsureTable(currentLevel, l, i == 0);
106                      currentLevel = currentLevel.Next[l];
107                  }
108  
109                  (ulong blockSize, int blockShift) = GetBlockSizeAndShift(depth);
110  
111                  for (ulong i = 0; i < mapSize; i += blockSize)
112                  {
113                      if ((va >> blockShift) << blockShift != va ||
114                          (pa >> blockShift) << blockShift != pa)
115                      {
116                          Debug.Fail($"Block size 0x{blockSize:X} (log2: {blockShift}) is invalid for VA 0x{va:X} or PA 0x{pa:X}.");
117                      }
118  
119                      WriteBlock(currentLevel, (int)(va >> blockShift) & LevelMask, depth, pa, attr);
120  
121                      va += blockSize;
122                      pa += blockSize;
123                  }
124              }
125          }
126  
127          private void UnmapImpl(PtLevel level, int depth, ulong va, ulong size)
128          {
129              ulong endVa = (va + size + PageMask) & ~((ulong)PageMask);
130              va &= ~((ulong)PageMask);
131  
132              (ulong blockSize, _) = GetBlockSizeAndShift(depth);
133  
134              while (va < endVa)
135              {
136                  ulong nextEntryVa = GetNextAddress(va, blockSize);
137                  ulong chunckSize = Math.Min(endVa - va, nextEntryVa - va);
138  
139                  int l = (int)(va >> (PageBits + (2 - depth) * LevelBits)) & LevelMask;
140  
141                  PtLevel nextTable = level.Next?[l];
142  
143                  if (nextTable != null)
144                  {
145                      // Entry is a table, visit it and update attributes as required.
146                      UnmapImpl(nextTable, depth + 1, va, chunckSize);
147                  }
148                  else if (chunckSize != blockSize)
149                  {
150                      // Entry is a block but is not aligned, we need to turn it into a table.
151                      ref ulong pte = ref level.AsSpan()[l];
152                      nextTable = CreateTable(pte, depth + 1);
153                      level.Next[l] = nextTable;
154  
155                      // Now that we have a table, we can handle it like the first case.
156                      UnmapImpl(nextTable, depth + 1, va, chunckSize);
157  
158                      // Update PTE to point to the new table.
159                      pte = (nextTable.Address & ~(ulong)PageMask) | 3UL;
160                  }
161  
162                  // If entry is a block, or if entry is a table but it is empty, we can remove it.
163                  if (nextTable == null || nextTable.EntriesCount == 0)
164                  {
165                      // Entry is a block and is fully aligned, so we can just set it to 0.
166                      if (nextTable != null)
167                      {
168                          nextTable.Allocation.Dispose();
169                          level.Next[l] = null;
170                      }
171  
172                      level.AsSpan()[l] = 0UL;
173                      level.EntriesCount--;
174                      ValidateEntriesCount(level.EntriesCount);
175                  }
176  
177                  va += chunckSize;
178              }
179          }
180  
181          private void UpdateAttributes(ulong va, ulong size, ulong newAttr)
182          {
183              UpdateAttributes(EnsureLevel0(), 0, va, size, newAttr);
184  
185              Interlocked.Exchange(ref _tlbInvalidationPending, 1);
186          }
187  
188          private void UpdateAttributes(PtLevel level, int depth, ulong va, ulong size, ulong newAttr)
189          {
190              ulong endVa = (va + size + PageSize - 1) & ~((ulong)PageSize - 1);
191              va &= ~((ulong)PageSize - 1);
192  
193              (ulong blockSize, _) = GetBlockSizeAndShift(depth);
194  
195              while (va < endVa)
196              {
197                  ulong nextEntryVa = GetNextAddress(va, blockSize);
198                  ulong chunckSize = Math.Min(endVa - va, nextEntryVa - va);
199  
200                  int l = (int)(va >> (PageBits + (2 - depth) * LevelBits)) & LevelMask;
201  
202                  ref ulong pte = ref level.AsSpan()[l];
203  
204                  // First check if the region is mapped.
205                  if ((pte & 3) != 0)
206                  {
207                      PtLevel nextTable = level.Next?[l];
208  
209                      if (nextTable != null)
210                      {
211                          // Entry is a table, visit it and update attributes as required.
212                          UpdateAttributes(nextTable, depth + 1, va, chunckSize, newAttr);
213                      }
214                      else if (chunckSize != blockSize)
215                      {
216                          // Entry is a block but is not aligned, we need to turn it into a table.
217                          nextTable = CreateTable(pte, depth + 1);
218                          level.Next[l] = nextTable;
219  
220                          // Now that we have a table, we can handle it like the first case.
221                          UpdateAttributes(nextTable, depth + 1, va, chunckSize, newAttr);
222  
223                          // Update PTE to point to the new table.
224                          pte = (nextTable.Address & ~(ulong)PageMask) | 3UL;
225                      }
226                      else
227                      {
228                          // Entry is a block and is fully aligned, so we can just update the attributes.
229                          // Update PTE with the new attributes.
230                          pte = (pte & ~AttributesMask) | newAttr;
231                      }
232                  }
233  
234                  va += chunckSize;
235              }
236          }
237  
238          private PtLevel CreateTable(ulong pte, int depth)
239          {
240              pte &= ~3UL;
241              pte |= (depth == 2 ? 3UL : 1UL);
242  
243              PtLevel level = new(_blockAllocator, LevelCount, depth < 2);
244              Span<ulong> currentLevel = level.AsSpan();
245  
246              (_, int blockShift) = GetBlockSizeAndShift(depth);
247  
248              // Fill in the blocks.
249              for (int i = 0; i < LevelCount; i++)
250              {
251                  ulong offset = (ulong)i << blockShift;
252                  currentLevel[i] = pte + offset;
253              }
254  
255              level.EntriesCount = LevelCount;
256  
257              return level;
258          }
259  
260          private static (ulong, int) GetBlockSizeAndShift(int depth)
261          {
262              int blockShift = PageBits + (2 - depth) * LevelBits;
263              ulong blockSize = 1UL << blockShift;
264  
265              return (blockSize, blockShift);
266          }
267  
268          private static (ulong, int) GetMapSizeAndDepth(ulong va, ulong pa, ulong endVa)
269          {
270              // Both virtual and physical addresses must be aligned to the block size.
271              ulong combinedAddress = va | pa;
272  
273              ulong l0Alignment = 1UL << (PageBits + LevelBits * 2);
274              ulong l1Alignment = 1UL << (PageBits + LevelBits);
275  
276              if ((combinedAddress & (l0Alignment - 1)) == 0 && AlignDown(endVa, l0Alignment) > va)
277              {
278                  return (AlignDown(endVa, l0Alignment) - va, 0);
279              }
280              else if ((combinedAddress & (l1Alignment - 1)) == 0 && AlignDown(endVa, l1Alignment) > va)
281              {
282                  ulong nextOrderVa = GetNextAddress(va, l0Alignment);
283  
284                  if (nextOrderVa <= endVa)
285                  {
286                      return (nextOrderVa - va, 1);
287                  }
288                  else
289                  {
290                      return (AlignDown(endVa, l1Alignment) - va, 1);
291                  }
292              }
293              else
294              {
295                  ulong nextOrderVa = GetNextAddress(va, l1Alignment);
296  
297                  if (nextOrderVa <= endVa)
298                  {
299                      return (nextOrderVa - va, 2);
300                  }
301                  else
302                  {
303                      return (endVa - va, 2);
304                  }
305              }
306          }
307  
308          private static ulong AlignDown(ulong va, ulong alignment)
309          {
310              return va & ~(alignment - 1);
311          }
312  
313          private static ulong GetNextAddress(ulong va, ulong alignment)
314          {
315              return (va + alignment) & ~(alignment - 1);
316          }
317  
318          private PtLevel EnsureLevel0()
319          {
320              PtLevel level0 = _level0;
321  
322              if (level0 == null)
323              {
324                  level0 = new PtLevel(_blockAllocator, LevelCount, true);
325                  _level0 = level0;
326              }
327  
328              return level0;
329          }
330  
331          private void EnsureTable(PtLevel level, int index, bool hasNext)
332          {
333              Span<ulong> currentTable = level.AsSpan();
334  
335              if ((currentTable[index] & 1) == 0)
336              {
337                  PtLevel nextLevel = new(_blockAllocator, LevelCount, hasNext);
338  
339                  currentTable[index] = (nextLevel.Address & ~(ulong)PageMask) | 3UL;
340                  level.Next[index] = nextLevel;
341                  level.EntriesCount++;
342                  ValidateEntriesCount(level.EntriesCount);
343              }
344              else if (level.Next[index] == null)
345              {
346                  Debug.Fail($"Index {index} is block, expected a table.");
347              }
348          }
349  
350          private static void WriteBlock(PtLevel level, int index, int depth, ulong pa, ulong attr)
351          {
352              Span<ulong> currentTable = level.AsSpan();
353  
354              currentTable[index] = (pa & ~((ulong)AllLevelsMask >> (depth * LevelBits))) | (depth == 2 ? 3UL : 1UL) | attr;
355  
356              level.EntriesCount++;
357              ValidateEntriesCount(level.EntriesCount);
358          }
359  
360          private static void ValidateEntriesCount(int count)
361          {
362              Debug.Assert(count >= 0 && count <= LevelCount, $"Entries count {count} is invalid.");
363          }
364  
365          public void Dispose()
366          {
367              _blockAllocator.Dispose();
368          }
369      }
370  }