1  using System;
  2  using System.Runtime.CompilerServices;
  3  
  4  namespace Ryujinx.Memory.Tracking
  5  {
  6      /// <summary>
  7      /// A MultiRegionHandle that attempts to segment a region's handles into the regions requested
  8      /// to avoid iterating over granular chunks for canonically large regions.
  9      /// If minimum granularity is to be expected, use MultiRegionHandle.
 10      /// </summary>
 11      public class SmartMultiRegionHandle : IMultiRegionHandle
 12      {
 13          /// <summary>
 14          /// A list of region handles starting at each granularity size increment.
 15          /// </summary>
 16          private readonly RegionHandle[] _handles;
 17          private readonly ulong _address;
 18          private readonly ulong _granularity;
 19          private readonly ulong _size;
 20          private readonly MemoryTracking _tracking;
 21          private readonly int _id;
 22  
 23          public bool Dirty { get; private set; } = true;
 24  
 25          internal SmartMultiRegionHandle(MemoryTracking tracking, ulong address, ulong size, ulong granularity, int id)
 26          {
 27              // For this multi-region handle, the handle list starts empty.
 28              // As regions are queried, they are added to the _handles array at their start index.
 29              // When a region being added overlaps another, the existing region is split.
 30              // A query can therefore scan multiple regions, though with no overlaps they can cover a large area.
 31  
 32              _tracking = tracking;
 33              _handles = new RegionHandle[size / granularity];
 34              _granularity = granularity;
 35  
 36              _address = address;
 37              _size = size;
 38              _id = id;
 39          }
 40  
 41          public void SignalWrite()
 42          {
 43              Dirty = true;
 44          }
 45  
 46          public void ForceDirty(ulong address, ulong size)
 47          {
 48              foreach (var handle in _handles)
 49              {
 50                  if (handle != null && handle.OverlapsWith(address, size))
 51                  {
 52                      handle.ForceDirty();
 53                  }
 54              }
 55          }
 56  
 57          public void RegisterAction(RegionSignal action)
 58          {
 59              foreach (var handle in _handles)
 60              {
 61                  if (handle != null)
 62                  {
 63                      handle?.RegisterAction((address, size) => action(handle.Address, handle.Size));
 64                  }
 65              }
 66          }
 67  
 68          public void RegisterPreciseAction(PreciseRegionSignal action)
 69          {
 70              foreach (var handle in _handles)
 71              {
 72                  if (handle != null)
 73                  {
 74                      handle?.RegisterPreciseAction((address, size, write) => action(handle.Address, handle.Size, write));
 75                  }
 76              }
 77          }
 78  
 79          public void QueryModified(Action<ulong, ulong> modifiedAction)
 80          {
 81              if (!Dirty)
 82              {
 83                  return;
 84              }
 85  
 86              Dirty = false;
 87  
 88              QueryModified(_address, _size, modifiedAction);
 89          }
 90  
 91          [MethodImpl(MethodImplOptions.AggressiveInlining)]
 92          private ulong HandlesToBytes(int handles)
 93          {
 94              return (ulong)handles * _granularity;
 95          }
 96  
 97          private void SplitHandle(int handleIndex, int splitIndex)
 98          {
 99              RegionHandle handle = _handles[handleIndex];
100              ulong address = _address + HandlesToBytes(handleIndex);
101              ulong size = HandlesToBytes(splitIndex - handleIndex);
102  
103              // First, the target handle must be removed. Its data can still be used to determine the new handles.
104              RegionSignal signal = handle.PreAction;
105              handle.Dispose();
106  
107              RegionHandle splitLow = _tracking.BeginTracking(address, size, _id);
108              splitLow.Parent = this;
109              if (signal != null)
110              {
111                  splitLow.RegisterAction(signal);
112              }
113              _handles[handleIndex] = splitLow;
114  
115              RegionHandle splitHigh = _tracking.BeginTracking(address + size, handle.Size - size, _id);
116              splitHigh.Parent = this;
117              if (signal != null)
118              {
119                  splitHigh.RegisterAction(signal);
120              }
121              _handles[splitIndex] = splitHigh;
122          }
123  
124          private void CreateHandle(int startHandle, int lastHandle)
125          {
126              ulong startAddress = _address + HandlesToBytes(startHandle);
127  
128              // Scan for the first handle before us. If it's overlapping us, it must be split.
129              for (int i = startHandle - 1; i >= 0; i--)
130              {
131                  RegionHandle handle = _handles[i];
132                  if (handle != null)
133                  {
134                      if (handle.EndAddress > startAddress)
135                      {
136                          SplitHandle(i, startHandle);
137                          return; // The remainer of this handle should be filled in later on.
138                      }
139                      break;
140                  }
141              }
142  
143              // Scan for handles after us. We should create a handle that goes up to this handle's start point, if present.
144              for (int i = startHandle + 1; i <= lastHandle; i++)
145              {
146                  RegionHandle handle = _handles[i];
147                  if (handle != null)
148                  {
149                      // Fill up to the found handle.
150                      handle = _tracking.BeginTracking(startAddress, HandlesToBytes(i - startHandle), _id);
151                      handle.Parent = this;
152                      _handles[startHandle] = handle;
153                      return;
154                  }
155              }
156  
157              // Can fill the whole range.
158              _handles[startHandle] = _tracking.BeginTracking(startAddress, HandlesToBytes(1 + lastHandle - startHandle), _id);
159              _handles[startHandle].Parent = this;
160          }
161  
162          public void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction)
163          {
164              int startHandle = (int)((address - _address) / _granularity);
165              int lastHandle = (int)((address + (size - 1) - _address) / _granularity);
166  
167              ulong rgStart = _address + (ulong)startHandle * _granularity;
168              ulong rgSize = 0;
169  
170              ulong endAddress = _address + ((ulong)lastHandle + 1) * _granularity;
171  
172              int i = startHandle;
173  
174              while (i <= lastHandle)
175              {
176                  RegionHandle handle = _handles[i];
177                  if (handle == null)
178                  {
179                      // Missing handle. A new handle must be created.
180                      CreateHandle(i, lastHandle);
181                      handle = _handles[i];
182                  }
183  
184                  if (handle.EndAddress > endAddress)
185                  {
186                      // End address of handle is beyond the end of the search. Force a split.
187                      SplitHandle(i, lastHandle + 1);
188                      handle = _handles[i];
189                  }
190  
191                  if (handle.Dirty)
192                  {
193                      rgSize += handle.Size;
194                      handle.Reprotect();
195                  }
196                  else
197                  {
198                      // Submit the region scanned so far as dirty
199                      if (rgSize != 0)
200                      {
201                          modifiedAction(rgStart, rgSize);
202                          rgSize = 0;
203                      }
204                      rgStart = handle.EndAddress;
205                  }
206  
207                  i += (int)(handle.Size / _granularity);
208              }
209  
210              if (rgSize != 0)
211              {
212                  modifiedAction(rgStart, rgSize);
213              }
214          }
215  
216          public void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction, int sequenceNumber)
217          {
218              int startHandle = (int)((address - _address) / _granularity);
219              int lastHandle = (int)((address + (size - 1) - _address) / _granularity);
220  
221              ulong rgStart = _address + (ulong)startHandle * _granularity;
222              ulong rgSize = 0;
223  
224              ulong endAddress = _address + ((ulong)lastHandle + 1) * _granularity;
225  
226              int i = startHandle;
227  
228              while (i <= lastHandle)
229              {
230                  RegionHandle handle = _handles[i];
231                  if (handle == null)
232                  {
233                      // Missing handle. A new handle must be created.
234                      CreateHandle(i, lastHandle);
235                      handle = _handles[i];
236                  }
237  
238                  if (handle.EndAddress > endAddress)
239                  {
240                      // End address of handle is beyond the end of the search. Force a split.
241                      SplitHandle(i, lastHandle + 1);
242                      handle = _handles[i];
243                  }
244  
245                  if (handle.Dirty && sequenceNumber != handle.SequenceNumber)
246                  {
247                      rgSize += handle.Size;
248                      handle.Reprotect();
249                  }
250                  else
251                  {
252                      // Submit the region scanned so far as dirty
253                      if (rgSize != 0)
254                      {
255                          modifiedAction(rgStart, rgSize);
256                          rgSize = 0;
257                      }
258                      rgStart = handle.EndAddress;
259                  }
260  
261                  handle.SequenceNumber = sequenceNumber;
262  
263                  i += (int)(handle.Size / _granularity);
264              }
265  
266              if (rgSize != 0)
267              {
268                  modifiedAction(rgStart, rgSize);
269              }
270          }
271  
272          public void Dispose()
273          {
274              GC.SuppressFinalize(this);
275  
276              foreach (var handle in _handles)
277              {
278                  handle?.Dispose();
279              }
280          }
281      }
282  }