[PATCH 0/6] MR1548: ntdll: Relax heap locking to access block information.

[Rémi Bernon]

We are currently locking the heap to iterate over the allocated regions, in order to check whether a pointer / block really belongs to one of them. This is not what native does it, as HeapFree / HeapReAlloc / HeapSize crashing on invalid pointers shows. This also makes it hard to improve the heap performance in multi-threaded scenarios.

This series reduces the locking requirement by keeping the region header offset in each block, relaxing the pointer checks, and assuming a heap region stays valid until all of its blocks have been freed. This also removes the locking requirement when accessing block level information, such as block type or flags or block user info. I'm assuming here that concurrent calls to heap functions on a given block are undefined.

Anything that involves modifying the block size, type or flags, walking the heap, or explicit validation still requires entering the heap lock.

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

[PATCH 1/6] ntdll: Keep the region base offset in the block header.

[Rémi Bernon]

From: Rémi Bernon <rbernon(a)codeweavers.com>

---
 dlls/ntdll/heap.c | 36 +++++++++++++++++++++++++++++-------
 1 file changed, 29 insertions(+), 7 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index cb1ff12c679..f661a05ed65 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -82,7 +82,8 @@ struct block
     WORD block_size;   /* block size in multiple of BLOCK_ALIGN */
     BYTE block_flags;
     BYTE tail_size;    /* unused size (used block) / high size bits (free block) */
-    DWORD block_type;
+    WORD base_offset;  /* offset to the region base in multiple of REGION_ALIGN */
+    WORD block_type;
 };
 
 C_ASSERT( sizeof(struct block) == 8 );
@@ -123,10 +124,10 @@ typedef struct
 C_ASSERT( sizeof(ARENA_LARGE) == offsetof(ARENA_LARGE, block) + sizeof(struct block) );
 C_ASSERT( sizeof(ARENA_LARGE) == 4 * BLOCK_ALIGN );
 
-#define BLOCK_TYPE_USED        0x455355
-#define BLOCK_TYPE_DEAD        0xbedead
-#define BLOCK_TYPE_FREE        0x45455246
-#define BLOCK_TYPE_LARGE       0x6752614c
+#define BLOCK_TYPE_USED        0x5355
+#define BLOCK_TYPE_DEAD        0xdead
+#define BLOCK_TYPE_FREE        0x5246
+#define BLOCK_TYPE_LARGE       0x614c
 
 #define BLOCK_FILL_USED        0x55
 #define BLOCK_FILL_TAIL        0xab
@@ -134,14 +135,26 @@ C_ASSERT( sizeof(ARENA_LARGE) == 4 * BLOCK_ALIGN );
 
 #define ROUND_ADDR(addr, mask) ((void *)((UINT_PTR)(addr) & ~(UINT_PTR)(mask)))
 #define ROUND_SIZE(size, mask) ((((SIZE_T)(size) + (mask)) & ~(SIZE_T)(mask)))
+#define FIELD_MAX(type, field) (((SIZE_T)1 << (sizeof(((type *)0)->field) * 8)) - 1)
 
 #define HEAP_MIN_BLOCK_SIZE   ROUND_SIZE(sizeof(struct entry) + BLOCK_ALIGN, BLOCK_ALIGN - 1)
 
 C_ASSERT( sizeof(struct block) <= HEAP_MIN_BLOCK_SIZE );
 C_ASSERT( sizeof(struct entry) <= HEAP_MIN_BLOCK_SIZE );
 
+/* used block size is coded into block_size */
+#define HEAP_MAX_USED_BLOCK_SIZE    (FIELD_MAX( struct block, block_size ) * BLOCK_ALIGN)
+/* free block size is coded into block_size + tail_size */
+#define HEAP_MAX_FREE_BLOCK_SIZE    (HEAP_MAX_USED_BLOCK_SIZE + (FIELD_MAX( struct block, tail_size ) << 16) * BLOCK_ALIGN)
+/* subheap distance is coded into base_offset */
+#define HEAP_MAX_BLOCK_REGION_SIZE  (FIELD_MAX( struct block, base_offset ) * REGION_ALIGN)
+
+C_ASSERT( HEAP_MAX_USED_BLOCK_SIZE == 512 * 1024 * (sizeof(void *) / 4) - BLOCK_ALIGN );
+C_ASSERT( HEAP_MAX_FREE_BLOCK_SIZE == 128 * 1024 * 1024 * (sizeof(void *) / 4) - BLOCK_ALIGN );
+C_ASSERT( HEAP_MAX_BLOCK_REGION_SIZE >= HEAP_MAX_FREE_BLOCK_SIZE );
+
 /* minimum size to start allocating large blocks */
-#define HEAP_MIN_LARGE_BLOCK_SIZE  (0x10000 * BLOCK_ALIGN - 0x1000)
+#define HEAP_MIN_LARGE_BLOCK_SIZE  (HEAP_MAX_USED_BLOCK_SIZE - 0x1000)
 
 /* There will be a free list bucket for every arena size up to and including this value */
 #define HEAP_MAX_SMALL_FREE_LIST 0x100
@@ -233,6 +246,12 @@ static inline UINT block_get_type( const struct block *block )
     return block->block_type;
 }
 
