ReactOS  r74405
syspte.c
Go to the documentation of this file.
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 
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  };
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 
70 ULONG
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
89  IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType,
91 {
92  KIRQL OldIrql;
93  PMMPTE PreviousPte, NextPte, ReturnPte;
95 
96  //
97  // Sanity check
98  //
99  ASSERT(Alignment <= PAGE_SIZE);
100 
101  //
102  // Acquire the System PTE lock
103  //
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  //
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  //
232 
233  //
234  // Flush the TLB
235  //
237 
238  //
239  // Return the reserved PTEs
240  //
241  return ReturnPte;
242 }
243 
244 PMMPTE
245 NTAPI
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
276  IN ULONG NumberOfPtes,
277  IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
278 {
279  KIRQL OldIrql;
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  //
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  //
394 }
395 
396 VOID
397 NTAPI
400  IN ULONG NumberOfPtes,
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 -
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 */
#define IN
Definition: typedefs.h:39
PMMPTE NTAPI MiReserveSystemPtes(IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
Definition: syspte.c:246
VOID NTAPI MiReleaseSystemPtes(IN PMMPTE StartingPte, IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
Definition: syspte.c:275
VOID NTAPI INIT_FUNCTION MiInitializeSystemPtes(IN PMMPTE StartingPte, IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE PoolType)
Definition: syspte.c:399
LONG MmSysPteListBySizeCount[5]
Definition: syspte.c:36
ULONG64 NextEntry
Definition: mmtypes.h:145
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel)?(CompletionRoutine!=NULL):TRUE)
#define MM_EMPTY_PTE_LIST
Definition: mm.h:77
ULONG64 OneEntry
Definition: mmtypes.h:139
union _MMPTE::@1890 u
PMMPTE MmSystemPtesStart[MaximumPtePoolTypes]
Definition: syspte.c:22
UCHAR KIRQL
Definition: env_spec_w32.h:591
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
ULONG MiNumberOfExtraSystemPdes
Definition: syspte.c:27
long LONG
Definition: pedump.c:60
MMPTE MmFirstFreeSystemPte[MaximumPtePoolTypes]
Definition: syspte.c:24
smooth NULL
Definition: ftsmooth.c:464
#define FORCEINLINE
Definition: ntbasedef.h:213
void DPRINT(...)
Definition: polytest.cpp:61
ULONG MmTotalSystemPtes
Definition: syspte.c:26
ULONG MmTotalFreeSystemPtes[MaximumPtePoolTypes]
Definition: syspte.c:25
const ULONG MmSysPteIndex[5]
Definition: syspte.c:28
MMPTE_LIST List
Definition: mmtypes.h:222
DWORD ClusterSize
Definition: format.c:67
FORCEINLINE ULONG MI_GET_CLUSTER_SIZE(IN PMMPTE Pte)
Definition: syspte.c:71
enum _MMSYSTEM_PTE_POOL_TYPE MMSYSTEM_PTE_POOL_TYPE
VOID FASTCALL KeReleaseQueuedSpinLock(IN KSPIN_LOCK_QUEUE_NUMBER LockNumber, IN KIRQL OldIrql)
Definition: spinlock.c:154
PMMPTE MmSystemPtesEnd[MaximumPtePoolTypes]
Definition: syspte.c:23
unsigned char UCHAR
Definition: xmlstorage.h:181
IN REFCLSID IN PUNKNOWN IN POOL_TYPE PoolType
Definition: unknown.h:68
_Requires_lock_held_ Interrupt _Releases_lock_ Interrupt _In_ _IRQL_restores_ KIRQL OldIrql
Definition: kefuncs.h:803
#define PAGE_SIZE
Definition: env_spec_w32.h:49
KIRQL FASTCALL KeAcquireQueuedSpinLock(IN KSPIN_LOCK_QUEUE_NUMBER LockNumber)
Definition: spinlock.c:108
#define MI_SYSTEM_PTE_BASE
Definition: mm.h:35
PMMPTE MmSystemPteBase
Definition: syspte.c:21
ULONG_PTR Long
Definition: mmtypes.h:215
#define DPRINT1
Definition: precomp.h:8
FORCEINLINE VOID KeFlushProcessTb(VOID)
Definition: ke.h:185
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
const UCHAR MmSysPteTables[]
Definition: syspte.c:29
PMMPTE NTAPI MiReserveAlignedSystemPtes(IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType, IN ULONG Alignment)
Definition: syspte.c:88
#define INIT_FUNCTION
Definition: ntoskrnl.h:11