Author: fireball
Date: Mon Feb 21 22:42:21 2011
New Revision: 50860
URL: http://svn.reactos.org/svn/reactos?rev=50860&view=rev
Log:
[RTL/DPH]
- Implement heap free operation using already implemented
busy/free/available/unused lists support and other base routines.
- Implement missing place to free list and remove from busy list routines.
- Implement find busy block routine (using AVL tree).
- Fix a bug in RtlpDphCoalesceNodeIntoAvailable() which resulted in unwanted
attempt to merge the only node with itself (which failed anyway).
- Fix a bug in RtlpDphCoalesceNodeIntoAvailable() which incorrectly removed a
node from available list (which is implemented as a standard NT double-linked
list, compared to unused and free lists which are implemented as single-linked
custom lists and busy list which is an AVL tree). Result of that bug was an
infinite loop at the next attempt to traverse the list of available nodes.
- In RtlpDphCoalesceFreeIntoAvailable() break when FreeAllocations becomes less
than LeaveOnFreeList (before it would break 1 size too early).
- Fix list traversal in RtlpDphSearchAvailableMemoryListForBestFit(). If it
couldn't find a node, it would return the last node in the list instead of NULL.
- In RtlpDphFindAvailableMemory(), a new smaller size should be 4 times
smaller, not just 2.
- Add a #if0-ed section in RtlpDphRemoveFromAvailableList which checks if a
request to remove node not in the list performed. Used only for debugging.
- Add a trace dprint to every type of list insert/removal operation for easier
tracking.
- Add break on NULL ptr freeing support.
- RtlpDphSetProtectionAfterUse() is stubbed and protection is set directly in
RtlpDphHeapFree(). To be moved into this function.
Modified:
trunk/reactos/lib/rtl/heappage.c
Modified: trunk/reactos/lib/rtl/heappage.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/heappage.c?rev=50860&r1=50859&r2=50860&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/heappage.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/heappage.c [iso-8859-1] Mon Feb 21 22:42:21 2011
@@ -137,20 +137,22 @@
#define DPH_BREAK_ON_RELEASE_FAIL 0x04
#define DPH_BREAK_ON_FREE_FAIL 0x08
#define DPH_BREAK_ON_PROTECT_FAIL 0x10
+#define DPH_BREAK_ON_NULL_FREE 0x80
/* RtlpDphDebugOptions */
#define DPH_DEBUG_INTERNAL_VALIDATE 0x01
#define DPH_DEBUG_VERBOSE 0x04
/* DPH ExtraFlags */
-#define DPH_EXTRA_CHECK_UNDERRUN 0x10
-#define DPH_LOG_STACK_TRACES 0x0 //FIXME: Get correct value
+#define DPH_EXTRA_LOG_STACK_TRACES 0x02
+#define DPH_EXTRA_CHECK_UNDERRUN 0x10
/* Fillers */
#define DPH_FILL 0xEEEEEEEE
#define DPH_FILL_START_STAMP_1 0xABCDBBBB
#define DPH_FILL_START_STAMP_2 0xABCDBBBA
#define DPH_FILL_END_STAMP_1 0xDCBABBBB
+#define DPH_FILL_END_STAMP_2 0xDCBABBBA
#define DPH_FILL_SUFFIX 0xD0
#define DPH_FILL_INFIX 0xC0
@@ -453,9 +455,31 @@
}
VOID NTAPI
+RtlpDphPlaceOnFreeList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK Node)
+{
+ DPRINT("RtlpDphPlaceOnFreeList(%p %p)\n", DphRoot, Node);
+
+ /* Node is being added to the tail of the list */
+ Node->pNextAlloc = NULL;
+
+ /* Add it to the tail of the linked list */
+ if (DphRoot->pFreeAllocationListTail)
+ DphRoot->pFreeAllocationListTail->pNextAlloc = Node;
+ else
+ DphRoot->pFreeAllocationListHead = Node;
+ DphRoot->pFreeAllocationListTail = Node;
+
+ /* Update byte counts taking in account this new node */
+ DphRoot->nFreeAllocations++;
+ DphRoot->nFreeAllocationBytesCommitted += Node->nVirtualBlockSize;
+}
+
+VOID NTAPI
RtlpDphPlaceOnPoolList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK Node)
{
- /* DphNode is being added to the tail of the list */
+ DPRINT("RtlpDphPlaceOnPoolList(%p %p)\n", DphRoot, Node);
+
+ /* Node is being added to the tail of the list */
Node->pNextAlloc = NULL;
/* Add it to the tail of the linked list */
@@ -473,6 +497,8 @@
VOID NTAPI
RtlpDphPlaceOnVirtualList(PDPH_HEAP_ROOT DphRoot, PDPH_HEAP_BLOCK Node)
{
+ DPRINT("RtlpDphPlaceOnVirtualList(%p %p)\n", DphRoot, Node);
+
/* Add it to the head of the virtual list */
Node->pNextAlloc = DphRoot->pVirtualStorageListHead;
if (!DphRoot->pVirtualStorageListHead)
@@ -490,6 +516,8 @@
PDPH_HEAP_BLOCK Node = DphRoot->pUnusedNodeListHead;
PDPH_HEAP_BLOCK Next;
+ DPRINT("RtlpDphTakeNodeFromUnusedList(%p), ret %p\n", DphRoot, Node);
+
/* Take the first entry */
if (!Node) return NULL;
@@ -508,6 +536,8 @@
RtlpDphReturnNodeToUnusedList(PDPH_HEAP_ROOT DphRoot,
PDPH_HEAP_BLOCK Node)
{
+ DPRINT("RtlpDphReturnNodeToUnusedList(%p, %p)\n", DphRoot, Node);
+
/* Add it back to the head of the unused list */
Node->pNextAlloc = DphRoot->pUnusedNodeListHead;
if (!DphRoot->pUnusedNodeListHead)
@@ -528,6 +558,37 @@
DPRINT("RtlpDphRemoveFromAvailableList(%p %p)\n", DphRoot, Node);
+ /* Check if it is in the list */
+#if 0
+ {
+ PLIST_ENTRY CurEntry;
+ PDPH_HEAP_BLOCK NodeEntry;
+ BOOLEAN Found = FALSE;
+
+ /* Find where to put this node according to its virtual address */
+ CurEntry = DphRoot->AvailableAllocationHead.Flink;
+
+ while (CurEntry != &DphRoot->AvailableAllocationHead)
+ {
+ NodeEntry = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK,
AvailableEntry);
+
+ if (NodeEntry == Node)
+ {
+ Found = TRUE;
+ break;
+ }
+
+ CurEntry = CurEntry->Flink;
+ }
+
+ if (!Found)
+ {
+ DPRINT1("Trying to remove non-existing in availlist node!\n");
+ DbgBreakPoint();
+ }
+ }
+#endif
+
/* Remove it from the list */
RemoveEntryList(&Node->AvailableEntry);
@@ -541,11 +602,31 @@
}
VOID NTAPI
+RtlpDphRemoveFromBusyList(PDPH_HEAP_ROOT DphRoot,
+ PDPH_HEAP_BLOCK Node)
+{
+ BOOLEAN ElementPresent;
+
+ DPRINT("RtlpDphRemoveFromBusyList(%p %p)\n", DphRoot, Node);
+
+ /* Delete it from busy nodes table */
+ ElementPresent = RtlDeleteElementGenericTableAvl(&DphRoot->BusyNodesTable,
&Node->pUserAllocation);
+ ASSERT(ElementPresent == TRUE);
+
+ /* Update counters */
+ DphRoot->nBusyAllocations--;
+ DphRoot->nBusyAllocationBytesCommitted -= Node->nVirtualBlockSize;
+ DphRoot->nBusyAllocationBytesAccessible -= Node->nVirtualAccessSize;
+}
+
+VOID NTAPI
RtlpDphRemoveFromFreeList(PDPH_HEAP_ROOT DphRoot,
PDPH_HEAP_BLOCK Node,
PDPH_HEAP_BLOCK Prev)
{
PDPH_HEAP_BLOCK Next;
+
+ DPRINT("RtlpDphRemoveFromFreeList(%p %p %p)\n", DphRoot, Node, Prev);
/* Detach it from the list */
Next = Node->pNextAlloc;
@@ -578,12 +659,13 @@
/* Find where to put this node according to its virtual address */
AvailListHead = &DphRoot->AvailableAllocationHead;
+
+ /* Find a point where to insert an available node */
CurEntry = AvailListHead->Flink;
while (CurEntry != AvailListHead)
{
NodeEntry = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK,
AvailableEntry);
-
if (NodeEntry->pVirtualBlock >= Node->pVirtualBlock)
{
PrevNode = NodeEntry;
@@ -592,10 +674,9 @@
CurEntry = CurEntry->Flink;
}
- /* Did we find a node to insert our one after? */
if (!PrevNode)
{
- /* No, just add to the head of the list then */
+ /* That means either this list is empty, or we should add to the head
of it */
InsertHeadList(AvailListHead, &Node->AvailableEntry);
}
else
@@ -615,20 +696,22 @@
/* Insert after PrevNode */
InsertTailList(&PrevNode->AvailableEntry, &Node->AvailableEntry);
}
- }
-
- /* Now check the next entry after our one */
- if (Node->AvailableEntry.Flink != AvailListHead)
- {
- NextNode = CONTAINING_RECORD(Node->AvailableEntry.Flink,
DPH_HEAP_BLOCK, AvailableEntry);;
- /* Node is not at the tail of the list, check if it's adjacent */
- if (Node->pVirtualBlock + Node->nVirtualBlockSize ==
NextNode->pVirtualBlock)
- {
- /* They are adjacent - merge! */
- Node->nVirtualBlockSize += NextNode->nVirtualBlockSize;
- Node->pNextAlloc = NextNode->pNextAlloc;
- RtlpDphReturnNodeToUnusedList(DphRoot, NextNode);
- DphRoot->nAvailableAllocations--;
+
+ /* Now check the next entry after our one */
+ if (Node->AvailableEntry.Flink != AvailListHead)
+ {
+ NextNode = CONTAINING_RECORD(Node->AvailableEntry.Flink,
DPH_HEAP_BLOCK, AvailableEntry);
+ /* Node is not at the tail of the list, check if it's adjacent */
+ if (Node->pVirtualBlock + Node->nVirtualBlockSize ==
NextNode->pVirtualBlock)
+ {
+ /* They are adjacent - merge! */
+ Node->nVirtualBlockSize += NextNode->nVirtualBlockSize;
+
+ /* Remove next entry from the list and put it into unused
entries list */
+ RemoveEntryList(&NextNode->AvailableEntry);
+ RtlpDphReturnNodeToUnusedList(DphRoot, NextNode);
+ DphRoot->nAvailableAllocations--;
+ }
}
}
}
@@ -643,10 +726,12 @@
/* Make sure requested size is not too big */
ASSERT(FreeAllocations >= LeaveOnFreeList);
+ DPRINT("RtlpDphCoalesceFreeIntoAvailable(%p %d)\n", DphRoot,
LeaveOnFreeList);
+
while (Node)
{
FreeAllocations--;
- if (FreeAllocations <= LeaveOnFreeList) break;
+ if (FreeAllocations < LeaveOnFreeList) break;
/* Get the next pointer, because it may be changed after following two
calls */
Next = Node->pNextAlloc;
@@ -657,6 +742,7 @@
/* And put into the available */
RtlpDphCoalesceNodeIntoAvailable(DphRoot, Node);
+ /* Go to the next node */
Node = Next;
}
}
@@ -713,20 +799,21 @@
SIZE_T Size)
{
PLIST_ENTRY CurEntry;
- PDPH_HEAP_BLOCK Node;
+ PDPH_HEAP_BLOCK Node, NodeFound = NULL;
CurEntry = DphRoot->AvailableAllocationHead.Flink;
- while (TRUE)
- {
- /* If we reached end of the list - return right away */
- if (CurEntry == &DphRoot->AvailableAllocationHead) return NULL;
-
+ while (CurEntry != &DphRoot->AvailableAllocationHead)
+ {
/* Get the current available node */
Node = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK, AvailableEntry);
/* Check its size */
- if (Node->nVirtualBlockSize >= Size) break;
+ if (Node->nVirtualBlockSize >= Size)
+ {
+ NodeFound = Node;
+ break;
+ }
/* Move to the next available entry */
CurEntry = CurEntry->Flink;
@@ -736,7 +823,7 @@
//ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Flink));
//ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Blink));
- return Node;
+ return NodeFound;
}
PDPH_HEAP_BLOCK NTAPI
@@ -757,7 +844,7 @@
if (DphRoot->nFreeAllocations <= DPH_FREE_LIST_MINIMUM) break;
/* Calculate a new free list size */
- NewSize = DphRoot->nFreeAllocations >> 1;
+ NewSize = DphRoot->nFreeAllocations >> 2;
if (NewSize < DPH_FREE_LIST_MINIMUM) NewSize = DPH_FREE_LIST_MINIMUM;
/* Coalesce free into available */
@@ -795,6 +882,23 @@
return Node;
}
+PDPH_HEAP_BLOCK NTAPI
+RtlpDphFindBusyMemory(PDPH_HEAP_ROOT DphRoot,
+ PVOID pUserMem)
+{
+ PDPH_HEAP_BLOCK Node;
+ PVOID Ptr;
+
+ /* Lookup busy block in AVL */
+ Ptr = RtlLookupElementGenericTableAvl(&DphRoot->BusyNodesTable, &pUserMem);
+ if (!Ptr) return NULL;
+
+ /* Restore pointer to the heap block */
+ Node = CONTAINING_RECORD(Ptr, DPH_HEAP_BLOCK, pUserAllocation);
+ ASSERT(Node->pUserAllocation == pUserMem);
+ return Node;
+}
+
NTSTATUS NTAPI
RtlpDphSetProtectionBeforeUse(PDPH_HEAP_ROOT DphRoot, PUCHAR VirtualBlock,
ULONG UserSize)
{
@@ -815,6 +919,20 @@
Protection = PAGE_READWRITE;
return RtlpDphProtectVm(Base, UserSize, Protection);
+}
+
+NTSTATUS NTAPI
+RtlpDphSetProtectionAfterUse(PDPH_HEAP_ROOT DphRoot, /*PUCHAR
VirtualBlock*/PDPH_HEAP_BLOCK Node)
+{
+ // FIXME: Bring stuff here
+ if (DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN)
+ {
+ }
+ else
+ {
+ }
+
+ return STATUS_SUCCESS;
}
PDPH_HEAP_BLOCK NTAPI
@@ -1685,8 +1803,91 @@
ULONG Flags,
PVOID Ptr)
{
- UNIMPLEMENTED;
- return FALSE;
+ PDPH_HEAP_ROOT DphRoot;
+ PDPH_HEAP_BLOCK Node;
+ ULONG ValidationInfo;
+ PDPH_BLOCK_INFORMATION Info;
+
+ /* Check for a NULL pointer freeing */
+ if (!HeapPtr)
+ {
+ if (RtlpDphBreakOptions & DPH_BREAK_ON_NULL_FREE)
+ {
+ DPRINT1("Page heap: freeing a null pointer \n");
+ DbgBreakPoint();
+ }
+ return TRUE;
+ }
+
+ /* Get a pointer to the heap root */
+ DphRoot = RtlpDphPointerFromHandle(HeapPtr);
+ if (!DphRoot) return FALSE;
+
+ /* Acquire the heap lock */
+ RtlpDphPreProcessing(DphRoot, Flags);
+
+ /* Perform internal validation if specified by flags */
+ if (RtlpDphDebugOptions & DPH_DEBUG_INTERNAL_VALIDATE)
+ RtlpDphInternalValidatePageHeap(DphRoot, NULL, 0);
+
+ /* Add heap flags */
+ Flags |= DphRoot->HeapFlags;
+
+ /* Find busy memory */
+ Node = RtlpDphFindBusyMemory(DphRoot, Ptr);
+
+ if (!Node)
+ {
+ /* This block was not found in page heap, try a normal heap instead */
+ //RtlpDphNormalHeapFree();
+ ASSERT(FALSE);
+ }
+
+ if (!(DphRoot->ExtraFlags & DPH_EXTRA_CHECK_UNDERRUN))
+ {
+ /* Check and report corrupted block */
+ if (!RtlpDphIsPageHeapBlock(DphRoot, Ptr, &ValidationInfo, TRUE))
+ {
+ RtlpDphReportCorruptedBlock(DphRoot, 1, Ptr, ValidationInfo);
+ }
+
+ // FIXME: Should go inside RtlpDphSetProtectionAfterUse
+ if (Node->nVirtualAccessSize != 0)
+ {
+ /* Set stamps */
+ Info = (PDPH_BLOCK_INFORMATION)Node->pUserAllocation - 1;
+ Info->StartStamp = DPH_FILL_START_STAMP_2;
+ Info->EndStamp = DPH_FILL_END_STAMP_2;
+
+ RtlpDphProtectVm(Node->pVirtualBlock, Node->nVirtualAccessSize,
PAGE_NOACCESS);
+ }
+ }
+ else
+ {
+ // FIXME: Should go inside RtlpDphSetProtectionAfterUse
+ if (Node->nVirtualAccessSize != 0)
+ RtlpDphProtectVm(Node->pVirtualBlock + PAGE_SIZE,
Node->nVirtualAccessSize, PAGE_NOACCESS);
+ }
+
+ /* Set new protection */
+ RtlpDphSetProtectionAfterUse(DphRoot, Node);
+
+ /* Remove it from the list of busy nodes */
+ RtlpDphRemoveFromBusyList(DphRoot, Node);
+
+ /* And put it into the list of free nodes */
+ RtlpDphPlaceOnFreeList(DphRoot, Node);
+
+ //if (DphRoot->ExtraFlags & DPH_EXTRA_LOG_STACK_TRACES)
+ // Node->StackTrace = RtlpDphLogStackTrace(3);
+ //else
+ Node->StackTrace = NULL;
+
+ /* Leave the heap lock */
+ RtlpDphPostProcessing(DphRoot);
+
+ /* Return success */
+ return TRUE;
}
PVOID NTAPI