+static inline void block_set_base( struct block *block, const void *base )
+{
+    const char *offset = ROUND_ADDR( block, REGION_ALIGN - 1 );
+    block->base_offset = (offset - (char *)base) / REGION_ALIGN;
+}
+
 static inline void block_set_type( struct block *block, UINT type )
 {
     block->block_type = type;
@@ -689,6 +708,7 @@ static void create_free_block( struct heap *heap, ULONG flags, SUBHEAP *subheap,
 
     valgrind_make_writable( block, sizeof(*entry) );
     block_set_type( block, BLOCK_TYPE_FREE );
+    block_set_base( block, subheap_base( subheap ) );
     block_set_flags( block, ~0, BLOCK_FLAG_FREE );
     block_set_size( block, block_size );
 
@@ -812,6 +832,7 @@ static struct block *allocate_large_block( struct heap *heap, DWORD flags, SIZE_
     arena->block_size = (char *)address + total_size - (char *)block;
 
     block_set_type( block, BLOCK_TYPE_LARGE );
+    block_set_base( block, arena );
     block_set_flags( block, ~0, BLOCK_FLAG_LARGE | BLOCK_USER_FLAGS( flags ) );
     block_set_size( block, 0 );
     list_add_tail( &heap->large_list, &arena->entry );
@@ -980,6 +1001,7 @@ static SUBHEAP *HEAP_CreateSubHeap( struct heap **heap_ptr, LPVOID address, DWOR
             block_set_flags( &pEntry->block, ~0, BLOCK_FLAG_FREE_LINK );
             block_set_size( &pEntry->block, 0 );
             block_set_type( &pEntry->block, BLOCK_TYPE_FREE );
+            block_set_base( &pEntry->block, heap );
             if (i) list_add_after( &pEntry[-1].entry, &pEntry->entry );
         }
 
@@ -1049,7 +1071,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo
     if ((*subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size,
                                         max( heap->grow_size, total_size ) )))
     {
-        if (heap->grow_size < 128 * 1024 * 1024) heap->grow_size *= 2;
+        if (heap->grow_size <= HEAP_MAX_FREE_BLOCK_SIZE / 2) heap->grow_size *= 2;
     }
     else while (!*subheap)  /* shrink the grow size again if we are running out of space */
     {
-- 
GitLab


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

[PATCH 2/6] ntdll: Find heap block region from its base offset.

[Rémi Bernon]

From: Rémi Bernon <rbernon(a)codeweavers.com>

---
 dlls/ntdll/heap.c | 114 +++++++++++++++++++++++++---------------------
 1 file changed, 61 insertions(+), 53 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index f661a05ed65..ea1821aa674 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -257,6 +257,14 @@ static inline void block_set_type( struct block *block, UINT type )
     block->block_type = type;
 }
 
+static inline SUBHEAP *block_get_subheap( const struct heap *heap, const struct block *block )
+{
+    char *offset = ROUND_ADDR( block, REGION_ALIGN - 1 );
+    void *base = offset - block->base_offset * REGION_ALIGN;
+    if (base != (void *)heap) return base;
+    else return (SUBHEAP *)&heap->subheap;
+}
+
 static inline UINT block_get_overhead( const struct block *block )
 {
     if (block_get_flags( block ) & BLOCK_FLAG_FREE) return sizeof(*block) + sizeof(struct list);
@@ -741,10 +749,11 @@ static void create_free_block( struct heap *heap, ULONG flags, SUBHEAP *subheap,
 }
 
 
-static void free_used_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, struct block *block )
+static void free_used_block( struct heap *heap, ULONG flags, struct block *block )
 {
     struct entry *entry;
     SIZE_T block_size;
+    SUBHEAP *subheap;
 
     if (heap->pending_free)
     {
@@ -753,7 +762,7 @@ static void free_used_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, s
         heap->pending_pos = (heap->pending_pos + 1) % MAX_FREE_PENDING;
         block_set_type( block, BLOCK_TYPE_DEAD );
         mark_block_free( block + 1, block_get_size( block ) - sizeof(*block), flags );
-        if (!(block = tmp) || !(subheap = find_subheap( heap, block, FALSE ))) return;
+        if (!(block = tmp)) return;
     }
 
     block_size = block_get_size( block );
@@ -767,6 +776,7 @@ static void free_used_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, s
     }
     else entry = (struct entry *)block;
 
+    subheap = block_get_subheap( heap, block );
     create_free_block( heap, flags, subheap, block, block_size );
     if (next_block( subheap, block )) return;  /* not the last block */
 
@@ -788,9 +798,11 @@ static void free_used_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, s
 }
 
 
-static inline void shrink_used_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, struct block *block,
+static inline void shrink_used_block( struct heap *heap, ULONG flags, struct block *block,
                                       SIZE_T old_block_size, SIZE_T block_size, SIZE_T size )
 {
+    SUBHEAP *subheap = block_get_subheap( heap, block );
+
     if (old_block_size >= block_size + HEAP_MIN_BLOCK_SIZE)
     {
         block_set_size( block, block_size );
@@ -1033,12 +1045,13 @@ static SUBHEAP *HEAP_CreateSubHeap( struct heap **heap_ptr, LPVOID address, DWOR
 }
 
 
-static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T block_size, SUBHEAP **subheap )
+static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T block_size )
 {
     struct list *ptr = &find_free_list( heap, block_size, FALSE )->entry;
     struct entry *entry;
     struct block *block;
     SIZE_T total_size;
+    SUBHEAP *subheap;
 
     /* Find a suitable free list, and in it find a block large enough */
 
@@ -1049,8 +1062,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo
         if (block_get_flags( block ) == BLOCK_FLAG_FREE_LINK) continue;
         if (block_get_size( block ) >= block_size)
         {
-            *subheap = find_subheap( heap, block, FALSE );
-            if (!subheap_commit( heap, *subheap, block, block_size )) return NULL;
+            if (!subheap_commit( heap, block_get_subheap( heap, block ), block, block_size )) return NULL;
             list_remove( &entry->entry );
             return block;
         }
@@ -1068,22 +1080,22 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo
     total_size = sizeof(SUBHEAP) + block_size + sizeof(struct entry);
     if (total_size < block_size) return NULL;  /* overflow */
 
-    if ((*subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size,
+    if ((subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size,
                                         max( heap->grow_size, total_size ) )))
     {
         if (heap->grow_size <= HEAP_MAX_FREE_BLOCK_SIZE / 2) heap->grow_size *= 2;
     }
-    else while (!*subheap)  /* shrink the grow size again if we are running out of space */
+    else while (!subheap)  /* shrink the grow size again if we are running out of space */
     {
         if (heap->grow_size <= total_size || heap->grow_size <= 4 * 1024 * 1024) return NULL;
         heap->grow_size /= 2;
-        *subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size,
+        subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size,
                                        max( heap->grow_size, total_size ) );
     }
 
-    TRACE( "created new sub-heap %p of %#Ix bytes for heap %p\n", *subheap, subheap_size( *subheap ), heap );
+    TRACE( "created new sub-heap %p of %#Ix bytes for heap %p\n", subheap, subheap_size( subheap ), heap );
 
-    entry = first_block( *subheap );
+    entry = first_block( subheap );
     list_remove( &entry->entry );
     return &entry->block;
 }
@@ -1207,11 +1219,12 @@ static BOOL validate_used_block( const struct heap *heap, const SUBHEAP *subheap
 }
 
 
-static BOOL heap_validate_ptr( const struct heap *heap, const void *ptr, 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 (!(subheap = find_subheap( heap, block, FALSE )))
     {
         if (!find_large_block( heap, block ))
         {
@@ -1222,7 +1235,7 @@ static BOOL heap_validate_ptr( const struct heap *heap, const void *ptr, SUBHEAP
         return validate_large_block( heap, block );
     }
 
-    return validate_used_block( heap, *subheap, block );
+    return validate_used_block( heap, subheap, block );
 }
 
 static BOOL heap_validate( const struct heap *heap )
@@ -1259,36 +1272,38 @@ static BOOL heap_validate( const struct heap *heap )
     return TRUE;
 }
 
-static inline struct block *unsafe_block_from_ptr( const struct heap *heap, const void *ptr, SUBHEAP **subheap )
+static inline struct block *unsafe_block_from_ptr( const struct heap *heap, const void *ptr )
 {
     struct block *block = (struct block *)ptr - 1;
-    const char *err = NULL, *base, *commit_end;
+    const char *err = NULL;
+    SUBHEAP *subheap;
 
     if (heap->flags & HEAP_VALIDATE)
     {
-        if (!heap_validate_ptr( heap, ptr, subheap )) return NULL;
+        if (!heap_validate_ptr( heap, ptr )) return NULL;
         return block;
     }
 
-    if ((*subheap = find_subheap( heap, block, FALSE )))
+    if ((ULONG_PTR)ptr % BLOCK_ALIGN)
+        err = "invalid ptr alignment";
+    else if ((subheap = block_get_subheap( heap, block )) >= (SUBHEAP *)block)
+        err = "invalid base offset";
+    else if (block_get_type( block ) == BLOCK_TYPE_USED)
     {
-        base = subheap_base( *subheap );
-        commit_end = subheap_commit_end( *subheap );
+        const char *base = subheap_base( subheap ), *commit_end = subheap_commit_end( subheap );
+        if (!contains( base, commit_end - base, block, block_get_size( block ) )) err = "invalid block size";
     }
-
-    if (!*subheap)
+    else if (block_get_type( block ) == BLOCK_TYPE_LARGE)
     {
-        if (find_large_block( heap, block )) return block;
-        err = "block region not found";
+        ARENA_LARGE *large = subheap_base( subheap );
+        if (block != &large->block) err = "invalid large block";
     }
-    else if ((ULONG_PTR)ptr % BLOCK_ALIGN)
-        err = "invalid ptr BLOCK_ALIGN";
-    else if (block_get_type( block ) == BLOCK_TYPE_DEAD || (block_get_flags( block ) & BLOCK_FLAG_FREE))
+    else if (block_get_type( block ) == BLOCK_TYPE_DEAD)
+        err = "delayed freed block";
+    else if (block_get_type( block ) == BLOCK_TYPE_FREE)
         err = "already freed block";
-    else if (block_get_type( block ) != BLOCK_TYPE_USED)
-        err = "invalid block header";
-    else if (!contains( base, commit_end - base, block, block_get_size( block ) ))
-        err = "invalid block size";
+    else
+        err = "invalid block type";
 
     if (err) WARN( "heap %p, block %p: %s\n", heap, block, err );
     return err ? NULL : block;
@@ -1465,8 +1480,7 @@ HANDLE WINAPI RtlDestroyHeap( HANDLE handle )
     {
         heap->pending_free = NULL;
         for (tmp = pending; *tmp && tmp != pending + MAX_FREE_PENDING; ++tmp)
-            if ((subheap = find_subheap( heap, *tmp, FALSE )))
-                free_used_block( heap, heap->flags, subheap, *tmp );
+            free_used_block( heap, heap->flags, *tmp );
         RtlFreeHeap( handle, 0, pending );
     }
 
@@ -1527,7 +1541,6 @@ static NTSTATUS heap_allocate( struct heap *heap, ULONG flags, SIZE_T block_size
 {
     SIZE_T old_block_size;
     struct block *block;
-    SUBHEAP *subheap;
 
     if (block_size >= HEAP_MIN_LARGE_BLOCK_SIZE)
     {
@@ -1539,13 +1552,13 @@ static NTSTATUS heap_allocate( struct heap *heap, ULONG flags, SIZE_T block_size
 
     /* Locate a suitable free block */
 
-    if (!(block = find_free_block( heap, flags, block_size, &subheap ))) return STATUS_NO_MEMORY;
+    if (!(block = find_free_block( heap, flags, block_size ))) return STATUS_NO_MEMORY;
     /* read the free block size, changing block type or flags may alter it */
     old_block_size = block_get_size( block );
 
     block_set_type( block, BLOCK_TYPE_USED );
     block_set_flags( block, ~0, BLOCK_USER_FLAGS( flags ) );
-    shrink_used_block( heap, flags, subheap, block, old_block_size, block_size, size );
+    shrink_used_block( heap, flags, block, old_block_size, block_size, size );
     initialize_block( block, 0, size, flags );
     mark_block_tail( block, flags );
 
@@ -1586,11 +1599,10 @@ void *WINAPI DECLSPEC_HOTPATCH RtlAllocateHeap( HANDLE handle, ULONG flags, SIZE
 static NTSTATUS heap_free( struct heap *heap, ULONG flags, void *ptr )
 {
     struct block *block;
-    SUBHEAP *subheap;
 
-    if (!(block = unsafe_block_from_ptr( heap, ptr, &subheap ))) return STATUS_INVALID_PARAMETER;
+    if (!(block = unsafe_block_from_ptr( heap, ptr ))) return STATUS_INVALID_PARAMETER;
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE) free_large_block( heap, block );
-    else free_used_block( heap, flags, subheap, block );
+    else free_used_block( heap, flags, block );
 
     return STATUS_SUCCESS;
 }
@@ -1628,10 +1640,9 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
 {
     SIZE_T old_block_size, old_size;
     struct block *next, *block;
-    SUBHEAP *subheap;
     NTSTATUS status;
 
-    if (!(block = unsafe_block_from_ptr( heap, ptr, &subheap ))) return STATUS_INVALID_PARAMETER;
+    if (!(block = unsafe_block_from_ptr( heap, ptr ))) return STATUS_INVALID_PARAMETER;
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE)
     {
         if (!(block = realloc_large_block( heap, flags, block, size ))) return STATUS_NO_MEMORY;
@@ -1646,6 +1657,8 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
     old_size = old_block_size - block_get_overhead( block );
     if (block_size > old_block_size)
     {
+        SUBHEAP *subheap = block_get_subheap( heap, block );
+
         if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE) &&
             block_size < HEAP_MIN_LARGE_BLOCK_SIZE && block_size <= old_block_size + block_get_size( next ))
         {
@@ -1663,14 +1676,14 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
             memcpy( *ret, block + 1, old_size );
             if (flags & HEAP_ZERO_MEMORY) memset( (char *)*ret + old_size, 0, size - old_size );
             valgrind_notify_free( ptr );
-            free_used_block( heap, flags, subheap, block );
+            free_used_block( heap, flags, block );
             return STATUS_SUCCESS;
         }
     }
 
     valgrind_notify_resize( block + 1, old_size, size );
     block_set_flags( block, BLOCK_FLAG_USER_MASK, BLOCK_USER_FLAGS( flags ) );
-    shrink_used_block( heap, flags, subheap, block, old_block_size, block_size, size );
+    shrink_used_block( heap, flags, block, old_block_size, block_size, size );
 
     initialize_block( block, old_size, size, flags );
     mark_block_tail( block, flags );
@@ -1779,9 +1792,8 @@ BOOLEAN WINAPI RtlUnlockHeap( HANDLE handle )
 static NTSTATUS heap_size( const struct heap *heap, const void *ptr, SIZE_T *size )
 {
     const struct block *block;
-    SUBHEAP *subheap;
 
-    if (!(block = unsafe_block_from_ptr( heap, ptr, &subheap ))) return STATUS_INVALID_PARAMETER;
+    if (!(block = unsafe_block_from_ptr( heap, ptr ))) return STATUS_INVALID_PARAMETER;
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE)
     {
         const ARENA_LARGE *large_arena = CONTAINING_RECORD( block, ARENA_LARGE, block );
@@ -1823,7 +1835,6 @@ SIZE_T WINAPI RtlSizeHeap( HANDLE handle, ULONG flags, const void *ptr )
 BOOLEAN WINAPI RtlValidateHeap( HANDLE handle, ULONG flags, const void *ptr )
 {
     struct heap *heap;
-    SUBHEAP *subheap;
     ULONG heap_flags;
     BOOLEAN ret;
 
@@ -1832,7 +1843,7 @@ BOOLEAN WINAPI RtlValidateHeap( HANDLE handle, ULONG flags, const void *ptr )
     else
     {
         heap_lock( heap, heap_flags );
-        if (ptr) ret = heap_validate_ptr( heap, ptr, &subheap );
+        if (ptr) ret = heap_validate_ptr( heap, ptr );
         else ret = heap_validate( heap );
         heap_unlock( heap, heap_flags );
     }
@@ -2042,7 +2053,6 @@ BOOLEAN WINAPI RtlGetUserInfoHeap( HANDLE handle, ULONG flags, void *ptr, void *
     NTSTATUS status = STATUS_SUCCESS;
     struct block *block;
     struct heap *heap;
-    SUBHEAP *subheap;
     ULONG heap_flags;
     char *tmp;
 
@@ -2054,7 +2064,7 @@ BOOLEAN WINAPI RtlGetUserInfoHeap( HANDLE handle, ULONG flags, void *ptr, void *
     if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags ))) return TRUE;
 
     heap_lock( heap, heap_flags );
-    if (!(block = unsafe_block_from_ptr( heap, ptr, &subheap )))
+    if (!(block = unsafe_block_from_ptr( heap, ptr )))
     {
         WARN( "Failed to find block %p in heap %p\n", ptr, handle );
         status = STATUS_INVALID_PARAMETER;
@@ -2089,7 +2099,6 @@ BOOLEAN WINAPI RtlSetUserValueHeap( HANDLE handle, ULONG flags, void *ptr, void
     struct block *block;
     BOOLEAN ret = FALSE;
     struct heap *heap;
-    SUBHEAP *subheap;
     ULONG heap_flags;
     char *tmp;
 
@@ -2098,7 +2107,7 @@ BOOLEAN WINAPI RtlSetUserValueHeap( HANDLE handle, ULONG flags, void *ptr, void
     if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags ))) return TRUE;
 
     heap_lock( heap, heap_flags );
-    if (!(block = unsafe_block_from_ptr( heap, ptr, &subheap )))
+    if (!(block = unsafe_block_from_ptr( heap, ptr )))
         WARN( "Failed to find block %p in heap %p\n", ptr, handle );
     else if (!(block_get_flags( block ) & BLOCK_FLAG_USER_INFO))
         WARN( "Block %p wasn't allocated with user info\n", ptr );
@@ -2128,7 +2137,6 @@ BOOLEAN WINAPI RtlSetUserFlagsHeap( HANDLE handle, ULONG flags, void *ptr, ULONG
     struct block *block;
     BOOLEAN ret = FALSE;
     struct heap *heap;
-    SUBHEAP *subheap;
     ULONG heap_flags;
 
     TRACE( "handle %p, flags %#lx, ptr %p, clear %#lx, set %#lx.\n", handle, flags, ptr, clear, set );
@@ -2142,7 +2150,7 @@ BOOLEAN WINAPI RtlSetUserFlagsHeap( HANDLE handle, ULONG flags, void *ptr, ULONG
     if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags ))) return TRUE;
 
     heap_lock( heap, heap_flags );
-    if (!(block = unsafe_block_from_ptr( heap, ptr, &subheap )))
+    if (!(block = unsafe_block_from_ptr( heap, ptr )))
         WARN( "Failed to find block %p in heap %p\n", ptr, handle );
     else if (!(block_get_flags( block ) & BLOCK_FLAG_USER_INFO))
         WARN( "Block %p wasn't allocated with user info\n", ptr );
-- 
GitLab


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

[PATCH 3/6] ntdll: Avoid clearing BLOCK_FLAG_USER_INFO in heap_reallocate.

[Rémi Bernon]

From: Rémi Bernon <rbernon(a)codeweavers.com>

---
 dlls/ntdll/heap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index ea1821aa674..21b284d2a0c 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1682,7 +1682,7 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
     }
 
     valgrind_notify_resize( block + 1, old_size, size );
-    block_set_flags( block, BLOCK_FLAG_USER_MASK, BLOCK_USER_FLAGS( flags ) );
+    block_set_flags( block, BLOCK_FLAG_USER_MASK & ~BLOCK_FLAG_USER_INFO, BLOCK_USER_FLAGS( flags ) );
     shrink_used_block( heap, flags, block, old_block_size, block_size, size );
 
     initialize_block( block, old_size, size, flags );
-- 
GitLab


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

[PATCH 4/6] ntdll: Stop locking heap to access block-local data.

[Rémi Bernon]

From: Rémi Bernon <rbernon(a)codeweavers.com>

This moves unsafe_block_from_ptr calls outside of the heap lock.

We assume here that concurrent call to another heap function on a block
being freed is undefined, and it should then be safe to do so:

* The block type or base offset never change after a block has been
  allocated and until it is freed.

* Block flags such as BLOCK_FLAG_LARGE, or BLOCK_FLAG_USER_INFO also
  never change after a block has been allocated.

* Other block flags are only read and modified inside the heap lock.
---
 dlls/ntdll/heap.c | 86 +++++++++++++++++++++++++----------------------
 1 file changed, 45 insertions(+), 41 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 21b284d2a0c..0a8694704d3 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1272,15 +1272,17 @@ static BOOL heap_validate( const struct heap *heap )
     return TRUE;
 }
 
-static inline struct block *unsafe_block_from_ptr( const struct heap *heap, const void *ptr )
+static inline struct block *unsafe_block_from_ptr( struct heap *heap, ULONG flags, const void *ptr )
 {
     struct block *block = (struct block *)ptr - 1;
     const char *err = NULL;
     SUBHEAP *subheap;
 
-    if (heap->flags & HEAP_VALIDATE)
+    if (flags & HEAP_VALIDATE)
     {
-        if (!heap_validate_ptr( heap, ptr )) return NULL;
+        heap_lock( heap, flags );
+        if (!heap_validate_ptr( heap, ptr )) block = NULL;
+        heap_unlock( heap, flags );
         return block;
     }
 
@@ -1596,14 +1598,10 @@ void *WINAPI DECLSPEC_HOTPATCH RtlAllocateHeap( HANDLE handle, ULONG flags, SIZE
 }
 
 
-static NTSTATUS heap_free( struct heap *heap, ULONG flags, void *ptr )
+static NTSTATUS heap_free( struct heap *heap, ULONG flags, struct block *block )
 {
-    struct block *block;
-
-    if (!(block = unsafe_block_from_ptr( heap, ptr ))) return STATUS_INVALID_PARAMETER;
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE) free_large_block( heap, block );
     else free_used_block( heap, flags, block );
-
     return STATUS_SUCCESS;
 }
 
@@ -1612,6 +1610,7 @@ static NTSTATUS heap_free( struct heap *heap, ULONG flags, void *ptr )
  */
 BOOLEAN WINAPI DECLSPEC_HOTPATCH RtlFreeHeap( HANDLE handle, ULONG flags, void *ptr )
 {
+    struct block *block;
     struct heap *heap;
     ULONG heap_flags;
     NTSTATUS status;
@@ -1622,10 +1621,12 @@ BOOLEAN WINAPI DECLSPEC_HOTPATCH RtlFreeHeap( HANDLE handle, ULONG flags, void *
 
     if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags )))
         status = STATUS_INVALID_PARAMETER;
+    else if (!(block = unsafe_block_from_ptr( heap, heap_flags, ptr )))
+        status = STATUS_INVALID_PARAMETER;
     else
     {
         heap_lock( heap, heap_flags );
-        status = heap_free( heap, heap_flags, ptr );
+        status = heap_free( heap, heap_flags, block );
         heap_unlock( heap, heap_flags );
     }
 
@@ -1635,14 +1636,13 @@ BOOLEAN WINAPI DECLSPEC_HOTPATCH RtlFreeHeap( HANDLE handle, ULONG flags, void *
 }
 
 
-static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
+static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, struct block *block,
                                  SIZE_T block_size, SIZE_T size, void **ret )
 {
     SIZE_T old_block_size, old_size;
-    struct block *next, *block;
+    struct block *next;
     NTSTATUS status;
 
-    if (!(block = unsafe_block_from_ptr( heap, ptr ))) return STATUS_INVALID_PARAMETER;
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE)
     {
         if (!(block = realloc_large_block( heap, flags, block, size ))) return STATUS_NO_MEMORY;
@@ -1675,7 +1675,7 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
             valgrind_notify_alloc( *ret, size, 0 );
             memcpy( *ret, block + 1, old_size );
             if (flags & HEAP_ZERO_MEMORY) memset( (char *)*ret + old_size, 0, size - old_size );
-            valgrind_notify_free( ptr );
+            valgrind_notify_free( block + 1 );
             free_used_block( heap, flags, block );
             return STATUS_SUCCESS;
         }
@@ -1697,6 +1697,7 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, void *ptr,
  */
 void *WINAPI RtlReAllocateHeap( HANDLE handle, ULONG flags, void *ptr, SIZE_T size )
 {
+    struct block *block;
     struct heap *heap;
     SIZE_T block_size;
     ULONG heap_flags;
@@ -1709,10 +1710,12 @@ void *WINAPI RtlReAllocateHeap( HANDLE handle, ULONG flags, void *ptr, SIZE_T si
         status = STATUS_INVALID_HANDLE;
     else if ((block_size = heap_get_block_size( heap, heap_flags, size )) == ~0U)
         status = STATUS_NO_MEMORY;
+    else if (!(block = unsafe_block_from_ptr( heap, heap_flags, ptr )))
+        status = STATUS_INVALID_PARAMETER;
     else
     {
         heap_lock( heap, heap_flags );
-        status = heap_reallocate( heap, heap_flags, ptr, block_size, size, &ret );
+        status = heap_reallocate( heap, heap_flags, block, block_size, size, &ret );
         heap_unlock( heap, heap_flags );
     }
 
@@ -1789,11 +1792,8 @@ BOOLEAN WINAPI RtlUnlockHeap( HANDLE handle )
 }
 
 
-static NTSTATUS heap_size( const struct heap *heap, const void *ptr, SIZE_T *size )
+static NTSTATUS heap_size( const struct heap *heap, struct block *block, SIZE_T *size )
 {
-    const struct block *block;
-
-    if (!(block = unsafe_block_from_ptr( heap, ptr ))) return STATUS_INVALID_PARAMETER;
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE)
     {
         const ARENA_LARGE *large_arena = CONTAINING_RECORD( block, ARENA_LARGE, block );
@@ -1810,16 +1810,19 @@ static NTSTATUS heap_size( const struct heap *heap, const void *ptr, SIZE_T *siz
 SIZE_T WINAPI RtlSizeHeap( HANDLE handle, ULONG flags, const void *ptr )
 {
     SIZE_T size = ~(SIZE_T)0;
+    struct block *block;
     struct heap *heap;
     ULONG heap_flags;
     NTSTATUS status;
 
     if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags )))
         status = STATUS_INVALID_PARAMETER;
+    else if (!(block = unsafe_block_from_ptr( heap, heap_flags, ptr )))
+        status = STATUS_INVALID_PARAMETER;
     else
     {
         heap_lock( heap, heap_flags );
-        status = heap_size( heap, ptr, &size );
+        status = heap_size( heap, block, &size );
         heap_unlock( heap, heap_flags );
     }
 
@@ -2061,12 +2064,10 @@ BOOLEAN WINAPI RtlGetUserInfoHeap( HANDLE handle, ULONG flags, void *ptr, void *
 
     *user_flags = 0;
 
-    if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags ))) return TRUE;
-
-    heap_lock( heap, heap_flags );
-    if (!(block = unsafe_block_from_ptr( heap, ptr )))
+    if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags )))
+        status = STATUS_SUCCESS;
+    else if (!(block = unsafe_block_from_ptr( heap, heap_flags, ptr )))
     {
-        WARN( "Failed to find block %p in heap %p\n", ptr, handle );
         status = STATUS_INVALID_PARAMETER;
         *user_value = 0;
     }
