ReactOS 0.4.15-dev-8227-g32d615f
vadnode.c File Reference
#include <ntoskrnl.h>
#include <debug.h>
#include <mm/ARM3/miarm.h>
#include "miavl.h"
#include <sdk/lib/rtl/avlsupp.c>
Include dependency graph for vadnode.c:

Go to the source code of this file.

Macros

#define NDEBUG
 
#define MODULE_INVOLVED_IN_ARM3
 
#define ASSERT_LOCKED_FOR_READ(Table)
 
#define ASSERT_LOCKED_FOR_WRITE(Table)
 

Functions

PMMVAD NTAPI MiLocateAddress (IN PVOID VirtualAddress)
 
TABLE_SEARCH_RESULT NTAPI MiCheckForConflictingNode (IN ULONG_PTR StartVpn, IN ULONG_PTR EndVpn, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *NodeOrParent)
 
VOID NTAPI MiInsertNode (IN PMM_AVL_TABLE Table, IN PMMADDRESS_NODE NewNode, IN PMMADDRESS_NODE Parent, IN TABLE_SEARCH_RESULT Result)
 
VOID NTAPI MiInsertVad (IN PMMVAD Vad, IN PMM_AVL_TABLE VadRoot)
 
NTSTATUS NTAPI MiInsertVadEx (_Inout_ PMMVAD Vad, _In_ ULONG_PTR *BaseAddress, _In_ SIZE_T ViewSize, _In_ ULONG_PTR HighestAddress, _In_ ULONG_PTR Alignment, _In_ ULONG AllocationType)
 
VOID NTAPI MiInsertBasedSection (IN PSECTION Section)
 
VOID NTAPI MiRemoveNode (IN PMMADDRESS_NODE Node, IN PMM_AVL_TABLE Table)
 
PMMADDRESS_NODE NTAPI MiGetPreviousNode (IN PMMADDRESS_NODE Node)
 
PMMADDRESS_NODE NTAPI MiGetNextNode (IN PMMADDRESS_NODE Node)
 
TABLE_SEARCH_RESULT NTAPI MiFindEmptyAddressRangeInTree (IN SIZE_T Length, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *PreviousVad, OUT PULONG_PTR Base)
 
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 PMMADDRESS_NODE *Parent)
 
NTSTATUS NTAPI MiFindEmptyAddressRangeDownBasedTree (IN SIZE_T Length, IN ULONG_PTR BoundaryAddress, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PULONG_PTR Base)
 
NTSTATUS NTAPI MiCheckSecuredVad (IN PMMVAD Vad, IN PVOID Base, IN SIZE_T Size, IN ULONG ProtectionMask)
 

Variables

CHAR MmReadWrite [32]
 
MM_AVL_TABLE MiRosKernelVadRoot
 

Macro Definition Documentation

◆ ASSERT_LOCKED_FOR_READ

#define ASSERT_LOCKED_FOR_READ (   Table)

Definition at line 109 of file vadnode.c.

◆ ASSERT_LOCKED_FOR_WRITE

#define ASSERT_LOCKED_FOR_WRITE (   Table)

Definition at line 110 of file vadnode.c.

◆ MODULE_INVOLVED_IN_ARM3

#define MODULE_INVOLVED_IN_ARM3

Definition at line 16 of file vadnode.c.

◆ NDEBUG

#define NDEBUG

Definition at line 13 of file vadnode.c.

Function Documentation

◆ MiCheckForConflictingNode()

TABLE_SEARCH_RESULT NTAPI MiCheckForConflictingNode ( IN ULONG_PTR  StartVpn,
IN ULONG_PTR  EndVpn,
IN PMM_AVL_TABLE  Table,
OUT PMMADDRESS_NODE NodeOrParent 
)

Definition at line 150 of file vadnode.c.

154{
155 PMMADDRESS_NODE ParentNode, CurrentNode;
156
158
159 /* If the tree is empty, there is no conflict */
160 if (Table->NumberGenericTableElements == 0) return TableEmptyTree;
161
162 /* Start looping from the root node */
163 CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
164 ASSERT(CurrentNode != NULL);
165 while (CurrentNode)
166 {
167 ParentNode = CurrentNode;
168
169 /* This address comes after */
170 if (StartVpn > CurrentNode->EndingVpn)
171 {
172 /* Keep searching on the right */
173 CurrentNode = RtlRightChildAvl(CurrentNode);
174 }
175 else if (EndVpn < CurrentNode->StartingVpn)
176 {
177 /* This address ends before the node starts, search on the left */
178 CurrentNode = RtlLeftChildAvl(CurrentNode);
179 }
180 else
181 {
182 /* This address is part of this node, return it */
183 *NodeOrParent = ParentNode;
184 return TableFoundNode;
185 }
186 }
187
188 /* There is no more child, save the current node as parent */
189 *NodeOrParent = ParentNode;
190 if (StartVpn > ParentNode->EndingVpn)
191 {
192 return TableInsertAsRight;
193 }
194 else
195 {
196 return TableInsertAsLeft;
197 }
198}
#define NULL
Definition: types.h:112
ASMGENDATA Table[]
Definition: genincdata.c:61
#define RtlRightChildAvl
Definition: miavl.h:45
#define RtlLeftChildAvl
Definition: miavl.h:46
#define ASSERT(a)
Definition: mode.c:44
ULONG_PTR EndingVpn
Definition: mmtypes.h:654
#define ASSERT_LOCKED_FOR_READ(Table)
Definition: vadnode.c:109

