[PATCH 3/3] ntdll: Use an rbtree for the large free blocks.
Rémi Bernon
rbernon at codeweavers.com
Fri Jan 15 09:11:22 CST 2021
Origin patch from: Sebastian Lackner <sebastian at fds-team.de>
Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=43224
Signed-off-by: Rémi Bernon <rbernon at 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 */
--
2.30.0
More information about the wine-devel
mailing list