[PATCH 1/3] ntdll: Introduce new HEAP_DeleteFreeBlock helper.

[Paul Gofman]

The structure introduced by these patches appears to be more vulnerable
to fatal destruction by app's out of bound and use after free accesses.
I've tracked several memory corruption bugs in the past which were
reproducible with these patches but not on Windows and not with Wine's
current heap implementation. Do you think it really worth it, given it
doesn't bring the heap structure closer to that on Windows, and doesn't
solve many heap related performance degradation issues? I thought your
LFH implementation is better both for compatibility and performance.

On 1/15/21 18:11, Rémi Bernon wrote:
> From: Sebastian Lackner <sebastian at fds-team.de>
>
> Signed-off-by: Rémi Bernon <rbernon at codeweavers.com>
> ---
>
> This is a patch series that has been in Wine Staging for ages, and that
> I've cleaned up a bit.
>
> The staging patch series actually does more than this, as it also
> increase the number of free lists by a lot and does some state caching
> and other small optimisations, but this rbtree optimization is the main
> source of performance improvement. [1]
>
> Although the series increases performance noticeably on synthethic
> benchmarks, as I measured in the past [2], it still isn't great in
> multi-threaded allocations scenarios, as it still uses a global lock.
>
> The patch series is in Wine Staging and in Proton though, so I thought
> it was still worth cleaning it up and sending it upstream, unless it is
> then considered not interesting enough.
>
> [1] I've split and analyzed each part of the patch separately in:
>
>   https://bugs.winehq.org/show_bug.cgi?id=49113#c9
>
> [2] https://www.winehq.org/pipermail/wine-devel/2020-May/165892.html
>
>  dlls/ntdll/heap.c | 24 ++++++++++++++++++------
>  1 file changed, 18 insertions(+), 6 deletions(-)
>
> diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
> index 88db935746a..31a7ba18d61 100644
> --- a/dlls/ntdll/heap.c
> +++ b/dlls/ntdll/heap.c
> @@ -3,6 +3,7 @@
>   *
>   * Copyright 1996 Alexandre Julliard
>   * Copyright 1998 Ulrich Weigand
> + * Copyright 2017 Sebastian Lackner
>   *
>   * This library is free software; you can redistribute it and/or
>   * modify it under the terms of the GNU Lesser General Public
> @@ -494,6 +495,17 @@ static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL la
>  }
>  
>  
> +/***********************************************************************
> + *           HEAP_DeleteFreeBlock
> + *
> + * Delete a free block from the free list.
> + */
> +static inline void HEAP_DeleteFreeBlock( HEAP *heap, ARENA_FREE *pArena )
> +{
> +    list_remove( &pArena->entry );
> +}
> +
> +
>  /***********************************************************************
>   *           HEAP_FindSubHeap
>   * Find the sub-heap containing a given address.
> @@ -602,7 +614,7 @@ static void HEAP_CreateFreeBlock( SUBHEAP *subheap, void *ptr, SIZE_T size )
>      {
>          /* Remove the next arena from the free list */
>          ARENA_FREE *pNext = (ARENA_FREE *)((char *)ptr + size);
> -        list_remove( &pNext->entry );
> +        HEAP_DeleteFreeBlock( subheap->heap, pNext );
>          size += (pNext->size & ARENA_SIZE_MASK) + sizeof(*pNext);
>          mark_block_free( pNext, sizeof(ARENA_FREE), flags );
>      }
> @@ -657,7 +669,7 @@ static void HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena )
>          pFree = *((ARENA_FREE **)pArena - 1);
>          size += (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
>          /* Remove it from the free list */
> -        list_remove( &pFree->entry );
> +        HEAP_DeleteFreeBlock( heap, pFree );
>      }
>      else pFree = (ARENA_FREE *)pArena;
>  
> @@ -677,7 +689,7 @@ static void HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena )
>  
>          size = 0;
>          /* Remove the free block from the list */
> -        list_remove( &pFree->entry );
> +        HEAP_DeleteFreeBlock( heap, pFree );
>          /* Remove the subheap from the list */
>          list_remove( &subheap->entry );
>          /* Free the memory */
> @@ -1694,7 +1706,7 @@ void * WINAPI DECLSPEC_HOTPATCH RtlAllocateHeap( HANDLE heap, ULONG flags, SIZE_
>  
>      /* Remove the arena from the free list */
>  
> -    list_remove( &pArena->entry );
> +    HEAP_DeleteFreeBlock( heapPtr, pArena );
>  
>      /* Build the in-use arena */
>  
> @@ -1851,7 +1863,7 @@ PVOID WINAPI RtlReAllocateHeap( HANDLE heap, ULONG flags, PVOID ptr, SIZE_T size
>          {
>              /* The next block is free and large enough */
>              ARENA_FREE *pFree = (ARENA_FREE *)pNext;
> -            list_remove( &pFree->entry );
> +            HEAP_DeleteFreeBlock( heapPtr, pFree );
>              pArena->size += (pFree->size & ARENA_SIZE_MASK) + sizeof(*pFree);
>              if (!HEAP_Commit( subheap, pArena, rounded_size )) goto oom;
>              notify_realloc( pArena + 1, oldActualSize, size );
> @@ -1869,7 +1881,7 @@ PVOID WINAPI RtlReAllocateHeap( HANDLE heap, ULONG flags, PVOID ptr, SIZE_T size
>  
>              /* Build the in-use arena */
>  
> -            list_remove( &pNew->entry );
> +            HEAP_DeleteFreeBlock( heapPtr, pNew );
>              pInUse = (ARENA_INUSE *)pNew;
>              pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE)
>                             + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);