[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...

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=506…
==============================================================================
--- 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-mo…
 */
 
 /* 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