1  using Ryujinx.Common;
  2  using System;
  3  
  4  namespace Ryujinx.HLE.HOS.Kernel.Memory
  5  {
  6      class KPageHeap
  7      {
  8          private class Block
  9          {
 10              private readonly KPageBitmap _bitmap = new();
 11              private ulong _heapAddress;
 12              private ulong _endOffset;
 13  
 14              public int Shift { get; private set; }
 15              public int NextShift { get; private set; }
 16              public ulong Size => 1UL << Shift;
 17              public int PagesCount => (int)(Size / KPageTableBase.PageSize);
 18              public int FreeBlocksCount => _bitmap.BitsCount;
 19              public int FreePagesCount => FreeBlocksCount * PagesCount;
 20  
 21              public ArraySegment<ulong> Initialize(ulong address, ulong size, int blockShift, int nextBlockShift, ArraySegment<ulong> bitStorage)
 22              {
 23                  Shift = blockShift;
 24                  NextShift = nextBlockShift;
 25  
 26                  ulong endAddress = address + size;
 27  
 28                  ulong align = nextBlockShift != 0
 29                      ? 1UL << nextBlockShift
 30                      : 1UL << blockShift;
 31  
 32                  address = BitUtils.AlignDown(address, align);
 33                  endAddress = BitUtils.AlignUp(endAddress, align);
 34  
 35                  _heapAddress = address;
 36                  _endOffset = (endAddress - address) / (1UL << blockShift);
 37  
 38                  return _bitmap.Initialize(bitStorage, _endOffset);
 39              }
 40  
 41              public ulong PushBlock(ulong address)
 42              {
 43                  ulong offset = (address - _heapAddress) >> Shift;
 44  
 45                  _bitmap.SetBit(offset);
 46  
 47                  if (NextShift != 0)
 48                  {
 49                      int diff = 1 << (NextShift - Shift);
 50  
 51                      offset = BitUtils.AlignDown(offset, (ulong)diff);
 52  
 53                      if (_bitmap.ClearRange(offset, diff))
 54                      {
 55                          return _heapAddress + (offset << Shift);
 56                      }
 57                  }
 58  
 59                  return 0;
 60              }
 61  
 62              public ulong PopBlock(bool random)
 63              {
 64                  long sOffset = (long)_bitmap.FindFreeBlock(random);
 65  
 66                  if (sOffset < 0L)
 67                  {
 68                      return 0;
 69                  }
 70  
 71                  ulong offset = (ulong)sOffset;
 72  
 73                  _bitmap.ClearBit(offset);
 74  
 75                  return _heapAddress + (offset << Shift);
 76              }
 77  
 78              public static int CalculateManagementOverheadSize(ulong regionSize, int currBlockShift, int nextBlockShift)
 79              {
 80                  ulong currBlockSize = 1UL << currBlockShift;
 81                  ulong nextBlockSize = 1UL << nextBlockShift;
 82                  ulong align = nextBlockShift != 0 ? nextBlockSize : currBlockSize;
 83                  return KPageBitmap.CalculateManagementOverheadSize((align * 2 + BitUtils.AlignUp(regionSize, align)) / currBlockSize);
 84              }
 85          }
 86  
 87          private static readonly int[] _memoryBlockPageShifts = { 12, 16, 21, 22, 25, 29, 30 };
 88  
 89  #pragma warning disable IDE0052 // Remove unread private member
 90          private readonly ulong _heapAddress;
 91          private readonly ulong _heapSize;
 92          private ulong _usedSize;
 93  #pragma warning restore IDE0052
 94          private readonly int _blocksCount;
 95          private readonly Block[] _blocks;
 96  
 97          public KPageHeap(ulong address, ulong size) : this(address, size, _memoryBlockPageShifts)
 98          {
 99          }
100  
101          public KPageHeap(ulong address, ulong size, int[] blockShifts)
102          {
103              _heapAddress = address;
104              _heapSize = size;
105              _blocksCount = blockShifts.Length;
106              _blocks = new Block[_memoryBlockPageShifts.Length];
107  
108              var currBitmapStorage = new ArraySegment<ulong>(new ulong[CalculateManagementOverheadSize(size, blockShifts)]);
109  
110              for (int i = 0; i < blockShifts.Length; i++)
111              {
112                  int currBlockShift = blockShifts[i];
113                  int nextBlockShift = i != blockShifts.Length - 1 ? blockShifts[i + 1] : 0;
114  
115                  _blocks[i] = new Block();
116  
117                  currBitmapStorage = _blocks[i].Initialize(address, size, currBlockShift, nextBlockShift, currBitmapStorage);
118              }
119          }
120  
121          public void UpdateUsedSize()
122          {
123              _usedSize = _heapSize - (GetFreePagesCount() * KPageTableBase.PageSize);
124          }
125  
126          public ulong GetFreePagesCount()
127          {
128              ulong freeCount = 0;
129  
130              for (int i = 0; i < _blocksCount; i++)
131              {
132                  freeCount += (ulong)_blocks[i].FreePagesCount;
133              }
134  
135              return freeCount;
136          }
137  
138          public ulong AllocateBlock(int index, bool random)
139          {
140              ulong neededSize = _blocks[index].Size;
141  
142              for (int i = index; i < _blocksCount; i++)
143              {
144                  ulong address = _blocks[i].PopBlock(random);
145  
146                  if (address != 0)
147                  {
148                      ulong allocatedSize = _blocks[i].Size;
149  
150                      if (allocatedSize > neededSize)
151                      {
152                          Free(address + neededSize, (allocatedSize - neededSize) / KPageTableBase.PageSize);
153                      }
154  
155                      return address;
156                  }
157              }
158  
159              return 0;
160          }
161  
162          private void FreeBlock(ulong block, int index)
163          {
164              do
165              {
166                  block = _blocks[index++].PushBlock(block);
167              }
168              while (block != 0);
169          }
170  
171          public void Free(ulong address, ulong pagesCount)
172          {
173              if (pagesCount == 0)
174              {
175                  return;
176              }
177  
178              int bigIndex = _blocksCount - 1;
179  
180              ulong start = address;
181              ulong end = address + pagesCount * KPageTableBase.PageSize;
182              ulong beforeStart = start;
183              ulong beforeEnd = start;
184              ulong afterStart = end;
185              ulong afterEnd = end;
186  
187              while (bigIndex >= 0)
188              {
189                  ulong blockSize = _blocks[bigIndex].Size;
190  
191                  ulong bigStart = BitUtils.AlignUp(start, blockSize);
192                  ulong bigEnd = BitUtils.AlignDown(end, blockSize);
193  
194                  if (bigStart < bigEnd)
195                  {
196                      for (ulong block = bigStart; block < bigEnd; block += blockSize)
197                      {
198                          FreeBlock(block, bigIndex);
199                      }
200  
201                      beforeEnd = bigStart;
202                      afterStart = bigEnd;
203  
204                      break;
205                  }
206  
207                  bigIndex--;
208              }
209  
210              for (int i = bigIndex - 1; i >= 0; i--)
211              {
212                  ulong blockSize = _blocks[i].Size;
213  
214                  while (beforeStart + blockSize <= beforeEnd)
215                  {
216                      beforeEnd -= blockSize;
217                      FreeBlock(beforeEnd, i);
218                  }
219              }
220  
221              for (int i = bigIndex - 1; i >= 0; i--)
222              {
223                  ulong blockSize = _blocks[i].Size;
224  
225                  while (afterStart + blockSize <= afterEnd)
226                  {
227                      FreeBlock(afterStart, i);
228                      afterStart += blockSize;
229                  }
230              }
231          }
232  
233          public static int GetAlignedBlockIndex(ulong pagesCount, ulong alignPages)
234          {
235              ulong targetPages = Math.Max(pagesCount, alignPages);
236  
237              for (int i = 0; i < _memoryBlockPageShifts.Length; i++)
238              {
239                  if (targetPages <= GetBlockPagesCount(i))
240                  {
241                      return i;
242                  }
243              }
244  
245              return -1;
246          }
247  
248          public static int GetBlockIndex(ulong pagesCount)
249          {
250              for (int i = _memoryBlockPageShifts.Length - 1; i >= 0; i--)
251              {
252                  if (pagesCount >= GetBlockPagesCount(i))
253                  {
254                      return i;
255                  }
256              }
257  
258              return -1;
259          }
260  
261          public static ulong GetBlockSize(int index)
262          {
263              return 1UL << _memoryBlockPageShifts[index];
264          }
265  
266          public static ulong GetBlockPagesCount(int index)
267          {
268              return GetBlockSize(index) / KPageTableBase.PageSize;
269          }
270  
271          private static int CalculateManagementOverheadSize(ulong regionSize, int[] blockShifts)
272          {
273              int overheadSize = 0;
274  
275              for (int i = 0; i < blockShifts.Length; i++)
276              {
277                  int currBlockShift = blockShifts[i];
278                  int nextBlockShift = i != blockShifts.Length - 1 ? blockShifts[i + 1] : 0;
279                  overheadSize += Block.CalculateManagementOverheadSize(regionSize, currBlockShift, nextBlockShift);
280              }
281  
282              return BitUtils.AlignUp(overheadSize, KPageTableBase.PageSize);
283          }
284      }
285  }