ntoskrnl/mm/ARM3/syspte.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         BSD - See COPYING.ARM in the top level directory
   4  * FILE:            ntoskrnl/mm/ARM3/syspte.c
   5  * PURPOSE:         ARM Memory Manager System PTE Allocator
   6  * PROGRAMMERS:     ReactOS Portable Systems Group
   7  *                  Roel Messiant (roel.messiant@reactos.org)
   8  */
   9
  10 /* INCLUDES *******************************************************************/
  11
  12 #include <ntoskrnl.h>
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16 #define MODULE_INVOLVED_IN_ARM3
  17 #include <mm/ARM3/miarm.h>
  18
  19 /* GLOBALS ********************************************************************/
  20
  21 PMMPTE MmSystemPteBase;
  22 PMMPTE MmSystemPtesStart[MaximumPtePoolTypes];
  23 PMMPTE MmSystemPtesEnd[MaximumPtePoolTypes];
  24 MMPTE MmFirstFreeSystemPte[MaximumPtePoolTypes];
  25 ULONG MmTotalFreeSystemPtes[MaximumPtePoolTypes];
  26 ULONG MmTotalSystemPtes;
  27 ULONG MiNumberOfExtraSystemPdes;
  28 const ULONG MmSysPteIndex[5] = { 1, 2, 4, 8, 16 };
  29 const UCHAR MmSysPteTables[] = { 0, // 1
  30                                  0, // 1
  31                                  1, // 2
  32                                  2, 2, // 4
  33                                  3, 3, 3, 3, // 8
  34                                  4, 4, 4, 4, 4, 4, 4, 4 // 16
  35                                };
  36 LONG MmSysPteListBySizeCount[5];
  37
  38 /* PRIVATE FUNCTIONS **********************************************************/
  39
  40 //
  41 // The free System Page Table Entries are stored in a bunch of clusters,
  42 // each consisting of one or more PTEs.  These PTE clusters are connected
  43 // in a singly linked list, ordered by increasing cluster size.
  44 //
  45 // A cluster consisting of a single PTE is marked by having the OneEntry flag
  46 // of its PTE set.  The forward link is contained in the NextEntry field.
  47 //
  48 // Clusters containing multiple PTEs have the OneEntry flag of their first PTE
  49 // reset.  The NextEntry field of the first PTE contains the forward link, and
  50 // the size of the cluster is stored in the NextEntry field of its second PTE.
  51 //
  52 // Reserving PTEs currently happens by walking the linked list until a cluster
  53 // is found that contains the requested amount of PTEs or more.  This cluster
  54 // is removed from the list, and the requested amount of PTEs is taken from the
  55 // tail of this cluster.  If any PTEs remain in the cluster, the linked list is
  56 // walked again until a second cluster is found that contains the same amount
  57 // of PTEs or more.  The first cluster is then inserted in front of the second
  58 // one.
  59 //
  60 // Releasing PTEs currently happens by walking the whole linked list, recording
  61 // the first cluster that contains the amount of PTEs to release or more. When
  62 // a cluster is found that is adjacent to the PTEs being released, this cluster
  63 // is removed from the list and subsequently added to the PTEs being released.
  64 // This ensures no two clusters are adjacent, which maximizes their size.
  65 // After the walk is complete, a new cluster is created that contains the PTEs
  66 // being released, which is then inserted in front of the recorded cluster.
  67 //
  68
  69 FORCEINLINE
  70 ULONG
  71 MI_GET_CLUSTER_SIZE(IN PMMPTE Pte)
  72 {
  73     //
  74     // First check for a single PTE
  75     //
  76     if (Pte->u.List.OneEntry)
  77         return 1;
  78
  79     //
  80     // Then read the size from the trailing PTE
  81     //
  82     Pte++;
  83     return (ULONG)Pte->u.List.NextEntry;
  84 }
  85
  86 PMMPTE
  87 NTAPI
  88 MiReserveAlignedSystemPtes(IN ULONG NumberOfPtes,
  89                            IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType,
  90                            IN ULONG Alignment)
  91 {
  92     KIRQL OldIrql;
  93     PMMPTE PreviousPte, NextPte, ReturnPte;
  94     ULONG ClusterSize;
  95
  96     //
  97     // Sanity check
  98     //
  99     ASSERT(Alignment <= PAGE_SIZE);
 100
 101     //
 102     // Acquire the System PTE lock
 103     //
 104     OldIrql = KeAcquireQueuedSpinLock(LockQueueSystemSpaceLock);
 105
 106     //
 107     // Find the last cluster in the list that doesn't contain enough PTEs
 108     //
 109     PreviousPte = &MmFirstFreeSystemPte[SystemPtePoolType];
 110
 111     while (PreviousPte->u.List.NextEntry != MM_EMPTY_PTE_LIST)
 112     {
 113         //
 114         // Get the next cluster and its size
 115         //
 116         NextPte = MmSystemPteBase + PreviousPte->u.List.NextEntry;
 117         ClusterSize = MI_GET_CLUSTER_SIZE(NextPte);
 118
 119         //
 120         // Check if this cluster contains enough PTEs
 121         //
 122         if (NumberOfPtes <= ClusterSize)
 123             break;
 124
 125         //
 126         // On to the next cluster
 127         //
 128         PreviousPte = NextPte;
 129     }
 130
 131     //
 132     // Make sure we didn't reach the end of the cluster list
 133     //
 134     if (PreviousPte->u.List.NextEntry == MM_EMPTY_PTE_LIST)
 135     {
 136         //
 137         // Release the System PTE lock and return failure
 138         //
 139         KeReleaseQueuedSpinLock(LockQueueSystemSpaceLock, OldIrql);
 140         return NULL;
 141     }
 142
 143     //
 144     // Unlink the cluster
 145     //
 146     PreviousPte->u.List.NextEntry = NextPte->u.List.NextEntry;
 147
 148     //
 149     // Check if the reservation spans the whole cluster
 150     //
 151     if (ClusterSize == NumberOfPtes)
 152     {
 153         //
 154         // Return the first PTE of this cluster
 155         //
 156         ReturnPte = NextPte;
 157
 158         //
 159         // Zero the cluster
 160         //
 161         if (NextPte->u.List.OneEntry == 0)
 162         {
 163             NextPte->u.Long = 0;
 164             NextPte++;
 165         }
 166         NextPte->u.Long = 0;
 167     }
 168     else
 169     {
 170         //
 171         // Divide the cluster into two parts
 172         //
 173         ClusterSize -= NumberOfPtes;
 174         ReturnPte = NextPte + ClusterSize;
 175
 176         //
 177         // Set the size of the first cluster, zero the second if needed
 178         //
 179         if (ClusterSize == 1)
 180         {
 181             NextPte->u.List.OneEntry = 1;
 182             ReturnPte->u.Long = 0;
 183         }
 184         else
 185         {
 186             NextPte++;
 187             NextPte->u.List.NextEntry = ClusterSize;
 188         }
 189
 190         //
 191         // Step through the cluster list to find out where to insert the first
 192         //
 193         PreviousPte = &MmFirstFreeSystemPte[SystemPtePoolType];
 194
 195         while (PreviousPte->u.List.NextEntry != MM_EMPTY_PTE_LIST)
 196         {
 197             //
 198             // Get the next cluster
 199             //
 200             NextPte = MmSystemPteBase + PreviousPte->u.List.NextEntry;
 201
 202             //
 203             // Check if the cluster to insert is smaller or of equal size
 204             //
 205             if (ClusterSize <= MI_GET_CLUSTER_SIZE(NextPte))
 206                 break;
 207
 208             //
 209             // On to the next cluster
 210             //
 211             PreviousPte = NextPte;
 212         }
 213
 214         //
 215         // Retrieve the first cluster and link it back into the cluster list
 216         //
 217         NextPte = ReturnPte - ClusterSize;
 218
 219         NextPte->u.List.NextEntry = PreviousPte->u.List.NextEntry;
 220         PreviousPte->u.List.NextEntry = NextPte - MmSystemPteBase;
 221     }
 222
 223     //
 224     // Decrease availability
 225     //
 226     MmTotalFreeSystemPtes[SystemPtePoolType] -= NumberOfPtes;
 227
 228     //
 229     // Release the System PTE lock
 230     //
 231     KeReleaseQueuedSpinLock(LockQueueSystemSpaceLock, OldIrql);
 232
 233     //
 234     // Flush the TLB
 235     //
 236     KeFlushProcessTb();
 237
 238     //
 239     // Return the reserved PTEs
 240     //
 241     return ReturnPte;
 242 }
 243
 244 PMMPTE
 245 NTAPI
 246 MiReserveSystemPtes(IN ULONG NumberOfPtes,
 247                     IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
 248 {
 249     PMMPTE PointerPte;
 250
 251     //
 252     // Use the extended function
 253     //
 254     PointerPte = MiReserveAlignedSystemPtes(NumberOfPtes, SystemPtePoolType, 0);
 255
 256     //
 257     // Check if allocation failed
 258     //
 259     if (!PointerPte)
 260     {
 261         //
 262         // Warn that we are out of memory
 263         //
 264         DPRINT1("MiReserveSystemPtes: Failed to reserve %lu PTE(s)!\n", NumberOfPtes);
 265     }
 266
 267     //
 268     // Return the PTE Pointer
 269     //
 270     return PointerPte;
 271 }
 272
 273 VOID
 274 NTAPI
 275 MiReleaseSystemPtes(IN PMMPTE StartingPte,
 276                     IN ULONG NumberOfPtes,
 277                     IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
 278 {
 279     KIRQL OldIrql;
 280     ULONG ClusterSize;
 281     PMMPTE PreviousPte, NextPte, InsertPte;
 282
 283     //
 284     // Check to make sure the PTE address is within bounds
 285     //
 286     ASSERT(NumberOfPtes != 0);
 287     ASSERT(StartingPte >= MmSystemPtesStart[SystemPtePoolType]);
 288     ASSERT(StartingPte + NumberOfPtes - 1 <= MmSystemPtesEnd[SystemPtePoolType]);
 289
 290     //
 291     // Zero PTEs
 292     //
 293     RtlZeroMemory(StartingPte, NumberOfPtes * sizeof(MMPTE));
 294
 295     //
 296     // Acquire the System PTE lock
 297     //
 298     OldIrql = KeAcquireQueuedSpinLock(LockQueueSystemSpaceLock);
 299
 300     //
 301     // Increase availability
 302     //
 303     MmTotalFreeSystemPtes[SystemPtePoolType] += NumberOfPtes;
 304
 305     //
 306     // Step through the cluster list to find where to insert the PTEs
 307     //
 308     PreviousPte = &MmFirstFreeSystemPte[SystemPtePoolType];
 309     InsertPte = NULL;
 310
 311     while (PreviousPte->u.List.NextEntry != MM_EMPTY_PTE_LIST)
 312     {
 313         //
 314         // Get the next cluster and its size
 315         //
 316         NextPte = MmSystemPteBase + PreviousPte->u.List.NextEntry;
 317         ClusterSize = MI_GET_CLUSTER_SIZE(NextPte);
 318
 319         //
 320         // Check if this cluster is adjacent to the PTEs being released
 321         //
 322         if ((NextPte + ClusterSize == StartingPte) ||
 323             (StartingPte + NumberOfPtes == NextPte))
 324         {
 325             //
 326             // Add the PTEs in the cluster to the PTEs being released
 327             //
 328             NumberOfPtes += ClusterSize;
 329
 330             if (NextPte < StartingPte)
 331                 StartingPte = NextPte;
 332
 333             //
 334             // Unlink this cluster and zero it
 335             //
 336             PreviousPte->u.List.NextEntry = NextPte->u.List.NextEntry;
 337
 338             if (NextPte->u.List.OneEntry == 0)
 339             {
 340                 NextPte->u.Long = 0;
 341                 NextPte++;
 342             }
 343             NextPte->u.Long = 0;
 344
 345             //
 346             // Invalidate the previously found insertion location, if any
 347             //
 348             InsertPte = NULL;
 349         }
 350         else
 351         {
 352             //
 353             // Check if the insertion location is right before this cluster
 354             //
 355             if ((InsertPte == NULL) && (NumberOfPtes <= ClusterSize))
 356                 InsertPte = PreviousPte;
 357
 358             //
 359             // On to the next cluster
 360             //
 361             PreviousPte = NextPte;
 362         }
 363     }
 364
 365     //
 366     // If no insertion location was found, use the tail of the list
 367     //
 368     if (InsertPte == NULL)
 369         InsertPte = PreviousPte;
 370
 371     //
 372     // Create a new cluster using the PTEs being released
 373     //
 374     if (NumberOfPtes != 1)
 375     {
 376         StartingPte->u.List.OneEntry = 0;
 377
 378         NextPte = StartingPte + 1;
 379         NextPte->u.List.NextEntry = NumberOfPtes;
 380     }
 381     else
 382         StartingPte->u.List.OneEntry = 1;
 383
 384     //
 385     // Link the new cluster into the cluster list at the insertion location
 386     //
 387     StartingPte->u.List.NextEntry = InsertPte->u.List.NextEntry;
 388     InsertPte->u.List.NextEntry = StartingPte - MmSystemPteBase;
 389
 390     //
 391     // Release the System PTE lock
 392     //
 393     KeReleaseQueuedSpinLock(LockQueueSystemSpaceLock, OldIrql);
 394 }
 395
 396 INIT_FUNCTION
 397 VOID
 398 NTAPI
 399 MiInitializeSystemPtes(IN PMMPTE StartingPte,
 400                        IN ULONG NumberOfPtes,
 401                        IN MMSYSTEM_PTE_POOL_TYPE PoolType)
 402 {
 403     //
 404     // Sanity checks
 405     //
 406     ASSERT(NumberOfPtes >= 1);
 407
 408     //
 409     // Set the starting and ending PTE addresses for this space
 410     //
 411     MmSystemPteBase = MI_SYSTEM_PTE_BASE;
 412     MmSystemPtesStart[PoolType] = StartingPte;
 413     MmSystemPtesEnd[PoolType] = StartingPte + NumberOfPtes - 1;
 414     DPRINT("System PTE space for %d starting at: %p and ending at: %p\n",
 415            PoolType, MmSystemPtesStart[PoolType], MmSystemPtesEnd[PoolType]);
 416
 417     //
 418     // Clear all the PTEs to start with
 419     //
 420     RtlZeroMemory(StartingPte, NumberOfPtes * sizeof(MMPTE));
 421
 422     //
 423     // Make the first entry free and link it
 424     //
 425     StartingPte->u.List.NextEntry = MM_EMPTY_PTE_LIST;
 426     MmFirstFreeSystemPte[PoolType].u.Long = 0;
 427     MmFirstFreeSystemPte[PoolType].u.List.NextEntry = StartingPte -
 428                                                       MmSystemPteBase;
 429
 430     //
 431     // The second entry stores the size of this PTE space
 432     //
 433     StartingPte++;
 434     StartingPte->u.Long = 0;
 435     StartingPte->u.List.NextEntry = NumberOfPtes;
 436
 437     //
 438     // We also keep a global for it
 439     //
 440     MmTotalFreeSystemPtes[PoolType] = NumberOfPtes;
 441
 442     //
 443     // Check if this is the system PTE space
 444     //
 445     if (PoolType == SystemPteSpace)
 446     {
 447         //
 448         // Remember how many PTEs we have
 449         //
 450         MmTotalSystemPtes = NumberOfPtes;
 451     }
 452 }
 453
 454 /* EOF */