@@ -2080,12 +2081,15 @@ BOOLEAN WINAPI RtlGetUserInfoHeap( HANDLE handle, ULONG flags, void *ptr, void *
     }
     else
     {
+        heap_lock( heap, heap_flags );
+
         tmp = (char *)block + block_get_size( block ) - block->tail_size + sizeof(void *);
         if ((heap_flags & HEAP_TAIL_CHECKING_ENABLED) || RUNNING_ON_VALGRIND) tmp += BLOCK_ALIGN;
         *user_flags = *user_flags & ~HEAP_ADD_USER_INFO;
         *user_value = *(void **)tmp;
+
+        heap_unlock( heap, heap_flags );
     }
-    heap_unlock( heap, heap_flags );
 
     heap_set_status( heap, flags, status );
     return !status;
@@ -2097,20 +2101,19 @@ BOOLEAN WINAPI RtlGetUserInfoHeap( HANDLE handle, ULONG flags, void *ptr, void *
 BOOLEAN WINAPI RtlSetUserValueHeap( HANDLE handle, ULONG flags, void *ptr, void *user_value )
 {
     struct block *block;
-    BOOLEAN ret = FALSE;
     struct heap *heap;
     ULONG heap_flags;
+    BOOLEAN ret;
     char *tmp;
 
     TRACE( "handle %p, flags %#lx, ptr %p, user_value %p.\n", handle, flags, ptr, user_value );
 
-    if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags ))) return TRUE;
-
-    heap_lock( heap, heap_flags );
-    if (!(block = unsafe_block_from_ptr( heap, ptr )))
-        WARN( "Failed to find block %p in heap %p\n", ptr, handle );
+    if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags )))
+        ret = TRUE;
+    else if (!(block = unsafe_block_from_ptr( heap, heap_flags, ptr )))
+        ret = FALSE;
     else if (!(block_get_flags( block ) & BLOCK_FLAG_USER_INFO))
