1512 lines
38 KiB
C
1512 lines
38 KiB
C
/*++
|
|
|
|
Copyright (c) 1989 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
wstree.c
|
|
|
|
Abstract:
|
|
|
|
This module contains the routines which manipulate the working
|
|
set list tree.
|
|
|
|
Author:
|
|
|
|
Lou Perazzoli (loup) 15-May-1989
|
|
|
|
Revision History:
|
|
|
|
--*/
|
|
|
|
#include "mi.h"
|
|
|
|
#if (_MSC_VER >= 800)
|
|
#pragma warning(disable:4010) /* Allow pretty pictures without the noise */
|
|
#endif
|
|
|
|
extern ULONG MmSystemCodePage;
|
|
extern ULONG MmSystemCachePage;
|
|
extern ULONG MmPagedPoolPage;
|
|
extern ULONG MmSystemDriverPage;
|
|
|
|
#if DBG
|
|
ULONG MmNumberOfInserts;
|
|
#endif
|
|
|
|
ULONG
|
|
MiLookupWsleHashIndex (
|
|
IN ULONG_PTR WsleEntry,
|
|
IN PMMWSL WorkingSetList
|
|
);
|
|
|
|
VOID
|
|
MiCheckWsleHash (
|
|
IN PMMWSL WorkingSetList
|
|
);
|
|
|
|
|
|
VOID
|
|
FASTCALL
|
|
MiInsertWsle (
|
|
IN WSLE_NUMBER Entry,
|
|
IN PMMWSL WorkingSetList
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine inserts a Working Set List Entry (WSLE) into the
|
|
working set.
|
|
|
|
Arguments:
|
|
|
|
Entry - The index number of the WSLE to insert.
|
|
|
|
WorkingSetList - Supplies the working set list to insert into.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, APCs disabled, Working Set Mutex held.
|
|
|
|
--*/
|
|
|
|
{
|
|
PVOID VirtualAddress;
|
|
PMMWSLE Wsle;
|
|
PMMSUPPORT WsInfo;
|
|
WSLE_NUMBER Hash;
|
|
PMMWSLE_HASH Table;
|
|
WSLE_NUMBER j;
|
|
PMMPTE PointerPte;
|
|
WSLE_NUMBER Index;
|
|
LARGE_INTEGER TickCount;
|
|
ULONG Size;
|
|
#if defined(_ALPHA_) && !defined(_AXP64_)
|
|
KIRQL OldIrql;
|
|
#endif
|
|
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
VirtualAddress = PAGE_ALIGN(Wsle[Entry].u1.VirtualAddress);
|
|
|
|
#if DBG
|
|
if (MmDebug & MM_DBG_PTE_UPDATE) {
|
|
DbgPrint("inserting element %lx %lx\n", Entry, Wsle[Entry].u1.Long);
|
|
}
|
|
|
|
ASSERT (Wsle[Entry].u1.e1.Valid == 1);
|
|
ASSERT (Wsle[Entry].u1.e1.Direct != 1);
|
|
#endif //DBG
|
|
|
|
WorkingSetList->NonDirectCount += 1;
|
|
|
|
if ((Table = WorkingSetList->HashTable) == NULL) {
|
|
return;
|
|
}
|
|
|
|
#if DBG
|
|
MmNumberOfInserts += 1;
|
|
#endif //DBG
|
|
|
|
Hash = MI_WSLE_HASH(Wsle[Entry].u1.Long, WorkingSetList);
|
|
|
|
|
|
// Check hash table size and see if there is enough room to
|
|
// hash or if the table should be grown.
|
|
|
|
|
|
if ((WorkingSetList->NonDirectCount + 10 +
|
|
(WorkingSetList->HashTableSize >> 4)) >
|
|
WorkingSetList->HashTableSize) {
|
|
|
|
if (WorkingSetList == MmWorkingSetList) {
|
|
WsInfo = &PsGetCurrentProcess()->Vm;
|
|
ASSERT (WsInfo->u.Flags.SessionSpace == 0);
|
|
}
|
|
else if (WorkingSetList == MmSystemCacheWorkingSetList) {
|
|
WsInfo = &MmSystemCacheWs;
|
|
ASSERT (WsInfo->u.Flags.SessionSpace == 0);
|
|
}
|
|
else {
|
|
WsInfo = &MmSessionSpace->Vm;
|
|
ASSERT (WsInfo->u.Flags.SessionSpace == 1);
|
|
}
|
|
|
|
if ((Table + WorkingSetList->HashTableSize + ((2*PAGE_SIZE) / sizeof (MMWSLE_HASH)) <= (PMMWSLE_HASH)WorkingSetList->HighestPermittedHashAddress) &&
|
|
(WsInfo->AllowWorkingSetAdjustment)) {
|
|
|
|
#if defined(_ALPHA_) && !defined(_AXP64_)
|
|
LOCK_EXPANSION_IF_ALPHA (OldIrql);
|
|
#endif
|
|
WsInfo->AllowWorkingSetAdjustment = MM_GROW_WSLE_HASH;
|
|
#if defined(_ALPHA_) && !defined(_AXP64_)
|
|
UNLOCK_EXPANSION_IF_ALPHA (OldIrql);
|
|
#endif
|
|
}
|
|
|
|
if ((WorkingSetList->NonDirectCount +
|
|
(WorkingSetList->HashTableSize >> 4)) >
|
|
WorkingSetList->HashTableSize) {
|
|
|
|
|
|
// No more room in the hash table, remove one and add there.
|
|
// Pick a victim within 16 of where this would hash to.
|
|
|
|
|
|
KeQueryTickCount(&TickCount);
|
|
j = Hash + (TickCount.LowPart & 0xF);
|
|
|
|
Size = WorkingSetList->HashTableSize;
|
|
|
|
if (j >= Size) {
|
|
j = TickCount.LowPart & 0xF;
|
|
}
|
|
|
|
do {
|
|
if (Table[j].Key != 0) {
|
|
PERFINFO_PAGE_INFO_DECL();
|
|
|
|
PointerPte = MiGetPteAddress (Table[j].Key);
|
|
Index = WorkingSetList->HashTable[j].Index;
|
|
ASSERT (Wsle[Index].u1.e1.Valid == 1);
|
|
PointerPte = MiGetPteAddress (Wsle[Index].u1.VirtualAddress);
|
|
|
|
PERFINFO_GET_PAGE_INFO(PointerPte);
|
|
if (MiFreeWsle (Index, WsInfo, PointerPte)) {
|
|
PERFINFO_LOG_WS_REMOVAL(PERFINFO_LOG_TYPE_OUTWS_HASHFULL, WsInfo);
|
|
break;
|
|
}
|
|
}
|
|
j += 1;
|
|
if (j >= Size) {
|
|
j = 0;
|
|
}
|
|
} while (TRUE);
|
|
}
|
|
}
|
|
|
|
|
|
// Add to the hash table.
|
|
|
|
|
|
while (Table[Hash].Key != 0) {
|
|
Hash += 1;
|
|
if (Hash >= WorkingSetList->HashTableSize) {
|
|
Hash = 0;
|
|
}
|
|
}
|
|
|
|
Table[Hash].Key = Wsle[Entry].u1.Long & ~(PAGE_SIZE - 1);
|
|
Table[Hash].Index = Entry;
|
|
|
|
#if DBG
|
|
if ((MmNumberOfInserts % 1000) == 0) {
|
|
MiCheckWsleHash (WorkingSetList);
|
|
}
|
|
#endif //DBG
|
|
return;
|
|
}
|
|
|
|
#if DBG
|
|
VOID
|
|
MiCheckWsleHash (
|
|
IN PMMWSL WorkingSetList
|
|
)
|
|
|
|
{
|
|
ULONG j;
|
|
ULONG found = 0;
|
|
PMMWSLE Wsle;
|
|
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
for (j =0; j < WorkingSetList->HashTableSize ; j++ ) {
|
|
if (WorkingSetList->HashTable[j].Key != 0) {
|
|
found += 1;
|
|
ASSERT (WorkingSetList->HashTable[j].Key ==
|
|
(Wsle[WorkingSetList->HashTable[j].Index].u1.Long &
|
|
~(PAGE_SIZE -1)));
|
|
}
|
|
}
|
|
if (found != WorkingSetList->NonDirectCount) {
|
|
DbgPrint("MMWSLE: Found %lx, nondirect %lx\n",
|
|
found, WorkingSetList->NonDirectCount);
|
|
DbgBreakPoint();
|
|
}
|
|
}
|
|
#endif //dbg
|
|
|
|
|
|
WSLE_NUMBER
|
|
FASTCALL
|
|
MiLocateWsle (
|
|
IN PVOID VirtualAddress,
|
|
IN PMMWSL WorkingSetList,
|
|
IN WSLE_NUMBER WsPfnIndex
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This function locates the specified virtual address within the
|
|
working set list.
|
|
|
|
Arguments:
|
|
|
|
VirtualAddress - Supplies the virtual to locate within the working
|
|
set list.
|
|
|
|
WorkingSetList - Supplies the working set list to search.
|
|
|
|
WsPfnIndex - Supplies a hint to try before hashing or walking linearly.
|
|
|
|
Return Value:
|
|
|
|
Returns the index into the working set list which contains the entry.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, APCs disabled, Working Set Mutex held.
|
|
|
|
--*/
|
|
|
|
{
|
|
WSLE_NUMBER i;
|
|
PMMWSLE Wsle;
|
|
ULONG Hash;
|
|
PMMWSLE_HASH Table;
|
|
ULONG Tries;
|
|
WSLE_NUMBER WsPteIndex;
|
|
PMMPTE PointerPte;
|
|
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
VirtualAddress = PAGE_ALIGN(VirtualAddress);
|
|
|
|
#if defined (_WIN64)
|
|
PointerPte = MiGetPteAddress (VirtualAddress);
|
|
WsPteIndex = MI_GET_WORKING_SET_FROM_PTE (PointerPte);
|
|
if (WsPteIndex != 0) {
|
|
while (WsPteIndex <= WorkingSetList->LastInitializedWsle) {
|
|
if ((VirtualAddress == PAGE_ALIGN(Wsle[WsPteIndex].u1.VirtualAddress)) &&
|
|
(Wsle[WsPteIndex].u1.e1.Valid == 1)) {
|
|
return WsPteIndex;
|
|
}
|
|
WsPteIndex += MI_MAXIMUM_PTE_WORKING_SET_INDEX;
|
|
}
|
|
|
|
|
|
// No working set index for this PTE !
|
|
|
|
|
|
KeBugCheckEx (MEMORY_MANAGEMENT,
|
|
0x41283,
|
|
(ULONG_PTR)VirtualAddress,
|
|
PointerPte->u.Long,
|
|
(ULONG_PTR)WorkingSetList);
|
|
}
|
|
#endif
|
|
|
|
if (WsPfnIndex <= WorkingSetList->LastInitializedWsle) {
|
|
if ((VirtualAddress == PAGE_ALIGN(Wsle[WsPfnIndex].u1.VirtualAddress)) &&
|
|
(Wsle[WsPfnIndex].u1.e1.Valid == 1)) {
|
|
return WsPfnIndex;
|
|
}
|
|
}
|
|
|
|
if (WorkingSetList->HashTable) {
|
|
Tries = 0;
|
|
Table = WorkingSetList->HashTable;
|
|
|
|
Hash = MI_WSLE_HASH(VirtualAddress, WorkingSetList);
|
|
|
|
while (Table[Hash].Key != (ULONG_PTR)VirtualAddress) {
|
|
Hash += 1;
|
|
if (Hash >= WorkingSetList->HashTableSize) {
|
|
Hash = 0;
|
|
if (Tries != 0) {
|
|
KeBugCheckEx (MEMORY_MANAGEMENT,
|
|
0x41284,
|
|
(ULONG_PTR)VirtualAddress,
|
|
WsPfnIndex,
|
|
(ULONG_PTR)WorkingSetList);
|
|
}
|
|
Tries = 1;
|
|
}
|
|
}
|
|
ASSERT (WorkingSetList->Wsle[Table[Hash].Index].u1.e1.Direct == 0);
|
|
return Table[Hash].Index;
|
|
}
|
|
|
|
i = 0;
|
|
|
|
for (; ; ) {
|
|
if ((VirtualAddress == PAGE_ALIGN(Wsle[i].u1.VirtualAddress)) &&
|
|
(Wsle[i].u1.e1.Valid == 1)) {
|
|
ASSERT (WorkingSetList->Wsle[i].u1.e1.Direct == 0);
|
|
return i;
|
|
}
|
|
i += 1;
|
|
}
|
|
}
|
|
|
|
|
|
#if 0
|
|
|
|
ULONG
|
|
MiLocateWsleAndParent (
|
|
IN PVOID VirtualAddress,
|
|
OUT PULONG Parent,
|
|
IN PMMWSL WorkingSetList,
|
|
IN ULONG WsPfnIndex
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine locates both the working set list entry (via index) and
|
|
it's parent.
|
|
|
|
Arguments:
|
|
|
|
VirtualAddress - Supplies the virtual address of the WSLE to locate.
|
|
|
|
Parent - Returns the index into the working set list for the parent.
|
|
|
|
WorkingSetList - Supplies a pointer to the working set list.
|
|
|
|
WsPfnIndex - Supplies the index field from the PFN database for
|
|
the physical page that maps the specified virtual address.
|
|
|
|
Return Value:
|
|
|
|
Returns the index of the virtual address in the working set list.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, APCs disabled, Working Set Mutex held.
|
|
|
|
--*/
|
|
|
|
{
|
|
ULONG Previous;
|
|
ULONG Entry;
|
|
PMMWSLE Wsle;
|
|
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
|
|
// Check to see if the PfnIndex field refers to the WSLE in question.
|
|
// Make sure the index is within the specified working set list.
|
|
|
|
|
|
if (WsPfnIndex <= WorkingSetList->LastInitializedWsle) {
|
|
if (VirtualAddress == PAGE_ALIGN(Wsle[WsPfnIndex].u1.VirtualAddress)) {
|
|
|
|
|
|
// The index field points to the WSLE, however, this could
|
|
// have been just a coincidence, so check to ensure it
|
|
// really doesn't have a parent.
|
|
|
|
|
|
if (Wsle[WsPfnIndex].u2.BothPointers == 0) {
|
|
|
|
|
|
// Not in tree, therefore has no parent.
|
|
|
|
|
|
*Parent = WSLE_NULL_INDEX;
|
|
return WsPfnIndex;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// Search the tree for the entry remembering the parents.
|
|
|
|
|
|
Entry = WorkingSetList->Root;
|
|
Previous = Entry;
|
|
|
|
for (;;) {
|
|
|
|
ASSERT (Entry != WSLE_NULL_INDEX);
|
|
|
|
if (VirtualAddress == PAGE_ALIGN(Wsle[Entry].u1.VirtualAddress)) {
|
|
break;
|
|
}
|
|
|
|
if (VirtualAddress < PAGE_ALIGN(Wsle[Entry].u1.VirtualAddress)) {
|
|
Previous = Entry;
|
|
Entry = Wsle[Entry].u2.s.LeftChild;
|
|
} else {
|
|
Previous = Entry;
|
|
Entry = Wsle[Entry].u2.s.RightChild;
|
|
}
|
|
}
|
|
|
|
*Parent = Previous;
|
|
return Entry;
|
|
}
|
|
#endif //0
|
|
|
|
|
|
VOID
|
|
FASTCALL
|
|
MiRemoveWsle (
|
|
IN WSLE_NUMBER Entry,
|
|
IN PMMWSL WorkingSetList
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine removes a Working Set List Entry (WSLE) from the
|
|
working set.
|
|
|
|
Arguments:
|
|
|
|
Entry - The index number of the WSLE to remove.
|
|
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, APCs disabled, Working Set Mutex held.
|
|
|
|
--*/
|
|
{
|
|
PMMWSLE Wsle;
|
|
PVOID VirtualAddress;
|
|
PMMWSLE_HASH Table;
|
|
ULONG Hash;
|
|
ULONG Tries;
|
|
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
|
|
// Locate the entry in the tree.
|
|
|
|
|
|
#if DBG
|
|
if (MmDebug & MM_DBG_PTE_UPDATE) {
|
|
DbgPrint("removing wsle %lx %lx\n",
|
|
Entry, Wsle[Entry].u1.Long);
|
|
}
|
|
if (MmDebug & MM_DBG_DUMP_WSL) {
|
|
MiDumpWsl();
|
|
DbgPrint(" \n");
|
|
}
|
|
|
|
#endif //DBG
|
|
|
|
ASSERT (Wsle[Entry].u1.e1.Valid == 1);
|
|
|
|
VirtualAddress = PAGE_ALIGN (Wsle[Entry].u1.VirtualAddress);
|
|
|
|
if (WorkingSetList == MmSystemCacheWorkingSetList) {
|
|
|
|
|
|
// count system space inserts and removals.
|
|
|
|
|
|
#if defined(_X86_)
|
|
if (MI_IS_SYSTEM_CACHE_ADDRESS(VirtualAddress)) {
|
|
MmSystemCachePage -= 1;
|
|
} else
|
|
#endif
|
|
if (VirtualAddress < MmSystemCacheStart) {
|
|
MmSystemCodePage -= 1;
|
|
} else if (VirtualAddress < MM_PAGED_POOL_START) {
|
|
MmSystemCachePage -= 1;
|
|
} else if (VirtualAddress < MmNonPagedSystemStart) {
|
|
MmPagedPoolPage -= 1;
|
|
} else {
|
|
MmSystemDriverPage -= 1;
|
|
}
|
|
}
|
|
|
|
Wsle[Entry].u1.e1.Valid = 0;
|
|
|
|
if (Wsle[Entry].u1.e1.Direct == 0) {
|
|
|
|
WorkingSetList->NonDirectCount -= 1;
|
|
|
|
if (WorkingSetList->HashTable) {
|
|
Hash = MI_WSLE_HASH(Wsle[Entry].u1.Long, WorkingSetList);
|
|
Table = WorkingSetList->HashTable;
|
|
Tries = 0;
|
|
|
|
while (Table[Hash].Key != (ULONG_PTR)VirtualAddress) {
|
|
Hash += 1;
|
|
if (Hash >= WorkingSetList->HashTableSize) {
|
|
Hash = 0;
|
|
if (Tries != 0) {
|
|
KeBugCheckEx (MEMORY_MANAGEMENT,
|
|
0x41784,
|
|
(ULONG_PTR)VirtualAddress,
|
|
Entry,
|
|
(ULONG_PTR)WorkingSetList);
|
|
}
|
|
Tries = 1;
|
|
}
|
|
}
|
|
Table[Hash].Key = 0;
|
|
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
VOID
|
|
MiSwapWslEntries (
|
|
IN WSLE_NUMBER SwapEntry,
|
|
IN WSLE_NUMBER Entry,
|
|
IN PMMSUPPORT WsInfo
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine swaps the working set list entries Entry and SwapEntry
|
|
in the specified working set list (process or system cache).
|
|
|
|
Arguments:
|
|
|
|
SwapEntry - Supplies the first entry to swap. This entry must be
|
|
valid, i.e. in the working set at the current time.
|
|
|
|
Entry - Supplies the other entry to swap. This entry may be valid
|
|
or invalid.
|
|
|
|
WsInfo - Supplies the working set list.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, Working set lock and PFN lock held (if system cache),
|
|
APCs disabled.
|
|
|
|
--*/
|
|
|
|
{
|
|
MMWSLE WsleEntry;
|
|
MMWSLE WsleSwap;
|
|
PMMPTE PointerPte;
|
|
PMMPFN Pfn1;
|
|
PMMWSLE Wsle;
|
|
PMMWSL WorkingSetList;
|
|
PMMWSLE_HASH Table;
|
|
#if DBG
|
|
WSLE_NUMBER CurrentSize = WsInfo->WorkingSetSize;
|
|
#endif //DBG
|
|
#if PFN_CONSISTENCY
|
|
KIRQL OldIrql;
|
|
#endif
|
|
|
|
WorkingSetList = WsInfo->VmWorkingSetList;
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
WsleSwap = Wsle[SwapEntry];
|
|
|
|
ASSERT (WsleSwap.u1.e1.Valid != 0);
|
|
|
|
WsleEntry = Wsle[Entry];
|
|
|
|
Table = WorkingSetList->HashTable;
|
|
|
|
if (WsleEntry.u1.e1.Valid == 0) {
|
|
|
|
|
|
// Entry is not on any list. Remove it from the free list.
|
|
|
|
|
|
MiRemoveWsleFromFreeList (Entry, Wsle, WorkingSetList);
|
|
|
|
|
|
// Copy the Entry to this free one.
|
|
|
|
|
|
Wsle[Entry] = WsleSwap;
|
|
|
|
PointerPte = MiGetPteAddress (WsleSwap.u1.VirtualAddress);
|
|
|
|
if (WsleSwap.u1.e1.Direct) {
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
#if PFN_CONSISTENCY
|
|
OldIrql = 99;
|
|
if (PFN_LOCK_OWNED_BY_ME() == 0) {
|
|
LOCK_PFN (OldIrql);
|
|
}
|
|
#endif
|
|
Pfn1->u1.WsIndex = Entry;
|
|
#if PFN_CONSISTENCY
|
|
if (OldIrql != 99) {
|
|
UNLOCK_PFN (OldIrql);
|
|
}
|
|
#endif
|
|
} else {
|
|
|
|
|
|
// Update hash table.
|
|
|
|
|
|
if (Table) {
|
|
Table [ MiLookupWsleHashIndex (WsleSwap.u1.Long,
|
|
WorkingSetList)].Index = Entry;
|
|
}
|
|
}
|
|
|
|
MI_SET_PTE_IN_WORKING_SET (PointerPte, Entry);
|
|
|
|
|
|
// Put entry on free list.
|
|
|
|
|
|
ASSERT (WorkingSetList->FirstFree <= WorkingSetList->LastInitializedWsle);
|
|
Wsle[SwapEntry].u1.Long = WorkingSetList->FirstFree << MM_FREE_WSLE_SHIFT;
|
|
WorkingSetList->FirstFree = SwapEntry;
|
|
ASSERT ((WorkingSetList->FirstFree <= WorkingSetList->LastInitializedWsle) ||
|
|
(WorkingSetList->FirstFree == WSLE_NULL_INDEX));
|
|
|
|
} else {
|
|
|
|
|
|
// Both entries are valid.
|
|
|
|
|
|
Wsle[SwapEntry] = WsleEntry;
|
|
|
|
PointerPte = MiGetPteAddress (WsleEntry.u1.VirtualAddress);
|
|
|
|
if (WsleEntry.u1.e1.Direct) {
|
|
|
|
|
|
// Swap the PFN WsIndex element to point to the new slot.
|
|
|
|
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
#if PFN_CONSISTENCY
|
|
OldIrql = 99;
|
|
if (PFN_LOCK_OWNED_BY_ME() == 0) {
|
|
LOCK_PFN (OldIrql);
|
|
}
|
|
#endif
|
|
Pfn1->u1.WsIndex = SwapEntry;
|
|
#if PFN_CONSISTENCY
|
|
if (OldIrql != 99) {
|
|
UNLOCK_PFN (OldIrql);
|
|
}
|
|
#endif
|
|
} else {
|
|
|
|
|
|
// Update hash table.
|
|
|
|
|
|
if (Table) {
|
|
Table[ MiLookupWsleHashIndex (WsleEntry.u1.Long,
|
|
WorkingSetList)].Index = SwapEntry;
|
|
}
|
|
}
|
|
|
|
MI_SET_PTE_IN_WORKING_SET (PointerPte, SwapEntry);
|
|
|
|
Wsle[Entry] = WsleSwap;
|
|
|
|
PointerPte = MiGetPteAddress (WsleSwap.u1.VirtualAddress);
|
|
|
|
if (WsleSwap.u1.e1.Direct) {
|
|
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
#if PFN_CONSISTENCY
|
|
OldIrql = 99;
|
|
if (PFN_LOCK_OWNED_BY_ME() == 0) {
|
|
LOCK_PFN (OldIrql);
|
|
}
|
|
#endif
|
|
Pfn1->u1.WsIndex = Entry;
|
|
#if PFN_CONSISTENCY
|
|
if (OldIrql != 99) {
|
|
UNLOCK_PFN (OldIrql);
|
|
}
|
|
#endif
|
|
} else {
|
|
if (Table) {
|
|
Table[ MiLookupWsleHashIndex (WsleSwap.u1.Long,
|
|
WorkingSetList)].Index = Entry;
|
|
}
|
|
}
|
|
MI_SET_PTE_IN_WORKING_SET (PointerPte, Entry);
|
|
}
|
|
ASSERT (CurrentSize == WsInfo->WorkingSetSize);
|
|
return;
|
|
}
|
|
|
|
ULONG
|
|
MiLookupWsleHashIndex (
|
|
IN ULONG_PTR WsleEntry,
|
|
IN PMMWSL WorkingSetList
|
|
)
|
|
|
|
{
|
|
ULONG Hash;
|
|
ULONG_PTR VirtualAddress;
|
|
PMMWSLE_HASH Table;
|
|
ULONG Tries = 0;
|
|
|
|
Table = WorkingSetList->HashTable;
|
|
VirtualAddress = WsleEntry & ~(PAGE_SIZE - 1);
|
|
|
|
Hash = MI_WSLE_HASH(WsleEntry, WorkingSetList);
|
|
|
|
while (Table[Hash].Key != (ULONG_PTR)VirtualAddress) {
|
|
Hash += 1;
|
|
if (Hash >= WorkingSetList->HashTableSize) {
|
|
Hash = 0;
|
|
if (Tries != 0) {
|
|
KeBugCheckEx (MEMORY_MANAGEMENT,
|
|
0x41884,
|
|
(ULONG_PTR)VirtualAddress,
|
|
WsleEntry,
|
|
(ULONG_PTR)WorkingSetList);
|
|
}
|
|
Tries = 1;
|
|
}
|
|
}
|
|
return Hash;
|
|
}
|
|
|
|
VOID
|
|
MiRemoveWsleFromFreeList (
|
|
IN ULONG Entry,
|
|
IN PMMWSLE Wsle,
|
|
IN PMMWSL WorkingSetList
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine removes a working set list entry from the free list.
|
|
It is used when the entry required is not the first element
|
|
in the free list.
|
|
|
|
Arguments:
|
|
|
|
Entry - Supplies the index of the entry to remove.
|
|
|
|
Wsle - Supplies a pointer to the array of WSLEs.
|
|
|
|
WorkingSetList - Supplies a pointer to the working set list.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, Working set lock and PFN lock held, APCs disabled.
|
|
|
|
--*/
|
|
|
|
{
|
|
WSLE_NUMBER Free;
|
|
WSLE_NUMBER ParentFree;
|
|
|
|
Free = WorkingSetList->FirstFree;
|
|
|
|
if (Entry == Free) {
|
|
ASSERT ((Wsle[Entry].u1.Long >> MM_FREE_WSLE_SHIFT) <= WorkingSetList->LastInitializedWsle);
|
|
WorkingSetList->FirstFree = (WSLE_NUMBER)(Wsle[Entry].u1.Long >> MM_FREE_WSLE_SHIFT);
|
|
|
|
} else {
|
|
do {
|
|
ParentFree = Free;
|
|
ASSERT (Wsle[Free].u1.e1.Valid == 0);
|
|
Free = (WSLE_NUMBER)(Wsle[Free].u1.Long >> MM_FREE_WSLE_SHIFT);
|
|
} while (Free != Entry);
|
|
|
|
Wsle[ParentFree].u1.Long = Wsle[Entry].u1.Long;
|
|
}
|
|
ASSERT ((WorkingSetList->FirstFree <= WorkingSetList->LastInitializedWsle) ||
|
|
(WorkingSetList->FirstFree == WSLE_NULL_INDEX));
|
|
return;
|
|
}
|
|
|
|
|
|
#if 0
|
|
|
|
VOID
|
|
MiSwapWslEntries (
|
|
IN ULONG Entry,
|
|
IN ULONG Parent,
|
|
IN ULONG SwapEntry,
|
|
IN PMMWSL WorkingSetList
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This function swaps the specified entry and updates its parent with
|
|
the specified swap entry.
|
|
|
|
The entry must be valid, i.e., the page is resident. The swap entry
|
|
can be valid or on the free list.
|
|
|
|
Arguments:
|
|
|
|
Entry - The index of the WSLE to swap.
|
|
|
|
Parent - The index of the parent of the WSLE to swap.
|
|
|
|
SwapEntry - The index to swap the entry with.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
Environment:
|
|
|
|
Kernel mode, working set mutex held, APCs disabled.
|
|
|
|
--*/
|
|
|
|
{
|
|
|
|
ULONG SwapParent;
|
|
ULONG SavedRight;
|
|
ULONG SavedLeft;
|
|
ULONG Free;
|
|
ULONG ParentFree;
|
|
ULONG SavedLong;
|
|
PVOID VirtualAddress;
|
|
PMMWSLE Wsle;
|
|
PMMPFN Pfn1;
|
|
PMMPTE PointerPte;
|
|
|
|
Wsle = WorkingSetList->Wsle;
|
|
|
|
if (Wsle[SwapEntry].u1.e1.Valid == 0) {
|
|
|
|
|
|
// This entry is not in use and must be removed from
|
|
// the free list.
|
|
|
|
|
|
Free = WorkingSetList->FirstFree;
|
|
|
|
if (SwapEntry == Free) {
|
|
WorkingSetList->FirstFree = Entry;
|
|
ASSERT ((WorkingSetList->FirstFree <= WorkingSetList->LastInitializedWsle) ||
|
|
(WorkingSetList->FirstFree == WSLE_NULL_INDEX));
|
|
|
|
} else {
|
|
|
|
while (Free != SwapEntry) {
|
|
ParentFree = Free;
|
|
Free = Wsle[Free].u2.s.LeftChild;
|
|
}
|
|
|
|
Wsle[ParentFree].u2.s.LeftChild = Entry;
|
|
}
|
|
|
|
|
|
// Swap the previous entry and the new unused entry.
|
|
|
|
|
|
SavedLeft = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = SavedLeft;
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u1.Long = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = 0;
|
|
|
|
|
|
// Make the parent point to the new entry.
|
|
|
|
|
|
if (Parent == WSLE_NULL_INDEX) {
|
|
|
|
|
|
// This entry is not in the tree.
|
|
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[SwapEntry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
Pfn1->u1.WsIndex = SwapEntry;
|
|
return;
|
|
}
|
|
|
|
if (Parent == Entry) {
|
|
|
|
|
|
// This element is the root, update the root pointer.
|
|
|
|
|
|
WorkingSetList->Root = SwapEntry;
|
|
|
|
} else {
|
|
|
|
if (Wsle[Parent].u2.s.LeftChild == Entry) {
|
|
Wsle[Parent].u2.s.LeftChild = SwapEntry;
|
|
} else {
|
|
ASSERT (Wsle[Parent].u2.s.RightChild == Entry);
|
|
|
|
Wsle[Parent].u2.s.RightChild = SwapEntry;
|
|
}
|
|
}
|
|
|
|
} else {
|
|
|
|
if ((Parent == WSLE_NULL_INDEX) &&
|
|
(Wsle[SwapEntry].u2.BothPointers == 0)) {
|
|
|
|
|
|
// Neither entry is in the tree, just swap their pointers.
|
|
|
|
|
|
SavedLong = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = SavedLong;
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[Entry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
Pfn1->u1.WsIndex = Entry;
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[SwapEntry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
Pfn1->u1.WsIndex = SwapEntry;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
// The entry at FirstDynamic is valid; swap it with this one and
|
|
// update both parents.
|
|
|
|
|
|
SwapParent = WorkingSetList->Root;
|
|
|
|
if (SwapParent == SwapEntry) {
|
|
|
|
|
|
// The entry we are swapping with is at the root.
|
|
|
|
|
|
if (Wsle[SwapEntry].u2.s.LeftChild == Entry) {
|
|
|
|
|
|
// The entry we are going to swap is the left child of this
|
|
// entry.
|
|
|
|
// R(SwapEntry)
|
|
// / \
|
|
// (entry)
|
|
|
|
|
|
WorkingSetList->Root = Entry;
|
|
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SwapEntry;
|
|
SavedRight = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SavedRight;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
|
|
} else {
|
|
|
|
if (Wsle[SwapEntry].u2.s.RightChild == Entry) {
|
|
|
|
|
|
// The entry we are going to swap is the right child of this
|
|
// entry.
|
|
|
|
// R(SwapEntry)
|
|
// / \
|
|
// (entry)
|
|
|
|
|
|
WorkingSetList->Root = Entry;
|
|
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SwapEntry;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
}
|
|
}
|
|
|
|
|
|
// The swap entry is the root, but the other entry is not
|
|
// its child.
|
|
|
|
|
|
// R(SwapEntry)
|
|
// / \
|
|
// .....
|
|
// Parent(Entry)
|
|
// \
|
|
// Entry (left or right)
|
|
|
|
|
|
|
|
WorkingSetList->Root = Entry;
|
|
|
|
SavedRight = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SavedRight;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
if (Parent == WSLE_NULL_INDEX) {
|
|
|
|
|
|
// This entry is not in the tree.
|
|
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[SwapEntry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
Pfn1->u1.WsIndex = SwapEntry;
|
|
return;
|
|
}
|
|
|
|
|
|
// Change the parent of the entry to point to the swap entry.
|
|
|
|
|
|
if (Wsle[Parent].u2.s.RightChild == Entry) {
|
|
Wsle[Parent].u2.s.RightChild = SwapEntry;
|
|
} else {
|
|
Wsle[Parent].u2.s.LeftChild = SwapEntry;
|
|
}
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
// The SwapEntry is not the root, find its parent.
|
|
|
|
|
|
if (Wsle[SwapEntry].u2.BothPointers == 0) {
|
|
|
|
|
|
// Entry is not in tree, therefore no parent.
|
|
|
|
SwapParent = WSLE_NULL_INDEX;
|
|
|
|
} else {
|
|
|
|
VirtualAddress = PAGE_ALIGN(Wsle[SwapEntry].u1.VirtualAddress);
|
|
|
|
for (;;) {
|
|
|
|
ASSERT (SwapParent != WSLE_NULL_INDEX);
|
|
|
|
if (Wsle[SwapParent].u2.s.LeftChild == SwapEntry) {
|
|
break;
|
|
}
|
|
if (Wsle[SwapParent].u2.s.RightChild == SwapEntry) {
|
|
break;
|
|
}
|
|
|
|
|
|
if (VirtualAddress < PAGE_ALIGN(Wsle[SwapParent].u1.VirtualAddress)) {
|
|
SwapParent = Wsle[SwapParent].u2.s.LeftChild;
|
|
} else {
|
|
SwapParent = Wsle[SwapParent].u2.s.RightChild;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (Parent == WorkingSetList->Root) {
|
|
|
|
|
|
// The entry is at the root.
|
|
|
|
|
|
if (Wsle[Entry].u2.s.LeftChild == SwapEntry) {
|
|
|
|
|
|
// The entry we are going to swap is the left child of this
|
|
// entry.
|
|
|
|
// R(Entry)
|
|
// / \
|
|
// (SwapEntry)
|
|
|
|
|
|
WorkingSetList->Root = SwapEntry;
|
|
|
|
Wsle[Entry].u2.s.LeftChild = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Entry;
|
|
SavedRight = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = SavedRight;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
|
|
} else if (Wsle[SwapEntry].u2.s.RightChild == Entry) {
|
|
|
|
|
|
// The entry we are going to swap is the right child of this
|
|
// entry.
|
|
|
|
// R(SwapEntry)
|
|
// / \
|
|
// (entry)
|
|
|
|
|
|
WorkingSetList->Root = Entry;
|
|
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SwapEntry;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
// The swap entry is the root, but the other entry is not
|
|
// its child.
|
|
|
|
|
|
// R(SwapEntry)
|
|
// / \
|
|
// .....
|
|
// Parent(Entry)
|
|
// \
|
|
// Entry (left or right)
|
|
|
|
|
|
|
|
WorkingSetList->Root = Entry;
|
|
|
|
SavedRight = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SavedRight;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
if (SwapParent == WSLE_NULL_INDEX) {
|
|
|
|
|
|
// This entry is not in the tree.
|
|
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[Entry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
ASSERT (Pfn1->u1.WsIndex == SwapEntry);
|
|
Pfn1->u1.WsIndex = Entry;
|
|
return;
|
|
}
|
|
|
|
|
|
// Change the parent of the entry to point to the swap entry.
|
|
|
|
|
|
if (Wsle[SwapParent].u2.s.RightChild == SwapEntry) {
|
|
Wsle[SwapParent].u2.s.RightChild = Entry;
|
|
} else {
|
|
Wsle[SwapParent].u2.s.LeftChild = Entry;
|
|
}
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
// Neither entry is the root.
|
|
|
|
|
|
if (Parent == SwapEntry) {
|
|
|
|
|
|
// The parent of the entry is the swap entry.
|
|
|
|
|
|
// R
|
|
// .....
|
|
|
|
// (SwapParent)
|
|
// |
|
|
// (SwapEntry)
|
|
// |
|
|
// (Entry)
|
|
|
|
|
|
|
|
// Update the parent pointer for the swapentry.
|
|
|
|
|
|
if (Wsle[SwapParent].u2.s.LeftChild == SwapEntry) {
|
|
Wsle[SwapParent].u2.s.LeftChild = Entry;
|
|
} else {
|
|
Wsle[SwapParent].u2.s.RightChild = Entry;
|
|
}
|
|
|
|
|
|
// Determine if this goes left or right.
|
|
|
|
|
|
if (Wsle[SwapEntry].u2.s.LeftChild == Entry) {
|
|
|
|
|
|
// The entry we are going to swap is the left child of this
|
|
// entry.
|
|
|
|
// R
|
|
// .....
|
|
|
|
// (SwapParent)
|
|
|
|
// (SwapEntry) [Parent(entry)]
|
|
// / \
|
|
// (entry)
|
|
|
|
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SwapEntry;
|
|
SavedRight = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SavedRight;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
|
|
} else {
|
|
|
|
ASSERT (Wsle[SwapEntry].u2.s.RightChild == Entry);
|
|
|
|
|
|
// The entry we are going to swap is the right child of this
|
|
// entry.
|
|
|
|
// R
|
|
// .....
|
|
|
|
// (SwapParent)
|
|
// \
|
|
// (SwapEntry)
|
|
// / \
|
|
// (entry)
|
|
|
|
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SwapEntry;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
}
|
|
if (SwapParent == Entry) {
|
|
|
|
|
|
|
|
// The parent of the swap entry is the entry.
|
|
|
|
// R
|
|
// .....
|
|
|
|
// (Parent)
|
|
// |
|
|
// (Entry)
|
|
// |
|
|
// (SwapEntry)
|
|
|
|
|
|
|
|
// Update the parent pointer for the entry.
|
|
|
|
|
|
if (Wsle[Parent].u2.s.LeftChild == Entry) {
|
|
Wsle[Parent].u2.s.LeftChild = SwapEntry;
|
|
} else {
|
|
Wsle[Parent].u2.s.RightChild = SwapEntry;
|
|
}
|
|
|
|
|
|
// Determine if this goes left or right.
|
|
|
|
|
|
if (Wsle[Entry].u2.s.LeftChild == SwapEntry) {
|
|
|
|
|
|
// The entry we are going to swap is the left child of this
|
|
// entry.
|
|
|
|
// R
|
|
// .....
|
|
|
|
// (Parent)
|
|
// |
|
|
// (Entry)
|
|
// /
|
|
// (SwapEntry)
|
|
|
|
|
|
Wsle[Entry].u2.s.LeftChild = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Entry;
|
|
SavedRight = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = SavedRight;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
|
|
} else {
|
|
|
|
ASSERT (Wsle[Entry].u2.s.RightChild == SwapEntry);
|
|
|
|
|
|
// The entry we are going to swap is the right child of this
|
|
// entry.
|
|
|
|
// R(Entry)
|
|
// / \
|
|
// (SwapEntry)
|
|
|
|
|
|
Wsle[Entry].u2.s.RightChild = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = Entry;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
}
|
|
|
|
}
|
|
|
|
|
|
// Neither entry is the parent of the other. Just swap them
|
|
// and update the parent entries.
|
|
|
|
|
|
if (Parent == WSLE_NULL_INDEX) {
|
|
|
|
|
|
// This entry is not in the tree.
|
|
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[Entry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
ASSERT (Pfn1->u1.WsIndex == Entry);
|
|
Pfn1->u1.WsIndex = SwapEntry;
|
|
|
|
} else {
|
|
|
|
if (Wsle[Parent].u2.s.LeftChild == Entry) {
|
|
Wsle[Parent].u2.s.LeftChild = SwapEntry;
|
|
} else {
|
|
Wsle[Parent].u2.s.RightChild = SwapEntry;
|
|
}
|
|
}
|
|
|
|
if (SwapParent == WSLE_NULL_INDEX) {
|
|
|
|
|
|
// This entry is not in the tree.
|
|
|
|
|
|
PointerPte = MiGetPteAddress (Wsle[SwapEntry].u1.VirtualAddress);
|
|
Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
|
|
ASSERT (Pfn1->u1.WsIndex == SwapEntry);
|
|
Pfn1->u1.WsIndex = Entry;
|
|
} else {
|
|
|
|
if (Wsle[SwapParent].u2.s.LeftChild == SwapEntry) {
|
|
Wsle[SwapParent].u2.s.LeftChild = Entry;
|
|
} else {
|
|
Wsle[SwapParent].u2.s.RightChild = Entry;
|
|
}
|
|
}
|
|
|
|
SavedRight = Wsle[SwapEntry].u2.s.RightChild;
|
|
Wsle[SwapEntry].u2.s.RightChild = Wsle[Entry].u2.s.RightChild;
|
|
Wsle[Entry].u2.s.RightChild = SavedRight;
|
|
SavedLeft = Wsle[SwapEntry].u2.s.LeftChild;
|
|
Wsle[SwapEntry].u2.s.LeftChild = Wsle[Entry].u2.s.LeftChild;
|
|
Wsle[Entry].u2.s.LeftChild = SavedLeft;
|
|
|
|
SavedLong = Wsle[Entry].u1.Long;
|
|
Wsle[Entry].u1.Long = Wsle[SwapEntry].u1.Long;
|
|
Wsle[SwapEntry].u1.Long = SavedLong;
|
|
|
|
return;
|
|
}
|
|
}
|
|
#endif //0
|