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 "../ARM3/miarm.h"
19 /* Include Mm version of AVL support */
20 #include "../ARM3/miavl.h"
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
)
82 PMMADDRESS_NODE CurrentNode
;
84 /* If the tree is empty, there is no conflict */
85 if (!Table
->NumberGenericTableElements
) return NULL
;
87 /* Start looping from the right */
88 CurrentNode
= RtlRightChildAvl(&Table
->BalancedRoot
);
89 ASSERT(CurrentNode
!= NULL
);
92 /* This address comes after */
93 if (StartVpn
> CurrentNode
->EndingVpn
)
95 /* Keep searching on the right */
96 CurrentNode
= RtlRightChildAvl(CurrentNode
);
98 else if (EndVpn
< CurrentNode
->StartingVpn
)
100 /* This address ends before the node starts, search on the left */
101 CurrentNode
= RtlLeftChildAvl(CurrentNode
);
105 /* This address is part of this node, return it */
110 /* Return either the conflicting node, or no node at all */
116 MiInsertNode(IN PMM_AVL_TABLE Table
,
117 IN PMMADDRESS_NODE NewNode
,
118 IN PMMADDRESS_NODE Parent
,
119 IN TABLE_SEARCH_RESULT Result
)
123 /* Insert it into the tree */
124 RtlpInsertAvlTreeNode(Table
, NewNode
, Parent
, Result
);
126 /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
127 Vad
= (PMMVAD_LONG
)NewNode
;
128 if (Vad
->u
.VadFlags
.Spare
== 0)
131 PMEMORY_AREA MemoryArea
;
133 PEPROCESS Process
= CONTAINING_RECORD(Table
, EPROCESS
, VadRoot
);
134 PVOID AllocatedBase
= (PVOID
)(Vad
->StartingVpn
<< PAGE_SHIFT
);
136 Size
= ((Vad
->EndingVpn
+ 1) - Vad
->StartingVpn
) << PAGE_SHIFT
;
137 Status
= MmCreateMemoryArea(&Process
->Vm
,
138 MEMORY_AREA_OWNED_BY_ARM3
,
146 ASSERT(NT_SUCCESS(Status
));
148 /* Check if this is VM VAD */
149 if (Vad
->ControlArea
== NULL
)
151 /* We store the reactos MEMORY_AREA here */
152 Vad
->FirstPrototypePte
= (PMMPTE
)MemoryArea
;
156 /* This is a section VAD. Store the MAREA here for now */
157 ASSERT(Vad
->u4
.Banked
== (PVOID
)0xDEADBABE);
158 Vad
->u4
.Banked
= (PVOID
)MemoryArea
;
165 MiInsertVad(IN PMMVAD Vad
,
166 IN PEPROCESS Process
)
168 TABLE_SEARCH_RESULT Result
;
169 PMMADDRESS_NODE Parent
= NULL
;
171 /* Validate the VAD and set it as the current hint */
172 ASSERT(Vad
->EndingVpn
>= Vad
->StartingVpn
);
173 Process
->VadRoot
.NodeHint
= Vad
;
175 /* Find the parent VAD and where this child should be inserted */
176 Result
= RtlpFindAvlTableNodeOrParent(&Process
->VadRoot
, (PVOID
)Vad
->StartingVpn
, &Parent
);
177 ASSERT(Result
!= TableFoundNode
);
178 ASSERT((Parent
!= NULL
) || (Result
== TableEmptyTree
));
180 /* Do the actual insert operation */
181 MiInsertNode(&Process
->VadRoot
, (PVOID
)Vad
, Parent
, Result
);
186 MiInsertBasedSection(IN PSECTION Section
)
188 TABLE_SEARCH_RESULT Result
;
189 PMMADDRESS_NODE Parent
= NULL
;
190 ASSERT(Section
->Address
.EndingVpn
>= Section
->Address
.StartingVpn
);
192 /* Find the parent VAD and where this child should be inserted */
193 Result
= RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot
, (PVOID
)Section
->Address
.StartingVpn
, &Parent
);
194 ASSERT(Result
!= TableFoundNode
);
195 ASSERT((Parent
!= NULL
) || (Result
== TableEmptyTree
));
196 MiInsertNode(&MmSectionBasedRoot
, &Section
->Address
, Parent
, Result
);
201 MiRemoveNode(IN PMMADDRESS_NODE Node
,
202 IN PMM_AVL_TABLE Table
)
206 /* Call the AVL code */
207 RtlpDeleteAvlTreeNode(Table
, Node
);
209 /* Decrease element count */
210 Table
->NumberGenericTableElements
--;
212 /* Check if this node was the hint */
213 if (Table
->NodeHint
== Node
)
215 /* Get a new hint, unless we're empty now, in which case nothing */
216 if (!Table
->NumberGenericTableElements
) Table
->NodeHint
= NULL
;
217 else Table
->NodeHint
= Table
->BalancedRoot
.RightChild
;
220 /* Free the node from ReactOS view as well */
221 Vad
= (PMMVAD_LONG
)Node
;
222 if (Vad
->u
.VadFlags
.Spare
== 0)
224 PMEMORY_AREA MemoryArea
;
227 /* Check if this is VM VAD */
228 if (Vad
->ControlArea
== NULL
)
230 /* We store the ReactOS MEMORY_AREA here */
231 MemoryArea
= (PMEMORY_AREA
)Vad
->FirstPrototypePte
;
235 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
236 MemoryArea
= (PMEMORY_AREA
)Vad
->u4
.Banked
;
239 /* Make sure one actually still exists */
242 /* Make sure we have not already freed it */
243 ASSERT(MemoryArea
!= (PVOID
)0xDEADBAB1);
245 /* Get the process */
246 Process
= CONTAINING_RECORD(Table
, EPROCESS
, VadRoot
);
248 /* We only create fake memory-areas for ARM3 VADs */
249 ASSERT(MemoryArea
->Type
== MEMORY_AREA_OWNED_BY_ARM3
);
250 ASSERT(MemoryArea
->Vad
== NULL
);
253 MmFreeMemoryArea(&Process
->Vm
, MemoryArea
, NULL
, NULL
);
255 /* Check if this is VM VAD */
256 if (Vad
->ControlArea
== NULL
)
258 /* Delete the pointer to it */
259 Vad
->FirstPrototypePte
= (PVOID
)0xDEADBAB1;
263 /* Delete the pointer to it */
264 Vad
->u4
.Banked
= (PVOID
)0xDEADBAB1;
272 MiGetPreviousNode(IN PMMADDRESS_NODE Node
)
274 PMMADDRESS_NODE Parent
;
276 /* Get the left child */
277 if (RtlLeftChildAvl(Node
))
279 /* Get right-most child */
280 Node
= RtlLeftChildAvl(Node
);
281 while (RtlRightChildAvl(Node
)) Node
= RtlRightChildAvl(Node
);
285 Parent
= RtlParentAvl(Node
);
286 ASSERT(Parent
!= NULL
);
287 while (Parent
!= Node
)
289 /* The parent should be a right child, return the real predecessor */
290 if (RtlIsRightChildAvl(Node
))
292 /* Return it unless it's the root */
293 if (Parent
== RtlParentAvl(Parent
)) Parent
= NULL
;
297 /* Keep lopping until we find our parent */
299 Parent
= RtlParentAvl(Node
);
308 MiGetNextNode(IN PMMADDRESS_NODE Node
)
310 PMMADDRESS_NODE Parent
;
312 /* Get the right child */
313 if (RtlRightChildAvl(Node
))
315 /* Get left-most child */
316 Node
= RtlRightChildAvl(Node
);
317 while (RtlLeftChildAvl(Node
)) Node
= RtlLeftChildAvl(Node
);
321 Parent
= RtlParentAvl(Node
);
322 ASSERT(Parent
!= NULL
);
323 while (Parent
!= Node
)
325 /* The parent should be a left child, return the real predecessor */
326 if (RtlIsLeftChildAvl(Node
))
332 /* Keep lopping until we find our parent */
334 Parent
= RtlParentAvl(Node
);
343 MiFindEmptyAddressRangeInTree(IN SIZE_T Length
,
344 IN ULONG_PTR Alignment
,
345 IN PMM_AVL_TABLE Table
,
346 OUT PMMADDRESS_NODE
*PreviousVad
,
349 PMMADDRESS_NODE Node
;
350 PMMADDRESS_NODE NextNode
;
351 ULONG_PTR StartingVpn
, HighestVpn
, AlignmentVpn
, LengthVpn
, LowVpn
;
354 /* Precompute page numbers for the length, alignment, and starting address */
355 LengthVpn
= (Length
+ (PAGE_SIZE
- 1)) >> PAGE_SHIFT
;
356 AlignmentVpn
= Alignment
>> PAGE_SHIFT
;
357 StartingVpn
= ROUND_UP((ULONG_PTR
)MM_LOWEST_USER_ADDRESS
>> PAGE_SHIFT
,
360 /* Check if the table is free, so the lowest possible address is available */
361 if (!Table
->NumberGenericTableElements
) goto FoundAtBottom
;
363 /* Otherwise, follow the leftmost child of the right root node's child */
364 Node
= RtlRightChildAvl(&Table
->BalancedRoot
);
365 while (RtlLeftChildAvl(Node
)) Node
= RtlLeftChildAvl(Node
);
367 /* This is the node for the remaining gap at the bottom, can it be used? */
368 if ((Node
->StartingVpn
> StartingVpn
) &&
369 (LengthVpn
< Node
->StartingVpn
- StartingVpn
))
372 /* Use this VAD to store the allocation */
374 *Base
= StartingVpn
<< PAGE_SHIFT
;
375 return STATUS_SUCCESS
;
378 /* Otherwise, we start a search to find a gap */
381 /* The last aligned page number in this entry */
382 LowVpn
= ROUND_UP(Node
->EndingVpn
+ 1, AlignmentVpn
);
384 /* Keep going as long as there's still a next node */
385 NextNode
= MiGetNextNode(Node
);
386 if (!NextNode
) break;
388 /* Can this allocation fit in this node? */
389 if ((LengthVpn
<= (NextNode
->StartingVpn
- LowVpn
)) &&
390 (NextNode
->StartingVpn
> LowVpn
))
393 /* Yes! Use this VAD to store the allocation */
395 *Base
= ROUND_UP((Node
->EndingVpn
<< PAGE_SHIFT
) | (PAGE_SIZE
- 1),
397 return STATUS_SUCCESS
;
400 /* Try the next node */
404 /* We're down to the last (top) VAD, will this allocation fit inside it? */
405 HighestVpn
= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1) >> PAGE_SHIFT
;
406 if ((HighestVpn
> LowVpn
) && (LengthVpn
<= HighestVpn
- LowVpn
)) goto Found
;
408 /* Nyet, there's no free address space for this allocation, so we'll fail */
409 return STATUS_NO_MEMORY
;
414 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length
,
415 IN ULONG_PTR BoundaryAddress
,
416 IN ULONG_PTR Alignment
,
417 IN PMM_AVL_TABLE Table
,
419 OUT PMMADDRESS_NODE
*Parent
)
421 PMMADDRESS_NODE Node
, LowestNode
, Child
;
422 ULONG_PTR LowVpn
, HighVpn
;
423 PFN_NUMBER PageCount
;
426 ASSERT(BoundaryAddress
);
427 ASSERT(BoundaryAddress
<= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1));
429 /* Compute page length, make sure the boundary address is valid */
430 Length
= ROUND_TO_PAGES(Length
);
431 PageCount
= Length
>> PAGE_SHIFT
;
432 if ((BoundaryAddress
+ 1) < Length
) return TableFoundNode
;
434 /* Check if the table is empty */
435 if (Table
->NumberGenericTableElements
== 0)
437 /* Tree is empty, the candidate address is already the best one */
438 *Base
= ROUND_UP(BoundaryAddress
+ 1 - Length
, Alignment
);
439 return TableEmptyTree
;
442 /* Calculate the initial upper margin */
443 HighVpn
= BoundaryAddress
>> PAGE_SHIFT
;
445 /* Starting from the root, go down until the right-most child
446 * which is just behind the boundary*/
447 LowestNode
= Node
= RtlRightChildAvl(&Table
->BalancedRoot
);
448 while (((Child
= RtlRightChildAvl(Node
)) != 0 )
449 && (Node
->EndingVpn
< HighVpn
)) Node
= Child
;
451 /* Now loop the Vad nodes */
454 /* Keep track of the lowest node */
457 /* Calculate the lower margin */
458 LowVpn
= ROUND_UP(Node
->EndingVpn
+ 1, Alignment
>> PAGE_SHIFT
);
460 /* Check if the current bounds are suitable */
461 if ((HighVpn
> LowVpn
) && ((HighVpn
- LowVpn
) >= PageCount
))
463 /* There is enough space to add our node */
464 LowVpn
= HighVpn
- PageCount
;
465 *Base
= LowVpn
<< PAGE_SHIFT
;
467 /* Can we use the current node as parent? */
468 Child
= RtlRightChildAvl(Node
);
471 /* Node has no right child, so use it as parent */
473 return TableInsertAsRight
;
477 /* Node has a right child, find most left grand child */
479 while ((Child
= RtlLeftChildAvl(Node
))) Node
= Child
;
481 return TableInsertAsLeft
;
485 /* Update the upper margin if neccessary */
486 if (Node
->StartingVpn
< HighVpn
) HighVpn
= Node
->StartingVpn
;
488 /* Go to the next lower node */
489 Node
= MiGetPreviousNode(Node
);
492 /* Check if there's enough space before the lowest Vad */
493 LowVpn
= ROUND_UP((ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
, Alignment
) >> PAGE_SHIFT
;
494 if ((HighVpn
> LowVpn
) && ((HighVpn
- LowVpn
) >= PageCount
))
496 /* There is enough space to add our address */
497 LowVpn
= HighVpn
- PageCount
;
498 *Base
= LowVpn
<< PAGE_SHIFT
;
499 *Parent
= LowestNode
;
500 return TableInsertAsLeft
;
503 /* No address space left at all */
506 return TableFoundNode
;
511 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length
,
512 IN ULONG_PTR BoundaryAddress
,
513 IN ULONG_PTR Alignment
,
514 IN PMM_AVL_TABLE Table
,
517 PMMADDRESS_NODE Node
, LowestNode
;
518 ULONG_PTR LowVpn
, BestVpn
;
521 ASSERT(Table
== &MmSectionBasedRoot
);
522 ASSERT(BoundaryAddress
);
523 ASSERT(BoundaryAddress
<= ((ULONG_PTR
)MM_HIGHEST_VAD_ADDRESS
+ 1));
525 /* Compute page length, make sure the boundary address is valid */
526 Length
= ROUND_TO_PAGES(Length
);
527 if ((BoundaryAddress
+ 1) < Length
) return STATUS_NO_MEMORY
;
529 /* Check if the table is empty */
530 BestVpn
= ROUND_UP(BoundaryAddress
+ 1 - Length
, Alignment
);
531 if (Table
->NumberGenericTableElements
== 0)
533 /* Tree is empty, the candidate address is already the best one */
535 return STATUS_SUCCESS
;
538 /* Go to the right-most node which should be the biggest address */
539 Node
= Table
->BalancedRoot
.RightChild
;
540 while (RtlRightChildAvl(Node
)) Node
= RtlRightChildAvl(Node
);
542 /* Check if we can fit in here */
543 LowVpn
= ROUND_UP(Node
->EndingVpn
, Alignment
);
544 if ((LowVpn
< BoundaryAddress
) && (Length
< (BoundaryAddress
- LowVpn
)))
546 /* Return the address */
547 *Base
= ROUND_UP(BoundaryAddress
- Length
, Alignment
);
548 return STATUS_SUCCESS
;
551 /* Now loop the Vad nodes */
554 /* Break out if we've reached the last node */
555 LowestNode
= MiGetPreviousNode(Node
);
556 if (!LowestNode
) break;
558 /* Check if this node could contain the requested address */
559 LowVpn
= ROUND_UP(LowestNode
->EndingVpn
+ 1, Alignment
);
560 if ((LowestNode
->EndingVpn
< BestVpn
) &&
561 (Length
<= (Node
->StartingVpn
- LowVpn
)))
563 /* Check if it fits in perfectly */
564 if ((BestVpn
> LowestNode
->EndingVpn
) &&
565 (BoundaryAddress
< Node
->StartingVpn
))
567 /* Return the optimal VPN address */
569 return STATUS_SUCCESS
;
572 /* It doesn't, check if it can partly fit */
573 if (Node
->StartingVpn
> LowVpn
)
575 /* Return an aligned base address within this node */
576 *Base
= ROUND_UP(Node
->StartingVpn
- Length
, Alignment
);
577 return STATUS_SUCCESS
;
581 /* Move to the next node */
585 /* Check if there's enough space before the lowest Vad */
586 if ((Node
->StartingVpn
> (ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
) &&
587 ((Node
->StartingVpn
- (ULONG_PTR
)MI_LOWEST_VAD_ADDRESS
) > Length
))
589 /* Check if it fits in perfectly */
590 if (BoundaryAddress
< Node
->StartingVpn
)
592 /* Return the optimal VPN address */
594 return STATUS_SUCCESS
;
597 /* Return an aligned base address within this node */
598 *Base
= ROUND_UP(Node
->StartingVpn
- Length
, Alignment
);
599 return STATUS_SUCCESS
;
602 /* No address space left at all */
603 return STATUS_NO_MEMORY
;
608 MiCheckSecuredVad(IN PMMVAD Vad
,
611 IN ULONG ProtectionMask
)
613 ULONG_PTR StartAddress
, EndAddress
;
615 /* Compute start and end address */
616 StartAddress
= (ULONG_PTR
)Base
;
617 EndAddress
= StartAddress
+ Size
- 1;
619 /* Are we deleting/unmapping, or changing? */
620 if (ProtectionMask
< MM_DELETE_CHECK
)
622 /* Changing... are we allowed to do so? */
623 if ((Vad
->u
.VadFlags
.NoChange
== 1) &&
624 (Vad
->u2
.VadFlags2
.SecNoChange
== 1) &&
625 (Vad
->u
.VadFlags
.Protection
!= ProtectionMask
))
628 DPRINT1("Trying to mess with a no-change VAD!\n");
629 return STATUS_INVALID_PAGE_PROTECTION
;
634 /* This is allowed */
638 /* ARM3 doesn't support this yet */
639 ASSERT(Vad
->u2
.VadFlags2
.MultipleSecured
== 0);
641 /* Is this a one-secured VAD, like a TEB or PEB? */
642 if (Vad
->u2
.VadFlags2
.OneSecured
)
644 /* Is this allocation being described by the VAD? */
645 if ((StartAddress
<= ((PMMVAD_LONG
)Vad
)->u3
.Secured
.EndVpn
) &&
646 (EndAddress
>= ((PMMVAD_LONG
)Vad
)->u3
.Secured
.StartVpn
))
649 if (ProtectionMask
& MM_DECOMMIT
)
651 DPRINT1("Not allowed to change protection on guard page!\n");
652 return STATUS_INVALID_PAGE_PROTECTION
;
655 /* ARM3 doesn't have read-only VADs yet */
656 ASSERT(Vad
->u2
.VadFlags2
.ReadOnly
== 0);
658 /* Check if read-write protections are allowed */
659 if (MmReadWrite
[ProtectionMask
] < MM_READ_WRITE_ALLOWED
)
661 DPRINT1("Invalid protection mask for RW access!\n");
662 return STATUS_INVALID_PAGE_PROTECTION
;
667 /* All good, allow the change */
668 return STATUS_SUCCESS
;