ReactOS  0.4.15-dev-3203-gacde1e0
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  //
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  // Return the PTE Pointer
258  //
259  return PointerPte;
260 }
261 
262 VOID
263 NTAPI
265  IN ULONG NumberOfPtes,
266  IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
267 {
268  KIRQL OldIrql;
270  PMMPTE PreviousPte, NextPte, InsertPte;
271 
272  //
273  // Check to make sure the PTE address is within bounds
274  //
275  ASSERT(NumberOfPtes != 0);
276  ASSERT(StartingPte >= MmSystemPtesStart[SystemPtePoolType]);
277  ASSERT(StartingPte + NumberOfPtes - 1 <= MmSystemPtesEnd[SystemPtePoolType]);
278 
279  //
280  // Zero PTEs
281  //
282  RtlZeroMemory(StartingPte, NumberOfPtes * sizeof(MMPTE));
283 
284  //
285  // Acquire the System PTE lock
286  //
288 
289  //
290  // Increase availability
291  //
292  MmTotalFreeSystemPtes[SystemPtePoolType] += NumberOfPtes;
293 
294  //
295  // Step through the cluster list to find where to insert the PTEs
296  //
297  PreviousPte = &MmFirstFreeSystemPte[SystemPtePoolType];
298  InsertPte = NULL;
299 
300  while (PreviousPte->u.List.NextEntry != MM_EMPTY_PTE_LIST)
301  {
302  //
303  // Get the next cluster and its size
304  //
305  NextPte = MmSystemPteBase + PreviousPte->u.List.NextEntry;
306  ClusterSize = MI_GET_CLUSTER_SIZE(NextPte);
307 
308  //
309  // Check if this cluster is adjacent to the PTEs being released
310  //
311  if ((NextPte + ClusterSize == StartingPte) ||
312  (StartingPte + NumberOfPtes == NextPte))
313  {
314  //
315  // Add the PTEs in the cluster to the PTEs being released
316  //
317  NumberOfPtes += ClusterSize;
318 
319  if (NextPte < StartingPte)
320  StartingPte = NextPte;
321 
322  //
323  // Unlink this cluster and zero it
324  //
325  PreviousPte->u.List.NextEntry = NextPte->u.List.NextEntry;
326 
327  if (NextPte->u.List.OneEntry == 0)
328  {
329  NextPte->u.Long = 0;
330  NextPte++;
331  }
332  NextPte->u.Long = 0;
333 
334  //
335  // Invalidate the previously found insertion location, if any
336  //
337  InsertPte = NULL;
338  }
339  else
340  {
341  //
342  // Check if the insertion location is right before this cluster
343  //
344  if ((InsertPte == NULL) && (NumberOfPtes <= ClusterSize))
345  InsertPte = PreviousPte;
346 
347  //
348  // On to the next cluster
349  //
350  PreviousPte = NextPte;
351  }
352  }
353 
354  //
355  // If no insertion location was found, use the tail of the list
356  //
357  if (InsertPte == NULL)
358  InsertPte = PreviousPte;
359 
360  //
361  // Create a new cluster using the PTEs being released
362  //
363  if (NumberOfPtes != 1)
364  {
365  StartingPte->u.List.OneEntry = 0;
366 
367  NextPte = StartingPte + 1;
368  NextPte->u.List.NextEntry = NumberOfPtes;
369  }
370  else
371  StartingPte->u.List.OneEntry = 1;
372 
373  //
374  // Link the new cluster into the cluster list at the insertion location
375  //
376  StartingPte->u.List.NextEntry = InsertPte->u.List.NextEntry;
377  InsertPte->u.List.NextEntry = StartingPte - MmSystemPteBase;
378 
379  //
380  // Release the System PTE lock
381  //
383 }
384 
385 CODE_SEG("INIT")
386 VOID
387 NTAPI
389  IN ULONG NumberOfPtes,
391 {
392  //
393  // Sanity checks
394  //
395  ASSERT(NumberOfPtes >= 1);
396 
397  //
398  // Set the starting and ending PTE addresses for this space
399  //
401  MmSystemPtesStart[PoolType] = StartingPte;
402  MmSystemPtesEnd[PoolType] = StartingPte + NumberOfPtes - 1;
403  DPRINT("System PTE space for %d starting at: %p and ending at: %p\n",
405 
406  //
407  // Clear all the PTEs to start with
408  //
409  RtlZeroMemory(StartingPte, NumberOfPtes * sizeof(MMPTE));
410 
411  //
412  // Make the first entry free and link it
413  //
414  StartingPte->u.List.NextEntry = MM_EMPTY_PTE_LIST;
416  MmFirstFreeSystemPte[PoolType].u.List.NextEntry = StartingPte -
418 
419  //
420  // The second entry stores the size of this PTE space
421  //
422  StartingPte++;
423  StartingPte->u.Long = 0;
424  StartingPte->u.List.NextEntry = NumberOfPtes;
425 
426  //
427  // We also keep a global for it
428  //
429  MmTotalFreeSystemPtes[PoolType] = NumberOfPtes;
430 
431  //
432  // Check if this is the system PTE space
433  //
434  if (PoolType == SystemPteSpace)
435  {
436  //
437  // Remember how many PTEs we have
438  //
439  MmTotalSystemPtes = NumberOfPtes;
440  }
441 }
442 
443 /* 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:264
LONG MmSysPteListBySizeCount[5]
Definition: syspte.c:36
ULONG64 NextEntry
Definition: mmtypes.h:145
#define MM_EMPTY_PTE_LIST
Definition: mm.h:87
ULONG64 OneEntry
Definition: mmtypes.h:139
union _MMPTE::@2274 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
ULONG MmTotalSystemPtes
Definition: syspte.c:26
KIRQL OldIrql
Definition: mm.h:1502
ULONG MmTotalFreeSystemPtes[MaximumPtePoolTypes]
Definition: syspte.c:25
VOID NTAPI MiInitializeSystemPtes(IN PMMPTE StartingPte, IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE PoolType)
Definition: syspte.c:388
const ULONG MmSysPteIndex[5]
Definition: syspte.c:28
#define ASSERT(a)
Definition: mode.c:44
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
#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:45
PMMPTE MmSystemPteBase
Definition: syspte.c:21
ULONG_PTR Long
Definition: mmtypes.h:215
#define FORCEINLINE
Definition: wdftypes.h:67
#define NULL
Definition: types.h:112
FORCEINLINE VOID KeFlushProcessTb(VOID)
Definition: ke.h:268
_Must_inspect_result_ _In_ WDFDEVICE _In_ DEVICE_REGISTRY_PROPERTY _In_ _Strict_type_match_ POOL_TYPE PoolType
Definition: wdfdevice.h:3810
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
const UCHAR MmSysPteTables[]
Definition: syspte.c:29
#define DPRINT
Definition: sndvol32.h:71
static CODE_SEG("PAGE")
Definition: isapnp.c:1482
PMMPTE NTAPI MiReserveAlignedSystemPtes(IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType, IN ULONG Alignment)
Definition: syspte.c:88