1  using Ryujinx.Common;
  2  using Silk.NET.Vulkan;
  3  using System;
  4  using System.Collections.Generic;
  5  using System.Diagnostics;
  6  using System.Threading;
  7  
  8  namespace Ryujinx.Graphics.Vulkan
  9  {
 10      class MemoryAllocatorBlockList : IDisposable
 11      {
 12          private const ulong InvalidOffset = ulong.MaxValue;
 13  
 14          public class Block : IComparable<Block>
 15          {
 16              public DeviceMemory Memory { get; private set; }
 17              public IntPtr HostPointer { get; private set; }
 18              public ulong Size { get; }
 19              public bool Mapped => HostPointer != IntPtr.Zero;
 20  
 21              private readonly struct Range : IComparable<Range>
 22              {
 23                  public ulong Offset { get; }
 24                  public ulong Size { get; }
 25  
 26                  public Range(ulong offset, ulong size)
 27                  {
 28                      Offset = offset;
 29                      Size = size;
 30                  }
 31  
 32                  public int CompareTo(Range other)
 33                  {
 34                      return Offset.CompareTo(other.Offset);
 35                  }
 36              }
 37  
 38              private readonly List<Range> _freeRanges;
 39  
 40              public Block(DeviceMemory memory, IntPtr hostPointer, ulong size)
 41              {
 42                  Memory = memory;
 43                  HostPointer = hostPointer;
 44                  Size = size;
 45                  _freeRanges = new List<Range>
 46                  {
 47                      new Range(0, size),
 48                  };
 49              }
 50  
 51              public ulong Allocate(ulong size, ulong alignment)
 52              {
 53                  for (int i = 0; i < _freeRanges.Count; i++)
 54                  {
 55                      var range = _freeRanges[i];
 56  
 57                      ulong alignedOffset = BitUtils.AlignUp(range.Offset, alignment);
 58                      ulong sizeDelta = alignedOffset - range.Offset;
 59                      ulong usableSize = range.Size - sizeDelta;
 60  
 61                      if (sizeDelta < range.Size && usableSize >= size)
 62                      {
 63                          _freeRanges.RemoveAt(i);
 64  
 65                          if (sizeDelta != 0)
 66                          {
 67                              InsertFreeRange(range.Offset, sizeDelta);
 68                          }
 69  
 70                          ulong endOffset = range.Offset + range.Size;
 71                          ulong remainingSize = endOffset - (alignedOffset + size);
 72                          if (remainingSize != 0)
 73                          {
 74                              InsertFreeRange(endOffset - remainingSize, remainingSize);
 75                          }
 76  
 77                          return alignedOffset;
 78                      }
 79                  }
 80  
 81                  return InvalidOffset;
 82              }
 83  
 84              public void Free(ulong offset, ulong size)
 85              {
 86                  InsertFreeRangeComingled(offset, size);
 87              }
 88  
 89              private void InsertFreeRange(ulong offset, ulong size)
 90              {
 91                  var range = new Range(offset, size);
 92                  int index = _freeRanges.BinarySearch(range);
 93                  if (index < 0)
 94                  {
 95                      index = ~index;
 96                  }
 97  
 98                  _freeRanges.Insert(index, range);
 99              }
100  
101              private void InsertFreeRangeComingled(ulong offset, ulong size)
102              {
103                  ulong endOffset = offset + size;
104                  var range = new Range(offset, size);
105                  int index = _freeRanges.BinarySearch(range);
106                  if (index < 0)
107                  {
108                      index = ~index;
109                  }
110  
111                  if (index < _freeRanges.Count && _freeRanges[index].Offset == endOffset)
112                  {
113                      endOffset = _freeRanges[index].Offset + _freeRanges[index].Size;
114                      _freeRanges.RemoveAt(index);
115                  }
116  
117                  if (index > 0 && _freeRanges[index - 1].Offset + _freeRanges[index - 1].Size == offset)
118                  {
119                      offset = _freeRanges[index - 1].Offset;
120                      _freeRanges.RemoveAt(--index);
121                  }
122  
123                  range = new Range(offset, endOffset - offset);
124  
125                  _freeRanges.Insert(index, range);
126              }
127  
128              public bool IsTotallyFree()
129              {
130                  if (_freeRanges.Count == 1 && _freeRanges[0].Size == Size)
131                  {
132                      Debug.Assert(_freeRanges[0].Offset == 0);
133                      return true;
134                  }
135  
136                  return false;
137              }
138  
139              public int CompareTo(Block other)
140              {
141                  return Size.CompareTo(other.Size);
142              }
143  
144              public unsafe void Destroy(Vk api, Device device)
145              {
146                  if (Mapped)
147                  {
148                      api.UnmapMemory(device, Memory);
149                      HostPointer = IntPtr.Zero;
150                  }
151  
152                  if (Memory.Handle != 0)
153                  {
154                      api.FreeMemory(device, Memory, null);
155                      Memory = default;
156                  }
157              }
158          }
159  
160          private readonly List<Block> _blocks;
161  
162          private readonly Vk _api;
163          private readonly Device _device;
164  
165          public int MemoryTypeIndex { get; }
166          public bool ForBuffer { get; }
167  
168          private readonly int _blockAlignment;
169  
170          private readonly ReaderWriterLockSlim _lock;
171  
172          public MemoryAllocatorBlockList(Vk api, Device device, int memoryTypeIndex, int blockAlignment, bool forBuffer)
173          {
174              _blocks = new List<Block>();
175              _api = api;
176              _device = device;
177              MemoryTypeIndex = memoryTypeIndex;
178              ForBuffer = forBuffer;
179              _blockAlignment = blockAlignment;
180              _lock = new(LockRecursionPolicy.NoRecursion);
181          }
182  
183          public unsafe MemoryAllocation Allocate(ulong size, ulong alignment, bool map)
184          {
185              // Ensure we have a sane alignment value.
186              if ((ulong)(int)alignment != alignment || (int)alignment <= 0)
187              {
188                  throw new ArgumentOutOfRangeException(nameof(alignment), $"Invalid alignment 0x{alignment:X}.");
189              }
190  
191              _lock.EnterReadLock();
192  
193              try
194              {
195                  for (int i = 0; i < _blocks.Count; i++)
196                  {
197                      var block = _blocks[i];
198  
199                      if (block.Mapped == map && block.Size >= size)
200                      {
201                          ulong offset = block.Allocate(size, alignment);
202                          if (offset != InvalidOffset)
203                          {
204                              return new MemoryAllocation(this, block, block.Memory, GetHostPointer(block, offset), offset, size);
205                          }
206                      }
207                  }
208              }
209              finally
210              {
211                  _lock.ExitReadLock();
212              }
213  
214              ulong blockAlignedSize = BitUtils.AlignUp(size, (ulong)_blockAlignment);
215  
216              var memoryAllocateInfo = new MemoryAllocateInfo
217              {
218                  SType = StructureType.MemoryAllocateInfo,
219                  AllocationSize = blockAlignedSize,
220                  MemoryTypeIndex = (uint)MemoryTypeIndex,
221              };
222  
223              _api.AllocateMemory(_device, in memoryAllocateInfo, null, out var deviceMemory).ThrowOnError();
224  
225              IntPtr hostPointer = IntPtr.Zero;
226  
227              if (map)
228              {
229                  void* pointer = null;
230                  _api.MapMemory(_device, deviceMemory, 0, blockAlignedSize, 0, ref pointer).ThrowOnError();
231                  hostPointer = (IntPtr)pointer;
232              }
233  
234              var newBlock = new Block(deviceMemory, hostPointer, blockAlignedSize);
235  
236              InsertBlock(newBlock);
237  
238              ulong newBlockOffset = newBlock.Allocate(size, alignment);
239              Debug.Assert(newBlockOffset != InvalidOffset);
240  
241              return new MemoryAllocation(this, newBlock, deviceMemory, GetHostPointer(newBlock, newBlockOffset), newBlockOffset, size);
242          }
243  
244          private static IntPtr GetHostPointer(Block block, ulong offset)
245          {
246              if (block.HostPointer == IntPtr.Zero)
247              {
248                  return IntPtr.Zero;
249              }
250  
251              return (IntPtr)((nuint)block.HostPointer + offset);
252          }
253  
254          public void Free(Block block, ulong offset, ulong size)
255          {
256              block.Free(offset, size);
257  
258              if (block.IsTotallyFree())
259              {
260                  _lock.EnterWriteLock();
261  
262                  try
263                  {
264                      for (int i = 0; i < _blocks.Count; i++)
265                      {
266                          if (_blocks[i] == block)
267                          {
268                              _blocks.RemoveAt(i);
269                              break;
270                          }
271                      }
272                  }
273                  finally
274                  {
275                      _lock.ExitWriteLock();
276                  }
277  
278                  block.Destroy(_api, _device);
279              }
280          }
281  
282          private void InsertBlock(Block block)
283          {
284              _lock.EnterWriteLock();
285  
286              try
287              {
288                  int index = _blocks.BinarySearch(block);
289                  if (index < 0)
290                  {
291                      index = ~index;
292                  }
293  
294                  _blocks.Insert(index, block);
295              }
296              finally
297              {
298                  _lock.ExitWriteLock();
299              }
300          }
301  
302          public void Dispose()
303          {
304              for (int i = 0; i < _blocks.Count; i++)
305              {
306                  _blocks[i].Destroy(_api, _device);
307              }
308          }
309      }
310  }