1  using Ryujinx.Memory.Range;
  2  using System;
  3  using System.Collections.Concurrent;
  4  using System.Threading;
  5  
  6  namespace Ryujinx.Graphics.Gpu.Memory
  7  {
  8      /// <summary>
  9      /// Virtual range cache.
 10      /// </summary>
 11      class VirtualRangeCache
 12      {
 13          private readonly MemoryManager _memoryManager;
 14  
 15          /// <summary>
 16          /// Represents a GPU virtual memory range.
 17          /// </summary>
 18          private readonly struct VirtualRange : IRange
 19          {
 20              /// <summary>
 21              /// GPU virtual address where the range starts.
 22              /// </summary>
 23              public ulong Address { get; }
 24  
 25              /// <summary>
 26              /// Size of the range in bytes.
 27              /// </summary>
 28              public ulong Size { get; }
 29  
 30              /// <summary>
 31              /// GPU virtual address where the range ends.
 32              /// </summary>
 33              public ulong EndAddress => Address + Size;
 34  
 35              /// <summary>
 36              /// Physical regions where the GPU virtual region is mapped.
 37              /// </summary>
 38              public MultiRange Range { get; }
 39  
 40              /// <summary>
 41              /// Creates a new virtual memory range.
 42              /// </summary>
 43              /// <param name="address">GPU virtual address where the range starts</param>
 44              /// <param name="size">Size of the range in bytes</param>
 45              /// <param name="range">Physical regions where the GPU virtual region is mapped</param>
 46              public VirtualRange(ulong address, ulong size, MultiRange range)
 47              {
 48                  Address = address;
 49                  Size = size;
 50                  Range = range;
 51              }
 52  
 53              /// <summary>
 54              /// Checks if a given range overlaps with the buffer.
 55              /// </summary>
 56              /// <param name="address">Start address of the range</param>
 57              /// <param name="size">Size in bytes of the range</param>
 58              /// <returns>True if the range overlaps, false otherwise</returns>
 59              public bool OverlapsWith(ulong address, ulong size)
 60              {
 61                  return Address < address + size && address < EndAddress;
 62              }
 63          }
 64  
 65          private readonly RangeList<VirtualRange> _virtualRanges;
 66          private VirtualRange[] _virtualRangeOverlaps;
 67          private readonly ConcurrentQueue<VirtualRange> _deferredUnmaps;
 68          private int _hasDeferredUnmaps;
 69  
 70          /// <summary>
 71          /// Creates a new instance of the virtual range cache.
 72          /// </summary>
 73          /// <param name="memoryManager">Memory manager that the virtual range cache belongs to</param>
 74          public VirtualRangeCache(MemoryManager memoryManager)
 75          {
 76              _memoryManager = memoryManager;
 77              _virtualRanges = new RangeList<VirtualRange>();
 78              _virtualRangeOverlaps = new VirtualRange[BufferCache.OverlapsBufferInitialCapacity];
 79              _deferredUnmaps = new ConcurrentQueue<VirtualRange>();
 80          }
 81  
 82          /// <summary>
 83          /// Handles removal of buffers written to a memory region being unmapped.
 84          /// </summary>
 85          /// <param name="sender">Sender object</param>
 86          /// <param name="e">Event arguments</param>
 87          public void MemoryUnmappedHandler(object sender, UnmapEventArgs e)
 88          {
 89              void EnqueueUnmap()
 90              {
 91                  _deferredUnmaps.Enqueue(new VirtualRange(e.Address, e.Size, default));
 92  
 93                  Interlocked.Exchange(ref _hasDeferredUnmaps, 1);
 94              }
 95  
 96              e.AddRemapAction(EnqueueUnmap);
 97          }
 98  
 99          /// <summary>
100          /// Tries to get a existing, cached physical range for the specified virtual region.
101          /// If no cached range is found, a new one is created and added.
102          /// </summary>
103          /// <param name="gpuVa">GPU virtual address to get the physical range from</param>
104          /// <param name="size">Size in bytes of the region</param>
105          /// <param name="range">Physical range for the specified GPU virtual region</param>
106          /// <returns>True if the range already existed, false if a new one was created and added</returns>
107          public bool TryGetOrAddRange(ulong gpuVa, ulong size, out MultiRange range)
108          {
109              VirtualRange[] overlaps = _virtualRangeOverlaps;
110              int overlapsCount;
111  
112              if (Interlocked.Exchange(ref _hasDeferredUnmaps, 0) != 0)
113              {
114                  while (_deferredUnmaps.TryDequeue(out VirtualRange unmappedRange))
115                  {
116                      overlapsCount = _virtualRanges.FindOverlapsNonOverlapping(unmappedRange.Address, unmappedRange.Size, ref overlaps);
117  
118                      for (int index = 0; index < overlapsCount; index++)
119                      {
120                          _virtualRanges.Remove(overlaps[index]);
121                      }
122                  }
123              }
124  
125              bool found = false;
126  
127              ulong originalVa = gpuVa;
128  
129              overlapsCount = _virtualRanges.FindOverlapsNonOverlapping(gpuVa, size, ref overlaps);
130  
131              if (overlapsCount != 0)
132              {
133                  // The virtual range already exists. We just need to check if our range fits inside
134                  // the existing one, and if not, we must extend the existing one.
135  
136                  ulong endAddress = gpuVa + size;
137                  VirtualRange overlap0 = overlaps[0];
138  
139                  if (overlap0.Address > gpuVa || overlap0.EndAddress < endAddress)
140                  {
141                      for (int index = 0; index < overlapsCount; index++)
142                      {
143                          VirtualRange virtualRange = overlaps[index];
144  
145                          gpuVa = Math.Min(gpuVa, virtualRange.Address);
146                          endAddress = Math.Max(endAddress, virtualRange.EndAddress);
147  
148                          _virtualRanges.Remove(virtualRange);
149                      }
150  
151                      ulong newSize = endAddress - gpuVa;
152                      MultiRange newRange = _memoryManager.GetPhysicalRegions(gpuVa, newSize);
153  
154                      _virtualRanges.Add(new(gpuVa, newSize, newRange));
155  
156                      range = newRange.Slice(originalVa - gpuVa, size);
157                  }
158                  else
159                  {
160                      found = overlap0.Range.Count == 1 || IsSparseAligned(overlap0.Range);
161                      range = overlap0.Range.Slice(gpuVa - overlap0.Address, size);
162                  }
163              }
164              else
165              {
166                  // No overlap, just create a new virtual range.
167                  range = _memoryManager.GetPhysicalRegions(gpuVa, size);
168  
169                  VirtualRange virtualRange = new(gpuVa, size, range);
170  
171                  _virtualRanges.Add(virtualRange);
172              }
173  
174              ShrinkOverlapsBufferIfNeeded();
175  
176              // If the range is not properly aligned for sparse mapping,
177              // let's just force it to a single range.
178              // This might cause issues in some applications that uses sparse
179              // mappings.
180              if (!IsSparseAligned(range))
181              {
182                  range = new MultiRange(range.GetSubRange(0).Address, size);
183              }
184  
185              return found;
186          }
187  
188          /// <summary>
189          /// Checks if the physical memory ranges are valid for sparse mapping,
190          /// which requires all sub-ranges to be 64KB aligned.
191          /// </summary>
192          /// <param name="range">Range to check</param>
193          /// <returns>True if the range is valid for sparse mapping, false otherwise</returns>
194          private static bool IsSparseAligned(MultiRange range)
195          {
196              if (range.Count == 1)
197              {
198                  return (range.GetSubRange(0).Address & (BufferCache.SparseBufferAlignmentSize - 1)) == 0;
199              }
200  
201              for (int i = 0; i < range.Count; i++)
202              {
203                  MemoryRange subRange = range.GetSubRange(i);
204  
205                  // Check if address is aligned. The address of the first sub-range can
206                  // be misaligned as it is at the start.
207                  if (i > 0 &&
208                      subRange.Address != MemoryManager.PteUnmapped &&
209                      (subRange.Address & (BufferCache.SparseBufferAlignmentSize - 1)) != 0)
210                  {
211                      return false;
212                  }
213  
214                  // Check if the size is aligned. The size of the last sub-range can
215                  // be misaligned as it is at the end.
216                  if (i < range.Count - 1 && (subRange.Size & (BufferCache.SparseBufferAlignmentSize - 1)) != 0)
217                  {
218                      return false;
219                  }
220              }
221  
222              return true;
223          }
224  
225          /// <summary>
226          /// Resizes the temporary buffer used for range list intersection results, if it has grown too much.
227          /// </summary>
228          private void ShrinkOverlapsBufferIfNeeded()
229          {
230              if (_virtualRangeOverlaps.Length > BufferCache.OverlapsBufferMaxCapacity)
231              {
232                  Array.Resize(ref _virtualRangeOverlaps, BufferCache.OverlapsBufferMaxCapacity);
233              }
234          }
235      }
236  }