Referenced by MiInsertVadEx(), MiMapLockedPagesInUserSpace(), MiProtectVirtualMemory(), MmLocateMemoryAreaByAddress(), MmLocateMemoryAreaByRegion(), and NtAllocateVirtualMemory().

◆ MiCheckSecuredVad()

NTSTATUS NTAPI MiCheckSecuredVad ( IN PMMVAD  Vad,
IN PVOID  Base,
IN SIZE_T  Size,
IN ULONG  ProtectionMask 
)

Definition at line 903 of file vadnode.c.

907{
908 ULONG_PTR StartAddress, EndAddress;
909
910 /* Compute start and end address */
911 StartAddress = (ULONG_PTR)Base;
912 EndAddress = StartAddress + Size - 1;
913
914 /* Are we deleting/unmapping, or changing? */
915 if (ProtectionMask < MM_DELETE_CHECK)
916 {
917 /* Changing... are we allowed to do so? */
918 if ((Vad->u.VadFlags.NoChange == 1) &&
919 (Vad->u2.VadFlags2.SecNoChange == 1) &&
920 (Vad->u.VadFlags.Protection != ProtectionMask))
921 {
922 /* Nope, bail out */
923 DPRINT1("Trying to mess with a no-change VAD!\n");
925 }
926 }
927 else
928 {
929 /* This is allowed */
930 ProtectionMask = 0;
931 }
932
933 /* ARM3 doesn't support this yet */
934 ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0);
935
936 /* Is this a one-secured VAD, like a TEB or PEB? */
937 if (Vad->u2.VadFlags2.OneSecured)
938 {
939 /* Is this allocation being described by the VAD? */
940 if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) &&
941 (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn))
942 {
943 /* Guard page? */
944 if (ProtectionMask & MM_DECOMMIT)
945 {
946 DPRINT1("Not allowed to change protection on guard page!\n");
948 }
949
950 /* ARM3 doesn't have read-only VADs yet */
951 ASSERT(Vad->u2.VadFlags2.ReadOnly == 0);
952
953 /* Check if read-write protections are allowed */
954 if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED)
955 {
956 DPRINT1("Invalid protection mask for RW access!\n");
958 }
959 }
960 }
961
962 /* All good, allow the change */
963 return STATUS_SUCCESS;
964}
#define DPRINT1
Definition: precomp.h:8
#define ULONG_PTR
Definition: config.h:101
#define MM_READ_WRITE_ALLOWED
Definition: miarm.h:253
#define MM_DELETE_CHECK
Definition: miarm.h:256
#define MM_DECOMMIT
Definition: miarm.h:64
static BYTE u3[]
Definition: msg.c:580
_In_opt_ ULONG Base
Definition: rtlfuncs.h:2439
#define STATUS_INVALID_PAGE_PROTECTION
Definition: ntstatus.h:305
#define STATUS_SUCCESS
Definition: shellext.h:65
ULONG ReadOnly
Definition: mmtypes.h:710
MMVAD_FLAGS2 VadFlags2
Definition: mmtypes.h:771
union _MMVAD_LONG::@2626 u2
uint32_t ULONG_PTR
Definition: typedefs.h:65
CHAR MmReadWrite[32]
Definition: vadnode.c:25
_Must_inspect_result_ _In_ WDFDEVICE _In_ PWDF_DEVICE_PROPERTY_DATA _In_ DEVPROPTYPE _In_ ULONG Size
Definition: wdfdevice.h:4533

Referenced by MiUnmapViewOfSection(), and NtAllocateVirtualMemory().

◆ MiFindEmptyAddressRangeDownBasedTree()

NTSTATUS NTAPI MiFindEmptyAddressRangeDownBasedTree ( IN SIZE_T  Length,
IN ULONG_PTR  BoundaryAddress,
IN ULONG_PTR  Alignment,
IN PMM_AVL_TABLE  Table,
OUT PULONG_PTR  Base 
)

Definition at line 799 of file vadnode.c.

