1  using Ryujinx.Graphics.GAL;
   2  using Ryujinx.Memory.Range;
   3  using System;
   4  using System.Collections.Generic;
   5  using System.Linq;
   6  using System.Runtime.CompilerServices;
   7  
   8  namespace Ryujinx.Graphics.Gpu.Memory
   9  {
  10      /// <summary>
  11      /// Buffer cache.
  12      /// </summary>
  13      class BufferCache : IDisposable
  14      {
  15          /// <summary>
  16          /// Initial size for the array holding overlaps.
  17          /// </summary>
  18          public const int OverlapsBufferInitialCapacity = 10;
  19  
  20          /// <summary>
  21          /// Maximum size that an array holding overlaps may have after trimming.
  22          /// </summary>
  23          public const int OverlapsBufferMaxCapacity = 10000;
  24  
  25          private const ulong BufferAlignmentSize = 0x1000;
  26          private const ulong BufferAlignmentMask = BufferAlignmentSize - 1;
  27  
  28          /// <summary>
  29          /// Alignment required for sparse buffer mappings.
  30          /// </summary>
  31          public const ulong SparseBufferAlignmentSize = 0x10000;
  32  
  33          private const ulong MaxDynamicGrowthSize = 0x100000;
  34  
  35          private readonly GpuContext _context;
  36          private readonly PhysicalMemory _physicalMemory;
  37  
  38          /// <remarks>
  39          /// Only modified from the GPU thread. Must lock for add/remove.
  40          /// Must lock for any access from other threads.
  41          /// </remarks>
  42          private readonly RangeList<Buffer> _buffers;
  43          private readonly MultiRangeList<MultiRangeBuffer> _multiRangeBuffers;
  44  
  45          private Buffer[] _bufferOverlaps;
  46  
  47          private readonly Dictionary<ulong, BufferCacheEntry> _dirtyCache;
  48          private readonly Dictionary<ulong, BufferCacheEntry> _modifiedCache;
  49          private bool _pruneCaches;
  50          private int _virtualModifiedSequenceNumber;
  51  
  52          public event Action NotifyBuffersModified;
  53  
  54          /// <summary>
  55          /// Creates a new instance of the buffer manager.
  56          /// </summary>
  57          /// <param name="context">The GPU context that the buffer manager belongs to</param>
  58          /// <param name="physicalMemory">Physical memory where the cached buffers are mapped</param>
  59          public BufferCache(GpuContext context, PhysicalMemory physicalMemory)
  60          {
  61              _context = context;
  62              _physicalMemory = physicalMemory;
  63  
  64              _buffers = new RangeList<Buffer>();
  65              _multiRangeBuffers = new MultiRangeList<MultiRangeBuffer>();
  66  
  67              _bufferOverlaps = new Buffer[OverlapsBufferInitialCapacity];
  68  
  69              _dirtyCache = new Dictionary<ulong, BufferCacheEntry>();
  70  
  71              // There are a lot more entries on the modified cache, so it is separate from the one for ForceDirty.
  72              _modifiedCache = new Dictionary<ulong, BufferCacheEntry>();
  73          }
  74  
  75          /// <summary>
  76          /// Handles removal of buffers written to a memory region being unmapped.
  77          /// </summary>
  78          /// <param name="sender">Sender object</param>
  79          /// <param name="e">Event arguments</param>
  80          public void MemoryUnmappedHandler(object sender, UnmapEventArgs e)
  81          {
  82              Buffer[] overlaps = new Buffer[10];
  83              int overlapCount;
  84  
  85              MultiRange range = ((MemoryManager)sender).GetPhysicalRegions(e.Address, e.Size);
  86  
  87              for (int index = 0; index < range.Count; index++)
  88              {
  89                  MemoryRange subRange = range.GetSubRange(index);
  90  
  91                  lock (_buffers)
  92                  {
  93                      overlapCount = _buffers.FindOverlaps(subRange.Address, subRange.Size, ref overlaps);
  94                  }
  95  
  96                  for (int i = 0; i < overlapCount; i++)
  97                  {
  98                      overlaps[i].Unmapped(subRange.Address, subRange.Size);
  99                  }
 100              }
 101          }
 102  
 103          /// <summary>
 104          /// Performs address translation of the GPU virtual address, and creates a
 105          /// new buffer, if needed, for the specified contiguous range.
 106          /// </summary>
 107          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 108          /// <param name="gpuVa">Start GPU virtual address of the buffer</param>
 109          /// <param name="size">Size in bytes of the buffer</param>
 110          /// <param name="stage">The type of usage that created the buffer</param>
 111          /// <returns>Contiguous physical range of the buffer, after address translation</returns>
 112          public MultiRange TranslateAndCreateBuffer(MemoryManager memoryManager, ulong gpuVa, ulong size, BufferStage stage)
 113          {
 114              if (gpuVa == 0)
 115              {
 116                  return new MultiRange(MemoryManager.PteUnmapped, size);
 117              }
 118  
 119              ulong address = memoryManager.Translate(gpuVa);
 120  
 121              if (address != MemoryManager.PteUnmapped)
 122              {
 123                  CreateBuffer(address, size, stage);
 124              }
 125  
 126              return new MultiRange(address, size);
 127          }
 128  
 129          /// <summary>
 130          /// Performs address translation of the GPU virtual address, and creates
 131          /// new physical and virtual buffers, if needed, for the specified range.
 132          /// </summary>
 133          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 134          /// <param name="gpuVa">Start GPU virtual address of the buffer</param>
 135          /// <param name="size">Size in bytes of the buffer</param>
 136          /// <param name="stage">The type of usage that created the buffer</param>
 137          /// <returns>Physical ranges of the buffer, after address translation</returns>
 138          public MultiRange TranslateAndCreateMultiBuffers(MemoryManager memoryManager, ulong gpuVa, ulong size, BufferStage stage)
 139          {
 140              if (gpuVa == 0)
 141              {
 142                  return new MultiRange(MemoryManager.PteUnmapped, size);
 143              }
 144  
 145              // Fast path not taken for non-contiguous ranges,
 146              // since multi-range buffers are not coalesced, so a buffer that covers
 147              // the entire cached range might not actually exist.
 148              if (memoryManager.VirtualRangeCache.TryGetOrAddRange(gpuVa, size, out MultiRange range) &&
 149                  range.Count == 1)
 150              {
 151                  return range;
 152              }
 153  
 154              CreateBuffer(range, stage);
 155  
 156              return range;
 157          }
 158  
 159          /// <summary>
 160          /// Performs address translation of the GPU virtual address, and creates
 161          /// new physical buffers, if needed, for the specified range.
 162          /// </summary>
 163          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 164          /// <param name="gpuVa">Start GPU virtual address of the buffer</param>
 165          /// <param name="size">Size in bytes of the buffer</param>
 166          /// <param name="stage">The type of usage that created the buffer</param>
 167          /// <returns>Physical ranges of the buffer, after address translation</returns>
 168          public MultiRange TranslateAndCreateMultiBuffersPhysicalOnly(MemoryManager memoryManager, ulong gpuVa, ulong size, BufferStage stage)
 169          {
 170              if (gpuVa == 0)
 171              {
 172                  return new MultiRange(MemoryManager.PteUnmapped, size);
 173              }
 174  
 175              // Fast path not taken for non-contiguous ranges,
 176              // since multi-range buffers are not coalesced, so a buffer that covers
 177              // the entire cached range might not actually exist.
 178              if (memoryManager.VirtualRangeCache.TryGetOrAddRange(gpuVa, size, out MultiRange range) &&
 179                  range.Count == 1)
 180              {
 181                  return range;
 182              }
 183  
 184              for (int i = 0; i < range.Count; i++)
 185              {
 186                  MemoryRange subRange = range.GetSubRange(i);
 187  
 188                  if (subRange.Address != MemoryManager.PteUnmapped)
 189                  {
 190                      if (range.Count > 1)
 191                      {
 192                          CreateBuffer(subRange.Address, subRange.Size, stage, SparseBufferAlignmentSize);
 193                      }
 194                      else
 195                      {
 196                          CreateBuffer(subRange.Address, subRange.Size, stage);
 197                      }
 198                  }
 199              }
 200  
 201              return range;
 202          }
 203  
 204          /// <summary>
 205          /// Creates a new buffer for the specified range, if it does not yet exist.
 206          /// This can be used to ensure the existance of a buffer.
 207          /// </summary>
 208          /// <param name="range">Physical ranges of memory where the buffer data is located</param>
 209          /// <param name="stage">The type of usage that created the buffer</param>
 210          public void CreateBuffer(MultiRange range, BufferStage stage)
 211          {
 212              if (range.Count > 1)
 213              {
 214                  CreateMultiRangeBuffer(range, stage);
 215              }
 216              else
 217              {
 218                  MemoryRange subRange = range.GetSubRange(0);
 219  
 220                  if (subRange.Address != MemoryManager.PteUnmapped)
 221                  {
 222                      CreateBuffer(subRange.Address, subRange.Size, stage);
 223                  }
 224              }
 225          }
 226  
 227          /// <summary>
 228          /// Creates a new buffer for the specified range, if it does not yet exist.
 229          /// This can be used to ensure the existance of a buffer.
 230          /// </summary>
 231          /// <param name="address">Address of the buffer in memory</param>
 232          /// <param name="size">Size of the buffer in bytes</param>
 233          /// <param name="stage">The type of usage that created the buffer</param>
 234          public void CreateBuffer(ulong address, ulong size, BufferStage stage)
 235          {
 236              ulong endAddress = address + size;
 237  
 238              ulong alignedAddress = address & ~BufferAlignmentMask;
 239              ulong alignedEndAddress = (endAddress + BufferAlignmentMask) & ~BufferAlignmentMask;
 240  
 241              // The buffer must have the size of at least one page.
 242              if (alignedEndAddress == alignedAddress)
 243              {
 244                  alignedEndAddress += BufferAlignmentSize;
 245              }
 246  
 247              CreateBufferAligned(alignedAddress, alignedEndAddress - alignedAddress, stage);
 248          }
 249  
 250          /// <summary>
 251          /// Creates a new buffer for the specified range, if it does not yet exist.
 252          /// This can be used to ensure the existance of a buffer.
 253          /// </summary>
 254          /// <param name="address">Address of the buffer in memory</param>
 255          /// <param name="size">Size of the buffer in bytes</param>
 256          /// <param name="stage">The type of usage that created the buffer</param>
 257          /// <param name="alignment">Alignment of the start address of the buffer in bytes</param>
 258          public void CreateBuffer(ulong address, ulong size, BufferStage stage, ulong alignment)
 259          {
 260              ulong alignmentMask = alignment - 1;
 261              ulong pageAlignmentMask = BufferAlignmentMask;
 262              ulong endAddress = address + size;
 263  
 264              ulong alignedAddress = address & ~alignmentMask;
 265              ulong alignedEndAddress = (endAddress + pageAlignmentMask) & ~pageAlignmentMask;
 266  
 267              // The buffer must have the size of at least one page.
 268              if (alignedEndAddress == alignedAddress)
 269              {
 270                  alignedEndAddress += pageAlignmentMask;
 271              }
 272  
 273              CreateBufferAligned(alignedAddress, alignedEndAddress - alignedAddress, stage, alignment);
 274          }
 275  
 276          /// <summary>
 277          /// Creates a buffer for a memory region composed of multiple physical ranges,
 278          /// if it does not exist yet.
 279          /// </summary>
 280          /// <param name="range">Physical ranges of memory</param>
 281          /// <param name="stage">The type of usage that created the buffer</param>
 282          private void CreateMultiRangeBuffer(MultiRange range, BufferStage stage)
 283          {
 284              // Ensure all non-contiguous buffer we might use are sparse aligned.
 285              for (int i = 0; i < range.Count; i++)
 286              {
 287                  MemoryRange subRange = range.GetSubRange(i);
 288  
 289                  if (subRange.Address != MemoryManager.PteUnmapped)
 290                  {
 291                      CreateBuffer(subRange.Address, subRange.Size, stage, SparseBufferAlignmentSize);
 292                  }
 293              }
 294  
 295              // Create sparse buffer.
 296              MultiRangeBuffer[] overlaps = new MultiRangeBuffer[10];
 297  
 298              int overlapCount = _multiRangeBuffers.FindOverlaps(range, ref overlaps);
 299  
 300              for (int index = 0; index < overlapCount; index++)
 301              {
 302                  if (overlaps[index].Range.Contains(range))
 303                  {
 304                      return;
 305                  }
 306              }
 307  
 308              for (int index = 0; index < overlapCount; index++)
 309              {
 310                  if (range.Contains(overlaps[index].Range))
 311                  {
 312                      _multiRangeBuffers.Remove(overlaps[index]);
 313                      overlaps[index].Dispose();
 314                  }
 315              }
 316  
 317              MultiRangeBuffer multiRangeBuffer;
 318  
 319              MemoryRange[] alignedSubRanges = new MemoryRange[range.Count];
 320  
 321              ulong alignmentMask = SparseBufferAlignmentSize - 1;
 322  
 323              if (_context.Capabilities.SupportsSparseBuffer)
 324              {
 325                  BufferRange[] storages = new BufferRange[range.Count];
 326  
 327                  for (int i = 0; i < range.Count; i++)
 328                  {
 329                      MemoryRange subRange = range.GetSubRange(i);
 330  
 331                      if (subRange.Address != MemoryManager.PteUnmapped)
 332                      {
 333                          ulong endAddress = subRange.Address + subRange.Size;
 334  
 335                          ulong alignedAddress = subRange.Address & ~alignmentMask;
 336                          ulong alignedEndAddress = (endAddress + alignmentMask) & ~alignmentMask;
 337                          ulong alignedSize = alignedEndAddress - alignedAddress;
 338  
 339                          Buffer buffer = _buffers.FindFirstOverlap(alignedAddress, alignedSize);
 340                          BufferRange bufferRange = buffer.GetRange(alignedAddress, alignedSize, false);
 341  
 342                          alignedSubRanges[i] = new MemoryRange(alignedAddress, alignedSize);
 343                          storages[i] = bufferRange;
 344                      }
 345                      else
 346                      {
 347                          ulong alignedSize = (subRange.Size + alignmentMask) & ~alignmentMask;
 348  
 349                          alignedSubRanges[i] = new MemoryRange(MemoryManager.PteUnmapped, alignedSize);
 350                          storages[i] = new BufferRange(BufferHandle.Null, 0, (int)alignedSize);
 351                      }
 352                  }
 353  
 354                  multiRangeBuffer = new(_context, new MultiRange(alignedSubRanges), storages);
 355              }
 356              else
 357              {
 358                  for (int i = 0; i < range.Count; i++)
 359                  {
 360                      MemoryRange subRange = range.GetSubRange(i);
 361  
 362                      if (subRange.Address != MemoryManager.PteUnmapped)
 363                      {
 364                          ulong endAddress = subRange.Address + subRange.Size;
 365  
 366                          ulong alignedAddress = subRange.Address & ~alignmentMask;
 367                          ulong alignedEndAddress = (endAddress + alignmentMask) & ~alignmentMask;
 368                          ulong alignedSize = alignedEndAddress - alignedAddress;
 369  
 370                          alignedSubRanges[i] = new MemoryRange(alignedAddress, alignedSize);
 371                      }
 372                      else
 373                      {
 374                          ulong alignedSize = (subRange.Size + alignmentMask) & ~alignmentMask;
 375  
 376                          alignedSubRanges[i] = new MemoryRange(MemoryManager.PteUnmapped, alignedSize);
 377                      }
 378                  }
 379  
 380                  multiRangeBuffer = new(_context, new MultiRange(alignedSubRanges));
 381  
 382                  UpdateVirtualBufferDependencies(multiRangeBuffer);
 383              }
 384  
 385              _multiRangeBuffers.Add(multiRangeBuffer);
 386          }
 387  
 388          /// <summary>
 389          /// Adds two-way dependencies to all physical buffers contained within a given virtual buffer.
 390          /// </summary>
 391          /// <param name="virtualBuffer">Virtual buffer to have dependencies added</param>
 392          private void UpdateVirtualBufferDependencies(MultiRangeBuffer virtualBuffer)
 393          {
 394              virtualBuffer.ClearPhysicalDependencies();
 395  
 396              ulong dstOffset = 0;
 397  
 398              HashSet<Buffer> physicalBuffers = new();
 399  
 400              for (int i = 0; i < virtualBuffer.Range.Count; i++)
 401              {
 402                  MemoryRange subRange = virtualBuffer.Range.GetSubRange(i);
 403  
 404                  if (subRange.Address != MemoryManager.PteUnmapped)
 405                  {
 406                      Buffer buffer = _buffers.FindFirstOverlap(subRange.Address, subRange.Size);
 407  
 408                      virtualBuffer.AddPhysicalDependency(buffer, subRange.Address, dstOffset, subRange.Size);
 409                      physicalBuffers.Add(buffer);
 410                  }
 411  
 412                  dstOffset += subRange.Size;
 413              }
 414  
 415              foreach (var buffer in physicalBuffers)
 416              {
 417                  buffer.CopyToDependantVirtualBuffer(virtualBuffer);
 418              }
 419          }
 420  
 421          /// <summary>
 422          /// Performs address translation of the GPU virtual address, and attempts to force
 423          /// the buffer in the region as dirty.
 424          /// The buffer lookup for this function is cached in a dictionary for quick access, which
 425          /// accelerates common UBO updates.
 426          /// </summary>
 427          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 428          /// <param name="gpuVa">Start GPU virtual address of the buffer</param>
 429          /// <param name="size">Size in bytes of the buffer</param>
 430          public void ForceDirty(MemoryManager memoryManager, ulong gpuVa, ulong size)
 431          {
 432              if (_pruneCaches)
 433              {
 434                  Prune();
 435              }
 436  
 437              if (!_dirtyCache.TryGetValue(gpuVa, out BufferCacheEntry result) ||
 438                  result.EndGpuAddress < gpuVa + size ||
 439                  result.UnmappedSequence != result.Buffer.UnmappedSequence)
 440              {
 441                  MultiRange range = TranslateAndCreateBuffer(memoryManager, gpuVa, size, BufferStage.Internal);
 442                  ulong address = range.GetSubRange(0).Address;
 443                  result = new BufferCacheEntry(address, gpuVa, GetBuffer(address, size, BufferStage.Internal));
 444  
 445                  _dirtyCache[gpuVa] = result;
 446              }
 447  
 448              result.Buffer.ForceDirty(result.Address, size);
 449          }
 450  
 451          /// <summary>
 452          /// Checks if the given buffer range has been GPU modifed.
 453          /// </summary>
 454          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 455          /// <param name="gpuVa">Start GPU virtual address of the buffer</param>
 456          /// <param name="size">Size in bytes of the buffer</param>
 457          /// <returns>True if modified, false otherwise</returns>
 458          public bool CheckModified(MemoryManager memoryManager, ulong gpuVa, ulong size, out ulong outAddr)
 459          {
 460              if (_pruneCaches)
 461              {
 462                  Prune();
 463              }
 464  
 465              // Align the address to avoid creating too many entries on the quick lookup dictionary.
 466              ulong mask = BufferAlignmentMask;
 467              ulong alignedGpuVa = gpuVa & (~mask);
 468              ulong alignedEndGpuVa = (gpuVa + size + mask) & (~mask);
 469  
 470              size = alignedEndGpuVa - alignedGpuVa;
 471  
 472              if (!_modifiedCache.TryGetValue(alignedGpuVa, out BufferCacheEntry result) ||
 473                  result.EndGpuAddress < alignedEndGpuVa ||
 474                  result.UnmappedSequence != result.Buffer.UnmappedSequence)
 475              {
 476                  MultiRange range = TranslateAndCreateBuffer(memoryManager, alignedGpuVa, size, BufferStage.None);
 477                  ulong address = range.GetSubRange(0).Address;
 478                  result = new BufferCacheEntry(address, alignedGpuVa, GetBuffer(address, size, BufferStage.None));
 479  
 480                  _modifiedCache[alignedGpuVa] = result;
 481              }
 482  
 483              outAddr = result.Address | (gpuVa & mask);
 484  
 485              return result.Buffer.IsModified(result.Address, size);
 486          }
 487  
 488          /// <summary>
 489          /// Creates a new buffer for the specified range, if needed.
 490          /// If a buffer where this range can be fully contained already exists,
 491          /// then the creation of a new buffer is not necessary.
 492          /// </summary>
 493          /// <param name="address">Address of the buffer in guest memory</param>
 494          /// <param name="size">Size in bytes of the buffer</param>
 495          /// <param name="stage">The type of usage that created the buffer</param>
 496          private void CreateBufferAligned(ulong address, ulong size, BufferStage stage)
 497          {
 498              Buffer[] overlaps = _bufferOverlaps;
 499              int overlapsCount = _buffers.FindOverlapsNonOverlapping(address, size, ref overlaps);
 500  
 501              if (overlapsCount != 0)
 502              {
 503                  // The buffer already exists. We can just return the existing buffer
 504                  // if the buffer we need is fully contained inside the overlapping buffer.
 505                  // Otherwise, we must delete the overlapping buffers and create a bigger buffer
 506                  // that fits all the data we need. We also need to copy the contents from the
 507                  // old buffer(s) to the new buffer.
 508  
 509                  ulong endAddress = address + size;
 510                  Buffer overlap0 = overlaps[0];
 511  
 512                  if (overlap0.Address > address || overlap0.EndAddress < endAddress)
 513                  {
 514                      bool anySparseCompatible = false;
 515  
 516                      // Check if the following conditions are met:
 517                      // - We have a single overlap.
 518                      // - The overlap starts at or before the requested range. That is, the overlap happens at the end.
 519                      // - The size delta between the new, merged buffer and the old one is of at most 2 pages.
 520                      // In this case, we attempt to extend the buffer further than the requested range,
 521                      // this can potentially avoid future resizes if the application keeps using overlapping
 522                      // sequential memory.
 523                      // Allowing for 2 pages (rather than just one) is necessary to catch cases where the
 524                      // range crosses a page, and after alignment, ends having a size of 2 pages.
 525                      if (overlapsCount == 1 &&
 526                          address >= overlap0.Address &&
 527                          endAddress - overlap0.EndAddress <= BufferAlignmentSize * 2)
 528                      {
 529                          // Try to grow the buffer by 1.5x of its current size.
 530                          // This improves performance in the cases where the buffer is resized often by small amounts.
 531                          ulong existingSize = overlap0.Size;
 532                          ulong growthSize = (existingSize + Math.Min(existingSize >> 1, MaxDynamicGrowthSize)) & ~BufferAlignmentMask;
 533  
 534                          size = Math.Max(size, growthSize);
 535                          endAddress = address + size;
 536  
 537                          overlapsCount = _buffers.FindOverlapsNonOverlapping(address, size, ref overlaps);
 538                      }
 539  
 540                      for (int index = 0; index < overlapsCount; index++)
 541                      {
 542                          Buffer buffer = overlaps[index];
 543  
 544                          anySparseCompatible |= buffer.SparseCompatible;
 545  
 546                          address = Math.Min(address, buffer.Address);
 547                          endAddress = Math.Max(endAddress, buffer.EndAddress);
 548  
 549                          lock (_buffers)
 550                          {
 551                              _buffers.Remove(buffer);
 552                          }
 553                      }
 554  
 555                      ulong newSize = endAddress - address;
 556  
 557                      CreateBufferAligned(address, newSize, stage, anySparseCompatible, overlaps, overlapsCount);
 558                  }
 559              }
 560              else
 561              {
 562                  // No overlap, just create a new buffer.
 563                  Buffer buffer = new(_context, _physicalMemory, address, size, stage, sparseCompatible: false);
 564  
 565                  lock (_buffers)
 566                  {
 567                      _buffers.Add(buffer);
 568                  }
 569              }
 570  
 571              ShrinkOverlapsBufferIfNeeded();
 572          }
 573  
 574          /// <summary>
 575          /// Creates a new buffer for the specified range, if needed.
 576          /// If a buffer where this range can be fully contained already exists,
 577          /// then the creation of a new buffer is not necessary.
 578          /// </summary>
 579          /// <param name="address">Address of the buffer in guest memory</param>
 580          /// <param name="size">Size in bytes of the buffer</param>
 581          /// <param name="stage">The type of usage that created the buffer</param>
 582          /// <param name="alignment">Alignment of the start address of the buffer</param>
 583          private void CreateBufferAligned(ulong address, ulong size, BufferStage stage, ulong alignment)
 584          {
 585              Buffer[] overlaps = _bufferOverlaps;
 586              int overlapsCount = _buffers.FindOverlapsNonOverlapping(address, size, ref overlaps);
 587              bool sparseAligned = alignment >= SparseBufferAlignmentSize;
 588  
 589              if (overlapsCount != 0)
 590              {
 591                  // If the buffer already exists, make sure if covers the entire range,
 592                  // and make sure it is properly aligned, otherwise sparse mapping may fail.
 593  
 594                  ulong endAddress = address + size;
 595                  Buffer overlap0 = overlaps[0];
 596  
 597                  if (overlap0.Address > address ||
 598                      overlap0.EndAddress < endAddress ||
 599                      (overlap0.Address & (alignment - 1)) != 0 ||
 600                      (!overlap0.SparseCompatible && sparseAligned))
 601                  {
 602                      // We need to make sure the new buffer is properly aligned.
 603                      // However, after the range is aligned, it is possible that it
 604                      // overlaps more buffers, so try again after each extension
 605                      // and ensure we cover all overlaps.
 606  
 607                      int oldOverlapsCount;
 608  
 609                      do
 610                      {
 611                          for (int index = 0; index < overlapsCount; index++)
 612                          {
 613                              Buffer buffer = overlaps[index];
 614  
 615                              address = Math.Min(address, buffer.Address);
 616                              endAddress = Math.Max(endAddress, buffer.EndAddress);
 617                          }
 618  
 619                          address &= ~(alignment - 1);
 620  
 621                          oldOverlapsCount = overlapsCount;
 622                          overlapsCount = _buffers.FindOverlapsNonOverlapping(address, endAddress - address, ref overlaps);
 623                      }
 624                      while (oldOverlapsCount != overlapsCount);
 625  
 626                      lock (_buffers)
 627                      {
 628                          for (int index = 0; index < overlapsCount; index++)
 629                          {
 630                              _buffers.Remove(overlaps[index]);
 631                          }
 632                      }
 633  
 634                      ulong newSize = endAddress - address;
 635  
 636                      CreateBufferAligned(address, newSize, stage, sparseAligned, overlaps, overlapsCount);
 637                  }
 638              }
 639              else
 640              {
 641                  // No overlap, just create a new buffer.
 642                  Buffer buffer = new(_context, _physicalMemory, address, size, stage, sparseAligned);
 643  
 644                  lock (_buffers)
 645                  {
 646                      _buffers.Add(buffer);
 647                  }
 648              }
 649  
 650              ShrinkOverlapsBufferIfNeeded();
 651          }
 652  
 653          /// <summary>
 654          /// Creates a new buffer for the specified range, if needed.
 655          /// If a buffer where this range can be fully contained already exists,
 656          /// then the creation of a new buffer is not necessary.
 657          /// </summary>
 658          /// <param name="address">Address of the buffer in guest memory</param>
 659          /// <param name="size">Size in bytes of the buffer</param>
 660          /// <param name="stage">The type of usage that created the buffer</param>
 661          /// <param name="sparseCompatible">Indicates if the buffer can be used in a sparse buffer mapping</param>
 662          /// <param name="overlaps">Buffers overlapping the range</param>
 663          /// <param name="overlapsCount">Total of overlaps</param>
 664          private void CreateBufferAligned(ulong address, ulong size, BufferStage stage, bool sparseCompatible, Buffer[] overlaps, int overlapsCount)
 665          {
 666              Buffer newBuffer = new Buffer(_context, _physicalMemory, address, size, stage, sparseCompatible, overlaps.Take(overlapsCount));
 667  
 668              lock (_buffers)
 669              {
 670                  _buffers.Add(newBuffer);
 671              }
 672  
 673              for (int index = 0; index < overlapsCount; index++)
 674              {
 675                  Buffer buffer = overlaps[index];
 676  
 677                  int dstOffset = (int)(buffer.Address - newBuffer.Address);
 678  
 679                  buffer.CopyTo(newBuffer, dstOffset);
 680                  newBuffer.InheritModifiedRanges(buffer);
 681  
 682                  buffer.DecrementReferenceCount();
 683              }
 684  
 685              newBuffer.SynchronizeMemory(address, size);
 686  
 687              // Existing buffers were modified, we need to rebind everything.
 688              NotifyBuffersModified?.Invoke();
 689  
 690              RecreateMultiRangeBuffers(address, size);
 691          }
 692  
 693          /// <summary>
 694          /// Recreates all the multi-range buffers that overlaps a given physical memory range.
 695          /// </summary>
 696          /// <param name="address">Start address of the range</param>
 697          /// <param name="size">Size of the range in bytes</param>
 698          private void RecreateMultiRangeBuffers(ulong address, ulong size)
 699          {
 700              if ((address & (SparseBufferAlignmentSize - 1)) != 0 || (size & (SparseBufferAlignmentSize - 1)) != 0)
 701              {
 702                  return;
 703              }
 704  
 705              MultiRangeBuffer[] overlaps = new MultiRangeBuffer[10];
 706  
 707              int overlapCount = _multiRangeBuffers.FindOverlaps(address, size, ref overlaps);
 708  
 709              for (int index = 0; index < overlapCount; index++)
 710              {
 711                  _multiRangeBuffers.Remove(overlaps[index]);
 712                  overlaps[index].Dispose();
 713              }
 714  
 715              for (int index = 0; index < overlapCount; index++)
 716              {
 717                  CreateMultiRangeBuffer(overlaps[index].Range, BufferStage.None);
 718              }
 719          }
 720  
 721          /// <summary>
 722          /// Resizes the temporary buffer used for range list intersection results, if it has grown too much.
 723          /// </summary>
 724          private void ShrinkOverlapsBufferIfNeeded()
 725          {
 726              if (_bufferOverlaps.Length > OverlapsBufferMaxCapacity)
 727              {
 728                  Array.Resize(ref _bufferOverlaps, OverlapsBufferMaxCapacity);
 729              }
 730          }
 731  
 732          /// <summary>
 733          /// Copy a buffer data from a given address to another.
 734          /// </summary>
 735          /// <remarks>
 736          /// This does a GPU side copy.
 737          /// </remarks>
 738          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 739          /// <param name="srcVa">GPU virtual address of the copy source</param>
 740          /// <param name="dstVa">GPU virtual address of the copy destination</param>
 741          /// <param name="size">Size in bytes of the copy</param>
 742          public void CopyBuffer(MemoryManager memoryManager, ulong srcVa, ulong dstVa, ulong size)
 743          {
 744              MultiRange srcRange = TranslateAndCreateMultiBuffersPhysicalOnly(memoryManager, srcVa, size, BufferStage.Copy);
 745              MultiRange dstRange = TranslateAndCreateMultiBuffersPhysicalOnly(memoryManager, dstVa, size, BufferStage.Copy);
 746  
 747              if (srcRange.Count == 1 && dstRange.Count == 1)
 748              {
 749                  CopyBufferSingleRange(memoryManager, srcRange.GetSubRange(0).Address, dstRange.GetSubRange(0).Address, size);
 750              }
 751              else
 752              {
 753                  ulong copiedSize = 0;
 754                  ulong srcOffset = 0;
 755                  ulong dstOffset = 0;
 756                  int srcRangeIndex = 0;
 757                  int dstRangeIndex = 0;
 758  
 759                  while (copiedSize < size)
 760                  {
 761                      if (srcRange.GetSubRange(srcRangeIndex).Size == srcOffset)
 762                      {
 763                          srcRangeIndex++;
 764                          srcOffset = 0;
 765                      }
 766  
 767                      if (dstRange.GetSubRange(dstRangeIndex).Size == dstOffset)
 768                      {
 769                          dstRangeIndex++;
 770                          dstOffset = 0;
 771                      }
 772  
 773                      MemoryRange srcSubRange = srcRange.GetSubRange(srcRangeIndex);
 774                      MemoryRange dstSubRange = dstRange.GetSubRange(dstRangeIndex);
 775  
 776                      ulong srcSize = srcSubRange.Size - srcOffset;
 777                      ulong dstSize = dstSubRange.Size - dstOffset;
 778                      ulong copySize = Math.Min(srcSize, dstSize);
 779  
 780                      CopyBufferSingleRange(memoryManager, srcSubRange.Address + srcOffset, dstSubRange.Address + dstOffset, copySize);
 781  
 782                      srcOffset += copySize;
 783                      dstOffset += copySize;
 784                      copiedSize += copySize;
 785                  }
 786              }
 787          }
 788  
 789          /// <summary>
 790          /// Copy a buffer data from a given address to another.
 791          /// </summary>
 792          /// <remarks>
 793          /// This does a GPU side copy.
 794          /// </remarks>
 795          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 796          /// <param name="srcAddress">Physical address of the copy source</param>
 797          /// <param name="dstAddress">Physical address of the copy destination</param>
 798          /// <param name="size">Size in bytes of the copy</param>
 799          private void CopyBufferSingleRange(MemoryManager memoryManager, ulong srcAddress, ulong dstAddress, ulong size)
 800          {
 801              Buffer srcBuffer = GetBuffer(srcAddress, size, BufferStage.Copy);
 802              Buffer dstBuffer = GetBuffer(dstAddress, size, BufferStage.Copy);
 803  
 804              int srcOffset = (int)(srcAddress - srcBuffer.Address);
 805              int dstOffset = (int)(dstAddress - dstBuffer.Address);
 806  
 807              _context.Renderer.Pipeline.CopyBuffer(
 808                  srcBuffer.Handle,
 809                  dstBuffer.Handle,
 810                  srcOffset,
 811                  dstOffset,
 812                  (int)size);
 813  
 814              if (srcBuffer.IsModified(srcAddress, size))
 815              {
 816                  dstBuffer.SignalModified(dstAddress, size, BufferStage.Copy);
 817              }
 818              else
 819              {
 820                  // Optimization: If the data being copied is already in memory, then copy it directly instead of flushing from GPU.
 821  
 822                  dstBuffer.ClearModified(dstAddress, size);
 823                  memoryManager.Physical.WriteTrackedResource(dstAddress, memoryManager.Physical.GetSpan(srcAddress, (int)size), ResourceKind.Buffer);
 824              }
 825  
 826              dstBuffer.CopyToDependantVirtualBuffers(dstAddress, size);
 827          }
 828  
 829          /// <summary>
 830          /// Clears a buffer at a given address with the specified value.
 831          /// </summary>
 832          /// <remarks>
 833          /// Both the address and size must be aligned to 4 bytes.
 834          /// </remarks>
 835          /// <param name="memoryManager">GPU memory manager where the buffer is mapped</param>
 836          /// <param name="gpuVa">GPU virtual address of the region to clear</param>
 837          /// <param name="size">Number of bytes to clear</param>
 838          /// <param name="value">Value to be written into the buffer</param>
 839          public void ClearBuffer(MemoryManager memoryManager, ulong gpuVa, ulong size, uint value)
 840          {
 841              MultiRange range = TranslateAndCreateMultiBuffersPhysicalOnly(memoryManager, gpuVa, size, BufferStage.Copy);
 842  
 843              for (int index = 0; index < range.Count; index++)
 844              {
 845                  MemoryRange subRange = range.GetSubRange(index);
 846                  Buffer buffer = GetBuffer(subRange.Address, subRange.Size, BufferStage.Copy);
 847  
 848                  int offset = (int)(subRange.Address - buffer.Address);
 849  
 850                  _context.Renderer.Pipeline.ClearBuffer(buffer.Handle, offset, (int)subRange.Size, value);
 851  
 852                  memoryManager.Physical.FillTrackedResource(subRange.Address, subRange.Size, value, ResourceKind.Buffer);
 853  
 854                  buffer.CopyToDependantVirtualBuffers(subRange.Address, subRange.Size);
 855              }
 856          }
 857  
 858          /// <summary>
 859          /// Gets a buffer sub-range starting at a given memory address, aligned to the next page boundary.
 860          /// </summary>
 861          /// <param name="range">Physical regions of memory where the buffer is mapped</param>
 862          /// <param name="stage">Buffer stage that triggered the access</param>
 863          /// <param name="write">Whether the buffer will be written to by this use</param>
 864          /// <returns>The buffer sub-range starting at the given memory address</returns>
 865          public BufferRange GetBufferRangeAligned(MultiRange range, BufferStage stage, bool write = false)
 866          {
 867              if (range.Count > 1)
 868              {
 869                  return GetBuffer(range, stage, write).GetRange(range);
 870              }
 871              else
 872              {
 873                  MemoryRange subRange = range.GetSubRange(0);
 874                  return GetBuffer(subRange.Address, subRange.Size, stage, write).GetRangeAligned(subRange.Address, subRange.Size, write);
 875              }
 876          }
 877  
 878          /// <summary>
 879          /// Gets a buffer sub-range for a given memory range.
 880          /// </summary>
 881          /// <param name="range">Physical regions of memory where the buffer is mapped</param>
 882          /// <param name="stage">Buffer stage that triggered the access</param>
 883          /// <param name="write">Whether the buffer will be written to by this use</param>
 884          /// <returns>The buffer sub-range for the given range</returns>
 885          public BufferRange GetBufferRange(MultiRange range, BufferStage stage, bool write = false)
 886          {
 887              if (range.Count > 1)
 888              {
 889                  return GetBuffer(range, stage, write).GetRange(range);
 890              }
 891              else
 892              {
 893                  MemoryRange subRange = range.GetSubRange(0);
 894                  return GetBuffer(subRange.Address, subRange.Size, stage, write).GetRange(subRange.Address, subRange.Size, write);
 895              }
 896          }
 897  
 898          /// <summary>
 899          /// Gets a buffer for a given memory range.
 900          /// A buffer overlapping with the specified range is assumed to already exist on the cache.
 901          /// </summary>
 902          /// <param name="range">Physical regions of memory where the buffer is mapped</param>
 903          /// <param name="stage">Buffer stage that triggered the access</param>
 904          /// <param name="write">Whether the buffer will be written to by this use</param>
 905          /// <returns>The buffer where the range is fully contained</returns>
 906          private MultiRangeBuffer GetBuffer(MultiRange range, BufferStage stage, bool write = false)
 907          {
 908              for (int i = 0; i < range.Count; i++)
 909              {
 910                  MemoryRange subRange = range.GetSubRange(i);
 911  
 912                  Buffer subBuffer = _buffers.FindFirstOverlap(subRange.Address, subRange.Size);
 913  
 914                  subBuffer.SynchronizeMemory(subRange.Address, subRange.Size);
 915  
 916                  if (write)
 917                  {
 918                      subBuffer.SignalModified(subRange.Address, subRange.Size, stage);
 919                  }
 920              }
 921  
 922              MultiRangeBuffer[] overlaps = new MultiRangeBuffer[10];
 923  
 924              int overlapCount = _multiRangeBuffers.FindOverlaps(range, ref overlaps);
 925  
 926              MultiRangeBuffer buffer = null;
 927  
 928              for (int i = 0; i < overlapCount; i++)
 929              {
 930                  if (overlaps[i].Range.Contains(range))
 931                  {
 932                      buffer = overlaps[i];
 933                      break;
 934                  }
 935              }
 936  
 937              if (write && buffer != null && !_context.Capabilities.SupportsSparseBuffer)
 938              {
 939                  buffer.AddModifiedRegion(range, ++_virtualModifiedSequenceNumber);
 940              }
 941  
 942              return buffer;
 943          }
 944  
 945          /// <summary>
 946          /// Gets a buffer for a given memory range.
 947          /// A buffer overlapping with the specified range is assumed to already exist on the cache.
 948          /// </summary>
 949          /// <param name="address">Start address of the memory range</param>
 950          /// <param name="size">Size in bytes of the memory range</param>
 951          /// <param name="stage">Buffer stage that triggered the access</param>
 952          /// <param name="write">Whether the buffer will be written to by this use</param>
 953          /// <returns>The buffer where the range is fully contained</returns>
 954          private Buffer GetBuffer(ulong address, ulong size, BufferStage stage, bool write = false)
 955          {
 956              Buffer buffer;
 957  
 958              if (size != 0)
 959              {
 960                  buffer = _buffers.FindFirstOverlap(address, size);
 961  
 962                  buffer.CopyFromDependantVirtualBuffers();
 963                  buffer.SynchronizeMemory(address, size);
 964  
 965                  if (write)
 966                  {
 967                      buffer.SignalModified(address, size, stage);
 968                  }
 969              }
 970              else
 971              {
 972                  buffer = _buffers.FindFirstOverlap(address, 1);
 973              }
 974  
 975              return buffer;
 976          }
 977  
 978          /// <summary>
 979          /// Performs guest to host memory synchronization of a given memory range.
 980          /// </summary>
 981          /// <param name="range">Physical regions of memory where the buffer is mapped</param>
 982          public void SynchronizeBufferRange(MultiRange range)
 983          {
 984              if (range.Count == 1)
 985              {
 986                  MemoryRange subRange = range.GetSubRange(0);
 987                  SynchronizeBufferRange(subRange.Address, subRange.Size, copyBackVirtual: true);
 988              }
 989              else
 990              {
 991                  for (int index = 0; index < range.Count; index++)
 992                  {
 993                      MemoryRange subRange = range.GetSubRange(index);
 994                      SynchronizeBufferRange(subRange.Address, subRange.Size, copyBackVirtual: false);
 995                  }
 996              }
 997          }
 998  
 999          /// <summary>
1000          /// Performs guest to host memory synchronization of a given memory range.
1001          /// </summary>
1002          /// <param name="address">Start address of the memory range</param>
1003          /// <param name="size">Size in bytes of the memory range</param>
1004          /// <param name="copyBackVirtual">Whether virtual buffers that uses this buffer as backing memory should have its data copied back if modified</param>
1005          [MethodImpl(MethodImplOptions.AggressiveInlining)]
1006          private void SynchronizeBufferRange(ulong address, ulong size, bool copyBackVirtual)
1007          {
1008              if (size != 0)
1009              {
1010                  Buffer buffer = _buffers.FindFirstOverlap(address, size);
1011  
1012                  if (copyBackVirtual)
1013                  {
1014                      buffer.CopyFromDependantVirtualBuffers();
1015                  }
1016  
1017                  buffer.SynchronizeMemory(address, size);
1018              }
1019          }
1020  
1021          /// <summary>
1022          /// Signal that the given buffer's handle has changed,
1023          /// forcing rebind and any overlapping multi-range buffers to be recreated.
1024          /// </summary>
1025          /// <param name="buffer">The buffer that has changed handle</param>
1026          public void BufferBackingChanged(Buffer buffer)
1027          {
1028              NotifyBuffersModified?.Invoke();
1029  
1030              RecreateMultiRangeBuffers(buffer.Address, buffer.Size);
1031          }
1032  
1033          /// <summary>
1034          /// Prune any invalid entries from a quick access dictionary.
1035          /// </summary>
1036          /// <param name="dictionary">Dictionary to prune</param>
1037          /// <param name="toDelete">List used to track entries to delete</param>
1038          private static void Prune(Dictionary<ulong, BufferCacheEntry> dictionary, ref List<ulong> toDelete)
1039          {
1040              foreach (var entry in dictionary)
1041              {
1042                  if (entry.Value.UnmappedSequence != entry.Value.Buffer.UnmappedSequence)
1043                  {
1044                      (toDelete ??= new()).Add(entry.Key);
1045                  }
1046              }
1047  
1048              if (toDelete != null)
1049              {
1050                  foreach (ulong entry in toDelete)
1051                  {
1052                      dictionary.Remove(entry);
1053                  }
1054              }
1055          }
1056  
1057          /// <summary>
1058          /// Prune any invalid entries from the quick access dictionaries.
1059          /// </summary>
1060          private void Prune()
1061          {
1062              List<ulong> toDelete = null;
1063  
1064              Prune(_dirtyCache, ref toDelete);
1065  
1066              toDelete?.Clear();
1067  
1068              Prune(_modifiedCache, ref toDelete);
1069  
1070              _pruneCaches = false;
1071          }
1072  
1073          /// <summary>
1074          /// Queues a prune of invalid entries the next time a dictionary cache is accessed.
1075          /// </summary>
1076          public void QueuePrune()
1077          {
1078              _pruneCaches = true;
1079          }
1080  
1081          /// <summary>
1082          /// Disposes all buffers in the cache.
1083          /// It's an error to use the buffer cache after disposal.
1084          /// </summary>
1085          public void Dispose()
1086          {
1087              lock (_buffers)
1088              {
1089                  foreach (Buffer buffer in _buffers)
1090                  {
1091                      buffer.Dispose();
1092                  }
1093              }
1094          }
1095      }
1096  }