[PATCH v3 0/2] MR4232: ntdll: Handle LFH blocks allocated in large blocks in heap_validate_ptr().

[Paul Gofman (＠gofman)]

Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=55842

The bug blames commit 059094c1c18ddc33b04eac53a72fd0eb7510be94 ("ntdll: Define heap block's BLOCK_FLAG_LFH as 0x80.") but actually before the blamed commit that worked essentially by chance.

The problem the patch is solving is that RtlValidateHeap() currently always fails for LFH blocks allocated from large block memory (vs subheap blocks). That can happen for large enough LFH block sizes. In case of the regressed game the user of RtlValidateHeap() is msvcr80.msvcrt_heap_free() which uses HeapValidate() to guess the heap used to allocate the pointer to free. I am attaching a standalone test program which can be used to reproduce the problem without the patch.
[test_lfh_validate.c](/uploads/006b04a9a00ffb7949956b66a275d5cf/test_lfh_validate.c)

--
  v3: ntdll: Fix pending free block validation in heap_validate() for LFH blocks.
      ntdll: Handle LFH blocks allocated in large blocks in heap_validate_ptr().

https://gitlab.winehq.org/wine/wine/-/merge_requests/4232

[PATCH v3 1/2] ntdll: Handle LFH blocks allocated in large blocks in heap_validate_ptr().

[Paul Gofman]

From: Paul Gofman

Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=55842
---
 dlls/ntdll/heap.c | 62 +++++++++++++++++++++++++++--------------------
 1 file changed, 36 insertions(+), 26 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index b5e2076ffae..f4faee1aa98 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1050,17 +1050,17 @@ static NTSTATUS heap_free_large( struct heap *heap, ULONG flags, struct block *b
 }

-/***********************************************************************
- *           find_large_block
- */
-static BOOL find_large_block( const struct heap *heap, const struct block *block )
+static ARENA_LARGE *find_arena_large( const struct heap *heap, const struct block *block, BOOL heap_walk )
 {
     ARENA_LARGE *arena;

LIST_FOR_EACH_ENTRY( arena, &heap->large_list, ARENA_LARGE, entry )
-        if (block == &arena->block) return TRUE;
+    {
+        if (contains( &arena->block, arena->block_size, block, 1 ))
+            return !heap_walk || block == &arena->block ? arena : NULL;
+    }

-    return FALSE;
+    return NULL;
 }

