Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880/* * PROJECT: ReactOS Kernel * LICENSE: BSD - See COPYING.ARM in the top level directory * FILE: ntoskrnl/mm/ARM3/vadnode.c * PURPOSE: ARM Memory Manager VAD Node Algorithms * PROGRAMMERS: ReactOS Portable Systems Group * Timo Kreuzer (timo.kreuzer@reactos.org) */
/* INCLUDES *******************************************************************/
#include <ntoskrnl.h>#define NDEBUG#include <debug.h>
#define MODULE_INVOLVED_IN_ARM3#include <mm/ARM3/miarm.h>
/* Include Mm version of AVL support */#include "miavl.h"#include <sdk/lib/rtl/avlsupp.c>
/* GLOBALS ********************************************************************/
CHAR MmReadWrite[32] ={ MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,};
/* FUNCTIONS ******************************************************************/
extern MM_AVL_TABLE MiRosKernelVadRoot;
#if DBG
staticVOIDMiDbgAssertIsLockedForRead(_In_ PMM_AVL_TABLE Table){ if (Table == &MmSectionBasedRoot) { /* Need to hold MmSectionBasedMutex */ ASSERT(MmSectionBasedMutex.Owner == KeGetCurrentThread()); } else if (Table == &MiRosKernelVadRoot) { /* Need to hold either the system working-set lock or the idle process' AddressCreationLock */ ASSERT(PsGetCurrentThread()->OwnsSystemWorkingSetExclusive || PsGetCurrentThread()->OwnsSystemWorkingSetShared || (PsIdleProcess->AddressCreationLock.Owner == KeGetCurrentThread())); } else { /* Need to hold either the process working-set lock or the current process' AddressCreationLock */ PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot); ASSERT(MI_WS_OWNER(Process) || (Process->AddressCreationLock.Owner == KeGetCurrentThread())); }}
staticVOIDMiDbgAssertIsLockedForWrite(_In_ PMM_AVL_TABLE Table){ if (Table == &MmSectionBasedRoot) { /* Need to hold MmSectionBasedMutex */ ASSERT(MmSectionBasedMutex.Owner == KeGetCurrentThread()); } else if (Table == &MiRosKernelVadRoot) { /* Need to hold both the system working-set lock exclusive and the idle process' AddressCreationLock */ ASSERT(PsGetCurrentThread()->OwnsSystemWorkingSetExclusive); ASSERT(PsIdleProcess->AddressCreationLock.Owner == KeGetCurrentThread()); } else { /* Need to hold both the process working-set lock exclusive and the current process' AddressCreationLock */ PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot); ASSERT(Process == PsGetCurrentProcess()); ASSERT(PsGetCurrentThread()->OwnsProcessWorkingSetExclusive); ASSERT(Process->AddressCreationLock.Owner == KeGetCurrentThread()); }}
#define ASSERT_LOCKED_FOR_READ(Table) MiDbgAssertIsLockedForRead(Table)#define ASSERT_LOCKED_FOR_WRITE(Table) MiDbgAssertIsLockedForWrite(Table)
#else // DBG
#define ASSERT_LOCKED_FOR_READ(Table)#define ASSERT_LOCKED_FOR_WRITE(Table)
#endif // DBG
PMMVADNTAPIMiLocateVad(_In_ PMM_AVL_TABLE Table, _In_ PVOID VirtualAddress){ PMMVAD FoundVad; ULONG_PTR Vpn; TABLE_SEARCH_RESULT SearchResult;
ASSERT_LOCKED_FOR_READ(Table);
/* Start with the the hint */ FoundVad = (PMMVAD)Table->NodeHint; if (!FoundVad) return NULL;
/* Check if this VPN is in the hint, if so, use it */ Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT; if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
/* VAD hint didn't work, go look for it */ SearchResult = RtlpFindAvlTableNodeOrParent(Table, (PVOID)Vpn, (PMMADDRESS_NODE*)&FoundVad); if (SearchResult != TableFoundNode) return NULL;
/* We found it, update the hint */ ASSERT(FoundVad != NULL); ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
/* We allow this (atomic) update without exclusive lock, because it's a hint only */ Table->NodeHint = FoundVad; return FoundVad;}
PMMVADNTAPIMiLocateAddress(_In_ PVOID VirtualAddress){ PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot; return MiLocateVad(Table, VirtualAddress);}
TABLE_SEARCH_RESULTNTAPIMiCheckForConflictingNode(IN ULONG_PTR StartVpn, IN ULONG_PTR EndVpn, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *NodeOrParent){ PMMADDRESS_NODE ParentNode, CurrentNode;
ASSERT_LOCKED_FOR_READ(Table);
/* If the tree is empty, there is no conflict */ if (Table->NumberGenericTableElements == 0) return TableEmptyTree;
/* Start looping from the root node */ CurrentNode = RtlRightChildAvl(&Table->BalancedRoot); ASSERT(CurrentNode != NULL); while (CurrentNode) { ParentNode = CurrentNode;
/* This address comes after */ if (StartVpn > CurrentNode->EndingVpn) { /* Keep searching on the right */ CurrentNode = RtlRightChildAvl(CurrentNode); } else if (EndVpn < CurrentNode->StartingVpn) { /* This address ends before the node starts, search on the left */ CurrentNode = RtlLeftChildAvl(CurrentNode); } else { /* This address is part of this node, return it */ *NodeOrParent = ParentNode; return TableFoundNode; } }
/* There is no more child, save the current node as parent */ *NodeOrParent = ParentNode; if (StartVpn > ParentNode->EndingVpn) { return TableInsertAsRight; } else { return TableInsertAsLeft; }}
VOIDNTAPIMiInsertNode(IN PMM_AVL_TABLE Table, IN PMMADDRESS_NODE NewNode, IN PMMADDRESS_NODE Parent, IN TABLE_SEARCH_RESULT Result){ ASSERT_LOCKED_FOR_WRITE(Table);
/* Insert it into the tree */ RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);}
VOIDNTAPIMiInsertVad(IN PMMVAD Vad, IN PMM_AVL_TABLE VadRoot){ TABLE_SEARCH_RESULT Result; PMMADDRESS_NODE Parent = NULL;
ASSERT_LOCKED_FOR_WRITE(VadRoot);
/* Validate the VAD and set it as the current hint */ ASSERT(Vad->EndingVpn >= Vad->StartingVpn); VadRoot->NodeHint = Vad;
/* Find the parent VAD and where this child should be inserted */ Result = RtlpFindAvlTableNodeOrParent(VadRoot, (PVOID)Vad->StartingVpn, &Parent); ASSERT(Result != TableFoundNode); ASSERT((Parent != NULL) || (Result == TableEmptyTree));
/* Do the actual insert operation */ MiInsertNode(VadRoot, (PVOID)Vad, Parent, Result);}
NTSTATUSNTAPIMiInsertVadEx( _Inout_ PMMVAD Vad, _In_ ULONG_PTR *BaseAddress, _In_ SIZE_T ViewSize, _In_ ULONG_PTR HighestAddress, _In_ ULONG_PTR Alignment, _In_ ULONG AllocationType){ ULONG_PTR StartingAddress, EndingAddress; PEPROCESS CurrentProcess; PETHREAD CurrentThread; TABLE_SEARCH_RESULT Result; PMMADDRESS_NODE Parent;
/* Align the view size to pages */ ViewSize = ALIGN_UP_BY(ViewSize, PAGE_SIZE);
/* Get the current process */ CurrentProcess = PsGetCurrentProcess();
/* Acquire the address creation lock and make sure the process is alive */ KeAcquireGuardedMutex(&CurrentProcess->AddressCreationLock); if (CurrentProcess->VmDeleted) { KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock); DPRINT1("The process is dying\n"); return STATUS_PROCESS_IS_TERMINATING; }
/* Did the caller specify an address? */ if (*BaseAddress == 0) { /* Make sure HighestAddress is not too large */ HighestAddress = min(HighestAddress, (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS);
/* Which way should we search? */ if ((AllocationType & MEM_TOP_DOWN) || CurrentProcess->VmTopDown) { /* Find an address top-down */ Result = MiFindEmptyAddressRangeDownTree(ViewSize, HighestAddress, Alignment, &CurrentProcess->VadRoot, &StartingAddress, &Parent); } else { /* Find an address bottom-up */ Result = MiFindEmptyAddressRangeInTree(ViewSize, Alignment, &CurrentProcess->VadRoot, &Parent, &StartingAddress); }
/* Get the ending address, which is the last piece we need for the VAD */ EndingAddress = StartingAddress + ViewSize - 1;
/* Check if we found a suitable location */ if ((Result == TableFoundNode) || (EndingAddress > HighestAddress)) { DPRINT1("Not enough free space to insert this VAD node!\n"); KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock); return STATUS_NO_MEMORY; }
ASSERT(StartingAddress != 0); ASSERT(StartingAddress < (ULONG_PTR)HighestAddress); ASSERT(EndingAddress > StartingAddress); } else { /* Calculate the starting and ending address */ StartingAddress = ALIGN_DOWN_BY(*BaseAddress, Alignment); EndingAddress = StartingAddress + ViewSize - 1;
/* Make sure it doesn't conflict with an existing allocation */ Result = MiCheckForConflictingNode(StartingAddress >> PAGE_SHIFT, EndingAddress >> PAGE_SHIFT, &CurrentProcess->VadRoot, &Parent); if (Result == TableFoundNode) { DPRINT("Given address conflicts with existing node\n"); KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock); return STATUS_CONFLICTING_ADDRESSES; } }
/* Now set the VAD address */ Vad->StartingVpn = StartingAddress >> PAGE_SHIFT; Vad->EndingVpn = EndingAddress >> PAGE_SHIFT;
/* Check if we already need to charge for the pages */ if ((Vad->u.VadFlags.PrivateMemory && Vad->u.VadFlags.MemCommit) || (!Vad->u.VadFlags.PrivateMemory && (Vad->u.VadFlags.Protection & PAGE_WRITECOPY))) { /* Set the commit charge */ Vad->u.VadFlags.CommitCharge = ViewSize / PAGE_SIZE; }
/* Check if the VAD is to be secured */ if (Vad->u2.VadFlags2.OneSecured) { /* This *must* be a long VAD! */ ASSERT(Vad->u2.VadFlags2.LongVad);
/* Yeah this is retarded, I didn't invent it! */ ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn = StartingAddress; ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn = EndingAddress; }
/* Lock the working set */ CurrentThread = PsGetCurrentThread(); MiLockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
/* Insert the VAD */ CurrentProcess->VadRoot.NodeHint = Vad; MiInsertNode(&CurrentProcess->VadRoot, (PVOID)Vad, Parent, Result);
/* Release the working set */ MiUnlockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
/* Update the process' virtual size, and peak virtual size */ CurrentProcess->VirtualSize += ViewSize; if (CurrentProcess->VirtualSize > CurrentProcess->PeakVirtualSize) { CurrentProcess->PeakVirtualSize = CurrentProcess->VirtualSize; }
/* Unlock the address space */ KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
*BaseAddress = StartingAddress; return STATUS_SUCCESS;}
VOIDNTAPIMiInsertBasedSection(IN PSECTION Section){ TABLE_SEARCH_RESULT Result; PMMADDRESS_NODE Parent = NULL; ASSERT(Section->Address.EndingVpn >= Section->Address.StartingVpn);
ASSERT_LOCKED_FOR_WRITE(&MmSectionBasedRoot);
/* Find the parent VAD and where this child should be inserted */ Result = RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot, (PVOID)Section->Address.StartingVpn, &Parent); ASSERT(Result != TableFoundNode); ASSERT((Parent != NULL) || (Result == TableEmptyTree)); MiInsertNode(&MmSectionBasedRoot, &Section->Address, Parent, Result);}
VOIDNTAPIMiRemoveNode(IN PMMADDRESS_NODE Node, IN PMM_AVL_TABLE Table){ ASSERT_LOCKED_FOR_WRITE(Table);
/* Call the AVL code */ RtlpDeleteAvlTreeNode(Table, Node);
/* Decrease element count */ Table->NumberGenericTableElements--;
/* Check if this node was the hint */ if (Table->NodeHint == Node) { /* Get a new hint, unless we're empty now, in which case nothing */ if (!Table->NumberGenericTableElements) Table->NodeHint = NULL; else Table->NodeHint = Table->BalancedRoot.RightChild; }}
PMMADDRESS_NODENTAPIMiGetPreviousNode(IN PMMADDRESS_NODE Node){ PMMADDRESS_NODE Parent;
/* Get the left child */ if (RtlLeftChildAvl(Node)) { /* Get right-most child */ Node = RtlLeftChildAvl(Node); while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node); return Node; }
Parent = RtlParentAvl(Node); ASSERT(Parent != NULL); while (Parent != Node) { /* The parent should be a right child, return the real predecessor */ if (RtlIsRightChildAvl(Node)) { /* Return it unless it's the root */ if (Parent == RtlParentAvl(Parent)) Parent = NULL; return Parent; }
/* Keep lopping until we find our parent */ Node = Parent; Parent = RtlParentAvl(Node); }
/* Nothing found */ return NULL;}
PMMADDRESS_NODENTAPIMiGetNextNode(IN PMMADDRESS_NODE Node){ PMMADDRESS_NODE Parent;
/* Get the right child */ if (RtlRightChildAvl(Node)) { /* Get left-most child */ Node = RtlRightChildAvl(Node); while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node); return Node; }
Parent = RtlParentAvl(Node); ASSERT(Parent != NULL); while (Parent != Node) { /* The parent should be a left child, return the real predecessor */ if (RtlIsLeftChildAvl(Node)) { /* Return it */ return Parent; }
/* Keep lopping until we find our parent */ Node = Parent; Parent = RtlParentAvl(Node); }
/* Nothing found */ return NULL;}
TABLE_SEARCH_RESULTNTAPIMiFindEmptyAddressRangeInTree(IN SIZE_T Length, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PMMADDRESS_NODE *PreviousVad, OUT PULONG_PTR Base){ PMMADDRESS_NODE Node, PreviousNode; ULONG_PTR PageCount, AlignmentVpn, LowVpn, HighestVpn; ASSERT(Length != 0);
ASSERT_LOCKED_FOR_READ(Table);
/* Calculate page numbers for the length, alignment, and starting address */ PageCount = BYTES_TO_PAGES(Length); AlignmentVpn = Alignment >> PAGE_SHIFT; LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT, AlignmentVpn);
/* Check for kernel mode table (memory areas) */ if (Table->Unused == 1) { LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn); }
/* Check if the table is empty */ if (Table->NumberGenericTableElements == 0) { /* Tree is empty, the candidate address is already the best one */ *Base = LowVpn << PAGE_SHIFT; return TableEmptyTree; }
/* Otherwise, follow the leftmost child of the right root node's child */ Node = RtlRightChildAvl(&Table->BalancedRoot); while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
/* Start a search to find a gap */ PreviousNode = NULL; while (Node != NULL) { /* Check if the gap below the current node is suitable */ if (Node->StartingVpn >= LowVpn + PageCount) { /* There is enough space to add our node */ *Base = LowVpn << PAGE_SHIFT;
/* Can we use the current node as parent? */ if (RtlLeftChildAvl(Node) == NULL) { /* Node has no left child, so use it as parent */ *PreviousVad = Node; return TableInsertAsLeft; } else { /* Node has a left child, this means that the previous node is the right-most child of it's left child and can be used as the parent. In case we use the space before the left-most node, it's left child must be NULL. */ ASSERT(PreviousNode != NULL); ASSERT(RtlRightChildAvl(PreviousNode) == NULL); *PreviousVad = PreviousNode; return TableInsertAsRight; } }
/* The next candidate is above the current node */ if (Node->EndingVpn >= LowVpn) LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
/* Remember the current node and go to the next node */ PreviousNode = Node; Node = MiGetNextNode(Node); }
/* We're up to the highest VAD, will this allocation fit above it? */ HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) / PAGE_SIZE;
/* Check for kernel mode table (memory areas) */ if (Table->Unused == 1) { HighestVpn = ALIGN_UP_BY((ULONG_PTR)(LONG_PTR)-1 >> PAGE_SHIFT, AlignmentVpn); }
if (HighestVpn >= LowVpn + PageCount) { /* Yes! Use this VAD to store the allocation */ *PreviousVad = PreviousNode; *Base = LowVpn << PAGE_SHIFT; return TableInsertAsRight; }
/* Nyet, there's no free address space for this allocation, so we'll fail */ return TableFoundNode;}
TABLE_SEARCH_RESULTNTAPIMiFindEmptyAddressRangeDownTree(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){ PMMADDRESS_NODE Node, OldNode = NULL, Child; ULONG_PTR LowVpn, HighVpn, AlignmentVpn; PFN_NUMBER PageCount;
ASSERT_LOCKED_FOR_READ(Table);
/* Sanity checks */ ASSERT(BoundaryAddress); ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS)); ASSERT((Alignment & (PAGE_SIZE - 1)) == 0);
/* Calculate page numbers for the length and alignment */ Length = ROUND_TO_PAGES(Length); PageCount = Length >> PAGE_SHIFT; AlignmentVpn = Alignment / PAGE_SIZE;
/* Check for kernel mode table (memory areas) */ if (Table->Unused == 1) { LowVpn = ALIGN_UP_BY((ULONG_PTR)MmSystemRangeStart >> PAGE_SHIFT, AlignmentVpn); } else { LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS, Alignment); }
/* Check if there is enough space below the boundary */ if ((LowVpn + Length) > (BoundaryAddress + 1)) { return TableFoundNode; }
/* Check if the table is empty */ if (Table->NumberGenericTableElements == 0) { /* Tree is empty, the candidate address is already the best one */ *Base = ALIGN_DOWN_BY(BoundaryAddress + 1 - Length, Alignment); return TableEmptyTree; }
/* Calculate the initial upper margin */ HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT;
/* Starting from the root, follow the right children until we found a node that ends above the boundary */ Node = RtlRightChildAvl(&Table->BalancedRoot); while ((Node->EndingVpn < HighVpn) && ((Child = RtlRightChildAvl(Node)) != NULL)) Node = Child;
/* Now loop the Vad nodes */ while (Node) { /* Calculate the lower margin */ LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
/* Check if the current bounds are suitable */ if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount)) { /* There is enough space to add our node */ LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, AlignmentVpn); *Base = LowVpn << PAGE_SHIFT;
/* Can we use the current node as parent? */ if (!RtlRightChildAvl(Node)) { /* Node has no right child, so use it as parent */ *Parent = Node; return TableInsertAsRight; } else { /* Node has a right child. This means we must have already moved one node left from the right-most node we started with, thus we already have an OldNode! */ ASSERT(OldNode != NULL);
/* The node we had before is the most left grandchild of that right child, use it as parent. */ ASSERT(RtlLeftChildAvl(OldNode) == NULL); *Parent = OldNode; return TableInsertAsLeft; } }
/* Update the upper margin if necessary */ if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
/* Remember the current node and go to the previous node */ OldNode = Node; Node = MiGetPreviousNode(Node); }
/* Check if there's enough space before the lowest Vad */ LowVpn = ALIGN_UP_BY((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) / PAGE_SIZE; if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount)) { /* There is enough space to add our address */ LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT); *Base = LowVpn << PAGE_SHIFT; *Parent = OldNode; return TableInsertAsLeft; }
/* No address space left at all */ *Base = 0; *Parent = NULL; return TableFoundNode;}
NTSTATUSNTAPIMiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length, IN ULONG_PTR BoundaryAddress, IN ULONG_PTR Alignment, IN PMM_AVL_TABLE Table, OUT PULONG_PTR Base){ PMMADDRESS_NODE Node, LowestNode; ULONG_PTR LowVpn, BestVpn;
ASSERT_LOCKED_FOR_READ(Table);
/* Sanity checks */ ASSERT(Table == &MmSectionBasedRoot); ASSERT(BoundaryAddress); ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
/* Compute page length, make sure the boundary address is valid */ Length = ROUND_TO_PAGES(Length); if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
/* Check if the table is empty */ BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment); if (Table->NumberGenericTableElements == 0) { /* Tree is empty, the candidate address is already the best one */ *Base = BestVpn; return STATUS_SUCCESS; }
/* Go to the right-most node which should be the biggest address */ Node = Table->BalancedRoot.RightChild; while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
/* Check if we can fit in here */ LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment); if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn))) {#if (NTDDI_VERSION >= NTDDI_VISTA) /* Return the address. */ *Base = BestVpn;#else /* Note: this is a compatibility hack that mimics a bug in the 2k3 kernel. It will can waste up to Alignment bytes of memory above the allocation. This bug was fixed in Windows Vista */ *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment);#endif return STATUS_SUCCESS; }
/* Now loop the Vad nodes */ do { /* Break out if we've reached the last node */ LowestNode = MiGetPreviousNode(Node); if (!LowestNode) break;
/* Check if this node could contain the requested address */ LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment); if ((LowestNode->EndingVpn < BestVpn) && (LowVpn < Node->StartingVpn) && (Length <= (Node->StartingVpn - LowVpn))) { /* Check if we need to take BoundaryAddress into account */ if (BoundaryAddress < Node->StartingVpn) { /* Return the optimal VPN address */ *Base = BestVpn; return STATUS_SUCCESS; } else { /* The upper margin is given by the Node's starting address */ *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment); return STATUS_SUCCESS; } }
/* Move to the next node */ Node = LowestNode; } while (TRUE);
/* Check if there's enough space before the lowest Vad */ if ((Node->StartingVpn > (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) && ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length)) { /* Check if it fits in perfectly */ if (BoundaryAddress < Node->StartingVpn) { /* Return the optimal VPN address */ *Base = BestVpn; return STATUS_SUCCESS; }
/* Return an aligned base address within this node */ *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment); return STATUS_SUCCESS; }
/* No address space left at all */ return STATUS_NO_MEMORY;}
NTSTATUSNTAPIMiCheckSecuredVad(IN PMMVAD Vad, IN PVOID Base, IN SIZE_T Size, IN ULONG ProtectionMask){ ULONG_PTR StartAddress, EndAddress;
/* Compute start and end address */ StartAddress = (ULONG_PTR)Base; EndAddress = StartAddress + Size - 1;
/* Are we deleting/unmapping, or changing? */ if (ProtectionMask < MM_DELETE_CHECK) { /* Changing... are we allowed to do so? */ if ((Vad->u.VadFlags.NoChange == 1) && (Vad->u2.VadFlags2.SecNoChange == 1) && (Vad->u.VadFlags.Protection != ProtectionMask)) { /* Nope, bail out */ DPRINT1("Trying to mess with a no-change VAD!\n"); return STATUS_INVALID_PAGE_PROTECTION; } } else { /* This is allowed */ ProtectionMask = 0; }
/* ARM3 doesn't support this yet */ ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0);
/* Is this a one-secured VAD, like a TEB or PEB? */ if (Vad->u2.VadFlags2.OneSecured) { /* Is this allocation being described by the VAD? */ if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) && (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn)) { /* Guard page? */ if (ProtectionMask & MM_DECOMMIT) { DPRINT1("Not allowed to change protection on guard page!\n"); return STATUS_INVALID_PAGE_PROTECTION; }
/* ARM3 doesn't have read-only VADs yet */ ASSERT(Vad->u2.VadFlags2.ReadOnly == 0);
/* Check if read-write protections are allowed */ if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED) { DPRINT1("Invalid protection mask for RW access!\n"); return STATUS_INVALID_PAGE_PROTECTION; } } }
/* All good, allow the change */ return STATUS_SUCCESS;}
/* EOF */