1  using Ryujinx.Graphics.GAL;
  2  using System.Collections.Generic;
  3  
  4  namespace Ryujinx.Graphics.Gpu.Memory
  5  {
  6      /// <summary>
  7      /// Represents the GPU counter cache.
  8      /// </summary>
  9      class CounterCache
 10      {
 11          private readonly struct CounterEntry
 12          {
 13              public ulong Address { get; }
 14              public ICounterEvent Event { get; }
 15  
 16              public CounterEntry(ulong address, ICounterEvent evt)
 17              {
 18                  Address = address;
 19                  Event = evt;
 20              }
 21          }
 22  
 23          private readonly List<CounterEntry> _items;
 24  
 25          /// <summary>
 26          /// Creates a new instance of the GPU counter cache.
 27          /// </summary>
 28          public CounterCache()
 29          {
 30              _items = new List<CounterEntry>();
 31          }
 32  
 33          /// <summary>
 34          /// Adds a new counter to the counter cache, or updates a existing one.
 35          /// </summary>
 36          /// <param name="gpuVa">GPU virtual address where the counter will be written in memory</param>
 37          /// <param name="evt">The new counter</param>
 38          public void AddOrUpdate(ulong gpuVa, ICounterEvent evt)
 39          {
 40              int index = BinarySearch(gpuVa);
 41  
 42              CounterEntry entry = new(gpuVa, evt);
 43  
 44              if (index < 0)
 45              {
 46                  _items.Insert(~index, entry);
 47              }
 48              else
 49              {
 50                  _items[index] = entry;
 51              }
 52          }
 53  
 54          /// <summary>
 55          /// Handles removal of counters written to a memory region being unmapped.
 56          /// </summary>
 57          /// <param name="sender">Sender object</param>
 58          /// <param name="e">Event arguments</param>
 59          public void MemoryUnmappedHandler(object sender, UnmapEventArgs e) => RemoveRange(e.Address, e.Size);
 60  
 61          private void RemoveRange(ulong gpuVa, ulong size)
 62          {
 63              int index = BinarySearch(gpuVa + size - 1);
 64  
 65              if (index < 0)
 66              {
 67                  index = ~index;
 68              }
 69  
 70              if (index >= _items.Count || !InRange(gpuVa, size, _items[index].Address))
 71              {
 72                  return;
 73              }
 74  
 75              int count = 1;
 76  
 77              while (index > 0 && InRange(gpuVa, size, _items[index - 1].Address))
 78              {
 79                  index--;
 80                  count++;
 81              }
 82  
 83              // Notify the removed counter events that their result should no longer be written out.
 84              for (int i = 0; i < count; i++)
 85              {
 86                  ICounterEvent evt = _items[index + i].Event;
 87                  if (evt != null)
 88                  {
 89                      evt.Invalid = true;
 90                  }
 91              }
 92  
 93              _items.RemoveRange(index, count);
 94          }
 95  
 96          /// <summary>
 97          /// Checks whenever an address falls inside a given range.
 98          /// </summary>
 99          /// <param name="startVa">Range start address</param>
100          /// <param name="size">Range size</param>
101          /// <param name="gpuVa">Address being checked</param>
102          /// <returns>True if the address falls inside the range, false otherwise</returns>
103          private static bool InRange(ulong startVa, ulong size, ulong gpuVa)
104          {
105              return gpuVa >= startVa && gpuVa < startVa + size;
106          }
107  
108          /// <summary>
109          /// Check if any counter value was written to the specified GPU virtual memory address.
110          /// </summary>
111          /// <param name="gpuVa">GPU virtual address</param>
112          /// <returns>True if any counter value was written on the specified address, false otherwise</returns>
113          public bool Contains(ulong gpuVa)
114          {
115              return BinarySearch(gpuVa) >= 0;
116          }
117  
118          /// <summary>
119          /// Flush any counter value written to the specified GPU virtual memory address.
120          /// </summary>
121          /// <param name="gpuVa">GPU virtual address</param>
122          /// <returns>True if any counter value was written on the specified address, false otherwise</returns>
123          public bool FindAndFlush(ulong gpuVa)
124          {
125              int index = BinarySearch(gpuVa);
126              if (index > 0)
127              {
128                  _items[index].Event?.Flush();
129  
130                  return true;
131              }
132              else
133              {
134                  return false;
135              }
136          }
137  
138          /// <summary>
139          /// Find any counter event that would write to the specified GPU virtual memory address.
140          /// </summary>
141          /// <param name="gpuVa">GPU virtual address</param>
142          /// <returns>The counter event, or null if not present</returns>
143          public ICounterEvent FindEvent(ulong gpuVa)
144          {
145              int index = BinarySearch(gpuVa);
146              if (index > 0)
147              {
148                  return _items[index].Event;
149              }
150              else
151              {
152                  return null;
153              }
154          }
155  
156          /// <summary>
157          /// Performs binary search of an address on the list.
158          /// </summary>
159          /// <param name="address">Address to search</param>
160          /// <returns>Index of the item, or complement of the index of the nearest item with lower value</returns>
161          private int BinarySearch(ulong address)
162          {
163              int left = 0;
164              int right = _items.Count - 1;
165  
166              while (left <= right)
167              {
168                  int range = right - left;
169  
170                  int middle = left + (range >> 1);
171  
172                  CounterEntry item = _items[middle];
173  
174                  if (item.Address == address)
175                  {
176                      return middle;
177                  }
178  
179                  if (address < item.Address)
180                  {
181                      right = middle - 1;
182                  }
183                  else
184                  {
185                      left = middle + 1;
186                  }
187              }
188  
189              return ~left;
190          }
191      }
192  }