804{
805 PMMADDRESS_NODE Node, LowestNode;
806 ULONG_PTR LowVpn, BestVpn;
807
809
810 /* Sanity checks */
812 ASSERT(BoundaryAddress);
813 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
814
815 /* Compute page length, make sure the boundary address is valid */
817 if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
818
819 /* Check if the table is empty */
820 BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
821 if (Table->NumberGenericTableElements == 0)
822 {
823 /* Tree is empty, the candidate address is already the best one */
824 *Base = BestVpn;
825 return STATUS_SUCCESS;
826 }
827
828 /* Go to the right-most node which should be the biggest address */
829 Node = Table->BalancedRoot.RightChild;
831
832 /* Check if we can fit in here */
833 LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment);
834 if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn)))
835 {
836#if (NTDDI_VERSION >= NTDDI_VISTA)
837 /* Return the address. */
838 *Base = BestVpn;
839#else
840 /* Note: this is a compatibility hack that mimics a bug in the 2k3
841 kernel. It will can waste up to Alignment bytes of memory above
842 the allocation. This bug was fixed in Windows Vista */
843 *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment);
844#endif
845 return STATUS_SUCCESS;
846 }
847
848 /* Now loop the Vad nodes */
849 do
850 {
851 /* Break out if we've reached the last node */
852 LowestNode = MiGetPreviousNode(Node);
853 if (!LowestNode) break;
854
855 /* Check if this node could contain the requested address */
856 LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment);
857 if ((LowestNode->EndingVpn < BestVpn) &&
858 (LowVpn < Node->StartingVpn) &&
859 (Length <= (Node->StartingVpn - LowVpn)))
860 {
861 /* Check if we need to take BoundaryAddress into account */
862 if (BoundaryAddress < Node->StartingVpn)
863 {
864 /* Return the optimal VPN address */
865 *Base = BestVpn;
866 return STATUS_SUCCESS;
867 }
868 else
869 {
870 /* The upper margin is given by the Node's starting address */
871 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
872 return STATUS_SUCCESS;
873 }
874 }
875
876 /* Move to the next node */
877 Node = LowestNode;
878 } while (TRUE);
879
880 /* Check if there's enough space before the lowest Vad */
881 if ((Node->StartingVpn > (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) &&
882 ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length))
883 {
884 /* Check if it fits in perfectly */
885 if (BoundaryAddress < Node->StartingVpn)
886 {
887 /* Return the optimal VPN address */
888 *Base = BestVpn;
889 return STATUS_SUCCESS;
890 }
891
892 /* Return an aligned base address within this node */
893 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
894 return STATUS_SUCCESS;
895 }
896
897 /* No address space left at all */
898 return STATUS_NO_MEMORY;
899}
#define TRUE
Definition: types.h:120
union node Node
Definition: types.h:1255
#define ROUND_UP(n, align)
Definition: eventvwr.h:34
#define ROUND_DOWN(n, align)
Definition: eventvwr.h:33
#define MI_LOWEST_VAD_ADDRESS
Definition: miarm.h:15
MM_AVL_TABLE MmSectionBasedRoot
Definition: section.c:109
_In_ ULONG _In_ ULONG _In_ ULONG Length
Definition: ntddpcm.h:102
#define MM_HIGHEST_VAD_ADDRESS
Definition: mm.h:46
#define STATUS_NO_MEMORY
Definition: ntstatus.h:260
Definition: dlist.c:348
PMMADDRESS_NODE NTAPI MiGetPreviousNode(IN PMMADDRESS_NODE Node)
Definition: vadnode.c:513
#define ROUND_TO_PAGES(Size)

Referenced by MmCreateArm3Section().

◆ MiFindEmptyAddressRangeDownTree()

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 PMMADDRESS_NODE Parent 
)

Definition at line 681 of file vadnode.c.

687{
688 PMMADDRESS_NODE Node, OldNode = NULL, Child;
689 ULONG_PTR LowVpn, HighVpn, AlignmentVpn;
690 PFN_NUMBER PageCount;
691
693
694 /* Sanity checks */
695 ASSERT(BoundaryAddress);
696 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS));
697 ASSERT((Alignment & (PAGE_SIZE - 1)) == 0);
698
699 /* Calculate page numbers for the length and alignment */
701 PageCount = Length >> PAGE_SHIFT;
702 AlignmentVpn = Alignment / PAGE_SIZE;
703
704 /* Check for kernel mode table (memory areas) */
705 if (Table->Unused == 1)
706 {
707 LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
708 }
709 else
710 {
712 }
713
714 /* Check if there is enough space below the boundary */
715 if ((LowVpn + Length) > (BoundaryAddress + 1))
716 {
717 return TableFoundNode;
718 }
719
720 /* Check if the table is empty */
721 if (Table->NumberGenericTableElements == 0)
722 {
723 /* Tree is empty, the candidate address is already the best one */
724 *Base = ALIGN_DOWN_BY(BoundaryAddress + 1 - Length, Alignment);
725 return TableEmptyTree;
726 }
727
728 /* Calculate the initial upper margin */
729 HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT;
730
731 /* Starting from the root, follow the right children until we found a node
732 that ends above the boundary */
733 Node = RtlRightChildAvl(&Table->BalancedRoot);
734 while ((Node->EndingVpn < HighVpn) &&
736
737 /* Now loop the Vad nodes */
738 while (Node)
739 {
740 /* Calculate the lower margin */
741 LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
742
743 /* Check if the current bounds are suitable */
744 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
745 {
746 /* There is enough space to add our node */
747 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, AlignmentVpn);
748 *Base = LowVpn << PAGE_SHIFT;
749
750 /* Can we use the current node as parent? */
752 {
753 /* Node has no right child, so use it as parent */
754 *Parent = Node;
755 return TableInsertAsRight;
756 }
757 else
758 {
759 /* Node has a right child. This means we must have already
760 moved one node left from the right-most node we started
761 with, thus we already have an OldNode! */
762 ASSERT(OldNode != NULL);
763
764 /* The node we had before is the most left grandchild of
765 that right child, use it as parent. */
766 ASSERT(RtlLeftChildAvl(OldNode) == NULL);
767 *Parent = OldNode;
768 return TableInsertAsLeft;
769 }
770 }
771
772 /* Update the upper margin if necessary */
773 if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
774
775 /* Remember the current node and go to the previous node */
776 OldNode = Node;
778 }
779
780 /* Check if there's enough space before the lowest Vad */
782 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
783 {
784 /* There is enough space to add our address */
785 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT);
786 *Base = LowVpn << PAGE_SHIFT;
787 *Parent = OldNode;
788 return TableInsertAsLeft;
789 }
790
791 /* No address space left at all */
792 *Base = 0;
793 *Parent = NULL;
794 return TableFoundNode;
795}
#define ALIGN_DOWN_BY(size, align)
#define ALIGN_UP_BY(size, align)
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn UINT32 *TableIdx UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE Parent
Definition: acpixf.h:732
#define MM_LOWEST_USER_ADDRESS
Definition: armddk.h:20
#define PAGE_SIZE
Definition: env_spec_w32.h:49
#define PAGE_SHIFT
Definition: env_spec_w32.h:45
#define MmSystemRangeStart
Definition: mm.h:32
ULONG PFN_NUMBER
Definition: ke.h:9
_Must_inspect_result_ _In_ WDFDEVICE _In_ WDFDEVICE Child
Definition: wdffdo.h:536