-        WARN( "Block %p wasn't allocated with user info\n", ptr );
+        ret = FALSE;
     else if (block_get_flags( block ) & BLOCK_FLAG_LARGE)
     {
         ARENA_LARGE *large = CONTAINING_RECORD( block, ARENA_LARGE, block );
@@ -2119,12 +2122,15 @@ BOOLEAN WINAPI RtlSetUserValueHeap( HANDLE handle, ULONG flags, void *ptr, void
     }
     else
     {
+        heap_lock( heap, heap_flags );
+
         tmp = (char *)block + block_get_size( block ) - block->tail_size + sizeof(void *);
         if ((heap_flags & HEAP_TAIL_CHECKING_ENABLED) || RUNNING_ON_VALGRIND) tmp += BLOCK_ALIGN;
         *(void **)tmp = user_value;
         ret = TRUE;
+
+        heap_unlock( heap, heap_flags );
     }
-    heap_unlock( heap, heap_flags );
 
     return ret;
 }
@@ -2135,9 +2141,9 @@ BOOLEAN WINAPI RtlSetUserValueHeap( HANDLE handle, ULONG flags, void *ptr, void
 BOOLEAN WINAPI RtlSetUserFlagsHeap( HANDLE handle, ULONG flags, void *ptr, ULONG clear, ULONG set )
 {
     struct block *block;
-    BOOLEAN ret = FALSE;
     struct heap *heap;
     ULONG heap_flags;
+    BOOLEAN ret;
 
     TRACE( "handle %p, flags %#lx, ptr %p, clear %#lx, set %#lx.\n", handle, flags, ptr, clear, set );
 
@@ -2147,19 +2153,17 @@ BOOLEAN WINAPI RtlSetUserFlagsHeap( HANDLE handle, ULONG flags, void *ptr, ULONG
         return FALSE;
     }
 
-    if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags ))) return TRUE;
-
-    heap_lock( heap, heap_flags );
-    if (!(block = unsafe_block_from_ptr( heap, ptr )))
-        WARN( "Failed to find block %p in heap %p\n", ptr, handle );
+    if (!(heap = unsafe_heap_from_handle( handle, flags, &heap_flags )))
+        ret = TRUE;
+    else if (!(block = unsafe_block_from_ptr( heap, heap_flags, ptr )))
+        ret = FALSE;
     else if (!(block_get_flags( block ) & BLOCK_FLAG_USER_INFO))
