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);
Signed-off-by: Rémi Bernon rbernon@codeweavers.com --- dlls/ntdll/heap.c | 42 +++++++++++++++++++++++++++++++----------- 1 file changed, 31 insertions(+), 11 deletions(-)
diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 31a7ba18d61..b7dab61dcd9 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -1004,20 +1004,13 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags,
/*********************************************************************** - * HEAP_FindFreeBlock - * - * Find a free block at least as large as the requested size, and make sure - * the requested size is committed. + * find_free_block_in_list */ -static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size, - SUBHEAP **ppSubHeap ) +static ARENA_FREE *find_free_block_in_list( HEAP *heap, SIZE_T size, FREE_LIST_ENTRY *pEntry, + SUBHEAP **ppSubHeap ) { SUBHEAP *subheap; struct list *ptr; - SIZE_T total_size; - FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( size + sizeof(ARENA_INUSE) ); - - /* Find a suitable free list, and in it find a block large enough */
ptr = &pEntry->arena.entry; while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr ))) @@ -1028,12 +1021,39 @@ static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size, if (arena_size >= size) { subheap = HEAP_FindSubHeap( heap, pArena ); - if (!HEAP_Commit( subheap, (ARENA_INUSE *)pArena, size )) return NULL; *ppSubHeap = subheap; return pArena; } }
+ return NULL; +} + + +/*********************************************************************** + * HEAP_FindFreeBlock + * + * Find a free block at least as large as the requested size, and make sure + * the requested size is committed. + */ +static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size, + SUBHEAP **ppSubHeap ) +{ + SUBHEAP *subheap; + SIZE_T total_size, index = get_freelist_index( size + sizeof(ARENA_INUSE) ); + FREE_LIST_ENTRY *pEntry = NULL; + ARENA_FREE *pArena; + + /* Find a suitable free list, and in it find a block large enough */ + + if (index < HEAP_NB_FREE_LISTS) pEntry = heap->freeList + index; + + if (pEntry && (pArena = find_free_block_in_list( heap, size, pEntry, ppSubHeap ))) + { + if (!HEAP_Commit( *ppSubHeap, (ARENA_INUSE *)pArena, size )) return NULL; + return pArena; + } + /* If no block was found, attempt to grow the heap */
if (!(heap->flags & HEAP_GROWABLE))
Origin patch from: Sebastian Lackner sebastian@fds-team.de Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=43224
Signed-off-by: Rémi Bernon rbernon@codeweavers.com --- dlls/ntdll/heap.c | 132 +++++++++++++++++++++++++++++++++++++++------- 1 file changed, 112 insertions(+), 20 deletions(-)
diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index b7dab61dcd9..f53f114d38f 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -36,6 +36,7 @@ #include "winternl.h" #include "ntdll_misc.h" #include "wine/list.h" +#include "wine/rbtree.h" #include "wine/debug.h" #include "wine/server.h"
@@ -58,6 +59,7 @@ typedef struct tagARENA_FREE DWORD size; /* Block size; must be the first field */ DWORD magic; /* Magic number */ struct list entry; /* Entry in free list */ + struct wine_rb_entry tree_entry; /* Entry in free tree */ } ARENA_FREE;
typedef struct @@ -99,7 +101,7 @@ C_ASSERT( sizeof(ARENA_LARGE) % LARGE_ALIGNMENT == 0 );
/* minimum data size (without arenas) of an allocated block */ /* make sure that it's larger than a free list entry */ -#define HEAP_MIN_DATA_SIZE ROUND_SIZE(2 * sizeof(struct list)) +#define HEAP_MIN_DATA_SIZE ROUND_SIZE(4 * sizeof(struct list)) #define HEAP_MIN_ARENA_SIZE (HEAP_MIN_DATA_SIZE + sizeof(ARENA_INUSE)) /* minimum size that must remain to shrink an allocated block */ #define HEAP_MIN_SHRINK_SIZE (HEAP_MIN_DATA_SIZE+sizeof(ARENA_FREE)) @@ -127,6 +129,8 @@ typedef union void *alignment[4]; } FREE_LIST_ENTRY;
+C_ASSERT(HEAP_MIN_DATA_SIZE >= sizeof(FREE_LIST_ENTRY)); + struct tagHEAP;
typedef struct tagSUBHEAP @@ -165,6 +169,7 @@ typedef struct tagHEAP ARENA_INUSE **pending_free; /* Ring buffer for pending free requests */ RTL_CRITICAL_SECTION critSection; /* Critical section for serialization */ FREE_LIST_ENTRY *freeList; /* Free lists */ + struct wine_rb_tree free_tree; /* Free tree for large blocks */ } HEAP;
#define HEAP_MAGIC ((DWORD)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24))) @@ -314,8 +319,9 @@ static inline unsigned int get_freelist_index( SIZE_T size ) return (size - HEAP_MIN_ARENA_SIZE) / ALIGNMENT;
for (i = HEAP_NB_SMALL_FREE_LISTS; i < HEAP_NB_FREE_LISTS - 1; i++) - if (size <= HEAP_freeListSizes[i - HEAP_NB_SMALL_FREE_LISTS]) break; - return i; + if (size <= HEAP_freeListSizes[i - HEAP_NB_SMALL_FREE_LISTS]) return i; + + return HEAP_NB_FREE_LISTS; }
/* get the memory protection type to use for a given heap */ @@ -353,6 +359,9 @@ static void HEAP_Dump( HEAP *heap ) LIST_ENTRY( heap->freeList[i].arena.entry.prev, ARENA_FREE, entry ), LIST_ENTRY( heap->freeList[i].arena.entry.next, ARENA_FREE, entry ));
+ TRACE( "free %08x: root=%p\n", (ULONG)(HEAP_MIN_ARENA_SIZE + HEAP_NB_FREE_LISTS * ALIGNMENT), + heap->free_tree.root ? LIST_ENTRY( heap->free_tree.root, ARENA_FREE, tree_entry ) : NULL ); + LIST_FOR_EACH_ENTRY( subheap, &heap->subheap_list, SUBHEAP, entry ) { SIZE_T freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize; @@ -366,11 +375,27 @@ static void HEAP_Dump( HEAP *heap ) if (*(DWORD *)ptr & ARENA_FLAG_FREE) { ARENA_FREE *pArena = (ARENA_FREE *)ptr; - TRACE( "%p %08x free %08x prev=%p next=%p\n", - pArena, pArena->magic, - pArena->size & ARENA_SIZE_MASK, - LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ), - LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ) ); + SIZE_T index = get_freelist_index( (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena) ); + + if (index < HEAP_NB_FREE_LISTS) + { + TRACE( "%p %08x free %08x prev=%p next=%p\n", pArena, pArena->magic, + pArena->size & ARENA_SIZE_MASK, LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ), + LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ) ); + } + else + { + ARENA_FREE *parent = NULL, *left = NULL, *right = NULL; + if (pArena->tree_entry.parent) + parent = WINE_RB_ENTRY_VALUE( pArena->tree_entry.parent, ARENA_FREE, tree_entry ); + if (pArena->tree_entry.left) + left = WINE_RB_ENTRY_VALUE( pArena->tree_entry.left, ARENA_FREE, tree_entry ); + if (pArena->tree_entry.right) + right = WINE_RB_ENTRY_VALUE( pArena->tree_entry.right, ARENA_FREE, tree_entry ); + TRACE( "%p %08x free %08x parent=%p left=%p right=%p\n", pArena, pArena->magic, + pArena->size & ARENA_SIZE_MASK, parent, left, right ); + } + ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK); arenaSize += sizeof(ARENA_FREE); freeSize += pArena->size & ARENA_SIZE_MASK; @@ -478,8 +503,10 @@ static HEAP *HEAP_GetPtr( */ static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL last ) { - FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( pArena->size + sizeof(*pArena) ); - if (last) + SIZE_T index = get_freelist_index( pArena->size + sizeof(*pArena) ); + FREE_LIST_ENTRY *pEntry = heap->freeList + index; + if (index == HEAP_NB_FREE_LISTS) wine_rb_put( &heap->free_tree, &pArena->size, &pArena->tree_entry ); + else if (last) { /* insert at end of free list, i.e. before the next free list entry */ pEntry++; @@ -498,11 +525,13 @@ static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL la /*********************************************************************** * HEAP_DeleteFreeBlock * - * Delete a free block from the free list. + * Delete a free block from the free list or free tree. */ static inline void HEAP_DeleteFreeBlock( HEAP *heap, ARENA_FREE *pArena ) { - list_remove( &pArena->entry ); + SIZE_T index = get_freelist_index( (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena) ); + if (index == HEAP_NB_FREE_LISTS) wine_rb_remove( &heap->free_tree, &pArena->tree_entry ); + else list_remove( &pArena->entry ); }
@@ -881,6 +910,25 @@ static BOOL validate_large_arena( HEAP *heap, const ARENA_LARGE *arena, BOOL qui return TRUE; }
+/*********************************************************************** + * free_tree_get_arena_size + */ +static inline DWORD free_tree_get_arena_size( const struct wine_rb_entry *entry ) +{ + ARENA_FREE *arena = WINE_RB_ENTRY_VALUE( entry, ARENA_FREE, tree_entry ); + return (arena->size & ARENA_SIZE_MASK); +} + +/*********************************************************************** + * free_tree_arena_compare + */ +static inline int free_tree_arena_compare( const void *key, const struct wine_rb_entry *entry ) +{ + DWORD arena_size = free_tree_get_arena_size( entry ); + if (*(DWORD *)key > arena_size) return 1; + else if (*(DWORD *)key < arena_size) return -1; + else return entry->left ? 1 : -1; +}
/*********************************************************************** * HEAP_CreateSubHeap @@ -962,6 +1010,8 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags, if (i) list_add_after( &pEntry[-1].arena.entry, &pEntry->arena.entry ); }
+ wine_rb_init( &heap->free_tree, free_tree_arena_compare ); + /* Initialize critical section */
if (!processHeap) /* do it by hand to avoid memory allocations */ @@ -1003,6 +1053,34 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags, }
+/*********************************************************************** + * find_free_block_in_tree + */ +static struct wine_rb_entry *find_free_block_in_tree( struct wine_rb_entry *entry, DWORD arena_size ) +{ + for (;;) + { + if (!entry) return NULL; + if (free_tree_get_arena_size( entry ) >= arena_size) break; + entry = entry->right; + } + + for (;;) + { + if (!entry->left) return entry; + if (free_tree_get_arena_size( entry->left ) < arena_size) break; + entry = entry->left; + } + + if (entry->left->right) + { + struct wine_rb_entry *ret; + if ((ret = find_free_block_in_tree( entry->left->right, arena_size ))) return ret; + } + + return entry; +} + /*********************************************************************** * find_free_block_in_list */ @@ -1040,6 +1118,7 @@ static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size, SUBHEAP **ppSubHeap ) { SUBHEAP *subheap; + struct wine_rb_entry *entry; SIZE_T total_size, index = get_freelist_index( size + sizeof(ARENA_INUSE) ); FREE_LIST_ENTRY *pEntry = NULL; ARENA_FREE *pArena; @@ -1054,6 +1133,16 @@ static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size, return pArena; }
+ /* Find a suitable block from the free tree */ + + if ((entry = find_free_block_in_tree( heap->free_tree.root, size + sizeof(ARENA_INUSE) - sizeof(ARENA_FREE) ))) + { + pArena = WINE_RB_ENTRY_VALUE( entry, ARENA_FREE, tree_entry ); + *ppSubHeap = HEAP_FindSubHeap( heap, pArena ); + if (!HEAP_Commit( *ppSubHeap, (ARENA_INUSE *)pArena, size )) return NULL; + return pArena; + } + /* If no block was found, attempt to grow the heap */
if (!(heap->flags & HEAP_GROWABLE)) @@ -1114,8 +1203,8 @@ static BOOL HEAP_IsValidArenaPtr( const HEAP *heap, const ARENA_FREE *ptr ) static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena ) { DWORD flags = subheap->heap->flags; - SIZE_T size; - ARENA_FREE *prev, *next; + SIZE_T size, index; + ARENA_FREE *prev = NULL, *next = NULL; char *heapEnd = (char *)subheap->base + subheap->size;
/* Check for unaligned pointers */ @@ -1146,31 +1235,34 @@ static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena ) ERR("Heap %p: bad size %08lx for free arena %p\n", subheap->heap, size, pArena ); return FALSE; } + index = get_freelist_index( size + sizeof(*pArena) ); /* Check that next pointer is valid */ - next = LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ); - if (!HEAP_IsValidArenaPtr( subheap->heap, next )) + if (index < HEAP_NB_FREE_LISTS) next = LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ); + else if (pArena->tree_entry.right) next = WINE_RB_ENTRY_VALUE( pArena->tree_entry.right, ARENA_FREE, tree_entry ); + if (next && !HEAP_IsValidArenaPtr( subheap->heap, next )) { ERR("Heap %p: bad next ptr %p for arena %p\n", subheap->heap, next, pArena ); return FALSE; } /* Check that next arena is free */ - if (!(next->size & ARENA_FLAG_FREE) || (next->magic != ARENA_FREE_MAGIC)) + if (next && (!(next->size & ARENA_FLAG_FREE) || (next->magic != ARENA_FREE_MAGIC))) { ERR("Heap %p: next arena %p invalid for %p\n", subheap->heap, next, pArena ); return FALSE; } /* Check that prev pointer is valid */ - prev = LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ); - if (!HEAP_IsValidArenaPtr( subheap->heap, prev )) + if (index < HEAP_NB_FREE_LISTS) prev = LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ); + else if (pArena->tree_entry.left) prev = WINE_RB_ENTRY_VALUE( pArena->tree_entry.left, ARENA_FREE, tree_entry ); + if (prev && !HEAP_IsValidArenaPtr( subheap->heap, prev )) { ERR("Heap %p: bad prev ptr %p for arena %p\n", subheap->heap, prev, pArena ); return FALSE; } /* Check that prev arena is free */ - if (!(prev->size & ARENA_FLAG_FREE) || (prev->magic != ARENA_FREE_MAGIC)) + if (prev && (!(prev->size & ARENA_FLAG_FREE) || (prev->magic != ARENA_FREE_MAGIC))) { /* this often means that the prev arena got overwritten * by a memory write before that prev arena */
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@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 );@@ -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);
On 1/15/21 4:20 PM, Paul Gofman wrote:
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.
Ah, I wasn't aware of such issues, and I didn't see any myself so far.
I'm not entirely sure what to do about use-after free in general, and it could be an issue, even with the current simpler linked list-only struct.
There is already a pending_free buffer that is supposed to mitigate such issues, and it should handle these patches in the same way. Maybe it's just not big enough.
About the LFH implementation:
It should solve the performance problem, but it wasn't specifically designed to be compatible with whatever Windows is doing at the moment.
It may not be worse than the current Wine heap though, as AFAICS, Windows implementation already varies quite a bit between Windows versions, and none apparently match what Wine is doing (for instance looking at block headers magic and fields).
What's probably more or less compatible already is the tagHEAP fields, at least for the flags and such, which are still used for the returned heap pointers.
Cheers,
-
Paul Gofman -
Rémi Bernon