Referenced by MiInsertVadEx(), and MmFindGap().

◆ MiFindEmptyAddressRangeInTree()

TABLE_SEARCH_RESULT NTAPI MiFindEmptyAddressRangeInTree ( IN SIZE_T  Length,
IN ULONG_PTR  Alignment,
IN PMM_AVL_TABLE  Table,
OUT PMMADDRESS_NODE PreviousVad,
OUT PULONG_PTR  Base 
)

Definition at line 584 of file vadnode.c.

589{
590 PMMADDRESS_NODE Node, PreviousNode;
591 ULONG_PTR PageCount, AlignmentVpn, LowVpn, HighestVpn;
592 ASSERT(Length != 0);
593
595
596 /* Calculate page numbers for the length, alignment, and starting address */
597 PageCount = BYTES_TO_PAGES(Length);
598 AlignmentVpn = Alignment >> PAGE_SHIFT;
599 LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT, AlignmentVpn);
600
601 /* Check for kernel mode table (memory areas) */
602 if (Table->Unused == 1)
603 {
604 LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn);
605 }
606
607 /* Check if the table is empty */
608 if (Table->NumberGenericTableElements == 0)
609 {
610 /* Tree is empty, the candidate address is already the best one */
611 *Base = LowVpn << PAGE_SHIFT;
612 return TableEmptyTree;
613 }
614
615 /* Otherwise, follow the leftmost child of the right root node's child */
616 Node = RtlRightChildAvl(&Table->BalancedRoot);
618
619 /* Start a search to find a gap */
620 PreviousNode = NULL;
621 while (Node != NULL)
622 {
623 /* Check if the gap below the current node is suitable */
624 if (Node->StartingVpn >= LowVpn + PageCount)
625 {
626 /* There is enough space to add our node */
627 *Base = LowVpn << PAGE_SHIFT;
628
629 /* Can we use the current node as parent? */
630 if (RtlLeftChildAvl(Node) == NULL)
631 {
632 /* Node has no left child, so use it as parent */
633 *PreviousVad = Node;
634 return TableInsertAsLeft;
635 }
636 else
637 {
638 /* Node has a left child, this means that the previous node is
639 the right-most child of it's left child and can be used as
640 the parent. In case we use the space before the left-most
641 node, it's left child must be NULL. */
642 ASSERT(PreviousNode != NULL);
643 ASSERT(RtlRightChildAvl(PreviousNode) == NULL);
644 *PreviousVad = PreviousNode;
645 return TableInsertAsRight;
646 }
647 }
648
649 /* The next candidate is above the current node */
650 if (Node->EndingVpn >= LowVpn)
651 LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
652
653 /* Remember the current node and go to the next node */
654 PreviousNode = Node;
656 }
657
658 /* We're up to the highest VAD, will this allocation fit above it? */
659 HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) / PAGE_SIZE;
660
661 /* Check for kernel mode table (memory areas) */
662 if (Table->Unused == 1)
663 {
664 HighestVpn = ALIGN_UP_BY((ULONG_PTR)(LONG_PTR)-1 >> PAGE_SHIFT, AlignmentVpn);
665 }
666
667 if (HighestVpn >= LowVpn + PageCount)
668 {
669 /* Yes! Use this VAD to store the allocation */
670 *PreviousVad = PreviousNode;
671 *Base = LowVpn << PAGE_SHIFT;
672 return TableInsertAsRight;
673 }
674
675 /* Nyet, there's no free address space for this allocation, so we'll fail */
676 return TableFoundNode;
677}
__int3264 LONG_PTR
Definition: mstsclib_h.h:276
PMMADDRESS_NODE NTAPI MiGetNextNode(IN PMMADDRESS_NODE Node)
Definition: vadnode.c:549
#define BYTES_TO_PAGES(Size)