static BOOL validate_large_block( const struct heap *heap, const struct block *block )
@@ -1220,11 +1220,35 @@ static BOOL validate_free_block( const struct heap *heap, const SUBHEAP *subheap
 static BOOL validate_used_block( const struct heap *heap, const SUBHEAP *subheap, const struct block *block,
                                  unsigned int expected_block_type )
 {
-    const char *err = NULL, *base = subheap_base( subheap ), *commit_end = subheap_commit_end( subheap );
+    const char *err = NULL, *base = NULL, *commit_end;
     DWORD flags = heap->flags;
     const struct block *next;
+    ARENA_LARGE *arena_large;
     int i;

+    if (subheap)
+    {
+        base = subheap_base( subheap );
+        commit_end = subheap_commit_end( subheap );
+    }
+    else if ((arena_large = find_arena_large( heap, block, FALSE )))
+    {
+        if (!validate_large_block( heap, &arena_large->block )) return FALSE;
+        if (block == &arena_large->block) return TRUE;
+
+        if (contains( &arena_large->block + 1, arena_large->data_size, block, sizeof(*block) )
+            && block_get_flags( block ) & BLOCK_FLAG_LFH)
+        {
+            base = (const char *)(&arena_large->block + 1);
+            commit_end = base + arena_large->data_size;
+        }
+    }
+    if (!base)
+    {
+        WARN( "heap %p, ptr %p: block region not found.\n", heap, block + 1 );
+        return FALSE;
+    }
+
     if ((ULONG_PTR)(block + 1) % BLOCK_ALIGN)
         err = "invalid block BLOCK_ALIGN";
     else if (block_get_type( block ) != BLOCK_TYPE_USED && block_get_type( block ) != BLOCK_TYPE_DEAD)
@@ -1237,9 +1261,8 @@ static BOOL validate_used_block( const struct heap *heap, const SUBHEAP *subheap
         err = "invalid block size";
     else if (block->tail_size > block_get_size( block ) - sizeof(*block))
         err = "invalid block unused size";
-    else if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_PREV_FREE) &&
-             /* LFH blocks do not use BLOCK_FLAG_PREV_FREE or back pointer */
-             !(block_get_flags( block ) & BLOCK_FLAG_LFH))
+    else if (!(block_get_flags( block ) & BLOCK_FLAG_LFH) /* LFH blocks do not use BLOCK_FLAG_PREV_FREE or back pointer */
+             && (next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_PREV_FREE))
         err = "invalid next block flags";
     else if (block_get_flags( block ) & BLOCK_FLAG_PREV_FREE)
     {
@@ -1280,20 +1303,8 @@ static BOOL validate_used_block( const struct heap *heap, const SUBHEAP *subheap
 static BOOL heap_validate_ptr( const struct heap *heap, const void *ptr )
 {
     const struct block *block = (struct block *)ptr - 1;
-    const SUBHEAP *subheap;
-
-    if (!(subheap = find_subheap( heap, block, FALSE )))
-    {
-        if (!find_large_block( heap, block ))
-        {
-            WARN("heap %p, ptr %p: block region not found\n", heap, ptr );
-            return FALSE;
-        }

-        return validate_large_block( heap, block );
-    }
-
-    return validate_used_block( heap, subheap, block, BLOCK_TYPE_USED );
+    return validate_used_block( heap, find_subheap( heap, block, FALSE ), block, BLOCK_TYPE_USED );
 }

static BOOL heap_validate( const struct heap *heap )
@@ -2448,7 +2459,7 @@ static NTSTATUS heap_walk_blocks( const struct heap *heap, const SUBHEAP *subhea
 static NTSTATUS heap_walk( const struct heap *heap, struct rtl_heap_entry *entry )
 {
     const char *data = entry->lpData;
-    const ARENA_LARGE *large = NULL;
+    const ARENA_LARGE *large;
     const struct block *block;
     const struct list *next;
     const SUBHEAP *subheap;
@@ -2459,9 +2470,8 @@ static NTSTATUS heap_walk( const struct heap *heap, struct rtl_heap_entry *entry
     else if (entry->wFlags & RTL_HEAP_ENTRY_BUSY) block = (struct block *)data - 1;
     else block = (struct block *)(data - sizeof(struct list)) - 1;

-    if (find_large_block( heap, block ))
+    if ((large = find_arena_large( heap, block, TRUE )))
     {
-        large = CONTAINING_RECORD( block, ARENA_LARGE, block );
         next = &large->entry;
     }
     else if ((subheap = find_subheap( heap, block, TRUE )))

[PATCH v3 2/2] ntdll: Fix pending free block validation in heap_validate() for LFH blocks.

[Paul Gofman]

From: Paul Gofman

---
 dlls/ntdll/heap.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index f4faee1aa98..72fc23b9f3e 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1343,15 +1343,11 @@ static BOOL heap_validate( const struct heap *heap )
         {
             if (!(block = heap->pending_free[i])) break;

-            subheap = find_subheap( heap, block, FALSE );
-            if (!subheap)
+            if (!validate_used_block( heap, find_subheap( heap, block, FALSE ), block, BLOCK_TYPE_DEAD ))
             {
-                ERR( "heap %p: cannot find valid subheap for delayed freed block %p\n", heap, block );
-                if (TRACE_ON(heap)) heap_dump( heap );
+                ERR( "heap %p: failed to to validate delayed free block %p\n", heap, block );
                 return FALSE;
             }
-
-            if (!validate_used_block( heap, subheap, block, BLOCK_TYPE_DEAD )) return FALSE;
         }

for (; i < MAX_FREE_PENDING; i++)

[Paul Gofman (＠gofman)]

v3:
 - changed condition for pre-checking LFH block: check for fitting large block range first and include full block header size in the check.

[Rémi Bernon (＠rbernon)]

Rémi Bernon (@rbernon) commented about dlls/ntdll/heap.c:
>  int i;
>
> - if (subheap)
> - {
> -
>    base = subheap_base( subheap );
> -
>    commit_end = subheap_commit_end( subheap );
> - }
> - else if ((arena_large = find_arena_large( heap, block, FALSE )))
> - {
> -
>    if (!validate_large_block( heap, &arena_large->block )) return FALSE;
> -
>    if (block == &arena_large->block) return TRUE;
> -
> -
>    if (contains( &arena_large->block + 1, arena_large->data_size, block, sizeof(*block) )
> -
>        && block_get_flags( block ) & BLOCK_FLAG_LFH)
> -
>    {
> -
>        base = (const char *)(&arena_large->block + 1);

We should keep the invariant of `base` being aligned to REGION_ALIGN.

[Rémi Bernon (＠rbernon)]

On Mon Nov  6 10:03:22 2023 +0000, Rémi Bernon wrote:
> We should keep the invariant of `base` being aligned to REGION_ALIGN.

I mean something like this:

```suggestion:-0+1
            base = ROUND_ADDR( arena_large, REGION_ALIGN - 1 );
            commit_end = (char *)(arena_large + 1) + arena_large->data_size;
```

Fwiw, I didn't get to it but my plan was to merge the SUBHEAP and arena_large structures together in a single `struct region`.