summaryrefslogtreecommitdiffstats
path: root/private/ntos/mm/wstree.c
diff options
context:
space:
mode:
Diffstat (limited to 'private/ntos/mm/wstree.c')
-rw-r--r--private/ntos/mm/wstree.c1418
1 files changed, 1418 insertions, 0 deletions
diff --git a/private/ntos/mm/wstree.c b/private/ntos/mm/wstree.c
new file mode 100644
index 000000000..231936bee
--- /dev/null
+++ b/private/ntos/mm/wstree.c
@@ -0,0 +1,1418 @@
+/*++
+
+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;
+
+ULONG MmNumberOfInserts;
+
+ULONG
+MiLookupWsleHashIndex (
+ IN ULONG WsleEntry,
+ IN PMMWSL WorkingSetList
+ );
+
+VOID
+MiCheckWsleHash (
+ IN PMMWSL WorkingSetList
+ );
+
+
+VOID
+FASTCALL
+MiInsertWsle (
+ IN ULONG Entry,
+ IN PMMWSL WorkingSetList
+ )
+
+/*++
+
+Routine Description:
+
+ This routine inserts a Working Set List Entry (WSLE) into the
+ working set tree.
+
+Arguments:
+
+ Entry - The index number of the WSLE to insert.
+
+
+Return Value:
+
+ None.
+
+Environment:
+
+ Kernel mode, APC's disabled, Working Set Mutex held.
+
+--*/
+
+{
+ ULONG i;
+ ULONG Parent;
+ PVOID VirtualAddress;
+ PMMWSLE Wsle;
+ PMMSUPPORT WsInfo;
+ ULONG Hash;
+ PMMWSLE_HASH Table;
+ ULONG j;
+ PMMPTE PointerPte;
+ ULONG Index;
+ LARGE_INTEGER TickCount;
+ ULONG Size;
+ KIRQL OldIrql;
+
+ 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 = (Wsle[Entry].u1.Long >> (PAGE_SHIFT - 2)) % (WorkingSetList->HashTableSize - 1);
+
+ //
+ // 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 (MmWorkingSetList == WorkingSetList) {
+ WsInfo = &PsGetCurrentProcess()->Vm;
+ } else {
+ WsInfo = &MmSystemCacheWs;
+ }
+
+ if ((WorkingSetList->HashTableSize <
+ (MM_WSLE_MAX_HASH_SIZE - ((2*PAGE_SIZE) / sizeof (MMWSLE_HASH))))
+ &&
+ (WsInfo->AllowWorkingSetAdjustment)) {
+ LOCK_EXPANSION_IF_ALPHA (OldIrql);
+ WsInfo->AllowWorkingSetAdjustment = MM_GROW_WSLE_HASH;
+ UNLOCK_EXPANSION_IF_ALPHA (OldIrql);
+ }
+
+ if ((WorkingSetList->NonDirectCount +
+ (WorkingSetList->HashTableSize >> 4)) >
+ WorkingSetList->HashTableSize) {
+
+ //
+ // No more room in the hash table, remove one and add there.
+ // Pick a victum 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) {
+ PointerPte = MiGetPteAddress (Table[j].Key);
+ Index = WorkingSetList->HashTable[j].Index;
+ ASSERT (Wsle[Index].u1.e1.Valid == 1);
+ PointerPte = MiGetPteAddress (Wsle[Index].u1.VirtualAddress);
+ if (MiFreeWsle (Index, WsInfo, PointerPte)) {
+ 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
+
+
+ULONG
+FASTCALL
+MiLocateWsle (
+ IN PVOID VirtualAddress,
+ IN PMMWSL WorkingSetList,
+ IN ULONG 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.
+
+Return Value:
+
+ Returns the index into the working set list which contains the entry.
+
+Environment:
+
+ Kernel mode, APC's disabled, Working Set Mutex held.
+
+--*/
+
+{
+ ULONG i;
+ PMMWSLE Wsle;
+ ULONG LastWsle;
+ ULONG Hash;
+ PMMWSLE_HASH Table;
+ ULONG Tries;
+
+ Wsle = WorkingSetList->Wsle;
+
+ VirtualAddress = PAGE_ALIGN(VirtualAddress);
+
+ 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 = ((ULONG)VirtualAddress >> (PAGE_SHIFT - 2)) % (WorkingSetList->HashTableSize - 1);
+
+ while (Table[Hash].Key != (ULONG)VirtualAddress) {
+ Hash += 1;
+ if (Hash >= WorkingSetList->HashTableSize) {
+ Hash = 0;
+ if (Tries != 0) {
+ KeBugCheckEx (MEMORY_MANAGEMENT,
+ 0x41284,
+ (ULONG)VirtualAddress,
+ WsPfnIndex,
+ (ULONG)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:
+
+ Retuns the index of the virtual address in the working set list.
+
+Environment:
+
+ Kernel mode, APC's 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 (
+ ULONG Entry,
+ IN PMMWSL WorkingSetList
+ )
+
+/*++
+
+Routine Description:
+
+ This routine removes a Working Set List Entry (WSLE) from the
+ working set tree.
+
+Arguments:
+
+ Entry - The index number of the WSLE to remove.
+
+
+Return Value:
+
+ None.
+
+Environment:
+
+ Kernel mode, APC's disabled, Working Set Mutex held.
+
+--*/
+{
+ ULONG i;
+ ULONG Parent;
+ ULONG Pred;
+ ULONG PredParent;
+ 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 (VirtualAddress < (PVOID)MM_SYSTEM_CACHE_START) {
+ 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 = (Wsle[Entry].u1.Long >> (PAGE_SHIFT - 2)) % (WorkingSetList->HashTableSize - 1);
+ Table = WorkingSetList->HashTable;
+ Tries = 0;
+
+ while (Table[Hash].Key != (ULONG)VirtualAddress) {
+ Hash += 1;
+ if (Hash >= WorkingSetList->HashTableSize) {
+ Hash = 0;
+ if (Tries != 0) {
+ KeBugCheckEx (MEMORY_MANAGEMENT,
+ 0x41784,
+ (ULONG)VirtualAddress,
+ Entry,
+ (ULONG)WorkingSetList);
+ }
+ Tries = 1;
+ }
+ }
+ Table[Hash].Key = 0;
+ }
+ }
+
+ return;
+}
+
+
+VOID
+MiSwapWslEntries (
+ IN ULONG SwapEntry,
+ IN ULONG 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),
+ APC's disabled.
+
+--*/
+
+{
+ MMWSLE WsleEntry;
+ MMWSLE WsleSwap;
+ PMMPTE PointerPte;
+ PMMPFN Pfn1;
+ PMMWSLE Wsle;
+ PMMWSL WorkingSetList;
+ PMMWSLE_HASH Table;
+#if DBG
+ ULONG CurrentSize = WsInfo->WorkingSetSize;
+#endif //DBG
+
+ 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;
+
+ if (WsleSwap.u1.e1.Direct) {
+ PointerPte = MiGetPteAddress (WsleSwap.u1.VirtualAddress);
+ Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
+ Pfn1->u1.WsIndex = Entry;
+ } else {
+
+ //
+ // Update hash table.
+ //
+
+ if (Table) {
+ Table [ MiLookupWsleHashIndex (WsleSwap.u1.Long,
+ WorkingSetList)].Index = 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;
+
+ if (WsleEntry.u1.e1.Direct) {
+
+ //
+ // Swap the PFN WsIndex element to point to the new slot.
+ //
+
+ PointerPte = MiGetPteAddress (WsleEntry.u1.VirtualAddress);
+ Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
+ Pfn1->u1.WsIndex = SwapEntry;
+ } else {
+
+ //
+ // Update hash table.
+ //
+
+ if (Table) {
+ Table[ MiLookupWsleHashIndex (WsleEntry.u1.Long,
+ WorkingSetList)].Index = SwapEntry;
+ }
+ }
+
+ Wsle[Entry] = WsleSwap;
+
+ if (WsleSwap.u1.e1.Direct) {
+
+ PointerPte = MiGetPteAddress (WsleSwap.u1.VirtualAddress);
+ Pfn1 = MI_PFN_ELEMENT (PointerPte->u.Hard.PageFrameNumber);
+ Pfn1->u1.WsIndex = Entry;
+ } else {
+ if (Table) {
+ Table[ MiLookupWsleHashIndex (WsleSwap.u1.Long,
+ WorkingSetList)].Index = Entry;
+ }
+ }
+ }
+ ASSERT (CurrentSize == WsInfo->WorkingSetSize);
+ return;
+}
+
+ULONG
+MiLookupWsleHashIndex (
+ IN ULONG WsleEntry,
+ IN PMMWSL WorkingSetList
+ )
+
+{
+ ULONG Hash;
+ ULONG VirtualAddress;
+ PMMWSLE_HASH Table;
+ ULONG Tries = 0;
+
+ Table = WorkingSetList->HashTable;
+ VirtualAddress = WsleEntry & ~(PAGE_SIZE - 1);
+
+ Hash = ((ULONG)VirtualAddress >> (PAGE_SHIFT - 2)) % (WorkingSetList->HashTableSize - 1);
+
+ while (Table[Hash].Key != (ULONG)VirtualAddress) {
+ Hash += 1;
+ if (Hash >= WorkingSetList->HashTableSize) {
+ Hash = 0;
+ if (Tries != 0) {
+ KeBugCheckEx (MEMORY_MANAGEMENT,
+ 0x41884,
+ (ULONG)VirtualAddress,
+ WsleEntry,
+ (ULONG)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 to 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, APC's disabled.
+
+--*/
+
+{
+ ULONG Free;
+ ULONG ParentFree;
+
+ Free = WorkingSetList->FirstFree;
+
+ if (Entry == Free) {
+ ASSERT ((Wsle[Entry].u1.Long >> MM_FREE_WSLE_SHIFT) <= WorkingSetList->LastInitializedWsle);
+ WorkingSetList->FirstFree = Wsle[Entry].u1.Long >> MM_FREE_WSLE_SHIFT;
+
+ } else {
+ do {
+ ParentFree = Free;
+ ASSERT (Wsle[Free].u1.e1.Valid == 0);
+ Free = 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, APC's 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-11 20:10:02 +0100