-        WARN( "Block %p wasn't allocated with user info\n", ptr );
+        ret = FALSE;
     else
     {
         block_set_flags( block, BLOCK_USER_FLAGS( clear ), BLOCK_USER_FLAGS( set ) );
         ret = TRUE;
     }
-    heap_unlock( heap, heap_flags );
 
     return ret;
 }
-- 
GitLab


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

[PATCH 5/6] ntdll: Inverse the control flow in heap_reallocate.

[Rémi Bernon]

From: Rémi Bernon <rbernon(a)codeweavers.com>

---
 dlls/ntdll/heap.c | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 0a8694704d3..4326199a07b 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1640,7 +1640,6 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, struct block *b
                                  SIZE_T block_size, SIZE_T size, void **ret )
 {
     SIZE_T old_block_size, old_size;
-    struct block *next;
     NTSTATUS status;
 
     if (block_get_flags( block ) & BLOCK_FLAG_LARGE)
@@ -1658,17 +1657,12 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, struct block *b
     if (block_size > old_block_size)
     {
         SUBHEAP *subheap = block_get_subheap( heap, block );
+        struct entry *entry;
+        struct block *next;
 
-        if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE) &&
-            block_size < HEAP_MIN_LARGE_BLOCK_SIZE && block_size <= old_block_size + block_get_size( next ))
-        {
-            /* The next block is free and large enough */
-            struct entry *entry = (struct entry *)next;
-            list_remove( &entry->entry );
-            old_block_size += block_get_size( next );
-            if (!subheap_commit( heap, subheap, block, block_size )) return STATUS_NO_MEMORY;
-        }
-        else
+        if (!(next = next_block( subheap, block )) || !(block_get_flags( next ) & BLOCK_FLAG_FREE) ||
+            block_size >= HEAP_MIN_LARGE_BLOCK_SIZE ||
+            block_size > old_block_size + block_get_size( next ))
         {
             if (flags & HEAP_REALLOC_IN_PLACE_ONLY) return STATUS_NO_MEMORY;
             if ((status = heap_allocate( heap, flags & ~HEAP_ZERO_MEMORY, block_size, size, ret ))) return status;
@@ -1679,6 +1673,12 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, struct block *b
             free_used_block( heap, flags, block );
             return STATUS_SUCCESS;
         }
