[PATCH v2 3/5] ntdll: De-duplicate module dependency edges.

[Jinoh Kang]

From: Jinoh Kang

Today, calling add_module_dependency() multiple times with the same
arguments results in duplicate edges.

Duplicate edges are harmless, but bloats memory usage.  The number of
duplicate edges does not affect the dependency graph; the graph is
determined by the set of unique edges.

To avoid duplicates, keep track of edges in a red-black tree, and
discard duplicate ones.  This allows us to generate a unique dependency
edge for all imports of export forwarders that belong to the same DLL.
---
 dlls/ntdll/loader.c | 46 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)

diff --git a/dlls/ntdll/loader.c b/dlls/ntdll/loader.c
index 35cf76d24dc..fedeb5746b8 100644
--- a/dlls/ntdll/loader.c
+++ b/dlls/ntdll/loader.c
@@ -34,6 +34,7 @@
 #include "wine/exception.h"
 #include "wine/debug.h"
 #include "wine/list.h"
+#include "wine/rbtree.h"
 #include "ntdll_misc.h"
 #include "ddk/ntddk.h"
 #include "ddk/wdm.h"
@@ -115,10 +116,18 @@ struct ldr_notification

static struct list ldr_notifications = LIST_INIT( ldr_notifications );

+struct dependency_key
+{
+    const LDR_DDAG_NODE *dependency_to;
+    const LDR_DDAG_NODE *dependency_from;
+};
 struct dependency_edge
 {
+    struct rb_entry entry;
     LDR_DEPENDENCY  ldr;
 };
+static int dependency_edge_cmp_rb( const void *key, const struct rb_entry *entry );
+static struct rb_tree dependency_edges = { dependency_edge_cmp_rb };

static const char * const reason_names[] =
 {
@@ -855,16 +864,47 @@ static void remove_single_list_entry( LDRP_CSLIST *list, SINGLE_LIST_ENTRY *entr
     entry->Next = NULL;
 }

+static int dependency_edge_cmp_rb( const void *key, const struct rb_entry *entry )
+{
+    const struct dependency_edge *entry_edge = RB_ENTRY_VALUE( entry, const struct dependency_edge, entry );
+    const struct dependency_key *key_ldr = key;
+
+    if ((ULONG_PTR)key_ldr->dependency_to < (ULONG_PTR)entry_edge->ldr.dependency_to) return -1;
+    if ((ULONG_PTR)key_ldr->dependency_to > (ULONG_PTR)entry_edge->ldr.dependency_to) return 1;
+    if ((ULONG_PTR)key_ldr->dependency_from < (ULONG_PTR)entry_edge->ldr.dependency_from) return -1;
+    if ((ULONG_PTR)key_ldr->dependency_from > (ULONG_PTR)entry_edge->ldr.dependency_from) return 1;
+
+    return 0;
+}
+
 /**********************************************************************
  *	    add_module_dependency_after
+ *
+ * The loader_section must be locked while calling this function.
  */
 static BOOL add_module_dependency_after( LDR_DDAG_NODE *from, LDR_DDAG_NODE *to,
                                          SINGLE_LIST_ENTRY *dep_after )
 {
+    const struct dependency_key key = { to, from };
     struct dependency_edge *dep;

if (!(dep = RtlAllocateHeap( GetProcessHeap(), 0, sizeof(*dep) ))) return FALSE;

+    if (rb_put( &dependency_edges, &key, &dep->entry ) == -1)
+    {
+        /* Duplicate dependency edge; discard edge and decrement reference of target */
+        LDR_DATA_TABLE_ENTRY *mod;
+        WINE_MODREF *wm;
+
+        RtlFreeHeap( GetProcessHeap(), 0, dep );
+
+        mod = CONTAINING_RECORD( to->Modules.Flink, LDR_DATA_TABLE_ENTRY, NodeModuleLink );
+        wm = CONTAINING_RECORD( mod, WINE_MODREF, ldr );
+        LdrUnloadDll( wm->ldr.DllBase );
+
+        return TRUE;
+    }
+
     dep->ldr.dependency_from = from;
     insert_single_list_after( &from->Dependencies, dep_after, &dep->ldr.dependency_to_entry );
     dep->ldr.dependency_to = to;
@@ -875,6 +915,8 @@ static BOOL add_module_dependency_after( LDR_DDAG_NODE *from, LDR_DDAG_NODE *to,

/**********************************************************************
  *	    add_module_dependency
+ *
+ * The loader_section must be locked while calling this function.
  */
 static BOOL add_module_dependency( LDR_DDAG_NODE *from, LDR_DDAG_NODE *to )
 {
@@ -883,11 +925,14 @@ static BOOL add_module_dependency( LDR_DDAG_NODE *from, LDR_DDAG_NODE *to )

/**********************************************************************
  *	    remove_module_dependency
+ *
+ * The loader_section must be locked while calling this function.
  */
 static void remove_module_dependency( struct dependency_edge *dep )
 {
     remove_single_list_entry( &dep->ldr.dependency_to->IncomingDependencies, &dep->ldr.dependency_from_entry );
     remove_single_list_entry( &dep->ldr.dependency_from->Dependencies, &dep->ldr.dependency_to_entry );
+    rb_remove( &dependency_edges, &dep->entry );
     RtlFreeHeap( GetProcessHeap(), 0, dep );
 }

@@ -3915,6 +3960,7 @@ void WINAPI LdrShutdownThread(void)
 /***********************************************************************
  *           free_modref
  *
+ * The loader_section must be locked while calling this function.
  */
 static void free_modref( WINE_MODREF *wm )
 {