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