BufferModifiedRangeList.cs
1 using Ryujinx.Common.Pools; 2 using Ryujinx.Memory.Range; 3 using System; 4 using System.Linq; 5 6 namespace Ryujinx.Graphics.Gpu.Memory 7 { 8 /// <summary> 9 /// A range within a buffer that has been modified by the GPU. 10 /// </summary> 11 class BufferModifiedRange : IRange 12 { 13 /// <summary> 14 /// Start address of the range in guest memory. 15 /// </summary> 16 public ulong Address { get; } 17 18 /// <summary> 19 /// Size of the range in bytes. 20 /// </summary> 21 public ulong Size { get; } 22 23 /// <summary> 24 /// End address of the range in guest memory. 25 /// </summary> 26 public ulong EndAddress => Address + Size; 27 28 /// <summary> 29 /// The GPU sync number at the time of the last modification. 30 /// </summary> 31 public ulong SyncNumber { get; internal set; } 32 33 /// <summary> 34 /// The range list that originally owned this range. 35 /// </summary> 36 public BufferModifiedRangeList Parent { get; internal set; } 37 38 /// <summary> 39 /// Creates a new instance of a modified range. 40 /// </summary> 41 /// <param name="address">Start address of the range</param> 42 /// <param name="size">Size of the range in bytes</param> 43 /// <param name="syncNumber">The GPU sync number at the time of creation</param> 44 /// <param name="parent">The range list that owns this range</param> 45 public BufferModifiedRange(ulong address, ulong size, ulong syncNumber, BufferModifiedRangeList parent) 46 { 47 Address = address; 48 Size = size; 49 SyncNumber = syncNumber; 50 Parent = parent; 51 } 52 53 /// <summary> 54 /// Checks if a given range overlaps with the modified range. 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 /// <summary> 66 /// A structure used to track GPU modified ranges within a buffer. 67 /// </summary> 68 class BufferModifiedRangeList : RangeList<BufferModifiedRange> 69 { 70 private const int BackingInitialSize = 8; 71 72 private readonly GpuContext _context; 73 private readonly Buffer _parent; 74 private readonly BufferFlushAction _flushAction; 75 76 private BufferMigration _source; 77 private BufferModifiedRangeList _migrationTarget; 78 79 private readonly object _lock = new(); 80 81 /// <summary> 82 /// Whether the modified range list has any entries or not. 83 /// </summary> 84 public bool HasRanges 85 { 86 get 87 { 88 lock (_lock) 89 { 90 return Count > 0; 91 } 92 } 93 } 94 95 /// <summary> 96 /// Creates a new instance of a modified range list. 97 /// </summary> 98 /// <param name="context">GPU context that the buffer range list belongs to</param> 99 /// <param name="parent">The parent buffer that owns this range list</param> 100 /// <param name="flushAction">The flush action for the parent buffer</param> 101 public BufferModifiedRangeList(GpuContext context, Buffer parent, BufferFlushAction flushAction) : base(BackingInitialSize) 102 { 103 _context = context; 104 _parent = parent; 105 _flushAction = flushAction; 106 } 107 108 /// <summary> 109 /// Given an input range, calls the given action with sub-ranges which exclude any of the modified regions. 110 /// </summary> 111 /// <param name="address">Start address of the query range</param> 112 /// <param name="size">Size of the query range in bytes</param> 113 /// <param name="action">Action to perform for each remaining sub-range of the input range</param> 114 public void ExcludeModifiedRegions(ulong address, ulong size, Action<ulong, ulong> action) 115 { 116 lock (_lock) 117 { 118 // Slices a given region using the modified regions in the list. Calls the action for the new slices. 119 ref var overlaps = ref ThreadStaticArray<BufferModifiedRange>.Get(); 120 121 int count = FindOverlapsNonOverlapping(address, size, ref overlaps); 122 123 for (int i = 0; i < count; i++) 124 { 125 BufferModifiedRange overlap = overlaps[i]; 126 127 if (overlap.Address > address) 128 { 129 // The start of the remaining region is uncovered by this overlap. Call the action for it. 130 action(address, overlap.Address - address); 131 } 132 133 // Remaining region is after this overlap. 134 size -= overlap.EndAddress - address; 135 address = overlap.EndAddress; 136 } 137 138 if ((long)size > 0) 139 { 140 // If there is any region left after removing the overlaps, signal it. 141 action(address, size); 142 } 143 } 144 } 145 146 /// <summary> 147 /// Signal that a region of the buffer has been modified, and add the new region to the range list. 148 /// Any overlapping ranges will be (partially) removed. 149 /// </summary> 150 /// <param name="address">Start address of the modified region</param> 151 /// <param name="size">Size of the modified region in bytes</param> 152 public void SignalModified(ulong address, ulong size) 153 { 154 // Must lock, as this can affect flushes from the background thread. 155 lock (_lock) 156 { 157 // We may overlap with some existing modified regions. They must be cut into by the new entry. 158 ref var overlaps = ref ThreadStaticArray<BufferModifiedRange>.Get(); 159 160 int count = FindOverlapsNonOverlapping(address, size, ref overlaps); 161 162 ulong endAddress = address + size; 163 ulong syncNumber = _context.SyncNumber; 164 165 for (int i = 0; i < count; i++) 166 { 167 // The overlaps must be removed or split. 168 169 BufferModifiedRange overlap = overlaps[i]; 170 171 if (overlap.Address == address && overlap.Size == size) 172 { 173 // Region already exists. Just update the existing sync number. 174 overlap.SyncNumber = syncNumber; 175 overlap.Parent = this; 176 177 return; 178 } 179 180 Remove(overlap); 181 182 if (overlap.Address < address && overlap.EndAddress > address) 183 { 184 // A split item must be created behind this overlap. 185 186 Add(new BufferModifiedRange(overlap.Address, address - overlap.Address, overlap.SyncNumber, overlap.Parent)); 187 } 188 189 if (overlap.Address < endAddress && overlap.EndAddress > endAddress) 190 { 191 // A split item must be created after this overlap. 192 193 Add(new BufferModifiedRange(endAddress, overlap.EndAddress - endAddress, overlap.SyncNumber, overlap.Parent)); 194 } 195 } 196 197 Add(new BufferModifiedRange(address, size, syncNumber, this)); 198 } 199 } 200 201 /// <summary> 202 /// Gets modified ranges within the specified region, and then fires the given action for each range individually. 203 /// </summary> 204 /// <param name="address">Start address to query</param> 205 /// <param name="size">Size to query</param> 206 /// <param name="syncNumber">Sync number required for a range to be signalled</param> 207 /// <param name="rangeAction">The action to call for each modified range</param> 208 public void GetRangesAtSync(ulong address, ulong size, ulong syncNumber, Action<ulong, ulong> rangeAction) 209 { 210 int count = 0; 211 212 ref var overlaps = ref ThreadStaticArray<BufferModifiedRange>.Get(); 213 214 // Range list must be consistent for this operation. 215 lock (_lock) 216 { 217 count = FindOverlapsNonOverlapping(address, size, ref overlaps); 218 } 219 220 for (int i = 0; i < count; i++) 221 { 222 BufferModifiedRange overlap = overlaps[i]; 223 224 if (overlap.SyncNumber == syncNumber) 225 { 226 rangeAction(overlap.Address, overlap.Size); 227 } 228 } 229 } 230 231 /// <summary> 232 /// Gets modified ranges within the specified region, and then fires the given action for each range individually. 233 /// </summary> 234 /// <param name="address">Start address to query</param> 235 /// <param name="size">Size to query</param> 236 /// <param name="rangeAction">The action to call for each modified range</param> 237 public void GetRanges(ulong address, ulong size, Action<ulong, ulong> rangeAction) 238 { 239 int count = 0; 240 241 ref var overlaps = ref ThreadStaticArray<BufferModifiedRange>.Get(); 242 243 // Range list must be consistent for this operation. 244 lock (_lock) 245 { 246 count = FindOverlapsNonOverlapping(address, size, ref overlaps); 247 } 248 249 for (int i = 0; i < count; i++) 250 { 251 BufferModifiedRange overlap = overlaps[i]; 252 rangeAction(overlap.Address, overlap.Size); 253 } 254 } 255 256 /// <summary> 257 /// Queries if a range exists within the specified region. 258 /// </summary> 259 /// <param name="address">Start address to query</param> 260 /// <param name="size">Size to query</param> 261 /// <returns>True if a range exists in the specified region, false otherwise</returns> 262 public bool HasRange(ulong address, ulong size) 263 { 264 // Range list must be consistent for this operation. 265 lock (_lock) 266 { 267 return FindOverlapsNonOverlapping(address, size, ref ThreadStaticArray<BufferModifiedRange>.Get()) > 0; 268 } 269 } 270 271 /// <summary> 272 /// Performs the given range action, or one from a migration that overlaps and has not synced yet. 273 /// </summary> 274 /// <param name="offset">The offset to pass to the action</param> 275 /// <param name="size">The size to pass to the action</param> 276 /// <param name="syncNumber">The sync number that has been reached</param> 277 /// <param name="rangeAction">The action to perform</param> 278 public void RangeActionWithMigration(ulong offset, ulong size, ulong syncNumber, BufferFlushAction rangeAction) 279 { 280 if (_source != null) 281 { 282 _source.RangeActionWithMigration(offset, size, syncNumber, rangeAction); 283 } 284 else 285 { 286 rangeAction(offset, size, syncNumber); 287 } 288 } 289 290 /// <summary> 291 /// Removes modified ranges ready by the sync number from the list, and flushes their buffer data within a given address range. 292 /// </summary> 293 /// <param name="overlaps">Overlapping ranges to check</param> 294 /// <param name="rangeCount">Number of overlapping ranges</param> 295 /// <param name="highestDiff">The highest difference between an overlapping range's sync number and the current one</param> 296 /// <param name="currentSync">The current sync number</param> 297 /// <param name="address">The start address of the flush range</param> 298 /// <param name="endAddress">The end address of the flush range</param> 299 private void RemoveRangesAndFlush( 300 BufferModifiedRange[] overlaps, 301 int rangeCount, 302 long highestDiff, 303 ulong currentSync, 304 ulong address, 305 ulong endAddress) 306 { 307 lock (_lock) 308 { 309 if (_migrationTarget == null) 310 { 311 ulong waitSync = currentSync + (ulong)highestDiff; 312 313 for (int i = 0; i < rangeCount; i++) 314 { 315 BufferModifiedRange overlap = overlaps[i]; 316 317 long diff = (long)(overlap.SyncNumber - currentSync); 318 319 if (diff <= highestDiff) 320 { 321 ulong clampAddress = Math.Max(address, overlap.Address); 322 ulong clampEnd = Math.Min(endAddress, overlap.EndAddress); 323 324 ClearPart(overlap, clampAddress, clampEnd); 325 326 RangeActionWithMigration(clampAddress, clampEnd - clampAddress, waitSync, _flushAction); 327 } 328 } 329 330 return; 331 } 332 } 333 334 // There is a migration target to call instead. This can't be changed after set so accessing it outside the lock is fine. 335 336 _migrationTarget.RemoveRangesAndFlush(overlaps, rangeCount, highestDiff, currentSync, address, endAddress); 337 } 338 339 /// <summary> 340 /// Gets modified ranges within the specified region, waits on ones from a previous sync number, 341 /// and then fires the flush action for each range individually. 342 /// </summary> 343 /// <remarks> 344 /// This function assumes it is called from the background thread. 345 /// Modifications from the current sync number are ignored because the guest should not expect them to be available yet. 346 /// They will remain reserved, so that any data sync prioritizes the data in the GPU. 347 /// </remarks> 348 /// <param name="address">Start address to query</param> 349 /// <param name="size">Size to query</param> 350 public void WaitForAndFlushRanges(ulong address, ulong size) 351 { 352 ulong endAddress = address + size; 353 ulong currentSync = _context.SyncNumber; 354 355 int rangeCount = 0; 356 357 ref var overlaps = ref ThreadStaticArray<BufferModifiedRange>.Get(); 358 359 // Range list must be consistent for this operation 360 lock (_lock) 361 { 362 if (_migrationTarget != null) 363 { 364 rangeCount = -1; 365 } 366 else 367 { 368 rangeCount = FindOverlapsNonOverlapping(address, size, ref overlaps); 369 } 370 } 371 372 if (rangeCount == -1) 373 { 374 _migrationTarget.WaitForAndFlushRanges(address, size); 375 376 return; 377 } 378 else if (rangeCount == 0) 379 { 380 return; 381 } 382 383 // First, determine which syncpoint to wait on. 384 // This is the latest syncpoint that is not equal to the current sync. 385 386 long highestDiff = long.MinValue; 387 388 for (int i = 0; i < rangeCount; i++) 389 { 390 BufferModifiedRange overlap = overlaps[i]; 391 392 long diff = (long)(overlap.SyncNumber - currentSync); 393 394 if (diff < 0 && diff > highestDiff) 395 { 396 highestDiff = diff; 397 } 398 } 399 400 if (highestDiff == long.MinValue) 401 { 402 return; 403 } 404 405 // Wait for the syncpoint. 406 _context.Renderer.WaitSync(currentSync + (ulong)highestDiff); 407 408 RemoveRangesAndFlush(overlaps, rangeCount, highestDiff, currentSync, address, endAddress); 409 } 410 411 /// <summary> 412 /// Inherit ranges from another modified range list. 413 /// </summary> 414 /// <remarks> 415 /// Assumes that ranges will be inherited in address ascending order. 416 /// </remarks> 417 /// <param name="ranges">The range list to inherit from</param> 418 /// <param name="registerRangeAction">The action to call for each modified range</param> 419 public void InheritRanges(BufferModifiedRangeList ranges, Action<ulong, ulong> registerRangeAction) 420 { 421 BufferModifiedRange[] inheritRanges; 422 423 lock (ranges._lock) 424 { 425 inheritRanges = ranges.ToArray(); 426 427 lock (_lock) 428 { 429 // Copy over the migration from the previous range list 430 431 BufferMigration oldMigration = ranges._source; 432 433 BufferMigrationSpan span = new BufferMigrationSpan(ranges._parent, ranges._flushAction, oldMigration); 434 ranges._parent.IncrementReferenceCount(); 435 436 if (_source == null) 437 { 438 // Create a new migration. 439 _source = new BufferMigration(new BufferMigrationSpan[] { span }, this, _context.SyncNumber); 440 441 _context.RegisterBufferMigration(_source); 442 } 443 else 444 { 445 // Extend the migration 446 _source.AddSpanToEnd(span); 447 } 448 449 ranges._migrationTarget = this; 450 451 foreach (BufferModifiedRange range in inheritRanges) 452 { 453 Add(range); 454 } 455 } 456 } 457 458 ulong currentSync = _context.SyncNumber; 459 foreach (BufferModifiedRange range in inheritRanges) 460 { 461 if (range.SyncNumber != currentSync) 462 { 463 registerRangeAction(range.Address, range.Size); 464 } 465 } 466 } 467 468 /// <summary> 469 /// Register a migration from previous buffer storage. This migration is from a snapshot of the buffer's 470 /// current handle to its handle in the future, and is assumed to be complete when the sync action completes. 471 /// When the migration completes, the handle is disposed. 472 /// </summary> 473 public void SelfMigration() 474 { 475 lock (_lock) 476 { 477 BufferMigrationSpan span = new(_parent, _parent.GetSnapshotDisposeAction(), _parent.GetSnapshotFlushAction(), _source); 478 BufferMigration migration = new(new BufferMigrationSpan[] { span }, this, _context.SyncNumber); 479 480 // Migration target is used to redirect flush actions to the latest range list, 481 // so we don't need to set it here. (this range list is still the latest) 482 483 _context.RegisterBufferMigration(migration); 484 485 _source = migration; 486 } 487 } 488 489 /// <summary> 490 /// Removes a source buffer migration, indicating its copy has completed. 491 /// </summary> 492 /// <param name="migration">The migration to remove</param> 493 public void RemoveMigration(BufferMigration migration) 494 { 495 lock (_lock) 496 { 497 if (_source == migration) 498 { 499 _source = null; 500 } 501 } 502 } 503 504 private void ClearPart(BufferModifiedRange overlap, ulong address, ulong endAddress) 505 { 506 Remove(overlap); 507 508 // If the overlap extends outside of the clear range, make sure those parts still exist. 509 510 if (overlap.Address < address) 511 { 512 Add(new BufferModifiedRange(overlap.Address, address - overlap.Address, overlap.SyncNumber, overlap.Parent)); 513 } 514 515 if (overlap.EndAddress > endAddress) 516 { 517 Add(new BufferModifiedRange(endAddress, overlap.EndAddress - endAddress, overlap.SyncNumber, overlap.Parent)); 518 } 519 } 520 521 /// <summary> 522 /// Clear modified ranges within the specified area. 523 /// </summary> 524 /// <param name="address">Start address to clear</param> 525 /// <param name="size">Size to clear</param> 526 public void Clear(ulong address, ulong size) 527 { 528 lock (_lock) 529 { 530 // This function can be called from any thread, so it cannot use the arrays for background or foreground. 531 BufferModifiedRange[] toClear = new BufferModifiedRange[1]; 532 533 int rangeCount = FindOverlapsNonOverlapping(address, size, ref toClear); 534 535 ulong endAddress = address + size; 536 537 for (int i = 0; i < rangeCount; i++) 538 { 539 BufferModifiedRange overlap = toClear[i]; 540 541 ClearPart(overlap, address, endAddress); 542 } 543 } 544 } 545 546 /// <summary> 547 /// Clear all modified ranges. 548 /// </summary> 549 public void Clear() 550 { 551 lock (_lock) 552 { 553 Count = 0; 554 } 555 } 556 } 557 }