Referenced by MiInsertVadEx(), MiMapLockedPagesInUserSpace(), and MmFindGap().

◆ MiGetNextNode()

PMMADDRESS_NODE NTAPI MiGetNextNode ( IN PMMADDRESS_NODE  Node)

Definition at line 549 of file vadnode.c.

550{
552
553 /* Get the right child */
555 {
556 /* Get left-most child */
559 return Node;
560 }
561
563 ASSERT(Parent != NULL);
564 while (Parent != Node)
565 {
566 /* The parent should be a left child, return the real predecessor */
568 {
569 /* Return it */
570 return Parent;
571 }
572
573 /* Keep lopping until we find our parent */
574 Node = Parent;
576 }
577
578 /* Nothing found */
579 return NULL;
580}
#define RtlParentAvl
Definition: miavl.h:44
#define RtlIsLeftChildAvl
Definition: miavl.h:47

Referenced by MiFindEmptyAddressRangeInTree(), and MiQueryMemoryBasicInformation().

◆ MiGetPreviousNode()

PMMADDRESS_NODE NTAPI MiGetPreviousNode ( IN PMMADDRESS_NODE  Node)

Definition at line 513 of file vadnode.c.

514{
516
517 /* Get the left child */
519 {
520 /* Get right-most child */
523 return Node;
524 }
525
527 ASSERT(Parent != NULL);
528 while (Parent != Node)
529 {
530 /* The parent should be a right child, return the real predecessor */
532 {
533 /* Return it unless it's the root */
535 return Parent;
536 }
537
538 /* Keep lopping until we find our parent */
539 Node = Parent;
541 }
542
543 /* Nothing found */
544 return NULL;
545}
#define RtlIsRightChildAvl
Definition: miavl.h:48

Referenced by MiFindEmptyAddressRangeDownBasedTree(), and MiFindEmptyAddressRangeDownTree().

◆ MiInsertBasedSection()

VOID NTAPI MiInsertBasedSection ( IN PSECTION  Section)

Definition at line 423 of file vadnode.c.

424{
427 ASSERT(Section->Address.EndingVpn >= Section->Address.StartingVpn);
428
430
431 /* Find the parent VAD and where this child should be inserted */
432 Result = RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot, (PVOID)Section->Address.StartingVpn, &Parent);
433 ASSERT(Result != TableFoundNode);
434 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
435 MiInsertNode(&MmSectionBasedRoot, &Section->Address, Parent, Result);
436}
#define RtlpFindAvlTableNodeOrParent
Definition: miavl.h:32
VOID NTAPI MiInsertNode(IN PMM_AVL_TABLE Table, IN PMMADDRESS_NODE NewNode, IN PMMADDRESS_NODE Parent, IN TABLE_SEARCH_RESULT Result)
Definition: vadnode.c:202
#define ASSERT_LOCKED_FOR_WRITE(Table)
Definition: vadnode.c:110
_At_(*)(_In_ PWSK_CLIENT Client, _In_opt_ PUNICODE_STRING NodeName, _In_opt_ PUNICODE_STRING ServiceName, _In_opt_ ULONG NameSpace, _In_opt_ GUID *Provider, _In_opt_ PADDRINFOEXW Hints, _Outptr_ PADDRINFOEXW *Result, _In_opt_ PEPROCESS OwningProcess, _In_opt_ PETHREAD OwningThread, _Inout_ PIRP Irp Result)(Mem)) NTSTATUS(WSKAPI *PFN_WSK_GET_ADDRESS_INFO
Definition: wsk.h:409
TABLE_SEARCH_RESULT
Definition: rtltypes.h:386

Referenced by MmCreateArm3Section().

◆ MiInsertNode()

VOID NTAPI MiInsertNode ( IN PMM_AVL_TABLE  Table,
IN PMMADDRESS_NODE  NewNode,
IN PMMADDRESS_NODE  Parent,
IN TABLE_SEARCH_RESULT  Result 
)

Definition at line 202 of file vadnode.c.

206{
207 PMMVAD_LONG Vad;
208
210
211 /* Insert it into the tree */
213
214 /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
215 Vad = (PMMVAD_LONG)NewNode;
216 if (Vad->u.VadFlags.Spare == 0)
217 {
220 SIZE_T Size;
222 PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
223
224 Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
225
226 if (AllocatedBase == NULL)
227 {
228 AllocatedBase = (PVOID)(ULONG_PTR)1;
229 Size -= 1;
230 }
231
234 &AllocatedBase,
235 Size,
237 &MemoryArea,
238 0,
239 PAGE_SIZE);
241
242 /* Check if this is VM VAD */
243 if (Vad->ControlArea == NULL)
244 {
245 /* We store the reactos MEMORY_AREA here */
247 }
248 else
249 {
250 /* This is a section VAD. Store the MAREA here for now */
251 ASSERT(Vad->u4.Banked == (PVOID)(ULONG_PTR)0xDEADBABEDEADBABEULL);
252 Vad->u4.Banked = (PVOID)MemoryArea;
253 }
254 }
255}
LONG NTSTATUS
Definition: precomp.h:26
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
_Must_inspect_result_ _In_ PLARGE_INTEGER _In_ PLARGE_INTEGER _In_ ULONG _In_ PFILE_OBJECT _In_ PVOID Process
Definition: fsrtlfuncs.h:223
Status
Definition: gdiplustypes.h:25
#define RtlpInsertAvlTreeNode
Definition: miavl.h:35
struct _MMPTE * PMMPTE
struct _MMVAD_LONG * PMMVAD_LONG
_In_ PMEMORY_AREA MemoryArea
Definition: newmm.h:207
#define PAGE_READWRITE
Definition: nt_native.h:1304
NTSTATUS NTAPI MmCreateMemoryArea(PMMSUPPORT AddressSpace, ULONG Type, PVOID *BaseAddress, SIZE_T Length, ULONG Protection, PMEMORY_AREA *Result, ULONG AllocationFlags, ULONG AllocationGranularity)
Definition: marea.c:410
#define MEMORY_AREA_OWNED_BY_ARM3
Definition: mm.h:97
ULONG_PTR Spare
Definition: mmtypes.h:697
union _MMVAD_LONG::@2628 u4
PMMPTE FirstPrototypePte
Definition: mmtypes.h:766
PVOID Banked
Definition: mmtypes.h:780
MMVAD_FLAGS VadFlags
Definition: mmtypes.h:763
ULONG_PTR EndingVpn
Definition: mmtypes.h:759
PCONTROL_AREA ControlArea
Definition: mmtypes.h:765
union _MMVAD_LONG::@2625 u
ULONG_PTR StartingVpn
Definition: mmtypes.h:758
void * PVOID
Definition: typedefs.h:50
ULONG_PTR SIZE_T
Definition: typedefs.h:80
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260

