[ros-diffs] [fireball] 50698: [RTL/DPH] - Implement more support functions: coalescing a node into the list of available nodes, finding a best fitting node for a given size, growing available virtual memory am...
fireball at svn.reactos.org
fireball at svn.reactos.org
Tue Feb 15 11:53:17 UTC 2011
Author: fireball
Date: Tue Feb 15 11:53:16 2011
New Revision: 50698
URL: http://svn.reactos.org/svn/reactos?rev=50698&view=rev
Log:
[RTL/DPH]
- Implement more support functions: coalescing a node into the list of available nodes, finding a best fitting node for a given size, growing available virtual memory amount.
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=50698&r1=50697&r2=50698&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/heappage.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/heappage.c [iso-8859-1] Tue Feb 15 11:53:16 2011
@@ -7,6 +7,7 @@
/* Useful references:
http://msdn.microsoft.com/en-us/library/ms220938(VS.80).aspx
+ http://blogs.msdn.com/b/jiangyue/archive/2010/03/16/windows-heap-overrun-monitoring.aspx
*/
/* INCLUDES *****************************************************************/
@@ -125,6 +126,7 @@
#define DPH_RESERVE_SIZE 0x100000
#define DPH_POOL_SIZE 0x4000
+#define DPH_FREE_LIST_MINIMUM 8
/* RtlpDphBreakOptions */
#define DPH_BREAK_ON_RESERVE_FAIL 0x01
@@ -149,6 +151,9 @@
#define POINTER_ADD_BIAS(ptr) ((ULONG_PTR)(ptr) & 1)
/* FUNCTIONS ******************************************************************/
+
+BOOLEAN NTAPI
+RtlpDphGrowVirtual(PDPH_HEAP_ROOT DphRoot, SIZE_T Size);
NTSTATUS NTAPI
RtlpSecMemFreeVirtualMemory(HANDLE Process, PVOID *Base, PSIZE_T Size, ULONG Type)
@@ -361,6 +366,75 @@
RtlpDphCoalesceNodeIntoAvailable(PDPH_HEAP_ROOT DphRoot,
PDPH_HEAP_BLOCK Node)
{
+ PDPH_HEAP_BLOCK NodeEntry, PrevNode = NULL, NextNode;
+ PLIST_ENTRY AvailListHead;
+ PLIST_ENTRY CurEntry;
+
+ /* Update heap counters */
+ DphRoot->nAvailableAllocationBytesCommitted += Node->nVirtualBlockSize;
+ DphRoot->nAvailableAllocations++;
+
+ /* Find where to put this node according to its virtual address */
+ AvailListHead = &DphRoot->AvailableAllocationHead;
+ CurEntry = AvailListHead->Flink;
+
+ while (CurEntry != AvailListHead)
+ {
+ NodeEntry = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK, AvailableEntry);
+
+ if (NodeEntry->pVirtualBlock >= Node->pVirtualBlock)
+ {
+ PrevNode = NodeEntry;
+ break;
+ }
+ 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 */
+ InsertHeadList(AvailListHead, &Node->AvailableEntry);
+ }
+ else
+ {
+ /* Check the previous node and merge if possible */
+ if (PrevNode->pVirtualBlock + PrevNode->nVirtualBlockSize == Node->pVirtualBlock)
+ {
+ /* They are adjacent - merge! */
+ PrevNode->nVirtualBlockSize += Node->nVirtualBlockSize;
+ RtlpDphReturnNodeToUnusedList(DphRoot, Node);
+ DphRoot->nAvailableAllocations--;
+
+ Node = PrevNode;
+ }
+ else
+ {
+ /* 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--;
+ }
+ }
+}
+
+VOID NTAPI
+RtlpDphCoalesceFreeIntoAvailable(PDPH_HEAP_ROOT DphRoot,
+ ULONG Size)
+{
UNIMPLEMENTED;
}
@@ -408,12 +482,90 @@
}
PDPH_HEAP_BLOCK NTAPI
+RtlpDphSearchAvailableMemoryListForBestFit(PDPH_HEAP_ROOT DphRoot,
+ SIZE_T Size)
+{
+ PLIST_ENTRY CurEntry;
+ PDPH_HEAP_BLOCK Node;
+
+ CurEntry = DphRoot->AvailableAllocationHead.Flink;
+
+ while (TRUE)
+ {
+ /* If we reached end of the list - return right away */
+ if (CurEntry == &DphRoot->AvailableAllocationHead) return NULL;
+
+ /* Get the current available node */
+ Node = CONTAINING_RECORD(CurEntry, DPH_HEAP_BLOCK, AvailableEntry);
+
+ /* Check its size */
+ if (Node->nVirtualBlockSize >= Size) break;
+
+ /* Move to the next available entry */
+ CurEntry = CurEntry->Flink;
+ }
+
+ /* Make sure Adjacency list pointers are biased */
+ ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Flink));
+ ASSERT(IS_BIASED_POINTER(Node->AdjacencyEntry.Blink));
+
+ return Node;
+}
+
+PDPH_HEAP_BLOCK NTAPI
RtlpDphFindAvailableMemory(PDPH_HEAP_ROOT DphRoot,
SIZE_T Size,
- PDPH_HEAP_BLOCK *Prev)
-{
- UNIMPLEMENTED;
- return NULL;
+ BOOLEAN Grow)
+{
+ PDPH_HEAP_BLOCK Node;
+ ULONG NewSize;
+
+ /* Find an available best fitting node */
+ Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
+
+ /* If that didn't work, try to search a smaller one in the loop */
+ while (!Node)
+ {
+ /* Break if the free list becomes too small */
+ if (DphRoot->nFreeAllocations <= DPH_FREE_LIST_MINIMUM) break;
+
+ /* Calculate a new free list size */
+ NewSize = DphRoot->nFreeAllocations >> 1;
+ if (NewSize < DPH_FREE_LIST_MINIMUM) NewSize = DPH_FREE_LIST_MINIMUM;
+
+ /* Coalesce free into available */
+ RtlpDphCoalesceFreeIntoAvailable(DphRoot, NewSize);
+
+ /* Try to find an available best fitting node again */
+ Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
+ }
+
+ /* If Node is NULL, then we could fix the situation only by
+ growing the available VM size */
+ if (!Node && Grow)
+ {
+ /* Grow VM size, if it fails - return failure directly */
+ if (!RtlpDphGrowVirtual(DphRoot, Size)) return NULL;
+
+ /* Try to find an available best fitting node again */
+ Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
+
+ if (!Node)
+ {
+ /* Do the last attempt: coalesce all free into available (if Size fits there) */
+ if (DphRoot->nFreeAllocationBytesCommitted + DphRoot->nAvailableAllocationBytesCommitted >= Size)
+ {
+ /* Coalesce free into available */
+ RtlpDphCoalesceFreeIntoAvailable(DphRoot, 0);
+
+ /* Try to find an available best fitting node again */
+ Node = RtlpDphSearchAvailableMemoryListForBestFit(DphRoot, Size);
+ }
+ }
+ }
+
+ /* Return node we found */
+ return Node;
}
PDPH_HEAP_BLOCK NTAPI
@@ -434,13 +586,13 @@
}
/* There is a need to make free space */
- Node = RtlpDphFindAvailableMemory(DphRoot, DPH_POOL_SIZE, NULL);
+ Node = RtlpDphFindAvailableMemory(DphRoot, DPH_POOL_SIZE, FALSE);
if (!DphRoot->pUnusedNodeListHead && !Node)
{
/* Retry with a smaller request */
Size = PAGE_SIZE;
- Node = RtlpDphFindAvailableMemory(DphRoot, PAGE_SIZE, NULL);
+ Node = RtlpDphFindAvailableMemory(DphRoot, PAGE_SIZE, FALSE);
}
if (!DphRoot->pUnusedNodeListHead)
@@ -499,6 +651,56 @@
}
return RtlpDphTakeNodeFromUnusedList(DphRoot);
+}
+
+BOOLEAN NTAPI
+RtlpDphGrowVirtual(PDPH_HEAP_ROOT DphRoot,
+ SIZE_T Size)
+{
+ PDPH_HEAP_BLOCK Node, AvailableNode;
+ PVOID Base;
+ SIZE_T VirtualSize;
+ NTSTATUS Status;
+
+ /* Start with allocating a couple of nodes */
+ Node = RtlpDphAllocateNode(DphRoot);
+ if (!Node) return FALSE;
+
+ AvailableNode = RtlpDphAllocateNode(DphRoot);
+ if (!AvailableNode)
+ {
+ /* Free the allocated node and return failure */
+ RtlpDphReturnNodeToUnusedList(DphRoot, Node);
+ return FALSE;
+ }
+
+ /* Calculate size of VM to allocate by rounding it up */
+ VirtualSize = (Size + 0xFFFF) & 0xFFFF0000;
+ if (VirtualSize < DPH_RESERVE_SIZE)
+ VirtualSize = DPH_RESERVE_SIZE;
+
+ /* Allocate the virtual memory */
+ Status = RtlpDphAllocateVm(&Base, VirtualSize, MEM_RESERVE, PAGE_NOACCESS);
+ if (!NT_SUCCESS(Status))
+ {
+ /* Free the allocated node and return failure */
+ RtlpDphReturnNodeToUnusedList(DphRoot, Node);
+ RtlpDphReturnNodeToUnusedList(DphRoot, AvailableNode);
+ return FALSE;
+ }
+
+ /* Set up our two nodes describing this VM */
+ Node->pVirtualBlock = Base;
+ Node->nVirtualBlockSize = VirtualSize;
+ AvailableNode->pVirtualBlock = Base;
+ AvailableNode->nVirtualBlockSize = VirtualSize;
+
+ /* Add them to virtual and available lists respectively */
+ RtlpDphPlaceOnVirtualList(DphRoot, Node);
+ RtlpDphCoalesceNodeIntoAvailable(DphRoot, AvailableNode);
+
+ /* Return success */
+ return TRUE;
}
RTL_GENERIC_COMPARE_RESULTS
More information about the Ros-diffs
mailing list