1 /*
2 * PROJECT: ReactOS Kernel
3 * LICENSE: BSD - See COPYING.ARM in the top level directory
4 * FILE: ntoskrnl/mm/ARM3/vadnode.c
5 * PURPOSE: ARM Memory Manager VAD Node Algorithms
6 * PROGRAMMERS: ReactOS Portable Systems Group
7 * Timo Kreuzer (timo.kreuzer@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 /* Include Mm version of AVL support */
20 #include "miavl.h"
21 #include <sdk/lib/rtl/avlsupp.c>
22
23 /* GLOBALS ********************************************************************/
24
25 CHAR MmReadWrite[32] =
26 {
27 MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
28 MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
29 MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
30
31 MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
32 MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
33 MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
34
35 MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
36 MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
37 MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
38
39 MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
40 MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
41 MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
42 };
43
44 /* FUNCTIONS ******************************************************************/
45
46 extern MM_AVL_TABLE MiRosKernelVadRoot;
47
48 #if DBG
49
50 static
51 VOID
MiDbgAssertIsLockedForRead(_In_ PMM_AVL_TABLE Table)52 MiDbgAssertIsLockedForRead(_In_ PMM_AVL_TABLE Table)
53 {
54 if (Table == &MmSectionBasedRoot)
55 {
56 /* Need to hold MmSectionBasedMutex */
57 ASSERT(MmSectionBasedMutex.Owner == KeGetCurrentThread());
58 }
59 else if (Table == &MiRosKernelVadRoot)
60 {
61 /* Need to hold either the system working-set lock or
62 the idle process' AddressCreationLock */
63 ASSERT(PsGetCurrentThread()->OwnsSystemWorkingSetExclusive ||
64 PsGetCurrentThread()->OwnsSystemWorkingSetShared ||
65 (PsIdleProcess->AddressCreationLock.Owner == KeGetCurrentThread()));
66 }
67 else
68 {
69 /* Need to hold either the process working-set lock or
70 the current process' AddressCreationLock */
71 PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
72 ASSERT(MI_WS_OWNER(Process) ||
73 (Process->AddressCreationLock.Owner == KeGetCurrentThread()));
74 }
75 }
76
77 static
78 VOID
MiDbgAssertIsLockedForWrite(_In_ PMM_AVL_TABLE Table)79 MiDbgAssertIsLockedForWrite(_In_ PMM_AVL_TABLE Table)
80 {
81 if (Table == &MmSectionBasedRoot)
82 {
83 /* Need to hold MmSectionBasedMutex */
84 ASSERT(MmSectionBasedMutex.Owner == KeGetCurrentThread());
85 }
86 else if (Table == &MiRosKernelVadRoot)
87 {
88 /* Need to hold both the system working-set lock exclusive and
89 the idle process' AddressCreationLock */
90 ASSERT(PsGetCurrentThread()->OwnsSystemWorkingSetExclusive);
91 ASSERT(PsIdleProcess->AddressCreationLock.Owner == KeGetCurrentThread());
92 }
93 else
94 {
95 /* Need to hold both the process working-set lock exclusive and
96 the current process' AddressCreationLock */
97 PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
98 ASSERT(Process == PsGetCurrentProcess());
99 ASSERT(PsGetCurrentThread()->OwnsProcessWorkingSetExclusive);
100 ASSERT(Process->AddressCreationLock.Owner == KeGetCurrentThread());
101 }
102 }
103
104 #define ASSERT_LOCKED_FOR_READ(Table) MiDbgAssertIsLockedForRead(Table)
105 #define ASSERT_LOCKED_FOR_WRITE(Table) MiDbgAssertIsLockedForWrite(Table)
106
107 #else // DBG
108
109 #define ASSERT_LOCKED_FOR_READ(Table)
110 #define ASSERT_LOCKED_FOR_WRITE(Table)
111
112 #endif // DBG
113
114 PMMVAD
115 NTAPI
MiLocateAddress(IN PVOID VirtualAddress)116 MiLocateAddress(IN PVOID VirtualAddress)
117 {
118 PMMVAD FoundVad;
119 ULONG_PTR Vpn;
120 PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
121 TABLE_SEARCH_RESULT SearchResult;
122
123 ASSERT_LOCKED_FOR_READ(Table);
124
125 /* Start with the the hint */
126 FoundVad = (PMMVAD)Table->NodeHint;
127 if (!FoundVad) return NULL;
128
129 /* Check if this VPN is in the hint, if so, use it */
130 Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
131 if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
132
133 /* VAD hint didn't work, go look for it */
134 SearchResult = RtlpFindAvlTableNodeOrParent(Table,
135 (PVOID)Vpn,
136 (PMMADDRESS_NODE*)&FoundVad);
137 if (SearchResult != TableFoundNode) return NULL;
138
139 /* We found it, update the hint */
140 ASSERT(FoundVad != NULL);
141 ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
142
143 /* We allow this (atomic) update without exclusive lock, because it's a hint only */
144 Table->NodeHint = FoundVad;
145 return FoundVad;
146 }
147
148 TABLE_SEARCH_RESULT
149 NTAPI
MiCheckForConflictingNode(IN ULONG_PTR StartVpn,IN ULONG_PTR EndVpn,IN PMM_AVL_TABLE Table,OUT PMMADDRESS_NODE * NodeOrParent)150 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
151 IN ULONG_PTR EndVpn,
152 IN PMM_AVL_TABLE Table,
153 OUT PMMADDRESS_NODE *NodeOrParent)
154 {
155 PMMADDRESS_NODE ParentNode, CurrentNode;
156
157 ASSERT_LOCKED_FOR_READ(Table);
158
159 /* If the tree is empty, there is no conflict */
160 if (Table->NumberGenericTableElements == 0) return TableEmptyTree;
161
162 /* Start looping from the root node */
163 CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
164 ASSERT(CurrentNode != NULL);
165 while (CurrentNode)
166 {
167 ParentNode = CurrentNode;
168
169 /* This address comes after */
170 if (StartVpn > CurrentNode->EndingVpn)
171 {
172 /* Keep searching on the right */
173 CurrentNode = RtlRightChildAvl(CurrentNode);
174 }
175 else if (EndVpn < CurrentNode->StartingVpn)
176 {
177 /* This address ends before the node starts, search on the left */
178 CurrentNode = RtlLeftChildAvl(CurrentNode);
179 }
180 else
181 {
182 /* This address is part of this node, return it */
183 *NodeOrParent = ParentNode;
184 return TableFoundNode;
185 }
186 }
187
188 /* There is no more child, save the current node as parent */
189 *NodeOrParent = ParentNode;
190 if (StartVpn > ParentNode->EndingVpn)
191 {
192 return TableInsertAsRight;
193 }
194 else
195 {
196 return TableInsertAsLeft;
197 }
198 }
199
200 VOID
201 NTAPI
MiInsertNode(IN PMM_AVL_TABLE Table,IN PMMADDRESS_NODE NewNode,IN PMMADDRESS_NODE Parent,IN TABLE_SEARCH_RESULT Result)202 MiInsertNode(IN PMM_AVL_TABLE Table,
203 IN PMMADDRESS_NODE NewNode,
204 IN PMMADDRESS_NODE Parent,
205 IN TABLE_SEARCH_RESULT Result)
206 {
207 PMMVAD_LONG Vad;
208
209 ASSERT_LOCKED_FOR_WRITE(Table);
210
211 /* Insert it into the tree */
212 RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
213
214 /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
215 Vad = (PMMVAD_LONG)NewNode;
216 if (Vad->u.VadFlags.Spare == 0)
217 {
218 NTSTATUS Status;
219 PMEMORY_AREA MemoryArea;
220 SIZE_T Size;
221 PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
222 PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
223
224 Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
225
226 if (AllocatedBase == NULL)
227 {
228 AllocatedBase = (PVOID)(ULONG_PTR)1;
229 Size -= 1;
230 }
231
232 Status = MmCreateMemoryArea(&Process->Vm,
233 MEMORY_AREA_OWNED_BY_ARM3,
234 &AllocatedBase,
235 Size,
236 PAGE_READWRITE,
237 &MemoryArea,
238 0,
239 PAGE_SIZE);
240 ASSERT(NT_SUCCESS(Status));
241
242 /* Check if this is VM VAD */
243 if (Vad->ControlArea == NULL)
244 {
245 /* We store the reactos MEMORY_AREA here */
246 Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
247 }
248 else
249 {
250 /* This is a section VAD. Store the MAREA here for now */
251 ASSERT(Vad->u4.Banked == (PVOID)(ULONG_PTR)0xDEADBABEDEADBABEULL);
252 Vad->u4.Banked = (PVOID)MemoryArea;
253 }
254 }
255 }
256
257 VOID
258 NTAPI
MiInsertVad(IN PMMVAD Vad,IN PMM_AVL_TABLE VadRoot)259 MiInsertVad(IN PMMVAD Vad,
260 IN PMM_AVL_TABLE VadRoot)
261 {
262 TABLE_SEARCH_RESULT Result;
263 PMMADDRESS_NODE Parent = NULL;
264
265 ASSERT_LOCKED_FOR_WRITE(VadRoot);
266
267 /* Validate the VAD and set it as the current hint */
268 ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
269 VadRoot->NodeHint = Vad;
270
271 /* Find the parent VAD and where this child should be inserted */
272 Result = RtlpFindAvlTableNodeOrParent(VadRoot, (PVOID)Vad->StartingVpn, &Parent);
273 ASSERT(Result != TableFoundNode);
274 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
275
276 /* Do the actual insert operation */
277 MiInsertNode(VadRoot, (PVOID)Vad, Parent, Result);
278 }
279
280 NTSTATUS
281 NTAPI
MiInsertVadEx(_Inout_ PMMVAD Vad,_In_ ULONG_PTR * BaseAddress,_In_ SIZE_T ViewSize,_In_ ULONG_PTR HighestAddress,_In_ ULONG_PTR Alignment,_In_ ULONG AllocationType)282 MiInsertVadEx(
283 _Inout_ PMMVAD Vad,
284 _In_ ULONG_PTR *BaseAddress,
285 _In_ SIZE_T ViewSize,
286 _In_ ULONG_PTR HighestAddress,
287 _In_ ULONG_PTR Alignment,
288 _In_ ULONG AllocationType)
289 {
290 ULONG_PTR StartingAddress, EndingAddress;
291 PEPROCESS CurrentProcess;
292 PETHREAD CurrentThread;
293 TABLE_SEARCH_RESULT Result;
294 PMMADDRESS_NODE Parent;
295
296 /* Align the view size to pages */
297 ViewSize = ALIGN_UP_BY(ViewSize, PAGE_SIZE);
298
299 /* Get the current process */
300 CurrentProcess = PsGetCurrentProcess();
301
302 /* Acquire the address creation lock and make sure the process is alive */
303 KeAcquireGuardedMutex(&CurrentProcess->AddressCreationLock);
304 if (CurrentProcess->VmDeleted)
305 {
306 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
307 DPRINT1("The process is dying\n");
308 return STATUS_PROCESS_IS_TERMINATING;
309 }
310
311 /* Did the caller specify an address? */
312 if (*BaseAddress == 0)
313 {
314 /* Make sure HighestAddress is not too large */
315 HighestAddress = min(HighestAddress, (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS);
316
317 /* Which way should we search? */
318 if ((AllocationType & MEM_TOP_DOWN) || CurrentProcess->VmTopDown)
319 {
320 /* Find an address top-down */
321 Result = MiFindEmptyAddressRangeDownTree(ViewSize,
322 HighestAddress,
323 Alignment,
324 &CurrentProcess->VadRoot,
325 &StartingAddress,
326 &Parent);
327 }
328 else
329 {
330 /* Find an address bottom-up */
331 Result = MiFindEmptyAddressRangeInTree(ViewSize,
332 Alignment,
333 &CurrentProcess->VadRoot,
334 &Parent,
335 &StartingAddress);
336 }
337
338 /* Get the ending address, which is the last piece we need for the VAD */
339 EndingAddress = StartingAddress + ViewSize - 1;
340
341 /* Check if we found a suitable location */
342 if ((Result == TableFoundNode) || (EndingAddress > HighestAddress))
343 {
344 DPRINT1("Not enough free space to insert this VAD node!\n");
345 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
346 return STATUS_NO_MEMORY;
347 }
348
349 ASSERT(StartingAddress != 0);
350 ASSERT(StartingAddress < (ULONG_PTR)HighestAddress);
351 ASSERT(EndingAddress > StartingAddress);
352 }
353 else
354 {
355 /* Calculate the starting and ending address */
356 StartingAddress = ALIGN_DOWN_BY(*BaseAddress, Alignment);
357 EndingAddress = StartingAddress + ViewSize - 1;
358
359 /* Make sure it doesn't conflict with an existing allocation */
360 Result = MiCheckForConflictingNode(StartingAddress >> PAGE_SHIFT,
361 EndingAddress >> PAGE_SHIFT,
362 &CurrentProcess->VadRoot,
363 &Parent);
364 if (Result == TableFoundNode)
365 {
366 DPRINT("Given address conflicts with existing node\n");
367 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
368 return STATUS_CONFLICTING_ADDRESSES;
369 }
370 }
371
372 /* Now set the VAD address */
373 Vad->StartingVpn = StartingAddress >> PAGE_SHIFT;
374 Vad->EndingVpn = EndingAddress >> PAGE_SHIFT;
375
376 /* Check if we already need to charge for the pages */
377 if ((Vad->u.VadFlags.PrivateMemory && Vad->u.VadFlags.MemCommit) ||
378 (!Vad->u.VadFlags.PrivateMemory &&
379 (Vad->u.VadFlags.Protection & PAGE_WRITECOPY)))
380 {
381 /* Set the commit charge */
382 Vad->u.VadFlags.CommitCharge = ViewSize / PAGE_SIZE;
383 }
384
385 /* Check if the VAD is to be secured */
386 if (Vad->u2.VadFlags2.OneSecured)
387 {
388 /* This *must* be a long VAD! */
389 ASSERT(Vad->u2.VadFlags2.LongVad);
390
391 /* Yeah this is retarded, I didn't invent it! */
392 ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn = StartingAddress;
393 ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn = EndingAddress;
394 }
395
396 /* Lock the working set */
397 CurrentThread = PsGetCurrentThread();
398 MiLockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
399
400 /* Insert the VAD */
401 CurrentProcess->VadRoot.NodeHint = Vad;
402 MiInsertNode(&CurrentProcess->VadRoot, (PVOID)Vad, Parent, Result);
403
404 /* Release the working set */
405 MiUnlockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
406
407 /* Update the process' virtual size, and peak virtual size */
408 CurrentProcess->VirtualSize += ViewSize;
409 if (CurrentProcess->VirtualSize > CurrentProcess->PeakVirtualSize)
410 {
411 CurrentProcess->PeakVirtualSize = CurrentProcess->VirtualSize;
412 }
413
414 /* Unlock the address space */
415 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
416
417 *BaseAddress = StartingAddress;
418 return STATUS_SUCCESS;
419 }
420
421 VOID
422 NTAPI
MiInsertBasedSection(IN PSECTION Section)423 MiInsertBasedSection(IN PSECTION Section)
424 {
425 TABLE_SEARCH_RESULT Result;
426 PMMADDRESS_NODE Parent = NULL;
427 ASSERT(Section->Address.EndingVpn >= Section->Address.StartingVpn);
428
429 ASSERT_LOCKED_FOR_WRITE(&MmSectionBasedRoot);
430
431 /* Find the parent VAD and where this child should be inserted */
432 Result = RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot, (PVOID)Section->Address.StartingVpn, &Parent);
433 ASSERT(Result != TableFoundNode);
434 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
435 MiInsertNode(&MmSectionBasedRoot, &Section->Address, Parent, Result);
436 }
437
438 VOID
439 NTAPI
MiRemoveNode(IN PMMADDRESS_NODE Node,IN PMM_AVL_TABLE Table)440 MiRemoveNode(IN PMMADDRESS_NODE Node,
441 IN PMM_AVL_TABLE Table)
442 {
443 PMMVAD_LONG Vad;
444
445 ASSERT_LOCKED_FOR_WRITE(Table);
446
447 /* Call the AVL code */
448 RtlpDeleteAvlTreeNode(Table, Node);
449
450 /* Decrease element count */
451 Table->NumberGenericTableElements--;
452
453 /* Check if this node was the hint */
454 if (Table->NodeHint == Node)
455 {
456 /* Get a new hint, unless we're empty now, in which case nothing */
457 if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
458 else Table->NodeHint = Table->BalancedRoot.RightChild;
459 }
460
461 /* Free the node from ReactOS view as well */
462 Vad = (PMMVAD_LONG)Node;
463 if ((Table != &MmSectionBasedRoot) && (Vad->u.VadFlags.Spare == 0))
464 {
465 PMEMORY_AREA MemoryArea;
466 PEPROCESS Process;
467
468 /* Check if this is VM VAD */
469 if (Vad->ControlArea == NULL)
470 {
471 /* We store the ReactOS MEMORY_AREA here */
472 MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
473 }
474 else
475 {
476 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
477 MemoryArea = (PMEMORY_AREA)Vad->u4.Banked;
478 }
479
480 /* Make sure one actually still exists */
481 if (MemoryArea)
482 {
483 /* Make sure we have not already freed it */
484 ASSERT(MemoryArea != (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL);
485
486 /* Get the process */
487 Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
488
489 /* We only create fake memory-areas for ARM3 VADs */
490 ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
491 ASSERT(MemoryArea->Vad == NULL);
492
493 /* Free it */
494 MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
495
496 /* Check if this is VM VAD */
497 if (Vad->ControlArea == NULL)
498 {
499 /* Delete the pointer to it */
500 Vad->FirstPrototypePte = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL;
501 }
502 else
503 {
504 /* Delete the pointer to it */
505 Vad->u4.Banked = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL;
506 }
507 }
508 }
509 }
510
511 PMMADDRESS_NODE
512 NTAPI
MiGetPreviousNode(IN PMMADDRESS_NODE Node)513 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
514 {
515 PMMADDRESS_NODE Parent;
516
517 /* Get the left child */
518 if (RtlLeftChildAvl(Node))
519 {
520 /* Get right-most child */
521 Node = RtlLeftChildAvl(Node);
522 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
523 return Node;
524 }
525
526 Parent = RtlParentAvl(Node);
527 ASSERT(Parent != NULL);
528 while (Parent != Node)
529 {
530 /* The parent should be a right child, return the real predecessor */
531 if (RtlIsRightChildAvl(Node))
532 {
533 /* Return it unless it's the root */
534 if (Parent == RtlParentAvl(Parent)) Parent = NULL;
535 return Parent;
536 }
537
538 /* Keep lopping until we find our parent */
539 Node = Parent;
540 Parent = RtlParentAvl(Node);
541 }
542
543 /* Nothing found */
544 return NULL;
545 }
546
547 PMMADDRESS_NODE
548 NTAPI
MiGetNextNode(IN PMMADDRESS_NODE Node)549 MiGetNextNode(IN PMMADDRESS_NODE Node)
550 {
551 PMMADDRESS_NODE Parent;
552
553 /* Get the right child */
554 if (RtlRightChildAvl(Node))
555 {
556 /* Get left-most child */
557 Node = RtlRightChildAvl(Node);
558 while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
559 return Node;
560 }
561
562 Parent = RtlParentAvl(Node);
563 ASSERT(Parent != NULL);
564 while (Parent != Node)
565 {
566 /* The parent should be a left child, return the real predecessor */
567 if (RtlIsLeftChildAvl(Node))
568 {
569 /* Return it */
570 return Parent;
571 }
572
573 /* Keep lopping until we find our parent */
574 Node = Parent;
575 Parent = RtlParentAvl(Node);
576 }
577
578 /* Nothing found */
579 return NULL;
580 }
581
582 TABLE_SEARCH_RESULT
583 NTAPI
MiFindEmptyAddressRangeInTree(IN SIZE_T Length,IN ULONG_PTR Alignment,IN PMM_AVL_TABLE Table,OUT PMMADDRESS_NODE * PreviousVad,OUT PULONG_PTR Base)584 MiFindEmptyAddressRangeInTree(IN SIZE_T Length,
585 IN ULONG_PTR Alignment,
586 IN PMM_AVL_TABLE Table,
587 OUT PMMADDRESS_NODE *PreviousVad,
588 OUT PULONG_PTR Base)
589 {
590 PMMADDRESS_NODE Node, PreviousNode;
591 ULONG_PTR PageCount, AlignmentVpn, LowVpn, HighestVpn;
592 ASSERT(Length != 0);
593
594 ASSERT_LOCKED_FOR_READ(Table);
595
596 /* Calculate page numbers for the length, alignment, and starting address */
597 PageCount = BYTES_TO_PAGES(Length);
598 AlignmentVpn = Alignment >> PAGE_SHIFT;
599 LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT, AlignmentVpn);
600
601 /* Check for kernel mode table (memory areas) */
602 if (Table->Unused == 1)
603 {
604 LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
605 }
606
607 /* Check if the table is empty */
608 if (Table->NumberGenericTableElements == 0)
609 {
610 /* Tree is empty, the candidate address is already the best one */
611 *Base = LowVpn << PAGE_SHIFT;
612 return TableEmptyTree;
613 }
614
615 /* Otherwise, follow the leftmost child of the right root node's child */
616 Node = RtlRightChildAvl(&Table->BalancedRoot);
617 while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
618
619 /* Start a search to find a gap */
620 PreviousNode = NULL;
621 while (Node != NULL)
622 {
623 /* Check if the gap below the current node is suitable */
624 if (Node->StartingVpn >= LowVpn + PageCount)
625 {
626 /* There is enough space to add our node */
627 *Base = LowVpn << PAGE_SHIFT;
628
629 /* Can we use the current node as parent? */
630 if (RtlLeftChildAvl(Node) == NULL)
631 {
632 /* Node has no left child, so use it as parent */
633 *PreviousVad = Node;
634 return TableInsertAsLeft;
635 }
636 else
637 {
638 /* Node has a left child, this means that the previous node is
639 the right-most child of it's left child and can be used as
640 the parent. In case we use the space before the left-most
641 node, it's left child must be NULL. */
642 ASSERT(PreviousNode != NULL);
643 ASSERT(RtlRightChildAvl(PreviousNode) == NULL);
644 *PreviousVad = PreviousNode;
645 return TableInsertAsRight;
646 }
647 }
648
649 /* The next candidate is above the current node */
650 if (Node->EndingVpn >= LowVpn)
651 LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
652
653 /* Remember the current node and go to the next node */
654 PreviousNode = Node;
655 Node = MiGetNextNode(Node);
656 }
657
658 /* We're up to the highest VAD, will this allocation fit above it? */
659 HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) / PAGE_SIZE;
660
661 /* Check for kernel mode table (memory areas) */
662 if (Table->Unused == 1)
663 {
664 HighestVpn = ALIGN_UP_BY((ULONG_PTR)(LONG_PTR)-1 >> PAGE_SHIFT, AlignmentVpn);
665 }
666
667 if (HighestVpn >= LowVpn + PageCount)
668 {
669 /* Yes! Use this VAD to store the allocation */
670 *PreviousVad = PreviousNode;
671 *Base = LowVpn << PAGE_SHIFT;
672 return TableInsertAsRight;
673 }
674
675 /* Nyet, there's no free address space for this allocation, so we'll fail */
676 return TableFoundNode;
677 }
678
679 TABLE_SEARCH_RESULT
680 NTAPI
MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,IN ULONG_PTR BoundaryAddress,IN ULONG_PTR Alignment,IN PMM_AVL_TABLE Table,OUT PULONG_PTR Base,OUT PMMADDRESS_NODE * Parent)681 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
682 IN ULONG_PTR BoundaryAddress,
683 IN ULONG_PTR Alignment,
684 IN PMM_AVL_TABLE Table,
685 OUT PULONG_PTR Base,
686 OUT PMMADDRESS_NODE *Parent)
687 {
688 PMMADDRESS_NODE Node, OldNode = NULL, Child;
689 ULONG_PTR LowVpn, HighVpn, AlignmentVpn;
690 PFN_NUMBER PageCount;
691
692 ASSERT_LOCKED_FOR_READ(Table);
693
694 /* Sanity checks */
695 ASSERT(BoundaryAddress);
696 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS));
697 ASSERT((Alignment & (PAGE_SIZE - 1)) == 0);
698
699 /* Calculate page numbers for the length and alignment */
700 Length = ROUND_TO_PAGES(Length);
701 PageCount = Length >> PAGE_SHIFT;
702 AlignmentVpn = Alignment / PAGE_SIZE;
703
704 /* Check for kernel mode table (memory areas) */
705 if (Table->Unused == 1)
706 {
707 LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
708 }
709 else
710 {
711 LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS, Alignment);
712 }
713
714 /* Check if there is enough space below the boundary */
715 if ((LowVpn + Length) > (BoundaryAddress + 1))
716 {
717 return TableFoundNode;
718 }
719
720 /* Check if the table is empty */
721 if (Table->NumberGenericTableElements == 0)
722 {
723 /* Tree is empty, the candidate address is already the best one */
724 *Base = ALIGN_DOWN_BY(BoundaryAddress + 1 - Length, Alignment);
725 return TableEmptyTree;
726 }
727
728 /* Calculate the initial upper margin */
729 HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT;
730
731 /* Starting from the root, follow the right children until we found a node
732 that ends above the boundary */
733 Node = RtlRightChildAvl(&Table->BalancedRoot);
734 while ((Node->EndingVpn < HighVpn) &&
735 ((Child = RtlRightChildAvl(Node)) != NULL)) Node = Child;
736
737 /* Now loop the Vad nodes */
738 while (Node)
739 {
740 /* Calculate the lower margin */
741 LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
742
743 /* Check if the current bounds are suitable */
744 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
745 {
746 /* There is enough space to add our node */
747 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, AlignmentVpn);
748 *Base = LowVpn << PAGE_SHIFT;
749
750 /* Can we use the current node as parent? */
751 if (!RtlRightChildAvl(Node))
752 {
753 /* Node has no right child, so use it as parent */
754 *Parent = Node;
755 return TableInsertAsRight;
756 }
757 else
758 {
759 /* Node has a right child. This means we must have already
760 moved one node left from the right-most node we started
761 with, thus we already have an OldNode! */
762 ASSERT(OldNode != NULL);
763
764 /* The node we had before is the most left grandchild of
765 that right child, use it as parent. */
766 ASSERT(RtlLeftChildAvl(OldNode) == NULL);
767 *Parent = OldNode;
768 return TableInsertAsLeft;
769 }
770 }
771
772 /* Update the upper margin if necessary */
773 if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
774
775 /* Remember the current node and go to the previous node */
776 OldNode = Node;
777 Node = MiGetPreviousNode(Node);
778 }
779
780 /* Check if there's enough space before the lowest Vad */
781 LowVpn = ALIGN_UP_BY((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) / PAGE_SIZE;
782 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
783 {
784 /* There is enough space to add our address */
785 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT);
786 *Base = LowVpn << PAGE_SHIFT;
787 *Parent = OldNode;
788 return TableInsertAsLeft;
789 }
790
791 /* No address space left at all */
792 *Base = 0;
793 *Parent = NULL;
794 return TableFoundNode;
795 }
796
797 NTSTATUS
798 NTAPI
MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length,IN ULONG_PTR BoundaryAddress,IN ULONG_PTR Alignment,IN PMM_AVL_TABLE Table,OUT PULONG_PTR Base)799 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length,
800 IN ULONG_PTR BoundaryAddress,
801 IN ULONG_PTR Alignment,
802 IN PMM_AVL_TABLE Table,
803 OUT PULONG_PTR Base)
804 {
805 PMMADDRESS_NODE Node, LowestNode;
806 ULONG_PTR LowVpn, BestVpn;
807
808 ASSERT_LOCKED_FOR_READ(Table);
809
810 /* Sanity checks */
811 ASSERT(Table == &MmSectionBasedRoot);
812 ASSERT(BoundaryAddress);
813 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
814
815 /* Compute page length, make sure the boundary address is valid */
816 Length = ROUND_TO_PAGES(Length);
817 if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
818
819 /* Check if the table is empty */
820 BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
821 if (Table->NumberGenericTableElements == 0)
822 {
823 /* Tree is empty, the candidate address is already the best one */
824 *Base = BestVpn;
825 return STATUS_SUCCESS;
826 }
827
828 /* Go to the right-most node which should be the biggest address */
829 Node = Table->BalancedRoot.RightChild;
830 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
831
832 /* Check if we can fit in here */
833 LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment);
834 if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn)))
835 {
836 #if (NTDDI_VERSION >= NTDDI_VISTA)
837 /* Return the address. */
838 *Base = BestVpn;
839 #else
840 /* Note: this is a compatibility hack that mimics a bug in the 2k3
841 kernel. It will can waste up to Alignment bytes of memory above
842 the allocation. This bug was fixed in Windows Vista */
843 *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment);
844 #endif
845 return STATUS_SUCCESS;
846 }
847
848 /* Now loop the Vad nodes */
849 do
850 {
851 /* Break out if we've reached the last node */
852 LowestNode = MiGetPreviousNode(Node);
853 if (!LowestNode) break;
854
855 /* Check if this node could contain the requested address */
856 LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment);
857 if ((LowestNode->EndingVpn < BestVpn) &&
858 (LowVpn < Node->StartingVpn) &&
859 (Length <= (Node->StartingVpn - LowVpn)))
860 {
861 /* Check if we need to take BoundaryAddress into account */
862 if (BoundaryAddress < Node->StartingVpn)
863 {
864 /* Return the optimal VPN address */
865 *Base = BestVpn;
866 return STATUS_SUCCESS;
867 }
868 else
869 {
870 /* The upper margin is given by the Node's starting address */
871 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
872 return STATUS_SUCCESS;
873 }
874 }
875
876 /* Move to the next node */
877 Node = LowestNode;
878 } while (TRUE);
879
880 /* Check if there's enough space before the lowest Vad */
881 if ((Node->StartingVpn > (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) &&
882 ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length))
883 {
884 /* Check if it fits in perfectly */
885 if (BoundaryAddress < Node->StartingVpn)
886 {
887 /* Return the optimal VPN address */
888 *Base = BestVpn;
889 return STATUS_SUCCESS;
890 }
891
892 /* Return an aligned base address within this node */
893 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
894 return STATUS_SUCCESS;
895 }
896
897 /* No address space left at all */
898 return STATUS_NO_MEMORY;
899 }
900
901 NTSTATUS
902 NTAPI
MiCheckSecuredVad(IN PMMVAD Vad,IN PVOID Base,IN SIZE_T Size,IN ULONG ProtectionMask)903 MiCheckSecuredVad(IN PMMVAD Vad,
904 IN PVOID Base,
905 IN SIZE_T Size,
906 IN ULONG ProtectionMask)
907 {
908 ULONG_PTR StartAddress, EndAddress;
909
910 /* Compute start and end address */
911 StartAddress = (ULONG_PTR)Base;
912 EndAddress = StartAddress + Size - 1;
913
914 /* Are we deleting/unmapping, or changing? */
915 if (ProtectionMask < MM_DELETE_CHECK)
916 {
917 /* Changing... are we allowed to do so? */
918 if ((Vad->u.VadFlags.NoChange == 1) &&
919 (Vad->u2.VadFlags2.SecNoChange == 1) &&
920 (Vad->u.VadFlags.Protection != ProtectionMask))
921 {
922 /* Nope, bail out */
923 DPRINT1("Trying to mess with a no-change VAD!\n");
924 return STATUS_INVALID_PAGE_PROTECTION;
925 }
926 }
927 else
928 {
929 /* This is allowed */
930 ProtectionMask = 0;
931 }
932
933 /* ARM3 doesn't support this yet */
934 ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0);
935
936 /* Is this a one-secured VAD, like a TEB or PEB? */
937 if (Vad->u2.VadFlags2.OneSecured)
938 {
939 /* Is this allocation being described by the VAD? */
940 if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) &&
941 (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn))
942 {
943 /* Guard page? */
944 if (ProtectionMask & MM_DECOMMIT)
945 {
946 DPRINT1("Not allowed to change protection on guard page!\n");
947 return STATUS_INVALID_PAGE_PROTECTION;
948 }
949
950 /* ARM3 doesn't have read-only VADs yet */
951 ASSERT(Vad->u2.VadFlags2.ReadOnly == 0);
952
953 /* Check if read-write protections are allowed */
954 if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED)
955 {
956 DPRINT1("Invalid protection mask for RW access!\n");
957 return STATUS_INVALID_PAGE_PROTECTION;
958 }
959 }
960 }
961
962 /* All good, allow the change */
963 return STATUS_SUCCESS;
964 }
965
966 /* EOF */
967
968