Referenced by MiInsertBasedSection(), MiInsertVad(), and MiInsertVadEx().

◆ MiInsertVad()

VOID NTAPI MiInsertVad ( IN PMMVAD  Vad,
IN PMM_AVL_TABLE  VadRoot 
)

Definition at line 259 of file vadnode.c.

261{
264
266
267 /* Validate the VAD and set it as the current hint */
268 ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
269 VadRoot->NodeHint = Vad;
270
271 /* Find the parent VAD and where this child should be inserted */
272 Result = RtlpFindAvlTableNodeOrParent(VadRoot, (PVOID)Vad->StartingVpn, &Parent);
273 ASSERT(Result != TableFoundNode);
274 ASSERT((Parent != NULL) || (Result == TableEmptyTree));
275
276 /* Do the actual insert operation */
277 MiInsertNode(VadRoot, (PVOID)Vad, Parent, Result);
278}

Referenced by MmInsertMemoryArea().

◆ MiInsertVadEx()

NTSTATUS NTAPI MiInsertVadEx ( _Inout_ PMMVAD  Vad,
_In_ ULONG_PTR BaseAddress,
_In_ SIZE_T  ViewSize,
_In_ ULONG_PTR  HighestAddress,
_In_ ULONG_PTR  Alignment,
_In_ ULONG  AllocationType 
)

Definition at line 282 of file vadnode.c.

