ReactOS 0.4.15-dev-7928-g68a8619
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
28const ULONG MmSysPteIndex[5] = { 1, 2, 4, 8, 16 };
29const 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
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
89 IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType,
91{
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;
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
244PMMPTE
245NTAPI
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
262VOID
263NTAPI
265 IN ULONG NumberOfPtes,
266 IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
267{
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;
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
385CODE_SEG("INIT")
386VOID
387NTAPI
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;
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 //
435 {
436 //
437 // Remember how many PTEs we have
438 //
439 MmTotalSystemPtes = NumberOfPtes;
440 }
441}
442
443/* EOF */
#define CODE_SEG(...)
DWORD ClusterSize
Definition: format.c:67
#define NULL
Definition: types.h:112
UCHAR KIRQL
Definition: env_spec_w32.h:591
#define PAGE_SIZE
Definition: env_spec_w32.h:49
VOID FASTCALL KeReleaseQueuedSpinLock(IN KSPIN_LOCK_QUEUE_NUMBER LockNumber, IN KIRQL OldIrql)
Definition: spinlock.c:154
KIRQL FASTCALL KeAcquireQueuedSpinLock(IN KSPIN_LOCK_QUEUE_NUMBER LockNumber)
Definition: spinlock.c:108
@ SystemPteSpace
Definition: miarm.h:403
@ MaximumPtePoolTypes
Definition: miarm.h:405
enum _MMSYSTEM_PTE_POOL_TYPE MMSYSTEM_PTE_POOL_TYPE
#define ASSERT(a)
Definition: mode.c:44
FORCEINLINE VOID KeFlushProcessTb(VOID)
Definition: ke.h:272
#define MI_SYSTEM_PTE_BASE
Definition: mm.h:45
#define MM_EMPTY_PTE_LIST
Definition: mm.h:87
long LONG
Definition: pedump.c:60
#define DPRINT
Definition: sndvol32.h:71
ULONG64 OneEntry
Definition: mmtypes.h:139
ULONG64 NextEntry
Definition: mmtypes.h:145
union _MMPTE::@2330 u
MMPTE_LIST List
Definition: mmtypes.h:222
ULONG_PTR Long
Definition: mmtypes.h:215
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
PMMPTE MmSystemPtesStart[MaximumPtePoolTypes]
Definition: syspte.c:22
PMMPTE MmSystemPtesEnd[MaximumPtePoolTypes]
Definition: syspte.c:23
LONG MmSysPteListBySizeCount[5]
Definition: syspte.c:36
VOID NTAPI MiReleaseSystemPtes(IN PMMPTE StartingPte, IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
Definition: syspte.c:264
PMMPTE MmSystemPteBase
Definition: syspte.c:21
FORCEINLINE ULONG MI_GET_CLUSTER_SIZE(IN PMMPTE Pte)
Definition: syspte.c:71
MMPTE MmFirstFreeSystemPte[MaximumPtePoolTypes]
Definition: syspte.c:24
ULONG MmTotalSystemPtes
Definition: syspte.c:26
const UCHAR MmSysPteTables[]
Definition: syspte.c:29
ULONG MmTotalFreeSystemPtes[MaximumPtePoolTypes]
Definition: syspte.c:25
PMMPTE NTAPI MiReserveSystemPtes(IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType)
Definition: syspte.c:246
PMMPTE NTAPI MiReserveAlignedSystemPtes(IN ULONG NumberOfPtes, IN MMSYSTEM_PTE_POOL_TYPE SystemPtePoolType, IN ULONG Alignment)
Definition: syspte.c:88
ULONG MiNumberOfExtraSystemPdes
Definition: syspte.c:27
#define NTAPI
Definition: typedefs.h:36
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
#define IN
Definition: typedefs.h:39
uint32_t ULONG
Definition: typedefs.h:59
_Must_inspect_result_ _In_ WDFDEVICE _In_ DEVICE_REGISTRY_PROPERTY _In_ _Strict_type_match_ POOL_TYPE PoolType
Definition: wdfdevice.h:3815
#define FORCEINLINE
Definition: wdftypes.h:67
_Requires_lock_held_ Interrupt _Releases_lock_ Interrupt _In_ _IRQL_restores_ KIRQL OldIrql
Definition: kefuncs.h:778
@ LockQueueSystemSpaceLock
Definition: ketypes.h:661
unsigned char UCHAR
Definition: xmlstorage.h:181