+
+        /* The next block is free and large enough */
+        entry = (struct entry *)next;
+        list_remove( &entry->entry );
+        old_block_size += block_get_size( next );
+        if (!subheap_commit( heap, subheap, block, block_size )) return STATUS_NO_MEMORY;
     }
 
     valgrind_notify_resize( block + 1, old_size, size );
-- 
GitLab


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

[PATCH 6/6] ntdll: Reallocate a new block if we failed to commit.

[Rémi Bernon]

From: Rémi Bernon <rbernon(a)codeweavers.com>

---
 dlls/ntdll/heap.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 4326199a07b..0c7300f8055 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1662,7 +1662,7 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, struct block *b
 
         if (!(next = next_block( subheap, block )) || !(block_get_flags( next ) & BLOCK_FLAG_FREE) ||
             block_size >= HEAP_MIN_LARGE_BLOCK_SIZE ||
-            block_size > old_block_size + block_get_size( next ))
+            block_size > old_block_size + block_get_size( next ) || !subheap_commit( heap, subheap, block, block_size ))
         {
             if (flags & HEAP_REALLOC_IN_PLACE_ONLY) return STATUS_NO_MEMORY;
             if ((status = heap_allocate( heap, flags & ~HEAP_ZERO_MEMORY, block_size, size, ret ))) return status;
@@ -1678,7 +1678,6 @@ static NTSTATUS heap_reallocate( struct heap *heap, ULONG flags, struct block *b
         entry = (struct entry *)next;
         list_remove( &entry->entry );
         old_block_size += block_get_size( next );
-        if (!subheap_commit( heap, subheap, block, block_size )) return STATUS_NO_MEMORY;
     }
 
     valgrind_notify_resize( block + 1, old_size, size );
-- 
GitLab

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