[navaraf] 12728: Change the MEMORY_AREAs to be stored it a binary search tree instead of linked list. Thanks to Royce Mitchell III and Mike Nordell for helping me.
Change the MEMORY_AREAs to be stored it a binary search tree instead of linked list. Thanks to Royce Mitchell III and Mike Nordell for helping me. Modified: trunk/reactos/ntoskrnl/cc/view.c Modified: trunk/reactos/ntoskrnl/include/internal/mm.h Modified: trunk/reactos/ntoskrnl/ke/bug.c Modified: trunk/reactos/ntoskrnl/ke/i386/exp.c Modified: trunk/reactos/ntoskrnl/ke/kthread.c Modified: trunk/reactos/ntoskrnl/mm/anonmem.c Modified: trunk/reactos/ntoskrnl/mm/aspace.c Modified: trunk/reactos/ntoskrnl/mm/cont.c Modified: trunk/reactos/ntoskrnl/mm/drvlck.c Modified: trunk/reactos/ntoskrnl/mm/iospace.c Modified: trunk/reactos/ntoskrnl/mm/marea.c Modified: trunk/reactos/ntoskrnl/mm/mdl.c Modified: trunk/reactos/ntoskrnl/mm/mm.c Modified: trunk/reactos/ntoskrnl/mm/mminit.c Modified: trunk/reactos/ntoskrnl/mm/ncache.c Modified: trunk/reactos/ntoskrnl/mm/pe.c Modified: trunk/reactos/ntoskrnl/mm/rmap.c Modified: trunk/reactos/ntoskrnl/mm/section.c Modified: trunk/reactos/ntoskrnl/mm/virtual.c Modified: trunk/reactos/ntoskrnl/ps/w32call.c _____
Modified: trunk/reactos/ntoskrnl/cc/view.c --- trunk/reactos/ntoskrnl/cc/view.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/cc/view.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -16,7 +16,7 @@
* along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -/* $Id: view.c,v 1.79 2004/10/22 20:11:12 ekohl Exp $ +/* $Id$ * * PROJECT: ReactOS kernel * FILE: ntoskrnl/cc/view.c @@ -813,8 +813,7 @@ #else MmLockAddressSpace(MmGetKernelAddressSpace()); MmFreeMemoryArea(MmGetKernelAddressSpace(), - CacheSeg->BaseAddress, - CacheSeg->Bcb->CacheSegmentSize, + CacheSeg->MemoryArea, CcFreeCachePage, NULL); MmUnlockAddressSpace(MmGetKernelAddressSpace()); _____
Modified: trunk/reactos/ntoskrnl/include/internal/mm.h --- trunk/reactos/ntoskrnl/include/internal/mm.h 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/include/internal/mm.h 2005-01-02 17:55:06 UTC (rev 12728) @@ -184,15 +184,17 @@
#endif /* __USE_W32API */
-typedef struct +typedef struct _MEMORY_AREA { + PVOID StartingAddress; + PVOID EndingAddress; + struct _MEMORY_AREA *Parent; + struct _MEMORY_AREA *LeftChild; + struct _MEMORY_AREA *RightChild; ULONG Type; - PVOID BaseAddress; - ULONG Length; ULONG Attributes; - LIST_ENTRY Entry; ULONG LockCount; - struct _EPROCESS* Process; + struct _EPROCESS* Process; /* FIXME: We don't need this! */ BOOLEAN DeleteInProgress; ULONG PageOpCount; union @@ -215,7 +217,7 @@
typedef struct _MADDRESS_SPACE { - LIST_ENTRY MAreaListHead; + PMEMORY_AREA MemoryAreaRoot; FAST_MUTEX Lock; PVOID LowestAddress; struct _EPROCESS* Process; @@ -333,6 +335,10 @@ LIST_ENTRY RegionListEntry; } MM_REGION, *PMM_REGION;
+typedef VOID (*PMM_FREE_PAGE_FUNC)(PVOID Context, PMEMORY_AREA MemoryArea, + PVOID Address, PFN_TYPE Page, + SWAPENTRY SwapEntry, BOOLEAN Dirty); + /* FUNCTIONS */
/* aspace.c ******************************************************************/ @@ -354,49 +360,68 @@
/* marea.c *******************************************************************/
-NTSTATUS MmCreateMemoryArea(struct _EPROCESS* Process, - PMADDRESS_SPACE AddressSpace, - ULONG Type, - PVOID* BaseAddress, - ULONG Length, - ULONG Attributes, - MEMORY_AREA** Result, - BOOL FixedAddress, - BOOL TopDown, - PHYSICAL_ADDRESS BoundaryAddressMultiple OPTIONAL); +NTSTATUS INIT_FUNCTION +MmInitMemoryAreas(VOID);
-MEMORY_AREA* MmOpenMemoryAreaByAddress(PMADDRESS_SPACE AddressSpace, - PVOID Address); +NTSTATUS STDCALL +MmCreateMemoryArea( + struct _EPROCESS* Process, + PMADDRESS_SPACE AddressSpace, + ULONG Type, + PVOID *BaseAddress, + ULONG_PTR Length, + ULONG Attributes, + PMEMORY_AREA *Result, + BOOLEAN FixedAddress, + BOOLEAN TopDown, + PHYSICAL_ADDRESS BoundaryAddressMultiple OPTIONAL);
-ULONG MmFindGapAtAddress(PMADDRESS_SPACE AddressSpace, - PVOID Address); +PMEMORY_AREA STDCALL +MmOpenMemoryAreaByAddress( + PMADDRESS_SPACE AddressSpace, + PVOID Address);
-NTSTATUS MmInitMemoryAreas(VOID); +ULONG STDCALL +MmFindGapAtAddress( + PMADDRESS_SPACE AddressSpace, + PVOID Address);
-NTSTATUS MmFreeMemoryArea(PMADDRESS_SPACE AddressSpace, - PVOID BaseAddress, - ULONG Length, - VOID (*FreePage)(PVOID Context, MEMORY_AREA* MemoryArea, - PVOID Address, PFN_TYPE Page, SWAPENTRY SwapEntry, - BOOLEAN Dirty), - PVOID FreePageContext); +NTSTATUS STDCALL +MmFreeMemoryArea( + PMADDRESS_SPACE AddressSpace, + PMEMORY_AREA MemoryArea, + PMM_FREE_PAGE_FUNC FreePage, + PVOID FreePageContext);
-VOID MmDumpMemoryAreas(PLIST_ENTRY ListHead); +NTSTATUS STDCALL +MmFreeMemoryAreaByPtr( + PMADDRESS_SPACE AddressSpace, + PVOID BaseAddress, + PMM_FREE_PAGE_FUNC FreePage, + PVOID FreePageContext);
-NTSTATUS MmLockMemoryArea(MEMORY_AREA* MemoryArea); +VOID STDCALL +MmDumpMemoryAreas(PMADDRESS_SPACE AddressSpace);
-NTSTATUS MmUnlockMemoryArea(MEMORY_AREA* MemoryArea); +PMEMORY_AREA STDCALL +MmOpenMemoryAreaByRegion( + PMADDRESS_SPACE AddressSpace, + PVOID Address, + ULONG_PTR Length);
-MEMORY_AREA* MmOpenMemoryAreaByRegion(PMADDRESS_SPACE AddressSpace, - PVOID Address, - ULONG Length); +PVOID STDCALL +MmFindGap( + PMADDRESS_SPACE AddressSpace, + ULONG_PTR Length, + ULONG_PTR Granularity, + BOOLEAN TopDown);
-PVOID MmFindGap(PMADDRESS_SPACE AddressSpace, ULONG Length, ULONG Granularity, BOOL TopDown); +VOID STDCALL +MmReleaseMemoryAreaIfDecommitted( + PEPROCESS Process, + PMADDRESS_SPACE AddressSpace, + PVOID BaseAddress);
-void MmReleaseMemoryAreaIfDecommitted(PEPROCESS Process, - PMADDRESS_SPACE AddressSpace, - PVOID BaseAddress); - /* npool.c *******************************************************************/
VOID MiDebugDumpNonPagedPool(BOOLEAN NewOnly); _____
Modified: trunk/reactos/ntoskrnl/ke/bug.c --- trunk/reactos/ntoskrnl/ke/bug.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/ke/bug.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -16,7 +16,7 @@
* along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -/* $Id: bug.c,v 1.48 2004/12/12 17:42:00 hbirr Exp $ +/* $Id$ * * PROJECT: ReactOS kernel * FILE: ntoskrnl/ke/bug.c @@ -116,6 +116,11 @@ Ke386DisableInterrupts(); DebugLogDumpMessages();
+ if (MmGetKernelAddressSpace()->Lock.Owner == KeGetCurrentThread()) + { + MmUnlockAddressSpace(MmGetKernelAddressSpace()); + } + if (KeGetCurrentIrql() < DISPATCH_LEVEL) { KeRaiseIrql(DISPATCH_LEVEL, &OldIrql); _____
Modified: trunk/reactos/ntoskrnl/ke/i386/exp.c --- trunk/reactos/ntoskrnl/ke/i386/exp.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/ke/i386/exp.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -320,7 +320,7 @@
{ KeRosPrintAddress((PVOID)Frame[1]); Frame = (PULONG)Frame[0]; - DbgPrint(" "); + DbgPrint("\n"); } #else DbgPrint("Frames: "); @@ -663,7 +663,7 @@ break; StackBase = Frame; Frame = (PULONG)Frame[0]; - DbgPrint(" "); + DbgPrint("\n"); } } _SEH_HANDLE _____
Modified: trunk/reactos/ntoskrnl/ke/kthread.c --- trunk/reactos/ntoskrnl/ke/kthread.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/ke/kthread.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -90,11 +90,10 @@
if (Thread->StackLimit != (ULONG_PTR)&init_stack) { MmLockAddressSpace(MmGetKernelAddressSpace()); - MmFreeMemoryArea(MmGetKernelAddressSpace(), - (PVOID)Thread->StackLimit, - MM_STACK_SIZE, - KeFreeStackPage, - NULL); + MmFreeMemoryAreaByPtr(MmGetKernelAddressSpace(), + (PVOID)Thread->StackLimit, + KeFreeStackPage, + NULL); MmUnlockAddressSpace(MmGetKernelAddressSpace()); } Thread->StackLimit = 0; _____
Modified: trunk/reactos/ntoskrnl/mm/anonmem.c --- trunk/reactos/ntoskrnl/mm/anonmem.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/mm/anonmem.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -16,7 +16,7 @@
* along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -/* $Id: anonmem.c,v 1.34 2004/12/19 16:16:57 navaraf Exp $ +/* $Id$ * * PROJECT: ReactOS kernel * FILE: ntoskrnl/mm/anonmem.c @@ -261,7 +261,7 @@ /* * Get the segment corresponding to the virtual address */ - Region = MmFindRegion(MemoryArea->BaseAddress, + Region = MmFindRegion(MemoryArea->StartingAddress,
&MemoryArea->Data.VirtualMemoryData.RegionListHead, Address, NULL); if (Region->Type == MEM_RESERVE || Region->Protect == PAGE_NOACCESS) @@ -525,6 +525,7 @@ { PEPROCESS Process; MEMORY_AREA* MemoryArea; + ULONG_PTR MemoryAreaLength; ULONG Type; NTSTATUS Status; PMADDRESS_SPACE AddressSpace; @@ -582,40 +583,44 @@ MemoryArea = MmOpenMemoryAreaByAddress(AddressSpace, BaseAddress);
- if (MemoryArea != NULL && - MemoryArea->Type == MEMORY_AREA_VIRTUAL_MEMORY && - MemoryArea->Length >= RegionSize) + if (MemoryArea != NULL) { - Status = - MmAlterRegion(AddressSpace, - MemoryArea->BaseAddress, - &MemoryArea->Data.VirtualMemoryData.RegionListHead, - BaseAddress, RegionSize, - Type, Protect, MmModifyAttributes); - MmUnlockAddressSpace(AddressSpace); - ObDereferenceObject(Process); - DPRINT("NtAllocateVirtualMemory() = %x\n",Status); - return(Status); + MemoryAreaLength = (ULONG_PTR)MemoryArea->EndingAddress - + (ULONG_PTR)MemoryArea->StartingAddress; + if (MemoryArea->Type == MEMORY_AREA_VIRTUAL_MEMORY && + MemoryAreaLength >= RegionSize) + { + Status = + MmAlterRegion(AddressSpace, + MemoryArea->StartingAddress, + &MemoryArea->Data.VirtualMemoryData.RegionListHead, + BaseAddress, RegionSize, + Type, Protect, MmModifyAttributes); + MmUnlockAddressSpace(AddressSpace); + ObDereferenceObject(Process); + DPRINT("NtAllocateVirtualMemory() = %x\n",Status); + return(Status); + } + else if (MemoryAreaLength >= RegionSize) + { + Status = + MmAlterRegion(AddressSpace, + MemoryArea->StartingAddress, + &MemoryArea->Data.SectionData.RegionListHead, + BaseAddress, RegionSize, + Type, Protect, MmModifyAttributes); + MmUnlockAddressSpace(AddressSpace); + ObDereferenceObject(Process); + DPRINT("NtAllocateVirtualMemory() = %x\n",Status); + return(Status); + } + else + { + MmUnlockAddressSpace(AddressSpace); + ObDereferenceObject(Process); + return(STATUS_UNSUCCESSFUL); + } } - else if (MemoryArea != NULL && MemoryArea->Length >= RegionSize) - { - Status = - MmAlterRegion(AddressSpace, - MemoryArea->BaseAddress, - &MemoryArea->Data.SectionData.RegionListHead, - BaseAddress, RegionSize, - Type, Protect, MmModifyAttributes); - MmUnlockAddressSpace(AddressSpace); - ObDereferenceObject(Process); - DPRINT("NtAllocateVirtualMemory() = %x\n",Status); - return(Status); - } - else if (MemoryArea != NULL) - { - MmUnlockAddressSpace(AddressSpace); - ObDereferenceObject(Process); - return(STATUS_UNSUCCESSFUL); - } }
Status = MmCreateMemoryArea(Process, @@ -626,7 +631,7 @@ Protect, &MemoryArea, PBaseAddress != 0, - (AllocationType & MEM_TOP_DOWN), + (AllocationType & MEM_TOP_DOWN) == MEM_TOP_DOWN, BoundaryAddressMultiple); if (!NT_SUCCESS(Status)) { @@ -635,18 +640,22 @@ DPRINT("NtAllocateVirtualMemory() = %x\n",Status); return(Status); } + + MemoryAreaLength = (ULONG_PTR)MemoryArea->EndingAddress - + (ULONG_PTR)MemoryArea->StartingAddress; +
MmInitialiseRegion(&MemoryArea->Data.VirtualMemoryData.RegionListHead, - MemoryArea->Length, Type, Protect); + MemoryAreaLength, Type, Protect);
if ((AllocationType & MEM_COMMIT) && ((Protect & PAGE_READWRITE) || (Protect & PAGE_EXECUTE_READWRITE))) { - MmReserveSwapPages(MemoryArea->Length); + MmReserveSwapPages(MemoryAreaLength); }
*UBaseAddress = BaseAddress; - *URegionSize = MemoryArea->Length; + *URegionSize = MemoryAreaLength; DPRINT("*UBaseAddress %x *URegionSize %x\n", BaseAddress, RegionSize);
MmUnlockAddressSpace(AddressSpace); @@ -702,7 +711,11 @@ */ if (MemoryArea->PageOpCount > 0) { - for (i = 0; i < PAGE_ROUND_UP(MemoryArea->Length) / PAGE_SIZE; i++) + ULONG_PTR MemoryAreaLength = (ULONG_PTR)MemoryArea->EndingAddress - + (ULONG_PTR)MemoryArea->StartingAddress; + + /* FiN TODO: Optimize loop counter! */ + for (i = 0; i < PAGE_ROUND_UP(MemoryAreaLength) / PAGE_SIZE; i++) { PMM_PAGEOP PageOp;
@@ -712,7 +725,7 @@ }
PageOp = MmCheckForPageOp(MemoryArea, Process->UniqueProcessId, - (char*)MemoryArea->BaseAddress + (i * PAGE_SIZE), + (PVOID)((ULONG_PTR)MemoryArea->StartingAddress + (i * PAGE_SIZE)), NULL, 0); if (PageOp != NULL) { @@ -745,8 +758,7 @@
/* Actually free the memory area. */ MmFreeMemoryArea(&Process->AddressSpace, - MemoryArea->BaseAddress, - 0, + MemoryArea, MmFreeVirtualMemoryPage, (PVOID)Process); } @@ -814,7 +826,7 @@ { case MEM_RELEASE: /* We can only free a memory area in one step. */ - if (MemoryArea->BaseAddress != BaseAddress || + if (MemoryArea->StartingAddress != BaseAddress || MemoryArea->Type != MEMORY_AREA_VIRTUAL_MEMORY) { MmUnlockAddressSpace(AddressSpace); @@ -829,7 +841,7 @@ case MEM_DECOMMIT: Status = MmAlterRegion(AddressSpace, - MemoryArea->BaseAddress, + MemoryArea->StartingAddress,
&MemoryArea->Data.VirtualMemoryData.RegionListHead, BaseAddress, RegionSize, @@ -856,11 +868,11 @@ PMM_REGION Region; NTSTATUS Status;
- Region = MmFindRegion(MemoryArea->BaseAddress, + Region = MmFindRegion(MemoryArea->StartingAddress,
&MemoryArea->Data.VirtualMemoryData.RegionListHead, BaseAddress, NULL); *OldProtect = Region->Protect; - Status = MmAlterRegion(AddressSpace, MemoryArea->BaseAddress, + Status = MmAlterRegion(AddressSpace, MemoryArea->StartingAddress,
&MemoryArea->Data.VirtualMemoryData.RegionListHead, BaseAddress, Length, Region->Type, Protect, MmModifyAttributes); @@ -878,11 +890,11 @@
Info->BaseAddress = (PVOID)PAGE_ROUND_DOWN(Address);
- Region = MmFindRegion(MemoryArea->BaseAddress, + Region = MmFindRegion(MemoryArea->StartingAddress,
&MemoryArea->Data.VirtualMemoryData.RegionListHead, Address, &RegionBase); Info->BaseAddress = RegionBase; - Info->AllocationBase = MemoryArea->BaseAddress; + Info->AllocationBase = MemoryArea->StartingAddress; Info->AllocationProtect = MemoryArea->Attributes; Info->RegionSize = (char*)RegionBase + Region->Length - (char*)Info->BaseAddress; Info->State = Region->Type; _____
Modified: trunk/reactos/ntoskrnl/mm/aspace.c --- trunk/reactos/ntoskrnl/mm/aspace.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/mm/aspace.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -68,7 +68,7 @@
MmInitializeAddressSpace(PEPROCESS Process, PMADDRESS_SPACE AddressSpace) { - InitializeListHead(&AddressSpace->MAreaListHead); + AddressSpace->MemoryAreaRoot = NULL; ExInitializeFastMutex(&AddressSpace->Lock); if (Process != NULL) { _____
Modified: trunk/reactos/ntoskrnl/mm/cont.c --- trunk/reactos/ntoskrnl/mm/cont.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/mm/cont.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -1,4 +1,4 @@
-/* $Id: cont.c,v 1.35 2004/10/22 20:38:22 ekohl Exp $ +/* $Id$ * * COPYRIGHT: See COPYING in the top level directory * PROJECT: ReactOS kernel @@ -42,7 +42,7 @@ { PMEMORY_AREA MArea; NTSTATUS Status; - PVOID BaseAddress = 0; + PVOID BaseAddress = NULL; PFN_TYPE PBase; ULONG Attributes; ULONG i; @@ -83,8 +83,7 @@ { MmLockAddressSpace(MmGetKernelAddressSpace()); MmFreeMemoryArea(MmGetKernelAddressSpace(), - BaseAddress, - 0, + MArea, NULL, NULL); MmUnlockAddressSpace(MmGetKernelAddressSpace()); @@ -174,11 +173,10 @@ MmFreeContiguousMemory(IN PVOID BaseAddress) { MmLockAddressSpace(MmGetKernelAddressSpace()); - MmFreeMemoryArea(MmGetKernelAddressSpace(), - BaseAddress, - 0, - MmFreeContinuousPage, - NULL); + MmFreeMemoryAreaByPtr(MmGetKernelAddressSpace(), + BaseAddress, + MmFreeContinuousPage, + NULL); MmUnlockAddressSpace(MmGetKernelAddressSpace()); }
@@ -260,11 +258,10 @@ IN MEMORY_CACHING_TYPE CacheType) { MmLockAddressSpace(MmGetKernelAddressSpace()); - MmFreeMemoryArea(MmGetKernelAddressSpace(), - BaseAddress, - NumberOfBytes, - MmFreeContinuousPage, - NULL); + MmFreeMemoryAreaByPtr(MmGetKernelAddressSpace(), + BaseAddress, + MmFreeContinuousPage, + NULL); MmUnlockAddressSpace(MmGetKernelAddressSpace()); }
_____
Modified: trunk/reactos/ntoskrnl/mm/drvlck.c --- trunk/reactos/ntoskrnl/mm/drvlck.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/mm/drvlck.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -1,4 +1,4 @@
-/* $Id: drvlck.c,v 1.6 2004/08/15 16:39:06 chorns Exp $ +/* $Id$ * * COPYRIGHT: See COPYING in the top level directory * PROJECT: ReactOS kernel @@ -64,7 +64,7 @@ MmLockPagableDataSection(IN PVOID AddressWithinSection) { PVOID Handle; - Handle = MmOpenMemoryAreaByAddress(NULL,AddressWithinSection); + Handle = MmOpenMemoryAreaByAddress(NULL, AddressWithinSection); MmLockPagableSectionByHandle(Handle); return(Handle); } _____
Modified: trunk/reactos/ntoskrnl/mm/iospace.c --- trunk/reactos/ntoskrnl/mm/iospace.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/mm/iospace.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -16,7 +16,7 @@
* along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -/* $Id: iospace.c,v 1.30 2004/08/15 16:39:07 chorns Exp $ +/* $Id$ * * PROJECT: ReactOS kernel * FILE: ntoskrnl/mm/iospace.c @@ -127,7 +127,7 @@ KEBUGCHECK(0); } } - return ((PVOID)((char*)Result + Offset)); + return (PVOID)((ULONG_PTR)Result + Offset); }
@@ -160,16 +160,17 @@ IN ULONG NumberOfBytes) { ULONG Offset; - Offset = (ULONG_PTR)BaseAddress % PAGE_SIZE; - BaseAddress = (PVOID)((PUCHAR)BaseAddress - Offset); + PVOID Address = BaseAddress; + + Offset = (ULONG_PTR)Address % PAGE_SIZE; + Address -= Offset; NumberOfBytes += Offset;
MmLockAddressSpace(MmGetKernelAddressSpace()); - MmFreeMemoryArea(MmGetKernelAddressSpace(), - BaseAddress, - NumberOfBytes, - NULL, - NULL); + MmFreeMemoryAreaByPtr(MmGetKernelAddressSpace(), + Address, + NULL, + NULL); MmUnlockAddressSpace(MmGetKernelAddressSpace()); }
_____
Modified: trunk/reactos/ntoskrnl/mm/marea.c --- trunk/reactos/ntoskrnl/mm/marea.c 2005-01-02 17:47:07 UTC (rev 12727) +++ trunk/reactos/ntoskrnl/mm/marea.c 2005-01-02 17:55:06 UTC (rev 12728) @@ -35,331 +35,590 @@
#define TAG_MAREA TAG('M', 'A', 'R', 'E')
+/* #define VALIDATE_MEMORY_AREAS */ + /* FUNCTIONS *****************************************************************/
-VOID MmDumpMemoryAreas(PLIST_ENTRY ListHead) +/** + * @name MmIterateFirstNode + * + * @param Node + * Head node of the MEMORY_AREA tree. + * + * @return The leftmost MEMORY_AREA node (ie. the one with lowest + * address) + */ + +static PMEMORY_AREA MmIterateFirstNode(PMEMORY_AREA Node) { - PLIST_ENTRY current_entry; - MEMORY_AREA* current; + while (Node->LeftChild != NULL) + Node = Node->LeftChild;
+ return Node; +} + +/** + * @name MmIterateNextNode + * + * @param Node + * Current node in the tree. + * + * @return Next node in the tree (sorted by address). + */ + +static PMEMORY_AREA MmIterateNextNode(PMEMORY_AREA Node) +{ + if (Node->RightChild != NULL) + { + Node = Node->RightChild; + while (Node->LeftChild != NULL) + Node = Node->LeftChild; + } + else + { + PMEMORY_AREA TempNode = NULL; + + do + { + /* Check if we're at the end of tree. */ + if (Node->Parent == NULL) + return NULL; + + TempNode = Node; + Node = Node->Parent; + } + while (TempNode == Node->RightChild); + } + return Node; +} + +/** + * @name MmIterateFirstNode + * + * @param Node + * Head node of the MEMORY_AREA tree. + * + * @return The rightmost MEMORY_AREA node (ie. the one with highest + * address) + */ + +static PMEMORY_AREA MmIterateLastNode(PMEMORY_AREA Node) +{ + while (Node->RightChild != NULL) + Node = Node->RightChild; + + return Node; +} + +/** + * @name MmIterateNextNode + * + * @param Node + * Current node in the tree. + * + * @return Previous node in the tree (sorted by address). + */ + +static PMEMORY_AREA MmIteratePrevNode(PMEMORY_AREA Node) +{ + if (Node->LeftChild != NULL) + { + Node = Node->LeftChild; + while (Node->RightChild != NULL) + Node = Node->RightChild; + } + else + { + PMEMORY_AREA TempNode = NULL; + + do + { + /* Check if we're at the end of tree. */ + if (Node->Parent == NULL) + return NULL; + + TempNode = Node; + Node = Node->Parent; + } + while (TempNode == Node->LeftChild); + } + return Node; +} + +#ifdef VALIDATE_MEMORY_AREAS +static VOID MmVerifyMemoryAreas(PMADDRESS_SPACE AddressSpace) +{ + PMEMORY_AREA Node; + + ASSERT(AddressSpace != NULL); + + /* Special case for empty tree. */ + if (AddressSpace->MemoryAreaRoot == NULL) + return; + + /* Traverse the tree from left to right. */ + for (Node = MmIterateFirstNode(AddressSpace->MemoryAreaRoot); + Node != NULL; + Node = MmIterateNextNode(Node)) + { + /* FiN: The starting address can be NULL if someone explicitely asks + * for NULL address. */ + ASSERT(Node->StartingAddress >= AddressSpace->LowestAddress || + Node->StartingAddress == NULL); + ASSERT(Node->EndingAddress >= Node->StartingAddress); + } +} +#else +#define MmVerifyMemoryAreas(x) +#endif + +VOID STDCALL +MmDumpMemoryAreas(PMADDRESS_SPACE AddressSpace) +{ + PMEMORY_AREA Node; + DbgPrint("MmDumpMemoryAreas()\n"); + + /* Special case for empty tree. */ + if (AddressSpace->MemoryAreaRoot == NULL) + return;
- current_entry = ListHead->Flink; - while (current_entry!=ListHead) + /* Traverse the tree from left to right. */ + for (Node = MmIterateFirstNode(AddressSpace->MemoryAreaRoot); + Node != NULL; + Node = MmIterateNextNode(Node)) { - current = CONTAINING_RECORD(current_entry,MEMORY_AREA,Entry); - DbgPrint("Base %x Length %x End %x Attributes %x Flink %x\n", - current->BaseAddress,current->Length, - (char*)current->BaseAddress+current->Length,current->Attributes, - current->Entry.Flink); - current_entry = current_entry->Flink; + DbgPrint("Start %x End %x Attributes %x\n", + Node->StartingAddress, Node->EndingAddress, + Node->Attributes); } + DbgPrint("Finished MmDumpMemoryAreas()\n"); }
-MEMORY_AREA* MmOpenMemoryAreaByAddress(PMADDRESS_SPACE AddressSpace, - PVOID Address) +PMEMORY_AREA STDCALL +MmOpenMemoryAreaByAddress( + PMADDRESS_SPACE AddressSpace, + PVOID Address) { - PLIST_ENTRY current_entry; - MEMORY_AREA* current; - PLIST_ENTRY previous_entry; + PMEMORY_AREA Node = AddressSpace->MemoryAreaRoot;
DPRINT("MmOpenMemoryAreaByAddress(AddressSpace %x, Address %x)\n", - AddressSpace, Address); + AddressSpace, Address);
- previous_entry = &AddressSpace->MAreaListHead; - current_entry = AddressSpace->MAreaListHead.Flink; - while (current_entry != &AddressSpace->MAreaListHead) + if (!(KdDebugState & KD_DEBUG_SCREEN)) + MmVerifyMemoryAreas(AddressSpace); + + while (Node != NULL) { - current = CONTAINING_RECORD(current_entry, - MEMORY_AREA, - Entry); - ASSERT(current_entry->Blink->Flink == current_entry); - ASSERT(current_entry->Flink->Blink == current_entry); - ASSERT(previous_entry->Flink == current_entry); - if (current->BaseAddress <= Address && - (PVOID)((char*)current->BaseAddress + current->Length) > Address) + if (Address < Node->StartingAddress) + Node = Node->LeftChild; + else if (Address >= Node->EndingAddress) + Node = Node->RightChild; + else { - DPRINT("%s() = %x\n",__FUNCTION__,current); - return(current); + DPRINT("MmOpenMemoryAreaByAddress(%x): %x [%x - %x]\n", + Address, Node, Node->StartingAddress, Node->EndingAddress); + return Node; } - if (current->BaseAddress > Address) - { - DPRINT("%s() = NULL\n",__FUNCTION__); - return(NULL); - } - previous_entry = current_entry; - current_entry = current_entry->Flink; } - DPRINT("%s() = NULL\n",__FUNCTION__); - return(NULL); + + DPRINT("MmOpenMemoryAreaByAddress(%x): 0\n", Address); + return NULL; }
-MEMORY_AREA* MmOpenMemoryAreaByRegion(PMADDRESS_SPACE AddressSpace, - PVOID Address, - ULONG Length) +PMEMORY_AREA STDCALL +MmOpenMemoryAreaByRegion( + PMADDRESS_SPACE AddressSpace, + PVOID Address, + ULONG_PTR Length) { - PLIST_ENTRY current_entry; - MEMORY_AREA* current; - ULONG Extent; + PMEMORY_AREA Node; + PVOID Extent = (PVOID)((ULONG_PTR)Address + Length);
- DPRINT("MmOpenMemoryByRegion(AddressSpace %x, Address %x, Length %x)\n", - AddressSpace, Address, Length); + MmVerifyMemoryAreas(AddressSpace);
- current_entry = AddressSpace->MAreaListHead.Flink; - while (current_entry != &AddressSpace->MAreaListHead) + /* Special case for empty tree. */ + if (AddressSpace->MemoryAreaRoot == NULL) + return NULL; + + /* Traverse the tree from left to right. */ + for (Node = MmIterateFirstNode(AddressSpace->MemoryAreaRoot); + Node != NULL; + Node = MmIterateNextNode(Node)) { - current = CONTAINING_RECORD(current_entry, - MEMORY_AREA, - Entry); - DPRINT("current->BaseAddress %x current->Length %x\n", - current->BaseAddress,current->Length); - if (current->BaseAddress >= Address && - current->BaseAddress < (PVOID)((char*)Address+Length)) + if (Node->StartingAddress >= Address && + Node->StartingAddress < Extent) { - DPRINT("Finished MmOpenMemoryAreaByRegion() = %x\n", - current); - return(current); + DPRINT("MmOpenMemoryAreaByRegion(%x - %x): %x - %x\n", + Address, Address + Length, Node->StartingAddress, + Node->EndingAddress); + return Node; } - Extent = (ULONG)current->BaseAddress + current->Length; - if (Extent > (ULONG)Address && - Extent < (ULONG)((char*)Address+Length)) + if (Node->EndingAddress > Address && + Node->EndingAddress < Extent) { - DPRINT("Finished MmOpenMemoryAreaByRegion() = %x\n", - current); - return(current); + DPRINT("MmOpenMemoryAreaByRegion(%x - %x): %x - %x\n", + Address, Address + Length, Node->StartingAddress, + Node->EndingAddress); + return Node; } - if (current->BaseAddress <= Address && - Extent >= (ULONG)((char*)Address+Length)) + if (Node->StartingAddress <= Address && + Node->EndingAddress >= Extent) { - DPRINT("Finished MmOpenMemoryAreaByRegion() = %x\n", - current); - return(current); + DPRINT("MmOpenMemoryAreaByRegion(%x - %x): %x - %x\n", + Address, Address + Length, Node->StartingAddress, + Node->EndingAddress); + return Node; } - if (current->BaseAddress >= (PVOID)((char*)Address+Length)) + if (Node->StartingAddress >= Extent) { - DPRINT("Finished MmOpenMemoryAreaByRegion()= NULL\n",0); - return(NULL); + DPRINT("Finished MmOpenMemoryAreaByRegion() = NULL\n"); + return NULL; } - current_entry = current_entry->Flink; } - DPRINT("Finished MmOpenMemoryAreaByRegion() = NULL\n",0); - return(NULL); + + return NULL; }
-static VOID MmInsertMemoryArea(PMADDRESS_SPACE AddressSpace, - MEMORY_AREA* marea) +/* + * @name MmCompressHelper + * + * This is helper of MmRebalanceTree. Performs a compression transformation + * count times, starting at root. + */ + +static VOID +MmCompressHelper( + PMADDRESS_SPACE AddressSpace, + ULONG Count) { - PLIST_ENTRY ListHead; - PLIST_ENTRY current_entry; - PLIST_ENTRY inserted_entry = &marea->Entry; - MEMORY_AREA* current; - MEMORY_AREA* next; + PMEMORY_AREA Root = NULL; + PMEMORY_AREA Red = AddressSpace->MemoryAreaRoot; + PMEMORY_AREA Black = Red->LeftChild;
- DPRINT("MmInsertMemoryArea(marea %x)\n", marea); - DPRINT("marea->BaseAddress %x\n", marea->BaseAddress); - DPRINT("marea->Length %x\n", marea->Length); + while (Count--) + { + if (Root) + Root->LeftChild = Black; + else + AddressSpace->MemoryAreaRoot = Black; + Black->Parent = Root; + Red->LeftChild = Black->RightChild; + if (Black->RightChild) + Black->RightChild->Parent = Red; + Black->RightChild = Red; + Red->Parent = Black; + Root = Black;
- ListHead = &AddressSpace->MAreaListHead; - - current_entry = ListHead->Flink; - if (IsListEmpty(ListHead)) - { - InsertHeadList(ListHead,&marea->Entry); - return; - } - current = CONTAINING_RECORD(current_entry,MEMORY_AREA,Entry); - if (current->BaseAddress > marea->BaseAddress) - { - InsertHeadList(ListHead,&marea->Entry); - return; - } - while (current_entry->Flink!=ListHead) - { - current = CONTAINING_RECORD(current_entry,MEMORY_AREA,Entry); - next = CONTAINING_RECORD(current_entry->Flink,MEMORY_AREA,Entry); - if (current->BaseAddress < marea->BaseAddress && - current->Entry.Flink==ListHead) + if (Count) { - current_entry->Flink = inserted_entry; - inserted_entry->Flink=ListHead; - inserted_entry->Blink=current_entry; - ListHead->Blink = inserted_entry; - return; + Red = Root->LeftChild; + Black = Red->LeftChild; } - if (current->BaseAddress < marea->BaseAddress && [truncated at 1000 lines; 1533 more skipped]
-
navaraf＠svn.reactos.com