1  using NUnit.Framework;
  2  using Ryujinx.Memory;
  3  using Ryujinx.Memory.Tracking;
  4  using System;
  5  using System.Collections.Generic;
  6  using System.Linq;
  7  
  8  namespace Ryujinx.Tests.Memory
  9  {
 10      public class MultiRegionTrackingTests
 11      {
 12          private const ulong MemorySize = 0x8000;
 13          private const int PageSize = 4096;
 14  
 15          private MemoryBlock _memoryBlock;
 16          private MemoryTracking _tracking;
 17          private MockVirtualMemoryManager _memoryManager;
 18  
 19          [SetUp]
 20          public void Setup()
 21          {
 22              _memoryBlock = new MemoryBlock(MemorySize);
 23              _memoryManager = new MockVirtualMemoryManager(MemorySize, PageSize);
 24              _tracking = new MemoryTracking(_memoryManager, PageSize);
 25          }
 26  
 27          [TearDown]
 28          public void Teardown()
 29          {
 30              _memoryBlock.Dispose();
 31          }
 32  
 33          private IMultiRegionHandle GetGranular(bool smart, ulong address, ulong size, ulong granularity)
 34          {
 35              return smart ?
 36                  _tracking.BeginSmartGranularTracking(address, size, granularity, 0) :
 37                  (IMultiRegionHandle)_tracking.BeginGranularTracking(address, size, null, granularity, 0);
 38          }
 39  
 40          private static void RandomOrder(Random random, List<int> indices, Action<int> action)
 41          {
 42              List<int> choices = indices.ToList();
 43  
 44              while (choices.Count > 0)
 45              {
 46                  int choice = random.Next(choices.Count);
 47                  action(choices[choice]);
 48                  choices.RemoveAt(choice);
 49              }
 50          }
 51  
 52          private static int ExpectQueryInOrder(IMultiRegionHandle handle, ulong startAddress, ulong size, Func<ulong, bool> addressPredicate)
 53          {
 54              int regionCount = 0;
 55              ulong lastAddress = startAddress;
 56  
 57              handle.QueryModified(startAddress, size, (address, range) =>
 58              {
 59                  Assert.IsTrue(addressPredicate(address)); // Written pages must be even.
 60                  Assert.GreaterOrEqual(address, lastAddress); // Must be signalled in ascending order, regardless of write order.
 61                  lastAddress = address;
 62                  regionCount++;
 63              });
 64  
 65              return regionCount;
 66          }
 67  
 68          private static int ExpectQueryInOrder(IMultiRegionHandle handle, ulong startAddress, ulong size, Func<ulong, bool> addressPredicate, int sequenceNumber)
 69          {
 70              int regionCount = 0;
 71              ulong lastAddress = startAddress;
 72  
 73              handle.QueryModified(startAddress, size, (address, range) =>
 74              {
 75                  Assert.IsTrue(addressPredicate(address)); // Written pages must be even.
 76                  Assert.GreaterOrEqual(address, lastAddress); // Must be signalled in ascending order, regardless of write order.
 77                  lastAddress = address;
 78                  regionCount++;
 79              }, sequenceNumber);
 80  
 81              return regionCount;
 82          }
 83  
 84          private static void PreparePages(IMultiRegionHandle handle, int pageCount, ulong address = 0)
 85          {
 86              Random random = new();
 87  
 88              // Make sure the list has minimum granularity (smart region changes granularity based on requested ranges)
 89              RandomOrder(random, Enumerable.Range(0, pageCount).ToList(), (i) =>
 90              {
 91                  ulong resultAddress = ulong.MaxValue;
 92                  handle.QueryModified((ulong)i * PageSize + address, PageSize, (address, range) =>
 93                  {
 94                      resultAddress = address;
 95                  });
 96                  Assert.AreEqual(resultAddress, (ulong)i * PageSize + address);
 97              });
 98          }
 99  
100          [Test]
101          public void DirtyRegionOrdering([Values] bool smart)
102          {
103              const int PageCount = 32;
104              IMultiRegionHandle handle = GetGranular(smart, 0, PageSize * PageCount, PageSize);
105  
106              Random random = new();
107  
108              PreparePages(handle, PageCount);
109  
110              IEnumerable<int> halfRange = Enumerable.Range(0, PageCount / 2);
111              List<int> odd = halfRange.Select(x => x * 2 + 1).ToList();
112              List<int> even = halfRange.Select(x => x * 2).ToList();
113  
114              // Write to all the odd pages.
115              RandomOrder(random, odd, (i) =>
116              {
117                  _tracking.VirtualMemoryEvent((ulong)i * PageSize, PageSize, true);
118              });
119  
120              int oddRegionCount = ExpectQueryInOrder(handle, 0, PageSize * PageCount, (address) => (address / PageSize) % 2 == 1);
121  
122              Assert.AreEqual(oddRegionCount, PageCount / 2); // Must have written to all odd pages.
123  
124              // Write to all the even pages.
125              RandomOrder(random, even, (i) =>
126              {
127                  _tracking.VirtualMemoryEvent((ulong)i * PageSize, PageSize, true);
128              });
129  
130              int evenRegionCount = ExpectQueryInOrder(handle, 0, PageSize * PageCount, (address) => (address / PageSize) % 2 == 0);
131  
132              Assert.AreEqual(evenRegionCount, PageCount / 2);
133          }
134  
135          [Test]
136          public void SequenceNumber([Values] bool smart)
137          {
138              // The sequence number can be used to ignore dirty flags, and defer their consumption until later.
139              // If a user consumes a dirty flag with sequence number 1, then there is a write to the protected region,
140              // the dirty flag will not be acknowledged until the sequence number is 2.
141  
142              // This is useful for situations where we know that the data was complete when the sequence number was set.
143              // ...essentially, when that data can only be updated on a future sequence number.
144  
145              const int PageCount = 32;
146              IMultiRegionHandle handle = GetGranular(smart, 0, PageSize * PageCount, PageSize);
147  
148              PreparePages(handle, PageCount);
149  
150              Random random = new();
151  
152              IEnumerable<int> halfRange = Enumerable.Range(0, PageCount / 2);
153              List<int> odd = halfRange.Select(x => x * 2 + 1).ToList();
154              List<int> even = halfRange.Select(x => x * 2).ToList();
155  
156              // Write to all the odd pages.
157              RandomOrder(random, odd, (i) =>
158              {
159                  _tracking.VirtualMemoryEvent((ulong)i * PageSize, PageSize, true);
160              });
161  
162              int oddRegionCount = 0;
163  
164              // Track with sequence number 1. Future dirty flags should only be consumed with sequence number != 1.
165              // Only track the odd pages, so the even ones don't have their sequence number set.
166  
167              foreach (int index in odd)
168              {
169                  handle.QueryModified((ulong)index * PageSize, PageSize, (address, range) =>
170                  {
171                      oddRegionCount++;
172                  }, 1);
173              }
174  
175              Assert.AreEqual(oddRegionCount, PageCount / 2); // Must have written to all odd pages.
176  
177              // Write to all pages.
178  
179              _tracking.VirtualMemoryEvent(0, PageSize * PageCount, true);
180  
181              // Only the even regions should be reported for sequence number 1.
182  
183              int evenRegionCount = ExpectQueryInOrder(handle, 0, PageSize * PageCount, (address) => (address / PageSize) % 2 == 0, 1);
184  
185              Assert.AreEqual(evenRegionCount, PageCount / 2); // Must have written to all even pages.
186  
187              oddRegionCount = 0;
188  
189              handle.QueryModified(0, PageSize * PageCount, (address, range) => { oddRegionCount++; }, 1);
190  
191              Assert.AreEqual(oddRegionCount, 0); // Sequence number has not changed, so found no dirty subregions.
192  
193              // With sequence number 2, all all pages should be reported as modified.
194  
195              oddRegionCount = ExpectQueryInOrder(handle, 0, PageSize * PageCount, (address) => (address / PageSize) % 2 == 1, 2);
196  
197              Assert.AreEqual(oddRegionCount, PageCount / 2); // Must have written to all odd pages.
198          }
199  
200          [Test]
201          public void SmartRegionTracking()
202          {
203              // Smart multi region handles dynamically change their tracking granularity based on QueryMemory calls.
204              // This can save on reprotects on larger resources.
205  
206              const int PageCount = 32;
207              IMultiRegionHandle handle = GetGranular(true, 0, PageSize * PageCount, PageSize);
208  
209              // Query some large regions to prep the subdivision of the tracking region.
210  
211              int[] regionSizes = new int[] { 6, 4, 3, 2, 6, 1 };
212              ulong address = 0;
213  
214              for (int i = 0; i < regionSizes.Length; i++)
215              {
216                  int region = regionSizes[i];
217                  handle.QueryModified(address, (ulong)(PageSize * region), (address, size) => { });
218  
219                  // There should be a gap between regions,
220                  // So that they don't combine and we can see the full effects.
221                  address += (ulong)(PageSize * (region + 1));
222              }
223  
224              // Clear modified.
225              handle.QueryModified((address, size) => { });
226  
227              // Trigger each region with a 1 byte write.
228              address = 0;
229  
230              for (int i = 0; i < regionSizes.Length; i++)
231              {
232                  int region = regionSizes[i];
233                  _tracking.VirtualMemoryEvent(address, 1, true);
234                  address += (ulong)(PageSize * (region + 1));
235              }
236  
237              int regionInd = 0;
238              ulong expectedAddress = 0;
239  
240              // Expect each region to trigger in its entirety, in address ascending order.
241              handle.QueryModified((address, size) =>
242              {
243                  int region = regionSizes[regionInd++];
244  
245                  Assert.AreEqual(address, expectedAddress);
246                  Assert.AreEqual(size, (ulong)(PageSize * region));
247  
248                  expectedAddress += (ulong)(PageSize * (region + 1));
249              });
250          }
251  
252          [Test]
253          public void DisposeMultiHandles([Values] bool smart)
254          {
255              // Create and initialize two overlapping Multi Region Handles, with PageSize granularity.
256              const int PageCount = 32;
257              const int OverlapStart = 16;
258  
259              Assert.AreEqual(0, _tracking.GetRegionCount());
260  
261              IMultiRegionHandle handleLow = GetGranular(smart, 0, PageSize * PageCount, PageSize);
262              PreparePages(handleLow, PageCount);
263  
264              Assert.AreEqual(PageCount, _tracking.GetRegionCount());
265  
266              IMultiRegionHandle handleHigh = GetGranular(smart, PageSize * OverlapStart, PageSize * PageCount, PageSize);
267              PreparePages(handleHigh, PageCount, PageSize * OverlapStart);
268  
269              // Combined pages (and assuming overlapStart <= pageCount) should be pageCount after overlapStart.
270              int totalPages = OverlapStart + PageCount;
271  
272              Assert.AreEqual(totalPages, _tracking.GetRegionCount());
273  
274              handleLow.Dispose(); // After disposing one, the pages for the other remain.
275  
276              Assert.AreEqual(PageCount, _tracking.GetRegionCount());
277  
278              handleHigh.Dispose(); // After disposing the other, there are no pages left.
279  
280              Assert.AreEqual(0, _tracking.GetRegionCount());
281          }
282  
283          [Test]
284          public void InheritHandles()
285          {
286              // Test merging the following into a granular region handle:
287              // - 3x gap (creates new granular handles)
288              // - 3x from multiregion: not dirty, dirty and with action
289              // - 2x gap
290              // - 3x single page: not dirty, dirty and with action
291              // - 3x two page: not dirty, dirty and with action (handle is not reused, but its state is copied to the granular handles)
292              // - 1x gap
293              // For a total of 18 pages.
294  
295              bool[] actionsTriggered = new bool[3];
296  
297              MultiRegionHandle granular = _tracking.BeginGranularTracking(PageSize * 3, PageSize * 3, null, PageSize, 0);
298              PreparePages(granular, 3, PageSize * 3);
299  
300              // Write to the second handle in the multiregion.
301              _tracking.VirtualMemoryEvent(PageSize * 4, PageSize, true);
302  
303              // Add an action to the third handle in the multiregion.
304              granular.RegisterAction(PageSize * 5, PageSize, (_, _) => { actionsTriggered[0] = true; });
305  
306              RegionHandle[] singlePages = new RegionHandle[3];
307  
308              for (int i = 0; i < 3; i++)
309              {
310                  singlePages[i] = _tracking.BeginTracking(PageSize * (8 + (ulong)i), PageSize, 0);
311                  singlePages[i].Reprotect();
312              }
313  
314              // Write to the second handle.
315              _tracking.VirtualMemoryEvent(PageSize * 9, PageSize, true);
316  
317              // Add an action to the third handle.
318              singlePages[2].RegisterAction((_, _) => { actionsTriggered[1] = true; });
319  
320              RegionHandle[] doublePages = new RegionHandle[3];
321  
322              for (int i = 0; i < 3; i++)
323              {
324                  doublePages[i] = _tracking.BeginTracking(PageSize * (11 + (ulong)i * 2), PageSize * 2, 0);
325                  doublePages[i].Reprotect();
326              }
327  
328              // Write to the second handle.
329              _tracking.VirtualMemoryEvent(PageSize * 13, PageSize * 2, true);
330  
331              // Add an action to the third handle.
332              doublePages[2].RegisterAction((_, _) => { actionsTriggered[2] = true; });
333  
334              // Finally, create a granular handle that inherits all these handles.
335  
336              IEnumerable<IRegionHandle>[] handleGroups = new IEnumerable<IRegionHandle>[]
337              {
338                  granular.GetHandles(),
339                  singlePages,
340                  doublePages,
341              };
342  
343              MultiRegionHandle combined = _tracking.BeginGranularTracking(0, PageSize * 18, handleGroups.SelectMany((handles) => handles), PageSize, 0);
344  
345              bool[] expectedDirty = new bool[]
346              {
347                  true, true, true, // Gap.
348                  false, true, false, // Multi-region.
349                  true, true, // Gap.
350                  false, true, false, // Individual handles.
351                  false, false, true, true, false, false, // Double size handles.
352                  true, // Gap.
353              };
354  
355              for (int i = 0; i < 18; i++)
356              {
357                  bool modified = false;
358                  combined.QueryModified(PageSize * (ulong)i, PageSize, (_, _) => { modified = true; });
359  
360                  Assert.AreEqual(expectedDirty[i], modified);
361              }
362  
363              Assert.AreEqual(new bool[3], actionsTriggered);
364  
365              _tracking.VirtualMemoryEvent(PageSize * 5, PageSize, false);
366              Assert.IsTrue(actionsTriggered[0]);
367  
368              _tracking.VirtualMemoryEvent(PageSize * 10, PageSize, false);
369              Assert.IsTrue(actionsTriggered[1]);
370  
371              _tracking.VirtualMemoryEvent(PageSize * 15, PageSize, false);
372              Assert.IsTrue(actionsTriggered[2]);
373  
374              // The double page handles should be disposed, as they were split into granular handles.
375              foreach (RegionHandle doublePage in doublePages)
376              {
377                  // These should have been disposed.
378                  bool throws = false;
379  
380                  try
381                  {
382                      doublePage.Dispose();
383                  }
384                  catch (ObjectDisposedException)
385                  {
386                      throws = true;
387                  }
388  
389                  Assert.IsTrue(throws);
390              }
391  
392              IEnumerable<IRegionHandle> combinedHandles = combined.GetHandles();
393  
394              Assert.AreEqual(handleGroups[0].ElementAt(0), combinedHandles.ElementAt(3));
395              Assert.AreEqual(handleGroups[0].ElementAt(1), combinedHandles.ElementAt(4));
396              Assert.AreEqual(handleGroups[0].ElementAt(2), combinedHandles.ElementAt(5));
397  
398              Assert.AreEqual(singlePages[0], combinedHandles.ElementAt(8));
399              Assert.AreEqual(singlePages[1], combinedHandles.ElementAt(9));
400              Assert.AreEqual(singlePages[2], combinedHandles.ElementAt(10));
401          }
402  
403          [Test]
404          public void PreciseAction()
405          {
406              bool actionTriggered = false;
407  
408              MultiRegionHandle granular = _tracking.BeginGranularTracking(PageSize * 3, PageSize * 3, null, PageSize, 0);
409              PreparePages(granular, 3, PageSize * 3);
410  
411              // Add a precise action to the second and third handle in the multiregion.
412              granular.RegisterPreciseAction(PageSize * 4, PageSize * 2, (_, _, _) => { actionTriggered = true; return true; });
413  
414              // Precise write to first handle in the multiregion.
415              _tracking.VirtualMemoryEvent(PageSize * 3, PageSize, true, precise: true);
416              Assert.IsFalse(actionTriggered); // Action not triggered.
417  
418              bool firstPageModified = false;
419              granular.QueryModified(PageSize * 3, PageSize, (_, _) => { firstPageModified = true; });
420              Assert.IsTrue(firstPageModified); // First page is modified.
421  
422              // Precise write to all handles in the multiregion.
423              _tracking.VirtualMemoryEvent(PageSize * 3, PageSize * 3, true, precise: true);
424  
425              bool[] pagesModified = new bool[3];
426  
427              for (int i = 3; i < 6; i++)
428              {
429                  int index = i - 3;
430                  granular.QueryModified(PageSize * (ulong)i, PageSize, (_, _) => { pagesModified[index] = true; });
431              }
432  
433              Assert.IsTrue(actionTriggered); // Action triggered.
434  
435              // Precise writes are ignored on two later handles due to the action returning true.
436              Assert.AreEqual(pagesModified, new bool[] { true, false, false });
437          }
438      }
439  }