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 <sdk/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
;
150 if (AllocatedBase
== NULL
)
152 AllocatedBase
= (PVOID
)(ULONG_PTR
)1;
156 Status
= MmCreateMemoryArea(&Process
->Vm
,
157 MEMORY_AREA_OWNED_BY_ARM3
,
164 ASSERT(NT_SUCCESS(Status
));
166 /* Check if this is VM VAD */
167 if (Vad
->ControlArea
== NULL
)
169 /* We store the reactos MEMORY_AREA here */
170 Vad
->FirstPrototypePte
= (PMMPTE
)MemoryArea
;
174 /* This is a section VAD. Store the MAREA here for now */
175 ASSERT(Vad
->u4
.Banked
== (PVOID
)(ULONG_PTR
)0xDEADBABEDEADBABEULL
);
176 Vad
->u4
.Banked
= (PVOID
)MemoryArea
;
183 MiInsertVad(IN PMMVAD Vad
,
184 IN PMM_AVL_TABLE VadRoot
)
186 TABLE_SEARCH_RESULT Result
;
187 PMMADDRESS_NODE Parent
= NULL
;
189 /* Validate the VAD and set it as the current hint */
190 ASSERT(Vad
->EndingVpn
>= Vad
->StartingVpn
);
191 VadRoot
->NodeHint
= Vad
;
193 /* Find the parent VAD and where this child should be inserted */
194 Result
= RtlpFindAvlTableNodeOrParent(VadRoot
, (PVOID
)Vad
->StartingVpn
, &Parent
);
195 ASSERT(Result
!= TableFoundNode
);
196 ASSERT((Parent
!= NULL
) || (Result
== TableEmptyTree
));
198 /* Do the actual insert operation */
199 MiInsertNode(VadRoot
, (PVOID
)Vad
, Parent
, Result
);
206 _In_ ULONG_PTR
*BaseAddress
,
207 _In_ SIZE_T ViewSize
,
208 _In_ ULONG_PTR HighestAddress
,
209 _In_ ULONG_PTR Alignment
,
210 _In_ ULONG AllocationType
)
212 ULONG_PTR StartingAddress
, EndingAddress
;
213 PEPROCESS CurrentProcess
;
214 PETHREAD CurrentThread
;
215 TABLE_SEARCH_RESULT Result
;
216 PMMADDRESS_NODE Parent
;
218 /* Align the view size to pages */
219 ViewSize
= ALIGN_UP_BY(ViewSize
, PAGE_SIZE
);
221 /* Get the current process */
222 CurrentProcess
= PsGetCurrentProcess();
224 /* Acquire the address creation lock and make sure the process is alive */
225 KeAcquireGuardedMutex(&CurrentProcess
->AddressCreationLock
);
226 if (CurrentProcess
->VmDeleted
)
228 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
229 DPRINT1("The process is dying\n");
230 return STATUS_PROCESS_IS_TERMINATING
;
233 /* Did the caller specify an address? */
234 if (*BaseAddress
== 0)
236 /* Make sure HighestAddress is not too large */
237 HighestAddress
= min(HighestAddress
, (ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
);
239 /* Which way should we search? */
240 if ((AllocationType
& MEM_TOP_DOWN
) || CurrentProcess
->VmTopDown
)
242 /* Find an address top-down */
243 Result
= MiFindEmptyAddressRangeDownTree(ViewSize
,
246 &CurrentProcess
->VadRoot
,
252 /* Find an address bottom-up */
253 Result
= MiFindEmptyAddressRangeInTree(ViewSize
,
255 &CurrentProcess
->VadRoot
,
260 /* Get the ending address, which is the last piece we need for the VAD */
261 EndingAddress
= StartingAddress
+ ViewSize
- 1;
263 /* Check if we found a suitable location */
264 if ((Result
== TableFoundNode
) || (EndingAddress
> HighestAddress
))
266 DPRINT1("Not enough free space to insert this VAD node!\n");
267 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
268 return STATUS_NO_MEMORY
;
271 ASSERT(StartingAddress
!= 0);
272 ASSERT(StartingAddress
< (ULONG_PTR
)HighestAddress
);
273 ASSERT(EndingAddress
> StartingAddress
);
277 /* Calculate the starting and ending address */
278 StartingAddress
= ALIGN_DOWN_BY(*BaseAddress
, Alignment
);
279 EndingAddress
= StartingAddress
+ ViewSize
- 1;
281 /* Make sure it doesn't conflict with an existing allocation */
282 Result
= MiCheckForConflictingNode(StartingAddress
>> PAGE_SHIFT
,
283 EndingAddress
>> PAGE_SHIFT
,
284 &CurrentProcess
->VadRoot
,
286 if (Result
== TableFoundNode
)
288 DPRINT1("Given address conflicts with existing node\n");
289 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
290 return STATUS_CONFLICTING_ADDRESSES
;
294 /* Now set the VAD address */
295 Vad
->StartingVpn
= StartingAddress
>> PAGE_SHIFT
;
296 Vad
->EndingVpn
= EndingAddress
>> PAGE_SHIFT
;
298 /* Check if we already need to charge for the pages */
299 if ((Vad
->u
.VadFlags
.PrivateMemory
&& Vad
->u
.VadFlags
.MemCommit
) ||
300 (!Vad
->u
.VadFlags
.PrivateMemory
&&
301 (Vad
->u
.VadFlags
.Protection
& PAGE_WRITECOPY
)))
303 /* Set the commit charge */
304 Vad
->u
.VadFlags
.CommitCharge
= ViewSize
/ PAGE_SIZE
;
307 /* Check if the VAD is to be secured */
308 if (Vad
->u2
.VadFlags2
.OneSecured
)
310 /* This *must* be a long VAD! */
311 ASSERT(Vad
->u2
.VadFlags2
.LongVad
);
313 /* Yeah this is retarded, I didn't invent it! */
314 ((PMMVAD_LONG
)Vad
)->u3
.Secured
.StartVpn
= StartingAddress
;
315 ((PMMVAD_LONG
)Vad
)->u3
.Secured
.EndVpn
= EndingAddress
;
318 /* Lock the working set */
319 CurrentThread
= PsGetCurrentThread();
320 MiLockProcessWorkingSetUnsafe(CurrentProcess
, CurrentThread
);
323 CurrentProcess
->VadRoot
.NodeHint
= Vad
;
324 MiInsertNode(&CurrentProcess
->VadRoot
, (PVOID
)Vad
, Parent
, Result
);
326 /* Release the working set */
327 MiUnlockProcessWorkingSetUnsafe(CurrentProcess
, CurrentThread
);
329 /* Update the process' virtual size, and peak virtual size */
330 CurrentProcess
->VirtualSize
+= ViewSize
;
331 if (CurrentProcess
->VirtualSize
> CurrentProcess
->PeakVirtualSize
)
333 CurrentProcess
->PeakVirtualSize
= CurrentProcess
->VirtualSize
;
336 /* Unlock the address space */
337 KeReleaseGuardedMutex(&CurrentProcess
->AddressCreationLock
);
339 *BaseAddress
= StartingAddress
;
340 return STATUS_SUCCESS
;
345 MiInsertBasedSection(IN PSECTION Section
)
347 TABLE_SEARCH_RESULT Result
;
348 PMMADDRESS_NODE Parent
= NULL
;
349 ASSERT(Section
->Address
.EndingVpn
>= Section
->Address
.StartingVpn
);
351 /* Find the parent VAD and where this child should be inserted */
352 Result
= RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot
, (PVOID
)Section
->Address
.StartingVpn
, &Parent
);
353 ASSERT(Result
!= TableFoundNode
);
354 ASSERT((Parent
!= NULL
) || (Result
== TableEmptyTree
));
355 MiInsertNode(&MmSectionBasedRoot
, &Section
->Address
, Parent
, Result
);
360 MiRemoveNode(IN PMMADDRESS_NODE Node
,
361 IN PMM_AVL_TABLE Table
)
365 /* Call the AVL code */
366 RtlpDeleteAvlTreeNode(Table
, Node
);
368 /* Decrease element count */
369 Table
->NumberGenericTableElements
--;
371 /* Check if this node was the hint */
372 if (Table
->NodeHint
== Node
)
374 /* Get a new hint, unless we're empty now, in which case nothing */
375 if (!Table
->NumberGenericTableElements
) Table
->NodeHint
= NULL
;
376 else Table
->NodeHint
= Table
->BalancedRoot
.RightChild
;
379 /* Free the node from ReactOS view as well */
380 Vad
= (PMMVAD_LONG
)Node
;
381 if ((Table
!= &MmSectionBasedRoot
) && (Vad
->u
.VadFlags
.Spare
== 0))
383 PMEMORY_AREA MemoryArea
;
386 /* Check if this is VM VAD */
387 if (Vad
->ControlArea
== NULL
)
389 /* We store the ReactOS MEMORY_AREA here */
390 MemoryArea
= (PMEMORY_AREA
)Vad
->FirstPrototypePte
;
394 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
395 MemoryArea
= (PMEMORY_AREA
)Vad
->u4
.Banked
;
398 /* Make sure one actually still exists */
401 /* Make sure we have not already freed it */
402 ASSERT(MemoryArea
!= (PVOID
)(ULONG_PTR
)0xDEADBAB1DEADBAB1ULL
);
404 /* Get the process */
405 Process
= CONTAINING_RECORD(Table
, EPROCESS
, VadRoot
);
407 /* We only create fake memory-areas for ARM3 VADs */
408 ASSERT(MemoryArea
->Type
== MEMORY_AREA_OWNED_BY_ARM3
);
409 ASSERT(MemoryArea
->Vad
== NULL
);
412 MmFreeMemoryArea(&Process
->Vm
, MemoryArea
, NULL
, NULL
);
414 /* Check if this is VM VAD */
415 if (Vad
->ControlArea
== NULL
)
417 /* Delete the pointer to it */
418 Vad
->FirstPrototypePte
= (PVOID
)(ULONG_PTR
)0xDEADBAB1DEADBAB1ULL
;
422 /* Delete the pointer to it */
423 Vad
->u4
.Banked
= (PVOID
)(ULONG_PTR
)0xDEADBAB1DEADBAB1ULL
;
431 MiGetPreviousNode(IN PMMADDRESS_NODE Node
)
433 PMMADDRESS_NODE Parent
;
435 /* Get the left child */
436 if (RtlLeftChildAvl(Node
))
438 /* Get right-most child */
439 Node
= RtlLeftChildAvl(Node
);
440 while (RtlRightChildAvl(Node
)) Node
= RtlRightChildAvl(Node
);
444 Parent
= RtlParentAvl(Node
);
445 ASSERT(Parent
!= NULL
);
446 while (Parent
!= Node
)
448 /* The parent should be a right child, return the real predecessor */
449 if (RtlIsRightChildAvl(Node
))
451 /* Return it unless it's the root */
452 if (Parent
== RtlParentAvl(Parent
)) Parent
= NULL
;
456 /* Keep lopping until we find our parent */
458 Parent
= RtlParentAvl(Node
);
467 MiGetNextNode(IN PMMADDRESS_NODE Node
)
469 PMMADDRESS_NODE Parent
;
471 /* Get the right child */
472 if (RtlRightChildAvl(Node
))
474 /* Get left-most child */
475 Node
= RtlRightChildAvl(Node
);
476 while (RtlLeftChildAvl(Node
)) Node
= RtlLeftChildAvl(Node
);
480 Parent
= RtlParentAvl(Node
);
481 ASSERT(Parent
!= NULL
);
482 while (Parent
!= Node
)
484 /* The parent should be a left child, return the real predecessor */
485 if (RtlIsLeftChildAvl(Node
))
491 /* Keep lopping until we find our parent */
493 Parent
= RtlParentAvl(Node
);
502 MiFindEmptyAddressRangeInTree(IN SIZE_T Length
,
503 IN ULONG_PTR Alignment
,
504 IN PMM_AVL_TABLE Table
,
505 OUT PMMADDRESS_NODE
*PreviousVad
,
508 PMMADDRESS_NODE Node
, PreviousNode
;
509 ULONG_PTR PageCount
, AlignmentVpn
, LowVpn
, HighestVpn
;
512 /* Calculate page numbers for the length, alignment, and starting address */
513 PageCount
= BYTES_TO_PAGES(Length
);
514 AlignmentVpn
= Alignment
>> PAGE_SHIFT
;
515 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MM_LOWEST_USER_ADDRESS
>> PAGE_SHIFT
, AlignmentVpn
);
517 /* Check for kernel mode table (memory areas) */
518 if (Table
->Unused
== 1)
520 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MmSystemRangeStart
>> PAGE_SHIFT
, AlignmentVpn
);
523 /* Check if the table is empty */
524 if (Table
->NumberGenericTableElements
== 0)
526 /* Tree is empty, the candidate address is already the best one */
527 *Base
= LowVpn
<< PAGE_SHIFT
;
528 return TableEmptyTree
;
531 /* Otherwise, follow the leftmost child of the right root node's child */
532 Node
= RtlRightChildAvl(&Table
->BalancedRoot
);
533 while (RtlLeftChildAvl(Node
)) Node
= RtlLeftChildAvl(Node
);
535 /* Start a search to find a gap */
539 /* Check if the gap below the current node is suitable */
540 if (Node
->StartingVpn
>= LowVpn
+ PageCount
)
542 /* There is enough space to add our node */
543 *Base
= LowVpn
<< PAGE_SHIFT
;
545 /* Can we use the current node as parent? */
546 if (RtlLeftChildAvl(Node
) == NULL
)
548 /* Node has no left child, so use it as parent */
550 return TableInsertAsLeft
;
554 /* Node has a left child, this means that the previous node is
555 the right-most child of it's left child and can be used as
556 the parent. In case we use the space before the left-most
557 node, it's left child must be NULL. */
558 ASSERT(PreviousNode
!= NULL
);
559 ASSERT(RtlRightChildAvl(PreviousNode
) == NULL
);
560 *PreviousVad
= PreviousNode
;
561 return TableInsertAsRight
;
565 /* The next candidate is above the current node */
566 if (Node
->EndingVpn
>= LowVpn
)
567 LowVpn
= ALIGN_UP_BY(Node
->EndingVpn
+ 1, AlignmentVpn
);
569 /* Remember the current node and go to the next node */
571 Node
= MiGetNextNode(Node
);
574 /* We're up to the highest VAD, will this allocation fit above it? */
575 HighestVpn
= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1) / PAGE_SIZE
;
577 /* Check for kernel mode table (memory areas) */
578 if (Table
->Unused
== 1)
580 HighestVpn
= ALIGN_UP_BY((ULONG_PTR
)(LONG_PTR
)-1 >> PAGE_SHIFT
, AlignmentVpn
);
583 if (HighestVpn
>= LowVpn
+ PageCount
)
585 /* Yes! Use this VAD to store the allocation */
586 *PreviousVad
= PreviousNode
;
587 *Base
= LowVpn
<< PAGE_SHIFT
;
588 return TableInsertAsRight
;
591 /* Nyet, there's no free address space for this allocation, so we'll fail */
592 return TableFoundNode
;
597 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length
,
598 IN ULONG_PTR BoundaryAddress
,
599 IN ULONG_PTR Alignment
,
600 IN PMM_AVL_TABLE Table
,
602 OUT PMMADDRESS_NODE
*Parent
)
604 PMMADDRESS_NODE Node
, OldNode
= NULL
, Child
;
605 ULONG_PTR LowVpn
, HighVpn
, AlignmentVpn
;
606 PFN_NUMBER PageCount
;
609 ASSERT(BoundaryAddress
);
610 ASSERT(BoundaryAddress
<= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
));
611 ASSERT((Alignment
& (PAGE_SIZE
- 1)) == 0);
613 /* Calculate page numbers for the length and alignment */
614 Length
= ROUND_TO_PAGES(Length
);
615 PageCount
= Length
>> PAGE_SHIFT
;
616 AlignmentVpn
= Alignment
/ PAGE_SIZE
;
618 /* Check for kernel mode table (memory areas) */
619 if (Table
->Unused
== 1)
621 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MmSystemRangeStart
>> PAGE_SHIFT
, AlignmentVpn
);
625 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MM_LOWEST_USER_ADDRESS
, Alignment
);
628 /* Check if there is enough space below the boundary */
629 if ((LowVpn
+ Length
) > (BoundaryAddress
+ 1))
631 return TableFoundNode
;
634 /* Check if the table is empty */
635 if (Table
->NumberGenericTableElements
== 0)
637 /* Tree is empty, the candidate address is already the best one */
638 *Base
= ALIGN_DOWN_BY(BoundaryAddress
+ 1 - Length
, Alignment
);
639 return TableEmptyTree
;
642 /* Calculate the initial upper margin */
643 HighVpn
= (BoundaryAddress
+ 1) >> PAGE_SHIFT
;
645 /* Starting from the root, follow the right children until we found a node
646 that ends above the boundary */
647 Node
= RtlRightChildAvl(&Table
->BalancedRoot
);
648 while ((Node
->EndingVpn
< HighVpn
) &&
649 ((Child
= RtlRightChildAvl(Node
)) != NULL
)) Node
= Child
;
651 /* Now loop the Vad nodes */
654 /* Calculate the lower margin */
655 LowVpn
= ALIGN_UP_BY(Node
->EndingVpn
+ 1, AlignmentVpn
);
657 /* Check if the current bounds are suitable */
658 if ((HighVpn
> LowVpn
) && ((HighVpn
- LowVpn
) >= PageCount
))
660 /* There is enough space to add our node */
661 LowVpn
= ALIGN_DOWN_BY(HighVpn
- PageCount
, AlignmentVpn
);
662 *Base
= LowVpn
<< PAGE_SHIFT
;
664 /* Can we use the current node as parent? */
665 if (!RtlRightChildAvl(Node
))
667 /* Node has no right child, so use it as parent */
669 return TableInsertAsRight
;
673 /* Node has a right child. This means we must have already
674 moved one node left from the right-most node we started
675 with, thus we already have an OldNode! */
676 ASSERT(OldNode
!= NULL
);
678 /* The node we had before is the most left grandchild of
679 that right child, use it as parent. */
680 ASSERT(RtlLeftChildAvl(OldNode
) == NULL
);
682 return TableInsertAsLeft
;
686 /* Update the upper margin if necessary */
687 if (Node
->StartingVpn
< HighVpn
) HighVpn
= Node
->StartingVpn
;
689 /* Remember the current node and go to the previous node */
691 Node
= MiGetPreviousNode(Node
);
694 /* Check if there's enough space before the lowest Vad */
695 LowVpn
= ALIGN_UP_BY((ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
, Alignment
) / PAGE_SIZE
;
696 if ((HighVpn
> LowVpn
) && ((HighVpn
- LowVpn
) >= PageCount
))
698 /* There is enough space to add our address */
699 LowVpn
= ALIGN_DOWN_BY(HighVpn
- PageCount
, Alignment
>> PAGE_SHIFT
);
700 *Base
= LowVpn
<< PAGE_SHIFT
;
702 return TableInsertAsLeft
;
705 /* No address space left at all */
708 return TableFoundNode
;
713 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length
,
714 IN ULONG_PTR BoundaryAddress
,
715 IN ULONG_PTR Alignment
,
716 IN PMM_AVL_TABLE Table
,
719 PMMADDRESS_NODE Node
, LowestNode
;
720 ULONG_PTR LowVpn
, BestVpn
;
723 ASSERT(Table
== &MmSectionBasedRoot
);
724 ASSERT(BoundaryAddress
);
725 ASSERT(BoundaryAddress
<= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1));
727 /* Compute page length, make sure the boundary address is valid */
728 Length
= ROUND_TO_PAGES(Length
);
729 if ((BoundaryAddress
+ 1) < Length
) return STATUS_NO_MEMORY
;
731 /* Check if the table is empty */
732 BestVpn
= ROUND_DOWN(BoundaryAddress
+ 1 - Length
, Alignment
);
733 if (Table
->NumberGenericTableElements
== 0)
735 /* Tree is empty, the candidate address is already the best one */
737 return STATUS_SUCCESS
;
740 /* Go to the right-most node which should be the biggest address */
741 Node
= Table
->BalancedRoot
.RightChild
;
742 while (RtlRightChildAvl(Node
)) Node
= RtlRightChildAvl(Node
);
744 /* Check if we can fit in here */
745 LowVpn
= ROUND_UP(Node
->EndingVpn
+ 1, Alignment
);
746 if ((LowVpn
< BoundaryAddress
) && (Length
<= (BoundaryAddress
- LowVpn
)))
748 #if (NTDDI_VERSION >= NTDDI_VISTA)
749 /* Return the address. */
752 /* Note: this is a compatibility hack that mimics a bug in the 2k3
753 kernel. It will can waste up to Alignment bytes of memory above
754 the allocation. This bug was fixed in Windows Vista */
755 *Base
= ROUND_DOWN(BoundaryAddress
- Length
, Alignment
);
757 return STATUS_SUCCESS
;
760 /* Now loop the Vad nodes */
763 /* Break out if we've reached the last node */
764 LowestNode
= MiGetPreviousNode(Node
);
765 if (!LowestNode
) break;
767 /* Check if this node could contain the requested address */
768 LowVpn
= ROUND_UP(LowestNode
->EndingVpn
+ 1, Alignment
);
769 if ((LowestNode
->EndingVpn
< BestVpn
) &&
770 (LowVpn
< Node
->StartingVpn
) &&
771 (Length
<= (Node
->StartingVpn
- LowVpn
)))
773 /* Check if we need to take BoundaryAddress into account */
774 if (BoundaryAddress
< Node
->StartingVpn
)
776 /* Return the optimal VPN address */
778 return STATUS_SUCCESS
;
782 /* The upper margin is given by the Node's starting address */
783 *Base
= ROUND_DOWN(Node
->StartingVpn
- Length
, Alignment
);
784 return STATUS_SUCCESS
;
788 /* Move to the next node */
792 /* Check if there's enough space before the lowest Vad */
793 if ((Node
->StartingVpn
> (ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
) &&
794 ((Node
->StartingVpn
- (ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
) >= Length
))
796 /* Check if it fits in perfectly */
797 if (BoundaryAddress
< Node
->StartingVpn
)
799 /* Return the optimal VPN address */
801 return STATUS_SUCCESS
;
804 /* Return an aligned base address within this node */
805 *Base
= ROUND_DOWN(Node
->StartingVpn
- Length
, Alignment
);
806 return STATUS_SUCCESS
;
809 /* No address space left at all */
810 return STATUS_NO_MEMORY
;
815 MiCheckSecuredVad(IN PMMVAD Vad
,
818 IN ULONG ProtectionMask
)
820 ULONG_PTR StartAddress
, EndAddress
;
822 /* Compute start and end address */
823 StartAddress
= (ULONG_PTR
)Base
;
824 EndAddress
= StartAddress
+ Size
- 1;
826 /* Are we deleting/unmapping, or changing? */
827 if (ProtectionMask
< MM_DELETE_CHECK
)
829 /* Changing... are we allowed to do so? */
830 if ((Vad
->u
.VadFlags
.NoChange
== 1) &&
831 (Vad
->u2
.VadFlags2
.SecNoChange
== 1) &&
832 (Vad
->u
.VadFlags
.Protection
!= ProtectionMask
))
835 DPRINT1("Trying to mess with a no-change VAD!\n");
836 return STATUS_INVALID_PAGE_PROTECTION
;
841 /* This is allowed */
845 /* ARM3 doesn't support this yet */
846 ASSERT(Vad
->u2
.VadFlags2
.MultipleSecured
== 0);
848 /* Is this a one-secured VAD, like a TEB or PEB? */
849 if (Vad
->u2
.VadFlags2
.OneSecured
)
851 /* Is this allocation being described by the VAD? */
852 if ((StartAddress
<= ((PMMVAD_LONG
)Vad
)->u3
.Secured
.EndVpn
) &&
853 (EndAddress
>= ((PMMVAD_LONG
)Vad
)->u3
.Secured
.StartVpn
))
856 if (ProtectionMask
& MM_DECOMMIT
)
858 DPRINT1("Not allowed to change protection on guard page!\n");
859 return STATUS_INVALID_PAGE_PROTECTION
;
862 /* ARM3 doesn't have read-only VADs yet */
863 ASSERT(Vad
->u2
.VadFlags2
.ReadOnly
== 0);
865 /* Check if read-write protections are allowed */
866 if (MmReadWrite
[ProtectionMask
] < MM_READ_WRITE_ALLOWED
)
868 DPRINT1("Invalid protection mask for RW access!\n");
869 return STATUS_INVALID_PAGE_PROTECTION
;
874 /* All good, allow the change */
875 return STATUS_SUCCESS
;