289{
290 ULONG_PTR StartingAddress, EndingAddress;
291 PEPROCESS CurrentProcess;
292 PETHREAD CurrentThread;
295
296 /* Align the view size to pages */
298
299 /* Get the current process */
300 CurrentProcess = PsGetCurrentProcess();
301
302 /* Acquire the address creation lock and make sure the process is alive */
304 if (CurrentProcess->VmDeleted)
305 {
307 DPRINT1("The process is dying\n");
309 }
310
311 /* Did the caller specify an address? */
312 if (*BaseAddress == 0)
313 {
314 /* Make sure HighestAddress is not too large */
315 HighestAddress = min(HighestAddress, (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS);
316
317 /* Which way should we search? */
318 if ((AllocationType & MEM_TOP_DOWN) || CurrentProcess->VmTopDown)
319 {
320 /* Find an address top-down */
322 HighestAddress,
323 Alignment,
324 &CurrentProcess->VadRoot,
325 &StartingAddress,
326 &Parent);
327 }
328 else
329 {
330 /* Find an address bottom-up */
332 Alignment,
333 &CurrentProcess->VadRoot,
334 &Parent,
335 &StartingAddress);
336 }
337
338 /* Get the ending address, which is the last piece we need for the VAD */
339 EndingAddress = StartingAddress + ViewSize - 1;
340
341 /* Check if we found a suitable location */
342 if ((Result == TableFoundNode) || (EndingAddress > HighestAddress))
343 {
344 DPRINT1("Not enough free space to insert this VAD node!\n");
346 return STATUS_NO_MEMORY;
347 }
348
349 ASSERT(StartingAddress != 0);
350 ASSERT(StartingAddress < (ULONG_PTR)HighestAddress);
351 ASSERT(EndingAddress > StartingAddress);
352 }
353 else
354 {
355 /* Calculate the starting and ending address */
356 StartingAddress = ALIGN_DOWN_BY(*BaseAddress, Alignment);
357 EndingAddress = StartingAddress + ViewSize - 1;
358
359 /* Make sure it doesn't conflict with an existing allocation */
360 Result = MiCheckForConflictingNode(StartingAddress >> PAGE_SHIFT,
361 EndingAddress >> PAGE_SHIFT,
362 &CurrentProcess->VadRoot,
363 &Parent);
364 if (Result == TableFoundNode)
365 {
366 DPRINT("Given address conflicts with existing node\n");
369 }
370 }
371
372 /* Now set the VAD address */
373 Vad->StartingVpn = StartingAddress >> PAGE_SHIFT;
374 Vad->EndingVpn = EndingAddress >> PAGE_SHIFT;
375
376 /* Check if we already need to charge for the pages */
377 if ((Vad->u.VadFlags.PrivateMemory && Vad->u.VadFlags.MemCommit) ||
378 (!Vad->u.VadFlags.PrivateMemory &&
379 (Vad->u.VadFlags.Protection & PAGE_WRITECOPY)))
380 {
381 /* Set the commit charge */
382 Vad->u.VadFlags.CommitCharge = ViewSize / PAGE_SIZE;
383 }
384
385 /* Check if the VAD is to be secured */
386 if (Vad->u2.VadFlags2.OneSecured)
387 {
388 /* This *must* be a long VAD! */
389 ASSERT(Vad->u2.VadFlags2.LongVad);
390
391 /* Yeah this is retarded, I didn't invent it! */
392 ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn = StartingAddress;
393 ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn = EndingAddress;
394 }
395
396 /* Lock the working set */
397 CurrentThread = PsGetCurrentThread();
398 MiLockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
399
400 /* Insert the VAD */
401 CurrentProcess->VadRoot.NodeHint = Vad;
402 MiInsertNode(&CurrentProcess->VadRoot, (PVOID)Vad, Parent, Result);
403
404 /* Release the working set */
405 MiUnlockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
406
407 /* Update the process' virtual size, and peak virtual size */
408 CurrentProcess->VirtualSize += ViewSize;
409 if (CurrentProcess->VirtualSize > CurrentProcess->PeakVirtualSize)
410 {
411 CurrentProcess->PeakVirtualSize = CurrentProcess->VirtualSize;
412 }
413
414 /* Unlock the address space */
416
417 *BaseAddress = StartingAddress;
418 return STATUS_SUCCESS;
419}
#define PsGetCurrentThread()
Definition: env_spec_w32.h:81
VOID FASTCALL KeReleaseGuardedMutex(IN OUT PKGUARDED_MUTEX GuardedMutex)
Definition: gmutex.c:53
VOID FASTCALL KeAcquireGuardedMutex(IN PKGUARDED_MUTEX GuardedMutex)
Definition: gmutex.c:42
FORCEINLINE VOID MiUnlockProcessWorkingSetUnsafe(IN PEPROCESS Process, IN PETHREAD Thread)
Definition: miarm.h:1239
FORCEINLINE VOID MiLockProcessWorkingSetUnsafe(IN PEPROCESS Process, IN PETHREAD Thread)
Definition: miarm.h:1169
#define min(a, b)
Definition: monoChain.cc:55
_In_ HANDLE _Outptr_result_bytebuffer_ ViewSize PVOID * BaseAddress
Definition: mmfuncs.h:404
_In_ HANDLE _Outptr_result_bytebuffer_ ViewSize PVOID _In_ ULONG_PTR _In_ SIZE_T _Inout_opt_ PLARGE_INTEGER _Inout_ PSIZE_T _In_ SECTION_INHERIT _In_ ULONG AllocationType
Definition: mmfuncs.h:410
_In_ HANDLE _Outptr_result_bytebuffer_ ViewSize PVOID _In_ ULONG_PTR _In_ SIZE_T _Inout_opt_ PLARGE_INTEGER _Inout_ PSIZE_T ViewSize
Definition: mmfuncs.h:408
#define MEM_TOP_DOWN
Definition: nt_native.h:1321
#define PAGE_WRITECOPY
Definition: nt_native.h:1305
#define STATUS_PROCESS_IS_TERMINATING
Definition: ntstatus.h:502
#define STATUS_CONFLICTING_ADDRESSES
Definition: ntstatus.h:261
#define DPRINT
Definition: sndvol32.h:73
MM_AVL_TABLE VadRoot
Definition: pstypes.h:1453
EX_PUSH_LOCK AddressCreationLock
Definition: pstypes.h:1290
SIZE_T PeakVirtualSize
Definition: pstypes.h:1272
SIZE_T VirtualSize
Definition: pstypes.h:1273
ULONG VmDeleted
Definition: pstypes.h:1398
ULONG VmTopDown
Definition: pstypes.h:1417
PVOID NodeHint
Definition: mmtypes.h:670
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 PMMADDRESS_NODE *Parent)
Definition: vadnode.c:681
TABLE_SEARCH_RESULT NTAPI MiFindEmptyAddressRangeInTree(IN SIZE_T Length, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *PreviousVad, OUT PULONG_PTR Base)
Definition: vadnode.c:584
TABLE_SEARCH_RESULT NTAPI MiCheckForConflictingNode(IN ULONG_PTR StartVpn, IN ULONG_PTR EndVpn, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *NodeOrParent)
Definition: vadnode.c:150
#define PsGetCurrentProcess
Definition: psfuncs.h:17

