1  using System;
  2  using System.Collections.Generic;
  3  using System.Linq;
  4  using System.Numerics;
  5  using System.Runtime.CompilerServices;
  6  using System.Threading;
  7  
  8  namespace Ryujinx.Memory.Tracking
  9  {
 10      /// <summary>
 11      /// A region handle that tracks a large region using many smaller handles, to provide
 12      /// granular tracking that can be used to track partial updates. Backed by a bitmap
 13      /// to improve performance when scanning large regions.
 14      /// </summary>
 15      public class MultiRegionHandle : IMultiRegionHandle
 16      {
 17          /// <summary>
 18          /// A list of region handles for each granularity sized chunk of the whole region.
 19          /// </summary>
 20          private readonly RegionHandle[] _handles;
 21          private readonly ulong Address;
 22          private readonly ulong Granularity;
 23          private readonly ulong Size;
 24  
 25          private readonly ConcurrentBitmap _dirtyBitmap;
 26  
 27          private int _sequenceNumber;
 28          private readonly BitMap _sequenceNumberBitmap;
 29          private readonly BitMap _dirtyCheckedBitmap;
 30          private int _uncheckedHandles;
 31  
 32          public bool Dirty { get; private set; } = true;
 33  
 34          internal MultiRegionHandle(
 35              MemoryTracking tracking,
 36              ulong address,
 37              ulong size,
 38              IEnumerable<IRegionHandle> handles,
 39              ulong granularity,
 40              int id,
 41              RegionFlags flags)
 42          {
 43              _handles = new RegionHandle[(size + granularity - 1) / granularity];
 44              Granularity = granularity;
 45  
 46              _dirtyBitmap = new ConcurrentBitmap(_handles.Length, true);
 47              _sequenceNumberBitmap = new BitMap(_handles.Length);
 48              _dirtyCheckedBitmap = new BitMap(_handles.Length);
 49  
 50              int i = 0;
 51  
 52              if (handles != null)
 53              {
 54                  // Inherit from the handles we were given. Any gaps must be filled with new handles,
 55                  // and old handles larger than our granularity must copy their state onto new granular handles and dispose.
 56                  // It is assumed that the provided handles do not overlap, in order, are on page boundaries,
 57                  // and don't extend past the requested range.
 58  
 59                  foreach (RegionHandle handle in handles.Cast<RegionHandle>())
 60                  {
 61                      int startIndex = (int)((handle.RealAddress - address) / granularity);
 62  
 63                      // Fill any gap left before this handle.
 64                      while (i < startIndex)
 65                      {
 66                          RegionHandle fillHandle = tracking.BeginTrackingBitmap(address + (ulong)i * granularity, granularity, _dirtyBitmap, i, id, flags);
 67                          fillHandle.Parent = this;
 68                          _handles[i++] = fillHandle;
 69                      }
 70  
 71                      lock (tracking.TrackingLock)
 72                      {
 73                          if (handle is RegionHandle bitHandle && handle.Size == granularity)
 74                          {
 75                              handle.Parent = this;
 76  
 77                              bitHandle.ReplaceBitmap(_dirtyBitmap, i);
 78  
 79                              _handles[i++] = bitHandle;
 80                          }
 81                          else
 82                          {
 83                              int endIndex = (int)((handle.RealEndAddress - address) / granularity);
 84  
 85                              while (i < endIndex)
 86                              {
 87                                  RegionHandle splitHandle = tracking.BeginTrackingBitmap(address + (ulong)i * granularity, granularity, _dirtyBitmap, i, id, flags);
 88                                  splitHandle.Parent = this;
 89  
 90                                  splitHandle.Reprotect(handle.Dirty);
 91  
 92                                  RegionSignal signal = handle.PreAction;
 93                                  if (signal != null)
 94                                  {
 95                                      splitHandle.RegisterAction(signal);
 96                                  }
 97  
 98                                  _handles[i++] = splitHandle;
 99                              }
100  
101                              handle.Dispose();
102                          }
103                      }
104                  }
105              }
106  
107              // Fill any remaining space with new handles.
108              while (i < _handles.Length)
109              {
110                  RegionHandle handle = tracking.BeginTrackingBitmap(address + (ulong)i * granularity, granularity, _dirtyBitmap, i, id, flags);
111                  handle.Parent = this;
112                  _handles[i++] = handle;
113              }
114  
115              _uncheckedHandles = _handles.Length;
116  
117              Address = address;
118              Size = size;
119          }
120  
121          public void SignalWrite()
122          {
123              Dirty = true;
124          }
125  
126          public IEnumerable<RegionHandle> GetHandles()
127          {
128              return _handles;
129          }
130  
131          public void ForceDirty(ulong address, ulong size)
132          {
133              Dirty = true;
134  
135              int startHandle = (int)((address - Address) / Granularity);
136              int lastHandle = (int)((address + (size - 1) - Address) / Granularity);
137  
138              for (int i = startHandle; i <= lastHandle; i++)
139              {
140                  if (_sequenceNumberBitmap.Clear(i))
141                  {
142                      _uncheckedHandles++;
143                  }
144  
145                  _handles[i].ForceDirty();
146              }
147          }
148  
149          public void QueryModified(Action<ulong, ulong> modifiedAction)
150          {
151              if (!Dirty)
152              {
153                  return;
154              }
155  
156              Dirty = false;
157  
158              QueryModified(Address, Size, modifiedAction);
159          }
160  
161          [MethodImpl(MethodImplOptions.AggressiveInlining)]
162          private void ParseDirtyBits(long dirtyBits, ref int baseBit, ref int prevHandle, ref ulong rgStart, ref ulong rgSize, Action<ulong, ulong> modifiedAction)
163          {
164              while (dirtyBits != 0)
165              {
166                  int bit = BitOperations.TrailingZeroCount(dirtyBits);
167  
168                  dirtyBits &= ~(1L << bit);
169  
170                  int handleIndex = baseBit + bit;
171  
172                  RegionHandle handle = _handles[handleIndex];
173  
174                  if (handleIndex != prevHandle + 1)
175                  {
176                      // Submit handles scanned until the gap as dirty
177                      if (rgSize != 0)
178                      {
179                          modifiedAction(rgStart, rgSize);
180                          rgSize = 0;
181                      }
182  
183                      rgStart = handle.RealAddress;
184                  }
185  
186                  if (handle.Dirty)
187                  {
188                      rgSize += handle.RealSize;
189                      handle.Reprotect();
190                  }
191  
192                  prevHandle = handleIndex;
193              }
194  
195              baseBit += ConcurrentBitmap.IntSize;
196          }
197  
198          public void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction)
199          {
200              int startHandle = (int)((address - Address) / Granularity);
201              int lastHandle = (int)((address + (size - 1) - Address) / Granularity);
202  
203              ulong rgStart = Address + (ulong)startHandle * Granularity;
204  
205              if (startHandle == lastHandle)
206              {
207                  RegionHandle handle = _handles[startHandle];
208  
209                  if (handle.Dirty)
210                  {
211                      handle.Reprotect();
212                      modifiedAction(rgStart, handle.RealSize);
213                  }
214  
215                  return;
216              }
217  
218              ulong rgSize = 0;
219  
220              long[] masks = _dirtyBitmap.Masks;
221  
222              int startIndex = startHandle >> ConcurrentBitmap.IntShift;
223              int startBit = startHandle & ConcurrentBitmap.IntMask;
224              long startMask = -1L << startBit;
225  
226              int endIndex = lastHandle >> ConcurrentBitmap.IntShift;
227              int endBit = lastHandle & ConcurrentBitmap.IntMask;
228              long endMask = (long)(ulong.MaxValue >> (ConcurrentBitmap.IntMask - endBit));
229  
230              long startValue = Volatile.Read(ref masks[startIndex]);
231  
232              int baseBit = startIndex << ConcurrentBitmap.IntShift;
233              int prevHandle = startHandle - 1;
234  
235              if (startIndex == endIndex)
236              {
237                  ParseDirtyBits(startValue & startMask & endMask, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
238              }
239              else
240              {
241                  ParseDirtyBits(startValue & startMask, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
242  
243                  for (int i = startIndex + 1; i < endIndex; i++)
244                  {
245                      ParseDirtyBits(Volatile.Read(ref masks[i]), ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
246                  }
247  
248                  long endValue = Volatile.Read(ref masks[endIndex]);
249  
250                  ParseDirtyBits(endValue & endMask, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
251              }
252  
253              if (rgSize != 0)
254              {
255                  modifiedAction(rgStart, rgSize);
256              }
257          }
258  
259          [MethodImpl(MethodImplOptions.AggressiveInlining)]
260          private void ParseDirtyBits(long dirtyBits, long mask, int index, long[] seqMasks, long[] checkMasks, ref int baseBit, ref int prevHandle, ref ulong rgStart, ref ulong rgSize, Action<ulong, ulong> modifiedAction)
261          {
262              long seqMask = mask & ~seqMasks[index];
263              long checkMask = (~dirtyBits) & seqMask;
264              dirtyBits &= seqMask;
265  
266              while (dirtyBits != 0)
267              {
268                  int bit = BitOperations.TrailingZeroCount(dirtyBits);
269                  long bitValue = 1L << bit;
270  
271                  dirtyBits &= ~bitValue;
272  
273                  int handleIndex = baseBit + bit;
274  
275                  RegionHandle handle = _handles[handleIndex];
276  
277                  if (handleIndex != prevHandle + 1)
278                  {
279                      // Submit handles scanned until the gap as dirty
280                      if (rgSize != 0)
281                      {
282                          modifiedAction(rgStart, rgSize);
283                          rgSize = 0;
284                      }
285                      rgStart = handle.RealAddress;
286                  }
287  
288                  rgSize += handle.RealSize;
289                  handle.Reprotect(false, (checkMasks[index] & bitValue) == 0);
290  
291                  checkMasks[index] &= ~bitValue;
292  
293                  prevHandle = handleIndex;
294              }
295  
296              checkMasks[index] |= checkMask;
297              seqMasks[index] |= mask;
298              _uncheckedHandles -= BitOperations.PopCount((ulong)seqMask);
299  
300              baseBit += ConcurrentBitmap.IntSize;
301          }
302  
303          public void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction, int sequenceNumber)
304          {
305              int startHandle = (int)((address - Address) / Granularity);
306              int lastHandle = (int)((address + (size - 1) - Address) / Granularity);
307  
308              ulong rgStart = Address + (ulong)startHandle * Granularity;
309  
310              if (sequenceNumber != _sequenceNumber)
311              {
312                  if (_uncheckedHandles != _handles.Length)
313                  {
314                      _sequenceNumberBitmap.Clear();
315                      _uncheckedHandles = _handles.Length;
316                  }
317  
318                  _sequenceNumber = sequenceNumber;
319              }
320  
321              if (startHandle == lastHandle)
322              {
323                  var handle = _handles[startHandle];
324                  if (_sequenceNumberBitmap.Set(startHandle))
325                  {
326                      _uncheckedHandles--;
327  
328                      if (handle.DirtyOrVolatile())
329                      {
330                          handle.Reprotect();
331  
332                          modifiedAction(rgStart, handle.RealSize);
333                      }
334                  }
335  
336                  return;
337              }
338  
339              if (_uncheckedHandles == 0)
340              {
341                  return;
342              }
343  
344              ulong rgSize = 0;
345  
346              long[] seqMasks = _sequenceNumberBitmap.Masks;
347              long[] checkedMasks = _dirtyCheckedBitmap.Masks;
348              long[] masks = _dirtyBitmap.Masks;
349  
350              int startIndex = startHandle >> ConcurrentBitmap.IntShift;
351              int startBit = startHandle & ConcurrentBitmap.IntMask;
352              long startMask = -1L << startBit;
353  
354              int endIndex = lastHandle >> ConcurrentBitmap.IntShift;
355              int endBit = lastHandle & ConcurrentBitmap.IntMask;
356              long endMask = (long)(ulong.MaxValue >> (ConcurrentBitmap.IntMask - endBit));
357  
358              long startValue = Volatile.Read(ref masks[startIndex]);
359  
360              int baseBit = startIndex << ConcurrentBitmap.IntShift;
361              int prevHandle = startHandle - 1;
362  
363              if (startIndex == endIndex)
364              {
365                  ParseDirtyBits(startValue, startMask & endMask, startIndex, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
366              }
367              else
368              {
369                  ParseDirtyBits(startValue, startMask, startIndex, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
370  
371                  for (int i = startIndex + 1; i < endIndex; i++)
372                  {
373                      ParseDirtyBits(Volatile.Read(ref masks[i]), -1L, i, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
374                  }
375  
376                  long endValue = Volatile.Read(ref masks[endIndex]);
377  
378                  ParseDirtyBits(endValue, endMask, endIndex, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction);
379              }
380  
381              if (rgSize != 0)
382              {
383                  modifiedAction(rgStart, rgSize);
384              }
385          }
386  
387          public void RegisterAction(ulong address, ulong size, RegionSignal action)
388          {
389              int startHandle = (int)((address - Address) / Granularity);
390              int lastHandle = (int)((address + (size - 1) - Address) / Granularity);
391  
392              for (int i = startHandle; i <= lastHandle; i++)
393              {
394                  _handles[i].RegisterAction(action);
395              }
396          }
397  
398          public void RegisterPreciseAction(ulong address, ulong size, PreciseRegionSignal action)
399          {
400              int startHandle = (int)((address - Address) / Granularity);
401              int lastHandle = (int)((address + (size - 1) - Address) / Granularity);
402  
403              for (int i = startHandle; i <= lastHandle; i++)
404              {
405                  _handles[i].RegisterPreciseAction(action);
406              }
407          }
408  
409          public void Dispose()
410          {
411              GC.SuppressFinalize(this);
412  
413              foreach (var handle in _handles)
414              {
415                  handle.Dispose();
416              }
417          }
418      }
419  }