1  using Ryujinx.Common;
  2  using System;
  3  using System.Collections.Generic;
  4  using System.Diagnostics;
  5  
  6  namespace Ryujinx.Horizon
  7  {
  8      class HeapAllocator
  9      {
 10          private const ulong InvalidAddress = ulong.MaxValue;
 11  
 12          private readonly struct Range : IComparable<Range>
 13          {
 14              public ulong Offset { get; }
 15              public ulong Size { get; }
 16  
 17              public Range(ulong offset, ulong size)
 18              {
 19                  Offset = offset;
 20                  Size = size;
 21              }
 22  
 23              public int CompareTo(Range other)
 24              {
 25                  return Offset.CompareTo(other.Offset);
 26              }
 27          }
 28  
 29          private readonly List<Range> _freeRanges;
 30          private ulong _currentHeapSize;
 31  
 32          public HeapAllocator()
 33          {
 34              _freeRanges = new List<Range>();
 35              _currentHeapSize = 0;
 36          }
 37  
 38          public ulong Allocate(ulong size, ulong alignment = 1UL)
 39          {
 40              ulong address = AllocateImpl(size, alignment);
 41  
 42              if (address == InvalidAddress)
 43              {
 44                  ExpandHeap(size + alignment - 1UL);
 45  
 46                  address = AllocateImpl(size, alignment);
 47  
 48                  Debug.Assert(address != InvalidAddress);
 49              }
 50  
 51              return address;
 52          }
 53  
 54          private void ExpandHeap(ulong expansionSize)
 55          {
 56              ulong oldHeapSize = _currentHeapSize;
 57              ulong newHeapSize = BitUtils.AlignUp(oldHeapSize + expansionSize, 0x200000UL);
 58  
 59              _currentHeapSize = newHeapSize;
 60  
 61              HorizonStatic.Syscall.SetHeapSize(out ulong heapAddress, newHeapSize).AbortOnFailure();
 62  
 63              Free(heapAddress + oldHeapSize, newHeapSize - oldHeapSize);
 64          }
 65  
 66          private ulong AllocateImpl(ulong size, ulong alignment)
 67          {
 68              for (int i = 0; i < _freeRanges.Count; i++)
 69              {
 70                  var range = _freeRanges[i];
 71  
 72                  ulong alignedOffset = BitUtils.AlignUp(range.Offset, alignment);
 73                  ulong sizeDelta = alignedOffset - range.Offset;
 74                  ulong usableSize = range.Size - sizeDelta;
 75  
 76                  if (sizeDelta < range.Size && usableSize >= size)
 77                  {
 78                      _freeRanges.RemoveAt(i);
 79  
 80                      if (sizeDelta != 0)
 81                      {
 82                          InsertFreeRange(range.Offset, sizeDelta);
 83                      }
 84  
 85                      ulong endOffset = range.Offset + range.Size;
 86                      ulong remainingSize = endOffset - (alignedOffset + size);
 87                      if (remainingSize != 0)
 88                      {
 89                          InsertFreeRange(endOffset - remainingSize, remainingSize);
 90                      }
 91  
 92                      return alignedOffset;
 93                  }
 94              }
 95  
 96              return InvalidAddress;
 97          }
 98  
 99          public void Free(ulong offset, ulong size)
100          {
101              InsertFreeRangeComingled(offset, size);
102          }
103  
104          private void InsertFreeRange(ulong offset, ulong size)
105          {
106              var range = new Range(offset, size);
107              int index = _freeRanges.BinarySearch(range);
108              if (index < 0)
109              {
110                  index = ~index;
111              }
112  
113              _freeRanges.Insert(index, range);
114          }
115  
116          private void InsertFreeRangeComingled(ulong offset, ulong size)
117          {
118              ulong endOffset = offset + size;
119              var range = new Range(offset, size);
120              int index = _freeRanges.BinarySearch(range);
121              if (index < 0)
122              {
123                  index = ~index;
124              }
125  
126              if (index < _freeRanges.Count && _freeRanges[index].Offset == endOffset)
127              {
128                  endOffset = _freeRanges[index].Offset + _freeRanges[index].Size;
129                  _freeRanges.RemoveAt(index);
130              }
131  
132              if (index > 0 && _freeRanges[index - 1].Offset + _freeRanges[index - 1].Size == offset)
133              {
134                  offset = _freeRanges[index - 1].Offset;
135                  _freeRanges.RemoveAt(--index);
136              }
137  
138              range = new Range(offset, endOffset - offset);
139  
140              _freeRanges.Insert(index, range);
141          }
142      }
143  }