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)
10 /* INCLUDES *******************************************************************/
16 #define MODULE_INVOLVED_IN_ARM3
17 #include <mm/ARM3/miarm.h>
19 /* Include Mm version of AVL support */
21 #include <lib/rtl/avlsupp.c>
23 /* GLOBALS ********************************************************************/
25 CHAR MmReadWrite
[32] =
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
,
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
,
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
,
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
,
44 /* FUNCTIONS ******************************************************************/
48 MiLocateAddress(IN PVOID VirtualAddress
)
52 PMM_AVL_TABLE Table
= &PsGetCurrentProcess()->VadRoot
;
53 TABLE_SEARCH_RESULT SearchResult
;
55 /* Start with the the hint */
56 FoundVad
= (PMMVAD
)Table
->NodeHint
;
57 if (!FoundVad
) return NULL
;
59 /* Check if this VPN is in the hint, if so, use it */
60 Vpn
= (ULONG_PTR
)VirtualAddress
>> PAGE_SHIFT
;
61 if ((Vpn
>= FoundVad
->StartingVpn
) && (Vpn
<= FoundVad
->EndingVpn
)) return FoundVad
;
63 /* VAD hint didn't work, go look for it */
64 SearchResult
= RtlpFindAvlTableNodeOrParent(Table
,
66 (PMMADDRESS_NODE
*)&FoundVad
);
67 if (SearchResult
!= TableFoundNode
) return NULL
;
69 /* We found it, update the hint */
70 ASSERT(FoundVad
!= NULL
);
71 ASSERT((Vpn
>= FoundVad
->StartingVpn
) && (Vpn
<= FoundVad
->EndingVpn
));
72 Table
->NodeHint
= FoundVad
;
78 MiCheckForConflictingNode(IN ULONG_PTR StartVpn
,
80 IN PMM_AVL_TABLE Table
,
81 OUT PMMADDRESS_NODE
*NodeOrParent
)
83 PMMADDRESS_NODE ParentNode
, CurrentNode
;
85 /* If the tree is empty, there is no conflict */
86 if (Table
->NumberGenericTableElements
== 0) return TableEmptyTree
;
88 /* Start looping from the root node */
89 CurrentNode
= RtlRightChildAvl(&Table
->BalancedRoot
);
90 ASSERT(CurrentNode
!= NULL
);
93 ParentNode
= CurrentNode
;
95 /* This address comes after */
96 if (StartVpn
> CurrentNode
->EndingVpn
)
98 /* Keep searching on the right */
99 CurrentNode
= RtlRightChildAvl(CurrentNode
);
101 else if (EndVpn
< CurrentNode
->StartingVpn
)
103 /* This address ends before the node starts, search on the left */
104 CurrentNode
= RtlLeftChildAvl(CurrentNode
);
108 /* This address is part of this node, return it */
109 *NodeOrParent
= ParentNode
;
110 return TableFoundNode
;
114 /* There is no more child, save the current node as parent */
115 *NodeOrParent
= ParentNode
;
116 if (StartVpn
> ParentNode
->EndingVpn
)
118 return TableInsertAsRight
;
122 return TableInsertAsLeft
;
128 MiInsertNode(IN PMM_AVL_TABLE Table
,
129 IN PMMADDRESS_NODE NewNode
,
130 IN PMMADDRESS_NODE Parent
,
131 IN TABLE_SEARCH_RESULT Result
)
135 /* Insert it into the tree */
136 RtlpInsertAvlTreeNode(Table
, NewNode
, Parent
, Result
);
138 /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
139 Vad
= (PMMVAD_LONG
)NewNode
;
140 if (Vad
->u
.VadFlags
.Spare
== 0)
143 PMEMORY_AREA MemoryArea
;
145 PEPROCESS Process
= CONTAINING_RECORD(Table
, EPROCESS
, VadRoot
);
146 PVOID AllocatedBase
= (PVOID
)(Vad
->StartingVpn
<< PAGE_SHIFT
);
148 Size
= ((Vad
->EndingVpn
+ 1) - Vad
->StartingVpn
) << PAGE_SHIFT
;
149 Status
= MmCreateMemoryArea(&Process
->Vm
,
150 MEMORY_AREA_OWNED_BY_ARM3
,
158 ASSERT(NT_SUCCESS(Status
));
160 /* Check if this is VM VAD */
161 if (Vad
->ControlArea
== NULL
)
163 /* We store the reactos MEMORY_AREA here */
164 Vad
->FirstPrototypePte
= (PMMPTE
)MemoryArea
;
168 /* This is a section VAD. Store the MAREA here for now */
169 ASSERT(Vad
->u4
.Banked
== (PVOID
)0xDEADBABE);
170 Vad
->u4
.Banked
= (PVOID
)MemoryArea
;
177 MiInsertVad(IN PMMVAD Vad
,
178 IN PEPROCESS Process
)
180 TABLE_SEARCH_RESULT Result
;
181 PMMADDRESS_NODE Parent
= NULL
;
183 /* Validate the VAD and set it as the current hint */
184 ASSERT(Vad
->EndingVpn
>= Vad
->StartingVpn
);
185 Process
->VadRoot
.NodeHint
= Vad
;
187 /* Find the parent VAD and where this child should be inserted */
188 Result
= RtlpFindAvlTableNodeOrParent(&Process
->VadRoot
, (PVOID
)Vad
->StartingVpn
, &Parent
);
189 ASSERT(Result
!= TableFoundNode
);
190 ASSERT((Parent
!= NULL
) || (Result
== TableEmptyTree
));
192 /* Do the actual insert operation */
193 MiLockProcessWorkingSetUnsafe(PsGetCurrentProcess(), PsGetCurrentThread());
194 MiInsertNode(&Process
->VadRoot
, (PVOID
)Vad
, Parent
, Result
);
195 MiUnlockProcessWorkingSetUnsafe(PsGetCurrentProcess(), PsGetCurrentThread());
202 _In_ ULONG_PTR
*BaseAddress
,
203 _In_ SIZE_T ViewSize
,
204 _In_ ULONG_PTR HighestAddress
,
205 _In_ ULONG_PTR Alignment
,
206 _In_ ULONG AllocationType
)
208 ULONG_PTR StartingAddress
, EndingAddress
;
209 PEPROCESS CurrentProcess
;
210 PETHREAD CurrentThread
;
211 TABLE_SEARCH_RESULT Result
;
212 PMMADDRESS_NODE Parent
;
214 /* Align the view size to pages */
215 ViewSize
= ALIGN_UP_BY(ViewSize
, PAGE_SIZE
);
217 /* Get the current process */
218 CurrentProcess
= PsGetCurrentProcess();
220 /* Acquire the address creation lock and make sure the process is alive */
221 KeAcquireGuardedMutex(&CurrentProcess
->AddressCreationLock
);
222 if (CurrentProcess
->VmDeleted
)
224 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
225 DPRINT1("The process is dying\n");
226 return STATUS_PROCESS_IS_TERMINATING
;
229 /* Did the caller specify an address? */
230 if (*BaseAddress
== 0)
232 /* Make sure HighestAddress is not too large */
233 HighestAddress
= min(HighestAddress
, (ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
);
235 /* Which way should we search? */
236 if ((AllocationType
& MEM_TOP_DOWN
) || CurrentProcess
->VmTopDown
)
238 /* Find an address top-down */
239 Result
= MiFindEmptyAddressRangeDownTree(ViewSize
,
242 &CurrentProcess
->VadRoot
,
248 /* Find an address bottom-up */
249 Result
= MiFindEmptyAddressRangeInTree(ViewSize
,
251 &CurrentProcess
->VadRoot
,
256 /* Get the ending address, which is the last piece we need for the VAD */
257 EndingAddress
= StartingAddress
+ ViewSize
- 1;
259 /* Check if we found a suitable location */
260 if ((Result
== TableFoundNode
) || (EndingAddress
> HighestAddress
))
262 DPRINT1("Not enough free space to insert this VAD node!\n");
263 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
264 return STATUS_NO_MEMORY
;
267 ASSERT(StartingAddress
!= 0);
268 ASSERT(StartingAddress
< (ULONG_PTR
)HighestAddress
);
269 ASSERT(EndingAddress
> StartingAddress
);
273 /* Calculate the starting and ending address */
274 StartingAddress
= ALIGN_DOWN_BY(*BaseAddress
, Alignment
);
275 EndingAddress
= StartingAddress
+ ViewSize
- 1;
277 /* Make sure it doesn't conflict with an existing allocation */
278 Result
= MiCheckForConflictingNode(StartingAddress
>> PAGE_SHIFT
,
279 EndingAddress
>> PAGE_SHIFT
,
280 &CurrentProcess
->VadRoot
,
282 if (Result
== TableFoundNode
)
284 DPRINT1("Given address conflicts with existing node\n");
285 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
286 return STATUS_CONFLICTING_ADDRESSES
;
290 /* Now set the VAD address */
291 Vad
->StartingVpn
= StartingAddress
>> PAGE_SHIFT
;
292 Vad
->EndingVpn
= EndingAddress
>> PAGE_SHIFT
;
294 /* Check if we already need to charge for the pages */
295 if ((Vad
->u
.VadFlags
.PrivateMemory
&& Vad
->u
.VadFlags
.MemCommit
) ||
296 (!Vad
->u
.VadFlags
.PrivateMemory
&&
297 (Vad
->u
.VadFlags
.Protection
& PAGE_WRITECOPY
)))
299 /* Set the commit charge */
300 Vad
->u
.VadFlags
.CommitCharge
= ViewSize
/ PAGE_SIZE
;
303 /* Check if the VAD is to be secured */
304 if (Vad
->u2
.VadFlags2
.OneSecured
)
306 /* This *must* be a long VAD! */
307 ASSERT(Vad
->u2
.VadFlags2
.LongVad
);
309 /* Yeah this is retarded, I didn't invent it! */
310 ((PMMVAD_LONG
)Vad
)->u3
.Secured
.StartVpn
= StartingAddress
;
311 ((PMMVAD_LONG
)Vad
)->u3
.Secured
.EndVpn
= EndingAddress
;
314 /* Lock the working set */
315 CurrentThread
= PsGetCurrentThread();
316 MiLockProcessWorkingSetUnsafe(CurrentProcess
, CurrentThread
);
319 CurrentProcess
->VadRoot
.NodeHint
= Vad
;
320 MiInsertNode(&CurrentProcess
->VadRoot
, (PVOID
)Vad
, Parent
, Result
);
322 /* Release the working set */
323 MiUnlockProcessWorkingSetUnsafe(CurrentProcess
, CurrentThread
);
325 /* Update the process' virtual size, and peak virtual size */
326 CurrentProcess
->VirtualSize
+= ViewSize
;
327 if (CurrentProcess
->VirtualSize
> CurrentProcess
->PeakVirtualSize
)
329 CurrentProcess
->PeakVirtualSize
= CurrentProcess
->VirtualSize
;
332 /* Unlock the address space */
333 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
335 *BaseAddress
= StartingAddress
;
336 return STATUS_SUCCESS
;
341 MiInsertBasedSection(IN PSECTION Section
)
343 TABLE_SEARCH_RESULT Result
;
344 PMMADDRESS_NODE Parent
= NULL
;
345 ASSERT(Section
->Address
.EndingVpn
>= Section
->Address
.StartingVpn
);
347 /* Find the parent VAD and where this child should be inserted */
348 Result
= RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot
, (PVOID
)Section
->Address
.StartingVpn
, &Parent
);
349 ASSERT(Result
!= TableFoundNode
);
350 ASSERT((Parent
!= NULL
) || (Result
== TableEmptyTree
));
351 MiInsertNode(&MmSectionBasedRoot
, &Section
->Address
, Parent
, Result
);
356 MiRemoveNode(IN PMMADDRESS_NODE Node
,
357 IN PMM_AVL_TABLE Table
)
361 /* Call the AVL code */
362 RtlpDeleteAvlTreeNode(Table
, Node
);
364 /* Decrease element count */
365 Table
->NumberGenericTableElements
--;
367 /* Check if this node was the hint */
368 if (Table
->NodeHint
== Node
)
370 /* Get a new hint, unless we're empty now, in which case nothing */
371 if (!Table
->NumberGenericTableElements
) Table
->NodeHint
= NULL
;
372 else Table
->NodeHint
= Table
->BalancedRoot
.RightChild
;
375 /* Free the node from ReactOS view as well */
376 Vad
= (PMMVAD_LONG
)Node
;
377 if (Vad
->u
.VadFlags
.Spare
== 0)
379 PMEMORY_AREA MemoryArea
;
382 /* Check if this is VM VAD */
383 if (Vad
->ControlArea
== NULL
)
385 /* We store the ReactOS MEMORY_AREA here */
386 MemoryArea
= (PMEMORY_AREA
)Vad
->FirstPrototypePte
;
390 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
391 MemoryArea
= (PMEMORY_AREA
)Vad
->u4
.Banked
;
394 /* Make sure one actually still exists */
397 /* Make sure we have not already freed it */
398 ASSERT(MemoryArea
!= (PVOID
)0xDEADBAB1);
400 /* Get the process */
401 Process
= CONTAINING_RECORD(Table
, EPROCESS
, VadRoot
);
403 /* We only create fake memory-areas for ARM3 VADs */
404 ASSERT(MemoryArea
->Type
== MEMORY_AREA_OWNED_BY_ARM3
);
405 ASSERT(MemoryArea
->Vad
== NULL
);
408 MmFreeMemoryArea(&Process
->Vm
, MemoryArea
, NULL
, NULL
);
410 /* Check if this is VM VAD */
411 if (Vad
->ControlArea
== NULL
)
413 /* Delete the pointer to it */
414 Vad
->FirstPrototypePte
= (PVOID
)0xDEADBAB1;
418 /* Delete the pointer to it */
419 Vad
->u4
.Banked
= (PVOID
)0xDEADBAB1;
427 MiGetPreviousNode(IN PMMADDRESS_NODE Node
)
429 PMMADDRESS_NODE Parent
;
431 /* Get the left child */
432 if (RtlLeftChildAvl(Node
))
434 /* Get right-most child */
435 Node
= RtlLeftChildAvl(Node
);
436 while (RtlRightChildAvl(Node
)) Node
= RtlRightChildAvl(Node
);
440 Parent
= RtlParentAvl(Node
);
441 ASSERT(Parent
!= NULL
);
442 while (Parent
!= Node
)
444 /* The parent should be a right child, return the real predecessor */
445 if (RtlIsRightChildAvl(Node
))
447 /* Return it unless it's the root */
448 if (Parent
== RtlParentAvl(Parent
)) Parent
= NULL
;
452 /* Keep lopping until we find our parent */
454 Parent
= RtlParentAvl(Node
);
463 MiGetNextNode(IN PMMADDRESS_NODE Node
)
465 PMMADDRESS_NODE Parent
;
467 /* Get the right child */
468 if (RtlRightChildAvl(Node
))
470 /* Get left-most child */
471 Node
= RtlRightChildAvl(Node
);
472 while (RtlLeftChildAvl(Node
)) Node
= RtlLeftChildAvl(Node
);
476 Parent
= RtlParentAvl(Node
);
477 ASSERT(Parent
!= NULL
);
478 while (Parent
!= Node
)
480 /* The parent should be a left child, return the real predecessor */
481 if (RtlIsLeftChildAvl(Node
))
487 /* Keep lopping until we find our parent */
489 Parent
= RtlParentAvl(Node
);
498 MiFindEmptyAddressRangeInTree(IN SIZE_T Length
,
499 IN ULONG_PTR Alignment
,
500 IN PMM_AVL_TABLE Table
,
501 OUT PMMADDRESS_NODE
*PreviousVad
,
504 PMMADDRESS_NODE Node
, PreviousNode
;
505 ULONG_PTR PageCount
, AlignmentVpn
, LowVpn
, HighVpn
;
508 /* Calculate page numbers for the length, alignment, and starting address */
509 PageCount
= BYTES_TO_PAGES(Length
);
510 AlignmentVpn
= Alignment
>> PAGE_SHIFT
;
511 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MM_LOWEST_USER_ADDRESS
>> PAGE_SHIFT
, AlignmentVpn
);
513 /* Check if the table is empty */
514 if (Table
->NumberGenericTableElements
== 0)
516 /* Tree is empty, the candidate address is already the best one */
517 *Base
= LowVpn
<< PAGE_SHIFT
;
518 return TableEmptyTree
;
521 /* Otherwise, follow the leftmost child of the right root node's child */
522 Node
= RtlRightChildAvl(&Table
->BalancedRoot
);
523 while (RtlLeftChildAvl(Node
)) Node
= RtlLeftChildAvl(Node
);
525 /* Start a search to find a gap */
529 /* Check if the gap below the current node is suitable */
530 if (Node
->StartingVpn
>= LowVpn
+ PageCount
)
532 /* There is enough space to add our node */
533 *Base
= LowVpn
<< PAGE_SHIFT
;
535 /* Can we use the current node as parent? */
536 if (RtlLeftChildAvl(Node
) == NULL
)
538 /* Node has no left child, so use it as parent */
540 return TableInsertAsLeft
;
544 /* Node has a left child, this means that the previous node is
545 the right-most child of it's left child and can be used as
546 the parent. In case we use the space before the left-most
547 node, it's left child must be NULL. */
548 ASSERT(PreviousNode
!= NULL
);
549 ASSERT(RtlRightChildAvl(PreviousNode
) == NULL
);
550 *PreviousVad
= PreviousNode
;
551 return TableInsertAsRight
;
555 /* The next candidate is above the current node */
556 if (Node
->EndingVpn
>= LowVpn
)
557 LowVpn
= ALIGN_UP_BY(Node
->EndingVpn
+ 1, AlignmentVpn
);
559 /* Remember the current node and go to the next node */
561 Node
= MiGetNextNode(Node
);
564 /* We're up to the highest VAD, will this allocation fit above it? */
565 HighVpn
= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1) / PAGE_SIZE
;
566 if (HighVpn
>= LowVpn
+ PageCount
)
568 /* Yes! Use this VAD to store the allocation */
569 *PreviousVad
= PreviousNode
;
570 *Base
= LowVpn
<< PAGE_SHIFT
;
571 return TableInsertAsRight
;
574 /* Nyet, there's no free address space for this allocation, so we'll fail */
575 return TableFoundNode
;
580 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length
,
581 IN ULONG_PTR BoundaryAddress
,
582 IN ULONG_PTR Alignment
,
583 IN PMM_AVL_TABLE Table
,
585 OUT PMMADDRESS_NODE
*Parent
)
587 PMMADDRESS_NODE Node
, OldNode
, Child
;
588 ULONG_PTR LowVpn
, HighVpn
, AlignmentVpn
;
589 PFN_NUMBER PageCount
;
592 ASSERT(BoundaryAddress
);
593 ASSERT(BoundaryAddress
<= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
));
594 ASSERT((Alignment
& (PAGE_SIZE
- 1)) == 0);
596 /* Calculate page numbers for the length and alignment */
597 Length
= ROUND_TO_PAGES(Length
);
598 PageCount
= Length
>> PAGE_SHIFT
;
599 AlignmentVpn
= Alignment
/ PAGE_SIZE
;
601 /* Check if there is enough space below the boundary */
602 if ((ALIGN_UP_BY((ULONG_PTR
)MM_LOWEST_USER_ADDRESS
, Alignment
) + Length
) >
603 (BoundaryAddress
+ 1))
605 return TableFoundNode
;
608 /* Check if the table is empty */
609 if (Table
->NumberGenericTableElements
== 0)
611 /* Tree is empty, the candidate address is already the best one */
612 *Base
= ALIGN_DOWN_BY(BoundaryAddress
+ 1 - Length
, Alignment
);
613 return TableEmptyTree
;
616 /* Calculate the initial upper margin */
617 HighVpn
= (BoundaryAddress
+ 1) >> PAGE_SHIFT
;
619 /* Starting from the root, follow the right children until we found a node
620 that ends above the boundary */
621 Node
= RtlRightChildAvl(&Table
->BalancedRoot
);
622 while ((Node
->EndingVpn
< HighVpn
) &&
623 ((Child
= RtlRightChildAvl(Node
)) != NULL
)) Node
= Child
;
625 /* Now loop the Vad nodes */
628 /* Calculate the lower margin */
629 LowVpn
= ALIGN_UP_BY(Node
->EndingVpn
+ 1, AlignmentVpn
);
631 /* Check if the current bounds are suitable */
632 if ((HighVpn
> LowVpn
) && ((HighVpn
- LowVpn
) >= PageCount
))
634 /* There is enough space to add our node */
635 LowVpn
= ALIGN_DOWN_BY(HighVpn
- PageCount
, AlignmentVpn
);
636 *Base
= LowVpn
<< PAGE_SHIFT
;
638 /* Can we use the current node as parent? */
639 if (!RtlRightChildAvl(Node
))
641 /* Node has no right child, so use it as parent */
643 return TableInsertAsRight
;
647 /* Node has a right child, the node we had before is the most
648 left grandchild of that right child, use it as parent. */
650 return TableInsertAsLeft
;
654 /* Update the upper margin if necessary */
655 if (Node
->StartingVpn
< HighVpn
) HighVpn
= Node
->StartingVpn
;
657 /* Remember the current node and go to the previous node */
659 Node
= MiGetPreviousNode(Node
);
662 /* Check if there's enough space before the lowest Vad */
663 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
, Alignment
) / PAGE_SIZE
;
664 if ((HighVpn
> LowVpn
) && ((HighVpn
- LowVpn
) >= PageCount
))
666 /* There is enough space to add our address */
667 LowVpn
= ALIGN_DOWN_BY(HighVpn
- PageCount
, Alignment
>> PAGE_SHIFT
);
668 *Base
= LowVpn
<< PAGE_SHIFT
;
670 return TableInsertAsLeft
;
673 /* No address space left at all */
676 return TableFoundNode
;
681 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length
,
682 IN ULONG_PTR BoundaryAddress
,
683 IN ULONG_PTR Alignment
,
684 IN PMM_AVL_TABLE Table
,
687 PMMADDRESS_NODE Node
, LowestNode
;
688 ULONG_PTR LowVpn
, BestVpn
;
691 ASSERT(Table
== &MmSectionBasedRoot
);
692 ASSERT(BoundaryAddress
);
693 ASSERT(BoundaryAddress
<= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1));
695 /* Compute page length, make sure the boundary address is valid */
696 Length
= ROUND_TO_PAGES(Length
);
697 if ((BoundaryAddress
+ 1) < Length
) return STATUS_NO_MEMORY
;
699 /* Check if the table is empty */
700 BestVpn
= ROUND_DOWN(BoundaryAddress
+ 1 - Length
, Alignment
);
701 if (Table
->NumberGenericTableElements
== 0)
703 /* Tree is empty, the candidate address is already the best one */
705 return STATUS_SUCCESS
;
708 /* Go to the right-most node which should be the biggest address */
709 Node
= Table
->BalancedRoot
.RightChild
;
710 while (RtlRightChildAvl(Node
)) Node
= RtlRightChildAvl(Node
);
712 /* Check if we can fit in here */
713 LowVpn
= ROUND_UP(Node
->EndingVpn
+ 1, Alignment
);
714 if ((LowVpn
< BoundaryAddress
) && (Length
<= (BoundaryAddress
- LowVpn
)))
716 #if (NTDDI_VERSION >= NTDDI_VISTA)
717 /* Return the address. */
720 /* Note: this is a compatibility hack that mimics a bug in the 2k3
721 kernel. It will can waste up to Alignment bytes of memory above
722 the allocation. This bug was fixed in Windows Vista */
723 *Base
= ROUND_DOWN(BoundaryAddress
- Length
, Alignment
);
725 return STATUS_SUCCESS
;
728 /* Now loop the Vad nodes */
731 /* Break out if we've reached the last node */
732 LowestNode
= MiGetPreviousNode(Node
);
733 if (!LowestNode
) break;
735 /* Check if this node could contain the requested address */
736 LowVpn
= ROUND_UP(LowestNode
->EndingVpn
+ 1, Alignment
);
737 if ((LowestNode
->EndingVpn
< BestVpn
) &&
738 (LowVpn
< Node
->StartingVpn
) &&
739 (Length
<= (Node
->StartingVpn
- LowVpn
)))
741 /* Check if we need to take BoundaryAddress into account */
742 if (BoundaryAddress
< Node
->StartingVpn
)
744 /* Return the optimal VPN address */
746 return STATUS_SUCCESS
;
750 /* The upper margin is given by the Node's starting address */
751 *Base
= ROUND_DOWN(Node
->StartingVpn
- Length
, Alignment
);
752 return STATUS_SUCCESS
;
756 /* Move to the next node */
760 /* Check if there's enough space before the lowest Vad */
761 if ((Node
->StartingVpn
> (ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
) &&
762 ((Node
->StartingVpn
- (ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
) >= Length
))
764 /* Check if it fits in perfectly */
765 if (BoundaryAddress
< Node
->StartingVpn
)
767 /* Return the optimal VPN address */
769 return STATUS_SUCCESS
;
772 /* Return an aligned base address within this node */
773 *Base
= ROUND_DOWN(Node
->StartingVpn
- Length
, Alignment
);
774 return STATUS_SUCCESS
;
777 /* No address space left at all */
778 return STATUS_NO_MEMORY
;
783 MiCheckSecuredVad(IN PMMVAD Vad
,
786 IN ULONG ProtectionMask
)
788 ULONG_PTR StartAddress
, EndAddress
;
790 /* Compute start and end address */
791 StartAddress
= (ULONG_PTR
)Base
;
792 EndAddress
= StartAddress
+ Size
- 1;
794 /* Are we deleting/unmapping, or changing? */
795 if (ProtectionMask
< MM_DELETE_CHECK
)
797 /* Changing... are we allowed to do so? */
798 if ((Vad
->u
.VadFlags
.NoChange
== 1) &&
799 (Vad
->u2
.VadFlags2
.SecNoChange
== 1) &&
800 (Vad
->u
.VadFlags
.Protection
!= ProtectionMask
))
803 DPRINT1("Trying to mess with a no-change VAD!\n");
804 return STATUS_INVALID_PAGE_PROTECTION
;
809 /* This is allowed */
813 /* ARM3 doesn't support this yet */
814 ASSERT(Vad
->u2
.VadFlags2
.MultipleSecured
== 0);
816 /* Is this a one-secured VAD, like a TEB or PEB? */
817 if (Vad
->u2
.VadFlags2
.OneSecured
)
819 /* Is this allocation being described by the VAD? */
820 if ((StartAddress
<= ((PMMVAD_LONG
)Vad
)->u3
.Secured
.EndVpn
) &&
821 (EndAddress
>= ((PMMVAD_LONG
)Vad
)->u3
.Secured
.StartVpn
))
824 if (ProtectionMask
& MM_DECOMMIT
)
826 DPRINT1("Not allowed to change protection on guard page!\n");
827 return STATUS_INVALID_PAGE_PROTECTION
;
830 /* ARM3 doesn't have read-only VADs yet */
831 ASSERT(Vad
->u2
.VadFlags2
.ReadOnly
== 0);
833 /* Check if read-write protections are allowed */
834 if (MmReadWrite
[ProtectionMask
] < MM_READ_WRITE_ALLOWED
)
836 DPRINT1("Invalid protection mask for RW access!\n");
837 return STATUS_INVALID_PAGE_PROTECTION
;
842 /* All good, allow the change */
843 return STATUS_SUCCESS
;