1  using Ryujinx.Common.Collections;
  2  using Ryujinx.Horizon.Common;
  3  using System.Diagnostics;
  4  
  5  namespace Ryujinx.HLE.HOS.Kernel.Memory
  6  {
  7      class KMemoryBlockManager
  8      {
  9          private const int PageSize = KPageTableBase.PageSize;
 10  
 11          private readonly IntrusiveRedBlackTree<KMemoryBlock> _blockTree;
 12  
 13          public int BlocksCount => _blockTree.Count;
 14  
 15          private KMemoryBlockSlabManager _slabManager;
 16  
 17          private ulong _addrSpaceStart;
 18          private ulong _addrSpaceEnd;
 19  
 20          public KMemoryBlockManager()
 21          {
 22              _blockTree = new IntrusiveRedBlackTree<KMemoryBlock>();
 23          }
 24  
 25          public Result Initialize(ulong addrSpaceStart, ulong addrSpaceEnd, KMemoryBlockSlabManager slabManager)
 26          {
 27              _slabManager = slabManager;
 28              _addrSpaceStart = addrSpaceStart;
 29              _addrSpaceEnd = addrSpaceEnd;
 30  
 31              // First insertion will always need only a single block, because there's nothing to split.
 32              if (!slabManager.CanAllocate(1))
 33              {
 34                  return KernelResult.OutOfResource;
 35              }
 36  
 37              ulong addrSpacePagesCount = (addrSpaceEnd - addrSpaceStart) / PageSize;
 38  
 39              _blockTree.Add(new KMemoryBlock(
 40                  addrSpaceStart,
 41                  addrSpacePagesCount,
 42                  MemoryState.Unmapped,
 43                  KMemoryPermission.None,
 44                  MemoryAttribute.None));
 45  
 46              return Result.Success;
 47          }
 48  
 49          public void InsertBlock(
 50              ulong baseAddress,
 51              ulong pagesCount,
 52              MemoryState oldState,
 53              KMemoryPermission oldPermission,
 54              MemoryAttribute oldAttribute,
 55              MemoryState newState,
 56              KMemoryPermission newPermission,
 57              MemoryAttribute newAttribute)
 58          {
 59              // Insert new block on the list only on areas where the state
 60              // of the block matches the state specified on the old* state
 61              // arguments, otherwise leave it as is.
 62  
 63              int oldCount = _blockTree.Count;
 64  
 65              oldAttribute |= MemoryAttribute.IpcAndDeviceMapped;
 66  
 67              ulong endAddr = baseAddress + pagesCount * PageSize;
 68  
 69              KMemoryBlock currBlock = FindBlock(baseAddress);
 70  
 71              while (currBlock != null)
 72              {
 73                  ulong currBaseAddr = currBlock.BaseAddress;
 74                  ulong currEndAddr = currBlock.PagesCount * PageSize + currBaseAddr;
 75  
 76                  if (baseAddress < currEndAddr && currBaseAddr < endAddr)
 77                  {
 78                      MemoryAttribute currBlockAttr = currBlock.Attribute | MemoryAttribute.IpcAndDeviceMapped;
 79  
 80                      if (currBlock.State != oldState ||
 81                          currBlock.Permission != oldPermission ||
 82                          currBlockAttr != oldAttribute)
 83                      {
 84                          currBlock = currBlock.Successor;
 85  
 86                          continue;
 87                      }
 88  
 89                      if (baseAddress > currBaseAddr)
 90                      {
 91                          KMemoryBlock newBlock = currBlock.SplitRightAtAddress(baseAddress);
 92                          _blockTree.Add(newBlock);
 93                      }
 94  
 95                      if (endAddr < currEndAddr)
 96                      {
 97                          KMemoryBlock newBlock = currBlock.SplitRightAtAddress(endAddr);
 98                          _blockTree.Add(newBlock);
 99                          currBlock = newBlock;
100                      }
101  
102                      currBlock.SetState(newPermission, newState, newAttribute);
103  
104                      currBlock = MergeEqualStateNeighbors(currBlock);
105                  }
106  
107                  if (currEndAddr - 1 >= endAddr - 1)
108                  {
109                      break;
110                  }
111  
112                  currBlock = currBlock.Successor;
113              }
114  
115              _slabManager.Count += _blockTree.Count - oldCount;
116  
117              ValidateInternalState();
118          }
119  
120          public void InsertBlock(
121              ulong baseAddress,
122              ulong pagesCount,
123              MemoryState state,
124              KMemoryPermission permission = KMemoryPermission.None,
125              MemoryAttribute attribute = MemoryAttribute.None)
126          {
127              // Inserts new block at the list, replacing and splitting
128              // existing blocks as needed.
129  
130              int oldCount = _blockTree.Count;
131  
132              ulong endAddr = baseAddress + pagesCount * PageSize;
133  
134              KMemoryBlock currBlock = FindBlock(baseAddress);
135  
136              while (currBlock != null)
137              {
138                  ulong currBaseAddr = currBlock.BaseAddress;
139                  ulong currEndAddr = currBlock.PagesCount * PageSize + currBaseAddr;
140  
141                  if (baseAddress < currEndAddr && currBaseAddr < endAddr)
142                  {
143                      if (baseAddress > currBaseAddr)
144                      {
145                          KMemoryBlock newBlock = currBlock.SplitRightAtAddress(baseAddress);
146                          _blockTree.Add(newBlock);
147                      }
148  
149                      if (endAddr < currEndAddr)
150                      {
151                          KMemoryBlock newBlock = currBlock.SplitRightAtAddress(endAddr);
152                          _blockTree.Add(newBlock);
153                          currBlock = newBlock;
154                      }
155  
156                      currBlock.SetState(permission, state, attribute);
157  
158                      currBlock = MergeEqualStateNeighbors(currBlock);
159                  }
160  
161                  if (currEndAddr - 1 >= endAddr - 1)
162                  {
163                      break;
164                  }
165  
166                  currBlock = currBlock.Successor;
167              }
168  
169              _slabManager.Count += _blockTree.Count - oldCount;
170  
171              ValidateInternalState();
172          }
173  
174          public delegate void BlockMutator(KMemoryBlock block, KMemoryPermission newPerm);
175  
176          public void InsertBlock(
177              ulong baseAddress,
178              ulong pagesCount,
179              BlockMutator blockMutate,
180              KMemoryPermission permission = KMemoryPermission.None)
181          {
182              // Inserts new block at the list, replacing and splitting
183              // existing blocks as needed, then calling the callback
184              // function on the new block.
185  
186              int oldCount = _blockTree.Count;
187  
188              ulong endAddr = baseAddress + pagesCount * PageSize;
189  
190              KMemoryBlock currBlock = FindBlock(baseAddress);
191  
192              while (currBlock != null)
193              {
194                  ulong currBaseAddr = currBlock.BaseAddress;
195                  ulong currEndAddr = currBlock.PagesCount * PageSize + currBaseAddr;
196  
197                  if (baseAddress < currEndAddr && currBaseAddr < endAddr)
198                  {
199                      if (baseAddress > currBaseAddr)
200                      {
201                          KMemoryBlock newBlock = currBlock.SplitRightAtAddress(baseAddress);
202                          _blockTree.Add(newBlock);
203                      }
204  
205                      if (endAddr < currEndAddr)
206                      {
207                          KMemoryBlock newBlock = currBlock.SplitRightAtAddress(endAddr);
208                          _blockTree.Add(newBlock);
209                          currBlock = newBlock;
210                      }
211  
212                      blockMutate(currBlock, permission);
213  
214                      currBlock = MergeEqualStateNeighbors(currBlock);
215                  }
216  
217                  if (currEndAddr - 1 >= endAddr - 1)
218                  {
219                      break;
220                  }
221  
222                  currBlock = currBlock.Successor;
223              }
224  
225              _slabManager.Count += _blockTree.Count - oldCount;
226  
227              ValidateInternalState();
228          }
229  
230          [Conditional("DEBUG")]
231          private void ValidateInternalState()
232          {
233              ulong expectedAddress = 0;
234  
235              KMemoryBlock currBlock = FindBlock(_addrSpaceStart);
236  
237              while (currBlock != null)
238              {
239                  Debug.Assert(currBlock.BaseAddress == expectedAddress);
240  
241                  expectedAddress = currBlock.BaseAddress + currBlock.PagesCount * PageSize;
242  
243                  currBlock = currBlock.Successor;
244              }
245  
246              Debug.Assert(expectedAddress == _addrSpaceEnd);
247          }
248  
249          private KMemoryBlock MergeEqualStateNeighbors(KMemoryBlock block)
250          {
251              KMemoryBlock previousBlock = block.Predecessor;
252              KMemoryBlock nextBlock = block.Successor;
253  
254              if (previousBlock != null && BlockStateEquals(block, previousBlock))
255              {
256                  _blockTree.Remove(block);
257  
258                  previousBlock.AddPages(block.PagesCount);
259  
260                  block = previousBlock;
261              }
262  
263              if (nextBlock != null && BlockStateEquals(block, nextBlock))
264              {
265                  _blockTree.Remove(nextBlock);
266  
267                  block.AddPages(nextBlock.PagesCount);
268              }
269  
270              return block;
271          }
272  
273          private static bool BlockStateEquals(KMemoryBlock lhs, KMemoryBlock rhs)
274          {
275              return lhs.State == rhs.State &&
276                     lhs.Permission == rhs.Permission &&
277                     lhs.Attribute == rhs.Attribute &&
278                     lhs.SourcePermission == rhs.SourcePermission &&
279                     lhs.DeviceRefCount == rhs.DeviceRefCount &&
280                     lhs.IpcRefCount == rhs.IpcRefCount;
281          }
282  
283          public KMemoryBlock FindBlock(ulong address)
284          {
285              return _blockTree.GetNodeByKey(address);
286          }
287      }
288  }