[NTOS]: Implement MmDeleteTeb, VADs are now deleted/freed on thread exit as well...
[reactos.git] / reactos / ntoskrnl / mm / ARM3 / vadnode.c
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 */
8
9 /* INCLUDES *******************************************************************/
10
11 #include <ntoskrnl.h>
12 #define NDEBUG
13 #include <debug.h>
14
15 #line 15 "ARMĀ³::VADNODE"
16 #define MODULE_INVOLVED_IN_ARM3
17 #include "../ARM3/miarm.h"
18
19 /* Include Mm version of AVL support */
20 #include "../ARM3/miavl.h"
21 #include "../../../lib/rtl/avlsupp.c"
22
23 /* FUNCTIONS ******************************************************************/
24
25 PMMVAD
26 NTAPI
27 MiLocateAddress(IN PVOID VirtualAddress)
28 {
29 PMMVAD FoundVad;
30 ULONG_PTR Vpn;
31 PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
32 TABLE_SEARCH_RESULT SearchResult;
33
34 /* Start with the the hint */
35 FoundVad = (PMMVAD)Table->NodeHint;
36 if (!FoundVad) return NULL;
37
38 /* Check if this VPN is in the hint, if so, use it */
39 Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
40 if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
41
42 /* VAD hint didn't work, go look for it */
43 SearchResult = RtlpFindAvlTableNodeOrParent(Table,
44 (PVOID)Vpn,
45 (PMMADDRESS_NODE*)&FoundVad);
46 if (SearchResult != TableFoundNode) return NULL;
47
48 /* We found it, update the hint */
49 ASSERT(FoundVad != NULL);
50 ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
51 Table->NodeHint = FoundVad;
52 return FoundVad;
53 }
54
55 PMMADDRESS_NODE
56 NTAPI
57 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
58 IN ULONG_PTR EndVpn,
59 IN PMM_AVL_TABLE Table)
60 {
61 PMMADDRESS_NODE CurrentNode;
62
63 /* If the tree is empty, there is no conflict */
64 if (!Table->NumberGenericTableElements) return NULL;
65
66 /* Start looping from the right */
67 CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
68 ASSERT(CurrentNode != NULL);
69 while (CurrentNode)
70 {
71 /* This address comes after */
72 if (StartVpn > CurrentNode->EndingVpn)
73 {
74 /* Keep searching on the right */
75 CurrentNode = RtlRightChildAvl(CurrentNode);
76 }
77 else if (EndVpn < CurrentNode->StartingVpn)
78 {
79 /* This address ends before the node starts, search on the left */
80 CurrentNode = RtlLeftChildAvl(CurrentNode);
81 }
82 else
83 {
84 /* This address is part of this node, return it */
85 break;
86 }
87 }
88
89 /* Return either the conflicting node, or no node at all */
90 return CurrentNode;
91 }
92
93 VOID
94 NTAPI
95 MiInsertNode(IN PMMADDRESS_NODE NewNode,
96 IN PMM_AVL_TABLE Table)
97 {
98 PMMADDRESS_NODE NodeOrParent = NULL;
99 TABLE_SEARCH_RESULT Result;
100
101 /* Find the node's parent, and where to insert this node */
102 Result = RtlpFindAvlTableNodeOrParent(Table,
103 (PVOID)NewNode->StartingVpn,
104 &NodeOrParent);
105
106 /* Insert it into the tree */
107 RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
108 }
109
110 VOID
111 NTAPI
112 MiRemoveNode(IN PMMADDRESS_NODE Node,
113 IN PMM_AVL_TABLE Table)
114 {
115 /* Call the AVL code */
116 RtlpDeleteAvlTreeNode(Table, Node);
117
118 /* Decrease element count */
119 Table->NumberGenericTableElements--;
120 }
121
122 PMMADDRESS_NODE
123 NTAPI
124 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
125 {
126 PMMADDRESS_NODE Parent;
127
128 /* Get the left child */
129 if (RtlLeftChildAvl(Node))
130 {
131 /* Get right-most child */
132 Node = RtlLeftChildAvl(Node);
133 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
134 return Node;
135 }
136
137 Parent = RtlParentAvl(Node);
138 ASSERT(Parent != NULL);
139 while (Parent != Node)
140 {
141 /* The parent should be a right child, return the real predecessor */
142 if (RtlIsRightChildAvl(Node))
143 {
144 /* Return it unless it's the root */
145 if (Parent == RtlParentAvl(Parent)) Parent = NULL;
146 return Parent;
147 }
148
149 /* Keep lopping until we find our parent */
150 Node = Parent;
151 Parent = RtlParentAvl(Node);
152 }
153
154 /* Nothing found */
155 return NULL;
156 }
157
158 NTSTATUS
159 NTAPI
160 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
161 IN ULONG_PTR BoundaryAddress,
162 IN ULONG_PTR Alignment,
163 IN PMM_AVL_TABLE Table,
164 OUT PULONG_PTR Base)
165 {
166 PMMADDRESS_NODE Node, PreviousNode;
167 ULONG_PTR CandidateAddress, EndAddress;
168 ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
169 PFN_NUMBER PageCount;
170
171 /* Sanity checks */
172 ASSERT(BoundaryAddress);
173 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
174
175 /* Compute page length, make sure the boundary address is valid */
176 Length = PAGE_ROUND_UP(Length);
177 if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
178
179 /* Compute the highest address to start at */
180 CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
181
182 /* Check if the table is empty */
183 if (!Table->NumberGenericTableElements)
184 {
185 /* Tree is empty, the candidate address is already the best one */
186 *Base = CandidateAddress;
187 return STATUS_SUCCESS;
188 }
189
190 /* Starting from the root, go down until the right-most child */
191 Node = RtlRightChildAvl(&Table->BalancedRoot);
192 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
193
194 /* Get the aligned ending address of this VPN */
195 EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
196 Alignment);
197
198 /* Can we fit the address without overflowing into the node? */
199 if ((EndAddress < BoundaryAddress) &&
200 ((BoundaryAddress - EndAddress) > Length))
201 {
202 /* There is enough space to add our address */
203 *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
204 return STATUS_SUCCESS;
205 }
206
207 PageCount = Length >> PAGE_SHIFT;
208 CandidateVpn = CandidateAddress >> PAGE_SHIFT;
209 BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
210 LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
211
212 PreviousNode = MiGetPreviousNode(Node);
213
214 StartVpn = Node->StartingVpn;
215 EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
216 AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
217
218 /* Loop until a gap is found */
219 for (PageCount = Length >> PAGE_SHIFT,
220 CandidateVpn = CandidateAddress >> PAGE_SHIFT,
221 BoundaryVpn = BoundaryAddress >> PAGE_SHIFT,
222 LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT,
223 PreviousNode = MiGetPreviousNode(Node),
224 StartVpn = Node->StartingVpn,
225 EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
226 AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
227 PreviousNode;
228 Node = PreviousNode,
229 PreviousNode = MiGetPreviousNode(Node),
230 StartVpn = Node->StartingVpn,
231 EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
232 AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
233 {
234 /* Can we fit the address without overflowing into the node? */
235 if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
236 {
237 /* Check if we can get our candidate address */
238 if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
239 {
240 /* Use it */
241 *Base = CandidateAddress;
242 return STATUS_SUCCESS;
243 }
244
245 /* Otherwise, can we fit it by changing the start address? */
246 if (StartVpn > AlignEndVpn)
247 {
248 /* It'll fit, compute the new base address for that to work */
249 *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
250 return STATUS_SUCCESS;
251 }
252 }
253
254 PreviousNode = MiGetPreviousNode(Node);
255 StartVpn = Node->StartingVpn;
256 EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
257 AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
258 }
259
260 /* See if we could squeeze into the last descriptor */
261 if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
262 {
263 /* Check if we can try our candidate address */
264 if (BoundaryVpn < StartVpn)
265 {
266 /* Use it */
267 *Base = CandidateAddress;
268 return STATUS_SUCCESS;
269 }
270
271 /* Otherwise, change the base address to what's needed to fit in */
272 *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
273 return STATUS_SUCCESS;
274 }
275
276 /* No address space left at all */
277 return STATUS_NO_MEMORY;
278 }
279
280 /* EOF */