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