[PATCH 0/3] MR6792: ntdll: Implement HashLinks field in LDR module data.

[PATCH 1/3] ntdll: Implement HashLinks field in LDR module data.

[Michael Müller]

From: Michael Müller

Changed by Paul Gofman in Wine-Staging patch:
 - remove older hash version support;
 - split off the test in a separate patch;
 - remove unrelated InInitializationOrderLinks nullification;
 - remove a comment.
---
 dlls/ntdll/loader.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/dlls/ntdll/loader.c b/dlls/ntdll/loader.c
index 2f2a7fe5427..edd85c422a9 100644
--- a/dlls/ntdll/loader.c
+++ b/dlls/ntdll/loader.c
@@ -128,6 +128,9 @@ struct file_id
     BYTE ObjectId[16];
 };

+#define HASH_MAP_SIZE 32
+static LIST_ENTRY hash_table[HASH_MAP_SIZE];
+
 /* internal representation of loaded modules */
 typedef struct _wine_modref
 {
@@ -600,6 +603,16 @@ static int base_address_compare( const void *key, const RTL_BALANCED_NODE *entry
     return 0;
 }

+/* compute basename hash */
+static ULONG hash_basename( const WCHAR *basename )
+{
+    ULONG hash = 0;
+    WCHAR c;
+
+    while ((c = *basename++)) hash = hash * 65599 + towupper( c );
+    return hash & (HASH_MAP_SIZE - 1);
+}
+
 /*************************************************************************
  *		get_modref
  *
@@ -1596,6 +1609,8 @@ static WINE_MODREF *alloc_module( HMODULE hModule, const UNICODE_STRING *nt_name
                    &wm->ldr.InLoadOrderLinks);
     InsertTailList(&NtCurrentTeb()->Peb->LdrData->InMemoryOrderModuleList,
                    &wm->ldr.InMemoryOrderLinks);
+    InsertTailList(&hash_table[hash_basename( wm->ldr.BaseDllName.Buffer )],
+                   &wm->ldr.HashLinks);
     if (rtl_rb_tree_put( &base_address_index_tree, wm->ldr.DllBase, &wm->ldr.BaseAddressIndexNode, base_address_compare ))
         ERR( "rtl_rb_tree_put failed.\n" );
     /* wait until init is called for inserting into InInitializationOrderModuleList */
@@ -2296,6 +2311,7 @@ static NTSTATUS build_module( LPCWSTR load_path, const UNICODE_STRING *nt_name,
             /* the module has only be inserted in the load & memory order lists */
             RemoveEntryList(&wm->ldr.InLoadOrderLinks);
             RemoveEntryList(&wm->ldr.InMemoryOrderLinks);
+            RemoveEntryList(&wm->ldr.HashLinks);
             RtlRbRemoveNode( &base_address_index_tree, &wm->ldr.BaseAddressIndexNode );

/* FIXME: there are several more dangling references
@@ -3966,6 +3982,7 @@ static void free_modref( WINE_MODREF *wm )

RemoveEntryList(&wm->ldr.InLoadOrderLinks);
     RemoveEntryList(&wm->ldr.InMemoryOrderLinks);
+    RemoveEntryList(&wm->ldr.HashLinks);
     RtlRbRemoveNode( &base_address_index_tree, &wm->ldr.BaseAddressIndexNode );
     if (wm->ldr.InInitializationOrderLinks.Flink)
         RemoveEntryList(&wm->ldr.InInitializationOrderLinks);
@@ -4387,6 +4404,7 @@ void loader_init( CONTEXT *context, void **entry )
         ANSI_STRING ctrl_routine = RTL_CONSTANT_STRING( "CtrlRoutine" );
         WINE_MODREF *kernel32;
         PEB *peb = NtCurrentTeb()->Peb;
+        unsigned int i;

peb->LdrData            = &ldr;
         peb->FastPebLock        = &peb_lock;
@@ -4405,6 +4423,9 @@ void loader_init( CONTEXT *context, void **entry )
         if (!(tls_dirs = RtlAllocateHeap( GetProcessHeap(), HEAP_ZERO_MEMORY, tls_module_count * sizeof(*tls_dirs) )))
             NtTerminateProcess( GetCurrentProcess(), STATUS_NO_MEMORY );

+        for (i = 0; i < HASH_MAP_SIZE; i++)
+            InitializeListHead( &hash_table[i] );
+
         init_user_process_params();
         load_global_options();
         version_init();

[PATCH 2/3] kernel32: Add tests for module hash links.

[Paul Gofman]

From: Paul Gofman

Based on a patch by Michael Müller .
---
 dlls/kernel32/tests/module.c | 45 ++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

diff --git a/dlls/kernel32/tests/module.c b/dlls/kernel32/tests/module.c
index 8f3ed5872e4..e38320f537b 100644
--- a/dlls/kernel32/tests/module.c
+++ b/dlls/kernel32/tests/module.c
@@ -1802,6 +1802,50 @@ static void test_base_address_index_tree(void)
     ok( tree_count == list_count, "count mismatch %u, %u.\n", tree_count, list_count );
 }

+static ULONG hash_basename( const WCHAR *basename )
+{
+    WORD version = MAKEWORD(NtCurrentTeb()->Peb->OSMinorVersion, NtCurrentTeb()->Peb->OSMajorVersion);
+    ULONG hash = 0;
+    WCHAR c;
+
+    while ((c = *basename++))
+    {
+        c = towupper( c );
+        if (version >= 0x0602)      hash = hash * 65599 + c;
+        else if (version == 0x0601) hash = hash + 65599 * c;
+        else                        hash = c - 'A';
+    }
+
+    return hash & 31;
+}
+
+static void test_hash_links(void)
+{
+    LIST_ENTRY *hash_map, *entry, *entry2, *mark, *root;
+    LDR_DATA_TABLE_ENTRY *module;
+    const WCHAR *modname;
+    BOOL found;
+
+    root = &NtCurrentTeb()->Peb->LdrData->InLoadOrderModuleList;
+    module = CONTAINING_RECORD(root->Flink, LDR_DATA_TABLE_ENTRY, InLoadOrderLinks);
+    hash_map = module->HashLinks.Blink - hash_basename( module->BaseDllName.Buffer );
+
+    for (entry = root->Flink; entry != root; entry = entry->Flink)
+    {
+        module = CONTAINING_RECORD(entry, LDR_DATA_TABLE_ENTRY, InLoadOrderLinks);
+        modname = module->BaseDllName.Buffer;
+        mark = &hash_map[hash_basename( modname )];
+        found = FALSE;
+        for (entry2 = mark->Flink; entry2 != mark; entry2 = entry2->Flink)
+        {
+            module = CONTAINING_RECORD(entry2, LDR_DATA_TABLE_ENTRY, HashLinks);
+            trace("%s %s.\n", debugstr_w(modname), debugstr_w(module->BaseDllName.Buffer));
+            if ((found = !lstrcmpiW( module->BaseDllName.Buffer, modname ))) break;
+        }
+        ok( found, "Could not find %s.\n", debugstr_w(modname) );
+    }
+}
+
 START_TEST(module)
 {
     WCHAR filenameW[MAX_PATH];
@@ -1840,4 +1884,5 @@ START_TEST(module)
     test_ddag_node();
     test_tls_links();
     test_base_address_index_tree();
+    test_hash_links();
 }

[PATCH 3/3] ntdll: Use HashLinks when searching for a dll using the basename.

[Michael Müller]

From: Michael Müller

---
 dlls/ntdll/loader.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/dlls/ntdll/loader.c b/dlls/ntdll/loader.c
index edd85c422a9..a60cf84a2d2 100644
--- a/dlls/ntdll/loader.c
+++ b/dlls/ntdll/loader.c
@@ -648,10 +648,10 @@ static WINE_MODREF *find_basename_module( LPCWSTR name )
     if (cached_modref && RtlEqualUnicodeString( &name_str, &cached_modref->ldr.BaseDllName, TRUE ))
         return cached_modref;

-    mark = &NtCurrentTeb()->Peb->LdrData->InLoadOrderModuleList;
+    mark = &hash_table[hash_basename( name )];
     for (entry = mark->Flink; entry != mark; entry = entry->Flink)
     {
-        WINE_MODREF *mod = CONTAINING_RECORD(entry, WINE_MODREF, ldr.InLoadOrderLinks);
+        WINE_MODREF *mod = CONTAINING_RECORD(entry, WINE_MODREF, ldr.HashLinks);
         if (RtlEqualUnicodeString( &name_str, &mod->ldr.BaseDllName, TRUE ) && !mod->system)
         {
             cached_modref = CONTAINING_RECORD(mod, WINE_MODREF, ldr);

[Paul Gofman (＠gofman)]

This was in Wine-Staging for a long time. I don't know which apps depended on that originally but now that is at least Farlight 84 and Test Drive Unlimited Solar Crown.

[PATCH 0/3] MR6792: ntdll: Implement HashLinks field in LDR module data. - approved

[Paul Gofman (＠gofman)]

This merge request was approved by Paul Gofman.

[Nikolay Sivov (＠nsivov)]

Hashing helper duplicates RtlHashUnicodeString(), I don't know if we want to use it, but I think we might.