d62a02c8a73e429b947dd56c707489c93c43bb01
[reactos.git] / 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 * Timo Kreuzer (timo.kreuzer@reactos.org)
8 */
9
10 /* INCLUDES *******************************************************************/
11
12 #include <ntoskrnl.h>
13 #define NDEBUG
14 #include <debug.h>
15
16 #line 15 "ARMĀ³::VADNODE"
17 #define MODULE_INVOLVED_IN_ARM3
18 #include "../ARM3/miarm.h"
19
20 /* Include Mm version of AVL support */
21 #include "../ARM3/miavl.h"
22 #include "../../../lib/rtl/avlsupp.c"
23
24 /* FUNCTIONS ******************************************************************/
25
26 PMMVAD
27 NTAPI
28 MiLocateAddress(IN PVOID VirtualAddress)
29 {
30 PMMVAD FoundVad;
31 ULONG_PTR Vpn;
32 PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
33 TABLE_SEARCH_RESULT SearchResult;
34
35 /* Start with the the hint */
36 FoundVad = (PMMVAD)Table->NodeHint;
37 if (!FoundVad) return NULL;
38
39 /* Check if this VPN is in the hint, if so, use it */
40 Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
41 if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
42
43 /* VAD hint didn't work, go look for it */
44 SearchResult = RtlpFindAvlTableNodeOrParent(Table,
45 (PVOID)Vpn,
46 (PMMADDRESS_NODE*)&FoundVad);
47 if (SearchResult != TableFoundNode) return NULL;
48
49 /* We found it, update the hint */
50 ASSERT(FoundVad != NULL);
51 ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
52 Table->NodeHint = FoundVad;
53 return FoundVad;
54 }
55
56 PMMADDRESS_NODE
57 NTAPI
58 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
59 IN ULONG_PTR EndVpn,
60 IN PMM_AVL_TABLE Table)
61 {
62 PMMADDRESS_NODE CurrentNode;
63
64 /* If the tree is empty, there is no conflict */
65 if (!Table->NumberGenericTableElements) return NULL;
66
67 /* Start looping from the right */
68 CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
69 ASSERT(CurrentNode != NULL);
70 while (CurrentNode)
71 {
72 /* This address comes after */
73 if (StartVpn > CurrentNode->EndingVpn)
74 {
75 /* Keep searching on the right */
76 CurrentNode = RtlRightChildAvl(CurrentNode);
77 }
78 else if (EndVpn < CurrentNode->StartingVpn)
79 {
80 /* This address ends before the node starts, search on the left */
81 CurrentNode = RtlLeftChildAvl(CurrentNode);
82 }
83 else
84 {
85 /* This address is part of this node, return it */
86 break;
87 }
88 }
89
90 /* Return either the conflicting node, or no node at all */
91 return CurrentNode;
92 }
93
94 VOID
95 NTAPI
96 MiInsertNode(IN PMM_AVL_TABLE Table,
97 IN PMMADDRESS_NODE NewNode,
98 IN PMMADDRESS_NODE Parent,
99 IN TABLE_SEARCH_RESULT Result)
100 {
101 /* Insert it into the tree */
102 RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
103
104 /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
105 PMMVAD Vad = (PMMVAD)NewNode;
106 if (Vad->u.VadFlags.Spare == 0)
107 {
108 NTSTATUS Status;
109 PMEMORY_AREA MemoryArea;
110 PHYSICAL_ADDRESS BoundaryAddressMultiple;
111 SIZE_T Size;
112 PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
113 PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
114 BoundaryAddressMultiple.QuadPart = 0;
115 Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
116 Status = MmCreateMemoryArea(&Process->Vm,
117 MEMORY_AREA_OWNED_BY_ARM3,
118 &AllocatedBase,
119 Size,
120 PAGE_READWRITE,
121 &MemoryArea,
122 TRUE,
123 0,
124 BoundaryAddressMultiple);
125 ASSERT(NT_SUCCESS(Status));
126
127 /* Check if this is VM VAD */
128 if (Vad->ControlArea == NULL)
129 {
130 /* We store the reactos MEMORY_AREA here */
131 DPRINT("Storing %p in %p\n", MemoryArea, Vad);
132 Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
133 }
134 else
135 {
136 /* This is a section VAD. Store the MAREA here for now */
137 DPRINT("Storing %p in %p\n", MemoryArea, Vad);
138 Vad->ControlArea->WaitingForDeletion = (PVOID)MemoryArea;
139 }
140 }
141 }
142
143 VOID
144 NTAPI
145 MiInsertVad(IN PMMVAD Vad,
146 IN PEPROCESS Process)
147 {
148 TABLE_SEARCH_RESULT Result;
149 PMMADDRESS_NODE Parent = NULL;
150
151 /* Validate the VAD and set it as the current hint */
152 ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
153 Process->VadRoot.NodeHint = Vad;
154
155 /* Find the parent VAD and where this child should be inserted */
156 Result = RtlpFindAvlTableNodeOrParent(&Process->VadRoot, (PVOID)Vad->StartingVpn, &Parent);
157 ASSERT(Result != TableFoundNode);
158 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
159
160 /* Do the actual insert operation */
161 MiInsertNode(&Process->VadRoot, (PVOID)Vad, Parent, Result);
162 }
163
164 VOID
165 NTAPI
166 MiRemoveNode(IN PMMADDRESS_NODE Node,
167 IN PMM_AVL_TABLE Table)
168 {
169 /* Call the AVL code */
170 RtlpDeleteAvlTreeNode(Table, Node);
171
172 /* Decrease element count */
173 Table->NumberGenericTableElements--;
174
175 /* Check if this node was the hint */
176 if (Table->NodeHint == Node)
177 {
178 /* Get a new hint, unless we're empty now, in which case nothing */
179 if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
180 else Table->NodeHint = Table->BalancedRoot.RightChild;
181 }
182
183 /* Free the node from ReactOS view as well */
184 PMMVAD Vad = (PMMVAD)Node;
185 if (Vad->u.VadFlags.Spare == 0)
186 {
187 PMEMORY_AREA MemoryArea;
188 PEPROCESS Process;
189
190 /* Check if this is VM VAD */
191 if (Vad->ControlArea == NULL)
192 {
193 /* We store the ReactOS MEMORY_AREA here */
194 MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
195 }
196 else
197 {
198 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
199 MemoryArea = (PMEMORY_AREA)Vad->ControlArea->WaitingForDeletion;
200 }
201
202 /* Make sure one actually still exists */
203 if (MemoryArea)
204 {
205 /* Get the process */
206 Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
207
208 /* We only create fake memory-areas for ARM3 VADs */
209 ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
210 ASSERT(MemoryArea->Vad == NULL);
211
212 /* Free it */
213 MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
214 }
215 }
216 }
217
218 PMMADDRESS_NODE
219 NTAPI
220 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
221 {
222 PMMADDRESS_NODE Parent;
223
224 /* Get the left child */
225 if (RtlLeftChildAvl(Node))
226 {
227 /* Get right-most child */
228 Node = RtlLeftChildAvl(Node);
229 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
230 return Node;
231 }
232
233 Parent = RtlParentAvl(Node);
234 ASSERT(Parent != NULL);
235 while (Parent != Node)
236 {
237 /* The parent should be a right child, return the real predecessor */
238 if (RtlIsRightChildAvl(Node))
239 {
240 /* Return it unless it's the root */
241 if (Parent == RtlParentAvl(Parent)) Parent = NULL;
242 return Parent;
243 }
244
245 /* Keep lopping until we find our parent */
246 Node = Parent;
247 Parent = RtlParentAvl(Node);
248 }
249
250 /* Nothing found */
251 return NULL;
252 }
253
254 PMMADDRESS_NODE
255 NTAPI
256 MiGetNextNode(IN PMMADDRESS_NODE Node)
257 {
258 PMMADDRESS_NODE Parent;
259
260 /* Get the right child */
261 if (RtlRightChildAvl(Node))
262 {
263 /* Get left-most child */
264 Node = RtlRightChildAvl(Node);
265 while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
266 return Node;
267 }
268
269 Parent = RtlParentAvl(Node);
270 ASSERT(Parent != NULL);
271 while (Parent != Node)
272 {
273 /* The parent should be a left child, return the real predecessor */
274 if (RtlIsLeftChildAvl(Node))
275 {
276 /* Return it */
277 return Parent;
278 }
279
280 /* Keep lopping until we find our parent */
281 Node = Parent;
282 Parent = RtlParentAvl(Node);
283 }
284
285 /* Nothing found */
286 return NULL;
287 }
288
289 NTSTATUS
290 NTAPI
291 MiFindEmptyAddressRangeInTree(IN SIZE_T Length,
292 IN ULONG_PTR Alignment,
293 IN PMM_AVL_TABLE Table,
294 OUT PMMADDRESS_NODE *PreviousVad,
295 OUT PULONG_PTR Base)
296 {
297 PMMADDRESS_NODE Node;
298 PMMADDRESS_NODE NextNode;
299 ULONG_PTR StartingVpn, HighestVpn, AlignmentVpn, LengthVpn, LowVpn;
300 ASSERT(Length != 0);
301
302 /* Precompute page numbers for the length, alignment, and starting address */
303 LengthVpn = (Length + (PAGE_SIZE - 1)) >> PAGE_SHIFT;
304 AlignmentVpn = Alignment >> PAGE_SHIFT;
305 StartingVpn = ROUND_UP((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT,
306 AlignmentVpn);
307
308 /* Check if the table is free, so the lowest possible address is available */
309 if (!Table->NumberGenericTableElements) goto FoundAtBottom;
310
311 /* Otherwise, follow the leftmost child of the right root node's child */
312 Node = RtlRightChildAvl(&Table->BalancedRoot);
313 while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
314
315 /* This is the node for the remaining gap at the bottom, can it be used? */
316 if ((Node->StartingVpn > StartingVpn) &&
317 (LengthVpn < Node->StartingVpn - StartingVpn))
318 {
319 FoundAtBottom:
320 /* Use this VAD to store the allocation */
321 *PreviousVad = NULL;
322 *Base = StartingVpn << PAGE_SHIFT;
323 return STATUS_SUCCESS;
324 }
325
326 /* Otherwise, we start a search to find a gap */
327 while (TRUE)
328 {
329 /* The last aligned page number in this entry */
330 LowVpn = ROUND_UP(Node->EndingVpn + 1, AlignmentVpn);
331
332 /* Keep going as long as there's still a next node */
333 NextNode = MiGetNextNode(Node);
334 if (!NextNode) break;
335
336 /* Can this allocation fit in this node? */
337 if ((LengthVpn <= (NextNode->StartingVpn - LowVpn)) &&
338 (NextNode->StartingVpn > LowVpn))
339 {
340 Found:
341 /* Yes! Use this VAD to store the allocation */
342 *PreviousVad = Node;
343 *Base = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
344 Alignment);
345 return STATUS_SUCCESS;
346 }
347
348 /* Try the next node */
349 Node = NextNode;
350 }
351
352 /* We're down to the last (top) VAD, will this allocation fit inside it? */
353 HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) >> PAGE_SHIFT;
354 if ((HighestVpn > LowVpn) && (LengthVpn <= HighestVpn - LowVpn)) goto Found;
355
356 /* Nyet, there's no free address space for this allocation, so we'll fail */
357 return STATUS_NO_MEMORY;
358 }
359
360 TABLE_SEARCH_RESULT
361 NTAPI
362 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
363 IN ULONG_PTR BoundaryAddress,
364 IN ULONG_PTR Alignment,
365 IN PMM_AVL_TABLE Table,
366 OUT PULONG_PTR Base,
367 OUT PMMADDRESS_NODE *Parent)
368 {
369 PMMADDRESS_NODE Node, LowestNode, Child;
370 ULONG LowVpn, HighVpn;
371 PFN_NUMBER PageCount;
372
373 /* Sanity checks */
374 ASSERT(BoundaryAddress);
375 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
376
377 /* Compute page length, make sure the boundary address is valid */
378 Length = ROUND_TO_PAGES(Length);
379 PageCount = Length >> PAGE_SHIFT;
380 if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
381
382 /* Check if the table is empty */
383 if (Table->NumberGenericTableElements == 0)
384 {
385 /* Tree is empty, the candidate address is already the best one */
386 *Base = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
387 return TableEmptyTree;
388 }
389
390 /* Calculate the initial upper margin */
391 HighVpn = BoundaryAddress >> PAGE_SHIFT;
392
393 /* Starting from the root, go down until the right-most child,
394 trying to stay below the boundary. */
395 LowestNode = Node = RtlRightChildAvl(&Table->BalancedRoot);
396 while ( (Child = RtlRightChildAvl(Node)) &&
397 Child->EndingVpn < HighVpn ) Node = Child;
398
399 /* Now loop the Vad nodes */
400 while (Node)
401 {
402 /* Keep track of the lowest node */
403 LowestNode = Node;
404
405 /* Calculate the lower margin */
406 LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment >> PAGE_SHIFT);
407
408 /* Check if the current bounds are suitable */
409 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
410 {
411 /* There is enough space to add our node */
412 LowVpn = HighVpn - PageCount;
413 *Base = LowVpn << PAGE_SHIFT;
414
415 /* Can we use the current node as parent? */
416 Child = RtlRightChildAvl(Node);
417 if (!Child)
418 {
419 /* Node has no right child, so use it as parent */
420 *Parent = Node;
421 return TableInsertAsRight;
422 }
423 else
424 {
425 /* Node has a right child, find most left grand child */
426 Node = Child;
427 while ((Child = RtlLeftChildAvl(Node))) Node = Child;
428 *Parent = Node;
429 return TableInsertAsLeft;
430 }
431 }
432
433 /* Update the upper margin if neccessary */
434 if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
435
436 /* Go to the next lower node */
437 Node = MiGetPreviousNode(Node);
438 }
439
440 /* Check if there's enough space before the lowest Vad */
441 LowVpn = ROUND_UP((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) >> PAGE_SHIFT;
442 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
443 {
444 /* There is enough space to add our address */
445 LowVpn = HighVpn - PageCount;
446 *Base = LowVpn << PAGE_SHIFT;
447 *Parent = LowestNode;
448 return TableInsertAsLeft;
449 }
450
451 /* No address space left at all */
452 *Base = 0;
453 *Parent = NULL;
454 return TableFoundNode;
455 }
456
457 /* EOF */