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 */