From: Sebastian Lackner sebastian@fds-team.de
Signed-off-by: Rémi Bernon rbernon@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);