* FILE: ntoskrnl/mm/ARM3/vadnode.c
* PURPOSE: ARM Memory Manager VAD Node Algorithms
* PROGRAMMERS: ReactOS Portable Systems Group
+ * Timo Kreuzer (timo.kreuzer@reactos.org)
*/
/* INCLUDES *******************************************************************/
VOID
NTAPI
-MiInsertNode(IN PMMADDRESS_NODE NewNode,
- IN PMM_AVL_TABLE Table)
+MiInsertNode(IN PMM_AVL_TABLE Table,
+ IN PMMADDRESS_NODE NewNode,
+ IN PMMADDRESS_NODE Parent,
+ IN TABLE_SEARCH_RESULT Result)
{
- PMMADDRESS_NODE NodeOrParent = NULL;
- TABLE_SEARCH_RESULT Result;
+ PMMVAD Vad;
- /* Find the node's parent, and where to insert this node */
- Result = RtlpFindAvlTableNodeOrParent(Table,
- (PVOID)NewNode->StartingVpn,
- &NodeOrParent);
-
/* Insert it into the tree */
- RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
+ RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
+
+ /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
+ Vad = (PMMVAD)NewNode;
+ if (Vad->u.VadFlags.Spare == 0)
+ {
+ NTSTATUS Status;
+ PMEMORY_AREA MemoryArea;
+ PHYSICAL_ADDRESS BoundaryAddressMultiple;
+ SIZE_T Size;
+ PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
+ PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
+ BoundaryAddressMultiple.QuadPart = 0;
+ Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
+ Status = MmCreateMemoryArea(&Process->Vm,
+ MEMORY_AREA_OWNED_BY_ARM3,
+ &AllocatedBase,
+ Size,
+ PAGE_READWRITE,
+ &MemoryArea,
+ TRUE,
+ 0,
+ BoundaryAddressMultiple);
+ ASSERT(NT_SUCCESS(Status));
+
+ /* Check if this is VM VAD */
+ if (Vad->ControlArea == NULL)
+ {
+ /* We store the reactos MEMORY_AREA here */
+ DPRINT("Storing %p in %p\n", MemoryArea, Vad);
+ Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
+ }
+ else
+ {
+ /* This is a section VAD. Store the MAREA here for now */
+ DPRINT("Storing %p in %p\n", MemoryArea, Vad);
+ Vad->ControlArea->WaitingForDeletion = (PVOID)MemoryArea;
+ }
+ }
+}
+
+VOID
+NTAPI
+MiInsertVad(IN PMMVAD Vad,
+ IN PEPROCESS Process)
+{
+ TABLE_SEARCH_RESULT Result;
+ PMMADDRESS_NODE Parent = NULL;
+
+ /* Validate the VAD and set it as the current hint */
+ ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
+ Process->VadRoot.NodeHint = Vad;
+
+ /* Find the parent VAD and where this child should be inserted */
+ Result = RtlpFindAvlTableNodeOrParent(&Process->VadRoot, (PVOID)Vad->StartingVpn, &Parent);
+ ASSERT(Result != TableFoundNode);
+ ASSERT((Parent != NULL) || (Result == TableEmptyTree));
+
+ /* Do the actual insert operation */
+ MiInsertNode(&Process->VadRoot, (PVOID)Vad, Parent, Result);
}
VOID
MiRemoveNode(IN PMMADDRESS_NODE Node,
IN PMM_AVL_TABLE Table)
{
+ PMMVAD Vad;
+
/* Call the AVL code */
RtlpDeleteAvlTreeNode(Table, Node);
/* Decrease element count */
Table->NumberGenericTableElements--;
+
+ /* Check if this node was the hint */
+ if (Table->NodeHint == Node)
+ {
+ /* Get a new hint, unless we're empty now, in which case nothing */
+ if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
+ else Table->NodeHint = Table->BalancedRoot.RightChild;
+ }
+
+ /* Free the node from ReactOS view as well */
+ Vad = (PMMVAD)Node;
+ if (Vad->u.VadFlags.Spare == 0)
+ {
+ PMEMORY_AREA MemoryArea;
+ PEPROCESS Process;
+
+ /* Check if this is VM VAD */
+ if (Vad->ControlArea == NULL)
+ {
+ /* We store the ReactOS MEMORY_AREA here */
+ MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
+ }
+ else
+ {
+ /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
+ MemoryArea = (PMEMORY_AREA)Vad->ControlArea->WaitingForDeletion;
+ }
+
+ /* Make sure one actually still exists */
+ if (MemoryArea)
+ {
+ /* Get the process */
+ Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
+
+ /* We only create fake memory-areas for ARM3 VADs */
+ ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
+ ASSERT(MemoryArea->Vad == NULL);
+
+ /* Free it */
+ MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
+ }
+ }
}
PMMADDRESS_NODE
return NULL;
}
+PMMADDRESS_NODE
+NTAPI
+MiGetNextNode(IN PMMADDRESS_NODE Node)
+{
+ PMMADDRESS_NODE Parent;
+
+ /* Get the right child */
+ if (RtlRightChildAvl(Node))
+ {
+ /* Get left-most child */
+ Node = RtlRightChildAvl(Node);
+ while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
+ return Node;
+ }
+
+ Parent = RtlParentAvl(Node);
+ ASSERT(Parent != NULL);
+ while (Parent != Node)
+ {
+ /* The parent should be a left child, return the real predecessor */
+ if (RtlIsLeftChildAvl(Node))
+ {
+ /* Return it */
+ return Parent;
+ }
+
+ /* Keep lopping until we find our parent */
+ Node = Parent;
+ Parent = RtlParentAvl(Node);
+ }
+
+ /* Nothing found */
+ return NULL;
+}
+
NTSTATUS
NTAPI
+MiFindEmptyAddressRangeInTree(IN SIZE_T Length,
+ IN ULONG_PTR Alignment,
+ IN PMM_AVL_TABLE Table,
+ OUT PMMADDRESS_NODE *PreviousVad,
+ OUT PULONG_PTR Base)
+{
+ PMMADDRESS_NODE Node;
+ PMMADDRESS_NODE NextNode;
+ ULONG_PTR StartingVpn, HighestVpn, AlignmentVpn, LengthVpn, LowVpn;
+ ASSERT(Length != 0);
+
+ /* Precompute page numbers for the length, alignment, and starting address */
+ LengthVpn = (Length + (PAGE_SIZE - 1)) >> PAGE_SHIFT;
+ AlignmentVpn = Alignment >> PAGE_SHIFT;
+ StartingVpn = ROUND_UP((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT,
+ AlignmentVpn);
+
+ /* Check if the table is free, so the lowest possible address is available */
+ if (!Table->NumberGenericTableElements) goto FoundAtBottom;
+
+ /* Otherwise, follow the leftmost child of the right root node's child */
+ Node = RtlRightChildAvl(&Table->BalancedRoot);
+ while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
+
+ /* This is the node for the remaining gap at the bottom, can it be used? */
+ if ((Node->StartingVpn > StartingVpn) &&
+ (LengthVpn < Node->StartingVpn - StartingVpn))
+ {
+FoundAtBottom:
+ /* Use this VAD to store the allocation */
+ *PreviousVad = NULL;
+ *Base = StartingVpn << PAGE_SHIFT;
+ return STATUS_SUCCESS;
+ }
+
+ /* Otherwise, we start a search to find a gap */
+ while (TRUE)
+ {
+ /* The last aligned page number in this entry */
+ LowVpn = ROUND_UP(Node->EndingVpn + 1, AlignmentVpn);
+
+ /* Keep going as long as there's still a next node */
+ NextNode = MiGetNextNode(Node);
+ if (!NextNode) break;
+
+ /* Can this allocation fit in this node? */
+ if ((LengthVpn <= (NextNode->StartingVpn - LowVpn)) &&
+ (NextNode->StartingVpn > LowVpn))
+ {
+Found:
+ /* Yes! Use this VAD to store the allocation */
+ *PreviousVad = Node;
+ *Base = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
+ Alignment);
+ return STATUS_SUCCESS;
+ }
+
+ /* Try the next node */
+ Node = NextNode;
+ }
+
+ /* We're down to the last (top) VAD, will this allocation fit inside it? */
+ HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) >> PAGE_SHIFT;
+ if ((HighestVpn > LowVpn) && (LengthVpn <= HighestVpn - LowVpn)) goto Found;
+
+ /* Nyet, there's no free address space for this allocation, so we'll fail */
+ return STATUS_NO_MEMORY;
+}
+
+TABLE_SEARCH_RESULT
+NTAPI
MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
IN ULONG_PTR BoundaryAddress,
IN ULONG_PTR Alignment,
IN PMM_AVL_TABLE Table,
- OUT PULONG_PTR Base)
+ OUT PULONG_PTR Base,
+ OUT PMMADDRESS_NODE *Parent)
{
- PMMADDRESS_NODE Node, PreviousNode;
- ULONG_PTR CandidateAddress, EndAddress;
- ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
+ PMMADDRESS_NODE Node, LowestNode, Child;
+ ULONG LowVpn, HighVpn;
PFN_NUMBER PageCount;
/* Sanity checks */
ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
/* Compute page length, make sure the boundary address is valid */
- Length = PAGE_ROUND_UP(Length);
+ Length = ROUND_TO_PAGES(Length);
+ PageCount = Length >> PAGE_SHIFT;
if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
-
- /* Compute the highest address to start at */
- CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
/* Check if the table is empty */
- if (!Table->NumberGenericTableElements)
+ if (Table->NumberGenericTableElements == 0)
{
/* Tree is empty, the candidate address is already the best one */
- *Base = CandidateAddress;
- return STATUS_SUCCESS;
+ *Base = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
+ return TableEmptyTree;
}
- /* Starting from the root, go down until the right-most child */
- Node = RtlRightChildAvl(&Table->BalancedRoot);
- while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
+ /* Calculate the initial upper margin */
+ HighVpn = BoundaryAddress >> PAGE_SHIFT;
- /* Get the aligned ending address of this VPN */
- EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
- Alignment);
+ /* Starting from the root, go down until the right-most child,
+ trying to stay below the boundary. */
+ LowestNode = Node = RtlRightChildAvl(&Table->BalancedRoot);
+ while ( (Child = RtlRightChildAvl(Node)) &&
+ Child->EndingVpn < HighVpn ) Node = Child;
- /* Can we fit the address without overflowing into the node? */
- if ((EndAddress < BoundaryAddress) &&
- ((BoundaryAddress - EndAddress) > Length))
- {
- /* There is enough space to add our address */
- *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
- return STATUS_SUCCESS;
- }
-
- PageCount = Length >> PAGE_SHIFT;
- CandidateVpn = CandidateAddress >> PAGE_SHIFT;
- BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
- LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
-
- PreviousNode = MiGetPreviousNode(Node);
-
- StartVpn = Node->StartingVpn;
- EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
- AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
-
- /* Loop until a gap is found */
- for (PageCount = Length >> PAGE_SHIFT,
- CandidateVpn = CandidateAddress >> PAGE_SHIFT,
- BoundaryVpn = BoundaryAddress >> PAGE_SHIFT,
- LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT,
- PreviousNode = MiGetPreviousNode(Node),
- StartVpn = Node->StartingVpn,
- EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
- AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
- PreviousNode;
- Node = PreviousNode,
- PreviousNode = MiGetPreviousNode(Node),
- StartVpn = Node->StartingVpn,
- EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
- AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
+ /* Now loop the Vad nodes */
+ while (Node)
{
- /* Can we fit the address without overflowing into the node? */
- if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
+ /* Keep track of the lowest node */
+ LowestNode = Node;
+
+ /* Calculate the lower margin */
+ LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment >> PAGE_SHIFT);
+
+ /* Check if the current bounds are suitable */
+ if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
{
- /* Check if we can get our candidate address */
- if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
+ /* There is enough space to add our node */
+ LowVpn = HighVpn - PageCount;
+ *Base = LowVpn << PAGE_SHIFT;
+
+ /* Can we use the current node as parent? */
+ Child = RtlRightChildAvl(Node);
+ if (!Child)
{
- /* Use it */
- *Base = CandidateAddress;
- return STATUS_SUCCESS;
+ /* Node has no right child, so use it as parent */
+ *Parent = Node;
+ return TableInsertAsRight;
}
-
- /* Otherwise, can we fit it by changing the start address? */
- if (StartVpn > AlignEndVpn)
+ else
{
- /* It'll fit, compute the new base address for that to work */
- *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
- return STATUS_SUCCESS;
+ /* Node has a right child, find most left grand child */
+ Node = Child;
+ while ((Child = RtlLeftChildAvl(Node))) Node = Child;
+ *Parent = Node;
+ return TableInsertAsLeft;
}
}
-
- PreviousNode = MiGetPreviousNode(Node);
- StartVpn = Node->StartingVpn;
- EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
- AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+
+ /* Update the upper margin if neccessary */
+ if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
+
+ /* Go to the next lower node */
+ Node = MiGetPreviousNode(Node);
}
- /* See if we could squeeze into the last descriptor */
- if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
+ /* Check if there's enough space before the lowest Vad */
+ LowVpn = ROUND_UP((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) >> PAGE_SHIFT;
+ if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
{
- /* Check if we can try our candidate address */
- if (BoundaryVpn < StartVpn)
- {
- /* Use it */
- *Base = CandidateAddress;
- return STATUS_SUCCESS;
- }
-
- /* Otherwise, change the base address to what's needed to fit in */
- *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
- return STATUS_SUCCESS;
+ /* There is enough space to add our address */
+ LowVpn = HighVpn - PageCount;
+ *Base = LowVpn << PAGE_SHIFT;
+ *Parent = LowestNode;
+ return TableInsertAsLeft;
}
-
+
/* No address space left at all */
- return STATUS_NO_MEMORY;
+ *Base = 0;
+ *Parent = NULL;
+ return TableFoundNode;
}
/* EOF */
projects / reactos.git / blobdiff