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

[Rémi Bernon]

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);
-- 
2.30.0