[NTOS][USERSRV] Silence noisy debug output.
[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 #define MODULE_INVOLVED_IN_ARM3
17 #include <mm/ARM3/miarm.h>
18
19 /* Include Mm version of AVL support */
20 #include "miavl.h"
21 #include <sdk/lib/rtl/avlsupp.c>
22
23 /* GLOBALS ********************************************************************/
24
25 CHAR MmReadWrite[32] =
26 {
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,
30
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,
34
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,
38
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,
42 };
43
44 /* FUNCTIONS ******************************************************************/
45
46 PMMVAD
47 NTAPI
48 MiLocateAddress(IN PVOID VirtualAddress)
49 {
50 PMMVAD FoundVad;
51 ULONG_PTR Vpn;
52 PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
53 TABLE_SEARCH_RESULT SearchResult;
54
55 /* Start with the the hint */
56 FoundVad = (PMMVAD)Table->NodeHint;
57 if (!FoundVad) return NULL;
58
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;
62
63 /* VAD hint didn't work, go look for it */
64 SearchResult = RtlpFindAvlTableNodeOrParent(Table,
65 (PVOID)Vpn,
66 (PMMADDRESS_NODE*)&FoundVad);
67 if (SearchResult != TableFoundNode) return NULL;
68
69 /* We found it, update the hint */
70 ASSERT(FoundVad != NULL);
71 ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
72 Table->NodeHint = FoundVad;
73 return FoundVad;
74 }
75
76 TABLE_SEARCH_RESULT
77 NTAPI
78 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
79 IN ULONG_PTR EndVpn,
80 IN PMM_AVL_TABLE Table,
81 OUT PMMADDRESS_NODE *NodeOrParent)
82 {
83 PMMADDRESS_NODE ParentNode, CurrentNode;
84
85 /* If the tree is empty, there is no conflict */
86 if (Table->NumberGenericTableElements == 0) return TableEmptyTree;
87
88 /* Start looping from the root node */
89 CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
90 ASSERT(CurrentNode != NULL);
91 while (CurrentNode)
92 {
93 ParentNode = CurrentNode;
94
95 /* This address comes after */
96 if (StartVpn > CurrentNode->EndingVpn)
97 {
98 /* Keep searching on the right */
99 CurrentNode = RtlRightChildAvl(CurrentNode);
100 }
101 else if (EndVpn < CurrentNode->StartingVpn)
102 {
103 /* This address ends before the node starts, search on the left */
104 CurrentNode = RtlLeftChildAvl(CurrentNode);
105 }
106 else
107 {
108 /* This address is part of this node, return it */
109 *NodeOrParent = ParentNode;
110 return TableFoundNode;
111 }
112 }
113
114 /* There is no more child, save the current node as parent */
115 *NodeOrParent = ParentNode;
116 if (StartVpn > ParentNode->EndingVpn)
117 {
118 return TableInsertAsRight;
119 }
120 else
121 {
122 return TableInsertAsLeft;
123 }
124 }
125
126 VOID
127 NTAPI
128 MiInsertNode(IN PMM_AVL_TABLE Table,
129 IN PMMADDRESS_NODE NewNode,
130 IN PMMADDRESS_NODE Parent,
131 IN TABLE_SEARCH_RESULT Result)
132 {
133 PMMVAD_LONG Vad;
134
135 /* Insert it into the tree */
136 RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
137
138 /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
139 Vad = (PMMVAD_LONG)NewNode;
140 if (Vad->u.VadFlags.Spare == 0)
141 {
142 NTSTATUS Status;
143 PMEMORY_AREA MemoryArea;
144 SIZE_T Size;
145 PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
146 PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
147
148 Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
149
150 if (AllocatedBase == NULL)
151 {
152 AllocatedBase = (PVOID)(ULONG_PTR)1;
153 Size -= 1;
154 }
155
156 Status = MmCreateMemoryArea(&Process->Vm,
157 MEMORY_AREA_OWNED_BY_ARM3,
158 &AllocatedBase,
159 Size,
160 PAGE_READWRITE,
161 &MemoryArea,
162 0,
163 PAGE_SIZE);
164 ASSERT(NT_SUCCESS(Status));
165
166 /* Check if this is VM VAD */
167 if (Vad->ControlArea == NULL)
168 {
169 /* We store the reactos MEMORY_AREA here */
170 Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
171 }
172 else
173 {
174 /* This is a section VAD. Store the MAREA here for now */
175 ASSERT(Vad->u4.Banked == (PVOID)(ULONG_PTR)0xDEADBABEDEADBABEULL);
176 Vad->u4.Banked = (PVOID)MemoryArea;
177 }
178 }
179 }
180
181 VOID
182 NTAPI
183 MiInsertVad(IN PMMVAD Vad,
184 IN PMM_AVL_TABLE VadRoot)
185 {
186 TABLE_SEARCH_RESULT Result;
187 PMMADDRESS_NODE Parent = NULL;
188
189 /* Validate the VAD and set it as the current hint */
190 ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
191 VadRoot->NodeHint = Vad;
192
193 /* Find the parent VAD and where this child should be inserted */
194 Result = RtlpFindAvlTableNodeOrParent(VadRoot, (PVOID)Vad->StartingVpn, &Parent);
195 ASSERT(Result != TableFoundNode);
196 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
197
198 /* Do the actual insert operation */
199 MiInsertNode(VadRoot, (PVOID)Vad, Parent, Result);
200 }
201
202 NTSTATUS
203 NTAPI
204 MiInsertVadEx(
205 _Inout_ PMMVAD Vad,
206 _In_ ULONG_PTR *BaseAddress,
207 _In_ SIZE_T ViewSize,
208 _In_ ULONG_PTR HighestAddress,
209 _In_ ULONG_PTR Alignment,
210 _In_ ULONG AllocationType)
211 {
212 ULONG_PTR StartingAddress, EndingAddress;
213 PEPROCESS CurrentProcess;
214 PETHREAD CurrentThread;
215 TABLE_SEARCH_RESULT Result;
216 PMMADDRESS_NODE Parent;
217
218 /* Align the view size to pages */
219 ViewSize = ALIGN_UP_BY(ViewSize, PAGE_SIZE);
220
221 /* Get the current process */
222 CurrentProcess = PsGetCurrentProcess();
223
224 /* Acquire the address creation lock and make sure the process is alive */
225 KeAcquireGuardedMutex(&CurrentProcess->AddressCreationLock);
226 if (CurrentProcess->VmDeleted)
227 {
228 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
229 DPRINT1("The process is dying\n");
230 return STATUS_PROCESS_IS_TERMINATING;
231 }
232
233 /* Did the caller specify an address? */
234 if (*BaseAddress == 0)
235 {
236 /* Make sure HighestAddress is not too large */
237 HighestAddress = min(HighestAddress, (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS);
238
239 /* Which way should we search? */
240 if ((AllocationType & MEM_TOP_DOWN) || CurrentProcess->VmTopDown)
241 {
242 /* Find an address top-down */
243 Result = MiFindEmptyAddressRangeDownTree(ViewSize,
244 HighestAddress,
245 Alignment,
246 &CurrentProcess->VadRoot,
247 &StartingAddress,
248 &Parent);
249 }
250 else
251 {
252 /* Find an address bottom-up */
253 Result = MiFindEmptyAddressRangeInTree(ViewSize,
254 Alignment,
255 &CurrentProcess->VadRoot,
256 &Parent,
257 &StartingAddress);
258 }
259
260 /* Get the ending address, which is the last piece we need for the VAD */
261 EndingAddress = StartingAddress + ViewSize - 1;
262
263 /* Check if we found a suitable location */
264 if ((Result == TableFoundNode) || (EndingAddress > HighestAddress))
265 {
266 DPRINT1("Not enough free space to insert this VAD node!\n");
267 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
268 return STATUS_NO_MEMORY;
269 }
270
271 ASSERT(StartingAddress != 0);
272 ASSERT(StartingAddress < (ULONG_PTR)HighestAddress);
273 ASSERT(EndingAddress > StartingAddress);
274 }
275 else
276 {
277 /* Calculate the starting and ending address */
278 StartingAddress = ALIGN_DOWN_BY(*BaseAddress, Alignment);
279 EndingAddress = StartingAddress + ViewSize - 1;
280
281 /* Make sure it doesn't conflict with an existing allocation */
282 Result = MiCheckForConflictingNode(StartingAddress >> PAGE_SHIFT,
283 EndingAddress >> PAGE_SHIFT,
284 &CurrentProcess->VadRoot,
285 &Parent);
286 if (Result == TableFoundNode)
287 {
288 DPRINT("Given address conflicts with existing node\n");
289 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
290 return STATUS_CONFLICTING_ADDRESSES;
291 }
292 }
293
294 /* Now set the VAD address */
295 Vad->StartingVpn = StartingAddress >> PAGE_SHIFT;
296 Vad->EndingVpn = EndingAddress >> PAGE_SHIFT;
297
298 /* Check if we already need to charge for the pages */
299 if ((Vad->u.VadFlags.PrivateMemory && Vad->u.VadFlags.MemCommit) ||
300 (!Vad->u.VadFlags.PrivateMemory &&
301 (Vad->u.VadFlags.Protection & PAGE_WRITECOPY)))
302 {
303 /* Set the commit charge */
304 Vad->u.VadFlags.CommitCharge = ViewSize / PAGE_SIZE;
305 }
306
307 /* Check if the VAD is to be secured */
308 if (Vad->u2.VadFlags2.OneSecured)
309 {
310 /* This *must* be a long VAD! */
311 ASSERT(Vad->u2.VadFlags2.LongVad);
312
313 /* Yeah this is retarded, I didn't invent it! */
314 ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn = StartingAddress;
315 ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn = EndingAddress;
316 }
317
318 /* Lock the working set */
319 CurrentThread = PsGetCurrentThread();
320 MiLockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
321
322 /* Insert the VAD */
323 CurrentProcess->VadRoot.NodeHint = Vad;
324 MiInsertNode(&CurrentProcess->VadRoot, (PVOID)Vad, Parent, Result);
325
326 /* Release the working set */
327 MiUnlockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
328
329 /* Update the process' virtual size, and peak virtual size */
330 CurrentProcess->VirtualSize += ViewSize;
331 if (CurrentProcess->VirtualSize > CurrentProcess->PeakVirtualSize)
332 {
333 CurrentProcess->PeakVirtualSize = CurrentProcess->VirtualSize;
334 }
335
336 /* Unlock the address space */
337 KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
338
339 *BaseAddress = StartingAddress;
340 return STATUS_SUCCESS;
341 }
342
343 VOID
344 NTAPI
345 MiInsertBasedSection(IN PSECTION Section)
346 {
347 TABLE_SEARCH_RESULT Result;
348 PMMADDRESS_NODE Parent = NULL;
349 ASSERT(Section->Address.EndingVpn >= Section->Address.StartingVpn);
350
351 /* Find the parent VAD and where this child should be inserted */
352 Result = RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot, (PVOID)Section->Address.StartingVpn, &Parent);
353 ASSERT(Result != TableFoundNode);
354 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
355 MiInsertNode(&MmSectionBasedRoot, &Section->Address, Parent, Result);
356 }
357
358 VOID
359 NTAPI
360 MiRemoveNode(IN PMMADDRESS_NODE Node,
361 IN PMM_AVL_TABLE Table)
362 {
363 PMMVAD_LONG Vad;
364
365 /* Call the AVL code */
366 RtlpDeleteAvlTreeNode(Table, Node);
367
368 /* Decrease element count */
369 Table->NumberGenericTableElements--;
370
371 /* Check if this node was the hint */
372 if (Table->NodeHint == Node)
373 {
374 /* Get a new hint, unless we're empty now, in which case nothing */
375 if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
376 else Table->NodeHint = Table->BalancedRoot.RightChild;
377 }
378
379 /* Free the node from ReactOS view as well */
380 Vad = (PMMVAD_LONG)Node;
381 if ((Table != &MmSectionBasedRoot) && (Vad->u.VadFlags.Spare == 0))
382 {
383 PMEMORY_AREA MemoryArea;
384 PEPROCESS Process;
385
386 /* Check if this is VM VAD */
387 if (Vad->ControlArea == NULL)
388 {
389 /* We store the ReactOS MEMORY_AREA here */
390 MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
391 }
392 else
393 {
394 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
395 MemoryArea = (PMEMORY_AREA)Vad->u4.Banked;
396 }
397
398 /* Make sure one actually still exists */
399 if (MemoryArea)
400 {
401 /* Make sure we have not already freed it */
402 ASSERT(MemoryArea != (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL);
403
404 /* Get the process */
405 Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
406
407 /* We only create fake memory-areas for ARM3 VADs */
408 ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
409 ASSERT(MemoryArea->Vad == NULL);
410
411 /* Free it */
412 MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
413
414 /* Check if this is VM VAD */
415 if (Vad->ControlArea == NULL)
416 {
417 /* Delete the pointer to it */
418 Vad->FirstPrototypePte = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL;
419 }
420 else
421 {
422 /* Delete the pointer to it */
423 Vad->u4.Banked = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL;
424 }
425 }
426 }
427 }
428
429 PMMADDRESS_NODE
430 NTAPI
431 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
432 {
433 PMMADDRESS_NODE Parent;
434
435 /* Get the left child */
436 if (RtlLeftChildAvl(Node))
437 {
438 /* Get right-most child */
439 Node = RtlLeftChildAvl(Node);
440 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
441 return Node;
442 }
443
444 Parent = RtlParentAvl(Node);
445 ASSERT(Parent != NULL);
446 while (Parent != Node)
447 {
448 /* The parent should be a right child, return the real predecessor */
449 if (RtlIsRightChildAvl(Node))
450 {
451 /* Return it unless it's the root */
452 if (Parent == RtlParentAvl(Parent)) Parent = NULL;
453 return Parent;
454 }
455
456 /* Keep lopping until we find our parent */
457 Node = Parent;
458 Parent = RtlParentAvl(Node);
459 }
460
461 /* Nothing found */
462 return NULL;
463 }
464
465 PMMADDRESS_NODE
466 NTAPI
467 MiGetNextNode(IN PMMADDRESS_NODE Node)
468 {
469 PMMADDRESS_NODE Parent;
470
471 /* Get the right child */
472 if (RtlRightChildAvl(Node))
473 {
474 /* Get left-most child */
475 Node = RtlRightChildAvl(Node);
476 while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
477 return Node;
478 }
479
480 Parent = RtlParentAvl(Node);
481 ASSERT(Parent != NULL);
482 while (Parent != Node)
483 {
484 /* The parent should be a left child, return the real predecessor */
485 if (RtlIsLeftChildAvl(Node))
486 {
487 /* Return it */
488 return Parent;
489 }
490
491 /* Keep lopping until we find our parent */
492 Node = Parent;
493 Parent = RtlParentAvl(Node);
494 }
495
496 /* Nothing found */
497 return NULL;
498 }
499
500 TABLE_SEARCH_RESULT
501 NTAPI
502 MiFindEmptyAddressRangeInTree(IN SIZE_T Length,
503 IN ULONG_PTR Alignment,
504 IN PMM_AVL_TABLE Table,
505 OUT PMMADDRESS_NODE *PreviousVad,
506 OUT PULONG_PTR Base)
507 {
508 PMMADDRESS_NODE Node, PreviousNode;
509 ULONG_PTR PageCount, AlignmentVpn, LowVpn, HighestVpn;
510 ASSERT(Length != 0);
511
512 /* Calculate page numbers for the length, alignment, and starting address */
513 PageCount = BYTES_TO_PAGES(Length);
514 AlignmentVpn = Alignment >> PAGE_SHIFT;
515 LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT, AlignmentVpn);
516
517 /* Check for kernel mode table (memory areas) */
518 if (Table->Unused == 1)
519 {
520 LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
521 }
522
523 /* Check if the table is empty */
524 if (Table->NumberGenericTableElements == 0)
525 {
526 /* Tree is empty, the candidate address is already the best one */
527 *Base = LowVpn << PAGE_SHIFT;
528 return TableEmptyTree;
529 }
530
531 /* Otherwise, follow the leftmost child of the right root node's child */
532 Node = RtlRightChildAvl(&Table->BalancedRoot);
533 while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
534
535 /* Start a search to find a gap */
536 PreviousNode = NULL;
537 while (Node != NULL)
538 {
539 /* Check if the gap below the current node is suitable */
540 if (Node->StartingVpn >= LowVpn + PageCount)
541 {
542 /* There is enough space to add our node */
543 *Base = LowVpn << PAGE_SHIFT;
544
545 /* Can we use the current node as parent? */
546 if (RtlLeftChildAvl(Node) == NULL)
547 {
548 /* Node has no left child, so use it as parent */
549 *PreviousVad = Node;
550 return TableInsertAsLeft;
551 }
552 else
553 {
554 /* Node has a left child, this means that the previous node is
555 the right-most child of it's left child and can be used as
556 the parent. In case we use the space before the left-most
557 node, it's left child must be NULL. */
558 ASSERT(PreviousNode != NULL);
559 ASSERT(RtlRightChildAvl(PreviousNode) == NULL);
560 *PreviousVad = PreviousNode;
561 return TableInsertAsRight;
562 }
563 }
564
565 /* The next candidate is above the current node */
566 if (Node->EndingVpn >= LowVpn)
567 LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
568
569 /* Remember the current node and go to the next node */
570 PreviousNode = Node;
571 Node = MiGetNextNode(Node);
572 }
573
574 /* We're up to the highest VAD, will this allocation fit above it? */
575 HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) / PAGE_SIZE;
576
577 /* Check for kernel mode table (memory areas) */
578 if (Table->Unused == 1)
579 {
580 HighestVpn = ALIGN_UP_BY((ULONG_PTR)(LONG_PTR)-1 >> PAGE_SHIFT, AlignmentVpn);
581 }
582
583 if (HighestVpn >= LowVpn + PageCount)
584 {
585 /* Yes! Use this VAD to store the allocation */
586 *PreviousVad = PreviousNode;
587 *Base = LowVpn << PAGE_SHIFT;
588 return TableInsertAsRight;
589 }
590
591 /* Nyet, there's no free address space for this allocation, so we'll fail */
592 return TableFoundNode;
593 }
594
595 TABLE_SEARCH_RESULT
596 NTAPI
597 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
598 IN ULONG_PTR BoundaryAddress,
599 IN ULONG_PTR Alignment,
600 IN PMM_AVL_TABLE Table,
601 OUT PULONG_PTR Base,
602 OUT PMMADDRESS_NODE *Parent)
603 {
604 PMMADDRESS_NODE Node, OldNode = NULL, Child;
605 ULONG_PTR LowVpn, HighVpn, AlignmentVpn;
606 PFN_NUMBER PageCount;
607
608 /* Sanity checks */
609 ASSERT(BoundaryAddress);
610 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS));
611 ASSERT((Alignment & (PAGE_SIZE - 1)) == 0);
612
613 /* Calculate page numbers for the length and alignment */
614 Length = ROUND_TO_PAGES(Length);
615 PageCount = Length >> PAGE_SHIFT;
616 AlignmentVpn = Alignment / PAGE_SIZE;
617
618 /* Check for kernel mode table (memory areas) */
619 if (Table->Unused == 1)
620 {
621 LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
622 }
623 else
624 {
625 LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS, Alignment);
626 }
627
628 /* Check if there is enough space below the boundary */
629 if ((LowVpn + Length) > (BoundaryAddress + 1))
630 {
631 return TableFoundNode;
632 }
633
634 /* Check if the table is empty */
635 if (Table->NumberGenericTableElements == 0)
636 {
637 /* Tree is empty, the candidate address is already the best one */
638 *Base = ALIGN_DOWN_BY(BoundaryAddress + 1 - Length, Alignment);
639 return TableEmptyTree;
640 }
641
642 /* Calculate the initial upper margin */
643 HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT;
644
645 /* Starting from the root, follow the right children until we found a node
646 that ends above the boundary */
647 Node = RtlRightChildAvl(&Table->BalancedRoot);
648 while ((Node->EndingVpn < HighVpn) &&
649 ((Child = RtlRightChildAvl(Node)) != NULL)) Node = Child;
650
651 /* Now loop the Vad nodes */
652 while (Node)
653 {
654 /* Calculate the lower margin */
655 LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
656
657 /* Check if the current bounds are suitable */
658 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
659 {
660 /* There is enough space to add our node */
661 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, AlignmentVpn);
662 *Base = LowVpn << PAGE_SHIFT;
663
664 /* Can we use the current node as parent? */
665 if (!RtlRightChildAvl(Node))
666 {
667 /* Node has no right child, so use it as parent */
668 *Parent = Node;
669 return TableInsertAsRight;
670 }
671 else
672 {
673 /* Node has a right child. This means we must have already
674 moved one node left from the right-most node we started
675 with, thus we already have an OldNode! */
676 ASSERT(OldNode != NULL);
677
678 /* The node we had before is the most left grandchild of
679 that right child, use it as parent. */
680 ASSERT(RtlLeftChildAvl(OldNode) == NULL);
681 *Parent = OldNode;
682 return TableInsertAsLeft;
683 }
684 }
685
686 /* Update the upper margin if necessary */
687 if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
688
689 /* Remember the current node and go to the previous node */
690 OldNode = Node;
691 Node = MiGetPreviousNode(Node);
692 }
693
694 /* Check if there's enough space before the lowest Vad */
695 LowVpn = ALIGN_UP_BY((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) / PAGE_SIZE;
696 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
697 {
698 /* There is enough space to add our address */
699 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT);
700 *Base = LowVpn << PAGE_SHIFT;
701 *Parent = OldNode;
702 return TableInsertAsLeft;
703 }
704
705 /* No address space left at all */
706 *Base = 0;
707 *Parent = NULL;
708 return TableFoundNode;
709 }
710
711 NTSTATUS
712 NTAPI
713 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length,
714 IN ULONG_PTR BoundaryAddress,
715 IN ULONG_PTR Alignment,
716 IN PMM_AVL_TABLE Table,
717 OUT PULONG_PTR Base)
718 {
719 PMMADDRESS_NODE Node, LowestNode;
720 ULONG_PTR LowVpn, BestVpn;
721
722 /* Sanity checks */
723 ASSERT(Table == &MmSectionBasedRoot);
724 ASSERT(BoundaryAddress);
725 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
726
727 /* Compute page length, make sure the boundary address is valid */
728 Length = ROUND_TO_PAGES(Length);
729 if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
730
731 /* Check if the table is empty */
732 BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
733 if (Table->NumberGenericTableElements == 0)
734 {
735 /* Tree is empty, the candidate address is already the best one */
736 *Base = BestVpn;
737 return STATUS_SUCCESS;
738 }
739
740 /* Go to the right-most node which should be the biggest address */
741 Node = Table->BalancedRoot.RightChild;
742 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
743
744 /* Check if we can fit in here */
745 LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment);
746 if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn)))
747 {
748 #if (NTDDI_VERSION >= NTDDI_VISTA)
749 /* Return the address. */
750 *Base = BestVpn;
751 #else
752 /* Note: this is a compatibility hack that mimics a bug in the 2k3
753 kernel. It will can waste up to Alignment bytes of memory above
754 the allocation. This bug was fixed in Windows Vista */
755 *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment);
756 #endif
757 return STATUS_SUCCESS;
758 }
759
760 /* Now loop the Vad nodes */
761 do
762 {
763 /* Break out if we've reached the last node */
764 LowestNode = MiGetPreviousNode(Node);
765 if (!LowestNode) break;
766
767 /* Check if this node could contain the requested address */
768 LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment);
769 if ((LowestNode->EndingVpn < BestVpn) &&
770 (LowVpn < Node->StartingVpn) &&
771 (Length <= (Node->StartingVpn - LowVpn)))
772 {
773 /* Check if we need to take BoundaryAddress into account */
774 if (BoundaryAddress < Node->StartingVpn)
775 {
776 /* Return the optimal VPN address */
777 *Base = BestVpn;
778 return STATUS_SUCCESS;
779 }
780 else
781 {
782 /* The upper margin is given by the Node's starting address */
783 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
784 return STATUS_SUCCESS;
785 }
786 }
787
788 /* Move to the next node */
789 Node = LowestNode;
790 } while (TRUE);
791
792 /* Check if there's enough space before the lowest Vad */
793 if ((Node->StartingVpn > (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) &&
794 ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length))
795 {
796 /* Check if it fits in perfectly */
797 if (BoundaryAddress < Node->StartingVpn)
798 {
799 /* Return the optimal VPN address */
800 *Base = BestVpn;
801 return STATUS_SUCCESS;
802 }
803
804 /* Return an aligned base address within this node */
805 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
806 return STATUS_SUCCESS;
807 }
808
809 /* No address space left at all */
810 return STATUS_NO_MEMORY;
811 }
812
813 NTSTATUS
814 NTAPI
815 MiCheckSecuredVad(IN PMMVAD Vad,
816 IN PVOID Base,
817 IN SIZE_T Size,
818 IN ULONG ProtectionMask)
819 {
820 ULONG_PTR StartAddress, EndAddress;
821
822 /* Compute start and end address */
823 StartAddress = (ULONG_PTR)Base;
824 EndAddress = StartAddress + Size - 1;
825
826 /* Are we deleting/unmapping, or changing? */
827 if (ProtectionMask < MM_DELETE_CHECK)
828 {
829 /* Changing... are we allowed to do so? */
830 if ((Vad->u.VadFlags.NoChange == 1) &&
831 (Vad->u2.VadFlags2.SecNoChange == 1) &&
832 (Vad->u.VadFlags.Protection != ProtectionMask))
833 {
834 /* Nope, bail out */
835 DPRINT1("Trying to mess with a no-change VAD!\n");
836 return STATUS_INVALID_PAGE_PROTECTION;
837 }
838 }
839 else
840 {
841 /* This is allowed */
842 ProtectionMask = 0;
843 }
844
845 /* ARM3 doesn't support this yet */
846 ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0);
847
848 /* Is this a one-secured VAD, like a TEB or PEB? */
849 if (Vad->u2.VadFlags2.OneSecured)
850 {
851 /* Is this allocation being described by the VAD? */
852 if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) &&
853 (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn))
854 {
855 /* Guard page? */
856 if (ProtectionMask & MM_DECOMMIT)
857 {
858 DPRINT1("Not allowed to change protection on guard page!\n");
859 return STATUS_INVALID_PAGE_PROTECTION;
860 }
861
862 /* ARM3 doesn't have read-only VADs yet */
863 ASSERT(Vad->u2.VadFlags2.ReadOnly == 0);
864
865 /* Check if read-write protections are allowed */
866 if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED)
867 {
868 DPRINT1("Invalid protection mask for RW access!\n");
869 return STATUS_INVALID_PAGE_PROTECTION;
870 }
871 }
872 }
873
874 /* All good, allow the change */
875 return STATUS_SUCCESS;
876 }
877
878 /* EOF */
879