Referenced by MiCreatePebOrTeb(), MiMapViewOfDataSection(), and NtAllocateVirtualMemory().

◆ MiLocateAddress()

PMMVAD NTAPI MiLocateAddress ( IN PVOID  VirtualAddress)

Definition at line 116 of file vadnode.c.

117{
118 PMMVAD FoundVad;
119 ULONG_PTR Vpn;
121 TABLE_SEARCH_RESULT SearchResult;
122
124
125 /* Start with the the hint */
126 FoundVad = (PMMVAD)Table->NodeHint;
127 if (!FoundVad) return NULL;
128
129 /* Check if this VPN is in the hint, if so, use it */
131 if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
132
133 /* VAD hint didn't work, go look for it */
134 SearchResult = RtlpFindAvlTableNodeOrParent(Table,
135 (PVOID)Vpn,
136 (PMMADDRESS_NODE*)&FoundVad);
137 if (SearchResult != TableFoundNode) return NULL;
138
139 /* We found it, update the hint */
140 ASSERT(FoundVad != NULL);
141 ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
142
143 /* We allow this (atomic) update without exclusive lock, because it's a hint only */
144 Table->NodeHint = FoundVad;
145 return FoundVad;
146}
if(dx< 0)
Definition: linetemp.h:194
struct _MMVAD * PMMVAD
ULONG_PTR EndingVpn
Definition: mmtypes.h:730
ULONG_PTR StartingVpn
Definition: mmtypes.h:729
_Must_inspect_result_ _In_ WDFDMATRANSACTION _In_ PFN_WDF_PROGRAM_DMA _In_ WDF_DMA_DIRECTION _In_ PMDL _In_ PVOID VirtualAddress

Referenced by MiCheckVadsForLockOperation(), MiCheckVirtualAddress(), MiUnmapLockedPagesInUserSpace(), MiUnmapViewOfSection(), MmDeleteTeb(), MmGetFileNameForAddress(), NtAreMappedFilesTheSame(), and NtFreeVirtualMemory().

◆ MiRemoveNode()

VOID NTAPI MiRemoveNode ( IN PMMADDRESS_NODE  Node,
IN PMM_AVL_TABLE  Table 
)

Definition at line 440 of file vadnode.c.

442{
443 PMMVAD_LONG Vad;
444
446
447 /* Call the AVL code */
449
450 /* Decrease element count */
451 Table->NumberGenericTableElements--;
452
453 /* Check if this node was the hint */
454 if (Table->NodeHint == Node)
455 {
456 /* Get a new hint, unless we're empty now, in which case nothing */
457 if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
458 else Table->NodeHint = Table->BalancedRoot.RightChild;
459 }
460
461 /* Free the node from ReactOS view as well */
462 Vad = (PMMVAD_LONG)Node;
463 if ((Table != &MmSectionBasedRoot) && (Vad->u.VadFlags.Spare == 0))
464 {
467
468 /* Check if this is VM VAD */
469 if (Vad->ControlArea == NULL)
470 {
471 /* We store the ReactOS MEMORY_AREA here */
473 }
474 else
475 {
476 /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
478 }
479
480 /* Make sure one actually still exists */
481 if (MemoryArea)
482 {
483 /* Make sure we have not already freed it */
484 ASSERT(MemoryArea != (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL);
485
486 /* Get the process */
488
489 /* We only create fake memory-areas for ARM3 VADs */
492
493 /* Free it */
495
496 /* Check if this is VM VAD */
497 if (Vad->ControlArea == NULL)
498 {
499 /* Delete the pointer to it */
500 Vad->FirstPrototypePte = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL;
501 }
502 else
503 {
504 /* Delete the pointer to it */
505 Vad->u4.Banked = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL;
506 }
507 }
508 }
509}
#define RtlpDeleteAvlTreeNode
Definition: miavl.h:36
NTSTATUS NTAPI MmFreeMemoryArea(PMMSUPPORT AddressSpace, PMEMORY_AREA MemoryArea, PMM_FREE_PAGE_FUNC FreePage, PVOID FreePageContext)
Definition: marea.c:283
struct _MEMORY_AREA * PMEMORY_AREA
PVOID Vad
Definition: mm.h:255
ULONG Type
Definition: mm.h:251

Referenced by MiDeleteARM3Section(), MiUnmapLockedPagesInUserSpace(), MiUnmapViewOfSection(), MmCleanProcessAddressSpace(), MmDeleteTeb(), MmFreeMemoryArea(), and NtFreeVirtualMemory().

Variable Documentation

◆ MiRosKernelVadRoot

MM_AVL_TABLE MiRosKernelVadRoot
extern

◆ MmReadWrite